基于最小能耗的無(wú)線傳感器網(wǎng)絡(luò)路由算法 - 全文

?

　　無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線通信方式形成的一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng)。同時(shí)，網(wǎng)絡(luò)中的節(jié)點(diǎn)擁有感知能力、無(wú)線通信能力以及計(jì)算能力。由于無(wú)線傳感器網(wǎng)絡(luò)具有不依賴與任何預(yù)設(shè)網(wǎng)絡(luò)設(shè)施等特點(diǎn)，所以在軍事應(yīng)用、大型設(shè)備監(jiān)控和環(huán)境監(jiān)測(cè)和預(yù)報(bào)等領(lǐng)域，傳感器網(wǎng)絡(luò)都有著廣泛的應(yīng)用前景。傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)分布數(shù)量眾多，且能量是由容量有限的電池供電，更換不易。傳感器節(jié)點(diǎn)消耗能量的模塊包括傳感器模塊、處理器模塊和無(wú)線通信模塊。隨著集成電路工藝的進(jìn)步，處理器和傳感器模塊的功耗變得很低，絕大部分能量消耗在無(wú)線通信模塊上。所以如何設(shè)計(jì)節(jié)能高效的路由策略是延長(zhǎng)網(wǎng)絡(luò)生存周期的重要手段。

　　近些年來(lái)，一些節(jié)能高效的路由算法相繼被提出。文獻(xiàn)通過(guò)引入長(zhǎng)期睡眠機(jī)制，防止網(wǎng)絡(luò)中的某些節(jié)點(diǎn)因?yàn)檫^(guò)早耗盡能量而死亡，引起網(wǎng)絡(luò)無(wú)效。文獻(xiàn)設(shè)計(jì)了一種無(wú)線傳感器網(wǎng)絡(luò)通信架構(gòu)ADOCA，有效地改善了無(wú)限傳感器網(wǎng)絡(luò)通信的有效性。文獻(xiàn)提出了一種基于多蟻群無(wú)線傳感器網(wǎng)絡(luò)路由算法，采用多種蟻群并行搜索，并在種群中采用基于目標(biāo)函數(shù)值的啟發(fā)式信息素分配策略和根據(jù)目標(biāo)函數(shù)自動(dòng)調(diào)整螞蟻搜索路徑。文獻(xiàn)中針對(duì)SPR路由算法進(jìn)行改進(jìn)，提出了EB-SPR算法。將網(wǎng)絡(luò)構(gòu)造成層次結(jié)構(gòu)，節(jié)點(diǎn)根據(jù)上一層鄰節(jié)點(diǎn)能量水平優(yōu)先使用能量多的節(jié)點(diǎn)作為下一跳來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)包，但是這種算法中節(jié)點(diǎn)需要時(shí)刻維護(hù)各個(gè)鄰節(jié)點(diǎn)能量信息，增加了數(shù)據(jù)傳輸量。文獻(xiàn)提出了最早的分層路由協(xié)議之一，LEACH算法。通過(guò)循環(huán)的方式隨機(jī)選擇簇首節(jié)點(diǎn)，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)傳感器節(jié)點(diǎn)中，從而達(dá)到降低網(wǎng)絡(luò)能耗、提高網(wǎng)絡(luò)整體生存時(shí)間的目的。本文提出了一種新的基于最小能耗的無(wú)線傳感器網(wǎng)絡(luò)路由算法，并對(duì)網(wǎng)絡(luò)中能量過(guò)低的節(jié)點(diǎn)采取休眠處理，延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

　　1 無(wú)線傳感器網(wǎng)絡(luò)能量消耗研究和路由分析

　　1.1 無(wú)線傳感器網(wǎng)絡(luò)能量消耗研究

　　傳感器網(wǎng)絡(luò)節(jié)點(diǎn)主要有傳感器模塊，處理器模塊，無(wú)線通信模塊和能量供應(yīng)模塊。隨著技術(shù)的進(jìn)步，目前傳感器模塊和處理器模塊能耗越來(lái)越低。但是，傳感器節(jié)點(diǎn)傳輸信息時(shí)要比執(zhí)行計(jì)算時(shí)更消耗電能，傳輸1 b信息到100 m距離需要的能量大約相當(dāng)于執(zhí)行3 000條指令消耗的能量。

　　本文假設(shè)一個(gè)簡(jiǎn)單的無(wú)線通信電路模型，其中發(fā)送和接收電路消耗能量Eelec=50 nJ/b，發(fā)送放大器消耗能量εamp=100 pJ/(b/m2)。所以，使用該模型從節(jié)點(diǎn)A傳輸kb信息至距離為d的節(jié)點(diǎn)B時(shí)，節(jié)點(diǎn)A消耗的能量為ETx(k，d)=Eeleck+εampkd2，接收該信息，節(jié)點(diǎn)B消耗的能量為ERx(k)=Eeleck。如圖1所示。

?

　　無(wú)線通信模塊存在發(fā)送、接收、空閑和睡眠4種狀態(tài)。無(wú)線通信模塊在空閑狀態(tài)一直監(jiān)聽無(wú)線信道的使用情況，檢查是否有數(shù)據(jù)發(fā)送給自己，而在睡眠狀態(tài)則關(guān)閉通信模塊。從圖2中可看到，無(wú)線通信模塊在發(fā)送狀態(tài)的能量消耗最大，在空閑狀態(tài)和接收狀態(tài)的能量消耗接近，略少于發(fā)送狀態(tài)的能量消耗，在睡眠狀態(tài)的能量消耗最少。

?

　　1.2 LEACH路由協(xié)議分析

　　最早的分簇路由協(xié)議是由Wendi等三人在2000年提出的LEACH算法，全稱為“低功耗自適應(yīng)集簇分層型協(xié)議”。LEACH算法的每一輪操作分為兩個(gè)運(yùn)行階段：簇建立階段和簇穩(wěn)定運(yùn)行階段。由于簇建立階段是屬于額外的通信需求，所以穩(wěn)定運(yùn)行的持續(xù)時(shí)間要遠(yuǎn)大于建立階段持續(xù)的時(shí)間。

　　在簇建立階段，傳感器節(jié)點(diǎn)隨機(jī)生成一個(gè)0，1之間的隨機(jī)數(shù)，并且與閾值T(n)做比較，如果小于該閾值，則該節(jié)點(diǎn)就會(huì)當(dāng)選為簇首。T(n)按照下面公式計(jì)算：

?

　　式中：P為節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的百分?jǐn)?shù);r為當(dāng)前輪數(shù);G為在這一輪中未當(dāng)選簇首的節(jié)點(diǎn)集合。

　　簇首節(jié)點(diǎn)選定后，廣播自己成為簇首的消息，節(jié)點(diǎn)根據(jù)接收到的消息的強(qiáng)度決定加入哪個(gè)簇，并告知相應(yīng)的簇首，完成簇的建立過(guò)程。然后，簇首節(jié)點(diǎn)采用TDMA的方式，為簇內(nèi)成員分配傳送數(shù)據(jù)的時(shí)隙。以上LEACH算法存在一個(gè)很大的缺陷，即協(xié)議沒有說(shuō)明蔟首節(jié)點(diǎn)的數(shù)目怎么分布才能遍及于整個(gè)網(wǎng)絡(luò)。因此，很可能出現(xiàn)被選的簇首節(jié)點(diǎn)集中在網(wǎng)絡(luò)某一區(qū)域的現(xiàn)象，這樣就會(huì)使得一些節(jié)點(diǎn)的周圍沒有任何簇首節(jié)點(diǎn)。同時(shí)，由于簇首節(jié)點(diǎn)是隨機(jī)選擇的，有可能出現(xiàn)某個(gè)節(jié)點(diǎn)剩余能量過(guò)低而不能成為簇首節(jié)點(diǎn)，從而導(dǎo)致網(wǎng)絡(luò)失效。

　　2 基于最小能耗的無(wú)線傳感器網(wǎng)絡(luò)路由算法

　　2.1 算法拓?fù)浣Y(jié)構(gòu)

　　圖3所示為無(wú)線傳感器網(wǎng)絡(luò)路由算法的拓?fù)浣Y(jié)構(gòu)。整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)被分為匯聚節(jié)點(diǎn)、簇首節(jié)點(diǎn)和普通節(jié)點(diǎn)。網(wǎng)絡(luò)由若干個(gè)子區(qū)域組成，子區(qū)域自主產(chǎn)生簇首節(jié)點(diǎn)，區(qū)域內(nèi)的其他節(jié)點(diǎn)和簇首節(jié)點(diǎn)通信并通過(guò)簇首節(jié)點(diǎn)將數(shù)據(jù)傳輸給匯聚節(jié)點(diǎn)。

?

　　2.2 算法描述

　　為了改進(jìn)上述LEACH算法存在的缺點(diǎn)，本文采用了以下方法：網(wǎng)絡(luò)開始運(yùn)行時(shí)，首先通過(guò)類似文獻(xiàn)中的擴(kuò)散法將整個(gè)網(wǎng)絡(luò)劃分為若干個(gè)子區(qū)域，然后再在各個(gè)子區(qū)域內(nèi)隨機(jī)選取簇首節(jié)點(diǎn)，這樣可以保證簇首節(jié)點(diǎn)更加均勻地分布在整個(gè)網(wǎng)絡(luò)中。同時(shí)，設(shè)定節(jié)點(diǎn)剩余能量閾值Eth，每次選取簇首節(jié)點(diǎn)之前，對(duì)剩余能量低于閾值的節(jié)點(diǎn)采取休眠處理。這樣保證了簇首節(jié)點(diǎn)選取的可用性，有效地提高了網(wǎng)絡(luò)的生存時(shí)間。圖4為簇首節(jié)點(diǎn)形成流程圖。網(wǎng)絡(luò)開始運(yùn)行時(shí)，依然將節(jié)點(diǎn)工作時(shí)間按周期劃分為簇首節(jié)點(diǎn)建立階段t1和穩(wěn)定運(yùn)行時(shí)間t2。t1階段網(wǎng)絡(luò)首先在各個(gè)子區(qū)域內(nèi)隨機(jī)產(chǎn)生簇首節(jié)點(diǎn)，新簇首節(jié)點(diǎn)產(chǎn)生后廣播告知整個(gè)網(wǎng)絡(luò)。此時(shí)，普通節(jié)點(diǎn)在接收到信息后開始發(fā)送入簇信息，簇首節(jié)點(diǎn)則為其分配通信時(shí)隙。圖5為整個(gè)算法的流程圖，在建立新的簇首節(jié)點(diǎn)和傳輸網(wǎng)絡(luò)后，簇內(nèi)節(jié)點(diǎn)開始將數(shù)據(jù)信息發(fā)送給簇首節(jié)點(diǎn)，并在其內(nèi)部進(jìn)行數(shù)據(jù)融合后轉(zhuǎn)發(fā)給匯聚節(jié)點(diǎn)，網(wǎng)絡(luò)開始穩(wěn)定運(yùn)行。經(jīng)過(guò)t2后，網(wǎng)絡(luò)開始重新選取簇首節(jié)點(diǎn)，此時(shí)要注意，每個(gè)節(jié)點(diǎn)都將判斷自己的剩余能量，對(duì)低于閾值的采取休眠處理并廣播告知其他節(jié)點(diǎn)。

?

　　3 結(jié)語(yǔ)

　　在分析LEACH算法和無(wú)線傳感器網(wǎng)絡(luò)的能量模型的基礎(chǔ)上，本文提出了一種改進(jìn)算法。在隨機(jī)選取簇首節(jié)點(diǎn)之前，首先把網(wǎng)絡(luò)劃分為若干個(gè)子區(qū)域，這樣可以將簇首節(jié)點(diǎn)分步得更加均勻，同時(shí)設(shè)定剩余能量閾值Eth，在每次選取簇首節(jié)點(diǎn)之前對(duì)剩余能量低于Eth的節(jié)點(diǎn)進(jìn)行休眠處理，有效地提升了整個(gè)網(wǎng)絡(luò)的生命周期。