无线传感器网络中的线段覆盖问题

张斌权，陈　永，张　安，陈光亭

(杭州电子科技大学理学院，浙江 杭州 310018)



无线传感器网络中的线段覆盖问题

张斌权，陈永，张安，陈光亭

(杭州电子科技大学理学院，浙江 杭州 310018)

摘要：线段覆盖问题是指用尽可能少的传感器覆盖某区域内的若干条线段，使得任意线段上的目标点均位于至少某一个传感器的覆盖区域内。主要讨论目标点位于水平或垂直方向线段上的情形，通过运用区域分层思想和传感器覆盖的几何特性设计了一个求解该问题的多项式时间近似算法，并在理论上证明了该近似算法的性能比为18。

关键词：无线传感器网络；线段覆盖；近似算法；性能比

0引言

无线传感器网络通过大量的廉价微型传感器节点，采集并处理网络覆盖区域中被感知对象的信息，从而实现信息传送的功能。基于微机电系统的微传感技术和无线联网技术为无线传感器网络赋予了广阔的应用前景，目前的应用领域主要包括环境检测、目标跟踪、医疗护理及军事领域等。覆盖问题是无线传感器网络中一类重要问题，在区域监控和环境检测等领域均有广泛应用[1]。区域覆盖问题是指用最少个数的传感器覆盖某区域内的若干个目标点[2-3]，而踪迹覆盖[4]和路径覆盖[5]均是考虑目标点位于某些道路或者通道的情形。本文所考虑的传感器覆盖问题中目标点均任意分布于某些水平或者垂直的道路上[6]，该情形在现实生活中较为常见。本文重点研究设计求解该问题的近似算法，并从理论上给出算法性能比的证明。

1问题陈述

根据文献[7]的论述，可以得出上述问题是NP-困难的。所以本文的研究重点为设计求解该问题的近似算法。基于此，首先研究所有线段都是水平方向放置的情形，随后讨论线段水平方向和垂直方向同时放置的一般情形。

2近似算法及其性能比证明

2.1　近似算法

根据前文问题陈述中的数学模型，设计了本近似算法，具体步骤如下：

3)删除完全包含在矩形区域ABCD中的所有线段以及部分包含在其中的线段中属于矩形区域ABCD的那部分，用步骤2中同样方法操作Sj层剩余线段，直至覆盖完Sj层所有线段。

为便于证明文中的主要定理，引入以下记号：

1)Qj：Sj层算法解的传感器集合；

2)Qj′：覆盖到Sj层线段的最优解传感器集合；

4)QA：算法解的传感器集合；

5)Q*：最优解的传感器集合；

图 1　Sj层的算法解覆盖

2.2　性能比证明

定理1如果区域R中所有线段都是水平方向放置的，则算法A的性能比为9且其时间复杂度为Ο(n2lgn)。

证明为了覆盖算法步骤2中的每个矩形区域，算法A至少需要放置3个传感器，而最优解中至少需要放置1个传感器，于是可得：

|Qj|≤3|Qj′|

(1)

|Qj′|≤|Qj-1*|+|Qj*|+|Qj+1*|

(2)

由于算法A的时间复杂度主要取决于每条线段位置的确定和覆盖每层中所包含的线段，因此算法的时间复杂度为O(n2lgn)。定理得证。

类似线段水平方向放置这一情形的算法及其性能比证明得证，同理可以设计出线段垂直方向放置的算法并给出理论分析。因此，综合水平方向和垂直方向的两种特殊情形，可得到如下定理。

定理 2如果区域R中线段既有水平方向又有垂直方向，则可设计出求解该问题的性能比为18的近似算法，且其时间复杂度O(n2lgn)。

3结束语

参考文献

[1]Thai M T,Wang F,Du D.Coverage problems in wireless sensor networks：Designs and analysis[J].International Journal of Sensor Networks,2008,3(3):191-200.

[2]Barun G,Partha S M.Approximation algorithms for sweep coverage in wireless sensor networks[J].Journal of Parallel and Distributed Computing,2014,74(8),2699-2707.

[3]Tan H S,Hao X H,Wang Y X,et al.An approximate approach for area coverage in wireless sensor networks[J].Procedia Computer Science,2013,19:240-247.

[4]Baumgartner K,Ferrari S.A geometric transversal approach to analyzing track coverage in sensor networks[J].IEEE Transactions on Computers,2008,57(8),1113-1128.

[5]Harada J,Shioda S,Saito H.Path coverage properties of randomly deployed sensors with finite data-transmission ranges[J].Computer Networks the International Journal of Computer & Telecommunications Networking,2009,53(7):1014-1026.

[6]Dinesh D,Arijit B,Arobinda G,et al.Approximation algorithms for deployment of sensors for line segment coverage in wireless sensor networks[J].Wireless Networks,2013,19(5):857-870.

[7]Fowler R J,Paterson M S,Tanimoto S L.Optimal packing and covering in the plane are NP-complete[J].Information Processing Letters,1981,12(3),133-137.

Line Segment Coverage Problem in Wireless Sensor Networks

Zhang Binquan，Chen Yong，Zhang An，Chen Guangting

(SchoolofScience，HangzhouDianziUniversity，HangzhouZhejiang310018，China)

Abstract：The coverage problem is an important problem in many wireless sensor network applications involving surveillance or environmental monitoring of an area.In this paper，we address the problem of covering a set of line segments with minimum number of sensors.A line segment is said to be covered if it is contained in the sensing region of at least one among the sensors.For this problem，a polynomial time approximation algorithm is proposed based on the layered design idea and geometry property of sensor covering.It is proved that the performance ratio of this algorithm is 18.

Key words：wireless sensor networks；line segment coverage；approximation algorithm；performance ratio

中图分类号：O224

文献标识码：A

文章编号：1001-9146(2015)06-0093-03

通讯作者：

作者简介：张斌权(1991-)，男，浙江嵊州人，在读研究生，运筹学与控制论.陈永副教授，E-mail：chenyong@hdu.edu.cn.

基金项目：国家自然科学基金资助项目(11401149)

收稿日期：2015-02-05

DOI：10.13954/j.cnki.hdu.2015.06.020