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

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

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

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

1 多傳感器調(diào)度覆蓋問題描述

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

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

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

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

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

圖2 區(qū)域覆蓋示意圖Fig.2 Area coverage diagrammatic sketch

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

2 粒子群優(yōu)化下的覆蓋控制

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

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

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

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

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

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

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

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

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

3.1 PSO的改進

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 試驗仿真結(jié)果

4.1 試驗環(huán)境

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

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

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

4.2 仿真結(jié)果

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

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

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

圖5 三種算法的優(yōu)化覆蓋Fig.5 Optimized coverage of the three algorithms

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

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

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

5 結(jié)語

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