唐 勇
(南華大學(xué) 電氣工程學(xué)院,湖南 衡陽 421001)
無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是由若干分布在監(jiān)測區(qū)域內(nèi)的傳感器節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)。這些節(jié)點(diǎn)可以用于感知濕度、溫度、光照條件、地震活動等方面的數(shù)據(jù),在環(huán)境健康監(jiān)測、智能家居、精準(zhǔn)農(nóng)業(yè)、邊境監(jiān)控、智能制造等有著廣泛應(yīng)用。對于鈾尾礦的放射性污染的監(jiān)測就是無線傳感網(wǎng)在環(huán)境健康監(jiān)測應(yīng)用的一種。
鈾尾礦庫是一種低水平的核廢料處理場,對周圍環(huán)境和人類依然存在危害,故有必要對鈾尾礦庫附近的環(huán)境進(jìn)行長期放射性污染監(jiān)測。近年來,不少學(xué)者提出多種基于WSN 的檢測方法,但WSN 的傳感器節(jié)點(diǎn)采用電池供電,能量有限。要對鈾尾礦的放射性污染進(jìn)行長時(shí)間有效監(jiān)測,那么網(wǎng)絡(luò)壽命就成為一個(gè)評價(jià)WSN 檢測方法優(yōu)劣的重要性能參數(shù)。
降低能量消耗是延長WSN 網(wǎng)絡(luò)壽命的一個(gè)重要方向。冗余的網(wǎng)絡(luò)覆蓋和通信會造成不必要的能量消耗,而傳感器節(jié)點(diǎn)的休眠調(diào)度可以顯著提高資源效率,延長網(wǎng)絡(luò)壽命。因此許多學(xué)者對無線傳感網(wǎng)絡(luò)的節(jié)點(diǎn)休眠調(diào)度進(jìn)行了研究。
文獻(xiàn)[1]中,NDSCT 算法從傳感器節(jié)點(diǎn)休眠調(diào)度和傳感網(wǎng)絡(luò)分簇拓?fù)淇刂苾煞矫娼档途W(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)壽命。NDSCT 算法判別冗余節(jié)點(diǎn)的方法只能休眠那些感測區(qū)域被鄰居節(jié)點(diǎn)的感測區(qū)域完全覆蓋的節(jié)點(diǎn),而部分覆蓋的節(jié)點(diǎn)仍處于活躍狀態(tài)。NDSCT 算法在分簇階段采用LEACH 改進(jìn)型算法,引入了節(jié)點(diǎn)的剩余能量因子增大了剩余能量多的節(jié)點(diǎn)被選作簇頭的概率。一定程度上均衡了各節(jié)點(diǎn)能耗,但是并沒有解決簇頭分布不均勻以及單跳傳送能耗過大的問題。
Dong[2]等人提出一種SSM-PSO 算法,通過粒子群優(yōu)化算法快速選擇最優(yōu)的活躍節(jié)點(diǎn)集合,為監(jiān)測區(qū)域提供覆蓋。算法的粒子適應(yīng)度函數(shù)只考慮了覆蓋率、冗余比以及節(jié)點(diǎn)剩余能量,沒有從整個(gè)網(wǎng)絡(luò)的角度考慮網(wǎng)絡(luò)通信能耗是否為最優(yōu)。
文獻(xiàn)[3]中的RTPSO 算法通過粒子群優(yōu)化算法尋找盡可能多的不相交覆蓋集合來延長網(wǎng)絡(luò)壽命,算法只適用于監(jiān)測區(qū)域中部署大量傳感器節(jié)點(diǎn)的場景。
目前,休眠調(diào)度算法大多采用經(jīng)典的圓盤覆蓋模型,僅考慮單個(gè)傳感器的感知能力,未考慮待測物理量的空間相關(guān)特性和相鄰傳感器之間的協(xié)作感知能力。因此,本文采用一種更加符合實(shí)際應(yīng)用的新覆蓋模型,即可信信息覆蓋模型(Confident Information Coverage,CIC)[4]。相較于傳統(tǒng)覆蓋模型,CIC 模型有效擴(kuò)大了節(jié)點(diǎn)的感測區(qū)域,降低了活躍節(jié)點(diǎn)數(shù)量,通過相鄰節(jié)點(diǎn)之間的協(xié)作感知降低節(jié)點(diǎn)的覆蓋冗余,并保證覆蓋率不受影響。
本文基于粒子群優(yōu)化算法和CIC 覆蓋模型,提出一種新的節(jié)點(diǎn)休眠調(diào)度協(xié)議,用最少的活躍節(jié)點(diǎn)提供期望覆蓋,提高了網(wǎng)絡(luò)能耗效率,延長了WSN網(wǎng)絡(luò)壽命。
本文采用的節(jié)點(diǎn)覆蓋模型是可信信息覆蓋模型,與傳統(tǒng)的覆蓋模型相比,CIC 的獨(dú)特優(yōu)勢在于利用了環(huán)境變量蘊(yùn)含的空間特性和傳感器節(jié)點(diǎn)之間的協(xié)同感測能力。
CIC 模型如圖1 所示。CIC 的協(xié)同感測表現(xiàn)為,通過監(jiān)測區(qū)域內(nèi)傳感器節(jié)點(diǎn)s1,s,s3,s4收集的環(huán)境變量信息,對未被收集到信息的空間點(diǎn)p進(jìn)行信息重建獲得信息。未被收集到信息的空間點(diǎn)被稱為重建點(diǎn)(Reconstruction Point,RP)。
圖1 可信信息覆蓋模型與圓盤模型的對比
變程(Correlation Range,CR)描述了環(huán)境變量的空間相關(guān)性,在空間點(diǎn)p變程范圍內(nèi)傳感器節(jié)點(diǎn)的信息才能用于信息重建。
CIC 模型從信息重構(gòu)和估計(jì)的角度定義了覆蓋的概念。使用均方根誤差(Root Mean Square Error,RMSE)來評估重建點(diǎn)p的重建信息的估計(jì)質(zhì)量,該質(zhì)量可定義為:
式中:ut(p)表示p點(diǎn)處環(huán)境變量的真實(shí)值,u^t(p)表示其估計(jì)值。計(jì)算重建點(diǎn)p的RMSE值,當(dāng)計(jì)算值不大于閾值,即Y(p)≤RMSET,則認(rèn)為p點(diǎn)被可信信息覆蓋。當(dāng)監(jiān)測區(qū)域內(nèi)所有空間點(diǎn)都被可信信息覆蓋,則稱該區(qū)域被可信信息覆蓋。
假設(shè)在w×wm2大小的監(jiān)測區(qū)域中有一個(gè)環(huán)境變量需要被監(jiān)測,且它的空間相關(guān)范圍是CR。根據(jù)CIC 模型環(huán)境變量的空間相關(guān)性將監(jiān)測區(qū)域劃分為一系列邊長為CR的正方形網(wǎng)格,每個(gè)網(wǎng)格稱為一個(gè)重建區(qū)域Z={z1,z2,…,zi},每個(gè)網(wǎng)格的幾何中心就是重建點(diǎn)P={p1,p2,…,pi}。
一定數(shù)量的傳感器節(jié)點(diǎn)N={s1,s2,…,sn}被隨機(jī)部署在監(jiān)測區(qū)域中。當(dāng)一個(gè)或多個(gè)節(jié)點(diǎn)形成的集合在當(dāng)前方格p處環(huán)境變量的重構(gòu)誤差小于閾值時(shí)RMSEm<RMSET,則重建點(diǎn)p被CIC 覆蓋,該重建區(qū)域被CIC 覆蓋。每個(gè)重建區(qū)域的覆蓋函數(shù)定義如下:
同時(shí)定義CIC 部分覆蓋率的計(jì)算公式為:
定義1:覆蓋有效節(jié)點(diǎn),一個(gè)節(jié)點(diǎn)處于活躍或休眠狀態(tài),會影響該重建區(qū)域的CIC 覆蓋狀態(tài),那么該節(jié)點(diǎn)即為覆蓋有效節(jié)點(diǎn)。
定義2:覆蓋無效節(jié)點(diǎn),一個(gè)節(jié)點(diǎn)處于活躍或休眠狀態(tài),都不會影響該重建區(qū)域的CIC覆蓋狀態(tài),那么該節(jié)點(diǎn)即為覆蓋無效節(jié)點(diǎn)。
定義3:可信信息覆蓋集合,由同屬一個(gè)重建區(qū)域的一個(gè)或多個(gè)覆蓋有效節(jié)點(diǎn)組成,當(dāng)集合中所有節(jié)點(diǎn)處于活躍狀態(tài),可以使該重建區(qū)域被CIC 覆蓋;當(dāng)集合中缺少任何一個(gè)覆蓋有效節(jié)點(diǎn)都無法使重建區(qū)域再次被CIC 覆蓋。
定義4:簇頭候選集合,由所有覆蓋無效節(jié)點(diǎn)構(gòu)成,可信信息覆蓋集合出現(xiàn)一個(gè)節(jié)點(diǎn)死亡,集合中剩余節(jié)點(diǎn)也會加入簇頭候選集合。
在無線傳感網(wǎng)絡(luò)中,傳感器節(jié)點(diǎn)的能量消耗主要由感知能耗、通信能耗以及數(shù)據(jù)處理能耗組成。單個(gè)節(jié)點(diǎn)數(shù)據(jù)量少,感知和數(shù)據(jù)處理消耗的能量相較于通信消耗的能量可以忽略不計(jì),因此本文采用經(jīng)典能耗模型[5],只計(jì)算各傳感器節(jié)點(diǎn)si的通信能耗當(dāng)傳感器節(jié)點(diǎn)向dtm 內(nèi)的傳感器節(jié)點(diǎn)傳輸Lbit 數(shù)據(jù)時(shí),發(fā)送端傳感器節(jié)點(diǎn)消耗的能量計(jì)算公式為:
式中:Eelec是傳輸單比特?cái)?shù)據(jù)消耗的能量,εfs和εmp是功率放大電路能量損耗系數(shù),是傳輸距離閾值。
關(guān)于接收端傳感器節(jié)點(diǎn)在接收Lbit 數(shù)據(jù)消耗的能量計(jì)算公式如下:
簇頭節(jié)點(diǎn)總的通信能耗計(jì)算公式如下:
粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)[6]是一種先進(jìn)的群體智能優(yōu)化算法。單個(gè)粒子i由速度vi、當(dāng)前位置xi和最佳位置pi三個(gè)D維向量組成,D是搜索空間的維數(shù)。當(dāng)前位置xi是問題的當(dāng)前解決方案,適應(yīng)度函數(shù)用于衡量當(dāng)前位置xi的優(yōu)劣,并將當(dāng)前粒子最優(yōu)位置存儲在pi中,所有粒子pi中的全局最優(yōu)位置存儲在gi中。粒子的速度和位置更新公式為:
式中:t代表當(dāng)前迭代次數(shù),c1是粒子跟隨本身歷史最優(yōu)解的權(quán)重系數(shù),c2是粒子跟隨全局歷史最優(yōu)解的權(quán)重系數(shù)。r1和r2是[0,1]之間的隨機(jī)數(shù),ω是慣性權(quán)重。
粒子群優(yōu)化算法用于為監(jiān)測區(qū)域選擇最優(yōu)的可信信息覆蓋集與簇頭的組合,是離散問題,故本文采用一種離散二進(jìn)制粒子群算法(BPSO)[7]。粒子為D維二進(jìn)制向量,粒子速度更新公式與連續(xù)PSO 相同,粒子位置更新通過將速度轉(zhuǎn)化為概率來實(shí)現(xiàn)離散化。速度與概率的映射函數(shù)為:
式中:vid是粒子i的速度在d維方向上的速度分量。s(vid)在[0,1]之間取值,代表了粒子位置在d維的變化概率。粒子i的位置在d維方向上的更新公式為:
式中:r0是[0,1]之間的隨機(jī)數(shù)。當(dāng)隨機(jī)數(shù)r0小于粒子的速度映射概率時(shí),粒子的位置更新為1,否則為0,這樣保證了粒子的位置只在二進(jìn)制空間內(nèi)跳變。
為了有效解決針對監(jiān)測鈾尾礦庫對周圍環(huán)境的放射性污染而提出的節(jié)點(diǎn)休眠調(diào)度問題,提出了一種基于粒子群的無線傳感網(wǎng)絡(luò)可信信息覆蓋的節(jié)點(diǎn)休眠調(diào)度算法(SSMPSO-CIC)。SSMPSOCIC 算法分為3 個(gè)階段:初始化階段、搜索階段及監(jiān)測階段。本章將對SSMPSO-CIC 算法進(jìn)行詳細(xì)的描述。
在初始化階段,算法根據(jù)預(yù)先設(shè)定的變程長度將目標(biāo)監(jiān)測區(qū)域劃分為有限個(gè)方形重建區(qū)域,激活所有WSN 節(jié)點(diǎn)。各節(jié)點(diǎn)相互協(xié)作,確定它們在整個(gè)網(wǎng)絡(luò)中的相對位置以及它們所屬的重建區(qū)域和鄰居節(jié)點(diǎn)。節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)的位置信息和待測環(huán)境變量的物理特性構(gòu)建CIC 覆蓋。同時(shí)各節(jié)點(diǎn)也開始初始化自己的參數(shù),E0、Crt、RMSEt被初始化。
同時(shí),算法在初始化階段還需要確定每個(gè)重建區(qū)域中覆蓋有效節(jié)點(diǎn)和覆蓋無效節(jié)點(diǎn),根據(jù)可信信息覆蓋模型的定義識別每個(gè)重建區(qū)域中所有的可信信息覆蓋集合和簇頭候選節(jié)點(diǎn)。
利用離散粒子群優(yōu)化算法為待監(jiān)測區(qū)域選擇合適的可信信息覆蓋集合和簇頭,屬于覆蓋集和簇頭的傳感器節(jié)點(diǎn)被激活,進(jìn)入活躍狀態(tài),其他傳感器節(jié)點(diǎn)為了節(jié)省能量進(jìn)入休眠狀態(tài)。
3.2.1 粒子編碼
粒子采用二進(jìn)制編碼方式,粒子的維數(shù)是所有的可信信息覆蓋集合個(gè)數(shù)與簇頭候選節(jié)點(diǎn)個(gè)數(shù)的和。節(jié)點(diǎn)到粒子的映射Φ=[φ1,…,φn],φn={s1,…,sk}是由一個(gè)或多個(gè)節(jié)點(diǎn)組成的節(jié)點(diǎn)集合。當(dāng)節(jié)點(diǎn)都是有效節(jié)點(diǎn),就代表一個(gè)重建區(qū)域的可信信息覆蓋集合的ID。φ只由一個(gè)簇頭候選節(jié)點(diǎn)組成時(shí),那么φ是簇頭候選節(jié)點(diǎn)的ID,簇頭為普通節(jié)點(diǎn)中繼感知數(shù)據(jù)到匯聚節(jié)點(diǎn)。每個(gè)粒子代表一種休眠調(diào)度中節(jié)點(diǎn)的選取方案,編碼后粒子第m位為1,代表在Φ 中第m位可信信息覆蓋集合中的覆蓋有效節(jié)點(diǎn)將處于活躍狀態(tài),為所處的重建區(qū)域提供CIC 覆蓋,當(dāng)在Φ 中第n位對應(yīng)的簇頭候選節(jié)點(diǎn)被選為簇頭。而當(dāng)粒子第m或n位為0 時(shí),則Φ 對應(yīng)的簇頭候選節(jié)點(diǎn)或是可信信息覆蓋集合中的覆蓋有效節(jié)點(diǎn)選擇了休眠狀態(tài)。
3.2.2 適應(yīng)度函數(shù)
適應(yīng)度函數(shù)的設(shè)計(jì)直接反映了可信信息覆蓋集合和簇頭選取的要求。網(wǎng)絡(luò)的覆蓋率、網(wǎng)絡(luò)的整體能耗以及節(jié)點(diǎn)的剩余能量都是選擇可信信息覆蓋集合和簇頭需要考慮的重要參數(shù)。適應(yīng)度函數(shù)值越小,可信信息覆蓋集合和簇頭選取的結(jié)果越優(yōu)。粒子整體適應(yīng)度函數(shù)為:
式中:α、β、χ為權(quán)重系數(shù),f1是有關(guān)網(wǎng)絡(luò)覆蓋率的適應(yīng)度函數(shù),f2是關(guān)于網(wǎng)絡(luò)整體能耗的適應(yīng)度函數(shù),f3是有關(guān)節(jié)點(diǎn)剩余能量的適應(yīng)度函數(shù)。
3.2.2.1 網(wǎng)絡(luò)的覆蓋率
節(jié)點(diǎn)的休眠調(diào)度方案首先要滿足網(wǎng)絡(luò)的期望覆蓋率,本文設(shè)計(jì)了網(wǎng)絡(luò)覆蓋率的適應(yīng)度函數(shù)
式中:|Z|代表了監(jiān)測區(qū)域中重建區(qū)域的個(gè)數(shù),υj(Φ)表示在所有可信信息覆蓋集只要存在一個(gè)覆蓋集覆蓋了第j個(gè)重建區(qū)域,則υj(Φ)值為1,否則為0。
3.2.2.2 網(wǎng)絡(luò)的整體能耗
3.2.2.3 節(jié)點(diǎn)的剩余能量
為了使剩余能量大的節(jié)點(diǎn)有更高的概率被選中進(jìn)入活躍狀態(tài),本文在適應(yīng)度函數(shù)中引入節(jié)點(diǎn)剩余能量因子,公式如下:
在監(jiān)測階段,先進(jìn)的數(shù)據(jù)路由策略可以顯著節(jié)省各節(jié)點(diǎn)的通信能耗。先進(jìn)的數(shù)據(jù)路由策略主要體現(xiàn)在選出的簇頭是否更加合理。SSMPSO-CIC 算法在選擇簇頭時(shí)采用兩種策略相結(jié)合的方式。當(dāng)簇頭候選集合中的節(jié)點(diǎn)數(shù)量大于閾值時(shí),簇頭都通過離散粒子群算法選出。而當(dāng)簇頭候選集合中的節(jié)點(diǎn)數(shù)量小于閾值時(shí),采用LEACH-OR[8]改進(jìn)算法從處于活躍狀態(tài)的有效節(jié)點(diǎn)中選出合適節(jié)點(diǎn)充當(dāng)簇頭。
LEACH-OR 改進(jìn)算法將節(jié)點(diǎn)的剩余能量以及與匯聚節(jié)點(diǎn)的距離兩個(gè)參數(shù)引入概率閾值公式,保證了選出的簇頭節(jié)點(diǎn)是簇頭候選節(jié)點(diǎn)或者剩余能量高的覆蓋有效節(jié)點(diǎn),同時(shí)還能保證簇頭在網(wǎng)絡(luò)中分布均勻。每個(gè)節(jié)點(diǎn)在每輪監(jiān)測中都會生成一個(gè)[0,1]的隨機(jī)概率值,當(dāng)這個(gè)隨機(jī)概率值小于閾值時(shí)節(jié)點(diǎn)為簇頭節(jié)點(diǎn),最終形成一個(gè)簇頭節(jié)點(diǎn)集合。成為簇頭的概率閾值公式T(si,r)如下:
式中:si代表ID 為i的傳感器節(jié)點(diǎn),r為當(dāng)前輪數(shù),Ψ是簇頭候選集合,p是簇頭節(jié)點(diǎn)數(shù)量在總活躍節(jié)點(diǎn)數(shù)中所占的比例,G為在1/p輪中未當(dāng)選簇頭的節(jié)點(diǎn)集合。為了使距離匯聚節(jié)點(diǎn)近且剩余能量高的節(jié)點(diǎn)更大概率當(dāng)選為簇頭,設(shè)置了一個(gè)含能量和距離的控制參數(shù)Qi(r)[8]。
為了驗(yàn)證SSMPSO-CIC 算法的有效性,通過Matlab 平臺做了大量仿真實(shí)驗(yàn),獲得了許多實(shí)驗(yàn)數(shù)據(jù),并對實(shí)驗(yàn)數(shù)據(jù)作相應(yīng)的分析,證明了所提出的SSMPSO-CIC算法與SSMPSO-Disk[9]、NDSCT、LEACH-OR 算法在網(wǎng)絡(luò)壽命方面的優(yōu)勢。
仿真實(shí)驗(yàn)的基本參數(shù)如表1所示。仿真實(shí)驗(yàn)中,節(jié)點(diǎn)隨機(jī)分布在監(jiān)測范圍內(nèi),仿真實(shí)驗(yàn)一共為200輪次。
表1 仿真參數(shù)設(shè)置
圖2 表示了在同一監(jiān)測區(qū)域中部署不同節(jié)點(diǎn)數(shù)量情形下四種算法關(guān)于一輪調(diào)度中平均活躍節(jié)點(diǎn)數(shù)量的對比。LEACH-OR 算法只改進(jìn)簇頭選舉策略,未采用節(jié)點(diǎn)休眠調(diào)度,所有節(jié)點(diǎn)都處于活躍狀態(tài),所以LEACH-OR 算法的平均活躍節(jié)點(diǎn)數(shù)是4 個(gè)算法中最多的。NDSCT 算法識別冗余節(jié)點(diǎn)的方法過于簡單,性能不及同樣采用圓盤覆蓋模型的SSMPSO-Disk 算法。SSMPSO-Disk 算法采用粒子群優(yōu)化算法識別冗余節(jié)點(diǎn),然后休眠冗余節(jié)點(diǎn)降低了平均活躍節(jié)點(diǎn)數(shù)。SSMPSO-CIC 算法采用可信信息覆蓋模型,只需要最少的活躍節(jié)點(diǎn)數(shù)量就可以滿足網(wǎng)絡(luò)的覆蓋要求。
圖2 不同算法的平均活躍節(jié)點(diǎn)數(shù)量
圖3 顯示了在同一監(jiān)測區(qū)域中部署不同節(jié)點(diǎn)數(shù)量情形下四種算法關(guān)于網(wǎng)絡(luò)壽命的數(shù)據(jù)對比。LEACH-OR 算法使簇頭分布更加合理,減小了節(jié)點(diǎn)間的通信能耗,一定程度上延長了網(wǎng)絡(luò)壽命。NDSCT 算法、SSMPSO-Disk 算法和SSMPSO-CIC算法除了在數(shù)據(jù)路由方面降低能耗外,還通過節(jié)點(diǎn)休眠調(diào)度減少活躍節(jié)點(diǎn)數(shù)量,增加覆蓋集延長網(wǎng)絡(luò)壽命。由于SSMPSO-CIC 算法采用先進(jìn)的可信信息覆蓋模型,故網(wǎng)絡(luò)壽命最優(yōu)。
圖3 不同算法的網(wǎng)絡(luò)壽命
SSMPSO-CIC 算法是以NDSCT 算法和LEACHOR 算法原理為基礎(chǔ),針對相關(guān)缺陷采用可信信息覆蓋模型和粒子群算法進(jìn)行改進(jìn)的一種先進(jìn)的休眠調(diào)度算法。從仿真結(jié)果可以看出,SSMPSO-CIC 算法活躍節(jié)點(diǎn)數(shù)更少,網(wǎng)絡(luò)壽命更長。