蔡 揚，張懷相

(杭州電子科技大學(xué)計算機(jī)學(xué)院，浙江 杭州 310018)

一種基于鄰近區(qū)域平均能量的分簇算法

蔡 揚，張懷相

(杭州電子科技大學(xué)計算機(jī)學(xué)院，浙江 杭州 310018)

針對無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點能量受限的問題，為減少節(jié)點能量消耗，提出了一種基于鄰近區(qū)域平均能量的節(jié)能分簇算法.算法采用分階段的簇頭選舉策略.在候選簇頭選舉階段，根據(jù)節(jié)點剩余能量與鄰近區(qū)域平均能量的比率來選取候選簇頭.在簇頭競選階段，使用功率控制方法使得每輪選出的簇頭個數(shù)穩(wěn)定，且均勻地分布在網(wǎng)絡(luò)中，從而均衡網(wǎng)絡(luò)能耗.仿真結(jié)果表明，算法具有更長的網(wǎng)絡(luò)生存時間，網(wǎng)絡(luò)穩(wěn)定周期較AEAR算法和TCAC算法分別提高了16.9%和10.0%.

鄰近區(qū)域平均能量；分簇；功率控制；節(jié)能；無線傳感器網(wǎng)絡(luò)

0 引 言

由于傳感器的存儲容量和計算能力有限，有效的拓?fù)淇刂茖?jié)能至關(guān)重要.拓?fù)淇刂埔话憧煞譃楣?jié)點功率控制和層次型拓?fù)浣Y(jié)構(gòu)兩類.功率控制通過設(shè)置或動態(tài)調(diào)整節(jié)點發(fā)射功率的大小，確保網(wǎng)絡(luò)的連通性，使得節(jié)點能耗最低或者網(wǎng)絡(luò)的干擾性最小.分簇機(jī)制是一種減少無線傳感器網(wǎng)絡(luò)通信開銷和提供更好數(shù)據(jù)聚合的拓?fù)涔芾矸椒╗1].低功耗自適應(yīng)集簇分層型協(xié)議(Low Energy Adaptive Clustering Hierarchy，LEACH)[2]是一種經(jīng)典的自適應(yīng)分簇算法，通過周期性執(zhí)行簇頭輪值，均勻分配節(jié)點間的能量負(fù)載.但LEACH算法采用隨機(jī)的方式選舉簇頭，簇頭在網(wǎng)絡(luò)中分布可能不均勻，且每個節(jié)點成為簇頭的概率相同，不適用于能量異構(gòu)的網(wǎng)絡(luò).文獻(xiàn)[3]在簇頭選舉時，考慮了網(wǎng)絡(luò)平均剩余能量，但每個節(jié)點須獲取整個網(wǎng)絡(luò)的平均剩余能量.文獻(xiàn)[4]在簇頭選舉時，考慮了所有前一輪所形成的簇在當(dāng)前輪的平均能量，但每輪每個節(jié)點都要重新計算簇內(nèi)平均剩余能量.多種方式結(jié)合也是拓?fù)淇刂蒲芯康囊粋€方向.例如拓?fù)淇刂频淖赃m應(yīng)分簇(Topology-Controlled Adaptive Clustering，TCAC)[5]算法在簇頭選舉階段，使用功率控制，以穩(wěn)定簇頭個數(shù)和均勻簇頭分布.為了均衡節(jié)點的能耗，延長網(wǎng)絡(luò)的生存時間，本文提出了一種基于鄰近區(qū)域平均能量的功率控制分簇算法(Power Controlled Clustering algorithm with Average Energy of Adjacent Region，PCCAEAR).

1 異構(gòu)網(wǎng)絡(luò)模型

數(shù)據(jù)傳輸?shù)哪芎哪Ｐ鸵话悴捎梦墨I(xiàn)[3]中的模型.每發(fā)送和接收一個Lbits數(shù)據(jù)的能耗分別描述如下：

(1)

ERx(L)=LEelec

(2)

其中，Eelec表示電路處理每個bit數(shù)據(jù)的能耗，d0表示距離閾值.如果傳輸距離小于d0，則采用自由空間傳輸模型，功放因子為εfs.反之采用多徑衰耗模型，其功放因子為εmp.

假設(shè)在一個M×M范圍內(nèi)有N個傳感器節(jié)點均勻分布，基站位于這個區(qū)域的中心，并且任意一個節(jié)點到基站或簇頭的距離都不大于距離閾值d0.則每輪消耗的網(wǎng)絡(luò)能量如下：

(3)

2 基于鄰近區(qū)域平均能量的分簇算法

網(wǎng)絡(luò)中，以某一個節(jié)點為中心，該節(jié)點一定通信半徑內(nèi)的區(qū)域稱為鄰近區(qū)域，在該鄰近區(qū)域中的其余節(jié)點稱為該節(jié)點的鄰近區(qū)域節(jié)點，這個區(qū)域中所有節(jié)點的平均能量被稱為鄰近區(qū)域平均能量.本文提出了一種基于鄰近區(qū)域平均能量的功率控制分簇算法PCCAEAR.算法分為4個階段，分別為網(wǎng)絡(luò)初始化、簇頭選舉、成簇及穩(wěn)定傳輸.

2.1 初始化網(wǎng)絡(luò)

初始時，網(wǎng)絡(luò)中所有的節(jié)點以Ri為半徑廣播Hello消息，Hello消息中包含節(jié)點剩余能量、地理位置等信息.

Ri=λRNavg, (Ri>RNavg)

(4)

節(jié)點i利用接收到的Hello消息統(tǒng)計出自己的鄰居數(shù)Nbi后，根據(jù)自身剩余能量Ei(r)和所有鄰居剩余能量計算其鄰近區(qū)域平均能量Ei Navg(r)(r表示當(dāng)前輪數(shù)，初始化時r=0)：

(5)

2.2 簇頭選舉

簇頭選舉包含候選簇頭選舉階段和候選簇頭競選簇頭階段.

1)候選簇頭選舉階段

PCCAEAR算法中，如果節(jié)點i在第r輪屬于能夠參與簇頭選舉的節(jié)點集合，則根據(jù)概率函數(shù)pi計算其成為候選簇頭的概率：

(6)

其中，P表示節(jié)點中簇頭的百分比.α表示影響候選簇頭個數(shù)的參數(shù)，由于在簇頭選舉階段要進(jìn)行功率控制，為選出一定量的簇頭，需增加候選簇頭個數(shù).

第r輪的鄰近區(qū)域平均能量Ei Navg(r)是根據(jù)上一輪的鄰近區(qū)域平均能量Ei Navg(r-1)與上一輪節(jié)點i估計消耗的能量Eic=Eround/N來計算的.若節(jié)點i當(dāng)選為簇頭節(jié)點時，需判斷是否需要更新自己的鄰近區(qū)域平均能量Ei Navg(r)，如果小于前一次更新的t倍時(稱t為簇頭鄰近區(qū)域平均能量更新因子)，則需用式(5)重新計算.所以得到新的計算鄰近區(qū)域平均能量公式如下：

(7)

然后節(jié)點i將概率pi值代入閾值函數(shù)計算出閾值T(i):

(8)

其中，G表示節(jié)點在第r輪能夠參與簇頭選舉的節(jié)點集合.如果節(jié)點i當(dāng)選為簇頭，節(jié)點i將會在接下來的1/pi輪內(nèi)都不參與簇頭的競選.

計算出閾值后，節(jié)點i隨機(jī)產(chǎn)生一個[0,1]之間隨機(jī)數(shù)，若比閾值小則該節(jié)點成為候選簇頭.當(dāng)α的值取0，且在簇頭競選過程中不采用功率控制，此時選出的候選簇頭節(jié)點作為最終的簇頭節(jié)點，將此算法稱之為AEAR算法.否則，需要對這些候選簇頭進(jìn)行篩選以得到簇頭節(jié)點.

2)候選簇頭競選簇頭階段

競選簇頭的方法類似于TCAC算法.經(jīng)過上一階段選出的候選簇頭以一定的發(fā)射半徑Rc廣播候選簇頭競選簇頭消息CCHMSG，消息包含節(jié)點位置、剩余能量等信息.

(9)

其中，β為影響簇頭競爭階段發(fā)射半徑的因子，rc根據(jù)每個簇頭的通信面積計算得到.

候選簇頭等待其他候選簇頭廣播CCHMSG消息.若候選簇頭未收到其他候選簇頭發(fā)來的CCHMSG消息，則該節(jié)點成為簇頭節(jié)點；若收到其他候選簇頭廣播的CCHMSG消息，則比較這些候選簇頭節(jié)點能量的大小.如果該候選簇頭節(jié)點能量最大，則被選為簇頭節(jié)點；否則，變?yōu)榉谴仡^節(jié)點.候選簇頭競選簇頭的過程如圖1所示.

圖1 候選簇頭競選簇頭過程

PCCAEAR算法的網(wǎng)絡(luò)成簇及穩(wěn)定傳輸階段同LEACH，非簇頭節(jié)點接收到簇頭廣播的CHMSG后，根據(jù)所收到的信號強(qiáng)度的大小，選擇加入某個簇并向該簇頭發(fā)送申請加入簇的消息REQMSG.

2.3 算法分析

PCCAEAR算法在網(wǎng)絡(luò)初始化階段節(jié)點是以小于最大功率的固定功率廣播消息，從而與其鄰居節(jié)點建立連接.相比于節(jié)點以最大功率廣播消息的其他算法，縮小了通信范圍，因此，在初始化階段減少了節(jié)點收集鄰居節(jié)點信息的能耗.算法通過兩步的方式選舉簇頭，首先，在選取候選簇頭時不是以固定概率來選取，而是考慮了節(jié)點的剩余能量和鄰近區(qū)域平均能量，能量高且其鄰近區(qū)域節(jié)點能量相對較低的節(jié)點被選中的概率大.PCCAEAR算法只有簇頭才有權(quán)利更新其鄰近區(qū)域平均能量，而且只有在小于上次更新的一定倍數(shù)時，才進(jìn)行更新操作.此更新操作只是收集小范圍內(nèi)鄰居節(jié)點的剩余能量，即簇頭的鄰近區(qū)域范圍內(nèi)的節(jié)點的能量.因此，相比于一般考慮平均能量這一參數(shù)的算法節(jié)約了通信開銷.然后在簇頭選舉時進(jìn)行功率控制，采用功率控制的方法可以有效避免簇頭分布過于密集，在一定范圍內(nèi)只有一個簇頭，使得簇頭的分布更加均勻，簇頭個數(shù)更加穩(wěn)定.

3 仿真實驗

仿真實驗中，節(jié)點一旦部署后就固定不動，每個節(jié)點可感知自身剩余能量和自身地理位置，節(jié)點能量分布在[E0,4E0]區(qū)間.基站位于網(wǎng)絡(luò)的中心位置.由于kopt≈10，設(shè)置最優(yōu)簇頭個數(shù)為10.仿真實驗參數(shù)如表1所示.

表1 仿真實驗參數(shù)設(shè)置

3.1 鄰近區(qū)域半徑和簇頭鄰近區(qū)域平均能量更新

首先確定鄰近區(qū)域半徑因子λ和簇頭鄰近區(qū)域平均能量更新因子t的值.將t從0.5增加到0.9，設(shè)置不同的λ為2到6之間的整數(shù)，第一個節(jié)點死亡的輪數(shù)如圖2所示.觀察發(fā)現(xiàn)，第一個節(jié)點死亡的輪數(shù)隨著t值的增大總體呈現(xiàn)先上升后下降的趨勢.t從0.7增加到0.8的過程中，第1個節(jié)點死亡的輪數(shù)呈現(xiàn)上升的狀態(tài)，可能的原因是：簇頭的選舉是基于節(jié)點的鄰近區(qū)域平均能量及剩余能量的，簇頭節(jié)點更新鄰近區(qū)域平均能量相對較為頻繁，選出來的簇頭較優(yōu)，均衡了網(wǎng)絡(luò)能量的消耗.當(dāng)λ=4，t=0.6時，第一個節(jié)點死亡輪數(shù)最大.所以取λ=4，t=0.6作為之后的實驗參數(shù).

對比AEAR，LEACH，LEACH-E[3]和REAC[4]算法的網(wǎng)絡(luò)生存時間，如圖3所示.從圖中觀察到，AEAR算法較LEACH-E和REAC網(wǎng)絡(luò)生存時間有所提高.因為AEAR算法并不是每輪都更新鄰近區(qū)域平均能量，只有當(dāng)簇頭的鄰近區(qū)域平均能量小于上次更新后能量值的0.6倍時才重新收集計算，相比于每輪都重新計算平均剩余能量LEACH-E和REAC算法減少了能量的消耗.AEAR算法相較于LEACH的穩(wěn)定周期大幅提高(穩(wěn)定周期指網(wǎng)絡(luò)中出現(xiàn)死亡節(jié)點前網(wǎng)絡(luò)執(zhí)行的輪數(shù))，由于LEACH算法每個節(jié)點當(dāng)選簇頭的概率相同，對于異構(gòu)網(wǎng)絡(luò)來說，能量較低的節(jié)點會過早地死亡.

圖2 不同λ，t對應(yīng)第一個節(jié)點死亡輪數(shù)

圖3 每輪存活節(jié)點個數(shù)

3.2 發(fā)射半徑和候選簇頭

繼續(xù)研究本文算法發(fā)射半徑和候選簇頭個數(shù)這2個參數(shù)對簇頭個數(shù)和網(wǎng)絡(luò)生存時間的影響.對α和β取不同值，計算平均簇頭個數(shù)和評估網(wǎng)絡(luò)生存時間.實驗時，將α從0.00增加到0.20，β從0.8遞增到1.2，找出最優(yōu)參數(shù)組，使得平均簇頭個數(shù)接近最優(yōu)簇頭個數(shù)的情況下網(wǎng)絡(luò)生存時間最長.

當(dāng)網(wǎng)絡(luò)生存一定時間后，部分節(jié)點逐漸開始死亡.因此，對前2 000輪的平均簇頭個數(shù)進(jìn)行評估，相應(yīng)的仿真結(jié)果如圖4所示.從仿真結(jié)果可知，當(dāng)β為特定值時，隨著α的增大，網(wǎng)絡(luò)中的每輪平均簇頭個數(shù)逐漸增大，增大到一定程度后到達(dá)穩(wěn)定的數(shù)目.原因是α較小時，所選出的候選簇頭較少，競爭選出的簇頭也較少.而隨著α增大時，所選出的候選簇頭增多，由于競選簇頭過程中，候選簇頭的競爭半徑是固定的，某一候選簇頭在其競爭范圍內(nèi)的候選簇頭數(shù)目可能增多，而在這區(qū)域內(nèi)最多只能競選出一個簇頭節(jié)點.因此，當(dāng)α增大到一定程度后，選出來的簇頭的數(shù)量趨于穩(wěn)定.在相同的α下，每輪平均簇頭個數(shù)隨β值的增大而減小.因為β對應(yīng)的是簇頭競爭階段的候選簇頭的發(fā)射半徑，在一定范圍內(nèi)只有一個能量最高的候選簇頭成為簇頭節(jié)點，β越大，選出的簇頭就越少.當(dāng)β取1.0，α從0.08到0.20時，網(wǎng)絡(luò)中每輪平均簇頭個數(shù)最接近于kopt.其他每輪平均簇頭個數(shù)接近kopt的參數(shù)組(α,β)有(0.03,0.8)和(0.04,0.9).

然后評估功率參數(shù)因子β和概率參數(shù)因子α對網(wǎng)絡(luò)生存時間的影響.網(wǎng)絡(luò)生存時間是依據(jù)第一個節(jié)點死亡的輪數(shù)來評估，結(jié)果如圖5所示.結(jié)果顯示節(jié)點死亡輪數(shù)隨著α增大而增大，到達(dá)一定值后減小.原因是α較小時，候選簇頭較少，競爭選出的簇頭也較少，簇間通信時簇頭的能耗較大.而α較大時，由于候選簇頭的數(shù)量增多，在簇頭競爭階段消耗更多的能量.這些都會造成節(jié)點相對較早死亡.結(jié)合之前選出的參數(shù)組，當(dāng)(α,β)=(0.12,1.0)，第一個節(jié)點死亡的輪數(shù)最大.從圖中也可以看出當(dāng)β=1.0時，α在0.10到0.16之間第一個節(jié)點死亡輪數(shù)相差不大.因此，最終取(α,β)=(0.12,1.0)作為最佳的參數(shù)組.

圖4 不同α，β對應(yīng)的平均簇頭個數(shù)

圖5 不同α，β對應(yīng)的第一個節(jié)點死亡的輪數(shù)

3.3 簇頭個數(shù)和網(wǎng)絡(luò)生存時間

根據(jù)相對較優(yōu)的參數(shù)組，設(shè)置PCCAEAR算法的參數(shù)α和β分別為0.12和1.0，并將本文算法與AEAR和TCAC算法比較.對于TCAC算法，傳輸半徑設(shè)置為rc，簇頭參數(shù)kinitial=2kopt.圖6顯示了3種算法的每輪簇頭個數(shù)，關(guān)于網(wǎng)絡(luò)生存時間仿真結(jié)果如圖7所示.

圖6 每輪簇頭個數(shù)

圖7 每輪存活節(jié)點個數(shù)

觀察圖6的仿真結(jié)果發(fā)現(xiàn)，TCAC和PCCAEAR算法每輪簇頭個數(shù)較為穩(wěn)定，在10左右小幅波動，而AEAR簇頭個數(shù)的波動范圍較大，在0到30之間.由此可見，在簇頭選舉階段進(jìn)行功率控制可以穩(wěn)定簇頭的個數(shù).

觀察圖7發(fā)現(xiàn)，PCCAEAR的穩(wěn)定周期最長，相較于AEAR和TCAC分別增加了16.9%和10.0%.因為PCCAEAR簇頭不是每輪都更新鄰近區(qū)域平均能量，而是當(dāng)小于上一次更新后的t倍時才進(jìn)行更新，減少了能量的消耗.AEAR的穩(wěn)定周期最短，由于每輪的簇頭個數(shù)不穩(wěn)定，導(dǎo)致一些能量較低的節(jié)點較早死亡.TCAC和PCCAEAR算法當(dāng)節(jié)點開始出現(xiàn)死亡后，剩余節(jié)點以較快的速度死亡，原因是進(jìn)行功率控制后網(wǎng)絡(luò)中節(jié)點分布較為均勻，導(dǎo)致網(wǎng)絡(luò)能耗也更為均勻.PCCAEAR算法較TCAC算法的網(wǎng)絡(luò)生命周期提高了約11.0%.因為TCAC雖然進(jìn)行了功率控制，但是每一輪都需要計算網(wǎng)絡(luò)的平均剩余能量，反而增加了網(wǎng)絡(luò)開銷.

4 結(jié)束語

本文以能量受限的無線傳感器網(wǎng)絡(luò)為背景，提出了一種基于鄰近區(qū)域平均能量的簇頭選舉算法AEAR，并在此基礎(chǔ)上，結(jié)合功率控制方法提出了PCCAEAR算法.實驗結(jié)果表明，PCCAEAR算法可以有效地穩(wěn)定簇頭個數(shù)和均勻簇頭分布，使得網(wǎng)絡(luò)的能耗更加均衡，相較于AEAR算法延長了網(wǎng)絡(luò)生存時間.PCCAEAR算法減少了簇頭收集鄰居信息的能耗，相較于每輪簇頭都要收集簇成員節(jié)點剩余能量的TCAC算法減少了額外開銷.然而,算法中的參數(shù)如鄰近區(qū)域半徑因子,功率參數(shù)因子,概率參數(shù)因子等是根據(jù)仿真實驗的結(jié)果來確定的.因此,在實際應(yīng)用中,必須對參數(shù)作進(jìn)一步的調(diào)整.

[1]BOYINBODE O, LE H, TAKIZAWA M. A survey on clustering algorithms for wireless sensor networks[J]. International Journal of Space-Based and Situated Computing, 2011,1(2/3):130-136.

[2]HEINZELMAN, RABINER W, CHANDRAKASAN, et al. Energy-efficient communication protocol for wireless microsensor networks[J]. Adhoc & Sensor Wireless Networks, 2000,18:8020.

[3]HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. Wireless Communications, IEEE Transactions on, 2002,1(4):660-670.

[4]LEU J S, CHIANG T H, YU M C, et al. Energy Efficient Clustering Scheme for Prolonging the Lifetime of Wireless Sensor Network With Isolated Nodes[J]. IEEE Communications Letters, 2015,19(2):259-262.

[5]DAHNIL D P, SINGH Y P, HO C K. Topology-controlled adaptive clustering for uniformity and increased lifetime in wireless sensor networks[J]. Wireless Sensor Systems Iet, 2012,2(4):318-327.

A Clustering Algorithm Based on Average Energy of Adjacent Region

CAI Yang, ZHANG Huaixiang

(SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Sensor nodes are energy constrained in wireless sensor networks, in order to reduce nodes energy consumption, an energy efficient clustering algorithm based on average energy of adjacent region is proposed. The algorithm adopts staged cluster heads election strategy. In candidate cluster heads election stage, candidate cluster heads are elected based on the ratio between residual energy and average energy of adjacent region. Power control is used in cluster heads election stage, cluster heads are elected in a stable number per round and evenly distributed in network that makes the network energy consumption more balanced. Simulation results show that proposed algorithm has a longer network lifetime, with the stability period increasing by 16.9% and 10.0% respectively compared to AEAR and TCAC.

average energy of adjacent region; clustering; power control; energy saving; wireless sensor network

10.13954/j.cnki.hdu.2017.04.009

2016-11-03

國家科技支撐計劃資助項目(2014BAF07B01)

蔡揚(1991-)，女，浙江麗水人，碩士研究生，無線傳感器網(wǎng)絡(luò).通信作者：張懷相副教授，E-mail：hxzhang@hdu.edu.cn.

TP393

A

1001-9146(2017)04-0041-06