基于模糊強化學習和果蠅優化的WSN數據聚合算法①

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

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

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

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

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

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

1 研究現狀

目前關于無線傳感網絡國內外已有大量相關學者進行了深入研究.文獻[4]針對節點覆蓋不均勻的問題,提出了一種自適應粒子群優化算法.文獻[5]提出了一種利用壓縮感知(HDACS)進行分層數據聚合的方法,根據集群的大小,建立多個壓縮閾值;在不同級別的數據收集中,傳輸的信息量被優化.文獻[6]提出了一種基于模糊邏輯的多層協議,以提高分布式WSN中數據聚合的處理效率.文獻[7]提出了一種基于代理的服務器系統方法,該方法改善了IoT/CPS 提供程序中異構WSN 之間的資源共享.上述的一些研究內容中大多沒有考慮數據聚合過程中可能存在的一些問題,在WSN 應用中,經常產生大量的冗余感知數據使得數據聚合更加耗能[8,9].為了降低能耗,在文獻[10,11]中采用了一種有效的數據聚合技術來控制數據,根據網絡拓撲、網絡流和服務質量對數據聚合過程進行分類.文獻[12]將從不同傳感器節點獲得的數據合并后進行冗余消除,以減少向匯聚節點的數據傳輸次數.此外還有如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]等一些數據聚合方案,然而這些方案的問題是數據的聚合依賴于簇頭和匯聚節點,當網絡大小和節點密度增加時,它會自動最大化能量的利用,從而導致網絡的生命周期變短.因此為了解決上述問題,本文提出了一種適用于密集分布無線傳感器網絡的節能數據聚合方案.

2 系統模型

2.1 網絡節點模型

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

圖1 網絡節點模型

(1)網絡中的所有節點都有類似的配置.

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

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

2.1.1 網格劃分

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

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

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

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

2.1.2 網格聚類和簇頭選擇

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

表1 傳感器節點信息

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

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

2.2 基于模糊規則系統評估aggregator 節點

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

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

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

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

表2 節點知識庫

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

圖2 CH_DIS 隸屬函數

圖3 NOVER 隸屬函數

圖4 AC 隸屬函數

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

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

圖5 節點去模糊值

2.3 基于模糊強化學習選取aggregator 節點

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

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

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

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

2.4 基于FOA的sink 節點遷移機制

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

算法1.基于FOA的sink 節點遷移輸入:V (傳感器節點集合);N (每個節點的鄰居節點集合);B (sink 節點的初始位置);r(u) (簇頭u 剩余能量)While true?u∈Vr(u)1.,收集剩余的能量 ;2.在每個傳感器節點中,通過對傳輸范圍的調整,確定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.計算新坐標所在網格簇的所有節點到所有aggregator 節點的跳數,作為算法中的味道濃度值,跳數越短,濃度值越大;6.將每個網格簇中總跳數最短的節點標記為可行點,4 個節點的權值標記為w1,w2,w3,w4,遷移路徑為可行路徑;SC*iw1,w2,w3,w4 7.設為中權值最大的移動候選節點;SC*i 8.If 節點的味道濃度值小于當前sink 節點;Break;SC*i Else 將sink 節點重定位到 ;End if End while

3 仿真及結果分析

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

表3 仿真參數

3.1 丟包率

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

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

圖6 丟包率

3.2 端到端延遲

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

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

圖7 端到端延遲

3.3 能量消耗

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

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

圖8 能量消耗

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

4 結論

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