SmallWorld Model-Based Polylogarithmic Routing Using Mobile Nodes

The use of mobile nodes to improve network system performance has drawn considerable attention recently. The movement-assisted model considers mobility as a desirable feature, where routing is based on the store-carry-forward paradigm with random or controlled movement of resource rich mobile nodes. The application of such a model has been used in several emerging networks, including mobile ad hoc networks (MANETs), wireless sensor networks (WSNs), and delay tolerant networks (DTNs). It is well known that mobility increases the capacity of MANETs by reducing the number of relays for routing, prolonging the lifespan of WSNs by using mobile nodes in place of bottleneck static sensors, and ensuring network connectivity in DTNs using mobile nodes to connect different parts of a disconnected network. Trajectory planning and the coordination of mobile nodes are two important design issues aiming to optimize or balance several measures, including delay, average number of relays, and moving distance. In this paper, we propose a new controlled mobility model with an expected polylogarithmic number of relays to achieve a good balance among several contradictory goals, including delay, the number of relays, and moving distance. The model is based on the small-world model where each static node has “short” link connections to its nearest neighbors and “long” link connections to other nodes following a certain probability distribution. Short links are regular wireless connections whereas long links are implemented using mobile nodes. Various issues are considered, including trade-offs between delay and average number of relays, selection of the number of mobile nodes, and selection of the number of long links. The effectiveness of the proposed model is evaluated analytically as well as through simulation.