Evaluatie van link-inschattingsalgoritmen voor RPL in dynamische sensornetwerken

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ëren 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ël 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ënt 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ëvalueerd. 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


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.


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ële groei van het aantal met het internet verbonden toestellen. . . . . .

2

1.2

Tmote Sky sensornode.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3

Industriële 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ërarchische 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ële groei van het aantal met het internet verbonden toestellen [1]. Het plaatsen van dergelijke sensornodes heeft heel wat industriële 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ëren van enkele tientallen tot wel duizenden sensoren. Verder kan het aantal sensornodes in het netwerk ook met de tijd variëren: 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ëren in de tijd. Indien een node op elk moment zijn pakketten via het meest efficiënte 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ëvalueerd 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ën (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ëntie en schaalbaarheid. Energie efficiënte MAC protocollen kunnen volgens [13] het eenvoudigst opgedeeld worden in vier categorieën: 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ënt 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ënt 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ënt 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 één 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ënte 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 één 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ënte 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 één 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ën: hiërarchische, geografische, data-centrische en boomgebaseerde routering. Hiërarchische 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ënter te maken. Zo worden pakketten enkel doorgestuurd naar nodes


10

Figuur 2.5: Links: clustering bij hiërarchische 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 één 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


11

boomstructuur ontstaat tussen elke twee nodes exact één 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ële 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


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ële 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.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ële 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ële 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ële 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ële 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


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


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ële 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


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.


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ënte 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ënt 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,


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 éénzelfde 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ën, 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.


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.


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ënte 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ënte 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ëvalueerd 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ën 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 plaatsen tijdsgebonden zijn en kan deze in de praktijk zeer snel variëren. 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ëntie 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


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ënter dan paden die gelijk verdeelde ETX-waarden hebben.


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


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 één kwaliteitsscore die dan als linkmetriek gebruikt kan worden. Een voorbeeldimplementatie in [48] gebruikt de aankomstratio om de kwaliteit van de link te modelleren, de


34

Figuur 3.14: Vaag regelsystem met lingu¨ıstische termen [48]. coëfficiënt 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 één 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ële 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ëvalueerd 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ëren 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ëren 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ëvalueerd, 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ën, 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ën 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ëren (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ëvalueerd 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 %


Cooja RX ratio

65 %

65 %


Degeneratiemodel

UDGM

UDGM

DGRM

Aantal connected

8

Afh. van positie

8

Aantal interferred

20

Afh. van positie


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ëntie, 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 één 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ëert 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ëren 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ële 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 één 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ëfficiënt 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ëfficiënt 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ëfficiënt van variantie van 0 in een perfecte score van 1, waarna de score lineair zakt tot een score van 0 bij een coëfficiënt 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ëfficiënt 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ëfficiënt 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


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


4.5

1

4 3.5 3 2.5

STANDARD

1.5 1 0.5 0

fuzzy

of0


lqi

rssi

etx

4b

fuzzy


0.6 0.5 0.4

SPARSE STANDARD

0.3 0.2 0.1


0.7


SPARSE

2

2 1.5 SPARSE STANDARD

1 0.5 0

0 of0

lqi

rssi

etx

4b

of0

fuzzy


lqi

rssi

etx

4b

fuzzy

(d) Aantal verstuurde DIO berichten


6 5 4

SPARSE STANDARD

3 2


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


of0

lqi

rssi

etx

4b

fuzzy


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


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



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


1.4 1.2 1 DENSE

0.8

STANDARD

0.6 0.4 0.2


1.6

2

1.5 DENSE

0.5

0 of0

lqi

rssi

etx

4b

STANDARD

1

0

fuzzy

of0


lqi

rssi

etx

4b

fuzzy



6 5 4

DENSE STANDARD

3 2


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


of0

lqi

rssi

etx

4b

fuzzy


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



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


lqi

rssi

etx

4b

fuzzy


6 5 4

ASYMMETRIC STANDARD

3 2 1


7


rssi





lqi

3 2.5 2

ASYMMETRIC STANDARD

1.5 1 0.5 0

0 of0

lqi

rssi

etx

4b

fuzzy


of0

lqi

rssi

etx

4b

fuzzy


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.


0.8 0.7 0.6 INTERFERENCE

0.5

STANDARD

0.4 0.3 0.2 0.1 0 of0

lqi

rssi

etx

4b


6

1 0.9

5 4

STANDARD

2 1 0

fuzzy

of0


lqi

rssi

etx

4b

fuzzy

(b) Gemiddelde radio-on tijd (%) 3


1.2


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


lqi

rssi

etx

4b

fuzzy



6 5 4

INTERFERENCE STANDARD

3 2


2.5 7

2 1.5 INTERFERENCE STANDARD

1 0.5

1

0

0 of0

lqi

rssi

etx

4b

fuzzy


of0

lqi

rssi

etx

4b

fuzzy


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




1 0.9

4 3.5 3 2.5

BURSTY STANDARD

2 1.5 1 0.5 0 of0

lqi

rssi

etx

4b

fuzzy


Figuur 5.9: Resultaten van het standaard en bursty scenario in de Cooja simulator.

5.1 Cooja simulator

69

3


0.7 0.6 0.5 BURSTY

0.4

STANDARD

0.3 0.2 0.1


0.8

0 of0

lqi

rssi

etx

4b

2 BURSTY

1.5

STANDARD

1 0.5 0

fuzzy

of0


lqi

rssi

etx

4b

fuzzy


6 5 4

BURSTY STANDARD

3 2 1


7


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


of0

lqi

rssi

etx

4b

fuzzy


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



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


etx

4b

fuzzy

7


0.7


rssi


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


of0

lqi

rssi

etx

4b

fuzzy

(d) Aantal verstuurde DIO berichten 7


6


lqi

5 4 3 2 1

6 5 4 3 2 1 0

0 of0

lqi

rssi

etx

4b

fuzzy


of0

lqi

rssi

etx

4b

fuzzy


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


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ëren. 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.


72

2.5



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


lqi

rssi

etx

4b

fuzzy



3


rssi





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


of0

lqi

rssi

etx

4b

fuzzy


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-


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.


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


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


0.1 0.05



SPARSE

1.2 1 SPARSE

0.8

STANDARD

0.6 0.4 0.2 0

0 of0

lqi

rssi

etx

4b

of0

fuzzy


lqi

rssi

etx

4b

fuzzy



2.5 2 SPARSE

1.5

STANDARD

1 0.5


4

3

3.5 3 2.5 SPARSE

2

STANDARD

1.5 1 0.5 0

0 of0

lqi

rssi

etx

4b

fuzzy


of0

lqi

rssi

etx

4b

fuzzy


Figuur 5.13: Resultaten van het standaard en sparse scenario op het 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.


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



4

1

3.5 3 2.5 DENSE

2

STANDARD

1.5 1 0.5 0 of0

lqi

rssi

etx

4b

fuzzy


Figuur 5.14: Resultaten van het standaard en dense scenario op het testbed.


75


1.2 1


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


lqi

rssi

etx

4b

fuzzy



3.5 3 2.5 DENSE

2

STANDARD

1.5 1


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


of0

lqi

rssi

etx

4b

fuzzy


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 één 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.


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



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


STANDARD

0.15 0.1 0.05



STANDARD

1


1.2 1 ASYMMETRIC

0.8

STANDARD

0.6 0.4 0.2 0

0 of0

lqi

rssi

etx

4b

of0

fuzzy


lqi

rssi

etx

4b

fuzzy


3.5 3 2.5 ASYMMETRIC

2

STANDARD

1.5 1 0.5


4


ASYMMETRIC

1.5

5 4 ASYMMETRIC

3

STANDARD

2 1 0

0 of0

lqi

rssi

etx

4b

fuzzy


of0

lqi

rssi

etx

4b

fuzzy


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


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.


78

4

0.8 0.7 0.6 INTERFERENCE

0.5

STANDARD

0.4 0.3 0.2 0.1



1 0.9

3.5 3 2.5

lqi

rssi

etx

4b

1 0.5 0

fuzzy

of0


rssi

etx

4b

fuzzy

2.5

1 0.8



lqi


1.2

2

1.5

INTERFERENCE

0.6

STANDARD

0.4


1

0.5

0.2 0 of0

lqi

rssi

etx

4b

0

fuzzy

of0


lqi

rssi

etx

4b

fuzzy


3 2.5 2


1.5 1


3.5


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


of0

lqi

rssi

etx

4b

fuzzy


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


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



1 0.9

2.5 2

0.5 0

fuzzy

of0

lqi

rssi

etx

4b

fuzzy


0.5 0.4 BURSTY

0.3

STANDARD

0.2 0.1


0.6


STANDARD

1


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


4

4

2

lqi

rssi

etx

4b

fuzzy


4.5

2.5

BURSTY

0.8

0

fuzzy



BURSTY

1.5

3 2.5 BURSTY

2

STANDARD

1.5 1 0.5 0

0 of0

lqi

rssi

etx

4b

fuzzy


of0

lqi

rssi

etx

4b

fuzzy


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.


81


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



4.5

1

4 3.5 3 2.5

NULLMAC STANDARD

2 1.5 1 0.5 0 of0

lqi

rssi

etx

4b

fuzzy


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.


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



1 0.9

18 16 14 Con8kiMAC

12

NullRDC

10

X-‐MAC

8

CX-‐MAC

6 4 2 0


of0

lqi

rssi

etx

4b

fuzzy


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


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


fuzzy


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


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 %)


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


1.2

RPL overhead (DIO berichten per node per minuut)


lukasiewics


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


zadeh

lukasiewics


3

2.5



zadeh

2.5 2

2

1.5

1.5 1 0.5

1

0.5

0 yagger

zadeh

lukasiewics


0 yagger

zadeh

lukasiewics


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-


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 één, twee, drie, vier of vijf retransmissies hebben gehad. Dit betekent dat een pakket dat na drie retransmissies succesvol is verzonden wordt geteld bij één, twee en drie. De gegevens zijn afkomstig uit één 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.


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ëvalueerd 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 éénduidig 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ëren 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 één 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


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


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.


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


bursty

Overzicht van het aantal ouderwissels per node per minuut van alle link-

inschattingsalgoritmen in de Cooja simulator.

A.1 Cooja simulator

94


6 5 OF0

4

LQI 3

RSSI ETX

2

4B FUZZY

1 0 standard

sparse

dense


bursty

Figuur A.4: Overzicht van het aantal verstuurde DIO-berichten per node per minuut van alle link-inschattingsalgoritmen in de Cooja simulator.


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


6 5 OF0

4

LQI

3

RSSI ETX

2

4B FUZZY

1 0 standard

sparse

dense


bursty

Figuur A.6: Overzicht van het aantal CSMA retransmissies per verzonden pakket van alle linkinschattingsalgoritmen in de Cooja simulator.

A.2



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.


96


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.


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.


97


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.


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.


98


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ärvi, and Petri Mähönen. 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.

Evaluatie van link-inschattingsalgoritmen voor RPL in dynamische sensornetwerken

Recommend Documents