基于粒子收斂機制的WSN覆蓋算法

葉小華

(黎明職業(yè)大學 通識教育學院，福建 泉州 362000)

無線傳感網(wǎng)技術(Wireless Sensor Network，WSN)作為供給側改革重點方向之一，正在新一代智慧城市構建領域中發(fā)揮舉足輕重的作用[1].由于無線傳感網(wǎng)采用自組織方式將傳感器部署于物理區(qū)域，可通過無線感知模式實現(xiàn)對物理區(qū)域的監(jiān)控，因而在綠色農(nóng)業(yè)、智慧通信和新冠防疫等領域具有廣泛用途[2].考慮到無線傳感節(jié)點部署密度較高，節(jié)點通信頻率較為頻繁，因此如何采取一定措施提高網(wǎng)絡及節(jié)點覆蓋能力并增強網(wǎng)絡生存質量，成為當前熱門研究領域之一[3].

WSN覆蓋技術主要立足于節(jié)點部署策略、能量利用效率及覆蓋強度等方面，其中覆蓋強度主要反映了網(wǎng)絡對物理區(qū)域的感知能力[4].以綠色農(nóng)業(yè)為例，WSN覆蓋主要存在三個方面.第一，節(jié)點在物理區(qū)域內(nèi)采用隨機游走模型，使得分布具有聚類特性，導致感知能力難以均衡.第二，網(wǎng)絡結構較為復雜，簇頭節(jié)點處于受限狀態(tài)時將導致網(wǎng)絡傳輸出現(xiàn)癱瘓現(xiàn)象.第三，節(jié)點通信較為頻繁，采用無線充電模式將導致嚴重的電磁頻譜污染現(xiàn)象，降低網(wǎng)絡生存質量[5].因此，為降低能量及傳輸受限時可能出現(xiàn)的覆蓋能力下降現(xiàn)象，需要盡量節(jié)約能量的前提下提高節(jié)點覆蓋效率，以便能夠改善網(wǎng)絡生存質量.

當前，研究者提出了一些具有前瞻性的研究方向，在一定程度上提高了節(jié)點覆蓋效率.如Susila[6]等提出了一種基于休眠切換方案的WSN覆蓋算法，算法主要采用預部署模型，在物理區(qū)域內(nèi)均勻部署若干簇頭節(jié)點以增強網(wǎng)絡覆蓋能力，可顯著降低節(jié)點受限時出現(xiàn)的傳輸受阻現(xiàn)象，網(wǎng)絡生存質量較高.不過，該算法也存在預部署節(jié)點數(shù)目過多的特點，使得網(wǎng)絡節(jié)點切換過程易出現(xiàn)失效現(xiàn)象，網(wǎng)絡覆蓋能力也將受到嚴重影響.Kumar[7]等提出了一種基于移動撥備模型的WSN覆蓋算法，該算法與文獻[6]相比，創(chuàng)造性地采用移動模型對節(jié)點進行預部署，可顯著增強節(jié)點覆蓋強度，且具有充能方便的特點.不過，該算法也存在一定的不足，特別是節(jié)點是移動狀態(tài)時存在頻率漂移特性，使得網(wǎng)絡結構易出現(xiàn)抖動現(xiàn)象，降低了該算法的適用性能.Thiruchelvi[8]等提出了一種基于柵欄覆蓋模型的WSN覆蓋算法，該算法采用條狀分割模型將節(jié)點進行層次化處理，優(yōu)選具有較強覆蓋能力的節(jié)點作為層次覆蓋節(jié)點，顯著提升了網(wǎng)絡對物理區(qū)域的感知能力，節(jié)點覆蓋能力較強.不過，該算法需要頻繁針對物理區(qū)域進行層次覆蓋流程，使得算法的便捷性較差，難以適應大規(guī)模部署場景.

為解決當前常見方案存在的不足，提出了一種基于粒子收斂機制的WSN覆蓋算法.算法主要采用定位校正方式對預設錨節(jié)點進行均衡操作，當察覺存在聚集現(xiàn)象時將予以離散處理，從而提高了網(wǎng)絡區(qū)域覆蓋能力.隨后，按照多參數(shù)方式設計了基于慣性權重調節(jié)機制的聚合收斂方法，改善了覆蓋空洞現(xiàn)象，提高了網(wǎng)絡生存質量.仿真實驗證明了所提算法的性能.

1 基于粒子收斂機制的WSN覆蓋算法

由于無線傳感網(wǎng)具有節(jié)點分布較為密集的特點，使得節(jié)點感知易出現(xiàn)失效現(xiàn)象，需要通過密集模式提高節(jié)點覆蓋能力[9].鑒于此，本文算法由兩個部分構成，基于均衡錨預設機制的收斂覆蓋方法和基于慣性權重調節(jié)機制的聚合收斂方法.

1.1 基于均衡錨節(jié)預設機制的收斂覆蓋模型

典型的無線傳感網(wǎng)覆蓋模型見圖1.網(wǎng)絡區(qū)域內(nèi)分布若干錨節(jié)點和子節(jié)點，兩類節(jié)點均可通過無線通信方式實現(xiàn)數(shù)據(jù)交互.當且僅當子節(jié)點處于錨節(jié)點覆蓋范圍內(nèi)時，方可將數(shù)據(jù)傳輸至錨節(jié)點并通過錨節(jié)點實現(xiàn)與sink節(jié)點間的數(shù)據(jù)交互傳輸.此外，無線傳感網(wǎng)在運行過程中遵循如下假設條件.

(i)sink節(jié)點具有超級節(jié)點屬性.sink節(jié)點在網(wǎng)絡覆蓋過程中具有最高優(yōu)先級，可對錨節(jié)點和子節(jié)點實施管理，若發(fā)現(xiàn)錨節(jié)點和子節(jié)點處于失效狀態(tài)時，可予以剔除.

(ii)節(jié)點能量可補充.錨節(jié)點與子節(jié)點處于受限狀態(tài)時，可進入休眠狀態(tài)并由sink節(jié)點予以能量補充，一旦能量得到恢復可繼續(xù)進行數(shù)據(jù)監(jiān)測和網(wǎng)絡覆蓋.

(iii)數(shù)據(jù)傳輸具有一跳特性.錨節(jié)點和子節(jié)點均只能與自身覆蓋范圍內(nèi)節(jié)點進行通信，數(shù)據(jù)傳輸至sink節(jié)點過程中需要采取數(shù)據(jù)中繼的方式，以便與sink節(jié)點實現(xiàn)雙向交互.

圖1 網(wǎng)絡覆蓋圖

將網(wǎng)絡中剩余能量較高的節(jié)點設定為錨節(jié)點(Anchor Nodes，AN節(jié)點)，錨節(jié)點的物理坐標可依據(jù)WSN節(jié)點定位算法獲取[10].不妨設當前AN節(jié)點的坐標為X(x,y)，其偏移量為ΔX(x,y)，成功獲取坐標和偏移量后，按如下模型進行均衡收斂.

ΔX(x,y)[m+1]=X(x,y)[m],ΔX(x,y)[m]

(1)

ΔX(x,y)[m+1]=ΔX(x,y)[m],ΔX(x,y)[m]≥D[m+1]，

(2)

公式(1)和(2)中，m表示坐標定位次數(shù)，X(x,y)[m]表示第m次定位過程中AN節(jié)點的坐標，ΔX(x,y)[m]表示第m次定位過程中AN節(jié)點坐標的偏移量，D[m]表示收斂覆蓋函數(shù)，該收斂覆蓋函數(shù)可通過如下方式獲取.

D[m]=min{D[k],D[k-1]，…}，

(3)

D[1]=ΔX(x,y)，

(4)

公式(3)中D[m]取{D[k],D[k-1]，…，D[1]}中的最小值，公式(3)和公式(4)中參數(shù)同公式(1)和公式(2).

考慮到收斂覆蓋過程中需要引入中斷，這是由于覆蓋過程中可能存在能力受限現(xiàn)象，從而使得錨節(jié)點難以實現(xiàn)區(qū)域覆蓋功能.鑒于此，本文設計了覆蓋收斂聚合度(Convergence Degree of Coverage，CDC)和覆蓋發(fā)散度(Coverage Divergence，CD)指標，對公式(1)和公式(2)所示的均衡收斂模型予以約束，相關指標可由如下公式獲取.

(5)

(6)

當CDC趨向于m時，說明在第m次定位過程中各錨節(jié)點分布較為均衡，無須繼續(xù)進行收斂即可完成物理區(qū)域的覆蓋，當CD趨向于0時，說明第m次定位過程中各錨節(jié)點分布較為稀疏，需要進行收斂以便完成對物理區(qū)域的覆蓋，見圖2.

圖2 基于均衡錨節(jié)預設機制的收斂覆蓋過程

按上圖2所示完成基于均衡錨節(jié)預設機制的收斂覆蓋方法后，錨節(jié)點將被均勻地預設于網(wǎng)絡區(qū)域中，一旦某個區(qū)域出現(xiàn)覆蓋空洞現(xiàn)象，將可以通過裁決CD值的方式繼續(xù)對錨節(jié)點予以均衡化覆蓋，從而提高錨節(jié)點對物理區(qū)域的覆蓋強度.

1.2 基于慣性權重調節(jié)機制的聚合收斂

基于均衡錨節(jié)點預設機制的收斂覆蓋方法執(zhí)行完畢后，預設的錨節(jié)點將能按照較高的乖離程度以實現(xiàn)均衡部署.然而，考慮到節(jié)點具有的漂移特性，需進一步對錨節(jié)點予以聚合收斂處理，以便提高錨節(jié)點的覆蓋能力.

步驟1 針對網(wǎng)絡中的錨節(jié)點，逐個按如下模型獲取慣性權重閾值f(x,y)[m].

(7)

公式(7)中,(x,y)表示錨節(jié)點的當前坐標，(x0,y0)表示錨節(jié)點的初始坐標，g表示錨節(jié)點的通信距離.

步驟2 獲取慣性權重閾值f(x,y)[m]后，構建調節(jié)閾值o[m]如下.

o[m]=f(x,y)[m]-f(x,y)[m-1] ，

(8)

公式(8)與式(7)中參數(shù)相同.

步驟3 當且僅當調節(jié)閾值o[m]高于0時，說明錨節(jié)點在第m次定位過程中可繼續(xù)進行收斂，收斂方法如下.

o[m]>0,L[m]，

(9)

o[m]<0,L[m-1] ，

(10)

其中，L表示位移，L[m]滿足

L[m]=ΔX(x,y).

(11)

步驟4 繼續(xù)針對下一個錨節(jié)點獲取慣性權重系數(shù)并回退至步驟1，流程結束.

圖3 基于慣性權重調節(jié)機制的聚合收斂過程

基于慣性權重調節(jié)機制的聚合收斂方法執(zhí)行完畢后，錨節(jié)點可達到較強的覆蓋效果，且節(jié)點與各傳感節(jié)點間將具有均衡化的分布距離，節(jié)點乖離程度也將處于較高水平，此時網(wǎng)絡覆蓋將達到最優(yōu)狀態(tài).

2 仿真實驗

為對比所提算法性能，采取NS2仿真實驗平臺[11].對照組算法為當前無線傳感網(wǎng)覆蓋領域中常見的基于拓撲優(yōu)化覆蓋策略的WSN覆蓋算法[12](A Novel Topology Optimization of Coverage-Oriented Strategy For Wireless Sensor Networks，NTO算法)和基于能量平衡和參數(shù)受控機制的WSN覆蓋算法[13](Data Association Coverage Algorithm Based on Energy Balance and Controlled Parameters in Wireless Sensor Networks，EBCP算法).仿真指標選取網(wǎng)絡覆蓋率和網(wǎng)絡生存時間兩項.

(i)網(wǎng)絡覆蓋率指節(jié)點開始工作后，隨著工作節(jié)點總數(shù)的變化，能有效覆蓋目標節(jié)點中工作節(jié)點監(jiān)測區(qū)域與網(wǎng)絡覆蓋總區(qū)域面積的比值.若平均覆蓋率越高，說明節(jié)點覆蓋性能也就越好，網(wǎng)絡覆蓋性能也就越高.

(ii)網(wǎng)絡生存時間指網(wǎng)絡開始工作后直到網(wǎng)絡無法工作為止，網(wǎng)絡經(jīng)歷的時間周期.若時間周期越久，說明網(wǎng)絡的生存性能也就越好.

此外，考慮到仿真環(huán)境與實際環(huán)境的貼合性，仿真區(qū)域為矩形，大小為10240 m×10240 m，仿真時間不低于10 min，數(shù)據(jù)速率不低于1 Mbps,錨節(jié)點數(shù)量不低于20個，數(shù)據(jù)傳輸周期不低于24 min，信道環(huán)境采取拉普拉斯信道和高斯信道兩種環(huán)境，其余仿真參數(shù)見表1.

表1 仿真參數(shù)表

2.1 網(wǎng)絡覆蓋率

圖4為所提算法、NTO算法和EBCP算法在網(wǎng)絡覆蓋率方面的對比仿真，由圖4可知所提算法在拉普拉斯信道和高斯信道兩種環(huán)境下均具有較高的網(wǎng)絡覆蓋率，顯示了優(yōu)越的網(wǎng)絡覆蓋性能.這是由于所提算法針對網(wǎng)絡覆蓋空洞問題，設計了基于均衡錨預設機制的收斂覆蓋方法和基于慣性權重調節(jié)機制的聚合收斂方法.可通過錨節(jié)點方式對網(wǎng)絡區(qū)域實現(xiàn)多重覆蓋，并可通過均衡錨預設方式調節(jié)錨節(jié)點的均衡覆蓋水平，因而具有較高的網(wǎng)絡覆蓋率.NTO算法主要采用均等概率機制定期更新網(wǎng)絡區(qū)域簇頭節(jié)點，將無線傳感器網(wǎng)絡的整體能耗均勻分布到傳感器節(jié)點上，實現(xiàn)簇內(nèi)成員節(jié)點數(shù)據(jù)的均衡分布，從而提高節(jié)點的拓撲覆蓋質量.但是，由于該算法未采用輪詢機制對簇頭節(jié)點進行更新操作，簇頭節(jié)點失效率較高，降低了算法的網(wǎng)絡覆蓋能力，因而網(wǎng)絡覆蓋率要低于所提算法.EBCP算法采用了簇內(nèi)低功耗和簇間高功耗的分簇思想，結合信道分配減少節(jié)點覆蓋時延，實現(xiàn)了簇間無沖突覆蓋，從而改善了網(wǎng)絡覆蓋性能.但是，由于該算法存在分簇均衡程度較低的特點，使得簇頭節(jié)點對區(qū)域覆蓋能力較低，因而該算法的網(wǎng)絡覆蓋率亦要低于所提算法.

圖4 網(wǎng)絡覆蓋率

2.2 網(wǎng)絡生存時間

圖5為所提算法、NTO算法和EBCP算法在拉普拉斯信道和高斯信道兩種環(huán)境下的網(wǎng)絡生存時間測試結果.由圖5可知，所提算法具有網(wǎng)絡生成時間較高的特點，顯示了優(yōu)越的網(wǎng)絡生存性能.這是由于所提算法針對網(wǎng)絡節(jié)點能耗所導致的覆蓋問題，設計了基于均衡錨預設機制的收斂覆蓋方法，以提高簇頭節(jié)點的覆蓋性能，特別是所提算法考慮到節(jié)點受限出現(xiàn)的覆蓋空洞現(xiàn)象，設計了基于慣性權重調節(jié)機制的聚合收斂方法，可提高錨節(jié)點對傳感區(qū)域的覆蓋能力，降低了因能量受限而導致的覆蓋空洞現(xiàn)象，因而網(wǎng)絡生存質量較高，具有較長的網(wǎng)絡生存時間.NTO算法采用均衡概率模型以提高簇頭節(jié)點覆蓋能力，但并未采用備份機制及時更新簇頭節(jié)點，因而網(wǎng)絡覆蓋率較低，易出現(xiàn)明顯的網(wǎng)絡受限現(xiàn)象，使得網(wǎng)絡生存時間要低于所提算法.EBCP算法為提高網(wǎng)絡生存質量，結合信道分配減少節(jié)點覆蓋時延，實現(xiàn)了簇間無沖突覆蓋.但是，該算法所選的簇頭均衡化水平較低，使得節(jié)點覆蓋性能較差進而導致節(jié)點分布較為集中，加劇了網(wǎng)絡擁塞現(xiàn)象，因而網(wǎng)絡生存時間要低于所提算法.

圖5 網(wǎng)絡生存時間

3 結束語

為提高無線傳感網(wǎng)的均衡覆蓋能力，提出了一種基于粒子收斂機制的WSN覆蓋算法，算法主要由基于均衡錨預設機制的收斂覆蓋方法和基于慣性權重調節(jié)機制的聚合收斂方法兩部分構成，可顯著提高網(wǎng)絡覆蓋能力，具有錨節(jié)點分布均衡程度較高的特點，網(wǎng)絡覆蓋性能優(yōu)越.