無線傳感器網(wǎng)絡(luò)中的控制劃分問題研究.pdf

1、無線傳感器網(wǎng)絡(luò)能夠獲取客觀物理世界的信息,并且集信息獲取、處理與傳輸為一體,近年來廣泛應(yīng)用于軍事監(jiān)測、環(huán)境和棲息地的監(jiān)測、火災(zāi)探測、目標(biāo)跟蹤、工農(nóng)業(yè)控制、危險(xiǎn)區(qū)域遠(yuǎn)程控制等諸多領(lǐng)域。無線傳感器網(wǎng)絡(luò)在工業(yè)界和學(xué)術(shù)界都引起了人們的極大關(guān)注,成為目前計(jì)算機(jī)領(lǐng)域中研究熱點(diǎn)之一。
　　在無線傳感器網(wǎng)絡(luò)中,通常需要尋找一個(gè)控制集作為虛擬骨干網(wǎng),在網(wǎng)絡(luò)中形成一個(gè)層次拓?fù)浣Y(jié)構(gòu)作為通信層。這樣只有控制集中的控制節(jié)點(diǎn)傳輸信息,極大地簡化了網(wǎng)絡(luò)的拓?fù)浣Y(jié)

2、構(gòu),減少了冗余信息的傳輸。但是控制集中的控制節(jié)點(diǎn)在收集、處理和轉(zhuǎn)發(fā)信息的過程中需要額外的能量開銷,因此比網(wǎng)絡(luò)中其他節(jié)點(diǎn)消耗更多的能量。而且傳感器節(jié)點(diǎn)的電池量有限、一次性布置難以對其二次充電,使得控制集中的控制節(jié)點(diǎn)會(huì)比其他節(jié)點(diǎn)更快地死亡,從而縮短了網(wǎng)絡(luò)的壽命。
　　控制劃分問題就是尋找多個(gè)不相交的控制集,通過依次輪轉(zhuǎn)每個(gè)控制集,對每個(gè)控制集進(jìn)行睡眠調(diào)度,從而均衡節(jié)點(diǎn)的能量消耗,延長網(wǎng)絡(luò)壽命。根據(jù)控制劃分中控制集的類型,控制劃分可分為

3、三類:k-控制劃分(k-DP)、控制劃分(DP)和連通控制劃分(CDP)。本文分別解決了這三類控制劃分上尚未解決的公開問題,在單位圓盤圖上分別提出一個(gè)具有常數(shù)近似比的算法,并通過仿真實(shí)驗(yàn)進(jìn)一步驗(yàn)證了算法的正確性和有效性。
　　首先本文研究了k-控制劃分。在僅知道節(jié)點(diǎn)間的連接信息的情況下,利用均勻劃分得到一個(gè)具有常數(shù)近似比的k-控制劃分近似算法。然后本文研究了控制劃分。提出一種細(xì)胞結(jié)構(gòu)的劃分,該結(jié)構(gòu)的劃分包括簇劃分和團(tuán)劃分兩個(gè)階段;

4、在細(xì)胞結(jié)構(gòu)的基礎(chǔ)上,利用輪廓線圓盤的性質(zhì),在單位圓盤圖上得到一個(gè)具有常數(shù)近似比的控制劃分近似算法;該算法不僅可以在局部模型下有效運(yùn)行,而且可以在阻塞模型下有效運(yùn)行。最后本文研究了連通控制劃分。在僅知道節(jié)點(diǎn)間連接信息的情況下,首先得到一個(gè)控制劃分,然后將得到的控制劃分?jǐn)U展為連通控制劃分,最后對這些連通控制集進(jìn)行有效地局部調(diào)度,達(dá)到延長網(wǎng)絡(luò)壽命的目的。
　　綜上所述,本文分別研究了三類控制劃分,對于推進(jìn)無線傳感器網(wǎng)絡(luò)控制劃分問題的研究