Optimal best-case and worst-case coverage for straight paths in ad hoc networks
- Resource Type
- Article
- Authors
- Hou, Yung-Tsung
- Source
- Journal of Information & Optimization Sciences; August 2019, Vol. 40 Issue: 6 p1317-1335, 19p
- Subject
- Language
- ISSN
- 02522667
AbstractGiven 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.