吳俊,，嚴(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ū)域為中心將整個網(wǎng)絡(luò)環(huán)境劃分為若干塊,。節(jié)點(diǎn)在熱點(diǎn)之間攜帶數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)從而提高了空閑節(jié)點(diǎn)的利用率。最后分析了該路由算法與傳統(tǒng)的延時容忍網(wǎng)絡(luò)路由算法在各方面的性能表現(xiàn),，證明了所提出算法的高效性,。

　　關(guān)鍵詞：熱點(diǎn)區(qū)域;延時容忍網(wǎng)絡(luò);傳輸鏈路;節(jié)點(diǎn)流

0引言

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

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

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

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

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

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

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

　　（3)傳染路由：當(dāng)源節(jié)點(diǎn)在它的周圍發(fā)現(xiàn)有n個鄰居節(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ù)包移動直到目標(biāo)節(jié)點(diǎn)接收到數(shù)據(jù)包或數(shù)據(jù)包的生命周期已經(jīng)結(jié)束。

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

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

　　2.1存在問題及解決方案

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

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

　　2.2具體實現(xiàn)

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

　?。?）熱點(diǎn)的選擇

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

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

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

　?、賯鬏攷挘涸谶@里用Ntij表示熱點(diǎn)i、 j之間的節(jié)點(diǎn)數(shù)目,，那么熱點(diǎn)之間的帶寬為：

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

　　②構(gòu)建路由表：根據(jù)已經(jīng)產(chǎn)生的鏈路帶寬表,，每個熱點(diǎn)計算發(fā)送大小為W bit數(shù)據(jù)給鄰居熱點(diǎn)所需要的時延,。假設(shè)每個節(jié)點(diǎn)的內(nèi)存為S bit，從熱點(diǎn)i到j(luò)傳輸?shù)念A(yù)計時延為,。T是傳送W bit數(shù)據(jù)的時間單位,。然后每個熱點(diǎn)的路由表根據(jù)自身到鄰居熱點(diǎn)的時延初始化。每個熱點(diǎn)使用距離向量協(xié)議構(gòu)建傳輸過程中指明下一跳熱點(diǎn)的完整路由表,。并且整個傳輸過程的時延為D(Hi,Hd),。對于路由表中的每一項，如果目的熱點(diǎn)Hd不在i的路由表中,，則通過設(shè)置下一跳ID為Hj,、總共時延為Dij+D(Hi+Hd)將目的熱點(diǎn)增加到路由表中。如果目的熱點(diǎn)已經(jīng)存在,，則檢查是否D(Hi,Hd)≤Dij+D(Hj,Hd),如果是則不改變,，否則下一跳ID為Lj，總時延更新為Dij+D(Hj,Hd),。這個過程不斷重復(fù)直到每個熱點(diǎn)最終到達(dá)目的熱點(diǎn),。

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

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

　　為了預(yù)測節(jié)點(diǎn)的傳輸目標(biāo)熱點(diǎn)，這里使用orderk馬爾科夫預(yù)測［10］,。假設(shè)下一次傳輸與過去的k次傳輸相關(guān)。一個節(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ù)的傳輸,。因此一個節(jié)點(diǎn)每次可能的下一次傳輸Txn,xn+1的概率如下所示：

　　and

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

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

　?、佼?dāng)源節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)后,，將數(shù)據(jù)包發(fā)送給遭遇的第一個熱點(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),；

　?、鄯駝t，熱點(diǎn)Hi檢查自身路由表選擇合適的下一個熱點(diǎn)并將熱點(diǎn)ID和預(yù)計的總時延附加在數(shù)據(jù)包上,；

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

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

3性能分析

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

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

　?。?）傳輸成功率：圖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)存上升時,，傳輸成功率也隨之上升。同樣可以看出,，當(dāng)數(shù)據(jù)包大小不斷上升,，這幾種方法的傳輸成功率開始下降。這可以說明延時容忍網(wǎng)絡(luò)對數(shù)據(jù)包的大小有一定要求,。

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

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

4結(jié)束語

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

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

       參考文獻(xiàn)

　?。?］ LINDGREN A, DORIA A, SCHELN O.Probabilistic routing in intermittently connected networks［J］. Mobile Computing and Communications Review, 2003,7(3):1920.

　?。?］ 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.

　?。?］ BURGESS J, GALLAGHER B, JENSEN D, et al. MaxProp:routing for vehiclebased disruptiontolerant networks［C］. In Proc. of INFOCOM, 2006:111.

　?。?］ 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.

　?。?］ 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.

　?。?］ 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.

　?。?0］ 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.