Edge Selection Strategies for Human-enabled Sensing Architectures

(1)

Università degli Studi di Pisa

Dipartimento di Informatica

Dottorato di Ricerca in Informatica

Ph.D. Thesis

Edge Selection Strategies for Human-enabled

Sensing Architectures

Dimitri Belli

Supervisor

Prof. Stefano Chessa

Dr. Michele Girolami

Year

(2)

ii

(3)

iii

Acknowledgments

First of all, I would like to thank Professor Maria Simi and Professor Paolo Milazzo for writing the recommendation letter for the Selection Board of the PhD. I would like to thank the whole members of the above Board for giving me the opportunity to embark the PhD Programme in Computer Science. I would also like to thank all the teachers with whom I had the privilege to measure myself on examination. In particular, a special thanks goes to Professors Linda Pagli, Pierpaolo Degano, Giuseppe Attardi, Maurizio Bonuccelli, and Marco Danelutto. Thanks to all those who have been close to me during such an important and not easy path. Thanks to my mother for putting up with me.

(4)

iv

Abstract

Human-enabled Edge Computing (HEC) is a recent development that combines the advantages of massive Mobile CrowdSensing (MCS) techniques with the potential of Multi-access Edge Computing (MEC) systems. The HEC model has attracted the attention of many researchers and industrial vendors for its ability of promoting the widespread collection of large amounts of information in urban settlement by providing support to the units involved in the sensing operations. In this context, the architectural hierarchy of the network shifts the management of sensing information close to terminal mobile nodes through peripheral edge nodes. The HEC model extends the coverage of traditional MEC geo-distributed solutions by leveraging people’s roaming and promoting massive sensing campaigns through users’ mobile devices. In this context, we consider two aspects that need to be investigated in order to find the appropriate trade-offs in the HEC configuration: the still limited computational and energy resources of mobile devices, and the installation and maintenance costs of MEC proxy servers. This thesis addresses such issues by proposing a social mobile edge architecture composed by interoperable fixed (FMEC) and mobile (M2EC) units in the MEC middleware layer. After introducing a method of task assignment based on MCS mobile resources, the thesis proposes some optimization methods to share contents between users leveraging their mobility and sociability. The central part of the thesis presents an algorithm for the selection of M2_{ECs to be used in synergy and/or in places of the fixed ones. The} M2EC social-aware selection algorithm is performed by leveraging the links between users and the fact that they tend to form cohesive communities. The thesis proposes two selection criteria: the first one is based on the users’ sociability, while the second criteria exploits the attitude of the users in performing the assigned tasks. The last part of the thesis introduces a probabilistic model for the estimation of the optimal number of M2ECs to be selected in order to achieve a specific coverage. The thesis also includes a comprehensive evaluation of the performance that can be obtained by combining FMECs and M2ECs. The solutions proposed have been tested with a real-world MCS dataset which provides meaningful mobility traces of students in urban areas for over one year of data collection. The final part draws the conclusions and presents some possible future development of these technologies as well.

(5)

v

Mobile CrowdSensing (henceforth MCS) [1] is a people-centric sensing paradigm for collecting, processing, and sharing huge amount of data from any type of environment. This technology is becoming a precious source of information for the management of Smart Cities (SC) because of its ability to collect large amount of heterogeneous data through mobile devices’ sensors. Given its peculiarity of involving a large number of individuals in the collection process, someone recognize in MCS the union of mobile sensing, that is the use of mobile sensors of devices to collect data from the environment, with crowdsourcing1. Others identify this term with the convergence of opportunistic and participatory sensing. Opportunistic sensing encompasses all those sensing operations that mobile and wearable devices can perform in background without the direct intervention of their owners. Differently, participatory sensing requires the direct involvement of users, who may be called for the execution of tasks individually or collectively.

MCS enables three different types of SC monitoring, that is,

1. Environmental, by measuring large-scale phenomena such as the noise level in a zone, the air pollution rate in an area, the contamination level of water resources in a river, and so forth.

2. Infrastructural, by measuring public infrastructure phenomena as traffic congestion, road surface monitoring, parking spot availability, and so on.

3. Social, through the information exchanged among individuals to improve, for instance, nutritional habits among groups of people with a particular disease, the identification of best routes for sustainable mobility, etc.

Examples of MCS systems developed for environmental monitoring are CreekWatch [2], an MCS app for urban hydrology, designed to involve people to take notes and photos of rivers to infer quality, level, and flow of waters; Common Sense [3], a mobile participatory

1

Crowdsourcing is an operational model that aims at developing collective projects. It is also referred as collective intelligence since its products are the result of a multitude of individuals. Crowdsourcing is often associated with the epithet the wisdom of crowds and shows how in certain contexts the aggregation of information in groups of people achieves better results than that attained by individuals in the same contexts. An example is Wikipedia.

(15)

15

sensing approach that enables individuals and groups to measure their personal exposure to pollution through air quality sensing devices connected with mobile phones; and SecondNose [4], an MCS project for collecting geo-referred environmental information as carbon monoxide values, air pressure and temperature of a given area.

Examples of MCS applications for civil infrastructural monitoring are Pothole Patrol [5], an MCS system that opportunistically collect information from the Global Positioning System (GPS) and vibration sensors of the drivers’ smartphones for detecting and reporting the conditions of the road surface; ParkJam [6], a mobile android application built on Linked Data that leverages geo-location information to infer parking availability; CoenoFire [7], a smartphone-based sensing system to support the work of the firefighters by monitoring their activity on-duty.

Examples of MCS systems for social monitoring are BikeNet [8], that maps the cyclist experience by leveraging the cellular data channel of the mobile phones, and also by using wireless access points along the way; DietSense [9], where people are required to take pictures of their meals and share such information within a community so to compare different eating habits; CenceMe [10], a sensing system that leverages sensor-enabled smartphones to capture the status of the users in terms of activities, disposition, habits, and surroundings to ease social interaction and buddy search.

Standard MCS platforms implement a broad-range community sensing paradigm that consists of three main units:

1. Individuals – people who express their willingness to take part in the MCS platform and to its campaign.

2. Mobile devices – equipped with sensors, short- and long-range communication interfaces, and an MCS application enabled for sensing operations via Application Programming Interfaces (API).

3. Centralized cloud-based servers - for data aggregation, storage, processing, analytics, and task assignment.

It follows that the MCS technology is not stand-alone. Its existence is made possible by the ubiquitous connectivity provided by the Internet and from the fact that powerful servers in the cloud are able to handle data flow from billions of devices displaced all over the world. In recent times, this infrastructure has sharpened its hierarchical architecture with the introduction of an intermediate layer made up of fixed nodes at the edge of the network. The middleware layer provides a first level of data filtering, aggregation analysis, and storage.

(16)

16

Moving the computation close to the network core, such an architecture reduces the burden on both end-user devices and remote cloud servers. This infrastructure is commonly referred to as Multi-access Edge Computing.

Multi-access Edge Computing (henceforth MEC) [11] is an initiative to create a standardized open environment that provides computing capabilities closer to the end users of the network to avoid the delays generated by the direct communication between mobile terminal nodes and cloud data centers. This concept is a solution to have same properties a Cloud Computing (CC) [12] system provides, just closer to the mobile end users. MEC reduces network congestion and improves applications performance through the use of highly virtualized environments at the edge of Radio Access Networks (RAN). Being able to process tasks closer to the cellular customers, such environment brings real-time, high-bandwidth, and low-latency access to all those latency-dependent applications distributed at the edge of the network. The MEC architectural concept is also acknowledged as one of the cornerstones for the new 5G system [13]. MEC use cases range from augmented to virtual reality [14, 15], from applications for interconnected vehicles to more general Internet of Things (IoT) implementations [16-18].

Both the MCS paradigm and the MEC technology have radically changed the way in which information is gathered and elaborated. The former by rethinking the way in which information is collected and shared, the latter by introducing a new way in which support services are provided. However, these technologies still suffer from many limitations.

Human-enabled Edge Computing (HEC) [19] has recently been proposed to overcome some of the weaknesses related to the traditional MEC model, such as the difficulty of the scalability of the platform and the burden of the maintenance costs of the MEC units, by using MCS systems. Through the synergistic use of MCS mobile devices and the MEC infrastructure, HEC enables powerful MEC-based MCS sensing applications. Such a model evolves the standard MEC architecture by adding mobile MEC (M2EC) units alongside the standard fixed MEC (FMEC) proxies in the MEC middleware layer. An M2EC can be viewed as an impromptu and temporary edge node that leverages the resources of a locally available mobile device. More properly, an M2EC is a mobile device that acts as a local proxy and it is dynamically activated in areas where people tend to stay for a while [20].

Generally, HEC refers to any system that combines the benefits of massive MCS with an architecture made up of three-tier hierarchy (client-tier, edge-tier, cloud-tier), regardless of whether it hosts cloudlet or edge nodes at the intermediate layer.

(17)

17

In literature only a limited number of contributions have explored the advantages of the joint use of MCS and MEC [21-23], and they all focus on technical aspects underestimating the crucial element of this emerging system, that is, human beings as the main actors of the data production process. Human monitoring can simplify the identification of strategic hotspots where to install M2ECs, as well as FMECs, so to leverage the one-hop communication and the store-and-forward principle to move data from FMECs to M2ECs and vice versa.

These technologies are the main theme of this thesis and are discussed in detail in the next chapter, where we present their appearance in the Information and Communication Technology (ICT) landscape and their evolution to the present days, highlighting similarities, differences, and the challenges they have brought to the world of research.

1.1 Research Questions and Objectives

What has been presented so far makes the idea of how important the hotspot identification process is. It also makes the idea of how heterogeneous the mobile nodes’ selection strategies could be. Based on these assumptions, this thesis aims to pursue two main objectives:

1. The study of architectural elements able to make the MEC-based MCS systems scalable and distributed (Section 1.1.1).

2. The optimization of the architectural dimensioning through the configuration of the nodes with respect to their co-workers and with respect to the mobile terminal devices (Section 1.1.2).

The necessity of maintaining a high level of platform performance, despite the increase of operational load on the system, is a fundamental requirement for both MCS and MEC. While the former has lots of potential solutions to lower the barriers and make the system scalable [24,25], for the latter such a problem is more difficult to solve [26]. This is because it is not possible to make the system scalable without introducing further FMECs, which result in additional installation and maintenance costs. To make easy the scalability of the MEC platform, our solution introduces M2EC units to support or replace the FMEC ones. As previously mentioned, M2EC units can perform FMECs functions with the additional benefit of not requiring supplementary platform costs since they are already displaced on the territory.

(18)

18

Until a few years ago, the topic was in an embryonic state, and approaches to innovative selection methods based on the sociability between users had not yet been analysed in detail. In order to fill this gap, this thesis studies social aspect of MCS users to plan efficient M2EC selection strategies. The following two sections describe in more detail the main goals listed above.

1.1.1 M

2

_{EC Selection}

The M2EC is a node belonging to the intermediate MEC layer that, unlike FMEC, has the ability to move in the environment as any other terminal mobile device. The adoption of M2EC units brings benefits to both the MCS platform and the MEC architecture. For the MCS system, the M2EC facilitates the burden of terminal devices by offering an initial support for storage, analysis, and acting as a bridge to forward sensing data to remote servers. For the MEC architecture, the use of the M2ECs is a valuable solution to make easy the platform scalability and, in addition, to reduce the costs associated to installation and maintenance of new MEC proxies, offering a better environmental spatial coverage as well.

The first goal of the thesis is the presentation of M2EC selection strategies for the MEC-based MCS system, as well as the assessment of operational efficiency for such unit, whether taken separately or interoperable with FMECs in a hybrid architecture. The objective is to demonstrate that a small number of M2ECs are capable of matching the performance of a large number of FMECs. While for the deployment of fixed edges is usually implemented a strategy that involves the identification of the most crowded areas [19], the mobile edge selection methods may include a more differentiated set of parameters such as the energy resources of mobile devices [27], the distance [28], the users’ sociability and reputation [29, 30], their ability to perform the assigned tasks [31], and so on.

Considering technical aspects strictly related to the performance of mobile devices (such as computational and energy resources), this thesis also introduces the problems related to the development of efficient M2EC recruitment algorithms based on users’ sociability. Such an aspect is a fundamental parameter both for the identification of M2ECs and for the development of FMECs deployment strategies.

(19)

19

1.1.2 FMEC and M

2

_{EC Configuration}

The estimation of the number of mobile devices to be selected as M2_{ECs (Chapter 5) and} the deployment strategies of FMECs within the territory (Chapter 6) are two problems that are addressed in the latter part of this thesis.

The study of architectural dimensioning raises the problem of quantifying the number of FMECs to be deployed and M2ECs to be recruited at the intermediate layer of the system, as well as which configuration strategy has to be adopted. For our purposes, we consider as functions of a FMEC just those concerning aggregation, real-time analytics, storing, and processing of sensing data. However, as a radio access bridge flanked with a bunch of highly virtualized server proxies, FMEC can perform many other applications and services, whose limits are given by authorizations of the owners of the infrastructure (that generally are network service providers). Third-party customers who obtain such permits can provide any kind of customized service and application to all those final users applying for it. Other than the above mentioned, applications and services that a FMEC can provide span from data caching to location services, from augmented reality to optimized content distribution, and so forth.

Both FMECs and M2ECs move the computation close to terminal nodes, by providing support for mobile and cloud central servers. The former, fixed, offers a permanent spatial coverage of a specific place of the territory; the latter, mobile, has the possibility to reach uncovered areas of the territory such as urban or rural ones. An HEC system configuration that ensures the interoperability of FMECs and M2_{ECs in the intermediate MEC layer} provides better support for both mobile terminal devices and remote cloud servers. However, it is possible to imagine an HEC architecture made up of M2_{ECs only. Therefore, the} fundamental issue does not lie in whether or not FMECs are interoperable with M2ECs, but in how many M2_{ECs are needed to guarantee the same spatial coverage that would guarantee} an HEC architecture in which both FMECs and M2ECs operate. The question of the number of M2ECs necessary to replace the work of the fixed ones is addressed in this thesis through the presentation of a probabilistic model (Chapter 5). Such a model estimates the number of M2ECs capable of meeting the performance of FMECs without subtracting benefits to the platform. The goal is reached through the development of an M2EC selection strategy which estimates, through a closed-form expression, the number of mobile edges to be recruited as FMECs substitute. Aside from being one of the main question still open in the field of MEC-based MCS systems, the last-mentioned aspect is also an effective strategy for the more

(20)

20

efficient use of resources to support the sensing activities of terminal nodes, as well as the assistance provided to the activities of remote cloud servers.

Concerning the strategies to be used to enable fixed and mobile edges, this thesis starts considering technical aspects related to the performance of mobile devices and then faces with the problem related to the development of efficient deployment/selection strategies on the basis of users’ sociability and some other criteria.

The results described in this thesis are partly obtained by experimentation through a synthetic dataset and, mainly, through information collected in a real-world dataset, ParticipAct [32], which is introduced in the next chapter. In the following section, instead, are detailed the thesis contribution and the methodology adopted for the resolution of the raised questions.

1.2 Thesis Contribution

In this thesis are proposed algorithms for the selection of M2ECs and strategies for the deployment of FMECs within three distinct types of HEC architectures. Each architecture differs one from the other by the type of edges acting in the HEC intermediate layer. The first HEC architecture consists of FMECs only, the second consists of FMECs and M2ECs, and the third consists of M2ECs only. The main result of this analysis is twofold: the demonstration that the architecture made up only of a small number of M2ECs is able to match in performance of the same architecture made up of a large number of FMECs, and that the hybrid approach is the best option in scenarios where a restricted number of M2_ECs is required.

The first part of the thesis introduces a study on the persistence of MCS mobile devices in a HEC architecture. The analysis of the configuration of terminal mobile devices is carried out to test their reliability in the execution of the tasks in a MCS campaign. In this scenario, the tasks are assigned by the intermediate HEC nodes on the basis of the mobile actual resources. The objective is to lower the energy and computational load on those devices with scarce resources. The thesis demonstrates that a selection based on computational and energy capacities of the mobiles is more effective than a selection strategy based only on the distances of the devices from the task to be performed.

Subsequently, the thesis faces the problem related to the identification of the M2ECs to be selected within a set of mobile devices of a MCS campaign by introducing two algorithms.

(21)

21

The first algorithm leverages the knowledge of the social ties between community users to select those who are best connected to the largest fraction of the population. The second algorithm operates at discrete intervals (periods), identifying the devices to be activated as M2ECs in a predictive way. Specifically, the identification of M2ECs is carried out by analysing the social network resulting from the mobiles in a previous period for the next one. It is worth pointing out from the start that mobile devices can play different roles with different level of specificity. Fig. 1.1 shows the level of specificity of mobile devices depending on the context.

Another issue addressed is the estimation of the number of M2ECs to be activated in an HEC architecture consisting of M2ECs only in the intermediate MEC layer. To overcome such problem, the thesis proposes a probabilistic model that estimates the number of M2ECs by tuning the parameters of a closed-form expression on the qualitative analysis of interaction between users.

The thesis also contributes to the identification of efficient strategies for FMEC deployment. To this goal, we analyse three different hotspot identification techniques: random-based, grid-based, and density-based. Results demonstrate that the study of user sociability through the density-based spatial clustering technique leads to better spatial coverage than the random or the grid-based deployment one.

(22)

22

1.3 Thesis Structure

The remaining part of the thesis is structured as follows:

In Chapter 2 we introduce a review of the background and the related work in order to give useful information to advance the reading. We present a general overview of the state of the art of MCS, MEC, and HEC according to the research questions introduced in Section 1.1, and a taxonomy based on the most relevant goals achieved in HEC architectures. We also compare the aspects related to service layer and network layer of integrated MEC-based MCS systems, presenting open issues, challenges, and opportunities towards achieving efficient HEC hybrid systems. We dedicate the last part of the chapter to the introduction of the concepts necessary for the advancement of this thesis. In detail we introduce the human-mobility concept and we present the dataset used for the development of the algorithms and the experimental results (Sections 2.4 and 2.5). In a subsection we present an in-depth analysis of the mobility traces of the dataset. The analysis is required for the development of the probabilistic model introduced in Chapter 5. The most significant results of this chapter has been published in [33].

In Chapter 3 we introduce a capacity-aware user recruitment framework for task execution in HEC platforms. The selection process considers energy and computational capacities of mobile devices through the support of a standard MEC architecture built on an abstraction of a real-world setting. The model is compared with a distance-based benchmark. Results demonstrate that our model performs better accuracy in task execution, with a greater number of successfully executed tasks. Besides, we demonstrate that the selection process devised is more effective and the average waste of platform resources is lower. Part of the contribution of this chapter has been published in [34].

In Chapter 4 we present an algorithm for the selection of social mobile edges in an HEC architecture. Moreover, we also introduce the results of a comparison between two M2_EC selection methodologies based on centrality measure and cooperativity score. The results obtained by simulation over a real-world mobility dataset show that M2ECs can well integrate to the standard MEC architecture, also as a viable alternative to the use of MEC proxies. Besides, tests on the performance of M2ECs selected on the basis of sociability report better results with respect the performance of M2ECs selected considering the attitude of the users to be cooperative. Such results support the thesis that M2ECs selected among those that are more sociable brings more benefits than the other candidate selection strategy. The most relevant outcomes of this chapter have been published in [35-37].

(23)

23

Chapter 5 presents a new M2EC selection algorithm and addresses the problem of selecting the number of M2ECs to be used in place of the FMECs in an HEC architecture by proposing a probabilistic model. The algorithm and the closed-form expression of the probabilistic model are developed through a qualitative analysis of one-year real-world mobility traces of the dataset introduced in Chapter 2. The analysis led us to the development of an algorithm that selects the first representative nodes of the largest communities identified in line with the concept of social coverage. Moreover, it proved useful to determine a correction factor for the calibration of the model to achieve good fitting between the model itself and the experimental results. The contribution of this chapter has been published in [38].

In Chapter 6 we address the synergies between MCS and MEC through the evaluation of strategies for both the deployment of FMECs and the selection of M2_{ECs to support data} collection in MCS campaigns within MEC architectures. The results presented show that M2_{ECs can replace more than complement FMECs, given their ability to reach users much} faster than FMECs. The main contribution of this chapter has been published in [39]. Submitted at the 2019 International Symposium on Computers and Communications (ISCC), [39] was awarded as the best paper among all articles accepted at the conference.

In Chapter 7 we draw conclusions, by summarizing the results presented in all the previous chapters. A subsection is dedicated to the reflection on possible future developments and perspectives of HEC architectures in 5G networks.

(24)

24

Chapter 2 Background and Related Work

This section provides background material and a review of the most important works available in literature related to the MCS and the MEC architectural models. The first section is dedicated to the MCS. We introduce here the main features that distinguish the MCS from other types of massive sensing techniques. We also introduce the main MCS solutions for the management and the analysis of data through the description of frameworks devised and goals achieved to date. The subsequent section introduces the MEC model and its role in the future 5G and 6G network infrastructures by highlighting the main benefits and its synergies with MCS.

Afterwards, we introduce the concept of HEC system, by presenting the main components characterizing the overall structure of this new paradigm and by defining a taxonomy based on the strategies adopted to improve both the network layer and the service layer of the HEC hybrid scenario. Comparisons are made on the basis of various criteria such as node structure, information exchange, resource/service management, and safety/security. In the last part of this chapter, we introduce an overview of the human mobility concept, presenting the real-world mobility traces dataset adopted for testing the effectiveness of the proposed solutions to the problems addressed.

The chapter is structured as follows. In Section 2.1 we introduce the MCS concept and its role in environments where massive sensing technologies are required (e.g., SC). A subsection is dedicated to issues and limitations of MCS in urban environments. In Section 2.2 we introduce the MEC concept highlighting, also for this paradigm, issues and limitations. In Section 2.3 we introduce the synergies between MCS and MEC, and the definition of HEC architecture. We also present a taxonomy of MEC solutions in HEC systems, highlighting the solutions to the problems faced by the scientific community so far and pointing out those still lacking a contribution. In Section 2.4 we introduce the concept of human-mobility and how it is possible to extract co-location information between users from human-mobility traces. In Section 2.5 we introduce the ParticipAct dataset and we present the qualitative analysis of one-year real-world mobility traces. Such analysis is the starting point of the main achievements of this thesis.

(25)

25

2.1 Mobile CrowdSensing

MCS is a paradigm born by the convergence of opportunistic and participatory sensing. Its main goals are the collection, sharing and processing of huge amount of information sensed from any kind of environment. The ubiquity of mobile and wearables fostered by their widespread in the last two decades, promoted MCS as one of the key-enabling techniques for SC monitoring. While including remote cloud servers for data storing and processing, the real strengths of MCS are individuals and the communication interfaces and sensors of their mobile devices. The term MCS was coined by Ganti et al. [1] to refer to a community sensing paradigm that embodies the characteristics of opportunistic and participatory sensing (Section 1.1). According to Guo et al. [40], instead, MCS is a tool to empower citizens, making them active participants in the process of acquisition and distribution of information through the use of their mobile and wearable devices. One of the main features that distinguish MCS from other types of massive sensing techniques is the possibility of exploiting the sociotechnical network effects to extend the crowd by exploiting communities of MCS users so to ensure efficient data collection and dissemination. Being a large-scale information collection technique, MCS is widely applied in urban settings to monitor, for instance, the traffic congestion, the noise pollution level, the road surface monitoring, and so on.

In recent years, the creation of MCS platforms has been facilitated by the development of frameworks for the management of sensing data. Examples of MCS frameworks are VITA, a popular MCS cyber-physical system that supports the development and management of multiple MCS applications and tasks across mobile and cloud platforms [41]; HySense, a hybrid MCS framework based on incentive mechanisms that combines mobile device sensors with static sensor nodes to improve the data collection process [42]; effSense, an MCS framework for energy-efficient and cost-effective data uploading that operates with adaptive uploading schemes within fixed data uploading cycles [43].

MCS creates the opportunity for the development of efficient massive sensing applications without rely on any other external (stand-alone) sensor device [44], by leveraging the ubiquity and multi-modal sensing capabilities of mobile and wearable, as well as the movement skills of their owners. In MCS campaigns, the sensing activity strongly depends on a series of task assignment policies. Generally, the term task refers to the process of collecting a certain type of data for a given amount of time, in a given location area. In this context, with the term task we simply refer to any kind of data that can be gathered

(26)

26

through mobile and wearable devices. Some meaningful examples of MCS tasks are multimedia contents, sensor readings or questionnaires submitted to users in order to collect feedbacks from, e.g., public events or the life quality in a specific region. The main task assignment strategies consider the population density of interesting areas at different timespan of the day, as well as the mobility patterns of the users and their willingness to perform sensing operations [45]. The benefits of careful user’s selection strategies are reflected in the minimization of the platform costs and the maximization of the accuracy and the execution of tasks. Generally, the most effective user recruitment policies for data acquisition consider the position of the user with respect to the data to be sensed [46], the sociability of individuals [47], and the current status of the resources of devices [48].

The process of task assignment in an MCS campaign can be made on the analysis of the human mobility. An example of multi-task assignment for MCS in mobile social networks is given by [49], where is proposed a task assignment algorithm that periodically upgrades the task scheduling based on the social context of MCS users.

Humans tend to establish social relationships on the basis of multiple factors such as their preferences, habits, and duties [50]. According to this, they form communities. In the context of MCS, communities are as important as the sensors of mobile devices because the knowledge of the social ties between user allows, inter alia, the planning of efficient strategies for the collection and sharing of sensing information. Although there is no strict definition of community [51, 52], it can be intuitively described as a group of people closely connected to one another by means of significant social relationships [53]. Such an interpretation implies that family relationships, those with colleagues at work, with friends, or those with strangers with whom humans occasionally interact, are all factors included in the concept of community. For the purpose of leveraging social relations, the concept of community in a MCS campaign is understood in a broad way, including also those situations where subjects, even if they do not interact, are in close proximity with each other (Wi-Fi distance) for a sufficient time to ensure the exchange of information between their devices. Examples are people waiting at bus stops or at the station tracks.

According to the concept of community, in Chapter 4 we introduce an algorithm that leverages the knowledge of the communities of users (and their sociability in full) to plan a selection strategy for M2_{ECs. In order to make the M}2_{EC selection process as effective as} possible, we implement a procedure that executes the ranking of strong communities (i.e., communities made up of a very limited number of nodes more cohesive than others) on the

(27)

27

basis of the dimension of their ego-network. An ego-network of a node is the set of nodes having ties with the node itself (the union of the ego-networks of the nodes in a strong community forms an extended community).

2.1.1 The Role of MCS in SC

More than 50% of the world population lives in cities. Today, more than ever, an intelligent use of the resources of our cities is necessary because they account for more than 75% of the global energy consumption and are responsible for more than 80% of the total greenhouse gases. It follows that the worldwide sustainability depends on the efficiency of our cities.

A SC is an urban environment that relies on the opportunities offered by ICT and IoT to promote strategies for the sustainable development. Basically, it takes advantage of the information retrieved by different types of sensors scattered in the urban environment to offer increasingly efficient services to citizens. In SCs, the mobile devices of the citizens can collect and exchange information from the environment in which they pass by, by generating a large amount of data to be used to feed more advanced services.

Among the plethora of devices acting in the urban fabric, mobile and wearables emerge as the main actors of paradigms as IoT and MCS. These devices are equipped with short- and long-range communication interfaces, that allow them to share information with other devices in proximity. Moreover, they are equipped with sensing units (e.g., gyroscopes, magnetometers, GPS, and so forth) that enable them to sense information from the environment in which they are located. In literature there are several examples of implications between MCS and SC [54, 55]. Examples of city infrastructure optimization by MCS comprehend applications that exploit the sensors of the mobile devices to detect the presence of dangerous pollutant [56], others that leverage the mobility-as-a-service to promote smart transportation [57], and many others involving people to monitor water supplies [2]. As a final point, MCS results an important enabling technology for SC if compared with the standard infrastructure-based sensing techniques made up of fixed sensor nodes, because it does not require deployment expenses of fixed infrastructures and allows scalable solutions.

(28)

28

2.1.2 MCS System Architecture

According to [58] it is possible to imagine the MCS system as a four-layer architecture that consists of:

• A sensing layer, gathering all devices’ sensors

• A communication layer, including all communication infrastructures and network interfaces required.

• A data layer, which is made up of remote servers for aggregation, storage, and processing.

• An application layer, to interface with users and manage sensing operations. The sensing layer is composed by sensing devices through which it is possible to collect information from the crowd. The upper layer includes all the communication technologies used for the transmission of sensing data, that is, the communication interfaces of the mobile devices as well as the network infrastructures that allow the routing and forwarding of information. The third layer is responsible for the aggregation, storage, analytic, and processing of sensing information. And finally, the upper layer gathers the functionalities of the application layer, that is, data visualization, task management, recruitment processes, and so on. Fig. 2.1 shows a schematic representation of the four-layer abstraction of the MCS paradigm.

Sensing Layer

Sensors are the fundamental components for data acquisition in MCS campaigns. The main sensing components used in smartphone interactions in everyday life are (just to name a few) the microphone for making calls, the camera to take pictures, the accelerometer when we rotate the phone and the screen rotates accordingly, and the gyroscope when we are busy in recreational activities. However, this is not the only use that can be imagined for these sensors. The microphone can be leveraged as acoustic sensor to detect high noise zones; the camera can be used as an image sensor for the retrieval of spatial information; the accelerometer detects mass inertia and can be used for mapping movements; and finally the gyroscope returns the orientation of the device and, therefore, the point of view of its owner. Like these, many other sensors currently embedded in mobile devices (such as thermometer, magnetometer, GPS, ambient light, humidity, proximity and so forth) can be leveraged to obtain a huge amount of information from the environment. Without claiming the completeness of a taxonomy, sensors can be divided into two main families:

(29)

29

• Hardware-based (or low-level sensors). • Software-based (or high-level sensors).

Hardware-based sensors generate data from measurements of real-world phenomena, like the force of the geomagnetic field, the acceleration, and so on. Software-based sensors are mimic by hardware-based sensors; for this characteristic they are called virtual or synthetic sensors as well. Examples are the gravity sensor, the linear acceleration sensor and the orientation sensor. Motion sensor, such as accelerometers, monitor the acceleration and the rotational forces of bodies. Position sensors, such as magnetometers, return the physical position or orientation of a device. Environmental sensors return pressure, humidity, temperature, brightness, and a wealth of other information about the environment in which they are located. Microphone and camera enable multimedia sensing, while touch screen sensor monitor the tactile activities of the users.

The short-range communication interface of mobile devices can extend the heterogeneity and the scope of the sensing through the connection of mobile devices with sensors external to their hardware such as the motes for air monitoring [59, 60] or the use of third-party sensors, installed inside the vehicles for emergency, traffic monitoring, and road lane detection [61]. However, in literature there are detailed studies on smartphones’ sensors and mobile sensing techniques, one for all [62].

Communication Layer

The communication layer is responsible for the transmission of the information in both directions: from the devices towards the cloud, and vice versa. In the communication layer are included all the technologies and the methodologies to deliver data, including the short-range communication interfaces as Wi-Fi, Wi-Fi direct, Bluetooth, LTE-direct, and long-range communication interfaces for broadband wireless access as UMTS, LTE, or 5G. The wireless communication is based on the protocol defined by the designer. The Communication protocols considered are divided in three categories according to the distance:

• Short distance communication, that is Personal Area Network (PAN), includes communication interfaces whose coverage distance range from Wi-Fi to Near Field Communication (NFC)

(30)

30

• Medium distance communication, that is Local Area Network (LAN), includes the wire-connected communication interfaces such as Ethernet, that manage connections between gateways through wired systems.

• Long distance communication, that is Wide Area Network (WAN), includes all the communication protocols supported by satellite networks (as LTE and 5G).

The communication layer is the main channel between the sensing activity of mobile terminal nodes and the cloud data centers (data layer).

Data Layer

The data layer is responsible for all operations concerning the processing, the storage, the analysis, and the data aggregation of information. In the standard MCS system the data layer takes place in the cloud. The analytic function makes inference on row data through a refining process. Furthermore, the data layer is responsible for generating and forwarding tasks, usually produced from refined sensing data.

Application Layer

High level aspects of the MCS campaign are found in the application layer. Recruitment and scheduling, tasks assignment and their executions, data visualization and the management of user interactions are all operations belonging to the application layer. MCS applications are responsible for managing all these aspects of the application layer.

(31)

31

The MCS application layer relies on standard APIs to interface with final users [63]. Through APIs it is possible to identify sensors, their capabilities, and monitor sensing events at run time. Monitoring sensing events fundamentally involves the retrieval and management of information such as the name of the sensor that triggered the event, the measurement data, its accuracy and the timestamp over which it was taken. APIs can provide access to raw data or be made available by the operating system at a higher level to provide access to context-dependent filtered data. MCS applications are generally oriented to:

• Data collection campaigns (for off-line, big-data analytics).

• Analysis of the user mobility for the sustainable mobility (understanding traffic flows, parking availability, road surface monitoring, etc.).

• Analysis of environmental datasets (weather predictions, pollutant monitoring, ecosystem conditions, etc.).

2.1.3 Issues and Limits

MCS solutions can be of extreme importance in the context of SC because of the ubiquity of mobile and wearables able to collect data in any environment. However, MCS does not lack of issues and limitations which lowers its large-scale adoptions. Issues and limitations in MCS can be grouped according to the following classification.

Data Reliability - The unreliability of the data is often due to the malice of the users, who for personal interest or for the simple taste of the upset, submit false data. This series of problem is addressed by the development of effective methods for validating sensing data [64].

Resource Constraints - The long-standing problem of the battery drain is felt to a greater extent when sensing activities involve sensors such as GPS. In this context, a targeted control of sensor activities and their careful programming, the use of alternative interface to infer sensing information, or feedbacks that notifies the high battery consumption by a sensor, they are all mechanisms able to reduce the costs related to battery drain. Thus, it is possible to obtain a balance between the Quality of Service (QoS) and the Quality of Experience (QoE). The QoE is not only guaranteed through forms of incentives. Many concerns are related to privacy and security in data collection and transmission. Given the vast amount of literature on the subject, we just limit to mention some recent works of data anonymization in MCS [65, 66], and some efficient solution to cope with privacy issues [67, 68]. MCS campaigns are usually characterized by a wide variety of mobile devices with heterogeneous

(32)

32

computational and energy capacities. Some data acquisition policies have focused on this aspect to allow a reasonable energy saving for devices with limited resources [29][69]. In MCS campaigns the problem of energy waste is often related to the bandwidth waste. In this respect, some studies have focused on local data mining solutions for data refinement [70,71].

Participation - Addressing problems and afflictions so to endure a high QoE for MCS users is not the only concern. For an effective and lasting MCS campaign, user participation must remain active over time. This goal is usually pursued through incentive mechanisms such as rewards [72], reputational systems [73], lotteries [74], and so on. Even if devices of the MCS campaigns are scattered throughout a territory where it is assumed that the connection is always available, there is always the possibility that they are unable to perform certain sensing operations due to environmental conditions (e.g., if they are in a hostile environment without cloud connection) [75]. Encouraging user participation covers both tangible and intangible aspects, namely, economic and psychological. The participation of users in order to obtain valuable data that can be used for research purposes is driven by purely economic aspects, requiring incentive mechanisms that motivate users to perform the assigned sensing tasks. The search for cost-effective solutions in this respect is usually linked to the cost/data quality trade-off. From a certain point of view, even the mechanism of non-annihilation of users is linked more to economic aspects rather than psychological ones. In these contexts, the participation is kept active through incentive mechanisms such as the assignment of a score for the performances of tasks, followed by a reward as credit or additional data traffic. User involvement can be stimulated not only through a system of monetary rewards but also to playful activities. Some platforms, for instance, maintain active the involvement of the players through a score mechanism, as in a sort of game.

Privacy - Confidentiality of information is the main plague that discourages the wide and rapid spread of this sensing paradigm. The GPS sensor, for example, can be used to monitor traffic congestion in a given area when the user is driving [76], as well as can be used to obtain confidential information of individuals, such as movements and usual routes [77]. In this respect, the anonymization of data plays a key role [78].

As a final point, we observe that MCS campaigns require enormous resources for sensing activities. The introduction of a three-tier architecture as MEC, to support the main operations of terminal mobile devices can bring enormous benefits to the overall MCS

(33)

33

system, facilitating the resolution of some of the previous issues and lowering the barriers that limit its optimal use and widespread deployment.

2.2 Multi-Access Edge Computing

In recent years the world of telecommunications has experienced an exponential growth on mobile communication technologies [79]. In January 2019 more than 70% of the world’s population had a subscription with a network service provider, while in the last decade such a percentage reached barely the 20%. And today, the sector is constantly evolving. The ability to experience video, music, social networking activities, as well as the continuous development of new mobile applications, contribute to the expansion of this sector. In addition, soon will make its official entry the 5G (scheduled for February 2020) with all the improvements that is expected to introduce. 5G aims at enabling all a series of proximity and context-aware services, integrating networking and ICT resources with cloud-oriented services through highly-virtualized environments.

More than a quarter ago, the European Telecommunications Standard Institute (ETSI), in anticipation of the entry of MEC model, launched the Industry Specification Group (ISG) to create an open environment between multi-vendor cloud platforms at the edge of the RAN. The decision was driven by the need to overcome the CC latency limitations. Relying on edge nodes to process data close to end users, network service providers can reduce bottlenecks in the main network channels and backbones, and, at the same time providing support for terminal network nodes enlightening their computational load and offering processing, storage, and real-time analytics. MEC disrupt the standard network architecture by introducing a further hierarchy in the communication channel between mobile devices and remote cloud servers. Such decentralized geo-distributed environment does not only relay the direct cloud-device communication but performs computing as well. These features make the MEC architecture an enabling technology for the next 5G communication system.

Providing a new ecosystem based on RAN edges with computational and storage, MEC aims at supporting terminal mobile nodes of the network through closer computing even if their backhaul is not optimized. Such cloud technology, decentralized, makes the MEC model an important pillar of the new 5G system [11][13][80, 81]. Standard MEC implementations consider individual platforms providing local services in a non-seamless way, without dealing with the mobility of the users. Advanced MEC implementations, in a landscape view, introduce the heterogeneous networking concept to support business and

(34)

34

non-business applications, both in indoor and outdoor environments [82, 83]. Current MEC architectures are also able to manage aspects like traffic, user mobility, and account seamlessly [84-86].

Recent studies have highlighted the benefits of interoperable MEC-5G systems with IoT applications. Such systems enable the development of platforms designed to manage large-scale devices with low-latency and no-bandwidth waste [87]. Other studies pointed out the importance of techniques based on computation offloading to save battery lifetime and calculation through the exploitation of devices interacting with MEC middleware nodes. In literature there is a wide range of references of computation offloading technique solutions over 5G heterogeneous networks; for a comprehensive study in the field it is possible to consult [88]. Other application in which MEC brought benefits comprehend localization [89], emergency [90], and public safety services for SCs [91, 92], big data storage and computation in massive sensing platforms [93], caching [94], and distributed content discovery and delivery [95, 96].

As a final point, we observe that the introduction of the MCS concept in the MEC architecture can bring great benefits to the collection and dissemination of data as well as to the scalability of the platform [97].

2.2.1 The Role of MEC in 5G Networks

The MEC architectural concept is considered the pillar of future 5G networks [98]. ETSI recently published the MEC white paper [99] for the MEC standard definition, to help developing a cloud application environment at the edges of the network. In addition, the ETSI ISG MEC group has recently published a series of specifications for the standardization of the MEC model concerning the orchestration and management of MEC applications. One of the key-aspect that enriches the MEC specification is the ability of MEC-oriented applications to acquire location real-time awareness and contextual information through standardized APIs. Thus, the ETSI ISG MEC group devoted significant efforts to produce a whole series of guidelines for the development of APIs for services [100], applications [101], and user equipment [82].

The MEC model foresees to include computing capabilities, associating to each base station a bunch of server nodes statically mounted at the edge of the network. The main function of the base stations is to act as local proxy for centralized network backbones so to

(35)

35

enable a better scalability of the network architecture and responsiveness in interactions with mobile nodes through local control decision and actuation. MEC aims at evolving the traditional two-layer cloud-device communication model, where mobile nodes rely on long-range communication interfaces to convey data towards centralized remote servers, introducing a more granular hierarchy of the network with the introduction of an intermediate layer made up of base stations. In MEC solutions the edges, are usually developed by telco providers to be static and installed in strategic points of the territory so to ensure the best possible spatial coverage. The MEC provides IT and CC capabilities within RAN close to terminal nodes of the network [102].

Four main expected benefits of the 5G network to the MEC model are:

1. High frequencies with massive bandwidth.

2. Interoperability of extreme density of base stations and core nodes capillary deployed into the territory.

3. Highly integrative systems, combining air interface and spectrum along with LTE and Wi-Fi to provide a significant rate of spatial coverage and to assure a seamless user experience.

4. Latency reduction, platform costs reduction, and support for many low-rate connections.

The technology trends that are set to become cornerstones of future 5G networks is the Network Function Virtualization (NFV) and Software-defined Network (SDN), which are progressively changing the way network services are provided. NFV is an architectural approach that leverages IT technologies to virtualize network node functions as building blocks that can be easily interconnected to implement communication services [103]. This trend, previously confined only to core nodes, has recently been extended to the base stations of the MEC model. SDN is a network management technology through CC that allows a rapid deployment of innovative services, enabling network programmability and multi-tenancy support [104]. SDN centralizes the network logic into separate components (MEC base stations) by dissociating the data forwarding process (i.e., the data plane) from the routing process (i.e., control plane) [161, 162]. Briefly, the NFV in base stations has the key benefit of separating network functions from the hardware infrastructure, by allowing software execution in a centralized manner on the virtual machine, thereby, lightening the processing load of physical network nodes. In this way, the standard network services can

(36)

36

be combined with a whole series of new services targeted at the individual end user. A detailed description of 5G, NFV, and SDN technologies goes beyond the purpose of this thesis. For further details on the 5G technology it is possible to consult [105], while for details on NFV and SDN in MEC architectures we refer to [106, 107].

From a network architectural point of view, the MEC is an evolution of the CC model, which acts as an Infrastructure as a Service (IaaS) for the storage and the processing of information received from both remote cloud servers and mobile terminal devices. In fact, the edge-cloud concept was initially introduced with cloudlets in a service key to assist mobile terminal nodes with data storage and computational issues, and this approach has pointed towards the most advanced concepts of Fog Computing (FC) and MEC. Both FC and MEC architectural models provide an open platform with similar features and services. In FC, the focus is on IoT applications that benefit from an orchestration between intermediate core nodes to assist network terminal nodes. MEC focuses instead on enhancing context-dependent applications through data processing, storing, and real-time analytics to support network terminal nodes. CC, FC, and MEC can be considered as evolution of the same architectural model, with the proxies of the intermediate layer called respectively cloudlets [108, 109], fog nodes [110, 111], and edges [112].

It is well known that the world of research, from one institution to another, often deals with common issues in parallel, associating them with different labels, until it converges on the name of a paradigm. That is what is happening with paradigms like CC, FC, and MEC. As they are conceived, these systems can be considered evolutions of the same concept. And the synergistic use of each of them with the MCS paradigm can be referred to as an HEC architecture. For this reason, the terms CC, FC, and MEC in the following are used interchangeably, giving priority to the term MEC as it is the more frequently used in the recent literature.

2.2.2 MEC System Architecture

Briefly, we introduce below the MEC architecture through an abstraction of its system components based on ETSI specifications [82][100][113].

(37)

37

The MEC stack shown in Fig. 2.2 is made up of three interoperable levels: system, host, and network level. At the highest level is the MEC orchestrator, which is responsible of the monitoring of the MEC system (hosts, resources, services etc.). At the distributed host level are located:

• The MEC platform manager, which is responsible for the management of life cycle of the applications, update the MEC orchestrator of relevant events concerning applications, providing management functions to the MEC platform, and managing the application rules (service authorization, traffic rules, DNS configuration, and conflicts).

• The virtualization infrastructure manager, which is responsible for the allocation, management and releasing of virtualized resources (computing, storage, and networking), the configuration of the infrastructure, collecting and reporting performance about virtualized resources, performing application relocation. • The device application, which is able to interact with the MEC system through an

user application lifecycle management proxy.

• The customer facing service portal, which allows to the operators of third-party to select the MEC useful applications and receive back service level information from the application provisioned. At the network level are located the network architectures, such as the next 5G, enabling the MEC paradigm.

(38)

38

2.2.3 Issues and limits

The 3 main problems with MEC architecture are the following:

• The difficult scalability of the platform due to significant installation and maintenance costs of MEC units [163].

• Technological advancements due to difficulties in the hardware upgrade.

• Inefficiencies in terms of resource optimization and, consequently, services offered only at certain time intervals.

Such problems are more or less correlated. Firstly, the difficult in platform scalability is mostly due to the costs associated to the servers and by the fact that such servers require periodic updates so that their long-term operability is ensured. Secondly, the maintenance operations imply hardware upgrades as the technology evolves (e.g., eNodeB for LTE or gNodeB for 5G network). Finally, in order to ensure efficient seamless services, it is necessary to guarantee the coverage of an increasingly large area of the territory.

Recently, the scientific community explored the possibilities of massive sensing in SC context, focusing on hybrid solutions of MEC and MCS [114]. The HEC model combines the power of MEC architectures with the versatility of the MCS paradigm. The main areas of study concern the preservation of privacy for mobile users [115], MEC-based MCS architectures for massive deployment of services [116], and technical challenges [21].

The HEC implementation, proposing the joint use of MEC and MCS, aims to overcome some of the above issues.

2.3 A Taxonomy of MEC Architectures in HEC

The research has recently been oriented to the discovery of synergies between MCS and MEC [118, 119], recognizing to the massive sensing applications a possible coexistence with cyber-physical systems [41]. In this section we introduce the HEC architecture, investigating the existing HEC concepts and defining for them a taxonomy. The taxonomy aims at highlighting the node structure, the exchange of information between units, the resource and service management, and the solutions adopted in terms of privacy and security. We must

Edge Selection Strategies for Human-enabled Sensing Architectures

Università degli Studi di Pisa

Dipartimento di Informatica

Dottorato di Ricerca in Informatica

Ph.D. Thesis

Edge Selection Strategies for Human-enabled

Sensing Architectures

Dimitri Belli

Supervisor

Supervisor

Prof. Stefano Chessa

Dr. Michele Girolami

Year

Acknowledgments

Abstract

Contents

1 Introduction ... 14

1.1 Research Questions and Objectives ... 17

1.1.1 M

EC Selection ... 18

1.1.2 FMEC and M

EC Configuration ... 19

1.2 Thesis Contribution ... 20

1.3 Thesis Structure ... 22

2 Background and Related Work ... 24

2.1 Mobile CrowdSensing ... 25

2.1.1 The Role of MCS in SC ... 27

2.1.2 MCS System Architecture ... 28

2.1.3 Issues and Limits ... 31

2.2 Multi-Access Edge Computing ... 33

2.2.1 The Role of MEC in 5G Networks ... 34

2.2.2 MEC System Architecture ... 36

2.2.3 Issues and limits ... 37

2.3 A Taxonomy of MEC Architectures in HEC ... 38

2.3.1 The HEC Architecture ... 39

2.4 Human Mobility Traces ... 49

2.5 The ParticipAct Living Lab ... 52

2.5.1 Qualitative Analysis of the ParticipAct Dataset ... 54

2.6 Community Detection Algorithms ... 55

2.6.1 TILES ... 56

2.6.2 Infomap ... 57

2.6.3 iLCD ... 58

2.6.3 DBSCAN... 58

3 A User Recruitment Framework for HEC Platforms ... 60

3.1 Reference Scenario ... 61

3.3 Results ... 66

3.4 Summary ... 71

4 Edge Selection for HEC ... 72

4.1 Reference Scenario ... 73

4.2 M

EC Selection Algorithm ... 74

4.2.1 Cooperative M

ECs ... 76

4.2.2 Social M

ECs ... 77

4.3 Experimental Settings and Metrics ... 78

4.3.1 FMECs Vs M

ECs ... 80

4.3.2 Cooperativity Vs Centrality ... 81

4.4 Results ... 82

4.4.1 M

ECs Vs FMECs ... 82

4.4.2 Cooperativity Vs Centrality ... 85

4.5 Summary ... 88

5 A Probabilistic Model for M

EC Selection ... 90

5.1 Detecting Communities with Spatial Clustering ... 91

5.1.1 Evaluation Metrics ... 93

5.2 A Generic M

EC Selection Algorithm ... 96

5.3 The Probabilistic Model ... 98

5.3.1 Model Calibration ... 100

5.3.2 Contribution of the M

EC in the Dataset ... 101

5.3.3 Experimental Results ... 101

5.4 Summary ... 105

6 Selection of M

ECs for Hybrid HEC Architectures ... 107

6.1 Methodology and Experimental Settings ... 108

6.2 FMEC and M

_{EC Selection ... 18}

_{EC Configuration ... 19}

_{EC Selection Algorithm ... 74}

_{ECs ... 76}

_{ECs ... 77}

_{ECs ... 80}

_{ECs Vs FMECs ... 82}

_{EC Selection ... 90}

_{EC Selection Algorithm ... 96}

_{EC in the Dataset ... 101}

_{ECs for Hybrid HEC Architectures ... 107}

_{EC Selection Strategy ... 109}

_{EC Selection Strategies ... 113}

_{EC Selection ... 119}

_{EC Mobile Multi-access Edge Computing}

_{EC Selection}

_{EC Configuration}