Information Technology Reference
In-Depth Information
The random variables
ρ
i
for all
i
are mutually independent and normally
distributed. The true mean of the random variable
ρ
i
is denoted as
r
i
.
The Euclidean distance is calculated using the following equation:
Z
=
N
r
i
)
2
2
=
N
q
2
2
(
ρ
i
−
(3)
i−
1
i−
1
It is important to note that Euclidean distance does not imply physical dis-
tance. It is simply a means of selecting the best estimate from the average and
sample RSS vectors.
In order to implement the location fingerprinting approach several param-
eters are needed, namely the number of access points in the network, the grid
spacing, the path loss exponent (effects of obstacles and distance) and the stan-
dard deviation of the received signal strength.
Microsoft Research and the Empirical Method.
Microsoft Research has
performed extensive research on empirical positioning methodologies [1, 13]. Re-
searchers tested their algorithms using the 802.11 network in the 10,500 square
foot Microsoft Research building. They termed their methodology Nearest Neigh-
bor(s) in Signal Space (NNSS).
The first stage involved collecting signal strengths at known locations through-
out the experiment area. Microsoft researchers chose seventy points at which to
record signal strength measurements. Given that signal strength can vary rela-
tive to orientation [1], measurements were taken from four different orientations
at each point. At each position and orientation twenty different readings were
recorded to average out any anomalies. All of this information was stored as
tuples in the form
< x,y,d,ss,snr >
where
x, y
represent position coordinates,
d
represents orientation,
ss
signal strength and
snr
signal-noise-ratio.
The location of a wireless device is determined by comparing the device's
signal strengths to each access point to the database of signal strengths and
orientations at the seventy different stored locations. The known tuple (nearest-
neighbor) that best matches the device's signal strength returns its associated
location. Using this method the mean error (50
th
percentile) was shown to be
approximately 3m.
The k-nearest neighbor algorithm was applied to this model to improve accu-
racy. The algorithm involves defining a distance in radio space
3
[5] and selecting
the
k
nearest neighbors from the training set to the unknown point. The po-
sitions of the
k
neighbors are then used to determine location. A user may be
nearly an equal distance between two or more known locations, but in a near-
est neighbor approach the location that is closer is chosen. With a k-nearest
neighbor approach, the relative closeness to known signal strength positions is
factored in. Using this additional logic, a slight improvement of 9% on the mean
error was obtained. The improvement using the k-nearest neighbor approach is
3
Radio space is defined to have 5 dimensions as it accounts for position in space and
orientation.
Search WWH ::
Custom Search