1 Department of Electronic Systems, The Technical Faculty of IT and Design, Aalborg University, VBN2 The Faculty of Engineering and Science (TECH), Aalborg University, VBN3 Wireless Communication Networks, The Technical Faculty of IT and Design, Aalborg University, VBN4 Mechanical Engineering, Texas A & M University, College Station, TX5 IIITD6 University of California at Berkeley7 Universidade do Porto8 University of California at Berkeley9 Universidade do Porto
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.