基于Grid-VFACO的數字化車間WSNs路由算法*

朱紹文， 紀志成， 王 艷， 吳定會

(江南大學 物聯網工程學院，江蘇 無錫 214122)

0 引 言

數字化車間是現代化車間信息化發展的新階段，及時正確地采集車間數據是實現數字化車間的重要前提。無線傳感器網絡(WSNs)具有支持拓撲變化、節點移動等特點[1～3]，特別適用于數字化車間數據采集過程中。車間涉及到產品制造過程中的各個生產步驟，數據類型[4]不同，采集能耗不均，數據冗余大，由于每個傳感器節點的能量有限，任一節點失效會導致服務器無法實時得到該節點采集范圍內的數據，而在車間這種特殊的需要長時間連續工作的系統中,停止當前工作給節點更換電池或充電的成本較高。因此,如何構建一個高效節能的路由協議[5]，提高節點的平均生存時間成為WSNs面臨的主要問題。基于分簇的路由[6]結合了數據融合技術，能顯著降低數據冗余，提高能量有效性和網絡的可擴展性。

圍繞分簇機制，目前已經有大量的研究工作。Heinzelman等人提出了LEACH[7]的算法，是以循環的方式隨機選擇簇首節點，將整個網絡的能量負載均衡平均分配到每個傳感器節點中，從而降低網絡能耗。Younis O等人[8]提出的HEED算法考慮了節點的剩余能量，并引入主從關系多個約束條件作用于簇首的選擇過程。Inbo Sim等人[9]提出一種簇頭選舉過程中考慮節點能量和當選為簇頭節點的次數的改進協議ECS。羅四維等人[10]提出了一種在簇首選舉中綜合考慮節點消耗速率和普通節點到Sink節點距離局限性的分簇路由協議EDRMC。上述協議簡單易于實現，但存在沒有考慮節點剩余能量或缺乏對位置因素的考慮等一些缺陷，不能適合數字化車間數據采集對WSNs的需求。

本文針對應用中存在的上述問題，提出了一種基于網格和虛擬力導向蟻群優化(Grid-VFACO)算法的高能效路由策略，先將車間數據采集區劃分成網格，并基于節點位置和剩余能量的考慮選舉簇首，優化簇首分布。在簇首節點形成一個上層網絡中采用VFACO算法求出最優數據轉發路徑，通過多跳的方式將數據發送到Sink節點，平衡簇首的能耗，并滿足應用中要求的傳輸時延。

1 網絡模型

在車間數據采集區M×M中分布N個傳感器節點，部署后位置不發生移動，應用場景為傳感器節點周期地獲取監測數據并不斷地將數據向Sink節點匯集。網絡具有以下性質：1) Sink節點位于網絡外側，計算能力和能量不受限制，傳感器節點和Sink節點在部署后位置不發生移動；2)傳感器節點具備數據融合功能，能感知自己的剩余能量，并且具有全網唯一ID；3)已知對方的發送功率，節點可以根據接收信號的強度計算發送者到自己的近似距離；4)采用與LEACH協議相同的無線通信能耗模型。節點將一個lbit的數據傳送距離d，則發送數據能耗

(1)

接收數據消耗模型

ERx(l)=Eelec·l.

(2)

Eelec為發射和接收電路每發送或接收單位bit數據的能耗，εfs和εamp分別為自由空間和多路衰減模型中天線增益所消耗的能量。

2 Grid-VFACO算法的設計

2.1 Grid的劃分

將數據采集區用網絡來覆蓋的目的是為了實現簇的均勻分布。劃分網格時，在連通度上要求任意相鄰的簇首都能直接通信，用R表示通信半徑，則網格的邊長d需滿足

(3)

在覆蓋度上要求合適的分簇數量可覆蓋監測區域。根據文獻[12]的分析，綜合考慮分簇對能耗和網絡時延的影響，推導出最優分簇數kopt

(4)

式中λ為能耗和時延的權重因子，Tslot為時隙長度。對kopt取整后求出網格的邊長

(5)

d越大，則被包含在一個網格內的節點數將越多，這對節省網絡能耗是有益的，因此,d取值為

(6)

基站將計算出的網格邊距通過“HELLO”報文廣播至全網節點，節點接收到邊距廣播消息后根據自身的地理坐標(xi,yi)計算出網格編號(Girdx,Girdy)

(7)

網絡節點會因能量耗盡而失效，存活節點數在整個過程中不斷發生變化，當減小到一定的比例時，基站會重新計算最優簇數目，調整簇的個數和網絡的邊長后再次發送廣播報文，完成簇的重構。

2.2 候選簇首的選舉

為了防止區域邊緣的節點成為簇首，在網格質心位置的一定范圍內，選擇出候選簇首。具體步驟為：

1)先計算每個劃分網格中質心點的位置坐標

(8)

式中n為每個網格內節點的個數，i表示節點的ID號。

2) 以所得質心點位置為圓心，選擇半徑為Rc內的節點，作為候選簇首參與簇首的競爭，并對候選節點進行標記

(9)

其中，dmax,dmin分別為簇內節點到簇質心點距離最大和最小值，daverage是簇內節點到質心的平均距離，c∈(0,1)。

2.3 簇首的選舉

在候選簇首中進一步選擇簇首，為保證簇首的能量達到完成一輪通信所消耗最小能量，并使簇首位置盡量靠近該網格的質心，目標函數為

Pch=(e-di)k1·(Eiresidual/Eave)1-k1，Eiresdual≥Eth,

(10)

式中dmi為網格中的節點到該網格質心點的距離，Eiresidual為節點i的剩余能量，Eave為候選節點的平均能量，Eth為能量門限值，當節點的剩余能量低于Eth時不能擔任簇首。由于節點的能量損耗主要用于接收、發送消息以及數據融合，因此，Eth值為

(11)

式中Ncollect為一次循環中數據收集次數，Caverage為簇內節點數，l為數據包長度,EDA為融合單位比特數據能耗。選擇Pch值最大的節點作為簇首。

當所有簇首確定后，廣播消息通知其它節點，具有相同網格編號的節點自組織成簇。

在每一輪的最后一幀，簇首的所有鄰居節點將剩余能量值報告給簇首，如果有簇首的剩余能量值低于Eth，原簇首在候選簇首集中選擇Pch最大的節點作為下一輪的簇首;否則,下一輪簇首不更換。

2.4 基于VFACO的數據轉發

簇首選舉之后，利用VFACO算法進行路徑搜索，目標是尋找從各個簇首到Sink代價最小的多跳路由。

定義f(i,j)表示節點j相對于節點i的虛擬吸引力為

(12)

(13)

將f(i,j)作為蟻群算法中轉移概率規則啟發因子，則位于節點i的螞蟻k選擇下一節點j進行訪問的概率為pk(i,j)

(14)

如果簇首chi和chj是選擇路徑上的節點，根據公式更新邊e(chi,chj)間的信息素濃度

τij(t+1)=(1-ρij)τij(t)+Δτij,ρij

=ρinit(Dj-sink/Di-sink),

(15)

式中 Δτij為路徑ij上的信息素濃度增量，ρij為信息素的蒸發率，與簇首到Sink節點的距離D密切相關，靠近Sink節點的信息素蒸發率的值較小，留在邊上的信息素較多，保證螞蟻能夠較快地到達Sink節點，提高數據傳輸的實時性。

當Sink節點收到從一個簇首發來所有前向節點后，通過對每個節點包里面記錄的路徑節點個數和各節點剩余能量值，計算各路徑平均剩余能量Eaverage進行比較，最終選出一條從該簇首到Sink節點的Eaverage最大的最優路徑

(16)

其中,route-i為節點i所走過的路徑。當Sink節點選出最優路徑后，立即產生一個反向螞蟻按照最優路徑返回到簇首，并對信息素進行全局更新，更新公式如下

τij(t+1)=τij(t)+Δτ(t),Δτ(t)=Q/lk，

(17)

式中Q為系統參數，lk為最優路徑長度。當簇首發生變化后，與上一輪簇首交換路由表信息，并重新計算信息素和概率。最終數據包經過簇首間的多跳路由從源點傳送到Sink節點。

3 算法仿真結果及分析

為了評價本文算法的性能優勢和有效性，在200 m×200 m的數字化車間數據采集區域分布100個傳感器節點，初始能量為0.5 J，通信半徑為180 m，Sink節點的位置為(100,275)m。εfs和εamp分別為10 pJ/bit/m2和0.001 3 pJ/bit/m4，Eelec和EDA分別為50，5 nJ/bit，數據包大小為2 kB，信息素蒸發率初始值ρinit為0.9，α和β值分別為1和2，Q值設為100。利用Matlab R2010a對本文Grid-VFACO算法和LEACH算法從網絡存活節點數和能耗2個方面進行仿真比較與分析。

圖1是本文算法首次數據采集區網格劃分和簇首選舉后的效果。從圖中可以看出:目標區域被劃分成9個網格，每個網格中選舉產生1個簇首(圖中“*”標記的節點為簇首)，靠近網格質心，簇首分布均衡，有助于平衡整個網絡的能耗。

圖1 首次網格的劃分與簇首選擇

3.1 生命周期對比分析

圖2為200×200的數字化車間數據采集區域中WSNs生命周期圖，在使用LEACH算法的網絡中，從474輪節點開始死亡，直到813輪節點全部死亡。在本文算法中，節點從653輪開始死亡，直到978輪節點全部死亡，由此說明:Grid-ACO算法在延長網絡生命方面的性能比LEACH算法有明顯的提升。

圖2 網絡生命周期的比較

3.2 能量消耗對比

圖3為2種算法的能量消耗圖，由圖可以發現，隨著運行輪數的增長，本文對簇首的分布和簇間路由進行優化，使能量消耗值比LEACH算法減小約20 %以上，由此證明:本文算法能顯著降低網絡能耗，加強網絡健壯性，提高了網絡的整體性能。

4 結束語

本文從數字化車間實際環境和現場應用的實時性考慮，提出了基于Grid-VFACO高能效路由算法，綜合考慮

圖3 網絡能耗的比較

節點分布位置和剩余能量，優化了簇首選擇機制，并利用VFACO算法實現了簇首間多跳路由性能的改善。仿真結果表明:本文Grid-VFACO算法能平衡網絡能耗，可以快速、準確地將數據傳輸到與數據庫服務器相連的Sink節點，使管理人員可以及時掌握車間生產信息。

參考文獻:

[1]李曉維，徐勇軍，任豐原.無線傳感器網絡技術[M].北京：北京理工大學出版社，2007:2-5.

[2]Haiying Shen,Ze Li,Lei et al.Efficient data collection for large-scale mobile monitoring applications[J].IEEE Transactions on Parallel and Distributed Systems,2013,99(1):1-10.

[3]凡高娟，郭拯危.無線傳感器網絡節點部署研究進展[J].傳感器與微系統,2012,31(4):1-4.

[4]林國富.離散制造車間數據采集系統的研究與開發[D].南京：南京理工大學,2011.

[5]Pantazis N A,Nikolidakis S A,Vergados D D.Energy-efficient routing protocols in wireless sensor networks: A survery[J].IEEE Communications Surveys & Tutorials,2013,15(2):551-591.

[6]由文凱.基于Zig Bee的無線傳感器網絡路由協議的研究[D].南京：南京郵電大學,2012.

[7]Heinzelman W R,Chandrakasan A P,Balakrishnan H.An application specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communication Networks,2002,1(4):660-670.

[8]Younis O,Fahmy S.HEED: A hybrid,energy efficient,distributed clustering approach for Ad Hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4): 366-379.

[9]Sim I,Choi K,Kwon K,et al.Energy-efficient cluster selection algorithm in WSNs[C]∥Proceedings of the International Confe-rence on Complex Intelligent and Software Intensive Systems,CISIS,2009:584-587.

[10] 羅四維，侯孟書，周益民.一種新的基于能量消耗速率模型的分簇路由協議[J].計算機科學,2012,39(6):47-50.

[11] 朱 敏，肖 震，劉昊霖,等.WSN中基于虛擬網格的分簇路由算法[J].四川大學學報：工程科學版，2011，31(2):324-327.