Presentation 11/06: Localization from mere connectivity
Su Kim
Title: Localization from mere connectivity
Published: in Proceedings of the 4th ACM international symposium on
Mobile ad hoc networking & computing, pages 201-212, 2003
Please reply to this message in order to write your critique and
summary.
Su Jin Kim
On Nov 6, 2007 12:10 PM, Su Kim <suji...@gmail.com> wrote:
>
Su Jin Kim
trouble to open it.
The critique from Aarti.
On Nov 6, 2007 12:10 PM, Su Kim <suji...@gmail.com> wrote:
>
jay.e...@asu.edu
Antennas" by Malhotra et al
Critique by: Jay Elston
Critique of paper
Summary
This paper presented analysis, experiments and simulation of the
effectiveness of using directional antenna to determine a mobile
node's position.
The paper analyzed four configurations of directional antenna use.
1. Aligned Nodes
Anchor(s): Single anchor node using a single directional antenna, Node
is aligned
Target: Two directional antenna, Target is aligned with anchor.
2. Omni-directional
Anchor(s): Single anchor node transmitting with Omni-directional
dipole antennas
Target: Two directional antenna, Target's alignment is known.
3. Unaligned Nodes
Anchor(s): Dual directional antennas, Anchor's alignment is known.
Target: Two directional antenna, Target is unaligned.
4. Dual anchor Nodes
Anchor(s): Two anchor nodes, each with Directional antenna, Anchor's
alignment is known.
Target: Single directional antenna, Target's alignment is known.
Key Contributions
The combination of analysis, simulation and actual experimentation
using motes is unique.
Analysis & Results
The research determined that it is possible to obtain location
information using directional antennas. There are some situations
where the positional information is not very accurate, especially if
the target node is at certain angles from the anchor node. Accuracy
can be improved with the addition of anchor nodes.
Localization using directional antenna is more accurate than using
omni-directional antenna.
Conclusions
The use of directional antenna with a suitable number of anchor nodes
provides a means to implement a localization scheme for an ad hoc
network. The data in this paper can be used to help engineer a
solution. For instance - if you can deploy the target nodes with known
alignment, and you can keep your target nodes "in front" (in a field
that is between 30 and 60 degrees) of an anchor node, you can get
positional estimates with a distance that is within +/- 20% error
(from the anchor node). If you cannot guarantee the alignment of your
nodes, you should use the scheme where the anchor nodes transmit with
a pair of directional antenna. If you cannot keep your target nodes
"in front" of an anchor node, or you need additional accuracy, you
will need additional anchor nodes.
jay.e...@asu.edu
Ruml, Ying Zhang, & Markus P. J. Fromherz
Critique by: Aarti Munjal, Sushma Myneni, Justin Comroe
Summarized by: Jay Elston
Summary
The paper discusses a nice scheme for localizing the nodes in a
network by using only the connectivity information between nodes. The
scheme is evaluated exhaustively for a number of different scenarios.
Key Contributions
The above mentioned paper uses only the connectivity metric to arrive
at the relative map of the sensor node locations in the network. It
performs even better if distance information between two sensors in
the network is know, and can produce an absolute map with very less
error if there are at least 3 or more anchor nodes in the same
network. The paper uses a technique called MDS (a multi dimensional
scaling) to compute the relative map taking inputs from previous step
(shortest path algorithm).
Analysis & Results
● The technique used in this paper can produce a relative map or an
absolute map if it has sufficient anchor nodes. So we can use this
technique to either generate a relative map or absolute map (providing
anchor nodes) based on our requirements.
● There is no specific requirement that anchor nodes should be
positioned at the edge of the network like for some of the
localization techniques.
● The computation complexity is O(n³), where n is the number of nodes
present in the network. So a sensor node itself cannot be used to
generate the map if number of nodes present is too high.
● All the computation needs to done at the centralised server. If the
nodes are mobile (as in most of the cases), at each time instant, they
need to send the server their connectivity information with respect to
other nodes in the network.
Criticisms / Suggested improvements
i. The paper itself suggests that the centralized computation
requirement is a drawback in using this approach to arrive at the map.
A decentralized method may be implemented by placing a number of
computational intensive sensors at fixed locations (using the same
sensor as anchor nodes). So even if the number of nodes increases the
computation task is shared among the computation intensive sensors.
ii. The paper discusses shortest distance between every pair of nodes.
Authors have considered Dijkstra's algorithm for the same purpose but
there are other algorithms, for instance, Floyd's algorithm, which
perform better when all pairs of nodes are taken into account for
calculating shortest distances. The paper mentions both the algorithms
but the results are discussed using only Dijkstra's algorithm.
iii. A point that has been stressed in the paper is 'performance
decreases for larger 'n'', but no strong argument has been given to
support the same. I am not sure how to answer this but I guess it can
be answered in a way taking two values of 'n'(say n=3 and n=5), each
one used in evaluation of 3rd step, then proving that the performance
in former is better than latter.
iv. If large number of anchor nodes lead to a low performance, the
motivation to use anchor nodes then in 3rd step is not clear, because
more information should lead to a better estimate of position.
v. The centralized computation scheme used in the paper is itself a
bottleneck in its performance. Every time data needs to be sent to the
server. The very nature of ‘distributed computing’ can be used for the
scheme to perform better.
vi. It is questionable how well this scheme will work in the real
world. “I’m looking at the scheme of MDS Maps as most useful for
outdoor applications (where dynamic positioning/repositioning is
crucial) … If you’re constantly regenerating the maps, then problems
arise as to how to efficiently do so (which is something not covered
in detail, but a serious implementation problem for real world use).
For instance, as is mentioned in the paper a limitation of the MDS Map
per their current implementation is its requirement for centralized
processing. It’s hinted that the system can be distributed, yet
there’s still the issue of computational power of mobile devices and
synchronization with remote nodes. The reason I mention this again is
to hint at why the use of MDS Maps (especially in a large outdoor
network), despite the dynamic generation of the location map, may not
be practical for use in cases where the data collection is done
entirely on mobile devices.
vii. The simulation made use of a pseudo-random number generator
(PRNG). The PRNG may not be truly random, which many affect the
results. Using a uniform distribution is not a good simulation of the
real-world.
viii. The MDS Map is inaccurate. The paper hints that this can be
compensated by the addition of anchor nodes with known locations (such
as a few nodes with GPS sensors). However, the novelty of the MDS
scheme is hinted as its ability to generate network maps in the
absence of many or any pre-provided absolute locations. And again,
random deployment it’s always possible that these anchor nodes could
land in locations where they’re not really beneficial to the MDS Map
generation. – It would be interesting to see how the MDS Map system
works in operation with real sensor deployments in various
environments/situations.
On Nov 6, 1:10 pm, Su Kim <sujin...@gmail.com> wrote: