基于三維空氣質量監(jiān)測系統的非均勻分簇算法

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

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

0 引言

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

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

圖1 無線傳感網分簇路由協議示意圖

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

1 網絡系統模型

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

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

2)BS位于網絡中心，其計算能力和能量均不受限制。

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

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

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

(1)

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

ER(l)=lEelec

(2)

2 算法描述

2.1 簇首數目的確定

網絡系統模型如上節(jié)所示，假設簇首數目為K，則平均簇內成員節(jié)點個數為N/K-1，簇首節(jié)點和簇成員節(jié)點的能耗分別為：

(3)

(4)

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

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

(5)

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

(6)

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

(7)

從而可得網絡運轉中每輪消耗的能量約為：

(8)

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

(9)

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

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

(10)

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

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

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

(13)

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

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

(14)

(15)

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

2.3 簇首更換機制

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

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

(16)

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

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

2.4 簇首間路由協議

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

圖4 分簇算法流程圖

3 仿真實驗

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

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

表1 實驗參數

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

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

圖5 簇首能耗的相關比較

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

圖6 存活節(jié)點個數隨網絡運轉變化圖

4 結束語

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