- 1 -
中国科技论文在线
DTN中基于公平丢包的拥塞控制研究
王梦杰，谢东亮**
作者简介：王梦杰（1987-），男，硕士，移动互联网/延迟容忍网络
通信联系人：谢东亮（1974-），男，副教授，移动智能终端与移动互联网、B3G/4G 宽带无线移动通信、
泛在、异构网络融合与协同、移动社会网络、延迟容忍网络. E-mail: xiedl@
（北京邮电大学 网络与交换技术国家重点实验室 北京 100876）
摘要：延迟容忍网络(Delay Tolerant Networks，DTN)采用“存储-携带-转发”的方式进行路由，5
依靠节点间的机会接触转发数据。当面对存储资源的持续性需求，而保管者本身的缓存又不
能得到释放时，势必造成某些活跃节点缓存资源的耗尽，此时就会导致网络的拥塞。为了解
决这一问题，本文建立了一种社会性多副本延迟容忍网络模型，并提出了一种基于公平丢包
的拥塞控制机制，试图在保证数据包级公平性的基础上缓解拥塞。最后，在 ONE仿真平台
进行仿真验证，结果表明该机制可以更好的提升网络吞吐量、提高数据交付率。 10
关键词：延迟容忍网络；拥塞控制；网络模型；社会性；公平性
中图分类号：
Research on Congestion Control based on Fair Drop in DTN
WANG Mengjie, XIE Dongliang 15
(State Key Laboratory of Network and Switching, Beijing University of Posts and
Telecommunications, 100876)
Abstract: Delay Tolerant Networks (DTNs) routing is based on "storage-carry-forward" approach, and
nodes communicate with each other based upon intermittent or opportunistic faced
with the ongoing demand of storage and custodians itself can't release the cache, it will cause some 20
custodians's cache resource depletion. This will lead to network congestion. In order to solve this
problem, this paper established a social delay tolerant network model, and puts forward a congestion
control mechanism based on Fair Drop duplicate. Extensive simulations show that the proposed Fair
Drop algorithm can improve network performance greatly.
Key words: Delay Tolerant Networks; Congestion Control; Network Model; Sociality; Fairness 25
0 引言
延迟容忍网络（DTN）源自于美军卫星通信，其目的是解决具有长延迟、高错误率、资
源受限、连接频繁中断等特点的受限网络中的通信问题，其特征是利用“存储-携带-转发”的
方式实现端到端的有效数据传输，对于国土资源、气象、航空航天、深洋、国防具有重要战30
略意义。由于 DTN 网络中节点移动性高、网络拓扑变化频繁、数据传输差错率高等原因，
传统的 Internet 路由协议和 Ad hoc 路由协议并不适用于 DTN 网络。近年来，随着 DTN 网
络研究的逐渐深入，很多研究者提出了多副本方式的路由协议，如：传染路由( epidemic) 、
散发与等待协议(Spray and Wait )等。
早期延迟容忍网络研究多数基于节点的完全随机运动，下一跳节点的选择是盲目的。其35
后许多研究发现，人类活动并不是完全随机的，而是具有明显的社会性。社会关系的变化非
常缓慢，可以用来提高 DTN 网络中的投递成功率。借助社会度量高的节点，数据包可以以
更高的概率被传递到目的节点。
相比于单副本路由，在相同的包产生率下多副本路由必然增大中间节点的负担。在路由
中引入社会性后，网络负担会向活跃的节点集中，导致这些节点很容易拥塞。情况严重时甚40
- 2 -
中国科技论文在线
至会造成全网的拥塞。网络的拥塞最终造成平均消息交付率的下降、端到端时延的增加及节
点资源和能量的过度消耗。因此，拥塞控制是 DTN 获得网络可靠性、稳定性和可接受性能
的关键技术。本文首先建立了一种基于社会性的多副本延迟容忍网络模型，然后在此基础上
提出了一种考虑数据包级公平性的拥塞控制策略：FD（Fair Drop）策略。
1 相关工作 45
目前关于 DTN 路由的研究发现，多副本路由能够比单副本路由取得更好的网络性能，
即，增加副本数量可以降低延迟，提升投递率。
而对社会网络的研究通常认为活跃个体应当承担更多的转发任务，因为这样有利于提高
数据包转发效率(BubbleRap，SimBet)。然而这样的节点往往仅占极少数，文献[1]分析了社会
网络的幂律分布特性。当周围节点需要发送数据时，必然选择这几个节点作为转发节点。网50
络运行一段时间后，所有的数据都逐渐汇聚到一个不断缩小的节点子集中，最后子集中的节
点将是需求最大的。一旦数据和副本数增长过快，这几个节点不能及时把数据转发出去，它
们的缓存就会拥塞。源节点随之开始竞争缓存等网络资源。DTN 中的网络资源可以是节点
的存储空间和机会连接状态下的链路带宽。本文涉及的网络资源主要是指节点存储空间，有
人假设中继节点的容量无限大、节点缓存无限等，这些都是不切实际的。 55
根据拥塞的资源关注点，可以将 DTN 拥塞控制分为三种类型[2]：第一种类型是节点级
的拥塞，主要表现为节点缓冲区溢出，导致分组丢失。第二种类型是链路级的拥塞，主要是
链路冲突严重，即链路饱和。第三种类型是区域级拥塞，在事件监测型应用等场景中，拥塞
并不表现为某个节点溢出或一个链路饱和，而是事件周围的一个地理区域的流量过载。本文
重点关注节点级拥塞这种情况。 60
许多研究人员对拥塞控制机制进行了研究，几种典型的缓解拥塞的方法如下：丢弃数据
包，迁移数据到替代位置存储，使用替代路径，降低源节点的数据发送速率和副本配额。
丢弃数据包应该是最简单的也是最有效的一种缓解拥塞的方式，文献[3]对当前常见丢包
策略进行了总结：FIFO (first in first out)，丢弃最先到达的数据包；MOFO (drop most forwarded
first)，丢弃转发次数最多的数据包；SHLI (drop shortest lifetime first)：丢弃生命期最短的数65
据包。文献[4]统计每个节点缓存中每条消息在其邻居中出现的次数。如果遇到多个邻居都持
有该消息副本，则将其删除。如果遇到很少邻居持有该副本，则再遇到邻居时就给邻居一个
副本，以此调控网络中的副本数量。
文献[5]提出了一种多策略混合的拥塞控制方法。根据缓存占用情况，将拥塞分为不同的
级别，从而采用不同的拥塞控制机制。1）轻量级负载：该阶段节点增加缓存中每条消息的70
副本系数，采用加法增长的方式。2）适度负载：减小缓存中每条消息的副本系数，采用乘
法减小的方式。3）重负载：采用基于相遇概率的效用路由。4）拥塞（例如缓存占用率 80%）：
选择最早到达的消息，转移到缓存最大的邻居节点中。5）缓存占用率 100%：如果拥塞节
点的缓存满了，则开始执行丢包策略。
上述文献提出的拥塞控制机制都能在一定程度上缓解拥塞，但是并不能保证在节点拥塞75
时，提供数据包级公平的服务。针对此种情况，我们提出了一种考虑数据包级公平性的拥塞
控制机制。
- 3 -
中国科技论文在线
2 考虑数据包级公平性的拥塞控制机制
网络模型
理想的拥塞控制机制应尽可能不依赖具体路由，以便适用于不同场合。但是不同场合下80
的 DTN 性质有太大的区别，难以全面覆盖。我们尤其关心具备如下两个特点的 DTN 网络。
网络建模
网络典型的工作场景是校园，大型会议，办公楼等。通信节点由人员携带，移动规律与
人类一致，因此体现出很强的社会性。
部署在某一平面区域中的 n 个节点构成一个多跳的 DTN 网络。将 DTN 节点的集合记85
为 N。集合中的各节点社会度量不同，但地位是同等的。每个节点都有可能成为源节点，请
求其它节点转发数据。同时，一个节点在被路由规则选中时，应该为相应的节点转发数据。
我们假设节点不能同时发送和接收数据；节点以一定的速率移动，移动规律同人类一致；
假设数据从产生到被目的节点接收的过程中不存在数据的压缩或聚合，而且不考虑安全威
胁。我们同时做出如下规定： 90
1) 将源节点向目的节点发送的数据包记为 m，所有源节点发出的数据包大小都是一样
的，记为 Pm；
2) 将源节点消息产生速率记为 V，网络中所有源节点都以固定的速率 V 产生消息。
3) 网络采用多副本的方式发送消息。将每个消息的副本配额记为 k，k 由源节点指定。
当一个节点转发消息时，副本在当前节点与下一跳节点之间分配。任意时刻，网络95
中携带消息 m 的节点数不会大于其配额 k。
4) 将副本系数记为 a，副本系数表明了一个消息在某节点上的副本数。消息最初产生
于源节点的缓存中时，其副本系数 a 等于其副本配额 k。
5) 将缓存空间记为 B，缓存空间即节点用于存放暂时未能转发出去的消息的空间。由
于消息的大小是固定的，缓存空间用可容纳的消息个数来描述。各节点的缓存空间100
可能不同。
6) 将副本处理效率记为 E，表示中间节点单位时间内可以处理掉的副本数。处理掉指
的是节点可以将该副本删除，从而空出相应的缓存空间。根据具体的路由，一般在
以下情况下中间节点可以将副本处理掉：a）遇到目的节点并成功将消息交给目的
节点；b）收到目的节点向网络反馈的确认消息；c）副本生命期已过。 105
7) 拥塞度 Ci：将缓存中所有数据包的大小之和，同缓存空间的大小比值称为拥塞度。
可以用如下方式描述：
1 (0 1)
n
m
m
P
Ci Ci
B
== ≤ ≤
∑
其中 Ci 表示当前节点 i 的拥塞度，Pm表示数据包 m 的大小，B 表示缓存空间的总
容量。 110
我们给出了不同拥塞度下节点处理拥塞的不同方式：
a) 当 0≤Ci< 时，表示节点 i 处于轻量级负载状态，该节点可以正常接收消息
并存储。
b) 当 ≤Ci< 时，表示节点 i 处于适度负载状态，即将进入拥塞状态，本文对
- 4 -
中国科技论文在线
处于这种状态下的节点进行拥塞缓冲操作。 115
c) 当 ≤Ci≤1 时，表示节点 i 处于拥塞状态，对节点 i 进行拥塞避免操作，直到
Ci 的值低于 。
拥塞缓冲主要是指为了缓解节点到达拥塞的状态而采取的一系列措施。本文采取的
方法为：该节点向其缓存中所有消息的源节点发送一个控制信息，降低这些节点发出数
据包的副本配额，使得到达该节点的数据包减少，降低其在单位时间内接收到的数据量，120
而实现拥塞缓冲。
拥塞避免是指对已处于拥塞状态的节点通过采取一定措施使其回到非拥塞状态。本
文中提出的 FD 策略主要通过公平丢弃数据包的方式实现拥塞避免。
社会性多副本路由
在社会性 DTN 中，路由通常借助节点的社会性和相遇历史来选择下一跳节点，以获得125
更高的递送率和更低的延迟。即使采用随机路由，活跃节点作为中间节点的概率也比其它节
点要高。而社会关系网常表现为复杂网络的形式，符合幂律分布。采用社会性和相遇历史后，
流量会更明显地向活跃节点汇集。
相比于单副本，使用多副本路由可以使 DTN 性能得到很大提高。多副本路由可以分为
两种：一种是由源节点指定副本配额的，另一种是由中间节点自主产生副本的。前一种的典130
型代表是 SW（spray and wait），后一种的典型代表是 Epidemic。Epidemic 是一种极端做法，
即中间节点只要遇到未被“感染”的节点就复制数据包将其“感染”。虽然已经有研究人员做了
相关工作来控制副本数量，但是由中间节点自行决定副本产生和消亡的方式依然很不利于准
确地控制其数量，因此我们的研究将主要基于 SW 方式。另外，文献[6]证明了如果节点运动
符合 IID（独立同分布），那么 SW 的最佳形式就是 BSW（Binary Spray and Wait）。虽然135
社会网络中的节点运动并不是 IID 的，然而基于[7]的分析，我们依然认为 BSW 是最好的方
式。
BSW 可以使一定数量的数据副本更快、更广泛地散发到网络中。纯粹的 BSW 不考虑
社会性和相遇历史。而利用社会性和相遇历史可以使数据副本以更大的概率朝向目的节点。
这二者的结合显然吸引了研究人员的兴趣。本研究提出的公平性保证机制适用于 BSW 与社140
会性、相遇历史结合的路由。
FD 策略
目前研究已经发现网络流量过大时会引发中间节点的拥塞。进一步地，当采用基于社会
性或相遇历史的路由时，少数社会度量高的关键节点会特别容易拥塞。相比于其它节点，活
跃节点的拥塞会带来更严重的网络性能恶化。当中间节点拥塞时，应该采用适当的拥塞缓解145
策略。
为了使得拥塞立即得到解除，发生拥塞的节点必然要丢弃一些缓存中的数据包，或拒绝
新来的转发请求，或二者兼有。本文将分析此时拥塞节点应该如何进行取舍。
优化目标
每个源节点都希望网络能够最大程度保证自身数据能安全到达目的地，然而，每一份数150
据副本在传输过程中都会消耗一定的资源，例如缓存等，任何给定的 DTN 网络都只能支持
一定数量的数据包。如果执行丢包算法时不考虑数据包的公平性，结果将导致某些数据丢失，
投递率下降，反而降低了源节点数据的安全保障。
- 5 -
中国科技论文在线
如果拥塞节点执行的拥塞控制策略适当考虑公平性，则可以让更多的数据包利用网络。
因此我们希望给出一种优化目标为数据包级公平性的拥塞控制机制。 155
数据副本的选择策略
用 BSW 的一个例子来说明公平问题，如图 1 所示：网络中有两个源节点 A,B，它们的
k（副本配额）值均为 8，需要向目的节点发送大小一样的数据包 Ma 和 Mb。经过若干次转
发后，网络中携带 Ma 的节点数为 2，携带 Mb 的节点数为 4。此时它们遇到了拥塞节点。
拥塞节点只能接收 Ma 和 Mb 中的一个。如果拥塞节点接收了 Ma，则网络中携带 Ma 和 Mb160
的节点数分别变为 3，4；如果拥塞节点接收了 Mb，则网络中携带 Ma 和 Mb 的节点数分别
变为 2，5。
图 1 场景示意图
后一种情况显然是不公平的，因为它阻止了本来已经扩散得较慢的 Ma，而加速了本来165
已经扩散得较快的 Mb。由此看到，拥塞节点对数据包的取舍直接影响到节点获取网络资源
的公平性。
进一步分析上述例子，Ma 的系数为 4，Mb 的系数可能为 2 或 4。占用同样多的缓存（数
据包大小一样），如果拥塞节点接收了 Ma，则可以为其带来 2 次扩散机会（包括拥塞节点
自身和未来的一次转发）；如果拥塞节点接收了系数为 2 的副本，则仅能为该信息带来 1170
次扩散机会。可见，在发生拥塞时选择系数大的副本还可以带来更好的网络转发效果。
根据以上分析，在副本配额相同的情况下，副本选择的策略就是接收具有最大系数的副
本。
然而以上分析基于发生竞争关系的源节点拥有同样的 k值。在 节提出的网络模型中，
网络中显然会出现具有不同 k 值的源节点。本节将对这种情况进行更进一步的分析。 175
对 k 副本路由而言，如果一个消息的系数等于 k，则表明网络中仅有一个节点（源）携
带该消息。与任何其它系数小于自身副本配额的节点相比，系数为 k 的节点都应该得到优先
扩散。因此，首先应该接收那些系数等于副本配额值的副本，以体现对源节点消息扩散的公
平。
当副本系数小于 k 时，拥塞节点无法确切得知网络中携带该消息的节点数量。设有两个180
节点 A、B 的 k 值 ka > kb，他们发出的消息分别记为 Ma、Mb。由于 k 值仅取 2 的整数次
幂，ka 至少是 kb 的两倍（或更大的 2 的整数次倍）。只要 Ma 经过一次以上转发，那么拒
绝或丢弃任何一个节点上的 Ma，网络中剩余的 Ma 数量都不会少于 Mb 数量（假设网络中
A
B
C 4Ma
2Mb
2Mb
2Mb
- 6 -
中国科技论文在线
其他节点没有拒绝或丢弃 Ma，Mb）。因此，当两个源节点的副本发生冲突而 k 较大的那个
副本已经被转发过，拥塞节点应该优先接收 k 较小的副本。 185
3 仿真及结果分析
本章我们对所提出的算法进行全面的评估。首先要确定场景所需的社会性多副本路由，
我们对 Bubble Rap 和 Spray and Wait 这两种路由机制进行了整合，在此基础上，我们实现了
所提出的算法。下面简单介绍一下网络中源节点和拥塞节点所必须的功能。源节点周期性的
产生消息发送到随机的目的节点。节点统计自身拥塞度，当进入拥塞状态时，节点开始运行190
FD 算法，直到拥塞度低于阈值。
仿真环境
本文在 ONE（Opportunistic Network Environment）仿真环境中实现了基于上述网络模型
的路由算法，并在此基础上对公平丢包的算法进行了验证。ONE 是芬兰阿尔托大学主导开
发的网络模拟器，是一款功能强大、使用简单、扩展性强的延迟容忍网络专用模拟器，能够195
充分满足路由设计、拥塞管理等方面的仿真需求。
本文使用的实验数据集为 Cambridge，由 Haggle 项目收集。Cambridge 中的数据由该校
学生携带通信节点采集完成，体现出了很强的社会性。节点主要分为两组，分别是剑桥大学
计算机实验室本科一年级和二年级的学生，另外还有一些博士生和硕士生。此数据集覆盖了
11 天的时间。该数据集具体参数如下表 1 所示： 200
表 1 Cambridge参数
参数 值
设备类型 iMote
网络类型 蓝牙
持续时间（天）
粒度（秒）
实验设备数量
内部接触数量
平均接触量（每对设备每天）
11
600
54
10873
另外本文所提算法基于多副本路由，除缓存大小和最大副本配额之外的参数设置如表 2
所示：
表 2 仿真参数设置 205
参数 值
数据包的大小 80K
初始副本配额
消息产生周期
消息生存时间 TTL
副本配额增长系数
缓存拥塞阈值
1
10
30s
80%
结果分析
该实验将本文提出的 FD 算法同传统的经典算法：Epidemic、Spray And Wait、Bubble Rap
进行比较。通过对比这四种算法中所有数据包的平均交付率随时间、副本配额、节点缓存的
变化而评估算法的优劣。
- 7 -
中国科技论文在线
210
图 2 交付率随时间的变化
从图 2 中我们看到四种算法的交付率都随时间的增长而增长，FD 的算法的交付率一直
都高于其他三种算法。Epidemic、Spray And Wait、Bubble Rap 三种算法都是采用的随机丢
包策略，不能有效的降低网络负荷，而 FD 算法丢弃数据包时考虑了数据包的公平性，照顾
了交付能力弱的节点发出的数据包，不但能够缓解拥塞，保持网络畅通，而且使得整体的交215
付率有所提高。
图 3 交付率随副本配额的变化
我们在仿真环境中不断增加源节点发出数据包的副本配额，因为 epidemic 的副本配额
是无上限的，而且 bubble rap 采用的单副本形式传输数据，所以这里我们分别取 epidemic 和220
bubble rap 算法随时间变化的平均交付率作为对比值。在这种情况下每种算法的交付率如图
3 所示。随着副本配额的逐渐增加，网络负载增大，这时可以有效利用网络资源，使性能得
到提升，交付率逐渐提高，但是超过一定额度之后，继续增加副本配额只会使得交付率下降，
这是因为网络中众多源节点普遍提高副本配额时，容易给网络造成很大的压力，导致网络拥
塞。FD 策略是在 Binary Spray And Wait 和 Bubble Rap 算法的基础上提出来的，所以和 Spray 225
And Wait 算法的变化有一定的相似性，但是 FD 具有社会性路由的特点，使其表现出明显的
优势。又因为 FD 采用了多副本的传输方式，所以在一定的副本配额范围内交付率要高于
Bubble Rap。
- 8 -
中国科技论文在线
图 4 交付率随节点缓存的变化 230
DTN 网络中节点缓存是一种宝贵的资源，因此它的大小是影响网络性能的一个重要因
素，我们为仿真场景中的节点设置了不同的缓存大小，运行相同时间之后，四种算法中数据
交付率的变化如上图 4 所示。从图中可以看到随着缓存的增大，Epidemic 算法交付率基本
呈直线上升趋势，Bubble Rap、SW 和 FD 算法增长较为平稳，这说明缓存大小对 Epidemic
算法的影响更为突出。其中 FD 算法表现出良好性能，交付率均比其他算法要高。 235
4 结论
本文首先建立了一种延迟容忍网络模型，该模型引入了社会性并采用多副本的传输机
制，然后在此基础上提出了一种拥塞控制策略：FD（Fair Drop）策略。该策略与其他论文
在这一问题上的研究不同，本文所提拥塞控制的优化目标是公平性，即，采用公平丢弃数据
包的方式缓解拥塞，该策略可以让更多的数据包利用网络资源。最后通过仿真实验表明，该240
策略同其他协议相比，可以有效的缓解网络拥塞，同时提高消息的交付率。
[参考文献] (References)
[1] Pujol J M, Toledo A L, Rodriguez P. Fair routing in delay tolerant networks[C]. IEEE INFOCOM, 2009,
837-845. 245
[2] 陶勇. 容迟容断网络拥塞控制关键技术研究[D]. 北京：国防科学技术大学, 2011.
[3] Soelistijanto B, Howarth M P. Transfer Reliability and Congestion Control Strategies in Opportunistic
Networks: A Survey[J].
[4] Walker B D, Glenn J K, Clancy T C. Analysis of simple counting protocols for delay-tolerant
networks[C].Proceedings of the second ACM workshop on Challenged networks. ACM, 2007: 19-26. 250
[5] Lo S C, Lu C L. A Dynamic Congestion Control based Routing for Delay-Tolerant Networks[C].Fuzzy
Systems and Knowledge Discovery (FSKD), 2012 9th International Conference on. IEEE, 2012: 2047-2051.
[6] Spyropoulos T, Psounis K, Raghavendra C S. Spray and wait: an efficient routing scheme for intermittently
connected mobile networks[C].Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking.
ACM, 2005: 252-259. 255
[7] Li Z, Shen H. Probabilistic routing with multi-copies in delay tolerant networks[C].Distributed Computing
Systems Workshops, 2008. ICDCS'08. 28th International Conference on. IEEE, 2008: 471-476.
