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

(江南大學 物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122)

0 引 言

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

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

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

1 網(wǎng)絡模型

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

(1)

接收數(shù)據(jù)消耗模型

ERx(l)=Eelec·l.

(2)

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

2 Grid-VFACO算法的設計

2.1 Grid的劃分

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

(3)

在覆蓋度上要求合適的分簇數(shù)量可覆蓋監(jiān)測區(qū)域。根據(jù)文獻[12]的分析，綜合考慮分簇對能耗和網(wǎng)絡時延的影響，推導出最優(yōu)分簇數(shù)kopt

(4)

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

(5)

d越大，則被包含在一個網(wǎng)格內(nèi)的節(jié)點數(shù)將越多，這對節(jié)省網(wǎng)絡能耗是有益的，因此,d取值為

(6)

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

(7)

網(wǎng)絡節(jié)點會因能量耗盡而失效，存活節(jié)點數(shù)在整個過程中不斷發(fā)生變化，當減小到一定的比例時，基站會重新計算最優(yōu)簇數(shù)目，調(diào)整簇的個數(shù)和網(wǎng)絡的邊長后再次發(fā)送廣播報文，完成簇的重構。

2.2 候選簇首的選舉

為了防止區(qū)域邊緣的節(jié)點成為簇首，在網(wǎng)格質(zhì)心位置的一定范圍內(nèi)，選擇出候選簇首。具體步驟為：

1)先計算每個劃分網(wǎng)格中質(zhì)心點的位置坐標

(8)

式中n為每個網(wǎng)格內(nèi)節(jié)點的個數(shù)，i表示節(jié)點的ID號。

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

(9)

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

2.3 簇首的選舉

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

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

(10)

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

(11)

式中Ncollect為一次循環(huán)中數(shù)據(jù)收集次數(shù)，Caverage為簇內(nèi)節(jié)點數(shù)，l為數(shù)據(jù)包長度,EDA為融合單位比特數(shù)據(jù)能耗。選擇Pch值最大的節(jié)點作為簇首。

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

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

2.4 基于VFACO的數(shù)據(jù)轉發(fā)

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

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

(12)

(13)

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

(14)

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

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

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

(15)

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

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

(16)

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

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

(17)

式中Q為系統(tǒng)參數(shù)，lk為最優(yōu)路徑長度。當簇首發(fā)生變化后，與上一輪簇首交換路由表信息，并重新計算信息素和概率。最終數(shù)據(jù)包經(jīng)過簇首間的多跳路由從源點傳送到Sink節(jié)點。

3 算法仿真結果及分析

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

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

圖1 首次網(wǎng)格的劃分與簇首選擇

3.1 生命周期對比分析

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

圖2 網(wǎng)絡生命周期的比較

3.2 能量消耗對比

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

4 結束語

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

圖3 網(wǎng)絡能耗的比較

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

參考文獻:

[1]李曉維，徐勇軍，任豐原.無線傳感器網(wǎng)絡技術[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]凡高娟，郭拯危.無線傳感器網(wǎng)絡節(jié)點部署研究進展[J].傳感器與微系統(tǒng),2012,31(4):1-4.

[4]林國富.離散制造車間數(shù)據(jù)采集系統(tǒng)的研究與開發(fā)[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的無線傳感器網(wǎng)絡路由協(xié)議的研究[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] 羅四維，侯孟書，周益民.一種新的基于能量消耗速率模型的分簇路由協(xié)議[J].計算機科學,2012,39(6):47-50.

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