无线传感器网络中分布式多跳路由算法研究*

尚凤军，任东海

(重庆邮电大学计算机科学与技术学院，重庆 400065)

在当今信息技术飞速发展的时代，互联网为人们提供了快捷的通信平台，极大地方便了人们的信息交流，无线传感器网络技术的产生将彻底改变人类自古以来仅仅靠自身的触觉、视觉、嗅觉来感知信息的现状，极大的提高人类获取信息的准确性和灵敏度［1］。作为信息时代的一项变革性的技术，无线传感器网络可以使人们在任何时间、任何地点和任何环境条件下获取大量详实、可靠的信息，真正实现“无处不在的计算”理念。无线传感器网络是计算机科学技术的一个新的研究领域，具有十分广阔的应用前景，它的出现引起了全世界范围的广泛关注［2］。美国《商业周刊》将无线传感器网络列为21世纪高技术领域中的四大支柱型产业之一；《技术评论》杂志也将其列为未来改变世界的10大新兴技术之首。可以预言，无线传感器网络的发展和广泛应用，将对人们的社会生活和产业变革带来极大的影响和产生巨大的推动力。

1 基于退避机制的成簇算法(CHTD)

目前，已经存在多种关于无线传感器网络分簇算法的研究。在文献［3－4］都提到使用时间延迟机制来选择簇头，通过给能量较大的节点设置较小的等待时间，从而使剩余能量较多的节点有较大的概率成为簇头。然而，文献［3］并未对每轮产生的簇头数目进行研究，若产生簇头数目不稳定，簇头能量消耗过大，进而影响网络整体的性能。文献［4］提出的TB-LEACH虽然产生了固定的簇头数目，但簇头的位置分布并不均匀，这样每个簇头管理的成员节点个数不均匀，导致簇与簇之间能量消耗不均匀，网络生存时间就得不到有效延长，而且没有考虑当网络运行初期节点能量相同的情况下竞选簇头发生的冲突问题。在文献［5］中，作者研究了单跳和多跳成簇模型的花费以及分组的聚合问题。文献［6］对LEACH的簇头选择方法进行了改进，数据传输采用了单跳和多跳相结合的方法，提高了系统的能量效率。文献［7］引入了定时器方法确定簇头，保证了能量高的节点优先成为簇头，提高了网络的能量效率。文献［8］提出了一个基于能量和到基站距离的分簇算法，并在簇首的数据发送中引入了改进的多跳路由算法，提高了基站接收到的数据量，延长了整个网络的寿命。文献［9］提出了一种非均匀成簇方法，但数据传输主要考虑单跳方式。文献［10］提出了一种分环多跳分簇路由算法，该算法采用分环的方式实现簇头间的多跳通信，通过在不同环内构建大小不同的簇解决传感器网络中存在的“热点”问题，延长网络的生命周期。文献［11］中综合考虑网络中节点的剩余能量和节点问传输数据的能耗，基于最短路径树算法，通过构造两种不同的权值函数，提出了“比例权值路由算法”，延长了网络生存时间。但当转发距离较近时，中间节点的电路消耗造成的总体能量消耗变大和簇头节点在选择下一跳路由时，簇头之间交换信息的开销问题，同时，基于簇的多跳路由算法中簇头之间和簇与簇之间的能量平衡问题也需要进一步的改进。另外随着传感器网络应用的拓展，QoS路由算法也成为当前研究的热点之一［12］。

为了解决以上问题，本文改进了节点的时间延迟机制模型并由此得到延迟时间，使得剩余能量较多的节点有较小的延迟时间，考虑到网络内节点的能量消耗和负载均衡，引入了最优簇半径和最佳簇头数目作用于簇头的选择过程当中，在簇数据传输过程中引入多跳机制，并着重考虑了中间转发节点的选择。实验证明，本算法使得选出的簇头更适合担当数据转发任务，网络能量消耗更小，网络生命周期进一步延长。

1.1 无线传输能量模型

由于网络中路由算法设计首要考虑的因素是能量问题，所以在无线传感器网络中，路由算法的设计与信道能量损耗模型息息相关。我们采用与文献［13］相同的无线通信能量消耗模型。节点发射L比特的数据到距离为d的位置，消耗的能量由发射电路损耗和功率放大损耗两部分组成，即

其中Eelec表示发射电路损耗的能量。ξfs、ξmp分别为两种模型中功率放大所需的能量。d0为一个距离常数:

距离大于d0时路径消耗会相当大，因此一般要求传输距离不大于d0，接收k比特的消息，接收机消耗的能量为:

簇头节点进行本地处理和数据融合的时候，每处理1比特的数据需要的能量损耗EDA。

1.2 CHTD簇头产生

CHTD算法的执行过程也划分为“轮”，每一轮分为设置阶段和稳定工作阶段，在设置阶段所有节点组织成簇，稳定工作阶段簇头把监测的数据融合后传递到基站。

CHTD算法在每一轮的开始，所有节点并不是立刻就生成随机数，并根据阀值来申请簇头，而是要先根据式(4)生成一个定时器，节点i在Ttimer(i)秒后超时。

当某一个节点延迟时间到达时，它将赢得竞争簇头的权利，拥有竞争权的节点通过自身的簇头信息集合查看网络内当前簇头个数，若已经达到最佳值，节点将不再参与簇头竞争，并且通过信号接收强度判断节点和集合中每个簇头节点之间的距离不小于最优簇半径，保证每轮的簇头个数都是最佳值并且均匀分布在监测的区域中。

1.3 CHTD簇头数量

假设传感器节点随机分布在一个区域内，位于r1区域的簇头的个数为h1，传感器节点的数量为N1，则每个簇首的能量消耗由接收所有簇成员的信息、融合这些数据、并把融合后的信息传送给Sink节点3个方面组成［13］。我们假设基站离第1区域比较近，同样采用自由空间模型进行传输，这样，在一帧中簇首节点消耗的能量为:

l为每个数据的信息位数，EDA为数据融合的消耗。假设网络中的簇头节点都按照多跳的方式进行数据的发送，并且每跳的传输距离假定为D。

簇内成员节点离簇首的距离假设它不超过自由空间模型的临界值，这样，一个非簇首节点的能量消耗为:

如果整个簇内节点的密度是均匀的，那么ρ=N1/()，那么，则

则发送一帧中整个簇的能量消耗为:

那么在R1区域的一帧的总能量消耗为:

忽略电路消耗和数据融合消耗，对Etotal求倒，让其等于零，得到h1最优簇头数为:

这个最优值和上面分区域大小的计算是在做了很多假设的情况下得到的，只能作为参考，实际的应用中需要具体考虑和设定。

2 CHTD簇数据传输

为了减小远距离的通信能耗，在CHTD算法的基础上给出了改进的CHTD多跳路由算法(CHTD-M)，多跳方式是在簇头间生成一种基于距离能量代价的路由树，簇头选择下一跳节点时，综合考虑了两节点间链路能耗、接收节点的剩余能量水平和距离基站的位置，通过局部信息动态选择下一跳，并且通过引入最短有效转发距离，合理有效的选择多跳，实验结果表明改进的CHTD-M进一步优化了网络中簇头节点的能量消耗，显著地延长了网络的生命周期。CHTD-M的下一跳路由节点在紧邻的区域内，簇头节点和它的下一跳路由节点距离不超过自己的通信范围，很容易实现。

2.1 最优转发跳数

在无线传感器网络中采用多跳的路由机制，虽然能够降低网络数据通信的能量开销，但当节点之间的距离较近时，却增加了作为路由中间节点的电路能量消耗，有时采用多跳的路由方式所消耗的能量要大于直接传送的方式，进而在一定的范围内会增加网络整体的能量消耗。因此，在簇数据传输时应该合理的选择多跳。假设有N个传感器节点随机分布在半径为r的一个区域内。区域内的传感器节点按照距离基站的远近划分为不同的区域，分别为r1，r2，r3，r4，…，rn，如图 1。

图1 无线传感器网络多跳模型

在这个区域中有h个簇头，平均分布于整个区域中，位于rn区域的簇头节点和基站的通信需要rn－1区域的簇头节点进行转发，并且每次通信的距离都不超过自由衰减模型的范围，为了便于研究，假设每个区域的簇头节点位于该区域的中部，并且每个区域的环宽度相同都为r，即r1区域的簇头位于r/2，r2区域的簇头位于3r/2，r2区域的簇头节点向基站发送数据时，需要r1区域的簇头节点转发数据，r3区域的簇头向基站发送数据需要r2区域的簇头节点进行转发，以此类推，则当位于ri区域的簇头向基站发送k比特数据时，网络中的单个簇头节点发送数据的能耗为:

其中β是数据传输经过的跳数，则网络的总体能量消耗为:

节省能量的跳数可从下面的计算得出:

由(7)可得:

由(8)可知，当网络中的节点距离基站的距离小于d0时，采用直接传输的方式可以节省网络能量，当网络中的节点距离基站的距离大于d0时，采用多跳的传输方式更能够节约网络的能量，我们把这个值定义为节点的最短有效转发距离(Restriction_distance)。从而可知，一个距离基站距离为d的传感器簇头节点i，它的节能转发跳数βopt=「d/d0⏋。

在实际应用当中，选择下一跳路由的转发节点时，应当综合考虑整个网络能量平衡的因素。

2.2 簇间路由树的生成

在网络部署完毕后，基站需要用一个给定的发送功率向网络内广播一个信号Sink_ADV，节点以此信号强度计算到基站的近似距离。获得这个距离不但有助于节点在向基站传输数据时选择合适的发送功率来节约能量消耗，而且它还是构造簇间路由树的必需信息之一。

在有些路由算法中，中继节点对接收到的数据进行数据融合，然后再断续发送。实际上，不同簇之间的数据相关性很小［14］，因此在本文中，中继簇头节点不再对来自其它簇头的数据进一步融合，只是简单的转发给下一跳。

其中，eij表示节点i和j直接通信的能量消耗，RSSj指节点j接收到Sink_ADV的信号强度，RSSmax是指基站广播Sink_ADV时的信号强度，D()表示距离估算函数。

综合考虑能量平衡的因素，本文节点i选择节点j作为父节点的策略是选择代价最小的DEC(i，j)，即:

若节点i的邻居信息表为空，说明此簇头周围没有其它的簇头存在，这种情况会出现在网络运行到后期，大部分节点已经死亡的情况下，此时，簇头将数据直接传输给基站。通过式(11)可以看出，DEC(i，j)充分考虑了两节点间通信的能量消耗和邻居节点的剩余能量以及到基站的距离状况，通过对这3个因素的综合考虑，选择最小的DEC(i，j)，使得在发送能耗较小的情况下，距离基站较近并且剩余能量充足的节点优先成为父节点。

按照以上策略确定路由方式之后，簇头生成一棵以基站为根的树，数据沿着基站的方向传输。

2.3 CHTD-M 的分析

通过分析整个算法，CHTD-M算法具有以下两个特性:(1)算法是完全分布式的，节点完全依赖本地信息决定自身的状态，无需知道其它节点的位置，具有良好的伸缩性。(2)算法的消息复杂度为O(N)。在整个网络中，有N个节点参与簇头竞选，最终共选出k个簇头，每个簇头广播一条CH_ADV消息宣布其竞选成功，则它们共广播k条CH_ADV消息，而N－k个簇成员广播N－k条JOIN_REQ消息。因此，网络中总的消息开销为k+N－k=N，所以消息复杂度为O(N)。该特点说明算法的消息开销较小，能量高效。

我们引入阈值Restriction_distance，若簇头到基站距离小于Restriction_distance，则直接与基站进等通信。若簇头到基站距离大于Restriction_distance时，簇头i的路由选择方法如下所示。

定义1通信能量消耗 任何两个可直接通信的节点i、j，通信一次发送k比特数据的能量消耗定义为两点之间距离dij的函数eij(k，dij)，公式如下:

其中α为功耗指数，与传输距离有关。

定义2距离能量代价 若某个簇的当前簇头为i，j是i的邻居信息表中的一个簇头节点，则节点i到节点j的距离能量代价 DEC(Distance Energy Cost)定义如下:

3 仿真分析

本文为了研究在不同的范围内 LEACH、TBLEACH、CHTD和CHTD-M的性能的差异，分别在两个场景中进行了模拟，具体见表1，通过仿真网络的生命周期、接收数据包、能量消耗和负载均衡来观察改进的CHTD-M的网络性能。

表1 仿真相关参数

3.1 生命周期

图2是100 m×100 m场景下的 LEACH、TBLEACH、CHTD和CHTD-M算法中无线传感器网络生命周期的对比图，在场景1中CHTD-M的第一个节点死亡的时间(FND)是LEACH的1.4倍，一半节点死亡(HND)的时间是LEACH的1.2倍。这表明CHTD-M算法使能量的损耗更加均匀的分布到所有节点中，避免了单个节点因能量损耗过大而过早死亡。与TB-LEACH和CHTD相比，CHTD-M算法的FND和HND时间几乎同时提高了1.1倍左右，这是因为CHTD-M采用了节能跳数，降低了网络的整体能量消耗。

图2 100 m×100 m死亡节点和轮的关系

图3是200 m×200 m场景下的网络生命周期，在场景2中CHTD-M的优势进一步得到体现，其FND、HND 时间分别是 LEACH 的3.2 倍、1.3 倍，与TB-LEACH和CHTD相比，CHTD-M的FND时间分别提高了1.9倍和1.3倍，HND时间也几乎同时提高了1.2倍，这是因为在大场景环境下，其它3种算法的簇头和基站之间的通信距离加大，簇头单次的通信能量损耗也随之加大，而CHTD-M中簇头和基站之间的通信选择通信能耗小、离基站较近且能量充裕的簇头转发，因此单个簇头单轮通信能量损耗不会随区域的增大而大幅增加，并且单轮的簇头和基站通信的过程中，簇头之间趋于能量平衡。另外，我们知道从FND到HND的时间跨度能够反应网络中节点的能量均衡状况，跨度越小表明网络的能量使用越高效。CHTD-M不仅显著地延长了网络的生命周期，而且时间跨度也较小，所以在前期，CHTDM算法的网络中的存活节点和网络覆盖面积远远大于其它3种算法，在某个时间点，CHTD-M网络中的节点开始迅速死亡，所以后期的存活节点数量迅速降低，无线传感器网络中死亡节点的数目占有一定比例的时候我们就可以认为网络的死亡，因此，这个不影响CHTD-M在延长无线传感器网络生命周期中的优越表现。

图3 200 m×200 m死亡节点和轮的关系

通过上述分析，我们可知，CHTD-M中的多跳策略可以节省网络的通信能量消耗，相比LEACH更能够均衡网络中不同位置的簇头节点的能量消耗，减少簇头节点的通信能量负载，相比TB-LEACH和 CHTD，CHTD-M中的节能跳数策略能够减少网络中数据转发的次数，能够较小网络的额外开销，防止网络中的电路消耗过大，减弱“热点问题”对网络性能的影响。

3.2 能量消耗

图4是100 m×100 m环境下LEACH、TB-LEACH、CHTD和CHTD-M算法中网络能量消耗和时间的关系，从图中可以看出，和CHTD、TB-LEACH和LEACH相比，CHTD-M能够节省网络总体能量消耗，经过一段时间后，LEACH的网络能耗增长速度缓慢，在某一时刻，CHTD-M的网络总能量消耗大于LEACH，这是因为随着时间的推移，LEACH中的大部分节点已经死亡，CHTD-M的覆盖面积远远大于LEACH，因此网络数据的采集量大于它们。

图4 100 m×100 m环境下LEACH、TB-LEACH、CHTD、CHTD-M能量的消耗

当网络范围变大时，CHTD-M的节能效果更加明显，图5是在200 m×200 m的环境下，CHTD-M和LEACH、TB-LEACH以及CHTD的能量消耗图，从图中可以看出，和TB-LEACH、CHTD相比，CHTD-M在时间为300轮时能够节约LEACH将近一半的能量，同样随着时间的推移，CHTD-M的覆盖面积远远大于LEACH，在某一时刻，CHTD-M的总能量消耗会大于LEACH。

图5 200 m×200 m环境下LEACH、TB-LEACH、CHTD、CHTD-M能量的消耗

从图4和5可知，CHTD-M采用多跳的路由策略节省了网络中通信的能量消耗，和 LEACH、TBLEACH相比，它具有很明显的节能优势，而CHTD随着网络范围的逐渐变大达不到CHTD-M的良好性能。

3.3 负载均衡

无线传感器网络性能评价的重要标准之一就是网络负载平衡，为了便于研究，本文将传感器节点按照它与基站之间的距离等分为两份，为了便于描述，我们假设第1份覆盖的范围为第1区域(距离基站较近的一半节点)，第2份覆盖的范围为第2区域(距离基站较远的一半节点)，统计不同算法中不同区域的节点能量消耗随时间的变化状况。

图6为100 m×100 m环境下CHTD-M各区域能量的消耗和时间的关系，很明显，在该场景下，CHTD-M中的两个区域的能量消耗并没有明显的差别，其中因为靠近基站的节点需要转发来自离基站较远节点的数据，因此能量消耗稍微多于远离基站的区域，但是这个在可以容忍的范围之内，通过图6可以看出，CHTD-M均衡了网络中不同位置的节点的能量负载，延长了网络寿命。

图6 100 m×100 m环境下CHTD-M各区能量的消耗

图7为200 m×200 m环境下CHTD-M两个区域的能量消耗，和100×100环境下相比，两个区域的能量消耗差别稍大，但是，和节点数量增加量相比，两个区域中单个节点的能量负载基本没有太大变化，在网络范围变大的情况下，CHTD-M依然能够使网络中的节点负载趋于平衡，因此，和LEACH以及类似的单跳成簇算法相比，网络范围越大CHTDM的优势越明显。

图7 200 m×200 m环境下CHTD-M各区能量的消耗

综合以上所述，通过对改进算法进行仿真分析，我们得到簇间多跳算法CHTD-M能够延长网络的生命周期，增加网络采集的数据包的数量，节省网络能量消耗，均衡网络的能量负载，完善了CHTD成簇算法。

4 总结

本文在对无线传感器网络路由算法深入研究的基础上，总结了目前无线传感器网络路由算法研究的主要思路，分析了基于簇的无线传感器网络路由算法中存在的问题，设计出了一种完全分布式的、能量有效的无线传感器网络分簇算法。主要进行了如下的研究:

(1)基于无线传感器网络分簇算法研究分析的基础上，给出了一种基于时间延迟机制的无线传感器网络分簇算法CHTD。该算法建立了节点的时间延迟机制模型并由此得到延迟时间，使得剩余能量较多的节点有较小的延迟时间，从而能够在每一轮中被优先选为簇头，达到均衡簇头能量消耗的目的。此外，该算法还考虑了每轮的簇头节点个数以及位置分布问题，通过维持每个节点的簇首信息集合使得每轮产生的簇头数目稳定且位置均匀分布。并通过仿真验证了CHTD分簇算法比LEACH和目前已有的基于定时器的分簇算法TB-LEACH对网络性能有明显改善。

(2)针对CHTD分簇完成之后的簇数据传输阶段进行算法改进，给出CHTD-M簇间多跳路由算法。该算法将网络中均匀分布的簇头构造成一棵路由树，通过多跳传输的方式减少直接与基站通信的簇头节点数量，从而更进一步的降低能量开销。同时，该算法还限制了多跳路由的最短转发距离，降低了中间节点的电路开销，减少了多跳的数据转发次数，节省了网络的能量消耗，弱化了网络中的“热点问题”。最后对整体算法进行仿真，实验结果表明，CHTD-M把节约网络能量和保持网络负载平衡结合起来，显著地延长了网络的生命周期。

［1］Akkaya K，Younis M.A Survey on Routing Protocols for Wireless Sensor Networks［J］.Ad Hoc Networks，2005，3(3):325－349.

［2］李建中，李金宝，石胜飞.传感器网络及其数据管理的概念、问题与进展［J］.软件学报，2003，14(10):1717－1727.

［3］曹涌涛，何晨，蒋铃鸽.无线传感器网络中基于自适应定时器策略的分簇算法［J］.电子学报，2007，35(9):1719－1723.

［4］Hu Junping，Jin Yuhui，Dou Liang.A Time-Based Cluster-Head Selection Algorithm for LEACH［C］//13th IEEE Symposium on Computers and Communications，2008:1172－1176.

［5］Mhatre V，Rosenberg C.Design Guidelines for Wireless Sensor Networks:Communication，Clustering and Aggregation［J］.Ad Hoc Networks，2004，2(1):45－63.

［6］胡钢，谢冬梅，吴元忠.无线传感器网络路由协议LEACH的研究与改进［J］.传感技术学报，2007，20(6):1391－1396.

［7］Fan Xiangning，Song Yulin.Improvement on LEACH Protocol of Wireless Sensor Networks［C］//Proceedings of 2007 International Conference on Sensor Technologies and Applications，2007:517－528.

［8］张磊，陈曙.一个新的基于能量和距离的传感器网络协议［J］.计算机应用，2008，28(5):1117－1119.

［9］李成法，陈贵海，吴杰，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30(1):27－36.

［10］刘志，裘正定.基于分环多跳的无线传感器网络分簇路由算法［J］.通信学报，2008，29(3):104－112.

［11］朱艺华，沈丹丹，吴万登，等.无线传感器网络优化生存时间的动态路由算法［J］.电子学报，2009，37(5):1041－1045.

［12］王寅，尚凤军，任东海.一种基于自适应蚁群系统的传感器网络 QoS 路由算法［J］.传感技术学报，2010，23(2):239－244.

［13］Heinzelman W R，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans.on Wireless Communications，2002，1(4):660－670.

［14］Li Chengfa，Ye Mao，Chen Guihai，et al.An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks［C］//IEEE International Conference on Mobile Ad-Hoc and Sensor Systems Conference，2005:604－611.