1、如何在保證目標(biāo)覆蓋率的前提下延長(zhǎng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的生命周期一、背景在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(簡(jiǎn)稱(chēng)WSN)中每一個(gè)傳感器節(jié)點(diǎn)監(jiān)控自己周?chē)沫h(huán)境并把感知得到 的數(shù)據(jù)無(wú)線(xiàn)傳輸給接收點(diǎn)。傳統(tǒng) WSN 面臨的一個(gè)基本問(wèn)題是節(jié)點(diǎn)電池壽命有限。為了最大 化WSN的生命周期并確保所有目標(biāo)都在監(jiān)控之中，一種做法是在目標(biāo)周?chē)稚⒍鄠€(gè)傳感器 節(jié)點(diǎn)。每個(gè)目標(biāo)被多個(gè)傳感器節(jié)點(diǎn)監(jiān)控，每個(gè)節(jié)點(diǎn)覆蓋多個(gè)目標(biāo)。傳感器節(jié)點(diǎn)有活躍和睡眠 兩種狀態(tài)，活躍狀態(tài)的節(jié)點(diǎn)負(fù)責(zé)監(jiān)控目標(biāo)并發(fā)送/轉(zhuǎn)發(fā)數(shù)據(jù)。睡眠狀態(tài)的節(jié)點(diǎn)保存能量，在 需要的時(shí)候被喚醒。近來(lái)，能量采集技術(shù)應(yīng)用在WSN中，將周?chē)h(huán)境能量轉(zhuǎn)換為電能。理論上，采用了能 量收集技術(shù)的 WSN 可以持

2、久運(yùn)行。二解決DMLC問(wèn)題Distributed Maximum Lifetime Coveroge(DMLC)是 WSN 共同面臨的一 問(wèn)題。傳 統(tǒng)WSN解決這個(gè)問(wèn)題致力于減少能量的消耗。本論文針對(duì)能量采集WSN，關(guān)心的是節(jié)點(diǎn) 的再充能以及能量的使用效率，關(guān)鍵目標(biāo)是平衡能量采集與能量需求，提出了 Maximum Energy Protection(MEP)算法和“資格測(cè)試”。前者的主要思想是用具備較高能量的睡眠節(jié) 點(diǎn)替換活躍節(jié)點(diǎn)，后者目的是減少冗余，最小化能量浪費(fèi)。1傳統(tǒng) WSN 解決 DMLC解決 DMLC 的通常做法是降低冗余以最小化能量使用。冗余指的是多個(gè)傳感器覆蓋相 同目標(biāo)的現(xiàn)象。傳

3、統(tǒng)WSN的做法大致可以分為兩類(lèi)：整體重配置和自我配置。1.1 整體重配置該做法在等長(zhǎng)的循環(huán)中執(zhí)行操作，每一個(gè)循環(huán)包含配置和感知兩個(gè)階段。其中配置占時(shí) 比感知短得多。在配置階段，所有傳感器節(jié)點(diǎn)與鄰居節(jié)點(diǎn)交換位置和目標(biāo)信息并決定其在感 知階段的狀態(tài)。采用這種做法的典型方案有兩種。方案1：如果一個(gè)節(jié)點(diǎn)的目標(biāo)區(qū)域被其他節(jié)點(diǎn)覆蓋，則該節(jié)點(diǎn)可以關(guān)閉自己。否則就在 感知階段激活自己。方案2：擁有較高剩余能量的傳感器節(jié)點(diǎn)自愿覆蓋某一目標(biāo)。該方案采用的決策機(jī)制與 方案 1 類(lèi)似。所謂自愿，是讓剩余能量較少的節(jié)點(diǎn)更早進(jìn)行決策。如果節(jié)點(diǎn)的監(jiān)控目標(biāo)被 其他活躍節(jié)點(diǎn)覆蓋便可以進(jìn)入睡眠狀態(tài)，把，職責(zé)”留給能量較高的活躍節(jié)

4、點(diǎn)。整體重配臵方法最大的缺點(diǎn)是在每一輪循環(huán)開(kāi)始會(huì)產(chǎn)生大量的信號(hào)傳輸開(kāi)銷(xiāo)。此外，如 果一個(gè)節(jié)點(diǎn)出現(xiàn)了問(wèn)題無(wú)法繼續(xù)監(jiān)視目標(biāo)，要等到下一輪循環(huán)才會(huì)被發(fā)現(xiàn)。1.2自我配置該做法是將配臵節(jié)點(diǎn)狀態(tài)的工作交由給每個(gè)傳感器節(jié)點(diǎn)，引入了一種探查狀態(tài)，處在探 查狀態(tài)的節(jié)點(diǎn)可以與其他活躍節(jié)點(diǎn)交換信息。方案1： PEAS算法。如果處在探查狀態(tài)節(jié)點(diǎn)的感知范圍內(nèi)沒(méi)有其他活躍節(jié)點(diǎn)，則探查 節(jié)點(diǎn)可以進(jìn)入活躍狀態(tài)。否則根據(jù)工作狀態(tài)節(jié)點(diǎn)剩余的能量和處在睡眠狀態(tài)節(jié)點(diǎn)的總數(shù)計(jì)算 其的休眠時(shí)間。方案2：與1類(lèi)似，探查節(jié)點(diǎn)與感知范圍內(nèi)節(jié)點(diǎn)的距離超過(guò)某一設(shè)定值則激活自己。采用這種做法，睡眠節(jié)點(diǎn)需要周期性進(jìn)入探查狀態(tài)。這樣可能會(huì)導(dǎo)致覆蓋漏洞

5、。覆蓋漏 洞是指存在一個(gè)或多個(gè)目標(biāo)不被任何節(jié)點(diǎn)覆蓋。比如，當(dāng)一個(gè)節(jié)點(diǎn)能量耗盡，被該節(jié)點(diǎn)監(jiān)控 的目標(biāo)處于不被監(jiān)視的狀態(tài)，直到有睡眠節(jié)點(diǎn)進(jìn)入探查狀態(tài)發(fā)現(xiàn)該現(xiàn)象為止。解決這種問(wèn)題的一種方法是為傳感器節(jié)點(diǎn)裝備觸發(fā)電路，當(dāng)一個(gè)節(jié)點(diǎn)的能量耗盡時(shí)， 它把感知范圍內(nèi)的所有睡眠節(jié)點(diǎn)喚醒并進(jìn)入探查狀態(tài)。2.WSN-EH 解決 DMLC2.1.符號(hào)和術(shù)語(yǔ)假設(shè) WSN 由被放臵在歐幾里得平面的傳感器節(jié)點(diǎn)組成，節(jié)點(diǎn)有活躍和睡眠兩種狀態(tài)。靈 輛 分別表示悻感器節(jié)點(diǎn)和呂標(biāo)。壤套|5|,；=1|/| o氏表吞節(jié)點(diǎn)舍當(dāng)前的能量,受到其電池客郢的釣束.E表示節(jié)點(diǎn)再充電速率n Ef表示節(jié)點(diǎn)能量消耗的速度盹J返回被為節(jié)點(diǎn)覆蓋的目標(biāo)的

6、集合n薊引函數(shù)返回覆蓋目殉的節(jié)點(diǎn)的集合。定義1：覆蓋生命周期是指從傳感器節(jié)點(diǎn)開(kāi)始監(jiān)控目標(biāo)直到因?yàn)槿狈δ茉催€無(wú)法繼續(xù)監(jiān) 控目標(biāo)為止的時(shí)間。定義2：完全目標(biāo)覆蓋是指所有目標(biāo)在任何時(shí)候都至少被一個(gè)節(jié)點(diǎn)覆蓋。我們假定所有節(jié)點(diǎn)的感知范圍相同并且節(jié)點(diǎn)能夠監(jiān)控在其感知范圍內(nèi)的所有目標(biāo)。節(jié)點(diǎn)間的 通信距離是節(jié)點(diǎn)感知距離的兩倍。笛的鄰居節(jié)點(diǎn)表示為N)指的是在奧通信距離之內(nèi)的其他節(jié)點(diǎn)n命題1：的鄰居節(jié)點(diǎn)至少有一個(gè)覆蓋目標(biāo)與二相同。Nfe)=5(Zfe)X VE5 (1)我們定義了重配置階段：M ： -二在這個(gè)階段，所有涉及到的節(jié)點(diǎn)需要決策是否進(jìn)入 睡眠狀態(tài)。：的長(zhǎng)度比節(jié)點(diǎn)的電池壽命短得多。根據(jù)off-duty規(guī)則

7、做出決策。off-duty規(guī)則：如果節(jié)點(diǎn)工感知范圍內(nèi)的所有目標(biāo)被工工的子集節(jié)點(diǎn)覆蓋，則工可以把 自己關(guān)閉而不會(huì)降低整體的覆蓋率。否則就進(jìn)入活躍狀態(tài)。每一輪重配置階段的開(kāi)始，涉及到的節(jié)點(diǎn)首先交換它們的epoch和目標(biāo)信息。epoch 指的是節(jié)點(diǎn)開(kāi)始下一次進(jìn)入重配置階段的時(shí)間。然后，每一個(gè)節(jié)點(diǎn)根據(jù)off-duty規(guī)則在延 遲T之后決策出各自的狀態(tài)，其中T是基于各個(gè)節(jié)點(diǎn)剩余能量水平計(jì)算出來(lái)的，如下：從該公式看出，剩余能量較少的節(jié)點(diǎn)先決策自己的狀態(tài)，如此，剩余能量更高的節(jié)點(diǎn)會(huì) 自愿負(fù)責(zé)監(jiān)控目標(biāo)。上述做法在有多個(gè)節(jié)點(diǎn)同時(shí)做出決策時(shí)可能會(huì)導(dǎo)致覆蓋漏洞。比如有兩個(gè)節(jié)點(diǎn)A和B 監(jiān)控同一個(gè)目標(biāo)。如果A和B在重配

8、置階段具有相同的能量水平，它們會(huì)以為對(duì)方是活躍 狀態(tài)從而都進(jìn)入睡眠狀態(tài)。為了解決這個(gè)問(wèn)題，公式(2)可以修改成如下形式：:是一個(gè)比:小得多的隨機(jī)值。在重配置階段最后，只有一部分節(jié)點(diǎn)被激活執(zhí)行感知任 務(wù)，其他節(jié)點(diǎn)則進(jìn)入睡眠狀態(tài)保存能量和再充電。2.2 資格測(cè)試資格測(cè)試的目的是判定一個(gè)節(jié)點(diǎn)是不是有價(jià)值的，從而決定是不是激活它。有價(jià)值是指一個(gè)節(jié)點(diǎn)當(dāng)前處于睡眠狀態(tài)，并且能夠跟其他節(jié)點(diǎn)一起組成一個(gè)子集節(jié)點(diǎn)，這個(gè)子集能夠覆 蓋某個(gè)活躍節(jié)點(diǎn)監(jiān)控的所有目標(biāo)。假定節(jié)點(diǎn)叭處于活麻狀態(tài)其即曲環(huán) 區(qū)（小表示節(jié)點(diǎn)生的鄰居節(jié)點(diǎn)覆蓋的目標(biāo)，1:表示鄰居節(jié)點(diǎn)的epoch。這些信息存儲(chǔ)在數(shù)組門(mén)中。曲心二表示節(jié)點(diǎn)二的鄰居節(jié)點(diǎn)的子

9、集，能夠覆蓋所有門(mén)監(jiān)控的目標(biāo)。有如下關(guān)系： 二匚二二乂上：匚，乂上二匚=: s假定匚丟三 壬=三匚二h丟三三 匸 =：- = .Z -：/-=：=.重配置階段時(shí)，-1會(huì) 做如下兩步測(cè)試：1）如果邑二：二:士忑二：否則-進(jìn)入第二步。2）如果一在5ubX -中，說(shuō)明它覆蓋了所有被二監(jiān)控的目標(biāo)。一通過(guò)測(cè)試。如果一在第一步通過(guò)了測(cè)試，則將其epoch更新為：:。如果匸在第二步通過(guò)測(cè)試，一：將 epoch更新為subNJ中最大的epoch。同時(shí)-也將其epoch更新為新的：:。如果-沒(méi) 有通過(guò)測(cè)試，則二者的epoch均保持不變。如果，通過(guò)了多個(gè)活躍鄰居節(jié)點(diǎn)的測(cè)試，將其 epoch 更新為最早的一個(gè)。根據(jù)

10、資格測(cè)試，有如下命題。命題2：節(jié)點(diǎn)匚和5.： J會(huì)正好在:或者早于這個(gè)時(shí)間進(jìn)入重配置階段。證明：在進(jìn)行了測(cè)試之后，二的所有鄰居節(jié)點(diǎn)的epoch不會(huì)超過(guò):。在二將其epoch 更新為subNJ中最大的epoch后，匚的任何一個(gè)在:之前達(dá)到epoch并且進(jìn)入重配置 階段的鄰居節(jié)點(diǎn)都會(huì)更新它們的epoch。這就是命題2的內(nèi)容。2.3MaximumEnergyProtectionAlgorithm （MEP 算法）系統(tǒng)初始化時(shí)，所有節(jié)點(diǎn)進(jìn)入重配置階段，依據(jù)off-duty規(guī)則決定各自的狀態(tài)。如果 節(jié)點(diǎn)刀決定進(jìn)入睡眠狀態(tài)，則將其epoch設(shè)置為守，并發(fā)送廣播消息TURN OFF,其中包含自己的epoch

11、和目標(biāo)。如果節(jié)點(diǎn)決定進(jìn)入活躍狀態(tài)，則將epoch設(shè)置為當(dāng)前電 池壽命，并初始化一個(gè)空數(shù)組一。數(shù)組中存放的是其鄰居節(jié)點(diǎn)的epoch和目標(biāo)。個(gè)處在活躍狀態(tài)的節(jié)點(diǎn)接收到鄰居節(jié)點(diǎn)發(fā)來(lái)的TURN OFF消息時(shí)，將鄰居節(jié)點(diǎn)存 儲(chǔ)到、中并對(duì)其進(jìn)行，資格測(cè)試”，如果鄰居節(jié)點(diǎn)通過(guò)了測(cè)試，活躍節(jié)點(diǎn)會(huì)回應(yīng)一個(gè)SET EPOCH的消息。否則，不予回應(yīng)。如果一個(gè)節(jié)點(diǎn)收到多個(gè)SET EPOCH消息，它會(huì)將其epoch設(shè)置成最早的那個(gè)。這 種情況可能產(chǎn)生冗余。例如，二收到兩個(gè)SET EPOCH消息，分別來(lái)自它的兩個(gè)活躍鄰居 節(jié)點(diǎn)A和B,其中4二弓 況二洪。一會(huì)將其epoch設(shè)置為5并在該時(shí)刻進(jìn)入重配置階段。 如果工決策進(jìn)入

12、活躍狀態(tài),便會(huì)產(chǎn)生冗余，因?yàn)锽節(jié)點(diǎn)還要3個(gè)時(shí)間單位才達(dá)到它的epoch。 為了減少冗余，節(jié)點(diǎn)激活自己時(shí)廣播一個(gè)CHECK REDUNDANT消息給它的活躍狀態(tài)的 鄰居節(jié)點(diǎn)。當(dāng)一個(gè)活躍節(jié)點(diǎn)收到上述消息后會(huì)立即進(jìn)入重配置階段決定自己的狀態(tài)。三、實(shí)驗(yàn)與總結(jié)每一個(gè)傳感器節(jié)點(diǎn)都裝備了太陽(yáng)能電池。假設(shè)太陽(yáng)能的轉(zhuǎn)換率為 10%，可再充電效率 為 50%。假定每一個(gè)節(jié)點(diǎn)都裝備一個(gè)計(jì)時(shí)器，可以觸發(fā)節(jié)點(diǎn)從睡眠狀態(tài)進(jìn)入重配置階段。將MEP與CPNS（覆蓋面保護(hù)節(jié)點(diǎn)方案）和DEEPS（適用于傳感器的確定性能量高效協(xié)議） 比較。分別觀(guān)測(cè)目標(biāo)密度，傳感器節(jié)點(diǎn)密度和節(jié)點(diǎn)感知范圍的變化對(duì)三種算法的網(wǎng)絡(luò)生命周 期和平均冗余程度

13、產(chǎn)生的影響。網(wǎng)絡(luò)生命周期 從無(wú)線(xiàn)傳感器網(wǎng)絡(luò)開(kāi)始運(yùn)作到有一個(gè)目標(biāo)不再被任何節(jié)點(diǎn)監(jiān)控為止。平均冗余程度 代表的是監(jiān)控相同目標(biāo)的傳感器數(shù)的平均值。任何一個(gè)活躍狀態(tài)的節(jié) 點(diǎn)監(jiān)控一個(gè)被其他活躍節(jié)點(diǎn)覆蓋的目標(biāo)都會(huì)增加冗余程度。實(shí)驗(yàn)表明，與CPNS和DEEPS算法相比，MEP算法增加了至少30%的網(wǎng)絡(luò)生命周期， 降低了 10%的網(wǎng)絡(luò)冗余。、一些思考如前所述，WSN面臨的一個(gè)嚴(yán)峻挑戰(zhàn)是能量有限。WSN多用電池提供能量，對(duì)于一個(gè) 部署好的WSN，為其傳感器節(jié)點(diǎn)更換電池是一件繁瑣，浩大的工程，有時(shí)甚至是不可操作 的。于是，如何盡可能延長(zhǎng)WSN的生命周期成了關(guān)鍵所在。隨著能量采集技術(shù)在WSN中 的應(yīng)用，上述WSN面臨的挑戰(zhàn)得到一定程度的緩解。但即便是在具備能量采集功能的W