File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: An O(log n) distributed approximation algorithm for local broadcasting in unstructured wireless networks
  • Basic View
  • Metadata View
  • XML View
TitleAn O(log n) distributed approximation algorithm for local broadcasting in unstructured wireless networks
 
AuthorsYu, D1
Hua, Q
Wang, Y2
Lau, FCM1
 
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 FieldValue
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
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Yu, D</contributor.author>
<contributor.author>Hua, Q</contributor.author>
<contributor.author>Wang, Y</contributor.author>
<contributor.author>Lau, FCM</contributor.author>
<date.accessioned>2012-10-18T08:49:49Z</date.accessioned>
<date.available>2012-10-18T08:49:49Z</date.available>
<date.issued>2012</date.issued>
<identifier.citation>The 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</identifier.citation>
<identifier.isbn>978-0-7695-4707-7</identifier.isbn>
<identifier.uri>http://hdl.handle.net/10722/169308</identifier.uri>
<description.abstract>The 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. &#169; 2012 IEEE.</description.abstract>
<language>eng</language>
<publisher>IEEE Computer Society. The Journal&apos;s web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1800455</publisher>
<relation.ispartof>International Conference on Distributed Computing in Sensor Systems Proceedings</relation.ispartof>
<rights>International Conference on Distributed Computing in Sensor Systems Proceedings. Copyright &#169; IEEE Computer Society.</rights>
<rights>&#169;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.</rights>
<rights>Creative Commons: Attribution 3.0 Hong Kong License</rights>
<subject>Distributed algorithm</subject>
<subject>Local broadcasting</subject>
<subject>Randomized algorithm</subject>
<subject>Sinr model</subject>
<subject>Unstructured wireless networks</subject>
<title>An O(log n) distributed approximation algorithm for local broadcasting in unstructured wireless networks</title>
<type>Conference_Paper</type>
<description.nature>published_or_final_version</description.nature>
<identifier.doi>10.1109/DCOSS.2012.39</identifier.doi>
<identifier.scopus>eid_2-s2.0-84864221157</identifier.scopus>
<identifier.hkuros>211539</identifier.hkuros>
<identifier.spage>132</identifier.spage>
<identifier.epage>139</identifier.epage>
<publisher.place>United States</publisher.place>
<bitstream.url>http://hub.hku.hk/bitstream/10722/169308/1/Content.pdf</bitstream.url>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Tsinghua University