A Cluster-Based MDS Scheme for Range-Free Localization in Wireless Sensor Networks

A wide range of applications used on wireless sensor networks requires the location information of sensor nodes. Some conventional localization techniques employ GPS or other location-tracking devices installed on sensor nodes. On the other hand, other methods provide location information by taking into account node connectivity only. One example of such methods is a multidimensional scaling-MAP (MDS-MAP), which provides the most accurate location information to date. MDS-MAP, however, has a computational overhead of O(n³) in a network of n nodes and also it intrinsically generates significant localization accuracy error in an environment with holes. This paper proposes a cluster-based MDS scheme for range-free localization, CMDS for short, which addresses the shortcomings of MDS-MAP and yields higher accuracy in all environments. Simulation results demonstrate that in a sensor network environment with holes, the proposed scheme gives up to 23% improvement in localization accuracy over hierarchical MDS (HMDS), which is an enhanced version of the conventional MDS-MAP.