【作者】 于瑞云；

【导师】 王兴伟；

【作者基本信息】 东北大学 ， 计算机应用技术， 2009， 博士

【摘要】 无线传感器网络是由大量具有感知、数据处理和通信能力的传感器节点组成的网络,并且通过传感器节点之间的协作,实现对各种现象的监测。由于具有低功耗、低成本、智能化、分布式、自组织等特点,无线传感器网络在军事、环保、医疗、商业、灾害预测及救援等领域有着广阔的应用前景。无线传感器网络是面向数据的网络,其主要任务就是进行数据处理,包括数据的感知、采集、传输、压缩、聚合等等。传感器网络节点通常密集分布在所监测的网络区域中,并且会产生大量的数据,地理位置邻近的节点产生的数据往往具有很大的相关性,这些都给无线传感器网络的数据采集算法设计带来了很大的挑战。传感器网络节点是能量受限的,在网络中传输大量的数据必然会缩短网络的生命周期。因此,优化网络通信结构和数据冗余缩减都能显著改善网络在时延、能耗、可靠性等方面的性能。在无线传感器网络中构造虚拟主干是优化网络通信结构的一个重要手段。支配集是在无线网络中构建虚拟主干最常用的技术,很多文献提出采用连通支配集作为无线网络的虚拟主干,并设计了一些有效的算法,但这些算法都是以通用的无线网络为研究背景,因而在构造连通支配集时没有考虑无线传感器网络的特殊性,包括数据采集、冗余缩减等。本文主要研究适合在无线传感器网络中进行高效数据采集的支配集结构。树形通信结构很适合在无线传感器网络中进行消息洪泛、数据采集和数据融合,因此本文先对树形的连通支配集进行研究。一般意义上的连通支配集是基于连通网络的,为了将连通支配集的概念应用到稀疏无线传感器网络中,并且在数据采集时考虑数据的相关性,本文还对支配集的概念进行了扩展,提出了虚拟支配集、全虚拟支配集和关联支配集等概念,并根据扩展的支配集概念,设计了一系列在无线传感器网络进行高效数据采集的算法。首先,提出了一个能量高效的支配树构造算法(EEDTC)来构建一个能在传感器网络中充当虚拟主干的树形的连通支配集。EEDTC算法利用节点的κ跳邻居节点信息,具有很好的可扩展性,选取合适的κ值能实现不同的消息复杂度和时间复杂度要求,同时EEDTC算法具有很好的节能特性和能量均衡特性。在不同的网络数据采集应用背景下,该算法都表现出很好的性能；其次,为了实现从部分连通的网络中采集数据,结合虚拟支配集的概念,提出了一个基于网格分割的移动单元调度算法(GBMES),调度一个移动单元(ME)周期性地从网络中采集数据。GBMES算法在降低移动单元的行进时延和数据采集时延等方面具有很好的性能,显著降低了由于传感器网络节点的缓存溢出而产生的数据丢失。然后,为保证移动采集节点MC在稀疏传感器网络中进行高效数据采集,基于Voronoi图提出了两个算法：基于普通Voronoi图的移动采集节点调度算法(VDMCS)和基于加权Voronoi图的能量均衡数据采集算法(MWVDC)。两个算法都是通过迭代的虚拟散点插入过程生成一个全虚拟支配集,在给定的通信半径范围内,这个集合恰好能覆盖所有的传感器节点。在全虚拟支配集的基础上,VDMCS为MC构建一条最短的行进路径,MWVDC算法则对数据采集时延和网络能耗进行综合考虑,为MC构造一条优化的数据采集路径,同时保证整个网络能量消耗的均衡性。最后,结合关联支配集的概念,设计了一个基于熵评判的关联支配集构造算法(EECDS),该算法首先通过评价随机变量的熵值来判断网络节点间的数据相关性,然后在网络中分布式地构造一个关联图,最后借助关联图的信息构造一个连通关联支配集。EECDS算法能有效地缩减无线传感器网络的数据冗余,同时具有很好的能量均衡特性和可扩展性。更多还原

【Abstract】 Wireless sensor networks consist of a large number of sensor nodes, which are equipped with sensing, data processing, and communicating components. The sensor nodes collaborate together to monitor various phenomenons. Due to the low-power, low-cost, intelligent, distributed, and self-organized characteristics, wireless sensor networks have shown great potential in many fields, such as, military, environment, health, business, disaster forecast and relief.Wireless sensor networks are data-oriented, whose main task is data processing, including sensing, data gathering, transmission, compress, aggregation, and so on. Wireless sensor networks are usually densely deployed in a network area, and generate a great deal of data. Moreover, the data sensed by neighboring nodes is high correlated. These all impose great challenges on the design of data gathering algorithms.Since the sensor nodes are power-constrained, transferring large amounts of data definitely will shorten the lifetime of sensor networks. Therefore, the network performance on energy consumption and stability could be improved through the communication structure optimization or data redundancy removal.A virtual backbone plays an important role for the communication structure optimization. One of the frequently used techniques for virtual backbone construction is the dominating set. Many literatures proposed to use a connected dominating set as a virtual backbone in wirless networks, and designed various efficient algorithms. But few of them take special properties of sensor networks into consideration, such as data gathering, redundancy removal, etc.This dissertation focuses on the dominating set problems for efficient data gathering in wireless sensor networks.Because the tree structure is more appropriate for flooding, data gathering, and data aggregation in wireless sensor networks, this work first investigate the tree-based connected dominating set problem. The ordinary connected dominating set problems are based on connected networks. To extend the concept of connected dominating set into sparse sensor networks, and considering the data correlation as well, we propose the concepts of the virtual dominating set, the completedly virtual dominating set, and the correlation dominating set. Several efficient data gathering algorithms based on the extended dominating set concept are presented in this dissertation.Firstly, the energy-efficient dominating tree construction (EEDTC) algorithm is proposed to construct a dominating tree as a virtual backbone in wireless sensor networks. The EEDTC algorithm uses k-hop neighborhood information, and adjusting k will achieve different message complexity and time complexity for the algorithm. The EEDTC algorithm has good performance on energy consumption and energy balance of the network, and performs well under various traffic patterns in data gathering applications.Sencondly, for the purpose of gathering data from partially-connected sensor networks, with the help of virtual dominating sets, a grid-based mobile element scheduling (GBMES) algorithm is raised to schedule a mobile element (ME) periodically gathering data from the network. The GBMES algorithm has decent performance on reducing the traveling delay and data gathering delay of ME, which minimizes data loss due to the buffer overflow of sensor nodes.Thirdly, to efficiently gather data from spase sensor networks, two Voronoi diagram based algorithms are proposed, one is the Voronoi diagram based mobile collector scheduling algorithm (VDMCS), and the other is the multiplicatively weighted Voronoi diagram approach to energy-balancing data collection (MWVDC). Two algorithms both construct a completedly virtual dominating set using iterative virtual site insertion. The completedly virtual dominating set just covers all sensor nodes within a given transmission radius. Based on the completedly virtual dominating set, VDMCS constructs a shortest loop tour for the mobile collector (MC), while MWVDC constructs a loop tour for MC by compromising data gathering delay and energy consumption. Moreover, MWVDC is able to attain energy balance for the sensor network.Finally, an algorithm named the entropy evaluation for correlation dominating set construction (EECDS) is presented. The EECDS algorithm exploits the concept of the correlation domining set. It first determines the correlation between sensor nodes by evaluating the entropy of random variables, and then distributively generates a correlation graph. At last, the algorithm constructs a correlation dominating set using the information of the correlation graph. The EECDS algorithm is very efficient on reducing data redundancy in wireless sensor networks, and performs well on energy balance and scalability.更多还原