Algorithms for Constructing Strongly Connected Dominating Set in Heterogeneous Wireless Sensor Networks

Abstract:

Energy-efficient routing is a very important issue in wireless sensor networks. An efficient routing method can avoid unnecessary data transmission and thus saves more power to extend the life of a network. The Connected Dominating Set (CDS) is a commonly used routing method which serves as a virtual backbone for a sensor network to achieve better transmission performance. The primary advantage of a CDS is its ability to adapt to the rapidly changed network topology. The construction of the CDS is a well-studied problem in an undirected unit disk graph, in which sensors are assumed to have the same transmission range. However, in practice, the sensors could have different transmission ranges due to their residual power or energy-saving mechanisms. The difference of transmission radius may form a one-way link between two nodes. Therefore, in this paper, we model the network as a directed graph and consider the CDS construction problem in such environment. We propose algorithms to construct a Strongly Connected Dominating Set (SCDS) which is a routing backbone that provides the service of efficient bidirectional data transmission between any two sensor nodes in the network.

• Periodical: Applied Mechanics and Materials (Volume 311)
• Pages: 87-92
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.311.87
• Online since: February 2013
• Authors: Chao Wei Chou, Chorng Horng Yang, Jiann Horng Lin, Hsien Leing Tsai, Ya Hui Ou
• Keywords: Breadth First Search Algorithm, Heterogeneous Network, Strongly Connected Dominating Set, Unidirectional Link

References

[1] S. Guha and S. Khuller, Approximation Algorithms for Connected Dominating Sets, Algorithmica, 20, (1998) 374-387.

DOI: 10.1007/pl00009201

[2] J.Wu and H.Li, On Calculating Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks, Proceedings of the Third International Workshop Discrete Algorithms and Methods for Mobile Computing and Comm,(1999).

DOI: 10.1145/313239.313261

[3] F.Dai and J.Wu, An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks, IEEE Transactions on Parallel and Distributed Systems,15,( 2004).

DOI: 10.1109/tpds.2004.48

[4] B. Chen, K. Jamieson, H. Balakrishnan, and R.Morris, Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, ACM Wireless Networks Journal, (2002) 481-494.

DOI: 10.1145/381677.381686

[5] D.Z. Du, M.T. Thai, Y. Li, D. Liu, and S.Zhu, Strongly Connected Dominating Sets in Wireless Sensor Networks with Unidirectional Links, Springer-Verlag Berlin Heidelberg 2006,(2006) 13-24.

DOI: 10.1007/11610113_2

[6] M.T. Thai, F. Wang, D. Liu, S. Zhu, and D.Z. Du, Connected Dominating Sets in Wireless Networks with Different Transmission Ranges, IEEE Transactions on Mobile Computing, 6, (2007).

DOI: 10.1109/tmc.2007.1034