Relay Node Placement for Connectivity Restoration in Wireless Sensor Networks Using Genetic Algorithms

Authors: Hanieh Tarbiat Khosrowshahi, Mojtaba Shakeri

Abstract:

Wireless Sensor Networks (WSNs) consist of a set of sensor nodes with limited capability. WSNs may suffer from multiple node failures when they are exposed to harsh environments such as military zones or disaster locations and lose connectivity by getting partitioned into disjoint segments. Relay nodes (RNs) are alternatively introduced to restore connectivity. They cost more than sensors as they benefit from mobility, more power and more transmission range, enforcing a minimum number of them to be used. This paper addresses the problem of RN placement in a multiple disjoint network by developing a genetic algorithm (GA). The problem is reintroduced as the Steiner tree problem (which is known to be an NP-hard problem) by the aim of finding the minimum number of Steiner points where RNs are to be placed for restoring connectivity. An upper bound to the number of RNs is first computed to set up the length of initial chromosomes. The GA algorithm then iteratively reduces the number of RNs and determines their location at the same time. Experimental results indicate that the proposed GA is capable of establishing network connectivity using a reasonable number of RNs compared to the best existing work.

Keywords: Connectivity restoration, genetic algorithms, multiple-node failure, relay nodes, wireless sensor networks.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1315907

References:

[1] C. Y. Chong, S. P. Kumar," Sensor networks: evolution, opportunities, and challenges," Proceedings of the IEEE, vol. 91, no. 8, pp. 1247–1256, Aug. 2003.
[2] J. Yick, B. Mukherjee, D. Ghosal, "Wireless sensor network survey," Computer networks, vol. 52, no. 12, pp. 2292-2330, Apr. 2008.
[3] V. Ranga, M. Dave, A. K. Verma, "Network partitioning recovery mechanisms in WSANs: a survey", Wireless personal communications, vol.72, no. 2, pp. 857-917, Feb. 2013.
[4] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, "Wireless sensor networks: a survey," Computer networks, vol. 38, no. 4, pp. 393-422, Dec. 2002.
[5] M. Younis, I. F. Senturk, K. Akkaya, S. Lee, F. Senel, "Topology management techniques for tolerating node failures in wireless sensor networks: A survey," Computer Networks, vol. 58, pp. 254-283, Sep. 2014.
[6] C. Wu, H. Chen, J. Liu, "A survey of connectivity restoration in wireless sensor networks," in 3rd International Conference. Consumer Electronics, Communications and Networks (CECNet), IEEE, 2013, pp. 65-67.
[7] S. Lee, M. Younis, "Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree," Journal of Parallel and Distributed Computing, vol.70, no. 5, pp. 525-536, Jun 2010.
[8] S. Lee, M. Younis, "Optimized relay node placement for connecting disjoint wireless sensor networks," Computer Networks, vol. 56, no. 12, pp. 2788-2804, May 2012.
[9] A. A. Abbasi, K. Akkaya, M. Younis, "A distributed connectivity restoration algorithm in wireless sensor and actor networks", in 32nd IEEE conference, on Local computer networks, IEEE, 2007, pp. 496-503.
[10] M. Younis, S. Lee, S. Gupta, K. Fisher, "A localized self-healing algorithm for networks of moveable sensor nodes". In Global Telecommunications Conference, Nov, 2008. IEEE GLOBECOM 2008, IEEE pp. 1-5.
[11] M. Imran, M. Younis, A. M. Said, H. Hasbullah, "Partitioning detection and connectivity restoration algorithm for wireless sensor and actor networks", IFIP International Conference on Embedded and Ubiquitous Computing, IEEE,2010.
[12] M. Imran, M. Younis, A. M. Said, H. Hasbullah, "Localized motion-based connectivity restoration algorithms for wireless sensor and actor networks," Journal of Network and Computer Applications, vol. 35, no. 2, pp. 844-856, Dec 2012.
[13] S. Lee, M. Younis," QoS-aware relay node placement for connecting disjoint segments in wireless sensor networks," In Distributed Computing in Sensor Systems Workshops (DCOSSW), 2010 6th IEEE International Conference on (pp. 1-6). IEEE, June 2010.
[14] F. Senel, M. F. Younis, K. Akkaya, "Bio-inspired relay node placement heuristics for repairing damaged wireless sensor networks," IEEE Transactions on Vehicular Technology, vol. 60, no. 4, pp. 1835-1848, May 2011.
[15] S. Lee, M. Younis, M. Lee," Connectivity restoration in a partitioned wireless sensor network with assured fault tolerance", Ad Hoc Networks, vol. 24, pp. 1-19, 2015.
[16] S. Lee, M. Younis, M. Lee, "Optimized bi-connected federation of multiple sensor network segments," Ad Hoc Networks, vol. 38, pp. 1-18, 2016.
[17] K. Bouyahia, M. Benchaïba, "CRVR: Connectivity Repairing in Wireless Sensor Networks with Void Regions," Journal of Network and Systems Management, vol. 25, no. 3, pp. 536-557, 2016.
[18] R. L. Graham," An efficient algorithm for determining the convex hull of a finite planar set", Information Processing Letters 1, 1972, pp. 132–133,1972.
[19] M. Younis, K. Akkaya," Strategies and techniques for node placement in wireless sensor networks: A survey," Ad Hoc Networks, vol. 6, no. 4, pp. 621-655, 2008.
[20] J. B. Kruskal,"On the shortest spanning subtree of a graph and the traveling salesman problem," Proceedings of the American Mathematical society, vol. 7, no. 1, pp. 48-50, 1956.