WLAN中非完全合作博弈策略的MAC協議

裴菁華

（湖北工業大學計算機學院，湖北 武漢430068）

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

筆者針對802.lle無線局域網中的不公平現象，將微觀經濟學的思想用于網絡性能優化中，通過基于非完全合作博弈論的站點間信道競爭機制保證各站點獲取信道訪問權.仿真表明，該方法能夠實現按優先級、延時以及碰撞率成比例的權重來接入信道，在保證了高優先級QoS需求的前提下，提高低優先級的吞吐量，降低時延，保證公平的信道訪問機率.

1 納什均衡

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

圖1 站點間的競爭策略

當節點發送分組成功時獲得效用函數us，等待則獲得效用函數uw，當兩個站點同時發送數據流時，獲得效用函數任意站點的效用值滿足

假設各站點具有相同的效用值 （uc，uw，us），站點的發送概率

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

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

那么，可求得任意站點i（i1，…，n）的最優發送策略

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

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

2 非完全合作博弈模型

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

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

2.1 分組初始發送策略

首先，根據各站點的優先級賦初始權值，假設站點i根據當前發送分組的權重Wi，按下式設置其初始退避時間參數 （Backoff Interval），L表示站點i發送的分組的平均長度，站點的退避時間間隔BI是時隙長度aslottime的整數倍.

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

2.1.2 合作策略 各站點之間的合作主要由相同優先級之間和不同優先級之間的合作來實現.在實現相同優先級的業務之間，為了實現其合作性，引入了均值為1的參數s，該參數的取值范圍是從0.9～1.1之間的隨機變量.以避免由于相同權重站點同時發送數據流，導致信道內發生碰撞而產生惡性競爭；在不同優先級之間，為了實現其合作性，引入了參數Scalling＿Factor此參數可以根據當前信道競爭狀態的動態進行調整.權重參數Wi體現了高優先級數據流相對于低優先級數據流競爭的特性，高優先級數據流與低優先級數據流之間合作的特點則通過參數Scalling＿Factor來實現：

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

2.2 分組碰撞解決策略

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

步驟1 碰撞計數器初始值為0，發生碰撞后增加1.

步驟2 更新當前權值，由下式計算各站點的權重，每行依次表示業務優先級、延時以及碰撞次數在權值中的比例：

步驟3 根據下式更新當前退避間隔，這樣就可以把業務的優先級、延時以及碰撞率等結合起來調整退避級數：

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

3 仿真及分析

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

表1 802.11b物理層參數

表2 EDCA機制仿真參數

3.1 吞吐量仿真及分析

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

圖2 EDCA吞吐量

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

圖3 圖G－EDCA吐吞量

3.2 延時仿真及分析

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

圖4 網絡拓撲

圖5 表示隨著仿真時間的增加，網絡中端到端的延時的變化狀況.在整個過程中隨著時間的增加，EDCA平均延時逐漸在增加，在60s的時候，延遲突然增大，這是因為，高優先級的業務耗盡了低優先級的業務資源，低優先級的業務出現了延遲，GEDCA可以在高競爭的情況下，提高低優先級業務的權重，保證數據流的發送，所以G－EDCA延時比較穩定.

圖5 延時對比

4 結論

本文提出了一種競爭合作相結合的EDCA協議.它將EDCA與非完全合作博理論相結合，采用競爭合作的方式，在高度競爭時，各站點保證高優先級業務的前提下，增加低優先級業務的權重，給低優先級的業務更好的服務，從而保證了網絡QOS.

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

［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］李明欣，陳山枝，謝東亮.異構無線網絡中基于非合作博弈論的資源分配和 接入控制［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］姚 欣，曹 敏，戴瓊海.無線網絡的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.