基于完美信息博弈的多無線電信道分配算法

戴昊峰，何世彪，2，韓 輝，張 暉，2，譚 冕

(1.重慶通信學院重慶 400035;2.重慶大學通信學院重慶 400044)

無線ad hoc網(wǎng)絡采用分布式、自組織、無中心的架構(gòu)，可以很方便地應用于不同場合，但是在網(wǎng)絡資源(主要是頻譜資源)有限的情況下，如何有效、公平地配置網(wǎng)絡資源，是ad hoc網(wǎng)絡在運用時遇到的一個最為關(guān)鍵的問題，也是目前尚未完全解決的問題［1］。近期的研究表明，博弈論可以作為此類問題的有效分析工具［2－3］。根據(jù)用戶對網(wǎng)絡信息的掌握情況，可分為完美信息博弈和不完美信息博弈。所謂完美信息博弈是指參與者知道用戶沖突域內(nèi)每個設備所使用的信道，或者每個信道所分配的無線電。隨著無線射頻收發(fā)器硬件相關(guān)技術(shù)的迅速發(fā)展:一是無線網(wǎng)絡節(jié)點的射頻端已經(jīng)具備感知周圍信息的功能，二是在一個無線網(wǎng)絡節(jié)點上裝備多個射頻器前端已經(jīng)成為廣泛的選擇。因此選擇基于完美信息博弈的多無線電信道分配在ad hoc網(wǎng)絡中具有可行性，在未來也有很大的發(fā)展前景，對它的研究有著重大的意義［4－5］。

目前，對于無線ad hoc網(wǎng)絡的信道分配機制主要分為集中式和分布式兩種，本文主要研究了分布式的信道分配機制。文獻［6］提出了一種最優(yōu)信道帶寬調(diào)制方法，利用一種“裝箱壓縮”方法并結(jié)合多無線電技術(shù)提出分布式流量感知的信道帶寬調(diào)制算法，有效地提高了頻譜使用率，但沒有考慮用戶獲取信道的公平性;文獻［7］中采用一種對每個節(jié)點分配同樣信道集合的方式，這種信道分配方式雖然易于實現(xiàn)，也能夠保證網(wǎng)絡的連通性，但不足以適應復雜的網(wǎng)絡情況;文獻［8］中根據(jù)用戶獲取信息的不同提出了3種算法解決多無線電信道的分配問題，3種算法都從不同方向?qū)崿F(xiàn)了自私節(jié)點向納什均衡點的收斂，并通過理論證明和仿真結(jié)果驗證了第三種信道分配算法可以實現(xiàn)在網(wǎng)絡中達到納什均衡的目的，但該算法假設網(wǎng)絡場景為單沖突域，無法適應多沖突域的網(wǎng)絡場景。文獻［9］在文獻［8］的基礎上提出了適合網(wǎng)絡場景為多沖突域的算法，算法假設兩跳范圍的用戶為沖突域內(nèi)，并以此為網(wǎng)絡中的各個自私節(jié)點以非合作博弈的方式對其無線電接口分配信道，最后仿真對比了單多沖突域的用戶平均傳輸速率，證明多沖突域情況更能最大化信道利用率，但是該算法復雜度較高，不易實現(xiàn)。針對以上算法的不足，本文提出一種較低復雜度的信道分配算法，用戶通過感知自身沖突域內(nèi)其他用戶的信道信息來選擇信道以達到納什均衡分配所需滿足的條件(即使效用函數(shù)最大)，仿真結(jié)果表明算法可以達到納什均衡點，并能夠較好地改善網(wǎng)絡性能(與單沖突域情況對比)。

1 系統(tǒng)模型

本文假設使用頻分復用(Frequency Division Multiple Access，F(xiàn)DMA)技術(shù)，將可用頻率分為相同帶寬的正交信道(在IEEE802.11a協(xié)議中有8條信道)。定義可用正交信道集合為C，可表示為

圖1 網(wǎng)絡拓撲結(jié)構(gòu)

假設距離用戶兩跳及以內(nèi)的用戶為沖突域內(nèi)用戶，用戶可以感知自身沖突域內(nèi)用戶的信道信息。如圖1所示，用戶1的沖突域包含用戶2，3，9，10，即用戶1在信道分配時可以感知到上述用戶的完全信息。其他范圍為用戶1的沖突域外，此時假如用戶6使用與用戶1相同的信道則不會對用戶1產(chǎn)生干擾。

由于使用多無線電技術(shù)，用戶能夠同時使用多個信道進行數(shù)據(jù)的傳輸，那么用表示用戶i的沖突域內(nèi)用戶i使用信道c∈Ci的無線電數(shù)目，Ci為用戶i使用的信道集合，有Ci?C，且該用戶所占用的所有無線電數(shù)目為，相應的，用戶i的沖突域內(nèi)使用信道c的無線電數(shù)目為。基于以上假設，用戶i的信道分配策略可以表示為:，其中。從表示式可以看出，策略向量就是占用每個信道的用戶無線電數(shù)目，那么所有用戶的策略矩陣S可以表示為

式中:用S－i表示除用戶i外所有用戶的策略集合。

用戶i的用戶收益，即用戶所占用信道的帶寬(用戶傳輸速率)表示為Ui，由于用戶位于不同的沖突域，假如用戶j位于用戶i的沖突域內(nèi)，用戶j的無線電如果占用的信道為用戶i的無線電所占用的，那么它們將平分該信道總的帶寬，假設信道的帶寬不會因為無線電數(shù)目的增加而下降［9］，而對于用戶i沖突域外的用戶而言，使用相同的信道將不會對用戶i造成干擾。因此如果用戶i的無線電占用信道c，那么用戶i的無線電能獲得的帶寬為

2 多無線電信道分配策略的納什均衡

本節(jié)研究在多沖突域條件下博弈的納什均衡存在性的判定條件。首先引入納什均衡［2］的定義:

換句話說，在一個已經(jīng)達到納什均衡的策略中，沒有用戶能夠通過單方面地改變用戶策略來改變用戶的收益。然而，納什均衡解可能存在兩種情況，一種是可能存在多個納什均衡解，二是納什均衡的解從系統(tǒng)模型來看不一定是最優(yōu)的。由此引出了帕累托最優(yōu)［2］的概念:

定義2:帕累托最優(yōu)(Pareto－Optimality)策略向量Spo是帕累托最優(yōu)的，假如存在S'使得式(5)成立

換句話說，假如一個策略集合是帕累托最優(yōu)的，那么不存在其他策略集合s'使得至少有一個參與者的效用得到增加，而其他參與者的效用不會減少。

引理1:如果S*是一個多無線電多信道分配博弈的納什均衡策略，那么就有ki=k，?i成立。

引理1表明，一個理性用戶會使用所有無線電來增加自身的效用。

根據(jù)文獻［8］和［9］有以下定理成立，此定理有較強的適應性，無論是在單沖突域還是多沖突域環(huán)境中都能成立，接下來本文所提算法將緊密圍繞這個定理展開。

定理1:信道分配策略S*是一個NE的，當且僅當滿足以下兩個條件:

由文獻［9］還可知假如信道c的帶寬函數(shù)R(kc)獨立于kc，?c∈C，那么NE信道分配策略S*一定是帕累托最優(yōu)的。也就是假如R(kc)的值不會隨著kc的變化而變化，那么得到的NE信道分配策略一定是最優(yōu)的。因此本文都假設R(kc)是獨立于kc。

3 信道分配算法描述

基于完美信息的信道分配算法要求用戶在信道分配前不僅知道自身的無線電所使用的信道情況，還要求用戶節(jié)點的無線電射頻端感知自身沖突域內(nèi)其他用戶的信息，以此來確定自身的信道策略使整體策略滿足定理1中的條件(使用戶自身效用函數(shù)達到最大值)。

算法最初進行一次隨機信道分配，分配完成后，每個用戶感知自身沖突域內(nèi)每條信道c∈C上的無線電數(shù)目，并試圖通過重新組織分配信道給用戶的無線電接口來增大用戶總的傳輸速率。但是這個過程可能會出現(xiàn)一個問題:很多用戶同時申請改變信道，這將會造成沖突，影響算法效率，延長收斂時間。為此，本文將引入IEEE802.11的退避機制來解決這個問題，首先定義一個退避窗口W，并且每個用戶以相同的概率從集合{1，2，…，W}中隨機選擇一個初始值作為退避計數(shù)器的值。然后在每一輪每個用戶都會將自身退避計數(shù)器值減1，當退避計數(shù)器的值為0時用戶才能重新將信道分配給無線電，在用戶分配完信道后，又返回退避窗口W重置一個隨機值。這樣有效地避免了用戶間的沖突，增強了網(wǎng)絡整體性能。當用戶的改變順序確定后，此時如果輪到用戶i∈N改變其信道，那么用戶i首先感知其沖突域內(nèi)有哪些用戶和其所有信道信息，將用戶i沖突域內(nèi)用戶記為，它是從所有用戶中提取出來的部分用戶的集合，記為用戶集合中使用次數(shù)最少的信道，表示用戶ii的無線電使用信道的數(shù)目，為用戶i的沖突域內(nèi)用戶使用信道的無線電數(shù)目，同理為為用戶i的沖突域內(nèi)用戶使用信道b的無線電數(shù)目。當完成第一部分信道分配后此時用戶i的沖突域內(nèi)用戶已經(jīng)滿足定理1中第2個條件，但算法不一定滿足第1個條件，所以需要再次判斷分配。最后經(jīng)過多次循環(huán)可以達到整體的納什均衡點。

算法的流程圖如圖2所示。

圖2 算法流程圖

4 仿真分析

為了驗證上述算法的相關(guān)性能，本小節(jié)設計了如下的仿真場景。用戶的拓撲結(jié)構(gòu)如圖1所示，假設每條信道的吞吐量假設固定均為R(kc)=54 Mbit/s，由前文可知其不隨著無線電數(shù)目的增加而下降。退避窗口值W=20，編程語言為MATLAB。

圖3給出一個已達納什均衡點的信道分配結(jié)果，其中，用戶數(shù)目=10，每個用戶的無線電接口數(shù)目相同為k=3，正交信道數(shù)目為=8，從圖中可以看出，任何用戶在其沖突域內(nèi)的信道分配結(jié)果都滿足定理1的條件，達到了納什均衡。

圖4中用戶數(shù)目=10，每個用戶的無線電接口數(shù)目k=3，正交信道數(shù)目為=8，但是假設所有用戶在同一沖突域內(nèi)，并假設距離用戶兩跳及以內(nèi)的用戶為沖突域內(nèi)用戶，即用戶位于不同的沖突域中，圖示呈現(xiàn)了用戶在單沖突域和多沖突域中用戶收益的仿真對比，可以看出，用戶在多沖突域中具有更高的信道使用率。

圖3 一種納什均衡的信道分配結(jié)果

圖4 用戶在單多沖突域收益對比

圖5 算法執(zhí)行前后用戶收益的對比

圖6 不同的無線電數(shù)目對用戶收益的影響

圖7 不同信道數(shù)目對用戶收益的影響

5 結(jié)束語

眾所周知，無線ad hoc網(wǎng)絡的信道分配問題一直都是一個NP難問題，本文根據(jù)無線ad hoc網(wǎng)絡分布式的特點，引入博弈論的方法，提出了一種適用于多沖突域情況的完美信息信道分配算法，通過實驗仿真與單沖突域的情況做出對比，驗證了本文的算法可以更好地最大化信道的使用率，使網(wǎng)絡負載更加均衡。本文考慮的是完美信息，實際中由于硬件條件等達不到要求可能很難做到獲取完美信息，并且文中并沒有考慮多沖突域環(huán)境下可能存在的隱藏/暴露終端等問題，因此下一步工作將考慮如果無法獲取完美信息應該如何達到納什均衡并且兼顧隱藏/暴露終端問題。

:

［1］汪濤.無線網(wǎng)絡技術(shù)導論［M］.北京:清華大學出版，2009.

［2］SRIVASTAVA V，NEEL J O，MACKENZIE A B，et al.Using game theory to analyze wireless ad hoc networks［J］.IEEE Communications Surveys and Tutorials，2005，7(1/4):46－56.

［3］彭文藝，饒志強，吳濤.博弈論在無線自組網(wǎng)技術(shù)中的應用［J］.計算機與數(shù)字工程，2006，34(6):117－119.

［4］BAHL V，ADYA A，PADHYE J，et al.Reconsidering the wireless LAN platform with multiple radios［C］//Proc.Workshop on Future Directions in Network Architecture.［S.l.］:IEEE Press，2003.

［5］YANG D，F(xiàn)ANG X，XUE G.Channel allocation in non－cooperative multi－radio multi－channel wireless networks［C］//Proc.IEEE INFOCOM.Orlando，F(xiàn)L:IEEE Press，2012:882－890.

［6］RANIWALA A，CHIUEH T.Architecture and algorithms for an IEEE 802.11－based multi－channel wireless mesh network［C］//Proc.24th Annual Joint Conference of the IEEE Computer and Communications Societies.New York:IEEE Press，2005:2223－2234.

［7］DRAVES R，PADHYE J，ZILL B.Routing in multi－radio，multi－h(huán)op wireless mesh networks［C］//Proc.10th Annual International Conference on Mobile Computing and Networking.［S.l.］:ACM Press，2004:114－128.

［8］FELEGYHAZI M，CAGALJ M，BIDOKHTI S S，et al.Non－cooperative multi－radio channel allocation in wireless networks［C］//Proc.26th IEEE International Conference on Computer Communications.［S.l.］:IEEE Press，2007:1442－1450.

［9］KIM H K，LEE T J.CHASS－M:channel assignment for fair payoff based on game theory for wireless multi－h(huán)op networks［C］//Proc.4th International Conference on Innovations in Information Technology.Dubai:IEEE Press，2007:282－286.

［10］史佳佳，劉宴兵.多射頻無線網(wǎng)絡中多信道分配方法的研究［J］.計算機應用研究，2012，29(6):2290－229.

［11］鄭鵬宇，何世彪，戴昊峰，等.基于最大化網(wǎng)絡吞吐量的WMN信道分配算法［J］.電視技術(shù)，2013，37(19):176－180.