張 華，李躍飛，鄭治武

(湖南信息學院計算機科學與工程學院，湖南 長沙 410004)

無線傳感器與執(zhí)行器網(wǎng)絡(Wireless Sensor and Actuator Network，WSAN)是由大量微型、電池供電的傳感節(jié)點組成[1]。 這些節(jié)點監(jiān)測物理環(huán)境，并將所監(jiān)測的數(shù)據(jù)傳輸至執(zhí)行器(數(shù)據(jù)收集器)。 執(zhí)行器收集這些數(shù)據(jù)后，再將數(shù)據(jù)傳輸至控制中心[2-3]。然而，若執(zhí)行器位置固定，不在執(zhí)行器通信范圍內的節(jié)點需通過多跳傳輸才能將數(shù)據(jù)傳輸至執(zhí)行器，而在其通信范圍內的節(jié)點只需單跳就能將數(shù)據(jù)傳輸至執(zhí)行器，這就使網(wǎng)絡內節(jié)點的能耗不均衡，容易形成能耗空洞[4]。

采用移動式執(zhí)行器(Mobile Actuator，MA)可有效緩解能耗空洞問題。 執(zhí)行器在網(wǎng)絡內移動，縮短了節(jié)點向執(zhí)行器傳輸數(shù)據(jù)的路徑，降低節(jié)點能耗，使網(wǎng)絡內節(jié)點間的能耗更均衡。 此外，采用MA 能緩解因網(wǎng)絡割裂所引發(fā)的數(shù)據(jù)傳輸問題。

執(zhí)行器沿路徑規(guī)劃移動并收集其覆蓋范圍內的節(jié)點數(shù)據(jù)[5]。 因此，如何規(guī)劃執(zhí)行器的移動路徑是WSAN 的研究熱點。 從分簇角度，現(xiàn)存路徑規(guī)劃策略可劃分為基于非分簇的路徑規(guī)劃和基于分簇的路徑規(guī)劃兩類。 在基于非分簇的路徑規(guī)劃策略中，執(zhí)行器需要遍歷所有節(jié)點。 因此，需要設計一條遍歷所有節(jié)點的移動路徑。 顯然，該策略下的移動路徑長度隨網(wǎng)絡規(guī)模增加而迅速增加。 為了解決此問題，基于分簇的路徑規(guī)劃策略被提出。 該策略將網(wǎng)絡內所有節(jié)點劃分成多個簇，執(zhí)行器只需遍歷各個簇的簇頭，減少了執(zhí)行器所停留的位置數(shù)，縮短了移動路徑長度。 例如，文獻[6]就采用了分簇策略，MA 只需遍歷各個簇首，有效地縮短了路徑長度。

據(jù)此，本文也采用基于分簇的路徑規(guī)劃策略。目前存在3 種規(guī)劃路徑方式:隨機移動、固定路線和動態(tài)控制。 在隨機移動方式中，MA 以隨機方式移動，隨意性強，數(shù)據(jù)收集效率低。 在固定路線方式中，MA 依據(jù)預設的固定路線移動。 由于網(wǎng)絡拓撲變化，預定路線并不適用。 因此，當前研究更傾向于采用動態(tài)控制方式規(guī)劃MA 的移動路徑。 在動態(tài)控制方式中，依據(jù)網(wǎng)絡拓撲變化動態(tài)地規(guī)劃MA 的移動路徑。 例如，文獻[7]提出基于模糊邏輯MA 的路徑規(guī)劃算法。 該算法在運動過程中調整MA 所遍歷的位置點，具有較好的適應性。

然而，現(xiàn)存多數(shù)研究工作只采用單個MA。 若采用單個MA，MA 需遍歷到網(wǎng)絡內所有駐留點(Rendezvous Point，RP)，才能收集所有節(jié)點數(shù)據(jù)，這增加了MA 收集數(shù)據(jù)的時延。 因此，文獻[8-9]提出多個MA 的策略。 通過多個MA 共同收集網(wǎng)絡內節(jié)點數(shù)據(jù)，降低時延。 然而，若多個MAs 共同工作時，需考慮它們協(xié)同工作效率。 即如何有效地規(guī)劃它們的路徑，最大程度地降低時延和能耗是一項挑戰(zhàn)工作。

同時，由于部署MA 的成本遠高于部署節(jié)點的成本，在實際應用環(huán)境中，應盡可能地減少MA 數(shù)量。 即以最少的MAs 完成數(shù)據(jù)收集任務。

為此，提出基于雙重聚類的執(zhí)行器路徑規(guī)劃算法(Dual Clustering-based Path Planning of Actuator，DCPA)。 主要工作如下:①DCPA 算法采用模糊化C-均值聚類算法計算簇中心，并以此簇中心作為RP 位置點；②利用密度峰值聚類算法將這些RPs點劃分成若干個聚群，每個聚群由一個MA 負責收集該聚群內的節(jié)點數(shù)據(jù)；使多個MAs 能協(xié)同地工作，避免它們重復地收集RPs 的數(shù)據(jù)，提升MA 的工作效率。 而現(xiàn)有算法只是利用聚類算法對節(jié)點進行分簇，并沒有將多個MAs 進行聚類。 ③利用改進的蝙蝠算法規(guī)劃MA 的路徑，使其能在最短時間收集節(jié)點數(shù)據(jù)。 考慮到傳統(tǒng)蝙蝠算法易陷入局部最優(yōu)的困境，對其進行改進。 采用慣性權重對蝙蝠的速度更新進行約束；④通過仿真分析驗證DCPA 算法性能，并著重分析DCPA 算法隨網(wǎng)絡拓撲變化性能，即分析網(wǎng)絡失效節(jié)點數(shù)對DCPA 算法的影響。

1 系統(tǒng)模型

1.1 網(wǎng)絡模型

假定WSAN 有N個節(jié)點和M個MAs。N個節(jié)點構成節(jié)點集S＝{si｜1≤i≤N}，其中si表示第i個節(jié)點。 每個MA 依據(jù)預定路線移動，收集其覆蓋范圍內的節(jié)點數(shù)據(jù)。

在網(wǎng)絡內產(chǎn)生K個RPs，K個RPs 構成RPs 集Q＝{qk｜1≤k≤K}，其中qk表示第k個RP。 再將這些RPs 劃分成M個聚群。 每個MA 負責一個聚群，由MA 依據(jù)預定路徑遍歷該聚群內的RPs，進而收集節(jié)點數(shù)據(jù)。 假定MA 具有充足能量完成收集數(shù)據(jù)任務[10]。 由MA 執(zhí)行路徑規(guī)劃算法，降低網(wǎng)絡內節(jié)點的能耗。

圖1 給出M＝2 的網(wǎng)絡模型示例。 利用模糊C-均值聚類算法(FuzzyC-Means，F(xiàn)CM)[11]產(chǎn)生7 個RPs，再將這些RPs 劃分成兩個聚群。 在每個聚群內，利用變鄰域蝙蝠算法規(guī)劃MA 遍歷這些RPs 的路徑。

圖1 網(wǎng)絡模型

1.2 能耗模型

考慮到節(jié)點所攜帶的能量較少，且傳輸、接收數(shù)據(jù)所消耗能量占據(jù)節(jié)點的大部分能量。 因此，本文只考慮節(jié)點傳輸、接收數(shù)據(jù)階段所消耗的能量[12]。采用圖2 所示的能耗模型。 采用多徑衰落模型。 節(jié)點傳輸m比特數(shù)據(jù)所消耗能量為:

圖2 能耗模型

式中:Ee表示無線通信模塊發(fā)送或接收單位比特數(shù)據(jù)的電路能耗[13]；Ea表示多徑衰落模型的功放參數(shù)；d表示收/發(fā)兩端間的歐氏距離。

接收m比特的數(shù)據(jù)包所消耗的能量Esd(m)為:

2 DCPA 算法

DCPA 算法由三個階段構成:①優(yōu)化RP 位置階段。 在此階段利用FCM 計算RP 數(shù)量以及各RP 的位置；②RPs 的簇化階段。 在此階段，采用密度峰值聚類算法將RPs 劃分成簇。 每個簇內有一個MA，并由此MA 負責遍歷該簇內的每個RP 點，進而收集節(jié)點數(shù)據(jù)；③MA 的路徑規(guī)劃。 在此階段，利用改進的蝙蝠算法規(guī)劃MA 的移動路徑。

2.1 基于FCM 的RP 位置的優(yōu)化

DCPA 算法將優(yōu)化RP 位置問題看成覆蓋問題，旨在使每個RP 能夠覆蓋更多的節(jié)點。 當MA 到達RP 位置時，RP 的覆蓋半徑就是MA 的通信半徑，進而使RP 覆蓋半徑內的節(jié)點只需通過單跳就能將數(shù)據(jù)傳輸至MA。 然而，由于MA 需停留在RP 位置上，才能收集節(jié)點數(shù)據(jù)。 因此，RPs 數(shù)越多，MA 收集數(shù)據(jù)的時延就越長。

因此，需要以盡可能少的RPs 數(shù)完成對所有節(jié)點的覆蓋。 換而言之，應最大化RP 的利用率，使每個RP 盡可能地覆蓋更多節(jié)點，并使鄰近RP 間的覆蓋重疊區(qū)最小。 為此，DCPA 算法利用FCM 優(yōu)化RP 位置。 具體步驟如下:

第一步:依據(jù)監(jiān)測區(qū)域面積和節(jié)點通信半徑估計RPs 數(shù):

式中:NRP表示監(jiān)測區(qū)內所需的RPs 數(shù)；Aa表示監(jiān)測區(qū)域面積；Rc表示節(jié)點的通信半徑；表示取整操作；λ為調控參數(shù)，可依據(jù)網(wǎng)絡拓撲環(huán)境調整λ值。

第二步:計算節(jié)點離聚類中心位置的關聯(lián)系數(shù)。令μik表示節(jié)點si離qk的關聯(lián)系數(shù):

式中:ν表示模糊值，且1≤ν＜∞，其反映了聚類被模糊的程度；‖xi-pk‖表示節(jié)點si離qk的歐氏距離，其中xi表示節(jié)點si的位置矢量；pk表示qk的位置矢量。

第三步:計算聚類中心位置pk:

式中:ν為模糊值。

最后，設置迭代終止條件。 用N×K維矩陣U表述所有節(jié)點離K個RP 的位置的關聯(lián)系數(shù)矩陣。μik屬矩陣U中第i行第k列元素。 當?shù)?+1 次迭代后矩陣U與第?次迭代后矩陣U值的差值小于預定值，則停止迭代。 即當‖U(?+1)-U(?)‖＜ξ，就停止迭代，其中ξ表示預定值；U(?)表示第?次迭代后矩陣U值。

圖3 給出了計算RP 位置的主要流程。 先初始化網(wǎng)絡參數(shù)，包括監(jiān)測區(qū)域面積、節(jié)點通信半徑和模糊值。 然后再計算聚類數(shù)以及矩陣U。 通過迭代，最終得到聚類中心位置。 將聚類中心位置作為RP位置。

圖3 基于FCM 的RP 位置優(yōu)化流程

2.2 基于密度峰值聚類的RPs 的簇化

采用密度峰值聚類[14-15]對RPs 進行聚類分簇。具體步驟如下:

第一步:計算密度距離。 依式(6)計算RPqk點(數(shù)據(jù)點)的局部密度ρk:

式中:dkh表示qk離qh的歐氏距離；D表示截斷距離，用RP 的通信距離Rc表示截斷距離，即D＝Rc。

第二步:計算qk到其更高密度數(shù)據(jù)點的距離δk:

第三步:依據(jù)式(8)計算決策度量γk，再依降序對決策度量進行排序。 然后，選取前M個RPs 作為聚類中心。

最后，將剩余的RPs 點(非聚類中心點)與距離該RP 點最近且擁有更高局部密度值的RP 點歸為一類。

2.3 基于改進蝙蝠算法的MA 路徑規(guī)劃

本節(jié)討論MA 移動路徑的規(guī)劃問題。 該問題屬旅行商問題(Travelling Salesman Problem，TSP)[16]。TSP 問題可簡述為:在給定的n點，旅行商從某點出發(fā)，每個點只到達一次，最終又回到出發(fā)點。 計算使該回路最短的路徑問題[17]。

作為群體智能優(yōu)化算法，蝙蝠算法就是通過模仿蝙蝠尋覓食物路線的路徑規(guī)劃算法。 考慮傳統(tǒng)的蝙蝠算法易陷入局部最優(yōu)的困境，對蝙蝠算法進行改進，再利用改進后的蝙蝠算法規(guī)劃MA 的路徑。

蝙蝠算法利用式(9)、式(10)和式(11)更新位置和速度:

式中:fi，fmin，fmax分別表示第i個蝙蝠個體聲波脈沖頻率，聲波頻率最小值，聲波頻率最大值。χ表示在0 至1 間的隨機變量；，分別表示第i個蝙蝠個體的飛行速度，位置，上標“t”表示迭代次數(shù)；x*表示全局最優(yōu)的蝙蝠個體位置。

若在飛行過程中發(fā)現(xiàn)了獵物，蝙蝠就增加聲波脈沖頻率，并更新位置:

式中:表示第i個蝙蝠個體在t+1 次迭代中的響度；表示第i個蝙蝠個體在t+1 次迭代中的脈沖發(fā)射率；表示初始的脈沖發(fā)射率；α、β均為調控參數(shù)。

考慮到傳統(tǒng)蝙蝠算法[18]易陷入局部最優(yōu)的困境，對其進行改進。 采用慣性權重對蝙蝠的速度更新進行約束。 因此，將式(10)重述為:

式中:ω為慣性權重系數(shù)，其定義如式(15)所示。

式中:ωmax，ωmin分別表示慣性權重的最大值、最小值；t表示當前的迭代次數(shù)；T表示允許的最大迭代次數(shù)。 從式(15)的定義可知，在初期迭代時(t值較小)，ω值較小，提升了算法在全局搜索能力。 隨著迭代次數(shù)增加，ω值也隨之增大，增強了與上一代群體的關聯(lián)性，提升了局部搜索能力。

圖4 給出基于改進后的蝙蝠算法規(guī)劃MA 路徑的流程。 先初始化個體參數(shù)(T，，xi，，?i)，然后計算個體適應值，找到最優(yōu)路徑x*。 第二步，分別利用式(9)、式(15)和式(11)更新，并計算當前個體的適應度值。 將當前的適應度值與上次迭代的適應度值進行比較，保留更優(yōu)的個體。

圖4 基于改進蝙蝠算法的MA 路徑規(guī)劃流程

第三步，生成一個隨機數(shù)Rand1。 若Rand1 大于，就進行變鄰域策略，否則保留當前最優(yōu)蝙蝠個體。

第四步，再生成一個隨機數(shù)Rand2。 若Rand2大于，并且，就利用式(12)和式(13)分別更新響度和脈沖發(fā)射率。

最后，更新全局最優(yōu)路徑，并判斷是否到達最大迭代次數(shù)。 否則，繼續(xù)迭代，最終輸出最優(yōu)路徑。

3 性能分析

3.1 仿真環(huán)境

利用MATLAB 2016a 建立仿真平臺。 90 個節(jié)點(N＝90)隨機分布于監(jiān)測區(qū)域300 m×300 m 內，節(jié)點的通信半徑為25 m。 MA 在每個RP 點停留5 s，收集該RP 覆蓋范圍內的節(jié)點數(shù)據(jù)。 具體的仿真參數(shù)如表1 所示。

表1 仿真參數(shù)

選擇文獻[19]提出的基于最小權重頂點覆蓋問題的RP 選擇算法(Minimum Weighted Vertex Cover-based RP Selection，MWVS)和文獻[20]提出的基于成本均衡的RP 選擇算法(Cost Balancingbased RP Selection，CBRP)作為參照，同DCPA 算法對比分析它們的性能。 MWVS 采用穩(wěn)定選舉策略，通過節(jié)點能量和距離信息選舉簇頭，使簇結構更為穩(wěn)定，再將簇頭作為MA 的遍歷點。 CBRP 算法采用多個MAs 收集網(wǎng)絡內節(jié)點數(shù)據(jù)。 CBRP 算法先將監(jiān)測區(qū)域劃分為多個子區(qū)域，然后依據(jù)成本分配MAs 收集子區(qū)域內的節(jié)點數(shù)據(jù)。 為了驗證改進后的蝙蝠算法效果，選擇基于未改進后的蝙蝠算法規(guī)劃每個執(zhí)行器遍歷RPs 的路徑，將其標記為DCPAUnI。 DCPA-UnI 算法與DCPA 算法的不同之處在于:DCPA 算法采用改進后蝙蝠算法規(guī)劃MA 遍歷RPs 路徑，而DCPA-UnI 算法采用傳統(tǒng)蝙蝠算法規(guī)劃MA 遍歷RPs 路徑。

此外，本文著重分析DCPA 算法對網(wǎng)絡失效節(jié)點(Failed NodE，F(xiàn)NE)的魯棒性。 節(jié)點部署后，因能量或者硬件、軟件故障，節(jié)點無法收集、傳輸數(shù)據(jù)，將這類節(jié)點稱為失效節(jié)點。 為此，本文以FNE 數(shù)為自變量，分析FNE 數(shù)對算法的性能影響。

3.2 節(jié)點的覆蓋率

首先分析FNE 數(shù)對節(jié)點覆蓋率的影響。 節(jié)點覆蓋率是指節(jié)點被RP 覆蓋的比例。 覆蓋點越高，越多節(jié)點能以單跳方式與RP 通信，性能越好。

圖5 給出平均的節(jié)點覆蓋率隨FNE 數(shù)的變化情況。 從圖可知，在FNE 數(shù)從0 至50 變化期間，DCPA 算法的覆蓋率不低于90%。 即使在FNE ＝50，DCPA 算法的覆蓋率仍達到約94%。 相比之下，MWVS 算法和CBRP 算法的覆蓋率隨FNE 數(shù)增加而快速下降，它們的覆蓋率低于DCPA 算法的覆蓋率。 在FNE 數(shù)較少時，MWVS 算法的節(jié)點覆蓋率可保持在90%以上，但當FNE 數(shù)增加至25 后，其節(jié)點覆蓋率迅速下降。 而CBRP 算法的覆蓋率性能比MWVS 算法更uda 。 此外，相比于DCPA-UnI 算法，DCPA 算法提高了節(jié)點覆蓋率，這說明通過對蝙蝠算法的速度更新進行約束，能夠獲取更優(yōu)的解，使MAs 能夠覆蓋更多節(jié)點。

圖5 節(jié)點覆蓋率隨FNE 數(shù)的變化情況

3.3 MA 遍歷的平均距離

接下來，分析FNE 數(shù)對MA 遍歷的平均距離的影響，如圖6 所示。 從圖可知，相比于MWVS 和CBRP 算法，DCPA 算法中MA 遍歷的平均距離最長。 原因在于:DCPA 算法保持90%以上的覆蓋率，MA 需移動較長距離，進而維持對節(jié)點的覆蓋。 此外，DCPA 算法中MA 遍歷的平均距離略大于DCPA-UnI 算法。 在FNE 數(shù)較少時，MA 遍歷的平均距離相近。 隨著FNE 數(shù)增加，DCPA 算法中MA遍歷的平均距離逐步大于DCPA-UnI 算法。 原因在于:DCPA 算法為了確保能覆蓋更多節(jié)點，需產(chǎn)生更多RPs，這就增加了MA 移動的距離。

圖6 MA 遍歷的平均距離隨FNE 數(shù)的變化情況

CBRP 算法將監(jiān)測區(qū)域劃分為網(wǎng)格，每個網(wǎng)格內產(chǎn)生一個RP。 因此，CBRP 算法中RP 移動的距離更短，但其是以低的覆蓋率為代價。 MWVS 算法中MA 遍歷的平均距離介于DCPA 算法與CBRP 算法中間。 MWVS 算法是以減少RPs 數(shù)為代價換取短的距離。

此外，DCPA 算法、MWVS 算法和CBRP 算法中MA 遍歷的平均距離隨FNE 數(shù)的變化情況并不相同。 在FNE 數(shù)變化期間，DCPA 算法中MA 遍歷的平均距離基本穩(wěn)定，而CBRP 算法和MWVS 算法中MA 遍歷的平均距離快速下降。 這說明它們對網(wǎng)絡拓撲變化的魯棒性低，自適應性差。

3.4 MA 遍歷的平均時間

圖7 顯示了DCPA、MWVS 和CBRP 算法中MA遍歷的平均時間。

圖7 MA 遍歷的平均時間隨FNE 數(shù)的變化情況

從圖7 可知，由于MA 移動速度固定，MA 遍歷的平均時間與遍歷的平均距離呈線性關系。 相比于MWVS 算法和CBRP 算法，DCPA 算法中MA 遍歷的平均時間最高，且在FNE 數(shù)變化期間保持穩(wěn)定。而MWVS 算法和CBRP 算法的MA 遍歷的平均時間短，且隨FNE 數(shù)增加快速下降。 原因在于:它們遍歷的平均距離短。

3.5 節(jié)點的平均剩余能量百分比

選用節(jié)點的平均剩余能量百分比評估網(wǎng)絡能耗性能，其定義如式(16)所示:

式中:表示節(jié)點si的剩余能量；Einit表示節(jié)點的初始能量。

圖8 顯示了DCPA、DCPA-UnI、MWVS 和CBRP算法的平均剩余能量百比分隨FNE 數(shù)的變化情況。從圖可知，F(xiàn)NE 數(shù)越大，節(jié)點的平均剩余能量百分比越低。 原因在于:FNE 數(shù)越大，網(wǎng)絡連通性越差，多數(shù)節(jié)點需要多跳才能將數(shù)據(jù)傳輸至MA，這就增加了節(jié)點能耗。

圖8 平均剩余能量百分比隨FNE 數(shù)的變化情況

相比DCPA-UnI、MWVS 和CBRP 算法，DCPA算法提高了平均剩余能量百分比。 原因在于:DCPA 算法通過增加MA 遍歷的距離，保證多數(shù)節(jié)點在RP 的覆蓋范圍內，使節(jié)點只需單跳就能與RP通信，最終降低了節(jié)點的能量消耗。 DCPA 算法通過增加MA 移動距離，覆蓋更多節(jié)點，使節(jié)點只需通過單跳就能將數(shù)據(jù)傳輸至RPs，進而節(jié)省能耗。 當然，這是不計MA 能量消耗。 換而言之，DCPA 算法是以犧牲MA 能量為代價，節(jié)省節(jié)點的能量。 這是可取的。 相比于節(jié)點，MA 可攜帶更多能量，并且具有可充電特性。

3.6 網(wǎng)絡吞吐量

最后，分析網(wǎng)絡吞吐量。 以MA 收集的數(shù)據(jù)量平均值作為吞吐量。 MA 收集的數(shù)據(jù)越多，表明MA覆蓋的節(jié)點越多，收集的數(shù)據(jù)越多，性能越好。

圖9 給出吞吐量隨FNE 數(shù)變化曲線，從圖可知，相比于MWVS 和CBRP 算法，DCPA 算法的吞吐量最大，這說明DCPA 算法能夠使RP 覆蓋更多節(jié)點，進而使MA 收集了更多數(shù)據(jù)，提升了吞吐量。 此外，DCPA 算法的吞吐量隨FNE 數(shù)增加而下降速度較緩慢，這說明DCPA 算法能夠應對網(wǎng)絡拓撲變化，而MWVS 和CBRP 算法的吞吐量下降速度更快。由于DCPA 算法降低了節(jié)點的能耗速度，它的吞吐量優(yōu)于DCPA-UnI 算法的吞吐量。

圖9 吞吐量隨FNE 數(shù)的變化情況

4 總結

本文以節(jié)點覆蓋為視角，討論WSAN 中MA 路徑的規(guī)劃問題。 先利用FCM 算法優(yōu)化網(wǎng)絡簇中心節(jié)點，再視每個簇中心為RP 點，進而使每個RP 覆蓋更多節(jié)點。 然后，利用密度峰值聚類算法將所選擇RPs 劃分成簇，并使簇數(shù)等于MA 數(shù)，進而使每個簇內由一個MA 完成該簇的數(shù)據(jù)收集任務。 最后，將MA 遍歷RPs 的順序視為TSP 問題，并利用改進的蝙蝠算法規(guī)劃MA 路徑。 性能分析表明，提出的DCPA 算法有效地提高覆蓋率，降低了能耗。

盡管DCPA 算法在節(jié)點覆蓋率、網(wǎng)絡能耗方面具有較好性能，但其在MA 移動距離以及時延方面并不具有優(yōu)勢。 未來將繼續(xù)研究DCPA 算法，通過優(yōu)化參數(shù)，縮短MA 的移動距離，進而降低時延，這是后期的研究工作。