王志飞，史培腾，邓苏，黄宏斌，吴亚辉



基于节点社会特征的机会网络最优发送策略

王志飞，史培腾，邓苏，黄宏斌，吴亚辉

（国防科技大学信息系统工程重点实验室，湖南长沙 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-），男，河南商丘人，博士，国防科学技术大学讲师，主要研究方向为机会网络、无线通信、网络优化。