基于无线传感器网络的采样算法.docx

1、基于无线传感器网络的采样算法基于无线传感器网络的采样算法 1.无线传感器网络的研究背景及应用现状 1.1 研究背景 无线传感器网络(Wireless Sensor Network，简称WSN) 的基本功能是将一系列在空间上分散的传感器单元通过自组织的无线网络进行连接，从而将各自采集的数据进行传输汇总，以实现对空间分散范围内的物理或环境状况的协作监控，并根据这些信息进行相应的分析和处理。因具有成本低、范围大、布设灵活、移动支持等特点，无线传感器网络在工业监控、智能电力、矿山安全、医疗健康、环境监测等行业的应用一直广受重视;与此同时，无线传感器网络也面临着延长节点工作时间、增加通信距离、小型化、标

2、准化等技术挑战和寻找应用场景等市场挑战。无线传感器网络的研究经历了以下四个阶段： （1）第一代传感器网络：20世纪70年代。点对点传输，具有简单信息获取能力。 （2）第二代传感器网络：获取多种信息的综合能力，采用串/并接口与传感控制器相联。 （3）第三代传感器网络：20世纪90年代后期。智能传感器采用现场总线连接传感控制器构成局域网络。 （4）第四代传感器网络：以无线传感器网络为标志，正处于研究和开发阶段。 近年来，无线传感器网络引起了业界极大关注，其应用环境通常是由价格便宜的传感器节点组成的，每个节点都能够采集、存储和处理环境信息，并且能和邻居节点通过无线链路保持通信。覆盖问题是无线传感器网

3、络配置首先面临的基本问题，因为传感器节点可能任意分布在配置区域，它反映了一个无线传感器网络某区域被监测和跟踪的状况。随着无线传感器网络应用的普及，更多的研究工作深入到其网络配置的基本理论方面，其中覆盖问题就是无线传感器网络设计和规划需要面临的一个基本问题之一。随着深入研究的角度不同，覆盖问题也表述成不同的理论模型，甚至在计算几何里面就能找到与覆盖相关的解决方案。尽管这些办法并不能直接应用到无线传感器网络1 中，但是研究这些问题有助于建立读者对无线传感器网络覆盖问题相关的理论背景。 1.2 无线传感器网络的应用现状 虽然无线传感器网络的大规模商业应用，由于技术等方面的制约还有待时日，但是最近几年

4、，随着计算成本的下降以及微处理器体积越来越小，已经为数不少的无线传感器网络开始投入使用。目前无线传感器网络的应用主要集中在以下领域： （1）环境的监测和保护 随着人们对于环境问题的关注程度越来越高，需要采集的环境数据也越来越多，无线传感器网络的出现为随机性的研究数据获取提供了便利，并且还可以避免传统数据收集方式给环境带来的侵入式破坏。比如，英特尔研究实验室研究人员曾经将32个小型传感器连进互联网，以读出缅因州大鸭岛上的气候，用来评价一种海燕巢的条件。无线传感器网络还可以跟踪候鸟和昆虫的迁移，研究环境变化对农作物的影响，监测海洋、大气和土壤的成分等。此外，它也可以应用在精细农业中，来监测农作物中

5、的害虫、土壤的酸碱度和施肥状况等。 （2）医疗护理 无线传感器网络在医疗研究、护理领域也可以大展身手。罗彻斯特大学的科学家使用无线传感器创建了一个智能医疗房间，使用微尘来测量居住者的重要征兆（血压、脉搏和呼吸）、睡觉姿势以及每天24小时的活动状况。英特尔公司也推出了无线传感器网络的家庭护理技术。该技术是做为探讨应对老龄化社会的技术项目Center for Aging Services Technologies（CAST）的一个环节开发的。该系统通过在鞋、家具以家用电器等家中道具和设备中嵌入半导体传感器，帮助老龄人士、阿尔茨海默氏病患者以及残障人士的家庭生活。利用无线通信将各传感器联网可高效传递

6、必要的信息从而方便接受护理。而且还可以减轻护理人员的负担。英特尔主管预防性健康保险研究的董事Eric Dishman称，在开发家庭用护理技术方面，无线传感器网络是非常有前途的领域。 （3）军事领域 2 由于无线传感器网络具有密集型、随机分布的特点，使其非常适合应用于恶劣的战场环境中，使其非常适合应用于恶劣的战场环境中，包括侦察敌情、监控兵力、装备和物资，判断生物化学攻击等多方面用途。美国国防部远景计划研究局已投资几千万美元，帮助大学进行智能尘埃传感器技术的研发。哈伯研究公司总裁阿尔门丁格预测：智能尘埃式传感器及有关的技术销售将从2004年的1000万美元增加到2010年的几十亿美元。 （4）其

7、他用途 无线传感器网络还被应用于其他一些领域。比如一些危险的工业环境如井矿、核电厂等，工作人员可以通过它来实施安全监测。也可以用在交通领域作为车辆监控的有力工具。此外和还可以在工业自动化生产线等诸多领域，英特尔正在对工厂中的一个无线网络进行测试，该网络由40台机器上的210个传感器组成，这样组成的监控系统将可以大大改善工厂的运作条件。它可以大幅降低检查设备的成本，同时由于可以提前发现问题，因此将能够缩短停机时间，提高效率，并延长设备的使用时间。 尽管无线传感器技术目前仍处于初步应用阶段，但已经展示出了非凡的应用价值，相信随着相关技术的发展和推进，一定会得到更大的应用。但就目前的技术水平来说，让

8、无线传感器网正常运行并大量投入使用还面临着许多问题： （1）网络内通信问题。无线传感器网络内正常通信联系中，信号可能被一些障碍物或其他电子信号干扰而受到影响，怎么安全有效的进行通信是个有待研究的问题。 （2）成本问题。在一个无线传感器网络里面，需要使用数量庞大的微型传感器，这样的话成本会制约其发展。 （3）系统能量供应问题。目前主要的解决方案有：使用高能电池；降低传感功率；此外还有传感器网络的自我能量收集技术和电池无线充电技术。其中后两者备受关注。 （4）高效的无线传感器网络结构。无线传感器网络的网络结构是组织无线传感器的成网技术，有多种形态和方式，合理的无线传感器网络可以最大限度的利用资源。

9、在这里面，还包括网络安全协议问3 题和大规模传感器网络中的节点移动性管理等诸多问题有待解决。 2. 无线传感器网络相关技术 2.1无线传感器网络节点构成 无线传感器网络由大量体积小、成本低、具有无线通信、传感、数据处理的传感器节点以自组织方式构成。传感器节点构成了网络的硬件基础。节点具备三个功能：首先，作为现场信息采集单元要完成信息的采集并按要求对采集到的信息进行适当的预处理，因此节点包括数据采集模块及数据预处理模块；其次，传感器节点还具有信息转发功能，将采集到的现场信息通过一定的方式传输到其他节点或信息处理中心，因此节点还必须包括通信模块来完成信息的接收、传递等；第三，当节点处要实现某种控制

10、作用时，还需要有控制模块。一般来说，无线传感器节点由以下几个物理部分构成： （1）由微处理器或微控制器构成的计算子系统，负责控制传感器、执行通信协议及处理传感数据的算法； （2）用于无线通信的短距离无线收发电路，即通信子系统； （3）由一组传感器和激励装置构成的传感子系统。 实际应用中，并不是所有的节点都需要控制模块。传感器节点的一种基本模型如图2-1所示。包括传感器、ADC、CPU及存储器、通信模块、控制模块及电源（能量）等，当不需要控制作用时，节点组成如图2-1中粗线内部分所示。所有这些模块组装成一个火柴盒大小甚至更小的传感器节点，各模块相互协作以完成一项共同的任务。 控制器控制模块微处理

11、器传感器无线收发ADC存储器通信模块数据处理模块采集模块DC/DC电池供电模块 传感器节点基本模型图2-1 4 除此之外，根据具体应用的需要，节点可能还会有定位系统、电源再生单元和移动单元等。其中电源再生单元是重要的模块之一，有的系统可能采用太阳能电池等方式来补充能量，但是大多数情况下传感器节点的电池是不可补充的。定位系统对传感器网络的路由是很重要的，有些传感器节点采用GPS进行定位，但是GPS模块价格昂贵且体积难以减少，所以不可能全部节点都使用GPS来进行定位。此外，GPS定位还受到其他限制，如网络放置于建筑物内部等。通常情况下是在整个网络中会有某些传感器节点配有GPS系统，其他节点通过局部

12、定位算法得到它们与配有GPS的节点之间的相对位置，这样所有节点都能知道各自的具体位置了。除借助GPS的定位方式外，还有离散梯度法等间接定位方式。 无线传感器网络中的节点不但要完成信息的采集、传输、预处理等，有时还涉及到较为复杂的任务调度及管理，因此在传感器网络中节点还可能带有嵌入式操作系统以进行更有效的管理，嵌入式操作系统可以是通用的如uCOSII等，也可以是专门针对传感器网络开发的操作系统，如UC Berkeley开发的TinyOS。 目前，无线传感网络的节点设计主要有两种方法：一种是利用市场上可以获得的商业元器件构建传感器节点，如围绕TinyOS项目设计的系列硬件平台；另一种方法是采用ME

13、MS和集成电路技术，设计包含微处理器、通信电路、传感器等模块的高度集成化传感器节点，如Smart Dust、WINS等。 2.2 无线传感器网络体系结构 无线传感器网络体系结构如图2-2所示,传感器网络通常包括传感器节点，汇聚节点和管理节点。传感器节点任意的分布在某一监测区域内，节点以自组织的形式构成网络，通过多跳中继方式将监测数据传送到汇聚节点，最后通过Internet或其他网络通讯方式将监测信息传送到管理节点。同样的，用户可以通过管理节点进行命令的发布，告知传感器节点收集监测信息。 5 图2-2 无线传感器网络体系结构图 传感器节点是一个具有信息收集和处理能力的微系统，集成了传感器模块、信

14、息处理模块、无线通讯模块和能量供应模块。其结构体 所示。系如图2-3 传感器节点体系结构图2-3 信息处理模块负传感器模块负责监测区域内信息的采集和转换，存储和处理自身采集的数据或者其他节点发责管理整个传感器节点、能量供无线通讯模块负责与其他传感器节点进行通讯，送来的数据， 应模块负责对整个传感器网络的运行进行能量的供应。考虑尽可能传感器节点能量的供应是采用电池，节点能量有限，保证能量的延长整个传感器网络的生命周期，在设计传感器节点时，传感器节点能量消耗的模块主供应的持续性是一个重要的设计原则。而绝大部分的信息处理模块和无线通讯模块，要是包括传感器模块、约占整个传感器节点能量消耗的能量消耗是集

15、中在无线通讯模块上，。因此，目前提出的传感器节点通讯路由协议主要是围绕着减少80% 能量消耗延长网络生命周期而进行设计的。在无线传感器网络中，路由协议不仅关心单个节点的能量消耗，同更关心整个网能量的均衡消耗，这样才能延长整个网络的生存期。这在路由协议中表现的最为无线传感器网络是以数据为中心的，时，选择路径可以不用根突出，每个节点没有必要采用全网统一的编址，更多的是根据感兴趣的数据建立数据源到汇聚节点之据节点的编址，6 间的转发路径。目前提出了很多类型的传感器网络路由协议，就是基于上述的目的。 3. 无线传感器网络协同采样路由算法性能指标 WSN协同采样路由算法的应用，有助于网络节点能量的有效利

16、用、感知服务质量的提高和整体生存时间的延长，但另一方面也会带来网络相关传输、管理、存储和计算等代价的提高。因此，WSN信息采样的性能评价标准对于分析一个信息采样策略及算法的可用性与有效性至关重要。通过从不同的角度总结出信息采样算法所面临的挑战，有助于清楚地比较出各种算法之间的优缺点。这里归纳出以下几点： 信息采样能力 (1)以环境感知、目标监测、信息获取和有效传输为主要目标的WSN需要关心对传感区域或监测目标的信息采样能力，无线传感器网络信息采样问题也正是由此而来。因此，网络对目标区域或是目标点的采样覆盖程度是衡量一个WSN信息采样算法是否优劣的首要标准。 能量有效性(即延长网络生存时间) (

17、2)由于WSN节点硬件平台资源受限、网络节点数量巨大、实际应用的环境条件复杂且大多不允许对“失效”节点进行电池更换，因此，如何节约各节点有限的电池能量并尽力延长整体网络的生存时间已成为WSN的重要性能指标。能量的有效性将是WSN信息采样所面临的一个主要挑战。 网络的连通性 (3)由于WSN是一种无基础设施的网络，大量节点采用自组织方式协同完成指令中心的查询、搜集等指令，网络节点之间需要通过无线多跳方式或直接或间接地相互通信来协同工作。网络的连通性将有效保证自身无线多跳自组织通信的开展，并直接决定了WSN感知、监视、传感、通信等各种服务质量的达到。 算法精确性 (4)由于受实际部署条件差异、网络

18、资源有限和覆盖目标特性等多方面的影响，况下是一个NP完全问题，只能达到近似优化采样。势必会造成采样控制算法执行结果产生误差，甚至不能使得WSN在很多7 情况下保证算法的有效执行。如何减小误差，提高算法的精确性成为优化采样控制算法的一项重要内容。 算法复杂性 (5)不同WSN采样控制策略及算法其实现方式不同导致算法复杂程度也有较大差别。衡量一个WSN采样算法是否优化的一项重要标准就是其算法的复杂性程度。算法的复杂性程度通常包括时间复杂度、通信复度以及实现复杂度等，需要综合考虑。 (6)算法实施策略 WSN采样控制算法的执行可以有分布式、集中式以及两者的混合式3种方式。通常来说，由于WSN自身的能

19、量消耗、协议操作代价、网络性能和精度等要求，使得利用本地信息执行的分布式算法更为适用。在一些特殊的网络操作环境下，分布式、集中式两种方式混合执行则更为有效。 除了上面列出的一些所面临的挑战之外，WSN采样控制协议算法还会存在是否需要知道网络节点位置、是否需要专门的采样控制消息等差别。同样，它们也是我们设计、分析具体协议和算法时要考察的内容。 4. 基于无线传感器网络分簇构架的协同采样算法描述及其MATLAB仿真分析 4.1 无线传感器网络中的分簇架构及算法介绍 4.1.1 无线传感器网络中的分簇架构 在采用分簇结构的无线传感器网络中，网络节点被划分为若干个簇。每个簇通常由一个簇头节点(CH)以

20、及多个成员节点(MN)组成。成员节点只与簇头通信，簇头与簇头构成高一级的虚拟骨干网，负责簇内的数据融合和簇间数据转发。因为簇头节点的能量消耗较大，通常采用周期性选择簇头节点的方法均衡网络中节点能量的消耗。簇头的集合形成连通统治集(CDS)，因为获得最优CDS是NPC问题，因此实际提出的算法均为启发式的。图4-1给出了分簇结构以及簇内与簇间的数据流向。 8 中的分簇结构及其簇内与簇间的数据流向图4-1 WSN 采用分簇结构具有如下一些显著的优点：WSN例如覆盖范围与采样精度要求(1)在满足一定约束条件情况下，簇成员节点可以在某些时间段内关闭通信模块，大幅度减少空等) 闲等待状况的能量消耗，因此可

21、节省能量。 簇头通常负责采集簇成员发送来的数据，这些数据具有较大(2)在保证信息量的情况下降低因此可以采用数据融合算法，的相关性， 数据通信量，降低数据转发的能量开销。因为采用层次结构，簇成员只需了解到所属簇头的路由信息，(3)减簇头只需了解簇头间的路由信息，因此可降低路由协议的复杂度， 少路由表项数目，路由维护开销也随之降低。 的应用场景。更加适合于大规模(4)具有较好的可扩展性能，WSN9 4.1.2 无线传感器网络分簇算法介绍 (1)集中式/分布式算法 根据是否存在一个中心控制节点负责整个网络的簇划分，分簇算法可分为集中式与分布式两类。典型的集中式算法有LEACH-C、APTEEN等。我

22、们提出的基于径向基函数(RBF)的分簇算法也属于此类。中心控制节点通常有持续的电源供应、较高的存储与计算能力，并能获得网络的全局信息，因此可以采用复杂的算法获得优化的分簇结果。但是由于普通无线传感器节点能量有限，计算与通信能力不强，因此对于大型的WSN，集中式算法在灵活性、可扩展性以及健壮性等方面存在缺陷，例如很多集中式算法要求获得节点的剩余能量，因为传感器节点运行中能量不断下降，所以必须隔一段时间就得通知中心控制点更新剩余能量信息，这就造成大量额外数据包的传输，使算法的开销过大。与集中式算法不同，分布式算法一般只需要相邻节点之间互相交换信息，甚至不考虑相邻节点独立作出判断，这类算法简单、高效

23、、灵活，因此更适用于大规模WSN。目前大部分经典的WSN分簇算法如LEACH、HEED等，都属于分布式算法，Hausdorff算法、响应式分布分簇算法(RDCA)也属于这一类。 (2) 基于地理位置/地理位置无关算法 根据是否需要借助GPS获得节点的地理位置，可以将分簇算法分为基于地理位置的算法与地理位置无关算法两类。典型的基于地理位置的算法有GAF等，其他大部分常见的分簇算法，如LEACH算法等，都不需要借助于地理位置信息。基于地理位置的算法有的需要获得全局信息，有的只需要通过广播包获得相邻节点的位置信息。因为传感器网络节点数量大，单个节点造价低、能量有限，而GPS模块不但成本高而且会额外消

24、耗节点能量，因此为每个节点都配备GPS模块是不经济的。通常的做法是在网络中设置少量信标节点，一般是通过携带GPS定位设备获得自身的精确位置，然后其他传感器节点通过信标节点的位置信息根据一定的定位算法获得自身的位置。常用的定位算法有到达时间(TOA)、到达时间差(TDOA)、接收信号强度指示(RSSI)、到达角度(AOA)和距离向量-跳数等。不过在室内、水下或森林等有障碍环境中无法使用GPS系统，使其应用受到一定限制。10 基于地理位置的分簇算法一般假设节点已知自身的精确位置，而如何获得自身位置信息则不包括在算法内。 (3)确定性/随机性算法 在网络拓扑结构与每个节点的剩余能量不变的情况下，根据

25、分簇算法是否能取得确定结果，可将其分为确定性与随机性算法。在确定性算法中，节点必须等待某个特定事件发生或某些特定节点已宣布自己的角色(CH还是MN)后，才能做出决定。例如DCA算法必须等待所有权值高于自己的相邻节点宣布成为CH或者加入到某个簇后，才能确定自身是成为CH还是MN。确定性算法的一个不足之处就是收敛时间依赖于网络规模，DCA算法的时间复杂度为O(d)，d为网络直径(通常用跳数来定义)，在最差情况下(节点线性分布)，d可达到n -1(n为节点个数)。此外网络的鲁棒性不好，如果一个节点在拓扑发现阶段后失效，可能造成其相邻节点陷入无限期等待。为消除这种现象，一些算法，例如ACE算法限制节点

26、在一定次数(如5次后)结束循环等待。随机性算法根据一定的概率确定节点是否成为簇头。LEACH算法中节点成为簇头的概率仅与过去若干轮次中节点自身的状态有关，HEED算法中的概率与剩余能量有关，还有一些算法同时考虑了节点度等多种参数。随机性算法分簇结果的优化程度通常不如确定性算法，但是收敛速度较快，开销较小，鲁棒性好，特别适合大规模网络。 (4) 单层/多层算法 根据算法产生的最终拓扑结构，可分为单层和多层算法。单层算法只进行一次分簇，目前提出的大部分分簇算法，如LEACH、HEAD、GAF等都属于此类，而多层算法在前一次分簇选举出的簇头基础上继续进行分簇，选举出第二层簇头和簇成员节点，随后可以进

27、行第三层、第四层等簇头选举。多层算法一般只用于超大规模WSN，算法较为复杂。文献提出了一种多层算法(层数从1到5)，该算法以最小化系统整体能量消耗为目标，推导出系统整体能量消耗的解析式，然后通过数值计算求出不同节点密度条件下的最优解。 (5) 簇内单跳/多跳算法 根据簇内MN到CH的跳数，可分为簇内单跳与簇内多跳算法，11 也可采用单跳算法的MN直接与CH进行通信，而多跳算法中的MN可通过其他MH中继与CH进行通信。LEACH、HEED等算法采用单跳方式，而Max-min D等算法使用多跳方式。 4.2 基于无线传感器网络协同采样算法的描述及其MATLAB仿真分析 协同采样是一种分布式主动采样

28、制度，该制度要求每一个传感器合作完成任务数据采样并且利用简洁的合作方式通过相邻传感器节点实现数据的传播。这可以通过利用在相邻传感的内部联系实现。该制度的目标是在确保收集数据的质量的前提下将发送冗余信息通过无线信道的能量浪费降到最低。协同采样需要两个关键操作部分：在单个传感器节点，一个传感器测量模型作为一个基于当地传感器测量的空时坐标的函数，这些通过窃听邻近传感器无线传播而获得的。传感器协同通过向其相邻节点声明它的当地测量以帮助建立覆盖全部传感器域的全局函数逼近。为了减少冗余信息的传播，每一个传感器节点需要判断。 在Slepian和Wolf的开创性工作中显示：如果知道两个传感器节点关联的先验知识

29、，那么相互之间所需的通信量将会大大减少；然而这种先验知识很少知道。因此需要在没有传感器之间联系说明的先验知识的情况下进行大量的工作来汇总在传感器之间传播信息的特定数据。一个好的数据子集应该提供一定覆盖范围概念的观点被提了出来，并且关于这种观点已经有了许多不同的形式。一些基于这种理念所提出的方法涉及到让节点选择一个代表节点来代表相邻节点区，但这是以在选择代表节点时架高节点并且在选择一个节点来代表整个区域出现错误为代价的。另一个观点是去估计优先函数而不是无线传12 感网络的节点值。然而这个工作被限制在将传感器区域划分为一系列的Voronoi胞区，或者仅仅是最邻近算法。有人建议：一些特定的增益能够通

30、过计算当地的所获得数据的时间线和更新来获得，一个节点通过延迟这些对称的平衡达到一个政策，走向一个更加分布的形式。 我们建议在传感器远距离传播中采用这种分布式形式。这个隐含在协同采样（CS）的想法是用了一个传播政策：不仅仅在当地每一个节点上有效率，同样适用于网络，或者至少是广播范围中传感器区域组成的网络中。举个例子：如果在这个网络中的一个节点有关于模型的知识，该模型是FC最大的利用其读物。那么这个节点就可以利用它窃听到的信息去建立一个初步的估计，该估计是关于FC自己读物可以达到的最大值。如果FC的最大值不远，那么这个节点所拥有的信息就会有冗余并且这个节点不会传播或报告它的读物。通过保持静默，这个

31、节点同样向这个网络的剩余节点做出表示并且向FC发送节点自己的对当前估计的认可度。我们在估计一个传感器网络的隐藏物理函数中应用CS的观点来展示CS在实际中的应用。 在仿真之前我们对传感器传播声明一些假设： i能够听到传感器传播线路是对称的，这就是说如果传感器节点（1）j 的广播， ji的广播。 同样能够听到传感器那么传感器（2）每个传感器的传播范围是一样的。 （3）所有传感器节点传播代价是相同的。 （4）传播时间相对于退避时间可忽略不计。 13 （5）FC没有功率约束。 （6）在每次传播之前没有握手。 （7）所有传播都能被FC听到并正确解码。 i在时来表示，同时用来表示节点个节点用 我们kNN?

32、1,.,X,iYii刻的瞬时读物。这个读物是通过一个未知的函数来得到。 kf为了简化，在本论文中我们只关注时间为常数的函数，就是说。这篇论文是跟随寻找实际函数f的步伐。因为只有)f(Xf(X,k)?ii?在，估计也是个同样的过程。我们估计在传感器位置的函数f1?k?1kff 次报告之后：第K? k1k?)f(?g这里 是一个速记符号适用于所有传感器节点，这些节点已经向上k?面节点传过报告包括第K次报告。是一个估计值用来近似隐含在(.)g当前信息下的函数值，它可能是个核心函数或者是一个最邻近映射。?之间测量误差的方法是测量预测读物与实际值一个获得估计值kff 和实际读物的误差，这只适用于每个节点上的差异。次报告被传播的节点的子集，那么从作为第K如果我们定义Sk 一个最优化的观点，这个问题能够被阐述这样，任给一个误差准则：采样1,2,3.不行的是，在大多数情形