張斌權(quán)，陳　永，張　安，陳光亭

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

?

無線傳感器網(wǎng)絡(luò)中的線段覆蓋問題

張斌權(quán)，陳永，張安，陳光亭

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

摘要：線段覆蓋問題是指用盡可能少的傳感器覆蓋某區(qū)域內(nèi)的若干條線段，使得任意線段上的目標(biāo)點均位于至少某一個傳感器的覆蓋區(qū)域內(nèi)。主要討論目標(biāo)點位于水平或垂直方向線段上的情形，通過運用區(qū)域分層思想和傳感器覆蓋的幾何特性設(shè)計了一個求解該問題的多項式時間近似算法，并在理論上證明了該近似算法的性能比為18。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；線段覆蓋；近似算法；性能比

0引言

無線傳感器網(wǎng)絡(luò)通過大量的廉價微型傳感器節(jié)點，采集并處理網(wǎng)絡(luò)覆蓋區(qū)域中被感知對象的信息，從而實現(xiàn)信息傳送的功能?；谖C電系統(tǒng)的微傳感技術(shù)和無線聯(lián)網(wǎng)技術(shù)為無線傳感器網(wǎng)絡(luò)賦予了廣闊的應(yīng)用前景，目前的應(yīng)用領(lǐng)域主要包括環(huán)境檢測、目標(biāo)跟蹤、醫(yī)療護(hù)理及軍事領(lǐng)域等。覆蓋問題是無線傳感器網(wǎng)絡(luò)中一類重要問題，在區(qū)域監(jiān)控和環(huán)境檢測等領(lǐng)域均有廣泛應(yīng)用[1]。區(qū)域覆蓋問題是指用最少個數(shù)的傳感器覆蓋某區(qū)域內(nèi)的若干個目標(biāo)點[2-3]，而蹤跡覆蓋[4]和路徑覆蓋[5]均是考慮目標(biāo)點位于某些道路或者通道的情形。本文所考慮的傳感器覆蓋問題中目標(biāo)點均任意分布于某些水平或者垂直的道路上[6]，該情形在現(xiàn)實生活中較為常見。本文重點研究設(shè)計求解該問題的近似算法，并從理論上給出算法性能比的證明。

1問題陳述

根據(jù)文獻(xiàn)[7]的論述，可以得出上述問題是NP-困難的。所以本文的研究重點為設(shè)計求解該問題的近似算法。基于此，首先研究所有線段都是水平方向放置的情形，隨后討論線段水平方向和垂直方向同時放置的一般情形。

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

2.1　近似算法

根據(jù)前文問題陳述中的數(shù)學(xué)模型，設(shè)計了本近似算法，具體步驟如下：

3)刪除完全包含在矩形區(qū)域ABCD中的所有線段以及部分包含在其中的線段中屬于矩形區(qū)域ABCD的那部分，用步驟2中同樣方法操作Sj層剩余線段，直至覆蓋完Sj層所有線段。

為便于證明文中的主要定理，引入以下記號：

1)Qj：Sj層算法解的傳感器集合；

2)Qj′：覆蓋到Sj層線段的最優(yōu)解傳感器集合；

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

5)Q*：最優(yōu)解的傳感器集合；

圖 1　Sj層的算法解覆蓋

2.2　性能比證明

定理1如果區(qū)域R中所有線段都是水平方向放置的，則算法A的性能比為9且其時間復(fù)雜度為Ο(n2lgn)。

證明為了覆蓋算法步驟2中的每個矩形區(qū)域，算法A至少需要放置3個傳感器，而最優(yōu)解中至少需要放置1個傳感器，于是可得：

|Qj|≤3|Qj′|

(1)

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

(2)

由于算法A的時間復(fù)雜度主要取決于每條線段位置的確定和覆蓋每層中所包含的線段，因此算法的時間復(fù)雜度為O(n2lgn)。定理得證。

類似線段水平方向放置這一情形的算法及其性能比證明得證，同理可以設(shè)計出線段垂直方向放置的算法并給出理論分析。因此，綜合水平方向和垂直方向的兩種特殊情形，可得到如下定理。

定理 2如果區(qū)域R中線段既有水平方向又有垂直方向，則可設(shè)計出求解該問題的性能比為18的近似算法，且其時間復(fù)雜度O(n2lgn)。

3結(jié)束語

參考文獻(xiàn)

[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

文獻(xiàn)標(biāo)識碼：A

文章編號：1001-9146(2015)06-0093-03

通訊作者：

作者簡介：張斌權(quán)(1991-)，男，浙江嵊州人，在讀研究生，運籌學(xué)與控制論.陳永副教授，E-mail：chenyong@hdu.edu.cn.

基金項目：國家自然科學(xué)基金資助項目(11401149)

收稿日期：2015-02-05

DOI：10.13954/j.cnki.hdu.2015.06.020