Infrastructure for location discovery
AssigneeEmpire Technology Development LLC
InventorMiodrag Potkonjak
Life of this patent
Estimating the term…
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.
Claims24
A method for a computing device to create a location discovery infrastructure (LDI) for estimating locations of one or more of a plurality of communication nodes in a terrain, comprising:
- finding a plurality of locations in the terrain to place a corresponding plurality of beacon nodes, 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 nodes;
- identifying a plurality of beacon node groups for the placed beacon nodes, based at least in part on the placed beacon nodes within individual beacon node groups being able to be active simultaneously without causing interference or collision at individual communication nodes of the plurality of communication nodes;
- and
- determining 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 location determination signals from one or more beacon nodes.
A method for a computing device to create a location discovery infrastructure (LDI) for estimating locations of one or more of a plurality of communication nodes in a terrain, comprising:
- grouping one or more of the plurality of communication nodes into a plurality of communication node groups, such that the communication nodes in individual communication node groups are in proximity and have approximately no obstacles in between;
- selecting a representative communication node from 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 a number and locations of beacon nodes to be placed in the terrain, based at least in part on individual representative communication nodes receiving signals from at least three beacon nodes.
A method for a computing device to group a plurality of beacon nodes, wherein signals from one or more of the plurality of beacon nodes is used for estimating locations of one or more of a plurality of communication nodes, the method comprising:
- identifying a likelihood of interference or collision at one or more communication nodes when two beacon nodes of a pair of beacon nodes from the plurality of beacon nodes simultaneously transmit location estimation signals;
- and
- 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 two associated beacon nodes transmitting signals simultaneously, and wherein the condition is based at least in part on the identified likelihood of interference of collision at the one or more communication nodes when the two associated beacon nodes simultaneously transmit location estimation signals.
A method for a computing device to group a plurality of beacon nodes, wherein signals from one or more of the plurality of beacon nodes is used for estimating locations of one or more of a plurality of communication nodes, the method comprising:
- identifying a likelihood of interference or collision at one or more communication nodes when two beacon nodes of a pair of beacon nodes from the plurality of beacon nodes simultaneously transmit location estimation signals;
- and
- determining a plurality of beacon node groups for the plurality of beacon nodes, based at least in part on the beacon nodes within individual beacon node groups being able to be active simultaneously without causing interference or collision at individual communication nodes of the plurality of communication nodes, wherein determining the plurality of beacon nodes groups is based at least in part on identifying the likelihood of inference or collision.
A method for a computing device to schedule signal transmission of a plurality of beacon nodes, wherein signals from one or more of the plurality of beacon nodes is used for estimating locations of one or more of a plurality of communication nodes, and wherein individual communication nodes receive signals from at least three beacon nodes, the method comprising:
- formulating an objective function based at least in part on waiting times of individual communication nodes for receiving location determination signals from the plurality of beacon nodes;
- and
- solving the objective function to determine a schedule for signal transmission of the plurality of beacon nodes.
An apparatus for creating a location discovery infrastructure (LDI) for estimating locations of one or more of a plurality of communication nodes in a terrain, comprising:
- a memory that stores a plurality of programming instructions;
- and
- a processor coupled to the memory and configured by the programming instructions to:
- find a plurality of locations in the terrain to place a corresponding plurality of beacon nodes, 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 nodes;
- identify a plurality of beacon node groups for the placed beacon nodes, based at least in part on the placed beacon nodes within individual beacon node groups being able to be active simultaneously without causing interference or collision at individual communication nodes of the plurality of communication nodes;
- 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 location determination signals from one or more beacon nodes.
An apparatus for creating a location discovery infrastructure (LDI) for estimating locations of one or more of a plurality of communication nodes in a terrain, comprising:
- a memory that stores a plurality of programming instructions;
- and
- a processor coupled to the memory and configured by the programming instructions to:
- group one or more of the plurality of communication nodes into a plurality of communication node groups, such that the communication nodes in individual communication node groups are in proximity and have approximately no obstacles in between;
- select a representative communication node from 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 the terrain, based at least in part on individual representative communication nodes receiving signals from at least three beacon nodes.
An apparatus for grouping a plurality of beacon nodes, wherein signals from one or more of the plurality of beacon nodes is used for estimating locations of one or more of a plurality of communication nodes, the apparatus comprising:
- a memory that stores a plurality of programming instructions;
- and
- a processor coupled to the memory and configured by the programming instructions to:
- identify a likelihood of interference or collision at one or more communication nodes when two beacon nodes of a pair of beacon nodes from the plurality of beacon nodes simultaneously transmit location estimation signals;
- and
- formulate 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 two associated beacon nodes transmitting signals simultaneously, and wherein the condition is based at least in part on the identified likelihood of interference of collision at the one or more communication nodes when the two associated beacon nodes simultaneously transmit location estimation signals.
An apparatus for scheduling signal transmission of a plurality of beacon nodes, wherein signals from one or more of the plurality of beacon nodes is used for estimating locations of one or more of a plurality of communication nodes, and wherein individual communication nodes receive signals from at least three beacon nodes, the apparatus comprising:
- a memory that stores a plurality of programming instructions;
- and
- a processor coupled to the memory and configured by the programming instructions to:
- formulate an objective function based at least in part on waiting times of individual communication nodes for receiving location determination signals from a plurality of beacon nodes;
- and
- solve the objective function to determine a schedule for signal transmission of the plurality of beacon nodes.
Dependencies are inferred from the claim text.