基于熵权法与灰色关联分析的WSNs路由算法*

刘 宏， 李好威

(江西理工大学 电气工程与自动化学院，江西 赣州 341000)



计算与测试

基于熵权法与灰色关联分析的WSNs路由算法*

刘 宏， 李好威

(江西理工大学 电气工程与自动化学院，江西 赣州 341000)

针对路由协议链路质量不高与能耗较大的问题，提出了一种基于熵权法与灰色关联分析的无线传感器网络(WSNs)路由算法(BEGRA)。首先建立下一跳节点的评价指标，其次引入熵权法确定各指标的权重，通过关联度分析法确定节点指标向量与参考向量间的加权关联度，最后由节点关联度的大小确定下一跳节点并确立路由路径。仿真结果表明：算法有效提高了网络生命周期，降低了网络能耗，且在网络数据传输效率方面具有良好性能。

无线传感器网络； 评价指标； 熵权法； 关联度分析； 指标向量

0 引 言

无线传感器网络(WSNs)的应用日益广泛，随着WSNs节点拓扑结构、网络环境的变化，如何高效利用节点能量提高网络寿命周期是路由设计的核心所在,例如文献[1]在LEACH算法的基础上提出了网络能量优化的算法，文献[2]中的路由算法与节点能量紧密相关，文献[3]采用分级传输方式以达到节省能耗的效果。

近年来模糊理论在WSNs中的应用越来越广泛。文献[4]中提出了模糊推理机制的路由算法，但算法中节点必须和基站频繁通信才能判定自身路由状况，能耗较大；文献[5]通过模糊逻辑控制方法构建路由，逐个判断自身节点到目的站的代价方法导致该算法性能有待完善；文献[6]通过模糊理论与蚁群算法相结合的方法建立路由,该算法在节点存活率方面有所提升，但权重赋值的主观判断性使评判结果在一定程度上缺乏客观性；文献[7]提出了一种基于模糊综合评判的多Sink最优路由算法，但存在不能客观反映路径中最小剩余能量等因素的权重问题。

基于此，在分析模糊理论、熵权法、灰色关联理论以及前期研究基础上，提出了一种基于熵权法与灰色关联分析的WSNs路由算法(BEGRA)，首先对节点的评价指标综合分析，其次引入熵权法确定各指标权重，通过灰色关联度分析法综合评价节点的指标向量与最优指标向量间的加权关联度，由加权关联度值确定下一跳节点。

1 模型假设

1.1 能量模型

两个节点之间发送lbit数据时，当两节点间发送距离d≤d0采用自由空间信道模型；d>d0时采用多路径衰减模型[8]。其发送端与接收端消耗的能量分别为

(1)

Erx(l)=lEelec

(2)

式中lEelec为节点处理lbit数据时的能量消耗;εfs，εmp分别为自由空间模型与多径衰减模型下功率放大的能量消耗;d0为两种模型的通信距离分界值。

1.2 网络模型

网络模型约束条件：1)网络有足够的节点组成，且基站能量不受限；2)网络内各节点间灵活性较强，可自行组织成一个网络；3)节点传输均为双向传输,各节点均具有各自不同的ID号；4)节点与基站均具有位置感知能力,节点初始能量相同；5)节点根据接收信号强度指示(RSSI)计算出发送节点到自身的近似距离。

2 设计思路

2.1 路由思想

定义节点的剩余能量率、邻居节点因子、双向向心率与成功发送率4个因素作为节点评价指标，通过熵权法与灰色关联度对待选下一跳节点进行综合评价，由关联度的值确定下一跳节点。

2.2 下一跳节点评价指标

1)剩余能量率：节点的剩余能量是节点工作的必备条件，定义下一跳节点j的剩余能量率ηj为

(3)

式中Ej为待选节点j的剩余能量；Eini-j为待选节点j初始能量。

2)邻居节点因子σj为一项重要指标，邻居节点数越多，数据传输的成功率相对越大,若节点重复发包数越多，则性能相对较差，综合两方面考虑定义下一跳节点j的邻居节点因子σj为

(4)

式中Mneighbour为邻居节点数；Cm为第m个邻居节点的重复发包次数。

3)双向向心率：在距离方面，算法从“能耗前后均衡、距离择直避弯”的角度出发，考虑待选节点与上一跳、下一跳的双向距离，如图1所示。从图中可以看出：在其他条件相同情况下，从距离因素考虑，节点3为最合适的下一跳节点，定义待选节点j的双向向心率Fj为

(5)

式中dij为待选节点j与上一跳节点i之间的距离；djk为待选节点j到下一跳节点k之间的距离。

图1 节点距离

4)成功发送率[9]：为待选节点j向下一跳节点k发送数据成功率的大小，定义节点j的成功发送率Rj为

(6)

式中Nj为节点j向下一跳节点k实发数据包总数；Nk为下一跳节点k实收节点j成功发送的数据包总数。

2.3 下一跳节点的综合评判方案设计

模糊综合评判是对受多种制约因素的事物做总体评判的一种方法，但存在2处不足：1)指标权重的确定依据经验值,缺乏一定的客观性；2)评判结果采用最大隶属度原则，其他信息忽略较多，误差较大。

因此，从权重和评判结果2方面改进以确定下一跳节点：1)权重确定：熵是对系统状态不确定性的一种度量，如果某评价指标的熵越小，说明该指标提供的信息量越大，在综合评价中的重要性越强，权重越高；反之，则越低。引入熵权法用于确定待选节点的指标权重，提高指标权重的客观性。2)评判结果确定：灰色关联度是根据各个因素之间发展趋势的相似或相异程度来作为衡量因素之间的关联程度的方法，WSNs中节点环境状态与灰色关联分析适用场合一致。引入灰色关联度分析法依据关联度的值确定下一跳节点，以增强评判结果的客观性。

3 路由算法

BEGRA算法通过熵权法与灰色关联分析确定下一跳节点。

3.1 确定节点的指标集与邻域信息包

由节点评价指标分析可知，节点指标集=(剩余能量率、邻居节点因子、双向向心率、成功发送率)。

选择开始时，基站以广播形式向网络发出构建路由的通知，各节点根据自身邻节点的信息建立属于自己的邻域信息包，信息包中存有各节点的指标集信息。

3.2 熵权法确定节点的指标权重

运用熵权法[10]确定m个节点,m=1,2,…,M的第n个指标权重,n=1,2,3,4。

1)构造评价指标矩阵

由m个下一跳节点、n个评价指标构成的评价指标矩阵如式(7)所示

R=[rmn]M×4

(7)

式中rmn为第m个节点下的第n个指标原始值。

2) 归一化评价指标矩阵

(8)

(9)

3)确定节点指标的权重

(10)

3.3 灰色关联度分析法[11]确定下一跳节点

1)确定指标的最优参考向量与原始向量

由式(9)可得参考向量与原始向量分别如式(11)与式(12)所示

(11)

(12)

2)确定指标关联系数

由式(13)确定节点原始指标与参考指标的关联度系数

(13)

3)确定节点关联度

关联系数指标向量与参考向量在4个指标上的关联程度值，为对比节点的整体性能，求取关联系数的平均值，作为指标向量与参考向量间关联程度的数量表示，即关联度。由式(13),式(14)可确定第m个节点与理想下一跳节点的平均加权关联度

(14)

式中wn与ξn分别为第n个节点指标的权重和关联度系数;N为指标个数。根据关联度的最大值可确定被关联节点的指标向量，进而确定下一跳节点。节点通过邻居节点数据包内指标信息计算各节点的关联度，选取关联度最大值作为下一跳，路由建立完成,进行数据传输。

4 仿真结果分析

采用OMNet++软件进行仿真，仿真参数设置：节点区域200 m×200 m,节点初始能量Einit=0.5 J，网络节点数N=400，自由空间信道模型能耗εfs=10 pJ/bit/m2，多径衰减信道模型能耗为εmp=0.001 3 pJ/(bit·m4)，电路能耗Eelec=50 nJ/bit，距离阈值d0=85 m，数据包长度l=4 000 bit,分辨系数ρ=0.5。仿真从网络能量消耗、生命周期、传输数据量3方面将BEGRA算法与LEACH,EEUC算法进行对比分析。

3种算法在网络能耗方面的对比曲线如图2所示。 在开始阶段各节点的剩余能量充足能耗差值较小，随着轮数的增加，3种算法的能耗均呈上升趋势，但BEGRA算法的能量消耗曲线较其他2种曲线的上升坡度相对较慢，说明BEGRA算法减缓了网络能耗速度，降低了网络能耗。

图2 网络能量消耗

BEGRA算法与LEACH，EEUC算法在生命周期的对比曲线图3所示。LEACH,EEUC，BEGRA算法分别在175，196，230轮节点开始死亡，而BEGRA算法的节点全部死亡时间明显晚于其他2种算法，说明BEGRA算法网络生命周期相比LEACH,EEUC算法有一定提高。

图4为3种算法在基站接收数据总量方面的对比曲线。由图看出：前200轮时3种算法传输数据量差别不大，但200轮以后BEGRA的传输数据量明显占优，EEUC次之，LEACH最差。说明BEGRA算法可传送更多的数据，网络的能量利用率较高。

图3 网络生命周期

图4 网络传输数据量

5 结 论

提出了一种基于熵权法与灰色关联分析的WSNs路由算法，通过对下一跳节点的评价指标进行分析确定后，采用熵权法确定各指标权重，实现了指标权重赋值的相对客观性；运用各指标的信息通过灰色关联度分析法确定下一跳节点，优化了路由路径的建立。仿真实验表明:与LEACH，EEUC算法相比，BEGRA算法降低了网络的能量消耗、提高了网络生命周期、提升了网络传输效率。

[1] 严斌亨，陈任秋，刘 军.能量优化的无线传感器网络LEACH算法[J].传感器与微系统，2016，35(7):120-122．

[2] 曹海英，元 元，刘志强.基于节点剩余能量和最大角度的无线传感器网络路由算法[J].传感器与微系统，2015，34(1):120-123．

[3] 赵菊敏，张子辰，李灯熬．一种无线传感器网络链式传输分簇路由协议[J].传感器与微系统，2014，33(3):135-138．

[4] 陈洁洁，蒋 平.基于模糊C—均值的无线传感器网络算法[J].计算机工程，2011，37(12):62-64.

[5] Minhas M R,Gopalakrishnan S,Leung V.Fuzzy algorithms for maximum lifetime routing in wireless sensor networks[C]∥Proc of Global Telecommunications Conference,[S.1.]:IEEE,2008:1284-1292.

[6] 陶志勇，蒋守凤.传感器网络中基于模糊理论和蚁群的路由算法[J].计算机应用与软件，2015，32(8):141-144.

[7] 袁甜甜，徐敬东，张建忠.一种基于基于模糊综合评判的多Sink最优路由算法[J].计算机工程，2012，38(7):73-76.

[8] 郑 希.基于LEACH的无线传感器网络路由协议能耗性能的研究及优化[D].上海:上海交通大学，2009.

[9] 刘华博，崔建明，戴鸿君.基于多元分类的无线传感器网络恶意节点检测算法[J].传感技术学报，2011，24(5):771-777.

[10] 程小辉，梁启亮，何军权.基于熵权法的WSNs性能指标权重决策方法[J].传感器与微系统，2013，32(10):44-47．

[11] 董 凯，关 欣，王海鹏，等.基于序贯修正灰关联度的全局最优航迹关联算法[J].电子与信息学报，2014，36(8):1940-1945．

刘 宏(1968-) ，男，教授，硕士生导师，主要从事无线传感器网络研究工作。

WSNs routing algorithm based on entropy weight method and grey relational analysis*

LIU Hong， LI Hao-wei

(School of Electrical Engineering and Automation,Jiangxi University of Science and Technology,Ganzhou 341000,China)

Aiming at the problems of low quality of routing protocol links and larger energy consumption,a wireless sensor networks(WSNs)routing algorithm based on entropy weight method and grey relational analysis (BEGRA) is proposed.Firstly,this algorithm establishes the evaluation indexes of next-hop node,then weight of each index is respectively determined by the method of entropy weight,the weighted correlation degree between the index vector and reference vector of the node are obtained through the correlation degree analysis method,finally the next-hop node is determined by the size of the node correlation degree and the node routing path is formed.Simulation results show that BEGRA effectively prolongs network life cycle,reduce the network energy consumption,and has good performance in terms of the efficiency of network data transmission.

wireless sensor networks (WSNs)； evaluation index； entropy weight method； correlation degree analysis； index vector

10.13873/J.1000—9787(2017)08—0117—04

2016—08—19

国家自然科学基金资助项目(61163063)

TP 393

A

1000—9787(2017)08—0117—04