Routing in intermittently connected networks: Age rumors in connected components

Mobile Ad Hoc Network (MANET) protocols are efficient in routing data dynamically between mobile nodes that belong to the same connected component and thus assume that the network is always fully connected. However, even if the network is continuously partitioned, a "communication path" may be available through time and mobility using intermediate mobile nodes (temporally within reach of each other). We consider the problem of routing with the sole assumption that the speed of the node mobility is less than the speed of transmitting a packet to a neighbor. We introduce new routing algorithms that vary depending on the buffering capability of the nodes while always minimizing the impact on the capacity (i.e., only one copy of a packet can be sent while a copy may be kept). The novelty is based on link aging rumors across connected components (as opposed to neighbor's aging). We show that various pattern of mobility and network clustering can be described by a single parameter such as the information speed propagation. We establish several analytical properties independent of mobility models using an analogy with the sound propagation in liquid where molecules creates temporary connected component in which sound travels fast.