無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂萍夹g(shù)

應(yīng)滿(mǎn)足的性質(zhì)

　　拓?fù)淇刂扑惴ǖ哪繕?biāo)是通過(guò)控制結(jié)點(diǎn)的傳輸范圍使生成的網(wǎng)絡(luò)拓?fù)錆M(mǎn)足一定的性質(zhì)，以延長(zhǎng)網(wǎng)絡(luò)生命周期，降低網(wǎng)絡(luò)干擾，提高吞吐率。
　　一般假設(shè)結(jié)點(diǎn)分布在二維平面上，所有結(jié)點(diǎn)都是同構(gòu)的，都使用無(wú)向天線。以有向圖建模無(wú)線傳感器網(wǎng)絡(luò)，如果結(jié)點(diǎn)i的傳輸功率Pi大于從結(jié)點(diǎn)i到結(jié)點(diǎn)j需要的傳輸功率Pij，則結(jié)點(diǎn)i到結(jié)點(diǎn)j之間有一條有向邊。所有結(jié)點(diǎn)都以最大功率工作時(shí)所生成的拓?fù)浞Q(chēng)為UDG圖(Unit Disk Graph)。

　　拓?fù)淇刂茟?yīng)使網(wǎng)絡(luò)拓?fù)錆M(mǎn)足下列性質(zhì)中的一個(gè)或幾個(gè)：

　　連通性―為了實(shí)現(xiàn)結(jié)點(diǎn)間的互相通信，生成的拓?fù)浔仨毐ＷC連通性，即從任何一個(gè)結(jié)點(diǎn)都可以發(fā)送消息到另外一個(gè)結(jié)點(diǎn)。連通性是任何拓?fù)淇刂扑惴ǘ急仨毐ＷC的一個(gè)性質(zhì)。由UDG圖的定義可以知道，UDG圖的連通性是網(wǎng)絡(luò)能夠提供的最大連通性，因此一般假定UDG圖是連通的。所以，任何拓?fù)淇刂扑惴ㄉ傻耐負(fù)涠际荱DG圖的子圖。

　　對(duì)稱(chēng)性―指如果從結(jié)點(diǎn)i到結(jié)點(diǎn)j有一條邊，那么一定存在從結(jié)點(diǎn)j到結(jié)點(diǎn)i的邊。由于非對(duì)稱(chēng)鏈路在目前的MAC協(xié)議中沒(méi)有得到很好的支持，而且非對(duì)稱(chēng)鏈路通信的開(kāi)銷(xiāo)很大，因此一般都要求生成的拓?fù)渲墟溌肥菍?duì)稱(chēng)的。

　　稀疏性―指生成的拓?fù)渲械倪厰?shù)為O(n)，其中n是結(jié)點(diǎn)個(gè)數(shù)。減少拓?fù)渲械倪厰?shù)可以有效減少網(wǎng)絡(luò)中的干擾，提高網(wǎng)絡(luò)的吞吐率。稀疏性還可以簡(jiǎn)化路由計(jì)算。
　　平面性―指生成的拓?fù)渲袥](méi)有兩條邊相交。由圖論可知，滿(mǎn)足平面性一定滿(mǎn)足稀疏性。地理路由協(xié)議是一種十分適合計(jì)算和存儲(chǔ)能力有限的無(wú)線傳感器結(jié)點(diǎn)的路由協(xié)議，它不需要維護(hù)路由表和進(jìn)行復(fù)雜的路由計(jì)算，只需要按照一定的規(guī)則轉(zhuǎn)發(fā)消息。但當(dāng)?shù)讓油負(fù)洳皇瞧矫鎴D時(shí)，地理路由協(xié)議不能保證消息轉(zhuǎn)發(fā)的可達(dá)性。因此，當(dāng)結(jié)點(diǎn)運(yùn)行地理路由協(xié)議時(shí)，要求生成的拓?fù)浔仨殱M(mǎn)足平面性。
　　結(jié)點(diǎn)度數(shù)有界―指在生成的拓?fù)渲薪Y(jié)點(diǎn)的鄰居個(gè)數(shù)小于一個(gè)常數(shù)d。降低結(jié)點(diǎn)的度數(shù)可以減少結(jié)點(diǎn)轉(zhuǎn)發(fā)消息的數(shù)量和路由計(jì)算的復(fù)雜度。
　　Spanner性質(zhì)―指在生成的拓?fù)渲腥魏蝺蓚€(gè)結(jié)點(diǎn)間的距離小于它們?cè)赨DG圖中距離的常數(shù)倍。

研究方法

　　目前對(duì)拓?fù)淇刂频难芯靠梢苑譃閮纱箢?lèi)。一類(lèi)是計(jì)算幾何方法，以某些幾何結(jié)構(gòu)為基礎(chǔ)構(gòu)建網(wǎng)絡(luò)的拓?fù)?，以滿(mǎn)足某些性質(zhì)。另一類(lèi)是概率分析方法，在結(jié)點(diǎn)按照某種概率密度分布情況下，計(jì)算使拓?fù)湟源蟾怕蕽M(mǎn)足某些性質(zhì)時(shí)結(jié)點(diǎn)所需的最小傳輸功率和最小鄰居個(gè)數(shù)。

　　1．計(jì)算幾何方法

　　該方法常使用的幾何結(jié)構(gòu)有如下幾種：

　　 最小生成樹(shù)(MST) 網(wǎng)絡(luò)拓?fù)涫且越Y(jié)點(diǎn)間的歐式距離為度量的最小生成樹(shù)。結(jié)點(diǎn)的傳輸半徑設(shè)為與該結(jié)點(diǎn)相鄰的最長(zhǎng)邊的長(zhǎng)度。以MST為拓?fù)涞木W(wǎng)絡(luò)能保證網(wǎng)絡(luò)的連通性。由于在分布式環(huán)境下構(gòu)造MST開(kāi)銷(xiāo)巨大，一種折中的方法是結(jié)點(diǎn)采用局部MST方法設(shè)置傳輸范圍。
　　 GG圖(Gabriel Graph) 在傳輸功率正比傳輸距離的平方時(shí)，GG圖是最節(jié)能的拓?fù)洹ST是GG圖的子圖，GG圖也滿(mǎn)足連通性。
　　 RNG圖(Relative Neighbor Graph) 其稀疏程度在MST和GG圖之間，連通性也在MST和GG圖之間，優(yōu)于MST，沖突干擾優(yōu)于GG圖，是兩者的折中。RNG圖易于用分布式算法構(gòu)造。
　　DT圖(Delaunay Triangulation) UDG與DT圖的交集稱(chēng)為UDel圖(Unit Delaunay Triangulation)。UDel圖是稀疏的平面圖，適合于地理路由協(xié)議、節(jié)能、簡(jiǎn)化路由計(jì)算，以及降低干擾，因此十分適合作為無(wú)線底層拓?fù)洹?br />　　Yao Graph 研究人員提出了許多Yao Graph的變種，如在GG圖上使用Yao Graph，在Yao Graph上使用GG圖等，以減少Yao Graph中的邊數(shù)并同時(shí)保持Spanner性質(zhì)。
　　θ-Graph 與Yao Graph非常相似。不同之處在于，Yao Graph在每個(gè)扇區(qū)中選擇最近的結(jié)點(diǎn)建立鏈路，而θ-Graph選擇在扇區(qū)中軸投影最短的結(jié)點(diǎn)建立鏈路。