@inproceedings{118b77ed72d14114bbc53100ffb998ff, title = "Minimum-latency beaconing schedule in multihop wireless networks", 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. {\textcopyright} 2009 IEEE.", author = "Peng-Jun Wan and Xiaohua Xu and Lixin Wang and Xiaohua Jia and Park, {E. K.}", year = "2009", doi = "10.1109/INFCOM.2009.5062160", language = "English", isbn = "9781424435135", pages = "2340--2346", booktitle = "Proceedings - IEEE INFOCOM", note = "28th Conference on Computer Communications (IEEE INFOCOM 2009) ; Conference date: 19-04-2009 Through 25-04-2009", }