基于博弈論的容遲網(wǎng)絡(luò)中布雷斯路由悖論研究

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

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

0 引 言

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

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

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

1 延遲容忍網(wǎng)絡(luò)的架構(gòu)

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

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

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

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

2.1 源路由選擇算法

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

2.2 分布式路由選擇算法

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

因而，分布式路由選擇相比源路由選擇更能適應(yīng)容遲網(wǎng)絡(luò)多變的拓?fù)浣Y(jié)構(gòu)，但是因?yàn)槔昧巳譅顟B(tài)進(jìn)行路由選擇，所以或多或少也存在源路由算法的問題；而如果不需要任何全局狀態(tài)的話，則必須傳送更多的報(bào)文，通信量一樣很大。此外，當(dāng)不同節(jié)點(diǎn)上的全局狀態(tài)不互相關(guān)聯(lián)時(shí)，就有可能出現(xiàn)環(huán)路。

2.3 距離矢量路由選擇算法

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

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

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é)點(diǎn)所有的鄰居節(jié)點(diǎn)，計(jì)算開銷；把收集到的交換信息合并為分組，并通知其他路由器；擴(kuò)散發(fā)布鏈路分組；計(jì)算所有路由器的最短路徑。這其實(shí)就是通常意義上的迪杰斯特拉(Dijkstra’s algorithm)算法[9]。

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

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

圖1 無向圖

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

3 布雷斯悖論博弈論分析

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

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

圖2 Braess悖論示例

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

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

回顧第2節(jié)的延遲容忍網(wǎng)絡(luò)路由算法可以發(fā)現(xiàn)，在鏈路狀態(tài)路由算法的運(yùn)算過程中，因?yàn)槠毡椴捎玫氖荄ijkstra算法，每次尋找的是最短路徑，因此可能會在一定情況下出現(xiàn)悖論現(xiàn)象。

3.2 Braess悖論對偶模型

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

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

4 仿真實(shí)驗(yàn)

4.1 節(jié)點(diǎn)仿真

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

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

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

4.2 算法實(shí)現(xiàn)

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

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

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

表3是兩組運(yùn)行結(jié)果的比較。

表3 運(yùn)行結(jié)果

4.3 結(jié)果分析

對于Length=10，NodeNum=30,Scale=10的隨機(jī)拓?fù)渚W(wǎng)絡(luò)，其運(yùn)行結(jié)果如表4所示。

表4 運(yùn)行結(jié)果

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

5 結(jié)束語

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