基于備份節點(diǎn)無(wú)線(xiàn)傳感器網(wǎng)絡(luò )設計策略

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

2 準備工作

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

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

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

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

3 算法思想

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

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

4 算法描述

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

在初始化階段，網(wǎng)絡(luò )中的每個(gè)節點(diǎn)需要確定自身到收集節點(diǎn)B的最小跳數。每個(gè)節點(diǎn)的初始狀態(tài)先置為工作態(tài)。收集節點(diǎn)首先以通信半徑rt廣播一個(gè)HOP消息。除收集節點(diǎn)之外，每個(gè)節點(diǎn)的初始跳數設置為無(wú)窮大。HOP消息的初始跳數設置為0。當某個(gè)節點(diǎn)收到HOP消息后，它將檢查是否已經(jīng)接收過(guò)該消息。如果未曾收到過(guò)，則該節點(diǎn)將把發(fā)送節點(diǎn)的信息(包括發(fā)送節點(diǎn)的ID號)放入其路由表中并把發(fā)送節點(diǎn)設為自己的上游節點(diǎn)，將HOP消息的跳數加1并將其值設置為自己的跳數，之后便以通信半徑rt將新的HOP消息轉發(fā)給鄰居節點(diǎn)；否則(即某個(gè)節點(diǎn)以前曾收到HOP消息)該節點(diǎn)將退避一段時(shí)間后再發(fā)送該HOP消息。并且，該節點(diǎn)只會(huì )考慮在退避時(shí)間內所收到的最小跳數的HOP消息。經(jīng)過(guò)退避時(shí)間后，節點(diǎn)將對所收到的HOP消息的跳數與節點(diǎn)以前曾保存的跳數進(jìn)行比較：如果前者比后者小于1，則節點(diǎn)將把發(fā)送者的信息也放人路由表中作為自己的另一個(gè)不同的上游節點(diǎn)；如果前者小于后者且二者之差大于1，則發(fā)送者將成為該節點(diǎn)的新的上游節點(diǎn)。相應的，路由表中的節點(diǎn)跳數以及消息跳數均需更新，修改后的HOP消息將繼續被該節點(diǎn)中轉；如果前者不小于后者，則節點(diǎn)將丟棄這新收到的HOP消息。注意在以上的描述中，節點(diǎn)僅在收到第1個(gè)HOP消息時(shí)才會(huì )立即進(jìn)行轉發(fā)。這一策略的好處在于可以加快HOP消息的傳輸速率，也縮短了初始化階段的執行延遲。另一方面，引入退避時(shí)間的好處在于可以讓節點(diǎn)處于等待狀態(tài)以便可以從其鄰居節點(diǎn)接收到更多的HOP消息。雖然較長(cháng)的退避時(shí)間會(huì )增加此階段的完成時(shí)間，但該方法是有效的，因為該階段對靜止的傳感器網(wǎng)絡(luò )來(lái)說(shuō)只需執行一次，并且也可以避免由于額外的轉發(fā)消息而增加的能耗。畢竟，能源問(wèn)題是傳感器節點(diǎn)最寶貴的資源?？梢钥吹?，在初始化階段執行之后，每個(gè)節點(diǎn)將準確的獲知自己的最小跳數以及其所有的上游節點(diǎn)。

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

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

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

5 算法消息負載分析

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

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

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

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

總之，如果初始化階段和任務(wù)接管階段的退避時(shí)間設置適當的話(huà)，算法中傳感器節點(diǎn)的消息負載最多為4個(gè)廣播消息。

6 仿真結果

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

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

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

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

7 結 論

為延長(cháng)網(wǎng)絡(luò )的持續工作時(shí)間，提出了一個(gè)基于備份感知節點(diǎn)的分布式算法，實(shí)驗證明了該算法在時(shí)間上有進(jìn)一步的提高，從而可以指導我們在現有的情況下如何對節點(diǎn)進(jìn)行優(yōu)化管理從而提高網(wǎng)絡(luò )生存時(shí)間。在今后工作中需要進(jìn)一步開(kāi)展的研究方向包括：①本文所提出的算法中在感知節點(diǎn)失效的情況下，由收集節點(diǎn)B主動(dòng)發(fā)起泛洪信息，將會(huì )導致網(wǎng)絡(luò )無(wú)線(xiàn)通道的擁塞引起網(wǎng)絡(luò )性能的下降，并且網(wǎng)絡(luò )中會(huì )出現某些節點(diǎn)收到多個(gè)鄰節點(diǎn)發(fā)來(lái)的同一泛洪信息的現象，這將會(huì )占用節點(diǎn)寶貴的內存資源。能否采用其他方法來(lái)避免這種不必要的通信開(kāi)銷(xiāo)和資源占用是今后研究的一個(gè)方向。②在算法中，假定數據源節點(diǎn)的數量為一個(gè)且位置固定，今后需考慮當數據源節點(diǎn)為多個(gè)且移動(dòng)情況下的分布式容錯算法。③傳感器網(wǎng)絡(luò )的算法都是與應用環(huán)境相關(guān)的，在某些情況下如果只使用一個(gè)感知節點(diǎn)的話(huà)，由于節點(diǎn)觀(guān)測事物角度的不同，將會(huì )影響數據采集結果的精確度，這就需要同時(shí)有多個(gè)節點(diǎn)間的合作以提高獲取數據的準確度。如何在準確性和網(wǎng)絡(luò )能耗兩個(gè)方面進(jìn)行折衷考慮也是一個(gè)值得研究的問(wèn)題。