TY - GEN
T1 - Performance-guaranteed strongly connected dominating sets in heterogeneous wireless sensor networks
AU - Liu, Chunyan
AU - Huang, Hejiao
AU - Du, Hongwei
AU - Jia, Xiaohua
PY - 2016
Y1 - 2016
N2 - In wireless sensor networks, Virtual Backbone (VB) construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Transmission ranges of sensors are not always equivalent. A sensor networks is modeled as a directed graph while sensors have different transmission ranges. In this paper, we will try to find a special Strongly Connected Bidirectional Dominating Set (SCBDS) within minimum routing cost for each pair of nodes in directed graphs. The SCBDS forms a VB of the networks whose sensors have different transmission radius. For any pair of sensors, the length of the shortest path they communicate with each other through VB should be no more than a constant times the length of the shortest path without using VB. We propose a constant approximate scheme to construct the SCBDS with the bounded size 3*(8ρ+1)2(2ρ+1)2/2 opt. A centralized and a distributed algorithm with the same performance ratio are presented to show the details to construct the SCDS in directed graphs. Simulation results show that the average shortest path length through our algorithms is reduced greatly compared with other algorithms.
AB - In wireless sensor networks, Virtual Backbone (VB) construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Transmission ranges of sensors are not always equivalent. A sensor networks is modeled as a directed graph while sensors have different transmission ranges. In this paper, we will try to find a special Strongly Connected Bidirectional Dominating Set (SCBDS) within minimum routing cost for each pair of nodes in directed graphs. The SCBDS forms a VB of the networks whose sensors have different transmission radius. For any pair of sensors, the length of the shortest path they communicate with each other through VB should be no more than a constant times the length of the shortest path without using VB. We propose a constant approximate scheme to construct the SCBDS with the bounded size 3*(8ρ+1)2(2ρ+1)2/2 opt. A centralized and a distributed algorithm with the same performance ratio are presented to show the details to construct the SCDS in directed graphs. Simulation results show that the average shortest path length through our algorithms is reduced greatly compared with other algorithms.
KW - Approximation algorithm
KW - Connected dominating set
KW - Wireless sensor networks
UR - http://www.scopus.com/inward/record.url?scp=84983266698&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84983266698&origin=recordpage
U2 - 10.1109/INFOCOM.2016.7524455
DO - 10.1109/INFOCOM.2016.7524455
M3 - 32_Refereed conference paper (with ISBN/ISSN)
SN - 978-1-4673-9954-8
BT - IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications
PB - IEEE
T2 - 35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016
Y2 - 10 April 2016 through 14 April 2016
ER -