改進PSO結合DSA技術的無線傳感器網絡均衡密度聚類方法

任昌鴻 安 軍

1(重慶師范大學涉外商貿學院信息技術中心 重慶 401520)2(重慶工商大學數學與統計學院 重慶 400030)

0 引 言

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

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

針對以上問題，提出一種改進粒子群算法結合DSA技術的無線傳感器網絡均衡密度聚類方法，實現了對網絡CH節點能耗均衡分簇的有效性。其主要創新點為：

(1) 現有的大多數方法中，沒有考慮節點的分布和生成的集群的大小，而本文方法利用改進粒子群算法優化能量均衡分簇算法以促進網絡能耗均衡分布，避免了網絡熱點問題并最大化傳感器網絡壽命。

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

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

實驗結果表明，本文方法與其他聚類技術相比，實現了更低的功耗，因此網絡壽命更長。

1 方法設計

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

1.1 改進PSO在網絡均衡密度聚類過程中的應用

1) 算法思想。在無線傳感器網絡中，首先需要確定活動區域等級并部署粒子，其中粒子數量與此區域內的傳感器節點數量相等。對粒子飛行規則進行適當修改，當粒子位置與傳感器節點位置相同時，將停止運動并固定位置，其余未到達與傳感器節點相同位置的粒子則將會繼續按照既定規則飛行，直至與對應的傳感器位置節點重合為止；當所有粒子都在位置重合后停止運動時，算法完成分簇并轉移到下一等級區域繼續執行分簇操作[13]。

2) 算法改進。

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

(1)

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

3) 算法基本步驟。

(1) 無線傳感器網絡等級區域可以根據與匯聚節點的距離進行劃分。通過選取不同簇投確定不同等級區域中的簇數以及簇規模。然后選定活動節點，通常選取第一等級區域，假定其余等級區域節點為休眠狀態，從而避免不同等級區域粒子之間的相互干擾。

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

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

(4) 根據類相似度和類間間距對粒子作出適應度評價，并采用鄰近歐幾里得距離所度量的聚類質量作為優化目標函數，具體表示如下：

(2)

式中：dist是測量對象之間的標準歐幾里得距離；x是粒子個體；K是聚類數。

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

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

(8) 重復步驟(3)-步驟(7)直至所有粒子位置與傳感器節點位置重合，完成對應等級區域內的傳感器節點分簇，輸出無線傳感器節點網絡的最優分簇聚類結果。

(9) 喚醒(n-1)R

算法流程如圖1所示。

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

1.2 利用DSA實現能耗均衡

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

圖2 DSA技術的工作機制流程圖

DSA技術可以分為子區域邊界發現、簇形成以及數據傳輸和簇調整三個主要步驟。

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

(a) 內部節點P

(b) 邊界節點P圖3 內部節點與邊界節點的差異

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

∠APB+∠APC+∠BPC=360°

(3)

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

(4)

當每個節點測試這個條件時，結果將根據它可以檢測到的鄰居數量而不同。當節點使用大的通信范圍值時，其鄰居的數量將增加，因此其作為內部節點的概率將增加。

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

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

(5)

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

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

(6)

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

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

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

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

Cost=βEResdiual-γDCH

(7)

式中：β和γ是本應用所描述的因子；EResdiual是剩余能量；DCH是節點到當前CH的距離。

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

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

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

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

(8)

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

(9)

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

② 接收L比特消息：

ERX=Eelec·L

(10)

③ 整合L比特消息：

EAgg=EDA·L

(11)

式中：在發送到BS之前，節點還需要對數據進行整合，這部分工作所消耗的能量為EDA。

網絡中的能量消耗是所有節點中能量損失的總值，節點根據其在網絡中的規則丟失不同的能量。

如果節點是成員(Me)節點，則感測數據傳輸到CH期間消耗的能量為：

(12)

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

(13)

網絡中的總能量消耗顯示為：

(14)

2 實 驗

2.1 實驗配置

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

表1 實驗參數設置

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

表2 實驗參數

2.2 結果對比

對比實驗設置為第一級區域的分簇效率對比，對比結果如表3所示。

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

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

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

在不同密度的網絡中部署不同數量的節點，來評估200 m×200 m網絡的如下幾個指標：

(1) 簇大小的均值和標準差；

(2) 能量消耗均值和能量消耗標準差；

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

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

(5) 對于不同數量的節點，網絡的總生存周期。

測量第一和第二參數以證明DSA技術實現的負載平衡。在部署120、160、200、220和280個節點的五個場景中測量平均簇大小和構建簇的大小之間的標準差，并測量每個群集內的能量消耗值之間的標準偏差，結果如表4所示。

表4 幾種方法的均值和標準差

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

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

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

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

對于兩個網絡，四種協議的能耗節省率如表5所示。可以看出，DSA技術可以有效節省能耗，延長網絡生存周期。

表5 四種協議能耗節省率對比 %

圖6為不同節點數量下四種算法實現的網絡生存周期。可以看出，當部署160個節點時，DSA協議實現的網絡生存周期分別比文獻[6]、文獻[7]和文獻[8]算法增加約35%、33%和25%；當部署320個節點時，DSA協議分別比文獻[6]、文獻[7]和文獻[8]算法增加33%、31%和24%。

圖6 不同節點數量時的網絡生存周期

3 結 語

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