最小化移动传感器最大迁移距离的快速栅栏覆盖算法

姚 培，黄培煌，郭龙坤

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.