一种适用于多基站环境的WSN分簇路由协议

潘琢金 陈天毅 王传云 杨 华

(沈阳航空航天大学计算机学院 辽宁 沈阳 110136)

0 引 言

由于构成无线传感器网络(WSN)的节点通常由电池供电,能量有限,因此节能是路由算法设计中的一个关键点。大部分有关无线传感器网络路由协议的研究设定的应用场景都是单基站环境。事实上,有很多的应用场景如森林火灾检测,需要多基站确保网络的连通,出于保护基站的目的或由于基站不易部署等原因,基站需要放在待检测区域的外围。

针对单基站部署于网络外的场景,文献[1]提出让靠近基站的簇更小,从而为这些簇头留出更多的能量用于簇间转发,很好地平衡了节点的能量消耗,但该协议不适用于多基站环境。针对多基站部署于网络内的场景,文献[2]采用相遇蚁群算法获得了更快的路由收敛速度,但其网络拓扑是平面网状的结构,一是难以避免热点问题,二是路由的寻找与维护依然十分复杂。文献[3]利用Q学习算法一定程度上避免了使用剩余能量少的节点做转发。文献[4]针对基站随机部署的场景进行研究,通过动态调整簇半径优化能耗。针对多基站部署在网络外的场景,文献[5]设计了考虑QoS的路由协议MSO-ETSSEP并仿真证实了多基站比单基站在延长网络寿命方面更有优势,但其网络模型中需要包含具有更高能量的节点。文献[6]的协议使用考虑路径能耗、路径最小剩余能量以及节点到基站跳数的簇间多跳转发来节省能量,延长了网络的使用寿命,但需要节点能够记录所有其他节点的位置和能量以便寻找路径和维护路由表,增加了协议的复杂度,且在每轮开始前所有节点向基站传输剩余能量会消耗较多的能量。文献[7]在节点上使用三扇区天线,仅利用节点的大概位置选择路由,避免了与查找定位信息相关的复杂计算,且算法可用于移动的WSN网络。分簇路由协议由于其节点能耗均衡且可扩展性好被广泛使用[8]。尽管LEACH协议[9]最初是为单基站部署于网络中心的应用场景设计的,但其思路依然可以用在多基站部署于检测区域外的场景下。文献[10]在考虑节点剩余能量的同时优化簇头数量,与LEACH算法相比降低了节点功耗。文献[11]基于改进Bayes估计的数据融合节点选取方法一定程度上实现了节点能耗均衡,提高了数据传输正确率。文献[12]提出了一种基于能量质心的分簇路由协议EECRP,当基站位于网络中时,其效果优于LEACH、LEACH-C[13]和GEEC[14]。大部分LEACH协议的改进版本都对阈值函数进行修改,目的是在选簇头时考虑到节点的位置和剩余能量,从而让簇头选择结果更加合理,但这些协议仍然基于节点每轮生成一个随机数与阈值函数进行比较的方法让节点自选举出簇头,这种方法每轮选出的簇头数量波动较大。

针对以上问题,结合多基站部署于网络外围的场景特征,本文提出一种适用于多基站环境的带有中转节点的分簇路由协议MSCRR(Multi-Sink Clustering Routing Protocol with Relay Nodes),使用一种新的簇头自选举方法来保证一轮中簇头个数的稳定,通过优先选择簇内质心位置剩余能量高的节点做簇头,并让网络边缘节点协助簇头转发消息至基站,以此来平衡节点的能耗,减轻簇头的负担,降低网络的总能耗,延长网络的使用寿命。

1 网络模型

1.1 网络拓扑

1.2 能耗模型

对于实验中节点能耗的计算,使用文献[9]中提到的如图1所示的一阶无线电模型。所有节点初始能量相同且同时开始工作。Eelec是发射机和接收机所需的能量,εamp是发射放大器所需的能量,Ecomp是数据融合需要的能量。

图1 一阶无线电模型

向距离d的位置发送k比特数据消耗的能量见式(1),接收k比特数据消耗的能量见式(2),对k比特消息做数据融合消耗的能量见式(3)。

ETx(k,d)=Eelec×k+εamp×k×d2

(1)

ERx(k)=Eelec×k

(2)

EC(k)=Ecomp×k

(3)

1.3 实验假设

该协议的仿真运行需满足以下假设:

1) 所有节点需周期性地采集并汇报数据;

2) 节点最大通信半径为正方形区域对角线长;

3) 节点最大通信半径内至少有一个基站;

4) 所有节点以及基站的时间都是同步的;

5) 节点已知自己的精确位置,且位置不变;

6) 未入簇的节点需直接向基站发送数据消息。

2 算 法

数据传输的路由过程按轮进行,一轮分为两个阶段:成簇阶段和传输阶段。为减少通信次数,算法由时间驱动,所有节点会按照事先制定好的时间表完成相应的任务,无须与其他节点或基站协商。每一轮的时长固定,该时长的选取需确保所有节点均能完成一轮内的数据传输任务。

2.1 成簇阶段

1) 簇头自选举。n是节点编号,N是网络中的节点个数,P是网络内所有节点中簇头的比例,r是当前轮数,其中n和r从0开始。当以上参数满足式(4)时,该节点自选举为簇头。

(4)

2) 簇头选择优化。由于自选举得到的簇头未必合理,需要进行优化,优化的思路是优先选择簇内靠近质心且剩余能量更高的节点。原簇头将每个节点与簇内其他节点的距离平方的和Sdist以及该节点的已消耗能量Eu组成pair〈Sdist,Eu〉,其中Sdist按照式(5)计算,Nc为簇内节点个数,节点自己的坐标为(X,Y),簇内其他节点的坐标为(Xi,Yi)。根据Sdist和Eu的值对pair〈Sdist,Eu〉按从小到大排序,规定若x1

(5)

3) 中转节点选择。选择中转节点的过程依然由原簇头完成。若新簇头将消息发送给中转节点,再由中转节点转发至基站预期产生的总能耗小于簇头直接发送给基站所需的能耗,则应选择中转节点。即:

[Eelec+εamp×(d1+d2)2]>

[3Eelec+εamp×(d12+d22)]

(6)

式(6)可化简为:

εampd1d2-Eelec>0

(7)

式中:d1是新簇头到候选中转节点的距离,d2是候选中转节点到基站的距离。若存在多个候选中转节点,由式(7),可为每个中转节点设定如式(8)的评分函数,选取分数最高的节点作为本轮的中转节点。为防止与基站接近的节点因总是成为中转节点而过快失效,剩余能量低于20%的节点不参与中转节点竞选。

SCORE=εampd1d2-Eelec

(8)

2.2 传输阶段

节点按TDMA发送数据给簇头。簇内若存在中转节点,则簇头将消息发送给中转节点,否则,簇头、中转节点和孤立节点按TDMA将数据消息发送给离自己最近的基站。

2.3 运行流程

使用MSCRR路由算法进行一轮数据收集的具体步骤如下:

1) 所有节点根据式(4)完成自选举,选为簇头的节点广播公告消息ADV_CH,告知邻居节点它们是簇头。

2) 当所有ADV_CH消息都到达目标节点时,非簇头节点根据ADV_CH消息选最近的簇头,发送JOIN_CH消息,需包含自己的位置信息和剩余能量。若节点未收到ADV_CH消息,则成为孤立节点,本轮不入簇,直接与基站通信。

3) 当所有JOIN_CH消息到达目标簇头时,簇头收到入簇申请并暂时保存;基站广播公告信息,告知所有节点它们的编号和位置。

4) 所有ADV_BS消息到达后,簇头根据JOIN_CH消息按照2.1节(2)中的方法寻找簇内是否有更适合成为簇头的节点,若有则寻找最适合的一个令其在本轮担任新簇头,将其编号附加进SCHED_CH消息;簇头接着按照2.1节(3)中的方法寻找簇内是否有适合为簇头做中转的节点,若有则寻找最合适的一个,并将其编号附加进SCHED_CH;簇头广播SCHED_CH给簇内节点。

5) 当簇内所有节点收到SCHED_CH消息后,节点检查自己是否为新簇头或中转节点。如果是新簇头则准备接收来自簇内的数据消息,如果是中转节点则准备接收来自簇头的数据消息。没有中转节点的簇头、中转节点、孤立节点将直连基站。需要直连基站的节点选择最近的基站发送JOIN_BS。

6) 所有JOIN_BS消息到达基站时,基站发出SCHED_BS。

7) 所有SCHED_BS消息到达节点时,普通节点开始按TDMA向簇头发送DATA。

8) 簇头收齐DATA消息后做数据融合,有中转节点的簇头发消息给中转节点。

9) 所有中转消息到达中转节点后,没有中转节点的簇头、中转节点、孤立节点开始按TDMA发送消息到基站。

10) 若一轮只发一次数据,则该轮结束,否则,继续传输数据直到一轮的时间结束。接着,重复以上步骤,直到所有节点失效。

协议运行需要的消息类型如表1所示。

表1 协议运行需要的消息类型

图2是MSCRR路由协议运行效果的示意图。

3 仿真实验

3.1 仿真参数

表2 仿真参数

大部分与LEACH相似的路由算法使用的簇头占总节点数的比例P的值是0.05,因为通过实验证明单基站条件下P为0.05时网络的总能耗最小。但在基站的位置改变、基站数量增加,以及簇头广播覆盖范围改变后,P的值需要重新确定。通过仿真实验发现,三种算法无论哪一种,前200轮内都不会出现节点失效的情况,因此每种算法通过100次随机实验,每次节点都随机且均匀地布撒在正方形区域内,测试前200轮所有节点的总能量消耗的平均值,结果如图3所示。可见,当P值选取为0.15时,总能耗最低。

图3 簇头所占比例与能耗的关系

3.2 仿真结果

图4显示了其中一次实验中LEACH协议经典的簇头自选举方法与本文中的簇头自选举算法每轮选出的簇头数的对比。LEACH每轮选出的簇头数不同,波动较大,当簇头比例较小时甚至会出现无法选出簇头的情况,有节点失效后,未选出簇头的概率会增加。若一轮中选不出簇头,则所有节点需要直接与基站通信,这会导致大量的能量浪费。选出过多的簇头则会导致部分簇头建立的簇没有节点加入,该簇头仍需直接与基站通信,造成不必要的能量浪费。本文算法可保证有节点失效前,选出的簇头个数固定为NP,有节点失效后,选不出簇头的次数也较少。

图4 不同协议每轮选出的簇头数

为消除单次实验的偶然性,以下所有实验的结果均来自100次随机实验的平均值,每次实验节点随机且均匀地布撒在指定的正方形区域中,每一轮只收集一次数据。

图5显示了100次实验每轮结束后网络中剩余节点数的均值与运行轮数的关系。表3显示了网络中1%、25%、50%、75%的节点失效在100次实验中最早出现的轮数,当更多的节点失效时,大面积的区域将无法被检测,此时网络变得几乎不可用,故不再讨论,此时应该向网络中补充新的节点。从实验结果可以看出,EECRP和MSCRR算法都有效地增加了1%、25%、50%、75%节点失效时的轮数,有效地延长了网络寿命,本文算法MSCRR表现更优。由于EECRP协议存在保护机制,即当一轮中某簇头与目标基站距离大于一定值时,该簇头将暂存数据不发,直到加入其他簇,该机制虽然能够节省能量但会引发暂时的丢包,尤其是在网络中剩余节点较少的情况下,而本文算法要求数据消息必须发送至基站,非节点或基站失效等特殊情况下,不存在丢包现象。

表3 节点失效所经历的轮数

图5 剩余节点数与运行轮数的关系

4 结 语

本文算法使用优先选择靠近簇内质心位置的高能量节点做簇头的方法以及中转节点机制,相比传统算法有效地降低了网络中的平均通信距离,进而降低了由通信产生的能耗;使用周期性轮换的簇头自选举方法有效地控制了网络中的簇头数量,避免了由于簇头过多或过少造成额外的能量浪费,且无须基站进行集中调度,减少了因集中调度产生的能量开销。同时,多基站的部署以及中转节点的机制也可让网络的覆盖面积更大,并可应对部分基站失效的情况,使网络的鲁棒性更好。本文算法采用节点自选举的方式产生簇头,成簇阶段不依赖基站,该方法可改为由基站集中控制的算法。集中控制的算法会在节点发送给基站自身的位置和能量等附加信息以及接收来自基站的控制报文上消耗更多的能量,但基站可以从全局考虑做出更合理的分簇方案,并为节点提前规划合适的路由,这是未来进一步研究的方向之一。