基于環(huán)分塊的能耗均衡分簇路由算法

汪漢新 洪思琴

摘 要：針對(duì)無線傳感器網(wǎng)絡(luò)（WSN）中節(jié)點(diǎn)能耗不均衡和能量效率低而影響網(wǎng)絡(luò)生命周期的問題，提出了基于環(huán)分塊的能耗均衡分簇路由算法（EBCR-RP）。首先，計(jì)算網(wǎng)絡(luò)能耗最低的單跳距離，并將其作為環(huán)間距;然后，優(yōu)化每環(huán)的簇?cái)?shù)目，并對(duì)每環(huán)進(jìn)行均勻分塊，且在每塊中選取能量最高的節(jié)點(diǎn)擔(dān)任簇頭，以均衡網(wǎng)絡(luò)能耗;最后，設(shè)計(jì)傳輸代價(jià)函數(shù)，搜索簇頭和匯聚節(jié)點(diǎn)之間數(shù)據(jù)的最佳傳輸路徑，以提高網(wǎng)絡(luò)能量效率。仿真結(jié)果表明，EBCR-RP與模糊理論簇形成協(xié)議（FLCFP）和改進(jìn)的非均勻分簇路由（IUCR）算法相比，網(wǎng)絡(luò)的生命周期分別延長(zhǎng)了51.4%和8.6%。EBCR-RP能夠有效地延長(zhǎng)網(wǎng)絡(luò)生命周期，均衡網(wǎng)絡(luò)能耗，提高能量效率。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);能耗均衡;分簇路由;環(huán)分塊;最佳路徑

中圖分類號(hào)： TP393.04

文獻(xiàn)標(biāo)志碼：A

Abstract： A novel Energy-Balanced Clustering Routing algorithm based on Ring Partition （EBCR-RP） was proposed to solve the network lifetime problem of unbalanced energy consumption and low energy efficiency in Wireless Sensor Network （WSN）. Firstly， the one-hop distance with minimize energy consumption was calculated and regarded as ring spacing. Secondly， the number of clusters was optimized and each ring was partitioned uniformly， and the node with highest energy in each block was chosen as cluster header to balance energy consumption. Finally， a cost function was designed to search optimal data transform path to improve energy efficiency. The simulation results show that network lifetime of EBCR-RP is increased by 51.4% and 8.6% compared with Fuzzy Logic Cluster Formation Protocol （FLCFP） and Improved Uneven Clustering Routing （IUCR） algorithms. EBCR-RP can effectively prolong network lifetime， balance energy consumption and improve energy efficiency.

Key words： Wireless Sensor Network （WSN）; energy balance; clustering routing; ring partition; optimal path

0 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network， WSN）是由大量的傳感器節(jié)點(diǎn)以無線通信方式組成的一個(gè)多跳自組織網(wǎng)絡(luò)，其主要功能是對(duì)指定區(qū)域進(jìn)行監(jiān)測(cè)獲取數(shù)據(jù)，具有自組織、快速展開、動(dòng)態(tài)拓?fù)涞忍攸c(diǎn)，在物聯(lián)網(wǎng)中有著廣泛的用途[1-2]。WSN中的傳感器節(jié)點(diǎn)一般由電池供電，應(yīng)用場(chǎng)景比較惡劣，不能及時(shí)進(jìn)行能量補(bǔ)給，因此設(shè)計(jì)能量高效的路由協(xié)議是WSN中研究的重要方面[3]。在無線傳感器網(wǎng)絡(luò)路由協(xié)議中，分簇路由算法相比平面路由算法具有更好的節(jié)能性，成為近年來研究的熱點(diǎn)[4]。

低能耗自適應(yīng)集簇分層（Low Energy Adaptive Clustering Hierarchy， LEACH）算法[5]是最早被提出的分簇路由算法，之后很多學(xué)者對(duì)其進(jìn)行了深入的研究。文獻(xiàn)[6]中提出了分布式節(jié)能分簇（Distributed Energy-Efficient Clustering， DEEC）算法，在選取簇頭時(shí)綜合考慮了節(jié)點(diǎn)的初始能量和剩余能量，能量越高的節(jié)點(diǎn)被選為簇頭的概率越大。文獻(xiàn)[7]中提出了模糊理論簇形成協(xié)議（Fuzzy Logic Cluster Formation Protocol， FLCFP），采用模糊理論優(yōu)化，綜合考慮節(jié)點(diǎn)剩余能量、與匯聚節(jié)點(diǎn)的距離、與鄰居節(jié)點(diǎn)的距離等因素來選取簇頭。雖然這類算法在簇頭選取階段有效地均衡了節(jié)點(diǎn)能耗，但在選取簇頭時(shí)隨機(jī)性很大，容易造成簇頭分布不均勻、簇頭數(shù)目不固定的問題。文獻(xiàn)[8]采用K-means方法對(duì)監(jiān)控區(qū)域的節(jié)點(diǎn)進(jìn)行均勻分簇，且選取每個(gè)簇中最靠近幾何中心的節(jié)點(diǎn)擔(dān)任簇頭，以解決簇頭分布不均勻的問題。文獻(xiàn)[9]中提出了間歇的簇頭選擇（Intermittent Cluster Head Selection， ICHS）算法，設(shè)置了一種新的概率公式來選取簇頭，能夠選出指定數(shù)目的簇頭，以解決簇頭數(shù)目不固定的問題;然而這些算法中簇頭直接與匯聚節(jié)點(diǎn)通信，當(dāng)兩者的距離較大時(shí)，數(shù)據(jù)傳輸能耗很大，因此這類算法不適用于大規(guī)模的無線傳感器網(wǎng)絡(luò)。文獻(xiàn)[10]中提出了多跳的低能耗自適應(yīng)集簇分層（Multiple-Hop Low Energy Adaptive Clustering Hierarchy， MH-LEACH）算法，該算法中簇頭不直接將數(shù)據(jù)傳輸給匯聚節(jié)點(diǎn)，而是通過中間節(jié)點(diǎn)進(jìn)行信息的轉(zhuǎn)發(fā)。雖然MH-LEACH在很大程度上降低了網(wǎng)絡(luò)能耗，但靠近匯聚節(jié)點(diǎn)的簇頭需要轉(zhuǎn)發(fā)大量數(shù)據(jù)，會(huì)導(dǎo)致網(wǎng)絡(luò)中能耗不均衡，產(chǎn)生熱區(qū)問題。文獻(xiàn)[11]中提出了能量高效的非均勻分簇（Energy-Efficient Uneven Clustering， EEUC）算法，利用非均勻分簇解決多跳模式下簇頭能耗不均衡的問題，但是該算法沒有考慮節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離等因素。針對(duì)該問題，文獻(xiàn)[12]中提出改進(jìn)的非均勻分簇路由（Improved Uneven Clustering Routing， IUCR）算法，在簇頭競(jìng)爭(zhēng)階段綜合考慮節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離、鄰居節(jié)點(diǎn)的數(shù)目以及能量消耗速度，并在非均勻分簇時(shí)引入競(jìng)爭(zhēng)半徑的概念;然而計(jì)算競(jìng)爭(zhēng)半徑需要考慮節(jié)點(diǎn)到匯聚節(jié)點(diǎn)之間的最大和最小距離值，當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，匯聚節(jié)點(diǎn)無法直接得到全局最大和最小值，導(dǎo)致簇建立階段能耗很大，且建立多跳路由時(shí)，沒有搜索傳輸代價(jià)最小的路徑，能量利用率較低。

本文針對(duì)網(wǎng)絡(luò)能耗不均衡、能量效率低的問題，提出了基于環(huán)分塊的能耗均衡分簇路由算法（Energy-Balanced Clustering Routing algorithm based on Ring Partition， EBCR-RP）。EBCR-RP計(jì)算了最佳單跳距離，通過均衡簇頭的能耗來均衡網(wǎng)絡(luò)能耗;不采用傳統(tǒng)的概率公式選取簇頭的方式，避免了簇頭分布不均勻和簇頭數(shù)目不固定的問題;構(gòu)建代價(jià)函數(shù)以尋找最佳數(shù)據(jù)傳輸路徑，降低通信能耗，提高能量效率。實(shí)驗(yàn)結(jié)果表明，與FLCFP和IUCR算法相比，EBCR-RP能夠有效延長(zhǎng)網(wǎng)絡(luò)生命周期，均衡網(wǎng)絡(luò)能耗，提高能量效率，改善網(wǎng)絡(luò)的性能。

1 系統(tǒng)模型

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

網(wǎng)絡(luò)模型如圖1所示，N個(gè)節(jié)點(diǎn)均勻部署在半徑為R的圓形監(jiān)測(cè)區(qū)域內(nèi)，匯聚節(jié)點(diǎn)位于監(jiān)測(cè)區(qū)域的中心;所有節(jié)點(diǎn)和匯聚節(jié)點(diǎn)部署后都是靜止的，能夠根據(jù)接收節(jié)點(diǎn)的距離來自動(dòng)調(diào)整發(fā)射功率;監(jiān)測(cè)區(qū)域內(nèi)所有的節(jié)點(diǎn)同構(gòu)，且每個(gè)節(jié)點(diǎn)都具有唯一的ID，節(jié)點(diǎn)的初始能量相同;監(jiān)測(cè)區(qū)域劃分為等間距的同心圓環(huán)，且每環(huán)被均勻地劃分為若干個(gè)區(qū)塊，匯聚節(jié)點(diǎn)所在的環(huán)為第0環(huán)，由匯聚節(jié)點(diǎn)向外的環(huán)依次編號(hào)為1，2，…，M。

圖1中灰色區(qū)域?yàn)橹眰鲄^(qū)[13]，該區(qū)域內(nèi)的節(jié)點(diǎn)不進(jìn)行分簇，直接將采集到的信息傳輸給匯聚節(jié)點(diǎn)，可以減少分簇、簇內(nèi)通信及數(shù)據(jù)融合等能耗，改善“熱區(qū)”問題。

1.2 能耗模型

采用經(jīng)典的無線電能耗模型[14-15]，發(fā)送節(jié)點(diǎn)向相距為d的目標(biāo)節(jié)點(diǎn)傳輸mbit數(shù)據(jù)的能耗由發(fā)射電路和功率放大電路能耗組成：

接收節(jié)點(diǎn)接收mbit數(shù)據(jù)能耗為：

簇頭對(duì)mbit的數(shù)據(jù)進(jìn)行融合的能耗為：

其中：Eelec表示發(fā)送單位比特?cái)?shù)據(jù)的能耗;εfs表示自由空間模式下單位比特的數(shù)據(jù)能耗;εamp表示多徑衰減模式下單位比特的數(shù)據(jù)能耗。d0=εfs/εamp是劃分空間模型的臨界值，稱為通信半徑：當(dāng)發(fā)送距離小于臨界值d0時(shí)，采用自由空間模式，發(fā)射功率呈d2衰減;當(dāng)發(fā)送距離大于或等于臨界值d0時(shí)，采用多徑衰減模式，發(fā)射功率呈d4衰減。EDA表示融合單位比特?cái)?shù)據(jù)的能耗。

2 算法描述

為了均衡整個(gè)網(wǎng)絡(luò)的能耗、提高能量效率、延長(zhǎng)網(wǎng)絡(luò)的生命周期，設(shè)計(jì)了一種基于環(huán)分塊的能耗均衡分簇路由算法（EBCR-RP）。EBCR-RP首先計(jì)算多跳通信中使網(wǎng)絡(luò)能耗最低的單跳距離，并將該距離作為環(huán)間距，對(duì)WSN的監(jiān)控區(qū)域進(jìn)行分環(huán)處理，匯聚節(jié)點(diǎn)所在的環(huán)為直傳區(qū)，該區(qū)域節(jié)點(diǎn)不進(jìn)行分簇，而是直接將信息傳輸給匯聚節(jié)點(diǎn);其次，通過讓直傳區(qū)外的簇頭的能耗相等，計(jì)算出各環(huán)簇?cái)?shù)目，并根據(jù)簇?cái)?shù)目對(duì)每環(huán)進(jìn)行均勻分塊;然后，在每個(gè)區(qū)塊中選取能量最高的節(jié)點(diǎn)來擔(dān)任簇頭，普通節(jié)點(diǎn)選擇離自身較近的簇頭成簇;最后，在數(shù)據(jù)傳輸階段，設(shè)計(jì)考慮傳輸距離、剩余能量和到匯聚節(jié)點(diǎn)距離的傳輸代價(jià)函數(shù)，尋找傳輸代價(jià)最小的數(shù)據(jù)傳輸路徑。

EBCR-RP通過簇頭的能耗均衡優(yōu)化各環(huán)簇?cái)?shù)目，能夠在非均勻分簇的基礎(chǔ)上，使網(wǎng)絡(luò)能耗更加均衡;使用傳統(tǒng)的概率公式選取簇頭的方式時(shí)，簇頭數(shù)目不固定且簇頭隨機(jī)分布，容易出現(xiàn)簇頭集聚的現(xiàn)象，導(dǎo)致網(wǎng)絡(luò)能耗不均衡，影響網(wǎng)絡(luò)的生命周期。為了避免該問題，EBCR-RP將每環(huán)均勻分區(qū)，并在每個(gè)區(qū)塊中選取一個(gè)節(jié)點(diǎn)擔(dān)任簇頭，進(jìn)一步均衡了網(wǎng)絡(luò)能耗;計(jì)算最佳單跳距離，且在數(shù)據(jù)傳輸階段設(shè)計(jì)傳輸代價(jià)函數(shù)，尋找傳輸代價(jià)最小的數(shù)據(jù)傳輸路徑，能夠有效地降低網(wǎng)絡(luò)能耗，提高能量效率，改善網(wǎng)絡(luò)負(fù)載。

2.1 環(huán)間距的計(jì)算

監(jiān)控區(qū)域首先被劃分為等間距的同心圓環(huán)。在多跳通信中，求得網(wǎng)絡(luò)能耗最低的單跳距離，然后將該距離作為同心圓環(huán)的環(huán)間距。

如圖2所示，第M環(huán)的節(jié)點(diǎn)通過多跳將mbit數(shù)據(jù)傳輸給第0環(huán)的節(jié)點(diǎn)，設(shè)每一跳的距離為dr。節(jié)點(diǎn)能耗由接收數(shù)據(jù)、融合數(shù)據(jù)和轉(zhuǎn)發(fā)數(shù)據(jù)的能耗組成：

其中：Esd表示發(fā)送數(shù)據(jù)的能耗;Erv表示接收數(shù)據(jù)的能耗;Eag表示融合數(shù)據(jù)的能耗。

整個(gè)傳輸過程的總能耗為：

為了求得使總能耗最低的單跳距離dopt，將總能耗對(duì)dr求導(dǎo)，得到最優(yōu)單跳距離為：

本文將所求得的dopt作為同心圓環(huán)的環(huán)間距，對(duì)監(jiān)控區(qū)域進(jìn)行分環(huán)處理，匯聚節(jié)點(diǎn)所在的環(huán)為直傳區(qū)。

2.2 環(huán)分塊原則

在多跳通信中，簇頭除了簇內(nèi)通信外，還要融合和轉(zhuǎn)發(fā)簇間數(shù)據(jù)，越靠近匯聚節(jié)點(diǎn)的簇頭需要轉(zhuǎn)發(fā)的數(shù)據(jù)越多，能耗越大，這樣會(huì)導(dǎo)致網(wǎng)絡(luò)中能耗不均衡，產(chǎn)生“熱區(qū)”問題。為了解決該問題，本文對(duì)直傳區(qū)以外的每環(huán)進(jìn)行均勻分塊，且在每個(gè)區(qū)塊中選取一個(gè)節(jié)點(diǎn)來擔(dān)任簇頭，通過優(yōu)化每環(huán)的簇?cái)?shù)目，即每環(huán)的區(qū)塊數(shù)目，來均衡網(wǎng)絡(luò)能耗。由于簇頭的能耗遠(yuǎn)遠(yuǎn)大于普通節(jié)點(diǎn)的能耗，因此均衡網(wǎng)絡(luò)能耗可以體現(xiàn)在均衡各環(huán)簇頭的能耗上，算法通過讓每環(huán)簇頭的能耗相等，來計(jì)算出每環(huán)的簇?cái)?shù)目，因而得到每環(huán)的區(qū)塊數(shù)目。

由網(wǎng)絡(luò)模型可知，監(jiān)控區(qū)域劃分為M+1個(gè)環(huán)，區(qū)域半徑R=（M+1）dopt，則可求得整個(gè)區(qū)域的環(huán)數(shù)M。假設(shè)每環(huán)的簇頭均勻分布，ki表示第i環(huán)的簇頭數(shù)目，由于傳感器節(jié)點(diǎn)在監(jiān)控區(qū)域是均勻分布的，則第i環(huán)的節(jié)點(diǎn)數(shù)目Ni為：

其中：λ1，λ2，…，λm-1為比例因子，當(dāng)各環(huán)簇頭數(shù)目的選取比例遵循式（15），就可保證每環(huán)簇頭的能耗相等，這樣就保證了整個(gè)網(wǎng)絡(luò)的能耗均衡。各環(huán)簇的數(shù)目確定后，各環(huán)區(qū)塊的數(shù)目也就確定了，然后對(duì)每環(huán)進(jìn)行均勻分區(qū)，并在每個(gè)區(qū)塊內(nèi)選取能量最高的節(jié)點(diǎn)擔(dān)任簇頭，避免簇頭集聚的問題。

2.3 代價(jià)函數(shù)的設(shè)計(jì)

在分簇路由算法中，數(shù)據(jù)傳輸階段的能耗很大，因此尋找傳輸代價(jià)較小的路徑十分重要，據(jù)此本文設(shè)計(jì)了一個(gè)傳輸代價(jià)函數(shù)，在匯聚節(jié)點(diǎn)和簇頭所組成的有向圖中搜索最佳的數(shù)據(jù)傳輸路徑，以提高網(wǎng)絡(luò)能量效率。該函數(shù)綜合考慮了三個(gè)因素：1）簇頭將采集的數(shù)據(jù)由外環(huán)向內(nèi)環(huán)傳輸;2）選擇剩余能量高的簇頭作為中繼節(jié)點(diǎn);3）選擇離自身較近的相鄰內(nèi)環(huán)簇頭作為中繼節(jié)點(diǎn)。

其中： j是i的中繼節(jié)點(diǎn);Ej_residual為簇頭j的剩余能量;Eint為簇頭j的初始能量;Dist（j，sink）表示簇頭j到匯聚節(jié)點(diǎn)的距離;Dist（i， j）表示簇頭i和簇頭j之間的距離;d0表示通信半徑;α、 β、γ為加權(quán)因子。簇頭j可能在簇頭i的相鄰?fù)猸h(huán)，也可能在相鄰內(nèi)環(huán)，若簇頭j在相鄰?fù)猸h(huán)，則Dist（j，sink）較大，傳輸代價(jià)較大，則j不作為i的中繼節(jié)點(diǎn)。如果簇頭j的剩余能量較高、與節(jié)點(diǎn)i的距離較近且距離匯聚節(jié)點(diǎn)也較近，那么傳輸代價(jià)較小，傳輸能耗較低，從而有效提高網(wǎng)絡(luò)的能量效率。

為了搜索數(shù)據(jù)傳輸代價(jià)最小的路徑，對(duì)簇頭進(jìn)行編號(hào){1，2，…，n}，匯聚節(jié)點(diǎn)編號(hào)為0，構(gòu)成有向圖的頂點(diǎn)，通過式（16）可計(jì)算有向圖每個(gè)頂點(diǎn)的邊集，如式（17）所示：

其中G為代價(jià)函數(shù)矩陣，通過G可以知道任意兩點(diǎn)間的傳輸代價(jià)。

在構(gòu)造好代價(jià)函數(shù)矩陣后，搜索每個(gè)簇頭到匯聚節(jié)點(diǎn)代價(jià)最小的數(shù)據(jù)傳輸路徑，其主要思想是：以匯聚節(jié)點(diǎn)為源點(diǎn)，通過搜索算法尋找其到各個(gè)簇頭的代價(jià)最小路徑，并將該路徑記錄下來，由于該搜索方式是反向搜索，所以目標(biāo)節(jié)點(diǎn)到源點(diǎn)的路徑還需要進(jìn)行出棧操作。搜索算法的具體過程：所有頂點(diǎn)分為已知最短路徑的頂點(diǎn)集合P和未知最短路徑的頂點(diǎn)集合Q，初始時(shí)，集合P中只有源點(diǎn)S（匯聚節(jié)點(diǎn)）一個(gè)頂點(diǎn)，設(shè)置源點(diǎn)到自己的最短路徑為0，即dis=0;在集合Q的所有頂點(diǎn)中，選擇一個(gè)離源點(diǎn)S最近的頂點(diǎn)u（簇頭）（即dis[u]最小，dis[u]表示頂點(diǎn)u到源點(diǎn)S的直接距離）加入到集合P中，然后觀察以u(píng)為起點(diǎn)的邊，對(duì)每一條邊進(jìn)行松弛操作（例如：存在一條從頂點(diǎn)u到頂點(diǎn)v的邊，e[u][v]表示這條邊的長(zhǎng)度，如果d[u]+e[u][v]

搜索算法的偽代碼如下：

其中，path記錄的下一跳節(jié)點(diǎn)是倒序的，因此尋找簇頭到匯聚節(jié)點(diǎn)的路徑時(shí)還需要作出棧操作。通過這個(gè)搜索過程，就能夠找到每個(gè)簇頭到匯聚節(jié)點(diǎn)傳輸代價(jià)最小的路徑，然后通過該路徑進(jìn)行數(shù)據(jù)傳輸。

2.4 算法復(fù)雜度分析

EBCR-RP的時(shí)間開銷主要包括路由選擇和簇頭選擇兩個(gè)階段。在路由選擇階段，集合P中節(jié)點(diǎn)數(shù)為m，集合Q中節(jié)點(diǎn)數(shù)為n，并且m

3 實(shí)驗(yàn)仿真及分析

為了驗(yàn)證EBCR-RP能夠提高網(wǎng)絡(luò)的性能，本文在Matlab R2017a仿真平臺(tái)下，對(duì)EBCR-RP、FLCFP和IUCR算法進(jìn)行了對(duì)比，仿真環(huán)境參數(shù)設(shè)置如表1所示，選取1%的節(jié)點(diǎn)擔(dān)任簇頭。

3.1 衡量指標(biāo)

本文從網(wǎng)絡(luò)生命周期、能耗均衡性和網(wǎng)絡(luò)能量效率這三個(gè)方面來衡量網(wǎng)絡(luò)的性能。一般認(rèn)為網(wǎng)絡(luò)中50%節(jié)點(diǎn)死亡時(shí)，網(wǎng)絡(luò)生命周期結(jié)束，所以將網(wǎng)絡(luò)中50%節(jié)點(diǎn)死亡時(shí)的輪數(shù)作為網(wǎng)絡(luò)的生命周期;設(shè)第一個(gè)節(jié)點(diǎn)死亡到最后一個(gè)節(jié)點(diǎn)死亡經(jīng)歷的時(shí)間作為時(shí)間跨度，那么時(shí)間跨度大小代表了節(jié)點(diǎn)能量消耗的均衡度;網(wǎng)絡(luò)能量效率通過網(wǎng)絡(luò)能量消耗速率判斷。

3.2 網(wǎng)絡(luò)的生命周期

網(wǎng)絡(luò)的生命周期是衡量一個(gè)網(wǎng)絡(luò)性能的重要指標(biāo)，對(duì)三種算法的網(wǎng)絡(luò)生命周期仿真結(jié)果如圖3所示。從圖3中可以看出，本文的EBCR-RP能有效地延長(zhǎng)網(wǎng)絡(luò)的生命周期。FLCFP網(wǎng)絡(luò)生命周期為839輪，EBCR-RP網(wǎng)絡(luò)生命周期為1271輪，比FLCFP提高了51.4%。雖然FLCFP采用模糊理論優(yōu)化，綜合考慮節(jié)點(diǎn)剩余能量、與匯聚節(jié)點(diǎn)的距離、與鄰居節(jié)點(diǎn)的距離等因素來選取簇頭;但是該算法中簇頭直接將數(shù)據(jù)傳輸給匯聚節(jié)點(diǎn)，當(dāng)網(wǎng)絡(luò)模型較大時(shí)網(wǎng)絡(luò)能耗很大。IUCR算法網(wǎng)絡(luò)生命周期為1170輪，EBCR-RP比IUCR算法提高了8.6%。這是因?yàn)楸疚挠?jì)算了最優(yōu)單跳距離，并采用了更有效的路由策略來尋找能耗更小的數(shù)據(jù)傳輸路徑，所以降低了網(wǎng)絡(luò)能耗，延長(zhǎng)了網(wǎng)絡(luò)生命周期。

同時(shí)從圖3中還可以看出，EBCR-RP的時(shí)間跨度最小，IUCR算法其次，F(xiàn)LCFP最大，這說明本文EBCR-RP的能耗更加均衡。這是因?yàn)镕LCFP沒有考慮整個(gè)網(wǎng)絡(luò)能耗均衡性，IUCR算法采用非均勻分簇和簇間多跳機(jī)制來均衡網(wǎng)絡(luò)的能耗;而本文EBCR-RP通過優(yōu)化各環(huán)的簇?cái)?shù)目以均衡網(wǎng)絡(luò)能耗，在非均勻分簇的基礎(chǔ)上使能耗更加均衡，并對(duì)網(wǎng)絡(luò)進(jìn)行分塊，在每個(gè)區(qū)塊內(nèi)選取一個(gè)節(jié)點(diǎn)擔(dān)任簇頭，避免了簇頭集聚問題，進(jìn)一步均衡了網(wǎng)絡(luò)能耗。

3.3 網(wǎng)絡(luò)的剩余能量

通過網(wǎng)絡(luò)的剩余能量曲線來對(duì)比算法的能量效率，仿真結(jié)果如圖4所示。網(wǎng)絡(luò)的初始能量相同，從三種算法的剩余能量斜率來看，F(xiàn)LCFP>IUCR>本文EBCR-RP，剩余能量曲線斜率代表網(wǎng)絡(luò)能耗的高低，這表明EBCR-RP優(yōu)化了網(wǎng)絡(luò)負(fù)載，提高了網(wǎng)絡(luò)能量效率。這是因?yàn)?，EBCR-RP通過計(jì)算最優(yōu)單跳距離降低了整個(gè)能耗，同時(shí)尋找能耗小的最佳數(shù)據(jù)傳輸路徑，有效降低了網(wǎng)絡(luò)能耗，優(yōu)化了網(wǎng)絡(luò)的負(fù)載，提高了網(wǎng)絡(luò)能量效率。

4 結(jié)語

針對(duì)無線傳感器網(wǎng)絡(luò)設(shè)計(jì)中能耗不均衡和能量效率低的問題，本文設(shè)計(jì)了一種基于環(huán)分塊的能耗均衡分簇路由算法（EBCR-RP）。EBCR-RP計(jì)算了最佳單跳距離，均衡了簇頭的能耗，且不采用傳統(tǒng)的概率公式選取簇頭的方式，避免了簇頭數(shù)目不固定和簇頭集聚的問題，同時(shí)設(shè)計(jì)傳輸代價(jià)函數(shù)來構(gòu)建最佳傳輸路徑以降低能耗。實(shí)驗(yàn)結(jié)果表明EBCR-RP的網(wǎng)絡(luò)性能得到了改善。本文算法只考慮了網(wǎng)絡(luò)能耗，并未考慮網(wǎng)絡(luò)時(shí)延問題，下一步將對(duì)如何降低網(wǎng)絡(luò)時(shí)延展開深入研究。

參考文獻(xiàn) （References）

[1] RAWAT P， SINGH K D， CHAOUCHI H， et al. Wireless sensor networks： a survey on recent developments and potential synergies[J]. Journal of Supercomputing， 2014， 68（1）：1-48.

[2] 王冠，王瑞堯.基于簇頭優(yōu)化的自供能無線傳感網(wǎng)絡(luò)路由算法[J].計(jì)算機(jī)應(yīng)用，2018，38（6）：1721-1725.（WANG G， WANG R Y. Routing algorithm based on cluster-head optimization for self-energized wireless sensor network[J]. Journal of Computer Applications， 2018， 38（6）：1721-1725.）

[3] USMAN M， HAR D， KOO I. Energy-efficient infrastructure sensor network for Ad Hoc cognitive radio network[J]. IEEE Sensors Journal， 2015， 16（8）：2775-2787.

[4] WARRIER M M， KUMAR A. Energy efficient routing in wireless sensor networks： a survey[C]// Proceedings of the 2016 International Conference on Wireless Communications， Signal Processing and Network. Piscataway， NJ： IEEE， 2016：1987-1992.

[5] HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An application specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications， 2002， 1（4）：660-670.

[6] QING L， ZHU Q， WANG M. Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J]. Computer Communications， 2006， 29（12）：2230-2237.

[7] MHEMED R， ASLAM N， PHILLIPS W， et al. An energy efficient fuzzy logic cluster formation protocol in wireless sensor networks [J]. Procedia Computer Science， 2012， 10（1）：255-262.

[8] PARK G Y， KIM H， JEONG H W， et al. A novel cluster head selection method based on k-means algorithm for energy efficient wireless sensor network[C]// Proceedings of the 2013 International Conference on Advanced Information Networking and Applications Workshops. Piscataway， NJ： IEEE， 2013：910-915.

[9] FAWZY A E， AMER A， SHOKAIR M， et al. Proposed intermittent cluster head selection scheme for efficient energy consumption in WSNs[C]// Proceedings of the 2017 Radio Science Conference. Piscataway， NJ： IEEE， 2017： 275-283.

[10] LEI Y， SHANG F J， LONG Z， et al. An energy efficient multiple-hop routing protocol for wireless sensor networks[C]// Proceedings of the 2018 International Conference on Intelligent Networks and Intelligent Systems. Piscataway， NJ： IEEE， 2008：147-150.

[11] 李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（1）：27-36.（LI C F， CHEN G H， YE M， et al. An uneven cluster based routing protocol for wireless sensor networks[J]. Chinese Journal of Computers， 2007， 30（1）：27-36.）

[12] 王磊，謝彎彎，劉志中，等.非均勻分簇路由協(xié)議改進(jìn)算法[J].計(jì)算機(jī)科學(xué)，2017，44（2）：152-156.（WANG L， XIE W W， LIU Z Z， et al. Improved algorithm for uneven clustering routing[J]. Computer Science， 2017， 44（2）：152-156.）

[13] TANESSAKULWATTANA S， PORNAVALAI C， CHAKRABORTY G. Adaptive multi-hop routing for wireless sensor networks[C]// Proceedings of the 2013 International Joint Conference on Computer Science and Software Engineering. Piscataway， NJ： IEEE， 2013：105-110.

[14] JANG S， KIM H Y， KIM N U， et al. Energy-efficient clustering scheme with concentric hierarchy[C]// Proceedings of the 2012 Radio Frequency and Microwave Conference. Piscataway， NJ： IEEE， 2012：79-82.

[15] HUYNH T T， DINH-DUC A V， TRAN C H. Delay-constrained energy-efficient cluster-based multi-hop routing in wireless sensor networks[J]. Journal of Communications & Networks， 2016， 18（4）：580-588.