孔國利　蘇玉

摘 要： 無線傳感網(wǎng)絡中低功耗自適應聚類分簇（LEACH）路由算法等概率選取簇首節(jié)點，容易導致整個網(wǎng)絡節(jié)點能量損耗出現(xiàn)極端化，減少網(wǎng)絡生存時間。為此，提出一種針對簇首節(jié)點選取和分簇的改進LEACH算法。該算法把整個網(wǎng)絡區(qū)域分為四個扇形區(qū)域，在每個區(qū)域內(nèi)獨立進行分簇路由；然后基站根據(jù)節(jié)點剩余能量和與基站的距離進行簇首節(jié)點選擇，節(jié)點根據(jù)簇首節(jié)點和基站接收信號強度選擇路由方式，以均衡網(wǎng)絡能量消耗。仿真結果表明，改進LEACH算法的網(wǎng)絡壽命是原有LEACH算法的150%，數(shù)據(jù)吞吐量提升了3倍。

關鍵詞： 無線傳感器網(wǎng)絡； 能量均衡； 扇形分簇； 簇首； 路由算法

中圖分類號： TN915?34； TP393.2 文獻標識碼： A 文章編號： 1004?373X（2017）05?0014?05

Abstract： The low energy adaptive clustering hierarchy （LEACH） routing algorithm for wireless sensor network selects the cluster head node by means of equal probability， which is easy to result in the extreme energy loss of the whole network nodes， and reduce the network lifetime. Therefore， an improved LEACH algorithm for the selection and clustering of the cluster head node is proposed. The whole network area is divided into four fan?shaped subareas with the algorithm to perform the clustering routing in each subarea independently. The cluster head node of the base station is selected according to the node residual energy and distance to the base station. The routing mode of the node is selected according to the cluster head node and the received signal strength of the base station to balance the network energy consumption. The simulation results show that the network lifetime of the improved LEACH algorithm is 150% of the original LEACH algorithm， and its data throughout is increased by three times.

Keywords： wireless sensor network； energy balance； fan?shaped clustering； cluster head； routing algorithm

0 引 言

無線傳感網(wǎng)絡是由分布式部署的微型傳感器節(jié)點組成的自組織網(wǎng)絡，其節(jié)點數(shù)量巨大，部署區(qū)域和環(huán)境復雜，被廣泛應用于實時車輛監(jiān)控、智能家居、森林防火防災等方面。其中，傳感器節(jié)點體積微小，配置的電池能量、計算能力和存儲能力有限，因此，如何均衡網(wǎng)絡能耗，提升網(wǎng)絡生存時間是合理有效設計無線傳感網(wǎng)絡的重要課題[1?2]。一般來說，無線傳感器網(wǎng)絡的路由算法應該具有能量優(yōu)先，基于局部的拓撲結構，以數(shù)據(jù)為中心的特點。現(xiàn)在國內(nèi)外已經(jīng)提出了很多經(jīng)典的無線傳感器網(wǎng)絡路由算法，有以數(shù)據(jù)中心為主的[3]，有以數(shù)據(jù)傳輸質(zhì)量為主的[4]，有以節(jié)點地理位置信息為主的[5]等，其中以網(wǎng)絡構成的結構劃分的，分為平面路由算法和分層路由算法。分層路由最經(jīng)典的算法為LEACH（Low Energy Adaptive Clustering Hierarchy）算法。LEACH算法在數(shù)據(jù)匯聚、拓撲適應和能量效率方面具有明顯的優(yōu)勢。

現(xiàn)有大量文獻對LEACH算法進行改進，以提升其性能。文獻[5]提出并對比了三種通過把節(jié)點自身的位置坐標和當前能量狀況匯報給基站，基站根據(jù)這些因素選取簇首的方法，但對于地理位置的獲取會消耗很大能量，同時沒有考慮到鏈首個數(shù)占整體節(jié)點總數(shù)的比例，導致不均衡。文獻[6]提出了簇首多跳算法，使得簇首之間形成一個多跳的最優(yōu)路徑，減少簇首的能量消耗，但是延長了路徑，從而使數(shù)據(jù)傳輸過程加長，時效性變?nèi)?。文獻[7]提出引入簇成員數(shù)門限和合并極小簇的方法，首先估計簇首能量消耗的情況，然后人為的控制節(jié)點休眠的狀況來配合簇首消息的傳送，雖然能量消耗方面得到改善，但是在時效性方面沒有充分考慮。文獻[8]考慮節(jié)點剩余能量和通信半徑，選擇簇首節(jié)點以減少整個傳感網(wǎng)絡中簇首節(jié)點的數(shù)目，延長網(wǎng)絡整體壽命。

本文考慮到能量消耗均衡性，網(wǎng)絡壽命長短因素，提出基于扇形分簇的路由算法，縮小分簇范圍進行通信。然后，根據(jù)剩余能量、通信距離選取簇首節(jié)點，均衡能量消耗，延長網(wǎng)絡壽命。

1 系統(tǒng)模型

LEACH示意圖如圖1所示，假定其覆蓋一定區(qū)域的無線傳感網(wǎng)絡，并且有以下假設[9]：

假設1：基站與整個網(wǎng)絡的位置保持不變，基站與整個網(wǎng)絡中的節(jié)點距離較遠。

假設2：每個節(jié)點有著同樣性質(zhì)、有限的能量、與基站直接通信的特性。

假設3：節(jié)點計算能力較強，支持TDMA。

假設4：WSN節(jié)點發(fā)送信息的功率可以變化、調(diào)整。

節(jié)點間的數(shù)據(jù)通信采用一階無線電模型（First Order Radio Model），通信模型如圖2所示。

這種通信模式有比較成熟的能量消耗計算體系。該模型假設WSN節(jié)點有著相同的計算能力，有限的能量；電信號在不同方向上的路徑損耗一樣。當傳輸長為m bit的信息經(jīng)過距離[d]的過程中，節(jié)點的能量消耗如下：

數(shù)據(jù)發(fā)送：

[ETx（m，d）=Eelec?m+εfs?m?d2， d

數(shù)據(jù)接收：

[ERx=Eelec] （2）

數(shù)據(jù)融合：

[EGx=Eg?m] （3）

式中：[εfs]是信號放大器的放大倍數(shù)；[Eelec]是發(fā)送和接收信息時對應的數(shù)據(jù)處理模塊消耗的能量。由于傳感器節(jié)點間距離不同，傳播環(huán)境迥異，因此，傳播相同數(shù)據(jù)量的能量消耗不同。式（1）中不同的能量消耗表征不同傳播距離和傳播環(huán)境對能量消耗的影響。其中，[d]是數(shù)據(jù)通信的距離；[d0]是節(jié)點的通信半徑；[εmp]是信道傳輸能量衰減系數(shù)，通信傳輸距離越短，能量消耗越少。

2 LEACH算法流程

LEACH算法將傳感器節(jié)點分為若干個簇，每個簇內(nèi)節(jié)點的信息匯聚至簇首節(jié)點后，由簇首節(jié)點轉(zhuǎn)發(fā)至基站。匯聚轉(zhuǎn)發(fā)的工作方式能夠提升LEACH算法的能量效率。此外，由于簇首節(jié)點的能量消耗較大，各個節(jié)點根據(jù)剩余能量狀況輪流擔任簇首節(jié)點，提升網(wǎng)絡整體壽命[10]。

LEACH算法以循環(huán)也就是“輪（round）”的方式執(zhí)行簇的構造過程。每輪都由兩階段組成：初始化簇的建立階段和數(shù)據(jù)傳輸階段，具體時序示意圖如圖3所示。

2.1 初始化簇階段

初始化簇階段分為簇首選取和成簇過程兩個步驟。

Step1：簇首選取。網(wǎng)絡中所有的節(jié)點會隨機產(chǎn)生一個在0～1之間的數(shù)，網(wǎng)絡會設定一個門限值[T（n）]如式（4）所示，基站會把節(jié)點產(chǎn)生的隨機數(shù)與設定的門限[T（n）]進行比較，會選擇小于[T（n）]的節(jié)點作為簇首。

[T（n）=Q1-Q?（lmod1Q） ， n∈G0， otherwise] （4）

式中：[Q]為每輪簇首節(jié)點與[n]個節(jié)點的比率；[l]為第[l]輪；[G]為在之前的幾輪中沒有被選為簇首節(jié)點的總和。

Step2：成簇過程。節(jié)點被選為簇首后會向其他所有節(jié)點廣播自己被選為簇首的消息。其他節(jié)點在接收到消息之后，根據(jù)最小能量的原則通過比較，判斷發(fā)送這些消息的節(jié)點的功率大小來選擇加入到相應的簇。一般節(jié)點會選擇接收到的功率越大的簇首節(jié)點形成的簇；然后發(fā)送自己要加入相應簇的消息給相應的簇首節(jié)點。簇首節(jié)點收到消息后會給節(jié)點一個回應，并將該節(jié)點加入自己的路由表中。

2.2 數(shù)據(jù)發(fā)送和接收

當所有傳感器節(jié)點都形成簇之后，節(jié)點間采用TDMA方式發(fā)送數(shù)據(jù)。各個節(jié)點的數(shù)據(jù)在簇頭節(jié)點處融合，然后由簇頭節(jié)點轉(zhuǎn)發(fā)給基站。一個簇分配方案維持數(shù)據(jù)通信一段時間后，重新進行下一輪的簇分配，以避免對簇首節(jié)點的能量過度消耗，提升網(wǎng)絡整體壽命。

3 改進LEACH算法原理

從LEACH算法中可知，以輪的方式等概率的選取簇首，并沒有考慮剩余能量的因素。對于剩余能量不同的節(jié)點當選簇首的幾率是一樣的。如果剩余能量偏低的節(jié)點被選為簇首，很容易耗盡能量，降低整個網(wǎng)絡的壽命。此外，在LEACH算法中，節(jié)點根據(jù)接收信號的強度來選擇簇首。若該節(jié)點距離簇首節(jié)點較遠，路徑損耗較高[11]，因此，節(jié)點能量會過早消耗而死亡，導致網(wǎng)絡的通信出現(xiàn)黑洞。

針對這些缺點，綜合考慮節(jié)點的能量和整個網(wǎng)絡信息傳輸?shù)募皶r性，本文在基于LEACH算法的基礎上提出了改進LEACH算法。該算法把整個網(wǎng)絡劃分為四個扇形分區(qū)；基站在每個扇形分區(qū)中通過比較每個節(jié)點產(chǎn)生的隨機數(shù)和節(jié)點的剩余能量選擇簇首，接著基站公布簇首的消息，節(jié)點根據(jù)接收到的該區(qū)域的消息強度、與簇首和基站的距離比較選擇加入簇還是選擇直接與基站進行通信。

3.1 扇形結構模型

由于覆蓋區(qū)域為圓形時，傳感器節(jié)點間的最大距離比覆蓋區(qū)域為其他形狀時要小，本文假定圓形覆蓋區(qū)域，基站位于圓形覆蓋區(qū)域中心。同時，為了進一步縮小節(jié)點間的最大距離，同時減少由于網(wǎng)絡中節(jié)點死亡而重新分簇帶來的通信開銷，改進LEACH算法將圓形覆蓋區(qū)域分為4個扇區(qū)，如圖4所示。在每個扇區(qū)內(nèi)，分別進行LEACH算法路由。選定某個參考點后，4個扇區(qū)分別記為扇區(qū)編號num={1，2，3，4}，圓心角[θ=π2。]

3.2 扇區(qū)編號確定

劃分好區(qū)域后，所有傳感器節(jié)點進行分簇時需要確定每個節(jié)點所在的扇區(qū)編號及在扇區(qū)的具體位置，方法如下：

（1） 計算節(jié)點的極坐標角度。所有的節(jié)點需要將自己的位置信息與ID信息發(fā)送給基站，基站根據(jù)正切函數(shù)特征進行計算。把圓放到直角坐標系中，圓心[O]的坐標為（0，0），設任意一個點[i]的坐標為[（x（i），y（i）），]如圖5所示。

（2） 確定節(jié)點所在區(qū)域。將節(jié)點[i]對應的角度[α]與圓心角[θ]相除，得到整數(shù)[k（i），]比較[k（i）]與已經(jīng)劃分好區(qū)域的編號[num（n），]獲得節(jié)點[i]所在的區(qū)域編號[k（i），]即：

所有節(jié)點的極坐標角度和扇區(qū)編號構成一個矩陣，記為Loc，其中，[Loc=（i）={a（i），k（i）}。]

3.3 簇首選取

改進LEACH算法同時考慮通信距離和節(jié)點剩余能量來選擇簇首節(jié)點，并且在每一輪都會進行選取，流程圖如圖6所示。

簇首節(jié)點選擇過程分為兩步：

Step1：先按照LEACH算法機制，比較每個節(jié)點產(chǎn)生的隨機數(shù)與網(wǎng)絡給定的閾值[T（n），]在低于閾值的節(jié)點中選擇簇首節(jié)點。

Step2：在第一步選擇的節(jié)點中，綜合考慮節(jié)點的能量和與基站的距離，進行簇首節(jié)點選擇。具體選擇的準則為：

[Q=Edis] （9）

式中：[E]為節(jié)點的剩余能量；dis為節(jié)點與基站之間的距離。由式（1）可以看出，距離dis也與[Q]成反比，距離基站越遠的節(jié)點消耗的能量更大，因此該點被選為簇頭的幾率也比較小。

綜上所述，剩余能量越多，離基站距離越近的節(jié)點成為最終簇首節(jié)點的概率越大。

3.4 分簇通信過程

當簇首節(jié)點選定以后，基站會向各個扇區(qū)廣播相應區(qū)域簇首節(jié)點的消息。各個扇區(qū)內(nèi)對應的節(jié)點知道自己為簇首后，就會在自己的覆蓋區(qū)域內(nèi)發(fā)布自己是簇首的消息。各個扇區(qū)的普通節(jié)點會根據(jù)自己接收到的來自簇首的信息和接收到來自基站的信息強度和相應的距離判斷是選擇加入簇還是直接與基站進行通信。當選擇加入簇后，會給相應的簇首發(fā)送消息，同時簇首也會相應的給回應。對于不加入簇中的節(jié)點，就只會把測量的消息直接發(fā)送給基站，流程圖如圖7所示。

在每輪傳輸數(shù)據(jù)時，各個區(qū)域簇內(nèi)的節(jié)點會把測量到的信息數(shù)據(jù)發(fā)送到相應的簇首，簇首節(jié)點傳送到基站，而簇外的節(jié)點會把消息直接傳輸給基站。當節(jié)點為普通節(jié)點或者是簇外節(jié)點時，能量消耗只包括節(jié)點將數(shù)據(jù)發(fā)送的能量；當節(jié)點為簇首節(jié)點時，能量消耗為節(jié)點接收、融合以及發(fā)送數(shù)據(jù)的能量總和。

4 仿真結果分析

為了評估改進LEACH算法的性能，使用Matlab進行仿真，重點分析經(jīng)過一定輪數(shù)網(wǎng)絡節(jié)點的死亡個數(shù)和網(wǎng)絡傳輸數(shù)據(jù)的情況[12]。假定基站固定且位于監(jiān)測區(qū)域的最中心，遠離傳感器節(jié)點；所有的節(jié)點計算能力和能量容量一樣；節(jié)點具有與其他節(jié)點和基站進行通信的能力；節(jié)點的位置固定不動。同時對比了原有的兩種改進算法LEACH1，LEACH2。其中，LEACH1是由文獻[13]提出的只針對簇首選取改進的算法，采用粒子群算法進行分區(qū)，分別在各個區(qū)域通過節(jié)點剩余能量選取簇首的方法。LEACH2是文獻[14]提出的結合LEACH與PEGASIS的改進算法，通過對節(jié)點分區(qū)分簇，把不同簇的簇首連成鏈進行通信的方法。

仿真中假定基站坐標為（0，0），數(shù)據(jù)包的長度為3 000 b，控制包的長度較小，可以忽略不計，其他的實驗參數(shù)設置如表1所示。

首先對兩種原有算法和LEACH算法在不同輪數(shù)死亡節(jié)點總數(shù)的統(tǒng)計進行比較，具體顯示結果如圖8所示。

從圖8可以看出，當運行到500輪左右時，四種算法都出現(xiàn)了節(jié)點開始死亡的現(xiàn)象。LEACH和LEACH2算法的節(jié)點死亡速度比較快。經(jīng)過1 500輪左右，使用這兩種算法的無線傳感網(wǎng)絡節(jié)點死亡率達到最大限度。到將近2 000輪左右時，兩種算法的節(jié)點死亡速度接近平緩，并將近全部死亡。這是由于這兩種算法沒有考慮節(jié)點剩余能量的影響，導致部分節(jié)點過早死亡。而改進LEACH算法和LEACH1算法的節(jié)點死亡狀況在一開始比較平緩，到1 300輪左右時速度變快，但都沒有LEACH快，并且在LEACH接近死亡時，改進算法中還存活將近20個節(jié)點?？梢钥闯?，改進算法比原有算法更好地延長了網(wǎng)絡壽命，并且比LEACH算法在節(jié)點存活概率方面提升了20%，節(jié)約了能量的消耗，延長了網(wǎng)絡的生命周期。

幾種算法數(shù)據(jù)傳輸性能的比較如圖9所示。

由圖9可知，隨著輪數(shù)的增大，四種算法數(shù)據(jù)傳輸?shù)牧慷荚谠黾?，并且改進LEACH算法與原有算法的數(shù)據(jù)傳輸差距也隨之增大，當?shù)? 000輪左右時，改進算法的數(shù)據(jù)傳輸量是LEACH算法的3倍。LEACH算法和改進算法LEACH2在1 500輪左右時，數(shù)據(jù)傳輸量的增加趨于穩(wěn)定，而改進算法和另外一種算法LEACH1的數(shù)據(jù)傳輸量一直在快速增加，當?shù)? 000輪左右時，LEACH和LEACH2算法已經(jīng)達到了最大數(shù)據(jù)傳輸量，而改進算法的數(shù)據(jù)傳輸量還在增加，并且將要達到LEACH算法的4倍，明顯提高了數(shù)據(jù)傳輸效率。因此，本文提出的改進算法通過合理使用節(jié)點能量，能夠提高網(wǎng)絡有效數(shù)據(jù)的傳輸量。

5 結 語

本文綜合考慮了扇形分區(qū)和節(jié)點剩余能量，對LEACH算法進行改進。仿真結果表明，改進LEACH算法能夠提升約150%的網(wǎng)絡壽命，同時能夠傳輸4倍于對比算法的數(shù)據(jù)量；該算法在均衡了能量消耗的同時還增強了網(wǎng)絡接收數(shù)據(jù)信息的及時性，提高了網(wǎng)絡的利用率，增加了網(wǎng)絡生存時間。

參考文獻

[1] 蘇儉華，劉宇紅，徐躍州.一種基于LEACH的無線傳感器網(wǎng)絡路由算法及仿真[J].通信技術，2014，47（1）：60?63.

[2] MAMUN Q. A qualitative comparison of different logical topologies for wireless sensor networks [J]. Sensors， 2012， 12（11）： 14887?14913.

[3] 任克強，余建華，謝斌.基于改進LEACH的多簇頭分簇路由算法[J].電視技術，2015，39（13）：69?71.

[4] MCBRIDE D， CROFT T N， CROSS M， et al. Optimization of a CFD： heap leach model and sensitivity analysis of process operation [J]. Minerals engineering， 2014， 63（8）： 57?64.

[5] 周萌，陳躍東，陳孟元.能耗最優(yōu)的LEACH協(xié)議改進[J].計算機工程與應用，2014，50（23）：82?86.

[6] GOETZ E R， RIEFLER R G. Performance of steel slag leach beds in acid mine drainage treatment [J]. Chemical engineering journal， 2014， 240（6）： 579?588.

[7] 陳曉娟，王卓，吳潔.一種基于LEACH的改進WSN路由算法[J].傳感技術學報，2013，26（1）：116?121.

[8] HU Songhua， HAN Jianghong， WEI Xing， et al. A multi?hop heterogeneous cluster?based optimization algorithm for wireless sensor networks [J]. Wireless networks， 2015， 21（1）： 57?65.

[9] 王夢瑩，王鑫，蔣華.基于簇首成鏈的低能耗層次路由協(xié)議[J].計算機科學，2015，42（11）：144?148.

[10] 蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡非均勻分簇路由協(xié)議[J].軟件學報，2012，23（5）：1222?1232.

[11] 吉正洵，江冰，李麗芳，等.采用改進算法對無線網(wǎng)絡節(jié)能優(yōu)化仿真研究[J].計算機仿真，2015，32（6）：266?270.

[12] 張巖.非變換簇的WSN分簇路由算法[J].現(xiàn)代電子技術，2015，38（18）：26?29.

[13] YANG Y， WANG X， WANG M， et al. Recovery of iron from red mud by selective leach with oxalic acid [J]. Hydrometallurgy， 2015， 157： 239?245.

[14] 王鑫，王夢瑩，蔣華.一種基于簇首成鏈的分層分簇路由協(xié)議[J].微電子學與計算機，2014（10）：9?12.