摘  要： 通過對(duì)多種類型的無線傳感器網(wǎng)絡(luò)協(xié)議的研究，提出一種基于節(jié)點(diǎn)最佳路徑移動(dòng)的無線傳感器網(wǎng)絡(luò)節(jié)能路由算法(EEBM)。它通過尋找瓶頸節(jié)點(diǎn)、冗余點(diǎn)以及選擇最佳節(jié)點(diǎn)移動(dòng)路徑的方法，提高“瓶頸節(jié)點(diǎn)”的壽命，從而延長了整個(gè)網(wǎng)絡(luò)的生命周期。仿真結(jié)果表明，EEBM算法比其他節(jié)點(diǎn)移動(dòng)算法有較大的改進(jìn)。
關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)；節(jié)能路由； 瓶頸節(jié)點(diǎn)

    無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)作為新興的網(wǎng)絡(luò)測控技術(shù)，是能夠自主實(shí)現(xiàn)數(shù)據(jù)采集、融合和傳輸?shù)闹悄芫W(wǎng)絡(luò)系統(tǒng)，在軍事、交通、數(shù)字醫(yī)療等領(lǐng)域得到了廣泛應(yīng)用，因而引起了業(yè)界的廣泛關(guān)注。但是由于WSN節(jié)點(diǎn)受到體積和成本等方面的限制，一般采用攜帶的電池，能量補(bǔ)充困難而且能量相對(duì)較少，這是目前WSN應(yīng)用的主要問題。因此，如何降低能耗，提高整個(gè)網(wǎng)絡(luò)的生命周期是WSN的研究熱點(diǎn)，也是亟待解決的問題。
    目前，國內(nèi)外大量學(xué)者針對(duì)如何降低和平衡節(jié)點(diǎn)能耗問題進(jìn)行了研究，本文針對(duì)WSN路由節(jié)能問題進(jìn)行研究。在WSN中，由于節(jié)點(diǎn)特殊原因或節(jié)點(diǎn)能量受限等因素影響，個(gè)別節(jié)點(diǎn)失效或不能工作狀況時(shí)有發(fā)生。當(dāng)出現(xiàn)節(jié)點(diǎn)失效等情況后，需要有新的節(jié)點(diǎn)及時(shí)移動(dòng)到失效節(jié)點(diǎn)的位置，取代失效節(jié)點(diǎn)繼續(xù)工作。在這個(gè)取代的過程中，節(jié)點(diǎn)移動(dòng)有許多要解決的難題。首先，節(jié)點(diǎn)移動(dòng)有嚴(yán)格的時(shí)間要求。當(dāng)舊節(jié)點(diǎn)剩余能量低于閾值時(shí)，新節(jié)點(diǎn)必須在規(guī)定的時(shí)間內(nèi)移動(dòng)到舊節(jié)點(diǎn)位置，并且越快越好，從而保證在舊節(jié)點(diǎn)失效之前，新節(jié)點(diǎn)能夠接替其工作。這樣才不會(huì)影響WSN正常運(yùn)行，也不會(huì)出現(xiàn)盲區(qū)或某一時(shí)間無法監(jiān)測的區(qū)域。其次，節(jié)點(diǎn)移動(dòng)不能影響網(wǎng)絡(luò)的正常工作，因?yàn)樵诠?jié)點(diǎn)移動(dòng)的過程中，節(jié)點(diǎn)要與周圍節(jié)點(diǎn)交換信息，甚至可能影響節(jié)點(diǎn)的中繼路由或簇的形成。第三，由于傳感器節(jié)點(diǎn)的能量有限，節(jié)點(diǎn)移動(dòng)的消耗能量應(yīng)盡可能少，節(jié)約傳感器節(jié)點(diǎn)能源，從而延長整個(gè)傳感器網(wǎng)絡(luò)的有效工作時(shí)間。針對(duì)這些問題，本文在總結(jié)和應(yīng)用其他學(xué)者研究成果的基礎(chǔ)上，提出了一種基于節(jié)點(diǎn)最佳路徑移動(dòng)的無線傳感器網(wǎng)絡(luò)節(jié)能路由算法EEBM(Energy-Efficient routing algorithm based on the Best node Movement route)。
1 相關(guān)研究
1.1 分層型路由協(xié)議
    分層型路由協(xié)議中，能量較高節(jié)點(diǎn)可用于處理和傳遞信息，而能量較低的節(jié)點(diǎn)則只能用于對(duì)目標(biāo)進(jìn)行近似測量。典型的分層型路由協(xié)議主要包括：
    (1)低能耗自適應(yīng)分簇LEACH(Low Energy Adaptive Clustering Hierarchy)算法，它是一種自適應(yīng)型分簇拓?fù)渌惴ǎㄟ^讓各節(jié)點(diǎn)等概率的擔(dān)任簇頭達(dá)到相對(duì)均衡網(wǎng)絡(luò)中各節(jié)點(diǎn)所消耗的能量的目的。LEACH是一種以最小化傳感器網(wǎng)絡(luò)能量損耗為目標(biāo)的分層式協(xié)議，它集成了傳感器網(wǎng)絡(luò)的基本路由協(xié)議和拓?fù)淇刂扑惴?。在LEACH算法中整個(gè)網(wǎng)絡(luò)的通信由一輪一輪的周期性動(dòng)作組成，每一輪包括簇的建立階段和數(shù)據(jù)通信階段，其中簇的建立階段完成簇的組織，數(shù)據(jù)傳輸階段將數(shù)據(jù)傳送到簇首，再由簇首發(fā)送到基站(BS)。
    (2)傳感器信息系統(tǒng)的節(jié)能型采集方法PEGAS-IS[1]，它是一種臨近最優(yōu)鏈?zhǔn)絽f(xié)議，其基本思想是：借鑒LEACH的動(dòng)態(tài)簇頭選舉思想[2]，建立一條包含所有節(jié)點(diǎn)的最短路徑(稱為“鏈”)，并最終在每輪中只選出一個(gè)簇頭負(fù)責(zé)與網(wǎng)關(guān)節(jié)點(diǎn)通信。由于最短路徑鏈上的節(jié)點(diǎn)都能以最小發(fā)射功率向鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)，相比于LEACH，PEGAS-IS使網(wǎng)絡(luò)的生存時(shí)間得到顯著延長。但是，由于目前還沒有尋找包含所有節(jié)點(diǎn)的最短路徑的有效方法，PEGAS-IS不適合在大規(guī)模網(wǎng)絡(luò)上使用。
1.2 平面型路由協(xié)議
    在平面型路由中，所有節(jié)點(diǎn)的地位平等，典型協(xié)議主要有：
    (1)序列分配路由SAR[3]，其基本原理是：選擇路由時(shí)，綜合考慮能量資源、各路徑的服務(wù)質(zhì)量(QoS)和各信息包的優(yōu)先權(quán)3個(gè)要素，根據(jù)最終的權(quán)值來決定當(dāng)前的路由。若由于節(jié)點(diǎn)故障拓?fù)溥壿嫯a(chǎn)生變化，則需要重新計(jì)算路由。其中，基站負(fù)責(zé)計(jì)算拓?fù)溥壿嬜兓目偭浚⒅芷谛杂|發(fā)路徑重新計(jì)算。同時(shí)，還采用鄰近節(jié)點(diǎn)間基于局部路徑重建的交換方式恢復(fù)路徑。
    (2)最小開銷前向傳遞算法MCFA[4]，其基本原理是：利用路由傳遞方向的己知信息(例如向外部固定基站傳遞數(shù)據(jù))對(duì)數(shù)據(jù)進(jìn)行路由。無線傳感器節(jié)點(diǎn)前向傳遞的每條信息都被發(fā)送到相鄰節(jié)點(diǎn)中。當(dāng)節(jié)點(diǎn)接收到該信息時(shí)，檢查自己是否處于源節(jié)點(diǎn)與基站間最小花費(fèi)路徑上。如果是，則再將信息傳遞給相鄰節(jié)點(diǎn)。不斷重復(fù)該過程，直至該信息被傳遞到基站中。在MCFA中，各節(jié)點(diǎn)需要了解從本節(jié)點(diǎn)到基站間的預(yù)計(jì)最小花費(fèi)路徑，節(jié)點(diǎn)無需包含特有ID或維護(hù)路由表。另外，各節(jié)點(diǎn)也不斷修正自己到基站的最低花費(fèi)值。
1.3 適應(yīng)型路由
    信息協(xié)商傳感器協(xié)議(SPIN)[5]是適應(yīng)型路由的典型協(xié)議，可通過控制特定的系統(tǒng)參數(shù)以適應(yīng)網(wǎng)絡(luò)當(dāng)前條件和可用的能量水平。
    通過對(duì)典型節(jié)能路由模型的研究可以看出，針對(duì)WSN能耗的研究主要集中在路由和網(wǎng)絡(luò)的建立、節(jié)點(diǎn)分簇、簇頭選取、輪詢策略等方面，而通過策略選取節(jié)點(diǎn)，將其移動(dòng)到指定區(qū)域來取代失效節(jié)點(diǎn)，完成類似移動(dòng)Internet或3G/4G的移動(dòng)服務(wù)等方面的研究還相對(duì)較少。
2 基于節(jié)點(diǎn)最佳路徑移動(dòng)的WSN節(jié)能路由算法EEBM
2.1 基本思想
    EEBM主要研究當(dāng)“瓶頸節(jié)點(diǎn)”即將發(fā)生失效等情況時(shí)，如何在滿足節(jié)約節(jié)點(diǎn)移動(dòng)消耗能量等多條件約束情況下，找到最佳的移動(dòng)節(jié)點(diǎn)(優(yōu)先考慮移動(dòng)獨(dú)立冗余節(jié)點(diǎn))和移動(dòng)路徑，從而保證網(wǎng)絡(luò)的正常工作，延長網(wǎng)絡(luò)的有效工作時(shí)間的方法。
    算法的主要思想如下：
    (1)網(wǎng)絡(luò)中獨(dú)立冗余節(jié)點(diǎn)的選取策略。所謂獨(dú)立冗余節(jié)點(diǎn)，即若關(guān)閉該節(jié)點(diǎn)，不會(huì)影響網(wǎng)絡(luò)的覆蓋率。以下通過Voronni劃分與Delaunay三角剖分來確定網(wǎng)絡(luò)中的獨(dú)立冗余節(jié)點(diǎn)[6]。
    (2)網(wǎng)絡(luò)中“瓶頸節(jié)點(diǎn)”的選取。所謂“瓶頸節(jié)點(diǎn)”，即在一個(gè)隨機(jī)部署的WSN中，那些由于它們的失效而造成整個(gè)網(wǎng)絡(luò)被割裂成兩個(gè)或多個(gè)不相連的區(qū)域，并且由于收集數(shù)據(jù)的基站和檢測目標(biāo)不在同一個(gè)區(qū)域內(nèi)，造成整個(gè)網(wǎng)絡(luò)生命期結(jié)束的最少數(shù)目的節(jié)點(diǎn)。直觀地說，如果瓶頸節(jié)點(diǎn)消亡，則整個(gè)WSN的生命就結(jié)束。參考文獻(xiàn)[7]就是在全局范圍內(nèi)找出限制網(wǎng)絡(luò)壽命的“瓶頸節(jié)點(diǎn)”。
     (3)節(jié)點(diǎn)移動(dòng)最佳路徑選擇。在前面兩部分的基礎(chǔ)上，選取合適的獨(dú)立冗余節(jié)點(diǎn)進(jìn)行移動(dòng)，將其移動(dòng)到“瓶頸節(jié)點(diǎn)”的周圍，有兩個(gè)約束條件：不破壞網(wǎng)絡(luò)原有的覆蓋率以及移動(dòng)損耗能量最少。在滿足基本網(wǎng)絡(luò)覆蓋率的情況下，使得“瓶頸節(jié)點(diǎn)”周圍有備用的節(jié)點(diǎn)，備用節(jié)點(diǎn)可以與“瓶頸節(jié)點(diǎn)”協(xié)同工作或失效的“瓶頸節(jié)點(diǎn)”替換。
    (4)移動(dòng)完畢后，網(wǎng)關(guān)節(jié)點(diǎn)會(huì)監(jiān)聽“瓶頸節(jié)點(diǎn)”發(fā)出的信息，一旦該“瓶頸節(jié)點(diǎn)”的剩余能量低于閾值，則移動(dòng)到其附近的節(jié)點(diǎn)會(huì)被喚醒，取代失效節(jié)點(diǎn)，從而使網(wǎng)絡(luò)正常工作。


2.3 尋找“瓶頸節(jié)點(diǎn)”的方法
    “瓶頸節(jié)點(diǎn)”具有如下特點(diǎn)：
    (1)“瓶頸節(jié)點(diǎn)”是兩個(gè)或多個(gè)WSN區(qū)域通信的唯一路徑，承擔(dān)著繁重的中繼任務(wù)。
    (2)“瓶頸節(jié)點(diǎn)”的能耗要大大高于普通節(jié)點(diǎn)乃至基站節(jié)點(diǎn)，這就造成了節(jié)點(diǎn)的能耗差異較大和不均勻性。
    (3)“瓶頸節(jié)點(diǎn)”失效意味著部分通信中斷、整個(gè)網(wǎng)絡(luò)失效或者部分失效(參考文獻(xiàn)[7]對(duì)此也有專門的討論)。針對(duì)上述特點(diǎn)，綜合KARGER等人提出的MINCUT算法[8]，借鑒開放最短路徑優(yōu)先OSPF(Open Shortest Path First)[9]中的探測協(xié)議，提出基于消息交換的瓶頸節(jié)點(diǎn)定位算法。
    算法的具體思想為：(1)節(jié)點(diǎn)發(fā)送報(bào)文到鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)以消息確認(rèn)形式反饋；(2)節(jié)點(diǎn)通過消息交換獲得鄰居節(jié)點(diǎn)信息，生成拓?fù)浣Y(jié)構(gòu)，判斷是否為瓶頸節(jié)點(diǎn)。
2.4 EEBM算法的實(shí)現(xiàn)
    經(jīng)過2.3的研究，能夠得到所有的獨(dú)立冗余節(jié)點(diǎn)及網(wǎng)絡(luò)中制約使用壽命的“瓶頸節(jié)點(diǎn)”，以下將在這些工作的基礎(chǔ)上，在不破壞網(wǎng)絡(luò)連通性和覆蓋率以及最小化能量消耗的前提下，完成節(jié)點(diǎn)移動(dòng)的任務(wù)，使得“瓶頸節(jié)點(diǎn)”周圍有備用的節(jié)點(diǎn)。
2.4.1 節(jié)點(diǎn)直接移動(dòng)
    由2.2及2.3可以得到所有獨(dú)立冗余節(jié)點(diǎn)的集合S和網(wǎng)絡(luò)中的“瓶頸節(jié)點(diǎn)”，節(jié)點(diǎn)直接移動(dòng)算法的具體步驟為：(1)從獨(dú)立冗余節(jié)點(diǎn)集合S中選出可以移動(dòng)的節(jié)點(diǎn)；(2)分別計(jì)算每個(gè)可移動(dòng)節(jié)點(diǎn)移動(dòng)時(shí)所消耗的能量及其剩余能量，并進(jìn)行綜合評(píng)估，找到消耗能量少且剩余能量多的移動(dòng)策略。但是，有時(shí)候消耗能量最小和剩余能量最大兩個(gè)最優(yōu)不會(huì)同時(shí)達(dá)到，所以需要對(duì)這兩個(gè)代價(jià)進(jìn)行折中；(3)向該節(jié)點(diǎn)發(fā)出命令信號(hào)，命令其向指定位置移動(dòng)。
2.4.2 節(jié)點(diǎn)最佳路徑移動(dòng)
    節(jié)點(diǎn)直接移動(dòng)方法的優(yōu)點(diǎn)是算法簡單、效率高，但仍存在著較大的缺陷。例如，當(dāng)可移動(dòng)節(jié)點(diǎn)離指定位置較遠(yuǎn)時(shí)，移動(dòng)該節(jié)點(diǎn)會(huì)耗費(fèi)較多能量，其移動(dòng)后的剩余能量會(huì)很小，若此時(shí)采用節(jié)點(diǎn)直接移動(dòng)算法，效果很差，因此以下給出采用節(jié)點(diǎn)最佳路徑移動(dòng)的方法。該方法是在保證連通性和覆蓋率的情況下，逐步移動(dòng)多個(gè)節(jié)點(diǎn)，使得最后移動(dòng)到“瓶頸節(jié)點(diǎn)”周圍的替補(bǔ)節(jié)點(diǎn)的剩余能量相對(duì)較高，使用壽命也會(huì)更長。
節(jié)點(diǎn)最佳路徑移動(dòng)的具體步驟如下：
    (1)尋找中介節(jié)點(diǎn)的算法
    當(dāng)WSN中產(chǎn)生失效節(jié)點(diǎn)時(shí)，需要有新的節(jié)點(diǎn)移動(dòng)到失效節(jié)點(diǎn)位置代替失效節(jié)點(diǎn)繼續(xù)工作。
    假設(shè)x0為失效節(jié)點(diǎn)，xi為冗余節(jié)點(diǎn)，則可以將節(jié)點(diǎn)xi移動(dòng)到節(jié)點(diǎn)x0的位置，或者不直接將節(jié)點(diǎn)xi移動(dòng)到處x0，而是尋找節(jié)點(diǎn)x0與節(jié)點(diǎn)xi之間的中介節(jié)點(diǎn)，產(chǎn)生多條節(jié)點(diǎn)移動(dòng)路徑，如圖1所示。

    用此方法可以找出x0與xi之間的多個(gè)中介節(jié)點(diǎn)，從而得到多條移動(dòng)路徑，如圖1所示。并且計(jì)算每個(gè)中介節(jié)點(diǎn)圓區(qū)域內(nèi)的節(jié)點(diǎn)分布密度、每個(gè)路徑的路徑節(jié)點(diǎn)密度、總體消耗能量和中介節(jié)點(diǎn)移動(dòng)后的最小剩余能量。
    (2)選擇最佳移動(dòng)路徑
    選擇最佳路徑的原則是：該路徑總體消耗能量最小，該路徑節(jié)點(diǎn)移動(dòng)后的剩余能量最大以及該路徑節(jié)點(diǎn)密度最大。一般情況下，不可能同時(shí)滿足上述三個(gè)原則，于是應(yīng)用層次分析法解決該問題。
    層次分析法是數(shù)學(xué)建模中常用的用于決策的方法。在深入分析實(shí)際問題的基礎(chǔ)上，將有關(guān)的各個(gè)因素按照不同屬性自上而下地分解成若干層次。同一層的諸因素從屬于上一層的因素或?qū)ι蠈右蛩赜杏绊?，同時(shí)又支配下一層的因素或受到下層因素的作用。最上層為目標(biāo)層，通常只有1個(gè)因素，最下層通常為方案或?qū)ο髮?，中間可以有1個(gè)或幾個(gè)層次，通常為準(zhǔn)則或指標(biāo)層。本文中目標(biāo)層為選擇最佳路徑，準(zhǔn)則層有3個(gè)因素分別是總體消耗能量最小、移動(dòng)后節(jié)點(diǎn)最小剩余能量最大和路徑節(jié)點(diǎn)密度最大，方案層為若干條后選路徑，如圖2所示(假設(shè)有3條候選路徑)。

2.4.3 仿真及結(jié)果分析
    仿真環(huán)境如下：無線傳感器節(jié)點(diǎn)隨機(jī)分布在40×40的平面正方形區(qū)域中，節(jié)點(diǎn)數(shù)目為48個(gè)，每個(gè)節(jié)點(diǎn)的初始能量E=2 000 J，節(jié)點(diǎn)移動(dòng)速度V=1 m/s，恢復(fù)時(shí)間T=10 s，節(jié)點(diǎn)移動(dòng)1 m消耗的能量為30 J，節(jié)點(diǎn)的傳感半徑R=6，傳感器的類型參數(shù)α=0.1，β=3進(jìn)行仿真。節(jié)點(diǎn)移動(dòng)前后瓶頸節(jié)點(diǎn)能耗對(duì)比如圖3所示。

    假設(shè)節(jié)點(diǎn)平均接收一次信號(hào)消耗的能量為0.5 J，發(fā)送一次信號(hào)的能量為0.7 J，并且瓶頸節(jié)點(diǎn)每10 s周期性地發(fā)送或接收信號(hào)，其余節(jié)點(diǎn)處于休眠狀態(tài)。對(duì)下面兩種情況進(jìn)行仿真：(1)不移動(dòng)任何節(jié)點(diǎn)；(2)將離瓶頸節(jié)點(diǎn)較近的冗余節(jié)點(diǎn)移動(dòng)到瓶頸節(jié)點(diǎn)的位置，共同分擔(dān)信號(hào)的接收和發(fā)送工作。仿真結(jié)果如圖3所示。
    從圖3可以發(fā)現(xiàn)，瓶頸節(jié)點(diǎn)有了支援節(jié)點(diǎn)后，其消耗的能量明顯地減少，即瓶頸節(jié)點(diǎn)的壽命有所延長，從而延長了整個(gè)網(wǎng)絡(luò)的有效壽命。
    本文對(duì)WSN中基于節(jié)點(diǎn)移動(dòng)的節(jié)能路由問題進(jìn)行了有針對(duì)性的研究，提出了利用冗余節(jié)點(diǎn)最佳移動(dòng)路徑算法來解決“瓶頸節(jié)點(diǎn)”能量消耗過快的問題，形成了移動(dòng)后的冗余節(jié)點(diǎn)與“瓶頸節(jié)點(diǎn)”協(xié)同工作，分擔(dān)通信負(fù)荷，提高“瓶頸節(jié)點(diǎn)”壽命的新型節(jié)能路由算法——EEBM。該算法考慮了節(jié)點(diǎn)移動(dòng)消耗能量、節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)分布密度等因素，運(yùn)用層次分析法，能夠在多條件約束情況下找到最佳的移動(dòng)節(jié)點(diǎn)和移動(dòng)路徑，從而保證在節(jié)點(diǎn)覆蓋不受影響的條件下網(wǎng)絡(luò)仍能正常工作，并且延長整個(gè)傳感器網(wǎng)絡(luò)的有效工作時(shí)間。仿真證明，在存在瓶頸節(jié)點(diǎn)的WSN中，EEBM算法相比其他節(jié)點(diǎn)移動(dòng)算法確有較大的改進(jìn)。
參考文獻(xiàn)
[1] LINDSEY S， RAGHAVENDRA C S. PEGASIS： Power-efficient gathering in sensor information systems[C]. Proceeding of the IEEE Aerospace Conf erence. Montana： IEEE Aerospace and Electronic Systems Society， 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. New York： IEEE Press， 2005： 535-540.
[3] SOHRABI K， GAO J， AILAWADHI V， et al. Protocols for self-organization of a wireless sensor network[J]. IEEE Personal Conununieations， 2000， 7(5)： 16-27.
[4] YE F， CHEN A， LIU S， et al， A scalable solution to minimum cost 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] 馬震，劉云.一種無線傳感器網(wǎng)絡(luò)的能耗平衡覆蓋模型[J].北京：北京交通大學(xué)學(xué)報(bào).
[7] 田樂，謝東亮.無線傳感器網(wǎng)絡(luò)中瓶頸節(jié)點(diǎn)的研究[J].軟件學(xué)報(bào)，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， United States， January， 1997： 324-333.
[9] MOY  J T. OSPF anatomy  of  an  internet routing protocol. Addison- Wesley， 1998.
[10] 李成法，陳貴海，葉慰，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào)，2007，30(1)：27-36.