無線傳感器網(wǎng)絡(luò)中基于“k?覆蓋問題”的多項式時間算法

王騏，肖正安，王懷興

?

無線傳感器網(wǎng)絡(luò)中基于“?覆蓋問題”的多項式時間算法

王騏，肖正安，王懷興

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

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

1 引言

2 基于UDG的幾何圖形

2.1 問題的描述

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

2.2 圓盤的擴展

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

同理可得定理2。

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

3.1 子區(qū)域及其分界線

圖3 子區(qū)域及其分界線

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

圖4 內(nèi)弧和外弧

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

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

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

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

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

for1 to

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

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

定義分界線bor

劃分bor為內(nèi)弧和外弧

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

定義分界線bor

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

for 每段分界線bor

switch（分界線類型）

casebor為邊界線的一部分

選取點poi∈bor

計算點poi的范圍內(nèi)傳感器節(jié)點數(shù)量

casebor為一段外弧

選取點poi∈bor

計算點poi的范圍內(nèi)傳感器節(jié)點數(shù)量，不包括poi所屬圓的中心節(jié)點

casebor為一段內(nèi)弧

選取點poi∈bor

計算點poi的范圍內(nèi)傳感器節(jié)點數(shù)量，包括poi所屬圓的中心節(jié)點

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

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

for 每個交點或切點poi

ifpoi為bor和bor的端點

setbor和bor為相鄰分界線

end

3.2 最差k?覆蓋問題

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

output: 布爾變量結(jié)果值

if()≥或() ≥

= 0

return

取消所有分界線的標(biāo)記

標(biāo)記/*起始于

list=

tree=

while（非空）

從鏈表頭選取分界線

從鏈表刪除分界線

for相鄰的每段分界線

if()

標(biāo)記

在樹上將作為的孩子

在鏈表尾增加

if被標(biāo)記

= 1

return

else

= 0

return

end

set/*設(shè)定搜索空間的上限值

set/*設(shè)定搜索空間的下限值

set/*設(shè)定迭代次數(shù)

for= 1 to

= (+)2

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

if= 1

=

else

end

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

3.3 最佳k?覆蓋問題

4 仿真結(jié)果

圖5 k?違反的最大值

圖6 k?支持的最小值

對比圖5和圖6，可得到以下結(jié)論。

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

5 結(jié)束語

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

[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圖的無線傳感器網(wǎng)絡(luò)覆蓋算法研究[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圖的無線傳感器網(wǎng)絡(luò)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] 丁旭, 吳曉蓓, 黃成. 基于改進粒子群算法和特征點集的無線傳感器網(wǎng)絡(luò)覆蓋問題研究[J]. 電子學(xué)報, 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] 孫澤宇, 伍衛(wèi)國, 王換招, 等. 無線傳感器網(wǎng)絡(luò)基于參數(shù)可調(diào)增強型覆蓋控制算法[J]. 電子學(xué)報, 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] 劉志強, 沈廼桐, 毛強, 等. 無線傳感器網(wǎng)絡(luò)動態(tài)覆蓋的CVT算法[J]. 傳感器與微系統(tǒng), 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] 高潔, 吳延紅, 白建俠, 等. 無線傳感器網(wǎng)絡(luò)最小覆蓋能量優(yōu)化算法[J]. 傳感技術(shù)學(xué)報, 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] 魯曉波, 阮福, 王立中. 無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化策略[J]. 內(nèi)蒙古師大學(xué)報(自然漢文版), 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] 王興偉, 蔡凌, 黃敏, 等. 基于空間鑲嵌的三維無線傳感器網(wǎng)絡(luò)覆蓋機制[J]. 小型微型計算機系統(tǒng), 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

湖北省高等學(xué)校優(yōu)秀中青年科技創(chuàng)新團隊計劃項目（No.T201417）

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

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

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

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