延遲容忍網絡能量受限的路由控制策略

吳亞輝，鄧 蘇，黃宏斌

?

延遲容忍網絡能量受限的路由控制策略

吳亞輝，鄧 蘇，黃宏斌

(國防科技大學信息系統工程重點實驗室 長沙 410073)

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

延遲容忍網絡; Edge-Markovian模型; Markov過程; 最優控制; two-hop算法

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

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

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

1 網絡模型

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

圖1 邊的狀態轉換圖

上述轉換是一個2狀態的馬爾科夫過程，存在穩定分布，因此有：

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

(2)

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

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

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

2 系統建模

假設在第個時隙末攜帶消息的節點數為()，(())表示對應的期望值。進一步假設每一個接受消息的節點只能在下一時隙才能進行轉發，且消息足夠小從而能夠在一個時隙內完成傳輸，顯然(0)=1。因為路由策略的能量消耗與轉發次數成正比，為簡單起見，直接利用轉發次數作為能量消耗的指標[9-12]。采用類似的方法，即用()表示從時刻0到第個時隙總共消耗的能量值。令()表示在第個時隙傳輸成功的概率(目的節點得到消息)。如果限定為傳輸一條消息，允許消耗的最大能量為，則存在問題：

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

(4)

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

當>時，其發送概率為0，因此得到消息的概率為0；在<時，由于發送概率為1，節點在第個時隙沒有得到消息，說明此時邊處于斷開狀態。因此，如果在第+1個時隙節點要得到消息，必須從0變為1，這一概率為，所以式(6)成立。當=時，由于上一時隙發送概率為1，可知值為p。

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

進一步可以得到：

(8)

對于目的節點，如果它在第(>1)個時隙(當=1時，只有能滿足，此概率為1)得到消息，且在此之前沒有得到，則此概率為：

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

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

進一步可以得到：

(11)

3 最優控制策略

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

根據定理1，可以得出最優閾值概率。

定理1 最優閾值h存在。

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

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

下面證明最優概率是閾值形式。在證明之前，先給出隨機序列的相關定理。

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

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

定理3 最優概率是閾值形式。

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

式中，參數τ()代表節點在第個時隙是否得到消息的指示量。值得注意的是，該參數的取值與節點在此之前是否得到消息無關。因此對應發送策略1滿足：

(14)

式中，p()代表節點與在第個時隙是否相遇，它只與節點運動規律有關，而與發送概率無關。因此，對應發送策略2有：

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

(16)

進一步有：

結合式(14)～式(17)，就可以知道(())是發送概率的單調遞增函數。下面對定理進行證明。

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

4 性能分析

4.1 仿真實驗

首先，采用機會網絡仿真平臺(opportunistic network environment simulator, ONE)驗證理論模型的正確性。因為采樣周期越長，連接失敗及短連接時間的邊消失的概率就越大[15]，這要求數據集具有較短的采樣周期，本文選用Rollernet數據集[16]，其采樣周期約為12 s，比傳統的Reality Mining[17]的600 s及Infocom 2005[18]的120 s都要短。利用前3 000 s的數據，并且選取60個節點，連接平均持續時間為26.18 s，節點平均度為4.75，由此可以得到=0.05，=0.57。如圖2所示，令從1增加到10，分別給出了=10和5時的結果。

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

圖2 實驗與理論結果比較

4.2 性能評估

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

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

圖3 消息生命周期的影響

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

圖4 最大能量的影響

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

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

圖5 最小能量消耗

5 結 論

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

[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

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

吳亞輝(1983-), 男, 博士, 主要從事延遲容忍網絡優化控制方面的研究.