無線監測網絡中多信道優化選擇算法

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

(合肥工業大學 計算機與信息學院,安徽 合肥　230009)

?

無線監測網絡中多信道優化選擇算法

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

(合肥工業大學 計算機與信息學院,安徽 合肥230009)

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

關鍵詞:多信道無線網絡;多電臺;信道選擇;SPSA算法;監測質量

近年來,無線網絡技術日益蓬勃發展,其強開放性、高動態性和易擴展性在促進網絡應用的同時也帶來了一些隱患,例如網絡中用戶的流動性導致網絡資源難以合理分配,造成“瓶頸現象”;信道特征多變和傳輸不穩定導致網絡的魯棒性欠缺等。為了保證無線網絡運行的安全性與穩定性,無線網絡監測技術應運而生。

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

1相關工作

近年來,無線監測網絡已成為研究熱點,其研究內容包括監測設備的研制、監測網絡系統設計、多信道選擇、監測數據融合與推斷等[2-8],其研究目標主要是提高網絡監測質量(quality of monitoring, QoM)。在上述研究內容中,通過優化監測節點的信道選擇以監測更多的網絡用戶,是提高QoM的一種有效方法。

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

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

本文在上述研究工作的基礎上,引入同步擾動隨機逼近理論,設計了一種最大化QoM的多電臺監測節點信道選擇算法,并通過大量的仿真實驗和實際測試驗證了算法的有效性。

2問題建模

2.1網絡模型

假設一個無線監測網絡由m個監測節點sniffer(以下簡稱節點)組成,每個節點配有p個電臺,每個電臺有q個可選信道。無線網絡中有n個用戶,每個用戶也有q個工作信道。

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

(a)　無向二分圖GR

(b)　無向二分圖G

2.2問題描述

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

圖2中m×p列表示m個節點的m×p個電臺,q行表示q個信道,每個節點電臺只能選擇1個信道進行數據采集,表示為圖中的陰影塊。可見,可能的信道選擇方案a有qm×p種,這構成了問題的求解空間。

圖2　節點電臺在信道空間內的選擇

定義1節點電臺的監測質量(monitoring quality of node’s radio, MQNR)。當無線監測網絡工作在某一信道選擇方案a時,節點電臺sr的監測質量為:

(1)

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

當給定信道選擇方案a,在節點各電臺監測質量已知的基礎上,節點的監測質量(monitoring quality of node, MQN)為:

(2)

根據MQN可得整個無線監測網絡的監測質量QoM為:

(3)

本文的研究目標是尋找一種信道選擇方案使得網絡的監測質量最大,即尋找最佳信道選擇方案,即

a*=argmaxQ(a)

(4)

由以上問題建模可見,無線監測網絡中多電臺節點的信道選擇是一個復雜的多維優化問題,不能通過獨立地為每個電臺選擇最優信道而使其自身目標函數最大化。因為每個電臺都與該節點上的其他電臺在相同的地理位置上,它們具有空間的“強關聯性”,其通信半徑覆蓋完全相同的鄰居用戶;同時每個節點可能有多個鄰居節點,它們具有空間的“弱關聯性”,其通信半徑可能交叉覆蓋相同的鄰居用戶,所以每個電臺、每個節點的信道選擇都會對其他電臺和節點的數據收集產生影響,進而影響整個網絡的監測質量QoM。這是一個多維優化問題,且各維之間不獨立。

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

3基于SPSA的信道選擇算法

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

由于SPSA算法被設計用于求解目標函數的最小值,基于(1)～(3)式構造目標函數如下:

(5)

(6)

(7)

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

應用SPSA算法求解無線監測網絡中節點信道選擇問題,假設信道選擇為:

以及微擾幅度ck,ck計算公式為:

(8)

其中,c為可變因子,根據信道數進行取值;γ=0.101;k為迭代次數。

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

(9)

完成以上計算后,最終獲得2組整數選擇方案,并得到2組方案的目標函數值為:

(10)

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

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

(11)

(12)

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

當迭代次數k超過Imax或者各節點電臺的信道選擇已經趨于穩定時,算法迭代停止。此時取整后的ak即為最終信道選擇結果。

4實驗結果與分析

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

圖3　無線監測網絡布置

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

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

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

在監測節點具有不同電臺數和用戶數的情況下,進行了SPSA信道選擇算法實驗。多組實驗中算法求解結果的QoM比較如圖5所示。

圖5　不同電臺數和用戶數算法求解結果的QoM

由圖5可知,當監測節點的電臺數從1增加到2時,網絡監測質量QoM的提高量大于當電臺數從2增加到3時的,這是因為監測節點的鄰居用戶數有限,所以監測手段的提高并不能線性增加網絡的QoM。同時,在電臺數一定的情況下,1 000個用戶的網絡QoM明顯高于500個用戶的,而且隨著電臺數的增加,這種差距在增大,因為在用戶數大的網絡中監測節點的鄰居用戶相對較多,多電臺技術有利于捕獲更多用戶信息。這也顯示了多電臺技術在大規模網絡中的優勢。

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

圖6　2種算法的性能對比

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

本文還進行了可選信道數分別為6、9、12、15時的比較實驗。在用戶分布、節點分布以及數據傳輸概率相同的情況下,多個用戶分別工作在6、9、12、15個信道上,運行DA-OSCA算法與本文的SPSA算法實現對監測節點的優化信道選擇,并將結果對應的QoM進行對比。4組實驗統計結果見表1所列。由表1可知,隨著信道數的增加,算法需要更長的時間收斂到優化解。

表1　4組實驗統計結果

不同信道上2種算法的性能對比如圖7所示。由圖7可以看出隨著信道數的增加,2種算法的QoM都在減少,原因在于信道數增加時,工作在每個信道上的用戶數會減少,因此整個無線監測網絡的QoM相對也會減少。由于SPSA算法非常適合于多維優化問題,且全局搜索能力強,因此隨著信道數的增加,算法的求解性能優勢得以體現,當信道數為12時,SPSA(QoM=21.565)的性能已經優于DA-OSCA(QoM=21.284);當信道數為15時,SPSA算法的性能優勢更明顯。

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

5結束語

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

[參考文獻]

[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]夏娜,陳秀珍,徐朝農,等.多信道無線網絡中優化QoM吉布斯采樣信道選擇算法[J].計算機學報,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.

(責任編輯胡亞敏)

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

文獻標識碼：A

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

Doi:10.3969/j.issn.1003-5060.2016.02.007

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

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

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

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