基于改進PSO的傳感器覆蓋控制策略研究

（西安工業大學 電子信息工程學院，西安710021）

隨著對傳感器在不同領域的不斷研究探討，它在軍事與無線通信領域的作用日益突出[1]。在對該區域內的布置與調度策略直接影響整個區域的覆蓋效果即覆蓋率，該作戰效果是為作戰指揮控制后續的其他戰場特性任務做準備的戰事前提，如目標的定位、跟蹤、數據的采集、處理等。

對于覆蓋控制任務的展開，其關鍵是研究如何合理有效地調度規劃出區域內傳感器節點的位置關系，保證整個空間內的覆蓋質量最優。采用人工部署節點[2]的方式不夠科學也容易造成傳感器初始位置分布不均的問題，導致整個作戰區域無法達到有效覆蓋。因此，研究調度覆蓋問題對于軍事調度控制有著極高的科研實際價值。

鑒于此，本文將多傳感器節點的部署問題轉化為粒子群覆蓋優化問題，針對原算法所存在的不足之處，以虛擬力算法為融合改進方向，對該空間內的粒子施加電場勢能作用力[3]。最終通過對比試驗，證明該改進算法使傳感器節點在區域覆蓋問題中展現出更好的分布效果，并有效提高了區域覆蓋率，減少了無效的冗余覆蓋。

1 多傳感器調度覆蓋問題描述

針對區域覆蓋問題，評價該體系的優劣主要通過對監測域的有效覆蓋、節點能量消耗，以及對網絡通信資源的優化配置3個方面進行研究探索。而對于初始化多傳感器調度覆蓋中調度變量節點的選取問題，分析規劃出的控制屬性如圖1所示，以便后續覆蓋部署的展開。

圖1 傳感器調度覆蓋屬性分類Fig.1 Sensor scheduling coverage attribute classification

根據圖1所示歸類，在此重點研究有效覆蓋問題。該問題通過對節點之間的合理調度來減少冗余覆蓋面積的產生，優化整體監測區域內的有效覆蓋。如果防御區域內的傳感器節點均處于工作狀態，雖然能夠達到全覆蓋的指標，但會造成大量的冗余資源，加大了傳感器節點能量的損耗。因此，有效覆蓋不僅可以提高對目標區域覆蓋探測質量，還可以最大限度延長傳感器工作的生存周期。

在該問題的各研究方向中僅選擇區域覆蓋這一屬性，即在給定的整個高價值區域內，進行對區域內每一個傳感器調度布控以達到整體有效覆蓋[4]，如圖2所示。

針對覆蓋部署的性質，采取可調性部署覆蓋方式。其一主要針對傳感器的感知半徑可以根據不同的環境或任務來進行適當的調節，起到節約能量的作用。其次可調性還包括調度移動，移動是指具有移動能力的傳感器節點在區域內的相對位置發生改變，以滿足均勻分布覆蓋的感知部署策略安排[5]，而且較好的算法可以減少移動距離，使能量消耗處理更為均衡合理。

圖2 區域覆蓋示意圖Fig.2 Area coverage diagrammatic sketch

在此，從上述分析得出的屬性要求出發，研究該配置選定下傳感器在給定區域內如何進行有效的覆蓋調度控制，以達到更高效的覆蓋率。

2 粒子群優化下的覆蓋控制

通過對覆蓋優化問題的研究，可以提高網絡覆蓋率，減少分布冗余性，降低網絡能耗。現今為止，覆蓋優化算法有蟻群算法、遺傳算法、魚群算法、螢火蟲算法等[6]。然而，這些算法在網絡覆蓋優化方面存在缺陷，比如：螢火蟲算法的尋優值較差導致網絡覆蓋率較低；蟻群算法涉及的參數過多，形成不易求解的復雜網絡模型，進而造成實際部署困難等。故在此首先采用粒子群PSO（particle swarm optimization）算法來優化網絡覆蓋率，解決網絡覆蓋不均勻和冗余問題，進而能夠有效地解決傳感器節點調度覆蓋優化問題。

假定，該算法所在空間為D 維，那么Xi為第i個粒子的位置，Vi為速度，Pi為粒子搜索到最佳位值，Pg為粒子群搜索到最佳位置，i為粒子個數。速度和位置的更新方程為

式中：c1，c2為加速因子；r1，r2為隨機數；w為慣性權重系數；xid為第i個粒子在D 維的搜索空間中的所處虛擬位置。

在對該算法的設計中，將其進行搜捕的每一個粒子研改為傳感器覆蓋的一次布控模式，每種布控方式就是一種傳感器的覆蓋布局[7]。并將該覆蓋優化模型的目標函數作為適應度函數，通過不斷尋優比較，使該適應度函數達到最大值，即輸出優化后的覆蓋率。

針對上述目標函數的設定，定義區域覆蓋率是把待監測區域劃分為M×N 網格，所有網格范圍是該作戰區域。每個網格的中心，如果被傳感器節點感知覆蓋到，則視為此網格被有效監測覆蓋[8]。為避免各網格中依然有很多區域未被監測，應盡可能將監測區域劃分成更多的網格。通過公式計算每個網格中心被所有傳感器終端節點感知覆蓋的概率p，統計被覆蓋到的網格總數，然后通過計算被監測的網格總數占所有網格的比例即可得到覆蓋率，傳感器節點集合s 對區域的覆蓋率C為

覆蓋率的定義：全部傳感器節點所能感知覆蓋的面積與整個被監測地區的面積大小之比。

但由于粒子群算法容易陷入局部最優的困境，而且對后期離散的優化問題處理不佳。故在此提出了改進粒子群混合虛擬力算法，以更好地解決該覆蓋控制優化問題。

3 融合虛擬力的改進粒子群增強覆蓋算法

粒子群算法具有原理簡單、設置參數少、收斂速度快的優點，但是在求解高維復雜問題時較容易陷入局部最優解，故在此首先對其自身的性能進行改進，再融入虛擬力算法提高算法的魯棒性及能效性，使得整體搜尋能更快更準地找到全局最優解，可以說最好的覆蓋率即最優的覆蓋調度部署方案。

3.1 PSO的改進

在此對于粒子群算法的慣性權重進行優化。慣性權重決定了粒子對其自身飛行速度的保存尋優程度，通過調整慣性權重設定來均衡全局搜索和局部搜索能力。將迭代的初始階段設置一個比較大的慣性權重，使其保持高效的全局性，增強信息共享，定位接近全局最優解所在區域，在迭代的后期，縮小其權重大小，使算法在全局最優范疇下增加的局部搜索能力，從而尋找到全局最優解。采用式（4）進行動態調節，將初始慣性權重設置為2，能夠取得比較好的算法效果。

式中：K為該粒子群算法最大迭代次數；k為當前迭代次數；ωmax為最大（初始）慣性權重；ωmin為最小（終止）慣性權重。因此，慣性權重在此范圍內進行有序的線性變化，總體成平穩變化趨勢，穩定了搜索過程中的波動。

3.2 融合虛擬力算法策略研究

在移動傳感器節點再部署算法中，虛擬力算法VFA（virtual force algorithm）正是起源于人工勢場中的虛擬勢場，可以將虛擬力中引力、斥力作用引用到自主可移動傳感器節點調度部署策略中[9]。其本質的優秀性能夠符合項目對調度覆蓋所需的控制要求，因此融合虛擬力算法是優化覆蓋問題的核心步驟。

虛擬力算法的核心架構是針對可調度性傳感器節點的屬性特征，將其變量代入算法中，看成勢力場中的帶電微粒并相互受到虛擬的作用力，這種虛擬作用力可以劃分為不同的表現形式引力、斥力。決定該力的屬性變化的原則是各節點之間存在的一個合理的距離閾值D 及區間判斷。節點之間距離大于D時，節點間將發生引力作用，反之節點間發生斥力作用。調度空間中的節點所受到的虛擬力是所在控制范圍內傳感器對彼此產生的合力，并且在該力的大小和方向引導下進行調度移動，最終通過虛擬作用力的引導，完成調節區域內節點間的分布，實現區域的均勻有效覆蓋[10]。

假設，所調度傳感器集合為S=｛s1，s2，…，sN｝，其中需要完成移動覆蓋調度任務的2個傳感器為si和sj，且sj屬于對si作用節點集合。則它們之間的距離為

則該施力方sj對受力方si的作用力為

式中：dij為傳感器節點si與sj之間的歐式距離；ωFa，ωFr分別為虛擬力引力、斥力參數；Dth為設定的距離閾值；αij為兩節點之間的方向夾角；R為傳感器的感知半徑。

最終對節點所受虛擬力Fij利用力的平行四邊形原理可分解到x 和y 兩個方向，設合力的標量大小為Fxy，且符合力的分析原理，向量關系和矢量關系為

其中以虛擬力中的引力為移動調度覆蓋的為例，傳感器之間如果存在較大的間隔勢必造成覆蓋空洞，覆蓋率低下的問題。而虛擬力中的引力，可以根據設定的距離閾值來操作可移動傳感器節點進行覆蓋修復工作，以達到均勻覆蓋分布。虛擬力引力作用如圖3所示。

圖3 虛擬力引力作用示意圖Fig.3 Diagrammatic sketch of virtual force gravitational action

最終，在分析區域內各傳感器節點的受力情況后，通過對作用力大小、方向的判定，完成相應節點的移動部署任務。其移動距離為

式中：xi，ini，yi，ini為傳感器移動之前（初始）的位置信息；xi，pres，yi，pres為傳感器調度移動以后的位置信息；Fx，Fy分別為傳感器所受力在x，y 方向上的投影；Fxy為作用在傳感器上的合力；dm，max為節點的單位最大虛擬移動步長；e1/Fxy為傳感器移動步長推進系數。

改進虛擬力混合粒子群算法IVFPSO（improve virtual force particle swarm optimization） 的本質是將傳感器在模擬場內所受到的引力、斥力的布控方式策略引入到粒子群算法中，使其帶給粒子更為有效合理的尋優及位置更新的方式。根據每次迭代過程中虛擬力作用下的搜索牽引，利用

進行計算，選擇出當前所有粒子的個體歷史最優解和整個種群的全局最優解，并在加速迭代下得出最優覆蓋率下的傳感器節點調度部署覆蓋結果。

具體的操作是：在初始化粒子位置后，為防止粒子過于聚集，通過密集度來增加距離閾值，讓更大范圍內的粒子進行尋優操作；通過平衡斥力系數在迭代開始的前期作用，使得排斥力在閾值作用下對距離越近的粒子更容易發生排斥，分散到未被覆蓋的區域，加強搜尋能力更容易跳出局部最優解；在后期當粒子將要處于均衡狀態時，粒子間可能存在少量的小空洞間隙，此時平衡引力系數會使傳感器節點之間相互吸引，修復這些空洞，達到最優覆蓋效率下的均勻覆蓋效果。

4 試驗仿真結果

4.1 試驗環境

操作系統為Windows 10，64 位處理器；CPU 環境為Intel（R）Core（TM）i7-8550 CPU@1.80 GHz；算法實現編程語言為MatLab 2016b。

粒子群參數初始化、虛擬力參數初始化如下：設置ωFa=2，ωFr=3，Dth=2；dm，max=2 m，粒子群種群大小為50，其他仿真參數見表1。

表1 混合算法仿真試驗參數Tab.1 Simulation experiment parameters of hybrid algorithm

4.2 仿真結果

調度空間中傳感器節點的初始隨機分布情況如圖4所示。將所提出的IVFPSO 與傳統PSO 和高效率虛擬力算法CEVFA（creativity efficiency virtual force algorithm） 算法進行對比，其仿真結果如圖5所示。圖中顯示了3種不同算法對30個半徑為10 m多傳感器的調度覆蓋部署情況。

由圖4可見，初始狀態的節點分布十分不均勻，未覆蓋區域嚴重影響了整體空間分布。圖5a為應用PSO 算法的節點分布情況，可見在調度空間的中心位置附近部分節點仍然處于極大的冗余狀態，影響了整體覆蓋效果；圖5b為應用CEVFA 算法的節點分布情況，部分節點超出區域邊界；圖5c為應用本文IVFPSO-E 算法的傳感器節點調度分布情況，節點分布變得相對均勻，覆蓋效果良好。

圖4 初始化隨機覆蓋Fig.4 Optimal coverage of initialization

圖5 三種算法的優化覆蓋Fig.5 Optimized coverage of the three algorithms

綜上，得出3種不同算法在調度過程中，隨著迭代次數變化對覆蓋率造成的影響。其對比結果如圖6所示。

圖6 覆蓋率隨迭代次數變化Fig.6 Coverage versus iteration number

在相同初始條件下分別運行PSO 算法、CEVFA算，以及所提出的IVFPSO 算法。由圖可見，在前20次迭代中，3種算法的覆蓋率均有較大幅度的提高，說明在調度過程的前期，粒子群算法也有著不錯的尋優能力，其中IVFPSO 提高的幅度最大，與初始覆蓋率相比提高了近25個百分點；在50次迭代之后，PSO 算法基本保持不變，說明粒子在后期搜索過程的能力逐漸減弱，可能無法跳出局部最優解，找到全局最優解，但PSO 算法仍具有快速收斂的性質，而CEVFA 算法和本文算法均能在虛擬力的牽動下繼續進行調度覆蓋任務，保持較高的尋優能力，然而與CEVFA 算法相比，本文算法由于融入新的組合參數并得到優化，使得整個調度覆蓋過程中的增長效果都比CEVFA 算法性能有所增幅，最終三者均趨于穩定，得到對應的最優覆蓋率。

5 結語

通過研究區域覆蓋控制問題，根據傳感器屬性特征改進了粒子群算法并融合了虛擬力算法。該改進的混合算法規避了初期節點因聚集分布情況使得算法陷入局部最優解的問題；在后期的處理上提升了其全局尋優的能力，使算法的收斂性、魯棒性更強。在解決實際問題上，提高了節點布控的均衡性，更好地適應了調度覆蓋問題，調度后的覆蓋效果更為均勻合理。后續將進一步研究考慮調度傳感器覆蓋過程中的能量消耗問題，進而延長調度區域的生命周期。