無線傳感器網絡的WiME系統路由設計及應用

3 路由方式的選擇

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

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

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

　　方法3：利用動態路徑規劃的思想，每個節點存儲與自身相關的一定范圍內的地理信息，并生成最優路徑信息。

　　方法4：每個節點存儲全局節點分布的地理信息和連接關系，在需要時與臨近的節點協同計算出最優路徑。這是借鑒了計算機網絡中分布式計算的概念。

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

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

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

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

　　4.1 路由信息的存儲和查詢

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

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