基于平均場均衡的Ad hoc網絡路由協議

張旭，錢志鴻，劉影，王雪

(1.吉林大學通信工程學院，吉林長春130012;2.遼寧工程技術大學電子與信息工程學院，遼寧葫蘆島125105)

在當今資訊發達的社會中，無線網絡已經變得越來越重要。近年來眾多無線通信技術中，無線自組織網絡以其快速組網、自主性和互聯性獲得了科研工作者的青睞。該技術的典型應用有戰場通訊，災難重建和搜尋營救操作，與此同時更多的商業應用也已經在開發中。在Ad hoc網絡中，通信是通過多跳無線連接而并沒有固定基礎設施如基站等，因此它是自治的移動用戶集合通過相對帶寬受限的無線鏈路組網。由于節點是移動的，網絡拓撲可能隨時間快速改變且不可預測，物理層、媒質接入層和網絡層是相互依賴相互作用的，因此在一個動態改變的網絡中尋找一條鏈路去轉發數據是很重要的。博弈方法在無線網絡的應用中并不鮮見，主要集中應用于在用戶間相互作用的模型建立以減少自私節點和協作節點。拓撲控制問題被研究建模為一種非合作博弈[1]。Huang[2-3]研究了具有無線通信背景的大規模LQG博弈。文獻[4]介紹了一個基于納什議價博弈的博弈理論框架以解決轉發節點區域預留帶寬的自私節點問題。文獻[5]介紹了一種馬氏跳變大種群隨機多自主體系統的平均場博弈。文獻[6]中提出一種域間路由協同監測激勵策略。文獻[7]介紹了一種基于博弈理論的無線傳感器網絡分布式節能路由算法。文獻[8]提出了一種分布式二級路由協議(distributed two-tier routing，DTTR)。文獻[9]介紹了基于非合作博弈的無線網絡路由機制。考慮到無線網絡的不穩定性、分布性等特點，同時將博弈論應用于無線網絡研究時，博弈模型的收斂性也是需要考慮的一個關鍵問題，因此本文提出一種基于平均場均衡(mean field equilibrium，MFE)的方法，可以適當降低冗余信息產生的系統開銷并提高網絡效率。

1 平均場均衡模型

網絡層的功能包括路由建立和更新以及沿途的數據包轉發。一些問題如網絡中的自私節點，不同路由技術對網絡拓撲改變的收斂，以及不同路由節點行為等，都可以使用博弈論進行分析。

1.1 基本原理

在無線自組織網絡中，節點間的連接是通過數據包或控制包的泛洪建立的。在這2種情況下，泛洪或轉播是傳送數據包至目的節點或在源節點和目的節點間尋找路徑的最可靠技術。圖1顯示了無線自組織網絡中源節點S需要轉發數據給目的節點D，可目的節點在它的傳輸范圍以外。所有位于源節點S無線傳輸范圍內的都是它的鄰居節點。通過簡單泛洪搜尋路由，S將廣播數據包并且這些數據將通過每一個S的鄰居節點和那些接收到這些S的鄰居節點數據包的節點轉發，直到抵達目的節點。如果網絡密度很大，將會存在很多冗余的信息廣播包。

圖1 無線自組織網絡中節點轉發策略Fig.1 Node forwarding strategy in Ad hoc network

這些冗余信息不僅僅使得路由選擇復雜化，同時也會因共享信道的關系而降低網絡整體性能。在一個共享媒質的環境里，大量的數據包開銷增加了網絡時延和碰撞的概率，因此最終導致較低的包投遞率和吞吐量。博弈論的發明提供了沖突和競爭數學推理的基礎。它已經成為一個豐富的理論，強大的數學和計算工具，同時更為直觀。而使用該理論工具作為一個潛在的強大的路由分析工具另外2點原因:

1)路由協議可以被建模為一個網絡和路由之間的博弈;

2)博弈的平衡點可以量化性能度量。

博弈論也廣泛應用于經濟學，社會科學，生物學和工程學科等[10-12]。采用一種博弈理論的包轉發模型在節點數較多的網絡中可以有效降低網絡的泛洪。

1.2 系統模型

通過建立合理有效的模型對節點之間的相互行為進行分析，其中代理的數量假設為無限的，即“平均場”的模式。同時認為每個代理設置解決一個路由轉發問題，但收益依賴于其他代理的行為。模型中描述為演變和代理行為。文中的隨機博弈模型中，代理采取行動更新他們的狀態，而且他們的收益和狀態的轉移可能受其余參與人的狀態影響?？紤]一個擁有m個節點的博弈。一個隨機博弈是一個數組 Γ =(X，A，P，π，β)，定義如下:

1)時間:時間 t是離散的，t∈{0，1，…}。

2)狀態:在t時刻局中人i的狀態為 xi，t∈X，是緊致的。用符號x-i，t表示t時刻除了局中人i以外的其余人的狀態。

3)行為:行為的數量為n，它們分別對應于一個代理可以選擇在任何給定的時間的行動。假設節點行為的結果是二進制的，“轉發”對應的節點獲得一個單位的獎勵，“不轉發”對應的節點是零獎勵。

4)類型:在任何給定時間的代理有一個類型，由一個隨機變量a的值在[0，1]中給出。其中n個元素代表的是n個參數對收益分布的影響。代理的類型是不可觀測的，這些參數之間的代理必須通過學習獲取。在代理中a是獨立同分布的。a群體測度記為 W，其中 W(A)表示概率，a∈A?[0，1]。

5)貼現因子β:貼現因子取值在(0，1)。

6)群體策略:xt為t時刻的一個普通代理狀態隨機變量，均勻地在人群中隨機提取。然后在時間t的群體策略定義為以下的n維概率向量:ft=(E[σ (xt，1)]，E[σ (xt，2)]，…，E[σ (xt，n)])7)收益:單一階段t時刻局中人i的收益為π(x，a，f)，本文認為回報是有條件獨立的，一個代理接收單位收益轉發的概率Q(θ(i)，f(i))，類型是θ和群體策略是f。假設，對于每一個固定的θ和 i，Q(θ(i)，·)是連續的。

8)狀態轉移:根據是否對應于所選擇的臂的收益變量是1或0，局中人的狀態對應的相應變量增加1。更準確地說，讓yi，ni為單位基本向量，對應的行為是轉發或不轉發。因此，如果當前狀態為x，更新到x+yi狀態，如果是轉發的話，反之則為z+ni?，F在可以定義使用策略σ的代理的轉移內核K。假設一個通用的代理的當前類型是θ，狀態是x，群體策略為 f，那么

以上建立了平均場博弈模型，可以假設一個局中人的收益受其余人的經驗分布影響，相同的假設應用于無線自組織網絡中。收益依賴于其余局中人的行為，代理之間動態不同質，每一個時間步其余局中人的有限子集相互作用。上述模型中，局中人通過狀態和收益函數相互作用，這種耦合是相互獨立的。匿名俘獲概念即是通過局中人狀態信息的聚合來相互作用。一個代理的目的是最大化他的收益:

當局中人數目比較大時，假設一個局中人只響應其他局中人的長期平均狀態分布f。則平均場預期的收益為

式中:μ是一個無視策略，僅依賴于xt。

1.3 收斂性分析

定義1 給定類型分布W，回報函數Q，策略σ，平均場均衡為(μ，f)，其中μ∈M是狀態和類型的聯合分布，f為群體策略，滿足以下2個條件:

1)平穩性:對于任何狀態x和任何類型的集A:

2)一致性:對所有的i

第1個條件要求μ在動態狀態，群體策略為f時是穩態分布，代理策略為σ。第2個條件是f為μ完全穩態分布。2個條件一起確保該系統處于平衡狀態。有以下的命題，建立存在的MFE。證明是通過拓撲不動點理論，根據假設，在群體策略中Q是連續的。

命題1 對于任何的策略σ，存在一個MFE(μ，f)。

證明:證明通過一系列引理進行，共分3個步驟:首先，給定的策略和固定的群體策略，產生的代理穩態分布是群體連續的。其次，這表明如果固定該策略和群體策略，并計算新的穩態分布引發的群體策略，初始群體策略的映射是連續的。該證明通過布勞威爾不動點理論完成[13-15]。

引理1 假設Pt(x|θ，f，σ)表示給定的代理狀態的條件分布，其中θ，f和σ是固定的。那么Pt在f中是連續的。

引理2 對于任何策略σ和群體策略f，存在一個唯一的分布Φ(σ，f)滿足條件1。此外，對于固定的σ，Φ(σ，f)在f中是連續的。

證明:當(σ，f)固定，轉移核Pt(·|θ，f，σ)表示一個馬爾科夫鏈狀態空間。由于幾何間隔更新的獨立性，Φ(σ，f)可以顯式的表示為更新間隔:

假設在歐幾里德范數下 fk→f，根據引理1，Pt(x|a，fk，σ)→ Pt(x|a，f，σ)。根據有界收斂性，這表示對于所有的狀態x和博雷爾幾何A，Φ(σ，fk)(x，a)→ Φ(σ，f)(x，a)。因此 Φ(σ，fk)弱收斂于Φ(σ，f)。

引理3 Fσ是連續的。

證明:在歐幾里德范數下序列fk→f，根據引理2，有Φ(σ，fk)→ Φ(σ，f)。因為X是可分離的，根據Skorokhod定理意味著擁有隨機變量(xk，ak)和相應的策略Φ(σ，fk)，以及一個隨機變量(x，a)和相應的策略Φ(σ，f)使得(xk，ak)→ (x，a)。由于xk在一個離散空間，這表示存在一個ε，對于所有的k＞ε，xk=x。因此對于任何的 i，σ(xk，i)→ σ(x，i)。根據有界收斂定理可以得到:

由于Fσ是連續的并且映射自身一個緊致集，使用布勞威爾定理，存在一個不動點f*滿足Fσ(f*)=f*。因此可以證明(σ，f*)可同時滿足條件1和2。考慮M總的全變差距離度量dTV，使用以下dTV的等價參數。

定義2 總的全變差距離有以下的等價定義:

1)讓 μ1，μ2∈M 是任意 2個測度，μ 是相對于μ1和 μ2絕對連續的任意測度。假設 ξ1，ξ2是 μ 的Radon-Nikodym導數，則:

2)F為所有博雷爾可測子集，則:

3)以 Ω(ξ1，ξ2)表示 2 個隨機向量(x1，a1)和(x2，a2)的所有聯合概率測度使得 k=1，2時，(xk，ak)的邊緣分布為μk，則:

這里的K已經在式(1)定義過。注意到如果μ*是映射 Tσ 的不動點，那么 μ*和f*=p(σ，μ*)是一個MFE。相反地，在任何MFE(μ，f)中，μ必須是Tσ的不動點，f=p(σ，μ)被唯一地確定。因此給定一個策略σ，唯一的MFE存在當且僅當映射Tσ存在一個唯一的不動點。其充分條件為Tσ是一個關于總的全變差距離度量的收縮映射。這種條件也表示如果初始化系統為一個任意的初始分布μ∈M，在映射Tσ下考慮系統的演化，最終將收斂至一個MFE。

1.4 MFEA 算法

本文提出的平均場均衡的無線自組織網絡AODV路由算法(mean field equilibrium AODV，MFEA)是基于按需平面距離矢量路由協議(Ad hoc on-demand distance vector routing，AODV)。在 AODV協議中，當源節點有數據要發送時，源節點需要廣播一個路由請求包，當中包含了最新節點的序列號。鄰居節點同樣廣播此分組，直到達到目的節點或者到達含有最新路由的中間節點為止。在節點轉發請求包的過程中，記錄經過的上游節點的ID，建立一條從源節點到目的節點的反向路由。AODV路由協議的帶寬利用率高，并且是應用于變化的網絡拓撲，但是由于在Ad hoc網絡中節點移動頻繁，對AODV路由協議路由表的維護較困難、可靠性低，而且部分節點的能量消耗過快，也會造成路由中斷。

在AODV協議中，信息可周期性通過節點廣播并用于鏈路監測，當節點M接收到來自節點N的信息，M意識到節點N在他的無線傳輸范圍內并且是它的鄰居節點。相反的，如果不能正確接收到信息則表明這是一個無效的鏈路。如果采用MFEA算法用于轉發AODV路由協議，MFEA算法在源節點在發送廣播分組的過程中，中間轉發節點根據周圍鄰居節點的行為信息，通過計算出收益轉發概率，進而決定是否作為中間轉移節點進行數據分組轉發，并且通過推算最大目的效益以及函數的迭代，更新中間節點的狀態信息，最終到達目的節點，同時形成反向的路由路徑。圖2介紹了MFEA的系統流程。

算法描述:

1)當一個源節點S要尋找到目的節點D的路徑時，首先要確定源節點S的當前時刻的狀態，以及其余節點的狀態信息，最開始網絡上的節點是隨機

給定任何策略σ，推導出MFE(μ，f)存在的充分條件，并且MFE收斂?？紤]映射Tσ:分布的，根據前向分組格式{源地址，目的地址，序列號，跳數，行為，節點1，…節點N}初始化分組，執行2)。

2)當數據分組傳送到下一個節點時，首先是判斷為目的節點還是中間節點。如果是中間節點，根據周圍節點的行為信息以及當前節點的類型θ，計算出節點的收益轉移概率Q(θ(i)，f(i))，確定是否作為中間節點，同時根據轉移概率，通過式(2)計算出最大目的收益，用值迭代函數計算均衡，使用新策略尋找下一個分布，最后計算誤差及狀態的累積分布，并將舊狀態更新為新狀態，重復執行2)。如果當前節點沒有到下一跳的路由信息，則重新選擇上游節點，重新執行2)。到達目的節點后，執行3)。

3)當分組到達目的節點后，根據后向分組格式{源地址，目的地址，序列號，跳數，行為，類型，轉移概率，節點1，..節點 N}更新數據分組格式。當分組到達目的節點后，更新周圍路由信息的同時，全局更新路徑上所有的鏈路信息，執行4)。

4)沿著獲得的反向路徑信息發送數據分組，反向路徑上的中間節點根據行為信息以及收益轉移概率轉移數據，重復執行4)直至到達源節點S。

5)源節點根據返回信息更新原路由信息。

圖2 MFEA流程圖Fig.2 MFEA flow diagram

2 仿真結果與分析

前面介紹了博弈轉發和納什平均場均衡，根據給定的狀態計算最優策略，下一個狀態的計算主要根據公式遞歸求出。為了證明該方法對整體網絡性能提升的影響，在網絡模擬器NS-2中進行一系列試驗。在模擬試驗中，仿真參數見表1所示。

表1 仿真參數Table 1 Parameters for simulation

下面將分別對不同網絡環境下的算法性能進行分析。無線自組織網絡是一個動態的網絡，首先仿真環境假設在不同的節點移動速度下進行，節點的移動速度設定為10 m/s，2種路由協議分別根據端到端的時延、分組投遞率和系統歸一化開銷3種性能指標進行分析。

把網絡建模為一個無向圖G=(V，E)，這里V代表節點集合，E代表連接節點之間的鏈路集合。每個節點都有一個唯一的識別以便于路由協議可以識別他。

端到端時延:由于網絡中鏈路可能被損壞以及節點隨時的移動性，任意鏈路e=(m，n)∈E都會存在相對應的時延D(e)，鏈路的信道時延包括無線傳播時延、隊列時延及協議出路時間等。任意2個節點m和n之間的路徑設定為P(m，n)=(m，e(m，x)，x，e(x，y)，y，… e(z，n)，n)?？梢岳斫鉃槿我?個節點之間的路徑就是組成他們之間鏈路的所有可能節點的集合。一般來說，P(i，j)=P{P0，P1，…，Pn}，此時的Pi代表節點m和n之間的路徑選擇。延時定義如下:

分組數據包投遞率:目的端接收到的數據包數目與網絡中實際發送數據包數目的比值，這個比率測量了發現路徑的效率。假設發送了100個數據包給目的節點，最后接收到了60個數據包，那么網絡中的數據包投遞率即為60%，該度量反映了發送數據的成功率。

歸一化開銷:每一個數據包成功被目的節點接收時候所需要的路由包數目。這個性能反映了網絡的擁塞程度以及節點的效率，開銷較大的協議擁塞的概率相對大一些，并且會延遲隊列中數據包的發送。

2.1 端到端時延

在節點數目由100～400變化的仿真實驗中，對協議的3種性能進行了分析。圖3比較了在不同節點數目情況下AODV路由協議和MFEA協議的平均端到端時延，可以看出MFEA方法中對于節點數目增加下的影響并不大，甚至在節點數目少的時候，AODV甚至延時低于MFEA協議可達0.05 s。不過當節點數目增加到150以上的時候，AODV的時延隨著節點數目的增加顯著增加。

這是因為在節點數目增加的情況下，網絡中的變化復雜起來，路由的可靠性不能保障，因此AODV協議的時延增加較快;而MFEA由于采取了均衡的方法，在數據包轉發的時候可以有效的進行轉發，不受節點數目增多所引起的網絡拓撲變化加快的影響，因此網絡的延時并沒有劇烈的變化，在節點數量為400時，MFEA算法的時延較AODV算法有將近0.2 s的提高，可見在大規模的網絡中更加實用。

圖3 MFEA流程圖Fig.3 MFEA flow diagram

2.2 分組數據包投遞率

圖4為2種協議下的數據包投遞率的性能比較。

圖4 不同節點數目下包投遞率比較Fig.4 Packet delivery ratio vs.number of nodes

從圖中可以看出，MFEA方法在節點數目較少的時候投遞率性能與AODV相似，投遞率在85%～90%左右。隨著節點數目增加，MFEA協議性能明顯優于正常的AODV協議，在節點數目較高的時候這種優勢尤其顯著，最高可達8%。這是因為網絡規模較大的時候，AODV在拓撲變化頻繁的網絡下不能及時選擇適當的路徑以傳播數據，同時在MAC層產生大量的數據碰撞也影響了整體的數據包投遞率，而MFEA協議采用了均衡的方法，更能有效地適應于變化的網絡拓撲。

2.3 歸一化開銷

從圖5中可以看出當節點數目在100～400，MFEA方法的路由協議的歸一化系統開銷均低于AODV協議，最大可達10。這是因為AODV在這種情況下需要不停的尋找新的可用路徑，從而產生大量的泛洪控制包，因此系統開銷也會增加很多。而MFEA算法是一種僅需要長期狀態平均的方法，它可以增加節點轉發請求包概率，同時也可以減少因為網絡拓撲變化帶來的鏈路斷開問題，降低了系統的開銷性能。

圖5 不同節點數目下歸一化開銷比較Fig.5 Normalized overhead vs.number of nodes

3 結束語

本文介紹了一種基于平均場均衡的無線自組織網絡路由協議，該方法對無線網絡路由中的轉發泛洪信息包求取平衡狀態，最終達到減少冗余信息包，降低系統開銷的目的。在節點數目100～400進行的仿真結果表明，本方法能有效地減少網絡平均端到端時延，系統開銷，同時也能增加包投遞率，因此延長了網絡的使用時間，從而提高了網絡效率。

[1]EIDENBENZ S，KUMAR V S，ZUST S.Equilibria in topology control games for ad hoc networks[J].Mobile Networks and Applications，2006，11(2):143-159.

[2]HUANG M，MALHAM＇E P R，CAINES P E.Nash certainty equivalence in large population stochastic dynamic games:connections with the physics of interacting particle systems[C]//Proceedings 45th IEEE Conference on Decision and Control.San Diego，USA，2006:4921-4926.

[3]HUANG M，CAINES P E，MALHAM＇E R P.Large population costcoupled LQG problems with nonuniform agents:individual-mass behavior and decentralized ε-Nash equilibria[J].IEEE Trans Autom Control，2007，52(9):1560-1571.

[4]LU Bin，POOCH U W.A game theoretic framework for bandwidth reservation in mobile ad hoc networks[C]//Proceedings of the First International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks(QSHINE’04).Dallas，USA，2004:234-241.

[5]王炳昌，張紀峰.馬氏跳變大種群隨機多自主體系統的平均場博弈[C]//Proceedings of the 29th Chinese Control Conference.Beijing，China，2010.WANG Bingchang，ZHANG Jifeng.Mean field games for large population stochastic multi-agent systems with Markov jumps[C]//Proceedings of the 29th Chinese Control Conference.Beijing，China，2010.

[6]郭毅，王振興，程東年.基于博弈的域間路由協同監測激勵策略[J].中國科學:信息科學，2012，42(7):803-814.GUO Yi，WANG Zhenxing，CHENG Dongnian.A game-theory-based incentive strategy for inter-domain routing cooperative monitoring[J].Scientia Sinica Informationis，2012，42(7):803-814.

[7]楊寧，田輝，黃平，等.基于博弈理論的無線傳感器網絡分布式節能路由算法[J].電子與信息學報，2008，30(5):1230-1233.YANG Ning，TIAN Hui，HUANG Ping，et al.Distributed energy-economical routing algorithm based on game-theory for WSN[J].Journal of Electronics＆ Information Technology，2008，30(5):1230-1233.

[8]胡靜，沈連豐.基于博弈論的無線傳感器網絡分簇路由協議[J].東南大學學報，2010，40(3):441-446.HU Jing，SHEN Lianfeng.Clustering routing protocol of wireless sensor networks based on game theory[J].Journal of Southeast University，2010，40(3):441-446.

[9]汪洋，林闖，李泉林，等.基于非合作博弈的無線網絡路由機制研究[J].計算機學報，2009，32(1):54-68.WANG Yang，LIN Chuang，LI Quanlin，et al.Non-cooperative game based research on routing schemes for wireless networks[J].Chinese Journal of Computers，2009，32(1):54-68.

[10]AUMANN R J.Handbook of game theory with economic applications[M].Amsterdam:Elsevier，1994.

[11]OSBORNE M J，RUBINSTEIN A.A course in game theory[M].Cambridge:MIT press，1994.

[12]GIBBONS R.Game theory for applied economists[M].Princeton:Princeton University Press，1992.

[13]ADLAKHA S，JOHARI R.Mean field equilibrium in dynamic games with complementarities[C]//2010 49th IEEE Conference on Decision and Control(CDC).Atlanta，USA，2010:6633-6638.

[14]WEINTRAUB G Y，BENKARD C L，Van ROY B.Oblivious equilibrium:a mean field approximation for large-scale dynamic games[C]//Neural Information Processing Systems.Vancouver，Canada，2005.

[15]IYER K，JOHARI R，SUNDARARAJAN M.Mean field equilibria of dynamic auctions with learning[J].ACM SIGecom Exchanges，2011，10(3):10-14.