TY - GEN
T1 - An improved greedy construction of minimum connected dominating sets in wireless networks
AU - Das, Ariyam
AU - Aasawat, Manish
AU - Mandal, Chittaranjan
AU - Reade, Chris
N1 - 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
T3 - IEEE Conference on Wireless Communications and Networking
SP - 790
EP - 795
BT - 2011 IEEE Wireless Communications and Networking Conference
PB - IEEE Publishing
T2 - IEEE Wireless Communications and Networking Conference 2011
Y2 - 28 March 2011 through 31 March 2011
ER -