Network Topology

Topology control is fundamental to solving the scalability and capacity problems in large-scale wireless ad hoc and sensor networks. The forthcoming wireless multi-hop networks such as ad hoc and sensor networks will allow network nodes to control the communication topology by choosing their transmitting ranges or scheduling node to sleep. Building an optimized network topology helps surpass the prevalent scalability and capacity problems.

Topology Control (TC) in wireless ad hoc and sensor networks provides an exhaustive coverage, considering both stationary networks, to which most of the existing solutions are tailored, and mobile networks. We design a series of algorithms (e.g. sensor deployment, node sleep scheduling, etc) to cover the special issue of topology in WSNs.

Approaches/Experiments

Sensor deployment algorithm: The optimal deployment of wireless sensor networks (WSNs) is one of the most important research issues. We study the optimal deployment strategy of a sensor network with a balanced strength of a minimal number of sensors to be used and a shorter routing length to the sink node whilst keeping a guaranteed connectivity of the network. To achieve these objectives, we propose a novel ant based approach to the optimal placement of sensors in a grid sensing area to minimize the number of nodes. We provide two algorithms to achieve the approach. The first algorithm is an ant based connectivity guaranteed sensor placement algorithm targeting to minimize the amount of sensor nodes. The second algorithm is a connectivity guaranteed sensor placement algorithm with routing length optimization targeting to minimize the number of used sensor nodes and the total routing length to the sink node. The essential feature of the two proposed algorithms is that they all guarantee the connectivity of the network and hence the proposed approach is practical.

Node sleep scheduling algorithm: Scheduling nodes to work alternatively can prolong network lifetime effectively. The existing solutions usually depend on geographic information which may introduce extra costs and compromise the overall effectiveness. Other node density control algorithms agnostics of geographic information do not guarantee a certain effected coverage degree. Analysis on pure stochastic-sleep scheduling mechanism reveals that a certain coverage degree can be met when numbers of nodes are at a certain level. However the mechanism did not consider network connectivity and therefore its applicability is limited. A new definition of effected coverage is proposed to describe the network coverage maintaining network connectivity at the same time. And based on the definition of effected coverage, a new fractional coverage algorithm is proposed.

Accomplishments

1. Wei Liu, XiaoGuang Niu and Li Cui. EasiTPQ：QoS Based Topology Control in Wireless Sensor Network, Journal of VLSI Signal Processing (Journal of Signal Processing Systems for Signal, Image, and Video Technology), in print
2. Wei Liu, Li Cui and Changcheng Huang. EasiFCCT: A fractional coverage algorithm for wireless sensor networks. Journal of Computer Research and Development, Vol.45, No.1, Pages 196-204, 2008.
3. Wei Liu, Yong Miao and Li Cui. Design and Simulation of a QoS Based Topology Control Algorithm for Wireless Sensor Networks. Journal of System Simulation, Vol. 19, No. 21, Page 5075-5080, 2007.
4. Dong Li, Wei Liu, Chunli Hui, ChangCheng Huang and Li Cui. Wireless Sensor Networks in Relics Protection: Deployment Methodology and Cross-layer Design. High Technology Letters.

Future Directions

It is a new attempt to use an ant based algorithm to solve the sensor network deployment problem and some other interesting issues will be further studied by using this method in our future works. For example, a QoS supported sensor placement design, a fault tolerant design rather than mainly pursuing a minimal number of sensors and so on.