Bekijk online - Ghent University Library

Evaluatie van link-inschattingsalgoritmen voor RPL in
dynamische sensornetwerken
Jens Devloo
Promotoren: prof. dr. ir. Ingrid Moerman, dr. ir. Eli De Poorter
Begeleider: David Carels
Masterproef ingediend tot het behalen van de academische graad van
Master of Science in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Informatietechnologie
Voorzitter: prof. dr. ir. Daniël De Zutter
Faculteit Ingenieurswetenschappen en Architectuur
Academiejaar 2013-2014
Evaluatie van link-inschattingsalgoritmen voor RPL in
dynamische sensornetwerken
Jens Devloo
Promotoren: prof. dr. ir. Ingrid Moerman, dr. ir. Eli De Poorter
Begeleider: David Carels
Masterproef ingediend tot het behalen van de academische graad van
Master of Science in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Informatietechnologie
Voorzitter: prof. dr. ir. Daniël De Zutter
Faculteit Ingenieurswetenschappen en Architectuur
Academiejaar 2013-2014
Voorwoord
Ik zou graag een aantal personen bedanken voor hun hulp en steun tijdens dit onderzoek en het
schrijven van deze thesis.
Allereerst een woordje van dank aan mijn begeleider David Carels en co-promotor dr. ir. Eli
De Poorter voor de uitstekende begeleiding tijdens het opstellen van dit werk. Ook bedankt om
steeds tijd voor me vrij te maken, voor de kritische feedback en de hulp bij de vele problemen die
ik onderweg ben tegengekomen. Verder wil ik ook mijn promotor prof. dr. ir. Ingrid Moerman
bedanken om dit onderzoek mogelijk te maken, voor het opvolgen van mijn thesis en om me de
nodige middelen te bezorgen.
Mijn ouders wil ik van harte bedanken om me de kans te geven om verder te studeren, omdat
zij steeds voor me klaarstonden en in me geloofden en me gedurende het ganse jaar hebben
gesteund wanneer dit nodig was.
Verder wil ik al mijn vrienden bedanken voor de steun en het nodige amusement om deze periode
tot een goed einde te brengen.
Als laatste een speciaal woordje van dank voor mijn vriendin Julie, die me het ganse jaar door
dik en dun gesteund en gemotiveerd heeft.
Jens Devloo, juni 2014
Toelating tot bruikleen
“De auteur geeft de toelating deze scriptie voor consultatie beschikbaar te stellen en delen van
de scriptie te kopi¨eren voor persoonlijk gebruik.
Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit
deze scriptie.”
Jens Devloo, juni 2014
Evaluatie van link-inschattingsalgoritmen
voor RPL in dynamische sensornetwerken
door
Jens Devloo
Masterproef ingediend tot het behalen van de academische graad van
Master in de ingenieurswetenschappen: Computerwetenschappen
Academiejaar 2013–2014
Promotoren: prof. dr. ir. Ingrid Moerman, dr. ir. Eli De Poorter
Begeleider: David Carels
Faculteit Ingenieurswetenschappen en Architectuur
Universiteit Gent
Vakgroep Informatietechnologie
Voorzitter: prof. dr. ir. Dani¨el De Zutter
Samenvatting
In draadloze sensornetwerken zijn er typisch meerdere mogelijke paden om pakketten naar de
sink te sturen. Wegens de beperkte energievoorraad van een sensormodule is het belangrijk
om de ingebouwde radio zo effici¨ent mogelijk te gebruiken door het totaal aantal keer dat een
pakket moet verzonden worden te minimaliseren. Door de grote verschillen in betrouwbaarheid
tussen de verschillende links is het van belang om uit deze mogelijke paden het meest geschikte
te selecteren. Indien de kwaliteit van een link goed zou kunnen ingeschat worden, leidt een pad
met links van hoge kwaliteit tot goede prestaties en een beperkt energieverbruik.
In deze thesis werden, naast de twee reeds bestaande, vier nieuwe link-inschattingsalgoritmen
toegevoegd aan de Contiki implementatie van het IPv6 Routing Protocol for Low-Power and
Lossy Networks (RPL). Deze link-inschattingsalgoritmen werden aan de hand van diverse metrieken en in verschillende dynamische scenario’s ge¨evalueerd. Dit zowel op de Cooja simulator
als op het iMinds w-iLab.t real-life testbed. Het uiteindelijke doel van deze thesis is inzicht
verkrijgen omtrent de gevolgen van de keuze voor bepaalde link-inschattingsalgoritmen en de
invloed van bepaalde netwerkkarakteristieken op de performantie van de kwaliteitsschatting in
RPL.
Trefwoorden
RPL, link-inschattingsalgoritmen, dynamische sensornetwerken, simulatie, experimenteel, RSSI,
LQI, Four bit, Fuzzy LQE
An evaluation of link estimation algorithms for RPL
in dynamical and wireless sensor networks
Jens Devloo
Supervisor(s): prof. dr. ir. I. Moerman, dr. ir. E. De Poorter, D. Carels
Abstract— Wireless sensor networks typically consist of multiple routes
to forward packets to a node responsible for collecting and processing the
data, referred to as the sink. Due to the limited energy resources of a sensor
module, it is important to use the radio as efficient as possible and limit the
required number of transmission. The large differences in reliability between links make it important for a node to select the best and most energyefficient route to the sink. If a node would be able to estimate the quality of a
link in a reliable way, a route to the sink using the best available links would
lead to a network which performs well and uses limited energy resources. In
this research multiple link estimation algorithms are added to the Contiki
implementation of Routing Protocol for Low-Power and Lossy Networks
(RPL). These algorithms will be evaluated by the use of performance tests
on several dynamical sensor networks, in a simulation environment and on
the real-life iMinds w-iLab.t office testbed.
Keywords— RPL, link estimation algorithms, wireless sensor networks,
simulation, experimental, RSSI, LQI, Four bit, Fuzzy LQE
I. I NTRODUCTION
IRELESS sensor networks (WSN) consist of multiple
small and inexpensive sensors which are equipped with
a restricted microprocessor, a small amount of memory and a
transceiver. These sensors are usually powered by battery and
commonly monitor temperature, pressure and humidity and forward this information to the sink, which is a sensor responsible
for collecting and processing the data. Industrial implementations range from forest and vulcano monitoring to locating free
parking spots and full dumpsters [1, 2]. The data will be transmitted to other nearby sensors, referred to as nodes in the network, until the data arrives at the sink. Since the sensors should
remain as small as possible, we have to cut down on processing power, energy resources and storage capabilities. Research
identifies the radio as primary source of energy consumption,
which forces RPL to use the radio in an energy efficient way.
II. M ETHODOLOGY
A. RPL
Routing Protocol for Low-Power and Lossy Networks (RPL)
is a proactive, distance-vector routing protocol specifically designed for Wireless Sensor Networks (WSN) [3]. The RPL protocol makes use of control packets (DIO, DAO and DIS) for
building a tree like topology (see figure 2), called a DestinationOriented Directed Acyclic Graph (DODAG). Each node has a
preferred parent which acts like a gateway towards the destination, usually the sink but Point-to-Point (P2P) traffic is also supported. The selection of the preferred parent is done by an objective function which is not specified in RPL. In this research,
the objective function will use the link quality estimated by the
link estimation algorithm to specify a link metric for each possible parent. RPL will use the route which minimizes the path
metric, i.e. the sum of all link metrics towards the sink.
W
Due to the large number of nodes in a wireless sensor network
and the limited range of the built-in radio there exist multiple
paths, which all take multiple hops to reach the sink. The hardware limitations and interference on the used 2.4 GHz spread
spectrum band greatly increases the probability of packet loss,
bit errors and time-dependent link qualities. If a node would
be able to use at any moment the most efficient path towards the
sink, a lot of energy can be saved. This is only possible when the
quality of a link can be estimated in a robust and reliable way. It
becomes the prominent liability of the link estimation algorithm
to select the most appropriate neighbor to send its packet to.
J. Devloo is with the Department of Information Technology, Ghent University (UGent), Gent, Belgium. E-mail: [email protected] .
Fig. 1: Example of a RPL DODAG.
B. ContikiOS
ContikiOS is a wireless sensor network operating system
completely written in C which provides IP communication and
is highly portable to different architectures like Texas Instruments MSP430 [4]. It also has its implementation of RPL, called
ContikiRPL [5].
C. Cooja simulator
Cooja is a Java-based simulator designed for simulating sensor networks running Contiki source code on different hardware platforms. Since Cooja is a software-based simulator, it
doesn’t take external interference into account and uses default
values for radio driver variables such as Link Quality Indicator (LQI) and Received Signal Strength Indicator (RSSI). The
Cooja Unit Disk Graph Medium (UDGM) channel model calculates the RSSI value based on the distance between the nodes
and uses 37 as default for all LQI values [6].
III. L INK ESTIMATION
Decent link estimation algorithms take the lossy nature and
time dependent link quality of wireless sensor networks into account when determining the best neighbor to forward data to.
Initial link estimators were relatively simple and selected the
neighbor based on some data link layer variables. A number of
improved estimators using well-defined information from multiple network layers have been proposed, such as Four bit [7] and
Fuzzy LQE [8]. Early estimators and their modern variants are
respectively called hardware and software based link estimation
algorithms [9].
A. Objective Function 0
The objective function 0, also referred to as hop count, minimizes the number of hops from the source towards the destination. Each link obtains the same link metric, so minimizing the
path metric results in minimizing the amount of hops taken.
B. Hardware based link estimation algorithms
Hardware based link estimation algorithms use information
from the data link layer and make the calculation of the link
metric quality dependent. The Received Signal Strength Indicator (RSSI) is an example of such a hardware calculated value
and indicates the strength of a received radio-frequency signal,
calculated over 8 symbol periods. RSSI seems to be highly
correlated with Packet Delivery Ratio (PDR) [10] and can be
used to model link quality. Alternatively, after packet reception
the transceiver calculates a Link Quality Indicator (LQI) value
which is an in IEEE 802.15 proposed measure of chip error rate.
It takes the amount of errors in the received packet and the distance between the received and expected frequency of the used
modulation schema into account. The LQI value calculation is
vendor specific and completely independent of the RSSI value,
although [9] indicates a clear correlation between both.
C. Software based link estimation algorithms
Unfortunately the LQI, RSSI and other data link layer values
are only calculated after reception of a packet, so packet loss
cannot be detected by the use of LQI and RSSI values. More
complex software based link estimation algorithms will tackle
this issue by using information from multiple network layers to
make intelligent decission in route making.
The Estimated Transmission Count (ETX) of a link is the expected number of transmissions needed to succesfully send a
packet over this link. It uses previous transmission to estimate
the required attempts and uses this ETX value as link metric in
route calculation.
The Four bit algorithm combines multiple sources of information from several network layers to calculate link metrics in a
reliable and intelligent way [7]. The LQI and RSSI values gain
insight in link and channel quality while the ETX path metric
resembles the network layer information. This algorithm is implemented using a flow chart to select the most appropriate parent. The algorithm to determine the best of two possible parents
can be found in algorithm 1.
I f one o f b o t h l i n k s h a s i t s w h i t e b i t s e t
I f t h i s l i n k has b e t t e r path metric ( i n c l .
threshold )
Then c h o o s e l i n k w i t h w h i t e b i t
Else
I f o t h e r l i n k ( without white b i t ) has b e s t path
metric ( incl . twice the threshold )
Then c h o o s e l i n k w i t h o u t w h i t e b i t
Else
Then c h o o s e l i n k w i t h w h i t e b i t
Else
I f both l i n k s have e q u a l p a t h m e t r i c s ( or d i f f <
threshold )
Then c h o o s e l i n k w i t h h i g h e s t RSSI v a l u e
Else
Then c h o o s e l i n k w i t h h i g h e s t p a t h m e t r i c
Algorithm 1: Four bit algorithm to select best parent
Fuzzy logic is a modern approach to combine multiple link
metrics by using membership functions which assign a score in
[0, 1] for every link metric. These individual scores can be combined with an aggregation function such as the Yagger operator
(see formula 1) [8]. It aggregates multiple values by calculation
of an weighted mean (β is typical 0.6) of the worst and average value of the metrics. This results in a link score which can
be inverted to obtain a link metric for routing purposes. Our
Fuzzy LQE implementation uses four link metrics to model link
quality: the end-to-end packet delivery rate, the coefficient of
variation of the ETX value to model link stability and the LQI
and RSSI values which resemble link and channel quality.
µ(L) = β ∗ min(µP dr (L), µSt (L), µLi (L), µCh (L))
+ (1 − β) ∗ mean(µP dr (L), µSt (L), µLi (L), µCh (L)) (1)
IV. E VALUATION
We evaluate link estimation algorithms in terms of multiple
metrics. Packet Delivery Ratio (PDR) is defined as the number of received packets at the sink to the total number of data
packets sent in the network. The average number of hops can be
used to model the number of transmission required. It is calculated by averaging the number of hops taken from every packet
which arrived at the sink. This method takes route changes during simulation into account, but only counts packets which effectively arrived at the sink. The control traffic overhead can
be measured by counting all DIO messages generated by each
node. RPL controls the redundant messages by making use of a
Trickle timer [11], which expands the interval between multiple
DIO-messages when the network stabilizes. Energy consumption is an important performance metric and can be modelled by
the percentage radio on time which dominates the power usage
in sensor nodes. Network stability can be measured by counting
the number of parent switches in the network. More stable networks tend to obtain higher Packet Delivery Ratio (PDR) due to
less control traffic overhead, but switching to a better preferred
parent can improve route quality significantly. Links with low
quality can also obtain high PDR by the use of multiple MAC
layer retransmissions. For this reason, the number of retransmission needed will be counted as last performance metric.
A. Cooja simulator
In order to conduct some WSN simulation in Cooja, six scenarios are constructed which focus on several important network
charactersitics. The standard scenario contains 63 client nodes
and 1 server acting as root in an evenly distributed 8 by 8 grid on
a 175 by 175m surface. Placing the sink in a corner results in a
realistic network, mimicking real-life forest or vulcano monitoring. Transmission and interference ranges are set to 45m (65%
delivery ratio) and 60m respectively and are chosen in a way
to model realistic scenarios. Cooja’s Unit Disk Graph Medium
(UDGM) degrades the signal quality based on the distance between nodes. To simulate data collection, each node will send
every 20 to 40 seconds a 30 byte packet towards the sink. The
sparse scenario consists of nodes with a limited transmission
(30m) and interference (40m) range, which limits the number
of available routes towards the sink. The third scenario has 144
nodes in a 12 by 12 grid on the same surface, which makes the
network a lot more dense. This will increase the amount of packets sent to the sink and the amount of interfered nodes during a
transmission. The fourth scenario emphasizes the asymmetric
behavior of a real-life sensor node by changing the range dependent to the direction. Due to hardware limitation, real-life radio
range also differs in each direction which can create asymmetric
links. These are links where only one of both nodes can send to
the other. In the fifth scenario, each nodes sends every 90 seconds 3 packets in a row which simulates bursty behavior. The
sixth scenario simulates mobility by adding two mobile nodes
to the standard network. While the grid functions as backbone
and only forwards packets, the mobile nodes will travel through
the network and periodically send packets to the sink.
Setting
Contiki version
MAC protocol
Radio Duty Cycling
Maximum number of retransmissions
Neighbor table size
Channel check rate (Hz)
CC2420 transmission power
Cooja simulation time
w-iLab.t testbed simulation time
Network stabilisation time
Value
2.7
CSMA
ContikiMAC
5
16
16
-15 dBm
10 minutes
30 minutes
1 minute
TABLE I: Simulation settings
B. iMinds w-iLab.t testbed
Due limitations of the Cooja simulator, we need a real-life
testbed to reliably evaluate all link estimation algorithms. The
iMinds w-iLab.t [12] testbed contains 200 Tmote Sky sensor
nodes [13] which can run Contiki source code and make it possible to evaluate our scenarios in a real-life office environment
(see figure 3). By varying the amount of nodes in the simulation we can simulate sparse and dense networks, running these
tests during daytime introduces extra external interference and
varying the transmit power of the Tmote Sky CC2420 radio [14]
allows to increase the asymmetry in the network.
V. R ESULTS
All simulations ran twice to determine the variance in results.
The simulation settings can be found in table I.
A. Cooja simulator
Fig. 2: Example of the Cooja mobility scenario. Other scenario’s use the same grid, but have more nodes or different transmission and interference regions.
Fig. 3: iMinds w-iLab.t office testbed. Indicated nodes are used
in the standard scenario while the sparse scenario only uses 10
nodes and the dense scenario uses all available nodes.
Research indicates Four bit and Fuzzy LQE algorithms obtain slightly higher packet delivery ratio in the standard scenario
(see figure 4) with similar energy consumption (see figure 5),
but require more parent switches and control traffic overhead
(not shown). All algorithms obtain more or less equal results
in average number of hops and number of retransmissions. The
RSSI based algorithm seems less stable and uses on average one
hop extra. In Cooja, LQI and hop count perform similar due to
simulation limitations. All LQI values are set to 37, which results in equal link metrics and a path metric only dependent on
the number of hops.
The sparse scenario shows less variance in performance due
to the limited number of paths towards the sink, which allows
the simple algorithms, such as hop count and the LQI-based algorithm, to obtain similar results as more complex ones, without
the need for extra RPL-overhead and thus low energy consumption.
The interference in dense networks results in smaller packet
delivery ratios, especially for the RSSI-based and Four bit algorithms. They results in less stable networks with high energy usage. Algorithms based on Estimated Transmission Count (ETX)
and Fuzzy LQE seem to perform best.
Fuzzy LQE and Four bit don’t show remarkable results in the
Cooja simulators asymmetric scenario, probably due to the limited usefull LQI and RSSI information. The increase in asymmetry forces the estimators to double the number of retrans-
Packet Delivery Ra/o 0.8 OF0 0.6 LQI 0.4 RSSI ETX 0.2 4B 0 standard sparse dense asymmetric interference mobility bursty FUZZY Fig. 4: Packet delivery ratio in the Cooja simulator.
Radio-­‐on )me (%) 10 OF0 8 LQI 6 RSSI 4 ETX 2 4B 0 FUZZY standard sparse dense asymmetric interference mobility bursty missions needed compared to the standard scenario. This also
causes an increase in radio-on time.
The interference scenario results in a small drop in packet
delivery ratio, but the RSSI and Four bit estimator seem a bit
more influenced. The larger interference region also causes an
overall increase in radio-on time and energy consumption.
Bursty behavior shows a serious drop in packet delivery ratio,
with a similar energy consumption. The largest decrease can be
found at the Four bit algorithm, which seems very sensitive for
changes in send behavior.
The mobility scenario obtains very low packet delivery ratios,
especially the RSSI algorithm cannot establish a stable network.
Very simple algorithms with limited RPL-overhead, such as hop
count, can be seen as the most promissing algorithms for these
kind of mobile networks. They obtain similar delivery ratios to
Fuzzy LQE, but require less overhead and have smaller energy
requirements.
Fig. 6: Packet delivery ratio with several radio duty cycling protocols in the Cooja simulator.
Radio-­‐on )me (%) Fig. 5: Average radio-on time (in %) in the Cooja simulator.
20 15 Con7kiMAC NullRDC X-­‐MAC CX-­‐MAC NullMAC 10 5 0 of0 lqi rssi etx 4b fuzzy Fig. 7: Radio-on time of several radio duty cycling protocols in
the Cooja simulator.
In Contiki the Radio Duty Cycling (RDC) driver is responsible for turning the radio on and off to obtain efficient and
limited energy usage and the Medium Access Control (MAC)
driver checks the radio channel for possible collisions before
sending data and retransmits the packet if no data link layer
acknowledgement arrived. Next to the default and for Contiki
optimised ContikiMAC with retransmissions [15], implementations of other MAC- and RDC-drivers such as X-MAC, CXMAC, NullMAC and NullRDC are also available. Varying these
drivers results in a packet delivery ratio shown in figure 6 and
radio-on time shown in figure 7. These results show ContikiMAC outperforms other drivers with a higher packet delivery ratio and low energy consumption. NullMAC and NullRDC both
don’t use retransmissions, but NullRDC never turns the radio
off and obtains a PDR three times as high. X-MAC, and CXMAC which has less strict timing to support more radio’s, are
both non-optimized implementations and obtain PDR close to
0.8 0.6 2 0.4 4 Cooja simulation, while ETX performs significantly less. This
can be explained by the different type of interference, or due
to the limitations on LQI and RSSI values used in Cooja. The
bursty scenario shows a performance increase compared to the
standard scenario, contradictory to the results in the Cooja simulator. Although, this results seems more trustworthy because
of the limitations of the simulator.
40000 8 0.2 16 0 of0 lqi rssi etx 4b fuzzy Fig. 8: Packet delivery ratio with several channel check rates in
the Cooja simulator.
35000 Frequence Packet Delivery Ra/o NullRDC, but use less energy. Most important, all MAC- and
RDC-drivers seem to have an equal impact on all link estimation algorithms. The differences in performance between the
estimators are retained.
32375 30000 23719 25000 Radio-­‐on )me (%) 4 2 3 4 2 8 1 16 0 of0 lqi rssi etx 4b fuzzy Fig. 9: Radio-on time of several channel check rates in the Cooja
simulator.
Contiki also allows us to specify a Channel Check Rate
(CCR), which is the frequency the MAC- and RDC-driver use
to turn on the radio and check the channel for possible transmissions. Research indicates higher CCR results in higher PDR
(see figure 8), but requires more energy (see figure 9). Again,
varying CCR seems to have an equal impact and is independent
on the type of estimator.
B. iMinds W-iLab.t testbed
In the standard scenario, the complex algorithms confirm their
results from the Cooja simulator (see figure 10 and 11), although
Fuzzy LQE seems to perform slightly better with less energy
consumption. The research also shows more variance in the
testbed results, especially in number of retransmissions. The
sparse scenario shows good performance of the hop count algorithm, it obtains a high PDR with very low RPL-overhead and a
small amount of retransmissions. Unfortunately, using all nodes
on the testbed doesn’t seem dense enough to obtain lower PDR
compared to the standard scenario. ETX and Fuzzy LQE obtain
best results, while Four bit doesn’t seem to handle this scenario
well. The hop count algorithm performs also very well due to
low overhead and very stable routes. The asymmetric scenario
shows a decrease in performance for most simple algorithms,
but an increase for the complex ones. This can be explained
by the network configuration which gives certain nodes higher
transmit power to increase asymmetry. The complex algorithms
seem to benefit from this higher transmit power. The number of
parent switches also decreases, due to larger difference in route
qualities less path switches occur. The Four bit algorithm performs in the interference scenario a lot better compared to the
19490 18739 3 4 5 15000 1 5 20466 20000 2 Number of retransmissions Fig. 12: Influence of maximum number of retransmissions in
RPL.
The maximum amount of retransmissions can be freely chosen in ContikiRPL, which allows to limit excessive retransmissions and energy usage. The default value of 5 indicates there
will be 6 attemps to send the packet before it gets dropped. By
inspecting the logs, the influence of this maximum amount of retransmission can be investigated. Figure 12 indicates how much
packets needed multiple retransmissions while performing the
standard scenario on the w-iLab.t office testbed.
Research indicates almost all packets needing two retranmissions, also had three or more retransmissions. This indicates
using more then two or three retransmission barely results in
higher packet delivery ratio, but causes higher energy consumption.
VI. C ONCLUSIONS
This research evaluates multiple link estimation algorithms in
ContikiRPL by the use of performance tests on several dynamical sensor networks, in a simulation environment and on the
real-life iMinds w-iLab.t office testbed. Next to ContikiRPL’s
standard hop count and Estimated Transmission Count (ETX)
algorithms two additional estimators based on the data link layer
Received Signal Strength Indicator (RSSI) and Link Quality Indicator (LQI) values and two more complex algorithms based
on the Four bits and Fuzzy LQE algorithms are added.
After evaluation on multiple performance metrics such as
Packet Delivery Ratio (PDR), radio-on percentage, RPL control
traffic overhead and network stability we can conclude there is
no algorithm which performs best on all scenarios. Research
indicates high packet delivery ratio comes with slightly higher
energy usage, so an equilibrium has to be found.
We can conclude the extra complexity and control traffic overhead of the Four bit and Fuzzy LQE doesn’t lead to significant
performance improvement in sparse and dense networks. These
scenarios can benefit from low overhead algorithms such as hop
count and estimators based on RSSI and LQI values. Although
estimators based on RSSI values should be tweaked to obtain
good results, which is a disadvantage due to the low robustness
of the algorithm.
Packet Delivery Ra/o 1 0.8 OF0 LQI RSSI ETX 4B FUZZY 0.6 0.4 0.2 0 standard sparse dense asymmetric interference bursty Fig. 10: Packet delivery ratio on the iMinds w-iLab.t testbed.
Radio-­‐on )me (%) 4 3 OF0 LQI RSSI ETX 4B FUZZY 2 1 0 standard sparse dense asymmetric interference bursty Fig. 11: Average radio-on time (in %) on the iMinds w-iLab.t testbed.
Interference scenarios on the Cooja simulator and on the wiLab.t testbed show different results. This can have multiple
causes: while the Cooja simulator only takes internal interference into account, the testbed scenario has a lot more external interference. Next to the type of interference, the amount
can differ significantly too and cannot easily be measured while
performing the tests. On the other hand, the limitations of the
Cooja simulator can also cause different results, especially in algorithms which exhibit the not trustworthy calculated LQI and
RSSI values.
The testbed’s bursty scenario shows a slightly higher packet
delivery ratio and lower energy consumption, so sending multiple packets together can lead to better performance in non time
dependent scenarios.
We can conclude combining information from multiple network layers obtains the best results, but comes with higher control traffic overhead and energy consumption. Algorithms using this technique take non-arriving packet into account while
calculating link metrics and are capable of performing well in
asymmetrical networks.
Because of the different results obtained by the Cooja simulator and the iMinds w-iLab.t testbed we can conclude the simulator is a decent tool for algorithm development but lacks capabilities to model real-life network characteristics and deliver
reliable results. Although we must keep in mind the iMinds wiLab.t testbed always has a certain amount of asymmetry due to
the positioning of the sensornodes and the presence of multiple
obstacles.
A small study of the consequences of varying Radio Duty
Cycling (RDC)- en Medium Access Control (MAC)-protocols
shows the MAC-protocol itself has no influence on the differences in performance between multiple link estimation algorithms, but has an impact on the overall performance and energy
consumption of the network.
ACKNOWLEDGMENTS
I would like to thank prof. dr. ir. Ingrid Moerman who gave
me the opportunity of conducting this research and dr. ir. Eli De
Poorter and David Carels for their guidance and advice.
R EFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
“iMinds GreenWeCan project,” http://www.iminds.be/en/
projects/2014/03/04/greenwecan, Online, last visited on May
12, 2014.
“Valcan project (Harvard University): monitoren van een vulkaan,”
http://fiji.eecs.harvard.edu/Volcano, Online, last visited
on May 12, 2014.
T. Winter, P. Thubert, A. Brandt, J. Hui, R. Kelsey, P. Levis, K. Pister,
R. Struik, J. Vasseur, and R. Alexander, “RPL: IPv6 Routing Protocol for
Low-Power and Lossy Networks,” RFC 6550 (Proposed Standard), Mar.
2012.
Adam Dunkels, Thiemo Voigt, and B. Gronvall, “Contiki - a lightweight
and flexible operating system for tiny networked sensors,” Local Computer
Networks, vol. 38, pp. 455–462, 2004.
Nicolas Tsiftes, Joakim Eriksson, and Adam Dunkels, “Low-power wireless IPv6 routing with ContikiRPL.,” in IPSN, Tarek F. Abdelzaher,
Thiemo Voigt, and Adam Wolisz, Eds. 2010, pp. 406–407, ACM.
F. Osterlind, A. Dunkels, J. Eriksson, N. Finne, and T. Voigt, “Cross-Level
Sensor Network Simulation with COOJA,” in Local Computer Networks,
Proceedings 2006 31st IEEE Conference on, Nov 2006, pp. 641–648.
Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis, “
Four Bit Wireless Link Estimation ,” in Proceedings of the Sixth Workshop
on Hot Topics in Networks (HotNets VI), 2007.
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
Nouha Baccour, Heni Kaaniche, Mohamed Chtourou, and Maher Ben Jemaa, “F-LQE: A Fuzzy Link Quality Estimator for Wireless Sensor Networks,” in International Multi-Conference on Systems, Signals and Devices (SSD 2007), Hammamet, Tunisia, March 2007.
Nouha Baccour, Anis Koubaa, Luca Mottola, Marco Antonio Ziga Zamalloa, Habib Youssef, Carlo Alberto Boano, and Mrio Alves, “Radio link
quality estimation in wireless sensor networks: A survey.,” TOSN, vol. 8,
no. 4, pp. 34, 2012.
Kannan Srinivasan and Philip Levis, “RSSI is Under Appreciated,” in
In Proceedings of the Third Workshop on Embedded Networked Sensors
(EmNets, 2006.
P. Levis, T. Clausen, J. Hui, O. Gnawali, and J. Ko, “The Trickle Algorithm,” RFC 6206 (Proposed Standard), Mar. 2011.
“iMinds w-iLab.t website,” http://ilabt.iminds.be/wilabt/
hardwarelayout/office/architecture, Online, last visited on
May 12, 2014.
“Tmote
Sky
Datasheet,”
http://www.eecs.harvard.
edu/˜konrad/projects/shimmer/references/
tmote-sky-datasheet.pdf, Online, last visited on May 12,
2014.
“Texas Instruments CC2420 Radio Datasheet,” http://www.ti.com/
lit/ds/symlink/cc2420.pdf, Online, last visited on May 12,
2014.
Adam Dunkels, “The ContikiMAC Radio Duty Cycling Protocol,” http:
//soda.swedish-ict.se/5128/1/contikimac-report.
pdf, 2011, Online, last visited on May 12, 2014.
INHOUDSOPGAVE
i
Inhoudsopgave
Lijst van figuren
iii
Lijst van tabellen
vi
Lijst van afkortingen
viii
1 Introductie
1
1.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Draadloze sensornetwerken
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.3
Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.4
Doelstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.5
Structuur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2 Literatuurstudie
6
2.1
MAC protocollen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
RPL routeringsprotocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.3
2.4
2.2.1
Controleberichten in RPL . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2.2
Opbouw van de DODAG . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2.3
Routering in RPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
ContikiOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.3.1
Cooja simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.3.2
ContikiMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
Het iMinds w-iLab.t sensornetwerk . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3 Linkestimatie
3.1
21
Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.1.1
22
Link onbetrouwbaarheid . . . . . . . . . . . . . . . . . . . . . . . . . . . .
INHOUDSOPGAVE
3.1.2
ii
Mogelijke oplossingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.2
Werking van linkestimatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.3
Link- en padmetriek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.4
Objective Function 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.5
Hardwaregebaseerde link-inschattingsalgoritmen . . . . . . . . . . . . . . . . . . .
28
3.5.1
Received Signal Strength Indicator . . . . . . . . . . . . . . . . . . . . . .
28
3.5.2
Link Quality Indicator . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
Softwaregebaseerde link-inschattingsalgoritmen . . . . . . . . . . . . . . . . . . .
30
3.6.1
Estimated Transmission Count . . . . . . . . . . . . . . . . . . . . . . . .
30
3.6.2
Four bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
3.6.3
Fuzzy LQE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
Gerelateerd werk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
3.6
3.7
4 Methodologie en implementatie
4.1
4.2
Methodologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.1.1
Gebruikte metrieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.1.2
Cooja scenario’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.1.3
iMinds w-iLab.t testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.2.1
Linkestimatie in Contiki . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.2.2
Verwijderstrategie van de oudertabel . . . . . . . . . . . . . . . . . . . . .
48
4.2.3
Objective Function 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
4.2.4
Received Signal Strength Indicator . . . . . . . . . . . . . . . . . . . . . .
49
4.2.5
Link Quality Indicator . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.2.6
Estimated Transmission Count . . . . . . . . . . . . . . . . . . . . . . . .
52
4.2.7
Four bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.2.8
Fuzzy LQE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
5 Resultaten
5.1
37
58
Cooja simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
5.1.1
Standaard scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
5.1.2
Standaard vs sparse scenario . . . . . . . . . . . . . . . . . . . . . . . . .
62
5.1.3
Standaard vs dense scenario . . . . . . . . . . . . . . . . . . . . . . . . . .
64
INHOUDSOPGAVE
iii
5.1.4
Standaard vs asymmetrisch scenario . . . . . . . . . . . . . . . . . . . . .
65
5.1.5
Standaard vs interferentie scenario . . . . . . . . . . . . . . . . . . . . . .
67
5.1.6
Standaard vs bursty scenario . . . . . . . . . . . . . . . . . . . . . . . . .
68
5.1.7
Mobiliteit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
5.1.8
Conclusie Cooja simulator . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
iMinds w-iLab.t testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
5.2.1
Standaard scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
5.2.2
Standaard vs sparse scenario . . . . . . . . . . . . . . . . . . . . . . . . .
72
5.2.3
Standaard vs dense scenario . . . . . . . . . . . . . . . . . . . . . . . . . .
74
5.2.4
Standaard vs asymmetrische scenario
. . . . . . . . . . . . . . . . . . . .
75
5.2.5
Standaard vs interferentie scenario . . . . . . . . . . . . . . . . . . . . . .
77
5.2.6
Standaard vs bursty scenario . . . . . . . . . . . . . . . . . . . . . . . . .
78
5.2.7
Conclusie iMinds w-iLab.t testbed . . . . . . . . . . . . . . . . . . . . . .
80
Invloed van het MAC/RDC protocol . . . . . . . . . . . . . . . . . . . . . . . . .
80
5.3.1
Invloed van de MAC driver . . . . . . . . . . . . . . . . . . . . . . . . . .
80
5.3.2
Invloed van de RDC driver . . . . . . . . . . . . . . . . . . . . . . . . . .
81
5.3.3
Invloed van de Channel Check Rate . . . . . . . . . . . . . . . . . . . . .
82
5.4
Invloed van de aggregator bij Fuzzy LQE . . . . . . . . . . . . . . . . . . . . . .
83
5.5
Invloed van het aantal retransmissies . . . . . . . . . . . . . . . . . . . . . . . . .
85
5.2
5.3
6 Conclusie en future work
88
6.1
Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
6.2
Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
A Overzicht van de resultaten
92
A.1 Cooja simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
A.2 iMinds w-iLab.t testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
LIJST VAN FIGUREN
iv
Lijst van figuren
1.1
Exponenti¨ele groei van het aantal met het internet verbonden toestellen. . . . . .
2
1.2
Tmote Sky sensornode.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3
Industri¨ele toepassingen van draadloze sensornetwerken. . . . . . . . . . . . . . .
3
1.4
Energieverbruik van de Tmote Sky sensornode. . . . . . . . . . . . . . . . . . . .
4
2.1
Werking van synchrone MAC protocollen. . . . . . . . . . . . . . . . . . . . . . .
7
2.2
Werking van asynchrone MAC protocollen. . . . . . . . . . . . . . . . . . . . . .
7
2.3
Werking van frame-slotted MAC protocollen. . . . . . . . . . . . . . . . . . . . .
8
2.4
Voorbeeld van multi-hop routering. . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.5
Illustratie van hi¨erarchische en geografische routering. . . . . . . . . . . . . . . .
10
2.6
Voorbeeld van boomgebaseerde routering. . . . . . . . . . . . . . . . . . . . . . .
10
2.7
Voorbeeld van een door RPL opgebouwde DODAG boomstructuur. . . . . . . . .
11
2.8
Opbouw van een RPL DODAG. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.9
Illustratie van RPL in storing en non-storing mode. . . . . . . . . . . . . . . . . .
15
2.10 Architectuur van het ContikiOS besturingssysteem. . . . . . . . . . . . . . . . . .
17
2.11 Screenshot van de Cooja simulator. . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.12 Architectuur van het iMinds w-iLab.t testbed. . . . . . . . . . . . . . . . . . . . .
20
3.1
Stralingspatroon van de Tmote Sky en een asymmetrische link. . . . . . . . . . .
23
3.2
Spatiale regio’s in draadloze sensornetwerken. . . . . . . . . . . . . . . . . . . . .
24
3.3
Illustratie van het hidden node probleem. . . . . . . . . . . . . . . . . . . . . . .
24
3.4
Algemene werking van een link-inschattingsalgoritme. . . . . . . . . . . . . . . .
25
3.5
Overzicht van de verschillende link-inschattingsalgoritmen. . . . . . . . . . . . . .
26
3.6
Illustratie van een link- en padmetriek. . . . . . . . . . . . . . . . . . . . . . . . .
27
3.7
Voorbeeld van de correlatie tussen RSSI en PDR. . . . . . . . . . . . . . . . . . .
28
LIJST VAN FIGUREN
v
3.8
Voorbeeld van de correlatie tussen LQI en PDR. . . . . . . . . . . . . . . . . . .
29
3.9
Illustratie van het nadeel van hardwaregebaseerde estimators. . . . . . . . . . . .
30
3.10 Illustratie van Estimated Transmission Count. . . . . . . . . . . . . . . . . . . . .
31
3.11 Verschil in PDR bij twee links met zelfde ETX padmetriek. . . . . . . . . . . . .
31
3.12 Gebruik van informatie uit verschillende netwerklagen bij Four bit. . . . . . . . .
32
3.13 Overzicht van de vier informatiebits in de Four bit estimator. . . . . . . . . . . .
33
3.14 Vaag regelsystem met linguistische termen. . . . . . . . . . . . . . . . . . . . . .
34
3.15 Gebruikte lidmaatschapsfuncties in Fuzzy LQE. . . . . . . . . . . . . . . . . . . .
34
4.1
Standard, bursty en mobiliteitsscenario in Cooja. . . . . . . . . . . . . . . . . . .
41
4.2
Dense en sparse scenario in Cooja. . . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.3
Asymmetrisch scenario in Cooja. . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
4.4
Interferentie scenario in Cooja. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
4.5
Positionering sensornodes op het iMinds w-iLab.t testbed . . . . . . . . . . . . .
45
4.6
Sensornodes gebruikt in het sparse scenario op het iMinds w-iLab.t testbed . . .
46
4.7
Link- en padmetriek bij OF0. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
4.8
Mapping van de RSSI-waarde op de linkmetriek. . . . . . . . . . . . . . . . . . .
50
4.9
Link- en padmetriek bij RSSI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.10 Mapping van de LQI-waarde op de linkmetriek. . . . . . . . . . . . . . . . . . . .
51
4.11 Link- en padmetriek bij LQI. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
4.12 Link- en padmetriek bij ETX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.13 Ouderselectie bij Four bit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
4.14 Lidmaatschapsfuncties vam de aankomstratio en linkstabiliteit bij Fuzzy LQE. .
56
4.15 Lidmaatschapsfuncties van de kanaal- en linkkwaliteit bij Fuzzy LQE. . . . . . .
56
5.1
Resultaten van het standaard scenario in de Cooja simulator. . . . . . . . . . . .
60
5.2
Werking van de Trickle-timer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
5.3
Verschil in DIO propagatie bij verschillende posities van de node in de DODAG.
62
5.4
Resultaten van het standaard en sparse scenario in de Cooja simulator. . . . . .
63
5.5
Resultaten van het standaard en dense scenario in de Cooja simulator. . . . . . .
64
5.6
Resultaten van het standaard en dense scenario in de Cooja simulator. . . . . . .
65
5.7
Resultaten van het standaard en asymmetrisch scenario in de Cooja simulator. .
66
5.8
Resultaten van het standaard en interference scenario in de Cooja simulator. . .
67
LIJST VAN FIGUREN
5.9
vi
Resultaten van het standaard en bursty scenario in de Cooja simulator. . . . . .
68
5.10 Resultaten van het standaard en bursty scenario in de Cooja simulator. . . . . .
69
5.11 Resultaten van het mobiliteitsscenario in de Cooja simulator. . . . . . . . . . . .
70
5.12 Resultaten van het standaard scenario op het testbed. . . . . . . . . . . . . . . .
72
5.13 Resultaten van het standaard en sparse scenario op het testbed. . . . . . . . . . .
73
5.14 Resultaten van het standaard en dense scenario op het testbed. . . . . . . . . . .
74
5.15 Resultaten van het standaard en dense scenario op het testbed. . . . . . . . . . .
75
5.16 Resultaten van het standaard en asymmetrische scenario op het testbed. . . . . .
76
5.17 Resultaten van het standaard en interferentie scenario op het testbed. . . . . . .
78
5.18 Resultaten van het standaard en bursty scenario op het testbed. . . . . . . . . .
79
5.19 Resultaten met en zonder CSMA retransmissies in de Cooja simulator. . . . . . .
81
5.20 Resultaten van verschillende RDC drivers in de Cooja simulator. . . . . . . . . .
82
5.21 Resultaten van verschillende CCR drivers in de Cooja simulator. . . . . . . . . .
83
5.22 Resultaten van verschillende aggregatoren bij Fuzzy LQE. . . . . . . . . . . . . .
85
5.23 Frequentie van het aantal retransmissies. . . . . . . . . . . . . . . . . . . . . . . .
86
A.1 Packet delivery ratio in Cooja: overzicht. . . . . . . . . . . . . . . . . . . . . . .
92
A.2 Gemiddelde radio-aan tijd in Cooja: overzicht. . . . . . . . . . . . . . . . . . . .
93
A.3 Aantal ouderwissels in Cooja: overzicht. . . . . . . . . . . . . . . . . . . . . . . .
93
A.4 RPL-overhead in Cooja: overzicht. . . . . . . . . . . . . . . . . . . . . . . . . . .
94
A.5 Gemiddeld aantal hops in Cooja: overzicht. . . . . . . . . . . . . . . . . . . . . .
94
A.6 Aantal retransmissies in Cooja: overzicht. . . . . . . . . . . . . . . . . . . . . . .
95
A.7 Packet delivery ratio op het testbed: overzicht. . . . . . . . . . . . . . . . . . . .
95
A.8 Gemiddelde radio-aan tijd op het testbed: overzicht. . . . . . . . . . . . . . . . .
96
A.9 Aantal ouderwissels op het testbed: overzicht. . . . . . . . . . . . . . . . . . . . .
96
A.10 RPL-overhead op het testbed: overzicht. . . . . . . . . . . . . . . . . . . . . . . .
97
A.11 Gemiddeld aantal hops op het testbed: overzicht. . . . . . . . . . . . . . . . . . .
97
A.12 Aantal retransmissies op het testbed: overzicht. . . . . . . . . . . . . . . . . . . .
98
LIJST VAN TABELLEN
vii
Lijst van tabellen
2.1
Specificaties van de Tmote Sky sensormodule. . . . . . . . . . . . . . . . . . . . .
19
4.1
Overzicht van de verschillende Cooja scenario’s. . . . . . . . . . . . . . . . . . . .
44
5.1
RPL-instellingen in ContikiOS 2.7. . . . . . . . . . . . . . . . . . . . . . . . . . .
59
5.2
Simulatietijden en -instellingen. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
5.3
Overzicht van de gebruikte t-normen. . . . . . . . . . . . . . . . . . . . . . . . . .
84
5.4
Invloed maximaal aantal retransmissies. . . . . . . . . . . . . . . . . . . . . . . .
87
6.1
Overzicht van de conclusies van dit onderzoek. . . . . . . . . . . . . . . . . . . .
90
Glossary
Lijst van afkortingen
CCR Channel Check Rate
CoAP Constrained Application Protocol
CSMA Carrier Sense Multiple Access
CTS Clear To Send
DAO Destination Advertisement Object
DGRM Directed Graph Radio Medium
DIO DODAG Information Object
DIS DODAG Information Solicitation
DODAG Destination-Oriented Directed Acyclic Graph
EE Enviroment Emulator
ETX Estimated Transmission Count
EWMA Exponential Weighted Moving Average
IoT Internet of Things
LLN Low power and Lossy Networks
LPL Low Power Listening
LPP Low Power Probing
LQI Link Quality Indicator
viii
Glossary
MAC Medium Access Control
MACA Medium Access with Collision Avoidance
MP2P Multipoint-to-Point
P2MP Point-to-Multipoint
P2P Point-to-Point
PDR Packet Delivery Ratio
PoE Power-over-Ethernet
RDC Radio Duty Cycling
RPL Routing Protocol for Low-Power and Lossy Networks
RSSI Received Signal Strength Indicator
RTS Request To Send
UDGM Unit Disk Graph Medium
WSAN Wireless Sensor and Actuator Networks
WSN Wireless Sensor Networks
ix
INTRODUCTIE
1
Hoofdstuk 1
Introductie
1.1
Inleiding
De mogelijkheden van een toestel kunnen enorm uitgebreid worden als we elk toestel uniek
adresseerbaar maken en dit toestel met het internet gaan verbinden. Zo is het intussen perfect
mogelijk om vanop een mobiel toestel met internetverbinding de koffiezet aan of uit te schakelen,
verlichting te bedienen en deuren te openen of te vergrendelen. Daar meer en meer toestellen
met het internet verbonden worden (zie figuur 1.1), evolueert het internet naar een netwerk van
toestellen of Internet of Things (IoT) [1].
1.2
Draadloze sensornetwerken
Een draadloos sensornetwerk bestaat uit vele kleine, goedkope sensoren die over een bepaald
gebied verspreid worden. Elke sensornode bevat een beperkte microprocessor, een kleine hoeveelheid geheugen en een radio (zie figuur 1.2). De aanwezige sensoren zijn in staat om de
temperatuur, lichtomstandigheden, druk en andere omgevingsvariabelen op te meten. Deze informatie wordt dan met behulp van de radio verstuurd naar andere, nabij gelegen sensoren (ook
wel nodes in het netwerk genoemd). Zo wordt alle informatie van deze individuele sensoren van
node naar node verstuurd tot ze bij een verzamelpunt (dit wordt de sink genoemd) aankomt en
daar wordt verwerkt of verder wordt verstuurd over het traditionele internet. Deze sensoren zijn
meestal ook voorzien van een kleine batterij, omdat ze bij veel toepassingen in een omgeving
worden geplaatst waar geen stroom voor handen is.
1.2 Draadloze sensornetwerken
2
Figuur 1.1: Exponenti¨ele groei van het aantal met het internet verbonden toestellen [1].
Het plaatsen van dergelijke sensornodes heeft heel wat industri¨ele toepassingen, zo kunnen afvalcontainers uitgerust worden met een sensor die de afvalmaatschappij waarschuwt indien vol,
voorzien we parkeerplaatsen van een sensor die kan aangeven of de parkeerplaats vrij of bezet is
en kunnen grote bosgebieden gemonitord worden om branden te voorkomen (zie figuur 1.3) [3–9].
De grootste uitdaging is het ontwikkelen van apparatuur die enkele jaren lang, zonder menselijke
interactie kan gebruikt worden. Hierdoor is er nood aan robuste hard- en software, maar moet
er vooral op het energieverbruik bespaard worden. Een sensornetwerk moet verder ook zeer
schaalbaar zijn, want afhankelijk van de toepassing kan de grootte van het netwerk vari¨eren van
enkele tientallen tot wel duizenden sensoren. Verder kan het aantal sensornodes in het netwerk
ook met de tijd vari¨eren: nodes waarvan de energievoorraad op raakt vallen weg en kunnen
vervangen worden door nieuwe nodes die tot het netwerk moeten toetreden. Verder evolueren
Wireless Sensor Networks (WSN) meer en meer naar Wireless Sensor and Actuator Networks
(WSAN) door het toevoegen van actuator nodes. Deze nodes kunnen naast het verzamelen van
1.3 Probleemstelling
3
Figuur 1.2: Voorbeeld van een sensornode: de Tmote Sky [2].
informatie, ook zelf actie ondernemen. Zo kan een parkeerplaats vanuit een centraal systeem
aangeduid worden, waarbij er in de sensoren in de richting van de parkeerplaats een lichtje gaat
branden zodat de chauffeur de parkeerplaats gemakkelijker kan vinden.
Figuur 1.3: Links: monitoren van vulkanen [5], rechts: monitoren van parkeerplaatsen [6].
1.3
Probleemstelling
Omdat we deze sensornodes zo klein mogelijk willen houden, moet er bezuinigd worden op rekencapaciteit, beschikbaar geheugen en capaciteit van de batterij. Deze beperkte energievoorraad
zorgt ervoor dat de sensoren zuinig moeten omspringen met berekeningen en communicatie via
de radio. Vooral dit laatste blijkt de grootste verbruiker van energie te zijn (zie figuur 1.4),
waardoor het gebruik van de radio zoveel mogelijk beperkt moet worden.
Door de aanwezigheid van een eerder goedkope, korte-afstandsradio zijn deze sensoren ook zeer
gevoelig voor interferentie met andere draadloze communicatieapparatuur die ook van de beperkte en druk bezette 2.4 GHz band gebruik maakt, hetgeen de kans op pakketverlies en
onstabiele links sterk verhoogt. Wegens bovenstaande redenen wordt dit type netwerken ook
1.4 Doelstelling
4
Low power and Lossy Networks (LLN) genoemd. Deze beperkingen hebben bijvoorbeeld consequenties voor het routeringsprotocol, daar de grootte van de routeringstabellen en het aantal te
versturen controleberichten beperkt moet blijven [10].
Wegens het grote aantal nodes in een draadloos sensornetwerk, zijn er meestal meerdere alternatieve routes beschikbaar om een pakket naar de sink te sturen. De bovenstaande beperkingen
zorgen ervoor dat de kwaliteit en betrouwbaarheid van de verschillende links sterk kan vari¨eren
in de tijd. Indien een node op elk moment zijn pakketten via het meest effici¨ente pad naar de
sink zou kunnen sturen, kan er door het uitblijven van retransmissies heel wat energie bespaard
worden. Dit is enkel mogelijk indien de kwaliteit van een link op een degelijke en betrouwbare manier kan ingeschat worden, het algoritme dat hiervoor verantwoordelijk is wordt het
link-inschattingsalgoritme genoemd.
90 80 Power (mW) 70 60 50 40 30 20 10 0 CPU Radio RX Radio TX Radio Idle Radio Sleep Figuur 1.4: Oorzaken van energieverbruik in de Tmote Sky sensornode [11].
1.4
Doelstelling
In deze thesis worden de twee link-inschattingsalgoritmen die reeds in (Contiki)RPL ingebouwd
zijn uitgebreid met enkele alternatieven. Naast een algoritme dat het aantal hops minimaliseert (Objective Function 0) en een algoritme dat het aantal vereiste transmissies (Estimated
Transmission Count (ETX)) gebruikt, voegt dit onderzoek twee hardwaregebaseerde en twee
softwaregebaseerde algoritmen toe. De hardwaregebaseerde algoritmen proberen aan de hand
van de Received Signal Strength Indicator (RSSI)- en Link Quality Indicator (LQI)-waarde de
kwaliteit van de link in te schatten en zo de pakketten via betrouwbare links te routeren. De
softwaregebaseerde algoritmen doen dit op een intelligentere manier door gebruik te maken van
meerdere informatiebronnen, verspreid over de verschillende netwerklagen.
1.5 Structuur
5
Na een grondige literatuurstudie en de implementatie in ContikiOS worden deze algoritmen
uitgebreid ge¨evalueerd in een simulatie-omgeving en op een real-life testbed. Aan de hand van
een zestal metrieken bepalen we de prestaties van elk algoritme en wordt de invloed van bepaalde
netwerkkarakteristieken uitgebreid bestudeerd.
Uiteindelijk moet dit werk de lezer inzicht verschaffen in de werking van deze algoritmen en
moet de invloed van de kwaliteitsschatting op de uiteindelijke routering duidelijk worden. Dit
onderzoek legt de basis voor verdere studies waarin meerdere link-inschattingsalgoritmen kunnen
gecombineerd worden in eenzelfde netwerk of waarbij een meta-schatter gebruikt wordt om de
resultaten van verschillende algoritmen te combineren.
Eenmaal de kwaliteit van een link op een degelijke en betrouwbare manier kan ingeschat worden,
kan verder onderzoek bepalen hoe we de kwaliteit van een link kunnen verbeteren. Wat is de invloed van een hogere verzendsterkte, hoe evolueert de kwaliteit als we een andere frequentieband
gebruiken, enzoverder.
1.5
Structuur
Deze thesis is opgedeeld in een zestal hoofdstukken waarvan in deze sectie een kort overzicht
wordt gegeven.
• In hoofdstuk 2 wordt een overzicht gegeven van de belangrijkste terminologie inzake draadloze sensornetwerken. De verschillende routeringsmogelijkheden en het RPL routeringsprotocol, de mogelijke MAC protocollen en het Contiki besturingssysteem worden er kort
besproken.
• Hoofdstuk 3 gaat dieper in op de probleemstelling waaruit het belang van een goede
linkestimatie blijkt. Verder bespreekt dit hoofdstuk de algemene werking van een linkestimator en worden de in deze thesis gebruikte algoritmen uitgebreid voorgesteld.
• In het eerste deel van hoofdstuk 4 komen de verschillende evaluatiescenario’s en gebruikte
metrieken aan bod. Hierna wordt dieper ingegaan op de exacte implementatie van de
link-inschattingsalgoritmen.
• De resultaten van het onderzoek in de simulator en op het testbed worden opgelijst in
hoofdstuk 5, waarna in hoofdstuk 6 de conclusies en verkregen inzichten geformuleerd
worden.
LITERATUURSTUDIE
6
Hoofdstuk 2
Literatuurstudie
In dit hoofdstuk worden de verschillende routeringsmogelijkheden en het Routing Protocol for
Low-Power and Lossy Networks (RPL)-routeringsprotocol, de beschikbare Medium Access Control (MAC) protocollen en het Contiki besturingssysteem [12] besproken. Daarnaast komen de
Cooja simulator en het iMinds w-iLab.t testbed aan bod en wordt een overzicht gegeven van
enkele gerelateerde studies.
2.1
MAC protocollen
Zoals vermeld in 1.3 is het verzenden en ontvangen van pakketten de oorzaak van het grootste
energieverbruik van sensornodes (zie figuur 1.4). Om dit zoveel mogelijk te beperken is het van
groot belang om de radio telkens uit te schakelen als deze niet wordt gebruikt.
Medium Access Control (MAC) mechanismen worden gebruikt om de radio’s van verschillende
nodes met elkaar te synchroniseren zodat de radio’s niet onnodig lang aan staan (idle-listening),
er geen pakketten voor andere nodes ontvangen worden (overhearing), er geen pakketten worden
verzonden naar nodes die nog uit staan (overemitting) of er niet meerdere pakketten op hetzelfde
ogenblik verstuurd worden (collision).
Wegens energiebeperkingen kunnen MAC protocollen uit andere draadloze technologi¨en (bijvoorbeeld 802.11 Wi-Fi) niet zomaar gebruikt worden in draadloze sensornetwerken. Zo kan
Medium Access with Collision Avoidance (MACA) collisions goed ontwijken, maar introduceert
het een grote overhead door het sturen van Request To Send (RTS) en Clear To Send (CTS) controlepakketten. MAC protocollen voor draadloze sensornetwerken moeten dus vooral uitblinken
2.1 MAC protocollen
7
in energie-effici¨entie en schaalbaarheid.
Energie effici¨ente MAC protocollen kunnen volgens [13] het eenvoudigst opgedeeld worden in
vier categorie¨en: synchrone en asynchrone protocollen, frame-slotted protocollen die gebruik
maken van op voorhand bepaalde tijdsloten en protocollen die meerdere kanalen gebruiken.
Figuur 2.1: Werking van synchrone MAC protocollen.
Bij synchrone MAC protocollen worden de nodes gesynchroniseerd zodat ze samen wakker worden en effici¨ent kunnen communiceren. Wanneer een node uit slaapmodus komt en zelf geen
pakketten heeft om te verzenden, zal deze een bepaalde tijd luisteren of er andere nodes zijn
die een pakket naar deze node willen sturen. Indien dit het geval is kan deze node het pakket
zeer effici¨ent ontvangen. Als er geen transmissie gedetecteerd wordt, zal de node zijn volgende
ontwaaktijd bepalen en opnieuw zijn radio uitschakelen (zie figuur 2.1). Indien een pakket verstuurd moet worden zal de sensornode bij het ontwaken controleren of het medium vrij is en
indien mogelijk het pakket versturen. Wegens de gesynchroniseerde slaapcycli is de ontvanger
aan het luisteren en kan deze het pakket ontvangen. Bij deze manier van werken is het van
groot belang dat de overhead van het synchroniseren van de nodes tot een minimum herleid
wordt en de vertraging zo klein mogelijk is. Hiervoor gaan veel synchrone MAC protocollen zich
groeperen in clusters die hetzelfde slaappatroon naleven [13].
Figuur 2.2: Werking van asynchrone MAC protocollen.
Asynchrone MAC protocollen focussen op het effici¨ent opzetten van communicatie als beide
nodes niet hetzelfde slaappatroon hebben. Enerzijds kan de verzender een rustig moment afwachten en dan de verbinding opzetten door aan de hand van een preamble aan te geven wat de
2.1 MAC protocollen
8
bestemming is van het pakket dat volgt. Deze preamble moet wel lang genoeg herhaald worden
zodat alle mogelijke ontvangers zeker ´e´en keer wakker worden, hierdoor wordt de grootste overhead van dit algoritme door de verzender gedragen (zie figuur 2.2). Deze protocollen zijn in de
literatuur bekend als sender-initiated Low Power Listening (LPL). Anderzijds kan de ontvanger
ook zelf een signaal uitsturen om aan te geven wanneer hij een pakket kan ontvangen en zo
de overhead naar zich toetrekken (bijvoorbeeld een sink die weinig tot geen energiebeperkingen
heeft). Deze techniek wordt receiver-initiated Low Power Probing (LPP) genoemd.
Figuur 2.3: Werking van frame-slotted MAC protocollen.
Om een zeer effici¨ente communicatie te bekomen, worden de tijdssloten bij frame-slotted protocollen zodanig verdeeld dat geen twee nodes in dezelfde spatiaal bereikbare omgeving hetzelfde
tijdsslot toegewezen krijgen, wat voor een botsingsvrije communicatieomgeving zorgt (zie figuur
2.3). Deze manier van werken zorgt in drukke omgevingen voor een hoge doorvoer met beperkte overhead, maar helaas gaat er veel tijd verloren indien er weinig nodes aanwezig zijn
of er bepaalde nodes zijn die meer moeten verzenden dan andere. Deze beperkingen kunnen
wel weggewerkt worden door het invoeren van adaptieve slottoekenning en de mogelijkheid dat
nodes vrije sloten gaan stelen van anderen.
Multikanaal protocollen gebruiken verschillende datakanalen om interferentie te omzeilen en parallelle transmissies mogelijk te maken. Door het gebruik van kanalen op verschillende frequenties
kan de beperkte bandbreedte van ´e´en kanaal stevig uitgebreid worden. Ook frequentiespecifieke
interferentie wordt hier tegengegaan omdat er steeds van frequentie gewisseld wordt. Hier is een
goeie synchronisatie tussen de nodes echter van groot belang, wat opnieuw voor heel wat extra
overhead zorgt.
Verder zijn er nog protocollen die meerdere radio’s gebruiken, zo kan een snelle radio gebruikt
worden voor de effectieve datatransmissie en wordt een goedkope radio met laag energieverbruik
2.2 RPL routeringsprotocol
9
gebruikt voor de controlesignalen. Deze tweede radio kan door zijn laag verbruik constant
aanstaan, waardoor een effici¨ente overdracht mogelijk gemaakt wordt. Helaas introduceert deze
extra radio een grote kost en een stijging in hardwarecomplexiteit wat deze oplossing niet zo
populair maakt.
2.2
RPL routeringsprotocol
Figuur 2.4: Multi-hop routering in een draadloos sensornetwerk [14].
Wegens de in 1.3 besproken beperkingen, zijn er voor LLN netwerken enkele speciale routeringsprotocollen ontwikkeld. Draadloze sensornetwerken kunnen gecategoriseerd worden onder
de ad-hoc netwerken, dit zijn netwerken zonder enige vorm van gecentraliseerde controle. Alle
nodes in het netwerk, met uitzondering van de sink, vervullen dezelfde rol. Wegens het beperkt zendvermogen van de radiomodules kunnen slechts enkele nodes rechtstreeks naar de sink
sturen, andere nodes hebben ´e´en of meerdere tussenstops nodig. Dit wordt in de literatuur
multi-hop [15] routering genoemd (zie figuur 2.4). De bestaande routeringsprotocollen kunnen onderverdeeld worden in enkele categori¨en: hi¨erarchische, geografische, data-centrische en
boomgebaseerde routering.
Hi¨erarchische routering verdeelt het netwerk in clusters met dynamisch toegekende clusterhoofden, waarbij de communicatie tussen de verschillende clusters volledig via deze clusterhoofden
verloopt (zie figuur 2.5).
Verder zijn de nodes bij data-centrische routering niet adresseerbaar op basis van een uniek
adres, maar wordt de data rondgestuurd naar nodes die deze data kunnen gebruiken.
Bij geografische routering wordt informatie over de locatie van de nodes gebruikt om het doorsturen van pakketten effici¨enter te maken. Zo worden pakketten enkel doorgestuurd naar nodes
2.2 RPL routeringsprotocol
10
Figuur 2.5: Links: clustering bij hi¨erarchische routering [16], rechts: geografische routering [17].
die zich dichter bij de ontvanger bevinden (zie figuur 2.5) om het overspoelen van netwerk met
pakketten te voorkomen. De locatie kan centraal in een locatiedatabank worden bijgehouden
(proactieve aanpak) of kan opgevraagd worden wanneer ze nodig is (reactieve aanpak). [18, 19]
Figuur 2.6: Boomgebaseerde routering in een draadloos sensornetwerk [20].
Het in deze thesis gebruikte Routing Protocol for Low-Power and Lossy Networks (RPL) [21]
routeringsprotocol maakt gebruik van een boomgebaseerd algoritme. Deze aanpak vormt paden
richting de sink door het opbouwen van een boomstructuur (zie figuur 2.6). Een boomstructuur
wordt gekenmerkt door het feit dat elke node (behalve de sink) juist ´e´en ouder heeft waar hij
zijn pakketten naar doorstuurt. Verder heeft elke node (behalve de onderste nodes, de bladeren
van de boom genaamd) enkele kinderen die hun pakketten naar deze node doorsturen. Met deze
2.2 RPL routeringsprotocol
11
boomstructuur ontstaat tussen elke twee nodes exact ´e´en pad waarlangs de pakketten gerouteerd
kunnen worden.
Bij het opstarten van het netwerk zal het RPL-protocol een Destination-Oriented Directed Acyclic Graph (DODAG) proberen opbouwen. Dit is een structuur gelijkaardig aan de boomstructuur in figuur 2.6, maar waarbij elke node meerdere potenti¨ele ouders kan hebben. Uit deze
ouders wordt dan aan de hand van een objectieffunctie een voorkeursouder gekozen, die als
bestemmeling wordt gebruikt bij het doorsturen van pakketten (zie figuur 2.7).
Verder is RPL een distance-vector protocol: omdat beperkingen qua geheugen- en verwerkingscapaciteit er toe leiden dat geen enkele node de volledige netwerktopologie kent, worden er aan
de hand van deze boomstructuur via de voorkeursouder paden opgebouwd die elke node met de
wortel verbindt.
Figuur 2.7: Voorbeeld van een door RPL opgebouwde DODAG boomstructuur.
2.2.1
Controleberichten in RPL
Binnen het routeringsprotocol RPL worden een drietal berichten gebruikt om de opbouw van
de DODAG en het routeren in goede banen te leiden. Deze drie types berichten worden nu
besproken.
DODAG Information Object (DIO)
Deze berichten bevatten informatie over de DODAG en worden door RPL periodiek verstuurd
doorheen het netwerk. Naast het versie- en instantie identificatienummer bevatten deze berichten
2.2 RPL routeringsprotocol
12
ook belangrijke routeringsinformatie. Zo gebruikt elke node deze berichten om zijn rank door
te geven aan de naburige nodes. Deze rank wordt gebruikt als kwaliteitsmetriek voor het pad
naar de sink die de node momenteel gebruikt. Op basis van de rank van de potenti¨ele ouders en
een inschatting van de linkkwaliteit naar deze ouders zal de node zijn voorkeursouder kiezen.
Eenmaal het netwerk gestabiliseerd is, is het onnodig om nog steeds op periodieke momenten
DODAG Information Object (DIO)-berichten uit te wisselen. Daarom zal de periode tussen het
versturen van twee DIO-berichten groter worden zolang het netwerk stabiel blijft. Het algoritme
dat hiervoor verantwoordelijk is wordt binnen RPL het Trickle algoritme [22] genoemd. Telkens
er een consistent DIO-bericht ontvangen wordt, dit is een bericht dat dezelfde informatie bevat
als het vorige bericht en dus eigenlijk overbodig is, wordt de periode tussen het uitsturen van twee
DIO-berichten verdubbeld tot een instelbaar maximum. Indien een bericht nieuwe informatie
bevat wordt de periode terug ingesteld op de minimumwaarde.
DODAG Information Solicitation (DIS)
Om overhead aan controlepakketten te voorkomen zal het Trickle algoritme de periode tussen
twee DIO-berichten in een stabiel netwerk telkens verdubbelen. Omdat deze periode behoorlijk
lang kan worden, kan het lang duren alvorens een nieuwe node een DIO-bericht ontvangt met
informatie over het netwerk dat hij wil toetreden. Daarom werd in RPL een DODAG Information
Solicitation (DIS)-bericht ge¨ıntroduceerd die het mogelijk maakt om actief een DIO-bericht op
te vragen bij de naburige nodes. Door dit mechanisme moet het toetreden van een node in een
reeds stabiel netwerk veel sneller verlopen en kan een mobiele node op een eenvoudige manier
de nodes binnen zijn bereik op de hoogte brengen van zijn aanwezigheid.
Destination Advertisement Object (DAO)
Wanneer er in bepaalde situaties ook berichten van de sink naar een bepaalde node gestuurd
moeten worden, wat downwards traffic of one-to-many traffic genoemd wordt, heeft men met de
eenrichtingspaden naar de sink echter onvoldoende informatie. Een Destination Advertisement
Object (DAO)-bericht in RPL wordt gebruikt om de prefix bereikbaarheid naar de bladeren toe
bekend te maken. Nodes gebruiken deze DAO-berichten om zichzelf en de nodes dieper in hun
subboom bij hun ouders bekend te maken. Zo beschikken die over voldoende informatie om de
berichten correct te routeren (zie 2.2).
2.2 RPL routeringsprotocol
2.2.2
13
Opbouw van de DODAG
Alvorens een DODAG opgebouwd kan worden, moet er vastgelegd worden welke node de wortel
van de boom, ook wel de sink genoemd, zal zijn. Dit wordt bij het ontwerp van het netwerk
handmatig vastgelegd door de netwerkbeheerder, omdat deze typisch een speciale taak vervult
met de verzamelde informatie en vaak minder beperkingen heeft qua geheugen- en verwerkingscapaciteit. Eenmaal de sink bepaald is, begint deze met het uitsturen van een DIO-bericht om
de naburige nodes op de hoogte te brengen dat er een DODAG in opbouw is.
Indien een node een DIO-bericht ontvangt, zal deze controleren of dit bericht afkomstig is van
een node die tot dezelfde DODAG behoort en of de rank van deze node al dan niet kleiner is dan
zijn eigen rank. Als dit beide het geval is, kan de verzender als potenti¨ele ouder gezien worden
en zal de node het bericht verder verwerken. Initieel heeft elke node een oneindig grote rank
waardoor het eerste DIO-bericht altijd verwerkt wordt. De nodes die het initi¨ele DIO-bericht van
de sink ontvangen hebben, stellen hierdoor de sink in als hun ouder. Daarna bepalen deze nodes
hun eigen rank op basis van een kwaliteitsschatting van de link naar de ouder en sturen ze deze
informatie verder in het netwerk door zelf een DIO-bericht uit te sturen. Andere nodes in het
netwerk kunnen nu meerdere DIO-berichten ontvangen en moeten dus een keuze maken welke
van de potenti¨ele ouders ze als voorkeursouder instellen. Deze keuze gebeurt door gebruik te
maken van een objectieffunctie die deze beslissing neemt op basis van de rank van de potenti¨ele
ouders en de kwaliteit van de link naar deze ouders. Eenmaal een node zijn voorkeursouder
heeft gekozen, berekent deze zijn eigen rank en stuurt dit weer verder in een DIO-bericht. Na
enkele herhalingen zijn alle bereikbare nodes toegetreden tot de DODAG en kan het netwerk
gebruikt worden voor het routeren van pakketten (zie figuur 2.8).
Aangezien bepaalde objectieffuncties de linkkwaliteit in rekening nemen bij het bepalen van de
rank en er nodes in het netwerk kunnen wegvallen of toegevoegd worden kan de rank van een
bepaalde node wijzigen. Hiervoor zal elke node periodiek DIO-berichten blijven uitsturen, maar
om een overvloed aan controlepakketten te voorkomen zal de periode tussen het versturen van
deze berichten in een stabiel netwerk wel groter en groter worden (zie 2.2.1).
2.2.3
Routering in RPL
Eenmaal opgebouwd, kan de DODAG gebruikt worden bij de routering van informatiepakketten
in een sensornetwerk. Afhankelijk van de verzender en de ontvanger van het pakket kunnen
2.2 RPL routeringsprotocol
14
Figuur 2.8: Opbouw van een DODAG in RPL [23].
we drie types van routeren onderscheiden. Allereerst hebben we Multipoint-to-Point (MP2P)
verkeer, wat het verzenden van pakketten van de nodes in het netwerk naar de sink toe inhoudt.
Dit verkeer komt normaal het meest voor en zal optimaal gebruik maken van de opgebouwde
DODAG structuur. Verder wordt het verkeer van de sink naar een andere node in het netwerk
Point-to-Multipoint (P2MP) genoemd. Als laatste kunnen we Point-to-Point (P2P) verkeer
onderscheiden, wat het het verzenden van pakketten tussen twee, van de sink verschillende,
nodes in het netwerk omvat.
Bij Multipoint-to-Point stuurt een node zijn eigen pakketten en de pakketten die hij ontvangt
gewoon door naar zijn voorkeursouder. Indien elke node in het netwerk deze strategie gaat toepassen komen alle pakketten uiteindelijk bij de sink terecht. Bij deze variant komt de DODAG
structuur volledig tot zijn recht. Enkele toepassingen zijn het doorsturen van temperatuurmetingen van nodes in een project om bosbranden te bestrijden [4], het doorsturen van de locatie
van een object naar een centrale computer om tracering mogelijk te maken enzoverder.
Voor Point-to-Multipoint verkeer, wat verkeer van de sink naar een node in de DODAG inhoudt,
is de informatie uit de DAO-berichten nodig (zie 2.2.1). De sink zal aan de hand van deze berichten een route opbouwen richting de node en de routeringsinformatie aan het informatiepakket
2.2 RPL routeringsprotocol
15
Figuur 2.9: Links: RPL in storing mode, rechts: RPL in non-storing mode [24].
toevoegen.
De werking van de laatste variant, Point-to-Point verkeer, is afhankelijk van hoe het netwerk
omgaat met de ontvangen DAO-berichten. RPL voorziet twee verschillende technieken om deze
informatie bij te houden, storing en non-storing mode [24]. In het eerste geval houdt elke node
een kleine routeringstabel bij met de nodige informatie over de nodes in zijn subboom. In het
tweede geval houdt enkel de sink een, weliswaar uitgebreidere, routeringstabel bij die de info
van alle nodes in het netwerk bevat (zie figuur 2.9).
In het eerste geval, waarbij elke node een routeringstabel voor zijn subboom bevat, wordt P2P
verkeer mogelijk gemaakt door een pakket door te sturen richting sink tot het bij een node komt
waarvan de bestemmeling in zijn subboom zit. Vanaf deze nodes wordt de routeringsinformatie
uit de tabel gehaald en aan het pakket toegevoegd. Het pakket wordt dan via deze route
neerwaarts verder gestuurd.
In het tweede geval, waarbij enkel de sink een routeringstabel heeft, wordt het pakket eerst
volledig tot aan de sink gestuurd volgens het MP2P principe. Vervolgens voegt de sink routeringsinformatie toe en kan het pakket ook correct gerouteerd worden zoals bij P2MP verkeer.
In deze non-storing mode wordt in veel gevallen een niet-optimaal pad afgelegd, maar hoeven de
nodes geen routeringstabel te onderhouden. Verder kan het toevoegen van routeringsinformatie
aan pakketten ook leiden tot formattering, omdat de maximale pakketgrootte van 127 bytes al
bij 8 hops overschreden wordt [25].
2.3 ContikiOS
2.3
16
ContikiOS
ContikiOS is een open-source besturingssysteem, vergelijkbaar met TinyOS [26], dat speciaal is
ontwikkeld voor microcontrollers met een beperkte rekencapaciteit en geheugen. ContikiOS, of
kortweg Contiki, is ontwikkeld in de C programmeertaal en heeft voldoende met enkele kilobytes
RAM als geheugen en enkele tientallen kilobytes ROM voor de code [27].
De sterke opmars van Contiki is vooral te danken aan zijn volledige ondersteuning van IPv6 met
diverse standaarden zoals 6lowPAN [28], een eigen versie van RPL [21, 29] en het Constrained
Application Protocol (CoAP) RESTful applicatielaag protocol [30]. Verder beschikt Contiki over
twee volwaardige communicatiemodules: uIP en Rime. De Rime module is speciaal ontworpen
voor radio’s met een beperkt vermogen en biedt ondersteuning voor multi-hop routering, data
transmissie met acknowledgements en een schaalbare datacollectie module. uIP is een kleine
RFC geschikte TCP/IP stack waardoor communicatie met het internet mogelijk wordt. Zie
figuur 2.10 voor de volledige architectuur van Contiki.
Verder zorgen de Protothreads [31] voor een event- en multithreaded programmeermechanisme
waarbij er geen aparte stack wordt voorzien per thread. Zo wordt de grote geheugenvereiste van
multithreading (wegens de nood aan een aparte stack voor elke thread) teniet gedaan en kunnen
de lange wachttijden bij grote berekeningen van een event-driven aanpak ook vermeden worden.
ContikiOS bezit verder ook een webbrowser, een shell en een flash gebaseerde bestandsstructuur
waardoor elke ontwikkelaar direct aan de slag kan [12].
2.3.1
Cooja simulator
Om het ontwikkelen van software voor draadloze sensornetwerken een groot stuk te vereenvoudigen biedt Contiki een eigen testomgeving aan. Deze softwaresimulator zorgt ervoor dat we niet
onmiddellijk gebruik hoeven te maken van een hardware testbed of een industri¨ele implementatie. Deze op Java gebaseerde simulator voor Contiki, Cooja genaamd (zie figuur 2.11) bevat
heel wat mogelijkheden om implementaties te testen. Zo worden verschillende afstandsmetrieken
voorzien, zijn er heel wat plugins voor handen en is de simulator volledig open-source wat eigen
toevoegingen mogelijk maakt.
Omdat Cooja een volledig softwarematige simulator is, zijn er jammergenoeg ook heel wat beperkingen. Zo wordt er geen rekening gehouden met externe interferentie en is er geen mogelijkheid
2.3 ContikiOS
17
Figuur 2.10: Architectuur van het ContikiOS besturingssysteem [32].
tot het uitlezen van de registers van de CC2420 radio [33]. Zo is de Link Quality Indicator, die
normaal door de radio wordt ingesteld na decoderen en verwerken van een ontvangen pakket, bij
het uitlezen steeds 37. Ook de Received Signal Strength Indicator (RSSI), die de signaalsterkte
van het ontvangen pakket (in dB) aangeeft kan in een softwareomgeving onmogelijk bepaald
worden. Deze wordt in een Unit Disk Graph Medium (UDGM) kanaalmodel ingesteld op basis
van de afstand tussen de nodes en moet in het Directed Graph Radio Medium (DGRM) model
door de gebruiker zelf ingesteld worden aan de hand van een constante waarde [34].
2.3.2
ContikiMAC
ContikiOS bevat een eigen implementatie van een asynchroon MAC protocol, ContikiMAC genaamd [36]. Dit protocol gebruikt een Radio Duty Cycling (RDC) mechanisme dat ervoor zorgt
ervoor dat de radio in normale omstandigheden tot 99% van de tijd uitgeschakeld kan worden.
ContikiMAC verwezenlijkt dit door intelligente en voor Contiki geoptimaliseerde tijdsschema’s
te gebruiken en door het ontwikkelen van een optimalisatie die de radio snel uitschakelt indien
enkel ruis gedetecteerd wordt. Dit is ook het MAC protocol dat zal gebruikt worden in het
verdere verloop van deze thesis.
Verder werden in ContikiOS ook enkele alternatieve, asynchrone MAC-protocollen ge¨ımplementeerd:
X-MAC [37], CX-MAC die gelijkaardig is aan X-MAC maar met minder strikte tijdsrestricties
2.4 Het iMinds w-iLab.t sensornetwerk
18
Figuur 2.11: Screenshot van de Cooja simulator [35].
werkt en NullMAC die helemaal geen Medium Access Control (MAC) uitvoert en bij ontvangst
van een pakket van de bovenliggende netwerklaag gewoon het pakket verstuurt.
2.4
Het iMinds w-iLab.t sensornetwerk
Om de in 2.3.1 besproken nadelen van de simulator te overbruggen, heeft iMinds [38] ge¨ınvesteerd
in twee draadloze sensornetwerken voor ontwikkelingstoepassingen. Het ene netwerk werd uitgerold in de kantoren van het Zuiderpoortgebouw en bootst een realistische kantooromgeving
na [39]. Naast de vele interferentie van draadloze netwerken, microgolfovens en dergelijke is er
veel beweging, meerdere verdiepingen enz. Kortom een ideale testomgeving om real-life scenario’s na te bootsen. Het tweede netwerk in hun site te Zwijnaarde is niet gelegen in een
kantooromgeving en kan dus beter gebruikt worden om toepassingen te ontwikkelen die een gecontroleerde interferentie vereisen. Verder bevat deze site verschillende Roomba robots om de
2.4 Het iMinds w-iLab.t sensornetwerk
Radio module
Chipcon CC2420 (2.4 GHz, 250 kbps)
Microcontroller
Texas Instruments MSP430 (8 Mhz)
Geheugen
10 kB RAM en 1 Mb flashgeheugen voor opslag
Sensoren
Licht, temperatuur en vochtigheid
Uitbreidingsmogelijkheden
I2C, ADC, DAC, UART, enz.
19
Tabel 2.1: Specificaties van de Tmote Sky sensormodule [11].
invloed van mobiliteit op de implementaties te testen [40].
Het testbed in de kantoren van de Zuiderpoort bestaat uit bijna 200 Tmote Sky sensornodes (zie
tabel 2.1) die voorzien zijn van licht-, temperatuur- en vochtigheidssensoren. Deze nodes zijn
verspreid over drie verdiepingen van een 12x80m groot kantoorgebouw en worden via Powerover-Ethernet (PoE) van stroom voorzien. Elke node is voorzien van een kleine linux pc (zie
figuur 2.12) die in staat is om de node te flashen en de output naar een gezamelijke databank te
schrijven. Verder werd elke node uitgerust met een Enviroment Emulator (EE), die het mogelijk
maakt om het gedrag van een bepaalde sensor of actuator na te bootsen en zo de werking ervan
op een goeie manier te kunnen testen.
2.4 Het iMinds w-iLab.t sensornetwerk
Figuur 2.12: Architectuur van het iMinds w-iLab.t testbed [41].
20
LINKESTIMATIE
21
Hoofdstuk 3
Linkestimatie
Daar er in draadloze sensornetwerken meestal meerdere, alternatieve paden beschikbaar zijn
waarlangs pakketten naar de sink gestuurd kunnen worden, is het zeer belangrijk om bij het
routeren gebruik te maken van het meest effici¨ente pad. Omdat elk van deze paden zijn eigen
kwaliteit en betrouwbaarheid heeft, moet deze kwaliteit mee in rekening gebracht worden bij het
bepalen van het meest geschikte pad. Hiervoor moet het routeringsalgoritme de kwaliteit van
een link kunnen inschatten, dit gebeurt via de linkestimator of het link-inschattingsalgoritme
van het routeringsprotocol. Omdat dit algoritme het hoofdonderwerp van deze thesis is, worden
de verschillende mogelijkheden om tot deze inschatting te komen in dit hoofdstuk uitgebreid
besproken [42]. Dit hoofdstuk gaat allereerst dieper in op de probleemstelling waaruit het belang
van een goede linkestimatie blijkt, vervolgens wordt de algemene werking van een linkestimator
besproken en worden enkele voorbeeldalgoritmen voorgesteld.
3.1
Probleemstelling
Zoals in figuur 1.4 wordt aangegeven is de radio van een sensornode verantwoordelijk voor het
grootste energieverbruik. Dit maakt het effici¨ent gebruiken van de radio een belangrijk punt bij
het ontwerpen van protocollen voor draadloze sensornetwerken. Het is van groot belang om het
totaal aantal keer dat een pakket moet verzonden worden zoveel mogelijk te beperken. Hierbij
spelen niet enkel het aantal tussenstops of hops een rol, maar ook het aantal verzendpogingen
over dezelfde link die nodig zijn tot het pakket goed ontvangen is. Verder is het belangrijk om in
te zien dat een sensornode in een multihop omgeving niet enkel zijn eigen pakketten doorstuurt,
3.1 Probleemstelling
22
maar ook die van nodes die dieper in de boom gelocaliseerd zijn. Zo zal een slechte link een
negatieve invloed hebben op alle pakketten die langs deze link gerouteerd worden, indien deze
zich dicht bij de sink bevindt kunnen dit er erg veel zijn.
3.1.1
Link onbetrouwbaarheid
Tussen de verschillende links in een sensornetwerk kan een zeer groot verschil in betrouwbaarheid
optreden. Naast de afstand tussen de twee nodes, zijn nog heel wat andere factoren bepalend.
Zo worden in ´e´enzelfde netwerk soms meerdere types van sensornodes gebruikt, ieder met hun
eigen bereik. Het is dus perfect mogelijk dat een bepaalde node zonder problemen pakketten
kan versturen naar een andere node, maar nooit pakketten van die andere node kan ontvangen
omdat het bereik van die node te beperkt is. Dit fenomeen wordt link-asymmetrie genoemd. Ook
indien overal hetzelfde type van sensornodes gebruikt worden, kan asymmetrie voorkomen door
het niet perfect bolvormig zijn van het stralingspatroon van de antenne. Zo zien we in figuur 3.1
twee nodes in een netwerk, waarbij hun bereik, twee-dimensionaal voorgesteld, gebaseerd is op
het stralingspatroon van de TMote Sky sensornode [11]. We zien dat node B zonder problemen
pakketten kan sturen naar node A, omdat die binnen zijn bereik ligt. Maar in de andere richting
is geen verkeer mogelijk. Node A mag er dus niet zomaar van uitgaan dat de link naar B van
hoge kwaliteit is omdat hij bepaalde pakketten van B zonder problemen ontvangt.
Verder is de aanwezige interferentie ook een belangrijke factor inzake linkkwaliteit. De radio
van een sensornode maakt gebruik van de vrij beschikbare 2.4 GHz ISM-band, die ook door heel
wat andere draadloze communicatietechnologie¨en, zoals IEEE 802.11 WIFI en IEEE 802.15.1
Bluetooth, gebruikt wordt. Deze frequentieband wordt daardoor, vooral in kantooromgevingen,
al goed gebruikt door andere, vaak sterkere, apparatuur. Verder kan het gebruik van bijvoorbeeld
een microgolfoven de helft van de 2.4GHz band be¨ınvloeden [43], wat een grote impact op de
linkkwaliteit heeft. Ook blijkt uit [42] dat IEEE 802.11.15 veel meer be¨ınvloed wordt door deze
interferentie dan IEEE 802.11 Wi-Fi en IEEE 802.15.1 Bluetooth.
Naast de interferentie speelt de aanwezigheid van objecten in de omgeving ook een grote rol. Deze
objecten, zoals muren of liften, zijn namelijk in staat om de signaalsterkte sterk te doen dalen.
De aanwezigheid van bewegende personen kan daarnaast voor een dynamische omgeving zorgen
die samen met diverse bronnen van externe interferentie een zeer tijds- en plaatsafhankelijk
gedrag van de linkkwaliteit veroorzaakt.
3.1 Probleemstelling
23
Figuur 3.1: Links: stralingspatroon van de TMote Sky [11], rechts: voorbeeld van een asymmetrische link.
Ook interne interferentie, wat het gelijktijdig verzenden van pakketten van meerdere sensornodes binnen hetzelfde bereik inhoudt, heeft een grote invloed. Spatiaal kunnen we drie regio’s
rond een sensornode afbakenen. De connected regio waarbij de verbinding vrij goed is (meestal
wordt als vuistregel een aankomstratio van 90% gebruikt), de intermediate regio (aankomstratio
tussen 10% en 90%) en de disconnected of interferentie regio (minder dan 10% van de pakketten komt hier effectief aan). Deze regio’s zijn door het stralingspatroon van de sensornode
(zie figuur 3.1) en de invloed van externe factoren zeker niet bolvormig en kunnen dynamisch
wijzigen [44, 45]. Binnen de grenzen van de laatste regio, de interferentie regio, kunnen bijna
geen pakketten succesvol verstuurd worden, maar zorgt het versturen van een pakket wel voor
voldoende interferentie om andere communicatie onmogelijk te maken (zie figuur 3.2).
Als laatste heeft een draadloos en gedeeld medium ook last van wat in de literatuur het hidden
node probleem genoemd wordt (zie figuur 3.3). Hier kan node C niet naar node B sturen, indien
die reeds een pakket aan het ontvangen is van node A. Het probleem hier is dat, wegens het
beperkte bereik van node A, node C deze tranmissie niet kan detecteren, er van zal uitgaan dat
het medium vrij is en het versturen zal starten. Indien C begint met het verzenden, zal niet enkel
zijn pakket niet aankomen, het kan ook de ontvangst in B van het pakket van A be¨ınvloeden.
3.1 Probleemstelling
24
Figuur 3.2: Illustratie van de verschillende spatiale regio’s [42].
Figuur 3.3: Illustratie van het hidden node probleem.
3.1.2
Mogelijke oplossingen
Betere en sterkere hardware zou de onbetrouwbaarheid van de links tegen kunnen gaan, maar
leidt tot sensornodes die veel meer energie gaan verbruiken. Ook het verhogen van de transmissiesterkte van de radio kan helpen, maar zorgt er voor dat de ingebouwde batterij het niet lang
zal uithouden. Omdat we de sensornode voornamelijk klein willen houden kunnen we de batterij
niet veel uitbreiden, waardoor deze oplossingen niet wenselijk zijn. Verder kan het aantal nodes
nog verhoogd worden, maar dit leidt ook tot meer interferentie en een significant hogere kost.
Indien de constante retransmissie en eventueel verlies van pakketten vermeden wil worden is
het dus van groot belang dat een sensornode de linkkwaliteit naar ieder van zijn buren op
een betrouwbare en effici¨ente manier kan inschatten. In sectie 3.2 worden de verschillende
mogelijkheden om dit te bekomen verder besproken.
3.2 Werking van linkestimatie
3.2
25
Werking van linkestimatie
Een goede linkestimator heeft als doel om op een effici¨ente en betrouwbare manier de kwaliteit
van een link tussen twee sensornodes in te schatten en moet rekening houden met de in 3.1.1
geziene asymmetrie, plotse kwaliteitsschommelingen enz. In figuur 3.4 wordt de algemene werking van een linkestimator getoond. Omdat de kwaliteit van een link moeilijk in te schatten valt
zonder effectief de link te gebruiken, moeten we als eerste stap het al dan niet bestaand verkeer
gaan monitoren. Indien we actief verkeer gaan genereren wordt de estimator een actieve schatter genoemd, indien we enkel het bestaand verkeer gebruiken wordt dit een passieve schatter
genoemd. Het voordeel van een actieve schatter is dat elke link kan ge¨evalueerd worden, ook
de links die normaal weinig of niet gebruikt worden. Helaas is er een extra energiekost verbonden aan het versturen van extra verkeer. Deze overhead komt bij passieve schatters niet voor,
maar de mogelijke schattingen beperken zich dan wel tot de links waarover standaardverkeer
(pakketten of RPL-berichten) verstuurd wordt.
Figuur 3.4: Algemene werking van een link-inschattingsalgoritme.
Verder kunnen we de beschikbare link-inschattingsalgoritmen in twee categori¨en opdelen: schatters die enkel informatie uit de fysische netwerklaag gebruiken of schatters die op basis van
meerdere informatiebronnen aan elke link een kwaliteitsscore toekennen. Deze worden respectievelijk hardwaregebaseerde en softwaregebaseerde link-inschattingsalgoritmen genoemd [42].
In figuur 3.5 worden de meest courante link-inschattingsalgoritmen volgens deze groepering
opgesomd.
Zoals vermeld in 3.1.1 kan de kwaliteit van een link zeer plaats- en tijdsgebonden zijn en kan deze
in de praktijk zeer snel vari¨eren. Omdat link-inschattingsalgoritmen de basis vormen waarop
de pakketten gerouteerd worden, mogen deze fluctuaties niet resulteren in grote schommelingen
van de geschatte linkkwaliteit. Indien dit het geval zou zijn, verkrijgen we zeer instabiele en
constant wijzigende routes en zal de overhead van RPL-berichten die hiermee gepaard gaat voor
een veel minder betrouwbaar netwerk zorgen.
Om deze fluctuaties te voorkomen bepalen de meeste estimators een gemiddelde, trend, Kalman
3.3 Link- en padmetriek
26
Figuur 3.5: Overzicht van de verschillende link-inschattingsalgoritmen.
filter of Exponential Weighted Moving Average (EWMA) van meerdere metingen. Vooral deze
laatste is zeer populair, omdat voor deze techniek de vorige waarden niet moeten bijgehouden
worden en er heel wat geheugen kan bespaard worden. Na elke nieuwe meting wordt een nieuwe
kwaliteitswaarde bepaald door een bepaald percentage van de vorige kwaliteitswaarde (parameter α, die typisch 0,8 of 0,9 bedraagt) in rekening te brengen (zie formule 3.1). Hierdoor worden
de fluctuaties veel meer uitgemiddeld en kan de reactiviteit van het algoritme geregeld worden
door het aanpassen van de α parameter.
Qt = α ∗ Qt−1 + (1 − α) ∗ St
3.3
(3.1)
Link- en padmetriek
Bij het routeren van pakketten in een DODAG moet elke node een voorkeursouder bepalen
uit eventueel meerdere, mogelijke ouders. Dit is de ouder die de totale padmetriek tot de
sink minimaliseert. De padmetriek is de som van alle linkmetrieken op het pad richting de
sink, waarbij de linkmetriek de kwaliteit van de link modelleert en door de linkestimator in de
3.4 Objective Function 0
27
objectieffunctie wordt ingesteld.
Als voorbeeld nemen we het netwerk in figuur 3.6. Hier moet node D een keuze maken tussen
node B en node C als voorkeursouder op het pad richting sink A. Uiteindelijk kiest hij node B,
want de totale padmetriek is hier 5 + 4 = 9, in vergelijking met 4 + 8 = 12 indien hij voor node
C zou kiezen.
Figuur 3.6: Illustratie van een link- en padmetriek.
In deze thesis is het link-inschattingsalgoritme telkens verantwoordelijk voor het bepalen van de
linkmetriek tussen twee sensornodes. De estimators die in deze thesis aan bod komen, worden
in de volgende secties uitgebreider besproken.
3.4
Objective Function 0
De objectieffunctie 0, kortweg of0, is een zeer eenvoudige schatter die de hop count modelleert.
Elke link krijgt een constante waarde als linkmetriek waardoor elke node de ouder kiest die het
aantal hops naar de sink minimaliseert.
Deze metriek heeft als voordeel dat er altijd zo weinig mogelijk transmissies nodig zijn om een
pakket bij de sink te krijgen, wat qua energie-effici¨entie zeer voordelig is. Helaas wordt er bij
deze metriek geen rekening gehouden met de linkkwaliteit en kan het voorkomen dat een pakket
meermaals moet verstuurd worden alvorens het effectief aankomt. Zo worden nodes die ver in het
netwerk liggen, maar dicht bij de sink, verkozen boven nodes die wat dichter liggen. Als gevolg
hebben die links omwille van hun afstand in veel gevallen een lagere kwaliteit en wordt de winst
van een minimaal aantal hops snel teniet gedaan door nood aan retransmissies of pakketten die
3.5 Hardwaregebaseerde link-inschattingsalgoritmen
28
gewoon verloren gaan.
Indien een node twee ouders heeft die resulteren in dezelfde padmetriek, wordt ofwel een arbitraire keuze gemaakt of gebruikt men een andere estimator om tussen deze twee links te kiezen.
3.5
Hardwaregebaseerde link-inschattingsalgoritmen
De estimator die het aantal hops minimaliseert houdt geen rekening met de kwaliteit van de link.
We kunnen dit wel doen door gebruik te maken van kwaliteitsindicators die door de fysische
netwerklaag worden ingevuld na ontvangst van een pakket. Deze sectie geeft een overzicht van
de in deze thesis gebruikte hardwaregebaseerde link-inschattingsalgoritmen.
3.5.1
Received Signal Strength Indicator
Een eerste eenvoudige, hardwaregebaseerde linkinschatter gebruikt de Received Signal Strength
Indicator (RSSI) of ontvangen signaalsterkte indicator die door de fysische laag wordt ingesteld
na ontvangst van een pakket. Een hoge RSSI-waarde resulteert uit een sterk signaal met weinig
ruis en zou een goeie indicator moeten zijn van een link met een hoge kwaliteit. Zoals besproken
in [46] en getoond op figuur 3.7 is er een duidelijke correlatie tussen de ontvangen signaalsterkte
en de aankomstratio van de pakketten.
Figuur 3.7: Correlatie tussen de gemeten RSSI-waarde en de aankomstratio (PDR) [46].
Deze estimator heeft zijn eenvoud als grote voordeel, de RSSI-waarde wordt bepaald op de
fysische laag en wordt in een register van de radio ingevuld. Het uitlezen van deze waarde vergt
weinig tot geen berekeningen en zorgt voor een snelle kijk op de linkkwaliteit.
3.5 Hardwaregebaseerde link-inschattingsalgoritmen
3.5.2
29
Link Quality Indicator
Een tweede hardwaregebaserede linkinschatter gebruikt een ietwat complexere Link Quality Indicator (LQI) of linkkwaliteitsindicator. Deze waarde wordt ook bepaald op de fysische netwerklaag en hangt af van het aantal fouten in het ontvangen pakket, de afstand tussen de ontvangen
frequentie en de verwachte frequentie in het modulatieschema enz. Deze waarde geeft aan hoe
eenvoudig een pakket gedemoduleerd kon worden en zou ook een goeie indicator zijn van de
linkkwaliteit. Deze waarde heeft geen verband met de ontvangen signaalsterkte (of RSSI), maar
er zou wel een duidelijke correlatie aanwezig zijn [42]. In figuur 3.8 zien we dat er ook een
duidelijk verband is tussen de LQI-waarde en de ontvangstratio.
Figuur 3.8: Correlatie tussen de gemeten LQI-waarde en de aankomstratio (PDR) [46].
Verder wordt deze waarde ook ingevuld door de fysische laag en vergt het gebruik weinig tot
geen extra berekeningen. De implementatie van het bepalen van deze LQI-waarde is echter niet
vastgelegd in de IEEE 802.15 standaard en is dus afhankelijk van fabrikant tot fabrikant, wat
het vergelijken van LQI-waarden tussen verschillende types sensornodes moeilijk maakt.
In figuur 3.9 zien we het grote nadeel van de hardwaregebaseerde estimators, deze worden
namelijk enkel bepaald voor effectief ontvangen pakketten en hebben geen zicht op de pakketten
die verloren gaan. Zo kunnen al heel wat pakketten verloren gegaan zijn voor de eerste succesvolle
transmissie, maar kan een goede RSSI- of LQI-waarde van dit laatste pakket de indruk geven
dat deze link van hoge kwaliteit is.
We kunnen concluderen dat deze metrieken een betrouwbaar beeld kunnen geven bij een link
van hoge kwaliteit, maar ze duidelijk tekortschieten bij gemiddelde of slechte links [42]. Om
dit probleem te kunnen opvangen is heel wat meer informatie nodig dan enkele indicatoren uit
3.6 Softwaregebaseerde link-inschattingsalgoritmen
30
Ti
j
d(
u)
Figuur 3.9: De gemeten LQI-waarde kan een reeks van verloren pakketten niet opmerken [46].
de fysische laag, waar de volgende softwaregebaseerde link-inschattingsalgoritmen wel rekening
mee houden.
3.6
Softwaregebaseerde link-inschattingsalgoritmen
Om de beperkingen van de hardwaregebaseerde algoritmen tegen te gaan, bestaan er ook diverse
softwaregebaseerde estimators. Deze algoritmen proberen het aantal nodige transmissies te voorspellen of gaan kwaliteitsindicators van verschillende netwerklagen combineren. De algoritmen
uit deze thesis die hiertoe behoren worden in deze sectie besproken.
3.6.1
Estimated Transmission Count
Een eerste uitgebreidere, softwaregebaseerde estimator die in deze thesis aan bod komt, is een
algoritme dat op basis van de vorige transmissies het aantal vereiste pogingen tot een succesvolle
transmissie probeert te voorspellen. Deze Estimated Transmission Count (ETX)-waarde zal door
de schatter voorspeld worden op basis van een EWMA filter (zie formule 3.1) die inwerkt op het
aantal vereiste pogingen van de vorige transmissies (zie figuur 3.10).
Zo krijgt een link waarbij gemiddeld gezien de eerste twee transmissies falen en de derde succesvol verloopt een ETX-waarde van 3. Deze waarde wordt dan gebruikt als linkmetriek, waardoor
3.6 Softwaregebaseerde link-inschattingsalgoritmen
31
Figuur 3.10: Illustratie van Estimated Transmission Count.
de padmetriek bij deze estimator een betrouwbare inschatting levert van hoeveel effectieve transmissies er nodig zullen zijn om een pakket aan de sink te krijgen.
Figuur 3.11: Verschil in PDR bij twee links met zelfde ETX padmetriek.
Deze estimator heeft echter als nadeel dat enkel actieve links, dit zijn links waar de node geregeld
een pakket naar probeert te sturen, een betrouwbare ETX-waarde hebben. Nieuwe links die
worden toegevoegd krijgen standaard een ETX van 5 en worden maar in extreme gevallen
gekozen. Dit probleem kan opgelost worden door actief andere links te gaan testen, maar komt
met de kost van enkele extra transmissies.
Verder kunnen twee paden met dezelfde padmetriek toch een sterk verschillende end-to-end
Packet Delivery Ratio (PDR) bekomen (zie figuur 3.11). Zo zijn paden waarin veel variantie in
de ETX-waarden voorkomt effici¨enter dan paden die gelijk verdeelde ETX-waarden hebben.
3.6 Softwaregebaseerde link-inschattingsalgoritmen
ET X(L) =
P DRA→B
32
1
∗ P DRB→A
(3.2)
Als alternatieve berekeningswijze wordt voor de ETX ook het inverse van het product van de
aankomstratio’s in beide richtingen gebruikt (zie formule 3.2). Deze berekeningswijze heeft als
voordeel dat de asymmetrie van de link in de berekening wordt opgenomen.
3.6.2
Four bit
De Four bit estimator is een heel wat complexere link-inschatter die informatie van verschillende
netwerklagen gaat combineren om zo een betrouwbaar zicht te verkrijgen op de linkkwaliteit.
De ontwerpers van dit algoritme stellen voor om vier informatiebits te gebruiken, die door drie
verschillende netwerklagen worden ingesteld (zie figuur 3.12). De combinatie van informatie uit
de verschillende netwerklagen zorgt ervoor dat dit algoritme zowel zicht heeft op de kwaliteit
van de ontvangen pakketten (via de fysische laag), maar ook informatie krijgt over de huidige
routering en de padmetriek (via de netwerklaag) en zelfs over het al dan niet ontvangen van
acknowledgements op niveau van de datalinklaag.
Figuur 3.12: Gebruik van informatie uit verschillende netwerklagen bij Four bit [47].
Zoals in figuur 3.13 getoond wordt, is het idee achter dit algoritme om gebruik te maken van
een witte bit uit de fysische laag die aangeeft of de linkkwaliteit van een goed niveau is en
een ack bit uit de datalinklaag die aangeeft of er een acknowledgement is ontvangen bij de
vorige transmissie. Verder zijn er nog twee bits uit de netwerklaag die aangeven of de link qua
padmetriek beter scoort dan andere mogelijke links in de buurtabel (compare bit) en of deze
3.6 Softwaregebaseerde link-inschattingsalgoritmen
33
link de voorkeur moet krijgen omdat ze op netwerkniveau een belangrijke rol speelt (pin bit),
zoals bijvoorbeeld een rechtstreekse link naar de sink een goede keuze kan zijn.
Di
ti
sni
etde
sl
echt
st
el
i
nk
Navor
i
get
r
ansmi
ssi
e
i
seenackont
vangen
Ver
wi
j
derdeze
l
i
nkni
et
Pakketbevat
wei
ni
gf
out
en
Figuur 3.13: Overzicht van de vier informatiebits in de Four bit estimator [47].
Deze vier informatiekanalen stellen dit algoritme in staat om op een veel intelligentere manier
de linkkwaliteit in te schatten. In veel implementaties gaat men een flowchart gebruiken om op
basis van deze vier bits een voorkeursouder te kiezen of om een vervangingsstrategie voor de
buurtabel uit te werken [47].
Dit algoritme heeft als nadeel dat het gebruik van bits, die aan of uit staan, ervoor zorgt dat
de informatie uit de netwerklagen zeer beperkt is. Zo zijn de parameters die intern gebruikt
worden om een bit al dan niet aan te zetten van groot belang en zorgt de afregeling van deze
parameters voor heel wat werk. Verder is de eigenlijke uitwerking van het algoritme ook niet
bekend, het Four bit algoritme is eerder een strategie om link-estimatie aan te pakken dan een
concreet uitgewerkt algoritme.
3.6.3
Fuzzy LQE
Dit link-inschattingsalgoritme gebruikt net als het Four bit algoritme meerdere informatiebronnen om een intelligente kwaliteitsschatting te kunnen uitvoeren. Hier wordt echter geen gebruik
gemaakt van een viertal bits, maar van de beginselen van de vaaglogica (fuzzy logic) om aan
elke link een score toe te kennen (zie figuur 3.14).
Het Fuzzy LQE algoritme gebruikt meerdere linkeigenschappen en gaat deze eigenschappen
combineren tot ´e´en kwaliteitsscore die dan als linkmetriek gebruikt kan worden. Een voorbeeldimplementatie in [48] gebruikt de aankomstratio om de kwaliteit van de link te modelleren, de
3.6 Softwaregebaseerde link-inschattingsalgoritmen
34
Figuur 3.14: Vaag regelsystem met lingu¨ıstische termen [48].
co¨effici¨ent van variantie op deze aankomstratio om de stabiliteit van de link te bepalen, het
verschil in aankomstratio in beide richtingen als maatstaf voor de asymmetrie en de gemiddelde
signaal-tot-ruis-verhouding als model voor de kanaalkwaliteit.
Figuur 3.15: Gebruikte lidmaatschapsfuncties in Fuzzy LQE [48].
De waarden van de gebruikte linkeigenschappen worden dan via een lidmaatschapsfunctie uit de
vaaglogica gemapt in het eenheidsinterval [0, 1] (zie figuur 3.15). De bekomen waarden gaan we
dan via een aggregator, in de literatuur t-norm genoemd [49, 50], samennemen tot ´e´en eindscore
die een maat is voor de linkkwaliteit. De keuze van geschikte t-norm is vrij, maar de auteurs
van [48] verklaren de beste resultaten te bekomen met een Yagger-operator (zie formule 3.3).
Deze operator zorgt ervoor dat de waarde van de slechtste linkeigenschap voor een factor β
(typisch 0,6) meespeelt in het eindresultaat en wordt aangevuld met het gemiddelde van alle
waarden.
3.7 Gerelateerd werk
35
µ(L) = β ∗ min(µP DR (L), µASY M (L), µST AB (L), µCHAN (L))
+ (1 − β) ∗ mean(µP DR (L), µASY M (L), µST AB (L), µCHAN (L)) (3.3)
Het Fuzzy LQE algoritme heeft de nadelen van het Four bit algoritme niet, door te werken met
re¨ele waarden voor asymmetrie, aankomstratio enz. in plaats van bits en die te mappen op een
score zijn er geen strikte grenzen voor wat nu een goeie of slechte waarde is. De te onderzoeken
parameters beperken zich zo ook tot verschillende lidmaatschapsfuncties en aggregatoren.
3.7
Gerelateerd werk
In deze thesis wordt het Routing Protocol for Low-Power and Lossy Networks (RPL) [21] gebruikt omdat uit diverse studies blijkt dat dit protocol uitermate geschikt is voor draadloze
sensornetwerken [24, 51]. De mogelijkheid om de linkkwaliteit en huidig energieniveau een rol
te laten spelen bij het routeren betekent in dit type netwerken een grote meerwaarde. Echter
blijkt uit [52] dat de performantie van RPL sterk afhankelijk is van de gekozen parameters.
Uit diverse gerelateerde onderzoeken kunnen we al concluderen dat algoritmen die asymmetrie
uit real-life netwerken in rekening nemen veel beter gaan presteren in vergelijking met bijvoorbeeld hop-count [52], maar veelal gepaard gaan met een niet te verwaarlozen overhead door de
vele ouderwissels en hervormingen van de opgebouwde DODAG structuur [53]. In netwerken
waar veel interferentie voorkomt blijken intelligente algoritmen, zoals Four bit, een duidelijke
performantiewinst op te leveren ten opzichte van eenvoudige, PDR gebaseerde algoritmen [54].
Enkel in dense netwerken kan de schaalbaarheid van deze algoritmen in vraag gesteld worden [55].
Onderzoek in [53] toont aan dat Four bit in dense netwerken veel minder presteert, omdat de
schommelingen in de vele informatiebronnen tot constant wijzigende metrieken leiden.
Uit [56] blijkt ook dat een onderzoek aan de hand van een software-simulator niet altijd tot
realistische conclusies leidt. In dit onderzoek werden verder diverse link-inschattingsalgoritmen
ge¨evalueerd op een testbed van 18 TMote Sky sensornodes, waaruit blijkt dat RSSI en LQI
waarden wel degelijk een correlatie met de bekomen PDR vertonen. De correlatie bij RSSI
gebaseerde algoritmen blijkt nog wat sterker te zijn, maar de optimale parameters van RSSI
blijken wel veel gevoeliger te zijn en kunnen sterk vari¨eren tussen verschillende omgevingen.
3.7 Gerelateerd werk
36
Verder toont [57] aan dat het combineren van meerdere, eenvoudige algoritmen ook tot betere
prestaties kan leiden. Het onderzoek ontwikkeld een link-estimator op basis van een combinatie
van RSSI en PRR en besluit dat dit algoritme, toegepast op een Moteiv TelosB platform met
12 nodes, tot een veel stabieler netwerk met hogere aankomstratio leidt dan de individuele
algoritmen.
METHODOLOGIE EN IMPLEMENTATIE
37
Hoofdstuk 4
Methodologie en implementatie
Zoals in hoofdstuk 3 werd aangegeven is een goede en betrouwbare linkestimatie van groot
belang voor de prestaties van het RPL routeringsprotocol. Om de in deze thesis behandelde
technieken voor linkestimatie op een duidelijke manier te evalueren werden enkele structureel
verschillende scenario’s en evaluatiemetrieken opgesteld. Verder wordt in dit hoofdstuk de precieze implementatie van de in hoofdstuk 3 besproken link-inschattingsalgoritmen in ContikiOS
uitgelegd.
4.1
Methodologie
In deze thesis wordt aan de hand van een zestal uitgewerkte scenario’s de invloed van verschillende link-inschattingsalgoritmen op de prestaties van het RPL protocol bepaald. Zo zal dit
onderzoek duidelijkheid brengen in welke situaties het nuttig kan zijn om een uitgebreider algoritme te gebruiken of wanneer een eenvoudige estimatie voldoende kan zijn. Om dit te bekomen
worden de in hoofdstuk 3 besproken link-inschattingsalgoritmen eerst grondig getest op de Cooja
simulator (zie 2.3.1) alvorens deze resultaten te verifi¨eren op het iMinds w-iLab.t (zie 2.4).
4.1.1
Gebruikte metrieken
De verschillende link-inschattingsalgoritmen worden aan de hand van zes metrieken ge¨evalueerd,
waardoor we een duidelijk zicht krijgen op de prestaties van het routeren, de stabiliteit van het
netwerk en het energieverbruik van de estimator.
4.1 Methodologie
38
End-to-end packet delivery ratio
Als eerste modelleert de end-to-end PDR hoeveel van de periodiek verzonden pakketten effectief
aankomen bij de sink. Wegens de in RPL voorziene limiet op het maximaal aantal retransmissies
alvorens een pakket verloren gaat, zal de keuze van goede links tot betrouwbare routes en een
goede PDR leiden.
Gemiddeld aantal hops
Verder bepalen we van elk pakket dat in de sink aankomt het aantal hops op de afgelegde
route, waardoor het gemiddeld aantal hops van alle pakketten het gemiddeld aantal effectieve
transmissies voorstelt en rechtstreeks verband houdt met het energieverbruik. Een pad met
minder hops leidt ertoe dat er minder effectieve transmissies vereist zijn, maar wegens de grotere
afstand zal de linkkwaliteit in veel gevallen ook een stuk minder zijn waardoor heel wat meer
retransmissies mogelijk zijn. Aangezien pakketten die niet aankomen niet worden meegeteld kan
deze metriek bij een zeer lage aankomstratio een vertekend beeld geven. Indien enkel pakketten
van de nodes rond de sink aankomen resulteert deze metriek in een te lage waarde voor het
gemiddeld aantal hops.
RPL-overhead
Om een zicht te krijgen op de overhead die de estimator veroorzaakt, wordt ook het aantal DIOberichten van het RPL protocol (zie 2.2.1) die binnen het netwerk verstuurd worden bijgehouden.
Deze berichtuitwisseling veroorzaakt ook heel wat transmissies en blijft best beperkt. Zo resulteert het aanpassen van de rank van de node in het resetten van de Trickle-timer (zie 2.2.1) en
worden DIO-berichten uitgestuurd die propageren tot aan de bladeren van de boom. Verder
wordt het aantal DAO-berichten niet bijgehouden, omdat deze berichten een veel minder duidelijke correlatie vertonen met het aantal ouderwissels en wijzigingen in de rank. Deze berichten
worden namelijk niet via multicast verdeeld, maar worden bij ontvangst van een DAO-bericht
vanuit een subboom aangepast en doorgestuurd naar de voorkeursouders. De timing hiervan is
veel minder gerelateerd aan de ouderwissels dan bij DIO-berichten, waarvan de timing door de
Trickle-timer wordt geregeld. Ook het aantal DIS berichten wordt niet in rekening gebracht,
omdat in geen enkel scenario nieuwe nodes worden toegevoegd aan het netwerk.
4.1 Methodologie
39
Energieverbruik
Om het energieverbruik van de verschillende link-inschattingsalgoritmen te kunnen vergelijken
zullen we het aantal cpu cycles, het percentage van de tijd dat de radio aanstaat en de radio effectief pakketten verstuurt of ontvangt bijhouden door gebruik te maken van de Powertrace [58]
applicatie uit Contiki [27]. Deze applicatie is in staat het aantal cpu cycles te tellen en houdt
constant bij in welke toestand de radio van de sensornode zich bevindt: aan het luisteren, ontvangen, verzenden of in slaapmodus. Aan de hand van deze applicatie wordt het mogelijk om de
nodige verwerkingscapaciteit en de gemiddelde radiotijden voor alle link-inschattingsalgoritmen
te gaan vergelijken.
Aantal ouderwissels
Om de stabiliteit van het netwerk te bepalen wordt ook het aantal ouderwissels van elke node
bijgehouden. Daar het wisselen van ouder resulteert in een andere route en rank, zal dit door
het resetten van de Trickle-timer (zie 2.2.1) voor extra overhead zorgen.
Aantal CSMA retransmissies
Als laatste houden we ook het aantal retransmissies op MAC niveau bij, daar een slechte link
deels kan opgelost worden door het pakket een aantal keer te versturen. Deze metriek kan
gecombineerd worden met het gemiddeld aantal hops om inzicht te krijgen in de strategie van
de estimator. Er wordt bijvoorbeeld verwacht dat de of0 (zie 3.4) estimator, die het aantal hops
minimaliseert, waarschijnlijk meer CSMA retransmissies zal nodig hebben omdat ze voorkeur
geeft aan langere, maar vaak onbetrouwbare links.
4.1.2
Cooja scenario’s
In de Cooja simulator (2.3.1) zijn een achttal scenario’s uitgewerkt die telkens verschillende
netwerktopologi¨en, verschillend verzendgedrag en eventuele mobiliteit van de nodes modelleren.
Deze scenario’s worden gebruikt om de invloed van de verschillende link-estimators op deze
topologi¨en te bepalen. Een overzicht van de verschillende scenario’s kan gevonden worden in
tabel 4.1.
4.1 Methodologie
40
Standaard
Het standaard scenario is ontwikkeld om een realistische implementatie van een sensornetwerk
na te bootsen. Het bestaat uit 63 client en 1 server node of sink in een 8 bij 8 rasterpatroon met
een oppervlakte van 175 op 175 meter (zie figuur 4.1). Door de sink in de hoek van het netwerk
te plaatsen bootsen we een realistisch netwerk na om een bos of vulkaan te monitoren, waar de
verwerkingseenheid ook aan de rand van het netwerk voorkomt. De keuze voor een multihop
netwerk met sink in een hoek resulteert in een netwerk waarbij de nodes dicht bij de sink veel
meer belast worden dan die verder in het netwerk, wat in de realiteit ook het geval is. De afstand
van 25 meter tussen de nodes is gekozen naar analogie met realistische implementatie in [4–9].
Verder werd de ontvangstafstand ingesteld op 45 meter, waardoor de nodes zowel horizontaal,
verticaal als diagonaal hun pakketten kunnen doorsturen. De interferentieafstand, de afstand
waarbinnen het versturen van een pakket andere transmissies verhindert, werd ingesteld op 60
meter. De Cooja simulator zorgt voor een degeneratie van de signaalkwaliteit op basis van de
afstand tussen de nodes. In dit Unit Disk Graph Medium (UDGM) model daalt de ontvangstratio lineair met toenemende afstand tussen de nodes, waarbij de nodes aan de rand van de
ontvangstregio nog 65% van de pakketten ontvangen. Dit resulteert in een ontvangstpercentage
van 89% voor de nodes die horizontaal of verticaal gelegen zijn en 78% voor de diagonale nodes.
Deze realistische percentages, het multihop principe en de vele interferentie zorgen ervoor dat
er toch een aanzienlijk percentage van de verstuurde pakketten verloren zal gaan. Verder zal
elke node om de 20 tot 40 seconden (gemiddeld om de 30 seconden) een pakket versturen naar
de sink, de spreiding zorgt ervoor dat niet alle nodes op hetzelfde moment hun pakketten gaan
versturen. Ook wordt er na het opstarten van het netwerk 60 seconden lang niet verstuurd,
om het netwerk de kans te geven te stabiliseren en de DODAG met routes naar de sink op te
bouwen.
Bursty
Dit scenario heeft dezelfde specificaties als het standaard scenario, enkel worden de pakketten
in dit geval in bursts van drie pakketten om de 60 tot 120 seconden verstuurd. Het totaal aantal
verstuurde pakketten blijft zo gelijk, enkel het verzendpatroon wijzigt (zie figuur 4.1).
4.1 Methodologie
41
Mobiliteit
In het mobiele scenario worden twee extra mobiele nodes toegevoegd die een vast traject in het
netwerk afleggen (zie figuur 4.1). Enkel deze mobiele nodes sturen gemiddeld om de 30 seconden
een pakket naar de sink, waarbij de rasterstructuur dit maal dienst doet als backbone voor het
routeren en afleveren van de pakketten aan de sink. In dit scenario werden de mobiele nodes
als bladeren in de DODAG ingesteld, waardoor ze door andere nodes niet als voorkeursouder
gekozen kunnen worden. Dit zou de stabiliteit van het netwerk ten goede moeten komen, omdat
deze nodes door hun mobiele karakter niet betrouwbaar zijn om als voorkeursouder te gebruiken.
Het traject van de twee mobiele nodes is zo gekozen om veel afwisseling in het aantal hops
naar de sink te bekomen en bevat een kleine periode waarin de nodes rechtstreeks naar de sink
kunnen sturen. De snelheid van de nodes werd ingesteld op 2 meter per seconde (7.2 km/u), wat
realistisch is wanneer we bijvoorbeeld personen of dieren in een natuurgebied willen monitoren.
Figuur 4.1: Links: standaard en bursty scenario in Cooja, rechts: scenario met mobiele nodes
in Cooja.
Dense
Dit scenario heeft vergeleken met het standaard scenario meer dan dubbel zoveel nodes op dezelfde oppervlakte, waardoor het een veel dichter bezet gebied modelleert. Hier werden 144
nodes in dezelfde rasterstructuur op dezelfde oppervlakte als het standaard scenario geplaatst
(zie figuur 4.2). De ontvangst- en interferentieafstand blijven gelijk, waardoor er nu veel meer
4.1 Methodologie
42
nodes bereikbaar en verstoord worden. Het UDGM degeneratiemodel zorgt voor een ontvangstratio van bijna 95% voor de directe buren tot 65% voor de bereikbare nodes aan de rand van de
bereikbare regio.
Sparse
Dit scenario modelleert een dun bezet gebied of een netwerk waarbij de maximale verzendafstand
veel lager ligt. Het netwerk is hier identiek aan het standaard netwerk, maar de ontvangst- en
interferentieafstand zijn verlaagd naar respectievelijk 30 en 45 meter (zie figuur 4.2). Deze
aanpassingen zorgen ervoor dat een node niet meer diagonaal in het raster kan versturen en er
nu maar vier in plaats van acht mogelijke ouders zijn. Ook het aantal verstoorde buren bij het
versturen daalt van twintig naar acht.
Figuur 4.2: Links: dense scenario in Cooja, rechts: sparse scenario in Cooja.
Asymmetrie
Om de in 3.1.1 besproken asymmetrie van draadloze sensornetwerken te modelleren is dit scenario
opgebouwd aan de hand van het veel uitgebreider degeneratiemodel DGRM. In dit netwerkmodel
moet de linkkwaliteit van elke link afzonderlijk opgegeven worden. Dit zorgt ervoor dat het nietbolvormig stralingspatroon van de Tmote Sky kan nagebootst worden door de ontvangstratio
en de signaalsterkte van de verschillende buren te gaan vari¨eren (zie figuur 4.3).
4.1 Methodologie
43
Interference
Omdat interferentie en het hidden node probleem een grote invloed heeft op de prestaties van het
netwerk, wordt in dit laatste scenario een netwerk gemodelleerd waarbij er veel meer interferentie
aanwezig is (zie figuur 4.4). De interferentieregio wordt hier opgetrokken tot 90 in plaats van 60
meter rond de versturende node, waardoor nu 45 nodes in plaats van 20 in de interferentie-regio
zitten.
Figuur 4.3: De linkspecificaties van het asymmetrisch scenario (links) zijn gebaseerd op het
stralingspatroon van de Tmote Sky (rechts).
4.1.3
iMinds w-iLab.t testbed
Wegens de vele beperkingen van de Cooja simulator (zie 2.3.1) worden de ontwikkelde linkinschattingsalgoritmes ook ge¨evalueerd op het iMinds w-iLab.t sensornetwerk aanwezig in het
Zuiderpoort kantoorgebouw (zie 2.4). Dit netwerk, met een kleine 200 nodes, is in staat om
de diverse scenario’s uit de simulator ook in de realiteit te gaan testen. Hiervoor gebruiken
we een vijftigtal nodes die verspreid zijn over de derde verdieping van het gebouw (zie figuur
4.5). De transmissiesterkte wordt standaard ingesteld op -15 dBm, waardoor we een multihop
netwerk bekomen met meerdere, alternatieve paden richting de sink en zo uitermate geschikt is
om de algoritmen voor linkestimatie te evalueren. Om veel interferentie van andere draadloze
communicatieapparatuur, microgolfovens en dergelijke te vermijden werden deze tests telkens
tussen 2 en 6u ’s nachts uitgevoerd.
4.1 Methodologie
44
Standard
Mobility
Asymmetric
Aantal nodes in simulatie
8x8 = 64
8x8 + 2 mobiele = 66
8x8 = 64
Transmissieregio
45m
45m
Obv. transmissiepatroon
Interferentieregio
60m
60m
60m
Cooja TX ratio
100 %
100 %
Obv. transmissiepatroon
Cooja RX ratio
65 %
65 %
Obv. transmissiepatroon
Degeneratiemodel
UDGM
UDGM
DGRM
Aantal connected
8
Afh. van positie
8
Aantal interferred
20
Afh. van positie
Obv. transmissiepatroon
Verzendratio
1 pakket/30s
1 pakket/30s
1 pakket/30s
Dense
Sparse
Interference
Bursty
Aantal nodes in simulatie
12x12 = 144
8x8 = 64
8x8 = 64
8x8 = 64
Transmissieregio
45m
30m
45m
45m
Interferentieregio
60m
40m
90m
60m
Cooja TX ratio
100 %
100 %
100 %
100 %
Cooja RX ratio
65 %
75 %
65 %
65 %
Degeneratiemodel
UDGM
UDGM
UDGM
UDGM
Aantal connected
25
4
8
8
Aantal interferred
45
8
45
20
Verzendratio
1 pakket/30s
1 pakket/30s
1 pakket/30s
3 pakketten/90s
Tabel 4.1: Overzicht van de verschillende Cooja scenario’s.
4.1 Methodologie
45
Figuur 4.4: Interferentie scenario in Cooja.
Standaard
Voor het standaard scenario wordt de sink in de rechterbovenhoek van het netwerk ingesteld
en worden twintig nodes, gelijk verspreid over het volledige netwerk, geselecteerd die deelnemen
aan het versturen en routeren van de pakketten (zie figuur 4.5). Deze twintig nodes sturen
opnieuw om de 20 tot 40 seconden, met een gemiddelde van 30 seconden, een pakket naar de
sink. De transmissiesterkte van -15 dBm zorgt ervoor dat elke node telkens meerdere mogelijke
buren heeft, waardoor de linkestimatie volledig tot zijn recht komt.
Figuur 4.5: Positionering en gebruikte sensornodes van het iMinds w-iLab.t in het standaard,
bursty, interference en asymmetrische scenario.
4.1 Methodologie
46
Bursty
Dit scenario heeft dezelfde specificaties als het standaard scenario (zie figuur 4.5), enkel worden
de pakketten in bursts van drie pakketten om de 60 tot 120, met een gemiddelde van 90, seconden
verstuurd. Het totaal aantal verstuurde pakketten blijft zo gelijk, enkel het verzendpatroon
wijzigt.
Dense
Dit scenario gebruikt alle nodes aanwezig op de derde verdieping van het Zuiderpoortgebouw,
ongeveer vijftig. Omdat de transmissiesterkte gelijk blijft, heeft elke node veel meer mogelijke
buren en treedt er ook veel meer interne interferentie op.
Sparse
Om een sparse netwerk te modelleren gebruiken we slechts een tiental nodes, gelijk verdeeld over
de volledige verdieping (zie figuur 4.6). Hierdoor heeft elke node maar 1 of 2 mogelijke ouders,
zijn er slechts een beperkt aantal mogelijke paden richting sink en wordt de interferentie sterk
beperkt.
Figuur 4.6: Gebruikte sensornodes van het iMinds w-iLab.t in het sparse scenario.
Asymmetrie
Omdat het testbed van nature al enige vorm van asymmetrie vertoont, wegens het gebruik van
echte sensornodes met een niet-bolvormig stralingspatroon (zie figuur 3.1), wordt deze asymmetrie in dit scenario nog wat versterkt. Dit wordt gerealiseerd door bepaalde sensornodes aan een
4.2 Implementatie
47
hoger of lager vermogen dan -15 dBm te laten verzenden, zo bekomen we een scenario waarin
bepaalde nodes het volledige netwerk kunnen bereiken en andere nodes maar 1 of 2 mogelijke
ouders hebben.
Interferentie
Om veel interferentie in het netwerk te bekomen, wordt het standaard scenario (zie figuur 4.5)
ook eens uitgevoerd tijdens de drukste kantooruren. Tijdens deze uren is er zeer veel externe
interferentie aanwezig, waardoor we de invloed hiervan kunnen bestuderen.
4.2
Implementatie
In deze sectie wordt dieper ingegaan op de precieze implementatie van de in hoofdstuk 3 besproken link-inschattingsalgoritmen in het besturingssysteem Contiki.
4.2.1
Linkestimatie in Contiki
Zoals besproken in sectie 3.3, maakt RPL gebruik van een onderscheid tussen link- en padmetrieken. Hierbij stelt de linkmetriek een waarde voor die de linkkwaliteit tussen twee nodes
voorstelt, hoe kleiner deze waarde hoe beter de linkkwaliteit. Elke node zal bij het aankomen van
een DIO-bericht de linkkwaliteit tussen zichzelf en de node waarvan het een DIO-bericht ontving
proberen in te schatten en aan deze linkkwaliteit een score toekennen. Het routeringsprotocol
in RPL gebruikt de som van alle linkmetrieken (of de padmetriek) op het pad richting de sink
om te routeren, waarbij de route met de laagste padmetriek wordt gekozen. Deze padmetriek
stuurt de node dan, aan de hand van zijn rank in de DIO-berichten, door naar zijn buren (zie
3.2).
ContikiOS zal bij aankomst van een DIO-bericht aan de linkestimator vragen om de linkkwaliteit
van deze link opnieuw te bepalen, dit omdat deze sterk kan verschillen van tijdstip tot tijdstip
(zie 3.1.1). Verder kan de totale padmetriek van de verzender van het DIO-bericht naar de sink
intussen ook gewijzigd zijn, omdat die node, of een node verder op het pad naar de sink, een
andere voorkeursouder heeft gekozen en hierdoor een andere rank bekomt.
Na het opnieuw bepalen van de linkkwaliteit en het toekennen van een nieuwe waarde voor de
linkmetriek, wordt aan het routeringsprotocol gevraagd of de verzender van dit DIO-bericht
4.2 Implementatie
48
geen betere voorkeursouder zou zijn, met andere woorden of de padmetriek nu niet kleiner is
dan de padmetriek van de route die momenteel gebruikt wordt.
Indien het routeringsprotocol beslist om van voorkeursouder te veranderen, wordt de Trickletimer voor het versturen van DIO-berichten opnieuw ingesteld en wordt de nieuwe informatie
rondgestuurd in het netwerk.
De hoofdtaak van de verschillende link-inschattingsalgoritmen is met andere woorden het toekennen van een kwaliteitsscore aan elke link tussen de node en zijn mogelijke ouders. Dit moet
op een betrouwbare en robuste manier gebeuren en moet, wegens de vereiste energie-effici¨entie,
gebeuren aan de hand van het bestaand verkeer van informatie- en RPL-berichten tussen deze
nodes (zie 3.2).
4.2.2
Verwijderstrategie van de oudertabel
Wegens het beperkte geheugen van de sensornodes kunnen deze geen oneindig grote lijst van
mogelijke ouders bijhouden. Het kan voorvallen dat nodes moeten toegevoegd worden aan de
oudertabel indien extra nodes aan het netwerk worden toegevoegd, indien een mobiele node binnen het bereik van deze node komt of wanneer andere omstandigheden in het netwerk wijzigen.
Verder kunnen nodes wegvallen indien hun batterij leeg raakt, ze verwijderd worden of in het
mobiele geval zich niet meer binnen het bereik van de node bevinden.
Indien een node wordt toegevoegd aan een reeds volledig bezette oudertabel moet er een andere
node verwijderd worden. Hiervoor wordt voor elke node een teller bijgehouden die elke seconde
verhoogd wordt. Indien een bericht wordt ontvangen, wordt de teller van de verzender terug
op 0 geplaatst. Bij het verwijderen wordt, indien er geen vrije plaats meer is, de oudste node
vervangen door de nieuwe node.
4.2.3
Objective Function 0
Dit algoritme, dat het aantal hops op het pad richting de sink probeert te minimaliseren (zie
3.4) is ´e´en van beide algoritmen die reeds in Contiki aanwezig zijn. Het is op een zeer eenvoudige manier ge¨ımplementeerd door aan elke link, onafhankelijk van de kwaliteit, de constante
waarde 256 toe te kennen. De linkmetriek is met andere woorden altijd gelijk, waardoor het
minimaliseren van de padmetrieken resulteert in een pad met een minimaal aantal hops (zie
figuur 4.7).
4.2 Implementatie
49
Figuur 4.7: Illustratie van de berekening van link- en padmetriek bij de objecttieffunctie 0.
Indien een node meerdere DIO-berichten met dezelfde rank ontvangt, wordt de ETX (zie 3.6.1)
waarde van deze link gebruikt om de knoop door te hakken. Indien deze ook gelijk zou zijn of
het verschil kleiner is dan een bepaalde parameter, wordt de eerst ingestelde ouder behouden
om de stabiliteit in het netwerk te verzekeren. Op deze manier garandeert dit algoritme een pad
met een minimaal aantal hops.
4.2.4
Received Signal Strength Indicator
De Received Signal Strength Indicator of RSSI (zie 3.5.1) wordt bij ontvangst van een pakket
ingesteld door de fysische laag en kan eenvoudig uitgelezen worden. Deze indicator neemt een
waarde aan in het interval [−50, −100], waarbij -50 een zeer sterk signaal voorstelt.
RSSIt = α ∗ RSSIt−1 + (1 − α) ∗ Last RSSI val
(4.1)
Deze waarde wordt bij ontvangst van een informatie of RPL-pakket uitgelezen en aan de hand van
een EWMA filter (zie formule 4.1) met α waarde 0,9 uitgemiddeld om stabiliteit te garanderen.
Deze EWMA gefilterde RSSI-waarde wordt door de link-estimator gebruikt om een score toe
te kennen aan deze link, dit gebeurt via de mapping in figuur 4.8. Deze mapping kent een
lage score toe aan een hoge signaalsterkte en vice versa. De mapping is bepaald op basis van
eigen metingen en [59] om het exponentieel karakter van de RSSI-waarde te modelleren, zodat
de toegekende linkmetriek evenredig verloopt met de PDR bij een bepaalde RSSI-waarde. Elke
RSSI-waarde groter dan -82 kan als behoorlijk goed gezien worden, waarden kleiner dan -82
4.2 Implementatie
50
RSSI Mapping 3000 Linkmetriek 2500 2000 1500 1000 500 0 -­‐100 -­‐95 -­‐90 -­‐85 -­‐80 -­‐75 -­‐70 -­‐65 -­‐60 -­‐55 -­‐50 RSSI waarde Figuur 4.8: Mapping van de RSSI-waarde op de linkmetriek.
worden exponentieel slechter en slechter.
Figuur 4.9: Illustratie van de berekening van link- en padmetriek bij de linkestimator gebaseerd
op RSSI.
Eenmaal de link-estimator een score aan de link heeft toegekend kan de padmetriek van het
pad langs deze ouder bepaald worden (zie figuur 4.9) en kan er eventueel van ouder gewisseld
worden.
4.2.5
Link Quality Indicator
De link-estimator op basis van de Link Quality Indicator of LQI (zie 3.5.2) werkt vrij gelijkaardig
aan de op de RSSI gebaseerde estimator. Na ontvangst van een RPL- of informatiepakket wordt
de ingestelde LQI, die waarden aanneemt in het interval [50, 110], uitgelezen en uitgemiddeld op
4.2 Implementatie
51
basis van de EWMA filter met α-waarde 0,9 in formule 4.2.
LQIt = α ∗ LQIt−1 + (1 − α) ∗ Last LQI val
(4.2)
Deze waarde wordt dan in combinatie met de voorbeeldmapping in figuur 4.10 gebruikt om een
kwaliteitswaarde voor deze link te bepalen.
LQI Mapping 16000 14000 Linkmetriek 12000 10000 8000 6000 4000 2000 0 50 55 60 65 70 75 80 85 90 95 100 105 110 LQI waarde Figuur 4.10: Mapping van de LQI-waarde op de linkmetriek.
Een uitgewerkt voorbeeld op figuur 4.11 toont hoe de LQI-waarde van een link de linkmetriek
tussen twee nodes bepaalt.
Figuur 4.11: Illustratie van de berekening van link- en padmetriek bij de linkestimator gebaseerd
op LQI.
4.2 Implementatie
4.2.6
52
Estimated Transmission Count
Het algoritme op basis van het verwacht aantal verzendpogingen is ook reeds in Contiki aanwezig
en wordt standaard gebruikt. Om de Estimated Transmission Count of ETX-waarde van een
link te bepalen wordt na het versturen van een pakket doorgegeven hoeveel pogingen er vereist
waren alvorens het pakket succesvol werd ontvangen. Deze waarde wordt opnieuw uitgemiddeld
door een EWMA filter met α-waarde 0,9.
De linkmetriek wordt dan eenvoudig bepaald door het vermeningvuldigen van de uitgemiddelde
ETX-waarde met een constante (hier 256), zoals in formule 4.3. Een voorbeeld van een dergelijke
berekening is te vinden in figuur 4.12.
Score(L) = 256 ∗ ET Xt (L)
(4.3)
Figuur 4.12: Illustratie van de berekening van link- en padmetriek bij de linkestimator gebaseerd
op ETX.
4.2.7
Four bit
Het link-inschattingsalgoritme gebaseerd op het Four bit algoritme gebruikt informatiebits uit
verschillende netwerklagen om op een intelligente manier de beste ouder te kiezen. De ontwikkelaars van dit algoritme kozen voor een werking met bits, omdat het toegankelijk maken van 1
bit geen sterke afhankelijkheid cre¨eert tussen de verschillende netwerklagen. Deze aanpak leidt
echter tot heel wat beperkingen in de informatie die verkregen kan worden, zo duidt de compare
4.2 Implementatie
53
bit enkel aan dat er een ouder is met een slechtere padmetriek, maar is er geen informatie over
welke ouder dit precies is.
Omdat het cre¨eren van een afhankelijkheid binnen de verschillende netwerklagen bij de implementatie toch geen probleem vormt, werd er bij implementatie in deze thesis gekozen om hiervan
af te stappen en enkel het eigenlijke idee van het combineren van informatie uit verschillende
netwerklagen te gebruiken.
Het in deze thesis ontwikkelde algoritme gebruikt enkel de white bit, dit om aan te geven of
de EWMA gefilterde LQI-waarde (zie formule 4.2) hoger is dan een constante waarde 105 (zie
formule 4.4). Verder wordt met de re¨ele waarden van bijvoorbeeld de RSSI of padmetriek
gewerkt.

 1 : LQIt (L) ≥ 105
W hitet (L) =
 0 : LQI (L) < 105
t
(4.4)
Bij het implementeren van dit algoritme, werd verder wat afgeweken van de standaardwerkwijze
aan de hand van link- en padmetrieken (zie 4.2.1). Deze Four bit implementatie zal niet enkel
een score toekennen aan een link en routeren op basis van de laagste padmetriek, maar gebruikt
een beslissingsdiagram om de beste van twee ouders te selecteren.
Figuur 4.13: Illustratie van de ouderselectie bij de linkestimator gebaseerd op het Four bit
algoritme.
4.2 Implementatie
54
Bij ontvangst van een DIO-bericht zal het algoritme nog steeds een link- en padmetriek berekenen
en deze verder uitsturen, volledig gelijkaardig aan het ETX algoritme. Deze link- en padmetriek
zal echter niet enkel en alleen gebruikt worden bij de ouderkeuze, maar zal een klein onderdeel
uitmaken van het beslissingsdiagram.
In de implementatie in deze thesis werd het beslissingsdiagram in figuur 4.13 gebruikt, de pseudocode van dit algoritme is te vinden in Algoritme 1. Bij elk ontvangen DIO-bericht zal Contiki
deze methode oproepen en bepalen of de verzender van dit DIO-bericht niet beter is dan de
huidige ouder.
Input White bit, padmetriek, RSSI na EWMA filter van beide links
Resultaat Meest geschikte link
if Indien de white bit voor ´e´en van beide links aanstaat then
if Padmetriek van de link met de white bit is beter (incl. threshold)) then
Kies de link met white bit als meest geschikt;
else
if Padmetriek van de andere link is beter (incl. dubbele threshold) then
Kies de link zonder white bit als meest geschikt;
else
Kies de link met white bit als meest geschikt;
end
end
else
if Beide links hebben zelfde padmetriek (of verschil kleiner dan threshold) then
Kies de link met de hoogste RSSI-waarde;
else
Kies link met de hoogste metriek;
end
end
Algoritme 1: Beslissingsalgoritme voor het Four bit algoritme
4.2.8
Fuzzy LQE
Net als het Four bit algoritme gebruikt het Fuzzy LQE algoritme verschillende informatiebronnen om de linkkwaliteit op een betrouwbare en robuste manier in te schatten (zie 3.6.3). Enkel
4.2 Implementatie
55
worden de informatiebronnen bij dit algoritme via een vaag regelsysteem omgevormd en gecombineerd om een kwaliteitsscore te bekomen.
Packet delivery ratio
Een eerste informatiebron bij het evalueren van een link is de end-to-end Packet Delivery Ratio
(PDR) (zie 4.1.1) op deze link. Om extra opslag van gegevens en berekening te vermijden wordt
voor deze metriek de estimated transmission count of ETX na uitmiddelling uit sectie 4.2.6
gebruikt. Hoe hoger de ETX-waarde, hoe meer transmissies nodig zijn en hoe lager de effectieve
PDR ligt.
Deze PDR wordt op een waarde in het interval [0, 1] gemapt aan de hand van de lidmaatschapsfunctie in figuur 4.14. Zo resulteert een ETX-waarde van 1 in een perfecte score van 1 en daalt
die score lineair tot een slechte score van 0 bij een slechte ETX van 4 of hoger.
Link stabiliteit
Een tweede metriek die binnen Fuzzy LQE gebruikt wordt, is de stabiliteit van de link waarover
we wensen te versturen. Deze bekomen door een geschiedenis van ETX-waarden bij te houden
en hierover de co¨effici¨ent van variantie te bepalen. Dit gebeurt aan de hand van formule 4.7.
n
1X
xi
n
i=1
p
ρ =
E[(X − µ)2 ]
ρ
cv =
µ
µ =
(4.5)
(4.6)
(4.7)
Deze co¨effici¨ent van variantie wordt dan opnieuw gemapt op een waarde in het interval [0, 1] aan
de hand van de lidmaatschapsfunctie in figuur 4.14. Zo resulteert een co¨effici¨ent van variantie
van 0 in een perfecte score van 1, waarna de score lineair zakt tot een score van 0 bij een
co¨effici¨ent van 0,7 of hoger.
Kanaalkwaliteit van de link
Een derde parameter is de kanaalkwaliteit van de link, hiervoor wordt de RSSI-waarde uit 4.2.4
na EWMA filteren aan de hand van formule 4.1 gebruikt. Deze waarde wordt aan de hand van
de lidmaatschapfunctie in figuur 4.15 gemapt tot een score in het interval [0, 1].
4.2 Implementatie
56
1 0.9 0.9 Lidmaatschapswaarde Lidmaatschapswaarde Lidmaatschapsfunc5e -­‐ Packet Delivery Rate 1 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Lidmaatschapsfunc5e -­‐ Stabiliteit 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 1.25 1.5 1.75 2 2.25 2.5 2.75 3 3.25 3.5 3.75 4 0 ETX waarde 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Coëfficiënt van varian5e Figuur 4.14: Links: lidmaatschapsfunctie voor de aankomstratio (PDR), rechts: lidmaatschapsfunctie voor de stabiliteit aan de hand van de co¨effici¨ent van variantie.
Linkkwaliteit van de link
De laatste informatiebron van het Fuzzy LQE algoritme gebruikt de LQI-waarde uit 4.2.5 als
modellering van de linkkwaliteit. Deze waarde wordt opnieuw na EWMA filteren aan de hand
van formule 4.2 gebruikt om aan de hand van de lidmaatschapfunctie in figuur 4.15 een score in
het interval [0, 1] te bepalen.
Lidmaatschapsfunc5e -­‐ Kanaalkwaliteit 1 0.9 Lidmaatschapsfunc4e -­‐ Linkkwaliteit 0.9 Lidmaatschapswaarde Lidmaatschapswaarde 1 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 -­‐100 -­‐95 -­‐90 -­‐85 -­‐80 -­‐75 -­‐70 RSSI waarde -­‐65 -­‐60 -­‐55 -­‐50 50 55 60 65 70 75 80 85 90 95 100 105 110 LQI waarde Figuur 4.15: Links: lidmaatschapsfunctie voor de kanaalkwaliteit aan de hand van de RSSI,
rechts: lidmaatschapsfunctie voor de linkkwaliteit aan de hand van de LQI.
Na het bepalen van een score voor de PDR, de stabiliteit, de kanaalkwaliteit en de linkkwaliteit
komt het er nog op aan om deze op een goede manier te gaan aggregeren naar een kwaliteitsscore.
Deze score moet alle informatiebronnen op een eenvoudige manier gaan combineren, waarbij met
4.2 Implementatie
57
elk van deze bronnen voldoende rekening wordt gehouden. De auteurs van het oorspronkelijke
Fuzzy LQE algoritme in [48] verklaren, zoals besproken in hoofdstuk 3, de beste resultaten te
bekomen met de Yagger-operator (zie formule 3.3). Deze operator zorgt ervoor dat de waarde
van de slechtste linkeigenschap voor een factor β (typisch 0,6) meespeelt in het eindresultaat en
wordt aangevuld met het gemiddelde van alle waarden.
Bij het implementeren van deze operator moet er wel rekening gehouden worden met het feit
dat er in sommige gevallen, vooral in de beginfase van de linkestimatie, nog nodige informatie
ontbreekt. Zo is het onmogelijk om de ETX-waarde te bepalen van een link waar er nog nooit een
bericht naar gestuurd is en is een co¨effici¨ent van variante niet te berekenen indien het algoritme
maar over 1 ETX-waarde beschikt. In deze gevallen mag het algoritme ook de waarde 0 niet
opnemen in de berekeningen, door de factor β (die typisch 0,6 bedraagt en het aandeel van de
minimale waarde bepaalt) zou deze nulwaarde veel te sterk gaan doorwegen bij het bepalen van
de uiteindelijke linkscore. Dit werd opgelost door de Yagger-operator enkel te laten inwerken op
de effectief bepaalde waarden.
De uiteindelijk geaggregeerde score µ(L) is hoog indien de link van hoge kwaliteit is en vice
versa. Daar het routeringsprotocol met linkmetrieken werkt die hoog zijn indien de link slecht
is, moet deze ge¨ınverteerd worden voor gebruik. Dit gebeurt via formule 4.8.
Linkmetriek(L) = 100 ∗ (1 − µ(L))
(4.8)
RESULTATEN
58
Hoofdstuk 5
Resultaten
In dit hoofdstuk worden de resultaten besproken van de evaluatiecriteria vermeld in hoofdstuk 4. De resultaten van de Cooja simulator (zie 2.3.1) worden eerst besproken, waarna de
conclusies geverifieerd worden op het iMinds w-iLab.t testbed (zie 2.4). De verschillende linkinschattingsalgoritmen worden telkens eerst besproken aan de hand van het standaard scenario.
Hierna worden alle andere scenario’s overlopen, waarbij de verschillen met de resultaten uit het
standaard scenario worden gelinkt met de verschillen in netwerkkarakteristieken tussen beide
scenario’s. Als laatste wordt ook de invloed van het MAC/RDC protocol en enkele andere
parameters besproken.
De verschillende link-inschattingsalgoritmen werden ontwikkeld in Contiki 2.7 en met behulp
van een MSP430-compiler omgezet naar broncode voor de TMote Sky sensornode (zie 2.1), die
zowel in de Cooja simulator als op het testbed gebruikt wordt. Alle tests, zowel de Cooja
simulaties als op het testbed, werden twee maal uitgevoerd om de variantie op de resultaten
te bepalen. Als eindresultaat werd het gemiddelde van beide resultaten gebruikt en wordt de
standaardafwijking aangeduid aan de hand van error bars.
ContikiOS 2.7 voorziet ook een aantal RPL-parameters die door de gebruiker kunnen ingesteld
worden, een overzicht is te vinden in tabel 5.1. De simulatietijden en de instellingen van de tests
in de Cooja simulator en op het iMinds w-iLab.t testbed zijn terug te vinden in tabel 5.2.
5.1 Cooja simulator
59
Instelling
Waarde
MAC protocol
CSMA met retransmissies
Radio Duty Cycling
ContikiMAC
Maximaal aantal retransmissies
5
Channel check rate (Hz)
16
Grootte buurtabel
16
Tabel 5.1: RPL-instellingen in ContikiOS 2.7.
Simulatietijden en -instellingen
Waarde
Cooja simulator
10 minuten
w-iLab.t testbed
30 minuten
Netwerk stabilisatietijd
1 minuut
Transmissiesterkte radio
-15 dBm
Snelheid mobiele nodes
2 m/s
Tabel 5.2: Simulatietijden en -instellingen.
5.1
Cooja simulator
In deze sectie worden de resultaten van de evaluatie van alle link-inschattingsalgoritmen in de
Cooja simulator besproken. Het is wel belangrijk dat we hierbij de beperkingen van de simulator
(zie 2.3.1) mee in rekening nemen.
5.1.1
Standaard scenario
De resultaten van het standard scenario in de Cooja simulator zijn te vinden in figuur 5.1. Het
onderzoek toont aan dat de complexere algoritmen, inzake Four bit en Fuzzy LQE, er in slagen
om een iets hogere PDR te bekomen dan de eerder eenvoudige varianten.
Deze complexere varianten hebben hiervoor wel een iets hoger aantal ouderwissels nodig en
veroorzaken zo wat extra RPL-overhead.
Het aantal retransmissies en het aantal hops toont bij de verschillende algoritmen weinig verschil,
enkel het RSSI algoritme kiest een pad dat gemiddeld 1 hop langer is. Dit RSSI algoritme lijkt
ook het minst stabiel te zijn, door de vele ouderwissels en bijhorende RPL-overhead heeft dit
algoritme ook het hoogste radio-on percentage.
5.1 Cooja simulator
60
4.5 Gemiddelde radio-­‐aan -jd (in %) Packet Delivery Ra/o (in %) 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b fuzzy 4 3.5 3 2.5 2 1.5 1 0.5 0 of0 (a) Packet Delivery Ratio
rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
2.5 RPL overhead (DIO-­‐berichten per node per minuut) 0.7 0.6 Aantal ouderwissels (per node per minuut) lqi 0.5 0.4 0.3 0.2 2 1.5 1 0.5 0.1 0 0 of0 lqi rssi etx 4b of0 fuzzy (c) Aantal ouderwissels per node
rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
1.6 Aantal CSMA retransmissies (per verzonden pakket) 7 Gemiddeld aantal hops lqi 6 5 4 3 2 1 1.4 1.2 1 0.8 0.6 0.4 0.2 0 0 of0 lqi rssi etx 4b (e) Gemiddeld aantal hops
fuzzy of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.1: Resultaten van het standaard scenario in de Cooja simulator.
Verder valt op dat het Four bit algoritme meer ouderwissels heeft dan het RSSI algoritme,
maar toch heel wat minder RPL-overhead veroorzaakt. De simulatielogs toonden dat dit komt
omdat de ouderwissels van het RSSI-algoritme veel meer verspreid in de tijd liggen. Het Four
bit algoritme vertoonde in het begin van de simulaties veel ouderwissels, terwijl deze bij het
5.1 Cooja simulator
61
RSSI-algoritme veel meer verspreid in de tijd voorkwamen.
Omdat elke ouderwissel de Trickle-timer reset, zorgen een reeks van meerdere ouderwissels op
een korte tijdspanne voor een beperkte stijging van de RPL-overhead. Een voorbeeld hiervan
wordt getoond in figuur 5.2. De figuur toont de werking van het Trickle-algoritme waarbij het
minimale interval tussen het verzenden van 2 DIO-berichten op 2 seconden en het maximale
interval op 32 seconden wordt ingesteld. De grafiek in stippellijn waarbij twee resets van de
timer in een kortere tijdspanne voorkomen, leidt uiteindelijk tot een situatie waarbij twee DIOberichten minder worden rondgestuurd.
Figuur 5.2: Illustratief voorbeeld van de werking van de Trickle-timer, waarbij twee resets in
een korte tijdspanne tot een lager aantal verstuurde DIO-berichten leiden.
Verder resulteren ouderwissels dieper in de DODAG-structuur in heel wat minder DIO-berichten
omdat DIO-berichten enkel neerwaarts worden doorgestuurd (zie figuur 5.3). In het linkse geval
wordt het DIO-bericht twee maal via een broadcast rondgestuurd, terwijl dit in het rechtse
voorbeeld vijf maal het geval is.
5.1 Cooja simulator
62
Figuur 5.3: Verschil in DIO propagatie bij verschillende posities van de node in de DODAG.
Het LQI algoritme scoort in alle opzichten gelijkaardig aan het of0 algoritme. Omdat de LQIwaarde in de simulator telkens op 37 wordt geplaatst (zie 2.3.1) is dit te verwachten, elke link
krijgt dezelfde linkmetriek waardoor het minimaliseren van de padmetriek resulteert in een
minimalisatie van het aantal hops, zoals bij het of0 algoritme. Hierdoor zijn beide algoritmes
ook het meest stabiel, ze resulteren het minst ouderwissels en het minst RPL-overhead.
5.1.2
Standaard vs sparse scenario
Dezelfde simulaties in een sparse scenario, waarbij het aantal nodes in het netwerk sterk wordt
verminderd, zouden tot minder verschil in de uiteindelijke resultaten moeten leiden. De linkestimator kan uit een kleiner aantal mogelijke paden kiezen, waardoor het nut van een degelijke
kwaliteitsinschatting wat verloren gaat.
De resultaten van het sparse scenario in de Cooja simulator zijn te vinden in figuur 5.4, waarbij
ook telkens de resultaten van het standaard scenario werden toegevoegd ter vergelijking.
Het onderzoek toont inderdaad veel minder variantie tussen de verschillende algoritmen. De
aankomstratio vertoont net als het aantal hops en het aantal retransmissies bijna geen verschil.
Hierdoor zijn zelfs de meest eenvoudige algoritmen, met een lage radio-on tijd en dus laag
energieverbuik, meer dan voldoende.
5.1 Cooja simulator
63
Packet Delivery Ra/o (in %) 0.9 0.8 0.7 0.6 SPARSE 0.5 STANDARD 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b Gemiddelde radio-­‐aan -jd (in %) 4.5 1 4 3.5 3 2.5 STANDARD 1.5 1 0.5 0 fuzzy of0 (a) Packet Delivery Ratio
lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
2.5 0.6 0.5 0.4 SPARSE STANDARD 0.3 0.2 0.1 RPL overhead (DIO-­‐berichten per node per minuut) 0.7 Aantal ouderwissels (per node per minuut) SPARSE 2 2 1.5 SPARSE STANDARD 1 0.5 0 0 of0 lqi rssi etx 4b of0 fuzzy (c) Aantal ouderwissels per node
lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
Gemiddeld aantal hops 6 5 4 SPARSE STANDARD 3 2 Aantal CSMA retransmissies (per verzonden pakket) 1.8 7 1.6 1.4 1.2 1 SPARSE 0.8 STANDARD 0.6 0.4 0.2 1 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.4: Resultaten van het standaard en sparse scenario in de Cooja simulator.
De resultaten vertonen wel een significant groter aantal ouderwissels en bijhorende RPL-overhead
bij het Fuzzy LQE algoritme. De configuratie van dit scenario in de simulator, waarbij elke node
slechts naar zijn horizontale en verticale buren kan sturen (zie 4.1.2) en de beperkte informatie
omtrent LQI- en RSSI-waarden (zie 2.3.1) die door de Cooja simulator worden geleverd veroorzaken geen duidelijk kwaliteitsverschil tussen de verschillende paden. Een hogere threshold bij
5.1 Cooja simulator
64
het vergelijken van twee padmetrieken zou dit probleem eenvoudig verhelpen. Dit probleem kan
ook bij het Four bit algoritme, weliswaar in beperkte mate, teruggevonden worden.
5.1.3
Standaard vs dense scenario
Omdat dit scenario een groter aantal nodes heeft op hetzelfde oppervlakte, kunnen we in tegenstelling tot bij de resultaten van het sparse scenario (zie 5.1.2) wel een groot verschil in
resultaten verwachten. Veel nodes resulteert in veel mogelijke paden naar de sink en veel meer
interne interferentie, waarbij het nut van het link-inschattingsalgoritme net ten goede moet
komen.
De resultaten van het dense scenario in de Cooja simulator zijn te vinden in figuur 5.5 en 5.6,
waarbij ook telkens de resultaten van het standaard scenario werden toegevoegd ter vergelijking.
De vele interferentie die in dit drukbezette netwerk aanwezig is zorgt ervoor dat de prestaties bij
alle algoritmen onder de prestaties van het standaard scenario liggen. Het zijn hoofdzakelijk het
op RSSI gebaseerde en het Four bit algoritme die heel wat minder presteren. Beide algoritmen
resulteren in een instabiel netwerk, waarbij de vele retransmissies voor een hoger energieverbruik
zorgen.
In dit scenario lijken het ETX- en Fuzzy LQE algoritme de beste prestaties te leveren en dit
Packet Delivery Ra/o (in %) 1 0.9 0.8 0.7 0.6 DENSE 0.5 STANDARD 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b fuzzy (a) Packet Delivery Ratio
Gemiddelde radio-­‐aan -jd (in %) zonder significant extra energieverbruik.
10 9 8 7 6 DENSE 5 STANDARD 4 3 2 1 0 of0 lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
Figuur 5.5: Resultaten van het standaard en dense scenario in de Cooja simulator.
5.1 Cooja simulator
65
2.5 Aantal ouderwissels (per node per minuut) 1.4 1.2 1 DENSE 0.8 STANDARD 0.6 0.4 0.2 RPL overhead (DIO-­‐berichten per node per minuut) 1.6 2 1.5 DENSE 0.5 0 of0 lqi rssi etx 4b STANDARD 1 0 fuzzy of0 (c) Aantal ouderwissels per node
lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
Gemiddeld aantal hops 6 5 4 DENSE STANDARD 3 2 Aantal CSMA retransmissies (per verzonden pakket) 4.5 7 4 3.5 3 2.5 DENSE 2 STANDARD 1.5 1 0.5 1 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.6: Resultaten van het standaard en dense scenario in de Cooja simulator.
5.1.4
Standaard vs asymmetrisch scenario
In het asymmetrisch scenario verwachten we de beste prestaties van de twee complexere algoritmen. De traditionele en eenvoudigere algoritmen zijn gekend om niet goed om te kunnen met
asymmetrie, dit omdat enkel de pakketten die aankomen verwerkt worden (zie figuur 3.9).
De resultaten van het asymmetrisch scenario in de Cooja simulator zijn te vinden in figuur 5.7,
waarbij ook telkens de resultaten van het standaard scenario werden toegevoegd ter vergelijking.
De prestaties van de complexere algoritmen vallen in de simulator wat tegen, opnieuw zal de
beperkt bruikbare informatie van de simulator geen winst opleveren ten opzichte van de klassieke
algoritmen. We verwachten een veel groter verschil bij de resultaten van het testbed.
De aanwezige asymmetrie zorgt ook voor heel wat meer retransmissies, ongeveer het dubbele
aantal van het standard scenario. Dit veroorzaakt ook de constant hogere radio-on tijd.
De reden waarom het gemiddeld aantal hops systematisch lager ligt dan bij het standard scenario
5.1 Cooja simulator
66
is te vinden bij de berekeningsmethode. Omdat er veel pakketten verloren gaan die door nodes
dieper in de DODAG-structuur verzonden werden en enkel de pakketten die effectief aankomen
gebruikt worden voor het bepalen van het gemiddeld aantal hops bekomen we een lager aantal
(zie 4.1.1).
6 0.8 0.7 0.6 ASYMMETRIC 0.5 STANDARD 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b Gemiddelde radio-­‐aan -jd (in %) Packet Delivery Ra/o (in %) 1 0.9 5 4 ASYMMETRIC 3 STANDARD 2 1 0 fuzzy of0 1.8 4 1.6 3.5 1.4 1.2 etx 4b fuzzy 3 2.5 1 ASYMMETRIC 0.8 STANDARD 0.6 0.4 ASYMMETRIC 2 STANDARD 1.5 1 0.5 0.2 0 0 of0 lqi rssi etx 4b of0 fuzzy (c) Aantal ouderwissels per node
lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
3.5 6 5 4 ASYMMETRIC STANDARD 3 2 1 Aantal CSMA retransmissies (per verzonden pakket) 7 Gemiddeld aantal hops rssi (b) Gemiddelde radio-on tijd (%)
RPL overhead (DIO-­‐berichten per node per minuut) Aantal ouderwissels (per node per minuut) (a) Packet Delivery Ratio
lqi 3 2.5 2 ASYMMETRIC STANDARD 1.5 1 0.5 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.7: Resultaten van het standaard en asymmetrisch scenario in de Cooja simulator.
5.1 Cooja simulator
5.1.5
67
Standaard vs interferentie scenario
Het interferentie scenario (zie 4.1.2) probeert om onder andere het hidden node probleem te
versterken door de interferentieregio te vergroten (zie sectie 3.1.1 en figuur 3.3).
De resultaten zijn te vinden in figuur 5.8, waarbij opnieuw telkens de resultaten van het standaard scenario werden toegevoegd ter vergelijking.
Packet Delivery Ra/o (in %) 0.8 0.7 0.6 INTERFERENCE 0.5 STANDARD 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b Gemiddelde radio-­‐aan -jd (in %) 6 1 0.9 5 4 STANDARD 2 1 0 fuzzy of0 (a) Packet Delivery Ratio
lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
3 RPL overhead (DIO-­‐berichten per node per minuut) 1.2 Aantal ouderwissels (per node per minuut) INTERFERENCE 3 2.5 1 0.8 INTERFERENCE 0.6 STANDARD 0.4 2 INTERFERENCE 1.5 STANDARD 1 0.5 0.2 0 of0 lqi rssi etx 4b 0 fuzzy of0 (c) Aantal ouderwissels per node
lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
Gemiddeld aantal hops 6 5 4 INTERFERENCE STANDARD 3 2 Aantal CSMA retransmissies (per verzonden pakket) 2.5 7 2 1.5 INTERFERENCE STANDARD 1 0.5 1 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.8: Resultaten van het standaard en interference scenario in de Cooja simulator.
5.1 Cooja simulator
68
Het verschil in aankomstratio in de Cooja simulator blijft vrij beperkt, enkel het RSSI en Four
bit algoritme lijken wat meer be¨ınvloed te worden door de grotere interferentieregio. Het ETXalgoritme haalt zelfs een ietwat hoger aankomstpercentage en een lager aantal retransmissies,
maar het verschil blijft vrij beperkt.
Verder resulteert de grotere interferentieregio in een systematisch hogere radio-on tijd. Het valt
op dat het RSSI-algoritme niet goed overweg kan met de vele interferentie, het algoritme is niet
stabiel en bekomt ook de laagste aankomstratio.
5.1.6
Standaard vs bursty scenario
In dit scenario wordt de invloed van het verzendgedrag bestudeerd, de resultaten zijn te vinden
in figuur 5.9 en 5.10.
De resultaten van de simulator zijn voor alle link-inschattingsalgoritmen zeer gelijkaardig, de
aankomstratio ligt een stuk lager, terwijl de radio-on tijd ongeveer gelijk blijft. Opvallend is de
grotere daling bij het Four bit algoritme, dit algoritme blijkt bijzonder gevoelig te zijn inzake
verzendgedrag.
Het licht lager aantal hops bij dit scenario zal terug te wijten zijn aan de lagere aankomstratio
van de verafgelegen nodes. Ook het aantal retransmissies ligt systematisch lager, wellicht door
het meer gespreid versturen. Een burst van drie pakketten verzenden duurt wel wat langer,
maar de tijd tussen twee bursts verdrievoudigt ook.
4.5 0.8 0.7 0.6 BURSTY 0.5 STANDARD 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b fuzzy (a) Packet Delivery Ratio
Gemiddelde radio-­‐aan -jd (in %) Packet Delivery Ra/o (in %) 1 0.9 4 3.5 3 2.5 BURSTY STANDARD 2 1.5 1 0.5 0 of0 lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
Figuur 5.9: Resultaten van het standaard en bursty scenario in de Cooja simulator.
5.1 Cooja simulator
69
3 Aantal ouderwissels (per node per minuut) 0.7 0.6 0.5 BURSTY 0.4 STANDARD 0.3 0.2 0.1 RPL overhead (DIO-­‐berichten per node per minuut) 0.8 0 of0 lqi rssi etx 4b 2 BURSTY 1.5 STANDARD 1 0.5 0 fuzzy of0 (c) Aantal ouderwissels per node
lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
1.6 6 5 4 BURSTY STANDARD 3 2 1 Aantal CSMA retransmissies (per verzonden pakket) 7 Gemiddeld aantal hops 2.5 1.4 1.2 1 BURSTY 0.8 STANDARD 0.6 0.4 0.2 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.10: Resultaten van het standaard en bursty scenario in de Cooja simulator.
5.1.7
Mobiliteit
In deze sectie bespreken we het mobiliteitsscenario in de Cooja simulator (zie 4.1.2).
Figuur 5.11 toont aan dat de aankomstratio in dit scenario behoorlijk laag ligt en er weinig
variantie in de aankomstratio en energieverbruik zit. Enkel het RSSI algoritme lijkt opnieuw
niet tot een stabiel netwerk te komen.
We kunnen concluderen dat het Objective Function 0 algoritme in dit geval als beste algoritme
kan gezien worden. Het algoritme haalt een gelijkaardige prestatie aan het Fuzzy LQE algoritme,
maar is stabieler en heeft een lager energieverbruik. De vele overhead die door een mobiele node
wordt gegenereerd zorgt er voor dat een eenvoudig algoritme toch zeer goed presteert.
5.1 Cooja simulator
70
9 Gemiddelde radio-­‐aan -jd (in %) Packet Delivery Ra/o (in %) 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b fuzzy 8 7 6 5 4 3 2 1 0 of0 (a) Packet Delivery Ratio
etx 4b fuzzy 7 RPL overhead (DIO-­‐berichten per node per minuut) 0.7 Aantal ouderwissels (per node per minuut) rssi (b) Gemiddelde radio-on tijd (%)
0.8 0.6 0.5 0.4 0.3 0.2 0.1 0 6 5 4 3 2 1 0 of0 lqi rssi etx 4b fuzzy (c) Aantal ouderwissels per node
of0 lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
7 Aantal CSMA retransmissies (per verzonden pakket) 6 Gemiddeld aantal hops lqi 5 4 3 2 1 6 5 4 3 2 1 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.11: Resultaten van het mobiliteitsscenario in de Cooja simulator.
5.1.8
Conclusie Cooja simulator
De Cooja simulator leert ons dat de complexere algoritmen in veel gevallen in staat zijn om
de informatie vanuit de verschillende netwerklagen om te zetten in een intelligente linkkeuze.
Omdat deze algoritmen vaker van ouder gaan wisselen, genereren ze een niet te verwaarlozen
5.2 iMinds w-iLab.t testbed
71
RPL-overhead.
In eenvoudige netwerken, zoals het sparse scenario, en in netwerken waar bijvoorbeeld mobiliteit
al tot hoge overhead leidt, slagen deze algoritmen er niet in om een significant hogere aankomstratio te bekomen. In deze gevallen kan het gebruik van een eenvoudig hop-count algoritme voor
gelijkaardige prestaties, maar met minder overhead en energieverbruik zorgen.
Het asymmetrisch en interferentie scenario vertonen geen uitdrukkelijke winnaar, wellicht is de
Cooja simulator te beperkt om hier duidelijke verschillen in op te merken.
Bij het bursty en dense scenario bekomen we een constant lagere aankomstratio en een hoger
aantal retransmissies, waarbij het ETX-algoritme het kleinste prestatieverschil vertoont.
5.2
iMinds w-iLab.t testbed
In deze sectie worden de resultaten van de evaluatie van alle link-inschattingsalgoritmen op
het iMinds w-iLab.t testbed (zie 2.4) besproken. Met deze evaluatie wordt geprobeerd om de
conclusies van de Cooja simulator te verifi¨eren. Natuurlijk moet er rekening gehouden worden
met het feit dat een real-life testbed al inherent asymmetrisch is en er veel factoren, zoals externe
interferentie, niet te controleren zijn. Wegens beperkingen van het iMinds w-iLab.t testbed kon
het mobiliteitsscenario niet getest worden in deze real-life omgeving.
5.2.1
Standaard scenario
De resultaten van het standaard scenario zijn te vinden in figuur 5.12.
Op het testbed bekomen de complexere algoritmen opnieuw de beste resultaten, enkel lijkt het
Fuzzy LQE algoritme nog wat beter te presteren dan Four bit. Terwijl de complexere algoritmen
op het testbed een lagere gemiddelde radio-on tijd noteerden, tonen de simulaties op het testbed
het tegenovergestelde resultaat. Dit is waarschijnlijk te wijten aan het onrealistisch simuleren
van de radio-aan tijd bij het verzenden en ontvangen in de Cooja simulator.
Het aantal retransmissies vertoont verder een grotere variantie, de algoritmen die minder presteren leveren een veel hoger aantal retransmissies op. Het of0 algoritme is het meest stabiel
met het laagste aantal ouderwissels, maar heeft de laagste PDR en het meest retransmissies
nodig. Het minimaliseren van het aantal hops zorgt met andere woorden voor links van een
lagere kwaliteit, waardoor meer retransmissies nodig zijn.
5.2 iMinds w-iLab.t testbed
72
2.5 Gemiddelde radio-­‐aan -jd (in %) Packet Delivery Ra/o (in %) 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b fuzzy 2 1.5 1 0.5 0 of0 0.4 1.6 0.35 1.4 0.3 0.25 0.2 0.15 0.1 etx 4b fuzzy 1.2 1 0.8 0.6 0.4 0.2 0.05 0 0 of0 lqi rssi etx 4b of0 fuzzy (c) Aantal ouderwissels per node
lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
4 Aantal CSMA retransmissies (per verzonden pakket) 3 Gemiddeld aantal hops rssi (b) Gemiddelde radio-on tijd (%)
RPL overhead (DIO-­‐berichten per node per minuut) Aantal ouderwissels (per node per minuut) (a) Packet Delivery Ratio
lqi 2.5 2 1.5 1 0.5 3.5 3 2.5 2 1.5 1 0.5 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.12: Resultaten van het standaard scenario op het testbed.
5.2.2
Standaard vs sparse scenario
Het sparse scenario (zie figuur 5.13) vertoont op het testbed resultaten met meer variantie dan
in de simulator, maar dit is te verklaren door het niet perfect controleerbaar zijn van een real-
5.2 iMinds w-iLab.t testbed
73
life testbed. Indien we de combinatie aankomstratio en energieverbruik als maatstaf nemen
scoren de complexere algoritmen opnieuw wat beter, maar het verschil is erg klein. Het beperkt
aantal paden richting de sink zorgt ook voor zeer een goeie prestatie van het ojectieffunctie 0
algoritme. Het slaagt erin om met een heel lage overhead en heel klein aantal retransmissies
toch een opmerkelijk goede PDR neer te zetten.
Packet Delivery Ra/o (in %) 0.9 0.8 0.7 0.6 SPARSE 0.5 STANDARD 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b Gemiddelde radio-­‐aan -jd (in %) 2.5 1 2 1.5 STANDARD 1 0.5 0 fuzzy of0 (a) Packet Delivery Ratio
0.4 1.6 0.35 1.4 0.3 0.25 SPARSE 0.2 STANDARD 0.15 lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
0.1 0.05 RPL overhead (DIO-­‐berichten per node per minuut) Aantal ouderwissels (per node per minuut) SPARSE 1.2 1 SPARSE 0.8 STANDARD 0.6 0.4 0.2 0 0 of0 lqi rssi etx 4b of0 fuzzy (c) Aantal ouderwissels per node
lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
Gemiddeld aantal hops 2.5 2 SPARSE 1.5 STANDARD 1 0.5 Aantal CSMA retransmissies (per verzonden pakket) 4 3 3.5 3 2.5 SPARSE 2 STANDARD 1.5 1 0.5 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.13: Resultaten van het standaard en sparse scenario op het testbed.
5.2 iMinds w-iLab.t testbed
5.2.3
74
Standaard vs dense scenario
Vreemd genoeg lijkt het gebruik van alle beschikbare nodes op het testbed een betere prestatie
te leveren dan het standaard scenario (zie figuur 5.14 en 5.15). Het aantal nodes lijkt nog niet
voldoende te zijn om veel interne interferentie en mindere prestaties af te dwingen.
De ETX- en Fuzzy LQE algoritmen scoren uitzonderlijk goed, dit zowel qua aankomstratio als op
vlak van energieverbruik. Blijkbaar is het Four bit algoritme ook niet in staat om alle informatie
op een goede manier te verwerken, het algoritme heeft door de vele retransmissies een veel hoger
energieverbruik bij gelijkaardige prestaties.
Verder tonen de resultaten dat het RPL-protocol het hogere aantal nodes effectief gebruikt door
gemiddeld langere paden te gebruiken om de pakketten bij de sink te krijgen.
Ook het eenvoudige objectieffunctie 0 algoritme scoort in dit scenario zeer goed, wellicht zorgt
het uitblijven van de RPL-overhead ervoor dat het aantal collisies binnen het netwerk beperkt
blijft en de de pakketten toch vlot tot bij de sink raken.
Het algoritme dat gebruikt maakt van de RSSI-waarde resulteert op het testbed opnieuw niet
in een stabiel netwerk, waardoor de resultaten van de simulator hier kunnen bevestigd worden.
Packet Delivery Ra/o (in %) 0.9 0.8 0.7 0.6 DENSE 0.5 STANDARD 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b fuzzy (a) Packet Delivery Ratio
Gemiddelde radio-­‐aan -jd (in %) 4 1 3.5 3 2.5 DENSE 2 STANDARD 1.5 1 0.5 0 of0 lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
Figuur 5.14: Resultaten van het standaard en dense scenario op het testbed.
5.2 iMinds w-iLab.t testbed
75
Aantal ouderwissels (per node per minuut) 1.2 1 RPL overhead (DIO-­‐berichten per node per minuut) 2.5 1.4 2 1.5 0.8 DENSE STANDARD 0.6 0.4 DENSE STANDARD 1 0.5 0.2 0 of0 lqi rssi etx 4b 0 fuzzy of0 (c) Aantal ouderwissels per node
lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
Gemiddeld aantal hops 3.5 3 2.5 DENSE 2 STANDARD 1.5 1 Aantal CSMA retransmissies (per verzonden pakket) 4 4 3.5 3 2.5 DENSE 2 STANDARD 1.5 1 0.5 0.5 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.15: Resultaten van het standaard en dense scenario op het testbed.
5.2.4
Standaard vs asymmetrische scenario
De resultaten van het asymmetrisch scenario (zie figuur 5.16) tonen een grotere variantie dan
in de simulator. Terwijl de prestaties van de eenvoudigere algoritmes een tiental procent daalt,
kunnen de complexere varianten zelfs betere prestaties leveren dan het standaard scenario. Gemiddeld gezien worden heel wat meer hops gebruikt, dit omdat heel wat paden uit het standaard
scenario wegens de asymmetrie niet meer gebruikt kunnen worden.
De reden waarom de complexere algoritmen een hogere aankomstratio verkrijgen is te vinden in
de configuratie van het netwerk. Om de asymmetrie van het netwerk wat te versterken wordt de
transmissiesterkte van bepaalde nodes verhoogd en verlaagd, waardoor sommige nodes nu naar
veel meer nodes kunnen sturen en andere nodes maar ´e´en of zelfs geen andere node binnen hun
bereik hebben. De complexere algoritmes lijken daar goed op in te spelen en handig gebruik te
maken van de nodes die het sterkste zendvermogen hebben.
5.2 iMinds w-iLab.t testbed
76
3.5 0.8 0.7 0.6 ASYMMETRIC 0.5 STANDARD 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b Gemiddelde radio-­‐aan -jd (in %) Packet Delivery Ra/o (in %) 1 0.9 3 2.5 2 0.5 0 fuzzy of0 0.45 1.6 0.4 1.4 0.35 0.3 0.25 ASYMMETRIC 0.2 lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
STANDARD 0.15 0.1 0.05 RPL overhead (DIO-­‐berichten per node per minuut) Aantal ouderwissels (per node per minuut) STANDARD 1 (a) Packet Delivery Ratio
1.2 1 ASYMMETRIC 0.8 STANDARD 0.6 0.4 0.2 0 0 of0 lqi rssi etx 4b of0 fuzzy (c) Aantal ouderwissels per node
lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
6 3.5 3 2.5 ASYMMETRIC 2 STANDARD 1.5 1 0.5 Aantal CSMA retransmissies (per verzonden pakket) 4 Gemiddeld aantal hops ASYMMETRIC 1.5 5 4 ASYMMETRIC 3 STANDARD 2 1 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.16: Resultaten van het standaard en asymmetrische scenario op het testbed.
Het aantal ouderwissels daalt bij het ETX en Four bit algoritme zeer sterk. De asymmetrie
versterkt de kwaliteitsverschillen waardoor er, indien eenmaal een goed pad gevonden is, niet
snel meer gewisseld wordt. Aangezien beide algoritmen ook een lager aantal retransmissies
vertonen, kunnen we concluderen dat ETX en Four bit de asymmetrie goed kunnen inschatten
en er zelf voordeel uit halen door alternatieve paden, waarbij de link in dit scenario van hogere
5.2 iMinds w-iLab.t testbed
77
kwaliteit is, te gebruiken.
We kunnen concluderen dat de complexere algoritmen hun nut in de tests op het testbed wel
hebben aangetoond. Intelligentere bepaling van de linkkwaliteit houdt duidelijk rekening met
meerdere factoren dan enkel de effectief aangekomen pakketten, waardoor asymmetrie geen groot
probleem vormt en zelfs nuttig gebruikt kan worden. De beperkingen van de simulator zorgen
ervoor dat er weinig echt verschil te merken is in deze resultaten.
5.2.5
Standaard vs interferentie scenario
Om de interferentie op het testbed te verhogen, werd dit scenario tijdens de drukke kantooruren
uitgevoerd zodat interferentie van draadloos internet, beweging en dergelijke niet uit de weg
gegaan wordt. De resultaten zijn terug te vinden in figuur 5.17.
Terwijl het Four bit algoritme het in de Cooja simulator wat minder en het ETX-algoritme het
wat beter deed dan in het standaard scenario, tonen de resultaten van het testbed een totaal
omgekeerd beeld. Het ETX-algoritme lijkt niet overweg te kunnen met de externe interferentie,
terwijl dat bij het Four bit algoritme zelfs beter lukt dan in het standard scenario. Wellicht komt
hier het verschil in type interferentie tot uiting, in de simulator wordt enkel interne interferentie
gebruikt door het uitbreiden van de interferentieregio, terwijl we op het testbed enkel gebruik
maken van de aanwezige externe interferentie van een kantoorgebouw. Anderzijds kan ook
de mate van interferentie bepalend zijn, of kan de beperkte informatie omtrent LQI en RSSI
waarden in de Cooja simulator de oorzaak zijn.
Verrassend genoeg slaagt ook het objectieffunctie 0 algoritme er in om beter te scoren dan in het
standaard scenario, met een lager aantal retransmissies en lagere radio-on tijd kan dit algoritme
toch een hogere ontvangstratio optekenen.
5.2 iMinds w-iLab.t testbed
78
4 0.8 0.7 0.6 INTERFERENCE 0.5 STANDARD 0.4 0.3 0.2 0.1 Gemiddelde radio-­‐aan -jd (in %) Packet Delivery Ra/o (in %) 1 0.9 3.5 3 2.5 lqi rssi etx 4b 1 0.5 0 fuzzy of0 (a) Packet Delivery Ratio
rssi etx 4b fuzzy 2.5 1 0.8 RPL overhead (DIO-­‐berichten per node per minuut) Aantal ouderwissels (per node per minuut) lqi (b) Gemiddelde radio-on tijd (%)
1.2 2 1.5 INTERFERENCE 0.6 STANDARD 0.4 INTERFERENCE STANDARD 1 0.5 0.2 0 of0 lqi rssi etx 4b 0 fuzzy of0 (c) Aantal ouderwissels per node
lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
4 3 2.5 2 INTERFERENCE STANDARD 1.5 1 Aantal CSMA retransmissies (per verzonden pakket) 3.5 Gemiddeld aantal hops STANDARD 1.5 0 of0 INTERFERENCE 2 3.5 3 2.5 INTERFERENCE 2 STANDARD 1.5 1 0.5 0.5 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.17: Resultaten van het standaard en interferentie scenario op het testbed.
5.2.6
Standaard vs bursty scenario
Op het testbed verkrijgen we opnieuw tegenstrijdige resultaten inzake aankomstratio ten opzichte van de simulator, want hier haalt het bursty scenario constant hogere aankomstratio’s
dan het standaard scenario (zie figuur 5.18). Hierdoor resulteert het gemiddeld aantal hops
5.2 iMinds w-iLab.t testbed
79
ook in een constant hoger resultaat voor het bursty scenario. Deze resultaten lijken ons heel
wat realistischer omdat het verzenden in bursts voor langere interferentie-vrije periodes zorgt
waardoor we een hogere aankomstratio verwachten.
3 0.8 0.7 0.6 BURSTY 0.5 STANDARD 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b Gemiddelde radio-­‐aan -jd (in %) Packet Delivery Ra/o (in %) 1 0.9 2.5 2 0.5 0 fuzzy of0 lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
1.6 0.5 0.4 BURSTY 0.3 STANDARD 0.2 0.1 RPL overhead (DIO-­‐berichten per node per minuut) 0.6 Aantal ouderwissels (per node per minuut) STANDARD 1 (a) Packet Delivery Ratio
0 of0 lqi rssi etx 4b 1.4 1.2 1 STANDARD 0.6 0.4 0.2 of0 3.5 3.5 3 BURSTY STANDARD 1.5 1 0.5 Aantal CSMA retransmissies (per verzonden pakket) 4 4 2 lqi rssi etx 4b fuzzy (d) Aantal verstuurde DIO berichten
4.5 2.5 BURSTY 0.8 0 fuzzy (c) Aantal ouderwissels per node
Gemiddeld aantal hops BURSTY 1.5 3 2.5 BURSTY 2 STANDARD 1.5 1 0.5 0 0 of0 lqi rssi etx 4b fuzzy (e) Gemiddeld aantal hops
of0 lqi rssi etx 4b fuzzy (f) Aantal retransmissies
Figuur 5.18: Resultaten van het standaard en bursty scenario op het testbed.
5.3 Invloed van het MAC/RDC protocol
5.2.7
80
Conclusie iMinds w-iLab.t testbed
Na de simulaties op het iMinds w-iLab.t testbed kan geconcludeerd worden dat de complexere
algoritmen het best presteren, waarbij Fuzzy LQE nog een kleine voorsprong op Four bit lijkt
te nemen door een gemiddeld hogere aankomstratio en lager energieverbruik.
Wel blijkt objectieffunctie 0 opnieuw de beste prestaties te leveren in het sparse scenario en komt
het nut van de complexere algoritmen in het asymmetrische scenario volledig tot zijn recht.
De resultaten van het dense en mobiliteitsscenario kunnen helaas niet geverifieerd worden, omdat
het testbed hiervoor te beperkt blijkt te zijn. Naast deze beperkingen kunnen we ook vaststellen
dat het testbed, wegens het oncontroleerbaar zijn van diverse factoren, veel meer variantie toont
in de verkregen resultaten. Zo bekomen we ook tegenstrijdige resultaten in het interferentie
en bursty scenario. De eventuele oorzaken van deze verschillen kunnen in verder onderzoek
bestudeerd worden.
5.3
Invloed van het MAC/RDC protocol
Omdat het gebruikte Medium Access Control (MAC) en Radio Duty Cycling (RDC) protocol
hoogstwaarschijnlijk een grote invloed heeft op de prestaties van het netwerk, werden er in Cooja
ook enkele simulaties uitgevoerd waarbij de standaard combinatie van ContikiMAC met CSMA
retransmissies vervangen werd door enkele andere, in ContikiOS ge¨ımplementeerde RDC- en
MAC-protocollen (zie 2.3.2).
5.3.1
Invloed van de MAC driver
Contiki bevat een implementatie van twee Medium Access Control (MAC) drivers: het standaard
ingestelde ContikiMAC met Carrier Sense Multiple Access (CSMA) dat wacht tot het medium
vrij is alvoren het pakket te verzenden en NullMAC die het pakket onmiddellijk en zonder
controle verstuurt. In deze sectie wordt het standaard scenario in de Cooja simulator herhaald
om de invloed van de gekozen MAC driver te bepalen. De resultaten van deze simulaties zijn te
vinden in figuur 5.19.
5.3 Invloed van het MAC/RDC protocol
81
Packet Delivery Ra/o (in %) 0.9 0.8 0.7 0.6 NULLMAC 0.5 STANDARD 0.4 0.3 0.2 0.1 0 of0 lqi rssi etx 4b fuzzy (a) Packet Delivery Ratio
Gemiddelde radio-­‐aan -jd (in %) 4.5 1 4 3.5 3 2.5 NULLMAC STANDARD 2 1.5 1 0.5 0 of0 lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
Figuur 5.19: Resultaten van het standaard scenario met en zonder CSMA retransmissies in de
Cooja simulator.
Het onderzoek toont aan dat het uitschakelen van het CSMA en retransmissie mechanisme
een zeer grote invloed heeft op de prestaties. De ontvangstratio zakt tot rond de vijf procent,
waarbij alle ontvangen pakketten van nodes afkomstig zijn die maximaal twee hops van de sink
verwijderd zijn. Het uitschakelen van de CSMA retransmissies leidt echter wel tot een daling
van het energieverbruik, maar dit weegt niet op tegen de slechte prestaties die behaald worden.
5.3.2
Invloed van de RDC driver
In Contiki is de RDC driver verantwoordelijk voor het op tijd aan- en uitschakelen van de radio.
ContikiMAC is als standaard driver speciaal geoptimaliseerd om te gebruiken in samenwerking
met Contiki (zie 2.3.2). Verder voorziet Contiki nog implementaties van onder andere X-MAC
[37], CX-MAC en NullRDC. De resultaten van elk van deze drivers op het standaard scenario
in Cooja zijn te vinden in figuur 5.20.
5.3 Invloed van het MAC/RDC protocol
82
20 0.8 0.7 Con=kiMAC 0.6 NullRDC 0.5 X-­‐MAC 0.4 CX-­‐MAC 0.3 0.2 0.1 0 of0 lqi rssi etx 4b fuzzy Gemiddelde radio-­‐aan -jd (in %) Packet Delivery Ra/o (in %) 1 0.9 18 16 14 Con8kiMAC 12 NullRDC 10 X-­‐MAC 8 CX-­‐MAC 6 4 2 0 (a) Packet Delivery Ratio
of0 lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
Figuur 5.20: Resultaten van het standaard scenario met verschillende RDC-drivers in de Cooja
simulator.
Uit de resultaten blijkt dat ContikiMAC met CSMA een veel hogere aankomstratio weet te
behalen dan de andere RDC-drivers en hier zelfs heel wat minder energie voor nodig heeft.
De NullRDC driver, die de radio nooit uitschakelt en een energieverbruik van 100% bekomt,
heeft net als NullMAC (zie figuur 5.19) geen CSMA en retransmissie mechanisme. Toch haalt
NullRDC een aankomstratio die ongeveer drie maal zo hoog is als NullMAC, omdat het de
radio niet uitschakelt. De X-MAC implementatie behaalt een iets lagere aankomstratio, maar
schakelt wel geregeld de radio uit zodat de radio-on tijd zakt naar een kleine 12 procent. Zoals
het onderzoek in [36] aantoonde, gebruikt deze standaard implementatie nog steeds veel meer
energie dan het geoptimaliseerde ContikiMAC. Het CX-MAC protocol, dat een iets minder
strikte timing dan X-MAC naleeft, scoort op beide vlakken nog iets minder, maar dit algoritme
is vanwege die minder strikte timing wel bruikbaar op een groter aantal radio’s.
De prestaties van de verschillende link-inschattingsalgoritmen komen wel terug bij alle gesimuleerde MAC-protocollen. De complexere algoritmen resulteren opnieuw in een netwerk
met een iets hoger aankomstratio en een beperkt energieverbruik.
De keuze voor een be-
paald MAC-protocol lijkt weinig tot geen invloed te hebben op de prestaties tussen de linkinschattingsalgoritmen onderling, maar zorgt eerder voor een algemeen prestatieverschil.
5.3.3
Invloed van de Channel Check Rate
Nu we kunnen concluderen dat ContikiMAC met CSMA op alle vlakken beter scoort dan de
alternatieven, kan de invloed van de Channel Check Rate (CCR) bepaald worden. Deze variabele
5.4 Invloed van de aggregator bij Fuzzy LQE
83
wordt uitgedrukt in Hertz (Hz) en stelt het aantal keer per seconde voor dat het MAC- en
RDC-protocol de radio aanschakelen en het medium controleren om een eventuele transmissie
te detecteren. In ContikiOS kan deze frequentie ingesteld worden op 2, 4, 8 of 16 keer per
Packet Delivery Ra/o (in %) 1 0.9 0.8 0.7 2 0.6 4 0.5 0.4 8 0.3 16 0.2 0.1 0 of0 lqi rssi etx 4b (a) Packet Delivery Ratio
fuzzy Gemiddelde radio-­‐aan -jd (in %) seconde.
4.5 4 3.5 3 2 2.5 4 2 8 1.5 16 1 0.5 0 of0 lqi rssi etx 4b fuzzy (b) Gemiddelde radio-on tijd (%)
Figuur 5.21: Resultaten van het standaard scenario met verschillende CCR frequenties in de
Cooja simulator.
De resultaten tonen aan dat de aankomstratio stijgt indien een hogere CCR gebruikt wordt,
vooral indien we van 8 naar 16 Hz overstappen. Deze stijging gaat echter gepaard met een hoger
energieverbruik, al is dit echter beperkt voor de betere prestaties die we verkrijgen. Verder
bekomen we opnieuw gelijkaardige verhoudingen tussen de link-inschattingsalgoritmen onderling,
waaruit blijkt dat de keuze voor een bepaalde CCR opnieuw eerder een algemene invloed heeft.
5.4
Invloed van de aggregator bij Fuzzy LQE
Zoals besproken in 3.6.3 gebruikt het Fuzzy LQE algoritme de Yagger operator (zie 3.3) om de
verschillende lidmaatschapswaarden te gaan combineren tot een eindscore, waaruit de linkmetriek berekend wordt via formule 4.8. In de literatuur rond vage regelsystemen komen heel wat
verschillende aggregatoren, of t-normen, voor [49, 50]. Het gebruik van verschillende t-normen
kan leiden tot zeer uiteenlopende resultaten, daarom werd in deze thesis ook de invloed van deze
aggregator bepaald aan de hand van drie veelgebruikte t-normen (zie tabel 5.3).
De in [48] voorgestelde Yagger operator combineert de gemiddelde en de slechtste waarde van de
vier metrieken, waarbij de verhouding te regelen is aan de hand van een factor β. Deze aanpak
heeft als voordeel dat er niet enkel gefocust wordt op de slechtste waarde, wat typisch gebeurt
5.4 Invloed van de aggregator bij Fuzzy LQE
84
Naam
Formule i (a,b)
Yagger
β * min(a,b) + (1 - β) * avg(a,b)
Zadeh
min(a,b)
Lukasiewics
max(a + b - 1, 0)
Tabel 5.3: Overzicht van de gebruikte t-normen.
bij aggregatie van lidmaatschapsfuncties. De vaak gebruikte Zadeh operator (zie tabel 5.3) doet
dit wel, waardoor het verschil tussen de andere drie linkeigenschappen niet gebruikt wordt bij de
bepaling van de linkmetriek. Deze techniek is zeer snel en eenvoudig, maar is wellicht te beperkt
om in deze context te gebruiken. De Lukasiewics operator gebruikt geen minimale of gemiddelde
waarde, maar een eenvoudige bewerking. Deze operator bepaalt als het ware het gemiddelde
van de scores boven de 0.5, waarbij geen negatieve getallen kunnen voorkomen. Zo zullen twee
grote waarden resulteren in een grote waarde, maar zullen veel combinaties uiteindelijk een
linkmetriek van 0 opleveren. De Lukasiewics operator focust zich dus op de goede links.
Om de invloed van deze aggregatoren te bestuderen, werd het Fuzzy LQE algoritme uitgebreid
om ondersteuning te bieden voor deze drie t-normen. Als evaluatie werd het standaard scenario
op het iMinds w-iLab.t testbed (zie 2.4) opnieuw uitgevoerd waarbij telkens een andere t-norm
gebruikt werd om de vier linkmetrieken te combineren.
De resultaten in figuur 5.22 tonen dat de Yagger operator inderdaad de beste prestaties behaalt,
zowel inzake aankomstratio als energieverbruik. De Zadeh operator, die enkel met de slechtste
linkmetriek rekening houdt, presteert heel wat minder en is ook het minst stabiel. Verder lijkt
de Lukasiewics operator tussen beide te presteren, enkel het zeer hoge aantal retransmissies valt
op. Het blijkt dat enkele nodes er in slagen om een zeer goed pad naar de sink te vinden zodat
bijna alle verzonden pakketten ook effectief aankomen. Andere nodes slagen hier niet in en zo
goed als al hun pakketten gaan verloren na 5 retransmissies.
We concluderen dat de Yagger operator het best presteert, waaruit blijkt dat een combinatie van
de gemiddelde en slechtste waarde een goede strategie is om meerdere linkwaarden te aggregeren.
5.5 Invloed van het aantal retransmissies
85
1 2.5 Gemiddelde radio-­‐on -jd (in %) Packet Delivery Ra/o (in %) 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 2 1.5 1 0.5 0 0 yagger zadeh yagger lukasiewics (a) Packet Delivery Ratio
1.2 RPL overhead (DIO berichten per node per minuut) Aantal ouderwissels (per node per minuut) lukasiewics (b) Gemiddelde radio-on tijd (%)
0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 1 0.8 0.6 0.4 0.2 0 yagger zadeh 0 lukasiewics yagger (c) Aantal ouderwissels per node
zadeh lukasiewics (d) Aantal verstuurde DIO berichten
3 3 2.5 Aantal CSMA retransmissies (per verzonden pakket) Gemiddeld aantal hops zadeh 2.5 2 2 1.5 1.5 1 0.5 1 0.5 0 yagger zadeh lukasiewics (e) Gemiddeld aantal hops
0 yagger zadeh lukasiewics (f) Aantal retransmissies
Figuur 5.22: Resultaten van verschillende aggregatoren bij Fuzzy LQE.
5.5
Invloed van het aantal retransmissies
In ContikiRPL kan het maximaal aantal retransmissies alvorens een pakket verloren gaat worden
ingesteld. Met een standaardwaarde van vijf (zie tabel 5.1) zijn er dus maximaal zes verzend-
5.5 Invloed van het aantal retransmissies
86
pogingen mogelijk. Indien we de retransmissies gaan loggen, kan de invloed van het maximaal
aantal onderzocht worden. In figuur 5.23 wordt uitgezet hoeveel pakketten ´e´en, twee, drie,
vier of vijf retransmissies hebben gehad. Dit betekent dat een pakket dat na drie retransmissies succesvol is verzonden wordt geteld bij ´e´en, twee en drie. De gegevens zijn afkomstig uit
´e´en volledige simulatie op het iMinds w-iLab.t testbed, waarbij elk scenario met elk mogelijk
link-inschattingsalgoritme gesimuleerd werd (zie tabel 5.2).
40000 Frequen'e 35000 32375 30000 25000 23719 20466 20000 19490 18739 15000 1 2 3 4 5 Aantal retransmissies Figuur 5.23: Frequentie van het aantal retransmissies.
De resultaten tonen aan dat bijna alle pakketten die twee retransmissies hebben gehad, ook drie
of meer retransmissies hebben gehad. De exacte percentages zijn te vinden in tabel 5.4 en tonen
aan dat bijna 90 procent van de pakketen die al twee retransmissies hebben gehad ook drie of
meer retransmissies hebben gehad. Hieruit kunnen we besluiten dat het verhogen of verlagen van
het maximaal aantal retransmissies weinig invloed zal hebben op de aankomstratio, daar er maar
weinig pakketten zijn die na twee of meer retransmissies toch succesvol verzonden raken. Een
minimum van twee of drie retransmissies is te verantwoorden, maar een hoger aantal zal meer
en meer tot een hoger energieverbruik leiden en zal weinig invloed hebben op de ontvangstratio.
5.5 Invloed van het aantal retransmissies
87
Aantal retransmissies
% van vorige
1
100 %
2
73.26 %
3
86.29 %
4
95.23 %
5
96.15 %
Tabel 5.4: Percentage van de pakketen die n retransmissies nodig hadden, die ook n+1 retransmissies nodig hadden.
CONCLUSIE EN FUTURE WORK
88
Hoofdstuk 6
Conclusie en future work
In dit laatste hoofdstuk worden de conclusies van deze thesis besproken en worden er enkele tips
voor verder onderzoek voorgesteld.
6.1
Conclusie
In deze thesis werden de twee link-inschattingsalgoritmen uit ContikiRPL uitgebreid met vier
alternatieve kwaliteitsschatters. Naast een algoritme die het aantal hops richting sink minimaliseert en een algoritme op basis van het verwacht aantal verzendpogingen (Estimated Transmission Count (ETX)) werden ook twee algoritmen gebaseerd op RSSI- en LQI-waarden en twee
complexere algoritmen die het Four bit en Fuzzy LQE algoritme als basis gebruiken toegevoegd.
Uiteindelijk zijn deze algoritmen uitgebreid getest in de Cooja simulator en op het iMinds wiLab.t testbed. Daarnaast zijn ze ge¨evalueerd op basis van diverse metrieken zoals aankomstratio,
energieverbruik en RPL-overhead. De link-inschatters werden zowel op de simulator als op het
real-life testbed onderworpen aan een zestal scenario’s: een scenario met een dicht- en dunbezet
netwerk, een scenario met veel interferentie, met asymmetrie, een scenario met mobiele nodes
en een scenario met een bursty verzendgedrag.
Uit de resultaten kunnen we besluiten dat er geen algoritme bestaat dat in alle scenario’s het
best presteert. Een hoge aankomstratio gaat veelal gepaard met een hoger energieverbruik,
waardoor een evenwicht tussen beide moet gevonden worden.
We kunnen wel besluiten dat kleine en dunbezette netwerken niet kunnen profiteren van de
extra complexiteit en RPL-overhead van de uitgebreidere algoritmen. In deze gevallen haalt een
6.1 Conclusie
89
eenvoudig algoritme op basis van het aantal hops of op basis van hardwaregebaseerde metrieken
zoals de RSSI- en LQI-waarde gelijkaardige prestaties. De resultaten van het RSSI-gebaseerde
algoritme tonen wel dat de parameters van dit algoritme goed moeten afgesteld worden alvorens
een stabiel netwerk met goede prestaties behaald kan worden. Deze parameters lijken sterk
afhankelijk van de omgeving en het aanwezig interferentieniveau op het testbed. Aangezien
de robuustheid van een algoritme ook als kwaliteitsnorm kan gezien worden, vormt dit een
aanzienlijk nadeel van het RSSI-algoritme.
De verschillende scenario’s waarbij veel interferentie wordt gesimuleerd resulteren niet in een
´e´enduidig resultaat. Het verschil tussen de interne interferentie in de simulator en de externe
interferentie op het testbed kan hiervan een mogelijke oorzaak zijn. Het is ook mogelijk dat het
Four bit algoritme in de Cooja simulator minder presteert wegens de beperkte informatie inzake
RSSI- en LQI-waarden die worden aangeleverd in de simulator. Als laatste kan ook de mate van
interferentie de oorzaak zijn, daar deze op het testbed onmogelijk te controleren valt.
Verder lijkt het een goed idee om pakketten, indien mogelijk, op te sparen en uiteindelijk als
burst te gaan verzenden. Dit leidt volgens het bursty scenario op het iMinds w-iLab.t testbed
tot een hogere aankomstratio en lager energieverbruik.
Over de volledige lijn kunnen we besluiten dat algoritmen die informatie uit verschillende netwerklagen gaan combineren, zoals Fuzzy LQE en Four bit, het best presteren. Deze gaan weliswaar vaak gepaard met een iets grotere RPL-overhead en hoger energieverbruik, maar zijn wel
in staat om asymmetrische links te detecteren en brengen ook pakketten die niet aankomen in
rekening bij het bepalen van de linkkwaliteit.
De vele verschillen in de resultaten van de Cooja simulator en het iMinds w-iLab.t testbed
wijzen erop dat de simulator een degelijke tool is om op een eenvoudige wijze de werking en
de correctheid van algoritmen te testen, maar dat deze software niet in staat is om realistische
scenario’s te simuleren en betrouwbare resultaten af te leveren. Ook moet er rekening gehouden
worden met het feit dat een simulatie op het iMinds w-iLab.t altijd enige vorm van asymmetrie
en externe interferentie ondervindt, wat in de simulator niet het geval is. Het onderzoek toont
ook aan dat het testbed heel wat meer variantie in de resultaten vertoont dan de Cooja simulator.
Het vari¨eren van de RDC- en MAC-protocollen toont aan dat de keuze voor een bepaald MACprotocol weinig tot geen invloed heeft op de prestatieverschillen tussen de inschattingsalgoritmen
onderling. Het protocol heeft eerder een algemene impact op de aankomstratio en het energieverbruik, waardoor we de algemene conclusies van ContikiMAC kunnen doortrekken.
6.2 Future work
90
Scenario
Beste link-inschattingsalgoritme
Standaard
Fuzzy LQE
Sparse
Ojectieffunctie 0
Dense
Fuzzy LQE of ETX
Asymmetrisch
Four bit of Fuzzy LQE
Interferentie
Fuzzy LQE
Bursty
Fuzzy LQE
Mobiliteit
ETX of Objectieffunctie 0
Tabel 6.1: Overzicht van de conclusies van dit onderzoek.
Om alle conclusies samen te vatten, zijn in tabel 6.1 enkele algemene adviezen te vinden die
kunnen gebruikt worden bij de selectie van het meeste geschikte link-inschattingsalgoritme.
Indien we ons op deze tabel gaan baseren, lijkt de combinatie van het objectieffunctie 0 en het
Fuzzy LQE algoritme voldoende te zijn om in elk van de in deze thesis bestudeerde scenario’s
goede resultaten te bekomen.
6.2
Future work
Deze thesis vormt een ideale aanloop naar verder onderzoek omtrent link-estimatie in dynamische
sensornetwerken. Via dit onderzoek krijgt de lezer een overzicht van een aantal belangrijke
technieken om aan link-inschatting te doen en wordt het eenvoudiger om voor een bepaald
netwerk de meest geschikte link-estimator te bekomen.
Wegens beperkte tijd geeft dit onderzoek geen degelijke studie van de invloed van alle mogelijke
parameters in de betrokken algoritmen. Zo kunnen we bij de algoritmen op basis van RSSI,
LQI en ETX gaan spelen met verschillende mappings voor het bepalen van de linkmetriek.
Verder kan het aanpassen van de grenswaarden in het Four bit algoritme en de verschillende
lidmaatschapsfuncties in het Fuzzy LQE algoritme heel andere resultaten opleveren.
Een ideaal algoritme is zelf in staat om de netwerkkarakteristieken te bepalen en zijn parameters
op een zelf-lerende manier in te stellen. Zo kan deze estimator in alle types netwerken gebruikt
worden en mag het netwerk dynamisch gaan wijzigen, de estimator past zich na verloop van tijd
zelf aan naar een nieuwe configuratie die optimaal is voor het netwerk.
Verder spitst dit onderzoek zich toe op scenario’s waarbij telkens heel het netwerk dezelfde
6.2 Future work
91
karakteristieken bevat. Realistische sensornetwerken bestaan vaak uit combinaties van de in deze
thesis onderzochte scenario’s. Hierdoor kan verder onderzoek zich toespitsen op de mogelijkheid
om meerdere link-inschattingsalgoritmen te gaan combineren in ´e´en netwerk.
Het idee van de complexere algoritmen, waarbij informatiebronnen uit verschillende netwerklagen worden gecombineerd, kan nog worden uitgebreid door het combineren van verschillende
link-inschattingsalgoritmen. Het ontwikkelen van een meta link-inschatter, die meerdere technieken van kwaliteitsinschatting combineert en deze geaggregeerde waarde gebruikt, kan de vooren nadelen van bepaalde estimators op een intelligente manier gebruiken.
OVERZICHT VAN DE RESULTATEN
92
Bijlage A
Overzicht van de resultaten
In deze bijlage worden enkele grafieken getoond die alle resultaten uit de Cooja simulator en het
iMinds w-iLab.t testbed samenvatten.
A.1
Cooja simulator
Packet Delivery Ra/o (in %) 1 0.9 0.8 0.7 OF0 0.6 LQI 0.5 RSSI 0.4 ETX 0.3 4B 0.2 FUZZY 0.1 0 standard sparse dense asymmetric interference mobility bursty Figuur A.1: Overzicht van de packet delivery ratio (in %) van alle link-inschattingsalgoritmen
in de Cooja simulator.
A.1 Cooja simulator
93
Gemiddelde radio-­‐aan -jd (in %) 6 5 OF0 4 LQI RSSI 3 ETX 2 4B FUZZY 1 0 standard Figuur A.2:
sparse dense asymmetric interference mobility bursty Overzicht van de gemiddelde radio-aan tijd (in %) van alle link-
inschattingsalgoritmen in de Cooja simulator.
Aantal ouderwissels (per node per minuut) 1.6 1.4 1.2 OF0 1 LQI RSSI 0.8 ETX 0.6 4B 0.4 FUZZY 0.2 0 standard Figuur A.3:
sparse dense asymmetric interference mobility bursty Overzicht van het aantal ouderwissels per node per minuut van alle link-
inschattingsalgoritmen in de Cooja simulator.
A.1 Cooja simulator
94
RPL overhead (DIO-­‐berichten per node per minuut) 6 5 OF0 4 LQI 3 RSSI ETX 2 4B FUZZY 1 0 standard sparse dense asymmetric interference mobility bursty Figuur A.4: Overzicht van het aantal verstuurde DIO-berichten per node per minuut van alle
link-inschattingsalgoritmen in de Cooja simulator.
Gemiddeld aantal hops 7 6 OF0 5 LQI 4 RSSI 3 ETX 2 4B FUZZY 1 0 standard sparse dense asymmetric interference mobility bursty Figuur A.5: Overzicht van het gemiddeld aantal hops van alle link-inschattingsalgoritmen in de
Cooja simulator.
A.2 iMinds w-iLab.t testbed
95
Aantal CSMA retransmissies (per verzonden pakket) 6 5 OF0 4 LQI 3 RSSI ETX 2 4B FUZZY 1 0 standard sparse dense asymmetric interference mobility bursty Figuur A.6: Overzicht van het aantal CSMA retransmissies per verzonden pakket van alle linkinschattingsalgoritmen in de Cooja simulator.
A.2
iMinds w-iLab.t testbed
Packet Delivery Ra/o (in %) 1 0.9 0.8 0.7 OF0 0.6 LQI 0.5 RSSI 0.4 ETX 0.3 4B 0.2 FUZZY 0.1 0 standard sparse dense asymmetric interference bursty Figuur A.7: Overzicht van de packet delivery ratio (in %) van alle link-inschattingsalgoritmen
op het iMinds w-iLab.t testbed.
A.2 iMinds w-iLab.t testbed
96
Gemiddelde radio-­‐aan -jd (in %) 4 3.5 3 OF0 2.5 LQI 2 RSSI 1.5 ETX 4B 1 FUZZY 0.5 0 standard Figuur A.8:
sparse dense asymmetric interference bursty Overzicht van de gemiddelde radio-aan tijd (in %) van alle link-
inschattingsalgoritmen op het iMinds w-iLab.t testbed.
Aantal ouderwissels (per node per minuut) 1.4 1.2 OF0 1 LQI 0.8 RSSI 0.6 ETX 4B 0.4 FUZZY 0.2 0 standard Figuur A.9:
sparse dense asymmetric interference bursty Overzicht van het aantal ouderwissels per node per minuut van alle link-
inschattingsalgoritmen op het iMinds w-iLab.t testbed.
A.2 iMinds w-iLab.t testbed
97
RPL overhead (DIO-­‐berichten per node per minuut) 2.5 2 OF0 LQI 1.5 RSSI 1 ETX 4B 0.5 FUZZY 0 standard sparse dense asymmetric interference bursty Figuur A.10: Overzicht van het aantal verstuurde DIO-berichten per node per minuut van alle
link-inschattingsalgoritmen op het iMinds w-iLab.t testbed.
Gemiddeld aantal hops 4 3.5 3 OF0 2.5 LQI RSSI 2 ETX 1.5 4B 1 FUZZY 0.5 0 standard sparse dense asymmetric interference bursty Figuur A.11: Overzicht van het gemiddeld aantal hops van alle link-inschattingsalgoritmen op
het iMinds w-iLab.t testbed.
A.2 iMinds w-iLab.t testbed
98
Aantal CSMA retransmissies (per verzonden pakket) 5 4.5 4 3.5 OF0 3 LQI 2.5 RSSI 2 ETX 1.5 4B 1 FUZZY 0.5 0 standard sparse dense asymmetric interference bursty Figuur A.12: Overzicht van het aantal CSMA retransmissies per verzonden pakket van alle
link-inschattingsalgoritmen op het iMinds w-iLab.t testbed.
BIBLIOGRAFIE
99
Bibliografie
[1] Dave Evans.
The Internet of Things:
How the Next Evolution of the Internet Is
Changing Everything. http://www.cisco.com/web/about/ac79/docs/innov/IoT_IBSG_
0411FINAL.pdf, 2001. Online, laatst bezocht op 12-Mei-2014.
[2] Afbeelding van een Tmote Sky sensornode. http://www.btnode.ethz.ch/pub/uploads/
Projects/tmote_sky.jpg. Online, laatst bezocht op 12-Mei-2014.
[3] iMinds GreenWeCan project.
http://www.iminds.be/en/projects/2014/03/04/
greenwecan. Online, laatst bezocht op 12-Mei-2014.
[4] Firebug project: forest fire detection. http://firebug.sourceforge.net. Online, laatst
bezocht op 12-Mei-2014.
[5] Valcan project (Harvard University): monitoren van een vulkaan. http://fiji.eecs.
harvard.edu/Volcano. Online, laatst bezocht op 12-Mei-2014.
[6] Afbeelding
van
het
monitoren
van
parkeerplaatsen.
traffictechnologytoday.com/news.php?NewsID=30424.
http://www.
Online, laatst bezocht op
12-Mei-2014.
[7] C. Garcia-Hernandez, P. Ibarguengoytia, J. Garcia-Hernandez, and J. Perez-Diaz. Multihop
Routing for Energy Efciency in Wireless Sensor Networks, Mar 2007.
[8] Jatuporn Chinrungrueng, Udomporn Sunantachaikul, and Satien Triamlumlerd. Smart Parking: An Application of Optical Wireless Sensor Network. In SAINT Workshops, page 66.
IEEE Computer Society, 2007.
[9] M. Presser, P. Barnaghi, M. Eurich, and C. Villalonga. The SENSEI project: integrating
the physical world with the digital world of the network of the future. Communications
Magazine, IEEE, 47, April 2009.
BIBLIOGRAFIE
100
[10] M. Qin Wang, Hempstead, and W. Yang. A Realistic Power Consumption Model for
Wireless Sensor Network Devices. Sensor and Ad Hoc Communications and Networks,
pages 286–295, April 2006.
[11] Tmote Sky Datasheet.
http://www.eecs.harvard.edu/~konrad/projects/shimmer/
references/tmote-sky-datasheet.pdf. Online, laatst bezocht op 12-Mei-2014.
[12] Contiki website. http://www.contiki-os.org/. Online, laatst bezocht op 12-Mei-2014.
[13] Pei Huang, Li Xiao, Matt W. Mutka, and Ning Xi. The Evolution of MAC Protocols in
Wireless Sensor Networks: A Survey. IEEE Communication surveys and tutorials, 15, 2013.
[14] Afbeelding van multihop routering. http://en.wikipedia.org/wiki/Wireless_sensor_
network. Online, laatst bezocht op 12-Mei-2014.
[15] Elias Yaacoub and Adnan Abu-Dayya. Multihop Routing In Self-Organizing Wireless Sensor
Networks. InTech, 2012.
[16] Afbeelding van hierarchische routering. http://www.my-smc.org/news/back/2010_12/
main_article3.html. Online, laatst bezocht op 12-Mei-2014.
[17] Afbeelding
van
geografische
routering.
http://www.linuxonly.nl/docs/1/74_
Geographical_routing_protocols.html. Online, laatst bezocht op 12-Mei-2014.
[18] Marjan Radi, Behnam Dezfouli, Kamalrulnizam Abu Bakar, and Malrey Lee. Multipath
Routing in Wireless Sensor Networks: Survey and Research Challenges. Sensors, 12(1):650–
685, 2012.
[19] Kemal Akkaya and Mohamed Younis. A survey on routing protocols for wireless sensor
networks. Ad Hoc Networks, 3:325–349, 2005.
[20] Afbeelding van boomgebaseerde routering. http://www.hindawi.com/journals/ijdsn/
2013/794326/fig2/. Online, laatst bezocht op 12-Mei-2014.
[21] T. Winter, P. Thubert, A. Brandt, J. Hui, R. Kelsey, P. Levis, K. Pister, R. Struik, J. Vasseur, and R. Alexander. RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks.
RFC 6550 (Proposed Standard), March 2012.
[22] P. Levis, T. Clausen, J. Hui, O. Gnawali, and J. Ko. The Trickle Algorithm. RFC 6206
(Proposed Standard), March 2011.
BIBLIOGRAFIE
101
[23] Niels Derdaele. Performatie van RPL met meerdere sinks in draadloze sensornetwerken.
Master’s thesis, Ghent University, Belgium, 2013.
[24] Tsvetko Tsvetkov. RPL: IPv6 Routing Protocol for Low Power and Lossy Networks, 2011.
[25] T. Clausen, U. Herberg, and M. Philipp. A critical evaluation of the IPv6 Routing Protocol
for Low Power and Lossy Networks (RPL). In Wireless and Mobile Computing, Networking
and Communications (WiMob), 2011 IEEE 7th International Conference on, pages 365–
372, Oct 2011.
[26] Philip Levis, Sam Madden, Joseph Polastre, Robert Szewczyk, Alec Woo, David Gay, Jason
Hill, Matt Welsh, Eric Brewer, and David Culler. TinyOS: An operating system for sensor
networks. In in Ambient Intelligence. Springer Verlag, 2004.
[27] Adam Dunkels, Thiemo Voigt, and B. Gronvall. Contiki - a lightweight and flexible operating system for tiny networked sensors. Local Computer Networks, 38:455–462, 2004.
[28] Chen Yibo, Kun mean Hou, Haiying Zhou, Hong-Ling Shi, Xing Liu, Xunxing Diao, Hao
Ding, Jian-Jin Li, and C. de Vaulx. 6lowpan stacks: A survey. In Wireless Communications,
Networking and Mobile Computing (WiCOM), 2011 7th International Conference on, pages
1–4, Sept 2011.
[29] Nicolas Tsiftes, Joakim Eriksson, and Adam Dunkels. Low-power wireless IPv6 routing
with ContikiRPL. In Tarek F. Abdelzaher, Thiemo Voigt, and Adam Wolisz, editors,
IPSN, pages 406–407. ACM, 2010.
[30] Christian Lerche, Klaus Hartke, and Matthias Kovatsch. Industry Adoption of the Internet
of Things: A Constrained Application Protocol Survey. In Proceedings of the 7th International Workshop on Service Oriented Architectures in Converging Networked Environments
(SOCNE 2012), Krak´
ow, Poland, September 2012.
[31] ProtoThreads. http://dunkels.com/adam/pt. Online, laatst bezocht op 12-Mei-2014.
[32] Muhammad Omer Farooq and Thomas Kunz. Operating Systems for Wireless Sensor
Networks: A Survey. Sensors, 11(6):5900–5930, 2011.
[33] F. Osterlind, A. Dunkels, J. Eriksson, N. Finne, and T. Voigt. Cross-Level Sensor Network Simulation with COOJA. In Local Computer Networks, Proceedings 2006 31st IEEE
Conference on, pages 641–648, Nov 2006.
BIBLIOGRAFIE
[34] Anuj
Sehgal.
102
Using
the
Contiki
Cooja
Simulator.
jacobs-university.de/courses/iotlab-2013/cooja.pdf, 2013.
http://cnds.eecs.
Online, laatst be-
zocht op 12-Mei-2014.
[35] Cooja simulator. http://www.contiki-os.org/start.html#simulation. Online, laatst
bezocht op 12-Mei-2014.
[36] Adam Dunkels.
The ContikiMAC Radio Duty Cycling Protocol.
http://soda.
swedish-ict.se/5128/1/contikimac-report.pdf, 2011. Online, laatst bezocht op 12Mei-2014.
[37] Michael Buettner, Gary V. Yee, Eric Anderson, and Richard Han. X-MAC: A Short Preamble MAC Protocol for Duty-cycled Wireless Sensor Networks. In Proceedings of the
4th International Conference on Embedded Networked Sensor Systems, SenSys ’06, pages
307–320, New York, NY, USA, 2006. ACM.
[38] Website iMinds. http://www.iminds.be. Online, laatst bezocht op 12-Mei-2014.
[39] Stefan Bouckaert, Wim Vandenberghe, Bart Jooris, Ingrid Moerman, and Piet Demeester.
The w-iLab.t Testbed. LNICST 46, pages 145–154, 2011.
[40] Website iMinds w-iLab.t 2 Zwijnaarde. http://www.wilab2.ilabt.iminds.be/. Online,
laatst bezocht op 12-Mei-2014.
[41] iMinds w-iLab.t website.
http://ilabt.iminds.be/wilabt/hardwarelayout/office/
architecture. Online, laatst bezocht op 12-Mei-2014.
[42] Nouha Baccour, Anis Koubaa, Luca Mottola, Marco Antonio Ziga Zamalloa, Habib Youssef,
Carlo Alberto Boano, and Mrio Alves. Radio link quality estimation in wireless sensor
networks: A survey. TOSN, 8(4):34, 2012.
[43] Dong Yang, Youzhi Xu, and M. Gidlund. Coexistence of IEEE802.15.4 based networks: A
survey. In IECON 2010 - 36th Annual Conference on IEEE Industrial Electronics Society,
pages 2107–2113, Nov 2010.
[44] Niels Reijers, Gertjan Halkes, and Koen Langendoen. Link layer measurements in sensor
networks. In Proc. of the the First IEEE International Conference on Mobile Ad-hoc and
Sensor Systems (MASS 2004), Fort Lauderdale (FL, pages 24–27. Society Press, 2004.
BIBLIOGRAFIE
103
[45] Alec Woo, Terence Tong, and David Culler. Taming the Underlying Challenges of Reliable
Multihop Routing in Sensor Networks. In In SenSys, pages 14–27. ACM Press, 2003.
[46] Octav Chipara. Routing in wireless sensor networks - Slides. http://homepage.divms.
uiowa.edu/~ochipara/classes/wsn/lectures/linkestimation.pdf. Online, laatst bezocht op 12-Mei-2014.
[47] Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis. Four Bit Wireless
Link Estimation . In Proceedings of the Sixth Workshop on Hot Topics in Networks (HotNets
VI), 2007.
[48] Nouha Baccour, Heni Kaaniche, Mohamed Chtourou, and Maher Ben Jemaa. F-LQE:
A Fuzzy Link Quality Estimator for Wireless Sensor Networks. In International MultiConference on Systems, Signals and Devices (SSD 2007), Hammamet, Tunisia, March 2007.
[49] Erich Peter Klement and Mirko Navara. A survey on different triangular norm-based fuzzy
logics. Fuzzy Sets and Systems, 101(2):241 – 251, 1999. Analytical and Structural Considerations in Fuzzy Modeling.
[50] Siegfried Gottwald. Axiomatizations of t-norm based logics - A survey. Soft Comput.,
4(2):63–67, 2000.
[51] Kevin C. Lee, Raghuram Sudhaakar, Jianxia Ning, Lillian Dai, Sateesh Addepalli, Jp Vasseur, and Mario Gerla. A Comprehensive Evaluation of RPL under Mobility.
[52] Hazrat Ali. A Performance Evaluation of RPL in Contiki. Master’s thesis, Swedish Institute
of Computer Science, Sweden, 2012.
[53] Oana Iova, Fabrice Theoleyre, and Thomas Nol. Stability and efficiency of RPL under
realistic conditions in Wireless Sensor Networks. In PIMRC, pages 2098–2102. IEEE, 2013.
[54] Vehbi C. Gungor and Mustafa Kemal Korkmaz. Wireless Link-Quality Estimation in Smart
Grid Environments. IJDSN, 2012, 2012.
[55] Sebastien Dawans, Simon Duquennoy, and Olivier Bonaventure. On link estimation in dense
RPL deployments. In LCN Workshops, pages 952–955. IEEE, 2012.
[56] Tobias Rein. Energy and Time Efficient Link-Quality Estimation for Wireless Sensor Networks. Master’s thesis, Eidgenossische Technische Hochschule Z¨
urich, Switzerland, 2007.
BIBLIOGRAFIE
104
[57] Michele Rondinone, Junaid Ansari, Janne Riihij¨arvi, and Petri M¨ah¨onen. Designing a
Reliable and Stable Link Quality Metric for Wireless Sensor Networks. In Proceedings of
the Workshop on Real-world Wireless Sensor Networks, REALWSN ’08, pages 6–10, New
York, NY, USA, 2008. ACM.
[58] Adam Dunkels, Joakim Eriksson, Niclas Finne, and Nicolas Tsiftes. Powertrace: Networklevel Power Proling for Low-power Wireless Networks, Mar 2011.
[59] Kannan Srinivasan and Philip Levis. RSSI is Under Appreciated. In In Proceedings of the
Third Workshop on Embedded Networked Sensors (EmNets, 2006.