一種基于信息熵的壓縮感知流量恢復(fù)算法

謝奇愛

(合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，合肥 230601)

在無線局域網(wǎng)絡(luò)(WALN)中，無線接入點(diǎn)(無線AP)的均衡負(fù)載能有效解決數(shù)據(jù)流量過大、網(wǎng)絡(luò)負(fù)荷過重等問題，其與網(wǎng)絡(luò)當(dāng)前的流量出入信息有關(guān)。如果流經(jīng)網(wǎng)絡(luò)的流量出入信息的粒度越小，那么調(diào)整負(fù)載均衡的效果就會(huì)越準(zhǔn)確。因此在無線局域網(wǎng)中，對(duì)移動(dòng)端用戶的網(wǎng)絡(luò)流量的分析與監(jiān)控最為關(guān)鍵。在以往的流量監(jiān)測(cè)研究中主要是使用一個(gè)提前定義的靜態(tài)的監(jiān)測(cè)頻率而不考慮網(wǎng)絡(luò)的突發(fā)情況，難免會(huì)出現(xiàn)高采樣頻率降低網(wǎng)絡(luò)性能，同時(shí)造成帶寬、存儲(chǔ)空間等資源的浪費(fèi)從而影響系統(tǒng)性能。如Manvi等人［1］提出了一種流量監(jiān)測(cè)機(jī)制，該機(jī)制在網(wǎng)絡(luò)節(jié)點(diǎn)通過使用移動(dòng)代理來緩和其計(jì)算代價(jià)以采集網(wǎng)絡(luò)流量信息。導(dǎo)致最終結(jié)果是用較高的流量采樣頻率換取了高的帶寬資源浪費(fèi)，同時(shí)，儲(chǔ)存大量的流量信息也會(huì)占用很大的存儲(chǔ)空間?；谝陨系膯栴}Adipat等人［2］又提出了一種動(dòng)態(tài)地基于實(shí)時(shí)的網(wǎng)絡(luò)帶寬消耗和網(wǎng)絡(luò)擁塞狀況調(diào)整監(jiān)測(cè)頻率的機(jī)制。即當(dāng)流量相對(duì)穩(wěn)定時(shí)，網(wǎng)絡(luò)流量監(jiān)測(cè)頻率就減小;當(dāng)負(fù)載比較差的時(shí)候，為避免加重網(wǎng)絡(luò)負(fù)載就降低網(wǎng)絡(luò)監(jiān)測(cè)頻率;當(dāng)流量變化較大時(shí)，網(wǎng)絡(luò)監(jiān)測(cè)頻率就增加以達(dá)到檢測(cè)網(wǎng)絡(luò)的突發(fā)變化。該方法同樣以消耗較大的存儲(chǔ)空間為代價(jià)。本次研究以校園無線局域網(wǎng)為采樣環(huán)境，根據(jù)網(wǎng)絡(luò)流量在時(shí)間和空間上存在的行為特性，提出一種基于信息熵的壓縮感知流量恢復(fù)算法，以更少的采樣觀測(cè)次數(shù)達(dá)到更好的恢復(fù)精度，從而調(diào)節(jié)網(wǎng)絡(luò)負(fù)載均衡，提高網(wǎng)絡(luò)性能。

1 相關(guān)技術(shù)

熵起初是從熱物理學(xué)領(lǐng)域中引用的一個(gè)概念，它表示了信源所包含的信息的多少。隨后應(yīng)用在很多的領(lǐng)域里如數(shù)論、控制論、概率論、計(jì)算機(jī)網(wǎng)絡(luò)等領(lǐng)域。將信息熵引入網(wǎng)絡(luò)應(yīng)用中形成的概念即網(wǎng)絡(luò)信息熵(用H(s)表示)。用公式(1)定義，統(tǒng)計(jì)不同源IP在一時(shí)間段內(nèi)出現(xiàn)次數(shù) mi，以m表示數(shù)據(jù)包的總數(shù)量，則各 IP出現(xiàn)概率為mi/m［3］。

壓縮感知即壓縮采樣是一個(gè)能對(duì)海量數(shù)據(jù)進(jìn)行稀疏性處理的新興的采樣方法。它具有高效采樣精確恢復(fù)的能力，其核心是將采樣和壓縮兩者相結(jié)合，通過開發(fā)信息具有的稀疏性，以遠(yuǎn)小于Nyquist采樣率的速率對(duì)信息進(jìn)行壓縮，并能在終端很好地恢復(fù)出原始信息。

圖1是傳統(tǒng)信號(hào)處理流程圖，圖2是壓縮感知的信號(hào)處理流程圖。

圖1 傳統(tǒng)信號(hào)處理流程圖

眾所周知，在壓縮感知理論中最關(guān)鍵的研究點(diǎn)主要包括直接影響到信息恢復(fù)精度的信號(hào)恢復(fù)算法的設(shè)計(jì)以及算法計(jì)算過程的復(fù)雜度等。目前壓縮感知信息恢復(fù)算法主要有3種:(1)凸優(yōu)化算法;(2)貪婪算法;(3)以上2種的混合算法。從恢復(fù)算法的精度和計(jì)算過程的復(fù)雜度這2個(gè)指標(biāo)來看以上3種算法各有優(yōu)勢(shì)。由于無線局域網(wǎng)用戶的網(wǎng)絡(luò)流量在時(shí)間和空間上具有相關(guān)性，以及無線網(wǎng)絡(luò)流量數(shù)據(jù)所具有的成簇的稀疏特性，因此可以利用該特性對(duì)信號(hào)進(jìn)行重構(gòu)并獲得更好的恢復(fù)結(jié)果，從而為壓縮感知理論提供輸入條件。

圖2 壓縮感知的信號(hào)處理流程圖

2 算法設(shè)計(jì)

眾所周知，矩陣奇異值分解是一種正向的思維方式:

研究文獻(xiàn)［4］中提出一種可逆的奇異值分解方法。即只要式(2)中的X^為原始矩陣X的r秩的近似解，則:

實(shí)際中，不直接求原始矩陣的近似解X^，而是求其分解矩陣L和R中的最小秩目標(biāo)函數(shù)等價(jià)轉(zhuǎn)化后最小Frobenius范數(shù)目標(biāo)函數(shù):

取權(quán)重系數(shù)為1，且用X直接代替A(X)，則:

由于無線用戶流量具有時(shí)間和空間的相關(guān)性，加入時(shí)間空間相關(guān)特征后得到:

式中:μ、β、Υ— 均是權(quán)重系數(shù);

E—時(shí)間約束矩陣，在其矩陣上每一行的元

素值就是該矩陣的時(shí)間約束系數(shù);

S— 空間約束矩陣，在其矩陣上每一行上的元素值都是該矩陣的空間約束系數(shù);

‖SLRT‖F(xiàn)— 同一時(shí)隙內(nèi)不同基站流量數(shù)據(jù)間的約束關(guān)系;

‖LRTET‖F(xiàn)—不同時(shí)隙內(nèi)同一基站流量數(shù)據(jù)間的約束關(guān)系。

從式(7)可以看出‖SLRT‖F(xiàn)和‖LRTET‖F(xiàn)能反映無線用戶原始網(wǎng)絡(luò)流量數(shù)據(jù)中所具有的時(shí)間空間相關(guān)性特征。

3 實(shí)驗(yàn)結(jié)果分析

以校園無線局域網(wǎng)獲取100 d的無線用戶流量數(shù)據(jù)集，把原始矩陣變成度量矩陣，再結(jié)合算法求出其估計(jì)矩陣，并將估計(jì)矩陣與其原始矩陣進(jìn)行對(duì)比。分析本算法與最近鄰算法，發(fā)現(xiàn)本算法對(duì)流量恢復(fù)重構(gòu)率高于最近鄰算法(見圖3)。

圖3 不同算法的性能比較圖

由圖3可以看出，本次研究提出的算法隨著測(cè)量矩陣完整性的降低，估測(cè)誤差值穩(wěn)定且較低，因此能可靠地恢復(fù)出無線用戶丟失的流量，達(dá)到較好的流量恢復(fù)效果。

4 結(jié)語

在獲得校園無線局域網(wǎng)大量真實(shí)數(shù)據(jù)的基礎(chǔ)上，根據(jù)無線用戶流量在時(shí)間空間上存在的一種相關(guān)性特征，提出一種基于信息熵的壓縮感知流量恢復(fù)算法。本算法較其他傳統(tǒng)算法而言有較高的恢復(fù)重構(gòu)率，能較好地進(jìn)行無線局域網(wǎng)的負(fù)載均衡處理，提高網(wǎng)絡(luò)的性能。在后續(xù)工作中將根據(jù)流量變化的趨勢(shì)特征，進(jìn)一步研究基于壓縮感知的流量預(yù)測(cè)方法，提高流量預(yù)測(cè)的精度，實(shí)現(xiàn)資源的高效利用和高效節(jié)能。

［1］ Manvi S S，Venkataram P.A Method of Network Monitoring by Mobile Agents［C］//Proctor of the International Conference Communication:Control and Signal Processing in the Next Millennium(CCSP-ZOOO)，2000:1-5.

［2］ Adipat B.Zhang DS.A Real-time Adaptive Traffic Monitoring Approach for Multimedia Content Delivery in Wireless Environment［C］//IEEE Systems，Man and Cybernetics Society.2003 IEEE International Conference on Systems，Man and Cybernetics Manchester:［s.n.］，2003:280-285.

［3］嚴(yán)承華，程晉，樊攀星.基于信息熵的網(wǎng)絡(luò)流量信息結(jié)構(gòu)特征研究［J］.技術(shù)研究，2014(3):28-32.

［4］ Roughan M，Zhang Y，Willinger W，et al.Spatio-temporal Compressive Sensing and Internet Traffic Matrices［J］.Networking，IEEE/ACM Transactions on，2012，20(3):662-676.

［5］王曉.壓縮感知在無線通信網(wǎng)絡(luò)數(shù)據(jù)釆集中的應(yīng)用研究［D］.杭州:浙江大學(xué)信息學(xué)院，2011:15-19.