摘 要： 提出一种针对缓存容量受限的容迟移动网络的多复制路由和缓存管理的方法。该方法能充分利用有限的网络资源，实现更高的传送成功率，降低平均发送延迟，同时实现不同重要性报文的服务质量分级。
关键词： 容迟移动网络； 容量受限； 多复制路由

　　当前的Internet体系结构和其中许多协议不能很好地适用于存在高延时路径和频繁分裂的网络。像陆地移动网络、军事无线自组织网络、星际网络及传感器网络等都存在网络断开的问题，这一类的网络被称作为受限网络。容迟网络DTN（Delay Tolerant Network）是一种新型的网络，最早在2003年的国际会议上由FALL K提出[1]。DTN网络通常延迟比较大，网络拓扑结构不断变化，不能用传统的路由方法来解决。所以DTN网络体系结构中采用了基于信息存储转发的端到端覆盖层——捆绑层。捆绑层的重要组成部分之一是保管传递，将信息从一个DTN保管节点可靠地传输到下一个保管节点等候转发，直到遇到目的节点为止[2]。为了维持这个保管传递，每个节点都需要一定的转发缓存来暂存其他节点发送过来的数据，等到合适的时机再传给下个节点。
　　近距离无线社会网络就是一种利用社会中普遍存在的“弱链接”关系的无线自组织网络，它符合DTN网络的特点，并充分利用社会群体的移动特性与短距离无线通信相结合所带来的空间复用能力，提高社会网络的吞吐量，降低社会网络对固定设备的依赖性，增强对不同应用的适应能力。因此，无线社会网络在小型移动传感器网络、手持通信设备的基础上可以实现火灾预警、高危人群身体健康状况监控、广告信息投递等各种类型的社会功能。
　　DTN网络的路由技术是DTN网络研究的重要方向之一。DTN的路由可以分为两类：单播路由[3]和多复制路由。
　　单播路由就是在一个数据报文开始发送后，并不对其本身进行复制，而是不断向下一个节点传递，直到传送到目的节点为止。由于数据报文只有一份，在DTN这种节点随意移动、网络拓扑结构不能保证的网络条件下，难以确保这唯一一份报文能否向正确的方向传输，可能造成数据不能到达或者延迟非常大。
　　多复制路由的优点是采用多条路径传输，有更大的几率以比较低的延迟将报文传送到目的节点，代价是复制出来的报文拷贝大量占用转发节点的转发缓存，如果缓存空间占满导致不能再接收新的转发数据，则结果是得不偿失的。
　　在DTN多复制路由中，常用的方法是路由扩散(Epidemic Routing)[4]。路由扩散是洪泛的极端情况，因为它试图在所有的路径上发送报文。这会产生很大的冗余，但是对节点和网络错误很健壮，如果资源充足，它会选择传输时间最小的路径。
　　源节点复制路由(Source Spay)[5]的提出就是为了控制泛洪的规模，避免太大的冗余。当报文在源节点产生时，除了一个唯一的ID用来表示以外，还在报文头上附上一个复制许可计数器，记录该报文被许可复制的份数N。当N值大于0时，该报文还能被复制到转发节点，N为0时就停止复制。每当这个报文从源节点被复制到一个转发节点时，源节点中的复制许可计数器减一，而转发节点只转发，没有权限对报文进行复制。
1 路由和缓存管理方法的设计和实现
1.1 路由
　　本文采用的路由方法是基于多复制路由的思路。路由扩散方法泛洪规模过大，对节点转发缓存要求太高；而源节点复制路由的复制环节在源节点处，范围有限。本文采用一种能够充分利用网络纵深的复制路由方法——二分法复制，获得比路由扩散或源节点复制路由更好的效果。与源节点复制路由方法类似，报文在源节点产生时，也有一个复制许可计数器，记录该报文被许可复制的份数N。当N值大于0时，该报文还能被复制到转发节点，N为0时就停止复制。当这个报文被复制到目的节点时，发送节点把一半的复制许可交给对方节点，即双方报文中复制许可计数器的值都变成N/2。在节点相遇时，如果对方节点没有该报文并且复制许可计数器的值大于1，则继续二分法复制，直到许可域的值为1。这里N的初始值就用2的整数次幂。二分法复制使复制环节不局限在源节点处，同时又控制了泛洪的规模。
1.2 缓存管理机制
　　缓存管理机制主要是处理缓存已经占满，同时又有新的需要转发的报文到达的情况。
传统的缓存管理一般采用先入先出(FIFO)，在缓存占满的情况下最先到达的报文被后面到来的挤出丢弃；或者是不丢弃报文的策略，只要缓存处于占满的状态就不再接受新的报文。本文采用了随机丢弃报文的策略。
当一个节点的转发缓存已满，又遇到其他结点要传送报文给它时，就随机丢弃转发缓存中的一个报文，接受新传送来的报文。因为一个报文在其源节点的源缓存中总是保留一个备份，所以在转发缓存中的丢弃不会造成该报文的永久丢失。随机丢弃在这种报文被多次复制的路由方法中，比起拒不接受新报文或者先入先丢弃的方法是具有一定优势的。因为从全网络的整体上看，被复制的次数比较多的报文被随机选中并丢弃的概率要大于被复制的次数少的报文。也就意味着原本传送可能性较小、传送难度大的报文被丢弃的概率小，一定程度上保持了公平。
1.3 移动和相遇模型
　　考虑到系统的应用背景是短距离的无线社会网络，个人手持通信设备以及传感器的传输距离有限，参与人数众多，个人的移动性比较随机，所以本文采用随机路点(Random Waypoint)[6]作为系统的移动模型，最为接近现实情况。
2 仿真结果
　　为了评价所提出的路由方法的优劣，本文用C++写了一个仿真过程。由于在该效用路由方法中，底层协议不会影响到本文对路由协议的评价，所以本文把主要精力集中在路由协议的仿真运行上。在仿真路由协议时，假设每个报文的长度是有限制的，节点间的传输带宽是足够充裕的。两个节点在相遇时，有充足的带宽来迅速交换彼此的报文，不会出现报文尚未传输完成就丢失连接的情况。
2.1 仿真参数
　　选取一个矩形区域作为随机路点模型的移动范围，长宽a、b各为3 000 m。节点的移动速度v为5 m/s~15 m/s中服从均匀分布的一个随机值。节点的收发半径r=20 m，数量为30个，转发缓存容量为20条报文。
　　每个节点每隔10 s产生一个报文，总共产生100个报文。其中有10个是高优先级的报文，90个为低优先级的。每个报文的生存时间为500 s。所以整个系统的仿真时间定为1 500 s，保证最后产生的报文也能在系统仿真结束前自然消亡。
2.2 仿真结果分析
　　本文在DTN网络模型中实现了普通的单播路由、路由扩散以及二分法路由，在多播路由的缓存管理上尝试了丢弃最早报文方式、拒绝新报文方式和随机丢弃报文方式。
2.2.1 报文的传输失败率
　　图1反映的是数据包丢失的总数和缓存容量的关系。在单播路由下，由于不涉及到报文的复制，所以缓存容量对于系统性能没有影响，丢失的数据包总数均为321个。路由扩散由于不限制报文的拷贝份数，在早先时间生成的报文会被大量复制，占据缓存空间，这些报文在没有到达目的地之前，阻止了后面生成的报文的复制传输，造成后续的报文难以到达目的地，在生存时间截止后被丢弃。在缓存容量较小的情况下，路由扩散方式丢失的报文数远大于单播路由方式，证明其不适用于节点缓存容量较小的系统。随着缓存容量的增加，路由扩散方式的丢包数大幅下降，最后小于单播路由的丢包数。说明当转发缓存不被轻易占满的情况下，多复制路由的性能会优于单播路由方式。二分法复制则由于考虑到节点转发缓存的容量，限制了报文复制的份数。在复制份数上限为8的情况下，所有报文的丢包数随着转发缓存容量的增加而减小，在转发缓存容量为60时就低于单播路由方式的丢包数，体现出明显的性能优势。尤其是高优先级的报文，丢包数一直稳定在30个以下，小于10%的丢包率，并随着转发缓存容量的增加进一步减小，在缓存容量为200时丢包率小于3%。低优先级的报文在缓存容量为20时丢包率为18.1%，随着缓存容量增加到200，丢包率减小到3%左右，和高优先级的报文相当。这说明在缓存容量足够的情况下，优先级的高低造成的丢弃或保留对于系统已经几乎没有影响，报文的丢失主要是因为路径完全不可达。而在缓存容量较小的情况下，高优先级的报文的丢包率明显小于低优先级的，说明该路由与缓存管理策略对紧急数据的传输有较好的支持。

2.2.2 报文的平均传输延迟
　图2 比较了三种不同的缓存管理策略的平均传输延迟表现。转发缓存容量固定为20，在复制许可份数较小的情况下，三种缓存管理策略的差异不大。拒绝接受新报文方式在复制许可数超过4之后延迟反而增加，说明先前的报文没发送出去时,后面的报文无法被复制、传输，直接增加了这些报文的延迟，所以出现性能下降。当选择两种丢弃方式后，报文的平均传输延迟在复制许可份数为8时获得最低值，而在复制许可份数为16时平均延迟略有增加。说明在转发缓存容量为20时，太多的复制许可份数反而造成部分报文被不必要地大量复制，而有些报文得不到复制机会，反而影响了总的平均延迟。8份复制许可的二分法复制方式是最为合适的。由于随机丢弃方式在总体上丢弃已经被复制较多次数的报文的概率大一些，而被复制次数少的报文被随机选中丢弃的概率小一些，这从一定程度上保证了公平，使那些后来的报文刚开始能多保留一些备份进行传输，所以性能略优于丢弃最早报文方式。

　　图3比较了不同路由方式下的平均传输延迟。如前文所述，单播路由的延迟不随缓存容量的增加而变化。路由扩散方式在缓存容量较小时延迟最大，随着缓存容量增加，延迟显著减小。而二分法复制始终拥有较小的传输延迟，在缓存容量超过80后延迟的减小趋于平稳。复制许可N=4的平均延迟始终高于N=8或16的平均延迟，说明未能充分利用转发缓存。复制许可N=8、缓存小于160时，平均延迟小于N=16的情况，说明当缓存不够大时，太多的复制许可份数反而影响总平均延迟。因此在缓存容量不是非常充裕时，复制许可为8份能够提供最小的传输延迟。

　　最后在N=8的情况下比较高低两种优先级报文的平均延迟。由图4可以看出，本文中针对不同优先级报文的处理方式保证了无论缓存容量充裕与否，高优先级报文的平均延迟都明显小于低优先级报文，在缓存容量较小的情况下，这种优势尤为明显。

　　本文主要对DTN网络的多复制路由方法进行改进，充分利用有限的转发缓存空间来保证传输成功率和延迟时间。使用控制复制份数的二分法复制来进行多复制路由，使用基于复制许可数和报文优先级的随机丢弃方式处理不同报文争抢有限转发缓存的矛盾，获得了更高的传输成功率和更低的平均传输延迟。本文还针对不同优先级报文采用不同的复制路由和缓存管理策略，在略微牺牲低优先级报文传输性能的代价下，使高优先级报文的传输性能得到显著提升。
参考文献
[1]  FALL K. A delay-tolerant network architecture for challenged internets. In Proceedings ACM SIGCOMM，2003，August 2003:25-29.
[2]  FALL K， HONG W， MADDEN S.  Custody transfer for reliable delivery in delay tolerant networks. Technical Report IRB-TR-03-030，Intel Research Berkeley，2003.
[3]  JAIN S, FALL K, PATRA R. Routing in a delay tolerant network. In Proceedings of ACM SIGCOMM,ACM Press, 2004,34:145-158.
[4]  VAHDAT A, BECKER D. Epidemic routing for partially-connected ad hoc networks,” Duke University, Tech. Rep., July 2000.
[5]  THRASYVOULOS SPYROPOULOS K P, RAGHAVENDRA C S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. in WDTN-05, 2005.
[6]  JOHNSON D B, MALTZ D A. Dynamic source routing in ad hoc wireless networks. In Tomasz Imielinski and Hank Korth, editors, Mobile Computing.Kluwer Academic Publishers, 1996. Chapter 5, 353:153-181.