A comparison of multidimensional scaling and non-linear regression for positioning applications.
For locating a set of stationary devices, algorithms such as MDS-MAP have been favoured by the sensor network community [4,5] because of their low computational complexity. Whilst comparisons for complexity and performance have been done for other algorithms, non-linear regression has been neglected. The authors find that it is not much more expensive, and can yield significantly better accuracy for sensor network localisation.
Algorithms
MDS-MAP [4] takes a block of measurements and calculates the NxN matrix of dissimilarities, which is the distances between each pair of devices. Those which are missing (i.e. which are not available via direct sensor measurement) are then filled in using a shortest-path algorithm, such as Floyd-Warshall. Once the dissimilarity matrix is complete, multidimensional scaling is performed which reduces the NxN matrix into a 2xN coordinate space using a form of isotonic regression.
Non-linear regression is a model-based fitting algorithm which takes the given measurements by a device and then, using a minimisation function such as Levenburg-Marquardt [3], performs non-linear least squares to produce a solution which best fits the model. This works by iteratively regressing the solution until the residual squared error is lower than a given threshold. For our localisation scenarios we have found the number of iterations to be between 3 and 7.
Complexity
MDS-MAP requires two main operations: computing shortest paths, and multidimensional scaling. If we take k as the number of devices in a neighbourhood, the complexity of the Floyd-Warshall shortest path algorithm is 
. Multidimensional scaling has a time complexity of 
, mostly stemming from eigenvalue decomposition. This brings the overall time complexity of MDS-MAP to 
as found by Bischoff et al [1]
Non-linear regression using Levenburg-Marquardt can be implemented efficiently using well-known algorithms, such as those outlined in Numerical Recipes in C. Using code analysis, the time complexity was found to be 
, where k is the number of nodes in the neighbourhood.
From the above comparison it is easy to see that non-linear regression is almost 8 times more expensive than MDS-MAP, in terms of the total number of operations required. But it is worth noting that MDS-MAP is limited to distance measures only. Non-linear regression uses parametric modelling and as such can use any mixture of metrics, such as range (time difference of arrival), pseudorange (time of arrival), and bearing (angle of arrival), to augment its solution.
Empirical comparison from sensor node data
Using data gathered from experiments using our custom ultrasonic devices [1]. Operating in round-robin fashion, each node transmits an ultrasonic pulse, while the other nodes measure and report the estimated range. MDS-MAP and non-linear regression algorithms were executed and their results compared. Measurements were taken in a 2.75 x 2.00 m arena (below, left) with a camera-based ground truth capture system (accurate to several millimetres) in place. The graph (below, right) is the cumulative localisation error distribution of a five nodes, placed in five randomly generated spatial layouts.
As the graph shows, the ninetieth percentile error of MDS-MAP is 27.5 cm with a median error of 5 cm, whilst non-linear regression has a ninetieth percentile error of 3.8 cm with a median error of 1.9 cm. An interesting point of note is the "long tail" of the distribution for MDS-MAP. The ninetieth percentile error of non-linear regression is better than the median of MDS-MAP, and the ninety-fifth percentile error of MDS-MAP is about half a metre.
With a much finer grain accuracy, non-linear regression seems a more flexible choice, especially with its support for many different measurement types our platform can also supply bearing measurements. Depending on the application, the poorer accuracy of MDS-MAP may not be worth its one-eighth computational complexity.
- Bischoff, U., Strohbach, M., Hazas, M., and Kortuem, G. Wireless Sensor Networks. Springer-Verlag, Berlin/Heidelberg, 2006.
- Decker, C., Krohn, A., Beigl, M., and Zimmer, T. The particle computer system. Information Processing in Sensor Networks, 2005. IPSN 2005. Fourth International Symposium on, IEEE (2005), 443–448.
- Lourakis, M. A Brief Description of the Levenberg-Marquardt Algorithm Implemened by levmar. Matrix 3, (2005), 2.
- Shang, Y. and Ruml, W. Improved MDS-based localization. Proc of INFOCOM 2004.
- Whitehouse, K. and Culler, D. A robustness analysis of multi-hop ranging-based localization approximations. Proceedings of the 5th international conference on Information processing in sensor networks, ACM (2006), 325.