一種DTN網絡擺渡節點存儲分配方案研究

從立鋼，楊華民，王楊惠，底曉強

（1.長春理工大學 計算機科學技術學院，長春 130022；2.長春理工大學 化學與環境工程學院，長春 130022）

一種DTN網絡擺渡節點存儲分配方案研究

從立鋼1，楊華民1，王楊惠2，底曉強1

（1.長春理工大學 計算機科學技術學院，長春 130022；2.長春理工大學 化學與環境工程學院，長春 130022）

為提高DTN網絡性能，針對擺渡路由算法中擺渡節點存儲資源分配存在的公平性問題，提出了一種基于加權最大最小公平原則的擺渡節點存儲資源的優化分配方案。區別于現有擺渡節點存儲資源分配所使用的先來先服務方式，加權最大最小公平原則可以在保證數據節點在獲得公平的數據傳輸機會的同時，為重點任務提供更多的資源支持。仿真實驗表明，經過存儲資源優化的擺渡路由算法與現有擺渡路由算法相比較，在網路傳輸成功率、平均網絡時延等方面性能均有顯著提高。

延遲容忍網絡；加權最大最小公平；擺渡路由算法

DTN［1］概念最早由DTNRG（Delay Tolerant Network Research Group，延遲容忍網絡研究組）在2003年提出，試圖通過DTN網絡來解決星際網絡頻繁中斷、時延大的問題。同年，在SIGCOMM國際會議上，Kevin Fall發表了著名論文“A Delay-Tolerant Network Architecture for Challenged In?ternets”，該文章成為了DTN網絡研究領域的經典。目前，DTN被廣泛應用在農業網絡［4］、星際網絡［5］、野生動物研究［6］等多方面。

做為一種新型的網絡形式，DTN尚有很多方面并不完善，需要進行深入研究，其中路由技術是當前的研究熱點之一。目前，經典的DTN路由算法有Epidemic算法、PROPHET算法、Spray and Wait算法以及MaxProp算法等。Epidemic傳染機制算法中，每個節點都將消息副本復制給相遇節點，但由于節點能量和緩存受限，容易造成消息的大量重傳和丟棄，網絡開銷大［9］；PROPHET算法根據節點運動的規律，利用歷史相遇信息預測到達目的節點的概率，將消息復制給完成數據傳遞概率更大的節點，從而限制了消息副本的數量，降低了網絡資源消耗［10］；Spray and Wait算法限制消息轉發的上限數目n，這種機制避免產生過多的消息，從而造成網絡開銷的爆發式增長［11］；MaxProp路由算法引入了優先級對數據進行標記，優先級高的數據先發送，同樣優先級低的數據先刪除，這樣大大提高了節點資源的利用率［12］。

除了以上DTN路由算法之外，還有一類路由算法被稱為擺渡路由算法［8］或數據騾子路由算法［3］，該路由算法的基本模式為“存儲-攜帶-轉發”，在網絡中專門設置一類節點負責接收數據，并攜帶數據到達目的節點附近轉發，實現數據的傳遞，這類專門承擔數據“存儲-攜帶-轉發”的節點被稱為擺渡節點，對于此類算法，擺渡節點的狀態對于路由過程的順利進行至關重要。

本文針對DTN路由節點的存儲分配方案展開研究，使用加權最小最大公平原則對存儲空間進行分配，在滿足資源分配公平性的要求同時提高了重點數據的保障水平，通過仿真實驗表明：與先到先服務分配模型相比較，利用本方案優化后的擺渡路由算法在網絡傳輸成功率、平均時延等方面均有提高，對提高DTN網絡性能作用明顯。

1 基于加權Max-Min的擺渡節點緩存分配模型

1.1 網絡模型

如圖1所示，擺渡節點在運動到當前位置時，在其通信范圍內有多個數據節點需要發送數據，其中個別數據節點數據量過大，而當前擺渡節點的內存不足以保存所有數據發送要求，就需要考慮其內存資源的分配問題。如果對擺渡節點內存簡單使用“先到先服務”模型進行分配，會導致部分數據節點等待時間過長問題，甚至會出現擺渡節點循環多次而個別重要數據仍未獲得服務的情況。

圖1 網絡模型圖

1.2 擺渡節點內存分配優化算法

加權最大最小公平算法［7］被廣泛應用于網絡路由、流量分配、資源調度等網絡通信領域，針對上一節中描述的DTN網絡模型及其遇到的實際問題，將從優化擺渡節點存儲資源分配入手，使用加權最大最小公平原則優化存儲分配方案，從而降低服務平均等待時間，提高網絡服務質量。

如圖1所示，在擺渡節點f到達當前位置時，通信范圍內有多個節點等待擺渡節點提供數據轉發服務，多個節點向百度節點提交服務請求數據包，經過解析后f獲得區域內需要存儲的數據總量，如果數據總量小于等于f的存儲資源，則為所有節點提供正常數據存儲轉發服務；如果數據總量大于f的存儲資源，則必須對內存空間的分配進行優化。

為提高該模型的一般性，假設在擺渡節點范圍內有n個數據節點，數據節點集合D={d1,…,dn}，數據節點此次會話的數據存儲需求為X={x1,…,xn}，其中x1＜=x1…＜=xn；假設當前擺渡節點f的剩余存儲空間大小為s，且擺渡節點與相關數據節點接觸時間足夠長，足以完成相關操作。

假設n個數據節點此次會話的權重分別為W={w1,…,wn}，權重代表相關數據節點的重要程度，也可以理解為相關會話的服務質量需求，本文將權重劃分為10個等級，用整數1到10表示，1表示最低級別，10表示最高級別。

基于以上假設，首先根據n個數據節點的權重對擺渡節點f剩余存儲空間進行第一輪分配，則擺渡內存資源分配情況可以表示為B1={b11,…,b1n}，其中b1i可以用公式（1）表示。

完成第一輪存儲空間分配后，將數據節點需求量xi與內存分配量bi相比較，如果bi等于xi，則節點ni獲得存儲空間bi；如果bi大于xi，則分配給節點ni存儲空間xi，并收回超出部分；如果bi小于xi，則分得存儲空間bi，同時節點ni參與下一輪存儲空間分配，第一輪數據節點獲得存儲資源如公式（2）所示。

經過第一輪存儲資源分配，假設此時擺渡節點內剩余的存儲資源為s1，尚有k個節點未獲得其所需的全部存儲資源，接下來重復利用公式（1）和（2）進行第二輪存儲資源分配，如果經過第二輪分配后尚未滿足所有數據節點對存儲資源的需求且擺渡節點剩余存儲資源不為零，則繼續重復以上步驟進行資源分配，直至資源分配結束或所有數據節點存儲資源需求均被滿足為止，具體過程如圖2所示。

圖2 擺渡節點存儲資源分配流程圖

2 算法仿真與分析

本文通過改變擺渡節點數量、擺渡節點存儲空間，觀察網絡傳輸成功率、網絡平均時延兩項重要性能指標觀察網絡狀態，對比分析加權最大最小存儲分配方案與先到先服務分配方案的性能。

2.1 仿真設置

本文所使用的仿真工具為ONE［13］，該工具由芬蘭赫爾辛基阿爾托大學的AriKer?nen和J?rg Ott等人利用Java編程語言開發，可以在Windows、Linux等多平臺上運行。

圖3 仿真網絡拓撲結構示意圖

如圖3所示，仿真環境中設置三組數據節點，每組40個節點圍繞固定點為中心做隨機運動。在三組數據節點之間設置三條路線，若干擺渡節點按照路線循環運動，提供數據存儲轉發服務，擺渡節點存儲資源分配方案分別采用加權最大最小算法和先來先服務算法進行存儲資源分配，其他主要仿真參數如表1所示。

2.2 仿真結果分析

本文通過修改擺渡節點存儲資源大小、數據包大小、擺渡節點數量以及數據節點的數量，對比分析加權最大最小方案和先來先服務存儲資源分配方案在不同情況下的性能。

（1）擺渡節點存儲與存儲分配方案性能關系

表1 主要仿真參數

本節研究擺渡節點存儲資源與擺渡路由算法性能之間的關系問題。以表1仿真場景為基礎，設定擺渡節點數量為5，通過修改擺渡節點存儲資源的大小，考察擺渡節點存儲資源大小對于不同儲存分配方案性能的影響，實驗結果如圖4、5所示。

圖4說明，隨著擺渡節點存儲資源的增加，網絡傳輸成功率明顯增加。在業務需求不變的情況下，當內存資源增加到一定程度后，網絡傳輸成功率趨于穩定，不再提高。同時，對比兩組曲線，采用加權最大最小存儲資源分配方案的擺渡路由算法在成功率方面要明顯優于先到先服務分配方案。

圖4 擺渡節點存儲與路由傳輸成功率關系圖

圖5說明，隨著擺渡節點存儲不斷增大，采用不同存儲分配方案的路由算法的網絡平均延時均明顯降低，其中采用加權最大最小分配儲存資源的路由算法有明顯優于先來先服務分配方法。

圖5 擺渡節點存儲與路由平均時延關系圖

（2）擺渡節點數量與存儲分配算法性能關系

本節研究擺渡節點數量對于加權最大最小分配和先到先服務兩種分配算法之間的關系問題。以表1仿真場景為基礎，設定擺渡節點存儲資源為50Mb，通過修改擺渡節點數量，考察擺渡節點數量變化對于不同儲存分配算法性能的影響，實驗結果如圖6、7所示。

圖6說明，在網絡傳輸成功率方面，擺渡節點數量與網絡傳輸成功率成正比，隨著擺渡節點的增加，網絡傳輸成功率增長明顯，同時，采用加權最大最小存儲資源分配方案的擺渡路由算法在成功率方面要明顯高于先到先服務分配方案。

圖6 擺渡節點數量與路由傳輸成功率關系圖

圖7 擺渡節點數量與路由平均時延關系圖

圖7說明，擺渡節點的增多對于降低DTN網絡平均時延十分有效，兩種路由算法在網絡平均延時均方面降低都很明顯，其中采用加權最大最小算法優化后的路由算法延時降低更為顯著。

產生以上結果的原因主要在于：①當擺渡節點數量一定時，較大的存儲空間能夠為更多的數據節點提供服務，提高網絡傳輸成功率；②在相同的存儲資源前提下，使用加權最大最小公平原則分配存儲資源，可以為更多的節點提供服務，減少數據節點的平均服務等待時間，降低網絡時延；③擺渡節點數量越多，數據節點獲得服務的機會就越多，DTN網絡的傳輸成功率和時延均會得到相應改善。

3 結論

為提高DTN網絡中擺渡路由算法的性能，本文從優化擺渡節點存儲資源分配入手，將加權最大最小公平原則應用于存儲分配，與傳統先到先服務分配方式相比，在網絡傳輸成功率和平均網絡時延方面均有改善，對于提高DTN網絡性能作用明顯，優化存儲分配是改善網絡服務質量的一種重要手段。

［1］ Burleigh S，Hooke A，Torgerson L，et al.Delay-toler?ant networking：an approach to interplanetary Internet［J］.Communications Magazine，IEEE，2003，41（6）：128-136.

［2］ Cerf V，Burleigh S，Hooke A，et al.RFC 4838：Delaytolerant networking architecture［S］.USA：IETF，2007.

［3］ Fall K.A delay-tolerant network architecture for chal?lenged internets，ACM SIGCOMM’03［C］.New York：ACM，2003.

［4］ Ochiai H，Ishizuka H，Kawakami Y，et al.A dtn-based sensor data gathering for agricultural applications［J］. IEEE Sensors Journal，2011，11（11）：2861-2868.

［5］ 于海洋，楊華民，姜會林，等.一種全球覆蓋的多層星座鏈路分析［J］.長春理工大學學報：自然科學版，2014，37（3）：56-59.

［6］ Juang P，Oki H，Yong W，et al.Energy-efficient com?puting for wildlife tracking：design tradeoffs and early experiences with ZebraNet［J］.Acm Sigops Operating Systems Review，2002，36（5）：96-107.

［7］ Nace D，Pioro M.Max-min fairness and its applications to routing and load-balancing in communication net?works：a tutorial［J］.Communications Surveys&Tutori?als IEEE，2008，10（4）：4-17.

［8］ Zhao W.A message ferrying approach for data delivery in sparse mobile Ad Hoc networks［C］.In Proc.5th ACM，2004：187-198.

［9］ Vahdat A，Becker D.Epidemic routing for partially con?nected ad hoc networks［R］.Technical Report CS-200006，Duke University，2000.

［10］ Lindgren A，Doria A，Schel O.Probabilistic routing in intermittently connected networks［J］.SIGMOBILE Mob.Comput.Commun.Rev，2003，7（3）：19-20.

［11］ Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait：an efficient routing scheme for intermittently connected mobile networks，ACM SIGCOMM 2005［C］.Philadelphia：ACM，2005.

［12］ Burgess J，Gallagher B，Jensen D，et al.MaxProp：Routing for vehicle-based disruption-tolerant net?works［C］.Proceedings-IEEE INFOCOM’15，Hong Kong：IEEE，2015.

［13］ Ari Ker?nen，J?rg Ott，Teemu K?rkk?inen.The ONE simulator for DTN protocol evaluation［C］.SIMU?Tools'09：2nd International Conference on Simulation Tools and Techniques.Rome：March 2009.

［14］ 從立鋼，楊華民，王楊惠，等.基于復制的DTN網絡路由算法研究［J］.長春理工大學學報：自然科學版，2016，39（4）：119-124.

Research on a Storage Allocation Schema for DTN Ferry Node

CONG Ligang1，YANG Huamin1，WANG Yanghui2，DI Xiaoqiang1
（1.School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022；2.School of Chemistry and Environmental Engineering，Changchun University of Science and Technology，Changchun 130022）

In order to improve the performance of DTN network and address the problem of fairness in the allocation of storage re?sources of ferry nodes in ferry routing algorithm.We propose an optimal allocation scheme based on the weighted max min fair?ness.Different from the existing ferry node storage resources allocation by using the first come first service，the weighted max min fairness principle can provide more resource support for the key tasks while ensuring the fair data transmission opportunities.The simulation results show that the performance of the proposed algorithm is better than that of the existing ferry routing algorithm，the network transmission success rate and average network delay and other aspects of performance have been significantly im?proved.

DTN；weighted max-min fairness；ferry routing algorithm

TP393

A

1672-9870（2017）03-0117-05

2017-04-11

“863”計劃信息技術領域課題資助項目（2015AA015701）；吉林省教育廳資助項目（JJKH20170628KJ）

從立鋼（1983-），男，博士，講師，E-mail：clg_cust@126.com