File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/INFOCOM.2015.7218469
- Scopus: eid_2-s2.0-84954214001
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Minimum connected dominating set construction in wireless networks under the beeping model
Title | Minimum connected dominating set construction in wireless networks under the beeping model |
---|---|
Authors | |
Issue Date | 2015 |
Publisher | IEEE 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? |
Abstract | Discrete 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. |
Description | INFOCOM, IEEE Computer and Communications Societies, IEEE Annual Joint Conference Open Access |
Persistent Identifier | http://hdl.handle.net/10722/219229 |
ISBN | |
ISSN | 2023 SCImago Journal Rankings: 2.865 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Yu, J | - |
dc.contributor.author | Jia, L | - |
dc.contributor.author | Yu, D | - |
dc.contributor.author | Li, G | - |
dc.contributor.author | Cheng, X | - |
dc.date.accessioned | 2015-09-18T07:18:17Z | - |
dc.date.available | 2015-09-18T07:18:17Z | - |
dc.date.issued | 2015 | - |
dc.identifier.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 | - |
dc.identifier.isbn | 978-1-4799-8381-0 | - |
dc.identifier.issn | 0743-166X | - |
dc.identifier.uri | http://hdl.handle.net/10722/219229 | - |
dc.description | INFOCOM, IEEE Computer and Communications Societies, IEEE Annual Joint Conference | - |
dc.description | Open Access | - |
dc.description.abstract | Discrete 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.language | eng | - |
dc.publisher | IEEE Computer Society. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/conhome.jsp?punumber=1000359 | - |
dc.relation.ispartof | IEEE Infocom Proceedings | - |
dc.rights | IEEE 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.title | Minimum connected dominating set construction in wireless networks under the beeping model | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Yu, D: dxyu@cs.hku.hk | - |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1109/INFOCOM.2015.7218469 | - |
dc.identifier.scopus | eid_2-s2.0-84954214001 | - |
dc.identifier.hkuros | 254081 | - |
dc.identifier.spage | 972 | - |
dc.identifier.epage | 980 | - |
dc.publisher.place | United States | - |
dc.customcontrol.immutable | sml 151104 | - |
dc.identifier.issnl | 0743-166X | - |