延時(shí)容忍網(wǎng)絡(luò)中基于熱點(diǎn)區(qū)域間節(jié)點(diǎn)流數(shù)據(jù)傳輸方案

吳　俊，嚴(yán)　俊

(揚(yáng)州大學(xué) 信息工程學(xué)院,江蘇 揚(yáng)州 225127)

?

延時(shí)容忍網(wǎng)絡(luò)中基于熱點(diǎn)區(qū)域間節(jié)點(diǎn)流數(shù)據(jù)傳輸方案

吳俊，嚴(yán)俊

(揚(yáng)州大學(xué) 信息工程學(xué)院,江蘇 揚(yáng)州 225127)

提出了一種熱點(diǎn)區(qū)域間節(jié)點(diǎn)流傳輸算法，在該算法中，將節(jié)點(diǎn)頻繁訪問的區(qū)域作為熱點(diǎn)區(qū)域并以熱點(diǎn)區(qū)域?yàn)橹行膶⒄麄€(gè)網(wǎng)絡(luò)環(huán)境劃分為若干塊。節(jié)點(diǎn)在熱點(diǎn)之間攜帶數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)從而提高了空閑節(jié)點(diǎn)的利用率。最后分析了該路由算法與傳統(tǒng)的延時(shí)容忍網(wǎng)絡(luò)路由算法在各方面的性能表現(xiàn)，證明了所提出算法的高效性。

熱點(diǎn)區(qū)域;延時(shí)容忍網(wǎng)絡(luò);傳輸鏈路;節(jié)點(diǎn)流

引用格式：吳俊，嚴(yán)俊. 延時(shí)容忍網(wǎng)絡(luò)中基于熱點(diǎn)區(qū)域間節(jié)點(diǎn)流數(shù)據(jù)傳輸方案[J].微型機(jī)與應(yīng)用，2016,35(17)：60-63,71.

0　引言

當(dāng)前網(wǎng)絡(luò)服務(wù)模型的設(shè)計(jì)主要基于一些現(xiàn)有的端到端傳輸理論。這些理論不能應(yīng)用在一些新興的網(wǎng)絡(luò)中，比如在邊境監(jiān)控中大量部署的無線傳感器網(wǎng)絡(luò)、偏遠(yuǎn)地區(qū)的非即時(shí)數(shù)據(jù)傳輸系統(tǒng)。在上述環(huán)境中，由于基礎(chǔ)設(shè)施的不完善或者出于成本考慮，使用傳統(tǒng)的網(wǎng)絡(luò)連接是不現(xiàn)實(shí)的。為了允許上述網(wǎng)絡(luò)中的節(jié)點(diǎn)可以相互通信，延時(shí)容忍網(wǎng)絡(luò)的概念被提出并進(jìn)行運(yùn)用。傳統(tǒng)的延時(shí)容忍網(wǎng)絡(luò)需要節(jié)點(diǎn)存儲(chǔ)信息等待下一個(gè)節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，這將浪費(fèi)大量時(shí)間從而增加了延遲。GROSSGLAUSER M的研究工作已經(jīng)說明通過減少源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的跳數(shù)可以提升數(shù)據(jù)的吞吐量從而減少時(shí)延[1]。

當(dāng)前的延時(shí)容忍網(wǎng)絡(luò)路由算法存在一個(gè)問題，即：當(dāng)從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的轉(zhuǎn)發(fā)跳數(shù)過多時(shí)，大量的閑置節(jié)點(diǎn)沒有被使用，這既造成了資源的浪費(fèi)，也在無形中增加了數(shù)據(jù)的傳輸時(shí)延。為了解決這個(gè)問題，本文提出了一種熱點(diǎn)區(qū)域間節(jié)點(diǎn)流傳輸算法，該算法充分利用了延時(shí)容忍網(wǎng)絡(luò)中的大量閑置節(jié)點(diǎn)，通過使用熱點(diǎn)區(qū)域之間的頻繁移動(dòng)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)從而提升了數(shù)據(jù)的吞吐量，減少了傳輸時(shí)延，并提高了數(shù)據(jù)傳輸?shù)某晒β省?/p>

最終通過相關(guān)的實(shí)驗(yàn)仿真，對(duì)該算法的傳輸時(shí)延、通信開銷等性能與傳統(tǒng)的路由算法進(jìn)行比較，證明了所提出算法的可行性和高效性。

1　延時(shí)容忍網(wǎng)絡(luò)

延時(shí)容忍網(wǎng)絡(luò)(Delay Tolerant Network, DTN)的路由是一種虛擬的路由，與傳統(tǒng)自組網(wǎng)中的實(shí)際的物理路由相比，DTN的路由不需要在信息傳輸?shù)恼麄€(gè)過程中有端到端的連接。延時(shí)容忍網(wǎng)絡(luò)的路由主要是攜帶-存儲(chǔ)-轉(zhuǎn)發(fā)的方式[2-3]。在DTN中做出路由選擇的決定并不需要端到端的連接。DTN路由也遭遇一些其他的挑戰(zhàn)，比如節(jié)點(diǎn)的緩存空間有限、傳輸成功率低等。正是由于這些傳統(tǒng)網(wǎng)絡(luò)中的一些路由方法比如動(dòng)態(tài)資源路由在DTN中是無效的，DTN的路由選擇使用新的模型，包含獨(dú)立的語句、本地發(fā)送指令等[4]。傳統(tǒng)的延時(shí)容忍網(wǎng)絡(luò)主要分為以下幾種路由方法：

(1)概率路由：概率路由使用節(jié)點(diǎn)之前的碰撞歷史記錄來預(yù)計(jì)未來的碰撞概率。當(dāng)兩個(gè)節(jié)點(diǎn)再一次相遇時(shí)，概率路由提升兩個(gè)節(jié)點(diǎn)的碰撞概率[5-6]。同樣的由概率路由發(fā)展而來的最大概率路由[7]和最大貢獻(xiàn)路由[8]則是由基于發(fā)送成功率而形成的存儲(chǔ)優(yōu)先次序拓展而來。

(2)社會(huì)網(wǎng)絡(luò)路由：由于攜帶移動(dòng)設(shè)備的人或設(shè)備通常存在一定的社會(huì)關(guān)系，因此基于社會(huì)網(wǎng)絡(luò)的路由算法[9-10]探索了社會(huì)網(wǎng)絡(luò)用于延時(shí)容忍網(wǎng)絡(luò)中發(fā)送數(shù)據(jù)包的性能優(yōu)劣。

(3)傳染路由：當(dāng)源節(jié)點(diǎn)在它的周圍發(fā)現(xiàn)有n個(gè)鄰居節(jié)點(diǎn),且這些鄰居節(jié)點(diǎn)都在源節(jié)點(diǎn)的通信范圍之內(nèi)，源節(jié)點(diǎn)將n份數(shù)據(jù)包拷貝發(fā)送給這些鄰居節(jié)點(diǎn)。然后這些節(jié)點(diǎn)攜帶數(shù)據(jù)包移動(dòng)直到目標(biāo)節(jié)點(diǎn)接收到數(shù)據(jù)包或數(shù)據(jù)包的生命周期已經(jīng)結(jié)束。

(4)散發(fā)等待路由：散發(fā)等待路由[11]是傳染路由的一種改進(jìn)。相對(duì)于傳染路由散發(fā)等待路由通過設(shè)置傳輸節(jié)點(diǎn)數(shù)目的上限減少了一定的通信開銷從而減少了網(wǎng)絡(luò)擁塞。

2　一種基于熱點(diǎn)數(shù)據(jù)傳輸方案

2.1存在問題及解決方案

在延時(shí)容忍網(wǎng)絡(luò)中，一個(gè)關(guān)鍵的問題就是高效的路由選擇。因此本文集中關(guān)注如何通過利用節(jié)點(diǎn)的移動(dòng)能力提升數(shù)據(jù)吞吐量、減少時(shí)延并提高數(shù)據(jù)傳輸?shù)某晒β省Ｈ鐖D1左側(cè)圖所示為在傳統(tǒng)的DTN路由算法中，源節(jié)點(diǎn)1產(chǎn)生數(shù)據(jù)包并需要將數(shù)據(jù)包發(fā)送到目的節(jié)點(diǎn)7、8。它首先由移動(dòng)節(jié)點(diǎn)1攜帶數(shù)據(jù)包等待遭遇移動(dòng)節(jié)點(diǎn)2。節(jié)點(diǎn)2將數(shù)據(jù)轉(zhuǎn)發(fā)并等待預(yù)計(jì)碰撞目的節(jié)點(diǎn)8的節(jié)點(diǎn)3和預(yù)計(jì)碰撞目的節(jié)點(diǎn)7的節(jié)點(diǎn)4。由于單一節(jié)點(diǎn)碰撞另一節(jié)點(diǎn)的概率較低，因此這需要消耗較多的時(shí)間等待，從而產(chǎn)生較大的延遲。并且大量的節(jié)點(diǎn)移動(dòng)并沒有被利用，這也造成資源的浪費(fèi)。這里使用一種新的傳輸方法進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)。

圖1　傳輸方案對(duì)比

如圖1右側(cè)圖所示，當(dāng)數(shù)據(jù)包從源節(jié)點(diǎn)1產(chǎn)生需要發(fā)往目的節(jié)點(diǎn)7和8時(shí)，可以規(guī)劃路徑，分別為熱點(diǎn)H1、H2、H5、H7和H1、H2、H5、H8、H9。Node-Flow用從一個(gè)熱點(diǎn)Hi到熱點(diǎn)Hj之間的移動(dòng)節(jié)點(diǎn)表示兩個(gè)熱點(diǎn)之間的數(shù)據(jù)傳輸能力。在傳輸過程中，熱點(diǎn)使用距離向量來構(gòu)建自身的路由表從而指明下一跳的熱點(diǎn)。熱點(diǎn)之間的傳輸使用概率路由，然后每個(gè)熱點(diǎn)根據(jù)已經(jīng)構(gòu)建的路由表選擇到下一個(gè)目的熱點(diǎn)傳輸效率高的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。這極大地提高了數(shù)據(jù)轉(zhuǎn)發(fā)的成功率并降低了時(shí)延。

2.2具體實(shí)現(xiàn)

本文延時(shí)容忍網(wǎng)絡(luò)數(shù)據(jù)傳輸系統(tǒng)主要由以下幾部分構(gòu)成：

(1)熱點(diǎn)的選擇

選擇移動(dòng)節(jié)點(diǎn)頻繁訪問的地點(diǎn)作為熱點(diǎn)，并以熱點(diǎn)為中心把整個(gè)網(wǎng)絡(luò)環(huán)境劃分成若干份。為了選擇熱點(diǎn)，一個(gè)簡單的方法就是收集節(jié)點(diǎn)的歷史訪問記錄并將訪問記錄較高的地點(diǎn)作為熱點(diǎn)。根據(jù)產(chǎn)生的熱點(diǎn)構(gòu)建熱點(diǎn)列表。當(dāng)然在同一個(gè)區(qū)域內(nèi)選擇節(jié)點(diǎn)訪問次數(shù)最多的點(diǎn)為候選熱點(diǎn)。

(2)構(gòu)建路由表

在延時(shí)容忍網(wǎng)絡(luò)中，每個(gè)熱點(diǎn)使用它與其他熱點(diǎn)之間的節(jié)點(diǎn)流動(dòng)數(shù)量來表示兩個(gè)熱點(diǎn)之間的傳輸帶寬并根據(jù)此帶寬來估計(jì)傳輸時(shí)延。根據(jù)預(yù)計(jì)的時(shí)延，路由表指出在傳往目的熱點(diǎn)過程中的每一個(gè)下一跳熱點(diǎn)。

其中Bijnew和Bijold分別為更新后的帶寬和更新前的帶寬。

(3)預(yù)測傳輸節(jié)點(diǎn)

由于延時(shí)容忍網(wǎng)絡(luò)依賴于節(jié)點(diǎn)的移動(dòng)轉(zhuǎn)發(fā)傳送數(shù)據(jù)，因此選擇合適的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)對(duì)整個(gè)傳輸過程是至關(guān)重要的。這里根據(jù)每個(gè)節(jié)點(diǎn)對(duì)熱點(diǎn)的歷史訪問記錄預(yù)測節(jié)點(diǎn)的下一次傳輸位置。

為了預(yù)測節(jié)點(diǎn)的傳輸目標(biāo)熱點(diǎn)，這里使用order-k馬爾科夫預(yù)測[10]。假設(shè)下一次傳輸與過去的k次傳輸相關(guān)。一個(gè)節(jié)點(diǎn)的傳輸歷史表示為：

TH=Tx1,x2Tx2,x3…Txj-1,xj…Txn-1,xn

這里Txj-1,xj表示從熱點(diǎn)Hxj-1到Hxj的一次傳輸。使用X(n-k,n)=Txn-k,xn-k+1…Txn-1,xn表示過去k次連續(xù)的傳輸。因此一個(gè)節(jié)點(diǎn)每次可能的下一次傳輸Txn,xn+1的概率如下所示：

where

Pr(X(n-k,n),Txn,xn+1)=Pr(X(n-k,n+1))

and

這里N(X(·))和N(Allk)表示X(·)的數(shù)目和TH中k次連續(xù)的傳輸。然后產(chǎn)生最大概率的傳輸被選擇為預(yù)計(jì)傳輸節(jié)點(diǎn)。

在數(shù)據(jù)包發(fā)送過程中，熱點(diǎn)根據(jù)自身的路由表選擇下一跳熱點(diǎn)然后使用預(yù)測的節(jié)點(diǎn)將數(shù)據(jù)包轉(zhuǎn)發(fā)給下一個(gè)熱點(diǎn)。本文路由算法分為以下幾步：

①當(dāng)源節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)后，將數(shù)據(jù)包發(fā)送給遭遇的第一個(gè)熱點(diǎn)；

②當(dāng)熱點(diǎn)Hi接收數(shù)據(jù)包后首先檢查是否存在節(jié)點(diǎn)將數(shù)據(jù)包直接發(fā)送給目的熱點(diǎn)。如果存在此節(jié)點(diǎn)，則將數(shù)據(jù)包發(fā)送給該節(jié)點(diǎn)；

③否則，熱點(diǎn)Hi檢查自身路由表選擇合適的下一個(gè)熱點(diǎn)并將熱點(diǎn)ID和預(yù)計(jì)的總時(shí)延附加在數(shù)據(jù)包上；

④熱點(diǎn)Hi監(jiān)測周圍節(jié)點(diǎn)是否有合適的內(nèi)存并將數(shù)據(jù)包發(fā)送給訪問下一個(gè)熱點(diǎn)概率最高的節(jié)點(diǎn)；

⑤當(dāng)節(jié)點(diǎn)遭遇熱點(diǎn)Hj后，將數(shù)據(jù)包存儲(chǔ)在熱點(diǎn)Hj中，然后重復(fù)上述過程選擇下一個(gè)熱點(diǎn)直到最終傳送到目的熱點(diǎn)。

3　性能分析

下面使用ONE模擬器[11]進(jìn)行一個(gè)基于熱點(diǎn)傳輸事件的仿真并將仿真結(jié)果與其他傳統(tǒng)傳輸方法進(jìn)行對(duì)比。仿真在赫爾辛基城市地圖(ONE模擬器默認(rèn)地圖)上進(jìn)行，整個(gè)仿真區(qū)域的范圍為10 000m×5 000m，網(wǎng)絡(luò)中共有200個(gè)節(jié)點(diǎn)，城市地圖中存在15個(gè)熱點(diǎn)區(qū)域。數(shù)據(jù)產(chǎn)生速率為每個(gè)節(jié)點(diǎn)每30s產(chǎn)生一條消息，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的移動(dòng)速度相同，數(shù)據(jù)包的生命周期設(shè)置為1 000s。數(shù)據(jù)的大小從10kb～100kb隨機(jī)分配。節(jié)點(diǎn)的通信范圍為50m，數(shù)據(jù)傳輸速度為50kb/s。將熱點(diǎn)傳輸方案與傳染路由、散發(fā)等待路由和先知路由進(jìn)行對(duì)比。為了全面驗(yàn)證熱點(diǎn)間節(jié)點(diǎn)流傳輸算法，本文使用數(shù)據(jù)傳輸時(shí)延、傳輸成功率以及通信開銷作為性能評(píng)價(jià)指標(biāo)。

(1)通信開銷對(duì)比：圖2和圖3比較了在節(jié)點(diǎn)內(nèi)存和數(shù)據(jù)包的大小變化情況下幾種不同的路由方法的通信開銷，在相同的數(shù)據(jù)包大小和數(shù)據(jù)傳輸率下，先知路由的通信開銷最小，而基于熱點(diǎn)路由的通信開銷稍大于先知路由，而傳染路由產(chǎn)生最大的通信開銷。同時(shí)隨著節(jié)點(diǎn)內(nèi)存的增加，熱點(diǎn)路由的通信開銷增加比較緩慢。由此可見，基于熱點(diǎn)路由在減少通信開銷方面有較好的表現(xiàn)，并且不隨節(jié)點(diǎn)內(nèi)存變化而產(chǎn)生較大影響。

圖2　節(jié)點(diǎn)內(nèi)存對(duì)通信開銷影響

圖3　數(shù)據(jù)包大小對(duì)通信開銷影響

圖4　內(nèi)存大小對(duì)傳輸成功率影響

圖5　數(shù)據(jù)包大小對(duì)傳輸成功率影響

(2)傳輸成功率：圖4和圖5展示了在節(jié)點(diǎn)的內(nèi)存和數(shù)據(jù)包的大小變化情況下4種不同的路由方法的傳輸成功率。由圖可知，在設(shè)定的生命周期內(nèi)傳染路由的傳輸成功率最高，其次是熱點(diǎn)路由。根據(jù)仿真的輸出結(jié)果可知，熱點(diǎn)路由的表現(xiàn)已經(jīng)優(yōu)于散發(fā)等待路由。當(dāng)節(jié)點(diǎn)的內(nèi)存上升時(shí)，傳輸成功率也隨之上升。同樣可以看出，當(dāng)數(shù)據(jù)包大小不斷上升，這幾種方法的傳輸成功率開始下降。這可以說明延時(shí)容忍網(wǎng)絡(luò)對(duì)數(shù)據(jù)包的大小有一定要求。

(3)平均傳輸時(shí)延：圖6和圖7說明了測試中使用這4種不同的路由方法的平均時(shí)延。可以觀察到，基于熱點(diǎn)路由的平均時(shí)延大于傳染路由但小于散發(fā)等待路由，而先知路由則產(chǎn)生了最高的傳輸時(shí)延。

圖6　節(jié)點(diǎn)內(nèi)存大小對(duì)平均時(shí)延影響

圖7　數(shù)據(jù)包大小對(duì)平均時(shí)延影響

通過以上仿真可以看出，不管在哪種條件下，熱點(diǎn)路由在通信開銷成功率和傳輸時(shí)延方面都可以取得較好的表現(xiàn)，在各方面可以取得一個(gè)平衡。

4　結(jié)束語

本文提出了一種基于熱點(diǎn)區(qū)域間節(jié)點(diǎn)流進(jìn)行數(shù)據(jù)傳輸?shù)穆酚伤惴āＴ撍惴ǔ浞掷脽狳c(diǎn)區(qū)域間大量頻繁移動(dòng)的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸，提升了通信鏈路的數(shù)據(jù)吞吐量，減少了因不存在合適轉(zhuǎn)發(fā)節(jié)點(diǎn)而導(dǎo)致的大量等待時(shí)間。仿真實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的延時(shí)容忍網(wǎng)絡(luò)路由選擇算法相比，本文提出的算法在傳輸時(shí)延和通信開銷方面有著較均衡的表現(xiàn)。

同時(shí)，仿真結(jié)果也表明，如果過多的節(jié)點(diǎn)參與數(shù)據(jù)傳輸就會(huì)產(chǎn)生一定的網(wǎng)絡(luò)擁堵，將導(dǎo)致網(wǎng)絡(luò)鏈路負(fù)載加重，進(jìn)而產(chǎn)生網(wǎng)絡(luò)擁塞等問題，因此提出合適的通信鏈路負(fù)載均衡策略是本文的后續(xù)工作。

[1] LINDGREN A, DORIA A, SCHELéN O.Probabilistic routing in intermittently connected networks[J]. Mobile Computing and Communications Review, 2003,7(3):19-20.

[2] LI F, WU J. MOPS: providing content-based service in disruption-tolerant networks[C]. In Proc. IEEE ICDCS, 2009: 526-533.

[3] DALY E M, HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANETs[C]. In Proc. ACM MobiHoc, 2007: 32-40.

[4] BURGESS J, GALLAGHER B, JENSEN D, et al. MaxProp:routing for vehicle-based disruption-tolerant networks[C]. In Proc. of INFOCOM, 2006:1-11.

[5] BALASUBRAMANIAN A, LEVINE B N, VENKATARAMANI A. DTN routing as a resource allocation problem[C]. In Proc. of SIGCOMM, 2007,37(4):373-384.

[6] LEE K, YI Y, JEONG J, et al. MaxContribution: On optimal resource allocation in delay tolerant networks[C].In Proc. of INFOCOM, 2010,14(3):1136-1144.

[7] HUI P, CROWCROFT J, YONEKI E. Bubble rap: social-based forwarding in delay tolerant networks[C]. In Proc. of MobiHoc, 2008,10(11):1576-1589.

[8] DALY E M, HAAHR M. Social network analysis for routing in disconnected delay-tolerant manets[C]. In Proc. of MobiHoc, 2007:32-40.

[9] YONEKI E, HUI P, CHAN S, et al. A socio-aware overlay for publish/subscribe communication in delay tolerant networks[C]. In Proc.of MSWiM, 2007:225-234.[10] COSTA P, MASCOLO C, MUSOLESI M, et al. Socially-aware routing for publish-subscribe in delay-tolerant mobile ad hoc networks[J].IEEE JSAC, 2008，26(5)：748-760.

[11] KERANEN A, OTT J, KARKKAINEN T. The ONE simulator for DTN protocol evaluation[C]. Proceedings of the 2nd International Conference on Simulation Tools and Techniques,Rome,2009:1-10.

Data transmission based on node-flow between hot spots in delay tolerant network

Wu Jun, Yan Jun

(College of Information Engineering,Yangzhou University, Yangzhou 225127,China)

In this article, we put forward a data flow transmission algorithm between hot spots.In the algorithm,it uses the area where are frequently accessed as the hot spots and then divides the area into some blocks with the hot spots to be the center of region.Nodes move with packets between hot spots in order to improve the utilization of idle nodes.In the end,we analyzed the performance of the proposed algorithm and the traditional algorithms in delay tolerant network to prove the effeciency of our algorithms.

hotspot region; delay tolerant network;network link;node flow

TN929.5

ADOI： 10.19358/j.issn.1674- 7720.2016.17.019

2016-05-09)

吳俊(1970-)，男，博士，副教授，主要研究方向：無線傳感器、網(wǎng)絡(luò)拓?fù)洹?/p>

嚴(yán)俊(1992-)，男，碩士研究生，主要研究方向：傳感器網(wǎng)絡(luò)。