Track Your Foot Step:Anchor-free Indoor Localization based on Sensing Users'Foot Steps Chang Liu',Lei Xief,Chuyu Wangt,Jie Wu,Sanglu Lut iState Key Laboratory for Novel Software Technology,Nanjing University,P.R.China Department of Computer Information and Sciences,Temple University,USA Email:Tliuchang@dislab.nju.edu.cn,Ixie@nju.edu.cn,Twangcyu217@126.com,Tjiewu@temple.edu,Tsanglu@nju.edu.cn Abstract-Currently,conventional indoor localization schemes mainly leverage WiFi-based or Bluetooth-based schemes to locate the users in the indoor environment.These schemes require to deploy the infrastructures such as the WiFi APs and Bluetooth beacons in advance to assist indoor localization.This property hinders the indoor localization schemes in that they are not scalable to any other situations without these infrastructures.In this paper,we propose FootStep-Tracker,an anchor-free indoor localization scheme purely based on sensing the user's footsteps. By embedding the tiny Sensor Tag into the user's shoes,FootStep- Tracker is able to accurately perceive the user's moving trace, including the moving direction and distance,by leveraging the accelerometers and gyroscopes.Furthermore,by detecting the Fig.1.The SensorTag used in FootStep-Tracker.We embed two tags into user's activities such as ascending/descending the stairs and the insoles and use an Android phone to collect and process the sensor data. taking an elevator,FootStep-Tracker can effectively correlate due to the inappropriate placement of sensors.Second,they with the specified positions such as stairs and elevators,and conventionally estimate the moving distance by counting the further determine the exacted moving traces in the indoor map by leveraging the space constraints in the map.Realistic experiment foot steps,while assuming the user's step length remains to be results show that,FootStep-Tracker is able to achieve an average a constant value.This approach is not adaptive to the variation localization accuracy of Im for indoor localization,without any of user's moving activities,since the user may sometimes walk infrastructures having been deployed in advance. with small steps,and sometimes jog with large steps.Third, they still need to leverage the anchor nodes like the WiFi APs I.INTRODUCTION to help determine the exact position in the map.This increases Recently,indoor localization schemes have been widely their dependence on the surrounding infrastructure. used to support various applications such as context-aware In this paper,we propose FootStep-Tracker,an anchor-free or location-based services.Conventional localization schemes indoor localization scheme purely based on sensing the user's mainly leverage WiFi-based or Bluetooth-based schemes to footsteps.Our novel solution is based on the observation that locate the users in the indoor environment.These schemes the user's moving activities can be effectively inferred from primarily require the deployment of the infrastructures such his/her footsteps by leveraging the tiny sensors embedded in as WiFi APs and Bluetooth beacons in advance to assist shoes,such as accelerometers and gyroscopes.As is shown in indoor localization.However.for a number of indoor environ- Fig.1 (a),by embedding the tiny sensor like the SensorTag ments,it is impossible (or rather expensive)to deploy such [4]into the user's shoes,FootStep-Tracker is able to accu- a large number of devices as the localization infrastructures. rately perceive the user's moving traces,including the moving This property hinders the indoor localization schemes in that direction and distance,by leveraging the accelerometers and there are not scalable to any other situations without these gyroscopes.Fig.1(b)shows the FootStep-Tracker Android infrastructures.Therefore,it is essential to design a brand new app.Furthermore,by detecting the user's activities such asas- approach for indoor localization without any requirement for cending/descending the stairs and taking an elevator,FootStep- the infrastructure. Tracker can effectively correlate with the specified positions Recently,a few researchers have sought to leverage the such as the stairs and elevators,and further determine the devices with embedded sensors,such as smart phones [1- exact moving traces in the indoor map,by leveraging the space 3]and wearable bracelets,to position and track the indoor constraints in the map. environment users.However,the previous work in positioning There are several challenges building the indoor localization and tracking the users have had the following common limita-scheme purely based on sensing the user's footsteps.First. tions:First,they usually put devices like smart phones into the it is difficult to accurately estimate the user's horizontal step user's pant pocket and perceive the user's movements via the movements.Since the sensors are embedded in the shoes,they embedded sensors.They cannot accurately capture the user's actually capture the feet's movement in the air while the user movements,including the moving directions and distances, is moving,and thus the user's horizontal movement cannotTrack Your Foot Step: Anchor-free Indoor Localization based on Sensing Users’ Foot Steps Chang Liu† , Lei Xie† , Chuyu Wang† , Jie Wu‡ , Sanglu Lu† †State Key Laboratory for Novel Software Technology, Nanjing University, P.R. China ‡Department of Computer Information and Sciences, Temple University, USA Email: † liuchang@dislab.nju.edu.cn, † lxie@nju.edu.cn, †wangcyu217@126.com, ‡ jiewu@temple.edu, † sanglu@nju.edu.cn Abstract—Currently, conventional indoor localization schemes mainly leverage WiFi-based or Bluetooth-based schemes to locate the users in the indoor environment. These schemes require to deploy the infrastructures such as the WiFi APs and Bluetooth beacons in advance to assist indoor localization. This property hinders the indoor localization schemes in that they are not scalable to any other situations without these infrastructures. In this paper, we propose FootStep-Tracker, an anchor-free indoor localization scheme purely based on sensing the user’s footsteps. By embedding the tiny SensorTag into the user’s shoes, FootStep￾Tracker is able to accurately perceive the user’s moving trace, including the moving direction and distance, by leveraging the accelerometers and gyroscopes. Furthermore, by detecting the user’s activities such as ascending/descending the stairs and taking an elevator, FootStep-Tracker can effectively correlate with the specified positions such as stairs and elevators, and further determine the exacted moving traces in the indoor map by leveraging the space constraints in the map. Realistic experiment results show that, FootStep-Tracker is able to achieve an average localization accuracy of 1m for indoor localization, without any infrastructures having been deployed in advance. I. INTRODUCTION Recently, indoor localization schemes have been widely used to support various applications such as context-aware or location-based services. Conventional localization schemes mainly leverage WiFi-based or Bluetooth-based schemes to locate the users in the indoor environment. These schemes primarily require the deployment of the infrastructures such as WiFi APs and Bluetooth beacons in advance to assist indoor localization. However, for a number of indoor environ￾ments, it is impossible (or rather expensive) to deploy such a large number of devices as the localization infrastructures. This property hinders the indoor localization schemes in that there are not scalable to any other situations without these infrastructures. Therefore, it is essential to design a brand new approach for indoor localization without any requirement for the infrastructure. Recently, a few researchers have sought to leverage the devices with embedded sensors, such as smart phones [1– 3] and wearable bracelets, to position and track the indoor environment users. However, the previous work in positioning and tracking the users have had the following common limita￾tions: First, they usually put devices like smart phones into the user’s pant pocket and perceive the user’s movements via the embedded sensors. They cannot accurately capture the user’s movements, including the moving directions and distances, Fig. 1. The SensorTag used in FootStep-Tracker. We embed two tags into the insoles and use an Android phone to collect and process the sensor data. due to the inappropriate placement of sensors. Second, they conventionally estimate the moving distance by counting the foot steps, while assuming the user’s step length remains to be a constant value. This approach is not adaptive to the variation of user’s moving activities, since the user may sometimes walk with small steps, and sometimes jog with large steps. Third, they still need to leverage the anchor nodes like the WiFi APs to help determine the exact position in the map. This increases their dependence on the surrounding infrastructure. In this paper, we propose FootStep-Tracker, an anchor-free indoor localization scheme purely based on sensing the user’s footsteps. Our novel solution is based on the observation that the user’s moving activities can be effectively inferred from his/her footsteps by leveraging the tiny sensors embedded in shoes, such as accelerometers and gyroscopes. As is shown in Fig. 1 (a), by embedding the tiny sensor like the SensorTag [4] into the user’s shoes, FootStep-Tracker is able to accu￾rately perceive the user’s moving traces, including the moving direction and distance, by leveraging the accelerometers and gyroscopes. Fig. 1 (b) shows the FootStep-Tracker Android app. Furthermore, by detecting the user’s activities such as as￾cending/descending the stairs and taking an elevator, FootStep￾Tracker can effectively correlate with the specified positions such as the stairs and elevators, and further determine the exact moving traces in the indoor map, by leveraging the space constraints in the map. There are several challenges building the indoor localization scheme purely based on sensing the user’s footsteps. First, it is difficult to accurately estimate the user’s horizontal step movements. Since the sensors are embedded in the shoes, they actually capture the feet’s movement in the air while the user is moving, and thus the user’s horizontal movement cannot