一種模糊評判的非均勻分簇路由優化算法

劉 宏,李好威

(江西理工大學 電氣工程與自動化學院,江西 贛州 341000) E-mail:jxligonglh@163.com

1 引 言

隨著計算機網絡、人工智能以及無線通信技術的快速發展,無線傳感器網絡(Wireless Sensor Networks,WSN)已深入人們生活[1].在WSN應用中各節點能量消耗是重要的性能指標,因此如何降低能耗、提高網絡壽命已成為當前路由協議研究的熱點之一.

目前路由協議算法中,分簇類協議在降低能耗、提高能量利用率等方面具有顯著優勢,成為當前重點研究的路由技術.國內外眾多學者對分簇路由算法進行了研究:文獻[2,3]通過改進簇首選取方式,提高了簇首性能,但對于簇內節點間距離不予考慮,導致簇內通信時能耗較大;文獻[4]提出了一種分布式非均勻分簇路由協議(DEBUC),使簇首節點分布更加合理,但簇的競爭半徑依次增大毫無限制,導致網絡消耗能量過大;文獻[5]對于簇首的選取僅考慮能量,忽略傳輸距離等因素,簇首選舉因素選取缺乏全面性;文獻[6]通過能量和傳輸距離對LEACH的閾值函數做出了改進,提升了網絡性能,但簇首能耗較大;文獻[7]提出能量均衡前行算法(EBFA),但該算法僅通過預先評估能量均衡情況選擇下一跳,簇間路由質量不高;文獻[8]以能量和節點度作為選擇下一跳的關鍵因素,但忽視距離從而使得下一跳節點的選取缺乏可靠性;文獻[9]在下一跳節點選取這一問題上通過簇首最大評判值選擇,但未考慮能量開銷問題,簇間路由能耗較大.

由文獻回顧可知,現有分簇路由協議中依然存在簇首選舉不當、網絡能耗較大等問題,本文從提高簇首選舉質量和提升簇間路由的效率出發,提出一種模糊評判的非均勻分簇路由優化算法(Uneven clustering Routing optimization algorithm Based on Fuzzy evaluation,URBF).在簇首選舉階段,采用熵權法[10]確定指標權重,并用優化的模糊綜合評判方法確定簇首.在簇間路由階段,通過設計鏈路評估值選取下一跳節點,以提高簇間路由質量和效率.

2 系統模型

2.1 能耗模型

根據發送節點和接收節點之間的通信距離分別采用自由空間模型和多路徑衰減模型[11],節點將k比特數據發送到距離為d的節點需要消耗的能量為:

(1)

節點接收k比特數據消耗的能量為:

ERx(l)=kEelec

(2)

其中,Eelec代表收發器的能量消耗,εfs與εmp分別代表自由空間模型和多路徑衰減模型中的功率放大的能量損耗,d為節點間距離,d0是通信距離分界值.

2.2 網絡模型

本文假設網絡區域內的節點具備以下性質:

1)網絡節點與基站位置固定,基站能量無限制;

2)節點間可自由通信,節點初始能量相等;

3)節點地位相等并具有同等機會充當簇首;

4) 任一節點均可依據節點接收信號強度值RSSI計算自身到對方節點的近似距離[12];

5)節點可根據需要調整自身發射功率.

本算法網絡結構采用非均勻分簇結構,使得距離越靠近基站、簇的規模越小,進而為簇首進行簇間數據轉發節省更多能量.

3 算法設計

URBF算法由三部分構成:簇首選舉,簇內通信與簇間路由.本文主要工作是在非均分簇算法的基礎上,對簇首選取以及簇間路由的建立進行設計.

3.1 簇首選取思想

通過模糊評判法選取簇首時,如果各指標權重隨機確定,會使得指標實際影響程度缺乏客觀性,導致評判缺乏客觀性,不利于平衡簇首能耗.如果對其權重有客觀實際的度量,則更能準確反映節點自身“實力”的大小.

熵權法,作為一種客觀賦值法,具有客觀性強、可信度大的優勢,且近年來在多屬性決策問題中,熵權法已在工程技術等領域得到廣泛應用,且應用后所得評價結果與實際情況相吻合,說明在研究中采用熵權法確定評價指標權重一定程度上具有科學性和可行性,這樣做能夠更客觀地反映各評價指標的實際影響度及對評判結果的客觀貢獻率.

在模糊綜合評判中,權重反映了各因素指標的重要性程度,權重對評判結果有直接的影響.鑒于以上分析,本文通過優化的模糊評判選取簇首,提高簇首質量.

模糊評判法選取簇首具體過程:

首先,確定節點指標隸屬函數;

其次,熵權法確定指標權重;

最后,通過模糊綜合評判值確定簇首.

3.1.1 節點指標隸屬函數

本文主要從相對剩余能量、傳輸距離和鄰居節點密度三個方面對指標進行分析確定.

1)相對剩余能量

能量是簇首節點首要考慮的因素,定義節點相對剩余能量的隸屬函數Cm1為節點當前剩余能量與簇內其它節點(假設節點數為S個)平均剩余能量之比,如式(3):

(3)

2)傳輸距離

本文從簇內能耗最小化出發,定義節點傳輸距離的隸屬函數Cm2,即待選簇首節點到簇內其它節點間平均距離作為簇首選取指標,如式(4):

(4)

3)鄰居節點密度

一個節點其鄰居節點密度越高,則鄰居節點數也就越多,則與其傳輸數據時平均耗能也就越低,因此鄰居節點密度Cm3也應作為簇首選舉的一個指標.

3.1.2 熵權法確定指標權重

簇內第m個節點的第n個指標權重確定的過程:

1)通過式(5)歸一化處理得到標準的指標隸屬函數:

(5)

其中,min(Cmn)、max(Cmn)為指標隸屬函數的原始最小值、最大值.

確定簇內節點指標隸屬度R′如矩陣(6):

(6)

2)通過式(7)求取第n個指標熵值:

(7)

3)通過式(8)求第n個指標的權重:

(8)

為避免各指標權重選取不當進而使選舉結果陷入局部最優,可采用權重調整策略如式(9)所示:

(9)

其中,Tmax、k分別為最大迭代次數和當前迭代次數.

由式(9)可知,通過節點指標值本身的大小、迭代次數和權重值進行指標系數的調整,這種方法實現了指標系數動態變化,前期指標系數變化較慢,維持了算法全局搜索能力.隨著輪數的運行,各指標值也逐漸呈現不同程度的減小,指標系數變化較快,提高了算法的求解效果,二者平衡考慮使得算法在局部搜索與全局尋優之間取得較為客觀的結果,這為算法跳出局部最優提供了幫助.

3.1.3 模糊評判確定簇首

由指標隸屬度矩陣和指標權重,通過式(10)運算后可得到各簇內各節點的模糊綜合評判值:

(10)

(11)

3.2 簇內通信

簇首確定后,簇首根據簇內節點數產生TDMA表發給簇內其它節點,告知其它節點何時將數據信息發送給簇首,當各簇簇首收集簇內數據后,開始建立簇間路由.

3.3 簇間路由

對于各層簇首當選下一跳節點根據相鄰兩層的鏈路評估值確定.鏈路評估值包含三部分:兩層簇首間距離、待選下一跳簇首(NH-ch,Nest-Hopclusterhead)與基站(BS)距離、待選下一跳簇首的能量,這樣做充分考慮了傳輸距離和能量,有利于提高了簇間路由的質量,如式(12)所示:

(12)

其中,分母部分為待選為下一跳簇首與上一跳簇首間、與基站間兩者距離之和,分子為待選下一跳簇首能量.

簇間路由具體構建過程為:

由第L層中的評判值最大的簇首節點為源點,通過式(12)查詢與第(L-1)層中各簇首間的鏈路評估值最大的簇首節點并將其作為自己的下一跳,由第(L-1)層中的下一跳簇首節點由式(12)查詢與第(L-2)層中的各簇首間鏈路評估值最大的節點并將其作為自己的下一跳,以此類推直到確定第1層中的下一跳節點,第一層中未當選下一跳節的簇首與基站直接通信,簇間路由建立示意圖如圖1所示.

圖1 簇間路由過程示意圖Fig.1 Schematic diagram of the inter-cluster routing process

4 仿真分析

4.1 參數設置

考慮到URBF算法對網絡性能影響,仿真中做以下假設:

1)仿真過程不考慮信道衰落引起的數據傳輸誤差問題;

2)傳輸路徑帶寬充足以盡最大努力降低擁塞度;

3)節點發送的數據均可以正常收發與接收;

4)路由重新選擇時,節點先前收到的數據不再保留,以避免數據重復發送浪費能源;

實驗仿真通過Matlab進行,網絡區域面積為(200,200)m,節點初始能量0.5J,其它參數設置如表1所示.

表1 仿真參數表Table 1 Experimental parameter list

4.2 仿真分析

將URBF算法與目前常用的EBFA、DEBUC兩種算法在網絡能量消耗、網絡生命周期、網絡能耗均衡性以及網絡數據傳輸量等方面進行比較,對比結果如下.

4.2.1 網絡能量消耗

圖2是三種算法在網絡能耗方面的仿真對比結果.

圖2 網絡能量消耗對比Fig.2 Comparison of network energy consumption

由圖2可知URBF算法一開始便保持較低的能耗,至200輪后優勢更加明顯.表明URBF算法有效地減緩了能耗速率,降低了網絡能耗.URBF算法選取簇首時,通過熵權法和節點綜合評判值綜合衡量節點性能,有效地避免了簇首隨機選取導致能耗過大的現象,對提高能量利用效率起較大作用.

4.2.2 網絡生命周期

三種算法在網絡生命周期方面的對比情況如圖3所示.

圖3 網絡生命周期對比Fig.3 Comparison of network lifetime

由圖3可知,三種算法的首個節點死亡以及全部節點死亡時間,URBF算法都最晚,DEBUC次之,EBFA最早.說明URBF算法網絡生命周期相比其它兩種算法有一定提高.

4.2.3 網絡能耗均衡性

節點剩余能量方差是衡量網絡能耗的均衡程度指標,剩余能量方差值越小,則表明節點間能量差異相對越均勻.

圖4 節點剩余能量方差對比Fig.4 Comparison of the remaining energy variance of nodes

由圖4可知,運行100以后,三種算法的剩余能量方差明顯發生了改變,EBFA算法的剩余能量方差波動最大,DEBUC算法較EBFA算法有了較大改善,而URBF算法的能量方差曲線一直較為平穩、波動范圍小,說明URBF算法有效的均衡了能耗.

4.2.4 網絡數據傳輸量

網絡數據傳輸量即基站接受數據量是衡量網絡服務質量優劣的標志,圖5是三種算法在基站接受數據量方面的對比情況.

圖5 數據傳輸量對比Fig.5 Comparison of data transmission

從圖5看出,200輪前UFBF的數據傳輸量稍微高于其它算法,但200輪后發送數據量開始增多,400到900輪之間尤為明顯,從整體來看URBF算法傳輸數據量較EBFA和DEBUC算法有所提高.UBFF算法通過各層簇首節點間的鏈路評估值完成簇間多跳路由的建立,提高了簇間路由的效率和路徑的健壯性,為傳輸更多數據提供了保證.

5 結束語

提高能量利用率、延長網絡生命周期是路由協議設計的重要目標.本文研究了一種模糊評判的非均勻分簇路由優化算法.由熵權法確定節點指標的權重,提高了簇首的整體性能;在簇間路由階段,通過各層簇首節點間的鏈路評估值完成簇間多跳路由的建立,提高了簇間路由的效率和路徑的健壯性,仿真表明本文提出的算法延長了網絡生命周期,從整體上降低了網絡能耗.