無線傳感器網絡中基于“k?覆蓋問題”的多項式時間算法

王騏，肖正安，王懷興

?

無線傳感器網絡中基于“?覆蓋問題”的多項式時間算法

王騏，肖正安，王懷興

（湖北第二師范學院物理與機電工程學院，湖北 武漢 430205）

無線傳感器網絡；?覆蓋問題；擴展圓盤；相鄰分界線；多項式時間算法

1 引言

2 基于UDG的幾何圖形

2.1 問題的描述

圖1 ?違反值和?支持值示意

2.2 圓盤的擴展

圖2 大于的“2?違反”路徑

同理可得定理2。

3 解決方案——多項式時間算法

3.1 子區域及其分界線

圖3 子區域及其分界線

由于這段弧是由兩個相鄰子區域相交的公共部分，分屬的兩個子區域的覆蓋度可能不相同，所以根據定義5來計算這段弧的覆蓋度就會產生矛盾[11]。為此特做以下定義。

圖4 內弧和外弧

定義7 （相鄰分界線）如果兩段分界線（內弧、外弧或邊界線）具有公共點，那么稱這兩段分界線為相鄰分界線。

根據定義7，由于同一段弧的內弧和外弧具有無限多個共同點，因此它們互為相鄰弧。當且僅當兩段分界線具有相同交點或切點時，它們互為相鄰分界線，如圖3所示。由于子區域可看成是由若干相鄰分界線形成的，因此，這些分界線具有和子區域相同的覆蓋度。

Procedure:/*計算所有的分界線，并且判定兩段分界線是否為相鄰分界線

input: 傳感器節點集{1,2,…, s}，圓半徑

output: 分界線集{1,2,…, bor}

for1 to

計算disk和所有其他圓或邊界線的交點或切點

for 圓周線上的每對相鄰交點或切點

定義分界線bor

劃分bor為內弧和外弧

for 平面邊界線上的每對相鄰交點或切點

定義分界線bor

/*計算每段分界線的覆蓋度

for 每段分界線bor

switch（分界線類型）

casebor為邊界線的一部分

選取點poi∈bor

計算點poi的范圍內傳感器節點數量

casebor為一段外弧

選取點poi∈bor

計算點poi的范圍內傳感器節點數量，不包括poi所屬圓的中心節點

casebor為一段內弧

選取點poi∈bor

計算點poi的范圍內傳感器節點數量，包括poi所屬圓的中心節點

/*判定兩段分界線是否互為相鄰分界線

set 所有分界線為非相鄰分界線

for 每個交點或切點poi

ifpoi為bor和bor的端點

setbor和bor為相鄰分界線

end

3.2 最差k?覆蓋問題

input: 邊界線集合{1,2,…,},∈,∈

output: 布爾變量結果值

if()≥或() ≥

= 0

return

取消所有分界線的標記

標記/*起始于

list=

tree=

while（非空）

從鏈表頭選取分界線

從鏈表刪除分界線

for相鄰的每段分界線

if()

標記

在樹上將作為的孩子

在鏈表尾增加

if被標記

= 1

return

else

= 0

return

end

set/*設定搜索空間的上限值

set/*設定搜索空間的下限值

set/*設定迭代次數

for= 1 to

= (+)2

{1,2,…,}=() /*調用函數(,)計算所有的分界線

if= 1

=

else

end

上限值和下限值可根據平面維度以及傳感器節點的密度來設定。每次迭代將使搜索空間減半，例如，如果搜索空間（||）的值為1 000，經過10次迭代可得到結果，且誤差小于1。一般情況下，10～20次迭代可足以確保結果的準確性[15]。

3.3 最佳k?覆蓋問題

4 仿真結果

圖5 k?違反的最大值

圖6 k?支持的最小值

對比圖5和圖6，可得到以下結論。

? 當傳感器節點數量相同時，?支持的最小值要遠大于?違反的最大值。可以證明，任何情況下，?支持的最小值均不會小于?違反的最大值。

5 結束語

本文分別闡述了最差和最佳?覆蓋問題，并基于擴展圓盤的幾何圖形提出了一系列的定義和定理，將?覆蓋問題轉化成了尋找相鄰分界線的問題，提出了解決此問題的多項式時間算法。

[1] MEGERIAN S, KOUSHANFAR F, POTKONJAK M, et al. Worst and best-case coverage in sensor networks[J]. IEEE Transaction on Mobile Computing, 2005, 4(1):84-92.

[2] 楊海靂, 趙靜. 基于Voronoi圖的無線傳感器網絡覆蓋算法研究[J]. 信息通信, 2015(7):28-31.

YANG H L, ZHAO J. Research of coverage algorithm with Voronoi diagram for wireless sensor network [J]. Information & Communications, 2015(7):28-31.

[3] 王成, 樊建席, 王仁喜, 等. 基于Voronoi圖的無線傳感器網絡K覆蓋算法[J]. 計算機工程, 2012, 38(4):84-87.

WANG C, FAN J X, WANG R X, et al. K coverage algorithm in wireless sensor network based on Voronoi diagram[J]. Computer Engineering, 2012, 38(4):84-87.

[4] 丁旭, 吳曉蓓, 黃成. 基于改進粒子群算法和特征點集的無線傳感器網絡覆蓋問題研究[J]. 電子學報, 2016, 44(4): 967-973.

DING X, WU X P, HUANG C. Area coverage problem based on improved PSO algorithm and feature point set in wireless sensor networks[J]. Acta Electronica Sinica, 2016, 44(4) : 967-973.

[5] 孫澤宇, 伍衛國, 王換招, 等. 無線傳感器網絡基于參數可調增強型覆蓋控制算法[J]. 電子學報, 2015, 43 (3):466-474.

SUN Z Y, WU W G, WANG H Z, et al. An enhanced coverage control algorithm for wireless sensor networks based on adjustable parameters[J]. Acta Electronica Sinica, 2015, 43 (3): 466-474.

[6] 劉志強, 沈廼桐, 毛強, 等. 無線傳感器網絡動態覆蓋的CVT算法[J]. 傳感器與微系統, 2015(6):115-118.

LIU Z Q, SHEN N T, MAO Q, et al. A dynamic coverage algorithm for wireless sensor networks based on CVT[J]. Transducer and Microsystem Technologies, 2015(6):115-118.

[7] 高潔, 吳延紅, 白建俠, 等. 無線傳感器網絡最小覆蓋能量優化算法[J]. 傳感技術學報, 2016, 29(9):1435-1440.

GAO J, WU Y H, BAI J X, et al. The minimum coverage energy optimization algorithms in wireless sensor network[J]. Chinese Journal of Sensors And Actuators, 2016, 29(9):1435-1440.

[8] LIU X Y, WU K L, ZHU Y, et al. Mobility increases the surface coverage of distributed sensor networks[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2013, 57(11):2348-2363.

[9] TAN L, CHENG Y C, YANG M H, et al. Priority coverage algorithm and performance simulation for node deployment in directional sensor networks[J]. Sensor Letters, 2014, 12(2): 275-280.

[10] 魯曉波, 阮福, 王立中. 無線傳感器網絡覆蓋優化策略[J]. 內蒙古師大學報(自然漢文版), 2016, 45(4):480-483.

LU X B, RUAN F, WANG L Z. Coverage optimization strategy of wireless sensor networks based on improved artificial fish swarm algorithm[J]. Journal of Inner Mongolia Normal University (Natural Science Edition), 2016, 45(4):480-483.

[11] 王興偉, 蔡凌, 黃敏, 等. 基于空間鑲嵌的三維無線傳感器網絡覆蓋機制[J]. 小型微型計算機系統, 2014, 35(3): 433-436.

WANG X W, CAI L, HUANG M, et al. Spatial tessellation basedcoverage scheme for 3D wireless sensor network[J]. Journal of Chinese Computer Systems, 2014, 35(3):433-436.

[12] MINI S, UDGATA S K, SABAT S L. Sensor deployment and scheduling for target coverage problem in wireless sensor networks[J]. IEEE Sensors Journal, 2014, 14(3):636-644.

[13] MAHBOUBI H, MOEZZI K, AGHDAM A G, et al. Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors[J]. IEEE Transactions on Industrial Informatics, 2013, 10(1):163-174.

[14] ZHANG Y, SUN X, WANG B. Efficient algorithm for-barrier coverage based on integer linear programming[J]. China Communications, 2016, 13(7):16-23.

[15] BAN D S, WEN J, JIANG J, et al. Constructing-barrier coverage in mobile wireless sensor networks[J]. Journal of Software, 2011, 22(9):2089-2103.

Polynomial time algorithm for solving-coverageproblem in wireless sensor networks

WANG Qi, XIAO Zheng’an, WANG Huaixing

School of Physics and Electromechanical Engineering, Hubei University of Education, Wuhan 430205, China

How to solve the-coverage problem, which was divided into worst-case and best-case, inside the two-dimensional target area in wireless sensor networks was explored, and a polynomial time algorithm for solving this problem was put forward. In this algorithm, a series of definitions and theorems were proposed based on the geometric graph of growing disks, and the-coverage problem was transformed into one of finding a series of adjacent borders. The simulation results show that the algorithm could compute the optimal-breach path and-support path in polynomial time, so as to avoid or select the network coverage reasonably.

wireless sensor network,-coverage problem, growing disk, adjacent border, polynomial time algorithm

TN918.91

A

10.11959/j.issn.1000?0801.2017287

2017?07?20；

2017?09?30

湖北省高等學校優秀中青年科技創新團隊計劃項目（No.T201417）

Hubei Provincial Department of Education Research Program (No.T201417)

王騏（1970?），男，博士，湖北第二師范學院物理與機電工程學院副教授，主要研究方向為無線傳感器網絡安全、嵌入式系統應用。

肖正安（1974?），男，湖北第二師范學院物理與機電工程學院講師，主要研究方向為圖像數字信號處理。

王懷興（1977?），男，湖北第二師范學院物理與機電工程學院副教授，主要研究方向為嵌入系統應用。