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
