带有节点状态估计的间断连接无线网络缓存管理策略

吴大鹏白 娜 王汝言

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

带有节点状态估计的间断连接无线网络缓存管理策略

吴大鹏*白 娜 王汝言

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

针对间断连接无线网络中的节点缓存资源有限的问题，该文提出一种适用于间断连接无线网络的缓存管理机制。根据运动过程中所获得的网络状态信息，各个节点以分布式的方式估计给定节点与其他节点直接及间接连接状态、节点服务率以及节点连通强度，动态感知各个节点服务能力的差异，同时预测当前节点成功投递该消息的概率以感知消息的效用值，从而执行缓存管理操作。结果表明，与其他缓存管理机制相比，所提出的缓存管理机制不仅能够有效降低投递开销，同时大幅度地提高了消息成功投递率。

间断连接无线网络；缓存管理；消息效用值；节点服务能力

1 引言

移动自组织网络(Mobile Ad hoc NETwork, MANET)[1]中，建立端到端连接是节点实现消息转发的首要前提。间断连接无线网络体系架构，以更加灵活的“存储-携带-转发”模式实现信息传输[2]，解决了MANET网络中源节点与目的节点之间路径频繁断裂所导致的通信中断问题。

为了保证消息传输的可靠性，通常需要在网络中注入多个消息副本[3,4]，各个副本通过多路径并行的方式进行传输。随着节点不断与其他节点相遇，其所携带消息副本数量逐渐增加，将导致有限的缓存被冗余消息副本浪费。因此，如何在节点的处理能力及存储能力有限的情况下，通过高效的缓存管理机制优化网络性能具有重要研究意义。

针对以上问题，文献[5]提出了带有消息投递概率感知的消息替换机制，该方法根据消息投递概率阈值将缓存空间等分为3个大小相等的区域，优先删除投递概率位于最低等级区域中的消息。但是该机制需预先等分缓存区域和设定阈值，难以适应复杂的间断连接无线网络环境。文献[6]在喷洒等待(Spray and Wait, SnW)[7]消息转发策略的基础上提出了相应的缓存管理策略，优先删除消息副本数与消息大小比值最小的消息，以保证副本数较少且占用缓存空间较大的消息优先替换。但是该方法需要预先设定消息副本数的初始值，扩展性较差。文献[8]认为当前节点成功投递该消息概率与相遇节点成功投递该消息概率的差值越大，则表明消息被成功投递的概率越高。当缓存溢出时，优先删除成功投递概率差值最大的消息。但是若当前节点与相遇节点成功投递该消息的概率都较低，而其成功投递概率差值却较大，则节点优先选择删除此类消息，导致消息成功投递概率下降。

为了提高有限缓存资源的利用率，本文提出一种带有节点状态估计的间断连接无线网络缓存管理机制(Intermittent connectivity wireless network Cache Management mechanism with Node Status evaluation, NS-ICM)，在充分考虑节点社会属性的基础上[9]，根据运动过程中所获知的连接状态历史信息，各个节点以分布式的方式估计自身的服务能力及当前节点成功投递该消息的概率，继而感知消息经由多个中继节点协同存储后的效用值，从而执行缓存管理操作。结果表明所提出的机制在提升投递率的同时降低了网络开销。

2 节点服务能力估计

显然，对于间接连接无线网络中的消息转发过程来说，中继节点服务能力直接影响消息成功投递的概率。利用服务能力较强的中继节点完成消息的传输，将极大地降低网络开销。

目前，节点服务能力的评估方法大部分以节点之间建立连接的次数作为衡量标准。但是，此类方法单一地考虑了节点之间的直接连接次数而忽略了间接相遇状态及消息转发数量等因素，无法准确地衡量节点服务能力。考虑到间断连接无线网络中节点的聚集特性，本文将节点间的相遇次数及相遇持续时间高于其历史运动过程均值的节点定义为其邻居节点，若当前节点与其他节点的直接连接次数较少，而其邻居节点数量较多，则可通过邻居节点与其他节点相遇机会完成消息转发，即可以通过其邻居节点的数量间接评估节点的服务能力。此外，为更精确地评估节点服务能力，本文进一步考虑了节点间相遇之后节点间的连通强度以及消息服务率。

2.1 邻居节点度估计

邻居节点数量直接影响给定节点的消息转发效率。需要通过节点自身记录的历史信息以及与其他节点相遇时所获取的状态信息来估计相遇次数和邻居节点度数。在节点的本地信息表中，每个相遇节点对应两个表项，分别为相遇节点的ID及相遇次数，其中相遇次数呈降序排列，如图1所示。

图1 节点自身及相遇节点的历史信息

节点i与邻居节点的相遇次数总和可按照式(1)所示方式进行计算，其中NeiLi为节点i的邻居节点集合，c(v)为节点i与节点v的相遇次数。

进而，根据式(2)可获知节点i的邻居节点度数之和，其中deg(v)为节点v的度数，反映了给定节点与其他节点的相遇频繁度。由于间断连接无线网络中的节点持续地在网络中移动，与其产生连接的节点列表最终趋于稳定，不同节点的相遇节点列表将出现相同的情况，则无法判定节点之间连接的紧密程度，因此传统的按照邻居列表大小评估节点度的方法无法准确区分邻居节点的活跃度。本文通过将邻居节点和其他节点的相遇次数与节点的平均相遇次数进行比较获知deg(v)。

对于节点i的邻居列表中节点j所对应的表项来说，节点j的邻居列表为NeiLj，将节点j与自身邻居列表中所有节点的相遇次数记为{c(vk)|k=1, 2,…,Nj,vk∈NeiLj}，同时记节点i与其邻居节点的相遇次数平均值为avei，若c(vk)＞avei，则deg(v)加1，依次比较，最终得到deg(v)。

2.2 节点连通强度的估计

节点间连通强度定义为节点之间的链路持续时间与给定时间的比值。该参数描述了给定节点为其他节点提供服务的时间长度，显然，连通强度越大，则表明节点服务能力越强。对于给定节点i，其第n次连接持续时间tuis(n)为

根据本地记录的运动过程中历史信息，节点i可得到m个相关节点在给定时间T内处于通信链路持续时间总和sum为

那么，根据上述定义在给定时间T内，节点i的连通强度λi可表示为节点处于通信链路持续时间总和与给定时间T的比值：

在相同时间段内，节点间连接持续时间越长，则其能够为其他节点提供更多的消息转发机会。

2.3 节点服务速率估计

节点服务速率定义为单位时间内节点转发的消息数目。若节点i在第n次通信链路持续时间为(n)，成功转发的消息数量为an，则第n次链路持续时间内，每个消息的转发时间为

那么节点i第n次建立连接时为其他节点所提供服务的速率即为τi(n)的倒数，如式(7)所示。

由于节点间的通信链路持续时间具有不确定性，同时成功转发的消息数量也具有较强随机性，因此取其统计平均值以衡量节点服务速率，如式(8)所示。

如前所述，间断连接无线网络中的消息转发过程需要多个中继节点辅助，各个节点的邻居节点可有效地将消息扩散至网络中的其他节点。因此，为了更全面地反映节点间的相遇情况，本文充分考虑直接相遇次数sumi与间接相遇次数Degi两个方面因素来衡量节点之间的相遇次数。进而，可根据节点i处于断开状态的时间长度T-λiT 来确定其相遇概率。更进一步地，相遇概率参数仅仅反映了给定时间内的节点相遇次数，忽略了节点相遇之后节点服务速率。当且仅当节点具有较高的相遇频率及服务速率的情况下，节点才具有较强的服务能力。综合上述因素，给定时间T内任意节点i的服务能力SerAi可采用式(9)所示方法进行估计。

3 消息投递概率估计

中继节点的服务能力直接反映了消息的投递状态，消息携带节点的服务能力越强，网络中消息的扩散程度越高，则消息成功投递的概率越高，从而大大降低了此类消息缓存及转发的必要性，但是，若持续地删除此类消息副本会对其成功投递产生较大的影响。因此，为合理地删除冗余消息副本，需要考虑当前节点在消息剩余存活时间内成功投递该消息的概率。

假设节点i与消息目的节点d之间建立连接的间隔时间可按照式(10)所示方式表示，式中，t0指节点i与消息目的节点d上次相遇时间，Xi(t)表示节点i在t时刻的坐标，R为通信范围。

在消息存活时间内，判断当前节点是否能够成功投递该消息需获知消息在网络中剩余存活时间，其计算方法如式(11)所示。其中tm指剩余存活时间，tTTL指消息的生存时间，tge指消息的产生时间，t指当前网络运行时间。

若节点与目的节点的相遇间隔时间小于消息的剩余存活时间，则表明此节点能够将消息成功投递，其投递概率定义如式(12)所示。

继而，利用马尔科夫不等式，通过比较消息的剩余存活时间及节点与目的节点的相遇间隔时间的期望值E(MTi,d)，可获知当前节点未能成功投递该消息的概率为

m P具体可表示为

4 NS-ICM缓存管理机制

在上述节点服务能力估计方法及消息投递概率估计方法的基础上，本节提出了带有节点状态估计的间断连接无线网络缓存管理机制，该机制能够动态地估计节点服务能力及节点投递消息的概率，进而感知消息继续转发的效用值。节点根据自身所获知的网络状态信息实时更新消息效用值，进而确定缓存中各个消息的处理优先级，以提高缓存资源的利用率。

4.1 消息转发决策

在动态性极强的间断连接无线网络中节点无法通过单次连接完成全部消息的转发。为了合理地选择消息优先转发，所提出的缓存管理机制充分考虑了传输容量与消息大小之间的关系，具体如式(16)所示。

当两节点相遇之后，将对方没有缓存的消息根据式(17)获知的优先级降序排列,其中，Pm为消息m的转发优先级，其根据消息转发概率和链路容量决定，具体定义如下：

4.2 消息携带决策

在消息携带决策过程中，所提出的机制通过比较效用值的大小决策消息是否继续携带，效用值可根据消息携带节点的平均服务能力及消息投递概率的估计值获知，进而确定是否继续缓存该消息。

携带节点的平均服务能力计算方法如式(18)所示。式中Qt(m)表示部分携带消息m节点的集合，h表示集合中节点的个数，表示此集合节点的平均服务能力。

对式(18)进行归一化处理之后，根据当前节点未能成功投递该消息的概率，可求得效用值V(m)。

式中，Amax指消息携带节点服务能力最大值，Am指存储消息m的中继节点的平均服务能力。α是节点服务能力对消息效用值的影响因子，β是节点成功投递消息概率对消息效用值的影响因子。本文通过定义拉格朗日(Lagrange)函数以及约束条件确定α与β的取值，使得消息效用V(m)取得最大值。

为了分析方便，设α,β满足单位化约束条件：

首先构造Lagrange函数，如式(20)所示。

求解方程组式(21)，并进行归一化处理得到权重值α′与β′：

为了避免效用值较高的消息提前溢出则优先从效用值最低的消息开始执行删除操作，直到可以接收该消息。接收消息m所需要的缓存空间计算方法如式(23)所示。

式中，B0指节点的空闲缓存大小，Sm指消息m的大小，Sl指节点缓存中消息l的大小，V(l)指消息l的效用值。

4.3 消息队列管理

为了确定给定消息所属部分，本文利用节点传输容量估计值设定动态阈值，考虑到消息大小及传输容量，所设定的阈值为式中，th指阈值的大小，Smin指当前节点缓存中消息大小的最小值，指节点i记录的第r次可传输的容量，通过求均值获得节点i可传输的平均容量。

节点相遇之后，对消息的具体处理过程如图2所示：节点缓存了n个消息，按照其跳数升序排列，并将已排序阈值前的消息m1,m2,…,mi划分为待转发部分，且按照消息的投递概率Pde(mi)进行降序排列；同时，将缓存中剩余的消息划分为待删除部分，并按照消息效用值的大小V(mi)设定消息的删除顺序。由式(24)可以看出，当节点的传输容量随着网络运行状态的变化，阈值th的大小也随之变化。该方法能够充分利用网络资源，改善了网络性能。

带有节点状态估计的间断连接无线网络缓存管理机制的伪代码如表1所示。

5 数值分析

图2 消息队列管理

本文采用网络环境(Opportunistic Network Environment, ONE)[10]对所提出的缓存管理机制NS-ICM进行了网络性能的验证。其中节点间的路由协议采用泛洪算法Epidemic，仿真参数具体设置如表2所示。

本文以基于消息传输状态缓存管理机制(MTSBR)[11]以及基于删除头部Prophet算法[12]作为对比算法。其中MTSBR机制中，节点以副本数量为依据，优先删除网络中副本数量较多的消息，以达到为其他消息预留缓存资源的目的。此外，对于采用头部删除的Prophet机制来说，节点选择接收时间最早的消息进行删除。

由图3可知，与MTSBR及Prophet-FIFO机制相比，本文所提NS-ICM机制在投递率方面可分别提高25.9%与31.2%。Prophet-FIFO机制由于未考虑节点间连接的时序特性，其相遇概率预测的准确性得不到保障，导致其投递概率较低。NS-ICM机制根据当前消息传输状态、相遇节点服务能力等因素确定其缓存内各个消息的优先级，使得中继节点的选择更具合理性，其投递率较高。MTSBR机制受节点缓存能力及消息传输方式的影响，获得消息副本的时间相对滞后，导致其投递概率在缓存较小的情况下并不理想。

表1 间断连接无线网络缓存管理机制伪代码

表2 仿真参数表

图4描述了3种机制在不同缓存容量下的投递开销性能。由结果可知，3种机制的投递开销随着节点缓存容量不断增加均呈下降趋势。Prophet-FIFO机制在节点缓存被占用之后，其单纯地根据接收时间删除消息，容易导致节点将重要程度较高的消息错误地删除，使得其开销大于NS-ICM机制。与之相比，NS-ICM机制优先删除具有高服务能力节点所携带过的消息，使得消息冗余度保持在较低的水平。因此，投递开销始终维持在85%～105%之间。MTSBR机制无法准确获得当前网络中给定消息的副本数量，难以进一步判定其冗余程度并合理地删除消息副本，导致消息的转发次数增加。NSICM与其他两种机制相比，开销分别降低了12.1 %和25.2 %，有效地改善了网络性能。

图3 不同缓存空间下投递率的比较

图4 不同缓存空间下投递开销的比较

图5 不同缓存空间下投递时延的比较

图5给出了所提出的缓存管理机制与其他两种机制在不同缓存容量下的消息平均投递时延，由结果可知，Prophet-FIFO机制比本文所提出的缓存管理机制NS-ICM在时延方面低24.2%。本文的NS-ICM在消息转发时考虑了携带消息节点的平均服务能力及投递概率等综合信息，进而更加合理地选择中继节点。与Prophet-FIFO机制相比，NS-ICM中的节点需要执行中继节点选择过程，导致消息需要在节点处的等待时间增加。但是与MTSBR机制相比，NS-ICM的时延降低了14.3 %。其原因在于MTSBR机制单纯地根据消息在网络中副本数目选择所要删除的消息，容易造成较重要消息的数量迅速地减少，导致其投递时延增大。

6 结束语

本文提出了节点服务能力以及消息投递概率估计方法，进而设计了带有节点状态估计的间断连接无线网络缓存管理机制，充分利用消息携带节点的服务能力合理地选择中继节点，并根据当前网络中的消息传输状态删除效用值较低的消息，从而为重要程度较高的消息预留缓存资源。仿真结果表明，本文提出的缓存管理机制不仅能有效降低投递开销，同时提高了消息的成功投递率。

[1] Darshana P and Vandana V. Security enhancement of AODV protocol for mobile Ad hoc network[J]. International Journal of Application or Innovation in Engineering and Management, 2013, 2(1): 317-321.

[2] Li Z and Shen H Y. SEDUM: exploiting social networks in utility-based distributed routing for DTNs[J]. IEEE Transactions on Computers, 2013, 62(1): 83-97.

[3] Ayub Q, Rashid S, and Zahid M S M. MinHop (MH) transmission strategy to optimized performance of epidemic routing protocol[J]. Journal of Computer Science and Technology, 2011, 11(9): 35-42.

[4] Wang Y S, Yang W S, and Wu J. Analysis of a hypercube-based social feature multipath routing in delay tolerant networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(9): 1706-1716.

[5] Rashid S, Hanan A A, Ayub Q, et al.. Dynamic prediction based multi queue (DPMQ) drop policy for probabilistic routing protocols of delay tolerant network[J]. Journal of Network and Computer Applications, 2013, 36(5): 1395-1402.

[6] Prodhan A T, Das R, Kabir H, et al.. TTL based routing in opportunistic networks[J]. Journal of Network and Computer Applications, 2011, 34(5): 1660-1670.

[7] Pan D R, Lin M, Chen L J, et al.. An improved spray and wait with probability choice routing for opportunistic networks[J]. Journal of Networks, 2012, 7(9): 1486-1492.

[8] Ayub Q, Rashid S, Soperi M Z M, et al.. Contact quality based forwarding strategy for delay tolerant network[J]. Journal of Network and Computer Applications, 2014, 39(3): 302-309.

[9] Pan H, Jon C, and Eiko Y. BUBBLE rap: social-based forwarding in delay-tolerant networks[J]. IEEE Transactions on Mobile Computing, 2011, 10(11): 1576-1589.

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

[11] Liu Y, Wang J X, Zhang S G, et al.. A buffer management scheme based on message transmission status in delay tolerant networks[C]. Globecom2011, Houston, 2011: 1-5.

[12] Lindgren A, Doria A, and Schelen O. Probabilistic routing in intermittently connected networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2003, 7(3): 19-20.

吴大鹏： 男，1979年生，副教授，博士，研究方向为泛在无线网络、社会计算、互联网服务质量控制.

白 娜： 女，1988年生，硕士，研究方向为机会网络.

王汝言： 男，1969年生，教授，博士，研究方向为空间光通信、光网络理论与技术、光信息处理、通信网络可靠性与故障管理.

Cache Management Mechanism with Node Status Evaluation for Intermittently Connected Wireless Networks

Wu Da-peng Bai Na Wang Ru-yan
(Broadband Ubiquitous Network Research Laboratory, Chongqing University of Posts and Telecommunication, Chongqing 400065, China)

Considering the limited cache resources of nodes in intermittently connected wireless networks, a cache management mechanism is proposed based on node state estimate. The direct and indirect connection status, service rate and connectivity degree between the given nodes can be evaluated in a distributed manner, according to the network state monitored during the movement. Further, the difference of service ability of each node can be determined dynamically. Furthermore, the probability of message successfully delivered by the current node and the utility for the given message can be estimated. Consequently, cache management operations are executed reasonably. Simulation results show that the proposed mechanism does not only constrain the overhead ratio effectively but also enhance the message delivery ratio, compared with other mechanisms.

Intermittently connected wireless network; Cache management; Message utility; Nodeservice ability

TP393

A

1009-5896(2015)02-0443-06

10.11999/JEIT140333

2014-03-13收到，2014-05-30改回

国家自然科学基金(61371097)，重庆市自然科学重点基金(CSTC2013JJB40001, CSTC2013JJB40006)，重庆市青年科技人才培养计划(CSTC2014KJRC-QNRC40001)和重邮青年自然科学基金(A2012-93)资助课题

*通信作者：吴大鹏 wudapengphd@gmail.com