樂光學，李明明，3，丁　輝，劉建生，駱　丹，馬伯林

(1.嘉興學院數(shù)理與信息工程學院，浙江嘉興314000; 2.江西理工大學理學院，江西贛州431000; 3.嘉興職業(yè)技術(shù)學院，浙江嘉興314000)

?

無線Mesh網(wǎng)絡(luò)中基于演化博弈的抗振蕩信道分配策略

樂光學1，2，李明明1，2，3，丁輝1，2，劉建生2，駱丹1，2，馬伯林2

(1.嘉興學院數(shù)理與信息工程學院，浙江嘉興314000; 2.江西理工大學理學院，江西贛州431000; 3.嘉興職業(yè)技術(shù)學院，浙江嘉興314000)

摘要：為抑制無線Mesh網(wǎng)絡(luò)中的信道振蕩和提升網(wǎng)絡(luò)效用，綜合分析路由端和用戶端信道振蕩產(chǎn)生的因素.引入演化博弈理論，聯(lián)合改進的果蠅優(yōu)化算法提出基于ESS-PFOA(Evolutionary Stable Status-Promoted Fruit-Flies Optimal Algorithm)算法的分布式信道分配策略.實驗分析發(fā)現(xiàn)當信道振蕩寬容因子β≤0.5時網(wǎng)絡(luò)呈同構(gòu)特征，β＞0.5時網(wǎng)絡(luò)向異構(gòu)轉(zhuǎn)化，β≥0.9時網(wǎng)絡(luò)呈異構(gòu)特征;網(wǎng)絡(luò)效用和信道振蕩抑制率與信道振蕩寬容因子β緊密相關(guān).仿真結(jié)果表明，ESS-PFOA算法的信道振蕩率從0.44下降至0.08，在異構(gòu)網(wǎng)絡(luò)環(huán)境下其網(wǎng)絡(luò)收益和信道振蕩抑制率明顯占優(yōu)，能有效提高網(wǎng)絡(luò)效用.

關(guān)鍵詞：無線Mesh網(wǎng)絡(luò);多信道多射頻;演化博弈;信道振蕩;網(wǎng)絡(luò)效用

1　引言

無線Mesh網(wǎng)絡(luò)的信道連接依賴問題頻繁發(fā)生，在通信鏈路上形成信道空閑、擁塞狀態(tài)，如何解決信道連接依賴問題是多信道多射頻無線Mesh網(wǎng)絡(luò)信道分配方案的關(guān)鍵［1～3］.信道連接依賴在多沖突域內(nèi)表征為信道振蕩［4］，發(fā)生信道振蕩的通信鏈路，存在流量分配不均、網(wǎng)絡(luò)負載失衡等問題，嚴重影響網(wǎng)絡(luò)穩(wěn)定性.如何有效規(guī)避信道振蕩發(fā)生率、穩(wěn)定提升網(wǎng)絡(luò)吞吐量，成為無線Mesh網(wǎng)絡(luò)信道分配策略的研究熱點之一.

大量研究報告表明，無線Mesh網(wǎng)絡(luò)信道分配是NP問題［5～7］.以提升網(wǎng)絡(luò)吞吐量［8～10］、降低鏈路干擾率［11］、優(yōu)化信道利用率［12］等方面為研究側(cè)重點，實現(xiàn)信道分配策略的優(yōu)化.文獻［1］研究多沖突域內(nèi)節(jié)點之間頻繁切換信道引發(fā)的信道振蕩問題，提出了基于局部自適應的分布式信道分配方案.文獻［13］提出適用于Ad Hoc網(wǎng)絡(luò)的集中式信道分配策略，并通過仿真實驗驗證信道振蕩的存在性［13］;文獻［14］在分析如何提升無線Mesh網(wǎng)絡(luò)有效聚合吞吐量時，發(fā)現(xiàn)通信域內(nèi)存在信道振蕩問題［14］.將信道振蕩發(fā)生率作為一種新的網(wǎng)絡(luò)性能評價指標，以信道振蕩發(fā)生作為研究入口，設(shè)計有利于規(guī)避信道振蕩并實現(xiàn)信道重分配的優(yōu)化策略.文獻［15］提出了聯(lián)合協(xié)議與接口分配策略相結(jié)合的信道分配優(yōu)化方案(Protocol and Communicational Interface-Channel to Utility-Channel Assignment，PCU-CA)，指出信道振蕩對Ad Hoc網(wǎng)絡(luò)信道分配結(jié)果的危害性，以給定的信道振蕩概率因子p =0.4作為評價指標，該算法僅適用于Ad Hoc網(wǎng)絡(luò).文獻［16］提出了基于C-Hyacinth(C-HYA)算法的增強型貪心信道分配策略，以訪問節(jié)點的優(yōu)先級作為分配序列，依次分配信道.由于策略僅處理單沖突域內(nèi)信道連接依賴問題，算法尚未計算信道振蕩發(fā)生率.

如圖1所示，若信道正常分配，多沖突域內(nèi)源節(jié)點S通過信道X向目的節(jié)點D轉(zhuǎn)發(fā)數(shù)據(jù)包，對應的目的節(jié)點D正通過信道Y與其目的節(jié)點R通信，一旦節(jié)點D切換信道X至信道Y，將引起信道X通信擁塞、信道Y無數(shù)據(jù)包轉(zhuǎn)發(fā)呈現(xiàn)空閑狀態(tài).并且在下一個沖突域范圍內(nèi)D-R通信鏈路上出現(xiàn)數(shù)據(jù)擁塞.同理S1-R1、S2-R2均產(chǎn)生類似的信道振蕩問題［4］.

在信道分配優(yōu)化方面，國內(nèi)外研究人員作了大量工作，并取得了突出成果.針對不同網(wǎng)絡(luò)拓撲，嘗試降低數(shù)據(jù)包的轉(zhuǎn)發(fā)率以提升網(wǎng)絡(luò)吞吐量［8～10］.在異構(gòu)網(wǎng)絡(luò)中，處理邊界節(jié)點的流量擁塞控制問題，提出了基于預知擁塞控制的數(shù)學模型［11］.在多層異構(gòu)無線網(wǎng)絡(luò)中，針對射頻接口能量流失問題，提出滿足所有鏈路需求的最小化射頻接口流量損失模型［12］.在多媒體異構(gòu)Mesh網(wǎng)絡(luò)中，建立多媒體異構(gòu)Mesh網(wǎng)絡(luò)的服務(wù)質(zhì)量控制機制，提出了雙層規(guī)劃模型的蟻群優(yōu)化路由算法［17］.為了實現(xiàn)完全的避免信道干擾，提出了域內(nèi)中心調(diào)度的接口分域信道分配(Interfaced-Clustered Channel Assignment，ICCA)方案，算法有效提升了網(wǎng)絡(luò)吞吐量［18］.將博弈理論應用于多信道多射頻無線Mesh網(wǎng)絡(luò)信道分配策略，分析自適應節(jié)點的行為以及如何有效提升網(wǎng)絡(luò)吞吐量［19～24］.由于節(jié)點位置和方向不定，無法計算網(wǎng)絡(luò)拓撲上的信道振蕩發(fā)生率，文獻［25］將演化博弈引入無線傳感器網(wǎng)絡(luò)中，僅針對節(jié)點信譽機制分析不同的演化穩(wěn)定均衡解.在異構(gòu)網(wǎng)絡(luò)環(huán)境下，文獻［26，27］提出了基于非合作博弈的信道資源分配接入模型，算法分析了自私節(jié)點的聚集度和網(wǎng)絡(luò)拓撲，仿真結(jié)果表明算法有效提升了網(wǎng)絡(luò)吞吐量.

本文將針對異構(gòu)無線Mesh網(wǎng)絡(luò)網(wǎng)關(guān)節(jié)點和用戶節(jié)點展開信道分配［13］方案的優(yōu)化，聯(lián)合演化博弈理論和改進的果蠅優(yōu)化算法，設(shè)計一種有效的抗振蕩信道分配策略(Evolutionary Stable Status-Promoted Fruit-flies Optimal Algorithm，ESS-PFOA).首先，建立節(jié)點的演化博弈模型，以節(jié)點所在干擾域的干擾率與節(jié)點有效聚合吞吐率的比值作為演化穩(wěn)定均衡解的方程.繼而，分析不同演化穩(wěn)定均衡狀態(tài)下的網(wǎng)絡(luò)收益.第三，評價不同信道振蕩寬容因子下服務(wù)節(jié)點的網(wǎng)絡(luò)收益，計算對應的信道振蕩發(fā)生率.最后，與已有抗振蕩的信道分配策略PCU-CA、C-HYA算法對比，綜合評價抗振蕩信道分配策略的有效性、穩(wěn)定性.

2　問題提出及模型的建立

2.1信道振蕩問題描述

PCU-CA算法采用線性模型處理給定節(jié)點之間的信道振蕩問題［15］，但是線性模型無法處理離散節(jié)點的分布［28］.C-HYA算法采用集中式的信道分配策略［16］，僅處理單沖突域內(nèi)信道連接依賴問題，且僅適用于穩(wěn)定的網(wǎng)絡(luò)拓撲［23］.基于ESS-FPOA算法針對離散節(jié)點采用非線性數(shù)學模型，為自適應的無線Mesh網(wǎng)絡(luò)設(shè)計分布式信道分配策略，實現(xiàn)業(yè)務(wù)穩(wěn)定傳輸.

假設(shè)多信道多射頻無線Mesh網(wǎng)絡(luò)的每一個節(jié)點具有兩個可用射頻接口，如圖2(a)所示其路由端節(jié)點的特點是自上而下的數(shù)據(jù)轉(zhuǎn)發(fā)方式，易造成通信鏈路信息冗余;如圖2(b)所示其用戶端節(jié)點具有隨機性和交互性，節(jié)點之間存在競爭行為.當節(jié)點B接收到來自不同沖突域的節(jié)點A和節(jié)點D的數(shù)據(jù)包，需要選擇切換信道，出現(xiàn)信道選擇停留狀態(tài)，該狀態(tài)是信道振蕩發(fā)生的明顯特征［4］.

2.2演化博弈模型

針對自適應的多沖突域無線Mesh網(wǎng)絡(luò)拓撲結(jié)構(gòu)，建立動態(tài)演化博弈模型.模型設(shè)計思路為:

(1)在多沖突域內(nèi)存在通信信道集C，服務(wù)節(jié)點集V，以及服務(wù)節(jié)點的信道接口集K，則通信過程中節(jié)點最大有效聚合吞吐量集合為B(C).得到節(jié)點的信道分配策略為S(K，C，V).如果節(jié)點在通信鏈路上通過射頻接口成功通信，則其網(wǎng)絡(luò)效用函數(shù)表示為U(S(K，C，V)，B(C)).

(2)由于服務(wù)節(jié)點群體數(shù)量受節(jié)點的在線服務(wù)時間、節(jié)點自組織、信道干擾等因素影響，將信道分配過程中服務(wù)節(jié)點數(shù)量的變化理解為服務(wù)節(jié)點抑制信道振蕩發(fā)生的演化過程.節(jié)點在時刻T選擇策略S的概率為P，則其混合策略為P.

(3)根據(jù)節(jié)點的信道分配策略S和混合策略P建立演化博弈模型，得到演化博弈穩(wěn)定均衡解.根據(jù)演化穩(wěn)定均衡解，分析不同的演化穩(wěn)定均衡狀態(tài)，選擇最優(yōu)狀態(tài).并計算最優(yōu)網(wǎng)絡(luò)收益U(S，B，P).

通信節(jié)點vi∈V使用信道cj∈C的接口數(shù)量kvi，cj∈K.第i個節(jié)點使用第j個信道成功通信策略Si= {(ki，1，…，ki，j，…ki，P)}，其中i = 1，2，…，N; j = 1，2，…，P，ki，j= { 0，1} .節(jié)點成功通信ki，j=1，否則ki，j=0.節(jié)點在t∈［0，T］時刻選擇Si的概率為Pi，j，可構(gòu)建在t時刻所有節(jié)點的混合策略描述模型:

式(2)定義了多沖突域內(nèi)節(jié)點成功通信的概率，即只允許第i個節(jié)點的射頻接口利用第j個信道通信.參考文獻［2］，給定M為沖突域的個數(shù)，d表示通信節(jié)點之間的距離.表示節(jié)點干擾域內(nèi)的干擾度，即當前節(jié)點可能干擾其后個節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包.成功通信的節(jié)點在t時刻使用策略Si的網(wǎng)絡(luò)收益為:

其中K表示干擾范圍內(nèi)節(jié)點的跳數(shù)，ni，j表示節(jié)點在干擾范圍內(nèi)節(jié)點與信道通信的射頻數(shù)量，表示節(jié)點上有效聚合吞吐量隨ni，j變化的遞減函數(shù).

在t +1時刻所有節(jié)點的混合策略描述模型可表征為:

聯(lián)合式(3)(4)求解節(jié)點的演化動態(tài)方程:

式(5)表示隨時間變化，節(jié)點狀態(tài)的演化率與節(jié)點網(wǎng)絡(luò)效用的演化率相同，其中B表示節(jié)點上行鏈路上的帶寬常量平均值，-U(Si，Bj)表示節(jié)點當前干擾域內(nèi)所有成功通信的節(jié)點之間的平均帶寬值.求解式(5)極限，則節(jié)點動態(tài)演化方程轉(zhuǎn)化為:

聯(lián)合求解式(5)(6)，當滿足式(7)時，達到網(wǎng)絡(luò)穩(wěn)定均衡狀態(tài)，其中Λ為節(jié)點的干擾閾值.

3　抗振蕩信道分配策略

為有效規(guī)避信道振蕩問題并提升穩(wěn)定網(wǎng)絡(luò)收益，將達到演化穩(wěn)定均衡狀態(tài)(Evolutionary Stable Status，ESS)的節(jié)點收益進行聚類優(yōu)化，實現(xiàn)多信道多射頻無線Mesh網(wǎng)絡(luò)的抗振蕩信道分配策略.引入果蠅演化算法(Fruit-Flies Optimal Algorithm，F(xiàn)OA)［29］，該算法原型為果蠅通過嗅覺尋找最優(yōu)路徑.算法保證適應度函數(shù)的快速收斂、縮短運行時間、方便科研驗證［29］.針對異構(gòu)網(wǎng)絡(luò)節(jié)點的行為特征，改進FOA算法.分析基于ESSPFOA算法的信道分配策略可行性、收斂性以及算法的時間復雜度.

3.1策略分析

定理1考慮不完全信息博弈的無線Mesh網(wǎng)絡(luò)環(huán)境，保證節(jié)點的順序理性和可信程度弱一致，順序理性主要保證節(jié)點之間不會出現(xiàn)某一節(jié)點單方面偏離.因而有限理性節(jié)點通信時能夠達到演化穩(wěn)定均衡狀態(tài)條件如下:

(2)存在任意參數(shù)ε∈(0，1)，在穩(wěn)定均衡狀態(tài)下，節(jié)點以穩(wěn)定均衡策略選擇穩(wěn)定策略其穩(wěn)定網(wǎng)絡(luò)效用期望滿足U(Si，Bj).其中:

證明為確保網(wǎng)絡(luò)拓撲穩(wěn)定轉(zhuǎn)發(fā)數(shù)據(jù)包，節(jié)點通信信道總數(shù)P至少與節(jié)點的接口總數(shù)等值，所有節(jié)點的射頻接口成功通信的數(shù)量之和小于等于通信節(jié)點的接口總數(shù)，體現(xiàn)動態(tài)無線Mesh網(wǎng)絡(luò)節(jié)點的移動交互能力［20］，故(1)可證.在動態(tài)信道分配中，處于穩(wěn)定均衡狀態(tài)的節(jié)點為全局最優(yōu)狀態(tài)［22］，采用反證法證明(2):

式(11)表示多個沖突域內(nèi)路由端、客戶端節(jié)點在其干擾域內(nèi)的干擾率等同于其當前的節(jié)點的網(wǎng)絡(luò)效用隨節(jié)點成功通信接口數(shù)量的變化率.

3.2算法描述

基于FOA算法中果蠅根據(jù)氣味濃度分辨食物的位置產(chǎn)生的路徑擇優(yōu)方法，改進FOA算法用來計算信道振蕩發(fā)生率.在無線Mesh網(wǎng)絡(luò)拓撲中以節(jié)點的干擾閾值來判斷信道振蕩的發(fā)生，根據(jù)節(jié)點聚集度來分析信道振蕩發(fā)生率，核心算法步驟如下:

Step1初始化網(wǎng)絡(luò)拓撲，隨機分配通信節(jié)點的群體位置，其中x(i)，y(i)表示節(jié)點的方向與相互之間的距離，T(i)表示節(jié)點與源節(jié)點之間的迭代距離，F(xiàn)it(i)為適應度函數(shù)的判斷函數(shù)，判斷節(jié)點是否收益.此時，計算復雜度為O(logn2).

Step2計算節(jié)點的最大化網(wǎng)絡(luò)效用.首先初始化網(wǎng)絡(luò)數(shù)據(jù)，計算節(jié)點成功通信的概率;其次計算成功通信節(jié)點的網(wǎng)絡(luò)效用值，分析演化穩(wěn)定狀態(tài)，并錄入最大的網(wǎng)絡(luò)效用值于Umax()表中，其中Umax((Si，Bj))為信道振蕩寬容因子影響下的網(wǎng)絡(luò)收益.此時，計算復雜度為O(n* log(n)).

Step3重復博弈，記錄轉(zhuǎn)折點位置，計算轉(zhuǎn)折點發(fā)生的比率，計算信道振蕩發(fā)生率.此時，計算復雜度為O(n2).

綜合step1～step3，得到算法的計算復雜度為O(n2).

4　仿真實驗與結(jié)果分析

參考文獻［14，16，30］仿真環(huán)境參數(shù)值，給定表1所示實驗參數(shù)，并通過16組實驗驗證ESS-PFOA算法在不同網(wǎng)絡(luò)信道振蕩寬容因子條件下的網(wǎng)絡(luò)效用收斂結(jié)果并與PCU-CA、C-HYA算法對比，分析不同算法在兩種實驗帶寬區(qū)間的網(wǎng)絡(luò)穩(wěn)定性.

4.1網(wǎng)絡(luò)有效性

實驗1是三種抗振蕩信道分配策略的網(wǎng)絡(luò)收益對比分析情況，以效用函數(shù)為對比指標.文獻［31］給出了惡意競爭節(jié)點的網(wǎng)絡(luò)收益寬容因子β值，調(diào)整寬容因子取值以詳細描述網(wǎng)絡(luò)節(jié)點收益，信道振蕩寬容因子取值如表2.

為了驗證ESS-PFOA算法的有效性，實驗中增加β取值區(qū)間和密度.為縮小篇幅，取寬容因子β=0.5、β= 0.9的網(wǎng)絡(luò)收益結(jié)果如圖3，β= 0.01～0.9之間網(wǎng)絡(luò)收益數(shù)據(jù)如表3.

表1　仿真實驗參數(shù)

表2　信道振蕩寬容因子β取值

實驗結(jié)果表明:

(1)PCU-CA、C-HYA算法均屬于靜態(tài)無線網(wǎng)絡(luò)的集中式信道分配策略，對于動態(tài)無線Mesh網(wǎng)絡(luò)環(huán)境適用性較小.對比其它算法在不同寬容因子β條件下的網(wǎng)絡(luò)收益，C-HYA算法雖然網(wǎng)絡(luò)吞吐量偏低，卻具有較為平穩(wěn)的網(wǎng)絡(luò)收益.

(2)當β＜0.50，ESS-PFOA算法網(wǎng)絡(luò)收益的波動率較其它算法小，C-HYA算法的網(wǎng)絡(luò)收益小于PCU-CA、ESS-PFOA算法.當β≥0.50，ESS-PFOA算法網(wǎng)絡(luò)收益較其它算法穩(wěn)定，ESS-PFOA算法的網(wǎng)絡(luò)收益高于其它算法.

(3)當β=0.90時ESS-PFOA算法具有最大網(wǎng)絡(luò)有效聚合吞吐量，其網(wǎng)絡(luò)效用和穩(wěn)定性整體占優(yōu).

(4)在100次迭代過程中，當β= 0.50時，三種算法的首次收斂時間分別為24、22、22;當β= 0.90時，三種算法的首次收斂時間分別為16、16、14，ESS-PFOA算法收斂時間略優(yōu)于其它兩種算法.

表3　信道振蕩寬容因子β下對不同抗振蕩信道分配策略的最大網(wǎng)絡(luò)收益和平均網(wǎng)絡(luò)收益

表3結(jié)果表明:

(1)隨寬容因子β值的增加，算法的網(wǎng)絡(luò)收益ESSPFOA＞PCU-CA＞C-HYA.

(2)增加寬容因子β從0.01到0.1之間、0.1到0.2之間變化，ESS-PFOA算法的平均網(wǎng)絡(luò)收益增加了約4.9倍、2.3倍，突出了節(jié)點的網(wǎng)絡(luò)收益穩(wěn)定提升的增長率.

4.2信道振蕩影響率對比分析

通過仿真節(jié)點的聚集度，分析當前網(wǎng)絡(luò)拓撲的信道振蕩發(fā)生情況.根據(jù)圖3網(wǎng)絡(luò)所示仿真結(jié)果觀測信道振蕩發(fā)生率(Channel Oscillation Ratio，COR)如圖4，信道振蕩發(fā)生率數(shù)據(jù)結(jié)果如表4.

實驗結(jié)果表明:

(1)節(jié)點聚集度與通信鏈路上信道振蕩發(fā)生率成正比，異構(gòu)網(wǎng)絡(luò)的聚集度明顯低于同構(gòu)網(wǎng)絡(luò).

表4　不同寬容因子β下的信道振蕩發(fā)生率

(2)當寬容因子β≤0.50時，網(wǎng)絡(luò)同構(gòu)特征明顯，PCU-CA、C-HYA、ESS-PFOA算法三種算法網(wǎng)絡(luò)效用和信道振蕩抑制率基本處于同一水平;當寬容因子β＞0.50時，網(wǎng)絡(luò)由同構(gòu)特征向異構(gòu)特征轉(zhuǎn)化; 當β≥0.90時，網(wǎng)絡(luò)異構(gòu)特征明顯.ESS-PFOA算法的網(wǎng)絡(luò)效用和信道振蕩抑制率明顯優(yōu)于PCU-CA、CHYA算法.

(3)當β=0.90時，PCU-CA、C-HYA算法由于節(jié)點之間協(xié)同服務(wù)質(zhì)量降低，聚集度下降，因而通信鏈路上信道振蕩發(fā)生率下降.

表4數(shù)據(jù)結(jié)果表明:

(1)在整個寬容因子β的取值區(qū)間內(nèi)，鏈路上的信道振蕩發(fā)生率由0.44下降至0.08，提高了信道分配成功幾率，提升了網(wǎng)絡(luò)穩(wěn)定性.

(2)在寬容因子β取值區(qū)間內(nèi)，ESS-PFOA算法的信道振蕩發(fā)生率均小于其它兩種算法，當β= 0.90時，ESS-PFOA算法具有最小信道振蕩發(fā)生率.

4.3網(wǎng)絡(luò)穩(wěn)定性分析

實驗2根據(jù)BC∈［0，5.4］和BC∈［5.4，54］兩種上行鏈路給定的網(wǎng)絡(luò)帶寬值區(qū)間，驗證寬容因子對網(wǎng)絡(luò)穩(wěn)定性的影響，其中β仿真結(jié)果如圖5，其數(shù)據(jù)結(jié)果如表5所示.

實驗結(jié)果表明:

(1)PCU-CA算法適合應用于帶寬區(qū)間BC∈［0，5.4］的通信鏈路，具有穩(wěn)定的網(wǎng)絡(luò)收益.在帶寬區(qū)間BC∈［5.4，54］，只有當β= 0.9時存在唯一穩(wěn)定的網(wǎng)絡(luò)收益.

(2)C-HYA算法在BC∈［0，5.4］、BC∈［5.4，54］中，因為剔除了發(fā)生信道振蕩的節(jié)點，可通信節(jié)點數(shù)量減少、網(wǎng)絡(luò)收益逐漸降低，但是其網(wǎng)絡(luò)收益穩(wěn)定收斂.

(3)PCU-CA、C-HYA算法均為集中式的抗振蕩信道分配策略.集合PCU-CA、C-HYA算法的優(yōu)點，ESSPFOA算法在帶寬區(qū)間BC∈［0，5.4］和BC∈［5.4，54］均具有較高網(wǎng)絡(luò)收益;當β≥0.5時ESS-PFOA算法在可容忍范圍內(nèi)保留貪婪節(jié)點，通信鏈路上網(wǎng)絡(luò)收益穩(wěn)定收斂;當β≤0.2時寬容因子太小，貪婪節(jié)點行為明顯，網(wǎng)絡(luò)收益存在波動，但是ESS-PFOA算法的穩(wěn)定網(wǎng)絡(luò)收益整體上較PCU-CA、C-HYA算法占優(yōu).

表5結(jié)果表明:

(1)ESS-PFOA算法在帶寬區(qū)間BC∈［0，5.4］和帶寬區(qū)間BC∈［5.4，54］的網(wǎng)絡(luò)收益均優(yōu)于PCU-CA、CHYA算法的網(wǎng)絡(luò)收益.

(2)PCU-CA算法在BC∈［5.4，54］帶寬區(qū)間的網(wǎng)絡(luò)收益隨寬容因子β值的增加而變小; C-HYA算法在BC∈［5.4，54］帶寬區(qū)間的網(wǎng)絡(luò)收益隨寬容因子β值的增加而穩(wěn)定下降并收斂，但是其網(wǎng)絡(luò)收益較小;當β= 0.9時，ESS-PFOA算法BC∈［5.4，54］帶寬具有最高的穩(wěn)定均衡網(wǎng)絡(luò)收益.

實驗3為基于演化博弈的抗振蕩信道分配策略與其它經(jīng)典抗振蕩的信道分配策略對比結(jié)果.仿真結(jié)果如圖6.

實驗3結(jié)果表明:

(1)在節(jié)點數(shù)量分別為1、8、12時，PCU-CA算法占優(yōu)，C-HYA算法的網(wǎng)絡(luò)收益隨節(jié)點數(shù)量變化穩(wěn)定變化.

(2)當網(wǎng)絡(luò)節(jié)點數(shù)量大于12時，ESS-PFOA算法的抗振蕩信道分配策略在提升網(wǎng)絡(luò)有效聚合吞吐量方面較其它算法明顯占優(yōu)，寬容因子β取值與網(wǎng)絡(luò)有效聚合吞吐量的增加成正比，網(wǎng)絡(luò)最大帶寬取值范圍對網(wǎng)絡(luò)穩(wěn)定性影響不明顯.

(3)分布式的抗振蕩信道分配策略比集中式的抗振蕩信道分配策略在網(wǎng)絡(luò)收益方面明顯占優(yōu)，當網(wǎng)絡(luò)寬容因子β取值為0.9時，基于演化博弈的抗振蕩信道分配策略的網(wǎng)絡(luò)收益和信道振蕩抑制率優(yōu)于PCU-CA、C-HYA算法.

5　總結(jié)與展望

本文從提升無線Mesh網(wǎng)絡(luò)的節(jié)點網(wǎng)絡(luò)效用和有效降低信道振蕩發(fā)生率的角度，展開無線Mesh網(wǎng)絡(luò)信道分配策略的研究，提出了基于演化博弈的信道分配策略，并進行了仿真實現(xiàn)，仿真結(jié)果表明當網(wǎng)絡(luò)寬容因子β取值為0.9時，基于ESS-PFOA算法的信道分配策略在降低信道振蕩和提升網(wǎng)絡(luò)吞吐量方面較其它抗振蕩的信道分配策略明顯占優(yōu).本文基于Matlab仿真平臺完成實驗，與實際應用可能存在誤差，接下來的研究工作將展開多平臺仿真實驗，以及基于演化博弈的路由協(xié)議研究工作.

表5　各算法在不同網(wǎng)絡(luò)帶寬時的穩(wěn)定網(wǎng)絡(luò)收益結(jié)果

參考文獻

［1］王嵚琦.無線Mesh網(wǎng)絡(luò)路由協(xié)議關(guān)鍵技術(shù)的研究［D］.成都:國防科技大學計算機科學與技術(shù)系，2009.

［2］馮云霞.多接口無線mesh網(wǎng)絡(luò)動態(tài)信道資源分配關(guān)鍵問題研究［D］.上海:上海交通大學電子信息與電氣工程學院計算機系，2008，9.

［3］Li K Q.Analysis of cost and quality of service of timebased dynamic mobility management in wireless networks［J］.Wireless Networks，2014，20(2 ): 261 - 288.

［4］Raniwala A，Gopalan K，Chiueh T.Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks［J］.Mobile Computing and Communications Review，2004，8(2): 50 -65.

［5］Tao J，Shi H B，Huo Y，et al.A novel channel assignment scheme for multi-radio multi-channel wireless mesh networks［A］.Wireless Algorithms，Systems，and Applications Lecture Notes in Computer Science(Volume 6843)［C］.Berlin Heidelberg: Spring-Verlag，2011.261 -270.

［6］LIU J，XIE X F.Cognitive network channel allocation method based on the queuing delay and game analysis［J］.Journal on Communications，2012，33(6): 73 -81.

［7］林闖.基于隨機博弈模型的網(wǎng)絡(luò)安全分析與評價［M］.北京:清華大學出版社，2011.

［8］Vedantham B，Kakumanu S，Lakshmanan S，et al.Component based channel assignment in single radio，multi-channel ad hoc networks［A］.Proceedings of the 12th Annual International Conference on Mobile Computing and Networking［C］.NY，USA: ACM，2006.378 -389.

［9］Bianchi G.Performance analysis of the IEEE 802.11 distributed coordination function［J］.IEEE Journal on Selected Areas in Communications，2000，18(3): 535 -547.

［10］Mantri D，Prasad N R，Prasad R.BECPA: Bandwidth efficient cluster based packet aggregation in wireless sensor network［J］.Wireless Personal Communications，2014，76(3): 335 -349.

［11］Lehrieder F，Menth M.RCFT: A termination method for simple PCN-based flow control［J］.Journal of Network and Systems Management，2014，22(1): 12 -146.

［12］Chavarria R，Akyildiz I F.Radio access network energy minimization in multi-layer heterogeneous wireless systems［A］.IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications(PIMRC)［C］.USA: IEEE，2013.3259 -3263.

［13］Luong T，Lee B，Yeo C K.Channel allocation for multiple channels multiple interfaces communication in wireless ad hoc networks［A］.NETWORKING 2008 Ad Hoc and Sensor Networks，Wireless Networks，Next Generation Internet Lecture Notes in Computer Science(Volume 4982)［C］.Berlin Heidelberg: Springer，2008.87 -98.

［14］徐晶.多接口無限網(wǎng)絡(luò)信道分配與路由技術(shù)研究［D］.武漢:華中科技大學信息與通信工程學院，2011.

［15］Kyasanur P，Vaidya N H.Routing and link-layer protocols for multi-channel multi-interface ad hoc wireless networks［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2006，10(1): 31 -43.

［16］馮琳函，錢志鴻，金冬成.增強型的無線mesh網(wǎng)絡(luò)信道分配方法［J］.通信學報，2012，39(3): 44 -50.Feng Lin-Han，Qian Zhi-Hong，Jin Dong-Cheng.Research on enhanced channel assignment scheme in wireless mesh network［J］.Journal on Communications，2012，39(3): 44 -50.(in Chinese)

［17］杜振國，洪佩琳，周武旸，等.多射頻無線Mesh網(wǎng)中的接口分域信道分配［J］.電子學報，2011，38(10): 723 -726.Du Zhen-guo，Hong Pei-lin，Zhou Wu-yang，et al.ICCA interface-clustered channel assignment in multi-radio wireless mesh networks［J］.Acta Electronica Sinica，2011，38(10): 723 -726.(in Chinese)

［18］張暉，董育寧，楊龍祥，等.多媒體異構(gòu)Mesh網(wǎng)絡(luò)體系設(shè)計及跨層QoS路由算法研究［J］.電子學報，2010，38(10): 2436 -2440.Zhang Hui，Dong Yu-ning，Yang Long-xiang，et al.Architecture design for heterogeneous multimedia mesh networks and research on cross-layer QoS routing algorithm［J］.Acta Electronica Sinica，2010，38(10): 2436 -2440.(in Chinese)

［19］Gapone A，Carello G，F(xiàn)ilippini I.Solving a resource allocation problem in wireless mesh networks: A comparison between a CP-based and a classical column generation［J］.Network Optimization，2010，55(3):221 -233.

［20］Anandprabhu S，Himanshu G，Samir R D.Minimum interference channel assignment in multi-radio wireless mesh networks［J］.Mobile Computing，2008，7(12): 1459 -1473.

［21］Fuarte P B F，F(xiàn)adlullah Z M，Vasilakos A V，et al.Channel assignment on wireless mesh network backbone with potential game approach［A］.Game Theory for Networks Lecture Notes of the Institute for Computer Sciences，Social Informatics and Telecommunications Engineering(Volume 75)［C］.Berlin Heidelberg: Springer，2012.43 -56.

［22］李云，于季紅，尤肖虎.資源受限的機會網(wǎng)絡(luò)節(jié)點激勵策略研究［J］.計算機學報，2013，36(5): 947 -956.Li Yun，Yu Ji-Hong，You Xiao-hu.An incentive protocol for opportunistic networks with resources constraint［J］.Chinese Journal of Computers，2013，36(5): 947 - 956.(in Chinese)

［23］任娟.無線Mesh網(wǎng)絡(luò)的資源分配及擁塞控制算法研究［D］.北京:北京交通大學信號與信息工程學院，2011，01.

［24］Zhao H Q，Sun J.A study of algorithm for testing route oscillation based on algebraic method［J］.Chinese Journal of Computers，2007，30(10): 1763 -1769.

［25］沈士根，馬絢，蔣華，等.基于演化博弈論的WSNs信任決策模型與動力學分析［J］.控制與決策，2012，27(8): 1133 -1138.Shen Shigen，Ma Xuan，Jiang Hua，et al.Evolutionary game theory based trust strategy model and dynamics analysis in wireless sensor networks［J］.Control and Decision，2012，27(8): 1133 -1138.(in Chinese)

［26］Kim T S，Yang Y，Hou J C，et al.Resource allocation for QOS support in wireless mesh networks［J］.IEEE Transactions on Communications，2013，12(5): 2046 - 2054.(in Chinese)

［27］李明欣，陳山枝，謝東亮，等.異構(gòu)無線網(wǎng)絡(luò)中基于非合作博弈論的資源分配和接入控制［J］.軟件學報，2010，1(8): 2037 -2049.Li Mingxin，Chen Shanzhi，Xie Dongliang.Based on noncooperative game theory in heterogeneous wireless network resource allocation and access control［J］.Journal of Software，2010，1(8): 2037 -2049.(in Chinese)

［28］徐雷，徐大專，張小飛，等.WLAN中基于多包接收的跨層資源分配方案［J］.電子學報，2011，39(10): 2402 -2406.Xu Lei，Xu Da-Zhuan，Zhang Xiao-Fei，et al.Cross-layer resource allocation scheme for WLAN based on multi packet reception［J］.Acta Electronica Sinica，2011，39(10): 2402 -2406.(in Chinese)

［29］Pan W T.Combining PSO cluster and nonlinear mapping algorithm to perform clustering performance analysis: take the enterprise financial alarming as example［J］.Quality＆Quantity，2011，45(6): 1291 -1302.

［30］胡潔，趙祚喜，陳潤恩.分布式網(wǎng)絡(luò)中基于一致性的信道分配算法［J］.電子學報，2014，42(6): 1132 -1138.Hu Jie，Zhao Zuo-Xi，Chen Run-En.Consensus-based channel assignment in decentralized network［J］.Acta Electronica Sinica，2014，42(6): 1132 - 1138.(in Chinese)

［31］許力，陳志德，黃川，著.博弈理論在無線網(wǎng)絡(luò)中的應用［M］.北京:科學出版社，2012.

樂光學男，1963年11月出生，貴州天柱人.工學博士，嘉興學院數(shù)理與信息工程學院教授，碩士研究生導師，主要從事計算機網(wǎng)絡(luò)、無線Mesh網(wǎng)絡(luò)等方面的研究工作.

E-mail: guangxueyue-111@163.com

李明明女，1988年8月出生，湖北黃岡人.碩士，現(xiàn)為嘉興職業(yè)技術(shù)學院信息分院教師，主要從事計算機網(wǎng)絡(luò)、無線Mesh網(wǎng)絡(luò)等方面的研究工作.

E-mail: leeag201@126.com

The Anti-Channel Oscillation Channel Assignment Scheme Based on Evolutionary Game in Wireless Mesh Network

YUE Guang-xue1，2，LI Ming-ming1，2，3，DING Hui1，2，LIU Jian-sheng2，LUO Dan1，2，MA Bo-lin2
(1.College of Mathematics Physics and Information Engineering，Jiaxing University，Jiaxing，Zhejiang 314000，China 2.School of Science，Jiangxi University of Science and Technology，Ganzhou，Jiangxi 431000，China; 3.Jiaxing Vocational Technical College，Jiaxing，Zhejiang 314000，China)

Abstract:What caused channel oscillation among face-to route and face-to client have been analyzed.In order to reduce channel oscillation and promote throughput of channel assignment scheme，evolutionary game has been imported to joint with promoted fruit-flies optimal algorithm，a distributed channel assignment scheme based on ESS-PFOA algorithm has been proposed in wireless mesh network.The simulations reflect that network utility and channel oscillation ratio have been influenced by channel oscillation tolerance factor，and network topology presents homogeneous when β≤0.5，else it turns to be heterogeneous when β＞0.5 and β≥0.9.The result reflects that channel oscillation ratio has been fallen from 0.44 to 0.08，channel oscillation inhibition ratio has been restrained，and network utility has been improved in heterogeneous network.

Key words:wireless mesh network; multi-radio multi-channel; evolutionary game; channel oscillation; network utility

作者簡介

基金項目:國家自然科學基金(No.61572014);浙江省自然科學基金(No.LY15F020040，No.LQ15F010008，No.LY16F020028);浙江省嘉興市科技計劃(No.2012AY1027);中央財政支持地方高校發(fā)展專項-無線Mesh網(wǎng)絡(luò)若干關(guān)鍵技術(shù)研究

收稿日期:2014-05-12;修回日期: 2015-02-03;責任編輯:孫瑤

DOI:電子學報URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.026

中圖分類號：TP393

文獻標識碼：A

文章編號：0372-2112(2016)01-0176-10