無線傳感器網(wǎng)絡(luò)拓?fù)渲羞B通支配集的研究.pdf

1、無線傳感器網(wǎng)絡(luò)的一個核心問題是拓?fù)浣Y(jié)構(gòu)的構(gòu)建。近年來，基于連通支配集及其變型的虛擬骨干網(wǎng)絡(luò)結(jié)構(gòu)受到廣泛的研究，它們對改善網(wǎng)絡(luò)路由性能，延長網(wǎng)絡(luò)生存時間具有重要意義，并能為網(wǎng)絡(luò)中移動節(jié)點的導(dǎo)航提供有效的追蹤信息。然而在單位圓盤圖的網(wǎng)絡(luò)模型中計算最小連通支配集、其變型：有效連通支配集、最小頂點覆蓋集等問題都是NP-難的，因此研究者們大多設(shè)計多項式時間算法在圖中尋找相應(yīng)問題的近似解。
　　本文根據(jù)研究現(xiàn)狀和已有研究方法，首先在單位圓盤圖

2、中提出一個(3,2)-有效連通支配集的近似算法。對任意給定充分小的>0，算法在網(wǎng)絡(luò)中使用網(wǎng)格劃分和平移策略，計算出一個近似因子與有關(guān)的(3,2)-有效連通支配集。我們證明了該算法的正確性且其時間復(fù)雜度為多項式級的。其次，在頂點度有限的有界增長圖中，當(dāng)缺乏網(wǎng)絡(luò)圖幾何表達(dá)時，本文分別對最小頂點覆蓋和最小權(quán)頂點覆蓋問題提出了近似因子為(1+)的多項式時間近似算法，其中>0。我們證明了相應(yīng)算法的正確性且其時間復(fù)雜度為多項式級的。最后，本文通過有