基于备份节点无线传感器网络设计策略

1 引 言

随着无线网络以及硬件技术，特别是超大规模集成电路技术的发展，将感知、通信、计算能力集成在一个传感器节点成为可能。无线传感器网络(以下简称传感器网络)就是由成千上万个这样的节点构成的。

它集感知、通信功能于一身，其目的就是实现对恶劣环境或者是人所不易到达的环境中各种参数(如温度、湿度、目标位置等)的监测和对某些敏感数据的采集。传感器网络如今已经得到了广泛的应用，包括用以分析远距离无人地区的环境情况(如依靠采集温度来实现对森林火警的监测);将感知节点安装在特定的交通工具上以分析本地区的通信流量并由此设计出从源点到目标点的最佳交通路线;军事上可用于监测、定位和跟踪目标点的运动;在高污染区还可以收集相关的信息以便于灾后重建。由于这些传感器节点受自身规模的限制，而且能源有限，要给网络内大量的节点重新补充能源几乎是不可行的，这就需要考虑如何在能源有限的情况下最大限度地降低节点能耗以延长传感器网络的连续工作时间。

2 准备工作

传感器节点按其功能可分为以下三个模块

①感知模块。假定数据源的产生速率为r，则节点单位时间的感知耗能为Psense=a3r，a3为一常数(单位为J/bit);②通信模块。给定发送节点u和接收节点v，发送数据的速率为r，两个节点间的距离为d。有Ptrans(u，v)=(a11+a2dk)r，Prec=a12r。Ptrans(u，v)表示节点u单位时间的传输能耗，Prec表示节点v单位时间的接收能耗。其中，k为路径衰减指数(k一般取2或4)，而a11，a12和a2均为无线通信常数(其中a2的取值与k有关)。③计算模块。相比于感知模块和通信模块来说，节点的计算模块能耗很小，通常可以忽略不计。

本文假设：

①传感器网络被应用于目标跟踪的场景下。②如图1所示，E为网络内某一时刻的数据源节点，而传感器节点主要用于对指定目标点的监测并将采集到的结果以多跳的方式传输给远端的收集节点B，这里我们认为节点B的能量充分大，即不考虑节点B的能耗。假设传感器网络中节点数量为N。③节点随机的分布在有限区域R内，节点的通信半径为rt，节点间的数据传输是双向的，即对于网络中的任意两个节点u和v，若节点u可与节点v直接通信，则节点v也可与节点u直接通信，如图1，节点的感知半径为ds，即感知节点只有在距数据源ds之内才能感知到它的存在。④传感器网络内所有的感知节点天线位于同一个水平线上，并且天线是全向的。⑤利用GPS技术传感器节点可获取自己的位置信息，目前GPS的精度可达5 m左右。

由文献[3]可知，给定一个二维空间R，传感器节点的感知半径ds，能耗参数a11，a12，a2，a3和路径衰变指数k，感知节点的数量N，每个节点的初始能量E，并且假定数据源运行轨迹遵循某个均匀分布的概率分布函数lsource(x，y)，则可得到网络生存时间T的上限值为

3 算法思想

传感器网络实际上就是以数据为中心的自组织网络，但在以前的关于传感器网络生存时间的研究中都是假定周围环境是可靠的，即感知节点只有在能量完全耗尽时才会失效，这并未考虑环境对感知节点的影响。

在传感器网络中，由于距数据源ds内的节点均能采集到数据并将数据进行转发，因而如何保证这些节点尽可能的长时间持续运行是我们所关注的问题，针对该问题我们借鉴了容错冗余的概念引入了备份的感知节点，使得某个感知节点的失效并不会影响整个网络的正常工作。因而在本文中，我们提出了一个基于备份的分布式算法以延长网络的连续工作时间，仿真结果表明在节点失效环境下通过合理的控制节点数量，该算法的持续工作时间要长于文献[3]中的方法。

4 算法描述

在算法的实际运行中，可分为三个阶段，分别为初始化阶段、数据传输阶段和任务接管阶段。

在初始化阶段，网络中的每个节点需要确定自身到收集节点B的最小跳数。每个节点的初始状态先置为工作态。收集节点首先以通信半径rt广播一个HOP消息。除收集节点之外，每个节点的初始跳数设置为无穷大。HOP消息的初始跳数设置为0。当某个节点收到HOP消息后，它将检查是否已经接收过该消息。如果未曾收到过，则该节点将把发送节点的信息(包括发送节点的ID号)放入其路由表中并把发送节点设为自己的上游节点，将HOP消息的跳数加1并将其值设置为自己的跳数，之后便以通信半径rt将新的HOP消息转发给邻居节点;否则(即某个节点以前曾收到HOP消息)该节点将退避一段时间后再发送该HOP消息。并且，该节点只会考虑在退避时间内所收到的最小跳数的HOP消息。经过退避时间后，节点将对所收到的HOP消息的跳数与节点以前曾保存的跳数进行比较：如果前者比后者小于1，则节点将把发送者的信息也放人路由表中作为自己的另一个不同的上游节点;如果前者小于后者且二者之差大于1，则发送者将成为该节点的新的上游节点。相应的，路由表中的节点跳数以及消息跳数均需更新，修改后的HOP消息将继续被该节点中转;如果前者不小于后者，则节点将丢弃这新收到的HOP消息。注意在以上的描述中，节点仅在收到第1个HOP消息时才会立即进行转发。这一策略的好处在于可以加快HOP消息的传输速率，也缩短了初始化阶段的执行延迟。另一方面，引入退避时间的好处在于可以让节点处于等待状态以便可以从其邻居节点接收到更多的HOP消息。虽然较长的退避时间会增加此阶段的完成时间，但该方法是有效的，因为该阶段对静止的传感器网络来说只需执行一次，并且也可以避免由于额外的转发消息而增加的能耗。毕竟，能源问题是传感器节点最宝贵的资源。可以看到，在初始化阶段执行之后，每个节点将准确的获知自己的最小跳数以及其所有的上游节点。

当指定要监测的目标出现后即进入了数据传输阶段。感知到该目标的多个节点利用信息交互尽可能的挑选出跳数最小且自身能量最大的节点作为目标的感知节点，而其他感知到该目标的节点作为备份节点，这些备份节点将进入休眠状态以降低节点能耗。在数据真正传输之前，真正的感知节点利用Rodoplu等人提出的MECN算法和节点的上游节点信息建立一条从源节点到收集节点B的最小能耗路径。

当出现下述两种情况之一时将进入任务接管阶段：①正常工作时(主动)的任务切换。此时，随着感知节点的运行，自身能耗也随之下降，当其无法再次完成数据的感知(或传输)任务时将主动地发起任务接管的命令。②感知节点异常时的任务切换。由于正常运行时所有的备份节点处于休眠状态，因此并不能使用分布式系统中的心跳技术来对感知节点的状态进行检测。这里我们采用超时方法，即当收集节点B在指定的时间间隔T内无法收到来自目标点的数据时，这就有可能存在感知节点失效的情况，此时收集节点B将会给传感器网络发出泛洪信息，利用定向扩散的原理将备份节点集中的节点唤醒后重新进行初始化操作。

当距离数据源节点ds内的所有传感器节点均没有足够的能量可以将数据转发给任意一个邻居节点时，整个传感器网络的持续工作时间将会终止。

5 算法消息负载分析

本节中，从单个节点平均处理的消息角度出发，我们对所提出算法的消息负载进行简单分析。

初始化阶段：每个节点广播的HOP消息数依赖于退避时间设置的大小。可以看到如果退避时间足够大，每个节点最多广播2个HOP消息：在节点从其邻居节点收到第1个HOP消息后将广播第1个HOP消息;而当退避时间超时后将广播第2个HOP消息。

数据传输阶段：感知节点只需要感知到指定目标的多个节点之间的广播消息即可确定，即此阶段节点只需广播1个消息。

任务接管阶段：正常工作时的任务接管节点只需广播1个消息;同样，异常时的任务接管节点只需发送1个来自于收集节点的泛洪消息(实际上该阶段与初始化阶段节点广播HOP消息的过程正好相反，我们可以寄期望如果该步骤的退避时间设置恰当的话，大多数节点广播的次数之多为1次)。可见，该阶段每个节点最多广播1个消息。

总之，如果初始化阶段和任务接管阶段的退避时间设置适当的话，算法中传感器节点的消息负载最多为4个广播消息。

6 仿真结果

采用由Berkeley大学开发的离散时间仿真工具Ns-2.29，假设传感器网络内所有节点随机均匀的分布在1500 m×1500 m的矩形范围内，节点的数量为N(150≤N≤1500)，每个节点的初始能量设置为2 J，其目的只是为缩短仿真实验的运行时问，并不会对仿真实验的行为产生任何变化。节点的无线传输半径rt设置为50 m，节点的感知半径ds设置为20 m，路径衰减参数k为4，a3=50 nJ/bit，a11=45 nJ/bit，a12=135 nJ/bit，a2=0.001 pJ/bit/m4，数据源的产生速率为1 bit/s，在节点上应用的路由协议采用无线自组网的AODV协议，应用层的流量发生器采用CBR(constant bit rate)，大小为512 bit/s。为得到更为可靠的数据结果，对每一种算法执行100次，对每一次的实验，均产生10个随机不同的传感器网络拓扑结构，最终仿真结果通过取平均值得到，置信区间设为95%。

在实际运行中，考虑正常和失效(随机模拟感知节点的失效)两种情况下算法的性能。给定不同的网络节点数，将新算法与文献[3]中的方法进行比较，给出了实验中得到的仿真结果与由式(1)得到的理论值之间的比率，如图2所示。

从图2中可以看出，在正常情况下，新算法的网络生命期要小于文献[3]中的理论值，这是因为相比于文献[3]，新算法中在运行过程中传感器节点有一部分能量消耗在了算法消息交换的执行上;而在感知节点失效的情况下，可以看到当150≤N≤550或者是N≥750时新算法的网络生命期要小于文献[3]中的理论值，原因在于当150≤N≤550时，由于网络中感知节点过少，有的节点则既作为感知点又作为中转节点，所以此时整个网络的时间性能会下降得很快;而当在N≥750时，随着网络中节点的增多，整个网络的密度增大，每个节点的邻节点数量增加，信道争用、信道发生冲突的概率也会相应增加。反过来也会给网络的生存时间带来不利的影响。但是当550≤N≤750时，本算法的网络生存时间要大于文献[3]中的理论值，即新算法的网络性能要优于文献[3]。因此，本文提出的分布式算法特别针对于网络中节点失效情况下的处理方法是可行的。

图3给出了算法在运行过程中节点平均消息负载与时间的关系示意。由图3可以看到随着部署节点的增加，每个节点的平均消息负载并没有显著的增加，这从另一方面验证了文中所设计的算法可适用于大规模的传感器网络;此外，还观察到从节点开始工作直至到达网络的生存时间，每个节点最大的消息负载只有5个，因此该算法是有效的。

7 结 论

为延长网络的持续工作时间，提出了一个基于备份感知节点的分布式算法，实验证明了该算法在时间上有进一步的提高，从而可以指导我们在现有的情况下如何对节点进行优化管理从而提高网络生存时间。在今后工作中需要进一步开展的研究方向包括：

①本文所提出的算法中在感知节点失效的情况下，由收集节点B主动发起泛洪信息，将会导致网络无线通道的拥塞引起网络性能的下降，并且网络中会出现某些节点收到多个邻节点发来的同一泛洪信息的现象，这将会占用节点宝贵的内存资源。能否采用其他方法来避免这种不必要的通信开销和资源占用是今后研究的一个方向。

②在算法中，假定数据源节点的数量为一个且位置固定，今后需考虑当数据源节点为多个且移动情况下的分布式容错算法。

③传感器网络的算法都是与应用环境相关的，在某些情况下如果只使用一个感知节点的话，由于节点观测事物角度的不同，将会影响数据采集结果的精确度，这就需要同时有多个节点间的合作以提高获取数据的准确度。如何在准确性和网络能耗两个方面进行折衷考虑也是一个值得研究的问题。