1 引 言
 
      隨著無線網絡以及硬件技術，特別是超大規模集成電路技術的發展，將感知、通信、計算能力集成在一個傳感器節點成為可能。無線傳感器網絡(以下簡稱傳感器網絡)就是由成千上萬個這樣的節點構成的。

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

      2 準備工作

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

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

　　本文假設：

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

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

      3 算法思想

　　傳感器網絡實際上就是以數據為中心的自組織網絡，但在以前的關于傳感器網絡生存時間的研究中都是假定周圍環境是可靠的，即感知節點只有在能量完全耗盡時才會失效，這并未考慮環境對感知節點的影響。

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

　　4 算法描述

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

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

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

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

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

　　當距離數據源節點ds內的所有傳感器節點均沒有足夠的能量可以將數據轉發給任意一個鄰居節點時，整個傳感器網絡的持續工作時間將會終止。

      5 算法消息負載分析

　　本節中，從單個節點平均處理的消息角度出發，我們對所提出算法的消息負載進行簡單分析。

　　初始化階段：每個節點廣播的HOP消息數依賴于退避時間設置的大小。可以看到如果退避時間足夠大，每個節點最多廣播2個HOP消息：在節點從其鄰居節點收到第1個HOP消息后將廣播第1個HOP消息；而當退避時間超時后將廣播第2個HOP消息。

　　數據傳輸階段：感知節點只需要感知到指定目標的多個節點之間的廣播消息即可確定，即此階段節點只需廣播1個消息。

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

　　總之，如果初始化階段和任務接管階段的退避時間設置適當的話，算法中傳感器節點的消息負載最多為4個廣播消息。

      6 仿真結果

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

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

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

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

      7 結 論

　　為延長網絡的持續工作時間，提出了一個基于備份感知節點的分布式算法，實驗證明了該算法在時間上有進一步的提高，從而可以指導我們在現有的情況下如何對節點進行優化管理從而提高網絡生存時間。在今后工作中需要進一步開展的研究方向包括：

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

　　②在算法中，假定數據源節點的數量為一個且位置固定，今后需考慮當數據源節點為多個且移動情況下的分布式容錯算法。

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