隨著無線網(wǎng)絡(luò)以及硬件技術(shù)，特別是超大規(guī)模集成電路技術(shù)的發(fā)展，將感知、通信、計算能力集成在一個傳感器節(jié)點成為可能。無線傳感器網(wǎng)絡(luò)(以下簡稱傳感器網(wǎng)絡(luò))就是由成千上萬個這樣的節(jié)點構(gòu)成的。

　　它集感知、通信功能于一身，其目的就是實現(xiàn)對惡劣環(huán)境或者是人所不易到達的環(huán)境中各種參數(shù)(如溫度、濕度、目標位置等)的監(jiān)測和對某些敏感數(shù)據(jù)的采集。傳感器網(wǎng)絡(luò)如今已經(jīng)得到了廣泛的應(yīng)用，包括用以分析遠距離無人地區(qū)的環(huán)境情況(如依靠采集溫度來實現(xiàn)對森林火警的監(jiān)測);將感知節(jié)點安裝在特定的交通工具上以分析本地區(qū)的通信流量并由此設(shè)計出從源點到目標點的最佳交通路線;軍事上可用于監(jiān)測、定位和跟蹤目標點的運動;在高污染區(qū)還可以收集相關(guān)的信息以便于災(zāi)后重建。由于這些傳感器節(jié)點受自身規(guī)模的限制，而且能源有限，要給網(wǎng)絡(luò)內(nèi)大量的節(jié)點重新補充能源幾乎是不可行的，這就需要考慮如何在能源有限的情況下最大限度地降低節(jié)點能耗以延長傳感器網(wǎng)絡(luò)的連續(xù)工作時間。

　　1.準備工作

　　傳感器節(jié)點按其功能可分為以下三個模塊

　　①感知模塊。假定數(shù)據(jù)源的產(chǎn)生速率為r，則節(jié)點單位時間的感知耗能為Psense=a3r，a3為一常數(shù)(單位為J/bit);②通信模塊。給定發(fā)送節(jié)點u和接收節(jié)點v，發(fā)送數(shù)據(jù)的速率為r，兩個節(jié)點間的距離為d。有Ptrans(u，v)=(a11+a2dk)r，Prec=a12r。Ptrans(u，v)表示節(jié)點u單位時間的傳輸能耗，Prec表示節(jié)點v單位時間的接收能耗。其中，k為路徑衰減指數(shù)(k一般取2或4)，而a11，a12和a2均為無線通信常數(shù)(其中a2的取值與k有關(guān))。③計算模塊。相比于感知模塊和通信模塊來說，節(jié)點的計算模塊能耗很小，通?？梢院雎圆挥?。

　　本文假設(shè)：

　?、賯鞲衅骶W(wǎng)絡(luò)被應(yīng)用于目標跟蹤的場景下。②如圖1所示，E為網(wǎng)絡(luò)內(nèi)某一時刻的數(shù)據(jù)源節(jié)點，而傳感器節(jié)點主要用于對指定目標點的監(jiān)測并將采集到的結(jié)果以多跳的方式傳輸給遠端的收集節(jié)點B，這里我們認為節(jié)點B的能量充分大，即不考慮節(jié)點B的能耗。假設(shè)傳感器網(wǎng)絡(luò)中節(jié)點數(shù)量為N。③節(jié)點隨機的分布在有限區(qū)域R內(nèi)，節(jié)點的通信半徑為rt，節(jié)點間的數(shù)據(jù)傳輸是雙向的，即對于網(wǎng)絡(luò)中的任意兩個節(jié)點u和v，若節(jié)點u可與節(jié)點v直接通信，則節(jié)點v也可與節(jié)點u直接通信，如圖1，節(jié)點的感知半徑為ds，即感知節(jié)點只有在距數(shù)據(jù)源ds之內(nèi)才能感知到它的存在。④傳感器網(wǎng)絡(luò)內(nèi)所有的感知節(jié)點天線位于同一個水平線上，并且天線是全向的。⑤利用GPS技術(shù)傳感器節(jié)點可獲取自己的位置信息，目前GPS的精度可達5 m左右。

　　由文獻[3]可知，給定一個二維空間R，傳感器節(jié)點的感知半徑ds，能耗參數(shù)a11，a12，a2，a3和路徑衰變指數(shù)k，感知節(jié)點的數(shù)量N，每個節(jié)點的初始能量E，并且假定數(shù)據(jù)源運行軌跡遵循某個均勻分布的概率分布函數(shù)lsource(x，y)，則可得到網(wǎng)絡(luò)生存時間T的上限值為

　　2.算法思想

　　傳感器網(wǎng)絡(luò)實際上就是以數(shù)據(jù)為中心的自組織網(wǎng)絡(luò)，但在以前的關(guān)于傳感器網(wǎng)絡(luò)生存時間的研究中都是假定周圍環(huán)境是可靠的，即感知節(jié)點只有在能量完全耗盡時才會失效，這并未考慮環(huán)境對感知節(jié)點的影響。

　　在傳感器網(wǎng)絡(luò)中，由于距數(shù)據(jù)源ds內(nèi)的節(jié)點均能采集到數(shù)據(jù)并將數(shù)據(jù)進行轉(zhuǎn)發(fā)，因而如何保證這些節(jié)點盡可能的長時間持續(xù)運行是我們所關(guān)注的問題，針對該問題我們借鑒了容錯冗余的概念引入了備份的感知節(jié)點，使得某個感知節(jié)點的失效并不會影響整個網(wǎng)絡(luò)的正常工作。因而在本文中，我們提出了一個基于備份的分布式算法以延長網(wǎng)絡(luò)的連續(xù)工作時間，仿真結(jié)果表明在節(jié)點失效環(huán)境下通過合理的控制節(jié)點數(shù)量，該算法的持續(xù)工作時間要長于文獻[3]中的方法。

　　3.算法描述

　　在算法的實際運行中，可分為三個階段，分別為初始化階段、數(shù)據(jù)傳輸階段和任務(wù)接管階段。

　　在初始化階段，網(wǎng)絡(luò)中的每個節(jié)點需要確定自身到收集節(jié)點B的最小跳數(shù)。每個節(jié)點的初始狀態(tài)先置為工作態(tài)。收集節(jié)點首先以通信半徑rt廣播一個HOP消息。除收集節(jié)點之外，每個節(jié)點的初始跳數(shù)設(shè)置為無窮大。HOP消息的初始跳數(shù)設(shè)置為0。當某個節(jié)點收到HOP消息后，它將檢查是否已經(jīng)接收過該消息。如果未曾收到過，則該節(jié)點將把發(fā)送節(jié)點的信息(包括發(fā)送節(jié)點的ID號)放入其路由表中并把發(fā)送節(jié)點設(shè)為自己的上游節(jié)點，將HOP消息的跳數(shù)加1并將其值設(shè)置為自己的跳數(shù)，之后便以通信半徑rt將新的HOP消息轉(zhuǎn)發(fā)給鄰居節(jié)點;否則(即某個節(jié)點以前曾收到HOP消息)該節(jié)點將退避一段時間后再發(fā)送該HOP消息。并且，該節(jié)點只會考慮在退避時間內(nèi)所收到的最小跳數(shù)的HOP消息。

　　經(jīng)過退避時間后，節(jié)點將對所收到的HOP消息的跳數(shù)與節(jié)點以前曾保存的跳數(shù)進行比較：如果前者比后者小于1，則節(jié)點將把發(fā)送者的信息也放人路由表中作為自己的另一個不同的上游節(jié)點;如果前者小于后者且二者之差大于1，則發(fā)送者將成為該節(jié)點的新的上游節(jié)點。相應(yīng)的，路由表中的節(jié)點跳數(shù)以及消息跳數(shù)均需更新，修改后的HOP消息將繼續(xù)被該節(jié)點中轉(zhuǎn);如果前者不小于后者，則節(jié)點將丟棄這新收到的HOP消息。注意在以上的描述中，節(jié)點僅在收到第1個HOP消息時才會立即進行轉(zhuǎn)發(fā)。這一策略的好處在于可以加快HOP消息的傳輸速率，也縮短了初始化階段的執(zhí)行延遲。另一方面，引入退避時間的好處在于可以讓節(jié)點處于等待狀態(tài)以便可以從其鄰居節(jié)點接收到更多的HOP消息。雖然較長的退避時間會增加此階段的完成時間，但該方法是有效的，因為該階段對靜止的傳感器網(wǎng)絡(luò)來說只需執(zhí)行一次，并且也可以避免由于額外的轉(zhuǎn)發(fā)消息而增加的能耗。畢竟，能源問題是傳感器節(jié)點最寶貴的資源?？梢钥吹?，在初始化階段執(zhí)行之后，每個節(jié)點將準確的獲知自己的最小跳數(shù)以及其所有的上游節(jié)點。

　　當指定要監(jiān)測的目標出現(xiàn)后即進入了數(shù)據(jù)傳輸階段。感知到該目標的多個節(jié)點利用信息交互盡可能的挑選出跳數(shù)最小且自身能量最大的節(jié)點作為目標的感知節(jié)點，而其他感知到該目標的節(jié)點作為備份節(jié)點，這些備份節(jié)點將進入休眠狀態(tài)以降低節(jié)點能耗。在數(shù)據(jù)真正傳輸之前，真正的感知節(jié)點利用Rodoplu等人提出的MECN算法和節(jié)點的上游節(jié)點信息建立一條從源節(jié)點到收集節(jié)點B的最小能耗路徑。