A Research On Hierarchical Topology Control Algorithms And The Related Problems Of Wireless Sensor Networks

Wireless sensor network (WSN) is a kind of new network which could mointor and collect data from physical regions by coordinating plenty of tiny sensor nodes which are capable of sensing, computing and wireless communicating. This kind of networks has gradually demonstrated a promising applicational future. WSN has characteristics such as limited hardware resources, big network scale, dynamic topology, self-organization and data-centric, and the central issues of WSN researches are energy conservation and network lifetime prolonging. Hierarchical topology control algorithms could enhance network performances and decrease network energy costs by selecting a subset of nodes as working nodes while let the rest nodes go to sleep to form an optimized data transmission structure under certain coverage and connectivity degree. Basically, hierarchical topology control algorithms are classified as two types: connectivity type and coverage type.This paper conducts researches on WSN hierarchical topology control algorithms and their related issues:Firstly, this paper proposes a novel connectivity type hierarchical topology control algorithm: Connectible-Cell based Topology Control algorithm (CCTC). Initially, by analyzing the limitations of current Cell based hierarchical topology control algorithms, this paper proposes 1-con method: when a Cell Head is connected to the current backbone, all Cells that could be reached by this head will be connected to the topology structure through it, and then this new backbone expands itself distributedly and recursively in the same way. By leveraging 1-con method, CCTC is designed, and it is theoretically proved that CCTC could not only guarantee network connectivity, but also use fewer active nodes per round than other algorithms do to form backbone network, so the working energy is notably decreased. CCTC is suitable for WSN since its computing complexity is linear, and the storage space as well as the message amount is bounded by constant magnitude. Simulation results also validate that CCTC provides impressive energy conservation effect and long network lifetime with decent robustness and limited control overheads.Afterwards, this paper focus on the problem that as far as a WSN and its normal nodes are concerned, which criteria should be adopted to determine whether to use the connectivity type topology algorithms or the coverage type topology algorithms. To the best of our knowledge, the current researches on these two types of hierarchical topology control algorithms mainly focus on the optimaization of energy cost and algorithm complexity, but no theoretical analysis has been conducted on when to use the connectivity type or coverage type. This paper discovers that with the increment of physical events frequencies, the coverage type algorithms are more energy efficient than the connectivity type be, and vice versa. By defining physical events densityρ_e---the times of events happening per unit time and unit area, this paper firstly gives the thresholdρ_e~* under the condition of events uniform distribution, i.e. if the physical events density satisfiesρ_e≥ρ_e~*, WSN should use coverage type, otherwise use connectivity type; then, this paper gives k~*: the action decision criterion for every normal node, i.e. if k---the total times of sensed events e of the node in a round ---satisfies k≥k~*, it should join in the coverage algorithm of working nodes set, otherwise it should go to sleep. Simulations validate that the theoretical results presented in this paper have decent significance on topology algorithm selection and nodes' action decision.Based on the above theoretical results, a Cell-based QoSE-Centric Topology Control algorithm (CQCTC) is proposed in the paper, which provides a trade-off between the connectivity type and the coverage type. This paper firstly gives the concept of QoSE (Quality of SEnsing) --- QoSE consists of the sensed frequency and signal strength, and normal node uses its QoSE predicted for next round to judge whether it could play the role as a valid candidate working node; then, every Cell Head collects the coverage information of all valid nodes in its Cell to construct an optimized working set to cover the high event-frequency regions while let the rest of nodes go to sleep. Simulations indicate CQCTC exploits the advantages of both connectivity type and coverage type and forms proper topology structures dynamically according to the distributions and frequencies of the targets/events, therefore the working energy cost is decreased and the data accuracy is enhanced. At last, this paper studies the QoS routing algorithms in heterogeneous WSN. Since users could set delay constraints for key data transmissions in continuous queries or snapshot queries, this paper propose the problem on how to find the least energy cost paths for simultaneously running queries under their delay constraints, and a distributed hierarchical routing protocol is given. Theoretical analysis proves that this protocol is correct and loop-free. Simulations also indicate that this protocol could save energy cost 3-8 times compared to LEACH with the delay constraints satisfied.