基于关联规则挖掘的无线电频谱占用预测*

满方微,石 荣,何彬彬

(1.电子科技大学资源与环境学院,成都611731;2.电子信息控制重点实验室,成都610036)

应用基础与前沿技术

基于关联规则挖掘的无线电频谱占用预测*

满方微1,2,石 荣2,何彬彬**1

(1.电子科技大学资源与环境学院,成都611731;2.电子信息控制重点实验室,成都610036)

无线电频谱占用预测是认知无线电研究中的关键技术之一。实验采用中星世通CS-805F可搬移监测测向系统对四川省成都市的GSM900上行频段(890～915 MHz)和广播电视业务的部分频段(750～806 MHz)进行了为期24 h的实地监测,针对频谱监测中产生的大量历史数据,选用了部分周期模式的关联规则挖掘方法,挖掘频谱使用中存在的频繁模式,并由信道占用频繁模式生成强关联规则,得到特定业务频段的使用规律,从而实现无线电频谱的占用预测。实验结果表明,该方法在两个业务频段的占用预测均取得了较好的效果,准确率分别可达74.02%和83.98%。另外,实验指出了该算法的敏感参数并进行了简要分析。实验对研究认知无线电设备实施动态频谱接入和提高频谱使用率有一定意义。

认知无线电;无线电监测;频谱预测;关联规则挖掘;部分周期模式

1 引 言

无线电频谱是一种有限的自然资源,作为信息传输的载体,在无线电通信系统中发挥着重要的作用。近年来,随着无线电通信技术的发展,传统的固定频谱分配策略的弊端逐渐凸显:一方面,无线电通信业务的不断扩展使频谱资源显得越发紧张;另一方面,一系列测量研究表明[1-3],多数已授权的业务频段利用率较低,造成了频谱资源的浪费。

认知无线电(Cognitive Radio,CR)被认为是缓解频谱资源紧张的主要方法[4],其主要思想是通过寻找频谱空洞,让非授权用户在不影响授权用户正常工作的条件下实施动态频谱接入,从而提高频谱利用效率。其中,频谱预测是认知无线电研究中的关键技术之一。频谱预测是一种通过分析频谱测量产生的历史数据获取频谱使用规律,进而预测未来频谱占用状态的方法。认知用户在进行频谱感知前通过频谱预测可减少对授权用户的干扰和频谱空穴检测时间,有利于寻找到更多的频谱接入机会。同时,频谱预测可有效降低认知用户的功耗,提高认知系统稳定性[5]。

文献[6]采用基于回归分析的预测方法对信道状态进行预测,但该方法中如果Hessian矩阵非正定,则将导致函数无法收敛。文献[7]假定授权用户的使用服从泊松过程,进而提出一个基于动态频谱接入的隐马尔科夫模型(Hidden Markov Model, HMM),但这种方法由于需要知道状态的转移概率和频谱占用的先验知识,而实际信道的频谱往往是不可知或者是不完全可知的,所以限制了该方法的适用范围。还有一些研究建立了诸如ON/OFF周期[8]、多层感知器(Multilayer Perception,MLP)等模型下的频谱预测机制[9],这些预测方法虽然取得了一定的预测效果,但计算开销较大,不能满足认知无线电在短时间内实施动态频谱接入的实际需求。

数据挖掘技术是一种可以从海量历史数据中挖掘潜在规律的有效手段,已成为各领域研究的热点。近年来,研究人员将数据挖掘的方法引入到频谱预测中,包括反向传播(Back Propagation,BP)神经网络、径向基函数(Radial Basis Function,RBF)神经网络、聚类算法、支持向量机(Support Vector Machine, SVM)和关联规则挖掘等,并取得了一定进展。文献[10]将BP神经网络应用于频谱预测,这种方法可达到一定精度,但BP神经网络存在收敛速度慢且初始权值的选取存在不确定性等缺点。文献[11]提出了基于K-均值聚类算法的RBF神经网络预测方法,可以说是基于BP神经网络的频谱预测方法的改进。文献[12]研究了基于SVM的频谱预测模型,将之与BP神经网络方法进行了定量的对比分析。文献[2]提出利用频繁模式挖掘算法挖掘频谱状态序列中的频繁模式,进而实现频谱预测,实验结果预测正确率大于0.95。之后,文献[13]提出利用部分周期模式挖掘的方法进行频谱预测,并通过与全周期频繁模式挖掘算法和HMM模型进行对比展示了更好的预测效果。总体上,关联规则挖掘方法在频谱预测研究中表现了出色的性能。因此,本文选用部分周期模式的关联规则挖掘算法,结合成都地区的实际频谱监测数据进行了频谱的预测分析。

2 算法原理

2.1 关联规则挖掘算法

关联规则挖掘用于寻找大量数据中项集之间有趣的关联或相关关系。其典型应用是购物篮分析,通过分析顾客购物篮中商品之间的联系挖掘顾客的购物习惯。它是一个两步过程:找出所有频繁项集;由频繁项集产生强关联规则。

(1)找出所有频繁项集

当项集出现频率满足用户定义的最小支持度min_sup即为频繁项集。Apriori算法是最有影响的频繁项集挖掘算法之一,算法思路:首先找出频繁1-项集的集合L1,L1用于寻找频繁2-项集的集合L2,如此迭代,直到不能找到频繁k-项集。实际应用中主要分为连接步和剪枝步两步。连接步是将两个不同的频繁(k-1)项集Lk-1连接生成候选k-项集Ck的过程。然而,这些候选k-项集Ck未必都是频繁集,因此,为提高频繁集逐层产生的效率,需要剪掉非频繁候选集。剪枝步用到了Apriori性质——频繁项集的所有非空子集也必须是频繁的,即如果一个候选k-项集的(k-1)-子集不在Lk-1中,则该候选集也不是频繁的。

(2)由频繁项集产生强关联规则

方法如下:

Step 1 对每个频繁项集S,产生S所有非空子集S1。

Step 2 若式(1)成立,输出关联规则 S1⇒(S-S1):

式中:support(S)、support(S1)分别是包含项集S、S1的事务数;min_conf是最小置信度阈值[14]。

2.2 基于部分周期模式的关联规则挖掘算法

部分周期模式只描述了时间序列中某些点的特征而并非全部时间点,是相对松散的周期模式,相对于完全周期模式在现实世界中更具有普遍性。例如:在频谱使用方面,某些广播频段在上午9～11点占用度比较高,而其他时间段的使用无规律,这就是一种部分周期模式。

频谱占用研究中,一方面,频谱占用模式受传感器感知错误,噪声和上述用户的不规律活动等因素的影响;另一方面,信道占用状态序列(由0和1组成,“0”表示占用,“1”表示空闲)具有元素单一性和时序性两个明显特征。故传统Apriori算法在此并不适用。综上,本文采用了类Apriori算法对信道占用状态序列进行部分周期模式挖掘[13]。

在信道状态序列中我们将不确定较高的点的值用“*”表示(“*”可以匹配任意值),并将“*”连续出现的次数记为g,例如:子序列“11**001”“10 *00**11”中g均为2。实际研究中,当子序列的g值较大时再用来进行迭代寻找下一个频繁序列,必然会对结果造成较大的不确定性,因此,我们设定一个阈值,记为gm,规定任一子序列中的g≤gm。另外,我们用条件熵的概念来量化序列中对应点的值的不确定性,此处的条件熵用H(x|P)表示,P为状态子序列,长度为L。设信道状态序列S总长度为N,定义如下:

式中:I={0,1};Q为长为L+1的序列,两者的关系为Q=P⊕x,即P为Q的前缀;NQ为总状态序列中Q出现的次数;p(x|P)即子序列P后为状态为x的概率,当H(x|P)大于用户设定的阈值h0,即认为P后一位的值不确定性较大。

下面是研究采用的类Apriori算法中涉及到的几个概念。

定义2-1(子序列位置索引集) 子序列P的第一个元素在总序列S中的位置所组成的集合,记为HIL(P)(Head Index List of P)。

定义2-4(规则置信度) 关联规则的可靠程度,相当于Apriori算法中的置信度概念,即由P状态到Q状态的转移率,用conf(P⇒Q)表示。

定义2-5(频繁子序列) 用户设定的子序列的最小置信度用min_conf表示,如果conf(P)＞min_ conf,则认为P为频繁子序列。

定义2-6(强关联规则) 设序列Q为序列P的子模式,即P为Q的前缀,用户设定的最小规则置信度为Rule_min_conf,当conf(P⇒Q)＞Rule_min_ conf时认为生成的规则(P⇒Q)为强关联规则。

本文采用的类Apriori算法继承了Apriori算法的思想,包括:连接步,即通过长度为L的子序列P寻找长度为L+1的子序列Q,得到元素长度均为L+ 1的频繁序列集FL+1;剪枝步,压缩频繁子序列集。

(1)连接步

Step 1 通过长度为L的子序列P寻找长度为L+1的子序列,记Q0=P⊕0,Q1=P⊕1,计算其对应的支持度。伪代码如下:

Step 2 记Q2=P⊕″*″,生成频繁集FL+1,其伪代码如下:

(2)剪枝步

为了压缩候选集降低运算量,这里继承了“剪枝”的思想,但具体剪枝算法不同。方法如下:

假设P=P[1],P[2],…,P[l]是一个长度为l的频繁子序列,给定另一个长为l+1的频繁子序列T,且满足T=x⊕P,如果supp(P)=supp(T),那么则认为序列P可以被剪掉。例如:P=“01”,x=“1”,即T=“101”,当支持度满足上述条件时,即由P发展得到的任意子序列都有前缀x,因此,P为冗余序列。实现剪枝的伪代码如下(S[i-1]为总序列S中第i-1个元素):

(3)生成强关联规则

如果序列P和Q均为频繁序列,且满足定义2-6的条件,则可得到用于预测的关联规则P⇒Q。“*”的存在使得关联规则存在冗余,例如:P1=“010”,P2=“0*0”,Q=“0101”且P1⇒Q,P2⇒Q,此时,若conf(P2)＞conf(P1),则P1可以舍去。

3 基于数据挖掘的频谱预测

3.1 数据采集

实验采用中星世通CS-805F可搬移监测测向系统,天线架设在成都市区某建筑物四楼,在室内环境下进行数据采集,得到两个业务频段的数据: GSM900上行频段(890～915 MHz),信道宽度为200 kHz,信道数量为 124,48 h测量的数据量约1.7 GB,时隙数约为172 800;广播电视频段(470～806 MHz),信道宽度为100 kHz,信道数量3 360, 48 h测量的数据量约0.98 GB,时隙数约为6 400。实验过程中,我们取一天的数据作为实验集,另一天的数据作为测试集。另外,广播业务频段由于频带较宽,因此,选取了750～806 MHz的数据进行实验。

3.2 数据预处理

频谱测量数据预处理阶段,阈值法应用广泛且原理简单,因而本实验采用阈值法将测量数据转换为信道状态序列。转换原理为

式中:CS表示信道状态;“1”表示信道占用;“0”表示信道空闲;Pc表示接收机得到的信道能量值;P0为噪声阈值,其大小为对应频段测量期间的最小值与噪声容限之和。

以往的研究采用的噪声容限值为3～5 dB[2-3],考虑到频谱使用的区域性差异,为了得到成都地区的频谱噪声容限,本文做了如下分析:由频谱分配情况可知,地面接收机接收到的2 200～2 300 MHz的能量仅由噪声导致,这部分信道的能量电平最大值和最小值相差范围约为5 dB,如图1所示,即任何高于最小电平5 dB的测量值暗示了信号的存在。

图1　噪声信道能量最大最小值Fig.1 The maximum and minimum energy levels of noisy channel

对实测数据进行统计得到,实验选用的两个业务频段其占用度大小如图2和图3所示。

图2　GSM900上行频段各信道占用度Fig.2 Channel occupancy rate of GSM900 uplink

图3　广播电视频段(部分)各信道占用度Fig.3 Channel occupancy rate of partial broadcast TV bands

实验数据统计分析得,GSM900上行频段中占用度大于80%的信道只有4.8%,广播电视频段(750～806 MHz)中 48.6%的信道占用度小于60%,因此,两个频段总体占用度较低,具有二次开发价值。

3.3 结果分析

实验中数据预处理与挖掘算法均采用java编程语言实现,实现数据处理与挖掘分析的全程自动化。过程中将数据预处理得到的信道占用状态序列保存为txt文件。该文件作为实验中挖掘算法的输入,程序读入文件中的信道占用状态序列,根据文章2.2节阐述的算法原理,经过连接与剪枝得到信道占用的频繁模式,在频繁模式之间的关联性大于规则置信度阈值min_conf(P⇒Q)时,生成信道占用模式的关联规则。

挖掘结果评价上,实验参考文献[2]和文献[13],对得到的关联规则采取了如下预测验证方法:如果当前的序列与得到的强关联规则P⇒Q中的P相匹配,我们预测下一个时隙的状态序列为Q的可能性,如果下一时隙状态序列与Q匹配,则预测正确,预测正确次数(记为Correct)加1,否则预测错误,预测错误次数(记为False)加1;如果我们得到的频繁子序列中没有能与当前的状态序列P匹配时,则不做出任何预测,记为丢失,丢失次数记为Loss,丢失率记为Loss_Rate,计算方法如下:

本实验结果所讨论的频谱预测的总正确率(记为CorrectRate_Overall)计算方法如下:

即预测错误和预测丢失都认为是预测失效。

3.3.1 GSM900上行频段信道状态预测结果

实验过程中当gm=2,h0=0.7,子序列置信度min_conf=0.025,规则置信度 Rule_min_conf= 0.7时,

实验中子序列最小置信度min_conf的变化对预测的正确率影响较大,究其原因在于,子序列的最小置信度直接影响频繁序列的个数和形式(“*”的个数),最终影响得到的强关联规则条数,当关联规则较少时会造成预测丢失较多,但由于频繁模式中通配符“*”的存在,这样的影响并非线性关系,如图4所示。

图4　GSM900上行频段(890～915 MHz)信道状态预测结果Fig.4 Channel state prediction results in the GSM900 uplink bands

3.3.2 广播电视部分频段(750～806 MHz)信道状态预测结果

用测试集对结果进行验证发现,预测精度对子序列频繁最小置信度min_conf的值较为敏感,例如:当0.1≤min_conf≤0.127时,min_conf的大小与丢失率关系较大,故而影响总体正确率,当然这个结果从另外一个角度也说明,预测错误的情况较少,具体如图5所示。实验过程中当gm=2,h0=0.7,子序列置信度min_conf=0.044,规则置信Rule_min_conf= 0.8时,

图5　广播电视部分频段(750～806 MHz)信道状态预测结果Fig.5 Channel state prediction results in the partialbroadcast TV bands(750～806 MHz)

总体上,本实验选取的数据挖掘方法在频谱的预测上表现出了较好的性能。

4 结束语

本实验利用中星世通CS-805F监测测向系统对成都地区的频谱进行了测量研究,结果表明所测频段(GSM900上行频段和广播电视业务的部分频段)利用率偏低,因此,选用部分周期模式的关联规则挖掘方法结合上述实测数据对频谱占用状态进行

[1] DAS D,DAS S.A survey on spectrum occupancy measurement for cognitive radio[J].Wireless Personal Communications,2015,85(4):2581-2598.

[2] YIN S,CHEN D,ZHANG Q,et al.Mining spectrum usage data:a large-scale spectrum measurement study[J]. IEEE Transactions on Mobile Computing,2012,11(6): 1033-1046.

[3] XUE J,FENG Z,CHEN K.Beijing spectrum survey for cognitive radio applications[C]//Proceedings of 2013 IEEE 78th Vehicular Technology Conference(VTC Fall). Lasvegas,NV,USA:IEEE,2013:1-5.

[4] 朱江,段昂,郭兵.认知网中感知时间和功率控制的联合优化机制[J].电讯技术,2016,56(3):246-251.ZHU Jiang,DUAN Ang,GUO Bing.A joint optimization mechanism of sensing time and power control in cognitive networks[J].Telecommunication Engineering,2016,56 (3):246-251.(in Chinese)

[5] 李红岩.认知无线电系统中频谱可预测性的递归定量分析[J].电讯技术,2015,55(2):124-128.LI Hongyan.Recurrence quantification analysis of spectrum predictability in cognitive radio systems[J].Telecommunication Engineering,2015,55(2):124-128.(in Chinese)

[6] GORCIN A,CELEBI H,QARAQE K A,et al.An autoregressive approach for spectrum occupancy modeling and prediction based on synchronous measurements[C]//Proceedings of 2011 IEEE 22nd International Symposium on Personal Indoor and Mobile Radio Communications(PIMRC).Toronto,ON,Canada:IEEE,2011:705-709.

[7] AKBAR I A,TRANTER W H.Dynamic spectrum alloca tion in cognitive radio using hidden Markov models:Poisson distributed case[C]//Proceedings of 2007 IEEE SoutheastCon.Richmond,Virginia:IEEE,2007:196-201.

[8] BRAH F,DAYOUB I,VANDENDORPE L.Constrained resource allocation for OFDMA cognitive radio networks with primary users activity consideration[C]//Proceedings of 2012 International Symposium on Wireless Communication Systems(ISWCS).Paris,France:IEEE, 2012:766-770.

[9] ZHAO J L,WANG M W,YUAN J S.Based on neural network spectrum prediction of cognitive radio[C]//Proceedings of 2011 International Conference on Electronics, Communications and Control(ICECC).Ningbo:IEEE, 2011:762-765.

[10] TANG Y J,ZHANG Q Y,LIN W.Artificial neural network based spectrum sensing method for cognitive radio [C]//Proceedings of 2010 6th International Conference on Wireless Communications Networking and Mobile Computing(WiCOM).Chengdu:IEEE,2010:1-4.

[11] 吴建绒,胡津铭,秦继新.基于K-RBF神经网络的认知无线电频谱预测[J].电视技术,2014,38(5):105-108. WU Jianrong,HU Jinming,QIN Jixin.Prediction of spectrum based on K-RBF neural network in cognitive radio[J].Video Engineering,2014,38(5):105-108. (in Chinese)

[12] 徐元,鲁华祥,陈旭.基于支持向量机的认知无线电频谱预测方法[J].电信科学,2014,30(11):87-92. XU Yuan,LU Huaxiang,CHEN Xu.A SVM based spectrum prediction scheme for cognitive radio[J].Telecommunications Science,2014,30(11):87-92.(in Chinese)

[13] HUANG P,LIU C J,YANG X,et al.Wireless spectrum occupancy prediction based on partial periodic pattern mining[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(7):1925-1934.

[14] HAN J W,KAMBER M.数据挖掘:概念与技术[M].范明,孟小峰,译.北京:机械工业出版社,2006:149-158. HAN J,KAMBER M.Data mining:concepts and techniques[M].Translated by FAN Ming,MENG Xiaofeng. Beijing:China Machine Press,2006:149-158.(in Chinese)

满方微(1990—),女,河北衡水人,2014年于电子科技大学获学士学位,现为硕士研究生,主要研究方向为基于数据挖掘的无线电监测数据分析;

MAN Fangwei was born in Hengshui,Hebei Province,in 1990.She received the B.S.degree from University of Electronic Science and Technology of China in 2014.She is now a graduate student.Her research concerns data analysis in radio monitoring based on data mining.

Email:manfangwei@163.com

石 荣(1974—),男,重庆人,2004年于电子科技大学获博士学位,现为研究员,主要研究方向为电子对抗、通信与雷达系统;

Email:wyx1719@sina.com

何彬彬(1972—),男,湖南人,2005年于中国矿业大学获博士学位,现为电子科技大学教授、博士生导师,主要研究方向为定量遥感、空间数据挖掘。

HE Binbin was born in Hunan Province,in 1972.He received the Ph.D.degree from China University of Mining and Technology in 2005.He is now a professor and also the Ph.D. supervisor.His research concerns quantitative remote sensing and spatial data mining.

Email:binbinhe@uestc.edu.cn

Wireless Spectrum Occupancy Prediction Based on Association Rule Mining

MAN Fangwei1,2,SHI Rong2,HE Binbin1
(1.School of Resources and Environment,University of Electronic Science and Technology of China,Chengdu 611731,China; 2.Science and Technology on Electronic Information Control Laboratory,Chengdu 610036,China)

Wireless spectrum occupancy prediction is one of the key technologies in cognitive radio systems.A 24-hour spectrum measurement experiment is conducted in the uplink bands of GSM service(ranging from 890 MHz to 915 MHz)and the partial broadcasting services(ranging from 750 MHz to 806 MHz),in Chengdu,Sichuan Province.For a large scale of history data produced by radio monitoring systems,association rules mining method in partial periodic pattern is chosen to mine frequent patterns in spectrum usage which can be used for generating association rules and acquiring using patterns of specific spectrum,thus realizing wireless spectrum occupancy prediction.The experiment results prove that the method can achieve a satisfactory prediction accuracy in two service bands(74.02%and 83.98%respectively).Moreover,the experiment points out sensitive parameters of this algorithm and offers a brief analysis of the parameters.The research has a certain significance for cognitive radio devices to apply dynamic spectrum access technology and improving spectrum utilization.

cognitive radio;radio monitoring;spectrum prediction;association rule mining;partial periodic pattern

Foundation of Science and Technology on Electronic Information Control Laboratory(JS15120401535)

**通信作者:binbinhe@uestc.edu.cn binbinhe@uestc.edu.cn

SHI Rong was born in Chongqing,in 1974.He the Ph.D.degree from University of Electronic Science and Technology of China in 2004.He is now a senior engineer of professor.His research concerns electronic countermeasure,communication and radar system.

TN971;TN929.5

A

1001-893X(2016)11-1183-06

10.3969/j.issn.1001-893x.2016.11.001

2016-03-23;

2016-07-07

date:2016-03-23;Revised date:2016-07-07

电子信息控制重点实验室基金项目(JS15120401535)

了预测,相比基于马尔科夫链和BP神经网络等预测方法,不需要任何先验知识,只根据历史数据即可快速作出预测,且达到了较好的预测效果,对认知无线电设备实施动态接入具有实际参考意义。另外,相较之前的研究[13],本文指出了部分周期模式的关联规则挖掘算法在实际频谱预测中的强敏感参数并进行了简要分析。实验结果对部分阈值较为敏感,且不同的业务频段设定情况不同,因此,如何快速找到不同业务频段对应的阈值取值范围有待进一步研究。

引用格式:满方微,石荣,何彬彬.基于关联规则挖掘的无线电频谱占用预测[J].电讯技术,2016,56(11):1183-1188.[MAN Fangwei,SHI Rong,HE Binbin. Wireless spectrum occupancy prediction based on association rule mining[J].Telecommunication Engineering,2016,56(11):1183-1188.]