Multipath routing in the presence of frequent topological changes

In this article we propose a framework for multipath routing in mobile ad hoc networks and provide its analytical evaluation. The instability of the topology (e.g., failure of links) in these types of networks, due to nodal mobility and changes in wireless propagation conditions, makes transmission of time-sensitive information a challenging problem. To combat this inherent unreliability of these networks, we propose a routing scheme that uses multiple paths simultaneously by splitting the information among the multitude of paths, to increase the probability that the essential portion of the information is received at the destination without incurring excessive delay. Our scheme works by adding some overhead to each packet, which is calculated as a linear function of the original packet bits. The resulting packet (information and overhead) is fragmented into smaller blocks and distributed over the available paths. Our goal is, given the failure probabilities of the paths, to find the optimal way to fragment and then distribute the blocks to the paths so that the probability of reconstructing the original information at the destination is maximized. Our algorithm has low time complexity, which is crucial since the path failure characteristics vary with time and the optimal block distribution has to be recalculated in real time.