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

殷昌盛

摘要：為解決無線Mesh網(wǎng)絡(luò)中的信道分配問題，提出了基于博弈論的信道分配（GBCA）算法。該算法將無線Mesh網(wǎng)中各節(jié)點(diǎn)的信道分配過程作為一個博弈過程，信道分配策略作為博弈者的策略選擇，信噪比函數(shù)為博弈的效用函數(shù)?；贜S2的仿真結(jié)果表明該算法在吞吐量和丟包率方面都有較好的性能。

關(guān)鍵詞：無線Mesh網(wǎng)；信道分配；博弈論

0引言

無線Mesh網(wǎng)（WMN，Wireless Mesh Network）是一種由Mesh路由器和Mesh終端組成的多跳無線網(wǎng)絡(luò)，具有傳輸速率高、覆蓋范圍廣和組網(wǎng)成本低等優(yōu)點(diǎn)，是解決無線終端接入Internet的一種比較有競爭力的技術(shù)方案。多信道Mesh雖能提高無線Mesh網(wǎng)絡(luò)容量，但合理的信道分配至關(guān)重要。

無線Mesh網(wǎng)作為一種可自組織和自管理的無線網(wǎng)絡(luò)架構(gòu)，其個節(jié)點(diǎn)節(jié)點(diǎn)可自行組網(wǎng)，并競爭接入信道。在這種網(wǎng)絡(luò)中，節(jié)點(diǎn)具有一定的自私性，之間是相互競爭資源又相互依賴的關(guān)系，其正與博弈論的思想有著非常大的相似性?；谏鲜隹紤]，本文提出了一種基于博弈論的信道分配（Gamebased channel assignment，GBCA）算法。將無線Mesh網(wǎng)中各節(jié)點(diǎn)的信道分配過程作為一個博弈過程，信道分配策略作為博弈者的策略選擇，信噪比函數(shù)為博弈的效用函數(shù)，通過最大化網(wǎng)絡(luò)信噪比進(jìn)行信道分配。

2系統(tǒng)模型構(gòu)建

利用博弈論對無線Mesh網(wǎng)絡(luò)進(jìn)行研究，其中的關(guān)鍵是如何將博弈論引入到相應(yīng)算法的設(shè)計與分析之中，找到算法的納什均衡點(diǎn)。即無線Mesh網(wǎng)絡(luò)中的頻譜分配問題是各節(jié)點(diǎn)頻譜選擇的博弈過程，將所研究的問題抽象成博弈論問題模型。

2.1信道分配博弈模型

將無線Mesh網(wǎng)中各節(jié)點(diǎn)的信道分配過程作為一個博弈過程，信道分配策略作為博弈者的策略選擇，信噪比函數(shù)為博弈的效用函數(shù)，通過最大化網(wǎng)絡(luò)信噪比進(jìn)行信道分配。

接收節(jié)點(diǎn)的信噪比（SINR）決定著該接收鏈路能否成功傳輸，從而影響網(wǎng)絡(luò)性能，所以本文以最大化網(wǎng)絡(luò)信噪比為目的進(jìn)行信道分配。鏈路中節(jié)點(diǎn)j處信噪比可表示為：

而為使網(wǎng)絡(luò)中總體干擾最小，只需要使每個節(jié)點(diǎn)所受到的干擾最小即可。同時，在無線WMNs中各節(jié)點(diǎn)在相同的信道上時，其干擾時相互的，這正與博弈論研究特征相符合。然而，由于Mesh網(wǎng)的網(wǎng)狀特點(diǎn)，任何一個節(jié)點(diǎn)，或說是博弈者，其所選擇的對于自身干擾最小的信道也許會對其鄰近節(jié)點(diǎn)造成很大的干擾，從而與網(wǎng)絡(luò)總體干擾最小化矛盾。因此，在確定博弈者的效用函數(shù)時，應(yīng)該同時考慮被干擾與干擾聯(lián)合最小化問題。所以，可以定義博弈者i的效用函數(shù)表達(dá)式為：

所以滿足潛在博弈函數(shù)條件，所以本文的博弈模型總會收斂于一個納什均衡。證畢。

2.3基本算法步驟

綜合以上分析，我們可以得出該博弈算法是一個收斂的重復(fù)博弈。在每次博弈循環(huán)中，每個Mesh節(jié)點(diǎn)i根據(jù)a_i來選擇策略u_a從而實(shí)現(xiàn)提高效用函數(shù)u（a）。如果可以因節(jié)點(diǎn)的策略的改變而提高，則節(jié)點(diǎn)策略改變，同時博弈過程進(jìn)入新一輪循環(huán)。同時，為了防止博弈效用函數(shù)的震蕩，規(guī)定同一時間內(nèi)只允許一個節(jié)點(diǎn)改變，所有節(jié)點(diǎn)依次進(jìn)行此操作從而達(dá)到NE。其基本算法步驟如下：

（1）初始化：隨機(jī)為N個Mesh節(jié)點(diǎn)用戶分配信道和發(fā)射功率。所有節(jié)點(diǎn)的策略組合即是整個網(wǎng)絡(luò)的初始信道分配策略，可記為A⁰。

（2）迭代過程：節(jié)點(diǎn)用戶按照接入網(wǎng)絡(luò)的先后順序依次進(jìn)行博弈，即每個節(jié)點(diǎn)依次選擇使得效用函數(shù)最大的策略，繼而更新整個網(wǎng)絡(luò)策略A^*。

（3）終止過程：重復(fù)迭代過程，直至算法收斂。

3仿真與分析

使用NS-2 2.33仿真軟件，基于802.11a/g的多接口無線Mesh網(wǎng)絡(luò)進(jìn)行了流量仿真實(shí)驗(yàn)。在收斂速率、網(wǎng)絡(luò)吞吐量與丟包率等方面與RCA、J-CAR算法進(jìn)行了比較與分析。

其中傳播模型采用圓盤傳播模型（two-ray ground模型），采用系統(tǒng)默認(rèn)發(fā)送功率，因此其信號傳輸范圍為125m，載波偵聽范圍為220m。同時，傳輸采用RTS/CTS四路握手機(jī)制。網(wǎng)絡(luò)結(jié)構(gòu)為設(shè)置為的網(wǎng)格狀網(wǎng)絡(luò)，m取值從2到6，節(jié)點(diǎn)間距離100m。每個節(jié)點(diǎn)擁有兩個接口，可使用的正交信道數(shù)為2到8條。

圖1描述了在不同網(wǎng)絡(luò)規(guī)模的情況下4種算法的網(wǎng)絡(luò)吞吐量、丟包率情況，可以看出：本文提出的GBCA算法吞吐量略高于RCA與J-CAR算法，而丟包率較低，這是因?yàn)镴-CAR算法不能適應(yīng)流量的變化，而RCA算法沒有考慮干擾，它們的信道分配結(jié)果有可能會造成較大的干擾。

當(dāng)網(wǎng)絡(luò)吞吐量隨著網(wǎng)絡(luò)規(guī)模的變大有一定的增加，特別是網(wǎng)絡(luò)規(guī)模較小時增幅較為明顯；而當(dāng)規(guī)模繼續(xù)增大時，由于網(wǎng)關(guān)節(jié)點(diǎn)的容量限制，網(wǎng)絡(luò)吞吐量增幅不明顯；另一方面，網(wǎng)絡(luò)規(guī)模較小時，GBCA算法的網(wǎng)絡(luò)吞吐量高于GBCA-PA算法，這是因?yàn)镚BCA算法沒有考慮節(jié)點(diǎn)公平性，犧牲了部分遠(yuǎn)離網(wǎng)關(guān)節(jié)點(diǎn)的Mesh節(jié)點(diǎn)的流量業(yè)務(wù)需求；而網(wǎng)絡(luò)規(guī)模增大時，改進(jìn)算法吞吐率變大，優(yōu)于基本算法，這是因?yàn)槠渫ㄟ^功率控制減小了鏈路之間的干擾。

4結(jié)語

文章根據(jù)博弈論思想與Mesh網(wǎng)多信道分配的特點(diǎn)，將無線Mesh網(wǎng)中的多信道分配問題模型化為一個聯(lián)合博弈（GBCA）。通過證明該模型為潛在博弈以及潛在函數(shù)的存在性，從理論上證明了算法的收斂性；給出了算法的具體實(shí)現(xiàn)，并通過NS-2軟件對算法進(jìn)行了網(wǎng)絡(luò)仿真。仿真結(jié)果表明，利用博弈論設(shè)計一種效用函數(shù)來實(shí)現(xiàn)最大化網(wǎng)絡(luò)信噪比，來解決無線Mesh網(wǎng)絡(luò)中多信道分配是一種行之有效的方法。