基于貪婪算法的樹(shù)形WSN 低功耗路由算法

肖 劍，何志成，胡 欣，張 贊，袁 曄

（1.長(zhǎng)安大學(xué) 電子與控制工程學(xué)院，陜西 西安 710064；2.長(zhǎng)安大學(xué) 能源與電氣工程學(xué)院，陜西 西安 710064；3.寧夏回族自治區(qū)無(wú)線(xiàn)電監(jiān)測(cè)站，寧夏 銀川 750001）

0 引 言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)主要由大量具備無(wú)線(xiàn)通信能力的傳感器節(jié)點(diǎn)和少量基站組成，傳感器節(jié)點(diǎn)對(duì)相關(guān)監(jiān)測(cè)數(shù)據(jù)進(jìn)行采集，然后將數(shù)據(jù)無(wú)線(xiàn)傳輸給基站以便數(shù)據(jù)的后續(xù)處理和分析，從而使無(wú)線(xiàn)傳感器網(wǎng)絡(luò)實(shí)現(xiàn)對(duì)某一片區(qū)域的實(shí)時(shí)監(jiān)測(cè)。然而傳感器節(jié)點(diǎn)大多被安裝在人難以觸及的地方，使得傳感器節(jié)點(diǎn)難以維護(hù)，所以傳感器節(jié)點(diǎn)大都由電池進(jìn)行供電，而一旦電能耗盡，該傳感器節(jié)點(diǎn)會(huì)立即失效。因此，如何在能量有限的情況下使盡可能多的傳感器節(jié)點(diǎn)有盡可能長(zhǎng)的生命周期已成為無(wú)線(xiàn)傳感器網(wǎng)絡(luò)技術(shù)領(lǐng)域的重要研究方向。

針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)存在的能耗問(wèn)題，Heinzelman 等[1]提出了基于分簇路由協(xié)議的LEACH 算法，通過(guò)等概率隨機(jī)選取簇首的方式使整個(gè)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的能耗盡可能均衡，進(jìn)而使更多的節(jié)點(diǎn)有更長(zhǎng)的生命周期。但是LEACH 算法在選取簇首時(shí)，沒(méi)有考慮到節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)所處的位置以及節(jié)點(diǎn)密度，這就有可能使某些節(jié)點(diǎn)過(guò)快凋亡。Lindsey等[2]提出了PEGASIS 算法，該算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)逐個(gè)連接起來(lái)形成長(zhǎng)鏈，然后沿著長(zhǎng)鏈進(jìn)行數(shù)據(jù)傳輸，最后再將數(shù)據(jù)傳輸給基站。劉偉強(qiáng)等[3]針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的PEGASIS協(xié)議進(jìn)行了研究與改進(jìn)，該算法以基站為圓心將無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的監(jiān)測(cè)區(qū)域分成若干個(gè)幅度相等的扇形區(qū)域，然后分別在每個(gè)扇區(qū)內(nèi)形成通信樹(shù)，數(shù)據(jù)先由通信樹(shù)的樹(shù)葉傳輸?shù)綐?shù)根，然后樹(shù)根再傳輸給基站。該算法通過(guò)通信樹(shù)的傳輸方式有效降低了節(jié)點(diǎn)的傳輸能耗，但是均勻劃分扇區(qū)的策略可能導(dǎo)致某些扇區(qū)的節(jié)點(diǎn)都距離基站較遠(yuǎn)，使得這些扇區(qū)中節(jié)點(diǎn)的能量消耗過(guò)快。王海浪等[4]提出一種基于PEGASIS 的剩余能量距離分區(qū)（PEGASIS-REDP）協(xié)議，該算法在建立網(wǎng)絡(luò)連接時(shí)對(duì)網(wǎng)絡(luò)進(jìn)行均勻分區(qū)并分別在每個(gè)分區(qū)中單獨(dú)成鏈以降低傳輸鏈中差鏈的數(shù)量。該算法通過(guò)降低差鏈數(shù)量有效降低網(wǎng)絡(luò)的能耗，但是仍然無(wú)法避免傳輸鏈上出現(xiàn)差鏈而導(dǎo)致部分節(jié)點(diǎn)能量消耗過(guò)快。胡中棟等[5]提出一種雙層樹(shù)型高能效多鏈路由算法，該算法在成鏈時(shí)使基站附近的節(jié)點(diǎn)不入鏈以降低分鏈和鏈頭鏈的能耗，用啟發(fā)式算法優(yōu)化鏈的傳輸路徑；選取主鏈頭時(shí)綜合考慮節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)與基站的距離，在選取分鏈頭時(shí)綜合考慮了節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)與相鄰分鏈頭的距離。但是分鏈之間的傳輸距離過(guò)長(zhǎng)導(dǎo)致鏈頭能量消耗過(guò)快。安葳鵬等[6]提出基于改進(jìn)灰狼優(yōu)化算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)路由協(xié)議，該算法將無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的監(jiān)測(cè)區(qū)域進(jìn)行分區(qū)，先以基站為圓心將區(qū)域劃分為多個(gè)環(huán)帶，然后在環(huán)帶的基礎(chǔ)上進(jìn)行扇形劃分以降低節(jié)點(diǎn)的遠(yuǎn)距離傳輸能耗，再分別在每個(gè)分區(qū)中單獨(dú)成鏈，最后利用改進(jìn)的灰狼優(yōu)化算法選取簇首。然而該算法的分區(qū)方式可能導(dǎo)致部分扇區(qū)中節(jié)點(diǎn)過(guò)于分散，使得這些節(jié)點(diǎn)的能量消耗過(guò)快。

針對(duì)以上算法存在的問(wèn)題，本文提出基于貪婪算法的樹(shù)形WSN 低功耗路由算法，該算法引入樹(shù)的概念，并通過(guò)貪婪算法形成樹(shù)，然后基于傳輸距離最近原則進(jìn)行樹(shù)的融合，最后使所有樹(shù)的根延伸到基站。

1 網(wǎng)絡(luò)模型

1.1 系統(tǒng)模型

本文假定所有傳感器節(jié)點(diǎn)隨機(jī)分布在正方形區(qū)域內(nèi)，并有以下設(shè)定：

（1）無(wú)線(xiàn)傳感器網(wǎng)絡(luò)由多個(gè)傳感器節(jié)點(diǎn)和一個(gè)基站組成；

（2）基站的能量無(wú)限制；

（3）傳感器節(jié)點(diǎn)和基站都是靜止的，且它們的坐標(biāo)都是已知的；

（4）每個(gè)節(jié)點(diǎn)都有唯一固定的ID 號(hào)；

（5）任意節(jié)點(diǎn)都能進(jìn)行數(shù)據(jù)融合。

1.2 能耗模型

本文中網(wǎng)絡(luò)的能耗模型采用與文獻(xiàn)[4]相同的一階無(wú)線(xiàn)電能耗模型。

發(fā)送L比特?cái)?shù)據(jù)所消耗的能量計(jì)算公式為：

式中：Eelec為發(fā)射電路和接收電路的功耗；εfs為自由空間信道模型下放大器功率的放大倍數(shù)；εamp為多路徑衰減模型下放大器功率的放大倍數(shù)；d為發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的歐氏距離；為劃分空間模型的閾值。

接收L比特?cái)?shù)據(jù)所消耗的能量計(jì)算公式為：

對(duì)長(zhǎng)度為L(zhǎng)比特的數(shù)據(jù)包進(jìn)行融合時(shí)消耗的能量Eda的計(jì)算公式為：

2 基于貪婪算法的樹(shù)形WSN 低功耗路由算法

2.1 貪婪算法

貪婪算法（Greedy Algorithm）又稱(chēng)貪心算法，具有實(shí)現(xiàn)簡(jiǎn)單和時(shí)間復(fù)雜度低的特點(diǎn)[7-10]。它的基本思想是基于當(dāng)前最優(yōu)解做出選擇，也就是在每一步選擇時(shí)只考慮最有利的選擇，而不會(huì)綜合考慮多次選擇對(duì)結(jié)果的影響，即只考慮眼前的最優(yōu)選擇[11-13]。

2.2 數(shù)據(jù)傳輸階段

樹(shù)上的節(jié)點(diǎn)分為三類(lèi)，分別是樹(shù)根節(jié)點(diǎn)、樹(shù)干節(jié)點(diǎn)和葉節(jié)點(diǎn)。一棵樹(shù)只有一個(gè)樹(shù)根節(jié)點(diǎn)，樹(shù)上所有節(jié)點(diǎn)的數(shù)據(jù)全都朝著樹(shù)根節(jié)點(diǎn)的方向傳輸，樹(shù)根節(jié)點(diǎn)負(fù)責(zé)接收數(shù)據(jù)、融合數(shù)據(jù)和發(fā)送數(shù)據(jù)；樹(shù)上的葉節(jié)點(diǎn)是樹(shù)的端點(diǎn)，只負(fù)責(zé)發(fā)送數(shù)據(jù)；除了樹(shù)根節(jié)點(diǎn)和葉節(jié)點(diǎn)，樹(shù)上其余的節(jié)點(diǎn)全都是樹(shù)干節(jié)點(diǎn)，樹(shù)干節(jié)點(diǎn)負(fù)責(zé)接收數(shù)據(jù)、融合數(shù)據(jù)和發(fā)送數(shù)據(jù)。因此，樹(shù)根節(jié)點(diǎn)和樹(shù)干節(jié)點(diǎn)的能耗相對(duì)較高，葉節(jié)點(diǎn)的能耗相對(duì)較低。

本文算法的數(shù)據(jù)傳輸階段參考經(jīng)典PEGASIS 算法[2]的方式，如圖1 所示，在一棵樹(shù)上有5 個(gè)節(jié)點(diǎn)，分別是A1、A2、A3、A4和A5。其中A5為樹(shù)根節(jié)點(diǎn)，A2和A4為樹(shù)干節(jié)點(diǎn)，A1和A3為葉節(jié)點(diǎn)。該樹(shù)的數(shù)據(jù)傳輸方向是其他節(jié)點(diǎn)朝著節(jié)點(diǎn)A5的方向傳輸數(shù)據(jù)。在數(shù)據(jù)傳輸階段，節(jié)點(diǎn)A1先將數(shù)據(jù)傳輸給節(jié)點(diǎn)A2，節(jié)點(diǎn)A2將接收到的數(shù)據(jù)與自身采集到的數(shù)據(jù)進(jìn)行融合并得到一個(gè)相同長(zhǎng)度的數(shù)據(jù)包；然后節(jié)點(diǎn)A2和節(jié)點(diǎn)A3將數(shù)據(jù)傳輸給節(jié)點(diǎn)A4，節(jié)點(diǎn)A4將接收到的數(shù)據(jù)與自身采集到的數(shù)據(jù)進(jìn)行融合并得到一個(gè)相同長(zhǎng)度的數(shù)據(jù)包；最后節(jié)點(diǎn)A4將數(shù)據(jù)傳輸給節(jié)點(diǎn)A5，節(jié)點(diǎn)A5將接收到的數(shù)據(jù)與自身采集到的數(shù)據(jù)進(jìn)行融合并得到一個(gè)相同長(zhǎng)度的數(shù)據(jù)包。

圖1 數(shù)據(jù)傳輸過(guò)程

2.3 本文算法中的定義

定義1：若在路由協(xié)議下無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中某兩點(diǎn)（包括節(jié)點(diǎn)和基站）之間可直接傳輸數(shù)據(jù)，則將這兩點(diǎn)之間直接傳輸數(shù)據(jù)的路徑稱(chēng)為“可用路徑”，網(wǎng)絡(luò)中全部“可用路徑”構(gòu)成的集合稱(chēng)為“可用路徑集合”，并用S表示。

定義2：任意點(diǎn)Ai（包括節(jié)點(diǎn)和基站）以及從點(diǎn)Ai出發(fā)沿集合S中的路徑可以到達(dá)的全部點(diǎn)構(gòu)成一棵樹(shù)的全部點(diǎn)，一棵樹(shù)的全部點(diǎn)和集合S中連接這些點(diǎn)的全部路徑構(gòu)成一棵樹(shù)。

定義3：設(shè)樹(shù)Vi中與樹(shù)Vi外某一點(diǎn)Ai之間距離最近的點(diǎn)是Bi，則樹(shù)Vi與Ai之間的距離等于Bi與Ai之間的距離。

2.4 基于貪婪算法形成樹(shù)

基于貪婪算法，每個(gè)節(jié)點(diǎn)只能將數(shù)據(jù)傳輸給距離自身最近的點(diǎn)（包括節(jié)點(diǎn)和基站），此時(shí)集合S包含且僅包含每個(gè)節(jié)點(diǎn)到距離其自身最近的點(diǎn)（包括節(jié)點(diǎn)和基站）之間的路徑，將數(shù)據(jù)傳輸給距離最近的點(diǎn)能夠有效降低每個(gè)節(jié)點(diǎn)傳輸數(shù)據(jù)的能耗，通過(guò)這種方法使多個(gè)節(jié)點(diǎn)形成數(shù)據(jù)傳輸鏈，這種數(shù)據(jù)傳輸鏈就是樹(shù)[14-15]。

在本文中，將樹(shù)分為第一類(lèi)樹(shù)和第二類(lèi)樹(shù)，包含基站的樹(shù)為第一類(lèi)樹(shù)，不包含基站的樹(shù)為第二類(lèi)樹(shù)。在基于貪婪算法形成樹(shù)后，如果在樹(shù)中不存在兩個(gè)節(jié)點(diǎn)使得這兩個(gè)節(jié)點(diǎn)互為距離彼此最近的節(jié)點(diǎn)，那么理論上該樹(shù)可以無(wú)限長(zhǎng)并且能夠延伸到基站，這類(lèi)樹(shù)就是第一類(lèi)樹(shù)，第一類(lèi)樹(shù)的樹(shù)根為基站。如果在樹(shù)中存在兩個(gè)節(jié)點(diǎn)使得這兩個(gè)節(jié)點(diǎn)互為距離彼此最近的節(jié)點(diǎn)，則該樹(shù)上的其他節(jié)點(diǎn)都會(huì)朝著這兩個(gè)節(jié)點(diǎn)的方向傳輸數(shù)據(jù)，因此該樹(shù)有限長(zhǎng)且不與基站相連，這類(lèi)樹(shù)就是第二類(lèi)樹(shù)。

2.5 樹(shù)的融合

由于第二類(lèi)樹(shù)不與基站相連，第二類(lèi)樹(shù)上的節(jié)點(diǎn)無(wú)法沿集合S中的路徑將數(shù)據(jù)傳輸給基站，因此需要將第二類(lèi)樹(shù)轉(zhuǎn)化為第一類(lèi)樹(shù)。為了將第二類(lèi)樹(shù)轉(zhuǎn)化為第一類(lèi)樹(shù)，需要對(duì)樹(shù)進(jìn)行融合。對(duì)樹(shù)進(jìn)行融合的步驟是重復(fù)執(zhí)行如下步驟，直到第二類(lèi)樹(shù)的個(gè)數(shù)為零：找出與第二類(lèi)樹(shù)距離最近的點(diǎn)（包括節(jié)點(diǎn)和基站），若距離最近的點(diǎn)是基站，則將基站與該樹(shù)中距離基站最近的節(jié)點(diǎn)之間直接傳輸數(shù)據(jù)的路徑添加到集合S中，此時(shí)該樹(shù)轉(zhuǎn)化為第一類(lèi)樹(shù)；若距離最近的點(diǎn)是節(jié)點(diǎn)，則將該節(jié)點(diǎn)與該樹(shù)中距離該節(jié)點(diǎn)最近的節(jié)點(diǎn)之間直接傳輸數(shù)據(jù)的路徑添加到集合S中，此時(shí)兩棵樹(shù)融合成一棵樹(shù)。

當(dāng)?shù)诙?lèi)樹(shù)的個(gè)數(shù)降為零時(shí)，則表示網(wǎng)絡(luò)的數(shù)據(jù)傳輸路徑確定下來(lái)，然后就可以進(jìn)行數(shù)據(jù)傳輸了。進(jìn)行數(shù)據(jù)傳輸時(shí)，只能沿集合S中的路徑進(jìn)行數(shù)據(jù)傳輸，并且總是朝著基站的方向進(jìn)行數(shù)據(jù)傳輸。

2.6 能耗平衡

首先引入能量差額因子概念，節(jié)點(diǎn)Ai的能量差額因子Sub(Ai)的表達(dá)式為：

式中：N表示網(wǎng)絡(luò)中存活節(jié)點(diǎn)個(gè)數(shù)；Ej表示第j個(gè)存活節(jié)點(diǎn)Aj的剩余能量。

將網(wǎng)絡(luò)中的存活節(jié)點(diǎn)分為兩類(lèi)，能量差額因子大于閾值α的節(jié)點(diǎn)構(gòu)成集合U1，其余節(jié)點(diǎn)構(gòu)成集合U2。

為了避免某些節(jié)點(diǎn)能量消耗過(guò)快從而導(dǎo)致無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的監(jiān)測(cè)區(qū)域出現(xiàn)覆蓋空洞，在形成樹(shù)和融合樹(shù)時(shí)做如下處理：

（1）在利用貪婪算法形成樹(shù)時(shí)，為了使集合U1中的節(jié)點(diǎn)不成為樹(shù)干節(jié)點(diǎn)以降低能耗，不考慮集合U1中的節(jié)點(diǎn)而只將集合U2中的節(jié)點(diǎn)連接形成樹(shù)。在利用貪婪算法形成樹(shù)之后，在集合U2中分別為集合U1中的每一個(gè)節(jié)點(diǎn)尋找一個(gè)距離最近的節(jié)點(diǎn)，并將集合U1中的節(jié)點(diǎn)和在集合U2中與它們距離最近的節(jié)點(diǎn)之間直接傳輸數(shù)據(jù)的路徑添加至集合S中，使得集合U1中的節(jié)點(diǎn)都形成樹(shù)的葉節(jié)點(diǎn)以降低這些節(jié)點(diǎn)的能耗，至此所有存活節(jié)點(diǎn)都形成樹(shù)。

（2）在對(duì)樹(shù)進(jìn)行融合時(shí)，為了避免集合U1中的節(jié)點(diǎn)由葉節(jié)點(diǎn)變成樹(shù)干節(jié)點(diǎn)從而增大能耗，在計(jì)算樹(shù)與節(jié)點(diǎn)的距離時(shí)不考慮樹(shù)內(nèi)屬于集合U1的節(jié)點(diǎn)（計(jì)算樹(shù)與節(jié)點(diǎn)的距離時(shí)，假定樹(shù)內(nèi)屬于集合U1的節(jié)點(diǎn)不存在），在尋找距離第二類(lèi)樹(shù)最近的節(jié)點(diǎn)時(shí)同樣不考慮集合U1中的節(jié)點(diǎn)。

2.7 本文算法流程

本文算法的流程如下：

（1）計(jì)算每個(gè)存活節(jié)點(diǎn)的能量差額因子，然后根據(jù)能量差額因子將全部存活節(jié)點(diǎn)分為U1和U2兩個(gè)集合；

（2）為每個(gè)存活節(jié)點(diǎn)尋找距離最近的存活節(jié)點(diǎn)；

（3）利用貪婪算法將集合U2中的節(jié)點(diǎn)連接形成樹(shù)；

（4）將集合U1中的節(jié)點(diǎn)作為葉節(jié)點(diǎn)接入樹(shù)；

（5）進(jìn)行樹(shù)的融合，直到第二類(lèi)樹(shù)的個(gè)數(shù)降為零；

（6）開(kāi)始數(shù)據(jù)傳輸，首先是葉節(jié)點(diǎn)將數(shù)據(jù)傳輸給樹(shù)干節(jié)點(diǎn)，然后樹(shù)干節(jié)點(diǎn)沿著樹(shù)干向數(shù)根節(jié)點(diǎn)（即基站）傳輸數(shù)據(jù)；

（7）本輪數(shù)據(jù)傳輸完成，并統(tǒng)計(jì)死亡節(jié)點(diǎn)ID 號(hào)，若節(jié)點(diǎn)未全部死亡，轉(zhuǎn)向步驟（1）。

3 實(shí)驗(yàn)仿真及算法性能分析

3.1 仿真參數(shù)及性能指標(biāo)

為分析算法的性能，本文利用MATLAB 對(duì)算法進(jìn)行仿真，并將本文提出的算法與LEACH 算法[1]、PEGASIS 算法[2]和PEGASIS-REDP 算法[4]進(jìn)行對(duì)比。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的仿真模型：設(shè)定在400 m×400 m 正方形區(qū)域內(nèi)隨機(jī)分布100 個(gè)節(jié)點(diǎn)，在正方形區(qū)域的正中心有一個(gè)基站，本文算法中能量差額因子的閾值α取0.01 J。其他仿真參數(shù)見(jiàn)表1 所列。

表1 仿真參數(shù)

網(wǎng)絡(luò)剩余總能量的變化情況反映了網(wǎng)絡(luò)總體能量的消耗速度以及能量的利用率，而存活節(jié)點(diǎn)個(gè)數(shù)的變化情況反映了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的監(jiān)測(cè)區(qū)域覆蓋率和無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的生命周期。因此本文用網(wǎng)絡(luò)的剩余總能量和存活節(jié)點(diǎn)個(gè)數(shù)這兩項(xiàng)指標(biāo)來(lái)評(píng)估算法的性能。

3.2 樹(shù)的形成和融合過(guò)程

傳統(tǒng)PEGASIS 算法通過(guò)單鏈形式傳輸數(shù)據(jù)，導(dǎo)致傳輸鏈上差鏈較多從而使差鏈一端的節(jié)點(diǎn)能耗過(guò)高。本文算法首先利用貪婪算法形成樹(shù)，然后對(duì)樹(shù)進(jìn)行融合直到第二類(lèi)樹(shù)的數(shù)量降為0，以避免差鏈的出現(xiàn)；同時(shí)引入能量均衡機(jī)制，避免剩余能量過(guò)低的節(jié)點(diǎn)接收數(shù)據(jù)和融合數(shù)據(jù)。網(wǎng)絡(luò)中樹(shù)的形成以及樹(shù)的融合如圖2 所示。

圖2 樹(shù)的形成和樹(shù)的融合

3.3 網(wǎng)絡(luò)存活節(jié)點(diǎn)個(gè)數(shù)對(duì)比

不同算法下存活節(jié)點(diǎn)數(shù)隨輪數(shù)的變化情況如圖3 所示。

圖3 存活節(jié)點(diǎn)數(shù)隨輪數(shù)的變化情況

根據(jù)圖3 可知，本文算法下的網(wǎng)絡(luò)中首個(gè)節(jié)點(diǎn)死亡時(shí)間相較于LEACH、PEGASIS 和PEGASIS-REDP 算法分別延長(zhǎng)了89.1%、81.8%和68.3%。當(dāng)有節(jié)點(diǎn)死亡后，就可能造成無(wú)線(xiàn)傳感器網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域的覆蓋空洞，數(shù)據(jù)表明本文算法能夠有效延長(zhǎng)網(wǎng)絡(luò)在監(jiān)測(cè)區(qū)域無(wú)覆蓋空洞時(shí)的工作時(shí)長(zhǎng)。本文算法下的網(wǎng)絡(luò)中全部節(jié)點(diǎn)死亡時(shí)間相較于LEACH、PEGASIS 和PEGASIS-REDP 分別延長(zhǎng)了70.4%、27.1%和14.4%，表明本文算法能夠有效延長(zhǎng)網(wǎng)絡(luò)的生命周期。

3.4 網(wǎng)絡(luò)剩余總能量對(duì)比

不同算法下網(wǎng)絡(luò)的剩余總能量隨輪數(shù)的變化情況如圖4所示。

圖4 剩余總能量隨輪數(shù)的變化情況

從圖4 可以看出，本文算法下網(wǎng)絡(luò)的剩余總能量始終高于LEACH、PEGASIS 和PEGASIS-REDP 算法，并且當(dāng)網(wǎng)絡(luò)剩余總能量為50%時(shí)，LEACH、PEGASIS、PEGASIS-REDP和本文算法下的網(wǎng)絡(luò)分別運(yùn)行了269 輪、446 輪、468 輪和549 輪。這表明相較于其他三種算法，本文算法的能量利用率更高。

4 結(jié) 語(yǔ)

本文針對(duì)PEGASIS 算法存在的問(wèn)題，提出基于貪婪算法的樹(shù)形WSN 低功耗路由算法，該算法引入樹(shù)的概念，并利用貪婪算法將節(jié)點(diǎn)連接起來(lái)形成樹(shù)；并且為了降低剩余能量過(guò)低的節(jié)點(diǎn)的能耗，在形成樹(shù)時(shí)避開(kāi)剩余能量過(guò)低的節(jié)點(diǎn)，形成樹(shù)之后再將這些節(jié)點(diǎn)連接到樹(shù)上，然后基于距離最近原則進(jìn)行樹(shù)的融合，直到所有樹(shù)都以基站為樹(shù)根。通過(guò)算法的仿真結(jié)果對(duì)比，表明本文所提出的算法在延長(zhǎng)網(wǎng)絡(luò)生命周期、平衡節(jié)點(diǎn)能耗和提高能量利用率方面都明顯優(yōu)于LEACH、PEGASIS 和PEGASIS-REDP 算法。