Localization Applying An Efficient
Neural Network Mapping

Li Li and Thomas Kunz

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

Formulate the Problem

Given a distance matrix D, find the coordinates of all the points to achieve

Basics of Localization

A – Hyperbolic trilateration

B - Triangulation

C – Multilateration

Range-based vs. range-free localization methods

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

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

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

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

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

Centralized CCA Solution: extremely good performance

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

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.

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

Results: Network Topologies

Results on Random Topologies

Results: Random Topologies

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


	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


	Given a distance matrix D, find the coordinates of all the points to achieve


	A – Hyperbolic trilateration
	B - Triangulation
	C – Multilateration
	Range-based vs. range-free localization methods


	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


	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


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


	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


	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


	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


	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.


	Need a minimum of 3 (or 4) anchors for the 2D (or 3D) space to transfer a relative map to an absolute map


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