Optimal best-case and worst-case coverage for straight paths in ad hoc networks

被引：2

作者：

Hou, Yung-Tsung ^{[1
]}

机构：

[1] Natl Formosa Univ, Dept Informat Management, 64 Wunhua Rd, Huwaei Township 632, Yulin, Taiwan

来源：

JOURNAL OF INFORMATION & OPTIMIZATION SCIENCES | 2019年 / 40卷 / 06期

关键词：

Ad hoc network; Best case coverage; Worst case coverage; Straight path; WIRELESS SENSOR NETWORKS; DYNAMIC COVERAGE;

D O I：

10.1080/02522667.2018.1536389

中图分类号：

G25 [图书馆学、图书馆事业]; G35 [情报学、情报工作];

学科分类号：

1205 ; 120501 ;

摘要：

Given a set of network nodes and their locations, the best support path problem is to find a path that has the min-max distance to network nodes and the maximal breach path problem is to find a path that has the max-min distance to network nodes. This paper considers straight paths and proposes optimal algorithms identifying both the best support and the maximal breach straight paths. Our study provides a coverage measurement method for straight paths in an ad hoc network. Based on computational geometry and graph theory, we propose plane-sweep algorithms to find the optimal straight paths for both the best-case and worst-case coverage problems in polynomial time. Mathematical analysis and simulations are used to prove the optimality of proposed algorithms.

引用

页码：1317 / 1335

页数：19

共 25 条

[1] Markov Decision Processes With Applications in Wireless Sensor Networks: A Survey
Abu Alsheikh, Mohammad
Dinh Thai Hoang
Niyato, Dusit
Tan, Hwee-Pink
Lin, Shaowei
[J]. IEEE COMMUNICATIONS SURVEYS AND TUTORIALS, 2015, 17 (03): : 1239 - 1267
[2] [Anonymous], 2002, P 1 ACM INT WORKSH W, DOI DOI 10.1145/570738.570744
[3] Brauer W., 2012, ALGORITHMS COMBINATO
[4] Improving wireless sensor network lifetime through power aware organization
Cardei, M
Du, DZ
[J]. WIRELESS NETWORKS, 2005, 11 (03) : 333 - 340
[5] Cardei M., 2004, Handbook of Sensor Networks
[6] Cormen T. H., 2009, Introduction to algorithms, VThird
[7] Daponte P., 2012, P ENV EN STRUCT MON, P576
[8] Mobility and Intruder Prior Information Improving the Barrier Coverage of Sparse Sensor Networks
He, Shibo
Chen, Jiming
Li, Xu
Shen, Xuemin
Sun, Youxian
[J]. IEEE TRANSACTIONS ON MOBILE COMPUTING, 2014, 13 (06) : 1268 - 1282
[9] An optimal new-node placement to enhance the coverage of wireless sensor networks
Hou, Yung-Tsung
Chen, Chia-Mei
Jeng, Bingchiang
[J]. WIRELESS NETWORKS, 2010, 16 (04) : 1033 - 1043
[10] The coverage problem in a wireless sensor network
Huang, CF
Tseng, YC
[J]. MOBILE NETWORKS & APPLICATIONS, 2005, 10 (04) : 519 - 528

← 1 2 3 →