基于熵權(quán)法與灰色關(guān)聯(lián)分析的WSNs路由算法*

劉 宏， 李好威

(江西理工大學 電氣工程與自動化學院，江西 贛州 341000)

?

計算與測試

基于熵權(quán)法與灰色關(guān)聯(lián)分析的WSNs路由算法*

劉 宏， 李好威

(江西理工大學 電氣工程與自動化學院，江西 贛州 341000)

針對路由協(xié)議鏈路質(zhì)量不高與能耗較大的問題，提出了一種基于熵權(quán)法與灰色關(guān)聯(lián)分析的無線傳感器網(wǎng)絡(luò)(WSNs)路由算法(BEGRA)。首先建立下一跳節(jié)點的評價指標，其次引入熵權(quán)法確定各指標的權(quán)重，通過關(guān)聯(lián)度分析法確定節(jié)點指標向量與參考向量間的加權(quán)關(guān)聯(lián)度，最后由節(jié)點關(guān)聯(lián)度的大小確定下一跳節(jié)點并確立路由路徑。仿真結(jié)果表明：算法有效提高了網(wǎng)絡(luò)生命周期，降低了網(wǎng)絡(luò)能耗，且在網(wǎng)絡(luò)數(shù)據(jù)傳輸效率方面具有良好性能。

無線傳感器網(wǎng)絡(luò)； 評價指標； 熵權(quán)法； 關(guān)聯(lián)度分析； 指標向量

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)的應(yīng)用日益廣泛，隨著WSNs節(jié)點拓撲結(jié)構(gòu)、網(wǎng)絡(luò)環(huán)境的變化，如何高效利用節(jié)點能量提高網(wǎng)絡(luò)壽命周期是路由設(shè)計的核心所在,例如文獻[1]在LEACH算法的基礎(chǔ)上提出了網(wǎng)絡(luò)能量優(yōu)化的算法，文獻[2]中的路由算法與節(jié)點能量緊密相關(guān)，文獻[3]采用分級傳輸方式以達到節(jié)省能耗的效果。

近年來模糊理論在WSNs中的應(yīng)用越來越廣泛。文獻[4]中提出了模糊推理機制的路由算法，但算法中節(jié)點必須和基站頻繁通信才能判定自身路由狀況，能耗較大；文獻[5]通過模糊邏輯控制方法構(gòu)建路由，逐個判斷自身節(jié)點到目的站的代價方法導(dǎo)致該算法性能有待完善；文獻[6]通過模糊理論與蟻群算法相結(jié)合的方法建立路由,該算法在節(jié)點存活率方面有所提升，但權(quán)重賦值的主觀判斷性使評判結(jié)果在一定程度上缺乏客觀性；文獻[7]提出了一種基于模糊綜合評判的多Sink最優(yōu)路由算法，但存在不能客觀反映路徑中最小剩余能量等因素的權(quán)重問題。

基于此，在分析模糊理論、熵權(quán)法、灰色關(guān)聯(lián)理論以及前期研究基礎(chǔ)上，提出了一種基于熵權(quán)法與灰色關(guān)聯(lián)分析的WSNs路由算法(BEGRA)，首先對節(jié)點的評價指標綜合分析，其次引入熵權(quán)法確定各指標權(quán)重，通過灰色關(guān)聯(lián)度分析法綜合評價節(jié)點的指標向量與最優(yōu)指標向量間的加權(quán)關(guān)聯(lián)度，由加權(quán)關(guān)聯(lián)度值確定下一跳節(jié)點。

1 模型假設(shè)

1.1 能量模型

兩個節(jié)點之間發(fā)送lbit數(shù)據(jù)時，當兩節(jié)點間發(fā)送距離d≤d0采用自由空間信道模型；d>d0時采用多路徑衰減模型[8]。其發(fā)送端與接收端消耗的能量分別為

(1)

Erx(l)=lEelec

(2)

式中l(wèi)Eelec為節(jié)點處理lbit數(shù)據(jù)時的能量消耗;εfs，εmp分別為自由空間模型與多徑衰減模型下功率放大的能量消耗;d0為兩種模型的通信距離分界值。

1.2 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)模型約束條件：1)網(wǎng)絡(luò)有足夠的節(jié)點組成，且基站能量不受限；2)網(wǎng)絡(luò)內(nèi)各節(jié)點間靈活性較強，可自行組織成一個網(wǎng)絡(luò)；3)節(jié)點傳輸均為雙向傳輸,各節(jié)點均具有各自不同的ID號；4)節(jié)點與基站均具有位置感知能力,節(jié)點初始能量相同；5)節(jié)點根據(jù)接收信號強度指示(RSSI)計算出發(fā)送節(jié)點到自身的近似距離。

2 設(shè)計思路

2.1 路由思想

定義節(jié)點的剩余能量率、鄰居節(jié)點因子、雙向向心率與成功發(fā)送率4個因素作為節(jié)點評價指標，通過熵權(quán)法與灰色關(guān)聯(lián)度對待選下一跳節(jié)點進行綜合評價，由關(guān)聯(lián)度的值確定下一跳節(jié)點。

2.2 下一跳節(jié)點評價指標

1)剩余能量率：節(jié)點的剩余能量是節(jié)點工作的必備條件，定義下一跳節(jié)點j的剩余能量率ηj為

(3)

式中Ej為待選節(jié)點j的剩余能量；Eini-j為待選節(jié)點j初始能量。

2)鄰居節(jié)點因子σj為一項重要指標，鄰居節(jié)點數(shù)越多，數(shù)據(jù)傳輸?shù)某晒β氏鄬υ酱?若節(jié)點重復(fù)發(fā)包數(shù)越多，則性能相對較差，綜合兩方面考慮定義下一跳節(jié)點j的鄰居節(jié)點因子σj為

(4)

式中Mneighbour為鄰居節(jié)點數(shù)；Cm為第m個鄰居節(jié)點的重復(fù)發(fā)包次數(shù)。

3)雙向向心率：在距離方面，算法從“能耗前后均衡、距離擇直避彎”的角度出發(fā)，考慮待選節(jié)點與上一跳、下一跳的雙向距離，如圖1所示。從圖中可以看出：在其他條件相同情況下，從距離因素考慮，節(jié)點3為最合適的下一跳節(jié)點，定義待選節(jié)點j的雙向向心率Fj為

(5)

式中dij為待選節(jié)點j與上一跳節(jié)點i之間的距離；djk為待選節(jié)點j到下一跳節(jié)點k之間的距離。

圖1 節(jié)點距離

4)成功發(fā)送率[9]：為待選節(jié)點j向下一跳節(jié)點k發(fā)送數(shù)據(jù)成功率的大小，定義節(jié)點j的成功發(fā)送率Rj為

(6)

式中Nj為節(jié)點j向下一跳節(jié)點k實發(fā)數(shù)據(jù)包總數(shù)；Nk為下一跳節(jié)點k實收節(jié)點j成功發(fā)送的數(shù)據(jù)包總數(shù)。

2.3 下一跳節(jié)點的綜合評判方案設(shè)計

模糊綜合評判是對受多種制約因素的事物做總體評判的一種方法，但存在2處不足：1)指標權(quán)重的確定依據(jù)經(jīng)驗值,缺乏一定的客觀性；2)評判結(jié)果采用最大隸屬度原則，其他信息忽略較多，誤差較大。

因此，從權(quán)重和評判結(jié)果2方面改進以確定下一跳節(jié)點：1)權(quán)重確定：熵是對系統(tǒng)狀態(tài)不確定性的一種度量，如果某評價指標的熵越小，說明該指標提供的信息量越大，在綜合評價中的重要性越強，權(quán)重越高；反之，則越低。引入熵權(quán)法用于確定待選節(jié)點的指標權(quán)重，提高指標權(quán)重的客觀性。2)評判結(jié)果確定：灰色關(guān)聯(lián)度是根據(jù)各個因素之間發(fā)展趨勢的相似或相異程度來作為衡量因素之間的關(guān)聯(lián)程度的方法，WSNs中節(jié)點環(huán)境狀態(tài)與灰色關(guān)聯(lián)分析適用場合一致。引入灰色關(guān)聯(lián)度分析法依據(jù)關(guān)聯(lián)度的值確定下一跳節(jié)點，以增強評判結(jié)果的客觀性。

3 路由算法

BEGRA算法通過熵權(quán)法與灰色關(guān)聯(lián)分析確定下一跳節(jié)點。

3.1 確定節(jié)點的指標集與鄰域信息包

由節(jié)點評價指標分析可知，節(jié)點指標集=(剩余能量率、鄰居節(jié)點因子、雙向向心率、成功發(fā)送率)。

選擇開始時，基站以廣播形式向網(wǎng)絡(luò)發(fā)出構(gòu)建路由的通知，各節(jié)點根據(jù)自身鄰節(jié)點的信息建立屬于自己的鄰域信息包，信息包中存有各節(jié)點的指標集信息。

3.2 熵權(quán)法確定節(jié)點的指標權(quán)重

運用熵權(quán)法[10]確定m個節(jié)點,m=1,2,…,M的第n個指標權(quán)重,n=1,2,3,4。

1)構(gòu)造評價指標矩陣

由m個下一跳節(jié)點、n個評價指標構(gòu)成的評價指標矩陣如式(7)所示

R=[rmn]M×4

(7)

式中rmn為第m個節(jié)點下的第n個指標原始值。

2) 歸一化評價指標矩陣

(8)

(9)

3)確定節(jié)點指標的權(quán)重

(10)

3.3 灰色關(guān)聯(lián)度分析法[11]確定下一跳節(jié)點

1)確定指標的最優(yōu)參考向量與原始向量

由式(9)可得參考向量與原始向量分別如式(11)與式(12)所示

(11)

(12)

2)確定指標關(guān)聯(lián)系數(shù)

由式(13)確定節(jié)點原始指標與參考指標的關(guān)聯(lián)度系數(shù)

(13)

3)確定節(jié)點關(guān)聯(lián)度

關(guān)聯(lián)系數(shù)指標向量與參考向量在4個指標上的關(guān)聯(lián)程度值，為對比節(jié)點的整體性能，求取關(guān)聯(lián)系數(shù)的平均值，作為指標向量與參考向量間關(guān)聯(lián)程度的數(shù)量表示，即關(guān)聯(lián)度。由式(13),式(14)可確定第m個節(jié)點與理想下一跳節(jié)點的平均加權(quán)關(guān)聯(lián)度

(14)

式中wn與ξn分別為第n個節(jié)點指標的權(quán)重和關(guān)聯(lián)度系數(shù);N為指標個數(shù)。根據(jù)關(guān)聯(lián)度的最大值可確定被關(guān)聯(lián)節(jié)點的指標向量，進而確定下一跳節(jié)點。節(jié)點通過鄰居節(jié)點數(shù)據(jù)包內(nèi)指標信息計算各節(jié)點的關(guān)聯(lián)度，選取關(guān)聯(lián)度最大值作為下一跳，路由建立完成,進行數(shù)據(jù)傳輸。

4 仿真結(jié)果分析

采用OMNet++軟件進行仿真，仿真參數(shù)設(shè)置：節(jié)點區(qū)域200 m×200 m,節(jié)點初始能量Einit=0.5 J，網(wǎng)絡(luò)節(jié)點數(shù)N=400，自由空間信道模型能耗εfs=10 pJ/bit/m2，多徑衰減信道模型能耗為εmp=0.001 3 pJ/(bit·m4)，電路能耗Eelec=50 nJ/bit，距離閾值d0=85 m，數(shù)據(jù)包長度l=4 000 bit,分辨系數(shù)ρ=0.5。仿真從網(wǎng)絡(luò)能量消耗、生命周期、傳輸數(shù)據(jù)量3方面將BEGRA算法與LEACH,EEUC算法進行對比分析。

3種算法在網(wǎng)絡(luò)能耗方面的對比曲線如圖2所示。 在開始階段各節(jié)點的剩余能量充足能耗差值較小，隨著輪數(shù)的增加，3種算法的能耗均呈上升趨勢，但BEGRA算法的能量消耗曲線較其他2種曲線的上升坡度相對較慢，說明BEGRA算法減緩了網(wǎng)絡(luò)能耗速度，降低了網(wǎng)絡(luò)能耗。

圖2 網(wǎng)絡(luò)能量消耗

BEGRA算法與LEACH，EEUC算法在生命周期的對比曲線圖3所示。LEACH,EEUC，BEGRA算法分別在175，196，230輪節(jié)點開始死亡，而BEGRA算法的節(jié)點全部死亡時間明顯晚于其他2種算法，說明BEGRA算法網(wǎng)絡(luò)生命周期相比LEACH,EEUC算法有一定提高。

圖4為3種算法在基站接收數(shù)據(jù)總量方面的對比曲線。由圖看出：前200輪時3種算法傳輸數(shù)據(jù)量差別不大，但200輪以后BEGRA的傳輸數(shù)據(jù)量明顯占優(yōu)，EEUC次之，LEACH最差。說明BEGRA算法可傳送更多的數(shù)據(jù)，網(wǎng)絡(luò)的能量利用率較高。

圖3 網(wǎng)絡(luò)生命周期

圖4 網(wǎng)絡(luò)傳輸數(shù)據(jù)量

5 結(jié) 論

提出了一種基于熵權(quán)法與灰色關(guān)聯(lián)分析的WSNs路由算法，通過對下一跳節(jié)點的評價指標進行分析確定后，采用熵權(quán)法確定各指標權(quán)重，實現(xiàn)了指標權(quán)重賦值的相對客觀性；運用各指標的信息通過灰色關(guān)聯(lián)度分析法確定下一跳節(jié)點，優(yōu)化了路由路徑的建立。仿真實驗表明:與LEACH，EEUC算法相比，BEGRA算法降低了網(wǎng)絡(luò)的能量消耗、提高了網(wǎng)絡(luò)生命周期、提升了網(wǎng)絡(luò)傳輸效率。

[1] 嚴斌亨，陳任秋，劉 軍.能量優(yōu)化的無線傳感器網(wǎng)絡(luò)LEACH算法[J].傳感器與微系統(tǒng)，2016，35(7):120-122．

[2] 曹海英，元 元，劉志強.基于節(jié)點剩余能量和最大角度的無線傳感器網(wǎng)絡(luò)路由算法[J].傳感器與微系統(tǒng)，2015，34(1):120-123．

[3] 趙菊敏，張子辰，李燈熬．一種無線傳感器網(wǎng)絡(luò)鏈式傳輸分簇路由協(xié)議[J].傳感器與微系統(tǒng)，2014，33(3):135-138．

[4] 陳潔潔，蔣 平.基于模糊C—均值的無線傳感器網(wǎng)絡(luò)算法[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] 陶志勇，蔣守鳳.傳感器網(wǎng)絡(luò)中基于模糊理論和蟻群的路由算法[J].計算機應(yīng)用與軟件，2015，32(8):141-144.

[7] 袁甜甜，徐敬東，張建忠.一種基于基于模糊綜合評判的多Sink最優(yōu)路由算法[J].計算機工程，2012，38(7):73-76.

[8] 鄭 希.基于LEACH的無線傳感器網(wǎng)絡(luò)路由協(xié)議能耗性能的研究及優(yōu)化[D].上海:上海交通大學，2009.

[9] 劉華博，崔建明，戴鴻君.基于多元分類的無線傳感器網(wǎng)絡(luò)惡意節(jié)點檢測算法[J].傳感技術(shù)學報，2011，24(5):771-777.

[10] 程小輝，梁啟亮，何軍權(quán).基于熵權(quán)法的WSNs性能指標權(quán)重決策方法[J].傳感器與微系統(tǒng)，2013，32(10):44-47．

[11] 董 凱，關(guān) 欣，王海鵬，等.基于序貫修正灰關(guān)聯(lián)度的全局最優(yōu)航跡關(guān)聯(lián)算法[J].電子與信息學報，2014，36(8):1940-1945．

劉 宏(1968-) ，男，教授，碩士生導(dǎo)師，主要從事無線傳感器網(wǎng)絡(luò)研究工作。

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