一種DTN網(wǎng)絡(luò)擺渡節(jié)點(diǎn)存儲(chǔ)分配方案研究

從立鋼，楊華民，王楊惠，底曉強(qiáng)

（1.長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022；2.長春理工大學(xué) 化學(xué)與環(huán)境工程學(xué)院，長春 130022）

一種DTN網(wǎng)絡(luò)擺渡節(jié)點(diǎn)存儲(chǔ)分配方案研究

從立鋼1，楊華民1，王楊惠2，底曉強(qiáng)1

（1.長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022；2.長春理工大學(xué) 化學(xué)與環(huán)境工程學(xué)院，長春 130022）

為提高DTN網(wǎng)絡(luò)性能，針對(duì)擺渡路由算法中擺渡節(jié)點(diǎn)存儲(chǔ)資源分配存在的公平性問題，提出了一種基于加權(quán)最大最小公平原則的擺渡節(jié)點(diǎn)存儲(chǔ)資源的優(yōu)化分配方案。區(qū)別于現(xiàn)有擺渡節(jié)點(diǎn)存儲(chǔ)資源分配所使用的先來先服務(wù)方式，加權(quán)最大最小公平原則可以在保證數(shù)據(jù)節(jié)點(diǎn)在獲得公平的數(shù)據(jù)傳輸機(jī)會(huì)的同時(shí)，為重點(diǎn)任務(wù)提供更多的資源支持。仿真實(shí)驗(yàn)表明，經(jīng)過存儲(chǔ)資源優(yōu)化的擺渡路由算法與現(xiàn)有擺渡路由算法相比較，在網(wǎng)路傳輸成功率、平均網(wǎng)絡(luò)時(shí)延等方面性能均有顯著提高。

延遲容忍網(wǎng)絡(luò)；加權(quán)最大最小公平；擺渡路由算法

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

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

除了以上DTN路由算法之外，還有一類路由算法被稱為擺渡路由算法［8］或數(shù)據(jù)騾子路由算法［3］，該路由算法的基本模式為“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”，在網(wǎng)絡(luò)中專門設(shè)置一類節(jié)點(diǎn)負(fù)責(zé)接收數(shù)據(jù)，并攜帶數(shù)據(jù)到達(dá)目的節(jié)點(diǎn)附近轉(zhuǎn)發(fā)，實(shí)現(xiàn)數(shù)據(jù)的傳遞，這類專門承擔(dān)數(shù)據(jù)“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的節(jié)點(diǎn)被稱為擺渡節(jié)點(diǎn)，對(duì)于此類算法，擺渡節(jié)點(diǎn)的狀態(tài)對(duì)于路由過程的順利進(jìn)行至關(guān)重要。

本文針對(duì)DTN路由節(jié)點(diǎn)的存儲(chǔ)分配方案展開研究，使用加權(quán)最小最大公平原則對(duì)存儲(chǔ)空間進(jìn)行分配，在滿足資源分配公平性的要求同時(shí)提高了重點(diǎn)數(shù)據(jù)的保障水平，通過仿真實(shí)驗(yàn)表明：與先到先服務(wù)分配模型相比較，利用本方案優(yōu)化后的擺渡路由算法在網(wǎng)絡(luò)傳輸成功率、平均時(shí)延等方面均有提高，對(duì)提高DTN網(wǎng)絡(luò)性能作用明顯。

1 基于加權(quán)Max-Min的擺渡節(jié)點(diǎn)緩存分配模型

1.1 網(wǎng)絡(luò)模型

如圖1所示，擺渡節(jié)點(diǎn)在運(yùn)動(dòng)到當(dāng)前位置時(shí)，在其通信范圍內(nèi)有多個(gè)數(shù)據(jù)節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)，其中個(gè)別數(shù)據(jù)節(jié)點(diǎn)數(shù)據(jù)量過大，而當(dāng)前擺渡節(jié)點(diǎn)的內(nèi)存不足以保存所有數(shù)據(jù)發(fā)送要求，就需要考慮其內(nèi)存資源的分配問題。如果對(duì)擺渡節(jié)點(diǎn)內(nèi)存簡單使用“先到先服務(wù)”模型進(jìn)行分配，會(huì)導(dǎo)致部分?jǐn)?shù)據(jù)節(jié)點(diǎn)等待時(shí)間過長問題，甚至?xí)霈F(xiàn)擺渡節(jié)點(diǎn)循環(huán)多次而個(gè)別重要數(shù)據(jù)仍未獲得服務(wù)的情況。

圖1 網(wǎng)絡(luò)模型圖

1.2 擺渡節(jié)點(diǎn)內(nèi)存分配優(yōu)化算法

加權(quán)最大最小公平算法［7］被廣泛應(yīng)用于網(wǎng)絡(luò)路由、流量分配、資源調(diào)度等網(wǎng)絡(luò)通信領(lǐng)域，針對(duì)上一節(jié)中描述的DTN網(wǎng)絡(luò)模型及其遇到的實(shí)際問題，將從優(yōu)化擺渡節(jié)點(diǎn)存儲(chǔ)資源分配入手，使用加權(quán)最大最小公平原則優(yōu)化存儲(chǔ)分配方案，從而降低服務(wù)平均等待時(shí)間，提高網(wǎng)絡(luò)服務(wù)質(zhì)量。

如圖1所示，在擺渡節(jié)點(diǎn)f到達(dá)當(dāng)前位置時(shí)，通信范圍內(nèi)有多個(gè)節(jié)點(diǎn)等待擺渡節(jié)點(diǎn)提供數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)，多個(gè)節(jié)點(diǎn)向百度節(jié)點(diǎn)提交服務(wù)請(qǐng)求數(shù)據(jù)包，經(jīng)過解析后f獲得區(qū)域內(nèi)需要存儲(chǔ)的數(shù)據(jù)總量，如果數(shù)據(jù)總量小于等于f的存儲(chǔ)資源，則為所有節(jié)點(diǎn)提供正常數(shù)據(jù)存儲(chǔ)轉(zhuǎn)發(fā)服務(wù)；如果數(shù)據(jù)總量大于f的存儲(chǔ)資源，則必須對(duì)內(nèi)存空間的分配進(jìn)行優(yōu)化。

為提高該模型的一般性，假設(shè)在擺渡節(jié)點(diǎn)范圍內(nèi)有n個(gè)數(shù)據(jù)節(jié)點(diǎn)，數(shù)據(jù)節(jié)點(diǎn)集合D={d1,…,dn}，數(shù)據(jù)節(jié)點(diǎn)此次會(huì)話的數(shù)據(jù)存儲(chǔ)需求為X={x1,…,xn}，其中x1＜=x1…＜=xn；假設(shè)當(dāng)前擺渡節(jié)點(diǎn)f的剩余存儲(chǔ)空間大小為s，且擺渡節(jié)點(diǎn)與相關(guān)數(shù)據(jù)節(jié)點(diǎn)接觸時(shí)間足夠長，足以完成相關(guān)操作。

假設(shè)n個(gè)數(shù)據(jù)節(jié)點(diǎn)此次會(huì)話的權(quán)重分別為W={w1,…,wn}，權(quán)重代表相關(guān)數(shù)據(jù)節(jié)點(diǎn)的重要程度，也可以理解為相關(guān)會(huì)話的服務(wù)質(zhì)量需求，本文將權(quán)重劃分為10個(gè)等級(jí)，用整數(shù)1到10表示，1表示最低級(jí)別，10表示最高級(jí)別。

基于以上假設(shè)，首先根據(jù)n個(gè)數(shù)據(jù)節(jié)點(diǎn)的權(quán)重對(duì)擺渡節(jié)點(diǎn)f剩余存儲(chǔ)空間進(jìn)行第一輪分配，則擺渡內(nèi)存資源分配情況可以表示為B1={b11,…,b1n}，其中b1i可以用公式（1）表示。

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

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

圖2 擺渡節(jié)點(diǎn)存儲(chǔ)資源分配流程圖

2 算法仿真與分析

本文通過改變擺渡節(jié)點(diǎn)數(shù)量、擺渡節(jié)點(diǎn)存儲(chǔ)空間，觀察網(wǎng)絡(luò)傳輸成功率、網(wǎng)絡(luò)平均時(shí)延兩項(xiàng)重要性能指標(biāo)觀察網(wǎng)絡(luò)狀態(tài)，對(duì)比分析加權(quán)最大最小存儲(chǔ)分配方案與先到先服務(wù)分配方案的性能。

2.1 仿真設(shè)置

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

圖3 仿真網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖

如圖3所示，仿真環(huán)境中設(shè)置三組數(shù)據(jù)節(jié)點(diǎn)，每組40個(gè)節(jié)點(diǎn)圍繞固定點(diǎn)為中心做隨機(jī)運(yùn)動(dòng)。在三組數(shù)據(jù)節(jié)點(diǎn)之間設(shè)置三條路線，若干擺渡節(jié)點(diǎn)按照路線循環(huán)運(yùn)動(dòng)，提供數(shù)據(jù)存儲(chǔ)轉(zhuǎn)發(fā)服務(wù)，擺渡節(jié)點(diǎn)存儲(chǔ)資源分配方案分別采用加權(quán)最大最小算法和先來先服務(wù)算法進(jìn)行存儲(chǔ)資源分配，其他主要仿真參數(shù)如表1所示。

2.2 仿真結(jié)果分析

本文通過修改擺渡節(jié)點(diǎn)存儲(chǔ)資源大小、數(shù)據(jù)包大小、擺渡節(jié)點(diǎn)數(shù)量以及數(shù)據(jù)節(jié)點(diǎn)的數(shù)量，對(duì)比分析加權(quán)最大最小方案和先來先服務(wù)存儲(chǔ)資源分配方案在不同情況下的性能。

（1）擺渡節(jié)點(diǎn)存儲(chǔ)與存儲(chǔ)分配方案性能關(guān)系

表1 主要仿真參數(shù)

本節(jié)研究擺渡節(jié)點(diǎn)存儲(chǔ)資源與擺渡路由算法性能之間的關(guān)系問題。以表1仿真場(chǎng)景為基礎(chǔ)，設(shè)定擺渡節(jié)點(diǎn)數(shù)量為5，通過修改擺渡節(jié)點(diǎn)存儲(chǔ)資源的大小，考察擺渡節(jié)點(diǎn)存儲(chǔ)資源大小對(duì)于不同儲(chǔ)存分配方案性能的影響，實(shí)驗(yàn)結(jié)果如圖4、5所示。

圖4說明，隨著擺渡節(jié)點(diǎn)存儲(chǔ)資源的增加，網(wǎng)絡(luò)傳輸成功率明顯增加。在業(yè)務(wù)需求不變的情況下，當(dāng)內(nèi)存資源增加到一定程度后，網(wǎng)絡(luò)傳輸成功率趨于穩(wěn)定，不再提高。同時(shí)，對(duì)比兩組曲線，采用加權(quán)最大最小存儲(chǔ)資源分配方案的擺渡路由算法在成功率方面要明顯優(yōu)于先到先服務(wù)分配方案。

圖4 擺渡節(jié)點(diǎn)存儲(chǔ)與路由傳輸成功率關(guān)系圖

圖5說明，隨著擺渡節(jié)點(diǎn)存儲(chǔ)不斷增大，采用不同存儲(chǔ)分配方案的路由算法的網(wǎng)絡(luò)平均延時(shí)均明顯降低，其中采用加權(quán)最大最小分配儲(chǔ)存資源的路由算法有明顯優(yōu)于先來先服務(wù)分配方法。

圖5 擺渡節(jié)點(diǎn)存儲(chǔ)與路由平均時(shí)延關(guān)系圖

（2）擺渡節(jié)點(diǎn)數(shù)量與存儲(chǔ)分配算法性能關(guān)系

本節(jié)研究擺渡節(jié)點(diǎn)數(shù)量對(duì)于加權(quán)最大最小分配和先到先服務(wù)兩種分配算法之間的關(guān)系問題。以表1仿真場(chǎng)景為基礎(chǔ)，設(shè)定擺渡節(jié)點(diǎn)存儲(chǔ)資源為50Mb，通過修改擺渡節(jié)點(diǎn)數(shù)量，考察擺渡節(jié)點(diǎn)數(shù)量變化對(duì)于不同儲(chǔ)存分配算法性能的影響，實(shí)驗(yàn)結(jié)果如圖6、7所示。

圖6說明，在網(wǎng)絡(luò)傳輸成功率方面，擺渡節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)傳輸成功率成正比，隨著擺渡節(jié)點(diǎn)的增加，網(wǎng)絡(luò)傳輸成功率增長明顯，同時(shí)，采用加權(quán)最大最小存儲(chǔ)資源分配方案的擺渡路由算法在成功率方面要明顯高于先到先服務(wù)分配方案。

圖6 擺渡節(jié)點(diǎn)數(shù)量與路由傳輸成功率關(guān)系圖

圖7 擺渡節(jié)點(diǎn)數(shù)量與路由平均時(shí)延關(guān)系圖

圖7說明，擺渡節(jié)點(diǎn)的增多對(duì)于降低DTN網(wǎng)絡(luò)平均時(shí)延十分有效，兩種路由算法在網(wǎng)絡(luò)平均延時(shí)均方面降低都很明顯，其中采用加權(quán)最大最小算法優(yōu)化后的路由算法延時(shí)降低更為顯著。

產(chǎn)生以上結(jié)果的原因主要在于：①當(dāng)擺渡節(jié)點(diǎn)數(shù)量一定時(shí)，較大的存儲(chǔ)空間能夠?yàn)楦嗟臄?shù)據(jù)節(jié)點(diǎn)提供服務(wù)，提高網(wǎng)絡(luò)傳輸成功率；②在相同的存儲(chǔ)資源前提下，使用加權(quán)最大最小公平原則分配存儲(chǔ)資源，可以為更多的節(jié)點(diǎn)提供服務(wù)，減少數(shù)據(jù)節(jié)點(diǎn)的平均服務(wù)等待時(shí)間，降低網(wǎng)絡(luò)時(shí)延；③擺渡節(jié)點(diǎn)數(shù)量越多，數(shù)據(jù)節(jié)點(diǎn)獲得服務(wù)的機(jī)會(huì)就越多，DTN網(wǎng)絡(luò)的傳輸成功率和時(shí)延均會(huì)得到相應(yīng)改善。

3 結(jié)論

為提高DTN網(wǎng)絡(luò)中擺渡路由算法的性能，本文從優(yōu)化擺渡節(jié)點(diǎn)存儲(chǔ)資源分配入手，將加權(quán)最大最小公平原則應(yīng)用于存儲(chǔ)分配，與傳統(tǒng)先到先服務(wù)分配方式相比，在網(wǎng)絡(luò)傳輸成功率和平均網(wǎng)絡(luò)時(shí)延方面均有改善，對(duì)于提高DTN網(wǎng)絡(luò)性能作用明顯，優(yōu)化存儲(chǔ)分配是改善網(wǎng)絡(luò)服務(wù)質(zhì)量的一種重要手段。

［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］ 于海洋，楊華民，姜會(huì)林，等.一種全球覆蓋的多層星座鏈路分析［J］.長春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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］ 從立鋼，楊華民，王楊惠，等.基于復(fù)制的DTN網(wǎng)絡(luò)路由算法研究［J］.長春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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”計(jì)劃信息技術(shù)領(lǐng)域課題資助項(xiàng)目（2015AA015701）；吉林省教育廳資助項(xiàng)目（JJKH20170628KJ）

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