李志勇

(大眾報業(yè)集團 信息技術(shù)部, 山東 濟南 250014)

0 引言

作為一種新型的自組織網(wǎng)絡(luò)，移動機會網(wǎng)絡(luò)的通信過程在端到端間實現(xiàn)，對于網(wǎng)絡(luò)傳輸中的延遲具有一定的容忍度，不同于傳統(tǒng)的自組織網(wǎng)絡(luò)(基于TCP/IP協(xié)議)，機會網(wǎng)絡(luò)的網(wǎng)絡(luò)通信基于“存儲-攜帶-轉(zhuǎn)發(fā)”機制實現(xiàn)，移動機會網(wǎng)絡(luò)消息的傳輸主要通過規(guī)律或隨機移動的節(jié)點所產(chǎn)生的相遇機會實現(xiàn)，無需搭建和維護從源節(jié)點到目的節(jié)點的完整路徑。受到自身特殊性的影響，機會網(wǎng)絡(luò)的節(jié)點經(jīng)常處于資源嚴重受限的狀態(tài)，導(dǎo)致其存在拓撲割裂頻繁、傳輸時延較高等不足。但在包括海洋探測、野生動物追蹤、軍事等在內(nèi)的部分極端應(yīng)用環(huán)境中，通過合理部署移動機會網(wǎng)絡(luò)可得到較佳的效果，由于其網(wǎng)絡(luò)節(jié)點的帶寬和存儲能力較低，如何實現(xiàn)消息的合理路由轉(zhuǎn)發(fā)以及避免消息泛濫成為機會網(wǎng)絡(luò)的一項研究重點。

1 設(shè)計原理

移動機會網(wǎng)絡(luò)具有資源有限、拓撲變化、節(jié)點移動頻繁、鏈路間歇性連接、時延高、安全性不足等特點，不同于傳統(tǒng)網(wǎng)絡(luò)，移動機會網(wǎng)絡(luò)中的節(jié)點傳遞消息時不建立完整的傳輸路徑，產(chǎn)生消息后的節(jié)點繼續(xù)移動，遇到其他子區(qū)域的節(jié)點后，在各自的通信范圍內(nèi)完成數(shù)據(jù)的交換，或向移動時遇到的節(jié)點傳遞消息，再經(jīng)過多跳傳輸后完成到目的節(jié)點的消息轉(zhuǎn)發(fā)過程，即移動機會網(wǎng)絡(luò)采用存儲-攜帶-轉(zhuǎn)發(fā)方式通過節(jié)點的移動與接觸完成數(shù)據(jù)傳輸。相繼被提出的多備份路由協(xié)議以實現(xiàn)提高移動機會網(wǎng)絡(luò)的數(shù)據(jù)擴散效率為目標，例如，一種改進的移動機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法；一種突發(fā)災(zāi)害應(yīng)急路由算法，主要結(jié)合社會活動和物理接觸設(shè)計；一種移動社交網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)方案；一種基于歷史信息的路由協(xié)議；類似傳染病擴散的EpidemicRouting算法，在降低傳輸時延的同時有效提高了數(shù)據(jù)傳輸投遞率，但存在明顯的網(wǎng)絡(luò)負載大、資源開銷大的不足；PeopleRank路由算法，包含少量的能量算法，將物流節(jié)點按照其社交性的高低進行排序，再以節(jié)點的中心度為依據(jù)完成路由決策，Geo-Social進行轉(zhuǎn)發(fā)決策，在以位置歷史作為社會特征的基礎(chǔ)上確定新的地理社會指標，使用效用值高的節(jié)點傳遞消息；針對資源受限的移動機會網(wǎng)絡(luò)，關(guān)于移動網(wǎng)絡(luò)的能量優(yōu)化路由算法、低功耗傳輸策略、最優(yōu)數(shù)據(jù)傳播問題、能量使用效率問題等方面的研究。移動社會網(wǎng)絡(luò)在實際通信過程中離不開能量的支持，而各移動設(shè)備能量有限，忽略能量因素易導(dǎo)致頻繁傳輸數(shù)據(jù)的關(guān)鍵節(jié)點過早死亡。部分緊急服務(wù)場景中的網(wǎng)絡(luò)節(jié)點難以及時補充能量，能量耗盡無法繼續(xù)工作，進而中斷了其他通過該節(jié)點的路徑，阻礙通信過程的正常進行。在延遲容忍網(wǎng)絡(luò)中，為保證網(wǎng)絡(luò)節(jié)點的存活率，避免因過度活躍而導(dǎo)致的低能量節(jié)點死亡問題，可根據(jù)節(jié)點的剩余能量，選用能量較高的節(jié)點傳輸數(shù)據(jù)[1-2]。本文在現(xiàn)有研究成果的基礎(chǔ)上，兼顧數(shù)據(jù)傳輸性能和較低的能量消耗，設(shè)計了一種節(jié)點不相交的路由算法，實現(xiàn)對網(wǎng)絡(luò)節(jié)點存活時間的延長，使網(wǎng)絡(luò)中節(jié)點能量消耗更加均衡。

2 路由算法設(shè)計分析

2.1 功能分析與設(shè)計

在網(wǎng)絡(luò)中通過洪泛路由算法可實現(xiàn)消息的快速擴散，此時網(wǎng)絡(luò)中存在較多相同的消息副本，在不限制網(wǎng)絡(luò)資源和節(jié)點能量等時具有最優(yōu)的數(shù)據(jù)投遞性能。但移動機會網(wǎng)絡(luò)在間歇性連接的情況下進行數(shù)據(jù)傳輸時，通常不存在完整路徑，且機會網(wǎng)絡(luò)中的移動設(shè)備能量有限，目前移動網(wǎng)絡(luò)在軍事、野外等較惡劣的現(xiàn)實環(huán)景下應(yīng)用較多，一旦鏈路中某個設(shè)備能量不足且無法進行能量補充時，將阻礙數(shù)據(jù)傳輸過程的正常進行。為此本文設(shè)計了一種節(jié)點不相交路由算法，規(guī)定全部中間節(jié)點(除源節(jié)點外)的數(shù)據(jù)包轉(zhuǎn)發(fā)機會均只有一次，完成一次數(shù)據(jù)傳輸后的中間節(jié)點不能向其他非目的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包，進而使任意兩條路徑上不會同時出現(xiàn)已轉(zhuǎn)發(fā)過數(shù)據(jù)包的某一中間節(jié)點，進而使關(guān)鍵節(jié)點因能力不足而過早死亡問題得以有效避免，實現(xiàn)了網(wǎng)絡(luò)存活時間的有效延長。對應(yīng)的多徑路由的示意圖，如圖1所示。

圖1 節(jié)點不相交多徑路由

A表示一般節(jié)點，S和D分別表示源節(jié)點和目的節(jié)點，箭頭表示數(shù)據(jù)傳輸方向，除相交的路徑與節(jié)點外共有3條源到目的節(jié)點的路徑。本文路由算法的設(shè)計目標為：相比于洪泛路由算法中副本的數(shù)量，移動機會網(wǎng)絡(luò)中單個消息的副本數(shù)明顯減少并盡可能提高傳遞率，消息的傳遞延遲則盡可能相近，最大程度降低節(jié)點的能量消耗[3]。

2.2 路由策略

本文路由算法的前提假設(shè)為：數(shù)據(jù)傳輸不存在信道爭用，網(wǎng)絡(luò)節(jié)點位置隨時間的推移呈現(xiàn)動態(tài)變化，各節(jié)點的能量均有限制，通信范圍內(nèi)的任意兩節(jié)點均具有傳輸數(shù)據(jù)的可能。為實現(xiàn)節(jié)點不相交，避免同一個節(jié)點轉(zhuǎn)發(fā)兩次數(shù)據(jù)，將一個初值為False的標志位Forwarded設(shè)置于各網(wǎng)絡(luò)節(jié)點中，F(xiàn)orwarded在節(jié)點接收并轉(zhuǎn)發(fā)數(shù)據(jù)后置為True，據(jù)此完成對節(jié)點轉(zhuǎn)發(fā)過數(shù)據(jù)與否的判斷。假設(shè)，由非源節(jié)點i攜帶消息，i從未復(fù)制轉(zhuǎn)發(fā)過攜帶消息時的Forwarded為False，當(dāng)i在網(wǎng)絡(luò)中移動遇到j(luò)時，若j為目的節(jié)點則直接傳遞消息；在j不是目的節(jié)點的情況下，若其含有i攜帶的消息副本則不轉(zhuǎn)發(fā)數(shù)據(jù)，若不含有i攜帶的消息副本則i會向j復(fù)制轉(zhuǎn)發(fā)消息，完成一次數(shù)據(jù)傳輸，之后i和j繼續(xù)移動并按照同樣策略進行轉(zhuǎn)發(fā)，此時由于i已轉(zhuǎn)發(fā)過一次消息其Forwarded變?yōu)門rue，i在接下來的移動中除非遇到目的節(jié)點否則不再轉(zhuǎn)發(fā)數(shù)據(jù)，以避免出現(xiàn)路徑相交問題。在遇到目的節(jié)點時，無論節(jié)點的Forwarded是False還是True均需傳輸數(shù)據(jù)，以完成通信任務(wù)。從而有效避免多條路徑出現(xiàn)同一節(jié)點的問題，使消息副本數(shù)量和能量消耗均得到明顯降低。同一種消息各節(jié)點僅能轉(zhuǎn)發(fā)一次則有效避免了關(guān)鍵節(jié)點出現(xiàn)過早死亡問題[4]。

3 模型設(shè)計

3.1 馬爾可夫鏈模型的建立

本文設(shè)計使用一個“病毒傳染”模型表示數(shù)據(jù)傳輸過程，源節(jié)點、未含消息副本的節(jié)點和目的節(jié)點分別對應(yīng)模型中的病毒感染點、易感節(jié)點和治療院，稱首次被感染的節(jié)點為傳染節(jié)點，其中，易感節(jié)點僅感染一次同一種病毒，每一個接觸病毒感染點的易感節(jié)點均能被其感染，非目的節(jié)點僅能被各傳染節(jié)點感染一次，感染某一易感節(jié)點后的傳染節(jié)點變?yōu)榈却委熢壕戎蔚墓?jié)點(此時不再具備傳染的功能)，易感節(jié)點可轉(zhuǎn)變?yōu)閭魅竞偷却戎蝺煞N狀態(tài)，這兩種狀態(tài)下的節(jié)點均稱為感染節(jié)點，節(jié)點不相交的目的通過設(shè)置僅具備一次傳染病毒機會的其他節(jié)點(除病毒感染點以外)實現(xiàn)。采用馬爾可夫鏈完成對受感染節(jié)點數(shù)目變化情況的建模，該節(jié)點不相交模型具體基于洪泛建立，易感節(jié)點由源病毒點和傳染節(jié)點感染后轉(zhuǎn)變形成傳染節(jié)點，由S→A表示，由A→W表示經(jīng)傳染節(jié)點轉(zhuǎn)變的等待救治節(jié)點，采用3層結(jié)構(gòu)的模型示意圖，如圖2所示。

圖2 洪泛傳染病馬爾可夫鏈模型示意圖

A對應(yīng)傳染狀態(tài)，S對應(yīng)易感狀態(tài)，W對應(yīng)等待救治狀態(tài)，這3種狀態(tài)中涵蓋了所有節(jié)點。此外，被感染后的易感節(jié)點是轉(zhuǎn)變?yōu)閭魅緺顟B(tài)的唯一路徑，變?yōu)閭魅緺顟B(tài)后的節(jié)點才能轉(zhuǎn)變?yōu)榈却戎螤顟B(tài)[5]。

3.2 模型分析

易感節(jié)點由病毒感染點與傳染節(jié)點感染后完成到傳染節(jié)點的轉(zhuǎn)變，被病毒感染后的傳染節(jié)點變?yōu)榈却戎螤顟B(tài)，因傳染節(jié)點的一次數(shù)據(jù)轉(zhuǎn)發(fā)而導(dǎo)致等待救治節(jié)點數(shù)量增加，傳染節(jié)點狀態(tài)對傳染節(jié)點數(shù)量變化不構(gòu)成影響，網(wǎng)絡(luò)節(jié)點狀態(tài)數(shù)量變化情況如圖3所示，圓圈對應(yīng)具體的時刻，箭頭表示數(shù)量變化情況，(i，j)對應(yīng)當(dāng)前時刻的某一狀態(tài)，其中i和j分別表示傳染節(jié)點的數(shù)目和等待救治節(jié)點的數(shù)目，這兩個數(shù)目的變化情況分別由IA和IW表示，狀態(tài)(i，j)向(i+1，j)的轉(zhuǎn)變表示保持j不變的同時增加1個傳染節(jié)點數(shù)目，說明此時有一個易感節(jié)點被病毒感染點感染了，因此IA++；狀態(tài)(i，j)向(i，j+1)的轉(zhuǎn)變表示某一被病毒感染后的傳染節(jié)點變?yōu)榈却戎蔚墓?jié)點，因此IW++，在原感染點不感染其他節(jié)點時被感染的節(jié)點變?yōu)閭魅竟?jié)點不會改變i的總數(shù)。假設(shè)，系統(tǒng)模型中初始時共包含節(jié)點N個，其中的病毒感染點(同時作為感染節(jié)點)和易感節(jié)點分別為1個、S個，無等待救治的節(jié)點。N表示節(jié)點的總數(shù)目，β表示節(jié)點的接觸率，I表示感染節(jié)點數(shù)目總和，在t時刻，系統(tǒng)中易受感染的節(jié)點數(shù)目由S(t)表示、感染節(jié)點數(shù)目由I(t)表示、傳染節(jié)點數(shù)目由IA(t)表示、等待救治節(jié)點數(shù)目由IW(t)表示，β(N-1)表示單位時間內(nèi)各節(jié)點接觸的節(jié)點數(shù)，S/(N-1)表示模型中未感染節(jié)點的占比。各類感染節(jié)點的數(shù)量變化，如圖3所示。

圖3 感染節(jié)點數(shù)目變化圖

采用馬爾可夫鏈(CTMC)模型完成追蹤，狀態(tài)S到IA的轉(zhuǎn)變率為：新增的傳染節(jié)點數(shù)目=βS(即源節(jié)點、單位時間接觸節(jié)點數(shù)和未感染節(jié)點的比例三者乘積)狀態(tài)IA到IW的轉(zhuǎn)變率為：新增的等待救治的節(jié)點數(shù)目=βS(IA- 1)(即傳染節(jié)點、單位時間接觸節(jié)點數(shù)和未感染節(jié)點比例三者乘積)。據(jù)此得出節(jié)點數(shù)量轉(zhuǎn)變的馬爾可夫模型[6]，如圖4所示。

圖4 節(jié)點數(shù)量變化的馬爾可夫鏈模型

狀態(tài)S和I中涵蓋了整個模型中節(jié)點狀態(tài)，假設(shè)各類病毒的傳染具有獨立性，在初始即t=0時，S=N-1，IA(0)=1，IW(0)=0，節(jié)點數(shù)目變化的瞬態(tài)解如下。

I=IA+IW，兩個時間函數(shù)IA(t)和IW(t)的表達式[7]如下。

3.3 模型驗證

對本文模型系統(tǒng)進行驗證和評估，需先完成節(jié)點間的接觸概率β值的計算，具體通過對每個S與IA、IA與IW感染的時間進行多次模擬和記錄實現(xiàn)，例如，記錄Δt時間間隔內(nèi)的狀態(tài)IA=i→IA=i+1、狀態(tài)IW=j→IW=j+1，取多次模擬中β的平均值。節(jié)點數(shù)目在某一時刻Δt內(nèi)由狀態(tài)S到A的瞬態(tài)解為βS，推出β=1/SΔt；同理推出由狀態(tài)A到W時的β=1/(S(IA-1)Δt)，取不同狀態(tài)上β的平均值，據(jù)此得到模型的β。通過參數(shù)β模擬上述模型，移動機會網(wǎng)絡(luò)中共包含90個節(jié)點，以KAIST中的真實數(shù)據(jù)集作為節(jié)點移動情況，模擬時間為15 000S，受感染節(jié)點數(shù)變化情況，如圖5所示。

模型曲線同理論結(jié)果基本吻合，能夠?qū)崿F(xiàn)對受感染節(jié)點數(shù)變化的準確預(yù)測，說明該模型合理有效[7]。

圖5 受感染節(jié)點數(shù)變化擬合曲線

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

設(shè)計仿真實驗對比本文路由算法和其他算法的性能，仿真時間設(shè)為15000S，仿真實驗采用KAIST的真實數(shù)據(jù)集，各節(jié)點的通信距離最大為250m，設(shè)置各節(jié)點的初始能量為10000個能量單位，接收或轉(zhuǎn)發(fā)數(shù)據(jù)各需消耗1個，通過使用VisualC++平臺完成了5種路由算法的集成，即Epidemic(基于洪泛的路由算法)、PageRank、PageRankEpidemicDisjointPath(基于中心度節(jié)點不相交的算法)、EpidemicDisjointPath(基于洪泛路徑不相交的路由算法)和Geosocial，已有文獻詳細介紹了該移動機會網(wǎng)絡(luò)模擬器平臺[8]。實驗初始時，從KAIST中隨機選出1 000對源-目的節(jié)點對，根據(jù)不同指標性能對比分析路由算法的性能，5種算法的投遞率的仿真結(jié)果，如圖6所示。

圖6 投遞率

EpidemicDisjointPath路由算法的投遞率僅次于最高的Epidemic路由算法，并且在7 500 S后增長緩慢，最早穩(wěn)定在0．9左右；0-7 000 S時，相比于PageRank和Geosocial，PageRankEpidemicDisjointPath算法的投遞率更高，7 000 S后逐漸趨近于PageRank并小于Geosocial算法?？偰芰肯姆抡娼Y(jié)果，如圖7所示。

圖7 總能量消耗

5種路由算法的能量消耗均隨時間的延長而增加，PageRank能量消耗最低，洪泛所達到的最高投遞率通過不計代價完成數(shù)據(jù)傳輸實現(xiàn)，因此會消耗掉大量的能量，其能量消耗快速達到巔峰，繼續(xù)傳輸剩余少量未投遞消息時能量消耗增長緩慢；EpidemicDisjointPath算法的能量消耗曲線變化趨勢同Epidemic基本相同，但消耗明顯小于Epidemic算法，能量消耗控制效果較佳；相比于Geosocial，PageRankEpidemicDisjointPath的能量消耗更少，并隨時間推移逐漸趨近于PageRank。說明通過節(jié)點不相交的方式的使用實現(xiàn)了對能量消耗的有效控制。平均投遞延時仿真結(jié)果，如圖8所示。

圖8 平均投遞延時

投遞延時隨時間推移而增大，Epidemic的投遞延時最小，PageRankEpidemicDisjointPath的投遞延時略大于Epidemic，EpidemicDisjointPath的投遞延時在7 500 S后開始放緩增長，最終低于Geosocial。平均網(wǎng)絡(luò)開銷(即消息在網(wǎng)絡(luò)中平均的副本數(shù))的仿真對比結(jié)果，如圖9所示。

圖9 平均網(wǎng)絡(luò)開銷

Epidemic的數(shù)據(jù)傳輸通過相遇的各節(jié)點進行，導(dǎo)致存在大量的消息副本，其網(wǎng)絡(luò)開銷在初始時急劇增長(所有網(wǎng)絡(luò)開銷幾乎均在此時產(chǎn)生)且已經(jīng)含有大量副本，此時其投遞率已趨于1，僅剩余少量的未投遞消息，隨后只產(chǎn)生少量副本；EpidemicDisjointPath的各節(jié)點僅轉(zhuǎn)發(fā)一次消息，明顯較少了網(wǎng)絡(luò)中的消息副本數(shù)量；其他3種算法的網(wǎng)絡(luò)開銷均明顯小于Epidemic，PageRankEpidemicDisjointPath的網(wǎng)絡(luò)開銷在15000S時幾乎與PageRank重合，預(yù)計隨后會小于PageRank。仿真實驗驗證了基于路徑不相交的路由算法的有效性，在較高投遞率下可實現(xiàn)對能量消耗的有效控制，其節(jié)點能量消耗的均衡性較好，可避免鏈路中斷的出現(xiàn)。

5 總結(jié)

目前多副本路由協(xié)議成為提升網(wǎng)絡(luò)中數(shù)據(jù)傳輸速度的有效手段，但由于缺少對能量問題的考慮，而易導(dǎo)致消耗能量較多時出現(xiàn)設(shè)備停止工作的狀況。考慮到移動機會網(wǎng)絡(luò)中沒有完整的傳輸路線且網(wǎng)絡(luò)節(jié)點的能量有限，為有效解決其中的數(shù)據(jù)傳遞能量消耗問題，本文設(shè)計了一種多路徑解決方案及路由算法，分析節(jié)點狀態(tài)間的變換，詳細介紹了節(jié)點不相交路由策略，利用二維連續(xù)時間馬爾可夫鏈完成了系統(tǒng)模型的構(gòu)建，并給出問題的求解方法，最后通過仿真實驗對比分析了本文算法和其他路由算法的相關(guān)性能，結(jié)果表明本文方案具有一定的研究價值，為進一步優(yōu)化和完善移動機會網(wǎng)絡(luò)提供參考。