An improved greedy construction of minimum connected dominating sets in wireless networks

Ariyam Das; Chittaranjan Mandal; Christopher Reade; Manish Aasawat

doi:10.1109/WCNC.2011.5779233

An improved greedy construction of minimum connected dominating sets in wireless networks

Ariyam Das
, Chittaranjan Mandal
, Christopher Reade
, Manish Aasawat

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

A minimum connected dominating set (MCDS) offers an optimized way of sending messages in wireless networks. However, constructing a MCDS is a NP-complete problem. Many heuristics based approximation algorithms for MCDS problems have been previously reported. In this paper, we propose a new degree-based multiple leaders initiated greedy approximation algorithm (PSCASTS) based on the selection of a pseudo- dominating set and an improved Steiner tree construction. We also show that our PSCASTS outperforms existing CDS construction algorithms in terms of CDS size and construction costs. The simulation results show that PSCASTS constructs better non-trivial CDSs for networks with uniform, nearly- uniform and random distribution of sensor nodes. While PSCASTS retains the current best performance ratio of (4.8+ln5)|opt|+1.2, |opt| being the size of an optimal CDS of the network, it has the best time complexity of O(D), where D is the network diameter.

Original language	English
Title of host publication	Published in the proceedings ISBN: 9781612842554. Organising Body: Institute of Electrical and Electronics Engineers Organising Body: Institute of Electrical and Electronics Engineers
Pages	790-795
DOIs	https://doi.org/10.1109/WCNC.2011.5779233
Publication status	Published - 30 Mar 2011
Externally published	Yes

Bibliographical note

Note: Published in the proceedings ISBN: 9781612842554.

Organising Body: Institute of Electrical and Electronics Engineers

Organising Body: Institute of Electrical and Electronics Engineers

Keywords

Connected dominating set (CDS)
maximal independent set (MIS)
Steiner tree
routing backbone
unit disk graph (UDG)
Computer science and informatics

Access to Document

10.1109/WCNC.2011.5779233

http://dx.doi.org/10.1109/WCNC.2011.5779233

1 Paper

An improved greedy construction of minimum connected dominating sets in wireless networks
Das, A., Mandal, C., Reade, C. & Aasawat, M., 30 Mar 2011.
Research output: Contribution to conference › Paper › peer-review

Cite this

Das, A., Mandal, C., Reade, C., & Aasawat, M. (2011). An improved greedy construction of minimum connected dominating sets in wireless networks. In Published in the proceedings ISBN: 9781612842554. Organising Body: Institute of Electrical and Electronics Engineers Organising Body: Institute of Electrical and Electronics Engineers (pp. 790-795) https://doi.org/10.1109/WCNC.2011.5779233

@inproceedings{ca12594856cc4f88bf4f75e68408e302,

title = "An improved greedy construction of minimum connected dominating sets in wireless networks",

abstract = "A minimum connected dominating set (MCDS) offers an optimized way of sending messages in wireless networks. However, constructing a MCDS is a NP-complete problem. Many heuristics based approximation algorithms for MCDS problems have been previously reported. In this paper, we propose a new degree-based multiple leaders initiated greedy approximation algorithm (PSCASTS) based on the selection of a pseudo- dominating set and an improved Steiner tree construction. We also show that our PSCASTS outperforms existing CDS construction algorithms in terms of CDS size and construction costs. The simulation results show that PSCASTS constructs better non-trivial CDSs for networks with uniform, nearly- uniform and random distribution of sensor nodes. While PSCASTS retains the current best performance ratio of (4.8+ln5)|opt|+1.2, |opt| being the size of an optimal CDS of the network, it has the best time complexity of O(D), where D is the network diameter.",

keywords = "Connected dominating set (CDS), maximal independent set (MIS), Steiner tree, routing backbone, unit disk graph (UDG), Computer science and informatics",

author = "Ariyam Das and Chittaranjan Mandal and Christopher Reade and Manish Aasawat",

note = "Note: Published in the proceedings ISBN: 9781612842554. Organising Body: Institute of Electrical and Electronics Engineers Organising Body: Institute of Electrical and Electronics Engineers",

year = "2011",

month = mar,

day = "30",

doi = "10.1109/WCNC.2011.5779233",

language = "English",

isbn = "9781612842554",

pages = "790--795",

booktitle = "Published in the proceedings ISBN: 9781612842554. Organising Body: Institute of Electrical and Electronics Engineers Organising Body: Institute of Electrical and Electronics Engineers",

}

Das, A, Mandal, C, Reade, C & Aasawat, M 2011, An improved greedy construction of minimum connected dominating sets in wireless networks. in Published in the proceedings ISBN: 9781612842554. Organising Body: Institute of Electrical and Electronics Engineers Organising Body: Institute of Electrical and Electronics Engineers. pp. 790-795. https://doi.org/10.1109/WCNC.2011.5779233

An improved greedy construction of minimum connected dominating sets in wireless networks. / Das, Ariyam; Mandal, Chittaranjan; Reade, Christopher et al.
Published in the proceedings ISBN: 9781612842554. Organising Body: Institute of Electrical and Electronics Engineers Organising Body: Institute of Electrical and Electronics Engineers. 2011. p. 790-795.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An improved greedy construction of minimum connected dominating sets in wireless networks

AU - Das, Ariyam

AU - Mandal, Chittaranjan

AU - Reade, Christopher

AU - Aasawat, Manish

N1 - Note: Published in the proceedings ISBN: 9781612842554. Organising Body: Institute of Electrical and Electronics Engineers Organising Body: Institute of Electrical and Electronics Engineers

PY - 2011/3/30

Y1 - 2011/3/30

N2 - A minimum connected dominating set (MCDS) offers an optimized way of sending messages in wireless networks. However, constructing a MCDS is a NP-complete problem. Many heuristics based approximation algorithms for MCDS problems have been previously reported. In this paper, we propose a new degree-based multiple leaders initiated greedy approximation algorithm (PSCASTS) based on the selection of a pseudo- dominating set and an improved Steiner tree construction. We also show that our PSCASTS outperforms existing CDS construction algorithms in terms of CDS size and construction costs. The simulation results show that PSCASTS constructs better non-trivial CDSs for networks with uniform, nearly- uniform and random distribution of sensor nodes. While PSCASTS retains the current best performance ratio of (4.8+ln5)|opt|+1.2, |opt| being the size of an optimal CDS of the network, it has the best time complexity of O(D), where D is the network diameter.

AB - A minimum connected dominating set (MCDS) offers an optimized way of sending messages in wireless networks. However, constructing a MCDS is a NP-complete problem. Many heuristics based approximation algorithms for MCDS problems have been previously reported. In this paper, we propose a new degree-based multiple leaders initiated greedy approximation algorithm (PSCASTS) based on the selection of a pseudo- dominating set and an improved Steiner tree construction. We also show that our PSCASTS outperforms existing CDS construction algorithms in terms of CDS size and construction costs. The simulation results show that PSCASTS constructs better non-trivial CDSs for networks with uniform, nearly- uniform and random distribution of sensor nodes. While PSCASTS retains the current best performance ratio of (4.8+ln5)|opt|+1.2, |opt| being the size of an optimal CDS of the network, it has the best time complexity of O(D), where D is the network diameter.

KW - Connected dominating set (CDS)

KW - maximal independent set (MIS)

KW - Steiner tree

KW - routing backbone

KW - unit disk graph (UDG)

KW - Computer science and informatics

U2 - 10.1109/WCNC.2011.5779233

DO - 10.1109/WCNC.2011.5779233

M3 - Conference contribution

SN - 9781612842554

SP - 790

EP - 795

BT - Published in the proceedings ISBN: 9781612842554. Organising Body: Institute of Electrical and Electronics Engineers Organising Body: Institute of Electrical and Electronics Engineers

ER -

An improved greedy construction of minimum connected dominating sets in wireless networks

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Research output

An improved greedy construction of minimum connected dominating sets in wireless networks

Cite this