基于功率控制與分簇數(shù)量的LEACH優(yōu)化算法

齊 華, 呂 龍, 陳 紅

(1.西安工業(yè)大學 電子信息工程學院，陜西 西安 710021； 2.武警工程大學 信息工程系，陜西 西安 710086)

0 引 言

合理高效地使用能量，是無線傳感器網(wǎng)絡[1,2](wireless sensor networks,WSNs)需要首先考慮的問題。近年來，國內(nèi)外學者從網(wǎng)絡的拓撲結(jié)構(gòu)出發(fā)，研究出各種均衡網(wǎng)絡能量消耗的算法，較為經(jīng)典的有低能量自適應聚簇分層(low energy adaptive clustering hierarchy,LEACH)[3]算法，該算法讓節(jié)點輪流當選簇頭，共同分擔簇頭節(jié)點的高能耗，實現(xiàn)均衡能耗的效果，但不足之處在于算法沒有考慮節(jié)點的發(fā)射功率、節(jié)點剩余能量和位置、 簇頭數(shù)量不穩(wěn)定等問題，文獻[4]提出一種基于距離劃分和剩余能量的分簇算法，以網(wǎng)格內(nèi)節(jié)點到匯聚節(jié)點的距離為標準，以剩余能量大小確定簇頭節(jié)點，使簇頭節(jié)點分布更合理；文獻[5]提出了一種基于剩余能量和節(jié)點度的分簇算法，在簇頭選取過程中，綜合考慮所有節(jié)點剩余能量和節(jié)點度，避免能量低的節(jié)點當選為簇頭；文獻[6]提出一種自適應功率控制及調(diào)度算法，通過監(jiān)聽鄰居簇首調(diào)度以及功率等級表來自適應地安排簇內(nèi)節(jié)點的發(fā)射功率級和時隙，減少簇間干擾和發(fā)射功率浪費的現(xiàn)象。

本文提出一種自適應功率控制與優(yōu)化分簇數(shù)量的改進路由算法 (LEACH-power control optional cluster，LEACH-PCOC)，綜合考慮節(jié)點的能量狀態(tài)、節(jié)點的位置、節(jié)點的發(fā)射功率和簇頭數(shù)的變化4個因素，最終實現(xiàn)網(wǎng)絡能量有效利用，延長網(wǎng)絡壽命。

1 LEACH-PCOC算法的實現(xiàn)思路

1)使用虛擬單元格劃分監(jiān)測區(qū)域。針對LEACH算法在簇的建立階段沒有考慮節(jié)點的分布情況以及節(jié)點的數(shù)據(jù)冗余度問題，本文通過引入虛擬單元格劃分監(jiān)測區(qū)域，將單元格內(nèi)的節(jié)點能量作為簇頭競選的條件，優(yōu)化簇的建立，減少數(shù)據(jù)冗余度，提高網(wǎng)絡生存周期。

2)優(yōu)化簇頭數(shù)目選取方式。若網(wǎng)絡中的簇頭數(shù)目過少，將會增加節(jié)點通信引起的能量損耗；若簇頭數(shù)目過多，每輪中總的耗能將會增大，因此，網(wǎng)絡中一定存在最優(yōu)的簇頭數(shù)目，使總能耗最小，根據(jù)網(wǎng)絡自身的變化調(diào)整簇頭數(shù)目將會提高 LEACH 算法的性能。

3)動態(tài)調(diào)整節(jié)點的發(fā)射功率。LEACH算法在簇頭選舉時，不考慮節(jié)點間的距離和簇間干擾，使用最大發(fā)射功率完成通信，導致節(jié)點能量的浪費，因此，自適應的調(diào)整發(fā)射功率，有利于延長網(wǎng)絡的生存周期。

4)改進簇頭閾值T(n)。LEACH算法在選擇簇頭時有可能使剩余能量小的節(jié)點被選為簇頭，導致這類節(jié)點加速死亡，縮短網(wǎng)絡壽命，改進閾值將會提高網(wǎng)絡節(jié)點存活率。

2 LEACH-PCOC算法的實現(xiàn)過程

2.1 算法模型及假設

1)網(wǎng)絡模型

設監(jiān)測區(qū)域為J=L×L的正方形，節(jié)點在監(jiān)測區(qū)域內(nèi)隨機播撒,匯聚節(jié)點位于區(qū)域中心的位置,節(jié)點自組網(wǎng)形成WSNs。

2)能量模型

本文假設的網(wǎng)絡采用簡單能量消耗模型，在模型中，A節(jié)點將k比特的數(shù)據(jù)包發(fā)送到距離為d的B節(jié)點，所需的發(fā)射能耗ETx(k,d)和接收能耗ERx(k,d)為

(1)

ERx(k,d)=k·Eelec

(2)

式中Eelec為電路發(fā)送或者接收1 bit數(shù)據(jù)所消耗的能量；εamp和εfs分別為遠近距離傳輸時的射頻參數(shù)，由功率放大器決定；d0為能量模型的傳輸臨界距離，若d>d0，采用自由空間衰落模型，若d≥d0，則采用多徑衰落信道模型。

在模型中,每個節(jié)點都具有數(shù)據(jù)融合的能力，設融合1 bit數(shù)據(jù)消耗的能量為EDA,則把m個節(jié)點1 bit數(shù)據(jù)融合成為1個數(shù)據(jù)消耗的能量表示為lEDA(m)。

3)相關假設

a.所有節(jié)點隨機部署在一個二維的平面內(nèi)，且部署后位置唯一,固定不動;

b.匯聚節(jié)點能量無限，通信距離覆蓋整個網(wǎng)絡;

c.節(jié)點可自由調(diào)節(jié)發(fā)射功率,且節(jié)點均可跟匯聚節(jié)點直接通信;

d.通信鏈路具有對稱性,接收節(jié)點能以相同功率向發(fā)射節(jié)點發(fā)送數(shù)據(jù);

e.簇頭執(zhí)行信號處理，并對簇內(nèi)節(jié)點的信息進行融合后傳輸給Sink節(jié)點。

2.2 算法描述

2.2.1 虛擬單元格劃分監(jiān)測區(qū)域

以網(wǎng)絡的匯聚節(jié)點為坐標原點的位置，建立直角坐標系，將L×L的平面監(jiān)測區(qū)域劃分為若干個邊長為r的正六邊形虛擬網(wǎng)格。區(qū)域劃分好后，設由4個正六邊形的中心點連接形成的長方形的長為2d，寬為2h，則每個網(wǎng)格的中心點坐標即可確定，設為(x0,y0)，如圖1所示，故可定義此網(wǎng)格的網(wǎng)格號為G(m,n)=(m=x0/d,n=y0/h)

圖1 正六邊形虛擬網(wǎng)格

通過節(jié)點關聯(lián)法計算節(jié)點(x,y)所屬的網(wǎng)格號G(m,n):

1)初始化：d=3r/2;h=sqrt(3)/2;Xint=int(x/d);Yint=int(y/d);Xr=x-Xintd;Yr=y-Yinth。

2)循環(huán)：判斷Xint+Yint是否偶數(shù)？

a.偶數(shù)：如果(Xr·Xr+Yr·Yr)≤(d-Xr)(d-Xr)+(h-Yr)(h-Yr),節(jié)點(x,y)屬于網(wǎng)格G(m,n);否則,節(jié)點(x,y)屬于網(wǎng)格G(m+1,n+1)。

b.奇數(shù)：如果(Xr·Xr+(h-Yr)(h-Yr))≤(d-Xr)(d-Xr)+Yr·Yr,節(jié)點(x,y)屬于網(wǎng)格G(m,n+1);否則,節(jié)點(x,y)屬于網(wǎng)格G(m+1,n)。

3)循環(huán)結(jié)束。把在虛擬網(wǎng)格中能量最多的節(jié)點作為該網(wǎng)格的活躍節(jié)點，參與競選簇頭，網(wǎng)格內(nèi)的其他節(jié)點可在一輪的循環(huán)中進入休眠的狀態(tài)。改進后的算法通過簇頭和活躍節(jié)點對區(qū)域進行監(jiān)測，保護能量小的節(jié)點，減少數(shù)據(jù)的冗余度。

2.2.2 簇頭數(shù)量動態(tài)優(yōu)化

針對文獻[7]提出的方法進行修改，設計一個與網(wǎng)絡變化相匹配的最優(yōu)簇頭數(shù)，提高網(wǎng)絡能耗均衡性。設在邊長為L的正方形監(jiān)測區(qū)域內(nèi)，隨機分布n個節(jié)點，其最優(yōu)簇頭數(shù)為k，則平均每個簇內(nèi)有1個簇頭節(jié)點和(n/k-1)個簇成員節(jié)點,則簇頭的總能耗為

(3)

(4)

式中dtoBS為節(jié)點到匯聚節(jié)點的距離,dtoCH為成員節(jié)點到簇頭的距離,Enon-CH為成員節(jié)點能耗。

假設簇頭位于簇的中心，且節(jié)點在區(qū)域內(nèi)是均勻分布的，則網(wǎng)絡的總耗能為

(5)

2.2.3 動態(tài)調(diào)整節(jié)點的發(fā)射功率

令d表示接收節(jié)點和發(fā)送節(jié)點間的距離間隔，Pt表示發(fā)送節(jié)點發(fā)送1個數(shù)據(jù)幀的功率，Pr表示接收節(jié)點接收到該數(shù)據(jù)幀的功率，則有

(6)

式中λ為載波波長；Gt,Gr為發(fā)射天線增益和接收天線增益；n為信道衰落系數(shù)。

預調(diào)整系數(shù)c可以由實驗確定。如果一個接收節(jié)點已知Pt和Rt，并且能夠測出接收信號的能量Pr，則就能夠計算出發(fā)送節(jié)點必須至少以多大的發(fā)射功率才能保證其被接收節(jié)點正確接收。

每個節(jié)點都有一個調(diào)度表，包含所有與其相鄰節(jié)點的信息。在基于功率控制的MAC協(xié)議中，調(diào)度表中增加了與功率控制有關的信息，即與相鄰節(jié)點進行通信時所需要的最低功率量化值(Pm)。每當從相鄰節(jié)點接收到一個SYNC幀時，系統(tǒng)會自動提取，并計算出這一相鄰節(jié)點的下一休眠時間以及其最低功率量化值，這樣發(fā)送節(jié)點就可以計算出到接收節(jié)點之間通信所需要的最小發(fā)射功率。

2.2.4 簇頭節(jié)點選舉

為了使剩余能量較多的節(jié)點更有機會當選為簇首, 同時為了避免網(wǎng)絡的后期因節(jié)點能量過低導致競選簇頭概率變低的問題，引入能量影響因子[8]和平衡因子

χ(i,r)=E(i,r)/Enet_average(r),

φ(i,r)=(Einitial-E(i,r))/Einitial

(7)

式中E(i,r)為節(jié)點i在第r輪開始前的剩余能量；Enet_averger(r)為在第r輪開始前網(wǎng)絡存活節(jié)點的平均能量。具體閾值為

(8)

式中m為網(wǎng)絡存活節(jié)點個數(shù)。

改進后的LEACH-PCOC算法的工作流程圖2。

圖2 LEACH-PCOC算法的工作流程

3 仿真結(jié)果與分析

本文使用 MATLAB對LEACH算法和LEACH-PCOC算法進行仿真，具體的實驗參數(shù)為：節(jié)點總數(shù)為200，匯聚節(jié)點位置為(100,100)m，Einitial=0.5 J，εfs=10 pJ/(bit/m2)，εmp=0.001 3 pJ/(bit/m4)，數(shù)據(jù)包為4 000 bit，廣播包為200 bit，Eelec=50 nJ/bit，EDA=5 nJ/bit。仿真結(jié)果如圖3所示。

圖3 2算法性能比較

由圖3(a)可以發(fā)現(xiàn)，在同一條件下，LEACH算法在700輪左右時，節(jié)點全部死亡，并且曲線斜率大，死亡的速度快，而改進算法在1 300輪左右時，節(jié)點全部死亡，曲線斜率較小，死亡緩慢。由此可見，LEACH-PCOC算法有效的均衡節(jié)點能耗，延長了網(wǎng)絡的生存時間。圖3(b)中在網(wǎng)絡運行的整個階段里，改進算法LEACH-PCOC的總能耗一直低于LEACH算法，由此可知，新算法更能使網(wǎng)絡中的能耗均衡，延長網(wǎng)絡的生存時間。

4 結(jié)束語

本文在分析LEACH路由算法的基礎上提出自適應功率控制與優(yōu)化分簇數(shù)量的新型路由算法LEACH-PCOC，提高了節(jié)點能量的利用率，平衡了網(wǎng)絡能耗，實現(xiàn)延長網(wǎng)絡生存周期的目的。