Robust Routing in Networks of Mobile Radio Nodes

Abstract

Mobile radio communication networks in the operational theater exhibit volatile network topology with rapid connectivity changes due to node mobility and the harsh conditions in the battlefield environment. Reliable packet transport becomes a challenging task in view of the constant connectivity changes. In this paper we present a systematic approach for reliable packet routing in mobile networks. A class of topology models that is broad enough to capture the topology changes encountered in a mobile network is introduced. The optimal routing policy is specified in terms of the Directed Acyclic shortest path Routing Graph (DARG). Two algorithms for computing the DARG are proposed. One of the two algorithms is iterative and amendable to distributed implementation. The DARG provided shortest path routing in random connectivity networks in analogy to the shortest path tree in fixed connectivity networks.