An Efficient Hierarchical Consensus Protocol For Mobile Ad Hoc Networks

MANET(Mobile Ad Hoc Network) is a kind of decentralized and self-organized network which is randomly comprised of wireless terminals without any pre-deployed infrastructure. Its random mobility and dynamic topology raise new challenges for research. Solving the consensus problem is the foundation of mobile computation. Since the exsiting consensus protocols are designed for wireline networks or infrastructure wireless networks, because of their extremely high message cost, they don’t apply to the MANETs which has a feature of resource constraint.Base on the analysis of the original protocol, an efficient consensus protocol for mobile Ad Hoc networks called HRH protocol is proposed by using hierarchical optimization. The thesis considers the system model for MANETs with host crashes, at most f hosts can crash where f<n/2(n is the total number of the hosts), and equipped with Chandra-Toueg’s unreliable failure detectors of class OS. The HRH protocol is based on a two-layer hierarchy with hosts associated with proxies. At least f+1hosts act as proxies and each host is associated with one proxy. The messages from all hosts are merged and forwarded to the local hosts by proxies so as to reduce the message cost. However, adding such a hierarchy is not trivial. The messages may be lost or missed due to proxy failures or host movements which may make the HRH protocol invalid. To address this problem, the thesis imports the handoff mechanism.The HRH protocol algorithm is implemented in NS-2simulation platform. It is compared with the original protocol in execution time and number of hops. The results of simulation show that the hierarchical approach can improve the scalability of the consensus protocol and the HRH protocol can significantly save time cost and message cost compared to the original protocol.