Thumbnail
Access Restriction
Open

Author Wan, Peng-Jun ♦ Wang, Zhu ♦ Du, Hongwei ♦ Huang, Scott C. -H. ♦ Wan, Zhiyuan
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Multihop Wireless Network ♦ First-fit Scheduling ♦ Constant-approximation Algorithm ♦ Approximation Algorithm ♦ Protocol Interference Model ♦ Shortest Schedule ♦ Uniform Interference Radius ♦ Arbitrary Interference Radius ♦ Abstract Beaconing ♦ Primitive Communication Task ♦ Efficient Implementation ♦ Synchronous Time-slots ♦ Fixed Distance ♦ Index Term Beaconing Schedule ♦ Physical Interference Model ♦ Physical Interference ♦ Greedy First-fit Manner ♦ Fixed-size Packet ♦ Interference Constraint ♦ Protocol Interference ♦ Problem Minimumlatency Beaconing Schedule
Abstract Abstract—Beaconing is a primitive communication task in which every node locally broadcasts a packet to all its neighbors within a fixed distance. Assume that all communications proceed in synchronous time-slots and each node can transmit at most one fixed-size packet in each time-slot. The problem Minimumlatency beaconing schedule (MLBS) in multihop wireless networks seeks a shortest schedule for beaconing subject to the interference constraint. MLBS has been intensively studied since the mid-1980s, but all assume the protocol interference model with uniform interference radii. In this paper, we first present a constant-approximation algorithm for MLBS under the protocol interference model with arbitrary interference radii. Then, we develop a constant-approximation algorithm for MLBS under the physical interference model. Both approximation algorithms have efficient implementations in a greedy first-fit manner. Index Terms—Beaconing schedule, protocol interference, physical interference, approximation algorithm I.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study