基于種群閾值優(yōu)化機制的WSN均衡覆蓋算法

劉 東 旭

(滁州職業(yè)技術(shù)學(xué)院 信息工程學(xué)院， 安徽 滁州 239500 )

0 前言

WSN(wireless sensor network，無線傳感網(wǎng))技術(shù)是大數(shù)據(jù)及人工智能技術(shù)發(fā)展的新方向[1]。WSN技術(shù)主要立足于智能傳感技術(shù)，采取自組織方式組網(wǎng)并通過傳感器將數(shù)據(jù)發(fā)送至基站節(jié)點(sink節(jié)點)，從而實現(xiàn)區(qū)域覆蓋及數(shù)據(jù)感知[2]。由于傳感節(jié)點同時具有易損特性，因此如何高效部署節(jié)點并提升節(jié)點均衡覆蓋能力，成為當(dāng)前研究的熱點之一[3]。

實踐中，主要采取策略部署、能量感知等方式提升節(jié)點的覆蓋性能，在能量消耗可控的前提下盡量提高傳感節(jié)點對區(qū)域的覆蓋強度，以增強網(wǎng)絡(luò)覆蓋比例，減少因覆蓋不到位而導(dǎo)致的區(qū)域空洞現(xiàn)象。文獻[4]中提出一種基于節(jié)點分簇機制的WSN均衡覆蓋算法，通過主備機制實現(xiàn)對區(qū)域的多重覆蓋，采用周期交替休眠模式對區(qū)域進行重疊覆蓋。采用該算法，可在很大程度上避免因節(jié)點失效而導(dǎo)致無法覆蓋的問題，網(wǎng)絡(luò)覆蓋比例較高。但是，該算法因主備節(jié)點更換頻繁而加劇能量消耗，易致節(jié)點受限，從而降低網(wǎng)絡(luò)覆蓋性能。文獻[5]中提出一種基于聚類分簇機制的WSN均衡覆蓋算法，對具有相似采集特性的節(jié)點進行聚類處理，以減少因區(qū)域分割而導(dǎo)致的重疊覆蓋現(xiàn)象。該算法所選簇頭節(jié)點的覆蓋能力較強，能夠適應(yīng)鏈路抖動頻繁的實際部署場景。但該算法也存在節(jié)點密度不均衡的特點，特別是網(wǎng)絡(luò)傳輸率較高時易出現(xiàn)聚類冗余度較高的問題，使節(jié)點覆蓋區(qū)域效果變差。文獻[6]中提出一種基于鏈路切換機制的WSN均衡覆蓋算法，對抖動頻繁的所有鏈路進行主備節(jié)點變換處理，以減少因鏈路抖動而導(dǎo)致的節(jié)點覆蓋能力下降問題。但由于鏈路切換過程中需要反復(fù)更換簇頭節(jié)點，使得節(jié)點能量消耗問題難以控制，因而節(jié)點易出現(xiàn)大面積受限現(xiàn)象。

為了彌補上述方法的不足，本次研究將提出一種新算法 —— 基于種群閾值優(yōu)化機制的WSN均衡覆蓋算法。首先，在新算法中引入定位機制，對節(jié)點坐標(biāo)及坐標(biāo)漂移進行周期量化迭代，當(dāng)傳感節(jié)點覆蓋度較高時即進行坐標(biāo)更新處理，從而提高網(wǎng)絡(luò)區(qū)域覆蓋強度。同時，設(shè)計了基于閾值優(yōu)化機制的節(jié)點均衡方法，引入簇內(nèi)最低覆蓋距離等參數(shù)，采取交叉判定方式降低節(jié)點迭代次數(shù)，改善重復(fù)覆蓋現(xiàn)象，較好地起到了均衡覆蓋的作用。最后，通過仿真實驗驗證算法的覆蓋能力及節(jié)點離散性能。

1 WSN均衡覆蓋算法設(shè)計

WSN均衡算法包括兩部分：基于種群周期更新機制的定位覆蓋和基于閾值優(yōu)化機制的節(jié)點均衡。

1.1 基于種群周期更新機制的定位覆蓋

首先，將網(wǎng)絡(luò)節(jié)點視為粒子，各分區(qū)內(nèi)的能量最優(yōu)粒子即其區(qū)內(nèi)能量最高的節(jié)點。將這些能量最優(yōu)粒子設(shè)定為簇頭節(jié)點(cluster head nodes，CH節(jié)點)，各粒子可根據(jù)定位算法[7]獲取當(dāng)前坐標(biāo)X(x，y)和坐標(biāo)漂移ΔX(x，y)。對所獲取的坐標(biāo)X(x，y)和坐標(biāo)漂移ΔX(x，y)進行迭代，迭代模型為：

ΔX(x，y)[k+1]=X(x，y)[k]，

ΔX(x，y)[k]

(1)

ΔX(x，y)[k+1]=ΔX(x，y)[k]，

ΔX(x，y)[k]≥f[k+1]

(2)

式中：X(x，y)[k]表示第k個傳輸周期所獲取的節(jié)點坐標(biāo)；ΔX(x，y)[k]表示第k個傳輸周期所獲取的坐標(biāo)漂移；f[k+1]表示迭代裁決函數(shù)，獲取模型為：

f[k+1]=min{f[k]，f[k-1]，…}

(3)

f[1]=ΔX(x，y)

(4)

對于迭代過程，需要考慮終止因素。這是因為，節(jié)點定位過程需要消耗能量，若頻繁進行迭代將會導(dǎo)致節(jié)點能量受限而覆蓋受阻[8]。在此，通過覆蓋集中度(coverage concentration，CC)和覆蓋次集中度(coverage sub concentration，CSC)函數(shù)對迭代過程進行控制。其相關(guān)定義滿足以下模型：

(5)

(6)

當(dāng)CC值接近于1時，說明各節(jié)點在第k次傳輸周期內(nèi)均分布集中于簇頭節(jié)點，此時需要進行迭代以便實現(xiàn)均衡覆蓋。當(dāng)CSC值接近于1時，說明各節(jié)點在第k次傳輸周期內(nèi)均具有離散特性，分布較為均衡，無須進行迭代。圖1所示為基于種群周期更新機制的定位覆蓋流程。

按圖1所示流程完成種群周期更新后，簇頭節(jié)點即為能量最高的節(jié)點，其余節(jié)點可通過種群周期更新進一步實現(xiàn)分布離散化，從而擴大節(jié)點對區(qū)域的覆蓋強度，提高網(wǎng)絡(luò)覆蓋質(zhì)量。

sink節(jié)點為超級節(jié)點，因此其搜尋過程中的能量消耗可忽略不計，整個搜尋流程遵照模型(1)、(2)所示遍歷算法。若種群中的粒子數(shù)為n，則搜索過程中的時間復(fù)雜度為o(n)，空間復(fù)雜度為T(n)。

1.2 基于閾值優(yōu)化機制的節(jié)點均衡

由前述基于種群周期更新機制的定位覆蓋方法可知，節(jié)點完成迭代過程后將圍繞簇頭節(jié)點并實現(xiàn)離散化分布。考慮到節(jié)點的移動特性[9]，進一步對其進行均衡處理，以便降低能耗及提高簇內(nèi)覆蓋比例。實現(xiàn)步驟如下：

Step1逐個獲取簇內(nèi)節(jié)點，按模型(7)獲取覆蓋閾值D(x，y)[k]：

(7)

式中：(x0，y0)表示簇頭節(jié)點坐標(biāo)；(x，y)表示當(dāng)前節(jié)點坐標(biāo)；l表示簇頭節(jié)點最低覆蓋距離。

Step2獲取覆蓋閾值D(x，y)[k]后，按模型(8)構(gòu)建交叉判定閾值Δ[k]：

Δ[k]=D(x，y)[k]-D(x，y)[k-1]

(8)

Step3當(dāng)且僅當(dāng)Δ[k]大于0時，說明節(jié)點在第k個傳輸周期內(nèi)可通過移動位置對簇內(nèi)區(qū)域進行再覆蓋，裁決方法如下：

Δ[k]>0，mov[k]

(9)

Δ[k]<0，mov[k-1]

(10)

式中：mov表示位移操作，位移距離lmov滿足式(11)：

lmov=ΔX(x，y)

(11)

由此可知，節(jié)點在移動過程中的位移距離lmov將由交叉判定閾值Δ[k]決定，且節(jié)點移動過程均在簇內(nèi)區(qū)域，移動的距離在數(shù)值上將不大于簇頭節(jié)點最低覆蓋距離；因此，節(jié)點與簇頭之間的通信距離亦在1跳范圍之內(nèi)，節(jié)點在通信過程中的額外能量消耗將不會增加。但就簇頭而言，其成員節(jié)點移動后的分布得到均衡，因此各節(jié)點間通信干擾亦得到緩解，從而使簇頭的覆蓋能力得到提高，實現(xiàn)與簇內(nèi)節(jié)點通信整體能耗均衡。

Step4在獲取節(jié)點位移后，算法將自動轉(zhuǎn)入Step 1并獲取下一個節(jié)點的覆蓋閾值，本次流程結(jié)束。

在節(jié)點處于移動狀態(tài)時，當(dāng)且僅當(dāng)其處于簇頭覆蓋范圍內(nèi)與簇頭節(jié)點存在信息交互關(guān)系，按模型(9)、(10)進行裁決時將始終位于簇頭節(jié)點的覆蓋半徑之內(nèi)，因此通信過程中的能量消耗較為均衡?？紤]到粒子覆蓋過程具有周期特性，在能量最高節(jié)點的能量消耗增加時，可從剩余節(jié)點中選取能量較高的節(jié)點作為新簇頭節(jié)點，并按模型(7)所示的閾值重新進行更新。因此，能量最優(yōu)節(jié)點的更迭將不會影響到后續(xù)算法執(zhí)行。

在實現(xiàn)了基于閾值優(yōu)化機制的節(jié)點均衡之后，簇頭節(jié)點將能發(fā)揮最大的覆蓋作用，且其余傳感節(jié)點與簇頭節(jié)點間的距離較為均衡，節(jié)點間交叉覆蓋現(xiàn)象出現(xiàn)的概率將顯著降低，網(wǎng)絡(luò)均衡覆蓋效果得以提高，節(jié)點覆蓋性能將始終保持較高的離散程度。此時，網(wǎng)絡(luò)覆蓋將達到最優(yōu)狀態(tài)。

2 仿真實驗結(jié)果分析

以Matlab仿真平臺作為實驗環(huán)境驗證算法的性能[10]，仿真參數(shù)如表1所示。對照組算法為當(dāng)前無線傳感網(wǎng)覆蓋領(lǐng)域內(nèi)常用的算法：基于對稱探測機制的無線傳感網(wǎng)空洞覆蓋算法[11](symmetric algorithm for detection of coverage hole in wireless sensor network，SDCH算法)和基于最大目標(biāo)匹配機制的無線傳感網(wǎng)覆蓋算法[12](maximum target coverage problem in mobile wireless sensor networks，MT算法)。選取2項仿真指標(biāo)：網(wǎng)絡(luò)區(qū)域覆蓋率和離散節(jié)點數(shù)量。

表1 仿真參數(shù)表

2.1 網(wǎng)絡(luò)區(qū)域覆蓋率分析

對比本次算法與SDCH、MT算法在2種信道條件下的網(wǎng)絡(luò)區(qū)域覆蓋率測試結(jié)果，如圖2所示?？梢钥闯?，本次算法具有網(wǎng)絡(luò)區(qū)域覆蓋率較高的特點，覆蓋性能較優(yōu)越。

圖2 網(wǎng)絡(luò)區(qū)域覆蓋率測試

本次算法中，針對節(jié)點重復(fù)覆蓋問題設(shè)計了基于種群周期更新機制的定位覆蓋方法和基于閾值優(yōu)化機制的節(jié)點均衡方法。其中節(jié)點可通過反復(fù)迭代的方式對目標(biāo)區(qū)域進行多次覆蓋，且能夠通過閾值模式調(diào)節(jié)迭代次數(shù)及方位，網(wǎng)絡(luò)區(qū)域覆蓋強度較大，因而區(qū)域覆蓋率較高。

SDCH算法中，根據(jù)網(wǎng)關(guān)性能參數(shù)、網(wǎng)關(guān)選擇準(zhǔn)則函數(shù)和對稱函數(shù)，建立了基于對稱網(wǎng)絡(luò)模型的節(jié)點覆蓋機制，利用多徑傳輸優(yōu)化因子計算相似度，采用加權(quán)平均法檢測無線傳感器網(wǎng)絡(luò)的覆蓋空洞，可消除因覆蓋不完全而導(dǎo)致的節(jié)點失效現(xiàn)象。然而，該算法未通過再覆蓋方式對節(jié)點進行移位處理，難以適應(yīng)拓?fù)渥儎虞^快的部署環(huán)境，易發(fā)生節(jié)點失效現(xiàn)象，因此網(wǎng)絡(luò)區(qū)域覆蓋率相低于本算法。

MT算法中，采用啟發(fā)模型對覆蓋區(qū)域進行著色，降低了因拓?fù)渥儎虞^快而導(dǎo)致的覆蓋失效現(xiàn)象。該算法所選簇頭節(jié)點能量較低，未采用迭代機制對簇頭節(jié)點進行更迭處理，所布節(jié)點分布較為集中。因此，該算法的網(wǎng)絡(luò)區(qū)域覆蓋率亦顯著低于本算法。

2.2 離散節(jié)點數(shù)量分析

對比本次算法與SDCH、MT算法在兩種信道條件下的離散節(jié)點數(shù)量測試結(jié)果，如圖3所示?？梢钥闯?，本次算法具有離散節(jié)點數(shù)量較大的特點，顯示出了較強的均衡覆蓋特性。

圖3 離散節(jié)點數(shù)量測試

本次算法中，針對拓?fù)渥儎虞^快而導(dǎo)致的網(wǎng)絡(luò)區(qū)域覆蓋性能下降現(xiàn)象，設(shè)計了基于種群周期更新機制的定位覆蓋方法用以提升節(jié)點部署性能。特別是針對節(jié)點頻繁迭代而出現(xiàn)的能量受限問題，設(shè)計了基于閾值優(yōu)化機制的節(jié)點均衡方法，可在降低節(jié)點能量消耗水平的前提下提高節(jié)點離散性能。對比之下，本次算法的離散節(jié)點數(shù)量較高。

SDCH算法中，基于對稱網(wǎng)絡(luò)模型設(shè)計了一種新的節(jié)點覆蓋機制，主要采用網(wǎng)關(guān)性能參數(shù)、網(wǎng)關(guān)選擇準(zhǔn)則函數(shù)和對稱函數(shù)，并通過相似度模型監(jiān)測覆蓋空洞現(xiàn)象，以提高節(jié)點的覆蓋性能。不過，該算法中未采取周期機制提升節(jié)點覆蓋效率，所選簇頭節(jié)點易因頻繁監(jiān)測而出現(xiàn)受限現(xiàn)象，節(jié)點覆蓋性能較差且分布較為集中。因此，該算法的離散節(jié)點數(shù)量相對低于本次算法。

對于MT算法，其主要采用啟發(fā)模型來完成網(wǎng)絡(luò)覆蓋，但是其所選擇的簇頭節(jié)點性能不佳，隨著網(wǎng)絡(luò)運行時間的延長，其能量被快速消耗，導(dǎo)致其覆蓋效果較差，從而使得離散節(jié)點大幅增加。

3 結(jié) 語

為了提高無線傳感網(wǎng)的區(qū)域覆蓋能力，并進一步增強其覆蓋均衡效果，提出了一種基于種群閾值優(yōu)化機制的WSN均衡覆蓋算法。本算法主要由基于種群周期更新機制的定位覆蓋方法和基于閾值優(yōu)化機制的節(jié)點均衡方法兩部分構(gòu)成，可提高網(wǎng)絡(luò)區(qū)域覆蓋強度，優(yōu)化節(jié)點分布并增強節(jié)點離散能力，具有較為優(yōu)越的網(wǎng)絡(luò)覆蓋效果。