無線傳感網絡中的路由選擇及優化研究

李飛，李登

(91497部隊，浙江寧波315122)

1 前言

無線傳感網絡通常是由分布廣泛的大量傳感器組成的，這些傳感器具備動態感知、無線傳輸通信功能，并且具備一定的計算能力。無線傳感器在將感知到的數據通過無線網絡傳輸到處理節點后，就可以組成物聯網絡，并且具有可擴展、自組織、強穩定性的優勢，能夠應用到社會領域的各個方面。

我國在無線傳感網絡方面的研究起步較晚，但是國家對科技領域的重視使得國家自然基金會在21世紀初將無線傳感網絡列為重點資助項目和重大研究課題，因此國內各大高校、研究機構也紛紛展開了對無線傳感網絡的研究。

無線傳感器的體積極小，因此通常用電池供電，有限的電池容量是無線傳感節點長時間使用的最大制約。為了保證無線傳感網絡的長時間及大規模應用，就需要優化無線網絡數據傳輸時的路由選擇，以降低無線傳感器的能量消耗，提高能量利用率、延長無線網絡壽命。

2 無線傳感網絡路由協議

無線傳感路由協議的目的是實現無線傳輸網絡中數據的轉發及路由選擇，從而為數據從采集段的無線傳感器傳輸到目的節點尋找一條最優路徑。由于無線傳感器一般由電池供電，其電量、計算及存儲能力的有限性決定了在設計無線傳感網絡路由協議時需要注意一些問題[1]：

1)能量消耗低且高效。無線傳感節點尤其是關鍵路徑上的傳感節點的電量耗盡，會導致整個無線傳感網絡出現傳輸故障，嚴重的甚至可能會引起網絡癱瘓；無線傳感網絡間通信時，能耗與傳輸距離有重要的關聯，因此設計無線傳感路由時需要權衡節點的能耗，以盡量延長無線傳感網絡的生命周期。

另外，還要從全局考慮整個無線傳感網絡的能量均衡，既不能出現“能量消耗熱點”，又盡可能避免“能量閑置”，充分提高整個無線傳感網絡中所有節點的效率。

2)無線傳感網絡的穩定可靠性。在傳感網絡中的某個節點出現能量耗盡等問題時，不會影響整個網絡的通信，無線傳感網絡的路由選擇需要能夠自適應網絡結構的拓撲變換。

3)服務質量。路由選擇以數據傳輸為中心，無線路由協議的主要目的是實現傳感數據的傳輸，而無線傳感網絡結構是會頻繁出現變化的，所以并不需要了解數據的采集節點，只需將其傳輸、轉發出去即可。服務質量要求在提供準確、全面的無線傳感信息的同時，關注無線傳感網絡的使用壽命。

根據無線傳感網絡的拓撲結構，可以將無線傳感路由協議分為兩大類：平面路由協議及分簇路由協議。在使用平面路由協議的無線傳感網絡中，每個網絡節點的地位和權限是相同的，并不存在管理節點，數據采集及傳輸是所有節點共同協作完成的，因此平面路由協議的優點是網絡結構簡單、網絡擴展方便。然而，在大規模的無線傳感網絡中，隨著路由跳數的增加，路由選擇及數據轉發的開銷成本也會顯著增加。一個典型的平面路由協議網絡拓撲如圖1所示：

圖1 平面路由協議網絡拓撲

采用分簇路由協議的無線路由網絡中，各個節點的地位有所不同[2]：無線傳感網絡會以簇為單位進行劃分，每個簇中包含一個簇頭(cluster head)節點，其余的為普通節點。普通傳感節點在采集到數據后會將其傳輸給簇頭節點，簇頭節點匯總本簇內所有節點采集到的數據，并將其一起傳輸到無線傳感基站。簇頭傳感節點的存儲、計算能力可以比普通節點的高一些，以完成所有數據的匯總工作。和采用平面路由協議的無線傳感網絡相比，采用分簇路由協議后，普通網絡節點的能量可以得到充分利用，有效延長了無線傳感網絡的生命周期。分簇路由協議的網絡拓撲如圖2所示。

圖2 分簇路由協議網絡拓撲

雖然采用分簇路由協議的無線傳感網絡比平面路由協議更有優勢，但在實際應用中還存在一定的不足[3]：1)組建無線傳感網絡初期難以確定簇大小。傳統的分簇路由協議是將無線傳感網絡中的所有節點平均分為若干簇，每個簇內的節點數目相同。這種均勻分簇方法可以均衡網絡內所有節點的能量負載，但是對于大型無線傳感網絡中的傳感節點隨機分布現象并不適用。為此無線傳感網絡節點組成的集群就不能固定化，而是根據網絡內節點分布情況以及能量使用來動態變化。2)簇頭選擇問題。無線傳感網絡中的簇頭(cluster head)節點會比普通節點存在能多能耗，因此在簇頭節點出現問題后，隨機選擇一個普通節點可能會有繼發問題。另外，分簇時僅采用能量指標存在單一性缺陷，需要綜合考慮多種指標，并合理分配不同指標的權重。3)局部最優解問題。無線傳感網絡節點的分布結構可能會導致路由算法陷入局部最優解。

3 分簇算法優化

對于采用分簇路由協議的無線傳感網絡，其分簇方式、簇大小、簇頭選擇等問題是限制分簇路由效率及精度的重要因素。

3.1 簇頭選擇方法

無線傳感節點在部署后，每個節點都可以確定自己的物理位置。無線傳感基站(Base Station，BS)會周期性地向所有節點廣播基站id 和基站的位置信息。無線傳感網絡內的節點在收到基站的廣播信息后，會存儲基站id 和基站位置信息，并計算節點到基站的距離Dist，節點距離基站越近，就越有可能成為“能量熱點”，同時也具備越強的競爭簇頭的能力[4]。

可以使用無線傳感網絡中的節點剩余能量及到基站的距離Dist兩個參數來計算不同節點競爭簇頭的優先級，并用模糊映射規則處理簇頭競爭的不確定性。

在計算無線傳感節點競爭簇頭能力，需要使用兩個模糊輸入變量：節點剩余能量、節點到基站的距離；經過模糊計算后就可以得到無限傳感節點的競爭簇頭能力。假如某傳感節點距離基站最近，并且其剩余的能量還最多，則認為此節點競爭簇頭的能力最強，反之亦然。這種簇頭選擇方法如圖3所示。

圖3 簇頭選擇方法

3.2 簇半徑計算方法

簇大小的選擇會直接影響無線傳感網絡的壽命，在決定簇大小時需要考慮的因素包括[4]：1)網絡中節點的分布密度。如果節點密度較大，則應該減小簇的半徑以降低簇頭節點的負載，反之則需要適當增加簇半徑。2)網絡中節點分布的離散程度。無線傳感網絡中非簇頭節點向簇頭節點傳輸數據時的能耗與到簇頭節點的距離成正比，因此如果節點分布相對離散，則傳輸到簇頭節點就需要更大的能耗，此時就需要適當減小簇半徑，反之則可以適當增加簇半徑。3)節點的剩余能量。簇頭節點的剩余能量越多，則可以選擇越大的簇半徑；隨著網絡使用時間的延長及節點能量的逐漸消耗，可以適當減少簇半徑。

考慮到上述因素，在計算簇半徑時可以根據無線傳感網絡中節點的信息來綜合權衡。首先，由節點i 自身的地理位置Li計算核函數KH(l-Li)，并和節點到基站的距離Dist、節點的能量一起反映節點的離散程度，以此進行核密度估計。然后，為避免計算全局條件下所有節點的累加值，可以只估計節點i 的K階近鄰，以此降低計算復雜度，得到節點i的局部帶寬估計。最后，進行自適應帶寬估計。不同節點的鄰居節點分布情況是有所不同的，為此基站在發送廣播信息時可以向所有節點同時發送一個最小簇半徑和最大簇半徑參數，每個節點根據鄰居節點的分布情況，在最小簇半徑和最大簇半徑參數之間選擇合適的簇半徑即可。

4 路由算法優化

4.1 簇間路由算法優化

蟻群算法是一種分布式尋找最優路徑的算法，在無線傳感網絡的路由選擇中有廣泛應用[5]。算法初期，所有螞蟻各自選擇無規則的路線，并在其訪問路徑上留下信息素。將蟻群算法應用到無線傳感網絡的路由選擇時，為了確保路由選擇算法在開始階段可以搜索到盡可能多的傳輸路徑，需要對無線傳感網絡的初始狀態路徑信息素進行修改。

對于無線傳感網絡中的所有節點，引入信息素揮發機制：信息素在一次完整訪問路徑完成后進行更新操作，更新的計算公式為：

其 中ρ是恢復率，(1 -ρ)*τij(t) 是 信息素的揮發過程，Δτij(t)是信息素的增加機制，即路由選擇過程中尋找路徑時經過某路徑所遺留的信息素增量。

信息素在經過若干次的迭代后將得到一個收斂值，根據此收斂值即為簇間初始化信息素濃度最大的值，也就是當前簇選擇的下一個簇，這樣就實現了簇間的路由選擇。

簇間路由選擇過程中，經過的每個網絡節點需要更新其鄰接表，對于多跳路由的無線傳感網絡，還需要根據簇頭節點到基站的距離對簇頭節點進行劃分，并根據簇頭節點的層級更新鄰接表：1)只能選擇比當前層級低的層級上的簇頭，只有低一層級上沒有簇頭節點時，才擴大簇半徑。2)預先設定一個閾值CR，鄰接節點的搜索范圍固定在CR到2CR之間。

4.2 分簇路由算法優化

在進行簇的劃分時，需要根據分簇路由算法選擇劃分的簇中的節點。

在剛建立簇的初期，已經根據前文介紹的簇半徑選擇方法和簇頭選擇方法選擇除了簇頭，并確定了簇半徑。網絡內的普通節點收到簇頭的廣播消息后，就可以知道本簇內已經確定好簇頭，因此放棄競選簇頭，并向簇頭發送申請加入簇的消息。如果普通節點收到多個簇頭發來的廣播消息，則選擇距其近的節點作為簇頭。

隨著簇頭在一個方向上不斷加入普通節點，當距離簇頭的距離達到簇半徑時，就虛構更改簇內的路由選擇方向。此時需要根據舉報信息素的累積增量設計轉移概率公式，并從鄰接表中選擇下一方向上的普通節點。這樣在一個分簇內進行路由選擇時，先在一個方向上不斷加入普通節點，方向距離到達簇半徑后再改變路由選擇方向的方式，可以有效降低無效路由帶來的能量損失。路由選擇輪數與無效傳感網絡的平均剩余能量的關系如圖4所示。

圖4 路由選擇優化效果

5 總結

本文對無線傳感網絡中的路由選擇及優化進行研究。首先，本文介紹了無線傳感網絡的路由協議；接下來本文從簇頭選擇、簇半徑計算等方面對分簇算法進行了優化；最后，本文對簇間及分簇內的路由選擇進行了優化。優化結果表明，隨著路由選擇迭代次數的增加，優化后的無線傳感網絡平均剩余能量得以有效分布。