殷昌盛

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

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

0引言

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

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

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

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

2.1信道分配博弈模型

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

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

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

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

2.3基本算法步驟

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

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

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

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

3仿真與分析

使用NS-2 2.33仿真軟件，基于802.11a/g的多接口無(wú)線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ā)送功率，因此其信號(hào)傳輸范圍為125m，載波偵聽(tīng)范圍為220m。同時(shí)，傳輸采用RTS/CTS四路握手機(jī)制。網(wǎng)絡(luò)結(jié)構(gòu)為設(shè)置為的網(wǎng)格狀網(wǎng)絡(luò)，m取值從2到6，節(jié)點(diǎn)間距離100m。每個(gè)節(jié)點(diǎn)擁有兩個(gè)接口，可使用的正交信道數(shù)為2到8條。

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

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

4結(jié)語(yǔ)

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