【作者】 王刚；

【导师】 黄刘生；

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

【摘要】 由大量的集成有传感单元、信息处理单元和通信单元的无线传感节点所组成的无线传感网络,具有隐蔽性优良、组网迅速、结构灵活、分布范围不易受自然条件限制、成本低廉、精度高、易扩展、体积小、规模大等等诸多优点,因而其可以被广泛应用于军事、环境、医疗卫生、空间探索、农业、智能家居等等人类生活的各个领域,在人类社会生活的各个方面均具有广泛的应用前景和重大的现实意义。但是,无线传感网络自身也存在着诸多问题与挑战,诸如能量受限,存储、计算、通信能力有限,带宽较低,实时性和可靠性较低等等。所以,研究人员需要充分考虑无线传感网络的各项特点,使之可以被更为高效、广泛地应用。正是因为无线传感网络具有这诸多的特点和巨大的现实意义,关于无线传感网络各项技术的研究,如路由协议、MAC协议、拓扑控制技术、数据处理技术等的研究才如火如荼。但是,无线传感网络现有的各项研究大多是在无线传感节点已经部署完毕后进行的,有些研究甚至完全忽略了无线传感网络的网络结构,就直接对无线传感网络进行相关协议的设计与处理,这实际上是忽视了无线传感网络的可配置性对于无线传感网络性能的影响。实际上,无线传感网络所有应用的第一步就是节点配置,当无线传感节点被散布到监测区域之后,我们可以利用节点的移动性,或者进行相关节点的添加等等方式,修缮整个无线传感网络的网络结构,使无线传感网络的性能得到大幅提高,这就是本文所要研究的无线传感网络配置问题。事实上,配置是无线传感网络中各种应用的基础,因为只有当无线传感节点经过配置阶段确定数目和位置之后,才可以进行实际应用和一些相关协议的设计与实现。故而,配置问题对于无线传感网络而言是相当重要的,在过去几年中,出现了很多无线传感网络中的配置算法。这些配置算法虽然针对无线传感网络的连通性、覆盖性、能耗、拥塞控制、存储能力等问题进行了研究,但其大多存在这样或者那样的缺点,诸如：应用背景适用性较差、假设过强、可扩展性差、计算与通信复杂度较高等特点。针对这一现状,我们在对配置问题进行了广泛的调研和研究的基础上,针对无线传感网络的传输可靠性较差,能量有限,存储和计算能力有限,现有配置算法缺乏对无线传感节点移动性的深入研究等问题,提出了一些相关的无线传感网络配置算法。首先,针对无线传感网络的数据传输可靠性较差的问题,本文研究了无线传感网络的可靠中继节点配置问题,其目标是使用最少数目的中继节点以保证整个无线传感网络的可靠性。本文提出了一种基于集合覆盖的迭代算法,并且分别研究了单层无线传感网络和两层无线传感网络下的可靠中继节点配置问题。同时,我们还证明了本文提出的单层无线传感网络的可靠中继节点配置算法与最优配置的最差性能比为(1+「(2~1/2D-2r/2R)」)(lnn-lnlnn+θ(1)),而两层无线传感网络的可靠中继节点配置算法的最差性能比为(1+「(2~1/2D/2R)」)(lnn-lnlnn+θ(1)),其中D为感知区域直径,n为初始无线传感节点数目,R＞r＞0分别为中继节点和传感节点的通信半径。其次,针对无线传感网络的能量有限的问题,本文研究了面向无线传感网络最大生命周期保证的中继节点配置算法。网络的生命周期,是无线传感网络的最重要的研究问题之一。本文通过分析网络结构对网络生命期造成的影响,研究了无线传感节点位置和数目与网络生命周期的关系,设计了相应的配置算法来保证无线传感网络的生命周期。算法首先放置一定数目的无线传感节点使整个网络连通,满足无线传感网络的基本要求,然后通过选择合适的节点位置进行冗余配置,保证整个无线传感网络的生命周期达到最长。然后,针对无线传感网络存储和计算能力有限的问题,本文研究了无线传感网络中的存储节点配置问题。算法通过在无线传感网络放置一定数目的存储节点来存储临近节点发送的数据,以减轻网络中的数据传输量。本文首先对存储节点配置问题进行规约,在这一过程中修正了已有算法在能量模型定义上的不足,并证明无线传感网络中的存储节点配置是NP-hard问题；接着文章提出了一个基于反向贪心策略的近似算法,并且证明了其最坏情况下的性能比为O(log n),其中n为网络中的传感节点数目。最后,针对现有配置算法缺乏对无线传感节点移动性进行深入研究的问题,本文研究了无线传感网络中移动节点配置问题,关注于移动节点密度与动态无线传感网络的扫描覆盖度之间的理论关系。在移动无线传感网络中,其实并不需要对感知区域中的每个点进行持续监测,对其中的每个点进行周期性监测已经足以满足大部分应用的需求,这一新型的覆盖模式被称之为扫描覆盖,其可以节省大量的无线传感节点。在本文中,我们首先探讨了移动传感网络中的t-扫描覆盖问题,并给出形式化定义,然后分析在无线传感网络中满足t-扫描覆盖的移动节点的最小密度。我们假设移动传感节点的速度为v,感知半径为R,无线传感网络的扫描间隔要求为t,则在完全移动无线传感网络中,当vt≥2(3~1/2)R时,移动节点密度为O(4／3vtR),否则移动节点密度为O(2／3(3~1/2)R2)；而存在一定数目的静态无线传感节点的混合网络中,当vt≥2(2~1/2)R时,移动节点密度为O(4(2~1/2)／evtR),否则移动节点密度为O(2／eR2)。更多还原

【Abstract】 Wireless Sensor Networks (WSNs) consist of a great number of sensor nodes which are composed of sensing unit, processing unit and communicating unit. Wireless sensor networks have a broad application prospect and great practical significance in human life, because WSNs are good for hiding, quick at network building, widespread, simple and inexpensive, easy to expand, small in size, large in scale, and they have flexible structure. WSNs can be used in various applications including:military, environment monitoring, health, space exploration, agriculture, intelligent home, and so on. However, there are many problems and challenges in wireless sensor networks, such as limited energy consumption, limited ability on storage, computing, and communications, low-bandwidth, etc. Therefore, researchers need to consider the various features of wireless sensor networks deeply, and make sure that wireless sensor networks can be efficientively and widely used. It is just the reason that there are a lot of protocols designed for wireless sensor networks, such as routing protocols, MAC protocols, topology control, data processing technology, and so on.However, most of the existing researches on WSNs are carried out after sensor nodes have been deployed, and some studies even completely ignore the structure of WSNs. These researches neglect that WSNs can be configurable. In fact, after sensor nodes are dispersed into the sensing field, we can take advantage of the mobility of sensor nodes, or adding some sensor nodes to rebuild the structure of WSNs, so that the performance of wireless sensor networks can enhanced significantly. This is the placement problem in wireless sensor networks that we will focus on in this paper.In fact, placement is the foundation of various applications in WSNs, because only if sensor nodes have been placed in the sensing field with specific number and positions, we could carry out the practical applications, and the design of all kinds of protocols. Placement is actually very important in wireless sensor networks, and in the past few years, there have been many placement algorithms for WSNs. Although, these placement algorithms focus on connectivity, coverage, energy consumption, congestion control, storage capacity and other issues in WSNs, there is still one or more shortcomings in these algorithms, such as:poor application background, too strong assumption, poor scalability, higher degree of complexity on computing and communications and so on. In response to this situation, we have conducted a wide range of investigation on placement problem in WSNs. Based on the weaknesses of wireless sensor networks, which are of poor transmission reliability, limited energy, limited storage and computing ability, the lack of placement algorithms for mobile sensor networks, we design a set of placement algorithms for wireless sensor networks.First of all, as WSNs have low reliability of data transmission, we study the problem of reliable relay node placement in wireless sensor networks, which aims to use minimum number of relay nodes to ensure the reliability of WSNs. We propose a set-cover based iterative algorithm for this problem which is to place minimum number of relay nodes for the reliability of two typical networks:single-tiered network and two-tiered network. We also prove that the performance ratio of the our placement algorithm is no worse than (1+[(2~1/2D-2r/2R)])(lnn-lnlnn+(?)(1)) for the single-tiered wireless sensor network, and the placement algorithm for the two-tiered network is no worse than (1+[(2~1/2d)/2R])(lnn-lnlnn+(?)(1)), where D is the size of the sensing field, n is the number of initial sensor nodes, constants R> r> 0 are the communication radius of relay node and sensor node.(?)Secondly, this paper studled relay node placement preblem for maximizing the lifetime of a wireless sensor network. Network lifetime is one of the most important research issues in wireless sensor networks. Through analyzing the impact of the positions and number of sensor nodes on network lifetime, we design placement algorithm to prolong the lifetime of WSNs. At first, some relay nodes are placed to connect the whole wireless sensor network through a greedy scheme to satisfy the basic requirement of WSNs. Next, some redundant relay nodes are placed to maximize the network lifetime. And then, we prove that the network lifetime can achieve maximum value through our algorithms.And then, we study the storage node placement problems in wireless sensor networks, to solve the problem that WSNs have limited storage and computing ability. By placing a certain number of storage nodes to store sensing data coming from back-fence sensor nodes, the data traffic in wireless sensor networks can be reduced. We first formulate the storage node placement problems, with modifying the shortcoming of the definition in the energy model of existing methods. And then, we proved that the storage node placement problem in wireless sensor networks is NP - hard; next we present a reverse-based greedy approximation algorithm for the problem, and we also prove that the performance ratio under worst-case of our algorithm is O(log n), where n is the number of sensor nodes.Finally, we study the placement problem in mobile wireless sensor networks, and we focus on the theoretical relationship between the mobile sensor density and sweep coverage. In mobile wireless sensor networks, there is no need to monitor each point in the sensing field continuously. In fact, periodic monitoring is sufficient to meet the needs of most applications in mobile wireless sensor networks. This new coverage model is called sweep coverage, which can save a large number of sensor nodes. In this paper, we first explored t-sweep coverage problem in mobile wireless sensor networks, and then, we gives a clear definition on it. Next, we calculate the minimum sensor density to satisfy t-sweep coverage. It is assumed that the speed of mobile sensor nodes is v, the sensing radius is R, scanning interval is t, then in mobile wireless sensor networks, if vt≥2(3~1/2)R, then the density of mobile nodes should be O(4/3vtR) to satisfy t-sweep coverage, otherwise, it is O(2/3(3~1/2)R2); in hybrid sensor networks with a certain number of static sensor nodes, if vt≥2(2~1/2)R, the density of mobile nodes should be O(4(2~1/2)/evtR), otherwise, it is O(2/eR2).更多还原