DTN中一种基于内容分类的数据分发算法

焦亚洲，金志刚，舒炎泰

(1. 天津大学计算机科学与技术学院，天津 300072；2. 天津大学电子信息工程学院，天津 300072)

传统的网络在设计数据分发算法时假设网络中的端到端路径总是存在的，然而在一些新出现的无线网络中，这种假设却不复存在．由于节点移动、分布稀疏等多种原因，这种网络常常处于不连通的状态，一般将这种网络称为容迟/容断网络(delay/dis-ruption tolerant networks，DTN)[1]．由于 DTN 的特点，给DTN中的数据分发带来了新的挑战，考虑到DTN中每个要转发的数据在中间节点上存储较长时间，因此内容存储便成了 DTN的核心服务[2]．所以笔者提出了一种基于内容分类(content classification，CC)的数据分发算法，将数据按内容分类后进行分发．该算法基于发布/订阅架构，该架构具有异步通信、松耦合和多点通信的特点，尤其适合DTN这样的环境．在发布数据的方式上与传染病协议(epidemic protocol，EP)[3]相同，但该方法消耗资源太多．单纯拉的方式相当于直接传输(direct transmission，DT)[2]，其延迟会非常大．因此本算法采取推拉相结合的方式，让订阅节点的订阅请求以洪泛的方式在网络中扩散，同时允许源节点将其发布的数据复制给中间节点，但中间节点只有在收到其他节点的请求时，才进行转发．

同时，DTN中节点多是一些移动终端，其缓存通常十分有限，缓存管理好坏直接影响着数据分发的性能．文中根据网络中各类数据的流行度来管理节点的缓存，在缓存不足时，可以保证网络中多数节点的利益．同时，提出了基于订阅时间的副本删除算法，在保证多数节点利益的同时照顾了少数节点的利益．

近些年来，很多研究人员对 DTN中的数据分发进行了研究．文献[4]针对车载网络的特点提出了一种基于随机存储和重放机制的数据分发系统．文献[5]针对公共交通系统设计了一种不需要节点标识的数据分发系统．文献[6]利用节点的社区特性来选择合适的推拉边界，但这种方法仅适用于节点具有社区特性的环境．与本文比较接近的是 DIRECT[7]，但该算法中源节点并不向网络中推送数据，延迟相对较大，并且该算法仅仅依靠消息的名字来进行匹配，这在实际中并不容易做到．而且，上述文献中都没有考虑节点的缓存管理问题，文献[8]根据对订阅节点订阅内容的预测来管理缓存，但是该方法并不能保证网络中节点利益达到全局的最优化．

1 基于内容分类的算法

假定需要分发的数据事先已按其内容进行了分类，接下来介绍本文所提的 CC算法．该算法所针对网络中的节点可分为 3种角色：订阅节点、发布节点和中间节点，同一个节点可以是这3种角色中的任意一种或几种．

1.1 节点的3种角色

订阅节点是指对某类消息发布了订阅请求的节点．当一个节点想获得它感兴趣的数据时，执行订阅操作，并标上所订阅消息的类别以及该订阅的发布时间、序列号、有效期，之后在遇到其他节点时将此订阅请求发送给对方．另外，如果订阅节点已经收到所订阅的消息，则需删除之前发布的订阅请求，以减少网络中对此消息的不必要传输．该节点可以单独发布删除的消息，也可以在发布新的订阅时捎带此信息．

发布节点是指发布了某类消息的节点．当一个节点想发布数据时，执行发布操作，并标上数据创建时间、分类号、版本号和有效期，这个数据就变成一个消息．分类号指明了本消息所属类别，版本号用来区分同一类不同消息，有效期则指明该消息的生存时间．之后当其遇到其他节点时，就将该消息发送给对方.

中间节点是指对于某消息，既没有发布此消息也没有订阅此消息的节点，如果中间节点收到发布节点发送的消息，将对其进行缓存，但是只有收到其他节点对此消息的订阅请求时才转发；如果是收到了订阅节点的订阅请求，则在遇到其他节点时也转发此请求．

1.2 转发算法

网络中的每个节点维护着两张表：请求列表和消息列表．当节点收到其他节点的订阅请求后，它按照自己记录的这两张表中的内容执行相应的操作．

请求列表记录了本节点发布或是收到的订阅请求的信息，如表1所示．

表1 请求列表Tab.1 Request list

消息列表记录了本节点发布或收到的消息的相关信息，如表2所示．

表2 消息列表Tab.2 Message list

当节点收到其他节点请求后，它按如下流程操作

(1) 节点检查自己消息列表是否有被请求的消息.

(2) 如果有，则转发给请求节点，并将该消息的被请求次数加1.

若该节点收到对多个不同消息的请求，则按已记录这些消息被请求次数的多少依次转发给请求节点.

(3) 如果没有缓存此消息，则检查请求列表，看是否记录有相同的请求.①如果有，则将该消息的被请求次数加 1，并将上一跳节点改为本次请求的节点；②如果没有，就将此请求添加到请求列表中．

(4) 当节点处理完其他节点的请求后，若它没有缓存所请求的消息，它也开始请求此消息．①如果在收到的请求中，源节点指明需删除的订阅序列号，则节点在请求时也要加上这个条目，以使得过时的订阅请求尽快从网络中被清除；②如果节点在缓存已满时收到其他节点对某类消息的请求，将此消息被请求次数加 1，如此数值大于排在最后的一类消息，本节点转发此请求，否则将不再转发．

(5) 当一个节点收到了所请求的消息后，检查是否是该消息的订阅节点．①如果是，就将这个消息恢复为原始数据；②如果不是，将消息发送给请求列表中记录的上一跳节点，如果这个上一跳节点在这个时候找不到了，就将此消息的相关信息在一跳范围内广播看是否有节点对此消息感兴趣．

值得指出，算法将消息被请求次数加 1的操作，仅在收到订阅请求的源节点与已记录的不同时才执行．

1.3 缓存管理

如果节点的缓存被占满，某些消息将会被丢弃，但究竟哪些消息应该被丢弃，是一个值得考虑的问题．一种常见的方法是按照先进先出(first in first out，FIFO)的原则，这实际上是对各类消息同等对待，是对缓存资源的平均分配．由于 DTN中的节点只能依靠彼此相遇的机会来转发数据，为了使消息能够尽快到达目的节点，通常只能将消息复制多份分发给网络中的其他节点，以期待该消息的一个副本能尽快到达目的节点，很显然，网络中该消息的副本数越多，目的节点尽早收到该消息的可能性就越大．而网络中对各类消息感兴趣的节点数通常是不相同的，因此对各类消息平均分配缓存资源是不公平的．

处理这一问题的根本思路是：在缓存不足时，应该对缓存资源按需分配而不是平均分配．因此根据消息所含内容的流行度(content popularity，CP)来管理缓存，因为消息的被请求次数是消息流行度的一个重要指标，在缓存不足时，被请求次数最少的消息应该首先被删除．如果有两个或多个消息的被请求次数相同，则删掉剩余有效期最短的消息．当然对于自己发布和订阅的消息各节点都是优先缓存的．这样，网络中流行度最高的消息在节点的缓存中会被存储更久的时间，这也就增加了该消息被订阅节点请求到的概率，因此，CC算法可以保证网络中多数节点的利益．

2 EP和CC算法的理论分析

为了对EP和CC算法有一个定性的认识，先从理论上分析采用FIFO策略的EP和本文中所提的采用CP管理策略的CC算法在消息平均延迟和网络开销(Overhead)方面的性能．平均延迟定义为所有收到订阅消息的节点，从其发布订阅到收到消息所经历时间的平均值．Overhead的定义为网络中消息被传送的次数与发布的消息数的比值，Overhead的值是与时间有关的，以消息到达目的节点的平均时间来度量．

由于篇幅限制，只分析网络中有两类消息的情况．假定每类消息只有1个版本，分别由1个源节点发布，两个源节点不参与转发．除这两个源节点外，网络中还有 100个节点．节点缓存大小都为消息大小的整数倍(用 n-slot表示，n＝1，2)，记录订阅请求相关信息所占用缓存空间忽略不计，各节点缓存是有限的，即网络中有部分节点缓存仅能够存储一类消息．网络中任意两个节点间相遇的时间间隔服从参数为β的指数分布，指数分布具有无记忆性，因此节点缓存状态的变化具有无后效性，可以用马氏链来建模．

因此，分析从考察节点缓存变化的马氏链着手．马氏链的状态代表网络中缓存处在此状态的节点数．在此对马氏链中的状态符号做以下约定：状态符号中的B代表该节点的缓存中存储消息的情况，考察 EP时，采用一维马氏链，其下标代表所存储的消息的种类，下标为 0则表示没有存储消息，下标的次序代表了收到消息的先后次序(CC算法对此不做区分)．考察CC时，采用二维马氏链，第1个下标的含义与考察EP时相同，第2个下标表示该节点收到的订阅请求的情况，其指明了订阅是针对哪一类消息的，该值为0则表示没有收到订阅请求，为x则表示收到的订阅请求是任意一种情况．所有状态符号上标中的数字代表该节点缓存的大小，上标中有s的代表此节点是发布订阅的源节点．

2.1 采用FIFO策略的EP算法的理论分析

考察采用 FIFO策略的 EP，因为网络中只有两类消息，且每类只有 1个版本，所以只需考察缓存为1-slot和大于1-slot(用2-slot表示)两种情况．

图1和图2分别给出了节点缓存为1-slot和2-slot时，节点缓存变化的马氏链．

图1 EP时缓存为1-slot时的马氏链Fig.1 Markov chain of EP as buffer space of 1-slot

图2 EP时缓存为2-slot时的马氏链Fig.2 Markov chain of EP as buffer space of 2-slot

式(1)～式(4)中的最后一项1代表发布该消息源节点．

根据Kolmogorov方程，从图1和图2中可以得到图中各个状态所满足的微分方程，如

将各个状态所满足的微分方程联立求解就可得到各状态随时间变化的数值解，这样将网络中所有某类消息的状态相加，就可以得到EP时网络中第1和第2类消息副本数ep1M 和ep2M 随时间变化的函数，即

因为采用 EP时，两类消息在网络中的地位完全一样，所以式(6)和式(7)实际上是一样的．

2.2 采用CP策略的CC算法的理论分析

在分析采用CP策略的CC算法时，假定网络中对第1类消息的订阅(用R1表示)数大于对第2类消息订阅的(用 R2表示)数．因为假定任意两个节点间相遇的速率都相同，因此 R1在网络中的扩散速度要大于R2，所以中间节点记录的R1大于R2，当其缓存不足时，将删除第2类消息．

图3和图4给出了中间节点缓存为 1-slot和 2-slot时的马氏链(为清晰起见，省去了转移速率上的β和转出状态的符号)．

图3 CC时缓存为1-slot时的马氏链Fig.3 Markov chain of CC as buffer space of 1-slot

图4 CC时缓存为2-slot时的马氏链Fig.4 Markov chain of CC as buffer space of 2-slot

图3 和图4中状态转移速率上的1表示只有遇到发布消息的源节点时才发生此次转移，符号iT(i＝1，2，…，11)所代表的表达式为

考察订阅节点的缓存变化情况，当缓存空间不足时，这些节点将优先存储自己所订阅的消息．当缓存为 1-slot时，发布 R1的节点的缓存变化相当于图 3中初始状态位于 B01,1的马氏链；而当缓存为2-slot时，发布R1和R2的节点的缓存变化分别相当于图4中初始状态位于 B0

2,1和B02,2的马氏链；只有缓存为 1-slot时，发布 R2的节点缓存变化比较特殊，因为它是优先存储第2类消息的．图5给出了缓存为1-slot时，发布R2的节点缓存变化的马氏链．

图5 CC时缓存为1-slot发布R2的节点的马氏链Fig.5 Markov chain of CC as buffer space of 1-slot and subscription of R2

与第2.1节相同，从图3～图5得到采用CC算法时网络中的每一类消息的副本数随时间变化的函数为

2.3 平均延迟的理论分析

设T为表示网络中消息传输延迟的随机变量，F( T)为其分布函数，F ( T)满足的微分方程为[9]

F′( T ) = β M( t) ( 1 − F ( T )) (21)则网络中各类消息延迟的期望E(T)为

将式(6)、式(7)、式(19)、式(20)得到的 ()M t 代入式(21)和式(22)中，即可解得采用不同算法时各类消息延迟的期望值．

令 ()A T表示网络中所有订阅节点收到其订阅的消息的平均延迟，则

式中1N和2N分别表示网络中发布 R1和 R2的节点个数．

2.4 Overhead的理论分析

值得指出，采用EP时，当两节点相遇，要交换彼此的 summary vector，以确定彼此没有缓存的消息，而采用CC时，节点相遇只需向对方发送订阅请求．因为发送 summary vector和订阅请求字节数相对于传递消息都比较小，在分析Overhead时都不考虑．

设Overhead的期望值为 ()E O，其计算式为

式中 ()E C和 ()E D分别表示当消息到达目的节点时，除源消息外其留存在网络中的平均副本数和其被丢弃的平均次数．文献[10]给出了 ()E C的表达式，即

将式(6)、式(7)、式(19)、式(20)得到的 M(t)代入式(25)即可得出各类消息的 ()E C．

类似地也可以得到

令 ()A O为采用 CC算法时，两类消息的平均Overhead，则

考察按照推导出的平均延迟和 Overhead的情况．图6和图7给出了网络中缓存为1-slot和2-slot的节点个数分别为 50时的平均延迟和 Overhead的情况，计算时β的取值与文献[10]相同，为0.004 7．

图6和图7中CCA表示采用CC算法时，两类消息的平均值，其值分别由式(23)和式(29)得出．从图6和图7可以看出，采用CC算法时，网络中发布R1的节点收到该消息的平均延迟与采用 EP时相当甚至更低，同时其产生的 Overhead却比 EP时少了10%左右．此外，整个网络中订阅两类消息的节点的平均延迟只比 EP时多了不到 10%，但同时网络中的Overhead却比 EP时少了 20%以上，当网络中 N1和N2的值相差较大时这种情况更加明显，如当1N为90、2N 为10时，平均延迟只比EP时多了3.4%，但是Overhead却少了27.8%．

图6 1-slot和2-slot的节点个数均为50时的平均延迟Fig.6 Average delay as nodes’ numbers of 1-slot and 2-slot of both 50

图7 1-slot和2-slot的节点个数均为50时OverheadFig.7 Overhead as nodes’ numbers of 1-slot 2-slot nodes of both 50

图8 和图9给出了网络中缓存为1-slot和2-slot的节点数分别为 80和 20时，平均延迟和 Overhead的情况．

图8 1-slot和2-slot的节点个数为80和20时的平均延迟Fig.8 Average delay as nodes’ numbers of 1-slot of 80 and 2-slot of 20

将图 8、图 9和图 6、图 7对比，可以看到，当网络中缓存不足的节点较多时，CC算法的表现更好，此时，网络中第 1类消息的平均延迟始终低于 EP，而其产生的 Overhead更比 EP时少了 20%左右．两类消息的平均表现也更加出色，如在1N为 90、2N为10时，平均延迟比 EP时少了 1.6%，而 Overhead更是少了 37.1%，这说明 CC算法在缓存资源紧张时表现更加出色．

图9 1-slot和2-slot的节点个数为80和20时的OverheadFig.9 Overhead as nodes’ numbers of 1-slot of 80 and 2-slot of 20

值得指出，因假定每类消息只有一个版本，因此两类消息最终都能够被成功投递．当网络中不断有新消息产生且节点的缓存不足时，如果采用 FIFO策略，老的消息就可能会在被成功投递之前从网络中消失，而采用文中所提的 CP策略却至少可以保证大多数订阅节点的利益，然而 CP策略在某些极端情况下却会造成部分节点“饿死”的情况．如以文中理论分析的场景为例，如果网络中所有节点的缓存都为1-slot，并且发布 R2的节点很少，那么网络中节点的缓存中存储的都将是第1类消息，而发布R2的节点最终收到第2类消息可能会经历漫长等待，甚至因消息过期而最终得不到消息．

3 基于订阅时间的副本删除算法

在实际应用中，各个节点缓存大小通常并不相同，并且由于网络不连通，每个节点记录的各类消息的流行度也可能与实际并不一致，为了防止这种极端情况出现，在上述算法基础上做一些改进．

考虑到网络中的订阅请求是以订阅节点为中心向外扩散的，因此收到此请求的先后时间在很大程度上反映了中间节点与订阅节点距离的远近，那么如果是将消息转发给离订阅节点更近的节点，而后将自己存储的消息副本删除，这对此消息的最终投递并不会造成太大影响，但却节省了该节点的缓存空间，使得它可以存储一些订阅较少的消息，因此提出了一种基于订阅时间的副本删除算法，根据节点收到的订阅请求的时间有选择进行副本删除，该算法具体如下：设节点 A的缓存为 n-slot，其缓存中存储有某类消息m，并且在 A记录的各类消息的被请求次数的排序中，m位于前[n/2]．考察A遇到了对m有请求的节点B时的情况，设 Si和 N ( Si)(i＝A，B)为节点记录的订阅某类消息 m的源节点的集合及该集合中元素的个数．对∀ C∈( SA∩ SB)，令 TA-C和 TB-C分别表示A和B记录的收到源节点为 C的订阅请求的时间，h为( SA∩ SB)中 TA-C早于 TB-C的元素的个数，则当 A将m转发给B后，其以概率p将m从其缓存中删除，p的表达式为

4 性能评价

通过仿真来比较CC、EP、DIRECT和DT这4种算法的性能，其中 CC采用带副本删除算法的CP缓存策略，后3种算法采用 FIFO策略．比较的指标有3个：平均延迟、Overhead和投递率．Overhead的度量时长是仿真的整个时长，投递率定义为针对每个消息，订阅该消息的节点收到该消息的数量占发布的订阅数量的比例．仿真实验采用一个基于 Java的仿真工具 dtnsim[1]，它是专门为 DTN 设计的一个离散事件仿真器．本实验在 dtnsim 中添加了发布/订阅机制，并且使一个消息可以发送给多个请求节点．

假定任意两个节点间的相遇时间间隔服从指数分布，这个假定对传统的移动模型如 Random Way Point(RWP)和 Random Direction等来讲是合适的，但在理论分析时由于篇幅限制仅考察了网络中有两类消息的情况，此假定下验证网络中消息的类别数多于两个的情况．采用 RWP模型进行仿真实验，仿真参数如下：网络中共有两个发布消息的源节点和 100个其他节点，两个源节点不参与转发，它们每隔 10 s发布一个消息，消息的类别随机选择，但每个节点每类消息最多只发布 10个，并依次赋给同类消息相应的版本号，每个消息的大小为500字节，有效期为8,min．其他节点每隔 1,min发布一个订阅请求，每个节点共发布10个订阅，订阅类别、版本号和节点号随机选择．链路的带宽设置为每秒传输 5个消息．节点的缓存设置为 20-slot．每个节点的移动速度服从10～20,m/s上的均匀分布，仿真区域为200,m×200,m，仿真共进行30,min．

图10、图 11和图 12给出了 3项指标随类别数变化的情况．可以看出，在平均延迟和投递率指标上，随着消息类别数的增加，CC算法表现得比EP和DIRECT越来越好，因为网络中的节点均只能缓存20个消息，而随着消息数的增加，缓存资源变得越来越紧张，而EP和DIRECT采取的FIFO策略是对各类消息平均分配缓存资源，因此每类消息被分到的资源越来越少，而CC采用的CP策略采取的是按需分配，可以满足网络中多数节点的利益，而同时每个节点根据收到订阅请求的时间有选择地删除一些消息的副本，进一步照顾了少数节点的利益，因此能够保持较高的投递率和较低的延迟．由于CC采取了推拉相结合的方法，防止了消息在网络中的洪泛，因此Overhead比EP低很多．由于CC中的源节点可以向网络中推送数据，跟DIRECT相比这会增加网络的Overhead，但由于采取了CP缓存管理策略，减少了消息被丢弃的次数，同时CP策略在缓存了被请求次数较多消息后就不再接收被请求次数较少的消息，而删除某消息后也不再接收该消息，避免重复接收某消息而后又丢弃的情况，因此 CC在 Overhead上达到与DIRECT相当的水平．DT算法虽然Overhead很低，但投递率也很低，平均延迟很大，在实际中并不适用．

图10 4种算法的平均延迟(RWP)Fig.10 Average delay of four algorithms(RWP)

图11 4种算法的Overhead(RWP)Fig.11 Overheads of four algorithms(RWP)

图12 4种算法的投递率(RWP)Fig.12 Delivery ratio of four algorithms(RWP)

图13 4种算法的平均延迟(Haggle)Fig.13 Average delays of four algorithms(Haggle)

分析和仿真结果都是在节点间的相遇时间间隔服从指数分布前提下得出的，而根据对实际环境中采集的trace数据的研究发现，节点间相遇时间间隔在很多时候却近似服从重尾分布．通过一个实际的trace数据考察所提算法的性能，数据来自于Haggle项目[11]，是利用iMotes记录剑桥大学学生以及剑桥市热点地区蓝牙设备间的接触情况，在本仿真中仅仅用到了36名学生10,d的trace数据．仿真时，36个节点在每天早8点到晚8点间每2,h发布一个消息(最后一天不发布)，消息类别、版本号和节点号均随机选择，总的类别数为 10个，每个消息有效期为1,d．同时，36个节点每 3,h发布一个订阅，订阅类别随机选择．

图13～图 15给出了 3项指标随节点缓存变化的情况．从中可以看出，CC算法与EP、DIRECT、DT相比表现出了与采用 RWP模型时相似的性能，在缓存不足时，其在3项指标上的表现都超越了EP和DIRECT，这说明文中所提算法的适用范围是很广的．

图14 4种算法的Overhead(Haggle)Fig.14 Overheads of four algorithms(Haggle)

图15 4种算法的投递率(Haggle)Fig.15 Delivery ratios of four algorithms(Haggle)

5 结 语

针对DTN的特点提出基于内容分类的数据分发算法，采取推拉相结合的方式进行分发．同时，根据网络中各类数据的流行度来管理节点的缓存，并进一步基于订阅时间有选择地进行副本删除，保证多数节点利益的同时照顾了少数节点的利益．理论分析和仿真实验表明，在缓存不足时，文中所提算法的性能优于 EP、DIRECT和 DT算法．下一步，将在更多场景中验证文中所提算法各方面的性能．

［1］ Jain S，Fall K，Rabin P. Routing in a delay tolerant network[C]// Proceedings of ACM SIGCOMM． Portland，USA：Association for Computing Machin-ery，2004：145-157.

［2］ 熊永平，孙利民，牛建伟，等. 机会网络[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(in Chinese).

［3］ Vahdat A，Becker D. Epidemic Routing for Partially Connected Ad Hoc Networks[R]. Durham：Department of Computer Science， Duke University：Technique Report CS-2000-06，2000.

［4］ Leontiadis I，Mascolo C. Opportunistic spatio-temporal dissemination system for vehicular networks[C]// Proceedings of Mobisys Workshop on Mobile Opportunistic Networking. San Juan：Association for Computing Machinery，2007：39-46.

［5］ Carrilho S，Esaki H. A Pub/Sub message distribution architecture for disruption tolerant networks[J]. IEICE Transactions on Information and Systems，2009，E92-D(10)：1888-1896．

［6］ Li F，Wu J. MOPS：Providing content-based service in disruption-tolerant networks[C]// Proceedings IEEE ICDCS． Montreal，Canada：Institute of Electrical and Electronics Engineers Inc，2009：526-533.

［7］ Solis I，Garcia-Luna-Aceves J J. Robust content dissemination in disrupted environments[C]// Proceedings of the 3 ACM workshop on Challenged Networks. San Francisco，USA：Association for Computing Machinery，2008：3-10.

［8］ Sollazzo G，Musolesi M，Mascolo C. TACO-DTN：A time-aware content-based dissemination system for delay tolerant networks[C]// Proceedings of MobiSys Workshop on Mobile Opportunistic Networking. San Juan：Association for Computing Machinery，2007：83-90.

［9］ Haas Z J，Small T. A new networking model for biological applications of Ad Hoc sensor networks[J].IEEE/ACM Transactions on Computer Systems，2008，14(1)：27-40.

［10］ Zhang X，Negliaet G，Kurose J，et al，Performance modeling of epidemic routing[J]. Computer Networks，2007，51(10)：2867-2891．

［11］ Leguay J，Lindgren A，Scott J，et al. CRAWDAD trace set upmc/content/imote[EB/OL]. http：//crawdad.cs. dartmouth. edu/upmc/content/imote，2006-11-17.