基于果蠅優(yōu)化算法的礦井WSN路由協(xié)議研究

王越群，湯麗娟

（江蘇商貿(mào)職業(yè)學(xué)院電子與信息學(xué)院，江蘇南通，226000）

1 緒論

礦井工作環(huán)境在不斷變化，地面和井下的良好溝通需要依賴持續(xù)穩(wěn)定地從井下接收有效可靠的信息，如巷道中自然因素信息（煤塵、風(fēng)速等）、礦工信息等數(shù)據(jù)，事故發(fā)生時，地面工作人員才能做出準(zhǔn)確地判斷和決定，確保礦工生命安全[1]。無線傳感網(wǎng)便于擴展，十分符合礦井井下的工作環(huán)境，既能確保感測消息的及時傳送，又便于網(wǎng)絡(luò)布置[2]。因此，WSN也被更多地使用在礦井行業(yè)中。

WSN（Wireless Sensor Network）作為一種分布式自組織的實時性網(wǎng)絡(luò)，在礦井行業(yè)中主要被應(yīng)用于井下的人員定位，井下環(huán)境數(shù)據(jù)的采集以及安全監(jiān)控[3]，這些應(yīng)用都需要信息及時可靠地傳輸。針對國內(nèi)礦井環(huán)境，為保證無線網(wǎng)絡(luò)的可靠性，對設(shè)計井下無線網(wǎng)絡(luò)的路由機制或相關(guān)改進機制卻并不多。因此，設(shè)計一個高性能的WSN路由協(xié)議，對礦井作業(yè)十分重要[4]。

2 無線傳感器網(wǎng)絡(luò)路由協(xié)議

■2.1 礦井WSN路由協(xié)議分析

無線傳感網(wǎng)路由算法的主要作用是優(yōu)化路徑，探求初始節(jié)點和目標(biāo)節(jié)點間的多跳優(yōu)化路徑并將數(shù)據(jù)沿優(yōu)化路徑正確傳輸[5]。其中，層次路由協(xié)議應(yīng)用最為廣泛，而LEACH作為最基礎(chǔ)的層次路由協(xié)議之一，也常被用來作為改進算法的基礎(chǔ)算法。

針對長帶狀井道的環(huán)境結(jié)構(gòu)，提出LEACH-mine協(xié)議。在LEACH協(xié)議的簇首選擇中，沒有重視節(jié)點能量。LEACH-mine協(xié)議將節(jié)點剩余能量作為條件，以簇內(nèi)節(jié)點的均衡能量作為比較基準(zhǔn)，選出能量高的節(jié)點成為簇首。限制節(jié)點多次成為簇首，均衡能量消耗。

（1）成簇階段，在狹長的巷道內(nèi)，簇首不必向所有區(qū)域內(nèi)的普通節(jié)點發(fā)送消息，只需通知相鄰節(jié)點，邀請入簇。以距離簇頭的距離為基準(zhǔn)，節(jié)點選擇距離小的簇，發(fā)出申請信息，這樣減少簇頭能量消耗。

（2）數(shù)據(jù)傳輸。簇間通訊采用多跳方式將消息傳送至Sink節(jié)點。利用最小跳數(shù)路由算法，選擇能量最多且相距最遠的節(jié)點轉(zhuǎn)發(fā)信息。

算法在相同能量的基礎(chǔ)上，信息傳輸距離最遠，優(yōu)化能量利用效率，適合遠距離傳輸?shù)木W(wǎng)絡(luò)結(jié)構(gòu)。而在文獻[6]中，筆者提出線性拓?fù)浜途植磕芰烤獾膶哟温酚蓞f(xié)議。簇首選舉的過程中，不僅考量節(jié)點當(dāng)前能量，還引入相對位置均衡因子，使得位于區(qū)域中央且能量較高的節(jié)點更方便成為簇首，有效解決了巷道邊緣節(jié)點成為簇首，卻不利于轉(zhuǎn)發(fā)消息的問題。

文獻[7]中，為了解決帶狀巷道的能耗均衡問題，筆者提出LEBUC算法。將節(jié)點能量、節(jié)點與Sink節(jié)點的距離、節(jié)點分布密度作為控制條件，選出符合要求的簇首，改善礦井WSN路由能量空洞的情況。在分簇前，由能量模型計算出能耗最小的條件下，最優(yōu)的簇首期望個數(shù)，而后通過調(diào)整閾值，使得候選簇首的數(shù)量大于期望的最優(yōu)個數(shù)，競爭失敗的節(jié)點暫時“停工”，以減少能耗。長距離線性巷道中，靠近Sink的節(jié)點由于大量轉(zhuǎn)發(fā)監(jiān)測信息，能耗快，生命期短，因此解決此能量“空洞”的有效辦法是計算合理的簇首競選半徑。作者改進了EEUC算法[8]只考慮候選簇首與Sink節(jié)點距離的情況，加入對節(jié)點剩余能量的考量。

煤礦巷道深長，網(wǎng)絡(luò)設(shè)計有特殊性，且存在諸多問題，在礦井巷道環(huán)境下使用層次路由如LEACH算法的挑戰(zhàn)和有待調(diào)整的地方有如下幾點:

(1)協(xié)議沒有將候選簇首的剩余能量作為條件因素之一。

(2)簇首的選舉是隨機產(chǎn)生的，由于人員的移動導(dǎo)致節(jié)點分布隨機且不均勻，因此簇的范圍大小也就不均勻，容易造成小范圍內(nèi)有多個簇，某些偏遠位置只有一個大范圍的簇存在，這樣不利于數(shù)據(jù)的傳輸。

(3)在窄長巷道中，Sink周圍的簇頭傳送自身的融合消息同時，也要負(fù)責(zé)轉(zhuǎn)發(fā)其他簇頭的消息，能耗負(fù)擔(dān)過重，容易失效，出現(xiàn)路由“空洞”，改變網(wǎng)絡(luò)結(jié)構(gòu)，降低網(wǎng)絡(luò)功效。

■2.2 基于能耗均衡的層次路由算法分析

最初的層次路由算法，以LEACH協(xié)議最為經(jīng)典。LEACH算法的分簇機制中，以“輪”為時間單位，在每一輪中，選舉出符合條件的簇首，從公式（1）中可以看出，能否成為簇首主要取決于網(wǎng)絡(luò)中簇首數(shù)量的比例。

其中，P是簇頭節(jié)點數(shù)占總節(jié)點數(shù)的比例；r是已經(jīng)過的輪數(shù)；G是在前1/P輪中沒有充當(dāng)簇頭節(jié)點的集合。

LEACH- mine算法在選舉簇首時，加入了節(jié)點剩余能量這一條件，優(yōu)化了LEACH算法隨機選舉簇首的問題。而線性拓?fù)浜途植磕芰烤獾姆执芈酚蓞f(xié)議（ LEACHTLLEB），簇首的條件還加入了節(jié)點位置信息，在巷道的狹長網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，邊緣節(jié)點避免成為簇首，有利于信息的轉(zhuǎn)發(fā)。但以上兩種優(yōu)化算法都沒有改善礦井無線網(wǎng)絡(luò)中路由“空洞”問題。 PCEB-MS路由協(xié)議（DPCA算法）則通過控制節(jié)點功率調(diào)節(jié)成簇范圍大小，解決路由空洞問題。SOCRP協(xié)議以簇首間“局部協(xié)商”策略，緩解了數(shù)據(jù)傳輸?shù)摹爸丿B”問題。

■2.3 礦井WSN路由協(xié)議存在的問題

WSN分布在礦井的狹長帶狀空間中，復(fù)雜的環(huán)境狀況和具有特殊性的空間結(jié)構(gòu)都讓礦井 WSN路由協(xié)議的設(shè)計具有一些特殊性和挑戰(zhàn)[9]：

（1）能耗不均

單跳通信的傳輸方式已經(jīng)無法適應(yīng)礦井巷道的結(jié)構(gòu)特點，若按傳統(tǒng)方式將 Sink節(jié)點安置在巷道通風(fēng)口處，那遠離巷道口的節(jié)點由于巷道幾十米甚至數(shù)百米的傳輸距離，普通節(jié)點無法負(fù)荷超長距離的傳輸，所以節(jié)點必須通過中間節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)才能將有效信息傳回到Sink節(jié)點，距離Sink節(jié)點較近的節(jié)點由于多次充當(dāng)“數(shù)據(jù)中繼站”，能量負(fù)擔(dān)遠大于其他節(jié)點。因此，多跳方式也存在能量負(fù)載不均衡的問題。

（2）數(shù)據(jù)延遲

長距離的多跳傳輸，距離較遠的節(jié)點傳輸數(shù)據(jù)經(jīng)歷的跳數(shù)越多，引發(fā)數(shù)據(jù)延遲問題。因此，多跳路由機制的關(guān)鍵問題是如何實現(xiàn)跳數(shù)與鏈路的能耗平衡。

（3）數(shù)據(jù)傳輸?shù)目煽啃院途?/p>

礦井條件惡劣，無線電信號的傳輸會受到嚴(yán)重干擾，但是由于礦井對于地下的安全性要求較高，所以對感知數(shù)據(jù)的精確度也有較高的要求，礦井 WSN路由協(xié)議的有一大挑戰(zhàn)就是確保惡劣條件下數(shù)據(jù)傳輸?shù)目煽啃院途取?/p>

（4）可擴展性

隨著節(jié)點的失效死亡以及工作面的掘進帶來的新的節(jié)點的投入，網(wǎng)絡(luò)路由機制的設(shè)計要有足夠的可擴展性，網(wǎng)絡(luò)的性能不能隨著規(guī)模的增大而降低[10]。

■2.4 果蠅優(yōu)化算法

為了方便研討最短路徑問題，礦井網(wǎng)絡(luò)路由可以用帶權(quán)值的圖來表示，可以表示為G(N,B)，N表示礦井網(wǎng)絡(luò)中的節(jié)點數(shù)量，B表示通信節(jié)點間的通路，Cij表示通路(i,j)的權(quán)值,C=C[ij]表示權(quán)值矩陣，S,D分別表示源節(jié)點和目標(biāo)節(jié)點，Iij表示每個通路的鏈接，定義如下:

如果Iij=1，Ijk=1，則Iik=1，網(wǎng)絡(luò)中求最短路徑的問題可以轉(zhuǎn)化為求目標(biāo)函數(shù)最小值的優(yōu)化問題，目標(biāo)函數(shù)可表示如下：

■2.5 適應(yīng)度函數(shù)

在路由網(wǎng)絡(luò)中，因為會用到鄰居節(jié)點來轉(zhuǎn)發(fā)數(shù)據(jù)，因此鄰居節(jié)點的剩余能量因素也要作為優(yōu)化需要考慮的條件之一。Er、Erb、Erave分別代表節(jié)點的剩余能量、鄰居節(jié)點的平均剩余能量和節(jié)點的平均剩余能量。這樣，單個節(jié)點的能量便可由公式（4）表示[11]:能量可分別由：

其中，α，β表示平衡因子，令0＜β＜α，表示更注重節(jié)點的剩余能量情況。

公式（5）中，fn(i= 1,2,3,...,n)分別對應(yīng)路徑中第i個節(jié)點的能量平衡值，節(jié)點的能量平衡比如公式（6）所示：

節(jié)點能量安全平衡比Vsafe=ε，0<ε<0.3。Vsafe是節(jié)點能量相較于全網(wǎng)能量比值的安全值，假若節(jié)點的能量過低即V＜Vsafe，那么該節(jié)點進入保護狀態(tài)，不再采集數(shù)據(jù)和轉(zhuǎn)發(fā)數(shù)據(jù)。若ε取的值較小時，網(wǎng)絡(luò)的初始能量與能耗成反比；反之，取大值。

已知Numnb（i=1,...,n）表示第i個節(jié)點的鄰居節(jié)點個數(shù)，簇內(nèi)路由選擇考慮節(jié)點鄰居節(jié)點個數(shù)多的節(jié)點，在其中優(yōu)先選擇能量代價較小的節(jié)點且鄰居節(jié)點數(shù)較多的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點，保證整體選擇最優(yōu)路徑，因此用單個節(jié)點的鄰居節(jié)點數(shù)倒數(shù)來表征。

在保證節(jié)點數(shù)量最少的條件下，優(yōu)化的最短路徑應(yīng)滿足公式（8）[12]：

利用鄰居節(jié)點個數(shù)和節(jié)點剩余能量代價構(gòu)造適應(yīng)度函數(shù)，如公式（9）所示：

在開始時刻產(chǎn)生一定數(shù)量的果蠅個體，計算每個個體的fitness，比較出最小值，迭代更新果蠅集體的位置和方向，fitness最小值對應(yīng)的節(jié)點，就是對應(yīng)最佳路徑上的節(jié)點。

圖1

■2.6 MRP-FOA算法思想

MRP-FOA算法的設(shè)計思路是：簇首節(jié)點選舉過程以節(jié)點剩余能量和全網(wǎng)能量的比值產(chǎn)生節(jié)點隨機數(shù)，與閾值比較，平衡全網(wǎng)節(jié)點的剩余能量；由于簇間通信鄰居節(jié)點承擔(dān)轉(zhuǎn)發(fā)的功能，將節(jié)點的鄰居節(jié)點個數(shù)引入作為“度數(shù)”平衡因子，利用節(jié)點鄰居節(jié)點個數(shù)確定出最終簇首節(jié)點；簇首節(jié)點位置應(yīng)盡量滿足距離區(qū)域中心距離最近的要求，由此將節(jié)點與區(qū)域中心的距離作為相對位置衡量因子引入閾值計算中；穩(wěn)定傳輸數(shù)據(jù)時，簇內(nèi)節(jié)點與簇首節(jié)點通信，采用多跳與單跳結(jié)合的方式，如果簇首節(jié)點與節(jié)點距離很近，屬于鄰居節(jié)點，那么節(jié)點直接將數(shù)據(jù)發(fā)送給簇首節(jié)點，若相距較遠，則根據(jù)FOA_C算法找到的最優(yōu)路徑依靠其他節(jié)點的多跳轉(zhuǎn)發(fā)，將數(shù)據(jù)發(fā)送出去。

3 仿真與分析

仿真參數(shù)如表1所示?；诠墐?yōu)化算法的分簇路由協(xié)議仿真結(jié)果分析如下：

表1 仿真參數(shù)表

（1）可靠性比較

圖2中可以看出MRP-FOA協(xié)議中基站接收數(shù)據(jù)包最穩(wěn)定且數(shù)量最多，這是因為本文在設(shè)計網(wǎng)絡(luò)模型時考慮到礦井巷道監(jiān)測的獨特性，因此采用等分區(qū)間設(shè)置多個Sink節(jié)點，縮短簇首節(jié)點與Sink節(jié)點間的距離。

圖2 數(shù)據(jù)包接收率

(2)死亡節(jié)點數(shù)量比較

圖3中可以明顯看出失效節(jié)點數(shù)量隨時間的變化趨勢，MRP-FOA協(xié)議死亡節(jié)點數(shù)量最少，網(wǎng)絡(luò)生命周期持續(xù)最長（實驗設(shè)定90%節(jié)點死亡時間為網(wǎng)絡(luò)生命周期）。

圖3 死亡節(jié)點數(shù)量

4 結(jié)論

本文優(yōu)化了簇間通信機制，在簇內(nèi)普通節(jié)點到簇首的路徑選擇上，通過改變步長優(yōu)化果蠅算法的收斂速度，同時結(jié)合簇內(nèi)節(jié)點到簇首歐式距離以及節(jié)點能量創(chuàng)造適應(yīng)度函數(shù)，利用改進的果蠅優(yōu)化算法FOA_C得到簇內(nèi)節(jié)點到簇首的最短路徑，使得穩(wěn)定傳輸階段，簇內(nèi)數(shù)據(jù)信息收集時，節(jié)點能耗降低，進而達到整體網(wǎng)絡(luò)能耗降低的效果。

無線傳感網(wǎng)在礦井方面的使用已經(jīng)引起廣泛地關(guān)注和討論，本文大量調(diào)研了關(guān)于礦井無線傳感網(wǎng)層次路由算法的相關(guān)研究，針對煤礦井下網(wǎng)絡(luò)的特殊結(jié)構(gòu)和層次路由協(xié)議的不同應(yīng)用，進行深入分析和對比各算法的優(yōu)勢和不足之處，層次路由算法將散落在窄長巷道的傳感器節(jié)點分簇，便于這種特殊拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)構(gòu)造，針對不同的問題，如能耗、時延等各協(xié)議給出了相應(yīng)的改進策略，但大多是以高能耗為代價，減少時延和保障通信質(zhì)量，或是為降低時延而增加網(wǎng)絡(luò)帶寬的開銷。