Alternate distance formula proposal

[davidgyoung]

An alternate distance formula proposal has been made by @WallyHale in the AltBeacon repo: AltBeacon/spec#30 (comment)

This is similar to the technique currently used by this library but it uses a comparison to the ratio of the measured rssi vs. the calibrated rssi at a series of known points and linear interpolation to approximate distance between these points.

[ericsuhong]

Is there any reason why we are not fitting a simple logarithmic function to sampled RSSIs for distance equation? (I do not know any relevant works done in this area, so please excuse my ignorance if I am missing some necessary background knowledge).

For my school project, I implemented an app that tracks the location using beacons, and I used a simple logarithmic function to estimate the distance, and it worked quiet well.

I measured signals from beacons using Samsung Galaxy Note 3, and sampled signals from 1m to 10m many iterations.

The data I collected seems to be similar to the measurements on an iPhone.

Calibration Full Data.xlsx

I eventually used this distance function: distance = e^((RSSI+60)/-12)) for my project.
(0.5m if RSSI < 60, for my project but can use different function for RSSI < 60)

[davidgyoung]

Hi, @sukhong. It looks like you have good results. The difficult part is making a formula that will work with multiple Android devices and multiple beacon transmitter power levels. Are you interested in doing some research to help find a good distance calculation for the library? If so, I can provide you with some raw data we have collected.

[ericsuhong]

I don't think I will have time to do research on this topic further next semester.

But I believe that regardless of device types and beacon power levels, all formulas should have a similar log slope because RSSI dbM is a logarithmic unit. (this, of course, may be a wrong assumption).

In my experience, each beacon had a different y-intercept, although they all had a similar slope around ~-11.

My hypothesis was that if we can find this "universal" slope that can fit most of the devices and beacons, we can find y-intercept for distance function y = a+Cln(x) given a reference signal level at 1m and universal slope C.

[andersborgabiro]

Well, the calibrated power value (TX?) should be set correctly in the beacon. My experience is that it's not. In my beacon writer app for a certain beacon brand I set TX based on selected real power, empirically calibrated for iPhone 4S (I happened to have one). Both the device's sensitivity and the beacon type (antenna design etc) will affect the actual power, despite being set to e.g. 0 dBm, so it will still differ. In practice I only rely on far/near/immediate.

[ghost]

Has there been any progress on a new distance algorithm? I have been using a couple of RadBeacon Dots and ranging for them on a OnePlus 2. The transmission power is set to maximum and the reference RSSI calibrated to between -49dBm and -52dBm for the different beacons using the Locate app at one meter.

I then have the same issue as has been discussed here and elsewhere, the distance from getDistance is way too small compared to the real distance as you move away from the beacon.

[andersborgabiro]

@sukhong The 60 you mention depends directly on the beacon's transmission power, so 60 should not be used as a constant in the implementation. Rather it should use the reported Tx Power (my different beacons say -53 or -59 dBm), assuming/hoping that the beacon is set up correctly. See my previous comment.

Optimally there would also be compensation for the sensitivity of the actual device, but determining that would be never-ending, as new devices come out all the time.

In what file is the current formula?

[davidgyoung]

There has been work on this periodically, but it is a bit time consuming so we have been looking for a volunteer to help with it.

There is a PR with an alternate distance implementation here: :#251

You might try that branch and enable the alternate algorithm as described there.

[davidgyoung]

FYI, current formula is here:

distance = (mCoefficient1)*Math.pow(ratio,mCoefficient2) + mCoefficient3;

https://github.com/AltBeacon/android-beacon-library/blob/master/src/main/java/org/altbeacon/beacon/distance/CurveFittedDistanceCalculator.java

[ghost]

Thank you, I will try using the experimental solution and see if it gives better results.

[andersborgabiro]

I'm no math expert, but if both rssi and txPower are in dBm they should be subtracted not divided, right? dBm is logarithmic.

[davidgyoung]

Yes, the path loss formula in the branch here #251 subtracts the two values as you suggest

[ghost]

I must admit a bit of fault here, I tried recalibrating the beacons in a more open area and received new values for TxPower that were much larger than where I was doing the first calibration. Now I get TxPowers ranging from -41 to -45 and the distances returned from getDistance() are much more sensible. With the distances I am getting now I think getDistance using the normal algorithm may be enough for my needs. Keep up the good work with this library!

[andersborgabiro]

But has anyone gone through the math and verified whether the current algorithm is correct? Isn't the conclusion that it's not?

@zakjut You mean RSSI right? TX Power is the calibration value.

[davidgyoung]

The current algorithm is based on a curve fit, which is certainly a valid technique. But it does not predict distance well with lower power transmitters, because the data points used for the curve fitting were based on a higher power transmitter.

In theory, the path loss formula referenced in the pull request is scientifically correct. However, we have not proven that it can predict distance well across a wide variety of beacn transmitter power levels and varying receiving mobile devices.

[andersborgabiro]

Is low power (well below 0 dBm) used much?

The beacons I source can be set to 0, -6 and -23 dBm. -23 is pretty much useless (verified). -6 might be useful for a battery/distance tradeoff. Lower than -6 doesn't seem very useful due to how easy it is to "confuse".

My experience is that beacon manufacturers don't understand the importance of setting TX Power correctly, with the exception of Radius Networks of course (hopefully) :).

[ghost]

@andersborgabiro No I mean TxPower, as in I performed the calibration at 1 meter again to get a new calibration value. The beacons I got from radius came with the calibration value set at -73dBm which was way too low. After the first recalibration I got my values -49 and -52 for the four beacons. Which was still too low. As I mentioned, I think the first set of values I got was weakened by interference in the room I was measuring in since I got higher values (between -41 and -45) when redoing the calibration in an open area. With these new reference values, I am finally getting sensible ranging data at short to medium distances.

[andersborgabiro]

Oh sorry, misunderstood.

Mine are around -60 dBm at 0 dBm.

I wish TX Power was set automatically when setting actual power.

[ghost]

@andersborgabiro Aye, that would have been a nice feature of a beacon if it used the current TxPower to extrapolate the new one automatically when transmission power is set.

Anyways, @davidgyoung what is the transmission power of the beacons that the fitting was done against, and is it not possible to have two versions of the fitting? One as it is now and another one that can be set if you know your beacons will transmit at some power under a certain threshold.

[heypiotr]

@zakjut @andersborgabiro That feature is up to beacon manufacturers. I know that Estimote Beacons for example come with pre-calibrated values for each transmit power level. Haven't checked other vendors. (Disclosure: I work at Estimote.)

[ghost]

@heypiotr Yea that is a good feature. Anyways, sorry for dragging this off topic.

[andersborgabiro]

What's confusing is that in the linked to discussion both division and subtraction are mentioned as valid methods.

http://stackoverflow.com/questions/20416218/understanding-ibeacon-distancing

Both RSSI and (supposedly correctly named) txPower are in dBm, hence subtraction before exponentiation. If the values were actual (in Watts), then division without exponentiation.

Also, radio signals attenuate 1 / x^2 by distance, if now that matters here.

What am I missing?

Is the algorithm used in iOS official?

[davidgyoung]

@zakjut, yes, Radius Networks' RadBeacon configuration app automatically sets the standard calibrated power constant corresponding to a change the transmitter power level. But you still may need to calibrate the beacon manually if you have environmental differences.

@andersborgabiro, signal theory says you should subtract values in dB to get a distance estimate. This is the technique used in the new formula in the pull request mentioned above. Again, the existing formula in the library is based on empirical data fit to a power curve, which isn't a log function. This is the reason subtraction is used is because "Division inside the log can be turned into subtraction outside the log, and vice versa." See: http://www.purplemath.com/modules/logrules.htm. Regardless, I would suggest that improvements in the formula be based upon the path loss formula in pull request #251 Unfortunately, the iOS formula is closed source and not published.

[andersborgabiro]

Understood. Yes, I know that level of math :).

[jackfengji]

@davidgyoung Is there a plan when will the pull request be merged and published? Is there any concern not to merge it?

[davidgyoung]

There is currently no test data to suggest that this alternative formula more accurately estimates distances vs. the current formula or a second proposed formula in #251. It doesn't make sense to switch to a new formula unless there is a demonstrated benefit.

Testing distances estimates with multiple devices and beacon settings can be time consuming, so I am looking for a volunteer to help out. Please let me know if you are interested in working on this testing, and I can help get you set up to do so.

[sbrkx]

@davidgyoung could you tell how you calculated receiverRssiSlope and receiverRssiOffset for each specific device? I would like to add some devices to your list to improve the database and also verify that the new path loss formula performs better.
It would be great if you could explain in detail how your test setup is built and how you do the calculations.
I have reference iOS devices (from 5-6S) and many current Android devives.

Thanks!

[davidgyoung]

Thanks, @sbkx, I'd love to have your contribution to this. Let me write something up for you, and then maybe we can arrange a Skype or Hangout to discuss.

[sbrkx]

@davidgyoung I'd love to hear from you soon! I sent you an email to discuss this further.

[davidgyoung]

@sbrkx, please take a look at the instructions here: http://altbeacon.github.io/android-beacon-library/distance-calculations2.html

Please also send me an email at david at radiusnetworks.com so we can discuss the path loss formula evaluation.

[pierre-oord]

Hi @davidgyoung @sbrkx how did your testing go?
I am working on a hardware device for which distance measuring is very important. I will soon have test results of the first devices. I'm planning to do the measurements as you suggested in your excel file, for different phones, and also with different tx power. I just bought an iPhone 5s as reference.

I think it might be wise if we would start a database with the original data - currently only the A,B,C variables are written down, that makes it difficult to test new formulas. Do you have test data available with the original received dBm?

[davidgyoung]

@pierre-oord, I do not have any test results from @sbkx following the exchange above.

Good point about the test data -- we really don't have it centralized, but it might be nice to make a shared google doc where we can keep them all in one place.

Here's the info I have:

Below is a very old table of data collections from Radius Networks in 2015

Meters	iPhone 4s	Galaxy S 3	Nexus 5	Galaxy S5	Moto G
0.25	-35	-39	-41	-61	-54
0.5	-52	-41	-43	-64	-62
1	-45	-52	-49	-71	-66
2	-56	-57	-65	-77	-75
3	-57	-61	-58	-83	-83
4	-61	-60	-57	-95	-83
5	-66	-58	-67	-91	-90
6	-68	-67	-67	-88	-89
7	-63	-65	-77	-101	-85
8	-65	-66	-70	-100	-81
9	-64	-65	-69	-101	-87
10	-67	-70	-75	-98	-84
12	-61	-66	-72	-98	-91
14	-73	-70	-72	-100	-94
16	-69	-79	-78	-101	-93
18	-79	-79	-83	-103	-95
20	-72	-76	-81	-99	-97
25	-72	-73	-81	-105	-95
30	-71	-75	-75	-98	-95
40	-71	-81	-83	-106	-97

And this is the data set from when the library's formula was first developed:

Distance (m)	Nexus 4 RSSI	iPhone 4S RSSI
0.0762195122	-32	-28
1	-56	-54
1.524390244	-66	-66
3.048780488	-73	-70
4.573170732	-65	-67
6.097560976	-74	-69
7.62195122	-74	-68
9.146341463	-76	-73
10.67073171	-73	-75
12.19512195	-78	-75
13.7195122	-84	-76
15.24390244	-79	-77

Some test data can also be found in a couple of issues and pull requests:

#385
#376
#47

[andersborgabiro]

I vote for that being documented separately, yet it would be nice with a separate library/method that did just that too: RSSI, TX and device in, distance out.

What was the physical environment for such tests?

• Walls far away, so no affecting reflections?
• Hanging nodes, so no absorption from nearby objects?
• 0 dBm?

Striking difference between phones. -35 to -54 dBm for the same physical distance is massive, and makes any attempt to use an average very unreliable.

Secondly, I often see that TX is set wrong (and sometimes even static independent of power), which adds to the level of error. Is TX adjusted based on set power in Radius beacons?

It's easier for iOS as there are so few variants of devices to cover, but even there TX is unreliable.

[davidgyoung]

Yes, for Radius beacons the RadBeacon config app was originally built to automatically adjust the measuredPower parameter when you change the transmitter level, with the adjustment made to the expected 1m rssi level as previously measured by an iPhone 4s.

For the distance/rssi measurements done by Radius, the standard procedure was to place a RadBeacon Tag at max power on an empty cardboard box to elevate it ~12" above ground level in an open field, then take 30 second average rssi readings at various distances with the phone's back facing the beacon on the same horizontal plane.

It would be nice to standardize the procedure, and request details about how the measurements were taken for those submitting data, but I have found getting folks to submit data at all to be challenging.

[andersborgabiro]

That's what I do in my beacon writer app as well, and I also used an iPhone (5) as reference :).

It doesn't seem to be any interest from Google and/or Android to regulate this. I wonder if they ask certified iBeacon and Eddystone providers (if now Google certifies) to send in such data.

Probably a better solution for the direction of the phone would be to use the side that has the highest sensitivity, as e.g. iPhone 6 and 7 have metal backs, and stick to that when measuring the levels.

[pierre-oord]

Thanks all for the information. I have created an Excel file that allows for adding new phones per row, and also calculates (regresses) the coefficients for the two different formulas I have found here. The formulas don't work on Google Spreadsheets unfortunately.

I have highlighted several cell for which information is missing. Especially note that the Nexus 5 demo row gives different coefficients than listed online - but the results do comply with the google docs file you have linked to.

It would be great if you can make changes to the file and send them to me. I'll try to keep the file updated then. Likely there is an easier method doing this with Github, but i'm very new here.
Phone RSSI database.xlsx

[andersborgabiro]

I've seen repos with arbitrary files, like PowerPoints etc, so not just code. Also repos with only documentation etc.

[pierre-oord]

It has been pretty rainy/misty here, but Friday I finally managed to do some measurements. I have attached the excel sheet. Two interesting things:

• The residual sum of squares (RSS) for the original formula is lower than the offset-formula for the phones I tested. Except for one Samsung phone, which always gives the same RSSI, and is useless anyway.
• After about 5 measurements with the locate App, the app seemed to misbehave. The iPhone app only took a few seconds for a reading, while the Android app started to give very different values.

ok	error
-67	-76
-66	-76
-63	-74
-81	-86
-78	-86
-42	-42
-69	-76

First column the values after killing and restarting the app. Second column the strange readings. Therefore, at every measurement, we killed and restarted the locate app, just to be sure.

Would you all please add more readings, and verify current readings in the Excel file (attached)? I'm missing quite some data for what I found on this forum. Thanks!

Phone RSSI database 2017-11-12.xlsx

[davidgyoung]

@pierre-oord, your help on this is very much appreciated!

Unfortunately, I do not have a copy of Microsoft Excel, and importing into Mac Numbers or into Google Sheets and the exporting to Excel will destroy your formulas. I really wish we could make the formulas work on Google Sheets, but I understand that this may be too challenging.

I did a search this morning to see if I can find more raw data, without success. I can do some additional measurements on the Nexus 5X, Moto G4 and the Huawei P9.

Three other things I think we should record when doing data collection:

1. Beacon transmitter make and model
2. Beacon transmitter power setting (if available, in dBm)
3. Beacon transmitter advertising rate (should be set to 10Hz, if possible)

[pierre-oord]

Hi David,

I got it running on Google Sheets, it just needed some omitted arguments.

It would be great if you could have a look at the spreadsheet. Especially for the phones that you added, as sometimes I was not sure what the iPhone 5 reference value was, for example, as I found multiple values here on the board.

About the three points you mentioned:

1. I'm not sure if this adds value. Difficulty here is that there are many different ones. We for example use a prototype board of an Cypress and a prototype board of a Dialog chip. I don't see how we can correct for such a factor in the future. Different antenna types will transmit the signal to a different position.
2. I think it's safest to rely on the iPhone 5s measurement. What I want to do next is do all the measurements again, but then for a lower power output. That way, we could see what the curve difference for different output power settings is (might be different??). Then, we could add some correction factor depending on the dBm of the iPhone 5s at one meter.
3. I think ours was set at 10 or 20 hz. However, I think it would be a better idea to change your calibration app. For example, you could set the app to need at least 1000 samples. After all, it's not the speed, but the amount of measurements that improve the quality?

I'll improve the Excel/Google sheets value later on, but for now, i just wanted to show you the progress and also show that the newer formula doesn't seem to add value.

If you could add new measurements, that would be great!

[davidgyoung]

Hey, great news on Google Sheets, @pierre-oord. Nice progress. I'll add those iPhone reference values if you give me edit access. (I do see a few calculations are showing #REF! or #DIV/0.)

1. I agree you cannot figure out the transmission characteristics by recording the beacon model. I suggest recording it only as a best practice for recording your equipment for any lab measurement. It may be useful info in the future to remind you of how you did the test, and help you reproduce the results (or understand why you cannot reproduce the results) later on.

2. The problem with using iPhone 5 as the reference device, of course, is that as time goes on it gets harder to get your hands on an iPhone 5. (I personally no longer have access to one, only an iPhone 6 and and iPod touch 5th Generation.) I'm not sure what to suggest as a tool for an easily accessible reference measurements that won't soon become obsolete. (Perhaps we should just rely on the latest iPhone device available and document what it was?)

3. On iOS at least, there is no way to get access to how many iBeacon packets were detected in a one second period -- the operating system automatically averages the RSSI for all packets received in a one second period, so calibrations must be done for a fixed period of time and not based on packet counts. Yes, on Android, the calibration could be based on a packet count. But I'm not sure it is worth introducing a difference from the behavior of iOS given that it is not possible to make iOS work consistently. It isn't so important that the advertising rate be set to a specific value as it is to set it to a high enough value to get good results, and many beacons are set to 1Hz or less frequent by default.

[pierre-oord]

Everyone can edit the file now. I'll keep a copy for myself, i'm not sure about Google's version management.

1. Ok, i'll add such a column.
2. I think we should simply build an iPhone reference database that either you or me will maintain. I think it should be possible to build ratio's on ratio's. What i mean is: if we know how the iPhone 5/6/7/8 relate to each other, we should be able to back-calculate the value to the iPhone 5 value (of forward-calculate all old values to the iPhone 8).
3. Ok, that's clear. Maybe we can show a warning in the Android app if the Hz value is too low, just to inform the user.

Please add the values in the file. I hope that the end results will be the same as they are currently listed online (I got different values, also with your original Google Sheets file).

[pierre-oord]

By the way, I'm struggling a bit with the intercept. I'm not sure if it's such a good idea to assume that the 1m start value is the "intercept". I have calculated the absolute difference between the real value in meters, and the calculated value in meters, and if I use Excel's solver function to calculate a different intercept, I get a lower total of absolute difference.

See below in green. Excel file also attached (sorry, I prefer Excel over Google docs as I'm very familiair with it).

Phone RSSI database 2017-11-14.xlsx

[davidgyoung]

@pierre-oord, I added three rows of new device measurements to the Google Docs spreadsheet with raw data and test notes in #620. I have some notes there about correlations you may want to review.

To answer your question about the intercept, I think any method of regression that produces a better correlation is better, and if that means the Excel solver method, then that's fine. We just need to document how this is calculated so it can be reproduced.