劉 宏， 李好威

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

?

計(jì)算與測(cè)試

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

劉 宏， 李好威

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

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

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

0 引 言

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

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

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

1 模型假設(shè)

1.1 能量模型

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

(1)

Erx(l)=lEelec

(2)

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

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

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

2 設(shè)計(jì)思路

2.1 路由思想

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

2.2 下一跳節(jié)點(diǎn)評(píng)價(jià)指標(biāo)

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

(3)

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

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

(4)

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

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

(5)

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

圖1 節(jié)點(diǎn)距離

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

(6)

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

2.3 下一跳節(jié)點(diǎn)的綜合評(píng)判方案設(shè)計(jì)

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

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

3 路由算法

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

3.1 確定節(jié)點(diǎn)的指標(biāo)集與鄰域信息包

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

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

3.2 熵權(quán)法確定節(jié)點(diǎn)的指標(biāo)權(quán)重

運(yùn)用熵權(quán)法[10]確定m個(gè)節(jié)點(diǎn),m=1,2,…,M的第n個(gè)指標(biāo)權(quán)重,n=1,2,3,4。

1)構(gòu)造評(píng)價(jià)指標(biāo)矩陣

由m個(gè)下一跳節(jié)點(diǎn)、n個(gè)評(píng)價(jià)指標(biāo)構(gòu)成的評(píng)價(jià)指標(biāo)矩陣如式(7)所示

R=[rmn]M×4

(7)

式中rmn為第m個(gè)節(jié)點(diǎn)下的第n個(gè)指標(biāo)原始值。

2) 歸一化評(píng)價(jià)指標(biāo)矩陣

(8)

(9)

3)確定節(jié)點(diǎn)指標(biāo)的權(quán)重

(10)

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

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

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

(11)

(12)

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

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

(13)

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

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

(14)

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

4 仿真結(jié)果分析

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

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

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

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

圖4為3種算法在基站接收數(shù)據(jù)總量方面的對(duì)比曲線。由圖看出：前200輪時(shí)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路由算法，通過對(duì)下一跳節(jié)點(diǎn)的評(píng)價(jià)指標(biāo)進(jìn)行分析確定后，采用熵權(quán)法確定各指標(biāo)權(quán)重，實(shí)現(xiàn)了指標(biāo)權(quán)重賦值的相對(duì)客觀性；運(yùn)用各指標(biāo)的信息通過灰色關(guān)聯(lián)度分析法確定下一跳節(jié)點(diǎn)，優(yōu)化了路由路徑的建立。仿真實(shí)驗(yàn)表明:與LEACH，EEUC算法相比，BEGRA算法降低了網(wǎng)絡(luò)的能量消耗、提高了網(wǎng)絡(luò)生命周期、提升了網(wǎng)絡(luò)傳輸效率。

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

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

[3] 趙菊敏，張子辰，李燈熬．一種無線傳感器網(wǎng)絡(luò)鏈?zhǔn)絺鬏敺执芈酚蓞f(xié)議[J].傳感器與微系統(tǒng)，2014，33(3):135-138．

[4] 陳潔潔，蔣 平.基于模糊C—均值的無線傳感器網(wǎng)絡(luò)算法[J].計(jì)算機(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].計(jì)算機(jī)應(yīng)用與軟件，2015，32(8):141-144.

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

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

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

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

[11] 董 凱，關(guān) 欣，王海鵬，等.基于序貫修正灰關(guān)聯(lián)度的全局最優(yōu)航跡關(guān)聯(lián)算法[J].電子與信息學(xué)報(bào)，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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163063)

TP 393

A

1000—9787(2017)08—0117—04