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

丁海霞

(江蘇食品職業技術學院 計算機應用技術系，江蘇 淮安 223003)

無線傳感器網絡WSN(Wireless Sensor Network)作為新興的網絡測控技術，是能夠自主實現數據采集、融合和傳輸的智能網絡系統，在軍事、交通、數字醫療等領域得到了廣泛應用，因而引起了業界的廣泛關注。但是由于WSN節點受到體積和成本等方面的限制，一般采用攜帶的電池，能量補充困難而且能量相對較少，這是目前WSN應用的主要問題。因此，如何降低能耗，提高整個網絡的生命周期是WSN的研究熱點，也是亟待解決的問題。

目前，國內外大量學者針對如何降低和平衡節點能耗問題進行了研究，本文針對WSN路由節能問題進行研究。在WSN中，由于節點特殊原因或節點能量受限等因素影響，個別節點失效或不能工作狀況時有發生。當出現節點失效等情況后，需要有新的節點及時移動到失效節點的位置，取代失效節點繼續工作。在這個取代的過程中，節點移動有許多要解決的難題。首先，節點移動有嚴格的時間要求。當舊節點剩余能量低于閾值時，新節點必須在規定的時間內移動到舊節點位置，并且越快越好，從而保證在舊節點失效之前，新節點能夠接替其工作。這樣才不會影響WSN正常運行，也不會出現盲區或某一時間無法監測的區域。其次，節點移動不能影響網絡的正常工作，因為在節點移動的過程中，節點要與周圍節點交換信息，甚至可能影響節點的中繼路由或簇的形成。第三，由于傳感器節點的能量有限，節點移動的消耗能量應盡可能少，節約傳感器節點能源，從而延長整個傳感器網絡的有效工作時間。針對這些問題，本文在總結和應用其他學者研究成果的基礎上，提出了一種基于節點最佳路徑移動的無線傳感器網絡節能路由算法EEBM (Energy-Efficient routing algorithm based on the Best node Movement route)。

1 相關研究

1.1 分層型路由協議

分層型路由協議中，能量較高節點可用于處理和傳遞信息，而能量較低的節點則只能用于對目標進行近似測量。典型的分層型路由協議主要包括：

(1)低能耗自適應分簇LEACH(Low Energy Adaptive Clustering Hierarchy)算法，它是一種自適應型分簇拓撲算法，通過讓各節點等概率的擔任簇頭達到相對均衡網絡中各節點所消耗的能量的目的。LEACH是一種以最小化傳感器網絡能量損耗為目標的分層式協議，它集成了傳感器網絡的基本路由協議和拓撲控制算法。在LEACH算法中整個網絡的通信由一輪一輪的周期性動作組成，每一輪包括簇的建立階段和數據通信階段，其中簇的建立階段完成簇的組織，數據傳輸階段將數據傳送到簇首，再由簇首發送到基站(BS)。

(2)傳感器信息系統的節能型采集方法PEGAS-IS[1]，它是一種臨近最優鏈式協議，其基本思想是：借鑒LEACH的動態簇頭選舉思想[2]，建立一條包含所有節點的最短路徑(稱為“鏈”)，并最終在每輪中只選出一個簇頭負責與網關節點通信。由于最短路徑鏈上的節點都能以最小發射功率向鄰居節點發送數據，相比于LEACH，PEGAS-IS使網絡的生存時間得到顯著延長。但是，由于目前還沒有尋找包含所有節點的最短路徑的有效方法，PEGAS-IS不適合在大規模網絡上使用。

1.2 平面型路由協議

在平面型路由中，所有節點的地位平等，典型協議主要有：

(1)序列分配路由 SAR[3]，其基本原理是：選擇路由時，綜合考慮能量資源、各路徑的服務質量(QoS)和各信息包的優先權3個要素，根據最終的權值來決定當前的路由。若由于節點故障拓撲邏輯產生變化，則需要重新計算路由。其中，基站負責計算拓撲邏輯變化的總量，并周期性觸發路徑重新計算。同時，還采用鄰近節點間基于局部路徑重建的交換方式恢復路徑。

(2)最小開銷前向傳遞算法 MCFA[4]，其基本原理是：利用路由傳遞方向的己知信息(例如向外部固定基站傳遞數據)對數據進行路由。無線傳感器節點前向傳遞的每條信息都被發送到相鄰節點中。當節點接收到該信息時，檢查自己是否處于源節點與基站間最小花費路徑上。如果是，則再將信息傳遞給相鄰節點。不斷重復該過程，直至該信息被傳遞到基站中。在MCFA中，各節點需要了解從本節點到基站間的預計最小花費路徑，節點無需包含特有ID或維護路由表。另外，各節點也不斷修正自己到基站的最低花費值。

1.3 適應型路由

信息協商傳感器協議(SPIN)[5]是適應型路由的典型協議，可通過控制特定的系統參數以適應網絡當前條件和可用的能量水平。

通過對典型節能路由模型的研究可以看出，針對WSN能耗的研究主要集中在路由和網絡的建立、節點分簇、簇頭選取、輪詢策略等方面，而通過策略選取節點，將其移動到指定區域來取代失效節點，完成類似移動Internet或3G/4G的移動服務等方面的研究還相對較少。

2 基于節點最佳路徑移動的WSN節能路由算法EEBM

2.1 基本思想

EEBM主要研究當“瓶頸節點”即將發生失效等情況時，如何在滿足節約節點移動消耗能量等多條件約束情況下，找到最佳的移動節點(優先考慮移動獨立冗余節點)和移動路徑，從而保證網絡的正常工作，延長網絡的有效工作時間的方法。

算法的主要思想如下：

(1)網絡中獨立冗余節點的選取策略。所謂獨立冗余節點，即若關閉該節點，不會影響網絡的覆蓋率。以下通過Voronni劃分與Delaunay三角剖分來確定網絡中的獨立冗余節點[6]。

(2)網絡中“瓶頸節點”的選取。所謂“瓶頸節點”，即在一個隨機部署的WSN中，那些由于它們的失效而造成整個網絡被割裂成兩個或多個不相連的區域，并且由于收集數據的基站和檢測目標不在同一個區域內，造成整個網絡生命期結束的最少數目的節點。直觀地說，如果瓶頸節點消亡，則整個WSN的生命就結束。參考文獻[7]就是在全局范圍內找出限制網絡壽命的“瓶頸節點”。

(3)節點移動最佳路徑選擇。在前面兩部分的基礎上，選取合適的獨立冗余節點進行移動，將其移動到“瓶頸節點”的周圍，有兩個約束條件：不破壞網絡原有的覆蓋率以及移動損耗能量最少。在滿足基本網絡覆蓋率的情況下，使得“瓶頸節點”周圍有備用的節點，備用節點可以與 “瓶頸節點”協同工作或失效的 “瓶頸節點”替換。

(4)移動完畢后，網關節點會監聽“瓶頸節點”發出的信息，一旦該“瓶頸節點”的剩余能量低于閾值，則移動到其附近的節點會被喚醒，取代失效節點，從而使網絡正常工作。

2.2 相關概念

假設一個 WSN 包含一組節點 X={x1，x2，x3…，xn}，其中n為網絡內節點數量，n個節點部署到一個監測區域MA網絡內通常存在一個基站節點BS來實現信息匯聚以及與外界通信，正常的網絡節點采用多跳方式與BS通信，將感知數據傳送到需要的地方。假設：

(1)節點xi可采用GPS或其他方式獲取自己的位置；

(2)節點 xi的感知半徑為 Rsi和感知區域為 Asi，節點xi的通信半徑為 Rci；

2.3 尋找“瓶頸節點”的方法

“瓶頸節點”具有如下特點：

(1)“瓶頸節點”是兩個或多個WSN區域通信的唯一路徑，承擔著繁重的中繼任務。

(2)“瓶頸節點”的能耗要大大高于普通節點乃至基站節點，這就造成了節點的能耗差異較大和不均勻性。

(3)“瓶頸節點”失效意味著部分通信中斷、整個網絡失效或者部分失效(參考文獻[7]對此也有專門的討論)。針對上述特點，綜合KARGER等人提出的MINCUT算法[8]，借鑒開放最短路徑優先OSPF(Open Shortest Path First)[9]中的探測協議，提出基于消息交換的瓶頸節點定位算法。

算法的具體思想為：(1)節點發送報文到鄰居節點，鄰居節點以消息確認形式反饋；(2)節點通過消息交換獲得鄰居節點信息，生成拓撲結構，判斷是否為瓶頸節點。

2.4 EEBM算法的實現

經過2.3的研究，能夠得到所有的獨立冗余節點及網絡中制約使用壽命的“瓶頸節點”，以下將在這些工作的基礎上，在不破壞網絡連通性和覆蓋率以及最小化能量消耗的前提下，完成節點移動的任務，使得“瓶頸節點”周圍有備用的節點。

2.4.1 節點直接移動

由2.2及2.3可以得到所有獨立冗余節點的集合S和網絡中的“瓶頸節點”，節點直接移動算法的具體步驟為：(1)從獨立冗余節點集合S中選出可以移動的節點；(2)分別計算每個可移動節點移動時所消耗的能量及其剩余能量，并進行綜合評估，找到消耗能量少且剩余能量多的移動策略。但是，有時候消耗能量最小和剩余能量最大兩個最優不會同時達到，所以需要對這兩個代價進行折中；(3)向該節點發出命令信號，命令其向指定位置移動。

2.4.2 節點最佳路徑移動

節點直接移動方法的優點是算法簡單、效率高，但仍存在著較大的缺陷。例如，當可移動節點離指定位置較遠時，移動該節點會耗費較多能量，其移動后的剩余能量會很小，若此時采用節點直接移動算法，效果很差，因此以下給出采用節點最佳路徑移動的方法。該方法是在保證連通性和覆蓋率的情況下，逐步移動多個節點，使得最后移動到“瓶頸節點”周圍的替補節點的剩余能量相對較高，使用壽命也會更長。

節點最佳路徑移動的具體步驟如下：

(1)尋找中介節點的算法

當WSN中產生失效節點時，需要有新的節點移動到失效節點位置代替失效節點繼續工作。

假設x0為失效節點，xi為冗余節點，則可以將節點 xi移動到節點x0的位置，或者不直接將節點xi移動到處x0，而是尋找節點 x0與節點 xi之間的中介節點，產生多條節點移動路徑，如圖1所示。

圖1 x0到 xi之間的多條節點移動路徑

如果節點xi可以移動到節點xj處，則必須滿足不等式：

其中，dij為節點 xi與節點 xj的距離，v為節點移動速度。

用此方法可以找出x0與xi之間的多個中介節點，從而得到多條移動路徑，如圖1所示。并且計算每個中介節點圓區域內的節點分布密度、每個路徑的路徑節點密度、總體消耗能量和中介節點移動后的最小剩余能量。

(2)選擇最佳移動路徑

選擇最佳路徑的原則是：該路徑總體消耗能量最小，該路徑節點移動后的剩余能量最大以及該路徑節點密度最大。一般情況下，不可能同時滿足上述三個原則，于是應用層次分析法解決該問題。

層次分析法是數學建模中常用的用于決策的方法。在深入分析實際問題的基礎上，將有關的各個因素按照不同屬性自上而下地分解成若干層次。同一層的諸因素從屬于上一層的因素或對上層因素有影響，同時又支配下一層的因素或受到下層因素的作用。最上層為目標層，通常只有1個因素，最下層通常為方案或對象層，中間可以有1個或幾個層次，通常為準則或指標層。本文中目標層為選擇最佳路徑，準則層有3個因素分別是總體消耗能量最小、移動后節點最小剩余能量最大和路徑節點密度最大，方案層為若干條后選路徑，如圖2所示(假設有3條候選路徑)。

2.4.3 仿真及結果分析

仿真環境如下：無線傳感器節點隨機分布在40×40的平面正方形區域中，節點數目為48個，每個節點的初始能量E=2 000 J，節點移動速度V=1m/s，恢復時間T=10s，節點移動1 m消耗的能量為30 J，節點的傳感半徑R=6，傳感器的類型參數α=0.1，β=3進行仿真。節點移動前后瓶頸節點能耗對比如圖3所示。

圖2 選擇最佳節點移動路徑的層次結構

圖3 移動一個節點前后瓶頸節點能量消耗示意圖

假設節點平均接收一次信號消耗的能量為0.5 J，發送一次信號的能量為0.7 J，并且瓶頸節點每10 s周期性地發送或接收信號，其余節點處于休眠狀態。對下面兩種情況進行仿真：(1)不移動任何節點；(2)將離瓶頸節點較近的冗余節點移動到瓶頸節點的位置，共同分擔信號的接收和發送工作。仿真結果如圖3所示。

從圖3可以發現，瓶頸節點有了支援節點后，其消耗的能量明顯地減少，即瓶頸節點的壽命有所延長，從而延長了整個網絡的有效壽命。

本文對WSN中基于節點移動的節能路由問題進行了有針對性的研究，提出了利用冗余節點最佳移動路徑算法來解決“瓶頸節點”能量消耗過快的問題，形成了移動后的冗余節點與“瓶頸節點”協同工作，分擔通信負荷，提高 “瓶頸節點”壽命的新型節能路由算法——EEBM。該算法考慮了節點移動消耗能量、節點剩余能量和節點分布密度等因素，運用層次分析法，能夠在多條件約束情況下找到最佳的移動節點和移動路徑，從而保證在節點覆蓋不受影響的條件下網絡仍能正常工作，并且延長整個傳感器網絡的有效工作時間。仿真證明，在存在瓶頸節點的WSN中，EEBM算法相比其他節點移動算法確有較大的改進。

[1]LINDSEY S，RAGHAVENDRA C S.PEGASIS：Power-efficient gatheringinsensorinformationsystems[C].ProceedingoftheIEEE Aerospace Conf erence.Montana：IEEE Aerospace and Electronic SystemsSociety，2002：1125-1130.

[2]YE M，LI C F，CHEN G H，et al.EECS：An energy efficient clustering scheme in wireless sensor networks[C].Proceeding of the IEEE Int’1 Performance Computing and Communications Conference.NewYork：IEEEPress，2005：535-540.

[3]SOHRABI K，GAO J，AILAWADHI V，et al.Protocols for selforganization of a wireless sensor network [J].IEEE Personal Conununieations，2000，7(5)：16-27.

[4]YE F，CHENA，LIUS，etal，Ascalablesolutiontominimumcost forwarding in large sensor networks[C].Proceeding of the tenth International Conference on Computer Communications and Networks(ICCCN)2001，2001：304-309.

[5]HEINZELMAN W R，KULIK J，BALAKRISHNAN H.Adaptive protocols for information dissemination in wireless sensor networks[C].In： Proceeding.of the ACM MobiCom’99.Seattle： ACM Press，1999：174-185.

[6]馬震，劉云.一種無線傳感器網絡的能耗平衡覆蓋模型[J].北京：北京交通大學學報.

[7]田樂，謝東亮.無線傳感器網絡中瓶頸節點的研究[J].軟件學報，2006，17(4)：830-837.

[8]CHEKURI C S，GOLDBERG V A，KARGER D R.Experimental study of minimum cut algorithms[C].Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms，New Orleans，Louisiana，UnitedStates，January，1997：324-333.

[9]MOY JT.OSPF anatomy of an internet routing protocol.Addison-Wesley，1998.

[10]李成法，陳貴海，葉慰，等.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報，2007，30(1)：27-36.