Conference Paper: An O(log n) distributed approximation algorithm for local broadcasting in unstructured wireless networks

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleAn O(log n) distributed approximation algorithm for local broadcasting in unstructured wireless networks
AuthorsYu, D
Hua, Q
Wang, Y
Lau, FCM
KeywordsDistributed algorithm
Local broadcasting
Randomized algorithm
Sinr model
Unstructured wireless networks
Issue Date2012
PublisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1800455
CitationThe 8th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS 2012), Hangzhou, China, 16-18 May 2012. In IEEE-DCOSS Proceedings, 2012, p. 132-139 [How to Cite?]
DOI: http://dx.doi.org/10.1109/DCOSS.2012.39
AbstractThe unstructured multi-hop radio network model, with asynchronous wake-up, no collision detection and little knowledge on the network topology, is proposed for capturing the particularly harsh characteristics of initially deployed wireless adhoc and sensor networks. In this paper, assuming such a practical model, we study a fundamental problem of both theoretical and practical interests - the local broadcasting problem. Given a set of nodes V where each node wants to broadcast a message to all its neighbors that are within a certain local broadcasting range R, the problem is to schedule all these requests in the fewest timeslots. By adopting the physical interference mode land without any knowledge on neighborhood, we give a new randomized distributed approximation algorithm for the local broadcasting problem with approximation ratio O (log n) where nis the number of nodes. This distributed approximation algorithm improves the state-of-the-art result in [22] by a logarithmic factor. © 2012 IEEE.
ISBN978-0-7695-4707-7
DOIhttp://dx.doi.org/10.1109/DCOSS.2012.39
DC Field
Value
dc.contributor.authorYu, D
dc.contributor.authorHua, Q
dc.contributor.authorWang, Y
dc.contributor.authorLau, FCM
dc.date.accessioned2012-10-18T08:49:49Z
dc.date.available2012-10-18T08:49:49Z
dc.date.issued2012
dc.description.abstractThe unstructured multi-hop radio network model, with asynchronous wake-up, no collision detection and little knowledge on the network topology, is proposed for capturing the particularly harsh characteristics of initially deployed wireless adhoc and sensor networks. In this paper, assuming such a practical model, we study a fundamental problem of both theoretical and practical interests - the local broadcasting problem. Given a set of nodes V where each node wants to broadcast a message to all its neighbors that are within a certain local broadcasting range R, the problem is to schedule all these requests in the fewest timeslots. By adopting the physical interference mode land without any knowledge on neighborhood, we give a new randomized distributed approximation algorithm for the local broadcasting problem with approximation ratio O (log n) where nis the number of nodes. This distributed approximation algorithm improves the state-of-the-art result in [22] by a logarithmic factor. © 2012 IEEE.
dc.description.naturepublished_or_final_version
dc.identifier.citationThe 8th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS 2012), Hangzhou, China, 16-18 May 2012. In IEEE-DCOSS Proceedings, 2012, p. 132-139 [How to Cite?]
DOI: http://dx.doi.org/10.1109/DCOSS.2012.39
dc.identifier.doihttp://dx.doi.org/10.1109/DCOSS.2012.39
dc.identifier.epage139
dc.identifier.hkuros211539
dc.identifier.isbn978-0-7695-4707-7
dc.identifier.scopuseid_2-s2.0-84864221157
dc.identifier.spage132
dc.identifier.urihttp://hdl.handle.net/10722/169308
dc.languageeng
dc.publisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1800455
dc.publisher.placeUnited States
dc.relation.ispartofInternational Conference on Distributed Computing in Sensor Systems Proceedings
dc.rightsInternational Conference on Distributed Computing in Sensor Systems Proceedings. Copyright © IEEE Computer Society.
dc.rights©2012 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
dc.subjectDistributed algorithm
dc.subjectLocal broadcasting
dc.subjectRandomized algorithm
dc.subjectSinr model
dc.subjectUnstructured wireless networks
dc.titleAn O(log n) distributed approximation algorithm for local broadcasting in unstructured wireless networks
dc.typeConference_Paper