于大為1，董茜茜，張 昀，于舒娟

(1.蘇州信息職業(yè)技術(shù)學(xué)院，江蘇 蘇州 215200；2.南京郵電大學(xué) 電子與光學(xué)工程學(xué)院，南京 210003)

0 引言

隨著工業(yè)和交通運輸業(yè)的飛速發(fā)展，大量的有害物質(zhì)被排到空氣中，空氣污染問題愈發(fā)的凸顯。空氣污染不僅在生活上給我們帶來了危害，還增加了各種疾病的爆發(fā)概率，同時也給自然環(huán)境帶來很多毀滅性的影響。環(huán)境監(jiān)測是環(huán)境保護工作的重要組成部分，而空氣質(zhì)量監(jiān)測是其中的一個重要環(huán)節(jié)?？諝赓|(zhì)量監(jiān)測是對空氣中污染物濃度的高低進行實時檢測，給出空氣的質(zhì)量狀況、污染指數(shù)、對人體健康影響的預(yù)告。當(dāng)前，作為新時期物聯(lián)網(wǎng)的典型案例，利用無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)實現(xiàn)大氣環(huán)境自動監(jiān)測已經(jīng)得到廣泛關(guān)注和應(yīng)用[1-2]。空氣質(zhì)量檢測的環(huán)境復(fù)雜，地域廣闊，傳感器節(jié)點經(jīng)常被隨機撒布在偏遠(yuǎn)地區(qū)、野外等人員難以到達(dá)地區(qū)，節(jié)點依靠干電池供電，部署后便無法對其進行回收或充能處理。因此，在空氣監(jiān)測系統(tǒng)無線傳感網(wǎng)的設(shè)計中，需要引入分簇和路徑規(guī)劃策略，保證節(jié)點能量的高效和均衡使用，從而延長網(wǎng)絡(luò)的生命周期。

為降低空氣質(zhì)量監(jiān)測系統(tǒng)無線傳感網(wǎng)中的通信能耗，基于分簇路由協(xié)議的策略受到廣泛使用。所謂分簇，如圖1所示將整個傳感器網(wǎng)絡(luò)劃分為相對獨立的若干區(qū)域，每個區(qū)域內(nèi)包含簇首和簇成員兩種類型的節(jié)點，簇成員節(jié)點負(fù)責(zé)感知數(shù)據(jù)，并將收集到的數(shù)據(jù)發(fā)送至簇首，簇首將簇成員傳輸過來的數(shù)據(jù)進行融合處理，然后以單跳或者多跳的形式傳輸給基站(Base Station,BS)。如今，許多研究人員已經(jīng)提出多種分簇路由算法[3-9]。W.Heinzelman等人提出了一種經(jīng)典的低功能自適應(yīng)分簇協(xié)議(low energy adaptive clustering hierarchy, LEACH)[3]，該協(xié)議以輪為單位分為簇的建立和數(shù)據(jù)傳輸兩個階段。在簇建立階段，根據(jù)閾值隨機選擇一定數(shù)量的節(jié)點擔(dān)任簇首，這極可能造成簇首分布過于集中，造成網(wǎng)絡(luò)局部癱瘓。而在傳輸數(shù)據(jù)時，簇首以單跳的形式將融合后的簇內(nèi)數(shù)據(jù)傳輸給基站，能耗不均，存在嚴(yán)重的“熱區(qū)”效應(yīng)[4]。LEACH協(xié)議每一輪都要執(zhí)行簇的重構(gòu)，帶來較大的通信開銷。A.Ray等人[5]研究了一種基于改進K-means算法的節(jié)能聚類協(xié)議EECPK-means，該協(xié)議使用中心算法來改善初始質(zhì)心選擇過程，最終平衡簇首的負(fù)載，延長網(wǎng)絡(luò)壽命。李成法等[6]提出了一個分布式非均勻分簇算法EEUC，以候選簇首離基站的距離為參數(shù)計算非均勻競爭半徑，使靠近基站的簇首的簇規(guī)模更小，為簇首預(yù)留更多的能量用于數(shù)據(jù)轉(zhuǎn)發(fā)。章力等[7]針對傳感器節(jié)點均勻分布的窖池測溫?zé)o線傳感網(wǎng)絡(luò)，利用差分進化算法選擇固定數(shù)目的簇首，并對簇首和簇成員節(jié)點采用能量異構(gòu)的策略。分簇一旦確立，網(wǎng)絡(luò)運轉(zhuǎn)過程中不再執(zhí)行選簇的機制。

圖1 無線傳感網(wǎng)分簇路由協(xié)議示意圖

本文在參考上述文獻(xiàn)的基礎(chǔ)上，根據(jù)空氣質(zhì)量監(jiān)測無線傳感網(wǎng)絡(luò)規(guī)模較大、節(jié)點分布不均的特點，以節(jié)點覆蓋率為目標(biāo)建立函數(shù)優(yōu)化模型，并采用差分進化算法對其優(yōu)化；通過計算簇首的競爭半徑，構(gòu)造大小不等的簇；為了節(jié)省通信開銷，網(wǎng)絡(luò)運轉(zhuǎn)過程中根據(jù)選簇頻率和節(jié)點編號更換簇首節(jié)點。仿真實驗表明，本文提出的分簇路由算法能夠有效均衡空氣質(zhì)量檢測系統(tǒng)無線傳感網(wǎng)絡(luò)的能耗，延長網(wǎng)絡(luò)生命周期。

1 網(wǎng)絡(luò)系統(tǒng)模型

根據(jù)圖2所示的空氣質(zhì)量監(jiān)測系統(tǒng)中傳感器節(jié)點的分布，本文假設(shè)網(wǎng)絡(luò)模型如下：在L×W×H的空間中，隨機撒布N個傳感器節(jié)點 ,其中L、W和H分別表示監(jiān)測區(qū)域的長度、寬度和高度。用Ci表示第i個傳感器節(jié)點，相應(yīng)的節(jié)點集合為C={C1,C2,…,CN}，N=|C|。用CHj表示第j個簇首節(jié)點，相應(yīng)的簇首節(jié)點節(jié)為CH={CH1,CH2,…,CHj}，我們假設(shè)：

1)所有傳感器節(jié)點和BS在隨機撒布后位置不再發(fā)生移動。

2)BS位于網(wǎng)絡(luò)中心，其計算能力和能量均不受限制。

3)所有節(jié)點的能量同構(gòu)且具有唯一的標(biāo)識(ID)，具備數(shù)據(jù)融合能力，能夠感知自己的剩余能量。

圖2 空氣質(zhì)量監(jiān)測系統(tǒng)傳感器節(jié)點分布

參照文獻(xiàn)[10]構(gòu)造能量模型，無線通信傳輸l比特信息經(jīng)過距離d0時所消耗的能量如式(1)所示：

(1)

其中:l為數(shù)據(jù)比特數(shù)，d為通信距離；Eelec，εfs和Emp表示系統(tǒng)在運轉(zhuǎn)時電路的能量消耗，Eelec由數(shù)字編碼方式、調(diào)制過程、濾波方法以及地域情況等因素決定，而εfsd2和εmpd4與傳輸者與接收者的距離和允許的誤碼率范圍有關(guān)。無線通信接收l比特的信息時的能耗如式(2)所示:

ER(l)=lEelec

(2)

2 算法描述

2.1 簇首數(shù)目的確定

網(wǎng)絡(luò)系統(tǒng)模型如上節(jié)所示，假設(shè)簇首數(shù)目為K，則平均簇內(nèi)成員節(jié)點個數(shù)為N/K-1，簇首節(jié)點和簇成員節(jié)點的能耗分別為：

(3)

(4)

其中:EDA表示融合單位比特數(shù)據(jù)消耗的能量，dave表示簇首和基站兩兩之間的平均距離，dtoCH為簇成員節(jié)點到其簇首得距離。

在三維空氣質(zhì)量監(jiān)測系統(tǒng)中，假設(shè)每個簇的覆蓋區(qū)域為以簇首為中心的圓球且節(jié)點均勻分布，節(jié)點分布的概率密度為ρ=(x,y,z)=1/((L*W*H)/K)，則簇成員節(jié)點到簇首距離的數(shù)學(xué)期望為：

(5)

再假設(shè)區(qū)域內(nèi)每個簇為半徑近似R的圓球，即：

(6)

將公式(6)代入公式(5)，可得：

(7)

從而可得網(wǎng)絡(luò)運轉(zhuǎn)中每輪消耗的能量約為：

(8)

將公式(7)代入公式(8)，并將總能量對K求導(dǎo)，得出K的最優(yōu)值為式(9)。

(9)

2.2 簇首坐標(biāo)的優(yōu)化

在空氣質(zhì)量監(jiān)測系統(tǒng)簇首定位模型中，由于靠近基站的簇首需要轉(zhuǎn)發(fā)額外的數(shù)據(jù)信息，很容易造成能量空洞的問題。我們采用非均勻的分簇機制。通過不同的成簇半徑，使得簇規(guī)模越靠近基站越小。因此，靠近簇首的基站可以預(yù)留更多的能量用于轉(zhuǎn)發(fā)其他簇首的數(shù)據(jù)。參考文獻(xiàn)[6]，成簇半徑定義為：

(10)

其中:dmax、dmin分別表示簇成員節(jié)點距離基站的最大值和最小值，d(Ci,BS)表示簇首Ci到基站的距離，Rmax表示節(jié)點間通信半徑，c為0～1內(nèi)的常數(shù)，用來控制成簇半徑在(1-c)Rmax。

差分進化算法主要用于求解全局優(yōu)化問題，是一種動態(tài)跟蹤、隨機搜索的智能進化算法。其主要分為兩個階段：初始化階段、進化階段。在本文簇首坐標(biāo)優(yōu)化問題初始化階段，采用實數(shù)編碼，則初始種群可根據(jù)公式(11)隨機產(chǎn)生：

(11)

進化階段包含變異、交叉和選擇個操作步驟。其中變異采用如式(12)所示的策略，得到子代變異個體vi(G+1)。其中，xt1(G)表示第G代種群的第t1個個體；t1、t2、t3、t4、t5∈{1,2,…,NP}，且互不相等；F為縮放因子。

vi(G+1)=xt1(G)+F·(xt2(G)-xt3(G))+

F·(xt4(G)-xt5(G))

(12)

種群完成變異操作后，將變異個體vi(G+1)與目標(biāo)個體xi(G)通常采用Binomial實驗方式生成個體ui(G)，這一過程稱之為交叉操作。值得注意的是，交叉操作的操作對象不再針對整個個體，而是按每個個體向量的分量進行的。交叉操作的公式如下：種群完成變異操作后，將變異個體vi(G+1)與目標(biāo)個體xi(G)通常采用Binomial實驗方式生成個體ui(G)，這一過程稱之為交叉操作。值得注意的是，交叉操作的操作對象不再針對整個個體，而是按每個個體向量的分量進行的。交叉操作的公式如下：

(13)

式中，CR為交叉概率，是區(qū)間[0,1]內(nèi)的一個常數(shù)；jrand是屬于集合{1,2,…,D}的隨機整數(shù)。

經(jīng)過變異交叉后，生成的試驗個體ui(G+1)與目標(biāo)個體xi(G)參照式(14)競爭選擇，生成下一代個體矢量。

(14)

(15)

最終通過差分進化算法得到最優(yōu)簇首節(jié)點，然后計算各自的成簇半徑，并對各簇內(nèi)節(jié)點按照到對應(yīng)簇首的距離編號(ID)，距離越近編號越小。

2.3 簇首更換機制

LEACH協(xié)議被麻省理工學(xué)院W.Heinzelman等人[3]提出，是最早的低功耗動態(tài)分簇自適應(yīng)路由協(xié)議，是應(yīng)用最廣泛的協(xié)議，也是后面很多學(xué)者提出的大部分路由協(xié)議的基礎(chǔ)。LEACH協(xié)議首次在無線傳感網(wǎng)的運轉(zhuǎn)中提出“輪”的概念，基本思想是：設(shè)定無線傳感器網(wǎng)絡(luò)中一次完整的數(shù)據(jù)采集為一輪，包括簇的建立和簇間數(shù)據(jù)傳輸兩個階段。每一輪簇首在簇的建立階段以預(yù)先設(shè)定的閾值為選擇標(biāo)準(zhǔn)，通過隨機的方式產(chǎn)生。LEACH協(xié)議的優(yōu)點是采用隨機選舉避免簇首能量過分消耗，缺點是網(wǎng)絡(luò)運轉(zhuǎn)過程中可能出現(xiàn)簇首分布不均的情況，距離匯聚節(jié)點過遠(yuǎn)的簇首能量消耗過大，簇首節(jié)點通信范圍內(nèi)覆蓋不到的孤立節(jié)點個數(shù)過多。為了解決無線傳感器網(wǎng)絡(luò)多跳路由中容易產(chǎn)生的“熱區(qū)”問題，一種非均勻分簇路由協(xié)議-EEUC協(xié)議被提出[6]。該協(xié)議與LEACH協(xié)議的最大差別是不需要在全局范圍內(nèi)選舉簇首，僅需在局部范圍內(nèi)實現(xiàn)簇首競選。EEUC協(xié)議每一輪也是由簇的建立和數(shù)據(jù)傳輸兩個階段構(gòu)成。EEUC協(xié)議是當(dāng)前比較有代表性的一個非均勻分簇路由協(xié)議，它的優(yōu)勢是利用大小不一的簇規(guī)模，通過均衡減少網(wǎng)絡(luò)節(jié)點能耗，延長了網(wǎng)絡(luò)的生命周期。它的缺陷是在候選簇首的抉擇上對地理位置和剩余能量等因素缺乏考慮，網(wǎng)絡(luò)動態(tài)性適用性較差。

在LEACH 協(xié)議和EEUC協(xié)議中，每輪均需要頻繁選取簇首或候選簇首，簇的結(jié)構(gòu)隨著輪數(shù)動態(tài)變化，大量的廣播消息消耗了過多的通信能量。因此本文所提算法設(shè)定選簇頻率f以降低建簇開銷。同時為了保證網(wǎng)絡(luò)正常工作，每輪運轉(zhuǎn)中都需要檢查當(dāng)前簇首的剩余能量。如果簇首的剩余能量低于能量閾值，則選擇簇中ID最小且剩余能量大于閾值的節(jié)點作為新的簇首。新的簇首節(jié)點向簇內(nèi)成員節(jié)點發(fā)送廣播信息，通知簇內(nèi)成員節(jié)點自己下一輪當(dāng)選為簇首節(jié)點。圖3示例具有ID號的傳感器節(jié)點的排序。能量閾值根據(jù)存活節(jié)點的信息由下式給出：

(16)

其中:countlive是存活節(jié)點總個數(shù)。

圖3 根據(jù)節(jié)點編號更換簇首示意圖

2.4 簇首間路由協(xié)議

簇首對簇內(nèi)的信息融合處理后以多跳的方式傳送給基站，中間轉(zhuǎn)發(fā)節(jié)點的選取和EEUC算法相同，在此不再贅述。針對空氣質(zhì)量監(jiān)測系統(tǒng)無線傳感網(wǎng)絡(luò)，本文所設(shè)計的非均勻分簇算法如圖4所示。

圖4 分簇算法流程圖

3 仿真實驗

為了驗證本文所提算法在空氣質(zhì)量檢測系統(tǒng)無線傳感網(wǎng)中的性能，利用Matlab仿真平臺經(jīng)過100次蒙特卡羅實驗對該算法進行評估與分析，并將其與LEACH和EEUC協(xié)議進行比較。實驗中所用的參數(shù)如表1所示。

根據(jù)3.1小節(jié)對最優(yōu)簇首數(shù)目的推導(dǎo)，在本文仿真的網(wǎng)絡(luò)環(huán)境下，最優(yōu)簇首數(shù)目Kopt=25。因此在差分進化算法尋找最優(yōu)簇首坐標(biāo)階段，種群規(guī)模NP=25。參照文獻(xiàn)[7]，差分進化迭代次數(shù)Iternum=800，F(xiàn)=0.6，CR=0.01。適應(yīng)度函數(shù)以最大化節(jié)點的覆蓋率為目標(biāo)，但在網(wǎng)絡(luò)運轉(zhuǎn)過程中，仍會出現(xiàn)簇首節(jié)點通信范圍內(nèi)覆蓋不到的區(qū)域，定義此區(qū)域內(nèi)的節(jié)點為孤立節(jié)點。表2給出了3種協(xié)議孤立節(jié)點個數(shù)隨著網(wǎng)絡(luò)運轉(zhuǎn)輪數(shù)的變化情況，本文所提算法用NEW代表。從表中可以看出，由于LEACH協(xié)議簇首分布不均，造成孤立節(jié)點數(shù)遠(yuǎn)大于其他兩種算法，節(jié)點利用率低。EEUC和本文所提算法孤立節(jié)點個數(shù)相差不大，但在前300輪生存時間內(nèi)，本文在所提算法節(jié)點利用率均高于LEACH 83%，也比EEUC提高了60%，從而采集信息的區(qū)域范圍更廣。

表1 實驗參數(shù)

表2 孤立節(jié)點個數(shù)比較

本文提出根據(jù)剩余能量和節(jié)點編號動態(tài)更換簇首的機制，和EEUC相比，省去了每輪選簇首和構(gòu)造簇結(jié)構(gòu)的通信開銷。通過對簇首能耗方差的比較，可以直觀地比較其能耗的均衡度，有效避免出現(xiàn)能量空洞問題的出現(xiàn)，從而延長網(wǎng)絡(luò)生命周期。圖5(a)比較了這3種算法中簇首能耗的方差，其中橫坐標(biāo)是在網(wǎng)絡(luò)生命周期內(nèi)隨機抽取的10輪。可以看出，本文所提算法和EEUC的方差波動浮動很小且相差不大，但均低于LEACH協(xié)議的方差。為了進一步比較本文所提算法和EEUC簇首能耗的優(yōu)劣，通過計算圖5(a)所示實驗中對應(yīng)簇首的剩余能量均值，其值如圖5(b)所示，可以得出本文算的簇首能耗較EEUC更低，從而可以延長節(jié)點的生存周期。

圖5 簇首能耗的相關(guān)比較

圖5從孤立節(jié)點個數(shù)和簇首的能耗兩個方面比較了3種算法。圖6針對整個網(wǎng)絡(luò)，從全局的角度出發(fā)，比較網(wǎng)絡(luò)生命周期。給出了3種算法網(wǎng)絡(luò)存活節(jié)點個數(shù)隨著運轉(zhuǎn)輪數(shù)變化的關(guān)系?？梢钥闯?，本文所提算法能夠顯著延長了第一個節(jié)點的死亡時間，整個網(wǎng)絡(luò)生命周期相較于LEACH和EEUC，分別提高了約55.6%和14.8%。由此可知本文所提算法能夠更好地均衡網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)的生命周期。

圖6 存活節(jié)點個數(shù)隨網(wǎng)絡(luò)運轉(zhuǎn)變化圖

4 結(jié)束語

本文從提高空氣質(zhì)量檢測系統(tǒng)無線傳感網(wǎng)的網(wǎng)絡(luò)生命周期出發(fā)，提出一種基于差分改進的非均勻分簇路由算法。本文所提算法有以下主要創(chuàng)新點:1)推導(dǎo)三維空間無線傳感網(wǎng)最優(yōu)簇首的計算，固定數(shù)目的簇首簡化分簇機制，節(jié)省節(jié)點間傳輸廣播消息的能耗；2)以高節(jié)點覆蓋率為目標(biāo)函數(shù)，同時考慮去除覆蓋冗余，利用差分進化算法尋找最優(yōu)簇首坐標(biāo)，減少簇首節(jié)點分布不合理帶來的能耗不均，孤立節(jié)點過多等問題；3)以成簇頻率和簇首編號來減少頻繁選簇，不僅可以解決簇首能耗不均導(dǎo)致的能量空洞問題，還可以均衡網(wǎng)絡(luò)中所有節(jié)點的能耗。通過仿真實驗證明，該算法能夠提高節(jié)點的利用率，有效延長空氣質(zhì)量檢測系統(tǒng)無線傳感的網(wǎng)絡(luò)生命周期。