Bloom Filter 概念分析

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

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

　　BIoom Filter概念

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

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

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

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

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

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

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

　　在生成Bloom Filter表的過(guò)程中，不可避免地會(huì)出現(xiàn)映射到v的同一位置的情況，這在存在增刪的情況下就會(huì)出現(xiàn)問(wèn)題。如果一個(gè)元素從集合中刪除，則其對(duì)應(yīng)的Bloom Filter表中的元素都要從1變?yōu)?。那么，其他映射到該位置的元素在查詢(xún)自身是否屬于集合時(shí)，就不會(huì)得到正確結(jié)果，這稱(chēng)為“反向誤檢(false negative)”。計(jì)數(shù)型Bloom Filter可以解決這個(gè)問(wèn)題，它將向量表中每個(gè)位置從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)系;針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中洪泛查詢(xún)的特點(diǎn)提出了隨空間域衰減的方式，其Bloom Filter向量表中置1的位會(huì)隨著空間域的變化以一定概率清0，則Bloom Filer解碼時(shí)就變成了統(tǒng)計(jì)k個(gè)hash函數(shù)對(duì)應(yīng)位置上1的個(gè)數(shù)(個(gè)數(shù)越大可能性越大);參考文獻(xiàn)[8]提出的拆分型Bloom Filter，針對(duì)反復(fù)增刪最終導(dǎo)致最初設(shè)計(jì)的Bloom Filter表不可用的情況，提出將總表分割成多個(gè)子表來(lái)設(shè)計(jì)。

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