无线传感网络中基于环形的层次型路由协议*

刘 青李兰兰张德树

(1.滁州职业技术学院 信息工程学院，安徽 滁州 239000；2.南京航空航天大学 计算机科学与技术学院，江苏 南京 211106)

无线传感网络(Wireless Sensor Networks，WSNs)具有组织、部署快捷等优势[1-2]。目前，WSNs已在多个领域内广泛使用，如健康医疗，野外环境监测。WSNs内节点先感测环境数据，再将数据传输至信宿(Sink)，进而实现对环境监测的目的。

由于Sink需收集检测区域内所有数据，邻近Sink的节点承担了较多的数据转发任务。这就使得这些节点的能耗速度快于其他远离Sink的节点。学术界将这种情况称为热点问题[3]或者能量空洞问题[4-5]。热点问题会导致网络分割，降低了WSNs的性能。

基于移动Sink的路由是缓解热点问题的可行办法。通过Sink的移动，平衡网络内节点的能耗，避免网络内节点的能量消耗过快，进而缓解热点问题[6-7]。然而，由于Sink的位置是随时间变化的，向节点通告Sink的位置需交互大量的消息，这增加了节点的能耗，以及数据传输时延。

将节点划分为双层的基于虚拟设备的层次路由可以有效地减少交互消息的开销[8-9]。在层次路由中，无需向整个网络泛洪Sink位置，只需向高层次的节点提供Sink位置。而当低层次的节点需要传输数据时，就向高层次节点索取Sink位置信息。高层次节点就为低层次节点扮演了Sink位置提供者的角色。此外，高层次节点有时也扮演数据转发者的角色。因此，层次路由能够缓解在网络通告Sink位置信息的开销以及降低数据传输时延。

为此，针对基于移动Sink的WSNs网络，提出一种基于环形的层次路由协议(Ring-based Hierarchical Routing，RBHR)。RBHR路由先将网络进行环形分割，形成多个等间隔的环。然后，再选择数据转发节点，并由这些节点构建环。最后，这些数据转发节点利用角度路由策略向Sink传输数据。仿真结果表明，RBHR路由降低了能耗，并降低了数据包传输时延。

1 系统模型

在二维方形检测区域ℓ×ℓ内均匀地部署n个传感节点和一个Sink。所有传感节点是静止的，不能移动。Sink遵照随机点移动(Random Waypoint Mobility，RWM)模型移动。

每个传感节点具有自己的唯一的ID号，令si表示第i个传感节点。令(xi，yi)表示传感节点si的位置。每个传感节点具有固定的通信半径R。此外，假定每个节点知晓检测区域ℓ×ℓ的中心点位置。

令Ni表示节点si的一跳邻居节点集，其定义如式(1)所示:

式中:R表示节点的通信半径；d(si，sj)表示节点si与节点sj间的欧式距离。

1.1 能量消耗模型

节点的大部分能量用于发送数据和接收数据。因此，本文只考虑节点在执行发送数据和接收数据这两个动作所消耗的能量。引用文献[10]相同的能量消耗模型，如图1所示。

图1 能量消耗模型

节点传输m比特数据所消耗的能量ETx(m，d):

式中:Eelec表示发射电路处理1比特数据所消耗的能量；εfs、εamp表示在自由空间信道模型、多径衰落信道模型下功率放大电路处理1比特数据所消耗的能量；d0表示判断信道模型的距离阈值，其定义如式(3)所示:

节点接收m比特数据所消耗的能量ERx(m):

2 RBHR路由

RBHR路由主要由三个阶段构成:区域分割，环上转发节点(Forwarding Node on Ring，FNR)的选举和数据传输三个阶段构成。

2.1 基于环的区域分割

将感测区域划分为n个等间隔的同心环R1，R2，…，Rn，这n个环所对应的半径分别为r1，r2，…，rn。如图2所示，图中空心圆表示传感节点；三个环R1，R2，R3以点C为圆心，分别以r1，r2，r3为半径。

图2 基于环的网络分割示例

首先，依据方形的检测区域的边长ℓ，估计最优的环数n:

然后，依据式(5)计算第k个环的半径rk:

2.2 环上转发节点的选举

确定了环数n和各个环的半径(r1，r2，…，rn)后，Sink就在监测区域内广播此信息infor_MSG，其包含[(r1，r2，…，rn)，(R1，R2，…，Rn)]。一旦收到infor_MSG消息，节点(假定节点si)计算其离检测区域中心点的距离，再判断此距离位于哪个环内。对于n个环半径，依据检测是否满足式(7)，若满足，则意味着落在第k个环内，并将节点si称为属于第k个环的候选转发节点。

式中:α＝R/2表示任意两个圆环间的间隔。

如图3所示，图中黑色实心点表示候选转发节点。依据式(7)，网络的部分节点将被选举为候选转发节点。

图3 候选转发节点示例

构选了候选转发节点后，每个环上的候选转发节点再依据逆时针方向构建环，将环上的节点称为环上转发节点(FNR)。具体的实现过程如下:

第一步:在每个环上先随机选择一个候选转发节点，将其称为构环起点(Start)。

通过上述两步，最终构建环上的转发节点。如图4所示。图中的黑色三角形表示构环起点，采用逆时针，依据式(8)构建一个闭合的环。

图4 环上转发节点的选择

2.3 数据传输过程

2.3.1 数据收集节点

当节点感测数据Data后，节点先将数据传输至离其最近FNR，然后由FNR再构建连通Sink的路由，并利用此路由将数据Data传输至Sink。

为了让传感节点获取周边的FNR信息，每个FNR广播通告消息Nb_Mes[Ri，ID，＾si(＾x，＾y)]，其包含了FNR所在环数，ID号以及位置。

节点可能收到来自多个FNRs传输的Nb_Mes消息。在这种情况下，节点就计算离各FNRs的距离，并选择离自己最近的FNR作为自己转发数据的节点，将此FNR称为节点的数据收集节点(Data Collecting Node，DCN)。每个节点就将自己的感测数据传输至自己的DCN。

2.3.2 Sink实时位置的分享

FNR收到数据后，需要将数据传输至Sink。由于Sink是移动的，FNR需知晓Sink的实时位置。为此，Sink将自己的位置以及在此位置的停留时间在网络内进行通告，将此过程称为Sink实时位置的分享。

考虑到Sink所有位置的不同，Sink采用不同的方向传输其位置消息Sink_Mes〈Sink(x，y)，pause time〉。依据Sink在环内或者环外，将其位置分为三种情况:①Sink在所有环外，如图5(a)所示；②Sink在所有环内，如图5(b)所示；③在任意两个环之间，如图5(c)所示。

图5 移动Sink位置的分类

若Sink在所有环外，Sink就向区域中心点传输Sink_Mes；若Sink在所有环内，Sink就向背离中心点传输Sink_Mes。若Sink在两环之间，Sink就向区域中心点和背离中心点两个方向传输Sink_Mes。如图5所示。

FNDs收到Sink_Mes后，就从Sink_Mes中提取Sink位置，并将此位置与自己原来保存的Sink位置进行匹配。如果两个位置相同，就丢失此Sink_Mes。否则，FNDs就与邻居节点分享Sink_Mes消息。

?

当一个FND分别从逆时针和顺时针两方向所接收了同一个Sink_Mes时，FND不再向邻居节点传输Sink_Mes。此外，在传输Sink_Mes时，邻近的传感节点(非FND)也可能会收到Sink_Mes。由于传感节点无需获取Sink位置，传感节点直接丢弃Sink_Mes。

算法1描述了分享Sink实时位置的流程。其中d(Sink(x，y)，C(xc，yc))表示Sink离中心点的位置。

2.3.3 FNDs向Sink传输数据

RBHR采用文献[11]提出的基于角度路由传输数据。FNDs收到数据后，就从邻居的FNDs节点中选择与Sink具有最小角度的节点作为下一跳数据转发节点，重复上述过程，直到数据传输至Sink。

如图6所示，s1为数据源节点。s1先将数据Data传输至离其最近的FND(B1)。收到数据Data后，B1需要选择下一跳节点。由于B1有两个邻居节点(B2和B3)，B1就利用基于角度路由策略分别计算角∠B2CS和角∠B3CS。其中C表示中心点位置；S表示Sink(数据包的目的节点)。

图6 数据传输示例

由于∠B3CS小于∠B2CS，B1选择B3作为下一跳转发节点。即B1将数据Data传输至B3。重复上述过程，最终，将数据传输至Sink。

3 性能仿真

3.1 仿真参数

利用MATLAB软件建立仿真平台，分析RBHR路由性能。在400 m×400 m方形区域内均匀部署100至300个节点。Sink依据RWM模型移动，移动速度3 km/h~15 km/h。具体的仿真参数如表1所示。

表1 仿真参数

为了更好地分析RBHR路由的性能，选择文献[12]提出的RRP路由和文献[13]提出的GCRP路由作为参照，并分析它们的能耗性能和数据传输性能。

3.2 节点数对能耗和数据传输性能的影响

本次实验分析节点数对RBHR路由、RRP和GCRP算法的能耗和数据传输性能的影响。Sink的平均移动速度为9 km/h。

首先，分析节点数对总体的能耗影响，如图7所示。从图可知，总体能耗随节点数的增加而上升。这主要是因为:节点数越多，产生的数据包越多，加大了传感节点和FND传输数据任务，这就增加了它们的能耗。

图7 总体能耗随节点数的变化

相比于RBHR路由，RRP路由消耗了更多的能耗。原因在于:RRP路由在传输数据前需要获取Sink位置信息，这加大了通信开销；而RBHR路由中，传感节点无需获取Sink位置，只有FND节点需要获取Sink位置。FNDs节点收集了数据后，再依据角度路由向Sink传输数据。

此外，与RBHR路由相类似，GCRP路由是沿着循环链传输数据。然而，由于Sink在外围移动，使不位于边界上的节点需要消耗更多能量传输数据。

接下来，分析节点数对传输数据包的平均时延的影响，如图8所示。平均时延是指将数据包从源节点传输至Sink所消耗的平均时延。传输数据的路径，跳数以及参与路由的节点数对平均时延均有影响。

图8 节点数对传输数据包的平均时延的影响

从图8可知，节点数的增加使平均时延呈上升趋势。原因在于:节点数越多，源节点连通于Sink的跳数也随之增加。相比于RRP路由，RBHR路由减少了传输数据包的平均时延。这归功于:RBHR路由依据角度决策路由，缩短了数据传输路径。而在RRP路由中，每个源节点采用贪婪策略构建路由。这增加了数据传输时延。

数据包传递率也是衡量路由的数据传输性能的重要指标。图9给出了数据包传递率随节点数的变化情况。从图可知，节点数的增加使数据包传递率呈下降趋势。原因在于:节点数的增加，增加了网络拥塞的概率，降低了数据包传递率。

图9 数据包传递率随节点数的变化情况

相比于RRP路由和GCRP路由，RBHR路由的数据包传递率随节点数的增加下降缓慢。在RBHR路由中，利用FNDs向Sink传输数据。FNDs只占节点数一部分。只有这些FNDs需要获取Sink位置，减少了网络负担，降低了网络拥塞概率。

3.3 Sink的移动速度对能耗和数据传输性能的影响

本次实验分析Sink移动速度对能耗和数据传输性能的影响。节点为200个，Sink的移动速度从3 km/h至15 km/h变化。

首先，分析Sink移动速度对网络总体能耗的影响，如图10所示。从图可知Sink移动速度的增加，增加了网络总体能耗。原因在于:Sink移动速度越快，更新位置的频率越快，这增加了网络总体能耗。此外，Sink的快速移动，也增加了路由断裂的概率。一旦路由断裂，需要重新构建路由，这也增加了网络的能耗。

图10 总体能耗随Sink的移动速度的变化情况

在RBHR路由，GCRP路由和RRP路由中，RRP路由的能耗最高。原因在于:RRP路由采用单一环结构传输数据，源节点需获取Sink位置，这增加了节点能耗。而RBHR路由利用基于角度构建路由，减少了需要获取Sink位置的节点数，降低了网络开销。

接下来，分析Sink移动速度对传输数据包的平均时延的影响，如图11所示。从图可知，Sink移动速度的增加，提升了传输数据包的平均时延。Sink移动速度越快，更新Sink位置的频率越高，开销越大，网络拥塞概率越高。此外，移动速度越快，加速路由断裂的概率，增加传输数据包的平均时延。

图11 传输数据包平均时延随Sink移动速度的变化情况

相比于RRP路由和GCRP路由，RBHR路由具有较低的平均时延性能。原因在于:RBHR路由通过FNDs构建环，并利用角度策略缩短了数据包传输路径，缩短了传输时延。

最后，分析Sink移动速度对数据包传递率的影响，如图12所示。Sink移动速度越大，Sink将在较短的时间内穿越较大的网络空间，这可能缩短了Sink收集数据的时间。从图可知，相比于GCRP和RRP路由，提出的RBHR路由的数据包传递率得到较大提高，并且控制了其随Sink移动速度的增加而降低的速度。

图12 数据包传递率随Sink移动速度的变化情况

4 结束语

针对基于移动Sink的WSNs中的热点问题，提出基于环形的层次路由协议RBHR。RBHR通过限制更新Sink位置的节点数，降低开销，同时采用基于角度路由策略向Sink传输数据，缩短了数据传输路径。仿真结果表明，提出的RBHR路由有效地降低了能耗，并减少了数据传输时延。

本文只考虑了一个Sink场景。后期，将进一步优化路由策略，并考虑多个Sink协作收集网络内的数据的场景。这将是未来的研究内容。