無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的WiME系統路由設計

　　引 言

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

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

　　WiME涉及兩個(gè)路由問(wèn)題：一個(gè)是在地理空間的機器人路徑規劃，另一個(gè)是在分散的通信節點(diǎn)之間的信息通信路由。復眼可以作為機器人導航過(guò)程中的電子燈塔；無(wú)線(xiàn)復眼網(wǎng)絡(luò )可以被認為是描述地理空間的一個(gè)拓撲圖、地理路徑規劃，也可以被簡(jiǎn)化為一個(gè)網(wǎng)絡(luò )拓撲圖中的路徑規劃。因此在WiME中，空間路徑規劃和信息通信路由可以以完全相同的方式工作，而路徑規劃將根據各分散節點(diǎn)的語(yǔ)義定義為基礎。

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

　　2 WiME系統

　　2.1 WiME的生物啟發(fā)

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

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

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

　　2.2 WiME的設計目標

　　(1)基于無(wú)線(xiàn)通信的分布式復眼

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

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

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

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

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

　　2.3 無(wú)線(xiàn)復眼系統中的單視神經(jīng)元的設計

　?、倩A運動(dòng)檢測器(EMD)。以生物視覺(jué)所特有的基礎運動(dòng)檢測器(EMD)為藍圖，將低分辨率并可隨機讀取的CMOS視覺(jué)傳感器作為視網(wǎng)膜，與無(wú)線(xiàn)模塊連接構成系統單眼。

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

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

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

　　3 路由方式的選擇

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

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

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

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

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

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

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

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

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

　　4 Bloom Filter

　　4.1 路由信息的存儲和查詢(xún)

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

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

　　4.2 BIoom Filter概念

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

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

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

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

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

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

　　4.4 計數型Bloom Filter

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

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

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

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

　　5 結 論

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

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