Patent ID: 8369242

Claim:
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.