Method for geofencing

• US 7,973,707 B2
• Filed: 06/11/2008
• Issued: 07/05/2011
• Est. Priority Date: 06/11/2008
• Status: Active Grant

• Current Assignee: SkyWave Mobile Communications Incorporated (ORBCOMM Incorporated)
• Original Assignee: 2201028 Ontario Incorporated
• Inventors: Verechtchiagine, Dmitri
• Primary Examiner(s): Tarcza; Thomas H
• Assistant Examiner(s): Mull; Fred H
• Application Number:
  US12/136,996
• Publication Number:
  US 20090309789A1
• Time in Patent Office: 1,119 Days
• Field of Search: 342/357.33, 342/357.34, 340/573.3, 340/573.4, 340/825.49
• US Class Current: 342/357.33
• CPC Class Codes: G01S 19/42 Determining position
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences

Abstract

A method for determining that a GPS receiver is located within a predetermined geofence volume. An embodiment of the invention includes the steps of receiving global positioning system signals from a plurality of GPS satellites; calculating a solution set of possible receiver positions from the global positioning signals; determining whether any portion of the solution set of receiver positions is within the geofence volume; and determining that the receiver is outside the geofence volume if no portion of the solution set of receiver positions is within the geofence volume. The concept of exclusion space is introduced and used in methods for determining the probability that a receiver is within a geofence volume.

Claims

1. A method for determining that a GPS receiver is located within a predetermined geofence volume, comprising:

receiving global positioning system signals from a plurality of GPS satellites;

calculating a solution set of possible receiver positions from said global positioning signals;

determining whether any portion of said solution set is within the geofence volume; and

determining that the receiver is outside the geofence volume if no portion of said solution set of receiver positions is within the geofence volume; and

wherein said plurality of satellites is selected from the group consisting of;

two satellites wherein said solution set is a solution plane; and

three satellites wherein said solution set is a solution line.

2. The method of claim 1, wherein said plurality of GPS satellites consists of two satellites.

3. The method of claim 1, wherein said plurality of GPS satellites consists of three satellites.

4. The method of claim 3, further comprising:

establishing an upper and lower exclusion space, defined to be spaces with generally horizontal border surfaces where there is a high probability that the receiver cannot be located;

defining an upper border surface for said upper exclusion space and a lower border surface for said lower border surface, said border surfaces being modeled with triangular elements;

determining triangular elements having intersection points with said solution line;

if more than one triangular element defining a border surface has an intersection point with said solution line, selecting the intersection point closest to a base position located within the geofence volume;

otherwise selecting the single intersection point for each border surface, to establish an upper and lower exclusion space intersection point;

establishing an alarm probability of zero if both of said intersection points are within the geofence volume.

5. The method of claim 4, further comprising:

where one or both of said intersection points is outside of the geofence volume, such that portions of said solution set are within the geofence volume and portions are within said exclusion spaces but not within the geofence volume, and portions are not in the geofence volume or said exclusion spaces, calculating a probability that the receiver is within the geofence volume by comparing the size of the portion of said solution set that is within the geofence volume with the size of the portion of said solution set that is not within either said exclusion spaces or said geofence volume.

6. The method of claim 3, wherein the geofence volume is a sphere, and wherein said determining whether any portion of said solution set is within the geofence volume comprises calculating the minimum distance from the center of said sphere to said solution line and determining that no portion of said solution set is within the geofence volume if said minimum distance from the center of said sphere to said solution line is greater than the radius of said sphere.

7. The method of claim 1, further comprising:

establishing a plurality of exclusion spaces defined to be spaces where there is a high probability that the receiver cannot be located; and

determining that the receiver is within the geofence volume if a portion of said solution set is within the geofence volume and the only portion of said solution set that is not within the geofence volume is completely within one or more of said plurality of exclusion spaces.

8. The method of claim 7, wherein the geofence is a sphere having a radius R_geof and further comprising Computing δ

_U^min=|δ

_U^min

Determining if δ

_U^min>

R_geof and if so, declaring P(Alarm)=1, and ending the method steps;

If P(Alarm) does not equal 1, finding vectors δ

_U,1^sph and δ

_U,2^sph pointing to the intersections of the solution line with the geofence sphere such that δ

_U,1z^sph<

δ

_U,2z^sph;

if δ

_U,1z^sph<

−

D_lower and δ

_U,2z^sph>

−

D_upper declaring P(Alarm)=0;

if P(Alarm) does not equal 0, declaring 0<

P(Alarm)<

1.

9. The method of claim 8, wherein a portion of said solution line is within said sphere and a larger portion of said solution line is not in said exclusion spaces, further comprising determining a value for P(Alarm) in the case where 0<

P(Alarm)<

1, by calculating the portion of said solution line within said sphere over the portion of said solution line not within said exclusion spaces.

10. The method of claim 1, further comprising:

establishing a plurality of exclusion spaces, defined to be spaces where there is a high probability that the receiver cannot be located;

where portions of said solution set are within the geofence volume and portions are within said exclusion space but not within the geofence volume, and portions are not in the geofence volume or said exclusion space, calculating a probability that the receiver is within the geofence volume by comparing the size of the portion of said solution set that is within the geofence volume with the size of the portion of said solution set that is not within either said exclusion spaces or said geofence volume.

11. An article of manufacture for enabling a global positioning system to determine where a global positioning receiver is within a predetermined geofence volume, the article of manufacture comprising:

a computer-readable storage medium; and

code stored in said computer-readable storage medium, such that when said code is executed in a processor in said global positioning receiver, said processor causes said receiver to receiving global positioning system signals from a plurality of GPS satellites;

calculates a solution set of possible receiver positions from said global positioning signals;

determines whether any portion of said solution set is within the geofence volume; and

determines that the receiver is outside the geofence volume if no portion of said solution set of receiver positions is within the geofence volume; and

wherein said plurality of satellites is selected from the group consisting of;

two satellites wherein said solution set is a solution plane; and

three satellites wherein said solution set is a solution line.

12. A method for determining the probability, P(Alarm), that a GPS receiver is outside of a predetermined geofence volume wherein the geofence volume is bounded by a plurality of exclusion spaces, the method comprising:

receiving global positioning system signals from a plurality of GPS satellites;

calculating a solution set of possible receiver positions from said global positioning signals;

determining whether any portion of said solution set is within the geofence volume; and

determining that P(Alarm)=1 if no portion of said solution set of receiver positions is within the geofence volume;

determining that P(Alarm)=0 if a portion of said solution set of receiver positions is within the geofence volume and no portion of said solution set of receiver positions is outside of the geofence volume and not inside any of said exclusion spaces; and

determining that if a portion of said solution set is not within the exclusion spaces or the geofence volume, then P(Alarm) equals the portion of said solution set of receiver positions within the geofence volume divided by the portion of said receiver positions that is not within the exclusion spaces.