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

TitleAn O(log n) distributed approximation algorithm for local broadcasting in unstructured wireless networks
Authors
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
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 How to Cite?
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. © 2012 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/169308
ISBN
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorYu, Den_US
dc.contributor.authorHua, Qen_US
dc.contributor.authorWang, Yen_US
dc.contributor.authorLau, FCMen_US
dc.date.accessioned2012-10-18T08:49:49Z-
dc.date.available2012-10-18T08:49:49Z-
dc.date.issued2012en_US
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-139en_US
dc.identifier.isbn978-0-7695-4707-7-
dc.identifier.urihttp://hdl.handle.net/10722/169308-
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.languageengen_US
dc.publisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1800455-
dc.relation.ispartofInternational Conference on Distributed Computing in Sensor Systems Proceedingsen_US
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 networksen_US
dc.typeConference_Paperen_US
dc.identifier.emailYu, D: dxyu@hku.hken_US
dc.identifier.emailHua, Q: huaqs@hku.hken_US
dc.identifier.emailLau, FCM: fcmlau@cs.hku.hk-
dc.identifier.authorityLau, FCM=rp00221en_US
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/DCOSS.2012.39-
dc.identifier.scopuseid_2-s2.0-84864221157-
dc.identifier.hkuros211539en_US
dc.identifier.spage132en_US
dc.identifier.epage139en_US
dc.identifier.isiWOS:000309235500019-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 130506-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats