無(wú)線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍澳芰坑行Ю脝?wèn)題研究.pdf

1、無(wú)線傳感器網(wǎng)絡(luò)生成的網(wǎng)絡(luò)拓?fù)渲?，如果沒(méi)有拓?fù)淇刂疲泄?jié)點(diǎn)都會(huì)以最大功率工作。在這種情況下，節(jié)點(diǎn)有限的能量將被快速消耗。對(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行控制是一種重要的節(jié)省能量消耗、延長(zhǎng)網(wǎng)絡(luò)壽命的策略。傳感器節(jié)點(diǎn)由電池提供能量，且分布在惡劣環(huán)境中，電池不能夠隨意更換或再充電，需要盡量節(jié)省能量，提高能量的有效利用率。本文主要研究無(wú)線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂萍澳芰坑行Ю脝?wèn)題，主要內(nèi)容如下：
　　 第一章緒論中概述了本論文所用到的有關(guān)圖論和組合優(yōu)

2、化的基本概念。
　　 第二章主要介紹了無(wú)線傳感器網(wǎng)絡(luò)中拓?fù)淇刂茊?wèn)題及其相關(guān)研究工作。對(duì)網(wǎng)絡(luò)拓?fù)淇刂茊?wèn)題，介紹拓?fù)淇刂频亩x和拓?fù)淇刂频姆椒?。從拓?fù)淇刂蒲芯康牟煌繕?biāo)，對(duì)文獻(xiàn)進(jìn)行了綜述介紹。
　　 第三章研究半徑可變的容錯(cuò)性連通覆蓋問(wèn)題，即給定一個(gè)由傳感器集合D組成的無(wú)線傳感器網(wǎng)絡(luò)和一個(gè)需要監(jiān)測(cè)的區(qū)域，如何選擇一個(gè)傳感子集M，并對(duì)M 中的任一傳感器分配傳感和通訊半徑，使選擇的子集在滿足2-連通k-覆蓋條件下的能量費(fèi)用最少。

3、對(duì)此問(wèn)題設(shè)計(jì)了一個(gè)貪婪算法，得到的近似因子為O(rlogkhn)，其中r為相連路長(zhǎng)，n為傳感器網(wǎng)絡(luò)中傳感器的個(gè)數(shù)，h為傳感器可以選擇的傳感半徑的個(gè)數(shù)。
　　 第四章研究延長(zhǎng)連通覆蓋集合的網(wǎng)絡(luò)壽命問(wèn)題。在尋找到滿足連通覆蓋要求的不同的傳感器集合后，如何給這些集合分配工作時(shí)間，使得網(wǎng)絡(luò)總的工作時(shí)間最長(zhǎng)。文中給出此問(wèn)題的具有指數(shù)個(gè)變量的LP 形式，用The Garg-K?nemannAlgorithm求解此問(wèn)題，給出了具有近似性能比為