基于功率控制與分簇數量的LEACH優化算法

齊 華, 呂 龍, 陳 紅

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

0 引 言

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

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

1 LEACH-PCOC算法的實現思路

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

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

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

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

2 LEACH-PCOC算法的實現過程

2.1 算法模型及假設

1)網絡模型

設監測區域為J=L×L的正方形，節點在監測區域內隨機播撒,匯聚節點位于區域中心的位置,節點自組網形成WSNs。

2)能量模型

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

(1)

ERx(k,d)=k·Eelec

(2)

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

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

3)相關假設

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

b.匯聚節點能量無限，通信距離覆蓋整個網絡;

c.節點可自由調節發射功率,且節點均可跟匯聚節點直接通信;

d.通信鏈路具有對稱性,接收節點能以相同功率向發射節點發送數據;

e.簇頭執行信號處理，并對簇內節點的信息進行融合后傳輸給Sink節點。

2.2 算法描述

2.2.1 虛擬單元格劃分監測區域

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

圖1 正六邊形虛擬網格

通過節點關聯法計算節點(x,y)所屬的網格號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)循環：判斷Xint+Yint是否偶數？

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

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

3)循環結束。把在虛擬網格中能量最多的節點作為該網格的活躍節點，參與競選簇頭，網格內的其他節點可在一輪的循環中進入休眠的狀態。改進后的算法通過簇頭和活躍節點對區域進行監測，保護能量小的節點，減少數據的冗余度。

2.2.2 簇頭數量動態優化

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

(3)

(4)

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

假設簇頭位于簇的中心，且節點在區域內是均勻分布的，則網絡的總耗能為

(5)

2.2.3 動態調整節點的發射功率

令d表示接收節點和發送節點間的距離間隔，Pt表示發送節點發送1個數據幀的功率，Pr表示接收節點接收到該數據幀的功率，則有

(6)

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

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

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

2.2.4 簇頭節點選舉

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

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

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

(7)

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

(8)

式中m為網絡存活節點個數。

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

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

3 仿真結果與分析

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

圖3 2算法性能比較

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

4 結束語

本文在分析LEACH路由算法的基礎上提出自適應功率控制與優化分簇數量的新型路由算法LEACH-PCOC，提高了節點能量的利用率，平衡了網絡能耗，實現延長網絡生存周期的目的。