Incremental and Decremental Optimal BLE Beacon Placement for Accurate Indoor Localization Shiyuan Zhuang1,† , Koichiro Ohashi1,† and Masamichi Shimosaka1,† 1 Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8550 Japan Abstract Indoor localization using BLE beacons is valued for its energy efficiency, cost-effectiveness, and scalability. Optimal beacon placement is crucial for minimizing the number of beacons, improving accuracy, coverage area and reducing installation costs. Previous methods focused on signal coverage, which doesn’t necessarily ensure localization accuracy. Other approaches use greedy search algorithms to place the beacons through pre-defined evaluation functions. However, different greedy strategies for placing the beacons have varying effects on the optimization results. We propose a new optimization model that uses real-time training accuracy rather than RSSI coverage. Our model incorporates two different greedy placement strategies. Experiments using actual RSSI values show our approach outperforms previous methods by 10.9% on average, with our greedy strategies achieving a 4.5% average and 17.2% maximum improvement. Keywords BLE beacon, Sensor Placement Optimization, Greedy strategy design 1. Introduction In recent years, many researches focus on indoor localization. Wi-Fi AP based method is frequently evaluated for the devices exist in many workplaces [1]. However, Wi-Fi access points are designed for communication and not capable for relocation when the localization result is affected. Therefore, Bluetooth Low Energy (BLE) beacon based system has become a well-accepted method [2, 3]. BLE beacons are lightweight, cost-effective, and have outstanding energy-saving capabilities. Aside from their success in IoT system design, BLE beacons are expected to significantly increase the accuracy of indoor localization. To achieve the design mentioned above, BLE beacon placement has become a significant topic in this field. However, current approaches for optimizing placement are mainly based on signal coverage using radio signal strength [4, 5]. Although indoor localization via BLE beacons typically uses their Radio Signal Strength Information (RSSI) as input, full signal coverage does not necessarily lead to satisfactory indoor localization accuracy. Additionally, existing methods propose the strategy that place as many beacons as possible and then remove the unnecessary ones, but this approach is quite costly [6]. To address this issue, a flexible greedy placement strategy should be proposed. We proposed a new design for beacon placement optimization using a real trained deep neural network model and object function to evaluate accuracy at each step of optimization, instead of signal coverage area. BLE beacons are placed as transmitters and device to-be-localized as receivers. This approach leads to better decision-making during the greedy search process. Additionally, we proposed and discussed two new greedy placement strategies, which were compared with the traditional optimization methods that only involve adding beacons. The contributions of this study are as follows: • We proposed a leading method that use not only incremental but also decremental based greedy strategies. Our method is the first in the field to consider correcting localization accuracy by Proceedings of the Work-in-Progress Papers at the 14th International Conference on Indoor Positioning and Indoor Navigation (IPIN-WiP 2024) † These authors contributed equally. Envelope-Open zhuang@miubiq.cs.titech.ac.jp (S. Zhuang); ohashi@miubiq.cs.titech.ac.jp (K. Ohashi); simosaka@miubiq.cs.titech.ac.jp (M. Shimosaka) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings adding and then removing beacons. Compared to methods that only add beacons, our approach achieves better results. • Our method of using localization accuracy as evaluation of the placement is designed for and only for indoor localization, this lead to better performance compared with those considering only about signal coverage. 2. Related Work 2.1. Sensor Selection Based Optimization A fundamental solution of beacon placement optimization is by sensor selection, which is to start with placement of high density and remove the unnecessary sensors in order to limit the number of beacons. ZigBee [6] proposed by Shimosaka et al. uses such way of placing a large number of devices and remove some of them in order to achieve final optimization. However, this approach requires a considerable number of beacons to be placed in reality, which is not practical for real-world usage. Approaches using sensor selection techniques could lead to optimization, but the demand for a large number of devices has become a bottleneck in the application of this technology [7, 8]. 2.2. Signal Strength based Optimization To overcome the need for a large number of devices, optimization based on signal strength has been proposed [5, 9]. The common method for localization using BLE beacons is to use a signal attenuation model evaluated by RSSI to calculate the simulated distance between the target and the beacon. To localize the target, three detectable beacons are necessary. Considering this fact, some studies focus on maximizing the area that can be covered by three beacons. Y. Zhen et al. proposed a design where beacons are placed one after another by selecting the position that maximizes the coverage area [10]. However, this approach does not guarantee the accuracy of the localization. Does a larger coverage area mean better accuracy? It only shows that the area can be localized, so there is a lack of evidence to suggest an improvement in accuracy. 3. Problem setting and existing methods for Optimization focus on Accuracy 3.1. Accuracy-oriented optimization problem setting To simplify the description, we divide the room into several grids, each of which has a unique number and xy-coordinates. Given a set of beacons 𝐵 = {𝑏1 , 𝑏2 , … , 𝑏𝑛 } and a set of grids 𝑋, let the position of the 𝑖-th beacon 𝑏𝑖 correspond to the grid number 𝑙𝑖 , where 𝑙𝑖 ∈ 𝑋. Define a valid placement 𝑃 (𝑛) as the set of 𝑛 beacons, with their respective positions 𝑙1 , 𝑙2 , … , 𝑙𝑛 . The positioning accuracy of this placement is denoted as Acc(𝑃). Our problem becomes finding: 𝑃 ̂ (𝑛) = arg max Acc(𝑃 (𝑛) ) 𝑃 (𝑛) where 𝑃 ̂ (𝑛) represents the optimal placement of the 𝑛 beacons. 3.2. Placement Optimization by maximizing coverage Existing approach by Zhen et al. optimize beacon placement by adding beacons one after another to maximize radio signal coverage at each step. They use basic signal attenuation model to initialize a radio map by the following expression. Figure 1: Overview. In each iteration of greedy search, an additional part and a removal part is defined, thus we add or remove the beacons follow our designed greedy placement strategies. 𝑟 = 𝑟0 − 𝜂 log10 𝑑 (1) Where 𝑑 is the physical distance between target and the beacon. 𝑟0 is the radio signal strength at 1 meter distance from the beacon. 𝜂 refers to the effect of environment to the signal decay. They collect RSSI at the new candidate and Bayesian optimization is used to correct the differences between the radio map created with a small amount of data collection and the actual radio map, and then determine the next beacon placement location. By continuously collecting data and adding beacons, coverage area is maximized in the end. Moreover, Falque et al. proposed method maximizing coverage area with more than 3 beacons as well as maximize the distance of the near beacons as great as possible [4]. 3.3. Limitation of coverage area and adding beacons only Compared with beacon selection, the optimization method of incrementally adding beacons requires fewer devices but does not guarantee the quality of placement. Since these studies focus on maximize the coverage area, how does this coverage impact the localization accuracy remains unknown. As for Falque’s research, even a target is covered with more than 3 beacons does not mean the accuracy of localizing it will be improved. Also, they did not consider about removing beacons after putting them, so it is not flexible towards changes. In forward greedy search, incorrect selection may occur in the early stages of the search, and there is no means to correct this error later. 4. Incremental and decremental Placement Optimization Focus on High Accuracy Indoor Localization 4.1. Overview In our proposed incremental and decremental greedy search, the number of beacons will increase from the initialized number to required number. An additional part and a removal part are defined to decide the next beacon to add or drop from the existing beacon set. The procedure is shown in Fig. 1. The selection of the next beacon to add or drop is based on an RSSI-based indoor localization machine learning model. Current placement’s accuracy over all the targets will be obtained by the accuracy of the localization model, then we use decision function to select from the beacon position candidates. 4.2. Accuracy-oriented next-beacon decision In order to select the best beacon to add or remove, our work combines radio signal strength simulations with the data actually collected. 4.2.1. Based on distance RSSI simulation When a beacon’s placement is determined, we simulate placing a new beacon there and calculate the RSSI values for all targets using a distance-based simulation. An improved RSSI simulation techniques could further improve performance. Note that this simulation is not part of our main proposal. 4.2.2. Indoor localization model using BLE RSSI We trained a simple three-layer fully connected neural network as a localization model, with Rectified Linear Unit(ReLU) as the activation function. It takes the RSSI features from multiple beacons as input and outputs results over the entire location grid for localization. We chose a relatively simple model because model design is not the main contribution of this study. With better models to determine accuracy, our proposed method can be improved. Therefore, this localization model can also be replaced with other high-precision models. 4.3. Incremental and decremental greedy search strategies In this part, we proposed a special object function which uses the output of the localization model to help the greedy algorithm to decide which candidate to select. We also designed two different greedy strategies that have their specific effect to the final result. 4.3.1. Reliability Area To evaluate placement accuracy, various metrics such as total distance error and classification error have been proposed. We chose to use reliability area instead of positioning accuracy for two reasons. The first reason is that when a greedy strategy is executed based on average positioning accuracy, the greedy algorithm may further optimize areas that already have good accuracy, resulting in many areas that cannot be located at all with the same number of beacons. This contradicts the fundamental design objective of covering the largest possible area with high-precision positioning. The second reason is that previous studies have shown that the highest achievable indoor positioning accuracy using pure BLE beacons is around 3 meters (when beacon density is extremely high). Therefore, there is a bottleneck when optimizing based on positioning accuracy as a metric. Considering these reasons, we chose reliability area and defined it as the total area with an average positioning error of less than 5 meters, ensuring that optimization can continue. 4.3.2. Object function for greedy search Let 𝐹 (𝑃) denote the reliability area for placement 𝑃. The reliability area is defined as the proportion of the total area where the mean positioning error is within 5 meters. We set 𝑝 as a threshold. Therefore, we use 𝐹 (𝑃) instead of Acc(𝑃). A larger 𝐹 (𝑃) indicates a larger area that can be positioned with high accuracy. Let 𝑓indoor (𝑥) represent the positioning error for grid 𝑥, where 𝑥 is located at the coordinates (𝑠, 𝑡), 𝑥 ∈ 𝑋. We use the following formula to determine whether the grid can be positioned with high accuracy: 1 𝑓indoor (𝑥) < 𝑝 𝑓 (𝑥) = { . (2) 0 𝑓indoor (𝑥) ≥ 𝑝 The greedy search aims to maximize the reliability area, thus the object function can be defined as: 𝑋 𝐹 (𝑃) = ∑ 𝑓 (𝑥). (3) 𝑥=1 In one iteration, as shown in Fig. 2, the algorithm first produces candidates for new beacon positions, then simulates a new beacon to be placed at each position. The RSSI data of each grid is used as the Figure 2: Method of selecting beacon to be added. Algorithm 1 Non-decision-based removal strategy(NRS) 1: Define addBeacon(𝑃) that adds a new beacon to 𝑃 2: Define removeBeacon(𝑃) that removes a beacon from 𝑃 3: for i = 1 to K do 4: 𝑃 ← addBeacon(𝑃) 5: end for 6: for j = 1 to L do 7: 𝑃 ← removeBeacon(𝑃) 8: end for 9: return 𝑃 training dataset for the model, in which the new beacon’s data is simulated and the information of other beacons is obtained in reality. After training, we evaluate the accuracy of the model and calculate the objective function of the greedy search process. Finally, we select the candidate with the greatest function value as the new state and start another iteration. For the new beacon, we can use the data collection method given by Zhen et al in [10]. 4.3.3. Proposed greedy search strategies of different removal policy We proposed two strategies: a decision-based strategy and a non-decision-based strategy. In the decision-based strategy, if removing a beacon does not necessarily lead to a better result, we choose not to remove it and continue to add more beacons. The non-decision-based strategy, on the other hand, removes a fixed number of beacons at each iteration, with the number of beacons removed being less than the number added. We do not decide whether to remove beacons in the current step but leave the optimization task to the future greedy strategy. This means that even if some beacons are removed, if they are beneficial, the algorithm will add them back in the future. In the non-decision-based removal strategy (NRS) Algorithm 1, let 𝐾 be the number of beacons to be added in each iteration, and 𝐿 be the number of beacons to be removed. Note that 𝐾 > 𝐿. In each iteration, the algorithm firstly add 𝐾 beacons, then remove 𝐿 beacons. This forced removal ensure that the number of beacons will increase in every iterations until the number reaches 𝑁. In the decision-based removal strategy (DRS), after adding a new beacon, the algorithm decide whether to remove an existing beacon or not. Retrieval is performed only if the accuracy is better than the current placement (after addition). This actually means replace a former beacon with a new one to see if the accuracy can be improved. The algorithm is described in 𝐴𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚2. In the DRS algorithm, the first loop identifies the optimal position to maximize the reliability area. In the second loop, we attempt to remove beacons from the current setup, excluding newly added ones, to see if the reliability area improves. If replacing a beacon with a new position enhances performance, the beacon count remains the same. Otherwise, we add a new beacon, increasing the total count by one. Algorithm 2 Decision-based removal strategy(DRS) 1: 𝐹 (𝑃) calculates the reliability area for a given placement 𝑃 2: 𝑟 ← 0 {Initialize the maximum reliability area} 3: 𝑃𝑖 {Input placement from last iteration} 4: 𝑃 ← 𝑃𝑖 {Initialize the corresponding placement} 5: 𝑟𝑠 ← 𝐹 (𝑃𝑖 ) {Save the reliability area for last state} 6: 𝐶 {Set of all possible positions of the new beacon} 7: for each candidate beacon 𝑏 in 𝐶 do 8: 𝑃 ′ ← 𝑃𝑖 ∪ {𝑏} {Add the candidate beacon to the set} 9: area ← 𝐹 (𝑃 ′ ) {Calculate the reliability area} 10: if area > 𝑟 then 11: 𝑟 ← area 12: 𝑃 ← 𝑃′ 13: end if 14: end for 15: for each beacon 𝑏 in 𝑃𝑖 do 16: 𝑃 ′ ← 𝑃𝑖 ∖ {𝑏} {Remove the beacon from the set} 17: area ← 𝐹 (𝑃 ′ ) {Calculate the reliability area} 18: if area > 𝑟𝑠 then 19: {Only if it is better than before} 20: 𝑟𝑠 ← area 21: 𝑃 ← 𝑃′ 22: end if 23: end for 24: return 𝑃 5. Experiment Our experiment compares our proposed method with an existing optimization method that uses greedy search and only adds beacons. Additionally, we compared our indoor localization accuracy-oriented method with a previous approach based on radio signal coverage area to demonstrate our advantages in improving accuracy. 5.1. Experiment settings 5.1.1. Initialization In this experiment, to ensure a fair comparison, the same initial state is set for different methods, placing three beacons in an equilateral triangle centered at the center of the experimental area. The three methods will then start their optimization based on this initial state. 5.1.2. Dataset In the experiment, we use RSSI simulation data from a previous experiment and actual RSSI data collected on the 4th floor of a building. When adding a new beacon, the RSSI of the existing beacons are from actual collected dataset, but that of the new beacon is not obtained yet. We use RSSI simulation based on distance for this case. However, this approach does not account for the effects of walls and structures in the indoor environment. Since new data will be collected after the placement, we do not consider this issue to be critical. Also, we collect actual data in our building by placing beacons and we use Mac Book Pro to collect RSSI value of the beacons. For each data collecting point we collect data from each beacon 20 times over 2 days and use the average value as our obtained data. For BLE beacons, we set txPower as 0dBm, beacon rate as 1/100ms. To improve data collection efficiency, we placed all beacons at once and collected data from all target points, as Fig. 3a and Fig. 3b. This differs slightly from the data collection method used in Zhen’s method, our comparative approach, where only partial data was collected after placing each new beacon. Our current data collection method does not affect the effectiveness of the comparative approach. By acquiring more data points, our method allows for a more effective analysis of the accuracy differences between the two methods. 5.1.3. Comparison We evaluate the methods by comparing the maximum reliability area produced by different placement schemes with the same number of beacons. A larger area indicates a greater region where high-precision localization can be achieved, implying that the current placement scheme is more effective. (a) Point where the beacons are placed (b) Locations where data is collected Figure 3: Beacon placements and data collection points 5.2. Evaluation of incremental and decremental beacon placement In this part, we compare our method with optimization based on coverage maximization. Fig. 4a shows the comparison result. The vertical axis represents the reliability area, indicating the proportion of the total area where the mean positioning accuracy is higher than 5 meters. The horizontal axis represents the number of beacons. ”Inc-only” refers to the greedy strategy of only adding beacons. ”inc_dec-best- only” refers to the strategy of DRS, which decides whether to remove beacons. ”coverage_maximization” refers to the method proposed by Zhen et al., which aims to maximize the coverage area. ”inc_dec_K5L4” represents the strategy of NRS, where in each iteration, 5 new beacons are added and 4 beacons are removed, resulting in a net increase of one beacon per iteration. Since the first three beacons are initialization beacons, we do not count their accuracy. When the number of beacons reaches 10, all areas in our experimental environment are already covered, causing the algorithm by Zhen et al. to stop iterating. Therefore, the yellow line in the graph does not show significant changes after the number of beacons exceeds 10. From Fig. 4a, it is obvious that our proposed method achieved a better reliability area when the number of beacons is the same as in the approach using coverage area. We assume that high coverage does not necessarily lead to high indoor localization accuracy. From Fig. 5a, we can see that to maximize coverage, the beacons are placed mostly near the hallway at the center of the experimental area. Since the width of the area is not very large, a beacon near the hallway might be able to cover an area from top to bottom. However, this results in poor signal strength at the corners and edges of the room. Additionally, to maximize coverage, some beacons are placed too close to each other, making the radio signals from these beacons very similar, which negatively affects localization accuracy. As for our method, as seen in Fig. 5b and Fig. 5c, the beacons are generally distributed throughout the entire space, with considerable distances between them. This distribution allows for a more distinctive fingerprint map, as our optimization is guided by model accuracy. With the same number of beacons, our method achieved accuracy improvements ranging from 6.8% to 28.8%, with an average improvement of 10.9%, compared to the method by Zhen et al. The experimental results indicate that our accuracy-guided optimization method achieved better performance. (b) NRS (a) Reliability changes over number of beacons (c) DRS Figure 4: Combined evaluation of different strategies. Additionally, compared to the previous methods that only incrementally add beacons, our method achieved a maximum accuracy improvement of 17.2% and an average improvement of 4.5%. Although there is a possibility of negative optimization in the early stages, as the number of beacons increases, the advantage of our method becomes more apparent because the previous method cannot remove unsuitable beacons from the early stages. Thus, it is found that compared to the greedy strategy of only adding beacons, our proposed strategy achieves a certain accuracy advantage. 10 10 10 5 5 5 0 0 0 (a) Coverage maximization (b) Non-decision based (c) Decision based Figure 5: The placement results for the three methods when the number of beacons is equal to 10. 5.3. Analysis of two greedy strategies Although both achieved better performance, the two proposed strategies are slightly different. NRS uses fixed number for adding and removing in each iteration, while DRS will decide whether to remove a beacon or not. In this part, we will discuss about the effect of the decision. To analyze the process of different algorithms, we plotted the curve of the number of beacons with the change in the number of iterations and the curve of the reliability area in Fig. 4b and Fig. 4c. For the non-decision based Algorithm(NRS), we use K2L1 as an example. The number of beacons increases steadily: for every two beacons added, one is removed. This results in a stable increase in the number of beacons. However, the improvement in the reliability area is less stable. Below 10 iterations, the reliability area rises rapidly because adding new beacons quickly expands localization area. Beyond 10 iterations, the rate of increase slows but continues as new beacons improve localization accuracy within the existing coverage. For DRS, since beacon removal is optional but addition is mandatory each iteration, the number of beacons increases more rapidly compared to NRS. The reliability area curve is similar to NRS but more stable in certain areas. DRS reaches the final target of 20 beacons in fewer iterations. By making removal optional, we accelerate growth during the rapid beacon increase phase and focus on adding beacons, while during the optimization phase, we focus on replacing beacons. This explains the superior performance of the decision-based strategy. 5.4. Discussion For NRS, we explored the effect of different parameter adjustments on the optimization results by using different K and L, including K2L1, K3L2, K4L3, and others. There was no significant improvement in the optimization results. We believe this is because the current total number of beacons is limited, making the optimization effects of larger KL choices on the previously placed beacons less apparent. In future experiments with a larger scale, we can verify this hypothesis. 6. Conclusion We propose a BLE beacon placement optimization method that focuses on indoor localization accuracy with incremental and decremental strategies. We evaluate the performance through experiments using actual collected data. Experiments show that, compared to methods that simply add beacons or maximize coverage, our method achieves a wider range of high-precision localization with the same number of beacons. References [1] M. Sugasaki, M. Shimosaka, Robust indoor localization across smartphone models with ellipsoid features from multiple RSSIs, Proc. ACM Interact. Mob. Wearable Ubiquitous Technol(IMWUT). 1 (2017). URL: https://doi.org/10.1145/3130968. doi:10.1145/3130968 . [2] M. Kwak, Y. Park, J. Kim, J. Han, T. Kwon, An energy-efficient and lightweight indoor localization system for internet-of-things (IoT) environments, ACM Interact. Mob. Wearable Ubiquitous Technol(IMWUT). (2018). URL: https://doi.org/10.1145/3191749. doi:10.1145/3191749 . [3] A. Jiménez, F. Seco, P. Peltola, M. Espinilla, Location of persons using binary sensors and BLE beacons for ambient assitive living, in: Proc. 2018 International Conference on Indoor Positioning and Indoor Navigation (IPIN), 2018. doi:10.1109/IPIN.2018.8533714 . [4] M. P. R. Falque, J. Biehl, Optimizing placement and number of RF beacons to achieve better indoor localization, in: Proc. 2018 IEEE International Conference on Robotics and Automation (ICRA), 2018. doi:10.1109/ICRA.2018.8460202 . [5] C. Zhang, D. Yankov, S. Shapiro, W. Wu, An end-to-end beacon placement optimization system for indoor positioning, in: Proc. 2021 International Conference on Indoor Positioning and Indoor Navigation (IPIN), 2021. doi:10.1109/IPIN51156.2021.9662619 . [6] M. Shimosaka, O. Saisho, T. Sunakawa, H. Koyasu, K. Maeda, R. Kawajiri, ZigBee based wireless indoor localization with sensor placement optimization towards practical home sensing, in: Proc. Advanced Robotics, 2016. doi:10.1109/IPIN54987.2022.9918130 . [7] C. Schaff, D. Yunis, A. Chakrabarti, M. R. Walter, Jointly optimizing placement and inference for beacon-based localization, in: Proc. 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2017. doi:10.1109/IROS.2017.8206574 . [8] X. Shen, P. K. Varshney, Sensor selection based on generalized information gain for target tracking in large sensor networks, IEEE Transactions on Signal Processing 62 (2014). doi:10.1109/TSP. 2013.2289881 . [9] D. Moreno-Salinas, A. M. S. Pascoal, J. A. Almansa, Optimal sensor placement for multiple target positioning with range-only measurements in two-dimensional scenarios, Sensors (2013). URL: https://api.semanticscholar.org/CorpusID:13490315. [10] Y. Zhen, M. Sugasaki, Y. Kawahara, K. Tsubouchi, M. Ishige, H. Murakami, M. Shimosaka, Efficient adaptive beacon deployment optimization for indoor crowd monitoring applications, Proc. ACM Interact. Mob. Wearable Ubiquitous Technol. 6 (2023). URL: https://doi.org/10.1145/3569462. doi:10. 1145/3569462 .