面向机会网络的自适应冗余副本删除机制

王汝言，金 勇，吴大鹏，林艳芳，徐 蕾

(1.重庆邮电大学宽带泛在接入技术研究所，重庆 400065;2.中国移动通信集团设计院有限公司重庆分公司，重庆 400042;3.无锡源清高新技术研究所有限公司传感网研究中心，江苏 无锡 214000)

0 引言

随着具有无线通信能力的个人手持设备逐渐普及，节点间可以通过自组织的形式组成通信网络，进而实现数据传输。但在复杂多变的实际环境中，节点频繁移动以及周期性休眠等原因，导致通信双方可能并不存在完整的端到端路径。为了提高此种网络状态下的通信灵活性，研究人员提出了一种新的网络体系结构，即机会网络［1］，利用节点移动形成的通信机会，以“存储—携带—转发”的路由模式实现节点间通信。

机会网络的路由机制可以分为两大类:单副本路由机制和多副本路由机制。对于单副本路由机制来说，整个网络中只存在给定消息的唯一副本。根据其采用的路由策略，源节点和中继节点将该消息逐跳转发到目的节点。但是对于动态性极强的机会网络来说，此种路由机制的消息投递难以保障。与单副本机制相对，多副本路由机制中，网络中存在多个相同消息的副本，以达到提高消息成功投递率的目的，此种机制的缺陷也比较明显，即多个副本将消耗掉更多的网络带宽及存储资源。

可见，机会网络采用面向无连接的消息转发方法，对于多副本机制来说，任何节点无法获知所携带消息其他副本的状态，其中包括副本数量及投递状态等。当消息的某个副本成功转发至目的节点之后，其他中继节点的缓存中可能依然保存该消息的副本，若继续对其余副本执行转发操作将极大地浪费有限的网络资源。因此，有效的冗余消息删除机制对提高资源有限的机会网络性能至关重要。

目前，对于上述冗余消息的删除方法主要是通过分发确认消息(acknowledgement，ACK)来实现，文献［2］提出了一种被动式ACK消息分发方法，携带ACK消息的节点并不执行主动扩散过程，而是当有其他节点向其转发已成功投递的消息时，节点才将对应的确认消息转发给对方，以删除冗余消息。虽然此种方法能够防止ACK消息的泛洪，但是，ACK信息在网络中扩散的速度较慢，无法及时删除消息的冗余副本。文献［3］提出了一种主动分发方法，每个节点保存相应的ACK列表，以标识其携带的ACK信息，当与其他节点相遇之后，首先转发彼此携带的全部ACK信息，从而快速扩散ACK消息。在主动分发ACK消息的基础上，文献［4］考虑了人类移动的特点，通过在人类聚集点设立固定的转发节点来分发ACK列表信息，从而以更快的速度删除冗余消息。可见，上述策略均以最大化ACK信息转发速度为目标，并未考虑ACK信息的分发所带来的开销。显然，每个成功投递的消息均与多个ACK消息对应，在网络规模较大或者所产生消息较多的情况下，转发ACK消息所耗费的网络资源将快速增加。此外，若两个节点的相遇间隔时间较短，仍然转发全部的ACK信息将引入不必要的开销。

本文提出了一种自适应的ACK分发机制(adaptive ACK distribution，AAD)，通过网络运行过程的历史信息，各个节点以分布式的方式估计区域消息密度，并根据ACK消息历史转发节点及ACK消息转发跳数来执行转发判定。由于考虑了不同ACK消息对于节点必要性之间的差异，所提出的ACK分发机制能够更好的使用网络资源。

1 ACK消息

对于任一节点，当收到以自身为目的节点的消息时会产生ACK消息，用来表示该消息已经成功投递。如前所述，机会网络中的数据转发过程需要多个中继节点辅助，网络中存在多个给定消息的副本，在消息成功投递后，容易产生冗余消息。与传统网络中TCP的确认机制不同，机会网络中的ACK消息并不是为了实现数据的可靠传输，而是为了删除冗余消息，防止其继续执行传输过程，占用网络资源，从而实现提高网络资源利用率的目标。

在节点维护的ACK列表中，每条记录与相应的ACK消息对应，其结构如图1所示，图1中源节点序列号与目的节点序列号标识了消息的发送节点与接收节点，大小为48 bit［5］。序列号字段记录源节点发送消息时对应的数据序号。按照上述方法，ACK所对应的消息由三元组唯一标识，其中包括源节点序列号，目的节点序列号，消息序列号。生存时间记录了该ACK消息能够在网络中存活的最长时间。节点定期检查ACK列表，当记录中的ACK消息生存期到期时，则删除该记录。

图1 ACK消息结构Fig.1 Structure of ACK message

2 自适应的ACK分发机制

机会网络中的各个节点所携带的消息不同，各个节点对于ACK消息的需求程度也呈现出一定的差异;同时，网络资源有限，节点之间的连接持续时间较短，因此，需要将ACK消息有针对性地转发给携带冗余消息以及将来可能接收冗余消息的节点。本文提出自适应ACK分发机制包含两个阶段，分别为洪泛阶段及转发控制阶段，在不同的阶段内定义了不同的转发的条件。

1)泛洪阶段:此阶段为ACK消息产生的初期阶段。为了以最快的速度删除冗余消息，ACK消息的携带节点以洪泛的方式向其他节点发送相关信息，即节点相遇之后，转发彼此携带的所有ACK消息。为了有效地限制转发过程中所产生的资源消耗，本文采用基于跳数的方法来控制ACK的转发范围。所提出的方法中，每个ACK消息具有相应的转发上限值，表明消息转发次数的最大值。图2描述了由节点A产生的初始转发上限值L=3的消息转发历史记录。

2)转发控制阶段:当节点携带的某个ACK消息的转发上限为0时，则进入转发控制阶段。该阶段中，ACK消息的转发由局部消息密度确定，在某个区域中，携带有消息i的节点数与这个区域中所有节点数的比值称为消息i的局部密度。若消息i的密度较高，则表明该区域内消息i对应的ACK消息较少，这时消息i会以较大的概率在区域中继续转发，感染其余节点，此种情况下需要转发ACK来减少这个区域中消息i的冗余度，以有效地降低冗余消息继续转发所带来的资源浪费。

图2 基于跳数转发的示例Fig.2 Illustration of hop-based forwarding

根据机会网络的消息转发原理，节点相遇之后，需要交换彼此的消息索引列表来告知对方自身所携带的消息状态，进而，节点可以维护相遇历史信息表，如图3所示，包括相遇节点的地址、相遇时间及节点携带消息的ID。消息的局部密度通过对列表内的信息进行估算得到。

图3 历史节点相遇信息Fig.3 Historical meeting information of node

根据T时间内相遇节点的个数N(T)及当中携带i消息的节点个数Mi(T)，可获知消息i的局部密度MDi(T)，如式(1)所示

根据消息i的局部密度值，节点按照式(2)执行ACK消息的转发判定。

(2)式中，ρth为局部密度阈值。

此外，ACK消息的分发方法至关重要，大多文献采用Hello或者Reply分组来携带ACK信息［6-7］，但此种分组采用周期发送方式，使得大量ACK消息出现重复投递的情况。本文提出的ACK分发机制中充分地考虑了相应的历史状态信息，节点转发ACK消息列表时，只针对未转发过的ACK消息。按照此种方式，Hello分组的转发数量得到了控制，降低了发送ACK消息列表所带来的开销，且没有增加新的控制分组来传送。

自适应ACK消息转发机制原理如图4所示，其中节点Y为相遇节点，ACK_i为消息i的确认消息。

图4 自适应的ACK消息转发机制Fig.4 Adaptive forwarding mechanism of ACK

加入ACK后路由的转发步骤会有所不同。对于节点X，Y来举例，X节点通过周期广播带有本地数据消息列表的Hello分组来寻找邻居节点，当Y节点收到X节点发送的Hello分组时，返回Reply对需要的数据消息进行请求，并转发按照图4确定需要转发的ACK，X节点收到Reply后首先根据收到的ACK列表对自身的冗余消息进行删除，然后按照路由转发策略发送请求分组。

3 仿真验证及结果分析

本部分采用ONE(opportunistic network environment)仿真平台［8］对所提机制的相关性能进行验证，并与其他典型路由机制进行比较，其中包括Epidemic［9］及 PROPHT［10］路由机制。具体参数如表 1 所示。

仿真场景中的节点包含3类，分别为电车节点、汽车节点和行人节点，电车节点按照固定轨道进行运动，行人及汽车都是以随机选择一个目的节点，然后按照最短路径移动到目的节点的方式进行运动。实验在不同缓存及不同节点数的情况下，将AAD方法与洪泛ACK的方法以及无ACK这3种情况进行了比较。其中初始转发上限L取6，ρth为0.2。

表1 仿真参数设置Tab.1 Simulation parameters

图5为ACK消息的平均携带率，也就是携带某个ACK消息的节点数与全网节点数的比例，ACK消息的平均携带率可以反映出ACK消息的平均分发程度。可以看到，当路由采用洪泛ACK的方法时，ACK消息几乎都能投递到网络中的所有节点，忽略了节点对于不同ACK的需求程度差异。而在采用AAD的Epidemic及PROPHT中，通过有效的分发控制，将ACK消息平均投递到网络中四分之一的节点中，并且具有与洪泛ACK相近的冗余消息删除能力，说明了AAD能够满足不同节点对于ACK消息的需求差异，降低了网络资源的消耗，相比洪泛ACK具有更高的效益。

图5 ACK消息的携带率比较Fig.5 Carriage ratio of ACK message

图6为网络性能随节点组个数变化的仿真图。在这个场景中，节点内存大小为50 MByte，行人组及汽车组中的节点个数在40－80之间变化。

图6 节点组个数变化对性能的影响Fig.6 Network performance under different group number

图6a表明引入ACK消息能够较大程度的提高消息的投递率。随着节点个数的增加，节点之间相遇的机会也随之增多，进而导致洪泛ACK所带来的开销更大，由于AAD能够使得ACK消息更加有效的分发，所以Epidemic及PROHPET路由采用AAD机制的投递率较采用洪泛ACK的投递率高。由图6b可以看到消息的传输时延随节点数量的增加而逐渐降低，其主要原因在于更多节点可以充当中继节点，从而使得平均时延降低。由于减少了ACK消息的转发，所提出的机制降低了控制开销，比采用洪泛ACK路由机制的时延更低。图6c中的网络负载率为:(转发的消息数－成功投递的消息数)/成功投递的消息数，反映的是平均转发多少个消息才能成功投递一个消息。图6c表明ACK消息的引入能够删除网络中的冗余消息，从而避免转发这类消息产生的不必要的开销。AAD及洪泛ACK都具有相似的开销，这说明AAD也能够及时的删除网络中的冗余消息，提高网络效率。

图7为性能随缓存大小变化的仿真图，在这个场景中，行人组及汽车组中的节点个数为50，节点内存在10－50 MByte变换。

图7 缓存大小变化对性能的影响Fig.7 Network performance under different buffer size

图7a中消息的投递率随着节点缓存的增大而提高，这是由于节点内存较小时容易发生拥塞，使得节点不得不丢弃某些消息从而影响投递率，随着内存的增加更多的消息能够保存在内存中使得消息成功投递的机会增加。ACK消息的引入能够删除冗余消息，腾出空间用来存放其余的消息，从而进一步提高投递率。路由使用AAD后能用较少的ACK消息来实现删除冗余消息的目标，在提高投递率的同时降低消息的平均时延。在图7b中传输时延逐渐增加，这是因为那些因内存不足被删除的消息在节点内存较大的时候会被保留下来，它们会经历更长的时间被投递到目的节点，导致传输时延的增加。图7c中AAD与洪泛ACK几乎具有相同的开销，表明AAD能够达到洪泛ACK对网络冗余消息删除的效果。

4 总结

本文研究了ACK消息在冗余消息删除上发挥的作用，阐明了洪泛ACK消息带来的问题，并根据节点对于ACK消息需要程度的不同，提出了自适应的ACK分发机制，该机制实现简单，且扩展性极强，能够适用于任何多副本路由机制。仿真结果表明，改进后的ACK分发机制能够有效的提高网络数据的投递率，降低端到端时延，提高网络性能。

［1］熊永平，孙利民，牛建伟，等.机会网络［J］.软件学报，2009，20(1):124-137.XIONG Yongping，SUN Limin，NIU Jianwei，et al.opportunistic networks［J］.Journal of Software，2009，20(1):124-137.

［2］KHALED H，KEVIN A，ELIZABETH B.Delay Tolerant Mobile Networks (DTMNs): Controlled Flooding Schemes in Sparse Mobile Networks［J］.IFIP Networking，2005:1180-1192.

［3］RICHARD J L，PADMA M ，MATT E ，et al.Epidemic routing with immunity in Delay Tolerant Networks［J］.Military Communications Conference，2008，21(1):1-7.

［4］KAVEEVIVITCHAI S，OCHIAI H，ESAKI H.Message Deletion and Mobility Patterns for Efficient Message Delivery in DTNs［J］.Pervasive Computing and Communications Workshops，2010，23(6):760-763.

［5］WIKIPEDIA.The Free Encyclopedia.MAC Address［EB/OL］.(2011-09-06)［2012-03-05］.http://en.wikipedia.org/wiki/MAC_address.

［6］MATSUDA T，TAKINE T.(p，q)-epidemic routing for sparsely populated mobile ad hoc networks［J］.Selected Areas in Communications，2008，26(5):783-793.

［7］JIN Zhigang，ZHAO Ximan，LUO Yongmei，et al.Adaptive Priority Routing with Ack_Mechanism for DTN networks［J］.Wireless Communications ＆ Signal Processing，2009，32(1):1-5.

［8］KERANEN A，OTT J，KARKKAINEN T.The ONE Simulator for DTN Protocol Evaluation［C］//ICST.The 2nd International Conference on Simulation Tools and Techniques.Italy:ACM，2009:1-10.

［9］VAHDAT A，BECKER D.Epidemic Routing for Partially connected Ad Hoc Networks［R］.Duke University:Technical Report CS-200006，2000.

［10］ANDERS L，AVRI D，OLOV S.Probabilistic routing in intermittently connected networks［J］.Service Assurance with Partial and Intermittent Resources，2004，18(2):239-254.