Scalable sensor localization for wireless sensor networks

An apparatus for use with a wireless sensor network, the wireless sensor network including a plurality of nodes, the nodes including sensors with unknown locations and anchor sensors with known locations, wherein each node comprises a network interface operable to exchange data with one or more other nodes, the apparatus comprising:

• a network interface for communicating with one or more nodes;
• and
• a compute engine coupled to said network interface and executing computer instructions to perform a method including the acts of:
• obtaining pair-wise distance measurements between a sensor whose location is unknown and an anchor sensor whose location is known and between sensors whose locations are unknown;
• formulating a subproblem to include a subset of anchor sensors whose locations are known and to further include a subset of sensors whose locations are unknown, including setting a maximum number of sensors to be included in the subset of sensors;
• determining a location of at least one of the sensors in the subset of sensors within a tolerable error by solving the subproblem;
• classifying the at least one sensor whose location has been determined within a tolerable error as a new anchor sensor;
• and
• iteratively repeating the acts of formulating, determining, and classifying.