1	Localization Applying An Efficient Neural Network Mapping Li Li and Thomas Kunz
2	Localization Location information is essential to identify, for example, where sensor readings originated from and to track events and targets Location information has numerous other applications support of context-based routing protocols geographic routing protocols location-aware services enhanced security protection mechanisms Many devices embedded in real-world artifacts, so GPS is not an option Software-based solutions explored in WSN world Often require many anchor nodes (nodes with known location) or iterations (or both) to achieve high accuracy Ranging measurements helpful where available, but not always available or of sufficient accuracy to be useful
3	Formulate the Problem Given a distance matrix D, find the coordinates of all the points to achieve
4	Basics of Localization A – Hyperbolic trilateration B - Triangulation C – Multilateration Range-based vs. range-free localization methods
5	Cooperative Localization Iterative trilateration/triangulation: utilization of the distance/angle information between the node and the anchor nodes Often requires high volume of anchor nodes Iterations of messaging Cooperative Localization: joint utilization of all connectivity/distance information among all nodes Require minimum anchor nodes or anchor free High level of accuracy Computationally intensive
6	Cooperative Localization State-of-Art Solution techniques: non-linear mapping, least square estimation, multi-dimensional scaling (MDS) Rigidity theory (mass-spring model, minimize energy) NP hard Heuristic algorithms Model inter-node distances as convex constraints Use linear programming/semi-definate programming to estimate location
7	Curvilinear Component Analysis Nonlinear mapping technique developed for self-organizing neural network Characteristics More efficient compared to other non-linear mapping algorithms: MDS-O(M³), Sammon’s mapping -O(M²N),CCA-O(M²) Precise distance cost function to reduce high dimensional data with high accuracy Far less problem of local minima MDS: computationally intensive post-processing step Self-learning capability for adding new nodes Not yet explored further in our work though
8	CCA Algorithm Given a data set I of dimension M, CCA projects I to data set O of dimension S where S<M and preserves in the output set O the distances between all the data points in I
9	Localize Nodes Using CCA Input data set: distance matrix Distance of the input data vectors: distance matrix (connectivity or measurement-based) Output dimension: 2D or 3D Output data set: node coordinates Initial values for y: derived from x
10	Centralized CCA Solution: extremely good performance
11	Issues & Solutions Distance Matrix for large networks is impossible to be obtained Local matrix, local maps and map patching solutions Hop counts as distance approximations Distance matrix reconstruction using incomplete distance information Experimented with the local map approach
12	Distributed Map Algorithm Every node collects distance matrix for nodes in its vicinity 1 hop or 2 hop (larger neighborhood not always better) Every node computes its local map (relative position) If needed, local maps can be patched to a bigger map or global map In any map, given three anchor nodes that have their coordinates known, the map is translated into the absolute positions.
13	Relative Map & After Transformation Need a minimum of 3 (or 4) anchors for the 2D (or 3D) space to transfer a relative map to an absolute map
14	Results: Network Topologies
15	Results on Random Topologies
16	Results: Random Topologies
17	Conclusions and Future Work For all network topologies, CCA-Map can achieve good localization results (below 10%r) for low connectivity levels when using ranging Using connectivity only, CCA-Map achieves 20%r or better for reasonably low connectivity levels CCA-Map almost always significantly better than MDS-Map CCA-Map does not require many anchor nodes Future Work Study irregular and anisotropic networks in more detail (Milcom paper) Improve stability of MDS and CCA in range-free case Implement algorithm in testbed to study computational complexity May exploit hierarchical nature of testbed to run localization on only clusterheads