[CUWiN-Dev] Node mapping

[David Young]

On Wed, Mar 22, 2006 at 07:40:52PM -0600, Wendy Edwards wrote:
> Regarding the node-mapping problem, what assumptions do we make?  Do none
> of the nodes have GPS coordinates, or only some of them?  What approach
> have people been taking?  I did a literature search and noticed some
> interesting papers.

Hi Wendy,

The idea behind the node visualization is that in many CUWiN applications,
the precise locations of nodes cannot be known, but it is nevertheless
possible to render a "virtual" map that places the nodes in the right
relationship to each other, topologically, using pairwise relationships
between nodes such as "X is adjacent to Y" or "signal strength of X at
Y is N" or "ETX of X at Y is N."

In general, you can assume that we know the GPS coordinates of very
few nodes.  However, as few as three nodes' GPS coordinates may suffice
to orient the map to the compass.  "It depends."

The approach we take now is to model the nodes as masses connected to
adjacent nodes with springs; the natural length of each spring is set to
ETX on that link.  Then we run the dynamical simulation and pray that it
settles into a steady state.  It is more complicated than that.  There are
other ways to find a "low-energy" solution to the system, including
"hill-climbing" (Seth Price's approach), simulated annealing, etc.

Note that the relationship between ETX and distance is probably not
linear, but ISTR the natural lengths of the springs is set to a constant
multiple of ETX.  That must explain some of the bad results.

You can also abandon the springs system altogether.  That may be best.
You should consider using Kohonen's Self-Organizing Map (SOM), which is
used to embed a two-dimensional manifold in a multidimensional space.
It is not difficult to program a SOM.

> BTW, I did generate and send an SSH key to get access - do I need to do
> anything else?

Let me install that, now.

Dave

-- 
David Young             OJC Technologies
dyoung at ojctech.com      Urbana, IL * (217) 278-3933