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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 融合虛擬力的改進(jìn)粒子群增強(qiáng)覆蓋算法

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

3.1 PSO的改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 試驗(yàn)仿真結(jié)果

4.1 試驗(yàn)環(huán)境

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

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

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

4.2 仿真結(jié)果

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

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

圖4 初始化隨機(jī)覆蓋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

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

5 結(jié)語

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