Voronoi圖的性質(zhì)及其在無線傳感器網(wǎng)絡(luò)中的應(yīng)用.pdf

1、無線傳感器網(wǎng)絡(luò)是由大量體積小、能耗低、計(jì)算、通信和存儲(chǔ)能力有限的傳感器節(jié)點(diǎn)組成的自組織網(wǎng)絡(luò),廣泛應(yīng)用于軍事和民用領(lǐng)域,有著非常廣闊的研究前景。覆蓋和連通是無線傳感器網(wǎng)絡(luò)研究領(lǐng)域的基本問題。網(wǎng)絡(luò)覆蓋可以反映網(wǎng)絡(luò)的“感知”服務(wù)質(zhì)量,通過對(duì)網(wǎng)絡(luò)覆蓋的控制可以實(shí)現(xiàn)資源優(yōu)化配置以延長網(wǎng)絡(luò)的生命周期,同時(shí)維持網(wǎng)絡(luò)的連通性,保證將傳感器節(jié)點(diǎn)采集的信息傳送到最終用戶。本文深入分析了無線傳感器網(wǎng)絡(luò)覆蓋和連通問題,并著重研究網(wǎng)絡(luò)覆蓋控制節(jié)能問題的解決方案,

2、主要工作包括以下幾個(gè)方面:
　　 (1)對(duì)于無線傳感器網(wǎng)絡(luò)覆蓋連通問題的研究,借助計(jì)算幾何的重要圖形Voronoi,圖來處理,是一種有效方法。本文首先討論了Voronoi圖的基本概念、性質(zhì)以及構(gòu)造方法,引出了к階Voronoi圖概念,深入探討其性質(zhì)后,證明了k階Voronoi圖的重要性質(zhì),該性質(zhì)作為以后章節(jié)中無線傳感器網(wǎng)絡(luò)覆蓋連通問題研究的理論基礎(chǔ)。
　　 (2)針對(duì)當(dāng)前Voronoi圖減點(diǎn)算法研究甚少,而該算法在Vor

3、onoi圖動(dòng)態(tài)更新中起到重要作用,本文基于Voronoi圖與Delaunay三角網(wǎng)對(duì)偶的性質(zhì),利用凸耳消元法,提出了一種二維平面Voronoi圖任意點(diǎn)刪除算法,該算法容易理解,且算法執(zhí)行效率高。
　　 (3)在無線傳感器網(wǎng)絡(luò)的不同應(yīng)用中,對(duì)網(wǎng)絡(luò)覆蓋度的要求有很大差異,故有必要知道網(wǎng)絡(luò)覆蓋度的情況以進(jìn)行覆蓋控制。本文基于к階Voronoi圖的性質(zhì)設(shè)計(jì)了一種覆蓋度判別算法,該算法具有算法復(fù)雜度低的優(yōu)點(diǎn),在優(yōu)化網(wǎng)絡(luò)資源配置中起到重要的