無(wú)線傳感器網(wǎng)絡(luò)中目標(biāo)覆蓋算法研究.pdf

1、目標(biāo)覆蓋是無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)基本問(wèn)題。它主要研究傳感器感知物理目標(biāo)的監(jiān)測(cè)程度，如何調(diào)度各傳感器節(jié)點(diǎn)來(lái)完成覆蓋任務(wù)，延長(zhǎng)網(wǎng)絡(luò)覆蓋的生命期。為了最大化目標(biāo)覆蓋的生命期，本文對(duì)無(wú)線傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋問(wèn)題作了如下研究：
　　 1.在集合分割算法的基礎(chǔ)上，提出一種線性規(guī)劃算法來(lái)解決目標(biāo)覆蓋問(wèn)題。
　　 首先，本文將傳感器網(wǎng)絡(luò)的工作時(shí)間分割成一個(gè)個(gè)小的時(shí)隙。在每個(gè)時(shí)隙中，選定一個(gè)目標(biāo)覆蓋集執(zhí)行目標(biāo)覆蓋任務(wù)。一個(gè)傳感器節(jié)點(diǎn)可以屬于

2、多個(gè)不同的目標(biāo)覆蓋集。這種傳感器節(jié)點(diǎn)分配給多個(gè)目標(biāo)覆蓋集的方法，突破了整數(shù)規(guī)劃的思想，引入了線性規(guī)劃的算法思路。接著，深入地分析了目標(biāo)覆蓋的網(wǎng)絡(luò)模型，設(shè)計(jì)了傳感器節(jié)點(diǎn)初始能量不完全相等的網(wǎng)絡(luò)模型，并提出一種線性規(guī)劃的表達(dá)式來(lái)描述目標(biāo)覆蓋問(wèn)題。最后，設(shè)計(jì)了一種線性規(guī)劃算法來(lái)解決目標(biāo)覆蓋問(wèn)題。線性規(guī)劃方法來(lái)描述和分析目標(biāo)覆蓋問(wèn)題，并證明目標(biāo)覆蓋問(wèn)題是一個(gè)NP 完全問(wèn)題，為目標(biāo)覆蓋問(wèn)題建立了理論基礎(chǔ)。
　　 2.為了降低算法的復(fù)雜度，

3、提出一種集中式的啟發(fā)式貪心最優(yōu)目標(biāo)覆蓋算法來(lái)解決目標(biāo)覆蓋問(wèn)題。
　　 在實(shí)際應(yīng)用中，在傳感器節(jié)點(diǎn)的處理能力、通信能力、電源能量都嚴(yán)重受限的條件下，要求傳感器節(jié)點(diǎn)執(zhí)行算法的復(fù)雜計(jì)算比較小。為了降低算法的復(fù)雜度，在分析無(wú)線傳感器網(wǎng)絡(luò)的目標(biāo)覆蓋能量模型的基礎(chǔ)上，找出目標(biāo)覆蓋生命期的關(guān)鍵約束，引入關(guān)鍵目標(biāo)的概念，在關(guān)鍵目標(biāo)優(yōu)先和最大化關(guān)鍵目標(biāo)生命期的基礎(chǔ)上，提出一種啟發(fā)式貪心最優(yōu)覆蓋算法。從目標(biāo)的覆蓋能量和覆蓋生命期的角度，來(lái)設(shè)計(jì)啟發(fā)式

4、貪心策略，克服了傳統(tǒng)的剩余能量?jī)?yōu)先和能量效率優(yōu)先的貪心策略的缺陷，取得很好的算法效果。
　　 3.針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的分布式自組織特點(diǎn)，設(shè)計(jì)了一種目標(biāo)覆蓋問(wèn)題的分布式最優(yōu)覆蓋算法。
　　 用線性規(guī)劃算法和集中式啟發(fā)式貪心算法來(lái)求目標(biāo)覆蓋問(wèn)題，都屬于集中式算法。在集中式算法中，匯節(jié)點(diǎn)或基站要取得全網(wǎng)的信息，成為全網(wǎng)的瓶頸。同時(shí)，全網(wǎng)管理信息的集中和分發(fā)要增加網(wǎng)絡(luò)流量，增大通信能耗。為了克服集中式算法的缺陷，針對(duì)無(wú)線傳感器網(wǎng)

5、絡(luò)的分布式和自組織特點(diǎn)，設(shè)計(jì)一種分布式最優(yōu)覆蓋算法來(lái)解決點(diǎn)目標(biāo)覆蓋問(wèn)題。
　　 首先，提出本地h-跳的目標(biāo)覆蓋問(wèn)題，并證明了1-跳分布式算法的可行性。接著，在分析目標(biāo)覆蓋能量模型的基礎(chǔ)上，引入了關(guān)鍵目標(biāo)的概念，設(shè)計(jì)了基于目標(biāo)覆蓋能量的能量效用函數(shù)，在關(guān)鍵目標(biāo)優(yōu)先和能效優(yōu)先的原則的基礎(chǔ)上設(shè)置節(jié)點(diǎn)等待時(shí)間，并建立了節(jié)點(diǎn)等待時(shí)間自適應(yīng)調(diào)整的機(jī)制。最后，設(shè)計(jì)了一種分布式最優(yōu)覆蓋算法。
　　 4.針對(duì)覆蓋半徑可調(diào)的無(wú)線傳感器網(wǎng)絡(luò)模

6、型，進(jìn)一步提出用線性規(guī)劃算法來(lái)解決覆蓋半徑可調(diào)的目標(biāo)覆蓋問(wèn)題。
　　 調(diào)整覆蓋半徑，是減小覆蓋能耗的重要技術(shù)之一。在覆蓋半徑可調(diào)的無(wú)線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)通過(guò)調(diào)整覆蓋半徑，減少重疊覆蓋率，減少覆蓋能耗，延長(zhǎng)目標(biāo)覆蓋的生命期。同時(shí)，通過(guò)調(diào)整傳感器節(jié)點(diǎn)的覆蓋半徑，也可以實(shí)現(xiàn)各目標(biāo)之間的能耗均衡，從總體上延長(zhǎng)網(wǎng)絡(luò)覆蓋的生命期。首先，在分析覆蓋半徑可調(diào)的目標(biāo)覆蓋問(wèn)題，用線性規(guī)劃表達(dá)式描述覆蓋半徑可調(diào)的目標(biāo)覆蓋問(wèn)題，并提出一種高效的啟

7、發(fā)法，最后設(shè)計(jì)模仿實(shí)驗(yàn)來(lái)證明算法的有效性。
　　 5. 設(shè)計(jì)一種基于能量均衡和覆蓋半徑自適應(yīng)調(diào)整的目標(biāo)覆蓋的分布式啟發(fā)算法來(lái)解決半徑可調(diào)的目標(biāo)覆蓋問(wèn)題。
　　 覆蓋半徑可調(diào)的目標(biāo)覆蓋問(wèn)題是一個(gè)NP 完全問(wèn)題。為了降低算法的復(fù)雜度，考慮到無(wú)線傳感器網(wǎng)絡(luò)的動(dòng)態(tài)拓?fù)浜头植际阶越M織的特點(diǎn)，本文采用分布式算法求局部h-跳的局部網(wǎng)絡(luò)的目標(biāo)覆蓋的生命期，來(lái)逼近整個(gè)網(wǎng)絡(luò)的目標(biāo)覆蓋生命期的全局最優(yōu)解。為此，在能量平衡和自適應(yīng)調(diào)整覆蓋半徑的