Research On Some Topology Contorl Problems For Wireless Sensor Networks

WSN(Wireless Sensor Networks) usually has the following features:large scale, self-organization,limited energy equipped sensor nodes and bad deployment environment etc,which determines that some energy efficient protocols must be designed to prolong the lifetime of WSN by reducing the energy consumption of sensor nodes.Topology control,as a core problem of WSN,has a fundamental impact on some important network parameters,such as prolonging the system lifetime of WSN, reducing signal interference,enhancing the energy efficiency of MAC and routing protocols,promoting data aggregation and enhancing the scalability,stability,and safety of WSN.As a result,how to perform topology control to optimize topology structure and prolong the WSN lifetime has been an important research topic recently.This dissertation mainly focuses on investigating energy efficient topology control algorithms:(1) propose a complete graph-based clustering algorithm(CGCA) applied in static densely deployed sensor networks(2) introduce some resource and hardware rich mobile nodes acting as inter-cluster gateways so as to augment the aforementioned clustering algorithm(3) propose a power control based topology control algorithm used in sparse mobile sensor networks(4) propose a clustering algorithm used in large-scale deployed mobile sensor networks.Some applications in WSN,such as ecosystem monitoring and military surveillance,often deploy large redundant sensor nodes on the monitored area to accurately perform data gathering and preserve coverage.In this situation to prolong the lifetime of WSN,some nodes keep active to form the backbone of forwarding data traffic,while other nodes can turn off their radios when having no tasks,and this is exactly where the hierarchical clustering algorithm handles.Aiming to solve the high overheads brought by re-clustering in a clustering algorithm,we propose an energy efficient complete graph-based algorithm(CGCA).By using the property that the nodes are of equivalence each other in a complete graph,CGCA is only executed at the system activation time and the cluster head role needs only to be rotated among the internal nodes in each cluster at the subsequent re-clustering phase,while the previous clustering algorithms need a global trigger to re-elect cluster heads,which incurs greatly reduced communication and computation overheads.Consequently our CGCA algorithm totally eliminates the ripple effect in re-clustering phase.The simulation experiments demonstrate that the number of exchanged message produced by CGCA is much less than that of HEED clustering algorithm in the densely deployed case.Finally, CGCA significantly outperforms LEACH algorithm in terms of evenly distributing cluster heads.Besides performing the basic sensing data task,a gateway node is also being responsible for the forwarding the data traffic among adjacent clusters in a typical clustering algorithm.Compared with the ordinary node,a gateway is much prone to deplete its energy due to the large data traffic among inter-clusters,thus being the bottlenecks of the system and in turn degrading the senor network performance.This dissertation introduces some resource and configuration rich mobile nodes to act as inter-cluster gateways to for the purpose of liberating the ordinary nodes from the heavy forwarding inter-cluster data,thus achieving the aim of prolonging the lifetime of WSN.Furthermore,letting the mobile nodes act as gateways can significantly enhance the stability and fault-tolerance of the whole system,because substituing the configuration rich mobile nodes for the energy constrained ordinary nodes can reduce the probability of occurring system malfunction,thus further promoting the system overall performance.Extensive simulation experiments demonstrate that the number of exchanged messages produced by our algorithm is only about 20%that of the traditional identifier based clustering algorithm in a densely deployed case. Furthermore,our proposed achieves an improvement in system lifetime of factor 2 that of the LEACH in a dense sensor network.The military and emergency rescuing applications of wireless sensor networks promote the proliferation of MSN(Mobile Sensor Networks).The changing underlying topology,due to the intrinsic mobility characteristic of monitored objects,makes it difficult to apply or adapt the traditional topology control algorithms to be applied in MSN.This dissertation proposes a power control based topology control algorithm under a given mobility model called VRMN(Variant Rate Mobile Network) and then presents its central and distributed versions respectively.In this algorithm each node first computes the one-hop neighbor set and then applies a XTC-like procedure to prune the furthest neighbor that can be reached by the relay of its closer neighbor,which incurs reducing transmitting power of each node and consequently saving power consumption to prolong the network lifetime on the basis of without impairing the network connectivity.Our algorithm obtains a polynomial time complexity of O(n~3) thus being efficient from the theoretic view and the experiments results show that our algorithm achieves comparatively better performance from the perspective of reducing node transmitting power and maintaining network connectivity.In a large scale mobile sensor network,a clustering algorithm can form a hierarchical structure,which can better support the scalability of network and maintain the stability of topology in the presence of node movement,thus making it well suitable for the topology control problem in a large-scale densely deployed mobile sensor network environment.Our clustering algorithm first partitioned the deployment region into some small grids,for each of which a mobile node was dispatched to act as cluster head.Subsequently,all the other mobile nodes can join their corresponding cluster by monitoring and comparing the signal strength of the "Hello" messages sent from cluster heads.In the cluster formation phase,our algorithm achieves both O(N) time and message complexity.In the subsequent cluster maintenance phase,the maintenance of the cluster structure is unsynchronously event driven,thus elminiating the ripple effect.So our algorithm achives a comparatively stable cluster structure so as to be well adapt to the node's movement and underlying topology's change.Furthermore,the simulation results show that our algorithm can produce comparatively small number of messages and long system lifetime.The contributions and novelties of this dissertation are as following:1) Aiming to solve the large computation and communication overheads and "ripple" effect brought by re-clustering,this dissertation proposes a complete graph-based clustering algorithm,called CGCA,which makes re-clustering unsynchronized and locally triggered,for the purpose of maintaining a stable cluster structure and prolonging the system lifetime.2) On the basis of the aforementioned algorithm,some resource rich mobile nodes are put into the sensor networks so as to act as gateways to relay the heavy inter-cluster data traffic,which can make the ordinary sensor nodes more devoted to the gathering or probing tasks and consequently further saving much energy to prolong the lifetime of the sensor networks.3) Under a given mobility model called VRMN,this dissertation presents a power control based topology control algorithm with a polynomial time complexity,which can reduce transmitting power on a per-node basis,thus achieving the goal of saving energy,without impairing the network connectivity.4) In a large scale mobile sensor networks,this dissertation presents a energy eifficent clustering algorithm,which has simple cluster formation and maintenance procedure.Our algorithm achieved a much stable cluster structure by limiting impact of the movement of nodes on the cluster into a local area.