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: Contribution to conference › Paper › 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
DOIs	https://doi.org/10.1109/WCNC.2011.5779233
Publication status	Published - 30 Mar 2011
Externally published	Yes
Event	IEEE Wireless Communications and Networking Conference 2011 - Cancun, Mexico Duration: 28 Mar 2011 → 31 Mar 2011

Conference

Conference	IEEE Wireless Communications and Networking Conference 2011
Period	28/03/11 → 31/03/11

Bibliographical note

Note: Published in the proceedings ISBN: 9781612842554.

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 Conference contribution

An improved greedy construction of minimum connected dominating sets in wireless networks
Das, A., Mandal, C., Reade, C. & Aasawat, M., 30 Mar 2011, Published in the proceedings ISBN: 9781612842554. Organising Body: Institute of Electrical and Electronics Engineers Organising Body: Institute of Electrical and Electronics Engineers. p. 790-795
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Cite this

@conference{3d3c0a7f963f436d9ce1c353dc24cdfa,

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; IEEE Wireless Communications and Networking Conference 2011 ; Conference date: 28-03-2011 Through 31-03-2011",

year = "2011",

month = mar,

day = "30",

doi = "10.1109/WCNC.2011.5779233",

language = "English",

}

TY - CONF

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

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 - Paper

T2 - IEEE Wireless Communications and Networking Conference 2011

Y2 - 28 March 2011 through 31 March 2011

ER -

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

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Fingerprint

Research output

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

Cite this