Algorithms for routing and rerouting in mobile wireless and ad hoc networks.

Abstract

Mobile computing---sometimes called Nomadic Computing---as the name suggests is computing with mobile users. A specialized case of mobile wireless network is an ad-hoc network where the network contains only mobile hosts and no base stations or any centralized routing infrastructure. Routing of packets in ad-hoc network is done by a store-and-forward mechanism from the source mobile host to the destination mobile host using intermediate mobile hosts. A pair of mobile hosts in an ad-hoc network can communicate with each other if they are in radio contact. This dissertation focuses on the following issues involved in routing and re-routing in connection-oriented mobile networks and ad-hoc networks: (1) Rerouting in connection oriented mobile networks. We have devised a framework for comparing, analyzing, and evaluating various rerouting schemes for connection-oriented mobile networks using several performance metrics. We also provided a comprehensive classification of rerouting schemes. We studied parallelism in messaging in the rerouting protocol and we suggest mechanisms to improve the performance of rerouting including radio-hints, parallel messaging. (2) Rerouting in mobile-mobile connections in connection-oriented networks. We have presented a distributed rerouting algorithm for mobile networks where both the ends of a connection are mobile hosts (Mobile-Mobile connections). We have compared our proposed algorithm with all the other Mobile-Mobile rerouting schemes using several performance metrics. (3) Evaluation of the effect of the various rerouting schemes on the performance of wireless TCP schemes. In a mobile environment, TCP can not discriminate packets dropped due to lossy links, intermittent connectivity, handoffs and the consequent rerouting with those dropped due to network congestion. We have studied the effect of how rerouting schemes effect the performance of Wireless TCP using simulation. (4) Routing in ad-hoc networks. We propose an efficient distributed spanning tree based routing algorithm for ad hoe networks that adjusts dynamically to fast changing dynamic topologies of ad-hoc networks. We achieve this by maintaining a forest of spanning trees. Our approach has less time, space and message complexities when compared with the algorithms described in literature. (Abstract shortened by UMI.)