Source-linked AI summary
A State-of-the-Art Survey on Multidimensional Scaling Based Localization Techniques
Nasir Saeed, Haewoon Nam, Tareq Y. Al-Naffouri, Mohamed-Slim Alouini
TL;DR
Wireless localization must operate accurately across outdoor, indoor, harsh, and modern network environments, where GPS is insufficient. This survey synthesizes MDS and MDS-based localization methods across wireless networks and compares centralized, semi-centralized, and distributed approaches, with distributed methods showing lower localization error in the reported scenarios.
Problem
Reliable real-time localization is needed across wireless applications, but GPS fails indoors and in harsh environments while range-based methods can require costly hardware.
Method
The paper comprehensively surveys MDS, ranging techniques, localization systems, and MDS-based methods across WSNs, IoT, cognitive radio networks, and 5G networks.
Results
Distributed MDS-based methods achieve lower reported average localization error than centralized and semi-centralized methods, including 0.15 m versus 2.21 m and 1.2 m, respectively.
Takeaways & Limitations
MDS-based localization provides a common framework for range-free and range-based schemes and supports localization analysis across diverse wireless networks and applications.
Abstract
from arXiv · showhide
Current and future wireless applications strongly rely on precise real-time localization. A number of applications such as smart cities, Internet of Things (IoT), medical services, automotive industry, underwater exploration, public safety, and military systems require reliable and accurate localization techniques. Generally, the most popular localization/ positioning system is the Global Positioning System (GPS). GPS works well for outdoor environments but fails in indoor and harsh environments. Therefore, a number of other wireless local localization techniques are developed based on terrestrial wireless networks, wireless sensor networks (WSNs) and wireless local area networks (WLANs). Also, there exist localization techniques which fuse two or more technologies to find out the location of the user, also called signal of opportunity based localization. Most of the localization techniques require ranging measurements such as time of arrival (ToA), time difference of arrival (TDoA), direction of arrival (DoA) and received signal strength (RSS). There are also range-free localization techniques which consider the proximity information and do not require the actual ranging measurements. Dimensionality reduction techniques are famous among the range free localization schemes. Multidimensional scaling (MDS) is one of the dimensionality reduction technique which has been used extensively in the recent past for wireless networks localization. In this paper, a comprehensive survey is presented for MDS and MDS based localization techniques in WSNs, Internet of Things (IoT), cognitive radio networks, and 5G networks.
I. INTRODUCTION
The introduction motivates reliable localization beyond GPS and positions MDS as a versatile approach for wireless networks. The survey consolidates positioning systems, ranging methods, MDS variants, applications, and comparative findings.
- Indoor and harsh environments challenge GPS because obstacles, multipath propagation, and interference degrade localization.
- Range-free localization reduces hardware and cost requirements by using connectivity or proximity information instead of actual ranges.
- MDS converts multidimensional data into lower-dimensional space while preserving essential information and using similarity or dissimilarity relationships.
- A. Related Surveys: Existing surveys are narrow, outdated, or incomplete, motivating comprehensive coverage of positioning systems and MDS-based localization.
- B. Survey Organization: The survey covers outdoor and indoor positioning, ranging techniques, MDS methods, wireless-network applications, comparisons, and prospective uses.
A. Global Positioning Systems
Global positioning systems use satellites to provide outdoor location information through systems including GPS, GLONASS, GALILEO, and BeiDou. The section describes their coverage, accuracy, interoperability, and positioning roles.
- Global positioning systems provide location information from satellites, with outdoor accuracy of a few meters and coverage from multiple systems.
- GPS uses 28 operational satellites to estimate longitude, latitude, and altitude with accuracy of a few meters.
- GLONASS provides an alternative to GPS, with accuracy up to 2 meters and improved coverage and accuracy when both systems operate together.
- GALILEO provides a civilian-controlled global positioning facility and interoperates with GPS and GLONASS.
- BeiDou, also called COMPASS, provides global accuracy up to 10 meters and Asia-Pacific accuracy up to 5 meters.
2) Environment:
Local positioning systems are organized by environment and transmission medium, spanning outdoor, indoor, underwater, RF, acoustic, and optical systems. Their capabilities and constraints depend on propagation conditions, infrastructure, and device requirements.
- Outdoor LPS: Outdoor positioning commonly uses GPS, but power constraints, cost, and unsatisfactory accuracy limit its use for small sensor devices.
- Indoor LPS: Indoor positioning is difficult because obstacles, signal fluctuations, noise, environmental changes, and non-line-of-sight communication affect propagation.
- Underwater LPS: Underwater localization depends on topology, ranging method, energy requirements, device capabilities, propagation losses, and anchor deployment.
- Transmission Medium: RF positioning includes cellular, WLAN, and RFID systems, with WLAN systems benefiting from established infrastructure and reported accuracy of 2 to 3 meters.
- Transmission Medium: Acoustic systems can provide three-dimensional localization using triangulation and time-of-arrival measurements.
- Transmission Medium: Optical positioning includes VLC and infrared systems, but multipath reflections, synchronization, line-of-sight dependence, coverage, and privacy remain concerns.
C. Fundamental Ranging Schemes
The section reviews ranging schemes that estimate distances from propagation time, time differences, received power, or radio fingerprints. Each approach uses different measurements and faces distinct channel or deployment constraints.
- ToA Estimation: ToA estimates distance from signal propagation delay, but multipath arrivals and the presumed line-of-sight signal complicate measurements.
- TDoA Estimation: TDoA estimates distance from two signals and locates nodes where anchor-derived hyperbolas intersect, without requiring anchor-node synchronization.
- RSS Estimation: RSS estimates distance from received power using path-loss models, while fading and shadowing affect the measurements.
- RSS Estimation: At reference distance d0, Pr(d0) denotes received power and η denotes the path-loss exponent.
- Fingerprinting: Fingerprinting localizes users by matching measured RSS values against a database collected during training at known locations.
5) Direction of Arrival (DoA) Technique:
The survey introduces MDS as a dimensionality-reduction approach and reviews its use in localization across wireless networks. It also describes MDS processing, loss functions, and limitations relevant to localization.
- A. What is MDS?: MDS converts higher-dimensional data into lower-dimensional space while preserving essential information and enabling graphical interpretation.It uses similarity or dissimilarity information to construct a spatial map.
- A. What is MDS?: MDS methods are specified by loss functions that relate measured dissimilarities to Euclidean distances, including raw stress and Kruskal stress.SMACOF is described as an iterative majorization approach for solving the loss function.
- A. What is MDS?: Traditional MDS assumes symmetric object distances, but similarity or dissimilarity can be asymmetric in some applications.Asymmetric MDS methods address cases where similarity depends on object-associated quantities as well as inter-point distances.
- A. What is MDS?: MDS maps a symmetric n × n distance-affinity matrix into d-dimensional coordinates whose estimated Euclidean distances match the input distances.The distance matrix is converted into an inner-product kernel matrix, then eigenvectors and eigenvalues provide the solution.
- MDS-based localization: MDS constructs node configurations from inter-node distances, producing two- or three-dimensional representations of wireless-network deployments.Classical MDS can use shortest-path distances as input and derive relative locations from dominant eigenvalues and eigenvectors.
- MDS-based localization: Localization converts relative MDS coordinates into global positions using anchor nodes and rigid Euclidean transformations.The transformation includes rotation, translation, and reflection.
B. Centralized MDS Based Localization
Centralized MDS localization estimates pairwise distances, applies MDS through double centering and eigenvalue decomposition, and transforms relative coordinates into global positions.
- Distance-affinity construction: Centralized MDS begins by estimating shortest-path distances between node pairs to construct a distance affinity matrix.Dijkstra or Floyd–Warshall algorithms can estimate multi-hop distances.
- Distance-affinity construction: Noisy direct distances combine Euclidean separation with ranging error modeled as a zero-mean Gaussian variable.The error variance depends on distance and η^2.
- MDS coordinate estimation: MDS minimizes discrepancies between estimated and Euclidean distances using a nonlinear, nonconvex stress function.Double centering is then used to obtain a closed-form solution.
- MDS coordinate estimation: Eigenvalue decomposition of the double-centered matrix yields relative two-dimensional coordinates from the two largest eigenvalues and eigenvectors.The resulting coordinates are relative rather than absolute.
- Global coordinate transformation: Linear transformations such as Procrustes analysis, Helmert transformation, or principal coordinate analysis convert relative estimates into global positions.This alignment step addresses the lack of absolute positioning in the MDS output.
C. Semi-centralized MDS Based Localization
Semi-centralized MDS divides the network into clusters, computes local maps, and stitches them into a global configuration while reducing the matrix size and computational burden.
- Motivation: Semi-centralized methods address the high complexity and irregular-network error associated with centralized MDS.The survey characterizes them as more robust and accurate with lower complexity.
- Cluster formation: Networks are clustered, and each cluster selects a cluster head using criteria such as energy consumption or neighborhood size.k-means, density-based, and fuzzy clustering are listed as possible approaches.
- Local map construction: Each cluster head computes shortest-path distances among its members and constructs a local distance affinity matrix.The matrix contains pairwise squared estimated distances for the cluster’s nodes.
- Local map construction: Applying MDS to each local matrix produces relative node positions through double centering and eigenvalue decomposition.The double-centered matrix is c×c rather than n×n, and the two largest eigenpairs provide two-dimensional coordinates.
- Map stitching: Local maps are stitched using inter-cluster nodes, alignment matrices, and reconstruction-error minimization before extracting global relative coordinates.At least three inter-cluster nodes are required to stitch two neighboring clusters; linear transformations can then produce absolute positions.
- Global alignment: The global relative coordinates are obtained from the two largest eigenvectors and eigenvalues, then transformed into absolute positions.Procrustes analysis, Helmert transformation, or principal coordinate analysis can perform the final transformation.
D. Distributed MDS Based Localization
Distributed MDS lets nodes estimate positions through local measurements and local cost minimization, avoiding dependence on a central bottleneck and supporting mobile networks.
- Distributed estimation: In distributed MDS, each node measures ranges to neighbors and updates its location by minimizing a local cost function.The approach follows steps similar to centralized and semi-centralized MDS schemes.
- Distributed estimation: Anchor-based formulations use the number of anchors and estimated node-to-anchor distances in the localization error model.L denotes the total number of anchors, while d̂_il is the estimated distance between node i and anchor l.
- Mobility support: Distributed MDS avoids the centralized bottleneck by minimizing local rather than global costs, which supports changing network topologies and mobility.The survey also associates distributed methods with lower complexity and better accuracy.
- Mobility support: Mobile-node localization has been combined with extended and unscented Kalman filters, majorization functions, and noisy-range formulations.These examples target tracking of moving sensors or users.
E. Comparison of Various MDS Based Localization Methods
The comparison shows that distributed MDS performs best in the reported regular and irregular simulations, while centralized MDS is most sensitive to irregular network geometry.
- Compared methods: Classical MDS is applied locally after C-means clustering, while distributed methods refine relative locations at each node.Patch stitching combines the local cluster maps into a complete configuration.
- Regular network results: 2.21 m, 1.2 m, and 0.15 m are the average localization errors for centralized, semi-centralized, and distributed MDS, respectively.The figure marks actual nodes, estimated nodes, anchors, and per-node localization error.
- Irregular network results: 14.5 m, 8.4 m, and 7 m are the reported errors for centralized, semi-centralized, and distributed MDS in the irregular network, respectively.The survey attributes the larger errors to shortest-path estimation error and limited anchor connectivity.
IV. MDS BASED LOCALIZATION FOR VARIOUS NETWORKS
The survey reviews MDS-based localization across WSNs-IoT, cognitive radio networks, and 5G networks.
- MDS-based localization literature is summarized for WSNs-IoT, cognitive radio networks, and 5G networks.
A. 3D MDS Based Localization for WSNs-IoT
The survey highlights that 3D localization is often needed in real-world WSN-IoT applications, while 2D methods cannot be directly transferred to 3D environments.
- 3D localization is often needed for better estimation and accuracy in real-world applications.
- Uniform-topology comparisons include centralized, semi-centralized, and distributed MDS methods.
- Non-uniform-topology comparisons likewise evaluate centralized, semi-centralized, and distributed MDS methods.
- 2D localization algorithms can have large errors in 3D environments because of three-dimensional deployment and complex environmental factors.At least four anchors are required in 3D networks, compared with three in 2D networks.
B. MDS Based Localization for Cognitive Radio Networks
Cognitive radio networks require localization of cooperative secondary users and non-cooperative primary users to support efficient network operation. MDS methods address this challenge by combining RSS-based distances with proximity information and by using centralized or clustered semi-centralized computation.
- Localization of primary and secondary users is challenging because primary users are not cooperative with secondary users.
- CRN localization can support spectrum-occupancy measurement, link-reliability assessment, beamforming, frequency reuse, and secondary-user network modeling.
- The methods assume that distances between secondary users can be estimated because they communicate with one another.
- MDS methods estimate secondary-user distances from RSS measurements and use binary proximity information between primary and secondary users.
- Centralized MDS localizes primary and secondary users, while cluster-based semi-centralized MDS addresses reduced accuracy in irregular topologies.
V. APPLICATIONS OF MDS BASED LOCALIZATION
MDS-based localization is applied across seismic analysis, military tracking, asset management, IoT microlocation, and underwater sensor networks. The survey concludes that centralized, semi-centralized, and distributed approaches have different complexity, accuracy, and environmental suitability, while practical methods remain an open research area.
- Seismic analysis: MDS maps can make complex relationships between seismic events easier to visualize and help identify clusters of similar objects.
- Military systems: Centralized MDS localization can help military systems track assets and troops in war zones.
- Asset management: Distributed MDS localization and tracking can support asset management and inventory operations.
- IoT: IoT microlocation targets centimeter-level accuracy for smart buildings, smart grids, and smart cities.
- Underwater exploration: Underwater MDS localization addresses harsh aquatic environments, but existing techniques are centralized and therefore have high complexity.
- Conclusions: The survey covers MDS and its localization applications across modern wireless networks, while accurate and practical methods remain open for current and future systems.