李 巍，韩九强，钟德星

(西安交通大学智能网络与网络安全教育部重点实验室电信学院自动化研究所，西安 710049)

无线传感器网络［1］(Wireless Sensor Network，WSN)是由多个节点构成的复杂网络，网络内部通过多跳近距离无线通信完成节点间数据交换、数据采集、网络配置管理等各项工作，由于其独特的工作特点，导致WSN具有通信拓扑复杂、拓扑变换频繁的特点。WSN应用范围广阔，具体应用模式各有差异，但如果按照节点在目标区域内完成初始布置后，节点位置是否发生变化来归纳，则可将其划分为两大类:节点固定的静态WSN与节点可移动的移动WSN。两种类型的WSN在学术研究上各有侧重，难点不同，从网络通信拓扑复杂度及网络拓扑动态性角度看移动WSN的研究难度要超过静态WSN，动态节点运动会引起网络通信拓扑大幅变化，进而导致网络通信效率下降、能耗增高，故需要在通信协议方面做出优化以提高网络性能、延长网络寿命，而路由协议受网络动态拓扑变换影响最为明显，所以移动WSN路由协议成为一个研究的热点、难点。

由于WSN中节点一般均采用资源受限的电池供电方式进行数据采集、传输的工作，所以伴随着节点失效，网络不断发生拓扑变化，所以即使在静态WSN中，路由协议也需要考虑网络的动态拓扑特性［2］，为了应对网络拓扑变换，Perkins［3－4］等人提出了基于路由表选择的路由协议:AWDS、DFR、DBF、DSDV［3］等，此类基于路由表协议对于网络拓扑变化反应较慢；而 BSR［5］、AODV、DSR、DYMO 等按需路由协议能够在有效降低网络开销的同时适应网络动态拓扑变化，但总体来说协议开销随网络拓扑动态变化程度提升而增大；在已建立路由基础上进行路由建立的协议如IERP、LBR、PLBR等，若无法提供网络特性的先验信息时，其在高动态拓扑情况下，协议性能仍旧不理想；基于分层的路由协议如LEACH［6－7］、FSR［8］、DDR［9］等在高动态拓扑情况下性能较为理想，但此类协议性能依赖于协议层次深度的划分及子编码寻址，协议参数选择对性能影响较为明显；针对高移动WSN提出的利用节点位置信息辅助路由的 TSG［10］、VDCH、GEOTORA［11］等协议在应对高动态拓扑网络时，如果对路由开销控制较好的状态下，网络整体性能随动态拓扑提高，性能下降较不明显。

从网络性质角度出发，移动WSN与静态WSN网络的基本特质相同，但移动WSN中使用的路由协议应根据网络节点运动情况采取针对网络高动态拓扑的措施以提高路由成功率；节点运动是其路由协议设计的挑战，但节点运动信息也是应对这一挑战最有利的工具，借鉴利用节点位置辅助路由的静态WSN路由协议思想，本文针对移动WSN高动态拓扑的特性，通过利用节点的运动信息，辅助路由工作，提出基于节点运动估计的路由选择算法NMEBRP。

1 节点收发功率动态优化模型

WSN中节点能量消耗的最主要部分是由节点无线通信模块数据收发带来的，而多节点共享通信介质的WSN中，一般采用的无线信道模型有自由空间模型、双路径地面反射模型、阴影模型等［12］，从模型准确度和仿真复杂度角度考虑，本文采用双路径地面反射模型作为无线信道模型，在双路径地面反射模型中，距离发射节点距离为d处的信号功率Pr(d)用下式进行计算:

其中，Pt为发送信号节点的发射功率；Gt和Gr分别为发送节点和接收节点的天线增益；L(L≥1)是系统的系统损耗；ht和hr分别为发送节点和接收节点的天线高度。

由于无线信号在空间中成距离的高次幂函数衰减，故节点间采取多跳转发能够较好的节省无线通信能量，节点需要根据各自位置关系判断是否针对特定数据包进行转发。将式(1)中常数合并化简为:

用有序实数对表示从前一个节点到下一个节点间的无线数据收发，如(1，2)表示从节点1到节点2的通信。节点保证能够与需要进行通信的目标节点通信的必要条件是在目标节点处的接收功率Pr(d)大于节点能够监听到的信号门限Pthreshold，则1、2节点间存在转发节点需满足:

且

若节点间均以监听信号功率门限为信号功率水平下限，则有:

Pthreshold在仿真实验环境中即为固定参数，则信号能量发送功率需满足的式(2)即能写为仅与相关节点间距离有关的不等式:

节点1、2通过计算可以得到存在转发节点的范围，其边界满足的参数方程如下式:

2 基于节点运动估计的动态路由选择算法

对于节点大量随机运动带来的网络拓扑变换频繁的问题，引入辅助信息手段来帮助各层网络协议进行性能优化是一个直接有效的解决办法。本文中，基于这一思路，使用节点的位置信息帮助网络中的独立节点进行路由选择，在使用节点位置信息辅助路由协议时，需要注意以下两个问题:

(1)使用位置信息进行判断的可信度的方向性。获取的位置信息仅仅包括其自身的实时位置信息和其邻居节点的过去某时间段内的位置信息。出于保证网络通信功能和网络实际应用效果的根本要求，运动估计获得网络通信状况、拓扑变化改善的可信度应低于网络状况恶化的可信度，以降低由于运动估计带来的网络性能误判导致的额外路由协议开销。

(2)位置信息采用的回溯时间长度。对于节点及其邻居节点未来时刻的位置估计是建立在已有过去某长度时间段节点位置变化情况的分析的基础上的，所以回溯的时间段长度非常重要，合适的回溯时间段长度能够很好的体现相应节点位置变化情况，还可以提高估计的可信度。

2.1 算法描述

对于布置在目标区域的一组无线传感器网络节点，将节点构成的集合记为:

节点的工作区域为二维平面S，其面积为L1×L2，节点部署方式为上节中的均匀随机部署，节点最大通信半径为Rradio。对于某时刻节点的位置记为:

其中i∈V。

网络中节点间位置信息的交换是通过将位置信息附加在每个发送或者转发的数据包末尾，附加的信息有节点本身的位置信息，也有节点自身已经获得的过去某一时刻目标节点的位置信息。无线传感器网络中的数据包的收发从分析的角度看，是在时间域内发生的离散事件，对于在t时刻收到的数据包中得到的节点i的位置信息记为post(i)的话，对于由上一个数据包中得到的节点i的位置信息记为post－1(i)，对于未来节点位置的估计记为 post+1，网络中的数据包的发送和接受同时都带有节点发出和收到的时刻信息，所以将收到两个相邻的数据包的时间间隔记为:

这一时间间隔ΔT对于收集到的信息的采信度评估有关。

对于节点i，其所有邻居节点对其位置预测采用如下方式:邻居节点根据过去某一时间段收到的k个数据包，获得节点i的k个过去时间点的位置信息记为:

对于某时刻节点的速度记为:

其中l=0，1，…，k。

对于节点的速度的预测值Velot+1(i)根据以下算式计算:

其中 α0+α1+…+αk－1=1。

α0，α1，…，αk－1的计算采用如下方法，其中辅助变量βm为:

其中m=0，1，…，k－1。则有:

在算法中单个节点对邻居节点进行位置估计的运算所需要的时间复杂度并不高，综合式(4)～式(6)，位置估计的复杂度基本为O(c*k)其中c为常数。所以对于估计邻居节点位置信息时，缩小k的取值在降低节点运算复杂度上并不能带来显著的效果，因此从这个角度出发降低k值的意义并不大。讨论k的合理取值的意义在于如何能够合理选择信息回溯时间长度，使得节点的运动估计既能够及时反映节点变化趋势，又能够使估计的结果具有相对的稳定性。

基于节点运动估计的路由选择算法仿真的主要步骤:(1)在满足网络目标区域覆盖要求的前提下，对于网络进行初始布置时，节点通信半径设置需使网络满足连通性条件。(2)从网络运行开始，网络中的源数据发送节点通过广播方式寻找网络中目标节点。(3)目标节点接收到源节点包含其位置信息的路由建立请求数据包后，根据其中的源节点位置信息发送附带有其位置信息的数据包进行响应。同时节点中其他节点通过发送生存周期TTL=1的广播包以期建立起各自的邻居节点表。(4)源节点发送的数据包依据目标节点位置信息进行路由，网络中的中间转发节点如有目标节点较新的位置信息可根据其信息对数据包进行修改，使数据包向目标节点位置方向传送。(5)节点在网络中一旦建立起邻居节点列表后，可自行根据本文第二章中的中间节点选择关系来修改本地路由表和节点无线收发功率，此过程由节点分布自主执行。(6)根据节点运动估计，对于邻居节点中在未来时间段内可能移动出节点最大无线通信范围的节点数目进行计算，如果小于节点邻居数目最小门限值Neighborthre(i)，节点i则通过最大通信距离发送新的TTL=1的广播数据包建立本地邻居表。

以上为路由选择的主要步骤框架，本文提出的路由协议的最大特点就是路由的发现、建立、判断使用和后期维护都是建立在对与网络中节点的具体地理位置信息的利用上，所有节点收发数据包时都要进行位置信息的附加以及提取。基于得到的位置信息，需要根据这些信息进行邻居节点数目判断以适应MWSN的高拓扑动态性。

3 仿真实验

本文利用Network Simulator 2(NS2)进行网络仿真实验，实验的主要部分为模拟了在1 200 m×1 200 m的实验范围内，节点总数为500的MWSN网络能量消耗、网络寿命等问题。实验的主要参数如下表所示。

表1 仿真参数

为了进行网络性能分析对比，本文主要采用了两种用于无线传感器网络的较为典型的协议和NMEBRP协议进行对比。其中一种路由协议为Ad hoc On-Demand Distance Vector Routing(AODV，RFC3561)，AODV［13］是一种使用在无线传感器网络或者移动无线传感器网络中的具有一定代表性和通用性的路由协议。另外一种为Distance Routing Effect Algorithm for Mobility(DREAM)［14］，这是一种利用节点位置信息进行路由决策的路由协议，在由于节点运动导致的高动态拓扑的网络中具有比较好的性能。

本文研究主要针对移动WSN中节点运动造成路由协议开销增大、网络寿命缩短情况下，路由协议的性能改进，节点随机运动造成的拓扑变化频繁是造成网络性能下降的主要原因，故仿真实验主要考察在不同节点运动幅度下，参考协议与本文提出协议的性能对比。

从图1中可以看出网络中随着节点随机移动的幅度增加，网络中节点能量耗尽的过程加快，用90%节点能量耗尽表示的网络寿命呈下降趋势，AODV协议在这种情况下应对节点的随机运动所付出的代价要远高于其他两种协议，NMEBRP性能好于DREAM协议，但在节点运动速度较快时，两种协议性能较为接近，说明两种协议对于节点运动情况适应能力的上限近似。

图1 网络中90%节点能量耗尽出现的时间

网络中路由协议开销会消耗一定量的能量，图2反映了三种协议的通信开销大小。由于在节点移动速度较快情况下，AODV协议需要发送大量数据包进行路由维护工作，所以导致其单位数据包传送能耗较高。DREAM协议根据网络中节点移动速度变化，需要更加频繁的更新网络内的节点位置信息，但相对来说通信开销随网络中节点移动速度增大的增长幅度还是可以接受的，但是当网络中节点处于运动速度较慢的情况时，其开销仍然较大。NMEBRP协议能够取得较低的单位数据包功耗的主要原因是，即使节点移动速度较快情况下，节点调整了数据收发的功率，但是网络中节点在满足建立路由的前提下，依然进行本地传送能量优化、路由调整工作，通过本地转发，使得传送数据包的平均能耗得以下降。

图2 网络中成功传送单个数据包的平均能耗

图3中在不同节点运动速度下，AODV协议在节点随机移动速度取值上限为12 m/s时，数据收发受到明显影响。但当节点运动速度再进一步增大时，由于节点随机运动程度剧烈，网络中节点相对位置变化快，导致部分数据包可以凭借节点的运动能力得到成功传送的机会，所以收发数据包的比例又有所上升。而DREAM协议对于节点移动的应对要相对稳定，随着节点运动程度的加剧，性能便相对较缓慢下降，整个过程没有出现明显收发比例下降的阶段。提出的NMEBRP协议在数据收发比例方面取得较好的效果，主要原因是当节点运动速度增加时，单位时间内根据协议算法，离开节点通信范围的现有邻居节点数目会明显减少，而并不根据节点运动情况估计邻居节点数目增加的情况，节点在这种情况下会主动调整数据收发功率，能够增加成功通信的几率。

图3 网络中成功接收的数据包与发送数据包比值

在图4中，NMEBRP的平均hop大，说明在仿真实验中，提出的协议能够按照构想思路，将单跳距离较长的节点间通信，分解为多个节点间较短距离的通信，图4说明NMEBRP协议延长网络寿命的主要途径与协议的初衷一致。图4也反映NMEBRP在网络性能方面的提升是需要付出通信跳数增加，网络延迟增加的代价。

图4 网络中成功传送单个数据包所经过的平均跳数

4 小结

节点随机运动造成移动WSN比静态WSN的网络拓扑变化更加频繁，网络内节点间通信效率随通信路径增长而明显降低；由此导致节点在通信路径修复及重建的过程中消耗了大量能量，从而显著影响了网络寿命。本文针对移动WSN的特点，在分析不同节点间存在优化能量转发节点的限定条件的基础上，确定了节点间本地通信转发的触发范围，进而提出了一种用于移动WSN的基于节点运动判断的路由选择算法NMEBRP，算法中节点依靠通信过程中收集到的临近节点位置信息，进行完全分布式的基于临近节点运动预测的动态路由调整。提出的算法计算复杂度较低，适合应用于节点计算能力受限的各种WSN应用。本文在节点运动速度均值不同的多种实验场景下进行了大量仿真实验，实验结果说明相比参考协议，NMEBRP协议传递单位数据包的平均能耗较低，且网络内用于路由修复及重建的数据包比例低，说明提出的算法将更多节点能量用于传输应用数据包，提高了移动WSN的能量利用效率，有效延长了移动WSN网络寿命。

移动WSN的网络拓扑高动态性特点使得针对其设计的路由层算法能够明显改善网络性能，但从本质上提高此类网络的应用效果，从通信协议角度考虑，还需要从数据链路层至传输层均结合节点运动特性进行跨层优化设计，提出完全适用于移动WSN的跨层通信协议。在本文NMEBRP算法的基础上，作者计划进行深入研究，希望能够提出完全针对移动WSN的跨层通信协议。

［1］Yick J，Mukherjee B，Ghosal D.Wireless Sensor Network Survey［J］.Computer Networks，2008，52(12):2292－2330.

［2］李少春，程良伦.一种自适应的混合型无线传感器网络拓扑控制算法［J］.传感技术学报，2010，23(3):428－433.

［3］Perkins C E，Bhagwat P.Highly Dynamic Destination-Sequenced Distance-Vector Routing(DSDV)for Mobile Computers［J］.Computer Communications Review，1994，24(4):234－234.

［4］Chen J，Zhou H，Lee Y Z，et al.AODV-DFR:Improving Ad Hoc Routing Scalability to Mobility and Load［C］//Vancouver，BC，Canada:Institute of Electrical and Electronics Engineers Computer Society，2007.550－553.

［5］Guo S，Yang O.Effects of Backup Routes and Cache Timeout Mechanism on ReliableSourceRoutingin MobileAd-Hoc Networks［C］//Hong Kong，China:Institute of Electrical and Electronics Engineers Computer Society，2005.361－365.

［6］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Maui，USA:IEEE，2000.223－231.

［7］张震，闫连山，潘炜，等.基于LEACH和PEGASIS的簇头成链可靠路由协议研究［J］.传感技术学报，2010，23(8):1173－1178.

［8］Guangyu P，Gerla M，Tsu-Wei C.Fisheye State Routing:A Routing Scheme for Ad Hoc Wireless Networks［C］//New Orleans，LA，US.ICC 2000:70－74.

［9］Al-Fares M S，Sun Z L，Cruickshank H.A Hierarchical Routing Protocol for Survivability in Wireless Sensor Network(WSN)［C］//Hong Kong，China.Imecs 2009.2009:262－268.

［10］Ok C S，Lee S，Mitra P，et al.Distributed Energy Balanced Routing for Wireless Sensor Networks［J］.Computers ＆ Industrial Engineering，2009，57(1):125－135.

［11］Ko Y B，Vaidya N H.GeoTORA:A Protocol for Geocasting in Mobile Ad Hoc Networks［C］//Osaka，Jpn:IEEE，2000:240－250.

［12］Rappaport T S.Wireless Communications:Principles and Practice［M］.Upper Saddle River:Prentice Hall PTR，2002.

［13］Charles E P.Ad-Hoc On-Demand Distance Vector Routing［C］//New Orleans LA，US.Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications.1999:90－90.

［14］Camp T，Boleng J，Williams B，et al.Performance Comparison of Two Location Based Routing Protocols for Ad Hoc Networks［C］//New York，NY，United States:Institute of Electrical and Electronics Engineers Inc.，2002:1678－1687.