一種基于能量感知無線傳感器網(wǎng)絡(luò)多路徑路由機制

摘要:目前，無線傳感器網(wǎng)絡(luò)在智能環(huán)境檢測，災(zāi)難控制，戰(zhàn)場偵察，安全監(jiān)視方面取得了日益廣泛的應(yīng)用，引起人們?nèi)找骊P(guān)注，在分析無線傳感器網(wǎng)絡(luò)能量消耗特征的基礎(chǔ)上，基于Markov模型提出了無線傳感器網(wǎng)絡(luò)節(jié)點能量消耗模型，改進了無線傳感器網(wǎng)絡(luò)多路徑路由協(xié)議。仿真結(jié)果表明，與傳統(tǒng)的多路徑路由機制相比，能夠有效地降低無線傳感器網(wǎng)絡(luò)節(jié)點能量消耗，提高網(wǎng)絡(luò)生存時間。

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò); Markov; Wavelet;能量消耗

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2010)21-5743-05

A Energy-aware Multipath Routing in Wireless Sensor Networks

WANG Lin1， DUAN Xiao-yang2

(1.College of Software Engineering， Tongji University， Shanghai 201804， China; 2.School of Computer and Information Engineering Henu University， Kaifeng 475004， China)

Abstract: Recently， there has been a growing interest in the potential use of Wireless Sensor Networks (WSNs) in many applications such as smart environments， disaster management， combat field reconnaissance， and security surveillance. Therefore， to realize their potential， there is a need of an simulation platform that facilities the research of wireless sensor network .This paper focuses on developing node energy consumption in WSN.Therefore， we proposed a energy consumption model based on Markov chain， Furthermore， using the proposed algorithm to improve the multi-paths route scheme can extend the lifetime of the whole WSN by remaining load evenly distributed among several paths. According to performance comparison betweenthe traditional algorithmand the new method， numerical results have been proved feasible.

Key words: WSN; markov; multipath route; energy consumption

無線傳感器網(wǎng)絡(luò)(wireless sensor network，簡稱WSN )的相關(guān)研究已經(jīng)成為現(xiàn)階段國內(nèi)外研究的熱點[1-4]，這不僅因為WSN相關(guān)領(lǐng)域技術(shù)的迅速發(fā)展，如微機電系統(tǒng)(Micro-Electro-Mechanism System)、無線通信和數(shù)字電子技術(shù)的發(fā)展，另外也是由于WSN在國防軍事、環(huán)境監(jiān)測、交通管理、醫(yī)療衛(wèi)生、防恐抗災(zāi)等眾多領(lǐng)域的廣闊應(yīng)用前景。WSN相關(guān)協(xié)議需要考慮的主要因素有傳感器網(wǎng)絡(luò)節(jié)點的有限計算能力和存儲空間、傳感器節(jié)點有限的能量資源等。由于傳感器網(wǎng)絡(luò)有限的計算能力和存儲空間，為盡可能減小節(jié)點的運算開銷，所設(shè)計的路由協(xié)議必須簡單有效。另外，傳感器節(jié)點通常由電池供電，因此如何高效率地利用有效的電池資源，從而盡可能地延長節(jié)點的生命周期也是WSN相關(guān)協(xié)議要考慮的重點因素。WSN的網(wǎng)絡(luò)管理與傳統(tǒng)網(wǎng)絡(luò)管理相比，不僅包括QoS支持、故障管理等功能域，還包括能量管理[2]。而WSN能量管理的核心是能量消耗模型，因此不管在理論意義上還是在現(xiàn)實價值中，建立WSN能量消耗模型都顯得十分重要。

WSN路由協(xié)議的任務(wù)是通過建立路由，使傳感器節(jié)點和匯聚節(jié)點之間可靠地傳遞數(shù)據(jù)。能量多路徑路由[5]在源節(jié)點和目的節(jié)點之間建立多條路徑，首先基于能量因素給每條路徑賦予被選擇使用的概率，在發(fā)送數(shù)據(jù)時，根據(jù)賦予的概率隨機選擇其中的一條路徑發(fā)送，這樣就沒有一條路徑一直傳送數(shù)據(jù)的現(xiàn)象，從而防止一條路徑上節(jié)點能量消耗過快。就是在源節(jié)點和目的節(jié)點之間建立多條路徑，根據(jù)路徑上節(jié)點的通信量消耗以及節(jié)點的均衡消耗節(jié)點能量延長網(wǎng)絡(luò)的生存期。但是由于其是在節(jié)點發(fā)生故障之后進行路徑切換的，因此耗費了大量節(jié)點的能量資源。

本文針對現(xiàn)有網(wǎng)絡(luò)傳感器網(wǎng)絡(luò)節(jié)點能量消耗的特點，在分析WSN節(jié)點能量消耗特征的基礎(chǔ)上，通過對無線傳感器網(wǎng)絡(luò)節(jié)點的運行狀態(tài)利用Markov來進行模擬，建立了無線傳感器與網(wǎng)絡(luò)的節(jié)點能量消耗模型，并基于能量消耗模型改進了無線傳感器網(wǎng)絡(luò)多路徑路由機制，通過在J-sim [6]無線傳感器網(wǎng)絡(luò)仿真平臺進行仿真對比，結(jié)果驗證了Markov節(jié)點能量消耗模型的性能，通過分析改進前后的無線傳感器網(wǎng)絡(luò)多路徑機制，結(jié)果表明基于能量感知的多路徑路由機制能夠有效降低節(jié)點能量消耗，提高網(wǎng)絡(luò)生存時間。

下文組織如下，第二節(jié)在分析WSN節(jié)點能量消耗的基礎(chǔ)上提出了一個WSN節(jié)點能量消耗模型;第三節(jié)基于能量消耗模型，改進了傳統(tǒng)的WSN多路徑路由機制;第四節(jié)在Jsim仿真平臺分別對WSN能量消耗模型和改進前后的多路徑路由機制進行了分析;最后在第五節(jié)總結(jié)全文。

1 無線傳感器網(wǎng)絡(luò)節(jié)點能量消耗模型

1.1 無線傳感器網(wǎng)絡(luò)節(jié)點能量消耗分析

典型的傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)通常由分布的傳感器節(jié)點、接收發(fā)送器、互聯(lián)網(wǎng)和用戶界面等構(gòu)成。其中，傳感器節(jié)點作為網(wǎng)絡(luò)中的獨立工作實體，其基本的功能子系統(tǒng)包括供電子系統(tǒng)、計算子系統(tǒng)、傳感子系統(tǒng)和通信子系統(tǒng)等，如圖1所示，其能量消耗分別說明如下。

供電子系統(tǒng):主要任務(wù)是為其他各個子系統(tǒng)供給能源，它主要由電池和DCDC轉(zhuǎn)換器等模塊構(gòu)成。電池是節(jié)點最主要的能量來源，因此它的性能與容量就顯得至關(guān)重要。為實現(xiàn)延長供電子系統(tǒng)的能量供給時間，從而給其他子系統(tǒng)提供持續(xù)性的能量供應(yīng)，可以采用增加電池容量的方法，但采用有效的再充電技術(shù)或是太陽能等再生性能源則更利于保證供電子系統(tǒng)的能量來源，。

計算子系統(tǒng):主要任務(wù)是負責(zé)控制傳感器、執(zhí)行通信協(xié)議和處理傳感數(shù)據(jù)等軟件算法，是節(jié)點的控制和計算核心。它主要包括存儲器和I/O接口電路、微處理器/微控制器、存儲器等硬件。作為節(jié)點的數(shù)據(jù)計算中心和功能控制中心，計算子系統(tǒng)與其他各個子系統(tǒng)聯(lián)系十分緊密，功能也很復(fù)雜。因此，其性能高低、功能強弱、在不同工作狀態(tài)(活動、空閑和休眠等)的持續(xù)時長以及不同狀態(tài)間的相互切換等，都會對整個節(jié)點的能量消耗產(chǎn)生嚴重影響。硬件上減少計算子系統(tǒng)能量消耗的常用技術(shù)包括低功耗器件、適時休眠和空閑時的降頻技術(shù)等。而要從網(wǎng)絡(luò)的整體來實現(xiàn)網(wǎng)絡(luò)節(jié)點的能量消耗相對均衡，則采用的主要是節(jié)點間的功能輪換。

傳感子系統(tǒng):主要任務(wù)是將采樣/收集被測控對象的敏感信息轉(zhuǎn)換成相應(yīng)的數(shù)字信息，它主要由一組傳感器和ADC、控制器等構(gòu)成。理想情況下，傳感子系統(tǒng)自動檢測周期性和非周期性兩類事件時[7]，它的能量消耗總量可以簡單描述為單次采樣消耗的能量與采樣次數(shù)的乘積。因此，該子系統(tǒng)的能量消耗可以從以下兩個方面進行控制:一是控制單次數(shù)據(jù)采樣所消耗的能量， 可通過采用低功耗器件，從元器件本身有效控制單次數(shù)據(jù)采樣的能量消耗。二是控制采樣頻率，有選擇性地減少單個節(jié)點的采樣頻率，由于傳感器網(wǎng)絡(luò)眾多分布節(jié)點中往往是成組節(jié)點去監(jiān)測相同的對象或敏感數(shù)據(jù)，因此它不會對被測數(shù)據(jù)有效性和完整性造成破壞，只要依據(jù)應(yīng)用需求合理設(shè)置節(jié)點采樣任務(wù)的激活原則，就能在保證數(shù)據(jù)準確性的前提下，較好地控制該子系統(tǒng)的能量消耗。

通信子系統(tǒng):主要任務(wù)是負責(zé)節(jié)點的通信，由無線收發(fā)部件(radio)構(gòu)成。影響通信子系統(tǒng)能量消耗的關(guān)鍵因素[8-9]包括無線收發(fā)部件采用的調(diào)制模式、數(shù)據(jù)率、發(fā)射功率和操作周期等。另外，在沒有通信任務(wù)時，通信子系統(tǒng)應(yīng)盡可能地處于休眠期，而不是處于空閑期[9]。這是因為通信子系統(tǒng)即使處于空閑期，也有著與接收期幾乎相近的能量消耗。

根據(jù)以上分析，以分簇方式組織的無線傳感器網(wǎng)絡(luò)，節(jié)點能量消耗主要是數(shù)據(jù)發(fā)送和數(shù)據(jù)處理模塊，節(jié)點運行時共分為6個狀態(tài)，如表1所示。其中狀態(tài)3和狀態(tài)4消耗能量最多。

1.2 基于Markov的無線傳感器網(wǎng)絡(luò)節(jié)點能量預(yù)測模型

無線傳感器網(wǎng)絡(luò)節(jié)點的狀態(tài)轉(zhuǎn)換是建立節(jié)點能量消耗仿真模型的基礎(chǔ)，采用Markov進行節(jié)點能量消耗的預(yù)測，其中關(guān)鍵點是轉(zhuǎn)移矩陣的生成。

1.2.1 狀態(tài)轉(zhuǎn)移概率矩陣生成模型

生成WSN狀態(tài)轉(zhuǎn)移矩陣有兩種可行的辦法，一種是WSN節(jié)點根據(jù)自身過去的歷史采集狀態(tài)值構(gòu)造自己的狀態(tài)轉(zhuǎn)移矩陣。另一種方法是混合在同一個區(qū)域中節(jié)點之間的概率，在這種情況下，遷移矩陣將代表一個網(wǎng)絡(luò)的特定區(qū)域中所有節(jié)點的行為。最終生成的狀態(tài)轉(zhuǎn)移陣如式(1)所示:

(1)

其中

2.2.2 Markov能量消耗預(yù)測模型分析

通過建立Markov仿真模型來模擬傳感器網(wǎng)絡(luò)節(jié)點能量消耗情況，其模型如下所示:

每個節(jié)點中用一個隨機變量序列表示該節(jié)點在這段時間的狀態(tài)，假設(shè)該隨機變量為X0，X1，X2……。那么每個節(jié)點在同一時間可以處在不同的模式下。Xn=i表示傳感器節(jié)點在時間段n處于操作模式i下。假定所有的狀態(tài)遷移發(fā)生在任何時間段的開始階段，如果狀態(tài)j是節(jié)點在狀態(tài)i后的下一個狀態(tài)，用Pij來表示節(jié)點由狀態(tài)i遷移到狀態(tài)j的概率，則這個概率可用下式來表示:

(1)

定義2階的遷移概率Pij(2)表示一個節(jié)點當(dāng)前在狀態(tài)i，經(jīng)歷兩次狀態(tài)遷移后到狀態(tài)j的概率，則該概率可表示為:

(2)

Pij(2)的計算如下式，可以由Pij得出:

(3)

由上可以得出，若Pij(n)為n階的遷移概率，則由Chapman-Kolmogorov方程式定義如下:

(4)

對于任意0

(5)

Pij(2)的值就是矩陣P和它自身的乘積矩陣P2(P*P)中第i行第j列的元素。類似的，Pij(n)就是矩陣P的n次方的第i行第j列的元素。又Pm+n=Pm*Pn，所以有:

(6)

在上面的模型中，傳感器節(jié)點的行為由遷移概率矩陣表示，每個節(jié)點的初態(tài)由X0表示，這樣我們就可以建立整個無線傳感器網(wǎng)絡(luò)能量消耗序列。

假定現(xiàn)在節(jié)點在初態(tài)i，即X0=i，節(jié)點在經(jīng)過T個時間段后到達狀態(tài)s，Pis(t)表示節(jié)點當(dāng)前處在初態(tài)I，經(jīng)歷t個時間段遷移到達狀態(tài)S的概率。則節(jié)點停留在任意的一個狀態(tài)s的時間段數(shù)可用下式計算:

(7)

假設(shè)BS表示節(jié)點在狀態(tài)S停留一個時間段所傳輸?shù)臄?shù)據(jù)量，BT表示節(jié)點當(dāng)前處在狀態(tài)i，經(jīng)過T個時間段后到達狀態(tài)s所傳輸?shù)臄?shù)據(jù)總量。而節(jié)點經(jīng)過T個時間段到達狀態(tài)s 的期望時間段數(shù)可由計算出來，于是可以得出BT:

(8)

由計算可以得出每個節(jié)點在時間T的數(shù)據(jù)，總的節(jié)點數(shù)由下式來計算:

(9)

其中BS表示一個節(jié)點在狀態(tài)s 停留一個時間段所傳輸?shù)臄?shù)據(jù)量，Ck-i表示它是屬于簇Ck 的第i個傳感器節(jié)點，Pis表示從狀態(tài)i遷移到狀態(tài)s的概率。

綜合上述可知，根據(jù)無線傳感器網(wǎng)絡(luò)的狀態(tài)轉(zhuǎn)移矩陣和建立Markov模型可以預(yù)測節(jié)點在T時刻的能量消耗。

2 改進多路徑路由協(xié)議

2.1 改進思想

在傳感器網(wǎng)絡(luò)中，為了實現(xiàn)網(wǎng)絡(luò)負載平衡和提高數(shù)據(jù)傳輸?shù)目煽啃裕谑且肓硕嗦窂铰酚伞Ｎ墨I提出一種多路徑路由機制，通過預(yù)先建立和維護一組數(shù)據(jù)，從而不需要周期性洪泛就能夠得到從數(shù)據(jù)源節(jié)點到匯聚節(jié)點的傳輸路徑。其基本思想是:在從數(shù)據(jù)源節(jié)點到匯聚節(jié)點之間除了建立一條主路徑之外，還建立多條備份路徑，首先通過主路徑傳送數(shù)據(jù)來維護數(shù)據(jù)的有效性，但當(dāng)主路徑失敗時，就從建立的備用路徑中選擇次優(yōu)路徑進行數(shù)據(jù)傳送。但是，這種思想并不適用于WSN的需求，因為由主路由失敗觸發(fā)的切換機制所引起的負載不均衡會導(dǎo)致傳感器節(jié)點資源消耗的不均衡，從而降低WSN全網(wǎng)的生存期。改進該思想，可以引入能量消耗預(yù)測機制，這樣主路徑在預(yù)測其將要傳輸失敗前就切換至次優(yōu)路徑，從而實現(xiàn)WSN多路徑之間的負載均衡。

2.2 實例分析

如在圖2所示的WSN節(jié)點拓撲中，節(jié)點A為傳感器源節(jié)點，匯聚節(jié)點sink node是目的節(jié)點，在基于預(yù)測的多路徑路由機制中，假定路徑A-B-C-D-sink node 為主路徑，其他兩條路徑為次優(yōu)路徑。其基本步驟為:

1) 在主路徑A-B-C-D-sink node中，每個關(guān)鍵節(jié)點中都建立了Markov能量消耗預(yù)測模型。

2) 主路徑中的關(guān)鍵節(jié)點從本地檢測網(wǎng)絡(luò)流量，建立閾值，如果檢測到即將發(fā)生擁塞，或者本節(jié)點能量即將耗盡，或者流量超過本節(jié)點負載，則給源節(jié)點A發(fā)送一個消息。

3) 源節(jié)點A接收到關(guān)鍵節(jié)點發(fā)送的消息后，就會立即進行路徑切換，選擇一條次優(yōu)路徑進行數(shù)據(jù)傳輸。

3 仿真比較分析

3.1 Markov能耗預(yù)測模型仿真說明

仿真的主要目的是比較Markov能量消耗感知模型和真實WSN能量消耗的性能，共分為訓(xùn)練時間比較和預(yù)測效果比較兩個方面，采用了J-sim平臺進行比較仿真驗證。J-Sim是一種基于Java的、開放源代碼的、實時進程驅(qū)動的網(wǎng)絡(luò)仿真平臺。該項目由美國DARPA、NSF、Cisco公司及美國高校項目資助開發(fā)。除了支持IP網(wǎng)絡(luò)之外，J-Sim還支持多種有線(MPLS、區(qū)分服務(wù)、綜合服務(wù))和無線網(wǎng)絡(luò)(Ad hoc網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò))，能夠?qū)Σ煌W(wǎng)絡(luò)層次、不同網(wǎng)絡(luò)結(jié)構(gòu)、不同網(wǎng)絡(luò)組件進行實時仿真。

具體仿真步驟如下所示:

1) 在真實環(huán)境中中進行WSN節(jié)點能量消耗采集，采樣流量數(shù)據(jù)的采集是每隔1秒采集一個數(shù)據(jù)，采集了88組數(shù)據(jù)。

2) 在J-Sim中，擴展實現(xiàn)Markov能量消耗模型。

3) 把步驟1)中所采集得到的WSN節(jié)點能量消耗數(shù)據(jù)序列化為矩陣。

4) 利用Markov能量消耗模型模擬WSN節(jié)點能量消耗過程。

5) 將仿真結(jié)果利用Jsim繪圖工具繪制成圖。

真實無線傳感器網(wǎng)絡(luò)節(jié)點采用了Medusa II Nodes.其能量消耗參數(shù)如表2所示。

3.2 WSN能量消耗仿真結(jié)果分析

仿真結(jié)果如圖3所示，在時間段(0，12)WSN節(jié)點狀態(tài)為休眠狀態(tài)，能量消耗比較少，在時間段(21，42)WSN節(jié)點采集傳感數(shù)據(jù)，在時刻31秒是能量消耗很大，然后節(jié)點在時間段(47，60)進行傳感數(shù)據(jù)處理，節(jié)點能量消耗相對較低，最后在(70，88)節(jié)點把傳感數(shù)據(jù)通過路由協(xié)議發(fā)送給其他節(jié)點，整體能量消耗達到最大點，與真實WSN節(jié)點能量消耗過程相比，Markov能量消耗模型能夠準確的預(yù)測出節(jié)點運行狀態(tài)變換，而且在每一個狀態(tài)中模擬曲線對實際WSN節(jié)點能量消耗具有良好的逼近性能，整體誤差范圍較小，說明基于Markov的WSN能量消耗仿真模型能夠有效的預(yù)測現(xiàn)有真實WSN節(jié)點的能量消耗過程。

3.3 WSN多路徑仿真

利用J-sim對改進前后的多路徑路由協(xié)議進行了性能比較。實驗參數(shù)如表3所示。

感知節(jié)點每次采樣生成的數(shù)據(jù)量為4096byte，分別用改進前后的多路徑路由協(xié)議機制對數(shù)據(jù)進行傳送。試驗中對生存節(jié)點個數(shù)和全網(wǎng)的能耗在每個采樣周期都進行了統(tǒng)計。統(tǒng)計結(jié)果如圖4所示。

圖4(a)為改進前后的存活節(jié)點的采樣值的統(tǒng)計圖。在前400s內(nèi)，存活節(jié)點的數(shù)量均未減少，而在400s之后，改進前的多路徑路由協(xié)議的存活節(jié)點數(shù)迅速下降，在600s內(nèi)即減少為0，而在改進后的多路徑路由協(xié)議機制中，節(jié)點的減少速度相對較小，特別在400s-500s之間，與改進前的相比節(jié)點的存活數(shù)減少趨勢較為平緩，最終在700s處才減少為0。因此改進后的協(xié)議可有效地減小WSN存活節(jié)點的減少速度。

圖4(b)為改進前后的全網(wǎng)能耗的統(tǒng)計圖。全網(wǎng)的初始功率為200J。基于能量預(yù)測的多路徑路由協(xié)議在同采樣時刻中的能耗和全網(wǎng)的生存期中，都表現(xiàn)出較改進前的更好的性能。這是因為在改進前的多路徑路由協(xié)議中，路徑切換至次優(yōu)路徑中是在主路徑失敗之后，而在改進后的多路徑路由協(xié)議中，路徑的切換是在主路徑即將失敗時實現(xiàn)的，這樣就使得全網(wǎng)的負載在各個路徑中的分配得以有效地平衡。這種機制與固定網(wǎng)中常見的重路由機制相類似，區(qū)分WSN中切換的是整條路徑，而在固定網(wǎng)中只是在路由的某一結(jié)點處調(diào)整網(wǎng)絡(luò)流量的物理路徑。

4 結(jié)論

綜上分析，本文通過采用Markov過程來模擬WSN節(jié)點的運行狀態(tài)，從而建立了WSN的節(jié)點能量消耗模型，并通過在J-sim網(wǎng)絡(luò)仿真平臺將其與一個真實的WSN節(jié)點能量消耗進行了對比分析，仿真結(jié)果表明本文提出的WSN能量消耗模型能夠有效的表示W(wǎng)SN能量消耗過程，并將能量預(yù)測模型引入到WSN多路徑路由機制中，結(jié)果表明該機制能夠有效減少WSN能量消耗，提高WSN中的節(jié)點存活數(shù)量。

參考文獻:

[1] 孫利民，李建中.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社，2005，5.

[2] 崔莉，鞠海玲.無線傳感器網(wǎng)絡(luò)研究進展[J].計算機研究與發(fā)展，2005.42(1):163-174.

[3] Wireless Integrated Network Sensors， University of California， Los Angeles.Available: http://www.janet.ucla.edu/WINS.

[4] J.M. Kahn， R.H. Katz，，K.S.J. Pister.Next century challenges: Mobile for smart dust，in Proc. Mobicom，1999:483-492.

[5] Ganesan D.， Govindan R.etc Highly-resilient， energy-efficient multipath routing in wireless sensor networks. Mobile Computing Review，2002.1(2):11-25.

[6] Jsim.http://www.cs.uga.edu/~jam/jsim/.

[7] Rhee S，Seetharam D，Liu S，et al. I Beans: An Ultra low Power Wireless Sensor Network.Interactive Poster in the Fifth International Conference on Ubiquitous Computing (UBICOMP)，October，2003.

[8] A. Wang， S-H. Cho， C.G. Sodini， and A.P. Chandrakasan.Energy-efficient modulation and MAC for asymmetric microsensor systems， in Proc.ISLPED， 2001:106-111.

[9] C. Schurgers，O. Aberthorne， and M. Srivastava，Modulation scaling for energy aware communication systems， in Proc. ISLPED， 2001:96-99.

[10] Dhanaraj M，Manoj B S，et al.A New Energy Efficient Protocol for Minimizing Multihop Latency in Wireless Sensor Networks.Proc of the 3rd IEEE Int'l Conf.on Pervasive Computing and Communications，2005.

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文