Scheduling Models for Industrial Internet of Things Networks

UNIVERSITÁ DIPISA

DOTTORATO DI RICERCA ININGEGNERIA DELL’INFORMAZIONE

S

CHEDULING

M

ODELS FOR

I

NDUSTRIAL

I

NTERNET OF

THINGS

NETWORKS

DOCTORALTHESIS

Author

Mike Oluwatayo Ojo

Tutor (s)

Prof. Stefano Giordano Prof. Michele Pagano Ing. Davide Adami

Reviewer (s)

Prof. Periklis Chatzimisios Prof. Burak Kantarci

The Coordinator of the PhD Program

Prof. Marco Luise

Pisa, October 2018 XXXI

Abstract

IEEE 802.15.4-2015 Time Slotted Channel Hopping (TSCH) Networks have gained a lot of attention within the Industrial Internet of Things (IIoT) research community due to its effectiveness in improving reliability and providing ultra-low power consumption for industrial applications, where communication is orchestrated by a schedule. The key feature of TSCH is the scheduling of time slots and frequencies, which can be typically created in various ways but should be computed according to specific requirements, such as throughput, energy, reliability and latency. Despite the promising features of the TSCH, IEEE 802.15.4 standard leaves out of its scope in defining how the sched-ule is built and maintained, which is the focus of this research. This thesis presents a centralized scheduling model in IEEE 802.15.4-2015 TSCH Networks, where the gateway makes frequency allocations and time slot assignments. We propose differ-ent scheduling models focusing on maximizing the overall throughput, minimizing the average scheduling delay, maximizing the energy efficiency, and providing throughput fairness through max-min fair approach. In achieving these, we devise algorithm-based optimal, sub-optimal yet heuristic algorithms. In addition to the heuristic algorithms and simulation-based studies, this thesis also provides a graph theoretical approach and proposes polynomial time graph algorithms. Moreover, experimental measurements are conducted on different platforms and various operating systems to assess the energy consumption and evaluate the impact of TSCH protocol. Lastly, the thesis focuses on emerging technologies for the Internet of Things (IoT), where we present a simple and general Software Defined Networking (SDN)-IoT architecture with Network Function Virtualization (NFV) implementation, providing specific choices on where and how to adopt SDN and NFV approaches to address the new challenges of the IoT.

List of publications

International Journals

1. Ojo, M.O., Giordano, S., Adami, D. and Pagano, M. (2018, September). Through-put Maximizing and Fair Scheduling Algorithms in Industrial Internet of Things Networks. IEEE Transactions of Industrial Informatics. IEEE.

2. Ojo, M.O., Giordano, S., Procissi, G. and Seitanidis, I. (2018, November). A Review of Low-end, Middle-end and High-end IoT Devices. IEEE Access. IEEE.

International Conferences/Workshops with Peer Review

1. Tsapardakis, E., Ojo, M., Chatzimisios, P., and Giordano, S. (2018, October). Performance Evaluation of SDN and RPL in Wireless Sensor Networks. In Global Information Infrastructure and Networking Symposium (GIIS), 2018 (pp. 1-5). IEEE.

2. Ojo, M., Giordano, S., Adami, D., and Pagano, M. (2018, June). A Novel Auc-tion Based Scheduling Algorithm in Industrial Internet of Things Networks. In International Conference on Computer Networks, 2018 (pp. 103-114). Springer, Cham.

3. Giordano, S., Seitanidis, I., Ojo, M., Adami, D., and Vignoli, F. (2018, March). IoT Solutions for Crop Protection against Wild Animal Attacks. In 2018 IEEE International Conference on Environmental Engineering (EE), 2018 (pp. 1-5). IEEE.

4. Ojo, M., Giordano, S., Portaluri, G., and Adami, D. (2017, December). Through-put Maximization Scheduling Algorithm in TSCH Networks with Deadline Con-straints. In Globecom Workshops (GC Wkshps), 2017 (pp. 1-6). IEEE.

5. Ojo, M., Giordano, S., Portaluri, G., Adami, D., and Pagano, M. (2017, May). An Energy Efficient Centralized Scheduling Scheme in TSCH Networks. In Commu-nications Workshops (ICC Workshops), 2017 IEEE International Conference on, (pp. 570-575). IEEE.

6. Ojo, M., Adami, D., and Giordano, S. (2016, December). A SDN-IoT Architec-ture with NFV Implementation. In Globecom Workshops (GC Wkshps), 2016 (pp. 1-6). IEEE.

7. Ojo, M., and Giordano, S. (2016, October). An Efficient Centralized Scheduling Algorithm in IEEE 802.15.4e TSCH networks. In Standards for Communications and Networking (CSCN), 2016 IEEE Conference on(pp. 1-6). IEEE.

8. Ojo, M., Adami, D., and Giordano, S. (2016, July). Performance Evaluation of Energy Saving MAC Protocols in WSN Operating Systems. In Performance Evaluation of Computer and Telecommunication Systems (SPECTS), 2016 Inter-national Symposium on(pp. 1-7). IEEE.

List of Abbreviations

Symbols

6LBR 6LoWPAN Border Router. 10, 11

6LoWPAN IPv6 over Low-Power Wireless Personal Area Networks. 13, 15, 17

A

ACK Acknowledgement. 7, 87

API Application Programming Interface. 14, 68 B

BILP Binary Integer Linear Programming. 8

BSD Berkeley Software Distribution. 15, 16

BSP Board Support Package. 16

BSS Business Support Systems. 70

C

CapEx Capital Expenditure. 62

CCT Charnes Cooper Transformation. 42, 55, 83

CFP Concave Fractional Programming. 42

CoAP Constrained Application Protocol. 15–17 CSMA-CA Carrier-Sense Multiple Access with

Colli-sion Avoidance. 7, 15 D

DAG Directed Acyclic Graph. 10

DAO DODAG Advertisement Object. 11

DIO DODAG Information Object. 11

DIS DODAG Information Solicitation. 11

DODAG Destination Oriented Directed Acyclic

List of Abbreviations

E

EE Energy Efficiency. 42, 53–55

EES Energy Efficient Scheduler. 42, 43, 56, 60

EPC Evolved Packet Core. 65

G

GA Genetic Algorithm. 5, 7, 9, 18, 20, 30, 31, 36, 38, 39, 41, 83

H

HTTP HyperText Transfer Protocol. 16, 17 I

I2C Inter-Integrated Circuit. 12

IEEE Institute of Electrical and Electronics Engi-neers. 3

IETF Internet Engineering Task Force. 3, 10, 15, 17, 74

IIoT Industrial Internet of Things. 2–5, 19, 20, 42–44, 48, 82, 84, 90

ILP Integer Linear Programming. 42, 45, 83

IoT Internet of Things. 2, 4–7, 12, 15, 62–68, 70–72, 79–81, 84

IPv6 Internet Protocol Version 6. 15 L

LLN Low Lossy Networks. 10

M

M2M Machine-to-Machine. 64, 65

MAC Medium Access Control. 3, 7, 15, 16, 19

MANO Management and Network Orchestration.

69

MCU Microcontroller Unit. 12, 13

MFS Max-Min Fair Scheduler. 42, 44, 46, 48,

50, 60, 83

MILP Mixed Integer Linear Programming. 14

MOCell Multi-Objective Cellular Genetic Algo-rithm. 33, 37

N

NFC Near-Field Communication. 66

NFV Network Function Virtualization. 4–7, 11, 62–66, 68–72, 79, 83, 84

NFVI Network Function Virtualized Infrastruc-ture. 69, 81

NLP Nonlinear Programming. 42

NSGA-II Non-dominated Sorting Genetic

Algorithm-II. 33, 37

NSGA-III Non-dominated Sorting Genetic

Algorithm-III. 33, 36, 37, 41, 83 O

OF Objective Function. 10, 11, 15

ONOS Open Network Operating System. 68, 73

OpEx Operating Expense. 62

OS Operating System. 5, 12, 15, 17, 36, 63, 87

OSS Operations Support Systems. 70

P

PF Pareto Front. 14, 38

PHY Physical. 3, 15

Q

QoE Quality of Experience. 66

QoS Quality of Service. 2, 65, 66

R

RAM Random Access Memory. 12, 36

RDC Radio Duty Cycle. 3, 15, 85

RFID Radio-Frequency Identification. 66

ROLL Routing Over Low power and Lossy

net-works. 10

RPL IPv6 Routing Protocol for Low Power and

Lossy Networks. 5, 6, 10, 11, 15, 17, 63, 73–75, 79, 80, 84

S

SDN Software Defined Networking. 4–7, 11,

62–68, 70–75, 77, 79, 80, 83, 84

SDR Software Defined Radio. 14

SoC System on Chip. 15

SPEA2 Strength Pareto Evolutionary Algorithm-2. 33, 37, 38

SPI Serial Peripheral Interface. 12 T

TCP Transmission Control Protocol. 16, 17 TSCH Time Slotted Channel Hopping. 3–5, 7, 8,

12, 16, 18–20, 22, 23, 28, 30, 34, 42–44, 48, 50, 82–85

List of Abbreviations

U

UDP User Datagram Protocol. 16, 17

V

VAM Vogel’s Approximation Method. 43, 57

VIM Virtualized Infrastrcuture Manager. 69

VM Virtual Machine. 69

VNF Virtual Network Function. 69–71, 81

W

WSN Wireless Sensor Network. 10, 13, 17, 63,

Contents

List of Abbreviations V

List of figures XII

List of tables 1 1 Introduction 2 1.1 Key Contributions . . . 5 1.2 Thesis Structure . . . 5 2 Background 7 2.1 TSCH in a Nutshell . . . 7 2.2 Optimization Techniques . . . 8 2.2.1 Genetic Algorithm . . . 9 2.2.2 Auction Theory . . . 9 2.3 Technologies . . . 10 2.3.1 RPL . . . 10 2.3.2 SDN . . . 11 2.3.3 NFV . . . 11 2.4 Hardware . . . 12 2.4.1 OpenMote-CC2538 . . . 12 2.4.2 Tmote Sky . . . 13 2.4.3 Zolertia Z1 . . . 13 2.5 Tools . . . 14 2.6 Operating Systems . . . 15

3 Throughput Maximizing Scheduler under Interference Constraints 18 3.1 Related Works . . . 19

3.2 System Model and Assumptions . . . 20

3.3 Problem Formulation . . . 22

3.3.1 Throughput Maximization Problem . . . 22

Contents

3.4 Throughput Maximizing Scheduling Algorithms . . . 24

3.4.1 Graph-Based Theoretical Approach . . . 24

3.4.2 Auction-Based Scheduling Approach . . . 28

3.4.3 Genetic Algorithm Based Scheduling Approach . . . 29

3.5 Performance Evaluation . . . 34

3.6 Chapter Summary . . . 40

4 Throughput Fair Scheduling and Energy Efficient Centralized Scheduling Algo-rithms 42 4.1 Related Works . . . 43

4.1.1 Throughput Fair Scheduling Algorithms . . . 43

4.1.2 Energy Efficiency in IIoT-TSCH Networks . . . 43

4.2 Max-Min Fairness Scheduler . . . 44

4.2.1 Algorithm for the Max-Min Fair Scheduling Problem . . . 46

4.2.2 Computational Complexity . . . 46

4.2.3 Performance Evaluation . . . 46

4.3 Energy Efficient Modeling . . . 50

4.3.1 Link Capacity Calculation/ Network Throughput Modeling . . . 50

4.3.2 Energy Consumption Model . . . 51

4.3.3 Problem Formulation . . . 53

4.4 Energy-Efficient Centralized Schedulers . . . 54

4.4.1 Optimal Energy-Efficient Scheduling (EE-OPT) . . . 55

4.4.2 Energy Efficient Scheduler (EES) . . . 56

4.4.3 Vogel’s Approximation Based Heuristic Scheduling Algorithm (VAM-HSA) . . . 57

4.4.4 Performance Evaluation . . . 57

4.5 Chapter Summary . . . 60

5 A SDN-IoT Architecture with NFV Implementation 62 5.1 Related Works . . . 63

5.2 Why SDN/NFV in IoT . . . 64

5.3 SDN-IoT Architecture with NFV . . . 66

5.3.1 IoT Architecture . . . 66

5.3.2 SDN-IoT Framework . . . 68

5.3.3 NFV-IoT Architecture . . . 68

5.3.4 SDN-IoT Architecture with NFV . . . 70

5.4 Methodology and Evaluation Environment . . . 72

5.5 Performance Evaluation . . . 75

5.6 Chapter Summary . . . 79

6 Conclusion 82 A Energy Consumption Measurements in WSN Operating Systems 85 A.1 Energy Consumption Measurements and Results . . . 85

A.1.1 Experimental Setup . . . 86

A.1.2 Experimental Comparison . . . 86

List of Figures

1.1 IEEE/IETF Standardized Industrial IoT Architecture . . . 3 2.1 Time Slotted Channel Hopping (TSCH) Slot-Channel matrix with a

sim-ple topology . . . 8 2.2 Flow Chart for our proposed GA-based algorithm . . . 10 2.3 NFV architecture . . . 12 2.4 The OpenMote hardware ecosystem: (from left to right)

OpenMote-CC2538, OpenBattery and OpenBase . . . 13 2.5 Network Stack of Contiki, OpenWSN Operating systems . . . 16 3.1 TSCH Slot-Channel matrix where each nk maintains a link with the

gateway (GW ) for both frequency f and time slot t, where k ∈ {1, · · · , N }; f ∈ {1, · · · , F }, t ∈ {1, · · · , T } . . . 21 3.2 Auction theory based scheduler flow diagram . . . 30 3.3 Average total throughput comparison of the proposed auction scheduling

algorithm vs the optimum results obtained through CPLEX simulations 35 3.4 Average total network throughput for the throughput maximization

schedul-ing problem by varyschedul-ing the number of antennas and frequencies . . . . 35 3.5 Execution Times of the Algorithm . . . 37 3.6 Minimizing the violated deadlines . . . 38 3.7 Average network throughput for the GA-based scheduling scheme with

N = 10, crossover = 0.9, mutation probability = 0.01 and varying the population size . . . 39 3.8 Average network throughput for the GA-based scheduling scheme with

N = 10 while varying µm . . . 40 3.9 Average network throughput for the GA-based scheduling scheme with

population size = 100, crossover = 0.9, mutation probability = 0.01 and varying number of nodes . . . 41 4.1 Average throughput of all nodes . . . 47 4.2 Average total throughput . . . 47

4.3 Average total throughput vs ω . . . 48

4.4 Average Jain’s Fairness Index vs ω . . . 49

4.5 Average total throughput for varying the number of nodes . . . 49

4.6 Average Jain’s Fairness Index for varying the number of nodes . . . 50

4.7 Average minimum throughput for HMFS while varying the number of nodes . . . 51

4.8 Time slot template for a transmitter (top) and the receiver node (bottom) 52 4.9 Probability of success for increasing F . . . 59

4.10 Probability of success for increasing N . . . 59

4.11 Energy Efficiency . . . 60

5.1 An IoT Architecture . . . 67

5.2 SD-IoT Architecture . . . 69

5.3 A NFV-IoT Architecture . . . 70

5.4 SDN-IoT Architecture with NFV . . . 71

5.5 SDN/NFV Edge Node for IoT Services . . . 72

5.6 Single-hop mesh topology . . . 73

5.7 Multi-hop topology . . . 74

5.8 Average Packet Loss Distribution for a Single-hop Mesh Topology (Sce-nario 1) . . . 76

5.9 Average Packet Loss Distribution for a Multi-hop Topology (Scenario 2) 76 5.10 Average convergence time for SDN and RPL in a single-hop mesh topol-ogy and multi-hop topoltopol-ogy . . . 77

5.11 Control Message Overhead Distribution . . . 78

5.12 Flow Rule Entry time . . . 78

5.13 Average Packet Loss vs Number of Hops . . . 79

5.14 Average Packet Delay . . . 80

A.1 Measurement Setup with an Oscilloscope . . . 87

A.2 A tree topology using OpenMote-CC2538 . . . 88

A.3 Energy Consumption in OpenMote-CC2538 running OpenWSN and Con-tiki using TSCH protocol . . . 88

A.4 Energy Consumption in OpenMote-CC2538 running Contiki with Con-tikiMAC and Contiki with TSCH . . . 89

A.5 Energy Consumption in Tmote Sky running Contiki with ContikiMAC and Contiki with TSCH . . . 89

A.6 Current drawn in the TX mode of OpenMote-CC238 running OpenWSN with TSCH . . . 90

List of Tables

2.1 IoT Device Specifications . . . 14

2.2 Low-end IoT operating systems comparison . . . 17

3.1 Symbols . . . 32

3.2 Basic Simulation Parameters . . . 34

3.3 Genetic Algorithm Parameters . . . 37

3.4 Average Execution times in ms of the various Genetic Algorithm Search Strategies . . . 37

3.5 Average Throughput for GA-based scheduling scheme with N = 10, population size = 100, crossover = 0.9 and varying the mutation probability 39 3.6 Parameters settings for the GA scheduler with varying number of nodes 40 4.1 Summary of Symbols and Basic Simulation Parameters . . . 58

CHAPTER

1

Introduction

The increasing number of physical objects connected to the Internet at a remarkable rate brings the idea of the rapid evolution of the Internet of Things (IoT). The tremen-dous impact IoT has on several aspects of everyday life has drawn significant research attention from both academic and industrial sectors over the past few years. Despite its popularity, its definition is still fuzzy due to its vast area of concepts (semantics, security, interoperability, reliability, data/control/management functions, etc.) and the ambiguity of the unique meaning of the two terms “Internet” and “Things” [1]; al-though both remain a physical and virtual counterpart. IoT is understood to be a global network infrastructure composed of diverse heterogeneous devices that rely on sensory, communication, networking and information processing technologies required to pro-vide advanced services aimed to improve our quality of life.

Industrial Internet of Things (IIoT), a natural evolution of the IoT, is indeed trans-formative and will change the basis of competition. It emphasizes the nonexistence of human intervention as well as the autonomous nature of machines. IIoT encompasses a vast amount of disciplines by providing a way to improve visibility into the company’s operations and assets through the integration of machine sensors, middleware and the cloud systems.

New developments have been undertaken in the field of IIoT in recent times to shape the need for high Quality of Service (QoS) and determinism to the industries. Devel-opments such as Wireless, IP-enabled for industrial networks have led to IIoT and have been identified as an attractive alternative for communication. It is rapidly becoming the technology of choice for communication so as to provide a viable and cost-effective solution in a growing class of applications such as distributed control systems, smart grids, automotive systems, and other kinds of network embedded systems [2, 3]. This has played a significant role towards the convergence of operational technology (i.e.

IPv6 IEEE802.15.4 (PHY) IEEE802.15.4-2015 TSCH 6LoWPAN IPv6 RPL UDP TCP CoAP HTTP Application Application

Figure 1.1: IEEE/IETF Standardized Industrial IoT Architecture

industrial networks) and information technology (i.e. the Internet). Moreover, the prin-ciples of IIoT give rise to the implementation of Industry 4.0, driven by the dramatic altering of manufacturing, energy, transportation and other industrial and municipal sectors, and where networks have been classified as one of the emerging key technolo-gies [4, 5].

IIoT will revolutionize manufacturing and also drive growth in productivity across various types of applications. A common requirement across various IIoT applications is to deliver both low-power and wire-like reliability. This can be achieved through the work of various standardization bodies, which have made so much effort in propos-ing standards to support the development of IIoT and also address fast growpropos-ing market needs. One of the leading standard in the IIoT is IEEE 802.15.4, which defined the Physical (PHY) and the Medium Access Control (MAC) layers for low-power, low rate wireless personal area networks. Various industrial and automation technologies such as ISA.100.11a [6], WirelessHART [7], that reside under the IIoT umbrella, have in-corporated the IEEE 802.15.4 PHY layer components.

Reliability, scalability and unbounded latency are some of the limits of IEEE 802.15.4 MAC. The third version of the IEEE 802.15.4 standard, called IEEE 802.15.4-2015 [8], addresses this limitation by improving the previous PHY and MAC layers. Among the operating modes in this standard is the Time Slotted Channel Hopping (TSCH), which aims at addressing the strict requirements in terms of timeliness and reliability especially in the industrial domain and has been incorporated in the industrial tech-nologies mentioned above. TSCH provides network robustness through spectral and temporal redundancy, ensuring low power operation, and also mitigating the effects of interference and multipath fading, while it increases the network throughput. This is done by combining time synchronization and channel hopping capabilities. Previous researches have shown that TSCH could achieve 99% end-to-end reliability with a Ra-dio Duty Cycle (RDC) below 1% [9]. Motivated by the great potential of IIoT, both Institute of Electrical and Electronics Engineers (IEEE) and Internet Engineering Task Force (IETF) standardization bodies propose the architecture for the IIoT shown in Fig-ure 1.1.

IEEE 802.15.4-2015 standard defines the mechanism of how TSCH executes a schedule, however, it does not mandate a specific scheduling mechanism, which is open to different implementations from the industry. The proper functioning of a TSCH

network depends on a schedule which can be typically created in various ways but should be computed according to the specific requirements of the applications, such as throughput, energy, reliability and latency. In this thesis, we present a scheduling model for IIoT-TSCH networks. Our scheduling model consists of a set of schedulers that is aimed at achieving data rate, time slot and frequency allocation in a hetero-geneous multi-channel environment where nodes are equipped with multiple antennas. Our scheduling model works in a centralized manner where the scheduler that resides at the gateway makes frequency and time slot allocations to the nodes, avoiding collision among them, and ensuring that communications between the nodes and the gateway are maintained.

We present different scheduling models focusing on throughput maximizing, delay minimization, energy efficiency maximization and providing throughput fairness. We address the problems by providing optimal, sub-optimal yet heuristic algorithms. In addition to the heuristic algorithms and simulation-based studies, we present a graph theoretical approach and propose polynomial time graph algorithms.

Another critical aspect in the IoT is the diverse heterogeneous devices that rely on sensory, communication, networking and information processing technologies required to provide advanced services aimed to improve our quality of life. The complexity, pos-sible limitations and heterogeneity of various IoT devices connected to the Internet will require specific tools to manage them, and to improve the performance of the whole network. Capability mismatch between devices can also be an issue when we have large number of IoT devices deployed in an urban environment with different protocols and designs. This will be more severe in real-time environments such as robot controls, self-driving cars etc. where the need to exchange real-time information will also need technologies to provide IoT applications in an efficient, scalable, seamless and cost-effective manner. Unfortunately, traditional technologies are not capable of providing such requirements in an efficient way [10].

Traditional architectures and network protocols for IoT devices are not designed to support high level of scalability, high amount of traffic and mobility together with the above-mentioned requirements. They are inefficient and have limitations to satisfy these new requirements. According to GSMA Intelligence1_{, it is forecasted that there} will be about 25 billion IoT devices by 2025, and managing these devices generating an impressive amount of data as a whole, without having elasticity and flexibility in-herently defined in the network would be difficult. If the networks are not prepared, the flood of IoT where a lot of traffic are generated could leave the network paralyzed. To achieve such goals, emerging technologies such as Software Defined Networking (SDN) and Network Function Virtualization (NFV) are being considered as technol-ogy enablers to provide adequate solutions. SDN and NFV are related and paired to each other but they come from different standard organizations with no combined stan-dardized architecture. This thesis presents a simple SDN-IoT architecture coupled with NFV to address the challenges of IoT particularly in the issues of routing, scalability and mobility. This is visualized to increase the efficiency and network agility of IoT applications.

1.1. Key Contributions

1.1

The main contributions of this thesis can be grouped into four as follows:

• Scheduling in TSCH model: We formulate the scheduling problem as throughput maximizing, delay minimizing and energy efficiency maximizing. In the through-put scheduling maximizing problem, we propose a polynomial time algorithm and we elaborate on certain special cases of this problem and explore their combina-torial properties. We introduce heuristic algorithms based on auction-based and Genetic Algorithms (GAs) to address the scheduling problem. For the energy effi-ciency maximization, we model the energy consumption of a TSCH node thereby, formulating the energy-efficient scheduling and providing optimal, sub-optimal yet heuristic algorithms.

• Fairness in TSCH Networks: We formulate a max-min fair scheduling problem that provides throughput fairness. It incorporates the past transmission history of each node to provide some degree of fairness among of the nodes. We proceed to propose a novel heuristic for the max-min fair scheduling problem and demon-strate its performance through extensive simulations.

• SDN-IoT: We present a simple and general SDN-IoT architecture coupled with NFV with specific choices on where and how to adopt SDN and NFV approaches in order to address the new challenges of the Internet of Things. We focus on routing as it is an essential way of ensuring reliability, lifetime and end-to-end delay of a network. We investigate on the performance of SDN and IPv6 Routing Protocol for Low Power and Lossy Networks (RPL) by providing a performance analysis on real-hardware based experimental measurements using OpenMote-CC2538.

• Energy Consumption in IoT devices: In order to gain deeper insights in the en-ergy consumption of IIoT-TSCH implementations. We focus on the enen-ergy con-sumption by conducting experimental measurements on different platforms i.e. OpenMote-CC2538 and Tmote Sky on various Operating Systems (OSs) includ-ing Contiki, OpenWSN.

To sum things up, in this thesis we are concerned with the problem of scheduling in IIoT-TSCH Networks by considering various scheduling models. We also focus on SDN and NFV applied to IoT. Lastly, we focus on energy consumption in IoT OSs.

1.2

The rest of the thesis is structured as follows:

• Chapter 2 introduces the background of the study and some important concepts related to some optimization techniques, technologies paradigms, low-end IoT devices, IoT operating systems and the tools that have been adopted.

• Chapter 3 presents the system model and the problem formulation for the through-put maximization and delay minimization problem. A polynomial-time algorithm

and auction-based heuristic algorithm is proposed for the throughput maximiza-tion problem. In addimaximiza-tion, deadline constraint is introduced in the problem formu-lation for the throughput maximization problem, and genetic algorithm is intro-duced to address this problem, in which its performance is demonstrated through simulations.

• Chapter 4 presents the max-min fair scheduling problem and the proposed heuris-tic algorithm to address this problem. The energy efficiency maximization prob-lem is also formulated, and the proposed scheduling algorithms are described in this chapter.

• Chapter 5 take a look of how SDN and NFV can be used to apply to IoT emphasiz-ing their domains of application, illustrated with examples. SDN-IoT architecture with NFV is also demonstrated in this chapter. Moreover, performance evalu-ation of SDN and RPL are performed based on low-end IoT devices including OpenMote-CC2538 and Zolertia Z1.

CHAPTER

2

Background

This chapter introduces the background of the study and some important concepts that will be used throughout the thesis. First, we present about TSCH background, and describe some optimization techniques proposed for addressing this problem including GA and Auction-based mechanism. We also present SDN and NFV paradigm that al-lows a flexible network management for IoT devices. We introduce the open source hardwares that are used for the performance evaluation and experimental results. Fi-nally, we describe the software tools used to perform our experiments.

2.1

IEEE 802.15.4-2015 TSCH standard introduces time scheduled transmission multi-plexed in frequency, where nodes are synchronized using a frame structure. Com-munication in TSCH networks occurs at well-defined times within a time slot and it is orchestrated by a schedule. The proper functioning of a TSCH network depends on a schedule, which can be typically created in various ways but should be computed according to the specific requirements of the applications, such as throughput, energy, reliability and latency. The duration of a time slot is not defined by the standard. A typical time slot duration in IEEE 802.15.4-2015 TSCH networks is 15ms [11], which is large enough to transmit a MAC frame of maximum size from a sender to a receiver, and to receive back an Acknowledgement (ACK) frame. Several time slots form a slot frame, which repeats over time. Depending upon the application, there can be a single slot-frame or multiple slot-frames within the network. Each time slot can be dedicated (i.e. contention free) or it can be shared1 _{(contention-based) according to TSCH}

speci-1_{the standard defines a Carrier-Sense Multiple Access with Collision Avoidance (CSMA-CA) algorithm to reduce the} proba-bility of repeated collision

0 1 2 3 4 5 6 7 0 A>C A>C 1 A>B 2 F>B A>F B>F 3 C>D A>D 4 B>C Cha nn el Of fse t Timeslot

First Cycle k Second Cycle k+1

F

B

A

C

D

Allocated cell for the link between node Cas a sender and node Das a

receiver

Shared cells, in which more than one transmitter are scheduled to use a cell with

a random back-off algorithm

Figure 2.1: Time Slotted Channel Hopping (TSCH) Slot-Channel matrix with a simple topology

fications. In our work, all data transmissions are scheduled in dedicated time slots as it introduces a more reliable link-layer communication. A slot frame can be represented as a time-slot, channel-offset matrix as shown in Figure 2.1. Figure 2.1 illustrates a typical TSCH slot frame - channel matrix for a simple network topology. In the figure shown, we have a slot frame, which is 8 time slots long and there are 5 channel offsets. Each node in the cell only cares about the cell it participates in. A link is a transac-tion that occurs within a cell. The two nodes at either end of the link communicate periodically once in every slot frame. TSCH does not impose a slot frame size and this depends on the application needs. TSCH schedule determines the time slot and frequency each node should transmit/receive data to/from its neighbours. An essential benefit of TSCH over asynchronous solutions in terms of low power operation and link stability has been demonstrated through experimental analysis in [12, 13].

2.2

The scheduling problem is combinatorial and it is a variant of knapsack problem which is NP-hard, where the frequencies correspond to the items and the nodes correspond to the knapsacks each with capacity ak(see chapter 3.3). In this section, we introduce dif-ferent heuristics for the optimization of the Binary Integer Linear Programming (BILP).

2.2. Optimization Techniques

2.2.1 Genetic Algorithm

Genetic Algorithm (GA) is a meta-heuristic that mimics the natural evolution process. It considers an initial set of solutions named population that are generated in a ran-dom way. During the execution of the algorithm, the population evolves across the iterations to a better one. Solution in GA is called chromosome and includes one or more characteristics with each one mapped into a gene. Each solution can be encoded as a string of symbols, a binary string, a vector of numbers, or a combination of the previous structure. The selection operator chooses some of the elements of the current population to produce new elements. New chromosomes are formed either by merging two chromosomes from current generation using a crossover operator or by modifying a chromosome using a mutation operator. The new chromosomes that are generated are called offspring. A new population is formed using a proper search strategy which chooses the best chromosomes and rejects the others, keeping the population size con-stant. GA associates a numerical value with each chromosome named fitness. The fitness value is related to the objective of the computation, and the goal of the GA is to find the most fitting solutions. Fitter chromosomes have higher probabilities of being selected with respect to the others. After several iterations, the algorithms converge to the best chromosome which hopefully represents the optimal or a sub-optimal solu-tion of the problem. The GA is an effective optimizasolu-tion technique that emulates the crossover and mutation phases in the evolution of a chromosome to effectively search for the optimal solution [14]. It is an efficient meta-heuristic search technique espe-cially for problems with large search spaces. A flowchart representing the behavior of GA is represented in Figure 2.2

2.2.2 Auction Theory

Auction theory originally developed in economics, is a branch of game theory that has been applied to solve various (network resource allocation) problems in engineer-ing. An auction mechanism works as follows, first, buyers submit bids for purchasing commodities, and sellers ask to sell commodities. There are four main types of tions described in most literatures; which are the ascending-bid auctions (English auc-tions), descending-bid auctions (Dutch aucauc-tions), first-price sealed-bid auctions, and the second-price sealed-bid auctions, also called Vickrey auctions [15].

In the ascending auction, all bidders start in the auction with a price of zero. The seller raises the price, bidders drop out until finally one bidder remains, and that bidder wins the object at this final price. Once a bidder drop out, he/she cannot re-enter. It is an open competition, where information is passed across to other bidders when other bidders drop out. In the descending auction, the auctioneer starts at a very high price, and then lowers the price continuously. At any point in time, the bidder can stop the auction, and then pays the current price. In the first-price sealed-bid, all bidders simul-taneously submit sealed bids (hidden from other bidders) to the auctioneer. The bidder with the highest bid wins the auction. In the second-price sealed-bid auctions, bidders simultaneously and independently submit sealed bids to the auctioneer without observ-ing the bids made by other competitors. The highest bidder wins the price and pays the value of the second highest bid. In our work, we utilized the first-price sealed-bid auc-tion mechanism for addressing the problem formulaauc-tion described in Chapter 3.3. Our

Generate Initial Population Number of iterations and termination criteria Select the chromosomes to be mated (selection) Crossover the chromosomes to produce offspring Mutate the offspring

Evaluate Population according to the search strategy

Yes

No

End Start

Figure 2.2: Flow Chart for our proposed GA-based algorithm

motivation for using the first-price sealed-bid auction mechanism is also highlighted in Chapter 3.4.2.

2.3

2.3.1 RPL

RPL is defined by the IETF Routing Over Low power and Lossy networks (ROLL) working group [16, 17] to meet the unique requirements of routing in RPL. Low Lossy Networks (LLN) is a routing protocol adapted for information routing with low power, low memory and processing sensor devices in static topologies commonly found in Wireless Sensor Networks (WSNs). It is a distance vector type routing protocol that builds Directed Acyclic Graphs (DAGs) based on routing metrics and constraints. RPL builds a Destination Oriented Directed Acyclic Graph (DODAG) to route traffic from the client nodes to the sink (the root node) in a multi-point-to-point fashion. Further options also allows point-to-multi-point traffic (from the central control point(s) to the devices) as well as point-to-point traffic (from the root node to the designated device). Building the DODAG requires the computation of an Objective Function (OF) - that operates on a combination of metrics and constraints to compute the ‘best’ path.

RPL defines a rank, which is basically the node’s individual position with respect to the DODAG root. The term 6LoWPAN Border Router (6LBR) is used interchangeably with the term "DODAG root" defined in RFC6550 [16]. The OF defines how RPL nodes

2.3. Technologies

compute their rank values and select their parents. Basically, DODAG construction is started by the 6LBR that sends DODAG Information Object (DIO) messages to its neighbors to announce a minimum rank value. These messages are sent in broadcast and periodically, with a frequency that depends on the network stability. Upon receiving a DIO message, a RPL node computes its own rank by using a given OF, and selects it preferred parent, which is used as the next hop on the upward route to the sink. After joining a DODAG, an RPL node begins to transmit DIO messages to announce its rank value and to continue the DODAG formation. An RPL node can use DODAG Advertisement Object (DAO) to advertise one or more of its parents to other nodes. A DODAG Information Solicitation (DIS) message can also be used to accelerate the join process of a node during network formation or to recover from errors during regular network operations.

2.3.2 SDN

SDN [18] is a networking paradigm that changes the limitations of current network infrastructures. It decouples the forwarding plane (data plane) from the network’s con-trol logic (concon-trol plane) traditionally coupled with one another. The concon-trol plane is implemented in a logically centralized controller (or network operating system), simpli-fying policy enforcement and network configuration and evolution [19], thus ensuring network flexibility. SDN is a new approach for network programmability where the network operator programs the controller to automatically manage data plane devices and optimize network resource usage. This results in improved network performance in terms of network management, control and data handling [20]. Network management decisions such as routing can be done at the SDN controller and moreover, the pro-grammability allows for any updates for new proposals or even clean state approaches. This brings additional advantages by avoiding extra resources for routing decisions since the controller make all the routing and policies decision. For example, in the case of data congestion, the controller will make the decision to redirect the flow of traffic and mandate the devices to update their flow accordingly. This feature of traffic management is not possible with the traditional networking models as changes to the routing paths cannot be implemented directly.

2.3.3 NFV

NFV [21] is a network architecture concept of replacing dedicated network appliances such as switches, routers, firewalls, to name a few, with software running on commer-cial off-the-shelf servers. This introduce an advantage in terms of energy savings, load optimization and network scalability. Figure 2.3 shows a NFV architecture which may consist of one or more virtual machines running different applications and processes in network servers, switches, storage, or even cloud computing infrastructure, instead of having custom hardware appliances for each network function. NFV can serve SDN by virtualizing the SDN controller to be rendered in the cloud thus allowing dynamic migration of the controllers to the optimal locations while SDN can serve NFV by pro-viding programmable network connectivity between NFVs to achieve optimized traffic engineering [22].

VNF 2

Virtual

Compute

Virtual

Storage

Virtual

Network

Virtualization layer

Hardware Resources

Network Function Virtualization Infrastructure

Management

an

d Or

che

str

a

ti

on

VNF 3

VNF n

Compute

Storage

Network

VNF 1

Figure 2.3: NFV architecture

2.4

2.4.1 OpenMote-CC2538

The OpenMote-CC2538 is an open-hardware platform designed to facilitate the pro-totyping and technology adoption of IEEE 802.15.4-2015 TSCH networks, and it is fully supported by OpenWSN. It is a 2.4GHz low-energy mote complaint that is based on the popular platform of Texas Instruments CC2538 housing a Cortex-M3 Micro-controller Unit (MCU), clocked up to 32MHz with a 32-bit architecture, with inte-grated radio module and 32KB of Random Access Memory (RAM) and 512KB of Flash making it a state-of-the-art micro-controller [23]. The device itself provides inter-faces including Inter-Integrated Circuit (I2C), Serial Peripheral Interface (SPI), which gives the opportunity to connect any kind of sensors. The OpenMote offers alongside with the OpenMote-CC2538 mote two modules, the OpenBase and the OpenBattery. OpenBase is a module with JTAG, mini USB Type-A for flashing a mote, an exten-der heaexten-der for the OpenMote-CC2538 mote and power supply through the mini USB Type-A ports. On the other hand, the OpenBattery has a built in support for 2-AAA batteries, a SHT21 temperature/ humidity sensor, a ADXL346 3-axis accelerometer sensor, a MAX4409 light sensor, four led lights and two buttons. Regarding the OS support for the OpenMote-CC2538 there is a wide range of IoT OS such as OpenWSN, ContikiOS, Thingsquare, FreeRTOS, RIOT. The performance evaluation of OpenMote-CC2538 have been demonstrated in [12]. The OpenMote hardware ecosystem is shown in Figure 2.4

2.4. Hardware

OpenMote-CC2538 OpenBattery OpenBase

Figure 2.4: The OpenMote hardware ecosystem: (from left to right) OpenMote-CC2538, OpenBattery and OpenBase

2.4.2 Tmote Sky

The Tmote Sky [24] is an ultra low-power 2.4GHz WSN module. The MCU of the Tmote Sky is a Texas Instruments MSP430F1611 clocked at 8MHz paired with 10KB of RAM and 48KB of flash. The development board comes with optional sensors like temperature/humidity sensor, light sensor, total solar radiation sensor, photo-synthetically active radiation sensor, a 10-pin expansion and a 6-pin expansion connectors. Further-more, the board provides an on-board JTAG controller and a USB 2.0 port. The radio module of Tmote Sky is a CC2420 module, which provides IEEE 802.15.4 connectiv-ity with a data rate up to 250Kbps. Tmote Sky is a low energy device with a power consumption as low as 5.1µA with the MCU on standby mode, while the maximum energy footprint of the device being less than 23mA. The device is compatible with TinyOS and ContikiOS.

2.4.3 Zolertia Z1

Zolertia Z1 is a low power WSN module compliant with IEEE 802.15.4 and ZigBee protocols that serves to help WSN developers to test and deploy their own applications and prototypes with the best trade-off between time of deployment and hardware flex-ibility. Z1 [25] was designed having in mind two main features: maximum backwards compatibility with the successful Tmote-like family motes while improving the per-formance in several aspects and maximum flexibility and expandability with regards to any combination of power-supplies, sensors and connectors. Its core architecture is based upon the MSP430 + CC2420 family of micro-controllers and radio transceivers by Texas Instruments, which makes it compatible with motes based on this same ar-chitecture. The radio operates in the 2.4GHz band and is fully compliant with IPv6 over Low-Power Wireless Personal Area Networks (6LoWPAN) and IEEE 802.15.4 standard. It has an optional external antenna and micro-USB connector for power and debugging. The Z1 is compatible with Tiny OS(2.X or higher), ContikiOS, OpenWSN.

Finally, the Zolertia Z1 mote is a power efficient WSN mote with a footprint less than 18.8mA. The main characteristics of the IoT devices described in this section are re-ported in Table 2.1 and more details can be found in [26].

Table 2.1: IoT Device Specifications

Mote Platform Processing Unit Clock speed RAM On-board Storage Radio Transceiver On-board Sensors OS Support OpenMote-CC2538 Cortex-M3 32MHz 32KB 512KB CC2538 temperature, humidity, light, accelerometer OpenWSN, ContikiOS, Thingsquare, FreeRTOS, RIOT Tmote Sky TI MSP430F1611 8MHz 10KB 48KB CC2420 temperature, humidity, light ContikiOS, TinyOS, MantisOS Zolertia Z1 TI MSP430F2617 16MHz 8KB 92KB CC2420 accelerometer, temperature ContikiOS, TinyOS, OpenWSN

2.5

In this section we briefly introduce all the software tools that we used to perform our experiments.

jMetal

jMetal is a Java-based framework mainly focused on development, experimentation and study of meta-heuristics for solving multi-objective optimization problems [27]. This framework includes a number of classic and modern state-of-the-art optimizers and genetic heuristic implementation, and it computes automatically all the Pareto Front (PF) quality indicators.

ILOG-CPLEX

ILOG OPL-CPLEX Development System is a rapid development system for optimiza-tion models adopting a high-level interface to embed models for solving Mixed Integer Linear Programming (MILP) problems [28].

Red Pitaya

Red Pitaya STEMlab [29] is an open-source experimental and measurement platform that has the advantages of ease of use, high performance-to-price ratio, and excellent performance. It is designed for various instrumentation purposes including signal gen-erator, oscilloscope, spectrum analyzer. It can be used as multifunction lab instrument, a data acquisition platform, a Software Defined Radio (SDR) transceiver, also as a teaching and learning tool. Device functionalities and data can be accessed through MatLab, Labview, Scilab and python Application Programming Interface (API). The

2.6. Operating Systems

analog front-end of Red Pitaya STEMlab has a 2×125 MS/s fast analog output RF channels and a 2×125 MS/s fast analog input RF channels, both with 50 MHz analog bandwidth. The hardware of the Red Pitaya STEMlab consists of a Zynq 7010 System on Chip (SoC) from Xilinx. The SoC integrates in a single device a dual core ARM Cortex-A9 and an Artix-7 FPGA. Red Pitaya runs Linux, which provides, among other features, different protocols for remote connection.

2.6

We take a look at the network stack of Contiki and OpenWSN OSs as shown in Fig-ure 2.5. This is necessary for the energy consumption measFig-urements that will be demonstrated in the Appendix section.

Contiki OS

Contiki OS is an open source, highly portable, multi-tasking OS for low-end IoT de-vices. Contiki OS follows a monolithic kernel architecture, making all components of the system to be developed together, thereby leading to a simpler and overall efficient design. Contiki code is available under Berkeley Software Distribution (BSD) license on GitHub2 _{and other platforms. In Contiki, processes run to completion, however,} event handlers can use internal mechanisms for preemption. Contiki maintains a queue of pending events, and events are dispatched to target processes in a First in First out (FIFO) manner. Contiki processes use lightweight protothreads [30] that provide a lin-ear, thread-like programming style on top of the event-driven kernel. Contiki follows a cooperative (non-preemptive) scheduling approach, where each thread is responsible to yield itself, because no other task, and in some cases not even the kernel, is able to interrupt a task. Contiki is written in the C programming language, and it is one of the most used OSs for constrained nodes, where its network stack is shown in Figure 2.5a. At the lower layer of the stack comprises of the PHY layer and the MAC layer. Tradi-tionally, duty cycling mechanisms are built into the MAC layer of the OSs networking stack. Contiki, however, employs duty cycling tactics in a separate level of the network-ing stack known as the RDC layer. Currently, Contiki provides various RDC protocols that follow the asynchronous paradigm, which relies heavily on low-power probing and low-power listening (LPL) including ContikiMAC [31], X-MAC [32].

Contiki uses CSMA-CA mechanism that places outgoing packets on a queue. Pack-ets from the queue are transmitted in order through the RDC layer. The RDC layer in turn transmits the packets through the radio link layer, which are IEEE 802.15.4 compli-ant. The MAC layer will retransmit packets until it sees a link layer acknowledgement from the receiver. If a collision occurs, the MAC layer does a linear back-off and re-transmits the packet. Outgoing Internet Protocol Version 6 (IPv6) packets flow from the IPv6 layer to the 6LoWPAN layer for header compression and fragmentation and more-over, the 6LoWPAN layer sends outgoing packets to the MAC layer. ContikiRPL [33] implements the RPL protocol, as specified in version 18 of the IETF RPL draft [16]. The ContikiRPL implementation separates protocol logic, message construction and parsing, and OF into different modules. Contiki uses Constrained Application Protocol (CoAP), which enables interoperability at the application layer through RESTful Web

RDC*

IPv6

6LoWPAN

CSMA

IEEE 802.15.4

ContikiRPL

UDP

CoAP/REST ENGINE

IEEE 802.15.4e

IPv6

6LoWPAN

IEEE 802.15.4

RPL

ICMP

ICMP

ICMP

CoAP

PCE

Figure 2.5: Network Stack of Contiki, OpenWSN Operating systems

services but with a lower cost in terms of bandwidth and implementation complexity than HyperText Transfer Protocol (HTTP)-based REST interfaces. Unlike HTTP over Transmission Control Protocol (TCP), CoAP uses User Datagram Protocol (UDP). OpenWSN Network Stack

OpenWSN project’s goal is to construct and provide a complete protocol stack based on open-source implementations of Internet of Things standards while being hardware independent [34]. OpenWSN comprises of a basic scheduler, and a Board Support Package (BSP), i.e., a simple hardware extraction, making it possible to run OpenWSN on a dozen IoT hardware platforms. OpenWSN code is available online under the BSD on GitHub3_{. OpenWSN is more of a network stack than a full-fledged OS. OpenWSN} is organized into two sub-projects: firmware and software. The firmware sub-project is the code that runs in embedded devices. It is written in standard C99 and uses the GCC as the default compiler, which enables compatibility of the firmware with AVR, ARM cortex and MSP processor architectures [35].

OpenWSN uses IEEE 802.15.4e as its MAC, which is an amendment to the well-known and widely used IEEE 802.15.4-2001 standard as shown in Figure 2.5b. IEEE 802.15.4-2015 is the improved version of IEEE 802.15.4e standard, which presents TSCH to achieve ultra-high reliability through frequency agility; and low-power through tight time synchronization. Synchronization accuracy directly relates to power con-sumption, and can vary from microseconds to milliseconds, depending on the hardware

2.6. Operating Systems

Table 2.2: Low-end IoT operating systems comparison

OS Architecture Programming Model Supported MCU families or Vendors Programming language Scheduling License

Contiki Monolithic Event-driven,

Protothreads AVR, MSP430, ARM7, ARM Cortex-M C Cooperative BSD OpenWSN

Monolithic Event-driven MSP430, ARM

Cortex-M C

non-preemptive scheduling with

priorities

BSD

and implementation. OpenWSN like most WSN OS utilizes the IETF 6LoWPAN for header compression that allow IPv6 packets to be sent and received over IEEE 802.15.4 based networks. It is mandatory to use a protocol that will find the multi-hop path connecting the nodes in the network with a small number of destination nodes, this functionality is achieved with the use of IETF RPL [16] protocol. Finally, on the upper layers we see both TCP and UDP with HTTP and CoAP respectively, with the CoAP over UDP being the most used combination due to the constraint resources. The main characteristics of the OSs described in this section are reported in Table 2.2.

CHAPTER

3

Throughput Maximizing Scheduler under

Interference Constraints

The key feature of TSCH networks is the scheduling of time slots and frequencies, which falls outside of the current standards. The TSCH scheduling task is an NP-hard problem [36]. Hence, most of the available scheduling algorithms use sub-optimal so-lutions, aiming at providing specific performance guarantees such as throughput, delay, fairness, just to mention a few.

In this chapter, we formulate the scheduling problem as throughput maximization and delay minimization. The throughput maximization problem is identified as combi-natorial optimization problem and NP-hard. For solving the throughput maximization scheduling problem, we propose a polynomial time algorithm by adopting a graph the-oretical approach, which introduce a tractable equivalent integer linear programming formulation. We examine and deliberate on some instances of the throughput maxi-mization scheduling problem with their combinatorial properties. We also introduce a novel auction-based heuristic algorithm to solve for the throughput maximization scheduling problem. A first-price sealed bid auction was used as the auction mecha-nism, where frequencies and time slots are considered as the auctioned resources and nodes as the bidders. Moreover, time complexity analysis of the algorithm is also pro-vided.

We made modifications to the throughput maximization problem by introducing deadline constraints. We address this problem by introducing a GA-based sub-optimal scheduler that yields a very close performance to the optimal scheduler. Finally, we evaluate all the algorithms performance through simulations. For the delay minimiza-tion problem, this is said to be a non-linear binary integer programming problem known to be NP-hard and can be solved using Branch-and bound algorithms.

3.1. Related Works

works and the system model is presented in Section 3.2. Next, we introduce the prob-lem formulation in Section 3.3. Section 3.4 presents the approaches and algorithms to address the throughput maximization problem. Section 3.5 provides the performance evaluation of the proposed schedulers with discussion and possible enhancements and finally Section 3.6 concludes the chapter with a summary.

3.1

Several schedule-based MACs have been proposed in the wireless networking litera-ture [37], [38], but they can not be applied to the TSCH MAC. Nonetheless, TSCH paradigm brings this topic into the focus of research again due to the following rea-sons: (a) IEEE 802.15.4-2015 standard defines the mechanism for a TSCH node to communicate, but the standard does not specify how to build an optimized schedule and to construct a schedule is policy specific; and (b) TSCH brings new opportunities and challenges because of its time synchronization multiplexed in frequency to improve reliability.

The TSCH scheduling task is an NP-hard problem [36]. Hence, most of the avail-able scheduling algorithms use sub-optimal solutions, aiming at providing specific per-formance guarantees such as throughput, delay, fairness, just to mention a few. The centralized approaches rely on a central entity where the scheduler resides. Farias et al.[39] proposed a queue-based algorithm for the path computation element to increase the reliability in industrial scenarios. The authors in [40] proposed a cross-layer low-latency topology management and TSCH scheduling technique that provides a very high time slot utilization to minimize communication latency. Palattella et al. de-veloped TASA [41], a centralized scheduler that exploits an innovative matching and colouring technique of graph theory to plan the distribution of time slots and channel offsets. The works in [39, 40] does not concern itself with throughput – a challenge we aim to handle in the paper. Other centralized scheduling approaches in IIoT-TSCH networks worth mentioning are [42], which maximizes the energy efficiency, and [43] addressing latency issues.

Under distributed algorithms, DeTAS [44] relies on exchanging traffic information based on neighbour-to-neighbour signalling. Jung et al. [45] proposed a scheduling algorithm to minimize the energy consumption while guaranteeing reliability. It works adaptively with traffic intensity and reliability requirements. Orchestra [13] is an au-tonomous scheduling mechanism, where each node independently builds its own sched-ule without any negotiation. While orchestra is flexible and able to achieve 99.99% packet delivery, it is unable to address bursty traffic. Further works in the literature have addressed the issue of bursty traffic [46]. In this paper, we focus on a centralized approach by providing a more compact scheduling model and accomplishing many tasks at the same time, since a centralized method has been demonstrated to be more efficient in practice [47]. The scheduling model is able to provide time, frequency and data rate allocation in a multi-node, multi-channel environment where nodes are equipped with multiple antennas for data transmission. The use of multiple transceivers can improve link quality and throughput, ensuring communication reliability [48]. This chapter is designed on maximizing the total throughput in an interference-aware system by proposing a polynomial time algorithm and an auction-based mechanism.

We shift from the above-mentioned techniques to addresses scheduling in TSCH networks using combinatorial properties based on Genetic Algorithms. The classic al-gorithms such as integer programming, branch-and-bound algorithm can achieve the global optimal solutions, but as a kind of NP-hard problem, the network optimization problem needs exponential time to be solved by using exact algorithms. To reduce the computational complexity and speed up the computation process, the use of heuristic methods such as GA can be presented.

The use of GAs has been proven to be quite successful for time slot and frequency assignment in both cellular networks [49] and satellite communications [50]. In IIoT, particularly the industrial wireless sensor network, the studies about the usage of GAs mainly revolve around the configuration of various sensor parameters such as symbol rate, modulation etc. [51], [52]. Other scheduling methods in IIoT networks worth mentioning that are applied in various applications are [53, 54] applied to smart factory and smart manufacturing, and [55] applied to smart cities.

The scheduling problem considered in this paper can be distinguished from other related works by introducing deadlines for job completion. Moreover, it differs from previous works due to TSCH attributes i.e. by accommodating the usage of differ-ent frequencies, the maximum allowable transmission rates of the frequency which are time-varying.

3.2

We consider a time-slotted IEEE 802.15.4-2015 network, where the nodes are managed by the gateway in a centralized manner as shown in Figure 3.1. The network consists of static nodes, and their locations are assumed to be known. Each node equipped with a radio has a communication range Rf, and the radio is assumed to transmit at a fixed transmission power. In addition, different channels can support different link capacities and transmission ranges. We are given a set of nodes nk where k ∈ {1, 2, · · · , N }, characterized by its frequency f ∈ {1, · · · , F } and its time slot t ∈ {1, · · · , T }. A communication graph G(V, E) is used to model the network, where every node k ∈ V corresponds to a device in the network, and there is a link e = (u, v) ∈ E if there exists a common channel available between u and v. Transmission is successful if the distance between them ku − vk ≤ Rf condition is satisfied.

At the beginning of the slot frame, each node nk calculates the transmission ca-pacity of the channel for each available frequency in time slot t, and transmits this information to the gateway in addition to the number of packets in its buffer (Qk). In this way, the gateway constructs a matrix U = [Uk,f,t], where Uk,f,t is the number of packets that can be transmitted by node k using frequency f in time slot t. Upon col-lection of all state information such as topology information, traffic generated by each node etc., the scheduler which resides at the gateway determines a transmission sched-ule applying its scheduling policy and broadcasts it to the nodes. The schedsched-uler decides on the time slot and frequency assignment with the goal of maximizing the throughput. Let Ck,f,t denote the Shannon’s capacity of the link lk,f,t between nk and the gate-way GW . Ck,f,t is a function of the signal-to-noise ratio SN Rk,f,t and represents the theoretical upper bound. In the calculation of Ck,f,t, only the background noise is

con-3.2. System Model and Assumptions

1

2

3

4

5

6

7

ڮ

T

1

2

3

ڮ

F

GW

Figure 3.1: TSCH Slot-Channel matrix where each nkmaintains a link with the gateway(GW ) for

both frequencyf and time slot t, where k ∈ {1, · · · , N }; f ∈ {1, · · · , F }, t ∈ {1, · · · , T }

sidered as we focus on an orthogonal frequency assignment as shown below:

Ck,f,t = Blog2(1 + SN Rk,f,t) (3.1)

where B is the channel bandwidth. Consequently, we can calculate the throughput that will be obtained if nktransmits at lk,f,t.

Mk,f,t = Ck,f,tT (3.2)

where T is the slot frame duration. Note that nkcan not transmit more than the number of packets in its buffer; Accordingly;

Uk,f,t = min(Mk,f,t, Qk) (3.3)

Xk,f,t =       

1 if node nktransmits using frequency f in time slot t;

0 otherwise;

(3.4)

~x = [Xk,f,t, k ∈ {1, · · · , N }; f ∈ {1, · · · , F }; t ∈ {1, · · · , T }] is the scheduling decision vector with elements Xk,f,t. Note that Xk,f,t is a function of the information available to nk. We calculate the total throughput in TSCH network as

M = N X k=1 F X f =1 T X t=1 Uk,f,tXk,f,t (3.5)

Interference and spectrum availabilities are constrained in the derivation of the formula for Uk,f,t. For instance, if a node k is very close to a node i that uses frequency f in time slot t, then node k cannot use frequency f in the same time slot, i.e., Uk,f,t = 0. Uk,f,tvalue quantifies the slot availabilities (i.e., the higher the Uk,f,tvalue is, the higher the data rate node k can have if it uses frequency f in time slot t). Uk,f,t values are in-put variables for the optimization problem in this paper. In the following, Uk,f is used instead of Uk,f,t because we assume that all parameters are to remain constant for each time-slot t of the slot frame period. The slot frame period is a time duration in which the network conditions remain fairly stable. For instance, in voice applications, the value of T tends to be fairly large.

3.3

In this section, we introduce the problem formulation for the throughput maximization and delay minimization.

3.3.1 Throughput Maximization Problem

Given the Uk,f values determined in the first phase, we introduce the binary integer linear programming to maximize the total throughput as follows:

P3.1: max N

X

X

X

U

X

3.3. Problem Formulation

X

f

Xk,f,t ≤ ak ∀k ∈ N ; ∀t ∈ T (3.9)

Xk,f,t ∈ {0, 1}; ∀k ∈ N ; ∀f ∈ F ; ∀t ∈ T (3.10)

In the problem formulation, the objective function in Equation (3.6) maximizes the total throughput of all the nodes in the TSCH network governed by the gateway. At least one time slot is allocated to each node as indicated by the constraint in Equation (3.7), thus achieving temporal fairness. Without this temporal fairness constraint in Equation (3.7), some nodes with bad channel conditions may end up not sending a packet for a long time. This constraint guarantees each node to send a packet. The constraint in Equa-tion (3.8) is used to prevent collision among the nodes, by guaranteeing that at most one node can transmit in a certain slot and frequency. Node k cannot transmit more frequencies than the number of antennas at the same time as indicated by constraint in Equation (3.9) because a node’s antenna can only tune to at most one frequency at a time, and finally constraint in Equation (3.10) indicates a binary decision variable. Note that, the problem formulation is valid for both single antenna i.e., ak = 1 ∀k ∈ N and multiple antennas i.e., ak > 1 ∀k ∈ N . The use of multiple antennas provides the need for simultaneous data transmission using different frequencies.

We assume in the simulations part of this work that the buffers of the nodes are continuously backlogged; i.e., there are always enough packets to be transmitted. This condition is relevant in order to adequately access our proposed scheduling algorithms by avoiding any possible traffic fluctuations.

3.3.2 Delay Minimization Problem

In this section, we formulate the scheduling problem in terms of delay minimization. The problem formulation is said to be a non-linear binary integer programming with linear constraints as shown below:

P3.2: min N X k=1 F X f =1 T X t=1 tUk,fXk,f,t N X k=1 F X f =1 T X t=1 Uk,fXk,f,t (3.11) s.t N X k=1 F X f =1 T X t=1 Uk,fXk,f,t > 0; (3.12) (3.7), (3.8), (3.9), (3.10) (3.13)

When Xk,f,t = 1, each one of Uk,f waits for t number of time slots, starting from the beginning of the schedule. Scheduling delay is used and refers to the number of time slots that a packet has to wait until its transmission; given that the packet is scheduled for transmission in that particular schedule. Therefore, the total scheduling delay of these Uk,fnumber of packets is equal to tUk,f. The numerator of the objective function in Equation (3.11) denotes the total scheduling delay experienced by all transmitted

packets in the schedule. It minimizes the scheduling delay in terms of time slots per packet. The constraint in Equation (3.12) is necessary to avoid the situation that the scheduler always selects the frequencies with which the nodes can send at most zero packets for the sake of reducing the average delay. Without (3.12), the scheduler can arrive at the irrational decision of having none of the nodes being able to transmit any packets, which would result in zero throughput. This constraint can be modified as follows F P f =1 T P t=1

Uk,fXk,f,t > Γ, where Γ is the required minimum total throughput value.

Branch and bound algorithms are usually used to solve this kind of problems [56].

3.4

3.4.1 Graph-Based Theoretical Approach

In this section, we propose a polynomial-time algorithm for the binary integer linear programming of the throughput maximization problem and investigate on some of the special instances of the problem.

Preliminaries

A polynomial time algorithm can be solved if the appropriate number of steps to com-plete the algorithm for a given input is O(ml) for some non-negative integer l, where m is the complexity of the input. This denote that the running time grows as a polyno-mial function of the size of the input. Unless P = N P , there is no polynopolyno-mial time algorithm for a given input size that finds an optimal solution for all instances of an NP-hard problem. A reasonable approach can be done by relaxing the requirements of finding the optimal solution and try to obtain a "good" solution that can be performed in polynomial time.

Let ∆ be a maximization problem formulation and let γ be a positive real num-ber, γ ≥ 1. A feasible solution s of an instance I of ∆ is a γ factor approximation if O∆(I, s) is at least a factor γ of O∗∆(I) of I, i.e., O∆(s) ≥

O∗_∆(I)

γ , where O∆(I, s) denotes the objective function value of solution s of instance I and O_∆∗ denotes the objective function value of an optimal solution of instance I. An algorithm is said to be a γ-approximation algorithm for a maximization problem ∆ if the algorithm returns a approximation for every instance I supplied to it. A problem ∆ is said to be γ-approximable if there is a polynomial-time γ-approximation algorithm for it. ∆ is said to be γ-inapproximable if there is no polynomial-time γ-approximation algorithm for it unless P = N P [57].

The essential concept is to reduce the variables of the problem such that it will be computationally more efficient and easy to solve. On this basis, an equivalent sim-pler problem formulation is proposed, which will be demonstrated as follows. Assume ∆ and ∆0 are two optimization problems such that the instances of one problem can be mapped onto instances of the other such that nearly optimal solution of ∆0 can be transformed back to yield nearly optimal solution of ∆. If there is an approximation algorithm for ∆0and an adequate approximation-preserving reduction from problem ∆ to problem ∆0, by composition, an approximation algorithm for ∆ also exists.

3.4. Throughput Maximizing Scheduling Algorithms

Lemma1. With the preliminaries explained, let ∆ be the optimization problem involv-ing only Xk,f,tvariables in the form of

T P t=1

Xk,f,tin its objective function O∆. We denote ∆0 to be the optimization problem obtained from ∆ by substituting

Yk,f = T X

t=1

Xk,f,t ∀k ∈ N ; ∀f ∈ F (3.14)

in O∆except constraints in Equation (3.8) – Equation (3.10). Constraints in Equation (3.8) – Equation (3.10) are replaced by the following constraints as shown below.

N X k=1 Yk,f ≤ T ; ∀f ∈ F (3.15) F X f =1 Yk,f ≤ akT ; ∀k ∈ N (3.16) Yk,f ∈ {0, T }; ∀k ∈ N , ∀f ∈ F (3.17)

Then ∆ and ∆0 are equivalent under the approximation-preserving reduction condi-tions.

Proof. The two optimization problems ∆ and ∆0are related. It is adequate to show that X of ∆ can be converted to a solution Y of ∆0 with O∆0(Y ) = O_∆(X) in polynomial time and vice versa. This holds for an optimum solution X∗ which makes both prob-lems to have the same optimal solution and a γ-approximated solution for one problem corresponds to a γ-approximated solution for the other.

With a solution X of ∆, the solution Y defined in Equation (3.14) clearly satisfies all constraints except Equation (3.8) – Equation (3.10). Constraints in Equation (3.15) – Equation (3.17) are obtained by summing up T inequalities of Equation (3.8) – Equa-tion (3.10) respectively, each of which is satisfied by our assumpEqua-tion.

Under the approximation-preserving reduction conditions, ∆ and ∆0 are equivalent. Given ∆0, the throughput maximization scheduling problem is equivalent to finding the vector Y given the following ILP formulation.

P3.3: max N

X

X

U

Y

It can be seen that the problem formulation (objective function and constraints) of ∆0 has less variables than ∆ formulation. With this, it is computationally easy to solve