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

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

      2 準(zhǔn)備工作

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

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

　　本文假設(shè)：

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

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

      3 算法思想

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

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

　　4 算法描述

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

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

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

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

      當(dāng)出現(xiàn)下述兩種情況之一時將進(jìn)入任務(wù)接管階段：①正常工作時(主動)的任務(wù)切換。此時，隨著感知節(jié)點(diǎn)的運(yùn)行，自身能耗也隨之下降，當(dāng)其無法再次完成數(shù)據(jù)的感知(或傳輸)任務(wù)時將主動地發(fā)起任務(wù)接管的命令。②感知節(jié)點(diǎn)異常時的任務(wù)切換。由于正常運(yùn)行時所有的備份節(jié)點(diǎn)處于休眠狀態(tài)，因此并不能使用分布式系統(tǒng)中的心跳技術(shù)來對感知節(jié)點(diǎn)的狀態(tài)進(jìn)行檢測。這里我們采用超時方法，即當(dāng)收集節(jié)點(diǎn)B在指定的時間間隔T內(nèi)無法收到來自目標(biāo)點(diǎn)的數(shù)據(jù)時，這就有可能存在感知節(jié)點(diǎn)失效的情況，此時收集節(jié)點(diǎn)B將會給傳感器網(wǎng)絡(luò)發(fā)出泛洪信息，利用定向擴(kuò)散的原理將備份節(jié)點(diǎn)集中的節(jié)點(diǎn)喚醒后重新進(jìn)行初始化操作。

　　當(dāng)距離數(shù)據(jù)源節(jié)點(diǎn)ds內(nèi)的所有傳感器節(jié)點(diǎn)均沒有足夠的能量可以將數(shù)據(jù)轉(zhuǎn)發(fā)給任意一個鄰居節(jié)點(diǎn)時，整個傳感器網(wǎng)絡(luò)的持續(xù)工作時間將會終止。

      5 算法消息負(fù)載分析

　　本節(jié)中，從單個節(jié)點(diǎn)平均處理的消息角度出發(fā)，我們對所提出算法的消息負(fù)載進(jìn)行簡單分析。

　　初始化階段：每個節(jié)點(diǎn)廣播的HOP消息數(shù)依賴于退避時間設(shè)置的大小?？梢钥吹饺绻吮軙r間足夠大，每個節(jié)點(diǎn)最多廣播2個HOP消息：在節(jié)點(diǎn)從其鄰居節(jié)點(diǎn)收到第1個HOP消息后將廣播第1個HOP消息；而當(dāng)退避時間超時后將廣播第2個HOP消息。

　　數(shù)據(jù)傳輸階段：感知節(jié)點(diǎn)只需要感知到指定目標(biāo)的多個節(jié)點(diǎn)之間的廣播消息即可確定，即此階段節(jié)點(diǎn)只需廣播1個消息。

　　任務(wù)接管階段：正常工作時的任務(wù)接管節(jié)點(diǎn)只需廣播1個消息；同樣，異常時的任務(wù)接管節(jié)點(diǎn)只需發(fā)送1個來自于收集節(jié)點(diǎn)的泛洪消息(實(shí)際上該階段與初始化階段節(jié)點(diǎn)廣播HOP消息的過程正好相反，我們可以寄期望如果該步驟的退避時間設(shè)置恰當(dāng)?shù)脑?，大多?shù)節(jié)點(diǎn)廣播的次數(shù)之多為1次)。可見，該階段每個節(jié)點(diǎn)最多廣播1個消息。

　　總之，如果初始化階段和任務(wù)接管階段的退避時間設(shè)置適當(dāng)?shù)脑?，算法中傳感器?jié)點(diǎn)的消息負(fù)載最多為4個廣播消息。

      6 仿真結(jié)果

　　采用由Berkeley大學(xué)開發(fā)的離散時間仿真工具Ns-2.29，假設(shè)傳感器網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)隨機(jī)均勻的分布在1500 m×1500 m的矩形范圍內(nèi)，節(jié)點(diǎn)的數(shù)量為N(150≤N≤1500)，每個節(jié)點(diǎn)的初始能量設(shè)置為2 J，其目的只是為縮短仿真實(shí)驗(yàn)的運(yùn)行時問，并不會對仿真實(shí)驗(yàn)的行為產(chǎn)生任何變化。節(jié)點(diǎn)的無線傳輸半徑rt設(shè)置為50 m，節(jié)點(diǎn)的感知半徑ds設(shè)置為20 m，路徑衰減參數(shù)k為4，a3=50 nJ／bit，a11=45 nJ／bit，a12=135 nJ／bit，a2=0.001 pJ／bit／m4，數(shù)據(jù)源的產(chǎn)生速率為1 bit／s，在節(jié)點(diǎn)上應(yīng)用的路由協(xié)議采用無線自組網(wǎng)的AODV協(xié)議，應(yīng)用層的流量發(fā)生器采用CBR(constant bit rate)，大小為512 bit／s。為得到更為可靠的數(shù)據(jù)結(jié)果，對每一種算法執(zhí)行100次，對每一次的實(shí)驗(yàn)，均產(chǎn)生10個隨機(jī)不同的傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，最終仿真結(jié)果通過取平均值得到，置信區(qū)間設(shè)為95％。

 　　在實(shí)際運(yùn)行中，考慮正常和失效(隨機(jī)模擬感知節(jié)點(diǎn)的失效)兩種情況下算法的性能。給定不同的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，將新算法與文獻(xiàn)[3]中的方法進(jìn)行比較，給出了實(shí)驗(yàn)中得到的仿真結(jié)果與由式(1)得到的理論值之間的比率，如圖2所示。

　　從圖2中可以看出，在正常情況下，新算法的網(wǎng)絡(luò)生命期要小于文獻(xiàn)[3]中的理論值，這是因?yàn)橄啾扔谖墨I(xiàn)[3]，新算法中在運(yùn)行過程中傳感器節(jié)點(diǎn)有一部分能量消耗在了算法消息交換的執(zhí)行上；而在感知節(jié)點(diǎn)失效的情況下，可以看到當(dāng)150≤N≤550或者是N≥750時新算法的網(wǎng)絡(luò)生命期要小于文獻(xiàn)[3]中的理論值，原因在于當(dāng)150≤N≤550時，由于網(wǎng)絡(luò)中感知節(jié)點(diǎn)過少，有的節(jié)點(diǎn)則既作為感知點(diǎn)又作為中轉(zhuǎn)節(jié)點(diǎn)，所以此時整個網(wǎng)絡(luò)的時間性能會下降得很快；而當(dāng)在N≥750時，隨著網(wǎng)絡(luò)中節(jié)點(diǎn)的增多，整個網(wǎng)絡(luò)的密度增大，每個節(jié)點(diǎn)的鄰節(jié)點(diǎn)數(shù)量增加，信道爭用、信道發(fā)生沖突的概率也會相應(yīng)增加。反過來也會給網(wǎng)絡(luò)的生存時間帶來不利的影響。但是當(dāng)550≤N≤750時，本算法的網(wǎng)絡(luò)生存時間要大于文獻(xiàn)[3]中的理論值，即新算法的網(wǎng)絡(luò)性能要優(yōu)于文獻(xiàn)[3]。因此，本文提出的分布式算法特別針對于網(wǎng)絡(luò)中節(jié)點(diǎn)失效情況下的處理方法是可行的。

　　圖3給出了算法在運(yùn)行過程中節(jié)點(diǎn)平均消息負(fù)載與時間的關(guān)系示意。由圖3可以看到隨著部署節(jié)點(diǎn)的增加，每個節(jié)點(diǎn)的平均消息負(fù)載并沒有顯著的增加，這從另一方面驗(yàn)證了文中所設(shè)計的算法可適用于大規(guī)模的傳感器網(wǎng)絡(luò)；此外，還觀察到從節(jié)點(diǎn)開始工作直至到達(dá)網(wǎng)絡(luò)的生存時間，每個節(jié)點(diǎn)最大的消息負(fù)載只有5個，因此該算法是有效的。

      7 結(jié) 論

　　為延長網(wǎng)絡(luò)的持續(xù)工作時間，提出了一個基于備份感知節(jié)點(diǎn)的分布式算法，實(shí)驗(yàn)證明了該算法在時間上有進(jìn)一步的提高，從而可以指導(dǎo)我們在現(xiàn)有的情況下如何對節(jié)點(diǎn)進(jìn)行優(yōu)化管理從而提高網(wǎng)絡(luò)生存時間。在今后工作中需要進(jìn)一步開展的研究方向包括：

　　①本文所提出的算法中在感知節(jié)點(diǎn)失效的情況下，由收集節(jié)點(diǎn)B主動發(fā)起泛洪信息，將會導(dǎo)致網(wǎng)絡(luò)無線通道的擁塞引起網(wǎng)絡(luò)性能的下降，并且網(wǎng)絡(luò)中會出現(xiàn)某些節(jié)點(diǎn)收到多個鄰節(jié)點(diǎn)發(fā)來的同一泛洪信息的現(xiàn)象，這將會占用節(jié)點(diǎn)寶貴的內(nèi)存資源。能否采用其他方法來避免這種不必要的通信開銷和資源占用是今后研究的一個方向。

　?、谠谒惴ㄖ?，假定數(shù)據(jù)源節(jié)點(diǎn)的數(shù)量為一個且位置固定，今后需考慮當(dāng)數(shù)據(jù)源節(jié)點(diǎn)為多個且移動情況下的分布式容錯算法。

　　③傳感器網(wǎng)絡(luò)的算法都是與應(yīng)用環(huán)境相關(guān)的，在某些情況下如果只使用一個感知節(jié)點(diǎn)的話，由于節(jié)點(diǎn)觀測事物角度的不同，將會影響數(shù)據(jù)采集結(jié)果的精確度，這就需要同時有多個節(jié)點(diǎn)間的合作以提高獲取數(shù)據(jù)的準(zhǔn)確度。如何在準(zhǔn)確性和網(wǎng)絡(luò)能耗兩個方面進(jìn)行折衷考慮也是一個值得研究的問題。