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.
