An Approximation Algorithm to Find Optimal Rendezvous Points in Wireless Sensor Networks

In recent times, mobile sink (MS) technology is one of the most popular approaches to collect data from sensor nodes. It has several advantages over a static sink network. To make data collection by MS more efficient, the path of the MS must be well designed. Several factors contribute in an optimal path of MS such as length of the path, number of halting points, and capacity of the MS. Location of the halting points is a major issue which affects the path length of the MS. Finding best position and number of halting points is very difficult and is considered as an NP-hard problem. Genetic algorithm (GA) is a popular and effective approximation approach for solving many NP-hard problems. In this paper, we present a novel approach based on GA to find the location of the rendezvous points (RPs) such that a good path for a MS can be obtained. We performed extensive simulation of our work and compared with other approach of tour planning. We also applied T test to judge statistical significance of our algorithm. The results demonstrate better performance of our algorithm in terms of the path length.