摘 要

无线传感器网络在军事、国家安全、环境监测等领域有巨大的应用价值，已经引起了世界许多国家专家学者们的极大关注。由于传感器节点一旦部署后就不能再次对其进行充电或更换电池，而其电池本身的能量又十分有限，所以为了延长网络的寿命，会在监控区域内分布大量节点轮换工作。如果太多的节点同时工作，就会消耗大量的能量，也会降低节点的使用效率，因此，怎样选择最优的节点集合，在保证完全覆盖的条件下以最少的工作节点和最低的能耗，对目标监控区域进行有效的覆盖成为无线传感器网络研究中的一个重要问题。本文分别对节点传感半径可调和固定的情况进行理论最好和最坏情况的成本分析，计算出了成本的取值范围，然后提出了优化节点部署的算法并进行了实验验证，结果表明算法在降低能量消耗上有效。

关键词：无线传感器网络；成本最低；半径可调；节点部署优化

Abstract

Wireless sensor networks have shown great value in many application areas，such as military，national security and environmental monitoring，causing most concern of experts and scholars from many countries in the world. sensor nodes once deployed，it’s unavailable for them to replace or charge the batteries. However，energy of the batteries are limited. Hence to extend the lifetime of sensor network，there are lots of sensor nodes which work in turn deployed in the interest area. If there are many nodes working simultaneously，much energy will be consumed while the efficiency of nodes will decrease. Therefore，it becomes an important problem in wireless sensor network research that how to select the set of nodes to cover the interest area with efficiency on the premise that complete coverage should be ensured. This article analyzes the best and the worst theoretically cost of two different situations，one of that is that the radius of sensor nodes are adjustable while another is that the radius of sensor nodes is fixed，and the range of the cost is figured out. Then node deployment optimization algorithm is proposed and the result shows the efficiency in reducing energy cost of the algorithm.

Key Words: Wireless sensor network；Lowest cost；Adjustable radius；Nodes deployment optimization

目 录

第1章 绪论 2

1.1 无线传感器网络 2

1.1.1 无线传感器网络简介 2

1.1.2 无线传感器网络特点 2

1.1.3 无线传感器的应用领域 4

1.2 研究背景及意义 5

1.3 国内外研究现状 6

1.4 研究内容 7

1.5 本文章节安排 7

第2章 无线传感器网络节点部署优化算法 9

2.1 引言 9

2.2 问题描述 9

2.2.1 节点感知模型和能耗模型 9

2.3 两种情况成本分析 10

2.3.1 感知半径固定 10

2.3.2 感知半径可调 11

2.4 节点部署优化算法 14

2.5 程序设计 16

第3章 实验结果分析 18

3.1 α=2时的成本分析 18

3.1.1 算法有效性 18

3.1.2 算法稳定性 19

3.2 α取其它值时的成本分析 20

3.2.1 α=1 20

3.2.2 α=3 21

3.2.3 α=4 22

第4章 总结与展望 23

4.1 总结 23

4.2 展望 23

参考文献 25

致谢 26

第1章 绪论

1.1 无线传感器网络

1.1.1 无线传感器网络简介

无线传感器网络(Wireless Sensor Networks, WSN)是一种分布式传感网络，由大量配备有一个或多个传感器、一些处理电路以及无线收发器的微小设备组成，这些设备称为传感器节点^[1]。这些节点非常小，因而使得在偏远地区部署大量传感器节点是一件很容易的事情，一旦部署，这些节点自组织成一个网络，所以它们能够结合各自对环境的监测情况。通过结合这些分散的监测情况就能给用户提供监测区域的全局视图。一个节点的能量通常来自于一个附加的电池元件，而一个元件的尺寸是有限的，因而其带有的能量也非常有限。传感器网络的结构、应用以及部署策略必须满足低能耗的要求。我们研究节点在目标监测区域的部署问题以实现用最低能量消耗来完成对该区域的完全覆盖。

一个典型的无线传感器的系统架构包括大量传感器节点、接收发送器汇聚节点、Internet或通信卫星、任务管理节点等部分^[2]，如图1.1所示。

图1.1 无线传感器系统架构

1.1.2 无线传感器网络特点

1. 大规模。一个传感器网络由大量传感器节点组成，这些节点被密集地部署在目标区域里或区域附近。传感器节点的位置不需要改变，也不需要预先确定，这就使得在交通不便的地形或救灾行动中随机部署传感器节点能够完成。
2. 自组织^[3]。传感器网络的大规模性也意味着传感器网络的协议和部署算法需要具备自组织能力；传感器网络之间相互协作，每个传感器节点上都配备有一个主板处理器，传感器节点运用它们的处理能力在本地进行简单的计算和发送需要的和部分处理过的数据，而不是直接将原始数据发送到负责数据融合的节点。
3. 能量限制。在真实的环境中，随机抛撒大量节点，每个节点都密集地分布于目标区域中，传感器节点通过自身所带的电池进行供电，一旦电池电量耗尽，节点便失去了感知和通信的能力。由于网络节点的部署具有随机性，所以网络的结构是处于动态变化中的，而维护网络的结构也是需要消耗能量的，所以节点的部署方式是无线传感器网络中研究的一个重要问题。
4. 动态性。传感器节点在初始部署后可能改变它们的位置。可移动性可能是由于环境的影响，例如风向、水流，传感器节点可能依附在可移动的实体上或者被搬运，传感器节点也可能本身拥有可移动的功能。换句话说，可移动性可能是个偶然的副作用，或者是系统需要的属性（例如，移动节点到目标物理位置），这样看来，可移动性可能是积极的（自动的）或者消极的（例如，不受传感器节点的控制依附在可移动的物体上）。可移动性或许适用于网络中的所有节点或只适用于部分节点。可移动性的程度也可分为长时间静止偶尔移动和持续移动。可移动性对网络动态性有很大的影响，从而影响网络协议和分布式算法。实际的移动速度也会产生影响，例如，当节点保持在彼此的通信范围内时。
5. 体积和成本限制。根据应用程序的实际需要，单个节点的组成要素可能从一个鞋盒大小（如气象站）到显微镜下的粒子大小（对于几乎看不见的传感器节点在军事上的应用）不等。同样，单个设备的成本可能从几百欧（对于拥有少量但是强大的节点的网络）到几美分（对于由简单节点组成的大规模网络）不等。由于传感器节点是无线自动设备，它们的能量和其他资源受到大小和成本的限制而非常有限。不同的大小和成本约束直接导致可用能量相应的不同的限制（即大小、成本和电池能量密度或消耗能量的设备），像计算、存储和通信资源一样。因此，一个节点的能量和其它可用资源也因系统的不同而有很大差异。能量既可以被存储（例如在电池中）又可以从环境中获得（例如通过太阳能电池）。
6. 不均匀性。早期的传感器网络预期从硬件和软件的角度来看是由均质设备组成。像非晶计算一样的一些项目甚至假设传感器节点之间是没有区别的，也就是说，它们甚至没有唯一的地址和名称，这一假设建立在生产大量的廉价传感器节点是可行的基础上。然而，在今天的许多可用的原型系统中，传感器网络包含各种不同的设备，节点的类型和附加传感器的数量可能不同；一些计算功能强大的“计算”节点可能从许多数据更有限的传感节点收集、处理、路由感应数据；一些传感器节点配备有特殊的硬件作为其它节点的指向标来推断它们的位置，如GPS接收器；一些节点可能作为远程数据通信网络（如GSM网络、卫星网络或互联网）的网关。传感器网络不均匀的程度是一个重要因素，因为它会影响在传感器网络上执行的软件的复杂性和整个系统的管理。

根据应用程序的需求，传感器网络必须支持像实时约束（例如，一个物理事件必须在一段时间内被报道）、健壮性（即，即使出现故障，网络也应该继续运作）、抗干扰（即，即使受到蓄意攻击，网络也应该继续运行）、防窃听（即，外部实体不能窃听数据流量）、不易被察觉或隐形（即，网络必须是很难去检测的）等服务质量。

（7）基站。构造实际的通信网络可以采取多种形式。两种常见的形式一种是基站网络，另一种是自组织网络。在基站网络中，传感器节点只能与基站直接通信。传感器节点之间的通信是通过基站的传递完成的。如果有多个基站，这些基站之间必须能互相通信。基站的数量取决于通信的范围和传感器节点的覆盖面积。移动电话网络和智能尘埃就是这种网络的例子。