Article is dedicated to the problems of indoor object position acquisition using wireless networks and its accuracy. Lateration - is the process of absolute or relational position acquisition by having the distances to objects, whose position is already known with help of geometry equations of circles, spheres and triangles intersections. For the plane this problem has the name Trilateration because of requirements to have at least 3 points with known positions. In three dimensional space there should be more than 3 points if their position is free.
The information of indoor position for all the participants can be used to solve many different actual tasks starting from logistics and ending up with market research. One of the problems is – evacuation of people from building during disasters. The problem is how to create optimal track for each person to leave the building under the minimal time [Amirgaliyev et al., 2016]. Another similar problem is – tactical planning of movement for mobile rescue groups within enclosed building, where information of current position for each participant is extremely valuable.
Trilateration is based on acquisition of coordinates of triangle vertices using lengths of triangles sides. The usual schema of trilateration pass depicted on figure 1. Using the known coordinates of A and B vertices, distance between them – b, and also measured lengths of sides and calculated horizontal position d1,d2,d3 and so on up to the other side b1 of the pass between C and D we can find the final result.
In this way using horizontal positions and direction angles (with help of trigonometry functions) we can find increments of coordinates, and then through them the coordinates of geodesy stations. 3
Today we have satellite positioning systems – GPS/GLONASS for outdoor navigation. The main disadvantage of satellite positioning systems is that they are problematic in enclosed spaces, as a result of which it is necessary to look for other ways of solving the problem of indoor navigation. There are several of them: 1. Wi-Fi navigation. The method is based on the signal strength. For determining the coordinates the user device scans available Wi-Fi access points, then sends information about them to the server, where coordinates for each access point are well known. According to them the user’s coordinates are calculated. Unfortunately, Wi-Fi points coordinates are uncertain and they can change. Accuracy of such an approach can be up to 2 meters. Also there may be a disadvantage – the protection system from advertisement that is integrated into new smartphones, that makes it impossible to acquire the position for device [Tikunov et al., 2004]. 2. Geomagnetic positioning.Built upon the orientation of the Earth’s magnetic field and is based on geomagnetic anomalies as criteria for geomagnetic positioning (anomalies arise due to heterogeneity of the geomagnetic field). It consists in fixing geomagnetic anomalies and applying them to the map of the territory on which it is supposed to navigate. Hereafter navigation is performed on a map made by the device, in which a magnetometer is built in. A practical example of implementation is the IndoorAtlas system of the team of scientists from the Finnish University of Oulu. The disadvantage is the high complexity of implementation, low accuracy. In the rooms there are a lot of dynamically changing magnetic anomalies (wiring, the field in which varies depending on the connected load and greatly changes the configuration of the magnetic field around them, visitors with their radio electronic devices, shelves, carts), greatly complicating the navigation based on the specified orientation in Space [Curran et al., 2009]. 3. Satellite navigation systems (GPS/GLONASS, etc.) + Inertial navigation system (INS).It is applicable when periodically there is a signal of satellite navigation systems – for example, travel through the tunnel – when we drive in the tunnel, we still have available current location and direction of travel from the GPS / GLONASS satellites, then at the entrance to the tunnel, we lose the signal, and use the already inertial navigation systems (INS, based on accelerometer, gyroscope, magnetometer), which is used as the initial conditions of the last actual data with GPS / GLONASS to the loss of communication with the satellite and supports their relevance on the basis of received sensor data about the current speed / acceleration / driving direction, before the resumption of communications with the satellites. It should be taken into account that errors constantly accumulate in INS, and over time, the data obtained from the INS become more and more different from reality [Curran et al., 2009]. 4. Orientation by base stations of cellular service providers (GSM). In the area of visibility of a cellular phone / GSM-modem there are at least one GSM base station, and usually several. The location coordinates of these base stations are known. Many modems allow you to get a list of visible base stations (BS) with their LAC and CELLID it remains only through the databases with the coordinates of the BS to get their coordinates and determine the approximate location using the triangulation method. Accuracy is very low (the BS can be placed at a distance of 35km from the user + some BS are mobile and constantly change their dislocation) [Curran et al., 2009]. 5. The use of Bluetooth beacongives sufficient accuracy at an acceptable level of financial costs; a promising technology that is actively developing, that’s why iBeacon will be discussed in detail in the next section and implemented in practice. 6. Navigation based on the synergy effectsolves the problem of determining the current location using all (or most) of the methods listed above. Efficiency is achieved due to the fact that we use several vector coordinates simultaneously, which helps to compensate errors and improve the accuracy of determining the coordinates [Curran et al., 2009]. The problem of determining the amount of people located in one or another place inside building can be solved by using simple video survey cameras as was described in [Amirgaliyev et al., 2016]. But there are situations where this approach is absolutely inappropriate – for example in fogged circumstances, or when camera is out of service. Therefore better solutions can be a radio signals, that come from different local stations (beacon). We can use the lateration algorithm to find the position of each person that has appropriate device and programmed module, by calculating distances between the desired point and at least three access points (beacons) with a further solution of the system of N nonlinear equations. With N = 3, this method is also known as trilateration. To find the distances, the radio wave propagation model is used, which requires the calibration of certain parameters that depend on the characteristics of the circumference:
P L(d) = Pt
P (d) = P L(d0) + n10lg d d0 (1) (2) where d is the distance to the agent, P L(d) is the signal power loss at a distance d, Pt is the transmit power, P (d) is the signal power at the receiver at a distance d, d0 is the distance of 1 meter, n is the signal propagation coefficient in the circumference. Figure 2 shows the geometric approaches to the solution of the positioning problem, where ri is the distance to the i-th access point from the agent.
Circular lateration (fig. 2-a) is based on the distance between the desired point and the access points. To calculate the coordinates of the agent it is necessary to solve the system from equations of the form [Miniakhmetov et al., 2013]: ri = √(Xi The advantage of the algorithm is a sufficiently high accuracy with the corresponding parameters of the circumference. The disadvantage of the algorithm is the need to carefully build a signal propagation model in each specific environment, for each individual access point, which ultimately does not guarantee very high accuracy, as a result of indoors effects such as attenuation and reflection of the signal, the simulation of which is a very problematic task. This algorithm is one of the basic, it is applied in GPS and cellular networks, where these high-frequency effects do not arise and the construction of a signal propagation model is not so labor-consuming task. This algorithm is an alternative to the previous one and is an approximation method, based on the search of possible coordinates of the agent, in order to find the nearest point to the intersection of circles. The advantage of this algorithm is that there is no need to calibrate parameters in the signal propagation model. The algorithm is presented in the following implementation options: Variant 1. The coordinates of the agent are calculated through minimization of the functional, the core of which is the attenuation ratio of the signal from the 1st and the i-th access points to an arbitrary point with the coordinates (x; y). We will assume that the signal attenuation coefficient, expressed in decibels, corresponds to the formula:
P (d) = P0 n10lgd where d is the distance to the agent, P0 is the signal power value at a distance of one meter and n is the signal propagation coefficient. The values of P 0 and n are unknown. In order to get rid of these uncertain parameters, it is necessary to evaluate the position of the agent through minimization of the following functional: (X0; Y0) = argmin[ (x; y)] N (x; y) = ∑ Pi i=2 P1 lg[di(x;y) 2 lg(d1(x;y) where d1 and di are the distances from 1 and the i-th access point to the current point with coordinates (x, y), respectively [Miniakhmetov et al., 2013].
Variant 2. The coordinates of the agent are also calculated through minimization of the functional, the core of which is the ratio of the attenuation of the signal from the 1st and the i-th access points. However, before this, the parameters in the signal propagation model are estimated by minimizing the mean square error: [
] P0 n = (M T M ) 1M T P; M = [ 1 . . . 1 10 lg d1 ] . .
. 10 lg dT ; P = [ P1 ] . . .
Pk Then the coordinates of the agent can be estimated by minimizing the new functional: (X0; Y0) = argmin[ (x; y)] N (x; y) = ∑ Pi i=2 P1
P0 n10 lg[di(x;y) 2 P0 n10 lg(d1(x;y) Variant 3. The coordinates of the agent are calculated through minimization of the functional, the core of which is the difference of the signal attenuation from the 1st and the i-th access points. This algorithm is a modification of variant 2. The functional for minimization is determined by the following expression: Advantages are ease of implementation and high accuracy. Variants of algorithms 2 and 3 demonstrate even higher accuracy, as the parameters for the signal propagation model are estimated. The disadvantages include the increased computational complexity O (N K), where K is the number of points for enumeration. To improve the quality of the algorithm, an initial approximation is necessary, which will reduce the computational complexity. This algorithm can be attributed to both basic and improving, and, preliminary measurements are not required [Miniakhmetov et al., 2013]. 5
The physical implementation of Beacon technology – is simple Bluetooth 4.0 Low Energy device. Typical Beacon has a very small size and can work up to 2 years from small battery. The range of such device can be from 10 to 40 meters. The Beacon is simple device, that can only sends it’s data to everyone [http://developer.android.com/guide/topics/connectivity/bluetooth-le.html]. To calculate the position of person within building with help of such devices - we should place Beacons all around the building. Then find and record coordinates of all Beacons in local coordinate system of the building. As all Beacons always broadcast their information, the person that has an appropriate device collects the data from nearest of them and then, by using the database of coordinates of Beacons and signal strengths can calculate it’s self position. Each beacon transmits in its message the value of the signal strength – TX Power. This is the reference value of the power of the beacon, which is the signal strength at a distance of 1 meter from the beacon. Measured and recorded in the beacon first time in its production. This constant is used to determine the distance from the user to the beacon. The first bit is signed (1 - “-”, 0 - “+”) [Falkov & Romanov, 2015].
To determine the position in the space of the mobile object, it is necessary to obtain information about the distance to the beacons. RSSI parameter(Received Signal Strength Indicator), calculated by the user’s Bluetooth-receiver based on the strength of the received signal, helps us to do it. The higher the value of this parameter, the closer the object is to the beacon. TX Power - this is RSSI, only the reference, measured by the manufacturer of the beacon at a distance of 1 meter from it. To determine the distance to the beacon (in meters), the current RSSI value is used, and the TX Power reference for correction.
The problem of calculating coordinates on the basis of obtaining data on the attenuation of a radio signal is related to the fact that even under direct line of sight conditions, the RSSI parameter “fluctuates”, randomly changing its value, as a result of which it is difficult to determine the distance to the beacon without using any additional approximation techniques. This is due to the following factors: 1. Orientation and characteristic of radiation direction or reception of antenna beacon / user device 2. The presence of large screening objects (the person is also one) in the direction from the beacon to the device 3. The presence of nearby surfaces of materials that reflect the radio signal well, as well as a large accumulation of beacons in one area, due to multipath interference with the main beam [Tikunov et al., 2004] To reduce the spread of RSSI values, we calculate the average value of them by using a data filer buffer and averaging them with a sliding window. Next, we choose only the top three in the RSSI averaging metrics. And use them to obtain the coordinates of the mobile object on the basis of the applied trilateration [Curran et al., 2009].
Even if the object does not move – its calculated location will be with an error of up to 3m. However, the accuracy can be improved by further mathematical processing of the results obtained. To do this, we use the Kalman’s filter [Kalman, 1960]. The filter removes the measurement noise and outputs the result both taking into account the results of the current measurements, and taking into account the predicted results based on past measurements. The filter uses the dynamic model of the system (the law of motion) and 2 cyclically repeating stages: prediction and correction. At the first stage – prediction – we calculate the state of the system at the next time, and on the second – the correction – we correct our forecast using the result of the next measurement. Application of Kalman’s filter gives us a better result in positioning of object with accuracy up to 1m. Figure 3.
There are different approaches to find indoor coordinates of object. Video surveillance [Amirgaliyev et al., 2016] or radio signals from small devices that can be attached to each person [Falkov & Romanov, 2015]. By using the simple Beacon technology and application of trilateration we can find precise position within 3 meters and up to 1 meter using Kalman’s filter of each person inside a building. This approach is much better than a video surveillance that can only provide approximate position of each person inside the space without answering – who is it, and also Beacon is better in fog conditions, when we can not rely on video data any more. We have analyzed their applicability for evacuation problem and found that as more accurate position of people we have inside the building, the more optimal paths for evacuation can be calculated. In problem of evacuation the application of these technologies increase the chance of staying alive in extreme conditions - providing the optimal track for evacuation to all. Also It should be noted that the model for calculating and obtaining coordinates is based on existing algorithms for averaging values and filters for improving accuracy. In the future, we plan to apply neural networks to improve the accuracy of determining the coordinates in an enclosed space. Because the object collects the data from all the beacons that are nearby, it is not known – which of the beacons in particular position of object inside the building has worst accuracy for the distance. Then it is possible to configure a multilayer neural network with 2 outcomes (positions in plane – x, y), and predefined number of inputs that is equal to the number of beacons in the building. We can then collect data from beacons for the different positions inside the building by calculating precise X and Y coordinates in plane using alternative existing methods (theodolite, lidar and so on) to acquire training set for neural network. In this way after training the neural network, we produce interpolation matrix for whole building of all possible positions for the objects according to the training set. [http://developer.android.com/guide/topics/connectivity/bluetooth-le.html] Bluetooth Low Energy.
Pre
Md