Optimal Stop Points for Data Gathering in Sensor networks with Mobile Sinks

Abstract

This thesis proposes an algorithm to select stop points for a mobile sink to minimize energy consumption in wireless sensor networks. The algorithm assumes that a mobile sink travels along a fixed path, and uses a stop-and-collect protocol known as an efficient algorithm to collect data. Based on data generation rate of node, the algorithm finds optimal stop points that minimize energy consumption in data gathering. The algorithm selects energy-optimal stop points that maximize network lifetime while ensuring full area coverage. We prove that selecting stop points is an NP-hard problem, and present an Integer Linear Programming formulation. Then, we implement a Tabu-search heuristics to reduce the exponentially increasing computation time required to obtain an exact solution. In experiments, the proposed heuristic provided near-optimal energy consumption values with low computation times, and is suitable for large-sized sensor networks.