李鋮+龍華+李克+蘇坡

【摘要】針對無線Mesh網中信道分配的適應性欠缺的問題，提出了一種基于權重優(yōu)化的信道分配算法。該算法引入損耗因子使每次節(jié)點博弈的權重自動更新，將傳統(tǒng)的靜態(tài)博弈變?yōu)閯討B(tài)博弈，通過非強占優(yōu)先制排隊模型求節(jié)點的優(yōu)先級使得信道分配更加公平。仿真結果表明，該算法在吞吐量和傳輸延時方面有所優(yōu)化，驗證了信道分配的公平性。

【關鍵詞】無線Mesh網博弈論權重公平性

中圖分類號：TP393文獻標識碼：A文章編號：1006-1010(2014)-08-0072-05

Research on WMN Channel Assignment Algorithm Based on Weight Optimization

LI Cheng1, LONG Hua1, LI Ke2, SU Po3

(1. School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China;

2. Zhongyuan Institute of Technology Library, Zhengzhou 450007, China;

3. School of Information Engineering, Changan University, Xian 710064, China)

[Abstract] According to the lack of channel assignment adaptability in wireless Mesh network, a channel assignment algorithm based on weight optimization is proposed. This algorithm introduces the loss factor to make the weight of each node update automatically in the game, which changes the traditional static game to dynamic game. The non-preemptive priority queuing model is adopted to get the priority of node, which makes the channel assignment fairer. The simulation results show that the algorithm has better performance in throughput and propagation delay and the fairness of channel assignment is verified.

[Key words]wireless Mesh networkgame theoryweightfairness

1 引言

隨著無線通信和移動計算的快速發(fā)展，為了滿足人們日益增長的對無線寬帶接入技術的需求，無線Mesh網[1]（WMN，Wireless Mesh Network）作為“最后一公里”的寬帶無線接入關鍵技術已經成為下一代無線寬帶接入研究的熱點。典型的無線Mesh網絡拓撲結構[2]如圖1所示。

其主要包括三類網元：

（1）無線Mesh網關（WMG），用來將無線Mesh網絡接入到Internet中去從而獲取服務；

（2）無線Mesh路由器（WMR），為底層的移動終端提供分組路由和轉發(fā)；

（3）移動終端（MC），即用戶節(jié)點。

信道分配即在網絡中有效地分配有限的無線頻譜資源。由于頻譜資源的有限性，信道分配則考慮如何充分利用這些頻帶資源。在WMN中，信道分配策略要保證有效利用可用信道資源的同時還保持網絡的連通性。公平性是無線Mesh網絡信道分配的重要特性之一。從概率上講，每個WMR得到信道帶寬是相同的，但是由于WMR接入的MC數量不等，某些節(jié)點可能會發(fā)生“餓死”現象，導致分配的不公平。目前WMN中信道分配方案主要集中在IEEE802.11技術的基礎上，針對原有方案的不足作出相應的增強改進，以確保網絡的公平性和資源利用率。

例如：文獻[3]提出的增強型信道分配方法即利用二次貪婪的方式克服了信道分配中的波紋效應，減少了信道間的干擾，但是并未涉及到公平性，也未優(yōu)化網絡的效益；文獻[4]采用協(xié)同博弈的方式將網絡中的每個節(jié)點模型化為一個弈者，每個弈者的策略為與其相關的路由與信道分配方案，收益函數為給定流量需求矩陣下的成功傳輸流量，弈者通過協(xié)同博弈來優(yōu)化收益函數以最大化網絡吞吐量，同時提出了基于博弈論的無線網狀網絡路由與信道分配聯(lián)合優(yōu)化方案，但是沒有考慮信道的公平性分配；文獻[5]采用了傳統(tǒng)的博弈論方法，雖然提升了帶寬公平性，但是同時也以延時的增加為代價；文獻[6]通過檢測子節(jié)點包含的活動終端數量，計算分配指數并發(fā)送給子節(jié)點，使其能根據分配指數調整介質訪問控制層的競爭窗口參數，在子節(jié)點向父節(jié)點發(fā)送數據時，采用加權輪詢調度算法進一步保證帶寬分配的公平性。

本文在已有的工作基礎上提出了一種基于權重優(yōu)化的信道分配算法（BWOCA，Based on Weight Optimization Channel Assignment Algorithm）。首先建立了本算法的網絡模型，分析了節(jié)點競爭無線信道的博弈模型；然后根據流量建立排隊模型，根據節(jié)點負載分析節(jié)點的優(yōu)先級；最后使用MATLAB仿真軟件建立模擬場景，同GBCA算法相比較，結果表明本算法減少了傳輸延時，提高了網絡的吞吐量和信道分配的公平性。

2 模型分析

2.1網絡模型分析

假設無線Mesh網絡的節(jié)點都在同一個平面上，網絡中的干擾包括信道與信道之間的干擾和節(jié)點之間的干擾。設每個節(jié)點的覆蓋范圍為Rcom，干擾范圍為Rinter，Rcom

圖2無線Mesh網絡干擾模型

假設節(jié)點i使用信道c，Inter(i)為i干擾范圍內的節(jié)點集合，則鄰居節(jié)點j干擾模型為：

（1）

假設為獨立事件，則，其中。

2.2信道分配競爭的博弈模型分析

博弈論中主要有三個要素，即參與者、博弈策略和效用函數。在本模型中，可以將信道分配問題看作為非合作博弈。網關WMG負責WMN與外界網絡的通信，而同一時間只能有一個WMR與WMG進行通信，因此對于每個WMR來說彼此都是競爭關系，可以看作是一個博弈的參與者。WMR只有兩種狀態(tài){通信，不通信}，如果沒有或多于兩個WMR選擇通信狀態(tài)時，會發(fā)生沖突而導致通信失??；只有一個WMR處于通信狀態(tài)時，才能成功通信。但是這在實際情況中不存在，每個WMR是以Pi的概率選擇通信的，這需要達到一個納什均衡（NE，Nash Equilibrium）。

以每個WMR選擇信道的概率作為博弈策略，對于節(jié)點i有si={si1,si2,…,sim}種策略可供選擇，每個策略都有相應的效益Ui=Ui(s1,s2,…,sM)，Ui可定義為節(jié)點i選擇某種策略所得到的吞吐量，當滿足Ui(s1,s2,…,sM)≤Ui(s*1,s*2,…,s*M)時，博弈達到納什均衡，其中s*1為使全網達到NE的最優(yōu)策略。

效用函數（Utility Function）的目標在于最大化吞吐量，定義目標函數為：

（2）

其中，Pi(c)為節(jié)點i選擇信道c的概率；fi為節(jié)點i的傳輸流量；Rb為節(jié)點i的實際傳輸率。

2.3流量模型分析

針對WMR的流量分配策略[7]可以用M/G/1非強占優(yōu)先制排隊模型[8]分析。整個無線Mesh網中每個節(jié)點數據到達率λi和處理速率μi服從泊松分布。為了計算效用函數，需要用到端到端延時Wql概率分布。根據M/G/1隊列的性質，Si為節(jié)點i的服務時間，=1/μi，則有：

（3）

其中，。端到端延時Wql由平均服務時間、排隊時間以及前一節(jié)點剩余服務時間構成，即Wql=Ws+Wq+Wo，，Wqi為第i節(jié)點的平均排隊等待時間；，S為系統(tǒng)服務時間；Wo=Wql?？梢缘玫蕉说蕉搜訒rWql的期望為：

（4）

節(jié)點的優(yōu)先級與節(jié)點所選信道的負載、節(jié)點的端口數和最小跳數有關。對優(yōu)先級的判斷首先根據所選信道的負載，節(jié)點所選信道c的負載越大，那么傳輸的需求就越大，優(yōu)先級就高；最小跳數是節(jié)點到網關節(jié)點的最小跳數，離網關越近的節(jié)點不僅需要傳輸自身負載，還要轉發(fā)離網關較遠節(jié)點的負載，優(yōu)先級就越高；射頻端口與WMN網絡容量支撐能力有關，接口越少，優(yōu)先級就越高。節(jié)點的優(yōu)先級可以表示為：

（5）

3 基于權重優(yōu)化的BWOCA算法

本文采用信道分配過程中的損耗對節(jié)點競爭博弈中的權重進行優(yōu)化，從而達到每一次博弈都會自動更新權重，動態(tài)分配信道，使信道分配更加公平有效。

3.1干擾損耗

帶寬損耗包含信道間損耗和網絡內部鄰居節(jié)點間的損耗。每個信道都只有兩種狀態(tài)，即占用和空閑。當一個節(jié)點i選擇信道c時，占用的時間定義為Tc,occupy(i)；當信道c空閑時，時間為Tc, free(i)，選擇信道c信道干擾損耗為：

（6）

對于網絡內部來說，損耗主要來自節(jié)點間的干擾損耗。同一時間選擇信道c的節(jié)點總和為，其中N-i為節(jié)點i的干擾范圍內的節(jié)點。則選擇信道c的節(jié)點之間的干擾節(jié)點密度為：

（7）

根據式（6）和式（7），可以得到節(jié)點i選擇信道c時總的干擾損耗函數為：

（8）

3.2切換延時損耗

每個節(jié)點的損耗不僅有干擾損耗，還存在切換延時損耗。每個節(jié)點都有兩種接口：發(fā)送接口Tr和接收接口Re。信道分配時選擇每個節(jié)點的Re接口接收傳輸數據，然后切換到Tr接口發(fā)送數據，切換過程中會產生延時，則切換延時損耗函數為：

（9）

3.3損耗指數因子

通過綜合干擾損耗和切換延時損耗引入損耗指數因子Lc(i)，其函數表達式為：

Lc(i)=αLossc,T(i)+(1-α)Lossc,I(i)（10）

其中，α為調節(jié)因子（α∈[0,1]），損耗指數因子Lc(i)的范圍也為[0,1]。

3.4權重優(yōu)化

由于無線Mesh網絡中數據傳輸存在著信道之間和節(jié)點之間的干擾，這些干擾是時刻變化的，而傳統(tǒng)的博弈模型中權重是固定的，采用傳統(tǒng)模型顯然會帶來一定的誤差。本文根據數據傳輸中的損耗，節(jié)點之間每次博弈都會自動更新博弈權重，使信道分配更加實時化。設r為博弈的輪數，r∈{1,2,…,Ro}，Ro為博弈的總輪數，則節(jié)點i后一輪的博弈權重與前一輪博弈權重關系如下：

（11）

其中，Lc(i)為損耗指數因子；ε為權重優(yōu)化因子（ε∈[0,1]），用來衡量權重優(yōu)化程度。ε越小，權重變化就越大，信道分配決策的誤差就越大；ε越大，權重變化就越小，信道分配決策的誤差就越小。通過仿真實驗ε取0.25。因此，節(jié)點i選擇信道c的概率分布Pi(c)為：

（12）

4 仿真及結果分析

在本文仿真場景中，設定無線Mesh網絡拓撲為1 000m ×1 000m范圍內，節(jié)點數為50，信道數為10，節(jié)點的傳輸半徑為10m、傳輸帶寬為5Mbit/s。將一種新式的基于博弈論的信道分配方法（GBCA）與本文的BWOCA算法相比較，可以看出BWOCA算法較GBCA算法在吞吐量方面有了很大的提高，如圖3所示。隨著節(jié)點數量的增多，吞吐量也越來越大，BWOCA算法的吞吐量隨著節(jié)點數的增加明顯高于GBCA的吞吐量。

圖3網絡吞吐量隨節(jié)點數目變化

如圖4所示，在傳輸平均延時方面，隨著節(jié)點數目的增加，節(jié)點的傳輸負載會相應增加，延時也會逐漸增大。本文提出的BWOCA算法在5個節(jié)點之前，延時與GBCA算法相當；5個節(jié)點之后，明顯延時低于GBCA算法的延時。

針對信道分配的公平性問題，本文采用Jain公平指標來評價，計算公式為：

（13）

xi為節(jié)點i的吞吐量；n為節(jié)點總數。將本文BWOCA算法與原有算法信道分配公平性作比較，如圖5所示。

從圖5可以看出，新算法的公平性指數數值均比原有算法大。經統(tǒng)計，新算法的信道分配公平性指數比原有算法提升了2.21%，這說明該算法具有更良好的公平性。

5 結束語

本文通過對通信傳輸中信道分配損耗因子的分析，提出了一種新的算法BWOCA對博弈中的權重進行優(yōu)化，將傳統(tǒng)的靜態(tài)博弈變?yōu)閯討B(tài)博弈，并引入非強占優(yōu)先制排隊模型根據節(jié)點的優(yōu)先級使得信道分配更加公平。仿真實驗表明，新算法的吞吐量有了很大的提高，傳輸延時有所降低，信道資源得到了公平地分配，符合公平性原則，網絡性能得到了良好的提升。但是算法并未考慮復雜度和能量消耗問題，因此還存在一定的局限性。未來將加入復雜度分析及節(jié)能措施，使其為無線Mesh網絡發(fā)展提供更有利的依據。

參考文獻：

[1] Chen Linlin, Liu Naian. Wireless Mesh Network and IEEE 802 Standards[J]. ZTE Communication, 2008,6(2): 7-10.

[2] Ekram Hossain, Kin Leung. Wireless Mesh Network Achitectures and Protocols[M]. USA: Springer Science Business Media, LLC, 2008.

[3] 馮琳函,錢志鴻,金冬成. 增強型的無線mesh網絡信道分配方法[J]. 通信學報, 2012(10): 44-50.

[4] 龍飛,汪春霆,楊治安. 一種基于博弈論的無線網狀網絡路由與信道分配聯(lián)合優(yōu)化算法[J]. 國防科技大學學報, 2012(2): 94-101.

[5] Vusumuzi Moyo, Olabisi Falowo, Mqhele Dlodlo. Improving Inter Service Bandwidth Fairness in Wireless Mesh Network[C]. Tunisia: Elec-trotechnical Conference. 2012: 1013-1016.

[6] 蘇凡軍,房慧聰,徐建,等. 多信道無線Mesh網絡公平帶寬分配算法[J]. 計算機工程, 2012(15): 66-69.

[7] 劉軍,謝秀峰. 基于排隊延時及博弈分析的認知無線網絡信道分配算法[J]. 通信學報, 2012(6): 73-81.

[8] 孫榮恒,李建平. 排隊論基礎[M]. 北京: 科學出版社, 2002.★

作者簡介

李鋮：昆明理工大學信息工程與自動化學院2011級碩士研究生，主要研究方向為無線Mesh網絡。

龍華：教授,現任職于昆明理工大學信息工程與自動化學院，主要研究方向為無線網絡。

李克：副教授，現任職于中原工學院圖書館，主要研究方向為情報學。

endprint

以每個WMR選擇信道的概率作為博弈策略，對于節(jié)點i有si={si1,si2,…,sim}種策略可供選擇，每個策略都有相應的效益Ui=Ui(s1,s2,…,sM)，Ui可定義為節(jié)點i選擇某種策略所得到的吞吐量，當滿足Ui(s1,s2,…,sM)≤Ui(s*1,s*2,…,s*M)時，博弈達到納什均衡，其中s*1為使全網達到NE的最優(yōu)策略。

效用函數（Utility Function）的目標在于最大化吞吐量，定義目標函數為：

（2）

其中，Pi(c)為節(jié)點i選擇信道c的概率；fi為節(jié)點i的傳輸流量；Rb為節(jié)點i的實際傳輸率。

2.3流量模型分析

針對WMR的流量分配策略[7]可以用M/G/1非強占優(yōu)先制排隊模型[8]分析。整個無線Mesh網中每個節(jié)點數據到達率λi和處理速率μi服從泊松分布。為了計算效用函數，需要用到端到端延時Wql概率分布。根據M/G/1隊列的性質，Si為節(jié)點i的服務時間，=1/μi，則有：

（3）

其中，。端到端延時Wql由平均服務時間、排隊時間以及前一節(jié)點剩余服務時間構成，即Wql=Ws+Wq+Wo，，Wqi為第i節(jié)點的平均排隊等待時間；，S為系統(tǒng)服務時間；Wo=Wql?？梢缘玫蕉说蕉搜訒rWql的期望為：

（4）

節(jié)點的優(yōu)先級與節(jié)點所選信道的負載、節(jié)點的端口數和最小跳數有關。對優(yōu)先級的判斷首先根據所選信道的負載，節(jié)點所選信道c的負載越大，那么傳輸的需求就越大，優(yōu)先級就高；最小跳數是節(jié)點到網關節(jié)點的最小跳數，離網關越近的節(jié)點不僅需要傳輸自身負載，還要轉發(fā)離網關較遠節(jié)點的負載，優(yōu)先級就越高；射頻端口與WMN網絡容量支撐能力有關，接口越少，優(yōu)先級就越高。節(jié)點的優(yōu)先級可以表示為：

（5）

3 基于權重優(yōu)化的BWOCA算法

本文采用信道分配過程中的損耗對節(jié)點競爭博弈中的權重進行優(yōu)化，從而達到每一次博弈都會自動更新權重，動態(tài)分配信道，使信道分配更加公平有效。

3.1干擾損耗

帶寬損耗包含信道間損耗和網絡內部鄰居節(jié)點間的損耗。每個信道都只有兩種狀態(tài)，即占用和空閑。當一個節(jié)點i選擇信道c時，占用的時間定義為Tc,occupy(i)；當信道c空閑時，時間為Tc, free(i)，選擇信道c信道干擾損耗為：

（6）

對于網絡內部來說，損耗主要來自節(jié)點間的干擾損耗。同一時間選擇信道c的節(jié)點總和為，其中N-i為節(jié)點i的干擾范圍內的節(jié)點。則選擇信道c的節(jié)點之間的干擾節(jié)點密度為：

（7）

根據式（6）和式（7），可以得到節(jié)點i選擇信道c時總的干擾損耗函數為：

（8）

3.2切換延時損耗

每個節(jié)點的損耗不僅有干擾損耗，還存在切換延時損耗。每個節(jié)點都有兩種接口：發(fā)送接口Tr和接收接口Re。信道分配時選擇每個節(jié)點的Re接口接收傳輸數據，然后切換到Tr接口發(fā)送數據，切換過程中會產生延時，則切換延時損耗函數為：

（9）

3.3損耗指數因子

通過綜合干擾損耗和切換延時損耗引入損耗指數因子Lc(i)，其函數表達式為：

Lc(i)=αLossc,T(i)+(1-α)Lossc,I(i)（10）

其中，α為調節(jié)因子（α∈[0,1]），損耗指數因子Lc(i)的范圍也為[0,1]。

3.4權重優(yōu)化

由于無線Mesh網絡中數據傳輸存在著信道之間和節(jié)點之間的干擾，這些干擾是時刻變化的，而傳統(tǒng)的博弈模型中權重是固定的，采用傳統(tǒng)模型顯然會帶來一定的誤差。本文根據數據傳輸中的損耗，節(jié)點之間每次博弈都會自動更新博弈權重，使信道分配更加實時化。設r為博弈的輪數，r∈{1,2,…,Ro}，Ro為博弈的總輪數，則節(jié)點i后一輪的博弈權重與前一輪博弈權重關系如下：

（11）

其中，Lc(i)為損耗指數因子；ε為權重優(yōu)化因子（ε∈[0,1]），用來衡量權重優(yōu)化程度。ε越小，權重變化就越大，信道分配決策的誤差就越大；ε越大，權重變化就越小，信道分配決策的誤差就越小。通過仿真實驗ε取0.25。因此，節(jié)點i選擇信道c的概率分布Pi(c)為：

（12）

4 仿真及結果分析

在本文仿真場景中，設定無線Mesh網絡拓撲為1 000m ×1 000m范圍內，節(jié)點數為50，信道數為10，節(jié)點的傳輸半徑為10m、傳輸帶寬為5Mbit/s。將一種新式的基于博弈論的信道分配方法（GBCA）與本文的BWOCA算法相比較，可以看出BWOCA算法較GBCA算法在吞吐量方面有了很大的提高，如圖3所示。隨著節(jié)點數量的增多，吞吐量也越來越大，BWOCA算法的吞吐量隨著節(jié)點數的增加明顯高于GBCA的吞吐量。

圖3網絡吞吐量隨節(jié)點數目變化

如圖4所示，在傳輸平均延時方面，隨著節(jié)點數目的增加，節(jié)點的傳輸負載會相應增加，延時也會逐漸增大。本文提出的BWOCA算法在5個節(jié)點之前，延時與GBCA算法相當；5個節(jié)點之后，明顯延時低于GBCA算法的延時。

針對信道分配的公平性問題，本文采用Jain公平指標來評價，計算公式為：

（13）

xi為節(jié)點i的吞吐量；n為節(jié)點總數。將本文BWOCA算法與原有算法信道分配公平性作比較，如圖5所示。

從圖5可以看出，新算法的公平性指數數值均比原有算法大。經統(tǒng)計，新算法的信道分配公平性指數比原有算法提升了2.21%，這說明該算法具有更良好的公平性。

5 結束語

本文通過對通信傳輸中信道分配損耗因子的分析，提出了一種新的算法BWOCA對博弈中的權重進行優(yōu)化，將傳統(tǒng)的靜態(tài)博弈變?yōu)閯討B(tài)博弈，并引入非強占優(yōu)先制排隊模型根據節(jié)點的優(yōu)先級使得信道分配更加公平。仿真實驗表明，新算法的吞吐量有了很大的提高，傳輸延時有所降低，信道資源得到了公平地分配，符合公平性原則，網絡性能得到了良好的提升。但是算法并未考慮復雜度和能量消耗問題，因此還存在一定的局限性。未來將加入復雜度分析及節(jié)能措施，使其為無線Mesh網絡發(fā)展提供更有利的依據。

參考文獻：

[1] Chen Linlin, Liu Naian. Wireless Mesh Network and IEEE 802 Standards[J]. ZTE Communication, 2008,6(2): 7-10.

[2] Ekram Hossain, Kin Leung. Wireless Mesh Network Achitectures and Protocols[M]. USA: Springer Science Business Media, LLC, 2008.

[3] 馮琳函,錢志鴻,金冬成. 增強型的無線mesh網絡信道分配方法[J]. 通信學報, 2012(10): 44-50.

[4] 龍飛,汪春霆,楊治安. 一種基于博弈論的無線網狀網絡路由與信道分配聯(lián)合優(yōu)化算法[J]. 國防科技大學學報, 2012(2): 94-101.

[5] Vusumuzi Moyo, Olabisi Falowo, Mqhele Dlodlo. Improving Inter Service Bandwidth Fairness in Wireless Mesh Network[C]. Tunisia: Elec-trotechnical Conference. 2012: 1013-1016.

[6] 蘇凡軍,房慧聰,徐建,等. 多信道無線Mesh網絡公平帶寬分配算法[J]. 計算機工程, 2012(15): 66-69.

[7] 劉軍,謝秀峰. 基于排隊延時及博弈分析的認知無線網絡信道分配算法[J]. 通信學報, 2012(6): 73-81.

[8] 孫榮恒,李建平. 排隊論基礎[M]. 北京: 科學出版社, 2002.★

作者簡介

李鋮：昆明理工大學信息工程與自動化學院2011級碩士研究生，主要研究方向為無線Mesh網絡。

龍華：教授,現任職于昆明理工大學信息工程與自動化學院，主要研究方向為無線網絡。

李克：副教授，現任職于中原工學院圖書館，主要研究方向為情報學。

endprint

以每個WMR選擇信道的概率作為博弈策略，對于節(jié)點i有si={si1,si2,…,sim}種策略可供選擇，每個策略都有相應的效益Ui=Ui(s1,s2,…,sM)，Ui可定義為節(jié)點i選擇某種策略所得到的吞吐量，當滿足Ui(s1,s2,…,sM)≤Ui(s*1,s*2,…,s*M)時，博弈達到納什均衡，其中s*1為使全網達到NE的最優(yōu)策略。

效用函數（Utility Function）的目標在于最大化吞吐量，定義目標函數為：

（2）

其中，Pi(c)為節(jié)點i選擇信道c的概率；fi為節(jié)點i的傳輸流量；Rb為節(jié)點i的實際傳輸率。

2.3流量模型分析

針對WMR的流量分配策略[7]可以用M/G/1非強占優(yōu)先制排隊模型[8]分析。整個無線Mesh網中每個節(jié)點數據到達率λi和處理速率μi服從泊松分布。為了計算效用函數，需要用到端到端延時Wql概率分布。根據M/G/1隊列的性質，Si為節(jié)點i的服務時間，=1/μi，則有：

（3）

其中，。端到端延時Wql由平均服務時間、排隊時間以及前一節(jié)點剩余服務時間構成，即Wql=Ws+Wq+Wo，，Wqi為第i節(jié)點的平均排隊等待時間；，S為系統(tǒng)服務時間；Wo=Wql?？梢缘玫蕉说蕉搜訒rWql的期望為：

（4）

節(jié)點的優(yōu)先級與節(jié)點所選信道的負載、節(jié)點的端口數和最小跳數有關。對優(yōu)先級的判斷首先根據所選信道的負載，節(jié)點所選信道c的負載越大，那么傳輸的需求就越大，優(yōu)先級就高；最小跳數是節(jié)點到網關節(jié)點的最小跳數，離網關越近的節(jié)點不僅需要傳輸自身負載，還要轉發(fā)離網關較遠節(jié)點的負載，優(yōu)先級就越高；射頻端口與WMN網絡容量支撐能力有關，接口越少，優(yōu)先級就越高。節(jié)點的優(yōu)先級可以表示為：

（5）

3 基于權重優(yōu)化的BWOCA算法

本文采用信道分配過程中的損耗對節(jié)點競爭博弈中的權重進行優(yōu)化，從而達到每一次博弈都會自動更新權重，動態(tài)分配信道，使信道分配更加公平有效。

3.1干擾損耗

帶寬損耗包含信道間損耗和網絡內部鄰居節(jié)點間的損耗。每個信道都只有兩種狀態(tài)，即占用和空閑。當一個節(jié)點i選擇信道c時，占用的時間定義為Tc,occupy(i)；當信道c空閑時，時間為Tc, free(i)，選擇信道c信道干擾損耗為：

（6）

對于網絡內部來說，損耗主要來自節(jié)點間的干擾損耗。同一時間選擇信道c的節(jié)點總和為，其中N-i為節(jié)點i的干擾范圍內的節(jié)點。則選擇信道c的節(jié)點之間的干擾節(jié)點密度為：

（7）

根據式（6）和式（7），可以得到節(jié)點i選擇信道c時總的干擾損耗函數為：

（8）

3.2切換延時損耗

每個節(jié)點的損耗不僅有干擾損耗，還存在切換延時損耗。每個節(jié)點都有兩種接口：發(fā)送接口Tr和接收接口Re。信道分配時選擇每個節(jié)點的Re接口接收傳輸數據，然后切換到Tr接口發(fā)送數據，切換過程中會產生延時，則切換延時損耗函數為：

（9）

3.3損耗指數因子

通過綜合干擾損耗和切換延時損耗引入損耗指數因子Lc(i)，其函數表達式為：

Lc(i)=αLossc,T(i)+(1-α)Lossc,I(i)（10）

其中，α為調節(jié)因子（α∈[0,1]），損耗指數因子Lc(i)的范圍也為[0,1]。

3.4權重優(yōu)化

由于無線Mesh網絡中數據傳輸存在著信道之間和節(jié)點之間的干擾，這些干擾是時刻變化的，而傳統(tǒng)的博弈模型中權重是固定的，采用傳統(tǒng)模型顯然會帶來一定的誤差。本文根據數據傳輸中的損耗，節(jié)點之間每次博弈都會自動更新博弈權重，使信道分配更加實時化。設r為博弈的輪數，r∈{1,2,…,Ro}，Ro為博弈的總輪數，則節(jié)點i后一輪的博弈權重與前一輪博弈權重關系如下：

（11）

其中，Lc(i)為損耗指數因子；ε為權重優(yōu)化因子（ε∈[0,1]），用來衡量權重優(yōu)化程度。ε越小，權重變化就越大，信道分配決策的誤差就越大；ε越大，權重變化就越小，信道分配決策的誤差就越小。通過仿真實驗ε取0.25。因此，節(jié)點i選擇信道c的概率分布Pi(c)為：

（12）

4 仿真及結果分析

在本文仿真場景中，設定無線Mesh網絡拓撲為1 000m ×1 000m范圍內，節(jié)點數為50，信道數為10，節(jié)點的傳輸半徑為10m、傳輸帶寬為5Mbit/s。將一種新式的基于博弈論的信道分配方法（GBCA）與本文的BWOCA算法相比較，可以看出BWOCA算法較GBCA算法在吞吐量方面有了很大的提高，如圖3所示。隨著節(jié)點數量的增多，吞吐量也越來越大，BWOCA算法的吞吐量隨著節(jié)點數的增加明顯高于GBCA的吞吐量。

圖3網絡吞吐量隨節(jié)點數目變化

如圖4所示，在傳輸平均延時方面，隨著節(jié)點數目的增加，節(jié)點的傳輸負載會相應增加，延時也會逐漸增大。本文提出的BWOCA算法在5個節(jié)點之前，延時與GBCA算法相當；5個節(jié)點之后，明顯延時低于GBCA算法的延時。

針對信道分配的公平性問題，本文采用Jain公平指標來評價，計算公式為：

（13）

xi為節(jié)點i的吞吐量；n為節(jié)點總數。將本文BWOCA算法與原有算法信道分配公平性作比較，如圖5所示。

從圖5可以看出，新算法的公平性指數數值均比原有算法大。經統(tǒng)計，新算法的信道分配公平性指數比原有算法提升了2.21%，這說明該算法具有更良好的公平性。

5 結束語

本文通過對通信傳輸中信道分配損耗因子的分析，提出了一種新的算法BWOCA對博弈中的權重進行優(yōu)化，將傳統(tǒng)的靜態(tài)博弈變?yōu)閯討B(tài)博弈，并引入非強占優(yōu)先制排隊模型根據節(jié)點的優(yōu)先級使得信道分配更加公平。仿真實驗表明，新算法的吞吐量有了很大的提高，傳輸延時有所降低，信道資源得到了公平地分配，符合公平性原則，網絡性能得到了良好的提升。但是算法并未考慮復雜度和能量消耗問題，因此還存在一定的局限性。未來將加入復雜度分析及節(jié)能措施，使其為無線Mesh網絡發(fā)展提供更有利的依據。

參考文獻：

[1] Chen Linlin, Liu Naian. Wireless Mesh Network and IEEE 802 Standards[J]. ZTE Communication, 2008,6(2): 7-10.

[2] Ekram Hossain, Kin Leung. Wireless Mesh Network Achitectures and Protocols[M]. USA: Springer Science Business Media, LLC, 2008.

[3] 馮琳函,錢志鴻,金冬成. 增強型的無線mesh網絡信道分配方法[J]. 通信學報, 2012(10): 44-50.

[4] 龍飛,汪春霆,楊治安. 一種基于博弈論的無線網狀網絡路由與信道分配聯(lián)合優(yōu)化算法[J]. 國防科技大學學報, 2012(2): 94-101.

[5] Vusumuzi Moyo, Olabisi Falowo, Mqhele Dlodlo. Improving Inter Service Bandwidth Fairness in Wireless Mesh Network[C]. Tunisia: Elec-trotechnical Conference. 2012: 1013-1016.

[6] 蘇凡軍,房慧聰,徐建,等. 多信道無線Mesh網絡公平帶寬分配算法[J]. 計算機工程, 2012(15): 66-69.

[7] 劉軍,謝秀峰. 基于排隊延時及博弈分析的認知無線網絡信道分配算法[J]. 通信學報, 2012(6): 73-81.

[8] 孫榮恒,李建平. 排隊論基礎[M]. 北京: 科學出版社, 2002.★

作者簡介

李鋮：昆明理工大學信息工程與自動化學院2011級碩士研究生，主要研究方向為無線Mesh網絡。

龍華：教授,現任職于昆明理工大學信息工程與自動化學院，主要研究方向為無線網絡。

李克：副教授，現任職于中原工學院圖書館，主要研究方向為情報學。

endprint