# Investigation of WLAN Access Point Placement for Indoor Positioning

Árpád Huszák, Győző Gódor, Károly Farkas

► To cite this version:

Árpád Huszák, Győző Gódor, Károly Farkas. Investigation of WLAN Access Point Placement for Indoor Positioning. 18th European Conference on Information and Communications Technologies (EU-NICE), Aug 2012, Budapest, Hungary. pp.350-361, 10.1007/978-3-642-32808-4_32. hal-01543150

HAL Id: hal-01543150

https://inria.hal.science/hal-01543150

Submitted on 20 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Investigation of WLAN Access Point Placement for Indoor Positioning

Árpád Huszák, Győző Gódor, Károly Farkas

Department of Telecommunications,
Budapest University of Technology and Economics,
Magyar tudósok krt. 2., 1117 Budapest, Hungary
{huszak, godorgy, farkask}@hit.bme.hu

**Abstract.** Wireless indoor positioning has been a popular research topic for years because it provides the basis for a broad domain of location-based applications. Especially the usage of WLAN (Wireless Local Area Network) technology is widespread to build an indoor positioning system due to the reuse of existing and almost ubiquitous WLAN infrastructure worldwide lowering the costs. However, these WLAN systems were not originally designed for positioning services, thus the provided accuracy might be low. The accuracy can be increased by the careful placement of WLAN access points to cover the given area appropriately. In this paper, we propose a method based on simulated annealing to find the optimal number and placement of WLAN access points for indoor positioning and show its investigation using simulations.

**Keywords:** Indoor positioning, WLAN, simulated annealing, MATLAB

## 1 Introduction

With the proliferation of mobile devices and the rapid development of pervasive communication the popularity of location-aware services and applications has been increasing. This requires the use of location sensing systems. Getting the position information in an outdoor environment is relatively simple by using matured technologies, such as GPS (Global Positioning System). However, indoor positioning has been an issue under research for years. Numerous technologies and systems have been proposed and developed for indoor location sensing [1], but the most popular technology is WLAN (Wireless Local Area Network) due to the low cost of WLAN equipments and the possible reuse of existing and almost ubiquitous WLAN infrastructure worldwide.

However, today's WLAN systems were not originally designed for location sensing, hence the accuracy and precision achieved by these systems might be low. For instance, several position estimation schemes use triangulation methods to determine the position of a mobile host [1]. The common indispensable condition for all of these methods is to receive the signal of at least three reference APs (Access Point). But most of the existing WLAN systems does not fulfill this criterion.
Moreover, the number and placement of the access points can have substantial impact on the position accuracy [2].

In this work, we investigated how to place the WLAN access points to receive the signal of at least three reference APs everywhere in the given indoor area, but keep the number of deployed APs as low as possible (thus minimizing the overall cost of the indoor positioning system and its operation expenses). To find the optimal number and placement of the APs considering the map of the given territory we propose a simulated annealing based algorithm. Our method can find a solution, in most of the cases a global optimal one, nearly in constant time in realistic scenarios. Moreover, we have developed a simulation tool in MATLAB [3] environment. We used this tool to implement our algorithm together with several signal propagation models and to analyze the algorithm's behavior.

The rest of the paper is structured as follows. In section 2 and section 3, we give a short overview about WLAN-based indoor positioning systems and signal propagation models, respectively. We describe our simulated annealing based algorithm in section 4, and present some simulation results of its evaluation in section 5. Finally, we give a short summary in section 6.

## 2 Overview of WLAN-based Indoor Positioning Systems

In the last decade, indoor location-based services have been developed rapidly requiring suitable and accurate indoor positioning. Wireless communication technologies are often used in positioning systems due to their handiness. Fig. 1 depicts the most popular wireless technologies used in current positioning systems with their accuracy, scale and the typical localization methods.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Wireless technologies in current positioning systems and their accuracy, scale and localization methods [1].</figcaption></figure>
As we can see from the figure the UWB (Ultra-Wide Band) technology offers the highest accuracy for indoor positioning, but it is quite an expensive solution still today. IR (Infrared) technology requires line-of-sight visibility, since GPS does not work in indoor environment. In cellular networks, usually the positioning information is accessible only by the network provider, and its accuracy is low. It is not so surprising, that WLAN technology is the most popular one to be used in indoor positioning systems, even if the accuracy it basically provides is only in the range of some meters, because it is inexpensive and easy to deploy.

## 2.1 Localization Methods Used in WLAN-based Positioning Systems

In the following, we briefly discuss the most relevant localization methods used in WLAN-based positioning systems [1].

*Received Signal Strengths (RSS):* This method is based on the measurement of the received signal level. By using signal path loss models the distance between the transmitter and the receiver can be estimated. In ideal case, the signal of three reference points is enough to calculate the position.

*Time Of Arrival (TOA):* This method is based on the travel time of a radio signal between the transmitter and the receiver. The distance between them can be derived from the carrier frequency knowing the medium. TOA requires at least three reference points and the precise synchronization of all transmitters and receivers.

*Time Difference Of Arrival (TDOA):* In case of TDOA the idea is analogous to TOA, but it uses the difference in signal arrival time measured at multiple receivers.

*Angle Of Arrival (AOA):* This method uses the direction of the received radio waves. At least three reference points and three measured angles are required to derive the location in the 3-D space.

## 2.2 Specific WLAN-based Indoor Positioning Systems

Several different indoor positioning systems have been developed using WLAN technology. In the following, we shortly discuss couple of them.

The RADAR system has been developed by Microsoft [4]. RADAR is an indoor position tracking system which applies existing WLAN architecture. This solution uses the RSS measurement method combined with the triangulation location technique. For the correct localization at least three APs' signals are to be received. The system achieves an accuracy of around 4m with 50% probability.

The COMPASS system is proposed in [5]. In COMPASS, the positioning algorithm uses a fingerprint-based technique in which the signal strength of a given mobile device is measured by different APs. Moreover, digital compasses are utilized for getting a relatively accurate position. Thus, the user's orientation, considered also in the location estimation, can be measured by a digital compass which is integrated in most of today's mobile devices. COMPASS can achieve an accuracy of about 1.65m, however this system is not suitable for tracking multiple users.
In the Horus system [6], the localization is based on a joint clustering technique using a probabilistic method. Each location candidate has a signal strength vector (fingerprint) and in the location estimation phase each candidate coordinate is regarded as a class associated with the probability that the mobile is in that location. A given location is chosen when its likelihood is the highest. This method can acquire an accuracy of 2.1m with more than 90% probability.

# 3 Indoor Signal Propagation Models

Most of the location estimation techniques in wireless networks is based on some kind of mapping of each transmitter’s signal. In a simple model, each point is mapped to the signal strength of each sensible access point. In case of a more complex model, besides the signal strengths other data can also be considered, such as the detailed map of the building, walls, obstructions, etc.

To compute the signal strength numerous propagation models were proposed [7]. The indoor signal propagation models are more complex than the outdoor ones, because approximating a real indoor environment (signal strength, path loss, etc.) is more difficult due to reflection, diffractions and multi-path propagation. In this section, we overview three well-known indoor signal propagation models we used in our WLAN access point placement investigations.

## 3.1 Free-Space Propagation Model

Line-of-sight path through free space can be described by the simple free-space propagation model. In this environment, there are no obstacles which could cause reflection or diffraction. Typically the free space is the air.

Equation (1) describes the free-space propagation model [8].

$$P_R = P_T \cdot G_T \cdot G_R \cdot \left( \frac{\lambda}{4 \cdot \pi \cdot d} \right)^2, \qquad (1)$$

where $P_R$ is the received power from transmitter (W), $P_T$ is the transmitted power (W), $G_T$ is the transmitter antenna gain (dB), $G_R$ is the receiver antenna gain (dB), $\lambda$ is the signal wavelength (m) and $d$ is the distance from the transmitter (m). In this model, the received power is inversely proportional to the square of the distance between the transmitter and receiver, proportional to the square of the radio signal’s wavelength, and directly proportional to the transmitter and receiver antenna gains [9].

In our investigations, we use this model in such a way that we examine the path between the transmitter and the receiver and in that case when an obstacle exists along the path the received power is reduced by a given value assigned to the object.
## 3.2 Site-General ITU Indoor RF Model

In contrast to the free-space propagation model, this model was developed for indoor environments [10, 11]. Equation (2) describes the ITU path loss model.

$$L = 20 \cdot \log f + N \cdot \log d + Lf(n) - 28, \quad (2)$$

where L is the total path loss (dB), f is the frequency (MHz), N is the distance power loss coefficient, d is the distance between the transmitter and the receiver (m), Lf(n) is the floor penetration loss factor and n is the number of floors between the transmitter and the receiver.

The received power strength can be derived according to equation (3).

$$P_R = P_T - L, \quad (3)$$

where P<sub>R</sub> is the received power (dBm), P<sub>T</sub> is the transmitted power (dBm) and L is the total path loss (dB).

From (2) we can deduce that increasing either the distance or the frequency the path loss also increases. It is analogous with the free-space model, however, the ITU indoor prediction model better estimates the real environment using factor N and Lf(n) [12]. Their values are defined in Table 1 and 2.

<table><caption>**Table 1.** Distance power loss coefficient values (N) used in the ITU model [9].</caption><thead><tr><th>Frequency</th><th>Home env.</th><th>Office env.</th><th>Commercial env.</th></tr></thead><tbody><tr><td>900 MHz</td><td>—</td><td>33</td><td>20</td></tr><tr><td>1.2-1.3 GHz</td><td>—</td><td>32</td><td>22</td></tr><tr><td>1.8-2 GHz</td><td>28</td><td>30</td><td>22</td></tr><tr><td>4 GHz</td><td>—</td><td>28</td><td>22</td></tr><tr><td>5.2 GHz</td><td>—</td><td>31</td><td>—</td></tr><tr><td>60 GHz</td><td>—</td><td>22</td><td>17</td></tr></tbody></table>

<table><caption>**Table 2.** Floor penetration loss factor values (Lf(n)) used in the ITU model [9].</caption><thead><tr><th>Frequency</th><th>No. of level</th><th>Home env.</th><th>Office env.</th><th>Commercial env.</th></tr></thead><tbody><tr><td>900 MHz</td><td>1</td><td>—</td><td>9</td><td>—</td></tr><tr><td>900 MHz</td><td>2</td><td>—</td><td>19</td><td>—</td></tr><tr><td>900 MHz</td><td>3</td><td>—</td><td>24</td><td>—</td></tr><tr><td>1.8-2 GHz</td><td>N</td><td>4n</td><td>15+4(n-1)</td><td>6+3(n-1)</td></tr><tr><td>5.2 GHz</td><td>1</td><td>—</td><td>16</td><td>—</td></tr></tbody></table>

Since our goal is to find the minimal number of APs for a WLAN-based indoor positioning system, which still guarantees full coverage, we selected the values of factor N and Lf(n) for the 1.8-2 GHz commercial environment to be used in our simulations.
## 3.3 Hata-Okumura

The Hata-Okumura model was developed to predict the path loss particularly in outdoor environments, but it can be used also indoor [13]. There are three variants of the model, such as urban area, suburban area and open area. Usually this model is applied in cellular telecommunication systems to predict the total path loss between the mobile station and the base station [14].

In this model, the received power can be derived by using equation (4).

$$P_R = P_T + G_T + G_R - 10 \cdot n \cdot \log d - X_\alpha + 20 \cdot \log \lambda - 20 \cdot \log(4 \cdot \pi), \quad (4)$$

where $P_R$ is the received power (dBm), $P_T$ is the transmitted power (dBm), $G_T$ is the transmitter antenna gain (dB), $G_R$ is the receiver antenna gain (dB), $n$ is the number of obstacles in the signal path (in case of an indoor environment the value is between 4 and 5), $d$ is the distance from the transmitter (m), $X_\alpha$ is a variable with normal distribution and $\alpha$ deviation (in case of WLAN environment (2.4 GHz) $\alpha$ is between 3 and 20dB) and $\lambda$ is the signal wavelength (m).

# 4 WLAN Access Point Placement

As we saw above, several position estimation schemes use triangulation methods to determine the position of a mobile host. The common indispensable condition for all of these methods is to receive the signal of at least three reference APs. In this work, we investigated how to place the APs to provide visibility of at least three reference points everywhere in the given area, but keep the number of deployed APs as low as possible. By reducing the number of deployed APs, the overall cost of the indoor positioning system and its operation expenses can be minimized.

## 4.1 Problem of Optimal WLAN Access Point Placement

Finding the optimal positions for the APs in real environment is a challenging task for analytical methods, because the signal absorption characteristics are too complex to be realistically modeled. However, in order to install the minimum number of reference APs an obvious approach is to analyze and compare all the possible AP setups. Unfortunately, in real world this process is hard to be accomplished, therefore simulations are to be used.

Actually, the number of AP position combinations is infinite because the territory, where the APs can be deployed, is continuous and contains infinite number of points available for AP deployment. To handle this problem, we assume that the APs can be located only in discrete points of the map. If the density of these points are high enough the original situation can be approximated well. For example, if we consider a 100x100m territory where the APs can be placed 10cm from each other, the number of possible AP locations is $10^6$.

Unfortunately, analyzing all possible AP location setups with a brute force algorithm cannot be accomplished due to the high number of location setup
combinations. In the previous example, $2^{1000000}$ different AP position setups exist that cannot be processed in acceptable time. To solve this problem, alternative solutions must be found.

## 4.2 Method for Optimal WLAN Access Point Placement

We propose the following top-down AP placement algorithm to find the optimal AP location setup(s).

The first step is to place an AP in every possible point on the map. In the next step, the coverage area of each AP must be estimated using signal propagation models in order to determine the number of sensed APs in each point where a mobile host can be present. If there is no point on the map where the number of sensed APs is less than three, one AP can be removed. If the number of sensed APs still fulfills the criterion another AP can be removed, otherwise the algorithm stops.

This method can be modeled with a tree graph, where the states are the AP combinations represented by binary numbers. The binary number determines which APs are part of the given setup (e.g., 010 means that the AP in the second position is installed, while the others are already removed). Fig. 2 illustrates the introduced algorithm where the Hamming distance of neighboring states is always one, because only one AP can be removed within one step.

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Graph representation of the proposed AP placement algorithm.</figcaption></figure>

The presented graph-model of the AP placement scheme can be used to originate our task in a graph theory problem. Thus, our goal is to find the longest distance from the root, where the three receivable AP criterion is still fulfilled. On each level of the tree the number of removed APs is the same, therefore the deeper we are in the tree the less APs are needed to cover the served territory. The described “longest path” task is an NP-complete problem in graph theory [15].

Numerous heuristic optimization algorithms were developed to find the global optimum for NP-complete problems, like hill climbing, swarm intelligence, integer linear programming, simulated annealing, etc. For our case, we propose simulated annealing to approach the optimal AP locations for WLAN-based indoor positioning. Simulated annealing is a generic probabilistic algorithm for the global optimization problem. It tries to locate a good approximation to the global optimum of a given function in a large search space even for NP-complete problems.
Our above mentioned AP placement scheme can be extended with the simulated annealing algorithm to approach optimal AP setup(s). Hence, a previously removed AP can be added again with probability given in (5):

$$ \exp\left(-\frac{\Delta E}{T}\right), \qquad (5) $$

where ΔE stands for the difference of cost functions of the two neighboring AP setup states. The cost function is determined as the number of APs in the given state of the graph. Parameter T is called temperature and calculated as the sum of the number of sensed APs for each position on the map. The possibility of putting a previously removed AP back prevents the method from being stuck in a local minimum that is worse than the global one.

The main steps of the extended algorithm are summarized in the following pseudocode:

1. initialization (add all APs)

2. WHILE (counter>0)

3. Choose neighbor state randomly (add or remove AP)

4. CASE add

5. IF {random < exp(dE/T)} addAP()

6. CASE remove

7. removeAP()

8. IF {visibleAPs < 3} restoreAP()

9. counter=counter-1

Note, that our method does not guarantee that the global optimum will be found, but it can be still useful to plan the AP placement in WLAN-based indoor positioning systems. Another weakness of the method is that the AP coverage areas must be estimated using signal propagation models. As we saw above, numerous models were developed in the last decades, but neither of them is 100% realistic. Fortunately, in our solution the punctual received signal strength is not important, only the coverage area borders of an AP must be estimated accurately.

# 5 Evaluation

In order to evaluate the proposed, simulated annealing based algorithm we used simulations.

## 5.1 Simulation Environment

We have developed a simulation tool in MATLAB [3] environment. Our AP positioning algorithm relies on signal propagation models, therefore we implemented the above mentioned three different models, such as free-space, ITU indoor and Hata-Okumura. The signal absorption depends on the frequency, transmitter antenna gain, receiver antenna gain and transmitted power in all of the models. The default values
of these parameters we used in the analysis are 2.4GHz, 5dB, 2dB and 100mW, respectively.

Our aim was to create a general tool, so we made our simulator adaptable to different wireless technologies by allowing the adjustment of the parameters. The received signal strength can be estimated using the propagation models. However, if the RSS is too low, the access point is not sensed by the host and cannot be used for positioning purposes. In order to determine the AP coverage area, we have introduced the sensitivity parameter (-80dB) of a host. If the received signal strength is lower than the host sensitivity, the terminal is out of the AP's range.

Moreover, the simulated area (map) has to be loaded at the beginning of the simulation process. A .bmp image file can be used to determine the simulated environment by defining the rooms, walls, pillars, etc. The wall attenuation is also an adjustable parameter in our tool, what we set to 5dB.

In the simulator, not only the simulated annealing based algorithm was implemented, but a brute force method, too. In cases, when the number of possible AP positions is not too high the brute force method is a better choice providing always the global optimal solution.

## 5.2 Simulation Results

Due to space limitation we can present only a small subset of our simulation results. In our first simulation, we have compared the brute force and simulated annealing based method using the free-space signal propagation model to analyze the limits of the algorithms. The simulation time was measured in function of the number of possible AP positions (Fig. 3).

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Simulation time vs. number of possible AP positions in case of the brute force and simulated annealing algorithms.</figcaption></figure>
The result shows that the simulated annealing algorithm is scalable and the simulation time remains almost constant even if the number of possible AP positions is increasing. On the contrary, the brute force algorithm does not scale well and the simulation time increases exponentially, as expected.

Then, we investigated further our extended AP positioning algorithm based on simulated annealing in a 102x106m territory, where the possible AP locations are 30cm from each other. In this case, the number of possible AP locations is close to 120000. Moreover, we used the ITU indoor signal propagation model this time. The simulation time was about 2 minutes. The simulated annealing randomly chooses the neighbor states in the graph, therefore in case of several optimal solutions the resulted AP setup scheme can be different in consecutive simulation runs, even if the input parameters are the same. An output of the simulation is presented in Fig. 4 where the selected AP locations and the RSS of the access points are illustrated.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Selected AP locations and the RSS of the access points using our extended AP positioning algorithm based on simulated annealing. The colors represent the highest RSS in the given point.</figcaption></figure>

The ideal AP positions are highly influenced by the walls inside the indoor area due to the significant signal attenuation, therefore the map of the territory must be entered before running the simulations (the walls, illustrated by straight lines, are slightly visible in Fig. 4). In the presented result, 9 APs were enough to cover the territory by receiving the signal of at least three APs in each point of the map. We have iterated the simulation process in order to examine whether the resulted number of APs is always the same (we reached a global optimal) or it is changing due to the randomness of the simulated annealing algorithm (we reached a local optimal). We found that in most of the cases the algorithm's output was 9 APs, but rarely it gave 10 APs as a solution. We can conclude that the simulation must be repeated several times to find a global optimal solution with high probability.
# 6 Summary

In this paper, we investigated the issue of optimal placement of WLAN access points for indoor positioning. We proposed a simulated annealing based method to find the optimal solution of how to place the access points to receive the signal of at least three reference APs everywhere in the given indoor area, but keep the number of deployed APs as low as possible. Our method provides a solution, usually a global optimal one, nearly in constant time in realistic scenarios. Moreover, we have developed a simulation tool in MATLAB environment. In this tool, we implemented our algorithm together with several signal propagation models and analyzed the algorithm's behavior.

The developed simulation tool and our simulated annealing based algorithm can be useful in planning radio-based positioning systems not just focusing on WLAN technology. By minimizing the amount of required access points, the cost of deployment and the operation expenses can be reduced but still an efficient and accurate positioning system can be operated.

As future work, we plan to further investigate the performance and limitations of our algorithm. Moreover, we plan to collect real world measurements and compare them with our simulation results.

**Acknowledgments.** This work was supported by the BME-Infokom Innovátor Nonprofit Kft. Károly Farkas has also been partially supported by the Hungarian Academy of Sciences through the Bolyai János Research Fellowship.

# References

1. Liu, H., Darabi, H., Banerjee, P., Liu, J.: Survey of Wireless Indoor Positioning Techniques and Systems. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Review. vol. 37, no. 6, pp. 1067--1080 (2007)

2. Baala, O., Zheng, Y., Caminada, A.: The Impact of AP Placement in WLAN-based Indoor Positioning System. In: Proc. of Eighth International Conference on Networks (2009)

3. MATLAB and Simulink for Technical Computing, www.mathworks.com

4. Bahl, P., Padmanabhan, V.: RADAR: An in-building RF based user location and tracking system. In: Proc. of IEEE INFOCOM, vol. 2, pp. 775--784 (2000)

5. King, T., Kopf, S., Haenselmann, T., Lubberger, C., Effelsberg, W.: COMPASS: A Probabilistic Indoor Positioning System Based on 802.11 and Digital Compasses. In: Proc. of First ACM Intl Workshop on Wireless Network Testbeds, Experimental evaluation and Characterization (WiNTECH). Los Angeles, CA, USA (2006)

6. Youssef, M., Agrawala, A., Shankar, A.U.: WLAN location determination via clustering and probability distributions. In: Proc. of IEEE Int. Conf. Pervasive Comput. Commun., pp. 143-151 (2003)

7. Tummala, D., Akl, R., Li, X.: Indoor Propagation Modeling at 2.4 Ghz for IEEE 802.11 Networks. In: Proc. of The Sixth IASTED International Multi-Conference on Wireless and Optical Communications (2006)

8. Sandeep, A.R., Shreyas, Y., Seth, S., Agarwal, R., Sadashivappa, G.: Wireless Network Visualization and Indoor Empirical Propagation Model for a Campus WI-FI Network. World Academy of Science, Engineering and Technology, vol. 42 (2008)
9. Seybold, J.S.: Introduction to RF Propagation. John Wiley & Sons, Inc. (2005)

10.Lkhagvatseren. T., Hruska. F., Path loss aspects of a wireless communication system for sensors. International Journal of Computers and Communications. issue 1, vol. 5 (2011)

11.Chrysikos, T., Georgopoulos, G., Kotsopoulos, S.: Site-Specific Validation of ITU Indoor Path Loss Model at 2.4 GHz. In: Proc. of IEEE International Symposium (WowMoM) (2009)

12.Ranvier, S.: Path loss models. Helsinki University of Technology (2004)

13.Bose, A., Foh, C.H.: A Practical Path Loss Model For Indoor WiFi Positioning Enhancement. In: Proc. of 6th International Conference on Information, Communications & Signal Processing (2007)

14.Nadir, Z., Elfadhil, N., Touati, F.: Pathloss Determination Using Okumura-Hata Model and Spline Interpolation for Missing Data for Oman. In: Proc. of the World Congress on Engineering, vol. I (2008)

15.Karger, D., Motwani, R., Ramkumar, G.: On approximating the longest path in a graph. Algorithmica. vol. 18, no. 1, pp. 82--98 (1997)