Calculation of minimal dominating set in wireless sensor network with host switch-on/off

Abstract

This paper proposes a simple and efficient distributed algorithm for calculating minimal dominating set in wireless sensor network. This method can avoid maintaining the connectivities between backbone hosts. Considering that the hosts in mobile networks have different characteristics, this paper proposes a method of calculating minimal dominating set with weight. The nodes can be chosen to form a minimal dominating set when the network topology changes. For the host switch on/off operation, the updating algorithm was provided. The change in the status of a host affects only the status of hosts in the restricted vicinity. Simulation results show that the proposed method can ensure fewer dominators but with higher weight to form the minimal dominating set and the nodes can be adaptive to the changes of network topology.

Keywords

wireless sensor network / virtual backbone / minimal dominating set / switch-on/off

References

[1] Sun Y., Zhang Jing. Wireless self-organized sensor network[J]. Chinese Journal of Sensors and Actuators, 2004, 17(2): 331-335.

[2] McQuillan J. M., Richer I., Rosen E. C. The new routing algorithm for the ARPANET[J]. IEEE Transactions on Communications, 1980, 28(5): 711-719.

[3] Moy J. Internet Request for Comments [EB/OL]. RFC1274. OSPF Version 2. 1991.

[4] Hedrick C. Routing Information Protocol. Internet Request for Comments[EB/OL]. RFC 1058, 1988.

[5] McQuillan J. M., Walden D. C. The ARPA network design decisions[J]. Computer Networks, 1977, 1(5): 243-289.

[6] Wu Jie, Li HaiLan. On calculating connected dominating set for efficient routing in ad-hoc wireless network[C]. In: Proceedings of the Third International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. Seattle, Washington, USA, 1999. 7–14.

[7] Zhang J., Sun Y., Fang Zhaohui. Energy-efficient minimum connected dominating set Chinese Journal of Sensors and Actuators, 2004, 17(4): 603-606.

[8] Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. 1979, San Francisco, USA: Freeman.

[9] Skold M, Yeongyoon C, Nilsson J. An analysis of mobile radio ad hoc networks using clustered architectures[C]. In: Proceedings of the 57th IEEE Semiannual Vehicular Technology Conference. Piscataway, NJ, USA, 2003. 181–185.

[10] Xu K., Hong X., Gerla M. Landmark routing in ad hoc networks with mobile backbones[J]. Journal of Parallel and Distributed Computing, 2003, 63(2): 110-122.

[11] Safwat A., Hassanein H., Mouftah H. Power-aware virtual base stations for wireless mobile ad hoc communications[ J] Computer Network, 2003, 41(3): 331-346.

[12] Chatterjee M., Das S. K., Turgut D. WCA: A weighted clustering algorithm for mobile ad hoc networks[J]. Journal of Cluster Computing, 2002, 5(2): 193-204.

[13] Yin J., Wu Kaiya. Graph Theory and Its Algorithm[M]. 2003, Hefei, China: University of Science and Technology of China Press.