節點緩沖區大小對城市部署的DTN網絡的影響分析

李文藻等

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

關鍵詞：容延遲網絡；節點緩存；數據投遞率；工作日模型； 路由算法

1 引言

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

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

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

2.1 Direct Delivery算法原理

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

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

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

2.2 Prophet路由算法

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

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

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

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

3 移動模型的設計

3.1 主要移動模型

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

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

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

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

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

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

3.2 WDM移動模型建立

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

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

4 仿真與結果分析

4.1 仿真的參數條件

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

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

4.2 場景設置相遇概率分析

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

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

4.3 節點緩存對Direct Delivery算法與Prophet算法的影響

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

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

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

5 結束語

通過設置城市中100余個移動節點，賦予節點的趨近于真實的移動特征，進行DTN的部署，在對節點的相遇概率統計與節點緩存變化對投遞率與平均延遲的分析得出以下結論。⑴城市中行人移動節點具有一定的規律性，其相遇概率服具有周期性特征。⑵基于城市部署的DTN網絡中，緩存的增加會導致投遞率的增加。⑶在工作日移動模型WDM中，隨著節點緩存的增加，由于傳輸半徑一定，會導致傳輸的平均延遲增加。⑷在城市中部署的行人作為移動節點模式下，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，Fan 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，Frangiadakis N，Filali 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訂閱查詢傳輸協議[J].電信科學.2013，29（3）：66-72.

[5]倪辰辰，李千目，姜怡，等.基于輕型機步野戰場景的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]孫踐知，劉乃瑞，張迎新，等.機會網絡典型路由算法性能分析[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.