Wireless Sensor Network Aided Search and Rescue in Trails

In recent years, wireless sensor networks have been used in applications of data gathering and target localization across large geographical areas. In this paper, we study the issues involved in applying wireless sensor networks to search and rescue of lost hikers in trails and focus on the optimal placement of sensors and access points such that the cost of search and rescue is minimized. Particularly, we address two problems: a) how to identify the lost hiker position as accurately as possible, i.e., obtain a small trail segments containing the lost hiker; and (b) how to search efficiently in trail segments for different trail topologies and search agent capabilities. For the optimal access point deployment problem, we propose theoretical models that consider both efficiency and accuracy criteria and present analytical results for simpler trail topologies. For complicated graph topologies, we develop efficient heuristic algorithms with various heuristics. After access point deployment is decided, the actual cost of search in individual trail segment can be computed. We analyze four different types of search and rescue agents, present algorithms to find the optimal search pathes for each one of them, and compute their search costs. The algorithms are developed based on solving Chinese Postman problems. Finally, we present extensive experimental results to examine the accuracy of the mathematical models and compare the performances of different methods. A heuristic method, divide-merge, is shown to outperform all others and finds near-optimal solutions.