延遲容忍網(wǎng)絡(luò)能量受限的路由控制策略

吳亞輝，鄧 蘇，黃宏斌

?

延遲容忍網(wǎng)絡(luò)能量受限的路由控制策略

吳亞輝，鄧 蘇，黃宏斌

(國防科技大學(xué)信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 長沙 410073)

延遲容忍網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接模式可以用Edge-Markovian模型描述，該模型優(yōu)于傳統(tǒng)的負(fù)指數(shù)模型。該文基于Edge-Markovian模型研究有限能量約束下two-hop算法的最優(yōu)控制問題。為了降低能量消耗，采用概率two-hop算法，信息源在每個(gè)通信機(jī)會(huì)以一定概率決定是否發(fā)送信息，問題轉(zhuǎn)化為選擇合適的概率在滿足能量約束的前提下最大化傳輸成功率。利用離散時(shí)間Markov過程對問題進(jìn)行建模，并從理論上證明最優(yōu)概率是閾值形式。仿真及數(shù)值結(jié)果證明了模型的有效性。

延遲容忍網(wǎng)絡(luò); Edge-Markovian模型; Markov過程; 最優(yōu)控制; two-hop算法

在移動(dòng)自組網(wǎng)(mobile Ad hoc networks, MANETs)領(lǐng)域，節(jié)點(diǎn)高速移動(dòng)、節(jié)點(diǎn)稀疏、交替活躍及惡意攻擊等因素造成網(wǎng)絡(luò)在很多情況下不連通，具有間歇連通的特點(diǎn)。這會(huì)導(dǎo)致節(jié)點(diǎn)對之間由于不存在通信路徑而無法及時(shí)傳輸信息。所以，以上應(yīng)用必須能夠容忍一定程度的延遲，這類網(wǎng)絡(luò)統(tǒng)稱為延遲容忍網(wǎng)(delay tolerant network，DTN)[1]。由于傳統(tǒng)MANETs路由策略的研究一般假設(shè)底層網(wǎng)絡(luò)是連通的，即任意收發(fā)節(jié)點(diǎn)對在傳輸數(shù)據(jù)之前存在一條完整的通信路徑，這些算法無法直接應(yīng)用于DTN。

為了在不連通網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)傳輸，節(jié)點(diǎn)需要把消息存儲(chǔ)起來，并跟著自身的移動(dòng)隨身攜帶，直到遇到目的節(jié)點(diǎn)完成傳輸，在此過程中節(jié)點(diǎn)可能需要把消息轉(zhuǎn)發(fā)或復(fù)制到其他非目的節(jié)點(diǎn)上以提高路由效率，事實(shí)上，這也是DTN路由策略的核心，這種方式稱為存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)工作模式。目前，DTN路由策略主要分為副本受限算法及副本非受限算法兩類。副本受限算法是指算法最多產(chǎn)生個(gè)副本，當(dāng)副本數(shù)達(dá)到時(shí)，只能向目的節(jié)點(diǎn)發(fā)送信息。這類算法中最簡單的是直接傳輸(direct transmission，DT)[2]，在該策略中，信息源只向目的節(jié)點(diǎn)發(fā)送消息，中間不經(jīng)過任何轉(zhuǎn)發(fā)，即=1，因此其延遲非常大，傳輸成功率也很低。為了提高效率，人們考慮提高的值，采用多副本策略，這類算法的核心是個(gè)副本如何傳播，最早有噴射等待(spray and wait, SW)[3]算法，SW采用二分法，此后出現(xiàn)了一系列改進(jìn)[4-5]。這些算法的本質(zhì)是盡量利用傳播能力強(qiáng)的節(jié)點(diǎn)來提高傳播效率。副本非受限算法是指沒有明確限定能夠產(chǎn)生多少副本的算法，最基礎(chǔ)的是泛洪(flooding)。在泛洪策略中，攜帶消息的節(jié)點(diǎn)每次遇到?jīng)]有攜帶消息的節(jié)點(diǎn)都把消息進(jìn)行轉(zhuǎn)發(fā)(不管是不是目的節(jié)點(diǎn))，顯然這種策略冗余非常大且需要耗費(fèi)大量的節(jié)點(diǎn)能量。為了提高效率，文獻(xiàn)[6-8]提出了把消息盡可能轉(zhuǎn)發(fā)到最有可能完成消息傳輸?shù)墓?jié)點(diǎn)上，從而在保證效率的前提下降低消息副本量。這些算法雖然效率較高，但計(jì)算量較大且需要額外的空間來存儲(chǔ)計(jì)算所需的信息，為此，人們提出了一些計(jì)算量較小且性能不錯(cuò)的算法，如two-hop算法。該算法允許信息源向任何節(jié)點(diǎn)發(fā)送消息，而其他攜帶消息的節(jié)點(diǎn)只能向目的節(jié)點(diǎn)發(fā)送消息。two-hop算法雖然通過限制轉(zhuǎn)發(fā)節(jié)點(diǎn)降低了資源消耗，但信息源仍可能產(chǎn)生大量副本，在能量受限的情況下會(huì)帶來問題。因此，在有限的資源消耗約束下如何提高信息分發(fā)的效率是two-hop算法研究的重點(diǎn)，這也是本文要解決的主要問題。值得說明的是，對于副本受限算法，當(dāng)達(dá)到最大副本量時(shí)，消息也可能會(huì)進(jìn)一步在網(wǎng)絡(luò)中傳輸，只是此時(shí)轉(zhuǎn)發(fā)消息的節(jié)點(diǎn)需要?jiǎng)h除自己所存儲(chǔ)的副本。從這個(gè)意義上講，之前講到的發(fā)送或轉(zhuǎn)發(fā)都等同于復(fù)制，本文也采用同樣的概念。

目前針對two-hop算法的優(yōu)化控制問題已經(jīng)有了一定的研究。文獻(xiàn)[9]采用離散時(shí)間Markov模型研究了two-hop算法最優(yōu)控制問題。文獻(xiàn)[10]采用連續(xù)時(shí)間Markov過程進(jìn)一步深入研究、探討了動(dòng)態(tài)概率傳輸策略。文獻(xiàn)[11-12]分別探討了異構(gòu)節(jié)點(diǎn)及存在惡意節(jié)點(diǎn)情況下的最優(yōu)控制問題。以上研究都假設(shè)網(wǎng)絡(luò)模型服從負(fù)指數(shù)分布，雖然這一假設(shè)在一些人工數(shù)據(jù)集如Random Waypoint中成立，但它無法描述節(jié)點(diǎn)之間邊動(dòng)態(tài)變化的依賴關(guān)系。文獻(xiàn)[13]指出這一點(diǎn)在真實(shí)網(wǎng)絡(luò)中普遍存在并且提出了Edge-Markov模型，探討了Edge-Markov模型中Flooding算法的執(zhí)行時(shí)間問題。文獻(xiàn)[14]針對文獻(xiàn)[13]模型探討了消息大小對泛洪算法的影響。但目前還沒有基于Edge-Markov模型對路由算法進(jìn)行最優(yōu)控制的研究。本文主要貢獻(xiàn)概括如下：1) 基于Edge-Markov模型，采用離散時(shí)間Markov過程來建模two-hop算法；2) 針對上述模型，從理論上證明最優(yōu)概率服從閾值形式，任何非閾值形式的發(fā)送策略都不可能是最優(yōu)策略；3) 仿真及數(shù)值結(jié)果證明了理論的正確性。

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

假設(shè)網(wǎng)絡(luò)中有+1個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)稱為目的節(jié)點(diǎn)，前個(gè)節(jié)點(diǎn)可以產(chǎn)生消息。簡單起見，假設(shè)其中的一個(gè)節(jié)點(diǎn)(稱為信息源)產(chǎn)生消息，其他-1個(gè)節(jié)點(diǎn)稱為中轉(zhuǎn)節(jié)點(diǎn)。采用離散時(shí)間模型，每個(gè)時(shí)間間隔(稱為時(shí)隙)為，第個(gè)時(shí)隙是指時(shí)間區(qū)間[,(+1)]。信息源在第一個(gè)時(shí)隙開始產(chǎn)生消息，的最大生存周期為(個(gè)時(shí)隙)。對于任意兩個(gè)節(jié)點(diǎn)和，它們之間的邊為e。e=1表示節(jié)點(diǎn)和處于連接狀態(tài)，可以相互通信；e=0意味著二者處于斷開狀態(tài)。網(wǎng)絡(luò)中任何一條邊的狀態(tài)轉(zhuǎn)換關(guān)系如圖1所示[15]。

圖1 邊的狀態(tài)轉(zhuǎn)換圖

上述轉(zhuǎn)換是一個(gè)2狀態(tài)的馬爾科夫過程，存在穩(wěn)定分布，因此有：

式中，0和1分別是在穩(wěn)定狀態(tài)邊處于斷開及連通狀態(tài)的概率。從式(1)可以得到：

(2)

本文采用概率two-hop算法，即信息源在每次遇到中轉(zhuǎn)節(jié)點(diǎn)時(shí)不是絕對發(fā)送，而是以一定概率進(jìn)行發(fā)送，以()表示在第個(gè)時(shí)隙所采取的概率。該概率可稱為發(fā)送概率或發(fā)送策略，它是一個(gè)隨機(jī)序列[9]，在任意時(shí)刻都可以看做一個(gè)隨機(jī)變量，如在第個(gè)時(shí)隙，()就是隨機(jī)變量，可以在[0,1]中任意取值。下面首先給出閾值概率的定義。

定義 1 如果存在一個(gè)正常數(shù)，在<時(shí)，()=1；在=時(shí)，()=(0≤<1)；在>時(shí)，()=0，則稱為閾值概率。

需要注意的是，這里的發(fā)送概率主要是指信息源與中轉(zhuǎn)節(jié)點(diǎn)之間的發(fā)送概率。而任何攜帶消息的節(jié)點(diǎn)(包含)都以概率1向目的節(jié)點(diǎn)發(fā)送消息。

2 系統(tǒng)建模

假設(shè)在第個(gè)時(shí)隙末攜帶消息的節(jié)點(diǎn)數(shù)為()，(())表示對應(yīng)的期望值。進(jìn)一步假設(shè)每一個(gè)接受消息的節(jié)點(diǎn)只能在下一時(shí)隙才能進(jìn)行轉(zhuǎn)發(fā)，且消息足夠小從而能夠在一個(gè)時(shí)隙內(nèi)完成傳輸，顯然(0)=1。因?yàn)槁酚刹呗缘哪芰肯呐c轉(zhuǎn)發(fā)次數(shù)成正比，為簡單起見，直接利用轉(zhuǎn)發(fā)次數(shù)作為能量消耗的指標(biāo)[9-12]。采用類似的方法，即用()表示從時(shí)刻0到第個(gè)時(shí)隙總共消耗的能量值。令()表示在第個(gè)時(shí)隙傳輸成功的概率(目的節(jié)點(diǎn)得到消息)。如果限定為傳輸一條消息，允許消耗的最大能量為，則存在問題：

上述優(yōu)化問題是指在有限的能量約束條件下最大化傳輸成功率。()的演化規(guī)律為：

(4)

式中，()是在第個(gè)時(shí)隙沒有攜帶消息的節(jié)點(diǎn)集合，且滿足|()|=-()；代表事件節(jié)點(diǎn)在時(shí)間區(qū)間[(1),(2)]是否接收到消息，值為1則代表成功收到消息，其表達(dá)式對于不同的發(fā)送策略是不同的。對于閾值概率有：

當(dāng)>時(shí)，其發(fā)送概率為0，因此得到消息的概率為0；在<時(shí)，由于發(fā)送概率為1，節(jié)點(diǎn)在第個(gè)時(shí)隙沒有得到消息，說明此時(shí)邊處于斷開狀態(tài)。因此，如果在第+1個(gè)時(shí)隙節(jié)點(diǎn)要得到消息，必須從0變?yōu)?，這一概率為，所以式(6)成立。當(dāng)=時(shí)，由于上一時(shí)隙發(fā)送概率為1，可知值為p。

根據(jù)式(4)可以得到()的期望值為：

進(jìn)一步可以得到：

(8)

對于目的節(jié)點(diǎn)，如果它在第(>1)個(gè)時(shí)隙(當(dāng)=1時(shí)，只有能滿足，此概率為1)得到消息，且在此之前沒有得到，則此概率為：

式中，()代表在第個(gè)時(shí)隙得到消息的節(jié)點(diǎn)集合，且滿足|()|=()；p(1,)代表目的節(jié)點(diǎn)在第個(gè)時(shí)隙從節(jié)點(diǎn)得到消息。對于(2)中的節(jié)點(diǎn)，它們在第-2個(gè)時(shí)隙已經(jīng)得到消息，所以如果在第-1個(gè)時(shí)隙與它們相遇，則即可得到信息，因此如果沒有得到信息，就可以知道與(2)中的節(jié)點(diǎn)在第-1個(gè)時(shí)隙處于斷開狀態(tài)。進(jìn)一步，如果在第個(gè)時(shí)隙仍沒有得到信息，則與它們中的任何一個(gè)節(jié)點(diǎn)之間的邊仍然處于斷開狀態(tài)(即在狀態(tài)0保持不變)，滿足p(1,)=。在第-1個(gè)時(shí)隙得到消息的節(jié)點(diǎn)集合可以表示為(-1)(2)，由于這些節(jié)點(diǎn)剛剛得到信息，則無法在本時(shí)隙內(nèi)進(jìn)一步把信息轉(zhuǎn)發(fā)到其他節(jié)點(diǎn)，所以即使這些節(jié)點(diǎn)在第-1個(gè)時(shí)隙與處于連接狀態(tài)，仍無法從它們得到信息，因此它們之間的邊在第-1個(gè)時(shí)隙可以處于任何狀態(tài)，所以在時(shí)刻沒有得到信息的概率為0。

為了計(jì)算()，本文借鑒文獻(xiàn)[9]中的方法，令()=1-()，則有：

進(jìn)一步可以得到：

(11)

3 最優(yōu)控制策略

對于閾值概率，結(jié)合式(6)和式(8)，有：

根據(jù)定理1，可以得出最優(yōu)閾值概率。

定理1 最優(yōu)閾值h存在。

1)=1，sum((1))，如果sum，轉(zhuǎn)步驟2)，否則h=-1，進(jìn)一步根據(jù)式(12)可以得出()的值；

2)=+1，sum(())，如果sum，轉(zhuǎn)步驟2)，否則h=-1，進(jìn)一步根據(jù)式(12)可以得出()的值。如果=+1，則h=+1。

下面證明最優(yōu)概率是閾值形式。在證明之前，先給出隨機(jī)序列的相關(guān)定理。

定理2[9]給定兩個(gè)隨機(jī)序列1和2，則1小于2，記作1st2，如果它們滿足1()≤2()，≥0；且至少存在一個(gè)常數(shù)≥0，1)2()。

設(shè)()是隨機(jī)序列的函數(shù)，如果兩個(gè)隨機(jī)變量1st2且(1)(2)，則()是隨機(jī)序列的遞增函數(shù)。

定理3 最優(yōu)概率是閾值形式。

證明：顯然，發(fā)送概率是隨機(jī)序列，而(())是對應(yīng)的隨機(jī)函數(shù)，令(())表示發(fā)送概率p對應(yīng)的(())。給定兩個(gè)發(fā)送概率1和2，其在第個(gè)時(shí)隙對應(yīng)的值分別為1()和2()。存在一個(gè)常數(shù)，滿足：≠，1()=2()，=，1()>2()，0<≤。從定理3可知2st1。下面證明(())是發(fā)送概率的遞增函數(shù)。以ζ()代表節(jié)點(diǎn)從時(shí)刻0到第個(gè)時(shí)隙是否得到消息的指示變量，為1則指已經(jīng)得到消息；為0則表示沒有得到消息，因此有：

式中，參數(shù)τ()代表節(jié)點(diǎn)在第個(gè)時(shí)隙是否得到消息的指示量。值得注意的是，該參數(shù)的取值與節(jié)點(diǎn)在此之前是否得到消息無關(guān)。因此對應(yīng)發(fā)送策略1滿足：

(14)

式中，p()代表節(jié)點(diǎn)與在第個(gè)時(shí)隙是否相遇，它只與節(jié)點(diǎn)運(yùn)動(dòng)規(guī)律有關(guān)，而與發(fā)送概率無關(guān)。因此，對應(yīng)發(fā)送策略2有：

對式(13)取期望，可以得到：

(16)

進(jìn)一步有：

結(jié)合式(14)～式(17)，就可以知道(())是發(fā)送概率的單調(diào)遞增函數(shù)。下面對定理進(jìn)行證明。

假設(shè)最優(yōu)閾值概率為1，其對應(yīng)的閾值為h，且滿足<h，()=1，=h，()=h<≤，()=0。當(dāng)h=+1時(shí)，發(fā)送概率總為1，因此是最優(yōu)概率。下面討論h≤的情形，給定另一個(gè)不同于1的發(fā)送策略2。假設(shè)存在常數(shù)≤h，且滿足1()≥2()，<;1()>2()；1()≥2()，<≤h。則發(fā)送概率在[0,]時(shí)隙內(nèi)滿足2≤st1，[, h]時(shí)隙內(nèi)滿足2st1。因此有(())≤(())，0≤<。當(dāng)≤≤*時(shí)，有(())<(())。當(dāng)>*時(shí)，根據(jù)定理2，(())已經(jīng)達(dá)到最大值，因此(())≤(())同樣成立。根據(jù)式(11)，可知最優(yōu)閾值概率1優(yōu)于2。假設(shè)常數(shù)不存在，則滿足1()=2()，≤h，且至少存在一個(gè)值1>h且滿足1()=0<2()；否則2st1。顯然，此時(shí)2st1，由于E(())是發(fā)送概率的單調(diào)遞增函數(shù)，結(jié)合定理1，則有((1))>(1))>。這違背了約束條件，因此最優(yōu)閾值概率始終是最優(yōu)概率。

4 性能分析

4.1 仿真實(shí)驗(yàn)

首先，采用機(jī)會(huì)網(wǎng)絡(luò)仿真平臺(tái)(opportunistic network environment simulator, ONE)驗(yàn)證理論模型的正確性。因?yàn)椴蓸又芷谠介L，連接失敗及短連接時(shí)間的邊消失的概率就越大[15]，這要求數(shù)據(jù)集具有較短的采樣周期，本文選用Rollernet數(shù)據(jù)集[16]，其采樣周期約為12 s，比傳統(tǒng)的Reality Mining[17]的600 s及Infocom 2005[18]的120 s都要短。利用前3 000 s的數(shù)據(jù)，并且選取60個(gè)節(jié)點(diǎn)，連接平均持續(xù)時(shí)間為26.18 s，節(jié)點(diǎn)平均度為4.75，由此可以得到=0.05，=0.57。如圖2所示，令從1增加到10，分別給出了=10和5時(shí)的結(jié)果。

從圖2可以看出，理論結(jié)果與實(shí)驗(yàn)結(jié)果非常接近。當(dāng)=10時(shí)，平均誤差為3.87%；=5時(shí)，平均誤差為3.26%。這說明本文模型非常精確。下面不進(jìn)行過多的仿真驗(yàn)證，只是通過數(shù)值結(jié)果對模型進(jìn)行深入探討。

圖2 實(shí)驗(yàn)與理論結(jié)果比較

4.2 性能評估

下面通過數(shù)值結(jié)果來說明最優(yōu)策略是閾值策略，且利用仿真試驗(yàn)中的數(shù)據(jù)集。首先針對消息最大生存期的變化進(jìn)行探討，假設(shè)從1增加到20，且令=10。為了說明閾值策略的優(yōu)越性，給出了隨機(jī)策略所對應(yīng)的理論結(jié)果。隨機(jī)策略是指在每一步信息源都從[0,1]范圍內(nèi)隨機(jī)選擇發(fā)送概率。同樣也給出了()恒為1時(shí)的結(jié)果，實(shí)際上此時(shí)無能量限制，信息源始終以概率1發(fā)送。

從圖3可以看出最優(yōu)閾值概率明顯優(yōu)于隨機(jī)概率，且與無能量限制的時(shí)候非常接近，只在中間部分有一定的差別。這是因?yàn)楫?dāng)消息生存期較小時(shí)，最優(yōu)閾值h幾乎等于，即信息源始終以概率1發(fā)送；當(dāng)較大時(shí)，即使最優(yōu)閾值h小于，由于有充足的時(shí)間來完成傳輸，其性能同樣接近與發(fā)送概率恒為1的時(shí)候。但當(dāng)處于中間位置時(shí)，最優(yōu)閾值h小于，因此中轉(zhuǎn)節(jié)點(diǎn)得到消息的概率較小，且由于消息生存期不大，沒有充足的時(shí)間來完成傳輸，此時(shí)最優(yōu)閾值概率會(huì)稍小于無能量限制的情形。

圖3 消息生命周期的影響

下面使最大能量從1增加到20，且固定=10，可以得到如圖4所示曲線。

圖4 最大能量的影響

圖4顯示最優(yōu)閾值策略明顯優(yōu)于其他策略。由于DTN網(wǎng)絡(luò)通信的不可靠性，傳輸延遲可能比較大，所以DTN網(wǎng)絡(luò)路由的主要指標(biāo)就是盡可能提高傳輸成功率。但傳輸成功率的提高往往需要較多的副本，從而消耗更多的能量。下面探討對于不同的傳輸成功率所消耗的能量。假設(shè)傳輸成功率從10%增加到100%，數(shù)值結(jié)果如圖5所示。

圖5顯示出隨著傳輸成功率的增加，最小能量不斷增加。此外，如果消息的有效期較長，則也可以用較少的能量來滿足需要。

圖5 最小能量消耗

5 結(jié) 論

利用Edge-Markovian模型描述DTN中節(jié)點(diǎn)之間的連接關(guān)系，并研究了能量約束條件下two-hop算法的最優(yōu)控制問題。首先通過離散時(shí)間Markov過程對算法的消息傳播過程進(jìn)行建模，在此基礎(chǔ)上證明了最優(yōu)發(fā)送概率必須服從閾值形式，并且給出了計(jì)算最優(yōu)閾值策略的定理。仿真實(shí)驗(yàn)證明了模型的正確性，數(shù)值結(jié)果說明最優(yōu)閾值概率優(yōu)于隨機(jī)概率。

[1] FALL K. A delay-tolerant network architecture for challenged internets[C]//Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. [S.l.]: ACM, 2003.

[2] ZHANG H, SHEN H, TAN Y. Optimal energy balanced data gathering in wireless sensor networks[C]//Parallel and Distributed Processing Symposium. California, USA: IEEE, 2007.

[3] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C. Spray and wait: an efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking. [S.l.]: ACM, 2005.

[4] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C. Efficient routing in intermittently connected mobile networks: the multiple-copy case[J]. IEEE/ACM Transactions on Networking, 2008, 16(1): 77-90.

[5] PICU A, SPYROPOULOS T. Distributed stochastic optimization in opportunistic networks: the case of optimal relay selection[C]//Proceedings of the 5th ACM Workshop on Challenged Networks. [S.l.]: ACM, 2010: 21-28.

[6] MTIBAA A, MAY M, DIOT C, et al. Peoplerank: Social opportunistic forwarding[C]//2010 Proceedings of the INFOCOM. San Diego, CA, USA: IEEE, 2010.

[7] BALASUBRAMANIAN A, LEVINE B, VENKATARAMANI A. Replication routing in DTNs: a resource allocation approach[J]. IEEE/ACM Transactions on Networking (TON), 2010, 18(2): 596-609.

[8] GAO W, CAO G. User-centric data dissemination in disruption tolerant networks[C]//Proceedings of the INFOCOM. Shanghai: IEEE, 2011.

[9] ALTMAN E, NEGLIA G, De PELLEGRINI F, et al. Decentralized stochastic control of delay tolerant networks[C]//Proceedings of the 30th INFOCOM. Rio de Janeiro: IEEE, 2009: 1134-1142.

[10] LI Y, JIANG Y, JIN D, et al. Energy-efficient optimal opportunistic forwarding for delay-tolerant networks[J]. IEEE Transactions on Vehicular Technology, 2010, 59(9): 4500-4512.

[11] DE PELLEGRINI F, ALTMAN E, BASCAR T. Optimal monotone forwarding policies in delay tolerant mobile ad hoc networks with multiple classes of nodes[C]// Proceedings of the 8th International Symposium on Modeling and Optimization in Mobile, Ad hoc and Wireless Networks(WiOpt). [S.l.]: IEEE, 2010: 497-504.

[12] ALTMAN E, BA?AR T, KAVITHA V. Adversarial control in a delay tolerant network[J]. Lecture Notes in Computer Science, 2010(6442): 87-106.

[13] CLEMENTI A, MACCI C, MONTI A, et al. Flooding time of edge-Markovian evolving graphs[J]. SIAM Journal on Discrete Mathematics, 2010, 24(4): 1694-1712.

[14] WHITBECK J, CONAN V, DIAS DE AMORIM M. Performance of opportunistic epidemic routing on edge-markovian dynamic graphs[J]. IEEE Transactions on Communications, 2011, 59(5): 1259-1263.

[15] KER?NEN A, OTT J, K?RKK?INEN T. The one simulator for DTN protocol evaluation[C]//Proceedings of the 2nd International Conference on Simulation Tools and Techniques. [S.l.]: ACM, 2009.

[16] TOURNOUX P U, Leguay J, Benbadis F, et al. The accordion phenomenon: Analysis, characterization, and impact on DTN routing[C]//Proceedings of the INFOCOM. [S.l.]: IEEE, 2009: 1116-1124.

[17] EAGLE N, PENTLAND A. Reality mining: Sensing complex social systems[J]. Personal and Ubiquitous Computing, 2006, 10(4): 255-268.

[18] CHAINTREAU A, HUI P, CROWCROFT J, et al. Impact of human mobility on opportunistic forwarding algorithms[J]. IEEE Transactions on Mobile Computing, 2007, 6(6): 606-620.

編 輯 張 俊

Optimal Routing Control with Limited Energy in Delay Tolerant Networks

WU Ya-hui, DENG Su, and HUANG Hong-bin

(Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology Changsha 410073)

Connectivity patterns in delay tolerant networks can be modeled as Edge-Markovian graph and this model is better than traditional negative exponential model. In this paper, the optimal control problem of two-hop routing algorithm is explored with energy constraint under the Edge-Markovian graph. Considering that the source forwards the message with certain probability and the probabilistic two-hop routing method is used to decrease the energy consumption, the problem turns into the finding of the optimal probability to maximize the delivery ratio with energy constraint. Thus, a theoretical model for the problem is proposed based on the discrete time Markov process. We further prove that the optimal forwarding probability conforms to the threshold form. Simulation and numerical results show the correctness of the theoretical model.

delay tolerant networks; Edge-Markovian model; Markov process; optimal control; two-hop algorithm

TP393

A

10.3969/j.issn.1001-0548.2015.02.011

2011-11-10；

2014-12-15

國家自然科學(xué)基金(61401482, 60904065)

吳亞輝(1983-), 男, 博士, 主要從事延遲容忍網(wǎng)絡(luò)優(yōu)化控制方面的研究.