带有消息投递概率估计的机会网络自适应缓存管理策略

吴大鹏 张普宁 王汝言

(重庆邮电大学宽带泛在接入技术研究所 重庆 400065)

1 引言

多样化手持与车载终端的广泛应用推动了移动自组织网络(Mobile Ad hoc NETwork, MANET)的快速发展。然而，MANET网络中的通信过程需预先建立端到端路径[1]，但实际应用场景中存在节点分布稀疏、高速移动、通信能力受限等问题，将导致源节点和目标节点之间建立的通信路径出现高频度断裂[2]。为实现复杂动态环境下的有效通信，研究人员提出了机会网络体系架构[3]。与MANET所采用的存储-转发消息传输模式不同，机会网络中节点转发消息前不需建立端到端路径，仅依靠节点相遇带来的通信机会，以更为灵活的存储-携带-转发方式传输消息。

针对机会网络特征，国内外研究人员对机会网络中的节点缓存管理机制展开了相关研究。文献[4]通过向邻居节点泛洪本地节点的缓存占用状态，从而避免缓存占用率较高的节点出现溢出。然而，此种泛洪策略极大地消耗了网络资源，严重影响了正常消息的传输过程，此种泛洪方法不适用于资源受限的机会网络。文献[5]证明了删除消息的冗余副本有利于改善消息投递率的结论，并根据边际效用递减规律，提出综合考虑消息复制数与副本传输速率的缓存替换策略。文献[6]结合消息副本数，存活时间及剩余生存时间等属性确定消息的效用值，当节点缓存占满时优先删除效用值最低的消息，以实现最大化消息投递率与最小化投递延迟。然而，上述文献所提副本数估计方法利用节点相遇机会进行节点本地历史信息的交互，对消息副本数的感知存在较大时延，造成对消息传播状态估计结果存在较大误差。

针对上述相关研究的局限性，本文构建了通用节点连接状态分析模型，感知各个节点间的服务能力差异，并据此估计消息经由多个中继节点协同存储后的投递概率，进而执行缓存管理操作，合理分配有限的节点缓存资源，以提高网络运行效率。

2 节点连接状态分析模型

节点建立连接的能力越强，其为相遇节点所携带的消息提供转发与缓存服务的能力就越强。按照连接的通断状况，节点在网络中的运行时间可分为连接间隔时间与连接持续时间，因而，针对节点连接状态的分析可分解为对连接间隔时间与连接持续时间的分析，如图1所示。

图1 节点连接状态分析

(1)机会网络中的节点运动具有独立同分布的性质，节点的运动状态并不受其它节点运动状态的影响。因此，节点间在非重叠时间域内建立连接的事件相互独立，即满足式(1)所示约束条件：

综合式(1)，式(2)和式(3)可知，给定时间内，节点之间的连接建立为随机事件，其发生的次数可等效为泊松过程，进而可知节点相继建立两次连接的时间间隔服从指数分布[7]；此外，相关研究表明，节点连接持续时间同样服从指数分布[8]。由此，本文采用M/M/ 1/1模型对节点连接过程进行建模分析。

通过上述建立的节点连接状态分析模型，节点可近似获知给定消息携带节点的服务能力，从而估计消息的投递概率，为消息的转发与删除提供决策依据。

3 消息投递概率估计方法

依托构建的节点连接状态分析模型，本部分提出节点服务能力感知方法以估计消息的投递概率，并实现有效的缓存管理。

3.1 节点服务能力感知方法

节点连接到达强度大小反映了节点服务能力的强弱。节点连接持续时间具有较强的随机性，且受限于媒介共享特性，节点之间存在链路冲突。因而，节点的服务能力应充分考虑节点连接到达强度及平稳连接可用概率。

机会网络中节点可由建立的分布式连接状态分析模型感知节点自身连接状态。对于给定节点i，其平均连接建立间隔时间ti可由本地记录的连接建立次数Ni与当前的系统运行时间T得到，如式(4)所示。

进而，可获知节点i的连接到达强度λi，如式(5)所示。

如前所述，节点连接间隔时间及连接持续时间均服从指数分布，则可以采用M/M/ 1 /1模型描述本文所构建的分布式节点连接状态分析模型。节点的连接状态流图如图2。

图2 节点连接状态流图

综合考虑节点连接到达强度λi及节点连接平稳可用概率Pa，即可得到任意节点i的服务能力SAi，如式(15)所示。

3.2 消息投递概率估计方法

消息的投递状态与携带该消息的中继节点相关，在对消息的投递概率进行估计时，应综合考虑存储过该消息的中继节点服务能力。

根据本文提出的节点服务能力感知方法，可获知网络中各个节点的相对服务能力，如式(16)所示。

其中n= N Path，为消息传输路径列表Path中存储的路径数量。Pd越大则该消息投递概率就越高，继续转发与存储该消息的必要性就越小。

与机会网络消息传输基本原理相同，本文利用节点相遇带来的通信机会，在节点之间交互消息传播路径与节点服务能力信息，经过较短的收敛时间当网络状态趋于稳定后，节点可近似获知本地消息的传输路径及各个节点的服务能力。

4 自适应缓存管理策略

为了提高节点缓存利用率，优化网络性能，应优先删除投递概率较高的消息，为投递概率较低的消息分配相应的节点缓存资源。

4.1 轻量级冗余副本删除方法

机会网络中的消息投递成功之后，网络中依然存在该消息的大量冗余副本，严重影响网络运行效率。因此，本文提出轻量级冗余副本删除机制，通过在相遇的节点间交换消息信标列表ib，确定消息投递状态，从而以分布式的方式删除已成功投递消息的副本，减少网络中的消息冗余副本数量，以缓解当前网络的拥塞状况。具体实施步骤如下：

步骤 1 任意节点i在本地维持已成功投递到目标节点的消息信标列表ib(由已成功投递消息的ID号及对应消息的剩余生存时间TR构成)；

步骤 2 建立连接的节点间通过交换彼此信标列表内的信息实现信标列表的更新；

步骤 3 节点在本地缓存内将信标列表中对应的消息依次删除。

由于所采用的信标列表仅需存储极少量的信息，其相比正常消息的大小可忽略不计，因此，消息信标列表在网络中的扩散并不会给网络带来严重的控制开销。

4.2 自适应队列排序与消息删除方法

当网络负载较为严重时，仅删除节点本地的冗余副本已无法为新到达的消息提供有效服务。基于前述消息投递概率估计方法，本文提出适用于机会网络的缓存管理机制。节点建立连接之后，需交换各自的状态信息，以获知消息传输路径及网络中各个节点的服务能力，进而估计节点缓存内部消息的投递概率，并据投递概率的大小，对节点缓存队列内的消息进行排序。

若新消息到达时，节点尚有足够的缓存空间，则直接接收该消息，反之，则将新消息与缓存队列尾部消息的投递概率进行比较，若新到达的消息投递概率较低，则删除缓存队列尾部消息，以接收新到达的消息，并对缓存队列中消息按照投递概率进行自适应排序，否则，拒绝接收该消息。

本文所提自适应缓存管理策略伪代码如下表 1所示。

表1 自适应缓存管理策略伪代码

5 仿真验证与结果分析

本部分采用机会网络环境[9,10](Opportunistic Networks Environment, ONE)验证带有消息投递概率估计的自适应缓存管理策略(Adaptive Buffer management strategy with Message Delivery Probability Estimating, ABMDPE)的有效性，并与机会网络中典型的缓存管理机制(Message Transmission Status Buffer Replacement schemes,MTSBR)[5]及传统缓存管理策略 First-In First-Drop (FIFD), Last-In First-Drop (LIFD)[11], Drop Least Remaining Life (DLRL), Drop Most Remaining Life (DMRL)进行对比。

5.1 不同网络负载状态下的性能分析

合理的缓存管理机制需具有对于不同网络负载状态的适应性，为验证所提ABMDPE机制在真实移动模型下的性能，本文采用INFOCOM2006会议的实测数据对上述各个机制的性能进行了验证。INFOCOM2006会议期间，研究人员通过为与会人员配备 iMotes来模拟会议期间人员的通信情况，iMote采用蓝牙作为通信模块，会场内总共部署了98个节点，其中 78个节点分配给参会人员，另外20个节点固定地放置在给定位置并采用外接天线的方式以作为无线接入点使用[12]。本文通过向 ONE平台中导入INFOCOM2006中的实测数据，进行了实测模型下的验证，验证结果如下所示。

随着消息产生时间间隔逐渐增大，上述6种算法的投递率均呈现上升趋势。由图 3可知，相比MTSBR及DLRL, ABMDPE机制在投递率方面可分别实现21%与42%的性能增益。

由图4可知，随着消息产生时间间隔逐渐增大，消息的平均转发次数逐渐增多，上述6种算法的投递率均呈现上升趋势。与MTSBR及DLRL两种机制相比较，ABMDPE机制可分别降低42%与57%的网络负载。

图5结果表明，随着消息产生时间间隔逐渐增大，消息的平均投递时延逐渐降低。ABMDPE机制的时延相比MTSBR机制降低了约7%，比FIFD低9%。

5.2 不同缓存空间下的性能分析

机会网络中节点缓存容量受限，而如何合理配置有限的节点缓存资源，实现网络性能的有效提升是本文的研究重点。因此，本小节主要验证所提ABMDPE机制在各种缓存资源设置下的性能。

随着缓存空间的逐渐增大，6种算法的投递率都呈现上升趋势。由图6可知，与MTSBR及DLRL机制相比，所提ABMDPE在投递率方面可分别提高24%与35%。

图3 6种算法在不同消息产生时间间隔下投递率的比较

图4 6种算法在不同消息产生时间间隔下负载率的比较

图5 6种算法在不同消息产生 时间间隔下时延的比较

缓存空间增大使得 6种算法的负载率逐渐降低。相比MTSBR及DLRL机制，ABMDPE可分别降低约53%, 46%的网络负载，结果如图7所示。

由图8可知，随着缓存空间的逐渐增大，消息的投递时延呈现逐渐降低趋势。由统计结果可知，ABMDPE机制相对MTSBR及DLRL，在时延性能方面可实现平均达25%与19%的增益。

通过构建节点连接状态分析模型，所提ABMDPE机制综合考虑了消息各个中继节点的服务能力，进而估计消息的投递概率，实现了网络资源的合理分配。MTSBR机制所提消息传播状态被动感知方法具有一定的滞后性。FIFD和LIFD两种机制仅依据消息在队列中的位置，进行简单的头部删除或尾部删除操作；DLRL和DMRL机制则分别删除最长已存活时间及最短已存活时间的消息。上述4种传统缓存管理算法缺乏有效的网络状态感知方法，对副本的删除选择具较大的盲目性。因而，所提ABMDPE机制相对上述5种算法在投递率、负载率、延迟方面均可取得较大的性能增益。

6 结束语

为充分利用机会网络有限的网络资源，进一步改善网络性能，本文提出一种消息投递概率估计的自适应缓存管理策略。通过构建节点连接状态分析模型，以分布式的方式感知节点服务能力，进而估计消息的投递概率，从而指导缓存队列的自适应管理过程。结果表明，本文提出的ABMDPE缓存管理机制能够大幅降低网络负载，提高消息成功投递率，并降低消息平均时延，实现了资源受限场景下节点缓存的合理配置。

图6 6种算法在不同缓存空间下投递率的比较

图7 6种算法在不同缓存空间下负载率的比较

图8 6种算法在不同缓存空间下时延的比较

[1] Khabbaz M J, Assi C M, and Fawaz W F. Disruption-tolerant networking: a comprehensive survey on recent developments and persisting challenges[J].IEEE Communications Surveys and Tutorials, 2012, 14(2): 607-640.

[2] Milena R and Andrew G. Efficient and adaptive congestion control for heterogeneous delay-tolerant networks[J].Ad hoc Networks, 2012, 10(7): 1322-1345.

[3] 熊永平, 孙利民, 牛建伟, 等. 机会网络[J]. 软件学报, 2009,20(1): 124-137.Xiong Y P, Sun L M, Niu J W,et al.. Opportunistic networks[J].Journal of Software, 2009, 20(1): 124-137.

[4] Jani L, Mikko P, and Jörg O. Using buffer space advertisements to avoid congestion in mobile opportunistic DTNs[C]. Proceedings of the 9th IFIP TC 6 International Conference, Vilanovala Geltru, Spain, 2011: 386-397.

[5] Yao L, Jianxin W, Shigeng Z,et al.. A buffer management scheme based on message transmission status in delay tolerant networks[C]. IEEE Globecom proceedings, Houston,USA, 2011: 1-5.

[6] Shin K and Kim S. Enhanced buffer management policy that utilises message properties for delay-tolerant networks[J].IET Communications, 2011, 5(6): 753-759.

[7] Chen Y D, Li L, Zhang Y,et al.. Fluctuations and pseudo long range dependence in network flows:a non-stationary Poisson process model[J].Chinese Physics B, 2012, 18(4):112-132.

[8] Thrasyvoulos S, Konstantinos P, and Cauligi S R.Performance analysis of mobility-assisted routing[C].Proceedings of the 7th ACM International Symposium,Florence, Italy, 2006: 49-60.

[9] Keränen A, Ott J, and Kärkkäinen T. The ONE simulator for DTN protocol evaluation[C]. The 2nd International Conference on Simulation Tools and Techniques, Rome, Italy,2009: 1-10.

[10] Vascon G J, Farid F, and Joel P C. Impact of vehicle movement models on VDTN routing strategies for rural connectivity[J].International Journal of Mobile Network Design and Innovation, 2009, 3(2): 103-111.

[11] Zhang X L, Neglia G, Kurose J,et al.. Performance modeling of epidemic routing[J].Computer Networks, 2007, 51(10):2867-2891.

[12] James S, Richard G, Jon C,et al.. CRAWDAD metadata structure[DB/OL]. http://crawdad.cs.dartmouth.edu/cambridge/haggle/imote/infocom, 2006, 2009-05.