求解无线传感器网络定位问题的线性规划算法

A Linear Programming Algorithm for Wireless Sensor Networks Localization

传感器节点的定位问题是无线传感器网络中的基础性问题之一.提出了一种线性规划算法用于求解无线传感器网络定位问题.该算法利用RSSI值和经验的无线信号传播模型推导出所有可通信节点间距离的相对关系,利用节点的通信半径估算出可通信节点间的距离,并以此为约束条件利用矩形近似圆形,将二次约束的规划问题转化为线性规划问题;求解该线性规划问题便可得未知节点坐标.通过仿真实验,证明了当锚节点分布在网络边缘时该算法能得到较好的定位效果,分析了锚节点分布、锚节点个数、网络连通度等实验参数对定位结果的影响.相比凸规划定位算法,该算法大大降低了求解规划问题的次数,且在相同的实验条件下定位误差更小.

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.