A Clustering Algorithm Based On Tree Backbone Network Design

Ad-Hoc Network is a multi-hop wireless network which is a collection of wireless nodes without the aid of any established. It's one of the hotspots in the research of wireless network at present because of its flexible and fast network organization. The mobility of the nodes brings the difficulties to routing algorithm and QoS guarantee. Therefore, it is necessary to select appropriate network topology architecture and route protocol according to network scale, expansibility and request of real time, to exert capability of network most.In recent years,as the scale of network becomes larger and nodes enhance the mobility, the present route protocols can't satisfy the new requirement on routing efficiency and loading ability. Hierarchy architecture which takes clustering algorithm as a representation is used to solve the problem efficiently. Aim at the shortage of the present clustering algorithms on clusterhead selection and network load balance, a new clustering algorithm is designed, which considers lots of factors affecting the network, and takes integrated weight as the standard for clusterhead selection to satisfy different request of clustering, and the scale of cluster is limited to improve load capability of network. Based on clustering, there is another problem of how to organize architecture along the clusters. Considering there is no circle in tree architecture and it can realized simply, the tree-backbone is used to build architecture along clusters, which can reduce the cost of route update and maintenance significantly, and make the routing along the cluster simpler and more efficient.The aim of this research is to present a clustering algorithm based on the tree-backbone and analyze fundament of the algorithm and the infection on capability of network. The thesis first introduces the appearance and development of Ad Hoc, then describes the clustering algorithm and analyzes the fundament and procedures of several representative clustering algorithms. The thesis introduces Kernel Tree Routing Protocol (KTRP), and after describing detailed algorithm it analyzes the characteristic and routing capability. Thesis presents a clustering algorithm based on tree-backbone named TBBC (Tree Backbone-Based Clustering) and discusses principles such as selection of clusterhead and gateway, then it designs detailed process and verifies performance of TBBC by using OPNET simulation. At last, the thesis gives a conclusion and presents the research direction.