【作者】 李建波；

【导师】 黄刘生；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2009， 博士

【摘要】 无线传感网络通常具有如下特点:大规模、自组织、传感器节点能量受限、部署环境恶劣等。这些特点决定了必须设计能量有效的协议来减少传感器节点的能耗以延长无线传感网络的寿命。拓扑控制问题作为无线传感网络中的核心问题之一,对于延长网络的生存时间、减小通信干扰、提高MAC协议和路由协议的效率以及促进数据融合、提高网络的可扩展性、可靠性、安全性等其他性能等具有重要意义。因此如何进行拓扑控制以优化拓扑结构并延长传感网络的寿命已经成为重要的研究方向。本文主要研究能量有效的拓扑控制算法:(1)应用于静态密集部署传感网络的一种基于完全图的分簇算法(2)一种在上述分簇算法基础上加入移动节点担当网关的算法(3)应用于稀疏移动传感网络的传输功率控制算法(4)应用于大规模部署移动传感网络的分簇算法。无线传感网络的某些应用,例如生态监护、军事侦察等,为了能够准确的对数据进行收集并保持覆盖性,通常会在监测区域部署大量冗余的静态节点。在这种情况下,为了能够延长传感网络的寿命,通常选取一定的节点保持活动,由它们构成数据传输的主干网,而其他节点在没有任务时可以进入睡眠状态,这正是层次分簇算法所应用的场合。针对分簇算法过程中的重新分簇所带来的高负载问题,本文提出了一种基于完全图的能量有效的分簇算法CGCA(Complete Graphbased Clustering Algorithm)。CGCA利用完全图中节点之间互相等价的性质,只在系统启动的时刻执行分簇算法,而在以后的重新分簇阶段,簇头只需要在每个簇的内部节点间进行轮换,而不像以前的分簇算法需要进行全局性的触发来选举新的簇头。因此CGCA从根本上消除了重新分簇所带来的“涟漪”效应。仿真试验表明:在节点密集部署的情况下,CGCA产生的消息交换个数远小于HEED(Hybrid Energy Efficient Distributed clustering)分簇算法。最后簇头均匀分布方面,CGCA也明显优于LEACH(Low-Energy Adaptive Clustering Hierarchy)分簇算法。在一个分簇算法中,一个网关节点(gateway)除了要完成负责基本的感知数据之外,还要在相邻的簇之间承担起数据转发的任务。由于簇之间的数据流量相对较大,因此相对于普通节点来说,网关节点更容易耗尽自己的能量,因此这些网关节点容易成为系统的瓶颈(bottleneck),从而严重影响传感网络系统的性能表现。本文在CGCA分簇算法的基础上的加入了一些资源和配置丰富的移动节点来担当簇之间的网关,以把普通节点从转发簇间数据的繁重任务中解放出来,籍此达到延长传感网络寿命的目的。除此之外,由移动节点来担当网关可以显著的提高系统的稳定性和容错性,这是因为由配置丰富的移动节点代替能量受限的普通节点来担当网关可以减少系统出现故障的概率,从而可以进一步的提升系统的整体性能表现。实验表明,在密集部署传感器节点的网络中,本算法产生的消息交换个数只是传统的基于最小标号分簇算法LIC(Low Identifier Clustering)的20%左右。另外,本算法所取得的系统时间也是LEACH算法的两倍左右。无线传感网络在军事和紧急搜救的应用促使了移动传感网络的兴起。由于这些被监控对象本身所具有的移动性,使得底层的拓扑在不断的发生变化,因此很难应用传统的拓扑控制算法或者简单的对它们改进使之适用于移动传感网络。本文提出了在给定移动网络模型VRMN(Vadant Rate Mobile Network)下的一种基于传输功率控制的拓扑控制算法,并分别给出了它的集中式和分布式版本。本算法首先求出每个节点的一跳邻居集合,然后利用类似于XTC的方法把可由较近邻居节点中继到达的最远邻居节点删除,这样在不损失连通性的前提下就可以减少节点的发射功率,从而达到节省节点能量以延长传感网络寿命的目的。理论证明,本算法是高效的,它具有O(n~3)的多项式复杂度时间。实验结果表明,本算法在减少节点传输功率和保持网络连通性方面也取得了较好的性能。在一个大规模移动传感网络中,由于分簇算法能够形成一个层次结构以及能够较好的支持网络的可扩展性并在节点移动时能够较好的维护拓扑结构的稳定性,这就使得分簇算法比较适合于对这种大规模密集移动传感网络进行拓扑控制。本文分簇算法首先将部署区域划分成小的单元格,在每个单元格的中心位置事先指定一个节点担当簇头,其他的移动节点只需要监听簇头的"Hello"消息并通过比较消息的信号强弱就可以加入到相应的簇头中。在簇形成阶段,本文分簇算法的时间复杂度和消息复杂度均为O(N),从而较大的节省了节点的能耗并取得了较好的能量有效性。而在簇维护阶段,簇的维护是由事件触发并且异步进行,不会产生“涟漪”效应,因此本文算法能够取得一个较为稳定的簇结构以适应节点的移动和底层拓扑的变化。仿真实验表明,本文算法能够产生了较少的消息个数和较长的系统寿命。本文的主要贡献和创新点如下:1)针对重新分簇所带来的大量计算和通信负载以及“涟漪”效应,本文提出了一种基于完全图的分簇算法CGCA,使得重新分簇只是异步的局部触发,从而维持了簇结构的稳定性以延长系统生命期。2)在上述分簇算法的基础上,通过加入资源丰富的移动节点来担当转发簇间数据的网关,从而使得普通节点能够集中到收集或者探测等任务上,这能够进一步的节省能量从而延长整个传感网络的工作寿命。3)在一个给定的移动网络模型VRMN下,提出了一种多项式时间的基于功率控制的拓扑控制算法,本算法能够在保持网络连通性的前提下,减少了节点的发射功率,从而达到节省节点能量的目的。4)在一个大规模移动传感网络中,提出了一种能量有效的分簇算法,它具有简单的簇形成和维护过程,使得节点移动可能对簇结构的影响局限在一个较小的范围内,从而形成了一个较为稳定的簇结构。更多还原

【Abstract】 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.更多还原