Energy-aware path-planning for a mobile data collector in wireless sensor network

Abstract

Data gathering or the process of collecting and delivering data packet in a resource constrained Wireless Sensor Network (WSN) is a very challenging task as the sensors become out of power anytime during the data gathering period. One of the methods of addressing this problem is to use a dedicated mobile element called Mobile Data Collector (MDC) which travels along the network, collects data packets directly from the sensor nodes and carry the data to the sink. The use of MDC has become popular as it elongates the lifetime of the sensor network, reduces the cost of deployment etc. Besides, it can gather data even in a disconnected and sparse sensor network. Using an MDC in a WSN is challenging in various aspects. It's mobility can be pre-planned or random. In the case of random mobility, one or more sensor nodes may not be visited by the MDC at all. In the case of pre-planned mobility, the most important objective is to cover all the sensor nodes. However, given the in nite number of points in the region, the optimal path-planning of an MDC becomes intractable. In that case, we can use the Travelling Salesman Problem tour or TSP-tour to nd the solution for a good path which ensures the data gathering from all of the sensor nodes. In this thesis, we prove that, a TSP-tour ensures the maximum lifetime for the WSN if data is collected by the MDC. There is another risk involved in using an MDC in the WSN, which is called data delivery latency. The MDC has to halt and collect data from the sensor nodes. The period of a complete tour is comparatively higher than the time required to send packets to the sink by multi-hop forwarding. The packet delivery latency in the case of TSP-tour by the MDC may be too high for some real-time applications of the WSN. Therefore, we need to shorten the TSP-tour by the MDC. In our research, we present a shorter tour than the TSP-tour by the MDC. Our method iteratively shortens the tour by nding Shortcuts. We nd that, to communicate with a sensor node, the MDC does not have to visit the exact location of the sensor node; instead, visiting any point within the transmission region su ces for the data collection. We use OMNET++ simulator to verify the performance of our algorithm. We design a realistic test bed, we compare our tours with the relevant tours and we nd that our method has the lower data delivery latency. The lifetime of the WSN in our method is as good as that of the TSP-tour. In addition to that, we nd the packet-drop rate, the throughput, the tour-time better in using our method. The running time of our algorithm is polynomial (O(mn2), where m is the number of iteration and n is the number of sensor nodes). Even though the problem of nding the minimum length TSP-tour is NP-Complete, there exist many approximate algorithm for this computation which runs in polynomial time. Therefore, Our method runs in polynomial time.