基于網(wǎng)格拓?fù)涞臒o線傳感器網(wǎng)絡(luò)低能耗路由策略

張江豐

（浙江大學(xué)電氣工程學(xué)院，浙江杭州 310027）

0 引言

無線傳感器網(wǎng)絡(luò)是由一組微型傳感器節(jié)點以自組織方式構(gòu)成的無線網(wǎng)絡(luò)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋的地理區(qū)域中感知對象的信息，并發(fā)布給觀察者［1，2］。如今，集成了傳感器技術(shù)、無線通信技術(shù)、嵌入式系統(tǒng)和微處理技術(shù)的無線傳感器網(wǎng)絡(luò)已經(jīng)取得了快速的進(jìn)展，并被廣泛應(yīng)用于各個領(lǐng)域［1］。如何有效減少無線傳感器網(wǎng)絡(luò)的能量消耗、延長網(wǎng)絡(luò)的生存時間一直是研究的熱點與難點。無線傳感器網(wǎng)絡(luò)的能量主要消耗在節(jié)點間的通信上［3］，選擇合適的數(shù)據(jù)包傳輸路徑，能夠有效地減少通信能耗，從而延長網(wǎng)絡(luò)的生存時間。

本文主要研究無線傳感器網(wǎng)絡(luò)的網(wǎng)格拓?fù)浣Y(jié)構(gòu)，通過解決延遲約束下的中繼節(jié)點選擇問題，可以得到最優(yōu)的中繼選擇，以達(dá)到減少網(wǎng)絡(luò)通信能耗、延長網(wǎng)絡(luò)壽命的目的。該算法主要應(yīng)用于實時無線傳感器網(wǎng)絡(luò)系統(tǒng)，它能夠在滿足延遲約束的條件下給出低能耗的路由策略。

1 問題描述

無線傳感器網(wǎng)絡(luò)的網(wǎng)格拓?fù)浣Y(jié)構(gòu)是一個簡單的拓?fù)浣Y(jié)構(gòu)，其結(jié)構(gòu)示于圖1。本文主要研究網(wǎng)格拓?fù)浣Y(jié)構(gòu)下無線傳感器網(wǎng)絡(luò)的低能耗路由問題。

圖1 網(wǎng)格拓?fù)浣Y(jié)構(gòu)Fig 1 Grid topology structure

不同的無線傳感器網(wǎng)絡(luò)對實時性的要求是不同的。應(yīng)用于環(huán)境監(jiān)測、海底探測、礦山勘察等的無線傳感器網(wǎng)絡(luò)都是非實時系統(tǒng)，這些傳感器網(wǎng)絡(luò)的地面基站并不需要實時數(shù)據(jù)，同時，這些系統(tǒng)也能容忍較大的時間延遲。另一方面，監(jiān)控、入侵檢測、輔助導(dǎo)航和定位等系統(tǒng)卻對實時性要求很高，高延時是無法容忍的。本文主要研究應(yīng)用于實時系統(tǒng)的無線傳感器網(wǎng)絡(luò)的低能耗路由算法。在無線傳感器網(wǎng)絡(luò)中主要的延遲包含以下部分:

1）載波偵聽延時:發(fā)送者監(jiān)聽載體是否空閑的延時。

2）傳輸延時:帶寬約束造成的延時。

3）處理延時:節(jié)點中嵌入式芯片的計算能力決定處理延時。

4）傳播延時:由距離和傳播速度決定傳播延時。

因此，傳送一個數(shù)據(jù)包需要的時間為Tc+Tt+Tpc+Tp，其中，Tc為載波偵聽延遲，Ti為傳輸延遲，Tpc為處理延遲，Tp為傳播延遲。

首先，考慮最簡單的線性拓?fù)浣Y(jié)構(gòu)，如圖2，其中所有傳感器節(jié)點在同一直線上。很顯然，這類傳感器網(wǎng)絡(luò)消耗的主要能量在信息交流上，希望數(shù)據(jù)包經(jīng)過多跳轉(zhuǎn)發(fā)從源節(jié)點A到終節(jié)點B之間的節(jié)點時消耗最小的能量。然而，一個多跳帶來額外的載波偵聽延遲，傳輸延遲和處理延遲。在有延遲約束的實時系統(tǒng)中，有時會考慮犧牲一定的能量，以保證低延遲。因此，總的跳數(shù)在減少，同時每一跳的距離在變大，從而導(dǎo)致能耗的增加［4］，所以，需要在能耗和延時2個方面進(jìn)行折衷。

圖2 線性拓?fù)浣Y(jié)構(gòu)Fig 2 Linear topology structure

本文主要研究網(wǎng)格拓?fù)浣Y(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)。針對有實時性約束的無線傳感器系統(tǒng)，提出了一種中繼節(jié)點分配的算法。根據(jù)系統(tǒng)的實時性約束，首先確定最優(yōu)的跳數(shù)，然后在給定跳數(shù)的前提下，合理地分配中繼節(jié)點，以減少系統(tǒng)能耗。

2 模型與假設(shè)

在如圖1所示結(jié)構(gòu)中，傳感器節(jié)點只能向4個方向發(fā)送數(shù)據(jù)。本文中用無向圖G（V，E）來描述該傳感器網(wǎng)絡(luò)，其中，V代表節(jié)點集合，E代表鏈路集合［5］。

在網(wǎng)格拓?fù)渲?，如果一個節(jié)點向另一個節(jié)點發(fā)數(shù)據(jù)，至少有一條最小能耗路徑。這些路徑可以由DSAP［6］協(xié)議給出。為簡化問題考慮，只保留一條僅改變一次發(fā)送方向的路徑。例如:在圖1中，數(shù)據(jù)包由A經(jīng)C發(fā)送到B就是一條僅改變一次發(fā)送方向的路徑。假設(shè)傳感器節(jié)點的通信范圍能覆蓋整個網(wǎng)絡(luò)，從而數(shù)據(jù)包就能僅僅經(jīng)過一跳最終傳到目標(biāo)節(jié)點。

在通信過程中，傳感器節(jié)點的能耗主要包含發(fā)送能耗、接收能耗和放大器能耗。發(fā)送能耗用于保證通信模塊的正常運行，接收能耗用于保證接收模塊的正常運行。放大器能耗用于保證接收端的信號強度，這是由于信號在傳播過程中有衰減，因此，需要對信號進(jìn)行放大以補償傳播過程中的衰減。如果將發(fā)送能耗表示為Ptx，接收能耗表示成Prx，放大器能耗表示為Pamp，那么，在傳感器通信過程中的能耗為

其中，Pamp，k為第k個節(jié)點的放大器能耗，那么，在一條n跳的路徑中，總能耗為

通常情況下，發(fā)送能耗和接收能耗遠(yuǎn)遠(yuǎn)小于放大器能耗。一般情況下，放大器能耗可以表示為

其中，c和α均為常數(shù)，dk是第k條鏈路的長度。

在本文中，假設(shè)接收能耗和發(fā)送能耗均為100 nJ/bit。常數(shù)c=1，α=2。在無線傳感器網(wǎng)絡(luò)的路由協(xié)議中，希望能使Ptotoal盡可能小。

本文主要研究路由問題，MAC協(xié)議不在本文的研究范圍內(nèi)，因此，假設(shè)傳感器網(wǎng)絡(luò)所采用的MAC協(xié)議為ALOHA協(xié)議。

3 線性拓?fù)涞淖顑?yōu)跳數(shù)

線性拓?fù)涫亲詈唵蔚耐負(fù)浣Y(jié)構(gòu)，同時也是構(gòu)成網(wǎng)格拓?fù)涞幕A(chǔ)。在本節(jié)中，首先研究延時約束條件下，線性拓?fù)浣Y(jié)構(gòu)的中繼節(jié)點選擇，以實現(xiàn)較低的能耗。在線性拓?fù)渲?，如圖2，假設(shè)A需要向B發(fā)送數(shù)據(jù)，在數(shù)據(jù)發(fā)送過程中需要經(jīng)歷n個節(jié)點，如果這n個節(jié)點能將A，B間的連線n等分，那么，通信過程中的能耗能達(dá)到最小值。假設(shè)數(shù)據(jù)包從A需要經(jīng)過h跳到達(dá)B，A，B間的距離為l，本文希望選取h－1個中繼節(jié)點將l等分為h小段，那么相對應(yīng)的能耗可以表示為

通過將式（4）求導(dǎo)，可以很容易地得到最優(yōu)的跳數(shù)。然而在有實時性要求的傳感器系統(tǒng)中，數(shù)據(jù)包需要在規(guī)定時間內(nèi)到達(dá)基站。本文在第一節(jié)中提到，數(shù)據(jù)包傳輸過程中的總延時可以表示為Tc+Tt+Tpc+Tp。由于信號的傳播速度在理論上是光速，因此，忽略TP。同時，本文中采用ALOHA的MAC協(xié)議，因此，Tc也被忽略。從而數(shù)據(jù)包經(jīng)過h跳到達(dá)基站所經(jīng)歷的延時可以表示為h（Ti+Tpc）。如果基站希望在時間T內(nèi)收到數(shù)據(jù)包，那么延時約束可以表示為

最優(yōu)的跳數(shù)就是選擇合適的h，從而在滿足式（5）的條件下，使得Rtotal最小。由于約束函數(shù)h（Ti+Tpc）是關(guān)于h的線性函數(shù)，所以，該優(yōu)化問題等價于Karush-Kuhn-Tucker（KKT）問題。通過引入輔助變量λ，KKT問題可以表示為

通過解KKT問題，得到最優(yōu)的跳數(shù)為

4 路由算法

傳感器網(wǎng)絡(luò)的路由問題就是選擇一些合適的中繼節(jié)點，通過多跳轉(zhuǎn)發(fā)，使數(shù)據(jù)包從源節(jié)點最終到達(dá)基站。

對于線性拓?fù)浣Y(jié)構(gòu)，盡管能獲得線性拓?fù)涞淖罴烟鴶?shù)，中繼節(jié)點可能無法將源節(jié)點和目標(biāo)節(jié)點之間的連線等分。假設(shè)源節(jié)點和基站之間的距離為l，數(shù)據(jù)包需要經(jīng)過h跳到達(dá)目的地，定義一個輔助函數(shù)

其中，dij為i和j之間的歐氏距離，eij為一個0～1決策變量。eij=1 表示鏈路（i，j）被選中，eij=0 表示鏈路（i，j）未被選中。優(yōu)化問題式（11）是一個0～1整數(shù)線性規(guī)劃問題，通過求解該問題，可以得到相應(yīng)的中繼節(jié)點選擇，從而解決延時約束下的路由問題。

對于網(wǎng)格拓?fù)浣Y(jié)構(gòu)，它與線性拓?fù)浣Y(jié)構(gòu)最大的差別在于數(shù)據(jù)包的傳播方向會發(fā)生改變。因此，拐點必須作為中繼節(jié)點，以保證數(shù)據(jù)包的正確發(fā)送。在第1節(jié)中，已經(jīng)提到數(shù)據(jù)包至多改變傳播方向一次最終到達(dá)基站，所以，只能有1個拐點。該拐點所對應(yīng) 都必需取1，從而網(wǎng)格拓?fù)涞穆酚蓡栴}可以描述為

式中i為拐點。

通過解形式如式（12）的0～1整數(shù)線性規(guī)劃，便可以得到最終的路徑。

5 仿真結(jié)果

在仿真實驗中，網(wǎng)絡(luò)包括100個傳感器節(jié)點，這些節(jié)點被分布在10000 m×10 000 m的二維區(qū)域內(nèi)。傳感器節(jié)點上嵌入式芯片的CPU工作頻率大約是數(shù)十兆赫?？紤]到數(shù)據(jù)的操作，1 bit數(shù)據(jù)量的處理時間約為0．05 ms。因此，設(shè)Tp=0．05 ms，同時傳輸延遲是由信道頻率決定的，即Ti=1/f。圖3為時間約束1～3 s最優(yōu)跳數(shù)的變化。

圖3 延遲約束與最優(yōu)跳數(shù)關(guān)系圖Fig 3 Relationship between optimal hop number and delay constraint

一旦最優(yōu)跳數(shù)確定了，路由就可以通過解決0～1整數(shù)線性規(guī)劃來獲得。在仿真實驗中，選擇一個節(jié)點作為源節(jié)點，該節(jié)點需要向基站發(fā)送一個1000 bit的數(shù)據(jù)包，在不同時間約束下，其能耗如圖4所示。

6 結(jié)論

為了減少無線傳感器網(wǎng)絡(luò)的能量消耗，本文提出了一種基于網(wǎng)格拓?fù)浣Y(jié)構(gòu)無線傳感器網(wǎng)絡(luò)的新型路由算法。對于有時間限制的實時傳感器系統(tǒng)，通過減少跳數(shù)來保證低延時。在延時約束內(nèi)，本文通過解決一個KKT條件推導(dǎo)出最佳跳數(shù)。在得到最優(yōu)跳數(shù)的前提下，本文將中繼節(jié)點的分配問題轉(zhuǎn)化為0～1整數(shù)線性規(guī)劃問題，通過解該問題得到最終的多跳路徑。仿真結(jié)果表明:本文所提出的算法是有效可行的。

圖4 延遲約束下的網(wǎng)絡(luò)能耗Fig 4 Network energy consumption vs delay constraint

［1］ Akyildiz I，Su W，Sankarasubramaniam Y，et al．Survey on sensor networks［J］．IEEE Communications Magazine，2002，40（8）:102－114．

［2］ 孫利民，李建中，陳 渝，等．無線傳感器網(wǎng)絡(luò)［M］．北京:清華大學(xué)出版社，2005．

［3］ Pottie G，Kaiser W．Wireless integrated network sensors［J］．Communications of ACM，2000，43（5）:51 －58．

［4］ Heinzelman W，Chandrakasan A，Balakrishnan H．An applicationspecific protocol architecture for wireless microsensor networks［J］．IEEE Transactions on Wireless Communications，2002，1（4）:660－670．

［5］ Merris R．Graph theory［M］．USA:Wiley-IEEE，2001．

［6］ Salhieh A，Weinmann J，Kochhal M，et al．Power efficient topologies for wireless sensor networks［C］∥International Conference on Parallel Processing，Valencia，Spain，2001:156 －163．