0 引言
無線傳感器網絡所具有的眾多類型的傳感器，可探測包括地震、電磁、溫度、濕度、噪聲、光強度、壓力、土壤成分、移動物體的大小、速度和方向等周邊環(huán)境中多種多樣的現(xiàn)象。基于MEMS的微傳感技術和無線聯(lián)網技術為無線傳感器網絡賦予了廣闊的應用前景。這些潛在的應用領域可以歸納為：軍事、航空、反恐、防爆、救災、環(huán)境、醫(yī)療、保健、家居、工業(yè)、商業(yè)等領域。
無線傳感器網絡WSN（Wireless Sensor Network）作為新興的網絡測控技術，是能夠自主實現(xiàn)數(shù)據(jù)采集、融合和傳輸?shù)闹悄芫W絡系統(tǒng)，在軍事、交通、數(shù)字醫(yī)療等領域得到了廣泛應用，因而引起了業(yè)界的廣泛關注。但是由于WSN節(jié)點受到體積和成本等方面的限制，一般采用攜帶的電池，能量補充困難而且能量相對較少，這是目前WSN應用的主要問題。針對這些問題，本文在總結和應用其他學者研究成果的基礎上，提出了一種基于節(jié)點最佳路徑移動的無線傳感器網絡節(jié)能路由算法EEBM（Energy-Efficient routing algorithm based ON the BeST node Movement route）。
1 相關研究
1.1 分層型路由協(xié)議
分層型路由協(xié)議中，能量較高節(jié)點可用于處理和傳遞信息，而能量較低的節(jié)點則只能用于對目標進行近似測量。典型的分層型路由協(xié)議主要包括：
?。?）低能耗自適應分簇LEACH（Low Energy Adaptive Clustering Hierarchy）算法，它是一種自適應型分簇拓撲算法，通過讓各節(jié)點等概率的擔任簇頭達到相對均衡網絡中各節(jié)點所消耗的能量的目的。LEACH是一種以最小化傳感器網絡能量損耗為目標的分層式協(xié)議，它集成了傳感器網絡的基本路由協(xié)議和拓撲控制算法。在LEACH算法中整個網絡的通信由一輪一輪的周期性動作組成，每一輪包括簇的建立階段和數(shù)據(jù)通信階段，其中簇的建立階段完成簇的組織，數(shù)據(jù)傳輸階段將數(shù)據(jù)傳送到簇首，再由簇首發(fā)送到基站（BS）。
?。?）傳感器信息系統(tǒng)的節(jié)能型采集方法PEGAS-IS[1]，它是一種臨近最優(yōu)鏈式協(xié)議，其基本思想是：借鑒LEACH的動態(tài)簇頭選舉思想，建立一條包含所有節(jié)點的最短路徑（稱為“鏈”），并最終在每輪中只選出一個簇頭負責與網關節(jié)點通信。由于最短路徑鏈上的節(jié)點都能以最小發(fā)射功率向鄰居節(jié)點發(fā)送數(shù)據(jù)，相比于LEACH，PEGAS-IS使網絡的生存時間得到顯著延長。但是，由于目前還沒有尋找包含所有節(jié)點的最短路徑的有效方法，PEGAS-IS不適合在大規(guī)模網絡上使用。
1.2 平面型路由協(xié)議
在平面型路由中，所有節(jié)點的地位平等，典型協(xié)議主要有：
（1）序列分配路由SAR，其基本原理是：選擇路由時，綜合考慮能量資源、各路徑的服務質量（QoS）和各信息包的優(yōu)先權3個要素，根據(jù)最終的權值來決定當前的路由。若由于節(jié)點故障拓撲邏輯產生變化，則需要重新計算路由。其中，基站負責計算拓撲邏輯變化的總量，并周期性觸發(fā)路徑重新計算。同時，還采用鄰近節(jié)點間基于局部路徑重建的交換方式恢復路徑。
（2）最小開銷前向傳遞算法MCFA，其基本原理是：利用路由傳遞方向的己知信息（例如向外部固定基站傳遞數(shù)據(jù)）對數(shù)據(jù)進行路由。無線傳感器節(jié)點前向傳遞的每條信息都被發(fā)送到相鄰節(jié)點中。當節(jié)點接收到該信息時，檢查自己是否處于源節(jié)點與基站間最小花費路徑上。如果是，則再將信息傳遞給相鄰節(jié)點。
1.3 適應型路由
信息協(xié)商傳感器協(xié)議（SPIN）是適應型路由的典型協(xié)議，可通過控制特定的系統(tǒng)參數(shù)以適應網絡當前條件和可用的能量水平。
通過對典型節(jié)能路由模型的研究可以看出，針對WSN能耗的研究主要集中在路由和網絡的建立、節(jié)點分簇、簇頭選取、輪詢策略等方面，而通過策略選取節(jié)點，將其移動到指定區(qū)域來取代失效節(jié)點，完成類似移動Internet或3G/4G的移動服務等方面的研究還相對較少。
2 基于節(jié)點最佳路徑移動的WSN節(jié)能路由算法EEBM
2.1 基本思想
EEBM主要研究當“瓶頸節(jié)點”即將發(fā)生失效等情況時，如何在滿足節(jié)約節(jié)點移動消耗能量等多條件約束情況下，找到最佳的移動節(jié)點（優(yōu)先考慮移動獨立冗余節(jié)點）和移動路徑，從而保證網絡的正常工作，延長網絡的有效工作時間的方法。
算法的主要思想如下：
?。?）網絡中獨立冗余節(jié)點的選取策略。所謂獨立冗余節(jié)點，即若關閉該節(jié)點，不會影響網絡的覆蓋率。以下通過Voronni劃分與Delaunay三角剖分來確定網絡中的獨立冗余節(jié)點。
（2）網絡中“瓶頸節(jié)點”的選取。所謂“瓶頸節(jié)點”，即在一個隨機部署的WSN中，那些由于它們的失效而造成整個網絡被割裂成兩個或多個不相連的區(qū)域，并且由于收集數(shù)據(jù)的基站和檢測目標不在同一個區(qū)域內，造成整個網絡生命期結束的最少數(shù)目的節(jié)點。直觀地說，如果瓶頸節(jié)點消亡，則整個WSN的生命就結束。
?。?）節(jié)點移動最佳路徑選擇。在前面兩部分的基礎上，選取合適的獨立冗余節(jié)點進行移動，將其移動到“瓶頸節(jié)點”的周圍，有兩個約束條件：不破壞網絡原有的覆蓋率以及移動損耗能量最少。
?。?）移動完畢后，網關節(jié)點會監(jiān)聽“瓶頸節(jié)點”發(fā)出的信息，一旦該“瓶頸節(jié)點”的剩余能量低于閾值，則移動到其附近的節(jié)點會被喚醒，取代失效節(jié)點，從而使網絡正常工作。
2.3 尋找“瓶頸節(jié)點”的方法
“瓶頸節(jié)點”具有如下特點：
?。?）“瓶頸節(jié)點”是兩個或多個WSN區(qū)域通信的唯一路徑，承擔著繁重的中繼任務。
?。?）“瓶頸節(jié)點”的能耗要大大高于普通節(jié)點乃至基站節(jié)點，這就造成了節(jié)點的能耗差異較大和不均勻性。
?。?）“瓶頸節(jié)點”失效意味著部分通信中斷、整個網絡失效或者部分失效（參考文獻[7]對此也有專門的討論）。針對上述特點，綜合KARGER等人提出的MINCUT算法，借鑒開放最短路徑優(yōu)先OSPF（Open Shortest Path First）[9]中的探測協(xié)議，提出基于消息交換的瓶頸節(jié)點定位算法。
算法的具體思想為：（1）節(jié)點發(fā)送報文到鄰居節(jié)點，鄰居節(jié)點以消息確認形式反饋；（2）節(jié)點通過消息交換獲得鄰居節(jié)點信息，生成拓撲結構，判斷是否為瓶頸節(jié)點。
2.4 EEBM算法的實現(xiàn)
經過2.3的研究，能夠得到所有的獨立冗余節(jié)點及網絡中制約使用壽命的“瓶頸節(jié)點”，以下將在這些工作的基礎上，在不破壞網絡連通性和覆蓋率以及最小化能量消耗的前提下，完成節(jié)點移動的任務，使得“瓶頸節(jié)點”周圍有備用的節(jié)點。
2.4.1 節(jié)點直接移動
由2.2及2.3可以得到所有獨立冗余節(jié)點的集合S和網絡中的“瓶頸節(jié)點”，節(jié)點直接移動算法的具體步驟為：（1）從獨立冗余節(jié)點集合S中選出可以移動的節(jié)點；（2）分別計算每個可移動節(jié)點移動時所消耗的能量及其剩余能量，并進行綜合評估，找到消耗能量少且剩余能量多的移動策略。
2.4.2 節(jié)點最佳路徑移動
節(jié)點直接移動方法的優(yōu)點是算法簡單、效率高，但仍存在著較大的缺陷。例如，當可移動節(jié)點離指定位置較遠時，移動該節(jié)點會耗費較多能量，其移動后的剩余能量會很小，若此時采用節(jié)點直接移動算法，效果很差，因此以下給出采用節(jié)點最佳路徑移動的方法。
節(jié)點最佳路徑移動的具體步驟如下：
?。?）尋找中介節(jié)點的算法
當WSN中產生失效節(jié)點時，需要有新的節(jié)點移動到失效節(jié)點位置代替失效節(jié)點繼續(xù)工作。
假設x0為失效節(jié)點，xi為冗余節(jié)點，則可以將節(jié)點xi移動到節(jié)點x0的位置，或者不直接將節(jié)點xi移動到處x0，而是尋找節(jié)點x0與節(jié)點xi之間的中介節(jié)點，產生多條節(jié)點移動路徑，如圖1所示。
用此方法可以找出x0與xi之間的多個中介節(jié)點，從而得到多條移動路徑，如圖1所示。并且計算每個中介節(jié)點圓區(qū)域內的節(jié)點分布密度、每個路徑的路徑節(jié)點密度、總體消耗能量和中介節(jié)點移動后的最小剩余能量。
（2）選擇最佳移動路徑
選擇最佳路徑的原則是：該路徑總體消耗能量最小，該路徑節(jié)點移動后的剩余能量最大以及該路徑節(jié)點密度最大。一般情況下，不可能同時滿足上述三個原則，于是應用層次分析法解決該問題。
層次分析法是數(shù)學建模中常用的用于決策的方法。在深入分析實際問題的基礎上，將有關的各個因素按照不同屬性自上而下地分解成若干層次。本文中目標層為選擇最佳路徑，準則層有3個因素分別是總體消耗能量最小、移動后節(jié)點最小剩余能量最大和路徑節(jié)點密度最大，方案層為若干條后選路徑，如圖2所示（假設有3條候選路徑）。
2.4.3 仿真及結果分析
仿真環(huán)境如下：無線傳感器節(jié)點隨機分布在40×40的平面正方形區(qū)域中，節(jié)點數(shù)目為48個，每個節(jié)點的初始能量E=2 000 J，節(jié)點移動速度V=1 m/s，恢復時間T=10 s，節(jié)點移動1 m消耗的能量為30 J，節(jié)點的傳感半徑R=6，傳感器的類型參數(shù)α=0.1，β=3進行仿真。節(jié)點移動前后瓶頸節(jié)點能耗對比如圖3所示。
假設節(jié)點平均接收一次信號消耗的能量為0.5 J，發(fā)送一次信號的能量為0.7 J，并且瓶頸節(jié)點每10 s周期性地發(fā)送或接收信號，其余節(jié)點處于休眠狀態(tài)。對下面兩種情況進行仿真：（1）不移動任何節(jié)點；（2）將離瓶頸節(jié)點較近的冗余節(jié)點移動到瓶頸節(jié)點的位置，共同分擔信號的接收和發(fā)送工作。仿真結果如圖3所示。
從圖3可以發(fā)現(xiàn)，瓶頸節(jié)點有了支援節(jié)點后，其消耗的能量明顯地減少，即瓶頸節(jié)點的壽命有所延長，從而延長了整個網絡的有效壽命。
3 結束語
本文對WSN中基于節(jié)點移動的節(jié)能路由問題進行了有針對性的研究，提出了利用冗余節(jié)點最佳移動路徑算法來解決“瓶頸節(jié)點”能量消耗過快的問題，形成了移動后的冗余節(jié)點與“瓶頸節(jié)點”協(xié)同工作，分擔通信負荷，提高“瓶頸節(jié)點”壽命的新型節(jié)能路由算法——EEBM。該算法考慮了節(jié)點移動消耗能量、節(jié)點剩余能量和節(jié)點分布密度等因素，運用層次分析法，能夠在多條件約束情況下找到最佳的移動節(jié)點和移動路徑，從而保證在節(jié)點覆蓋不受影響的條件下網絡仍能正常工作，并且延長整個傳感器網絡的有效工作時間。仿真證明，在存在瓶頸節(jié)點的WSN中，EEBM算法相比其他節(jié)點移動算法確有較大的改進。
