对机会网络缓存管理机制性能分析的异同研究

引言

近年来,随着无线通信技术飞速发展,智能手机、PDA等个人手持设备的普及,以及硬件技术不断提升,使得普通节点可以直接通信,无需通过中心节点进行中继转发,这使分布式自组织网成为可能。在这种背景下,人们设计了无需中心控制节点,仅依赖普通节点完成通信的移动自组织网络(mobile ad hoc network, MANET)[1]。在移动自组织网络中,建立端到端的完整路径是实现消息转发的首要前提,但随时间和位置不断变化的移动模式以及受限的传播条件等多种因素均会中断通信链路,导致既定的完整转发路径无法得到保证。区别于MANET的通信模式“存储—转发”,研究者提出了以“存储—携带—转发”为通信模式的机会网络[23],其利用运动过程中节点带来的相遇机会进行转发消息。

1机会网络

1.1机会网络概念

在间断连接的机会网络中,节点间无需保证端到端的链路,仅需利用节点运动过程中带来的相遇机会进行消息的中继转发,直至目的节点成功接收到该消息,因此,此种网络架构下的通信模式能够有效克服MANET网络中源节点与目的节点之间路径断裂的问题。然而,消息转发过程中,多个节点将作为中继节点对需要转发的消息进行保存并携带,可能导致消息传输过程的延迟较大。目前关于机会网络的研究已引起研究人员的广泛关注,随着研究的深入,机会网络主要研究方向包括缓存管理机制、消息转发机制、能量有效控制和信任管理机制。

1.2机会网络体系架构

由于机会网络的特殊性,为延时很小的Internet设计的TCP/IP协议不再适用于机会网络。研究人员将传统的5层协议TCP/IP协议进行修改,在应用层和传输层之间叠加了Bundle层[4]。机会网络传输示意图如图1所示。当节点收到经逐层解封后的消息,判别当前节点是否为该消息的目的节点,若是,则利用对应的端口传输至应用层;若该节点不是消息的目的节点,寻找“下一跳”中继节点。

相比端到端连接的传统网络而言,机会网络对节点有限缓存资源的合理利用更敏感。其主要原因是传统网络中利用节点间端到端的连接,目的节点成功接收消息之后,发送ACK通知源节点消息已成功投递,进而抑制源端消息重发。但是在间断连接的机会网络中,为了保证消息能够以较高的概率传输至目的节点,需向网络中注入多个消息副本,以多路径并行的方式进行传输。同时,为了避免增加额外的网络负载,消息到达目的节点后,通常并不会向各个中继节点发送ACK以通知其他节点删除已经完成传输的消息副本。在没有合理高效的缓存管理机制对消息进行处理的情况下,节点缓存溢出时会盲目地随机选择删除大量的消息,而且这种现象常会周而复始地持续进行下去,由滚雪球的复利法则可知,势必直接导致消息投递率急剧下降和网络负载急剧增加。由此可见,设计适合于机会网络的缓存管理机制至关重要。

本文将对机会网络中经典的缓存管理机制进行介绍,同时对其各自的优缺点给出进一步分析。

2.1预分配重要因子缓存管理机制

在文献[5]中,作者按照预先给消息分配的固定重要因子降序排列,即重要因子最低的消息位于队列尾部。这是为了避免重要程度较高的消息提前溢出,影响网络整体性能。因此,当消息到达节点缓存,且剩余缓存大小不足以接收该消息时,则比较缓存消息与需接收消息的重要因子,若需接收消息的重要因子较高,则从重要因子最低的消息开始执行删除操作,直到为该消息留出足够的缓存空间。缓存操作的具体过程如图2所示,图2中,I(Mi)为消息i的重要因子,Mi-3为将要到达的消息,若I(M1) 2.2消息传播状态缓存替换机制

在文献[6]中,作者根据微观经济学中的边际效用递减规律提出了一种缓存管理机制。边际效用递减规律如图3所示。图3中,TU代表总体效用,MU代表边际效用,Q代表消费量。可以看出,随着Q的增加,边际效用(MU)一直是递减的。当边际效用之后,消费量的增加反而使得总体效用减少。作者将这种思想引入机会网络,提出当某个消息在网络的已存在副本数过多时,继续转发该消息的副本数不能显着提高消息投递率,反而占用了其他消息的网络资源,会使得网络的整体性能下降。因此,为实现最大化网络资源的利用,提出基于消息在网络中传播状态的缓存管理机制。

图3边际效用递减规律图作者假设消息在网络中扩散的次数决定了其被成功投递的概率,消息在网络中扩散的程度越高,表明其成功投递的概率越高,反而越低,并从理论上证明了此假设。因此,利用节点自身的记录信息以及与其相遇节点交互学习时获取的信息近似估计消息在网络中副本数。基于所证假设的基础上,当节点缓存已满时,优先删除网络中副本数目较多的消息,腾出足够容纳将要到达消息的空间。当消息的副本数目相等时,则按照消息在网络中传播的速度进行依次删除。消息的传播速度描述了单位时间内该消息被传播的次数。计算方法如式(1)所示。Rate=KmTTLinit-TTL(1)式(1)中:Km为节点通过相遇交互获知的消息m在网络中传播的次数;TTLinit为产生消息m时初始化的最大能够存活时间;TTL为消息m在网络中能够继续存活的时间。

该机制从理论上证明了消息副本数目与消息投递概率之间的关系。但受限于节点的缓存能力,存储的消息数目极其有限,使得仅利用节点记录的信息无法正确感知消息副本数目这个全局变量。如果可以考虑网络的运行状态,提出更好的方法准确估计消息副本数目这一全局变量,一定能够提高网络性能。

2.3缓存替换决策

文献[7]中,作者提出需利用网络全局信息以及消息在网络中的传播状态考虑消息的删除,才能全面有效地提高网络性能。在没有获知整个网络运行状态的情况下,单个节点无法准确估计自身与其他节点的相遇情况,以及缓存中消息的状态。为了获知近似全局网络的信息,每个节点维护自身及其他节点的历史信息,并与其他相遇之后交互各自保留的节点历史信息。

根据节点在随机移动模型下,节点间的相遇间隔服从指数分布的理论,以及通过相遇获知的历史信息,推导出满足全网投递概率期望值最大及全网时延期望值最小的公式,当缓存溢出时,以最大化投递概率或最小化平均时延作为优化目标选择消息进行删除。

为实现消息成功投递概率最大化,需选择本地缓存中消息效用值最低消息删除,其效用值的计算如式(2)所示。

Vdelivery=1-mi(Ti)L-1λRiexp(-λni(Ti)Ri) (2)

若需满足消息投递时延最小化,按照式(3)选择消息进行删除。

Vdelay=1ni(Ti)2λ(1-mi(Ti)L-1)(3)

式(2)和式(3)中:mi(Ti)表示当消息生存时间为T时,历史转发过消息i的节点个数;ni(Ti)为经过时间Ti后消息i在网络中的数量;L为网络中的节点个数;λ为节点间的相遇概率;R为消息的剩余生存时间。

显然,在分布式运行的机会网络中,无法获知网络的全局信息。作者只能通过网络运行的历史信息近似地估计mi(Ti)与ni(Ti)。

2.4基于消息重要程度的缓存管理机制

文献[8]中,作者为了 最有效地利用节点有限的缓存资源,在缓存管理时,将消息的处理优先级分为转发优先级与删除优先级2种。

当2个节点相遇之后,首先将对方节点没有缓存的消息按照自身转发消息的概率排序,使得概率值较大的消息优先获得转发权。与传统的随机选择转发消息的方式不同,利用上述这种转发方式,最大化利用了网络资源。根据消息的跳数、大小以及生存时间确定消息的转发顺序。计算如式(4)所示。

Pkf=1Hk×TTLk×sk(4)

式(4)中:Hk指消息的跳数;TTLk表示消息的生存时间;sk指消息的大小。

当缓存空间不足时,优先删除消息副本数与消息大小比值最小的消息,以保证副本数较少且占用缓存空间较大的消息优先替换,最大化存储资源的利用率。消息删除的优先级如式(5)所示。Pkd=Lksk(5)式(5)中:Pkd指消息的删除优先级;Lk指消息的副本数。

所提出的机制利用节点之间的相遇机会获知网络中消息副本数目,但受限于节点的缓存能力,存储的消息数目极其有限,消息副本数目获知的滞后性严重,直接影响消息的处理,进而使得网络性能恶化。同时,消息的传输过程受到多个因素影响,单纯地使用消息副本数与消息大小无法准确反映消息投递状态。

2.5基于动态预测的多队列缓存管理机制

文献[9]提出了基于动态预测的多队列缓存管理机制,所提出的机制将本地缓存空间等分为3个队列,将相遇节点为消息目的节点的消息位于最高等级队列中,当前节点成功投递该消息概率较高的消息位于次高等级队列中,投递概率较低的消息位于最低等级队列中。当节点空闲缓存大小不足时,优先替换投递概率位于最低等级队列中的消息。若最低等级队列为空时,则选择替换位于次等级队列中的消息,次等级队列中消息仍为空时,需判断将要接收的消息的目的节点是否为该节点,如果是该节点,那么删除位于最高等级队列中消息存储到达的消息,否则拒绝接收该消息。

但是该机制需预先将缓存区域根据预设的固定阈值的方式进行划分,阈值的大小设定直接影响缓存资源的利用,阈值选取的合理性会造成有限资源的浪费,难以适应复杂的间断连接无线网络环境。

2.6基于节点连接状态的缓存管理机制

在文献[10]中,作者提出了基于节点连接状态的机会网络缓存管理机制,该机制具体包含消息转发和消息删除2个部分。根据消息的效用值大小确定缓存中各个消息的处理优先级,以提高缓存资源的利用率。

当节点x与y相遇之后,首先节点x将缓存中消息的概要向量发给节点y,y将自身没有缓存的消息概要向量及成功投递消息的概率发给节点x。比较节点x及y成功投递消息的概率值大小,将消息转发到投递概率较高的节点,达到提高消息投递概率的目的。

作者认为当前节点成功投递该消息概率与相遇节点成功投递该消息概率的差值越大,则表明消息被成功投递的概率越高。进而,当节点缓存空间不足的时候,优先删除成功投递概率差值最大的消息。所提出的机制通过比较效用值的大小决策消息是否继续携带,能够为效用值更高的消息充分地预留存储资源,达到了高效利用节点缓存能力的目的。但是若当前节点与相遇节点成功投递该消息的概率都较低,则消息被成功投递的概率也较低,而其成功投递概率差值却较大,则节点优先选择删除此类消息,导致其投递率下降。

3结束语

本文首先通过对机会网络的研究背景、基本概念以及体系架构进行了简要的介绍及分析,接着对现有的利用机会网络特性设计的缓存管理机制进行总结,并从机制的网络性能方面进行了优缺点的比较分析。

机会网络中缓存管理机制的实质就是针对节点缓存能力有限的情况,设计高效的缓存管理机制,达到最大化网络资源的利用和全网性能的提升。针对机会网络特点,总结其缓存管理机制的未来设计目标应主要满足2个方面。1)协助节点存储重要程度更高的消息。重要程度主要从以下两方面衡量,一方面是根据历史信息预测该消息在网络中已成功投递的概率;另一方面是考虑此次存储是否有利于消息快速到达目的节点。2)合理选择及准确估计参数是关键。动态性极强的机会网络中,由于各种恶劣的网络环境的限制,如间断连接、节点处理能力及通信持续时间等,使准确动态地估计参数面临挑战。因此,需在参数的可用性和参数的估计代价之间做权衡