無線傳感器網絡基于樹的能量有效路由協議

摘要：能量有效性是無線傳感器網絡需要考慮的一個重要問題。針對無線傳感器網的能量有效路由問題，提出了基于樹的能量有效路由協議（TEERP），TEERP同時考慮了路徑的能量消耗最小化以及網絡的能量均衡性能。該協議具有能量有效性以及簡單性的優點。利用NS2，對其進行了性能仿真。

關鍵詞：無線傳感器網絡； 能量有效性； 樹

中圖法分類號：TP393文獻標識碼：A

文章編號：1001－3695(2007)01－0294－03

1引言

無線傳感器網絡以其獲取信息精度高、部署靈活性強、可靠性高、經濟性好等特點，在軍事偵察、環境監測、工業控制與監視、智能建筑、交通運輸以及其他商業領域具有非常廣闊的應用前景[1]。無線傳感器網中，由于傳感器節點依靠電池供電，能量有效性是需要考慮的一個重要問題。文獻[2]給出了能量有效性的五種度量指標，這其實是從兩方面考慮能量有效性的：尋找一條總體最節能的路由；盡量保證各個節點剩余能量均衡。許多路由協議都是基于這兩個基本準則來提高路由協議的能量有效性[3~5] 的。

SPIN[3]是洪泛的一種改進，在回傳數據時，假設所有節點都是目的節點。SPIN適用于傳感器網中的數據回傳，并且節點一次傳送的數據量比較大的情況，只有這樣，協商一次才具有更大的價值。SPIN實現能量有效性的方法是只有當節點的能量足夠大時，才進行分組的轉發。但是傳感器網絡的目的節點只有一個Sink節點，因此，這樣做的能量開銷還是非常大的。

定向擴散[4]屬于反應式路由協議，是以數據為中心的路由的典型范例。節點不需要全局ID，代價就是由Sink把查詢請求在全網洪泛，數據又沿著洪泛建立的梯度返回，帶來了比較大的能量開銷。

LEACH[5]是傳感器網中比較經典的分群路由協議之一，設計了“普通節點—群首—Sink”的數據傳輸模式，并給出了由群首實現數據聚合的思想。LEACH考慮能量有效性的方式是節點輪換著擔當群首，從而實現能量均衡消耗。但是，LEACH假設所有節點一跳可達Sink，限制了傳感器網絡的規模。而且隨著網絡規模的擴大，LEACH中假設的全網同步也會變得十分困難甚至難以實現。

本文針對無線傳感器網的能量有效性問題，提出了基于樹的能量有效路由協議（Treebased Energy Efficient Routing Protocol，TEERP）。由Sink發送請求，建立所有節點到Sink的路徑，考慮了最小能量路徑以及能量的均衡消耗。相比于SPIN，數據不是在全網洪泛，而是建立源到目的的路徑，當網絡的業務量比較大時，節省了能量。相比于定向擴散，不是節點發送查詢反應式建立源到目的的路徑，而是由所有節點先應式維護到Sink的路徑，這非常適合于無線傳感器網絡的周期報告以及事件觸發業務。相比于LEACH，沒有采用群首實現數據聚合，而是由樹杈上的節點完成數據聚合，即樹結構相當于建立了一種網絡結構，而這樣的網絡結構非常便于實現數據聚合。再者，傳感器節點的處理能力以及計算能力有限，TEERP對節點的處理、計算以及存儲能力都要求很低，是實現路由的一種簡單、有效的方式。

2TEERP詳細描述

在TEERP中，考慮節點的能量有效性，這主要從兩方面來實現：①選擇最少跳數路徑，這對于功率不可調整的網絡，相當于選擇了最小能量路徑；②盡量讓剩余能量多的節點完成分組轉發功能，以提高網絡的能量均衡性能。

2．1TEERP的路徑建立

樹的建立由Sink節點開始。Sink節點廣播RREQ消息，RREQ中攜帶廣播ID、自己距離Sink的跳數、節點的能量以及TTL。節點在接收到第一個RREQ時設置定時器，在定時器超時時間內，比較新收到的RREQ與當前緩存記錄，如果新的RREQ距離Sink的跳數小于當前的記錄，則根據新的RREQ更新緩存中的記錄；如果跳數相等，則比較發送RREQ節點的能量，如果能量大于當前緩存記錄的能量，則根據新的RREQ更新緩存中的記錄，否則丟棄RREQ。在定時器超時后，認為選擇出最佳的父節點。然后，根據緩存中的記錄，向父節點發送RREP消息，父節點收到RREP消息后，將其加入自己的子節點列表，并向其回復ACK消息，該節點收到ACK消息后，把其列為當前父節點。這樣，一直到全網所有的節點，建立全網的樹，如圖1所示。

RREQ消息中的TTL可以限制RREQ傳播的范圍。對于有多個Sink的傳感器網，TTL可以保證傳感器節點盡量加入距離自己更近的Sink為根節點的樹，限制RREQ的傳播范圍，節省網絡的能量消耗。另外，在建立樹時，沒有建立備份路由，以降低算法的復雜度，并節省存儲空間。

2．2TEERP的路徑維護

當某個節點的父節點失效時，需要對樹進行維護。樹的維護采用周期維護和事件觸發維護兩種方式。周期維護由Sink節點發起，與樹建立過程相同。

節點在一段時間內沒有收到父節點的Hello消息，則認為父節點失效，此時可對樹進行事件觸發的維護。節點一旦發現當前的父子關系斷裂，則在鄰居節點范圍內發送路由維護消息，然后設置定時器，在定時器超時時間內選擇一個最優的父節點，這與節點接收到RREQ消息后選擇最優父節點的方法相同。定時器超時，則認為選擇出最佳的父節點，然后向新的父節點發送要求確認消息。節點收到該消息后，向其發送確認消息，建立兩者之間的父子關系。

2．3TEERP的環路避免

事件觸發維護時有可能會出現環路。節點發現自己的父節點失效后，需要在鄰居節點中找到一個最優的節點作為該節點的父。較好的情況是：節點3發現自己的父節點1不存在了，則廣播一個一跳的路由維護消息，此時，接收到該消息的鄰居節點向節點3發送一個應答，節點3在延遲一段時間后，選擇節點2作為自己的新父節點，并向其發送要求確認消息，待節點3收到來自節點2的確認后修改路由表，將父節點域改為節點2，修復了節點3到Sink的路徑，如圖2所示。

在比較惡劣的情況下，只有節點的子節點才有可能成為該節點的下一跳節點，即父子關系反向，這樣就形成環路，如圖3所示。節點3發送路由維護消息，等待一段時間后，只有自己原先的子節點4向其作出應答，此時節點3選擇自己的子節點4作為新父節點，并向其發送要求確認的消息，節點4接收到該消息后，發現形成環路，修改路由表，置其為空或者無效，但不向節點3發送確認消息。然后，節點4在自己的一跳范圍內廣播路由維護消息，完成與節點3同樣的找路過程。如果找到一個非子節點作為節點4的新父節點，節點4向節點3發送確認消息，節點3收到該確認消息后，修改路由表，父節點域修改為節點4。節點3只有收到自己選擇的父節點的確認，才修改路由表。節點3在足夠長的時間內沒有收到確認，則認為該節點為游離節點，沒有到達Sink節點的路徑。

3仿真結果和性能分析

我們采用NS2分析TEERP的性能。網絡中有50個節點，分布在100m×100m的范圍內，節點的通信范圍為20m，每個節點的初始能量為10。網絡中只有一個Sink節點，位于網絡中的任意位置，Sink節點的初始能量配置為50J。在仿真中，設發送功率為0.050 208W，接收功率為0.05W，偵聽功率為0．045W。所有節點在仿真的整個過程中處于靜止態。業務為CBR業務，分組大小為512Bytes。

圖4和圖5分別是分組遞交率和開銷隨著樹維護周期的變化曲線圖。在仿真時，仿真時間為100s，選擇父的延遲系數設為0.006 7，Hello間隔取值為2.75s～3.75s之間的隨機值。從圖4可以看出，隨著周期維護樹時間間隔的增大，分組遞交率不斷減小。當樹維護周期為15s時，分組遞交率可以達到93％。當整個網絡運行時間內只建立一次樹，而不作周期維護時，分組遞交率只能達到20%。從圖5可以看出，維護樹的周期越大，控制分組的開銷就越小。當樹維護周期為15s時，控制開銷降低到一定程度，即使樹維護周期變大，控制開銷也不再減小。從圖4和圖5可以看出，當樹維護間隔為15s時，分組遞交率和開銷達到最好的效果。

為了保證節點之間的連通性，節點之間必須不斷地發送Hello消息，這樣做的原因是：盡早發現失效父節點，及時恢復失效的路徑。圖6和圖7分別是樹維護間隔為15s時，分組遞交率以及控制開銷隨著Hello發送間隔的變化曲線圖。仿真中樹維護間隔的取值為15s。曲線橫坐標的第一個值表示Hello間隔為1.75s～2.75s之間的值，后面的值依此類推。從圖6和圖7可以看出，分組遞交率以及開銷均隨著Hello間隔的增大而減小?？梢钥闯?，Hello間隔時間為2.75s～3.75s時，分組遞交率以及控制開銷達到比較優化的組合。 

圖8是選擇父節點時延與分組端到端時延之間的關系曲線圖。圖8的節點間Hello間隔設為2.75s~3.75s，節點樹維護周期設為15s。從圖中可以看出，在選擇父的延遲為0，即在收到第一個RREQ消息就選擇其為父節點，則分組的端到端延遲比較大，隨著選擇父時延的增加，端到端時延會逐漸減小；當選擇父的延遲的系數大于0.0-04s時，則分組的端到端延遲又開始增大。這是因為在選擇父節點的延遲為0時，選擇的路徑是非最優路徑，路徑的跳數比較大。此時分組的端到端延遲比較大。隨著延遲的增大，選擇了比較好的路徑，分組的端到端延遲減小，但是如果選擇父的延遲繼續增大，則路徑建立的延遲增大，節點會使用一些舊的路徑，或進行路徑的修復，從而將增大分組的端到端延遲。

圖9是選擇父延遲與網絡能量均衡性能之間的關系曲線圖。從圖中可以看出，選擇收到的第一個RREQ的節點作為父節點，網絡的能量均衡性能比較差。隨著選擇父延遲的增大，能量均衡性能逐漸變好；當延遲繼續增大時，網絡的能量均衡性能逐漸變差。這是因為，選擇第一個節點作為父節點，選擇的并不是最優路徑，有可能該節點的能量即將耗盡，使得網絡的能量均衡性能變差。隨著延遲的增大，選擇了比較好的節點作為父節點，網絡的能量均衡性能達到最優。此后隨著選擇父延遲的增大，有可能節點有數據要發送時，還是選擇了以前的舊路徑，使用了能量已經很少的節點，導致網絡的能量均衡性能變差。綜合圖8和圖9可以看出，當α×D0=0．001s時，分組的端到端延遲以及網絡的能量均衡性能達到最優。

4結束語

本文給出了無線傳感器網絡基于樹的能量有效路由協議，而休眠是節省能量的最有效的方式。在該路由協議中并沒有考慮節點的休眠調度，下一步工作中，需要考慮如何調度節點，以更好地延長網絡的工作時間。另外，傳感器網的覆蓋是需要研究的另一個重要方面，如何在保證覆蓋的前提條件下，最優地調度節點，并保證網絡的連通性以建立能量有效的路由是需要研究的一個重要問題[6，7]。

附：TEERP路徑建立算法

Begin

For every intermediate node A do

1. Ifthe timer expires

2.A sends RREP to parent cluster;

3.A broadcasts RREQ again;

4. When A receives RREQ

5. Ifthe timer has expired

6. A drops it;

7.Else ifit is the first received RREQ

8.A starts a timer and places RREQ in the cache;

9.Else

10. A compares sequence number of this new RREQ with the record in the cache

11.Ifnew sequence number is larger than the old one

12.A replaces the old record with this new RREQ;

13.Iftheir sequence number is equal， A compares hops to Sink

14.Ifnew hops is smaller than the old one

15.A replaces the old record with this new RREQ;

16.Iftheir hops are equal， A compare energy of node

17.Ifnew energy is larger than the old one

18.A replaces the old record with this new RREQ;

End

參考文獻：

［1］任豐原， 黃海寧， 林闖．無線傳感器網絡[J]．軟件學報， 2003， 14(7): 12821291．

［2］Singh S， Woo M， Raghavendra C．PowerAware Routing in Mobile Ad hoc Networks[C]．New York: ACM Press， 1998．181190．

［3］J Kulik， W Heinzelman， H Balakrishnan．Negotiationbased Protocols for Disseminating Information in Wireless Sensor Networks[J]． Wireless Networks， 2002， 8(2): 169185．

［4］Chalermek Intanagonwiwat， Ramesh Govindan， Deborah Estrin. Directed Dffusion: A Scalable and Robust Communication Paradigm for Sensor Networks[C]．New York: ACM Press， 2000．5667．

［5］W Heinzelman， A Chandrakasan， H Balakrishnan．An ApplicationSpecific Protocol Architecture for Wireless Microsensor Networks[J]．IEEE Transactions on Wireless Communications， 2002， 1(4): 660670．

［6］F Ye， G Zhong， S Lu，et al.Peas: A Robust Energy Conserving Protocol for Longlived Sensor Networks[C]．Washington， DC: IEEE Computer Society， 2003．2837．

［7］D Tian， N D Georganas．A Coveragepreserving Node Scheduling Scheme for Large Wireless Sensor Networks[C]．New York: ACM Press， 2002．3241．

作者簡介：

劉湘雯（1977），女，陜西華縣人，博士研究生，研究方向為無線網絡路由；

侯惠峰（1977），男，河北衡水人，博士研究生，研究方向為無線網絡路由；

胡捍英（1961），男，河南南陽人，教授，博導，國家重大科技攻關項目“中國第三代移動通信系統研究開發項目”總體專家組成員。

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