可逆Bloom Filter及其在長流識(shí)別應(yīng)用中的研究.pdf

1、長流識(shí)別對(duì)流量工程、網(wǎng)絡(luò)操作和網(wǎng)絡(luò)管理都有著重要意義。大量的流測(cè)量的研究表明：在各種網(wǎng)絡(luò)中，流的分布表現(xiàn)出明顯的重尾特征，即大多數(shù)的流(短流)僅擁有少量的報(bào)文，而少數(shù)的流(長流)卻擁有大量的報(bào)文。相較于流的總數(shù)，長流的個(gè)數(shù)非常少，但同時(shí)它們也占有著網(wǎng)絡(luò)流量的大比例。了解了網(wǎng)絡(luò)傳輸中長流的信息就能夠很好地掌握此次通信行為。在這篇論文中，我們研究并改進(jìn)可逆Bloom Filter，使它能夠更好地應(yīng)用到長流識(shí)別中。 本文首先介紹了Bl

2、oom Filter及其變體在網(wǎng)絡(luò)測(cè)量中的應(yīng)用情況。然后重點(diǎn)說明可逆Bloom Filter，它也是由Bloom Filter變形得到的，是近幾年新提出的一種網(wǎng)絡(luò)測(cè)量技術(shù)。文中的可逆Bloom Filter包括8個(gè)哈希函數(shù)，它們選取源串的部分比特位作為哈希函數(shù)的哈希值?？赡鍮loom Filter可以根據(jù)哈希函數(shù)的特性和流分布的重尾特征還原出長流完整流標(biāo)識(shí)和長度信息。所以，可逆Bloom Filter識(shí)別長流不需要再為每個(gè)哈希表項(xiàng)維護(hù)流

3、標(biāo)識(shí)。此外，可逆Bloom Filter為每個(gè)哈希函數(shù)分配獨(dú)立的存儲(chǔ)空間，消除了哈希過程中的內(nèi)部沖突。在流標(biāo)識(shí)的還原過程中，還原算法只作用在那些超過閾值的哈希短串上，相較于所有短串這些短串的個(gè)數(shù)是很小的，所以極大地減少了計(jì)算量。 本文使用從CERNET網(wǎng)絡(luò)上收集的Traces進(jìn)行離線模擬實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，文中提出的可逆Bloom Filter的算法可以精確地獲得長流的標(biāo)識(shí)信息和長度信息。 盡管學(xué)術(shù)界的努力使可逆Bloo

4、m Filter的研究和發(fā)展上都取得一定成果，但是可逆Bloom Filter仍然是網(wǎng)絡(luò)測(cè)量中的一種較新的技術(shù)，還需要優(yōu)化。本文的研究和改進(jìn)使可逆Bloom Filter能夠更有效地應(yīng)用到長流識(shí)別中。 獨(dú)立分量分析(ICA)作為統(tǒng)計(jì)信號(hào)處理和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域的新方法，因具有優(yōu)異的盲辨識(shí)、特征提取和表示能力，已經(jīng)日益廣泛地應(yīng)用于通信、語音提取、圖像增強(qiáng)和醫(yī)學(xué)信號(hào)處理等領(lǐng)域。碼分多址(CDMA)信號(hào)模型與ICA模型形式相似，將ICA適

5、用于多用戶檢測(cè)問題，直接從期望用戶的觀測(cè)數(shù)據(jù)出發(fā)，利用ICA可以將用戶信息序列從被多址干擾(MAI)污染的混合信號(hào)中分離出來。本文的主要工作如下： 1.利用矩陣?yán)碚撏茖?dǎo)了獨(dú)立分量分析的克拉美羅性能界。克拉美羅性能界是估計(jì)理論中無偏參數(shù)估計(jì)方差的下界，是評(píng)價(jià)參數(shù)估計(jì)性能最常用的度量。基于瞬時(shí)ICA模型推導(dǎo)了分離矩陣w的Fisher信息矩陣。為了準(zhǔn)確衡量算法的分離精度，定義了增益矩陣G，并推導(dǎo)了關(guān)于G的克拉美羅性能界?？死懒_性能界

6、為獨(dú)立分量分析算法性能評(píng)價(jià)提供了一種衡量準(zhǔn)則。 2.提出了廣義高斯變量生成算法和自適應(yīng)的FastICA算法?；谫が敺植茧S機(jī)變量，綜合運(yùn)用隨機(jī)變量變換法和舍選抽樣法，提出了一種簡便的廣義高斯分布隨機(jī)變量生成算法。該算法計(jì)算簡單，通過調(diào)整分布參數(shù)的值，可產(chǎn)生具有任何形狀參數(shù)和任何方差的廣義高斯分布隨機(jī)變量。為了克服傳統(tǒng)FastICA算法中要依據(jù)先驗(yàn)信息選定合適的非線性激活函數(shù)的缺點(diǎn)，提出了一種自適應(yīng)FastICA算法。該算法基于廣

7、義高斯模型，通過高斯模型的形狀參數(shù)的優(yōu)化和分離矩陣迭代結(jié)合，實(shí)現(xiàn)了激活函數(shù)向源信號(hào)評(píng)價(jià)函數(shù)的逼近，可以同步實(shí)現(xiàn)不同類型源信號(hào)的估計(jì)。并給出了算法的穩(wěn)定性分析和仿真實(shí)驗(yàn)。 3.提出了非參數(shù)廣義高斯核ICA算法。當(dāng)參數(shù)ICA算法不能分離信號(hào)時(shí)，基于廣義高斯核函數(shù)，提出了非參數(shù)廣義高斯核ICA算法。它在源信號(hào)密度函數(shù)全“盲”情況下，能實(shí)現(xiàn)正確分離，解決了如何選取估計(jì)信號(hào)評(píng)價(jià)函數(shù)的難題，可用于任意分布的源信號(hào)。廣義高斯核函數(shù)可以根據(jù)源信

8、號(hào)的高階統(tǒng)計(jì)自適應(yīng)地改變窗寬以適應(yīng)不同源信號(hào)的要求。 4.提出了基于負(fù)熵準(zhǔn)則的FastICA盲多用戶檢測(cè)算法。該算法使用四次冪函數(shù)，把基于負(fù)熵的非高斯性測(cè)度轉(zhuǎn)化為信號(hào)峰度的形式，降低了計(jì)算量。同時(shí)，算法充分考慮了各用戶信號(hào)的統(tǒng)計(jì)獨(dú)立性，在下行鏈路干擾用戶的擴(kuò)頻碼未知情況下，把目標(biāo)用戶的擴(kuò)頻碼作為訓(xùn)練序列，并用于初始化FastICA算法的分離向量，使用隨機(jī)梯度法進(jìn)行優(yōu)化計(jì)算，獲得了優(yōu)異的符號(hào)估計(jì)性能。對(duì)算法的計(jì)算復(fù)雜度的分析可以看

9、出，計(jì)算量隨著接收數(shù)據(jù)長度和用戶數(shù)的增加而增加。在同步CDMA信道中與傳統(tǒng)匹配濾波器、MMSE檢測(cè)算法比較，MAI較低的時(shí)該算法檢測(cè)性能與MMSE的性能接近；隨著MAI增加，其性能明顯優(yōu)于MMSE算法。 5.提出了基于非參數(shù)似然比準(zhǔn)則的盲多用戶算法。當(dāng)建立的概率密度模型不準(zhǔn)確時(shí)，參數(shù)ICA算法算法有時(shí)不能分離源信號(hào)，為此，提出了非參數(shù)ICA的檢測(cè)算法。直接由觀測(cè)信號(hào)樣本出發(fā)，使用高斯核函數(shù)估計(jì)分離信號(hào)的概率密度函數(shù)，計(jì)算非參數(shù)似