Algorithms for Collecting Data from Cooperating Sensor Motes using Unmanned Vehicles

This article addresses a fundamental resource allocation problem that arises in monitoring applications: given the locations of the motes, the amount of data that needs to be transferred from each mote to the base station, and an Unmanned Vehicle (UV), find (i) a communication network among the motes, (ii) a subset of motes, referred to as cluster-heads, that act as relays between the motes and the UV, and (iii) a path for the UV such that each mote uses the communication network to transmit its data to one of the cluster-heads, each of the cluster-heads is visited by the UV, and the sum of communication costs involved in transmitting the data from the motes to the cluster-heads and the travel costs of the UV is a minimum. This problem is a generalization of a single Traveling Salesman Problem (TSP) and is NP-Hard. This article presents a rounding algorithm and heuristics to solve the problem. Computational results show that the rounding algorithm performed the best for the tested instances with up to 50 motes and produce solutions that are on an average within 5% of the optimum time relatively fast