无线监测网络中多信道优化选择算法

丁　胜,　蒋建国,　夏　娜,　王佩佩

(合肥工业大学 计算机与信息学院,安徽 合肥　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-),男,安徽芜湖人,博士,合肥工业大学教授,硕士生导师.