齊 華, 呂 龍, 陳 紅

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

0 引 言

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

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

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

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

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

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

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

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

2.1 算法模型及假設(shè)

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

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

2)能量模型

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

(1)

ERx(k,d)=k·Eelec

(2)

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

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

3)相關(guān)假設(shè)

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

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

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

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

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

2.2 算法描述

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

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

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

通過節(jié)點(diǎn)關(guān)聯(lián)法計(jì)算節(jié)點(diǎn)(x,y)所屬的網(wǎng)格號(hào)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é)點(diǎn)(x,y)屬于網(wǎng)格G(m,n);否則,節(jié)點(diǎn)(x,y)屬于網(wǎng)格G(m+1,n+1)。

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

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

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

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

(3)

(4)

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

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

(5)

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

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

(6)

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

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

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

2.2.4 簇頭節(jié)點(diǎn)選舉

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

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

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

(7)

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

(8)

式中m為網(wǎng)絡(luò)存活節(jié)點(diǎn)個(gè)數(shù)。

改進(jìn)后的LEACH-PCOC算法的工作流程圖2。

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

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

本文使用 MATLAB對(duì)LEACH算法和LEACH-PCOC算法進(jìn)行仿真，具體的實(shí)驗(yàn)參數(shù)為：節(jié)點(diǎn)總數(shù)為200，匯聚節(jié)點(diǎn)位置為(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輪左右時(shí)，節(jié)點(diǎn)全部死亡，并且曲線斜率大，死亡的速度快，而改進(jìn)算法在1 300輪左右時(shí)，節(jié)點(diǎn)全部死亡，曲線斜率較小，死亡緩慢。由此可見，LEACH-PCOC算法有效的均衡節(jié)點(diǎn)能耗，延長了網(wǎng)絡(luò)的生存時(shí)間。圖3(b)中在網(wǎng)絡(luò)運(yùn)行的整個(gè)階段里，改進(jìn)算法LEACH-PCOC的總能耗一直低于LEACH算法，由此可知，新算法更能使網(wǎng)絡(luò)中的能耗均衡，延長網(wǎng)絡(luò)的生存時(shí)間。

4 結(jié)束語

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