Research On Clustering Algorithm In Ad Hoc Network Based On NWCA And Measure Functions

Ad Hoc wireless mobile network get more and more attention because of its flexibility and practicality in recent years.Ad-Hoc networks clustering protocol has been proposed. If the network is divided into clusters based on hierarchical structure, it will be able to use cellular networks to extend it to the Ad Hoc network. Clustering algorithm, therefore, through a network of clusters can be divided into a large extent, improve the performance of Ad Hoc networks, is of great significance. Existing clustering algorithms can be classified based on the ID algorithm, the maximum node degree of node algorithm and heuristic algorithm, such as weight, initial analysis shows that the required information because of low computational complexity algorithm for smaller sub-clusters of Control Message text of small, fast algorithm. However, due to consider a single problem, the algorithm is too simple, the generated hierarchy is not necessarily optimal, and algorithm is also very narrow scope of application.Because in order to solve the updating and maintenance of the virtual backbone caused many control overhead and energy consumption, the use of network graph theory in this article in the dominating set, independent set and some measure of function theory, the combination of NWCA algorithm, taking into account the larger, more frequent mobile different application environments give the use of connected dominating set and independent set of the model of the virtual backbone network, building and energy conservation based on the stability of the algorithm design.To enable optimal dominating set selected to ensure that the performance as the backbone of the host node, for the Ad Hoc network topology characterized by more stable, this chapter NWCA improved algorithm, based on the NWCA and the measure function Connected Dominating Set clustering algorithm. NWCA algorithm for information only without taking into account its own node and adjacent node connectivity, cluster formation of the first set can not guarantee that connectivity is not conducive to the maintenance of the stability of the structure of sub-clusters.The introduction of the improved algorithm of the node parameters of connectivity, the use of graph theory to calculate the adjacency matrix node connectivity, making the selection on the first cluster, so that the whole topology connectivity tend to be larger and energy to become cluster head node. Any given a undirected graph G (V, E) are constituted by nodes and links of the map. V express a collection of nodes, E edges express collection. Nodes x and y exist between the edge (x, y)∈E, implies that x and y are to communicate with each other node of the one hop neighbors. Better to strike a group of nodes as the first cluster node, with their neighbors d hop cluster nodes constitute the structure and coverage of the entire network.The advantages of this algorithm are dominated by only a few nodes rather than to store all nodes of the whole network topology information, which will reduce the access and update information expenditures. NWCA and measurement-based Connected Dominating Set function clustering algorithm, only the disposal of the need to maintain routing nodes, making route discovery is very simple and quick to ensure the communication delay small. Also because of the design of Connected Dominating Set based on the clustering algorithm (CDS) of the partial update algorithm, so as long as the changes did not affect the topology of the subnet, you do not need to re-calculate the routing table.As long as the changes in mobile Ad Hoc networks do not exceed, the NWCA measure function based on Connected Dominating Set clustering algorithm is very effective, and at the local update algorithm, through the cluster head node selection method can balance the sub-cluster size. To determine the course of cluster head, clustering in the selection of members of the clustering using d jump, will probably have more cluster head, resulting in redundancy. In this paper, d jump at the beginning of the use of adjacency matrix obtained Connected Dominating set, reduce the redundant cluster head node, because the wireless communication module and the energy consumption is much larger than the energy consumption of the processor module, a great power based on Connected Dominating Set d jump clustering algorithm, can effectively reduce the communication energy consumption and thus extend the network life cycle.On a larger scale, more frequent mobile Ad hoc network, if network topology changes too fast, a dominant point of impact of change will probably have other disposal sites around the changes in the connectivity of the maintenance of CDS and update routing tables become more complex and difficult. By independent dominating set to build a virtual backbone, the backbone to overcome the need to preserve the connectivity between nodes of the problem, the faster topological changes in the reconstruction when the backbone network can quickly achieve.However, independent dominating set theory is based on the node connectivity in terms of the right of the algorithm, the calculation of node weights has become the focus of the algorithm and difficult. At the same time, independent dominating set itself to consider only the connectivity of the nodes and the node itself does not take information such as energy, mobile speed, and the relative distance between adjacent nodes and so on. For highly mobile Ad Hoc networks, this article NWCA improved algorithm, making it more suitable for frequent mobile network environment, the NWCA and the measure function based on independent dominating set of clustering algorithms, independent dominating set constitute a virtual backbone center, to overcome the maintenance of between the dominant node connectivity problem. Previous clustering algorithms, non-cluster-head node must be the first to add a cluster to maintain an increase of extra workload, and each non-cluster head node has a cluster head only but also limited by the emergence of many pathways. The cluster head algorithm for the disposal of the corresponding point, and go with the non-dominated points in place of non-cluster head node without having to establish a point of adding a disposable, so that each non-dominated points, there may be dominated by more than one point, both to ensure that the many Drive, also enable the maintenance of simplistic, such as a disposable point line, and its dominance as long as nodes have dominated other points, would not make any changes.NWCA and the measure function based on independent dominating set of the clustering algorithm uses a centralized clustering algorithm, in accordance with institutional change topology, such as the host on-line, offline and mobile cases, local clustering has been updating and maintenance, so the distribution of algorithm strong, has good scalability and can be applied to moving frequently as a layered network of on-demand routing foundation.For improving the program, the use of network simulation tool NS2 simulation of the corresponding implementation modules, and give a specific simulation program and parameters of selection, and the environment at the same experimental protocol compared with the original analysis, through simulation testing of the correctness of the algorithm and self-recovery capability.The results show that the program has been made to improve the less the number of sub-clusters and a relatively stable network structure. The number of cluster head less, then the fewer the number of clusters, which can effectively improve the utilization of links, a reduction of network redundancy. Also because of the ability of the first cluster have certain restrictions, a cluster can not be the first of many members of the Cluster Service, the selection node cluster at a time when the first try select a small cluster cluster head node. This Ad Hoc networks is of great significance.