Infrastructure for location discovery

• US 9,125,066 B2
• Filed: 01/16/2013
• Issued: 09/01/2015
• Est. Priority Date: 03/31/2009
• Status: Expired due to Fees

• Current Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC), Regents of the University of California (University of California)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Potkonjak, Miodrag
• Primary Examiner(s): Elhag, Magdi
• Application Number:
  US13/742,944
• Publication Number:
  US 20130130701A1
• Time in Patent Office: 958 Days
• Field of Search: 455446-450, 455/456.1, 455/456.5, 455/456.6, 455/404.2, 455/41.2, 370/254, 370/255, 370/328, 702 85- 95, 702149-155, 342/385, 342/386, 342/413, 342/450, 342/451, 342/459
• US Class Current: 1/1
• CPC Class Codes: G01S 1/00 Beacons or beacon systems transmitting signals having a characteristic or characteristics capable of being detected by non-directional receivers and defining directions, positions, or position lines fixed relatively to the beacon transmitters; Receivers co-operating therewith position fixing by co-ordinating a plurality of determinations of direction or position lines G01S5/00
• CPC Class Codes: G01S 1/02 using radio waves G01S19/00 takes precedence
• CPC Class Codes: G01S 1/022 Means for monitoring or calibrating
• CPC Class Codes: G01S 1/024 of beacon transmitters
• CPC Class Codes: G01S 1/026 of associated receivers
• CPC Class Codes: G01S 1/028 Simulation means, e.g. of beacon signals therefor for teaching or training purposes G09B9/00
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 16/20 for indoor coverage or short range network deployment
• CPC Class Codes: H04W 16/28 using beam steering
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 64/003 locating network equipment
• CPC Class Codes: H04W 72/542 using measured or perceived quality
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

Techniques are generally described for determining locations of a plurality of communication devices in a network. In some examples, methods for creating a location discovery infrastructure (LDI) for estimating locations of one or more of a plurality of communication nodes may comprise one or more of determining a plurality of locations in the terrain to place a corresponding plurality of beacon nodes, determining a plurality of beacon node groups for the placed beacon nodes, and determining a schedule for the placed beacon nodes to be active. Additional variants and embodiments are also disclosed.

Claims

1. A method comprising:

grouping, by a computing device, one or more of a plurality of communication nodes into a plurality of communication node groups, wherein communication nodes in individual communication node groups of the plurality of communication node groups are in proximity;

selecting, by the computing device, a representative communication node from each of the individual communication node groups, the selected representative communication nodes of the plurality of communication node groups forming a dominating set of communication nodes; and

determining, by the computing device, a number and locations of beacon nodes to be placed in a terrain, based at least in part on an individual representative communication node receiving a signal from a plurality of beacon nodes;

wherein the selecting comprises formulating and solving an objective function to minimize a number of the selected representative communication nodes in the dominating set of communication nodes; and

wherein each node in the dominating set of communication nodes is configured to receive signals from a same set of three neighboring beacon nodes.

2. The method of claim 1, wherein the determining is further based at least in part on reducing a likelihood of location discovery error for discovering locations of one or more of the plurality of communication nodes using the placed beacon node.

3. The method of claim 1, further comprising determining, by the computing device, a schedule for the placed beacon node to be active, based at least in part on a waiting time of individual communication nodes to receive a location determination signal.

4. The method of claim 1, wherein the determining is further based at least in part on individual representative communication nodes receiving signals from a plurality of placed beacon nodes.

5. The method of claim 1, wherein the identifying the plurality of beacon node groups further comprises:

identifying, for individual pairs of the placed beacon nodes, a likelihood of at least one of interference or collision at a communication node in response to a pair of beacon nodes transmitting location estimation signals.

6. The method of claim 5, wherein the identifying the plurality of beacon node groups further comprises:

formulating a graph coloring problem, wherein individual vertices of a graph represents a corresponding beacon node, wherein an edge between two vertices of the graph represents a condition associated with the pair of beacon nodes, and wherein the condition is based at least in part on the identified at least one of the likelihood of interference or collision at the communication node; and

solving the graph coloring problem to determine the plurality of beacon node groups.

7. The method of claim 1, further comprising:

determining the schedule for the placed beacon node to be active, based at least in part on reducing the waiting time of individual communication nodes to receive location determination signals.

8. The method of claim 1, wherein the determining the at least one of the number or location comprises:

determining a minimum number of beacon nodes required to be placed.

9. The method of claim 1, wherein the determining the at least one of the number or location comprises:

determining the at least one of the number or location of beacon nodes to be placed, based at least in part on reducing a likelihood of location discovery error for discovering locations of the representative communication nodes using the placed beacon nodes.

10. The method of claim 9, wherein the determining the at least one of the number or location further comprises:

determining the likelihood of location discovery error from a location discovery model that models correlation between a number of neighboring nodes of a communication node and a likelihood of location discovery error of the communication node.

11. An apparatus, comprising:

a memory that stores a plurality of programming instructions; and

a processor coupled to the memory and configured to execute the plurality of programming instructions to enable the apparatus, in response to execution of the plurality of programming instructions, to;

group one or more of a plurality of communication nodes into a plurality of communication node groups, wherein communication nodes in individual communication node groups of the plurality of communication node groups are in proximity;

select a representative communication node from each of the individual communication node groups, the selected representative communication nodes of the plurality of communication node groups forming a dominating set of communication nodes; and

determine a number and locations of beacon nodes to be placed in a terrain, based at least in part on an individual representative communication node receiving a signal from a plurality of beacon nodes;

wherein the selecting comprises formulating and solving an objective function to minimize a number of the selected representative communication nodes in the dominating set of communication nodes; and

wherein each node in the dominating set of communication nodes is configured to receive signals from a same set of three neighboring beacon nodes.

12. The apparatus of claim 11, wherein in response to execution of the programming instructions, the apparatus is further enabled to:

determine the at least one of the number or location of the beacon node to be placed, based at least in part on reducing a likelihood of location discovery error for discovering locations of one or more of the plurality of communication nodes using the placed beacon node; and

determine a schedule for the placed beacon nodes to be active, based at least in part on a waiting time of individual communication nodes to receive a location determination signal from one or more beacon nodes.