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

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

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

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