TY - JFULL AU - Hanieh Tarbiat Khosrowshahi and Mojtaba Shakeri PY - 2018/4/ TI - Relay Node Placement for Connectivity Restoration in Wireless Sensor Networks Using Genetic Algorithms T2 - International Journal of Electronics and Communication Engineering SP - 160 EP - 170 VL - 12 SN - 1307-6892 UR - https://publications.waset.org/pdf/10008613 PU - World Academy of Science, Engineering and Technology NX - Open Science Index 135, 2018 N2 - 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. ER -