Optimal best-case and worst-case coverage for straight paths in ad hoc networks. Issue 6 (18th August 2019)

• Record Type: Journal Article
• Authors: Hou, Yung-Tsung
• Is Part Of: Journal of information & optimization sciences. Volume 40:Issue 6(2019)
• Page Start: 1317
• Page End: 1335
• Publication Date: 2019-08-18
• Subjects: 68R10; Ad hoc network -- Best-case coverage -- Worst-case coverage -- Straight path; Electronic data processing -- Periodicals; Information science -- Periodicals; Mathematical optimization -- Periodicals; 519.6
• DOI: 10.1080/02522667.2018.1536389
• Languages: English
• ISSNs: 0252-2667

Abstract

Abstract: 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.