基于節點社會特征的機會網絡最優發送策略

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

?

基于節點社會特征的機會網絡最優發送策略

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

（國防科技大學信息系統工程重點實驗室，湖南長沙 410073）

建立了基于節點社會特征的機會網絡信息傳輸模型，使用龐特里亞金極大值定理求得最優發送策略，該策略服從閾值形式，設停止時間為，當<時，節點以最大概率發送信息，當>時，節點停止發送信息。實驗表明，該策略優于最優靜態策略。進一步分析發現，節點的平均朋友數目越多，最優發送策略的停止時間越小，同時，其性能也越好。

機會網絡；社會特征；最優控制；能量約束

1 引言

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

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

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

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

2 最優控制問題描述

2.1 網絡模型

2.1.1 節點移動模型

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

其中，表示負指數分布的參數。

2.1.2 節點社會特征

現有工作[10]表明，社會網絡具有無標度特性，因此可以用冪律分布來表示社會特征。

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

2.2 理論框架

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

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

(4)

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

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

(6)

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

(7)

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

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

(9)

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

其中，是一個與網絡相關的衡量單位時間內探測能量消耗的正常數。

綜上，機會網絡信息傳輸過程中能量消耗可以表示為

為便于后續推導和計算，令

(12)

則有

式(13)就是網絡系統的狀態空間表達式，此時，本文的主要問題就是解決下述優化問題。

(14)

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

3 最優發送策略

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

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

對應的伴隨狀態函數為

(17)

其中，轉移條件滿足

進一步可知，該問題的最優策略必然滿足

(19)

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

因此，對于最優策略，控制參數1()應滿足

(21)

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

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

其中，為停止時間。

證明 首先，本文定義如下函數

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

(25)

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

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

(27)

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

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

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

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

4 性能分析

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

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

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

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

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

5 結束語

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

[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

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

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

王志飛（1990-），男，河北邯鄲人，國防科學技術大學博士生，主要研究方向為機會網絡、隨機網絡。

史培騰（1993-），男，河南濮陽人，國防科學技術大學碩士生，主要研究方向為網絡科學、大數據分析技術。

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

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

吳亞輝（1983-），男，河南商丘人，博士，國防科學技術大學講師，主要研究方向為機會網絡、無線通信、網絡優化。