WLAN中非完全合作博弈策略的MAC協(xié)議

裴菁華

（湖北工業(yè)大學(xué)計算機(jī)學(xué)院，湖北 武漢430068）

IEEE802.11協(xié)議是無線局域網(wǎng)的實施標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)為無線網(wǎng)絡(luò)提供了兩種媒體接入控制機(jī)制：分布式協(xié)調(diào)功能（DCF）方式和點協(xié)調(diào)功能（PCF）方式，DCF使用CSMA／CA（載波偵聽多點接入／沖突避免）協(xié)議，DCF對所有類型的數(shù)據(jù)流都只提供統(tǒng)一的盡力而為的服務(wù)，一個站點檢測到無線媒介空閑的時候才開始發(fā)送信號；PCF定義一種輪詢協(xié)議，但是，DCF或者PCF都不支持任何形式的數(shù)據(jù)優(yōu)先次序［1］.由于語音和多媒體在無線網(wǎng)絡(luò)中的應(yīng)用，IEEE 802.11MAC層不區(qū)分?jǐn)?shù)據(jù)優(yōu)先級的標(biāo)準(zhǔn)需要增加服務(wù)質(zhì)量（QoS）條款.在802.11e中采用EDCA增強(qiáng)型分布式信道訪問是基于DCF進(jìn)行改進(jìn)的接入方式，采用優(yōu)先級分類，將業(yè)務(wù)分為4個AC（access category），指的是 Voice、Video、Best effort、Back ground的訪問類別，通過區(qū)分優(yōu)先級的方式，采用8個優(yōu)先級來實現(xiàn)不同業(yè)務(wù)流的QOS的保障.但是，研究表明，當(dāng)系統(tǒng)處于高競爭的狀態(tài)下，高優(yōu)先級業(yè)務(wù)會耗盡低優(yōu)先級業(yè)務(wù)的資源，使低優(yōu)先級數(shù)據(jù)流出現(xiàn)“饑餓”現(xiàn)象，引發(fā)公平性問題［2］.

筆者針對802.lle無線局域網(wǎng)中的不公平現(xiàn)象，將微觀經(jīng)濟(jì)學(xué)的思想用于網(wǎng)絡(luò)性能優(yōu)化中，通過基于非完全合作博弈論的站點間信道競爭機(jī)制保證各站點獲取信道訪問權(quán).仿真表明，該方法能夠?qū)崿F(xiàn)按優(yōu)先級、延時以及碰撞率成比例的權(quán)重來接入信道，在保證了高優(yōu)先級QoS需求的前提下，提高低優(yōu)先級的吞吐量，降低時延，保證公平的信道訪問機(jī)率.

1 納什均衡

設(shè)參與信道競爭的站點為i和j，任意站點k（k＝i，j）在同一競爭時刻具有兩種策略：S（發(fā)送），W（等待），任意兩站點的博弈策略如圖1所示.

圖1 站點間的競爭策略

當(dāng)節(jié)點發(fā)送分組成功時獲得效用函數(shù)us，等待則獲得效用函數(shù)uw，當(dāng)兩個站點同時發(fā)送數(shù)據(jù)流時，獲得效用函數(shù)任意站點的效用值滿足

假設(shè)各站點具有相同的效用值 （uc，uw，us），站點的發(fā)送概率

那么，任意站點i的效用平均值

每個用戶的效用函數(shù)若要達(dá)到最大化效用函數(shù)的值，其一階必要條件是將集合ui對τ進(jìn)行微分［3］：

那么，可求得任意站點i（i1，…，n）的最優(yōu)發(fā)送策略

納什均衡表明該策略集合是所有參與者的最優(yōu)戰(zhàn)略的組合，記為其中是第i個參與者在均衡情況下的最優(yōu)策略.它是i的所有可能的戰(zhàn)略中使用戶效用ui最大化的戰(zhàn)略.ui表示所有參與人的策略組合的函數(shù)，i的最優(yōu)策略通常依賴于其他參與者的戰(zhàn)略選擇.這里用τ－i＝（τ1，…，τi－1，τi＋1，…，τn）表示除了一個確定的參與者i之外的其他參與者的集合，表示由除QSTAi外的剩余所有參與者的策略組合的向量.τ＊是給定τ－i情況下第i個參與者的最優(yōu)策略［4］，即

而均衡則意味著對所有站點i∈（1，2…n）均成立，所有站點最優(yōu)策略的組合就是參加本次博弈的納什均衡，兩站點競爭的納什均衡組合為

2 非完全合作博弈模型

非完全合作博弈相比合作博弈和非合作博弈而言有所不同［5］.首先，非合作博弈，WLAN中該方式充分考慮了用戶節(jié)點之間互相競爭的特征，即節(jié)點自私地希望最優(yōu)化自己的性能參數(shù)，從而使網(wǎng)絡(luò)處于無序的競爭狀態(tài)，雖然使用區(qū)別優(yōu)先級的方式，但是在高競爭的情況下，低優(yōu)先級的業(yè)務(wù)卻無法保障，導(dǎo)致整個系統(tǒng)性能的降低；其次，完全合作博弈的方式并不符合實際情況中節(jié)點自私性的特點.而非完全合作博弈的方式更適合用于優(yōu)化網(wǎng)絡(luò)中的分組碰撞解決協(xié)議CSMA／CA的方式，使節(jié)點保持既競爭又合作的狀態(tài)，在保障自己質(zhì)量的前提下盡量保障其它的業(yè)務(wù)的質(zhì)量，這樣才能夠得到網(wǎng)絡(luò)整體性能都有所提升的策略，節(jié)點之間雖然沒有明確的合作協(xié)議，但是卻能夠達(dá)到一種合作的效果［6］.

網(wǎng)絡(luò)中各站點間競爭信道的過程主要分為兩個階段，即初始發(fā)送分組階段和分組發(fā)生碰撞的階段，在第一階段的時候各站點競爭信道，在第二階段分組發(fā)生碰撞后的各站點啟動退避策略，依據(jù)這兩個階段將非完全合作博弈的機(jī)制分為兩個過程：

2.1 分組初始發(fā)送策略

首先，根據(jù)各站點的優(yōu)先級賦初始權(quán)值，假設(shè)站點i根據(jù)當(dāng)前發(fā)送分組的權(quán)重Wi，按下式設(shè)置其初始退避時間參數(shù) （Backoff Interval），L表示站點i發(fā)送的分組的平均長度，站點的退避時間間隔BI是時隙長度aslottime的整數(shù)倍.

2.1.1 競爭策略 站點之間的競爭針對不同優(yōu)先級、延時以及碰撞率來設(shè)置權(quán)值實現(xiàn)，站點i的權(quán)重參數(shù)用Wi表示.站點i在博弈中具有非協(xié)作、自私特性，由式［1］可知，權(quán)重參數(shù)與退避時間成反比，Wi值越小，優(yōu)先級越低，退避時間越長，站點占用信道的可能性越小，Wi值越大，優(yōu)先級越高，退避時間越短，站點占用信道的可能性越大.

2.1.2 合作策略 各站點之間的合作主要由相同優(yōu)先級之間和不同優(yōu)先級之間的合作來實現(xiàn).在實現(xiàn)相同優(yōu)先級的業(yè)務(wù)之間，為了實現(xiàn)其合作性，引入了均值為1的參數(shù)s，該參數(shù)的取值范圍是從0.9～1.1之間的隨機(jī)變量.以避免由于相同權(quán)重站點同時發(fā)送數(shù)據(jù)流，導(dǎo)致信道內(nèi)發(fā)生碰撞而產(chǎn)生惡性競爭；在不同優(yōu)先級之間，為了實現(xiàn)其合作性，引入了參數(shù)Scalling＿Factor此參數(shù)可以根據(jù)當(dāng)前信道競爭狀態(tài)的動態(tài)進(jìn)行調(diào)整.權(quán)重參數(shù)Wi體現(xiàn)了高優(yōu)先級數(shù)據(jù)流相對于低優(yōu)先級數(shù)據(jù)流競爭的特性，高優(yōu)先級數(shù)據(jù)流與低優(yōu)先級數(shù)據(jù)流之間合作的特點則通過參數(shù)Scalling＿Factor來實現(xiàn)：

高負(fù)載的情況下，信道競爭激烈時，為避免無序的惡性競爭導(dǎo)致系統(tǒng)性能降低，各優(yōu)先級站點都要利用公式（2）增大其Scalling＿Factor參數(shù)值，延長退避時間；反之，低負(fù)載的情況下，當(dāng)信道較為空閑時，各站點可以利用公式（3）減小Scalling＿Factor參數(shù)值，自利的減少退避時間，獲得較高的系統(tǒng)吞吐量.

2.2 分組碰撞解決策略

上述的納什均衡競爭策略雖然能夠降低不同優(yōu)先級站點之間的初始退避時間的可能性，但是沖突還是不能完全避免，當(dāng)系統(tǒng)中有多個站點同時發(fā)送分組，而退避間隔在同一時刻結(jié)束，那么各站點就會再次同時發(fā)送分組，從而產(chǎn)生碰撞［7］.信道競爭狀況與信道的競爭站點的博弈狀態(tài)有關(guān)，在EDCA的服務(wù)中區(qū)分Acess Category的優(yōu)先級，博弈狀態(tài)不僅要考慮信道的競爭站點數(shù)，更要考慮站點攜帶數(shù)據(jù)流的優(yōu)先級等因素.因此，這里站點的博弈狀態(tài)參數(shù)包括碰撞次數(shù) Collision［P］，參數(shù) Collision＿Counter用來記錄站點當(dāng)前分組發(fā)生碰撞的次數(shù).每次發(fā)生碰撞后，站點i按以下步驟更新其退避間隔BI和博弈狀態(tài)參數(shù)：

步驟1 碰撞計數(shù)器初始值為0，發(fā)生碰撞后增加1.

步驟2 更新當(dāng)前權(quán)值，由下式計算各站點的權(quán)重，每行依次表示業(yè)務(wù)優(yōu)先級、延時以及碰撞次數(shù)在權(quán)值中的比例：

步驟3 根據(jù)下式更新當(dāng)前退避間隔，這樣就可以把業(yè)務(wù)的優(yōu)先級、延時以及碰撞率等結(jié)合起來調(diào)整退避級數(shù)：

在上述對于各站點發(fā)生碰撞之后的解決策略的思想是：碰撞計時器初始值為0，站點i分組每發(fā)生一次碰撞，碰撞計數(shù)器增加1，然后根據(jù)公式更新站點i的權(quán)值，最后根據(jù)權(quán)值采用二進(jìn)制退避方法來調(diào)整退避間隔BI的值［8］.

3 仿真及分析

為了簡化分析，設(shè)站點內(nèi)的各隊列處于飽和狀態(tài)，即始終都有分組待發(fā)送，每個站點只有同種類型的數(shù)據(jù)流發(fā)送，信道理想，不考慮隱藏終端和捕獲效應(yīng).通過和標(biāo)準(zhǔn)的IEEE802.11eEDCA進(jìn)行比較，對G－EDCA基于數(shù)據(jù)流不同的優(yōu)先級，采用優(yōu)先級、延時以及碰撞次數(shù)以不同的比例對不同業(yè)務(wù)設(shè)置不同的權(quán)重，并對其進(jìn)行仿真及分析.本文中物理層采用IEEE802.11b的物理層參數(shù)如表1，使用802.11e協(xié)議的默認(rèn)站點競爭參數(shù)見表2.

表1 802.11b物理層參數(shù)

表2 EDCA機(jī)制仿真參數(shù)

3.1 吞吐量仿真及分析

25個節(jié)點隨機(jī)分布在500m×500m的場景下，仿真時間為80s.圖2所示，在低負(fù)載的情況下，高優(yōu)先級的業(yè)務(wù)（AC3，AC2）吞吐量呈上升趨勢，隨著競爭站點的增加，網(wǎng)絡(luò)負(fù)載增大，信道競爭變得激烈，AC3，AC2逐漸下降并趨于穩(wěn)定；低優(yōu)先級的業(yè)務(wù)（AC1，AC0）的吞吐量卻隨著網(wǎng)絡(luò)負(fù)載的增大而迅速下降，表明EDCA機(jī)制在高負(fù)載的情況下，低優(yōu)先級的業(yè)務(wù)會被高優(yōu)先級的業(yè)務(wù)耗盡，產(chǎn)生不公平.

圖2 EDCA吞吐量

圖3 所示，采用非完全合作博弈論競爭與合作相結(jié)合的G－DECA方法，高優(yōu)先級的業(yè)務(wù)隨著負(fù)載增加而上升，在競爭逐漸激烈的情況下，吞吐量相較EDCA有所降低，卻并不至于影響其QOS，低優(yōu)先級的業(yè)務(wù)吞吐量降低明顯減慢，保障了低優(yōu)先級業(yè)務(wù)的性能.

圖3 圖G－EDCA吐吞量

3.2 延時仿真及分析

18個節(jié)點分布在500m×1 000m的場景下，如圖4所示，仿真時間為450s.從2個QSTA開始，每隔50s增加一個節(jié)點發(fā)送數(shù)據(jù)流.

圖4 網(wǎng)絡(luò)拓?fù)?/p>

圖5 表示隨著仿真時間的增加，網(wǎng)絡(luò)中端到端的延時的變化狀況.在整個過程中隨著時間的增加，EDCA平均延時逐漸在增加，在60s的時候，延遲突然增大，這是因為，高優(yōu)先級的業(yè)務(wù)耗盡了低優(yōu)先級的業(yè)務(wù)資源，低優(yōu)先級的業(yè)務(wù)出現(xiàn)了延遲，GEDCA可以在高競爭的情況下，提高低優(yōu)先級業(yè)務(wù)的權(quán)重，保證數(shù)據(jù)流的發(fā)送，所以G－EDCA延時比較穩(wěn)定.

圖5 延時對比

4 結(jié)論

本文提出了一種競爭合作相結(jié)合的EDCA協(xié)議.它將EDCA與非完全合作博理論相結(jié)合，采用競爭合作的方式，在高度競爭時，各站點保證高優(yōu)先級業(yè)務(wù)的前提下，增加低優(yōu)先級業(yè)務(wù)的權(quán)重，給低優(yōu)先級的業(yè)務(wù)更好的服務(wù)，從而保證了網(wǎng)絡(luò)QOS.

從NS2仿真實驗可以看出，與IEEE 802.11eEDCA相比，G－EDCA能夠有效地提高網(wǎng)絡(luò)的吞吐量，降低了端到端的延遲.但是，本文沒有對每個QSTA發(fā)送不同類型的數(shù)據(jù)流做研究，在今后的工作中，還需要對G－EDCA做情況更加復(fù)雜的研究與驗證，設(shè)計更加完善的實驗?zāi)Ｐ团c仿真.

［1］IEEE.Wireless LAN Medium Access Control（MAC）and Physical Layer （PHY）specifications：Medium Access Control（MAC）Quality of Service（QoS）Enhancements［S］.IEEE Standard 802.11e，2005.

［2］周立衡，章國安，邱恭安.IEEE 802.11eEDCA 競爭窗口算法的研究［J］.SCIENCE ＆ TECHNOLOGY INFORMATION.2010，（25）：19.

［3］GBianehi.Performance analysis of the IEEE802.11 distributed coordination function［J］.IEEE Journal of Selected Areas in Telceommunications.2000.3，18（3）：535－547.

［4］李明欣，陳山枝，謝東亮.異構(gòu)無線網(wǎng)絡(luò)中基于非合作博弈論的資源分配和 接入控制［J］.Journal of software.2010.8：2 037－2 049.

［5］熊啟濱，胡放之.合作與非完全合作博弈理論研究綜述［J］.Journal of China Three Gorges University，Humanities＆Sciences，2009，5（3）：80－83.

［6］姚 欣，曹 敏，戴瓊海.無線網(wǎng)絡(luò)的QoS控制的博弈論［J］.電信快報，2001（7）：9－10.

［7］Jia Hu，Geyong Min，Weijia Jia.Admission control in the IEEE 802.11eWLANs based on analytical modelling and game theory［J］.IEEE Communications Society，2009，（19）：379－384.

［8］LI Yishan，LI Yuhong，LI Tao.A game－theoretic resource allocation algorithm based on utility in IEEE 802.11e［J］.IEEE computer society.2011（131）：283－288.