基于節(jié)點社會特征的機會網(wǎng)絡(luò)最優(yōu)發(fā)送策略

王志飛，史培騰，鄧蘇，黃宏斌，吳亞輝

?

基于節(jié)點社會特征的機會網(wǎng)絡(luò)最優(yōu)發(fā)送策略

王志飛，史培騰，鄧蘇，黃宏斌，吳亞輝

（國防科技大學(xué)信息系統(tǒng)工程重點實驗室，湖南長沙 410073）

建立了基于節(jié)點社會特征的機會網(wǎng)絡(luò)信息傳輸模型，使用龐特里亞金極大值定理求得最優(yōu)發(fā)送策略，該策略服從閾值形式，設(shè)停止時間為，當<時，節(jié)點以最大概率發(fā)送信息，當>時，節(jié)點停止發(fā)送信息。實驗表明，該策略優(yōu)于最優(yōu)靜態(tài)策略。進一步分析發(fā)現(xiàn)，節(jié)點的平均朋友數(shù)目越多，最優(yōu)發(fā)送策略的停止時間越小，同時，其性能也越好。

機會網(wǎng)絡(luò)；社會特征；最優(yōu)控制；能量約束

1 引言

機會網(wǎng)絡(luò)從移動自組織網(wǎng)絡(luò)演化而來，與傳統(tǒng)的移動自組織網(wǎng)絡(luò)不同的是，在機會網(wǎng)絡(luò)中，由于網(wǎng)絡(luò)鏈接時斷時續(xù)、網(wǎng)絡(luò)鏈接持續(xù)時間短、網(wǎng)絡(luò)拓撲動態(tài)變化，源節(jié)點和目的節(jié)點之間往往不存在可靠的通信鏈路，因此，在機會網(wǎng)絡(luò)中進行信息傳輸具有很大的挑戰(zhàn)性。為了克服網(wǎng)絡(luò)分割的問題，機會網(wǎng)絡(luò)引入了“存儲—攜帶—轉(zhuǎn)發(fā)”（store-carry-forward）的信息傳輸方式[1]，在該方式中，節(jié)點往往不維護到其他節(jié)點的路由表，而是將信息緩存到具有存儲能力的移動節(jié)點上，隨著節(jié)點移動尋找合適的轉(zhuǎn)發(fā)機會轉(zhuǎn)發(fā)信息。傳統(tǒng)的自組織網(wǎng)絡(luò)和互聯(lián)網(wǎng)將節(jié)點移動導(dǎo)致的網(wǎng)絡(luò)不連通看成是挑戰(zhàn)，而機會網(wǎng)絡(luò)則把節(jié)點移動產(chǎn)生的相遇看成是傳輸機會。

如果攜帶信息的節(jié)點將信息傳遞到每個相遇的節(jié)點，目的節(jié)點就可以較快地接收到信息，但同時，能量消耗也會比較大。如果源節(jié)點只在遇到目的節(jié)點時才轉(zhuǎn)發(fā)信息，雖然節(jié)省了能量，但傳輸延遲往往會非常大。也就是說，較高的能量消耗也會帶來較高信息傳輸成功率，對于無線設(shè)備來說，能量非常珍貴，因此，探討在機會網(wǎng)絡(luò)中能量受限條件下的最優(yōu)發(fā)送策略具有很重要的理論意義和實踐意義。

目前，已有一些學(xué)者對機會網(wǎng)絡(luò)中的最優(yōu)發(fā)送問題進行了一定的研究，Altman等[2]首先研究了機會網(wǎng)絡(luò)中的最優(yōu)發(fā)送策略，基于傳輸延遲和能量消耗描述了最優(yōu)控制問題，計算了傳輸概率的最優(yōu)靜態(tài)值，發(fā)現(xiàn)當隨時間變化時，其最優(yōu)策略滿足閾值策略。Li等[3]基于能量約束，為泛洪路由和兩跳路由描述了機會網(wǎng)絡(luò)最優(yōu)控制問題，設(shè)計了不同的靜態(tài)和動態(tài)策略，研究發(fā)現(xiàn)最優(yōu)發(fā)送策略服從閾值策略。Wang等[4]考慮2個文件的轉(zhuǎn)發(fā)優(yōu)先級，以最大化收到信息的節(jié)點數(shù)目為優(yōu)化目標，發(fā)現(xiàn)最優(yōu)路由策略服從閾值策略。

上述研究沒有考慮節(jié)點的社會特征，Shrestha等[5]將機會網(wǎng)絡(luò)中的節(jié)點劃分為多個不重疊的社區(qū)，基于平均場理論描述了最優(yōu)控制問題，進一步地，他們證明了最優(yōu)發(fā)送策略服從閾值策略，并提供了一個啟發(fā)式優(yōu)化算法進一步說明最優(yōu)策略。實際上，節(jié)點的社會特征具有無標度特性，本文基于無標度特性這一節(jié)點社會特征探討機會網(wǎng)絡(luò)中的最優(yōu)發(fā)送策略。

2 最優(yōu)控制問題描述

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

2.1.1 節(jié)點移動模型

研究人員試圖根據(jù)真實軌跡來描述機會網(wǎng)絡(luò)節(jié)點的移動模式，Conan[6]發(fā)現(xiàn)相遇時間間隔的分布服從對數(shù)正態(tài)分布，同時，負指數(shù)曲線也能夠很好地擬合其分布。Karagiannis[7]也發(fā)現(xiàn)如果考慮長尾，分布的尾部服從指數(shù)分布。同時，很多工作[8,9]使用這一簡單假設(shè)來建模并取得了很有意義的結(jié)果。為簡化理論分析，本文仍然使用相遇時間間隔服從負指數(shù)分布這一假設(shè)，任何2個節(jié)點在時間間隔[,+ Δ]相遇的概率為

其中，表示負指數(shù)分布的參數(shù)。

2.1.2 節(jié)點社會特征

現(xiàn)有工作[10]表明，社會網(wǎng)絡(luò)具有無標度特性，因此可以用冪律分布來表示社會特征。

其中，()表示擁有個朋友的節(jié)點數(shù)所占比例，為節(jié)點總數(shù)，是最小朋友數(shù)，表示偏度，(,)為歸一化常數(shù)。

2.2 理論框架

假設(shè)網(wǎng)絡(luò)中包含個節(jié)點，其中，包含一個源節(jié)點和一個目的節(jié)點，這個節(jié)點按照2.1.1節(jié)描述的負指數(shù)模型移動，節(jié)點間的社會特征由2.1.2節(jié)給出的冪律分布定義，以(,)代表具有個朋友的節(jié)點在時刻時攜帶信息的概率，以變量上方加點表示相應(yīng)變量的導(dǎo)數(shù)，下同。根據(jù)文獻[11]，則有

其中，的取值范圍為[,?1]，在后續(xù)敘述中，均采用此取值范圍。1()和2()分別表示朋友間和非朋友間傳遞信息的概率，簡單起見，本文假設(shè)非朋友間不傳遞信息，實際上，出于安全和隱私等考慮，節(jié)點可能不會將信息轉(zhuǎn)發(fā)給陌生人。將2() = 0代入式(3)，則有

(4)

其中，以()表示時刻目的節(jié)點接收到信息的概率，()表示目的節(jié)點一直到時刻都沒有接收到信息的概率，顯然，() = 1 –()。假設(shè)所有節(jié)點給目的節(jié)點發(fā)送信息的概率為1，記事件Θ為在時間[,+ Δ]內(nèi)目的節(jié)點沒有接收到信息的概率，可以得到

其中，(Θ)可以理解為目的節(jié)點在[,+ Δ]內(nèi)沒有遇到攜帶信息的節(jié)點的概率，因此有

(6)

聯(lián)合式(5)和式(6)，可以得到

(7)

由于() = 1 –()，因此有

下面開始考慮信息傳輸過程中的能量消耗及限制，能量消耗主要包括2部分：一部分為發(fā)送節(jié)點的發(fā)送能量消耗及接收節(jié)點的接收能量消耗；另一部分為節(jié)點為發(fā)現(xiàn)其他節(jié)點而產(chǎn)生的探測能量消耗。每次發(fā)送與接收都會產(chǎn)生一個信息副本，由于每次發(fā)送和接收的能量消耗是相同的，因此，此過程的能量消耗和網(wǎng)絡(luò)中節(jié)點攜帶的信息副本數(shù)成正比，該過程的能量消耗可以表示為

(9)

當節(jié)點移動到其通信范圍時，通過節(jié)點的探測活動就能發(fā)現(xiàn)其他節(jié)點。和現(xiàn)有工作類似[12]，假設(shè)只有沒有攜帶信息的節(jié)點才會進行探測活動，以求發(fā)現(xiàn)攜帶信息的節(jié)點。因此，該過程的能量消耗可以表示為

其中，是一個與網(wǎng)絡(luò)相關(guān)的衡量單位時間內(nèi)探測能量消耗的正常數(shù)。

綜上，機會網(wǎng)絡(luò)信息傳輸過程中能量消耗可以表示為

為便于后續(xù)推導(dǎo)和計算，令

(12)

則有

式(13)就是網(wǎng)絡(luò)系統(tǒng)的狀態(tài)空間表達式，此時，本文的主要問題就是解決下述優(yōu)化問題。

(14)

其中，是信息的最大生命周期，是網(wǎng)絡(luò)能量限制，在總能量受限的情況下，通過調(diào)整1()在任意時刻的取值，使傳輸成功率達到最大。

3 最優(yōu)發(fā)送策略

本文使用龐特里亞金極大值定理對問題進行求解，由于(0) = 0，因此有

簡單起見，以((,S,),)表示對應(yīng)參數(shù)的描述，如在時刻，S就表示(,)，表示()，表示()，同樣地，1就代表1()，根據(jù)龐特里亞金極大值定理，可以得到如下的哈密頓函數(shù)

對應(yīng)的伴隨狀態(tài)函數(shù)為

(17)

其中，轉(zhuǎn)移條件滿足

進一步可知，該問題的最優(yōu)策略必然滿足

(19)

因此，通過求解最大化哈密頓函數(shù)便可以得到該問題的最大值，根據(jù)式(16)可以得到

因此，對于最優(yōu)策略，控制參數(shù)1()應(yīng)滿足

(21)

信息傳輸成功率的取值范圍為[0, 1]，當=1時，此時目的節(jié)點已經(jīng)獲得信息，就不再探討最優(yōu)發(fā)送策略，當≠1時，可以得到定理1。

定理1 式(13)和式(14)描述的最優(yōu)控制問題的最優(yōu)發(fā)送策略1滿足閾值形式，且最多只有一跳，也就是存在時刻，0≤≤，使1滿足

其中，為停止時間。

證明 首先，本文定義如下函數(shù)

將()對時間求導(dǎo)，可以得到

(25)

當()≤0時，根據(jù)式(22)可知1()=0，進一步，將1()=0代入式(4)可以得到，，又根據(jù)式(17)可以知道，，因而，當()≤0時，可以將式(25)化簡為

基于式(17)和1() = 0，可以得到

(27)

此外，1+λ>0始終成立，否則，假設(shè)存在某一時刻滿足1+λ()≤0，則有

從式(28)可知λ()在時刻非遞增，也就是說，在的下一時刻依然滿足1+λ()≤0，依次類推，當=時有，1+λ()≤0，也就是，λ()≤?1，這與式(18)相矛盾，因此，假設(shè)不成立，1+λ> 0始終成立，故有，，其中，的取值范圍為[,?1]。

如果對于任意的∈[,?1]，都有S= 1，則說明網(wǎng)絡(luò)中的所有節(jié)點都接收到了信息，包括目的節(jié)點，此時，不需要再探討最優(yōu)策略，因此，本文只需要探討存在∈[,?1]，使S<1，也就是，1?S>0，根據(jù)式(26)，可以得知，，進而可以得知，在下一時刻，則有()<0，依次類推，可以得到在后續(xù)的時間始終有()<0。綜上，如果()≤0，則在下一時刻()為負值，并始終為負值，假設(shè)為第一個不大于0的時刻，即()>0,<，由上述證明過程可知，()≤0,>，結(jié)合式(22)，可以得知

其中，0≤≤，定理得證。

4 性能分析

本文使用機會仿真環(huán)境（ONE, opportunistic network environment）[13]進行仿真驗證，移動模型采用經(jīng)典的RWP（random waypoint）移動模型，所有的節(jié)點在1 000 m×1 000 m的區(qū)域中移動，節(jié)點移動速度的取值范圍為0.5~1.5 m/s，通信距離為5 m。對于社會特征來說，偏度設(shè)置為3，這來源于真實的社會網(wǎng)絡(luò)[10]。使用200個節(jié)點進行仿真，每個節(jié)點至少有20個朋友，朋友間傳遞信息的概率為0.9，即= 200，= 20，= 0.9。和是與網(wǎng)絡(luò)相關(guān)的常量，和具體應(yīng)用有關(guān)，類似于文獻[12,14,15]，取= 1,= 10?6。讓最大生存周期從0 s增加到40 000 s，進行50次仿真實驗，結(jié)合對應(yīng)的理論結(jié)果，可以得到的仿真結(jié)果如圖1所示，對比發(fā)現(xiàn)，傳輸成功率的誤差為5.18%，能量消耗的誤差為6.44%，這就驗證了模型的準確性。

下面以數(shù)值結(jié)果來探討最優(yōu)策略的優(yōu)越性，設(shè)定總能量限制為= 20。為了驗證最優(yōu)發(fā)送策略的優(yōu)越性，設(shè)計一種靜態(tài)策略，顯然，1()越大，傳輸成功率越大，但必須滿足式(14)的能量約束，1取最大時就稱為最優(yōu)靜態(tài)策略，當=1,= 10?6時，可以得到性能對比結(jié)果如圖2(a)所示，當= 1,= 2×10?6時，可以得到性能對比結(jié)果如圖2(b)所示。

從圖2可以看出，由式（22）得出的策略優(yōu)于最優(yōu)靜態(tài)策略。此外，當信息最大生存周期較小時，兩者的性能相同，如在圖2(a)中，當<27 474 s時，兩者的性能相同。這是因為，當較小時，最優(yōu)策略中的取值始終為1，不存在跳躍，此時，最優(yōu)策略和最優(yōu)靜態(tài)策略一致。

下面探討最優(yōu)策略和節(jié)點社會特征的關(guān)系，設(shè)定= 3，分別取20、25、30，得到最優(yōu)發(fā)送策略及其性能如圖3所示。圖3(a)說明了最優(yōu)發(fā)送策略確實服從閾值形式，越大，節(jié)點的平均朋友數(shù)越多，停止時間越小，同時，由圖3(b)可知，越大，最優(yōu)策略的性能也就越好。

下面設(shè)定= 20，分別取1、2、3，得到最優(yōu)發(fā)送策略及其對應(yīng)的性能如圖4所示。從圖中可發(fā)現(xiàn)，越小，節(jié)點的平均朋友數(shù)也就越多，停止時間也越小，最優(yōu)策略性能也越好，這和圖3的結(jié)論是一致的，這說明最優(yōu)發(fā)送策略是和節(jié)點社會特征密切相關(guān)的。

5 結(jié)束語

目前，關(guān)于機會網(wǎng)絡(luò)的最優(yōu)發(fā)送策略都沒有考慮網(wǎng)絡(luò)的無標度特性這一社會特征，針對這一點，本文提出了基于節(jié)點社會特征的機會網(wǎng)絡(luò)最優(yōu)發(fā)送策略并探討了最優(yōu)發(fā)送策略的形式和影響因素。研究發(fā)現(xiàn)，最優(yōu)發(fā)送策略服從閾值形式，此外，節(jié)點的平均朋友數(shù)越多，最優(yōu)策略的停止時間也越小，其性能也就越好。但是本文假設(shè)未接收到信息的節(jié)點不斷探測，實際上，節(jié)點會選擇合適的機會停止探測以節(jié)省能量，此外，為了獲得最優(yōu)發(fā)送策略，如何激勵節(jié)點協(xié)作傳輸，也是下一步值得深入研究的問題。

[1] Lin Y, Wang X, Zhang L, et al. The impact of node velocity diversity on mobile opportunistic network performance[J]. Journal of Network & Computer Applications, 2015, 55:47-58.

[2] ALTMAN E, BASAR T, PELLEGRINI F D. Optimal monotone forwarding policies in delay tolerant mobile ad-hoc networks[J]. Valuetools Proceedings of International Conference on Performance Evaluation Methodologi, 2010, 67(4): 299-317.

[3] 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.

[4] WANG S, KHOUZANI M, KRISHNAMACHARI B, et al. Optimal control for epidemic routing of two files with different priorities in delay tolerant networks[C]//American Control Conference (ACC). 2015IEEE, c2015:1387-1392.

[5] SHRESTHA N, SASSATELLI L. On optimality of routing policies in delay-tolerant mobile social networks[C]//Vehicular Technology Conference (VTC Spring). 2013 IEEE 77thIEEE, c2013: 1-5.

[6] CONAN V, LEGUAY J, FRIEDMAN T. Characterizing pairwise inter-contact patterns in delay tolerant networks[C]//The 1st International Conference on Autonomic Computing and Communication Systems. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering). c2007: 19.

[7] KARAGIANNIS T, LE BOUDEC J Y, VOJNOVI? M. Power law and exponential decay of inter contact times between mobile devices[J]. IEEE Transactions on Mobile Computing, 2010, 9(10): 1377-1390.

[8] WU Y, DENG S, HUANG H. Information propagation through opportunistic communication in mobile social networks[J]. Mobile Networks and Applications, 2012, 17(6): 773-781.

[9] LI Y, SU G, WU D O, et al. The impact of node selfishness on multicasting in delay tolerant networks[J]. IEEE Transactions on Vehicular Technology, 2011, 60(5): 2224-2238.

[10] RAPOPORT A, HORVATH W J. A study of a large sociogram[J]. Behavioral Science, 1961, 6(4): 279-291.

[11] WU Y, DENG S, HUANG H. Evaluating the impact of selfish behaviors on epidemic forwarding in mobile social networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2013, 2013(02): P02018.

[12] Wu Y, Deng S, Huang H. Energy-efficient joint control of epidemic routing in delay tolerant networks[J]. Ksii Transactions on Internet & Information Systems, 2013, 7(2):234-252.

[13] Ker?nen A, Ott J, K?rkk?inen T. The ONE simulator for DTN protocol evaluation[C]//The 2nd International Conference on Simulation Tools and Techniques. c2009: 55.

[14] Altman E, Azad A P, Basar T, et al. Optimal activation and transmission control in delay tolerant networks[C]//IEEE INFOCOM. IEEE, c2010: 1-5.

[15] Li Y, Wang Z, Jin D, et al. Optimal beaconing control for epidemic routing in delay tolerant networks[J]. IEEE Transactions on Vehicular Technology, 2012, 61(1): 311-320.

Optimal forwarding policy in opportunistic based on social features of nodes

Wang Zhi-fei, Shi Pei-teng, Deng Su, Huang Hong-bin, Wu Ya-hui

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

A forwarding model of opportunistic network was established based on social features of node and by introducing the Pontryagin’s maximal principle, the optimal policy was got, which obeyed the threshold form. Letdenotes the stop time, when<, nodes forward the messages with the maximum probability, when>, the node stops sending messages. Experiments show that the optimal strategy is better than optimal static policy. Further analysis show that the bigger the average number of friends of node is, the smaller the stopping time is, the better the performance is.

opportunistic network, social feature, optimal control, energy constraint

TP393

A

10.11959/j.issn.1000-436x.2016126

2015-11-03；

2016-04-06

國家自然科學(xué)基金資助項目（No.61401482）

The National Natural Science Foundation of China (No.61401482)

王志飛（1990-），男，河北邯鄲人，國防科學(xué)技術(shù)大學(xué)博士生，主要研究方向為機會網(wǎng)絡(luò)、隨機網(wǎng)絡(luò)。

史培騰（1993-），男，河南濮陽人，國防科學(xué)技術(shù)大學(xué)碩士生，主要研究方向為網(wǎng)絡(luò)科學(xué)、大數(shù)據(jù)分析技術(shù)。

鄧蘇（1963-），男，湖南株洲人，博士，國防科學(xué)技術(shù)大學(xué)教授，主要研究方向為移動自組網(wǎng)、信息物理融合系統(tǒng)和信息管理。

黃宏斌（1975-），男，江蘇南通人，博士，國防科學(xué)技術(shù)大學(xué)研究員，主要研究方向為信息聚焦服務(wù)、信息物理融合系統(tǒng)。

吳亞輝（1983-），男，河南商丘人，博士，國防科學(xué)技術(shù)大學(xué)講師，主要研究方向為機會網(wǎng)絡(luò)、無線通信、網(wǎng)絡(luò)優(yōu)化。