移動機會網絡路由算法應用研究

李志勇

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

0 引言

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

1 設計原理

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

2 路由算法設計分析

2.1 功能分析與設計

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

圖1 節點不相交多徑路由

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

2.2 路由策略

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

3 模型設計

3.1 馬爾可夫鏈模型的建立

本文設計使用一個“病毒傳染”模型表示數據傳輸過程，源節點、未含消息副本的節點和目的節點分別對應模型中的病毒感染點、易感節點和治療院，稱首次被感染的節點為傳染節點，其中，易感節點僅感染一次同一種病毒，每一個接觸病毒感染點的易感節點均能被其感染，非目的節點僅能被各傳染節點感染一次，感染某一易感節點后的傳染節點變為等待治療院救治的節點(此時不再具備傳染的功能)，易感節點可轉變為傳染和等待救治兩種狀態，這兩種狀態下的節點均稱為感染節點，節點不相交的目的通過設置僅具備一次傳染病毒機會的其他節點(除病毒感染點以外)實現。采用馬爾可夫鏈完成對受感染節點數目變化情況的建模，該節點不相交模型具體基于洪泛建立，易感節點由源病毒點和傳染節點感染后轉變形成傳染節點，由S→A表示，由A→W表示經傳染節點轉變的等待救治節點，采用3層結構的模型示意圖，如圖2所示。

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

A對應傳染狀態，S對應易感狀態，W對應等待救治狀態，這3種狀態中涵蓋了所有節點。此外，被感染后的易感節點是轉變為傳染狀態的唯一路徑，變為傳染狀態后的節點才能轉變為等待救治狀態[5]。

3.2 模型分析

易感節點由病毒感染點與傳染節點感染后完成到傳染節點的轉變，被病毒感染后的傳染節點變為等待救治狀態，因傳染節點的一次數據轉發而導致等待救治節點數量增加，傳染節點狀態對傳染節點數量變化不構成影響，網絡節點狀態數量變化情況如圖3所示，圓圈對應具體的時刻，箭頭表示數量變化情況，(i，j)對應當前時刻的某一狀態，其中i和j分別表示傳染節點的數目和等待救治節點的數目，這兩個數目的變化情況分別由IA和IW表示，狀態(i，j)向(i+1，j)的轉變表示保持j不變的同時增加1個傳染節點數目，說明此時有一個易感節點被病毒感染點感染了，因此IA++；狀態(i，j)向(i，j+1)的轉變表示某一被病毒感染后的傳染節點變為等待救治的節點，因此IW++，在原感染點不感染其他節點時被感染的節點變為傳染節點不會改變i的總數。假設，系統模型中初始時共包含節點N個，其中的病毒感染點(同時作為感染節點)和易感節點分別為1個、S個，無等待救治的節點。N表示節點的總數目，β表示節點的接觸率，I表示感染節點數目總和，在t時刻，系統中易受感染的節點數目由S(t)表示、感染節點數目由I(t)表示、傳染節點數目由IA(t)表示、等待救治節點數目由IW(t)表示，β(N-1)表示單位時間內各節點接觸的節點數，S/(N-1)表示模型中未感染節點的占比。各類感染節點的數量變化，如圖3所示。

圖3 感染節點數目變化圖

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

圖4 節點數量變化的馬爾可夫鏈模型

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

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

3.3 模型驗證

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

模型曲線同理論結果基本吻合，能夠實現對受感染節點數變化的準確預測，說明該模型合理有效[7]。

圖5 受感染節點數變化擬合曲線

4 仿真實驗與結果分析

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

圖6 投遞率

EpidemicDisjointPath路由算法的投遞率僅次于最高的Epidemic路由算法，并且在7 500 S后增長緩慢，最早穩定在0．9左右；0-7 000 S時，相比于PageRank和Geosocial，PageRankEpidemicDisjointPath算法的投遞率更高，7 000 S后逐漸趨近于PageRank并小于Geosocial算法。總能量消耗仿真結果，如圖7所示。

圖7 總能量消耗

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

圖8 平均投遞延時

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

圖9 平均網絡開銷

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

5 總結

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