Bloom Filter 概念分析

　　在參考文獻(xiàn)中，作者提出了在無線傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)帶有語義的路由，其具體方法是在每個節(jié)點(diǎn)存儲了一個語義檢索表，檢索表的每一點(diǎn)對應(yīng)一個區(qū)域分類。每個節(jié)點(diǎn)只存在有限的幾個區(qū)域分類或稱為“路由可能”。這樣，當(dāng)發(fā)生包含足夠?qū)傩缘恼Z義信息的路由查詢輸入時(shí)，節(jié)點(diǎn)調(diào)用自己的規(guī)則引擎，通過計(jì)算匹配到檢索表中的某一點(diǎn)，并從其對應(yīng)的區(qū)域信息獲取通往該區(qū)域的下一跳的信息。這與本沒計(jì)中的這種單步路徑查詢的方法有相似之處。本設(shè)計(jì)中也有這樣的一種規(guī)則引擎，即下文所要介紹的Bloom Filter。所不同的是，在本設(shè)計(jì)中，檢索表不是一個，而是多個;檢索表中的元素不再指示區(qū)域或路由的類別，而是指示輸入是否在當(dāng)前路由表中;而且查詢輸人不是抽象的語義信息，而是人名、房間號或單位名稱等這樣的含有明確語義的地理空間標(biāo)識。

　　下面可以看到，采用Bloom Filter不僅可以解決路由的分類和查詢問題，而且可以進(jìn)一步降低資源有限的無線傳感器節(jié)點(diǎn)中的路徑信息的數(shù)據(jù)量。進(jìn)而在WiME的設(shè)計(jì)中，對每一個分組使用計(jì)數(shù)型Bloom Filter實(shí)現(xiàn)了路由信息的動態(tài)修改。下面介紹基本的Bloom Filter和計(jì)數(shù)型Bloom Filter這兩種“規(guī)則引擎”。

　　BIoom Filter概念

　　Bloom Filter的概念最早是由B.H.Bloom于1970年提山的。已知一個集合S含有n個元素，每個元素可以是人名、網(wǎng)址或者某個編號之類的能被計(jì)算機(jī)識別的獨(dú)有的一個或一組符號。我們定義一個含有m個元素的向量表v，v中的每個元素只使用1位表示，即每個元素只能表示為0或1。初始化v的每個元素為0。假設(shè)有k個獨(dú)立的hash函數(shù)H1，…，Hk，映射范圍為m。對S中的每個元素，將其進(jìn)行hash變換后在v中對應(yīng)的位置上置1。

　　如果要知道一個元素a是否在集合S中，可以參照圖1對其進(jìn)行k個hash變換，并查詢v中對應(yīng)的元素是否為1。如果k個對應(yīng)元素均為1，就斷定a在集合S中。

　　舉例來說，如果S表示的是一個URL查找表，每個元素平均包含50個ASCII碼，則直接存儲需要400n位;而采用Bloom Filter存儲，需要m位(m和kn同數(shù)量級)。由于hash函數(shù)的計(jì)算需要花費(fèi)一定的時(shí)間，限制k的個數(shù)不會很大，使得存儲空間大大縮小，所以這是一種用時(shí)間換取空間的辦法。

　　最優(yōu)情況下Bloom Filter的正向誤檢概率

　　從上面可以看到，集合元素個數(shù)n、hash函數(shù)個數(shù)k和向量表長度m是Bloom Filter的3個關(guān)鍵參數(shù)。BloomFilter中存在著這樣一種情況，即雖然一個元素不屬于集合S，由于hash函數(shù)的隨機(jī)性，有可能k個hash變換在v中的對應(yīng)元素均為1，從而該元素被誤認(rèn)為屬于集合S。這種情況稱為“正向誤檢(false positive)”。從概率上看，正向誤檢總是不可避免的。

　　將n個元素插入Bloom Filter表中后，每一位元素仍然為0的概率是(如無聲明，下面均認(rèn)為hash函數(shù)是均勻映射的)：

　　計(jì)數(shù)型Bloom Filter

　　在生成Bloom Filter表的過程中，不可避免地會出現(xiàn)映射到v的同一位置的情況，這在存在增刪的情況下就會出現(xiàn)問題。如果一個元素從集合中刪除，則其對應(yīng)的Bloom Filter表中的元素都要從1變?yōu)?。那么，其他映射到該位置的元素在查詢自身是否屬于集合時(shí)，就不會得到正確結(jié)果，這稱為“反向誤檢(false negative)”。計(jì)數(shù)型Bloom Filter可以解決這個問題，它將向量表中每個位置從1位表示改為多位表示。這樣，添加操作中每映射到某一位置1次，該位置就計(jì)數(shù)加1;刪除操作中時(shí)，該位置減1。計(jì)數(shù)位數(shù)決定了所能計(jì)數(shù)的最大值。

　　Bloom Filter的其他改進(jìn)

　　除了計(jì)數(shù)型Bloom Filter，還有許多在嘗試提出改進(jìn)的Bloom Filter數(shù)據(jù)結(jié)構(gòu)。探討了非最優(yōu)情況下m、n和k之間的相互關(guān)系;針對無線傳感器網(wǎng)絡(luò)中洪泛查詢的特點(diǎn)提出了隨空間域衰減的方式，其Bloom Filter向量表中置1的位會隨著空間域的變化以一定概率清0，則Bloom Filer解碼時(shí)就變成了統(tǒng)計(jì)k個hash函數(shù)對應(yīng)位置上1的個數(shù)(個數(shù)越大可能性越大);參考文獻(xiàn)[8]提出的拆分型Bloom Filter，針對反復(fù)增刪最終導(dǎo)致最初設(shè)計(jì)的Bloom Filter表不可用的情況，提出將總表分割成多個子表來設(shè)計(jì)。

　　綜合考慮，筆者仍然認(rèn)為計(jì)數(shù)型Bloom Filter是簡單、易用的，而且具有較好的性能。建議使用4位計(jì)數(shù)，但經(jīng)過對計(jì)數(shù)位數(shù)的理論分析和實(shí)驗(yàn)驗(yàn)證，筆者最終采用了2位計(jì)數(shù)。這已經(jīng)可以將進(jìn)行反復(fù)增刪可能造成的反向誤檢的概率降低到1.85×10-4。反復(fù)增刪5396次，才會出現(xiàn)1次反向誤檢，對1000個節(jié)點(diǎn)這樣的規(guī)模已經(jīng)是夠用的了。不過，對于這一問題的討論已經(jīng)超出了本文的范圍，這里不再贅述。