Small World Model-Based Polylogarithmic Routing Using Mobile Nodes

The use of mobile nodes to improvenetwork 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 randomor controlled movement of resource rich mobile nodes. The application ofsuch a model has been used in several emerging networks, includingmobile ad hoc networks (MANETs), wireless sensor networks (WSNs), anddelay tolerant networks (DTNs). It is well known that mobility increasesthe capacity of MANETs by reducing the number of relays for routing,prolonging the lifespan of WSNs by using mobile nodes in place ofbottleneck static sensors, and ensuring network connectivity in DTNsusing mobile nodes to connect different parts of a disconnected network.Trajectory planning and the coordination of mobile nodes are twoimportant design issues aiming to optimize or balance several measures,including delay, average number of relays, and moving distance. In thispaper, we propose a new controlled mobility model with an expectedpolylogarithmic number of relays to achieve a good balance among severalcontradictory goals, including delay, the number of relays, and movingdistance. The model is based on the small-world model where each staticnode has ``short'' link connections to its nearest neighbors and``long'' link connections to other nodes following a certain probabilitydistribution. Short links are regular wireless connections whereas longlinks 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 oflong links. The effectiveness of the proposed model is evaluatedanalytically as well as through simulation.