Research On Ad Hoc Network Clustering Algorithms Based On Graph Theory

Wireless Mobile Ad Hoc network is a dynamic ad hoc network topology system which is made up of a group of mobile terminal nodes which are devices with wireless communication transceiver. The system is arbitrary and without a central, each node of the system is both a host and a router. Mobile Ad Hoc Networks have the following characteristics: Self-organizing, mobile, multi-hop routing started fast and strong resistance to destruction, without the support of the existing information infrastructure and so on. Therefore they are used in military communications, sensor networks, emergency services and disaster recovery, mobile networks, Etc.First, the article studied the structure, the characteristics of Mobile Ad Hoc Networks and key technologies related. The mobile Ad Hoc networks and traditional networks have different characteristics which determine their key technology's differences. Based on its own structure and characteristics of Mobile Ad Hoc, focusing on its unique mode connectivity, the article mainly researches the topology formation algorithm for the Ad Hoc network. Ad Hoc network has two kinds of topological structures. The plane structure is relatively simple. In the plane structure, all the nodes have the same position and equal functionality, and the bottleneck will not occurs principlely, so it is relatively safe. With the increasing of the number of the nodes in the network, hierarchical structure is usally chosen in order to control costs and increase network scalability, in another word, it seeks a virtual backbone network. The virtual backbones in Ad Hoc Network commonly have two kinds of structures--tree and group.Secondly, the paper proposed a new approach using graph theory to get virtual backbone of Ad Hoc Networks. In wireless ad hoc group, the process to search the trunk node and the virtual backbone formatted with the head nodes is similar to solving process of minimum connected dominating set and minimum dominating set problem in graph theory. Among the resoving process of connected dominating set algorighm, It will emerge some new connected dominating sets during the connection of independent sets, which may resulted in the formation of loop between nodes. This not only increases the probability of generating redundant dominate nodes, but also increased maintenance costs of the backbone. So feedback idea is used to limit the emergence of its loop, and the numbers of gateway nodes is reduced.Finally, performance comparison is given between our algorithm model and Alzoubi dominating set construction algorithm model using NS2. The results show that, when the transmission radius is not bigger, our model has a better performance than Alzoubi dominating set construction algorithm model in the follwing aspects: time complexity, space complexity and number of the first group (the total number of dominating nodes). And the two algorithms have the same performance when the transmission radius is large.