Node Position Discovery in Wireless Sensor Networks M. Onur Ergin Adam Wolisz

Node Position Discovery in Wireless Sensor
Networks
M. Onur Ergin
Adam Wolisz
Telecommunication Networks Group
Technische Universität Berlin, Germany
Email: [email protected]
Telecommunication Networks Group
Technische Universität Berlin, Germany
Email: [email protected]
Abstract—Wireless sensor networks (WSN) have gained a significant attention in research and carry the promise to be helpful
in numerous aspects of life. For many applications, the location
information of the nodes needs to be known. As this information
is not necessarily available, there is a huge interest in algorithms
estimating the positions of individual nodes. The precision and
computational complexity of such “localization” algorithms is
still a big issue. However, there are cases where the nodes are
placed in one of a few possible predetermined positions. In those
cases, computing the relative positions of nodes in relation to
each other might be sufficient to determine their real positions.
In this study, we introduce a methodology for discovering the
sequence of nodes in a unidimensional configuration using the
measured Received Signal Strength(RSS) values and allowance
of frequency diversity of high frequency radio (CC2420) that
is frequently used in wireless sensor networks. In the reported
experimental tests, we were able to determine the node sequence
correctly for the nodes that are as close as 50cm to each other,
using the developed methodology.
I. I NTRODUCTION
Wireless Sensor Networks(WSN) are composed of tiny
devices, that are often called sensor nodes, and have a broad
range of application areas. These areas include security and
safety, environmental monitoring, target tracking, inventory
tracking, smart living environments and more. For many of
them, the location information is important, if not crucial.
Some applications, like target tracking, require very precise
location information. For others, like outdoor environmental
monitoring, less precise location information is sufficient.
Different systems and technologies are used to detect the
relative or absolute positions of the sensor nodes, such as radio
frequency(RF) ranging, acoustic ranging, ultra-wide band signal ranging or global positioning system (GPS)[1]. In general,
however, precise determination of the position, especially in
the indoors scenarios, is recognized to be a complex problem,
for which better solutions are needed.
There are applications in which the positions of the nodes
are limited. In fact, a node can be located in one of the
predetermined positions. We will assume further on that the
positions are defined by a regular grid. In those cases highly
accurate calculations for node localization is not needed.
Instead; mapping the nodes to the set of potential positions
will give us the exact locations of each node deployed. We call
this; position discovery. We claim that position discovery can
be done pretty accurately with low computational complexity,
and less energy consumption. Here, we demonstrate this for a
unidimensional grid.
An example for the application areas that can benefit
from this work is inventory tracking where wireless sensor
nodes can be attached to the items of interest in a storage
environment. However, locating them (or finding the correct
place in the storage area) is difficult. Solutions supporting
such applications exist, e.g. using RFID technology [2] but
they come with extra complexity, cost and restrictions on
locating the inventory. It is also not usable for sensing related
communication. Other indoor non-RFID solutions can only
provide information about joining to or leaving the network.
We are specifically interested in discovering the location of
the nodes indoors, using only the easily available signal
strength information (RSS). However, due to multipath, this
is considered a complex issue.
Difficulty of precisely assessing the location of a sensor
node by using just simple RSS information is well known. In
this paper, we will demonstrate that combining the frequency
diversity and simple RSS measurements, it is possible to
discover the position of a sensor node (equipped with CC2420
radio) within a set of possible locations with high accuracy.
The experiment results have shown that we can achieve correct
results under the case that the nodes are positioned indoors as
close as 50cm to each other on a single dimensional plane.
This paper is structured as follows: we give an overview
to the existing studies in Section II. The problem and the
system model is defined in Section III. The explanation of
our approach is in Section IV, followed by the experiments
and results in Section V. Finally, we conclude and refer to the
future work in Section VI.
II. R ELATED W ORK
To discover the positions of WSN nodes, a number of
approaches have been considered. Multiple studies, such as
[3], show that RSS data by itself does not provide practical use
for range estimation. The studies that rely on RSS information
often require an intensive calibration process or a database for
mapping the RSS values to actual distances or positions. Those
computations are environment specific and not reusable in
different locations without precalibrating. In [5], a calibration
method that promises to reduce the error in localization has
been described. A good comparison of some of the best
known RSS based localization algorithms is given in [6], with
conclusions that the relative positioning error is between 50%
and 100% in most cases.
Another valuable result is given in [7], focusing on indoor
applications. It is shown that even when the nodes are located
between 1 to 2 meters apart in a grid, the error is more than
2 meters with a probability of 0.5 or higher.
In the current wireless sensor network literature, there is
a gap for indoor node sequence discovery. In this study, we
propose a cost effective solution to fill this gap.
III. P ROBLEM S TATEMENT AND S YSTEM M ODEL
We consider a set of N nodes deployed indoors in relatively
smaller areas with all nodes being in the transmission range
of each other. In other words, we cannot divide the network
by neighborhood information. The nodes are assumed to be
located along a line with equal distances apart from their
immediate neighbors. We are specifically interested in dense
placement of non-mobile nodes, at distances that are known
and in the order of tens of centimeters. The position of the
first node in the sequence is assumed to be known (we call this
node ’reference node’), while the sequence of the remaining
nodes is to be determined.
We assume all nodes to be equipped with high
frequency(2.4GHz), low power radios chips, which provide
the signal strength (RSS) information upon packet reception.
Using the available RSS information, we will discover the
geographically closest node to the reference node and iterate
for all nodes in the sequence.
IV. A PPROACH
We assume that all transmissions are done at a constant
power level T x. Then let us assume that RxAB be the expected
RSS value at node B for the transmission of node A in the
ideal case of having no external effects, but only distance
correlated attenuation. Similarly, RxAC is the ideal RSS value
of the reception at node C. If node B is closer to node A
than node C, then the inequality of RxAB > RxAC is true.
This phenomenon, however, is severely affected by multipath
distortion in reality.
Multipath distortion can be defined as a combination of
multipath propagation (multiple paths caused by reflection
or refraction of the transmitted signal) and RF interference
(constructive or destructive). In this context, we refer this
shortly as multipath. Multipath can corrupt or destroy the
signal, as well as increase or decrease its amplitude at the
receiver antenna.
Inevitably, there is a magnitude of multipath effects that
will add to the Rx value, which we show by Ψ as a normally
distributed random variable. So the measured signal strength
at node B will be RSSAB = RxAB + ΨAB , and it will be
RSSAC = RxAC + ΨAC at node C.
Assuming this three node sequence discovery case, in
Figure 1, node A wants to determine whether node B or node
C is closer, where all of them are placed d distance apart
from each other. For the sake of simplicity we take this three
node scenario. For more nodes, the suggested approach can
be iterated as far as desired.
RSSAB = RxAB + ΨAB node A d node B A. Principles of the suggested approach
Received signal strength (RSS) is widely used as an indicator of the signal quality at the receiver side. However, signal
quality does not always correlate with the actual geographic
distance. Due to many reasons like signal attenuation and
multipath propagation, it does not always change relatively
with the distance. Even under stationary conditions, RSS varies
in time; therefore it is not suitable for indoor ranging [3].
However, we claim that it is possible to recognize the closeness
of the nodes in regards to each other by using available RSS
information.
We start our considerations with a simplified model of lineof-sight transmissions. In such a case, the power of transmitted
radio signal attenuates with the distance. This means; the
farther node will measure a lower RSS than a closer node
to the source of the signal in line of sight settings, under ideal
conditions. So signal attenuation is a function of distance. The
derivative of this function is negative and the absolute value
of this derivative decreases as the distance to the transmitter
grows. Ergo, the node that measures the highest RSS value,
from a particular instance of transmission, is the closest node
to the transmitter. In sequence discovery, it is intuitional to
sort the nodes by iterating the sequence by discovering the
closest node to the previously sorted node until all nodes are
added to the sequence.
node C d RSSAC = RxAC + ΨAC Fig. 1.
Three nodes (A,B,C) and effective multipath (Ψ)
We would be able to recognize the sequence correctly, if
RSSAB >> RSSAC was always correct. So we desire to
achieve the inequality given in Equation 1.
RSSAB ? RSSAC
⇒ RxAB + ΨAB ? RxAC + ΨAC
⇒ RxAB − RxAC ? ΨAC − ΨAB
(1)
To make this equation hold, we can either increase the left
side, or decrease the right side of the inequality, and we do
both. We increase the difference on the left side by assuring to
operate on the steep part of the attenuation curve. This is the
case when we select node A to be close to both node B and
node C. On the other hand, node B and node C are not allowed
to be excessively close to each other. So, the derivative of the
signal attenuation curve remains bigger. Concurrently, we want
to reduce the difference on the right side of the inequality by
finding proper values of Ψ for both of the receivers.
There is always a chance, that the farther away node
can be affected by a bigger constructive multipath than the
closer node, or the closer node can be affected by a greater
destructive multipath. Yet, the peak of the multipath for a
transmission by node A is expected to be close when received
by neighboring nodes B and C due to their closeness to each
max
other, as Ψmax
AB ≈ ΨAC . Let this peak value of multipath be
max
Ψ
. Therefore, we are trying to find the peak magnitude of
the received signal strength at the receiver (RSS max ), which
is transmitted signal power with attenuation plus multipath
effect, to use in our comparisons (Equation 2).
max
RxAB − RxAC ? Ψmax
AC − ΨAB
max
max
⇒ RSSAB
? RSSAC
(2)
To assure that we will measure something close to the Ψmax
AB
and Ψmax
AC , we will use both time diversity and frequency
diversity, as shown in the following section.
B. Frequency diversity
If a node(A) is transmitting to another node(B), the measured signal strength(RSSAB ) varies, in principle, with the
change of distance between the nodes. However, as we discussed above, this difference is not always comparable due to
multipath. In [8], the signal strength as a function of distance
has been shown. It is stated that the replacement of receiver
antenna in factors of the wavelength, causes a big change in
RSS gain.
Fig. 2.
Signal Strength as Function of Position [8]
Figure 2 shows that some positional displacement of the
radio antenna can lead us to the Ψmax within a wavelength
distance. However, it is not possible to reposition the nodes in
a network to find the best positions separately. At this point, we
want to benefit from the high frequency multichannel radio for
displacing the propagation path of the signal. The displacement
of disseminated signal in fractions of a wavelength in higher
frequencies can have a big effect on aggregate gain, which we
examine below.
While moving the node antenna by fraction of a wavelength
is not possible, because the nodes are fixed, a similar effect
can be achieved by changing the wavelength of the radio
output. The above figure shows that there is a rough periodicity
in the amplitude of the received signal strength that equals
to half of a wavelength. Unfortunately, even that movement
would not assure achieving Ψmax ; in some cases movement
for several wavelengths would be needed. When using the
CC2420 radio chip, which operates on 2.4Ghz frequency,
we need roughly 1.2Ghz bandwidth for observing the whole
change in RSS. But we have only 80M hz bandwidth spread
across 16 channels(11 to 26) that are 5M hz apart [4]. Our
hypothesis is to combine this limited frequency diversity
with time diversity in order to achieve an acceptably good
approximation of RSS max , therefore Ψmax .
In order to find RSS max , we spread the transmissions
both in time and frequency. Among all samples, we choose
the highest measured RSS being the (Rx + Ψmax ). Since
multipath (Ψ) is a random variable, we want to find the
maximum that it takes within a certain time for all nodes
that are in comparison. Therefore we claim that, if we collect
a number of samples over time, we have a better chance in
reaching (or getting sufficiently close) to one of the peaks that
are illustrated in Figure 2.
We verify this hypothesis by experiment.
In one experiment, node A is positioned 100cm away
from node B at its line-of-sight and node A transmitted
a bulk of IEEE 802.15.4 packets starting from the lowest
available channel to the highest at a constant transmit power.
The plotted values in Figure 3 are the averages (over 100
measurements) of RSSAB values at each channel. Here we
observe, that the difference in the strength of the received
signal on different channels can be as big as 25dbm. This
change very much achieve the whole scope of the changes of
Ψ as theoretically predicted in Figure 2. In our experiments,
we observed that sampling 40 times with 20ms intervals is
just as good as sampling 100 times at the same speed and
having 200 samples did not improve results. Hence combining
the frequency diversity with time diversity is promising for
measuring close Ψ magnitudes of nearby nodes, therefore we
can reduce the right side of Equation 1.
Thus, we come to the understanding that, if the maximum
RSS value that we measure over time and frequency by Node
A to Node B is greater than that to Node C, it is highly
probable that Node B is closer to Node A than Node C. So
we implement this comparison in our algorithms starting from
a known reference node, which is placed in the first place in
the sequence. Then the roles are changed and every node in
the sequence becomes the transmitter (in turns) while others,
as well as the previous transmitters, remain as receivers. This
procedure is shown in Algorithms 1 , 2 and 3.
Algorithm 1 for node A (reference node)
for ch = 1 to endChannel do
for i = 1 to N do
Radio.Send(P acketi )
end for
end for
RSS change over Channel
Si = [Ni , Nj , ..., Nk , ..., Nm ], where
−40
max
max
max
RSSN
> RSSN
> RSSN
i Nj
i Nk
i Nm
−45
In this sequence, the nodes that are closer to the head node
(Ni ) are more likely to be geographically closer as well, since
they measured a higher RSS max than the nodes that are
farther from the head node in the sequence.
For the final decision, we take the reference node (NR )
and assign it to the first place in the sequence and flag it.
Then starting from SR , we take the first unflagged node from
its sequence (Nt ) and iterate from the sequence of that node
(St ). This procedure is given in Algorithm 4.
Average RSS
−50
−55
−60
−65
−70
0
2
4
6
8
10
12
14
16
Channel
Fig. 3. Change in RSS between two nodes over 16 channels at 2.4Ghz using
CC2420
Algorithm 2 for nodes B and C (receiver nodes)
Y ← T HIS N ODE ID
for ch = 1 to endChannel do
i←0
while i < N do
P acket pkt ← Radio.Receive()
i ← getOrder(pkt)
X ← getSenderId(pkt)
rss ← getRss(pkt)
max
= (RxXY + Ψmax ) then
if rss > RSSXY
max
RSSXY ← rss
end if
end while
end for
Algorithm 3 Decision algorithm
max
max
if RSSAB
> RSSAC
then
CloserN ode ← B
else
max
max
if RSSAC
> RSSAB
then
CloserN ode ← C
end if
end if
C. Position Computation
In a network of m nodes, we can extend the above procedure
to compute the sequence of nodes, therefore their positions.
After having each node Ni (1 ≤ i ≤ m) collected the
maximum RSS values from each of its neighbors, a sequence
of neighborhood S is created by using these measured RSS
values in Algorithm 3.
Algorithm 4 Sequence algorithm
S ← Set of Sequences
N ← All N odes
P ← {} // Empty Positions Set
NR ← N.getRef erenceN ode()
Nt ← NR
while UnflaggedExists(N) do
P.add(Nt )
Nt .setF lag(true)
Nt ← f irstU nf laggedIn(Si )
end while
return P
V. E XPERIMENTS AND P ERFORMANCE R ESULTS
In our experiments, using the algorithms that are described
in Section IV, we chose the closest node for each node. The
first node in the node sequence has been taken as the reference
node. Then, iteratively, we sorted the remaining nodes into
a single dimensional sequence. All experiments were done
indoors with severe observed multipath.
In one experiment, we placed 3 TelosB nodes in a single dimensional space that were about 100cm apart from each other.
We collected RSS max values in all available 16 channels that
the CC2420 radio operates at. Each transmission is repeated
100 times. The nodes were given IDs 5, 6, 7 and they were
positioned in the order 5−7−6. The reference node was Node
5 at the first place in the node sequence. Hence node 5 was
the transmitter while the nodes 6 and 7 were the receivers at
the first iteration. For each proceeding iteration, nodes 6 and 7
have become the transmitters in turns. After collecting the RSS
data from the measurements, we iteratively sorted them and
found the correct ordering as being 5 − 7 − 6. The experiment
output is shown in the Figure 4.
We extended the same experiment to 4 nodes, having a
sequence of nodes with IDs 5 − 7 − 6 − 8 relatively and having
the Node 5 as the reference node. In these experiments, the
node placement was done intentionally irrespective of node
IDs to prevent any false positive verdicts due to software error.
Applying the same computations, we were again able to find
the correct ordering with the data shown in Figure 5.
Node: 6 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−65
−60
−70
−80
−90
−100
10
15
20
25
−75
−90
10
30
15
Channel
20
25
30
RSSmax
20
25
RSSmax
−60
5
6
8
9
−70
−80
10
−75
Channel
Node: 9 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−50
15
20
25
30
Channel
Fig. 4.
Node: 6 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−60
−65
−65
−70
−70
RSSmax
Node: 5 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−60
−75
−80
−95
10
15
20
25
−80
5
7
8
−90
−95
10
30
15
20
25
30
Channel
Node: 8 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−70
−60
−75
RSSmax
Node: 7 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−50
−70
−80
−100
10
5
6
8
15
20
Channel
Fig. 5.
25
30
20
25
30
−60
5
6
7
9
−80
−100
10
15
20
25
30
Channel
−80
−85
−90
10
15
20
25
30
Channel
Experiment output gives the correct ordering: 5-6-7-8-9
−95
10
very well, letting us to discover the correct sequence of nodes,
there has been few cases in which the sequence of two of the
neighboring nodes were swapped. Such as, the data illustrated
in Figure 7 has given us the ordering as 5 − 7 − 6 − 8 − 9 with
Node 5 being the reference node, while the correct ordering
was 5−6−7−8−9. This experiment was done with the same
settings and at the location as the other experiments and the
internode distance was 100cm. However, when we took the
reference node as Node 9, we could find the correct ordering
as 5 − 6 − 7 − 8 − 9.
A. Verification of the concept
5
6
7
−90
30
5
6
7
8
−75
Channel
−90
25
−70
Fig. 6.
−85
6
7
8
−90
20
−80
Experiment output gives the correct ordering: 5-7-6
−85
15
15
Channel
Node: 8 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−40
−60
RSSmax
−80
10
−90
10
30
−70
5
6
RSSmax
15
5
7
8
9
−70
−80
Channel
Node: 7 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−50
Channel
−65
max
6
7
8
9
−80
−100
10
Node: 7 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−60
RSS
−60
−80
5
7
RSSmax
−60
−85
6
7
Node: 6 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−50
RSSmax
−70
Node: 5 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−40
RSSmax
RSSmax
max
RSS
Node: 5 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−50
15
20
25
30
Channel
Experiment output gives the correct ordering: 5-7-6-8
In another experiment we used 5 nodes with IDs
5, 6, 7, 8, 9 and placed them in the sequence 5−6−7−8−9
while decreasing the distance in between nodes to 50cm, again
having the reference node as Node 5. After following the
suggested methodology, the outcome of this experiment has
again been the correct sequence, which is shown in Figure 6.
Even though in most cases the suggested method performed
To verify the effectiveness of frequency diversity on closeness information, we performed two other sets of experiments.
We placed 5 nodes 50cm apart from each other in a small,
multipath-prone room. Each node transmitted 40 packets with
20ms intervals, only on channel 11(2405M hz) and we sorted
the nodes according to the methodology in subsection IV-C.
We repeated this experiment 10 times. Later, we repeated the
same set of experiments for the whole bandwidth case, which
is 16 channels.
In these experiments, we positioned Node 0 as the first
node (reference node) in the sequence and positioned nodes
1, 2, 3, 4 next to it respectively, each node 50cm farther than
the previous one. Hence, if the output of our algorithm is
{0 1 2 3 4}, then the verdict is true(T), otherwise false(F).
Node: 5 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−60
Node: 6 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−40
RSSmax
RSS
max
−70
6
7
8
9
−80
−90
−100
10
15
20
25
−60
5
7
8
9
−80
−100
10
30
Channel
Node: 7 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−60
15
20
25
30
Channel
Node: 8 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−60
RSSmax
RSSmax
−70
−70
5
6
8
9
−80
−90
10
15
20
25
5
6
7
9
−80
−90
30
−100
10
Channel
Node: 9 −−−−−−−−−−−−−−−−−−−−−−−−−−−−
−60
15
20
25
30
Channel
ACKNOWLEDGMENTS
max
−70
RSS
RSS from transmissions in all available channels that the radio
chip allows us to operate at. For decision criterion, we take
the highest measured RSS among all channels between a node
pair and by comparing these values with all other pairs we
give a binary decision to choose the closest node. Starting
from one known reference node, we iterate sorting the nodes
in the sequence until positions of all nodes are computed. In
our experiments we have high success in sequence discovery
with occasional error of swapped adjacent nodes, while the
overall sequence is still being correct.
As for future work, we will extend the experiments to an
increased number of nodes and we will use non-line-of-sight
settings, which will bring us more challenge in discovering
the node sequence. The step after this will be extending the
position computations for two-dimensional setups for discovering 2 × M and N × M setups. With increased experiment
scale, we will develop a methodology to rank the reliability
of the computed sequence.
The authors would like to thank Dr. Vlado Handziski
and Jan-Hinrich Hauer for valuable discussions and given
software support. This work has been supported by European
Aeronautic Defense and Space Company (EADS) Deutschland
GmbH under AMETYST project.
5
6
7
8
−80
−90
−100
10
15
20
25
30
Channel
R EFERENCES
Fig. 7.
Experiment output gives the ordering slightly wrong as: 5-7-6-8-9
Exp. No:
1
2
3
4
5
6
7
8
9
10
Result:
Single Channel
02143
F
02134
F
02134
F
02134
F
02134
F
02341
F
02134
F
02134
F
02143
F
02134
F
0/10 Success
Multiple Channel
02341
F
01234
T
01234
T
01234
T
01234
T
01234
T
01234
T
01234
T
01234
T
01234
T
9/10 Success
TABLE I
V ERIFICATION : S INGLE C HANNEL VS M ULTIPLE C HANNEL
In Table I, each row is the result of a single experiment.
We see that in single channel case none of the 10 experiments resulted in correct sequence, while in multiple channel
experiments 9 out of 10 verdicts have been correct. It is also
noticeable that in the incorrect verdict of multiple channel
experiments, only one node was not found in its respective
position.
VI. C ONCLUSION
In this paper, we suggested an approach for discovering
the node sequence in wireless sensor networks in a single
dimensional space. In our methodology we take Received
Signal Strength (RSS) as our input parameter. We sample the
[1] Li X.Y., ”Wireless Ad Hoc and Sensor Networks: Theory and Applications”, Cambridge University Press, pp. 463-501, Cambridge, 2008
[2] H. Yang and S.-H. Yang, Connectionless indoor inventory tracking in
zigbee rd sensor network, in Industrial Electronics, 2009. IECON 09.
35th Annual Conference of IEEE, pp. 2618 2623, nov. 2009.
[3] Whitehouse K., Karlof C. and Culler D., A Practical Evaluation of Radio
Signal Strength for Ranging-based Localization, ACM Mobile Computing
and Communications Review (MC2R), Special Issue on Localization
Technologies and Algorithms, 2006
[4] http://focus.ti.com/lit/ds/symlink/cc2420.pdf
[5] Jihoon Kang; Daeyoung Kim; Youngsoo Kim; , ”RSS Self-calibration
Protocol for WSN Localization,” Wireless Pervasive Computing, 2007.
ISWPC ’07. 2nd International Symposium on , vol., no., 5-7 Feb. 2007
[6] De Cauwer, et. al., ’Study of RSS-Based Localisation Methods in
Wireless Sensor Networks”, in proc. ECUMICT 2010
[7] G. Zanca, A. Zanella, F. Zorzi, M. Zorzi ”Experimental comparison of
RSSI-based localization algorithms for indoor wireless sensor networks”
In Proceedings of REALWSN’08. Glasgow, Scotland, UK
[8] Cavers J. K., Mobile Channel Characteristics, Kluwer Academic Publishers, 2000.