Research On The 3D Topology Organizing And Clustering Algorithms In Sensor Networks

Wireless sensor networks (WSNs) consist of low-cost, low-power tiny sensor nodes that can communicate with each other to perform sensing and data processing cooperatively. Network topology and energy consumption are two primary problems in wireless sensor networks. The coverage and connectivity of a sensor network depends to a large extent on the network topology. The lifetime of a sensor network is determined by its energy consumption. This thesis focuses on the three-dimensional (3D) topology organizing in wireless sensor networks and the energy-balanced clustering of sensor nodes.The two-dimensional (2D) assumption which is adopted by most of the current researchers of wireless sensor networks cannot satisfy all demands of the real life. A large number of wireless sensor networks embedded in the physical world will be 3D, e.g. space sensor networks, underwater sensor networks and underground sensor networks. However, due to the surprising difficulties of 3D problem-solving, most of the algorithms designed for 2D wireless sensor networks cannot be extended to 3D directly. New methods and new techniques are needed to solve the difficult problems in 3D wireless sensor networks.The phase transition phenomena of random 3D wireless sensor networks are firstly discussed in this thesis. Since previous works on random structured wireless networks used sophisticated probabilistic tools to derive their bounds, a simpler analysis technique, called bin-covering, is applied to get tight threshold for coverage properties of random structured 3D sensor networks.This thesis provides a new lattice-based technique to study the topology construction in 3D wireless sensor networks. First, three spatial symmetric cubic lattice structures are proposed for deterministic deployment of 3D wireless sensor networks. The formulas of sensor nodes position in these structures are provided based on the generator matrix of cubic lattices and the coverage and connectivity of them are analyzed. These symmetric structure networks possess many interesting properties. They can guarantee the full coverage of the target space. They are sparse and connected. For a given node degree, they can maximize the coverage range and reduce the communication traffic among nodes. These cubic lattice structures are suitable for 3D wireless sensor networks in the atmosphere, underground, or in the building.While sensor networks with symmetric structure have prominent features, for a large scale sensor network, it isn't cost-effective to deploy sensor nodes one by one. Moreover, in many cases sensor nodes cannot be deployed manually due to the limitation of the environment. In this thesis, a series of virtual Voronoi cell-based topology organizing strategies for random 3D wireless sensor networks are presented based on the lattice theory. In these strategies, distributed algorithms for finding the nearest lattice point in different virtual cubic lattices are designed. Using these algorithms, a sensor node can find which Voronoi cell it belongs to by itself. Then sensor nodes with same cell id can use some leader selection algorithms to periodically choose a leader among them. These leaders act as the active node of the cell to maintain the network coverage and connectivity. Because on every duty cycle only a small number of nodes are active, the network lifetime is prolonged.An underwater surveillance sensor network is a typical 3D networks. A novel expansion topology generation algorithm (ETG) is proposed according to the requirement of the underwater surveillance system. The principle of ETG is to construct a 3D sensor network from 2D randomly deployed sensor devices which can move only vertically. ETG integrates the deployment of devices with a scheduling mechanism. When sensor devices are densely deployed on the sea surface, a 3D underwater network is generated by active devices with less device movement in a short duration. Extensive simulation results show that ETG can not only improve the initial sensor field coverage rate, but also achieve larger coverage space at lower cost of average device movement distance than the random deployment strategy and the cubic-based coordination scheme. Thus the energy cost at the network set-up phase is reduced effectively.Finally, this thesis considers two kinds of nodes clustering algorithms. The first one is the static clustering algorithm which divides the whole coverage area of sensor networks into virtual cells. Once a cell is formed it will not change during the network lifetime. Every duty cycle a node is elected to work as a leader. Current random leader election algorithms cannot ensure the balanced energy consumption among nodes in a cell. A self-adaptive random leader election algorithms (SARLE) was proposed to solve this problem. According to the principle of events of extremely low probability, SARLE tunes the running parameters based on the history information. Simulation results show that SARLE can balance the energy consumptions among nodes more effectively.The second one is the dynamic clustering algorithm which randomly selects a few nodes as cluster heads and rotates this role to evenly distribute the energy load among the sensors in the network. LEACH is one of the most popular algorithms of it. This thesis spot that there exists a slight inaccuracy in the computation of the node self-selected probability in LEACH, which causes the expected number of cluster per round is not the optimal value. An improved algorithm (I-LEACH) is proposed to correct this inaccuracy. Extensive simulation results show that I-LEACH can ensure a more stable number of clusters.