中继节点的选择将直接影响机会网络的数据转发性能.对此提出一种带有投递概率感知的低开销机会网络路由机制.利用节点间的间接相遇时间间隔估计间接相遇概率，并结合直接相遇概率预测节点间的综合相遇概率，进而合理地选择中继节点，以极低开销的方式转发数据.结果表明，在数据传输过程中，所提出机制的负载率平均降低了64.9%.
The selection of relay node will directly affect the data forwarding performance of opportunity network. Therefore the cost-efficient routing mechanism with delivery probability perception (DPP-CERM) in opportunistic networks is proposed. The probability of comprehensive encounter between nodes by combining the probability of direct encounter and indirect encounter is estimated and evaluated by indirect inter-meeting time between nodes. The relay node reasonably and forward data with very lower cost were chosen thereafter. It is shown that DPP-CERM can reduce the average overhead ratio of data forwarding at least 64.9%.
传统的移动自组织网络(MANET，mobile ad-hoc network)传输数据之前需要在源节点和目的节点之间至少建立一条完整的路径[1].但网络环境的变化将使得节点之间的连通程度呈现出较强的动态性，导致使用MANET路由协议的节点无法完成有效通信.因此，利用节点移动时产生的相遇机会实现节点间的相互通信的机会网络[2]应运而生，其路由机制对于改善网络性能至关重要.传染转发(EF，epidemic forwarding)机制[3]以泛洪的方式复制数据副本，其性能受限于缓存资源. Bian等[4]提出泛洪控制机制(EC，epidemic control)，利用控制副本数量的方法降低网络开销. Lindgren等[5]提出了基于节点状态预测的转发机制，利用概率传递性预测相遇状态，以提高网络性能.
显然，活跃程度较高的节点将更加适合作为中继节点转发数据，节点活跃度估计普遍采用基于相遇历史信息的方式，如相遇频率、社会属性[6-7]. Bulut等[8-9]对节点间的相遇时间间隔进行仿真比较，且推导证明了节点的移动过程并非独立.并且将间接相遇时间间隔作为衡量最短路径的标准，选择节点间的最短路径转发数据，从而提高网络性能.但机会网络拓扑动态变化，仅利用直接或间接相遇时间间隔评估节点相遇状态并完成数据转发，其准确度难以得到保障，且转发过程中易产生大量冗余数据.
提出一种带有投递概率感知的低开销路由机制(DPP-CERM，cost efficient routing mechanism with delivery probability perception).综合考虑节点各类相遇事件，预测节点间直接和间接相遇概率，进而估计节点间的综合相遇概率，使得中继节点的选择更为合理，在提升投递率的同时降低了网络开销.
1 投递概率动态感知对于采用“存储-携带-转发”方式进行数据转发的机会网络来说，数据需要在多个中继节点进行存储，且节点之间并不存在显式的端到端路径.因此，数据的投递状态需要综合考虑节点之间的直接相遇概率和间接相遇概率.显然，节点之间的相遇次数越多，则两者之间的相遇概率越大.因此，节点间直接相遇概率如定义1所示.
定义1 假设在无向网络G(V, E)中，当前时刻节点X与节点Mj的直接相遇概率满足式(1) 所示关系，即直接相遇概率PX(Mj)为两节点的相遇次数l与节点X记录的总相遇次数n的比值，其中Mj是节点X缓存中所记录的相遇历史信息节点.
|
(1) |
节点之间的间接相遇概率受限于间接相遇时间间隔、平均间接相遇时间间隔、间接相遇时间间隔总和以及间接相遇次数，其估计方法如下：给定时间内，节点之间的相遇次数越多，即相遇时间间隔越短，表明其相遇概率越大.同理，源节点与目的节点的间接相遇时间间隔越短，表明源节点与中间节点相遇后，在下一时刻遇到目的节点的概率越大.因此，利用间接相遇时间间隔作为节点间接相遇概率估计的参数，可以使估测更加准确，有利于提高网络性能.下面给出间接相遇时间间隔的定义.
定义2 在无向网络G(V, E)中，当节点X与节点N相遇后，再与节点M相遇时所耗费的时间称为节点X的间接相遇时间间隔，记作TX(M|N).
为了更加简洁地给出计算方法，下面举例给出所需参数的计算公式.假设有3个节点，分别为节点A、节点B和节点C.节点A与节点B、C发生连接的时间点分别为
|
则节点A与节点B相遇之后遇到节点C的间接相遇时间间隔总和TAsum(C|B)为
|
(2) |
其中r(k)=min {i:TC，i≥TB，k}. |r(k)|表示相遇历史信息中节点A与节点B相遇之后，进而与节点C相遇的间接相遇次数.当|r(k)|=0时，TAsum(C|B)=0.
节点A与节点B相遇之后再遇到节点C的平均间接相遇时间间隔TA(C|B)为间接相遇时间间隔总和TAsum(C|B)与间接相遇次数|r(k)|的比值，如式(3) 所示.
|
(3) |
节点的平均间接相遇时间间隔越小，表明间接相遇次数越多、间接相遇时间间隔越短，则其间接相遇概率越大.因此，可利用平均间接相遇时间间隔作为估计间接相遇概率的参数.下面给出间接相遇概率的定义和计算方法.
定义3 在无向网络G(V, E)中，节点X与节点N相遇后，进而与节点M相遇的概率称为节点X的间接相遇概率，满足式(4) 所示关系，记作PX(M|N).
|
(4) |
其中：T表示给定时间间隔，|TX(M|N)|表示间接相遇次数，TXsum(M|N)表示间接相遇时间间隔总和，如式(2) 所示，TX(M|N)表示平均间接相遇时间间隔，如式(3) 所示.
若本地节点的相遇历史信息中，某个相遇节点为目的节点，则间接相遇概率为
|
(5) |
其中TX(M)为节点X与M的平均相遇时间间隔，其计算方法为
|
(6) |
其中TM，first、TM，last分别表示节点X与节点M的第1次相遇时间和最后一次相遇时间，n表示相遇次数.
如前所述，节点之间的数据传输过程需要综合考虑节点之间的直接相遇概率和间接相遇概率.根据数据转发过程的历史信息，提出了相应的投递概率感知方法.网络中各个节点都按照表 1的方式存储节点相遇状态信息，且表项中的数值随着数据转发过程进行实时更新，以确保投递概率的时效性.对于此种网络架构下的千字节级甚至兆字节级的数据来说，节点历史相遇信息表所占的缓存大小几乎可以忽略不记.
|
表 1 相遇历史信息 |
其中：M1, M2, …, Mj为节点X历史相遇节点的身份标示号码(ID，identity). TM1, TM2, …, TMj为节点X和各节点的相遇时间集合.
可见，节点的相遇历史信息为完备事件组，与其相遇的每个节点为该“节点相遇事件”的划分.显然PX(Mj)>0, (i=1, 2, …, n).成立.按照上述原理，综合考虑直接相遇概率和间接相遇概率，节点X与目的节点D的投递概率如式(7) 所示.
|
(7) |
其中K表示节点X的历史相遇节点个数.
2 数据转发过程按照上述投递概率感知方法，所提出的数据转发过程如下所述.当产生新数据时，系统自动为新产生的数据赋予一个全网唯一的标识(ID，identity)，相遇节点间在进行数据传输时，按照数据进入缓存的时间顺序依次传输.节点进行数据交互时需交换各自缓存内数据的概要向量(SV，summary vector)，并更新双方节点的相遇历史信息.网络状态在有限的时间尺度内趋于稳定，节点间通过不断交互相遇信息，从而能近似地获知网络中各个节点的相遇信息.
在发送数据之前，需首先判定相遇节点是否为数据的目标节点，若满足条件，则直接投递该数据至对方节点；反之，则根据节点本地保存的相遇历史信息，利用所提出的DPP-CERM机制，综合考虑节点的直接相遇和间接相遇状态信息，估计节点与数据的目标节点的投递概率.若相遇节点与目标节点的投递概率大于本地节点，则将数据发送至相遇节点，反之，则继续存储于本地，直至数据生存期终止.
3 数值结果在机会网络环境(ONE，opportunistic network environment)[10]仿真平台上，对DPP-CERM及PRoPHET、Epidemic、EpidemicControl进行了性能比较.为了充分表明所提出机制具有较强的实际应用价值，选取Infocom06的实测数据作为测试数据，其中节点为78个，在3d的记录时间内，节点总连接次数为197336次，其他参数如表 2所示.
|
|
表 2 仿真参数 |
对4个路由在不同缓存大小下的负载率、投递率和传输时延进行了比较，如图 1~图 3所示.其中，负载率为未成功投递数据数量与成功投递数据数量的比值.由图 1可知，随着缓存的逐渐增大，4个路由机制的负载率整体呈下降趋势.主要原因在于随着缓存的增大，节点能携带更多的数据，提高了成功转发的概率，从而避免了冗余转发，即负载率降低.与其他路由机制相比，DPP-CERM的负载率最低. DPP-CERM的负载率平均比PRoPHET低64.9%，比Epidemic低75.3%，比EpidemicControl低73.4%.其主要原因在于DPP-CERM不仅考虑了节点间的直接相遇概率，而且综合考虑间接相遇因素，从而更加全面地考虑了数据的转发过程，能更加合理地选择中继节点，避免不必要的间接投递过程，有效地控制了冗余数据的数量，进而提高了网络资源利用率.
|
图 1 不同缓存对负载率的影响 |
|
图 2 不同缓存对投递率的影响 |
|
图 3 不同缓存对传输时延的影响 |
由图 2可知，4个路由机制的投递率随着缓存的增大呈上升趋势.其主要原因在于随着缓存的增大，节点携带的数据数量随之增加，其成功投递的概率升高.从结果中可知，DPP-CERM的投递率性能最优，比PRoPHET高5.3%，比Epidemic高15.1%，比Epidemic-Control高11.3%.结果表明，DPP-CERM能更加准确地选择合适的中继节点，减少不必要的转发，避免了部分数据在转发过程中因生命期终止或者缓存不足而被删除，从而达到改善投递率的效果.该机制随着节点的移动而频繁地交互相遇信息，及时地感知局部区域内各节点对数据的投递概率，从而选择区域内投递概率最大的中继节点进行数据转发；且该机制不是严格意义上的单副本数据转发机制，合理的进行数据副本的转发，有效地避免了环状路由问题.
由图 3可知，各个路由机制的传输时延随着缓存容量的增大而逐渐上升. DPP-CERM的传输时延比PRoPHET略低，表明DPP-CERM选择的中继节点更加合理.但是DPP-CERM比Epidemic类数据转发机制的传输时延高，主要由于Epidemic类采用泛洪的方式进行数据传输，虽然其扩散程度较快，但是消耗了大量的网络资源.
4 结束语提出一种带有投递概率感知的低开销机会网络路由机制，充分考虑了节点间的直接相遇概率与间接相遇概率，进而更加准确地评估节点之间的连接状态.与传统的路由机制相比，所提出的DPP-CERM能合理地选择中继节点，进而提高网络资源利用率，改善网络性能.由于所提出机制能更加准确地选取中继节点，所以，该机制更适合应用在社区网络等具有社会属性的无线网络中.
| [1] | Chiang T C, Chang J L, Lin S W. A distributed multicast protocol with location aware for mobile ad-hoc networks[J]. Advances in Intelligent and Soft Computing, 2012(2): 691–679. |
| [2] | Elizabeth M, Mads H. The challenges of disconnected delay-tolerant MANETs[J]. Ad Hoc Networks, 2010, 8(2): 241–250. doi: 10.1016/j.adhoc.2009.08.003 |
| [3] | Khouzani M H R, Sarkar S, Altman E. Optimal control of epidemic evolution[C]//INFOCOM' 2011. Shanghai: IEEE Press, 2011: 1683-1691. |
| [4] | Bian Hong, Yu Haizheng. An efficent control method of multi-copy routing in DTN[C]//Network Security Wireless Communications and Trusted Computing. Wuhan: IEEE Press, 2010: 153-156. |
| [5] | Lindgren A, Doria A, Schelen O. Probabilistic routing in intermittently connected networks[J]. SIGMOBILE Mobile Computing and Communications Review, 2003, 7(3): 19–20. doi: 10.1145/961268 |
| [6] | Zhang Yang, Gao Wei, Cao Guohong, et al. Social aware data diffusion in delay tolerant MANETs[J]. Springer Optimization and Its Applicatins, 2012(58): 457–481. |
| [7] | Li Qinghua, Gao Wei, Zhu Sencun, et al. A routing protocol for socially selfish delay tolerant networks[J]. Ad Hoc Networks, 2012, 10(8): 1619–1632. doi: 10.1016/j.adhoc.2011.07.007 |
| [8] | Bulut E, Geyik S C, Szymanski B K. Efficient routing in delay tolerant networks with correlated node mobility[C]//Mobile Ad-hoc and Sensor Systems (MASS). San Francisco: IEEE Press, 2010: 79-88. |
| [9] | Bulut E, Geyik S C, Szymanski B K. Conditional shortest path routing in delay tolerant networks[C]//World of Wireless Mobile and Multimedia Networks (WoWMoM). Montreal: IEEE Press, 2010: 1-6. http://www.jwcn.eurasipjournals.com/content/2015/1/202 |
| [10] | 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(SimuTools'09). Brussels: ICTS Press, 2009: 1-10. |