可逆Bloom Filter及其在長流識別應用中的研究.pdf

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

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

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

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

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

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

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

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

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