無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的拓撲控制技術(shù)

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

　　拓撲控制算法的目標是通過(guò)控制結點(diǎn)的傳輸范圍使生成的網(wǎng)絡(luò )拓撲滿(mǎn)足一定的性質(zhì)，以延長(cháng)網(wǎng)絡(luò )生命周期，降低網(wǎng)絡(luò )干擾，提高吞吐率。
　　一般假設結點(diǎn)分布在二維平面上，所有結點(diǎn)都是同構的，都使用無(wú)向天線(xiàn)。以有向圖建模無(wú)線(xiàn)傳感器網(wǎng)絡(luò )，如果結點(diǎn)i的傳輸功率Pi大于從結點(diǎn)i到結點(diǎn)j需要的傳輸功率Pij，則結點(diǎn)i到結點(diǎn)j之間有一條有向邊。所有結點(diǎn)都以最大功率工作時(shí)所生成的拓撲稱(chēng)為UDG圖(Unit Disk Graph)。

　　拓撲控制應使網(wǎng)絡(luò )拓撲滿(mǎn)足下列性質(zhì)中的一個(gè)或幾個(gè)：

　　連通性―為了實(shí)現結點(diǎn)間的互相通信，生成的拓撲必須保證連通性，即從任何一個(gè)結點(diǎn)都可以發(fā)送消息到另外一個(gè)結點(diǎn)。連通性是任何拓撲控制算法都必須保證的一個(gè)性質(zhì)。由UDG圖的定義可以知道，UDG圖的連通性是網(wǎng)絡(luò )能夠提供的最大連通性，因此一般假定UDG圖是連通的。所以，任何拓撲控制算法生成的拓撲都是UDG圖的子圖。

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

　　稀疏性―指生成的拓撲中的邊數為O(n)，其中n是結點(diǎn)個(gè)數。減少拓撲中的邊數可以有效減少網(wǎng)絡(luò )中的干擾，提高網(wǎng)絡(luò )的吞吐率。稀疏性還可以簡(jiǎn)化路由計算。
　　平面性―指生成的拓撲中沒(méi)有兩條邊相交。由圖論可知，滿(mǎn)足平面性一定滿(mǎn)足稀疏性。地理路由協(xié)議是一種十分適合計算和存儲能力有限的無(wú)線(xiàn)傳感器結點(diǎn)的路由協(xié)議，它不需要維護路由表和進(jìn)行復雜的路由計算，只需要按照一定的規則轉發(fā)消息。但當底層拓撲不是平面圖時(shí)，地理路由協(xié)議不能保證消息轉發(fā)的可達性。因此，當結點(diǎn)運行地理路由協(xié)議時(shí)，要求生成的拓撲必須滿(mǎn)足平面性。
　　結點(diǎn)度數有界―指在生成的拓撲中結點(diǎn)的鄰居個(gè)數小于一個(gè)常數d。降低結點(diǎn)的度數可以減少結點(diǎn)轉發(fā)消息的數量和路由計算的復雜度。
　　Spanner性質(zhì)―指在生成的拓撲中任何兩個(gè)結點(diǎn)間的距離小于它們在UDG圖中距離的常數倍。

研究方法

　　目前對拓撲控制的研究可以分為兩大類(lèi)。一類(lèi)是計算幾何方法，以某些幾何結構為基礎構建網(wǎng)絡(luò )的拓撲，以滿(mǎn)足某些性質(zhì)。另一類(lèi)是概率分析方法，在結點(diǎn)按照某種概率密度分布情況下，計算使拓撲以大概率滿(mǎn)足某些性質(zhì)時(shí)結點(diǎn)所需的最小傳輸功率和最小鄰居個(gè)數。

　　1．計算幾何方法

　　該方法常使用的幾何結構有如下幾種：

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