File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Minimum connected dominating set construction in wireless networks under the beeping model

TitleMinimum connected dominating set construction in wireless networks under the beeping model
Authors
Issue Date2015
PublisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000359
Citation
The 2015 IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 26 April-1 May 2015. In IEEE Infocom Proceedings, 2015, p. 972-980 How to Cite?
AbstractDiscrete beeping is an extremely rigorous local broadcast model depending only on carrier sensing. It describes an anonymous broadcast network where the nodes do not need unique identifiers and have no knowledge about the topology and size of the network. Within such a model, time is divided into slots, and nodes can either beep or keep silent at each slot. We consider the problem of constructing a minimum dominating set (MDS) and a minimum connected dominating set (MCDS), respectively, under the discrete beeping model in this paper. By assuming that an upper bound N of the network size is known, we first propose and analyze a distributed synchronous algorithm termed BMDS for constructing a minimum dominating set (MDS) and then propose a distributed synchronous algorithm BCDS for CDS construction based on a maximal independent set (MIS) algorithm and a weakly CDS (WCDS). To our best knowledge, we are the first to study the MCDS construction under the discrete beeping model. We prove that the time complexity of BMDS is O(log2 N) rounds with constant approximation ratio of at most 2, and BCDS can converge to a CDS within O(log3 N) rounds.
DescriptionINFOCOM, IEEE Computer and Communications Societies, IEEE Annual Joint Conference
Open Access
Persistent Identifierhttp://hdl.handle.net/10722/219229
ISBN
ISSN

 

DC FieldValueLanguage
dc.contributor.authorYu, J-
dc.contributor.authorJia, L-
dc.contributor.authorYu, D-
dc.contributor.authorLi, G-
dc.contributor.authorCheng, X-
dc.date.accessioned2015-09-18T07:18:17Z-
dc.date.available2015-09-18T07:18:17Z-
dc.date.issued2015-
dc.identifier.citationThe 2015 IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 26 April-1 May 2015. In IEEE Infocom Proceedings, 2015, p. 972-980-
dc.identifier.isbn978-1-4799-8381-0-
dc.identifier.issn0743-166X-
dc.identifier.urihttp://hdl.handle.net/10722/219229-
dc.descriptionINFOCOM, IEEE Computer and Communications Societies, IEEE Annual Joint Conference-
dc.descriptionOpen Access-
dc.description.abstractDiscrete beeping is an extremely rigorous local broadcast model depending only on carrier sensing. It describes an anonymous broadcast network where the nodes do not need unique identifiers and have no knowledge about the topology and size of the network. Within such a model, time is divided into slots, and nodes can either beep or keep silent at each slot. We consider the problem of constructing a minimum dominating set (MDS) and a minimum connected dominating set (MCDS), respectively, under the discrete beeping model in this paper. By assuming that an upper bound N of the network size is known, we first propose and analyze a distributed synchronous algorithm termed BMDS for constructing a minimum dominating set (MDS) and then propose a distributed synchronous algorithm BCDS for CDS construction based on a maximal independent set (MIS) algorithm and a weakly CDS (WCDS). To our best knowledge, we are the first to study the MCDS construction under the discrete beeping model. We prove that the time complexity of BMDS is O(log2 N) rounds with constant approximation ratio of at most 2, and BCDS can converge to a CDS within O(log3 N) rounds.-
dc.languageeng-
dc.publisherIEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000359-
dc.relation.ispartofIEEE Infocom Proceedings-
dc.rightsIEEE Infocom Proceedings. Copyright © IEEE Computer Society.-
dc.rights©2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.-
dc.titleMinimum connected dominating set construction in wireless networks under the beeping model-
dc.typeConference_Paper-
dc.identifier.emailYu, D: dxyu@cs.hku.hk-
dc.description.naturelink_to_OA_fulltext-
dc.identifier.doi10.1109/INFOCOM.2015.7218469-
dc.identifier.hkuros254081-
dc.identifier.spage972-
dc.identifier.epage980-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 151104-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats