基于簇的无线传感器网络交会路由协议

杨 旭，王春佳2，李 莉

(1.云南机电职业技术学院 工业信息技术系，昆明 650203;2.云南师范大学 基础教育集团，昆明 650092)

0 引言

无线传感器网络(WSN)由大量低成本、低功耗和智能传感器节点以及一个或多个sink或基站(BS)组成[1-2]，这些节点体积小，可以执行许多重要功能，包括事件感知、信息处理和数据通信[3-4]，WSN已经广泛应用与军事应用和民用场景[5-6]，由于易于部署，扩展传输范围和自组织等各种优点，WSN已经取代了传统网络。

WSN中传感器节点成本低且能量有限，由于这种能量约束，有效的路由协议可以使得传感器节点感测环境并生成有用的数据[7]。当用户或sink想要数据时，将查询发送到具有相关数据的传感器节点，传感器节点通过中间节点将生成的数据发送给用户或sink。由于这些传感器节点具有有限的功率，它们可以容易地耗尽其能量，因此为了增加网络寿命并减少延迟，需要从源节点到sink数据的有效路由[8]。随着WSN技术的深入，平衡网络负载、延长网络寿命和均衡网络能量消耗已经成为WSN研究的重点。

WSN中的分层路由是一个非常重要的主题，在过去十年中一直吸引着研究者，典型的分层路由称为簇的路由，其中网络被分成多个簇，低功耗自适应集簇分层协议(Low-Energy Adaptive Clustering Hierarchy, LEACH)是一种典型的分层协议[9]，目前许多协议都是在LEACH协议上进行改进得到的[10]，如文献[11]中提出的基于非均匀分簇的无线传感器网络分层路由协议，该协议以LEACH的分簇思想为基础，通过分层机制及竞争机制选取簇首，使簇首节点分布更加合理，有效均衡节点的能量消耗。和文献[12]中基于簇首移动的无线传感器网络路由算法，该协议创新点是将簇首设置为移动节点，通过一定规则确定簇首每轮所需移动到的最佳位置，实现节点能耗均衡。

最近关于WSN的研究有一部分为非典型分层路由，包括基于链的路由协议、基于树的路由协议、基于网格的路由协议和基于区域的路由协议[13]。基于区域的拓扑是一种最新结构，其中一些传感器节点在特定区域中指定并充当高层节点。高层节点执行从普通节点的数据收集和到数据的数据传输任务，可以根据负载平衡要求调整区域的大小[14]。在基于区域的路由协议中，网络在不同区域之间划分，传感器节点是由他们所属的地区确定。LBDD是一种典型的基于区域的路由协议[15]，拓扑结构简单，通信方式也很简单，但是这种拓扑很容易导致能量消耗不平衡，此外，在大区域网络中，线路或条带上的泛滥将导致节点的大量能量消耗。与LBDD不同，Railroad协议和ring由协议[16]首先从会合区域获取sink的位置信息，然后将数据发送到sink，但是两种路由协议在大型网络中导致过多的开销，而预期数据传输延迟高于LBDD。

为了解决现有基于区域路由协议中能量不均衡、网络寿命问题，本文提出一种基于簇的交会路由协议CRRP。在该协议中，整个传感器网络被划分为若干交会区域，并且根据所驻留的区域对节点进行分类。在本文中，簇在分区区域内构建，然后根据节点程度进行簇头选择，簇头具有sink位置的信息，只要sink的位置发生变化，sink就会通过网关节点将其更新的信息发送到最近的簇头。为了找到sink的位置，常规节点将请求消息发送到其最近的骨干节点，并且该骨干节点将请求发送到簇头。通过这种方式，常规节点了解了sink的位置，然后直接将数据发送到sink，当簇头开始耗尽其能量时，重新进行新簇形成。本文协议会合区域划分整个网络区域并在传感器节点之间分配网络负载，可以增加网络寿命。

1 CRRP协议

在所提路由协议中，网络由若干传感器节点组成，传感器节点本质上是静态的。网络由交叉区域划分，并在其中构建簇，sink将其更新的位置信息发送到交叉区域内的节点，并且源节点从它们获取sink的当前位置并将数据发送到sink。

如图1所示，在网络中间构造一些水平和垂直宽度的虚拟区域，其中心位于任意位置(u,v)。该虚拟结构将网络划分为四个部分：1)水平左hl;2)水平右hr;3)垂直向上vu;4)垂直底部vb。这个交叉区域充当交会区域，位于该会合区域内的传感器节点被称为骨干节点。在该交叉区域中，基于节点和最大公共邻接节点来构造簇，每个簇由一个簇头组成。这些簇头负责将sink的位置发送到源节点，并根据sink的当前位置更新sink位置。该协议包括发现邻居、形成交叉区域、簇的形成和簇头创建，发现传感器节点区域和最终数据传输。

图1 交会区域和骨干节点的初始视图

首先对WSN网络模型进行假设：

1)部署后，所有传感器节点都是静止的。

2)Sink将改变其位置，即sink是移动的。

3)对于sink的计算能力，电池消耗和存储器没有限制。

4)传感器节点的能量有限。

5)所有传感器节点均匀。

6)为每个节点分配一个唯一的ID。

7)网络拓扑在簇形成时不受影响。

本文协议的整体流程见图2所示。

图2 本文协议流程图

1.1 邻居发现和交会区域形成

在邻居发现的第一阶段，起始节点广播邻居发现(NBR_D)控制包，包含节点的ID，节点位置及其剩余能量水平。在接收到该包时，该节点邻居表包含发送方节点的节点ID，其位置和剩余能量。如果表中已经存在发送方节点的条目，则接收方丢弃该包；如果先前没有广播，sink也广播相同的包。在此阶段结束时，所有节点都具有关于其一跳邻居的信息。

算法1：邻居发现。

Nb(x)任何节点x的邻居集合，初始化为φ

Nbtable(x)：由节点x维持的邻居表初始化为φ

Erx：节点x的能量

NBR_Dx：如果传感器节点x发送数据包，则节点x的邻居发现控制数据包设置为真，初始化为false

Locx：节点x的位置

NBR_D:if (idy∉Nb(x)) then

Nb(x)=Nb(x)∪y；

用更新Nbtable(x)

if(NBR_Dx==false)then

NBR_Dx←true

1_rb(NBR_Dx,idx,Erx,Locx)；

▷广播NBR_D包

else 丢弃包

endif

else丢弃包

endif

对于交会区域的生成与构建，将其视为(Xmax,Ymax)，并将区域的宽度视为w。因此wx和wy可以确定条带的水平和垂直范围。

(1)

(2)

1.2 传感器节点区域发现

传感器节点使用它们的位置信息坐标(x,y)来确定它们所属的区域。例如，驻留在第一分区和第八分区中的节点将从hr与目的地(x,v)通信。以相同的方式，第二和第三分区的传感器节点可以从vu与目的地(u,y)等进行通信，其中(u,v)是网络的中心。

算法2：节点区域发现。

θ=0,α=0

(u,v)：网络的中心

(x,y)：节点的位置

令π=180°;C←(u,v)

▷C定义了网络的中心。

计算节点x与位置的新坐标(x-u,y-u)和(x,y)

(A,B)←(x-u,y-u)

if (A>0&&B>0)thenα←θ

具有位置(x,y)的节点属于第1区域，可以从hr与目标位置进行通信(x,v)。

具有位置(x,y)的节点属于第2区域，可以从vu与目标通信位置(u,y)。

end if

end if

if (A<0&&B>0) thenα←π-θ

具有位置(x,y)的节点属于第3区域，可以从vu与目标位置通信(u,y)。

位置为(x,y)的节点属于第4区域，可以从hl节点与目标位置通信(x,v)。

end if

end if

if (A<0&&B<0) thenα←π+θ

位置为(x,y)的节点属于第5区域，可以从hl节点与目标位置通信(x,v)。

位置为(x,y)的节点属于第6区域，可以通过vb与目标通信位置(u,y)。

end if

end if

if (A>0&&B<0) thenα←2π-θ

位置为(x,y)的节点属于第7区域，可以通过vb与目标位置进行通信(u,y)。

位置为(x,y)的节点属于第8区域，可以从hr与目标位置进行通信(x,v)。

end if

end if

1.3 簇的生成

通过以下步骤在集合区内建立簇：

1) 簇形成机制由具有最高节点度的节点i发起；

2)在初始节点的单跳邻居中，找出节点p，具有最大的公共邻接。如果有多个节点，则考虑ID最低的节点；

3)节点i和p的一个跳邻居中常见的节点属于包括i和p的一个簇，节点i将被视为簇头(CH)；

4)具有最节点度的剩余节点i(发起节点)的一跳邻居为簇的形成开始相同的进程，并声明自己为CH。

簇生成伪代码见算法3。

算法3:簇的生成：

N：网络中节点的总数

(Vi,Ei)：节点i的连通矩阵

▷Vi包含节点i和它的单跳邻中

▷Ei包含Vi中节点之间的双向边

i：发起节点

S(i)：节点i的邻居集

L(i)：L(i)包含节点i的一个跳过邻居节点

C(i)：簇中元素集合，最初为空

N_C(i)：不在簇中的节点集

i=maxargjdegree(Nj) ▷j是任意节点

S(i)={j,(i,j)∈Ei},C(i)={i}While (L(i)≠φ)

发现p∈L(i)与最大|l(i)∩l(p)|

C(i)←[Ci∪{p}∪{j,{j,p}}∈Ei]

N_Ci←[Vi∉Ci]

Endwhile

i=maxargidegree(N_Ci)

CH←i

对节点i重复步骤2

簇形成过程如图3所示，假设节点1具有最大的节点度，因此启动了簇的形成过程。节点(2, 3, 4, 5, 6)是相邻的节点。根据算法3，节点3应该是节点p，因为它与节点1的公共邻域最大。所以节点(1, 2, 3, 4, 5)必须在一个簇中，节点1应该是CH。

图3 簇形成技术

在本文协议中，簇头重选与新的簇形成一起发生，步骤为：

1)当任何簇头节点i开始耗尽其能量时，按照算法1得到簇内具有最大公共邻接的节点；

2)节点将声明为新的簇头，并按照算法3生成新的簇。

1.4 移动sink管理

在协议汇聚节点的这个阶段，节点通过网关节点将其位置通知给簇头节点，集合点区域内的所有簇头都有关于sink位置的信息。当sink移动时，将Beacon包广播到其邻居之后，sink选择其邻居之一将其位置信息中继到集合区域内最近的簇头之一。sink借助传感器节点区域发现机制或借助位置因子(LF)转发数据。

令节点i想要从邻居节点Nb(i)中选择其中一个邻居节点，Eri是其剩余能量，LF(i)定义节点i的每个相邻节点的位置因子。具有坐标(xk,yk)的k∈Nb(i)具有残余能量Erk，并且节点k距离目的地的Eucledian距离是Dk。

(3)

那么kth邻居的LF(k)可以计算为:

(4)

(5)

next_nodei=max(LF(i))

(6)

其中:next_nodei是由节点i选择的相邻节点。

算法4:移动sink管理：

Loc_sinkx：任何节点x都存储sink位置信息

B_x：如果任何标记为主干节点的节点x为真，初始化为false

sink_loc：sink的位置

Beacon：l_rf(BeaconReply,idx,Erx,idsink)；

▷将BeaconReply包单播到sink

使用主干节点作为算法2中的骨干节点发送位置sink，汇聚节点转发位置使用位置因子将包发送到节点z；

l_rf(Location,idsink,sink_loc,next_nodez)；

▷位置包被单排到选定位置节点z。

节点y或sink向节点x发送以下数据包。

Lacation：

if (idx==next_nodey)then

if (Loc_sinkx≠sink_loc) then

Loc_sinkx←sink_loc

if (B_x==true) then

x将sink信息发送给它的CH。

else 选择距离目标最近的节点z。

endif

else

丢弃包；

end if

else

丢弃包；

end if

一旦到达骨干节点的sink位置信息，就发送到其簇头，然后该簇头以相同的方式将其发送到其相邻的簇头，现在所有簇头具有关于sink的新位置的信息。

1.5 sink位置恢复

Sink的位置信息在簇头的帮助下到达常规节点，当常规节点想要传输数据时，它应该知道从集合区域内的簇头获得新sink的位置。它通过使用位置因子选择相邻节点来发送Locreq的包，并且该相邻节点将请求包转发到其最近的骨干节点。 一旦到达骨干节点，骨干节点就会将其转发到其簇头，簇头已经有了新的sink的位置信息，因此簇头将sink位置信息转发到常规传感器节点，如算法5所示。

算法5:sink位置恢复。

CH：具有sink位置

CHid：簇头的id

Bx：如果任何节点是骨干节点，则为真

sink_Loc：Sink的位置

next_nodex：任何下一个节点都由任何节点x选择转发该数据包

reversex：簇头x选择节点将sink的位置发送到请求的节点

Locreq节点从节点y∈Nbr(x)接收数据包

Locreq:if (idx==next_nodey) then

reversex←idy；

if (Bx==true)

Bx将Locreq转发给它的CH。

lr(Locreply,CHid,sink_locreversex)；

▷响应请求的节点。

else

▷节点x使用位置因子选择next_nodex

lr(Locreq,idx,next_nodex)；

endif

else

丢弃包

endif

最后进行数据传输，在从骨干节点传感器节点获得有关sink位置的信息之后，借助于相邻节点将数据转发到sink。传感器节点借助于位置因子，基于剩余能量和距离sink的最小距离来选择相邻节点。在接收数据时，相邻节点使用相同的技术将其转发到其邻居，重复相同的过程直到数据到达sink。

2 仿真结果分析

为验证本文CRRP协议有效性，将本文算法与现有其他算法进行比较，仿真实验环境为MATLAB R2013b，基于表1中所示的参数来执行仿真实验。

表1 仿真实验参数

传感器节点发送控制包以构建会聚区域并管理汇聚移动性，图4中给出了不同协议的具有不同sink速度的控制包的平均能耗。将本文协议与现有其他协议进行比较，包括Rendezvous路由协议[17]，LBDD路由协议，Railroad路由协议和Ring路由协议。

图4 控制数据包开销

如图所示，与其他协议相比，本文协议的控制包开销非常少，少于其他协议，这是因为本文协议中，会合区域与源或sink之间的平均距离小于其他协议，且在本文协议中只有部分高层节点(即簇头)参与到发送sink位置到源节点的主要任务中，而源节点通过建立有效的路由将数据发送到sink，这种方法将有助于降低能耗。而在LBDD中，内联节点存储来自源节点的数据，当该内联节点收到查询时，它会将数据发送到sink，这会导致控制数据包开销增加。在RailRoad路由协议中，站点处的元数据存储过程和从站点检索sink位置的过程需要控制包交换。在Ring路由协议中，所有环节点都存储sink的位置，随着网络操作的进行，它需要交换控制包来修复环，因此环长度增加，导致更多的能量消耗。Rendezvous路由协议在交会区域内保持树来发送数据，控制包需要根据sink位置来设置链路。随着速度的增加，导致控制数据包开销增加。各种协议的每个节点的总能量消耗如图5所示。

图5 平均能耗

可以观察到，由于更大的控制包开销，LBDD的能量消耗最高，其存储来自源节点的数据，并在会合区域中淹没sink的查询，随着sink速度的增加，LBDD的能量消耗近似线性增长。Rendezvous协议不需要sink位置，但是平均路径长度高于RailRoad协议，Ring路由协议总能量根据sink速度而增加。本文协议中，源和sink之间的平均距离几乎与RailRoad和Ring路由协议相同，由于较少的控制包开销，使得本文所提协议能耗少于现有其他协议。

每个节点的能量消耗和传感器节点之间的不平衡负载影响网络寿命，在图6中给出了不同协议之间的网络寿命性能，可以看出本文协议的网络寿命大于其他协议的网络寿命，原因是本文协议消耗更少的控制包，平衡传感器节点之间的负载，并遵循用于数据传输的最佳路由。

图6 网络寿命

3 结论

在本文中，提出了一种基于簇的会合路由协议CRRP，其中在会合区域内构建簇以实现可扩展性并维持网络负载，当传感器节点想要将数据传输到sink时，从该会合区域获取sink的位置信息，然后将数据发送到sink。所有骨干节点都不参与sink位置检测，只有簇头参与到发送sink位置到源节点的主要任务中，能够使得WSN降低能耗和延长网络寿命。将本文协议与现有LBDD协议、Ring Routing协议、RailRoad和Rendezvous协议进行比较，仿真实验表明，本文协议在能耗和网络寿命性能方面优于其他现有协议，表明本文方法的可行性与有效性。