移動(dòng)傳感器網(wǎng)絡(luò)中路徑掃描覆蓋問(wèn)題研究

繆欣，陳璇，鮑紅瑩，張靜軒，余煒

（1.華東理工大學(xué) 數(shù)學(xué)學(xué)院，上海 200237；2.華東理工大學(xué) 商學(xué)院，上海 200237）

0 概述

隨著無(wú)線通信技術(shù)、傳感技術(shù)、微機(jī)電系統(tǒng)等迅速發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)得到了廣泛應(yīng)用，并逐漸在軍事國(guó)防、搶險(xiǎn)救災(zāi)、生態(tài)監(jiān)測(cè)、醫(yī)療護(hù)理、智能家居、目標(biāo)保護(hù)與追蹤等領(lǐng)域體現(xiàn)出越來(lái)越高的使用價(jià)值［1-2］。傳感器網(wǎng)絡(luò)的典型系統(tǒng)結(jié)構(gòu)包括感知、通信、供能、數(shù)據(jù)處理等單元［3-4］。節(jié)點(diǎn)感知、接收和處理被覆蓋區(qū)域的信息，并通過(guò)接收發(fā)送器將信息傳輸至遠(yuǎn)程控制中心［5］。由于信息傳輸?shù)馁|(zhì)量和及時(shí)性與節(jié)點(diǎn)覆蓋的方式有較大聯(lián)系，因此覆蓋問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)中基本問(wèn)題之一［6-7］。

在傳統(tǒng)的靜態(tài)覆蓋場(chǎng)景中，網(wǎng)絡(luò)管理者需要部署大量的無(wú)線傳感器，因此產(chǎn)生不必要的能量消耗、高額的運(yùn)營(yíng)成本和維護(hù)成本，而解決這些問(wèn)題需要良好的調(diào)度機(jī)制。LI等［8］提出基于興趣點(diǎn)的掃描覆蓋機(jī)制，大幅減少移動(dòng)傳感器的部署數(shù)量，延長(zhǎng)傳感器網(wǎng)絡(luò)使用壽命。

在掃描覆蓋的應(yīng)用場(chǎng)景中，網(wǎng)絡(luò)管理者采用移動(dòng)的無(wú)線傳感器對(duì)區(qū)域內(nèi)各個(gè)分散的POI 進(jìn)行定期掃描，以滿足POI 的覆蓋間隔需求。LI等［8］將掃描覆蓋應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)中，并證明掃描覆蓋問(wèn)題是一個(gè)NP-Hard問(wèn)題。DU等［9］提出OSweep 算法，并設(shè)計(jì)一個(gè)新的啟發(fā)式算法MinExpand，實(shí)驗(yàn)結(jié)果表明這2 個(gè)算法的性能均較好。CHEN等［10］提出能量約束掃描覆蓋問(wèn)題，并針對(duì)有距離約束和基站成本的掃描覆蓋問(wèn)題設(shè)計(jì)近似比為7的MinDCSC-SB算法。CHEN等［11］通過(guò)減少傳感器移動(dòng)距離進(jìn)行能量約束，提出EEMA 算法，并安排移動(dòng)傳感器到劃分后的區(qū)域中。GORAIN等［12］混合靜態(tài)和移動(dòng)傳感器來(lái)減少能量消耗，提出近似度為5 的算法，并進(jìn)行模擬實(shí)驗(yàn)。LIANG等［13］針對(duì)能量約束情境提出最小距離約束掃描覆蓋問(wèn)題并展開研究，其目標(biāo)為在能量有限情境下找到完成掃描覆蓋的移動(dòng)傳感器及其軌跡的最少數(shù)量。NIE等［14］通過(guò)假設(shè)移動(dòng)傳感器在不同單位路段所產(chǎn)生的能耗不同，將能量限制掃描覆蓋擴(kuò)展到一般能量限制掃描覆蓋，并進(jìn)一步提出GERSC 問(wèn)題，即在能量約束條件下最小化掃描覆蓋范圍內(nèi)所需的移動(dòng)傳感器數(shù)量。ZHANG等［15］綜合考慮有權(quán)重目標(biāo)以及返回時(shí)間約束的無(wú)線傳感器掃描覆蓋問(wèn)題，提出區(qū)域覆蓋算法，并采用仿真實(shí)驗(yàn)說(shuō)明該算法相比MinExpand 等算法的平均掃描覆蓋周期更短，路徑有效率更高。文獻(xiàn)［16］處理了周期性覆蓋興趣點(diǎn)進(jìn)行多移動(dòng)傳感器掃描覆蓋調(diào)度的問(wèn)題，并進(jìn)一步提出CycleSplit、HeterocyceSplit 和PathSplit 3 種常數(shù)因子近似，以最小化不同場(chǎng)景下移動(dòng)傳感器的最長(zhǎng)掃描周期。GUANG等［17］以最大化POI 掃描覆蓋價(jià)值為目標(biāo)，設(shè)計(jì)隨機(jī)取整的近似算法和改進(jìn)的貪心算法。實(shí)驗(yàn)結(jié)果表明2 種算法的求解質(zhì)量雖略低于整數(shù)規(guī)劃算法，但運(yùn)行時(shí)間均更快。SHENG等［18］考慮到傳感器感知范圍受限等問(wèn)題，提出多目標(biāo)優(yōu)化的算法，同時(shí)使節(jié)點(diǎn)的覆蓋面最大及掃描路徑最短，仿真實(shí)驗(yàn)表明該算法在保證覆蓋率的同時(shí)能夠較大程度降低能耗。LIU等［19］針對(duì)帶返回時(shí)間約束的掃描覆蓋問(wèn)題提出最小化移動(dòng)傳感器節(jié)點(diǎn)數(shù)目問(wèn)題，并針對(duì)該問(wèn)題提出G-MSCR 和Min DExpand 算法。

目前的研究主要以最少化傳感器數(shù)量、最小化掃描成本為目標(biāo)，并在此基礎(chǔ)上考慮有界區(qū)域、距離約束、周期性返回基站等問(wèn)題，其中大多數(shù)為非線性模型，一般無(wú)法直接求解。然而，在很多場(chǎng)景中，傳感器成本較高，數(shù)量有限，可能出現(xiàn)某些POI 無(wú)法在掃描周期內(nèi)被覆蓋的情形，導(dǎo)致POI 信息時(shí)效性下降。此時(shí)，掃描覆蓋成本除傳感器耗用成本之外，還包括部分POI 未被及時(shí)掃描覆蓋產(chǎn)生的罰時(shí)代價(jià)。

本文研究最少傳感器數(shù)量-最小罰時(shí)路徑掃描覆蓋（Minimum Sensor Number and Punishment Sweep Coverage on Path，MNPSCP）問(wèn)題，通過(guò)調(diào)度移動(dòng)傳感器掃描給定路徑上的POI 集合，使傳感器使用數(shù)量以及產(chǎn)生的POI 總罰時(shí)成本之和最小。將該問(wèn)題轉(zhuǎn)換為整數(shù)規(guī)劃問(wèn)題，但由于該整數(shù)規(guī)劃解空間很大［20］，只能高效求解中小規(guī)模的實(shí)例，因此本文進(jìn)一步設(shè)計(jì)貪心算法、遺傳算法和遺傳模擬退火算法，從而提高求解質(zhì)量和算法局部尋優(yōu)能力。

1 MNPSCP 模型

在很多場(chǎng)景中，網(wǎng)絡(luò)管理者需要調(diào)用傳感器對(duì)某一條路徑上的POI 進(jìn)行掃描覆蓋。對(duì)于給定路徑上 的POI集合P={1，2，…，n}，配備傳感器集合S={1，2，…，m}，其中第i個(gè)傳感器的移動(dòng)速度為vi，第j個(gè)POI 的掃描周期為Tj。在掃描覆蓋的場(chǎng)景中，每個(gè)POI 在其掃描周期內(nèi)均至少被覆蓋一次，即實(shí)現(xiàn)及時(shí)掃描覆蓋。在傳感器數(shù)量有限的情況下，若存在掃描覆蓋方案能夠滿足掃描覆蓋需求，則探究的問(wèn)題是，如何在確保分布于一條路徑上的POI 均能在各自掃描周期內(nèi)被覆蓋的條件下，通過(guò)調(diào)度移動(dòng)傳感器使其耗用成本最小。由于網(wǎng)絡(luò)管理者需要在網(wǎng)絡(luò)節(jié)點(diǎn)上預(yù)先完成對(duì)無(wú)線傳感器的數(shù)量以及路徑的規(guī)劃，因此不必考慮算法對(duì)傳感器的能耗。

將第i個(gè)傳感器以第j個(gè)POI 為起點(diǎn)向右最遠(yuǎn)可以掃描覆蓋的POI 集合定義為Cij，用變量xij表示傳感器i是否按照Cij進(jìn)行掃描覆蓋，表達(dá)式如式（1）所示：

由此可得如下整數(shù)規(guī)劃模型ILP-1：

式（2）的含義是所有的POI 都需要被掃描覆蓋，式（3）的含義為每個(gè)傳感器只能選擇一種掃描方案，即只能被使用一次。

以上描述了POI 在其掃描周期內(nèi)均被掃描覆蓋的情形，但若對(duì)于上述定義的掃描覆蓋方案，所有POI 均不能被及時(shí)掃描覆蓋，則該模型無(wú)可行解。此時(shí)，對(duì)于未被及時(shí)掃描覆蓋的POI，該模型也沒有考慮到信息時(shí)效性下降而產(chǎn)生的罰時(shí)成本。對(duì)此，本文放寬了對(duì)POI 掃描覆蓋周期的限制，進(jìn)一步提出MNPSCP 問(wèn)題：針對(duì)所有分布在一條路徑上的POI，通過(guò)調(diào)度移動(dòng)傳感器使掃描方案的傳感器耗用成本和POI 的罰時(shí)成本之和最小。在傳感器數(shù)量充足時(shí)，罰時(shí)成本為0，生成所需傳感器數(shù)量成本最少的監(jiān)測(cè)方案；在傳感器數(shù)量不足以完成對(duì)所有POI的及時(shí)掃描覆蓋時(shí)，傳感器耗用成本固定，生成罰時(shí)成本最少的監(jiān)測(cè)方案。罰時(shí)成本的計(jì)算方式：為POI 分配一個(gè)懲罰算子，懲罰算子和超出POI 掃描周期的時(shí)間共同決定了懲罰值，且其隨超時(shí)時(shí)間增加而不斷增大，最終給出POI 全覆蓋的監(jiān)測(cè)方案，使產(chǎn)生的懲罰值之和最小。

傳感器i以第l個(gè)POI 為左端點(diǎn)，可能的掃描覆蓋方案為{l}，{l，l+1}，…，{l，l+1，…，n}，因此，傳感器i所有可能的掃描覆蓋方案共有p=種。將第i個(gè)傳感器的第j個(gè)掃描覆蓋方案定義為Cij，用變量xij表示第i個(gè)傳感器是否按照第j個(gè)方案掃描覆蓋，表達(dá)式如式（1）所示，由此可得整數(shù)規(guī)劃模型ILP-2：，約束條件如式（2）～式（4）所示。其中：f為懲罰算子；tij為第i個(gè)傳感器的第j個(gè)方案的超時(shí)時(shí)間；f(tij)為對(duì)應(yīng)的懲罰值。模型ILP-2 的含義為調(diào)度移動(dòng)傳感器掃描給定路徑上的POI 集合，使其耗用成本以及產(chǎn)生的POI 總罰時(shí)成本之和最小?？偭P時(shí)成本的計(jì)算方式：為所有POI 分配一個(gè)懲罰算子，根據(jù)未被及時(shí)掃描覆蓋的時(shí)間計(jì)算每個(gè)POI的罰時(shí)代價(jià)，并最終求和［21］。

由于整數(shù)規(guī)劃只能求解中小規(guī)模的實(shí)例，為求解大規(guī)模的實(shí)例，本文分別設(shè)計(jì)了貪心算法、遺傳算法和遺傳模擬退火算法。

2 MNPSCP 問(wèn)題的貪心算法

本節(jié)將針對(duì)MNPSCP 問(wèn)題設(shè)計(jì)貪心算法，以快速高效求解［22］MNPSCP 問(wèn)題。貪心算法的主要思想是在選擇傳感器的過(guò)程中，每次都優(yōu)先選擇未超時(shí)且覆蓋POI 數(shù)量最多的傳感器，若傳感器全部用完仍有POI 未被覆蓋，則選擇加入此未被覆蓋的POI后罰時(shí)最小的傳感器。貪心算法具體如下：

算法1貪心算法

輸入POI集合P={1，2，…，n}和相鄰POI之間的距離D={d1，d2，…，dn-1}，其中：第l個(gè)POI 的掃描周期為Tl；dl為第l個(gè)POI與第l+1 個(gè)POI之間的距離；傳感器集合S={1，2，…，m}；傳感器i的移動(dòng)速度為vi

輸出傳感器集合S對(duì)POI 集合P的掃描覆蓋方案C，即每個(gè)傳感器應(yīng)該去掃描哪個(gè)POI 子集

1）對(duì)于任意的i∈S和l∈P，根據(jù)POI 的掃描周期和距離計(jì)算Pil，Pil為第i個(gè)傳感器以第l個(gè)POI 為起點(diǎn)向右最遠(yuǎn)可以掃描覆蓋的集合，令使用的傳感器集合I=?，C=?；

3 MNPSCP 問(wèn)題的遺傳算法

遺傳算法作為一種仿生學(xué)方法，能夠有效解決NP 難問(wèn)題［23-24］，根據(jù)決策變量的0-1 二值變量類型，結(jié)合染色體的二進(jìn)制編碼和遺傳操作，本文在染色體生成和評(píng)估過(guò)程中基于模型的約束條件對(duì)貪心策略進(jìn)行調(diào)整，使模型能夠在較短時(shí)間內(nèi)獲得滿意的近似解。遺傳算法具體如下：

算法2遺傳算法

輸入POI 集合P={1，2，…，n}和相鄰POI 之間的距離D={d1，d2，…，dn-1}，其中：第l個(gè)POI 的掃描周期為Tl；dl為第l個(gè)POI與第l+1 個(gè)POI 之間的距離；傳感器集合S={1，2，…，m}；傳感器i的移動(dòng)速度為vi

輸出傳感器集合對(duì)POI 集合的掃描覆蓋方案

1）染色體編碼與種群的初始化。每個(gè)染色體由n個(gè)節(jié)點(diǎn)組成s1s2…sn，每個(gè)節(jié)點(diǎn)sl代表1 個(gè)POI 節(jié)點(diǎn)，采用一位二進(jìn)制編碼，即sl=0 或1。編碼表示的含義：若該染色體中=k，則說(shuō)明編碼為1 的節(jié)點(diǎn)sl將路徑分割為k+1 個(gè)片段，每個(gè)片段代表1 個(gè)傳感器規(guī)劃的路徑，掃描所有規(guī)劃的路徑需使用k+1 個(gè)傳感器。按照上述編碼，隨機(jī)產(chǎn)生一定數(shù)量的染色體，每個(gè)染色體隨機(jī)產(chǎn)生最多m-1 個(gè)編碼為1 的節(jié)點(diǎn)，以初始化種群，種群的規(guī)模為N。

2）計(jì)算適應(yīng)度函數(shù)。由于遺傳算法中適應(yīng)度越大越有利于種群進(jìn)化，而模型的目標(biāo)函數(shù)則越小越好，因此取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度值。每個(gè)染色體的目標(biāo)函數(shù)值按照下述方式計(jì)算：設(shè)=k，則路徑分為k+1 個(gè)片段，每個(gè)片段的路徑長(zhǎng)度為r1，r2，…，rk+1，將路徑從大到小排序后，設(shè)r1>r2>…>rk+1，若k+1>m，即使用的傳感器數(shù)量超出了給定的限制，則目標(biāo)函數(shù)值為無(wú)窮大；若k+1 ≤m，則將傳感器的速度也從大到小排序，設(shè)v1>v2>…>vm，則安排速度為vi的傳感器掃描長(zhǎng)度為ri的路徑，其超時(shí)時(shí)間為ti，若傳感器未被調(diào)用，則超時(shí)時(shí)間為0。適應(yīng)度函數(shù)形式化定義如下：

3）遺傳操作。對(duì)種群中的個(gè)體根據(jù)適應(yīng)度隨機(jī)進(jìn) 行遺傳操作，包括選擇、交叉、變異。

（1）選擇。采用隨機(jī)競(jìng)爭(zhēng)選擇法，假設(shè)S1，S2，…，SN為種群中各個(gè)個(gè)體的適應(yīng)度，其中N為種群中的個(gè)體數(shù)量，種群中第t個(gè)個(gè)體的適應(yīng)度為St，其被選擇的概率為，那么=1，隨機(jī)選擇2 個(gè)個(gè)體Sa和Sb。

由好產(chǎn)業(yè)與好龍頭帶領(lǐng)，解決貧困人口收益機(jī)制問(wèn)題。因利益機(jī)制不健全這一問(wèn)題在農(nóng)業(yè)產(chǎn)業(yè)扶貧中較為普遍，要將健全的農(nóng)業(yè)產(chǎn)業(yè)扶貧利益機(jī)制相結(jié)合，共享理念貫徹落實(shí)其中，秉承長(zhǎng)短結(jié)合的原則，使貧困人口真正受益。另外，推廣訂單幫扶模式，政府財(cái)政扶持資金根據(jù)相關(guān)比例落實(shí)到集體，村集體根據(jù)資產(chǎn)入股企業(yè)，與企業(yè)簽訂協(xié)議，建立合理的受益分配機(jī)制，企業(yè)形成利益機(jī)制，既能夠提高村民的收益，也能夠調(diào)動(dòng)企業(yè)的積極性。

（2）交叉。采用兩點(diǎn)交叉法，根據(jù)給定的交叉概率pu對(duì)選擇的2 個(gè)個(gè)體進(jìn)行交叉，若交叉，則隨機(jī)選擇2 個(gè)交叉點(diǎn)，將2 個(gè)個(gè)體交叉點(diǎn)之間的染色體交換組成新的個(gè)體；若不交叉，則這2 個(gè)個(gè)體將直接作為新的個(gè)體。

（3）變異。對(duì)于2 個(gè)新的個(gè)體，根據(jù)給定的變異概率pv進(jìn)行變異，隨機(jī)選擇1 個(gè)染色體節(jié)點(diǎn)sl，并作取反運(yùn)算。

重復(fù)上述遺傳操作，產(chǎn)生新的種群，直到新的種群與原種群個(gè)體數(shù)量一致。

4）進(jìn)化迭代。設(shè)置最大進(jìn)化代數(shù)MAXGEN，重復(fù)步驟2 和步驟3，當(dāng)進(jìn)化次數(shù)達(dá)到MAXGEN 時(shí)停止計(jì)算，取適應(yīng)度最高的個(gè)體作為模型的近似解。

4 MNPSCP 問(wèn)題的遺傳模擬退火算法

雖然遺傳算法的全局搜索能力較強(qiáng)，但是算法的“早收斂”特點(diǎn)影響了求解結(jié)果［25］。由于模擬退火算法可以有效避免傳統(tǒng)遺傳算法的早熟現(xiàn)象，因此本文考慮將遺傳算法和模擬退火算法相結(jié)合，使算法更加有效。其基本思路為在遺傳操作后引入模擬退火操作。

算法3遺傳模擬退火算法

輸入POI集合P={1，2，…，n}和相鄰POI之間的距離D={d1，d2，…，dn-1}，其中：第l個(gè)POI 的掃描周期為Tl；dl為第l個(gè)POI與第l+1 個(gè)POI之間的距離；傳感器集合S={1，2，…，m}；傳感器i的移動(dòng)速度為vi

輸出傳感器集合對(duì)POI 集合的掃描覆蓋方案

1）染色體編碼與種群的初始化。

2）計(jì)算適應(yīng)度函數(shù)。

3）遺傳操作。

4）模擬退火操作。

（1）初始化參數(shù)。設(shè)初始溫度Ts，結(jié)束溫度Te，降溫系數(shù)α。

（2）對(duì)于種群中的第t個(gè)個(gè)體，其適應(yīng)度為St。為隨機(jī)產(chǎn)生擾動(dòng)，隨機(jī)生成2 個(gè)點(diǎn)位l和l′，設(shè)l′>l，顛倒l和l′之間的染色體節(jié)點(diǎn)，即s1s2…sj-1sj′sj′-1…sjsj′+1…sn。

（3）對(duì)新產(chǎn)生的解計(jì)算適應(yīng)度，設(shè)為Snew，若Snew>St，則將種群中的該個(gè)體替換為新產(chǎn)生的個(gè)體；否則，根據(jù)Metropolis 準(zhǔn)則接受新解，即按照概率接受新解。

（4）降溫過(guò)程。令Ts=αTs。

（5）若Ts>Te，則一直重復(fù)步驟（2）～步驟（5）。

5）進(jìn)化迭代。設(shè)置最大進(jìn)化代數(shù)MAXGEN，重復(fù)算法3 的步驟2）～步驟4），當(dāng)進(jìn)化次數(shù)到達(dá)MAXGEN時(shí)停止計(jì)算，取適應(yīng)度最高的個(gè)體作為模型的近似解。

5 時(shí)間和空間復(fù)雜度分析

5.1 貪心算法

算法1 中的步驟1 需要的運(yùn)行時(shí)間為O(mn2)，步驟2～步驟4 需要的運(yùn)行時(shí)間為O(mn)，步驟5 需要重復(fù)步驟2～步驟4 至多m次，因此步驟1～步驟5需要的運(yùn)行時(shí)間為O(m2n2)。步驟6 和步驟7 的運(yùn)行時(shí)間相對(duì)于步驟1～步驟5 的更少，因此貪心算法的時(shí)間復(fù)雜度為O(m2n2)。

貪心算法的空間復(fù)雜度主要體現(xiàn)在步驟1 中的掃描覆蓋方案消耗內(nèi)存，其他變量則相對(duì)為常數(shù)，故空間復(fù)雜度為O(mn2)。

5.2 遺傳算法

算法步驟1 需要的運(yùn)行時(shí)間為O(Nn)，步驟2 需要對(duì)種群中的每個(gè)個(gè)體計(jì)算適應(yīng)度，遍歷個(gè)體需要的運(yùn)行時(shí)間為O(n)，排序需要的運(yùn)行時(shí)間為O(nlogan)，遺傳操作的運(yùn)行時(shí)間相對(duì)步驟1 和步驟2的更少，因此步驟2 和步驟3 需要的運(yùn)行時(shí)間為O(Nnlogan)。由于需要迭代MAXGEN 次，因此遺傳算法的時(shí)間復(fù)雜度為O(MAXGEN×Nnlogan)。

遺傳算法中種群的復(fù)雜度為O(Nn)，而適應(yīng)度評(píng)估、遺傳操作等均可以原地實(shí)現(xiàn)，故遺傳算法的空間復(fù)雜度為O(Nn)。

5.3 遺傳模擬退火算法

6 實(shí)驗(yàn)結(jié)果與分析

為檢驗(yàn)上述算法的性能，本文基于MATLAB編寫程序進(jìn)行仿真實(shí)驗(yàn)。在仿真場(chǎng)景中，傳感器和POI的參數(shù)范圍參考文獻(xiàn)［4，26］，并由程序隨機(jī)生成，設(shè)置罰時(shí)算子為線性算子f(tij)=αtij。傳感器的移動(dòng)速度范圍為8～10 m/s，POI 之間的距離為80～120 m，掃描周期為80～100 s。實(shí)驗(yàn)環(huán)境為windows10 系統(tǒng)，12 GB 內(nèi)存，Intel i7-7500U 處理器。

由于整數(shù)規(guī)劃模型可以較快地求解中小規(guī)模實(shí)例，而較大規(guī)模實(shí)例難以求解，故本實(shí)驗(yàn)在不同的懲罰算子下，對(duì)比在較大規(guī)模實(shí)例中不同算法的性能。由于需要對(duì)比算法產(chǎn)生的近似解與最優(yōu)解的差距，因此將傳感器分為每組10 個(gè)，同組內(nèi)移動(dòng)速度相同，不同組的傳感器移動(dòng)速度不同，以簡(jiǎn)化變量、加快求解速度。實(shí)驗(yàn)將對(duì)比整數(shù)規(guī)劃、貪心算法、遺傳算法和遺傳模擬退火算法在不同懲罰算子和數(shù)據(jù)規(guī)模下的運(yùn)行時(shí)間以及求解質(zhì)量，以完成對(duì)算法性能的綜合評(píng)價(jià)，結(jié)果如表1 所示，其中：近似解是指將算法重復(fù)執(zhí)行10 次的結(jié)果中最優(yōu)的解；平均解是指算法執(zhí)行10 次所得到的所有解的平均值。

表1 大規(guī)模分組實(shí)驗(yàn)的結(jié)果對(duì)比Table 1 Comparison of results of large-scale grouping experiment

由表1 可知，整數(shù)規(guī)劃求出的是最優(yōu)解，具有最低的覆蓋代價(jià)。對(duì)于貪心算法而言，其運(yùn)行時(shí)間最短，但是求出的解與最優(yōu)解差距較大，質(zhì)量較差。遺傳算法雖然運(yùn)行時(shí)間比貪心算法時(shí)間長(zhǎng)，但解的質(zhì)量比貪心算法要好，在算法執(zhí)行次數(shù)較多時(shí)普遍可以得到比貪心算法更優(yōu)的解，但仍有求解不穩(wěn)定的問(wèn)題，求解平均值有時(shí)比貪心算法好，有時(shí)差。遺傳算法經(jīng)過(guò)模擬退火操作優(yōu)化后，穩(wěn)定性有了明顯提高，其求解的平均值優(yōu)于貪心算法，解的質(zhì)量也明顯優(yōu)于其他算法。

由于遺傳算法的“早收斂”對(duì)求解結(jié)果影響很大，因此本文引入了模擬退火算法。為對(duì)比遺傳算法和模擬退火算法的局部尋優(yōu)能力，本文設(shè)置仿真實(shí)驗(yàn)，實(shí)驗(yàn)中每種算法迭代1 000 次，若每次迭代得出的結(jié)果比迭代前的最優(yōu)結(jié)果更優(yōu)，則認(rèn)為算法跳出了局部極值，不同算法在不同傳感器數(shù)量和POI數(shù)量下跳出局部極值的次數(shù)對(duì)比結(jié)果如表2 所示。已知同一條件下跳出局部極值的次數(shù)越多，局部尋優(yōu)能力越強(qiáng)。由表2 可以看出，遺傳模擬退火算法跳出局部最優(yōu)的能力明顯強(qiáng)于遺傳算法。

表2 不同算法跳出局部極值的次數(shù)對(duì)比Table 2 Comparison of times for different algorithms to jump out of local extremum

綜上可知，遺傳模擬退火算法較好地提升了模擬退火算法的局部尋優(yōu)能力，但對(duì)于全局尋優(yōu)能力沒有明顯提升，求出的解與最優(yōu)解仍有差距，收斂速度相對(duì)遺傳算法較好，適用于大規(guī)模實(shí)例求解。

7 結(jié)束語(yǔ)

本文研究了移動(dòng)傳感器網(wǎng)絡(luò)中最少傳感器數(shù)量-最小罰時(shí)路徑掃描覆蓋問(wèn)題，將該問(wèn)題轉(zhuǎn)換為整數(shù)規(guī)劃模型，并設(shè)計(jì)貪心算法、遺傳算法以及遺傳模擬退火算法。實(shí)驗(yàn)結(jié)果表明：貪心算法的耗時(shí)遠(yuǎn)低于整數(shù)規(guī)劃，但解的質(zhì)量較差；與貪心算法相比，遺傳算法的運(yùn)行時(shí)間更長(zhǎng)，解的質(zhì)量有所提高，但仍有不穩(wěn)定的問(wèn)題。經(jīng)過(guò)模擬退火操作優(yōu)化后，遺傳算法的穩(wěn)定性得到明顯提高，解的平均質(zhì)量?jī)?yōu)于貪心算法，且運(yùn)行時(shí)間比整數(shù)規(guī)劃少。本文的創(chuàng)新點(diǎn)在于放寬POI 掃描覆蓋周期的限制，對(duì)已有研究中掃描覆蓋成本最小問(wèn)題進(jìn)行了拓展，但本文只考慮了一維給定路徑的掃描覆蓋問(wèn)題，下一步可以將其拓展至二維場(chǎng)景，如探究樹形結(jié)構(gòu)或平面上點(diǎn)或網(wǎng)格結(jié)構(gòu)中的最少傳感器數(shù)量-最小罰時(shí)路徑掃描覆蓋問(wèn)題。