Ontwikkeling van zelf-lerende sensornetwerken door middel van artificiële intelligentie

Faculteit Ingenieurswetenschappen en architectuur Vakgroep Informatietechnologie Voorzitter: Prof. dr. ir. D. DE ZUTTER

Ontwikkeling van zelf-lerende sensornetwerken door middel van artifici¨ ele intelligentie door Gustav JANSSENS

Promotoren: Prof. dr. ir. I. MOERMAN, dr. ir. E. DE POORTER Scriptiebegeleider: M. ROVCANIN

Scriptie ingediend tot het behalen van de academische graad van Master of Science in de ingenieurswetenschappen: elektrotechniek: informatie- en communicatietechnologie Academiejaar 2012–2013

Voorwoord Draadloze sensornetwerken bestaan uit een netwerk van autonome sensornodes, die verschillende metingen kunnen uitvoeren, en de data op een co¨operatieve manier kunnen doorsturen naar een centraal punt; de sink. Deze netwerken zijn een zeer recente topic van onderzoek, met vele interessante mogelijkheden. Eerst werd deze technologie actief gesponsord voor militaire doeleinden, hoofdzakelijk verkenning en bewaking. Heden ten dage worden deze netwerken ook gebruikt in vele commerci¨ele en industri¨ele toepassingen, zoals het monitoren van natuurgebieden (voorkomen van bosbranden e.d.), het opvolgen van pati¨enten, controle van luchtkwaliteit, monitoren van voorraad, . . . Deze veelvoud van mogelijke toepassingen maakt het een zeer interessant en actief onderzoeksgebied. Het was dan ook zeer interessant voor mij om mijn scriptie over dit onderzoeksdomein te kunnen schrijven. Ik hoop dat ik met dit werk mijn steentje heb kunnen bijdragen aan het dichterbij brengen van goedkopere en beter functionerende sensornetwerken. Ik wil dan ook mijn promotor, dr. ir. Eli De Poorter bedanken voor de intense begeleiding, en de persoonlijke opvolging van de uiteindelijke invulling en implementatie van de thesis. Ook zou ik graag Prof. dr. ir. Ingrid Moerman bedanken voor het voorstellen van dit onderwerp, en de initi¨ele begeleiding. Verder zou ik graag Milos Rovcanin bedanken voor de samenwerking en het gebruik van een deel van zijn software. Zonder hem zou de implementatie nog een heel stuk verder af staan. Verder wil ik ook nog de vele mensen bedanken die de tijd namen om mijn scriptie na te lezen; Kaat, Mathias, pa en ma, bedankt voor jullie geduld en tijd! Verder wil ik nog specifiek mijn ouders bedanken, om mij alle mogelijkheden te geven die mij de persoon gemaakt hebben die ik nu ben. Ten slotte wil ik nog de mensen bedanken die hier niet specifiek vermeld zijn, maar die mij toch op de een of andere manier gesteund hebben. Bedankt.

Gustav Janssens, juni 2013

Toelating tot bruikleen “De auteur geeft de toelating deze scriptie voor consultatie beschikbaar te stellen en delen van de scriptie te kopi¨eren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze scriptie.”

Gustav Janssens, juni 2013

Ontwikkeling van zelf-lerende sensornetwerken door middel van artifici¨ ele intelligentie door Gustav JANSSENS Scriptie ingediend tot het behalen van de academische graad van Master of Science in de ingenieurswetenschappen: elektrotechniek: informatie- en communicatietechnologie Academiejaar 2012–2013 Promotoren: Prof. dr. ir. I. MOERMAN, dr. ir. E. DE POORTER Scriptiebegeleider: M. ROVCANIN Faculteit Ingenieurswetenschappen en architectuur Universiteit Gent Vakgroep Informatietechnologie Voorzitter: Prof. dr. ir. D. DE ZUTTER

Samenvatting In dit werk proberen we de kostprijs van het opzetten en onderhouden van sensornetwerken te verminderen door het netwerk zelf-lerend te maken. Hiertoe implementeren we een zelf-lerend algoritme m.b.v. reinforcement learning en LSPI, dat parameters optimaliseert van bestaande MAC– en routeringsprotocollen. Vervolgens wordt dit getest in softwaresimulaties met motes die het Contiki besturingssysteem draaien.

Trefwoorden Sensornetwerk, artifici¨ele intelligentie, reinforcement learning, LSPI, Contiki, ContikiMAC, RPL

Lijst van afkortingen

MAC

Media Access and Control

IP

Internet Protocol

6LoWPAN

IPv6 over Low power Wireless Personal Area Networks

OS

Operating System

UDGM

Unit Disk Graph Medium

RPL

“Ripple” Routing Protocol

CoAP

Constrained Application Protocol

CCA

Clear Channel Assessment

RDC

Radio Duty Cycle

LLN

Low power and Lossy Network

ROLL

Routing over Low power and Lossy [networks]

DODAG

Destination Oriented Directed Acyclic Graph

DAG

Directed Acyclic Graph

ETX

Expected Transmission Count

URI

Uniform Resource Identifier

RL–LSPI

Reinforcement Learning – Least Squares Policy Iteration

TCP

Transmission Control Protocol

UDP

User Datagram Protocol

Cf

Californium

Er

Erbium

SLIP

Serial Line Interface Protocol

XML

Extensible Markup Language

Development of self-learning wireless sensor networks using artificial intelligence Gustav Janssens Supervisor(s): Ingrid Moerman, Eli De Poorter, Milos Rovcanin Abstract— This article tries to reduce the price of setting up and maintaining sensor networks by implementing a self-learning algorithm. Parameters of existing MAC– and routing protocols are optimised using Reinforcement Learning and LSPI. This is tested in software simulation, using Cooja and the Contiki OS. Keywords— Sensor network, artificial intelligence, reinforcement learning, LSPI, Contiki, ContikiMAC, RPL

I. I NTRODUCTION HE cost of setting up and maintaining wireless sensor networks is currently very high, due to the high amount of manual design and maintenance that is required. This article presents a method to allow the network to tune specific parameters in existing network protocols, thus decreasing the amount of manual work that needs to be done. This also allows the network to adapt to a changing environment, without manually reconfiguring the parameters. In this abstract, we will present a Negotiation Engine, which uses Reinforcement Learning and LSPI[1] to optimise 2 parameters, each having 2 discrete values. We will then test this in Cooja, which is a cross-level network simulator for the Contiki operating system[2].

T

II. D ESIGN CHOICES A. OS and protocols As mentioned before, we will optimise 2 parameters from existing protocols in the Contiki OS. We have selected ContikiMAC[3], a very efficient RDC protocol, and RPL[4], a distance vector IPv6 routing protocol. In ContikiMAC, we will optimise the wake-up frequency (8Hz or 16Hz), and in RPL we will optimise ETX ALPHA, which controls the ratio in which previous measurements are considered for the current link quality (65% or 90% weight for current measurement). Getters and setters for these parameters are implemented in the source code. We will use CoAP (Constrained Application Protocol) to distribute the values of these parameters to the sensornodes, by running an Er CoAP server[5] on each node, and implementing a CoAP client in the Negotiation Engine. B. Artificial Intelligence The Negotiation Engine will utilise Reinforcement Learning, and more specifically, the LSPI method[1]. Its incentives (or basis functions) are: total radio-off time and packet delivery ratio. The user is able to set goals for these functions. These goals are then compared to measurements gathered during an episode to calculate a reward (using an exponentially rising function that tapers off when the goal is exceeded). The state that yields

the highest expected future reward is then chosen. The possible states are as follows: • State 0: Wake-up frequency 8Hz, ETX ALPHA 90; • State 1: Wake-up frequency 16Hz, ETX ALPHA 90; • State 2: Wake-up frequency 16Hz, ETX ALPHA 65; • State 3: Wake-up frequency 8Hz, ETX ALPHA 65. C. Cooja scenario We will test this Negotiation Engine using a Cooja scenario with Contiki motes, using an UDGM (Unit Disk Graph Medium) radio model with distance loss. Twelve udp-senders send UDP packets to an udp-sink in an RPL network, using ContikiMAC. These packets contain a sequence number and RDC information, to be used in the calculation of rewards. We also implement a border router functionality in the udp-sink, to send information to a separate server (or the host of the Cooja simulation), which runs the Negotiation Engine. An episode can, for example, last until approximately 200 packets are received in the sink. A simplified overview of the setup is shown in Fig. 1. Notice that the approach is very modular, and several parts are interchangeable. The setup can easily be modified to use different scenarios, parameters, and even methods. The Negotiation Engine itself is also built out of different parts (not shown in Fig. 1), such as a main logic loop, a function that handles measurement gathering, main LSPI logic, . . . This means that changing one detail of the implementation does not necessitate a complete rework of the implementation.

Fig. 1. Simplified overview of the complete setup. UDP-senders send UDP packets in an RPL network to the UDP-sink. Measurements are sent by the UDP-sink to the server running the Negotiation Engine. A CoAP client is used by the Negotiation Engine to change parameters in the UDP-senders, by querying the CoAP servers

III. E VALUATION N EGOTIATION E NGINE A. Basic scenario To evaluate the choices of discrete values, we first test each incentive separately; only rewarding long radio-off times or high

throughputs. We see that for long radio-off times, we consistently pick a wake-up frequency of 8Hz, alternating between states 0 and 3. For a high throughput, we alternate between states 0 and 1, for an ETX ALPHA value of 90. We then allocate even attention to both incentives, with goals of 1% RDC and 95% throughput (about 10.5 packets lost on average in an episode of 200 received packets). We see that states 0 and 1 are picked about evenly (in a test run with 212 episodes, states 0 and 1 are picked 71 and 80 times, respectively). To evaluate this choice, we compare the results with a static choice of state 1 and state 3 (respectively the most and least chosen state). These results are shown in table I. The algorithm strikes a compromise between both extremes, to meet the incentives we specified. This test run was executed with a random exploration of 30%, which impacts the performance for a static scenario (no random exploration is needed, the environment does not change over time). Without random exploration, we can achieve averages of 1.32% RDC and only 2.43 lost packets (in a test run with 240 episodes).

as well, due to more frequent RPL path changes. We will test this hypothesis in a scenario with 350 episodes. In the first 153 episodes of the scenario, we will run the basic scenario as outlined previously. In episodes 154-350, the nodes will become mobile, with random movement (between -1 and +1 meter per second) for 40 seconds. This pattern will then be repeated. In the first half of the scenario, state 0 is preferred, with better performance in both RDC and packet loss. In the second half, state 1 becomes more and more interesting, and is being picked often (69 times vs. 93 times for state 0). State 3 shows much worse performance, however, and is seldomly being picked. The chosen states as a function of the episode (episodes 50-250) are shown in Fig. 2.

TABLE I R ESULTS ( AVERAGE RDC AND AVERAGE AMOUNT OF PACKETS LOST ) FOR TEST RUNS WITH THE ALGORITHM RUNNING , AND WITH STATIC STATES 1 AND 3 Fig. 2. State as a function of episode, episodes 50-250. Episode 154 is marked.

Algorithm State 1 State 3

RDC 1.34% 1.51% 1.23%

Lost packets 9.88 1.97 15.60

B. Negotiation Engine overhead To disseminate the state in the network, we need to implement updating periods, during which the CoAP PUT requests are sent to each node. In the current implementation, the UDP traffic is still being sent, along with the CoAP messages. After each node has sent an ACK of the state update, the Negotiation Engine waits 6 minutes before measurements are resumed. To estimate the overhead of such a period, we will look at its average RDC and at the average throughput of the UDP traffic in a test run with 486 episodes, using the same settings as before. As a measure of energy consumption, we first look at the average RDC during an update period. We measure an average increase of 0.000922% extra radio-on time, which is anincrease of only 0.07% relative to the RDC in measurement periods. We can thus assume that the impact on the lifetime is limited. However, most of the overhead cost is situated in the interference generated by the extra traffic. The throughput of UDP packets lowers to 88.08%, compared to an average of 94.62% during measurements periods. The usecase will have to take this into account, either by limiting or halting normal traffic during updateperiods, or by limiting random exploration (which limits the amount of updateperiods). C. Other scenarios To test a more volatile scenario, we will simulate mobile nodes. Mobile nodes should value a lower ETX ALPHA higher

IV. C ONCLUSION The simulations show that the implementation is able to strike a balance between incentives given by the developer, by changing the parameters of MAC– and routingprotocols at runtime. The system is also able to adapt to changing circumstances. There are many tests that can still be performed however, such as testing the implementation in hardware, testing other scenarios, other parameters and other protocols. The Negotiation Engine itself can also be improved, for example to allow more discrete values. Still, the simulation results are promising, and the overhead cost is not prohibitive. With further work, the implementation as it is presented in this thesis could aid in the development of a fully autonomous self-learning sensornetwork. R EFERENCES [1] Lagoudakis, M. G. and Parr, R. (2001). Model-free least squares policy iteration. Technical report, Advances in Neural Information Processing Systems. [2] http://www.contiki-os.org , consulted on 18/05/2013 [3] Dunkels, A. (2011). The contikimac radio duty cycling protocol. [4] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, J., and Alexander, R. (2012). RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks. RFC 6550 (Proposed Standard). [5] Kovatsch, M., Duquennoy, S., and Dunkels, A. (2011). A low-power coap for contiki. In Proceedings of the 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2011), Valencia, Spain.

INHOUDSOPGAVE

i

Inhoudsopgave 1 Inleiding

1

1.1

Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Doelstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

2 Literatuurstudie

4

2.1

Algemene ontwerpkeuzes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.2

Protocolkeuzes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2.1

MAC-protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2.2

Routeringsprotocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

Internet of things en het sensornetwerk . . . . . . . . . . . . . . . . . . . . . . . .

7

2.3.1

Internet of things . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.3.2

Besturingssysteem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.3.3

ContikiMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.3.4

“Ripple” routing protocol (RPL) . . . . . . . . . . . . . . . . . . . . . . .

9

2.3.5

Constrained Application Protocol (CoAP) . . . . . . . . . . . . . . . . . .

10

Zelf-lerend Algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.4.1

Type artifici¨ele intelligentie . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.4.2

Reinforcement Learning en Q-learning . . . . . . . . . . . . . . . . . . . .

12

2.4.3

Least Squares Policy Iteration (LSPI) . . . . . . . . . . . . . . . . . . . .

13

2.3

2.4

3 Ontwerp en implementatie 3.1

16

Opstelling basisscenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.1.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.1.2

Parameter getter-setters . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.1.3

Erbium CoAP Server

19

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

INHOUDSOPGAVE

3.2

3.3

3.1.4

Basisscenario: rpl-collect . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.1.5

Aanpassingen rpl-collect . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.1.6

Border router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

Negotiation Engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.2.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.2.2

RL-LSPI implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.2.3

Negotiation Engine logica . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.2.4

Verzamelen van metingen . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.2.5

Cf CoAP Client . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.2.6

Verwerken gegevens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

Integratie onderdelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.3.1

Verloop test run . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.3.2

Uitbreidingsmogelijkheden . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

4 Evaluatie Negotiation Engine 4.1

4.2

4.3

ii

35

Testen basisscenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

4.1.1

Basisalgoritme – RDC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

4.1.2

Basisalgoritme – Throughput . . . . . . . . . . . . . . . . . . . . . . . . .

38

4.1.3

Volledig basisscenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

4.1.4

Kost CoAP update periode . . . . . . . . . . . . . . . . . . . . . . . . . .

44

4.1.5

Besluit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

Testen geavanceerde scenario’s . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

4.2.1

Mogelijke scenario’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

4.2.2

Scenario met interferentie . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

4.2.3

Verhogen packet sending rate . . . . . . . . . . . . . . . . . . . . . . . . .

47

4.2.4

Scenario met mobiele nodes . . . . . . . . . . . . . . . . . . . . . . . . . .

49

Vari¨erende scenario’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

4.3.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

4.3.2

Vari¨erend scenario met mobiliteit . . . . . . . . . . . . . . . . . . . . . . .

51

5 Conclusie en verder onderzoek

54

5.1

Bereikte doelstellingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

5.2

Verder onderzoek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

INHOUDSOPGAVE

5.3

iii

5.2.1

Real-life scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

5.2.2

Verdere testmogelijkheden . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

5.2.3

Uitbreidingen Negotiation Engine . . . . . . . . . . . . . . . . . . . . . . .

57

Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

INLEIDING

1

Hoofdstuk 1

Inleiding 1.1

Probleemstelling

Een draadloos sensornetwerk bestaat uit een potentieel groot aantal sensornodes die verspreid zijn over een oppervlak om er metingen uit te voeren. De vergaarde metingen worden verzameld in een sink. Sensornodes zijn goedkope, onbetrouwbare en energiebeperkte devices die voor een zo lang mogelijke tijd autonoom moeten functioneren. Dit leidt tot een heel aantal uitdagingen. Het opzetten van een draadloos sensornetwerk vereist heel wat tijd, en is dus zeer duur. De protocolkeuzes en instellingen zijn immers sterk afhankelijk van vele parameters, zoals vereisten op vlak van levensduur, betrouwbaarheid, de omgeving, de densiteit van de nodes, mobiliteit van de nodes, . . . Deze parameters kunnen ook veranderen in de tijd, en de performantie van het netwerk kan hierdoor verminderen. Voorbeelden hiervan zijn veranderende interferentie, het wegvallen van nodes, veranderende vereisten in trafiek, . . . Vaak leidt dit tot een (dure) manuele herconfiguratie van het netwerk. Draadloze sensornetwerken zijn nog niet courant in gebruik door de hoge complexiteit, en dus ook kostprijs, van het opzetten en onderhouden ervan. Het doel van de thesis is om deze complexiteit te verminderen door het sensornetwerk zelf-lerend te maken, zodat er minder manuele configuratie nodig is.

1.2 Doelstelling

1.2

2

Doelstelling

Draadloze sensornetwerken kennen een zeer breed toepassingsdomein. Voorbeelden van toepassingen zijn[4]: militaire verkenning en bewaking, bosbrand detectie, pati¨ent monitoring en tracking, environmental control, inventory control, . . . Elk ontwerp van een sensornetwerk dient rekening te houden met de karakteristieken van de omgeving en de vereistes van de toepassing. Sensornodes in een rurale omgeving zullen een volledig verschillend stralingspatroon vertonen t.o.v. nodes in een haven, waar het metaal van de containers voor zeer veel interferentie kan zorgen. Een sensornetwerk voor militaire toepassingen zal veel striktere vereistes stellen t.o.v. betrouwbaarheid, daar waar sensornodes voor bosbranddetectie eerder rekening zullen houden met energie-effici¨entie, . . . De ontwerper van het sensornetwerk moet dus een aantal ontwerpkeuzes maken, op basis van de geschatte performantie van de verschillende keuzes. Hierbij dient hij rekening te houden met de eigenschappen van de omgeving, en de vereistes van de toepassing. Een volgende ontwerpstap bestaat erin om het netwerk (indien mogelijk) te simuleren, om de performantie ervan beter in te schatten. Als deze simulaties voldoen aan de specificaties, kan het netwerk ontplooid worden. Vaak dient er na deze stap nog verdere tuning te gebeuren, aangezien de resultaten in simulaties nagenoeg altijd verschillen van de werkelijkheid. De ontwerper dient dus na de ontplooiing verdere metingen uit te voeren, om ontwerpkeuzes te tunen, of indien nodig, andere keuzes te maken. Het doel van de thesis is aldus om het ontwerp te vereenvoudigen door het sensornetwerk zelflerend te maken. De ontwerper dient dan enkel de specificaties van de usecase te vertalen naar een set van incentives die bruikbaar zijn door het zelf-lerend netwerk. Door gebruik te maken van feedback uit de omgeving, kan het netwerk bij het opstarten intelligente keuzes maken, zonder dat de ontwerper hier actief bij betrokken moet worden. Dit proces van continu optimaliseren kan bovendien voortgezet worden in de tijd, zodat het netwerk zich automatisch aanpast aan de veranderende omgeving. Zo kan het netwerk bv. autonoom reageren op verslechterende transmissiekarakteristieken van de omgeving door een deel van de energie-effici¨entie op te geven (door bv. het vermogen van de radio op te drijven, of door het slaapschema aan te passen). Zo kan het netwerk zelf een trade-off realiseren tussen de verschillende incentives, die bepaald zijn door de usecase.

1.2 Doelstelling

3

Ook kan de gebruiker van het netwerk gemakkelijk de performantie van het netwerk finetunen door de incentives aan te passen. Een voorbeeld hiervan zou zijn dat de gebruiker minder pakketverlies wil, en bereid is om hiervoor toegevingen te doen in andere incentives. Het zelf-lerend maken van het sensornetwerk leidt aldus niet alleen tot een significante kostendaling door de vermindering van de bijdrage van de ontwerper, maar ook tot een algemenere verhoging van de adaptibiliteit en de flexibiliteit.

LITERATUURSTUDIE

4

Hoofdstuk 2

Literatuurstudie 2.1

Algemene ontwerpkeuzes

Het netwerk kan op enkele niveaus zelf-lerend gemaakt worden. Een aantal pistes zijn: het kiezen tussen verschillende protocollen, het aanpassen van parameters in deze protocollen, tot het afstemmen van protocolkeuzes tussen verschillende netwerken, teneinde de onderlinge interferentie te minimaliseren[23]. Voor deze thesis werd gekozen voor het optimaliseren van parameters in een welgekozen MAC– en routeringsprotocol. In eerste instantie wordt de scope ook beperkt tot het optimaliseren van twee verschillende parameters (zowel in een MAC– als in een routeringsprotocol), met elk twee toegelaten discrete waardes. Het algoritme wordt echter zo opgesteld dat zowel het aantal ge¨ımplementeerde parameters als het aantal discrete waardes gemakkelijk uitgebreid kan worden. Het zelf-lerend algoritme kan centraal of gedistribueerd ge¨ımplementeerd worden, elk met specifieke voor- en nadelen. Het grote voordeel van een gedistribueerd algoritme is schaalbaarheid, hetgeen een belangrijk punt is, gelet op de potenti¨ele grootte van sensornetwerken. Echter, de architectuur van het doorsnee sensornetwerk, waarin een sinknode data verzamelt van de sensornodes (Figuur 2.1)[4], suggereert reeds een centrale aanpak. Deze sinknode is typisch ook niet zo beperkt in energievoorziening en rekencapaciteit. Omwille van deze redenen wordt gekozen voor een gecentraliseerde artifici¨ele intelligentie, waarin de sinknode feedback verzamelt van de sensornodes, en op basis hiervan een beslissing neemt voor nieuwe parameterwaardes. Deze waardes worden vervolgens weer verdeeld over het netwerk.

2.2 Protocolkeuzes

5

Figuur 2.1: Typische architectuur van een draadloos netwerk. De artifici¨ele intelligentie zou in dit voorbeeld kunnen gedraaid worden op de task manager node, waarbij de sink fungeert als bottleneck voor de trafiek afkomstig van zowel de feedback als de configuratie

2.2

Protocolkeuzes

Omdat de keuze van het protocol op voorhand vast ligt, is het belangrijk om te kiezen voor performante en breed inzetbare protocollen voor zowel MAC als routering.

2.2.1

MAC-protocol

De hoofdfunctie van het MAC-protocol is om zoveel mogelijk energie te besparen, om zo de levensduur van het netwerk te verhogen. Voor deze thesis moet het protocol ook gemakkelijk aanpasbaar zijn zodat de tradeoff tussen energie-effici¨entie en bandbreedte/end-to-end latency gemakkelijk gemaakt kan worden. Een veelgebruikt concept is een slaapschema, waarbij de sensornode slechts periodisch de radio aanschakelt. Een voor de hand liggende parameter om aan te passen is de lengte van dit wake-up interval, waarbij een langere wake-up een hogere bandbreedte en een lagere end-to-end latency garandeert, ten koste van de levensduur van de node. In de literatuur zijn er veel voorstellen voor deze protocollen beschikbaar, zoals B-MAC[7], X-MAC[5] en WiseMAC[6]. Het principe van WiseMAC wordt ge¨ıllustreerd in (Figuur 2.2)[8]. Het is evident dat het verhogen van de wake-up frequency de end-to-end latency zal verminderen, en dat het verlengen van de wake-up periode de maximale bandbreedte verhoogt. Een gelijkaardig idee is uitgewerkt in ZeroCal[19], een MAC-protocol dat de lengte van het slaapritme automatisch aanpast at runtime. Een cruciaal verschil is echter dat dit protocol het

2.2 Protocolkeuzes

6

opstellen van een energiemodel vereist, waar een algoritme op basis van artifici¨ele intelligentie kan functioneren in een model-vrije omgeving, indien het zelf-lerend algoritme goed gekozen is (zie sectie 2.4).

Figuur 2.2: WiseMAC slaapschema: de zender stuurt een korte preamble uit zodat de bestemmeling de radio op standby houdt. Het veranderen van dit schema heeft invloed op de energie-effici¨entie enerzijds, en op de end-to-end latency en bandbreedte anderzijds.

2.2.2

Routeringsprotocol

De keuze van routeringsprotocol is sterk afhankelijk van de architectuur van het sensornetwerk. Aangezien de keuze gemaakt is om te werken met een gecentraliseerd algoritme, dienen we een protocol te kiezen dat geoptimaliseerd is voor het versturen van data van en naar een centrale sink. Daarom wordt geopteerd voor een protocol dat hierarchisch ge¨ınspireerd is. In hierarchische protocollen wordt de schaalbaarheid gerealiseerd door verschillende clusters te definieren, waarbij er in de cluster wordt gerouteerd via multi-hop communicatie. Elk clusterhoofd zou dan de artifici¨ele intelligentie kunnen implementeren, en de optimale configuratie bepalen voor de cluster.

2.3 Internet of things en het sensornetwerk

2.3 2.3.1

7

Internet of things en het sensornetwerk Internet of things

In deze thesis wordt de filosofie van het “Internet of things” gevolgd, waarin het sensornetwerk gezien wordt als extensie van het internet. Elke node is individueel aanspreekbaar via een IPv6 adres, zodat er met elke node individueel kan ge¨ınterageerd worden. Het besturingssysteem voor de sensornodes moet deze filosofie ondersteunen. Meer bepaald moet 6LoWPAN[9] (IPv6 over Low power Wireless Personal Area Network) en IPv6 ondersteund worden. 6LoWPAN maakt het mogelijk om IPv6 pakketten te versturen over netwerken die gebruik maken van de IEEE 802.15.4 standaard (definieert de physical layer en MAC voor low-rate personal area networks, of LR-WPANs). 6LoWPAN definieert de encapsulatie van de pakketten en de headercompressietechnieken die dit mogelijk maakt. De vertaling naar gecomprimeerde IPv6 headers en adressen en vice versa gebeurt dan in de border router, zodat het sensornetwerk transparant is t.o.v. de rest van het internet. Deze werkwijze neemt meer geheugen in beslag en verbruikt ook meer energie, maar biedt wel de voordelen van een IP gebaseerd sensornetwerk. Zo is het mogelijk om de parameters van elke node apart op te vragen en te wijzigen via eenvoudige HTTP GET en PUT / POST commando’s (zie sectie 2.3.5). De technologische evolutie verzekert ook steeds krachtigere sensornodes, met meer geheugen en rekenkracht, zodat de nadelen minder en minder opwegen tegen de voordelen.

2.3.2

Besturingssysteem

Op basis van deze vereisten wordt er gekozen voor ContikiOS[1], een open source OS dat specifiek ontwikkeld werd voor sensornodes in het “Internet of Things”. De volledige broncode is in C geschreven, en is vrij beschikbaar. Ook is er ondersteuning voorzien voor IPv6 en enkele recente standaarden waarvan gebruik zal gemaakt worden in deze thesis, nl. 6LoWPAN, RPL en CoAP. Verder draait er standaard een zeer effici¨ent MAC-protocol dat gebruik maakt van een periodisch wake-up interval, met enkele verbeteringen, zoals verder besproken zal worden. Contiki wordt specifiek ontwikkeld voor sensornodes, en ondersteunt dus ook een heel aantal recente MCU’s/SoCs, zoals de TI MSP430, gebruikt in o.a. de Tmote Sky, en de TI MSP430x, gebruikt in o.a. de Zolertia Z1[2].

2.3 Internet of things en het sensornetwerk

8

Contiki biedt ook een simulator aan, Cooja[12], dat toelaat om het volledig netwerk te simuleren in software. Deze simulator ondersteunt vele platformen, zoals de Tmote Sky en de Zolertia Z1. Dit laat de ontwikkelaar toe om netwerken op een grote schaal te simuleren, of om enkele nodes in hoog detail te emuleren. In deze thesis zal er van deze laatste optie gebruik gemaakt worden, om zo het concept in software te evalueren. Als radio medium wordt het zogenaamde UDGM (Unit Disk Graph Medium) met afstandsverlies gebruikt, om zo interferentie in rekening te kunnen brengen.

2.3.3

ContikiMAC

ContikiMAC[10] is een radio duty cycling MAC protocol, dat nodes toelaat om te communiceren, en toch voor het grootste deel van de tijd de radio uit te zetten. Het is ge¨ınspireerd op bestaande duty cycling protocollen, zoals besproken werd in sectie 2.2.1. De radio samplet periodisch het medium d.m.v. CCA’s (Clear Channel Assessments), die heel vermogenseffici¨ent zijn. Indien er activiteit op het medium gedetecteerd wordt, zal de node de radio aangeschakeld houden voor de tijd nodig om het pakket te ontvangen. Zo wordt het merendeel van de verzendkost naar de zender verschoven. Dit principe wordt ge¨ıllustreerd in Figuur 2.3[10]. Door de vele optimalisaties die ingebouwd zijn in ContikiMAC, vertoont dit protocol een veel hogere energie-effici¨entie dan bijvoorbeeld X-MAC (Figuur 2.4[10]). Dit protocol wordt standaard gebruikt in Contiki 2.6.

Figuur 2.3: ContikiMAC werking: De ontvanger samplet het medium periodisch d.m.v. CCA’s, en blijft wakker indien een transmissie gedetecteerd wordt. Na het ontvangen van het volgend pakket verstuurt de ontvanger een link layer ACK. De zender verstuurt het pakket dus tot er een link layer ACK ontvangen wordt van de ontvanger.

2.3 Internet of things en het sensornetwerk

9

Figuur 2.4: Vergelijking Radio Duty Cycle (RDC) performantie van X-MAC en ContikiMAC i.f.v. de channel check rate (wake-up frequency). ContikiMAC vertoont een merkbaar lagere RDC voor elke wake-up frequency, en is dus ook energie-effici¨enter.

2.3.4

“Ripple” routing protocol (RPL)

De sterke opkomst van IP smart object networks heeft ook op het vlak van routing voor een heel aantal uitdagingen gezorgd. Deze netwerken (LLNs, Low power and Lossy Networks) zijn potentieel erg groot, vertonen vaak veel interferentie, de nodes zijn vaak weinig betrouwbaar en beperkt in energie, . . . Het IETF richtte daarom een taskforce op, ROLL (Routing over Low power and Lossy) Networks[27], die als doel had om een IPv6 gebaseerde routing oplossing te vinden voor LLNs. Het resultaat van deze taskforce is het “Ripple” routing protocol (RPL)[26]. RPL is een distance vector IPv6 routing protocol, geoptimaliseerd voor LLNs. Het construeert een gerichte graaf (DODAG, Destination Oriented Directed Acyclic Graph), op basis van enkele metrieken, zoals paden met de beste ETX (Expected Transmission Count) waarde, of beste latency met nog steeds een aanvaardbaar energieverbruik. Aangezien de intentie van RPL nauw aansluit bij het “Internet of things”, wordt dit protocol standaard ondersteund in Contiki 2.6 als ContikiRPL[28]. Een voorbeeld van een DAG in Contiki wordt getoond in Figuur 2.5. In dit protocol zijn er een aantal parameters die vooraf ingesteld worden. Zo wordt de ETX waarde berekend op basis van zowel huidige als vorige metingen van de linkkwaliteit. De precieze

2.3 Internet of things en het sensornetwerk

10

ratio tussen deze metingen hangt af van netwerk tot netwerk. Zo zal een ontwerper voor een netwerk met mobiele nodes minder rekening willen houden met vorige metingen. In statische netwerken kan het aangewezen zijn om net meer rekening te houden met vorige metingen. Zo kan een kortstondige interferentie op het ogenblik van de ETX meting leiden tot een slechte ETX, en het pad kan onterecht gedropt worden. Door het netwerk zelf te laten bepalen welke ratio er optimaal is op dat bepaald moment, dient de ontwerper dit niet zelf meer in te stellen. Ook kan het netwerk deze ratio nog aanpassen indien de omgeving verandert, zonder dat er manueel onderhoud aan te pas moet komen.

Figuur 2.5: Een voorbeeld van een RPL netwerk in Contiki met 1 sink node (RPL root), en 24 andere nodes. De ETX waardes zijn in blauw vermeld bij elke link.

2.3.5

Constrained Application Protocol (CoAP)

Aangezien we opteren voor een gecentraliseerd algoritme, hebben we een methode nodig om te interageren met de nodes. Meer bepaald willen we de parameters kunnen opvragen en wijzigen in nodes. Gezien de filosofie van het “Internet of things”, dient deze methode zo algemeen mogelijk te zijn.

2.4 Zelf-lerend Algoritme

11

Het Constrained Application Protocol (CoAP)[29] beantwoordt aan al deze specificaties. CoAP is een web transfer protocol, speciaal ontwikkeld voor LLNs. CoAP voorziet een method / response model tussen twee application end-points, met enkele belangrijke componenten zoals resource discovery, URIs (Uniform Resource Identifiers) en content types. Dit laat het protocol toe om gemakkelijk vertaald te worden naar HTTP, terwijl het nog steeds ontwikkeld is voor simpliciteit en lage overhead. Ook CoAP wordt ondersteund in Contiki 2.6[15]. Met behulp van CoAP zal het mogelijk worden om een getter / setter te schrijven voor beide parameters in het MAC- en routeringsprotocol, om zo een eenvoudig uitbreidbaar updatemechanisme te voorzien. Het gecentraliseerd algoritme kan dan gebruik maken van een CoAP client om de parameters op te vragen en te wijzigen. De volledige protocol stack bij het gebruik van CoAP wordt weergegeven in Figuur 2.6[15].

Figuur 2.6: De volledige protocol stack bij het gebruik van CoAP.

2.4

Zelf-lerend Algoritme

Zoals eerder aangegeven in sectie 2.1, kiezen we hier voor een gecentraliseerd zelf-lerend algoritme. Hiervoor zijn er nog steeds enkele opties, die verder uiteengezet zullen worden. De vereistes voor dit algoritme zijn: een goede trade-off van huidige en toekomstige performantie, snel convergeren naar een (sub)optimale oplossing en model-vrije werking (geen vooropgesteld model van de omgeving vereist).

2.4 Zelf-lerend Algoritme

2.4.1

12

Type artifici¨ ele intelligentie

In het domein van machine learning is er al heel wat onderzoek gebeurd, en er bestaan vele methodes. Voorbeelden hiervan zijn Reinforcement Learning, Swarm Intelligence, genetisch geinspireerde algoritmes, . . . We kiezen hier voor Reinforcement Learning, aangezien er hiervoor effici¨ente algoritmes bestaan die geen voorkennis vereisen van de omgeving, en die een goede trade-off kunnen maken tussen het leerproces en onmiddellijke effici¨entie.

2.4.2

Reinforcement Learning en Q-learning

Reinforcement Learning is een verzamelterm voor biologisch ge¨ınspireerde machine learning technieken, waarbij de kennis vergaard wordt door trial and error in de omgeving[13, 14]. Bij elke stap wordt er een bepaalde actie ondernomen, en worden de resulaten ervan op de omgeving bestudeerd. Door dit vele malen te herhalen, leert het algoritme uit ervaring welke acties optimaal zijn in de huidige omgeving. Hierbij dient het algoritme ook rekening te houden met de gevolgen van zijn keuzes op langere termijn. In deze methodes interageert een agent met een omgeving. Deze omgeving bestaat uit een discrete set van states S, een discrete set van acties A die bestaan uit state-overgangen a(s) naar alle mogelijke states s, en een scalaire reward function R(s, a). Deze functie geeft de reward weer vanuit de omgeving als reactie op de actie a die de agent genomen heeft in de state s. De policy π : S → A van de agent wordt gedefinieerd als de actie die de agent zal ondernemen in de state s. Hierbij dient de agent een reward op lange termijn te maximaliseren. De policy die dit realiseert, noemen we de optimale policy π∗ . Hierbij wordt overigens niet verondersteld dat eenzelfde actie ondernomen in eenzelfde state altijd leidt tot eenzelfde eindstate, of tot eenzelfde reward. We veronderstellen echter wel dat de probabiliteiten hierop constant blijven, m.a.w. dat de omgeving stationair is (de algoritmes werken echter wel in traag vari¨erende niet-stationaire omgevingen, maar hier bestaat niet zoveel wiskundige achtergrond over[14]). Formeel kunnen we het probleem modelleren als een Markov beslissingsprobleem, dat bestaat uit[14]: • een discrete set van states S • een discrete set van acties A

2.4 Zelf-lerend Algoritme

13

• een reward function R : S × A → < • een state transition function T : S × A → Π(S), met Π(S) een probabiliteitsdistributie op de set van states S. Dit betekent dat T (s, a, s0 ) = P (s0 |s, a) de probabiliteit is dat de actie a ondernomen in de state s leidt tot een transitie naar een nieuwe state s0 .

Nu zijn er twee verschillende benaderingen om een optimale policy te bepalen. Er kan een model van de omgeving opgesteld worden, zodat de state transition function T (s, a, s0 ) en de reward function R(s, a) gekend zijn. Er bestaan echter ook technieken om een optimale policy te bepalen, zonder dat er een model gekend is op voorhand. Een van deze methodes is de zogenaamde Q-learning methode. Hierbij is de Q-functie Q∗ (s, a) de verwachte totale gedisconteerde reward bij het nemen van actie a in state s, en waarbij vanaf dan de optimale policy π∗ gevolgd wordt. Er kan aangetoond worden dat deze Q-functie als volgt geschreven kan worden (Bellman’s equation)[21]: Q∗ (s, a) = R(s, a) + γ

X

T (s, a, s0 ) max Q∗ (s0 , a0 ) 0

s0 ∈S

a

(2.1)

De eerste term van Q∗ (s, a) stelt de onmiddellijke reward voor, de tweede term is de gedisconteerde verwachte toekomstige reward, met disconteringsfactor γ. De optimale policy wordt dan gegeven door: π∗ (s) = arg maxa Q∗ (s, a). De methodes in Qlearning zijn dan gericht op het accuraat schatten van deze Q waardes, waaruit we de optimale policy kunnen achterhalen. Om te vermijden dat het algoritme blijft kiezen voor een lokaal maximum, moeten we toelaten dat de agent nu en dan een mogelijk suboptimale actie onderneemt, zodat de ruimte van Q-waardes verkend wordt. Hiertoe gebruiken we een -greedy algoritme, waarbij de agent met een kans  kiest voor een willekeurige actie, en met een kans 1 −  voor de actie met maximale Q-waarde. Deze factor  noemen we ook de exploratiefactor.

2.4.3

Least Squares Policy Iteration (LSPI)

Q-learning berekent dan deze Q-waardes deterministisch. Deze aanpak vertoont echter een aantal belangrijke nadelen in het geval van draadloze sensornetwerken. Een voorbeeld waar Qlearning toegepast werd op een routeringsprotocol (AdaR, Adaptive Routing[22]) toont enkele van deze nadelen aan:

2.4 Zelf-lerend Algoritme

14

• Een groot aantal episodes moet doorlopen worden eer het algoritme convergeert naar de optimale oplossing. Hierdoor kunnen de kosten van het samplen van de omgeving (waarbij er suboptimale keuzes gemaakt worden) de baten van de optimale keuze overschrijden • De prestatie van het algoritme is sterk afhankelijk van de initi¨ele settings • Het gebruiken van Q-learning kan leiden tot het breken van nodige convergentievoorwaarden voor het Markov beslissingsprobleem

Om deze nadelen te omzeilen, maken we gebruik van de Least Squares Policy Iteration methode (LSPI)[17]. In deze methode wordt de Q-functie voor een gegeven policy π benaderd door een gewogen lineaire combinatie Qπ van k basisfuncties, ook wel features genoemd: ˆ π (s, a, w) = Q

k X

φi (s, a)wi = φ(s, a)T w

(2.2)

i=1

waarbij φi (s, a) de i-de basisfunctie is, en wi haar gewicht in de approximatie. Deze k basisfuncties stellen dan de informatie voor die we bezitten over het state-action paar (s, a). De set van k basisfuncties φi (s, a) die we kiezen is sterk afhankelijk van de doelstellingen in het netwerk, en moeten manueel opgesteld worden. Voorbeelden van deze features zijn: de residuele energie van een node, de packet delivery ratio, de totale afstand tot de sinks in aantal hops, . . . We kunnen dan vergelijking (2.1) herschrijven in matrixformaat, met behulp van de lineaire approximatie in vergelijking (2.2): Φw ≈ R + γP π Φw waarbij Φ een (|S||A| × k) matrix is die de k basisfuncties bevat. Als we veronderstellen dat de kolommen van Φ lineair onafhankelijk zijn, dan bekomen we: ΦT (Φ − γP π Φ)wπ = ΦT R ˆ π (s, a) bekomen door het Dit betekent dat we de gewichten w van de lineaire approximaties Q volgend lineair stelsel op te lossen: w = A−1 b waarbij A = ΦT (Φ − γP π Φ) b = ΦT R

(2.3)

2.4 Zelf-lerend Algoritme

15

Deze matrices A en b worden nu bekomen door samples (s, a, s0 , r) uit de omgeving te verzamelen, waarbij s de huidige state is, a de gekozen actie, s0 de nieuwe state, en r de resulterende reward. Als we een set D van L samples verzameld hebben, D = (sdi , adi , s0di , rdi |i = 1, 2, . . . , L), dan kunnen we de matrices Φ, P π Φ en R als volgt bepalen:   φ(sdi , adi )T    ˆ = Φ   ···   T φ(sdL , adL )   0 0 T φ(sd1 , π(sd1 )     πΦ =  [ P  ···   0 0 T φ(sdL , π(sdL )   r  d1   ˆ = · · · R    rdL Het invullen van deze matrices Φ, P π Φ en R in het stelsel (2.3) levert dan de gewichten w op. LSPI is hier gepast omdat het algoritme sneller convergeert dan andere bekende algoritmes[17], omdat de samples heel nuttig gebruikt worden. Ook moeten er geen additionele parameters gezet worden, zoals een learning rate. De policy wordt ge¨evalueerd op basis van alle samples, en is dus insensitief t.o.v. beginsettings. Ook is de lineaire approximatie met basisfuncties hier heel geschikt, omdat we zo effectief een trade-off kunnen realiseren tussen verschillende doelen of features. De gewichten worden automatisch aangepast in het algoritme bij het verzamelen van nieuwe samples, zoals weergegeven in het stelsel (2.2).

ONTWERP EN IMPLEMENTATIE

16

Hoofdstuk 3

Ontwerp en implementatie 3.1 3.1.1

Opstelling basisscenario Inleiding

In deze sectie wordt het basisscenario gecre¨eerd, onderdeel per onderdeel. Zoals eerder vermeld, dienen ContikiMAC en RPL gebruikt te worden in een scenario dat voldoende trafiek genereert om de performantie te beoordelen. De parameters dienen veranderbaar te zijn via CoAP, dit betekent dat elke node ook een CoAP server moet draaien. Informatie over de performantie van het netwerk dient ook beschikbaar te zijn voor de Negotiation Engine, het centraal draaiende LSPI algoritme. Deze Negotiation Engine zal worden gedraaid op een aparte server die in contact staat met de root van het RPL netwerk. Ook de communicatie tussen de Negotiation Engine enerzijds en het scenario anderzijds dient dus ge¨ımplementeerd te worden. Ten slotte moet er aandacht besteed worden aan de algemeenheid van de oplossing, zodat het werk als basis kan dienen voor verdere verdieping en onderzoek. De uiteindelijke implementatie (met minder nodes, om het overzicht te bewaren) is te zien in Figuur 3.1. Deze figuur kan een handig overzicht geven bij dit hoofdstuk. UDP trafiek wordt gestuurd vanuit de udp-senders naar de udp-sink in het RPL netwerk. Informatie over de performantie van het netwerk wordt gestuurd vanuit de udp-sink naar de server waarop de Negotiation Engine draait. Ten slotte wordt CoAP gebruikt om de parameters in elke node op te vragen en te wijzigen.

3.1 Opstelling basisscenario

17

Figuur 3.1: Een overzicht van het basisscenario dat we zullen opstellen.

3.1.2

Parameter getter-setters

Vooreerst kijken we naar de specifieke parameters die we initieel willen afstellen. Deze beinvloeden het slaapritme van ContikiMAC (zie ook sectie 2.3.3), en de ratio tussen nieuwe en oude metingen bij het berekenen van de ETX (Expected Transmission Count) waarde van RPL (sectie 2.3.4). Zoals aangeduid in Figuur 2.4[10], heeft de wake-up frequency (channel check rate) een grote invloed op de radio duty cycle, en dus ook op het energieverbruik en de performantie. Deze parameter kan geset worden in een scenario (voor alle nodes die deel uitmaken van dat scenario) m.b.v. de volgende lijn code: #define NETSTACK RDC CHANNEL CHECK RATE 8 Hiermee wordt de wake-up frequency op 8Hz gedefinieerd bij wijze van voorbeeld, zoals we kunnen afleiden uit de volgende lijn code in contikimac.c: #define CYCLE TIME (RTIMER ARCH SECOND / NETSTACK RDC CHANNEL CHECK RATE) Uiteraard willen we dit niet statisch defini¨eren voor alle nodes, maar kunnen opvragen en wijzigen per node afzonderlijk. Hiertoe wijzigen we de broncode voor het ContikiMAC protocol (/core/ net/mac/contikimac.c en /core/net/mac/contikimac.h). Meer bepaald wordt er een gettersetter gedefinieerd in contikimac.h: // G e t t e r and S e t t e r f o r NETSTACK RDC CHANNEL CHECK RATE int NETSTACK RDC CHANNEL CHECK RATE2

3.1 Opstelling basisscenario

18

= NETSTACK RDC CHANNEL CHECK RATE; int getCHANNEL CHECK RATE( ) { return NETSTACK RDC CHANNEL CHECK RATE2; } void setCHANNEL CHECK RATE( int x ) { NETSTACK RDC CHANNEL CHECK RATE2 = x ; } Waarbij ook alle instanties van deze wake-up frequency in contikimac.c aangepast worden. Dit laat ons toe om de frequentie aan te passen at runtime, in elke node. De beginwaarde wordt nog steeds globaal gedefinieerd. We zullen als mogelijke wake-up frequencies 8Hz en 16Hz nemen. Voor het RPL protocol willen we de parameter aanpassen die de ratio bepaalt tussen de huidige waarde van de linkkwaliteit en vorige waardes. Deze waardes worden berekend in de broncode die het bijhouden van informatie van de buren regelt voor RPL: /core/net/neighbor-info.c: /∗ Update t h e EWMA o f t h e ETX f o r t h e n e i g h b o r . ∗/ n e w m e t r i c = ( ( u i n t 1 6 t ) r e c o r d e d m e t r i c ∗ ETX ALPHA + ( u i n t 1 6 t ) p a c k e t m e t r i c ∗ (ETX SCALE − ETX ALPHA) ) / ETX SCALE ; Hierbij is ETX SCALE gedefinieerd op 100. Opnieuw defini¨eren we een eenvoudige gettersetter voor deze ETX ALPHA waarde. Deze getter-setter implementeren we in de broncode /core/net/neighbor-info.c: // G e t t e r and S e t t e r f o r ETX ALPHA int ETX ALPHA2 = ETX ALPHA; int getETX ALPHA ( ) { return ETX ALPHA2 ; } void setETX ALPHA( int x ) { ETX ALPHA2 = x ;

3.1 Opstelling basisscenario

19

} Ook passen we elke instantie van ETX ALPHA aan naar ETX ALPHA2 in de broncode. Standaard krijgt deze parameter de waarde 90, m.b.v. de getter-setter kunnen we deze waarde laten vari¨eren in het bereik [0,100]. We zullen als mogelijke waardes voor ETX ALPHA 90 en 65 nemen. We verwachten dat de waarde 65 betere prestaties zal voorleggen indien de nodes mobiel zijn, aangezien het pad sneller opnieuw gevormd kan worden.

3.1.3

Erbium CoAP Server

Om de getter-setters extern op te roepen, dienen we een CoAP server te implementeren op elke node. De algemeenheid van CoAP laat ons toe om bv. een HTTP GET request te sturen naar een specifieke node (a.d.h.v. het IPv6 adres). De border router zou deze HTTP request dan kunnen vertalen naar een CoAP request, waarna deze behandeld kan worden in de node. De node genereert een CoAP response, die in de border router weer vertaald kan worden naar een HTTP response. Deze vertaling wordt ook beschreven in de CoAP drafts[29]. In deze implementatie werken we met een CoAP client (zie sectie 3.2.5). CoAP wordt in Contiki ondersteund met de Erbium (Er) REST engine[15], die de CoAP draft specificatie implementeert (versie 07)[29]. Dit laat ons toe om heel eenvoudig een getter-setter server te implementeren op elke node. Hiertoe vertrekken we van een voorbeeldscenario dat ge¨ıncludeerd is in de broncode: /examples/er-rest-example/. Dit bevat o.a. de broncode (er-example-server.c) voor een node die een Er server draait, met een aantal mogelijke resources (zoals een helloworld, leds toggle, . . . ). We implementeren twee extra resources, die ons toelaten om beide parameters op te vragen en te wijzigen. De resource die de getter-setter van ETX ALPHA afhandelt, wordt als volgt gedefinieerd: RESOURCE(ETX, METHOD GET | METHOD POST | METHOD PUT, ” params /ETX ALPHA” , ” t i t l e =\”ETX ALPHA v a l u e g e t o r s e t \ ” ; r t =\”Text \” ” ) ; Hiermee wordt een resource “ETX” gecre¨eerd, die de zowel GET, POST als PUT requests behandelt. Het URI pad is “params/ETX ALPHA”. In de handler voor deze resource dienen we nu onderscheid te maken tussen een GET en een PUT/POST request, om respectievelijk de getter of setter op te roepen. Hiervoor gebruiken we de method code[29] van de request, zie ook Tabel 3.1. Voor specifieke details van de handler verwijzen we naar de ge¨ıncludeerde broncode.

3.1 Opstelling basisscenario

20

We defini¨eren een analoge resource voor de wake-up frequency. We kunnen ook gemakkelijk nieuwe resources implementeren voor nieuwe parameters, indien de correcte getters en setters gedefinieerd zijn in de broncode van de betrokken protocollen (zie sectie 3.1.2).

Code

Methode

1

GET

2

POST

3

PUT

4

DELETE

Tabel 3.1: Method codes en de corresponderende methode[29]

Het serverproces dat de CoAP requests verwerkt en de ACKs of responses terugstuurt, kan dan gestart worden samen met andere processen (die bv. de reguliere trafiek zullen genereren).

3.1.4

Basisscenario: rpl-collect

De vereisten voor het scenario zijn: gebruik van IPv6, ContikiMAC, RPL en CoAP, een border router, regelmatige trafiek en een manier om de performantie te meten. Een van de voorbeelden in de broncode implementeert vele van deze functies: /examples/ipv6/rpl-collect/. Het basisscenario bestaat uit een RPL DAG met 1 udp-sink als root node en 24 udp-senders als leaf nodes (zie ook Figuur 2.5), waarbij de udp-senders periodisch UDP pakketten versturen naar de sink. Deze pakketten bevatten nuttige data, waarmee statistieken opgemaakt worden over het netwerk in een aparte Java applicatie, CollectView. Twee van deze statistieken kunnen we direct gebruiken als performantie-maatstaven voor elke node: het geschatte aantal verloren pakketten en de RDC. Een voorbeeld van de grafiek met RDC waardes is te zien in Figuur 3.2. We kunnen deze informatie in eerste instantie uitprinten vanuit CollectView naar tekstbestanden, en terug uitlezen bij het verzamelen van de meetgegevens. Ook kan de berekening rechtstreeks gemaakt worden, door de meetgegevens bij ontvangst van een UDP pakket te forwarden via de border router naar de Negotiation Engine. Omdat een schatting van het aantal verloren pakketten eenvoudig af te leiden valt uit de sequence numbers die meegegeven worden in de pakketten, zullen we deze statistiek zelf berekenen. De sink stuurt

3.1 Opstelling basisscenario

21

deze sequence numbers door in UDP pakketten naar de Negotiation Engine, waar deze verzameld en verwerkt zullen worden (zie secties 3.1.6 en 3.2.4). De RDC waardes worden uitgelezen uit het tekstbestand dat geprint wordt door code die we toevoegen in CollectView.

Figuur 3.2: RDC (Radio Duty Cycle) grafiek van een basisscenario

In de CollectView tool kunnen we een grafiek opvragen met de RDC waardes (zie ook Figuur 3.2). Om deze waardes ook uit te schrijven naar een tekstbestand, zullen we de code van de tool aanpassen waar deze gegevens verwerkt worden. De grafiek met RDC waardes wordt opgesteld in de broncode /tools/collect-view/src/se/sics/contiki/collect/CollectServer. java: new BarChartPanel ( this , POWER, ” Radio Duty Cycle ” , ” Average Radio Duty Cycle ” , ” Nodes ” , ”Duty Cycle (\%) ” , new S t r i n g [ ] { ” Radio l i s t e n ” , ” Radio t r a n s m i t ” } ) { { ValueAxis a x i s = c h a r t . g e t C a t e g o r y P l o t ( ) . getRangeAxis ( ) ;

3.1 Opstelling basisscenario

22

( ( NumberAxis ) a x i s ) . s e t A u t o R a n g e I n c l u d e s Z e r o ( true ) ; } } // . . . } In deze BarChartPanel wordt vervolgens een methode voorzien om sensordata toe te voegen aan deze grafiek: protected void addSensorData ( SensorData data ) { Node node = data . getNode ( ) ; S t r i n g nodeName = node . getName ( ) ; S e n s o r D a t a A g g r e g a t o r a g g r e g a t o r = node . g e t S e n s o r D a t a A g g r e g a t o r ( ) ; d a t a s e t . addValue ( 1 0 0 ∗ a g g r e g a t o r . getAverageDutyCycle ( S e n s o r I n f o . TIME LISTEN ) , c a t e g o r i e s [ 0 ] , nodeName ) ; d a t a s e t . addValue ( 1 0 0 ∗ a g g r e g a t o r . getAverageDutyCycle ( S e n s o r I n f o . TIME TRANSMIT) , c a t e g o r i e s [ 1 ] , nodeName ) ; } We voegen nu een methode toe in deze functie addSensorData waardoor we een totale RDC waarde uitprinten naar een tekstbestand RDC.txt: try { // P r i n t RDC. t x t S t r i n g d i r = ” /home/ u s e r / e c l i p s e w o r k s p a c e / N e g o t i a t i o n E n g i n e / ” ; // Keep t h e f i l e s h o r t : r e s e t f i l e when RDC o f node 2 i s p r i n t e d : boolean n e w F i l e = ( nodeName . e q u a l s ( ” 2 . 0 ” ) ) ? f a l s e : true ; B u f f e r e d W r i t e r out = new B u f f e r e d W r i t e r (new F i l e W r i t e r ( d i r+ ”RDC. t x t ” , n e w F i l e ) ) ; double totaalRDC = 100∗ a g g r e g a t o r . getAverageDutyCycle ( S e n s o r I n f o . TIME LISTEN) + 100∗ a g g r e g a t o r . getAverageDutyCycle ( S e n s o r I n f o . TIME TRANSMIT ) ; out . w r i t e ( nodeName + ” : ” + totaalRDC ) ; out . newLine ( ) ; out . c l o s e ( ) ;

3.1 Opstelling basisscenario

23

} catch ( E x c e p t i o n e ) { System . e r r . p r i n t l n ( ” E r r o r : ” + e . getMessage ( ) ) ; } Hierdoor wordt de data die gebruikt wordt voor het updaten van de grafiek (Figuur 3.2), ook uitgeprint naar het tekstbestand. Zo kunnen we deze data op een eenvoudige manier verwerken in de Negotiation Engine.

3.1.5

Aanpassingen rpl-collect

Zoals reeds aangehaald in sectie 3.1.4, implementeert rpl-collect de volgende functies: een IPv6 RPL netwerk met regelmatige trafiek, waarbij verschillende performantie-metrieken verzameld worden. Ook wordt standaard ContikiMAC gebruikt als MAC protocol. Merk op dat in de sink de radio duty cycling permanent uitgeschakeld wordt, gezien de grote hoeveelheid aan pakketten die er verwerkt moeten worden (zowel datapakketten als controlepakketten voor bv. RPL). Het toevoegen van de Er CoAP server in elke node kan ge¨ımplementeerd worden door de broncode ervan te includeren in het project, en het serverproces te starten na de initialisatie van de udp-senders. In de makefile van het project dient nu ook het REST framework ge¨ıncludeerd te worden, waarbij ook enkele vlaggen gezet worden (o.a. wordt ook het gebruik van TCP uitgeschakeld, dit betekent dat de sink hier ook geen gebruik meer van kan maken voor communicatie met de Negotiation Engine!). Aangezien de sink geen CoAP services dient te gebruiken (maar het gebruik van TCP kan wel handig zijn), zullen we de sink declareren in een apart project. De hoofding van de makefile van het project (te vinden in de map /examples/thesis/rpl-collect-separatesink) begint dus als volgt: CONTIKI = . . / . . / . . APPS = p o w e r t r a c e c o l l e c t −view CONTIKI PROJECT = udp−s e n d e r PROJECT SOURCEFILES += c o l l e c t −common . c #Add t h e CoAP s e r v e r code PROJECT SOURCEFILES += er−s e r v e r . c #Add t h e P r o j e c t d i r t h a t c o n t a i n s t h e udp−s i n k code PROJECTDIRS += . . / udp−s i n k −s e p a r a t e

3.1 Opstelling basisscenario

24

De udp-sender wordt opgebouwd met processen die verspreid zijn over 3 sourcefiles: udpsender.c, dat het main proces bevat, collect-common.c, waarin het versturen van pakketten geregeld wordt, en er-server.c, de Erbium CoAP server (zie sectie 3.1.3). Ook wordt er een aparte project directory toegevoegd, waarin de code te vinden is voor de udp-sink. We moeten er nu wel voor zorgen dat het volledig scenario nog correct ge¨ınitialiseerd wordt. Om bijvoorbeeld communicatie mogelijk te maken, moeten we de de vlag die de 6LoWPAN compressie bepaalt, in beide projecten gelijk zetten (zodat beide nodetypes dezelfde compressie toepassen). Deze wordt immers gedeclareerd in het project-conf.h configuratiebestand, dat uniek is per project. Bij het combineren van de voorgenoemde processen bereiken we al snel de limiet van RAM en ROM geheugen op de Sky nodes die gebruikt worden in het rpl-collect scenario. De gebruikelijke technieken om geheugen te besparen, zoals het beperken van buffer sizes, voldoen niet om dit op te lossen. Een Sky node heeft als microcontroller de Texas Instruments MSP430 (10kb RAM, 48kb flash). Bij het toevoegen van de Er server verkrijgen we een RAM overflow van 44bytes, en een ROM overflow van 4050bytes. Om dit te verhelpen zullen we als platform de Zolertia Z1[2] gebruiken, die de 2de generatie TI MSP430 microcontroller gebruikt (MSP430F2617, 8kb RAM, 92kb flash). Samen met enkele RAM besparende maatregelen (beperken van uIP buffers, neighbor lists, REST chunk sizes, . . . ) die geen invloed hebben op de beoogde functionaliteit, kunnen we deze Z1 motes gebruiken in het scenario. De RAM besparende maatregelen worden gedeclareerd in het configuratiebestand. Het uiteindelijk scenario dat we zullen gebruiken, is opgesteld in .csc XML bestanden (zie /examples/thesis/rpl-collect-separatesink). Merk op dat we het aantal nodes ook terugbrengen naar 13 (12 udp-senders, 1 udp-sink), dit om de simulatiesnelheid te verhogen.

3.1.6

Border router

Het implementeren van border router functionaliteit in het scenario is echter niet direct oplosbaar. In voorbeeldscenario’s waar een border router nodig is, wordt er gebruik gemaakt van een aparte border router node, die niet energiebeperkt is (radio permanent aan). Deze border router is te vinden in de broncode: /examples/ipv6/rpl-border-router. Deze node zet een

3.1 Opstelling basisscenario

25

RPL DAG op als root, met een bepaalde prefix (bv. aaaa::). Ook zet de node een SLIP (Serial Line Interface Protocol) connectie op met de linux host, om zo als router te fungeren tussen de PC en het sensornetwerk. SLIP is een verouderd protocol dat een IP pakket encapsuleert en verstuurt over een seri¨ele poort (of via een modem connectie). Voor PCs is dit protocol vervangen door het PPP (Point-to-Point Protocol), maar omwille van de lage overhead wordt SLIP nog gebruikt op microcontrollers. In Contiki zijn er tools voorzien om een SLIP tunnel op te zetten tussen een fysieke seri¨ele poort (of met Cooja), en een virtuele netwerkinterface in linux (tun interface). De lijn in de makefile waarmee we de tunslip6 tool opstarten om een IPv6 tunnel op te zetten naar het scenario is bv. als volgt gedefinieerd: connect −r o u t e r −c o o j a : $ (CONTIKI) / t o o l s / t u n s l i p 6 sudo $ (CONTIKI) / t o o l s / t u n s l i p 6 −L −v6 −a 1 2 7 . 0 . 0 . 1 a a a a : : 1 /64 Dit betekent dat de interface het adres aaaa::1 heeft, en dat de pakketten met als bestemming aaaa::/64 over deze interface gerouteerd zullen worden (naar de local host). De border router neemt kennis van deze prefix via een request-response mechanisme (zie verder). Een pakket gestuurd vanuit deze linux pc met als bestemming bv. de node met IPv6 adres aaaa::c30c:0:0:2 wordt dan gerouteerd over deze interface naar de border router in de Cooja omgeving. De border router (ook de DAG root node) kan dit pakket dan forwarden naar de correcte leaf-node. We kunnen deze border router (/examples/ipv6/rpl-border-router) echter niet zomaar integreren in het scenario, aangezien de udp-sink al de DAG root node is. We dienen dus de border router functionaliteit te integreren in de udp-sink, zodat deze node beide functies combineert (zie verder). Het opsplitsen van het scenario in twee projecten (project met udp-sender, project met udp-sink) zoals eerder besproken, biedt hier opnieuw voordeel, aangezien de code voor beide nodes heel wat verschilt (vergeleken met het origineel scenario). De udp-senders draaien nu immers ook een Er CoAP server, terwijl de udp-sink instaat voor border router functionaliteit. De aangepaste udp-sink met ge¨ıntegreerde border router is te vinden in de map /examples/ thesis/udp-sink-seperate. De hoofding van de makefile van dit project is als volgt: CONTIKI = . . / . . / . . CONTIKI PROJECT=udp−s i n k APPS = p o w e r t r a c e c o l l e c t −view

3.1 Opstelling basisscenario

26

PROJECT SOURCEFILES += s l i p −b r i d g e . c PROJECT SOURCEFILES += c o l l e c t −common . c De code in slip-bridge.c is identiek aan deze uit de voorbeeld border router /examples/ ipv6/rpl-border-router, en implementeert functies om te kunnen communiceren over de SLIP bridge. De functies die hier ge¨ımplementeerd worden zijn als volgt: • Het defini¨eren van de fallback interface: indien de bestemming van het pakket niet gekend is (buiten de RPL DAG), wordt het pakket over de serial line gestuurd; • Het initialiseren van de SLIP connectie met een bepaalde baud rate (hier 115200bits/s); • Het implementeren van een request-response mechanisme om de prefix te bepalen; • Het implementeren van de nodige output functies, om data te kunnen versturen over de SLIP connectie. Verder passen we de code in de udp-sink aan, gelijkaardig aan deze in het voorbeeld /examples/ ipv6/rpl-border-router, zodanig dat de RPL DAG slechts opgebouwd wordt na het ontvangen van een prefix via de SLIP connectie. Verder zetten we een UDP connectie op met de Negotiation Engine om het aantal ontvangen pakketten en de sequence numbers door te sturen. Het totale aantal ontvangen pakketten wordt bijgehouden in de sink d.m.v. een counter. De sequence numbers kunnen we rechtstreeks uit de ontvangen UDP pakketten halen. Deze informatie sturen we door naar de server waarop de Negotiation Engine draait, naar 2 verschillende poorten (hier kiezen we voor poorten 1234 en 2345). Daartoe voegen we de volgende code toe in de tcpip handler die opgeroepen wordt bij ontvangst van een pakket: // Send t o N e g o t i a t i o n Engine : t o t a l Count : s p r i n t f ( buf , ”Count:\%u\n”,++count ) ; u i p u d p p a c k e t s e n d t o ( h o s t c o n n , buf , s t r l e n ( buf ) , &h o s t i p a d d r , UIP HTONS(NEGOTIATION ENGINE PORT ) ) ; // Send t o N e g o t i a t i o n Engine : sender , s e qn o s p r i n t f ( buf , ” Sender :\%u : Seqno :\%u\n” , s e n d e r . u8 [ 0 ] + ( s e n d e r . u8 [ 1 ] << 8 ) , seqno ) ; u i p u d p p a c k e t s e n d t o ( h o s t c o n n , buf , s t r l e n ( buf ) , &h o s t i p a d d r , UIP HTONS(NEGOTIATION ENGINE PORT2 ) ) ;

3.2 Negotiation Engine

27

Het toevoegen van dergelijke UDP connecties naar de server kan dus eenvoudig opgezet worden, dankzij de SLIP connectie.

3.2

Negotiation Engine

3.2.1

Inleiding

In deze sectie zullen we de praktische uitwerking van het centraal draaiend, zelf-lerend algoritme bespreken. Zoals uiteengezet in sectie 2.4, kiezen we voor Reinforcement Learning, en meer bepaald LSPI. Aangezien het algoritme buiten het sensornetwerk draait, dienen we geen rekening te houden met energie- of geheugenbeperkingen. Het algoritme wordt dan ook ge¨ımplementeerd in Java. Een overzicht van de werking van de Negotiation Engine is te zien in Figuur 3.3.

Figuur 3.3: Een overzicht van het basisscenario dat we zullen opstellen.

3.2.2

RL-LSPI implementatie

Voor de implementatie van het RL-LSPI algoritme (LSPI NE.java) volgens sectie 2.4.3 baseren we ons op de implementaties uit [23, 22]. Initieel zullen we enkel 2 parameters beschouwen, elk met 2 discrete waarden, in totaal dus 4 states. Deze states worden als volgt gekozen: • State 0: Channel Check Rate 8Hz, ETX ALPHA 90 • State 1: Channel Check Rate 16Hz, ETX ALPHA 90 • State 2: Channel Check Rate 16Hz, ETX ALPHA 65

3.2 Negotiation Engine

28

• State 3: Channel Check Rate 8Hz, ETX ALPHA 65 Zoals beschreven in sectie 2.4.3, kiezen we de state met de hoogste Q-waarde (formule (2.2)). Deze Q-waardes zijn het resultaat van een lineaire som van basisfuncties, waarbij de basisfuncties (of ook features) manueel ontworpen dienen te worden, afhankelijk van de beoogde doelstellingen in het netwerk. In eerste instantie defini¨eren we de basisfuncties als volgt: • φ0 : Total average radio-off time (%) (100-RDC) • φ1 : Packet Delivery Ratio (%) (100-Packet Loss Ratio) Waarbij de basisfuncties φ0 en φ1 respectievelijk maatstaven zijn voor de verbruikte energie en het pakketverlies in een episode. De gewichten w0 en w1 worden ge¨ınitialiseerd op 0.5, en worden verder berekend m.b.v. het stelsel (2.3). Energie in een sensornode wordt, algemeen gezien, gebruikt voor twee doeleinden: communicatie en dataverwerking[4]. Omdat communicatie veruit het meeste energie verbruikt[4], en om het verwerken van de gegevens te vereenvoudigen, nemen we enkel de energie verbruikt in communicatie in rekening in de basisfunctie φ0 . Contiki is voorzien van een tool die de energie opmeet, powertrace[11], waarmee de energie kan geschat worden. Zoals te zien is in Figuren 3.2 en 3.4, is het meeste van deze energie toe te schrijven aan het radioverkeer (radio listen en transmit), en is er hier ook meer variatie te vinden tussen de nodes onderling. Zoals ook vermeld wordt in sectie 2.4.2, dienen we ook de exploratiefactor  te bepalen. Dit is een ontwerpkeuze, afhankelijk van de doelstellingen van de ontwerper. In onze implementatie wordt deze exploratiefactor statisch gedefinieerd in de code. Andere methodes hiervoor zullen we bespreken in sectie 5.2.3. De keuze van rewardfuncties is minder eenvoudig, aangezien het algoritme voldoende mogelijkheden moet bieden aan de gebruiker om zelf zijn policies te bepalen. Een eerste implementatie zou er als volgt kunnen uitzien: Rtotal = Rlif etime + Rloss Rlif etime = φ0 Rloss = φ1

3.2 Negotiation Engine

29

Figuur 3.4: Powertrace grafiek van een basisscenario

Deze na¨ıeve implementatie is echter niet zo nuttig vanwege verschillende redenen. De groottes van de rewards Rlif etime en Rloss kunnen drastisch van elkaar verschillen, gezien de verwachtingen van de total average radio-off time en de packet delivery ratio niet noodzakelijk van eenzelfde grootteorde zijn. Ook kan de gebruiker hier geen policy bepalen. Het is interessanter om de gebruiker een aantal opties te laten bepalen, over wat hij verwacht van het netwerk, en waar hij de nadruk op wilt leggen. We kunnen bijvoorbeeld een richtwaarde vragen voor de totale radio-off tijd en de packet throughput, en de rewards begrenzen indien we deze waardes bereiken, met slechts een marginale groei indien we de verwachtingen overschrijden. Hierdoor kan het algoritme zich concentreren op het verbeteren van andere features (die bv. de doelstelling nog niet bereikt hebben). Ook kunnen we de verhouding vastleggen tussen deze

3.2 Negotiation Engine

30

features. Een voorbeeld hiervan is als volgt: Rtotal = C × Rlif etime + (1 − C) × Rloss φ

Rlif etime = 1 − e

(−α×( RDC0

goal

))

φ

Rloss = 1 − e

1 (−α×( throughput

goal

(3.1) ))

Deze rewardfuncties Rlif etime en Rloss zijn exponentieel stijgende, uitdovende functies. Indien we α = 3 kiezen in het stelsel (3.1), bekomen we de curve in Figuur 3.5. Deze curve vlakt af naarmate we de doelstelling naderen, en blijft stijgen (zij het exponentieel afnemend) naarmate we de doelstelling overschrijden. De rewards zijn nu ook genormaliseerd, zodat deze zonder problemen kunnen opgeteld worden in Rtotal . We zullen deze functie met α = 3 dan ook gebruiken in de evaluatie van de Negotiation Engine (zie hoofdstuk 4).

Figuur 3.5: De functies Rlif etime en Rloss i.f.v.

φ0 RDCgoal

en

φ1 throughputgoal

Ook kan de gebruiker hier het gewicht van beide features bepalen, door de parameter C in de functie Rtotal vast te leggen (stelsel (3.1)). Dit maakt het mogelijk voor de gebruiker om te bepalen in hoeverre het netwerk de nadruk dient te leggen op energie-effici¨entie dan wel op throughput.

3.2 Negotiation Engine

3.2.3

31

Negotiation Engine logica

De functies uit LSPI NE.java (zie sectie 3.2.2) worden opgeroepen uit de centrale Negotiation Engine logica, ge¨ımplementeerd in NegotiationEngine.java. Deze broncode bevat de mainfunctie, en controleert de input en output. Zie ook het overzicht in Figuur 3.3. Vooreerst wordt aan de gebruiker een aantal initi¨ele settings gevraagd, om het algoritme te sturen. Zoals eerder vermeld, wordt een doel gevraagd voor de totale radio-off tijd, de packet throughput en de parameter C die het gewicht van deze features in Rtotal vastlegt (zie ook het stelsel (3.1)). Het meeste van de logica wordt ge¨ımplementeerd in een (potentieel oneindige) lus, zie Figuur 3.6[23]. Er wordt een nieuwe episode gestart van een bepaalde duur (bv. 200 ontvangen pakketten). Tijdens deze episode wordt er feedback verzameld uit het netwerk (bepaald door de gekozen features of basisfuncties). Aan het einde van een episode wordt er een beslissing gemaakt (via de logica in LSPI NE.java), en deze beslissing wordt verdeeld in het netwerk m.b.v. een CoAP client (zie sectie 3.2.5). Vervolgens wordt er een tijd gewacht, tot de invloed van de updatecyclus niet meer merkbaar is in de metingen (in deze scriptie nemen we een wachttijd aan van 6 minuten). Het aantal ontvangen pakketten kunnen we uitlezen uit de UDP pakketten die we toegestuurd krijgen van de sink, zoals uiteengezet in sectie 3.1.6.

3.2.4

Verzamelen van metingen

De Negotiation Engine maakt gebruik van de module Measurements.java om metingen te verzamelen en bij te houden uit het netwerk. Zo wordt er een lijst bijgehouden met de RDC waardes van elke node, en een lijst met sequence numbers van de laatst ontvangen pakketten van elke node. Hieruit kan dan de gemiddelde RDC waarde berekend worden voor de basisfunctie φ0 , en het totale aantal verloren pakketten voor de basisfunctie φ1 . Deze RDC waardes worden verzameld m.b.v. de CollectView applicatie, door deze waardes niet alleen te schrijven naar een interne database (cf. Figuur 3.2), maar ook naar een tekstbestand, dat uitgelezen kan worden in Measurements.java.

3.2 Negotiation Engine

32

Figuur 3.6: De lus die een Reinforcement Learning algoritme doorloopt om te interageren met en te leren uit de omgeving

De sequence numbers worden op een gelijkaardige manier verzameld als het totale aantal verzonden pakketten (zie sectie 3.2.3), het totale aantal verloren pakketten wordt geschat m.b.v. deze waardes. Merk op dat we niet gebonden zijn aan de methodes die hier uiteengezet zijn. Vele opties zijn hier mogelijk. Zo kan de Negotiation Engine aangepast worden om relevante gegevens te verzamelen via bv. de CoAP server in elke node, of door de data rechtstreeks uit te lezen uit UDP pakketten.

3.2.5

Cf CoAP Client

Voor het opvragen en wijzigen van de parameters in het sensornetwerk spreken we de CoAP Erbium server aan in elke udp-sender node (zie sectie 3.1.3). Hiervoor hebben we een CoAP client nodig, waarmee ge¨ınterageerd kan worden vanuit Java.

3.3 Integratie onderdelen

33

Het Californium (Cf) CoAP framework[16, 20] biedt hier een ideale oplossing voor. Californium (Cf) is een modulaire CoAP implementatie geschreven in Java, dat o.a. toelaat om op een eenvoudige manier server en client applicaties te schrijven. We passen in het bijzonder het cf-client voorbeeld aan om de client module CfClient.java te schrijven. Hoofdzakelijk voegen we functionaliteit toe waardoor het antwoord van de server op een GET request niet alleen geprint wordt, maar ook meegegeven wordt na het oproepen van de methode. Ook wordt het optreden van een time-out gemeld, zodat we een manuele retransmit van de nieuwe parameterwaarde kunnen uitvoeren op een later tijdstip.

3.2.6

Verwerken gegevens

Om het evalueren van het algoritme eenvoudig te maken, zullen we de gegevens verzameld tijdens de test run exporteren in een handig formaat. Per episode printen we een aantal gegevens af naar een tekstbestand, met als delimiter het karakter “:”. De episodes worden gescheiden door een newline (“\n”). Zo kunnen we per episode de volgende gegevens bijhouden: state, volgende state, gemiddelde RDC, aantal verloren pakketten, basis- en rewardfuncties, . . . Ook wordt er algemene informatie meegegeven, zoals een herhaling van de gemaakte keuzes door de gebruiker. Het gebruik van een delimiter verzekert een gemakkelijke verwerking van de gegevens in bijvoorbeeld Microsoft Excel.

3.3 3.3.1

Integratie onderdelen Verloop test run

In deze sectie zullen we het verloop van een test run beschrijven. Vooreerst zetten we het scenario op (beschreven in sectie 3.1) in Cooja. Vervolgens maken we maken een connectie met de border router in de udp-sink, en we configureren 2 netcat connecties op de host, die de input van de udp-sink naar tekstbestanden print (count.txt: het totale aantal ontvangen pakketten, en seqno.txt: het laatst ontvangen sequence number van elke node). We laten de CollectView applicatie draaien om de RDC percentages te berekenen. Deze applicatie is immers zodanig aangepast dat de updates voor de RDC grafiek (Figuur 3.2) ook weggeschreven worden naar een tekstbestand RDC.txt.

3.3 Integratie onderdelen

34

We kunnen het netwerk dan simuleren (default state 0), en op elk moment de NegotiationEngine opstarten. De nodige input is beschikbaar via de tekstbestanden op de host, en de output wordt correct gerouteerd via de border router in de root udp-sink. Bij het opstarten van de Negotiation Engine kunnen enkele parameters ingesteld worden (zie sectie 3.2.3), waarna de main loop begint.

3.3.2

Uitbreidingsmogelijkheden

Bij het verloop van de implementatie werd er aandacht besteed aan de algemeenheid van de oplossing. De Negotiation Engine werd modulair ge¨ımplementeerd, zodat dit gemakkelijk kan uitgebreid worden naar grotere netwerken met meer nodes. De keuze voor het RL LSPI algoritme laat toe om de oplossing gemakkelijk uit te breiden naar meerdere parameters, en meerdere discrete waardes, zonder een al te groot verlies aan performantie (zie ook sectie 5.2). De specifieke protocolkeuzes zoals voorgesteld in deze thesis kunnen eenvoudig aangepast worden. Zo kan de CoAP client ingewisseld worden voor bv. een HTTP client, door de relevante server te draaien op de nodes, en een gepaste client toe te voegen (i.p.v. de Cf CoAP client, zie sectie 3.2.5). Om een parameter te veranderen in een ander protocol dient het volgende te gebeuren: • Er moet een getter-setter gedefinieerd worden in de broncode van het protocol (sectie 3.1.2); • Er moet een resource toegevoegd worden in de Er CoAP server (sectie 3.1.3); • Het verwerken van de gegevens dient aangepast te worden in measurements.java (sectie 3.2.6).

EVALUATIE NEGOTIATION ENGINE

35

Hoofdstuk 4

Evaluatie Negotiation Engine 4.1

Testen basisscenario

4.1.1

Basisalgoritme – RDC

Om de werking van het algoritme te bestuderen, is het leerzaam om elke feature eerst apart te testen. In deze sectie testen we een basisscenario met 12 udp-senders, die elke 60–62s een pakket versturen naar de sink. De Negotiation Engine gebruikt episodes van ongeveer 200 pakketten, waarin hij gegevens verzamelt zoals uiteengezet in sectie 3.3. Op het einde van elke episode wordt er een beslissing genomen voor de volgende state, waarna deze verdeeld wordt over het netwerk. Na deze disseminatie wordt er gewacht met een volgende meetcyclus gedurende 6 minuten. In de rewardfunctie Rtotal wordt er enkel rekening gehouden met de energiefeature (basisfunctie φ0 ), of dus: Rtotal = Rlif etime . Als doelstelling nemen we RDCgoal = 1%. Voor de exploratiefactor werd er gekozen voor  = 0.7, hetgeen garandeert dat er regelmatig (30% van de gevallen) at random wordt gekozen. De gemiddelde RDC waardes per episode van de nodes in een test run met 43 volledige episodes (in totaal 14949 pakketten verstuurd) zijn te zien in Figuur 4.1. Het algoritme kiest consequent voor states 0 en 3, de states met een channel check rate van 8Hz. De waarde voor ETX ALPHA heeft geen invloed op de beslissing (in state 0 heeft deze parameter de waarde 90, in state 3 de waarde 65). De verdeling van de states is te zien in Figuur 4.2. We zien dat het algoritme nadeel ondervindt tijdens de iteratie over alle states, en dat dit effect

4.1 Testen basisscenario

36

Figuur 4.1: RDC waardes (%) i.f.v. episode. Test run waarbij enkel rewards toegekend worden voor lage RDC waardes.

een tijd nodig heeft om uit te doven. Het algoritme convergeert terug naar de laagste RDC waarde, zoals we verwachten. In 4 episodes werd er een random state gekozen (volgens het epsilon-greedy mechanisme) met channel check rate 16Hz, en dit heeft een negatieve invloed op de RDC waardes, hoewel het effect minder uitgesproken is (state 2 werd gekozen in episodes 10, 14, 32 en 39). Om het algoritme te evalueren op basis van de RDC, kunnen we het experiment herhalen met dezelfde settings, echter zonder de state te veranderen. Eerst veronderstellen we dat de designer state 0 gekozen heeft, en dus de channel check rate heeft vastgelegd op 8Hz. We laten het algoritme lopen, echter zonder dat de state verdeeld wordt over het netwerk. We bereiken dit door de PUT commando’s te vervangen door GET requests, waardoor er nog steeds periodes plaatsvinden waar er CoAP verkeer aanwezig is (waarna er een pauze plaats vindt van 6 minuten voor het aanvatten van een nieuwe episode). Hierdoor komen de usecases in beide scenario’s zoveel als mogelijk overeen en kunnen we relevante conclusies trekken uit de vergelijking van beide test runs. Het resultaat op de gemiddelde RDC is te zien in Figuur 4.3. We zien dat dit resultaat beter is dan hetgeen we bekomen met het werkend algoritme. Door direct de “juiste” keuze te maken, convergeert de RDC snel naar een lage waarde, nl. 0.889%. Deze waarde is ook lager dan wat we kunnen bereiken met het volledig algoritme. De gemiddelde waarde over 43 episodes voor het basisalgoritme is 1.149%, terwijl dit voor het ideale geval (constante state 0) 0.912% is. Dit betekent een relatief verlies in performantie van 20.63% in

4.1 Testen basisscenario

37

Figuur 4.2: State i.f.v. episode. Test run waarbij enkel rewards toegekend worden voor lage RDC waardes.

Figuur 4.3: RDC waardes (%) i.f.v. episode. Channel check rate vastgelegd op 8Hz (state 0).

extra radio-on tijd. Vervolgens voeren we hetzelfde experiment uit (23157 verzonden pakketten, 62 episodes), ditmaal met de channel check rate gekozen op 16Hz (state 1). Hier heeft de designer de “foute” keuze gemaakt (op basis van de features die we geselecteerd hebben). De gemiddelde RDC waardes per episode zijn te zien in Figuur 4.4. We zien dat de RDC waardes hoger liggen dan bij het gebruik van state 0, en belangrijker, ook hoger dan bij het gebruik van het basisalgoritme. De gemiddelde RDC over 43 episodes is hier 1.516%. Het basisalgoritme biedt hier een relatieve winst van 31.94%. Deze resultaten worden samengevat in Tabel 4.1

4.1 Testen basisscenario

38

Figuur 4.4: RDC waardes (%) i.f.v. episode. Channel check rate vastgelegd op 16Hz (state 1).

RDC

Relatieve winst

Algoritme

1.149

-

Statisch State 0

0.912

20.63%

Statisch State 1

1.216

-31.94%

Tabel 4.1: Resultaten (in RDC en relatieve winst t.o.v. het algoritme) van test runs met het algoritme, statisch state 0 en statisch state 1. Enkel rewards toegekend voor RDC.

4.1.2

Basisalgoritme – Throughput

Nu zullen we de werking van de throughput feature bestuderen, en de energiefeature negeren. We behouden de settings van het basisalgoritme uit sectie 4.1.1, maar ditmaal houden we enkel rekening met de packetlossfeature (basisfunctie φ1 ), of dus: Rtotal = Rloss . We nemen als doelstelling throughputgoal = 95%, hetgeen neerkomt op ongeveer 10.5 verloren pakketten bij 200 ontvangen pakketten. De pakketverlies waardes per episode met 119 volledige episodes (in totaal 38874 pakketten verstuurd) zijn te zien in Figuur 4.5. Het algoritme verkiest hier over het algemeen states 0 en 1, beide met een ETX ALPHA waarde van 90. De verdeling van de states is te zien in Figuur 4.6. In het netwerk met state 0 zijn er echter 2 episodes waar er zeer veel pakketverlies optreedt, nl. 116 en 60 pakketten in respectievelijk episodes 59 en 102. In beide gevallen reageert het algoritme met een overgang naar state

4.1 Testen basisscenario

39

1, waarna het pakketverlies terug drastisch daalt.

Figuur 4.5: Packet loss waardes i.f.v. episode. Test run waarbij enkel rewards toegekend worden voor hoge throughput.

Figuur 4.6: State i.f.v. episode. Test run waarbij enkel rewards toegekend worden voor hoge throughput.

Het gemiddeld pakketverlies in een bepaalde state wordt getoond in Figuur 4.7. In de gehele test run gaan er gemiddeld genomen 5.55 pakketten verloren per episode (episode duur is ong. 200 ontvangen pakketten). Dit betekent een throughput van 97.3%. We kunnen dit opnieuw vergelijken met het klassieke, statisch gedefinieerde scenario. Hiervoor initialiseren we het netwerk eerst in de gewenste state, waarna het algoritme zoals normaal verloopt om meetgegevens te verzamelen. We vervangen echter opnieuw de CoAP PUT commando’s door GET commando’s, zodanig dat de usecase gelijkaardig blijft (episodes waarin metingen uitgevoerd worden, regelmatig gevolgd door periodes waarin er CoAP trafiek optreedt).

4.1 Testen basisscenario

40

Figuur 4.7: Packet loss waardes i.f.v. state. Test run waarbij enkel rewards toegekend worden voor hoge throughput.

Eerst zullen we veronderstellen dat de ontwerper de “juiste” keuze maakt (op basis van de throughput), en het netwerk initieert in state 1. Hiertoe voeren we een test run uit met 137 episodes, waarvan het resultaat te zien is in Figuur 4.8. We zien dat we een zeer hoge thoughput bekomen, die relatief stabiel blijft. Gemiddeld genomen gaan er 1.82 pakketten verloren per episode. Dit komt neer op een throughput van 99.1%.

Figuur 4.8: Packet loss waardes i.f.v. episode. Netwerk in state 1 (Channel Check Rate 16Hz, ETX ALPHA 90).

Vervolgens vergelijken we dit met een “foute” keuze (opnieuw op basis van de throughput) van de designer, bijvoorbeeld state 3. Het resultaat van een test run met 141 episodes wordt getoond

4.1 Testen basisscenario

41

in Figuur 4.9. Dit resultaat is niet alleen beduidend slechter dan de statische, “juiste” keuze, maar ook slechter dan het resultaat dat we bekomen met de Negotiation Engine. Gemiddeld genomen verliezen we 10.01 pakketten per episode. Dit komt neer op een throughput van 95.2%.

Figuur 4.9: Packet loss waardes i.f.v. episode. Netwerk in state 3 (Channel Check Rate 8Hz, ETX ALPHA 65).

Opnieuw zien we dat het algoritme een verbetering biedt t.o.v. een statische implementatie met een “foute” keuze, maar uiteraard wel een verminderde performantie vertoont t.o.v. een statisch ideaal geval. Deze resultaten worden nog eens samengevat in Tabel 4.2 Verloren pakketten

Throughput

Algoritme

5.55

97.3%

Statisch State 1

1.82

99.1%

Statisch State 3

10.01

95.2%

Tabel 4.2: Resultaten (in aantal verloren pakketten en throughputpercentage) van test runs met het algoritme, statisch state 1 en statisch state 3. Enkel rewards toegekend voor throughput.

4.1.3

Volledig basisscenario

In deze sectie zullen we de performantie bestuderen van het volledige algoritme. We volgen dezelfde werkwijze als in secties 4.1.1 en 4.1.2, maar ditmaal zullen we beide incentives even

4.1 Testen basisscenario

42

zwaar laten doorwegen in Rtotal , m.a.w. we kiezen C = 1 2

× Rlif etime +

1 2

1 2

in vergelijking (3.1), of dus: Rtotal =

× Rloss .

We voeren een test run uit met in totaal 212 episodes, opnieuw met dezelfde parameters als in secties 4.1.1 en 4.1.2 ( = 0.7, RDCgoal = 1%, throughputgoal = 95%). De verdeling van de states is te zien in Figuur 4.10. We zien dat state 1 het meest gekozen wordt, gevolgd door state 0. States 2 en 3 worden zelden gekozen. Het algoritme wisselt dus af tussen een channel check rate van 8Hz (state 0) en 16Hz (state 1), maar prefereert sterk een ETX ALPHA waarde van 90 (states 0 en 1). Een gedetailleerd overzicht per state is te zien in Tabel 4.3. Het hoge pakketverlies in state 0 is mede te verklaren door een eenmalige piek in verlies in episode 51, waarin er 151 pakketten verloren gaan.

Figuur 4.10: Verdeling van de states in een test run met 212 episodes. Gelijk gewicht van beide incentives (verbruikte energie en pakketverlies).

Episodes

RDC

Verloren pakketten

State 0

71

1.313

9.11

State 1

80

1.368

7.7

State 2

32

1.343

14.19

State 3

29

1.339

13.03

Tabel 4.3: Gedetailleerd overzicht van het aantal episodes doorgebracht in elke state, en de gemiddelde performantie per state

4.1 Testen basisscenario

43

Deze piek zou kunnen optreden door een tijdelijk verlies van een geldig pad in RPL, en duren tot alle paden terug hersteld zijn (verder onderzoek is hiervoor nodig). Het algoritme reageert door de state een tijdlang niet te kiezen, maar omdat er met meerdere vorige states rekening wordt gehouden, wordt de state niet compleet uitgesloten. Ook kan de state nog gekozen worden door de random exploratie. In deze test run bekomen we een gemiddelde RDC van 1.34%, en we verliezen gemiddeld 9.88 pakketten per episode. We kunnen dit opnieuw vergelijken met een statische keuze. Op basis van de verdeling van de states (Figuur 4.10), kiezen we voor het beste geval statisch state 1, en voor het slechtste geval state 3 (test runs met resp. 212 en 192 episodes). De resultaten worden samengevat in Tabel 4.4. Packet loss waardes fluctueren vaak tussen episodes onderling (o.a. ten gevolge van het RPL algoritme), de RDC waardes convergeren naar het gemiddelde toe. Voor de volledigheid werden ook test runs uitgevoerd met statisch state 0 en state 2, met resp. 209 en 207 episodes. Merk op dat deze resultaten ook verschillen met eerder bekomen resultaten: hier is state 0 veruit de beste keuze, terwijl dit verschil in een vorige test run (Tabel 4.1) heel wat kleiner was. Ook is het verschil met state 3 opmerkelijk, aangezien beide states een wake-up frequency hebben van 8Hz, voorheen waren states 0 en 3 op vlak van RDC zeer gelijkend (zie bv. de keuzes van het algoritme in Figuur 4.2).

RDC

Verloren pakketten

Algoritme,  = 0.7

1.34%

9.88

Statisch State 0

0.88%

1.81

Statisch State 1

1.51%

1.97

Statisch State 2

1.76%

15.04

Statisch State 3

1.23%

15.60

Algoritme,  = 1

1.32%

2.43

Tabel 4.4: Resultaten (gemiddelde RDC en gemiddeld aantal verloren pakketten per episode) van test runs met het algoritme (met en zonder exploratie), en met statische states.

4.1 Testen basisscenario

4.1.4

44

Kost CoAP update periode

Zoals eerder vermeld, wordt de nieuwe state verdeeld in het netwerk d.m.v. CoAP berichten. In deze periode sturen we een PUT request naar elke node, met daarin de nieuwe waarde van de parameter. Na het afhandelen van deze request (na een timeout, of na het ontvangen van een ACK) wachten we 10 seconden. Requests worden herhaald tot er een ACK ontvangen is van elke node. Deze extra trafiek zal leiden tot een verhoogde radio-activiteit, en dus ook tot energieoverhead. In deze sectie zullen we deze overhead proberen inschatten. In eerste instantie bepalen we de gemiddelde lengte van de updateperiode. Dit kunnen we eenvoudigweg bepalen in Java met de functie System.currentTimeMillis(). We printen de lengte van dit updateinterval uit naar de resultaten. In een test run met 135 episodes ( = 0.7) doorlopen we 64 updaterondes, met een gemiddelde lengte van 238 seconden. Om het effect op de RDC in te schatten, zullen we nu tijdens deze updateronde de gemiddelde RDC opmeten, en uitprinten naar de resultaten. Indien we de RDC opmeten tijdens het updateinterval (6 minuten wachttijd niet meegerekend), zien we dat het effect niet zo groot is. In een test run met 486 episodes, krijgen we een gemiddelde RDC van 1.287383% tijdens een meetperiode, en dit stijgt gemiddeld met 0.000922% tijdens een updateinterval. Dit is een relatieve stijging met slechts 0.07%. We schatten de overhead op vlak van energie dus laag in. In deze analyse is er echter geen rekening gehouden met het effect op de CPU. De overheadkost situeert zich vooral in de extra interferentie die gegenereerd wordt. In dezelfde test run vergelijken we de throughput van UDP trafiek tijdens de meetperiodes en updateperiodes; we verkrijgen slechts 88.08% throughput tijdens de updateperiode, tegenover 94.62% tijdens de meetperiode. Hierbij werd de 6 minuten wachttijd wel meegerekend. De usecase zal dus ofwel rekening moeten houden met extra interferentie en pakketverlies tijdens de updateperiodes, ofwel zal de reguliere trafiek tijdens de updateperiode verminderd (of gestopt) moeten worden.

4.1.5

Besluit

We zien dat we met het algoritme een tradeoff kunnen bereiken tussen een goed passende set parameters en een set minder goed passende parameters. De ontwerper dient enkel de incentives voor het netwerk mee te geven bij het opstarten ervan, en het algoritme verandert de state

4.1 Testen basisscenario

45

op basis van de gemeten waardes. We zien dat we aanvaardbare resultaten krijgen, die beantwoorden aan de incentives. We stelden als doelen voorop om een RDC van 1% te krijgen, en gemiddeld ongeveer 10.5 verloren pakketten per episode, en we bekomen een RDC van 1.34% en gemiddeld 9.88 verloren pakketten. Door af te wisselen tussen de states, bereikt het netwerk hier een evenwicht tussen beide incentives (zie Tabel 4.4). Voor een statisch scenario (zoals het basisscenario er grotendeels een is), kunnen we vermoeden dat het optimaler is om een kleinere exploratiefactor te gebruiken, of deze te laten verminderen in de tijd. We verwachten immers dat de performantie van elke state niet veel zal veranderen in de tijd. Om dit te valideren, zullen we de test run uit sectie 4.1.3 herhalen, ditmaal met  = 1, of dus zonder random exploratie, met 240 episodes. De gemiddelde RDC waardes en het gemiddeld aantal verloren pakketten per episode zijn weergegeven in Tabel 4.4. De verdeling van de states is te zien in Figuur 4.11. We zien dat het algoritme resoluut kiest voor state 1, na een 40tal episodes in state 3.

Figuur 4.11: State i.f.v. episode. Test run zonder random exploratie ( = 1).

Voor een statisch scenario verwachten we dat het gebruik van random exploratie een nefaste invloed heeft op de performantie, en dit vermoeden wordt bevestigd door de resultaten. Voor de ontwerper van een netwerk zal de keuze van een correcte  waarde dus zeer belangrijk zijn. We zien dat de performantie van het algoritme voor een statisch scenario grotendeels voldoet aan onze verwachtingen. Nu zullen we het algoritme uittesten op een nieuw scenario, waarin de omstandigheden veranderen, om te testen hoe goed het algoritme omgaat met een veranderende omgeving, en wat het effect is op de performantie t.o.v. een statisch netwerk.

4.2 Testen geavanceerde scenario’s

4.2

46

Testen geavanceerde scenario’s

4.2.1

Mogelijke scenario’s

Om een dynamisch scenario op te stellen, dienen we een usecase te vinden waarvan de performantie voldoende verschilt van het standaardscenario. Hiervoor zijn er enkele opties, die we in de volgende secties zullen bespreken. Vooreerst kunnen we interferentie introduceren, in de vorm van additionele motes die niet-gerelateerde trafiek uitsturen. Een andere mogelijkheid is om de nodes vaker pakketten te laten versturen. Ten slotte kunnen we de nodes mobiel maken.

4.2.2

Scenario met interferentie

Vooreerst kunnen we een disturber mote introduceren ergens in het netwerk. Dit is een standaard application mote type, dit wil zeggen dat deze mote enkel op applicatie niveau gesimuleerd wordt. De code hiervoor is dan ook in java geschreven, ContikiOS wordt niet gesimuleerd zoals dat wel het geval is bij andere motes. De broncode /tools/cooja/java/se/sics/cooja/motes/ DisturberMoteType.java bevat een klasse DisturberMoteType, waarin er continu pakketten gestuurd worden, met een instelbare delay en duration. De beschrijving van deze disturber mote is als volgt: /∗ ∗ ∗ Simple a p p l i c a t i o n −l e v e l mote t h a t p e r i o d i c a l l y t r a n s m i t s ∗ dummy r a d i o p a c k e t s on a l l r a d i o c h a n n e l s ( −1) , ∗ i n t e r f e r i n g a l l s u r r o u n d i n g r a d i o communication . ∗ ∗ This mote t y p e a l s o implements t h e mote f u n c t i o n a l i t y ∗ (” mote s o f t w a r e ” ) , and can be used as an example o f ∗ i m p l e m e n t i n g a p p l i c a t i o n −l e v e l mote . ∗ ∗ @see D i s t u r b e r M o t e ∗ @author F r e d r i k O s t e r l i n d , Thiemo V o i g t ∗/ @ C l a s s D e s c r i p t i o n ( ” D i s t u r b e r mote” ) @AbstractionLevelDescription (” Application l e v e l ”)

4.2 Testen geavanceerde scenario’s

47

Standaard zijn deze delay en duration waardes ingesteld als volgt: private f i n a l s t a t i c long DELAY = S i m u l a t i o n . MILLISECOND/ 5 ; private f i n a l s t a t i c long DURATION = 10∗ S i m u l a t i o n . MILLISECOND ; die in de volgende functie gebruikt worden: public void s e n t P a c k e t ( RadioPacket p ) { /∗ Send a n o t h e r p a c k e t a f t e r a s m a l l pause ∗/ g e t S i m u l a t i o n ( ) . s c h e d u l e E v e n t (new MoteTimeEvent ( this , 0 ) { public void e x e c u t e ( long t ) { /∗ l o g g e r . i n f o (” Sending a n o t h e r r a d i o p a c k e t on c h a n n e l : ” + r a d i o . g e t C h a n n e l ( ) ) ; ∗/ r a d i o . s t a r t T r a n s m i t t i n g P a c k e t ( r a d i o P a c k e t , DURATION) ; } } , g e t S i m u l a t i o n ( ) . g e t S i m u l a t i o n T i m e ( ) + DELAY) ; } Het gebruik van een standaard disturber mote heeft echter tot gevolg dat de interferentie totaal is, zowel in de TX range (afstand tot mote waarin zijn pakketten correct kunnen ontvangen worden) als in de INT range (afstand tot mote waarin er interferentie optreedt ten gevolge van het versturen van pakketten). Dit betekent dat de motes in deze ranges geen pakketten meer kunnen ontvangen. Deze standaard disturber mote kunnen we dus niet gebruiken in het scenario. We kunnen de disturber mote nu aanpassen zodanig dat de DELAY waarde ge¨ınitialiseerd wordt op bv. 1 seconde. We plaatsen de mote nabij de sink, zodat er regelmatig interferentie optreedt voor alle trafiek. Gedetailleerde resultaten zijn te zien in Tabel 4.5 (merk op dat er 2 episodes optreden met een piek in pakketverlies, beide in state 1: episodes 192 en 264, met resp. 166 en 113 verloren pakketten). We zien dat states 2 en 3 relatief gezien interessanter worden op vlak van energieverbruik, hoewel er nog steeds teveel pakketverlies optreedt.

4.2.3

Verhogen packet sending rate

We kunnen de usecase ook aanpassen zodanig dat er meer trafiek gestuurd wordt. Hiertoe passen we de packet sending rate aan, die bepaald wordt in de code \examples\thesis\

4.2 Testen geavanceerde scenario’s

48

Episodes

RDC

Verloren pakketten

State 0

89

1.337

6.36

State 1

112

1.352

7.42

State 2

51

1.346

10.94

State 3

40

1.338

12.95

Tabel 4.5: Gedetailleerd overzicht van het aantal episodes doorgebracht in elke state, en de gemiddelde performantie per state, voor een test run met 1 disturber mote (delay 1s) rpl-collect-separatesink\collect-common.c: /∗ Send a p a c k e t e v e r y 60−62 s e c o n d s . ∗/ e t i m e r s e t (& p e r i o d t i m e r , CLOCK SECOND∗PERIOD ) ; while ( 1 ) { PROCESS WAIT EVENT ( ) ; i f ( ev == PROCESS EVENT TIMER) { i f ( data == &p e r i o d t i m e r ) { e t i m e r r e s e t (& p e r i o d t i m e r ) ; e t i m e r s e t (& w a i t t i m e r , random rand ( ) %(CLOCK SECOND∗RANDWAIT) ) ; } e l s e i f ( data == &w a i t t i m e r ) { if ( send active ) { /∗ Time t o send t h e d a t a ∗/ collect common send ( ) ; } } } } Deze PERIOD constante is dus gedefinieerd op 60. We zullen nu een test run van 232 episodes uitvoeren met PERIOD 15. Gedetailleerde resultaten zijn te zien in Tabel 4.6. Het valt op dat de RDC waarde voor state 1 lager ligt dan voor state 0, waar dit in andere tests omgekeerd is. Dit kan mogelijks verklaard worden door de toegenomen interferentie, waarbij het continu opnieuw verzenden van pakketten leidt tot een langere radio-on tijd. In zo’n geval zou het uiteindelijk beter kunnen zijn om de wake-up frequency hoger te maken, niet alleen voor de throughput,

4.2 Testen geavanceerde scenario’s

49

maar ook voor de totale radio-off tijd. Opnieuw zien we dat een ETX ALPHA waarde van 65 vermeden wordt. Door de grotere frequentie van UDP trafiek, merken we ook een grotere last in de updateperiods. De throughput daalt van 95.72% naar 88.58%, en de RDC stijgt met 0.0026%, hetgeen toch een relatieve stijging betekent van 12.22%. De throughput ondervindt een gelijkaardige daling als bij het basisscenario, maar er wordt wel meer energie verbruikt in een updateperiod. Episodes

RDC

Verloren pakketten

State 0

88

2.174

6.02

State 1

90

2.149

5.74

State 2

18

2.181

18.89

State 3

36

2.167

26.47

Tabel 4.6: Gedetailleerd overzicht van het aantal episodes doorgebracht in elke state, en de gemiddelde performantie per state, voor een test run met een hogere packet sending rate.

4.2.4

Scenario met mobiele nodes

Een andere mogelijke usecase is om de nodes mobiel te maken. Hiervoor kunnen we in Cooja gebruik maken van de Mobility plugin[30]. Deze plugin verwerkt een tekstbestand (positions.dat) waarin de positie over de tijd staat voor elke node in de simulatie (met spaties als delimiters). De plugin kan op elk moment gestart worden vanuit Cooja, waarbij het tijdstip t = 0s in positions.dat gelijkgesteld wordt aan de huidige simulatietijd. Indien het eind van de positie-data bereikt wordt, reset de tijd, en worden de posities herhaald. Een voorbeeld van een eenvoudige positions.dat bestand is als volgt: #NodeID time [ s ] X p o s i t i o n [m] Y p o s i t i o n [m] 0 0 . 0 2 4 2 . 8 3 1 8 4 0 1 −88.93434686 1 0 . 0 2 0 5 . 7 6 4 5 1 3 4 −62.43874048 2 0 . 0 2 5 0 . 5 1 8 6 4 8 6 −59.24201654 0 1 . 0 2 4 3 . 8 3 1 8 4 0 1 −87.93434686 1 1 . 0 2 0 6 . 7 6 4 5 1 3 4 −61.43874048

4.2 Testen geavanceerde scenario’s

50

2 1 . 0 2 5 1 . 5 1 8 6 4 8 6 −58.24201654 Dit bestand zou kunnen gebruikt worden voor een simulatie met 3 nodes (NodeIDs 0, 1 en 2) die na een seconde een meter naar rechts opschuiven (Xposition + 1), en een meter naar boven (Yposition - 1). Na deze seconde bewegen de nodes terug naar hun originele positie (zoals opgegeven bij t = 0s). Dit wordt herhaald tot de plugin afgesloten wordt. We testen de Mobility plugin met een positions.dat bestand waarin we zowel de Xposition als de Yposition laten verschillen met een willekeurige afstand x ∈ Z : −3 ≤ x ≤ 3, per seconde, voor t = 0s tot t = 10s. We zien echter dat we de nodes niet zo bruusk kunnen laten bewegen, aangezien er teveel pakketten verloren gaan. Dit betekent dat het verdelen van de state te traag verloopt, door de vele CoAP timeouts (slechts 22 episodes na ongeveer 24u simulatie). We kunnen de nodes echter ook langzamer laten bewegen. We maken hiertoe een positions.dat bestand waarin we de zowel de Xposition als de Yposition laten verschillen met een willekeurige afstand x =

y 10

: y ∈ Z : −10 ≤ y ≤ 10, per seconde, voor t = 0s tot t = 40s. We kiezen als

incentives opnieuw een gemiddelde RDC van 1%, en gemiddeld ongeveer 10.5 verloren pakketten per episode. De resultaten van een test run met 195 episodes zijn weergegeven in Tabel 4.7. Episodes

RDC

Verloren pakketten

State 0

99

1.24%

6.18

State 1

56

1.29%

3.27

State 2

18

1.25%

21.06

State 3

22

1.24%

17.14

Tabel 4.7: Resultaten (aantal episodes doorgebracht in de state, gemiddelde RDC en gemiddeld aantal verloren pakketten) van een test run met mobiele nodes.

We zien ditmaal een voorkeur voor state 0. Gezien we als doelstellingen 1% RDC en 95% throughput vooropstelden (ongeveer 10.5 pakketten verloren per episode), wordt er vaker gekozen voor de energie-effici¨entere state 0, waarbij we iets meer pakketverlies moeten aanvaarden. Dit gedrag is mogelijk door onze keuze voor exponentieel stijgende, uitdovende, genormaliseerde rewardfuncties (zie sectie 3.2.2), en is conform de doelstellingen opgegeven door de ontwerper.

4.3 Vari¨erende scenario’s

51

De states met ETX ALPHA = 65 worden opnieuw niet gekozen, wegens teveel pakketverlies, hoewel we wel merken dat de gemiddelde RDC relatief gezien verbetert. Een gedetailleerdere analyse van RPL met mobiliteitsaanpassingen is te lezen in [25]. We kozen hier voor een ETX ALPHA waarde van 65, maar het blijkt dat we hiermee geen betere resultaten behalen in dit mobiliteitsscenario.

4.3 4.3.1

Vari¨ erende scenario’s Inleiding

In deze sectie zullen we het gedrag van het algoritme bestuderen bij vari¨erende scenario’s. Hiertoe zullen we het scenario laten vari¨eren in de tijd, door te starten in het basisscenario (sectie 4.1), en na een tijd over te gaan naar een geavanceerd scenario (sectie 4.2).

4.3.2

Vari¨ erend scenario met mobiliteit

We zullen het gedrag bestuderen van een usecase waarin de nodes eerst statisch zijn, en na een tijd mobiel worden (zoals beschreven in sectie 4.2.4). Hiertoe voeren we een test run uit met 350 episodes, met statische nodes in de eerste 153 episodes, en mobiele nodes in de rest van het scenario (197 episodes). We zullen bestuderen hoe het algoritme reageert op deze verandering. We nemen opnieuw dezelfde parameters aan:  = 0.7, RDCgoal = 1%, throughputgoal = 95% en C = 21 . In de eerste 153 episodes zien we dat het algoritme sterk state 0 prefereert, aangezien zowel de gemiddelde RDC als het gemiddeld aantal verloren pakketten optimaal zijn in deze state. De resultaten zijn opgelijst in Tabel 4.8. In episodes 154-350 zien we dat de gemiddelde RDC stijgt, en dat state 1 interessant wordt. Ondanks het feit dat er in de eerste 153 episodes sterk werd gekozen voor state 0, zien we dat het algoritme de state regelmatig aanpast naar state 1. Dit kunnen we inderdaad zien op Figuur 4.12, waarin we de states zien i.f.v. de episode, voor episodes 50-250. Na episode 154 (gemarkeerd), zien we dat het algoritme vaak overschakelt op state 1. Verder verkrijgen we ook significant slechtere resultaten in state 3, deze state wordt dan minder gekozen (zie ook Figuur 4.12). De resultaten van episodes 154-350 zijn opgelijst in Tabel 4.9.

4.3 Vari¨erende scenario’s

52

In episode 269 zien we een zeer hoge piek in het pakketverlies, met 170 verloren pakketten. Dit heeft tot gevolg dat het algoritme overschakelt op state 3 voor de volgende paar episodes, waarin er slechts 8 en 11 pakketten verloren gaan. In episode 272 zien we echter opnieuw een piek in het pakketverlies, ditmaal gaan er 184 pakketten verloren. Daarna wordt er gekozen voor state 1, en pas na een tijd opnieuw voor state 0 (episode 285). De gekozen state i.f.v. de episode is te zien in Figuur 4.13. Statische nodes

Episodes

RDC

Verloren pakketten

State 0

80

1.184%

2.65

State 1

19

1.196%

5.79

State 2

22

1.207%

14.45

State 3

32

1.209%

6.84

Tabel 4.8: Resultaten (aantal episodes doorgebracht in de state, gemiddelde RDC en gemiddeld aantal verloren pakketten per episode in de state) van episodes 1-153.

Mobiele nodes

Episodes

RDC

Verloren pakketten

State 0

93

1.2525%

4.57

State 1

69

1.2519%

3.52

State 2

19

1.2578%

13.84

State 3

16

1.2566%

27.25

Tabel 4.9: Resultaten (aantal episodes doorgebracht in de state, gemiddelde RDC en gemiddeld aantal verloren pakketten per episode in de state) van episodes 154-350.

We zien hier opnieuw pieken in het pakketverlies. Het algoritme reageert door de betrokken state een tijdlang niet te kiezen, maar het optreden van een eenmalig extreem verlies in performantie leidt niet tot het volledig negeren van deze state. Dit valt te verklaren door het gebruik van een exploratiefactor, en door de werking van het RL-LSPI algoritme, waarin er rekening wordt gehouden met meerdere episodes uit het verleden. Het algoritme kan zich aanpassen aan veranderende omstandigheden, en blijkt toch nog resistent tegen eenmalig optredende factoren.

4.3 Vari¨erende scenario’s

Figuur 4.12: State i.f.v. episode, episodes 50-250. Episode 154 is gemarkeerd.

Figuur 4.13: State i.f.v. episode, episodes 260-300. Episodes 269 en 272 zijn gemarkeerd.

53

CONCLUSIE EN VERDER ONDERZOEK

54

Hoofdstuk 5

Conclusie en verder onderzoek 5.1

Bereikte doelstellingen

Zoals uiteengezet in sectie 1.2, wilden we een zelf-lerend netwerk opstellen, dat op basis van incentives ingegeven door de ontwerper, zelf de beste keuze maakt, gelet op de omgeving. Hiertoe ontwikkelden we een Negotiation Engine, die m.b.v. RL-LSPI het zelflerend algoritme implementeert, en via CoAP communiceert met het sensornetwerk. De Negotiation Engine kiest tussen 4 states: 2 parameters uit 2 verschillende protocollen (RPL en ContikiMAC), elk met 2 mogelijke discrete waardes. Ook stelden we een scenario op in Cooja waarop we de Negotiation Engine konden testen. Dit alles wordt beschreven in hoofdstuk 3. Merk op dat de implementatie bewust algemeen is gekozen, zodat het relatief evident is om uit dit werk een nieuwe implementatie te maken, met bv. andere protocollen om te optimaliseren, meerdere states, andere manieren om gegevens op te vragen en uit te wisselen, . . . Ook kozen we voor Cooja, omdat deze een zeer accurate emulatie toelaat van sensornodes en een model van het radioverkeer met interferentie implementeert[12]. In hoofdstuk 4 evalueerden we tenslotte de Negotiation Engine, zowel op het basisscenario als op enkele geavanceerde scenario’s. Indien de ontwerper een doordachte keuze van de parameters en hun waardes maakt, zien we dat het algoritme over het algemeen een aanvaardbare tradeoff realiseert tussen de keuzes, met een goede performantie. De overheadkost blijkt relatief beperkt op vlak van radio-off tijd (en dus ook op vlak van energieverbruik), maar er treedt wel significant meer pakketverlies op door de interferentie die gegenereerd wordt door de updates. De usecase zal hier dus ofwel rekening mee moeten houden (door bv. de trafiek te verminderen of te stoppen

5.2 Verder onderzoek

55

tijdens updateperiodes), ofwel moet de random exploratie verminderd worden, zodat er minder updateperiodes optreden. De keuze die we maakten voor de wake-up frequency (8Hz en 16Hz) blijkt goed te zijn, waarbij beide waardes gekozen worden, afhankelijk van de incentives die we voorop stelden. Onze keuze voor ETX ALPHA (90 en 65) blijkt minder optimaal voor de scenario’s die we testten. We verwachtten dat de optie ETX ALHPA = 65 een valabele optie zou zijn voor mobiele nodes[25], maar dit blijkt niet het geval. Verder onderzoek zou deze mobiliteitsresultaten kunnen verbeteren, zie sectie 5.2.2. De sterkte van het zelflerend algoritme is echter dat deze foute keuze niet leidt tot een slecht performerend sensornetwerk. De Negotiation Engine kan aldus het werk van de ontwerper vereenvoudigen, indien hij bereid is om een mindere performantie t.o.v. een statisch, ideaal scenario kunnen aanvaarden. De ontwerper kan zich focussen op de correcte protocollen, en een aantal realistische discrete waardes voor de parameters. Ook zien we dat het netwerk zich kan aanpassen aan veranderende omstandigheden, hetgeen een manuele opvolging van het sensornetwerk minder nodig maakt. Samen met het eenvoudiger ontwerpen ervan, lijkt dit een aanzet tot een behoorlijke kostvermindering voor draadloze sensornetwerken, door het verminderen van het manuele ontwerp– en opvolgwerk.

5.2

Verder onderzoek

Deze thesis biedt een aanzet tot een volledig autonoom zelflerend sensornetwerk. Er is echter nog veel ruimte tot verder testen, en vele mogelijkheden voor uitbreidingen. In deze sectie zullen we een overzicht geven van mogelijk verder werk.

5.2.1

Real-life scenario

Een van de sterktes van Contiki is de simulator die aangeboden wordt: Cooja[12]. Deze voert immers een gedetailleerde emulatie uit van de hardwareplatformen waarop Contiki gedraaid wordt (i.t.t. een applicatiemote, zoals de Disturber Mote, zie sectie 4.2.2), en gebruikt een eenvoudig radiomodel met interferentie. Uiteraard kan deze simulator niet volledig conform de werkelijkheid zijn.

5.2 Verder onderzoek

56

Een logische verdere stap is dan ook het uittesten van de Negotiation Engine in een real-life scenario. Deze stap kan, mits enkele aanpassingen, eenvoudig gezet worden m.b.v. de oplossing zoals deze is voorgesteld in deze scriptie. De Negotiation Engine zou kunnen draaien op een aparte server, die via tunslip in contact staat met de udp-sink (zie sectie 3.1.6). In dit geval zal de virtuele tun interface verbonden worden met de seri¨ele poort, waar de udp-sink aan verbonden wordt. In een real-life scenario kunnen we geen gebruik meer maken van de CollectView tool, daarom zullen we de RDC waardes moeten berekenen uit de UDP pakketten die naar de sink gestuurd worden, analoog zoals in de CollectView tool zelf gebeurt (en zoals we het aantal verloren pakketten rechtstreeks schatten uit de sequence numbers).

5.2.2

Verdere testmogelijkheden

De Negotiation Engine kan ook verder getest worden, zowel met de huidige protocollen, als met fundamenteel andere. In deze sectie geven we een aantal mogelijkheden. Een eerste optie is om andere scenario’s te testen, zowel in software, als in hardware. Mogelijke scenario’s kunnen bijvoorbeeld andere interfererende nodes bevatten, of een andere usecase draaien (ander type trafiek, andere incentives, . . . ). Verder kunnen er andere protocollen geselecteerd worden, of kan er ge¨experimenteerd worden met andere parameters. Rekening houdende met recent onderzoek van het gedrag van RPL in mobiliteitsscenario’s[25], zou de NegotiationEngine getest kunnen worden met een beter mobiliteitsscenario. Het zou interessant zijn om bv. het DIS (DODAG Information Sollicitation) broadcast interval of de ETX ALPHA waarde aan te passen at runtime, en de performantie ervan te vergelijken met een statische keuze. Het zelfregulerend gedrag zou hier een groot voordeel moeten bieden, aangezien het gedrag in een mobiel scenario sneller kan veranderen. Ook kan de impact van bepaalde parameters in de Negotiation Engine zelf onderzocht worden, zoals de wachttijd tussen een updateperiode en een periode waarin metingen worden uitgevoerd, en de invloed ervan op de metingen. Hier namen we statisch een bepaalde waarde (6 minuten). Een andere mogelijkheid zou zijn om de metingen te hervatten indien we de invloed van de meetperiode zien dalen (bv. nadat we een bepaalde throughput threshold bereiken, zie sectie 4.1.4).

5.3 Conclusie

5.2.3

57

Uitbreidingen Negotiation Engine

De Negotiation Engine zelf kan ook nog uitgebreid worden, om meerdere states toe te laten, met bv. meer paramaters, of meer discrete waardes voor de parameters. Een continu bereik toelaten is echter minder evident. Er kan echter wel een tussenweg gezocht worden, door enkel het aantal mogelijke waardes vast te leggen. Indien het algoritme resoluut kiest voor een welbepaalde waarde, kan het bereik van waardes aangepast worden naar een kleiner bereik, zodanig dat het algoritme de parameter kan finetunen. Zo zouden we een interessant parameterinterval kunnen vinden, en dan verfijnen tot de beste waarde door “in te zoomen” op dit interval. Verder zijn er ook betere opties voor random exploratie. In deze scriptie nemen we een vaste kans op een random state, hoewel aangetoond is dat dit in statische scenario’s leidt tot een verlies in performantie (sectie 4.1.5). Een betere methode is om deze kans afhankelijk te maken van de vorige gemeten performantie van de state. In ander werk[24] werd er gekozen voor een dergelijke state switch functie: P = Qα log Q. Hoe hoger de Q-waarde, hoe meer kans dat deze state gekozen wordt. De parameter α kan gekozen worden afhankelijk van de usecase (zie [24]). Dergelijke verbeteringen in de Negotiation Engine kunnen ge¨ıncorporeerd worden in de implementatie zoals deze uiteengezet is in deze scriptie.

5.3

Conclusie

In deze scriptie stelden we een systeem voor, waarbij de ontwerper de MAC– en routeringsprotocollen selecteert, met de parameters die getuned moeten worden. Ook geeft hij de doelstellingen mee voor het netwerk. De Negotiation Engine, die op een aparte server draait, kiest de volgende state op basis van de doelstellingen en de feedback uit het netwerk. Dit bevrijdt de ontwerper van een groot deel van het manueel uittesten van het netwerk. Ook kan het netwerk zich aanpassen aan veranderende omstandigheden, zonder dat er manuele herconfiguratie aan te pas moet komen. Dit alles verlaagt de kostprijs van het ontwikkelen en onderhouden van een draadloos sensornetwerk. De overheadkost hierbij is een mogelijk mindere performantie t.o.v. een ideale, statische keuze (indien die bestaat), en periodes waarin er extra configuratietrafiek plaatsvindt. Deze overheadkost lijkt zich vooral te situereren in extra interferentie (met een lagere throughput in deze periode tot gevolg), en een eerder beperkte verhoging in het energieverbruik. Dit systeem is zeer modulair, en kan dan ook aangepast worden naar nieuwe protocollen, of met

5.3 Conclusie

58

een nieuwe methode van gegevens verzamelen en verspreiden, zoals eerder beschreven werd. Uiteraard is het werk nog niet af. Het systeem kan nog op vele manieren getest en uitgebreid worden. We maakten dan ook een aantal suggesties voor verder onderzoek. De simulatieresultaten zijn echter veelbelovend, en de overhead kost is niet afschrikkend. De implementatie zoals voorgesteld in deze thesis zou een stap vooruit kunnen betekenen in de ontwikkeling van een volledig autonoom, zelf-lerend sensornetwerk.

BIBLIOGRAFIE

59

Bibliografie [1] http://www.contiki-os.org , geraadpleegd op 18/05/2013 [2] http://www.zolertia.com/products/z1 , geraadpleegd op 18/05/2013 [3] Akkaya, K. and Younis, M. (2005). A survey on routing protocols for wireless sensor networks. Ad Hoc Networks, 3:325–349. [4] Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., and Cayirci, E. (2002). Wireless sensor networks: a survey. Computer Networks, 38:393–422. [5] Buettner, M., Yee, G. V., Anderson, E., and Han, R. (2006). 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. ACM. [6] El-Hoiydi, A., Decotignie, J.-D., Enz, C., and Le Roux, E. (2003). Poster abstract: wisemac, an ultra low power mac protocol for the wisenet wireless sensor network. In Proceedings of the 1st international conference on Embedded networked sensor systems, SenSys ’03, pages 302–303, New York, NY, USA. ACM. [7] Polastre, J., Hill, J., and Culler, D. (2004). Versatile low power media access for wireless sensor networks. In Proceedings of the 2nd international conference on Embedded networked sensor systems, SenSys ’04, pages 95–107, New York, NY, USA. ACM. [8] Demirkol, I., Ersoy, C., and Alagoz, F. (2006). Mac protocols for wireless sensor networks: a survey. IEEE Communications Magazine, 44(4):115–121. [9] Mulligan, G. (2007). The 6lowpan architecture. In Proceedings of the 4th workshop on Embedded networked sensors, EmNets ’07, pages 78–82, New York, NY, USA. ACM.

BIBLIOGRAFIE

60

[10] Dunkels, A. (2011). The contikimac radio duty cycling protocol. [11] Dunkels, A., Eriksson, J., Finne, N., and Tsiftes, N. (2011). Powertrace: Network-level power profiling for low-power wireless networks. SICS Technical Report T2011:05. ¨ [12] Osterlind, F., Dunkels, A., Eriksson, J., Finne, N., and Voigt, T. (2006). Cross-level sensor network simulation with cooja. In Proceedings of the First IEEE International Workshop on Practical Issues in Building Sensor Network Applications, SenseApp ’06, Tampa, Florida, USA. [13] Forster, A. (2007). Machine learning techniques applied to wireless ad-hoc networks: Guide and survey. [14] Kaelbling, L. P., Littman, M. L., and Moore, A. W. (1996). Reinforcement learning: a survey. Journal of Artificial Intelligence Research, 4:237–285. [15] Kovatsch, M., Duquennoy, S., and Dunkels, A. (2011). A low-power coap for contiki. In Proceedings of the 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2011), Valencia, Spain. [16] Kovatsch, M., Mayer, S., and Ostermaier, B. (2012). Moving application logic from the firmware to the cloud: Towards the thin server architecture for the internet of things. In Proceedings of the 6th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS 2012), Palermo, Italy. [17] Lagoudakis, M. G. and Parr, R. (2001). Model-free least squares policy iteration. Technical report, Advances in Neural Information Processing Systems. [18] Langendoen, K. (2008). Medium access control in wireless sensor networks. In Wu, H. and Pan, Y., editors, Medium Access Control in Wireless Networks, pages 535–560. Nova Science Publishers, Inc. [19] Meier, A., Woehrle, M., Zimmerling, M., and Thiele, L. (2010). Zerocal: Automatic mac protocol calibration. In DCOSS, pages 31–44. [20] Pauli, D. and Obersteg, D. I. (2011). Californium. Lab Thesis. [21] Watkins, C. and Dayan, P. (1992). Q-learning. Machine Learning, 8(3):279–292.

BIBLIOGRAFIE

61

[22] Wang, P. and Wang, T. (2006). Adaptive routing for sensor networks using reinforcement learning. In Proceedings of the Sixth IEEE International Conference on Computer and Information Technology, CIT ’06, pages 219–, Washington, DC, USA. IEEE Computer Society. [23] Rovcanin, M., De Poorter E., Moerman I., Demeester P. (2012). An LSPI based reinforcement learning approach to enable network cooperation in cognitive wireless sensor networks. [24] Rovcanin, M., De Poorter E., Moerman I., Demeester P. (2013). Reinforcement Learning as a viable method to cope with the ever-increasing complexity of wireless network configurations. Submitted to EURASIP Journal on Wireless Communications and Networking. [25] Carels, D., De Poorter E., Moerman I., Demeester P. (2013). Extending the IETF RPL routing protocol with mobility support. In preparation for Ad Hoc Networks journal. [26] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, J., and Alexander, R. (2012). RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks. RFC 6550 (Proposed Standard). [27] http://datatracker.ietf.org/wg/roll/charter/ , geraadpleegd op 18/05/2013 [28] Tsiftes, N., Eriksson, J., and Dunkels, A. (2010). Low-power wireless ipv6 routing with contikirpl. In Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks, IPSN ’10, pages 406–407, New York, NY, USA. ACM. [29] Shelby, Z., Hartke, K., Bormann, C., and Frank, B. Constrained Application Protocol (CoAP) draft-ietf-core-coap-07 Technical Report, IETF Secretariat, Fremont, CA, USA, July 2011. [30] http://contikiprojects.svn.sourceforge.net/viewvc/contikiprojects/ , geraadpleegd op 18/05/2013