基于剖分的傳感器網(wǎng)絡(luò)覆蓋快速算法研究.pdf

1、近年來，無線傳感網(wǎng)絡(luò)已成為首選的研究課題。他們有巨大的長期經(jīng)濟(jì)潛力，有能力改變我們的生活，并帶來許多新體制建設(shè)的挑戰(zhàn)。傳感器網(wǎng)絡(luò)還引起大量的新概念和優(yōu)化方面的問題。諸如定位、部署和跟蹤，這些根本的問題，很大程度上都是依靠他們來獲得所需要的信息。傳感器網(wǎng)絡(luò)發(fā)展至今，仍有許多可以應(yīng)用的環(huán)境待開發(fā)，也仍有許多技術(shù)的問題需要克服，值得各界學(xué)者及研究團(tuán)隊繼續(xù)深入地研究。 在傳感器網(wǎng)絡(luò)的許多監(jiān)控應(yīng)用領(lǐng)域中，網(wǎng)絡(luò)中的每個傳感器負(fù)責(zé)收集自己周圍

2、的局部信息并將得到的數(shù)據(jù)傳送到一個匯聚節(jié)點Sink，然后Sink再通過匯總所有節(jié)點的局部數(shù)據(jù)以得到其某個感興趣區(qū)域P的整體信息。要保障整體信息的完整性，則Sink首先要判定該感興趣的區(qū)域是否被一組給定的傳感器節(jié)點覆蓋，因此，對傳感器網(wǎng)絡(luò)中的覆蓋問題進(jìn)行深入研究具有重要意義。例如，在火災(zāi)監(jiān)控現(xiàn)場，人們可能要知道傳感器網(wǎng)絡(luò)對某片重災(zāi)地區(qū)的覆蓋情況。因此，覆蓋問題有時候也被看作是衡量傳感器網(wǎng)絡(luò)的服務(wù)質(zhì)量(Quality of Service)

3、的一種標(biāo)準(zhǔn)。 本文較深入地研究了傳感器網(wǎng)絡(luò)覆蓋問題，這是屬于傳感器網(wǎng)絡(luò)的基本問題之一。覆蓋是衡量傳感器網(wǎng)絡(luò)工作性能的重要指標(biāo)之一，通過對覆蓋問題的研究可以尋求提高傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的方法。 本文逐漸加深依次研究了覆蓋問題中比較常見的四個問題：二維k-覆蓋(k≥1)、二維最大七一覆蓋、三維k-覆蓋和三維最大七．覆蓋問題。首先提出了把感興趣區(qū)域劃分為正三角形區(qū)域的思想，代替?zhèn)鹘y(tǒng)的Voronoi網(wǎng)格劃分，減少了區(qū)域劃分的時間復(fù)

4、雜度，在此基礎(chǔ)上，本文進(jìn)一步對k-覆蓋問題進(jìn)行了研究，提出了一種基于正三角形剖分的k-覆蓋判定算法和最大k-覆蓋判定算法，并對算法在實際中的應(yīng)用進(jìn)行了討論。然后把算法進(jìn)一步擴(kuò)展，把這個思想擴(kuò)展到三維空間領(lǐng)域，提出了基于立方體剖分的三維k覆蓋判定算法。這些算法可以使得實際應(yīng)用中，更快地判斷傳感器網(wǎng)絡(luò)是否覆蓋特定區(qū)域，從而做出重新布置網(wǎng)絡(luò)等后續(xù)操作。最后，本文簡要介紹了傳感器網(wǎng)絡(luò)仿真平臺的設(shè)計與實現(xiàn)。該平臺提供一個傳感器網(wǎng)絡(luò)覆蓋算法的仿真試