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

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

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