適于地下管廊的無線傳感網(wǎng)絡(luò)節(jié)能分簇算法

商益民，施亦旺，胡力勤，駱 懿

(1.杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018；2.中國電信股份有限公司浙江分公司，浙江 杭州 310001；3.浙江建設(shè)職業(yè)技術(shù)學(xué)院，浙江 杭州 311231)

0 引 言

隨著城市的現(xiàn)代化發(fā)展，地下管廊成為城市建設(shè)的重要組成。常用的地下管廊監(jiān)控方式是將通信電纜作為信息傳輸?shù)妮d體，但是，地下管廊又長又窄，貫通整個城市，通信電纜架設(shè)困難，成本高，不易維護，而無線傳感器網(wǎng)絡(luò)布局簡單，架設(shè)成本低，同時自組織能力強，能大規(guī)模組網(wǎng)，可靠性也高[1]，適宜地下管廊環(huán)境。由于無線傳感器網(wǎng)絡(luò)的能量由電池供電，經(jīng)常在地下管廊中更換電池是不現(xiàn)實的[2]，同時，無線傳感器網(wǎng)絡(luò)能耗不均，地下管廊的長遠(yuǎn)大于寬，導(dǎo)致能耗更加不均[3]。針對這些技術(shù)難題，學(xué)者們主要通過在分簇拓?fù)浣Y(jié)構(gòu)下延長網(wǎng)絡(luò)的生命周期，例如，劉廣聰?shù)萚4]提出二分K-means算法，將圓簇進行二分裂，通過合并過小的簇來均衡網(wǎng)絡(luò)簇結(jié)構(gòu)，但是大小簇合并復(fù)雜，隨意性大；王丹丹等[5]在地下管廊中隨機部署網(wǎng)絡(luò)結(jié)構(gòu)，改進網(wǎng)絡(luò)模型，對監(jiān)測區(qū)域分簇，但采用隨機部署網(wǎng)絡(luò)結(jié)構(gòu)使得節(jié)點數(shù)目過多，增大了網(wǎng)絡(luò)能耗。本文提出一種基于層次聚類和固定部署網(wǎng)路結(jié)構(gòu)的綜合算法，簡稱HC-CFSFDP，在固定部署網(wǎng)絡(luò)結(jié)構(gòu)下，通過二分裂思想和快速搜索密度峰值聚類(Clustering by Fast Search and Find of Density Peaksd，CFSFDP)[6]將監(jiān)測區(qū)域進行分簇，從而使網(wǎng)絡(luò)生命周期得到延長。

圖1 管廊的二維平面網(wǎng)絡(luò)結(jié)構(gòu)模型圖

1 網(wǎng)絡(luò)模型與最優(yōu)簇數(shù)計算

無線傳感器網(wǎng)絡(luò)的能耗不均主要受簇首能耗的影響，簇間通信的能耗與簇首數(shù)量成正比，簇內(nèi)通信所消耗的能量與簇首數(shù)量成反比，因此，適合的簇首數(shù)能大大均衡網(wǎng)絡(luò)的能耗。以管廊的二維平面建立數(shù)學(xué)模型，如圖1所示。圖1中，部署傳感器節(jié)點感知范圍滿足全覆蓋，同時節(jié)點感知范圍的重疊面積也是最小的，此時簇為橢圓簇。監(jiān)測區(qū)域為長方形，橢圓表示簇；部署在管廊上的黑點為傳感器節(jié)點；虛線圓表示節(jié)點的感知范圍。長方形區(qū)域的長為L，寬為M(L?M)。因此，監(jiān)測區(qū)域內(nèi)的網(wǎng)絡(luò)模型呈現(xiàn)單行線形橢圓形狀，以圖1所示，長方形監(jiān)測區(qū)域內(nèi)單行排列k個橢圓簇，因此，假設(shè)橢圓簇的長半軸長和短半軸長分別為M/2和R。

橢圓簇與監(jiān)測區(qū)域的關(guān)系如下：

(1)

從式(1)中可以得出k與R的關(guān)系：

(2)

長方形區(qū)域內(nèi)分布著k個簇，N個傳感器節(jié)點，簇成員節(jié)點服從均勻分布，采用經(jīng)典無線電模型[7]計算。則關(guān)系式為：

(3)

根據(jù)式(2)和(3)可以計算得出簇首與簇內(nèi)節(jié)點平方距離的期望值，則該值為：

(4)

由式(4)可知，每一個簇內(nèi)簇成員節(jié)點的平均能耗為：

(5)

每一個簇的簇首節(jié)點的平均能耗為：

(6)

式中，dBS為基站與簇首距離，Eelec為發(fā)射機或接收機電路發(fā)送或接收每bit信息量所消耗的能量，εfs為自由空間模型能耗系數(shù)，εmp為多路徑放大電路能耗系數(shù)，EDA為每bit數(shù)據(jù)融合的耗能。根據(jù)式(5)和式(6)可知，單個簇的平均能量消耗為：

(7)

通過式(7)可以得到整個網(wǎng)絡(luò)的總能耗為：

(8)

將Etotal對k求導(dǎo)，得出最優(yōu)簇數(shù)kopt為：

(9)

2 基于層次聚類的的節(jié)能分簇算法

本文提出的基于層次聚類和固定部署網(wǎng)路結(jié)構(gòu)的綜合算法HC-CFSFDP主要是通過自上而下的層次聚類思想[8]進行分簇操作。首先，根據(jù)第1節(jié)計算k值，作為一輪中分簇過程的結(jié)束條件；然后，根據(jù)母簇選舉因子選舉出母簇，用CFSFDP分裂母簇；最后，通過簇首綜合指標(biāo)選舉出各自的簇首節(jié)點，根據(jù)相應(yīng)的路由傳輸數(shù)據(jù)。分簇流程如圖2所示。

圖2 分簇協(xié)議流程圖

圖2中，J為當(dāng)前監(jiān)測區(qū)域內(nèi)簇的個數(shù)，Gc為選出需要被分裂的簇的選舉因子，k為最優(yōu)簇數(shù)，i為當(dāng)前被選舉出簇首的數(shù)量。算出當(dāng)前每個簇的Gc值，最大值的簇就會成為下一個被分裂的簇，1個簇分裂成2個簇，此時簇數(shù)就增加1個，即J增加1。

2.1 截斷距離的優(yōu)化

CFSFDP是通過局部密度和鄰近距離來聚類。首先，在數(shù)據(jù)節(jié)點集中找到滿足以下條件的點作為匯聚中心點：(1)匯聚中心節(jié)點的密度比其周圍所有節(jié)點的都要高；(2)匯聚中心周圍節(jié)點與該匯聚中心點距離相比于與其它匯聚中心點的距離來說，是最近的。然后，該匯聚中心與距離其近的節(jié)點組成一個簇。鄰近距離使2個匯聚中心點更加分散，利于母簇分裂成2個子簇。局部密度使匯聚中心點與大多數(shù)鄰近點的距離都較近，利于母簇的選舉和減少簇的能耗，而局部密度是根據(jù)截斷距離的大小來確定范圍的。通過多次的計算得出，該網(wǎng)絡(luò)模型中簇內(nèi)每個節(jié)點的平均鄰居節(jié)點個數(shù)與節(jié)點總數(shù)的比例為3%～5%，此時，能大大優(yōu)化局部密度，CFSFDP很好地與本文的細(xì)胞分裂思想結(jié)合起來，每次分裂都均衡了網(wǎng)絡(luò)的能耗。

2.2 母簇的選取

無線傳感器節(jié)點部署在長方形監(jiān)測區(qū)域內(nèi)，該區(qū)域就是本文初始的母簇，初始母簇直接一分為二，從分裂出的若干簇中選出接下來要分裂的簇，依次選取簇，對簇進行下一步分裂，直到滿足簇數(shù)為k，才結(jié)束分裂。當(dāng)一個簇的相對面積更大，同時母簇中各節(jié)點與匯聚中心的距離方差更大時，這樣的簇才是此次要被選取分裂的簇。母簇中的節(jié)點數(shù)目與母簇的面積成正比，基于此，構(gòu)造1個目標(biāo)函數(shù)用于在許多簇中選取出合適的簇作為要被分裂的簇：

(10)

2.3 簇首選舉

根據(jù)HC-CFSFDP協(xié)議和網(wǎng)絡(luò)模型。當(dāng)簇內(nèi)節(jié)點的局部密度越大，節(jié)點與基站距離越短，同時節(jié)點的剩余能量更充足，此時該節(jié)點成為簇首節(jié)點的可能性更大。本文構(gòu)造1個目標(biāo)函數(shù)用于在簇中選舉出合適的節(jié)點作為簇首：

(11)

3 仿真分析

表1 仿真參數(shù)值

仿真實驗中，節(jié)點分別分布于的300×20和600×20的長方形區(qū)域中，其基站坐標(biāo)分別為(150,10)和(300,10)，無線傳感器網(wǎng)絡(luò)都是同構(gòu)網(wǎng)絡(luò)，初始能量為0.5 J。分別采用低功耗自適應(yīng)分簇算法(Low Energy Adaptive Clustering Hierarchy，LEACH)、分布式節(jié)能分簇算法(Distribute Energy-Efficient Clustering，DEEC)、低功耗自適應(yīng)的比例能量分簇算法(LEACH Proportion Energy Algorithm，LPEA)和HC-CFSFDP進行100次仿真實驗，以平均值作為最后實驗結(jié)果。在2種網(wǎng)絡(luò)規(guī)模下，從網(wǎng)絡(luò)生命周期、網(wǎng)絡(luò)能耗和網(wǎng)絡(luò)吞吐量方面進行比較。實驗相關(guān)參數(shù)如表1所示。

3.1 網(wǎng)絡(luò)生命周期

表2 不同算法在不同網(wǎng)絡(luò)規(guī)模下的節(jié)點死亡輪數(shù)

第1個節(jié)點和最后1個節(jié)點死亡輪數(shù)均能反映網(wǎng)絡(luò)生命周期的情況。不同算法的無線傳感器網(wǎng)絡(luò)在不同網(wǎng)絡(luò)規(guī)模下的節(jié)點死亡輪數(shù)如表2所示。

由表2可知，在網(wǎng)絡(luò)運行過程中，LPEA的網(wǎng)絡(luò)存活節(jié)點超過LEACH，因為LPEA的節(jié)點死亡較慢，使得LPEA的網(wǎng)絡(luò)生命周期要比LEACH長；DEEC在每輪簇首選舉時考慮了節(jié)點剩余能量和網(wǎng)絡(luò)的平均能量，延長了網(wǎng)絡(luò)的生命周期，在2種網(wǎng)絡(luò)規(guī)模中，與LEACH相比，DEEC將網(wǎng)絡(luò)生命周期分別延長了4.4%，10.1%；HC-CFSFDP的簇首選舉考慮了節(jié)點能量，簇首與基站間的距離和簇內(nèi)節(jié)點距離，兩個距離的綜合使得長方形區(qū)域?qū)φ麄€網(wǎng)絡(luò)性能的影響進一步降低，最終延長了網(wǎng)絡(luò)的生命周期，在2種網(wǎng)絡(luò)規(guī)模中，與LEACH相比，HC-CFSFDP將網(wǎng)絡(luò)的生命周期分別延長了22.9%，15.2%。

3.2 網(wǎng)絡(luò)能耗

不同算法的網(wǎng)絡(luò)剩余能量在不同網(wǎng)絡(luò)規(guī)模和輪數(shù)的比較如表3所示。

表3 不同算法在不同輪數(shù)和網(wǎng)絡(luò)規(guī)模下的網(wǎng)絡(luò)剩余能量 單位：J

由表3可知，網(wǎng)絡(luò)能耗速度與網(wǎng)絡(luò)的部署區(qū)域長度成正比，其原因在于節(jié)點通信距離隨著區(qū)域變長而變長，這樣增加了節(jié)點通信能量的消耗。由表3可知，HC-CFSFDP在最優(yōu)簇首數(shù)的計算、簇的形成和簇首選舉方面都均衡了整個網(wǎng)絡(luò)的能耗，使得其能耗速度明顯要比LEACH,LPEA,DEEC慢。

3.3 網(wǎng)絡(luò)吞吐量

表4 不同算法在不同網(wǎng)絡(luò)規(guī)模下的網(wǎng)絡(luò)吞吐量 單位：bit·s-1

不同算法在不同網(wǎng)絡(luò)規(guī)模下的網(wǎng)絡(luò)吞吐量之間的比較。比較情況如表4所示。

由表4可知，LPEA在數(shù)據(jù)吞吐總量上比LEACH的稍微多一點。DEEC的傳輸總量超過LEACH和LPEA，DEEC在簇首選舉時考慮了網(wǎng)絡(luò)的平均能量，保證了網(wǎng)絡(luò)更長的通信能力，從而增大了網(wǎng)絡(luò)的數(shù)據(jù)吞吐量。HC-CFSFDP的吞吐量始終高于其他算法，在2種網(wǎng)絡(luò)規(guī)模下，其數(shù)據(jù)吞吐總量分別是DEEC的152.3%和120.2%，是LPEA協(xié)議的176.6%和245.8%，因此，HC-CFSFDP的網(wǎng)絡(luò)生命周期更長，使得網(wǎng)絡(luò)能長久穩(wěn)定地傳輸更多數(shù)據(jù)。

4 結(jié)束語

針對二分K-means算法和隨機網(wǎng)絡(luò)部署網(wǎng)絡(luò)結(jié)構(gòu)在地下管廊中應(yīng)用的不足，本文提出一種基于層次聚類和固定部署網(wǎng)路結(jié)構(gòu)的HC-CFSFDP算法。算法結(jié)合二分K-means算法的分簇思想和新網(wǎng)絡(luò)結(jié)構(gòu)，在大小簇的處理和節(jié)點的部署方面都有很大的改善，提高了網(wǎng)絡(luò)的性能。本文算法是在二維網(wǎng)絡(luò)模型下完成的，但是，現(xiàn)實應(yīng)用中都是空間三維結(jié)構(gòu)，下一步將進行三維網(wǎng)絡(luò)模型實驗，使無線傳感器網(wǎng)絡(luò)的應(yīng)用更符合實際。