Font Size: a A A

The Research On Key Algorithms Of Distributed Clustering And Energy Efficient Data Gathering Protocol In Wireless Sensor Networks

Posted on:2009-01-01Degree:DoctorType:Dissertation
Country:ChinaCandidate:J B XuFull Text:PDF
GTID:1118360242490765Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
As a new way to obtain information and a novel model for data processing, Wireless Sensor Network (WSN) can acquire target information by deploying massive sensor nodes in monitor region, and provide processed data to the end-user via multi-hop wireless communication. It links the logical information world with the physical world, changes the human interaction mode and realizes the connectivity among physical world, computer world and human nature. Thus, data gathering is the basic application of WSN, and it is the foundation of other complex applications. As the data acquired from physical world is massive with high relevance, we proposed a distributed clustering protocol for Wireless Sensor Network. MDG(Miscellaneous Data Gathering Protocol)achieves a good performance in terms of efficiency, accuracy, robustness and energy-saving.Through analyzing the existing data collection protocols, we found that the hierarchical topology, especially the sub-cluster structure is very suitable for data collection in large-scale, high-density WSN. Clustering has been proved to be more appropriate for large-scale sensor networks and data fusion technology, it significantly improved load balance and network lifetime.In this dissertation, we first proposed a parallel distributed energy saving clustering algorithm BPEC. Cluster-heads are elected by two probabilities. The primary probability is based on the ratio between average residual energy of neighbor nodes and itself residual energy. The subsidiary probability is the node's degree. By using BPEC algorithm, the entire network broadcasting complexity is O(n), the entire network complexity is O(1). The cluster set generated by BPEC is proved to be a Maximum Independent Set, which can cover all network nodes. The experimental results show that when nodes are enough, the cluster set size is close to the theoretical values.To ensure the user's expectation for target coverage, we derived the smallest active node number K through node active-sleep theory. We also achieved energy-saving routing algorithm between intra-cluster and inter-cluster. The cluster set produced by BPEC can construct a Connected Dominating Set and a data gathering tree by the use of reverse diffusion method.To address signal interference problem between adjacent clusters in data collection, a TDMA schedule algorithm based on cluster routing structure is proposed. The data collection time in each round will be segmented along the data gathering tree, each cluster node along the data gathering tree preserves two data, which is the initial distribution of itself work time and the controlling time of its sub-tree. It must be ensured that each node's controlling time in the data gathering tree is much more than the sum of its children's time, and each node's work time is more than that of any child, and its left child's work time is always less than that of right child. After the distribution, the initial work time of each node are different, the nodes can transmit data according to their own TDMA slot without a collision conflict.Finally, wireless sensor network achieves Differentiated Services by double queues technology. Taking into account the general data aggregation and immediate forward for emergency data, a mechanism based on the differentiated services is proposed, satisfying user's require for unexpected emergency events. Simulation results show that MDG data gathering protocol can achieve a longer network life time and scalability than LEACH and HEED.This dissertation is supported by the National Natural Science Foundation project "a positioning algorithm for complex environment in wireless sensor networks" (No. 60673061)...
Keywords/Search Tags:clustering, topology control, differentiated services, data aggregation, TDMA
PDF Full Text Request
Related items