楊 萍，李敬兆，張小波，呂 樂，唐 俊

(1.安徽理工大學(xué) 電氣與信息工程學(xué)院，安徽 淮南 232001；2.中國科學(xué)技術(shù)大學(xué)，安徽 合肥 231600；3.陜西延長石油榆林煤化有限公司，陜西 榆林 719000)

煤炭作為科技發(fā)展的重要工業(yè)能源[1]，煤炭工業(yè)為我國經(jīng)濟(jì)發(fā)展提供了重要支持。然而，由于煤礦井下空間異構(gòu)、環(huán)境惡劣，導(dǎo)致瓦斯事故、機(jī)電故障等時常發(fā)生。因此，需要對礦井進(jìn)行全覆蓋、不間斷的安全監(jiān)測。但是礦井有線通信部署困難，成本較高；無線信號衰減快，存在視野盲區(qū)。在這種情況下，機(jī)會網(wǎng)絡(luò)被引入到礦井通信系統(tǒng)中。

機(jī)會網(wǎng)絡(luò)(OPportunistic NETwork)是一種不需要進(jìn)行網(wǎng)絡(luò)部署，對基礎(chǔ)設(shè)備要求不高的移動自組織網(wǎng)絡(luò)[2，3]，常應(yīng)用在車載網(wǎng)絡(luò)、災(zāi)難應(yīng)急、野外數(shù)據(jù)收集等領(lǐng)域[4-6]。機(jī)會網(wǎng)絡(luò)是通過移動節(jié)點間的相遇帶來的通信機(jī)會進(jìn)行數(shù)據(jù)的傳輸[7]，所采用的路由機(jī)制是“存儲—攜帶—轉(zhuǎn)發(fā)”，在中繼節(jié)點上緩存信息，遇到其他節(jié)點時進(jìn)行信息轉(zhuǎn)發(fā)，直到信息到達(dá)目的節(jié)點[8]。一般地，機(jī)會網(wǎng)絡(luò)中的節(jié)點是由人攜帶的便攜性通信終端構(gòu)成[9]，具有移動性強(qiáng)、網(wǎng)絡(luò)連接間歇性[10]和網(wǎng)絡(luò)延時大的特點。

因此，在礦井實際應(yīng)用場景中，攜帶通信設(shè)備的礦工和車輛可視為移動節(jié)點，通過日常工作活動和交流，使得節(jié)點相遇，從而實現(xiàn)數(shù)據(jù)傳輸。因為人是具有社會性的，根據(jù)工作任務(wù)來進(jìn)行活動，相應(yīng)地，節(jié)點也具有一定的社會性，節(jié)點移動的隨機(jī)性減小[11]。針對以上實際特點，本文提出一種基于消息效用的煤礦井下概率路由算法，根據(jù)節(jié)點的聚散程度劃分為不同社區(qū)[12]，并依據(jù)社區(qū)內(nèi)外節(jié)點的社會性，設(shè)計不同的路由機(jī)制，使得消息投遞成功率提高、網(wǎng)絡(luò)延時降低；并建立緩存管理機(jī)制，合理管控節(jié)點緩存空間[13]，減少網(wǎng)絡(luò)中的冗余消息。

1 文獻(xiàn)綜述

機(jī)會網(wǎng)絡(luò)是依靠節(jié)點的移動傳遞消息，這便決定了網(wǎng)絡(luò)延時較高、投遞成功率低等特性，為解決這個問題，一般從緩存管理策略和路由策略兩大方面解決機(jī)會網(wǎng)絡(luò)消息傳遞過程出現(xiàn)的問題。

文獻(xiàn)[14]針對礦井環(huán)境和礦工移動特點分區(qū)建立馬爾可夫模型，通過綜合開考慮計算出終端網(wǎng)絡(luò)時延、 與目的節(jié)點相遇概率和擴(kuò)散范圍，最后選擇最合適消息轉(zhuǎn)發(fā)策略，實現(xiàn)分組低延時轉(zhuǎn)發(fā)。但是在終端活躍度差異不大，活動范圍較大的情況下，不能良好地模擬出礦井的實際情況，并且沒有考慮緩存空間和網(wǎng)絡(luò)中的冗余副本，造成網(wǎng)絡(luò)負(fù)擔(dān)較大。

文獻(xiàn)[15]以消息傳遞概率作為消息轉(zhuǎn)發(fā)依據(jù)，先后計算當(dāng)前一跳和二跳節(jié)點的消息傳輸概率；將二跳節(jié)點的消息傳輸概率與一跳節(jié)點的消息傳輸概率比較，若一跳節(jié)點的消息傳輸概率大于二跳節(jié)點，優(yōu)先選擇一跳節(jié)點中消息傳遞概率大的節(jié)點傳輸消息；若都不是，則將消息存于緩存區(qū)。該算法減少了網(wǎng)絡(luò)中的消息副本，并提高了消息投遞成功率，但是算法復(fù)雜，使得網(wǎng)絡(luò)延時增加。

文獻(xiàn)[16]提出了基于運(yùn)動相似性的機(jī)會網(wǎng)絡(luò)緩存管理策略，首先定義并計算節(jié)點的消息擴(kuò)散程度和運(yùn)動相似性，從而得出消息轉(zhuǎn)發(fā)效用值和存儲效用值；其次，依據(jù)消息轉(zhuǎn)發(fā)效用值來選擇合適的節(jié)點轉(zhuǎn)發(fā)消息，當(dāng)緩存空間溢出時，優(yōu)先丟棄存儲效用值較低的消息。該算法將節(jié)點運(yùn)動相似性和緩存空間作為消息轉(zhuǎn)發(fā)概率影響因素，有效減少節(jié)點的盲目攜帶，降低了網(wǎng)絡(luò)負(fù)載，但是沒有考慮節(jié)點相遇持續(xù)時間對節(jié)點消息轉(zhuǎn)發(fā)的影響，該算法的消息投遞成功率有待提高。

文獻(xiàn)[17]通過收集節(jié)點的歷史接觸信息，包括節(jié)點的相遇時間、相遇次數(shù)和節(jié)點關(guān)系穩(wěn)定度，以此計算節(jié)點轉(zhuǎn)發(fā)效用值；然后，在通信范圍內(nèi)選擇消息轉(zhuǎn)發(fā)效用值最大的節(jié)點轉(zhuǎn)發(fā)消息；最后，根據(jù)余弦相似度選擇下一節(jié)點轉(zhuǎn)發(fā)消息。該算法使得轉(zhuǎn)發(fā)節(jié)點最大程度均勻分布，但是容易導(dǎo)致消息重復(fù)擴(kuò)散，并且對于活躍度大，消息轉(zhuǎn)發(fā)概率高的節(jié)點利用率不高。

本文根據(jù)井下移動節(jié)點移動規(guī)律和節(jié)點間的社會性，對節(jié)點移動范圍進(jìn)行分區(qū)，根據(jù)社區(qū)內(nèi)外的節(jié)點移動屬性選擇不同的路由傳輸策略。通過加入節(jié)點的相遇持續(xù)時間、移動軌跡相似度等相關(guān)因素，形象模擬了井下節(jié)點的移動特征，有效地提高了消息投遞成功率，并大幅度降低了消息延時和網(wǎng)絡(luò)負(fù)載。

2 網(wǎng)絡(luò)模型及定義

2.1 礦井機(jī)會網(wǎng)絡(luò)模型

煤礦井下通信信號差，巷道中節(jié)點間的通信鏈路間歇性連接甚至不連接，因此通過增加礦工和礦車攜帶的移動通信設(shè)備，從而增強(qiáng)井下的通信交流。礦工或礦車表示移動節(jié)點，因此節(jié)點間具有一定的社會關(guān)系，并保持相對穩(wěn)定。節(jié)點間的密切程度與工作內(nèi)容相關(guān)[18]，因此煤礦井下的節(jié)點間可形成一種隱形的工作關(guān)系網(wǎng)絡(luò)，這種關(guān)系網(wǎng)絡(luò)表示了節(jié)點間因工作而產(chǎn)生的聯(lián)系程度，定義網(wǎng)絡(luò)的節(jié)點集合V={v1，v2，…，vn}，節(jié)點之間的關(guān)系連接集合E?{(a，b)|a，b∈V}，那么可以得到加權(quán)無向圖：

G=(V，E，ρ)(1)

式中，ρa(bǔ)，b表示節(jié)點a和節(jié)點b的關(guān)聯(lián)性，數(shù)值越大，表示節(jié)點a和節(jié)點b之間相遇頻率越高、密切程度越高；若(a，b)?E，那么ρa(bǔ)，b=0，即節(jié)點a和節(jié)點b之間無交集；ρa(bǔ)，b∈[0，1]，根據(jù)工作安排調(diào)整參數(shù)。在社區(qū)內(nèi)部，節(jié)點密度較高，聯(lián)系頻繁，而處于不同社區(qū)的節(jié)點聯(lián)系的頻率相對較低。因此，將網(wǎng)絡(luò)按照節(jié)點密度劃分為不同的社區(qū)。

井下礦工和礦車的往往遵循相同的移動規(guī)律，他們會根據(jù)自己的工作任務(wù)在固定的巷道中移動，行駛相同的移動軌跡，因此本文選用基于地圖的固定路線的MRM(Map Route Movement)作為移動模型[19]，用其來模擬礦車和礦工在井下工作的移動規(guī)律。礦井機(jī)會網(wǎng)絡(luò)的應(yīng)用場景如圖1所示。

圖1 礦井機(jī)會網(wǎng)絡(luò)應(yīng)用場景

2.2 相關(guān)定義

1)定義1 ：節(jié)點相遇持續(xù)時間。井下移動節(jié)點的工作活動往往表現(xiàn)出周期性的規(guī)律，并且，節(jié)點間的關(guān)系隨著移動過程中與其他節(jié)點頻繁建立連接而加強(qiáng)。節(jié)點在移動過程中可以和一個節(jié)點建立多次通信或者和多個節(jié)點建立通信，每次的通信時間都不相同，若節(jié)點間的通信次數(shù)越多，通信時間越長，表明節(jié)點間的關(guān)聯(lián)性越強(qiáng)。那么用通信時長表示節(jié)點間的關(guān)系程度，設(shè)計在時間T內(nèi)，節(jié)點a和節(jié)點b間建立通信n次，通信時間集合為{t1，t2，…，tn}，那么節(jié)點的相遇持續(xù)時間公式為：

ρa(bǔ)，b=Ta，b/T=(t1+t2+…+tn)/T(2)

式中，Ta，b表示節(jié)點a與節(jié)點b相遇持續(xù)時間總和。

2)定義2：節(jié)點移動軌跡相似度。煤礦井下的礦工和礦車的每天工作幾乎無異，因此它們的移動軌跡往往有著高度重合性，通過比較礦工當(dāng)前的移動軌跡和歷史移動軌跡，衡量該節(jié)點歷史移動軌跡信息的可用性，以節(jié)點的移動軌跡去輔助預(yù)測節(jié)點的相遇概率，在時間T內(nèi)，取m個軌跡點。節(jié)點i的歷史軌跡按照時間順序由軌跡點組成，歷史移動軌跡為{p1，p2，…，pm}，當(dāng)前的移動軌跡為{q1，q2，…，qm}，則節(jié)點i移動軌跡相似度計算公式：

其中，匹配函數(shù)：

式中，|d|為兩軌跡點間的距離；ε為當(dāng)前和歷史節(jié)點移動軌跡點間的誤差，可根據(jù)節(jié)點移動速度適當(dāng)調(diào)整。當(dāng)兩軌跡點之間的距離少于等于ε時，match函數(shù)取值為1，表示節(jié)點歷史移動軌跡與當(dāng)前移動軌跡重合度較高，具有較高的可信度。否則match函數(shù)取值為0。

3)定義3：節(jié)點相似度。節(jié)點a和節(jié)點b的相似率是指節(jié)點a與節(jié)點b擁有的共同相遇節(jié)點個數(shù)與它們兩個節(jié)點分別相遇的節(jié)點總數(shù)的比值。

式中，Na表示在時間T內(nèi)節(jié)點a所相遇的節(jié)點；Nb表示在時間T內(nèi)節(jié)點b所相遇的節(jié)點。

3 基于消息效用的煤礦井下概率路由算法

根據(jù)煤礦井下工作內(nèi)容的不同將節(jié)點活動分為兩類：①工作活動限制在一個范圍內(nèi)，定義為社區(qū)內(nèi)；②在不同的工作區(qū)域活動，定義為社區(qū)間。

3.1 社區(qū)內(nèi)消息效用值轉(zhuǎn)發(fā)策略

同一個區(qū)域內(nèi)礦工的工作內(nèi)容和范圍相同，對于社區(qū)內(nèi)的消息傳遞概率也大致相同，優(yōu)先選擇節(jié)點中緩存空間、活躍度高的節(jié)點，消息投遞的成功率也更大。用消息轉(zhuǎn)發(fā)效用值作為判斷依據(jù)，節(jié)點選擇消息轉(zhuǎn)發(fā)效用值最大的進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)。

其中，Ti為節(jié)點i在時間T內(nèi)與其他節(jié)點相遇持續(xù)時間總和；Ni為節(jié)點i在時間T內(nèi)相遇節(jié)點個數(shù)，N表示總節(jié)點個數(shù)；Bfree為節(jié)點剩余緩存空間；Btotal為節(jié)點總緩存空間。

3.2 社區(qū)間移動軌跡輔助決策消息轉(zhuǎn)發(fā)策略

節(jié)點的移動軌跡和歷史移動軌跡重合度越高，則節(jié)點歷史信息的可信度越高。利用節(jié)點移動軌跡相似度輔助相遇概率的預(yù)測，相遇概率的計算分為更新、衰退、和傳遞三個部分。

1)更新。當(dāng)社區(qū)間的兩節(jié)點相遇時，用一下公式更新投遞概率：

P(a，b)=P(a，b)old+[1-P(a，b)old]MS(a)(7)

2)衰減。當(dāng)兩節(jié)點在一段時間內(nèi)，相遇次數(shù)減少甚至無相遇，那么他們之間的相遇概率也會降低，由此得到衰減投遞概率公式：

3)傳遞。若節(jié)點a、c都能與目的節(jié)點b相遇，那節(jié)點a便可通過中間節(jié)點c將消息傳遞給目的節(jié)點b。那么節(jié)點的傳遞性投遞概率公式為：

P(a，c)=P(a，c)old+[1-P(a，c)old]

P(a，b)P(b，c)ρa(bǔ)，c(9)

3.3 路由算法

3.3.1 消息轉(zhuǎn)發(fā)流程

路由算法的步驟及流程如圖2所示。

圖2 路由算法流程

3.3.2 ACK刪除機(jī)制

由于冗余的消息副本在網(wǎng)絡(luò)長時間保留會占用節(jié)點寶貴的緩存空間，并影響新消息的轉(zhuǎn)發(fā)和投遞。然而礦井下的數(shù)據(jù)十分重要，過滿的緩存空間會導(dǎo)致重要數(shù)據(jù)丟失，甚至關(guān)乎到工人的生命安全，因此設(shè)計一個合理的緩存管理十分重要。本文將添加 ACK 刪除機(jī)制來刪除冗余副本和已經(jīng)成功傳遞的消息。每個節(jié)點都有自己的列表，當(dāng)消息成功傳輸?shù)侥康墓?jié)點時，該消息就被標(biāo)上投遞成功的標(biāo)記，在與其他節(jié)點相遇交換信息列表時，可獲取相關(guān)信息，從而刪除緩存的已送達(dá)的副本。

3.3.3 社區(qū)間消息轉(zhuǎn)發(fā)示例

節(jié)點A攜帶有消息M1、M3、M5、M7，節(jié)點B攜帶有消息M2、M3、M4、M6，每條消息都有各自的目標(biāo)節(jié)點；其中節(jié)點A攜帶的消息M1的目標(biāo)節(jié)點是節(jié)點B，節(jié)點B攜帶的消息M4目標(biāo)節(jié)點是節(jié)點A。在相遇前節(jié)點A和節(jié)點B各自的消息列表如圖3所示。

圖3 節(jié)點A和節(jié)點B相遇前

節(jié)點A和B相遇后消息列表如圖4所示，節(jié)點A將消息M1傳遞給節(jié)點B，節(jié)點A刪除該條消息，節(jié)點B對M1標(biāo)記，表示投遞完成。同理，消息M4更新投遞概率，判斷是否還有消息需要轉(zhuǎn)發(fā)。

圖4 節(jié)點A和節(jié)點B相遇后

其中，節(jié)點A攜帶消息M5的目的節(jié)點是節(jié)點F，節(jié)點A和節(jié)點B相遇，節(jié)點B并非消息M5的目的節(jié)點，但是節(jié)點B對節(jié)點F的預(yù)測投遞概率大于節(jié)點A對節(jié)點F的預(yù)測投遞概率，所以節(jié)點A將消息轉(zhuǎn)發(fā)給節(jié)點B。由于節(jié)點B的緩存空間已滿，所以刪除節(jié)點B消息列表里跳數(shù)最大的消息M6，空出緩存空間，從而節(jié)點A攜帶的消息M5成功被轉(zhuǎn)發(fā)到節(jié)點B，并且節(jié)點A和節(jié)點B對消息M5的跳數(shù)增加。

4 仿真實驗及結(jié)果分析

4.1 仿真環(huán)境

本算法在One平臺模擬礦井機(jī)會路由仿真，采用MRM移動模型，仿真節(jié)點模擬煤礦井下主要移動節(jié)點：礦工、礦車和無線基站固定，選取經(jīng)典算法Epidemic算法、Porphet算法、Sprad and Wait算法和本文算法，從節(jié)點數(shù)量和節(jié)點緩存對投遞成功率、平均傳輸延時、網(wǎng)絡(luò)負(fù)載和平均剩余能量四個維度進(jìn)行性能評估。實驗的仿真參數(shù)見表1。

表1 仿真節(jié)點參數(shù)設(shè)置

4.2 不同節(jié)點緩存下的性能評估

四種算法的性能評估分別如圖5—圖8所示，從圖中可以看出本文提出的算法在投遞成功率、網(wǎng)絡(luò)負(fù)載和平均跳數(shù)上表現(xiàn)均較為優(yōu)異，從而表明本算法在井下機(jī)會網(wǎng)絡(luò)中有一定的優(yōu)勢作用。

圖5 不同節(jié)點緩存下的投遞成功率

從圖5中可以看到在節(jié)點緩存不同時，本算法在投遞成功率比Epidemic算法提高了26%，比Porphet算法提高了18%～21%，比Sprad and Wait算法提高了5%～10%。當(dāng)節(jié)點的緩存空間增大時，四種算法的投遞成功率都隨之增大，這是因為傳送的消息不用因為緩存空間不足被刪去或者選擇其他的節(jié)點暫存，從而提高了投遞成功率。

圖6、圖7的仿真結(jié)果展示了在緩存空間增大的情況下，四種算法在平均傳輸延時和網(wǎng)絡(luò)負(fù)載方面表現(xiàn)出相同的趨勢，且本算法在兩方面表現(xiàn)優(yōu)良。這是由于其他三種算法在傳輸過程中不斷增加副本，而本文算法中引入了ACK刪除機(jī)制，刪除冗余副本，從而降低網(wǎng)絡(luò)負(fù)載和平均傳輸延時。

圖6 不同節(jié)點緩存下的平均傳輸延時

圖7 不同節(jié)點緩存下的網(wǎng)絡(luò)負(fù)載

圖8表明，本文算法在節(jié)點緩存空間不斷增大時，平均跳數(shù)仍較為穩(wěn)定，這是因為本文算法通過添加ACK刪除機(jī)制刪除網(wǎng)絡(luò)中的消息副本，節(jié)點緩存空間的大小對平均跳數(shù)幾乎沒有影響。

圖8 不同節(jié)點緩存下的平均跳數(shù)

4.3 不同消息生存時間下的性能評估

下面描述了四種算法在不消息生存周期不斷增加的情況下的性能表現(xiàn)分別如圖9—圖12所示。

圖9 不同消息生存周期下的投遞成功率

圖9仿真結(jié)果表明，在消息生存周期增加的情況下，本算法的投遞成功率保持良好，甚至有所提高。這是因為消息在網(wǎng)絡(luò)中存活時間越長，相應(yīng)地，能被投遞到合適地目標(biāo)節(jié)點的概率越大。

從圖10的仿真結(jié)果可以看出，在消息生存周期增加時，平均延時大幅度增加，這是由于消息生存時間過長，一定程度上使得網(wǎng)絡(luò)中存在的冗余消息過多，增加了網(wǎng)絡(luò)負(fù)載，使得網(wǎng)絡(luò)處理消息的速度降低，從而平均傳輸時延增加。

圖10 不同消息生存周期下的平均傳輸時延

圖11、圖12的仿真結(jié)果表明本算法在生存周期增加的條件下，在網(wǎng)絡(luò)負(fù)載和平均跳數(shù)上仍表現(xiàn)不錯。這是由于本算法結(jié)合了移動軌跡相似度和節(jié)點相遇持續(xù)時間，使得節(jié)點在移動過程中能夠選擇更合適的中繼節(jié)點，并且增加的ACK刪除機(jī)制，從而在消息生存時間不變的情況下，提高消息的投遞成功率，降低網(wǎng)絡(luò)負(fù)載和減少平均跳數(shù)。

圖11 不同節(jié)消息生存周期下的網(wǎng)絡(luò)負(fù)載

圖12 不同消息生存周期下的平均跳數(shù)

5 結(jié) 語

根據(jù)礦井下機(jī)會網(wǎng)絡(luò)通信中節(jié)點的移動規(guī)律性、節(jié)點之間的相關(guān)性，提出基于消息效用的煤礦井下概率路由算法，將節(jié)點活動范圍分成不同社區(qū)，根據(jù)社區(qū)內(nèi)和社區(qū)間節(jié)點的移動特點，選擇不同的消息轉(zhuǎn)發(fā)策略，減少消息在網(wǎng)絡(luò)中的盲目傳遞，更快更準(zhǔn)確地將消息傳遞給目的節(jié)點。針對消息在傳遞過程中不斷增加副本問題，添加了ACK刪除機(jī)制，有效減少了網(wǎng)絡(luò)負(fù)載和冗余消息。One平臺仿真實驗證明，本算法更具針對性，對于煤礦井下的場景更為適用，但仍存在不足，如網(wǎng)絡(luò)延時上并沒有得到較好的改善，仍有優(yōu)化空間。