基于模糊強化學習和果蠅優(yōu)化的WSN數(shù)據(jù)聚合算法①

閻 峻,黃建德,孫鵬玉,蔣池劍,陸 靚

1(國網(wǎng)新源控股有限公司,北京 100761)

2(華東桐柏抽水蓄能發(fā)電有限責任公司,杭州 310006)

3(南京南瑞信息通信科技有限公司,南京 210003)

隨著物聯(lián)網(wǎng)與各種通信技術的快速發(fā)展,無線傳感網(wǎng)絡(Wireless Sensor Network,WSN)開始受到廣泛關注[1].WSN 作為信息采集的一種重要手段,相比于傳統(tǒng)有線或者人工信息采集優(yōu)勢十分明顯,WSN 可以做到快速部署以及大規(guī)模覆蓋,因此WSN 目前廣泛應用于軍事、工業(yè)、農(nóng)業(yè)等多個領域[2].然而傳感器的壽命完全依賴于電池[3],如果由傳感器因為電池耗盡而停止工作,那么無線傳感網(wǎng)絡的信息采集完整度就會受到很大的影響.因此降低WSN的能耗,同時保證網(wǎng)絡傳輸質量是一個值得研究的問題.

本文提出了一種適用于密集分布無線傳感器網(wǎng)絡的數(shù)據(jù)聚合方案,首先利用網(wǎng)格聚類劃分網(wǎng)絡,然后通過模糊強化學習選取數(shù)據(jù)聚合節(jié)點并利用果蠅優(yōu)化算法動態(tài)定位外部通信節(jié)點降低了無線傳感網(wǎng)絡的能耗,同時也保證了較低的丟包率和端到端延遲.

1 研究現(xiàn)狀

目前關于無線傳感網(wǎng)絡國內(nèi)外已有大量相關學者進行了深入研究.文獻[4]針對節(jié)點覆蓋不均勻的問題,提出了一種自適應粒子群優(yōu)化算法.文獻[5]提出了一種利用壓縮感知(HDACS)進行分層數(shù)據(jù)聚合的方法,根據(jù)集群的大小,建立多個壓縮閾值;在不同級別的數(shù)據(jù)收集中,傳輸?shù)男畔⒘勘粌?yōu)化.文獻[6]提出了一種基于模糊邏輯的多層協(xié)議,以提高分布式WSN中數(shù)據(jù)聚合的處理效率.文獻[7]提出了一種基于代理的服務器系統(tǒng)方法,該方法改善了IoT/CPS 提供程序中異構WSN 之間的資源共享.上述的一些研究內(nèi)容中大多沒有考慮數(shù)據(jù)聚合過程中可能存在的一些問題,在WSN 應用中,經(jīng)常產(chǎn)生大量的冗余感知數(shù)據(jù)使得數(shù)據(jù)聚合更加耗能[8,9].為了降低能耗,在文獻[10,11]中采用了一種有效的數(shù)據(jù)聚合技術來控制數(shù)據(jù),根據(jù)網(wǎng)絡拓撲、網(wǎng)絡流和服務質量對數(shù)據(jù)聚合過程進行分類.文獻[12]將從不同傳感器節(jié)點獲得的數(shù)據(jù)合并后進行冗余消除,以減少向匯聚節(jié)點的數(shù)據(jù)傳輸次數(shù).此外還有如EASR (Energy Aware Sink Relocation)[13]、TCBDGA(Tree-Cluster-Based Data-Gathering Algorithm)[14]和FR-EEDG(Fuzzy Reinforcement learning-based Energy-Efficient Data Gathering)[15]等一些數(shù)據(jù)聚合方案,然而這些方案的問題是數(shù)據(jù)的聚合依賴于簇頭和匯聚節(jié)點,當網(wǎng)絡大小和節(jié)點密度增加時,它會自動最大化能量的利用,從而導致網(wǎng)絡的生命周期變短.因此為了解決上述問題,本文提出了一種適用于密集分布無線傳感器網(wǎng)絡的節(jié)能數(shù)據(jù)聚合方案.

2 系統(tǒng)模型

2.1 網(wǎng)絡節(jié)點模型

本文網(wǎng)絡節(jié)點模型如圖1所示,將傳感器網(wǎng)絡區(qū)域的整個區(qū)域劃分成網(wǎng)格單元簇,再將網(wǎng)格單元中的所有可用節(jié)點中用樹形結構連接,并選擇一個簇頭進行外部數(shù)據(jù)傳輸.圖中的每個節(jié)點都滿足如下兩個條件:

圖1 網(wǎng)絡節(jié)點模型

(1)網(wǎng)絡中的所有節(jié)點都有類似的配置.

(2)接收和網(wǎng)絡中所有其他考慮的節(jié)點都是靜態(tài)的,在部署之后,它不能移動到網(wǎng)絡的任何地方.

其中,sensor nodes為傳感器節(jié)點,aggregator node為一個網(wǎng)格簇的數(shù)據(jù)匯聚節(jié)點,sink為整個傳感器網(wǎng)絡的數(shù)據(jù)匯聚節(jié)點和外部通信節(jié)點(可為網(wǎng)絡中的任意節(jié)點),為了加以區(qū)分,下文中的相關節(jié)點都將用英文表示.

2.1.1 網(wǎng)格劃分

要將傳感器網(wǎng)絡劃分成圖1所示的網(wǎng)格結構,需要執(zhí)行下面兩個步驟:

步驟1.對網(wǎng)絡區(qū)域進行縱向劃分,將其劃分為高為H,寬為W的矩形區(qū)域,用1～n對這些矩形的進行編號.

步驟2.將每個矩形劃分成更小且不相等的區(qū)域,即網(wǎng)格.每個的位置與數(shù)據(jù)匯聚點之間的距離決定了在這個矩形中創(chuàng)建的網(wǎng)格的邊界.我們用(m,n)表示第n個矩形中的第m個網(wǎng)格,則網(wǎng)格(m,n)的邊界可以由式(1)求出:

其中,l和c用于表示網(wǎng)格線以及網(wǎng)格的列向量,hcl表示網(wǎng)格高度.令第i個節(jié)點的坐標為(a,b),那么在網(wǎng)格劃分結束后就可以得到節(jié)點所屬于的網(wǎng)格.

2.1.2 網(wǎng)格聚類和簇頭選擇

在每個網(wǎng)格單元中,聚類和簇頭選擇過程由sink節(jié)點啟動.Sink 節(jié)點會定期將信標消息發(fā)送到sensor節(jié)點,sensor 節(jié)點會發(fā)送包含位置信息和能級信息的回復消息.從sensor 節(jié)點獲得此信息后,sink 節(jié)點根據(jù)最大剩余能量水平因數(shù)選擇簇頭.表1顯示了傳感器節(jié)點的詳細信息.

表1 傳感器節(jié)點信息

CH (Cluster Header) 表示簇頭,k(i,sink) 表示sink 節(jié)點與第i個sensor 節(jié)點之間的長度.式(2)用于判斷傳感器節(jié)點能否作為簇頭:

其中,maxID表示為網(wǎng)絡中存在的節(jié)點的最大ID,Ecur表示節(jié)點i的當前能量,Eini表示初始能量,c1和c2表示為從0 到1的任意常數(shù)范圍.

2.2 基于模糊規(guī)則系統(tǒng)評估aggregator 節(jié)點

Aggregator 節(jié)點的選擇是在網(wǎng)格簇的簇頭節(jié)點幫助下進行的.模糊規(guī)則系統(tǒng)將簇頭距離(Cluster Header DIStance,CH_DIS),鄰域重疊(Neighbourhood OVERlap,NOVER)和代數(shù)連通性(Algebraic Connectivity,AC)視為解決aggregator 節(jié)點適用性的3 個指標.

NOVER為直接度量,用于確定兩個節(jié)點的鏈路之間存在的已連接鄰居的范圍,具有最高NOVER 值的節(jié)點鏈路的起始節(jié)點最有可能成為簇頭節(jié)點.節(jié)點鏈接的AC 用于評估節(jié)點到節(jié)點鏈接連接的魯棒性,較高AC 值的節(jié)點鏈接也更有可能成為簇頭節(jié)點.模糊邏輯系統(tǒng)根據(jù)三角隸屬函數(shù)公式為輸入指標找到相關的隸屬函數(shù).

模糊化步驟:在此步驟中,模糊器調用數(shù)據(jù)輸入指標的清晰值,并提供給它們相對預定義的隸屬度函數(shù)以及模糊描述變量.

映射步驟:基于表2中列出的知識庫規(guī)則庫,推理機根據(jù)CH_DIS,NOVE和AC的模糊值,將其映射到預定義的規(guī)則,以獲取成為aggregator 節(jié)點的等級,作為模糊輸出值.例如CH_DIS 值為near,NOVER 值為good,AC 值為strong,則節(jié)點等級為acceptable.

表2 節(jié)點知識庫

去模糊化:在去模糊化過程中,使用預定義的輸出隸屬度函數(shù)將模糊輸出值轉換為相關的數(shù)值.CH_DIS,NOVER和AC的隸屬函數(shù)如圖2～圖4所示.

圖2 CH_DIS 隸屬函數(shù)

圖3 NOVER 隸屬函數(shù)

圖4 AC 隸屬函數(shù)

重心法用于去模糊化.其數(shù)學定義為:

其中,A表示模糊集,x是樣本元素,而 μA(x)是模糊集的隸屬函數(shù).最終的去模糊值是對應于圖5中所示頂點的x坐標值,它定義了節(jié)點的能力值.

圖5 節(jié)點去模糊值

2.3 基于模糊強化學習選取aggregator 節(jié)點

整個網(wǎng)絡被表示為一個環(huán)境,所有集群成員節(jié)點都參與學習.通過交換信標消息,每個節(jié)點與其他節(jié)點一起學習整個網(wǎng)絡環(huán)境.選擇根節(jié)點是每個節(jié)點上用于數(shù)據(jù)傳輸和聚合的操作.每個節(jié)點都有一張Q表,其中每個Q值(Q(st,r))表示在狀態(tài)st處選擇r作為根節(jié)點的值.

對于每個動作和狀態(tài),每個節(jié)點都必須維持Q值.其中,狀態(tài)是當前節(jié)點的鏈路質量.動作是將當前節(jié)點選作根節(jié)點,以達到與相鄰節(jié)點的最大鏈路質量.Q表以5 s的間隔頻繁更新.從接收器節(jié)點接收到信標消息后,未選擇節(jié)點的Q表將更新.每個節(jié)點的Q值在開始時都設置為0.從接收器接收到信標消息后,初始節(jié)點將與接收器對應的Q值更新為:

其中,BQ(r,b)是信標消息的接收率.對于Qb(st,r),箭頭左邊表示當前值,右邊表示先前值,Nr代表群集內(nèi)節(jié)點的數(shù)量.當前狀態(tài)和下一個狀態(tài)分別表示為st和st+1.

其中,LQr是計算得出的當前節(jié)點到鄰居節(jié)點的鏈路質量,而LQ1r是節(jié)點1 可獲得的最大鏈路質量.Nc表示特定群集中可用的活動節(jié)點集.如果節(jié)點r達到良好的鏈路質量,則獎勵為正;否則,獎勵為0.對于整個網(wǎng)絡,經(jīng)過不斷的強化學習,最終每個節(jié)點都維護了一個學習隨迭代次數(shù)波動較小的Q矩陣,Q矩陣給出了在不同狀態(tài)下應該選定作為根節(jié)點的aggregator 節(jié)點.

2.4 基于FOA的sink 節(jié)點遷移機制

果蠅優(yōu)化算法(Fruit fly Optimization Algorithm,FOA)的主要目標是根據(jù)sink 節(jié)點的先前坐標執(zhí)行重定位操作,并且與其他優(yōu)化算法相比,FOA 可以實現(xiàn)更好的收斂速度.在本文中,FOA 遵循基于氣味的搜索機制.考慮兩個部分.第一階段是確定sink 節(jié)點重定位的條件,第二階段是確定sink 節(jié)點移動的路徑和重定位距離.重新定位的過程在算法1中進行了描述.

算法1.基于FOA的sink 節(jié)點遷移輸入:V (傳感器節(jié)點集合);N (每個節(jié)點的鄰居節(jié)點集合);B (sink 節(jié)點的初始位置);r(u) (簇頭u 剩余能量)While true?u∈Vr(u)1.,收集剩余的能量 ;2.在每個傳感器節(jié)點中,通過對傳輸范圍的調整,確定WSN的通信圖G;?u∈VP*usC(P*us)3.,計算極限能力路徑和極限能力值 ;4.定義上下左右4 個可移動的方向,一次可以移動的距離為20:左移:■■■■■■■■■Xi=Xaxis-20 Yi=Yaxis+0右移:■■■■■■■■■Xi=Xaxis+20 Yi=Yaxis+0上移:■■■■■■■■■■■■■■■■■■Xi=Xaxis+0 Yi=Yaxis+20 Xi=Xaxis+0 Yi=Yaxis-20下移:5.計算新坐標所在網(wǎng)格簇的所有節(jié)點到所有aggregator 節(jié)點的跳數(shù),作為算法中的味道濃度值,跳數(shù)越短,濃度值越大;6.將每個網(wǎng)格簇中總跳數(shù)最短的節(jié)點標記為可行點,4 個節(jié)點的權值標記為w1,w2,w3,w4,遷移路徑為可行路徑;SC*iw1,w2,w3,w4 7.設為中權值最大的移動候選節(jié)點;SC*i 8.If 節(jié)點的味道濃度值小于當前sink 節(jié)點;Break;SC*i Else 將sink 節(jié)點重定位到 ;End if End while

3 仿真及結果分析

本文仿真在Matlab中進行,分別對本文所提方案的丟包率,端到端時延以及能量消耗做出了仿真,仿真參數(shù)如表3所示.

表3 仿真參數(shù)

3.1 丟包率

丟包率(Packet Loss Ratio,PLR)定義為從源到目標節(jié)點的傳輸以及在目標節(jié)點中接收時發(fā)生的數(shù)據(jù)丟失,是傳輸?shù)臄?shù)據(jù)與接收的數(shù)據(jù)之比,以100 個節(jié)點為單位,如式(6)所示:

圖6為節(jié)點數(shù)和PLR的關系,本文所提方案相比EASR的丟包率始終保持在較低水平.因為每個aggregator 節(jié)點僅覆蓋有限的范圍,并且在網(wǎng)格聚類時根據(jù)節(jié)點的距離進行調整,從而避免了重疊,節(jié)點被放置在彼此的半徑內(nèi),這導致分組丟失最小化.

圖6 丟包率

3.2 端到端延遲

端到端延遲由式(7)計算得出:

端到端延遲的評估如圖7所示.提出的系統(tǒng)比其他現(xiàn)有系統(tǒng)具有最低的延遲.在100 個節(jié)點中,所提出方案的端到端延遲為2.8 s,而EASR為6 s.

圖7 端到端延遲

3.3 能量消耗

WSN中節(jié)點能耗影響數(shù)據(jù)的傳輸以及網(wǎng)絡效率,因此,它成為至關重要的問題.令Econ是節(jié)點固定能耗,l2為能量損失率,群集節(jié)點之間的跨度用d表示.數(shù)據(jù)通過放大器傳輸?shù)焦?jié)點的能耗為tamp×l2,其中tamp是用于傳輸數(shù)據(jù)的能量.m表示數(shù)據(jù)長度(位).然后通過以下公式計算能量:

在圖8中,仿真顯示了能耗評估.通過與EASR 進行比較,本文方案的能耗顯著降低,在100 節(jié)點時,本文方案使用50 MJ的能量,而EASR 系統(tǒng)使用150 MJ的能量.

圖8 能量消耗

在所提出的方案中,通過sink 節(jié)點重定位避免了數(shù)據(jù)聚合的復雜性.因此,防止了重復的數(shù)據(jù)傳輸.當兩個節(jié)點位于彼此的半徑內(nèi)時,冗余數(shù)據(jù)可能會轉發(fā)到aggregator 節(jié)點,這會最大化aggregator 節(jié)點的工作負載,并且浪費能源.因此,通過避免重復數(shù)據(jù),處理操作被最小化,并且聚合器節(jié)點的壽命得以延長.

4 結論

本文提出了一種基于模糊強化學習和果蠅優(yōu)化的WSN 數(shù)據(jù)聚合算法,首先將網(wǎng)絡區(qū)域劃分成不同層次的網(wǎng)格簇,其次根據(jù)剩余能量選取網(wǎng)格簇的簇頭,接著評估所有可能的數(shù)據(jù)聚合節(jié)點,然后采用模糊強化學習選取最佳數(shù)據(jù)聚合節(jié)點,最后利用果蠅優(yōu)化算法動態(tài)定位外部通信節(jié)點.本文所述算法適用于大規(guī)模密集型無線傳感器網(wǎng)絡,可應用在工業(yè)生產(chǎn)信息采集等場景中.