Localization of Distributed Wireless Sensor Networks using Two Sage SDP Optimization

Abstract

A wireless sensor network (WSN) may comprise a large distributed set of low cost, low power sensing nodes. In many applications, the location of sensors is a necessity to evaluate the sensed data and it is not energy and cost efficient to equip all sensors with global positioning systems such as GPS. In this paper, we focus on the localization of sensors in a WSN by solving an optimization problem. In WSN localization, some sensors (called anchors) are aware of their location. Then, the distance measurements between sensors and anchors locations are used to localize the whole sensors in the network. WSN localization is a non-convex optimization problem, however, relaxation techniques such as semi-definite programming (SDP) are used to relax the optimization. To solve the optimization problem, all constraints should be considered simultaneously and the solution complexity order is O(n2) where n is the number of sensors. The complexity of SDP prevents solving large size problems. Therefore, it would be beneficial to reduce the problem size in large and distributed WSNs. In this paper, we propose a two stage optimization to reduce the solution time, while provide better accuracy compared with original SDP method. We first select some sensors that have the maximum connection with anchors and perform the SDP localization. Then, we select some of these sensors as virtual anchors. By adding the virtual anchors, we add more reference points and decrease the number of constraints. We propose an algorithm to select and add virtual anchors so that the total solution complexity and time decrease considerably, while improving the localization accuracy.