基于簇的无线传感网络路由改进算法

侯爱霞

（重庆科创职业学院 信息与机电工程学院，重庆 402160）

基于簇的无线传感网络路由改进算法

侯爱霞

（重庆科创职业学院 信息与机电工程学院，重庆 402160）

环境危害、能量耗尽、设备故障等原因常导致传感节点错误，影响无线传感网络（WSNs）的应用性能，缩短无线传感网络寿命。为解决传感节点错误问题，提出面向容错的基于簇的分布式FTCD路由。在初始阶段，传感节点利用离簇头（CH）的距离、簇头离基站（BS）的距离及簇头的剩余能量信息选择自己的簇头；在数据路由阶段，簇头以最小化能量消耗方式选择下一跳簇头，并提出容错处理。仿真实验结果表明，FTCD路由能有效应对簇头错误，提高了能量利用率，使其多方面的性能都得到显著提高。

WSNs；FTCD；CH；传感节点

1 问题的提出

无线传感网络（W ireless Sensor Network，简称WSNs）被广泛应用于环境监测、战场勘察、健康医疗等各类行业及灾难管理[1]。目前，传感节点能量的有限性及不可替换性是阻碍WSNs应用发展的重要因素[2]，因而降低传感节点能量消耗，提高能量利用率被认为是WSNs应用的关键。为此，设计有效的能量协议，包括低功耗的通信硬件、能量感知MAC协议等，其中基于能量有效的簇化路由算法被认为是WSNs最有前景的技术[3]。

基于簇化的WSNs网络模型如图1所示。

图1 基于簇化的WSNs网络模型

传感节点被划分为不同的群，称为簇。每个簇有一个簇头（CH），每个传感节点仅属于一个簇[4]。簇化的WSNs有以下优势：一是CH接收簇内成员的感测数据并进行融合，摒弃冗余数据后，再向基站（BS）传输，降低了传感节点的能量消耗。二是由CHs构建数据传输主线，更容易管理路由，同时也提高了网络的扩展性和重要性。但簇化的WSNs中CH承担了更多的任务，如从传感节点接收数据并进行融合，向基站传输。繁重的任务加快了CH的能量消耗，缩短了CH的工作寿命。一旦能量耗尽，CH就不能正常工作，本文将此类节点称为传感节点错误。CH承担了数据收集、融合、传输的多项任务，一旦CH错误，WSNs的数据传输将中断，从而降低WSNs的应用性能[5]。此外，由于环境干扰、能量耗尽及设备故障等因素，也会导致传感节点错误，影响WSNs的应用性能，缩短WSNs工作寿命。但相较而言，CH错误的危害更为严重。因此，为了确保WSNs的应用性能，在设计路由协议时，必须考虑CH及传感节点错误，即路由具有容错性[6]。

基于簇化的路由算法有集中式和分布式，广泛应用于WSNs。集中式路由算法由BS执行，需要掌握网络拓扑的全局信息，并将路由信息发送至CH；分布式路由算法依据局部信息进行路由决策。EELBC（Energy Efficient Load-Balanced Clustering）算法强调能量利用率和负担开销的平衡[7]，但该算法是假定BS已知每个传感节点和CH位置为前提。此外，这些算法并没有考虑CH错误问题。EECS（Energy-Efficient Clustering Scheme）协议在CH选择过程中，不仅考虑了传感节点的剩余能量，还考虑了离信宿的距离，提高了簇分布的均匀性[8]，但该协议并没有考虑传感节点能量消耗速率情况。DEBR（Distributed Energy Balance Routing）路由平衡网络的能量消耗，但该路由没有考虑CH错误问题。MHRM（M inimum Hop Routing Model）每个转发节点以最短的通信跳数建立离BS的路径，因而转发节点总是选择离自己远的一跳邻居节点作为下一跳的转发节点，这将消耗大量的能量[9]。FTCA（Fault Tolerant Clustering Algorithm）算法考虑CH错误问题，但其路由性能差，并没有考虑传感节点的能量消耗问题。

本文提出FTCD（Fault Tolerant Clustering-based Distributed）路由，重点考虑CH错误，分为初始阶段和数据处理阶段。初始阶段进行网络簇化，每个传感节点依据增益函数为自己选择一个CH，增益函数融合了离CH的距离、CH的剩余能量及CH离BS的距离信息；数据处理阶段，CH以平衡能量消耗的角度选择下一跳CH，通过这种分布式路由向BS传输数据。

2 系统模型及定义

考虑N个传感节点Si, i=1, 2, …, N，随机分布于WSNs。有m个chk, k=1, 2, …, m。一旦部署后，传感节点不再移动，即传感节点是静态的。为了后续描述简单，定义以下变量：

（1）传感节点集S={s1, s2, …, sN}。

（2）CH集C={ch1, ch2, …, chm}。

（3）CH的最大通信范围Rch，传感节点的通信范围Rs。

（4）传感节点si与sj间的距离d (si, sj)。

（5）传感节点si的剩余能量EResidual(si)。

（6）传感节点si覆盖的CH集ComCH (si)：在传感节点si的通信范围内所有的CH，即：

（7）传感节点si的邻居集Nei(si)：在传感节点si的通信范围内所有的传感节点，即：

（8）chk的邻居集Com(chk)：在chk的通信范围内所有的CH，即：

（9）chk离BS的跳数HCou(chk)：如果chk能与BS直接通信，则HCou(chk)=1。

（10）chk后向Bch(chk)：在chk通信范围内，并且离BS的跳数大于chk离BS的跳数，则：

（11）被CH覆盖的传感节点集CO：若在传感节点si的通信范围内，至少存在一个CH，那么si属于传感节点集CO；若在传感节点si的通信范围内，不存在CH，那么si属于非传感节点集UnCO，则：

（12）非传感节点集内的传感节点si的支持节点集Baup (si)：当si∈UnCO，si的邻居节点可作为连接CH的中间节点。这些中间节点集称为si的支持节点集Baup (si)，即：

（13）活动节点和失效节点：有能量将感测数据以直接或间接方式传输至CH，称为活动节点；将不能与CH通信的节点称为失效节点[10]。

3 FTCD协议

BS, CH及传感节点是FTCD协议内的三个通信实体。BS周期地广播HELLO消息，通过接收信号强度判断CH离BS的距离。FTCD协议主要分为初始阶段和数据处理阶段。初始阶段形成不同的簇；数据处理阶段主要进行数据感测、传输。将数据处理阶段划分为多个固定时隙回合（Round），在每一个回合中，CH接收簇成员感测的数据并进行融合，再利用分布式路由算法传输至BS，如图2所示。

图2 FTCD协议网络模型

3.1 初始阶段

在初始阶段，CH周期地向邻居区域广播HELLO消息，包含CH的ID、剩余能量及离BS的距离信息。若传感节点si能收到HELLO消息，则可能收到多条HELLO消息，只要能收到1条HELLO消息，则表明传感节点si至少被一个CH所覆盖，即si∈CO；若在规定的一段时间内没有收到HELLO消息，则表明传感节点si未被任何一个CH覆盖，即si∈UnCO。

（1）若si∈CO，si可能收到多条HELLO消息，表明si在多个CH覆盖区域内。在这种环境下，si必须选择一个CH作为它的领导者。在选择过程中，需要考虑CH的剩余能量、离CH的距离及CH离BS的距离信息，融合为一个指标CHco (si, chr)，即：

其中，si选择chr作为CH的增益值，且chr∈ComCH (si)。

再从中择优选择具有最大增益值的CH，即：

一旦选择了CH，就向其发送JOIN_REQ消息；收到消息后，CH将该传感节点作为自己的成员。

（2）若si∈UnCO，si未被任何一个CH覆盖。在这种环境下，si广播HELLO消息寻求支持，si便从Baup (si)（见（6）式）集中找到一个节点作为连接CH的中间转发节点。若Baup (si)≠φ，就从中选择一个传感节点作为连接CH的中间节点。在选择过程中，着重考虑传感节点的能量，即选择剩余能量最大的节点，即：

依据上述分析，初始阶段中簇的形成算法流程如图3所示。

图3 簇的形成算法流程

3.2 数据处理阶段

CH构成网络传输主线，在选择下一跳转发节点时，充分考虑CH的能量、距离及离BS的跳数信息。为此，建立增益函数Cost (chi, chk)，表示chi选择chk作为下一跳的增益，即：

chi选择具有最大增益及离BS的跳数更小的CH作为下一跳的转发节点，即：

3.3 容错性分析

在数据处理阶段，由于能量耗尽等原因，CH可能失效。一旦检测到失效的CH，该CH的成员节点就广播HELP消息。假定传感节点si广播HELP消息，来自chk内的成员节点sj接收此消息，且chk∈ComCH(si)，sj∈Nei (si)，并回复RELP消息。若传感节点si收到来自sj发送的RELP消息，则si∈CO，并更新Baup (si)，否则si∈UnCO。容错处理算法流程如图4所示。

图4 容错处理算法流程

4 仿真实验

利用MATLAB R2012b建立仿真平台。在400m× 400m的方形区域，BS位于区域中心（200m×200m），其中，传感节点N=400，CH中m=40。每个传感节点的初始能量为2J，通信半径Rs=60m；CH的初始能量为10J，通信半径Rch=100m。每次实验重复100次，取平均值作为最终数据。为了更充分地分析路由性能，选择容错簇算法FTCA和分布式算法DEBR和MHRM进行仿真实验比较，结果如图5～图7所示。

4.1 错误的CH数及BS接收的数据包

由图5可知，在整个网络有效期内，FTCD路由错误的CH数少于DEBR, FTCA, MHRM路由的CH数。在FTCA路由中，CH直接与BS直接通信频繁，导致能量消耗过快。在DERB路由中，为了平衡CH能量消耗，可能选择与BS反方向的CH作为转发数据的CH，可能使数据最终不能传输到BS，浪费了能量。在MHRM路由中，为了限制跳数，离BS最远的CH作为下一跳转发节点，致使CH因长距离传输而能量消耗过快。在FTCD路由中，在选择下一跳转发节点时融合了能量、距离信息，并且具有容错性，一旦CH错误，FTCD路由能寻找另一个CH进行数据传输。FTCD路由的BS可接收更多的数据包，优于DEBR, FTCA, MHRM路由，由此进一步验证了FTCD路由性能的优越性。

4.2 总体能量消耗和平均能量消耗

由图6可知，尽管四个路由的总体能量消耗曲线走势相同，但提出的FTCD路由略优于DEBR, FTCA, MHRM，但随着Round的增加，优势减弱。究其原因在于FTCD路由中BS接收了更多的数据包。

4.3 CH剩余能量的标准偏差和错误的传感节点数

图5 错误的CH数及BS接收的数据包

图6 总体能量消耗及每接收一个数据包的平均能量消耗

由图7可知，FTCD路由的标准偏差曲线变化平衡，波动小，且小于DEBR, FTCA, MHRM路由的标准偏差，充分说明FTCD路由的能量消耗更平衡。此外，还可比较四个路由错误的传感节点数。如果传感节点的剩余能量不为零，且至少一个CH在其通信范围内，这样的传感节点被认为是正常的传感节点，否则被认为是错误的传感节点。FTCD路由错误的传感节点数少于DEBR, FTCA, MHRM路由错误的传感节点数，且随Round的增加而增加的步伐减缓。这主要是因为FTCD路由考虑了传感节点的能量消息。

图7 CH剩余能量的标准偏差及错误的传感节点数

5 结 论

针对无线传感网络数据传输问题，提出FTCD路由。FTCD路由引用簇化的分布式路由理念，充分考虑了簇头错误情况，初始阶段簇头先广播HELLO消息，传感节点计算选择不同簇头的增益，提出容错处理算法。仿真实验结果表明，FTCD路由能有效应对簇头错误，提高了能量利用率。下一步将研究基于簇的路由机制，将其拓展至任何一个分布式路由协议，进而提高路由协议的性能。

[1] 杨明霞，王万良，马晨明.面向节能和容错的异构WSNs数据收集算法[J].传感技术学报，2016（6）：934-940.

[2] M ISRA S，KRISHNA P V，SARITHA V.LACAV：an Energy-Ef f cient Channel Assignment Mechanism for Vehicular ad Hoc Networks[J]. The Journal of Supercomputing，2012（3）：1241-1262.

[3] 王莘.一种无线传感网络节能分簇算法[J].电子测试，2014（5）：50-52.

[4] 沈艳霞，薛小松.无线传感网络移动信标节点路径优化策略[J].传感器与微系统，2012（12）：42-44.

[5] 归奕红.无线传感器网络HEDSA数据聚合研究[J].计算机工程，2011（7）：160-162.

[6] 周磊，董乃铭，洪振杰.UKF算法与SVDKF算法性能的比较[J].温州职业技术学院学报，2013（1）：81-83.

[7] KUILA P，JANA P K.Energy Ef f cient Load-balanced Clustering A lgorithm for W ireless Sensor Network[J].Procedia Technology，2012（4）：771-777.

[8] 罗四维，侯孟书，周益民.一种新的基于能量消耗速率模型的分簇路由协议[J].计算机科学，2012（6）：47-50.

[9] CHIANG S S，HUANG C H，CHANG K C. A M inimum Hop Routing Protocol for Home Security Systems Using Wireless Sensor Networks[J]. IEEE Transactions on Consumer Electronics，2007（4）：1483-1489.

[10] BANERJEE I，CHANAK P，RAHAMAN H A，et al.Effective Fault Detection and Routing Scheme for Wireless Sensor Networks[J]. Computers & Electrical Engineering，2014（2）：291-306.

[责任编辑：田启明]

Cluster-based Routing Algorithm for W ireless Sensor Networks

HOU Aixia
(School of Mechanic and Electronic Engineering, Chongqing Creation Vocational College, Chongqing, 402160, China)

Sensor nodes are very prone to failure due to several factors such as environmental hazards, energy depletion and device failure, which affects the application performance of WSNs and the overall network lifetime. In order to solve the problem of sensor node failure, the paper proposes a fault-tolerant and clustering-based distributed (FTCD) rouging in WSNs. In the clustering phase, sensor nodes select its CH on the basis of the distance between sensor node and the CH, the distance from the CH to the base station, and the residual energy of the CH. In data routing phase, the CHs select their next hop neighbor CH in such a way that their energy consumption w ill be balanced and minimized. The simulation experiment shows that the FTCD roughing can cope w ith the sensor node failure effectively, and increase the energy ef f ciency so as to improve the performance in various other aspects.

WSNs; FTCD; CH; Sensor nodes

TN929.5; TP212.9

A

1671-4326 (2017) 02-0051-05

DO I: 10.13669/j.cnki.33-1276/z.2017.034

2016-12-28

侯爱霞（1981—），女，湖北襄阳人，重庆科创职业学院信息与机电工程学院讲师，硕士.