Optimization Online


Locality sensitive heuristics for solving the Data Mule Routing Problem

P.L.A Munhoz (pmunhoz***at***ic.uff.br)
U.S. Souza (ueverton***at***ic.uff.br)
P.H. González (pegonzalez***at***cos.ufrj.br)
L.S. Ochi (satoru***at***ic.uff.br)
P. Michelon (philippe.michelon***at***univ-avignon.fr)
L.M.A. Drummond (lucia***at***ic.uff.br)

Abstract: 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 heuristics are proposed. These heuristics 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 heuristics. The obtained results show that the proposed heuristics give good solutions in a reasonable time when compared with the optimal solutions and lower bounds.

Keywords: Data Mule, Routing Problem , Locality Sensitive , Heuristics , Convex hull

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Combinatorial Optimization (Approximation Algorithms )

Citation: Submited to Annals of Operations Research. S.I.: Claio 2016


Entry Submitted: 02/14/2017
Entry Accepted: 02/14/2017
Entry Last Modified: 02/15/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society