Method for determining if the location of a wireless communication device is within a specified area

• US 6,212,392 B1
• Filed: 02/26/1999
• Issued: 04/03/2001
• Est. Priority Date: 02/26/1999
• Status: Expired due to Term

• Current Assignee: Unwired Planet LLC (JP Morgan Chase & Co)
• Original Assignee: Signalsoft Corporation (JP Morgan Chase & Co)
• Inventors: Fitch, James A., Wager, Garrick T.
• Primary Examiner(s): Nguyen, Lee
• Application Number:
  US09/258,228
• Time in Patent Office: 767 Days
• Field of Search: 455/456, 455/457, 342/357.01, 342/357.09, 342/451, 701/207, 701/208, 701/213, 340/988, 340/991, 340/993, 340/995
• US Class Current: 455/456.2
• CPC Class Codes: H04B 7/18547 for geolocalisation of a station position fixing by direction or distance determination G01S5/00
• CPC Class Codes: H04M 11/04 with alarm systems, e.g. fire, police or burglar alarm systems
• CPC Class Codes: H04M 2242/04 for emergency applications
• CPC Class Codes: H04M 2242/30 Determination of the location of a subscriber
• CPC Class Codes: H04M 3/42 Systems providing special services or facilities to subscribers specially adapted for wireless communication networks H04W4/00
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

The present invention is directed to a method for determining whether a location associated with a wireless station, such as a cellular telephone, is located within an area of interest. The area of interest is defined using quadtree representation of an area that includes the area of interest and identifying nodes within the quadtree that represent the area of interest. By iterative comparison of the location associated with the wireless station to the locations associated with a node at each level of the quadtree, a determination can be made as to whether or not the location associated with the wireless station is within the area of interest.

Claims

1. A method for use in determining whether a wireless station in a wireless telecommunication system is located within a predetermined are of interest that is of substantially any shape, the method comprising:

receiving a location associated with a wireless station;

providing a quadtree representation of an area that includes a predetermined area of interest, wherein said guadtree representation includes;

level-1 through level-n, where n is an integer;

wherein level-1 has at least one level-1 node that represents a level-1 area;

wherein associated with each level-1 node is a level-1 location;

wherein level-x, where 1<

x≦

n, has a maximum of four level-x nodes for each level-(x−

1) node;

wherein each level-x node represent one of the four subsidiary areas of a level(x−

1) area associated with one of the level-(x−

1) nodes;

wherein associated with each level-x node is a level-x location;

wherein associated with each level-n node is an indicator of whether or not the level-n area represented by the level-n node is part of the predetermined area of interest; and

using said location associated with a wireless station and said quadtree representation to determine whether the wireless station is located within the predetermined area of interest.

2. A method, as claimed in claim 1, wherein said step of using includes:

setting x equal to 1;

first identifying the level-1 node that represents the level-1 area that includes the location associated with the wireless station as the relevant level-x node;

comparing said location associated with a wireless station to a level-x location associated with the relevant level-x node, where 1≦

x<

n, to determine which level-(x+1) node represents the level-(x+1) area that includes the location associated with the wireless station;

second identifying the level-(x+1) node determined to represent the level-(x+1) area that includes the location associated with the wireless station as the relevant level-x node;

incrementing, following said step of comparing, the value of x by 1;

repeating, if x<

n, said steps of comparing, second identifying and incrementing;

transmitting, if x=n, the indicator associated with the level-n node that indicates whether or not the location of the wireless stations is within the predetermined area of interest.

3. A method, as claimed in claim 2, wherein said step of comparing includes:

determining whether the latitude of said location associated with a wireless station is greater than or less than the latitude associated with said level-x location;

determining whether the longitude of said location associated with a wireless station is greater than or less than the longitude associated with said level-x location.

4. A method, as claimed in claim 1, wherein said step of providing a quadtree includes;

storing a level of said quadtree on a disk drive.

5. A method for constructing a quadtree representation of an area that includes an area of interest and is suitable for use in high-speed, wireless telecommunication application that requires a determination of whether a location associated with a wireless station is within the area of interest, the method comprising:

receiving a map of an area of interest in a telecommunication application;

vectorizing the boundaries of the area of interest to define a polygon defined by a plurality of edges that enclose an area;

establishing a quadtree level depth n, where n is an integer;

setting x equal to 1;

identifying a level-1 node that represents a level-1 area that includes the polygon;

defining, if an edge of said polygon is located within a level-(x+1) area that is one of four subsidiary areas of said level-x area, as a level-(x+1) node;

incrementing the value of x by 1;

repeating, if x<

n, said steps of defining and incrementing;

establishing, if x=n, an indicator for each level-n node that identifies the polygon;

wherein said identifier can subsequently be used to determine if the location associated with a wireless station is within said polygon.

6. A method, as claimed in claim 5, wherein said step of establishing includes:

determining if four nodes at level-n that represent the four subsidiary areas of a level-(n−

1) area have the indicator;

establishing, if all four nodes at level-n have the indicator, the indicator in the level-(n−

1) node that has the level-(n−

1) area that includes the four subsidiary areas associated with the four nodes at level n; and

removing, if all four nodes at level-n have the indicator, the four nodes at level-n from the quadtree.

7. A method, as claimed in claim 6, wherein said step of establishing includes:

repeating said steps of determining, removing and establishing for all the groups of four nodes at level-n that represent four subsidiary areas of a level-(n−

1) area that have the indicator.

8. A method, as claimed in claim 7, wherein said step of establishing includes:

repeating said step of determining, removing and establishing for each level.

9. A method, as claimed in claim 5, wherein said step of establishing includes:

setting x equal to n;

determining for all groups of four nodes at level-x that represent the four subsidiary areas of a level-(x−

1) area if all four nodes of a group have the indicator;

establishing, for all groups of four nodes have the indicator, the indicator in the level-(x−

1) node that has the level-(x−

1) area that includes the four subsidiary areas associated with the four nodes at level x;

removing, for all groups of four nodes that have the indicator, the four nodes in each group from the quadtree; and

decrementing x by 1;

repeating, if x≧

1, said steps of determining, removing and establishing.

10. A method, as claimed in claim 5, further comprising:

inserting a second node to replace an existing, first node;

wherein said second node has either removed or inserted an indicator relative to the existing first, node;

removing, following said step of inserting, said existing, first node.

11. A method for use in determining whether a wireless station in a wireless telecommunication system is located within a predetermined area of interest that is of substantially any shape, the method comprising:

receiving a location associated with a wireless station;

providing a quadtree representation of an area that includes a predetermined area of interest wherein said quadtree representation includes;

level-1 through level-n, where n is an integer;

wherein level-1 has at least one level-1 node that represents a level-1 area;

wherein associated with each level-1 node is a level-1 location;

wherein level-x, where 1<

x≦

n, has a number of level-x nodes that is a multiple of four, where the multiplier is a value from 0 to the number of level-(x−

1) nodes;

wherein each level-x node represents one of the four subsidiary areas of a level-(x−

1) area associated with one of the level-(x−

1) nodes;

wherein associated with each level-x node is a level-x location;

wherein associated with each level-n node is an indicator of whether or not the level-n area represented by the level-n node is part of the predetermined area of interest; and

using said location associated with a wireless station and said quadtree representation to determine whether the wireless station is located within the predetermined area of interest.

12. A method, as claimed in claim 11, wherein said step of using includes:

setting x equal to 1;

first identifying the level-1 node that represents the level-1 area that includes the location associated with the wireless station as the relevant level-x node;

comparing said location associated with a wireless station to a level-x location associated with the relevant level-x node, where 1≦

x<

n , to determine which level-(x+1) node represents the level-(x+1) area that includes the location associated with the wireless station;

second identifying the level-(x+1) node determined to represent the level-(x+1) area that includes the location associated with the wireless station as the relevant level-x node;

incrementing, following said step of comparing, the value of x by 1;

repeating, if x<

n, said steps of comparing, second identifying and incrementing;

transmitting, if x=n, the indicator associated with the level-n node that indicates whether or note the location of the wireless stations is within the predetermined area of interest.

13. A method, as claimed in claim 12, wherein said step of comparing includes;

determining whether the latitude of said location associated with a wireless station is greater than or less than the latitude associated with said level-x location;

determining whether the longitude of said location associated with a wireless station is greater than or less than the longitude associated with said level-x location.

14. A method for use in determining whether a wireless station in a wireless telecommunication system is located within a predetermined area of interest that is of substantially any shape, the method comprising:

receiving a location associated with a wireless station;

providing a quadtree representation of an area that includes a predetermined area of interest; and

using said location associated with a wireless station and said quadtree representation to make a determination as to whether the wireless station is located within the predetermined area of interest;

said method further comprising the steps of;

establishing a definition of said area of interest in terms of area elements of said quadtree data structure and storing said first definition for use by a platform of said wireless telecommunication system for making said determination;

receiving a modification regarding said area of interest said modification affecting an affected portion less than the whole of said definition of said area of interest;

establishing modification information reflecting said modification affecting said affected portion of said definition of said area of interest;

storing said modification information for use by said platform of said wireless telecommunication system for making said determination; and

after said step of storing said modification information, deleting information related to said affected portion from said definition of said area of interest;

wherein said definition of said area of interest is modified with little effect on said wireless telecommunication system.