Efficient location discovery

A method for adding one or more beacon nodes to a wireless network with a plurality of communication nodes, comprising:

• first selecting by a computing device, a grid location among a plurality of grid locations in the wireless network;
• determining by the computing device, an expected improvement to a location discovery error of the plurality of communication nodes in the wireless network if a new beacon node is added to the grid location;
• repeating by the computing device, said first selecting and determining for individual grid locations of at least a portion of the plurality of grid locations, until expected improvement to location discovery errors has been determined corresponding to the individual grid locations of at least the portion of the plurality of grid locations;
• and
• second selecting by the computing device, one of the grid locations from at least the portion of the plurality of grid locations to add a new beacon node, based at least in part on the determined expected improvement to location discovery errors corresponding to the individual grid locations of at least the portion of the plurality of grid locations.

A method for simultaneously adding N new nodes to a network comprising a plurality of communication nodes, location of one or more of which is unknown, and a plurality of beacon nodes, location of one or more of which is known, the method comprising:

• forming by a computing device, an objective function indicative of the number of new nodes to be added to the network;
• solving by the computing device, a minimization of the objective function subject to one or more of:
• a new node not being added to a location where a node pre-exists;
• individual existing nodes having at least three neighbors that includes existing and/or added new nodes;
• and
• individual added new nodes having at least three neighbors that includes existing and/or added new nodes.

An article of manufacture comprising:

• a computer readable storage medium;
• a first plurality of programming instructions stored in the computer readable storage medium, and configured to implement a distance measurement error model comprising a plurality of monotonic piece-wise linear functions, to permit an apparatus to model errors in estimating distance measurement between a communication node and a beacon node of a wireless network;
• and
• a second plurality of programming instructions stored in the computer readable storage medium, and configured to implement a distance calculation error model based at least in part on modeled location discovery errors at two nodes, to permit an apparatus to model distance calculation error between the two nodes.

An apparatus arranged to determine locations of individual communication devices that are in a wireless network with one or more beacon nodes, the apparatus comprising:

• a memory arranged to store programming instructions;
• and
• a processor coupled to the memory and configured by the programming instructions to:
• identify known locations associated with one or more of the beacon nodes;
• identify attributes associated with individual communication devices and one or more beacon nodes whose locations are known;
• formulate a determination of locations of one or more of the individual communication devices as a quantitative problem based at least in part on the identified attributes, wherein the quantitative problem is expressed in terms of an objective function, one or more constraints, and one or more models;
• and
• calculate a solution to the quantitative problem to determine the location of one or more of the individual communication devices, wherein the solution includes manipulation of at least one of the objective function, one of the one or more constraints or one of the one or more models.

An apparatus arranged to add one or more beacon nodes to a wireless network with a plurality of communication nodes, the apparatus comprising:

• a memory arranged to store programming instructions;
• and
• a processor coupled to the memory and configured by the programming instructions to:
• first select a grid location among a plurality of grid locations in the wireless network;
• determine an expected improvement to a location discovery error of a plurality of communication nodes in the wireless network if a new beacon node is added to the grid location;
• repeat said first selecting and determining for individual grid locations of at least a portion of the plurality of grid locations, until expected improvement to location discovery errors has been determined corresponding to the individual grid locations of at least the portion of the plurality of grid locations;
• and
• second select one of the grid locations from at least the portion of the plurality of grid locations to add a new beacon node, based at least in part on the determined expected improvement to location discovery errors corresponding to the individual grid locations of at least the portion of the plurality of grid locations.

An apparatus arranged to simultaneously add N beacon nodes to a network with a plurality of communication nodes locations of which are unknown, and a plurality of beacon nodes location of one or more of which are known, the apparatus comprising:

• a memory arranged to store programming instructions;
• and
• a processor coupled to the memory and configured by the programming instructions to:
• form an objective function indicative of the number of new nodes to be added to the network;
• and
• solve a minimization of the objective function subject to one or more of:
• a new node not being added to a location where a node pre-exists;
• individual existing nodes having at least three neighbors that includes existing and/or added new nodes;
• and
• individual added new nodes having at least three neighbors that includes existing and/or added new nodes.