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

3 路由方式的選擇

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

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

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

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

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

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

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

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

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

　　4.1 路由信息的存儲(chǔ)和查詢

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

　　下面可以看到，采用Bloom Filter不僅可以解決路由的分類和查詢問題，而且可以進(jì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ī)則引擎”。