一種基于博弈論的無(wú)線網(wǎng)狀網(wǎng)絡(luò)信道分配算法

鄭鵬宇，何世彪，張馨月，黃 帥

(1.重慶通信學(xué)院，重慶 400035;2.中國(guó)煙草總公司重慶市公司石柱分公司，重慶 409100)

無(wú)線網(wǎng)狀網(wǎng)(wireless mesh network，WMN)是由組織成網(wǎng)狀的無(wú)線節(jié)點(diǎn)構(gòu)成的通信網(wǎng)絡(luò)，具有自組織、自配置、低開銷、自愈性以及高帶寬等優(yōu)點(diǎn)。鑒于這些優(yōu)點(diǎn)，WMN具有許多重要的商業(yè)應(yīng)用，如“社會(huì)無(wú)線網(wǎng)絡(luò)”“應(yīng)急通信”等。

現(xiàn)在研究的熱點(diǎn)集中于多天線多信道(multi-radio multi-channel，MRMC)WMN網(wǎng)絡(luò)上。多天線多信道無(wú)線Mesh網(wǎng)絡(luò)是由若干配置了多個(gè)IEEE802.11 標(biāo)準(zhǔn)天線［1-3］的網(wǎng)狀節(jié)點(diǎn)構(gòu)成的，在MRMC網(wǎng)絡(luò)中節(jié)點(diǎn)可以和鄰居同時(shí)發(fā)送和接收數(shù)據(jù)。

影響MRMC網(wǎng)絡(luò)性能的因素主要是同信道間的干擾。這種干擾產(chǎn)生的主要原因是鄰近節(jié)點(diǎn)在同一時(shí)間內(nèi)使用相同的信道傳輸。信道分配的目的就在于通過(guò)將可用的正交信道分配至每一條鏈路，在保證鏈接的條件下，使得干擾最小。

本文采用博弈論的方法來(lái)解決無(wú)線Mesh網(wǎng)絡(luò)中信道分配的問(wèn)題。博弈論主要研究多個(gè)自主實(shí)體之間為了達(dá)到某種目的而相互作用的輸出結(jié)果。而無(wú)線Mesh是一個(gè)分布式、自組織以及自配置的網(wǎng)絡(luò)，這些特點(diǎn)就使得每個(gè)分布式的節(jié)點(diǎn)都可以被視為一個(gè)自主實(shí)體，這樣博弈論就非常適合于解決無(wú)線Mesh網(wǎng)絡(luò)中信道分配的問(wèn)題。

本文提出了一種基于博弈論的無(wú)線Mesh網(wǎng)絡(luò)信道分配算法。

1 無(wú)線傳播和干擾模型

在理論分析當(dāng)中，通常使用的傳播模型為圓盤傳播模型(two-ray ground模型)，該模型可以描述節(jié)點(diǎn)的信號(hào)傳輸范圍和載波偵聽的范圍(干擾距離)。用Rt表示數(shù)據(jù)最大傳輸距離，Ri表示載波偵聽距離，其關(guān)系為Ri=qRt(q≥2)。

無(wú)線信道的廣播特性導(dǎo)致了同信道鄰近節(jié)點(diǎn)之間的干擾。文獻(xiàn)［4］總結(jié)出了3種干擾模型:PCA(primary conflict avoidance)、RCA(receiver conflict avoidance)和TRCA(transmitter-receiver conflict avoidance)，其中TRCA是最為嚴(yán)格的干擾模型，在干擾范圍內(nèi)所有的節(jié)點(diǎn)都無(wú)法通信。

在如圖1所示的圓盤傳播模型(q=2)和TRCA干擾模型中，任意一對(duì)接點(diǎn)通信時(shí)會(huì)對(duì)同信道的鄰近節(jié)點(diǎn)造成干擾。圖1中，節(jié)點(diǎn)A和節(jié)點(diǎn)B通信時(shí)會(huì)對(duì)周圍16個(gè)節(jié)點(diǎn)造成干擾，因此，單信道網(wǎng)絡(luò)的通信效率很低。圖1中還顯示，在同一信道下，節(jié)點(diǎn)C和節(jié)點(diǎn)D通信必須和使用相同信道通信的節(jié)點(diǎn)A和B相隔3倍Rt才不會(huì)產(chǎn)生干擾。

圖1 TRCA干擾模型和Two-ray Ground傳播模型

2 博弈論建模

2.1 博弈論模型

利用博弈論對(duì)無(wú)線Mesh網(wǎng)絡(luò)進(jìn)行研究，其中的關(guān)鍵是如何將博弈論引入到相應(yīng)算法的設(shè)計(jì)與分析之中，找到算法的納什均衡點(diǎn)［5］。因此，在利用博弈論信道分配問(wèn)題之前，首先將所研究的問(wèn)題抽象成博弈論問(wèn)題模型，無(wú)線Mesh網(wǎng)絡(luò)中的頻譜分配問(wèn)題是關(guān)系到各節(jié)點(diǎn)頻譜選擇的博弈過(guò)程。假設(shè)把頻譜的分配等同于信道的分配，即信道分配問(wèn)題可以建模成一個(gè)博弈輸出。在這個(gè)博弈過(guò)程中，無(wú)線Mesh網(wǎng)絡(luò)中的節(jié)點(diǎn)可視為參與者，對(duì)于傳輸信道的選擇就是行動(dòng)策略，且參與者的效用與所選擇的信道相關(guān)聯(lián)。那么，頻譜分配問(wèn)題的博弈論數(shù)學(xué)描述的一般形式為

其中:N是參與者(選擇某個(gè)信道傳輸數(shù)據(jù)的無(wú)線Mesh節(jié)點(diǎn))的有限集;Si是相對(duì)于參與者i的策略集，定義S= ×Si，i∈N是策略空間，則Ui:S→R是效用函數(shù)集。在博弈中效用函數(shù)Ui是參與者i選擇策略si和其對(duì)手所選策略s-i的函數(shù)。

博弈論分析的關(guān)鍵問(wèn)題之一是判斷對(duì)于自適應(yīng)的信道分配算法是否存在收斂點(diǎn)，且這個(gè)收斂點(diǎn)對(duì)于任何用戶都不會(huì)偏移，也就是納什均衡。因此，對(duì)于參與者的一組策略，S={s1，s2，…，sN}，當(dāng)且僅當(dāng) Ui(S)≥Ui(s'i，s-i)，?i∈N，s'i∈Si時(shí)，這組策略是納什均衡。

2.2 效用函數(shù)的確定

通過(guò)為每條鏈路合理地分配信道來(lái)達(dá)到最大化網(wǎng)絡(luò)信噪比的目的。而鏈路能否成功傳輸數(shù)據(jù)與網(wǎng)絡(luò)中的干擾有著密切的聯(lián)系，即與信噪比SINR有關(guān)。因此，在接收端j關(guān)于發(fā)射端i的信噪比記為SINRre，表達(dá)式為

式中:pi是發(fā)射端i的發(fā)射功率;Gij為發(fā)射端i到接收端j的鏈路增益;Δ 是背景噪聲［6］;f(k，j)是表示由節(jié)點(diǎn)k到接收端j的干擾方程，其表達(dá)式為

可見WMN網(wǎng)絡(luò)中總干擾最小就是使得網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)所受到的干擾最小，但節(jié)點(diǎn)之間在相同頻譜上的干擾又是相互的，這也正符合了博弈論研究問(wèn)題的特征。

在通常情況下，參與者i能夠通過(guò)感知在某個(gè)特定信道上的干擾來(lái)選取最佳的信道傳輸數(shù)據(jù)。另一方面，由于網(wǎng)絡(luò)中參與者之間的干擾是相互的，參與者i所選取的對(duì)自身干擾最小的信道并不能保證其對(duì)鄰近的參與者也是最小的，同時(shí)不能保證整個(gè)網(wǎng)絡(luò)的總干擾水平最小。因此，還必須保證參與者i所選取的信道對(duì)于其他鄰近參與者的干擾最小。定義參與者i效用函數(shù)表達(dá)式為

干擾方程為

式(4)、(5)中:P={p1，p2，…，pN}是 WMN 網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的發(fā)射功率集合(N為節(jié)點(diǎn)數(shù));S={s1，s2，…，sM}是策略集(M為正交信道數(shù)量)。式(4)中:第1部分是參與者i受到其鄰近參與者在相應(yīng)信道上的干擾，記為Iid;第2部分為參與者在相應(yīng)信道上對(duì)其他鄰近參與者的干擾，記為Iod。

則效用函數(shù)ui的另一種表達(dá)方式為

其中:Iid在接收端測(cè)量得到;Iod在發(fā)射端計(jì)算得出。雖然在采用ui的情況下，算法需要在公共信道上使用一個(gè)數(shù)據(jù)包來(lái)傳遞參與者對(duì)鄰近節(jié)點(diǎn)干擾的測(cè)量信息，算法的復(fù)雜度會(huì)增加，但是效用函數(shù)的設(shè)計(jì)的確能滿足最小化系統(tǒng)總干擾水平的目標(biāo)要求。

位勢(shì)博弈的特性是博弈中存在一個(gè)位勢(shì)函數(shù)，該函數(shù)可以準(zhǔn)確地反映任何參與者的效用函數(shù)中產(chǎn)生的單方面變化［7］。這個(gè)位勢(shì)函數(shù)代替了具體的博弈效用函數(shù)反映效用的改善信息。一個(gè)確定的位勢(shì)函數(shù)P定義為:

定義1 若存在一個(gè)函數(shù)，對(duì)所有的i和si，si'∈Si有這樣的性質(zhì):

則稱該函數(shù)為位勢(shì)函數(shù)。

通過(guò)計(jì)算，對(duì)于效用函數(shù)ui的信道分配博弈，一個(gè)確定的位勢(shì)函數(shù)為

即

具體證明參照文獻(xiàn)［8］。

3 算法實(shí)現(xiàn)以及算法改進(jìn)

3.1 算法實(shí)現(xiàn)及過(guò)程

因?yàn)樗惴ǖ膶?shí)現(xiàn)需要接收端和發(fā)送端在一條公共信道上傳輸信令，因此設(shè)計(jì)一個(gè)3次握手機(jī)制的握手協(xié)議。

借鑒使用與IEEE802.11協(xié)議中的RTS-CTS交換協(xié)議相類似的協(xié)議，其中規(guī)定信令協(xié)議包如表1所示。

信令協(xié)議中的信令數(shù)據(jù)包主要起2個(gè)方面的作用:①測(cè)量各傳輸信道的干擾量，計(jì)算效用函數(shù);②廣播節(jié)點(diǎn)對(duì)于某條信道的使用情況。每個(gè)節(jié)點(diǎn)的接收端和發(fā)射端均保存一個(gè)信道狀態(tài)表(CST)，用于記錄各信道被其他節(jié)點(diǎn)占用的情況和儲(chǔ)存數(shù)據(jù)流的目的節(jié)點(diǎn)和下一跳節(jié)點(diǎn)的信息。一旦用戶偵聽到公共信道中相應(yīng)信道的信令數(shù)據(jù)包，則更新自身發(fā)送端和接收端的CST，以便掌握其他節(jié)點(diǎn)的信息。

表1 信令協(xié)議中數(shù)據(jù)包功能

算法的偽代碼見算法1。

算法1資源分配算法

3.2 算法改進(jìn)

雖然效用函數(shù)ui能實(shí)現(xiàn)系統(tǒng)的效用函數(shù)最大化，但是這種系統(tǒng)級(jí)的性能優(yōu)化沒(méi)有考慮到不同節(jié)點(diǎn)的業(yè)務(wù)需求，忽略了個(gè)性化的QoS需求和公平性。系統(tǒng)資源可能被少數(shù)節(jié)點(diǎn)占用，使其超過(guò)業(yè)務(wù)QoS需要的資源，而相當(dāng)一部分節(jié)點(diǎn)占用的資源無(wú)法保證其業(yè)務(wù)最低的QoS要求。因此，需要對(duì)效用函數(shù)U進(jìn)行必要的修正。

根據(jù)參考文獻(xiàn)［7］的算法，引入功率調(diào)整方法，研究一種滿足業(yè)務(wù)需求的分布式動(dòng)態(tài)分配方案。每個(gè)節(jié)點(diǎn)根據(jù)自己的QoS需求和本地信息進(jìn)行分布式信道選擇和功率控制。本算法采用SINR來(lái)量化業(yè)務(wù)的QoS需求，既有:

在式(4)的基礎(chǔ)上對(duì)系統(tǒng)的目標(biāo)進(jìn)行擴(kuò)展，可表示為

式(13)所示算法分為2個(gè)階段來(lái)實(shí)現(xiàn):第1階段為信道分配，即每個(gè)用戶通過(guò)博弈算法選擇信道;第2階段為功率調(diào)整，即在第1階段結(jié)果的基礎(chǔ)上，根據(jù)用戶的QoS需求進(jìn)行功率調(diào)整。

第2階段的具體步驟:

根據(jù)第1階段的分配結(jié)果，計(jì)算業(yè)務(wù)的信噪比SINR并調(diào)整功率，調(diào)整策略包括3種:

1)若 SINRi，min≤SINRi≤SINRi，max保持第 1 階段的發(fā)射功率不變。

2)若 SINRi＜SINRi，min則用戶需要增加自身發(fā)射功率，使得滿足最小SINR要求，有2種情況:①若不存在使得，則關(guān)閉節(jié)點(diǎn)i的發(fā)送;②若存在，則

3)若 SINRi≥SINRi，max，則節(jié)點(diǎn) i需要降低發(fā)射功率，使得滿足最大SINR要求，既有SINRi，max，則然后將第2階段的結(jié)果返回第1階段進(jìn)行迭代，直至收斂。

4 算法仿真

在仿真中評(píng)估了算法1和其改進(jìn)算法的性能。網(wǎng)狀節(jié)點(diǎn)隨即分布在一個(gè)區(qū)域?yàn)?00 mm的場(chǎng)景內(nèi)。無(wú)線Mesh網(wǎng)絡(luò)中的節(jié)點(diǎn)使用IEEE802.11b天線，設(shè)計(jì)一個(gè)接收接口和一個(gè)發(fā)送接口，在場(chǎng)景中隨機(jī)分布20到50個(gè)節(jié)點(diǎn)，有一條信道作為公共信道用于傳輸信令數(shù)據(jù)包，可使用的正交信道數(shù)為2到8條，每個(gè)節(jié)點(diǎn)的發(fā)射功率不超過(guò)1 W。使用NS2.34作為仿真工具。

首先計(jì)算位勢(shì)函數(shù)值(圖2)，從中看出算法的收斂情況。當(dāng)節(jié)點(diǎn)數(shù)為50，可用正交信道為4條重復(fù)計(jì)算80次得到2種算法的位勢(shì)函數(shù)。由圖2可以看出2種算法隨著迭代次數(shù)的增加逐漸趨于收斂。算法1在迭代40次后進(jìn)入收斂狀態(tài)，而改進(jìn)算法在迭代67次后才趨于收斂。由圖2可知2種算法在前40次迭代中的位勢(shì)函數(shù)值是相同的，但改進(jìn)算法在達(dá)到算法1達(dá)到收斂之后還將繼續(xù)判斷各節(jié)點(diǎn)的SINR值是否滿足用戶需求，所以導(dǎo)致改進(jìn)算法需要更多的迭代次數(shù)才能達(dá)到收斂。

圖2 2種算法位勢(shì)函數(shù)收斂狀況比較

從圖3中可以看出:①在不同信道數(shù)量的情況下2種算法的收斂速度都是很快的，但是改進(jìn)算法的收斂速度要慢于算法1。②當(dāng)信道數(shù)量較少時(shí)，算法的收斂次數(shù)是增加的，這是因?yàn)樵诳捎眯诺罃?shù)較小的情況下網(wǎng)絡(luò)中節(jié)點(diǎn)會(huì)頻繁的切換信道;而當(dāng)可用信道比較多時(shí)，2種算法的迭代至收斂的次數(shù)都會(huì)逐漸減小，這是因?yàn)樵谛诺垒^多的情況下節(jié)點(diǎn)的信道選擇會(huì)較快地達(dá)到穩(wěn)定狀態(tài)并保持在這一狀態(tài)。

圖3 2種算法的位勢(shì)函數(shù)在不同信道數(shù)量下收斂狀況的比較

圖4和圖5分別描述了2種算法的網(wǎng)絡(luò)性能。圖4為2種算法的系統(tǒng)吞吐量隨著節(jié)點(diǎn)數(shù)量變換的結(jié)果，可以看出:系統(tǒng)吞吐量隨著節(jié)點(diǎn)數(shù)量的增加而增加，且改進(jìn)算法的系統(tǒng)吞吐量的變化幅度較大;在節(jié)點(diǎn)數(shù)比較少的情況下，算法1的系統(tǒng)吞吐量較大，但當(dāng)節(jié)點(diǎn)數(shù)增多至30個(gè)以上是，改進(jìn)算法的系統(tǒng)吞吐量變大，即節(jié)點(diǎn)數(shù)越多，改進(jìn)算法的優(yōu)勢(shì)越明顯。而從圖5中可以看出，算法1的信道接入時(shí)延性能要優(yōu)于改進(jìn)算法，這是因?yàn)楦倪M(jìn)算法的復(fù)雜度要高于算法1。

圖4 2種算法的系統(tǒng)吞吐量隨著節(jié)點(diǎn)數(shù)量變化的情況比較

圖5 2種算法的信道接入時(shí)延在不同信道數(shù)量下的變化

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

綜上所述，利用博弈論設(shè)計(jì)無(wú)線Mesh網(wǎng)絡(luò)的信道分配算法是一種行之有效的方法。本文采用博弈論的方法設(shè)計(jì)了一種效用函數(shù)來(lái)實(shí)現(xiàn)最大化網(wǎng)絡(luò)信噪比的目的，并通過(guò)改變各節(jié)點(diǎn)發(fā)射功率的大小來(lái)提高個(gè)節(jié)點(diǎn)的QoS，使得網(wǎng)絡(luò)資源能得到更為合理的利用。

［1］Akyildiz I，Wang X.A survey on wireless mesh networks［J］.IEEE Communications Magazine，2005，43(9)：23-30.

［2］Bruno R，Conti M，Gregori E.Mesh networks：commodity multi-hop ad hoc networks［J］.IEEE Communications Magazine，2005，43(3)：123-131.

［3］Audhya G K，Sinha K，Ghosh S C，et al.A survey on the channel assignment problem in wireless networks［J］.Wireless Communications and Mobile Computing，2011，11(5)：583-609.

［4］Kodialam M ，Nandagopai T.The effect of interference on the capacity of multi-hop wireless networks［M］.Chicago，IEEE Symposium on Information Theory，2004：470-479.

［5］Singh M，Saxena A.Secure computation for data privacy［C］//Proc SECCOM 07.Nice：［s.n.］，2007：58-62.

［6］Blough D，Resta G，Santi P.Approximation algorithms for wireless link scheduling with SINR-based interference［J］.IEEE/ACM Transactions on Networking(TON)，2010，18(6)：1701-1712.

［7］Mondere D，Shapley L.Potential Games and Economic［J］.Behavior，1996，14：124-143.

［8］Yu Q，Chen J，F(xiàn)an Y，et al.Multi-channel assignment in wireless sensor networks：A game theoretic approach［C］//Proc of INFOCOM 10.San Diego：IEEE，2010：1-9.