程 飛,劉 凱,丁文文,時 歡,張百戩

(西安電子科技大學(xué)計算機學(xué)院,陜西西安 710071)

測量報告數(shù)據(jù)的譜分析壓縮算法

程 飛,劉 凱,丁文文,時 歡,張百戩

(西安電子科技大學(xué)計算機學(xué)院,陜西西安 710071)

針對網(wǎng)絡(luò)帶寬難以滿足海量測量報告?zhèn)鬏斠?定義了測量數(shù)據(jù)的譜,并提出了測量報告數(shù)據(jù)的譜分析壓縮算法.該算法通過分析測量數(shù)據(jù)的譜,提出了對數(shù)據(jù)完成兩次排序的預(yù)處理方案,減少了數(shù)據(jù)冗余的間隔距離,以期提高上下文的命中率.其次,該壓縮算法構(gòu)建了測量數(shù)據(jù)的多個上下文模型,并作為單層神經(jīng)網(wǎng)絡(luò)的輸入結(jié)點.神經(jīng)網(wǎng)絡(luò)通過對每個上下文模型的預(yù)測概率線性組合,得到對下一比特的預(yù)測概率,并用真實的下一比特來調(diào)整對應(yīng)輸入結(jié)點的權(quán)重,提高匹配歷史信息的概率.實驗結(jié)果表明,在采用該壓縮算法后,算法的運行時間明顯減小,壓縮率隨被壓縮數(shù)據(jù)量的增大而提高.與其他通用壓縮算法相比,該算法能有效提高測量數(shù)據(jù)的壓縮率,從而達到減少網(wǎng)絡(luò)數(shù)據(jù)傳輸量的目的.

測量報告;數(shù)據(jù)壓縮;譜分析;神經(jīng)網(wǎng)絡(luò)

移動運營商需要對正式投入運行的通信網(wǎng)絡(luò)進行數(shù)據(jù)采集和分析工作[1],以洞悉通信狀態(tài)的動態(tài)變化.其主要收集用戶終端發(fā)出的測量報告(Measure Report,MR),獲知所轄的移動網(wǎng)絡(luò)狀態(tài).測量報告包含接入電平門限、切換電平門限、話務(wù)密度等性能參數(shù),并且記錄移動通信網(wǎng)絡(luò)的配置.測量報告數(shù)據(jù)采集過程如圖1所示,處在某蜂窩網(wǎng)中的用戶終端隨時會與基站保持通信,將測量報告通過基站和基站控制器傳輸并保存到數(shù)據(jù)采集服務(wù)器上.數(shù)據(jù)采集服務(wù)器周期性將數(shù)據(jù)遠程傳輸?shù)綌?shù)據(jù)中心,以便于全面地了解網(wǎng)絡(luò)的運行狀況,及時地發(fā)現(xiàn)網(wǎng)絡(luò)故障,并針對問題給出解決方案.隨著終端用戶增加,MR數(shù)據(jù)量出現(xiàn)大幅度的增長.數(shù)據(jù)采集服務(wù)器與數(shù)據(jù)中心之間的帶寬有限,難以適應(yīng)測量數(shù)據(jù)的海量傳輸.為減少數(shù)據(jù)傳輸量,需要對MR數(shù)據(jù)進行壓縮處理.

現(xiàn)有的文本壓縮算法主要是針對常規(guī)文本數(shù)據(jù)的壓縮過程[2-7].如文獻[2]使用字典編碼的機制,用偏移加長度的方式表示重復(fù)出現(xiàn)的字符串,結(jié)合哈夫曼編碼和Deflate來壓縮文本數(shù)據(jù).文獻[3-4]提出基于上下文模型的預(yù)測的自適應(yīng)性的統(tǒng)計數(shù)據(jù)壓縮技術(shù),該系列算法將不同階的上下文模型混合預(yù)測輸入序列的下個字符.文獻[6]中的壓縮算法思想與局部匹配預(yù)測(Prediction by Partial Matching,PPM)類似,與其不同的是,其利用多層神經(jīng)網(wǎng)絡(luò)將上下文模型混合,得到下個字符的預(yù)測概率.文獻[7]提出用伯羅斯惠勒變換(Burrows-Wheeler Transform,BWT)將重復(fù)性的字符序列轉(zhuǎn)換為同樣字母組成的字符串,再利用前向移動技術(shù)和哈夫曼編碼處理文本.

圖1　測量報告數(shù)據(jù)采集示意圖

與其他文本[8]和圖像[9-11]壓縮問題不同,測量數(shù)據(jù)是一種特殊的文本數(shù)據(jù).測量數(shù)據(jù)中冗余信息的間隔距離對這些算法提出了挑戰(zhàn).距離間隔是冗余信息在原始數(shù)據(jù)的偏移量的差值,表現(xiàn)為冗余信息之間其他字段所占用的字節(jié)數(shù).由于MR數(shù)據(jù)是由多個MR報文順序組成的,冗余信息的間隔距離分為報文間距和字段間距兩種情況,報文間距為數(shù)據(jù)冗余多的報文之間存在多個報文;相鄰報文的同一字段之間存在其他字段,這些字段形成了字段間距.當(dāng)冗余信息的間隔距離過長時,常規(guī)壓縮算法無法在有限的上下文模型的范圍內(nèi)查找成功,信息的數(shù)據(jù)編碼變長,導(dǎo)致數(shù)據(jù)壓縮效果不明顯.

筆者提出了一種基于譜分析的MR數(shù)據(jù)壓縮算法,該算法定義了MR的譜,同時根據(jù)譜分析的結(jié)果對MR數(shù)據(jù)采取兩次排序的預(yù)處理方案.該預(yù)處理過程分為多關(guān)鍵字歸并排序與合并字段排序兩個步驟.多關(guān)鍵字歸并排序提出對MR聯(lián)合TRXID和MXID字段聯(lián)合排序,提高相鄰報文的相似性,減少報文間距.在聯(lián)合字段排序的基礎(chǔ)上合并字段排序,減少字段間距.其次,壓縮算法采用神經(jīng)網(wǎng)絡(luò)模型,筆者提出了建立適合MR數(shù)據(jù)的上下文模型,每個上下文模型均輸出上下文預(yù)測概率,將這些概率預(yù)測混合得到下個字符的預(yù)測概率,并將混合的預(yù)測概率代入算術(shù)編碼器進行字符編碼.

1　MR 數(shù)據(jù)壓縮算法

1.1MR譜分析

數(shù)據(jù)收集服務(wù)器收集每個終端的MR報文發(fā)送給數(shù)據(jù)分析中心.若終端在某時間段內(nèi)的某些通信特征不發(fā)生明顯變化,該段時間的MR數(shù)據(jù)在時間上存在冗余,則稱為時間相關(guān)性.若某個蜂窩網(wǎng)中的終端數(shù)目可達到一定的密度,所監(jiān)測的信號范圍相互交疊,則稱為空間相關(guān)性.時空相關(guān)性[12]是MR存在數(shù)據(jù)冗余的原因,然而由于各個基站通信狀態(tài)和數(shù)據(jù)收集時間是相互獨立的,MR報文到達數(shù)據(jù)收集服務(wù)器時間也是相互獨立的,MR文件中的報文次序是隨機排列的.因此,存在含有冗余信息的報文在MR文件存儲順序是非相鄰的情況.為提高MR數(shù)據(jù)的壓縮率,可結(jié)合MR數(shù)據(jù)時空相關(guān)性調(diào)整報文的順序,減小冗余信息的間隔距離.MR報文包含若干字段,選取何種字段作為調(diào)整MR文件中報文次序的依據(jù)成為難題.假設(shè)從某個特定的時刻開始采集數(shù)據(jù),直到另一個固定時刻為止,獲得MR數(shù)據(jù)表示成矩陣形式為

其中,Xk=(xk1,xk2,…,xkm)T,(k∈N,N={1,2,…,n})是MR數(shù)據(jù)中第k個報文;xkj(k∈N,j={1,2,…,m})是第k個報文的第j字段,m為MR報文中字段總數(shù).矩陣Y的每行表示1個報文,每個列表示某個數(shù)據(jù)字段.向量Xk與Xj的歐式距離Sk,j表示報文Xk與Xj的相似性,Sk,j的數(shù)值越小,報文Xk與Xj相似性越大,則報文之間存在冗余信息的概率越大.MR數(shù)據(jù)是以報文為單位順序存儲的,選取不同的字段排序后,相鄰報文的相似性會發(fā)生改變.相鄰的報文相似性越大,MR數(shù)據(jù)中冗余距離減小的可能性就越大.為此,筆者提出了MR數(shù)據(jù)的譜dY的定義.dY是指為所有相鄰報文相似性的均值,可表示為

其中,Si,i+1表示第i個報文和第i+1個報文的相似性,譜的值越小,冗余數(shù)據(jù)的間隔距離就越小.矩陣Y按照m個字段分別排序后的譜均有變化,按第k個字段排序的MR譜記為dY(k).若能夠找到min dY(k),就能夠最大程度地減少數(shù)據(jù)冗余的距離.

以MR數(shù)據(jù)為實驗對象.該數(shù)據(jù)由360 096個MR報文構(gòu)成,按其所含59個不同字段分別調(diào)整報文順序,計算得到的排序后的MR譜dY(k),如圖2所示.圖2中,橫坐標(biāo)表示MR報文的所有字段,縱坐標(biāo)表示MR數(shù)據(jù)按某字段排序后的譜dY(k),水平虛線是表明為未進行字段排序的MR初始的譜dY(0),可作為排序后對比的基準(zhǔn).由圖2可知,按MXID排序的譜最小,TRXID排序次之.因此,MXID排序后,相鄰報文的冗余信息較大,或者說冗余信息的間隔距離較小.字段MXID表示基站號,字段TRXID表示載頻號.在同一個基站的范圍內(nèi)的用戶終端,MR數(shù)據(jù)中的基站號相同,具有空間相關(guān)性;一個基站內(nèi)不同用戶設(shè)備(User Equipment,UE)被分配的載頻號不同,MXID和TRXID相同的報文表示同一UE的MR消息,具有時空相關(guān)性.以上按不同字段排序后的MR相關(guān)性的分析方法,稱為譜分析.

圖2　MR數(shù)據(jù)的譜分析

1.2多歸并排序

依據(jù)MR譜分析,可對MR報文按MXID和TRXID多歸并排序.多communications Measure Report,GSM-MR)數(shù)據(jù)格式中,MXID和TRXID是相鄰字段,MXID字段位數(shù)是4 B,TRXID字段位數(shù)是2 B.將MXID和TRXID映射到一個64 bit的無符號整型數(shù)據(jù)中,高16 bit用0填充.在多字段排序中,依據(jù)每個報文中MXID和TRXID對應(yīng)的64位無符號整型為主鍵,將多

歸并排序變?yōu)橐淮螝w并排序,最好情況和最壞情況的時間復(fù)雜度都為n log(n).從矩陣角度來看,多

歸并排序就是根據(jù)列的數(shù)值重新排矩陣Y的行序列.

按照相關(guān)度大小選擇排序多個字段,第1個排序主字段為MXID,第2個排序主字段為TRXID.首先,依據(jù)MXID的值對MR數(shù)據(jù)進行歸并排序,改變數(shù)據(jù)的初始順序;當(dāng)MXID的數(shù)值相等時,依照TRXID再進行歸并排序.一次歸并排序的最好情況和最壞情況的時間復(fù)雜度均為n log n.多

分別排序是兩次歸并,時間消耗較大,時間復(fù)雜度是n log n≤T(n)≤2n log n.在全球移動通信系統(tǒng)測量報告(Global System for Mobile

1.3合并字段排序

多歸并排序后,相同字段間還存在字段間距,這會影響概率預(yù)測準(zhǔn)確度.多T,其中,歸并處理文件對應(yīng)的矩陣(Y′)T,即對n×m矩陣Y′按列排序生成m×n矩陣(Y′)T.

歸并排序后的MR數(shù)據(jù)稱為MR歸并數(shù)據(jù),記為Y′.將MR歸并數(shù)據(jù)中所有報文的同字段依次順序排列,減少字段間距.具體地說,將所有報文的第1個字段順序排列,接著將第2個字段順序排列,以此類推.對于矩陣將第1列代表的字段作為整體,接著把第2列代表的字段排在第1列的后面,即對矩陣Y′進行轉(zhuǎn)置變換(Y′)

1.4基于神經(jīng)網(wǎng)絡(luò)的多上下文編碼

將MR的各字段擴展為整字節(jié)的數(shù)據(jù)字段,筆者對此提出建立4類上下文模型,分別為半字節(jié)上下文模型、整字節(jié)上下文模型、雙字節(jié)上下文模型以及四字節(jié)上下文模型.其中,每個上下文模型通過匹配輸入比特得到的預(yù)測概率為Pi,i=1,2,…,4;4個上下文模型的預(yù)測概率Pi通過單層神經(jīng)網(wǎng)絡(luò)加權(quán)線性混合后得到的輸出預(yù)測概率為P.輸入Pi,神經(jīng)網(wǎng)絡(luò)的輸入結(jié)點可表示為

神經(jīng)網(wǎng)絡(luò)的預(yù)測概率P可表示為

其中,y是輸入的下一比特;y-P是預(yù)測誤差;γ為學(xué)習(xí)率,其取值不宜過大,取值為0.002.P作為算術(shù)編碼器編碼的依據(jù),設(shè)字符s出現(xiàn)的概率為P(s),那么為該字符分配一個在Q和Q+P(s)之間的數(shù)作為編碼,其中Q為所有在字符s之前出現(xiàn)的概率之和.基于神經(jīng)網(wǎng)絡(luò)的多上下文編碼該過程被記為XDMRC(XDMR Coding).綜合形成的MR壓縮算法步驟如下:

(1)對輸入的MR進行譜分析,按照TRXID和MXID進行多歸并排序,減少報文間距.

(2)對歸并排序后的MR進行合并字段排序,減少字段間距.

(3)4個上下文模型匹配已輸入字段,輸出每個模型的預(yù)測概率Pi,利用式(3)和式(4)得到神經(jīng)網(wǎng)絡(luò)的預(yù)測概率P,將P送入算術(shù)編碼器編碼.

(4)利用式(5)將讀入的下一比特y來調(diào)整神經(jīng)網(wǎng)絡(luò)中每個輸入結(jié)點的權(quán)重wi.

2　實驗結(jié)果及分析

筆者采取3組實驗來說明所提出的XDMR壓縮算法的有效性.XDMR壓縮算法采用C語言編寫,實驗測試環(huán)境的機器配置為3.0 GHz主頻的Intel Core i5-2320中央處理器,4 GB內(nèi)存計算機,預(yù)裝Windows 7 64位旗艦版操作系統(tǒng).其中,XDMR壓縮算法分為MR預(yù)處理和多上下文模型的算術(shù)編碼過程,簡記為Pre和XDMRC.

實驗1 測試預(yù)處理對MR數(shù)據(jù)壓縮效果的影響.實驗采用PPMd、PAQ8L、XDMRC、GZIP、LZMA和PPMd+pre、PAQ8L+pre、XDMRC+pre、GZIP+pre、LZMA+pre對3組原始的MR數(shù)據(jù)平均壓縮情況、預(yù)處理前后的壓縮率和相對壓縮率RC進行對比.RC=(Sorigi-Spre)/Spre,其定義了相對壓縮率MR數(shù)據(jù)平均壓縮情況,表示壓縮算法采用預(yù)處理相比未采用預(yù)處理壓縮效果的相對提升程度,Sorigin表示對未經(jīng)預(yù)處理MR壓縮后的文件大小,Spre表示對預(yù)處理的MR壓縮后的文件大小.如圖3所示,左斜線柱和右斜線柱分別表明未經(jīng)預(yù)處理的壓縮算法和預(yù)處理的壓縮算法針對3組MR數(shù)據(jù)的平均壓縮率.在未經(jīng)預(yù)處理的壓縮算法中,PAQ8L和XDMR對MR壓縮效果較明顯,平均壓縮率分別為18.27%和24.51%,RAR壓縮效果最差,平均數(shù)據(jù)壓縮率為37.56%.對采用預(yù)處理的壓縮算法中,PAQ8L+pre和XDMRC+pre算法的數(shù)據(jù)壓縮效果相對較好,平均數(shù)據(jù)壓縮率是13.09%和14.59%,bzip2+pre和RAR+pre算法的數(shù)據(jù)壓縮相對較差,平均數(shù)據(jù)壓縮率是20.97%和19.99%.未加預(yù)處理和結(jié)合預(yù)處理的壓縮算法對MR數(shù)據(jù)壓縮率的變化,表明所列的壓縮算法結(jié)合文中所提出的預(yù)處理方法能夠有效提升MR數(shù)據(jù)壓縮率.交叉線柱圖是對比兩種方式的相對壓縮率,表明預(yù)處理過程對MR數(shù)據(jù)壓縮提升效果的量化數(shù)據(jù).各壓縮算法采用預(yù)處理對MR數(shù)據(jù)的相對壓縮率在28.38%～46.84%之間,提升效果明顯.

圖3　預(yù)處理方法對MR數(shù)據(jù)壓縮效果

實驗2 測試對比預(yù)處理方法和未采用預(yù)處理方法以及MR文件大小與壓縮率的變化關(guān)系.實驗2與實驗3均是壓縮大小為5 MB、10 MB、15 MB、20 MB的12個MR數(shù)據(jù),每組有3個MR文件,壓縮率是每組平均壓縮率.如圖4所示,無預(yù)處理的壓縮算法對MR數(shù)據(jù)的壓縮率隨文件大小變化的曲線是基本上平行橫坐標(biāo)的直線,可認為壓縮率是恒定的數(shù)值.這說明無預(yù)處理的壓縮算法,壓縮率與文件大小的關(guān)系是恒定不變的.與此不同的是,從采用預(yù)處理的壓縮算法對MR的壓縮率與MR大小的變化曲線可以看出,MR數(shù)據(jù)的壓縮率隨MR文件的增大而變小.例如,PPMd+pre在4類大小不同數(shù)據(jù)的平均壓縮率取值分別是20.78%、19.65%、19.29%、19.09%,其中,5 MB大小的數(shù)據(jù)文件壓縮率最高,20 MB大小的數(shù)據(jù)文件壓縮率最低.壓縮率的降低原因是MR文件越大,存在冗余的報文可能性越增多.因此,采用預(yù)處理的壓縮算法的特點之一是MR數(shù)據(jù)的壓縮率隨文件大小緩慢降低,這也是未采用預(yù)處理的壓縮算法所不具備的特點.

圖4　預(yù)處理方法和未采用預(yù)處理方法數(shù)據(jù)大小與壓縮率的變化關(guān)系

實驗3 對比未采用預(yù)處理與采用預(yù)處理的壓縮算法消耗的壓縮時間.如圖5所示,PAQ8L和PAQ8L +pre消耗的壓縮時間是未采用預(yù)處理和采用預(yù)處理的壓縮算法中耗時最長的,所有的壓縮算法的壓縮耗時,都隨文件增大而增大.圖5表明采用預(yù)處理壓縮算法比未采用預(yù)處理的壓縮算法對于同樣大小的MR文件的壓縮耗時少,采用預(yù)處理的壓縮算法減少了冗余信息的距離,而且減少了冗余信息的匹配次數(shù),因此,采用預(yù)處理的壓縮算法的消耗的壓縮時間少于未采用預(yù)處理過程的壓縮算法.從3組實驗可知,XDMR是較為理想的測量報告壓縮算法.

3　結(jié)束語

筆者提出了基于譜分析的測量報告壓縮算法.該算法提出了MR數(shù)據(jù)譜分析的方法,并利用分析結(jié)果對MR數(shù)據(jù)進行兩次排序,再利用神經(jīng)網(wǎng)絡(luò)對測量報告建立上下文.實驗結(jié)果表明,在采用壓縮算法后,壓縮時間明顯減小,壓縮率隨被壓縮數(shù)據(jù)的增大而減小,對測量報告的壓縮效果結(jié)果明顯.

圖5　未采用預(yù)處理與采用預(yù)處理的壓縮算法消耗的壓縮時間

[1]AL R Y,KARMOUCH A.QoS-Based Composition of Service Specific Overlay Networks[J].IEEE Transactions on Computers,2015,64(3):832-846.

[2]ZIV J,LEMPEL A.A Universal Algorithm for Sequential Data Compression[J].IEEE Transactions on Information Theory,1977,23(3):337-343.

[3]CLEARY J G,WITTEN I H.Data Compression Using Adaptive Coding and Partial String Matching[J].IEEE Transactions on Communications,1984,32(4):396-402.

[4]SHKARIN D.PPM:One Step to Practicality[C]//Data Compression Conference Proceedings:2002.Piscataway: IEEE,2002:202-211.

[5]STEINRUECKEN C,GHAHRAMANI Z,MACKAY D.Improving PPM with Dynamic Parameter Updates[C]//Data Compression Conference Proceedings:2015.Piscataway:IEEE,2015:193-202.

[6]MAHONEY M.Adaptive Weighing of Context Models for Lossless Data Compression[R].Melbourne:Florida Institute of Technology,2005.

[7]SEWARD J.On the Performance of BWT Sorting Algorithms[C]//Data Compression Conference Proceedings:2000. Piscataway:IEEE,2000:173-182.

[8]BRISABOA N R,CERDEIRA-PENA A,NAVARRO G.XXS:Efficient XPath Evaluation on Compressed XML Documents [J].ACM Transactions on Information Systems,2014,32(3):13.

[9]劉凱,李云松,郭杰.高性能EBCOT編碼加速算法及其實現(xiàn)結(jié)構(gòu)[J].西安電子科技大學(xué)學(xué)報,2010,37(4): 587-593. LIU Kai,LI Yunsong,GUO Jie.High Performance EBCOT Algorithm and VLSI Architecture[J].Journal of Xidian University,2010,37(4):587-593.

[10]STRUTZ T.Adaptive Context Formation for Linear Prediction of Image Data[C]//IEEE International Conference on Image Processing.Piscataway:IEEE,2014:5631-5635.

[11]STRUTZ T.Entropy Based Merging of Context Models for Efficient Arithmetic Coding[C]//IEEE International Conference on Acoustics,Speech and Signal Processing.Piscataway:IEEE,2014:1991-1995.

[12]ACETO G,BOTTA A,PESCAPéA,et al.Efficient Storage and Processing of High-volume Network Monitoring Data [J].IEEE Transactions on Network and Service Management,2013,10(2):162-175.

(編輯:齊淑娟)

Spectrum analysis compression algorithm of measure report data

CHENG Fei,LIU Kai,DING Wenwen,SHI Huan,ZHANG Baijian
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

To solve to the problem that with the increment of the number of mobile users,the network bandwidth cannot meet the mass transfer of the measure report.This paper defines the conception of the spectrum of the measure report and proposes a spectrum analysis compression algorithm for the measure report.The algorithm utilizes two step sorting in order to reduce the distance between similar contents according to the analysis of the spectrum of measure report data.Furthermore,this algorithm employs several context models,which are regarded as the input nodes of the neural network.The prediction probability is calculated by the linear combination of the probability of each context model,and the weight in each link is tuned by the next bit in order to increase the possibility of matching.Experimental results reveal that the algorithm not only decreases the compression consuming time,but also ascends the compression ratio with the increment of the size of compression data.Compared with other competitors,this algorithm can effectively increase the compression ratio of the measure report to gain a better transfer time.

measure report;data compression;spectrum analysis;neural network

TP391

A

1001-2400(2016)04-0178-06

10.3969/j.issn.1001-2400.2016.04.031

2015-10-19

國家自然科學(xué)基金資助項目(61571345,61550110247);中央高校基本科研業(yè)務(wù)費專項資金資助項目(BDY191420);安徽省高等學(xué)校自然科學(xué)研究資助項目(KJ2014B14)

程 飛(1985-),男,西安電子科技大學(xué)博士研究生,E-mail:chengfei8582@163.com.