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

引 言

　　隨著微機(jī)電技術(shù)、低功耗嵌入式技術(shù)和通信技術(shù)的飛速發(fā)展，具有感知能力、計算能力和無線通信能力的微型傳感器得到了廣泛的應(yīng)用。這些由無線微型傳感器組成的傳感器網(wǎng)絡(luò)能夠協(xié)作地實時監(jiān)測、感知和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境或檢測對象的信息，并對這些信息進(jìn)行處理，傳送到需要這些信息的用戶。這便是被美國商業(yè)周刊認(rèn)定的21世紀(jì)最具影響力的21項技術(shù)之一——無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)。

　　在一個20層樓高、有著上千個房間的龐大醫(yī)院中，一位剛進(jìn)入大樓的坐在智能車中的老年人或殘障病人，如何可以輕松地到達(dá)自己要去的房間?我們正在嘗試為這樣的需求提供一種不需要外界干預(yù)的“室內(nèi)自動導(dǎo)航系統(tǒng)”——稱為“無線復(fù)眼系統(tǒng)(Wireless MOSaic Eyes，WiME)”。概括地講，它是一個基于生物行為啟發(fā)的無線傳感器網(wǎng)絡(luò)，通過空中大量分布的無線節(jié)點對智能車提供行為控制，因此是一個采用無線傳感器網(wǎng)絡(luò)實現(xiàn)的機(jī)器人導(dǎo)航系統(tǒng)。

　　WiME涉及兩個路由問題：一個是在地理空間的機(jī)器人路徑規(guī)劃，另一個是在分散的通信節(jié)點之間的信息通信路由。復(fù)眼可以作為機(jī)器人導(dǎo)航過程中的電子燈塔；無線復(fù)眼網(wǎng)絡(luò)可以被認(rèn)為是上海衛(wèi)星電視描述地理空間的一個拓?fù)鋱D、地理路徑規(guī)劃，也可以被簡化為一個網(wǎng)絡(luò)拓?fù)鋱D中的路徑規(guī)劃。因此在WiME中，空間路徑規(guī)劃和信息通信路由可以以完全相同的方式工作，而路徑規(guī)劃將根據(jù)各分散節(jié)點的語義定義為基礎(chǔ)。

　　為了在WiME這樣一個采用無線傳感器網(wǎng)絡(luò)技術(shù)的系統(tǒng)的節(jié)點上實現(xiàn)完整地圖的機(jī)器人導(dǎo)航，本設(shè)計使用一種單步方向查詢的路徑存儲和查詢系統(tǒng)。為了進(jìn)一步減小資源有限的無線傳感器節(jié)點中的路徑信息的數(shù)據(jù)量，在WiME的設(shè)計中對每一個分組使用Bloom Filter來壓縮存儲。另外，由于路徑信息可能是動態(tài)建立的，為了滿足頻繁修改的要求，將每個子表設(shè)計為計數(shù)型Bloom Filter。

　　2 WiME系統(tǒng)

　　2.1 WiME的生物啟發(fā)

　　自主機(jī)器人通常都配備有傳感器，能夠感知環(huán)境并自主移動，其配備的傳感器可以認(rèn)為是機(jī)器人的器官，它們所感知到的信息由機(jī)載電腦集中處理。這種集中構(gòu)架面臨如下三大問題：傳感器處理過程在真實環(huán)境中不魯棒；在動態(tài)環(huán)境中，處理算法的計算量大；在非結(jié)構(gòu)化的環(huán)境中理解場景十分困難。

　　然而，與脊椎動物的眼睛相比，更低級的昆蟲的眼睛是極具創(chuàng)造性和多樣性的。生物學(xué)研究發(fā)現(xiàn)，一些昆蟲可以用很小的神經(jīng)系統(tǒng)來處理上萬只小眼的信息。狼蛛復(fù)眼中的單眼功能不盡相同，一些用以提供前向視覺，而其他的則用來探測和提供周邊的視覺信息，這些視覺信號傳遞到大腦后可以融合并完成移動檢測、距離估計、運(yùn)動控制等。因此，通過分布式功能劃分和適當(dāng)?shù)膫鞲衅髀酚?，?fù)眼的信息處理機(jī)制的效率可以很高。

　　受此啟發(fā)，建立WiME這樣一個基于無線復(fù)眼網(wǎng)絡(luò)的智能環(huán)境。其中，各單眼將由低分辨率的視覺傳感器節(jié)點構(gòu)成，通過IEEE 802.15.4協(xié)議通信并組織形成環(huán)境神經(jīng)系統(tǒng)；通過探索仿生技術(shù)和算法，以支持無線復(fù)眼系統(tǒng)的智能信息處理(包括路徑規(guī)劃、行為協(xié)調(diào)、傳感器融合和路由等)以及視覺伺服。在WiME中，每個單眼都提供有明確的語義(定位信息和行為集)，而它們的拓?fù)溥B接將采用行為網(wǎng)絡(luò)來隱式建立；行為將通過能量累積所產(chǎn)生的事件進(jìn)行激發(fā)。節(jié)點之間的連接包含了信息融合和路由的條件概率信息；機(jī)器人的導(dǎo)航將建立在具有明確語義的傳感器拓?fù)鋱D的基礎(chǔ)之上，而不是建立在非結(jié)構(gòu)的地理環(huán)境之上。

　　2.2 WiME的設(shè)計目標(biāo)

　　(1)基于無線通信的分布式復(fù)眼

　　以無線傳感器網(wǎng)絡(luò)為連接機(jī)制，將具有高運(yùn)算量和大數(shù)據(jù)量特征的局部視覺信息以具有明確語義概念的形式實現(xiàn)通信連接，完成低通信帶寬的視覺協(xié)同。

　　(2)基于語義和信息全息的路由算法

　　該算法是一個針對用戶詢問的最優(yōu)路徑搜索算法。路由算法應(yīng)充分考慮查詢語義，采用信息全息編碼方式壓縮可能查詢和全局路由表，最終實現(xiàn)快速尋優(yōu)。這也是昆蟲復(fù)眼信息流分布的具體體現(xiàn)。

　　(3)生物啟發(fā)的分布式行為協(xié)調(diào)

　　由于本研究將眾多運(yùn)動行為分布在整個復(fù)眼系統(tǒng)中，機(jī)器人導(dǎo)航控制將面臨如何和諧地組織與激發(fā)行為。本研究將由生物神經(jīng)網(wǎng)絡(luò)為啟發(fā)，探索脈沖(spike)激勵的動作組織方式，以實現(xiàn)具有目標(biāo)驅(qū)動和及時響應(yīng)特性的行為控制網(wǎng)絡(luò)。

　　2.3 無線復(fù)眼系統(tǒng)中的單視神經(jīng)元的設(shè)計

　　①基礎(chǔ)運(yùn)動檢測器(EMD)。以生物視覺所特有的基礎(chǔ)運(yùn)動檢測器(EMD)為藍(lán)圖，將低分辨率并可隨機(jī)讀取的CMOS視覺傳感器作為視網(wǎng)膜，與無線模塊連接構(gòu)成系統(tǒng)單眼。

　?、诘头直媛蕡D像的語義提取。實時圖像語義提取的內(nèi)容包括：低分辨率的特征提取，包括顏色、紋理和區(qū)域形狀；融合紋理、顏色和形狀特征并給出解釋；區(qū)域分割和空間分析。這部分將采用降分辨率技術(shù)，通過并行運(yùn)算與FPGA實現(xiàn)相結(jié)合，減少計算代價并把算法應(yīng)用到分布式視覺融合中。

　?、蹖ο蟾櫤湍Ｊ阶R別。

　?、軣o線傳感器節(jié)點。節(jié)點一方面通過外圍電路與EMD相連，另一方面通過IEEE 802.15.4協(xié)議的接收器與其他復(fù)眼及機(jī)器人進(jìn)行通信，從而提供復(fù)眼神經(jīng)系統(tǒng)的信道；同時，復(fù)眼信息的融合與行為序列的產(chǎn)生這樣的運(yùn)算也要在節(jié)點上完成。

　　3 路由方式的選擇

　　所有的機(jī)器人導(dǎo)航都需要解決這樣的一個問題：機(jī)器人如何獲知通往目的地的道路。在無線傳感器網(wǎng)絡(luò)中，無線節(jié)點之間的信息通信路由也是一個首先要解決的問題。如前所述，由于地理信息固定，在WiME中空間路徑規(guī)劃和信息通信路由完全可以以相同的方式工作。因此下面以路徑規(guī)劃來說明這樣一個路由存儲和查詢方式的選擇問題。
　
　　在無線傳感器網(wǎng)絡(luò)中，無線節(jié)點由于能量受限，采用的是低功耗嵌入式處理器，其計算能力和存儲空間都有限。WiME也不例外，一般無法直接存儲路徑信息或者將地圖信息存儲在節(jié)點上從而在需要時計算出最優(yōu)路徑。為此，首先考慮下面的4種方法。

　　方法1：作為一種常用的方法，可以查詢整個地圖的路徑信息。由于房間數(shù)n眾多(認(rèn)為n不小于1000)，路徑數(shù)據(jù)巨大(存在n(n-1)／2條路徑)，這樣的地圖可以由1臺或多臺主服務(wù)器提供。任何一個無線節(jié)點或鄰近的有限多個節(jié)點都滿足不了這樣的存儲量。一個自然的方法是將全局地圖存儲到服務(wù)器上，機(jī)器人終端在必要時從服務(wù)器上下載路徑信息。這類似于GPS設(shè)備的工作方式。

　　方法2：根據(jù)使用的廣播式無線路由通信協(xié)議，建立一條到目標(biāo)點的無線通信鏈路，并利用建立的這條通信線路作為地理導(dǎo)航線路。

　　方法3：利用動態(tài)路徑規(guī)劃的思想，每個節(jié)點存儲與自身相關(guān)的一定范圍內(nèi)的地理信息，并生成最優(yōu)路徑信息。

　　方法4：每個節(jié)點存儲全局節(jié)點分布的地理信息和連接關(guān)系，在需要時與臨近的節(jié)點協(xié)同計算出最優(yōu)路徑。這是借鑒了計算機(jī)網(wǎng)絡(luò)中分布式計算的概念。

　　每種方法各有其優(yōu)劣。第1種方法修改容易，增加或刪除節(jié)點只需要在主服務(wù)器端更新。第2種方法不需要事先知道節(jié)點的地理位置信息，整個路徑信息是動態(tài)建立和修改的。第3種方法可以隨著道路情況動態(tài)調(diào)整最優(yōu)路徑。由于節(jié)點能夠?qū)崟r觀察到道路信息，可以引入?yún)?shù)來反映當(dāng)前周邊道路狀況，比如道路的堵塞程度，并由此動態(tài)維護(hù)這樣一個包含自身及臨近區(qū)域的最優(yōu)路徑表。但是這3種方法都是在多跳通信的情況下完成的，返回完整的路徑信息需要較多的通信帶寬和較長的通信延時，這對通信協(xié)議的魯棒性提出了挑戰(zhàn)。第4種方法的存儲量相對要小，與節(jié)點個數(shù)同數(shù)量級，但是多節(jié)點協(xié)同的最優(yōu)路徑的實時分布式計算對于無線傳感器節(jié)點無疑是一個困難的問題。畢竟當(dāng)前的分布式計算仍然局限在計算機(jī)網(wǎng)絡(luò)領(lǐng)域。如何將分布式計算和最新的網(wǎng)格計算的思想運(yùn)用到無線傳感器網(wǎng)絡(luò)上，可能會成為嵌入式系統(tǒng)領(lǐng)域的下一個方向。

　　在本設(shè)計的WiME中并沒有主機(jī)這個概念，每個無線移動節(jié)點同時充當(dāng)了主機(jī)和路由器——這是一個Ad-Hoc網(wǎng)絡(luò)。Ad-Hoc網(wǎng)絡(luò)的路由方式可以分為兩大類：基于路由表的路由和基于按需建立路由的路由。由于龐大的路徑數(shù)據(jù)量和極為有限的存儲空間，上面的方法2、方法3和方法4都采用了基于按需建立路由的路由方式；而方法1雖然是通過服務(wù)器的方式提供了基于路由表的路由，但是有限的服務(wù)器的數(shù)量并不適合這樣一個龐大的無線傳感器網(wǎng)絡(luò)。難道真的不能在每個無線節(jié)點上存儲這樣一個全局路由表，實現(xiàn)真正的基于路由表的路由方式嗎？

　　綜合考慮，本文提出了下面的方法——查詢目標(biāo)方向。這類似于人們在大街上問路，對方會告知該往哪個方向走；走到下一岔口時，又只好重新問路；最終可以成功到達(dá)目的地，而被詢問者并不能提供這條路線的完整路徑，所能提供的只是一個大概方向。

　　相比而言，這種方法利用到了室內(nèi)相對固定的地理信息的先驗知識；每個節(jié)點只需要存儲自身到目標(biāo)點的方向信息，其存儲量只是O(n)；查詢時也避免了多跳通信的發(fā)生，而且沒有增加額外的通信負(fù)擔(dān)，顯然更適合無線傳感器網(wǎng)絡(luò)的特點。因此，WiME系統(tǒng)中的路徑查詢采用了這種方法，通信路由也基于這種方式建立。

　　4 Bloom Filter

　　4.1 路由信息的存儲和查詢

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

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

　　4.2 BIoom Filter概念

　　Bloom Filter的概念最早是由B.H.Bloom于1970年提山的。已知一個集合S含有n個元素，每個元素可以是人名、網(wǎng)址或者某個編號之類的能被計算機(jī)識別的獨有的一個或一組符號。我們定義一個含有m個元素的向量表v，v中的每個元素只使用1位表示，即每個元素只能表示為0或1。初始化v的每個元素為0。假設(shè)有k個獨立的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ù)的計算需要花費(fèi)一定的時間，限制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ù)的隨機(jī)性，有可能k個hash變換在v中的對應(yīng)元素均為1，從而該元素被誤認(rèn)為屬于集合S。這種情況稱為“正向誤檢(false positive)”。從概率上看，正向誤檢總是不可避免的。

　　將n個元素插入Bloom Filter表中后，每一位元素仍然為0的概率是(如無聲明，下面均認(rèn)為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的其他改進(jìn)

　　除了計數(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，針對無線傳感器網(wǎng)絡(luò)中洪泛查詢的特點提出了隨空間域衰減的方式，其Bloom Filter向量表中置1的位會隨著空間域的變化以一定概率清0，則Bloom Filer解碼時就變成了統(tǒng)計k個hash函數(shù)對應(yīng)位置上1的個數(shù)(個數(shù)越大可能性越大)；參考文獻(xiàn)[8]提出的拆分型Bloom Filter，針對反復(fù)增刪最終導(dǎo)致最初設(shè)計的Bloom Filter表不可用的情況，提出將總表分割成多個子表來設(shè)計。

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

　　5 結(jié) 論

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

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