基于消息参数的机会网络缓存队列管理策略

邹　鑫,符　敏,陈晓丹（华南师范大学　物理与电信工程学院，广州　510006）

基于消息参数的机会网络缓存队列管理策略

邹鑫,符敏,陈晓丹
（华南师范大学物理与电信工程学院，广州510006）

摘要：为提高机会网络的传输效率，根据消息路由跳数、数据大小与自身携带的TTL等参数计算副本的缓存参数与转发效用值做出转发或替换的决策，由消息目的节点与中继节点的历史相遇次数判断消息副本与中继节点的相关度，根据人类活动路径特定的模式，设计出基于消息参数的缓存管理与队列管理策略。仿真实验显示，此缓存策略可有效提高网络的成功投递率，降低平均投递延迟，具有较好的网络性能。

关键词：机会网络；权值估计；缓存队列管理；消息效用

0　引言

机会网络[1]的节点利用其移动性，在没有完整链路的网络中使用“存储-携带-转发”的路由方式传递消息。现存的基本网络管理策略有[2-3]：DL(DropLastReceived)：丢弃最新接收的副本；DLR(DropLeastRecentlyReceived)：丢弃在缓存中驻留最久的消息副本；DOA(DroptheOldest)：丢弃已生存时间最长的消息。KRIFA等人[4]根据副本的历史信息估计其在网络中的副本数，并推导出能满足最小延迟以及最大传输率所需的删除条件。文献[5]提出了一种基于节点集群的缓存统一维护管理策略，利用P2P网络[6]的相关技术，将相邻的节点构成一个簇，并将能量较高且较稳定的一个节点作为簇头，通过组网内实时在簇头节点上建立更新树并发送更新的消息。请求节点与簇头的路由距离比它到源节点的路由距离相对较短，因此这样的策略使节点网络连接更可靠、响应延迟更短和能量消耗更小。叶晖等人[7]提出ON-CRP (OpportunisticNetworkingCacheReplacementPolicy)机会网络缓存替换策略，利用消息副本与不同目的节点的相关度来执行缓存替换。由节点的社会属性可找出节点的行为模式，然后以节点群组为目标进行消息递交，但由于单一地依靠消息与节点的关联度进行替换判断，可能会使消息在缓存中保存时间过长，造成投递延迟增加。

本文综合消息的全局递交率，根据人类移动模型[8]中表现出的节点移动规律，考察网络中递交消息副本的路由记录与全局历史缓存信息，利用消息参数反映的各中继节点和目的节点间的相对关系提出MIPM（MessageInformationforPriorityManagement）缓存策略。根据参数进行缓消息存队列的管理，由已传递消息的副本计算参数与路由向量记录判断消息送达的可能性，从而充分利用节点有限缓存，实现消息最大的成功投递率并降低投递延迟，以提高网络整体性能。

1　基于消息参数的缓存管理

提出基于消息参数的缓存管理算法包括缓存管理替换与队列管理两个部分。其中替换策略的核心是通过估计副本缓存参数与缓存内消息进行比较替换，各节点根据自身情况，结合缓存中的消息参数进行取舍判定；队列管理采用路径向量匹配排队策略，根据节点维护的状态信息结构进行缓存队列排序管理。

1.1副本缓存参数

在机会网络中，网络拥塞通常是由过多消息副本造成的。选取主要影响传输效率的两个参数，消息副本数和传递深度进行缓存管理，通过控制消息副本数或根据消息参数变化找到传输较优的平衡点。各参数定义如表1所示。

表1　缓存参数与定义

该策略在消息副本传播时以副本的相关状态参数作为其缓存参数的计算参数，使单个节点对任一消息i计算的缓存参数更符合当前网络的传输优化条件。缓存策略不控制消息副本转发次数的条件下，消息i产生后会被各节点在相遇时复制并转发。当每个节点收到新的消息时，根据副本携带的各参数来估算此消息在整个网络中大致的副本数量nt(i)，并依此计算出在缓存内分配的优先值Uj(i)，进而在缓存溢出时根据Uj(i)对相应的副本做出取舍判断。

消息i缓存参数的计算表达式：

其中Uj(i)表示消息i到达节点j时的缓存参数，pj(i)是节点j中消息副本i的效用值。由多副本传输机制，在任一时刻t，对于消息i可知其副本的消息剩余存活时间越小，则消息i在网络中停留的时间越长，被节点复制转发的副本越多，进而增大其成功投递率。

由文献[9]，[10]可知，在大多数的移动模型中，任意两节点的相遇时间t服从指数分布，或在时间上表现出类似指数衰减的曲线，如随机路点模型[11]、随机路线模型、随机方向模型、社区模型[12]，以及在现实生活中用移动设备采集的真实路径模型[13-14]等。

假设网络中共生成了Mt个互不相同的消息，在任一时刻t下，节点做出判断，有可能会将生存时间为Tt(i)的消息i丢弃，对于任一消息i∈[1,Mt]，Dt(i)表示从消息产生至时刻t止，缓存过消息i的节点总数（源节点除外），nt(i)为在时刻t下携带有消息i副本的节点数，则整个网络在t时刻对全部消息的平均全局递交概率Wt由下式表示：

其中：

Lt为t时刻时网络中的节点总数由以上定义描述可知，有nt(i)≤Dt(i)+1。由于两节点间的相遇时间服从参数为λ的指数分布[15]，则消息i的一个副本投递失败的概率等价于此节点在下次相遇时碰到目标节点的时间大于消息剩余存活时间，即exp(-λRt(i))。

效用值uj(i)可看作是消息副本的临界效用，是基于消息参数而得的某一副本相对当前节点内全部缓存副本的一个评估值，在节点缓存溢出时的最佳缓存管理策略应是替换缓存内效用值最小的副本，即有：

1.2队列管理与替换算法

1.2.1入栈管理

本文MIPM算法的入栈管理中，设节点缓存内已有n个不同的消息副本 i1～in，节点考察参数Ht(1)～Ht(n)，并将其按大小排序组成队列。当节点j收到大小为Si0的消息i0时，首先判断缓存容量，若BSj≥Si0，则可将i0直接放入缓存队列；若BSjSi0，即可将i0放入缓存。

从一个消息产生开始，每个消息及其副本都带有唯一的路由表，用以记录此副本在网络中经过的节点。消息的路由表用一个一维数组RV表示，记作RV=[R1,R2,R3,...,Rn]。其中Ri(i=1,2,...,m)表示此副本经过的第i个中继节点的ID。随着消息副本在网络中的复制和传递，每到一个中继节点，该节点即读取此副本的目的节点ID和其路由数组RV，并将其加入自身维护的区域路由列表中，此表大小为n×m，不同节点的路由记录来自缓存过的副本携带的路由表。

1.2.2出栈管理

当网络中的节点移动时，它们相遇后可进行通信。假设某节点J碰到网络中另一节点K时，两节点在可进行消息交换的条件下，先获取对方的ID，分别记作NA和NB，然后在各自的路由列表中查询此ID。若ID存在，说明对方曾作为网络中某条链路Ri的中继节点Riy递交过消息，它遇见Ri内上下节点Riy+1和Riy-1的概率较其他随机节点大。再读取对方Ri的全部中继节点ID，到缓存中匹配各消息副本的目的节点Dx，若存在，说明此副本到达其目的节点的链路在网络中曾经存在。同时，依照节点活动的社会规律性，同一链路中的各结点再次相遇的概率大于其他节点。因此可判断对方结点是潜在的高效递交中继，即可把相应的消息副本发送给对方。若匹配失败，说明对方节点是在本节点历史链路中首次出现，则按消息副本缓存参数Uj(i)高低将缓存内消息副本排序后，发送Uj(i)最高的副本给对方节点。

各节点相互传递消息副本之后，副本的Rv都会自动将接收方节点的ID记录到向量末尾并更新一次路由列表。

2　仿真验证与分析

2.1仿真环境设置

使 用 theONE(OpportunisticNetworkEnvironment)平 台[16]作为网络仿真工具。路由协议使用传染病路由算法[17](Epidemic Immunity)，仿真区域为4500m×3400m的城市道路网，移动模型使用随机路点模型RWP(RandomWayPoint)，仿真时间为43200秒。各个节点在本地对缓存内的消息按优先级排序，通信方式为蓝牙传输，通信范围10m，信道传输速率256KBit/s，初始化消息生存时间为18000s。默认节点缓存大小为20M，消息大小为500-1000kByte，产生间隔为25-35s。

2.2MIPM策略性能分析

本小节在不同的条件下对提出的缓存管理算法进行了仿真实验。对比本文的MIPM策略和具有代表性的RO(RemovetheOldest)策略：丢弃在网络中最长驻留时间的消息。本节主要以消息投递率，网络消耗量和传输延迟的性能指标对算法进行评估，仿真以上管理策略并对它们的网络性能进行比较。

当节点缓存大小从20M增加至50M时，对比两种策略的网络投递率。网络中节点数固定为210个。从图1中可看出，随着节点缓存空间的增加，两种策略的投递率均有上升，而在缓存空间5M时MIPM策略的递交率比RO策略高约154.5%，缓存到50M时同比高约31.9%，且在缓存大小超过25M后MIPM算法的递交率上升变化趋缓，稳定在90%左右。

在同样的仿真设置中，考察各策略的网络开销。如图2所示，当节点缓存仅有5M时，两种策略所得网络开销较接近，且缓存在增加的过程中，RO的网络消耗下降明显，MIPM在节点缓存大于10M后即无明显下降趋势，在200附近上下波动，是因为算法本身的限制使得节点在碰到合适的中继节点后继续发送消息；RO策略在有足够大的缓存时会减少节点的丢包次数，单个节点携带消息的平均时间更长，因此其网耗相对较小，在缓存50M时的网耗仅为MIPM的39.1%。

同样的，在图3中当节点数量恒定为210个时，不同算法的网络递交延迟有较大差别。当缓存为5M时MIPM的延迟约为RO策略的48.8%，随着缓存的增加，其递交延迟也增加。到缓存增为50M时MIPM平均延迟为RO的46.2%，RO上升58.5%，MIPM上升50%，但在这个方面MIPM有比较明显的优势，能以更少的时间递交信息。

在缓存固定为20M而节点数增加的条件下，两种策略表现出较平稳的网络递交率，从图4看出，MIPM的递交率在80%上下波动，而RO策略的递交率在50%附近，有下降趋势。节点数量的增加对两种算法的网络递交率并无太大影响，MIPM因在队列管理中加入消息参数信息的判断因而能让节点更有目的地投递，使网络有较高的递交率。

同样地，图5显示在缓存不变而节点数从100个增加到400个时，两种策略的网络消耗也随之增大。当节点较少时，MIPM的网耗略大于RO算法，在节点为350以上时，MIPM表现出轻微优势，比RO的网耗低约7.5%。从图中可看出MIPM算法的网络开销在节点数变化时其稳定性不如RO算法。节点数从100个变化到400个的过程中，MIPM增加了246.2%，RO增加了1100%。

当节点数从100变为400时，在恒定缓存20M的条件下，对比算法的网络递交平均延迟。从图6中可知在节点数进阶增加的条件下，两种策略的平均延迟均呈类似下降趋势。在节点数增加300%的过程中，MIPM策略的延迟下降60%，RO策略延迟下降30.8%，而横向比较中MIPM在节点数为100时延迟为RO的60.6%，在节点数为400时为RO的33.3%。

通过仿真实验，本文提出的MIPM机会网络缓存管理算法相比传统策略有较高的成功投递率和较少的网络消耗和网络延迟。从整体上评价算法对网络的改善效率，在考虑消息参数与其效用值的基础上做出缓存替换决策能比传统缓存管理策略提高网络递交率约15%至40%，同时能达到较低的网络递交延迟。结论证明本文提出的MIPM缓存管理算法在实验条件下能有较优的网络性能。

3　结论

本文主要研究基于消息参数的机会网络传输过程的缓存管理，通过消息参数来确定副本在网络中的投递状态，以TTL0和Si等参数计算消息的效用值pj(i)以评估其缓存价值，进而节点根据pj(i)进行缓存参数计算与执行替换策略。在队列管理算法中，综合考虑消息与节点的相关度，确定节点缓存的排队序列与转发顺序。最后仿真实验并对比分析了MIPM缓存管理算法的网络性能，仿真结果显示本文提出的策略相对传统算法能较好的适应社会网络消息的投递。本算法的网络消耗在节点数变化时较不稳定，只能在特定环境中保证较高的递交率，且尚未考虑在现实网络中利用群组节点的社会关系和周期性相遇时间对某类特定消息的递交效率的评估，作为进一步提高机会网络传输效率的研究方向之一。

参考文献:

[1]Pelusi L, Passarella A, Conti M. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[J]. Communications Magazine, IEEE, 2006, 44(11): 134-141.

[2]Davis J A, Fagg A H, Levine B N. Wearable computers as packet transport mechanisms in highly-partitioned ad-hoc networks[C]//Wearable Computers, 2001. Proceedings. Fifth International Symposium on. IEEE, 2001: 141-148.

[3]Lindgren A, Phanse K S. Evaluation of queueing policies and forwarding strategies for routing in intermittently connected networks[C]//Communication System Software and Middleware, 2006. Comsware 2006. First International Conference on. IEEE, 2006: 1-10.

[4]Krifa A, Barakat C, Spyropoulos T. Optimal buffer management policies for delay tolerant networks[C]//Sensor, Mesh and Ad Hoc Communications and Networks, 2008. SECON'08. 5th Annual IEEE Communications Society Conference on. IEEE, 2008: 260-268.

[5]谢高岗，李振宁，李嘉宁.MANET中基于族的缓存一致性维护策略[J].软件学报,2008,19(11):3042_3052.

[6]牛新征, 佘堃, 秦科 等. 移动 P2P 网络的协作缓存优化策略[J]. 计算机研究与发展, 2008, 45(04): 656-665.

[7]叶晖, 陈志刚, 赵明. ON-CRP: 机会网络缓存替换策略研究[J].通信学报, 2010 (05): 98-107.

[8]Gonzalez M C, Hidalgo C A, Barabasi A L. Understanding individual human mobility patterns[J]. Nature, 2008, 453(7196): 779-782.

[9]Chaintreau A, Hui P, Crowcroft J, et al. Impact of humanmobility on opportunistic forwarding algorithms[J].Mobile Computing, IEEE Transactions on, 2007, 6(6): 606-620.

[10]Karagiannis T, Le Boudec J Y, Vojnovic M.Power law and exponential decay of intercontact times between mobile devices[J].Mobile Computing, IEEE Transactions on, 2010, 9(10): 1377-1390.

[11]Bettstetter C, Hartenstein H, Pérez-Costa X.Stochastic properties of the random waypoint mobility model[J].Wireless Networks, 2004, 10(5): 555-567.

[12] Spyropoulos T, Psounis K, Raghavendra C S.Performance analysis of mobility-assisted routing[C]//Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing.ACM, 2006: 49-60.

[13]McNett M, Voelker G M.Access and mobility of wireless PDA users[J].ACM SIGMOBILE Mobile Computing and Communications Review, 2005, 9(2): 40-55.

[14]Hui P, Chaintreau A, Scott J, et al.Pocket switched networks and human mobility in conference environments[C]// Proceedings of the 2005 ACM SIGCOMM workshop on Delaytolerant networking.ACM, 2005: 244-251.

[15] Krifa A, Barakat C, Spyropoulos T.Message drop and scheduling in DTNs: Theory and practice[J].Mobile Computing, IEEE Transactions on, 2012, 11(9): 1470-1483.

[16]Keränen A, Ott J, Kärkkäinen T.The ONE simulator for DTN protocol evaluation[C]//Proceedings of the 2nd international conference on simulation tools and techniques.ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2009:55.

[17]Mundur P, Seligman M, Lee G.Epidemic routing with immunity in delay tolerant networks[C]//Military Communications Conference, 2008.MILCOM 2008.IEEE.IEEE, 2008:1-7.

作者简介：邹鑫（1988—），男，广西南宁人，硕士，研究方向：机会网络缓存优化。