DTRP基于动态树的无线传感器网络路由协议.doc

第11A期蔡新文等：DTRP：基于动态树的无线传感器网络路由协议91DTRP：基于动态树的无线传感器网络路由协议蔡新文，裴庆祺，李凤华（西安电子科技大学 计算机网络与信息安全教育部重点实验室，陕西 西安 710071）摘 要：为了延长网络的使用寿命，更有效的利用传感器节点的能量，在分簇路由（如LEACH）的基础上，提出了一种节省能量的基于动态树的无线传感器网络路由协议DTRP。仿真结果显示DTRP与传统的LEACH相比，可以显著地节约能量，平衡节点能量消耗。关键词：无线传感器网络；分簇协议；动态树路由协议；多跳中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2007)11A-0087-06DTRP: based on dynamic tree routing protocol in wireless sensor networksCAI Xin-wen, PEI Qing-qi, LI Feng-hua(Key Lab. of Computer Networks and Information Security, Ministry of Edu., Xian 710071, China)Abstract: To prolong the network life and use the energy of sensor nodes more effective, A new Dynamic Tree Routing Protocol was proposed based on the clustering protocol such as LEACH, which can have significant impact on the overall energy depletion of the network. Simulations show that DTRP can achieve a considerable reduction in energy dissipation compared with conventional LEACH.Key words: wireless sensor network; cluster protocol; dynamic tree routing protocol; multi-hop1 引言随着传感器技术、嵌入式计算技术、低功耗无线通信技术的飞速发展，具备感应、无线通信以及信息处理的能力的微型无线传感器也开始出现。这些廉价的、低功率的传感器组织成无线网络，能够协作地监测、感应其网络覆盖区域内的多种环境信息(如温度，湿度等)并传送到远处的基站进行处理.无线传感器网络(wireless sensor network)能够在恶劣的环境条件下获取大量详实而可靠的信息，可以广泛应用于国防军事、工业控制、环境监测、交通管理等领域。收稿日期：2007-09-25基金项目：陕西省自然科学基础研究计划基金资助项目（2005F28）；西安市科技攻关计划基金资助项目（GG06017）Foundation Items: The Natural Science Foundation Research Plan of Shanxi Province(2005F28); Xian City Pioneer Program of Science and Technology (GG06017)与传统的无线网络不同，无线传感器网络中的节点带宽、内存等资源更为缺乏，尤其是其有限的能量直接影响传感器网络的生命周期以及网络的信息质量。由于传感器节点的能量通常无法得到补充，节点上的通信协议应能够有效地利用节点有效的能量，以延长网络的生命周期。目前已有大量的研究工作从不同的角度来力求延长传感器网络的寿命16。本文提出了一种完全分布的、高效节能的数据通信协议DTRP，其特点是节点以聚类的方式组织节点，聚类覆盖的区域大小是限制在一定范围内，簇内以簇头节点为根节点组成树(tree)，子节点只与距离很近的父节点通信，子节点产生的数据动态寻找路径，多跳传送至簇头节点，簇头节点直接与基站通信。模拟实验显示DTRP具有良好的性能。2 背景 2.1 相关工作对于传感器网络中节能的数据通信协议的研究已有不少。最简单的数据通信协议是直接通信(direct transmission)，即节点收集数据后直接与基站通信。显然，当基站距离很远时，节点的通信代价太大，将很快死亡。为解决这个问题，一些以节约能量为目的算法相继被提出来。LEACH7是MIT的Wendi等人为无线传感器网络设计的一种分布式自组织的协议，其核心思想是减少与基站直接通信的节点数量来达到节能的目的。LEACH协议按轮(round)运行，每轮分为设置(setup)和稳定(steady)2个阶段。在设置阶段，首先随机选出若干个节点作为簇头，簇头节点向所有的节点广播消息，普通节点根据接收消息的强弱加入最近的簇头。在稳定阶段中，簇中的成员节点把收集到的数据传送给簇头，簇头将所有收集到的数据进行数据聚合后发送到基站。由于LEACH协议在每一轮中簇头都要重新随机选取，这种方式保证了能量损耗被均匀地分布到所有的节点上。LEACH协议与DIRECT协议相比，可以使传感器网络寿命(第一个节点死亡)得到8倍左右的提高。Lindsey和Raghavendra在LEACH的基础上提出了PEGASIS协议。其思想是进一步减少直接与基站通信的节点。PEGASIS把网络中所有节点用贪婪算法构成一个边长之和接近最小的链，指定某个节点作为与基站通信的节点。收集数据时，任意节点从位于链上的一个相接节点接收数据并把接收到的数据和本节点的数据聚合，然后把聚合后的数据发送到链上的另一相接节点，如此直到与基站通信的节点。在通信的过程中，所有的节点都接收并发送数据一次，同时各节点轮换充当与基站通信的节点，能量进一步均匀消耗在所有节点中。与LEACH协议相比，PEGASIS协议与基站直接通信的节点更少而且数据聚合能力更强，从而显著减少了每一轮的能量消耗，特别是在基站远离监测区域的情况下，这种效果更加明显。根据模拟实验表明，PEGASIS相对于LEACH其传感器网络寿命提高了13倍。PEGASIS不足的之处在于节点需要维护全局的位置信息，以及数据的延迟较大。网络规模较大时，建立链表和维护代价相当大。2.2 无线能量模式近年来，在低能量无线通信方面进行了大量的研究工作。本文与文献8使用了相同的无线通信模型。该无线通信模型给出了一个阈值d0(d0是常数，数值取决于使用环境)，当发送节点与接收节点的距离小于d0时，发送方发送数据的能量损耗与距离的平方成正比，否则与距离的4次方成正比。上述的2种能量衰减模型分别称为自由空间模型(free space)和多路衰减模型(multipath fading)。因此，根据发送节点和接收节点之间的距离，发送节点可以使用不同的能耗模型计算发送数据所需要的能量。例如，节点a向距离d外的另一节点b发送k字节的数据，可以使用下面的式(1)计算其能量消耗： (1)而b接收a发送的消息，其无线接收装备产生的能耗为(2)在式(2)中，表示无线收发电路所消耗的能量。表示放大器消耗的能量，其大小取决于发送节点与接收节点间的距离以及可接受的位错误率。式 (1)为发射k比特数据耗损的能量，由发射功耗和功率放大耗损两部分组成，式 (2)为接收k比特数据的能量耗损。此外，大部分协议和算法都采用了数据聚合技术来减少发送和接收的数据量，从而达到节省能量的目的。DTRP协议同样采用数据聚合技术来减少能量损耗。与PEGASIS协议一致，DTRP协议假设数据聚合的能力为NK=K，其中N表示传感器网络中所有节点的数量，K表示数据包长度。此外，本文假设无线通信是对称的，即从节点a、b之间的链路是双向的。3 问题描述设计能量有效的路由协议的原则是使每轮数据的收集的总能耗最小，同时保证能量的损耗均匀分布在所有节点上。基于簇的路由协议能有利用能量，延长网络的生命周期。在传感器网络中基于簇的通信协议应该满足以下几个目标：1) 网络中节点之间的通信，应该遵循自由空间模型，避免远距离通信传输的高能量衰减，因此每个节点的通信半径应该限制在一定的范围内。LEACH协议中，成为簇头的节点在全网范围内广播，其功率衰减遵循多路径衰减模型，而所有其他节点接收此信息也将损耗一定的能量，事实上对于大多数未成为此聚簇成员而言，接收此消息的能量损耗是不必要的。同时这些随机选取的簇头节点可能在网络的边缘，势必增加通信的能量消耗。在网络覆盖区域很大的情况下，成员与簇头间的通信急剧上升，能量耗损将相当可观。2) 协议是完全分布的，节点完全根据本地信息决定自身的状态，无需知道其他节点的位置，具有良好的伸缩性。在文献1中，Lindsey 和Raghavendra注意到了在一定距离范围以内，节点收发电路所消耗的能量大于该节点放大电路所消耗的能量。因此提出了PEGASIS协议，该协议需要知道所有节点的全局信息，然后用贪婪算法构造一个边长之和接近最小的链，链上的每条边只接收(发送)数据一次。与LEACH相比，PEGASIS协议与基站直接通信的节点更少而且数据聚合能力更强，从而减少了能量的消耗。3) 簇头的选举应该考虑到节点剩余能量的状况。与LEACH协议不同，本文推出的算法假定簇头在每轮中的能量开销一致，因此需要算法保证能量开销被均匀地分布到每一个节点上，避免个别节点过早死亡。在后面的DPTR仿真分析中，我们把簇头选举分为考虑节点剩余能量和不考虑节点剩余能量两种情况来比较分析。本文在已有研究的基础上提出一种动态树型路由协议，簇内以簇头为根节点组成树，子节点只与距离很近的父节点通信，子节点产生的数据动态寻找路径，多跳传送至首领，簇头直接与基站通信。这种路由协议的特点是：融合了单路径路由和多路径路由的优点，子节点动态路由到首领，可以灵活的实现路径修复，提高了网络的容错性，同时减少额外能量消耗；节点大部分的通信都是短距离(r)传输，节省能量；网络中多个簇可以同时传送数据，降低了时间延迟；局部通信避免了大量节点同时发送可能导致的冲突。 4 DTRP协议描述DTRP协议按轮运行，每轮分为、2个阶段。在中，通过竞争选举出簇头节点，簇头节点通过广播set-up包，建立一颗以簇头节点为根节点的路由树；为数据传输阶段，节点检测到数据后动态地选择路径把数据发送到自己的父节点，父节点再发送到自己的父节点，最终到达sink节点。4.1 路由树生成算法簇头的选举与LEACH算法一样，每个节点都维护一个闸门T(n)，在考虑节点剩余能量时，把节点的剩余能量状况也参与T(n)的计算。簇头产生之后，成为簇头的节点发一个set-up广播，其中包括了簇头节点ID (CH_ID)，接收节点与首领的相对距离DtCH=0(Distance to CH)。每当一个节点接收到set-up广播，首先确认该set-up是否是网络重组的新广播，若是重组，则无论广播帧中DtCH是何值，一律用广播帧中的DtCH值加1更新自己的DtCH。并根据set-up中的信息(CH_ID, sender_ID)置本节点的根节点(root _ID)和父节点(father_ID)。然后判断是否大于跳数上限(TTL)，若小于TTL则将广播帧DtCH加1并转发该广播帧。如果不久之后，节点又收到一广播帧，则先检查是否已经收到同一簇头发出的广播帧。若不是，丢弃该帧；反之则判断帧中DtCH+1是否小于本节点DtCH。若等于，将源节点添加到候选父节点列表中；若小于，重置本节点DtCH、根节点和父节点，判断是否超过TTL以决定DtCH是否加1转发。网络初始化后，簇内关系如图1所示， 圆圈内的数字是该节点的DtCH，簇头的DtCH=0，所有节点的广播半径为r，DtCH=1的节点是首领的子节点，DtCH=2是DtCH=1的子节点，以此类推。虚线表示2是3的候选父节点。簇内的节点组成了以簇头为根节点的树型结构。图1 节点之间的关系显然，初始化过程的算法复杂度不高，而且在初始阶段发送和接收的都是小数据包，能量消耗与数据传送阶段相比可与忽略不计。在下面的数学分析中只考虑网络在数据传送时的消耗。4.2 数据传输阶段通信按CSMA/CA方式进行，分为上行和下行两种：下行指簇头节点发广播到各成员节点，该广播包括了各种指令，如重设采样频率，更改采集参数，发查询命令等。而上行指的是各节点将感知数据传到各簇头节点。在上行过程，子节点如想发送或中转数据，则按一种均衡策略，动态选择发送数据到候选父节点之一，即按一种“动态路径”传送信息。“动态路径”的概念：动态地选择路由，不遵循固定路径传输，有利于平衡各节点耗能，提高网络可靠性。比如，某子节点发现它的父节点失效，可选择候选父节点代为转发。如果所有候选父节点都没有回应，即相邻节点没有它的父节点，这可能是网络拓扑结构变化。则该节点将自身DtCH加1（即在树的结构中下降一级），并将root_ID域置为无效值，要求所有DtCH较小的节点转发，而不管是不是在同一簇内。与此同时其子节点更新父节点列表。重复以上过程，直至DtCH=TTL时，宣布发送失败，等待下一轮开始。这种自适应算法可以在网络生命后期，一部分节点相继失效，或某些节点发生移动时继续保持网络连通性，提高了网络顽健性。5 性能分析5.1 仿真与分析用ns2作为实验平台，模拟实验中各项参数见表1，在模拟实验中，网络寿命包含3种不同的定义，分别为：第1个节点死亡，一半节点死亡和最后一个节点死亡，此外，在模拟DTRP协议时，设各节点的感知半径为12m，且当节点能量小于0.002J时，认为该节点死亡。为了对DIRECT,LEACH,PEGASIS以及DTRP这四种协议进行全面的比较，在实验中分别模拟了监测区域大小变化和基站的位置变化对协议性能的影响，结果及分析见第5.2节。其中DTRP协议分为DTRP-1和DTRP-2(在簇头选举时考虑节点的剩余能量)2种协议。表1实验参数参数取值网络覆盖区域A(100,100)汇聚节点sink的位置(50,175),(50,200),(50,215),(50,230),(50,245),(50,260),(50,275),(50,300),(50,400)节点数量N100传感器节点初始能量2J50nJ/bit0.0013pJ/(bit*m4)10pJ/(bit*m2)75m数据包的大小k4000 bits节点的通信半径r30m簇内最大跳数TTL55.2 实验结果及分析图2是基站位置为(50,245)，监测区域A大小为100m100m，节点数量为100是节点死亡数量与网络工作时间(轮数)之间的关系图。可以看到，图2中DTRP协议曲线几乎是一条平行于X轴的直线。由于DPTR协议使得网络能量消耗被均匀分担到每个节点上。因此第1节点和最后一个节点的死亡时间非常接近，一般在40轮以内。从图2中可以看出，与LEACH和PEGASIS相比，DTRP协议使得网络的生命分别提高了305%和47%(第1个节点死亡)。需要注意的是，由于节点的能量消耗比较均匀，因此使用节点的剩余能量来进行簇头选举方法的DTRP-2协议不能显著地提高网络寿命，其性能略优于DTRP-1。图2 节点死亡时间图图3图5分别描述了上述3种定义的网络寿命与基站位置的关系。由图3可以看出，当网络寿命定义为第1个节点死亡时，DTRP协议随着监测的区域A与基站距离的增加其网络寿命减少得最慢，实验表明，当基站位置从(50,175)(50,300)时，网络寿命从903轮降到736轮，减小的幅度不到18%，远优于PEGASIS和LEACH协议。同时还可以看到，DTRP协议在3幅图中的曲线变化最小，这说明了运行DTRP协议的网络，其3种定义的网络寿命在时间上相差不大。图3 基站位置与网络寿命（第1个节点死亡）图4 基站位置与网络寿命（一半节点死亡）图5 基站位置与网络寿命（最后一个节点死亡）从图25中可以看出，DTRP-1和DTRP-2的性能相差总是较小，这是因为节点的通信半径都设定为r，在均匀分布的网络中，落在某个节点的通信范围的节点的个数相同，因此每轮节点能量消耗相差不大。节点的剩余能量也就比较相近，下一轮选举簇头的概率也就近似相等。对于按轮运行的协议，每轮中所有活动节点收集环境数据的次数是一致的(在模拟中，我们设节点每轮数据收集次数为5)。6 结束语本文提出了一种分布式的、高效节能的基于动态树的路由协议DTRP，各节点独立的运行DTRP协议，该协议的思想是，把每个节点的通信半径都预先设定为某一个值(r)，通过簇头选举产生簇头节点之后，簇头节点通过广播set-up广播包来建立一颗根节点为簇头节点的动态路由树，并利用ns2工具进行了仿真分析。与前文提到的一些文献相比，动态树有以下一些优点：1) 本文提出了“动态路径”的概念，子节点的数据不沿着固定路线向首领传送，在其父节点失效时，可选择候选父节点来转发数据，使网络具有很强的顽健性。2) 每个节点只记录它的父节点和候选父节点，而不用记录完整的路由信息，可节省内存空间。3) 在无线传感网络中，MAC协议根据网络结构的不同可以有很大区别，动态树路由协议相对其他路由协议只需要更简单的MAC层协议就可以实现。非常适合无线传感器网络节点小而简单的特色。但本文并未考虑簇内最大跳数对性能的影响，也未考虑传送半径r不同时对网络的影响，这些都将是我们进一步的工作。参考文献：1YE W, HEIDENMANN J, ESTRIN D. An energy-efficient MAC protocol for wireless sensor networkA. Proc of the IEEE INFOCOMC. 2002. 2SOHRABI K, GAO J, AILAWADHI V, et al. Protocols for self-organization of a wireless sensor networkJ. IEEE Personal Comm Mag, 2002, 7(5):16-27.3KAWADIA V, KUMAR P R. Power control and clustering in ad hoc networksA. Proc of the IEEE INFOCOMC. 2003. 459-460.4杜军朝，刘惠，陈平. 无线传感器网络中邻居发现及链路通信质量预测技术J. 西安电子科技大学学报，2007,34(2):181-186.DU J Z, LIU H, CGEN P. Study of neighborhood discovery and link quality estimation in WSNsJ. Journal of Xidian University, 2007, 34(