吳俊，嚴俊

　　(揚州大學 信息工程學院,江蘇 揚州 225127)

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

　　關鍵詞：熱點區(qū)域;延時容忍網絡;傳輸鏈路;節(jié)點流

0引言

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

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

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

1延時容忍網絡

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

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

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

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

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

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

　　2.1存在問題及解決方案

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

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

　　2.2具體實現(xiàn)

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

　?。?）熱點的選擇

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

　?。?）構建路由表

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

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

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

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

　?。?）預測傳輸節(jié)點

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

　　為了預測節(jié)點的傳輸目標熱點，這里使用orderk馬爾科夫預測［10］。假設下一次傳輸與過去的k次傳輸相關。一個節(jié)點的傳輸歷史表示為：

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

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

　　and

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

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

　?、佼斣垂?jié)點產生數(shù)據后，將數(shù)據包發(fā)送給遭遇的第一個熱點；

　?、诋敓狳cHi接收數(shù)據包后首先檢查是否存在節(jié)點將數(shù)據包直接發(fā)送給目的熱點。如果存在此節(jié)點，則將數(shù)據包發(fā)送給該節(jié)點；

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

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

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

3性能分析

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

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

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

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

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

4結束語

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

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

       參考文獻

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

　　［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.

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

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

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