WarpMap: Accurate and Efficient Indoor Location by Dynamic Warping in Sequence-Type Radio-Map

Radio-map based method has been widely used for indoor location and navigation, but remaining key challenges are: 1) laborious efforts to calibrate a fine-grained radio-map, and 2) the locating result inaccuracy and not robust problems due to random signal strength (RSS) noises. An efficient way to overcome these problems is to collect RSS signatures along indoor paths and utilize sequence matching to enhance the location robustness. But, due to problems of indoor path combinational explosion, random RSS loss during movement, and moving speed disparity during online and offline phases, how to exploit sequence matching in radio-map remains difficult. This paper proposes WarpMap, an efficient sequence-type radio-map model and an accurate indoor location method by dynamic warping. Its distinct features include: 1) an undirected graph model (Trace-graph) for efficiently calibrating and storing sequence-type radio-map, which overcomes the path combinational explosion and RSS miss-of-detection problems; 2) an efficient sub-sequence dynamic time warping (SDTW) algorithm for accurate and efficient on-line locating. We show SDTW can tolerate random RSS disparities at discrete points and handle the moving speed differences in on-line and off-line phases. The impacts of different warping distance functions, RSS preprocessing techniques were also investigated. Extensive experiments in office environments verified the efficiency and accuracy of WarpMap, which can calibrated within ten minutes by one person for 1100 m² area and provides overall nearly 20% accuracy improvements than the state-of-the-art of radio-map method.