Finding by Counting: A Probabilistic Packet Count Model for Indoor Localization in BLE Environments
Subham De Shreyans Chowdhary Aniket Shirke Yat Long Lo Robin Kravets Hari Sundaram















  University of Illinois at Urbana-Champaign
  
  Urbana
  Illinois
  61801

de5@illinois.edu



  University of Illinois at Urbana-Champaign
  
  Urbana
  Illinois
  61801

shreyanschowdhary2@gmail.com



  IIT Bombay
  
  Mumbai
  India
aniket8897@gmail.com



  University of Illinois at Urbana-Champaign
  
  Urbana
  Illinois
yllo2@illinois.edu



  University of Illinois at Urbana-Champaign
  
  Urbana
  Illinois
  61801

rhk@illinois.edu



  University of Illinois at Urbana-Champaign
  
  Urbana
  Illinois
  61801

hs1@illinois.edu

















We propose a probabilistic packet reception model for Bluetooth Low Energy (BLE) packets in indoor spaces and we validate the model by using it for indoor localization. We expect indoor localization to play an important role in indoor public spaces in the future. We model the probability of reception of a packet as a generalized quadratic function of distance, beacon power and advertising frequency. Then, we use a Bayesian formulation to determine the coefficients of the packet loss model using empirical observations from our testbed. We develop a new sequential Monte-Carlo algorithm that uses our packet count model. The algorithm is general enough to accommodate different spatial configurations. We have good indoor localization experiments: our approach has an average error of ∼ 1.2m, 53% lower than the baseline range-free Monte-Carlo localization algorithm.




















































Finding by Counting: A Probabilistic Packet Count Model for Indoor Localization in BLE Environments
    Hari Sundaram
    December 30, 2023
===================================================================================================






§ INTRODUCTION



In this paper we develop a probabilistic model for Bluetooth Low Energy (BLE) packet reception within an indoor environment. Then, as a test application, we use the packet reception model for indoor localization. We expect Indoor localization using BLE to play an important role in future retail experiences, facilitating automated checkouts and targeted advertisements.
The importance of developing a packet reception model is two-fold: novel indoor localization techniques; network simulations. First, techniques for indoor localization fall under two camps: Received Signal Strength (i.e. energy loss models) fingerprinting, and range free models that avoid using RSS indicators. We know that RSS indicators to be unreliable—they vary with human presence, presence of obstructions and affected by multi-path loss. Range free models in contrast assume that a heard beacon is within a known distance threshold. A packet reception model allows us to localize based on packet counts without making assumptions on RSS or distance thresholds. Second, a packet reception model would serve as an alternative to RSS based packet models used in network simulators such as NS3.

Our main contributions are a new BLE packet reception model for indoor environments and a sequential Monte-Carlo localization application of the proposed model.  We model the probability of reception of a packet as a generalized quadratic function of distance, beacon power and advertising frequency. We obtain extensive empirical data by conducting experiments varying beacon power and frequency in an experimental testbed with stacks to dampen packet reception. Then, we proposed a Bayesian formulation to determine the coefficients of the packet loss model using the empirical observations. We develop a new sequential Monte-Carlo algorithm that uses our packet count model. The algorithm is general enough to accommodate different spatial configurations.

Our experiments on indoor localization reveal that our proposed approach works well: it has an average error of ∼ 1.2m which is 53% lower than the baseline Monte-Carlo Localization algorithm.  Our localization errors within an aisle are even better at ∼ 0.4m, with the increased errors arising due to the transition.


In the next section, we discuss related work. Then, in <Ref>, we formally define the two problems that we solve. In <Ref>, we introduce solutions to both estimating the packet reception model, and indoor localization using packet counts. In <Ref>, we discuss testbed set-up, collect empirical data and conduct localization experiments. We present our results in <Ref> and conclude in <Ref>.


































§ RELATED WORK



Now we discuss prior work related to wireless propagation models and indoor localization. Propagation models deal with loss in energy of radio waves between sender and receiver. Localization models track mobile nodes in an environment using seed nodes with known locations.


There is prior work on modeling the loss in energy during transmission for wireless signals like Wi-Fi, Bluetooth. The Received Signal Strength (RSS) i.e energy of received signal varies due to factors like distance, obstruction, walls, multi-path fading in indoor environment. <cit.> provides a detailed analysis of all these factors. Deterministic models like the Friis propagation model <cit.>, Log Distance Path Loss <cit.>
give a fixed RSS value based on distance. Stochastic models like Jakes model <cit.>, two-parameter Nakagami distribution
<cit.>
capture the uncertainty in received RSS values.








A wide range of techniques exist to localize a node within an indoor environment. All these techniques involve installing seed nodes in the environment with known prior location and then localizing other nodes relative to these seed nodes. These systems vary—the measuring capability of nodes, the nature of environment (i.e indoor/outdoor), and the mobility of nodes. Range-Based techniques involve the use of specialized and expensive hardware to measure some quantity which is then translated back to distance. GPS uses Time of Arrival (TOA) technique. <cit.> proposed the use of Time Difference of Arrival (TDOA) technique. Received Signal Strength based ranging techniques like SpotOn <cit.> are cheaper but inaccurate. RSS values in indoor environments becomes uncertain due to random factors like multi-path loss, fading and shadowing effects<cit.>. WiFi RSS fingerprinting based methods try to mitigate this problem of inaccuracy, but require expensive human labor. <cit.> gives a detailed survey of all such methods.

Range free techniques do not use special hardware, but rather make assumptions on certain properties of node movement and signal propagation. Monte Carlo Localization (MCL) <cit.> , Mobile and Static sensor network Localization (MSL) <cit.>, Weighted MCL <cit.> use previous location estimate and current observations to find present location of moving nodes. They assume that a heard beacon must be within a threshold distance to the current measurement location.

Our framework does not calculate RSS loss for each packet, or make any assumptions about beacon distance. Instead, we model the probability of receiving a packet, and use this probability for localization. Next we will formally define our problem and then discuss the entire solution architecture.



















§ PROBLEM DEFINITION



Our broad goal in this work is two fold—finding a model of packet reception rate in a Bluetooth Low Energy (BLE) Internet of Things (IoT) retail store like environment and then use the model to localize individuals.

We assume that we are in a rectangular W × L space comprising stacks.

We have k BLE beacons in fixed, known positions in the space. All beacons transmit at the same frequency f and at the same power r. Further, we assume that at any location (x,y), the probability of receiving packets from any beacon is binomially distributed with parameter p. In other words, the probability of receiving m packets when we send N packets is: m ∼B(N, p).



 §.§ Packet Reception Rate


We aim to discover how p, the probability that we would hear a packet from a beacon varies as a function g of distance (d), frequency (f) and Power (r). That is p = g(d, f, r). Additionally g will vary based on number of intermediate stacks between beacon and packet reception location.







One can consider our probabilistic packet counting model to be a hybrid of the RSSI model and the models used in range free localization. Energy loss models
 
<cit.> <cit.> are attractive in that they model the signal attenuation in the physical world. Prior work <cit.> also shows that packet RSSI is highly unpredictable in indoor environment and varies with the environment layout. Existing range free models assume a spherical zone of hearing for the packets <cit.> assuming that if we hear a beacon, it must be in this zone. In contrast, we make no assumptions about distance when we hear a beacon.














 §.§ Localization



Now, we list our assumptions for the localization problem. Assume that we have an individual moving in our hypothetical retail store, possessing a device that listens to the BLE beacons. This may be a smartphone, and the retail store application running on the smartphone is logging the BLE packets and then sending them to the cloud for analysis. Assume further than we would like to track the individual every δ sec. Finally, we assume stable store layout—beacon and stack locations don't change while the individual is moving.

Without loss of generality, assume that the smartphone application listens to the packets creates the following log

    L = { (b_1,t_1), (b_2,t_2), …,  (b_N,t_N) }

where b_i refers to the BLE beacon  heard at time t_i. The goal is to determine a list of locations XY_δ={x_i, y_i; δ}, at a store determined time resolution δ such that we know the location every δ sec.

Having presented the problems for determining packet reception and localization, we now discuss potential solutions.

























§ SOLUTION ARCHITECTURE



In this section we first show how to determine the probability of receiving a packet as a function of distance, frequency and power. Then, we present a solution to the problem of tracking individuals through the retail location using the packet reception model. Common to both approaches is a Bayesian formulation of the problem.



 §.§ Estimating the packet reception model



First, we solve the problem of determining the free space packet reception model—the case when stacks are present will follow in a straightforward manner.

To determine the packet reception model,  we assume that we know the ground truth location of any spot where we listen to the beacons. Since we know the ground truth locations of all the k beacons, we can calculate distance from the spot to each of the beacons heard at the spot. Assume that there exist N such spots. Thus at any location l_i,   i ∈{1, …, N }, we have a list D_i containing the number of packets of every beacon heard at l_i.  That is, D_i = {(b_j, c_j),   j ∈ 1, …, k }, where c_j is the count of beacon b_j.

We make a simplifying assumption about g(d, f, r).  We assume g to be an exponential function of the variable and that the log of the probability log p is quadratic in the variables. More formally:

    log p = b_0 + ∑_i b_i x_i + ∑_i, j b_i, x_i  x_j,    i, j ∈{1, 2, 3}

where, x_i refer to the variables of d, f, r.

Since power (f) and power (r) are constant for a specific configuration,  <Ref> reduces to a quadratic equation in distance (d). That is,

    log p = b_0 + b_1 d + b_2 d^2

The more general formulation of  <Ref> essentially states that the coefficients b_0, b_1, b_2 of  <Ref> regress in frequency (f) and power (r). Thus the more general form allows us estimate the packet reception model for a variety of beacon power and beacon frequency configurations.

We can use Maximum Likelihood (ML) estimation via least squares to estimate the coefficients b_i.  We can assume that at any one of the N locations, the probability p_i of receiving the i-th beacon is:

    p̅_̅i̅ = c_i/f ∗δ,

p̅_̅i̅
where, c_i is the number of packets received, f is the number of packets sent per second and δ is the time window of observation. Then we can estimate b_i from  <Ref> through least squares regression. The major challenge is that for low frequencies (e.g. f = 1Hz) or low power (e.g. -20db) we may not receive enough packets for a stable ML estimate of the coefficients.

A Bayesian formulation allows us to quantify the uncertainty in the coefficient estimates; when the number of packets received is large, the ML estimates and the Bayesian estimates of the coefficients will agree.

Let θ≡{ b_i} be the set of coefficients that we plan to estimate. Then the goal is estimate P(θ| D), where P(θ| D) ∝ P(D |θ) P(θ). D refers to the observed data—the number of packets heard for every beacon, at every location.

To set up a Bayesian formulation, let us view packet reception through the lens of a generative process. Assume that we are at a particular spot A, listening to the i-th beacon. Then the number of packets received c_i is drawn from a binomial distribution:

    c_i    = B  (N, p_i)
    
        p_i    = g(f, r, d_i,A)


where the probability p_i of receiving a packet from the i-th beacon is a function of frequency, power and the distance between the spot A and the location l_i of the i-th beacon. To formulate the priors P(θ), we assume that the prior of each of the coefficients b_i is drawn from independent and identically distributed Normal distribution.  That is,

    b_i ∼𝒩(μ, σ),

where we set μ=0 and σ=10 so that the priors are conservative, allowing for a large range of values.
The Bayesian formulation is compactly summarized in  <Ref>.
We compute the posterior P(θ| D) using a standard Markov Chain Monte Carlo technique.



We can use the same formulation for the free space case and the case when there are stacks. At each location, we filter the packets based on the beacon  allowing us to separately analyze the different cases since we know the ground truth location of the beacons and we know their distances to the location where we are making the measurement.


































 §.§ Estimating location sequence



We use Bayesian formulation for determining the location of a person in a store. We plan to use the layout of the space to impose constraints on the solution.



Let us begin with what is observable. As before, at any location, the observations include the packet counts from each beacon. We do know the ground truth locations of each beacon, the frequency (f) of transmission and the power (r).

Now due to the results of  <Ref>, we know the parameters of the packet reception model.

For any location, we need to estimate  hidden parameters. First, since we don't know the location, we don't know the location of any of the beacons relative to the current position. We do not know, when we receive packets from the i-th beacon, if the i-th beacon is in the same aisle, or one or more aisles away. Thus the number of aisles between the current location and any beacon is a latent parameter for that beacon. The speed s at which a person moves through the store is a latent variable. We can assume an upper bound for the speed.

Now, we describe the movement model. Let us assume as before that we wish to estimate the true (x,y) values at N locations, where the N depends on  the temporal resolution at which the retail store wishes to track its customers. The basic movement model assumes the following priors:

    s_i    ∼ U(0, S_max),   i ∈{1, …, N-1 }
    
        x_0    ∼ U(0, W),
    
        y_0    ∼ U(0, L),
    
        x_i| x_i-1   ∼𝒩(0, s_i-1*δ),   i ∈{1, …, N-1 }
    
        y_i | y_i-1   ∼𝒩(0, s_i-1*δ), i ∈{1, …, N-1 } .




Where, s_i refer to the speed between locations, and uniform prior until some speed S_max, (x_0, y_0) are the initial (x,y) locations of the person, and since we know little about them, we assume that they are uniformly distributed over the space. We assume that an intermediate location (x_i, y_i) is Normally distributed around (x_i-1, y_i-1) with a standard deviation equal to s_i-1 * δ, where s_i-1 is the speed with which the person left the previous location (x_i, y_i) and where δ is the time window of observation.

To estimate the location of the beacon relative to the measurement location, we make use of the layout of the space. We arrange our beacons in regularly spaced intervals on stacks. The beacons on the two sides of an aisle form a group. In  <Ref>, beacon numbers [1-12], [13-36] and [37-60] form three groups. All beacons in the same group must be an identical number of stacks away from the current location. Thus all beacons in the same group will use the same packet reception model. In our layout, the packet reception model used for a beacon group will depend on the y coordinate of the person. We can model the decision to switch as follows:

    τ_i    ∼ U(0, L),   i ∈{1, 2}
    
        A_i    = 
        0    y_i < τ_1,
    
        1   τ_1 ≤ y_i ≤τ_2, 
    
        2    y > τ_2, 
    
        S_i,k   = M(A_i, b_k).


Where, τ_i are two latent variables with a uniform prior along the y direction;  <Ref> helps us determine the estimate of the current aisle A_i and M is a deterministic mapping of the relative number of the stacks S_i,k between the current location i and beacon k. We can do this mapping because we know the store layout. The variable S_i,k helps us determine the appropriate packet reception model.

We estimate parameters θ≡{{x_i, y_i }, {s_i}, τ_i }.  The data collected D over all locations include the packet counts { c_k} of each beacon b_k within each time window. Notice that since we estimate S_i,k the number of stacks between beacon k and current location i, we use the following relation:

    c_i,k   = B(M, p_i,k),   M= f * δ,
    
        p_i,k   = g  (f, r, d_i,k;   S_i,k),
    
        d_i,k   = √((x_i - b_k,x)^2 + (y_i - b_k,y)^2).


Where, the packet counts c_i,k of the k-th beacon at location i is Binomially distributed with parameter p_i,k. We obtain the parameter p_i,k using the correct packet reception model, by using the estimate of the number of stacks S_i,k between location i and location of beacon k. The distance between the location i and location of beacon k denoted as (b_k,x, b_k,y) is the standard Euclidean distance.

Our goal is to estimate P(θ| D) ∝ P(D |θ) P(θ). We use a standard MCMC framework to estimate P(θ| D).

What if the store geometry was not so simple to use the two latent random variables τ_i?. We can formulate the number of stacks between the beacon and the location in a more general way using a Dirichlet ditribution as a prior:





    q_i,k   ∼Dir(α)
    
    S_i,k   ∼Cat(q_i,k)




Where we use a symmetric Dirichlet distribution with parameter α=1; We draw a three dimensional distribution q_i,k from the Dirichlet, for each location i and for each beacon k corresponding to the probabilities that there is either no stack, or one stack or  two stacks respectively, between beacon k and location i. We would use probabilities q_i,k to then draw from a categorical distribution. We did not use this formulation, since in our case we could exploit geometric constraints.

In this section we presented a solution to estimating the packet reception model and then showed how to use that model in locating an individual as she walks in a retail environment. A Bayesian formulation is central to solving both problems. In the next section, we discuss how we gathered empirical data to develop our packet reception model model and how we use the developed model to locate the individual.






































































§ EXPERIMENT DESIGN



In this section we will describe the three steps of carrying out the real world experiments—setting up the devices (<Ref>), the experimental testbed (<Ref>) and data collection (<Ref>).



 §.§ Device Set-Up



First we discuss three device types used in our testbed — Bluvision iBeeks, BluFi, TI packet sniffer.

iBeeks send out bluetooth low energy (BLE) packets into the environment and act as seed nodes of location. We choose these particular beacons because of their battery capacity, transmission power range and high advertising frequency. Their batteries last for a long time ranging from three to nine years. They support a wide range of broadcasting power from -40 dBm to +5 dBm. -40 dBm translates to 3 meter line of sight range, while +5 dBm gives us a range as large as 150 meter. We test the impact of range of sight on localization accuracy in our experiments. The beacons advertise packets as fast as one per 100 milliseconds. iBeeks are installed on particular locations in the environment and they remain stationary throughout the experiment. As their locations are known to us, they act like seed nodes based on which the location of other nodes are estimated.

BluFi enables mass re-configuration of iBeeks. To test the effects of frequency and power on packet reception rate, we need to re-configure the beacons at regular intervals. Bluzone app allows us to talk with single iBeek at a time. BluFi pushes new configurations to thousands of beacons with one single command from the Bluzone cloud.

Thus this device proves to be essential in large scale BLE beacon deployments.

Texas Instrument Packet Sniffer scans BLE packets sent out by iBeeks and also act as the node for which we want to estimate the location. iBeeks broadcast on three different channels and the packet properties vary a lot based on the channel.

The sniffer is a CC2540 dongle developed by Texas Instruments that can capture BLE packets on one advertising channel. The packets captured can be shown in real time by the Smart RF Packet Sniffer Software.
 
 The sniffer connected to a Windows laptop is kept at fixed locations during the training phase to collect the beacon packet trace. We walk around with the sniffer during the test phase to collect movement traces.




 §.§ Environment Set-Up



Now we will report on two environments that constitute our testbed—Undergraduate Library (UGL) and Grainger Engineering Library at the University of Illinois at Urbana-Champaign. Both environments are subareas of a library floor. They have book shelves segregating the floor into aisles and corridors. We chose to experiment in library spaces since we didn't have ready access to retail locations; we hope to perform future experiments in actual retail stores. The floor plan is like retail stores where we have stack of items. The two environments differ: presence of walls, different kinds of obstructing materials.

We do the training phase of the experiment at the UGL. This phase involves collecting of packet trace data at different locations. We  estimate the packet reception model parameters using empirical data collected at this location. Aisles between shelves provide free space and they are 1.22 meters wide. We use two bookshelves, each 0.64 meters wide and 17 meters long. On each aisle, we place two rows of 16 beacons on the two shelves facing the aisle. The inter-beacon distance on the same row is 1 meter, while the inter-beacon distance for beacons on the same shelf, but on different aisles is 0.64 meter i.e the thickness of the book shelf. The shelves are made of wood. We collect the packet traces in the aisles.

The testing phase takes place at the Grainger Library. This phase involves using the packet reception model to localize a moving person in the space. The Grainger environment differs from the training phase location in three  aspects. First, there are steel bookshelves as opposed to wooden shelves in UGL. Second, there is more open space on either side of boundary shelves as opposed to a more closed feature with walls on either side in UGL. We expect the effects of multi-path fading to be different. Third, this particular region has high foot traffic people in contrast to the training location where foot traffic was low. This will help us study the impact of dynamic human presence on localization.

The testing location differs in number of stacks, length and width of the aisle. Each stack is 11 meters long and 0.5 meters wide. The environment comprises three such stacks. Aisles are 0.7 meters wide. We place two rows of 12 beacons on each stack. The inter-beacon distance on the same row is 0.91 meter, while the inter-beacon distance for two devices kept opposite each other on the same shelf, but facing two different aisles is 0.43 meter.































 




 §.§ Data Collection



We collect two types of data at different power and frequency—beacon packet trace required for training the packet reception model and movement trace to test the utility of the packet reception model in localization.

We collect beacon packet traces during the training phase while standing at fixed spots in the layout. Since the distance calculations have to be exact, we do not introduce mobility in this step.

The broad steps for this phase are the following.


  * Placing the beacons on the shelves at regular intervals.

  * Using BluFi to re-configure the beacons to desired parameter settings (power, advertising  frequency).

  * Collecting the packet trace for current beacon configuration at three fixed locations per aisle. Two locations chosen near the two ends of each aisle and one in the middle.

  * Repeating Steps 2 and 3 until all the desired parameter settings are covered.




We collect movement trace in the testing phase by carrying out a modified random waypoint mobility model. This trace data contains two parts—packet trace heard during movement and actual ground truth locations. Obtaining actual locations while moving becomes is a challenge. We address the challenge by carrying out a random waypoint like movement model in real world with one modification: we fix in advance all the destinations while introducing movement randomness. Stop locations marked in  <Ref> act as destinations. We start moving from one end aisle and finish in the other.  <Ref> shows the exact movement sequence at the testing location starting from stop location 1 and ending at 9. Like a waypoint model, the speed of movement remains random since an actual person is doing the movement. The pause time after reaching each destination is also randomly chosen between 8 seconds and 10 seconds. We collect the movement trace for all beacon parameter settings. After one round of movement we use BluFi to re-configure all the beacons.







§ RESULTS



In this section we estimate the packet reception model parameters in <Ref> and the localization using the packet reception model in <Ref>.


 §.§ Inferring the Noise Model



The variables affecting the packet reception rate are distance, frequency and beacon power. We measure distance, represented as (d), in meters and frequency, shown as (f), in Hertz (Hz). 1Hz advertising frequency represents a time interval of 1 sec between each packet. We represent beacon power in dBm. Since dBm is a relative figure, we use -12dbm as a reference to compute the parameters in our model. Our reference power of -12dBm translates to a 10-12m beacon hearing range.









We collect data at three values each for device parameters of frequency and power. We use frequency values of 1Hz, 2Hz and 10Hz. High frequency of 10Hz helps us to check the effect of high packet emission rate on the noise or confusion in the medium. Such noise in turn can lead to lower reception rate. We set beacon powers at values -20db, -15db, -12db. -12db gives us a large range of 10-11 meters which  almost covers our entire experiment layout. -20db covers a much smaller range of 3-4 meters. We carried out experiments and collected data at all nine possible combinations of these two parameters.
















































We estimate the posterior P(θ| D) using PyMC3 a standard MCMC package <cit.>. We estimate θ (parameter values b_i of <Ref>) by using the entire dataset that includes all nine combinations of frequency and power.
 <Ref> shows the distributions. The plot shows that the distribution for all the coefficients have converged.
Taking the mean estimates of the posterior distributions of each parameter, the model for  log p_0 the log of the free space packet reception probability:

    log p_0 = -0.101 - 0.012f + 0.056r -0.272d + 0.189rd

The mean of the coefficients of d^2, r^2, f^2, f· d are close to zero and ignored.

 <Ref> shows the free space model fit to the raw data for all nine combinations of power and frequency. The dots show the raw packet counts received at varying distance while the curves represent the Bayesian fit. We can see from the figure that increasing power increases the packet reception probability and that decreasing frequency increases packet reception due to decreasing packet interference.















Now we infer a stack model where the process of estimation remains the same, but we filter the data points such that there is obstruction present between the device and receiver.

Figure <ref> shows a comparison of the different stack models for a fixed frequency of 10Hz. One stack and two stack model obtained on estimation is as follow.

    log p_1    =  -0.236 - 0.026f + 0.303r -0.292d + 0.018rd
    log p_2    =  -0.305 - 0.033f + 0.604r -0.302d + 0.017rd

where p_i,   i ∈{1,2} is the probability for the case of one stack and two stacks respectively, and where, f, r, d represent frequency, power and distance respectively.


With the increase in the number of stacks, the constant factor in packet reception becomes lower (i.e parameter b_0 becomes more negative). This means in general, we have a lower chance of getting a packet. Similarly, the decay rate due to frequency b_1 and distance b_3 increase as well. The most significant change occurs in the impact of beacon power on packet reception. The coefficient of r, b_2 jumps from 0.056 in the no stack case to 0.303 in one stack case and 0.604 in two stack case. This is also evident in <Ref> where the gradual increase of power from left to right has more impact on two stack and one stack cases as compared to the no stack case. We can justify this result by the fact that the stacks dampen the power of the transmitted packets and larger power helps in crossing this barrier leading to higher reception. Beacon power plays more significant role in reception across stacks. Due to increased role of beacon power in overcoming the stacks, it has less impact on compensating for distance which is evident by decreasing value of b_4.



Thus, packet reception varies based on distance, frequency, power and presence of obstructions. It decreases with increase in distance, frequency or number of obstructions. Power plays a vital role in compensating for the effects of both distance and obstructions. It helps in increasing reception across obstructions and to a larger distance in free space.



 §.§ Localization Accuracy




In this section we present the accuracy using our packet reception probability model along with MCMC localization. We term our localization framework as Packet Count-Monte-Carlo Localization or PC-MCL in short. We compare against a standard range free localization algorithm, MCL <cit.> to see the effects of the packet reception model on its performance. While more recent work <cit.>, <cit.> improve upon the standard MCL accuracy, all assume a hard threshold model for hearing the beacons (i.e. if they hear a beacon, then  it must be nearer some threshold distance d_0).







We estimate location in discrete time intervals of size δ and then calculate localization error over each interval. We segregate the movement trace of the person into time windows each of duration δ seconds. In our case, we choose δ=10 sec. Localization error in each interval is the euclidean distance between predicted and ground truth location.




 <Ref> shows the average error for different device settings. Packet count based MCL gives higher accuracy compared to baseline MCL. Our system can localize within a range of 1-2m while baseline MCL always has an error over 3m. Note that the errors are lowest for a device power of -15dB. This is because at -20dB power beacons have a low coverage and individual moving in the space may not receive sufficient number of packets to get localized with low error. In contrast, -12dB gives high coverage and we hear all the beacons with increased reception rate throughout our layout. This makes it slightly harder to distinguish through which aisle the person is moving.



The average localization error within an aisle, and when the person transitions between the aisles using the corridor are different.   <Ref> shows the time series variation of error of our proposed PC-MCL and the baseline MCL algorithms for a device setting of -15dB and 1Hz. We see that the errors increase during the time intervals 4-5-6 and 10-11-12 for both the algorithms. This is because during the transition we don't have the right packet reception model to be used. Thus the average error of both algorithms increases due to errors during the transition. Indeed, the average error within an aisle drops to as low as 0.4m with our PC-MCL algorithm. Thus, if we can eliminate the high errors during transition, our algorithm can achieve high localization accuracy in the range of  0.4-0.5m. One way to achieve this to learn a packet counting model for the corridor where transitions occur, in addition to the packet count model for the aisles.














§ CONCLUSION



In this paper, we developed a probabilistic model for BLE packet reception in an indoor environment with stacks and used this model to localize moving individuals in an indoor environment. We observed that the packet counts for a beacon are binomially distributed with a parameter p, and then modeled p as function of advertising frequency, beacon power and distance to beacon. We estimated the coefficients using a Bayesian MCMC technique. We developed a Monte-Carlo localization technique using the packet reception model exploiting environment geometry in our solution. Our proposed framework performs well: we achieve an average reduction of 53% in localization error compared to a baseline Monte-Carlo localization algorithm.

We can improve our proposed framework. We noticed that while our average localization error was around ∼ 1.2m, the errors within an aisle were ∼ 0.4m. The increase in the average localization error is due to poor localization during the transition. This leads us to conclude that a “corridor” packet model in conjunction to the proposed “aisle” packet model will lead to reduction of average localization error.



ACM-Reference-Format


