移動機會網(wǎng)絡(luò)中的節(jié)點分簇路由算法

張霖 王蘭

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

關(guān)鍵詞：移動機會網(wǎng)絡(luò);網(wǎng)絡(luò)節(jié)點;分簇;數(shù)據(jù)傳輸

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A

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

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

1 引言

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

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

在移動機會網(wǎng)絡(luò)環(huán)境中，節(jié)點間的數(shù)據(jù)傳輸效率問題一直是研究熱點。許多學(xué)者通過研究路由算法來不斷優(yōu)化節(jié)點傳輸過程，利用數(shù)學(xué)概率計算，或利用貪心算法，神經(jīng)網(wǎng)絡(luò)等技術(shù)，結(jié)合移動機會網(wǎng)絡(luò)特點，設(shè)計開發(fā)了多種路由轉(zhuǎn)發(fā)算法，不斷改進(jìn)前人的方案，取得了一定進(jìn)步和成效，但在數(shù)據(jù)傳輸過程中，仍然存在網(wǎng)絡(luò)資源浪費，傳輸安全風(fēng)險大，傳輸性能不夠等問題。

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

2 相關(guān)工作

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

基于復(fù)制的傳輸方案解決了移動節(jié)點的數(shù)據(jù)快速傳輸問題，但該方案同時也制造了大量數(shù)據(jù)冗余，浪費了網(wǎng)絡(luò)資源，且傳輸性能不高?；谙嘤鲱A(yù)測型的路由協(xié)議通過對相遇概率的計算減少數(shù)據(jù)信息的洪泛傳遞，但根據(jù)歷史信息進(jìn)行概率估計可能與實際傳輸情況不符，影響數(shù)據(jù)傳輸?shù)臏?zhǔn)確性[5]。通過尋找最優(yōu)下一跳的方案較好地優(yōu)化了數(shù)據(jù)傳輸路徑，但卻忽略了各移動節(jié)點的能力差異，較大的數(shù)據(jù)運算為節(jié)點帶來了較大的負(fù)擔(dān)。各種路由協(xié)議各有所長，但也各自存在著相應(yīng)的弊端。

本文基于文獻(xiàn)[4]，改進(jìn)了其傳輸方案，設(shè)計了移動機會網(wǎng)絡(luò)中的節(jié)點分簇路由算法，通過節(jié)點組合分簇方案，結(jié)合最小生成樹分析法，在獲取最優(yōu)下一跳節(jié)點的同時，有效減輕弱節(jié)點[6]的傳輸負(fù)擔(dān)，達(dá)到節(jié)約網(wǎng)絡(luò)資源，提升數(shù)據(jù)傳輸性能的目的。

3 節(jié)點分簇路由算法

3.1 移動機會模型

移動機會網(wǎng)絡(luò)通過各個節(jié)點的移動創(chuàng)造相遇機會實現(xiàn)節(jié)點之間的網(wǎng)絡(luò)通信，但只有在同一個連通區(qū)域內(nèi)的節(jié)點之間才可以完成通信[7-8]?，F(xiàn)假定在某一個時刻s，網(wǎng)絡(luò)由t個不同的連通區(qū)域組成，其中圖1表示s時刻隨機兩個連通區(qū)域的機會網(wǎng)絡(luò)結(jié)構(gòu)圖。

由圖1可得，A、B、C、D、E、F節(jié)點和G、H、I、J、K節(jié)點分別屬于連通區(qū)域1和連通區(qū)域2，由機會網(wǎng)絡(luò)的特性可知，連通區(qū)域1內(nèi)的所有節(jié)點可以互相傳遞數(shù)據(jù)信息，如A節(jié)點的數(shù)據(jù)信息可以傳遞給B、C、D、E、F，連通區(qū)域2中節(jié)點的數(shù)據(jù)信息也可以互相傳遞，試想若希望將A節(jié)點的數(shù)據(jù)傳遞到不屬于同一連通區(qū)域的H節(jié)點，則要通過節(jié)點不斷移動到同一連通區(qū)域才可實現(xiàn)。

3.2 節(jié)點分簇描述

經(jīng)過上文描述，現(xiàn)將圖1中的任一連通區(qū)域中的各個節(jié)點實現(xiàn)分簇處理，分簇方法為，根據(jù)網(wǎng)絡(luò)中節(jié)點的接收信號強度和節(jié)點連通度確定簇內(nèi)成員，即根據(jù)無線網(wǎng)絡(luò)中的節(jié)點物理位置相關(guān)性完成節(jié)點分組，定義α為評價尺度常量，表示節(jié)點間數(shù)據(jù)傳輸?shù)淖畲缶嚯x門限值，現(xiàn)將網(wǎng)絡(luò)環(huán)境中以評價尺度常量α劃分為若干子區(qū)域，在每個子區(qū)域中隨機選中一個節(jié)點t作為簇頭，若任意節(jié)點v滿足如下規(guī)則：

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

節(jié)點v加入當(dāng)前t為簇頭的簇T，分簇后的網(wǎng)絡(luò)形成由各個簇組成的新的網(wǎng)絡(luò)環(huán)境，在確定簇成員后，簇內(nèi)成員發(fā)送自身數(shù)據(jù)包給簇頭，簇頭接收到各成員的數(shù)據(jù)包后進(jìn)行數(shù)據(jù)融合處理，融合后的簇頭中包含了各個節(jié)點的數(shù)據(jù)，同時消除了各節(jié)點中冗余的數(shù)據(jù)信息。

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

3.3下一跳節(jié)點選取過程

每個簇節(jié)點中存放了各個簇中經(jīng)過數(shù)據(jù)融合處理的數(shù)據(jù)信息，假設(shè)在當(dāng)前時刻T，網(wǎng)絡(luò)環(huán)境M中存在如上圖2中的連通圖。從A出發(fā)，尋找最優(yōu)傳輸路徑過程如下。

1）起始狀態(tài)，只有A為當(dāng)前節(jié)點，即U={A}，V={B，C，D，E.F}。

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

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

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

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

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

8）統(tǒng)計依次插入的節(jié)點為A、D、B、E、F、C。則A一>D一>B一>E一>F一>C為當(dāng)前最優(yōu)路徑。

3.4 算法設(shè)計

通過上一節(jié)內(nèi)容總結(jié)出NCRA算法執(zhí)行過程描述如下。

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

第二步：采用節(jié)點邏輯路徑比較訪問法標(biāo)記當(dāng)前環(huán)境下的各節(jié)點邏輯距離，找出最小邏輯距離節(jié)點i，并將i并入集合U，令U={m，ij，

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

第四步，重復(fù)第三步，直到U中存在所有節(jié)點為止。

第五步：輸出集合U中的所有節(jié)點，該集合順序即為節(jié)點信息傳輸?shù)淖顑?yōu)路徑。

4 仿真與實驗分析

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

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

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

[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]任智，黃勇，陳前斌，等，機會網(wǎng)絡(luò)路由協(xié)議[J].計算機應(yīng)用研究，2010，30（3）：723-72.

[4]張霖，陳志剛，吳嘉，等.最優(yōu)化選擇鄰居節(jié)點路由協(xié)議[J].小型微型計算機系統(tǒng)，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.

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

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