Beacon geofence about trail-sense HOT 9 OPEN

The author was so nice to make their paper publicly available:
https://www.researchgate.net/publication/339904498_Low_computation_in-device_geofencing_algorithm_using_hierarchy-based_searching_for_offline_usage

from trail-sense.

I hid my own comment, cause it was suggesting the same feature you suggested :) I basically thought of the same thing when In read it. Might be a nice followup paper actually :)

from trail-sense.

Just cause I sumbled over it, here is a link to a research paper from IEEE about an efficient geofencing algorithm.
Low computation in-device geofencing algorithm using hierarchy-based searching for offline usage

Can probably contact the author via research gate to check if he would provide the paper for free for the project, cause it fits kinda well into the problem.

Edit:
I had a quick fly over the paper (can access IEEE over my student licence). It sounds pretty promising as a concept. It can definetly be improved for the use in Trail Sense to use less computation when checking if you are still outside of a zone. Won't go into detail for now, as the contents of the paper are still protected :) I can hit up the author and ask if he wants to provide the paper for this project.

from trail-sense.

@Portagoras thank you, that would be great!

from trail-sense.

@Portagoras thank you for reaching out to the author! That is great news, I will give it a read.

from trail-sense.

I read through the paper and it is a very interesting topic. The method described seemed to be focused around computational efficiency (time complexity and frequency of recalculation), but it didn't seem to talk about frequency of the trigger (ex. how frequent to wake up and poll the GPS). This approach may be useful to implement if there are a lot of geofences set up, though I'm not sure I'm too concerned about there being a lot yet in Trail Sense. But I am interested in seeing if this will benefit the nearby beacons filtering - currently I'm retrieving all beacons and filtering to those that are nearby, which is pretty inefficient. I could use a tree structure, like this paper describes, to more efficiently filter the beacons.

My main concern is how often the geofencing check will be triggered in the background.

My potential solution to this is that the delay becomes longer the further away from the geofences you are, with a min/max restriction on the frequency. For example, if I won't be able to travel to the nearest geofence within an hour, I shouldn't run the geofence algorithm again for another hour.

When the process is triggered, I could use a version of the algorithm described by the paper to check the geofences without needing to recalculate all distances, but I will need to do some performance tests with the naïve approach before implementing it.

If the paper did talk about this, but I missed it, please let me know.

from trail-sense.

I actually thought about the same issue and also think I found a pretty good solution or solutions.

1. Optimization

When the geofencing first triggers, it checks in what part of the tree you are. For now, let's focus on the root, so you are not in a geofence.
The first time it triggers, it finds the closest first-level region and retrieves the distance. Then we create a virtual geofence with a radius of the closest geofence. Now, whenever it triggers, we only need to check if we left that zone or if the tree changed. So we just eliminated all first-level computations. This should also work on any other level of the tree.

2. Optimization

Estimating speed is essential for this. We can use anything from accelerometers to short-range GPS usage.
When we know the size of our virtual fence, how far away we are from the center of it, and therefore how far away we are from the perimeter, and we know our speed, we can find intervals when we need to check the GPS again.
Example. Our virtual geofence-free zone is 10 km, and we are currently 2 km from the center, so the distance to the perimeter is 8km. When we are on foot, we travel something like 5 km/h, so we can easily wait over an hour for the next GPS check.
This could also be an energy-saving setting.

EDIT: I completly missed the section where you suggested basically the same. Therefore hidden.

from trail-sense.

Just a simple first idea about the trigger frequency: Wouldn't it be possible to just use an active backtrack as foundation for this problem? This way the user could decide for itself on which timescale the geofence will be reached and how precise the notification time has to be.

Potential problems/downsides:

• At long backtrack intervals you potentially miss a relatively small fenced area, or cross it without being noticed.
• You may want to have a larger backtrack interval than that you need for detecting your geofence entering.
• What happens if your location cannot be detected at the time a backtrack record fires?

from trail-sense.

@Z3NOX that could be possible, and maybe a good initial implementation. My only concern is that they serve two different purposes. The geofence would be for navigation and reminders, while backtrack's main purpose it for retracing your steps. I think the two should operate independently, so that you don't need to record a path if you only want to be notified about the proximity to a beacon.

from trail-sense.