無線傳感器網(wǎng)絡區(qū)域內(nèi)心距離的固定分簇算法

伍敏君

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

0 引言

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

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

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

1 分簇算法

1.1 LEACH算法

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

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

(1)

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

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

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

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

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

1.2 LEACH-E算法

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

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

LEACH-E算法由于考慮了節(jié)點能量信息來選舉簇頭節(jié)點，避免了能量較低的節(jié)點當選簇頭而造成網(wǎng)絡拓撲不合理的問題，減緩了網(wǎng)絡能量消耗速度。

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

2 FCA算法

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

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

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

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

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

3)除匯聚節(jié)點外，其余節(jié)點坐標隨機分布，具有相同初始能量且不能補充，有唯一ID號；

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

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

2.2 能量消耗模型

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

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

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

ETX(L,d)=

(2)

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

(3)

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

ERX(L)=L·Eelec

(4)

2.3 算法描述

2.3.1 固定分簇的劃分

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

(5)

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

(6)

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

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

圖2 固定分簇的劃分

2.3.2 簇頭的選舉

分簇算法中網(wǎng)絡的拓撲控制主要由簇頭來完成，簇頭分布對網(wǎng)絡性能影響較大。在每個固定分簇中選舉一個節(jié)點當選簇頭，簇頭較均衡地散布于網(wǎng)絡各個分簇中，避免了監(jiān)測區(qū)域中簇頭過于密集或分散的問題，優(yōu)化了簇頭的布局。

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

(7)

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

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

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

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

(8)

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

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

L·εfs·dtoBS2

(9)

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

各分簇消耗的能量Ecluster為：

(10)

2.3.4 FCA算法流程

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

1)在網(wǎng)絡初始化時，以匯聚節(jié)點為原點，生成坐標系，部署網(wǎng)絡中各個節(jié)點，生成隨機坐標并保存，配置各節(jié)點的初始能量；

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

3)以匯聚節(jié)點分中心，劃分8個固定分簇區(qū)域并編號；

4)各個節(jié)點根據(jù)自身的坐標信息，加入固定分簇，并保存所在的分簇編號等信息；

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

6)計算第r輪中節(jié)點i當選簇頭代價函數(shù)costi(r)，求出各分簇中的最大值；

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

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

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

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

圖3 FCA算法流程圖

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

3.1 仿真環(huán)境

本文采用Matlab R2014a軟件對LEACH、LEACH-E、FCA算法進行仿真分析。仿真場景如圖4所示，正方形區(qū)域范圍為(-50，-50)～(50，50)，部署100個節(jié)點，圖中“▲”為匯聚節(jié)點，位于坐標原點處，“○”為節(jié)點，坐標隨機產(chǎn)生。節(jié)點初始能量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ù)包長度L為4 000 bit。

3.2 仿真結(jié)果分析

3.2.1 簇頭分布

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

圖5 LEACH簇頭分布

圖6 LEACH-E簇頭分布

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

圖7 FCA簇頭分布

3.2.2 分簇大小

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

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

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

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

3.2.3 每輪簇頭數(shù)量

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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