2nd International ICST Conference on Scalable Information Systems

Research Article

Wireless Sensor Network Aided Search and Rescue in Trails

Download76 downloads
  • @INPROCEEDINGS{10.4108/infoscale.2007.928,
        author={Peng Zhuang and Qingguo Wang and Yi Shang and Hongchi Shi and Bei  Hua},
        title={Wireless Sensor Network Aided Search and Rescue in Trails},
        proceedings={2nd International ICST Conference on Scalable Information Systems},
        keywords={Search and rescue Mobile agent Wireless sensor network Graphpartitioning Chinese postman problem},
  • Peng Zhuang
    Qingguo Wang
    Yi Shang
    Hongchi Shi
    Bei Hua
    Year: 2010
    Wireless Sensor Network Aided Search and Rescue in Trails
    DOI: 10.4108/infoscale.2007.928
Peng Zhuang1,*, Qingguo Wang1,*, Yi Shang1,*, Hongchi Shi1,*, Bei Hua2,*
  • 1: Department of Computer Science University of Missouri-Columbia
  • 2: Department of Computer Science and Technology University of Science and Technology of China
*Contact email: pz797@mizzou.edu, qwp4b@mizzou.edu, shangy@missouri.edu, shih@missouri.edu, bhua@ustc.edu.cn


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.