移動機會網絡中的節點分簇路由算法

張霖 王蘭

摘要：移動機會網絡中的數據傳輸具有隨機性特點，但源節點和目的節點的最優傳輸路徑選擇問題一直是研究的熱點，該文提出一種節點分簇路由算法，即Node Clustering Routing Algorithm （NCRA）算法，該算法通過節點隨機分簇找出簇頭，再通過各簇頭節點的數據選擇傳輸，完成數據包的轉發，最終將數據從源節點傳輸到目的節點，并找出最優信息傳遞路徑。通過仿真實驗，并與移動機會網絡的Epidemic算法和OSNN算法比較，NCRA算法優化了網絡數據傳輸路徑，且具有傳輸效率高，能量消耗少，數據冗余少的特點。

關鍵詞：移動機會網絡;網絡節點;分簇;數據傳輸

中圖分類號：TP393 文獻標識碼：A

文章編號：1009-3044（2020）21-0023-03

開放科學（資源服務）標識碼（OSID）：

1 引言

信息技術的高速發展給人們帶來了巨大的生活便利，移動網絡，無線網絡等的出現更是為人類生產和生活縮小了物理距離，使人們即使相隔千里亦可以通過網絡連線，實時分享生活點滴。特別地，在無線網絡環境中，存在著多種類型的網絡，如無線傳感器網絡，AdHoc網絡，社交網絡，移動機會網絡等。

移動機會網絡是一種延遲容忍類自組織性網絡。其特點是源節點和目的節點間沒有預先規劃好的傳輸路徑，完全依靠途徑節點間的移動相遇完成信息傳遞，節點的移動規律是“攜帶一存儲一轉發”。移動機會網絡具有較多的應用場景，如手持設備組網，車載網絡，野外數據收集等。

在移動機會網絡環境中，節點間的數據傳輸效率問題一直是研究熱點。許多學者通過研究路由算法來不斷優化節點傳輸過程，利用數學概率計算，或利用貪心算法，神經網絡等技術，結合移動機會網絡特點，設計開發了多種路由轉發算法，不斷改進前人的方案，取得了一定進步和成效，但在數據傳輸過程中，仍然存在網絡資源浪費，傳輸安全風險大，傳輸性能不夠等問題。

本文研究了一種移動機會網絡中的節點分簇路由算法（Node Clustering Routing Algorithm（NCRA））算法，該算法先根據節點分布情況自由組合分簇，并在自由組成的簇中競選出簇頭節點，數據傳輸過程中，只需要考慮各簇頭節點的傳輸路徑，結合最短路徑算法將各簇頭節點間的邏輯距離進行比較，得出當前節點的最優鄰居節點，進行下一跳選擇傳輸。該算法能有效減少數據傳輸過程中的數據冗余和，節約網絡資源，優化數據傳輸過程。

2 相關工作

文獻[1]提出了Epidemic路由協議，該協議在節點移動過程中，利用節點的相遇和移動來完成數據交互。其核心思想是講當前節點攜帶的數據通過復制副本的方式傳輸給相遇節點。因此每個傳輸節點都需要在緩存區中存儲傳遞數據。該協議的本質是一種洪泛的路由協議。PROPHET路由協議[2]在Epi-demic協議基礎上做了技術改進，該方案中，消息傳遞給下一跳節點前，會通過簡單的數學概率計算，預先估計一條數據傳輸路線[3]，從而找出更合適的下一跳節點，優化傳輸路徑。文獻[4]利用了數學異或運算的特點，在數據傳輸過程中，通過節點信息的異或比較，找出最優的下一跳，從而找出最優的傳輸路徑，完成節點數據轉發。

基于復制的傳輸方案解決了移動節點的數據快速傳輸問題，但該方案同時也制造了大量數據冗余，浪費了網絡資源，且傳輸性能不高。基于相遇預測型的路由協議通過對相遇概率的計算減少數據信息的洪泛傳遞，但根據歷史信息進行概率估計可能與實際傳輸情況不符，影響數據傳輸的準確性[5]。通過尋找最優下一跳的方案較好地優化了數據傳輸路徑，但卻忽略了各移動節點的能力差異，較大的數據運算為節點帶來了較大的負擔。各種路由協議各有所長，但也各自存在著相應的弊端。

本文基于文獻[4]，改進了其傳輸方案，設計了移動機會網絡中的節點分簇路由算法，通過節點組合分簇方案，結合最小生成樹分析法，在獲取最優下一跳節點的同時，有效減輕弱節點[6]的傳輸負擔，達到節約網絡資源，提升數據傳輸性能的目的。

3 節點分簇路由算法

3.1 移動機會模型

移動機會網絡通過各個節點的移動創造相遇機會實現節點之間的網絡通信，但只有在同一個連通區域內的節點之間才可以完成通信[7-8]。現假定在某一個時刻s，網絡由t個不同的連通區域組成，其中圖1表示s時刻隨機兩個連通區域的機會網絡結構圖。

由圖1可得，A、B、C、D、E、F節點和G、H、I、J、K節點分別屬于連通區域1和連通區域2，由機會網絡的特性可知，連通區域1內的所有節點可以互相傳遞數據信息，如A節點的數據信息可以傳遞給B、C、D、E、F，連通區域2中節點的數據信息也可以互相傳遞，試想若希望將A節點的數據傳遞到不屬于同一連通區域的H節點，則要通過節點不斷移動到同一連通區域才可實現。

3.2 節點分簇描述

經過上文描述，現將圖1中的任一連通區域中的各個節點實現分簇處理，分簇方法為，根據網絡中節點的接收信號強度和節點連通度確定簇內成員，即根據無線網絡中的節點物理位置相關性完成節點分組，定義α為評價尺度常量，表示節點間數據傳輸的最大距離門限值，現將網絡環境中以評價尺度常量α劃分為若干子區域，在每個子區域中隨機選中一個節點t作為簇頭，若任意節點v滿足如下規則：

其中D（T，v）表示節點間通信鏈路函數，即表示任意節點v到簇頭t的通信距離。

節點v加入當前t為簇頭的簇T，分簇后的網絡形成由各個簇組成的新的網絡環境，在確定簇成員后，簇內成員發送自身數據包給簇頭，簇頭接收到各成員的數據包后進行數據融合處理，融合后的簇頭中包含了各個節點的數據，同時消除了各節點中冗余的數據信息。

任意選擇一個t時刻的某個網絡環境M為研究切人點，做出如下假設，假設M中有n個節點，將其根據物理位置相關性隨機生成6個連通區域，即同時形成6個簇，隨機指定各簇頭，簇頭將各自內部的節點信息數據融合處理，將分好的6個簇用集合表示為U={A，B，C，D，E，F 1，其中每個簇都能實現數據的轉發;設當前時刻A為起始節點，且當前網絡拓撲結構保持不變，構建如下網絡連通圖，如圖2所示。根據圖2得到連通圖G=（U，v）其中，初始狀態U={A}，V={B，C，D，E，F} ，圖2中各節點間的橫線表示各節點之間的邏輯傳輸距離。

3.3下一跳節點選取過程

每個簇節點中存放了各個簇中經過數據融合處理的數據信息，假設在當前時刻T，網絡環境M中存在如上圖2中的連通圖。從A出發，尋找最優傳輸路徑過程如下。

1）起始狀態，只有A為當前節點，即U={A}，V={B，C，D，E.F}。

2）從A節點出發，比較V中的各代價邊，分別標記各節點與初始節點A的邏輯距離，如D（A，3），B（A，6），E（A，5），C（A，∞），F（A，∞）。通過邏輯距離比較得到，當前最小邊為D（A，3），即確定下一跳節點為D，此時，U={A，D），V={B，C，E，F）。

3）更新V中各個頂點與U的代價邊，即B（D，2），C（D，6），E（A，5），F（A，。。），通過邏輯距離比較得到當前最小邊為B（D，2），即確定下一跳節點為B，此時，U={A，D，B}，V={C，E，F）。

4）更新V中各個頂點與U的代價邊，即C（B，7），E（B，4），F（B，6），通過邏輯距離比較得到當前最小邊為E（B，4），即確定下一跳節點為E，此時，U={A，D，B，E}，v={C，F）。

5）更新V中各個頂點與U的代價邊，即C（B，7），F（E，1），通過邏輯距離比較得到當前最小邊為F（E，1），即確定下一跳節點為F，此時，U={A，D，B，E，F），V={C}。

6）更新V中各個頂點與U的代價邊，即C（F，4），確定下一跳節點為C，此時，U={A，D，B，E，F，C），到此，路徑規劃結束。

8）統計依次插入的節點為A、D、B、E、F、C。則A一>D一>B一>E一>F一>C為當前最優路徑。

3.4 算法設計

通過上一節內容總結出NCRA算法執行過程描述如下。

第一步：將當前節點存入集合V，其初始值為通信信息的第一個節點，該節點為當前節點m，把m并人集合U中，令U={ml。

第二步：采用節點邏輯路徑比較訪問法標記當前環境下的各節點邏輯距離，找出最小邏輯距離節點i，并將i并入集合U，令U={m，ij，

第三步：更新節點距U中最新節點的邏輯距離，找到下一最小邏輯距離節點k，并將k并人集合U=（m，j，k），

第四步，重復第三步，直到U中存在所有節點為止。

第五步：輸出集合U中的所有節點，該集合順序即為節點信息傳輸的最優路徑。

4 仿真與實驗分析

為驗證NCRA算法的性能，實驗采用ONEl.4仿真平臺工具，通過與Epidemic算法和OSNN路由協議進行比較，在保證節點個數、節點傳輸范圍以及節點移動速度一致的前提下分別采用三種算法進行仿真實驗，在一定的時間內，觀察節點密度變化對傳輸成功率，傳輸延遲以及路由開銷的影響程度，將三種結果進行比對，綜合分析得出實驗結論。

圖3中節點密度直接影響數據的傳輸成功率，節點密度較小時三個算法的傳輸成功率幾乎都保持在10%-15%，但當節點密度不斷增大時，NCRA算法的傳輸成功率明顯優于另外兩種算法，結合理論分析不難解釋該仿真結果，NCRA算法通過節點分簇后比較節點邏輯距離選取傳播距離最小的節點進行數據傳遞，因此取得較高的數據傳播成功率。

由圖4可以得出的結論是三種路由協議算法對數據傳輸延遲的影響都不是很大，其中Epidemic算法的延遲最小，NCRA算法較OSNN算法的傳輸延遲略小。出現這種情況的原因是Epidemic算法的特點為“遍地撒網”式，不對下一跳節點優化處理就直接轉發，因此傳輸延遲小，而NCRA算法和OSNN算法在傳輸過程中要通過不同的處理方式選擇下一跳路徑，而選擇過程就造成了傳輸延遲略高于Epidemic算法。另外，OSNN算法需要對每個節點進行計算比較，而NCRA算法只針對簇頭節點進行比較計算，因此優化了傳輸流程，同時降低了傳輸延遲。

圖5中，當節點密度很小時，三種算法的路由開銷相差無幾，通過不斷增加節點密度，Epidemic算法的路由開銷明顯增大，且一直處于高速上升狀態，而OSNN和NCRA算法造成的路由開銷明顯低于Epidemic算法，其原因是OSNN和CNDTR算法是擇優選擇下一跳傳輸數據，因此每一跳只選擇最優節點傳輸，因此造成路由開銷比較小，而Epidemic算法是洪泛式傳遞，因此節點密度越大，其路由開銷就會越大。由圖看出，隨著節點密度不斷增大，NCRA算法造成的路由開銷最小。

通過仿真實驗以及結合理論知識的分析可得，NCRA算法能夠在傳輸數據的同等條件下降低路由開銷，并提高數據傳輸成功率。不可否認的是，因下一跳選擇時需要計算選擇，造成了傳輸延遲，但就總體性能而言，相對其他經典傳輸算法，NCRA算法具有一定優勢。

5 結束語

本文提一種移動機會網絡中的節點分簇路由算法（NodeClustering Routing Algorithm （NCRA》算法，通過將節點融合成簇后采用簇頭節點通過節點間的邏輯距離比較，每次都選擇最短路徑來確定下一跳，最終獲得最優傳輸路徑，實現高效網絡數據的傳輸，減少網絡資源的浪費，節省路由開銷。通過仿真實驗驗證，與Epidemic、OSNN算法進行比較，CNDTR算法可以節省路由開銷的同時減少網絡數據冗余。

參考文獻：

[1] Vahdat A，Becker D.Epidemic Routing for Partially ConnectedAd Hoc Networks[J]，Master Thesis. 2000.

[2] Lindgren A， Doria A， Davies E，Grasic S.Probabilistic routingprotocol for intermittently connected networks[J]，lnternet Engi-neering Task Force （IETF）， 2007.

[3]任智，黃勇，陳前斌，等，機會網絡路由協議[J].計算機應用研究，2010，30（3）：723-72.

[4]張霖，陳志剛，吳嘉，等.最優化選擇鄰居節點路由協議[J].小型微型計算機系統，2017（1）.

[5] Luo J ， Yu F R ， Chen Q ， et al. Adaptive Video StreamingWith Edge Caching and Video Transcoding Over Software-De-fined Mobile Networks： A Deep Reinforcement Learning Ap-proach[J]. IEEE Transactions on Wireless Communications，2020， 19（3）：1577-1592.

[6] Wen R ， Feng C ， Tang J ， et al. On Robustness of WetworkSlicing for Next-Generation Mobile Networks[J]. IEEE Trans-actions on Communications， 2019， 67（1）：430-444.

[7] Chhabra， Anshuman， Vashishth， et al. A fuzzy logic and gametheory based adaptive approach for securing opportunistic net-works against black hole attacks[J]. International Journal ofCommunication Systems， 2018.

[8] Fu X ， Yao H ， Postolache 0 ， et al. Message forwarding forWSN-Assisted Opportunistic Network in disaster scenarios[J].Journal of Network and Computer Applications， 2019， 137：11- 24.

基金項目：重慶第二師范學院青年項目（KY201926C）

作者簡介：張霖（1993-），女（土家族），湖南常德人，助教，碩士研究生，研究方向為無線網絡、網絡安全;王蘭（1991-），女，四川宜賓人，助教，碩士研究生，研究方向為信息安全。