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
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/7/27
Y1 - 2016/7/27
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 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 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 - https://www.scopus.com/pages/publications/84983266698
U2 - 10.1109/INFOCOM.2016.7524455
DO - 10.1109/INFOCOM.2016.7524455
M3 - 会议稿件
AN - SCOPUS:84983266698
T3 - Proceedings - IEEE INFOCOM
BT - IEEE INFOCOM 2016 - 35th Annual IEEE International Conference on Computer Communications
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016
Y2 - 10 April 2016 through 14 April 2016
ER -