机会网络数据替换机制性能分析的建设策略

　0引言
　　随着通信技术的不断发展与完善，品种繁多的低成本，具备短距离无线通信能力的智能设备大量出现（如手机、PDA和蓝牙设备等），无线自组织网络得以快速发展。传统多跳无线网络的通信模式要求通信源节点与目标节点间至少存在一条完整的端到端路径，而在现实生活中由于网络稀疏，节点频繁移动等原因导致网络不连通，各个节点间的连接频繁地中断，造成网络性能下降，从而引起网络不可用[1]。由于人们对通信需求的不断增加，使得通信容量不断扩大，给网络带来了更多的挑战和困难。为了解决间断连接环境下无线网络中节点之间的通信问题，研究人员非常有必要提出一种新型的网络组网方式，满足人们日益增长的需求。
　　1机会网络概述及发展现状
　　作为一种新型的组网方式，机会网络概念来源于早期的容忍延迟网络研究，可以看作是具有容忍延迟网络一般特征的无线自组网。在移动自组织网络（mobile ad hoc network，MANET）中，普通节点承担路由及数据转发的责任，通过事先建立的完整端到端路径，有据可循地将数据投递到目的节点，从而实现节点间通信。但在复杂的移动通信环境中，多种因素可能导致通信链路中断，从而无法保证端到端路径的完整性。为了解决这一问题，人们提出了机会网络[2]。
　　1.1机会网络特点
　　与传统的移动自组织网络不同，机会网络有以下特点：1）利用节点频繁移动获得的相遇机会逐跳地进行通信；2）网络频繁地断开和连接，并不一定全连通，无法保证节点之间总在一条完整的端到端的通信路径；3）以“存储—携带—转发”的传输模式进行数据传输；4）网络节点存在异质性，即网络传输设备多种多样，可以是不同种类的具备无线通信能力的通信设备。机会网络体系结构在传输层之上叠加了一个束（buddle）层[3]，束层提供了类似网关的功能，从而使数据能够跨越异构网络实现通信，其体系结构如下图1所示。
　　1.2机会网络应用场景
　　随着移动终端设备的发展，机会网络已经得到了研究者的广泛关注，但由于理论研究的时间并不长，许多问题的研究仍处于起步阶段。目前，其相关技术仅在某些特殊环境中得到应用通信；3）车载网络组网。通过在汽车内部安装无线通信模块，车辆之间可以组成临时的通信网络；4）普通移动终端组网。机会网络利用人与人之间的相遇机会进行通信，不必通过传统的Internet网络转发数据，这种可以提供特殊服务的简单组网方式给人们带来了很大的商机。
　　2机会网络数据替换机制
　　在机会网络中，为了保证数据成功投递率，数据在网络中以多个副本的方式进行转发，随着网络中各节点转发数据的不断增加，有限的节点缓存资源将快速耗尽。由于机会网络以数据的成功投递为目标，缓存管理策略设计的核心思想在于选择对网络性能影响最小的数据进行替换，从而为重要程度较高的数据分配资源。可见，在缓存资源有限的机会网络中，设计高效的数据替换机制对提高机会网络的性能十分关键。本文将对比较经典的机会网络数据替换机制进行介绍，同时对于其各自的优缺点给出进一步分析。
　　2.1基于FIFO队列的数据替换机制
　　在机会网络研究初期，为了缓解节点拥塞带来的问题，研究人员套用在传统网络中广泛应用的基于先进先出（first input first output ，FIFO）队列的数据替换策略作为缓存管理的方法[5]。FIFO队列如图2所示，是指节点按照数据到达的先后顺序维持的缓存队列。缓存溢出时，按照优先替换位置的不同可以分为头部替换（frontdrop）和尾部替换（taildrop）2种缓存管理方式。这2种算法的计算复杂度仅为O（1），实现极其简单，在传统网络中得到了广泛的应用。
　　图2基于FIFO队列数据替换过程当缓存即将溢出时，上述2种缓存替换策略都能在一定程度上优化网络资源。并且在机会网络环境下，优先头部替换的性能要略高于优先尾部替换，但由于机会网络中数据的投递依赖于节点的运动情况，节点决定存储哪些数据将十分重要。而上述2种算法没有考虑网络情况或者数据的状态，并不适合机会网络这种多变的环境。
　　2.2基于生存时间或跳数的数据替换机制
　　基于生存时间或跳数的数据替换机制将数据的已存活时间和数据转发跳数作为判断参数，并认为数据存活的时间越长，跳数越多，其成功投递到目的节点的概率越大[68]。基于这种假设，已存活时间越小、已转发跳数越少的数据具有更大的优先级，节点收到数据时，按生存时间的大小或数据转发跳数排列在缓存队列中，生存时间较小或转发跳数越少的位于队头。当缓存溢出时，首先替换队尾的数据，过程如图3所示。并且，为了避免数据长时间地存在于网络，永不停息地在网络中转发，浪费节点缓存资源，网络给每个数据设置一个生存时间阈值或转发跳数阈值，当数据在网络的时间或转发跳数超过这个阈值时，则认为数据已传到目的节点，可以将其替换。
　　针对缓存溢出问题，该策略能有效地缓解缓存不足，从而使得数据更加准确地投递到目的节点。但是阈值设置的准确性对网络性能影响较大，当阈值设置过大时数据仍然会长时间占据网络资源，对网络拥塞没有实质改善，过小时又会使得未成功投递的数据被替换，导致网络可靠性的下降。
　2.3基于转发状态的数据替换机制
　　研究人员根据微观经济学中的边际效用递减规律提出了一种缓存管理方法。边际效应即用户每购买某种产品1个单位时，会增加一定的边际效用，但随着用户对这种产品消费的增加，其同样购买1个单位产品所带来的效。基于这一理论证明，作者以网络 中副本数量估计数据传播状态，以此作为衡量数据效用的主要条件。并定义数据在单位时间内的扩散范围为传播速率，作为次要条件，用公式（1）表示。
　　由于当前时刻数据在网络中的副本数量是一个全局变量，在机会网络环境下的节点无法准确获知，作者通过在节点相遇时学习彼此统计的信息近似估计数据的副本数量。在需要替换某一数据时，会先比较数据的传播状态，具有最大传播状态的数据将被优先替换，若有多个数据具有相同的传播状态时，将优先替换具有最大传播速度的数据。
　　此方法能够较为准确地替换数据，从而增加缓存利用率，优化网络资源。但是，机会网络的事实网络状态很难获知，从而不能准确地估算数据副本的扩散程度，导致估算不准确，影响网络性能。虽然上述参数可以从某种程度上反映出数据在当前的重要程度，但仅考虑单一参数并不能综合全面衡量数据在某个节点的效用。
　　2.4基于节点相关度的数据替换机制
　　结合人类日常移动具有规律性的理论，即大多数人在习惯的支配下总是频繁往返于几个特定地点，研究人员提出了机会网络缓存替换机制（opportunistic networking cache replacement policy，ONCRP） [10]。当数据的目的节点在节点频繁往返的若干个地点的范围之内时，表明数据被节点成功投递的概率大，这时数据与该节点具有较高的相关度。ONCRP利用节点携带的GPS设备记录节点的运动轨迹，并用公式（2）计算经过某地的频繁程度，其中k为经过某地的次数，T（k）为节点第k次经过某地的停留时间。Wlocation=k∑k1T（k）（2）同时，为了避免记录过多信息会增加节点负担，不便于数据的交换，因此，节点维护的数据表中只保留4个地点信息。数据表格式如图4所示。
　　图4记录数据格式若数据的目标节点在节点常往返地点的P范围之内，则认为匹配，相关度为1。作者利用相关度确定要替换的数据，并在此基础上使用数据的访问与更新频率比值衡量数据的有效性。ONCRP算法的目标是使得有限缓存中的数据效用和最大，在缓存已满且有新数据到达时，采用替换或转移的方式替换掉有效性最低的数据。其替换方式的选择由式（3）确定。
　　2.5基于效用值的数据替换机制
　　基于效用值的数据替换机制从全局的角度考虑数据的替换，从而获得最优的结果。并利用随机移动模型下，节点相遇时间间隔服从指数分布的理论研究成果，推导出全网投递概率及全网时延期望的公式，在缓存管理时，选择最大投递概率或最小平均时延作为优化目标[11]。
　　为满足最大数据成功投递率，在需要替换数据时将选择效用值最小的数据，效用值用公式（4）计算。
　　显然，在网络分割严重的机会网络中，想要获得网络的全局信息是很难实现的，作者在分析了单纯洪泛数据的存储状态以获得数据的历史全局信息带来的资源耗费及准确性不足的问题，提出了一种利用全网数据在经过T时的平均M（T）及N（T）值来估计mi（Ti）及ni（Ti）值的方法，并说明了此方法能够较好地估计上述参数。
　　2.6基于转移的数据替换机制
　　机会网络可以采用保管传输模式以增加数据传输的可靠性，在这种模式下，节点A将数据m传递到节点B时，节点B负有保管传输数据m的责任，在m超时之前，必须存储数据直到转发给m的目的节点或者将保管传输的责任委托给下一节点C，否则不能替换该数据。研究人员提出通过将数据转存给邻居节点，以解决采用保管传输模式下节点自身的缓存拥塞问题行转移。转移节点的确定包括2步：一是寻找k跳范围内的邻居节点，节点执行ERS寻找算法，初始选择1≤i≤k作为请求数据的跳数上限，向网络中发送请求，在收到至少一个节点的响应后，进入第二步，选择保管开销最低的节点。保管开销计算公式如式（6）所示。
　　基于效用值的方法能综合考虑节点的综合效用值，从而更加准确地估测节点自身的缓存状况，能够优化网络资源。但对于此种方法，虽然暂时解决了本地缓存不足的问题，但当周围邻居节点都缓存溢出时，很难缓解缓存空间不足的问题。
　　2.7基于确认分发的数据替换机制
　　为了减少冗余数据对网络的影响，研究人员采用分发确认数据的方式对冗余数据进行替换[13]。当目的节点成功接收了数据M，会生成一个确认ACK数据表示数据M的成功投递。确认ACK数据在节点之间进行转发，接收节点根据确认ACK数据自行替换已成功投递的数据，由于所采用的确认ACK数据仅需记录极其少量的信息，其相比正常数据的大小可忽略不计，因此，确认ACK数据在网络中的扩散并不会给网络带来严重的控制开销。
　　此种方法对于缓解网络拥塞，优化网络资源有较为显著的作用。但是由于确认ACK数据在机会网络中的扩散速度有限，不能够实时地替换已成功投递的数据。
　　3总结与展望
　　本文首先对于机会网络的基本概念、发展现状、网络特点以及应用场景进行了简要的介绍和分析。其次对于现有的部分有代表性的机会网络数据替换机制进行了总结，并且对于各替换机制存在的优缺点进行了详细的分析。
　　机会网络数据替换机制在允许数据在网络中存在多个副本进行转发的情况下，以有效的替换一个或多个对网络影响较小的数据为基本方法，从而成功地投递数据，并且优化网络资源。但是由于机会网络拓扑动态变化，节点准确获知数据的转发情况较为困难。因此，对于未来机会网络数据替换机制的研究问题有：1）节点如何准确地获知数据副本的扩散程度，并且有效综合多个相关参数估算数据效用值；2）如何设定一个合理的可变阈值，动态管理本地缓存，从而优化整个网络资源；3）在数据成功投递后，怎样较为实时地替换网络中冗余副本。针对以上问题继续进行数据副本替换机制的研究，从而做到更大程度的优化网络资源，提高资源利用率。

 本文选自《数字通信》2014年第2期，版权归原作者和期刊所有。