王騏,肖正安,王懷興
?
無線傳感器網絡中基于“?覆蓋問題”的多項式時間算法
王騏,肖正安,王懷興
(湖北第二師范學院物理與機電工程學院,湖北 武漢 430205)
無線傳感器網絡;?覆蓋問題;擴展圓盤;相鄰分界線;多項式時間算法
圖1 ?違反值和?支持值示意
圖2 大于的“2?違反”路徑
同理可得定理2。
圖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
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]。
圖5 k?違反的最大值
圖6 k?支持的最小值
對比圖5和圖6,可得到以下結論。
? 當傳感器節點數量相同時,?支持的最小值要遠大于?違反的最大值??梢宰C明,任何情況下,?支持的最小值均不會小于?違反的最大值。
本文分別闡述了最差和最佳?覆蓋問題,并基于擴展圓盤的幾何圖形提出了一系列的定義和定理,將?覆蓋問題轉化成了尋找相鄰分界線的問題,提出了解決此問題的多項式時間算法。
[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?),男,湖北第二師范學院物理與機電工程學院副教授,主要研究方向為嵌入系統應用。