能量感知的WSN節點分類控制路由算法*

劉 群，白全煒，曾憲華，王 亮

(重慶郵電大學計算機學院，重慶 400065)

無線傳感器網絡(WSN)是一種新型的無線通信網絡，它融合了通信技術，嵌入式計算技術和傳感器技術，由大量的傳感器節點通過無線介質連接構成，采用自組織的形式配置微型的智能傳感器節點，通過節點的協同工作來采集和處理網絡覆蓋區域中目標信息。傳感器節點通常由電池供電，而且在一些應用環境下更換電池或者對電池進行充電是不可行的，所以如何高效，合理地使用能源，盡可能地延長網絡的生命期，成為了傳感器網絡研究的核心問題之一［1－3］。

路由協議在無線傳感器網絡中起著相當重要的作用，并且其能量消耗也是網絡消耗中的主要部分，因此設計一種有效的路由協議是減少網絡能量消耗的關鍵。目前在無線傳感器網絡中，路由協議分為三類:平面路由、分層路由以及能量感知路由。

在平面路由中所有節點具有相同的地位和功能，它們通過相互之間的局部操作和信息反饋來生成路由。平面路由的優點是簡單、易擴散，無須進行任何結構維護工作，不易產生瓶頸效應，因此具有較好的健壯性，典型的平面路由有Flooding Routing［4］，DD(directed diffusion)［5］，SPIN(sensor protocols for information via negotiation)［6］等。平面路由的最大缺點在于:網絡中無管理節點，缺乏對通信資源的優化管理，對網絡動態變化的反應速度較慢等。

在分層路由中，LEACH算法［7］是第一個基于多簇結構的路由算法，其成簇思想貫穿于其后提出的多個算法中，但是也存在著不足。如在簇頭選舉的過程中沒有考慮到節點的剩余能量，可能能量較低的節點被選為簇頭，導致該節點過早死亡。HEED算法［8］在選擇簇頭時考慮了節點的剩余能量，但需要在一定的迭代次數內與周圍鄰居節點不斷地進行信息交互，因此算法的實現需要額外的通信代價。PEGASIS［9］則將節點組織成鏈的形式，鏈的形成由每一個節點或者基站計算得到，因此需要知道網絡拓撲的全局信息。

隨著無線傳感器網絡研究的深入，路由協議的研究已從當初避免網絡擁塞和保持網絡連通性等方面，轉而重點研究提高整個網絡的利用率、平衡網絡流量和能耗、減小通信延時等方面，而能量感知路由則代表著該研究方向。

文獻［10］提出了一種能量感知路由協議，EAR(Energy Aware Routing，簡稱EAR)協議。在該協議中，源節點和目的節點之間建立多條通信路徑，每條路由都具有一個與節點剩余能量有關的選擇概率，當源節點需要向目的節點傳輸數據時，協議根據路徑的選擇概率選擇一條路徑進行數據傳輸。但該機制沒有考慮對距離(跳數)的優化，且需周期性地實施洪泛查詢來進行路由維護，增加協議開銷。

文獻［11］提出的GEAR協議根據地理位置信息，建立Sink到監測區域的優化路徑，支持Sink向監測區所有節點發送查詢命令，避免了洪泛傳播方式，減少了路由建立的開銷。GEAR把節點到監測區域的距離和節點剩余能量定義為估計路由代價，并利用捎帶機制獲取實際路由代價，進行數據傳輸的路徑優化，形成能量高效的傳輸路徑。協議雖然實現了節點間的負載均衡，但在異構網絡中，初始能量較少的節點會較早耗盡能量而失效，影響整個網絡的性能。并且隨著網絡中建立的路由不斷增加，在路由方向上的節點耗能增大，其選擇代價增大，相應地，路由方向以外的節點會被優先選擇，從而出現數據在多個能量旺盛的節點間跳轉的現象，稱為“折線效應”，其直接的后果就是數據傳輸的延時增加，網絡總能耗增大。

針對GEAR協議的不足之處，本文提出了一種新的能量感知的WSN節點分類控制路由算法CEAR(Classifying Control-based Energy Aware Routing Algorithm fornodesin WirelessSensorNetworks，CEAR)。算法首先定義了能量閾值把普通節點分為骨干節點和獨立節點，從而保護初始能量較少的節點。然后骨干節點通過建立骨干路由樹來傳輸數據，獨立節點則根據周圍鄰居節點的不同情況采用不同的選擇函數進行下一跳路由;針對部分獨立節在傳輸數據時會出現“折線效應”，算法采用了自適應調整策略，從而消除此折線效應，提高了數據傳輸的時效性，節約了網絡總能耗。

論文余下部分結構如下:第1部分主要是介紹無線傳感器網絡的拓撲結構;第2部分從能量閾值、骨干路由樹的建立以及獨立節點的路由選擇三個大的方面具體闡述本文算法;第3部分通過實驗驗證CEAR算法在均衡節點能量消耗，傳送數據包和延時方面都優于GEAR算法;第4部分為總結與展望。

1 WSN拓撲結構描述

無線傳感器網絡沒有底層基礎設施。在傳感器被放置到監測環境后，傳感器自行組織構成網絡。其基本網絡拓撲可分為 3種［12］，分別是基于簇(Cluster)的分層結構、基于網(Mesh)的平面結構和基于鏈(Chain)的線結構，其各自的網絡拓撲結構如圖1所示。

圖1 自組織無線傳感器網絡拓撲圖

基于簇的分層結構具有天然的分布式處理能力，簇頭就是分布式處理中心，每個簇成員都把數據傳給簇頭，在簇頭完成數據處理和融合，然后由其他簇頭多跳轉發或直接傳給用戶節點，簇中的成員是輪流或者每次選擇剩余能量最多的成員做簇頭。基于網的平面結構傳感器節點連成一張網，網絡健壯性強，且傳輸可靠性非常高，個別鏈路和傳感器節點發生失效時，不會引起網絡分立，可以同時通過多條信源信宿間路由傳輸數據。基于鏈的線性結構傳感器節點被串聯在一條或多條鏈上，鏈尾與Sink節點相連。

2 CEAR路由算法

2.1 能量閾值

Sink節點需要周期性地探測網絡的能量情況來生成能量閾值，但探測整個網絡所有節點的能量情況會給網絡帶來更大負擔，所以Sink節點只探測周圍鄰居節點的能量情況，來近似估計整個網絡的能量情況，從而生成能量閾值。

定義1能量閾值(Energy Threshold):Sink節點首先對周圍鄰居節點的剩余能量進行探測［13］，統計并計算各鄰居節點剩余能量的均值，該均值為本文的能量閾值，即記

其中，Ni為sink節點周圍的第i個鄰居節點，n為鄰居節點個數為第i個鄰居節點的剩余能量。

定義2骨干節點(Mainstay Node，記作MN):如果任意普通節點Ni有Es(Ni)≥ET，那么該普通節點Ni屬于骨干節點。其中，Es(Ni)表示節點Ni自身的剩余能量。

定義 3獨立節點(Independent Node，記作IN):如果任意普通節點Nj有Es(Nj)＜ET，那么該普通節點Nj屬于獨立節點。其中，Es(Nj)表示節點Nj自身的剩余能量。

2.2 建立骨干路由樹

匯聚節點通過廣播路徑建立消息，各節點對廣播報文內的信息和自身信息進行判斷，建立骨干路由樹［14］，從而形成數據的主要傳輸路徑。具體步驟如下:

(1)如果節點是匯聚節點，則通過發送MYAGENT_ASK報文對鄰居節點的能量情況進行探測，并準備接收MYAGENT_ANSWER報文，從而近似估計出整個網絡的能量情況。

(2)如果傳感器節點收到MYAGENT_ASK報文，則回復MYAGENT_ANSWER報文來報告自身能量情況。

(3)匯聚節點通過接收MYAGENT_ANSWER報文來獲得鄰居節點的能量，將這些節點及其能量寫入MYAGENT_ENERGY緩沖區，并通過計算均值來獲得能量閾值。

(4)匯聚節點將能量閾值放入到MYAGENT_BROAD報文中，對網絡進行廣播。

(5)如果普通傳感器節點收到 MYAGENT_BROAD報文，首先將自身剩余能量與ET進行比較，如果小于ET，則節點被判定為獨立節點，轉向(6)。否則，通過到匯聚節點的跳數來決定是否將該節點放入骨干路由樹中。如果通過判斷該節點能夠加入到骨干路由樹中，則轉向(8)，否則繼續等待其他節點發送的MYAGENT_BROAD報文。

(6)當節點被判定為獨立節點時，就會定時發出MYAGENT_RREQ報文，對鄰居節點的情況進行探測，并準備接收MYAGENT_RREP報文，將鄰居節點情況寫入MYAGENT_RARRAY緩沖區。

(7)如果節點收到MYAGENT_RREQ報文，則回復MYAGENT_RREP報文，來報告自身的路由情況。

(8)當節點被判定可以加入到骨干路由樹中，將其在樹中的父節點的信息寫入father緩沖區，判斷該路徑上的最小PA(power Available)，并把MYAGENT_BROAD報文中的rp_hop項加1，繼續向鄰居節點轉發該報文。

(9)所有節點都不停的準備接收各種MYAGENT報文，當不再有MYAGENT報文發送和接收時，骨干路由樹建立過程結束，得到的網絡結構圖如圖2所示。

圖2 網絡結構圖

利用路由樹生成算法建立骨干路由樹，該建樹過程融入了源節點到目標節點的最小跳數算法［15］，骨干節點通過骨干路由樹進行數據傳輸，由此可知，骨干節點傳輸數據時不會出現“折線效應”。

2.3 獨立節點的路由選擇

2.3.1 能量效用選擇函數

如果節點是IN，則要對鄰居節點進行周期性的信息探測［16］來獲得該節點到匯聚節點的下一跳信息，然后在利用選擇函數來選擇更優化合理的下一跳節點。IN進行路徑探測所獲得鄰居節點的信息可能出現四種情況，下面對這四種情況分別討論如下:

(1)如果鄰居節點中包含匯聚節點(如圖3中虛線區域所示)，則不進行選擇函數計算，把匯聚節點作為該節點發送或轉發數據的下一跳節點。因為數據直接傳送給匯聚節點能減少給其他節點帶來的負擔及整個網絡的能量消耗。

圖3 IN的鄰居節點包含Sink節點

(2)如果鄰居節點中既包含骨干節點又包含獨立節點(如圖4虛線區域所示)，則對獨立節點不予考慮，只考慮骨干節點，如果有幾個骨干節點處于同一條路徑上，則只保留到達匯聚節點跳數最少的骨干節點，放棄其他節點。最后選擇的節點都是各條通往匯聚節點路徑上距匯聚節點跳數最少的骨干節點，用Nj表示。

圖4 IN的鄰居節點包含兩類節點

定義4選擇函數P與PAj成正比，與dij和Hj成反比。即獨立節點INi選擇下一跳節點的函數為:

其中，PAj為Nj所在路徑上的最小可用能量，dij為節點INi和Nj的直接通信距離，Hj為骨干節點Nj到匯聚節點的跳數。

該IN可以根據選擇每個骨干節點的函數值和每項的通信代價［17］計算本身到匯聚節點的代價COST(INj)，該代價可用于其他獨立節點選擇下一跳節點時的函數計算。由于網絡中骨干路由樹的覆蓋度較高，因此僅對這些經過一跳到達骨干路由樹的獨立節點進行特殊考慮，其他經過多跳到達骨干路由樹的節點不予考慮。

定義5獨立節點INj的代價為各個下一跳節點到達匯聚節點通信代價的平均值，即

其中，PAj為最小可用能量，dij為直接通信距離，Hj為骨干節點到匯聚節點的跳數。

(3)如果鄰居節點全部是獨立節點(如圖5虛線區域所示)，并且這些獨立節點中含有經過一跳就可到達骨干路由樹的節點，則只對這部分節點(用INj表示)進行考慮，放棄其余獨立節點。這樣可以使數據盡快到達匯聚節點并減少整個網絡的能量消耗。

定義6選擇函數P與Rj成正比，與dij和Cost(Nj)成反比。即INi的選擇函數為:

其中，Rj為獨立節點INj的剩余能量，dij為節點INi和INj的直接通信距離，Cost(Nj)為獨立節點INj到匯聚節點的代價。

圖5 含一跳到達骨干節點的節點

(4)如果鄰居節點全部是獨立節點(如圖6虛線區域所示)，并且這些獨立節點都不能經過一跳到達骨干路由樹，則根據獨立節點INi到獨立節點INj的直接通信距離dij以及獨立節點INj的剩余能量Rj進行選擇函數計算。

定義7獨立節點INi的代價選擇函數為:

其中，RNj為獨立節點INj的剩余能量，dij為直接通信距離，考慮上述決策值在數量級上可能不一致，需要進行歸一化，dmax和Rmax分別為到所有鄰居節點距離的最大值和剩余能量的最大值;t為權重系數。

圖6 不含一跳到達骨干節點的節點

由上述可以看出，鄰居節點距離獨立節點越近，剩余能量越多，其代價函數值越小，從而被選擇為路由節點。該路由選擇策略具有良好的方向性和節點能量均衡性［18］。從而使基于節點剩余能量進行數據傳輸的路由中，能量較多的節點得到充分利用，保護能量較少的節點。

2.3.2 選擇函數的自適應調整策略

針對2.3.1節中第4種情況可能會出現“折線效應”，對選擇函數中的權重系數t引入自適應調整機制，其計算公式為:

其中，n0為網絡第1次建立數據路由的節點跳數;k為“折線效應”判定系數，可取≥1的整數;h為某次數據路由的當前跳數。當h≥kn0時，判定為出現“折線效應”。

在網絡運行初期，路由尚未出現“折線效應”時，權重系數t=t0;而當h≥kn0時，出現“折線效應”，權重系數t的值以指數形式增加，如圖7所示，增加了距離因子在選擇函數P中的重要程度，從而剩余能量較多的節點對路由的吸引力降低，路由的方向性得以改善，“折線效應”開始被抑制;在路由跳數持續增大的情況下，權重系數t會繼續增加并趨于1，逐漸降低“折線效應”。當t=1時，路由協議即退化為純地理信息路由。“折線效應”的消除可以減小路由的延時，降低網絡總能耗。

圖7 權重系數的變化

3 實驗仿真

為了評估本文路由算法的性能，在NS2中分別把GEAR和本文算法進行了仿真。重點通過網絡的吞吐量、死亡節點數以及端到端延遲來進行對比分析，仿真結果表明，CEAR算法能夠達到預期效果。

在仿真環境中，設置網絡范圍為150 m×150 m，網絡節點數為100并隨機分布，匯聚節點處于整個網絡的幾何中心。仿真中采用NS2提供的CMU無線模塊，該模塊實現了傳輸帶寬為1 M的802.11協議，Sink節點的初始能量設置為10 J，發送功率為0.5 W，接收功率為 0.4 W，節點的通信距離為40 m，傳感器節點的初始能量在1 J～6 J間隨機分布。數據包大小為4 000 bit，發送的時間間隔為0.5 s，網絡運行時間為 40 s。網絡參數k=1、t0=0.5。使用gawk腳本對生成的.tr文件進行分析，仿真實驗結果如圖8、9、10、11 所示。

圖8顯示了網絡在相同的時間內發送的數據包數量基本相同。

圖8 發送包數目對比

圖9顯示了網絡中的數據包接收數量，從圖中可見，開始一段時間內，GEAR路由協議算法下的匯聚節點收到的數據包數量要略高于CEAR路由算法。當網絡運行一段時間后，CEAR算法中接收數據包的數量逐漸與GEAR路由協議算法持平，在剩余的大部分時間內，CEAR的匯聚節點收包數明顯高于GEAR路由協議。因為CEAR算法周期性的生成能量閾值保護了低能量節點，并且骨干節點和獨立節點有規則地控制數據傳輸，盡可能的避免了通信中斷，進而使得數據包發送成功率得到較大程度的改善。

圖9 接收包數目對比圖

圖10顯示了網絡中的死亡節點數，從圖中可以看出，網絡運行的前一段時間，CEAR算法中的死亡節點數要明顯低于GEAR路由協議。而網絡運行后期，CEAR路由協議中死亡節點數與GEAR路由協議基本持平，甚至在最后階段超過了GEAR路由協議。因為CEAR算法使用了能量閾值，隨著網絡的運行，低能量節點會逐漸增多，所以死亡節點數會出現增多的現象。另外，CEAR算法Sink節點收包數明顯高于GEAR路由協議，表明網絡運行后期，CEAR算法消耗更多的能量，導致死亡節點數目增多。這從側面反應了CEAR算法處于正常運行狀態的時間要長于GEAR路由協議。

圖10 死亡節點數對比圖

圖11顯示了數據包從源節點到Sink節點的傳輸延時。從圖中可知，CEAR算法端到端的平均時延減小，隨著節點數增加，網絡中的數據流量也會增加，進而造成延時也加大。CEAR算法通過建立骨干路由樹和對部分獨立節點的選擇函數引入自適應調整策略來盡可能的抑制“折線效應”，使源節點和Sink節點之間的路由得到優化，數據包的平均傳輸路徑變短，從而降低了端到端的傳輸時延。

圖11 傳輸數據包延時對比圖

4 總結與展望

本文提出了一種基于能量感知的傳感器網絡節點分類控制路由算法(CEAR)。該算法根據能量閾值周期性地把普通節點分為骨干節點和獨立節點，從而保護低能量節點。骨干節點根據骨干路由樹生成算法建立骨干路由樹，骨干節點按照骨干路由樹進行數據的傳輸，獨立節點根據保存的周圍鄰居節點信息利用能量效用選擇函數選擇下一跳節點進行數據傳輸。對部分選擇函數引入自適應調整策略來消除折線效應，從而減小路由的延時，提高路由的時效性。仿真結果表明，CEAR算法克服了GEAR路由協議算法的缺陷，能夠進一步均衡能耗，降低數據傳輸延時，延長網絡生命周期。

目前，無線傳感器網絡路由算法的研究是非常廣泛的，不少新穎的想法被相繼提出。然而，大多數都還停留在理論研究階段，網絡環境設置相對簡單，與真實的復雜場景相比還有很大差距。本文也只是做了一定的理論設計，算法的現實可行性還要進一步驗證。在本文的基礎上，有很多值得繼續研究和探討的地方:能量閾值不是通過全網節點的能量情況來計算的，如果能夠設計出更優的公式計算出最理想的能量閾值，對于延長網絡生命周期將會具有更加重要的意義;另外本文的仿真實驗方案稍顯簡單，要進一步提高算法的有效性，在后續工作中，最好能夠在一些比較典型的異構網絡中對算法進行模擬實驗。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.A Survey on Wireless Sensor Networks［J］.IEEE Communication Magazine，2009，40(8):102－114.

［2］于海斌，曾鵬，梁群.智能無線傳感器網絡系統［M］.北京:科學出版社，2006:215－278.

［3］李建中，高宏.無線傳感器網絡的研究進展［J］.計算機研究與發展，2008，45(1):1－15.

［4］Hedetniemi S，Liestman A.A Survey of Gossiping and Broadcasting in Communication Networks［J］.Network，2002，18(4):319－349.

［5］Shah R C，Rabaey J M.Energy Aware Routing for low Energy Ad hoc Sensor Networks［C］//Proc.of the IEEE Wireless Communications and Networking Conference.New York，USA:［s.n.］，2006.

［6］Kulik J，Heinzelman W，BalakrishnanH.Negotiation Based Protocolsfor Disseminating Information in Wireless Sensor Networks［J］.Wireless Networks，2009，8(2/3): － .

［7］Sun Yong，lingBo，ZhangZonglin.EnergyEfficientNode Placement Method of Wireless Sensor Networks Based on Uneven Ring Belt Model［J］.Chinese Journal of Sensors and Actuators，2008，19(4):1287－1289.

［8］YOUNIS O，FAHMY S.A Hybrid Energy Efficent Distributed Clustering Approach for Ad_Hoc sensor Networks［J］.IEEE Transcations on Mobile Computing，2004，3(4):660－66.

［9］Karlof C，Wagner D.Secure Routing in Wireless Sensor Networks:Attacks and Mountermeasures.The 1st IEEE Int’1 Workshop on Sensor Network Protocol and Applications，Anchorage，Alaska，2007.

［10］Shan R C，Mabaey J.Energy Aware Routing for Low Energy Ad Hoc Sensor Networks［C］//Wirless Communication and Networking Conf(WCNC 2002)，Florida，USA，2002.

［11］Yu V，Govindan R，Estrin D.Geographical and Energy Aware Routing:a Recursive Data Dissemination Protocol for Wireless Sensor Networks［R］.http://graphics.stanford.edu/courses/cs428－03－spring/papers/reading/Networking/Estringeo－routingo1.pdf，2009－03－15.

［12］張學，陸桑璐，陳貴海.無線傳感器網絡的拓撲控制［J］.軟件學報，2008，18(4):943－954.

［13］KIM M，JEONG E，BANG Y C，et al.Multipath Energy-Aware Routing Protocol in Wireless Sensor Networks［C］//INSS 2008:Proceedings of the 5th International Conference on Networked Sensing Systems.Kanazawa［s.n.］，2008:127－130.

［14］李翔，閻新芳，孫雨耕，等.無線傳感器網絡中簇樹骨干網的構建及算法［J］.傳感技術學報，2006，19(4):1279－1283.

［15］郝曉辰，竇晶晶，劉浩然，等.基于鏈路質量的WSN代價均衡路由選擇算法［J］.電子與信息學報，2010，32(5):1212－1218.

［16］Conti M，Francesco M D，Passarella A，et al.Energy Conservation in Wireless Sensor Networks:A Survey［J］.Ad Hoc Networks，2009，(7):537－568.

［17］劉群，先興平，郭松濤.無線傳感器網絡路由中合作性重復博弈模型的研究［J］.傳感技術學報，2010，23(9):1322－1327.

［18］黃旗明，劉笑.均衡能耗和時延的無線傳感器網絡組內融合機制研究［J］.傳感技術學報，2009，22(1):126－130.