基于Grid-VFACO的數(shù)字化車(chē)間WSNs路由算法*

朱紹文， 紀(jì)志成， 王 艷， 吳定會(huì)

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

0 引 言

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

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

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

1 網(wǎng)絡(luò)模型

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

(1)

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

ERx(l)=Eelec·l.

(2)

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

2 Grid-VFACO算法的設(shè)計(jì)

2.1 Grid的劃分

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

2.2 候選簇首的選舉

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

1)先計(jì)算每個(gè)劃分網(wǎng)格中質(zhì)心點(diǎn)的位置坐標(biāo)

(8)

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

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

(9)

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

2.3 簇首的選舉

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

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

(10)

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

(11)

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

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

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

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

簇首選舉之后，利用VFACO算法進(jìn)行路徑搜索，目標(biāo)是尋找從各個(gè)簇首到Sink代價(jià)最小的多跳路由。

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

(12)

(13)

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

(14)

如果簇首chi和chj是選擇路徑上的節(jié)點(diǎn)，根據(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é)點(diǎn)的距離D密切相關(guān)，靠近Sink節(jié)點(diǎn)的信息素蒸發(fā)率的值較小，留在邊上的信息素較多，保證螞蟻能夠較快地到達(dá)Sink節(jié)點(diǎn)，提高數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性。

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

(16)

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

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

(17)

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

3 算法仿真結(jié)果及分析

為了評(píng)價(jià)本文算法的性能優(yōu)勢(shì)和有效性，在200 m×200 m的數(shù)字化車(chē)間數(shù)據(jù)采集區(qū)域分布100個(gè)傳感器節(jié)點(diǎn)，初始能量為0.5 J，通信半徑為180 m，Sink節(jié)點(diǎn)的位置為(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值設(shè)為100。利用Matlab R2010a對(duì)本文Grid-VFACO算法和LEACH算法從網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)和能耗2個(gè)方面進(jìn)行仿真比較與分析。

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

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

3.1 生命周期對(duì)比分析

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

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

3.2 能量消耗對(duì)比

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

4 結(jié)束語(yǔ)

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

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

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

參考文獻(xiàn):

[1]李曉維，徐勇軍，任豐原.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)技術(shù)[M].北京：北京理工大學(xué)出版社，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ú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署研究進(jìn)展[J].傳感器與微系統(tǒng),2012,31(4):1-4.

[4]林國(guó)富.離散制造車(chē)間數(shù)據(jù)采集系統(tǒng)的研究與開(kāi)發(fā)[D].南京：南京理工大學(xué),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ú)線(xiàn)傳感器網(wǎng)絡(luò)路由協(xié)議的研究[D].南京：南京郵電大學(xué),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] 羅四維，侯孟書(shū)，周益民.一種新的基于能量消耗速率模型的分簇路由協(xié)議[J].計(jì)算機(jī)科學(xué),2012,39(6):47-50.

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