ACE: An accurate and efficient multi-entity device-free WLAN localization system

Device-free (DF) localization in WLANs has been introduced as a value-added service that allows tracking of indoor entities that do not carry any devices. Previous work in DF WLAN localization focused on the tracking of a single entity due to the intractability of the multi-entity tracking problem whose complexity grows exponentially with the number of humans being tracked. In this paper, we introduce ACE: a system that uses a probabilistic energy-minimization framework that combines a conditional random field with a Markov model to capture the temporal and spatial relations between the entities' poses. A novel cross-calibration technique is introduced to reduce the calibration overhead of multiple entities to linear, regardless of the number of humans being tracked. We design an efficient energy-minimization function that can be mapped to a binary graph-cut problem whose solution has a linear complexity on average and a third order polynomial in the worst case. We further employ clustering on the estimated location candidates to reduce outliers and obtain more accurate tracking in the continuous space. Experimental evaluation in two typical testbeds, with a side-by-side comparison with the state-of-the-art, shows that ACE can achieve a multi-entity tracking accuracy of less than 1.3 m. This corresponds to at least 11.8 percent, and up to 33 percent, enhancement in median distance error over the state-of-the-art DF localization systems. In addition, ACE can estimate the number of entities correctly to within one difference error for 100 percent of the time. This highlights that ACE achieves its goals of having an accurate and efficient multi-entity indoors localization.