李文藻等

摘 要：容延遲網(wǎng)絡DTN（Delay Tolerant Networks）在基于城市部署下具有區(qū)域密度差別大，局部節(jié)點聚集停頓時間較長的特征，節(jié)點緩存大小對數(shù)據(jù)投遞率具有較大的影響。文章利用工作日模型WDM（Working Day Movement）設置趨向于真實城市的場景，分析Prophet路由算法與Direct Delivery路由算法對移動節(jié)點的影響。實驗結果表明，Prophet路由性能明顯優(yōu)于Direct Delivery路由性能，數(shù)據(jù)包大小在500k～1M的基礎上，節(jié)點緩存在10M左右，DTN網(wǎng)絡投遞率與數(shù)據(jù)包時延均值獲得最優(yōu)效果。

關鍵詞：容延遲網(wǎng)絡；節(jié)點緩存；數(shù)據(jù)投遞率；工作日模型； 路由算法

1 引言

容延遲網(wǎng)絡是較為新型的網(wǎng)絡結構，對延遲、中斷有一定的容忍性，是未來移動通信領域發(fā)展的重要方向之一。容延遲網(wǎng)絡與目前網(wǎng)絡最大的區(qū)別在于不需要源節(jié)點與目的節(jié)點存在確定的路徑，數(shù)據(jù)包的傳輸模式依靠移動節(jié)點的攜帶-存儲-轉發(fā)的模式，利用節(jié)點的移動來創(chuàng)造節(jié)點的相遇的機會并傳輸數(shù)據(jù)包[1]。容延遲網(wǎng)絡目前討論較多的應用于缺乏通信基礎設施、網(wǎng)絡環(huán)境及自然環(huán)境部署比較惡劣的挑戰(zhàn)性網(wǎng)絡中。主要的討論集中在軍事、野生動物研究、星際網(wǎng)絡、陸地移動網(wǎng)絡、車聯(lián)網(wǎng)以及傳感器網(wǎng)絡等領域[2-3]。伴隨著移動智能終端的普及以及大數(shù)據(jù)技術的不斷發(fā)展，容延遲網(wǎng)絡也將會在氣象數(shù)據(jù)采集、大數(shù)據(jù)前端網(wǎng)絡采集、數(shù)據(jù)挖掘等領域有更多的應用空間[4]。由于DTN網(wǎng)絡在信息傳輸角色中的不可替代性，DTN網(wǎng)絡中的路由算法，節(jié)點覆蓋理論及傳輸安全都逐漸成為DTN研究中的熱點[5-6]。

在城市環(huán)境部署DTN網(wǎng)絡的研究仍然比較少，而在市政建設、車聯(lián)網(wǎng)、電子眼數(shù)據(jù)采集以及大數(shù)據(jù)的數(shù)據(jù)挖掘源等方面，延遲容忍網(wǎng)絡的應用也有廣闊的市場空間，在移動智能終端的應用越來越多的情況下，在城市中的DTN網(wǎng)絡研究不容忽視。來自Nielsen公司的市場研究報告《2013移動消費者報告》顯示，中國在截止2013年3月，智能手機的普及率達到66%。這些都為DTN在城市中的部署創(chuàng)造了良好的條件與機遇。由于城市的場景與大多數(shù)挑戰(zhàn)性網(wǎng)絡特性有所區(qū)別，如節(jié)點密度區(qū)域集中性、POI（Point of Interest）區(qū)域可測性及特殊節(jié)點（如公交車，地鐵）等路徑明確性等，都與其余的DTN網(wǎng)絡部署有一定的區(qū)別[7]?；谝陨系膱鼍疤卣鳎芯磕壳拜^為普遍的直接交付Direct Delivery路由算法與基于概率交付的Prophet路由算法中移動節(jié)點緩存對投遞性能的影響，可以平衡移動節(jié)點資源與投遞性能之間的矛盾，對研究適合城市部署的DTN路由算法具有重要的意義。

2 城市部署中的DTN路由算法

2.1 Direct Delivery算法原理

Direct Delivery算法基于轉發(fā)的策略，在數(shù)據(jù)報文傳輸過程中，節(jié)點不會對報文生成副本，同一ID數(shù)據(jù)包只有唯一一個，算法要求在遇到目標節(jié)點時將報文直接交付給目的節(jié)點，也稱之為Direct Transmission[8]。該算法優(yōu)勢在于由于網(wǎng)絡中副本較少并不存在冗余數(shù)據(jù)包的情況，對節(jié)點的緩存要求相對較少。在Direct Delivery算法下的DTN網(wǎng)絡負載參數(shù)較好。證明網(wǎng)絡負載性能如下：假設其中 表示源節(jié)點數(shù)據(jù)包隨時間均勻產(chǎn)生數(shù)據(jù)包集， 表示到達目的節(jié)點的數(shù)據(jù)包集，其網(wǎng)絡負載β定義由式（1）所示：

其中 表示隨時間節(jié)點數(shù)據(jù)成功建立鏈接并傳輸成功的數(shù)據(jù)包。在Direct Delivery算法中，節(jié)點相遇目標節(jié)點后才能進行數(shù)據(jù)包的發(fā)送，所以 。式（1）也趨近于0，證畢。

在這里考慮對Direct Delivery路由算法的分析，是由于Direct Delivery算法可以直觀的觀測到數(shù)據(jù)的投遞概率，也可以觀測到移動節(jié)點在對唯一緩存要求最少的路由算法中的緩存需求。其中數(shù)據(jù)包投遞率表示數(shù)據(jù)包從源節(jié)點傳送到目的節(jié)點的概率，是DTN網(wǎng)絡中一個重要的指標。若設投遞率w，其w的計算如式（2）所示：

2.2 Prophet路由算法

Prophet算法是基于概率的策略，該類路由算法對報文傳輸成功的概率進行報文傳遞的依據(jù)，與普通的泛洪式傳染路由算法Epidemic相近，但是由于Epidemic泛洪算法數(shù)據(jù)包副本較多，對網(wǎng)絡負載影響較大，這里對Epidemic協(xié)議不做考慮。在Prophet算法協(xié)議中，節(jié)點不盲目的轉發(fā)信息與相遇節(jié)點，而是預先估計其傳輸?shù)侥康墓?jié)點的概率，而判斷是否應該傳輸數(shù)據(jù)包到相遇節(jié)點或存儲數(shù)據(jù)包等待更好的傳輸機會，有效的節(jié)省了傳輸帶寬資源[9]。

在這里算法核心思想引入了一個傳輸預測概率P（a，b），P（a，b）代表節(jié)點a能夠發(fā)送信息到節(jié)點b的概率，當兩個節(jié)點相遇時，節(jié)點a與節(jié)點b將會交換各自的預測向量表，表中包含自身到所有節(jié)點的傳輸預測概率值P（a，b），而P（a，b）隨著時間的增加，會不斷的更新到達其余節(jié)點的P（a，b）值。其P（a，b）由式（3）所示：

其中 的初始化常數(shù)， 為更新周期前的舊傳輸預測概率。在兩個節(jié)點之間的傳輸預測概率隨時間進行指數(shù)級變化，及設定該預測概率值的老化算法，其老化方程如式（4）所示：

其中 表示老化常數(shù)，k表示時間的單位數(shù)，通過老化常數(shù)的引入，保障在節(jié)點隨著t的增加P（a，b）的值滿足指數(shù)衰減，使節(jié)點傳輸過程中有效的降低網(wǎng)絡數(shù)據(jù)包的副本數(shù)。由于城市部署中節(jié)點區(qū)域密度特征，與POI的可預測性，選擇Prophet路由協(xié)議作為研究具有典型意義。

3 移動模型的設計

3.1 主要移動模型

在目標仿真場景中的實驗結論價值的大小，與節(jié)點移動模型密切相關。其中在DTN中討論比較多的主要包括以下幾種：

⑴隨機走動移動模型（Random Walk Mobility），節(jié)點移動選擇隨機方向與隨機速度

⑵隨機路徑點移動模型（Random Waypoint Mobility），基于隨機目標點選擇，利用區(qū)間隨機速率到達目的點，再重新下一目標點。

⑶隨機方向移動模型（Random Direction Mobility Model），節(jié)點在移動到場景邊緣時隨機改變方向與速度。

⑷高斯-馬爾科夫移動模型（Gauss-Markov Mobility Model），利用一個調(diào)整參數(shù)改變節(jié)點隨機等級的移動模型。

⑸基于路徑的移動模型（Pathway Mobility Model），利用地理條件事先設定移動路徑限制節(jié)點的移動，如地圖等。

3.2 WDM移動模型建立

在城市中部署DTN網(wǎng)絡存在對移動模型高度真實的要求，才能夠得到最接近真實情況的節(jié)點投遞性能。所以在節(jié)點移動模型上選擇了由Frans Ekman提出的工作日移動模型。選擇該模型的優(yōu)勢在于充分考慮了節(jié)點的行為習慣特征、由公交移動模型（Bus submodel）、步行子模型（Waiking submodel）等多種子模型的組合使節(jié)點的移動特征更趨于真實情景，所以這里利用工作日模型模擬城市中的DTN部署場景。在城市場景中主要考慮到場景的真實性提高，考慮到節(jié)點在家區(qū)域、辦公區(qū)域、傍晚商場區(qū)域與節(jié)點在源坐標與目的坐標之間的移動模式組建仿真場景。其模型建立如圖1所示：

通過上述的移動模型建立流程，基本可以保障仿真場景移動模型接近真實的移動特征。該模型的構建可以很好的表現(xiàn)每個人在一天的生活現(xiàn)狀，從早上到單位工作，晚上工作完后回家并購物的移動軌跡[10-11]。其中的數(shù)據(jù)文件由OPENJUMP軟件進行繪制數(shù)據(jù)導入為可以表示矢量幾何對象，空間參照系統(tǒng)的文本標記語言WKT（Well-Know Text）。

4 仿真與結果分析

4.1 仿真的參數(shù)條件

在移動模型建立后，利用Opportunistic Networking Environment simulator對仿真場景進行設置并仿真，采用赫爾辛基城市地圖為真實場景地圖文件，模擬在赫爾辛基城市下部署的DTN網(wǎng)絡的移動模型特征與DTN下的Direct Delivery與Prophet算法中節(jié)點緩存大小對投遞效率的影響。由于場景的設置目的是盡可能使仿真接近真實城市特征。場景中節(jié)點數(shù)目設置為100個，仿真目標為攜帶智能終端的行人，每個節(jié)點移動速率符合真實行人的移動速度，100節(jié)點隨機選擇0.8m/s與1.4m/s的速率，由于緩存的設計與數(shù)據(jù)包大小有關，根據(jù)普通的數(shù)據(jù)應用需求，設置數(shù)據(jù)包大小為500k～1M。其他參數(shù)如表1所示：

設置與真實場景近似的重要參數(shù)后，并設置工作地點停滯時間范圍10s～100ks，下班購物時間1小時～2小時。

4.2 場景設置相遇概率分析

為了分析城市中以行人為主體的移動節(jié)點數(shù)據(jù)投遞性能，其移動節(jié)點中的相遇次數(shù)與時間，在算法對投遞率上有較大的影響。由于移動節(jié)點的移動特征，首先對移動節(jié)點的相遇次數(shù)進行統(tǒng)計分析。在DTN網(wǎng)絡中，都是依靠節(jié)點的相遇機會進行數(shù)據(jù)的交換，通過設置每小時計數(shù)節(jié)點相遇次數(shù)，進行仿真分析在WDM下的相遇特征。其相遇的統(tǒng)計數(shù)據(jù)如圖2所示：

通過圖2分析可知，基于城市部署的行人移動節(jié)點，具有在時間條件下相遇概率非均勻性統(tǒng)計特征，由于行人在城市的生活規(guī)律性，導致節(jié)點密集相遇時段與稀疏相遇時段具有較大的差異。從結果也可以看到，節(jié)點相遇概率具有較強的周期性，周期大約為24小時，并且前24小時由于初始化節(jié)點，統(tǒng)計數(shù)據(jù)趨于不穩(wěn)定狀態(tài)。通過相遇概率分析，確定在工作日模型中，仿真時間應該大于48小時，為了充分考慮節(jié)點的緩存影響，仿真時間設定為5天。

4.3 節(jié)點緩存對Direct Delivery算法與Prophet算法的影響

仿真考慮目前移動智能終端緩存的大小設置5M～12M的合理范圍區(qū)間進行仿真，投遞率與緩存的變化情況如圖3所示：

通過圖3分析可以發(fā)現(xiàn)，伴隨移動節(jié)點緩存的增加，其數(shù)據(jù)投遞率增加。并且在投遞指標上Prophet算法優(yōu)于Direct Delivery算法較為明顯。在10M緩存設置上Prophet算法投遞性能達到相對較好的位置，優(yōu)于Direct Delivery算法。其數(shù)據(jù)延遲特征如圖4所示。

從圖5可以分析，伴隨著移動節(jié)點的緩存變大，其延遲也逐漸增加。主要的原因是由于伴隨著節(jié)點緩存的增加，其覆蓋半徑不變的情況下，待投遞數(shù)據(jù)包數(shù)量越來越多的情況下導致數(shù)據(jù)包的延遲增加。所以節(jié)點的緩存大小并不是越大越好。從圖中可以到10M緩存的延遲與11M緩存的延遲有一個較大的跳變，綜合分析圖3，圖4，當數(shù)據(jù)包設計大小為500k～1M的前提下，節(jié)點的緩沖區(qū)設置在10M是最優(yōu)的性能。

5 結束語

通過設置城市中100余個移動節(jié)點，賦予節(jié)點的趨近于真實的移動特征，進行DTN的部署，在對節(jié)點的相遇概率統(tǒng)計與節(jié)點緩存變化對投遞率與平均延遲的分析得出以下結論。⑴城市中行人移動節(jié)點具有一定的規(guī)律性，其相遇概率服具有周期性特征。⑵基于城市部署的DTN網(wǎng)絡中，緩存的增加會導致投遞率的增加。⑶在工作日移動模型WDM中，隨著節(jié)點緩存的增加，由于傳輸半徑一定，會導致傳輸?shù)钠骄舆t增加。⑷在城市中部署的行人作為移動節(jié)點模式下，Prophet算法的投遞性能明顯高于Direct delivery算法。

[參考文獻]

[1]Mundur P，Seligman M.Delay tolerant network routing：Beyond epidemic routing[C].Wireless Pervasive Computing，2008.ISWPC 2008.3rd International Symposium on.IEEE，2008：550-553.

[2]Lu Z，F(xiàn)an J.Delay/disruption tolerant network and its application in military communications[C].Computer Design and Applications （ICCDA），2010 International Conference on.IEEE， 2010，5：231-234.

[3]C?mara D，F(xiàn)rangiadakis N，F(xiàn)ilali F，et al.Vehicular delay tolerant networks[J].Handbook of Research on Mobility and Computing：Evolving Technologies and Ubiquitous Impacts，2011： 356-367.

[4]曹佩，錢江波，陳葉芳，等.基于合并的DTN訂閱查詢傳輸協(xié)議[J].電信科學.2013，29（3）：66-72.

[5]倪辰辰，李千目，姜怡，等.基于輕型機步野戰(zhàn)場景的DTN通信策略設計與性能分析[J].電信科學.2013，29（10）：123-130.

[6]Johnson E，Cruickshank H，Sun Z.Providing Authentication in Delay/Disruption Tolerant Networking （DTN） Environment[M].Personal Satellite Services.Springer Berlin Heidelberg，2013： 189-196.

[7]Yasmeen F，Urushidani S，Yamada S.A probabilistic position-based routing scheme for delay-tolerant networks[C].Computers and Information Technology， 2009.ICCIT'09.12th International Conference on.IEEE，2009：88-93.

[8]孫踐知，劉乃瑞，張迎新，等.機會網(wǎng)絡典型路由算法性能分析[J].計算機工程.2011，37（16）.

[9]Santiago J，Casaca A，Pereira P R.Non-custodial multicast over the dtn-prophet protocol[M].Wireless Sensor and Actor Networks II.Springer US，2008：197-208.

[10]Chowell G，Hyman J M，Eubank S，et al.Scaling laws for the movement of people between locations in a large city[J]. Physical Review E，2003，68（6）：066102.

[11]Ekman F，Ker?nen A，Karvo J，et al.Working day movement model[C].Proceedings of the 1st ACM SIGMOBILE workshop on Mobility models.ACM，2008：33-40.