無線傳感器網(wǎng)絡(luò)的WiME系統(tǒng)路由設(shè)計及應(yīng)用

4.2 BIoom Filter概念

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

　　如果要知道一個元素a是否在集合S中，可以參照圖1對其進行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ù)的計算需要花費一定的時間，限制k的個數(shù)不會很大，使得存儲空間大大縮小，所以這是一種用時間換取空間的辦法。

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

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

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

4.4 計數(shù)型Bloom Filter

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

　　4.5 Bloom Filter的其他改進

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

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

　5 結(jié) 論

　　WiME是一個基于生物行為啟發(fā)的、使用無線傳感器網(wǎng)絡(luò)實現(xiàn)的智能復(fù)眼系統(tǒng)。它嘗試著從仿生的角度來有效地降低智能實現(xiàn)的復(fù)雜性，提高機器人的移動能力；同時拓寬機器人的應(yīng)用范圍，使廉價移動機器人也可以表現(xiàn)出卓越的移動智能。這是從另一個視角解決集中式人工智能所面臨的應(yīng)用難點的一種新的理論嘗試。

　　WiME中的機器人導(dǎo)航技術(shù)采用單步的方向查詢方式，完成了一跳情況下的路由查詢?nèi)蝿?wù)；而且使用了Bloom Filter來壓縮存儲，空間進行了高度優(yōu)化。這使在無線傳感器網(wǎng)絡(luò)這樣一個計算能力弱、資源嚴重受限的環(huán)境下完成路徑和通信路由查詢系統(tǒng)這樣一個包含大數(shù)據(jù)最的工作變成了現(xiàn)實。希望本設(shè)計的思路，對于其他的機器人導(dǎo)航應(yīng)用有很好的啟發(fā)作用。