自适应的机会网络消息副本调整策略

黄丹莉，邱雪松，张黎明

(1.北京邮电大学网络技术研究院，北京100876； 2.中国国际工程咨询公司高技术业务部,北京100048)

自适应的机会网络消息副本调整策略

黄丹莉1，邱雪松1，张黎明2

(1.北京邮电大学网络技术研究院，北京100876； 2.中国国际工程咨询公司高技术业务部,北京100048)

提出了一种具有自适应的消息副本调整策略。该方法对消息副本的数量属性分层划分，通过控制属性来控制副本数量，是一种可定量定性调整的策略。根据划分的属性提取副本数优先度，综合考虑消息的其他属性，完成基于效用优先级消息队列的调整。实验结果表明，该方法能够自适应调整消息副本的冗余程度，达到较高的投递率，对不同网络负载有较高的适应性。

机会网络；路由协议；自适应；队列调整

0 引言

与传统网络不同，机会网络中没有端到端的持久的连接路径，借助节点相遇机会，完成不同连通域的源节点和目的节点的通信。它对于城市感知研究和未来普适计算的实现有很大的促进作用。因而近年来引起了科研工作者们的关注[1]。在野生动物追踪[2]、星际互联网络[3]、车联网等方面都具有很高的应用价值。较为典型的机会网络路由协议有基于单消息的直接传输路由协议(direct delivery)[4]，源节点携带消息移动，直到遇到目的节点；epidemic路由协议[5]，消息被复制给所有不具有该消息副本的节点，并继续复制传播下去；prophet路由协议[6]，节点间维护相互之间的接触概率信息，消息仅被复制给更高概率接触到目标节点的其他节点，并继续复制传播下去；spray and wait路由协议[7]，消息创建时限定消息副本的个数，在spray阶段传播复制消息，当节点携带的消息副本不能再复制时进入wait阶段，等待遇到目的节点完成投递。上述方法中在消息副本数量的分配上缺乏网络适应性，没有考虑存储空间对网络性能的影响。

本文基于spray and wait路由协议提出一种可适应的机会网络消息副本调整策略。通过划分消息副本数量属性达到定量定性控制的目的。量化消息副本的属性价值进行队列调整，能够达到存储空间占用较少、投递率较高的效果。

1 消息副本数的自适应控制

首先定义了消息副本限额范围(l0,lmax)：为了确保网络容量能够被充分利用且投递率能够达到一定的概率，分配一个静态范围属性。

消息副本数属性域：将一个消息副本的数量维度划分为数值区域，表示3种不同的状态，见表1。

表1 消息副本数属性区域表

其中lawake，是最高状态等级的消息副本数，lsleepy和lasleep分别表示另外两种副本数状态，状态等级以此降低，这3个属性被综合用来控制消息副本在路由过程中的复制传递，lmax是副本数的上限。awake属性的副本承担着主要的路由转发任务，该属性值之和在整个网络中不会发生变化(优先级保护)；sleepy属性用于辅助加速扩散、增加传递成功率，为之后的传递任务减轻压力且预留延迟误差，它与asleep相互转化；asleep属性值的存在用于记录和定量恢复至预定的副本数上限。需要注意的是，和喷射等待协议相似地，无论一条消息副本的3个数值区域是多少，只要该消息没有被丢弃，那么在存储空间只占用一条消息大小的空间。这三者的数量关系满足如下方程组：

(1)

当网络负载较轻时，调整策略是对于asleep属性值不为0的消息，唤醒一个asleep副本，转变为sleepy状态。发生拥塞时，采取缩减策略(也称为催眠过程)。对于节点vi存储空间里的每一条消息都会进行副本数属性值的修改，用于限制减少之后在网络中继续喷射的消息副本数量。即asleep属性值减一，sleepy属性值加一，awake属性值不变；跳过asleep属性值为0的消息，不做修改，调整下一条消息，见下列方程组：

(2)

2 基于消息副本效用的队列调整

从消息副本投递效用和存储空间利用率的角度出发，综合考虑了消息副本状态和数量分布所反映的消息重要性、剩余生存时间ttl对投递的效用回报。在传输消息时优先传送效用更高的消息副本，在删除消息时首先删除投递效用最低的。

首先定义了消息副本数量属性反应的效用优先度：

lp=β1·lawake+β2·lsleepy+β3·lasleepy。

(3)

然后，结合消息效用和经历跳数、延时所反应的消息效用回报，定义归一化权重分配矩阵：

α=[α1α2α3]，

(4)

式中：α1表示分配给lp属性的权重；α2表示ttl属性所占的权重；α3表示跳数hop属性的权重。

(5)

在效用重要度比值矩阵A中，a12表示副本数优先度lp与ttl属性权重的重要性比值，a23表示ttl属性权重与跳数hop属性的重要度比值。

为了得到一致性可以计算最大特征根λ和对应的特征向量ω。ω的转置矩阵即为归一化权重分配矩阵α。在不同场景下这3个属性相互的重要程度可以适当倾斜，但仍然需要一致性检测。

最后得到消息副本的效用优先级计算公式如下所示：

(6)

1+msg.hop是考虑到刚刚创建的消息跳数为0，为了防止分母为0采取数值加一措施。另外，TTL_maxvi是预分配的消息最大生存时间，任意消息的剩余生存时间与其关系满足msg.TTL∈[0，TTL_maxvi]；lp_maxvi是在节点vi上最大的消息副本数优先度，其中任意消息副本的副本数优先度满足lp∈[0，lp_maxvi]；hop_maxvi是节点vi上最大的消息副本跳数。在计算消息效用优先级时采用最大最小规格化方法将这3个维度的效用加权求和。求出的值越大意味着传递该消息对网络性能提高更有贡献，其优先级就越高，反之，效用更低，优先级越低。

3 实验结果

为了验证算法的有效性和可适应性，下面展示使用theONEsimulator仿真器进行的实验(核心参数见表2)。对消息的投递率、传输开销变化、仿真结束网络节点平均存储空间占用情况进行比较和分析。

表2 仿真参数设置

图1 消息产生时间间隔对网络各性能指标的影响

图1呈现了关于AQOS算法网络投递率、传输开销以及传输延时与消息产生时间间隔之间的关系。间隔减小，单位时间内产生的消息增加，网络传输压力增大，网络投递率降低，但是AQOS始终保持较为稳定的投递率输出。而达到这样的效果是调整了消息副本数量，适应这样的变化。

图2 消息大小对网络各性能指标的影响

图2呈现了关于AQOS算法网络投递率、传输开销以及传输延时与消息大小之间的关系。随着消息大小的增大，单位消息需要占据的节点缓存空间增加，网络负载压力增大，网络投递率降低。但是AQOS始终保持较高的投递率输出，即使在消息大小为700k也仍然保持在83%以上；当消息大小不大于500k时，可以获得至少89%的投递率，且较为稳定。可以看出负载压力较大时，消息副本数量自适应缩减，高效地利用有限的节点存储资源。

图3 投递率与节点缓存大小的关系

消息成功率如图3所示。从图示结果可以看出，AQOS协议完成的消息投递率保持在86%以上，优于其他协议。另外，对比分析喷射等待(sprayandwait)协议副本数配额为6和20的性能可以发现，AQOS提出的算法投递率性能更优。同时，随节点缓存空间增大而增大，但是幅度缓和，可见AQOS相较于其他协议不容易受到节点缓存空间变化的影响。最显著的优势在于节点缓存空间为5M时，仍然能够完成较高的投递率。

从图4可以看出在仿真结束时，AQOS的缓存占用率仅高于低效率的DirectDelivery协议，在投递率性能优越的同时剩余空间充裕，更容易抵抗短时间拥塞带来的不良影响。可见AQOS较好地权衡了消息队列中各消息可以带来的投递效用，进行了调度优化，故而获得较高的投递率。

图4 网络负载与节点缓存大小的关系

4 结语

本文提出了一种具有自适应的消息副本调整策略，该方法能够自适应调整消息副本的冗余程度。通过大量的仿真实验和对比实验，在消息产生最频繁、节点存储空间最小的情况下仍然可以取得较高的投递率和较大的剩余存储空间，综合性能优于其他经典路由协议。可以证明该策略对变化网络负载有较高的适应性，达到较高的投递率。

[1] 马华东,袁培燕,赵东.移动机会网络路由问题研究进展[J].软件学报,2015,26(3):600-616.

[2]JuangP.Energy-efficientcomputingforwildlifetracking：designtrade-offsandearlyexperienceswithZebraNet[J].ACMSIGPLAM，2002，37：96-107.

[3]DianaR,LochinE,FranckL,etal.DTNroutingforquasi-deterministicnetworkswithapplicationtoLEOconstellations[J].InternationalJournalofSatelliteCommunications&Networking,2015，10：1-18.

[4]SpyropoulosT，PsounisKCS,Raghavendra.Efficientroutinginintermittentlyconnectedmobilenetworks:thesingle-copycase[J].IEEE/ACMTrans.Networking，2008，16：63-76.

[5]VahdatA,BeckerD.Epidemicroutingforpartially-connectedAdHocnetworks[R].TechnicalReportCS-200006,Durham:DukeUniversity,2000:1-14.

[6]LindgrenA,DoriaA,DaviesE,etal.Probabilisticroutingprotocolforintermittentlyconnectednetworks[J].ACMSIGMOBILEmobilecomputingandcommunicationsreview,2003,7(3):19-20.

[7]SpyropoulosT,PsounisK,RaghavendraCS.Sprayandwait:anefficientroutingschemeforintermittentlyconnectedmobilenetworks[C]//Proceedinsofthe2005ACMSIGCOMNworkshoponDelay-tolerantnetworking(WDTN′05).NewYork,USA:ACM,2005:252-259.

[8]LoSC,LuCL.Adynamiccongestioncontrolbasedroutingfordelay-tolerantbetworks[C]//FuzzySystemsandKnowledgeDiscovery(FSKD),2012 9thInternationalConferenceon.Chongqing,China:IEEE,2012:2047-2051.

[9]TangS,LiW.QoSprovisioningandqueuemanagementinmobileadhocnetworks[C]//WirelessCommunicationsandNETWORKINGConference.LasVegas,Nevada,USA:IEEE,2006:400-405.

[10]keränenA,OttJ,KärkkäinenT.TheonesimulatorforDTNprotocolevaluation[C]//Proceedingofthe2ndInternationalConferenceonSimulationToolsandTechniques(Simutools’09).Rome,Italy:ICST(InstituteforComputerSciences,Social-InformaticsandTelecommunicationsEngineering),2009:55.

The Optimization Strategy for Adaptable Opportunistic Network Message Replica

HUANG Dan-li，et al.

(InstituteofNetworkTechnology，BeijingUniversityofPostsandTelecommunications，Beijing100876，China)

This paper presents an adaptive message replica adjustment strategy.This method is a kind of quantitative and qualitative adjustment strategy to control the number of replicas by controlling attributes，and then according to the attribute partition，the priority of the replica is extracted.Moreover，the other attributes of the message are considered to form the message queue optimization based on the priority of utility.The experimental results show that the proposed method can adaptively adjust the redundancy degree of message replicas to achieve higher delivery rate，and have higher adaptability to different network loads.

opportunistic network；routing protocol；adaptable strategy；queue optimization

10.3969/j.issn.1009-8984.2016.04.025

2016-11-15

国家科技支撑计划(2015BAH03F02) 国家自然科学基金面上项目(61272515)

黄丹莉(1992-)，女(汉)，湖北，硕士 主要研究机会网络路由协议。

TP393

A

1009-8984(2016)04-0096-04