Indoor localization using BLE beacons is valued for its energy eficiency, cost-efectiveness, 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, diferent greedy strategies for placing the beacons have varying efects on the optimization results. We propose a new optimization model that uses real-time training accuracy rather than RSSI coverage. Our model incorporates two diferent 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.
In recent years, many researches focus on indoor localization. Wi-Fi AP based method is frequently
evaluated for the devices exist in many workplaces [
Therefore, Bluetooth Low Energy (BLE) beacon based system has become a well-accepted method
[
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 [
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. CEUR
ceur-ws.org 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.
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 [
To overcome the need for a large number of devices, optimization based on signal strength has been
proposed [
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.
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.
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 efect of environment to the signal decay. They collect RSSI at the new candidate and Bayesian optimization is used to correct the diferences 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 [
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.
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.
In order to select the best beacon to add or remove, our work combines radio signal strength simulations with the data actually collected.
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.
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.
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 diferent greedy strategies that have their specific efect to the final result.
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.
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:
The greedy search aims to maximize the reliability area, thus the object function can be defined as: () = { 1 indoor() < 0 indoor() ≥
. ( ) = ∑ ().
=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 (2) (3)
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 [
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 ′ ← ∪ {} {Add the candidate beacon to the set}
′) {Calculate the reliability area} area ← ( if area > then ← area ← ′ end if 14: end for 15: for each beacon in do area ← ( if area > then ′ ← ∖ {} {Remove the beacon from the set}
′) {Calculate the reliability area} {Only if it is better than before} 8: 9:
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.
In this experiment, to ensure a fair comparison, the same initial state is set for diferent 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 efects 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 eficiency, we placed all beacons at once and collected data from all target points, as Fig. 3a and Fig. 3b. This difers 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 afect the efectiveness of the comparative approach. By acquiring more data points, our method allows for a more efective analysis of the accuracy diferences between the two methods.
We evaluate the methods by comparing the maximum reliability area produced by diferent 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 efective. (a) Point where the beacons are placed (b) Locations where data is collected
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-bestonly” 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 afects 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 ifngerprint 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.
(a) Reliability changes over number of beacons
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. (b) NRS (c) DRS 10 5 0 10 5 0 10 5 0 (a) Coverage maximization (b) Non-decision based (c) Decision based
Although both achieved better performance, the two proposed strategies are slightly diferent. 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 efect of the decision. To analyze the process of diferent 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. For NRS, we explored the efect of diferent parameter adjustments on the optimization results by using diferent 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 efects of larger KL choices on the previously placed beacons less apparent. In future experiments with a larger scale, we can verify this hypothesis.
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.