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

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

0 引言

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

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

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

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

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

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

1)所有傳感器節(jié)點(diǎn)和BS在隨機(jī)撒布后位置不再發(fā)生移動(dòng)。

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

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

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

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

(1)

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

ER(l)=lEelec

(2)

2 算法描述

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

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

(3)

(4)

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

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

(5)

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

(6)

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

(7)

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

(8)

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

(9)

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

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

(10)

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

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

(11)

進(jìn)化階段包含變異、交叉和選擇個(gè)操作步驟。其中變異采用如式(12)所示的策略，得到子代變異個(gè)體vi(G+1)。其中，xt1(G)表示第G代種群的第t1個(gè)個(gè)體；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)

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

(13)

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

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

(14)

(15)

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

2.3 簇首更換機(jī)制

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

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

(16)

其中:countlive是存活節(jié)點(diǎn)總個(gè)數(shù)。

圖3 根據(jù)節(jié)點(diǎn)編號(hào)更換簇首示意圖

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

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

圖4 分簇算法流程圖

3 仿真實(shí)驗(yàn)

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

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

表1 實(shí)驗(yàn)參數(shù)

表2 孤立節(jié)點(diǎn)個(gè)數(shù)比較

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

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

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

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

4 結(jié)束語(yǔ)

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