Routing algorithms for ad hoc wireless networks with a realistic physical layer

Abstract

The design and evaluation of existing routing protocols for ad hoc wireless networks normally assume an ideal physical layer model, where the message is received if and only if two nodes are within the transmission range. Routing protocols designed for this model show poor performance in simulators implementing more realistic models. In this thesis, we introduce a model that simplifies the realistic log-normal shadowing model by approximating the probability of packet reception based on distance between nodes. We then design several localized, position based routing algorithms with and without acknowledgements, with fixed message sizes. An appropriate MAC protocol for acknowledging the message is described. Localized position and acknowledgement based protocols are based on calculating ideal hop count, and optimizing expected progress. Improved, iterative versions of these protocols are also presented. These algorithms strive to optimize the expected hop count (EHC) measure in delivering the message from the source to the destination, where EHC takes into account all acknowledgements and retransmissions. We also propose several localized non acknowledgement-based algorithms. These protocols aim to maximize the probability of delivery of a packet from the source node to the destination node. Our, performance evaluation shows that newly proposed localized protocols are competitive with global shortest weighted path based protocols, and superior to threshold based localized protocols that were also proposed in this thesis. We also studied the impact of imprecise location information on the performance of the suggested protocols.