無線傳感器網絡路由算法研究

摘要：傳感器網絡是由一組傳感器以Ad Hoc方式構成的有線或無線網絡，其目的是協作地感知、采集和處理網絡覆蓋的地理區域中感知對象的信息，并發布給觀察者。本文針對無限傳感器網絡的路由技術展開研究，主要從平面路由協議和層次化路由協議兩個方面對無限路由算法做了介紹和分析。

關鍵詞：無線傳感器網絡；路由算法；LEACH協議

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)22-648-02

1 引言

無線傳感器網絡是由一組傳感器以Ad Hoc 方式構成的無線網絡，其目的是協作地感知、采集和處理網絡覆蓋的地理區域中感知對象的信息，并發布給觀察者。在早期的研究中，人們認為ad hoc網協議稍加修改甚至無需修改就可以直接應用于無線傳感器網絡。但是隨著研究的深入，人們逐漸認識到這兩種網絡具有許多不同的特點，傳感器網絡不能簡單借用以往（所謂“傳統的”）ad hoc網的協議。原因如下[1]：

1)傳感器網絡中的節點數量和分布密度遠遠超過以往ad hoc 網絡中的節點數；

2)大部分節點不像ad hoc 節點一樣快速移動；

3)傳感器節點出現故障的可能性要大于ad hoc 網絡；

4)傳感器節點的存儲能力、計算能力和電能有限；

5)傳感器節點主要采用廣播方式通信，而ad hoc 網絡大都采用點對點方式通信；

6)由于數目極大，傳感器節點不一定具有全球唯一的標識.

無線傳感器網絡中路由算法的設計目標是，能夠建立能源有效性路徑，提高路由的容錯能力，形成可靠數據轉發機制，延長最大網絡生命周期，按照現有無線傳感器網絡路由算法實現方法的特點，可以將它們分為平面路由協議和層次化路由協議。

2 平面路由協議

在平面路由協議里面，目前已經有人提出了四種路由算法，下面做一簡單介紹。

2.1 Flooding

泛洪是傳統的路由技術，Flooding 與Gossiping它們是傳感器網絡應用最早最簡單的路由協議，不需要任何路由算法，也不需要維護網絡拓撲結構。在泛洪協議（Flooding）中，節點向它的所有鄰居節點廣播接收到的數據，如此反復，直到數據達到目的節點或者達到數據報的最大跳數。

■

圖1 內爆圖2 重疊

泛洪協議存在的問題是內爆（implosion）和重疊（overlap）。內爆是由于不同節點向同一節點發送相同數據引起的，見圖1；重疊是由于檢測同一區域的節點向相同節點發送數據引起的，見圖2。針對泛洪的內爆問題，S.Hedetniemi[2]等人提出了Gossiping 協議，節點隨機選擇一個鄰居節點轉發分組，而不是向所有鄰居節點轉發數據。但是協議增加了端到端的數據傳輸延遲。

2.2 SPIN（Sensor Protocol for Information via Negotiation）

SPIN 是以數據為中心的自適應路由協議，通過協商機制來解決泛洪算法中的“內爆”和“重疊”問題。傳感器節點僅廣播采集數據的描述信息，當有相應的請求時，才有目的地發送數據信息。由于元數據大小小于采集的數據，所以傳輸元數據消耗的能量相對也較少。

SPIN 協議中有3 種類型的消息，即ADV、REQ 和DATA。節點用ADV 宣布有數據發送， REQ 請求表示希望接收數據，用DATA 封裝數據。SPIN 協議的擴展性差；功耗在所有節點之間分布不均衡，sink 節點附近的節點首先耗盡電能。為避免盲目使用資源，所有傳感器節點必須監控各自的能量變化情況。

2.3 SAR（Sequential Assignment Routing）

在選擇路徑時，有序分配路由（SAR）策略充分考慮了功耗、QoS和分組優先權等特殊要求，采用局部路徑恢復和多路徑備份策略，避免節點或鏈路失敗時進行路由重計算的開銷。為了在每個節點與sink（網關）節點間生成多條路經，需要維護多個樹結構，每個樹以落在sink（網關）節點有效傳輸半徑內的節點為根向外生長，枝干的選擇需滿足一定QoS要求并要有一定的能量儲備。這一處理使大多數傳感器節點可能同時屬于多個樹，可任選其一將采集數據回傳到sink（網關）節點。

2.4 定向擴散（Directed Diffusion）

定向擴散模型[3]是Estrin 等人專門為傳感器網絡設計的路由策略，與已有的路由算法有著截然不同的實現機制。節點用一組屬性值來命名它所生成的數據，比如將溫度傳感器生成的數據命名為Type=temperature，id=12，timestamp=02.01.22/21：10：23，location=305。Sink節點發出的查詢業務也用屬性的組合表示，逐級擴散，最終遍歷全網，找到所有匹配的原始數據。

有一個稱為“梯度”的變量與整個業務請求的擴散過程相聯系，反映了網絡中間節點對匹配請求條件的數據源的近似判斷。更直接的方法是節點用一組標量值表示它的選擇，值越大意味著向該方向繼續搜索獲得匹配數據的可能性越大。這樣的處理最終將會在整個網絡中為sink節點的請求建立一個臨時的“梯度”場。匹配數據可以沿“梯度”最大的方向中繼回sink（網關）節點。

3 層次化路由協議

層次化路由協議將所有的節點分為若干簇，每個簇選舉一個首領。由首領實現數據融合，達到節約功耗的目的。簇的劃分依據是節點現有的電量和它與首領的距離。LEACH是最早提出的層次化協議，在它的基礎之上又衍生出了許多類似協議。TEEN是另一種典型的層次化路由協議。

3.1 LEACH（Low Energy Adaptive Clustering Hierarchy）

LEACH[4]協議是由MIT 的Heinzelman 等人提出的。協議將所有節點分為若干簇，每個簇選舉一個首領，簇首領還可以組成更高層次的簇。簇首領接收本簇中節點發送的數據，實現數據融合功能，并向基站發送數據。由于向基站發送數據要消耗很大的電能，每隔一段時間需要重新選舉首領，以保證功耗在所有節點的平均分配。該協議具有兩個運行階段：簇建立階段和穩定運行階段。為減少協議開銷，穩定運行階段的持續時間要長于簇建立階段。

在簇建立階段，將所有節點劃分為若干簇，每個簇選舉一個首領。每個節點選取一個介于0 和1 之間的隨機數。如果這個數大于門限值T（n），該節點成為簇首領。門限值計算方法如下：

■

其中p 是首領節點占全部節點的百分數；r 是現在的輪次；G 是在最近1/p 輪沒有成為首領的節點集合。選舉結束之后，新當選的首領節點向所有節點廣播自己成為首領的消息。根據收到廣播信號的強弱，每個節點決定加入哪個簇，并答復該簇的首領。

在穩定運行階段，簇中的所有節點按照時分復用的方式向首領發送數據。每個節點發送一遍數據所用的時間稱為幀時間。在持續工作一段時間之后，網絡進入下一輪工作周期，重新劃分簇并選舉首領。

總之，LEACH是低功耗自適應聚類路由算法，主要通過隨機選擇聚類首領，平均分擔中繼通信業務來實現。LEACH協議分為兩個階段，即類準備階段和就緒階段。在類準備階段，LEACH協議隨機選擇一個傳感器節點作為頭節點，頭節點與其附近的節點構成簇，頭節點成為簇首領。為了防止某個節點長期作為頭節點而能量過量損耗，將會利用選舉算法使得每個節點都有成為頭節點的機會，頭節點負責簇內部和各個簇之間的通信。

3.2 TEEN（Threshold Sensitive Energy Efficient Sensor Network）

TEEN[5]協議對LEACH 協議進行了改進，定義了硬、軟兩個門限值，只有在同時滿足兩個門限值時節點才發送數據。軟門限的初值為0，當監測數據第一次超過設定的硬門限時，節點用它作為新的硬門限，并在接著到來的時隙內發送它。在接下來的過程中，如果監測數據的變化幅度大于軟門限界定的范圍，則節點傳送最新采集的數據，并將它設定為新的硬門限。通過調節軟門限值的大小，可以在監測精度和系統能耗之間取得合理的平衡。

4 結束語

傳感器網絡具有廣闊的應用前景，將是未來社會應用最廣的網絡，通過近幾年的研究，人們對傳感器網絡固有特點的認識已經逐漸明確，并在相關技術方面取得了一些進展。但是，傳感器網絡要真正實用化，在路由技術上還有許多基礎性問題和關鍵技術需要解決，比如，針對較大規模的無線傳感器網絡應用，路由的容錯能力的提高等。

參考文獻：

[1] Intanagonwiwat C.， Govindan R.， D.EstrinD. \"Directed Diffusion:A Scalable and Robust Communication Paradigm for Sensor Networks，\" ACM MobiCOM，2000.

[2] Parkka K J. and Vangils M.，\"Health monitoring in the home of the future\"，IEEE Engineering in Medicine and Biology Magazine May 66-73 2003.

[3]Knaian N.\"A wireless sensor network for smart roadbeds and intelligent transportation systems\" MSc thesis， MIT 2000.

[4] Warneke B， Last M，Liebowitz B，Pister KSJ. Smart dust:Communicating with a cubic-millimeter computer.IEEE Computer Magazine，2001，34(1):44-51.

[5] Estrin D，Govindan R，Heidemann J，Kumar S. Next century challenges: Scalable coordinate in sensor network.In:Proceedings of the 5th ACM/IEEE International Conference on Mobile Computing and Networking. Seattle： IEEE Computer Society，1999:263-270.