基于博弈论的容迟网络中布雷斯路由悖论研究

赵晨曦，王 杨，许闪闪，孟 丹，赵传信

(安徽师范大学 数学计算机科学学院，安徽 芜湖 241000)

0 引 言

容迟网络(delay tolerant network)是一种自组织网络，不需要在源节点和目的节点之间建立完整的通信路径，利用节点相遇实现网络通信，是无线网络研究领域的一个新兴热门方向。延迟容忍网络架构[1]保证了异步消息在链路中断和传输节点资源有限情况下的可靠传输。其应用涵盖了因特网以外的许多通信网络，如星际网络、乡村网络、战争网络、移动AdHoc网络和无线传感器网络等。人们对容迟网络的研究是希望在不稳定的动态变化情况下，网络可以提供足够品质的服务，对未来网络建设具有重要的研究意义。

在一个交通网络上增加一条路段反而使网络上的旅行时间增加了，而且所有出行者的通行时间都相应增加了，这一附加路段不但没有减少交通延滞，反而降低了整个交通网络的服务水准，这种出力不讨好且与人们直观感受相悖的交通网络现象就是人们所说的布雷斯悖论现象。

文中简要介绍了延迟容忍网络的架构，分析了延迟容忍网络中常用的几种路由选择算法；然后依据博弈论的知识，分析Braess悖论的成因，建立相应模型；最后给出了仿真实验及结果分析。

1 延迟容忍网络的架构

由于主机和路由器的不断移动而出现了“受限网络”[2]，这就对现有的Internet体系结构和协议应用产生了挑战。因为在陆地移动网、军事无线自组织网等网络[3-6]中，由于情况的特殊，经常会出现大的链路延迟、端对端无路由路径、缺少及时的能量补给和足够的存储能力等状况。

为了解决这个问题，可以选择两种方式：一种是在现有的Internet体系结构和协议应用下，提出一些“弥补”措施，例如“链路修正法”(link-repair approaches)和“网络特殊代理法”(network-specific proxies approaches)。前者是试图把网络中有问题的链路转化为可以适应TCP/IP的类似链路，尽力保持互联网端到端的可靠性和命运共享模式，而所有的路由器和端节点要执行IP协议；后者是把那些受限网络当作互联网的边缘，用特殊的代理方式连接互联网和受限网络。但是因为受限网络端到端之间的高延迟，低数据率，易断开，排队时间长，端系统寿命有限等特性，理所当然地想在这种网络上修改、加强协议来进行应用也是很复杂、难适应的；另一种方式就是提出一种新的专用于容迟网络的体系结构，它可以避免上述麻烦，很好地解决问题。

因为目前因特网互联主要还是依靠有线信道，因此TCP/IP协议被普遍应用。但是随着无线互联技术的发展，TCP协议的劣势开始显露，主要还是由于TCP通信需要一段时间往返以建立连接，若传输的延迟超出了通信持续时间，那么应用层就没有数据可发送，其对数据丢失和网络拥塞处理的方式使TCP吞吐量随着往返延迟的增加而减少。所以研究者在应用层和传输层之间插入一个包裹来确保端到端可靠的数据传输服务，这个包裹层可以提供存储转发功能，可以很好地克服网络中断现象[7-8]。

2 延迟容忍网络路由算法

2.1 源路由选择算法

源路由选择算法将一个分布式问题转化为集中式问题，算法中每个节点都保留着所有的全局状态信息，包括网络的拓扑结构和每条链路的状态信息。利用已知信息，在源节点便可计算出全局的可行路径，然后沿此路径，用于通知中间节点前后节点信息的控制报文被发送出去，其中链路状态协议用来在每个节点更新全局状态。因此，源路由选择算法的概念十分简单且易于测试。但是对于小型网络，其开销尚可接受，而对于大型网络，每次为了保持全局信息的准确，就必须频繁地依次刷新，通信开销不小，实际可行性较低。

2.2 分布式路由选择算法

在分布式路由选择中，源节点和目的节点之间的各个中间节点都在进行路径的计算。节点之间交换控制报文，同时每个节点上的状态信息被集中用来进行路径寻找，大部分的分布式路由选择算法都采用距离向量协议(或链路状态协议)以距离向量的形式在每个节点上保持全局状态。由于路径通过分布式的计算得出，因此路由选择的响应时间大大缩短，算法更加易于扩展。网络并行寻找多条路径，进而从中找出可行的一条，大大提高了成功的可能性。大部分现有的分布式路由选择算法都要求每个节点保存全局网络状态信息，并利用此状态逐跳进行路由选择。

因而，分布式路由选择相比源路由选择更能适应容迟网络多变的拓扑结构，但是因为利用了全局状态进行路由选择，所以或多或少也存在源路由算法的问题；而如果不需要任何全局状态的话，则必须传送更多的报文，通信量一样很大。此外，当不同节点上的全局状态不互相关联时，就有可能出现环路。

2.3 距离矢量路由选择算法

在距离矢量路由选择算法(distance vector routing algorithm)中，每个路由器都有一张以其他路由器为索引的向量表，表中包括每个目的地已知的最佳距离和路径。

设节点X的邻接点集合为T{G1,G2,…,Gn}，其中X到Gi的代价为C(X-Gi)，Gi到Y的最小代价为Cmin(Gi-Y)，则节点X到节点Y的最小代价为：

Cmin(X-Y)=min{C(X-Gi)+CLeast(Gi-Y)},

i=1,2,…,n

(1)

2.4 链路状态路由算法

链路状态路由算法(link state routing algorithm)概括起来有4步：发现本节点所有的邻居节点，计算开销；把收集到的交换信息合并为分组，并通知其他路由器；扩散发布链路分组；计算所有路由器的最短路径。这其实就是通常意义上的迪杰斯特拉(Dijkstra’s algorithm)算法[9]。

迪杰斯特拉算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。该算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止，又叫SPF算法。从某个源节点到目的节点的最短路径就是所有到目的节点的路径中具有最小权值的那条。迪杰斯特拉算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表示的方式。

如图1所示，其最短路径计算过程为：从节点A开始(A放入S集合)，相邻节点为B、C，其中A→C最短，C加入S集合；C相邻节点有：B、D、E，而A→C→B=5，比上面A→B=6短，A→C→D=6，A→C→E=7，B加入S集合，B相邻节点有D，而A→C→B→D=10比上一步A→C→D=6长，所以B出S集合，D进入S集；按照这些步骤，最后结果是A→C→D→F=9。

图1 无向图

此算法对网络上的每个节点仅发送路由表中包含自身链路的那部分，克服了距离矢量路由算法收敛慢、容易成环的缺点。

3 布雷斯悖论博弈论分析

3.1 Braess悖论产生原因

Braess悖论现象是由1968年意大利数学家Dietrichi Braess发现并提出的[10]，是交通网络均衡理论的典型案例[11-12]。Braess就满足Wardrop第一出行原则的用户平衡分配问题给出了一个实例，即在一个交通网络上增加一条路段反而使网络上的旅行时间(travel time)增加了，而且使所有出行者的旅行时间都增加了，这一附加路段不但没有减少交通延滞，反而降低了整个交通网络的服务水准(level of service)。

图2 Braess悖论示例

由于非合作网络中的纳什平衡点不在帕累托边界(Pareto boundary)上，Braess悖论现象中出现效益负增长。这种情况下，存在一种非平衡的流量分布，使网络相对于平衡流量分布时某些用户的出行时间缩短，同时其他用户的出行时间也不会增加[13-16]。从博弈论的角度分析，这是一个典型的“囚徒困境”，即每个博弈方都以使其从起点到终点所需的行程时间最小为原则，在选择路径的时候不考虑其选择对其他驾车者的影响。博弈双方都追求个人利益最大化的结果是：每个博弈方的状况恶化，与此同时，使整个系统的效率降低。

依据上述分析，如果在容迟网络路由选择中可能出现布雷斯悖论现象，那么此路由选择方法中就必须出现追求自我利益最大化的选择策略，从而陷入上述的“囚徒困境”。

回顾第2节的延迟容忍网络路由算法可以发现，在链路状态路由算法的运算过程中，因为普遍采用的是Dijkstra算法，每次寻找的是最短路径，因此可能会在一定情况下出现悖论现象。

3.2 Braess悖论对偶模型

要证明Braess悖论的存在，可从其对偶形式入手，证明Braess悖论的对偶形式存在即可。

Braess悖论的对偶形式为：在其他条件不变的前提下，增加车流量,系统总通行时间减少，与预期相反。对应于容迟网络路由算法中，即可理解为在其他条件不变的前提下，增加网络负载权值，不但没有增加路由选择所需的总时间，反而提高了选择过程的效率。

4 仿真实验

4.1 节点仿真

先在Matlab中随机建立容迟网络的路由节点，规定路由节点间的距离、传输速度等权值。容迟网络的拓扑结构采用网络拓扑随机生成算法，程序中的参数包括区域边长、节点个数、网络特征参数等。各参数和作用如表1所示。

表1 仿真程序参数列表

此程序可以随意控制网络参数，生成指定数量的路由节点，每个节点的参数可以显示或者输出到文件。仿真在Intel Pentium Dual-Core 1.86 GHz CPU、内存3 G的计算机上进行。

4.2 算法实现

根据仿真得到的随机节点各项参数，通过输出到文件收集了多组基于不同网络特征参数的数据样本，应用这些数据样本，可以编程来模拟路由算法以进行数据的分析。

分析程序使用Codeblocks 10.05编译运行，gcc版本4.6.1。程序中的参数解释见表2。

表2 程序参数列表

表3是两组运行结果的比较。

表3 运行结果

4.3 结果分析

对于Length=10，NodeNum=30,Scale=10的随机拓扑网络，其运行结果如表4所示。

表4 运行结果

取表4的第一和第二行数据样本，网络总流量128 567<128 628，而总时间116 728>115 964。从实验结果可以得出，网络流量虽然在增加，但并不是严格地呈上升趋势，相反某些相邻点之间呈现了下降趋势。所以悖论的对偶问题成立，悖论现象出现，因而悖论在此也是成立的。

5 结束语

对容迟网络的路由选择算法进行了分析，通过深入研究布雷斯悖论的理论出现原因，找到了可能的出现场景，并通过仿真和程序验证了猜想，得出容迟网络路由中存在布雷斯悖论现象的结论。但是不能忽视的是布雷斯及其对偶形式存在一个严格的假设前提：博弈方在选择路径前完全了解网络信息。这在实际中是不可能实现的。因此，此研究在产生条件、参数影响、分析方法等方面仍有进一步深入探讨的空间。