Michael Lodi
email: michael.lodi@unibo.it

Informatical Thinking 1

Keywords: computational thinking, informatics, misconceptions, definition, disciplinary way of thinking, informatical thinking

In this paper, we reviewed many definitions of computational thinking, finding they share a lot of common elements, of very different nature. We classified them in mental processes, methods, practices, and transversal skills. Many of these elements seem to be shared with other disciplines and resonate with the current narrative on the importance of 21st-century skills. Our classification helps on shedding light on the misconceptions related to each of the four categories, showing that, not to dilute the concept, elements of computational thinking should be intended inside the discipline of Informatics, being its "disciplinary way of thinking".

Introduction 2

The expression computational thinking (CT, from now on) seems to have been firstly used in print by Seymour [START_REF] Papert | Mindstorms: Children, Computers, and Powerful Ideas[END_REF] and then was brought to the attention of the informatics community by Jeannette [START_REF] Wing | Computational thinking[END_REF].

From 2006, a considerable body of literature has been produced to search for a better definition of this concept, to provide tools and frameworks, to introduce and assess CT in K-12 education.

Even if there is no agreement between authors, a lot of proposed definitions stress the fact that CT is not only about technical methods and practices, but also about mental processes and transversal competences 3 like creativity, collaboration, tolerance for ambiguity, resilience, and more. However, educational and psychological research warns about optimistic claims on the transfer of competences from a discipline to other far domains and to general skills.

In this paper, we review some of the most important definitions emerged in the last years and propose a classification of the common elements that can be useful to better frame the misinterpretations of the concepts.

We will argue that CT must maintain its bond with informatics, representing its "disciplinary way of thinking".

Definitions of computational thinking 4

The expression "computational thinking" was brought back to the informatics community by [START_REF] Wing | Computational thinking[END_REF], gaining massive attention 5 . In that seminal article, Wing did not give a definition, but related the concept to informatics, stating "Computational thinking involves solving problems, designing systems, and understanding human behavior, by drawing on the concepts fundamental to computer science", arguing that "thinking like computer scientists" would be a benefit for everyone, not just for professionals or scientists.

In these years, many definitions have been proposed. In [START_REF] Corradini | Conceptions and Misconceptions about Computational Thinking among Italian Primary School Teachers[END_REF] authors started from five of the most important definitions to find out constituting elements of CT. [START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF] schematized many of the definitions proposed from Papert's views up to 2017. We review all of them in the following table. In the third column, we provide pointers to the classification that we will propose in Section 3.

Paper

Description Elements (Sec. 3) [START_REF] Wing | Computational thinking[END_REF] In her seminal article, Wing informally defines CT as "thinking like computer scientists".

1)

Wing (2008,2011) Wing defines more formally CT as "the thought processes involved in formulating problems and their solutions so that the solutions are represented in a form that can be effectively carried out by an information-processing agent". This definition is attributed to Jan Cuny, Larry Snyder, and Jeannette M. Wing, in an unpublished work from 2010: "Demystifying Computational Thinking for Non-Computer Scientists," referenced by [START_REF] Wing | Research notebook: Computational thinking-What and why[END_REF] herself. Moreover, Wing says it was originated by a discussion with Alfred Aho.

Wing also identifies characteristic elements of CT. In particular, she states the most important elements are abstraction (the "mental" tool of computing) and automation (by using a computer, the "metal" tool of computer scientists): "computing is the automation of our abstractions" [START_REF] Wing | Computational thinking and thinking about computing[END_REF]. [START_REF] Wing | Research notebook: Computational thinking-What and why[END_REF] recognises significant overlapping or inclusions between CT and other types of thinking: logical thinking, algorithmic thinking, parallel thinking, compositional reasoning, pattern matching, procedural thinking, and recursive thinking. [START_REF] Aho | Ubiquity Symposium: Computation and Computational Thinking[END_REF] Alfred Aho provides a definition very similar to the Cuny-Snyder-Wing one, more focused on "algorithmic thinking": "We consider computational thinking to be the thought processes involved in formulating problems so their solutions can be represented as computational steps and algorithms."

1) d) 2) a) 1) a) b) 2) c) e) f)
It is worth noticing that Aho stresses, in particular, the role played in this definition by the information processing agent, and that computational thinking should be based on clearly defined models of computation.

 Data Collection  Data Analysis  Data Representation  Problem Decomposition  Abstraction 1) a) c) d) f) 2) a) b) c) d) e) 4) b) d) e)
 Algorithms and Procedures  Automation  Simulation  Parallelization Google (n.d.) Google assumes the same ISTE/CSTA definition but -instead of a vocabulary -lists and (re)defines a series of CT concepts, pointing out that they are mental processes or tangible outcomes:

 Abstraction  Algorithm Design  Automation  Data Analysis  Data Collection  Data Representation  Decomposition  Parallelization  Pattern Generalization  Pattern Recognition  Simulation 1) a) c) d) e) f) 2) a) b) c) d) Brennan & Resnick (2012)
o expressing o connecting o questioning 1) a) c) d) 2) b) c) f) 3) a) b) c) 4) a) b) c)
1) a) b) c) d) e) f) 2) e) 3) a) b) 4) a) b) e)
Grover and After a literature review, assumed the

c) d) f) 2) b) c) d) e) f)
3) b) [START_REF] Selby | Computational thinking: The developing definition[END_REF] In a widely referenced Technical Report, Selby and Woollard examined a number of CT definitions, and argued that the most relevant and useful elements are:

 thought process  abstraction  decomposition  algorithmic thinking  evaluation  generalization 1) a) c) d) f)
2) e)

1) a) d) e) f) 2) b) d) e) f) 3) b) 4) a) d) e)
o Thinking in levels o Communicating Informations about a System o Defining Systems and Managing Complexity [START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF] They view CT as a "complex higher-order thinking, skills may require to use the power of human cognitive ability and embrace the support of machines to think and solve problems." They propose a "Framework for Computational Thinking as a Problem Solving Process" in five steps.



) c) d) e) f) 2) a) b) c) d) e) 3) b) 4) a)
Krauss and Prottsman (2016)

Krauss and Prottsman define6 CT as using thinking patterns and processes to pose and solve problems or prepare programs for computation.

Lessons plans are given for the following categories:  Decomposition (data analysis)  Pattern matching (data visualization)  Abstraction (data modelling, pattern generalization)  Automation (algorithm design, parallelization, simulation)

1) a) c) d) e) 2) a) b) c) d) 4) a) Shute et al. ( 2017
)
After an extensive literature review, they provide a very general definition of CT: "the conceptual foundation required to solve problems effectively and efficiently (i.e., algorithmically, with or without the assistance of computers) with solutions that are reusable in different contexts.". They then recognize the following categories and subcategories, giving however explanations that are quite general and far from Informatics.

 Decomposition  Abstraction (data collection and analysis, pattern recognition, modelling)  Algorithms (algorithm design, parallelism, efficiency, automation)

 Debugging  Iteration  Generalization 1) a) c) d) e) f) 2) a) b) c) d) e) 3) a) b) 4) a)
College Board (2017)

Proposes a CT framework for the AP CS Principles course, made of six practices.

 Connecting Computing o Identify impacts of computing. o Describe connections between people and computing. o Explain connections between computing concepts.  Creating Computational Artifacts

o Create a computational artifact with a practical, personal, or societal intent. Denning and Tedre, in their book about CT, proposed the following definition: Computational thinking the mental skills and practices for  designing computations that get computers to do jobs for us, and  explaining and interpreting the world as a complex of information processes. Moreover, they distinguish between "CT for beginners" (the one that is spreading in K-12 education, teaching basic computational problem solving) with "CT for professionals" (the one used by cutting-edge engineers and scientists in all fields as a powerful professional tool). They recognize CT has six important dimensions, "windows" looking at CT:

1) a) d) 2) b) d) e) 3) b) 4) a) b) c) o Select
 Computing & Society 1) a) b) c) d) e) f) 2) a) b) d) e) 3) b) 4) a) b) c) o
 Methods  Machines  Computing Education  Software Engineering  Design  Computational Science 4) a) c)
2) a) d)

Comparison

We compared the CT elements found in the analysed definitions.

Those who give a precise definition agree on the fact that CT is a way of thinking (thought process) for problem solving. They all somehow specify that it is a computational (rather than general) problem solving: the formulation and the solution of the problem must be expressed in a way that allows an "external" processing agent (a human or a machine) to carry it out.

Apart from the general statement, all definitions list some constitutive elements of CT. These elements are of very different kinds (from thinking habits to specific programming concepts), and many authors group them in categories, but there is no universal agreement on the classification.

We classified all the elements into four categories. For each category, we list the elements, trying to summarise all aspects stated in the analysed definitions. Instead of an "intersection approach", keeping only the elements that had a wider consensus (like what was done by [START_REF] Selby | Computational thinking: The developing definition[END_REF]), we used a "union approach", trying to build a comprehensive list of all the characteristics proposed by different authors. 1) Mental/thought processes: mental strategies useful to solve problems.

a) Algorithmic thinking: use algorithmic/procedural thinking (ISTE & CSTA, 2011b; [START_REF] Wing | Computational thinking and thinking about computing[END_REF][START_REF] Wing | Research notebook: Computational thinking-What and why[END_REF] to design a sequence of ordered step (instructions) to solve a problem, achieve a goal or perform a task [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF][START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF]Google, n.d [START_REF] Wing | Research notebook: Computational thinking-What and why[END_REF] and reasoning to make sense of things, establish and check facts [START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF]. Also recognised by [START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF]. c) Problem decomposition and modularisation: split a complex problem into simpler subproblems to solve it more easily [START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF]Google, n.d.;ISTE & CSTA, 2011a); modularise [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF]; use compositional reasoning [START_REF] Wing | Computational thinking and thinking about computing[END_REF]. Also recognised by [START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF][START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF][START_REF] Krauss | Computational Thinking and Coding for Every Student: The Teacher's Getting-Started Guide[END_REF][START_REF] Selby | Computational thinking: The developing definition[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF]. d) Abstraction: get rid of useless details to focus on relevant information or ideas [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF][START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF]Google, n.d.;ISTE & CSTA, 2011a;[START_REF] Wing | Research notebook: Computational thinking-What and why[END_REF]. Also recognised by (College Board, 2017;[START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF][START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF][START_REF] Krauss | Computational Thinking and Coding for Every Student: The Teacher's Getting-Started Guide[END_REF][START_REF] Selby | Computational thinking: The developing definition[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF][START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF]. e) Pattern recognition: discover and use regularities in data and problems [START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF]Google, n.d.;[START_REF] Wing | Research notebook: Computational thinking-What and why[END_REF]. Also recognised by [START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF][START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF][START_REF] Krauss | Computational Thinking and Coding for Every Student: The Teacher's Getting-Started Guide[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF][START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF]. f) Generalisation: use discovered similarities to make predictions or to solve more general problems [START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF]Google, n.d.;[START_REF] Iste | Operational Definition of Computational Thinking for K-12 Education[END_REF]. Also recognised by [START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF][START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF][START_REF] Selby | Computational thinking: The developing definition[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF][START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF]. 2) Methods: operational approaches widely used by computer scientists.

a) Automation: automate the solutions (ISTE & CSTA, 2011b; [START_REF] Wing | Computational thinking and thinking about computing[END_REF]; use a computer or a machine to do repetitive tasks (Google, n.d.;ISTE & CSTA, 2011a). Also recognised by [START_REF] Denning | Computational Thinking[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF][START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF][START_REF] Krauss | Computational Thinking and Coding for Every Student: The Teacher's Getting-Started Guide[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF]. b) Data collection, analysis and representation: gather information/data, make sense of them by finding patterns, represent them properly (Google, n.d.;ISTE & CSTA, 2011a); store, retrieve and update values [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF]. Also recognised by (College Board, 2017;[START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF][START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF][START_REF] Krauss | Computational Thinking and Coding for Every Student: The Teacher's Getting-Started Guide[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF][START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF]. c) Parallelisation: carry out tasks simultaneously to reach a common goal [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF]Google, n.d.;ISTE & CSTA, 2011a), use parallel thinking [START_REF] Wing | Research notebook: Computational thinking-What and why[END_REF]. Also recognised by [START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF][START_REF] Krauss | Computational Thinking and Coding for Every Student: The Teacher's Getting-Started Guide[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF]. d) Modelling and simulation: represent data and (real world) processes through models (Google, n.d.;[START_REF] Iste | Operational Definition of Computational Thinking for K-12 Education[END_REF], run experiments on models (ISTE & CSTA, 2011a). Also recognised by (College Board, 2017;[START_REF] Denning | Computational Thinking[END_REF][START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF][START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF][START_REF] Krauss | Computational Thinking and Coding for Every Student: The Teacher's Getting-Started Guide[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF][START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF]. e) Analysis and evaluation: implement and analyse solutions (ISTE & CSTA, 2011a) to judge them [START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF], in particular for what concerns effectiveness, and efficiency in terms of time and resources. Also recognised by (College Board, 2017;[START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF][START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF][START_REF] Selby | Computational thinking: The developing definition[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF][START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF]. f) Programming: use some common concepts in programming (e.g. loops, events, conditionals, mathematical and logical operators [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF], recursion [START_REF] Wing | Research notebook: Computational thinking-What and why[END_REF]). Also recognised by [START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF].

3) Practices: typical practices used in the implementation of computing machinery based solutions.

a) Experimenting, iterating, tinkering: in iterative and incremental software development, one develops a project with repeated iterations of a design-build-test cycle, incrementally building the final result [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF]; tinkering means trying things out using a trial and error process, learning by playing, exploring, and experimenting [START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF]. Also recognised by [START_REF] Shute | Demystifying computational thinking[END_REF]. b) Test and debug: verify that solutions work by trying them out [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF]; find and solve problems (bugs) in a solution/ program [START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF]. Also recognised by (College Board, 2017;[START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF][START_REF] Kalelioğlu | A Framework for Computational Thinking Based on a Systematic Research Review[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF][START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF]. c) Reuse and remix: build your solution on existing code, projects, ideas [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF]. 4) Transversal skills: general ways of seeing and operating in the world fostered by thinking like computer scientists; useful life skills that can enhance thinking like a computer scientist. a) Design and create: design and build things [START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF] and computational artifacts, use computation to be creative and express yourself [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF] [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF][START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF][START_REF] Iste | Operational Definition of Computational Thinking for K-12 Education[END_REF]. Also recognised by (College Board, 2017;[START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF]. c) Reflect, learn, meta-reflect, understand the world computationally: use computation to reflect and understand computational aspects of the world [START_REF] Brennan | New frameworks for studying and assessing the development of computational thinking (Using artifact-based interviews to study the development of computational thinking in interactive media design[END_REF], identify impacts of computing on society (College Board, 2017). Also recognised by [START_REF] Denning | Computational Thinking[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF]. d) Be tolerant for ambiguity: deal with non-well specified and open-ended, real-world problems [START_REF] Iste | Operational Definition of Computational Thinking for K-12 Education[END_REF]. Also recognised by [START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF]. e) Be persistent when dealing with complex problems: be confident in working with difficult or complex problems (ISTE & CSTA, 2011a), persevering, being determined, resilient and tenacious [START_REF] Csizmadia | Computational thinking-A guide for teachers[END_REF]. Also recognized by [START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF].

CT as Informatics "disciplinary way of thinking"

Note that many of the cited elements in the previous classification are broad and general. This led to some critiques (for an overview, see Martins-Pacheco al. ( 2020)): some of these concepts are not exclusively associated with Informatics, but taught in other disciplines (e.g., Math and Sciences) or are general skills that children have been learning for a long time before the birth of Informatics. [START_REF] Cansu | An Overview of Computational Thinking[END_REF], summarising critics from Hemmendinger (2010), stated for example that:

 Reformulating hard problems is typical of all domains of problem solving,  Philosophers have been thinking about thinking -recursively -for a long time,  Mathematics surely uses abstraction, and so do all disciplines that build models,  Separation of concerns and using heuristics also characterizes problem-solving in general. By contrast, other authors argue that computing features extend and differentiate these elements from other domains [START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF], and provide some characteristic problem-solving methods (e.g., the possibility to effectively execute a solution, a model, an abstraction by running an implementation of its algorithm [START_REF] Martini | Lingua Universalis[END_REF]).

We agree, arguing that Informatics is what needs to be taught in schools, and CT is, at most, the conceptual sediment of that teaching, what remains even when the technical aspects have been forgotten [START_REF] Lodi | Do we really need computational thinking? Mondo Digitale[END_REF].

In other disciplines, like Math, it is recurrent to talk about mathematical thinking (Sternberg & Ben-Zeev, 1996), or mathematical reasoning [START_REF] English | Mathematical Reasoning: Analogies, Metaphors, and Images[END_REF], or mathematical problem solving [START_REF] Schoenfeld | Mathematical Problem Solving[END_REF].

Like what mathematical thinking is for Math, CT is Informatics "disciplinary way of thinking" [START_REF] Pace | Decoding the Disciplines: Helping Students Learn Disciplinary Ways of Thinking: New Directions for Teaching and Learning[END_REF] (and this explains the provocative title "Informatical thinking"). [START_REF] Chick | From generic to signature pedagogies: Teaching disciplinary understandings[END_REF], talking about signature pedagogies (pedagogies to "engage students in the ways of knowing, the habits of mind, and the values shared by experts in [a] field" (Gurung et al., 2009, p. xvii)), affirms that "effective teaching results from core values and principles of our courses and of our disciplines, rather than from generic views of learning. […] higher-level thinking is inhibited by such generic conceptions and lays the groundwork for questions about the central values, habits, and ways of thinking within their disciplines" (Chick et al., 2009, p. 4).

According to Li et al. (2019, p. 8) […] domain-specific thinking and domain-general thinking are not dichotomous, as thinking itself is a complex process involving many different components. Domain-general thinking is often derived from human's thinking performance across different knowledgelean (e.g., solving a puzzle) or -rich task domains (e.g., solving algebraic equations). Domain-specific thinking is often characterized in terms of its disciplinary content but also involves more general cognitive components. In other words, domain-specific thinking should contain both domain-specific and -general aspects of cognitive activities. For example, a mathematician's thinking is scarcely only mathematics (the knowledge component). It can share possible common elements with a biologist's thinking (e.g., certain aspects of metacognition and meta-representation). The same reasoning applies to students' thinking in specific disciplines. […] some aspects of mathematical problem solving are largely discipline specific (e.g., the knowledge base), some heavily disciplineoriented (e.g., strategies and beliefs), some much like discipline domain-general (e.g., metacognition). While we agree disciplinary thinking contains both specific and general aspects, we keep spotting the tendency of educators and policymakers to focus, for what concerns CT, only on the more general ones. [START_REF] Voogt | Computational thinking in compulsory education: Towards an agenda for research and practice[END_REF] recognise, in some of the abovementioned definitions of CT, a tension between "the 'core' qualities of CT versus certain more 'peripheral' qualities". The latter highly overlap with what we called "transversal skills," and we agree with Voogt that this "runs the risk of diluting the idea of CT, blurring and making it indistinct from other 21st century skills".

As CT movement has grown in educational contexts, many unverified claims about the effects of learning CT/Informatics has emerged (e.g., that it will automatically transfer to thinking logically, better problem solving in every aspect of life, developing perseverance, getting better results in math and science, and so on [START_REF] Lewis | Good (and Bad) Reasons to Teach All Students Computer Science[END_REF]). Most of these claims are not supported by research, and "appear in blog posts, opinion pieces, and other 'grey literature'" (Duncan, 2019, p. 32). As Denning & Tedre (2019, p.xiii) put it:

[CT] is sometimes portrayed as a universal approach to problem solving. Take a few programming courses, the story in the popular media goes, and you will be able to solve problems in any field. Would that this were true! Your ability to solve a problem for someone depends on your understanding of their context in which the problem exists. For instance, you cannot build simulations of aircraft in flight without understanding fluid dynamics. You cannot program searches through genome databases without understanding the biology of the genome and the methods of collecting the data. Computational is powerful, but not universal. As we will see, non-specialist teachers that most probably never studied Informatics in their schooling or training may tend to stick to some "general versions" of the listed characteristics (and especially on the peripheral qualities), not necessarily related to Informatics.

We believe, by contrast, CT must be understood inside Informatics: while many characteristics are (more or less apparently) shared with other disciplines, we need to focus on their specific "informatical" instantiation.

We believe that the classification we proposed in the previous section is a good tool to frame the misconceptions about CT and Informatics in K-12 education [START_REF] Denning | Remaining Trouble Spots with Computational Thinking[END_REF][START_REF] Denning | Misconceptions about Computer Science[END_REF]. In the next four subsections, we will discuss in this light the four main categories we recognised.

Mental Processes

Mental processes are, on the surface, shared with other disciplines, but should be understood and experienced as Informatics specific. "CT draws on a rich legacy of related frameworks as it extends previous thinking skills" (Lee et al., 2011, p. 32).

First of all, analysed definitions are clear in stressing on the computational (rather than general) nature of problem solving. In facts, many authors (recall for example Aho's position) agree that what differentiates algorithmic thinking (which has been used for centuries, firstly by mathematicians) and computational thinking is the automation of the algorithm [START_REF] Stephens | Computational/Algorithmic Thinking[END_REF].

Next, as diSessa points out, abstraction, one of the core CT concepts according to Wing and many others, has different nuances in different disciplines:

Mathematical abstraction (let's call it, inferential abstraction) occurs in order to build conceptual worlds where a small set of attributes fully define entities, resulting in a substantial inferential fabric-a family of basic ideas and secure inferences (proofs) from them to other ideas (theorems). Abstraction in physics (empirical abstraction) is taking a look at the world and finding in it new things that cut away certain details, but build on others that might initially be completely ignored, in order to create core models that apply across a very wide range of circumstances. Mathematicians do not, in general, need or use the skill of "peeling away" from the world as it exists, nor digging through the difficulties of finding out how the world is in the first place, nor do they have the constraint of confirming empirically that the world admits in a certain abstraction, usually within prescribed limits. Abstraction in computer science (practical abstraction) resides substantially in peeling away the irrelevant particulars of an implementation so that one only need think about the features of a piece of it that are essential for a given use-its "contract" with the rest of the program. (diSessa, 2018, p. 21) Moreover, it is hugely debated if general skills (like general problem solving, critical thinking, creative thinking, decision making, and so on) exist, are transferrable or even teachable (for a comprehensive review, see (Lodi, 2020, ch. 4)). For example, [START_REF] Gick | Analogical problem solving[END_REF] found that problem decomposition, one of the most highlighted aspects of CT [START_REF] Guzdial | A new definition of Computational Thinking: It's the Friction that we want to Minimize unless it's Generative[END_REF], is not easily transferrable. They described to students a situation where an army had to be divided into small groups to successfully attack a fortress; immediately after they asked the students how to attack a tumour with a laser without damaging healthy tissues. The vast majority of the students were not able to use the same approach (divide the laser in multiple weaker beams). They only managed to do so when explicitly prompted to think at the army example.

That is why these skills should be taught in an Informatics-specific context.

Informatics methods

Many methods are, again, shared with other disciplines, but we believe they must be experienced in the context of automatic elaboration of information. Emblematic examples are unplugged activities, teaching activities not using a computer or tablet or smartphone to teach informatics concepts and methods. After experiencing the activities without computers, it is essential to relate what students have done to the specific informatics context, to understand what happens on physical devices. [START_REF] Bell | CS Unplugged-How Is It Used, and Does It Work[END_REF] suggest that Unplugged activities offer best results when used in combination with "plugged (i.e. programming tasks). Using unplugged activities before the plugged one seems to foster even more effective results than the programming activities alone.

Two early studies discovered that, without this explicit connection, "the program [based on CS Unplugged] had no statistically significant impact on student attitudes toward computer science or perceived content understanding " [START_REF] Feaster | Teaching CS Unplugged in the High School (with Limited Success)[END_REF] and that "the students' attitudes and intentions regarding CS did not change in the desired direction" [START_REF] Taub | CS Unplugged and Middle-School Students' Views, Attitudes, and Intentions Regarding CS[END_REF].

Informatics practices

Listed practices are, of course, shared with other disciplines and activities. As we will also discuss for transversal competences, we should not justify the introduction of Informatics in K-12 education mainly for teaching this kind of general approaches (which have been used and taught for centuries before the advent of Informatics).

However, we agree that computers are powerful tools to "concretely experiment with". This is one aspect of the constructionist learning theory from Seymour Papert (see Lodi (2020, chapters 3, 6)).

Already in 1970, Papert and colleagues, while designing and experimenting with the LOGO programming language, noted [START_REF] Feurzeig | Programming-Languages as a Conceptual Framework for Teaching Mathematics[END_REF] that the peculiarities of computer programming make it a privileged tool for learning problem solving with an experimental approach. In fact, children have to impose on themselves rigour and precision in instructing the computer -being explicit and precise is not imposed (incomprehensibly) by enforcement of the teacher, but naturally emerges from the need of being understood by an automated executor with a limited instruction set, which is unable to perform any "human" inference. Briefly: the computer creates an intrinsic motivation to learn by trial, error and debug.

Transversal competences

Transversal competences like perseverance and tolerance for ambiguity are useful for learning a difficult topic like Informatics, but including it in the definition may cause people to think CT is mainly about these competences.

For example, Corradini et al. (2017a) found that teachers saw the value of Programma il Futuro project (the Italian version of Code.org) more in fostering transversal competences or domain-general skills (like promotion of awareness and comprehension of problem solving, logical thinking, creativity, attention, planning ability, motivation for learning, students interest, cooperation) than in teaching Informatics core concepts.

The same sample [START_REF] Corradini | Conceptions and Misconceptions about Computational Thinking among Italian Primary School Teachers[END_REF] struggled to give a sound and complete definition of CT, focusing on some crucial aspects like problem solving, mental processes, logic, but often forgetting to refer in any way to an information-processing agent, giving a very partial view of Informatics. Moreover, many of them mentioned transversal competences, which hints the view of Informatics as an instrumental discipline, not valuable in itself. This is possibly deriving from attempts to convince teachers of the importance of CT by focusing mainly on its value for other disciplines and as a general learning tool.

Moreover, non-specialists may get the wrong direction of the implication: while researchers agree that competences like perseverance, dealing with complexity, and collaboration are essential to succeed in Informatics, which is a challenging subject [START_REF] Murphy | Dangers of a Fixed Mindset: Implications of Self-Theories Research for Computer Science Education[END_REF], the opposite implication (CT fostered by these skills) is far from being proved.

For example, Lewis (2017, p. 18) states that "programming has been speculated to be uniquely qualified to help normalize failure and thus encourage productive learning strategies". However, research in education tells us that transfer is difficult and unlikely to happen, especially between knowledge domains far from one another, and especially when treating domain-general skills [START_REF] Guzdial | Learner-Centered Design of Computing Education: Research on Computing for Everyone[END_REF][START_REF] Lewis | Good (and Bad) Reasons to Teach All Students Computer Science[END_REF].

At the moment, there is no proof that transversal skills like perseverance are automatically fostered by learning CT (for examples, we found no difference in students' mindset, with respect of studying or not studying Informatics at school [START_REF] Lodi | Does Studying CS Automatically Foster a Growth Mindset[END_REF]).

Conclusions

The expression "computational thinking" has become a buzzword related to the introduction of CS in K-12 education. Although it had already been used in the 80s by Papert, it started to be massively in Informatics education after being re-proposed by Wing. Many authors tried to define CT: despite being quite different, the most famous definitions share many characteristics. All agree CT is a form of thinking for solving problems by expressing the solution in a way that can be automatically carried out by an (external) processing agent. We identified four categories of CT constitutive elements proposed by authors: mental processes, methods, practices, and transversal skills. We argued that this classification could be useful to frame misconceptions about CT.

Mental processes (e.g., problem solving, problem decomposition, abstraction, logical thinking) and transversal competences (e.g., tolerance for ambiguity, perseverance) resonate with the current narrative on the importance of the 21st-century skills, and are probably even one of the reasons of the widespread of CT in education. This is confirmed by large scale qualitative studies (Corradini et al., 2017a), showing that generalist teachers mainly find value in introducing CT in schools for promoting general skills rather than Informatics core concepts.

However, educational research warns about the transferability of this kind of general skills between disciplines, and some even doubt their teachability.

Moreover, putting too much focus on this aspects risks to dilute the fundamental concepts that distinguish CS from other disciplines (e.g., the presence of a precise external executor that solves problems following provided algorithms, the possibility to describe and execute abstractions through specific languages, the possibility to simulate worlds, and so on). The definitions of CT contain many elements directly linked to CS methods (e.g., automation, data analysis, evaluation) and programming practices (e.g., iterating, debugging). However, educators may fail to include references to these CS specific aspects in their definition of CT.

Since even more specific concepts appear to be shared with other disciplines, the message that teaching separately some of these concepts (often in an informatics-unrelated way) -or simply recognising them inside other disciplines (like math for problem solving, geography for giving precise directions, and so on) -will automatically foster CT is spreading between educators.

We therefore argued that all the characteristics, especially the "core" ones, should be read, understood, and taught inside the discipline of Informatics. A lot of "thinking" are worth being taught, CT "is often a welcome addition to other fields, but not a replacement for their ways of thinking and not a meta-skill for all fields " (Denning & Tedre, 2019, p. 213).

CT should represent the "disciplinary way of thinking" of Informatics: Informatical thinking.

  appropriate techniques to develop a computational artifact. o Use appropriate algorithmic and information management principles.  Abstracting o Explain how data, information, or knowledge is represented for computational use. o Explain how abstractions are used in computation or modeling. o Identify abstractions. o Describe modeling in a computational context.  Analyzing Problems and Artifacts o Evaluate a proposed solution to a problem. o Locate and correct errors. o Explain how an artifact functions. o Justify appropriateness and correctness of a solution, model, or artifact.  Communicating Explain the meaning of a result in context. o Describe computation with accurate and precise language, notations, or visualizations. o Summarize the purpose of a computational artifact. Exchange knowledge and feedback with a partner or team member. o Review and revise their work as needed to create a high-quality artifact.

	Juškevičienė	After reviewing many definitions, Juškevičienė & Dagienė found eight CT
	& Dagienė	components groups.
	(2018)	 Data analysis & representation
		o Data collection
		o Data analysis
		o Data representation
		o Generalisation
		o Patterns finding
		o Drawing conclusions
		 Computing Artefacts
		o Artefact development
		o Artefact designing
		 Decomposition
		o Breaking into parts
		 Abstraction
		o Details suppression
		o Modelling
		o Information filtering
		 Algorithms
		o Sequence of steps
		o Procedures
		o Set of instructions
		o Automation
		 Communication & collaboration
		o Communication
		o Collaboration
		o Computational analysis

 Collaborating o Collaborate with another student in solving a computational problem. o Collaborate with another student in producing an artifact. o Share the workload by providing individual contributions to an overall collaborative effort. o Foster a constructive, collaborative climate by resolving conflicts and facilitating the contributions of a partner or team member. o

  .;ISTE & CSTA, 2011a). Also recognised by(College Board, 2017;[START_REF] Grover | Computational Thinking in K-12: A Review of the State of the Field[END_REF][START_REF] Juškevičienė | Computational Thinking Relationship with Digital Competence[END_REF][START_REF] Krauss | Computational Thinking and Coding for Every Student: The Teacher's Getting-Started Guide[END_REF][START_REF] Selby | Computational thinking: The developing definition[END_REF][START_REF] Shute | Demystifying computational thinking[END_REF][START_REF] Weintrop | Defining Computational Thinking for Mathematics and Science Classrooms[END_REF]. b) Logical thinking: use logical thinking

As cited inJuškevičienė and Dagienė (2018, p. 270)

Acknowledgements

I would like to thank Prof. Simone Martini for supporting my research.


Philippe Fabian
email: philippe.fabian][rachedi]@u-pem.fr

Abderrezak Rachedi

Dynamic selection of relays based on classification of mobility profile in a highly mobile context

Keywords: Mobile Relays, Machine Learning, Mobility Classification, Mobile Networks, Internet of Mobile Things

With an increasing amount of connected cars and devices having more and more sensors, the development of smart architectures and algorithms to efficiently transport data is a major concern. The selection of relays to allow users to connect to Internet is an important aspect in networks with high mobility, particularly in low-population areas having poor network coverage. Furthermore, cellular connectivity can be expensive for users. The solution proposed in this paper uses a machine learning based classification algorithm to select the best relays amongst any user based on their mobility profile. Not only this solution can be used on its own to enhance network performance without requiring a dedicated architecture, but it can be coupled with other algorithms as well to increase performance even more. Simulation results will show the proposition is able to scale up to several hundreds of users simultaneously, it improves the delivery rate of packets by up to a factor 2, it increases connectivity, generates less signaling and yields a more stable topology compared to a random selection or the use of static relays.

I. INTRODUCTION

Wireless mobile devices are more and more present in everyday life. All kinds of vehicles are equipped with sensors (cars, trucks, buses, bicycles, scooters, etc.) and are connected to Internet. Many people also carry a smartphone. All these devices generate traffic and the expected traffic from mobile users will reach 20% of the total IP traffic in the near future [START_REF] Index | Global mobile data traffic forecast update, 2016-2021 white paper[END_REF]. Also, most of the mobile traffic will be from cellular connections [START_REF] Index | Global mobile data traffic forecast update, 2016-2021 white paper[END_REF]. Networks must be designed accordingly in order to absorb such a huge quantity of data and to ensure Quality of Service (QoS). Although several users can directly connect to Internet using a 4/5G connection, it is not necessarily possible for everybody. High costs, lack of connectivity due to environmental factors or poorly serviced areas are a few examples where connecting a user can be an issue. One solution is to use relays to forward data from and to those users to allow them to have network access. Selecting which relays to use will have a major impact on performance and in specific contexts it is not always possible to have dedicated static relays (e.g. in a low populated area), as the cost to deploy them is too high compared to the amount of (potential) users. Furthermore, in a context where all users move, like the Internet of Mobile Things (IoMT), the constantly changing topology poses an even greater challenge to the selection process of relays. Indeed, some users can move far enough to leave the coverage area or a traffic jam can cause a section of a road to suddenly have a peak of network traffic due to a sudden increase in the number of users. In such situations, it can be hard to decide where to place static relays and relaying on Mobile Relays (MR) instead can greatly help in adapting the topology to this very dynamic context, without incurring a higher cost.

The selection of relays is a problem that was extensively studied [START_REF] Shamganth | A survey on relay selection in cooperative device-to-device (d2d) communication for 5g cellular networks[END_REF]. Most solutions focus on the selection of relay users connect to (detailed in section II). Relays -mobile or not -are usually dedicated devices as well. Several researchers propose solutions using Artificial Intelligence (AI), more specifically Machine Learning (ML) : such techniques allow to efficiently solve complex problems thanks to their capacity to adapt to dynamic contexts like in the case of mobility in wireless networks [START_REF] Zhang | Deep learning in mobile and wireless networking: A survey[END_REF]. ML is used in networking to address different problems, like routing [START_REF] Jiang | Unleashing the potential of data-driven networking[END_REF]. We have decided to focus on the process of selection of relays.

In this paper, we propose a novel solution that uses ML to classify users according to their mobility profile. Then, the best profiles amongst users are selected to act as mobile relays. Contrary to the state of the art, our solution does not require a dedicated infrastructure; it is thus able to adapt to a vast amount of different situations. A cellular antenna is still needed, though, as a mean to connect to Internet. Once MRs are selected, any routing protocol can be used to transport data. It is also possible to narrow down the set of selected MRs to improve performance even more by considering connectivity, lowest delay, energy consumption or any other metric seen as relevant. This makes the proposed solution suitable to couple with an existing routing protocol to greatly increase QoS. Furthermore, in this paper we study different mobility profiles together (car and bicycle), interacting with one another at the same time. To the best of our knowledge, other solutions consider motorized vehicles only which makes our approach original.

The remaining of this paper is organized as follows : state of the art is presented in section II, section III introduces the studied architecture and the proposed solution, simulation results are shown and discussed in section IV and the paper is concluded in section V.

II. RELATED WORK

As we will see in this section, most algorithms focus on the selection of dedicated relays or some information is supposed to be known a priori to aid the selection process. The first part (section II-A) is about classical algorithms whereas the second part (II-B) will cover algorithms using machine learning.

A. Classical algorithms

Classical algorithms are solutions that do not use ML to solve the problem at hand. Some examples include the use of matching theory [START_REF] Liu | Opportunistic mobility utilization in flying ad-hoc networks: A dynamic matching approach[END_REF], Markov chains [6] [7] or formulating the question as a maximization problem [START_REF] Alam | Relay selection and resource allocation for multi-user cooperative ofdma networks[END_REF].

Authors in [START_REF] Liu | Opportunistic mobility utilization in flying ad-hoc networks: A dynamic matching approach[END_REF] use Matching Game to anticipate future radio conditions of flying drones. The position and trajectory of drones are used to dynamically adjust the transmission mode of each one and to select which drones will forward data. However, in the context of vehicular it is not always possible to know the future trajectory of users.

In [START_REF] Li | A dynamic relay selection scheme for mobile users in wireless relay networks[END_REF], the authors propose a relay selection scheme where Mobile Users (MU) select relays according to a cost. The model is composed of a base station, several relays and MUs. The mobility of users is represented by a transition matrix and the problem is modeled using a constrained Markov decision process. Though the mobility of users is accounted for in this proposition, the use of dedicated relays constrains the problem.

The solution proposed in [START_REF] Alam | Relay selection and resource allocation for multi-user cooperative ofdma networks[END_REF] aims to maximize the system throughput by satisfying QoS requirements of users by considering a power constraint. The model is composed of one antenna, several fixed relays and users. The maximization problem allows to find the best relay for each user. However, given relays are dedicated units and no mobility is considered, the solution is not adapted in a highly mobile environment with potential relays moving in and out of the studied area.

In [START_REF] Liao | Mobile relay deployment in multihop relay networks[END_REF], the authors propose to add MRs to help manage high traffic periods of fixed relays in order to reduce signaling overhead and improve user mobility experience. High traffic periods are modeled using Markov chains. Though mobility is considered, MRs are supposed to be mounted on vehicles, such as buses and move at constant speed. This might not be adapted in areas with a low-population density.

Authors in [START_REF] Dao | Resource-aware relay selection for inter-cell interference avoidance in 5g heterogeneous network for internet of things systems[END_REF] propose a mechanism of relay selection to assist nodes showing high interference. The model is made of a macro cell antenna, a few pico cell antennae and several users. This solution is interesting as any node can potentially relay data to help another node. However, it uses static nodes and is not intended to use in a context with high mobility.

B. Machine learning based algorithms

ML algorithms use artificial intelligence to solve problems. In the case of supervised ML, the algorithm is first trained on a set of data where the output is known in advance. After this step, the algorithm is able to deduce the output on a set of data having the same nature as the training set.

In [START_REF] Mchergui | Relay selection based on deep learning for broadcasting in vanet[END_REF], the authors propose to use deep learning to select the best relays to enhance dissemination of data. The studied case is made of a road network with static Road Side Units (RSU) near the roads and vehicles moving around on the roads. Although the use of several features is good to make a more relevant choice, relays are static and dedicated units. This makes this solution non-adapted if deployment cost of the infrastructure is too high or if it is not possible to deploy a dedicated architecture at all. Authors in [START_REF] Abdelreheem | Deep learning-based relay selection in d2d millimeter wave communications[END_REF] propose to use deep learning to select the most appropriate relay for nodes suffering blocking of radio waves. A user that has bad radio conditions will consider several metrics for the deep learning algorithm to find a suitable relay. However, the presented architecture does not consider a user can connect to the base station through several hops.

In [START_REF] Zhou | A fuzzy-rule based data delivery scheme in vanets with intelligent speed prediction and relay selection[END_REF], the authors propose a powerful model using the K-nearest neighbors ML algorithm. They consider a vehicular network composed of several RSUs and many vehicles driving around. The idea is to connect a vehicle directly to a RSU if one is in range, otherwise it tries to find a path through other vehicles to connect to a RSU using several features. Though the model uses many relevant features in the context of mobility, it relies on static relays and only motorized vehicles are considered.

As aforementioned, state of the art solutions either require dedicated relays or make use of some information considered as known beforehand. We are convinced a more general approach is key in improving performance and in adding a great flexibility. This is why we propose a solution that only requires one cellular antenna to connect to Internet and a few users with cellular access to this antenna.

III. ARCHITECTURE AND CLASSIFICATION ALGORITHM

We first present the studied architecture (section III-A) before introducing the classification algorithm (section III-B).

A. Proposed architecture

As depicted in figure 1, we are in the context of IoMT. Different types of user are supposed to be present in the environment : soft mobility users such as bicycles or pedestrians and high mobility users like cars, trucks or buses. They can either connect to a nearby cellular antenna or they can connect to other users on the network. These users make the fog part of the architecture (see fig. 1). A user directly connected to the antenna can act as a mobile relay. Users that cannot directly connect to the cellular network connect to the MRs or to another user. The resulting topology is a tree where relays act as root of the topology they manage (it is the same kind of topology as in the Routing Protocol for Low-power and Lossy Networks (RPL), RFC 6550 [START_REF] Winter | Rfc 6550: Rpl: Ipv6 routing protocol for low-power and lossy networks[END_REF]). The other part of the architecture is the cloud part (as shown in fig. 1). It is composed of the cellular antenna used by users in the fog network and a control server (or controller). The antenna is connected to the controller via Internet with a wired link (fiber optic, for instance). The control server gathers users' data and runs the ML algorithm using this data (this is explained below, in section III-B).

Once the prediction is done, the topology can be built : figure 1 shows a network already set up : 2 users (1 car and 1 pedestrian) are directly connected to the antenna and they act as relay. The other users are connected to these relays or intermediate users to reach the antenna. In this paper, we focus on how the controller selects MRs in the fog part of the architecture. Given the topology is based upon RPL, the way a node (user) selects a parent to connect to is left to the developer. We have used a routing algorithm from previous work [START_REF] Fabian | Fuzzybased Objective Function for Routing Protocol in the Internet of Things[END_REF] that we will not detail here, as it is out of the scope of this article. The following section presents the proposed ML algorithm more in detail.

B. Classification algorithm based on mobility profile

The proposed solution uses supervised ML, more specifically decision trees. Supervised learning for classification works by first training the algorithm on a problem where the classes are already known. A decision tree is a binary tree such that on each node a comparison is made : if the answer is true go to left branch (or right), otherwise go to right branch (or left). In our case, the input of the algorithm is data gathered from users such as speed, acceleration, position (i.e. type of road the user is on), etc. These inputs are the features (see section II-B). The output is the mobility class (car, bicycle, pedestrian). Once this step is done, it is possible to determine which users are the best candidates to serve as relays. A "best candidate" can be a user with soft mobility (a pedestrian, perhaps, or a static node), a device lightly used (e.g. high available resources, low buffer occupancy) or any other target device suited for the current context.

We define network composed of U users and C different classes of mobility. Each user u stores a vector M of mobilityrelated metrics :

Algorithm 1 The machine learning algorithm to classify users depending on their mobility profile. number of mobile relays and the vector of relevant metrics (arg[0] and arg [START_REF] Index | Global mobile data traffic forecast update, 2016-2021 white paper[END_REF] in algorithm 1, respectively). Lines 1 to 3 are the initialization steps, where relays is the set of selected relays (eq. 6). The users' data are sent to the controller (lines 4 to 6; see section III-A). Lines 7 to 14 is the prediction step : the relevant data of all users are used to predict their mobility class (line 8; eq. 3 and 4). If the current user is predicted as being in the best mobility class, it is added to the set of selected relays (line 9; eq. 6). The algorithm stops when the target amount of mobile relays is reached (line 11 in algorithm 1). If there are more candidates than the amount of required relays, users not connected to Internet (or not in range of a parent able to connect to Internet) have priority to increase connectivity. Note that in the case not enough relays are selected, non-optimal users will have to be selected.

IV. PERFORMANCE EVALUATION

We have evaluated the proposed solution using the OM-NeT++ simulator. We also used the Simulation of Urban MObility (SUMO) to have more realistic results.

A. Simulation setup

The simulation was run using OMNeT++ 5.4.1 and SUMO 0.32.0. The Veins framework was used to interface OMNeT with SUMO. We have imported a real map from Open-StreetMap2 into SUMO and we have generated urban traffic using a tool from the SUMO package. Veins allows to run an OMNeT simulation using the mobility patterns of users (cars, bicycles) generated from SUMO to create and move nodes in a more realistic way. That is, each user in SUMO will have a corresponding entity in OMNeT (a "node" in our case). Thus, OMNeT will create one "node" from each user in SUMO and destroy those when they reach their destination.

The ML model was trained using a real map different from the the map used to test the model (i.e. run the simulation) : this allows to test the generalization of the studied algorithm. Table I shows the accuracy of the decision tree in correctly predicting the mobility class of users. A good prediction means a car, for instance, is predicted as a car. A wrong prediction means a bicycle, for instance, is predicted as something else than a bicycle. The "Delay" column in table I corresponds to the time data is gathered from users before making the prediction (see section III). When the delay is very short (2s for instance), the error is rather high because the user was not active long enough. For example, a car just starting might stop at a red light right away and it is not possible to differentiate it from a bicycle on such a short notice. However, although a longer delay allows for better accuracy, it also means a longer time before choosing a new sink. During this time, no connectivity will degrade QoS and might not be the right choice. This is why a compromise must be found between accuracy and delay to yield the best QoS possible. The predictive algorithm is compared to a random selection of sinks. The random selection serves as a base case and has the advantage of a zero delay to choose a new sink. The random choice is not represented in table I. We also ran the simulation without prediction using static relays (from 2 to 7) to compare the proposed solution with a solution using a dedicated infrastructure. They are placed randomly on the simulated area. We suppose all users can connect to Internet (directly via cellular network or not) to send their mobility-related data. Users without cellular connectivity will connect to other users and eventually transmit these data to the controller.

B. Result analysis

In the following, bar charts (figs. 2a, 3a, 4a and 5) represent results using dynamic relay selection amongst users. The horizontal axis is the time taken to make the prediction. The (b) The PDR in the case of static relays.

Fig. 2: The average PDR of the data packets of users.

without prediction using static dedicated relays. The horizontal axis is the number of relays placed on the area. We recall the reader simulations with dynamic relay selection are achieved using 5 relays (see table II).

1) Packet Delivery Ratio:

The PDR is the amount of data packets that reach the destination divided by the amount of data packets sent. This metric allows to understand the reliability of the network. The higher the PDR the better.

Figure 2 shows PDR results of the different simulations. The random selection (fig. 2a) yields a PDR of about 11%. Considering error bars, the proposed solution performs significantly better when the selection delay is 2s (fig. 2a) because the selecting of soft-mobility users as relays allows the topology to be more stable, reducing the amount of packet loss. PDR is potentially higher when using ML and tends to decrease as the selection delay increases because waiting longer to choose a new sink causes data packets to be rerouted after a longer delay, increasing the probability of packet lost. Static relays (fig. 2b) have lower PDR than the predictive solution because users move around and those relays eventually service no users at all. Those results are comparable to the random selection. When 2 relays are used, results from figure 2b show a PDR significantly lower than the proposed solution with a delay of 2s and 4s : static relays have a limited coverage, so only 2 yields low performance. More relays, in this case, help to increase performance, as shown in figure 2b. Note that in figure 2a the lowest PDR value with a selection time of 2s is 17.9865% whereas in figure 2b the highest PDR value with 5 relays is 18.0529%, so there is a slight overlap.

2) Connectivity ratio: The connectivity ratio is the percentage of time a user is connected to a sink during her trip. For instance, a connectivity of 25% on a 8000s run means the user was connected during 2000s in total. Connectivity is linked to PDR, as more connectivity increases the chance for packets to reach their destination though it is not necessarily the case, as a non-connected user will not try to send packets. This metric allows to see the coverage of the studied area and if sinks/relays are well placed. The higher the connectivity ratio the better.

The connectivity ratio is depicted in figure 3. The proposed solution is comparable to the random selection (fig. 3a) with a connectivity of about 30%. Indeed, mobile relays are located such that there is similar connectivity no matter the selection method. However, with a prediction time of 2s or 4s, the proposed solution performs significantly better when compared to static relays (fig. 3b) when using 2 or 3 relays. This is caused by the fact static relays (fig. 3b) eventually spend some time not being in range of users. A longer selection delay will negatively impact the predictive algorithm because users will spend more time disconnected.

3) Amount of signaling: The amount of signaling represents to number of packets sent on the topology excluding data and acknowledgment packets. Signaling is mostly used to set up and maintain the topology. Sending a signaling packet again because it was not acknowledged counts in the amount of signaling. This metric shows how much overhead is generated and how good transmissions are. The lower the signaling the better.

We can see in figure 4 the random selection performs significantly better (about 1.5 packets per minute per user on average) than the proposed solution (around 2.25 packets per minute per user on average) when the selection delay is 2s or 4s (see fig. 4a). The lower overhead of the random selection is due to lower performance in terms of PDR (fig. 2 connectivity (fig. 3). Indeed, less signaling will be sent in absolute if users are less connected to one another. In figure 4b, the amount of signaling is very high when there is (are) 1 or 2 relay(s). This is due to low coverage causing long paths (i.e. high number of hops from any user to the sink) with higher probability of retransmissions. Long paths also increase the probability of any user moving away causing the need to repair the topology. Transmission distances are longer as well because relays are static, causing many losses. The proposed solution is significantly better than the case of static relays (fig. 4b) except when the number of relays is 4 or 7, with overheads of about 2.2 packets per minute and 1.7 packets per minute respectively. A high number of overhead does not necessarily means performance is bad (see PDR in fig. 2). However, the scaling will be problematic if overhead is very high, as is the case of 1 and 2 relay(s) (fig. 4b). 4) Number of sink change: When dynamic selection of sinks happens, this metric shows how many times sinks are replaced. When an elected sink leaves the area of interest or fails due to low battery, a new one will be chosen. This metric shows the stability of the topology. The lower the number of changes the better.

Figure 5 shows the predictive algorithm performs significantly better in all instances. The random selection process causes more changes of sink. This is due to selecting high mobility users (cars) more often that leave the area of interest quicker, so a change is required. The proposed solution yields more stability as the number of changes is below 1.5 per minute on average. This means that one new sink is chosen approximately every 40s on average, compared to the random case (around 3 changes per minute) where one sink is chosen every 20s on average.

V. CONCLUSION

The solution proposed in this paper aims at determining the mobility class of users to select the best relays using a machine learning based approach, without requiring a dedicated infrastructure. This solution can be coupled with other algorithms to further improve network performance. Simulation results show the proposed algorithm increases performance in terms of PDR and stability compared to a random selection. The contribution also performs better than an approach with static relays in terms of PDR, connectivity and overhead and it is able to scale from several tens to several hundreds of users simultaneously in different scenarii. Future works will focus on extending the model with more mobility classes (e.g. pedestrians) and different traffic densities.

Fig. 1 :

 1 Fig. 1: The proposed architecture with several types of users and the controller running the ML algorithm.

  leftmost bar is the random selection (selection delay of 0s) and other bars represent the ML algorithm (selection delay of 2s to 10s). The line plots (figs. 2b, 3b and 4b) represent results Packet delivery ratio (

  The connectivity when using static relays.

Fig. 3 :

 3 Fig. 3: The average connectivity of users during their trip.

Fig. 4 :

 4 Fig. 4: Study of the amount of signaling packets (excluding acknowledgments) in two different scenarii. Note vertical axes have different scales.

Fig. 5 :

 5 Fig. 5: Stability of the topology in terms of the rate of sink change.

1 :

 1 maxRelays ← arg[0] 2: relevantM etrics[] ← arg[1] 3: relays ← N U LL 4: for all users do

	5:	user.gatherData()
	6: end for
	7: for all users do
	8:	if A(user, relevantM etrics) == optimal then
	9:	relays.append(user)
	10:	end if
	11:	if relays.size() == maxRelays then
	12:	break
	13:	end if
	14: end for
	15: return relays
		Delay (s)	2	4	6	8	10
		Accuracy (%)	20	27	88	79	86

TABLE I :

 I The accuracy of the predictive algorithm given the delay to gather data.

TABLE II :

 II Values for the most relevant parameters of the simulations. † Number of relays is set for the predictive case and varies from 2 to 7 in the case of static dedicated relays.

	Parameter	Value
	Playground size	1 km 2
	User generation period	1.5 s
	Num. of users, total	±4800
	Num. of users, inst.	10's to 100's
	Num. of relays †	5
	Car:bike ratio	9:1
	Simulation duration	8000 s
	Traffic model	VBR
	Traffic density	10 packets/s
	Data packet size	1280 bytes
	Max. user throughput	10 Mbps

In some cases, for instance in a heavy traffic jam, it might be hard to discern from the different classes of mobility even if a long time τ is used by the algorithm.

The real map is a sub-area of the Saint-Laurent borough, Montreal, Canada.

ACKNOWLEDGMENTS

We thank Ozgur Turk who wrote the code to interface data generated by SUMO with the machine learning algorithm, in order to train and test it.

Where µ is the number of different metrics (speed, acceleration, and so on). Each user periodically records values for these metrics (recording of speed, position, etc.). Depending on the ML algorithm used, different metrics (features) can yield a different expected accuracy (output). Hence, we introduce the vector of relevant metrics M ρ u for user u :

M ρ u can be composed of all metrics from equation ( 1). At least one metric must be used otherwise no input will be fed to the prediction algorithm. We suppose the recorded values for the metrics of equation ( 1) are sent to the controller after a time τ that we call the prediction time. We define the ML algorithm that takes as arguments the vector of relevant metrics and the prediction time :

Where c p u ∈ C is the predicted class of user u. A user can either be correctly classified or wrongly classified. Let c r u ∈ C be the real mobility class of user u :

From equation ( 4), we see the predicted class (c p u ) can either be the real class of the user (c r u ) or some other class which is not the right one (depicted as c x in eq. ( 4)). As aforementioned, the resulting accuracy of the considered algorithm depends on the time since a user exists. Indeed, more data is gathered if the user has been on the network for a longer duration and the predicted class usually 1 has a higher probability of being the correct one. Now, we define C b ∈ C as the best mobility class. Users belonging to this class are determined by equation 4. To act as relay, a user must have access to Internet (for instance via 5G). We define I ⊆ U the set of users with Internet access. Thus, only users within the correct mobility class and with access to Internet can potentially be selected as relays :

Where R is the set of potential relays. It is now possible to determine the set of selected relays R s that will serve as relays in the network :

From equation 6, we see there can be one relay or as many as the size of R s . This number will depend on the context and constraints. If a high connectivity is of paramount importance, more relays might be desirable. However, if the number of users and traffic are low, having only a few relays can be better. Note that R s can be small if the number of users with Internet access is small and/or if few users have the best profile as determined by function A(t) (see eq. 4). If no users are in the set R (eq. 5), non-optimal users have to be selected. Note that a non-optimal user can end up in R if the prediction failed (eq. 4). Hence, if the predictive algorithm is not adapted at all to the current context QoS might suffer greatly. Finally, if we set the gathered metrics of a user as constant, the probability the algorithm from equation (3) yields a correct prediction is proportional to τ :

Algorithm 1 illustrates the use of the proposed solution. It is called whenever the number of relays is less than the specified amount and a delay of τ has elapsed. The algorithm is supposed to be called with two parameters : the maximum