基于環分塊的能耗均衡分簇路由算法

汪漢新 洪思琴

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

關鍵詞：無線傳感器網絡;能耗均衡;分簇路由;環分塊;最佳路徑

中圖分類號： TP393.04

文獻標志碼：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 引言

無線傳感器網絡（Wireless Sensor Network， WSN）是由大量的傳感器節點以無線通信方式組成的一個多跳自組織網絡，其主要功能是對指定區域進行監測獲取數據，具有自組織、快速展開、動態拓撲等特點，在物聯網中有著廣泛的用途[1-2]。WSN中的傳感器節點一般由電池供電，應用場景比較惡劣，不能及時進行能量補給，因此設計能量高效的路由協議是WSN中研究的重要方面[3]。在無線傳感器網絡路由協議中，分簇路由算法相比平面路由算法具有更好的節能性，成為近年來研究的熱點[4]。

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

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

1 系統模型

1.1 網絡模型

網絡模型如圖1所示，N個節點均勻部署在半徑為R的圓形監測區域內，匯聚節點位于監測區域的中心;所有節點和匯聚節點部署后都是靜止的，能夠根據接收節點的距離來自動調整發射功率;監測區域內所有的節點同構，且每個節點都具有唯一的ID，節點的初始能量相同;監測區域劃分為等間距的同心圓環，且每環被均勻地劃分為若干個區塊，匯聚節點所在的環為第0環，由匯聚節點向外的環依次編號為1，2，…，M。

圖1中灰色區域為直傳區[13]，該區域內的節點不進行分簇，直接將采集到的信息傳輸給匯聚節點，可以減少分簇、簇內通信及數據融合等能耗，改善“熱區”問題。

1.2 能耗模型

采用經典的無線電能耗模型[14-15]，發送節點向相距為d的目標節點傳輸mbit數據的能耗由發射電路和功率放大電路能耗組成：

接收節點接收mbit數據能耗為：

簇頭對mbit的數據進行融合的能耗為：

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

2 算法描述

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

EBCR-RP通過簇頭的能耗均衡優化各環簇數目，能夠在非均勻分簇的基礎上，使網絡能耗更加均衡;使用傳統的概率公式選取簇頭的方式時，簇頭數目不固定且簇頭隨機分布，容易出現簇頭集聚的現象，導致網絡能耗不均衡，影響網絡的生命周期。為了避免該問題，EBCR-RP將每環均勻分區，并在每個區塊中選取一個節點擔任簇頭，進一步均衡了網絡能耗;計算最佳單跳距離，且在數據傳輸階段設計傳輸代價函數，尋找傳輸代價最小的數據傳輸路徑，能夠有效地降低網絡能耗，提高能量效率，改善網絡負載。

2.1 環間距的計算

監控區域首先被劃分為等間距的同心圓環。在多跳通信中，求得網絡能耗最低的單跳距離，然后將該距離作為同心圓環的環間距。

如圖2所示，第M環的節點通過多跳將mbit數據傳輸給第0環的節點，設每一跳的距離為dr。節點能耗由接收數據、融合數據和轉發數據的能耗組成：

其中：Esd表示發送數據的能耗;Erv表示接收數據的能耗;Eag表示融合數據的能耗。

整個傳輸過程的總能耗為：

為了求得使總能耗最低的單跳距離dopt，將總能耗對dr求導，得到最優單跳距離為：

本文將所求得的dopt作為同心圓環的環間距，對監控區域進行分環處理，匯聚節點所在的環為直傳區。

2.2 環分塊原則

在多跳通信中，簇頭除了簇內通信外，還要融合和轉發簇間數據，越靠近匯聚節點的簇頭需要轉發的數據越多，能耗越大，這樣會導致網絡中能耗不均衡，產生“熱區”問題。為了解決該問題，本文對直傳區以外的每環進行均勻分塊，且在每個區塊中選取一個節點來擔任簇頭，通過優化每環的簇數目，即每環的區塊數目，來均衡網絡能耗。由于簇頭的能耗遠遠大于普通節點的能耗，因此均衡網絡能耗可以體現在均衡各環簇頭的能耗上，算法通過讓每環簇頭的能耗相等，來計算出每環的簇數目，因而得到每環的區塊數目。

由網絡模型可知，監控區域劃分為M+1個環，區域半徑R=（M+1）dopt，則可求得整個區域的環數M。假設每環的簇頭均勻分布，ki表示第i環的簇頭數目，由于傳感器節點在監控區域是均勻分布的，則第i環的節點數目Ni為：

其中：λ1，λ2，…，λm-1為比例因子，當各環簇頭數目的選取比例遵循式（15），就可保證每環簇頭的能耗相等，這樣就保證了整個網絡的能耗均衡。各環簇的數目確定后，各環區塊的數目也就確定了，然后對每環進行均勻分區，并在每個區塊內選取能量最高的節點擔任簇頭，避免簇頭集聚的問題。

2.3 代價函數的設計

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

其中： j是i的中繼節點;Ej_residual為簇頭j的剩余能量;Eint為簇頭j的初始能量;Dist（j，sink）表示簇頭j到匯聚節點的距離;Dist（i， j）表示簇頭i和簇頭j之間的距離;d0表示通信半徑;α、 β、γ為加權因子。簇頭j可能在簇頭i的相鄰外環，也可能在相鄰內環，若簇頭j在相鄰外環，則Dist（j，sink）較大，傳輸代價較大，則j不作為i的中繼節點。如果簇頭j的剩余能量較高、與節點i的距離較近且距離匯聚節點也較近，那么傳輸代價較小，傳輸能耗較低，從而有效提高網絡的能量效率。

為了搜索數據傳輸代價最小的路徑，對簇頭進行編號{1，2，…，n}，匯聚節點編號為0，構成有向圖的頂點，通過式（16）可計算有向圖每個頂點的邊集，如式（17）所示：

其中G為代價函數矩陣，通過G可以知道任意兩點間的傳輸代價。

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

搜索算法的偽代碼如下：

其中，path記錄的下一跳節點是倒序的，因此尋找簇頭到匯聚節點的路徑時還需要作出棧操作。通過這個搜索過程，就能夠找到每個簇頭到匯聚節點傳輸代價最小的路徑，然后通過該路徑進行數據傳輸。

2.4 算法復雜度分析

EBCR-RP的時間開銷主要包括路由選擇和簇頭選擇兩個階段。在路由選擇階段，集合P中節點數為m，集合Q中節點數為n，并且m

3 實驗仿真及分析

為了驗證EBCR-RP能夠提高網絡的性能，本文在Matlab R2017a仿真平臺下，對EBCR-RP、FLCFP和IUCR算法進行了對比，仿真環境參數設置如表1所示，選取1%的節點擔任簇頭。

3.1 衡量指標

本文從網絡生命周期、能耗均衡性和網絡能量效率這三個方面來衡量網絡的性能。一般認為網絡中50%節點死亡時，網絡生命周期結束，所以將網絡中50%節點死亡時的輪數作為網絡的生命周期;設第一個節點死亡到最后一個節點死亡經歷的時間作為時間跨度，那么時間跨度大小代表了節點能量消耗的均衡度;網絡能量效率通過網絡能量消耗速率判斷。

3.2 網絡的生命周期

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

同時從圖3中還可以看出，EBCR-RP的時間跨度最小，IUCR算法其次，FLCFP最大，這說明本文EBCR-RP的能耗更加均衡。這是因為FLCFP沒有考慮整個網絡能耗均衡性，IUCR算法采用非均勻分簇和簇間多跳機制來均衡網絡的能耗;而本文EBCR-RP通過優化各環的簇數目以均衡網絡能耗，在非均勻分簇的基礎上使能耗更加均衡，并對網絡進行分塊，在每個區塊內選取一個節點擔任簇頭，避免了簇頭集聚問題，進一步均衡了網絡能耗。

3.3 網絡的剩余能量

通過網絡的剩余能量曲線來對比算法的能量效率，仿真結果如圖4所示。網絡的初始能量相同，從三種算法的剩余能量斜率來看，FLCFP>IUCR>本文EBCR-RP，剩余能量曲線斜率代表網絡能耗的高低，這表明EBCR-RP優化了網絡負載，提高了網絡能量效率。這是因為，EBCR-RP通過計算最優單跳距離降低了整個能耗，同時尋找能耗小的最佳數據傳輸路徑，有效降低了網絡能耗，優化了網絡的負載，提高了網絡能量效率。

4 結語

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

參考文獻 （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] 王冠，王瑞堯.基于簇頭優化的自供能無線傳感網絡路由算法[J].計算機應用，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] 李成法，陳貴海，葉懋，等.一種基于非均勻分簇的無線傳感器網絡路由協議[J].計算機學報，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] 王磊，謝彎彎，劉志中，等.非均勻分簇路由協議改進算法[J].計算機科學，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.