Infrastructure for location discovery
View Patent ↗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.
1. 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, by the computing device, the one or more of the plurality of communication nodes into a plurality of communication node groups, such that communication nodes in individual communication node groups are in proximity and have approximately no obstacles in between;
selecting, by the computing device, a representative communication node from 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 the terrain, based at least in part on individual representative communication nodes receiving signals from at least three beacon nodes;
wherein S={S i },i=1, . . . , N s denote the plurality of communication nodes to be divided into a plurality of communication node groups; and
wherein the selecting comprises formulating and solving an objective function (OF) as follows:
OF
:
min
∑
i
=
1
N
s
d
i
such
that
:
∑
j
=
1
N
s
d
j
E
ij
≥
1
,
i
=
1
,
…
,
N
S
,
E
ij
=
{
1
,
if
communication
nodes
Si
and
Sj
receive
signals
from
same
set
of
three
or
more
beacon
nodes
0
,
otherwise
,
and
d
i
=
{
1
,
if
communication
nodes
Si
is
selected
in
the
dominating
set
0
,
otherwise
.
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 nodes; and
wherein the method further comprises determining, by the computing device, 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.
3. The method of claim 1 ,
wherein the determining is further based at least in part on individual representative communication nodes receiving signals from at least four of the placed beacon nodes.
4. The method of claim 1 , further comprising:
identifying, for individual pairs of the placed beacon nodes, a likelihood of interference or collision at one or more communication nodes when two beacon nodes of a pair of beacon nodes simultaneously transmits location estimation signals.
5. The method of claim 4 , wherein the identifying further comprises:
formulating a graph coloring problem, wherein individual vertices of a graph represent a corresponding beacon node, wherein an edge between two vertices of the graph represent a condition associated with the two associated beacon nodes transmitting signals simultaneously, and wherein the condition is based at least in part of identifying the likelihood of interference or collision for the two beacon nodes; and
solving the graph coloring problem to determine the plurality of beacon node groups.
6. The method of claim 1 , wherein the determining the schedule comprises:
determining the schedule for the placed beacon nodes to be active, based at least in part on reducing the waiting time of individual communication nodes to receive location determination signals from one or more beacon nodes.
7. The method of claim 1 , wherein the determining the number and locations comprises:
determining a minimum number of beacon nodes required to be placed in the terrain.
8. The method of claim 1 , wherein the determining the number and locations comprises:
determining the number and locations of beacon nodes to be placed in a terrain, 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.
9. The method of claim 8 , wherein determining the number and locations 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.
10. 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 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 the plurality of communication nodes into a plurality of communication node groups, such that communication nodes in individual communication node groups are in proximity and have approximately no obstacles in between;
select a representative communication node from 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 the terrain, based at least in part on individual representative communication nodes receiving signals from at least three beacon nodes;
wherein S={S i },i=1, . . . , N s denote the plurality of communication nodes to be divided into a plurality of communication node groups; and
wherein selecting comprises solving an objective function (OF) as follows:
OF
:
min
∑
i
=
1
N
s
d
i
such
that
:
∑
j
=
1
N
s
d
j
E
ij
≥
1
,
i
=
1
,
…
,
N
S
,
E
ij
=
{
1
,
if
communication
nodes
Si
and
Sj
receive
signals
from
same
set
of
three
or
more
beacon
nodes
0
,
otherwise
;
and
d
i
=
{
1
,
if
communication
nodes
Si
is
selected
in
the
dominating
set
0
,
otherwise
.
11. The apparatus of claim 10 , wherein in response to execution of the programming instructions, the apparatus is further enabled to:
determine the number and locations of beacon nodes to be placed in the terrain, 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; 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.