基于演化博弈的抗?jié)i漪效應(yīng)信道分配算法

代紹慶,,

(1.嘉興職業(yè)技術(shù)學(xué)院 信息技術(shù)分院,浙江 嘉興 314000; 2.嘉興學(xué)院 數(shù)理與信息工程學(xué)院,浙江 嘉興 314000)

0 概述

無線Mesh網(wǎng)絡(luò)(Wireless Mesh Network,WMN)作為一種綜合接入技術(shù),在傳輸質(zhì)量、通信速率、網(wǎng)絡(luò)穩(wěn)定性方面較傳統(tǒng)無線網(wǎng)絡(luò)有更高的要求[1]。隨著多信道多射頻(Multi-channel Multi-radio,MCMR)技術(shù)的深入應(yīng)用,無線Mesh網(wǎng)絡(luò)通信技術(shù)對信道分配要求日趨嚴(yán)格。優(yōu)化網(wǎng)絡(luò)吞吐量、降低信道干擾率、提高網(wǎng)絡(luò)收益、穩(wěn)定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),是無線Mesh網(wǎng)絡(luò)信道分配技術(shù)的關(guān)鍵[2-3]。

無線Mesh網(wǎng)絡(luò)信道分配仍然面臨這些問題:1)單沖突域內(nèi)通信鏈路上的漣漪效應(yīng)問題[4-5],采用集中式信道分配算法如 C-HYA算法[2]、ELIA-OCA算法[6]等,一定程度上抑制了漣漪效應(yīng),但算法在動態(tài)無線Mesh網(wǎng)絡(luò)中適用度較低[7]。2)端到端節(jié)點上非重疊信道的分配問題,已有研究成果僅處理主干網(wǎng)的正交信道分配,僅通過網(wǎng)關(guān)熱點節(jié)點或射頻接口節(jié)點上的匯聚流量作為吞吐量,容易產(chǎn)生流量瓶頸問題,影響網(wǎng)絡(luò)穩(wěn)定性[8-9]。3)由于無線Mesh網(wǎng)絡(luò)節(jié)點存在自適應(yīng)性,導(dǎo)致信道分配需要考慮節(jié)點之間的競爭。利用博弈相關(guān)理論分析節(jié)點行為,是近年來無線Mesh網(wǎng)絡(luò)信道分配的有效研究方法之一[10-14]。

為有效抑制多射頻多信道無線Mesh網(wǎng)絡(luò)中單沖突域內(nèi)的漣漪效應(yīng),提升穩(wěn)定網(wǎng)絡(luò)吞吐量,本文基于演化穩(wěn)定均衡思想,分析端到端節(jié)點競爭行為,展開信道分配方案的優(yōu)化,聯(lián)合果蠅優(yōu)化算法,構(gòu)建一種啟發(fā)式的分布式信道分配算法。根據(jù)當(dāng)前的單沖突域內(nèi)節(jié)點信道分配問題,基于節(jié)點群體中信道干擾率,演化分析網(wǎng)絡(luò)性能并求解博弈穩(wěn)定均衡解。將穩(wěn)定演化的節(jié)點干擾率、節(jié)點的在線流量比率作為演化穩(wěn)定均衡條件,計算漣漪效應(yīng)發(fā)生率。通過仿真實驗,驗證節(jié)點的干擾比率在不同值情況下的網(wǎng)絡(luò)收益狀況,并通過網(wǎng)絡(luò)有效吞吐率和漣漪效應(yīng)發(fā)生率,對比已有抗?jié)i漪效應(yīng)信道分配算法[2,6,15-16]驗證算法的可行性和有效性。

1 國內(nèi)外研究現(xiàn)狀

大量研究證明,多信道多射頻環(huán)境中的信道分配技術(shù)是NP問題。針對局部信息展開端節(jié)點的信道分配,逐漸成為無線Mesh網(wǎng)絡(luò)信道分配的重點[6-8]。TAO分析了網(wǎng)關(guān)熱點問題和鏈路流量負(fù)載問題,提出了基于集中式的準(zhǔn)靜態(tài)信道分配方案,旨在提升網(wǎng)絡(luò)吞吐量[8]。文獻[9]提出了聯(lián)合組播路由的集中式信道分配方案,旨在處理網(wǎng)關(guān)熱點和射頻接口的混合流量轉(zhuǎn)發(fā),根據(jù)非重疊信道展開了干擾模型的設(shè)計。文獻[17]提出了以局部拓?fù)浜袜徲騼?nèi)信道利用率為觸發(fā)條件的自適應(yīng)集中式信道分配算法(Local Information based Channel Assignment,LICA),算法有效提升了靜態(tài)網(wǎng)絡(luò)中的網(wǎng)絡(luò)吞吐,但理想的啟發(fā)式條件難以適用于動態(tài)無線Mesh網(wǎng)絡(luò)。

通過最大化網(wǎng)絡(luò)效益來實現(xiàn)信道分配的優(yōu)化效果,是當(dāng)前信道分配的主要目標(biāo)。文獻[6]認(rèn)為無線Mesh網(wǎng)絡(luò)中容量下降問題導(dǎo)致了信道分配的必要性,著重分析了終端節(jié)點上流量不相關(guān)的非重疊信道分配技術(shù),提出了EP-OCA(End-to-End Partially)算法。算法的優(yōu)勢在于:分別從鄰居-接口、接口-信道2種通信方式建立節(jié)點無向圖和鏈路干擾模型,并計算鄰域內(nèi)節(jié)點的干擾率;算法的不足表現(xiàn)為:僅針對基于IEEE802.11b/g標(biāo)準(zhǔn)的3條非重疊信道展開信道分配,產(chǎn)生的網(wǎng)絡(luò)開銷較大,且信道分配基于集中式算法,在動態(tài)無線Mesh中容易導(dǎo)致沖突域內(nèi)的信道依賴問題[17]。文獻[16]指出了集中式信道分配算法無法滿足分布式節(jié)點通信的全局性,以匈牙利算法作為研究基礎(chǔ),提出基于一致性前向和反向拍賣機制的和分布式信道分配算法(Consensus-based Decentralized Auction for Channel Assignment,CDACA)。算法的優(yōu)勢體現(xiàn)在:以拍賣方式分析終端Mesh節(jié)點數(shù)量和其所在通信鏈路上空閑信道數(shù)量對信道分配的影響,通過前向拍賣實現(xiàn)。算法不足表現(xiàn)在:算法針對了離散的Mesh路由節(jié)點和Mesh終端節(jié)點展開局部不完全信息的拍賣機制,算法開銷大,同時引入了較大的信噪比。

隨著漣漪效應(yīng)在無線Mesh網(wǎng)絡(luò)信道分配過程中的發(fā)現(xiàn),漣漪效應(yīng)成為信道分配研究的重點[5,18]。文獻[7]通過分析信道分配過程中影響信道利用率的幾種網(wǎng)絡(luò)缺陷,認(rèn)為漣漪效應(yīng)是導(dǎo)致網(wǎng)絡(luò)有效帶寬下降和網(wǎng)絡(luò)不穩(wěn)定的主要原因,提出了LORA(Low-cost Ripple effect Attack)缺陷檢驗方法。文獻[2]根據(jù)鏈路優(yōu)先級的排隊順序分配信道,通過實驗驗證了算法能有效抑制靜態(tài)網(wǎng)絡(luò)中的漣漪效應(yīng),但算法預(yù)處理信道資源導(dǎo)致算法缺乏靈活性,且算法時間復(fù)雜度未知。文獻[15]提出了基于接收機制的分布式信道分配算法RBA(Receiver-based channel Allocation),算法側(cè)重于信道分配的路由路徑尋找,通過信道分配結(jié)果分析單沖突域內(nèi)的漣漪效應(yīng)。文獻[18]為了有效評價信道分配算法的性能,根據(jù)馬爾科夫鏈的動態(tài)信道分配(Dynamic Channel Assignment,DCA)算法評價模型,將網(wǎng)絡(luò)節(jié)點之間的干擾率作為評價指標(biāo),考慮了通信可靠性和網(wǎng)絡(luò)吞吐量,但未深入討論漣漪效應(yīng)問題[19]。

漣漪效應(yīng)是信道分配過程中影響信道分配效率的主要因素,其產(chǎn)生原因主要為通信鏈路上部分信道空閑、部分信道擁塞引起的通信范圍內(nèi)的數(shù)據(jù)交換失敗,其存在方式以群體繁殖為主,動態(tài)網(wǎng)絡(luò)中的漣漪效應(yīng)不僅在子節(jié)點之間繁殖,也存在于父節(jié)點之間[5]。如圖1所示,節(jié)點1從信道1切換至信道3時,由于信道之間存在連接依賴,節(jié)點2、節(jié)點3均切換至信道3,導(dǎo)致了節(jié)點2中止信道2,節(jié)點3中止信道1。漣漪效應(yīng)發(fā)生后,信道1、信道2通信中止,進入空閑狀態(tài),信道3疲于轉(zhuǎn)發(fā)數(shù)據(jù)產(chǎn)生擁塞,繼而在通信范圍內(nèi)廣播[3]。

圖1 漣漪效應(yīng)發(fā)生情況

隨著無線節(jié)點自適應(yīng)性的發(fā)現(xiàn)和深入研究,博弈理論逐漸應(yīng)用于無線網(wǎng)絡(luò)中[20-23]。文獻[4]針對動態(tài)的無線Mesh網(wǎng)絡(luò)引入博弈理論分析異構(gòu)網(wǎng)絡(luò)節(jié)點行為模式,模型實現(xiàn)了收斂、提升了網(wǎng)絡(luò)效益,但是增加了網(wǎng)絡(luò)開銷和延時。演化博弈作為一種全新的經(jīng)濟學(xué)博弈思想,在無線網(wǎng)絡(luò)中側(cè)重于分析節(jié)點群體性行為[20]。文獻[21]將演化博弈思想用于優(yōu)化無線傳感網(wǎng)絡(luò)中的分簇路由,建立基于簇節(jié)點的聯(lián)盟式演化博弈模型,根據(jù)網(wǎng)絡(luò)收益函數(shù)的動態(tài)方程展開穩(wěn)定均衡分析。文獻[22]將演化博弈思想用于分析無線傳感網(wǎng)節(jié)點的模糊信任機制,旨在提升網(wǎng)絡(luò)節(jié)點的信任值。

綜合而言,在不穩(wěn)定的動態(tài)網(wǎng)絡(luò)拓?fù)渲?采用演化博弈分析單沖突域內(nèi)節(jié)點集的信道分配具有一定的優(yōu)化效果。作為優(yōu)化網(wǎng)絡(luò)吞吐量的制約因素,有效抑制信道分配過程中的漣漪效應(yīng)問題并提升動態(tài)無線Mesh網(wǎng)絡(luò)的網(wǎng)絡(luò)吞吐率,需要從以下3點展開深入研究:

1)針對動態(tài)無線Mesh網(wǎng)絡(luò)中節(jié)點的自適應(yīng)特性,構(gòu)建適合動態(tài)網(wǎng)絡(luò)拓?fù)渲泄?jié)點群體的演化博弈環(huán)境,以實現(xiàn)節(jié)點的全局信道資源博弈過程。

2)分析節(jié)點之間產(chǎn)生漣漪效應(yīng)的原因,展開漣漪效應(yīng)問題的信道分配優(yōu)化方案。運用演化博弈穩(wěn)定均衡思想求解抑制漣漪效應(yīng)的穩(wěn)定網(wǎng)絡(luò)收益。

3)通過仿真實驗,記錄演化過程中發(fā)生漣漪效應(yīng)的節(jié)點數(shù)量,計算出漣漪效應(yīng)發(fā)生率,以最優(yōu)方式確定節(jié)點群體的穩(wěn)定狀態(tài)以獲取穩(wěn)定吞吐量,確保信道分配結(jié)果的可實施性。

2 穩(wěn)定均衡演化博弈建模

2.1 模型假設(shè)

為了有效抑制漣漪效應(yīng),提升網(wǎng)絡(luò)吞吐量,在非穩(wěn)定動態(tài)網(wǎng)絡(luò)拓?fù)渲?采用演化博弈分析單沖突域內(nèi)的節(jié)點行為,構(gòu)建WMN信道分配算法的數(shù)學(xué)模型和算法,現(xiàn)作如下假設(shè):

1)假設(shè)每一個節(jié)點均具有2個可用通信接口,同一時間節(jié)點的該射頻接口僅與同一信道通信。

2)拓?fù)渖系墓?jié)點均為理性、貪婪節(jié)點,所有節(jié)點均參與博弈過程。

3)假設(shè)穩(wěn)定均衡下的漣漪效應(yīng)發(fā)生率低于初始階段的漣漪效應(yīng)發(fā)生率,穩(wěn)定均衡狀態(tài)的網(wǎng)絡(luò)有效聚合吞吐率高于初始階段的網(wǎng)絡(luò)有效聚合吞吐量。

2.2 系統(tǒng)建模

在MCMR的無線Mesh網(wǎng)絡(luò)中,通信鏈路上存在的可用信道數(shù)量集合用C={cj∈C,j=1,2,…,M}表示,Mesh終端節(jié)點集用V={vi∈V,i=1,2,…,N}表示。因此,節(jié)點利用信道完成通信的算法表示為SV,C={Sv1,c1,Sv2,c2,…,Svi,cj,SvN,cM},設(shè)ki,j={0,1}表示節(jié)點vi射頻接口使用信道cj的狀態(tài),成功通信則ki,j=1,反之ki,j=0。如果節(jié)點vi與其鄰域節(jié)點通信成功,則其信道分配算法為Si,j={ki,1,ki,2,…,ki,M}。

對于任意信道cj∈C,依賴于共享信道的節(jié)點射頻數(shù)量為ncj,則沖突域內(nèi)最大有效聚合吞吐量為R(nj)[4]。此時,節(jié)點成功通信時其通信鏈路上的有效聚合吞吐率結(jié)果影響著節(jié)點的網(wǎng)絡(luò)收益。構(gòu)建節(jié)點的網(wǎng)絡(luò)收益函數(shù):

(1)

式(1)表示度數(shù)為Dg的節(jié)點vi的射頻接口nj經(jīng)過h跳成功與信道cj通信得到的網(wǎng)絡(luò)收益Rnj。其中,h表示數(shù)據(jù)流從當(dāng)前節(jié)點vi向下一個節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)產(chǎn)生的跳數(shù),Dg為干擾范圍內(nèi)源節(jié)點vi到目的節(jié)點vj的度數(shù)。文獻[7-8]分別給Mesh節(jié)點設(shè)置節(jié)點度數(shù)為2、3,而實際應(yīng)用中給定節(jié)點度數(shù)≤5,因此針對具有競爭特點的動態(tài)Mesh節(jié)點度數(shù)取值范圍設(shè)置為3≤Dg≤5。

(2)

(3)

根據(jù)式(2)、式(3),構(gòu)建節(jié)點穩(wěn)定網(wǎng)絡(luò)收益演化方程:

(4)

根據(jù)上述演化方程,構(gòu)建節(jié)點的網(wǎng)絡(luò)最大化收益的演化博弈模型。以節(jié)點vi在t時刻和t+1時刻選擇算法Si,j時的網(wǎng)絡(luò)收益,等價于其平均網(wǎng)絡(luò)收益的總支付與所有算法集合中獲得平均效用支付之差。則定義連續(xù)時間內(nèi)的穩(wěn)定演化動態(tài)方程如下:

(5)

式(5)表達了復(fù)制者動態(tài)系統(tǒng)中端節(jié)點vi選擇算法Si,j時產(chǎn)生的平均網(wǎng)絡(luò)收益與總收益之差。根據(jù)連續(xù)時間規(guī)律,式(4)演化結(jié)果可以修正為:

(6)

(7)

3 抗?jié)i漪效應(yīng)的信道分配算法

3.1 演化穩(wěn)定均衡算法

(8)

綜合而言,當(dāng)式(8)滿足了以下2種條件時,演化模型均能達到穩(wěn)定均衡狀態(tài)。

基于上述2種演化穩(wěn)定均衡狀態(tài),沖突域內(nèi)節(jié)點的網(wǎng)絡(luò)吞吐率受節(jié)點干擾率演化而變化。即節(jié)點干擾率高于節(jié)點的吞吐率時,通信鏈路受阻;如果節(jié)點干擾率低于或等于節(jié)點的吞吐率,通信鏈路將實現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)傳輸,保持網(wǎng)絡(luò)穩(wěn)定性、優(yōu)化網(wǎng)絡(luò)吞吐率。

3.2 改進的果蠅優(yōu)化算法

由于演化博弈理論應(yīng)用于無線網(wǎng)絡(luò)中,著重分析節(jié)點算法的選擇和突變問題[23],因此選擇適合于演化博弈模型的節(jié)點智能算法,以實現(xiàn)信道穩(wěn)定分配,成為Mesh網(wǎng)絡(luò)中信道分配的研究熱點[24-25]。粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法在無線網(wǎng)絡(luò)節(jié)點行為分析中應(yīng)用廣泛,但是算法本身參數(shù)復(fù)雜、操作有難度,果蠅優(yōu)化算法(Flies-flying Optimal Algorithm,FOA)基于粒子群算法完成了演化式計算[26]。在無線Mesh網(wǎng)絡(luò)的信道分配問題方面應(yīng)用果蠅優(yōu)化算法有以下優(yōu)勢:1)利用果蠅尋找食物的演化過程,分析無線Mesh網(wǎng)絡(luò)節(jié)點的信道選擇行為,用以實現(xiàn)無線Mesh網(wǎng)絡(luò)節(jié)點信道分配的演化過程。2)以果蠅按食物氣味尋覓路徑的方法為導(dǎo)線,計算節(jié)點集的漣漪效應(yīng)發(fā)生率,前者是通過一定范圍內(nèi)隨氣味變化切換尋覓路徑,后者是拓?fù)渲邪l(fā)生了漣漪效應(yīng)轉(zhuǎn)發(fā)信道實現(xiàn)重分配過程。

結(jié)合改進的果蠅優(yōu)化算法(Promoted Flies-flying Optimal Algorithm,PFOA),將演化過程歸一化,實現(xiàn)穩(wěn)定的網(wǎng)絡(luò)收益和WMN信道分配算法的演化式優(yōu)化。

當(dāng)系統(tǒng)達到穩(wěn)定均衡狀態(tài)(如式(5)),得到演化穩(wěn)定均衡解(如式(7)),計算得到演化穩(wěn)定均衡狀態(tài)下的網(wǎng)絡(luò)收益,并以此作為ESS-PFOA[3]((Evolutionary Stable Strategy Promoted Flies-flying Optimal Algorithm))算法的網(wǎng)絡(luò)收益指標(biāo)。因為網(wǎng)絡(luò)拓?fù)渲邪l(fā)生漣漪效應(yīng)的節(jié)點會切換信道,在ESS-PFOA算法中以演化穩(wěn)定拓?fù)鋬?nèi)未聚集的節(jié)點數(shù)量比率作為漣漪效應(yīng)發(fā)生率指標(biāo)。算法實現(xiàn)的主要步驟為:

1)網(wǎng)絡(luò)拓?fù)涑跏蓟?通信節(jié)點的群體位置隨機分配,其中,vi、cj分別表示節(jié)點和信道,Si,j表示節(jié)點的信道分配算法,也即適應(yīng)度函數(shù),Fi,j表示節(jié)點適應(yīng)度函數(shù)的判斷函數(shù)。在t時刻節(jié)點的網(wǎng)絡(luò)收益的果蠅優(yōu)化改進結(jié)果表示為:

(9)

2)果蠅尋徑函數(shù)Smelli,j(t),也即節(jié)點的網(wǎng)絡(luò)收益函數(shù)Fi,j(t)。其關(guān)鍵在于:計算在t∈[0,T]時間周期內(nèi)成功通信的節(jié)點數(shù)量、概率、接口總數(shù)以及干擾閾值;記錄穩(wěn)定狀態(tài)的節(jié)點網(wǎng)絡(luò)吞吐量;完成重復(fù)博弈。此步驟得到算法時間復(fù)雜度為O(logn2)。

3)保留穩(wěn)定均衡狀態(tài)下的節(jié)點轉(zhuǎn)折位置,計算未聚集的節(jié)點數(shù)量,作為漣漪效應(yīng)發(fā)生次數(shù)。此步驟得到算法時間復(fù)雜度為O(n2)。

綜上所述,ESS-PFOA算法時間復(fù)雜度為O(n2),即算法以聚集節(jié)點選擇信道的迭代次數(shù)為代價,實現(xiàn)網(wǎng)絡(luò)吞吐量的穩(wěn)定增長并有效抑制漣漪效應(yīng)發(fā)生。

3.3 算法收斂性分析

為了驗證ESS-PFOA算法可行性、收斂性,經(jīng)典收斂性算法的驗證實驗如圖2所示。通過200次迭代,Mesh網(wǎng)關(guān)的上行鏈路網(wǎng)絡(luò)吞吐量以10 Mb/s為基準(zhǔn)參考值,驗證PSO、FOA、PFOA、ESS-PFOA算法吞吐率的收斂性。

圖2 算法收斂性對比

實驗結(jié)果表明,4種算法收斂一致;ESS-PFOA算法的網(wǎng)絡(luò)穩(wěn)定吞吐率明顯高于PFOA算法,其收斂結(jié)果從小到大依次為2.795 9、3.919 9、4.311 9、9.799 7,ESS-PFOA算法較PSO算法高3.5倍、較FOA算法高2.5倍、較PFOA算法高2.3倍,網(wǎng)絡(luò)性能相對其他算法占優(yōu)。

4 仿真實驗與性能分析

為了驗證算法有效性,參考已有的仿真環(huán)境[6,8,16],假設(shè)網(wǎng)絡(luò)中有25個隨機的網(wǎng)絡(luò)節(jié)點部署在1 000 m×1 000 m區(qū)域中,每個節(jié)點配置2個無線射頻接口,通信半徑為R=250 m,干擾半徑為R1=450 m,非重疊的信道數(shù)量為12,網(wǎng)絡(luò)拓?fù)錇?×5,信道數(shù)量為12,節(jié)點度數(shù)為1～5,節(jié)點跳數(shù)為2～5。通過3組實驗驗證基于演化博弈的信道分配算法漣漪效應(yīng)發(fā)生率、網(wǎng)絡(luò)有效聚合吞吐量,綜合評價算法有效性。仿真環(huán)境描述及網(wǎng)絡(luò)仿真參數(shù)如表1所示。

表1 參數(shù)設(shè)定

4.1 信道干擾閾值分析

實驗1根據(jù)式(8)所得閾值為仿真參數(shù),驗證在不同的網(wǎng)絡(luò)帶寬下節(jié)點度數(shù)和跳數(shù)對網(wǎng)絡(luò)收益結(jié)果的影響。根據(jù)提出的無線Mesh網(wǎng)絡(luò)節(jié)點跳數(shù)范圍,給定h值范圍為1≤h≤5,聯(lián)合式(8)得到:

(10)

根據(jù)式(10)所示結(jié)果,分別選取Λ值為0.2、0.4、0.6、0.8、1.0,分別從5 Mb/s、10 Mb/s、20 Mb/s、50 Mb/s帶寬初值狀態(tài)展開12條非重疊信道的網(wǎng)絡(luò)收益分析,實驗結(jié)果如圖3所示。

圖3 干擾閾值Λ對網(wǎng)絡(luò)收益的影響結(jié)果

仿真結(jié)果表明:

1)基于這4種帶寬初值,5 Mb/s和10 Mb/s時的網(wǎng)絡(luò)收益存在波動,20 Mb/s和50 Mb/s時的網(wǎng)絡(luò)收益穩(wěn)定收斂;網(wǎng)絡(luò)初始帶寬在20 Mb/s～50 Mb/s的網(wǎng)絡(luò)穩(wěn)定性高于5 Mb/s～10 Mb/s,其中50 Mb/s帶寬初值下的網(wǎng)絡(luò)收斂速度明顯占優(yōu)。

2)干擾閾值在1處,即節(jié)點度數(shù)、跳數(shù)為H=5,Dg=5時;4種網(wǎng)絡(luò)拓?fù)潆m然均實現(xiàn)了穩(wěn)定收斂,但是這一演化穩(wěn)定狀態(tài)下的網(wǎng)絡(luò)收益均呈現(xiàn)理想化狀態(tài),這一結(jié)果更適用于信道分配結(jié)果不受漣漪效應(yīng)影響的靜態(tài)信道分配環(huán)境。

3)當(dāng)閾值小于1時,4種帶寬初值下的網(wǎng)絡(luò)收益效果和收斂情況均相似,但穩(wěn)定收斂的信道數(shù)量逐漸降低。當(dāng)干擾閾值為0.2時,網(wǎng)絡(luò)收益結(jié)果最小,此時節(jié)點度數(shù)、跳數(shù)為H=1,Dg=5,當(dāng)干擾閾值為0.8時,網(wǎng)絡(luò)收益結(jié)果最優(yōu),此時節(jié)點度數(shù)、跳數(shù)為H=4,Dg=5。

4)節(jié)點上有效聚合帶寬值隨信道數(shù)量的增加逐漸減少,4種帶寬初值狀態(tài)下的網(wǎng)絡(luò)收益均呈現(xiàn)一定程度的下降,網(wǎng)絡(luò)收益下降率為Λ=0.6≤Λ=0.2<Λ=0.4≤Λ=0.8。從收益效果來看,當(dāng)Λ=0.6時,4種帶寬初值下的網(wǎng)絡(luò)收益效果最優(yōu),此時節(jié)點度數(shù)、跳數(shù)為H=3,Dg=5。

4.2 網(wǎng)絡(luò)收益分析

上述實驗結(jié)果表明,在50 Mb/s帶寬初值下,當(dāng)信道干擾閾值為0.6時,滿足演化穩(wěn)定均衡條件。因此,基于H=3,Dg=5的實驗條件,以實現(xiàn)算法穩(wěn)定均衡為目標(biāo),實驗2分別從節(jié)點數(shù)量、信道數(shù)量對網(wǎng)絡(luò)有效聚合吞吐量的影響方面展開ESS-PFOA算法、EP-OCA算法、CDACA算法、C-HYA算法、RBA算法的網(wǎng)絡(luò)收益分析,算法的收益分析結(jié)果如圖4所示。并分別驗證了200次、500次迭代的網(wǎng)絡(luò)收益狀況,結(jié)果如圖5所示。相應(yīng)網(wǎng)絡(luò)穩(wěn)定收益數(shù)據(jù)如表2所示。

圖4 不同迭代次數(shù)下的網(wǎng)絡(luò)有效聚合吞吐量

圖5 不同信道分配算法的網(wǎng)絡(luò)有效聚合吞吐量

表2 不同信道分配算法的網(wǎng)絡(luò)收益結(jié)果 (Mb·s-1)

實驗結(jié)果表明:

1)如圖4所示,隨著信道數(shù)量的增加,5種信道分配算法的網(wǎng)絡(luò)收益均發(fā)生變化,其中收益效果依次為:ESS-PFOA,CDACA,EP-OCA,RBA,C-HYA;隨著節(jié)點數(shù)量的增加,5種信道分配算法的網(wǎng)絡(luò)收益效果依次為:ESS-PFOA,CDACA,RBA,C-HYA,EP-OCA。結(jié)果表明,隨著信道數(shù)量的增加,考慮端節(jié)點的信道分配算法所得網(wǎng)絡(luò)收益較其他算法明顯占優(yōu);隨著節(jié)點數(shù)量的增加,分布式算法的網(wǎng)絡(luò)收益較集中式算法的網(wǎng)絡(luò)收益明顯占優(yōu)。

2)如圖5所示,5種信道分配算法,在200次迭代次數(shù)下的穩(wěn)定網(wǎng)絡(luò)收益和500次迭代次數(shù)下的網(wǎng)絡(luò)穩(wěn)定收益差異均不明顯,均呈現(xiàn)了迭代次數(shù)越多,網(wǎng)絡(luò)穩(wěn)定收益越小的趨勢。網(wǎng)絡(luò)收益值在2種迭代次數(shù)下從大到小依次為:ESS-PFOA,EP-OCA,RBA,CDACA,C-HYA。

對比圖4、圖5結(jié)果與表2數(shù)據(jù),得出如下結(jié)論:

1)受信道數(shù)量影響的端到端節(jié)點的網(wǎng)絡(luò)收益較其他節(jié)點類型網(wǎng)絡(luò)收益高,受節(jié)點數(shù)量影響的分布式算法網(wǎng)絡(luò)收益較集中式算法高。

2)2種迭代下,由于EP-OCA算法針對端到端節(jié)點采用了非重疊信道分配,只在12條信道轉(zhuǎn)發(fā)時產(chǎn)生網(wǎng)絡(luò)開銷,相對于其他信道分配算法其網(wǎng)絡(luò)收益明顯占優(yōu),但是其收益結(jié)果呈現(xiàn)出了較大的波動性;CDACA算法因為采用的是一致性公平競爭的原則,其網(wǎng)絡(luò)收益較其他算法整體上呈現(xiàn)穩(wěn)定變化的趨勢,但其收益結(jié)果較其他算法明顯偏低;ESS-PFOA算法較另外2種分布式信道分配算法在網(wǎng)絡(luò)收益方面明顯占優(yōu)。

4.3 漣漪效應(yīng)發(fā)生率分析

為了有效分析ESS-PFOA算法在抑制單沖突域內(nèi)漣漪效應(yīng)的效果,結(jié)合實驗1、實驗2仿真數(shù)據(jù),展開多組驗證實驗,分析并計算平均的穩(wěn)定均衡環(huán)境下漣漪效應(yīng)發(fā)生率。此時,干擾閾值為0.6,即H=3,Dg=5,網(wǎng)絡(luò)有效初始帶寬值為50 Mb/s,經(jīng)過200次迭代后,基于式(9)所示的果蠅尋徑計算方法,計算信道分配過程中聚合節(jié)點上存在漣漪效應(yīng)而發(fā)生尋徑轉(zhuǎn)折數(shù)量,漣漪效應(yīng)發(fā)生率如圖6所示,漣漪效應(yīng)發(fā)生率數(shù)據(jù)結(jié)果如表3所示。

圖6 不同信道分配算法下漣漪效應(yīng)發(fā)生率情況

表3 漣漪效應(yīng)發(fā)生率對比結(jié)果

圖7 穩(wěn)定均衡條件下的網(wǎng)絡(luò)收益和漣漪效應(yīng)發(fā)生情況

圖6、圖7所示結(jié)果表明:

1)初始狀態(tài)下的穩(wěn)定網(wǎng)絡(luò)收益在迭代40次開始進入穩(wěn)定收斂,漣漪效應(yīng)發(fā)生率維持在28%左右;達到穩(wěn)定演化均衡狀態(tài)下的網(wǎng)絡(luò)收益在迭代20次時進入第1次穩(wěn)定收斂,迭代40次時進入第2次穩(wěn)定收斂,收斂效果較初始狀態(tài)下明顯占優(yōu),多次實驗驗證下的平均漣漪效應(yīng)發(fā)生率為8%,如圖7(漣漪效應(yīng)發(fā)生率2)所示,最理想狀態(tài)時得到了漣漪效應(yīng)發(fā)生率為4%,如圖6(f)所示。

2)經(jīng)過多次實驗驗證和網(wǎng)絡(luò)收益對比分析(如實驗2結(jié)果),不同算法得到的穩(wěn)定狀態(tài)下漣漪效應(yīng)發(fā)生率從大到小依次為:RBA,EP-OCA,CDACA,C-HYA,ESS-PFOA。

實驗結(jié)果表明:

1)5種信道分配算法中未發(fā)生漣漪效應(yīng)的節(jié)點成聚集狀態(tài),且所有算法的漣漪效應(yīng)在初始狀態(tài)高于穩(wěn)定狀態(tài);節(jié)點發(fā)生漣漪效應(yīng)的時間和位置是隨機的,證明了演化穩(wěn)定均衡環(huán)境的隨機性和節(jié)點演化特點。

2)表3結(jié)果表明,在靜態(tài)環(huán)境下的集中式信道分配算法中,漣漪效應(yīng)發(fā)生率明顯低于動態(tài)的分布式信道分配算法,其中C-HYA算法實現(xiàn)了漣漪效應(yīng)發(fā)生率由12%下降至0,但是動態(tài)的Mesh網(wǎng)絡(luò)中漣漪效應(yīng)不可避免。

3)在動態(tài)WMN中存在信道重疊和節(jié)點的貪婪、自私行為等不可預(yù)測問題,漣漪效應(yīng)的發(fā)生不可避免。因此,采用分布式信道分配算法的3種算法,在穩(wěn)定狀態(tài)時仍然存在漣漪效應(yīng)。其中ESS-FPOA算法實現(xiàn)的漣漪效應(yīng)在穩(wěn)定時最小,相對于其他信道分配算法,其漣漪效應(yīng)下降率最為明顯。

5 結(jié)束語

本文從提升無線Mesh網(wǎng)絡(luò)的吞吐量和降低漣漪效應(yīng)發(fā)生率角度出發(fā),展開基于演化博弈的分布式信道分配算法研究,建立了端節(jié)點的演化博弈模型,分析模型實現(xiàn)穩(wěn)定均衡的條件,并通過實驗驗證算法的有效性,平均漣漪效應(yīng)發(fā)生率從28%下降至8%,網(wǎng)絡(luò)吞吐量優(yōu)化明顯,有效提升了網(wǎng)絡(luò)吞吐率,抑制了漣漪效應(yīng)發(fā)生率,保證了網(wǎng)絡(luò)穩(wěn)定性。

[1] 林 闖.基于隨機博弈模型的網(wǎng)絡(luò)安全分析與評價[M].北京:清華大學(xué)出版社,2010.

[2] 馮琳函,錢志鴻,金冬成.增強型的無線Mesh網(wǎng)絡(luò)信道分配方法[J].通信學(xué)報,2012,33(10):44-50.

[3] 李明明.基于演化博弈的無線Mesh網(wǎng)絡(luò)信道分配策略研究[D].贛州:江西理工大學(xué),2014.

[4] 徐 晶.多接口無限網(wǎng)絡(luò)信道分配與路由技術(shù)研究[D].武漢:華中科技大學(xué),2011.

[5] RANIWALA A,CHIUEH T.Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network[C]//Proceedings of IEEE INFOCOM’05.Washington D.C.,USA:IEEE Press,2005:2223-2234.

[6] WANG Jihong,SHI Wenxiao.Partially overlapped channels-and flow-based end-to-end assignment for multi-radio multi-channel wireless mesh networks[C]//Proceedings of IEEE International Conference on Communications.Washington D.C.,USA:IEEE Press,2015:3770-3775.

[7] KYUNGJUN K,JONGHOON P.Performance analysis of the multi-channel wireless mesh networks[C]//Pro-ceedings of International Conference on Computer Applications for Communication,Networking.Washington D.C.,USA:IEEE Press,2012:161-166.

[8] JING Tao,SHI Hongbin,HUO Yan,et al.A novel channel assignment scheme for multi-radio multi-channel wireless mesh networks[C]//Proceedings of International Conference on Wireless Algorithms.Washington D.C.,USA:IEEE Press,2011:261-270.

[9] WANG Jihong,SHI Wenxiao,JIN Feng.On channel assignment for multicast in multi-radio multi-channel wireless mesh networks:a survey[J].China Communica-tions,2015,12(1):122-135.

[10] 樂光學(xué),李明明,丁 輝,等.無線Mesh網(wǎng)絡(luò)中基于演化博弈的抗振蕩信道分配策略[J].電子學(xué)報,2015,44(1):176-185.

[11] ROHITH D V,ARUN A K,MURTHY C S R.A non-cooperative game-theoretic approach to channel assignment in multi-channel multi-radio wireless networks[J].Wireless Networks,2011,17(6):411-435.

[12] 邱振謀,姚國祥,官全龍,等.多信道無線Mesh網(wǎng)絡(luò)的多播信道分配算法[J].計算機工程,2011,37(6):107-109.

[13] 劉 蔚,趙 宇,陳 銳.基于0-1規(guī)劃的網(wǎng)絡(luò)優(yōu)化模型及其在信道分配中的應(yīng)用[J].計算機工程,2016,42(5):93-101.

[14] LAI Xiaochen,LIU Quanli,WANG Wei,et al.An algorithm of channel assignment of MAC layer in Ad Hoc network based on dynamic game with perfect and complete information[C]//Proceedings of International Conference on Industrial Engineering & Other Applications of Applied Intelligent Systems.Berlin,Germany:Springer,2012:144-155.

[15] ALMASAEID H M,KAMAL A E.Receiver-based channel allocation in cognitive radio wireless mesh networks[J].ACM Transactions on Networking,2015,23(4):1286-1299.

[16] 胡 潔,趙祚喜,陳潤恩.分布式網(wǎng)絡(luò)中基于一致性的信道分配算法[J].電子學(xué)報,2014,42(6):1132-1138.

[17] KAUR A,SINGH P.Distributed channel assignment in 802.11:a survey[J].International Journal of Computer Applications,2014,105(1):20-22.

[18] 張招亮,陳海明,黃庭培,等.無線傳感器網(wǎng)絡(luò)中一種抗無線局域網(wǎng)絡(luò)干擾的信道分配機制[J].計算機學(xué)報,2012,35(3):504-517.

[19] 賈 杰,李燕燕,陳 劍,等.認(rèn)知無線網(wǎng)狀網(wǎng)中基于差分演化的功率控制與信道分配[J].電子學(xué)報,2013,41(1):62-67.

[20] 黃開枝,洪 穎,羅文宇.基于演化博弈機制的物理層安全協(xié)作方法[J].電子與信息學(xué)報,2015,37(1):193-199.

[21] 張 繼,張大方,謝 鯤,等.一種基于演化博弈的分簇協(xié)作路由算法[J].電子學(xué)報,2016,44(9):2158-2163.

[22] 梁鍾燁,曹奇英,沈士根.無線傳感網(wǎng)絡(luò)節(jié)點模糊信任演化模型[J].計算機應(yīng)用與軟件,2016,33(8):131-135.

[23] 劉保見,張效義,李 青.基于演化博弈論的無線傳感網(wǎng)監(jiān)測節(jié)點分群算法[J].計算機應(yīng)用,2016,36(8):2157-2162.

[24] MARTINEZ D M,ANDRADE A G.FPGA implementation of dynamic channel assignment algorithm for cognitive wireless sensor networks[J].International Journal of Electronics,2015,102(7):1177-1189.

[25] GHAHFAROKHI B S.Distributed QoE-aware channel assignment algorithms for IEEE 802.11 WLANs[J].Wireless Networks,2015,21(1):21-34.

[26] 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):231-237.