最小化移動傳感器最大遷移距離的快速柵欄覆蓋算法

姚 培，黃培煌，郭龍坤

1(福州大學 數學與計算機科學學院，福州 350116)

2(福州大學 物理與信息工程學院，福州 350116)

1 引 言

本世紀以來，隨著微機電系統、片上系統、無線通信和低功耗嵌入式技術的飛速發展，無線傳感器網絡快速興起.近年來由于其低功耗、低成本、分布式和自組織的特點，無線傳感器網絡更在軍事、農業、環境監測、智能交通、建筑物監測等領域展現了廣闊應用前景和工業價值，得到了眾多計算機網絡研究者的關注.覆蓋問題是無線傳感器網絡當前的一個研究熱點，其主要包括柵欄覆蓋[11]和區域覆蓋[17].對于一個給定的區域，區域覆蓋的目標是保證區域中的每個點至少被一個傳感器所覆蓋.柵欄覆蓋則對給定區域中的特定柵欄進行監測，使得當有入侵者穿過柵欄時能夠被傳感器檢測到.柵欄覆蓋的主要優點是其所使用的傳感器數量遠少于區域覆蓋，因此在大規模覆蓋中具有更好的經濟價值.

在傳統無線傳感器網絡中，傳感器不具備移動能力.部署傳感器對柵欄的覆蓋之后，一個問題是傳感器之間可能存在漏洞，而無法完成對柵欄的完全覆蓋.在移動無線傳感網中，一些傳感器具備移動能力，從而能通過它們的移動覆蓋漏洞，以完全覆蓋柵欄.由于無線傳感器配備的電池能耗有限，故需要研究如何最小化最大的電池能耗，使得柵欄覆蓋的持續時間最久.這產生了最小化最大移動的柵欄覆蓋問題(Minimum-Maximum Sensor Movement problem，MMSM).

1.1 問題模型

本文主要研究柵欄為直線且傳感器的初始位置都在直線上時的MMSM問題，即一維的最小化最大移動的柵欄覆蓋問題(1-Dimensional Minimum-Maximum Sensor Movement problem，1D-MMSM)，其定義如下：

1.2 相關工作

文章[23]首次研究了1D-MMSM問題，并給出了一個多分辨率融合算法.文章[17]則給出了改進的貪心算法以及循環貪心算法兩個傳感器自部署算法.對于傳感器感知半徑相同時的1D-MMSM問題，文章[6]給出了以下算法：當傳感器不能完全覆蓋給定的柵欄時，對于連續和不連續的情況提出了一個線性時間最優算法獲得最大覆蓋；而當傳感器能夠完成覆蓋時，則給出了一個O(n2)時間算法.之后在文章[5]算法的時間復雜度降低到O(n log n)，且對感知半徑不同的情況給出了一個O(n2log n log log n)時間的算法.文章[25]中對于基于線段布置的柵欄覆蓋進行了廣泛的研究，為后來的學者對柵欄覆蓋的研究更好的進行打下了基礎.Saipulla等人的研究表明：當隨機偏移量明顯小于傳感器的感知半徑時，基于行的柵欄覆蓋明顯優于泊松模型的柵欄覆蓋.而Chen等人則對局部局部柵欄覆蓋進行了更多的研究，證明了單個傳感器可以局部確定局部屏障的存在[4].

當傳感器的初始位置分布在平面上而非在直線上時，相應的柵欄覆蓋問題為2D-MMSM問題.Liu和Towsley兩人首次在文章[18]中研究了2D-MMSM問題.之后文章[8]證明了二維平面的最小化最大傳感器移動問題(2D-MMSM)在傳感器感知半徑不同時是一個NP-完全問題.

1D-MMSM問題的一些變體也得到了很好的研究.當優化目標是使用最少數量的傳感器，而非最小化最大移動距離時，為Min-Num柵欄覆蓋問題.若所給定的傳感器具有相同的監測半徑，則Min-Num柵欄覆蓋問題是多項式時間可解的.對該問題J.Czyzowice等人給出一個運行時間為O(n2)的算法，同時也證明了對于傳感器不同的監測半徑，Min-Num柵欄覆蓋問題在傳感器移動距離之和小于k的條件下是NP-難的[7].Mehrandish等人則證明對于傳感器監測半徑不同時，這個問題為一個-NP難問題[22].柵欄的邊界并不一定只有線段，因此圓或者多邊形柵欄覆蓋也得到研究者的關注.文章[1]給出圓與多邊形柵欄覆蓋的算法：圓形柵欄的覆蓋算法運行時間為O(n3.5log n)；多邊形柵欄的覆蓋算法運行時間為O(n3.5log n).圓形柵欄的覆蓋算法在之后文章[28]中運行時間被降低到O(n2.5log n).

在移動傳感器出現之前，使用固定傳感器進行柵欄覆蓋最早出現在文章[9]中.文章[11]中將傳感器的布置轉化為點不相交路徑并給出了一個高效算法.同時在這篇文章中也將柵欄覆蓋分為強柵欄覆蓋和弱柵欄覆蓋兩種，并且分析了柵欄覆蓋相對于區域覆蓋的優勢：對于同一區域柵欄覆蓋使用的傳感器數量少于區域覆蓋使用的傳感器數量.對于柵欄覆蓋而言，睡眠喚醒問題是-NP難的[27]，文章[13]給出了一個通過柵欄覆蓋的睡眠喚醒問題來延長傳感器使用周期的算法.其它傳感器覆蓋問題也陸續得到研究.Li和Wan等人關于路徑覆蓋問題提出了一個更加高效的分布式算法[16]；Huang和Tseng給出了一個將傳感器數量轉化為分布式協議的多項時間算法[10]；Cardei和Wu解決了靜態無線傳感器網絡的節能覆蓋問題[3]；Krumar等人在給定的傳感器位置是確定的情況下提出了一個判斷柵欄是否被完全覆蓋的算法[11]；Shen等人對于傳感器網絡遷移問題更加關注于能量屏障覆蓋問題[26]；Liet等人提出關于傳感器布置的最小花費問題，并在離散情況下給出了一個多項式時間算法，在連續情況下給出一個常數時間的近似算法[15]；Kumar等人研究了傳感器網絡的k覆蓋問題[12]，Li等人進一步提出了一個算法判斷柵欄是否為弱-柵欄覆蓋[14]；Wang等人給出了無線傳感器網絡柵欄覆蓋容忍誤差的計算方法[31]；Mehrandish等人對于路由選擇給出了一個局部搜索算法以及連通的控制集算法[21]；一些早期的柵欄覆蓋問題的研究可參見[2].

其他的柵欄覆蓋問題主要研究使用具有更多功能的傳感器如：有移動能力限制的移動傳感器[24]，移動相機傳感器[19，30]，最小相機柵欄覆蓋[20]，定向傳感器網絡[29]以及混合定向傳感器網絡[32]等.

1.3 組織結構

本文第2部分對于D1D-MMSM問題提出一個簡單的貪心算法求解，即在確定的遷移距離D下是否存在柵欄的一個可行覆蓋；第3部分基于一個提出的充分條件給出算法正確性的證明；第4部分設計了驗證實驗，并給出實驗分析結果；第5部分總結并給出文章的結論.

算法1. D1D-MMSM問題的一個貪心算法

輸入：一個移動距離上界D∈Z+，柵欄的長度M，一個傳感器集合Γ={1，…，n}，傳感器i的半徑為{Ri|i∈[n]+}，初始位置為xi；

1：令I：=Γ，s：=0；/*s為柵欄未被覆蓋區域最左端點.*/

2：對每個傳感器i：

計算傳感器i能夠監測的最左端點li和最右端點gi；

3：當I≠?且存在i′∈I使得li≤s≤gi則

/*在傳感器{i′|Ii′≤s}之間選擇gi最小的傳感器；*/

6： 如果s>M則

8： 否則

9： 輸出＂問題無解＂.

2 1D-MMSM的貪心算法

令[li，gi]為傳感器i在柵欄所在直線上能夠覆蓋的最大范圍，其中li和gi分別為在給定的柵欄所在的直線上傳感器能夠通過移動監測到的最大范圍的最左端點和最右端點，即傳感器i在遷移距離D之下能夠覆蓋的最左端點和最右端點.本文算法的主要思想是：依據[li，gi]，選擇傳感器i從柵欄最左端未被覆蓋的點s向右依次進行覆蓋，直到柵欄被完全覆蓋或發現不存在一個合法覆蓋為止.

圖1 一個算法1運行的例子Fig.1 An example of executing Algorithm 1

引理1.算法1的運行時間是O(n log n).

證明：算法步驟2花費O(n)時間來計算每個傳感器的li和gi；步驟3-7從左到右對柵欄進行覆蓋，需要花費O(n log n)時間將傳感器根據li和gi進行排序.因此，算法總時間為O(n log n).

定理1.算法1返回“可行解”當且僅當線段[0，M]在遷移距離D下能夠被傳感器完全覆蓋.

3 定理1證明

證明算法1能夠輸出最優解的主要思想是：首先說明若一個1D-MMSM問題在遷移距離D下是可解的，則存在一個s-有序的最優解，之后將證明算法1能夠輸出一個s-有序的最優解.因此論文首先在引理2中證明對于傳感器覆蓋的最優解是能夠直接滿足或在交換后滿足s-有序且不會產生漏洞.對于引理2的證明主要分為兩個步驟：首先考慮無序傳感器對之間不存在傳感器的情況下，無序的傳感器對能否交換；然后考慮無序傳感器對之間存在其他傳感器的情況下，無序的傳感器對能否交換，交換之后其他傳感器的處理.

算法2.交換算法

輸入：一個覆蓋柵欄的最優解.

1.從左到右檢查傳感器序列；

且gwi>gwj則；

3. 找出傳感器wi，wj之間的傳感器{v1，…，vn}；

4. 如果Rwi≤Rwj則

5. 交換傳感器wi，wj的位置，其他傳感器向右移動2Rwj-2Rwi；

7. 從x"wj向右繼續檢查新產生的序列；

8. 如果Rwi>Rwj則

9. 令Γ1=?，Γ2=?，

11. Γ1=Γ1Ujn；

13. Γ2=Γ2Ujn；

直到最左端的傳感器覆蓋x"wi+Rwi，傳感器wi向

移動使x"wj-Rwi覆蓋Γ1最右端點，Γ1中的傳感器

15. 從x"wj向右繼續檢查新產生的序列；

16.返回新的位置序列{x"wi|wi∈[n]+}.

1.在i1，i2之間無傳感器

在這種情況下，傳感器i1覆蓋的最左端點為s，傳感器i2覆蓋的最右端點為v.因傳感器i1，i2均能覆蓋點s且gi1>gi2，則交換傳感器位置后傳感器i1能夠覆蓋點v且傳感器i2能夠覆蓋點s不會形成漏洞.

2.在i1，i2之間存在傳感器

假設i1，i2之間存在的傳感器為j1，…，jn，傳感器i1覆蓋的右端點為u.

Ⅰ.Ri1≤Ri2

(1)

則可知：

(2)

算法3.刪除冗余的傳感器算法

輸入：算法1產生的傳感器集合Γ={1，…，n}的位置序列X以及相應的半徑序列R；

輸出：一個新的序列

1.令s=0，ss=0，Φ=Γ；

2.計算s=X+R；ss=X-R；

3.當Φ≠?則

4. 若對任意傳感器在傳感器集合φi有s(i)≥s(j)

且ss(i)≥ss(j)則

/*φi為傳感器集合Γ={1，…，n}中傳感i之后的所有傳感器*/

5. 刪除傳感器i；

6. 若對任意傳感器i在傳感器集合φi有s(i)≤s(j)

且ss(i)≥ss(j)則

7. 刪除傳感器j；

8. 若對傳感器i在傳感器集合φi有s(i)=ss(j)則

9. 刪除傳感器i+1；

10.令Φ=Φ-{i}，轉到步驟 3.

若u?[ljj，gjj]，則對于傳感器k1，…kd，由于傳感器kn(n=1，…，d)不能覆蓋u則需要證明的是在傳感器i1，i2交換位置之后，傳感器kn(n=1，…，d)能否可以向右移動使得柵欄上沒有漏洞.

(3)

(4)

Ⅱ·Ri1>Ri2

(5)

圖2 兩個算法的運行時間Fig.2 Runtime of the two algorithms圖3 兩個算法的解值相同Fig.3 Identical value of the output solution of the two algorithms

則可知道：

(6)

基于引理2，下面給出定理1的證明.定理1的證明主要通過對比算法輸出的可行解與s-有序的可行解之間的關系.

4 實驗仿真結果

4.1 仿真實驗環境

本實驗的運行環境基于鐳龍APU處理器A10-7850K與Windows 7操作系統.為評估算法的性能，本文使用Matlab語言進行編程設計，其版本為Matlab2009a.在仿真實驗中，每個傳感器的初始位置位于線段所在直線上且是隨機生成的，所有傳感器的半徑是10～50中隨機的一個數值.傳感器的數量范圍是100～1000.評估性能的指標是算法是否產生最優解，以及算法的運行時間，使用的傳感器數量，使用的傳感器半徑之和，與使用的傳感器的平均半徑.

4.2 算法比較

文章[5]中給出解決1D-MMSM問題的一個算法，記該算法為CDG-算法.該算法是從給定的柵欄上未被覆蓋的點s開始，找出滿足li≤s≤gi的傳感器集合Si1，若Si1≠?，則找到集Si1中gi最大的傳感器i′，即gi′=max{gi}，此時s=s+2Ri′；若Si1=?，則找到滿足0

在算法1計算完成覆蓋之后，可以通過檢測冗余覆蓋的傳感器集合減少使用的傳感器個數.即若一個傳感器覆蓋的區域同時被其他傳感器完全覆蓋，則這個傳感器可從覆蓋集中刪除(詳見算法3).對比算法1與CDG-算法所使用的傳感器的總半徑和傳感器的總數量，如圖4，圖5.則由圖可以看出算法1使用的傳感器數量以及使用傳感器的總半徑長度是多于CDG-算法使用的傳感器數量及傳感器半徑的總長度.對比算法1CDG-算法使用的傳感器平均半徑，如圖6.從圖中可知算法1使用的傳感器的平均半徑小于CDG-算法使用的傳感器的平均半徑.

圖4 兩個算法使用的傳感器數量對比Fig.4 Comparison of the numbers of used sensors in the two algorithms

圖5 兩個算法使用的傳感器的總半徑對比Fig.5 Comparison of the radius sum of the used sensors in the two algorithms

圖6 兩個算法使用傳感器的平均半徑對比Fig.6 Comparison of the average radius of the used sensors in the two algorithms

5 結 論

本文研究了一維柵欄上的最小化最大傳感器移動距離(1D-MMSM)問題，并給出了一個基于貪心策略與排序的運行時間為O(nlognlog (M+dmax))的快速算法.理論分析表明，本文所設計算法可求出問題最優解，并且時間復雜度優于前人算法.實驗分析表明，本文算法的實際性能也同樣優于前人算法.本文算法的缺點在于其使用的傳感器數量多于前人算法，原因在于算法1使用傳感器的平均半徑可能小于所對比算法.

：

[1] Binay Bhattacharya，Mike Burmester，Hu Yu-zhuang，et al.Optimal movement of mobile sensors for barrier coverage of a planar region [J].Theoretical Computer Science，2009，410(52)：5515-5528.

[2] Meguerdichian S，Koushanfar F，Potkonjak M，et al.Coverage problems in wireless ad-hoc sensor networks[C].Proceedings of the Twentieth Joint Conference of the IEEE Computer and Communications Societies(INFOCOM)，IEEE，2014，3：1380-1387.

[3] Mihaela Cardei and Jie Wu.Energy-efcient coverage problemsin wireless ad-hoc sensor networks[J].Computer Communications，2006，29(4)：413-420.

[4] Ai Chen，Santosh Kumar，Ten H Lai.Local barrier coveragein wireless sensor networks[J].IEEE Transactions on Mobile Computing，2010，9(4)：491-504.

[5] Danny Z Chen，Yan Gu，Jian Li，et al.Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain[J].Discrete & Computational Geometry，2013，50(2)：374-408.

[6] Jurek Czyzowicz，Evangelos Kranakis，Danny Krizanc，et al.On minimizing the maximum sensor movement for barrier coverage of a line segment[C].International Conference on Ad-Hoc，Mobile and Wireless Networks，Springer，2009：194-212.

[7] Jurek Czyzowicz，Evangelos Kranakis，Danny Krizanc，et al.On minimizing the sum of sensor movements for barrier coverage of a line segment[C].International Conference on Ad-Hoc，Mobile and Wireless Networks，Springer，2010：29-42.

[8] Stefan Dobrev，Stephane Durocher，Mohsen Eftekhari，et al.Complexity of barrier coverage with relocatable sensors in the plane [J].Theoretical Computer Science，2015，579：64-73.

[9] Douglas W Gage.Command control for many-robot systems [R].Naval Command Control and Ocean Surveillance Center Rdt and E Div San Diego Ca，1992.

[10] Chi-Fu Huang，Yu-Chee Tseng.The coverage problem ina wireless sensor network[J].Mobile Networks and Applications，2005，10(4)：519-528.

[11] Santosh Kumar，Ten H Lai，Anish Arora.Barrier coverage with wireless sensors[C].Proceedings of the 11th Annual International Conference on Mobile Computing and Networking，ACM，2005：284-298.

[12] Santosh Kumar，Ten H Lai，et al.On k-coveragein a mostly sleeping sensor network[C].Proceedings of the 10th Annual International Conference on Mobile Computing and Networking，ACM，2004：144-158.

[13] Santosh Kumar，Ten H Lai，Marc E Posner，et al.Optimal sleep-wakeup algorithms for barriers of wireless sensors [C].Proceedings of the Fourth International Conference on Broadband Communications，Networks and Systems(BROADNETS 2007)，IEEE，2007：327-336.

[14] Li Lei，Zhang Bao-xian，Shen Xiao-jun，et al.A study on the weak barrier coverage problem in wireless sensor networks [J].Computer Networks，2011，55(3)：711-721.

[15] Li Min-ming，Sun Xian-wei，Zhao Ying-chao.Minimum cost linear coverage by sensors with adjustable ranges[C].Proceedings of the 2011 International Conference on Wireless Algorithms，Systems，and Applications. Springer，2011：25-35.

[16] Li Xiang-yang，Wan Peng-jun，Ophir Frieder.Coveragein wireless ad hoc sensor networks[J].IEEE Transactions on Computers，2003，52(6)：753-763.

[17] Li Xu，Hannes Frey，Nicola Santoro，et al.Localized sensor self-deployment with coverage guarantee[J].Acmsigmobile Mobile Computing and Communications Review，2008，12(2)：50-52.

[18] Benyuan Liu and Don Towsley.A study of the coverage of large scale sensor networks[C].Proceedings of the 2004 IEEE International Conference on Mobile Ad-hoc and Sensor Systems，IEEE，2004：475-483.

[19] Liu Xiao-lan，Yang Bin，Chen Gui-lin.Barrier coveragein mobile camera sensor networks with grid-based deployment[J].ArXiv preprint arXiv：1503.05352，2015.

[20] Ma Huan，Yang Meng，Li De-ying，et al.Minimum camera barrier coverage in wireless camera sensornetworks[C].Proceedings of the 31rd IEEE International Conference on Computer Communica-tions(INFOCOM).IEEE，2012：217-225.

[21] Mona Mehrandish.On routing，backbone formation and barriercoverage in wireless Ad Hoc and sensor networks[D].PhD Thesis，Concordia University，2011.

[22] Mona Mehrandish，Lata Narayanan，Jaroslav Opatrny.Minimizing the number of sensors moved on line barriers[C].Proceedings of the IEEE 2011 Wireless Communications and Networking Conference (WCNC).IEEE，2011：653-658.

[23] Qi Hai-rong，Iyengar S，Krishnendu Chakrabarty.Multi resolution data integration using mobile agents in distributed sensor networks[J].IEEE Transactions on Systems，Man，and Cybernetics，Part C(Applications and Reviews)，2001，31(3)：383-391.

[24] Anwar Saipulla，Liu Ben-yuan，Xing Guo-liang，et al.Barrier coverage with sensors of limited mobility[C].Proceedings of the Eleventh ACM International Symposium on Mobile ad hoc Networking and Computing(Mobicom)，ACM，2010：201-210.

[25] Anwar Saipulla，Cedric Westphal，Benyuan Liu，et al.Barrier coverage of line-based deployed wireless sensor networks[C].Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM 2009).IEEE，2009：127-135.

[26] Shen Chang-xiang，Cheng Wei-fang，Liao Xiang-ke，et al.Barrier coverage with mobile sensors[C].Proceedings of the 2008 International Symposium on Parallel Architectures，Algorithms，and Networks (I-SPAN 2008).IEEE，2008：99-104.

[27] Sasha Slijepcevic，Miodrag Potkonjak.Power efcient organization of wireless sensor networks[C].Proceedings of the IEEE 2001 International Conference on Communications(ICC 2001).IEEE，2001，2：472-476.

[28] Tan Xue-hou，Wu Gang-shan.New algorithms for barriercoverage with mobile sensors[C].Proceedings of the 2010 International Workshop on Frontiers in Algorithmics.Springer，2010：327-338.

[29] Tao Dan，Tang Shao-jie，Zhang Hai-tao，et al.Strong barrier coverage in directional sensor networks[J].Computer Communications，2012，35(8)：895-905.

[30] Wang Yi，Cao Guo-hong.Barrier coverage in camera sensor networks[C].Proceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc Networking and Computing,ACM，2011：12.

[31] Wang Zhi-bo，Chen Hong-long，Cao Qing，et al.Fault tolerant barrier coverage for wireless sensor networks[C].Proceedings of the 33rd IEEE International Conference on Computer Communications(INFOCOM)，IEEE，2014：1869-1877.

[32] Wang Zhi-bo，Liao Ji-long，Cao Qing，et al.Achieving k-barrier coverage in hybrid directional sensor networks [J].IEEE Transactions on Mobile Computing，2014，13(7)：1443-1455.