基于改進螢火蟲聚類的異構WSNs能耗優(yōu)化路由算法*

羅 劍,畢曉東

(浙江經濟職業(yè)技術學院數字信息技術學院,杭州310018)

無線傳感器網絡(WSNs),是由隨機投放在監(jiān)測區(qū)域內的大量低成本且擁有傳感、計算、數據處理和通信能力的微型節(jié)點構成的自組織網絡,具有部署迅速、實時性強等優(yōu)點。通過感知、收集和融合目標對象的觀測數據,將預處理后的信息發(fā)送回基站,擴展了人們洞悉外部世界的能力[1-2]。根據節(jié)點計算能力、內存容量、通信帶寬和初始能量等的差異,WSNs可以分為同構型WSNs和異構型WSNs。因為外界環(huán)境的制約,傳感器節(jié)點通常由電池供電,自身攜帶能量有限,無法得到及時補充。僅初始能量不同的節(jié)點所組成的能量異構型WSNs在維持網絡節(jié)點數量不變、降低成本開銷的前提下增加了網絡能量,特別具有研究價值[3]。

在傳感器節(jié)點中動態(tài)均衡地分配通信和計算負載、從而節(jié)約能耗是WSNs路由算法需要解決的關鍵問題,很大程度決定了整個網絡的生命周期[4-5]。分簇路由算法綜合考量節(jié)點發(fā)送、接收數據的固定能耗和跟隨傳輸距離遠近改變的發(fā)送端無線功放能耗,將網絡劃分為若干本地簇,簇頭消耗額外能量負責從簇成員接收數據并發(fā)往基站。分簇結構使得網絡整體擴展性良好,相比節(jié)點與基站直接通信和節(jié)點間最小傳輸能量路由(MTE)性能更優(yōu),已經成為WSNs路由算法的研究重心,得到國內外學者的廣泛關注[6]。LEACH算法是最早提出的WSNs分簇路由算法,利用合適的閾值概率公式,保持網絡節(jié)點在運行周期內的各個輪次擁有同樣的競爭簇頭概率以平衡節(jié)點間能耗,但該算法只適用于節(jié)點初始能量相同的WSNs[7]。根據高級節(jié)點相對全體節(jié)點的數量占比和高級節(jié)點多于普通節(jié)點初始能量的比例,SEP算法修改閾值概率公式,按照初始能量的差異維持節(jié)點成比例地消耗能量,有效地延長了異構WSNs的穩(wěn)定期(第1個節(jié)點死亡前)[8]。DEEC算法通過預測節(jié)點每個輪次的殘余能量,修正不同節(jié)點競爭簇頭的概率,比較SEP算法獲得了更長的網絡生命期[9]。

上述分布式隨機分簇算法無須了解節(jié)點的具體位置,本地化自適應簇生成過程計算簡單,減少了網絡控制流量。然而隨機算法存在兩個問題:首先,每個輪次的簇頭數圍繞最優(yōu)簇頭數波動,加大了網絡通信負載;其次,隨機選擇的簇頭位置可能集中于局部區(qū)域,造成部分簇頭與成員間距離過遠,不利于平衡節(jié)點能耗。許多WSNs應用中節(jié)點位置預知,如果依據最優(yōu)簇頭數采用聚類算法獲得更為緊密的本地簇,同時算法改進減少的網絡能耗大于網絡控制包負載和聚類計算的多余能耗,完全可能大幅度地提升網絡能效。

螢火蟲算法是一種仿生螢火蟲個體的種群趨光性特征的群智能優(yōu)化算法,起初用于求解非線性數值優(yōu)化問題[10]。為了將該算法引入聚類分析領域,定義目標函數為聚類中心與簇成員間距離和,目標函數值越小螢火蟲亮度越高。使用UCI機器學習庫的13類典型基準數據集與其他11種聚類算法進行比較,結果表明螢火蟲算法擁有良好的整體性能[11]。該算法進一步改善聚類效果、提高穩(wěn)定性和降低計算負載的研究,圍繞著螢火蟲移動位置的選取策略和最優(yōu)類中心擾動的快速收斂展開[12-13]。

綜上所述,本文提出的IFCEER算法的基本思路是:WSNs初始化階段節(jié)點將位置坐標一次性發(fā)往基站,使用改進螢火蟲算法完成對全體高能節(jié)點的第1次聚類。隨后運行的每個輪次分為簇形成和數據傳輸兩個階段。簇形成階段向全網廣播主副簇頭消息,節(jié)點加入臨近的簇。數據傳輸階段簇頭接收和融合成員數據,在事先規(guī)劃指定的TDMA時隙發(fā)往基站。同時,該階段根據閾值條件預測節(jié)點能量,決定是否重新執(zhí)行聚類。因此,網絡運行第1輪之后簇形成階段只有在滿足任意簇頭能量小于指定閾值條件的輪次才會執(zhí)行,否則保持原有簇結構。實驗數據表明,提出的IFCEER算法平衡和降低了通信能耗,有效地延長了網絡壽命。

1 系統(tǒng)模型

1.1 多級能量異構WSNs模型

考慮n個節(jié)點隨機分布于M×M監(jiān)測區(qū)域的多跳傳感網絡。假定S為網絡內全體傳感節(jié)點集合,如式(1)所示:

S={s1,…,si,…,sn}

(1)

式中,si表示第i個傳感節(jié)點。

多級能量異構WSNs中節(jié)點初始能量在閉區(qū)間[E0,E0(1+αmax)]內隨機分布,E0是節(jié)點能量下界,αmax決定了節(jié)點的最大能量。節(jié)點si的初始能量為E0(1+αi),其中αi∈[0,αmax]。因此,網絡的整體能量可以描述為式(2):

(2)

模型具有以下特點:①基站位置固定于監(jiān)測區(qū)域中心,能量和計算資源不受限制,通信范圍覆蓋整個監(jiān)測區(qū)域。②節(jié)點擁有全網唯一的標識ID,位置固定。③基站通過某些渠道,如節(jié)點裝備GPS等,了解每個節(jié)點的定位信息。④節(jié)點的發(fā)射功率以及通信半徑可以根據需要自動調整。⑤鏈路對稱,即已知發(fā)射端的發(fā)射功率,接收端可以根據接收到的信號強度估算兩者距離。⑥節(jié)點以固定速率監(jiān)測環(huán)境,定期上報監(jiān)測數據。

1.2 能量消耗模型

本文采用文獻[7]的能耗模型,即一階無線電模型。發(fā)射方能耗ETX(l,d) 、接收方能耗ERX(l)和數據融合能耗Ec的具體公式如式(3)～式(5):

ETX(l,d) =ETX-elec(l)+ETX-amp(l,d)

(3)

ERX(l)=ETX-elec(l)=lEelec

(4)

Ec=lEDA

(5)

假定在一個輪次內每個簇成員發(fā)送l比特監(jiān)測數據和自身殘余能量等級到主簇頭,因為殘余能量占用數據位遠小于l比特,所以忽略不計。主簇頭將接收的全部信息融合成(1+φ)l比特信息包經副簇頭發(fā)往基站。其中l(wèi)比特是融合的本地監(jiān)測數據,φl比特包含簇全體節(jié)點殘余能量信息。根據前述能耗模型,得到每個輪次主簇頭能耗EMCH、副簇頭能耗EVCH和簇成員能耗EnonCH的相關公式如式(6)～式(8):

(6)

(7.1)

(7.2)

(8)

式中,k為簇數,dtoCH為簇成員與簇頭間的平均距離,dtoBS為簇頭與基站的平均距離,E[·]為期望值。由于簇頭和基站間距離可能較遠,式(7.1)對應自由空間模型,式(7.2)對應多路徑衰減模型。假設節(jié)點滿足均勻分布,則[8]:

(9)

(10)

式(10)是選擇采用自由空間模型或者多路徑衰減模型的依據,同理計算得到:

(11)

(12)

在一個輪次內簇消耗能量如下:

(13)

因為k≤n,所以一個輪次內網絡消耗的全部能量Eround近似于:

(14.1)

(14.2)

式(14.1)對應自由空間模型,式(14.2)對應多路徑衰減模型,兩公式分別對k求導數,得到不同模型下最優(yōu)簇頭數kopt公式如式(15.1)和(15.2)所示:

(15.1)

(15.2)

2 提出的IFCEER算法

2.1 改進螢火蟲聚類

(16)

(17)

式中,nj是Gj中節(jié)點sj的個數。

(18)

亮度值的大小體現了螢火蟲所處位置的優(yōu)劣,目標函數值越小,螢火蟲亮度越高。如果螢火蟲F的亮度大于螢火蟲Q,那么Q將被F吸引,即Q的kopt個分量一一對應地向F的kopt個分量所指示的方向移動。兩個螢火蟲分量的匹配規(guī)則是兩兩之間距離最近,假設Q中第i個分量qi與F的第j個分量fj之間距離rij小于與F的其他分量的距離,則qi向fj指示的方向移動。由于初始位置選取的隨機性,兩個螢火蟲分量間的對應關系可能不具備充分的辨識度,如圖1所示。螢火蟲Q的#4分量與螢火蟲F的#5分量距離更近,但是因為存在Q的#5分量,所以Q的#4分量只能和F的#4分量對應。當kopt增加時,這種隨機匹配的概率同步增加?；谏鲜鲈?算法依次從兩個螢火蟲的分量集合中查找距離最近的點對完成匹配,以維護合適的對應關系。

圖1 螢火蟲分量的對應關系

螢火蟲彼此間吸引度公式為:

(19)

式中,β0為最大吸引度,γ為光強吸收系數。

螢火蟲Q向F移動的位置更新公式如式(20)所示:

(20)

經過螢火蟲之間互相吸引和移動之后得到的本次迭代最亮螢火蟲,按照式(21)進行最優(yōu)類中心擾動,評估再次移動效果。如果亮度優(yōu)于移動前,則移動到新位置;否則保持原來位置不變。

(21)

螢火蟲算法的參數適用于標準化數據,所以需要對節(jié)點集合S進行標準化和歸一化處理,標準化處理公式由式(22)列出:

(22)

改進螢火蟲聚類算法的主要步驟可以描述為:

步驟1 輸入參數。傳感節(jié)點集合S,最優(yōu)聚類數Kopt,螢火蟲群體規(guī)模N,最大吸引度β0,光強吸收系數γ,步長因子α,最大迭代次數τmax。

步驟2 根據式(22)標準化集合S;執(zhí)行N次隨機選擇Kopt個節(jié)點作為螢火蟲個體位置的操作,初始化全體螢火蟲。

步驟3 由式(17)生成螢火蟲各個分量對應的Kopt個聚類中心,根據式(16)計算螢火蟲種群目標函數。

步驟4 將螢火蟲按照亮度由低到高排序,從亮度最低的螢火蟲開始兩兩比較,執(zhí)行次數為N×N。如果Ii

步驟5 最亮螢火蟲根據式(21)圍繞其聚類中心擾動。如果得到的目標函數小于擾動前,則移動到新位置;否則保持原位置不變。

步驟6 達到最大迭代次數τmax停止算法,否則轉到步驟3。

步驟7 輸出最亮螢火蟲V。

2.2 算法實現

IFCEER算法支持周期性地遠程監(jiān)測WSNs,網絡按照運行時序劃分為若干輪次(round),每輪由兩個部分組成:簇形成階段和數據傳輸階段,網絡初始化還包括一個獨立的信息收集階段,如圖2所示,T1?T2。在每個輪次內產生分簇并傳輸數據,網絡經歷的輪次越多,說明網絡運行時間越長,即網絡壽命越大。

圖2 IFCEER算法運行時序

2.2.1 信息收集階段

(23)

參照式(15.1)或者式(15.2)確定最優(yōu)簇數Kopt,對全體高能節(jié)點集合SHN運行改進螢火蟲聚類算法,得到全局最優(yōu)簇集合。

2.2.2 簇形成階段

在每個簇中,選擇距離簇聚類中心最近的節(jié)點作為簇內通信的主簇頭(MCH),選擇距離基站最近的節(jié)點作為與基站通信的副簇頭(VCH)。主副簇頭策略平衡了簇內負載,縮短了通信距離[15]?；鞠蛉W廣播簇頭消息CH_stat_Msg(MCH_ID,VCH_ID),全體節(jié)點接收到該消息后,副簇頭根據指定的主簇頭加入簇,其他節(jié)點的入簇機制與LEACH算法相同[7]。

圖3 IFCEER算法流程

2.2.3 數據傳輸階段

(24)

因此,聚類只在當前簇頭預測能量低于閾值Eth或者有節(jié)點死亡的少數輪次才會執(zhí)行,從而盡可能地減少網絡通信負載和計算延時,增強魯棒性和適用性,IFCEER算法流程如圖3所示。另外,一次聚類之后,沒有采用在簇內高能節(jié)點間輪轉(rotate)生成簇頭來避免再次聚類的策略,主要基于三點考慮:①保留讓外部節(jié)點加入網絡的機會;②再次聚類可以動態(tài)尋找位置更優(yōu)的簇頭;③聚類計算由基站在時間充裕的數據傳輸階段完成,鑒于基站強大的計算能力,不會影響網絡整體性能。

3 仿真與結果分析

為了評估IFCEER算法性能,使用MATLAB軟件搭建仿真平臺,完成兩步實驗。首先,分析改進螢火蟲聚類算法的精度和收斂性;其次,從生命期、傳輸數據包、能耗、重新聚類次數占比等指標考量算法的網絡性能。根據節(jié)點傳輸數據方式的不同設立了兩組實驗數據,分別是自由空間模型主導的100 m×100 m監(jiān)測環(huán)境,以及多路徑衰減模型主導的300 m×300 m監(jiān)測環(huán)境,傳感節(jié)點隨機分布在監(jiān)測區(qū)域。

3.1 聚類仿真實驗

聚類實驗用于比較本文提出的改進螢火蟲聚類算法IFA、螢火蟲聚類算法FA和K-means聚類算法的性能指標[11,14],兩種螢火蟲算法的初始聚類中心保持一致,計算參數N=15,β0=1,γ=0.8,α=0.06。圖4顯示了在100 m×100 m數據集上3種算法聚類的收斂曲線,總迭代次數為20次,運行30次取平均值,得到IFA算法最優(yōu)目標函數值JC=36.92,FA算法最優(yōu)目標函數值JC=37.90,K-means算法最優(yōu)目標函數值JC=39.21。因此,IFA算法的精度最高。IFA算法、FA算法和K-means算法達到最優(yōu)目標函數值的平均迭代次數分別為9次、7次和16次。比較而言,K-means算法容易收斂于局部次優(yōu)解,穩(wěn)定性最差。IFA算法和FA算法收斂性基本一致,因為IFA算法引入了最優(yōu)類中心擾動,所以迭代次數相比無擾動的FA算法略有增加。

圖4 100 m×100 m數據集聚類收斂曲線

為了直觀地對比聚類效果,圖5中繪制了3種算法聚類后節(jié)點分布的隸屬情況。圖5(a)是IFA算法的簇結構圖和聚類中心分布圖,圖5(b)是FA算法的簇結構圖和聚類中心分布圖,圖5(c)是K-means算法的簇結構圖和聚類中心分布圖,圖中O代表聚類中心。由圖5可得,IFA算法簇劃分更為均勻,簇內節(jié)點間的距離更接近,聚類效果優(yōu)于其他兩種算法。

圖5 3種算法的聚類效果

3.2 網絡仿真實驗

網絡實驗在多級能量異構WSNs環(huán)境下比較IFCEER算法與DEEC算法性能。仿真實驗參數如表1所示,其他參數與聚類實驗相同。100 m×100 m監(jiān)測環(huán)境的最優(yōu)簇頭數Kopt參照自由空間模型計算公式(15.1)得到;300 m×300 m監(jiān)測環(huán)境的最優(yōu)簇頭數Kopt大于多路徑衰減模型公式(15.2)的計算結果,是為了避免過多減少簇頭使得簇內節(jié)點間距離增加甚至超過d0的情況大量出現。在網絡穩(wěn)定期,簇頭數量等于最優(yōu)簇頭數Kopt;當節(jié)點大量死亡后,如果具備競爭簇頭能力的高能節(jié)點的數量小于最優(yōu)簇頭數Kopt,則這些高能節(jié)點都成為簇頭,以盡可能保持網絡的連通?？刂茢祿鼣y帶了節(jié)點殘余能量等級等信息。

表1 仿真參數

圖6是存活節(jié)點圖,反映了隨時間關系網絡中存活的節(jié)點個數。

圖6 網絡中剩余的存活節(jié)點數

圖6(a)100 m×100 m監(jiān)測環(huán)境 IFCEER 算法和DEEC算法分別在706輪和497輪出現節(jié)點死亡,在712輪和662輪有50%節(jié)點死亡,在716輪和775輪有90%節(jié)點死亡。圖6(b)300 m×300 m監(jiān)測環(huán)境IFCEER算法和DEEC算法分別在260輪和80輪出現節(jié)點死亡,在520輪和171輪有50%節(jié)點死亡,在548輪和442輪有90%節(jié)點死亡?？梢钥吹?圖6(a)中IFCEER算法的曲線幾乎是一條垂直于y軸的直線。由于IFCEER算法引入了預測能量閾值,只有大于該閾值的高能節(jié)點具備競爭簇頭的資格,網絡能耗被均勻地分布到異構網的每個節(jié)點上,因此第1個節(jié)點和最后一個節(jié)點的死亡時間非常接近。圖6(b)300 m×300 m監(jiān)測環(huán)境簇內節(jié)點間距離大幅增加,副簇頭與基站平均距離大于d0,可以反映算法在惡劣條件下的性能表現。IFCEER算法大部分節(jié)點在450輪之后才開始死亡,而DEEC算法在80輪之后節(jié)點就迅速死亡,網絡性能下降嚴重。體現出改進螢火蟲聚類對比隨機聚類在尋找緊密簇結構、生成全局最優(yōu)簇方面的優(yōu)越性,而且主副簇頭機制進一步均衡了網絡能耗。從圖6可以看到,與DEEC算法比較第1個節(jié)點死亡時間,IFCEER算法在100 m×100 m和300 m×300 m監(jiān)測環(huán)境使得網絡壽命分別提高了43%和225%。更長的網絡生命期意味著更多的傳輸數據,如圖7所示,DEEC算法在100 m×100 m監(jiān)測環(huán)境網絡整體傳輸了67 231個數據包,在300 m×300 m監(jiān)測環(huán)境傳輸了23 923個數據包;而IFCEER算法分別為75 026和51 769,效果提升明顯。

圖8展示了網絡總體能量隨時間的消耗情況。兩組實驗環(huán)境中IFCEER算法網絡生命期能耗曲線的斜率幾乎保持不變,均低于DEEC算法的能耗曲線,IFCEER算法的性能表現為更節(jié)約能量。

圖7 網絡傳輸的數據量

圖8 網絡總體能耗

由表1可知,自由空間模型100 m×100 m監(jiān)測環(huán)境的能量消耗中接收和發(fā)送數據的電路固定能耗占比較大,因此IFCEER算法的優(yōu)勢更多地體現在節(jié)點間能耗的均勻分配,從而推遲節(jié)點的平均死亡時間。多路徑衰減模型300 m×300 m監(jiān)測環(huán)境的消耗能量中隨傳輸距離改變的無線功放能耗占據主導地位,造成經過全局最優(yōu)聚類獲得緊密簇結構的IFCEER算法的能耗顯著低于DEEC算法。表2是兩種算法的能耗統(tǒng)計,與經典DEEC算法相比,隨著節(jié)點間傳輸距離的增加,本文采用的IFCEER算法有效減少了網絡的總體能量消耗,網絡性能得到了很大的提高。

表2 兩種算法的能耗統(tǒng)計

根據式(24),通過比較全體簇頭的下一輪預測殘余能量與閾值能量的大小決定網絡運行過程是否重新聚類,簇形成階段執(zhí)行的次數與重新聚類的次數相當。因此,重新聚類次數越少,網絡通信負載越低。IFCEER算法默認有節(jié)點死亡的輪次都會重新聚類,所以僅統(tǒng)計網絡穩(wěn)定期所有輪次對應的重新聚類次數。仿真運行20次得到的100 m×100 m監(jiān)測環(huán)境數據如表3,結果表明只有約29.5%的輪次需要重新聚類,有效地減少了網絡控制包數量。

表3 IFCEER算法重新聚類次數

4 結束語

本文提出基于改進螢火蟲聚類的異構WSNs能耗優(yōu)化路由算法IFCEER,算法通過改進螢火蟲聚類算法對全體高能節(jié)點進行預測分簇,在簇內選擇與聚類中心和基站臨近的高能節(jié)點作為主副簇頭,形成結構緊密的全局最優(yōu)簇集合,只有大于指定殘余能量閾值的節(jié)點具備持續(xù)競爭簇頭的資格。利用上述策略,較好地平衡了網絡的能量負載,降低了網絡能耗,從而達到延長網絡生命期的效果,仿真實驗證明IFCEER算法擁有可觀的性能提升。后續(xù)研究圍繞3個方面開展:①綜合節(jié)點距離、殘余能量等因素拓寬螢火蟲聚類算法中目標函數的定義,使得聚類結果更深刻地反映網絡變化情況,簡化后續(xù)執(zhí)行步驟;②在節(jié)點死亡后動態(tài)增加新節(jié)點可以持續(xù)保持網絡的通信能力[16],注入新節(jié)點的策略值得深入研究;③大規(guī)模WSNs基站和簇頭相距遙遠,需要采用簇間多跳方式解決遠距離數據傳輸問題。利用IFCEER算法為基礎,開發(fā)相應的新算法是可行之道。