WSN中基于多因素的能量優化分簇路由算法

田紀堯,劉廣鐘

(上海海事大學 信息工程學院,上海 201306)

0 概述

無線傳感器網絡(Wireless Sensor Network,WSN)是一種分布式傳感網絡,其由微小、能量有限的傳感器組成,主要應用于環境監測、軍事、航空、工業、商業等領域[1]。目前基于分簇的分層路由已經被證明是提高網絡能量利用效率最有效的技術之一[2]。通過分簇,普通節點收集信息,簇頭對信息融合整理進而傳輸至基站。傳統的LEACH[3]協議采用“隨機選取簇首,單跳傳輸至基站”的機制。由于簇首的選取帶有一定隨機性,簇首任務繁重,較其他的節點要消耗更多的能量,這樣會加快低能量節點的死亡。同時,在簇間路由階段,簇首選擇單跳方式直接與基站通信,導致距離較遠的節點由于長距離傳輸而增加傳輸能耗,也會加快節點死亡。因此,無線傳感器網絡研究的主要目標是最小化能量消耗并延長網絡壽命[4]。

模糊算法在無需建立數學建模基礎上[5],對多個因素綜合評價得出優先級,并以傳統的蟻群優化(Ant Colony Optimization,ACO)[6]算法作為路由選擇的基礎。由此,本文提出一種基于多因素的能量優化分簇路由算法,利用模糊理論推選出最優簇首,引入泰爾指數改進蟻群算法的轉移概率函數,并在信息素更新過程中建立多因素線性規劃模型提高能量優化率,以延長整個網絡生命周期。

1 相關工作

針對LEACH分簇協議存在的不足,研究人員提出多種關于改進的分層路由協議。文獻[7]提出LEACH-C協議,通過基站記錄所有節點的位置和能量狀況,依據數據信息求出網絡整體的能量剩余狀態,然而每個節點需要與基站通信,簇首的選取過程采取集中式,由基站負責挑選簇首,從而增大整個網絡的能量消耗,并不適用大規模網絡。文獻[8]提出EEUC協議,該協議通過節點與基站之間不同距離劃分為規模的簇,然而在該協議的設計過程中并未將節點的剩余能量考慮其中,極易出現在后續輪的簇首推選中,使能量較低的節點成為簇首。文獻[9]為延長網絡生命周期提出了REAC-IN協議,然而結合節點剩余能量和區域平均能量確定簇首的方式極易造成距離基站遠的節點承擔巨大的運輸任務。文獻[10]以聚類方式按照節點之間的位置分為不同區域,以節點剩余能量確定區域之間的距離,但個別節點剩余能量較多,無法實現傳輸能量動態平衡。文獻[11]提出的BEERA協議改進LEACH閾值和最優半徑選擇簇頭,以跳數確定簇間路由,然而跳數小的2個簇頭之間會一直擔任轉發任務,降低了網絡負載均衡性能。

近年來,眾多學者將模糊理論和蟻群算法應用于分簇路由協議。文獻[12-13]的2種協議采用模糊理論,基于距離和能量2個要素推選簇首,摒棄隨機概率選擇簇首,較LEACH相比有效延長了網絡壽命。CHBFT[14]雖采用模糊規則算法推選簇頭,然而在簇間路由確定中僅限于小規模網絡。文獻[15]對基于ACO的分簇路由協議進行了全面審查,提到以能量為基礎的BABR、EEABR、ACO-QoSR等和以位置為基礎的ASTRL、UMM、ODTS等均未綜合考慮節點之間的相對距離和剩余能量,以致簇首能量消耗過快,從而縮減網絡整體生命周期。文獻[16]提出一種基于蟻群的新路由算法,考慮節點之間的通信距離、剩余能量,利用蟻群算法尋找到最優路徑,此過程未考慮信息素更新帶來的局部消耗過快問題。文獻[17]提出CFEL協議,該協議應用模糊規則并基于距離和能量2個要素推選合適的簇首。該協議要求每個節點配置GPS,但未考慮節點密度這個變量,一方面增加了節點的整體花銷,另一方面選取簇首中密度較大的簇可能會造成消耗能量快,同時,其對簇間路由階段沒有進行改進,不利于提高網絡利用率。

本文提出一種基于多因素的能量優化分簇路由算法。該算法通過將模糊理論和蟻群優化相結合選取最優簇首和簇間路由,從而加強簇首選舉質量,提高負載均衡性能。

2 系統模型

2.1 網絡模型

本文算法采用與文獻[18]類似的網絡模型,MFEO協議對無線傳感器網絡作出以下假設:

1)區域內的所有節點隨機分布在檢測區域內,所有節點初始能量相同且基站能量無限。

2)節點數為100,檢測區域面積為100 m×100 m。

3)節點沒有配備GPS天線,因此它們無法感知位置信息,相反可以基于接收信號強度來計算節點之間的近似距離。

4)所有節點具有相同屬性和性能,既可以擔任普通節點,也可以擔任簇首,簇首節點會進行數據融合去除冗余。

2.2 能量模型

本文使用與經典LEACH協議相同的一階無線電模型[19],根據發送點與接收點之間的距離采用自由空間和多路徑衰減模型,無線電模型如圖1所示。

圖1 無線電模型Fig.1 Radio model

節點將kbit數據發送到距離為d的節點消耗能量為:

(1)

節點接收kbit數據消耗的能量為:

Erx(k)=k×Eelec

(2)

由式(1)可知:

(3)

其中,Eelec為節點發送或接收1 bit數據所消耗的能量,εf-s與εm-p分別為自由空間模型和多路徑衰減模型中功率放大的能量損耗,單位分別為J/(bit·m2)和J/(bit·m4),d為兩節點之間距離,d′為傳輸距離閾值,當消息傳輸距離小于d′時采用自由空間模型,否則使用多徑衰落模型。

3 算法描述

本文算法每輪分為分簇階段和數據傳輸階段。在分簇階段,一方面完成網絡分簇,另一方面選出簇首。通過改進的模糊規則算法,綜合考慮節點因素推選出合適的簇首,在每個簇中只有一個簇首,完成數據收集、轉發和數據融合去除冗余傳至基站。在數據傳輸過程中,傳統意義的“蟻群算法”設計中缺少能耗與通信質量均衡,通過對蟻群算法中的概率轉移模型進行優化并且在信息素更新過程中建立能量消耗與通信質量線性規劃,從而優化全局信息素的更新。

3.1 網絡分簇

采用非均勻分簇方式將網絡分為大小不同的區域,首先選出部分節點作為候選節點,存儲于集合TC(i),其次基站通過給定的功率向所有的節點發送廣播,按照式(4)中的能量競爭半徑分簇[20]。

c1+c2=1

(4)

3.2 簇首選取

模糊控制器通過使用模糊思維對建立的數學模型進行控制,其結構包括模糊變量輸入、建立隸屬度函數、模糊規則表和解模糊過程[21]。MFEO算法在簇頭選取階段以候選節點的相對剩余能量、相對中心度、節點所在簇相對密度3個變量作為輸入變量,通過變量模糊化、模糊規則制定、解模糊化,得到一個機會變量,從而推出最優簇頭。

3.2.1 模糊變量的確定

確定模糊變量主要有以下3點:

1)相對剩余能量

節點的相剩余能量是指候選節點TTC(i)的剩余能量和所在簇中的所有節點平均剩余能量之比。在網絡的運行過程中,能量作為網絡生命周期持續運行的基本條件,只有相對剩余能量較多,成為簇首的可能性更大,則相對剩余能量為:

(5)

2)相對中心度

節點的相對中心度計算公式為[22]:

(6)

其中,xi和yi代表候選節點i的橫坐標和縱坐標。

候選節點的相對中心度是指節點與其鄰居節點的緊密程度,緊密程度越高,節點之間通信距離越短,消耗的能量越少,則相對中心度為:

(7)

其中,D(X)為當前候選節點的中心度,Dmax和Dmin分別代表所在簇內最大、最小中心度。

3)相對密度

節點密度是指在一定的通信范圍內節點附近密集程度(具體而言是指一個節點在信息交流范圍內節點的數目),節點密度計算公式為:

(8)

其中,Sum(i)為當前候選節點i通信范圍內的鄰居數目,RRD代表式(7)中的相對中心度。

針對一個簇內的候選節點,簇頭擔任的任務是將各節點收集到的數據進行融合進而轉發至基站,若鄰居多的節點,其任務工作量更加艱巨,因而考慮相對密度這一變量,如式(9)所示。

(9)

從式(5)、式(7)、式(9)可知,在簇首選取過程中,綜合考慮節點的剩余能量、中心度、密度3個因素,候選節點的相對剩余能量越大,與鄰居節點越緊密以及密度越大,成為簇首的可能也越大。下文將對3個模糊變量模糊化,即建立隸屬度函數和模糊規則庫。

3.2.2 模糊變量的模糊化

模糊規則控制即通過輸入精確值,模糊處理綜合多個指標進行分析,最后經過解模糊過程輸出精確值。候選節點相對剩余能量、相對中心度、相對密度3個變量作為模糊輸入值,機會變量作為輸出變量。中間的模糊化過程包括建立隸屬度函數和模糊規則庫。

在建立隸屬度函數過程中,通過輸入變量和輸出變量確定參數及等級,如表1所示。

表1 隸屬度函數參數及等級Table 1 Parameters and levels membership function

隸屬度函數的確定帶有一定的主觀性,需要參考一定的經驗。相對剩余能量采取梯形隸屬度函數;相對中心度和相對密度采用梯形隸屬度函數和高斯隸屬函數,如圖2所示。

圖2 變量隸屬度函數的輸入Fig.2 Input of variable membership function

3個變量作為輸入值進行模糊運算,通過模糊規則將輸出變量即機會變量Chance分為7個等級,如圖3所示。

圖3 機會變量隸屬度函數的輸出Fig.3 Output of the membership function of the chance variable

模糊規則的制定基于3條輸入變量,共有3×3×3=27條規則。MFEO算法采用“IF-THEN”規則,即IFX、Y、Z、THENC,其中,X代表相對剩余能量模糊集合,Y代表相對中心度模糊集合,Z代表相對密度模糊集合,C代表機會變量對應的模糊集合。如對于簇內的每個節點,相對剩余能量越多,相對中心度越緊密以及相對密度越大,則成為簇頭的機會更大。模糊規則如表2所示,其中括號中數字為節點數。

表2 模糊規則Table 2 Fuzzy rules

3.2.3 解模糊化

解模糊化的過程則是把經過模糊規則處理的數據通過一定方法轉變成具體的數值,MFEO算法采用式(10)提出的重心法COG(Centre of Gravity)[23],計算公式如下:

(10)

重心法為每一個節點求出一個確定的數值,數值的大小說明了簇首當選的優先級,則通過綜合考慮節點的剩余能量、鄰居節點的緊密程度及相對密度,從而確定最優簇首。此時,在通信半徑d范圍內,最佳的簇頭選取完畢并存儲于集合CH(i)中,范圍內的其他節點自動轉為普通節點。之后,簇首進行發送廣播,普通節點收到廣播后選擇最近范圍內的簇首發送請求入簇請求,簇首收到廣播后將請求的節點加入到自己的鄰居表中,隨后向簇中的成員發送確認消息并分配TDMA時隙,簇頭則會通過計算自己的時隙大小,根據其時隙的數值大小向簇首發送數據。

3.3 簇間路由

在分簇完成后,選擇合適的簇間路由是數據傳輸階段的關鍵。為實現能量消耗的均衡,提高網絡數據傳輸的有效性,采用蟻群算法作為路由選擇的基礎,引入經濟學中的泰爾指數綜合考慮剩余能量與簇首間的距離,進而優化轉移概率模型,并且在信息素更新過程中引入能耗因子建立多因素線性規劃模型。

3.3.1 蟻群算法轉移概率函數的優化

基于傳統的轉移概率函數,數據包傳輸過程假設為“螞蟻”尋徑過程,t時刻螞蟻k從節點m選擇下一跳為n的概率函數為:

(11)

其中,τmn為路徑(m,n)上的信息素,m和n分別代表2個簇首,初始信息素為τ0,存儲在簇首的路由表中,ηm,n為局部啟發因素,α和β分別為信息素權重、啟發因子權重,q代表下一跳的節點,Mi代表下一跳集合。“螞蟻”可以根據信息素及局部的啟發因素確定下一跳。

經濟學中的泰爾指數是一種度量個人或社會人均經濟分配不均的方法,計算公式如式(12)所示。

(12)

其中,xi、pi分別代表第i個樣本單位指標值和人口,X、P分別代表總體樣本單位的指標值和人口綜合[24]。簇首選擇下一跳過程中需要考慮多種因素,簇內節點將數據傳輸至簇首時,簇首的剩余能量不均以及各簇首之間相對距離不同,從而簇間路由的確定涉及到多因素不均的情形。因此,將泰爾指數引入到簇間路由確定過程中,即:

(13)

(14)

(15)

在新的轉移概率函數中,優化局部啟發因素,綜合考慮簇首的剩余能量與相對距離,防止在下一跳簇首選取過程中存在選擇的節點剩余能量高且相對距離遠的情況,進而選擇下一跳更具有針對性。最后選取的簇首按照概率大小依次存入集合Mnext。

Mnext=argmax(Pm,q),?q∈Mi

(16)

3.3.2 信息素更新

前向螞蟻從初始地到目的地后,后向螞蟻完成信息素的更新。由于“正反饋”的特性,最短路徑上的信息素含量會升高,導致會有更多的螞蟻通過此路徑,這樣帶來的結果使得該路徑的能量不斷地被消耗,加速該路徑上的節點快速死亡。此外,由于非最優路徑上的信息素會隨時間不斷揮發,最初找到的最佳路徑不再是需要的“合適路徑”。因而,在信息素更新過程中,為提高全局路徑的利用性,信息素更新采用局部和全局相互結合的規則。

局部更新公式為:

(17)

為防止信息素更新過程中出現局部更新滯留或者全局更新揮發過快的情況,綜合網絡能量和通信距離建立一個線性規劃模型,提高整體網絡的通信效率。路徑的通信能量取決于簇首與下一跳的相對能量值,通信距離則需要當前節點與下一跳之間的相對距離值表示,為兩者建立的線性規劃問題如式(18)所示。

α+β=1,m,n∈Mi

(18)

當一次迭代后所有的螞蟻到達目的地,將式(18)引入其中,進行全局信息素更新。

(19)

其中,Qk為螞蟻k釋放的信息素濃度,Lk為螞蟻k從目的地到終點所記錄的最佳路徑。

通過上述公式可知,在信息素更新過程中,綜合考慮簇首之間的相對能量值及距離問題,同時采用局部和全局更新方式,可有效保持信息素更新的動態平衡。

3.4 復雜度分析

時間復雜度是衡量算法計算量的標準,本節主要分析MFEO算法的時間復雜度。MFEO算法將整個分簇路由協議分為2個階段:利用模糊算法進行簇首的選舉與優化蟻群算法的轉移概率函數,完成簇間路由的確定。2個階段的偽代碼如下:

偽代碼1簇首選舉過程

Begin

1.For i=1 to S(i)

2.Sink node broadcast to each node i with a given power

3.Calculate the R(i) based on 式(1)

4.End For

5.For i=1 to TC(i)

6.Launch fuzzy logic to calculate RE(TC)、RD、RCD based on 式(5)、式(7)、式(9)

7.Output Chance variable for each TC(i)

8.End For

9.Select Cluster Headers saved in CH(i)

10.For i=1 to CH(i)

11.Each Cluster Header sends message to ordinary nodes in R(i)

12.Sensor nodes join cluster and allocate the TDMA

13.End For

End

偽代碼2簇間路由過程

Begin

1.For each Cluseter Header in CH(i)

2.Compute pm,n(t) based on 式(15)

3.Stored by probability in Mnext(i)

4.End For

5.While (Mnext(i)≠?)

6.Update pheromone based on 式(19)

7.Each Cluster Header establish inter-cluster routing dynamically based on 式(18)

8.End While

End

在第1階段中,核心部分為第5步～第12步。初始化階段基站發布消息通過RSSI測出每個節點到基站的距離。假設參與簇首競選的有NNT個,通過模糊算法有M個候選簇首競選成功,簇首發布M條廣播,通信半徑內其他N-M個節點自動轉為普通節點,發布入簇的消息,從而分簇階段完成。在第2階段中,M個簇首通過蟻群算法發布M條消息,按照轉移概率大小進行排序,進而建立M條簇間路由,因此,整個網絡復雜度為:O(N)=1+NNT+M+N-M+M=(T+1)N+M+1。

4 仿真結果與分析

4.1 參數設置

采用Matlab平臺對本文提出的MFEO和已有的LEACH、CFEL算法進行仿真。仿真環境是在一個長和寬為100 m的正方形區域內隨機部署100個無線傳感器節點。部分參數如表3所示,無線傳感器網絡節點部署仿真模型如圖4所示。

表3 部分仿真參數Table 3 Part of simulation parameters

圖4 無線傳感器節點部署示意圖Fig.4 Wireless sensor node deployment

4.2 仿真性能指標分析

MFEO算法在簇首選取階段采用模糊規則算法,以“輪”為基礎,與CFEL算法相比加入“相對密度”要素,與LEACH相比未采用隨機概率選取簇首,以提高簇首選擇的針對性;在簇間路由階段,采用優化的蟻群算法,同時考慮簇首能量與相對距離,此外,建立線性規劃問題,加強“信息素”更新過程,提高下一跳選擇的針對性。實驗分別從網絡生命周期、網絡能耗、網絡的負載均衡3個方面進行討論分析。

4.2.1 網絡生命周期

圖5是MFEO與CFEL、LEACH算法在死亡節點數目的對比曲線。實驗以4 000輪為基礎,死亡節點數是網絡生命周期的體現,死亡節點越少,則網絡的生命周期則越長。從圖5可知,3種算法出現死亡節點區間輪數分別為[1 500,1 800]、[1 800,2 000]、[2 500,3 000]。由于MFEO在簇首選取階段,綜合“相對能量”“相對中心度”“相對密度”3個要素。在距離普通節點遠、處于稀疏的情況下提高簇首選取的高效性,所以節點相對剩余能量多、鄰居節點多、彼此之間相對距離近的節點更有可能成為簇首。同時,在簇間路由階段,對蟻群算法中的轉移概率函數進行優化,在選擇下一跳過程中,不僅考慮相對剩余能量,同時考慮簇首之間的相對距離,從而提高了選擇下一跳的合理性。因此,MFEO在能量的消耗方面較CFEL、LEACH算法有所提高,從而延長了整個網絡的生命周期。

圖5 LEACH、CFEL、MFEO 3種算法死亡節點數對比Fig.5 Comparison of the dead nodes number of LEACH, CFEL,MFEO algorithms

4.2.2 網絡能耗

維持無線傳感器網絡中的節點壽命主要是節點能量,因此,節點剩余能量越多,整個網絡維持的時間越久。圖6是MFEO與CFEL、LEACH三者的節點剩余能量對比。從圖6可知,在整個網絡的運行過程中,MFEO在同一輪中與CFEL、LEACH相比,剩余能量較多,說明MFEO明顯降低了能量的消耗。這得益于在選取簇首過程中綜合考慮了多種因素,因而選出的簇首更具有合理性,其次在數據傳輸過程中,普通節點將數據傳輸至所在簇的簇首后,優化搜索最佳路徑方式,減少了網絡傳輸中能量消耗。

圖6 LEACH、CFEL、MFEO 3種算法節點剩余能量對比Fig.6 Comparison of the remaining energy of nodes of LEACH,CFEL,MFEO algorithm

4.2.3 網絡負載均衡

圖7為MFEO與CFEL、LEACH算法節點平均方差對比。在初始的運行過程中,三者具有相同的走向,MFEO與CFEL、LEACH相比,出現波峰的時間較晚,并且數值大于后者,從而說明了MFEO提高了負載均衡能力。這主要是由于在簇首路由建立過程中,不僅要考慮數據的傳輸,同時綜合考慮數據傳輸過程中通信質量與能量消耗的均衡,為兩者建立線性規劃,從而減少數據傳輸造成的節點能耗不均的問題。

圖7 MFEO、CFEL、LEACH 3種算法節點平均方差對比Fig.7 Comparison of the average variance of MFEO,CFEL,LEACH algorithms

5 結束語

為降低WSN中的能量消耗、延長網絡的生命周期,本文提出一種基于多因素的能量優化分簇路算法(MFEO)。綜合相對剩余能量、相對中心度、相對密度3個變量,利用模糊規則算法選出最優簇首,引入經濟學中的泰爾系數改進概率轉移函數模型,優化信息素的更新過程,同時建立通信質量與能量消耗線性規劃模型,以選擇簇首之間的最佳路徑。仿真結果表明,與CFEL、LEACH算法相比,MFEO算法能明顯提高網絡生命周期并降低能量消耗。