Locality Sensitive Algotrithms for Data Mule Routing Problem

摘要

A usual way to collect data in a Wireless Sensor Network (WSN) is by the support of a special agent, called data mule, that moves between sensor nodes and performs all communication between them. In this work, the focus is on the construction of the route that the data mule must follow to serve all nodes in the WSN. This paper deals with the case when the data mule does not have a global view of the network, i.e., a prior knowledge of the network as a whole. Thus, at each node, the data mule makes a decision about the next node to be visited based only on a limited local knowledge of the WSN. Considering this realist scenario, two locality sensitive algorithms are proposed. These algorithms differ by the criterion of choice of the next visited node, while the first one uses a simpler greedy choice, the second one uses the geometric concept of convex hull. They were executed in instances of the literature and their results were compared both in terms of route length and in number of sent messages as well. Some theoretical results, a mathematical formulation, and some lower bounds for the global view scenario are also proposed, in order to provide some parameters to evaluate the quality of the solutions given by the proposed algorithms. The obtained results show that the proposed algorithms give good solutions in a reasonable time when compared with the optimal solutions and lower bounds.