丁　勝,　蔣建國,　夏　娜,　王佩佩

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥　230009)

?

無線監(jiān)測網(wǎng)絡(luò)中多信道優(yōu)化選擇算法

丁勝,蔣建國,夏娜,王佩佩

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥230009)

摘要:無線監(jiān)測網(wǎng)絡(luò)中多電臺監(jiān)測節(jié)點(diǎn)通過捕捉和分析無線用戶的通信數(shù)據(jù),可以達(dá)到監(jiān)測網(wǎng)絡(luò)行為、診斷網(wǎng)絡(luò)故障和管理網(wǎng)絡(luò)資源的目的，而為多電臺監(jiān)測節(jié)點(diǎn)優(yōu)化選擇工作信道、最大化捕獲數(shù)據(jù)量、獲得最佳網(wǎng)絡(luò)監(jiān)測質(zhì)量(quality of monitoring,QoM)是一個(gè)關(guān)鍵問題。文章研究了一種基于同步微擾隨機(jī)近似(SPSA)的信道選擇算法。該算法在迭代過程中以隨機(jī)擾動(dòng)策略得到目標(biāo)函數(shù)的近似梯度,引導(dǎo)搜索過程逐步逼近最優(yōu)解;適合于復(fù)雜的多維優(yōu)化問題求解,收斂速度快、復(fù)雜度低。實(shí)驗(yàn)結(jié)果表明，該算法可以實(shí)現(xiàn)無線監(jiān)測網(wǎng)絡(luò)中多電臺監(jiān)測節(jié)點(diǎn)的信道優(yōu)化選擇,并且性能優(yōu)良。

關(guān)鍵詞:多信道無線網(wǎng)絡(luò);多電臺;信道選擇;SPSA算法;監(jiān)測質(zhì)量

近年來,無線網(wǎng)絡(luò)技術(shù)日益蓬勃發(fā)展,其強(qiáng)開放性、高動(dòng)態(tài)性和易擴(kuò)展性在促進(jìn)網(wǎng)絡(luò)應(yīng)用的同時(shí)也帶來了一些隱患,例如網(wǎng)絡(luò)中用戶的流動(dòng)性導(dǎo)致網(wǎng)絡(luò)資源難以合理分配,造成“瓶頸現(xiàn)象”;信道特征多變和傳輸不穩(wěn)定導(dǎo)致網(wǎng)絡(luò)的魯棒性欠缺等。為了保證無線網(wǎng)絡(luò)運(yùn)行的安全性與穩(wěn)定性,無線網(wǎng)絡(luò)監(jiān)測技術(shù)應(yīng)運(yùn)而生。

無線網(wǎng)絡(luò)監(jiān)測技術(shù)包括主動(dòng)監(jiān)測和被動(dòng)監(jiān)測2類,后者是目前被廣泛研究和應(yīng)用的方式。它將一系列監(jiān)測節(jié)點(diǎn)(sniffer)布置在無線網(wǎng)絡(luò)的用戶之間,以捕獲用戶的通信數(shù)據(jù),進(jìn)而評估網(wǎng)絡(luò)的狀況和性能。此類評估可被用來進(jìn)行網(wǎng)絡(luò)故障診斷、網(wǎng)絡(luò)入侵監(jiān)測、網(wǎng)絡(luò)資源管理等。由多個(gè)sniffer組成的網(wǎng)絡(luò)稱為“無線監(jiān)測網(wǎng)絡(luò)”。由于無線網(wǎng)絡(luò)的用戶電臺通常被調(diào)頻到多個(gè)非重疊信道上以增加網(wǎng)絡(luò)容量[1],因此，為無線監(jiān)測網(wǎng)絡(luò)中的sniffer(特別是多電臺sniffer)合理選擇信道,以監(jiān)測到盡可能多的用戶,捕獲到盡可能多的用戶通信數(shù)據(jù)成為了一個(gè)極具挑戰(zhàn)的關(guān)鍵問題。

1相關(guān)工作

近年來,無線監(jiān)測網(wǎng)絡(luò)已成為研究熱點(diǎn),其研究內(nèi)容包括監(jiān)測設(shè)備的研制、監(jiān)測網(wǎng)絡(luò)系統(tǒng)設(shè)計(jì)、多信道選擇、監(jiān)測數(shù)據(jù)融合與推斷等[2-8],其研究目標(biāo)主要是提高網(wǎng)絡(luò)監(jiān)測質(zhì)量(quality of monitoring, QoM)。在上述研究內(nèi)容中,通過優(yōu)化監(jiān)測節(jié)點(diǎn)的信道選擇以監(jiān)測更多的網(wǎng)絡(luò)用戶,是提高QoM的一種有效方法。

文獻(xiàn)[2]采用線性規(guī)劃(LP)算法進(jìn)行多信道選擇,并針對變化速率不同的2種動(dòng)態(tài)網(wǎng)絡(luò)提出了2種操作模式以減少能耗;文獻(xiàn)[3-6]中均假設(shè)在算法執(zhí)行前,無線網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和用戶的工作信道已知;文獻(xiàn)[3]提出一種基于吉布斯采樣的多信道選擇算法,實(shí)現(xiàn)了問題的分布式求解,以監(jiān)測節(jié)點(diǎn)的監(jiān)測質(zhì)量構(gòu)造本地能量函數(shù),計(jì)算各信道的選擇概率,完成對信道的優(yōu)化選擇;文獻(xiàn)[4]研究了2種不同的模式,第1種稱為“面向用戶”的模式,即監(jiān)測節(jié)點(diǎn)可以捕獲數(shù)據(jù)幀級信息,并可以甄別不同用戶的活動(dòng)，第2種稱為“面向監(jiān)測節(jié)點(diǎn)”的模式,即只有信道活動(dòng)的二進(jìn)制信息可以被捕獲,這2種模式定義了監(jiān)測節(jié)點(diǎn)不同的通信捕獲能力;文獻(xiàn)[5]采用蒙特卡洛增強(qiáng)的離散粒子群算法求解信道選擇問題,通過離散粒子群算法不斷搜索最優(yōu)編碼,獲得最優(yōu)信道選擇方案;文獻(xiàn)[6]提出一種基于多基因位量子免疫克隆的信道選擇算法,通過多次迭代,使抗體(信道選擇方案)的每個(gè)基因位(監(jiān)測節(jié)點(diǎn)信道選擇)獲得最優(yōu)解;文獻(xiàn)[7]提出了序列學(xué)習(xí)用戶活動(dòng)策略,求得最優(yōu)解對應(yīng)的信道選擇方案,但需要解決NP-hard問題而計(jì)算量巨大，文獻(xiàn)[8]在此基礎(chǔ)上提出了2種近似在線學(xué)習(xí)算法。

上述研究工作均針對“單電臺”監(jiān)測節(jié)點(diǎn)進(jìn)行信道選擇。隨著無線監(jiān)測網(wǎng)絡(luò)研究的深入和發(fā)展,學(xué)術(shù)界和工業(yè)界開始著眼于“多電臺”監(jiān)測節(jié)點(diǎn)的信道選擇問題。文獻(xiàn)[9-10]研究了在無線網(wǎng)絡(luò)固定的情況下,如何布置監(jiān)測節(jié)點(diǎn)并實(shí)現(xiàn)多電臺多信道的分配,并采用LP方法對該問題進(jìn)行求解。文獻(xiàn)[9-10]雖然對多電臺信道選擇問題進(jìn)行了建模,但在求解時(shí)仍簡化成單電臺問題進(jìn)行求解,忽略了監(jiān)測節(jié)點(diǎn)多電臺與單電臺的工作差別,沒有從本質(zhì)上解決多電臺監(jiān)測節(jié)點(diǎn)的信道選擇問題。

本文在上述研究工作的基礎(chǔ)上,引入同步擾動(dòng)隨機(jī)逼近理論,設(shè)計(jì)了一種最大化QoM的多電臺監(jiān)測節(jié)點(diǎn)信道選擇算法,并通過大量的仿真實(shí)驗(yàn)和實(shí)際測試驗(yàn)證了算法的有效性。

2問題建模

2.1網(wǎng)絡(luò)模型

假設(shè)一個(gè)無線監(jiān)測網(wǎng)絡(luò)由m個(gè)監(jiān)測節(jié)點(diǎn)sniffer(以下簡稱節(jié)點(diǎn))組成,每個(gè)節(jié)點(diǎn)配有p個(gè)電臺,每個(gè)電臺有q個(gè)可選信道。無線網(wǎng)絡(luò)中有n個(gè)用戶,每個(gè)用戶也有q個(gè)工作信道。

為了更加直觀地表達(dá)無線監(jiān)測網(wǎng)絡(luò)中節(jié)點(diǎn)電臺與用戶的關(guān)系,采用無向二分圖GR=(SR,U,E)的形式描述,如圖1a所示。E代表邊集合。節(jié)點(diǎn)電臺sr與用戶u存在一條邊e=(sr,u)∈E的條件是sr可以捕獲到u傳輸?shù)男畔?或者說u被sr監(jiān)測到。由于一個(gè)節(jié)點(diǎn)所獲得的監(jiān)測信息量是其所有p個(gè)電臺捕獲用戶傳輸信息的總和,因此可以將GR簡化為G=(S,U,E),如圖1b所示。在G中存在1條邊的條件是節(jié)點(diǎn)s可以監(jiān)測到u的傳輸信息,即稱u被s覆蓋。N(u)表示用戶u鄰居節(jié)點(diǎn)集合,N(s)表示節(jié)點(diǎn)s鄰居用戶集合。當(dāng)一個(gè)節(jié)點(diǎn)在另一個(gè)節(jié)點(diǎn)的通信范圍內(nèi),則稱這2個(gè)節(jié)點(diǎn)相鄰,這個(gè)節(jié)點(diǎn)是另一節(jié)點(diǎn)的鄰居節(jié)點(diǎn),B(s)表示節(jié)點(diǎn)s的鄰居節(jié)點(diǎn)集合。

(a)　無向二分圖GR

(b)　無向二分圖G

2.2問題描述

雖然一個(gè)節(jié)點(diǎn)的不同電臺是獨(dú)立地選擇信道,但是這些不同電臺處于相同的地理位置上,它們的鄰居節(jié)點(diǎn)信息和鄰居用戶信息都是相同的。信道選擇方案a可以用二維網(wǎng)格形式表示,如圖2所示。

圖2中m×p列表示m個(gè)節(jié)點(diǎn)的m×p個(gè)電臺,q行表示q個(gè)信道,每個(gè)節(jié)點(diǎn)電臺只能選擇1個(gè)信道進(jìn)行數(shù)據(jù)采集,表示為圖中的陰影塊?？梢?可能的信道選擇方案a有qm×p種,這構(gòu)成了問題的求解空間。

圖2　節(jié)點(diǎn)電臺在信道空間內(nèi)的選擇

定義1節(jié)點(diǎn)電臺的監(jiān)測質(zhì)量(monitoring quality of node’s radio, MQNR)。當(dāng)無線監(jiān)測網(wǎng)絡(luò)工作在某一信道選擇方案a時(shí),節(jié)點(diǎn)電臺sr的監(jiān)測質(zhì)量為:

(1)

(1)式表示當(dāng)節(jié)點(diǎn)s鄰居用戶中與節(jié)點(diǎn)電臺sr工作在同一信道的用戶越多,用戶傳輸概率越大,并且使用該信道監(jiān)測這些用戶的鄰居節(jié)點(diǎn)電臺越少,則節(jié)點(diǎn)電臺的監(jiān)測質(zhì)量越高。節(jié)點(diǎn)電臺的監(jiān)測質(zhì)量反映了可以與其通信的鄰居活動(dòng)用戶個(gè)數(shù)。

當(dāng)給定信道選擇方案a,在節(jié)點(diǎn)各電臺監(jiān)測質(zhì)量已知的基礎(chǔ)上,節(jié)點(diǎn)的監(jiān)測質(zhì)量(monitoring quality of node, MQN)為:

(2)

根據(jù)MQN可得整個(gè)無線監(jiān)測網(wǎng)絡(luò)的監(jiān)測質(zhì)量QoM為:

(3)

本文的研究目標(biāo)是尋找一種信道選擇方案使得網(wǎng)絡(luò)的監(jiān)測質(zhì)量最大,即尋找最佳信道選擇方案,即

a*=argmaxQ(a)

(4)

由以上問題建?？梢?無線監(jiān)測網(wǎng)絡(luò)中多電臺節(jié)點(diǎn)的信道選擇是一個(gè)復(fù)雜的多維優(yōu)化問題,不能通過獨(dú)立地為每個(gè)電臺選擇最優(yōu)信道而使其自身目標(biāo)函數(shù)最大化。因?yàn)槊總€(gè)電臺都與該節(jié)點(diǎn)上的其他電臺在相同的地理位置上,它們具有空間的“強(qiáng)關(guān)聯(lián)性”,其通信半徑覆蓋完全相同的鄰居用戶;同時(shí)每個(gè)節(jié)點(diǎn)可能有多個(gè)鄰居節(jié)點(diǎn),它們具有空間的“弱關(guān)聯(lián)性”,其通信半徑可能交叉覆蓋相同的鄰居用戶,所以每個(gè)電臺、每個(gè)節(jié)點(diǎn)的信道選擇都會(huì)對其他電臺和節(jié)點(diǎn)的數(shù)據(jù)收集產(chǎn)生影響,進(jìn)而影響整個(gè)網(wǎng)絡(luò)的監(jiān)測質(zhì)量QoM。這是一個(gè)多維優(yōu)化問題,且各維之間不獨(dú)立。

作為該問題求解的已知條件,所有節(jié)點(diǎn)和用戶的分布(位置)已知，節(jié)點(diǎn)的通信半徑已知，用戶的工作信道和傳輸概率pu可以通過全射頻掃描的方式獲得。

3基于SPSA的信道選擇算法

SPSA(simultaneous perturbation stochastic approximation)算法是Spall在1987年提出的一種隨機(jī)優(yōu)化算法[11],它利用“微擾”獲得目標(biāo)函數(shù)在某一點(diǎn)的近似梯度,避免了對目標(biāo)函數(shù)梯度的精確計(jì)算[12]。算法在過程統(tǒng)計(jì)、系統(tǒng)識別與參數(shù)估計(jì)、隨機(jī)優(yōu)化與決策等方面都有廣泛的應(yīng)用,而且均被證明具有實(shí)現(xiàn)方便、收斂速度快以及解的質(zhì)量高的優(yōu)點(diǎn)。本文引入該算法求解無線監(jiān)測網(wǎng)絡(luò)中節(jié)點(diǎn)信道選擇問題,即通過該算法搜索具有最大網(wǎng)絡(luò)監(jiān)測質(zhì)量QoM的信道選擇方案。

由于SPSA算法被設(shè)計(jì)用于求解目標(biāo)函數(shù)的最小值,基于(1)～(3)式構(gòu)造目標(biāo)函數(shù)如下:

(5)

(6)

(7)

為了便于公式化表達(dá),將信道C={c1,c2,…,cq}直接取下標(biāo)表示信道號。在算法迭代過程中,信道選擇向量a中的元素不一定是整數(shù),為了使SPSA算法順利運(yùn)行,將(6)式的整數(shù)約束條件松弛,變成(7)式中從1到q的連續(xù)點(diǎn)約束。在計(jì)算目標(biāo)函數(shù)時(shí)再對其進(jìn)行取整。

應(yīng)用SPSA算法求解無線監(jiān)測網(wǎng)絡(luò)中節(jié)點(diǎn)信道選擇問題,假設(shè)信道選擇為:

以及微擾幅度ck,ck計(jì)算公式為:

(8)

其中,c為可變因子,根據(jù)信道數(shù)進(jìn)行取值;γ=0.101;k為迭代次數(shù)。

在擾動(dòng)后形成的上述信道選擇方案中每一維的取值通常會(huì)出現(xiàn)小數(shù),因此采用四舍五入的方式取整,取整符號為R[·]。對向量的取整即為向量中所有元素分別取整。同時(shí),在擾動(dòng)取整后還會(huì)出現(xiàn)取值越界的情況,需要對這些元素進(jìn)行以下越界處理,即

(9)

完成以上計(jì)算后,最終獲得2組整數(shù)選擇方案,并得到2組方案的目標(biāo)函數(shù)值為:

(10)

其中,ak和Gk(ak)為向量,分別為第k次迭代后的信道選擇方案和該信道選擇方案對應(yīng)的目標(biāo)函數(shù)的近似梯度。

在SPSA算法迭代的過程中,使用(11)式來更新搜索新的信道選擇方案,即

(11)

(12)

其中,λk為步長因子；λ為大于0的常數(shù),同樣根據(jù)信道數(shù)量來確定;α=0.602；A≤10%Imax,Imax為預(yù)期的迭代總數(shù)；k為當(dāng)前迭代次數(shù)。

當(dāng)?shù)螖?shù)k超過Imax或者各節(jié)點(diǎn)電臺的信道選擇已經(jīng)趨于穩(wěn)定時(shí),算法迭代停止。此時(shí)取整后的ak即為最終信道選擇結(jié)果。

4實(shí)驗(yàn)結(jié)果與分析

無線監(jiān)測網(wǎng)絡(luò)如圖3所示。在1 000 m×1 000 m的區(qū)域內(nèi)隨機(jī)分布1 000個(gè)用戶(圖3中的細(xì)點(diǎn));按方陣結(jié)構(gòu)均勻布置25個(gè)無線監(jiān)測節(jié)點(diǎn)(圖3中的粗圓點(diǎn))。每個(gè)監(jiān)測節(jié)點(diǎn)配備2個(gè)電臺用于監(jiān)測區(qū)域內(nèi)用戶的通信活動(dòng)。整個(gè)區(qū)域被多個(gè)通信基站劃分成多個(gè)六邊形構(gòu)成的蜂窩結(jié)構(gòu)。每個(gè)蜂窩內(nèi)的基站和用戶工作在相同的信道上;任意2個(gè)相鄰的蜂窩內(nèi)的基站工作在不同信道上,以避免干擾。圖3中不同朝向的三角形表示不同的信道。假設(shè)節(jié)點(diǎn)的監(jiān)測半徑為200 m,有12個(gè)非重疊信道可供選擇,并且每個(gè)信道的帶寬相同。用戶的數(shù)據(jù)傳輸概率∈[0, 0.05](該區(qū)域內(nèi)有33個(gè)基站,平均每個(gè)基站覆蓋30個(gè)用戶,平均每個(gè)用戶的數(shù)據(jù)傳輸概率為0.033,取值范圍為[0, 0.05])。

圖3　無線監(jiān)測網(wǎng)絡(luò)布置

由于SPSA算法中的微擾幅度ck與步長因子λk分別為擾動(dòng)與尋優(yōu)2個(gè)步驟中的重要參數(shù),因此它們的取值會(huì)直接影響算法的性能。本文對微擾可變因子c與步長因子λ的選擇進(jìn)行了實(shí)驗(yàn)。在不同c與λ的取值情況下,算法的收斂速度和所求解的QoM均表現(xiàn)出一定的差異。在c=1,2,4時(shí)不同用戶數(shù)量下,算法收斂過程的比較如圖4所示。

圖4　不同c值時(shí)SPSA算法收斂過程的比較

當(dāng)c較小時(shí),微擾幅度小,算法收斂較慢;當(dāng)c較大時(shí),微擾幅度大,雖然能夠較快地收斂,但易出現(xiàn)斜率過大而錯(cuò)過最優(yōu)解的情況,因此需要選擇適當(dāng)?shù)奈_因子。由圖4可以看出，c=1時(shí)無論用戶數(shù)n為500、1 000還是1 500,算法收斂速度都相對較慢,而當(dāng)c=4時(shí)算法收斂較快,但是解的質(zhì)量相對較差,唯有折中選擇c=2時(shí)收斂速度與所求解的QoM值都相對較好。對于λ=15,20,25的算法性能比較實(shí)驗(yàn),由于實(shí)驗(yàn)結(jié)果的圖示與圖4基本一致,限于篇幅不再給出。當(dāng)λ較小時(shí)每次迭代的步長較小,收斂速度較慢;當(dāng)λ較大時(shí)每次迭代的步長較大,不僅容易錯(cuò)過最優(yōu)解,而且易出現(xiàn)陷入邊界的情況,因此也需要適當(dāng)選取λ的值以保證解的質(zhì)量。在本文實(shí)驗(yàn)中當(dāng)λ=20時(shí)算法性能較優(yōu)。

在監(jiān)測節(jié)點(diǎn)具有不同電臺數(shù)和用戶數(shù)的情況下,進(jìn)行了SPSA信道選擇算法實(shí)驗(yàn)。多組實(shí)驗(yàn)中算法求解結(jié)果的QoM比較如圖5所示。

圖5　不同電臺數(shù)和用戶數(shù)算法求解結(jié)果的QoM

由圖5可知,當(dāng)監(jiān)測節(jié)點(diǎn)的電臺數(shù)從1增加到2時(shí),網(wǎng)絡(luò)監(jiān)測質(zhì)量QoM的提高量大于當(dāng)電臺數(shù)從2增加到3時(shí)的,這是因?yàn)楸O(jiān)測節(jié)點(diǎn)的鄰居用戶數(shù)有限,所以監(jiān)測手段的提高并不能線性增加網(wǎng)絡(luò)的QoM。同時(shí),在電臺數(shù)一定的情況下,1 000個(gè)用戶的網(wǎng)絡(luò)QoM明顯高于500個(gè)用戶的,而且隨著電臺數(shù)的增加,這種差距在增大,因?yàn)樵谟脩魯?shù)大的網(wǎng)絡(luò)中監(jiān)測節(jié)點(diǎn)的鄰居用戶相對較多,多電臺技術(shù)有利于捕獲更多用戶信息。這也顯示了多電臺技術(shù)在大規(guī)模網(wǎng)絡(luò)中的優(yōu)勢。

為了充分驗(yàn)證本文SPSA算法在求解無線監(jiān)測網(wǎng)絡(luò)多電臺、多信道優(yōu)化選擇問題上的有效性,將其與文獻(xiàn)[9]的DA-OSCA算法進(jìn)行對比實(shí)驗(yàn)。DA-OSCA算法是一種線性規(guī)劃算法,通過松弛、取整2個(gè)基本步驟獲取信道選擇的最終解,由于是確定性算法,所以只運(yùn)行1次,其參數(shù)設(shè)置為:d=0.5,wn=pu,l=1。其中,d為由線性規(guī)劃問題轉(zhuǎn)換成二次規(guī)劃問題時(shí)引入的參數(shù);wn為用戶權(quán)重,相當(dāng)于本文算法中的pu;l為DA-OSCA雙層嵌套中求解松弛解的循環(huán)次數(shù)。本文SPSA算法的參數(shù)c取值為2,λ取值為20。2種算法的對比實(shí)驗(yàn)結(jié)果如圖6所示。

圖6　2種算法的性能對比

由圖6可知,DA-OSCA算法作為一種確定性算法可以快速求解出近似最優(yōu)解(QoM=21.284),但它是將多電臺信道選擇問題簡化為單電臺信道選擇問題并加以求解,忽略了監(jiān)測節(jié)點(diǎn)多電臺與單電臺的本質(zhì)差別,求解結(jié)果難以達(dá)到最優(yōu)。本文SPSA算法是一種真正的多電臺、多信道優(yōu)化算法,以迭代進(jìn)化的方式快速收斂到了更優(yōu)的解(QoM=21.565)。

本文還進(jìn)行了可選信道數(shù)分別為6、9、12、15時(shí)的比較實(shí)驗(yàn)。在用戶分布、節(jié)點(diǎn)分布以及數(shù)據(jù)傳輸概率相同的情況下,多個(gè)用戶分別工作在6、9、12、15個(gè)信道上,運(yùn)行DA-OSCA算法與本文的SPSA算法實(shí)現(xiàn)對監(jiān)測節(jié)點(diǎn)的優(yōu)化信道選擇,并將結(jié)果對應(yīng)的QoM進(jìn)行對比。4組實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果見表1所列。由表1可知,隨著信道數(shù)的增加,算法需要更長的時(shí)間收斂到優(yōu)化解。

表1　4組實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

不同信道上2種算法的性能對比如圖7所示。由圖7可以看出隨著信道數(shù)的增加,2種算法的QoM都在減少,原因在于信道數(shù)增加時(shí),工作在每個(gè)信道上的用戶數(shù)會(huì)減少,因此整個(gè)無線監(jiān)測網(wǎng)絡(luò)的QoM相對也會(huì)減少。由于SPSA算法非常適合于多維優(yōu)化問題,且全局搜索能力強(qiáng),因此隨著信道數(shù)的增加,算法的求解性能優(yōu)勢得以體現(xiàn),當(dāng)信道數(shù)為12時(shí),SPSA(QoM=21.565)的性能已經(jīng)優(yōu)于DA-OSCA(QoM=21.284);當(dāng)信道數(shù)為15時(shí),SPSA算法的性能優(yōu)勢更明顯。

圖7　不同信道數(shù)下2種算法性能對比

5結(jié)束語

本文研究了無線監(jiān)測網(wǎng)絡(luò)中多電臺監(jiān)測節(jié)點(diǎn)信道選擇問題,提出了一種基于SPSA的信道優(yōu)化選擇算法。此算法在迭代過程中以隨機(jī)擾動(dòng)策略得到目標(biāo)函數(shù)的近似梯度,以引導(dǎo)搜索過程逐步逼近最優(yōu)解。算法的運(yùn)行只需要已知監(jiān)測節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)、鄰居用戶的工作信道信息,這些信息可通過全掃頻的方式獲得。本文算法適合于復(fù)雜的多維優(yōu)化問題求解,復(fù)雜度低、收斂速度快。大量實(shí)驗(yàn)結(jié)果表明本文算法可以實(shí)現(xiàn)無線監(jiān)測網(wǎng)絡(luò)中多電臺監(jiān)測節(jié)點(diǎn)的信道優(yōu)化選擇,解的質(zhì)量較高,且在可選信道數(shù)較大時(shí)優(yōu)勢更為明顯。

[參考文獻(xiàn)]

[1]Urgaonkar R, Ramanathan S, Redi J, et al. Channel assignment processes for high density multi-channel multi-radio (MC-MR) wireless networks: US，20140307583 [P]. 2014-10-16.

[2]Shin D H, Bagchi S, Wang C C. Distributed online channel assignment toward optimal monitoring in multi-channel wireless networks[C]//Proceedings of IEEE INFOCOM 2012.IEEE, 2012:2626-2630.

[3]夏娜,陳秀珍,徐朝農(nóng),等.多信道無線網(wǎng)絡(luò)中優(yōu)化QoM吉布斯采樣信道選擇算法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(7):1214-1223.

[4]Nguyen H, Scalosub G, Zheng R. On quality of monitoring for multichannel wireless infrastructure networks [J]. IEEE Transactions on Moblie Computing, 2014, 13(3): 664-677.

[5]Du H Z, Xia N, Jiang J G, et al. A Monte Carlo enhanced PSO Algorithm for optimal QoM in multi-channel wireless networks [J]. Journal of Computer Science and Technology, 2013, 28(3): 553-563.

[6]Xia N, Xu L, Ni C C, et al. Optimal QoM in multichannel wireless networks based on MQICA[J]. International Journal of Distributed Sensor Networks,2013,44(2):131-144.

[7]Le T, Szepesvári C, Zheng R. Sequential learning for multi-channel wireless network monitoring with channel switching costs [J]. IEEE Transactions on Signal Processing, 2014, 62(22): 5919-5929.

[8]Zheng R, Le T, Han Z. Approximate online learning for passive monitoring of multi-channel wireless networks[C]//Proceedings IEEE INFOCOM,2013:3111-3119.

[9]Shin D H, Bagchi S. An optimization framework for monitoring multi-channel multi-radio wireless mesh networks[J]. Ad Hoc Networks,2013,11(3):926-943.

[10]Shin D H, Bagchi S. Optimal monitoring in multi-channel multi-radio wireless mesh networks[C]//Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing.ACM,2009:229-238.

[11]Spall J C. Introduction to stochastic search and optimization:estimation, simulation, and control [M]. Wiley -Interscience,2003:78-109.

[12]Wang Q, Spall J C. Rate of convergence analysis of discrete simultaneous perturbation stochastic approximation algorithm [C]//Proceedings of American Control Conference,Washington D C，2013:4771-4776.

(責(zé)任編輯胡亞敏)

Multi-channel selection algorithm in wireless monitoring networks

DING Sheng，JIANG Jian-guo，XIA Na，WANG Pei-pei

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

Abstract:In wireless monitoring networks, multi-radio wireless sniffers are distributed for capturing and analyzing user activities in order to realize network monitoring, fault diagnosis, resource management and so on. Therefore, it is a key topic to optimize the channel selection for sniffers to maximize the information collected, so as to maximize the quality of monitoring(QoM). In this paper, a simultaneous perturbation stochastic approximation(SPSA)-based solution is proposed in order to realize optimal channel selection. During iteration process, the random perturbation strategy is used to compute the approximate gradient of the objective function, which can lead the searching to the optimal solution. The algorithm is fast in convergence and low in complexity. The results of comparison experiments demonstrate that the proposed algorithm can realize the multi-channel selection in wireless monitoring networks with high QoM.

Key words:multi-channel wireless network; multi-radio; channel selection; simultaneous perturbation stochastic approximation(SPSA) algorithm; quality of monitoring(QoM)

中圖分類號:TP393

文獻(xiàn)標(biāo)識碼：A

文章編號：1003-5060(2016)02-0177-07

Doi:10.3969/j.issn.1003-5060.2016.02.007

作者簡介：丁勝(1979-),男,安徽淮北人,合肥工業(yè)大學(xué)講師;蔣建國(1955-),男,安徽寧國人,合肥工業(yè)大學(xué)教授,博士生導(dǎo)師;

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61100211);新世紀(jì)優(yōu)秀人才支持計(jì)劃資助項(xiàng)目(NCET-13-0768)和安徽高校省級自然科學(xué)研究資助項(xiàng)目(KJ2013A210)

收稿日期：2015-09-06；修回日期：2015-11-18

夏娜(1979-),男,安徽蕪湖人,博士,合肥工業(yè)大學(xué)教授,碩士生導(dǎo)師.