吳俊，嚴俊

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

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

　　關鍵詞：熱點區域;延時容忍網絡;傳輸鏈路;節點流

0引言

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

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

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

1延時容忍網絡

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

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

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

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

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

2一種基于熱點數據傳輸方案

　　2.1存在問題及解決方案

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

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

　　2.2具體實現

　　本文延時容忍網絡數據傳輸系統主要由以下幾部分構成：

　　（1）熱點的選擇

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

　　（2）構建路由表

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

　　①傳輸帶寬：在這里用Ntij表示熱點i、 j之間的節點數目，那么熱點之間的帶寬為：

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

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

　　（3）預測傳輸節點

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

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

　　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次連續的傳輸。因此一個節點每次可能的下一次傳輸Txn,xn+1的概率如下所示：

　　and

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

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

　　①當源節點產生數據后，將數據包發送給遭遇的第一個熱點；

　　②當熱點Hi接收數據包后首先檢查是否存在節點將數據包直接發送給目的熱點。如果存在此節點，則將數據包發送給該節點；

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

　　④熱點Hi監測周圍節點是否有合適的內存并將數據包發送給訪問下一個熱點概率最高的節點；

　　⑤當節點遭遇熱點Hj后，將數據包存儲在熱點Hj中，然后重復上述過程選擇下一個熱點直到最終傳送到目的熱點。

3性能分析

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

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

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

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

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

4結束語

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

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

       參考文獻

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