丁　勝,　蔣建國(guó),　夏　娜,　王佩佩

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

?

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

丁勝,蔣建國(guó),夏娜,王佩佩

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

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

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

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

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

1相關(guān)工作

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

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

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

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

2問(wèn)題建模

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

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

為了更加直觀地表達(dá)無(wú)線監(jiān)測(cè)網(wǎng)絡(luò)中節(jié)點(diǎn)電臺(tái)與用戶的關(guān)系,采用無(wú)向二分圖GR=(SR,U,E)的形式描述,如圖1a所示。E代表邊集合。節(jié)點(diǎn)電臺(tái)sr與用戶u存在一條邊e=(sr,u)∈E的條件是sr可以捕獲到u傳輸?shù)男畔?或者說(shuō)u被sr監(jiān)測(cè)到。由于一個(gè)節(jié)點(diǎn)所獲得的監(jiān)測(cè)信息量是其所有p個(gè)電臺(tái)捕獲用戶傳輸信息的總和,因此可以將GR簡(jiǎn)化為G=(S,U,E),如圖1b所示。在G中存在1條邊的條件是節(jié)點(diǎn)s可以監(jiān)測(cè)到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)　無(wú)向二分圖GR

(b)　無(wú)向二分圖G

2.2問(wèn)題描述

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

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

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

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

(1)

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

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

(2)

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

(3)

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

a*=argmaxQ(a)

(4)

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

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

3基于SPSA的信道選擇算法

SPSA(simultaneous perturbation stochastic approximation)算法是Spall在1987年提出的一種隨機(jī)優(yōu)化算法[11],它利用“微擾”獲得目標(biāo)函數(shù)在某一點(diǎn)的近似梯度,避免了對(duì)目標(biāo)函數(shù)梯度的精確計(jì)算[12]。算法在過(guò)程統(tǒng)計(jì)、系統(tǒng)識(shí)別與參數(shù)估計(jì)、隨機(jī)優(yōu)化與決策等方面都有廣泛的應(yīng)用,而且均被證明具有實(shí)現(xiàn)方便、收斂速度快以及解的質(zhì)量高的優(yōu)點(diǎn)。本文引入該算法求解無(wú)線監(jiān)測(cè)網(wǎng)絡(luò)中節(jié)點(diǎn)信道選擇問(wèn)題,即通過(guò)該算法搜索具有最大網(wǎng)絡(luò)監(jiān)測(cè)質(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)表示信道號(hào)。在算法迭代過(guò)程中,信道選擇向量a中的元素不一定是整數(shù),為了使SPSA算法順利運(yùn)行,將(6)式的整數(shù)約束條件松弛,變成(7)式中從1到q的連續(xù)點(diǎn)約束。在計(jì)算目標(biāo)函數(shù)時(shí)再對(duì)其進(jìn)行取整。

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

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

(8)

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

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

(9)

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

(10)

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

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

(11)

(12)

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

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

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

無(wú)線監(jiān)測(cè)網(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è)無(wú)線監(jiān)測(cè)節(jié)點(diǎn)(圖3中的粗圓點(diǎn))。每個(gè)監(jiān)測(cè)節(jié)點(diǎn)配備2個(gè)電臺(tái)用于監(jiān)測(cè)區(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)測(cè)半徑為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　無(wú)線監(jiān)測(cè)網(wǎng)絡(luò)布置

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

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

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

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

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

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

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

圖6　2種算法的性能對(duì)比

由圖6可知,DA-OSCA算法作為一種確定性算法可以快速求解出近似最優(yōu)解(QoM=21.284),但它是將多電臺(tái)信道選擇問(wèn)題簡(jiǎn)化為單電臺(tái)信道選擇問(wèn)題并加以求解,忽略了監(jiān)測(cè)節(jié)點(diǎn)多電臺(tái)與單電臺(tái)的本質(zhì)差別,求解結(jié)果難以達(dá)到最優(yōu)。本文SPSA算法是一種真正的多電臺(tái)、多信道優(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)對(duì)監(jiān)測(cè)節(jié)點(diǎn)的優(yōu)化信道選擇,并將結(jié)果對(duì)應(yīng)的QoM進(jìn)行對(duì)比。4組實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果見(jiàn)表1所列。由表1可知,隨著信道數(shù)的增加,算法需要更長(zhǎng)的時(shí)間收斂到優(yōu)化解。

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

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

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

5結(jié)束語(yǔ)

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

[參考文獻(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ú)線網(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)

中圖分類號(hào):TP393

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

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

Doi:10.3969/j.issn.1003-5060.2016.02.007

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

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

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

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