Throughput and delay optimization on IEEE 802.15.4e networks

(1)

List of Figures

1.1 The Internet of Thing vision . . . 2

1.2 Number of worldwide connected devices . . . 3

1.3 Wireless Sensor Network . . . 4

1.4 The typical architecture of the sensor node . . . 4

1.5 6LoWPAN protocol stack . . . 6

1.6 IEEE802.15.4 PHY layer . . . 8

1.7 Superframe structure . . . 10

1.8 Slot frame structure . . . 11

1.9 Data frame and ACK transmission within a timeslot . . . 11

1.10 Example of schedule with 16 channels and 31 time slot . . . . 13

2.1 Network topology . . . 15

2.2 System Model . . . 16

3.1 Big-O complexity . . . 21

3.2 Matching graph . . . 22

3.3 Scaled value using rank scaling . . . 27

3.4 Dierence between rank and top scaling . . . 27

3.5 Stochastic selection of a single individual . . . 28

3.6 Roulette wheel approach: based on tness . . . 29

3.7 Crossover operation . . . 30

3.8 Scattered crossover . . . 31

3.9 Single point crossover . . . 31

3.10 Two point crossover . . . 31

3.11 Genetic Algorithm Flowchart . . . 33

4.1 Throughput vs nodes . . . 47

4.2 Throughput vs Population Size . . . 48

4.3 Throughput vs Pairing . . . 48

4.4 Throughput vs Mutation . . . 49

4.5 Iteration vs Nodes . . . 51

4.6 Average throughput with dierent algorithm . . . 51

(3)

List of Tables

1.1 Products energy consumption . . . 5

1.2 Multiple PHY layers . . . 7

3.1 Hungarian Algorithm . . . 23

3.2 Genetic Algorithm Example . . . 34

4.1 Optimization GA . . . 38

4.2 Simulation GA . . . 46

(4)

(5)

Introduction

With the consistently growing impact of the Internet on everyday tasks and the increasing of diversity in connected devices, the topic Internet of Things (IoT) has nowadays gained relevant interest. The IoT describes a scenario in which not only personal computers and smartphones are interconnected, but everyday things are transformed into smart objects that can communicate and react to their environment [1].

This thesis focuses on the area of Wireless Sensor Networks (WSN), which describes an even more specic subset of the IoT and often show traits from both of the above movements. Wireless sensor networks have attracted great attention in recent years by several research groups and companies, especially because in view of the their exibility alongside combined with the wide variety of application scenarios in which they can be used.

However, they are characterized by some aspects that dier signicantly from traditional computer networks: rstly, the power supply of nodes, which consists mainly of batteries, lack needs special attention to energy eciency, secondly, since wireless communication used used in dierent environments and it utilizes antennas with limited power and coverage range, failure s or loss of connectivity. are more likely to happen. Finally, the limited computing and storage resources available at the nodes, do not allow the use of common protocols and applications.

To address these problems, several solutions have been proposed by vari-ous standards bodies. One of the leading standard is IEEE.802.15.4e, which is an improvement of the previous standard (made in 2011), used to dene the MAC layer and physical layer of the protocol stack. This presents the Time Slotted Channel Hopping (TSCH) which has gained popularity among various companies since it improves the reliability of the network nodes with the use of ultra-low power consumption nodes.

The robustness of the network and has sensibly improved and the eects of interference and multipath fading has reduced thanks to the use of the time synchronization and the ability of the channel hopping.

The thesis introduces the scheduling problem as throughput maximiza-tion and delay minimizamaximiza-tion problem. The throughput maximizamaximiza-tion prob-lem is a binary integer linear programming probprob-lem that has been solved in this work through dierent heuristic algorithm (Hungarian algorithm and

(6)

Genetic algorithm):

The scheduling problem as a multiobjective optimization, is also de-scribed. In this case optimal decisions need to be taken in the presence of trade-os between the average throughput of the network and the delay suered by a packet travelling through the network.

The rest of the thesis is organized as follow:

The Chapter 1 describes the state of the art. We introduce the concepts of Internet of things, Wireless Sensor Network, and it shows the structures of sensor nodes that will build up the proposed network. Then we go for a overview of the standard IEEE802.15.4 making a brief summary of how the standard has changed over the years and introduced various specic. At the end we relates our work to the current state of the art.

The Chapter 2 introduces the new proposed system model and it de-scribes the problems formulation.

The Chapter 3 explains the various algorithms used; A brief introduction describes the theory of graphs and the features Hungarian algorithm and the Genetic algorithm. . T he latter, is described in more details, highlighting all its dierent options and specifying the dierent phases in the iterative algorithm operation.

The Chapter 4 presents the implementation and evaluation details. The multi-objective optimization the results of simulations are showed.

(7)

Chapter 1

State of art

1.1 Internet of Things

The rst who introduced the term "Internet of Things" was Kevin Ashton from the MIT Auto-ID Center, in 1999, that used this phrase to describe the chain connection of Radio Frequency Identiers (RFID) in a network [2]. Soon after the idea has spread to all common objects, ranging from mobile phones, personal health devices and home automation, to industrial automation, smart metering and environmental monitoring systems. Finally, in 2013, the Global Standards Initiative on Internet of Things (IoT-GSI) dened the IoT as "the infrastructure of the information society."[3].

The vision behind the Internet of Things is that embedded devices, also called smart objects, are universally becoming IP enabled. For this reason, the impact of Internet of Things will be signicant, with the potential of trillions of devices becoming IP-enabled [4].

From the gure we can see how Internet of Things ts into the existing structure: the core Internet consists of all those nodes, it is estimated ap-proximately one million nodes, which form the Internet backbone and which hardly suer changes; the peripheral part, called fringe Internet, is consti-tuted by all the devices used at personal level; because its size depends on the number of users using these devices to connect to the Internet. The latest announcements speak of more than 1.5 billion of nodes in this part of the Internet.

The last piece, the newest, is the one regarding the Internet of Things, sometimes called embedded fringe, which as we have already said, is the network of physical devices, vehicles, buildings and other items [5]. One of the major confusions about IoT lies in understanding what the "things" are. Coetzee & Eksteen (2011) state that the denition of "things" in IoT is enormously wide and includes a variety of physical elements. The list includes personal gadgets that we take with us all day, like: smartphones, tablets, smart watches and digital cameras.

(8)

Figure 1.1: The Internet of Thing vision

According to the authors, the elements in our environment will be added to this list whether at home, car, oce or restaurants. To be dened as a "thing", that can be connected to the internet, they need a way to be bridged to the connection. Objects with Radio Frequency Identication (RFID) tags, other types of wireless sensors, are so far the biggest foundation of things in IoT.

1.1.1 Requirements of Internet of Things

The requirements of the Internet of Things dierentiate from the current use of PCs, laptops, smart phones and other peripherals connected to the Internet.

• Firstly, the individual bandwidth requirement per device is low, as most devices will only collect and send sensory data, or receive actu-ating data [First requirements];

• Secondly, IoT devices do not require a user interface as what is nor-mally expected when working with connected devices. Rather, IoT devices are capable to function and make decisions without human intervention. Devices may collect data, the data might be then pro-cessed by some application and a suitable action could then be executed accordingly to some pre-congured algorithm or self learned pattern recognition software.

• Thirdly, the scale of the Internet of Things will be much greater than that of current connected devices, which will require an Internet back-bone capable of handling a large amount of devices. The size of the

(9)

1.2. WIRELESS SENSOR NETWORK 3 Internet of Things is growing exponentially, and the studies of the Cisco Internet Business Solutions Group (IBSG) have suggested that, start-ing from 14.4 billion nodes in 2014, we can arrive in 2020 to 50.1 billion nodes [Thirdly requirements]. In fact, it has already far exceeded the size of the rest of the Internet. Obviously, this is due to the "objects" connection that does not depend directly by users. In fact, Google recently announced the passing of a trillion unique Internet URLS.

Figure 1.2: Number of worldwide connected devices

1.2 Wireless Sensor Network

A Wireless Sensor Networks (WSN) usually consists of a number of battery powered sensor and actuator devices, which are typically constrained in terms of storage and processing power. Wireless communication has the advantage of being easy to implement in already constructed buildings, as it requires no extra installation of wires.

A Wireless Sensor Network (WSN) is usable in various applications such as home automation and the monitoring of animal, vegetation, machine and car. The home automation applications stretch from alarm systems and damage monitoring to ventilation control and sprinkler systems.

A WSN often contains a bridging unit, a gateway, to which all infor-mation is sent from control and/or sensor nodes. The main function of the nodes is to monitor and measure the environment as well as control electron-ics that interfere with the environment, for instance heat, motion or smoke detectors, cameras and lamp controllers. From the gateway the retrieved

(10)

data is sent via a wireless communication link to an external controlling unit, for example a Central Monitoring Station (CMS), a server and/or an-other collector/distributor of information, such as a user mobile phone or tablet, see Figure 4 for an overview. The topology of the WSNs can vary from a simple star network to an advanced multi-hop wireless mesh network [6].

Figure 1.3: Wireless Sensor Network

1.3 Sensor Node

This enormous growth has been possible through the use of low-power wire-less devices with limited processing capabilities; a sensor node, also known as mote, is a node in a sensor network that is capable of performing some processing, gathering sensory information and communicating with other connected nodes in the network [7]. As we can see from Figure 1.4, typi-cally a mote is composed of one or more sensors, a microcontroller and a transceiver, a power unit and an external memory.

(11)

1.3. SENSOR NODE 5 • Controller: central part of the node, controls and manages the op-erations due to other components. Its use is preferred to that of a microprocessor, for both the low costs that for low energy consump-tion.Those used in our laboratory, which also are very widespread in the commercial, are the OpenMote Cc2538, which uses a 32-bit pro-cessor at 32Mhz and the Atmel SAMr21 that uses a 32-bit propro-cessor operating at 48 MHz [8],[9];

• Transceiver:The transceiver is responsible for a part of the entire node radio. In most cases it uses the ISM band, Which gives free radio spectrum allocation and global availability. Among the possible choices, the most used frequencies are around 2.4 Ghz, because coincide with the requirements of the most common standard (IEEE.802.15.4). There are three possible states in which one can nd the microcon-troller: "sleep" in which we have the lowest energy consumption, where the node switch o the radio (the one consuming more); "Idle", but it is preferable to avoid this state since the energy consumption is some-times equal to that which it has when it is in a state of reception; "Active" in which you have the transmission or reception of packets from neighboring nodes. Table 1.1 lists data sheet numbers from dif-ferent vendors;

Table 1.1: Products energy consumption

Vendor Product Transmit

current[mA] current[mA]Receive

OpenMote Cc2538 24.9 19.1

Atmel SAMr21 15.3 12

Microchip MRF24J40 23 19

Ember EM357 27.5 25

• External memory: Rarely present, since the energy consumption by an external memory, would be to strongly aect the total consumption of the node, which must be as low as possible;

• Power source: The low power consumption of a sensor node is the main challenge regarding their implementation. Very often, given the diculty or impossibility of achieving these nodes, it is necessary that the batteries will last for the duration required for performing the func-tion by the node. A much debated issue is to nd new sources of energy from the environment, so as to recharge the batteries and increase more and more the life of the node[10].

• Sensor: To acquire the information to be processed and sent to the neighbors, each node must have one or more sensors. They dier from

(12)

each node, depending on the network needs. They are hardware devices that produce a measurable response to a change in a physical condition like temperature, sound, pressure, humidity...

1.4 IEEE 802.15.4

To eciently interconnect these nodes, it is necessary to pay attention to some features: a low power communication stack, a highly reliable commu-nication stack and an Internet-enabled commucommu-nication stack [11]; given the need to create a communication protocol for systems having these charac-teristics, the standardization society (IEEE and IETF on all), have begun working groups [12],[13].

The IEEE 802.15.4 standard (Low Rate WPAN) is widely recognized as one of the most successful low-power technologies for low data rate but very long battery life (months or even years) and very low complexity. The standard denes both the physical (PHY) and data-link (MAC) layers of the OSI model. One of the big advantages of this protocol is that standardized and proprietary networks (or mesh) layer protocols run over 802.15.4-based networks, like ZigBee, 6LoWPAN, WirelessHART [14],[15],[16].

Since the protocol was used for short-range technologies, a task group was created in 2007 and formalizes an amendment, called IEEE 802.15.4a, which provided higher precision ranging and location capability (1 meter accuracy and better), higher aggregate throughput, adding scalability to data rates and lower power consumption and cost.The IEEE 802.15.4 oers three operational frequency bands centered in 2.4 GHz, 915 MHz and 868 MHz; three of these frequency bands are based on the Direct Sequence Spread Spectrum (DSSS) spreading technique, and one which used parallel-sequence spread spectrum (PSSS). Two options were included to the physical layer, a UWB Pulse Radio and a Chirp Spread Spectrum (operating in unlicensed 2.4 GHz spectrum) [17].

(13)

1.4. IEEE 802.15.4 7 Next, to improve the reliability and better support the proprietary of-ferings, it was also amended the MAC layer through the IEEE 802.15 Task Group 4e. With these changes, higher-level protocols owners, could use the proposed standard, completing the OSI model; the most important are 6LoWPAN as a convergence layer, ROLL RPL as a routing protocol, and CoAP allowed a good integration of networks into the Internet [18],[19],[20].

1.4.1 PHY layer

As we can see from Table 2 the current standard denes multiple PHY layers but the most widely used is the one operating in the 2.4 − 2.485GHz frequency band, a worldwide and unlicensed band.

Table 1.2: Multiple PHY layers PHY

option FrequencyBand [MHz] Chip Rate [kcps] Spreading Sequence length Number of se-quence Modulation Option 1 868-868.6 300 16 2 BPSK Option 2 902-928 600 16 2 BPSK Option 3 2400-2483.5 2000 32 16 O-QPSK

The chip sequences of each data symbol shall be modulated by using Oset-Quadrature Phase-Shift Keying (O-QPSK) with half-sine pulse shap-ing. To form the oset between I-phase and Q-phase chip modulation, the Q-phase chips (odd-indexed chips) shall be delayed by Tc with respect to the I-phase chips (even-indexed chips). Tc is the inverse of the chip rate (nominally 2.0Mchips/s), which is 32 times the symbol rate. Internally to the radio, every group of 4 bits of data sent for transmission are encoded as 32 chips ("physical bits") using a simple lookup table. From a user's perspective, the bitrate appears to be 250kbps, although internally 8 more chips are sent over a 2Mcps link.

Baseband chips are represented with a half-sine pulse shape described by equation (1.1): p(t) = ( sin(π_2Tt c) 0 ≤ t ≤ 2Tc 0 otherwise (1.1)

In the frequency range in which it operates, the standard denes 16 channels, away 5Mhz each from each other. The available bandwidth for each channel is 2 MHz, so that the n-th channel, does not interfere with the (n + 1)-th channel. Always to prevent interference, the channels are orthogonal to each other.

Each packet, or PHY protocol data unit (PPDU), contains a preamble, a start of packet delimiter, a packet length, and a payload eld, or PHY service data unit. The 32-bit preamble is designed for acquisition of symbol

(14)

(a) IEEE802.15.4e channel.

(b) PPDU format

Figure 1.6: IEEE802.15.4 PHY layer

and chip timing. The IEEE 802.15.4 payload length can vary from 2 to 127 bytes. This structure is shown in Fig 3:

• Synchronization Header (SHR): the synchronization header (SHR) consists of the preamble sequence followed by the start of frame delim-iter (SFD). The preamble sequence is dened to be 4 bytes (8 symbols) of 0x00. The SFD is one byte set to 0xA7. A synchronization header is always transmitted rst in all transmission modes since it enables the receiver to synchronize and to lock into a bit stream.

The circuitry in the receiver looks for a physical preamble to "lock onto". Once locked on, the receiver waits for the SFD, then for the length byte. It then lls a receive buer with the number of bytes indi-cated in the length byte, after which it can switch o. After successfully receiving a packet, the radio indicates reception to the micro-controller. • PHY Header (PHR): the frame length eld denes the number of bytes in the PSDU. Note that the length eld does not include the length eld itself. It does however include the frame check sequence (FCS) of the MPDU. The length eld is 7 bits in length and has a maximum value of 127. The most signicant bit in the length eld is reserved and has to be set to zero.

(15)

1.4. IEEE 802.15.4 9

1.4.2 MAC layer

The IEEE 802.15 Task Group 4e was chartered to dene a MAC amend-ment to the existing standard 802.15.4-2006. The intent of this amendamend-ment was to enhance and add functionality to the 802.15.4-2006 MAC to better support the industrial markets. Specically, 802.15.4e extends the previ-ous 802.15.4 standard by introducing MAC behavior modes: through time synchronization and channel hopping, it enables high reliability while main-taining very low duty cycles. Time Synchronized Channel Hopping (TSCH), is the latest generation of highly reliable and low-power MAC protocol, and thus very suitable for a protocol stack for IoT. The MAC protocol supports two operational modes:

• The non beacon-enabled mode: When the coordinator selects the non-beacon enabled mode, there are neither beacons nor superframes. Medium access is ruled by an unslotted CSMA/CA mechanism; • The beacon-enabled mode: In this mode, beacons are periodically

sent by the coordinator or router to synchronize nodes that are as-sociated with it, and to identify the PAN. A beacon frame delimits the beginning of a superframe dening a time interval during which frames are exchanged between dierent nodes in the PAN. Medium access is basically ruled by slotted CSMA/CA. However, the beacon-enabled mode also enables the allocation of contention free time slots, called Guaranteed Time Slots (GTSs) for nodes requiring guaranteed bandwidth.

The Carrier Sense Multiple Access Collision Avoidance (CSMA-CA) al-gorithm is used to avoid concurrent transmissions in wireless systems. Each time a device wants to transmit, it waits for a random time period (back-o ). After this back(back-o, the devices samples the channel. If the channel is empty, the device transmits its data; if the channel is busy, the device refrains from accessing the channel and waits for another backo interval. If no channel access is possible after (max) 5 retries, the MAC reports an error back to the upper layer. If the message was successfully sent, the following acknowledgement is sent without using CSMA-CA.

Beacon-enabled PANs use the slotted CSMA-CA version. The backo periods are aligned with the start of the beacon transmissions. If a device wants to access the channel during a CAP it waits for a random number of backo slots. If the channel is busy, the device waits for another random number of backo slots before trying to access the channel again. The CAP boundaries are included in the beacon frame, the devices listen for the beacon to align their backo periods to the start of it. In this mode, acknowledge-ments and beacon frames are sent without using CSMA-CA. The CSMA-CA parameters can be adjusted on the dierent layers with command frames.

(16)

Each coordinator denes a superframe structure Figure (Suerframe) which is constructed based on: the Beacon Interval (BI), which denes the time be-tween two consecutive beacon frames; the Superframe Duration (SD), which denes the active portion in the BI, and is divided into 16 equally-sized time slots, during which frame transmissions are allowed.

Figure 1.7: Superframe structure

The active portion of the superframe structure is composed of three parts, the Beacon, the Contention Access Period (CAP) and the Contention Free Period (CFP): the beacon frame is transmitted at the start of slot 0. It con-tains the information on the addressing elds, the superframe specication, the GTS elds, the pending address elds and other PAN related. The CAP starts immediately after the beacon frame and ends before the beginning of the CFP, if it exists. If a transmission cannot be completed before the end of the CAP, it must be deferred until the next superframe. The CFP starts immediately after the end of the CAP and must complete before the start of the next beacon frame or the end of the superframe. Transmissions are contention-free since they use reserved time slots (GTS) that must be pre-viously allocated by the coordinator or router of each cluster. All the GTSs that may be allocated by the coordinator are located in the CFP and must occupy contiguous slots. The CFP may therefore grow or shrink depending on the total length of all GTSs.

Slot Frame Time Synchronized Channel Hopping (TSCH) is the latest generation of highly reliable and low-power MAC protocol, but the rst to apply similar ideas to WSNs was a proprietary protocol called Time Syn-chronized Mesh Protocol (TSMP) [21]. In TSMP, nodes in the network are synchronized on a slotted time base. An individual timeslot is long enough for a sender to send a data frame, and for a receiver to acknowledge correct reception (a timeslot of 10 ms is common). L consecutive timeslots form a superframe, which repeats over time.

A TSCH schedule instructs each mote what to do in each timeslot: trans-mit, receive or sleep. As regards the transmission: if a node has a packet to transmit, it sends to its neighbor and waits for a return ACK; if you receive it, delete the package assuming that the transmission is successful. If does not receive it, he proceeds in the retransmission of the same packet (a given

(17)

1.4. IEEE 802.15.4 11

Figure 1.8: Slot frame structure

number of times), until it receives the ACK message.If the buer does should not be a queued packet, the node turns o the radio and goes in the "sleep" mode.

As regards the reception: shortly before the time when the node is ex-pected to receive the package, it put in the "listen" mode by turning on his radio. If it receives a packet, then sends an ACK to those who had sent him. If it do not receive anything within a certain time-out, turn o his radio and goes in a "sleep" mode; in this case, if there was an error when forwarding the packet, the non-arrival of the ACK to the sender, it would mean the need for retransmission.

Figure 1.9: Data frame and ACK transmission within a timeslot Scheduling Scheduling can be done either centrally or distributed manner:

Centrally mode: In this approach, we have a coordinator of the net-work, it is often the gateway node that connects the wireless sensor network to the Internet, who takes responsibility for managing the construction and maintenance of the network. To do so it needs, periodically, of the

(18)

informa-tion of the entire network: each node has to communicate to the coordinator which are the nodes close to him, and the amount of data that is planning to enter into the network. With this information, the coordinator draws the complete topology and organizes on the basis to the various needs, the graph of the connections between the various nodes.

Done this, it sends to all network components this graph, so that the various nodes can follow these guidelines. In the event of any change, each node should promptly inform the coordinator, which will change the topology of the network. For this, the centralized approach, it is very inconvenient for dynamic networks, as there would be a huge exchange of information only to draw the topology, and would also be very slow reconguration;

In contrast, it is very useful to optimize the scheduling, that a coordinator is aware of the network requirements and can meet them all. As we will see later, this will be the approach that will be used in our model.

Distribute mode: This approach, unlike the previous one, allows each node, locally, to make forwarding decisions for packets choose independently what should be the next hop. It tends to use this kind of approach when the network changes quickly, or when have so many nodes that have the gateway function to the outside.

Channel Hopping For each scheduled cell, the schedule species a slot number and a Ch.Oset (is a number that represents the value that give to each available channel (so in our case, using all available channels, will be equal to 16)). In a well-built schedule, when node A has a transmit cell to node B on Ch.Oset 5, node B has a receive cell from node A on the same Ch.Oset. The Ch.Oset is translated by both nodes into a frequency using the following function:

ActualChannel = F (ASN + Ch.Of f set)modN ch (1.2) where ASN = (K ∗ S + t) is the Absolute Slot Number (indicating the number of timeslots since the beginning of the network), S is the slotframe size, K is the slotframe cycle and t is the slot oset. The function F consists of a look-up table containing the set of available channels. The value Nch (the number of available frequencies) is the size of this look-up table.

This results in "channel hopping": even with a static schedule, pairs of neighbors "hop" between the dierent frequencies when communicating. A way of ensuring communication happens on all available frequencies is to set the number of timeslots in a slotframe to a prime number (other words, successive frames over a same link are sent over dierent physical frequencies in successive slotframe cycles k). Channel hopping is a technique known to eciently combat multi-path fading and external interference.

(19)

1.5. RELATED WORKS 13

Figure 1.10: Example of schedule with 16 channels and 31 time slot

1.5 Related Works

As we explained in the introduction, a TSCH network, can operate with a centralized scheduling (so the necessary information is sent to a sink, that manages the use of the links by the nodes), or distributed (in which each node applies distributed multi-hop scheduling protocols and neighbor-to-neighbor scheduling negotiation [22]).

The rst work, called Trac Aware Scheduling Algorithm (TASA) [23], who presented a proposal for a centralized scheduling, propose an innovative technique for building both a matching (set of edges without common vertex) and a vertex coloring (assignment of labels to elements of a graph subject to certain constraints) problem (in graph theory), based on the network topology and the trac load. This type of scheduling requires that the master node has complete topology information, so each node will send to the network coordinator the information about their neighbors and about the load of trac generated.

The coordinator thus know the graph G, the physical connectivity graph Pand the trac load generated by each node, and it can builds time/frequency patterns respecting low latency and low duty cycle at the same time.

Another centralized scheduling was proposed by Nirapai [24], in which it provides multi-channel utilization with intelligent controlling mechanism. In this process, each nodes performs frequency scanning at the x intervals, in order to detect currently available channels, then sends achieved information to the network coordinator. The exibility of the method proposed allows the system to have better system performance both in terms of average packet end-to-end delay and system throughput.

As a counterpart, some distributed approaches have also been studied. The function of uRes [25] is to establish and maintain the links with neighbor

(20)

and the computation and communication for link reservation just happen locally. There will be a negotiation between neighboring nodes and the available cells; these cells are assigned to minimizing the risk of collision, according to information received from the previous trading. Since collisions can still occur, they are resolved by re-allocating the colliding cells. uRes just ts to TSCH and provides exibility for further optimization and extension. In Wave [26], any node each node except the sink, needs to know some information: its parent and its children in the routing graph considered, the acknowledgment policy, the nodes that generate conicts with themselves and the trac demand of these nodes. Through this information Wave ensures the absence of conicting transmissions in the schedule provided, minimized data delays by reducing the number of slots assigned to nodes and the energy ecient because a node is awake only during its slots and the slots of its children in the routing graph.

Another distributed approach has been studied to arrive at the develop-ment of DeTAS [27]; this algorithm, through a small exchange of information between neighboring nodes, allows the construction of an optimum collision-free schedules in multi-hop TSCH networks. It also takes care to minimize the grow of the queue utilization, not to ll the memory buer, so as to avoid the risk of not being able to receive a packet in transit and avoiding trac congestion.

A new approach to scheduling was introduced by Orchestra [28], in fact this solution not involve any extra central entity, negotiation, signaling, nor multi-hop path reservation among nodes. Each node stores their own sched-ule locally, creating it through their Routing Protocol for Low-Power and Lossy Networks (RPL) neighbors and parents. The advantage in using this proposal, is that managing to not worsen the latency, or the energy demand, there is a marked improvement in reliability of the network.

In [29] Morell introduced a fair distributed scheduler and how the new idea of multiprotocol label switching can be mapped to LLNs to manage the network's schedule. This allocation scheme at the link level was introduced because it allows a correct distribution of end-to-end delay between nodes, and this produces a marked improvement in throughput to the network.

(21)

Chapter 2

System Model & Related Work

2.1 System Model

In order to study the behavior of our TSCH network, that is with the char-acteristics described in the previous chapter, we need to build a model that will consider three main features: a network model, an interference pattern, a model queue.

2.1.1 Network Model

As shown in the gure, we have modeled our network with a single access point (called the gateway), which will also be used to connect our TSCH network to the external world (ie the Internet).

Figure 2.1: Network topology

For this type of architecture, it is convenient to use a centralized way: the task of scheduling no longer falls on the shoulders of many nodes, but on the gateway whose main responsibility is scheduling and synchronization. The scheduler is able to compute the network path based on the network graph and applying computational constraints. The scheduler resides at the gateway and determines the allocation of time slots and with which frequency each node will transmit on.

(22)

The network will be modeled as a directed graph (a set of objects (called nodes) that are connected together, where all the edges are directed from one nodes to another) G = (V, E, d). V is the set of nodes including the sink (ie gateway). The total number of the nodes of the network is Nk, so

| V |= N_k, and the set will be described by V = {n0, n1, n2, ..., nN} where

1 ≤ k ≤ Nk− 1; nk will be each nodes in the network and n0 represents the

sink.

E is the set of links between the dierent nodes and d consist of a set of physical distances between each pair of adjacent nodes in the set. So, taking any two of the network nodes i and j, chosen from the Nk available, their physical distance will be equal to di,j. In this case too so | ei,j |= di,j, and

the set will be described by E = {e0,1, e0,2, ..., ei,j, ...}.

Figure 2.2: System Model

Each node, since it must be able to communicate with their neighbors, must have access to a radio. The antenna will be characterized by a certain communication range Ri. This value, given the particularities of a TSCH network with very small distances and limited energy, will be very low. Some that have been studied in particular detail are [30], [31].

To get a communication between two nodes, node j will not be further from the node i of the communication range; that is the transmission is successful if di,j ≤ Ri is satised. To see it in graphic way, I will have a

direct connection between the node ni and the node nj (therefore, as we can

see from the gure, an arrow will connect the two nodes), if di,j ≤ Ri and

i 6= j.

The nodes are managed by the gateway where each node in the network is synchronized. To do this, the sink node needs some information that periodically the various nodes are providing. This information is sent at beginning of slotframe. Each node sends its state to the gateway as [U, Q], where U represents a vector denoting the number of packets transmitted by nk, at frequency f (in TSCH network there are a total of 16 dierent

(23)

2.1. SYSTEM MODEL 17 frequencies, each corresponding to a dierent channel), in timeslot t. Q represents a vector denoting the number of packets in the buer of nk.

We assume a time-varying wireless channel between each node (sender and receiver). We denote by Ck,f,t as the channel capacity of link lk,f at

time t. For as we have just dened the vector U, we can dene Uk,f,t as the

maximum number of packets that can be transmitted over lk, f at time t.

Therefore Uk,f,t can be calculated as follows:

Uk,f,t= Ck,f,tT (2.1)

It's hard to measure this variable, what really we can calculate from the information that each node gives us (the couple who slotframe send to start the gateway), is the eective rate of lk,f,t if nk transmit at frequency f in

timeslot t. We denote it with Mk,f,t and we can be calculated as follows:

Mk,f,t= min{Uk,f,t, Qk} (2.2)

What the gateway want to get will be a scheduling decision vector, con-taining the necessary information (so what frequency and in which times-lot) to node ni to communicate with the node nj, and we denote with

~

x = [Xk,f,t, k ∈ {1, ..., Nk}; f ∈ {1, ..., F }; t ∈ {1, ..., S}].

The element Xk,f,t that make the vector, is a binary decision variable,

which is 1 if the nk node transmits in timeslot t at frequency f; nk is 0 if

the node is not transmitting and can turn o its radio (to optimize energy savings). Note that Xk,f,t is a function of the information available to nk,

so the gateway has no problem to calculate this variables.

2.1.2 Interference Model

The interference between two links in the network depends in the Interference model, and we use the proposed model [32],[33], in this thesis. As we did for introducing the network model, also in this case we dene an interference graph GI = (VI, EI); as before, VI will be the set of nodes that forming the

Network, EI will be the set of links that connect the various nodes.

This model helps us to consider two situations in which occurs an in-terference: when a node send and receive at the same time or when receive from multiple nodes at the same time. Consider a node ni, the transmission

of the node nj will interfere with the transmission of ni if

(the length of the line segment connecting them) between the node ni and

the node nj, and with ∆ > 0 we indicate a guard zone specied by the

(24)

channel at the same time. It also allows for imprecision in the achieved range of transmission [34].

As we said, we must respect two conditions to avoid cases of interfer-ence; therefore we will obtain the formulas that will form the equations of constraint for the optimization of which is covered later. The rst problem is that the node ni cannot receive from multiple nodes at the same time

X

Xi,j,t≤ 1 (2.4)

Also, a node nj cannot transmit and receive at the same time. That is,

if Xi,j,t= 1, then, Xj,p,t must be 0

Xi,j,t+

X

Xj,p,t ≤ 1 (2.5)

From a graphical point of view, it means that if a link li, j is used in a

certain time slot, then you can not use another link lj, p in the same time slot. The nodes in the interference graph corresponds to queues to which packets arrive according to a stochastic process at every time slot. A scheduling algorithm must pick an independent set of each slot such that neighbouring nodes will not be activated simultaneously.

2.2 Problem Formulation

In this section, we introduce the formulation of the problems for throughput maximization and delay minimization. In the next chapters, we argue about the algorithms and their eciency to solve the problems.

2.2.1 Throughput Maximization Problem

Referring to our network model, the throughput maximization problem is to nd the vector X so that each node of the network obtains a transmission schedule, which is the list of time slots and frequencies it could send packets such that the schedule is interference-free and the overall throughput of the network is maximized.

We must consider how physically structured network and avoid possible interference. Therefore, in addition to the objective function, we will have to insert in the formulation of our problem also of the conditions that satisfy the interference constraint.

Since we chose a centralized scheduling, such as initial data we have those that we can provide the gateway, then the complete network topology: Nk is the number of the nodes, F is the total number of the possible channels, S is the slotframe size and Mk,f,t already mentioned in the network model.

(25)

2.2. PROBLEM FORMULATION 19 max Nk X k=1 F X f =1 S X t=1 Xk,f,tMk,f,t (2.6) F X f =1 S X t=1 Xk,f,t≥ 1; ∀k ∈ {1, ..., Nk} (2.7) Xk,f,t+ Xk0_,f,t ≤; ∀k, k0 ∈ {1, ..., N_k}; k 6= k0; ∀f ; ∀t (2.8) Xk,f,t ∈ {0, 1}; ∀k ∈ Nk; ∀f ∈ F ; ∀t ∈ S (2.9)

In the formulation, the objective function in (2.6) maximize the total throughput of all nodes in TSCH network governed by the gateway. Con-straint (2.7) regards the physical condition, ensure that each node is assigned at least one time slot. If there is a need to ensure more bandwidth to a link, this can be done by putting more slots to that link which allows the need to send more packets inside the frame.

Constraint (2.8) is used to avoid collision. As we have seen in the inter-ference model, we must ensure that a node does not transmit and receive at the same time or receives from multiple nodes simultaneously, this con-straint assures that at most one user can transmit or receive in a certain slot and frequency oset. Constraint (2.9) indicate that the scheduling decision vector is a binary decision variable.

2.2.2 Delay Minimization Problem

Way as throughput, we formulate a scheduling problem in terms of latency minimization to minimize the average scheduling latency. Latency of a packet is an expression of how much time it takes for a packet of data to get from one designated point (in our case when it was generated by application) to another (when it's received at the destination).

(26)

The binary ILP formulation is: min Nk X k=1 F X f =1 S X t=1 αXk,f,tUk,f,t Nk X k=1 F X f =1 S X t=1 Xk,f,tUk,f,t (2.10) Nk X k=1 F X f =1 S X t=1 Xk,f,tUk,f,t > 0; ∀k ∈ Nk (2.11) F X f =1 S X t=1 Xk,f,t ≥ 1; ∀k ∈ {1, ..., Nk} (2.12) Xk,f,t+ Xk0_,f,t ≤; ∀k, k0 ∈ {1, ..., N_k}; k 6= k0; ∀f ; ∀t (2.13) Xk,f,t ∈ {0, 1}; ∀k ∈ Nk; ∀f ∈ F ; ∀t ∈ S (2.14)

Each Uk,f,t waits for t times when Xk,f,t=1 and the total time delay for

each packet amounts to α. The scheduling delay comprises of the number of time slots that a packet has to wait until its transmission. This includes: the queuing delay, that is the time the packet spends in routing queues, the transmission delay, that is the time it takes to push the packet's bits onto the link, the propagation delay that is the time for a signal to reach its destination; this also includes the channel switching latency when node switch channels during sensing period.

The total of the delay is denotes in the numerator of objective function (2.10).The only constraint that diers from those already seen and discussed, is the (2.11) that assures that at each frequency there is a packet ready to be sent. This constraint ensures that you can not fall into zero throughput.

(27)

Chapter 3

Optimization Algorithm

After formulating the throughput maximization problem and delay mini-mization problem, we have to deal with the resolution method. An algorithm is an eective method for calculating a function and is a self-contained step-by-step set of operations to be performed. The analysis of an algorithm is the determination of the amount of resources (such as time) necessary to execute them; our goal goes back is to solve the problems optimally in polynomial time.

The time complexity of an algorithm is commonly expressed using big O notation (used to classify algorithms by how they respond to changes in input size), and a polynomial time mean that the number of the step to performed the algorithm is O(nk₎_{, where n is the complexity of the input}

and k ≥ 0 is an integer.

Figure 3.1: Big-O complexity 21

(28)

Our idea is to transform the typical combinatorial optimization problem [44], in a graph-based heuristic algorithm, so to work with graph theory [45] and bring us back to a maximum weighted bipartite matching (MWBM) problem. After that, we adopt a greedy algorithm to the hope of nding a global optimum (greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time).

In this chapter, we review some preliminaries of MWBM and some greedy algorithm (Hungarian Algorithm and Genetic Algorithm); in the next instead we are going to apply these algorithms to our problems and we will see the computational costs and solutions under varying characteristics of these algorithms.

3.1 Bipartite Graph

In the eld of graph theory, a bipartite graph, is a graph whose vertices can be divided into two disjoint sets U and V ; a complete bipartite graph is a special kind of bipartite graph where every vertex of the rst set is connected to every vertex of the second set [46]. In a weighted bipartite graph, each edge has an associated value.

Let G = (U, V, E) be a weighted bipartite graph where U = {u1, u2, ..., unk}, V = {v1, v2, ..., vF ∗S} and E = {(u, v)|u ∈ U, v ∈ V } are the edges of G.

Edge has weight of ωij ≥, and this is not a loss of generality because we can

increase the weights of all edge of the amount of the one most negative, so as to make them all positive.

Given a graph G = (V, E), a matching M ⊂ G graph is a subgraph of a graph where there are no edges adjacent to each other. Simply, there should not be any common vertex between any two edges.

A matching M of a graph G is maximal if every edge in G has a non-empty intersection with at least one edge in M. In other world, a matching M of graph G is said to maximal if no other edges of G can be added to M.

(a) Maximal matching. (b) Maximum matching

Figure 3.2: Matching graph

A maximum matching is a matching that contains the largest possible number of edges. It is also known as largest maximal matching; maximum

(29)

3.2. HUNGARIAN ALGORITHM 23 matching is dened as the maximal matching with maximum number of edges. Note that every maximum matching is maximal, but not every max-imal matching is a maximum matching.

A perfect matching is a matching which matches all vertices of the graph. A matching of graph is said to be a perfect match, if every vertex of graph G is incident to exactly one edge of the matching M. Every perfect matching of graph is also a maximum matching of graph, because there is no chance of adding one more edge in a perfect matching graph. A maximum matching of graph need not be perfect.

A maximum weighted bipartite matching is dened as a matching where the sum of the values of the edges in the matching have a maximal value.

3.2 Hungarian Algorithm

The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time (it can achieve O(n3₎_{. To}

bet-ter explain the operation of the algorithm, usually resorts to an example: three workers (Oliver, Jack and Harry), must be allocated to three dierent jobs (computer programmer, webmaster and systems analyst); Each person will take a salary for each job and the goal is to nd the combination that minimizes the cost to complete all three works.

Table 3.1: Hungarian Algorithm

Computer Programmer Webmaster System Analist

Oliver 19e 38e 21e

Jack 21e 40e 13e

Harry 25e 44e 15e

The rst condition, veried in the example, is that the matrix is square, i.e. the number of rows must equal the number of columns. The Hungarian algorithm, modied gradually the matrix of costs through addition and sub-traction of constant of rows and columns. These updates of matrix of costs are made to always ensure no negative costs and, at the same time, trying to increase the null elements (and consequently the pairs of zero cost) up to reach the optimal solution, consisting precisely into n pairs of no cost.

Analyze the matrix of the costs (C) to nd the minimum value of each line, and subtracting that value to each element of the line; then I do the same step as regards the columns; in this way it updates the C matrix whose generic element now applies:

(30)

ci,j = ci,j− min ci,j; i = 1, ..., n (3.1)

ci,j = ci,j− min ci,j; j = 1, ..., n (3.2)

We will now determine the minimum number of lines (horizontal or ver-tical) that are required to cover all zeros in the matrix. If the number of lines required is lower than the size of the matrix, we continue with next step.

Oliver 0 0 2

Jack 8 8 0

Harry 10 10 0

First, we nd that the smallest uncovered number is 8. We subtract this number from all uncovered elements and add it to all elements that are covered twice. Again, we determine the minimum number of lines required to cover all zeros in the matrix. Now there are three lines required. Because the number of lines required equals the size of the matrix (n = 4), an optimal assignment exists among the zeros in the matrix. Therefore, the algorithm stops.

Oliver 0 0 10

Jack 0 0 0

Harry 2 2 0

The previous zeros cover an optimal assignment. This corresponds to the following optimal assignment in the original cost matrix: Oliver will do the Computer Programmer at the cost of 19 e, Jack will do the Webmaster at the cost of 40 eand Harry will do the System Analist at the cost of 15e. The total cost of this optimal assignment is to 19e + 40e + 15e = 74e.

3.3 Genetic Algorithm

In this section, we are going to list the characteristics of genetic algorithm and describe the various options of the algorithm's operations. In the next chapter we're going to evaluate the algorithm going to change the various options and seeing how they act on the nal result.

In articial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic opti-mization algorithm. A genetic algorithm (GA) is inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms.

(31)

3.3. GENETIC ALGORITHM 25 Since the eld of GA is inspired from the biological genetic evolution, the eld uses a number of biological metaphors in its terminology. Before proceeding with the explanation of how the algorithm works, it is necessary to introduce specic terminology [47]:

• Organism: it represents the entity being optimized; in our case, is the throughput of the network;

• Population: pool of individuals exhibiting equal or similar genome structures, which allows the application of genetic operators;

• Chromosome: an array of parameters or genes, that is passed to the cost function, thus represents a possible solution to the case under examination;

• Gene: it is the basic component that goes to form a chromosome, so it can represent every single feature of the problem studied (each chromosome can contain a number of genes);

• Allele: a specied set of alternatives for each gene, thereby specifying the allowable strings of genes (the possible chromosomes);

• Locus: it is the position on the chromosome containing a particular gene of interest.

In a genetic algorithm, a population of candidate solutions to an opti-mization problem is evolved toward better solutions. Each candidate solution has a set of properties which can be mutated and altered[48].

We use binary representation for individuals (bit strings of 1's and 0's). Bit strings have been shown to be capable of usefully code variety of informa-tion, and they have been shown to be eective representations in unexpected domains. [49]

3.3.1 Initialization

The rst step of the algorithm is to create an initial population. For research purpose, random initializing a population is suitable. The most commonly used mode that species the function that creates the initial population for genetic algorithm are three:

• Uniform: creates a random initial population with a uniform distri-bution;

• Feasible population: creates a random initial population that satis-es all bounds and linear constraints, so it creates many individuals on the boundaries of the constraint region, and creates a well-dispersed population;

(32)

• Non-linear feasible population: has the same operation as the pre-vious one, but it is used to create the population in the presence of non-linear constraint.

3.3.2 Fitness Function

It is used to evaluate the tness of the individuals in population (quality of the solutions). Better solutions will get higher score. Evaluation function directs population towards progress because good solutions (with high score) will be selected during selection process and pour solutions will be rejected. Many properties of evaluation function enhance or degrade a genetic al-gorithm's performance. One is normalization process used. Normalization is tness scaling (increasing the dierence between the tness values). As a population converges on a denitive solution, the dierence between tness values may become very small. Best solutions can't have signicant advan-tage in reproductive selection. For example, let us have scores 2 and 3. If these scores are used without any change as measures of each individual's t-ness for reproduction, it will take some time before the descendants of good individual will gain the majority in the population. Fitness scaling solves this problem by adjusting the tness values to the advantage of the most-t solutions.

Fitness scaling converts the raw tness scores that are returned by the tness function to values in a range that is suitable for the selection function. The selection function uses the scaled tness values to select the parents of the next generation. The selection function assigns a higher probability of selection to individuals with higher scaled values.

Scaling Rank Rank is the most common scaling function, scales the raw scores based on the rank of each individual instead of its score. The rank of an individual is its position in the sorted scores. An individual with rank r has scaled score proportional to 1/√r. So the scaled score of the most t individual is proportional to 1, the scaled score of the next most t is proportional to 1/sqrt2, and so on.

This method has been studied in the case in which our goal is to minimize the function; in the case of a maximization we can use squared values of tness scores. Rank tness scaling removes the eect of the spread of the raw scores.

Scaling Top Top scaling scales the top individuals. Each of the individ-uals that produce ospring is assigned an equal scaled value, while the rest are assigned the value 0. The scaled values have the form {0, 1/n, 1/n,0, 0, 1/n, 0, 0, 1/n...}; we can change the value of n (between 0 and 1), which species the number of individuals That are assigned positive scaled values.

(33)

3.3. GENETIC ALGORITHM 27

Figure 3.3: Scaled value using rank scaling

Figure 3.4: Dierence between rank and top scaling

After the initialization part and evaluation, we have various operators. The simplest form of genetic algorithm involves three types of operators: selection, crossover, and mutation:

3.3.3 Selection

Selection is a necessary operator in each evolutionary algorithm, selects chro-mosome in the population for the reproduction of the individuals. Selection gives a direction to evolution, it guides the search: in most cases, the higher the tness value (every chromosome has its own tness value determined by calculating the objective function value for each of them) of a chromosome, the higher the probability that this chromosome is selected to breed a new generation.

Chromosomes having sucient tness values to be the candidates for becoming the parents of the new population, the children of who will live in the next generation are transferred into the next generation. The remaining

(34)

ones are considered to be dead and excluded from the population. This operation is repeated in the subsequent iterations so that the good ones shall survive to reach the best solutions at the end of generations. In the application of the selection operator, the idea of natural selection is imposed. A selection operator combines the relative tness of the chromosomes of the population with some randomness in order to determine parents of the ospring generation. There are dierent techniques which a genetic algorithm can use to select the individuals to be copied over into the next generation. We see the dierent types of selection in the next chapter, when we will evaluate the eectiveness of the algorithm;

Stochastic selection The most common selection method; lays out a line in which each parent corresponds to a section of the line of length propor-tional to its scaled value. The tness level (the value obtained by each individual from the tness function) is used to associate a probability of selection with each individual chromosome. This gives weaker members of the population (according to their tness) a chance to be chosen and thus reduces the unfair nature of tness-proportional selection methods.

Figure 3.5: Stochastic selection of a single individual

Remainder In the remainder selection, the average tness of the popu-lation fave is calculated and the tness associated to each individual fI is

divided by the average tness. The population must be formed with the in-teger part of the expression result fI

fave, it means that the probability that a parent is chosen in this step is proportional to the fractional part of its scaled value. In this case, free places were lled based on the Roulette method. Uniform Uniform selection chooses parents using the expectations and number of parents. Uniform selection is useful for debugging and testing, but is not a very eective search strategy.

Roulette In the Roulette method [50], the rst step is to calculate the cumulative tness of the whole population through the sum of the tness of

(35)

Member Chromosome Integer

value Fitnessvalue selection (in %)Prob. of

1 0001101011 107 6.82 31

2 1111011000 984 6.82 5

3 0100000101 261 8.48 38

4 1110100000 928 2.57 12

5 1110001011 907 3.08 14

all individuals. The following table lists a sample population of 5 individuals (a typical population of 400 would be dicult to illustrate). These individ-uals consist of 10 bit chromosomes and are being used to optimize a simple mathematical function: f(x) = −1

4x2+ 2x + 5.

After that, the probability of selection is calculated for each individual as being P robsel = _{P f}fI_I. Then, an array is built containing cumulative

probabilities of the individuals. So, n random numbers are generated to the range 0 to (0 − P fI) and for each random number an array element which

can have higher value is searched for. Therefore, individuals are selected according to their probabilities of selection.

Figure 3.6: Roulette wheel approach: based on tness

Tournament As the name suggests, the chromosomes are selected through performing more "tournaments", chosen at random from the population. The winner of each tournament, judged through the tness value, are selected for the crossover operator. Selection pressure is easily adjusted by changing

(36)

the tournament size. If the tournament size is larger, weak individuals have a smaller chance to be selected.

3.3.4 Crossover

: The crossover operator is a method for sharing information between chro-mosomes. Selected parents reproduce the ospring by performing a crossover operation on the chromosomes.

Figure 3.7: Crossover operation

It has always been regarded as the main search operator in genetic algo-rithms because it exploits the available information in previous samples to inuence future searches. In nature, crossover implies two parents exchange parts of their corresponding chromosomes. Since more t individuals have a higher probability of producing ospring than less t ones, the new popula-tion will possess on the average an improved tness. This is why the most real coded research has been focused on developing eective real-parameter crossover operators.

Scattered Also called Uniform, creates a random binary vector and selects the genes where the vector is a 1 from the rst parent, and the genes where the vector is a 0 from the second parent, and combines the genes to form the child. For example:

Single Point In this type of crossover are selected two parents from the population, it is taken a random point where make the cut, and switches the code strings. In the following example you can see this operation:

Two Point Two-point crossover use two selected points, two random inte-gers m and n between 1 and the number of bits in a chromosome, to perform

(37)

Figure 3.8: Scattered crossover

Figure 3.9: Single point crossover

the slicing of the parent organism strings. Everything between the two points is swapped between the parent organisms, rendering two child organisms.

Figure 3.10: Two point crossover

Intermediate Creates children by taking a weighted average of the par-ents. The function creates the child from parent1 and parent2 using the following formula:

child = parent1 + rand ∗Ratio ∗ (parent2 − parent1) (3.3) We can specify the weight with which to make the choice through the Ratio parameter, which is between 0 and 1, so all the children lie on the line

(38)

between the parents.

Heuristic Returns a child that lies on the line containing the two parents, a small distance away from the parent with the better tness value in the direction away from the parent with the worse tness value. Making the assumption that the parent1 has a higher tness value, the function returns the child is:

child = parent2 +Ratio ∗ (parent1 − parent2) (3.4) Even in this case, we can control the crossover through a parameter: we can specify how far the child is from the better parent by the parameter Ratio. Arithmetic In general, some arithmetic operation is performed to make a new ospring; in our case we creates children that are the weighted arithmetic mean of two parents.

3.3.5 Mutation

This operator randomly ips some of the bits in a chromosome. Mutation in genetic algorithms serves as an operator to reintroduce lost genes into the population. It works on the level of chromosome genes by randomly altering a gene value. The operation is designed to prevent genetic algorithm from premature termination.

Mutation is a random process where once the genes are replaced by an-other to produce a new genetic structure. In genetic algorithms, mutation is randomly applied with low probability and modies elements in the chromo-somes. Usually considered as a background operator, the role of mutation is often seen as providing a guarantee that the probability of searching any given chromosome will never be zero and acting as a safety net to recover good genetic material that may be lost through the action of selection and crossover.

Gaussian The default mutation function for unconstrained problems, Gaus-sian, adds a random number taken from a Gaussian distribution with mean 0 to each entry of the parent vector. The standard deviation of this distri-bution is determined by the parameters Scale and Shrink:

• The Scale parameter determines the standard deviation at the rst generation;

• The Shrink parameter controls how the standard deviation shrinks as generations go by. The standard deviation at the kth generation, σk,

is given by the recursive formula: σk= σk−1 1 − Shrink k n◦_{of Generation} (3.5)

(39)

3.3. GENETIC ALGORITHM 33 Uniform It 's the most widely used process, and also the one that will be used in the next chapter to study changes in the objective function. First, the algorithm selects a fraction of the vector entries of an individual for mutation, where each entry has a probability Rate of being mutated, second, the algorithm replaces each selected entry by a random number selected uniformly from the range for that entry. To evaluate the eectiveness of the process, we are going to change the parameter Rate.

3.3.6 A Simple Example

To better understand the operation of the algorithm, we use the proposed example in [51] which explains the various operations leading to the nal result.

Figure 3.11: Genetic Algorithm Flowchart A simple problem could be:

max f (x) = x3; x ∈ N; 0 ≤ x ≤ 2047 (3.6) Obviously the solution (x = 2047) is trivial, but it is a simple example to understand how the iterative algorithm works; There are many ways to solve this maximization, we'll use the following:

Continuing with the example, let the initial population be:

Going forward with step 4 of the algorithm, the 1,5,6 and 7 members have the greatest value tness, so we're going to eliminate the other strings with lower tness value to create a temporary table and continue with the algorithm.

(40)

Table 3.2: Genetic Algorithm Example

1 Form a population: eight binary string of length eleven;

2 Decode: assign a natural number x to each string. (e.g. 00000010011 it is encoded with x = 19);

3 Calculate the tness value for each individual calculated through the function f(x): e.g. the solution x = 19 has a tness of 193 _{= 6859;}

4 Take half of the individuals of the population choosing those that have the highest tness value, these will form the next generation; 5 It takes two parents from these new strings that have the greatest value tness and using the crossover operator (in this case we will use the single point crossover, for the operation to see the next chapter); in this way we

will create the two child strings;

6 Let the mutation: with a certain probability, in each string will scroll bits and ips 0 into 1 and vice versa;

7 Form new population: we combine the child (which are 4) and the parents, to form the eight strings that begin the cycle again 8 Return to

step 2, and repeat until meet stopping criteria.

Population member String x Fitness value

1 11010110010 1714 5035382344 2 01010001011 651 275894451 3 01101111101 893 712121957 4 01010000110 646 269586136 5 01110101110 942 835896888 6 10110100100 1444 3010936384 7 10000101101 1069 1221611509 8 01001101010 618 236029032

Temporary pop mem String x Fitness value

1 11010110010 1714 5035382344

2 01110101110 942 835896888

3 10110100100 1444 3010936384

4 10000101101 1069 1221611509

To clarify the next point, should rst see how the crossover operator acts on two strings randomly: take 11000110100 and 11100011100, pick a random point (in this case we choose between the third and the fourth bit) between two bits, cut the strings in the selected point and reverse the code (so the right part of the cut). So we will create the two child:

Returning to the example, choose the strings couples randomized to which to apply the crossover operator: as the position in which to make the cut is chosen randomly and independently for each pair of strings (in

(41)

Parents Children

110\00110100 11000011100 111\00011100 11100110100

this case we will have two pairs), we choose the rst and the third and choose to cut between the second and the third bit, and the second and fourth, in which we choose to cut between the fourth and fth bit. So the new population will be composed of parents in the temporary table and of children just "created".

Population member String x Fitness value

1 11\010110010 1714 5035382344 2 0111\0101110 942 835896888 3 10\110100100 1444 3010936384 4 1000\0101101 1069 1221611509 5 11110100100 1956 7483530816 6 01110101101 941 833237621 7 10010110010 1202 1736654408 8 10000101110 1070 1225043000

To check that our algorithm is working, let's examine the tness value of the new population of strings, and compare them with those initials. The average tness value of the initial population is fave = 1449682337, instead

than the current population is fave = 2672786621. Even considering the

tness value of each individual string, we have improved: the maximum value in the initial population is fmax = 5035382344, instead now is fmax=

7483530816.

The stopping criteria can be multiple: it can be since the average tness value is far from the maximum value (for example, it is stopped when the distance is less than 10−5_{), or we could decide to stop after a certain}

num-ber of generations ( for example we stop after fty generations) and so on; assuming that the criterion that still was not satised to end the algorithm, the next temporary population becomes:

Temporary pop mem String x Fitness value

1 11010110010 1714 5035382344

2 10110100100 1444 3010936384

3 11110100100 1956 7483530816

4 10010110010 1202 1736654408

In this table, we can see that in any string there is a 1 in last place. For how we set the selection and crossover, there can never be more than a 1 in the bottom of the string; this means that we can never achieve the absolute maximum (which we know to be the string of all 1, encoded by the number

(42)

2047), but we could get the most of 11111111110 string, which can never be exceeded, and therefore become dominant for all populations.

This domination of the population by a single sub-optimal string gives a rst indication of why mutation might be important. This is because the crossover operator not introduce any new information, because it just swaps the code strings that already exist. To introduce new information, we need an operator that maintains the genetic diversity of the population, and that is exactly what makes the mutation operator [52].

(43)

Chapter 4

Implementation and Evaluation

In this chapter rst of all we show the results of simulations, in which we tried as does the average throughput of the network under varying the genetic algorithm characteristics, then we will show the results of simulations made to evaluate the multi-objective problem.

4.1 Genetic Algorithm optimization

First of all, we set the key parameters:

Nk = 10; Npop= 100; Nbest= 50; µn= 0.01;

Where Nk is the number of the nodes of the network; Npop says how

many chromosomes are in population (in one generation). If there are too few chromosomes, GA have a few possibilities to perform crossover and only a small part of search space is explored. On the other hand, if there are too many chromosomes, GA slows down. Research shows that after some limit (which depends mainly on encoding and the problem) it is not useful to increase population size, because it does not make solving the problem faster;

Nbest: the ttest chromosomes in a population will be called "best" and,

as "best" chromosomes, they will be used in the pairing procedure. The chromosomes with poor tness are to be replaced in the next population with new ospring. µn = 0.01 says how often will be parts of

chromo-some mutated. If there is no mutation, ospring is taken after crossover (or copy) without any change. If mutation is performed, part of chromosome is changed. If mutation probability is 100%, whole chromosome is changed, if it is 0%, nothing is changed. Mutation is made to prevent falling GA into local extreme, but it should not occur very often, because then GA will in fact change to random search.

After, we did simulations, varying the functions that make up the al-gorithm. In total, they were made over 90 simulations, choosing the best performing in terms of total throughput of the network and in terms of