張霖 王蘭
摘要:移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中的數(shù)據(jù)傳輸具有隨機(jī)性特點(diǎn),但源節(jié)點(diǎn)和目的節(jié)點(diǎn)的最優(yōu)傳輸路徑選擇問(wèn)題一直是研究的熱點(diǎn),該文提出一種節(jié)點(diǎn)分簇路由算法,即Node Clustering Routing Algorithm (NCRA)算法,該算法通過(guò)節(jié)點(diǎn)隨機(jī)分簇找出簇頭,再通過(guò)各簇頭節(jié)點(diǎn)的數(shù)據(jù)選擇傳輸,完成數(shù)據(jù)包的轉(zhuǎn)發(fā),最終將數(shù)據(jù)從源節(jié)點(diǎn)傳輸?shù)侥康墓?jié)點(diǎn),并找出最優(yōu)信息傳遞路徑。通過(guò)仿真實(shí)驗(yàn),并與移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)的Epidemic算法和OSNN算法比較,NCRA算法優(yōu)化了網(wǎng)絡(luò)數(shù)據(jù)傳輸路徑,且具有傳輸效率高,能量消耗少,數(shù)據(jù)冗余少的特點(diǎn)。
關(guān)鍵詞:移動(dòng)機(jī)會(huì)網(wǎng)絡(luò);網(wǎng)絡(luò)節(jié)點(diǎn);分簇;數(shù)據(jù)傳輸
中圖分類(lèi)號(hào):TP393 文獻(xiàn)標(biāo)識(shí)碼:A
文章編號(hào):1009-3044(2020)21-0023-03
開(kāi)放科學(xué)(資源服務(wù))標(biāo)識(shí)碼(OSID):
1 引言
信息技術(shù)的高速發(fā)展給人們帶來(lái)了巨大的生活便利,移動(dòng)網(wǎng)絡(luò),無(wú)線網(wǎng)絡(luò)等的出現(xiàn)更是為人類(lèi)生產(chǎn)和生活縮小了物理距離,使人們即使相隔千里亦可以通過(guò)網(wǎng)絡(luò)連線,實(shí)時(shí)分享生活點(diǎn)滴。特別地,在無(wú)線網(wǎng)絡(luò)環(huán)境中,存在著多種類(lèi)型的網(wǎng)絡(luò),如無(wú)線傳感器網(wǎng)絡(luò),AdHoc網(wǎng)絡(luò),社交網(wǎng)絡(luò),移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)等。
移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)是一種延遲容忍類(lèi)自組織性網(wǎng)絡(luò)。其特點(diǎn)是源節(jié)點(diǎn)和目的節(jié)點(diǎn)間沒(méi)有預(yù)先規(guī)劃好的傳輸路徑,完全依靠途徑節(jié)點(diǎn)間的移動(dòng)相遇完成信息傳遞,節(jié)點(diǎn)的移動(dòng)規(guī)律是“攜帶一存儲(chǔ)一轉(zhuǎn)發(fā)”。移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)具有較多的應(yīng)用場(chǎng)景,如手持設(shè)備組網(wǎng),車(chē)載網(wǎng)絡(luò),野外數(shù)據(jù)收集等。
在移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)環(huán)境中,節(jié)點(diǎn)間的數(shù)據(jù)傳輸效率問(wèn)題一直是研究熱點(diǎn)。許多學(xué)者通過(guò)研究路由算法來(lái)不斷優(yōu)化節(jié)點(diǎn)傳輸過(guò)程,利用數(shù)學(xué)概率計(jì)算,或利用貪心算法,神經(jīng)網(wǎng)絡(luò)等技術(shù),結(jié)合移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)特點(diǎn),設(shè)計(jì)開(kāi)發(fā)了多種路由轉(zhuǎn)發(fā)算法,不斷改進(jìn)前人的方案,取得了一定進(jìn)步和成效,但在數(shù)據(jù)傳輸過(guò)程中,仍然存在網(wǎng)絡(luò)資源浪費(fèi),傳輸安全風(fēng)險(xiǎn)大,傳輸性能不夠等問(wèn)題。
本文研究了一種移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)分簇路由算法(Node Clustering Routing Algorithm(NCRA))算法,該算法先根據(jù)節(jié)點(diǎn)分布情況自由組合分簇,并在自由組成的簇中競(jìng)選出簇頭節(jié)點(diǎn),數(shù)據(jù)傳輸過(guò)程中,只需要考慮各簇頭節(jié)點(diǎn)的傳輸路徑,結(jié)合最短路徑算法將各簇頭節(jié)點(diǎn)間的邏輯距離進(jìn)行比較,得出當(dāng)前節(jié)點(diǎn)的最優(yōu)鄰居節(jié)點(diǎn),進(jìn)行下一跳選擇傳輸。該算法能有效減少數(shù)據(jù)傳輸過(guò)程中的數(shù)據(jù)冗余和,節(jié)約網(wǎng)絡(luò)資源,優(yōu)化數(shù)據(jù)傳輸過(guò)程。
2 相關(guān)工作
文獻(xiàn)[1]提出了Epidemic路由協(xié)議,該協(xié)議在節(jié)點(diǎn)移動(dòng)過(guò)程中,利用節(jié)點(diǎn)的相遇和移動(dòng)來(lái)完成數(shù)據(jù)交互。其核心思想是講當(dāng)前節(jié)點(diǎn)攜帶的數(shù)據(jù)通過(guò)復(fù)制副本的方式傳輸給相遇節(jié)點(diǎn)。因此每個(gè)傳輸節(jié)點(diǎn)都需要在緩存區(qū)中存儲(chǔ)傳遞數(shù)據(jù)。該協(xié)議的本質(zhì)是一種洪泛的路由協(xié)議。PROPHET路由協(xié)議[2]在Epi-demic協(xié)議基礎(chǔ)上做了技術(shù)改進(jìn),該方案中,消息傳遞給下一跳節(jié)點(diǎn)前,會(huì)通過(guò)簡(jiǎn)單的數(shù)學(xué)概率計(jì)算,預(yù)先估計(jì)一條數(shù)據(jù)傳輸路線[3],從而找出更合適的下一跳節(jié)點(diǎn),優(yōu)化傳輸路徑。文獻(xiàn)[4]利用了數(shù)學(xué)異或運(yùn)算的特點(diǎn),在數(shù)據(jù)傳輸過(guò)程中,通過(guò)節(jié)點(diǎn)信息的異或比較,找出最優(yōu)的下一跳,從而找出最優(yōu)的傳輸路徑,完成節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)。
基于復(fù)制的傳輸方案解決了移動(dòng)節(jié)點(diǎn)的數(shù)據(jù)快速傳輸問(wèn)題,但該方案同時(shí)也制造了大量數(shù)據(jù)冗余,浪費(fèi)了網(wǎng)絡(luò)資源,且傳輸性能不高。基于相遇預(yù)測(cè)型的路由協(xié)議通過(guò)對(duì)相遇概率的計(jì)算減少數(shù)據(jù)信息的洪泛傳遞,但根據(jù)歷史信息進(jìn)行概率估計(jì)可能與實(shí)際傳輸情況不符,影響數(shù)據(jù)傳輸?shù)臏?zhǔn)確性[5]。通過(guò)尋找最優(yōu)下一跳的方案較好地優(yōu)化了數(shù)據(jù)傳輸路徑,但卻忽略了各移動(dòng)節(jié)點(diǎn)的能力差異,較大的數(shù)據(jù)運(yùn)算為節(jié)點(diǎn)帶來(lái)了較大的負(fù)擔(dān)。各種路由協(xié)議各有所長(zhǎng),但也各自存在著相應(yīng)的弊端。
本文基于文獻(xiàn)[4],改進(jìn)了其傳輸方案,設(shè)計(jì)了移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)分簇路由算法,通過(guò)節(jié)點(diǎn)組合分簇方案,結(jié)合最小生成樹(shù)分析法,在獲取最優(yōu)下一跳節(jié)點(diǎn)的同時(shí),有效減輕弱節(jié)點(diǎn)[6]的傳輸負(fù)擔(dān),達(dá)到節(jié)約網(wǎng)絡(luò)資源,提升數(shù)據(jù)傳輸性能的目的。
3 節(jié)點(diǎn)分簇路由算法
3.1 移動(dòng)機(jī)會(huì)模型
移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)通過(guò)各個(gè)節(jié)點(diǎn)的移動(dòng)創(chuàng)造相遇機(jī)會(huì)實(shí)現(xiàn)節(jié)點(diǎn)之間的網(wǎng)絡(luò)通信,但只有在同一個(gè)連通區(qū)域內(nèi)的節(jié)點(diǎn)之間才可以完成通信[7-8]?,F(xiàn)假定在某一個(gè)時(shí)刻s,網(wǎng)絡(luò)由t個(gè)不同的連通區(qū)域組成,其中圖1表示s時(shí)刻隨機(jī)兩個(gè)連通區(qū)域的機(jī)會(huì)網(wǎng)絡(luò)結(jié)構(gòu)圖。
由圖1可得,A、B、C、D、E、F節(jié)點(diǎn)和G、H、I、J、K節(jié)點(diǎn)分別屬于連通區(qū)域1和連通區(qū)域2,由機(jī)會(huì)網(wǎng)絡(luò)的特性可知,連通區(qū)域1內(nèi)的所有節(jié)點(diǎn)可以互相傳遞數(shù)據(jù)信息,如A節(jié)點(diǎn)的數(shù)據(jù)信息可以傳遞給B、C、D、E、F,連通區(qū)域2中節(jié)點(diǎn)的數(shù)據(jù)信息也可以互相傳遞,試想若希望將A節(jié)點(diǎn)的數(shù)據(jù)傳遞到不屬于同一連通區(qū)域的H節(jié)點(diǎn),則要通過(guò)節(jié)點(diǎn)不斷移動(dòng)到同一連通區(qū)域才可實(shí)現(xiàn)。
3.2 節(jié)點(diǎn)分簇描述
經(jīng)過(guò)上文描述,現(xiàn)將圖1中的任一連通區(qū)域中的各個(gè)節(jié)點(diǎn)實(shí)現(xiàn)分簇處理,分簇方法為,根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的接收信號(hào)強(qiáng)度和節(jié)點(diǎn)連通度確定簇內(nèi)成員,即根據(jù)無(wú)線網(wǎng)絡(luò)中的節(jié)點(diǎn)物理位置相關(guān)性完成節(jié)點(diǎn)分組,定義α為評(píng)價(jià)尺度常量,表示節(jié)點(diǎn)間數(shù)據(jù)傳輸?shù)淖畲缶嚯x門(mén)限值,現(xiàn)將網(wǎng)絡(luò)環(huán)境中以評(píng)價(jià)尺度常量α劃分為若干子區(qū)域,在每個(gè)子區(qū)域中隨機(jī)選中一個(gè)節(jié)點(diǎn)t作為簇頭,若任意節(jié)點(diǎn)v滿(mǎn)足如下規(guī)則:
其中D(T,v)表示節(jié)點(diǎn)間通信鏈路函數(shù),即表示任意節(jié)點(diǎn)v到簇頭t的通信距離。
節(jié)點(diǎn)v加入當(dāng)前t為簇頭的簇T,分簇后的網(wǎng)絡(luò)形成由各個(gè)簇組成的新的網(wǎng)絡(luò)環(huán)境,在確定簇成員后,簇內(nèi)成員發(fā)送自身數(shù)據(jù)包給簇頭,簇頭接收到各成員的數(shù)據(jù)包后進(jìn)行數(shù)據(jù)融合處理,融合后的簇頭中包含了各個(gè)節(jié)點(diǎn)的數(shù)據(jù),同時(shí)消除了各節(jié)點(diǎn)中冗余的數(shù)據(jù)信息。
任意選擇一個(gè)t時(shí)刻的某個(gè)網(wǎng)絡(luò)環(huán)境M為研究切人點(diǎn),做出如下假設(shè),假設(shè)M中有n個(gè)節(jié)點(diǎn),將其根據(jù)物理位置相關(guān)性隨機(jī)生成6個(gè)連通區(qū)域,即同時(shí)形成6個(gè)簇,隨機(jī)指定各簇頭,簇頭將各自?xún)?nèi)部的節(jié)點(diǎn)信息數(shù)據(jù)融合處理,將分好的6個(gè)簇用集合表示為U={A,B,C,D,E,F(xiàn) 1,其中每個(gè)簇都能實(shí)現(xiàn)數(shù)據(jù)的轉(zhuǎn)發(fā);設(shè)當(dāng)前時(shí)刻A為起始節(jié)點(diǎn),且當(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é)點(diǎn)間的橫線表示各節(jié)點(diǎn)之間的邏輯傳輸距離。
3.3下一跳節(jié)點(diǎn)選取過(guò)程
每個(gè)簇節(jié)點(diǎn)中存放了各個(gè)簇中經(jīng)過(guò)數(shù)據(jù)融合處理的數(shù)據(jù)信息,假設(shè)在當(dāng)前時(shí)刻T,網(wǎng)絡(luò)環(huán)境M中存在如上圖2中的連通圖。從A出發(fā),尋找最優(yōu)傳輸路徑過(guò)程如下。
1)起始狀態(tài),只有A為當(dāng)前節(jié)點(diǎn),即U={A},V={B,C,D,E.F}。
2)從A節(jié)點(diǎn)出發(fā),比較V中的各代價(jià)邊,分別標(biāo)記各節(jié)點(diǎn)與初始節(jié)點(diǎn)A的邏輯距離,如D(A,3),B(A,6),E(A,5),C(A,∞),F(xiàn)(A,∞)。通過(guò)邏輯距離比較得到,當(dāng)前最小邊為D(A,3),即確定下一跳節(jié)點(diǎn)為D,此時(shí),U={A,D),V={B,C,E,F(xiàn))。
3)更新V中各個(gè)頂點(diǎn)與U的代價(jià)邊,即B(D,2),C(D,6),E(A,5),F(xiàn)(A,。。),通過(guò)邏輯距離比較得到當(dāng)前最小邊為B(D,2),即確定下一跳節(jié)點(diǎn)為B,此時(shí),U={A,D,B},V={C,E,F(xiàn))。
4)更新V中各個(gè)頂點(diǎn)與U的代價(jià)邊,即C(B,7),E(B,4),F(xiàn)(B,6),通過(guò)邏輯距離比較得到當(dāng)前最小邊為E(B,4),即確定下一跳節(jié)點(diǎn)為E,此時(shí),U={A,D,B,E},v={C,F(xiàn))。
5)更新V中各個(gè)頂點(diǎn)與U的代價(jià)邊,即C(B,7),F(xiàn)(E,1),通過(guò)邏輯距離比較得到當(dāng)前最小邊為F(E,1),即確定下一跳節(jié)點(diǎn)為F,此時(shí),U={A,D,B,E,F(xiàn)),V={C}。
6)更新V中各個(gè)頂點(diǎn)與U的代價(jià)邊,即C(F,4),確定下一跳節(jié)點(diǎn)為C,此時(shí),U={A,D,B,E,F(xiàn),C),到此,路徑規(guī)劃結(jié)束。
8)統(tǒng)計(jì)依次插入的節(jié)點(diǎn)為A、D、B、E、F、C。則A一>D一>B一>E一>F一>C為當(dāng)前最優(yōu)路徑。
3.4 算法設(shè)計(jì)
通過(guò)上一節(jié)內(nèi)容總結(jié)出NCRA算法執(zhí)行過(guò)程描述如下。
第一步:將當(dāng)前節(jié)點(diǎn)存入集合V,其初始值為通信信息的第一個(gè)節(jié)點(diǎn),該節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)m,把m并人集合U中,令U={ml。
第二步:采用節(jié)點(diǎn)邏輯路徑比較訪問(wèn)法標(biāo)記當(dāng)前環(huán)境下的各節(jié)點(diǎn)邏輯距離,找出最小邏輯距離節(jié)點(diǎn)i,并將i并入集合U,令U={m,ij,
第三步:更新節(jié)點(diǎn)距U中最新節(jié)點(diǎn)的邏輯距離,找到下一最小邏輯距離節(jié)點(diǎn)k,并將k并人集合U=(m,j,k),
第四步,重復(fù)第三步,直到U中存在所有節(jié)點(diǎn)為止。
第五步:輸出集合U中的所有節(jié)點(diǎn),該集合順序即為節(jié)點(diǎn)信息傳輸?shù)淖顑?yōu)路徑。
4 仿真與實(shí)驗(yàn)分析
為驗(yàn)證NCRA算法的性能,實(shí)驗(yàn)采用ONEl.4仿真平臺(tái)工具,通過(guò)與Epidemic算法和OSNN路由協(xié)議進(jìn)行比較,在保證節(jié)點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)傳輸范圍以及節(jié)點(diǎn)移動(dòng)速度一致的前提下分別采用三種算法進(jìn)行仿真實(shí)驗(yàn),在一定的時(shí)間內(nèi),觀察節(jié)點(diǎn)密度變化對(duì)傳輸成功率,傳輸延遲以及路由開(kāi)銷(xiāo)的影響程度,將三種結(jié)果進(jìn)行比對(duì),綜合分析得出實(shí)驗(yàn)結(jié)論。
圖3中節(jié)點(diǎn)密度直接影響數(shù)據(jù)的傳輸成功率,節(jié)點(diǎn)密度較小時(shí)三個(gè)算法的傳輸成功率幾乎都保持在10%-15%,但當(dāng)節(jié)點(diǎn)密度不斷增大時(shí),NCRA算法的傳輸成功率明顯優(yōu)于另外兩種算法,結(jié)合理論分析不難解釋該仿真結(jié)果,NCRA算法通過(guò)節(jié)點(diǎn)分簇后比較節(jié)點(diǎn)邏輯距離選取傳播距離最小的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳遞,因此取得較高的數(shù)據(jù)傳播成功率。
由圖4可以得出的結(jié)論是三種路由協(xié)議算法對(duì)數(shù)據(jù)傳輸延遲的影響都不是很大,其中Epidemic算法的延遲最小,NCRA算法較OSNN算法的傳輸延遲略小。出現(xiàn)這種情況的原因是Epidemic算法的特點(diǎn)為“遍地撒網(wǎng)”式,不對(duì)下一跳節(jié)點(diǎn)優(yōu)化處理就直接轉(zhuǎn)發(fā),因此傳輸延遲小,而NCRA算法和OSNN算法在傳輸過(guò)程中要通過(guò)不同的處理方式選擇下一跳路徑,而選擇過(guò)程就造成了傳輸延遲略高于Epidemic算法。另外,OSNN算法需要對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行計(jì)算比較,而NCRA算法只針對(duì)簇頭節(jié)點(diǎn)進(jìn)行比較計(jì)算,因此優(yōu)化了傳輸流程,同時(shí)降低了傳輸延遲。
圖5中,當(dāng)節(jié)點(diǎn)密度很小時(shí),三種算法的路由開(kāi)銷(xiāo)相差無(wú)幾,通過(guò)不斷增加節(jié)點(diǎn)密度,Epidemic算法的路由開(kāi)銷(xiāo)明顯增大,且一直處于高速上升狀態(tài),而OSNN和NCRA算法造成的路由開(kāi)銷(xiāo)明顯低于Epidemic算法,其原因是OSNN和CNDTR算法是擇優(yōu)選擇下一跳傳輸數(shù)據(jù),因此每一跳只選擇最優(yōu)節(jié)點(diǎn)傳輸,因此造成路由開(kāi)銷(xiāo)比較小,而Epidemic算法是洪泛式傳遞,因此節(jié)點(diǎn)密度越大,其路由開(kāi)銷(xiāo)就會(huì)越大。由圖看出,隨著節(jié)點(diǎn)密度不斷增大,NCRA算法造成的路由開(kāi)銷(xiāo)最小。
通過(guò)仿真實(shí)驗(yàn)以及結(jié)合理論知識(shí)的分析可得,NCRA算法能夠在傳輸數(shù)據(jù)的同等條件下降低路由開(kāi)銷(xiāo),并提高數(shù)據(jù)傳輸成功率。不可否認(rèn)的是,因下一跳選擇時(shí)需要計(jì)算選擇,造成了傳輸延遲,但就總體性能而言,相對(duì)其他經(jīng)典傳輸算法,NCRA算法具有一定優(yōu)勢(shì)。
5 結(jié)束語(yǔ)
本文提一種移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)分簇路由算法(NodeClustering Routing Algorithm (NCRA》算法,通過(guò)將節(jié)點(diǎn)融合成簇后采用簇頭節(jié)點(diǎn)通過(guò)節(jié)點(diǎn)間的邏輯距離比較,每次都選擇最短路徑來(lái)確定下一跳,最終獲得最優(yōu)傳輸路徑,實(shí)現(xiàn)高效網(wǎng)絡(luò)數(shù)據(jù)的傳輸,減少網(wǎng)絡(luò)資源的浪費(fèi),節(jié)省路由開(kāi)銷(xiāo)。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證,與Epidemic、OSNN算法進(jìn)行比較,CNDTR算法可以節(jié)省路由開(kāi)銷(xiāo)的同時(shí)減少網(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]任智,黃勇,陳前斌,等,機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)應(yīng)用研究,2010,30(3):723-72.
[4]張霖,陳志剛,吳嘉,等.最優(yōu)化選擇鄰居節(jié)點(diǎn)路由協(xié)議[J].小型微型計(jì)算機(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.
基金項(xiàng)目:重慶第二師范學(xué)院青年項(xiàng)目(KY201926C)
作者簡(jiǎn)介:張霖(1993-),女(土家族),湖南常德人,助教,碩士研究生,研究方向?yàn)闊o(wú)線網(wǎng)絡(luò)、網(wǎng)絡(luò)安全;王蘭(1991-),女,四川宜賓人,助教,碩士研究生,研究方向?yàn)樾畔踩?/p>