无线传感器网络多跳路由协议研究

袁耀东,许红艳

(郑州澍青医学高等专科学校 卫生管理系，郑州 450064)

无线传感器网络多跳路由协议研究

袁耀东,许红艳

(郑州澍青医学高等专科学校 卫生管理系，郑州 450064)

无线传感器网络发展迅速，但传感器的高能耗问题成为制约其发展的主要瓶颈，高效节能的路由协议设计成为研究热点;针对目前无线传感器网络常用的LEACH路由协议存在的簇首能耗过分集中、簇首分布不均衡问题，提出了改进的路由协议EEACRA，在总结、分析LEACH路由协议现有问题的基础上，给出了EEACRA路由协议的簇首选取门限值、簇首位置调整算法和基于能量代价最小的簇间多跳路由算法的实现方法，同时给出了具体的实现EEACRA协议的工作流程和关键算法；在MATLAB环境下对LEACH路由协议和EEACRA路由协议进行了仿真，对比了不同能耗降低措施对网络能耗降低的贡献;仿真结果表明EEACRA路由协议的网络稳定期较LEACH路由协议有较大的改善;证明了改进的路由协议EEACRA可以有效地提高网络的稳定期。

无线传感器网络;网络体系结构;路由协议;分簇算法;LEACH协议

0 引言

近年来，无线传感器网络得到了快速发展，但能耗问题一直是无线传感器网络[1]发展的瓶颈，因此高效节能的路由协议设计就显得至关重要。针对常用的LEACH路由协议进行改进的LEACH-C路由协议[2-3]能够优化簇首分布，但在每轮簇首选举前都必须知道全网的剩余能量；而自组织协议SOA能够适应网络拓扑变化，并通过调整发射功率与其距离最近的节点进行通信，有效地减少了能量开销，但其对路由节点的运算能力、存储空间和定位能力要求过高。

针对上述问题，提出了改进的路由协议EEACRA。通过把能量判决门限和能量因子引入簇首选举概率阈值中，使能量较多的节点被选举为簇首的概率增加[4-5]；同时将延时机制引入簇首广播阶段，降低簇首广播阶段报文传送发生碰撞冲突的可能性；最后通过基于能量代价最小的簇间多跳路由算法将信息发送至基站，有效的降低了网络能耗并延长了网络的生存时间。

1 EEACRA协议网络体系及能耗模型

1.1 EEACRA协议网络体系

EEACRA协议是分层路由协议，采用分布式自举成簇算法[6-7]，在逻辑上将整个网络划分为汇聚节点，簇首节点成员节点三层，具体如图1所示。

图1 EEACRA协议网络体系结构模型

在数据传送过程中，各簇首节点通过多跳方式选取最优路由线路将数据传送至汇聚节点。簇首节点主要负责成员节点的管理和时隙分配，同时将接收到的成员节点数据进行融合后发送至汇聚节点；成员节点主要负责周围环境信息的采集和将采集到的信息发送至簇首节点；汇聚节点主要负责与外围网络进行通信，将采集到的数据传送至客户端。

1.2 EEACRA协议能耗模型

LEACH路由协议的能耗模型如图2所示。

图2 路由协议能耗框图

出现发送节点和信息接收节点之间距相近的情况时，根据无线电自由空间传播模型，信号功率与距离的2次方成反比，接收功率如式(1)所示：

(1)

出现发送节点和信息接收节点之间距相远的情况时，根据双线地面反射传播模型，信号功率与距离的4次方成反比，接收功率如式(2)所示：

(2)

在式(1)、式(2)中，Pt表示发射功率，Gt表示发射天线增益，Gr表示接收天线增益，λ表示波长，L表示系统损耗因子，hr表示接收天线高度，ht表示发射天线高度，d表示收发节点间距。

为研究问题方便，分别用近距离功率衰减系数和远距离功率衰减系数εfs和εmp代替式(2)、式(3)中与收发节点间距d无关的量。故传感器节点向间距d处的节点发送l bits数据的能耗如式(3)所示：

(3)

式(3)中，Eelec为节点接收或发送单位bit数据的能耗。

无线电波传送的分界参考距离d0如式(4)所示：

(4)

传感器节点接收lbit数据的能耗如式(5)所示：

ERx(l)=Eelec×l

(5)

簇首融合n个传感器节点数据的能耗如式(6)所示：

E(l,n)=EDA×l×n

(6)

式(6)中，EDA为融合单位bit数据的能耗。

2 EEACRA协议实现

2.1 簇首选取门限的确定

根据文献[8]的分析可知，LEACH路由协议无法避免能量较小的节点被选举为簇首，也无法保证各轮簇首选举过程中簇首数目能够达到最优值；而当网络中有节点的能量耗尽时，簇首数目最优值也无法进行相应的调整[9]。

为解决上述问题，提出新的簇首选举门限。不妨设网络初始化时的节点数目为N0，在初始化时经统计得出网络能耗最低时的簇首数目为kep，则网络能耗最低时的簇首比例为kep/N0。但随着网络节点能量的消耗，部分节点变为无效节点，整个网络能耗最低时的簇首个数kep会发生变化，簇首选举概率如式(7)所示：

(7)

从式(7)中可以看出，随着网络有效节点数量的减少，簇首选举概率与网络中存活的节点数目N的平方根成反比，与网络初始化时节点数目N0的平方根成正比[10-11]。

为加大剩余能量较高的节点被选举为簇首的概率。在考虑节点剩余能量和优化簇首选举门限的基础上，再引入网络中当前存活的节点数目对网络能耗最低时簇首比例的影响，同时在门限值T(n)中引入簇首选举概率Pep，则EEACRA路由协议的簇首选举公式如式(8)所示：

Tep(n)=

(8)

式(8)中，Pep表示当前轮节点n被选举为簇首的概率，En_cur表示节点n的当前剩余能量，Ech_av(r-1)表示上一轮所有簇首剩余能量的平均值，r表示当前轮次，σ表示修正系数。

2.2 簇首位置调整算法

EEACRA路由协议最佳簇首的个数用kep表示，在传感器节点均匀分布的情况下，各簇首间距的期望值如式(9)所示：

(9)

式中，c表示满足网络任务覆盖要求所需的常数，S表示网络覆盖的总面积，kep表示簇首个数均值。

为解决每轮选举过程中，各簇首距离过近引起的簇首广播阶段报文传送发生碰撞冲突的概率，需要对各簇首位置进行调整[11-12]。具体方法如下：

1)当节点通过门限值确定可以成为簇首后，并不立刻进行簇首声明的广播，先根据上轮所有簇首的能量均值和节点自身的剩余能量设定一个定时器t(n)，节点自身剩余的能量越多，设定的定时时间就越短；

2)如果在到达定时器的定时时间之前接收到其它节点的簇首声明的广播，则先判断其与簇首声明节点的距离，如果间距小于分界距离d0，则该节点直接加入簇首，成为其成员节点；否则广播簇首声明，声明自己为簇首。

定时器的定时时间与节点自身剩余能量的关系如式(10)所示：

0

(10)

式中，ε表示时间调整系数，En_cur表示节点n的当前剩余能量，Ech_av(r-1)表示上一轮所有簇首剩余能量的平均值。从式中可以看出，t(n)的大小由节点当前的剩余能量决定，因此，各节点通过定时器得到的广播时延一般不同，由此可见，引入t(n)可以调整簇首位置，同时也能够降低信道冲突的概率。但EEACRA路由协议的簇首位置调整算法将部分簇首节点重置为普通节点，这就使网络最优簇首数目的期望值偏离了预设的簇首优化值kep，因此必须通过修正系数σ修正簇首选取公式。

2.3 基于能量代价最小的簇间多跳路由算法

2.3.1 算法概述

簇首节点需要处理接收到的成员节点数据并将融合后的数据发送至汇聚节点的双重任务。因此，当簇首与汇聚节点的间距较大时，为减小簇首节点能耗，应采用多跳路由算法，但多跳路径很多，EEACRA路由协议使用能量代价最小的多跳路由算法来均衡簇首能耗，具体算法如下：

1)在成簇期间，汇聚节点向整个网络周期性的广播包含发射功率、时钟同步等信息的控制报文，各簇首依据发射功率和RSSI值估算其与汇聚节点的间距，然后通过式3计算其到汇聚节点的通信能耗，并将其作为初始路径代价在簇首广播中声明。

2)各簇首在接收到其它簇首广播后，比较自身的原路径代价和通过广播簇首为中继节点的路径代价，如果自身的原路径代价大于通过广播簇首为中继节点的路径代价，则对该节点的中继节点和路径代价进行更新，同时在备用的中继路由信息库中保存原中继节点和路径代价，随后簇首向全网广播更新后的路径代价[13-14]。

2.3.2 最优中继簇首的选择

研究表明传感器节点的主要能耗来源是无线通信模块，其中空闲能耗与接收能耗基本持平，约为发送能耗的75%。在选择最优中继簇首的过程中，EEACRA路由协议考虑了中继簇首发送和接收数据两方面的能耗。最优中继簇首选择的的过程如下：

1)初始路径代价的计算。各簇首先估算其到汇聚节点的通信距离dto_Sink，然后根据式3计算出自身与汇聚节点直接进行通信的能耗，记为初始路径代价Cost0(CHi)，其计算公式如式(11)所示：

(11)

2)更新路径代价的计算。各簇首在接收到其它簇首的广播后，通过估算其与其它簇首的间距来计算以其它簇首作为中继节点的路径代价，如果中继路径代价比簇首的初始路径代价低，则以中继路径代价作为簇首的路径代价。但在网络中可能存在若干个小于簇首初始路径代价的中继节点，簇首默认的中继节点为路径代价最小的中继节点，并在随后的广播中声明该路径代价为簇首的路径代价[15]。

簇首i以簇首j作为其中继节点时的路径代价如式12所示：

(12)

2.3.3 路由维护

网络每轮簇首选举开始时，成簇阶段建立的簇间多跳路由关系都要重新建立，因此无需对路由表进行专门的维护。在各轮数据传送过程中，如果簇首默认的中继节点不能正常进行中继，则选取次优中继节点完成数据传送；如果全部中继节点都无法进行正常中继，则簇首与汇聚节点直接进行数据传送。因此EEACRA路由协议的多跳算法对于网络应用是稳定可靠的，不会存在数据无法传送的情况。

2.4 EEACRA协议工作流程

EEACRA路由协议为分簇层次型路由协议，采用簇首轮换的方式来均衡网络各节点的能耗，每轮簇首轮换过程由组网和数据传输两个阶段组成。EEACRA路由协议的工作流程框图如图3所示。

图3 EEACRA路由协议工作框图

2.4.1 组网阶段

组网初始化：首先复位各节点状态，然后汇聚节点向全网周期性地广播Beacon信息，信息的主要内容包括网络初始化时的节点数N0，本轮组网前存活的节点数N，本轮簇首选举概率Pep，上轮簇首能量均值Ech_av(r-1)，修正系数σ，距离分界值d0、发射功率和时间同步等信息。

产生准簇首：各节点随机生成一个0到l之间的数，如果生成的随机数小于式8中的门限值T(n)，则自举该节点为准簇首。

产生簇首：各簇首通过式11计算自身的初始路径代价，然后按式10计算自身的定时时间同时启动定时器。到达定时时间时，向全网广播簇首声明信息。

簇首位置调整与簇间多跳路由建立：根据前述的簇首位置调整算法，可以建立整个网络的簇首节点；然后按式12进行路径迭代，即可建立多跳路由。

普通节点入网：普通节点会接收到周围各簇首的簇首广播，根据广播的信号强度选取一个距离最近的簇首加入。选定要加入的目标簇首后，通过CSMA/CA协议接入信道，向选定簇首发出内容为簇首ID和节点ID的Join-REQ消息请求加入成为其成员节点。

分配时隙：当簇首定时器计时到时，簇首为每个成员节点分配工作时隙。簇首先通过CSMA/CA协议接入通信信道，然后广播Join-ACK消息使其成员节点接收到时隙分配表。成员节点按照时隙分配情况设定定时器，并据此切换通信和休眠状态。

2.4.2 数据传送阶段

簇首融合信息：簇内全部成员节点在分配的时隙内将采集到的数据传送至簇首后，簇首按预先设定的算法对信息进行融合，成员节点则进入休眠状态直至下个组网周期。

数据传送：簇首将各成员节点的数据融合后发送至汇聚节点。当网络完成一定时间的数据传送后，根据相关算法进入下轮组网阶段。

3 系统仿真

本文利用MATLAB对EEACRA路由协议和LEACH路由协议进行了对比仿真。仿真网络传感器节点数量为100，监测面积为100 m*100 m，无线传感器节点随机布置，在网络监测中心位置设置汇聚节点，其仿真参数为：4 000 bits的数据包、1J的节点初始状态能量、10 pJ/bit/m2的近距离功率衰减系数εfs、40 bits的控制包长度、5 nJ/bit的节点收发送单位bit数据的能耗Eelec、0.001 3 pJ/bit/m4的远距离功率衰减系数εmp。EEACRA协议共采取了3种措施来降低LEACH协议的能耗，具体如表1所示。

表1 EEACRA协议能耗降低措施

EEACRA(EP)协议与LEACH协议的网络稳定期仿真结果如图4所示。

图4 EEACRA(EP)与LEACH 网络稳定期对比

EEACRA(EPD)协议与LEACH协议的网络稳定期仿真结果如图5所示。

图5 EEACRA(EPD)与LEACH 网络稳定期对比

EEACRA(EPDH)协议与LEACH协议的网络稳定期仿真结果如图6所示。

图6 EEACRA(EPDH)与LEACH 网络稳定期对比

从图4中可以看出，节点随机部署的情况下，EEACRA(EP)协议的网络稳定期均值为2296 轮，LEACH协议的网络稳定期均值为1892 轮，平均网络稳定期延长比例约为21.35%。

从图5中可以看出，节点随机部署的情况下，EEACRA(EPD)协议的网络稳定期均值为2415轮，LEACH协议的网络稳定期均值为1892轮，平均网络稳定期延长比例约为27.64%。

从图6中可以看出，节点随机部署的情况下，EEACRA(EP)协议的网络稳定期均值为2444 轮，LEACH协议的网络稳定期均值为1892 轮，平均网络稳定期延长比例约为29.18%。

综上可以看出，节点随机部署的情况下，EEACRA(EP)、EEACRA(EPD)和EEACRA(EPDH)与LEACH相比，网络稳定期均值分别提高了约21.35%、27.64%和29.18%。但各措施对协议能耗的改善贡献不同，其中，能量加权因子使EACRA的网络稳定期均值延长了约21.35%，延时机制使网络稳定期均值延长了约6.29%，多跳路由机制使网络稳定期均值延长了约1.42%。故在实际网络应用中，可根据不同的网络要求对协议进行适当裁剪，使协议在获得良好增益性能的前提下降低算法的复杂度。

4 结论

针对无线传感器网络常用的LEACH路由协议存在的簇首能耗过分集中、簇首分布不均衡问题，提出了改进的路由协议EEACRA，有效地提高了网络的稳定期。同时给出了EEACRA路由协议实现的关键算法和工作流程，并对比了不能能耗降低措施对网络能耗降低的贡献，对EEACRA协议在无线传感器网络中的实际应用具有重要意义。

[1] 孙利民, 李建中, 陈 渝，等. 无线传感器网络[M]. 北京: 清华大学出版社, 2005.

[2] Heinzelman W B, Chandrakasan A P, Balakrishnan H. An application-specific protocol architecture for wireless sensor network[J]. IEEE Transactions on Wireless Communications. 2002, 1(4):660-670.

[3] 俞黎阳. 无线传感器网络网格状分簇路由协议和数据融合算法的研究[D]. 上海：华东师范大学, 2007(1):56-58.

[4] Kulik J, Heinzelman W, Balakrishnan H. Negotiation-based protocols for disseminating information in wireless sensor networks[J]. Wireless Networks, 2002, 8(2): 169-185.

[5] Krishnamachari B, Estrin D, Wicker S B. Impact of Data Aggregation in Wireless Sensor Networks[A]. Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS)[C].2002: 575-578.

[6] Ko Y, Vaidya N H. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks[J]. Wireless Networks. 2000, 6(4): 307-321.

[7] Hedetniemi S M, Hedetniemi S T, Liestman A L.A survey of gossiping and broadcasting in communication networks[J]. Networks, 1988, 18(4): 319-349.

[8] Estrin D. Wireless Sensor Networks Tutorial Part IV-Sensor Network Protocols[R]. 2002(1):22-24.

[9] 王万良, 陈陪俊, 郑建炜,等. 一种基于LEACH的无线传感器路由算法及其仿真[J]. 系统仿真技术, 2008, 4(2): 75-79.

[10] 于立娟, 李思敏. 无线传感器网络LEACH改进算法的设计与仿真[J]. 光通信研究, 2008,34(5): 67-70.

[11] 苏均宇,曾子维,石嘉鹏.基于定向扩散路由协议的改进[J].传感技术学报.2007,20(3):673-676.

[12] Ganesan D, Govindan R, Shenker S, et al. Highly-Resilient, Energy-Efficient Multipath Routing in Wireless Sensor Newtorks[J]. Mobile Computing and Communications Review. 2011, 1(2): 1-13.

[13] Felemban E, Lee C, Ekici E, et al. Probabilistic QoS Guarantee in Reliability and Timeliness Domains in Wireless Sensor Networks[A]. Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2005). [C]. 2010: 2646-2657.

[14] 毕俊蕾, 任新会, 郭拯危. 无线传感器网络路由协议分类研究[J]. 计算机技术与发展. 2010, 18(5): 131-137.

[15] Callaway B E H. Wireless Sensor Networks Architectures And Protocols[M]. CRC Press, 2012:255-257.

Research of Wireless Sensor Network (WSN)Multiple Hop Routing Protocol

Yuan Yaodong,Xu Hongyan

(Department of Public Science Education, Zhengzhou Shuqing Medical College, Zhengzhou 450064, China)

The wireless sensor network has developed rapidly, but the high energy consumption of the sensor has become the main bottleneck restricting its development. Based on the current LEACH routing protocol of wireless sensor network (WSN)are commonly used excessive concentration of energy consumption of cluster head, cluster head distribution imbalance problem, puts forward the improved routing protocol EEACRA. After studying the existing problems on the basis of LEACH routing protocol, gives the EEACRA routing protocol of the cluster head selecting threshold method, cluster head position adjustment algorithm and the cluster based on the minimum energy cost between multiple hops routing algorithm implementation method, finally in the MATLAB environment to LEACH routing protocol and EEACRA routing protocols are simulated, the contribution of different energy consumption reduction measures to the network energy consumption reduction is compared. The simulation results show that the network stability EEACRA routing protocol is the improvement of the LEACH routing protocol have larger. Proved that the validity of the agreement.

wireless sensor network; network architecture; routing protocols; clustering algorithms; LEACH agreement

2016-10-25；

2016-11-18。

袁耀东(1984-),男, 硕士，讲师，网络工程师，主要从事计算机网络与云计算方向的研究。

1671-4598(2017)04-0254-05

10.16526/j.cnki.11-4762/tp.2017.04.069

TM417

A