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

(安徽師范大學 數(shù)學計算機科學學院，安徽 蕪湖 241000)

0 引 言

容遲網(wǎng)絡(delay tolerant network)是一種自組織網(wǎng)絡，不需要在源節(jié)點和目的節(jié)點之間建立完整的通信路徑，利用節(jié)點相遇實現(xiàn)網(wǎng)絡通信，是無線網(wǎng)絡研究領域的一個新興熱門方向。延遲容忍網(wǎng)絡架構[1]保證了異步消息在鏈路中斷和傳輸節(jié)點資源有限情況下的可靠傳輸。其應用涵蓋了因特網(wǎng)以外的許多通信網(wǎng)絡，如星際網(wǎng)絡、鄉(xiāng)村網(wǎng)絡、戰(zhàn)爭網(wǎng)絡、移動AdHoc網(wǎng)絡和無線傳感器網(wǎng)絡等。人們對容遲網(wǎng)絡的研究是希望在不穩(wěn)定的動態(tài)變化情況下，網(wǎng)絡可以提供足夠品質的服務，對未來網(wǎng)絡建設具有重要的研究意義。

在一個交通網(wǎng)絡上增加一條路段反而使網(wǎng)絡上的旅行時間增加了，而且所有出行者的通行時間都相應增加了，這一附加路段不但沒有減少交通延滯，反而降低了整個交通網(wǎng)絡的服務水準，這種出力不討好且與人們直觀感受相悖的交通網(wǎng)絡現(xiàn)象就是人們所說的布雷斯悖論現(xiàn)象。

文中簡要介紹了延遲容忍網(wǎng)絡的架構，分析了延遲容忍網(wǎng)絡中常用的幾種路由選擇算法；然后依據(jù)博弈論的知識，分析Braess悖論的成因，建立相應模型；最后給出了仿真實驗及結果分析。

1 延遲容忍網(wǎng)絡的架構

由于主機和路由器的不斷移動而出現(xiàn)了“受限網(wǎng)絡”[2]，這就對現(xiàn)有的Internet體系結構和協(xié)議應用產(chǎn)生了挑戰(zhàn)。因為在陸地移動網(wǎng)、軍事無線自組織網(wǎng)等網(wǎng)絡[3-6]中，由于情況的特殊，經(jīng)常會出現(xiàn)大的鏈路延遲、端對端無路由路徑、缺少及時的能量補給和足夠的存儲能力等狀況。

為了解決這個問題，可以選擇兩種方式：一種是在現(xiàn)有的Internet體系結構和協(xié)議應用下，提出一些“彌補”措施，例如“鏈路修正法”(link-repair approaches)和“網(wǎng)絡特殊代理法”(network-specific proxies approaches)。前者是試圖把網(wǎng)絡中有問題的鏈路轉化為可以適應TCP/IP的類似鏈路，盡力保持互聯(lián)網(wǎng)端到端的可靠性和命運共享模式，而所有的路由器和端節(jié)點要執(zhí)行IP協(xié)議；后者是把那些受限網(wǎng)絡當作互聯(lián)網(wǎng)的邊緣，用特殊的代理方式連接互聯(lián)網(wǎng)和受限網(wǎng)絡。但是因為受限網(wǎng)絡端到端之間的高延遲，低數(shù)據(jù)率，易斷開，排隊時間長，端系統(tǒng)壽命有限等特性，理所當然地想在這種網(wǎng)絡上修改、加強協(xié)議來進行應用也是很復雜、難適應的；另一種方式就是提出一種新的專用于容遲網(wǎng)絡的體系結構，它可以避免上述麻煩，很好地解決問題。

因為目前因特網(wǎng)互聯(lián)主要還是依靠有線信道，因此TCP/IP協(xié)議被普遍應用。但是隨著無線互聯(lián)技術的發(fā)展，TCP協(xié)議的劣勢開始顯露，主要還是由于TCP通信需要一段時間往返以建立連接，若傳輸?shù)难舆t超出了通信持續(xù)時間，那么應用層就沒有數(shù)據(jù)可發(fā)送，其對數(shù)據(jù)丟失和網(wǎng)絡擁塞處理的方式使TCP吞吐量隨著往返延遲的增加而減少。所以研究者在應用層和傳輸層之間插入一個包裹來確保端到端可靠的數(shù)據(jù)傳輸服務，這個包裹層可以提供存儲轉發(fā)功能，可以很好地克服網(wǎng)絡中斷現(xiàn)象[7-8]。

2 延遲容忍網(wǎng)絡路由算法

2.1 源路由選擇算法

源路由選擇算法將一個分布式問題轉化為集中式問題，算法中每個節(jié)點都保留著所有的全局狀態(tài)信息，包括網(wǎng)絡的拓撲結構和每條鏈路的狀態(tài)信息。利用已知信息，在源節(jié)點便可計算出全局的可行路徑，然后沿此路徑，用于通知中間節(jié)點前后節(jié)點信息的控制報文被發(fā)送出去，其中鏈路狀態(tài)協(xié)議用來在每個節(jié)點更新全局狀態(tài)。因此，源路由選擇算法的概念十分簡單且易于測試。但是對于小型網(wǎng)絡，其開銷尚可接受，而對于大型網(wǎng)絡，每次為了保持全局信息的準確，就必須頻繁地依次刷新，通信開銷不小，實際可行性較低。

2.2 分布式路由選擇算法

在分布式路由選擇中，源節(jié)點和目的節(jié)點之間的各個中間節(jié)點都在進行路徑的計算。節(jié)點之間交換控制報文，同時每個節(jié)點上的狀態(tài)信息被集中用來進行路徑尋找，大部分的分布式路由選擇算法都采用距離向量協(xié)議(或鏈路狀態(tài)協(xié)議)以距離向量的形式在每個節(jié)點上保持全局狀態(tài)。由于路徑通過分布式的計算得出，因此路由選擇的響應時間大大縮短，算法更加易于擴展。網(wǎng)絡并行尋找多條路徑，進而從中找出可行的一條，大大提高了成功的可能性。大部分現(xiàn)有的分布式路由選擇算法都要求每個節(jié)點保存全局網(wǎng)絡狀態(tài)信息，并利用此狀態(tài)逐跳進行路由選擇。

因而，分布式路由選擇相比源路由選擇更能適應容遲網(wǎng)絡多變的拓撲結構，但是因為利用了全局狀態(tài)進行路由選擇，所以或多或少也存在源路由算法的問題；而如果不需要任何全局狀態(tài)的話，則必須傳送更多的報文，通信量一樣很大。此外，當不同節(jié)點上的全局狀態(tài)不互相關聯(lián)時，就有可能出現(xiàn)環(huán)路。

2.3 距離矢量路由選擇算法

在距離矢量路由選擇算法(distance vector routing algorithm)中，每個路由器都有一張以其他路由器為索引的向量表，表中包括每個目的地已知的最佳距離和路徑。

設節(jié)點X的鄰接點集合為T{G1,G2,…,Gn}，其中X到Gi的代價為C(X-Gi)，Gi到Y的最小代價為Cmin(Gi-Y)，則節(jié)點X到節(jié)點Y的最小代價為：

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

i=1,2,…,n

(1)

2.4 鏈路狀態(tài)路由算法

鏈路狀態(tài)路由算法(link state routing algorithm)概括起來有4步：發(fā)現(xiàn)本節(jié)點所有的鄰居節(jié)點，計算開銷；把收集到的交換信息合并為分組，并通知其他路由器；擴散發(fā)布鏈路分組；計算所有路由器的最短路徑。這其實就是通常意義上的迪杰斯特拉(Dijkstra’s algorithm)算法[9]。

迪杰斯特拉算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。該算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止，又叫SPF算法。從某個源節(jié)點到目的節(jié)點的最短路徑就是所有到目的節(jié)點的路徑中具有最小權值的那條。迪杰斯特拉算法一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN,CLOSE表示的方式。

如圖1所示，其最短路徑計算過程為：從節(jié)點A開始(A放入S集合)，相鄰節(jié)點為B、C，其中A→C最短，C加入S集合；C相鄰節(jié)點有：B、D、E，而A→C→B=5，比上面A→B=6短，A→C→D=6，A→C→E=7，B加入S集合，B相鄰節(jié)點有D，而A→C→B→D=10比上一步A→C→D=6長，所以B出S集合，D進入S集；按照這些步驟，最后結果是A→C→D→F=9。

圖1 無向圖

此算法對網(wǎng)絡上的每個節(jié)點僅發(fā)送路由表中包含自身鏈路的那部分，克服了距離矢量路由算法收斂慢、容易成環(huán)的缺點。

3 布雷斯悖論博弈論分析

3.1 Braess悖論產(chǎn)生原因

Braess悖論現(xiàn)象是由1968年意大利數(shù)學家Dietrichi Braess發(fā)現(xiàn)并提出的[10]，是交通網(wǎng)絡均衡理論的典型案例[11-12]。Braess就滿足Wardrop第一出行原則的用戶平衡分配問題給出了一個實例，即在一個交通網(wǎng)絡上增加一條路段反而使網(wǎng)絡上的旅行時間(travel time)增加了，而且使所有出行者的旅行時間都增加了，這一附加路段不但沒有減少交通延滯，反而降低了整個交通網(wǎng)絡的服務水準(level of service)。

圖2 Braess悖論示例

由于非合作網(wǎng)絡中的納什平衡點不在帕累托邊界(Pareto boundary)上，Braess悖論現(xiàn)象中出現(xiàn)效益負增長。這種情況下，存在一種非平衡的流量分布，使網(wǎng)絡相對于平衡流量分布時某些用戶的出行時間縮短，同時其他用戶的出行時間也不會增加[13-16]。從博弈論的角度分析，這是一個典型的“囚徒困境”，即每個博弈方都以使其從起點到終點所需的行程時間最小為原則，在選擇路徑的時候不考慮其選擇對其他駕車者的影響。博弈雙方都追求個人利益最大化的結果是：每個博弈方的狀況惡化，與此同時，使整個系統(tǒng)的效率降低。

依據(jù)上述分析，如果在容遲網(wǎng)絡路由選擇中可能出現(xiàn)布雷斯悖論現(xiàn)象，那么此路由選擇方法中就必須出現(xiàn)追求自我利益最大化的選擇策略，從而陷入上述的“囚徒困境”。

回顧第2節(jié)的延遲容忍網(wǎng)絡路由算法可以發(fā)現(xiàn)，在鏈路狀態(tài)路由算法的運算過程中，因為普遍采用的是Dijkstra算法，每次尋找的是最短路徑，因此可能會在一定情況下出現(xiàn)悖論現(xiàn)象。

3.2 Braess悖論對偶模型

要證明Braess悖論的存在，可從其對偶形式入手，證明Braess悖論的對偶形式存在即可。

Braess悖論的對偶形式為：在其他條件不變的前提下，增加車流量,系統(tǒng)總通行時間減少，與預期相反。對應于容遲網(wǎng)絡路由算法中，即可理解為在其他條件不變的前提下，增加網(wǎng)絡負載權值，不但沒有增加路由選擇所需的總時間，反而提高了選擇過程的效率。

4 仿真實驗

4.1 節(jié)點仿真

先在Matlab中隨機建立容遲網(wǎng)絡的路由節(jié)點，規(guī)定路由節(jié)點間的距離、傳輸速度等權值。容遲網(wǎng)絡的拓撲結構采用網(wǎng)絡拓撲隨機生成算法，程序中的參數(shù)包括區(qū)域邊長、節(jié)點個數(shù)、網(wǎng)絡特征參數(shù)等。各參數(shù)和作用如表1所示。

表1 仿真程序參數(shù)列表

此程序可以隨意控制網(wǎng)絡參數(shù)，生成指定數(shù)量的路由節(jié)點，每個節(jié)點的參數(shù)可以顯示或者輸出到文件。仿真在Intel Pentium Dual-Core 1.86 GHz CPU、內存3 G的計算機上進行。

4.2 算法實現(xiàn)

根據(jù)仿真得到的隨機節(jié)點各項參數(shù)，通過輸出到文件收集了多組基于不同網(wǎng)絡特征參數(shù)的數(shù)據(jù)樣本，應用這些數(shù)據(jù)樣本，可以編程來模擬路由算法以進行數(shù)據(jù)的分析。

分析程序使用Codeblocks 10.05編譯運行，gcc版本4.6.1。程序中的參數(shù)解釋見表2。

表2 程序參數(shù)列表

表3是兩組運行結果的比較。

表3 運行結果

4.3 結果分析

對于Length=10，NodeNum=30,Scale=10的隨機拓撲網(wǎng)絡，其運行結果如表4所示。

表4 運行結果

取表4的第一和第二行數(shù)據(jù)樣本，網(wǎng)絡總流量128 567<128 628，而總時間116 728>115 964。從實驗結果可以得出，網(wǎng)絡流量雖然在增加，但并不是嚴格地呈上升趨勢，相反某些相鄰點之間呈現(xiàn)了下降趨勢。所以悖論的對偶問題成立，悖論現(xiàn)象出現(xiàn)，因而悖論在此也是成立的。

5 結束語

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