基于平均場均衡的Ad hoc網(wǎng)絡(luò)路由協(xié)議

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

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

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

1 平均場均衡模型

網(wǎng)絡(luò)層的功能包括路由建立和更新以及沿途的數(shù)據(jù)包轉(zhuǎn)發(fā)。一些問題如網(wǎng)絡(luò)中的自私節(jié)點(diǎn)，不同路由技術(shù)對網(wǎng)絡(luò)拓?fù)涓淖兊氖諗?，以及不同路由?jié)點(diǎn)行為等，都可以使用博弈論進(jìn)行分析。

1.1 基本原理

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

圖1 無線自組織網(wǎng)絡(luò)中節(jié)點(diǎn)轉(zhuǎn)發(fā)策略Fig.1 Node forwarding strategy in Ad hoc network

這些冗余信息不僅僅使得路由選擇復(fù)雜化，同時(shí)也會(huì)因共享信道的關(guān)系而降低網(wǎng)絡(luò)整體性能。在一個(gè)共享媒質(zhì)的環(huán)境里，大量的數(shù)據(jù)包開銷增加了網(wǎng)絡(luò)時(shí)延和碰撞的概率，因此最終導(dǎo)致較低的包投遞率和吞吐量。博弈論的發(fā)明提供了沖突和競爭數(shù)學(xué)推理的基礎(chǔ)。它已經(jīng)成為一個(gè)豐富的理論，強(qiáng)大的數(shù)學(xué)和計(jì)算工具，同時(shí)更為直觀。而使用該理論工具作為一個(gè)潛在的強(qiáng)大的路由分析工具另外2點(diǎn)原因:

1)路由協(xié)議可以被建模為一個(gè)網(wǎng)絡(luò)和路由之間的博弈;

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

博弈論也廣泛應(yīng)用于經(jīng)濟(jì)學(xué)，社會(huì)科學(xué)，生物學(xué)和工程學(xué)科等[10-12]。采用一種博弈理論的包轉(zhuǎn)發(fā)模型在節(jié)點(diǎn)數(shù)較多的網(wǎng)絡(luò)中可以有效降低網(wǎng)絡(luò)的泛洪。

1.2 系統(tǒng)模型

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

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

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

3)行為:行為的數(shù)量為n，它們分別對應(yīng)于一個(gè)代理可以選擇在任何給定的時(shí)間的行動(dòng)。假設(shè)節(jié)點(diǎn)行為的結(jié)果是二進(jìn)制的，“轉(zhuǎn)發(fā)”對應(yīng)的節(jié)點(diǎn)獲得一個(gè)單位的獎(jiǎng)勵(lì)，“不轉(zhuǎn)發(fā)”對應(yīng)的節(jié)點(diǎn)是零獎(jiǎng)勵(lì)。

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

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

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

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

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

當(dāng)局中人數(shù)目比較大時(shí)，假設(shè)一個(gè)局中人只響應(yīng)其他局中人的長期平均狀態(tài)分布f。則平均場預(yù)期的收益為

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

1.3 收斂性分析

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

1)平穩(wěn)性:對于任何狀態(tài)x和任何類型的集A:

2)一致性:對所有的i

第1個(gè)條件要求μ在動(dòng)態(tài)狀態(tài)，群體策略為f時(shí)是穩(wěn)態(tài)分布，代理策略為σ。第2個(gè)條件是f為μ完全穩(wěn)態(tài)分布。2個(gè)條件一起確保該系統(tǒng)處于平衡狀態(tài)。有以下的命題，建立存在的MFE。證明是通過拓?fù)洳粍?dòng)點(diǎn)理論，根據(jù)假設(shè)，在群體策略中Q是連續(xù)的。

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

證明:證明通過一系列引理進(jìn)行，共分3個(gè)步驟:首先，給定的策略和固定的群體策略，產(chǎn)生的代理穩(wěn)態(tài)分布是群體連續(xù)的。其次，這表明如果固定該策略和群體策略，并計(jì)算新的穩(wěn)態(tài)分布引發(fā)的群體策略，初始群體策略的映射是連續(xù)的。該證明通過布勞威爾不動(dòng)點(diǎn)理論完成[13-15]。

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

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

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

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

引理3 Fσ是連續(xù)的。

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

由于Fσ是連續(xù)的并且映射自身一個(gè)緊致集，使用布勞威爾定理，存在一個(gè)不動(dòng)點(diǎn)f*滿足Fσ(f*)=f*。因此可以證明(σ，f*)可同時(shí)滿足條件1和2?？紤]M總的全變差距離度量dTV，使用以下dTV的等價(jià)參數(shù)。

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

1)讓 μ1，μ2∈M 是任意 2個(gè)測度，μ 是相對于μ1和 μ2絕對連續(xù)的任意測度。假設(shè) ξ1，ξ2是 μ 的Radon-Nikodym導(dǎo)數(shù)，則:

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

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

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

1.4 MFEA 算法

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

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

算法描述:

1)當(dāng)一個(gè)源節(jié)點(diǎn)S要尋找到目的節(jié)點(diǎn)D的路徑時(shí)，首先要確定源節(jié)點(diǎn)S的當(dāng)前時(shí)刻的狀態(tài)，以及其余節(jié)點(diǎn)的狀態(tài)信息，最開始網(wǎng)絡(luò)上的節(jié)點(diǎn)是隨機(jī)

給定任何策略σ，推導(dǎo)出MFE(μ，f)存在的充分條件，并且MFE收斂。考慮映射Tσ:分布的，根據(jù)前向分組格式{源地址，目的地址，序列號，跳數(shù)，行為，節(jié)點(diǎn)1，…節(jié)點(diǎn)N}初始化分組，執(zhí)行2)。

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

3)當(dāng)分組到達(dá)目的節(jié)點(diǎn)后，根據(jù)后向分組格式{源地址，目的地址，序列號，跳數(shù)，行為，類型，轉(zhuǎn)移概率，節(jié)點(diǎn)1，..節(jié)點(diǎn) N}更新數(shù)據(jù)分組格式。當(dāng)分組到達(dá)目的節(jié)點(diǎn)后，更新周圍路由信息的同時(shí)，全局更新路徑上所有的鏈路信息，執(zhí)行4)。

4)沿著獲得的反向路徑信息發(fā)送數(shù)據(jù)分組，反向路徑上的中間節(jié)點(diǎn)根據(jù)行為信息以及收益轉(zhuǎn)移概率轉(zhuǎn)移數(shù)據(jù)，重復(fù)執(zhí)行4)直至到達(dá)源節(jié)點(diǎn)S。

5)源節(jié)點(diǎn)根據(jù)返回信息更新原路由信息。

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

2 仿真結(jié)果與分析

前面介紹了博弈轉(zhuǎn)發(fā)和納什平均場均衡，根據(jù)給定的狀態(tài)計(jì)算最優(yōu)策略，下一個(gè)狀態(tài)的計(jì)算主要根據(jù)公式遞歸求出。為了證明該方法對整體網(wǎng)絡(luò)性能提升的影響，在網(wǎng)絡(luò)模擬器NS-2中進(jìn)行一系列試驗(yàn)。在模擬試驗(yàn)中，仿真參數(shù)見表1所示。

表1 仿真參數(shù)Table 1 Parameters for simulation

下面將分別對不同網(wǎng)絡(luò)環(huán)境下的算法性能進(jìn)行分析。無線自組織網(wǎng)絡(luò)是一個(gè)動(dòng)態(tài)的網(wǎng)絡(luò)，首先仿真環(huán)境假設(shè)在不同的節(jié)點(diǎn)移動(dòng)速度下進(jìn)行，節(jié)點(diǎn)的移動(dòng)速度設(shè)定為10 m/s，2種路由協(xié)議分別根據(jù)端到端的時(shí)延、分組投遞率和系統(tǒng)歸一化開銷3種性能指標(biāo)進(jìn)行分析。

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

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

分組數(shù)據(jù)包投遞率:目的端接收到的數(shù)據(jù)包數(shù)目與網(wǎng)絡(luò)中實(shí)際發(fā)送數(shù)據(jù)包數(shù)目的比值，這個(gè)比率測量了發(fā)現(xiàn)路徑的效率。假設(shè)發(fā)送了100個(gè)數(shù)據(jù)包給目的節(jié)點(diǎn)，最后接收到了60個(gè)數(shù)據(jù)包，那么網(wǎng)絡(luò)中的數(shù)據(jù)包投遞率即為60%，該度量反映了發(fā)送數(shù)據(jù)的成功率。

歸一化開銷:每一個(gè)數(shù)據(jù)包成功被目的節(jié)點(diǎn)接收時(shí)候所需要的路由包數(shù)目。這個(gè)性能反映了網(wǎng)絡(luò)的擁塞程度以及節(jié)點(diǎn)的效率，開銷較大的協(xié)議擁塞的概率相對大一些，并且會(huì)延遲隊(duì)列中數(shù)據(jù)包的發(fā)送。

2.1 端到端時(shí)延

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

這是因?yàn)樵诠?jié)點(diǎn)數(shù)目增加的情況下，網(wǎng)絡(luò)中的變化復(fù)雜起來，路由的可靠性不能保障，因此AODV協(xié)議的時(shí)延增加較快;而MFEA由于采取了均衡的方法，在數(shù)據(jù)包轉(zhuǎn)發(fā)的時(shí)候可以有效的進(jìn)行轉(zhuǎn)發(fā)，不受節(jié)點(diǎn)數(shù)目增多所引起的網(wǎng)絡(luò)拓?fù)渥兓涌斓挠绊?，因此網(wǎng)絡(luò)的延時(shí)并沒有劇烈的變化，在節(jié)點(diǎn)數(shù)量為400時(shí)，MFEA算法的時(shí)延較AODV算法有將近0.2 s的提高，可見在大規(guī)模的網(wǎng)絡(luò)中更加實(shí)用。

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

2.2 分組數(shù)據(jù)包投遞率

圖4為2種協(xié)議下的數(shù)據(jù)包投遞率的性能比較。

圖4 不同節(jié)點(diǎn)數(shù)目下包投遞率比較Fig.4 Packet delivery ratio vs.number of nodes

從圖中可以看出，MFEA方法在節(jié)點(diǎn)數(shù)目較少的時(shí)候投遞率性能與AODV相似，投遞率在85%～90%左右。隨著節(jié)點(diǎn)數(shù)目增加，MFEA協(xié)議性能明顯優(yōu)于正常的AODV協(xié)議，在節(jié)點(diǎn)數(shù)目較高的時(shí)候這種優(yōu)勢尤其顯著，最高可達(dá)8%。這是因?yàn)榫W(wǎng)絡(luò)規(guī)模較大的時(shí)候，AODV在拓?fù)渥兓l繁的網(wǎng)絡(luò)下不能及時(shí)選擇適當(dāng)?shù)穆窂揭詡鞑?shù)據(jù)，同時(shí)在MAC層產(chǎn)生大量的數(shù)據(jù)碰撞也影響了整體的數(shù)據(jù)包投遞率，而MFEA協(xié)議采用了均衡的方法，更能有效地適應(yīng)于變化的網(wǎng)絡(luò)拓?fù)洹?/p>

2.3 歸一化開銷

從圖5中可以看出當(dāng)節(jié)點(diǎn)數(shù)目在100～400，MFEA方法的路由協(xié)議的歸一化系統(tǒng)開銷均低于AODV協(xié)議，最大可達(dá)10。這是因?yàn)锳ODV在這種情況下需要不停的尋找新的可用路徑，從而產(chǎn)生大量的泛洪控制包，因此系統(tǒng)開銷也會(huì)增加很多。而MFEA算法是一種僅需要長期狀態(tài)平均的方法，它可以增加節(jié)點(diǎn)轉(zhuǎn)發(fā)請求包概率，同時(shí)也可以減少因?yàn)榫W(wǎng)絡(luò)拓?fù)渥兓瘞淼逆溌窋嚅_問題，降低了系統(tǒng)的開銷性能。

圖5 不同節(jié)點(diǎn)數(shù)目下歸一化開銷比較Fig.5 Normalized overhead vs.number of nodes

3 結(jié)束語

本文介紹了一種基于平均場均衡的無線自組織網(wǎng)絡(luò)路由協(xié)議，該方法對無線網(wǎng)絡(luò)路由中的轉(zhuǎn)發(fā)泛洪信息包求取平衡狀態(tài)，最終達(dá)到減少冗余信息包，降低系統(tǒng)開銷的目的。在節(jié)點(diǎn)數(shù)目100～400進(jìn)行的仿真結(jié)果表明，本方法能有效地減少網(wǎng)絡(luò)平均端到端時(shí)延，系統(tǒng)開銷，同時(shí)也能增加包投遞率，因此延長了網(wǎng)絡(luò)的使用時(shí)間，從而提高了網(wǎng)絡(luò)效率。

[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]王炳昌，張紀(jì)峰.馬氏跳變大種群隨機(jī)多自主體系統(tǒng)的平均場博弈[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]郭毅，王振興，程東年.基于博弈的域間路由協(xié)同監(jiān)測激勵(lì)策略[J].中國科學(xué):信息科學(xué)，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]楊寧，田輝，黃平，等.基于博弈理論的無線傳感器網(wǎng)絡(luò)分布式節(jié)能路由算法[J].電子與信息學(xué)報(bào)，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]胡靜，沈連豐.基于博弈論的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].東南大學(xué)學(xué)報(bào)，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]汪洋，林闖，李泉林，等.基于非合作博弈的無線網(wǎng)絡(luò)路由機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào)，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.