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

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

0 概述

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

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

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

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

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

1 MNPSCP 模型

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

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

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

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

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

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

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

2 MNPSCP 問題的貪心算法

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

算法1貪心算法

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

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

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

3 MNPSCP 問題的遺傳算法

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

算法2遺傳算法

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

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

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

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

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

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

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

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

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

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

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

4 MNPSCP 問題的遺傳模擬退火算法

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

算法3遺傳模擬退火算法

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

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

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

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

3）遺傳操作。

4）模擬退火操作。

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

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

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

（4）降溫過程。令Ts=αTs。

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

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

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

5.1 貪心算法

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

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

5.2 遺傳算法

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

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

5.3 遺傳模擬退火算法

6 實驗結(jié)果與分析

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

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

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

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

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

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

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

7 結(jié)束語

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