消息替换风险动态感知的缓存管理策略

黄沛昱，应 俊

(重庆邮电大学光电工程学院，重庆 400065)

0 引言

目前，研究人员提出了多种消息替换方法，文献［2］将缓存空间划分为若干个子空间并赋予不同的优先级，当缓存溢出时，优先级最低子空间中的消息会被丢弃。但是，划分子空间的标准界限难以衡量。文献［3］所提出的策略选择剩余生存时间最小的消息进行替换，但消息的投递状态与多个因素直接相关，单独使用剩余生存时间无法准确反映消息的当前状态。利用随机运动模型下节点相遇时间间隔成指数分布的性质，文献［4］提出了基于消息投递概率的多队列消息删除管理机制，将缓存空间等分为3个空间区域，当空闲缓存大小不足时，优先删除等级最低的消息。但是该机制需预先将缓存区域等分，会造成有限资源的浪费。此外阈值的设定也是关键，阈值设置过小对于缓存管理没有实质改进，过大又会使得没有成功投递的消息被删除，导致消息的成功投递下降。文献［5］根据经济学中的边际效应理论，认为消息在网络中副本数量越多，其成功投递到目的节点的概率越大，进而设计了基于副本数量的消息替换策略。

显然，机会网络中的节点运行环境复杂，消息转发过程受到多个方面因素的影响。因此，单纯地根据某个条件来确定消息副本的替换难以有效地提高有限缓存的利用率。本文综合考虑了消息的已生存时间(time to live，TTL)、跳数、副本数以及区域概率4个参数，对消息的投递状态及替换风险进行了估计，提出了一种基于消息替换风险估计的缓存管理策略(message replicating risk aware cache management，MRRCM)。

1 投递状态估计

如前所述，单纯地根据某个消息状态参数无法准确获知其在网络中的传播状态［6］，此外，此种“存储－携带－转发”架构下的消息传输状态与给定消息在某个区域的密度及区域内节点与消息目的节点的相遇概率直接相关，称之为消息i的区域概率。为了能够准确地评估消息的传输状态，本文综合考虑消息的已生存时间、跳数、副本数及区域概率4个参数，以分布式的方式实现传输状态估计，进而为消息替换提供依据。

1.1 权重分配

考虑到上述因素对于消息传输状态的影响程度并不相同，本文运用层次分析法(analytic hierarchy process，AHP)确定各个参数的权重。

1 )构造判断矩阵。判断矩阵如(1)式所示，表示本层所有因素针对上一层某一个因素相对重要性的比较。层次结构如图1所示，C1，C2，C3，C4代表各因素对目标O的重要性。

图1 层次结构图Fig.1 Hierarchical chart

C1为消息已生存时间对传输状态的影响因子，C2为跳数H对传输状态的影响因子，该参数能够反映消息的转发深度，显然，转发深度较高的消息具有更高的成功投递概率［7］。与文献［6］所得到的结论类似，即以跳数为依据所获得的消息投递状态更为准确，本文所建立的层次模型中，置a12=1/2。C3表示消息副本数M对其传输状态的影响因子。根据机会网络消息转发过程的基本原理，若某个消息在网络中的副本数越多，其成功投递的概率也随之增大［8］。相比于 C1，C2，消息副本的数量能够更直接地反映其自身的传输状态，因此，置a13=1/5，a23=1/3。C4表示区域密度及目的节点对于给定区域活跃程度对消息传输状态的影响因子。消息传输包括存储、携带及转发3个过程，相比于 C1，C2，区域概率能够反映更多的网络连接状态信息，因此，置a14=1/3，a24=1/2。而C3在感知范围上显著大于C4，置 a34=2。

2 )权重计算。根据判断矩阵，可得最大特征根λ所对应的特征向量w，如式(2)所示。

这件事情翠姨是晓得的，而今天又见了我的哥哥，她不能不想哥哥大概是那样看她的。她自觉地觉得自己的命运不会好的。现在翠姨自己已经订了婚，是一个人的未婚妻；二则她是出了嫁的寡妇的女儿，她自己一天把这个背了不知有多少遍，她记得清清楚楚。

所求特征向量w经归一化即为各因素的权重分配。本文使用雅克比法得到 w为(0.0882，0.157，0.4829，0.272)T，λ =4.015。

3 )一致性检测。为了验证以上得到的权重分配结果是否合理，需要对判断矩阵进行一致性检测。一致性指标定义如式(3)所示

(3)式中:CI为一致性指标;n为矩阵维数。代入数值得到CI=0.005。当CI=0时，有完全的一致性，CI接近于0，表示判断矩阵有满意的一致性，CI越大，不一致程度越严重。为了衡量CI的大小，引入随机一致性指标RI，1～9阶判断矩阵的RI值如表1所示。

表1 平均随机一致性指标RI的值Tab.1 Values ofmean random consistency index RI

1.2 消息投递状态估计

如前所述，消息i的各维状态参数数值越大，则该消息成功投递的概率越高。因此，准确估计给定消息的传输状态是评估消息冗余程度的关键。给定消息的状态参数TTL和H可由封装在分组头部的消息产生时间及消息传递路径获知。状态参数M及P的确定需要节点获知网络中全部节点的状态信息，即网络中所有节点的存储情况及区域内的节点相遇情况。受限于机会网络的分布式特性，节点无法采用泛洪的方式将自身的状态信息在整个网络范围内及时、准确地扩散，因此，本文通过节点间的交互，以尽力而为的方式感知网络状态信息。每个节点本地维护相应的节点信息列表，其中相遇信息列表记录了该节点与网络中其余节点的相遇情况，包括相遇节点地址及相遇时间，历史消息ID列表记录了节点存储过的消息。节点相遇之后将转发更新时间大于对方的节点信息。按照上述方法，节点可近似获得网络中各个节点的状态信息。

通过统计列表中存储消息i的节点数量，节点可以得到消息i的状态参数M在t时刻的估计值。文献［9］提出使用全网消息经历T时间之后的平均m(T)值来估计消息i在T时刻的副本数mi(T)，并认为其能更准确地估计消息i被保存的次数。文献［10］对估计的准确度进行了理论推导及仿真验证，推导得到m(T)服从正态分布，由正态分布性质可知，其参数数值绝大部分都分布在均值附近，可用其均值估计其分布中的各个数据的大小，即

此外，本文中所提出的消息区域概率估计过程分为2个部分，分别为消息i的区域密度及消息i的目的节点对于该区域的活跃程度。消息的局部密度可通过对本地保存列表内的信息获知。根据T时间内相遇节点的个数N(T)及其中携带有消息i的节点个数 Mi(T)，可获知消息 i的局部密度MDi(T)，如式(4)所示。

区域活跃度Ai(T)描述了消息i的目的节点在T时间内与区域内N(T)个节点的相遇次数，通过对这N(T)个节点的相遇信息列表进行查询，可以得到相遇次数C(T)，其估计方法如式(5)所示。

根据上述得到的权重，通过式(6)可以得到队列中各个消息的状态加权和。

(6)式中:wj为对应的权重大小;Cij为消息i的状态。由于状态TTL，H，M，P对于消息投递状态的影响均为正相关。因此，根据式(6)所得到的加权和越大，则表明消息被成功投递的可能性越高，其在网络中存在的重要性就越小，反之，效用越大。

1.3 消息替换风险估计

当节点所携带消息的效用值都比较低的时候，继续替换投递状态加权和最大的消息副本将对其所存储的消息投递产生较大影响，因此，此种情况下还需要考虑替换消息所带来的风险。若节点替换消息副本i，则对于这个消息来说可能造成的结果有2个:消息i仍然被成功投递，没有损失;消息i没有被成功投递，造成损失。由于状态参量的大小无法准确地反映出替换消息所带来的风险，本文运用数据挖掘的方法评估对给定消息替换的风险。对于每条消息的替换过程来说，节点需要记录如下信息＜ID，TTL，H，mi(t)，Pi，β＞，其中 ID 为替换消息的编号，以唯一地标识给定消息，TTL，H，mi(t)以及Pi为替换消息i时的状态，称作替换特征。β为标签，当节点因缓存拥塞而主动丢弃消息时，该参数β置为0，若后来收到与ID对应的确认消息，则将β重置为 1;当成功投递未替换消息时，直接置β为1。

对于给定节点来说，若消息i与其历史替换消息m具有相似的特征，则表明两者在网络中的投递状态相近。由机会网络的传输原理可知，消息m具有与消息i类似的投递机会，因此，可知替换消息i产生损失的概率与替换与i具有相似特征的历史消息相近。按照上述结论，若有S个与消息i相似的历史消息被替换，其中替换后造成损失的个数为Sloss，可以得到替换消息i的风险，如式(7)所示。

为了确定各个消息与消息i的相似程度，本文采用K－均值聚类法根据记录样本信息的特征对消息副本进行分类［11］，然后计算消息i与各个类别的相似度，确定消息i的归属类别。根据聚类的特点，同一类中的对象具有较高的相似度，而不同类中的对象相似程度较低。若消息归属于类Cj，可以认为消息i与Cj中的对象相似。

2 MRRCM基本原理

当节点的缓存占用超过预留的阈值θ时，节点会对自身携带的消息进行替换，以缓解节点缓存的拥塞。

在具体执行过程中，首先节点计算缓存队列中各个消息的投递加权和，确定已成功投递概率相对最大的消息i。根据消息i替换风险程度Riski的不同，可以划分为3种级别:高风险(Riski＞HL)，一般风险(LL≤Riski＜HL)，低风险(Riski＜LL)。其中HL，LL为风险划分阈值。

当替换消息i的风险程度为高时，表明此类消息在网络中的扩散程度较低，替换此类消息将极度浪费上游节点在转发过程中所耗费的网络资源，同时严重降低消息的成功投递率，因此，对于这种情况来说，节点将不替换该消息的副本。当风险程度一般时，节点首先将该消息副本转发给缓存剩余空间最多并且可容纳该消息的邻居节点，避免消息成功投递率降低的同时还可以对节点负载进行均衡。若没有邻居节点或邻居节点的缓存均为拥塞状态时，则不执行此类消息副本的转发操作，而将其直接替换。当替换风险为低时，节点将直接替换该消息，从而将有限的缓存资源分配给其他扩散程度不高的消息以提高整体的投递率。

3 数值结果

本文通过机会网络仿真平台(opportunistic network environment，ONE)［12］对所提的缓存管理策略MRRCM进行了实现，并以消息成功投递率、网络负载率和网络平均传输时延作为指标验证MRRCM算法的相关性能［13］。仿真采用基于免疫的传染路由算法(epidemic immunity)，具体参数如表2所示。

表2 仿真参数设置Tab.2 Design simulation parameters

仿真场景中的节点包含汽车节点和行人节点，都是随机选择一个目的节点，然后按照最短路径移动到目的节点的方式进行运动。实验在不同缓存大小的情况下，将DropOldest，基于历史信息删除策略(history based drop，HBD)，MRRCM 3种缓存管理策略进行了比较，其中HDB算法以最大全网投递概率为优化目标。

消息成功投递率如图2所示。从结果中可知，MRRCM总体的消息成功投递率要优于其他2种算法。同时，投递率随着节点缓存的增大而提高。图3描述了各类机制的平均时延，从结果中可知，各个机制的时延基本相同，且呈现出一定的上升趋势。网络负载率如图4所示，随着缓存容量的增加，网络负载逐渐降低。

图2 消息成功投递率Fig.2 Message delivery rate

图3 网络平均时延Fig.3 Average network delay

4 结论

为了解决节点拥塞导致的网络性能降低的问题，本文首先提出了消息投递状态的估计方法，并对消息替换所带来的风险进行了估计，根据消息投递状态和替换风险的不同，提出了一种基于消息替换风险估计的缓存管理机制。与典型的DropOldest算法和以最优全网概率的HDB算法相比，本文所提机制可以有效地提高消息的成功投递率并降低传输开销。同时，该机制具有较强的扩展性，能够适用于任何多副本路由机制。

图4 网络负载率Fig.4 Network load rate

［1］MCMAHON，FARRELL S.Delay－disruption－tolerantnetworking［J］.IEEE Internet Computing，2009，13(6):82－87.

［2］WAHIDABANU R S D，FATHIMA G.A new queuing policy for delay tolerant networks［J］.International Journal of Computer Applications，2010，1(20):56－60.

［3］刘期烈，潘英俊，李云，等.延迟容忍网络中基于分离时间和副本控制的路由算法［J］.北京邮电大学学报，2011，34(2):113－117.

LIU Qilie，PAN Yingjun，LIYun，et al.A Routing Algorithm Based on Separation Time and Copy Control in Delay Tolerant Network ［J］.Chongqing University of Posts and Telecommunications，2011，34(2):113－117.

［4］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.

［5］LIU Y，WANG J，ZHANG S，et al.A Buffer Management Scheme Based on Message Transmission Status in Delay Tolerant Networks［C］//Global Telecommunications Conference.Houston，Texas，USA:IEEE，2011:1－5.

［6］YUENW H，SCHULZRINNE H.Performance evaluation of time－based and hop－based TTL schemes in partially connected ad hoc networks［C］//IEEE International Conference on Communications.Istanbul，Turkey:IEEE Press，2006:3844－3849.

［7］BURGESS J，GALLAGHER B，JENSEN D，et al.Max－Prop:Routing for Vehicle－Based Disruption－Tolerant Networks［C］//Proceedings of 25th IEEE International Conference on Computer Communications.Barcelona:IEEE Press，2006:1－11.

［8］ZHANG Z S.Routing in intermittently connected mobile Ad hoc networks and delay tolerant networks Overview and challenges［J］.IEEE Communications Surveys Tutorials，2006，8(1):24－37.

［9］KRIFA A，BARAKAT C，SPYROPOULOS T.Optimal buffer management policies for delay tolerant networks［C］//The 5th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks.San Francisco，California，USA:IEEE Press，2008:260－268.

［10］吴大鹏，周建二，王汝言，等.机会网络中消息冗余度动态估计的缓存管理策略［J］.电子与信息学报，2012，34(1):101－107.

WU Dapeng，ZHOU Jianer，WANGRuyan，etal.Messageredundancy Estimating Adaptive Buffer Management Mechanism for Opportunistic Network［J］.Journal of Electronics ＆Information Technology，2012，34(1):101－107.

［11］HAN J，KAMBERM，PEIJ.Datamining:concepts and techniques［M］.San Francisco:Morgan kaufmann，2006:401－407.

［12］吴大鹏，张普宁，王汝言.节点连接态势感知的低开销机会网络消息传输策略［J］.通信学报，2013，34(3):44－52.

WU Dapeng，ZHANG Puning，WANG Ruyan.Connection Status aware cost efficient message transmission mechanism in opportunistic networks［J］.Journal on Communications，2013，34(3):44－52.

［13］MUNDUR P，SELIGMAN M，LEE G.Epidemic routing with immunity in delay tolerant networks［C］//Military Communications Conference，2008.San Diego， CA:IEEE Press，2008:1－7.

(编辑:田海江)