Efficient location discovery
Techniques are generally described for determining locations of a plurality of communication devices in a network. In some examples, methods for determining locations of a plurality of communication devices in a network may comprises formulating the determination as a quantitative problem based at least in part on one or more attributes between individual communication devices and one or more beacon nodes whose locations are known, wherein the quantitative problem is expressed in terms of an objective function, one or more constraints, and one or more models, and solving the quantitative problem to determine the location of at least a portion of the one or more communication devices, wherein the solving includes manipulation of at least the objective function, one of the one or more constraints or one of the one or more models. Additional variants and embodiments are also disclosed.
1. A method for determining respective locations of a plurality of communication devices, comprising:
formulating, by a computing device, the determining of the respective locations as a quantitative problem based at least in part on estimated distances between individual communication devices and neighboring beacon nodes whose locations are known, wherein the quantitative problem is expressed in terms of a non-linear objective function, wherein the non-linear objective function is to minimize a total amount of error according to a location discovery error model; and
solving, by the computing device, the quantitative problem to determine the respective locations of the plurality of communication devices, wherein the solving includes solving a linearized approximation of the non-linear objective function;
wherein the non-linear objective function is
OF: min M (ε i ),
wherein ε i =√{square root over ((X Bi −X s ) 2 +(Y Bi −Y s ) 2 )}{square root over ((X Bi −X s ) 2 +(Y Bi −Y s ) 2 )}−d is '
wherein X Bi , Y Bi are X and Y coordinates of beacon node Bi,
X s , Y s are X and Y coordinates of communication node s,
D is is the estimated distance between the beacon node Bi and the communication node s,
ε i is an amount of error between the estimated distance and a measured distance between a communication node and the i th beacon node, and
M(ε i ) is an expected location discovery error according to the location discovery error model;
wherein the solving comprises:
solving a piece-wise linear approximation of the non-linear objective function, by solving
OF
:
min
L
i
=
1
,
…
,
N
(
ɛ
i
)
such
that
C
i
ɛ
i
+
C
j
ɛ
j
=
C
ij
+
B
x
X
S
+
B
y
Y
S
for
all
{
i
=
1
,
…
,
N
B
j
=
1
,
…
,
N
B
i
≠
j
wherein L is the piece-wise linear approximation applied on the measurement error,
C i , C j , and C ij are constants,
B x =(X Bj −X Bi ),
B y =(Y Bj −Y Bi ), and
N B is the number of beacon nodes.
2. The method of claim 1 , wherein the formulating comprises:
formulating the determining of the respective locations based at least in part on the estimated distances between the individual communication devices and at least three non-collinear neighboring beacon nodes whose locations are known.
3. The method of claim 1 , wherein the formulating and the solving are performed for one communication device at a time.
4. The method of claim 1 , wherein the formulating and the solving are performed for a plurality of communication devices simultaneously, employing non-linear programming and a one-dimensional search.
5. The method of claim 1 , wherein the formulating comprises:
identifying a subset of the plurality of communication devices and the neighboring beacon nodes such that communication device or devices in the subset have probabilities of relatively lower location discovery error as compared to communication device or devices that are not in the subset; and
formulating the determining of the respective locations, based at least in part on estimated distances between the communication device or devices in the identified subset and the neighboring beacon nodes in the identified subset.
6. An apparatus, comprising:
means for formulating a determination of locations of a plurality of communication devices as a quantitative problem based at least in part on estimated distances between individual communication devices and neighboring beacon nodes whose locations are known, wherein the quantitative problem is expressed in terms of a non-linear objective function, wherein the non-linear objective function is to minimize a total amount of error according to a location discovery error model; and
means for solving the quantitative problem to determine the locations of the plurality of communication devices, wherein the solving includes solving a linearized approximation of the non-linear objective function;
means for formulating comprises means for formulating the non-linear objective function as:
OF : min M (ε i ),
wherein ε i =√{square root over ((X Bi −X s ) 2 +(Y Bi −Y s ) 2 )}{square root over ((X Bi −X s ) 2 +(Y Bi −Y s ) 2 )}−d is
wherein X Bi , Y Bi are X and Y coordinates of beacon node Bi,
X s , Y s are X and Y coordinates of communication node s,
d is is the estimated distance between the beacon node Bi and the communication node s,
ε i is an amount of error between the estimated distance and a measured distance between a communication node and the i th beacon node, and
M(ε i ) is an expected location discovery error according to the location discovery error model; and
the means for solving comprises means for solving a piece-wise linear approximation of the non-linear objective function, by solving
OF
:
min
L
i
=
1
,
…
,
N
(
ɛ
i
)
such
that
C
i
ɛ
i
+
C
j
ɛ
j
=
C
ij
+
B
x
X
S
+
B
y
Y
S
for
all
{
i
=
1
,
…
,
N
B
j
=
1
,
…
,
N
B
i
≠
j
wherein L is the piece-wise linear approximation applied on the measurement error,
C i , C j , and C ij are constants,
B X =(X Bj −X Bi ) 2
B y =(Y Bj −Y Bi ), and
N B is the number of beacon nodes.