移動傳感器網絡中路徑掃描覆蓋問題研究

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

（1.華東理工大學 數學學院，上海 200237；2.華東理工大學 商學院，上海 200237）

0 概述

隨著無線通信技術、傳感技術、微機電系統等迅速發展，無線傳感器網絡得到了廣泛應用，并逐漸在軍事國防、搶險救災、生態監測、醫療護理、智能家居、目標保護與追蹤等領域體現出越來越高的使用價值［1-2］。傳感器網絡的典型系統結構包括感知、通信、供能、數據處理等單元［3-4］。節點感知、接收和處理被覆蓋區域的信息，并通過接收發送器將信息傳輸至遠程控制中心［5］。由于信息傳輸的質量和及時性與節點覆蓋的方式有較大聯系，因此覆蓋問題是無線傳感器網絡中基本問題之一［6-7］。

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

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

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

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

1 MNPSCP 模型

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

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

由此可得如下整數規劃模型ILP-1：

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

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

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

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

2 MNPSCP 問題的貪心算法

本節將針對MNPSCP 問題設計貪心算法，以快速高效求解［22］MNPSCP 問題。貪心算法的主要思想是在選擇傳感器的過程中，每次都優先選擇未超時且覆蓋POI 數量最多的傳感器，若傳感器全部用完仍有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，即每個傳感器應該去掃描哪個POI 子集

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

3 MNPSCP 問題的遺傳算法

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

算法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個節點組成s1s2…sn，每個節點sl代表1 個POI 節點，采用一位二進制編碼，即sl=0 或1。編碼表示的含義：若該染色體中=k，則說明編碼為1 的節點sl將路徑分割為k+1 個片段，每個片段代表1 個傳感器規劃的路徑，掃描所有規劃的路徑需使用k+1 個傳感器。按照上述編碼，隨機產生一定數量的染色體，每個染色體隨機產生最多m-1 個編碼為1 的節點，以初始化種群，種群的規模為N。

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

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

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

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

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

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

重復上述遺傳操作，產生新的種群，直到新的種群與原種群個體數量一致。

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

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

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

算法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）計算適應度函數。

3）遺傳操作。

4）模擬退火操作。

（1）初始化參數。設初始溫度Ts，結束溫度Te，降溫系數α。

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

（3）對新產生的解計算適應度，設為Snew，若Snew>St，則將種群中的該個體替換為新產生的個體；否則，根據Metropolis 準則接受新解，即按照概率接受新解。

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

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

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

5 時間和空間復雜度分析

5.1 貪心算法

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

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

5.2 遺傳算法

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

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

5.3 遺傳模擬退火算法

6 實驗結果與分析

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

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

表1 大規模分組實驗的結果對比Table 1 Comparison of results of large-scale grouping experiment

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

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

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

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

7 結束語

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