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