RESOURCES OPTIMIZATION FOR DISTRIBUTED MOBILE PLATFORMS IN SMART CITIES

Conclusions

In this chapter, a cost function has been defined for optimizing contemporaneously time and energy consumption in a scenario where smart mobile devices are supposed to perform an application; the aim was to optimize the amount of computation performed locally and remotely. The remote execution is faster and can relieve mobile devices from the correlated energy consumption, but it involves data exchange with the cloud server, spending time and energy to transmit, depending also from the load of the HetNet. The cost function is proposed to evaluate the percentage of application to offload for time and energy optimization. The results show that for applications requesting both high execution work and data exchange a particular value of this percentage, depending on the number of devices, optimize the performance.

Introduction

New user's needs cause a major boost of wireless communication techniques employed in smart cities, as well as a rapid growth and diffusion of enhancing technologies. To achieve the goal of interacting with city services, allowing to simplify everyday life, MCC and HetNets become together the killer applications for resolving the significant facing problems: the former for offloading application to powerful remote servers, shortening execution time and extending battery life of mobile devices, the latter for exploiting high-speed and stable connectivity in an ever grown mobile traffic trend, allowing the use of small cells in addition to macrocells [23]. In such a scenario users can access to remote resources without interruption in time and space.

In this context, energy saving and performance improvement of SMDs have been widely recognized as primary issues. In fact, the execution of every complex application is a big challenge due to the limited battery power and computation capacity of the mobile devices [25]. The distributed execution between the cloud and mobile devices has been widely investigated [9], highlighting the challenges towards a more efficient cloud-based offloading framework and also suggesting some opportunities that may be exploited. Indeed, the joint optimization of HetNets and distributed processing is a promising research trend [5]. We envision that the success of HetNets, jointly with MCC, would ultimately depends on user satisfaction, which in turn relies on saving energy and computing application quickly. Identifying the relevant QoS for each of the diverse application types and distinguishing the variation of user satisfaction related to the QoS is a research challenge [36].

Various mobile data offloading policies are proposed in the literature where the partial offloading of data to the network infrastructure is performed according to the variations of the network conditions and the operator strategies [37]; however, a model related to user satisfaction regarding battery saving and speed of computation is not already taken in consideration.

In this chapter we propose a utility function model that takes into account a series of parameters related to HetNet's nodes, SMDs' characteristics and types of performed application. We categorize applications in different classes, and consider for each application type the amount of data and computation transferred to the MCC and how the HetNet traffic load affects the power consumption of the SMDs and their execution time. The opportunity to move to the cloud a portion of the computing application is taken into account, because the decision whether moving the computation tasks of mobile applications from the local SMDs to the remote cloud involves a tradeoff between energy consumption and computational time [38].

System Model

The system model we are focusing on relies on the results of the chapter 2.. We consider a reference scenario analogous to fig. 2.1, but, in this case, various SMDs are requesting three different types of application, with a casual uniform distribution. Each type is partially offloaded giving the optimization problem investigated previously. The SMDs are interacting with a traditional centralized cloud requesting for offloading through two types of RAT that compose the basic elements of the HetNet: macrocells and small cells.

Recalling the characteristics the system is premised on, we can summarize:

• a certain application requires $O$ operations and $D$ data,
• the speeds of the mobile device and of the cloud server are, respectively, $S_{\textit{md}}$ and $S_{\textit{cs}}$
• the speed of the mobile device for transferring data to the access point is $S_{\textit{tr}}$
• the weight coefficients representing, respectively, the fraction of the computational task and the fraction of the data sent for the offloading are ${\gamma}$ and ${\delta}$, satisfying ${0 \le \gamma ,\delta \le 1}$

We recall also that the transmission time is mostly due to the access network transfer, by considering as negligible the transfer time on the backbone network between the access point and the cloud server, due to the higher data rate, and the return time from the cloud server to the user terminal because the amount of data in response to the elaboration in the cloud server is small with respect to the data sent toward the cloud server [32], [33].

The values $\gamma$ and $\delta$, previously found in the optimization procedure of chapter 2, have been considered here for each selected application. We will focus on three application types, characterized by a specific amount of required operations $O_k$, amount of data that need to be exchanged $D_k$, fraction of offloaded computational tasks $\gamma_k$, and fraction of offloaded data $\delta_k$, as defined in Table 3.1. The considered application classes are:

• Real time road traffic analysis: the applications aiming to optimize the route toward a certain destination (e.g., navigation applications);
• Mobile Video and Audio Communications: the applications that elaborates user generated audio and video content;
• Mobile Social Networking: the applications used for social networking.

In order to describe the throughput, the consumed energy and the time spent by a device for the computation - the three measures we chose for the QoS evaluation - let us focus now on the network infrastructure, by considering a generic couple composed by the $i$-th access point and the $j$-th SMD.

Throughput ${S_{\textit{tr},\textit{ij}}}$ The throughput ${S_{\textit{tr},\textit{ij}}}$ is affected by the bandwidth ${\textit{BW}}_{i}$ of the $i$-th access point, by the distance ${d_{\textit{ij}}}$ between the access point and the SMD, by the signal to noise ratio $\textit{SNR}_i$ at the receiver, and by the number of devices $n_i$ already connected to the $i$-th access point. By resorting to the Shannon formula, the throughput ${S_{\textit{tr},\textit{ij}}}$ can be written as:

Energy $E_{\textit{part}\_\textit{od},\textit{ijk}}$The energy spent for the partial offloading can be written as the sum of the energy spent to perform locally a part of the task and the energy spent during the idle period and during the transmission of the remaining part of the task to the cloud; the idle period corresponds to the amount of time needed by the cloud to perform the computation: we suppose that during this time the SMD remains in an idle state. In this case it is possible to derive the overall spent energy for the $k$-th application as:

where $P_{l,j}$ corresponds to the power consumption for performing the local computation by the $j$-th SMD, $P_{\textit{id,j}}$ is the power consumption of the $j$-th SMD in idle state, $P_{\textit{tr,ij}}$ is the power consumption of the $j$-th SMD for transmitting the data to the $i$-th access point, and $S_{\textit{md,j}}$ is the computing speed in operations per second of the $j$-th SMD.

Time $T_{\textit{part}\_\textit{od},\textit{ijk}}$The computation time for executing the application can be written as the maximum value between the time needed to compute the local portion of the task and the time needed for the offloaded portion; we have supposed that the two phases can be performed at the same time, so that the overall time corresponds to the maximum value:

User-Satisfaction Based Utility Function

We introduce, for each of the three quality parameters taken in consideration, a function representing the QoS degree perceived by the user. The functions are modeled as sigmoid curves, since they are well-known functions often used to describe QoS perception [24], [36], [39]. A sigmoid curve can be defined as:

Focusing on the three QoS parameters we are considering, i.e., throughput, energy and time, it is possible to define the related sigmoid functions, by taking into account that the user satisfaction grows with higher throughput values and lower energy and time values. To this aim, concerning the user throughput, it is possible to define the related sigmoid function as:

where $S_{\textit{tro,k}}$ is the objective throughput value for the $k$-th application.

On the other hand, since the energy and time parameters need to decrease for increasing the user satisfaction, the related cost functions need to be decreasing sigmoid functions defined as:

The parameter $\alpha_q$ ($q = 1,2,3$) is defined as the steepness of $f_q$ and is related to the user's sensitivity to the QoS degradation of the $q$-th parameter. The parameters $S_\textit{tro,k}$, $E_\textit{o,k}$ and $T_\textit{o,k}$ are the center points of the curves $f_q$, indicating the acceptable region of operation. $S_\textit{tro,k}$ and $T_\textit{o,k}$ are reference values for the data transmission rate and the computing time related to the type of application requested, whereas $E_\textit{o,k}$, the energy spent to compute le application locally, is also associated to the type of device in addition to the type of application. For the goal of this study, referring to network analysis rather than SMD's types analysis, we considered values of $E_\textit{o,k}$ dependent only to application types. The values of $S_\textit{tro,k}$, $E_\textit{o,k}$ and $T_\textit{o,k}$ in relation with the application classes are defined in tab. 3.2.

On the basis of the QoS sigmoid functions, we introduce a model developed from the economic concept of utility function [39]. By focusing on the access point $i$ (related to the type of RAT) and the SMD $j$, the cost function for the association of the $j$-th SMD to the $i$-th access point is given by:

where $S_{\textit{tr},\textit{ij}}$, $E_{\textit{part}\_\textit{od},\textit{ijk}}$ and $T_{\textit{part}\_\textit{od},\textit{ijk}}$ are the QoS parameters related to the connection between the $i$-th access point and the $j$-th SMD for partial offloading of the $k$-th application. The weight parameters $c_q$ are associated to the importance of the respective quality-related parameters in the performance of the application. For example, for an application of type 1 (real time road traffic analysis) a high weight $c_1$ (related to $S_\textit{tr}$) is required, rather then in an application of type 2 (Mobile Video and Audio Communication) where it is more important to have a low delay time, therefore a high value of $c_{3}$.

The weight parameters $c_q$ are normalized with respect to a certain application, so that it is possible to assume that: $$\sum_{h=1}^3 c_h=1. \tag{3.9}$$ for each application $k$. Table 3.3 shows the considered weight parameters for each type of application; it is worth to be noticed that, higher is a certain parameter $c_k$ for a certain application $k$, higher is the importance of the related QoS parameter for the selected application.

Cell Association

The above defined utility function is at the basis of the CA scheme that allows the selection of the best access point by the SMD, for respecting the requirements of the considered applications; whenever a SMD requests to offload an application, the utility function is evaluated for each access point of the network. The SMD will connect to the access point with the maximum utility function.

The selection of a certain access point for establishing the connection could modify the values $S_\textit{tr}$, $E_{\textit{part}\_\textit{od}}$ and $T_{\textit{part}\_\textit{od}}$ for the SMDs already connected with the same access point. Hence, the utility function related to those SMDs is evaluated again, by considering the new incoming SMD. The cell association algorithm is reported in Algorithm 1, where it is possible to note the utility function elaboration and the updating of the utility function for all the SMDs already connected to the selected access point.The CA algorithm is performed for all the SMDs in the scenario.

Algorithm 1 - Cell Association.

Numerical Results

This section deals with the numerical results of the proposed utility function approach by resorting to computer simulations. The smart city scenario has been modeled in Matlab by considering a randomly placed number of SMDs in a deployment area of $1000\times1000\ m^2$, where one LTE eNodeB with channel capacity equal to 100 MHz and three WiFi access points with channel capacities equal to 22 MHz are positioned to cover the entire area. The SMDs, positioned randomly, will connect to one of the access point/eNodeB, depending on the cell association policy; to this aim we suppose that all the SMDs are capable to connect to both WiFi and LTE. The infrastructures are positioned in the same configuration as represented in Fig. 2.3, where the access points are positioned at point (0,0), (500,1000) and (0,1000), and the LTE eNodeB at (500,500).

The SMDs, positioned randomly, request in sequence to offload a random application type and are connected accordingly, on the basis of the presented cell association algorithm. The values $S_{\textit{md}}$, $P_{\textit{id}}$, $P_{\textit{tr}}$ and $P_l$ are specific parameters of the mobile devices. We utilized the values of an HP iPAQ PDA with a 400 MHz Intel XScale processor ($S_{\textit{md}}=400$) and the following values: $P_l\approx0.9 W$, $P_{\textit{id}}\approx0.3 W$ and $P_{\textit{tr}}\approx1.3 W$. As for the cloud server used for the offloading we suppose that $S_{cs}$ = 8000 [32].

In the same way used for the utility function, we have resorted to the following values for the steepness of the sigmoidal functions: $\alpha_1 = 1.6\cdot 10^{-3}$, $\alpha_2 = 10^{-6}$, and $\alpha_3 = 10^{-6}$. These values have been selected after a numerical optimization phase as reported in chapter 2. We have supposed that the three applications are equally distributed among all the SMDs existing in the environment, so that they have same probability equal to 1/3.

The numerical results are reported by focusing on the performance in terms of average energy consumption, computational time and throughput for each SMD. The numerical results have been compared with three other approaches: local computation, total offloading and nearest node. For the local computation algorithm is assumed that the computation is performed locally by each SMD; in this case no data is exchanged on the network. In the total offloading algorithm an opposite situation is assumed, since nothing is computed locally, while the entire data load is offloaded to the centralized cloud servers. The nearest node algorithm, finally, assumes that each SMD will connect to the nearest AP/eNodeB.

In fig. 3.1 the results in terms of energy consumption are reported. It is possible to note that both the utility function and the nearest node approaches outperform the local computing and the total offloading. Moreover, it is possible to note that the utility function algorithm allows to have almost the same values for different numbers of nodes, outperforming the nearest node approach for increasing number of SMDs. A similar behavior can be noted in terms of average time for executing the application, in fig. 3.2, where, also in this case, the utility function algorithm outperforms the other approaches.

In fig. 3.3, the performance in terms of average throughput has been reported. In this case the performance for the local computation approach is not reported because in this case no data transfer occurs. It is possible to note that the throughput for the utility function algorithm remains stable, hence giving an optimized value to each SMD, while in the nearest node approach the throughput decreases when the number of SMDS increases.

Fig 3.1 - Performance results in terms of average energy consumption with a variable number of SMDs.

Fig 3.2 - Performance results in terms of average computation time with a variable number of SMDs.

Fig 3.3 - Performance results in terms of average throughput with a variable number of SMD.

Conclusions

In this chapter we introduced a utility function derived from the economic world aiming to optimize the cell association of the smart devices for achieving low energy consumption and computational time while maximizing the overall throughput. The proposed approach allows to increase the performance with respect to a nearest node association, and with respect to statical approaches where the computation is performed locally or is completely offloaded.

Introduction

The evolutionary trends of the Information Society have lead to the definition of the smart city as the most challenging scenario for the IoT applicability. Among several things composing a smart city, the computing infrastructures are responsible for giving a distributed elaboration intelligence to the environment aiming at providing unprecedented services and efficiency. The increasing number of devices, appliances, smartphones and objects connected to the Internet has lead to the introduction of the IoT paradigm, aiming at design the network infrastructure as composed by a multitude of devices collaborating each others. Among several different functions provided by the IoT devices, the distributed computing approach seems to have an increasing interest allowing to establish an interaction between the IoT and the MCC worlds [7], [40].

This chapter takes into consideration the computation offloading towards other SMDs pooled together, in addition to powerful remote servers, with the aim of an exploitation for shortening execution time and extending battery life. The actual innovation is to take into account different types of mobile cloud infrastructures, considering also a non-trivial extension of the MCC paradigm to the edge of the network, where a collaborative crowd of end-user clients or near-user edge devices share storage, communication, computation, and control. In this context, the issues of mobile device energy saving and performance improvement become increasingly a source of concern, because of the strict constraints on their memory capacity, network bandwidth, CPU speed and battery power [25]. The proposed cluster based computation offloading technique is able to work in a distributed environment, in order to better satisfy the QoS requirements of the SMD users, by minimizing a cost function that takes into account the already mentioned tradeoff between SMD's energy consumption and execution time. By analyzing an actual case of this very complex system, we introduce an algorithm for offloading a real-time navigation application in a distributed fashion, aiming to minimize the execution time.

Although the computation offloading can significantly increase the data processing capabilities for each mobile user, it is challenging to achieve an efficient coordination among the entire set of requesting devices, because this operation can affect the efficiency of the CCIs, since the channel capacity has to be shared among all the devices, causing a reduction of the throughput experienced by each user. This could make not convenient the offloading operation [41].

Several excellent works have been done to study cloud and radio resource management issues; among them in the last years there is an increasing importance in the collaborative mobile device offloading [42], [43], [44], as well as other considerable studies that face up jointly to clouds and fog architectures [13], [45]. Further, this investigation proposes a system model that takes into account jointly a series of features related to HetNet nodes, different CCIs - in particular a distributed cloud of devices merged together to share resources - and various SMDs’ characteristics [46], [47].

In this chapter we consider a system where users can interact with all the different topologies of cloud - centralized, cloudlets, and distributed mobile cloud - as described in section 1.2. This allows users to optimize the system performance by offloading a fraction of the application among different cloud structures. The advantage of this approach consists in computing the application that is referred to a specific service exploiting the different cloud infrastructures and network technologies, optimizing important characteristics of the system, i.e. maximize throughput and time computation or minimize the energy used by the SMDs.

A cost function is introduced to optimize the nodes assignment and the resources allocation for distributing the application through the system. In particular we focused on a cluster based solution aiming at exploiting the MCC environment for executing an application in a distributed fashion, for handling a real-time navigation application in a vehicular environment.

Application Scenario

We consider a UMCC environment where each SMD aims at performing an application, interacting with many CCIs through different wireless connections, in order to distribute the computation load to one or more CCIs and receive data results from the CCIs themselves. We will consider the possibility of distributing the computation load exploiting multiple CCIs at the same time, for offloading to each one of them a different part of the application. In this chapter we neglect the storage optimization, since each device is supposed to own a storage capacity fitting its computation load. This simplification allows to focus on the proper computation offloading optimization.

A SMD can delegate computation functions towards one or more CCIs for performing the requested application. The CCIs can be distinguished on the basis of their features and are classified following the three types described in section 1.2: an ubiquitous centralized cloud infrastructure, many roadside cloudlet infrastructures, and a distributed cloud infrastructure composed by neighboring SMDs pooled together for resource sharing. The centralized cloud refers to an infrastructure with a huge amount of storage space and computing power, virtually infinite, offering the major advantage of the elasticity of resource provisioning. The cloudlets are instead fixed small cloud infrastructures available in a delimited area, installed in proximity of the users and provided with a dedicated transmission node that supports the wireless communication into this area. Finally, the distributed cloud is a a Mobile Ad-hoc Network (MANET) composed by the neighboring SMDs.

From the computational point of view, the centralized cloud allows to reduce the computing time by exploiting powerful processing units, but it could suffer from the distribution latency, due to the remote data transfer. Cloudlets, instead, allow to decrease the distribution latency with respect to the centralized cloud, but the storage capacity and the computation power are reduced. Finally, a distributed cloud is composed by the SMDs themselves sharing their own amount of resources depending on the instantaneous usage.

The communication side consists of all the wireless connections available within the selected smart city environment allowing to exploit the centralized cloud, various cloudlet nodes and the SMDs themselves. Aim of the selected system is to divide a certain smart city application into different parts and distribute them among the available nodes. In case a fraction of an application is distributed towards the centralized cloud infrastructure, one of the available HetNet nodes is used for the offloading operation. In case of computation offloading towards a roadside cloudlet infrastructure, the only available node is the one provided in the proximity of the cloudlet itself. In case of computation offloading towards other SMDs belonging to the distributed cloud infrastructure, the transferring operation is made directly by the SMD. Besides, part of the application can be computed locally by the SMD requesting the application. Referring to figure 1.3, we consider the complete distribution, exploiting each of the CCIs represented.

The Partial Distributed Offloading Model

Even if every SMD of the system can simultaneously requests the computation offloading of one or more applications, we are focusing on a scenario where a single requesting smart mobile device wants to perform an application $App$, whereas all the other SMDs are considered only for receiving and computing it. This simplification does not prevent the generalization of the system, as we can consider the general case as an extension composed by the overlapping of many simplified cases.

The application $App$ is defined through the number of operations to be executed, $O$, and the amount of data to be exchanged, $D$. The $App$ is running on a certain SMD, named Requesting Smart Mobile Device RSMD, that is the SMD requesting to the CCIs to execute the $App$. We focus for the moment on the presence of a single $App$ and a single requesting RSMD.

We suppose that the system demands some features in terms of QoS, in order to have a reliable execution of the $App$. We have taken into account:

• latency: the interval between a task of the application is requested and its results are acquired,
• energy consumption: the amount of energy the RSMD consumes for performing the application.

Thus, being $T_{\textit{RSMD}}$ and $E_{\textit{RSMD}}$, respectively, the amount of time and energy spent by the RSMD for offloading the application, the system optimization consists in minimizing a weighted sum of the normalized $T_\textit{RSMD}$ and $E_\textit{RSMD}$, giving more weight to the first or the second parameter depending on the importance of minimizing the energy consumption or the latency:

where $w_E$ and $w_T$ are the weight coefficients, and $E_o$ and $T_o$ reference values.

Both $T_\textit{RSMD}$ and $E_\textit{RSMD}$ depend on the parameters $O$ and $D$ of the $App$ and on the overall throughput $\eta_\textit{RSMD}$ between the nodes and the RSMD, hence, we can rewrite the eq. \eqref{eq:latency-energy}, for emphasizing this dependency, as:

The system is composed by $M$ available HetNet nodes for offloading towards the centralized cloud (marked as $\textit{HN}$), $N$ cloudlets nodes (marked as $\textit{CL}$), and $K$ SMDs' nodes (marked as $\textit{MD}$), for sharing the computation in the distributed cloud. Thus, being $\eta_\textit{Xi}$ the throughput offered by the $i^{th}$ node of type $X$, where $X$ stands for $\textit{HN}$, $\textit{CL}$, and $\textit{MD}$, it results that $\eta_\textit{RSMD}$ is the sum of the throughput offered by the nodes available for the transfer operation:

where we suppose that the RSMD can connect ideally with all the available nodes. The throughput $\eta_\textit{Xi}$ is related to the number of SMDs $n_\textit{Xi}$ connected to the $i^{th}$ node and the channel capacity $BW_\textit{Xi}$ of the $i^{th}$ node, and can be expressed by resorting to the Shannon Formula:

where $\textit{SNR}$ is a reference signal to noise ratio value of the RSMD at a distance equal to 1m and $d_\textit{Xi}$ is the distance between the RSMD and the $i^{th}$ node. We have considered for simplicity a no fading-affected channel; this simplification does not affect the operating principles of the framework. Furthermore, we assume a uniform distribution of the available bandwidth among all the $n_\textit{Xi}$ nodes.

$T_\textit{RSMD}$ can be defined as the sum of the time spent to perform locally part of the task, $T_\textit{l}$, plus the time spent to transmit data to the clouds, $T_\textit{tr}$, plus the time spent during the idle period, $T_\textit{id}$, waiting for the computation performed outside and the results transmitted back. In this case we assume that the transmission time is mostly due to the access network, because the backbone network data rate is much higher. Hence, we can write:

$T_\textit{l}$ can be evaluated as the ratio between the fraction of operation computed locally, $\alpha_0 O$ (where $\alpha_0$ is the percentage of operations $O$ computed locally), and the computing speed of the RSMD, $f_\textit{l}$:

$T_\textit{tr}$ is the sum of the transferring times towards each node, corresponding to the ratio between the amount of transferred data $\beta_\textit{Xi} D$ (where $\beta_\textit{Xi}$ is the percentage of transferred data $D$ to the $i^{th}$ node), and the throughput of the node, $\eta_\textit{Xi}$. Thus we can write:

$T_\textit{id}$ depends on the starting time and the duration of the offloaded computations. Since each CCI is able to compute it own task independently and simultaneously with the other CCIs, and since an offloaded computation cannot begin until all the data needed for performing it are provided, $T_\textit{id}$ would be optimized.

We consider for simplicity the worst case for $T_\textit{id}$, i.e., the maximum value among every duration of the offloaded computations. Furthermore, by defining as $f_\textit{CLi}$ and $f_\textit{MDi}$ the computing speed of the $i^{th}$ cloudlet and the $i^{th}$ SMD, respectively, and $f_\textit{CC}$ the computing speed of the centralized cloud, and considering $\alpha_\textit{Xi}$ the precentage of computed operations $O$ within the $i^{th}$ node, $T_\textit{id}$ can be written as:

$E_\textit{RSMD}$ can be defined as the sum of the energy spent to perform locally part of the task, $E_\textit{l}$, plus the energy spent to transmit data to the clouds, $E_\textit{tr}$, plus the energy spent during the idle period, $E_\textit{id}$, waiting for the computation performed outside and the results transmitted back:

$E_\textit{l}$ is obtained by multiplying the \gls{RSMD}'s local computation power consumption, $P_l$, by the time consumed for computing locally the application:

$E_\textit{tr}$ is determined by the power consumption of the RSMD for transmitting, $P_\textit{tr}$, multiplied by the transferring time. Thus we can write:

$E_\textit{id}$ corresponds to the idle time $T_\textit{id}$, thus, taking into account the same considerations used for $T_\textit{id}$, we can write the following:

Thus, the optimization model consists in finding the values $\alpha_\textit{Xi}$ and $\beta_\textit{Xi}$ that minimize the equation \eqref{eq:latency-energy2}, by taking into account the relationships defined in equations \eqref{eq:throughput4}, \eqref{eq:shannon4}, \eqref{eq:latencyRSMD}, \eqref{eq:Tl}, \eqref{eq:Ttr}, \eqref{eq:Tid}, \eqref{eq:energyRSMD}, \eqref{eq:El}, \eqref{eq:Etr}, and \eqref{eq:Eid}. The model constraints are derived from the observation that the sum of the offloaded fractions must be equal to 1, thus the optimization problem becomes:

The obtained minimization problem cannot easy solved, so that, in the following section, we will resort to a sub-optimal solution based on a clusterization approach.

Cluster based optimization

The idea is to divide the urban area in subareas having range $r$; each SMD can share resources only with the other SMDs, cloudlets, and HetNet access points placed in the same subarea. This approach, even if sub-optimal, can simplify the problem by reducing the amount of concurrent devices that are involved in the computation offloading. This means, on the other hand, that we have to select the most appropriate cluster size.

If we define with $M_r$, $N_r$ and $K_r$, the number of HetNet access points, cloudlets and SMDs, respectively, within the cluster having range $r$, it is possible to write the transferring time needed by a single RSMD as:

Let us suppose that among the $K_r$ SMDs within a cluster, $\bar{K}_r \leq K_r$ have an active task to be computed that can be offloaded to the surrounding nodes. Without going into the details of a scheduling algorithm to be used by the cluster based SMDs, we suppose that the $Apps$ are computed by all the SMDs that act as a pool of resources, by exploiting a RAN as a Service (RANaaS) cloud model [48]. In this case it is possible to calculate the overall transferring time as:

where $D_j$ is the amount of $App$ data requested by the $j^{th}$ RSMD. Similarly, it is possible to write the overall energy needed by the $\bar{K}_r$ nodes for offloading the task as:

From equations \eqref{T_tr_tot} and \eqref{E_tr_tot}, it is possible to observe that the transferring time related to the offloading within the SMD cluster is proportional to the square of the number of the SMDs, i.e., $T_\textit{tr,r},E_\textit{tr,r} \propto~K_r^2$, whereas it is linearly proportional to the number of SMDs in case only the centralized cloud or the cloudlets are used, i.e., $T_\textit{tr,r}, E_\textit{tr,r} \propto~K_r$; hence, it is possible to state that there is an optimal number of devices ${K}^o_{r}$ within a cluster such that, for $K_r\le{K}^o_{r}$ the offloading towards the centralized cloud is the optimal solution, whereas for $K_{r}>{K}^o_{r}$ the best performance is obtained for the distributed cloud. This means that the cluster size affects the optimization problem.

Since the numbers of SMDs affect primarily the transferring time and energy consumption, we focus our attention on their behaviour, without focusing on the idle and local time and energy consumption. Hence, the optimization problem in \eqref{eq:optim-model}, can be rewritten as:

where the aim is to minimize the linear combination of latency and energy consumption by selecting the cluster size $r_o$ that contains the optimal number of devices ${K}^o_{r}$: this corresponds to estimate the density of the surrounding nodes and select the cluster size by comparing their amount with the optimal number. It is worth to be noticed that the density estimation of a distributed network has been studied in the literature by resorting to specific algorithms, such as in [49]. Hence, for a given scenario, once estimated the SMDs density, it is possible to set the cluster size based on ${K}^o_{r}$.

Once set the cluster size, with respect to the offloading problem, if $K_r\le{K}^o_{r}$, it is convenient to set $\sum_{i=1}^{M_r}{\alpha_\textit{HNi}}=1$ and $\sum_{i=1}^{M_r}\beta_\textit{HNi}$=1, that corresponds to a complete offloading towards the centralized cloud, whereas it is better to perform the offloading towards the nodes in the cluster for $K_r>{K}^o_{r}$. In this case we consider $\alpha_\textit{CLi} =\beta_\textit{CLi}$ and $\alpha_\textit{MDi}=\beta_\textit{MDi} $ for every node of the distributed cloud, since it is reasonable that the amount of processed data is proportional to the computation load; furthermore, we choose $\alpha_\textit{CLi}$ and $\alpha_\textit{MDi}$ s.t. $\alpha_\textit{CLi}/f_\textit{CLi} = \alpha_\textit{MDi} / f_\textit{MDi}$ for every node, since this is the value that minimize equation \eqref{eq:Tid} and, hence, equation \eqref{eq:latencyRSMD}.

Numerical Results

In order to prove the effectiveness of the proposed approach, we resort to a typical scenario for an Intelligent Trasportation System (ITS) proposed by Yu et al. [20], composed by the three-layered hierarchical cloud architecture for vehicular networks where the SMDs exploit cloud resources and services in an environment composed by vehicular clouds (i.e., the distributed topology), a set of roadside cloudlets, and a centralized cloud (see Fig. 4.1).

Fig 4.1 - Realtime navigation with computation resource sharing, connection with the centralized cloud, the nearest cloudlet and near vehicles.

All the devices are supposed to be connected for improving transportation safety, relieve traffic congestion, reduce air pollution and enhance comfort of driving. The selected real-time application, unlike a traditional navigation - which only provides static geographic maps - could be able to offer dynamic three-dimensional maps and adaptively optimize routes based on traffic data mining. Thus, the computational time requirement is of utmost importance. On the other hand, considering that the great part of the involved mobile devices can be recharged directly from the cars in which they are placed, they do not need a restrictive energy consumption requirement. Due to these considerations, we focused the optimization problem for this scenario on a sub-optimal solution minimizing $T_\textit{RSMD}$, i.e. we consider the weight coefficients $w_E = 0$ and $w_T = 1$ and we assumed that all the devices are requesting the same application. Also the storage requirement could be neglected, while we established that the number of operations $O$ to be executed is equal to $10^6$ flops and the amount of exchanged data $D$ by each $App$ is equal to 0.5 Mbit.

In our scenario we considered a linear road 1000 m long with the presence of one centralized cloud with a computation rate $f_\textit{CC}$ equal to $10^3$ Gflops, obtained by an Amazon EC2 Cluster GPU instance, through a unique Proxim Tsunami MP 8250 Base Station Unit 4G placed in the middle of the road (at point 500), with a channel capacity equal to 300 Mbps.

A set of four roadside units are the cloudlets evenly positioned at the relative positions of 125, 375, 625, 875 m respectively. Every cloudlet is a compute-box using Nvidia GT520 GPUs with a computing capability $f_\textit{cl}$ equal to 150 Gflops [50]. The offered throughput of the cloudlet $\eta_\textit{cl}$ is 40 Mbps (considering one LTE cloudlet-devices link), with a coverage range $r_{\text{cl}}$ equal to 250 m, so that each cloudlet covers only a limited part of the road.

The SMDs are placed along the route with a uniform distribution, simulating a road where a fluent traffic is present. The SMD computational speed $f_\textit{dev}$ is equal to 10 Gflops, while their offered throughput $\eta_{dev}$ is equal to 10 Mbps - considering to use the IEEE 802.11p vehicle-to-vehicle standard - and a reference SNR equal to 30 dB. We considered also, for the energy evaluation, the parameters of an HP iPAQ PDA with $P_l$ equal to 0.9 W, $P_{\textit{id}}$ equal to 0.3 W, $P_{\textit{tr}}$ equal to 1.3 W.

We have chosen different cases for partitioning the subareas of the distributed clouds, with ranges equal to 250 m, 50 m, 25 m, and 10 m, where every SMD can share resources with the other SMDs placed in the same subarea.

In Fig. 4.2 the performance in terms of average latency for an increasing number of SMDs by comparing the total offloading towards the centralized cloud and the distributed clouds is depicted. Four possible clusterizations for the distributed cloud infrastructure are considered; furthermore the total offloading to the nearest cloudlet is also considered. These are compared with the local computation as a benchmark. Moreover, the optimal solution is reported, where the range is selected based on the SMD density.

Fig 4.2 - Average latency vs the number of RSMDs, in a fluent traffic scenario.

It is possible to see that by varying the number of SMDs inside the considered area, the most efficient CCIs, to which is convenient to offload, change. In particular for a low density of SMDs it is convenient to offload towards the centralized cloud, corresponding to set the cluster range to infinity, while the cloudlets are convenient just over. This is because in case of low density the SMDs are isolated and, moreover, their communications through the eNodeB -i.e., centralized cloud or cloudlets- have a limited intra-system interference. However, when the number of SMDs increases it is possible to see that the use of the distributed cloud become more convenient, with the cluster size reducing with the increasing of the SMDs. The optimal solution allows to select the best cluster range based on different density situations by approaching always the best cluster size. It is worth to be noticed that the optimal number of SMDs $K^o_r$, in this case, is equal to 50.

In Fig. 4.3 the average energy consumption is depicted by considering a variable number of SMDs, and considering the same cluster sizes as in Fig. 4.2. Even if the energy issue does not affect the operations of this particular scenario, where all SMDs are supposed to have unlimited energy since reloaded by the cars' resources, we can consider this issue from an echo-friendly point of view. Comparing the trends of the consumed average energy in the various cases, it is undeniable that the clusterization allows to reduce the consumed energy in case of high traffic scenarios as those present in a smart city environment, and the optimal solution allows to select for different populations the best cluster size, and offloading policy.

Fig 4.3 - Average Energy vs the number of RSMDs, in a fluent traffic scenario.

Finally, in Fig. 4.4 the performance in terms of throughput is shown by comparing the distributed cloud infrastructure with 10 m of range, the total offloading toward the central cloud and the nearest cloudlet and the optimal solution. It is possible to note that the distributed offloading technique outperform the other techniques, except in case of low density of the nodes.

Fig 4.4 - Average throughput vs the number of RSMDs, in fluent traffic scenario.

Conclusions

In this chapter an optimization model for supporting the computation offloading in the UMCC is conceived in a particular IoT scenario, where the objects, consisting of different CCI, can interact through different types of wireless connections, for creating a distributed computing environment. The distributed computing resource allocation results to be a complex problem due to the presence of several devices and possible wireless connections, thus, we resort to decreasing its complexity by considering a clustering approach for the resource sharing, observing that the use of cluster offloading is useful especially for high density SMD distribution. The numerical results, based on a scenario performing a real-time navigation application of with computation resource sharing, confirm the advantages of the clusterization especially in dense scenarios.

Introduction

In this chapter the UMCC is exploited for accomplishing applications in a cooperative way while satisfying the QoS requirements for the citizens involved. By taking into account all users in the assignment process, the proposed biased-randomized algorithm allows to enhance social-aware performance as compared with the greedy approach while, at the same time, it allows for online allocation of resources.

Although the computation offloading can significantly increase data processing capability for the single mobile users, it is challenging to achieve an efficient coordination among the entire set of requesting devices when the environment is particularly crowded. In fact, the computation offloading entails data transmission among the devices and the cloud, to make the operation possible. If a great number of users utilize the same wireless resource to delegate computation to the cloud, this operation can affect the efficiency of the access node, since its channel capacity has to be shared among all the devices, causing a reduction of the throughput experienced by each user. This can lead to a crucial use of energy and time spent for data transmission, making not convenient the offloading operation [41].

In this chapter we present a probabilistic method that makes use of biased-randomization techniques to solve the CA problem, i.e. to select, among the available access nodes, the one that increases the system efficiency. This method is compared with the global optimization solution, that is shown to be unacceptable from a point of view of time computation, and with a greedy algorithm [52], that instead implement a selfish behaviour in allocating the resources to the users. All the three techniques - the probabilistic, the greedy and the optimal - are based on the definition of a proper cost function that takes into account the different requirements and characteristics of the considered UMCC framework. We will consider, for our example and calculation, the throughput, the energy consumption, and the delay as those parameters that drives the optimal allocation of the resources to be offloaded.

The novel proposed algorithm improves the solutions and is easy to implement in real time, thus outperforming by far the solutions provided by the heuristic approach. The underlying biased randomization techniques [51] introduces some degree of randomness using a skewed probability distribution and reaching a solution nearer to the optimal without the need of knowing all the SMDs' positions.

As it will be illustrated in the numerical results, the use of the biased-randomized approach allows to easily enhance the quality of the solutions generated by the original heuristic in different dimensions when considering social or collective performance. It is important to notice that if a uniform probability distribution would be used instead of a skewed one, this improvement would very rarely occur since the logic behind the constructive heuristic would be destroyed and, accordingly, the process would be random but not correctly oriented.

In the context of combinatorial optimization problems, constructive heuristics use an iterative process in order to construct a `good' and feasible solution. Examples of these heuristics are the savings procedure for the Vehicle Routing Problem [53], the NEH procedure for the Flow-Shop Problem [54], or the Path Scanning procedure for the Arc Routing Problem [55]. In all these heuristics, a `priority' list of potential movements is traversed during the iterative process. At each iteration, the next constructive movement is selected from this list, which is sorted according to some criteria. The criteria employed to sort the list depends upon the specific optimization problem being considered. Therefore, a constructive heuristic is nothing more than an iterative greedy procedure, which constructs a feasible `good' solution to the problem at hand by selecting, at each iteration, the `best' option from a list, sorted according to some logical criterion. Notice that this is a deterministic process, since once the criterion has been defined, it provides a unique order for the list of potential movements. Of course, if we randomize the order in which the elements of the list are selected, then a different output is likely to occur each time the entire procedure is executed. However, a uniform randomization of that list will basically destroy the logic behind the greedy behaviour of the heuristic and, therefore, the output of the randomized algorithm is unlikely to provide a good solution.

Problem Description

The environment consists of a urban area with a pervasive wireless coverage, where several mobile devices are interacting with a centralized cloud infrastructure and request for services from a remote data center. In order to connect the SMDs to the cloud, the presence of different types of RATs that compose the basic elements of the HetNet has been considered. The SMDs can connect to the cloud, as shown in Figure 5.1, by using the reachable RATs. The selection will depend upon the distance to the RATs as well as on other features that will be detailed below.

Fig 5.1 - The reference scenario with different node types in HetNet used by SMDs for offloading applications to UMCC.

The existence of different RATs allows cloud computing systems to complement the resource-constrained mobile devices. In effect, storage and computing tasks can be completed in the cloud, where the appropriate technology is selected among a variety of options. Different strategies can be carried out in order to enhance the network capacity, such as: deployment of relays, distributed antennas, and small cellular base stations (e.g. macrocells, picocells, femtocells), etc. These deployments have occurred indoors, in residential homes and offices, as well as outdoors, in amusement parks and busy intersections.

These new network deployments are typically comprised by a mix of low-power nodes underlying the conventional homogeneous macrocell network. By deploying additional small cells within the local-area range and bringing the network closer to users, they can significantly boost the overall network capacity through a better spatial resource reuse. Inspired by the attractive features and the potential advantages of HetNets, their development have gained much momentum in the wireless industry and research communities during the past few years.

The goal of the system and of every SMDs, indeed, is to choose and exploit effectively the different available RATs for transmitting the application data and for offloading towards the cloud. However, if this operation is not convenient, the application can be computed locally by the requesting SMDs. The analized approaches to solve a collective CA problem are based on a cost function related to the number and the localization of the SMDs. The first approach is the optimization of the cost function, considering a relation among the different measures involved, but it can only be used once the position and requests of all the SMDs is known {i.e., it cannot be used for online allocation of resources. Thus, this approach assumes that all users' requests are processed at the same time (or, alternatively, that the allocation decision is postponed until all requests have been received, which, in practice, might require customers to wait for their requests to be served.

The second approach adopts a heuristic method that makes use of a `greedy' behavior consisting on the selection of the `best next step' from a list of potential constructive movements [47], allowing to find a good solution on the fly, so that every SMD can connect to the proper cell without waiting for all the other SMDs taking place in the environment.

The third, finally, is a novel algorithm that makes use of biased-randomization techniques [48] to improve the results obtained with the second.

In the base heuristic described for the second algorithm, each agent tries to make the choice that maximizes his/her individual utility function. However, this might lead to sub-optimal solutions from a collective or social point of view, since individual decisions do not take into account a global perspective.

In this context, the main idea behind our third approach is to introduce a slight modification in the greedy constructive behavior. This is done such in a way that the constructive process is still based on the heuristic logic but, at the same time, some degree of randomness is introduced. This random effect is generated throughout the use of a skewed probability distribution: at each step of the constructive process, each potential movement receives a probability of being selected, being this probability higher as more `promising' the movement is.

In the following of this section the various components of the UMCC described in chapter 1 are recalled emphasizing the dependency from the parameters that play a role in the used algorithms.

Centralized Cloud

The cloud entity Ccc is characterized by its own computation speed, fcc. The storage availability of Ccc can be considered infinite, and thus it does not represent a constraint in the interaction with the SMDs. Hence, for the centralized cloud it is possible to write:

HetNet nodes

The wireless HetNet infrastructure is composed of some RAT nodes, each of them characterized by different features:

• Channel Capacity $BW$: the nominal bandwidth of a certain communication technology that is available for the requesting connecting devices;
• $n$: the number of devices connected to the RAT;
• $posRAT(x; y)$: the position in which the RAT is located.

Hence, for the a generic RAT it is possible to write:

Applications

Even if every SMD of the system can simultaneously request the computation offoading of one or more applications, we focus on a scenario where each SMD demand is restricted to a single application, which is characterized by the number of operations to be executed, $O$, and the amount of data to be exchanged, $D$. This simplification does not prevent the generalization of the system, since the general case in which a user requests several applications at a given time can be seen as an aggregation of several single-application requests. Hence, it is possible to express a generic application $App$ as:

SMDs

Each SMD is characterized by the following features which infuence the performance of the computation offloading:

• $P_\textit{tr}$: the power consumed by the SMD to transmit data to the node
• $P_l$: the power consumed by the SMD for local computation
• $P_\textit{id}$: the power consumed by the SMD in waiting mode while the computation in performed in the cloud
• $f_\textit{md}$: the speed to perform the computation locally
• $\textit{SNR}$: the SNR of the device
• $pos_\textit{md}(x,y)$: the position in which the SMD is located.

Hence, for a generic smart mobile device SMD:

Given these entities, with the respective features, and defining $d_\textit{i,j}$ as the distance between the $i$-th RAT to the $j$-th SMD, we can resort the Shannon formula for the throughput $S_\textit{i,j}$ delivered by the $i$-th RAT to the $j$-th SMD, where $k$ is an attenuation coefficient for the signal propagation:

In case of computation offloading, Equation \eqref{eq:throughput-5} affects both the measures we are considering for evaluating the QoS:

• the energy consumed by the $j$-th SMD, i.e.: the sum of the energy spent in transmitting the application data plus the energy consumed while the application is computed on the cloud server;
• the time required to accomplish the application, i.e.: the sum of the time spent in transmitting the application data plus the time for computation on the cloud server.

Considering an overall number of $N$ devices and a total number of $M$ HetNet nodes, the energy and the time spent by the $j$-th SMD for offloading towards the $i$-th RAT are, respectively:

On the other hand, in case of local computation executed by the $j$-th SMD, the energy and the time consumed by the SMD are, respectively:

where the 0 index represents a fictitious node related to this operation.

The SMD requesting to compute an application $App$ evaluates if the computation offloading is convenient and which is the RAT to be used. The decision aims at minimizing the energy consumption of the user requesting the service as well as the execution time required to accomplish the application. Therefore, the decision is `selfish' in the sense that it does not take into account the current and future needs of other users.

We consider, instead, to optimize the global energy consumption, assuming an environment where the devices of the set ${\cal{N}} = \{ 1, 2, \cdots, j, \cdots, \textit{N} \}$ are requesting to offload an application using the nodes of the set ${\cal{M}} = \{ 0, 1, 2, \cdots, i, \cdots, \textit{M} \}$, where the 0-th element represents the fictitious node related to the local computation.

Defining $x_{i,j}$ as a binary variable that indicates whether SMD$_j$ is assigned to RAT$_i$ or not, and $y_j$ as another binary variable to account for SMD$_j$ computing locally its application, it is possible to write the energy consumed by SMD$_j$ when offloading towards RAT$_i$ (Equation \eqref{eq:energyOD-5}) by exploiting Equation \eqref{eq:throughput-5}

where $n_i$ is the number of SMDs connected to RAT$_i$, i.e. $n_i = \sum_{l \in \cal{N}} x_{i,l}$.

Rearranging the constant terms and the variable terms it is possible to write:

The constant part for offloading due to the transmission is computed as $K^\textit{tr}_{i,j} = \frac{P_\textit{tr j}\,D}{\textit{BW}_ilog_2\left\{1+\textit{SNR}_j e^{-k d_\textit{i,j}} \right\}}$ plus the constant part $ K^{id}_j = \frac{P_{id\,j}\,O }{f_{cc}}$. Therefore the optimization model can be expressed as:

The objective function (\eqref{eq:mod_minEnergy-5}) minimizes the overall energy spent, while ensuring that all devices are either assigned to a RAT or leaving the computations to be done locally.

5.3 Optimal and Heuristic Solutions

In this section different methods to solve the optimization model are presented. A first approach is to use an off-the-shelf commercial solver, but for real large-size instances it requires unsuitable computation times. Moreover, since we take into account mobile SMDs, thus their position changes in time, the cell association has to be computed often. Therefore, given that the assignation of the SMDs to the RAT nodes has to be done in a very short time, we analyze several heuristic procedures. We focus on a novel \autoref{algo:BRAalgo} based on biased randomization strategy, that is proposed to improve the quality of the solution from a social or collective point of view, enhancing a previously proposed greedy \autoref{algo:ACalgo}. To evaluate their effectiveness we use the optimal solution presented in \autoref{sub:model}, that can only be applied \emph{ex-post}, once all the SMD requests have been revealed. This optimal solution is found using the procedure of \autoref{algo:Baronalgo}. In particular, since the global optimization needs to know the position and the requests of all the SMDs, it cannot be used for online allocation of resources. Thus, this approach assumes that all users' requests are processed at the same time --or, alternatively, that the allocation decision is postponed until all requests have been received--, which in practice might require customers to wait for their requests to be served.

On the other hand, the heuristic method making use of a `greedy' behavior, consisting on the selection of the `best next step' from a list of potential constructive movements \cite{Globecom2014}, allows to find a good solution in real time, so that every SMD can connect to the proper cell without waiting for all the other SMDs taking place in the environment. But with this heuristic, each agent tries to make the choice that maximizes his/her individual utility function, so that this might lead to sub-optimal solutions from a collective or social point of view, since individual decisions do not take into account a global perspective.

Optimal Solution

The previous objective function shown in \autoref{mod:assignmentModel-5} can be seen as an application of the QSAP which is NP-hard \cite{burkard-2013}. A first approach to find the solution is to use the global optimizer Baron \cite{Baron}. The Branch-And-Reduce Optimization Navigator derives its name from its combining constraint propagation, interval analysis, and duality in its reduce arsenal with advanced branch-and-bound optimization concepts.

Note that the QSAP not only needs to know the position of all SMDs requests before assigning them to an antenna, but also it takes a time longer than the needed to serve quickly the SMDs, as shown in \autoref{sec:numerical-results-5}. Therefore, the optimal resolver can be taken only as reference, to compare fast heuristics (which can do the assignation dynamically or with a \emph{wait-and-go}) with an optimal, ideal solution.

The Greedy Heuristic

In this sub-section, we recall a heuristic algorithm used to solve the CA problem following a greedy behavior. It has been used also in \autoref{chap:GLOBECOM14}, to resolve the CA problem in the case discussed above, considering a user-satisfaction based utility function. If the offloading operation is advantageous with respect to the local computation, the CA scheme leads to select the `best' next node from the list of the available ones. The requests of the SMDs appear in time sequence, and the cost function is evaluated on the basis of the current situation, i.e., considering only the previously appeared SMDs. If the offloading cost is less than the cost for the local computation, the SMD will connect to the node which minimizes the cost function, otherwise it will compute the application without connecting. The selection of the $i$-th node for connecting the $j$-th SMD modifies the values of the throughput $S_\textit{i,k}$ and consequently of the energy $E_\textit{i,k}$ for the SMDs already connected with the same node, i.e., for $k=1,2,\dots,j-1$. Thus, this strategy, reported in \autoref{algo:ACalgo}, does not take into account any forecast of future connections, leading to a sub-optimization due to the randomness of the requests.

Biased-randomized Algorithm

Making use of biased-randomization techniques \cite{Juan2011}, the proposed probabilistic algorithm is able to find near-optimal solutions in real time, thus outperforming by far the solutions provided by the heuristic approach. The main idea behind our novel approach is to introduce a slight modification in the greedy constructive behavior. This is done in such a way that the constructive process is still based on the heuristic logic but, at the same time, a certain degree of randomness is introduced. This random effect is generated throughout the use of a skewed probability distribution: at each step of the constructive process, each potential movement receives a probability of being selected, being this probability higher for the more \emph{promising} movements.

As it will be illustrated in the numerical results, the use of the biased-randomized approach allows to easily enhance the quality of the solutions generated by the original heuristic in different dimensions when considering social or collective performance, reaching a solution nearer to the optimal, without the need to know all the SMDs' positions.

Also, it is important to notice that if a uniform probability distribution would be used instead of a skewed one, this improvement would very rarely occur since the logic behind the constructive heuristic would be destroyed and, accordingly, the process would be random but not correctly oriented.

To avoid losing the logic behind the heuristic, GRASP meta-heuristics \cite{Feo1995} proposes to consider a restricted list of candidates --i.e., a sub-list including just some of the most promising movements, that is, the ones at the top of the list--, and then apply a uniform randomization in the order the elements of that restricted list are selected. This way, a deterministic procedure is transformed into a randomized algorithm --which can be encapsulated into a multi-start process--, while most of the logic or common sense behind the original heuristic is still respected.

The proposed biased-randomization approach goes one step further, and instead of restricting the list of candidates, it assigns different probabilities of being selected to each potential movement in the sorted list. In this way, the elements at the top of the list receive more probabilities of being selected than those at the bottom of the list, but potentially all elements could be selected. Notice that by doing so, we are not only avoiding the issue of selecting the proper size of the restricted list, but we also guarantee that the probabilities of being selected are always proportional to the position of each element in the list. As a result, each time the randomized algorithm is executed, a new probabilistic solution is obtained (\autoref{fig:Scheme}). Some of these solutions will improve the original one provided by the base heuristic and, moreover, the proposed approach allows to offer alternative solutions to choose from, each of them with different properties.

Focusing on our specific problem, the biased-randomization algorithm for the cell association consists of a skewed criteria based on the same cost function utilized for the greedy heuristic, i.e., the SMD's energy consumption for computing the application. When a SMD request occurs, the cost function $E_\textit{i,j}$ is evaluated for every possible RAT node (considering also the fictitious node $0$ related to the local computation).

The values are sorted in a way so that the probabilities of being selected depend not only on the cost function $E_\textit{i,j}$, but also on the distances $d_\textit{i,j}$ of the device from the RAT nodes and on the number of devices $n_i$ that potentially can be connected to each RAT node.

In fact, on the basis of the greedy algorithm, a SMD far from all the RAT nodes, but occurred before any other, is associated to a RAT because the cost function value of the offloading is less than the cost function for the local computation. Instead, due to the high probability that another SMD closer to this RAT occurs, the local computation could be a better choice, giving place to the connection of the second closer SMD. To improve the cell association, the criteria for sorting the list of choices takes into account the product $d_\textit{i,j} \cdot E_\textit{i,j}$, with $i \in \{{0\}} \cup \mathcal{M}$, instead of $E_\textit{i,j}$. The value of $d_\textit{0,j}$ is adjusted empirically and depends on the overall number of SMDs which are expected to interact in the system. We selected a value $d_\textit{0,j}$ depending on the overall number of SMDs which are supposed to interact in the system. The value of $d_\textit{0,j}$ has been evaluated observing the optimal solution given by \ref{sub:model} in the post-analysis, i.e., when all the SMD positions are already known.

This strategy is reported in Algorithm \autoref{algo:BRAalgo}.

5.4 Numerical Results

We considered a deployment area similar to that of the previous chapters, i.e. an extension of $1000 m^2$, where one LTE eNodeB with channel capacity equal to 100 MHz is positioned at point (500, 500) and three WiFi access points with channel capacities equal to 22 MHz are positioned at point (0, 0), (500, 999) and (1000, 0). Each of them is supposed to cover the entire area and we considered an attenuation coefficient for the propagation $k$ equal to $10^{-3}$. Furthermore, similarly to \cite{Globecom2014}, the capacity constraints on the antennas is not considered, assuming there is no limitation on the number of customers.

The SMDs are placed in the deployment area according to a uniform distribution. In particular, we have chosen a controlled random number generation of type Mersenne Twister with seed equal to 1. The values of $f_{\textit{md}}$, $P_{\textit{id}}$, $P_{\textit{tr}}$, $P_l$, and $\textit{SNR}$ are specific parameters of the mobile devices. We considered the values of an HP iPAQ PDA with a 400 MHz Intel XScale processor ($f_{\textit{md}}=400$ MHz) and the following values: $P_l = 0.9 W$, $P_{\textit{id}} = 0.3 W$, $P_{\textit{tr}} = 1.3 W$, and $\textit{SNR} = 1000$. Regarding the cloud server, we suppose a computation speed $f_{cs} = 10^6$ MHz~\cite{Kumar}. We have chosen an application which is accomplished through a number of operation $O = 10^7$ and, if offloaded, needs a data transfer $D = 10^4$ bits.

We have compared the cell association configurations resulting from the greedy heuristic, the biased-randomization algorithm, and the Baron solution. The no-connections configuration (all the SMDs compute local) and the nearest-node configuration (each SMD connected to the closest RAT) are also taken into account for comparison. The throughput, the energy consumed by the SMDs and the time employed for accomplishing the application are evaluated and observed for each configuration, considering an increasing number of SMDs involved in the system, in particular 500, 1000, 2000, and 5000.

\autoref{tab:result_throughput}, \autoref{tab:result_energy}, and \autoref{tab:result_time} show, respectively, the results related to the throughput, the energy, and the time. The ex-post solution has been computed with Baron under the Neos server http://www.neos-server.org). The QSAP model is implemented with the mathematical modeling language GAMS. The other methods have been implemented in Matlab.

5.5 Analisys of Results

The results of \autoref{tab:result_throughput}, \autoref{tab:result_energy}, and \autoref{tab:result_time} show that the biased-randomized algorithm clearly improves the cell association configuration with respect to the greedy heuristic. These improvements are: 2.24\% in throughput, 14.30\% in energy consumption, and 0.42\% in computation time.

Also, the average energy and time values provided by the randomized algorithm, which only requires some milliseconds to compute, are quite similar to the solutions provided by Baron, which is stopped after 1,000 seconds of computation. The results are visually compared in \autoref{fig:throughputComparison} and in~\autoref{fig:throughput-5}, where we can see that the trends of average throughput are very similar, practically overlapped, in the three cases of interest, i.e. the greedy heuristic, the biased randomized algorithm, and the Baron ex-post configuration. This means that the capacity of the RAT nodes is well-exploited in all the three cases considered. In \autoref{fig:throughputComparison} the average throughput values are visualized in a different scale to make possible the comparison of the three algorithms.

Considering the average energy consumed by a SMD to perform the application, which is the objective function to minimize, Figure \autoref{fig:energy-5} shows that the biased-randomized algorithm clearly outperforms the greedy heuristic. The same observation can be inferred from Figure\autoref{fig:time-5} in relation to the average time that a device needs to accomplish the application. Both the average energy and the time values are very close to the respective Baron configuration average energy and time values, thus the biased randomized algorithm can be exploited by the SMDs to reach a near-optimal configuration in real time while the solution seen from a collective point of view minimizes the overall energy consumption. This is useful for offloading applications which need a fast cell association decision, for example when the users are in movement and the configuration must be updated very often.

Comparing the different configurations of the devices placed in the observed area, reported in \autoref{fig:scatter500}, \autoref{fig:scatter1000}, \autoref{fig:scatter2000} and \autoref{fig:scatter5000} for a total number of SMD equal to 500, 1000, 2000 and 5000 respectively, we can note that the case referring to the biased-randomized algorithm is very similar to the ex-post optimal solution, where the SMDs connected to the same RAT are clustered in the neighborhood of the RAT.

5.6 Conclusion

In this chapter we presented different strategies for efficient cell association in pervasive wireless environments. In particular, we proposed an original probabilistic algorithm that allows to consider a more global point of view --instead of just an individual one-- during the real-time resource allocation. Thus, the mobile communication system is managed in a cooperative way, considering the QoS of the entire population of mobile users. This vision could be adopted for the provision of services in a smart city, improving performance and well-being of the community through a social use of the UMCC framework. Our approach is based on the use of biased-randomization techniques, which have been used in the past to solve similar combinatorial optimization problems in the fields of logistics, transportation, and production. This work extends their use to the field of smart cities and mobile telecommunications. Some numerical experiments contribute to illustrate the potential of the proposed approach.

6.1 Final Conclusions

The actual realization of the vision of smart cities is an exciting perspective with the potential of bringing tremendous improvements to our society, thanks to novel pervasive services assisting us in every aspect of our lives.

While the increasingly deep integration of ICT services in the physical world has been the main enabling factor motivating this vision, we believe that the intelligent and efficient exploitation of the infrastructures will be the key to its success.

Our contribution has proposed an original solution approach for dealing with common resources that need an optimization for the distribution among users.

We hope that our work was successful in proposing general and simple solution principles that can be used fruitfully as starting points for new research efforts toward the realization of future large scale smart pervasive environments. Finally, let us note that, while the scope of our research was focused on the specific application scenario of smart city environments, we believe that most of the presented results can be easily and successfully used in other scenarios with similar requirements of efficient and scalable distribution, such as the management of large scale telecommunication infrastructures or smart grids deployments.

6.2 Directions for Future Works

Cities around the globe are beginning to build out new digital services such as smart lighting, traffic, waste management and data analytics to reduce costs, tap new sources of revenue, create new innovation business districts and improve the overall quality of urban life. Integrated IoT and MCC applications enabling the creation of smart environments such as smart cities need to be able to combine services offered by multiple stakeholders and scale to support a large number of users in a reliable and decentralized manner. They deal with constraints such as access devices or data sources with limited power and unreliable connectivity. The UMCC needs to be enhanced to support a seamless execution of applications harnessing capabilities of multiple dynamic and heterogeneous resources to meet quality of service requirements of diverse users.

The management of distributes mobile platform resources need further investigation. This thesis is a starting point for a user-centric model that requires additional heterogeneity: i.e. customized needs and different QoS levels. For example, some users could not have problem of battery charge whereas others could need to save energy (i.e. SMD having a low-battery-level status). Thus, the clusterization debated in chapter 4 needs to be deeply investigated.

A further point of invetigation is the study of SMDs in motion, for analyzing the time evolution of the system: in chapter 5 the approach on the fly assigns a RAT node to a SMD every time a request occurs, but, since it depends on the position of the devices, the CA needs a time optimization subordinate to the speed of the devices.

In addition, considering an operational research perspective, the CA assignation in the UMCC can be seen as a stochastic allocation of resources, in particular an assignation of the SMDs to the available RATs, as shown in Fig. 6-1.

Fig 6.1 - Allocation of mobile devices with random positions to RATs.

In fact, being mobile, the position of the devices change over time, and it is possible to assume that the position of each device in a future target time can be characterized by two random variables, describing the x and y location, respectively as shown in Fig. 6-2..

Fig 6.2 - Random position of the devices in a target time.

It will also be assumed that the expected value of each random variable will be given by the current position of the respective device. Assuming that the expected value of each random variable will be given by the current position of the respective device, it is possible to model this scenario as a FLP with stochastic assignment costs - i.e. a combination of different factors, such as time-based costs and energy-based costs, random variables proportional to the Euclidean distance between the device and the RAT node. It is worth to note that the RATs’ capacity could be considered either as virtually unlimited or not, thus leading to two different problems: the Uncapacitated FLP and the Capacitated FLP, respectively. One way to deal with these stochastic FLP would be to use a simheuristic approach [59] i.e., a combination between a fast metaheuristic - able to quickly generate several good or promising solutions for the deterministic version of the FLP - and a fast simulation process able to estimate the expected cost associated to a given deterministic solution when it is used for the stochastic scenario. The main goal of this future work will be to minimize the expected costs of the assignment process. The simulation, however, could also provide insights on the ‘robustness’ of each promising solution, enriching a risk analysis investigation.

List of Tables

ddd