節(jié)點(diǎn)緩沖區(qū)大小對城市部署的DTN網(wǎng)絡(luò)的影響分析

李文藻等

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

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

1 引言

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

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

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

2.1 Direct Delivery算法原理

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

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

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

2.2 Prophet路由算法

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

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

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

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

3 移動模型的設(shè)計(jì)

3.1 主要移動模型

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

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

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

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

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

⑸基于路徑的移動模型（Pathway Mobility Model），利用地理?xiàng)l件事先設(shè)定移動路徑限制節(jié)點(diǎn)的移動，如地圖等。

3.2 WDM移動模型建立

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

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

4 仿真與結(jié)果分析

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

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

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

4.2 場景設(shè)置相遇概率分析

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

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

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

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

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

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

5 結(jié)束語

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

[參考文獻(xiàn)]

[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].電信科學(xué).2013，29（3）：66-72.

[5]倪辰辰，李千目，姜怡，等.基于輕型機(jī)步野戰(zhàn)場景的DTN通信策略設(shè)計(jì)與性能分析[J].電信科學(xué).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ī)會網(wǎng)絡(luò)典型路由算法性能分析[J].計(jì)算機(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.