be directly derived from the collected sensor data.To address position.[3,11-17].Leppakoski et al.[11]proposed an IMU this challenge,we leverage the gyroscope to measure the angle sensors,WLAN signals and indoor map combined localization between the foot's direction of movement and the ground,and system.By using extended Kalman filter to combine the sensor leverage the accelerometer to measure the actual movement with WLAN signal and particle filter to combine the inertial of the foot.We then build a geometric model to estimate data with map information,the diverse data are fused well the horizontal movement.Second,it is difficult to accurately to improve the pedestrian dead reckoning.Vidal et al.[12] estimate the user's moving direction during the movement. present an indoor pedestrian tracking system with the sensor While tracking the user's foot steps,the angle variation of the on the smart phone.Combined with the dead-reckoning and foot steps cannot be directly correlated to the user's moving the gait detecting approach,and aided by the indoor signatures direction.To address this challenge,we build a geometric such as corners,the system have an acceptable location accu- model to depict the relationship between the angle variation racy.Wang et al.[13]present UnLoc,which leverage the iden- of the foot steps and the moving direction,and further derive tifiable signal signatures of indoor environment which can be the user's moving direction from the measurements from the captured by the sensor or WiFi to improve the dead-reckoning embedded sensors.Third,to realize the indoor localization, method.With UnLoc,the localization system converge speed it is essential to determine the exact moving traces in the can be effectively improved.Fourati et al.[15]proposed an indoor map.To address this challenge,we use activity sensing Complementary Filter algorithm to process the sensor data, to effectively figure out the reference positions,such as the and combined with Zero Velocity Update (ZVU).the system elevators and stairs,and further leverage the space constraints can locate the user with high accuracy.Rai el al.developed in the indoor map to filter out those infeasible candidate traces, ZEE [3],which leverages the smart phone built-in sensors, so as to fix the moving traces in the indoor map. tracking the user when he travels in an indoor environment, We advance the state of the art on positioning and tracking and scanning with WiFi signal simultaneously.By combining the users from three perspectives.First,we propose an anchor-the sensors and WiFi,ZEE uses crowdsourcing to locate the free indoor localization purely based on sensing the user's user,achieving a meter-level location accuracy. footsteps,without the support of any infrastructure.Second, Different from the previous work,in this paper,we pro- we propose efficient solutions to accurately estimate the mov- pose an anchor-free indoor localization system.By sensing ing direction and distance,by only leveraging the low-cost the user's foot step and utilizing the reference position and inertial sensors like accelerometer and gyroscope.Third,we constraint of the indoor map,FootStep-Tracker track the user's leverage activity sensing to effectively figure out the reference location without any deployment of anchor nodes. positions during the process of tracking the user,so as to further determine the exact moving traces in the indoor map. III.SYSTEM OVERVIEW II.RELATED WORK In our system,called FootStep-Tracker,we focus on how to A.Infrastructure based Indoor Localization track the user's position based on the low-cost inertial sensors Infrastructure based indoor localization schemes primarily embedded inside the shoes,according to a given indoor map. Fig.2 shows the framework of FootStep-Tracker.First,the use wireless signal,such as RF signal and WiFi signal,to lo- cate the users or objects in the indoor environment.Several lo- Activity Classifier is designed to classify the user's activities cation algorithms such as Fingerprint[6]and LANDMARC[7] into two activity groups,i.e.,walking and reference activities such as ascending/descending the stairs,and the elevator have been proposed and widely accepted in the academic area.Yang et al.[9]proposed Tagoram,an object localization ascending/descending,according to the raw sensor data of system based on COTS RFID reader and tags.By proposed gyroscope and accelerometer.In regard to the walking activity, Differential Augmented Hologram (DAH),Tagoram can re- we measure the moving distance based on the Step Segmen- tation and Step Length Estimator,and measure the moving cover the tag's moving trajectories and achieves a milimeter location accuracy in tracking mobile RFID tags.Xiao et al. direction based on Moving Direction Estimator.According to [10]proposed Nomloc which dynamically adjusts the WLAN the moving distance and moving direction,we reconstruct the network topology by nomadic WiFi AP to address the per- user's moving trace relative to the starting point.Meanwhile, formance variance problem.By the proposed space partition it is possible to derive the reference positions according based algorithm and fine-grained channel state information, to the activity sensing results from the Activity Classifier. Nomloc can effectively mitigate the multipath and NLOS For example,the reference positions can be the elevators effects. if the activity of elevator ascending/descending is detected. Furthermore,by leveraging the space constraints in the indoor B.Infrastructure-free based Indoor Localization map to filter out those infeasible candidate traces,our solution State-of-the-art infrastructure-free based indoor localization could finally determine the user's trace in the indoor map schemes,especially for pedestrian navigation work track the The components of FootStep-Tracker are as follows: user by detecting the user's movement with the IMU sensors, 1)Activity Classifier.It extracts corresponding features and dead-reckoning is the most popular scheme which esti- from the inertial sensor data of human movement,then mate the object's current position by it's previous determined it estimates the user's current activities via the classifica-be directly derived from the collected sensor data. To address this challenge, we leverage the gyroscope to measure the angle between the foot’s direction of movement and the ground, and leverage the accelerometer to measure the actual movement of the foot. We then build a geometric model to estimate the horizontal movement. Second, it is difficult to accurately estimate the user’s moving direction during the movement. While tracking the user’s foot steps, the angle variation of the foot steps cannot be directly correlated to the user’s moving direction. To address this challenge, we build a geometric model to depict the relationship between the angle variation of the foot steps and the moving direction, and further derive the user’s moving direction from the measurements from the embedded sensors. Third, to realize the indoor localization, it is essential to determine the exact moving traces in the indoor map. To address this challenge, we use activity sensing to effectively figure out the reference positions, such as the elevators and stairs, and further leverage the space constraints in the indoor map to filter out those infeasible candidate traces, so as to fix the moving traces in the indoor map. We advance the state of the art on positioning and tracking the users from three perspectives. First, we propose an anchor￾free indoor localization purely based on sensing the user’s footsteps, without the support of any infrastructure. Second, we propose efficient solutions to accurately estimate the mov￾ing direction and distance, by only leveraging the low-cost inertial sensors like accelerometer and gyroscope. Third, we leverage activity sensing to effectively figure out the reference positions during the process of tracking the user, so as to further determine the exact moving traces in the indoor map. II. RELATED WORK A. Infrastructure based Indoor Localization Infrastructure based indoor localization schemes primarily use wireless signal, such as RF signal and WiFi signal, to lo￾cate the users or objects in the indoor environment. Several lo￾cation algorithms such as Fingerprint[6] and LANDMARC[7] have been proposed and widely accepted in the academic area. Yang et al. [9] proposed Tagoram, an object localization system based on COTS RFID reader and tags. By proposed Differential Augmented Hologram (DAH), Tagoram can re￾cover the tag’s moving trajectories and achieves a milimeter location accuracy in tracking mobile RFID tags. Xiao et al. [10] proposed Nomloc which dynamically adjusts the WLAN network topology by nomadic WiFi AP to address the per￾formance variance problem. By the proposed space partition based algorithm and fine-grained channel state information, Nomloc can effectively mitigate the multipath and NLOS effects. B. Infrastructure-free based Indoor Localization State-of-the-art infrastructure-free based indoor localization schemes, especially for pedestrian navigation work track the user by detecting the user’s movement with the IMU sensors, and dead-reckoning is the most popular scheme which esti￾mate the object’s current position by it’s previous determined position.[3, 11–17]. Leppakoski et al. [11] proposed an IMU ¨ sensors, WLAN signals and indoor map combined localization system. By using extended Kalman filter to combine the sensor with WLAN signal and particle filter to combine the inertial data with map information, the diverse data are fused well to improve the pedestrian dead reckoning. Vidal et al. [12] present an indoor pedestrian tracking system with the sensor on the smart phone. Combined with the dead-reckoning and the gait detecting approach, and aided by the indoor signatures such as corners, the system have an acceptable location accu￾racy. Wang et al. [13] present UnLoc, which leverage the iden￾tifiable signal signatures of indoor environment which can be captured by the sensor or WiFi to improve the dead-reckoning method. With UnLoc, the localization system converge speed can be effectively improved. Fourati et al. [15] proposed an Complementary Filter algorithm to process the sensor data, and combined with Zero Velocity Update (ZVU), the system can locate the user with high accuracy. Rai el al. developed ZEE [3], which leverages the smart phone built-in sensors, tracking the user when he travels in an indoor environment, and scanning with WiFi signal simultaneously. By combining the sensors and WiFi, ZEE uses crowdsourcing to locate the user, achieving a meter-level location accuracy. Different from the previous work, in this paper, we pro￾pose an anchor-free indoor localization system. By sensing the user’s foot step and utilizing the reference position and constraint of the indoor map, FootStep-Tracker track the user’s location without any deployment of anchor nodes. III. SYSTEM OVERVIEW In our system, called FootStep-Tracker, we focus on how to track the user’s position based on the low-cost inertial sensors embedded inside the shoes, according to a given indoor map. Fig.2 shows the framework of FootStep-Tracker. First, the Activity Classifier is designed to classify the user’s activities into two activity groups, i.e., walking and reference activities such as ascending/descending the stairs, and the elevator ascending/descending, according to the raw sensor data of gyroscope and accelerometer. In regard to the walking activity, we measure the moving distance based on the Step Segmen￾tation and Step Length Estimator, and measure the moving direction based on Moving Direction Estimator. According to the moving distance and moving direction, we reconstruct the user’s moving trace relative to the starting point. Meanwhile, it is possible to derive the reference positions according to the activity sensing results from the Activity Classifier. For example, the reference positions can be the elevators if the activity of elevator ascending/descending is detected. Furthermore, by leveraging the space constraints in the indoor map to filter out those infeasible candidate traces, our solution could finally determine the user’s trace in the indoor map. The components of FootStep-Tracker are as follows: 1) Activity Classifier. It extracts corresponding features from the inertial sensor data of human movement, then it estimates the user’s current activities via the classifica-