基于圖嵌入的無線傳感器網(wǎng)絡幾何路由算法研究.pdf

1、幾何路由協(xié)議可以為無線傳感器網(wǎng)絡提供高效、可擴展的路由。基于節(jié)點虛擬位置的幾何路由協(xié)議是其中一個嶄新分支，此類協(xié)議中的網(wǎng)絡節(jié)點不需要知道預定義的地理坐標，位置信息通過圖嵌入的方法獲得，路由根據(jù)圖嵌入得到的虛擬坐標進行，從而有效降低節(jié)點定位所帶來的能耗。路由算法是路由協(xié)議的核心，過去的相關算法主要缺陷在于節(jié)點虛擬坐標表示的復雜性，給傳感器網(wǎng)絡帶來了無法忍受的存儲開銷。目前，Schnyder幾何路由算法可有效解決這一問題，使幾何路由變得簡單

2、高效，但Schnyder幾何路由算法建立在嚴格的數(shù)學結構之上，當網(wǎng)絡拓撲結構動態(tài)變化時（特別是節(jié)點失效），算法將不再適用。本文針對這一問題展開研究，主要研究了基于圖嵌入的幾何路由算法，解決了節(jié)點失效問題。
　　本文在Schnyder幾何路由算法的基礎上，研究并提出了容忍網(wǎng)絡節(jié)點失效的幾何路由算法。首先，針對3-連通平面圖和平面三角剖分圖中節(jié)點失效問題，提出簡單高效的貪婪-指南針雙模路由算法為消息的傳遞指明方向。接著提出用二次嵌入的

3、方法可保證節(jié)點失效后的網(wǎng)絡仍有100％的消息可達率：針對3-連通平面圖拓撲模型中的節(jié)點失效問題，提出基于圖st-定向的樹路由算法，該算法繼承了Schnyder幾何路由算法中節(jié)點坐標表示的簡潔性；針對平面三角剖分圖拓撲模型中區(qū)域節(jié)點失效引起的“空洞”問題，使用基于Ricci流的共形映射算法將帶有不規(guī)則形狀“空洞”的網(wǎng)絡映射為帶有圓形“空洞”的圓盤，從而保證網(wǎng)絡中不存在局部最小點，使貪婪幾何路由能夠順利進行。
　　針對于本文設計的幾何