最小努力交付的跨区虚拟簇多跳路由方法

摘要

本发明公布了一种最小努力交付的跨区虚拟簇多跳路由方法，属于计算机通信网络领域。本发明根据无线传感器网络中分簇多跳路由算法的特点，在LEACH协议的基础上，引用“区域”的概念，由汇聚节点向整个网络广播一个控制消息，各节点根据收到的信号强度确定自己所属的区域，通过区域的限制来规定多跳路由的方向。在网络轮循环过程中，当某区域选举簇头失败时网络在该区域产生补充簇头，在建立路由时，将簇虚拟成一个节点，避免相距较远的簇头间直接通信，进行最小努力的交付。本发明可以提高网络的生存时间，更好地平衡网络的节点能耗，均匀死亡节点的分布，也扩大协议适用的网络规模。

说明书

技术领域

本发明涉及一种无线传感器网络中负载均衡的路由方法，属于计算机通信网络的多跳路由选择方法的技术领域。

背景技术

无线传感器网络是由部署在监测区域内的大量微型、低成本、低功耗的传感器节点组成的多跳无线网络。由于传感器节点能量、处理能力和存储能力有限，传统MANET网络中的大多路由协议都不能很好地适用于传感器网络环境。在传感器网络的研究和设计中，实现路由协议的能量高效是人们关注的核心问题之一。随着研究的深入，文献中已经报告了多种路由协议算法，主要包括平面路由协议和层次路由协议两类。在平面路由协议中，所有节点的地位平等，不存在等级和层次差异，具有简单、易扩展、无须维护的优点。典型的平面路由算法有DD(Directed Diffusion)，SAR(SequentialAssignment Routing)和SPIN(Sensor Protocols for Information via Negotiation)等。但是采用这类路由的网络无管理节点，缺乏对通信资源的优化管理。层次路由弥补了平面路由的一些不足。层次路由通常将网络划分为簇(cluster)，簇头管理簇内节点，进行数据收集和融合处理，并转发到汇聚节点(sink)。LEACH(Low Energy AdaptiveClustering Hierarchy)是一种比较经典的、基于分簇的能量有效路由协议。

但是LEACH算法没有考虑节点的能量，簇头选举的随机性可能导致距离汇聚节点较远的簇头因远距离通信能耗过多，而较快死亡，影响整个网络的生存时间。对此，许多研究人员进行了深入研究并提出了若干LEACH的改进算法。但是在这些改进算法中，一些复杂参数的引入使得节点的运算量和运算复杂度增加。在分区定位算法中，自定义的WSN跨区多跳路由LEACH-CS(LEACH-Customizable Zone-Spanned)是一种比较简单的高效路由算法。因此，本发明在LEACH和LECSVCR的基础上，提出一种最小努力交付的跨区虚拟簇多跳路由算法LECSVCR(Least Effort Delivering CustomizableZone-Spanned Virtual Cluster Multi-hop Router)。算法通过判断接收信号的强弱来定位节点位置，在簇头间采用最小努力交付的多跳路由机制，有效避免了网络中节点能量消耗的不均衡问题，延长了网络寿命，使其适用规模扩大到汇聚节点所能覆盖的全部范围。

发明内容

本发明目的是改进LEACH协议的以下不足：

首先，簇头选举由于随机数产生的不稳定性可能导致簇头分布不合理和个数偏离期望值；

第二，簇头与汇聚节点直接通信，远离汇聚节点的簇头能耗较大，死亡较早，死亡分布不均匀；

第三，节点的通信范围有限，簇头与汇聚节点的单跳方式限制了网络覆盖范围，不适用大规模部署的网络；

第四，多次的仿真结果显示，从第一个节点死亡到网络失效经历了一段较长的时间，这一部分的能量可以更好地利用起来。

本发明为实现上述目的，采用如下技术方案：

本发明最小努力交付的跨区虚拟簇多跳路由方法包括如下步骤：

(1)网络初始化阶段，汇聚节点向整个网络广播一个控制消息，各节点判断接收到该消息的信号强度RSSI，估算与汇聚节点的距离，根据预设的区域差半径r0来标识各节点所属区域；

(2)簇的选举阶段，当节点产生的0～1之间的随机数小于阈值T(n)时，该节点当选簇头并广播自己是簇头的消息，非簇头节点根据收到的广播消息计算出自身到可与之通信的各簇头距离并记入距离表项；

(3)成簇阶段，非簇头节点检查自己表项，判断非簇头节点所属区域是否已产生簇头，若没有，则返回步骤(2)自动成为簇头，并广播消息，收到消息的非簇头节点各自计算距离值并记录到距离表项；若有，则采用就近原则选择最近的簇头节点发送入簇请求，同时复制自己的距离表项给簇头，告知簇头节点自己还可以和哪些区域的哪些簇头节点通信及其距离；簇头节点收到入簇请求后建立TDMA时刻表，与非簇头节点构成一个虚拟簇，并根据最远的簇成员确定广播半径回复各申请；

(4)路由建立阶段，同区域簇头相互不通信，X区域中的簇头按最近原则向Y区域中的簇头传递数据，其中X≠Y，且X区域中的任意节点到汇聚节点的距离均大于Y区域中的任意节点到汇聚节点的距离；

(5)数据传输阶段，非簇头节点收集数据，发送给所在虚拟簇的簇头节点：簇头节点对数据融合处理后交给下一跳虚拟簇，下一跳虚拟簇的边缘节点接收数据后转发给自己的簇头节点，由簇头节点向下一跳虚拟簇头转发，直到汇聚节点；循环(2)至(4)步至网络失效。

步骤(4)所述传递数据是根据区域差半径r0来确定下一跳虚拟簇的：所有簇头节点首先检查自己的表项，当没有可选的下一跳簇头节点时，比较各个非簇头节点的距离表项，选择距离汇聚节点较近方向的非簇头节点作为下一跳，该非簇头节点的表项中有距汇聚节点更近区域的下一跳节点，并且没有可选的下一跳的簇头节点与距汇聚节点更近区域的下一跳节点不在同一个区域内；若找不到这样的成员节点，则本轮放弃传递自己的数据，同时不接收路由请求；当有可选的下一跳时，簇头节点选择下一跳，发送路由请求；

收到路由请求的簇头判断两簇头间的距离，当距离小于等于d0/2时，直接回复确认消息，以实际距离作为请求者的广播半径；当距离大于d0/2时，查看下一跳簇头节点所在区域的非簇头节点距离表项，查找可达该路由请求者且距离小于下一跳簇头节点自身到请求簇头节点距离的成员，选择与该请求簇头节点距离最近的非簇头节点作为接收者，告知被选中的非簇头节点接收数据包并转发，下一跳簇头节点回复确认消息告知请求簇头节点将与最远的虚拟簇距离作为广播半径。

步骤(3)成簇阶段中所述被选的簇头节点不一定与非簇头节点在同区域。

本发明具有以下有益效果：

1、将一个真实簇的所有节点抽象成一个节点，减少上一跳的通信距离；

2、各节点维护各自距离表项，汇报给簇头节点，便于选择最佳的路由路径；

3、簇间建立多跳路由，算法简单，均衡能耗，死亡节点分布均匀；

4、延长了网络有效时间，缩短从第一个节点死亡到网络失效的时间；

5、保留原LEACH中关于节点自主决定是否成为簇头的特点，从而不需要全局信息，减少通信能耗。

附图说明

图1簇头跨一区多跳路由示意图；

图2MATLAB随机生成网络节点拓扑图；

图3LEACH第100轮死亡节点分布图；

图4LECSVCR第100轮死亡节点分布图；

图5网络生存时间曲线；

图6网络总能耗曲线。

具体实施方式

下面结合附图对本发明的技术方案进行详细说明：

1.自定义的跨区多跳路由算法LECSVCR

1.1LEACH算法简介

LEACH是由MIT的Heinzelman等人设计的一种层次型低功耗自适应聚类路由协议。其执行过程引入了“轮”的概念，每轮循环分为簇的建立阶段和数据通信阶段。在簇的建立阶段，每个存活节点产生一个0～1之间的随机数，如果此数小于阈值T(n)，则发布它是簇头的消息。在每轮循环中，如果节点已成为簇头，则将T(n)设为0，这样该节点不会在本轮再次当选簇头。T(n)表示为：

$T\left(n\right)=\left(\begin{array}{cc}\frac{P}{1-P\left[r\mathrm{mod}(1/P)\right]},& n\in G\\ 0,& n\notin G\end{array}\right)---\left(1\right)$

其中，P是簇头在所有节点中所占的百分比，r是选举轮数，rmod(1/p)为这一轮循环中当选过簇头的节点个数，G是这一轮循环中未当选过簇头的节点集合。在数据通信阶段，簇内节点把数据发送给簇头，簇头进行数据融合后将结果发送给汇聚节点。因此簇头消耗的能量比簇内节点要多。LEACH通过轮循环方式保证各节点等概率地担任簇头，使节点相对均衡地消耗能量。但是仍然有一些缺陷，主要体现在以下方面：

(1)第一个节点死亡较早。从文献[9]以及后续的相关改进工作中发现，LEACH出现第一个死亡节点直至整个网络死亡，经历了一个较长的时间。这一部分的能量可以更好地利用起来；

(2)簇头选举的随机性会导致每轮簇头分布不均匀。部分簇头与簇内节点可能出现距离太近或太远，使得簇的拓扑结构不理想，部分簇头的负担过重，降低网络的能耗均衡性；

(3)节点死亡的不均匀性。多次的仿真结果显示，距离sink节点远的节点比距离近的节点死亡得更快，在网络后期传感到的数据实际上仅来自sink节点附近的区域，已经提前失去了监测的意义，降低网络的实际应用效果；

(4)不适用于节点大规模部署。LEACH中簇头到sink节点的通信方式是单跳的，而目前的节点覆盖能力一般为200米左右，这个距离会限制传感节点的部署范围，不能进行大规模的监测。

1.2LEACH-CS简介

首先，介绍一下能量模型。在算法分析过程中，LEACH-CS采用LEACH的提出者Heinzelman W等人应用的信道传输模型，即自由空间模型和多路径衰落模型。当发送节点和接收节点之间的距离d小于某个值d₀时，采用自由空间模型，发射功率呈d²衰减；否则采用多路径衰减模型，发射功率呈d⁴衰减。模型定义无线电路发送距离为dm的1bit消息消耗的能量为：

$E_{\mathrm{Tx}}(l,d)=E_{\mathrm{Tx}-\mathrm{elec}}(l,d)+E_{\mathrm{Tx}-\mathrm{amp}}(l,d)$

$=\left(\begin{array}{cc}{\mathrm{lE}}_{\mathrm{elec}}+{\mathrm{lϵ}}_{\mathrm{fs}}{d}^2,& d<d_0\\ {\mathrm{lE}}_{\mathrm{elec}}+{\mathrm{lϵ}}_{\mathrm{mp}}{d}^4,& d\ge d_0\end{array}\right)---\left(2\right)$

相应地，接收这些信息消耗的能量为：

E_Rx(l，d)＝E_Rx-elec(l，d)＝lE_elec    (3)

数据融合消耗的能量为：

E_Gx(l，d)＝lE_gather    (4)

以上式中，E_elec表示电路发送或接收1bit数据所消耗的能量；ε_fsd²和ε_mpd⁴为每放大1bit数据放大器消耗的能量；E_gather为每1bit数据融合处理消耗的能量；式(4)为将接收到的n个节点发送过来的n×1bit数据融合成1bit数据所消耗的能量。式(2)中的d₀由下面式子决定：

$d_0=\sqrt{\frac{{ϵ}_{\mathrm{fs}}}{{ϵ}_{\mathrm{mp}}}}---\left(5\right)$

LECSVCR是在LEACH的基础上，引入“区域”和“区域差”的概念，当某区域选举簇头失败时产生补充簇头，建立簇间路由时以跨区距离的约束来自定义合适的多跳路由方案。算法中“区域(zone)”，指以汇聚节点为圆心，以多个不同长度为半径的相邻圆周线之间围成的各圆环带(如图1)；“区域差半径(zone difference radius)”，指形成相邻圆周的两个半径之差的绝对值，记为r₀(如图1)。

LECSVCR规定了节点分布密度ρ和区域差半径r₀的关系(式2、式3)，在理论上为网络发挥更好的能效提供参考。

$r_0=\frac{2}{j}\sqrt{\frac{\mathrm{ch}}{\mathrm{\pi \rho p}}}---\left(6\right)$

式中，ch是包含在距汇聚节点d₀范围内的j个区域中所产生的簇头总数，这些簇头分担其它远汇聚节点的区域内簇头传来的数据量，ch的值可以根据实际情况自定义。近汇聚节点的ch个簇头接收由其它簇头发送来的数据所消耗的能量，等同于这ch个节点新接受了簇内成员，但是必须对接受的数量加以限制。整个网络平均簇成员数为(1-p)/p，设这ch个簇头新增成员不得超过其1/v，v可据实际情况自定义，则可得到式3：

$r_0\ge \frac{2a}{j}\sqrt{\frac{\mathrm{pv}}{(1-p)\pi }}---\left(7\right)$

式(6)提供了r₀和ρ的关系，式(7)提供了r₀和v的关系，实际环境中参考两式使网络发挥更好的效能。LEACH-CS选择簇头间合适的传输距离的方法就是跨区多跳，其具体方案如下：

(1)网络初始化阶段，汇聚节点向整个网络广播一个控制消息，各节点判断接收到该消息的信号强度RSSI，估算与汇聚节点的距离，根据预设的r₀来标识自己所属区域；

(2)簇的建立阶段，当节点产生的0～1之间的随机数小于阈值T(n)时，该节点当选簇头并广播自己是簇头的消息，非簇头节点根据收到的广播消息判断自己所属区域是否已产生簇头。若没有，则自己作为簇头，并广播消息；若有，则采用就近原则选择最近的簇头发送入簇请求(被选的簇头不一定与自己同区域)。簇头收到入簇请求后建立TDMA时刻表并回复各成员；

(3)路由建立阶段，同区域簇头相互不通信，距汇聚节点较远区域的簇头按最近原则向距汇聚节点较近区域的簇头发送路由请求，收到请求消息的簇头回复确认消息。当簇头距离汇聚节点d₀范围内，便直接与汇聚节点通信。

(4)数据传输阶段，非簇头节点收集数据，发送给所在簇的簇头节点。簇头对数据融合处理后交给下一跳节点，直到汇聚节点。循环(2)至(4)步至网络失效。

LEACH-CS选择典型的分簇式路由协议LEACH作为研究对象，提出了自定义的跨区多跳路由机制。该机制以区域为基础，执行簇头补充、跨区入簇和自定义跨区多跳路由等新过程，提高了网络生存时间、能耗速度和死亡节点分布等方面的性能。但是在真实环境中，在长时间的循环后，区域中远汇聚节点那一侧边缘的节点将会较区域中其他方位的节点死亡早，逐渐形成检测盲区。

下一节主要叙述本发明LECSVCR协议。

1.3最小努力交付的多跳路由算法

一般来说，近距离节点之间的通信能耗少，通信质量也比较好。LECSVCR协议就是通过缩短通信节点间的距离来节省能量。在无线传输中，发射功率的衰减随着传输距离的增大而呈指数衰减。在算法分析过程中，本发明同样采用LEACH的提出者Heinzelman W等人应用的信道传输模型。其具体方案如下：

(1)网络初始化阶段，汇聚节点向整个网络广播一个控制消息，各节点判断接收到该消息的信号强度RSSI，估算与汇聚节点的距离，根据预设的r0来标识自己所属区域；

(2)簇的建立阶段，当节点产生的0～1之间的随机数小于阈值T(n)时，该节点当选簇头并广播自己是簇头的消息，非簇头节点根据收到的广播消息计算出自身到可与之通信的各簇头距离并记入距离表格。完成这个过程后，网络开始补充簇头。普通节点检查自己表项，判断自己所属区域是否已产生簇头，若没有，则自动成为簇头，并广播消息，收到消息的节点各自计算距离值并记录到距离表格；若有，则等待很短时间后，采用就近原则选择最近的簇头发送入簇请求(被选的簇头不一定与自己同区域)，同时复制自己的表格给簇头，告知簇头自己还可以和哪些区域的哪些簇头通信及其距离。簇头收到入簇请求后建立TDMA时刻表，并根据最远的簇成员确定广播半径回复各申请；

(3)路由建立阶段，同区域簇头相互不通信，距汇聚节点较远区域的簇头按最近原则向距汇聚节点较近区域的簇头传递数据。算法中是根据区域差半径r0来确定下一跳节点所在区域的。进入路由建立阶段后，所有簇头首先检查自己的表项，当没有可选的下一跳时，比较成员的距离表项，选择距离汇聚节点较近方向的某一成员作为下一跳，该成员的表项中应有距汇聚节点更近区域的下一跳。若找不到这样的成员，则本轮放弃传递自己的数据，同时不接收路由请求。完成这一过程后，簇头选择下一跳，发送路由请求。收到请求消息的簇头判断两簇头间的距离，当距离小于等于d0/2时，直接回复确认消息，以实际距离作为请求者的广播半径。当距离大于d0/2时，查看成员距离表项，查找可达该请求者且距离小于簇头自身到请求者距离的成员，选择与该请求者距离最近的几个成员作为接收者，告知被选中的节点接收数据包并转发。回复确认消息告知请求者将与最远的接受者距离作为广播半径。这样，对于上一跳而言，下一跳所要到达的整个簇对于上一跳而言被抽象成为一个大的虚拟的簇头，实现了最小努力交付。当簇头距离汇聚节点d0范围内，便直接与汇聚节点通信。(时隙5)

值得注意的是，簇头下一跳的选择可以是相邻区、跨一区或跨更多区的最近簇头，这取决于r0和d0的关系。一般情况，如当r0等于d0时，邻区传递；当d0是r0的两倍时，跨一区传递；当d0是r0的三倍时，跨两区传递等。跨区一方面提供更多距近汇聚节点d0范围内的簇头来分担数据传输能耗，另一方面缩小区域边缘可能形成的盲区带。如图1，设定Zone1和Zone2合为α区，Zone3和Zone4合为β区，Zone5和Zone6合为γ区，且不采用跨区路由，则β、γ区按照邻区最近原则建立路由，这样本来由Zone1和Zone3中簇头中继的数据将分别由Zone2和Zone4中簇头中继，这样Zone2和Zone4区中的簇头能耗将增加，导致α、β分区一侧的节点死亡较早，形成盲区带。

(4)数据传输阶段，非簇头节点收集数据，发送给所在簇的簇头节点。簇头对数据融合处理后交给下一跳虚拟簇，下一跳的边缘节点接收数据后转发给自己的簇头，由自己的簇头向下一跳虚拟簇头转发，直到汇聚节点。循环(2)至(4)步至网络失效。

从上述步骤中可见，由于各节点不需要周期性地报告所属区域，只在初始化阶段判断并只告知自己自身位置，所以这样的定位能耗不仅不会给整个网络带来明显的负担而且可以基本忽略。且由汇聚节点发送控制消息，可以将网络规模扩大到汇聚节点信号覆盖的范围。算法中，簇头选举采取区域自治，即当某区域没有产生簇头时，该区域某节点会自动成为簇头，对簇头均匀化分布起到补充作用；而在成簇时，非簇头节点打破区域的束缚，寻找距离最近的簇头入簇，节省能量；簇间路由采用尽最小努力交付的跨区多跳方式，节省簇头能量消耗，推迟整个网络节点死亡时间、平均分布死亡节点。2.1仿真环境及参数配置

假设200m×200m的正方形中随机分布500个节点，汇聚节点位于正方形的右上角(如图2)。具体仿真参数如表1所示。

表1仿真参数

 参数类型  参数值 传感器个数  500

 传感器位置坐标范围(单位：m)  (0，0)～(200，200) 数据包长度  4000bit 控制包长度  100bit 电子发射消耗能量E_Tx  50nJ/bit 电子接收消耗能量E_Rx  50nJ/bit 近距离发射放大器参数ε_fs  10pJ/bit/m² 远距离发射放大器参数ε_mp  0.0013pJ/bit/m⁴ 数据整合能量E_DA  5nJ/bit/signal 簇的最佳个数百分比p  5％ 传感器初始能量E₀  1J 距离门限d₀  87.7m 区域差半径r_o  45m

由表1知，在整个网络中每轮簇头数约为25，现将这25个簇头传输的数据分担到3个或4个近汇聚节点簇头上，即ch＝3或ch＝4。将相关参数代入式(6)中，计算得表2。

表2ch＝3和ch＝4时的r₀取值情况

  p＝0.05ρ＝0.0125  ch＝3  ch＝4  邻区/j＝1/45＜r₀≤90  r₀＝79  r₀＝90  跨一区/j＝2/30＜r₀≤45  r₀＝39  r₀＝45  跨两区/j＝3/23＜r₀≤30  r₀＝26  r₀＝30

若以式(7)计算，则相当于v＝2或v＝3，即不得超过平均簇成员数的1/2或1/3。表2中r₀的值都是可取值，实验中取r₀＝45。

仿真设定网络运行轮循环周期为20s，普通节点每2s收集一次数据转发给簇头，即每周期普通节点发送10次数据，簇头节点接收、融合和发送10次数据。设定LEACH和LECSVCR的网络节点初始能量、拓扑结构一样，规定当网络中80％的节点无法工作即认为该网络不可用。

2.2性能评价标准

仿真实验将改进的路由算法和原LEACH在相同的仿真环境和网络参数配置下进行测试。从多个方面对跨区多跳和原有方式的路由表现进行比较，具体包括：

■网络寿命；

■节点死亡个数和分布；

■第一个节点死亡至网络无效的时间；

■网络累计能耗的变化情况；

仿真结果如图3至图6及表3所示，分别对比两种协议的网络寿命、死亡节点分布和特定数量节点的死亡时间等。

表3LECSVCR和LEACH两种协议的节点死亡状况统计

2.3实验性能分析

图3和图4分别是LEACH协议与LECSVCR协议在第100轮时节点死亡的分布状态。LEACH协议中距汇聚节点较远的节点已经基本死亡(如图3)，这与LEACH协议簇头直接和汇聚节点通信消耗能量较大的分析基本符合。而LECSVCR协议采用最小交付的跨区多跳虚拟簇路由机制，使得在多轮循环后大多数节点依然存活，并且基本保证死亡节点的平均分布(如图4)。这样可以在一段较长的时间内保证数据监测范围。同时，图4也显示，在汇聚节点附近的节点仍然比其它区域存活的多，这是由于该区域的节点少，成簇时簇内成员相对较少，节省了簇头能量，因而存活的节点较多。

图5和图6分别是两种协议在各轮次存活节点数目和网络总能耗的曲线图。在图5中，LECSVCR继承LEACH-CS的簇头补充机制使得簇头平均分布、最小交付的虚拟簇多跳使得能耗均匀，所以第一个节点的死亡时间远远晚于LEACH。另外，LECSVCR在任意时刻存活的节点数目多于LEACH，生存周期长。结合表2，LECSVCR的第一个节点死亡时间是LEACH的3.14倍，随着时间的推移，倍数逐渐减少，百分之八十的节点死亡时间仅为LEACH的1.36倍。这也反映在图5中，随着轮次增加，LECSVCR曲线渐渐靠近LEACH曲线。这是由于LECSVCR协议增加了路由控制信息，在网络生存的后期，各节点能量所剩无几，这些控制信息会明显增加能耗，加快节点死亡。曲线的走势说明LECSVCR有效的存活期比LEACH更加集中，网络出现大面积监控盲区的时间短。图6是网络总能耗的累计曲线图，从图中看出，LECSVCR总能耗变化率比LEACH变化小，说明LECSVCR每轮能耗更加均衡。结合表3，LECSVCR在减少能耗的同时，对整个网络的运行能力并没有减弱。