TY - GEN
T1 - Minimum-latency beaconing schedule in multihop wireless networks
AU - Wan, Peng-Jun
AU - Xu, Xiaohua
AU - Wang, Lixin
AU - Jia, Xiaohua
AU - Park, E. K.
PY - 2009
Y1 - 2009
N2 - 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. © 2009 IEEE.
AB - 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. © 2009 IEEE.
UR - http://www.scopus.com/inward/record.url?scp=70349656199&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-70349656199&origin=recordpage
U2 - 10.1109/INFCOM.2009.5062160
DO - 10.1109/INFCOM.2009.5062160
M3 - 32_Refereed conference paper (with ISBN/ISSN)
SN - 9781424435135
SP - 2340
EP - 2346
BT - Proceedings - IEEE INFOCOM
T2 - 28th Conference on Computer Communications (IEEE INFOCOM 2009)
Y2 - 19 April 2009 through 25 April 2009
ER -