The general message ferry route (MFR∗) problem and the An-Improved-Route (AIR) scheme

Abstract

In existing studies of message ferry (MF) schemes in wireless ad hoc networks, routes for message ferries are often adopted from the solutions of the Traveling Salesman Problem (TSP) and its variants. In such existing solutions, a message ferry route is often assumed to be a simple cycle which has no repeated vertices nor edges. In this paper, we consider a more general case, where the route is a closed walk. In doing so, we generalize the massage ferry route (MFR) problem as the MFR∗ problem, and propose the An-Improved-Route (AIR) scheme to construct routes for the ferry. Simulation proves that the AIR scheme effectively reduces the delay of the MF schemes. Moreover, our studies and schemes in this paper can easily be extended to operation research problems in other related fields, such as transportation and traffic coordination etc.