On robustness in high load mobile ad hoc networks
Nael Abu‐Ghazaleh, Paul Rogers · 2005
Mobile Ad hoc Networks (MANETs) are increasing in popularity as an approach for cost-effective and fast deployment of wireless connectivity. In this work, it is first shown that MANETs experience erratic and unpredictable behavior under high loads even in the absence of mobility. Some of the causes of the behavior are identified by analysis of problematic scenarios. Two contributing problems are isolated and then analyzed. The major focus of the work (the first problem considered) is the poor robustness of Network Wide Broadcast (NWB) algorithms. Most existing NWB algorithm research focuses on reducing the overhead of these algorithms. The work in this dissertation focuses on increasing their robustness. The root of the robustness problem is the unreliability of the Medium Access Control (MAC) level broadcast primitive. This component of the work first classifies NWB according to their features that influence robustness. These algorithms are studied experimentally to evaluate their robustness. In order to improve the robustness of a NWB, the potential solution space for NWB algorithms is reviewed. Solutions that use implicit feedback, explicit feedback, and solutions that provide a fixed level of redundancy based on factors such as the network quality are examined. Protocols that improve the coverage of a NWB in each sector of the solution space are proposed. First, to improve NWB robustness, a selective rebroadcast approach is evaluated. This network level solution leads to a considerable improvement in NWB coverage, with only a small increase in overhead. This solution, which relies on implicit feedback, can be added to virtually all NWB approaches in order to improve their reliability. Second, a new MAC level primitive is proposed, which significantly improves the reliability of link level broadcast. In particular, this solution that uses explicit feedback is especially suited for optimized NWB algorithms that build a virtual backbone because it allows full reliability for the messages as they cross the backbone. Lastly, this work proposes a new Connected Dominating Set (CDS) algorithm that assigns qualities to links between nodes, and builds a tree to cover these nodes that takes the qualities into account. The second problem examined in this dissertation is the problem of unpredictable hop-level interactions under high load. More specifically, it is observed that destructive interactions occur in some scenarios that allow certain transmitters to capture the medium. (Abstract shortened by UMI.)