映射－编码－分发构架在DTN中的应用*

钱景辉，谢开源

（南京工业大学，江苏 南京 211816）

0 引言

机会网络是延迟容忍网络（delay tolerant networks，DTN）中的一个重要的分支［1］，在DTN中通信时间是随机而且未知的，几个典型的应用如SMANETs（sparse mobile Ad-Hoc networks），ZebraNet［2］，UWSNs（underwater sensor networks）［3］，PSNs（pocket switched networks）［4］等。它们在无线范围限制下可能并不存在一条终端到终端的路径，在这样的网络环境下路由变得很困难，而当今流行的无线通信机制在这些网络中无法确保网络的连接。现有方案旨在解决特定的机会网络环境下的路由问题。

本文提出一种新的映射—编码—分发（MCR）机会网络构架，将机会网络传输分成上层网络与下层网络来简化移动模型，并将网络编码引入机会网络之中，保持网络负载基本不变的情况下可以大幅提高网络传输效率;同时，整合网络传输算法，在缺乏网络全局拓扑结构和全局信息的情况下能够依据带宽、存储等限制有效传输信息。

1 相关理论

本文的工作同时涉及机会网络传输构架、网络编码以及机会网络传输。

1．1 机会传输

根据机会网络传输所使用的机制，可以将网络传输分为两大类:基于复制分发［5～7］和基于编码［8］。

基于复制分发的方案在已有的方案中应用非常广泛。它的基本思路是将多个可识别的数据副本注入网络之中，然后依靠节点的移动将数据传输至目的地。若信息成功传输，目标至少需要收到一份数据副本。在网络非常大的情况下，基于复制的方案可以获得较好的网络延迟特性，然而这些方案的主要不足便是造成数据阻塞。当网络资源有限的时候（比如:缓存、网络带宽），基于复制分发的方案会明显地降低性能（比如传输率）。

基于编码的方案其基本思路是将单个数据格式化成k个子数据包进行传输。与基于复制分发的方案不同的是，当目标收集到k+ε个子数据包时便可以重建原始信息。在网络极其差的情况下，基于编码的方案比基于复制分发的方案更加健全。然而，当网络连接非常好时，基于编码的方案表现并不尽人意，这主要是收集附加的子数据包造成的。

然而，机会网络中成功的路由技术必须同时考虑到性能与可靠性。一个有效的路由方案需要同时适应最差与最好延迟性能情况。

1．2 网络编码

当数据包提升了节点中组的级别时，认为节点收到了一个新数据包。数据传输算法中，会根据一些参数在决定哪些包需要被发送，哪些包需要被丢弃。在缓存有限的情况下，需要讨论怎样才能有效地进行网络编码和高效率的解码。在MCR构架中本文提出了一种维护算法，这将有助于减少重复编码信息，在移除旧信息的同时仍然具有很高的可解码性。

1．3 传输机制

网络传输中，本文使用一种考虑资源分配的传输算法—RAPID（resource allocation protocolforintentional DTN）［7］。

算法考虑了资源的限制、路由方案以及移动特性等。许多算法只考虑了节点存储的限制，然而对传输带宽却没有限制，比如:PRoPHET［6］等。当网络通信传输时所传输数据允许比节点存储的数据还要多时，上述这种情况才可能发生。然而在目前存储比较便宜且能源充足的情况下这种情况并不常见。数据显示高比特率传输将比能源和存储贵得多。

在每个机会传递时，算法将路由环境解释为每个数据包的效用参数并不断通过控制频道（control channel）来同步全局网络状态的局部视图。算法通过内置的控制频道使用小部分传输带宽来交换节点之间的网络状态，如数据包副本的位置数量、过往的平均传输量等附加元数据（metadata）。虽然这些信息是有延迟的和不准确的，但这些信息在传输中对性能的提高却起到了非常重要的作用。

2 MCR构架

2．1 概 述

本文采用了一种新的构架，将网络层分为上下两层。上层主要负责选取最优路径，而下层则专注于机会传输。

MCR构架相对于单纯的编码和复制分发策略优势在于:

1）整合编码与分发，集合了编码低丢包率和复制分发策略对网络资源的控制的特点;

2）对于上层网络是透明的，避免了纯粹的机会传输所造成的资源浪费和性能下降;

3）在网络拓扑结构改变时，MCR只需要调整对应的部分，而不需要对整个构架进行重新设计。

MCR构架主要作用在以下几方面:1）选择上层网络基站构成最优传输路径;2）将上层网络路径映射到一条或多条物理传输路径上;3）整合网络编码与机会传输，依据物理传输路径的带宽、容量等限制配合编码将数据包以最优化的方式传递给目标节点。MCR构架如图1所示。

图1 MCR构架Fig 1 MCR framework

2．2 上层网络:路径选择与映射

在上层网络中由于不需要考虑丢包率，算法可以对网络状态有很好的认识。在以下理论中，设区域内存在零散的与广域网相通的固定基站。这些基站是互相连通的，可以通过广域网无限制地互相传递信息。为了区别于现有蜂窝网络，区域内所有基站并不能将整个区域覆盖，相反只能覆盖很小一部分的区域。

如图2，有两块区域P1和P2，A，B，C，D为与广域网相连的固定基站，a，b，c，d，e为移动节点。在某一时刻，假设a，b，c在P1区域内活动，d，e在P2区域内活动。若a想要传递信息给d，上层网络首先获取到d的路径，在本例中最优路径为a→B→C→d。然后算法将路径映射到下层网络中，并使用机会传输将信息编码传送至目标（节点a和基站B之间可能不存在完整的路径，机会传输便利用a和B之间的其他移动节点，这里为b，将信息编码后传递过去）。

图2 上层信息传输Fig 2 Upper layer information transmission

上层网络的作用在于:

1）选择一条只包含途经的固定基站的从源节点到目标节点的最优路径。

2）将路径映射到下层网络以便下层网络能有效地执行机会传输。

上层网络的路径选择能够大大地简化机会传输时的移动模型，并提高传输效率。例如:社交模型中，人们会在不同的子区域内停留聚集，整个移动模型十分复杂。在本文中，社交模型可以按照聚集场所划分为若干个子区域，而子区域中便可以使用简单得多的移动模型替代原有模型。信息在子区域内通过机会传输传送至基站;基站通过广域网与目标区域的基站通信;目标基站再将信息再次通过机会传输在目标子区域内传递，直到达到目标。

2．3 下层网络:网络编码

在下层网络中，为了能减少丢包率，首先将信息进行编码。

设V为网络中的节点数，S为数据源节点数，S⊆V，m=|S|。设每个节点v∈V在物理层有邻居节点N（v），设xi是源节点si（i=1，…，m）产生的信息向量，每个向量值都在限定的域F2k中。为了使编码更具效率，这里设域为F28，这样所涉及的加法和乘法可以使用xor和2个255字节的查找表来解决。每一个信息向量xi都与一个系数相关，此处简记做ei。设M=|xi|为xi中所包含的信息数，信息向量总是与编码向量同时发送出。节点v在矩阵Gv中保存了接收到的信息向量和解码向量，新接收到的向量会被添加到矩阵中。对于节点中已经存在的信息则不会再次添加进去。矩阵Gv通过高斯消去法可以持续的减少矩阵的阶数，当矩阵存在一行为（ei，xi）的时候节点便可以解码出原信息xi。因此，要解码源信息，至少需要m个独立的信息。

2．4 下层网络:机会传输

本文中使用的机会传输算法为RAPID，它基于效用的机制来解决资源分配的问题。数据包将被复制分发直到达到目标。算法的关键在于在给定带宽和存储下优化数据包的分发。假设路由需要实现最小平均延迟，设Ui为发送数据包i的理想时间的负值。设δUi为发送数据包i时Ui的增加量，si为i的大小。RAPID会分发缓存中δUi/si最高的数据包，换言之，算法将发送最小效用的数据包。RAPID在分发中同样考虑到了存储的限制，若节点耗尽了所有存储容量，则最低效用的数据包将会被删除。然而，源节点在收到通知前不会删除其自己的消息。

本文前面讲到，节点的信息传递效率将从全局系统状态信息中获益。为实现这个目标，RAPID利用少量的带宽散布全局系统状态信息。其使用内置的控制频道在每次机会传输时交换数据包信息和包含过去所有交换记录的元数据信息。

RAPID在相遇节点时交换以下信息:

1）过去的平均机会传输次数;

2）节点相遇期望时间;

3）过去所发送的全部消息列表;

4）对于每个自己的数据包，期望估计时间将根据目前缓存中的状态来计算;

5）其他节点在上次相遇后改变的信息。

当算法使用控制频道时，对于全局系统状态也只是一个概览。这些状态在节点运动时可能改变或延迟，即使这些消息不是很精确，但依旧可以给算法带来性能的提高，而元数据本身的负载却很少。

2．5 旧信息维护

当节点解码信息后，整个矩阵中的信息对于该节点就不再有用了，但是对于其他节点，这些信息可能依旧会在解码时使用到。节点需要保存矩阵中的信息，然而却不需要保存整个矩阵。在存储容量有限的情况下，节点可以减少已经解码的矩阵的阶数。例如:可以将第rn－1行和第rn行线性相加得到一个新行rn－1。这种方式不会减少解码的几率，只要重要的向量至少存在一个，那么，新节点将仍然可以解码出所有的数据。

3 仿真与评估

在上文中已经提到，MCR构架将整个DTN划分成若干个子区域，而每个子区域内的节点移动模型将比整个区域的模型简单得多。如何在上层网络中选取合适的最优路径已经不属于DTN机会传输的范畴，下文的仿真将针对机会网络来进行。

在网络中，网络节点之间的相遇是未知的。本文将MCR 与 RAPID，PRoPHET，Spray and Wait，Epidemic 进行了对比，同时展示了网络编码对数据的影响。在所有仿真中，都使用了RAPID的内置控制频道来传输元数据。

Epidemic随机地向节点分发数据;Spray and Wait限制了分发数L，其中，L由网络节点数计算而得［5］，在仿真中使用了binary Spray and Wait，同时设L为12;在 PRoPHET中Pinit=0．75，β =0．25，γ =0．98;MCR（1）中没有冗余，即源节点产生的线性和个数m与数据包个数n相同，MCR（2）中有20%的冗余编码，即m=1．2n;全局消息 TTL（time to live）为 1800 s。

仿真实验证明，MCR的表现比 RAPID，PRoPHET，Spray and Wait和Epidemic都要好。当消息产生速率相同时，Epidemic的网络负载已经接近MCR的2倍。

从表1可以看出:MCR在传输率、平均延迟、平均缓冲时间等方面与其他算法比较都有着很大优势。算法的传输比率=传输成功数/消息数，而MCR由于使用了网络编码，因此，在解码过程中会有一些消息无法解码。在数据中看出:虽然有消息无法被解出，但传输比率依旧比其他算法要高。

表1 各算法性能Tab 1 Performances of different algorithms

图3为元数据在带宽中占有不同百分比的情况下对传输性能的影响。数据显示，随着限制的放宽，传输性能也在不断提高。当对元数据不加限制时，算法可以得到最佳的性能。在有元数据的情况下MCR可以得到约20%的提升。

图4中为互补累计分布函数（CCDF）曲线，显示的是网络编码对传输性能的影响。从图中看出在TTL为1800时，没有网络编码的情况下的丢包率约为25%，而在无冗余网络编码参与时丢包率约为29%。本文对原始数据经行编码时引入20%的冗余，即矩阵Gv大小增加20%，表1与图4中MCR（1）为没有冗余时的数据，MCR（2）为添加冗余后的数据。从对比看出:虽然网络负载与平均延迟有所增加（网络负载增加3．6%，平均延迟增加56 s），但在TTL不变的情况下丢包率已经降低到21%，比无网络编码时高出4%。

综上，MCR在没有冗余数据时，无编码MCR比有编码MCR性能要好，而当引入少量冗余后有编码MCR的表现比无编码MCR要好。在现实环境中，增加少量的网络带宽来换取更少的丢包率是完全可行的。

图3 控制频道对性能的影响Fig 3 Effect of control channel on character

4 结论

机会网络是一个新兴的研究领域。在机会网络中传输有别于传统的网络，在该网络中可能并不存在一条完整的传输路径，因此，节点的移动在传输中起到了至关重要的作用。目前，已有的一些机会网络传输策略仅在特定的环境下有很好的效果，而在多变的现实环境中并不适用。本文提出了一种新的机会传输构架，它简化了移动模型，完善了对网络资源的控制，在整合现有策略的基础上能够适应多变的现实环境并保持很高的传输效率。

图4 网络编码对性能的影响Fig 4 Effect of network coding on character

本文提出的构架主要着眼于离散无线网络，例如:车载网络、无线手持网络、无线传感器网络等。在一些网络不发达的区域或者军事限制区域中，有望得到很好的应用。

［1］ Xiong Y P，Sun L M，Niu J W，et al．Opportunistic networks［J］．Journal of Software，2009，20（1）:124 －137．

［2］ Juang P，Oki H，Wang Y，et al．Energy-efficient computing for wildlife tracking:Design tradeoffs and early experiences with ZebraNet［C］∥Proc of the 10th Int’l Conf on Architectural Support for Programming Languages and Operating Systems，New York:ACM，2002:96 －107．

［3］ Cui J H，Kong J，Gerla M，et al．Challenges:Building scalable mobile underwater wireless sensor networks for aquatic applications［J］．IEEE Network，Special Issue on Wireless Sensor Networking，2006，20（3）:12 －18．

［4］ Chaintreau A，Hui P，Crowcroft J，et al．Impact of human mobility on the design of opportunistic forwarding algorithms［J］IEEE Trans on Mobile Computing，2007，6（6）:606 －620．

［5］ Spyropoulos T，Psounis K，Raghavendra C S．Spray and wait:An efficient routing scheme for intermittently connected mobile network-s［C］∥Proc of 2005 ACM SIGCOMM，2007，Workshop on Delay-Tolerant Networking，Philadelphia:ACM，2005:252 －259．

［6］ Lindgren A，Doria A，Schel’en O．Probabilistic routing in intermittently connected networks［C］∥Proc of SAPIR Workshop，2004:239－254．

［7］ Balasubramanian A，Levine B N，Venkataramani A．DTN routing as a resource allocation problem［C］∥SIGCOMM 2007，2007:373－384．

［8］ Wang Y，Jain S，Martonosi M，et al．Erasure-Coding based routing for opportunistic networks［C］∥Proc of 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking，Philadelphia:ACM，2005:229-236．

［9］ Widmer J，Boudec J L．Network coding for efficient communication in extreme networks［C］∥Proc of 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking，Philadelphia:ACM，2005:284－291．