A Linear Programming Algorithm for Wireless Sensor Networks Localization

Wireless sensor networks are widely applied in many fields. Sensor node localization problem is the basis and prerequisite for most applications. A linear programming algorithm is presented for wireless sensor networks localization. The received signal strength indications (RSSI) and empirical radio propagation model are used to deduce the relationships of the distances between communicable node pairs in a wireless sensor network. And the communication range is used to estimate the distances between communicable paired nodes. These estimated distances are modeled as a set of square constraints by approximating circle to square. And a linear programming problem for these constraints is employed to substitute the programming problem with quadric constraints. A global solution of the linear programming problem yields estimations for the unknown node positions. Then the node ordinatets are obtained. Simulation results show that preferable localization accuracy can be achieved when anchors are distributed near the fringe of the networks. Some analyses are made to validate the influences of anchor distribution, the number of anchors, and the connectivity on the localization error. Furthermore, compared with the convex position estimation for sensor node localization, the linear programming localization algorithm enormously declines the times for solving programming problems, and has smaller localization error when with the same simulation conditions.