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

4.2 BIoom Filter概念

　　Bloom Filter的概念最早是由B.H.Bloom于1970年提山的。已知一個(gè)集合S含有n個(gè)元素，每個(gè)元素可以是人名、網(wǎng)址或者某個(gè)編號(hào)之類的能被計(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變換，并查詢v中對(duì)應(yīng)的元素是否為1。如果k個(gè)對(duì)應(yīng)元素均為1，就斷定a在集合S中。

　　舉例來說，如果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í)間換取空間的辦法。

4.3 最優(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。這種情況稱為“正向誤檢(false positive)”。從概率上看，正向誤檢總是不可避免的。

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

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

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

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

　　除了計(jì)數(shù)型Bloom Filter，還有許多在嘗試提出改進(jìn)的Bloom Filter數(shù)據(jù)結(jié)構(gòu)。參考文獻(xiàn)[6]提出的壓縮型Bloom Filter探討了非最優(yōu)情況下m、n和k之間的相互關(guān)系；參考文獻(xiàn)[7]提出的域衰減Bloom Filter，針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中洪泛查詢的特點(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è)子表來設(shè)計(jì)。

綜合考慮，筆者仍然認(rèn)為計(jì)數(shù)型Bloom Filter是簡(jiǎn)單、易用的，而且具有較好的性能。盡管參考文獻(xiàn)[5]建議使用4位計(jì)數(shù)，但經(jīng)過對(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)是夠用的了。不過，對(duì)于這一問題的討論已經(jīng)超出了本文的范圍，這里不再贅述?！?/p>

　5 結(jié) 論

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

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