Research On Ad Hoc Network Clustering Algorithm

Good clustering algorithm in Ad Hoc network can help for the research on routing protocol and broadcast algorithm. Aiming at the defect of energy saving and virtual backbone network size in the existing algorithms, article separately proposes three clustering algorithms: Based on period execution energy-saving clustering algorithm, Based on the counter adaptive energy-saving clustering algorithm, Based on node priority MIS strategy clustering algorithm.Based on period execution energy-saving clustering algorithm contraposing the cluster head node becoming the bottleneck node and the defect of accelerating network partition of the traditional clustering algorithm, considering each node become cluster head node opportunities, put forward the concept of period execution. Period as complete a cluster establishment and cluster maintenance tasks required for a period of continuous time. Then select proper number nodes as candidate cluster head nodes by limit threshold. In each period, selects the appropriate nodes as cluster head node, and then guarantee the nodes as the cluster head nodes in the next period time loss the chance of becoming cluster head. Thus average consumption node power, prolong the life period, decelerate network partition. Further the local update maintenance algorithm is put forward. As long as the network topology changes without the influence to the virtual backbone, it doesn't need to re-clustering, it only need update local un-backbone node. And this change is based on common nodes join existing cluster, on the basis of new cluster structure will not be increased, favorable and control of period time. The based on period execution energy-saving clustering algorithm is effective in network topology changes small case. Compared with the traditional clustering algorithm, it is good at saving node energy, prolonging the network life time.To network node moving quickly lead to the network structure with topology changes frequently, a based on the counter adaptive energy-saving clustering algorithm to adapting the quick mobile network is put forward. Firstly the Ad Hoc network node equipment add counter module. Then consumption quantitative show the cluster head node power and mapping cluster head time say, and count the time of cluster head node. Through the threshold limit selected part node participation algorithm performance stage of cluster head elections. According to counter recorded as cluster head node length to select less time as head of nodes become cluster head node. Through cluster head nodes and distributed gateway node connections consist of virtual backbone network. In long-term operation stage through the judgment as cluster head node time meets the adaptive period start threshold will start algorithm for clustering. And then give algorithm maintenance update scheme according to the network topology changing. According to the node to join and leave and mobile case of clustering algorithm of local the renewal and the maintenance, take two-jump node to join the way to avoid cluster head node of frequent replacement. Through the example analysis and simulation experiment, Virtual backbone network response effectively when topology changes rapidly, has achieved good energy saving effect. At the same time because the existence of adaptive periodic threshold, can better balance the spent energy. But in the condition of the network topology invariable, clustering effect due to the influence of node equipment itself requirements, the effect it is inferior compare with the based on period execution energy-saving clustering algorithm.Considering cluster structure load balancing after clustering, establish relatively small virtual backbone cover the entire network, prolong the network life time, a based on node priority MIS strategy clustering algorithm is put forward. The nodes in the network through mutual information with neighbor nodes to obtain its node priority size which is relative neighbor nodes. Consider the following influence factors of network clustering:the power factor, the mobility of nodes, the connectivity of nodes and the power dissipation of nodes, in each period time according to weights calculation formula calculates the current period the value of nodes'weight. According to the relative priority of local nodes select the network of cluster head dominate node in each period, finally through independent dominate node-set MIS connected ways to create connected dominating sets constitute a virtual backbone. In connecting stage adopts two basic strategies:two-jump path takes precedence over three-jump path, the average weight values smaller path takes precedence over the average weight values greater path. The constructing virtual backbone which is through the above ways has elected a relatively optimal solution and removes the repeated path of connected dominating concentration. Through examples and comparative simulation proof, the methods of priority calculating on network clustering and selection process was effective, while in reasonable factor influence function, algorithm creates virtual backbone relative with the traditional clustering algorithm is lesser, balance the cluster head load, extend nodes life time.