Reducing message delay with the general Message Ferry Route (MFR*) problem

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 Message 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.