Title :
Minimum-Latency Beaconing Schedule in Multihop Wireless Networks
Author :
Wan, Peng-Jun ; Xu, XiaoHua ; Wang, Lixin ; Jia, Xiaohua ; Park, E.K.
Author_Institution :
Dept. of Comput. Sci., Illinois Inst. of Technol., Chicago, IL
Abstract :
Minimum-latency beaconing schedule (MLBS) in synchronous multihop wireless networks seeks a schedule for beaconing with the shortest latency. This problem is NP-hard even when the interference radius is equal to the transmission radius. All prior works assume that the interference radius is equal to the transmission radius, and the best-known approximation ratio for MLBS under this special interference model is 7. In this paper, we present a new approximation algorithm called strip coloring for MLBS under the general protocol interference model. Its approximation ratio is at most 5 when the interference radius is equal to transmission radius, and is between 3 and 6 in general.
Keywords :
approximation theory; communication complexity; interference (signal); protocols; radio networks; scheduling; NP-hard; approximation ratio; general protocol interference model; interference radius; minimum-latency beaconing scheduling; shortest latency; strip coloring; synchronous multihop wireless networks; transmission radius; Communications Society; Computer science; Delay; Interference; Network topology; Peer to peer computing; Processor scheduling; Protocols; Spread spectrum communication; Wireless networks;
Conference_Titel :
INFOCOM 2009, IEEE
Conference_Location :
Rio de Janeiro
Print_ISBN :
978-1-4244-3512-8
Electronic_ISBN :
0743-166X
DOI :
10.1109/INFCOM.2009.5062160
