Minimum-latency beaconing schedule in multihop wireless networks

Peng-Jun Wan; Xiaohua Xu; Lixin Wang; Xiaohua Jia; E. K. Park

doi:10.1109/INFCOM.2009.5062160

Minimum-latency beaconing schedule in multihop wireless networks

Peng-Jun Wan, Xiaohua Xu, Lixin Wang, Xiaohua Jia, E. K. Park

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

15 Citations (Scopus)

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. © 2009 IEEE.

Original language	English
Title of host publication	Proceedings - IEEE INFOCOM
Pages	2340-2346
DOIs	https://doi.org/10.1109/INFCOM.2009.5062160
Publication status	Published - 2009
Event	28th Conference on Computer Communications (IEEE INFOCOM 2009) - Rio de Janeiro, Brazil Duration: 19 Apr 2009 → 25 Apr 2009

Publication series

Name
ISSN (Print)	0743-166X

Conference

Conference	28th Conference on Computer Communications (IEEE INFOCOM 2009)
Place	Brazil
City	Rio de Janeiro
Period	19/04/09 → 25/04/09

Access Output

10.1109/INFCOM.2009.5062160

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@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",

}

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 - RGC 32 - Refereed conference paper (with host publication)

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 -

Minimum-latency beaconing schedule in multihop wireless networks

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this