基于博弈論的容遲網絡中布雷斯路由悖論研究

趙晨曦，王 楊，許閃閃，孟 丹，趙傳信

(安徽師范大學 數學計算機科學學院，安徽 蕪湖 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 結束語

對容遲網絡的路由選擇算法進行了分析，通過深入研究布雷斯悖論的理論出現原因，找到了可能的出現場景，并通過仿真和程序驗證了猜想，得出容遲網絡路由中存在布雷斯悖論現象的結論。但是不能忽視的是布雷斯及其對偶形式存在一個嚴格的假設前提：博弈方在選擇路徑前完全了解網絡信息。這在實際中是不可能實現的。因此，此研究在產生條件、參數影響、分析方法等方面仍有進一步深入探討的空間。