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

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

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

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

現(xiàn)在研究的熱點(diǎn)集中于多天線多信道(multi-radio multi-channel，MRMC)WMN網(wǎng)絡(luò)上。多天線多信道無線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)使用相同的信道傳輸。信道分配的目的就在于通過將可用的正交信道分配至每一條鏈路，在保證鏈接的條件下，使得干擾最小。

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

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

1 無線傳播和干擾模型

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

無線信道的廣播特性導(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)都無法通信。

在如圖1所示的圓盤傳播模型(q=2)和TRCA干擾模型中，任意一對接點(diǎn)通信時(shí)會(huì)對同信道的鄰近節(jié)點(diǎn)造成干擾。圖1中，節(jié)點(diǎn)A和節(jié)點(diǎn)B通信時(shí)會(huì)對周圍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 博弈論模型

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

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

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

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

通過為每條鏈路合理地分配信道來達(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)之間在相同頻譜上的干擾又是相互的，這也正符合了博弈論研究問題的特征。

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

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

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

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

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

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

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

即

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

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

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

因?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è)方面的作用:①測量各傳輸信道的干擾量，計(jì)算效用函數(shù);②廣播節(jié)點(diǎn)對于某條信道的使用情況。每個(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)級的性能優(yōu)化沒有考慮到不同節(jié)點(diǎn)的業(yè)務(wù)需求，忽略了個(gè)性化的QoS需求和公平性。系統(tǒng)資源可能被少數(shù)節(jié)點(diǎn)占用，使其超過業(yè)務(wù)QoS需要的資源，而相當(dāng)一部分節(jié)點(diǎn)占用的資源無法保證其業(yè)務(wù)最低的QoS要求。因此，需要對效用函數(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來量化業(yè)務(wù)的QoS需求，既有:

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

式(13)所示算法分為2個(gè)階段來實(shí)現(xiàn):第1階段為信道分配，即每個(gè)用戶通過博弈算法選擇信道;第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 算法仿真

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

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

圖2 2種算法位勢函數(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ù)量下收斂狀況的比較

圖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)勢越明顯。而從圖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é)束語

綜上所述，利用博弈論設(shè)計(jì)無線Mesh網(wǎng)絡(luò)的信道分配算法是一種行之有效的方法。本文采用博弈論的方法設(shè)計(jì)了一種效用函數(shù)來實(shí)現(xiàn)最大化網(wǎng)絡(luò)信噪比的目的，并通過改變各節(jié)點(diǎn)發(fā)射功率的大小來提高個(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.