伍敏君

(中山火炬職業(yè)技術(shù)學(xué)院 光電信息學(xué)院，廣東 中山 528400)

0 引言

無線電通信、嵌入式、傳感器、微電子等技術(shù)的迅速發(fā)展，使無線傳感器網(wǎng)絡(luò)技術(shù)被廣泛應(yīng)用于各領(lǐng)域[1]，如軍事安全、農(nóng)業(yè)監(jiān)測(cè)[2-3]、醫(yī)療護(hù)理、工業(yè)生產(chǎn)、交通物流、自然災(zāi)害預(yù)測(cè)等。監(jiān)測(cè)區(qū)域內(nèi)大規(guī)模地部署傳感器節(jié)點(diǎn)，各節(jié)點(diǎn)以自組織方式形成無線通信網(wǎng)絡(luò)[4-5]。節(jié)點(diǎn)能量有限且無法及時(shí)補(bǔ)充，能量效率是無線傳感器網(wǎng)絡(luò)技術(shù)難點(diǎn)問題，合理路由管理可延長(zhǎng)網(wǎng)絡(luò)生命周期[6-8]。分簇的拓?fù)淇刂?，能大幅度減少數(shù)據(jù)傳輸量，降低能耗[9-12]。

低功耗自適應(yīng)聚類層次算法(LEACH,low energy adaptive clustering hierarchy)[13]是經(jīng)典的分簇算法，其簇頭數(shù)量不穩(wěn)定且分布不均勻，對(duì)此提出了固定分簇技術(shù)。固定分簇算法能有效地降低分簇開銷，均衡各個(gè)分簇大小[14]。文獻(xiàn)[15]提出基于粒子群(PSO)優(yōu)化的固定簇類區(qū)域路由算法，綜合考慮分簇與匯聚節(jié)點(diǎn)距離、簇內(nèi)節(jié)點(diǎn)間距、剩余能量等因素。文獻(xiàn)[16]提出固定分簇和能量均衡的多跳路由協(xié)議，基于遺傳模擬退火算法來分簇，簇頭選舉考慮節(jié)點(diǎn)剩余能量和全簇平均能量值，簇間以單跳或多跳方式來通信。文獻(xiàn)[17]提出異構(gòu)網(wǎng)絡(luò)的固定區(qū)域分簇路由算法，網(wǎng)格固定分區(qū)內(nèi)綜合考慮節(jié)點(diǎn)剩余能量及節(jié)點(diǎn)分布情況來選舉簇頭。文獻(xiàn)[18]提出基于網(wǎng)格分簇路由算法，設(shè)置能量閾值，當(dāng)能量低于此閾值的鄰居節(jié)點(diǎn)個(gè)數(shù)超過一定量時(shí)，采用唯一簇頭選舉法生成新簇頭。

本文針對(duì)LEACH算法中簇頭分布不均以及數(shù)量動(dòng)態(tài)變化而造成網(wǎng)絡(luò)能耗不均衡的問題，提出一種改進(jìn)的固定分簇算法(FCA,fixed clustering algorithm)，簇頭的選舉綜合考慮區(qū)域的內(nèi)心距離、位置布局、節(jié)點(diǎn)剩余能量等因素，從而達(dá)到優(yōu)化簇頭布局、均衡網(wǎng)絡(luò)能耗、延長(zhǎng)網(wǎng)絡(luò)穩(wěn)定周期和生命周期的目的。

1 分簇算法

1.1 LEACH算法

LEACH是一種分布式的分簇算法，為了將整個(gè)網(wǎng)絡(luò)的能量消耗更均勻地散布到各個(gè)節(jié)點(diǎn)中，LEACH算法采用按輪的方式進(jìn)行劃分各分簇，每輪均分為簇的建立階段和穩(wěn)定階段兩個(gè)階段。

在簇的建立階段中，LEACH采用動(dòng)態(tài)分簇的方式劃分網(wǎng)絡(luò)。網(wǎng)絡(luò)中剩余能量大于零的節(jié)點(diǎn)，稱為存活節(jié)點(diǎn)。在此階段開始時(shí)，LEACH采取隨機(jī)方式選舉簇頭，各個(gè)存活節(jié)點(diǎn)均選取一個(gè)[0,1]范圍內(nèi)的隨機(jī)數(shù)。如果此節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)低于閾值T(n)，同時(shí)此節(jié)點(diǎn)在前面1/p輪中還未當(dāng)選過簇頭的，則這個(gè)節(jié)點(diǎn)在此輪中當(dāng)選為簇頭。其中，節(jié)點(diǎn)n在第r輪中的閾值T(n)計(jì)算公式為：

(1)

式中，p是簇頭占所有節(jié)點(diǎn)總數(shù)的百分比；G是最近1/p輪中沒有當(dāng)選為簇頭的節(jié)點(diǎn)集合。

在各個(gè)分簇內(nèi)，只選舉一個(gè)節(jié)點(diǎn)當(dāng)選簇頭，其余節(jié)點(diǎn)稱為成員節(jié)點(diǎn)[19]。每輪中，簇頭周期性地更換，當(dāng)節(jié)點(diǎn)在此輪中當(dāng)選為簇頭后，向周圍其余節(jié)點(diǎn)廣播自身成為簇頭的消息。其余節(jié)點(diǎn)按收到簇頭消息的強(qiáng)弱，可知與此簇頭的距離長(zhǎng)短，據(jù)此，其余節(jié)點(diǎn)加入距離最近的分簇中，并向該簇頭發(fā)送加入分簇的請(qǐng)求。

當(dāng)簇頭節(jié)點(diǎn)收到其余節(jié)點(diǎn)的加入請(qǐng)求后，根據(jù)自身簇內(nèi)加入節(jié)點(diǎn)的數(shù)量，建立該簇的時(shí)分多址(TDMA，time division multiple access)調(diào)度表，并把此輪的TDMA調(diào)度表發(fā)送至其簇內(nèi)的各成員節(jié)點(diǎn)。

穩(wěn)定階段也稱數(shù)據(jù)傳輸階段，在此階段中，LEACH算法利用簇頭進(jìn)行數(shù)據(jù)融合，減少冗余信息，降低網(wǎng)絡(luò)數(shù)據(jù)傳輸量從而節(jié)省能耗。首先，簇頭節(jié)點(diǎn)主要任務(wù)是對(duì)成員節(jié)點(diǎn)進(jìn)行管理和協(xié)調(diào)，收集其簇內(nèi)所有成員節(jié)點(diǎn)感知的數(shù)據(jù)。當(dāng)各成員節(jié)點(diǎn)的TDMA時(shí)隙到來時(shí)，各自向簇頭節(jié)點(diǎn)發(fā)送自身感知周圍環(huán)境的數(shù)據(jù)信息。簇頭節(jié)點(diǎn)對(duì)自身分簇內(nèi)的所有數(shù)據(jù)進(jìn)行壓縮融合后轉(zhuǎn)發(fā)到匯聚節(jié)點(diǎn)[20]。在此階段中，成員節(jié)點(diǎn)不直接與匯聚節(jié)點(diǎn)通信。

LEACH算法的簇頭選舉具有隨機(jī)性，當(dāng)能量較低的節(jié)點(diǎn)選為簇頭時(shí)，容易加速節(jié)點(diǎn)的死亡，從而影響網(wǎng)絡(luò)的生命周期。

1.2 LEACH-E算法

在分簇算法中，簇頭承擔(dān)著融合分簇內(nèi)的數(shù)據(jù)并向匯聚節(jié)點(diǎn)轉(zhuǎn)發(fā)的重任，因此簇頭消耗的能量遠(yuǎn)大于成員節(jié)點(diǎn)。當(dāng)能量低的節(jié)點(diǎn)當(dāng)選為簇頭后，由于承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)的耗能任務(wù)，很容易導(dǎo)致能量消耗過多而死亡。此時(shí)，網(wǎng)絡(luò)中部分節(jié)點(diǎn)的死亡，會(huì)造成部分區(qū)域感知數(shù)據(jù)的缺失以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不穩(wěn)定。

對(duì)此，LEACH-E算法對(duì)LEACH作了改進(jìn)，在簇頭選舉時(shí)，考慮各節(jié)點(diǎn)自身的剩余能量以及當(dāng)前網(wǎng)絡(luò)的平均能量水平，只有剩余能量大于當(dāng)前網(wǎng)絡(luò)平均能量的節(jié)點(diǎn)才有資格在此輪中參與簇頭競(jìng)選。

LEACH-E算法由于考慮了節(jié)點(diǎn)能量信息來選舉簇頭節(jié)點(diǎn)，避免了能量較低的節(jié)點(diǎn)當(dāng)選簇頭而造成網(wǎng)絡(luò)拓?fù)洳缓侠淼膯栴}，減緩了網(wǎng)絡(luò)能量消耗速度。

但在LEACH和LEACH-E算法中，均沒有考慮簇頭位置因素的影響，網(wǎng)絡(luò)中簇頭的分布不均勻，各個(gè)分簇大小不均衡。

2 FCA算法

針對(duì)LEACH和LEACH-E算法中簇頭分布及分簇大小不均的問題，本文提出一種改進(jìn)算法FCA，以固定方式劃分各個(gè)分簇，簇頭選舉過程中引入代價(jià)函數(shù)，該代價(jià)函數(shù)綜合考慮區(qū)域的內(nèi)心距離、節(jié)點(diǎn)剩余能量及位置布局等因素來選舉簇頭，優(yōu)化簇頭數(shù)量和布局，使分簇更加合理。

2.1 網(wǎng)絡(luò)模型假定

結(jié)合實(shí)際情況以及無線傳感器網(wǎng)絡(luò)的特性，在本算法中提出以下網(wǎng)絡(luò)假設(shè)：

1)所有節(jié)點(diǎn)能夠感知自身的坐標(biāo)位置和剩余能量，部署后不再移動(dòng)，均能與匯聚節(jié)點(diǎn)通信；

2)只有一個(gè)匯聚節(jié)點(diǎn)，位于網(wǎng)絡(luò)區(qū)域中央處，能量可以補(bǔ)充且不受限；

3)除匯聚節(jié)點(diǎn)外，其余節(jié)點(diǎn)坐標(biāo)隨機(jī)分布，具有相同初始能量且不能補(bǔ)充，有唯一ID號(hào)；

4)網(wǎng)絡(luò)的通信鏈路具有對(duì)稱性，即對(duì)于同等量的數(shù)據(jù)，從A點(diǎn)發(fā)送到B點(diǎn)所消耗的能量，與從B點(diǎn)發(fā)送到A點(diǎn)所消耗的能量一致；

5)節(jié)點(diǎn)發(fā)射功率可調(diào)控，即節(jié)點(diǎn)可以根據(jù)距離選擇不同的傳播模型——自由空間傳播模型和多路徑衰減傳播模型。

2.2 能量消耗模型

本文采用通用無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗模型，如圖1所示，能耗包括發(fā)射器傳輸電路能耗、發(fā)射放大電路能耗，以及接收器的接收電路能耗。

圖1 節(jié)點(diǎn)能量消耗模型

當(dāng)發(fā)送端與接收端之間的距離d小于或等于臨界值d0時(shí)，采用自由空間傳播模型，能量呈d2衰減，能耗系數(shù)為εfs；d大于d0時(shí)，采用多路徑衰減傳播模型，能量呈d4衰減，能耗系數(shù)為εmp。節(jié)點(diǎn)發(fā)送Lbit數(shù)據(jù)的能耗ETX(L,d)與數(shù)據(jù)包長(zhǎng)度L、通信距離d有關(guān)，為：

ETX(L,d)=

(2)

式中，Eelec表示發(fā)送或接收單位信息所消耗的能量。d0是兩種傳播模型的臨界值，為：

(3)

節(jié)點(diǎn)接收Lbit數(shù)據(jù)的能耗ERX(L)與數(shù)據(jù)包長(zhǎng)度L成正比，為：

ERX(L)=L·Eelec

(4)

2.3 算法描述

2.3.1 固定分簇的劃分

以匯聚節(jié)點(diǎn)為坐標(biāo)原點(diǎn)，建立直角坐標(biāo)系，將M×M的正方形監(jiān)測(cè)區(qū)域劃分為k個(gè)等大小的固定分簇，設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量為N，在LEACH 算法中，網(wǎng)絡(luò)中簇頭最優(yōu)數(shù)量kopt為[13]：

(5)

其中:dtoBS為節(jié)點(diǎn)到匯聚節(jié)點(diǎn)距離，其期望值E[dtoBS]為：

(6)

其中:A為網(wǎng)絡(luò)區(qū)域的面積；x為節(jié)點(diǎn)的橫坐標(biāo)；y為節(jié)點(diǎn)的縱坐標(biāo)。

當(dāng)N=100，M=100時(shí)，可得簇頭最優(yōu)數(shù)量kopt≈10，簇頭比例p=kopt/N≈0.1。本文取k為8，固定分簇的數(shù)量接近LEACH算法中的最優(yōu)簇頭數(shù)量，將網(wǎng)絡(luò)區(qū)域劃分為8個(gè)等大小的固定分簇，編號(hào)分別為①～⑧，如圖2所示。

圖2 固定分簇的劃分

2.3.2 簇頭的選舉

分簇算法中網(wǎng)絡(luò)的拓?fù)淇刂浦饕纱仡^來完成，簇頭分布對(duì)網(wǎng)絡(luò)性能影響較大。在每個(gè)固定分簇中選舉一個(gè)節(jié)點(diǎn)當(dāng)選簇頭，簇頭較均衡地散布于網(wǎng)絡(luò)各個(gè)分簇中，避免了監(jiān)測(cè)區(qū)域中簇頭過于密集或分散的問題，優(yōu)化了簇頭的布局。

簇頭選舉中考慮節(jié)點(diǎn)剩余能量、到分簇區(qū)域內(nèi)心位置的距離等因素。在第r輪中節(jié)點(diǎn)i當(dāng)選簇頭代價(jià)函數(shù)costi(r)為：

(7)

其中:Ei(r)為第r輪中節(jié)點(diǎn)i的剩余能量；E0為初始能量；dmax為節(jié)點(diǎn)到匯聚節(jié)點(diǎn)距離的最大值；diclusterj為節(jié)點(diǎn)i到其所在固定分簇區(qū)域j(j=1,2,…,8)內(nèi)心位置的距離。內(nèi)心位置為各固定分簇內(nèi)接圓的圓心坐標(biāo)位置。Ei(r)的值越大，節(jié)點(diǎn)剩余能量越充足，costi(r)越大，當(dāng)選簇頭幾率越高；diclusterj的值越小，節(jié)點(diǎn)i到固定分簇區(qū)域內(nèi)心位置的距離越小，costi(r)越大，當(dāng)選簇頭幾率越高。

2.3.3 數(shù)據(jù)傳輸階段

設(shè)節(jié)點(diǎn)總數(shù)為N，劃分為k個(gè)固定分簇，則平均每個(gè)簇內(nèi)有N/k個(gè)節(jié)點(diǎn)，其中一個(gè)為簇頭，其余的(N/k-1)個(gè)為成員節(jié)點(diǎn)。在數(shù)據(jù)傳輸階段，考慮到傳輸距離d≤d0，采用自由空間傳播模型能耗系數(shù)εfs，節(jié)點(diǎn)i向其簇頭以單跳方式發(fā)送Lbit數(shù)據(jù)所消耗的能量Enon-CHi為：

Enon-CHi=L·Eelec+L·εfs·dtoCHi2

(8)

其中:dtoCHi為成員節(jié)點(diǎn)i到簇頭的距離。

簇頭融合簇內(nèi)成員節(jié)點(diǎn)的數(shù)據(jù)，并向匯聚節(jié)點(diǎn)以單跳方式發(fā)送處理后的數(shù)據(jù)所消耗能量ECH為：

L·εfs·dtoBS2

(9)

其中:EDA為融合1 bit信息所消耗的能量；dtoBS為簇頭到匯聚節(jié)點(diǎn)的距離值。

各分簇消耗的能量Ecluster為：

(10)

2.3.4 FCA算法流程

FCA算法流程如圖3所示，算法按如下步驟實(shí)現(xiàn)：

1)在網(wǎng)絡(luò)初始化時(shí)，以匯聚節(jié)點(diǎn)為原點(diǎn)，生成坐標(biāo)系，部署網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)，生成隨機(jī)坐標(biāo)并保存，配置各節(jié)點(diǎn)的初始能量；

2)各節(jié)點(diǎn)向匯聚節(jié)點(diǎn)發(fā)送自身的坐標(biāo)位置、當(dāng)前的能量水平等信息；

3)以匯聚節(jié)點(diǎn)分中心，劃分8個(gè)固定分簇區(qū)域并編號(hào)；

4)各個(gè)節(jié)點(diǎn)根據(jù)自身的坐標(biāo)信息，加入固定分簇，并保存所在的分簇編號(hào)等信息；

5)各個(gè)分簇分別計(jì)算并保存自身分簇區(qū)域內(nèi)心位置的坐標(biāo)信息；

6)計(jì)算第r輪中節(jié)點(diǎn)i當(dāng)選簇頭代價(jià)函數(shù)costi(r)，求出各分簇中的最大值；

7)各分簇區(qū)域中代價(jià)函數(shù)取值最大的，在該輪中當(dāng)選簇頭，其余為成員節(jié)點(diǎn)；

8)簇頭向簇內(nèi)成員節(jié)點(diǎn)發(fā)送其簇頭狀態(tài)的廣播消息，以及TDMA調(diào)度表；

9)進(jìn)入穩(wěn)定階段，各成員節(jié)點(diǎn)向簇頭發(fā)送感知的數(shù)據(jù)，簇頭融合簇內(nèi)數(shù)據(jù)后，向匯聚節(jié)點(diǎn)發(fā)送數(shù)據(jù)；

10)本輪分簇結(jié)束，進(jìn)入下一輪。

圖3 FCA算法流程圖

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 仿真環(huán)境

本文采用Matlab R2014a軟件對(duì)LEACH、LEACH-E、FCA算法進(jìn)行仿真分析。仿真場(chǎng)景如圖4所示，正方形區(qū)域范圍為(-50，-50)～(50，50)，部署100個(gè)節(jié)點(diǎn)，圖中“▲”為匯聚節(jié)點(diǎn)，位于坐標(biāo)原點(diǎn)處，“○”為節(jié)點(diǎn)，坐標(biāo)隨機(jī)產(chǎn)生。節(jié)點(diǎn)初始能量E0為0.5 J，簇頭比例p為0.08，發(fā)送或接收單位數(shù)據(jù)能耗Eelec為50 nJ/bit，自由空間傳播模型能耗系數(shù)εfs為10 pJ/bit/m2，多路徑衰減傳播模型能耗系數(shù)εmp為0.001 3 pJ/bit/m4，數(shù)據(jù)包長(zhǎng)度L為4 000 bit。

3.2 仿真結(jié)果分析

3.2.1 簇頭分布

LEACH和LEACH-E算法其中一輪簇頭分布情況，如圖5和圖6所示，“□”為簇頭，“○”為成員節(jié)點(diǎn)，“--”為節(jié)點(diǎn)與簇頭的單跳通信。可見，LEACH和LEACH-E中簇頭分布隨機(jī)，某些區(qū)域簇頭過于密集，某些區(qū)域內(nèi)無簇頭，使得節(jié)點(diǎn)加入分簇時(shí)，離其簇頭距離過大。

圖5 LEACH簇頭分布

圖6 LEACH-E簇頭分布

FCA算法其中一輪簇頭分布情況，如圖7所示，“□”為簇頭，“○”為成員節(jié)點(diǎn)，“--”為節(jié)點(diǎn)與簇頭的單跳通信，“-·”為各個(gè)固定分簇的劃分，可見，各簇頭分布較均勻，基本分布在各固定分簇的區(qū)域中央位置，避免由邊緣處節(jié)點(diǎn)當(dāng)選簇頭而導(dǎo)致簇內(nèi)通信距離過大的問題。

圖7 FCA簇頭分布

3.2.2 分簇大小

LEACH、LEACH-E、FCA算法各分簇的節(jié)點(diǎn)數(shù)量如表1所示。

表1 各算法分簇節(jié)點(diǎn)數(shù)量

LEACH算法劃分了9個(gè)分簇，分簇節(jié)點(diǎn)數(shù)均值為E(n)=11.1，標(biāo)準(zhǔn)差為σ=4.93。LEACH-E算法劃分了6個(gè)分簇，分簇節(jié)點(diǎn)數(shù)均值為E′(n)=16.7，標(biāo)準(zhǔn)差為σ′=8.16。FCA算法劃分了8個(gè)分簇，分簇節(jié)點(diǎn)數(shù)均值為E″(n)=12.5，標(biāo)準(zhǔn)差為σ″=2.45。

可見，LEACH、LEACH-E簇頭選舉未考慮節(jié)點(diǎn)位置因素，分簇大小不均衡，標(biāo)準(zhǔn)差較大。FCA算法各分簇節(jié)點(diǎn)數(shù)目較穩(wěn)定，分簇大小均衡，標(biāo)準(zhǔn)差較小。

3.2.3 每輪簇頭數(shù)量

LEACH、LEACH-E、FCA算法中每輪的簇頭數(shù)量統(tǒng)計(jì)如圖8所示。LEACH、LEACH-E中每輪簇頭數(shù)量不穩(wěn)定，分布在1～14之間。FCA算法采用固定分簇技術(shù)，每輪中簇頭數(shù)量比較穩(wěn)定，簇頭數(shù)量為8的輪數(shù)有1 757次。

圖8 每輪簇頭數(shù)量統(tǒng)計(jì)

3.2.4 穩(wěn)定周期、半衰周期和生命周期

LEACH、LEACH-E、FCA三種算法的節(jié)點(diǎn)存活數(shù)隨時(shí)間變化情況如圖9所示。

圖9 每輪的節(jié)點(diǎn)存活情況

1)穩(wěn)定周期，即網(wǎng)絡(luò)運(yùn)行開始后首節(jié)點(diǎn)死亡的時(shí)間。LEACH、LEACH-E、FCA的穩(wěn)定周期分別為1 007輪、1 135輪、1 658輪。FCA對(duì)比LEACH延長(zhǎng)了64.65%，對(duì)比LEACH-E延長(zhǎng)了46.08%。

2)半衰周期，為網(wǎng)絡(luò)中50%節(jié)點(diǎn)死亡時(shí)間。LEACH、LEACH-E、FCA的半衰周期分別為1 220輪、1 189輪、2 366輪。FCA對(duì)比LEACH延長(zhǎng)了93.93%，對(duì)比LEACH-E延長(zhǎng)了98.99%。

3)生命周期，描述了從網(wǎng)絡(luò)開始工作到全部節(jié)點(diǎn)死亡的時(shí)間段。LEACH、LEACH-E、FCA的生命周期分別為1 509輪、1 257輪、2 501輪。FCA對(duì)比LEACH算法延長(zhǎng)了65.74%，對(duì)比LEACH-E算法延長(zhǎng)了98.97%。

3.2.5 網(wǎng)絡(luò)能量消耗情況對(duì)比

LEACH、LEACH-E、FCA三種算法的網(wǎng)絡(luò)剩余總能量隨時(shí)間變化情況如圖10所示。FCA算法采用固定分簇技術(shù)，簇頭選舉綜合考慮節(jié)點(diǎn)剩余能量和位置的因素，有效均衡了網(wǎng)絡(luò)能量消耗，其每輪中網(wǎng)絡(luò)剩余總能量均比LEACH、LEACH-E算法高。

圖10 每輪的網(wǎng)絡(luò)能量消耗情況

4 結(jié)束語

本文提出一種改進(jìn)的固定分簇算法，將網(wǎng)絡(luò)劃分為等大小的分簇，簇頭選舉的代價(jià)函數(shù)考慮區(qū)域內(nèi)心距離、節(jié)點(diǎn)剩余能量及位置信息綜合因素，以優(yōu)化簇頭數(shù)量和布局。仿真結(jié)果表明，改進(jìn)后的算法有效均衡了網(wǎng)絡(luò)能耗，實(shí)現(xiàn)延長(zhǎng)網(wǎng)絡(luò)穩(wěn)定周期、半衰周期以及生命周期的目的。