WLAN中非合作博弈的信道分配研究

吳秀琳，周蓮英

（江蘇大學(xué) 計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江212013）

0 引 言

隨著新無(wú)線電設(shè)備和應(yīng)用的出現(xiàn)及對(duì)無(wú)線電頻譜的需求激增，當(dāng)前適用于無(wú)線通信的頻譜資源變得日益緊張，迫使美國(guó)聯(lián)邦通信委員會(huì)改變基于IEEE 802.11的無(wú)線局域網(wǎng)使用單一的固定信道結(jié)構(gòu)的僵化的信道分配政策。這種信道分配方式已經(jīng)嚴(yán)重阻礙稀缺的頻譜資源的分配，并造成分配給用戶的頻譜資源有不同程度的閑置或緊缺，從而降低了整個(gè)網(wǎng)絡(luò)的性能，因此動(dòng)態(tài)頻譜分配成為研究的方向?，F(xiàn)在有了CR技術(shù)［1］的幫助，能夠主動(dòng)檢測(cè)頻譜使用情況，自適應(yīng)的改變自身通信參數(shù)，重新配置無(wú)線電設(shè)備的重要參數(shù)，包括中心頻率，信道寬度等［2］。有了這種可改變的新信道，無(wú)線局域網(wǎng)的接入點(diǎn)可以根據(jù)通信需求選擇合適的信道寬度和中心頻率 （初始頻率），以期望實(shí)現(xiàn)高可靠性通信，使無(wú)線電設(shè)備能有效自適應(yīng)的去分配使用頻譜資源。

由于競(jìng)爭(zhēng)開(kāi)放的頻譜資源將使得用戶不再相互合作，接入點(diǎn)只為追求自身利益，且博弈論是非常適用于研究主體的自私行為及其相互間作用的理論，而認(rèn)知無(wú)線電關(guān)鍵技術(shù)是對(duì)頻譜資源在認(rèn)知用戶間的分配，因而可以使用博弈論為其認(rèn)知主體相關(guān)的博弈過(guò)程找到納什均衡點(diǎn)。目前博弈論的動(dòng)態(tài)頻譜分配方法已成為國(guó)內(nèi)外研究的熱點(diǎn)。盡管存在基于博弈論的動(dòng)態(tài)頻譜分配方法，例如通過(guò)成功的增強(qiáng)頻譜功率方法可以分配滿足納什均衡，但是功率的增加同樣帶來(lái)噪聲干擾的增加，致使系統(tǒng)效率降低；例如還可使用本地觀察站進(jìn)行信道變分法等。但仍有些基礎(chǔ)問(wèn)題待解決，如頻譜周圍的環(huán)境經(jīng)常的改變并且這里沒(méi)有中央機(jī)構(gòu)去協(xié)調(diào)不同的接入點(diǎn)分配頻譜，因此在典型的無(wú)中心分布式的頻譜資源分配方式下，本文以非合作博弈理論為依據(jù)［3－4］，所有的接入點(diǎn)都參與并做出選擇開(kāi)始頻率和結(jié)束頻率行為，以純納什均衡為特征來(lái)研究可變帶寬信道分配策略，以純納什均衡策略代替固定信道分配，實(shí)現(xiàn)單階段單碰撞域中公平且系統(tǒng)最優(yōu)的信道帶寬分配，在對(duì)客戶滿足信道公平性的基礎(chǔ)上也能實(shí)現(xiàn)系統(tǒng)吞吐量達(dá)到最大化。

1 系統(tǒng)模型

假定考慮的情況是K組用戶同時(shí)共存在一個(gè)時(shí)空并同時(shí)完成頻譜帶寬分配，同一組中用戶也可相互進(jìn)行通信。頻譜的使用將會(huì)相互干擾其它組，為研究簡(jiǎn)單起見(jiàn)，假設(shè)每一個(gè)組有唯一單個(gè)的發(fā)射臺(tái)接受器裝置。所有的收發(fā)設(shè)備都完全有效的負(fù)載使用的，也就是說(shuō)接入點(diǎn)總是有數(shù)據(jù)進(jìn)行傳輸，在一時(shí)間段上，所有的收發(fā)裝置都盡量占用頻譜，實(shí)驗(yàn)環(huán)境假設(shè)信道是瑞利衰落的，也就是在無(wú)線通信中，密集的建筑和其它物體使得無(wú)線設(shè)備的發(fā)射機(jī)和接收機(jī)之間沒(méi)有直射路徑，而且使得無(wú)線信號(hào)被衰減、反射、折射、衍射。經(jīng)過(guò)曼哈頓的實(shí)驗(yàn)證明，當(dāng)?shù)氐臒o(wú)線信道環(huán)境確實(shí)接近于瑞利衰落。故建筑物密集的城鎮(zhèn)中心地帶的無(wú)線信道分配中信道使用符合瑞利衰落模型。

多接入點(diǎn)無(wú)線網(wǎng)絡(luò)模型中，考慮單碰撞域方案［5］：

（1）非重疊，每一接入點(diǎn)都不能與其它接入點(diǎn)在傳輸頻率上有重疊；

（2）負(fù)載不均衡，根據(jù)無(wú)線局域網(wǎng)最新的一些測(cè)量數(shù)據(jù)顯示，在無(wú)線局域網(wǎng)中的接入點(diǎn)通常有不均衡的通信負(fù)荷；

（3）每個(gè)客戶端都要和關(guān)聯(lián)接入點(diǎn)進(jìn)行聯(lián)系；

（4）根據(jù)文獻(xiàn) ［3－4］頻譜資源采用分布式的非合作自私分配策略。

為研究簡(jiǎn)單起見(jiàn)，忽略接收器帶來(lái)的干擾，重點(diǎn)考慮非重疊信道分配，在許多情況下，可能過(guò)于保守［6］?？墒褂媒品ǚ椒ㄕ{(diào)整一個(gè)由于頻率重疊所造成的接入點(diǎn)之間所能承受的干擾范圍。

接收的信號(hào)在一個(gè)時(shí)間段內(nèi)假設(shè)保持不變，從時(shí)間段到另一個(gè)時(shí)間段獨(dú)立地改變，白噪聲是獨(dú)立同分布的用Wi～CN （0，N0）表示，N0是噪聲功率，CDMA中已經(jīng)證實(shí)白噪聲約等于高斯噪聲。受設(shè)備功能的限制，設(shè)備i的傳輸功率不能超過(guò)自己的功率峰值。通常這里沒(méi)有功率中心去協(xié)調(diào)頻譜分配，共存的不同的系統(tǒng)不會(huì)自愿的互相幫助去分享同一個(gè)目標(biāo)，也就是假設(shè)每個(gè)設(shè)備都是自私的是非常合理的，對(duì)無(wú)線用戶來(lái)說(shuō)唯一的目標(biāo)就是追求更高的自我利益，即得到更大信道帶寬。這種自私行為能夠通過(guò)博弈論進(jìn)行很好的分析。因此，我們提出共享頻譜的博弈模型如下所示：

局中人：K個(gè)不同的傳輸接收裝置。

行為：每個(gè)局中人能夠選擇傳輸功率pi。

結(jié)果：功率已被不同局中人使用后，局中人i獲得的傳輸。

認(rèn)知無(wú)線電的頻譜分配問(wèn)題是一個(gè)關(guān)系到不同用戶頻譜策略選擇的博弈過(guò)程，如果把功率的使用分配等同于信道頻譜的分配，此問(wèn)題可以建模成一個(gè)博弈的輸出［6］，數(shù)學(xué)定義博弈為Γ＝ ｛N，｛Si｝i∈N，｛Ui｝i∈N｝，N是無(wú)線局域網(wǎng)接入點(diǎn)參與者 （認(rèn)知用戶，他們的行動(dòng)策略是對(duì)傳輸信道的選擇，并且他們的效用和所選擇的信道有關(guān)）的有限集，Si是相對(duì)于認(rèn)知用戶i的策略集。定義S＝×Si，（i∈N）作為策略空間，Ui：S→R是和局中人i相關(guān)策略的效用函數(shù)集。對(duì)于博弈Γ中的每一個(gè)認(rèn)知用戶i，效用函數(shù)Ui是Si和其它競(jìng)爭(zhēng)用戶S－i［5］的函數(shù)，其中Si是認(rèn)知用戶i選擇的策略，S－i是其它競(jìng)爭(zhēng)用戶的策略。

用chall＝ ［Min，Max］代表整個(gè)網(wǎng)絡(luò)的頻譜范圍，分配給APi的信道用chi＝ ［mini，maxi］（0＜Min≤mini≤maxi≤Max）來(lái)表示，chi的帶寬定義為Bi＝ maxi－mini，chi∩chj表示chi和chj（i≠j）的重疊部分，且maxj＞ mini或maxi＞minj。用chi∪chj表示chi和chj不重疊的部分。

為局中人設(shè)計(jì)效用函數(shù)。假設(shè)可達(dá)到的數(shù)率和發(fā)射功率即有效帶寬是線性相關(guān)的［3－4］。那么和接入點(diǎn)APi相關(guān)的客戶需求總量用Di（Di＞0）bit／s表示，注意到帶寬和功耗的近似線性關(guān)系，帶寬越高功耗越大［4］，故用代價(jià)函數(shù)來(lái)表示帶寬耗費(fèi)，用C （Bi）（C （Bi）＞0）表示局中人i的代價(jià)函數(shù)，很明顯，這是一個(gè)關(guān)于Bi的遞增函數(shù)。接下來(lái)定義一個(gè)效用函數(shù)：

Vi（·）通常是用來(lái)表示信道使用收益的遞增函數(shù)，λ是正常量，這個(gè)常量可使信道頻譜中的可用頻率有效使用，在博弈過(guò)程中認(rèn)知主體相應(yīng)的調(diào)整該值。假設(shè)Bi＞0并且V （λBi）＞ C （Bi），并且 V （λBi）－C （Bi）也是隨 Bi遞增的。效用函數(shù)顯示，當(dāng)局中人被其它接入點(diǎn)重疊，效用函數(shù)趨近于0，因此，一個(gè)理性的局中人應(yīng)該想方設(shè)法地去避開(kāi)重疊。例如局中人i，當(dāng)λBi＜Di時(shí)總希望會(huì)放大信道帶寬，然而，當(dāng)λBi≥Di，由于擴(kuò)大信道帶寬將會(huì)減少局中人i的效用，因此局中人i不再有擴(kuò)大信道帶寬的動(dòng)機(jī)。因此，前面的效用函數(shù)能強(qiáng)制所有局中人節(jié)約信道資源。簡(jiǎn)明起見(jiàn)，假設(shè)V （·）和C（·）用線性遞增函數(shù)表示。

2 系統(tǒng)效用最大理想公平分配

2.1 純納什均衡的策略

純納什均衡就是雙方在對(duì)方的策略下自己現(xiàn)有的策略是最好的策略，即此時(shí)雙方在對(duì)方給定的策略下不愿意調(diào)整自己的策略，因此只有純NE才能有穩(wěn)定的信道分配。

由純納什均衡含義可知，如果一個(gè)策略組合 （S1，S2，…，Sn）是一個(gè)純納什均衡，那么 i∈ ｛1，2，…，N｝必定UFi（Si，S－i）≥0，并且λBi≤Di。

現(xiàn)在給出一個(gè)策略組合 （S1，S2，…，Sn），若每一個(gè)局中人i（i∈ ｛1，2，…，N｝）滿足下列條件之一，則是一個(gè)純納什均衡。

（1）Di＞λBi，并且chi∪chj（ j≠i），滿足下列件之一：①-j≠i，-k≠i，maxk－mini＝ minj－ maxi＝ 0。②-j≠i，minj－ maxi＝0且 mini－ Min＝0。③-j≠i，mini－maxj＝0，且 Max－maxi＝0。（條件1）

假設(shè)局中人i（i∈ ｛1，2，…，N ｝）滿足 （條件1），在這種情況下，局中人不會(huì)通過(guò)單方面偏離來(lái)增加他的效用。因?yàn)槿绻鼣U(kuò)大信道帶寬，那么它必將和其它局中人的信道會(huì)產(chǎn)生重疊，這樣通過(guò)效用函數(shù)可以得到局中人信道因?yàn)橹丿B，效用將變?yōu)?。而如果它降低自己的信道帶寬，它的效用將減少。而對(duì)自私主體而言是不會(huì)自己減少信道頻譜的。故上面的策略是對(duì)局中人而言的一種純納什均衡。

（2）Di＝λBi，且chi∪chj（ j≠i）。（條件2）

假設(shè)局中人i（i∈ ｛1，2，…，N ｝）滿足 （條件2），局中人i因?yàn)樗男枨笠呀?jīng)全部都滿足了，它的效用已經(jīng)是最大的了，所以不可能通過(guò)單方面偏離來(lái)增加他的效用。

故以上策略組合中，沒(méi)有局中人有單方面偏離策略組合的動(dòng)機(jī)，由純納什均衡的定義可知這種策略組合就是純納什均衡。

2.2 系統(tǒng)最優(yōu)

證明：納什均衡符合 （條件1）意味著若一個(gè)局中人為了提高效用，必須擴(kuò)大帶寬，但由于所有頻譜均被使用故該局中人必然會(huì)占用別人的帶寬，且由于信道不能被重疊，否則效用為0，就必然使得其它的局中人減少帶寬，導(dǎo)致其它局中人效用降低。即得證在不使其它任何人境況變壞的情況下，這個(gè)局中人不可能提高自己效用，可知該策略組合是帕累托最優(yōu)［7］。

納什均衡符合 （條件1）意味著所有的頻譜被局中人使用，并且局中人的帶寬總和也達(dá)到策略最大值。且V （·）和C（·）是線性函數(shù)，由UFi可知系統(tǒng)效用依靠局中人帶寬。因此該純納什均衡滿足 （條件1）即是系統(tǒng)效用最大化而且是系統(tǒng)最優(yōu)的。

證明：由于每個(gè)局中人i帶寬已經(jīng)是滿足最大了，不會(huì)發(fā)生偏離，更不會(huì)改變其它局中人的策略，這種策略下已是帕累托最優(yōu)了。

由效用函數(shù)可知由于擴(kuò)大信道帶寬將會(huì)減少局中人i的效用，此時(shí)每個(gè)局中人i帶寬已經(jīng)是滿足最大了，因此局中人i不再有擴(kuò)大信道帶寬的動(dòng)機(jī)，且V （·）和C（·）是線性函數(shù)可知已經(jīng)是最大化系統(tǒng)效用。因此這個(gè)純納什均衡策略組合，是帕累托最優(yōu)和系統(tǒng)最優(yōu)。

2.3 系統(tǒng)公平性

在前面提出的兩個(gè)純納什均衡策略中局中人當(dāng)且僅當(dāng) i，j，Bi／Di＝Bj／Dj這個(gè)純納什均衡才是公平的。使用Jains公平指數(shù)來(lái)量化研究客戶的公平性。其中M是無(wú)線局域網(wǎng)的客戶總數(shù)，Ci是接入點(diǎn)i吞吐量或獲得的帶寬。分配給不同接入點(diǎn)的帶寬是根據(jù)接入點(diǎn)從相關(guān)聯(lián)的客戶端獲取通信需求函數(shù)［8－9］。

3 公平的信道分配算法

在證明了穩(wěn)定的，系統(tǒng)最優(yōu)的公平分配存在基礎(chǔ)上提出一個(gè)為接入點(diǎn)實(shí)現(xiàn)理想的公平分配的算法。每一個(gè)接入點(diǎn)廣播其通信需求總量 （客戶端數(shù)目）并且其ID經(jīng)主干網(wǎng)傳送。每一個(gè)接入點(diǎn)選擇其相應(yīng)頻譜間隔和相應(yīng)的信道。定義兩個(gè)正常數(shù)：B和T （T＞B）。在協(xié)議中，所有認(rèn)知主體使用兩個(gè)計(jì)數(shù)器：反向讀數(shù)器和階段計(jì)數(shù)器。所有局中人在每一個(gè)固定間隔，階段計(jì)數(shù)器要減1。

（1）每個(gè)局中人的階段計(jì)數(shù)器設(shè)置為T，每個(gè)接入點(diǎn)從集合 （0，B］中隨機(jī)選擇一個(gè)值作為其反向計(jì)數(shù)器的初始值，然后每一個(gè)接入點(diǎn)的兩個(gè)計(jì)數(shù)器開(kāi)始計(jì)數(shù)。當(dāng)反向計(jì)數(shù)器減至0，接入點(diǎn)廣播其通信需求總量 （客戶端數(shù)目）并且其ID經(jīng)主干網(wǎng)傳送。所有其它的接入點(diǎn)都要記錄下。

（2）當(dāng)階段讀數(shù)器T減至0，這時(shí)每一個(gè)接入點(diǎn)都已經(jīng)廣播其通信需求總量 （客戶端數(shù)目），并且知道了其它接入點(diǎn)通信需求，這是一個(gè)完全信息靜態(tài)博弈。按照前面討論的帕累托最優(yōu)和系統(tǒng)最優(yōu)且公平的方式分配給自己一個(gè)區(qū)間頻率和信道。為了論文的簡(jiǎn)明起見(jiàn)，把所有的接入點(diǎn)根據(jù)通信需求按升序排列，并且用接入點(diǎn)APj（j∈ ｛1，2，…，N｝）來(lái)表示。而如果兩個(gè)或兩個(gè)以上接入點(diǎn)的通信需求是一樣的，那么就根據(jù)它們的ID升序排列。這樣，頻率間隔FPj就能被分配給APj。Min＋（Max－Min）·

用 ［fpminj，fpmaxj］表示CHj，這樣，APj可以按如下方式選擇信道：

以上分配方案，方式一在調(diào)整λ后按照方式二進(jìn)行頻譜分配依然是純納什均衡的。因論文篇幅所限，省略證明。故實(shí)際上整個(gè)頻譜均按照方式二進(jìn)行分配。

以上分配方式是整個(gè)網(wǎng)絡(luò)沒(méi)有異常中斷情況下進(jìn)行的，顯然這是不穩(wěn)定的。引入一個(gè)buffer，T計(jì)數(shù)器每次計(jì)數(shù)到0時(shí)，完成頻譜分配后，把這個(gè)分配情況備份到buffer中，以便如果網(wǎng)絡(luò)發(fā)生異常，接下來(lái)的一個(gè)階段的帶寬分配情況參照buffer的值進(jìn)行認(rèn)知。

4 數(shù)據(jù)仿真與分析

本節(jié)通過(guò)仿真實(shí)驗(yàn)數(shù)據(jù)來(lái)評(píng)估提出的頻譜分配算法，例如參照文獻(xiàn) ［8－9］選取開(kāi)放頻譜2.4GHz的ISM波段中的一段。假設(shè)1 MHz頻譜的速率是1.2Mbps［8－9］，預(yù)設(shè)條件如下：無(wú)線局域網(wǎng)絡(luò)中最多12個(gè)接入點(diǎn)，可分配頻譜范圍是86MHz，為仿真簡(jiǎn)化，假設(shè)C（·）和帶寬相當(dāng)。

本次仿真在單階段下進(jìn)行，數(shù)據(jù)如表1所示。

表1 單階段仿真數(shù)據(jù)

在該仿真數(shù)據(jù)，Si表示為每一個(gè)模擬方案，Si的AP集為 ｛AP1，AP2，…，AP2i｝，i∈ ｛1，2，3，4，5，6｝，設(shè)定λ＝1／2。每個(gè)接入點(diǎn)的通信需求 （MHz）為客戶數(shù)量／λ。由于每個(gè)接入點(diǎn)AP是理性的，故APj（實(shí)際分配給接入點(diǎn)AP的帶寬）不會(huì)超過(guò)Dj／λ。

用Jains指數(shù)，來(lái)評(píng)估每個(gè)客戶的公平性。其中包含3種分配方案：

（1）公平的納什均衡；

（2）不公平的納什均衡；

（3）固定帶寬分配，在所有帶寬分配中，所有AP不管他的需求平均分配信道寬度。

仿真結(jié)果顯示如圖1所示。

圖1 公平性

從數(shù)據(jù)結(jié)果可以看出，公平性模擬方案中純納什均衡分配的公平指數(shù)總是1（根據(jù)前面Jains公平指數(shù)計(jì)算出），固定帶寬分配和不公平的納什分配公平指數(shù)都較低。

單階段系統(tǒng)效用的仿真數(shù)據(jù)也采用3種方式進(jìn)行相互對(duì)比，如下所示：

（1）公平的純納什均衡；

（2）不公平的納什均衡；

（3）固定帶寬分配。

圖2 系統(tǒng)效用

仿真結(jié)果如圖2所示。在單階段無(wú)違規(guī)情況下，純納什均衡的可變帶寬分配的整個(gè)系統(tǒng)利用率要明顯比固定帶寬來(lái)得高一些。因此，純納什均衡的可變分配比其它兩種分配能更高的提高系統(tǒng)效用。

5 結(jié)束語(yǔ)

本文研究了單碰撞域中，自私接入點(diǎn)的非重疊可變信道帶寬分配問(wèn)題。在給出的實(shí)用系統(tǒng)模型上，首先證明了公平的、系統(tǒng)最優(yōu)的納什均衡頻譜分配的存在，繼而提出了實(shí)現(xiàn)這個(gè)分配的算法，最后通過(guò)仿真實(shí)驗(yàn)的結(jié)果數(shù)據(jù)證明本文所設(shè)計(jì)的算法是符合實(shí)際行之有效的。但在實(shí)際運(yùn)用中要比實(shí)驗(yàn)環(huán)境的情況復(fù)雜一些，例如接入點(diǎn)設(shè)備收到的噪聲干擾，無(wú)線環(huán)境下博弈是多階段的，必然有接入點(diǎn)為獲得更多帶寬而提出虛假的客戶數(shù)量信息，如何在多階段博弈執(zhí)行過(guò)程中對(duì)違規(guī)的局中人進(jìn)行處罰已經(jīng)阻止局中人有違規(guī)動(dòng)機(jī)等，這有待于進(jìn)一步的研究。

［1］Akyildiz I F，Lee W，Vuran M C，et al.Next generation dynamic spectrum access cognitive radio wireless networks：a survey ［C］.Elsevier Computer Networks，2006：2127－2159.

［2］Yuan Y，Bahl P，Chandra R，et al.KNOWS：kognitive networking over whitesp aces ［C］.Proc of IEEE Dyspan，2007：416－427.

［3］Bahl P，Chandra R，Moscibroda T，et al.Load aware channel－width assignments in wireless LANs ［R］.Microsoft Research Technical Report，2007.

［4］Yuan Y.Enabling dynamic spectrum allocation in cognitive radio networks［D］.University of Maryland，2007.

［5］Felegyhazi M，Cagalj M，Bidokhti S S，et al.Non－cooperative multi－radio channel allocation in wireless networks ［C］.Anchorage，Alaska，USA：INFOCOM，2007：1442－1450.

［6］MacKenzie A B，Dasilva L，TranterW.Game theory for wireless engineers［M］.Morgan and Claypool Publishers，2006.

［7］ZHANG Ye，GONG Xiaofeng.Game theory method for cognitive radio spectrum allocation ［J］.Communication Technology，2009，42 （6）：5－7.

［8］Chandra R，Mahajan R，Moscibroda T，et al.A case for adapting channel width in wireless networks ［C］.Seattle，Washington，USA：SIGCOMM’08，2008：135－146.

［9］Huang J，Berry R，Honig M.Distributed interference compensation for wireless networks ［J］.IEEE J Select Areas Commun，2006，24 （5）：1074－1084.

［10］DelRe E，Argenti F，Ronga L S，et al.Power allocation strategy for cognitive radio terminals ［C］.Aalborg，Denmark：First International Workshop on Proc Cognitive Radio and Advanced Spectrum Management，2008：1－5.

［11］Keshavamurthy S，Chandra K.Multiplexing analysis for spectrum sharing ［C］.Washington，DC：Proc IEEE MILCOMM’06，2006.

［12］Han Z，Ji Z，Liu K J R.A cartel maintenance framework to enforce cooperation in wireless networks with sefish users［J］.IEEE Trans Wireless Commun，Special Issue on Cooperative Communications，2008，7 （5）：1889－1899.

［13］Neel J.Analysis and design of cognitive radio networks and distributed radio resource management algorithms［D］.Ph D Dissertation，Virginia Polytechnic Institute and State University，2006.

［14］Nie N，Comaniciu C.Adaptive channel allocation spectrum etiquette for cognitive radio networks［C］.Baltimore，MD：Proc of First IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks，2005：269－278.

［15］Bloem M，Alpcan T，Basar T.A stackelberg game for power control and channel allocation in cognitive radio networks ［C］.Nantes，F(xiàn)rance：Proc of 2nd International Conference on Performance Evaluation Methodologies and Tools，2007.