owlps/doc/owlps-positionerd.t2t

586 lines
26 KiB
Plaintext
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Owl Positioning System Positioner
OwlPS {{OWLPS_VERSION}}
October 2013
%%%
% Man title & section:
%!postproc(man): "^(\.TH.*) 1 " ".TH owlps-positionerd 1 "
% Fix .TH, add NAME section and TABLE OF CONTENTS title:
%!postproc(man): "^(\.TH.*)$" "\1 OwlPS\ User\ Manual\n.SH NAME\nowlps-positionerd - compute results from OwlPS positioning requests"
% Man "links":
%!preproc(man): "(owlps)\.t2t" "//\1//(7)"
%!preproc(man): "(owlps-architecture)\.t2t" "//\1//(7)"
%!preproc(man): "(owlps-deployment)\.t2t" "//\1//(7)"
%!preproc(man): "(owlps-[^ ]*)\.t2t" "//\1//(1)"
%!preproc(man): "(owlps[^ ]*\.h)" "//\1//(3)"
%%%
= Synopsis =
**owlps-positionerd** [ options ]
= Description =
**OwlPS Positioner** reads aggregated requests from the aggregation
server (OwlPS Aggregator, see owlps-aggregatord.t2t) and computes the
positioning results. It can either receive requests directly from the
aggregation server through a UDP socket, or read a CSV aggregation file
offline. It can output the results in several ways, the three main ways
being through a UDP socket, by writing a CSV file, and on the standard
output (see “**Output options**” below).
Several positioning algorithms are implemented, based on signal strength
location fingerprinting (or cartography-based), on trilateration, or
both:
- Nearest-neighbour in Signal Strength (NSS), a simple cartography-based
algorithm inspired by the RADAR positioning system. In most cases,
this algorithm is the most precise, and one can use the
autocalibration mechanism to avoid building manually the database of
reference points (see section “**Autocalibration**”).
- Trilateration using a static propagation formula adapted to indoor
environments. This is a very basic and inaccurate technique.
- Trilateration using the FBCM (Friis-Based Calibrated Model) algorithm,
which adapts the propagation formula to better match the deployment
area's characteristics, thanks to a minimal calibration.
- Basic FRBHM (FBCM and Reference-Based Hybrid Model), that is a
combination of the NSS and the FBCM which allows to adapt dynamically
the propagation formula to the characteristics of the room where the
mobile terminal is supposed to be.
These algorithms are presented in detail in the section “**Algorithms**”
below.
= Options =
== General options ==
: **-h**, **--help**
Print help message and exit.
: **-V**, **--version**
Print version information and exit.
: **-f** //file//, **--config-file** //file//
Use an alternative configuration file.
: **-v**, **--verbose**
Turn on verbose mode.
== Data input options ==
: **--data-input.cp-medium** //medium//
Medium from which capture points are read. You can specify this option
more than once. Currently, only “CSV” is allowed.
: **--data-input.cp-csv-file** //file//
CSV file to use for capture points input (when
**data-input.cp-medium** = “CSV”).
: **--data-input.mobile-medium** //medium//
Medium from which mobiles are read. You can specify this option more
than once. Currently, only “CSV” is allowed.
: **--data-input.mobile-csv-file** //file//
CSV file to use for mobiles input (when **data-input.mobile-medium** =
“CSV”).
: **--data-input.topology-medium** //medium//
Medium from which topology (buildings, areas and waypoints) is read.
You can specify this option more than once. Currently, only “CSV” is
allowed.
: **--data-input.areas-csv-file** //file//
CSV file to use for topology input (when
**data-input.topology-medium** = “CSV”).
: **--data-input.waypoints-csv-file** //file//
CSV file to use for waypoints input (when
**data-input.topology-medium** = “CSV”).
: **--data-input.reference-points-medium** //medium//
Medium from which reference points are read. You can specify this
option more than once. Currently, only “CSV” is allowed.
: **--data-input.reference-points-csv-file** //file//
CSV file to use for reference points input (when
**data-input.reference-points-medium** = “CSV”).
== Input options ==
: **-I** //medium//, **--input.medium** //medium//
Medium from which requests are read. Allowed: “CSV”, “UDP”.
: **--input.csv-file** //file//
CSV file to use for input (when **input.medium** = “CSV”).
: **--input.udp-port** //port//
Port on which the UDP socket listens (when **input.medium** = “UDP”).
Default: 9902.
== Log options ==
: **-L** //medium//, **--log.medium** //medium//
Medium to which the requests will be logged. You can specify this
option more than once. Allowed: “none”, “CSV”. The “none” value
completely disables logging.
: **--log.csv-file** //file//
CSV file to use for logging (when **log.medium** = “CSV”).
== Positioning options ==
: **-a** //algorithm//, **--positioning.algorithm** //algorithm//
Algorithms used to compute positions (see section “**Positioning**
**algorithms**” below). You can specify this option more than once
(but at least once). Allowed: “Real”, “FBCM”, “FRBHMBasic”,
“InterlinkNetworks”, “NSS”.
: **--positioning.accept-new-mobiles** < //true// | //false// >
When receiving requests, add unknown mobiles (mobiles which are not
declared in the mobiles' configuration file) to the mobiles' list.
Default: false.
: **--positioning.accept-new-cps** < //true// | //false// >
When receiving requests, add unknown capture points (those which are
not declared in the configuration file) to the list of capture points
(default is false, for security purposes).
: **--positioning.update-cp-coordinates-online** < //true// | //false// >
Allow capture points' coordinates to be updated when a calibration
request with new coordinates is received from the capture point
(default is false, for security purposes).
: **--positioning.area-start** //3d_point//
Coordinates of the first point of the deployment area; this is used to
delimit the area in which the MinMax trilateration method tests points
and in which the reference points are generated, if the corresponding
options are activated (string format: “X;Y;Z”).
: **--positioning.area-stop** //3d_point//
Coordinates of the last point of the deployment area (string format:
“X;Y;Z”).
: **--positioning.smallest-ss** //ss_level//
Smallest possible value for a received signal strength, in dBm.
Default: -99.
: **--positioning.ss-similarity** //algorithm//
Algorithm used to calculate the similarity, in the signal strength
space, between two measurements (see section “**Similarity**
**algorithms**” below). Allowed: “mean”, “interval”, “interval2”.
Default: “mean”.
: **--positioning.generate-reference-points** //value// arg (=false)
Generate reference points from the (auto)calibration requests
received. Can be “false” to disable reference point generation, “mesh”
to generate reference points regularly according to the meshing grain
specified and the positioning area defined, “line” to generate
reference points regularly according to a straight path (cf. options
**generated-line-path** and **generated-line-step**), “list” to
generate reference points from a list (cf. option
**generated-points-list**), or a combination of the three previous
options (separated by any character) to generate points in several
ways. Default: false.
: **--positioning.generate-multi-packet-reference-points** < //true// | //false// >
Generate several packets per reference point by trying to match the
packets in the real requests. If false, the SS values of the requests
are averaged and only one packet is generated. Default: true.
: **--positioning.generated-meshing-grain-x** //distance//
When **generate-reference-points** includes “mesh”, this distance (in
metres) will separate each point to the next in X. Default: 0.5.
: **--positioning.generated-meshing-grain-y** //distance//
When **generate-reference-points** includes “mesh”, this distance (in
metres) will separate each point to the next in Y. Default: 0.5.
: **--positioning.generated-meshing-grain-z** //floors//
When **generate-reference-points** includes “mesh”, this parameter
represents the number of the floor. Currently, each increment of Y is
a new floor (full 3-D coordinates are not supported yet), so it should
be left to 1 in most cases. Default: 1.
: **--positioning.generated-line-path** //path//
Path of reference points to generate, if **generate-reference-points**
includes “line”; the reference points are generated in straight lines
between the given points, and one of the points must be the
coordinates of a capture point (string format:
“(X1;Y1;Z1);(X2;Y2;Z2);...” or “X1;Y1;Z1;X2;Y2;Z2;...”).
: **--positioning.generated-line-step** //distance//
When **generate-reference-points** includes “line”, two generated
points will be separated approximately by this distance (in metres).
Default: 0.5.
: **--positioning.generated-points-list** //list//
List of reference points to generate, if **generate-reference-points**
includes “list” (string format: “(X1;Y1;Z1);(X2;Y2;Z2);...” or
“X1;Y1;Z1;X2;Y2;Z2;...”).
: **--positioning.accept-new-calibration-requests** < //true// | //false// >
Add the calibration requests received during run-time to the
calibration requests' list; this is required for the self-calibration.
If unactivated, the calibration requests are handled as positioning
requests (default is unactivated, for security purposes).
: **--positioning.calibration-requests-timeout** //timeout//
Maximum age of a calibration request before to delete it (0 =
unlimited). See also the **replay** option. Default: 0.
: **--positioning.unique-calibration-requests** < //true// | //false// >
Always delete existing former calibration requests when receiving a
new calibration request for an existing reference point. Default:
true.
: **--positioning.position-calibration-requests** < //true// | //false// >
When **accept-new-calibration-requests** is activated, allow the
calibration requests to be positioned as normal requests. The default
is false, i.e. to add them to the calibration requests' list without
position them.
: **--positioning.nss.average-reference-points** < //true// | //false// >
With the NSS algorithm, for a given positioning request, average all
the calibration requests associated with a reference point before to
compute the SS similarity. The default is false, i.e the positioning
request is compared directly to each calibration request.
: **--positioning.nss.ignore-cp-reference-points** < //true// | //false// >
With the NSS algorithm, try to avoid selecting the reference points
which are coordinates of a capture point. Default: false.
: **--positioning.filter.max-speed** //max-speed//
Maximal speed at which the mobile terminal can move, in km/h. This
option also controls the activation of the filter. Default: 0
(disabled).
: **--positioning.filter.cp-reset-distance** //distance//
With this option set to a positive number, the maximum speed is
temporarily set to //max-speed-cp// instead of //max-speed// (see
these options) when the mobile terminal is found to be close enough to
a capture point. This option determines this “close enough” distance,
in metres.
This is useful in deployments where the system is much more accurate
when the mobile is close to a capture point, such as underground
mining tunnels; in such environments, 15 m appears to be a reasonable
value to start experimenting.
Default: 0 (disabled, i.e. never change the speed even when the
terminal is close to a capture point).
: **--positioning.filter.max-speed-cp** //max-speed-cp//
Maximal (virtual) speed at which the mobiles can move when they are
within //cp-reset-distance// (see this option), in km/h.
//max-speed// × 10 seems to be a good value to start experimenting.
Default: 0, which corresponds to an unlimited speed (i.e. filtering
will be completely disabled when the mobile is found to be close to a
capture point).
== Output options ==
: **--output.2d-error** < //true// | //false// >
Compute the distance error in two dimensions instead of three
dimensions. Default: false.
: **-O** //medium//, **--output.medium** //medium//
Medium to which the results will be written. You can specify this
option more than once. Allowed: “Terminal”, “CSV”, “UDP”, “TCPEvAAL”
(EvAAL 2012 format). If this option is absent, the results are printed
on the terminal.
: **--output.csv-file** //file//
CSV file to use for output (when **output.medium** = “CSV”).
: **--output.udp-host** //host//
Name or IP address of the host to which the UDP data is sent (when
**output.medium** = “UDP”).
: **--output.udp-port** //port//
Port on which the UDP data is sent (when **output.medium** = “UDP”).
Default: 9910.
: **--output.tcpevaal-host** //ip_address//
IP address (host name will not work!) of the host to which the TCP
data is sent (when **output.medium** = “TCPEvAAL”). Default:
127.0.0.1.
: **--output.tcpevaal-port** //port//
Port on which the TCP data is sent (when **output.medium** =
“TCPEvAAL”). Default: 4444.
== Miscellaneous options ==
: **--flush-output-files** < //true// | //false// >
Flush output text files after each line. Default: true.
: **--replay** < //true// | //false// >
“Replay” mode. With this option enabled, the current time is the
transmission timestamp of the most recent request; you will want to
enable this when reading inputs (requests) offline to replay
scenarios, if time-related options are enabled (e.g.
**positioning.calibration-requests-timeout**). To be useful, this
option requires the listeners' clocks to be synchronised. Default:
false.
= Configuration hints =
== Device management ==
The administrator can provide a list of known capture points and mobile
terminals, along with some relevant information (cf. “**Data input**
**options**” above). By default, only these will be taken into account
by the system, and unknown equipments will be ignored. If unknown mobile
terminals are to be located, one should enable the
**positioning.accept-new-mobiles** option.
If new capture points can appear while the system is running, the
**positioning.accept-new-cps** option can be enabled. However, this can
have security consequences as the program will accept measurements
(potentially fake) from any device. That being said, this problem exists
in any case since turning this option off does not protect against MAC
address spoofing.
In a deployment where the capture points are potentially mobile, they
can be allowed to send their updated coordinates to the system thanks to
the **positioning.update-cp-coordinates-online** option. This is
relevant only when the autocalibration is enabled (see below). Once
again, the administrator should consider the potential security issues
before to enable this option.
== Autocalibration ==
In order to enable the self-calibration mechanism, one has to set at
least the following options:
- **positioning.generate-reference-points**, to one or more modes of
generating points;
- one or several of the options **positioning.generated-***, depending
on the selected mode(s);
- **positioning.accept-new-calibration-requests** to true.
For more information, please refer to these options' descriptions and to
the section “**Autocalibration algorithms**” below.
= Algorithms =
== Positioning algorithms ==
: **NSS**
RADAR is a system developed by P. Bahl and V.N. Padmanabhan of
Microsoft Research, published for the first time in “RADAR: An
in-building RF-based user location and tracking system”, INFOCOM (2),
2000. It is certainly the best known (and maybe the first) Wi-Fi-based
positioning system that uses location fingerprinting of the signal
strength.
It uses a simple cartography (database) of reference points, built
manually during the system's deployment. When a mobile terminal is to
be located, the database is searched for the reference measurement
that is the most similar to the instantaneous measurement from the
terminal, i.e. the //Nearest in Signal strength Space// (NSS). More
precisely, the instantaneous measurement is compared to each reference
point using one of the similarity algorithms (see “**Similarity**
**algorithms**” below).
Please note that the original RADAR system uses a mobile-centred
architecture (measurements and position computation are done by the
mobile terminal), whereas OwlPS is infrastructure-centred.
: **InterlinkNetworks**
In their technical report entitled “A practical approach to
identifying and tracking unauthorized 802.11 cards and access points”
published in 2002, Interlink Networks, Inc. proposed to use a
transmission equation adapted to indoor environments in order to
compute distances between devices and deduce the positions by
trilateration. The equation used is the one proposed in Pegasus
Technologies, Inc.'s article
[“An introduction to indoor radio propagation” http://www.sss-mag.com/indoor.html];
It is simply an adaptation of the Friis transmission equation, given
as:
L = -35 × log10(d) + 40
with L the path loss in dB and d the distance between the two devices
in metres. (Note that the leading minus sign was omitted in the
article.) To obtain the distance in function of the path loss, it is
written as:
d = 10^(40-L / 35)
: **FBCM** (Friis-Based Calibrated Model)
FBCM is an algorithm designed by F. Lassabe that uses the same
principle as the InterlinkNetwork technique, except the path loss
equation is adapted to each deployment area (instead of a generic
indoor environment), thanks to a minimal calibration of the system
(about one reference point per room of a regular office environment).
For a given capture point, one Friis index is computed for each
calibration point, then all these indexes are averaged; this average
index is the Friis index of the capture point in question. There are
therefore as much Friis indexes as capture points, but they stay the
same unless a new calibration is conducted. As for InterlinkNetwork,
the position is resolved by trilateration.
FBCM was published in the following articles:
- F. Lassabe, O. Baala, P. Canalda, P. Chatonnay, F. Spies, “A
Friis-based calibrated model for WiFi terminals positioning”, in
Proceedings of IEEE Int. Symp. on a World of Wireless, Mobile and
Multimedia Networks, 2005.
- F. Lassabe, P. Canalda, P. Chatonnay, F. Spies, “Indoor Wi-Fi
positioning: Techniques and systems”, in Annals of
telecommunications 64(9/10), 2009.
: **FRBHMBasic** (FBCM and Reference-Based Hybrid Model, basic variant)
FRBHM is a hybrid technique that follows the FBCM in F. Lassabe's
work. The main idea of the FRBHM is to combine the FBCM with a signal
strength cartography (that can be the same as the one used to
calibrate the FBCM). Three variants exist, but the current version of
OwlPS implements only the first one, called “basic”, which was
published in:
F. Lassabe, D. Charlet, P. Canalda, P. Chatonnay, F. Spies, “Refining
WiFi indoor positionning renders pertinent deploying location-based
multimedia guide”, in Procs of IEEE 20th Int. Conf. on Advanced
Information Networking and Applications, 2006.
Once the signal strength from the mobile terminal is measured, the
cartography is searched for the most similar point (like in the NSS
algorithm); the signal strength values of this reference point are
used to calibrate the propagation equation of the FBCM. The FBCM is
then used to compute a new position by trilateration, which is the
solution proposed by the algorithm.
Unlike the FBCM, the FRBHM allows to take into account only the
approximate location of the mobile terminal to calibrate the
propagation equation, instead of using an average of all the reference
points of the deployment area. Indeed, it has been found that the
propagation equation can be very different from a location of a given
building to another.
== Similarity algorithms ==
The similarity algorithm is one of the key elements of a
cartography-based positioning technique. It is the function which is in
charge of searching the database of reference points and compare the
similarity of the reference points with the current measurement. More
generally speaking, a similarity function's goal is to assess the
resemblance of two samples. We write //p// the sample containing the
measurements corresponding to the positioning request sent by the mobile
terminal, and //c_i// the sample containing the measurements
corresponding to the //i//th reference point of the cartography. The
similarity between the two samples is written //S(p,c_i)//. Numerically
speaking, the more similar are the two samples, the smallest is the
similarity score (so it behaves like a distance in this regard).
: **mean**
Appropriately enough, the first similarity method implemented in OwlPS
Positioner, called //mean//, is a distance. More precisely, it is the
Spearman distance (i.e. the square Euclidean distance) between the mean
signal strength of the two samples. With //M(x)// the mean signal
strength of the sample //x//, the similarity is expressed as:
S(p,c_i) = (M(p) - M(c_i))²
The //mean// similarity function is the reference, and so far it has
been the most reliable and the most accurate of the implemented
similarity algorithms.
: **interval**
This first alternative to the good old //mean// function is a basic
method to take into account the standard deviation in the similarity
assessment, called //interval//. The mean //M(p)// and the standard
deviation //σ(p)// of the signal strengths of the positioning
request's packets are calculated. The nearest calibration measurement
from //p// is the one which has the greatest number of packets with
signal strength in the interval [M(p) - σ(p) ; M(p) + σ(p)].
In order for the similarity score to be lower when the two samples are
closer, it is in fact calculated as the reciprocal of the number of
packets in the interval. With //x// a signal strength of //c_i//, the
similarity function is expressed as:
S(p,c_i) = 1 / Σ_x(M(p) - σ(p) ≤ c_i_x ≤ M(p) + σ(p))
If at least one of the signal strength values corresponds to the
selection criteria, the similarity score is in the interval
]0 ; 1]. In order to avoid the division by zero, the score is set
to 2 when no packet correspond.
: **interval2**
The second similarity algorithm using the mean and the standard
deviation is called //interval2//. Like in //interval//, //M(p)// and
//σ(p)// are calculated. Then, the program calculates the proportion
of packets of //c_i// that belong to the two following intervals
//I₁// and //I₂//:
- I₁: [M(p) - 0.674 × σ(p) ; M(p) + 0.674 × σ(p)]
- I₂: [M(p) - σ(p) ; M(p) + σ(p)]
-
Assuming the signal strength distribution is Gaussian (which,
incidentally, has been proven not to be always the case), about 50% of
the packets of //c_i// should belong to //I₁//, and about 68% should
belong to //I₂//. The nearest calibration measurement to //p// is the
one for which these two proportions are the closest to the theoretical
values. Mathematically speaking, the measurement point selected is
the one that minimises the sum of both distances between the
theoretical value and the observed value of the intervals. Writing
//P(c_i,I_x)// the proportion of packets of //c_i// that belong to the
interval //I_x//, the similarity is expressed as:
S(p,c_i) = (P(c_i,I₁) - 68)² + (P(c_i,I₂) - 50)²
The similarity score obtained theoretically ranges from 0  when the
two calculated proportions are strictly equal respectively to 50 and
68, and therefore the similarity is maximal  to 7124  when the two
proportions equal zero and the similarity is minimal.
== Autocalibration algorithms ==
The self-calibration mechanism of OwlPS can work in several modes,
possibly simultaneously: //mesh//, //line// and //list//. As a reminder,
the self-calibration only works with location fingerprinting-based
(cartography-based) algorithms; its goal is therefore to generate
calibration points (reference points).
: **mesh**
In this mode, the reference points are generated in a regular meshing.
It is the most suitable mode for general-purpose localisation. The
step between two points can be set independently for each axis, so
that an asymmetric meshing is possible (e.g. 1.50 m in X and 2 m in
Y). The Z coordinate is different since it is not a distance in metres
but a number of floors (cf. option
**positioning.generated-meshing-grain-z**).
For now, all the capture points declared in the system are assumed to
be in coverage, which can be problematic for bigger deployment areas.
: **line**
This mode allows the reference points to be generated along a path
defined by a series of points including the coordinates of the capture
points. It is suitable for environments where there is no or few
visibility between the different capture points, for example a network
of underground tunnels. The approximate step between two generated
points is set by the administrator (cf. option
**positioning.generated-line-step**), but the system adjusts it for
each segment of the path to generate the ideal number of points
separated by equal distances. For now, a given reference point will
contain measurements for only one or two capture points, depending if
it is at the extremity of the path or between two capture points.
: **list**
In this mode, the user provides a list of points to generate. The
mechanism of generation is otherwise similar to the one used in mesh
mode.
= Files =
: //{{INSTALL_PREFIX}}/etc/owlps/owlps-positioner.conf//
Default configuration file.
= Copying =
This documentation is part of the Owl Positioning System (OwlPS)
project. It is subject to the copyright notice and license terms
in the COPYRIGHT.t2t file found in the top-level directory of the
OwlPS distribution and at
https://code.lm7.fr/mcy/owlps/src/master/COPYRIGHT.t2t
= See also =
owlps.t2t, owlps-architecture.t2t, owlps-deployment.t2t