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

吳　俊，嚴　俊

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

?

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

吳俊，嚴俊

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

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

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

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

0　引言

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

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

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

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é)點的緩存空間有限、傳輸成功率低等。正是由于這些傳統(tǒng)網(wǎng)絡(luò)中的一些路由方法比如動態(tài)資源路由在DTN中是無效的，DTN的路由選擇使用新的模型，包含獨立的語句、本地發(fā)送指令等[4]。傳統(tǒng)的延時容忍網(wǎng)絡(luò)主要分為以下幾種路由方法：

(1)概率路由：概率路由使用節(jié)點之前的碰撞歷史記錄來預(yù)計未來的碰撞概率。當兩個節(jié)點再一次相遇時，概率路由提升兩個節(jié)點的碰撞概率[5-6]。同樣的由概率路由發(fā)展而來的最大概率路由[7]和最大貢獻路由[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)傳染路由：當源節(jié)點在它的周圍發(fā)現(xiàn)有n個鄰居節(jié)點,且這些鄰居節(jié)點都在源節(jié)點的通信范圍之內(nèi)，源節(jié)點將n份數(shù)據(jù)包拷貝發(fā)送給這些鄰居節(jié)點。然后這些節(jié)點攜帶數(shù)據(jù)包移動直到目標節(jié)點接收到數(shù)據(jù)包或數(shù)據(jù)包的生命周期已經(jīng)結(jié)束。

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

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

2.1存在問題及解決方案

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

圖1　傳輸方案對比

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

2.2具體實現(xiàn)

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

(1)熱點的選擇

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

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

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

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

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

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

為了預(yù)測節(jié)點的傳輸目標熱點，這里使用order-k馬爾科夫預(yù)測[10]。假設(shè)下一次傳輸與過去的k次傳輸相關(guān)。一個節(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的概率如下所示：

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ù)計傳輸節(jié)點。

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

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

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

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

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

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

3　性能分析

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

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

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

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

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

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

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

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

圖6　節(jié)點內(nèi)存大小對平均時延影響

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

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

4　結(jié)束語

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

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

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