Patent ID: 8401560

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