  Device-free (DF) localization in WLANs has been introduced as a value-added
service that allows tracking 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 Spot as an accurate and efficient system for multi-entity
DF detection and tracking. Spot is based on 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.
This also helps in increasing the system accuracy. We design the energy
minimization function with the goal of being efficiently solved in mind. We
show that the designed function 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. Experimental
evaluation in two typical testbeds, with a side-by-side comparison with the
state-of-the-art, shows that Spot can achieve a multi-entity tracking accuracy
of less than 1.1m. This corresponds to at least 36% enhancement in median
distance error over the state-of-the-art DF localization systems, which can
only track a single entity. In addition, Spot can estimate the number of
entities correctly to within one difference error. This highlights that Spot
achieves its goals of having an accurate and efficient software-only DF
tracking solution of multiple entities in indoor environments.
