Method of Constructing a Three-Dimensional Wireless Coverage Map Nikolay Manaev1[0000-0003-4162-3290], Taufik Aliev2[0000-0003-0278-688X] 1 ITMO University, Saint-Petersburg 197101, Russia manaev.ny@gmail.com aliev@cs.ifmo.ru Abstract. In recent years, wireless networks have become widespread. Devices connected to Wi-Fi and mobile networks generate a significant share of Internet traffic. Analysts predict that devices connected to Wi-Fi and mobile networks will generate 73% of Internet traffic by 2021. Due to the growing need for data exchange not only in two-dimensional space, there is a need for three- dimensional analysis of wireless network coverage. The use of modern algo- rithms of simultaneous localization and mapping allow to automate the acquisi- tion of information about the level of the received signal from Wi-Fi access points simultaneously with the acquisition of sufficiently accurate data on the location of the receiver. The method under development will help network en- gineers and network administrators to build wireless coverage maps that will most representatively show existing network coverage. In this work, we devel- op and estimate the quality of a method for constructing a three-dimensional map of a network coverage by anchor points using approximation and interpola- tion methods. Keywords: wireless networks, coverage analysis, interpolation methods. 1 Introduction Over the past 10-15 years, wireless networks (especially the 802.11*) have become widespread. Wi-Fi is used in lecture halls, stadiums, train stations, exhibition com- plexes, meeting rooms in office complexes, etc. Analysts from CISCO predict that devices connected to Wi-Fi and mobile networks will generate 73% of Internet traffic by 2021 [1]. The high density of the location of WLAN users makes it more rational to use ac- cess points, more competently calculate their location. Heatmaps are currently used to show representative network coverage. Sample of WLAN heatmap is shown in fig 1. ___________________ Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribu- tion 4.0 International (CC BY 4.0). 2 Fig. 1. Sample of wireless coverage heatmap (created with Ekahau HeatMapper). In recent years, the use of wireless networks has ceased to be limited to two- dimensional space. Small unmanned vehicles, such as quadcopters, have been used in various areas of human activity. Also, IoT class devices are widely used, which also actively use wireless connections and are often located in hard-to-reach places. All existing software for building heatmaps can be divided into 2 categories: based on model data[6-7] and based on experimental data[8-13]. For example, D-Link Wi-Fi Planner Pro [6] allows to simulate signal propagation taking into account the characteristics of network equipment (antenna patterns) and a given environment (dimensions and material from which surrounding objects and partitions are made). Most often, the simulation results do not correspond to real data, since the simulation does not take into account a number of parameters that signifi- cantly affect the signal propagation. In support of the above, the creators of this soft- ware say that after the actual deployment of the network, this model should not be used to replace the existing one [6]. Also, Wi-Fi Planner Pro does not allow to simu- late a heat map for open spaces (street quarters, stadiums, etc.). Due to the growing need for data exchange not only in two-dimensional space, there is a need for three-dimensional analysis of wireless network coverage [2]. They do not allow to accurately correlate the RSSI value and its corresponding co- ordinate in space, since the user has to “guess” his location on the floor plan. The developed method will help network engineers, network administrators in con- structing wireless coverage maps that will show the current status of network cover- age. The task of this type of analysis will be facilitated by combining algorithms for constructing a function by anchor points and algorithms for simultaneous localization and mapping – SLAM [4]. This method will allow you to receive the signal strength from Wi-Fi access points at the same time obtaining accurate data on the location of the receiver. 3 The result of data collection will be a built-up cloud of points of the surrounding space, the trajectory of the camera and the corresponding values of the received signal strength indicator – RSSI. An example of the obtained trajectory using the SLAM algorithm is shown in Fig. 2. Fig. 2. Example of calculated point cloud and camera track [4] In this paper, we propose a method for constructing a three-dimensional map of the coverage by anchor points using approximation and interpolation methods. 2 Related work 2.1 Development of mathematical model The camera path and RSSI values will be obtained as {𝑥𝑖 , 𝑦𝑖 , 𝑧𝑖 , 𝑅𝑆𝑆𝐼𝑖 }, where 𝑖 ∈ 1 … 𝑁 – is the number of collected points. Next, the user sets the step of the spatial grid – 𝐷 and the radius of the search for anchor points 𝑅. Figure 3 shows a schematic representation of the spatial grid: yellow points is known values; purple points will be used for RSSI calculations. RSSI can be represented as a function of 𝑅𝑆𝑆𝐼(𝑥, 𝑦, 𝑧). RSSI calculation should be based on known values using approximation and interpolation methods. For this, the authors propose using the Lagrange polynomial of the second degree. 4 y RSSI(0.9, 2.1, 0.3) RSSI(0.8, 1.2, 1.1) RSSI(1.05, 0.3, 0.5) z RSSI(0, 1, 1) RSSI(1, 0, 1) RSSI(1, 1, 1) Fig. 3. Schematic representation of a spatial grid The Lagrange interpolation polynomial is usually used to obtain a function of one variable in the form of a polynomial at given points (interpolation nodes), the values of which are known [11]. The single-degree polynomial has the following form [11]: 𝑥 1 |𝑥 1| 𝐿(𝑥) = ∑𝑖=1 (𝑓(𝑥𝑖 ) × ∏𝑗=1,𝑗≠𝑖 𝑥𝑗𝑖 𝑛 𝑛 1 ), (1) |𝑥 1| 𝑗 where: 𝑛 – is the number of interpolation nodes, 𝑖 – is the index from 1 to 𝑛 (𝑛 ≥ 2) according to the node (anchor point) numbers, 𝑓(𝑥𝑖) – values in the nodes. The work [3] describes the application of the Lagrange polynomial for functions of several variables, and not of one. The formula for constructing a polynomial function of 𝑚 is presented below: 𝑥 (1) ⋯ 𝑥 (𝑚) 1 (1) (𝑚) | 𝑥𝑘1 ⋯ 𝑥𝑘 1 1| | ⋮ ⋱ ⋮ ⋮| (1) (𝑚) 𝑥𝑘 … 𝑥𝑘 1 𝐿(𝑥 (1) ,…,𝑥(𝑚)) = ∑𝑖∈{1,…,𝑛} 𝑓(𝑥 (1) ,…,𝑥(m)) × ∏ 𝑘1 ∈{{1,…,𝑛}\{𝑖}} 𝑚 (1) 𝑚 (𝑚) , (2) 𝑖 𝑖 𝑥𝑖 ⋯ 𝑥𝑖 1 ⋮ (1) (𝑚) 𝑘𝑚 ∈{{1,…,𝑛}\{𝑖,𝑘1 ,…,𝑘𝑚−1}} | 𝑥𝑘1 ⋯ 𝑥𝑘 1 1| | ⋮ ⋱ ⋮ ⋮| (1) (𝑚) ( 𝑥𝑘 𝑚 … 𝑥𝑘 𝑚 1) 5 where: m – is the number of given points (𝑚 ≤ 𝑛 − 1); 𝑘1 … 𝑘𝑚 – all possible linear combinations from 1 to 𝑚, excluding 𝑖; other variables have the same meaning as in formula (1) [2]. In the problem under consideration, the dimension of space is 4 (𝑥, 𝑦, 𝑧, 𝑅𝑆𝑆𝐼), therefore, to compose a polynomial of the second degree, it suffices to have 𝑚 = 5 anchor points. Resultant formula for calculating RSSI at a random spatial point {𝑥, 𝑦, 𝑧} takes the form of the following linear combination: (1) (2) (3) (4) (5) 𝑅𝑆𝑆𝐼(𝑥,𝑦,𝑧) = 𝑙(𝑥,𝑦,𝑧) + 𝑙(𝑥,𝑦,𝑧) + 𝑙(𝑥,𝑦,𝑧) + 𝑙(𝑥,𝑦,𝑧) + 𝑙(𝑥,𝑦,𝑧) , (3) Each of the elements of this linear combination has the following form: 𝑥 𝑦 𝑧 1 𝑥𝑘1 𝑦𝑘 𝑧𝑘1 1 1 | ⋮ ⋮ ⋮ | ⋮| (i) 𝑥𝑘5 𝑦𝑘 𝑧𝑘5 1 𝑙(𝑥,𝑦,𝑧) = 𝑅𝑆𝑆𝐼(𝑥𝑖,𝑦𝑖 ,𝑧𝑖) × ∏ 𝑘1 ∈{{1,…,5}\{𝑖}} 𝑥𝑖 𝑦𝑖 5 𝑧𝑖 1 , (4) ⋮ 𝑥𝑘1 𝑦𝑘 𝑧𝑘1 1 1 | 𝑘5 ∈ {{1,…,5}\{𝑖,𝑘1 ,…,𝑘5 }} | ⋮ ⋮ ⋮ ⋮| 𝑥𝑘5 𝑦𝑘 𝑧𝑘5 1 5 Full formula for each element shown in (5-10) 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦2 𝑧2 1 𝑥 𝑦2 𝑧2 1 𝑥 𝑦2 𝑧2 1 𝑥 𝑦3 𝑧3 1 | 2 | | 2 | | 2 | | 3 | 𝑥3 𝑦3 𝑧3 1 𝑥3 𝑦3 𝑧3 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 (1) 𝑥 𝑦4 𝑧4 1 𝑥 𝑦5 𝑧5 1 𝑥 𝑦5 𝑧5 1 𝑥 𝑦5 𝑧5 1 𝑙(𝑥,𝑦,𝑧) = 𝑅𝑆𝑆𝐼(𝑥1 ,𝑦1 ,𝑧1 ) × 4 𝑥1 𝑦1 𝑧1 1 × 5 𝑥1 𝑦1 𝑧1 1 × 5 𝑥1 𝑦1 𝑧1 1 × 5 𝑥1 𝑦1 𝑧1 1 (5) 𝑥 𝑦2 𝑧2 1 𝑥 𝑦2 𝑧2 1 𝑥 𝑦2 𝑧2 1 𝑥 𝑦3 𝑧3 1 | 2 | | 2 | | 2 | | 3 | 𝑥3 𝑦3 𝑧3 1 𝑥3 𝑦3 𝑧3 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 𝑥5 𝑦5 𝑧5 1 𝑥5 𝑦5 𝑧5 1 𝑥5 𝑦5 𝑧5 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦3 𝑧3 1 | 1 | | 1 | | 1 | | 3 | 𝑥3 𝑦3 𝑧3 1 𝑥3 𝑦3 𝑧3 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 (2) 𝑥 𝑦4 𝑧4 1 𝑥 𝑦5 𝑧5 1 𝑥 𝑦5 𝑧5 1 𝑥 𝑦5 𝑧5 1 𝑙(𝑥,𝑦,𝑧) = 𝑅𝑆𝑆𝐼(𝑥2 ,𝑦2 ,𝑧2 ) × 4 𝑥2 𝑦2 𝑧2 1 × 5 𝑥2 𝑦2 𝑧2 1 × 5 𝑥2 𝑦2 𝑧2 1 × 5 𝑥2 𝑦2 𝑧2 1 (6) 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦3 𝑧3 1 | 1 | | 1 | | 1 | | 3 | 𝑥3 𝑦3 𝑧3 1 𝑥3 𝑦3 𝑧3 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 𝑥5 𝑦5 𝑧5 1 𝑥5 𝑦5 𝑧5 1 𝑥5 𝑦5 𝑧5 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥1 𝑦1 𝑧1 1 𝑥1 𝑦1 𝑧1 1 𝑥1 𝑦1 𝑧1 1 𝑥2 𝑦2 𝑧2 1 | | | | | | | | 𝑥2 𝑦2 𝑧2 1 𝑥2 𝑦2 𝑧2 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 (3) 𝑥 𝑦4 𝑧4 1 𝑥 𝑦5 𝑧5 1 𝑥 𝑦5 𝑧5 1 𝑥 𝑦5 𝑧5 1 𝑙(𝑥,𝑦,𝑧) = 𝑅𝑆𝑆𝐼(𝑥3 ,𝑦3 ,𝑧3 ) × 4 𝑥3 𝑦3 𝑧3 1 × 5 𝑥3 𝑦3 𝑧3 1 × 5 𝑥3 𝑦3 𝑧3 1 × 5 𝑥3 𝑦3 𝑧3 1 (7) 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦2 𝑧2 1 | 1 | | 1 | | 1 | | 2 | 𝑥2 𝑦2 𝑧2 1 𝑥2 𝑦2 𝑧2 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 𝑥5 𝑦5 𝑧5 1 𝑥5 𝑦5 𝑧5 1 𝑥5 𝑦5 𝑧5 1 6 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦2 𝑧2 1 | 1 | | 1 | | 1 | | 2 | 𝑥2 𝑦2 𝑧2 1 𝑥2 𝑦2 𝑧2 1 𝑥3 𝑦3 𝑧3 1 𝑥3 𝑦3 𝑧3 1 (4) 𝑥 𝑦3 𝑧3 1 𝑥 𝑦3 𝑧3 1 𝑥 𝑦5 𝑧5 1 𝑥 𝑦5 𝑧5 1 𝑙(𝑥,𝑦,𝑧) = 𝑅𝑆𝑆𝐼(𝑥4 ,𝑦4 ,𝑧4 ) × 3 𝑥4 𝑦4 𝑧4 1 × 3 𝑥4 𝑦4 𝑧4 1 × 5 𝑥4 𝑦4 𝑧4 1 × 5 𝑥4 𝑦4 𝑧4 1 (8) 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦2 𝑧2 1 | 1 | | 1 | | 1 | | 2 | 𝑥2 𝑦2 𝑧2 1 𝑥2 𝑦2 𝑧2 1 𝑥3 𝑦3 𝑧3 1 𝑥3 𝑦3 𝑧3 1 𝑥3 𝑦3 𝑧3 1 𝑥5 𝑦5 𝑧5 1 𝑥5 𝑦5 𝑧5 1 𝑥5 𝑦5 𝑧5 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥 𝑦 𝑧 1 𝑥1 𝑦1 𝑧1 1 𝑥1 𝑦1 𝑧1 1 𝑥1 𝑦1 𝑧1 1 𝑥2 𝑦2 𝑧2 1 | | | | | | | | 𝑥2 𝑦2 𝑧2 1 𝑥2 𝑦2 𝑧2 1 𝑥3 𝑦3 𝑧3 1 𝑥3 𝑦3 𝑧3 1 (5) 𝑥 𝑦3 𝑧3 1 𝑥 𝑦3 𝑧3 1 𝑥 𝑦4 𝑧4 1 𝑥 𝑦4 𝑧4 1 𝑙(𝑥,𝑦,𝑧) = 𝑅𝑆𝑆𝐼(𝑥5 ,𝑦5 ,𝑧5 ) × 3 𝑥5 𝑦5 𝑧5 1 × 3 𝑥5 𝑦5 𝑧5 1 × 4 𝑥5 𝑦5 𝑧5 1 × 4 𝑥5 𝑦5 𝑧5 1 (9) 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦1 𝑧1 1 𝑥 𝑦2 𝑧2 1 | 1 | | 1 | | 1 | | 2 | 𝑥2 𝑦2 𝑧2 1 𝑥2 𝑦2 𝑧2 1 𝑥3 𝑦3 𝑧3 1 𝑥3 𝑦3 𝑧3 1 𝑥3 𝑦3 𝑧3 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 𝑥4 𝑦4 𝑧4 1 2.2 Modeling “Ideal” coverage Path-Loss model According to research [2] RSSI is measured by a receiver on a logarithmic scale in dBm and can be described by the following equation: 𝑑 𝑃𝑑 = 𝑃0 − 10 ∗ 𝑛 ∗ lg (𝑑 ) (10) 0 where: 𝑑 [м] is the distance from the device to the transmitter; 𝑑0 [м] is the distance from the device to the access point at which the signal power 𝑃0 was measured; 𝑃0 [𝑑𝐵𝑚] is the signal power of the device, measured at a unit distance 𝑑0 from the device; 𝑛 is the coefficient of signal power loss during propagation in the medium, dimen- sionless quantity (𝑛 = 2 for air, increases increase with obstacles); 𝑃𝑑 [𝑑𝐵𝑚] – RSSI. In the paper [5], the dependence indicated above is confirmed experimentally. Figure 4 graphically displays the dependence. The black line indicates RSSI values indoors, the red line indicates outdoor RSSIs at a distance of up to 300 m. 7 Fig. 4. Combined indoor and outdoor RSSI dependence from distance [5] Application of Path-Loss model To evaluate the quality of the developed method, the following steps are proposed: 1. simulating the ideal propagation of the signal in the room (result – dataset 1); 2. simulating the movement of the “receiver” in this room with the registration of RSSI values (result – dataset 2); 3. applying the proposed mathematical model to the dataset collected in the previous step (result – dataset 3); 4. compare the dataset 1 and dataset 2. Room parameters: ─ size: 30m * 30m * 15m; ─ step of spatial grid (D): 1,35m; ─ two access points with coordinates: {15m, 5m, 15m} and {25m, 20m, 7m}. Calculated dataset 1 is shown in the fig. 5. 8 Fig. 5. Visual representation of dataset 1 To simulate the movement of the "receiver" in space, the Path-Loss model was ap- plied to a certain number of points that have the shape of a spiral segment, resulting in a new dataset, visually displayed in fig. 6. 2.3 Application of developed mathematic model As a result of applying formulas (3, 4) to dataset 2, a spatial grid is obtained, shown in fig. 7. As we can be seen from fig. 7, in general, dataset 1 and dataset 3 looks similar, but only in a first approximation. Obviously, each of the calculated RSSI values has its own confidence level depending on the distance to the anchor points from dataset 2. 9 Fig. 6. Visual representation of dataset 2 Fig. 7. Visual representation of dataset 3 Authors propose dividing all the calculated points from dataset 3 into several groups. Then, for each group, calculate the standard deviation of RSSI from ideal propagation (dataset 1). The results are presented in fig. 8. 10 25 20 ∆RSSI [dBm] 15 10 5 0 1,00 6,00 11,00 16,00 21,00 R [m] Fig. 8. Dependence of the standard deviation of the error (∆RSSI, Y-axis) on the distance to the anchor points (R, X-axis) The highest deviations at a distance of more than 5 meters from anchor points. These values are not acceptable for predicting signal propagation at these points. But they indicate that further research and refinement of the method, the use of more ad- vanced approximation algorithms will reduce deviations from "ideal" model data. 3 CONCLUSIONS The subject of this study has a weak theoretical and practical development. In this paper, the first steps in the creation of a new method of constructing maps of wireless propagation. Due to the analysis of errors, directions for further developments were identified, hypothetical methods for increasing the accuracy of the method were found, and fur- ther development of the researches was determined. With further development, this method will help network engineers and adminis- trators to build three-dimensional maps of wireless signal propagation. Also, when combining the developed method with SLAM algorithm, there will be no need for manual comparison of odometric data when measuring the level of the wireless signal in space, which will have a positive impact on the accuracy of the maps. 11 References 1. Cisco Visual Networking Index: Forecast and Trends, 2017–2022 White Paper, https://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking- index-vni/white-paper-c11-741490.html, last accessed 24.10.2019. 2. Brett G.: 3D Signal Strength Mapping of 2.4GHz Wi-Fi Networks, Electrical Engineering Department, California Polytechnic State University, (2018). 3. V. A. Tarannik, Application of the “Lagrange Interpolation Polynomial” for functions with many variables, ScienceRise (2015). 4. LSD-SLAM: Large-Scale Direct Monocular SLAM, https://vision.in.tum.de/research/vslam/lsdslam?redirect=1, last accessed 27.10.2019. 5. E. Goldoni, L. Prando, A. Vizziello, P. Savazzi, [etc.] Experimental data set analysis of RSSI-based indoor and outdoor localization in LoRa networks: Wiley, July, 2018. – 6p. 6. D-link Wi-Fi Planner PRO, http://www.dlink.ru/ru/faq/345/1640.html, last accessed. 25.01.2020. 7. Ekahau Pro. Industry standard tool for designing, analyzing, optimizing and troubleshoot- ing Wi-Fi Networks, https://www.ekahau.com/products/ekahau-site-survey/overview/, last accessed. 25.01.2020. 8. Wi-Fi Heat Maps with Network Performance Monitor, https://www.solarwinds.com/network-performance-monitor/use-cases/wifi-heat-map, last accessed. 25.01.2020. 9. 2D & 3D Wi-Fi Network Coverage Maps with Acrylic Wi-Fi Heatmaps , https://www.acrylicwifi.com/en/wlan-wifi-wireless-network-software-tools/wifi-site- survey-software-acrylic-heat-maps/high-quality-3d-wifi-coverage-maps/, last accessed. 25.01.2020. 10. VisiWave Site Survey, https://www.visiwave.com/wifi/site-survey.php, last accessed. 25.01.2020. 11. Ekahau Site Survey and Wi-Fi Planner - Cisco DevNet Ecosystem Exchange https://developer.cisco.com/ecosystem/spp/solutions/89193/, last accessed. 25.01.2020. 12. Signal Mapper – Signal Garden, https://signalgarden.com/signal-mapper/, last accessed. 25.01.2020. 13. Wireless EM Propagation Software - Wireless InSite – Remcom, https://www.remcom.com/wireless-insite-em-propagation-software, last accessed. 25.01.2020.