基于關聯規則挖掘的無線電頻譜占用預測*

滿方微,石 榮,何彬彬

(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模型進行對比展示了更好的預測效果?？傮w上,關聯規則挖掘方法在頻譜預測研究中表現了出色的性能。因此,本文選用部分周期模式的關聯規則挖掘算法,結合成都地區的實際頻譜監測數據進行了頻譜的預測分析。

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.]