Virtual Backbone Construct Robust Clustering Algorithm Research

At present, with the rapid development of wireless communication, self-organized Ad hoc networks are widely used in various areas. But, because of the limited wideband and limited energy, when the number of sensor nodes is large enough, the capacity and performance of sensor networks will decrease a lot. So it is very necessary to group the network into hierarchical cluster networks so as to make the local network smaller. This dissertation is mainly fousing on the research of clustering algorithms which meet specific reqirements. Besed on the analysis of the clustering algorithms proposed by others before, connection probability is considered which is as the new factor when considering network clustering. How to construct a robust and stable virtual backbone network is discussed in great detail, which includes:1. The character of wireless channel is considered when clustering wireless sessor network. The wireless connection probability is introduced as the new factor;2. The clustering algorithm involving connection probability based on threshold is proposed, which is compared with maximum node degree clustering algorithm;3. Algebraic connectivity in graph theory is introduced to as metric of network topology connectivity. Meanwhile when wireless channel character is considered, the algebraic connectivity based on connection probability is proposed;4. A new metric called network quality (γ) is proposed, which includes the factors of network robustness and network cost;5. Robust virtual backbone network construction model is setup and centralized greedy algorithm is proposed, which is then compared with low-cost clustering algorithm by way of computer simulation;6. Two clustering algorithms which improve the centralized greed algorithm are proposed, including centralized algorithm based on transition probability and distributed algorithm.In addition, with the development of 3G systems and the trend of future wirless communication system, this dissertation discusses the interworking solutions between WiMAX and CDMA2000 and also solutions between WiMAX and SAE, in order to meet the reqirements of all network convengence.