Construction Algorithm Of Virtual Backbone In Mobile Ad Hoc Network

Mobile ad hoc network—a novel decentralized self-organized network, is comprised of wireless terminals situated randomly without any pre-deployed infrastructure. It receives more and more attention from researchers since it can be applied in many fields. Mobile ad hoc network is of random mobility and dynamic topology, which pose a great challenge for the research. There are still many intricate problems to be investigated and solved. Due to the characteristics of Mobile ad hoc network and its potential applications, we study the technologies of mobile ad hoc network in this thesis. We firstly analyze the main characteristics of mobile ad hoc network and reveal how it can be applied to other fields.Some key technologies for mobile ad hoc network such as network framework, physical layer, MAC scheme, routing protocols, the performance of transport layer and network security are discussed. The existing solutions for the key technologies are presented; other intricate problems which are remained to be solved are pointed out as well. Among the problems mentioned above, the construction of virtual backbone plays an important role in network routing, MAC protocol, and network security. The algorithms of construction of virtual backbone in mobile ad hoc network are reviewed in detail, and categorized mainly as ID based and link state based algorithms. Other algorithms, different from the ID and link state based algorithms, are also analyzed. Additionally, Some commonly used performance evaluation methods are discussed. The thesis proposes a new algorithm, called CB-MCDS for short, so that we could efficiently construct backbone in mobile ad hoc network by using random time-slot strategy, which is widely used in network design and optimization. Coloring in graph theory is employed here to model the algorithm.To evaluate its performance and compare it with other existing methods, four performance indices, including the ratio of the number of backbone to the optimal number, time complexity, message complexity and topology information, are employed. The evaluations show that CB-MCDS algorithm outperforms the commonly cited methods, and it has better scalability and is suitable for various dynamic environments of mobile ad hoc network.