改進(jìn)PSO結(jié)合DSA技術(shù)的無線傳感器網(wǎng)絡(luò)均衡密度聚類方法

任昌鴻 安 軍

1(重慶師范大學(xué)涉外商貿(mào)學(xué)院信息技術(shù)中心 重慶 401520)2(重慶工商大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院 重慶 400030)

0 引 言

伴隨著信息時代的發(fā)展以及物聯(lián)網(wǎng)技術(shù)的出現(xiàn)，無線傳感器網(wǎng)絡(luò)領(lǐng)域的研究也受到了極大的關(guān)注[1-3]。在網(wǎng)絡(luò)中使用的傳感器節(jié)點因其獨有的特性在各種應(yīng)用中得到了廣泛的應(yīng)用，這些節(jié)點能夠檢測和監(jiān)測物理現(xiàn)象的變化。但它們的設(shè)計存在兩個問題：(1) 傳感器的有限壽命，因為它們由小電池供電；(2) 選擇應(yīng)用程序采用的部署方法，其中最重要的環(huán)節(jié)是聚類過程，而影響聚類過程的重要因素之一就是Cluster Head(CH)節(jié)點的分布。因此，研究WSN中的聚類方法具有很好的現(xiàn)實意義和實用價值[4-5]。

國內(nèi)外許多專家及學(xué)者圍繞WSN中的聚類方法展開了深入的研究。文獻(xiàn)[6]研究了一種利用低能量自適應(yīng)聚類層次協(xié)議的無線傳感器網(wǎng)絡(luò)的動態(tài)聚類技術(shù)，該技術(shù)提供了一種簡單的機制，可以將大量節(jié)點組織到集群中，并定期更改網(wǎng)絡(luò)中每個節(jié)點的角色。然而，它沒有考慮CH節(jié)點的分布和生成的集群的大小。文獻(xiàn)[7]提出一種混合能量分布式聚類協(xié)議，并制定了延長網(wǎng)絡(luò)生命周期的兩個重要指標(biāo)。這些指標(biāo)是剩余能量和集群內(nèi)通信成本，但它是一種迭代技術(shù)，會消耗更多的開銷。文獻(xiàn)[8]基于遺傳算法提出了一種新的適用于無線傳感器網(wǎng)絡(luò)的聚類技術(shù)，其目標(biāo)函數(shù)最小化了從成員節(jié)點到其相關(guān)CH之間的總距離。文獻(xiàn)[9]使用粒子群優(yōu)化來產(chǎn)生一種節(jié)能聚類技術(shù)，其目標(biāo)函數(shù)最小化成員節(jié)點及其相關(guān)CH之間的平均距離以及所有節(jié)點的總初始能量與候選CH的總能量之比。文獻(xiàn)[10]提出一種節(jié)能聚類方案協(xié)議，該協(xié)議基于競爭機制從一組隨機選擇的候選節(jié)點中選擇作為其鄰居之間具有較高剩余能量的節(jié)點，剩余節(jié)點基于成本函數(shù)加入集群，但初始隨機選擇的候選CH節(jié)點可能產(chǎn)生不均勻的分布。因此，以上方法仍然具有一定的創(chuàng)新和改進(jìn)空間[11-12]。

針對以上問題，提出一種改進(jìn)粒子群算法結(jié)合DSA技術(shù)的無線傳感器網(wǎng)絡(luò)均衡密度聚類方法，實現(xiàn)了對網(wǎng)絡(luò)CH節(jié)點能耗均衡分簇的有效性。其主要創(chuàng)新點為：

(1) 現(xiàn)有的大多數(shù)方法中，沒有考慮節(jié)點的分布和生成的集群的大小，而本文方法利用改進(jìn)粒子群算法優(yōu)化能量均衡分簇算法以促進(jìn)網(wǎng)絡(luò)能耗均衡分布，避免了網(wǎng)絡(luò)熱點問題并最大化傳感器網(wǎng)絡(luò)壽命。

(2) 現(xiàn)有的大多數(shù)方法中，均采用迭代技術(shù)，通常會消耗較多的開銷，而本文方法利用基于分布式空間分析(Distributed Space Analysis,DSA)的聚類技術(shù)，實現(xiàn)了整個構(gòu)建集群的能耗均衡。

(3) 現(xiàn)有的大多數(shù)方法中，初始隨機選擇的候選節(jié)點可能產(chǎn)生不均勻的分布，而本文方法融合了兩種算法的優(yōu)勢，加快了算法聚類收斂速度。

實驗結(jié)果表明，本文方法與其他聚類技術(shù)相比，實現(xiàn)了更低的功耗，因此網(wǎng)絡(luò)壽命更長。

1 方法設(shè)計

在無線傳感器網(wǎng)絡(luò)中，首先利用改進(jìn)粒子群算法結(jié)構(gòu)簡單尋優(yōu)速度快等優(yōu)點，優(yōu)化能量均衡分簇算法，促進(jìn)網(wǎng)絡(luò)能耗均衡分布，避免了網(wǎng)絡(luò)熱點問題，同時使傳感器網(wǎng)絡(luò)壽命最大化。然后結(jié)合基于分布式空間分析的聚類技術(shù)，充分利用分布式計算資源，合理聚類并分配網(wǎng)絡(luò)能耗，實現(xiàn)了整個無線傳感器網(wǎng)絡(luò)中集群構(gòu)建的能耗均衡。通過兩種算法的深度融合，克服對初始聚類中心點選擇等敏感問題的同時加快了聚類收斂速度，形成了傳感器節(jié)點位置的最優(yōu)分簇。

1.1 改進(jìn)PSO在網(wǎng)絡(luò)均衡密度聚類過程中的應(yīng)用

1) 算法思想。在無線傳感器網(wǎng)絡(luò)中，首先需要確定活動區(qū)域等級并部署粒子，其中粒子數(shù)量與此區(qū)域內(nèi)的傳感器節(jié)點數(shù)量相等。對粒子飛行規(guī)則進(jìn)行適當(dāng)修改，當(dāng)粒子位置與傳感器節(jié)點位置相同時，將停止運動并固定位置，其余未到達(dá)與傳感器節(jié)點相同位置的粒子則將會繼續(xù)按照既定規(guī)則飛行，直至與對應(yīng)的傳感器位置節(jié)點重合為止；當(dāng)所有粒子都在位置重合后停止運動時，算法完成分簇并轉(zhuǎn)移到下一等級區(qū)域繼續(xù)執(zhí)行分簇操作[13]。

2) 算法改進(jìn)。

(1) 在對應(yīng)等級區(qū)域中k個聚類的粒子群體Ci(i=1，2，…，k)經(jīng)改進(jìn)PSO算法修改后可表示為：

(1)

(2) 不同于一般的粒子群飛行規(guī)則，修改后的粒子位置和速度都按照自身最優(yōu)和群體最優(yōu)的原則進(jìn)行運動，并且在聚類過程中，當(dāng)粒子運動到的位置與傳感器節(jié)點所處位置相重合時才會收斂。此時粒子速度減小為0，位置固定不變，剩余未重合粒子則將按照上述規(guī)則繼續(xù)飛行，直至所有粒子位置與傳感器節(jié)點位置重合，輸出無線傳感器節(jié)點網(wǎng)絡(luò)的最優(yōu)分簇聚類結(jié)果。

3) 算法基本步驟。

(1) 無線傳感器網(wǎng)絡(luò)等級區(qū)域可以根據(jù)與匯聚節(jié)點的距離進(jìn)行劃分。通過選取不同簇投確定不同等級區(qū)域中的簇數(shù)以及簇規(guī)模。然后選定活動節(jié)點，通常選取第一等級區(qū)域，假定其余等級區(qū)域節(jié)點為休眠狀態(tài)，從而避免不同等級區(qū)域粒子之間的相互干擾。

(2) 粒子群參數(shù)初始化。隨機生成多個粒子，粒子總數(shù)與改進(jìn)后的傳感器節(jié)點數(shù)相同。

(3) 采用K-均值聚類計算聚類總數(shù)k和聚類中心ci。

(4) 根據(jù)類相似度和類間間距對粒子作出適應(yīng)度評價，并采用鄰近歐幾里得距離所度量的聚類質(zhì)量作為優(yōu)化目標(biāo)函數(shù)，具體表示如下：

(2)

式中：dist是測量對象之間的標(biāo)準(zhǔn)歐幾里得距離；x是粒子個體；K是聚類數(shù)。

(6) 判斷粒子位置。當(dāng)vi=0，xi=xsensor時粒子速度減小為0，位置固定不變。

(7) 更新其余粒子的xi和vi。

(8) 重復(fù)步驟(3)-步驟(7)直至所有粒子位置與傳感器節(jié)點位置重合，完成對應(yīng)等級區(qū)域內(nèi)的傳感器節(jié)點分簇，輸出無線傳感器節(jié)點網(wǎng)絡(luò)的最優(yōu)分簇聚類結(jié)果。

(9) 喚醒(n-1)R

算法流程如圖1所示。

圖1 改進(jìn)粒子群算法的能量均衡密度聚類方法流程圖

1.2 利用DSA實現(xiàn)能耗均衡

DSA技術(shù)是基于密度的聚類，但除了節(jié)點度之外，它還考慮了節(jié)點在其鄰居內(nèi)的相對位置以及改變其通信范圍的效果。由于部署中的隨機性，導(dǎo)致具有不同密度級別的子區(qū)域，可通過定義與這些子區(qū)域相鄰的邊界節(jié)點來完成。DSA技術(shù)主要依賴于聚類之前對網(wǎng)絡(luò)執(zhí)行先前的空間分析，基于BS向網(wǎng)絡(luò)中的每個節(jié)點提供的一些全局信息，并且還期望保留部署的節(jié)點的數(shù)量，因為任何節(jié)點必須具有到BS的連接以被視為網(wǎng)絡(luò)中的工作節(jié)點。通過在聚類過程開始時廣播這兩個值，每個節(jié)點可以啟動DSA，工作機制流程如圖2所示。

圖2 DSA技術(shù)的工作機制流程圖

DSA技術(shù)可以分為子區(qū)域邊界發(fā)現(xiàn)、簇形成以及數(shù)據(jù)傳輸和簇調(diào)整三個主要步驟。

(1) 子區(qū)域邊界發(fā)現(xiàn)。目的是發(fā)現(xiàn)每個節(jié)點周圍的鄰居的分布，并且能夠區(qū)分高密度和低密度子區(qū)域。僅僅測量每個節(jié)點周圍的鄰居數(shù)量是不夠的，因為也需要知道這些鄰居有多遠(yuǎn)。為此，使用邊界發(fā)現(xiàn)機制將節(jié)點分為兩類，即內(nèi)部節(jié)點和邊界節(jié)點。內(nèi)部節(jié)點彼此靠近分布并構(gòu)成高密度區(qū)域。以一組位于邊界處的邊界節(jié)點作為邊界，構(gòu)成低密度區(qū)域，使用分布式算法中的第一跳鄰域信息來區(qū)分內(nèi)部節(jié)點和邊界節(jié)點。如果節(jié)點被包圍在三個相鄰節(jié)點的三角形中，則該節(jié)點將是內(nèi)部的；否則，它將成為邊界節(jié)點。內(nèi)部節(jié)點和邊界節(jié)點之間的差異如圖3所示。

(a) 內(nèi)部節(jié)點P

(b) 邊界節(jié)點P圖3 內(nèi)部節(jié)點與邊界節(jié)點的差異

基于從三角形的每個頂點節(jié)點繪制并且以內(nèi)部節(jié)點為中心的三個角度的總和等于360度的條件，可以測試內(nèi)部條件。不滿足內(nèi)部條件的節(jié)點被分類為邊界節(jié)點。從圖3可以看出，內(nèi)部條件可以寫成：

∠APB+∠APC+∠BPC=360°

(3)

使用可根據(jù)接收信號強度指示器(Received Signal Strength Indicator,RSSI)計算的距離，可以將內(nèi)部條件寫為如下形式：

(4)

當(dāng)每個節(jié)點測試這個條件時，結(jié)果將根據(jù)它可以檢測到的鄰居數(shù)量而不同。當(dāng)節(jié)點使用大的通信范圍值時，其鄰居的數(shù)量將增加，因此其作為內(nèi)部節(jié)點的概率將增加。

(2) 簇形成。在DSA技術(shù)中，信息傳遞依賴于計算每個節(jié)點周圍的內(nèi)部和邊界鄰居的數(shù)量[14]。這有助于將密集的子區(qū)域與稀疏的子區(qū)域區(qū)分開來，并根據(jù)此選擇最佳的CH。節(jié)點周圍更多內(nèi)部鄰居的出現(xiàn)表明它位于密集的子區(qū)域中。相對位于密集子區(qū)域中心的節(jié)點是作為CH的更好候選者，因為它們以較少的通信范圍實現(xiàn)更多連接。另一方面，節(jié)點周圍更多邊界鄰居的出現(xiàn)表明它位于稀疏子區(qū)域中，其特征在于分布在大區(qū)域上的少量節(jié)點。這些區(qū)域選擇的CH必須使用更多的通信范圍來平衡其大小，即能夠與更多成員通信并增加其在網(wǎng)絡(luò)中的連接性[15]。

據(jù)此，可以設(shè)定每個節(jié)點可以確定為CH的條件。第一個條件是CH必須是內(nèi)部節(jié)點，第二個條件取決于節(jié)點的鄰居的分布或節(jié)點的能量。為了能夠檢查節(jié)點的鄰居的分布，引入了一個新參數(shù)，將其命名為內(nèi)部度INdegree，它是內(nèi)部鄰居數(shù)量與節(jié)點所有鄰居的數(shù)量的比率：

(5)

節(jié)點從鄰近的表信息計算其INdegree，并將其能量作為節(jié)點開銷node_cost(S.id,S.INdegree,S.Energy)消息廣播到其鄰居，其中：S.id是路由的id，S.INdegree是路由內(nèi)部度，S.Energy是路由的能量消耗。在從所有鄰居接收到成本后，每個節(jié)點通過向其添加所有鄰居的INdegree和能量來更新其相鄰表。

相鄰表可用于幫助每個節(jié)點確定其在網(wǎng)絡(luò)中的角色。在相同內(nèi)部度的情況下具有最高INdegree或最高能量的內(nèi)部節(jié)點將其狀態(tài)改變?yōu)镃H。通過這種方式，最終選擇的CH在其子區(qū)域中高度集中，這種選擇產(chǎn)生較少且平衡的集群內(nèi)通信成本。根據(jù)周圍鄰居的分布調(diào)整所選擇的CH的通信范圍值，目的是產(chǎn)生相對平衡大小的集群，并在整個網(wǎng)絡(luò)中實現(xiàn)平衡的能量消耗。CH的通信范圍的適應(yīng)根據(jù)式(6)來完成。所有節(jié)點都開始集群形成過程，其通信范圍值等于在DSA技術(shù)的第一步中計算的初始值。根據(jù)該值，確定簇半徑，即可以加入每個簇的成員數(shù)。

(6)

式中：rinitial表示簇半徑的初始值。

在調(diào)整所選擇的CH的通信范圍值之后，這些節(jié)點將其自身宣告為CH并將頭部(S.id，S.status)消息廣播到其范圍內(nèi)的所有節(jié)點，其中，S.status是路由的狀態(tài)。鏈接消息(S.id，S.CH)在CH選擇之后通過向該CH發(fā)送，并將沒有選擇的節(jié)點加入最近的CH的簇，其中，S.CH是路由箭頭，而沒有從任何CH聽到的節(jié)點則宣布自己為CH。

(3) 數(shù)據(jù)傳輸和簇調(diào)整。在創(chuàng)建第一個集群之后，數(shù)據(jù)傳輸開始。CH使用時分多址(TDMA)調(diào)度來為每個成員節(jié)點分配時間。

網(wǎng)絡(luò)中的所有節(jié)點都以初始能量值開始聚類過程。在網(wǎng)絡(luò)的生命周期中，節(jié)點消耗用于感測、處理和通信活動的功率。CH比集群成員消耗更多功率，因為它負(fù)責(zé)聚集和發(fā)送集群中所有成員感知的數(shù)據(jù)到BS，所以長時間保持CH會加速該節(jié)點的死亡。出于這個原因，CH必須改變它們的角色，以便為其他節(jié)點提供成為CH的機會，并在網(wǎng)絡(luò)的其他節(jié)點之間分配通信負(fù)載。在數(shù)據(jù)傳輸之后開始輪集群調(diào)整過程，為了保持構(gòu)造集群的相同結(jié)構(gòu)，選擇新的CH作為具有較高剩余能量的當(dāng)前CH的最近節(jié)點。其中CH主要集中在中間，并且具有比其他成員更高的能量，它是由計算成本值來完成的，而新CH是具有最大成本的節(jié)點。此成本函數(shù)如下：

Cost=βEResdiual-γDCH

(7)

式中：β和γ是本應(yīng)用所描述的因子；EResdiual是剩余能量；DCH是節(jié)點到當(dāng)前CH的距離。

當(dāng)前CH向其鄰居廣播Announce_new_CH(S(i).id，New_CH_id)消息以通告新選擇的CH；其中，S(i).id表示第i個路由id，New_CH_id表示新的路由id。

為每個節(jié)點計算能量消耗活動的方程如下[16]：

① 將L比特的消息發(fā)送到位于距離d的接收器：

ETX=Eelec·L+εfs·L·d2d

(8)

ETX=Eelec·L+εmp·d4d≥D0

(9)

式中：D0表示簇直徑的初始值；Eelec為節(jié)點電路在發(fā)送或接收數(shù)據(jù)時的能量消耗；εfs為放大器在小距離的自由空間模型中的能量消耗；εmp為在遠(yuǎn)距離的多徑衰落模型中的能量消耗。

② 接收L比特消息：

ERX=Eelec·L

(10)

③ 整合L比特消息：

EAgg=EDA·L

(11)

式中：在發(fā)送到BS之前，節(jié)點還需要對數(shù)據(jù)進(jìn)行整合，這部分工作所消耗的能量為EDA。

網(wǎng)絡(luò)中的能量消耗是所有節(jié)點中能量損失的總值，節(jié)點根據(jù)其在網(wǎng)絡(luò)中的規(guī)則丟失不同的能量。

如果節(jié)點是成員(Me)節(jié)點，則感測數(shù)據(jù)傳輸?shù)紺H期間消耗的能量為：

(12)

如果節(jié)點是CH，則在聚合期間消耗的能量以及所收集的數(shù)據(jù)到BS的傳輸為：

(13)

網(wǎng)絡(luò)中的總能量消耗顯示為：

(14)

2 實 驗

2.1 實驗配置

為驗證所提方法有效性，基于MATLAB平臺進(jìn)行了仿真實驗，實驗環(huán)境為Windows 10 Intel?Corei7- 6500 CPU 2.9 GHz，32 GB RAM，達(dá)到預(yù)期實驗驗證效果，設(shè)置了與文獻(xiàn)[6]、文獻(xiàn)[7]和文獻(xiàn)[8]協(xié)議能耗節(jié)省率的對比實驗，其具體參數(shù)設(shè)置如表1所示。

表1 實驗參數(shù)設(shè)置

通過模擬運行50次，求取平均值對算法性能進(jìn)行評估。首先假設(shè)節(jié)點和BS的位置是固定的，BS位于該地區(qū)域區(qū)的中心，實驗參數(shù)如表2所示。為評估網(wǎng)絡(luò)中的能耗，使用與文獻(xiàn)[15]中相同的無線電模型，假設(shè)每個節(jié)點在每一輪中向BS發(fā)送一個分組，CH匯集來自每個集群的所有成員的數(shù)據(jù)并將其發(fā)送到BS。

表2 實驗參數(shù)

2.2 結(jié)果對比

對比實驗設(shè)置為第一級區(qū)域的分簇效率對比，對比結(jié)果如表3所示。

表3 兩種方法的WSN分簇效率

可以看出，相同的目標(biāo)函數(shù)值下，K-均值聚類和所提聚類方法的迭代次數(shù)存在較大差異，其中本文方法大約能減少10代左右的迭代能量消耗，具有更高的最優(yōu)目標(biāo)搜索效率。

進(jìn)行模擬實驗以驗證本文方法的有效性。在將一輪的每個協(xié)議應(yīng)用于相同的部署網(wǎng)絡(luò)之后預(yù)覽生成的集群的分布。在DSA中，屬于任何CH的成員節(jié)點是最接近它的集合，其他技術(shù)無法控制CH和成員之間的距離。因此，一些成員位于遠(yuǎn)距離的集群，易遭受高通信能量消耗的影響。此外，除了DSA之外的所有技術(shù)中的簇的大小之間都存在差異。

在不同密度的網(wǎng)絡(luò)中部署不同數(shù)量的節(jié)點，來評估200 m×200 m網(wǎng)絡(luò)的如下幾個指標(biāo)：

(1) 簇大小的均值和標(biāo)準(zhǔn)差；

(2) 能量消耗均值和能量消耗標(biāo)準(zhǔn)差；

(3) 在不同輪次的總能量消耗；

(4) 不同輪次中死亡節(jié)點的數(shù)量；

(5) 對于不同數(shù)量的節(jié)點，網(wǎng)絡(luò)的總生存周期。

測量第一和第二參數(shù)以證明DSA技術(shù)實現(xiàn)的負(fù)載平衡。在部署120、160、200、220和280個節(jié)點的五個場景中測量平均簇大小和構(gòu)建簇的大小之間的標(biāo)準(zhǔn)差，并測量每個群集內(nèi)的能量消耗值之間的標(biāo)準(zhǔn)偏差，結(jié)果如表4所示。

表4 幾種方法的均值和標(biāo)準(zhǔn)差

在表4中，看起來DSA簇的大小具有小的分散，即簇具有大致相似的大小，而文獻(xiàn)[6-8]算法在其簇的尺寸之間存在高度分散，導(dǎo)致簇之間的能量消耗不平衡。網(wǎng)絡(luò)密度對算法中生成的簇的大小沒有明顯影響，文獻(xiàn)[6-7]算法的情況相同，在不同的密度部署中分別具有大約18和16個平均簇大小。然而，DSA中的平均簇大小隨著網(wǎng)絡(luò)密度的增加而增加。在對比協(xié)議中，預(yù)期節(jié)點之間的距離較遠(yuǎn)，導(dǎo)致低密度網(wǎng)絡(luò)中的簇的大小對高集群內(nèi)通信成本影響較大。因此，這些方法需要高網(wǎng)絡(luò)密度才能實現(xiàn)可接受的性能，然而，無論網(wǎng)絡(luò)密度如何，DSA技術(shù)的效率都是相同的。

圖4和圖5分別顯示了160和280個部署節(jié)點的網(wǎng)絡(luò)總能量消耗。這些值根據(jù)式(14)進(jìn)行計算，進(jìn)行相同輪次通信，與其他技術(shù)相比，DSA技術(shù)實現(xiàn)了更低的能量消耗率。

圖4 不同通信輪次的能量消耗(160個節(jié)點)

圖5 不同通信輪次的能量消耗(280個節(jié)點)

對于兩個網(wǎng)絡(luò)，四種協(xié)議的能耗節(jié)省率如表5所示。可以看出，DSA技術(shù)可以有效節(jié)省能耗，延長網(wǎng)絡(luò)生存周期。

表5 四種協(xié)議能耗節(jié)省率對比 %

圖6為不同節(jié)點數(shù)量下四種算法實現(xiàn)的網(wǎng)絡(luò)生存周期。可以看出，當(dāng)部署160個節(jié)點時，DSA協(xié)議實現(xiàn)的網(wǎng)絡(luò)生存周期分別比文獻(xiàn)[6]、文獻(xiàn)[7]和文獻(xiàn)[8]算法增加約35%、33%和25%；當(dāng)部署320個節(jié)點時，DSA協(xié)議分別比文獻(xiàn)[6]、文獻(xiàn)[7]和文獻(xiàn)[8]算法增加33%、31%和24%。

圖6 不同節(jié)點數(shù)量時的網(wǎng)絡(luò)生存周期

3 結(jié) 語

本文提出一種改進(jìn)粒子群算法結(jié)合DSA技術(shù)的無線傳感器網(wǎng)絡(luò)均衡密度聚類方法，有效地提高了能量消耗率。與其他的聚類技術(shù)相比，實現(xiàn)了更低的功耗，因此網(wǎng)絡(luò)壽命更長，在低密度和高密度網(wǎng)絡(luò)中表現(xiàn)良好。未來的研究方向是使用空間分析的概念來解決無線傳感器網(wǎng)絡(luò)中的其他問題，如空洞探測和目標(biāo)跟蹤。在空間分析之后定義的拓?fù)浣Y(jié)構(gòu)也定義空子區(qū)域，這些次區(qū)域可能遭受覆蓋漏洞。除此之外，將利用節(jié)點之間定義的邊界周期來跟蹤網(wǎng)絡(luò)中的移動目標(biāo)。