吳俊，嚴(yán)俊

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

      摘要：提出了一種熱點(diǎn)區(qū)域間節(jié)點(diǎn)流傳輸算法，在該算法中，將節(jié)點(diǎn)頻繁訪問(wè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)，證明了所提出算法的高效性。

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

0引言

　　當(dāng)前網(wǎng)絡(luò)服務(wù)模型的設(shè)計(jì)主要基于一些現(xiàn)有的端到端傳輸理論。這些理論不能應(yīng)用在一些新興的網(wǎng)絡(luò)中，比如在邊境監(jiān)控中大量部署的無(wú)線傳感器網(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)說(shuō)明通過(guò)減少源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的跳數(shù)可以提升數(shù)據(jù)的吞吐量從而減少時(shí)延［1］。

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

　　最終通過(guò)相關(guān)的實(shí)驗(yàn)仿真，對(duì)該算法的傳輸時(shí)延、通信開(kāi)銷等性能與傳統(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è)過(guò)程中有端到端的連接。延時(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中是無(wú)效的，DTN的路由選擇使用新的模型，包含獨(dú)立的語(yǔ)句、本地發(fā)送指令等［4］。傳統(tǒng)的延時(shí)容忍網(wǎng)絡(luò)主要分為以下幾種路由方法：

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

　　（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é)束。

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

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

　　2.1存在問(wèn)題及解決方案

　　在延時(shí)容忍網(wǎng)絡(luò)中，一個(gè)關(guān)鍵的問(wèn)題就是高效的路由選擇。因此本文集中關(guān)注如何通過(guò)利用節(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)并沒(méi)有被利用，這也造成資源的浪費(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時(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ù)傳輸能力。在傳輸過(guò)程中，熱點(diǎn)使用距離向量來(lái)構(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)成：

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

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

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

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

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

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

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

　?。?）預(yù)測(cè)傳輸節(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ò)程是至關(guān)重要的。這里根據(jù)每個(gè)節(jié)點(diǎn)對(duì)熱點(diǎn)的歷史訪問(wèn)記錄預(yù)測(cè)節(jié)點(diǎn)的下一次傳輸位置。

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

　　and

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

　　在數(shù)據(jù)包發(fā)送過(guò)程中，熱點(diǎn)根據(jù)自身的路由表選擇下一跳熱點(diǎn)然后使用預(yù)測(cè)的節(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)；

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

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

　?、莓?dāng)節(jié)點(diǎn)遭遇熱點(diǎn)Hj后，將數(shù)據(jù)包存儲(chǔ)在熱點(diǎn)Hj中，然后重復(fù)上述過(guò)程選擇下一個(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 000 m×5 000 m，網(wǎng)絡(luò)中共有200個(gè)節(jié)點(diǎn)，城市地圖中存在15個(gè)熱點(diǎn)區(qū)域。數(shù)據(jù)產(chǎn)生速率為每個(gè)節(jié)點(diǎn)每30 s產(chǎn)生一條消息，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的移動(dòng)速度相同，數(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)行對(duì)比。為了全面驗(yàn)證熱點(diǎn)間節(jié)點(diǎn)流傳輸算法，本文使用數(shù)據(jù)傳輸時(shí)延、傳輸成功率以及通信開(kāi)銷作為性能評(píng)價(jià)指標(biāo)。

　?。?）通信開(kāi)銷對(duì)比：圖2和圖3比較了在節(jié)點(diǎn)內(nèi)存和數(shù)據(jù)包的大小變化情況下幾種不同的路由方法的通信開(kāi)銷，在相同的數(shù)據(jù)包大小和數(shù)據(jù)傳輸率下，先知路由的通信開(kāi)銷最小，而基于熱點(diǎn)路由的通信開(kāi)銷稍大于先知路由，而傳染路由產(chǎn)生最大的通信開(kāi)銷。同時(shí)隨著節(jié)點(diǎn)內(nèi)存的增加，熱點(diǎn)路由的通信開(kāi)銷增加比較緩慢。由此可見(jiàn)，基于熱點(diǎn)路由在減少通信開(kāi)銷方面有較好的表現(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)存上升時(shí)，傳輸成功率也隨之上升。同樣可以看出，當(dāng)數(shù)據(jù)包大小不斷上升，這幾種方法的傳輸成功率開(kāi)始下降。這可以說(shuō)明延時(shí)容忍網(wǎng)絡(luò)對(duì)數(shù)據(jù)包的大小有一定要求。

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

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

4結(jié)束語(yǔ)

　　本文提出了一種基于熱點(diǎn)區(qū)域間節(jié)點(diǎn)流進(jìn)行數(shù)據(jù)傳輸?shù)穆酚伤惴?。該算法充分利用熱點(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í)延和通信開(kāi)銷方面有著較均衡的表現(xiàn)。

　　同時(shí)，仿真結(jié)果也表明，如果過(guò)多的節(jié)點(diǎn)參與數(shù)據(jù)傳輸就會(huì)產(chǎn)生一定的網(wǎng)絡(luò)擁堵，將導(dǎo)致網(wǎng)絡(luò)鏈路負(fù)載加重，進(jìn)而產(chǎn)生網(wǎng)絡(luò)擁塞等問(wèn)題，因此提出合適的通信鏈路負(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.

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

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