Research Of Clustering Algorithm Based On Grid In Ad Hoc Network

Ad hoc network is a multi-hop temporary self-organized system,which consists of a set of mobile terminals with radio devices.Each mobile terminal is both a host and router,performing route setup and packet forwarding according to a routing algorithm.As a kind of self-organized communication network without center,Ad hoc network is widely applied in the fields of emergency environments such as military strategy environment and accident environment for its efficient self-organization, dynamic mapping topography structure,and multi-hop retransmission technology.At the beginning,Ad hoc network often bases on plat structure for small-scale.The advantage of the plat structure is simple and has no maintaining cost,and limits the scale expansion of the network at the same time.To enhance the wireless network scalability,large-scale Ad hoc wireless network often uses the hierarchical structure.The Ad hoc wireless network is divided into some clusters,which consist of the cluster head and ordinary nodes.Hierarchical structure is easily scalabled, has smaller routing and control overhead.Now a suitable cluster algorithm with less cluster maintaining cost and stable structure is an important research subject in Ad hoc network.In order to construct the network better with the hierarchical structure, the paper divides the whole network area into several grids,and explains a clustering algorithm based on grids with several cluster heads combining the global position with area partition.The main idea is dividing the network into grids through global position.Meanwhile, several grids compose a cluster.Such grid in the cluster is pointed to be the cluster head area,which will produce several cluster heads for the cluster.This paper elabrates a new routing protocol named CBGP (Cluster Based on Grid Protocol) which consists of selecting cluster head and routing algorithm.In the selecting of cluster heads,we use Automatic On-demand Weighted algorithm,and choose nodes with less mobility, higher degree and more energy to be cluster heads.In routing,the search area is a rectangle which defined by the source and destination.The routing includes inter cluster routing and intra cluster routing.The cluster algorithm in this paper avoids the overlapping between clusters,prolongs the cluster lifetime,and reduces the clustering cost.The paper compares the new cluster algorithm with the Low-ID cluster algorithm in CBRP(Cluster Based on Routing Protocol).The numerical simulation indicates that new cluster algorithm based on grids with several cluster heads has less clustering cost than the Low-ID. Furthermore,the paper constructs the network simulation environment on NS-2 simulation platform in which the mobile nodes are set up randomly performing packet forwarding and routing.Analyze of simulation result indicates that CBGP is better than CBRP on both clustering cost and cluster lifetime.There are some problems dissolved in this paper.In the last chapter of this paper some suggestion are given to them.