基于耦合因子的WSN無標度路徑能耗優(yōu)化算法

朱永平，孔凡鳳

(湖南郵電職業(yè)技術學院移動通信系，湖南 長沙 410115)

?

基于耦合因子的WSN無標度路徑能耗優(yōu)化算法

朱永平，孔凡鳳

(湖南郵電職業(yè)技術學院移動通信系，湖南 長沙 410115)

在大規(guī)模無線傳感器網絡中針對能耗不均衡問題，建立多跳路徑能量優(yōu)化模型，得到路徑能量消耗隨節(jié)點度變化規(guī)律，求出最優(yōu)的節(jié)點度取值，并引入耦合因子參數構建網絡形成無標度拓撲結構，提出一種基于耦合因子的WSN無標度路徑能耗優(yōu)化算法.仿真實驗結果表明分析表明此算法具有較好容錯性能，生成的網絡拓撲結構節(jié)點度分布服從冪律，具有無標度性，而且可以減少能量消耗并延長網絡生命周期.

無線傳感器網絡；耦合因子；路徑能量消耗；容錯；無標度

WSN(Wireless Sensor Network)是通信和計算機領域的結合產物，能夠對覆蓋區(qū)域進行感知并具有計算能力，經常被用于惡劣環(huán)境中.覆蓋范圍、節(jié)點能耗、生命周期、容錯性、服務質量是衡量無線傳感網絡重要技術指標[1].在惡劣的環(huán)境中因WSN節(jié)點電池不能更換，節(jié)點能量耗盡后網絡拓撲結構會發(fā)生變化.所以在構建網絡時，不但要考慮網絡拓撲結構的魯棒性，也要考慮網絡的節(jié)能性[2]，如何構造一個強健的網絡拓撲結構是當前專家學者的研究熱點.

Barabasi和Albert[3]在1999年提出了一種度分布遵循冪律的Barabasi-Albert (BA)模型，此模型組建了魯棒性較強的無標度拓撲結構，對于解決復雜網絡的隨機故障問題提供了新的思路.BA模型指出如果存在一個t+m、t·m條邊的網絡，新加入j與已存在節(jié)點i的連接概率和度服從冪指數為3的函數.陳力軍等[4]根據兩個參數生長和偏好通過兩個步驟形成無標度的網絡拓撲結構，然后隨機行走加入到父親節(jié)點，從而使網絡的節(jié)點分布更加均勻.Zheng et al[5]則對網絡的節(jié)點進行邊緣化處理，通過嵌入、刪除、補償節(jié)點及重構邊緣從而構造具有重構機制的Barabasi-Albert模型，提高了網絡的容錯性.Zhu et al[6]從節(jié)省節(jié)點能量角度出發(fā)，構建了2種自組織的拓撲網絡模型，EAEM(Energy-Aware Evolution Model)算法通過節(jié)點的剩余能量構建連通網絡，因此有較好的容錯能力，特別是對抗隨機誤差，性能提高較多；EBEM(Energy-Balanced Evolution Model)則約束每一個節(jié)點的能量，設置了閾值，網絡的能量消耗更加均衡.Li et al[7]對匯聚節(jié)點的節(jié)點度設置了最大值，從而解決了因為節(jié)點度過大而造成的過早死亡，使網絡的節(jié)點能量消耗更加均衡，延長整個網絡的壽命，但是網絡的容錯性有待提高.劉浩然等[8]提出的EETA算法充分考慮了無線傳感器網絡平均跳數和單跳通信損耗，但是沒有考慮局域世界節(jié)點間的依賴性.上面的文獻都對網絡的拓撲結構構建提出了建設性的方案，同時還考慮了節(jié)點的能量消耗，但是沒有考慮構節(jié)點間的競爭能力及隨機誤差對網絡的影響，也導致WSN的能量消耗不均衡，生命周期縮短.

基于以上所述，本文在無標度的網絡拓撲結構下考慮WSN的節(jié)能性，構建網絡結構與路徑能耗的關系，建立節(jié)點度、單跳模型能耗與平均跳數的關系式，從而求出最優(yōu)的節(jié)點度數值，并通過節(jié)點間的耦合因子調整節(jié)點度的分布，提出了基于耦合因子的WSN無標度路徑能耗優(yōu)化算法(Energy Efficiency Based on Coupling Coefficients Topology Algorithm，EEBC)，使無標度的網絡不但健壯而且還延長了網絡生命周期.

1　路徑能耗模型

本文研究角度是無標度網絡拓撲結構的構建及網絡能量消耗的均衡，所以從節(jié)點單跳路徑能耗和網絡平均跳數入手，分析網絡路徑能量消耗與節(jié)點度的關系曲線，得出最優(yōu)節(jié)點度的取值，為構建基于耦合因子的路徑能耗優(yōu)化算法EEBC提供理論基礎.

考慮能量消耗不能只看單個節(jié)點，還與網絡的拓撲結構密切相關，也就是說任意一個節(jié)點傳遞數據信息的能量消耗不僅與距離有關系，還與跳數有關，更進一步說就是路徑能量消耗E隨著單個節(jié)點能耗Ecost、平均跳數〈h〉增大而增加.定義：E=Ecost〈h〉.

本文分別從單跳能量消耗和數據轉發(fā)的平均跳數兩個參數入手，結合推理得到總消耗E和節(jié)點度k的關系式，并仿真分析E和節(jié)點度的關系，最終求出使E最小的最優(yōu)節(jié)點度.

1.1單跳路徑能耗

根據無線傳播路徑的模型，在距離為d的節(jié)點間傳輸n bit的數據，總的能量消耗Ecost為發(fā)送能量消耗Etx和接收能量消耗Er x之和，滿足下面的關系式

Ecost= Etx+ Er x

=(Eelctn+εampndα)+Eelctn

=2Eelctn+εampndα

(1)

其中，Eelct為電路裝置接發(fā)每單位bit數據的能量損耗；εamp是傳輸單位比特經過每平方米的能量消耗；α是衰減指數，一般取值范圍為2≤α≤5，此參數與環(huán)境有關，當網絡環(huán)境較理想時,α=2.令l=nEelct，μ=nεamp，則上式改寫成

Ecost=2l+μd2

(2)

定義N個節(jié)點隨機分布在面積為G的區(qū)域內，那么節(jié)點服從均勻分布

(3)

節(jié)點落在半徑為d的圓形區(qū)域內概率為

(4)

k為在區(qū)域D內的節(jié)點數，那么通信距離d與k、N存在如下關系

(5)

將上式代入公式(3)，則可以計算出節(jié)點i單跳路徑內消耗的能量為

(6)

1.2平均跳數〈h〉

在復雜網絡中，普通節(jié)點與基站距離較遠，不能實現數據直接傳輸，文獻[9]LEACH算法首先選出簇頭，普通節(jié)點根據節(jié)點信號的強弱加入最近的簇頭，在數據傳輸中數據從普通節(jié)點傳遞到簇頭，然后匯聚后到基站，從而實現數據的聚合.數據從自身節(jié)點到基站需要多次轉發(fā).

定義：跳數為信息從源節(jié)點到基站所轉發(fā)的次數.現在較為成熟的轉發(fā)算法有：固定傳輸范圍內的最短前進距離轉發(fā)、固定傳輸范圍內的最大前進距離轉發(fā)、貪婪轉發(fā)(GFF).通過比較可以看出GFF具有算法復雜度低、平均跳數小等優(yōu)點.

(7)

如圖1所示，A1和A2為陰影較大和較小部分的面積，d表示節(jié)點最大通信半徑，a則為源節(jié)點到目的節(jié)點的距離.從圖1中可以看出，假設兩節(jié)點的距離又一定時，如果Z越大，那么到達的目的節(jié)點的跳數將越少.

圖1　GFF轉發(fā)

(8)

(9)

1.3路徑能耗優(yōu)化模型

由上面的兩個小節(jié)分別推出了Ecost和〈h〉與k關系式，代入到式E=Ecost〈h〉可以得出平均的能耗E.

(10)

式中ρ為傳感器節(jié)點監(jiān)測范圍的密度.從上式也可以推導出存在最優(yōu)的節(jié)點度使能量消耗E最小.如果網絡已經獲知，節(jié)點度k為變量，其他的參數為定值，那么只要求出最佳k就可以使能量消耗達到最低.

圖2　路徑能量消耗隨節(jié)點度變化曲線

現設定一組參數取值，L=1，l=1×108J，π=3.14，節(jié)點密度ρ=0.0032.此條件下，WSN最優(yōu)的節(jié)點密度為10，求出路徑能量消耗的曲線變化，如圖2所示.從圖上可以看出，在為1～10的范圍內，隨著網絡節(jié)點度的增加，路徑消耗迅速下降，當大于10的時候，平均路徑損耗又緩慢升高，那么我們可以認為存在能量消耗的極小值，從而在WSN可以求出使E最小的最優(yōu)節(jié)點度〈h〉.

通過實驗也可以求出節(jié)點密度ρ與最優(yōu)節(jié)點度〈h〉的關系，可以得知隨著節(jié)點密度的增大，節(jié)點度〈h〉也在遞增，并且成單向遞增，所以兩者為正比關系如圖3所示.可以推出如果已知節(jié)點的密度，則可以求出最佳節(jié)點度，進而使能量消耗達到最低.

圖3　節(jié)點密度與最優(yōu)節(jié)點度的關系圖

2　基于耦合因子的路徑能耗優(yōu)化算法

BA的模型首次提出了實際網絡的無標度網絡的建模機理，兩個關鍵參數是增長和擇優(yōu)連接.但是BA的局限性在于在節(jié)點的連接增長中僅考慮了時間變化的長短，而實際的網絡模型在形成過程中還要考慮優(yōu)先連接因素，因此，本文設計的EEBC算法針對BA模型的優(yōu)先連接概率的設計過于簡單作了改進.

第一，擇優(yōu)連接增長概率不僅取決于節(jié)點度，還依賴于競爭關系，本文用耦合因子函數表示，不但具有網絡的無標度特性，而且又有較強的容錯能力.

第二，網絡節(jié)點的度數不能隨意增長，引入關于耦合因子si的適應模型，不但防止節(jié)點的過度消耗而導致的死亡，使整個網絡的消耗更加均衡，而且通過控制耦合因子si調整網絡節(jié)點度的期望值〈h〉，從而得到最佳節(jié)點度.此算法不但具有能耗優(yōu)化能力即有較強的信息傳遞能力，同時也更接近于真實的網絡.

2.1耦合因子參數的定義

本文用耦合因子來描述相鄰節(jié)點的相互關系.耦合在硬件上兩個元器件的輸入和輸出存在相互的影響，能量可以從輸入端傳遞到另外一側.從數學的角度上說，就是兩個對象之間存在較大的相關性.耦合因子表示為元件間耦合的松緊程度，也可以描述網絡的局部相鄰節(jié)點之間的傳遞信息的能力.

定義：無線傳感器網絡節(jié)點間的耦合因子初始值為1，每新加入一個節(jié)點，耦合因子的計算規(guī)則為：

(11)

其中，常數0<δ<1，控制耦合因子的大小，Γi為節(jié)點的集合，kl為節(jié)點i的度，最大值為kmax.

在網絡的生長過程中，無標度的容錯拓撲結構的網絡度服從ρ(k)=Ck-λ(C>0,λ>2)，記節(jié)點的最小度為1，則可由下面的公式計算出無標度網絡的鄰居節(jié)點數期望〈h〉.

(12)

(13)

WSN網絡在生長過程中每個時間邊數加1，因此可以得出節(jié)點度期望值〈h〉和最大度kmax的關系.

(14)

由上式可以得出，節(jié)點度期望值〈h〉可以由kmax和λ決定，反之，如果〈h〉和λ已知，可以求出kmax.

本文的網絡生成演進規(guī)則按照如下規(guī)則生成：

1)初始化網絡：給定一個具有m0節(jié)點，e0條邊的網絡.網絡按照時間步增長，但是不能無限制的增長，否則會引起網絡的消耗不均衡.

(15)

(16)

2.2算法EEBC動態(tài)性分析

分布屬性會影響EEBC算法的性能，假設新的節(jié)點m在t時刻加入網絡，R0為網絡的初始半徑，Rt為t時刻的半徑，RQ為節(jié)點的通信半徑.因此

(17)

將式(17)代入(16)得到

(18)

一般網絡生成過程中采用平均場的方法，節(jié)點i的度數kl的t時刻增長率為：

(19)

其中，新的節(jié)點在t時刻進入網絡，初始的度數為kj(t)=m，然后以節(jié)點的度數以概率p不斷變化.解方程得：

(20)

當t→∞時，上式可得

(21)

(22)

節(jié)點i的度ki(t)小于k的概率為

(23)

(24)

度分布概率密度為

(25)

當t→∞時

(26)

從上式可以得出此算法是無標度的，當psi越大，耦合因子的函數越大，節(jié)點度的變化就越明顯.

3　仿真結果與性能比較

通過上面的分析，理論上證明了網絡的拓撲度分布具有冪律特征.本文與容錯性代表算法EBEM和生命周期較好代表算法EETA算法進行比較.通過實驗平臺MATLAB進行仿真，實驗的參數設置如下：

表1　仿真參數設置

3.1無標度特性

本文EEBC算法拓撲結構如圖4所示，在200個節(jié)點中，生成了少數的高節(jié)點度的中樞節(jié)點和多數的普通的末梢節(jié)點，從而避免了網絡中“貧富”差距，造成網絡節(jié)點消耗比較均衡.

圖4　網絡拓撲結構

3.2容錯能力對比

依據于表1給的實驗參數，同時根據上文的理論分析，計算求得kmax=17.408，取整為kmax=17來實現EEBC算法，從而研究網絡的拓撲性能.

每輪各個節(jié)點會跟鄰居節(jié)點進行數據交換，網絡中節(jié)點發(fā)生故障的概率是相同的，在具有300個節(jié)點的網絡中，實驗中隨機地移除某個節(jié)點，統(tǒng)計網絡中最大連通支配集中節(jié)點的數目，觀察EEBC、EBEM、EETA三種算法的容錯能力.

圖5　隨機失效容忍能力對比

從圖5中不難看出，三種算法都具有較好的容錯能力，網絡中度較小的節(jié)點失效的概率較大，對于網絡連通性影響小，容錯性就比較好.EEBC拓撲網絡連通分支大于EBEM和EETA，在移除15個節(jié)點時，網絡覆蓋依然比較完整，故具有較好的容錯能力.

3.3節(jié)點能耗分析及網絡的生命周期對比

選取100、200、300、400個節(jié)點的任意節(jié)點間通信能耗來體現網絡能耗，重復試驗50次，每次統(tǒng)計信息傳遞中路徑的單跳路徑能耗和跳數，最后取平均值，結果如圖6所示.

圖6　網絡平均路徑能量損耗

EETA算法充分考慮了無線傳感器網絡平均跳數和單跳通信損耗，EBEM算法不但考慮了節(jié)點的剩余能量，還考慮了節(jié)點度的最大值，網絡較均衡.但是EBEM沒有考慮路徑能量消耗，EETA則沒有考慮局域世界節(jié)點間的依賴性.由圖6可以看出EEBC在路徑能量消耗方面具有優(yōu)勢，節(jié)能有明顯的提升.

圖7　網絡生命周期比較

從圖7可以看出，EEBC出現首個節(jié)點死亡的輪數要比EAEM晚112輪，而且EEBC算法在整體上消耗能量比EBEM算法要少.在實驗中，每一輪節(jié)點與鄰居節(jié)點交換數據，隨著生命運行周期輪數的不斷增加，失效節(jié)點的比例數也在增加，但是EEBC算法節(jié)能明顯，所以生命周期要長于EBEM算法.EEBC算法不但考慮了平均跳數和單跳通信能耗，而且通過節(jié)點間耦合因子控制節(jié)點的連通支配，得到網絡結構比較均衡，使網絡的生命周期得到延長.

4　結束語

本文通過分析網絡節(jié)點數據交換的平均跳數和單跳路徑的能量消耗兩個變量，得到了網絡節(jié)點度的分布，并得出最優(yōu)取值，提出一種基于耦合因子WSN無標度路徑能耗優(yōu)化算法，分析得到該算法具有無標度性.通過實驗仿真表明，EEBC算法構成的網絡結構的路徑能量消耗比較均衡，優(yōu)于EBEM和EETA算法，具有較好的節(jié)能特性.在真實的環(huán)境中設計能耗低同時容侵能力強的無標度算法是接下來的研究方向.

[1]Chen X, Kim Y A, Wang B, et al. Fault-tolerant monitor placement for out-of-band wireless sensor network monitoring[J].Ad Hoc Net-works, 2012, (1):62-74.

[2]Baria A, Jaekel A, Jiang J, et al. Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirement[J].Computer Communications, 2012, (3):320-333.

[3]Barabasi A, Albert R. Emergence of scaling in random net-works[J].Science, 1999,(15):509-512.

[4]陳力軍, 劉明, 陳道蓄, 等.基于隨機行走的無線傳感器網絡簇間拓撲演化[J].計算機學報, 2009, (1):69-76.

[5]Zheng G Z, Liu S Y, Qi X G. Scale-free topology evolution for wireless sensor networks with reconstruction mechanism[J].Computer & Electrical Engineering, 2012, (3):643-651.

[6]Zhu H L, Luo H, Peng H P, et al. Complex networks-based energy-efficient evolution model for wireless sensor networks[J].Chaos, Solitons & Fractals, 2009, (4):1828-1835.

[7]Li S D, Li L X, Yang Y X. A local-world heterogeneous model of wireless sensor networks with node and link diversity[J]. Physica A, 2011, (6):1182-1191.

[8]劉浩然, 韓濤, 李雅倩, 等.具有路徑能耗優(yōu)化特性的無標度容錯拓撲控制算法[J].通信學報, 2014, (6):64-72.

[9]Hou T C, Li V. Transmission range control in multihop packet radio networks[J].IEEE Transactions on Communications, 1986, (1):38-44.

[10]Klenrock L, Silvester J. Optimum transmission radii for packet radio networks or why six is a magic number[C]. Proc IEEE Nat Telecomm Conf[C]. 1978.

(責任編校：晴川)

Scale-free Algorithm in WSN Based on Coupling Coefficients with Optimization of Path Energy Consumption

ZHU Yongping, KONG Fanfeng

(Department of Mobile Communication, Hunan Post and Telecommunication College,Changsha Hunan 410115, China)

For the issue of path energy imbalance consumption in large-scale sensor network，an optimization model of network path energy consumption based on the mode of multi-hop was established, and the law of the change of the energy consumption of the path was obtained. According to the optimal value of nodes, the network topology was built based on the coupling factor parameter which could control the network average node degree, and a scale-free topology control algorithm EEBC having the characteristics that could minimize the path energy consumption was put forward. The performance analysis indicates that the algorithm has good fault-tolerant performance and the node degree distribution follows the power law. The simulation results show that the algorithm also reduces the path energy consumption in the network and then prolongs the network life.

WSN; coupling coefficients ; path energy consumption; fault-tolerant; scale-free

2016-06-08

湖南省教育廳重點項目(批準號：ZJA2013023)；湖南省教育廳科學研究項目(批準號：16C1187).

朱永平(1971— )，男，湖南祁陽人，湖南郵電職業(yè)技術學院移動通信系講師，碩士.研究方向：移動通信、無線傳感器網絡.

TP393

A

1008-4681(2016)05-0053-05