胡 敏，王言通，黃春妮

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

目前國(guó)內(nèi)外研究機(jī)構(gòu)在延遲容忍網(wǎng)絡(luò)(delay tolerant network，DTN)路由機(jī)制方面的研究中，研究熱點(diǎn)是利用節(jié)點(diǎn)關(guān)系(如社會(huì)關(guān)系、相遇概率)確定消息轉(zhuǎn)發(fā)節(jié)點(diǎn)[1,2]，完成消息傳輸過程。Pan等[3]提出的Bubble Rap路由，依據(jù)節(jié)點(diǎn)的移動(dòng)信息對(duì)節(jié)點(diǎn)劃分社區(qū)，同時(shí)利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性計(jì)算節(jié)點(diǎn)活躍度并排序，根據(jù)節(jié)點(diǎn)排名選擇轉(zhuǎn)發(fā)消息節(jié)點(diǎn)；Abdelkader等[4]利用社會(huì)網(wǎng)絡(luò)中“小世界”特性制定路由策略，依據(jù)節(jié)點(diǎn)相似性和中心性確定轉(zhuǎn)發(fā)節(jié)點(diǎn)；吳大鵬等[5]提出根據(jù)節(jié)點(diǎn)社會(huì)屬性感知的數(shù)據(jù)轉(zhuǎn)發(fā)策略，利用節(jié)點(diǎn)連接持續(xù)時(shí)間評(píng)估節(jié)點(diǎn)關(guān)系。此外，研究人員發(fā)現(xiàn)利用節(jié)點(diǎn)的歷史信息可以對(duì)節(jié)點(diǎn)的運(yùn)動(dòng)進(jìn)行預(yù)測(cè)。王恩等[6]利用節(jié)點(diǎn)歷史信息預(yù)測(cè)節(jié)點(diǎn)相遇概率并根據(jù)預(yù)測(cè)值確定轉(zhuǎn)發(fā)節(jié)點(diǎn)；Peng等[7]提出的基于投遞概率預(yù)測(cè)的高效路由(delivery probability prediction based on efficient routing，DPER)，根據(jù)節(jié)點(diǎn)投遞概率預(yù)測(cè)值選擇節(jié)點(diǎn)并根據(jù)預(yù)測(cè)值分配消息副本。在上述研究的節(jié)點(diǎn)關(guān)系評(píng)估中，忽略了節(jié)點(diǎn)間關(guān)系強(qiáng)度受其連接節(jié)點(diǎn)的影響，使所得結(jié)果與節(jié)點(diǎn)在網(wǎng)絡(luò)中的實(shí)際關(guān)系強(qiáng)度不相吻合，從而錯(cuò)誤評(píng)估了節(jié)點(diǎn)轉(zhuǎn)發(fā)能力，降低網(wǎng)絡(luò)傳輸性能。

針對(duì)上述問題，本文提出節(jié)點(diǎn)關(guān)系強(qiáng)度感知的延遲容忍網(wǎng)絡(luò)路由機(jī)制(node relationship magnanimity aesthesis routing，NMAR)，該機(jī)制利用相遇節(jié)點(diǎn)信息衡量節(jié)點(diǎn)關(guān)系強(qiáng)度變化，并依據(jù)節(jié)點(diǎn)連接狀態(tài)信息估計(jì)節(jié)點(diǎn)相遇概率，并結(jié)合節(jié)點(diǎn)關(guān)系預(yù)測(cè)節(jié)點(diǎn)轉(zhuǎn)發(fā)能力，根據(jù)節(jié)點(diǎn)關(guān)系強(qiáng)度和轉(zhuǎn)發(fā)能力值選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，提高消息轉(zhuǎn)發(fā)效率，提高網(wǎng)絡(luò)性能。

1 節(jié)點(diǎn)關(guān)系強(qiáng)度感知

節(jié)點(diǎn)關(guān)系通?？紤]節(jié)點(diǎn)間的相遇時(shí)間或相遇頻率[8]，節(jié)點(diǎn)關(guān)系強(qiáng)度能夠反映節(jié)點(diǎn)間連接的緊密情況。但節(jié)點(diǎn)關(guān)系強(qiáng)度并不能僅考慮兩節(jié)點(diǎn)的連接情況，其它節(jié)點(diǎn)也會(huì)對(duì)兩節(jié)點(diǎn)關(guān)系產(chǎn)生影響。

1.1 節(jié)點(diǎn)關(guān)系

網(wǎng)絡(luò)中的節(jié)點(diǎn)選擇任意方向移動(dòng)，并依靠與其它節(jié)點(diǎn)相遇建立的連接轉(zhuǎn)發(fā)消息。節(jié)點(diǎn)運(yùn)動(dòng)場(chǎng)景如圖1所示。

節(jié)點(diǎn)運(yùn)動(dòng)使節(jié)點(diǎn)間關(guān)系產(chǎn)生變化，由此節(jié)點(diǎn)間關(guān)系變化取決于節(jié)點(diǎn)運(yùn)動(dòng)情況。移動(dòng)過程中相遇節(jié)點(diǎn)信息反映節(jié)點(diǎn)運(yùn)動(dòng)情況，利用相遇節(jié)點(diǎn)數(shù)量的變化分析節(jié)點(diǎn)運(yùn)動(dòng)情況，評(píng)估節(jié)點(diǎn)間關(guān)系的變化。

圖1 節(jié)點(diǎn)運(yùn)動(dòng)場(chǎng)景

相遇節(jié)點(diǎn)信息是記錄存儲(chǔ)該節(jié)點(diǎn)移動(dòng)過程中相遇節(jié)點(diǎn)的信息，包括節(jié)點(diǎn)ID、相遇次數(shù)、開始時(shí)間、結(jié)束時(shí)間等。本文利用相遇節(jié)點(diǎn)的數(shù)量衡量節(jié)點(diǎn)關(guān)系強(qiáng)度，利用兩節(jié)點(diǎn)共同相遇節(jié)點(diǎn)(共遇節(jié)點(diǎn))的數(shù)量變化描述節(jié)點(diǎn)關(guān)系強(qiáng)度變化，即共遇節(jié)點(diǎn)數(shù)目增加，則節(jié)點(diǎn)關(guān)系強(qiáng)度增加；反之，節(jié)點(diǎn)關(guān)系強(qiáng)度減弱。節(jié)點(diǎn)關(guān)系強(qiáng)度變化如圖2所示。兩節(jié)點(diǎn)間關(guān)系越強(qiáng)，節(jié)點(diǎn)間轉(zhuǎn)發(fā)消息的能力越強(qiáng)，消息的傳輸效率越高。

圖2 網(wǎng)絡(luò)中節(jié)點(diǎn)關(guān)系變化

1.2 節(jié)點(diǎn)關(guān)系強(qiáng)度感知

網(wǎng)絡(luò)G由n個(gè)節(jié)點(diǎn)構(gòu)成，N為節(jié)點(diǎn)集合。節(jié)點(diǎn)a與節(jié)點(diǎn)b為網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)a的相遇節(jié)點(diǎn)集合記為表示為M(a)={ni|ni∈N},ni為網(wǎng)絡(luò)中節(jié)點(diǎn)。節(jié)點(diǎn)a和節(jié)點(diǎn)b的共遇節(jié)點(diǎn)集合記為

CM(a,b)={ni|ni∈M(a),ni∈M(b),ni∈N}

(1)

定義1 共遇節(jié)點(diǎn)變化度

共遇節(jié)點(diǎn)變化度指節(jié)點(diǎn)a與節(jié)點(diǎn)b的相鄰兩個(gè)時(shí)間周期內(nèi)共遇節(jié)點(diǎn)數(shù)目的變化值與非共遇節(jié)點(diǎn)數(shù)目的比值，記為

(2)

式中：CM(a,b)i表示節(jié)點(diǎn)a與節(jié)點(diǎn)b在第i個(gè)周期內(nèi)的共遇節(jié)點(diǎn)集，CM(a,b)i-1表示節(jié)點(diǎn)a與節(jié)點(diǎn)b在第i-1個(gè)周期內(nèi)的共遇節(jié)點(diǎn)集。

共遇節(jié)點(diǎn)變化度反映節(jié)點(diǎn)關(guān)系強(qiáng)度變化，當(dāng)共遇節(jié)點(diǎn)變化度大于零，共遇節(jié)點(diǎn)數(shù)目增多，節(jié)點(diǎn)關(guān)系強(qiáng)度增加；反之，節(jié)點(diǎn)關(guān)系強(qiáng)度減弱。同時(shí)共遇節(jié)點(diǎn)變化度的絕對(duì)值表征節(jié)點(diǎn)間關(guān)系強(qiáng)度的變化程度，絕對(duì)值越大，節(jié)點(diǎn)關(guān)系強(qiáng)度變化越劇烈。

定義2 節(jié)點(diǎn)連接度

節(jié)點(diǎn)連接度是指節(jié)點(diǎn)a與節(jié)點(diǎn)b的共遇節(jié)點(diǎn)數(shù)目與兩節(jié)點(diǎn)所有相遇節(jié)點(diǎn)數(shù)目的比值，記

(3)

式中：CM(a,b)i表示節(jié)點(diǎn)a與節(jié)點(diǎn)b在第i個(gè)周期內(nèi)的共遇節(jié)點(diǎn)集，M(a)i,M(b)i表示為節(jié)點(diǎn)a與節(jié)點(diǎn)b在第i個(gè)周期內(nèi)的相遇節(jié)點(diǎn)集。

節(jié)點(diǎn)連接度表征節(jié)點(diǎn)間關(guān)系強(qiáng)度，連接度越大，節(jié)點(diǎn)間關(guān)系強(qiáng)度越高。

定義3 相遇節(jié)點(diǎn)變化度

相遇節(jié)點(diǎn)變化度是指節(jié)點(diǎn)a在兩個(gè)相鄰的時(shí)間周期內(nèi)相遇節(jié)點(diǎn)數(shù)目變化值與相遇節(jié)點(diǎn)數(shù)目的比值，記為

(4)

式中：M(a)i為節(jié)點(diǎn)a在第i個(gè)時(shí)間周期內(nèi)的相遇節(jié)點(diǎn)集合，M(a)i-1為節(jié)點(diǎn)a在第i-1個(gè)時(shí)間周期內(nèi)的相遇節(jié)點(diǎn)集合。

相遇節(jié)點(diǎn)變化度反映節(jié)點(diǎn)因移動(dòng)造成相遇節(jié)點(diǎn)的變化程度，體現(xiàn)節(jié)點(diǎn)移動(dòng)能力大小，變化度值越大，移動(dòng)能力越強(qiáng)。

節(jié)點(diǎn)a，d的關(guān)系強(qiáng)度函數(shù)記為

Re(a,d)=μCon(a,d)+εDis(a,d)+Var(a)

(5)

式中：μ、ε和為權(quán)重因子，μ+ε+=1，μ=0.5，ε=0.3，=0.2。

1.3 節(jié)點(diǎn)的轉(zhuǎn)發(fā)能力

節(jié)點(diǎn)關(guān)系強(qiáng)度反映節(jié)點(diǎn)間連接路徑的數(shù)量。消息轉(zhuǎn)發(fā)效率不僅與路徑數(shù)目多少相關(guān)，還與各個(gè)路徑的節(jié)點(diǎn)轉(zhuǎn)發(fā)能力有關(guān)。節(jié)點(diǎn)轉(zhuǎn)發(fā)能力包括相遇轉(zhuǎn)發(fā)能力和鄰接轉(zhuǎn)發(fā)能力，相遇轉(zhuǎn)發(fā)能力是指與目的節(jié)點(diǎn)相遇完成消息轉(zhuǎn)發(fā)的能力，鄰接轉(zhuǎn)發(fā)能力是指由非目的節(jié)點(diǎn)完成消息轉(zhuǎn)發(fā)的能力。轉(zhuǎn)發(fā)能力用相遇概率描述，而相遇概率由節(jié)點(diǎn)間連接狀態(tài)預(yù)測(cè)得到。

網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的連接狀態(tài)由連通和斷開交替變化，并且兩節(jié)點(diǎn)a、b在將來tk+1時(shí)刻的狀態(tài)(連通/斷開)只與當(dāng)前時(shí)刻tk的狀態(tài)有關(guān)而與過去其它時(shí)刻無關(guān)，如圖3所示。因此，節(jié)點(diǎn)連接狀態(tài)的變化過程可視作連續(xù)時(shí)間的馬爾可夫鏈。

圖3 節(jié)點(diǎn)連接狀態(tài)變化過程

圖3中λ、μ分別表示節(jié)點(diǎn)間的連接狀態(tài)由斷開轉(zhuǎn)變?yōu)檫B通、由連通轉(zhuǎn)變?yōu)閿嚅_的概率，設(shè)連接的持續(xù)時(shí)間與連接的間隔時(shí)間分別用ct、ict來表示，則λ=∑ct/∑t,μ=∑ict/∑t。

該馬爾可夫鏈?zhǔn)且粋€(gè)齊次馬爾可夫過程，其狀態(tài)轉(zhuǎn)移概率為

(6)

即狀態(tài)轉(zhuǎn)移矩陣為

(7)

節(jié)點(diǎn)a、b間連接狀態(tài)由斷開到斷開的轉(zhuǎn)移速率為

(8)

同理，連接狀態(tài)由連通到連通的轉(zhuǎn)移速率為

(9)

即上述演化過程的Q矩陣為

(10)

由柯爾莫哥洛夫向前方程可以得到

(11)

根據(jù)求解方程得到，節(jié)點(diǎn)a、b間連接狀態(tài)由斷開到連接的概率為

(12)

則節(jié)點(diǎn)a、b相遇概率值為

(13)

式中：ict′為平均間隔時(shí)間，td為當(dāng)前時(shí)刻距上一次相遇的間隔時(shí)間。

節(jié)點(diǎn)a、b間轉(zhuǎn)發(fā)能力函數(shù)記為for(a,b)

(14)

2 NMAR路由機(jī)制

為提高消息的傳輸效率，降低網(wǎng)絡(luò)開銷，本文提出了一個(gè)感知節(jié)點(diǎn)間關(guān)系強(qiáng)度的路由機(jī)制NMAR。該路由機(jī)制消息傳輸流程如圖4所示，描述如下：

(1)當(dāng)兩節(jié)點(diǎn)進(jìn)入彼此通信半徑內(nèi)(相遇)，比較相遇節(jié)點(diǎn)是否為消息目的節(jié)點(diǎn)。若是則直接將消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)，同時(shí)刪除該消息副本；

(2)若相遇節(jié)點(diǎn)不是消息的目的節(jié)點(diǎn)且攜帶消息的副本，則不轉(zhuǎn)發(fā)消息；

(3)若相遇節(jié)點(diǎn)不是消息的目的節(jié)點(diǎn)且沒有攜帶消息的副本，計(jì)算節(jié)點(diǎn)關(guān)系強(qiáng)度函數(shù)，并且與當(dāng)前節(jié)點(diǎn)的函數(shù)值進(jìn)行比較，當(dāng)相遇節(jié)點(diǎn)關(guān)系強(qiáng)度值大于當(dāng)前節(jié)點(diǎn)時(shí)，進(jìn)入步驟(4)，否則不轉(zhuǎn)發(fā)消息。

(4)計(jì)算節(jié)點(diǎn)轉(zhuǎn)發(fā)能力值，并與當(dāng)前節(jié)點(diǎn)能力值進(jìn)行比較，當(dāng)相遇節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)時(shí)，將消息轉(zhuǎn)發(fā)給中繼節(jié)點(diǎn)，否則不轉(zhuǎn)發(fā)消息。

圖4 算法實(shí)現(xiàn)流程

3 仿真與分析

本文采用機(jī)會(huì)網(wǎng)絡(luò)環(huán)境模擬器ONE(opportunistic network environment)[9]對(duì)消息投遞率、開銷比、平均傳輸時(shí)延等網(wǎng)絡(luò)性能指標(biāo)進(jìn)行仿真分析。

3.1 仿真結(jié)果與分析

NMAR路由算法選擇運(yùn)動(dòng)能力和投遞能力更強(qiáng)的節(jié)點(diǎn)來轉(zhuǎn)發(fā)消息，算法偽代碼見表1。

仿真中引入考慮節(jié)點(diǎn)投遞能力的Prophet路由算法[10]，控制網(wǎng)絡(luò)開銷的SprayandWait路由算法[11](SnW)和考慮節(jié)點(diǎn)運(yùn)動(dòng)的DPER進(jìn)行仿真驗(yàn)證。仿真參數(shù)設(shè)置見表2。

3.2 網(wǎng)絡(luò)性能與節(jié)點(diǎn)緩存大小

設(shè)置網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)目為120，節(jié)點(diǎn)緩存空間變化范圍為5 M至50 M，變化間隔為5 M。仿真結(jié)果如圖5～圖7所示。

由圖5可以看出網(wǎng)絡(luò)中消息投遞率隨節(jié)點(diǎn)緩存的增加而提高，在達(dá)到最佳效果后趨于平穩(wěn)，然后消息投遞率不再受緩存增加的影響。相比于Prophet、SprayandWait和DPER路由算法，NMAR的消息投遞率分別提升了9.55%、5.72%和3.21%。圖6為路由算法的平均傳輸時(shí)延與節(jié)點(diǎn)緩存關(guān)系的對(duì)比圖，平均傳輸時(shí)延隨著節(jié)點(diǎn)緩存的增加呈現(xiàn)出先下降后上升的趨勢(shì)直至趨于平穩(wěn)狀態(tài)，NMAR路由算法的平均傳輸時(shí)延低于Prophet、SprayandWait和DPER路由算法。圖7描述了網(wǎng)絡(luò)的開銷比隨節(jié)點(diǎn)緩存增加的變化趨勢(shì)。從整體看，4種路由算法的開銷比隨著節(jié)點(diǎn)緩存的增加而減小，逐步趨于平穩(wěn)，NMAR路由算法的開銷比整體較小，優(yōu)于其它3種路由算法。

表1 NMAR路由算法實(shí)現(xiàn)代碼

表2 仿真參數(shù)設(shè)置

圖5 投遞率隨節(jié)點(diǎn)緩存大小的變化

圖6 平均時(shí)延隨節(jié)點(diǎn)緩存大小的變化

圖7 開銷比隨節(jié)點(diǎn)緩存大小的變化

3.3 網(wǎng)絡(luò)性能與節(jié)點(diǎn)數(shù)目

結(jié)合上一小節(jié)的仿真實(shí)驗(yàn)結(jié)果，將節(jié)點(diǎn)緩存空間大小設(shè)置為38 M，其它仿真參數(shù)保持不變，節(jié)點(diǎn)數(shù)目變化范圍為40到200，增幅間隔為40。仿真結(jié)果如圖8～圖10所示。

圖8 消息投遞率隨節(jié)點(diǎn)數(shù)量的變化

圖9 平均時(shí)延隨節(jié)點(diǎn)數(shù)量的變化

圖10 開銷比隨節(jié)點(diǎn)數(shù)量的變化

從圖8可以看出消息投遞率隨節(jié)點(diǎn)數(shù)目增加而增加，相比于Prophet、SprayandWait和DPER路由算法，NMAR的消息投遞率優(yōu)于其它3種路由算法，分別提升了15.47%、12.02%和5.68%。由圖9可以看出隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目的增加，消息平均傳輸時(shí)延不斷減小后趨于平穩(wěn)，NMAR的平均傳輸時(shí)延低于Prophet、SprayandWait和DPER路由算法。圖10描述了網(wǎng)絡(luò)開銷比隨節(jié)點(diǎn)數(shù)目增加的變化趨勢(shì)。從整體看，4種路由算法的開銷比均隨著節(jié)點(diǎn)數(shù)目的增加表現(xiàn)出上升趨勢(shì)。從局部看，NMAR路由算法的開銷比整體較小，優(yōu)于其它3種路由算法。

4 結(jié)束語

本文研究了延遲網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)系強(qiáng)度，通過節(jié)點(diǎn)連通狀態(tài)的分析給出了節(jié)點(diǎn)強(qiáng)度關(guān)系的感知和度量方法，進(jìn)一步給出了基于節(jié)點(diǎn)關(guān)系強(qiáng)度感知的延遲容忍網(wǎng)絡(luò)路由機(jī)制，該機(jī)制利用運(yùn)動(dòng)過程中相遇節(jié)點(diǎn)數(shù)量的增減描述節(jié)點(diǎn)間關(guān)系強(qiáng)度的變化，同時(shí)依據(jù)節(jié)點(diǎn)之間的連接狀態(tài)預(yù)測(cè)節(jié)點(diǎn)相遇概率，并結(jié)合節(jié)點(diǎn)關(guān)系評(píng)估節(jié)點(diǎn)的轉(zhuǎn)發(fā)能力，根據(jù)節(jié)點(diǎn)關(guān)系強(qiáng)度和轉(zhuǎn)發(fā)能力值選擇合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)，優(yōu)化消息的傳輸，提升消息的轉(zhuǎn)發(fā)效率。仿真實(shí)驗(yàn)驗(yàn)證了該路由機(jī)制具有很高的擴(kuò)展性，提高了消息傳輸效率，改善了網(wǎng)絡(luò)性能，提升了資源的利用率。

[1]Khabbaz M J,Assi C M,Fawaz W F.Disruption-tolerant networking:A comprehensive survey on recent developments and persisting challenges[J].Communications Surveys & Tuto-rials,IEEE,2012,14(2):607-640.

[2]Cao Yue,Sun Zhili.Routing in delay/disruption tolerant networks:A taxonomy,survey and challenges[J].IEEE Communications Surveys & Tutorials,2013,15(2):654-677.

[3]Wei Kaimin,Liang Xiao,Xu Ke.A survey of social-aware routing protocols in delay tolerant networks:Applications,taxonomy and design-related issues[J].IEEE Communications Surveys & Tutorials,2014,16(1):556-578.

[4]Abdelkader T,Naik K,Nayak A,et al.SGBR:A routing protocol for delay tolerant networks using social grouping[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(12):2472-2481.

[5]WU Dapeng,KONG Xiaolong,ZHANG Hongpei,et al.Social attributes aware data forwarding strategy in intermittently connected wireless networks[J].Journal on Communications,2015,36(1):42-51(in Chinese).[吳大鵬,孔曉龍,張洪沛,等.社會(huì)屬性感知的間斷連接無線網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)策略[J].通信學(xué)報(bào),2015,36(1):42-51.]

[6]Wang En,Yang Yongjian,Li li.A clustering routing method based on semi-Markov process and path-finding strategy in DTN[J].Chinese Journal of Computers,2015,38(3):483-499.

[7]Wang E,Yang Y,Chen X,et al.The improved algorithm of spray and wait routing protocol in delay tolerant network[J].International Journal of Advancements in Computing Technology,2013,5(7):238-245.

[8]Bulut E,Geyik S C,Szymanski B K.Utilizing correlated node mobility for efficient DTN routing[J].Pervasive and Mobile Computing,2014,13(4):150-163.

[9]Ayub Q,Rashid S,Zahid M S M,et al.Contact quality based forwarding strategy for delay tolerant network[J].Journal of Network and Computer Applications,2014,39(1):302-309.

[10]Mota V F S,Cunha F D,Macedo D F,et al.Protocols,mobility models and tools in opportunistic networks:A survey[J].Computer Communications,2014,48(8):5-19.

[11]ZHANG Feng,WANG Xiaoming,ZHANG Shanshan.Buffer aware ProPhet routing algorithm for opportunistic networks[J].Computer Engineering and Design,2015,36(5):1145-1149(in Chinese).[張峰,王小明,張珊珊.機(jī)會(huì)網(wǎng)絡(luò)中考慮緩存的ProPhet路由算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2015,36(5):1145-1149.]