Prof Abdelhakim Hafid

Keywords: Mobile computing, Cloud computing, Game theory, Markov process iii Informatique mobile, Informatique dans les nuages, Théorie des jeux, Processus de Markov mobile computing -cloud computinggame theory -Markov process

Global mobile traffic is increasing dramatically due to the popularity of smart mobile devices and data hungry mobile applications. Mobile data offloading is considered as a promising solution to alleviate congestion in cellular network. Mobile computation offloading can move the computation intensive tasks and large data storage from mobile devices to cloud. In this thesis, we first study mobile data offloading problem under the architecture of mobile cloud computing. In order to minimize the overall cost for data delivery, we formulate the data offloading process as a finite horizon Markov decision process. We further propose two data offloading algorithms to achieve minimal communication cost. Then, we consider a mobile data offloading market where mobile network operator can sell bandwidth to mobile users. We formulate this problem as a multi-item auction in order to maximize the profit of mobile network operator. We propose one robust optimization algorithm and two iterative algorithms to solve this problem. Finally, we investigate computation offloading problem in mobile edge computing. We focus on workload balancing problems to minimize the transmission latency and computation latency of computation offloading. We formulate this problem as a population game in order to analyze the aggregate offloading decisions. We further propose two workload balancing algorithms based on evolutionary dynamics and revision protocols. Simulation results show the efficiency and robustness of our proposed methods.

Les points d'accès WiFi sont gérés par un seul MNO qui fournit un accès réseau à ses abonnés mobiles (par exemple, MS1). La capacité de réseau des points d'accès WiFi (par exemple, AP1) est allouée aux MS pour le déchargement du trafic de données. Dans ce scénario, MS1, MS2 et MS3 font une offre pour la bande passante (c'est-à-dire, AP1, AP2 et AP3) avec des évaluations différentes. Compte tenu de la zone de couverture de chaque point d'accès, MS2 peut enchérir sur trois points d'accès, tandis que MS1 et MS3 peuvent enchérir sur deux points d'accès. MNO qui est le commissaire-priseur alloue la bande passante de différents points d'accès aux états membres. Les états membres gagnants peuvent utiliser la bande passante déterminée par MNO. 7.9 Organigramme de l'algorithme optimal proposé. La colonne de gauche indique la phase d'allocation nominale, tandis que la colonne de

List of Acronyms

Introduction

We begin this chapter by introducing the concept of mobile data offloading, mobile computation offloading, mobile cloud computing and mobile edge computing in Section 1.1. We then present the motivations and contributions in Section 1.2 and Section 1.3, respectively. We finally introduce the thesis organization in Section 1.4.

Research Background

In this section, we present the research background of two mobile techniques (i.e., mobile data offloading and mobile computation offloading), and two computing paradigms (i.e., mobile cloud computing and mobile edge computing). Two types of data offloading techniques: WiFi offloading and device-to-device (D2D) offloading are introduced in Section 1.1.1. Depending on the destination of computation offloading, e.g., remote cloud center or local edge cloud, two different computation offloading techniques are summarized in Section 1.1.2. These two destinations of computation offloading lead to two emerging computing paradigms, namely, mobile cloud computing and mobile edge computing, introduced in Section 1.1.3 and Section 1.1.4, respectively.

Mobile Data Offloading

Data traffic in cellular network has seen an exponential rise, due to the explosion of mobile devices and mobile applications. The rapid growth of mobile data traffic raises big challenges to cellular network. Global mobile data traffic grew 63 percent and reached 7.2 exabytes per month in 2016, which is 18-fold over the past 5 years [1]. The huge amount of mobile data traffic exceeds the capacity of cellular network and reduces the network quality [2]. To address such challenges, one simple solution is to increase the capacity of cellular network, which is inefficient and expensive due to the corresponding expensive investments in radio access networks and the core infrastructure. One promising solution, namely mobile data offloading (MDO), is to offload cellular traffic to other kinds of networks, e.g. WiFi access points and D2D communication; this can solve the cellular traffic overload problem.

Mobile data offloading refers to the use of complementary network technologies and innovative techniques for delivery of data originally targeted for cellular networks in order to alleviate congestion and make better use of available network resources. The objective is to maintain QoS for customers, while also to reduce the cost and impact of carrying capacityhungry services on the wireless network [3]. It is expected that mobile data offloading will Chapter 1. Introduction become a key industry segment in the near future as the data traffic on mobile networks continues to increase rapidly [1].

Cloud

Cellular BS MS

WiFi AP

Cellular connection WiFi connection MS moving trace

According to the complementary network, there are two types of data offloading, WiFi offloading and D2D offloading, as shown in Figs. 1.1 and 1.2, respectively. WiFi offloading uses WiFi hot spots to transfer data originally targeted to cellular network, while D2D offloading uses nearby mobile helper (MH) to transfer data to mobile subscriber (MS).

WiFi offloading

WiFi offloading is considered as a promising solution to reduce mobile data traffic in cellular network. WiFi Access Points (APs) can efficiently reduce cellular traffic. It is shown that about 65% of cellular traffic can be offloaded through WiFi APs [4]. Although WiFi APs can provide better data rate than cellular network, their coverage area is much smaller than cellular network [START_REF] Iosifidis | A double-auction mechanism for mobile data-offloading markets[END_REF].

D2D offloading

Another data offloading method, called D2D offloading (opportunistic offloading), is based on D2D communication [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF]. D2D offloading uses the store-carry-forward strategy, where some mobile users can store data in the buffer (called MHs), carry the data when they are moving, and forward the data to other mobile users (called MSs) [START_REF] Cheng | Offloading multiple mobile data contents through opportunistic device-to-device communications[END_REF]. When mobile network operator (MNO) wants to deliver data to MSs, it can first send the data to MHs. Then, MHs will transmit data to MSs using opportunistic connections. With more than half a billion mobile devices and connections added in 2015 [1], D2D communication is becoming an important data delivery scheme. However, the data rate of D2D communication is low and the mobility patterns of MHs or MSs are difficult to predict. The comparison of WiFi offloading and D2D offloading is shown in Table 1.1.

Cloud

Cellular BS MS MH A MH B

D2D connection Cellular connection WiFi connection MS moving trace

Mobile Computation Offloading

Mobile devices are widely used as the most convenient communication tools in daily life.

Mobile users can acquire large amounts of various services from mobile applications running on the local devices and/or on remote servers via wireless networks. However, mobile devices are facing many challenges in their resources (e.g., battery life, storage, and Chapter 1. Introduction bandwidth) and communications (e.g., mobility, availability and heterogeneity). These challenges will reduce the QoS that can be provided to mobile users. One feasible solution, mobile computation offloading (MCO), is to offload part of the computation tasks from mobile devices to remote cloud servers or local edge servers. MCO can improve the performance of mobile devices by taking advantage of computation offloading. Moreover, MCO can reduce energy consumption in mobile devices and/or implement sophisticated applications by offloading computation intensive tasks to cloud or edge servers with higher computation and storage capabilities. We first introduce the computation offloading decision problem and then discuss the computation offloading process.

There are mainly three kinds of computation offloading decisions.

• Non-offloading: mobile computation is executed fully in mobile devices;

• Full offloading: the whole computation is offloaded from mobile devices to cloud servers or edge servers;

• Partial offloading: only a part of computation is executed in mobile devices while the rest if executed in servers.

The objective of MCO is to minimize the processing delay of mobile application, to minimize the energy consumption of mobile devices while satisfying delay constraints or to trade off between processing delay and energy consumption. According to different offloading destinations, there are two types of computing paradigms, namely, mobile cloud computing introduced in Section 1.1.3 and mobile edge computing introduced in Section 1.1.4.

Mobile Cloud Computing

Mobile devices are capable of supporting large numbers of mobile applications, some of which demand an ever increasing computational power. This poses a challenge because mobile devices are resource constrained devices with limited computation power, memory, storage, and energy. Fortunately, the cloud computing technology offers virtually unlimited dynamic resources for computation, storage, and service provision. Therefore, researchers envision extending cloud computing services to mobile devices to overcome the mobile devices constraints. The challenge in doing so is that the traditional mobile application models do not support the development of applications that can incorporate cloud computing features and requires specialized mobile cloud application models. In order to solve this problem, mobile cloud computing (MCC) is proposed and defined as follows [START_REF] Hoang T Dinh | A survey of mobile cloud computing: architecture, applications, and approaches[END_REF].

Mobile cloud computing at its simplest, refers to an infrastructure where both the data storage and data processing happen outside of the mobile device. Mobile cloud applications move the computing power and data storage away from mobile phones and into cloud, bringing applications and mobile computing to not just mobile users but a much broader range of mobile subscribers.

MCC is an extension of cloud computing (CC). It integrates CC into the mobile environment. CC is widely recognized as the next generation computing infrastructure. Cloud providers provide computing, storage, services and applications as services to cloud users. CC enables users to utilize cloud resources in on-demand and pay-as-you-go method. Moreover, it helps reducing capital cost, decouples services from the underlying technology, and provides flexibility in terms of resource provisioning. MCC can take advantage of the benefits of CC to improve the QoS of mobile services. With the explosive growth of mobile applications, MCC has been proposed as a potential technology for mobile services. MCC integrates CC into mobile devices to overcomes obstacles related to the performance (e.g., battery life, storage, and bandwidth), environment (e.g., heterogeneity, scalability, and availability), and security (e.g., reliability and privacy).

Advantages of MCC

MCC is an extension of cloud computing. It can overcome several obstacles in mobile computing. The following are the advantages of introducing cloud computing into mobile environment.

• MCC can extend battery lifetime of mobile devices. In [START_REF] Kumar | Cloud computing for mobile users: Can offloading computation save energy?[END_REF], the authors show that cloud computing can save energy for mobile systems. Since the battery for mobile devices is limited, offloading computation intensive tasks to cloud computing can save computation time and energy for mobile devices.

• MCC can store and process data in cloud side. It can extend the storage capacity for mobile devices. MCC is developed to enable mobile users to store/access large amounts of data on cloud through wireless networks.

• MCC can reduce the running cost for compute-intensive applications that consume large amount of computing resources. It can help run applications that cannot be executed on the limited-resources devices.

• MCC can improve reliability. Storing and processing data on cloud side is an effective way to improve the reliability thanks to the back-up technology that is used in cloud servers. This reduces the chance of data data loss/damage on mobile devices.

Challenges of MCC

Although it has many advantages for cloud providers and mobile users, MCC has to face many issues in computation side and mobile communication side. For computation side, the optimal program partition for offloading is difficult to find. Also, it is difficult to obtain the accurate execution time of computations because the time varies in different instances of the computations, and the inaccurate information results in inefficient offloading performance. For communication side, bandwidth is the most important issue for MCC because the radio resource in wireless networks is scarce. This issue is even worse with the increase of the number of smart mobile devices and data heavy mobile applications, such as video streaming and cloud backup.

Many researchers proposed optimal and efficient solutions for bandwidth allocation. New technologies (e.g. 5G network) are being developed to increase significantly bandwidth for wireless communication. However, bandwidth limitation is still a big concern because the number of mobile devices is dramatically increasing.

• Low bandwidth. Bandwidth is one of the big issues in MCC because the radio resource for wireless networks is much scarce as compared with the traditional wired networks. • Availability. Service availability becomes a more important issue in MCC than that in the CC with wired networks. Mobile users may not be able to connect to cloud to obtain a service due to traffic congestion, network failures, and the out-of-signal.

• Heterogeneity. Mobile cloud computing will be used in the highly heterogeneous networks in terms of wireless network interfaces. Different mobile nodes access to cloud through different wireless networks, such as cellular, WiFi networks. As a result, an issue of how to handle the wireless connectivity while satisfying MCC's requirements arises (e.g., always-on connectivity, on-demand scalability of wireless connectivity, and the energy efficiency of mobile devices).

• Enhancing the efficiency of data access. Handling the data resources on cloud is not an easy problem because of the low bandwidth, mobility, and the limitation of resource capacity of mobile devices.

Mobile users need to access to servers located in cloud when requesting services and resources in cloud. However, mobile users may face some problems such as congestion due to the limitation of wireless bandwidth, network disconnection, and the signal attenuation caused by mobile users' mobility. This may cause delays when users want to communicate withwith cloud degrading significantly QoS. To reduce network delay, mobile edge computing has been proposed.

Mobile Edge Computing

MCC introduces significant processing delay of computation offloading, consisting of uploading computation-related data (e.g., programming codes and input data) to cloud center, getting back the computation result and code execution in cloud center. Especially, the delay incurred by long distance between mobile users and cloud center makes computation offloading unsuitable for many real-time applications. Moreover, the transmitted task data may not reach cloud servers, or the data executed on the servers will be lost when it has to be returned to mobile devices. Instead of offloading tasks to remote cloud directly, mobile devices can offload tasks to nearby edge servers.

To cope with the delay problem introduced by MCC, another computing paradigm, mobile edge computing (MEC) is proposed. The main idea of MEC is to bring computation and storage resources to the edge of mobile network while meeting strict delay constants with short data transmission distance [START_REF] Mach | Mobile edge computing: A survey on architecture and computation offloading[END_REF]. Bringing computation close to mobile users is the key concept of MEC. Fig. 1.3 illustrates MEC in software defined network. Edge cloud can enhance small cells, e.g., microcells, picocells or femtocells, with augmented computation capability and storage capability. Since a large number of small cells will be deployed in the future, MEC is considered to be a promising destination of mobile computation offloading, especially for mobile tasks or applications having stringent constraints on latency. The control BS is used to implement dynamic and elastic resource management of small cells and have the knowledge of information about mobile users (e.g., user location and mobile tasks), information about edge clouds (e.g., computation resources and storage resources) and information about small cell BSs (e.g., network condition and signal interference). Based on the information, control BS is in charge of the computation offloading process to optimize the system performance (e.g., energy consumption minimization or delay minimization). A comparison between MEC and MCC is shown in Table 1.2. Except for edge cloud, another similar concept, the so-called cloudlet has been proposed. A cloudlet is a trusted, resource-rich computer or cluster of computers which is well-connected to the Internet and available for use by nearby mobile devices [START_REF] Hoang T Dinh | A survey of mobile cloud computing: architecture, applications, and approaches[END_REF]. Cloudlet is an important complement to the device-cloud hierarchy. It refers to a layer connecting mobile devices and cloud servers in MCC; it plays a mediator role focusing on the business logic [START_REF] Gai | Dynamic energy-aware cloudlet-based mobile cloud computing model for green computing[END_REF]. It is a self-management mechanism that is used to strengthen communications between mobile devices and cloud servers by reducing latency [START_REF] Pang | A Survey of Cloudlet Based Mobile Computing[END_REF].

Chapter 1. Introduction

Motivations

Although mobile data offloading can significantly reduce cellular traffic, the task of developing a comprehensive and reliable mobile data offloading system remains challenging. A key challenge is how to achieve an efficient data offloading coordination among multiple mobile devices. By opportunistic utilization of lower cost access points, mobile subscribers will have better wireless access service with lower cost. In contrast, MNOs who have deployed these access points want to maximize the revenue by selling bandwidth. Thus, how to effectively allocate this bandwidth to mobile devices effectively becomes a key problem to be solved.

Given the limited bandwidth of APs deployed in a mobile data offloading market, when demands of mobile devices exceed supply, MNO needs to allocate the bandwidth to mobile devices and decide the price for allocated bandwidth in order to achieve the highest revenue. Auction mechanism is considered as an economically efficient approach towards the allocation of APs' bandwidth, and assigns bandwidth to mobile users who value it the most [START_REF] Mangili | Bandwidth and cache leasing in wireless information-centric networks: A game-theoretic study[END_REF][START_REF] Yu | Auction-based coopetition between LTE unlicensed and Wi-Fi[END_REF][START_REF] Mohammad | Incentivizing device-to-device load balancing for cellular networks: An online auction design[END_REF][START_REF] Wang | Pricing mobile data offloading: A distributed market framework[END_REF]. In a real-world data offloading market, the bidding prices of mobile users are private information unavailable for MNO. However, MNO may use historical information to identify the numerical characteristics of the bidding prices. Consequently, it is natural to consider how to model the bidding prices based on historical information. Here, uncertainty set is used to model the possibility of bidding prices. MNO assumes that all bidding prices belong to the uncertainty set derived from historical information. Then, MNO makes an offloading mechanism based on the uncertainty set instead of some fixed bidding prices.

The challenges for mobile devices are due to the characteristic of mobility (or wireless). Because of mobility, mobile devices do not have continuous power supply; this is one of the key problems for these devices. At the same time, mobile devices lack stable/continuous network connection due to wireless networks. Although having great improvement in recent years, mobile devices still have limited computing and storage resources.

These restrictions make many energy-consumption applications not suitable running in mobile devices. This is because, for example, these applications usually consume too much power resources and generate lots of heat causing bad user experience. Furthermore, many sophisticated applications are not suitable to execute in mobile devices with restricted computation, memory and storage capacity.

To make MCC a reality, a number of problems need to be solved. These problems include:

(1) intermittent connection caused by mobility and wireless environment, and (2) limited energy supply in mobile devices. Even though there has been a lot improvements in mobile devices (e.g., computing resources, storage ability and battery life) and wireless networks (e.g., LTE), there is still a need to address these problems:

• Limited battery life has been found as the biggest complaint for smartphones [START_REF] Xu | A survey of mobile cloud computing for rich media applications[END_REF]. Two main factors contribute to the energy problem. One is the limited capacity of batteries. The other is the increasing demand for energy-hungry applications (such as video streaming and online gaming).

• Limited bandwidth and large network latency has a great impact on MCC. Also, intermittent network connection may also cause problems for MCC. Indeed, even though

Contributions

the network condition may have a great improvement in the future, with the development of high speed wireless network technologies (such as 5G technology [START_REF] Barbarossa | Communicating while computing: Distributed mobile cloud computing over 5G heterogeneous networks[END_REF]), it is not sufficient to solve the problem.

• Costly network access: Network access cost has a big impact on MCC users, since cellular network service (e.g., 4G LTE) is more expensive than traditional wired Internet access or WiFi service.

• Problems in service integration: Using services in MCC involves both mobile service provider (MSP) and cloud service provider (CSP). However, MSPs and CSPs have different services management, customers management, methods of payment, and prices.

IoT is proposed to equip everyday objects with electronics, software, sensors, and network connectivity, and bring the vision of a connected world into reality [START_REF] Shah-Mansouri | Hierarchical Fog-Cloud Computing for IoT Systems: A Computation Offloading Game[END_REF]. However, computation-intensive applications, such as e-health, automatic driving, and industrial automation, consume large amounts of computing and storage capabilities of IoT devices. These sophisticated applications have stringent requirements of computation resources and processing delay on IoT Devices (IoTDs). However, IoTDs are resource-constrained and have limited computational capacities and battery life. Running computation intensive applications on IoTDs would result in high energy consumption and long processing delay [START_REF] Guo | Computation Offloading for Multi-Access Mobile Edge Computing in Ultra-Dense Networks[END_REF]. The tension between computation intensive applications and resource constrained IoTDs brings a significant challenge for future mobile development. MEC is envisioned to be a promising solution to address this challenge, with the objective to provide cloud computing capabilities to IoTDs through radio access network [START_REF] Guo | Collaborative Mobile Edge Computation Offloading for IoT over Fiber-Wireless Networks[END_REF]. By offloading computation intensive tasks to edge cloud (or MEC server) in proximity, the local energy consumption on IoTDs can be reduced and the local processing delay may be shortened [START_REF] Liu | Population Game Based Energy and Time Aware Task Offloading for Large Amounts of Competing Users[END_REF].

To offload computation intensive tasks to edge cloud, task-related data should be transferred between IoTDs and edge cloud through base station (BS). If BS is congested by large amounts of IoTDs choosing to offload tasks simultaneously, the quality of experience and quality of service of IoTDs will not be guaranteed [START_REF] Liu | Prediction-Based Mobile Data Offloading in Mobile Cloud Computing[END_REF][START_REF] Liu | Decentralized data offloading for mobile cloud computing based on game theory[END_REF]. Moreover, facing the rapid increase of IoTDs and massive offloading tasks, the resource bottleneck of edge cloud becomes significant, since edge cloud has relatively limited resources compared to cloud computing [START_REF] Zhang | Joint Offloading and Resource Allocation Optimization for Mobile Edge Computing[END_REF]. Thus, lack of proper offloading coordination among large amounts of self-interested IoTDs may lead to large communication and computation latencies due to insufficient resources and serve interferences [START_REF] Wang | Computation offloading and resource allocation in wireless cellular networks with mobile edge computing[END_REF][START_REF] Zhang | Mobile Edge Computing and Networking for Green and Low-Latency Internet of Things[END_REF]. As a result, how to design an energy-efficient offloading mechanism while satisfying the processing delay requirements becomes a challenging problem, especially when large amounts of IoTDs compete for limited resources.

Contributions

We summarize three contributions in this thesis. Each contribution, coming from one journal paper, is made up of specific mobile technique, computing paradigm and mathematical tool. The characteristics of these contributions are shown in Population Game, Potential Game, Paper [3] In the first contribution, we propose two mobile data offloading schemes based on Finite Horizon Markov Decision Process (FHMDP). Our objective is to minimize the communication cost for delivering mobile data with different delay sensitivities through multiple wireless networks, i.e., cellular network, WiFi network and D2D communication. The main contexts of this contribution can be summarized as follows:

• We propose a hybrid offloading model, where multiple wireless networks are used to transfer mobile data. MNO can minimize the total communication cost by selecting different networks.

• We formulate the data offloading problem in hybrid wireless networks as an FHMDP model, and propose an offloading algorithm that can support different delay requirements (i.e., loose and tight delay tolerant).

• We prove that there exit threshold structures in the optimal policy and propose a monotone offloading algorithm for generating monotone policy with lower computational complexity.

• The simulation results demonstrate that our proposed schemes achieve the lowest communication cost as compared with three offloading schemes.

In the second contribution, we focus on designing an efficient auction mechanism for allocating APs' bandwidth among multiple MSs; this is considered as a multi-item auction problem. MNO which owns the network infrastructure acts as the auctioneer and sells bandwidth to mobile devices through an auction. We formulated the auction problem based on robust optimization which models the desirable properties (budget feasibility, incentive compatibility, and individual rationality) of optimal auctions enabling the auctioneer to use historical data or prior knowledge of valuations. The uncertainty of item valuations is modeled as an uncertainty set, which is constructed based on limit theorems of probability theory. The optimal auction mechanism with reservation price has the structure of a Vickrey-Clarke-Groves (VCG) mechanism [START_REF] Giannakopoulos | The VCG Mechanism for Bayesian Scheduling[END_REF]. The main contexts of this contribution can be summarized as follows:

• We characterize the interaction among MNO and MSs in a multi-item auction aiming at maximizing the MNO's revenue and the amount of offloaded traffic from mobile subscribers (MSs). Our proposed multi-item auction calculates reservation prices based • Since the optimal multi-item auction problem is difficult to solve, we further propose two greedy auctions that can solve the offloading market problem in polynomial time, while preserving the properties of budget feasibility, incentive compatibility, and individual rationality. These two greedy auctions outperforms each other in different network scenarios.

• We perform numerical analysis and comparative evaluation of the proposed optimal and greedy auctions, considering realistic network scenarios. We further illustrate that the proposed offloading mechanisms can improve cellular data offloading performance and has higher robustness compared to Myerson auction.

In the third contribution, we propose a population game based approach to investigate workload balancing problem for MEC in IoT. Population game is envisioned as a powerful tool to model strategic interactions among large amounts of agents [START_REF] Barreiro-Gomez | Distributed population dynamics: Optimization and control applications[END_REF][START_REF] Quijano | The role of population games and evolutionary dynamics in distributed control systems: The advantages of evolutionary game theory[END_REF]. Specifically, we model the offloading decision making problem among large amounts of competing IoTDs as a population game, wherein IoTDs are self-interested agents and make offloading decisions individually. The main contexts of this contribution are summarized as follows:

• Population game model formulation: We formulate MEC workload balancing problem as a population game and propose an IoT Device classification model. We design an inference affected queueing model that can capture the inference among IoTDs. We use αutility function to implement different kinds of workload balancing.

• Evolutionary game dynamics analysis: We calculate NE dynamically, i.e., IoTDs can change their offloading decisions through some learning mechanism. The learning mechanism is defined as a revision protocol that allows IoTDs to adjust their offloading decisions based on decisions of other IoTDs in proximity. The evolutionary process of IoTDs's offloading strategies can be modeled by evolutionary game dynamics (i.e., a differential equation). The evolutionary game dynamics describes the variation of IoTDs's offloading decisions until an NE is obtained.

• Workload balancing algorithms: We propose two workload balancing algorithms, namely centralized workload balancing algorithm and decentralized workload balancing algorithm, based on the concept of evolutionary dynamics and revision protocols, respectively. We show that these algorithms can achieve an NE. Simulation results illustrate the evolutionary dynamics and show that the proposed algorithms can achieve efficient workload balancing in BSs and edge clouds.

Organization

The rest of this thesis is organized as follows.

• Chapter 2 gives the related works.

• Chapter 3 presents our Markov decision process based mobile data offloading.

• Chapter presents our multi-item auction based mobile data offloading.

• Chapter 5 presents our population game based workload balancing in mobile edge computing.

• Chapter provides the contributions and potential future directions.

• Chapter proposes a French summary of this thesis.

• Chapter lists the journal papers and conference papers produced during this thesis.

Chapter 2

Review of the Literature

This chapter provides the related work for mobile data offloading and mobile computation offloading in mobile cloud computing and mobile edge computing.

Review on Mobile Data Offloading

Mobile Data Offloading From Implemention Perspective

In the following, we present a survey of prior work aiming to offload cellular traffic to other mobile networks, including WiFi network and D2D communication, to reduce the network congestion.

Several contributions have shown the benefits of offloading mobile data from cellular network to WiFi network. Song et al. [START_REF] Song | Interworking of wireless LANs and cellular networks[END_REF] investigated offloading schemes for cellular and WLAN integrated networks. They considered the WLAN-first resource allocation scheme where WLAN connection is used whenever possible, in order to benefit from low cost and large bandwidth of WLAN. Siris et al. [START_REF] Vasilios | Enhancing mobile data offloading with mobility prediction and prefetching[END_REF] investigated the methods for enhancing mobile data offloading from mobile networks to WiFi APs by using mobility prediction and prefetching techniques. They evaluated these methods in terms of offloading ratio, data transmission time and cache size when using prefetching. Cheng et al. [START_REF] Cheng | Opportunistic WiFi offloading in vehicular environment: A queueing analysis[END_REF] presented an analytical framework for offloading cellular traffic to WiFi network using queuing theory. They evaluated the offloading performance in terms of average service delay. Mehmeti et al. [START_REF] Mehmeti | Performance Analysis of Mobile Data Offloading in Heterogeneous Networks[END_REF] evaluated the performance of on-the-spot mobile data offloading. They analyzed the performance improvement by WiFi-based offloading using queuing theory. Jung et al. [START_REF] Byoung Hoon | A network-assisted usercentric WiFi-offloading model for maximizing per-user throughput in a heterogeneous network[END_REF] proposed a network-assisted user-centric WiFi-offloading model in a heterogeneous network; the objective was to maximize throughput for each MS by utilizing network information.

Other contributions have shown the possibility of offloading mobile data from cellular network to D2D network. The main idea is to transmit mobile data using opportunistic communication among MSs; this has been shown to provide significant wireless capacity gains. Vinicius et al. [START_REF] Vinicius | Managing the decision-making process for opportunistic mobile data offloading[END_REF] proposed a multi-criteria decision-making framework for data offloading from 3G network to D2D network. The framework avoids changes in the infrastructure by employing only user knowledge to select MHs. It shows that delay tolerant applications can offload six-fold mobile data compared to delay sensitive applications. Sciancalepore et al. [START_REF] Sciancalepore | Offloading cellular traffic through opportunistic communications: Analysis and optimization[END_REF] considered data offloading in D2D network with heterogeneous node mobility patterns.

They used an optimization method to minimize cellular network traffic while satisfying the applications' constraints. Filippo et al. [START_REF] Rebecchi | DROid: Adapting to individual mobility pays off in mobile data offloading[END_REF] proposed a method, called DROiD, to control Chapter 2. Review of the Literature popular data distribution in D2D network; the aim was to minimize the usage of infrastructure resources. They did show that the proposed method can offload a significant amount of data from cellular network to D2D network under tight delivery delay constraints. Andreev et al. [START_REF] Andreev | Analyzing assisted offloading of cellular user sessions onto D2D links in unlicensed bands[END_REF] investigated the offloading method from cellular network to D2D network. They demonstrated that assisted offloading of cellular user sessions into D2D links improves the degree of spatial reuse and reduces the impact of interference.

Since the coverage area of D2D network is flexible with the movement of MHs, it can help offload data when WiFi connections are not available, especially for transmitting small size data, due to the short connection time and low data rate. However, since the data rate of WiFi network is higher than that of D2D network and WiFi network is more stable than D2D network, WiFi based offloading generally outperforms D2D based offloading from MS's perspective [START_REF] Zhuo | An incentive framework for cellular traffic offloading[END_REF]. Notice that D2D based offloading can offload significant mobile data from MNO's perspective, since the number of MHs can be quite large. In the simple case, WiFi APs can be considered as a special kind of MHs. Compared with MHs, WiFi APs are installed at some fixed locations and have more bandwidth.

We conclude that most existing contributions are based on WiFi offloading or opportunistic networks, without considering the combination of different mobile networks. In this thesis, we consider a hybrid offloading model, where mobile data can be offloaded through WiFi offloading and D2D communication. Our objective is to minimize the overall cost for data delivery while satisfying delay requirements of different user types.

Mobile Data Offloading From Decision Making Perspective

To cope with the growth of cellular traffic, some existing contributions have studied efficient data offloading methods from the perceptive of data offloading decision making. Cheung et al. [START_REF] Hon | DAWN: Delay-Aware Wi-Fi offloading and network selection[END_REF] proposed a Markov decision process based network selection algorithm for delaytolerant applications under the setting of a single MS. Barbarossa et al. [START_REF] Barbarossa | Joint allocation of computation and communication resources in multiuser mobile cloud computing[END_REF] proposed a centralized scheduling algorithm to jointly optimize the communication and computation resource allocations among multiple users with latency requirements. Kang et al. [START_REF] Kang | Mobile data offloading through a third-party WiFi access point: An operator's perspective[END_REF] studied the offloading problem from MNO's perspective and proposed a usage-based charging model to maximize MNO's revenues. Wu et al. [START_REF] Wu | Optimal resource allocations for mobile data offloading via dualconnectivity[END_REF] studied optimal resource allocation for data offloading via dual-connectivity, while taking into account the trade-off between optimal bandwidth allocation for base stations and optimal power allocation for mobile users.

Other contributions have investigated data offloading problems based on auction theory or game theory. Chen et al. [START_REF] Xu | Decentralized computation offloading game for mobile cloud computing[END_REF] studied the scenario where multiple users can access the same wireless base station, and designed a decentralized offloading mechanism that ensures the scalability of the proposed mechanism with the number of mobile users. Cheng et al. [START_REF] Cheng | Opportunistic WiFi offloading in vehicular environment: A gametheory approach[END_REF] took into consideration users' mobility information and proposed an auction based offloading mechanism to maximize MSs' social welfare and improve MNO's revenues. Lee et al. [START_REF] Lee | Economics of WiFi offloading: Trading delay for cellular capacity[END_REF] proposed a two-stage sequential game to model the interaction between MNO and MSs, and demonstrated, via simulations, that WiFi offloading is economically beneficial for both MNO and MSs. Paris et al. [START_REF] Paris | An efficient auction-based mechanism for mobile data offloading[END_REF] proposed a reverse auction based offloading algorithm leasing WiFi access points, owned by third parties, to allocate bandwidth to multiple mobile users. However, all these contributions assume that all players are rational and will take the truthful bidding. Different from existing contributions, we consider to implement

Mobile Cloud Computing

worst case optimality as long as the bid values belong to the uncertainty set constructed by historical bidding information.

Mobile Data Offloading From Market Perspective

Most existing studies on multi-item mechanisms aim to maximize MNO's revenue or incentivize the participation of MSs. Zhao et al. [START_REF] Zhao | Budget-feasible online incentive mechanisms for crowdsourcing tasks truthfully[END_REF] proposed an online auction method to maximize the value of services in mobile crowdsourcing (MCS), and to incentivize the participation of MSs in MCS applications. Gan et al. [START_REF] Gan | Incentivize multi-class crowd labeling under budget constraint[END_REF] proposed a reverse auction method to incentivize the participation of MSs in MCS applications. Wang et al. [START_REF] Wang | MELODY: A long-term dynamic quality-aware incentive mechanism for crowdsourcing[END_REF] designed a truthful, individual rational, budget feasible and quality-aware algorithm for task allocation in MCS. However, these contributions only considered the budget feasibility of MNO. This is because that, in MCS, MSs consume their own resources such as computational resources and computing power to help MNO solve a complex problem. MNO needs to pay MSs in return. In our model, MSs request bandwidth resources of MNO, while in MCS, MNO request services from MSs. Thus, we need to consider the budget feasibility of all MSs, which is more complex than MCS.

Other contributions consider the budget constraints of MSs. Bhattacharya et al. [START_REF] Bhattacharya | Budget constrained auctions with heterogeneous items[END_REF] proposed an approximation algorithm to solve the multi-item auction problem. Wang et al. [START_REF] Wang | A distributed truthful auction mechanism for task allocation in mobile cloud computing[END_REF] studied distributed truthful auction mechanism for task allocation in MCC. They proposed an auction model considering computational efficiency, individual rationality, truthfulness guarantee of the bidders, and budget balance. Jin et al. [START_REF] Jiang | Geographic multipath routing based on geospatial division in duty-cycled underwater wireless sensor networks[END_REF] investigated the resource sharing problem for cloudlets in MCC. They proposed an incentive mechanism to charge MSs and reward cloudlets. Although these contributions considered the budget constraints of MSs, they do not use the historical bidding information. In this thesis, we design an optimal multi-item auction mechanism based on the historical bidding information, while taking into consideration MSs' budget constraints.

Compared with the above mechanisms, the auction problem designed in Section 4 is rather challenging, and has the following differences: (1) we take full advantage of historical bidding information and prevent abnormal auction to destroy the multi-item auction;

(2) we consider the worst case optimization problem; thus, our proposed method has strong robustness compared to other optimal auction mechanisms; and (3) our optimal auction considers reservation prices that are functions of the uncertainty set and the budgets, thus can potentially protect the MNO's revenue.

Mobile Cloud Computing

Mobile computation offloading among multiple MUs has been studied in the context of two different approaches, namely centralized and decentralized computation offloading. Centralized offloading considers the scenarios where MUs don't negotiate with each other. MUs first send offloading requests to MNO with computational meta data (e.g., size of transmission data and demanding computational resources). Then, MNO can perform centralized offloading algorithm in order to implement optimal allocation [START_REF] Mao | Dynamic computation offloading for mobile-edge computing with energy harvesting devices[END_REF][START_REF] Cao | Optimal radio resource allocation for mobile task offloading in cellular networks[END_REF][START_REF] Yang | Mobile Edge Computing Empowered Energy Efficient Task Offloading in 5G[END_REF][START_REF] Chen | Task Offloading for Mobile Edge Computing in Software Defined Ultra-dense Network[END_REF]. Cao et al. [START_REF] Cao | Optimal radio resource allocation for mobile task offloading in cellular networks[END_REF] proposed an optimal radio resource allocation method to minimize the overall execution time. Yang et al. [START_REF] Yang | Mobile Edge Computing Empowered Energy Efficient Task Offloading in 5G[END_REF] considered an an energy optimization problem for computation offloading Chapter 2. Review of the Literature in order to minimize the overall energy consumption. Chen et al. [START_REF] Chen | Task Offloading for Mobile Edge Computing in Software Defined Ultra-dense Network[END_REF] proposed integer optimization based method aiming to minimize the time delay while saving the battery life of mobile devices. All these contributions investigated the minimization of time delay and energy consumption separately. They do not jointly consider these two problems.

Decentralized offloading investigates the interaction among multiple MUs. The offloading decision made by each MU is affected by other MUs's decisions. Meskar et al. [START_REF] Meskar | Energy aware offloading for competing users on a shared communication channel[END_REF] modeled the computation offloading problem as a competitive game wherein each MU aims to minimize his energy consumption. All these contributions considered a small number of MUs, since more MUs increase the overhead of system control. As a result, the computational overhead of these offloading schemes are sensitive to the number of MUs. In this thesis, we model offloading problem as a competitive population game that is insensitive to the number of MUs. Thus, large amounts of competing MUs would not increase the computational overhead. Moreover, we study the scenario where each MU aims to minimize his overall cost, i.e., the combination of the time delay minimization problem and energy consumption minimization problem.

Although many excellent work has been proposed to investigate mobile cloud computing and mobile data offloading, these two important areas have traditionally been addressed separately in the literature. To the best of our knowledge, the joint study of mobile cloud computing and mobile data offloading for next generation cellular networks has not been addressed in previous work. In Section 3, we study the network selection problem in mobile cloud computing with the objective of optimizing the transmission cost of mobile network operators. Despite the potential benefits brought by mobile data offloading, one of the major challenges is that the mobility of mobile users is inaccurate due to the randomness of MUs. We take a Markov decision process, which has well developed mechanisms to predict the mobilities of mobile users. An optimal policy can be found based on the particular structure of the monotone policies.

Mobile devices can be used to form a mobile computing grid due to the increase of their computation and communication capabilities. However, it is challenging to organize the heterogeneous computation and communication capabilities of mobile devices in proximity. Viswanathan et al. [START_REF] Viswanathan | Uncertainty-Aware Autonomic Resource Provisioning for Mobile Cloud Computing[END_REF] investigated the inherent uncertainty (e.g., network connectivity and device availability) of mobile computing grid in order to implement autonomic capabilities (i.e., self-organization, self-optimization, and self-healing) among mobile devices. Chen et al. [START_REF] Chen | Energy-Efficient Fault-Tolerant Data Storage and Processing in Mobile Cloud[END_REF] studied the dynamic nature of mobile computing grid, such as frequent topology changes due to device availability and mobility. They proposed an energy-efficient data storage and processing approach while considering the fault-tolerant problem. The nature of these contributions is to offload computation to peer mobile devices. The management cost of dynamic mobile computing grid is non-trivial; the reliability of mobile computing grid is hard to be guaranteed.

Recent Advances in Mobile Edge Computing

As an emerging computing paradigm, MEC is considered as a key enabler for future networks, and it can improve computing and storage capacities at network edge.

Cooperation with MHs

You et al. [START_REF] You | Exploiting Non-Causal CPU-State Information for Energy-Efficient Mobile Cooperative Computing[END_REF] considered a co-computing system where MS offloads computation to MHs. They formulated the energy-efficient co-computing problem as two subproblems: the slave problem and the master problem. They aimed at minimizing the energy consumption for computation offloading by considering the deadline and buffer constraints. He et al. [START_REF] He | D2D Communications Meet Mobile Edge Computing for Enhanced Computation Capacity in Cellular Networks[END_REF] studied the cooperation of D2D communications and MEC to improve the computational capacity of cellular networks, where an MU's task can be offloaded to edge cloud or nearby MU. They aimed to maximize the number of MUs that can be supported by cellular networks under the constraints of limited communication and computation resources. They formulated the computation offloading problem as a mixed integer non-linear problem and solved it with two subproblems.

Although the above studies have demonstrated the help of D2D communications in improving the computation performance of wireless networks, the limited resources at MHs are not adequate to support all mobile applications. Furthermore, it is challenging to implement efficiently distributed management among MSs and MHs.

Cooperation with Data Caching

Zhang et al. [START_REF] Zhang | Cooperative Edge Caching in User-Centric Clustered Mobile Networks[END_REF] studied delay-optimal edge caching in wireless networks, where the content placement and content size are optimized based on the information of network topology, mobile traffic, channel quality, and content popularity. Wang et al. [START_REF] Wang | Computation Offloading and Resource Allocation in Wireless Cellular Networks With Mobile Edge Computing[END_REF] jointly considered computation offloading decisions and content caching strategies in MEC. They formulated the computation offloading decisions and content caching strategies as an optimization problem, while considering the total revenue of the wireless network. Liu et al. [START_REF] Liu | Distributed Resource Allocation in Blockchain-Based Video Streaming Systems With Mobile Edge Computing[END_REF] proposed a blockchain-based framework with adaptive block sizes for mobile video streaming in MEC. They designed an incentive mechanism to facilitate collaboration among content creators, video transcoders, and content consumers. They formulated the resource allocation, offloading decisions, and adaptive block sizes as an optimization problem.

However, the cached contents change frequently with the variations of MUs' requests or network conditions, which may lead to network congestion and delay in computation offloading.

Cooperation with Energy-Harvesting Devices

MEC and wireless power transfer (WPT) are considered as promising techniques to provide mobile devices with enhanced computation capability and sustainable energy supply. Wang et al. [START_REF] Wang | Joint Offloading and Computing Optimization in Wireless Powered Mobile-Edge Computing Systems[END_REF] designed an MEC-WPT framework, where an AP can broadcast wireless power to charge multiple mobile devices and execute tasks offloaded from mobile devices. They jointly optimized energy transmit beamforming and computation offloading at AP. Hu et al. [START_REF] Hu | Wireless Powered Cooperation-Assisted Mobile Edge Computing[END_REF] studied a scenario where mobile devices are energized by WPT from an AP and they can offload mobile tasks to the AP connected with an edge cloud. They aimed at minimizing AP's total transmit energy under the constraints of mobile tasks. Bi et al. [START_REF] Bi | Computation Rate Maximization for Wireless Powered Mobile-Edge Computing With Binary Computation Offloading[END_REF] investigated the combination of WPT and MEC to achieve sustainable device operation and enhanced computational capability. They considered a WPT enhanced MEC system, where MUs follow a binary computation offloading policy. They aimed at maximizing the Chapter 2. Review of the Literature total computation rate of all MUs by jointly optimizing the computing mode selection and transmission time allocation.

The integration of WPT and MEC technologies can potentially tackle the two fundamental performance limitations (battery and computation) in mobile devices. Meanwhile, it brings new challenges to the management of wireless networks, e.g., WPT and computation offloading need to share the limited wireless resources.

Dynamic Offloading Decision Model

Most researchers consider computation offloading decision making in a quasi-static scenario. In order to implement dynamic offloading decision making, two kinds of approaches are proposed. The first one is online approach and the second one is based on queueing models.

Lyu et al. [START_REF] Lyu | Distributed Online Optimization of Fog Computing for Selfish Devices With Out-of-Date Information[END_REF] proposed an online approach to enable cooperations of N selfish MUs, where selfish behaviors are discouraged by a tit-for-tat mechanism. They achieved asymptotic optimality in a fully distributed scenario. Neto et al. [START_REF] Neto | ULOOF: A User Level Online Offloading Framework for Mobile Edge Computing[END_REF] proposed an User-Level Online Offloading Framework (ULOOF) for mobile computation offloading. Thet aimed to minimize remote execution overhead of computation offloading. Mao et al. [START_REF] Mao | Stochastic Joint Radio and Computational Resource Management for Multi-User Mobile-Edge Computing Systems[END_REF] developed an online algorithm in MEC to jointly manage the radio and computational resources . They aimed at minimizing the long-term average weighted power consumption of MUs and edge clouds.

Sarikaya et al. [START_REF] Sarikaya | Stability and Dynamic Control of Underlay Mobile Edge Networks[END_REF] studied the stability and dynamic control of MEC. They proposed a centralized flow control and a scheduling algorithm to stabilize the queues of mobile devices. You et al. [START_REF] You | Asynchronous Mobile-Edge Computation Offloading: Energy-Efficient Resource Management[END_REF] studied the energy-efficient resource-management for asynchronous MEC systems. They assumed that mobile devices have heterogeneous input-data arrival time and computation deadlines. However, the inference among large amounts of mobile devices proposes a great challenge in these models.

We conclude that tiered clouds or hierarchy clouds, i.e., clouds at multiple distances (local or remote) can improve the performance and scalability of mobile applications. Thus, the combination of different computing paradigms, e.g., mobile edge computing and mobile cloud computing, can overcome the drawbacks of these computing paradigms and further improve QoS for mobile users. Moreover, the combination of computing paradigms and different network architectures (e.g., SDN) or different mobile devices (e.g., energy-harvesting devices) are drawing attention to many researchers. Finally, different kinds of powerful mathematical tools (e.g., game theory, auction theory, optimization method and queueing model) are still widely used by many researchers.

Chapter 3 Markov Decision Process Based Mobile Data Offloading

In this chapter, we propose two mobile data offloading schemes based on Finite Horizon Markov Decision Process. Our objective is to minimize the communication cost for delivering mobile data with different delay sensitivities through multiple wireless networks, i.e., cellular network, WiFi network and D2D communication. The main contributions of this chapter can be summarized as follows:

• We propose a hybrid offloading model, where multiple wireless networks are used to transfer mobile data. MNO can minimize the total communication cost by selecting different networks.

• We formulate the data offloading problem in hybrid wireless networks as an FHMDP model, and propose an offloading algorithm that can support different delay requirements (i.e., loose and tight delay tolerant).

• We prove that there exit threshold structures in the optimal policy and propose a monotone offloading algorithm for generating monotone policy with lower computational complexity.

• The simulation results demonstrate that our proposed schemes achieve the lowest communication cost as compared with three offloading schemes.

The rest of this chapter is organized as follows. Section 3.1 describes the system model. Section 3.2 formulates the mobile data offloading problem as an FHMDP model. Section 3.3 proposes a hybrid offloading algorithm. Section 3.4 establishes the sufficient conditions for the existence of threshold policy and proposes a monotone offloading algorithm based on threshold policy. Section 3.5 evaluates the performance of the proposed offloading algorithms. Finally, Section 3.6 concludes the chapter.

System Model

In this section, we present our system model to enhance data offloading in mobile cloud.

In our model, we consider that mobile devices can access cloud services through multiple wireless networks, as shown in Fig. In our data offloading system, mobile helpers are chosen to work as data providers for mobile subscribers. Incentives for MHs to participate in data offloading can be provided by using some micro-payment scheme, or MNO can offer participants a reduced cost for the service. In this chapter, we choose the micro-payment scheme [START_REF] Zhuo | An incentive framework for cellular traffic offloading[END_REF][START_REF] Li | Multiple Mobile Data Offloading Through Disruption Tolerant Networks[END_REF], where MHs can get rewards by participating in data offloading. The price for transmitting a data unit (i.e., χ 4 ) is set by MNO. MNO first announces the price to mobile users and then chooses MHs from those users who accept the price and are willing to participate in data offloading. It is worth noting that a full analysis of such process is not the focus of this chapter.

The mobile data being received from cloud to MS is divided into a sequence of data units. The data units are predetermined by MNO. Delivering data means transmitting data of size K to MS before deadline D. K is the number of total data units and D is the maximum available time for data transmission. The data delivery is completed when non-transmitted data size k (i.e., k is the size of data that has not been received by MS) is zero before D. Conventionally, without WiFi APs and MHs, MS receives all mobile data through cellular communication. However, in our model, MS has an option to receive parts of the data through nearby WiFi or D2D communication, which may offer higher data rates and lower communication cost.

Upon arrival of a data delivery request from MS, MNO decides whether to transmit data by cellular network or offload it to WiFi and D2D networks according to data characteristics and network performance. The possibility of offloading depends on the delay characteristic (i.e. delay tolerant or not) of mobile data. If data is delay tolerant, MNO can defer data transmission to increase the possibility of offloading. Otherwise (i.e., data is delay sensitive), MNO will have less opportunities to offload mobile data from cellular network. Moreover, if data rates of WiFi and D2D networks are higher than that of cellular network, MNO can shorten the delivery time by cellular data offloading.

The main idea of data offloading is to use delay tolerance of mobile data and mobility of mobile users to seek opportunities to use WiFi and D2D networks.

We assume that a time slot T is long enough for MS to receive at least one data unit from cellular, WiFi or D2D network. An offloading decision (i.e., selecting a network) is made at the beginning of each time slot. The time when offloading decision is determined is denoted by d; it is called decision epoch. Thus, a network is selected at each decision epoch and will be the working network during the time slot.

At each decision epoch, MNO observes the current system states, i.e., the location of MS, the non-transmitted data size and the locations of available MHs. Based on the observed system state, MNO computes the communication cost for available networks. Then, MNO makes an offloading decision of either transmitting data using cellular network or offloading data to other network (i.e., WiFi or D2D network).

In this chapter, we propose a Finite Horizon Markov Decision Process to formulate this problem, with the aim to minimize communication costs and satisfy delay constraints by offloading mobile data as much as possible with WiFi network and D2D communication. Markov decision process is a useful model for sequential decision making, where MNO needs to take a sequence of actions (wireless network selection). FHMDP is a Markov decision process with a finite number of decision epochs [START_REF] Kolobov | Planning with Markov decision processes: An AI perspective[END_REF]. Since every data delivery task should be finished before a given deadline, FHMDP will plan data offloading decisions at each decision epoch. FHMDP planning phase can be implemented in remote cloud and ease the heavy burden of complex data offloading management by MS.

It is worth noting that the locations of WiFi APs and the base station are stationary, while MHs are moving around in the coverage area of base station. MHs can be considered as supplementary to WiFi APs because of their mobility.

Problem Formulation

In this section, we formulate the mobile data offloading problem as an FHMDP problem. Table 3.1 shows the notations used in the rest of this chapter. In our model, mobile data is initially delivered to one or more MSs through cellular and WiFi networks. Additionally, any MH who carries a copy of the data can opportunistically transmit it to MSs using D2D communication. For each MS, data of size K needs to be transmitted before deadline D. MNO will select a wireless network for MS, at each decision epoch d ∈ D = {1, • • • , D}, based on the system state at that time.

System State and Action Space

The system state for multiple MSs and multiple MHs is defined as s = (M, H), where M and H are the sets of states for MSs and MHs, respectively. More specifically, M = {m i , i ∈ {1, • • • , M }} includes all the states of MSs, where m i = (l i , u i , k i ) denotes the possible state of MS i; l i denotes the location of MS i, u i denotes the user type, and k i is the size of data to be transmitted. H = {l j , j ∈ {1, • • • , N }} is a set that includes all the locations of MHs, where l j is the location of MH j.

In the following, we omit the subscripts i and j of state parameters l, u and k for simplification. The state parameter l ∈ L = {1, • • • , L} denotes the index of grid (or location), where L is the number of possible grids that MSs may reach before D. We assume that cellular network can provide seamless coverage to all grids. We divide the data, to be transmitted, into K equal portions; the state parameter k ∈ K = {0, 1, • • • , K} represents the number of data portions still to be transmitted. If k = 0 when d ≤ D, the data delivery process is completed. After defining the system state of FHMDP, we next introduce the action space of MNO in mobile data offloading system. At each decision epoch, MNO selects one of the offloading actions for data transmission. There are four actions in the action space corresponding to four offloading decisions. Formally, action a ∈ A = {1, 2, 3, 4}: (1) a = 1 (waiting action): MS will wait for a chance to receive data from WiFi or D2D network; (2) a = 2 (cellular action); (3) a = 3 (WiFi action); and (4) a = 4 (D2D action): MS can receive data from cellular network,WiFi network and D2D connection, respectively.

We observe that WiFi action is available when MS is in WiFi coverage and D2D action is available when MS can access a nearby MH. Thus, the available actions depend on the state parameter l. We also notice that the mobile user type u impacts the available actions, i.e., D2D action is not available for delay sensitive data due to the low data rate. A(l, u) ⊆ A representing the set of available actions at grid l for data with type u, is defined as follows:

A(l, u) =          {1, 2}, l ∈ L 1 d , u ∈ U, {1, 2, 3}, l ∈ L 2 d , u ∈ U, {1, 2, 4}, l ∈ L 3 d , u ∈ U 0 , {1, 2, 3, 4}, l ∈ L 4 d , u ∈ U 0 . (3.1)

Transition Cost and Transition Probabilities

The transition cost for MS i, c d (m i , a), is independent from current state m i and decision epoch d. It is equal to the action cost function cost(a), which is defined as follows:

c d (m i , a i ) = cost(a i ) = ν l i a i • T • χ a i , (3.2)
where ν l a is the network data rate at grid l with action a, T is the period of time between two consecutive decision epochs, and χ a is the cost to transmit a data unit by action a, i.e., χ 2 , χ 3 and χ 4 are incurred by the usage of cellular, WiFi and D2D actions, respectively. The benefit of mobile data offloading is based on the fact that χ 3 < χ 2 and χ 4 < χ 2 . This means that the cost to send data using cellular network is higher than that of using WiFi network and D2D communication. The total cost of transmitting data of size K is the sum of costs incurred at each period during the total transmission process.

There may be some data transmission tasks that cannot be completed before the deadline. For failed data transmissions (i.e. k > 0 when d > D), the penalty cost function is defined as follows:

c D+1 (m i ) = penalty(u, k) = k (u+1) , (3.3)
where u and k finish the state parameters of m i . k (u+1) is an increasing function of k and u and reflects the fact that a larger remaining data size k and a tighter delay sensitivity u lead to a larger penalty.

In the following, we derive the transition probability between system states, which is the probability that current state s changes into s in the next decision epoch by taking action Chapter 3. Markov Decision Process Based Mobile Data Offloading a. a = {a 1 , • • • , a M } is the set of actions for all MSs. Since each MS or MH changes its state independently, we obtain the following state transition function.

P(s |s, a) = i∈M P(m i |m i , a i ) • j∈N P(l j |l j ), (3.4)
where

P(m i |m i , a i ) = P(l i , u i , k i |l i , u i , k i , a i ) = P(l i |l i ) • P(k i |l i , u i , k i , a i ). (3.5)
For MS i, the next grid l i depends only on the current grid l i and the user type u i does not change during the offloading process, i.e., u i = u i . The remaining data size k i depends on current location l i , user type u i , data size k i , and selected action a i .

P(l i |l i )
is the probability that MS will move from grid l i to grid l i . We consider a two dimensions memoryless mobility pattern of MS as follows:

P(l i |l i ) = µ, if l i = l i , ρ j , otherwise, (3.6)
where µ is the stable factor that denotes the probability that MS i stays at the same grid in two sequential decision epochs. Alternatively, MS can move randomly to an adjacent location with probability ρ j , j ∈ {1, 2, 3, 4}, where j represents one of four possible moving directions (i.e., north, south, east and west). µ and ρ j satisfy the relation µ+ j∈{1,2,3,4} ρ j = 1.

P(k i |l i , u i , k i , a i )
is the probability describing the change of remaining data size k i and is defined as follows:

P(k i |l i , u i , k i , a i ) =      1, if k i = max{k i -ν l i a i , 0} and a i ∈ A(l i , u i ), 0, otherwise, (3.7)
where the availability of a i depends on grid l i and user type u i . Fig. 3.2 illustrates MS state transition graph considering parameters l and k; the terminal states are those with k = 0.

Hybrid Offloading Algorithm

In this section, we propose an algorithm, called hybrid offloading algorithm, to compute the optimal offloading policy. A policy in FHMDP is denoted by π = {π i } i∈M , where π i : M i × D → A is the policy for MS i, which can decide an action based on m i and the decision epoch d. The feasible domain for π is denoted by Π. The objective function is defined as follows:

min π∈Π i∈M E π i m i,1 D d=1 c d m π i i,d , π i (m π i i,d , d) + c D+1 (m π i i,D+1
) .

(3.8)

Hybrid Offloading Algorithm

25

The objective function aims to minimize the expected cost to deliver data of size K for all MSs. Before presenting our offloading algorithm, we define the value function as follows.

V * d (m i ) = min a i ∈A(l i ,u i ) Q d (m i , a i ), (3.9)
where

Q d (m i , a i ) = m i ∈M i P(m i |m i , a i ) • c d (m i , a i ) + V * d+1 (m i ) = c d (m i , a i ) + m i ∈M P(m i |m i , a i ) • V * d+1 (m i ) = ν l i a i • T • χ a i + l i ∈L k i ∈K P(l i |l i ) • P(k i |l i , u i , k i , a i ) • V * d+1 (l i , u i , k i ) = ν l i a i • T • χ a i + l i ∈L P(l i |l i ) • V * d+1 (l i , u i , (k i -ν l i a i T )).
(3.10)

The value function V * d (m i ) denotes the minimal expected cost for MS i in state m i in decision epoch d to finish the data delivery process. Q d (m i , a i ) is a one step forward function that calculates the minimal expected cost if MS i selects action a i ; it is the sum of current cost c d (m i , a i ) and expected future cost. Eq (3.10) is derived from Eqs. (3.2), (3.5) and (3.7). The optimal policy is defined as

π * d (m i ) = argmin a i ∈A(l i ,u i ) Q d (m i , a i ). (3.11)
Due to the mobility of MHs, we are interested in the expected number of MHs in grid l at decision epoch d, denoted by N(d, l).

N(d, l) =      j∈N δ(l 1 j , l), if d = 1, l ∈L P(l|l ) • N(d -1, l ), if d = 2, • • • , D, (3.12)
where l 1 j is the initial location of MH j. The function δ(l 1 j , l) returns 1, if l 1 j = l; otherwise, it returns 0.

Our hybrid offloading algorithm, illustrated in Algorithm 1, consists of three phases: initialization phase (steps 1-3), planning phase (steps 4-12) and offloading phase (steps 13-22). In the initialization phase, we calculate the expected number of MHs in different locations and decision epochs using Eq. (3.12). N(d, l) is used to indicate the availability of D2D action in planning phase. We consider that MSs with the same user type have the same offloading policy. Thus, we generate the optimal policy based on the user type. Since the state transition graph, illustrated in Fig. 3.2, is an acyclic graph, we use the backward induction method to obtain the optimal offloading policy. In the planning phase, we first calculate the value function in D + 1 (steps 4-6). Then, we calculate the value function V * d (l, u, k) and optimal policy π * u (l, u, k, d) from decision epoch D to 1 (steps 7-12).

Algorithm 1 Hybrid Offloading Algorithm

1: for d ← {1, • • • , D} and l ∈ L do 2:
Compute N(d, l) using Eq. (3.12) 3: end for 4: for l ∈ L, u ∈ U and k ∈ K do 5:

V * D+1 (l, u, k) ← c D+1 (l, u, k) 6: end for 7: for u ∈ U do 8: for d ← {D, • • • , 1}, k ← {0, • • • , K} and l ∈ L do 9: Compute V * d (l, u, k) using Eq. ( 3.9) 10:
Compute π * u (l, u, k, d) using Eq. (

end for 12: end for 13: for i ∈ M do Get current idle N(d,

l d i ) 18: Set a ← π * u i (l d i , u i , k, d) 19: if k -(D -d) • ν2 • κ(u) > 0 then 20: Set a ← argmax a∈A(l d i ,u i ) ν l a 21: end if 22: Set k ← k -ν l a • T 23: Set d ← d + 1 24:
end while 25: end for

(l 1 , 3) (l 1 , 2) (l 1 , 1) (l 1 , 0) (l 2 , 3) (l 2 , 4) (l 2 , 2) (l 2 , 1) (l 2 , 0) (l 3 , 3) (l 3 , 2) (l 3 , 1) (l 3 , 0) a 1 a 2 FIGURE 3
(l i , 0), i ∈ L.
In the offloading phase, MNO determines the offloading action at each decision epoch.

Step 16 gets the location of MS i at decision epoch d, denoted by l d i .

Step 17 obtains the idle MHs (MHs that are not serving other MSs) in proximity to MS i. If N(d, l d i ) ≥ 1, then D2D action is available. Step 18 sets a to the action provided by optimal policy. In order to counteract the prediction error caused by the mobility of MSs and MHs, steps 19-21 first check whether data of size k can be transmitted using cellular network before deadline. If the response is yes, MNO will take action according to the optimal policy. Otherwise, the network with highest data rate will be selected (step 20). ν2 is the average data rate of cellular network. Notice that the function κ(u) (step 19) is used to control the delay sensitivity of different user types. Generally, user type accepting D2D communication results in larger prediction error, leading to a higher value of κ(u). We set κ(u) to 1.2 and 1 for u ∈ U 0 and u ∈ U 1 , respectively [START_REF] Calabrese | Human mobility prediction based on individual and collective geographical preferences[END_REF]. However, these two values can be adjusted according to different situations. The main computational complexity of Algorithm 1 is associated with the planning phase, that is O(U DLK).

Monotone Policy and Offloading Algorithm

Since the state space becomes extremely large with the increase of deadline D, data size K and the number of grids L, Algorithm 1 will take more time and resources to solve the problem. In order to reduce the computational complexity for generating the optimal policy, we provide sufficient conditions under which the offloading policy is monotone (nondecreasing or non-increasing) in terms of data size k and decision epoch d, called monotone policy. The monotone policy enables efficient computation due to the existence of threshold structure in optimal policy. Threshold structure has several boundaries between different Chapter 3. Markov Decision Process Based Mobile Data Offloading offloading decisions according to k and d, as discussed in Section 3.5.1. Thus, instead of generating the optimal actions for all the system state, we only need to determine the threshold states, which can greatly reduce the computational complexity.

The rest of this section is organized as follows. Subsection 3.4.1 presents our assumptions. Subsection 3.4.2 discusses the properties of optimal policy. Subsection 3.4.3 shows the special case where the monotone policy degrades into a single action a * that does not change with k and d. Subsection 3.4.4 shows the general case where the monotone policy has threshold structures. Subsection 3.4.5 presents an algorithm for generating and executing monotone policy, called monotone offloading algorithm.

Assumptions

We make the following assumptions for deriving the monotone policy.

Assumption 1. The unit costs of cellular, WiFi and D2D networks (χ 2 , χ 3 and χ 4 ) satisfy the relation

χ 3 < χ 4 < χ 2 .
Note that the benefit of cellular data offloading is based on the fact that χ 2 > χ 3 and χ 2 > χ 4 [START_REF] Rebecchi | Data offloading techniques in cellular networks: a survey[END_REF][START_REF] Gao | Opportunistic Mobile Data Offloading with Deadline Constraints[END_REF]. We further assume that χ 3 < χ 4 , since free WiFi can often be found in places such as homes, offices, or coffee shops [START_REF] Kang | Mobile data offloading through a third-party WiFi access point: An operator's perspective[END_REF][START_REF] Lee | Economics of WiFi offloading: Trading delay for cellular capacity[END_REF].

Assumption 2. The data rates of cellular, WiFi and D2D networks (ν 2 , ν 3 and ν 4 ) are location independent [START_REF] Hon | DAWN: Delay-Aware Wi-Fi offloading and network selection[END_REF].

We underline that our model can be extended to location dependent rates by considering the same action with different data rates as different actions. For example, the data rate of action a in grid l, denoted by ν l a , is location dependent. We replace action a with actions (a 1 , • • • , a W ), each of which represents the WiFi action with a different data rate. Thus, the data rate of WiFi action becomes location independent, denoted by ν a i , i ∈ {1, • • • , W }, where W denotes the number of different data rates that can be used in the case of WiFi action.

Properties of the optimal policy

We discuss some properties of the optimal policy under above assumptions.

Lemma 1. The penalty function c D+1 (l, u, k) satisfies the following relation:

c D+1 (l, u, k) -c D+1 (l, u, (k -ν a T )) ≥ c d (l, u, k, a), (3.13
)

for all d ∈ D, l ∈ L, u ∈ U, k ≥ ν a T and a ∈ A.
Proof. Note that the penalty cost (defined in Eq. (3.3)) is greater than the action cost (defined in Eq. (3.2)) for the same data size ν a T , as shown in Assumption 1.

Moreover, given u, the penalty cost is a power function with respect to data size k (see Eq. (3.3)). Thus, we obtain that, ∀k ≥ ν a T ,

c D+1 (l, u, k)-c D+1 (l, u, (k -ν a T )) ≥ c D+1 (l, u, ν a T ) -c D+1 (l, u, 0) = c D+1 (l, u, ν a T ) (3.14)

Lemma 2. The value function

V * d (l, u, k) is non-decreasing in the remaining data size k, ∀l ∈ L, u ∈ U, d ∈ D.
Proof. We prove the result using backward induction. Since the penalty function c D+1 (l, u, k) is non-decreasing in k, the value function

V * D+1 (l, u, k) = c D+1 (l, u, k) is non-decreasing in k. Assume that V * d (l, u, k) is non-decreasing in k for d ∈ {d + 1, • • • , D}.
Based on Eq (3.10), we get

V * d (l, u, k) = Q d (l, u, k, a * ) = ν a * T χ a * + l ∈L P(l |l) • V * d+1 (l , u, (k -ν a * T )). (3.15) By induction hypothesis, V * d+1 (l , u, (k -ν a * T ) is non-decreasing in k. Thus, V * d (l, u, k) is non-decreasing in k. Lemma 3. The value function V * d (l, u, k) is non-decreasing in decision epoch d, ∀l ∈ L, u ∈ U, k ∈ K. Proof. We first show that V * D+1 (l, u, k) ≥ V * D (l, u, k).
From Eq (3.9), we obtain

V * D (l, u, k) = c D (l, u, k, a * ) + c D+1 (l , u, (k -ν a * T )) ≤ c D+1 (l, u, k) = V * D+1 (l, u, k), (3.16)
where the inequality is based on Assumption 1. Next, we assume that

V d (l, u, k) is non- decreasing for d ∈ {d + 1, • • • , D}. By induction hypothesis, V * d+1 (l , u, (k -ν a * T ) is non- decreasing in Eq. (3.15). Thus, V * d (l, u, k) is non-decreasing in d.
Lemma 2 reflects the fact that the expected cost is higher when the non-transmitted data size k is larger. Lemma 3 shows that a larger decision epoch d (i.e. the deadline is closer) results in higher expected cost.

Single action monotone policy

In this subsection, we show the special case where the monotone policy degrades into a dominant action policy, i.e., π

* d (l, u, k) = a * (l,u) . Definition 1. Given l ∈ L and u ∈ U, a * (l,u) ∈ A(l, u) is a dominant action if π * d (l, u, k) = argmin a (l,u) ∈A(l,u) Q d (l, u, k, a) = a * (l,u) , (3.17)
for all d ∈ D and k ∈ K + , K + = K \ {0}; k = 0 indicates that the data transmission process is finished and thus no action is chosen. Notice that a * (l,u) is different from a * . a * (l,u) is the optimal action for all d ∈ D and k ∈ K + , while a * is the optimal action for some k and d. Next, we establish conditions under which a dominant action exists.

Chapter 3. Markov Decision Process Based Mobile Data Offloading

Theorem 1. Given u ∈ U and l ∈ L 2 d ∪ L 4 d where WiFi action is available, if ν 2 < ν 3 and ν 4 < ν 3 , then a * (l,u) = 3 (W iF i) is a dominant action, for all d ∈ D and k ∈ K + . The optimal policy is π * d (l, u, k) = a * (l,u) = 3 (W iF i). (3.18)
Proof. We first prove that

Q d (l, u, k, 3) ≤ Q d (l, u, k, 2)
. From Eq. (3.15), we get

Q d (l, u, k, 3) = ν 3 T χ 3 + l ∈L P (l |l) • V * d+1 (l , u, (k -ν 3 T )), (3.19)
Q d (l, u, k, 2) = ν 2 T χ 2 + l ∈L P (l |l) • V * d+1 (l , u, (k -ν 2 T )). ( 3
Q d (l, u, k, 2) -Q d (l, u, k, 3) = ν 2 T χ 2 -ν 3 T χ 3 + l ∈L P (l |l) • V * d+1 l , u, (k -ν 2 T ) -V * d+1 l , u, (k -ν 3 T ) (3.21a) = ν 2 T (χ 2 -χ 3 ) -δT χ 3 + l ∈L P (l |l) • V * d+1 l , u, (k -ν 2 T ) -V * d+1 l , u, (k -ν 2 T -δT ) (3.21b) > l ∈L P (l |l) • V * d+1 l , u, (k -ν 2 T ) -V * d+1 l , u, (k -ν 2 T -δT ) -δT χ 3 (3.21c) = l ∈L P (l |l) • a∈A p a δT χ a -δT χ 3 (3.21d) ≥ a∈A p a δT χ 3 -δT χ 3 (3.21e) = 0. (3.21f) Note that: (1) Based on Assumption 1, where χ 2 > χ 3 , we get ν 2 T (χ 2 -χ 3 ) > 0 in Eq. (3.21b). By eliminating ν 2 T (χ 2 -χ 3 ) > 0, we get Eq. (3.21c); (2) Eq. (3.21d) is obtained based on Lemma 2. Since (k -ν 2 T ) ≥ (k -ν 2 T -δT ), we get Eq. (3.22). V * d+1 l , u, (k -ν 2 T ) -V * d+1 l , u, (k -ν 2 T -δT ) = ∆ ≥ 0, (3.22)
where ∆ is the cost for transmitting data of size δT ; it is defined in Eq. (3.23).

∆ = a∈A p a δT χ a , (3.23)
where p a is the percentage of data size δ transmitted by choosing action a. Except for the waiting action a = 1, where p 1 = 0, p a is unknown for other actions. From Assumption 1, χ 3

is the minimum cost, we get Eq. (3.24).

∆ = δT a∈A\{1} p a χ a ≥ δT a∈A\{1} p a χ 3 = δT χ 3 . (3.24)
By Eq. (3.21), we have proved that

Q d (l, u, k, 3) ≤ Q d (l, u, k, 2). Similarly, if ν 4 < ν 3 , we can prove that Q d (l, u, k, 3) ≤ Q d (l, u, k, 4). Moreover, since ν 1 = 0 < ν 3 , we obtain Q d (l, u, k, 3) ≤ Q d (l, u, k, 1). According to Definition 1, a * (l,u) = 3 (W iF i) is the dominant action.
Based on Theorem 1, where the waiting action, cellular action and D2D action are dominated by WiFi action, we obtain the following corollary.

Corollary 1. (1) Given l ∈ L and u ∈ U, for all a 1 (l,u) ∈ A(l, u) and a 2 (l,u) ∈ A(l, u), if χ a 1 (l,u) > χ a 2 (l,u) and ν a 1 (l,u) < ν a 2 (l,u) , then a 1 (l,u) is dominated by a 2 (l,u) . (2) Given l 1 , l 2 ∈ L and u ∈ U, for all a 1 (l 1 ,u) ∈ A(l 1 , u) and a 2 (l 2 ,u) ∈ A(l 2 , u), if χ a 1 (l 1 ,u) > χ a 2 (l 2 ,u) , ν a 1 (l 1 ,u) < ν a 2 (l 2 ,u) and a 2 (l 2 ,u) ∈ A(l 2 , u) \ A(l 1 , u), then a 1 (l 1 ,u)
is potentially dominated by a 2 (l 2 ,u) . This corollary includes two parts. The first part implies the dominant relationship between two actions in same grid, while the second part reveals the potentially dominant relationship between actions in different grids.

General monotone policy

In this subsection, we show the general case where the monotone policy exists in dimensions k and d. We first introduce the basic definitions and properties of superadditive function and illustrate that Q d (l, u, k, a) is a superadditive function in K × A and D × A. Then we derive the optimal monotone policy π * d (l, u, k) in dimensions k and d.

Definition 2. A real valued function f (m, a) is superadditive in M × A, if f (m + , a + ) -f (m + , a -) ≥ f (m -, a + ) -f (m -, a -), (3.25)
for ∀m + , m -∈ M and ∀a + , a -∈ A, where m + ≥ m -and a + ≥ a -.

Given the definition of superadditive function, we next illustrate its properties summarized in Lemmas 4 and 5 [START_REF] Krishnamurthy | Partially Observed Markov Decision Processes[END_REF].

Lemma 4. If f 1 (m, a) and f 2 (m, a) are superadditive functions in M × A, then the function h(m, a) = f 1 (m, a) + f 2 (m, a) is superadditive in M × A.
π * d (l, u, k) = 2 (cellular), if k ≥ k * (l, u, d), 1 (waiting), otherwise, (3.27)
and ∀k ∈ K,

π * d (l, u, k) = 2 (cellular), if d ≥ d * (l, u, k), 1 (
π * d (l, u, k) = 2 (cellular), if k ≥ k * (l, u, d), 3 (W iF i), otherwise, (3.29)
and ∀k ∈ K,

π * d (l, u, k) = 2 (cellular), if d ≥ d * (l, u, k), 3 (W iF i), otherwise. ( 3
π * d (l, u, k) =      1 (waiting), if k ≤ k * 1 (l, u, d), 2 (cellular), if k ≥ k * 2 (l, u, d), 4 (D2D), otherwise, (3.31)
and ∀k ∈ K,

π * d (l, u, k) =      1 (waiting), if d ≤ d * 1 (l, u, k), 2 (cellular), if d ≥ d * 2 (l, u, k), 4 (D2D),
otherwise.

π * d (l, u, k) =      3 (W iF i), if k ≤ k * 1 (l, u, d), 2 (cellular), if k ≥ k * 2 (l, u, d), 4 (D2D), otherwise, (3.33)
and ∀k ∈ K,

π * d (l, u, k) =      3 (W iF i), if d ≤ d * 1 (l, u, k), 2 (cellular), if d ≥ d * 2 (l, u, k), 4 (D2D),
otherwise.

(3.34)

Proof. We prove the result of Theorem 2.a. First, we show that the transition cost c d (s, a) defined in Eq. (3.13) is superadditive in M × A. From Eq. (3.13), we get Then, we show that

c d (m + , a + ) -c d (m + , a -) = ν a + T χ a + -ν a -T χ a -, (3.35)
c d (m -, a + ) -c d (m -, a -) = ν a + T χ a + -ν a -T χ a -. ( 3
c d (m + , a + ) -c d (m + , a -) = c d (m -, a + ) -c d (m -, a -). ( 3
V * d+1 (l , u, (k -ν a )) is superadditive in M × {a -, a + }, where a -= 1 and a + = 2.
According to Lemma 2, we get Eq. (3.38). Thus,

V * d+1 (l , u, (k -ν a T )) is superadditive in M × {a -, a + }. V * d+1 (l , u, (k + -ν a + T )) -V * d+1 (l , u, (k + -ν a -T )) ≥ V * d+1 (l , u, (k --ν a + T )) -V * d+1 (l , u, (k --ν a -T )). (3.38)
Based on Lemma 4, we obtain that Q d (l, u, k, a) defined in Eq. (3.39) is superadditive in M × {a -, a + }.

Q d (l, u, k, a) = c d (m, a) + l ∈L P (l |l) • V * d+1 (l , u, (k -ν a T )) (3.39)
Based on Lemma 5, we obtain that the optimal policy π * d (l, u, k) defined in Eq. (3.40) is monotone increasing with s.

π * d (l, u, k) = argmin a∈{a -,a + } Q d (l, u, k, a) (3.40)
Thus, π * d (l, u, k) is a step function of the form Eq. (3.27). k * (l, u, d) is a state at which the optimal policy switches from a -= 1 to a + = 2, called threshold state. Similarly, we can prove Eq. (3.28) by showing that

Q d (l, u, k, a) is superadditive in D × A by Lemma 3.
We can derive Theorem 2.(b)-(d) by Corollary 1 and then prove them the same way as Theorem 2.a. For example, considering Theorem 2.b, where χ 3 < χ 4 < χ 2 (by Assumption 1) and ν 2 > ν 3 > ν 4 , action 4 is potentially dominated by action 3. This is because that χ 3 < χ 4 and ν 3 > ν 4 when 3 ∈ A(l, u) and 4 / ∈ A(l, u). Notice that the waiting action 1 is used to delay data transmission by seeking better offloading action. However, we don't need to delay now, since action 4 (the only action not in A(l, u)) is potentially dominated by action 3. Moreover, action 2 and action 3 is not dominated by each other. Thus, A(l, u) = {2, 3} and there is one threshold in l ∈ L 2 . Since χ 3 < χ 2 , we first choose action 3 (W iF i) which has lower cost. When exceeding the threshold k * (l, u, d) or d * (l, u, k), action 2 (cellular) which has higher data rate is used, as shown in Eqs. (3.29) and (3.30).

The monotone offloading algorithm will search the threshold states from the state space. In order to reduce the searching complexity, we make use of the following corollary.

Corollary 2. In the monotone policy

, ∀l ∈ L, u ∈ U, i ∈ {1, 2} is the index of thresholds, (1) k * i (l, u, d) ≥ k * i (l, u, d + 1) and k * 2 (l, u, d) ≥ k * 1 (l, u, d), ∀d ∈ D; (2) d * i (l, u, k) ≥ d * i (l, u, k + 1) and d * 2 (l, u, k) ≥ d * 1 (l, u, k), ∀k ∈ K.

Monotone offloading algorithm

We propose monotone offloading algorithm to calculate the general monotone policy with a lower computational complexity, compared with hybrid offloading algorithm. By taking advantage of the threshold structure, monotone offloading algorithm only searches for the threshold states, instead of computing the optimal action for every system state. The threshold states are calculated in dimension k, denoted by

Π = k * i (l, u, d) = k, ∀ l ∈ L, u ∈ U, d ∈ D, i ∈ {1, 2} .
Algorithm 2 consists of two phases: (1) planning phase (steps 3-5): Algorithm 3 is used to calculate the threshold states; and (2) running phase (steps 7-14): The offloading action is decided by MS's grid l. For grid with WiFi coverage (step 10), the optimal action is WiFi action; For grid with only cellular coverage (step 11), the optimal action is determined by Theorem 2.a; For grid with D2D coverage (step 12), the optimal action is determined by Theorem 2.c. Calculate Q d (s, a), ∀a ∈ A(l, u) using Eq. (3.10)

Algorithm 2 Monotone Offloading Algorithm

7: Set π * d (l, u, k) ← argmin a∈A(l,u) Q * d (s, a) 8: Set V * (s, d) ← Q * d (s, π * d (l, u, k)) 9: if π * d (l, u, k) == a i , set Π ← Π ∪ k * i (l, u, d) ← k and f lag ← 1 endif 10: Set k ← k + 1 11:
end while 12: end for Algorithm 3 calculates the threshold states for l ∈ L 1 d ∪ L 3 d . Notice that there is one threshold in l ∈ L 1 d and two thresholds in l ∈ L 3 d , as illustrated in Section 3.5.1. Algorithm 3 first determines the number of thresholds based on l (step 1). Then it calculates the threshold states k * i (l, u, d) in dimension k. Notice that we only consider k that starts from k * i (l, u, d + 1) (step 3) instead of ∀ k ∈ K, due to the fact that the threshold states cannot be found in k < k * i (l, u, d + 1) based on Corollary 2. Algorithm 3 can find the threshold states within a constant number of loops. Indeed, the maximum number of outer loops (steps 2-10) is 2. The number of inner loops (steps 4-9) is determined by

max d∈D {k * i (l, u, d) -k * i (l, u, d + 1
)}, which is a constant number. Thus, the complexity of Algorithm 3 is O(1). The complexity of Algorithm 2 is mainly due to the planning phase, that is O(LU D).

Performance Evaluation

This section evaluates the performance of our proposed approaches to implement efficient mobile data offloading. More specifically, we aim to evaluate the impact of mobile data size and delay tolerance on the performance of our offloading methods. First, we describe the parameters' settings used in our numerical analysis. Next, the threshold structures in monotone policy are illustrated. At last, we evaluate the performance metrics considered in our analysis.

Threshold Structures in Monotone Policy

Experimental Setup

We have solved the optimal offloading policy and implemented the proposed offloading methods using MATLAB. For each choice of parameters' settings, we run the simulations 1000 times and show the average values. The number of grids L equals to 20 × 20. MSs and MHs move in the grids according to the memoryless mobility pattern, where the stable factor µ = 0.6 and ρ i = 0.1, ∀i ∈ {1, 2, 3, 4} [START_REF] Cheng | Offloading multiple mobile data contents through opportunistic device-to-device communications[END_REF][START_REF] Sciancalepore | Offloading cellular traffic through opportunistic communications: Analysis and optimization[END_REF][START_REF] Hon | DAWN: Delay-Aware Wi-Fi offloading and network selection[END_REF]. The number of WiFi APs and MHs are denoted as n w and n h , respectively. The locations of WiFi APs and MHs are generated randomly. The data rates of WiFi, cellular and D2D actions follow normal distribution with means ν 2 = 16 Mbps, ν 3 = 24 Mbps and ν 4 = 8 Mbps, respectively, and standard deviations equal to 5 Mbps, which is a rational setting based on [START_REF] Lee | Economics of WiFi offloading: Trading delay for cellular capacity[END_REF][START_REF] Hao | Resource sharing optimization for device-to-device communication underlaying cellular networks[END_REF].

Similar to [START_REF] Hon | DAWN: Delay-Aware Wi-Fi offloading and network selection[END_REF], the cellular unit cost is set to χ 2 = 1 serving as a baseline. We set the unit cost for WiFi network and D2D communication in terms of the reserve price (i.e., the price that MNO is willing to pay at most for offloading one data unit), where χ 3 = [0.05, 0.08] and χ 4 = 0.2 [START_REF] Zhuo | An incentive framework for cellular traffic offloading[END_REF]. The reserve price χ 4 is set by MNO. If MNO sets a high χ 4 for D2D communication, MHs will get high rewards and thus will be willing to help in D2D offloading. In our evaluation, we set χ 3 = 0.08 and χ 4 = 0.2. The length of time slot T is 10 seconds unless stated otherwise.

In our settings, WiFi action has the highest data rate and lowest cost. Thus, according to d , where A(l, u) = {1, 2}. Thus, MNO has two actions, i.e., waiting action and cellular action. As shown in Fig. 3.3, a single threshold exits in dimension d. It shows that cellular action is selected when d is large enough. Otherwise, MNO chooses the waiting action. For example, in Fig. 3.3(a), given k = 10, the optimal action changes from waiting action to cellular action when d > 26. The single threshold that exits in dimension k has similar observation. Fig. 3.3 shows that our monotone policy will delay the usage of cellular network until the threshold state (k * (l, u, d) or d * (l, u, k)). This is rational since MNO seeks to use WiFi network or D2D communication before deadline.

We observe that the threshold changes with the number of WiFi APs and MHs. With the belief that the number of WiFi APs in Fig. 3.3(a) is higher than that in Fig. 3.3(b), MS in Fig. 3.3(a) has larger WiFi connection probability, which implies higher offloading potential (the size of data can be transmitted using WiFi network or D2D communication before deadline). Thus, the waiting action area in Fig. 3.3(a) is larger than that in Fig. 3.3(b). Since Fig. 3.3(c) has the smallest offloading potential, the waiting action area is smaller than that in Figs.

Performance Comparisons among Different Schemes

In order to evaluate the performance of our proposed offloading methods, we consider following performance metrics: (1) Total cost. The total network cost for data transmission; (2) Completion time. The total time used for data transmission; (3) Offloading ratio. The percentage of cellular traffic that MNO transmits through WiFi or D2D networks; and (4) Time usage percentage (TUP). The ratio of completion time to the deadline. We compare our proposed scheme (we name D4) with four benchmark schemes (see Table 3.2). The abbreviation of

Performance Comparison of Hybrid and Monotone Policies

Fig. 3.5 shows the performance comparison of our proposed hybrid offloading policy and monotone policy. We observe that hybrid policy has better performance in total cost (see Fig. 3.5(a)) and offloading ratio (see Fig. 3.5(b)). This is because that Algorithm 1 generates the hybrid policy based on location dependent data rates of different networks, while Algorithm 2 calculates the monotone policy based on the average data rates of different networks. Thus, hybrid policy achieves the better performance at the cost of higher computational complexity.

Impact of Data Size

We compare the performance metrics of different schemes with a given deadline D. Fig. 3.6(a) shows that the total cost increases with data size. We observe that D4 outperforms the other schemes by achieving the lowest total cost for any data size. Note that when K < 150 Mbytes, D3 outperforms N D4; it is not the case when K > 150 Mbytes. This can be explained by the fact that N D4 can use D2D action to offload more data than D3 when K > 150 Mbytes, while D3 can use delayed WiFi offloading to offload more data than N D4 when K < 150 Mbytes. Offloading ratio nw=200,nh=300 nw=300,nh=300 nw=400,nh=400 nw=500,nh=500 nw=800,nh=800

(e) Offloading ratio versus data size K for D = 100 seconds. drops rapidly with the increase of data size, while that of D4 and N D4 drop slowly. This is because D4 and N D4 use alternative D2D action to offload data. Notice that D4 has the highest offloading ratio. We also observe that the offloading ratios for delayed and nondelayed schemes are the same when K = 400 Mbytes. This can be explained by the fact that 400 Mbytes is the transmission limit under the setting used in our simulations. Since all offloading schemes try to complete data delivery before deadline, they use WiFi network wherever possible and cellular network when WiFi network is not available, which is the offloading policy used by N D3. It means that all other offloading polices (i.e., D4, N D4, and D3) degenerate to the policy N D3. Notice that, N D4 can offload more data than D3 when K < 300 Mbytes, while D3 can offload more data than N D4 when K > 300 Mbytes. This is because D3 uses delayed policy, while N D4 uses alternative D2D action.

In Figs. 3.6(d), 3.6(e) and 3.6(f), we investigate the impact of n w and n h on total cost, offloading ratio and completion time for D4. We observe that the total cost and completion time decreases, while the offloading ratio increases, with the increase of the number of WiFi APs and MHs. For example, when n w = 800 and n h = 800, we observe that the lowest total cost and completion time is achieved since it has the largest number of WiFi APs and MHs. This shows that our proposed method performs well with the increase of the numbers of APs and MHs.

Impact of Delay Tolerance

We compare the performance metrics of different schemes with a given data size K. Fig. 3.7(a) shows that, for delayed schemes (i.e., D4 and D3) and N D4, the total cost decreases when the deadline increases; indeed, larger deadlines give more opportunities (i.e. more time) to look for WiFi and D2D actions to transmit data. We observe that the total cost of D3 is larger than that of N D4 when D < 300 Mbytes. However, the situation changes when D > 300 Mbytes. This is because D3 uses waiting based strategy for seeking WiFi offloading opportunities; larger deadlines imply more WiFi offloading opportunities. Note that D4 incurs the minimum total cost compared to other schemes. Fig. 3.7(b) shows that the total transmission time increases with the deadline. We observe that, for N D3, the total time does not increase when D > 200 seconds. This is because N D3 uses on-the-spot strategy and cannot make use of the delay tolerance. The total time for delayed schemes (e.g., D3 and D4) increases almost linearly with the deadline; indeed D3 and D4 use delayed time to seek for offloading opportunities. Moreover, D4 uses slightly less total time than D3 when the deadline increases. However, D4 can offload more data than D3, as shown in Fig. 3.7(c). This is because D2D action can be used to transmit data when WiFi action is not available.

In Fig. 3.7(c), we observe that offloading ratio increases with the deadline for delayed schemes (i.e., D3 and D4). This is because delayed schemes can take advantage of the delay tolerance to seek offloading opportunities through WiFi and D2D actions. We also observe that offloading ratio for N D3 does not increase with the deadline, while offloading ratio for N D4 increases with the deadline. This is because, for N D4, MS has more opportunities to use D2D action as the deadline increases. We conclude that D4 achieves the maximum offloading ratio while satisfying data transmission deadline.

Offloading Component Analysis

We evaluate the impact of delay tolerance on the transmission time and the amount of data transmitted by different networks, as shown in Figs. 3.8 and 3.9, respectively. Three scenarios with low, middle, and high delay tolerance are considered by setting D to 200, 300 and 400 seconds, respectively. The data size K is set to 400 Mbytes. In Fig. 3.8, we observe that higher delay tolerance results in better data offloading performance for delayed schemes (i.e., D4 and D3) at the cost of longer completion time. To offload the same size of data, less cellular time is used in high delay tolerance scenario. We also observe that the completion time for delayed schemes is larger than non-delayed schemes in high delay tolerance scenario. This is because delayed schemes look for more offloading opportunities by extending the waiting time. Fig. 3.8 shows that the waiting time for D4 and D3 grows significantly when D increases. Note that the completion time of N D3 is always smaller than that of N O, due to the fact that ν 3 > ν 2 . This implies that using WiFi network can reduce the completion time. However, the completion time of N D4 is not always smaller than that of N O, as shown in Fig. 3.8(a). This can be explained by the fact that although WiFi network can reduce the completion time, the usage of D2D action may increase the completion time, due to the fact that ν 4 < ν 2 . Fig. 3.8 shows that N D4 uses less cellular time than D3 when D = 200 and D = 300 seconds. However, D3 outperforms N D4 when D = 400 seconds. This is because D3 can offload more cellular traffic with higher delay tolerance. Furthermore, Fig. 3.8 shows that D4 uses the minimum cellular time in all situations.

In Fig. 3.9, we evaluate the impact of delay tolerance on the amount of data transmitted by different networks. For each scheme, the total amount of data transmitted by different Chapter 3. Markov Decision Process Based Mobile Data Offloading networks is equal to 400 Mbytes. We observe that the cellular data size of delayed schemes (e.g., D4 and D3) decreases as the deadline increases, due to the fact that a higher delay tolerance can provide more opportunities of delivering data using WiFi or D2D action. Figs.

3.9(a), 3.9(b) and 3.9(c) shows that for D4, with the increase of WiFi data size, cellular data size decreases accordingly. However, D2D data size first increases and then decreases with the increase of deadline D. The reason behind this phenomenon is that when higher delay tolerance is allocated, it is more likely to have more D2D connections or larger D2D data size. However, higher delay tolerance also increases the WiFi data size with lower cost χ 3 < χ 4 . Thus, part of D2D offloading is replaced by WiFi offloading when more WiFi connections are possible. Moreover, compared to other schemes, the cellular data size of D4 decreases faster with higher delay tolerance, as shown in Figs. 3.9(a), 3.9(b) and 3.9(c). This demonstrates that the proposed D4 can offload more cellular data in practice.

Conclusion

This chapter proposed a hybrid data offloading model, where MNO can use WiFi network and D2D communication to offload mobile data of MSs. We formulated the mobile data offloading problem as an FHMDP and proposed a hybrid offloading algorithm for delay sensitive and delay tolerant applications. Moreover, we established sufficient conditions for the existence of thresholds in monotone policy and proposed a monotone offloading algorithm which can reduce the computational complexity caused by large data size and long deadline. The simulation results demonstrate that, compared to existing offloading schemes, our proposed schemes can achieve minimal data offloading cost and maximum offloading ratio.

Chapter 4

Multi-Item Auction Based Mechanism for Mobile Data Offloading

In this chapter, we focus on designing an efficient auction mechanism for allocating APs' bandwidth among multiple MSs; this is considered as a multi-item auction problem. MNO which owns the network infrastructure acts as the auctioneer and sells bandwidth to mobile devices through an auction. We formulated the auction problem based on robust optimization which models the desirable properties (budget feasibility, incentive compatibility, and individual rationality) of optimal auctions enabling the auctioneer to use historical data or prior knowledge of valuations. The uncertainty of item valuations is modeled as an uncertainty set, which is constructed based on limit theorems of probability theory. The optimal auction mechanism with reservation price has the structure of a VCG mechanism [START_REF] Giannakopoulos | The VCG Mechanism for Bayesian Scheduling[END_REF].

The main contributions of this chapter can be summarized as follows:

• We characterize the interaction among MNO and MSs in a multi-item auction aiming at maximizing the MNO's revenue and the amount of offloaded traffic from mobile subscribers. Our proposed multi-item auction calculates reservation prices based on the uncertainty set and the MSs' budgets; this can prevent market manipulation. Our proposed auction is implemented by robust optimization. Instead of requiring the full knowledge of MSs' valuations, robust optimization uses few information of MSs' valuations and can obtain a global -optimal solution.

• Since the optimal multi-item auction problem is difficult to solve, we further propose two greedy auctions that can solve the offloading market problem in polynomial time, while preserving the properties of budget feasibility, incentive compatibility, and individual rationality. These two greedy auctions outperforms each other in different network scenarios.

• We perform numerical analysis and comparative evaluation of the proposed optimal and greedy auctions, considering realistic network scenarios. We further illustrate that the proposed offloading mechanisms can improve cellular data offloading performance and has higher robustness compared to Myerson auction.

The rest of the chapter is organized as follows. Section 4.1 presents the system model. Section 4.2 formulates the multi-item auction as a robust optimization problem. Section 4.3 and Section 4.4 propose the optimal and greedy auction mechanisms, to solve the offloading market problem, respectively. Section 4.5 illustrates and analyzes the numerical results. Section 4.6 concludes the chapter.

System Model

In this section, we present the economic definitions and network model that are considered in our multi-item auction mechanism; the objective of this mechanism is to implement efficient mobile data offloading. A scenario of data offloading among multiple APs and MSs is shown in Figure 4.1, where MSs, in the coverage area of APs, engage in an auction to acquire bandwidth (in WiFi network). We first model the uncertainty of MNO's beliefs on MS's val- uations using uncertainty set. Then, we introduce the general economical definitions for multi-item auction.

Cellular BS WiFi AP1 WiFi AP2 WiFi AP3 MS1 MS3 MS2
Let N denote the set of MSs, and M denote the set of APs owned by MNO, where |N | = n and |M| = m. MS i has a private valuation for the unit bandwidth usage associated with AP j, denoted by v ij which is unknown to MNO. Let v = {v ij |i ∈ N , j ∈ M} denote the private valuation matrix. Thus, for AP j, v j = (v 1j , . . . , v nj ) denotes the column vector of private valuation matrix P. Moreover, MS i is budget constrained and the available budget is denoted by B i , i ∈ N , while AP j is bandwidth constrained and the available bandwidth is denoted by C j , j ∈ M. In this chapter, we consider that the valuation information is private (only known to MS) and budget information is public (known to MNO). 1For AP j, since the private valuations of MSs are hidden from MNO, we model MNO's beliefs on the valuations of n MSs using uncertainty set U j , where the valuation vector v j ∈ U j . MNO's belief on valuations for all APs is denoted as U = {U j } j∈M .

We assume that the valuations for AP j are independent and identically distributed, as well as the expectation and deviation of AP j are µ j and δ j respectively. Based on the central limit theory, the distribution of

n i=1 v ij -n • µ j √ n • δ j
is approximately a standard normal distribution when n → ∞. Thus, the uncertainty set U j can be constructed as follows.

U j = (v 1j , . . . , v nj ) -Γ ≤ n i=1 v ij -n • µ j √ n • δ j ≤ Γ , (4.1)
where F j and F j are the lower bound and upper bound of the competition function f i (k), respectively. Γ is a parameter that controls the conservativeness of the historical valuations. For example, under the central limit theorem, the probability that

(v 1j , • • • , vnj ) belongs to -Γ ≤ n i=1 v ij -n • µ j √ n • δ j ≤ Γ can be calculated by P (v 1j , • • • , vnj ) ∈ U j = 2Φ(Γ) -1, (4.2)
where Φ(•) is the cumulative distribution function of the standard normal. If we set Γ to 1,2 and 3, then P((v 1j , • • • , vnj ) ∈ U j ) is 0.683, 0.955 and 0.997, respectively. A smaller Γ makes MNO consider only those valuations with higher probability. A larger Γ makes MNO consider a larger range of valuations, which increases the accuracy of auction at the cost of computational complexity. Thus, MNO needs to choose a proper Γ to balance the accuracy and computational complexity of the auction.

Problem Statement

In this section, we formulate the multi-item auction based data offloading problem as a robust optimization problem. Our objective is to maximize the total revenue of MNO for all valuations in the uncertainty set U. We first introduce the decision variables that represent the allocation rule and the payment rule. Then, we define the properties that the allocation and payment rules should satisfy in order to implement an efficient auction. The notations used in this chapter are described in Table 4.1.

Allocation and Payment Rules

The decision variable x v = {x v ij } i∈N ,j∈M describes APs' bandwidth allocation among multiple MSs based on the valuation matrix v, that is, if the valuation matrix is v, MNO will allocate x v ij bandwidth of AP j to MS i. If MS i is not in the coverage area of AP j, then

B = {B i } i∈N MS budget constraints D = {D i } i∈N MS bandwidth demand C = {C i } i∈M AP bandwidth constraints v = {v ij } i∈N ,j∈M Bid matrix v k = {v kj } j∈M Bid vector of MS k v -k = {v ij } i∈N \{k},j∈M
Bid vector except for MS k

z = {z ij } i∈N ,j∈M Worst case bid vector x * = {x * ij } i∈N ,j∈M
Nominal allocation in worst case

r * = {r * ij } i∈N ,j∈M
Reservation prices in worst case

y v = {y v ij } i∈N ,j∈M Adapted allocation y v -k = {y v -k ij } i∈N \{k},j∈M Adapted allocation without MS k a v = {a v ij } i∈N ,j∈M Real allocation p v = {p v i } i∈N Real payments x v ij = 0. The decision variable p v = {p v i } i∈N
denotes the payment of MSs according to current valuation matrix v, where p v i is the total payment of MS i for using the bandwidth of APs. Thus, p v i ≥ 0. Given the allocation variable x v and payment variable p v , we can derive the utility (i.e., the difference of total valuation and payment) of MS i as follows,

U v i = j∈M v ij • x v ij -p v i , i ∈ N , v ∈ U. (4.3)
The allocation and payment variables should satisfy the following properties in order to implement an efficient multi-item auction.

• Individual Rationality (IR). This property ensures nonnegative utilities (i.e., the payment of MS should be less than his obtained valuation) for MSs who bid truthfully. Formally,

p v i ≤ j∈M v ij • x v ij , ∀i ∈ N , ∀v ∈ U. (4.4)
• Budget Feasibility (BF). This property ensures the payment of each MS is within his budget constraint. Formally,

p v i ≤ B i , ∀i ∈ N , ∀v ∈ U, (4.5)
where B i is the limited budget of MS i.

• Incentive Compatibility (IC). This property ensures that MS cannot improve his utility by bidding untruthfully. Thus, the utility of MS under truthful bidding is higher than untruthful biddings; this allows avoiding market manipulation by MSs. Formally,

U (v i ,v -i ) i ≥ U (u i ,v -i ) i , ∀i ∈ N , ∀(v i , v -i ) ∈ U, ∀(u i , v -i ) ∈ U, (4.6)
where v i = {v ij } j∈M is the truthful valuation of MS i and u i = {u ij } j∈M is a possible valuation of MS i. v -i = {v kj } k∈N \{i},j∈M denotes the valuation matrix obtained by omitting the valuations from MS i. By substituting Eq. ( 4.3) into Eq. (4.6), we have

j∈M v ij •x (v i ,v -i ) ij -p (v i ,v -i ) i ≥ j∈M v ij • x (u i ,v -i ) ij -p (u i ,v -i ) i , ∀i ∈ N , ∀(v i , v -i ) ∈ U, ∀(u i , v -i ) ∈ U, (4.7)
With some mathematical manipulation of Eq. (4.7), we obtain the following equation.

j∈M v ij • x (u i ,v -i ) ij -x (v i ,v -i ) ij + p (u i ,v -i ) i -p (v i ,v -i ) i ≥ 0, ∀i ∈ N , ∀(v i , v -i ) ∈ U, ∀(u i , v -i ) ∈ U. (4.8)

Optimal auction problem

The optimal auction design problem, based on the above property constraints, is formulated as a robust optimization problem, with the objective to maximize the revenue of MNO for all the valuations in set U. Since MNO's beliefs on MSs' valuations are modeled as an uncertainty set, we focus on maximizing the worst case revenue.

p v i ≤ j∈M v ij • x v ij , ∀i ∈ N , ∀v ∈ U (4.9c) p v i ≤ B i , ∀i ∈ N , ∀v ∈ U (4.9d) j∈M v ij • x (u i ,v -i ) ij -x (v i ,v -i ) ij + p (u i ,v -i ) i -p (v i ,v -i ) i ≥ 0, ∀i ∈ N , (4.9e)
∀(v i , v -i ) ∈ U, ∀(u i , v -i ) ∈ U i∈N x v ij ≤ C j , ∀j ∈ M, ∀v ∈ U (4.9f) j∈M x v ij ≤ D i , ∀i ∈ N , ∀v ∈ U (4.9g) x v ij ≥ 0, ∀i ∈ N , ∀j ∈ M, ∀v ∈ U (4.9h) p v i ≥ 0, ∀i ∈ N , ∀v ∈ U. (4.9i)
Constraint (4.9b) ensures the maximization of worst case revenue considering all the possible valuations in the uncertainty set U. Constraints (4.9c), (4.9d) and (4.9e) correspond to IR, BF and IC properties, respectively. Constraint (4.9f) ensures that the bandwidth allocation should not exceed the available bandwidth of an AP. Constraint (4.9g) guarantees that each MS cannot obtain over-demanding bandwidth. Note that the demand D i varies over time due to the stochastic nature of MS traffic. We consider a quasi-static network scenario [START_REF] Shah-Mansouri | An incentive framework for mobile data offloading market under price competition[END_REF], and analyze the auction mechanism in a data offloading period (e.g., ten seconds), during which D i remains unchanged for all i ∈ N . Finally, Constraint (4.9i) prevents negative allocation and payment for MSs. Note that v ∈ U is defined as

{v = (v 1 , • • • , v m )|v j ∈ U j , ∀j ∈ M}. v j ∈ U j
is short for the following two constraints derived from Eq. (4.1).

n i=1 v ij -n • µ j ≤ Γ √ n • δ j , ∀j ∈ M, n i=1 v ij -n • µ j ≥ -Γ √ n • δ j , ∀j ∈ M.
For simplicity, we use v ∈ U to stand for the above constraints in the rest of the chapter.

Optimal auction mechanism

In this section, we propose the optimal auction mechanism to solve the optimization problem (4.9) in order to determine an optimal allocation and payment rules. That is, how APs' bandwidth is shared among multiple MSs, and how much MSs are charged for using allocated bandwidth. Our optimal auction mechanism illustrated in Algorithm 4, takes as input the uncertainty set U, MS budget vector B, AP constraint vector C, MS demand vector D and bid matrix v, and calculates as output the real allocation matrix a v and the payment vector p v . We will refer to Algorithm 4 as Optimal Algorithm in the rest of chapter. We first introduce the details of Optimal Algorithm. Then, we show the auction properties of Optimal Algorithm. for j ∈ M do 5:

Algorithm 4 Optimal offloading auction mechanism

Input: U, B, C, D, v, M, N Output: a v ,
r * ij = ξ * j + (η * i + λ * i + θ * i ) • z ij 6:
end for 7: end for 8: y v ← solving problem (4. for j ∈ M do 14: 2). The aim of nominal allocation is to calculate the reservation price r * = {r ij } i∈N ,j∈M and the nominal allocation x * = {x ij } i∈N ,j∈M . MS i has to bid at least r ij in order to use the bandwidth provided by AP j. x * represents the best allocation in worst case scenario, which is part of the final allocation calculated in the phase of final allocation. Reservation price is obtained by calculating problems [START_REF] Mach | Mobile edge computing: A survey on architecture and computation offloading[END_REF] and ( 13) sequentially. Final allocation calculates the real allocation a v and final payment p v based on a specific bid matrix v. The final allocation a v = x * + y v , where y v = {y v ij } i∈N ,j∈M , called adapted allocation, denotes the best allocation for a specific bid matrix v. Final allocation is based on the results of optimization problems Chapter 4. Multi-Item Auction Based Mechanism for Mobile Data Offloading [START_REF] Yu | Auction-based coopetition between LTE unlicensed and Wi-Fi[END_REF] and [START_REF] Mohammad | Incentivizing device-to-device load balancing for cellular networks: An online auction design[END_REF]. Problems ( 14) and ( 15) can be calculated independently, since their inputs don't rely the results of each other.

a v ij = x * ij + y v
Problem [START_REF] Mach | Mobile edge computing: A survey on architecture and computation offloading[END_REF] Input: Q, U Solution: x * , z Problem ( 13)

Input: Q, x * , z Solution: * , η * , λ * , θ * Reservation Price Input: Q, * , η * , λ * , θ * Run Steps (3 -7) Solution: r * Problem (14) Input: Q, x * , r * , v Solution: y v Problem (15) Input: Q, x * , r * , v Solution: y v -k Final Results Input: x * , r * , y v , y v -k Run Steps (12 -19) Solution: a v , p v

Phase of Nominal Allocation

In the phase of nominal allocation, Step 1 calculates the worst case bid matrix z and reservation price r * by solving the bilinear optimization problem (4.10), where the constraints (4.10b), (4.10c) and (4.10d) are derived from constraints (4.9d), (4.9f) and (4.9g), respectively. Constraint (4.10e) that captures the IC and IR properties of problem (4.9) is used to calculate the worst case bid matrix z, under which the obtained payoff j∈M x ij • z ij for MS i is minimum. The nominal allocation x * is a preallocation that corresponds to the worst case bid matrix z.

max x,v i∈N j∈M x ij v ij (4.10a) s.t. j∈M x ij • v ij ≤ B i , ∀i ∈ N , (4.10b) i∈N x ij ≤ C i , ∀j ∈ M, (4.10c) j∈M x ij ≤ D j , ∀i ∈ N , (4.10d) j∈M x ij • v ij ≤ j∈M x ij • u ij , ∀u ∈ U, ∀i ∈ N , (4.10e)
x ≥ 0, v ∈ U. (4.10f)

In order to obtain the reservation price r * , We first simplify the problem (4.10) as a linear programming problem with decision variable x by: 1) replacing variable v with constant z (obtained in Step 1); 2) replacing Constraint (4.10e) with Eq. (4.11).

j∈M

x ij • v ij ≤ j∈M x * ij u i j , ∀i ∈ N , (4.11)
where

u i = arg min u∈U j∈M x * ij • u ij , ∀i ∈ N . (4.12)
Then, we can obtain the dual problem of simplified problem (4.10) as follows.

min ξ,η,λ,θ j∈M

ξ j C i + i∈N η i B i + λ i D i + θ i j∈M x * ij u i j (4.13a) s.t. ξ j + z ij (η i + λ i + θ i ) ≥ z ij , ∀i ∈ N , j ∈ M, (4.13b)
ξ j , η i , λ i , θ i ≥ 0, ∀i ∈ N , j ∈ M. ( 4

Phase of Final Allocation

In the phase of final allocation, We first calculates the adapted allocation y v based on bid matrix v in Step 8. The adapted allocation y v is obtained by solving the linear problem (4.14). The objective function (Eq. (4.14a)) of this problem maximizes the social welfare (i.e., the total valuations of all MSs) taking into consideration the reservation price r * . Thus, Constraints (4.14b), (4.14c) and (4.14d) are adjusted by considering the impact of nominal allocation x * and reservation price r * obtained from the phase of nominal allocation.

max y v i∈N j∈M y v ij • (v ij -r * ij ) (4.14a) s.t. i∈N y v ij ≤ C i - i∈N x * ij , ∀j ∈ M, (4.14b) j∈M y v ij • v ij ≤ B i - j∈M x * ij • r * ij , ∀i ∈ N , (4.14c) j∈M y v ij ≤ D j - j∈M x * ij , ∀i ∈ N . ( 4
max y v -k i∈N \{k} j∈M y v -k ij • (v ij -r * ij ) (4.15a) s.t. i∈N \{k} y v -k ij ≤ C i - i∈N \{k} x * ij , ∀j ∈ M, (4.15b) j∈M y v -k ij • v ij ≤ B i - j∈M x * ij r * ij , ∀i ∈ N \ {k}, (4.15c) j∈M y v -k ij ≤ D j - j∈M x * ij , ∀i ∈ N \ {k}. (4.15d)
With x * and r * obtained in the phase of nominal allocation, as well as y v and y v -k obtained in this phase, we can calculate the final allocation a v and the final payment p v for all k ∈ N . Steps 12 -16 calculate the final allocation a v that is the sum of nominal allocation x * and adapted allocation y v . Steps 17 -19 calculate the final payment p v using Eq. (4.16), where p v k consists of the payment of using a v k bandwidth and the difference between the optimal value of the objective function obtained with and without the participation of k. This payment scheme guarantees the IR property of Optimal Algorithm. Furthermore, we show that Optimal Algorithm can implement an efficient auction according to Theorem 3.

p v k = j∈M y v kj • r * kj + j∈M x * kj • r * kj + i∈N \{k} j∈M y v -k ij (v ij -r * ij ) - i∈N \{k} j∈M y v ij (v ij -r * ij ), ∀k ∈ N . (4.16)
Theorem 3. The proposed auction mechanism illustrated in Optimal Algorithm has the properties of incentive compatibility, budget feasibility, individual rationality and worst case optimality.

The proof of Theorem 3 is illustrated in Section 4.7.

Design Rational

We discuss the relationship of our proposed mechanism and VCG mechanism as follows.

(a) The allocation rule has a structure similar to that of VCG mechanism, where the bandwidth is allocated to a set of MUs in order to maximize a social welfare function. In Optimal Algorithm, the social welfare function is defined in Eq. (14a), which is parameterized by the reservation price r * .

(b) The payment rule, as defined in Eq. ( 16), is also similar to that of VCG mechanism.

Each MU is charged with the opportunity cost, which is defined as the lowest amount that MU has to bid in order to win the allocation.

(c) Unlike VCG mechanism, we calculate the reservation price r * in the worst case. Thus, r ij is defined as the lowest price that MNO would be willing to accept for allocating the corresponding bandwidth from AP j to MS i. The reservation price is a threshold price; the bids less than the reservation price will not be accepted. The reservation price can accelerate the auction process, since the set of prices that are lower than the reservation price can be discarded.

(d) Unlike VCG mechanism, we focus on the case where the payments of MUs provided by the optimal mechanism do not exceed their budget constraints. Standard mechanisms, such as VCG mechanism and its variants, are not applicable here [START_REF] Singer | Budget feasible mechanisms[END_REF][START_REF] Deng | Truthful mechanisms for secure communication in wireless cooperative system[END_REF].

In summary, the well-known VCG mechanism is a dominant strategy mechanism, which can achieve ex-post incentive compatibility (truth-telling is a dominant strategy for every player in the game). However, VCG mechanism cannot implement the budget feasibility of the auction, which costs extra payment from MUs and decreases their payoffs. Thus, it cannot be properly used in the problem that we are solving in this chapter. Compared with VCG mechanism, our proposed optimal mechanism is an incentive efficient mechanism that can maximize the expected total payoff of all MUs. Additionally, it achieves the budget feasibility of MUs. There is no extra cost paid in the auction when applying our optimal mechanism while VCG mechanism can not.

Solving Optimal Algorithm

Solving Optimal Algorithm needs to calculate one bilinear optimization problem (4.10) and three linear optimization problems (4.13), (4.14) and (4.15). The linear problems can be solved using simplex method [START_REF] Holzhauser | A network simplex method for the budget-constrained minimum cost flow problem[END_REF]. The bilinear problem, which is the computation intensive step in the proposed mechanism, is NP-hard [START_REF] Del | Mixed-integer quadratic programming is in NP[END_REF]. However, we can solve problem [START_REF] Mach | Mobile edge computing: A survey on architecture and computation offloading[END_REF] in polynomial time to achieve global -optimal solution. This is based on the observation that both inner and outer optimization problems of problem [START_REF] Mach | Mobile edge computing: A survey on architecture and computation offloading[END_REF] are linear optimization problems. Thus, fixing the inner optimal solution, there always exists an extreme point solution to the outer problem and vice versa. We can use Bender decomposition algorithm [START_REF] Hadi Meshgi | Optimal resource allocation in multicast device-to-device communications underlaying LTE networks[END_REF] to solve problem [START_REF] Mach | Mobile edge computing: A survey on architecture and computation offloading[END_REF] by simply enumerating all the extreme points. Please refer to [START_REF] Hadi Meshgi | Optimal resource allocation in multicast device-to-device communications underlaying LTE networks[END_REF] for details.

Greedy Auction Mechanism

In this section, we turn to the concept of two-sided matching [START_REF] Gao | Two-sided matching based cooperative spectrum sharing[END_REF] to solve the data offloading problem in polynomial time. In our two-sided matching scenario, one matching partners are MSs and another matching partners are APs. Note that each AP can be matched to multiple MSs. We propose two greedy auction mechanisms: 1) MatchingAP scheme, i.e., it is AP which selects MSs that it will provide network connection to; 2) MatchingMS scheme, i.e., it is MS which selects appropriate AP for network connection. Then, we show that these two algorithms satisfy the properties of individual rationality and incentive capability.

MatchingAP Scheme

Algorithm 5 Greedy MatchingAP Scheme

Input: b, d, M, N , C Output: a, p 1: M ← Sort(j ∈ M, C j |N j | , "non -decreasing ) 2: N ← N 3: while M = ∅ ∧ N = ∅ do 4: j ← N ext(M ), M ← M \ {j} 5: N j ← Sort(i ∈ N j , b i , "non -decreasing ) 6: while i∈N j a ij ≤ C j ∧ N j = ∅ do 7: i ∈ N ext(N j ) 8: if j∈M a ij = 0 ∧ d i + i∈N j a ij ≤ C j then 9: a ij ← d i 10: N ← N \ {i} 11: end if 12:
end while 13: end while 14: for all j ∈ M do 15:

p k ← max {i∈N j |a ij =0} b i 16: for all i ∈ N j ∧ a ij = d i do 17: p i ← p j • d i 18:

end for 19: end for

The greedy algorithm for MatchingAP scheme, illustrated in Algorithm 5, is composed of two phases, namely, allocation phase and payment phase. The allocation phase aims to select MSs for each AP that can offload mobile data traffic. The payment phase calculates the price paid by each winner by considering the maximum bid from un-winning MSs. This payment scheme is widely used in second price auction to derive a truthful bidding [START_REF] Brocas | Second-price common value auctions with uncertainty, private and public information: experimental evidence[END_REF].

Greedy Auction Mechanism

55

In Algorithm 5, Step 1 defines the allocation order for the set of APs. The sorted list M is obtained by sorting all APs participating in the auction in a non-decreasing order of bandwidth per number of covered MSs (i.e., the potential bidders for each AP). The allocation phase (Steps 3 -13) considers APs starting from the first AP in M . In MatchingAP scheme, each AP can select MSs under its radio coverage area as potential bidders. Since one AP may have multiple bidders, we define an allocation rule for each AP, which states that the bidder who bids higher value has a higher probability to be served, as shown in Step 5, where MSs under the coverage of AP j are sorted in a non-decreasing order according to the bids submitted by MSs. The bandwidth allocation phase continues until AP j has allocated all its bandwidth or it has no more MSs to be considered (Step 6). For each MS, if it is not allocated to other APs (i.e., served by other APs) and the network demand does not exceed the bandwidth of AP j, it will be allocated to AP j (Steps 8 -9). The payment phase (Steps 14 -19) defines the price paid by each winning MS as the maximum bid value of the set of un-winning MSs. The final payment of MS i is calculated by the market clearing price p k (obtained in Step 15) and the network demand D i (Step 17).

MatchingMS Scheme Algorithm 6 Greedy MatchingMS Scheme

Input: b, d, M, N , C Output: a, p 1: N ← Sort(i ∈ N , max j∈M b ij , "non -decreasing ) 2: M ← M 3: while M = ∅ ∧ N = ∅ do 4: i ← N ext(N ), N ← N \ {i} 5:
M i ← Sort(j ∈ M i , C j , "nondecreasing )

6:

while j∈M a ij < d i ∧ M i = ∅ do 7: j ∈ N ext(M i ) 8: if d i + i∈N j a ij ≤ C j then 9: a ij ← d i 10: M ← M \ {j} 11: end if 12:
end while 13: end while 14: for all j ∈ M do 15:

p k ← max {i∈N j |a ij =0} b i 16: for all i ∈ N j ∧ a ij = d i do 17: p i ← p j • d i 18:
end for 19: end for

In the following, we present the greedy algorithm illustrated in Algorithm 6 for MatchingMS scheme; it has the same algorithm structure as MatchingAP scheme. It also includes allocation and payment phases. Particularly, MatchingMS scheme has same payment rule as MatchingAP scheme.

Chapter 4. Multi-Item Auction Based Mechanism for Mobile Data Offloading

In Algorithm 6, Step 1 sorts the set of MSs by the maximum bid in a non-decreasing order. Since we aim to maximize the revenue of MNO, MSs are considered according to the allocation order obtained in N . The allocation phase (Steps 3 -13) terminates until all MSs or APs are considered. In the inner loop, MS selects one AP that can provide network connection to it. APs that cover MS i are sorted in the list M i according to bandwidth (Step 5). The network selection phase continues until MS i has selected one AP or it has no more APs to consider (Step 6). For each AP, if it has enough bandwidth to satisfy the demand of MS, it will be selected by MS (Steps 8 -9). The payment phase (Steps 14 -19) is the same as that in Algorithm 5.

These two algorithms satisfy the properties of individual rationality and incentive capability, since they adopted the similar auction structure used in [START_REF] Paris | An efficient auction-based mechanism for mobile data offloading[END_REF]. The budget feasibility is satisfied by the fact that the payment of each MS will not be greater than its bid, i.e., if MS i selects bid b i ≤ B i d i , then its final payment satisfies p i ≤ b i . We next analyze the time complexity of MatchingAP and MatchingMS. We consider the time complexity of MatchingAP in three parts.

• (Step 1) In MatchingAP algorithm, the construction of an AP preference list is the first step. Since there are m APs, with an efficient sorting algorithm, we can get the AP preference list in time of O(m log(m)).

• (Steps 3 -13) We first consider the outer while loop of the algorithm. This loop will terminate when the set of APs or the set of MSs becomes empty. Thus, the maximum number of loops is max{m, n}. In step 5, we construct an MS preference list for each AP with the complexity of O(n log(n)). Then, we consider the inner while loop from step 6 to step 12. It is obvious that the maximum number of loops is n, which is the total attempts made by an AP. Indeed, assume that every summation has time complexity O(1). The total complexity of inner loop is O(n). Since step 5 has higher complexity than that of inner loop, the total complexity of outer loop is O(n log(n)max{m, n}).

• (Steps 14 -19 ) It is easy to see that the time complexity of these steps is O(mn).

Finally, the total complexity of the MatchingAP is O max{m log(m), (n log(n)max{m, n}), mn} . In general cases, the number of MSs is larger than that of APs, i.e., n > m. Thus, the time complexity of MatchingAP is O(n 2 log(n)), mainly due to steps 3 -13. Following the similar analysis, we can obtain that the time complexity of MatchingMS is O max{n log(n), (m log(m)max{m, n}), In general cases, the time complexity of MatchingMS is O (mn log(m))} .

Numerical Results

In this section, we evaluate the performance of the proposed auction mechanism for selling APs' bandwidth to MSs in proximity. More specifically, we aim to evaluate the impact of AP density (the number of APs), budget constraint and uncertainty set of valuation on the performance of the proposed mechanisms in order to implement an effective mobile data offloading marketplace. We first introduce the parameter settings, then we illustrate and discuss the numerical results achieved by the proposed offloading schemes.

We compare our proposed schemes, namely optimal scheme (Optimal Algorithm) and two greedy schemes (i.e., MatchingAP scheme and MatchingMS scheme), with the work in [99, 100], denoted as MDP scheme, since this work aims to maximize the amounts of offloaded data based on Markov Decision Process. The following performance metrics are considered in the evaluation.

• Total revenue: The total payoff of MNO.

• Offloaded traffic: The amount of traffic that can be offloaded.

• Winning MSs: The number of MSs that win the auction.

Simulation Setup

In our evaluation, we consider a measurement-based model [START_REF] Shah-Mansouri | An incentive framework for mobile data offloading market under price competition[END_REF], where there is an MNO represented by a macrocell BS. The number of APs and MSs, located in the coverage of BS, are chosen uniformly from the intervals [2,[START_REF] Guo | Computation Offloading for Multi-Access Mobile Edge Computing in Ultra-Dense Networks[END_REF] and [START_REF] Mach | Mobile edge computing: A survey on architecture and computation offloading[END_REF][START_REF] Viswanathan | Uncertainty-Aware Autonomic Resource Provisioning for Mobile Cloud Computing[END_REF], respectively. Unless stated otherwise, we use the information from [START_REF] Zhuo | An incentive framework for cellular traffic offloading[END_REF][START_REF] Shah-Mansouri | An incentive framework for mobile data offloading market under price competition[END_REF][START_REF] Kou | An economic user-centric WiFi offloading algorithm for heterogeneous network[END_REF] to set the parameters' values. Each MS submits a bid drawn from a normal distribution with mean value equal to 2$/M b and derivation equal to 1$/M b. The maximum bandwidth of each AP is in the range of [5M bps, 40M bps], while the traffic demand of each MS is in the range of [2M bps, 10M bps]. The budget of MS is selected from the range of [10$, 20$]. We use the historical bidding information, i.e., µ j and δ j , to construct the uncertainty set U j , ∀j ∈ M. We assume that µ j and δ j are drawn randomly from the intervals [1$, 3$] and [1$, 2$], respectively. We consider the scenario with high conservativeness of historical valuations by setting Γ to 1. To compare the performance of two greedy schemes, we define I n m as n m , which is the ratio between the number of MSs and

Impact of AP Density in Homogeneous Networks

In order to evaluate the impact of AP density on the performance of our proposed mechanisms, we consider three levels of AP density, i.e., m is equal to 5, 10, and 20, respectively. Each AP's bandwidth is set to 30M bps. The simulation results are shown in Figs. 4.3, 4.4 and 4.5.

We first evaluate MNO's revenue for three levels of AP density, as shown in Figs. 4.3(a), 4.4(a) and 4.5(a), respectively. We observe that MNO's revenue increases with the number of MSs. The larger number of MSs, the higher competition MSs may have, and consequently MNO can choose MSs with higher bid values. Moreover, optimal scheme outperforms two greedy schemes and MDP scheme in all scenarios. We further observe that MatchingAP outperforms MatchingMS in low AP density scenario (see in Fig. 4.3(a)), while MatchingMS outperforms MatchingAP in high AP density scenario ((see in Fig. 4.5(a))). This is because MatchingAP can take advantage of the competition among MSs to obtain higher revenue. This observation can be further validated by Fig. 4.4(a), where MatchingAP achieves higher revenue than MatchingMS only when n > 32. Note that m = 10 in Fig. 4.4(a). Thus, we can obtain a threshold ratio when MatchingAP outperforms MatchingMS; that is I n * m = 3.2 in our settings. Since I n m ≥ 4 > I n * m in Fig. 4.3(a), MatchingAP achieves higher revenue than show that optimal scheme has the largest number of winning MSs; this indicates that optimal scheme can implement better fairness allocation among multiple MSs. Figure 4.5(b) illustrates that the number of winning MSs for all schemes increase linearly with the number of MSs. This is because high AP density implies enough bandwidth for traffic demand from MSs. However, it is not the same case for low AP density and medium AP density, where the total APs' bandwidth is not sufficient to support a large number of MSs. By comparing Figs. 4.5(a) and 4.5(b), we observe that MatchingMS achieves higher revenue than MatchingAP, even when two greedy schemes have the same number of winning MSs. This observation implies that two greedy schemes allocate bandwidth to different sets of MSs and MatchingMS can select the set of MSs with higher bid values in high AP density scenario.

We finally investigate how AP density affects the data offloading performance. We plot the offloaded traffic versus the number of MSs in Figs. 4.3(c), 4.4(c) and 4.5(c). We see that optimal scheme achieves the highest size of offloaded traffic and MDP scheme outperforms two greedy schemes, since MDP scheme aims to maximize the size of offloaded traffic. However, as illustrated in Figs. 4.3, 4.4 and 4.5, we observe that two greedy schemes achieve higher revenue than MDP scheme, even if MDP scheme can offload more data traffic. This is due to that MDP scheme does not take advantage of the competition of MSs to obtain revenue. Fig.

Impact of AP Bandwidth in Heterogeneous Networks

In order to evaluate the effect of AP bandwidth on the performance of our proposed schemes, we consider three levels of bandwidth C, namely low, medium and high, corresponding to 5, 25, and 40M bps, respectively. The number of MSs varies in the range of [START_REF] Quijano | The role of population games and evolutionary dynamics in distributed control systems: The advantages of evolutionary game theory[END_REF][START_REF] Zhuo | An incentive framework for cellular traffic offloading[END_REF] show the variation of revenue with the number of APs. We observe that the revenues of all schemes increase with the number of APs. As more APs participate in the auction, MNO has more bandwidth provided to MSs, leading to higher revenue. We find that optimal scheme outperforms the other schemes in all scenarios. MatchingMS achieves higher revenue than MatchingAP when AP bandwidth is low, as shown in Figure 4.6(a). Note that with low bandwidth 5 Mbps, each AP can serve one MS at most, since the minimum demand of MS is 3 Mbps. In this scenario, the final payment of winning MS is the same as its bid value, since the only bidder is the winning MS itself. According to the sorting rule of MatchingMS (see Algorithm 6), MS with a higher bid value has higher chance of winning the auction, resulting in a higher revenue. We summarize that the optimal scheme outperforms all other schemes in all scenarios. MatchingMS outperforms MatchingAP in the following two scenarios:

• High AP density: In this case, choosing MS with higher value generates higher revenue, since its demand can always be satisfied;

• Low AP bandwidth: This leads to a special case of data offloading, where one AP is connected to at most one MS at a time.

Impact of Budget Constraint

We evaluate the effect of budget constraint on the performance of our proposed schemes. We consider two scenarios based on whether the aggregate bandwidth of APs can satisfy the bandwidth demands of MSs or not. Fig. 4.9 shows the result when the aggregate bandwidth of APs is sufficient, i.e., m = 10, while Fig. 4.10 shows the result when the aggregate bandwidth of APs cannot satisfy all the demands from MSs, i.e., m = 5. We observe that the optimal method can obtain the highest revenue in all cases, as shown in Figs. 4.9(a) and 4.10(a). MatchingMS outperforms MatchingAP when the aggregate bandwidth of APs is sufficient, while MatchingAP outperforms MatchingMS when the aggregate bandwidth of APs is small.

In Fig. 4.9, we further observe that the total revenue increases with the value of budget. When B i ≥ 25, all MSs win the auction (see Fig. 4.9(b)) and bandwidth demands are satisfied (see Fig. 4.9(c)). Thus, the number of winning bidders and the offloaded traffic cannot increase with the value of budget when B i ≥ 25. However, the total revenue still increases when B i ≥ 25 (see Fig. 4.9(a)), since higher budget indicates higher valuation from MSs.

Fig. 4.10 shows the scenario where the total bandwidth demands of MSs is larger than the aggregate bandwidth of APs. As shown in Fig. 4.10(c), when B i ≥ 15, the offloaded traffic cannot increase the value of budget. This implies that all bandwidth of APs have been allocated. We observe that, when B i ≥ 15, the increase of budget leads to higher revenue (see Fig. 4.10(a)) and smaller number of winning bidders (see Fig. 4.10(b)). It is because where F j (.) and f j (.) are the cumulative distribution function and probability density function, respectively, of the probability distribution that the valuation v j is sampled from. Note that our method calculates the reservation price by solving the bilinear programming problem (4.10). Thus, the reservation prices obtained by Myerson auction are different from that calculated by our proposed method in most cases.

We consider a simple scenario where valuation v j follows the normal distribution with parameters µ * j = 3 and δ * j = 2, for all j ∈ M, where µ * j and δ * j are the practical expectation and deviation of the normal distribution, respectively. The number of APs is 10 and the number of MSs is 30.

We first investigate the revenue achieved by MNO when the assumed deviation δ j is different from the practical deviation δ * j . To evaluate the impact of different deviations, we choose δ j ∈ {0.5, 1, 1.5, 3, 4}. Fig. 4.11 shows the total revenue obtained by Myerson auction and our optimal scheme. The larger value of δ j , the lower revenue that the Myerson auction can obtain. For example, when δ j = 4, optimal scheme outperforms Myerson auction by 56%. This is because the reservation price used in Myerson auction depends on the assumed distribution. Thus, a misspecified (e.g., non-realistic) distribution reduces the performance of Myerson auction. Furthermore, our optimal scheme can achieve better performance due to its insensitivity to the assumed distribution.

We further evaluate how the assumed expectation µ j affects the total revenue when using the Myerson auction and our optimal scheme. Fig. 4.12 shows the total revenue obtained by Myerson auction and optimal scheme, when the value of µ j is chosen from {1.5, 2, 2.5, 4, 5}. We observe that both methods achieve good performance when µ j < µ * j . However, the situation changes when µ j > µ * j , e.g., µ j = 5, where both methods achieve lower revenue due to the misspecification of µ j .

We conclude that both Myerson auction and optimal scheme are sensitive to the misspecification of µ j . Furthermore, Myerson auction is sensitive to the misspecification of δ j , especially when δ j > δ * j , while optimal scheme is insensitive to the misspecification of δ j . Thus, optimal scheme has stronger robustness than Myerson auction when the deviation of normal distribution is misspecified.

Lastly, we evaluate the running time of the proposed schemes on an Intel (R) Core(TM) i7-2620M CPU 2.70GHz processor with RAM of 16.00 GB and 64-bit Linux operating system. We measure the running time (seconds) of different schemes with different numbers of APs and MSs. In Fig. 4.13, we observe that MatchingAP achieves the lowest running time in all cases. The running time of optimal scheme increases faster than the two other schemes with the number of APs and MSs. Note that when the number of APs is 100 and the number of MSs is 200, the running time of optimal scheme is 1.34 seconds, which is a reasonable value, since the auction is executed every ten seconds.

Conclusion

This chapter proposed a new trading marketplace where mobile operators can sell bandwidth made available by their own APs to offload data traffic of their MSs. The offloading problem was formulated as a multi-item auction based robust optimization approach to guarantee individual rationality, incentive capability and budget feasibility for realistic scenarios in which only part of the valuation information of MSs is known to MNO. In order to solve efficiently (i.e., in polynomial time) the offloading problem for large-scale network scenarios, we also proposed two greedy algorithms. Numerical results show that the proposed schemes capture well the economical and networking essence of the problem, thus representing a promising solution to implement a trading marketplace for next-generation access networks composed of heterogeneous systems.

Proof of the properties of the proposed auction mechanism

In this section, we present the proof that our proposed auction mechanism has the following properties in sequence, i.e., incentive compatibility (see Lemma 7), budget feasibility (see Lemma 8), individual rationality (see Lemma 9) and worst case optimality (see Lemma 10).

Lemma 6. If z and x * are the optimal solution of problem (4.10), then z and x * satisfy the following conditions:

j∈M x * ij • z ij ≤ B i , ∀i ∈ N , (4.18) i∈N x * ij ≤ C j , ∀j ∈ M, (4.19)
j∈M x * ij ≥ D i , ∀i ∈ N , (4.20)
j∈M x * ij • z ij ≤ j∈M x * ij • u ij , ∀u ∈ U, ∀i ∈ N . ( 4
U (v k ,v -k ) k ≥ U (u k ,v -k ) k
, which means that MS k gets higher utility with truthful bidding v k .

Proof. We assume that the private valuation for MS k is v k ∈ R m , and the private valuation for the rest (n -1) MSs is v -k ∈ R (n-1) × R m . Now if MS k chooses to bid with valuation u k ∈ R m instead of v k ; using Eq. ( 4.3), where the utility U

(u k ,v -k ) k
is the difference of payoff 4.7. Proof of the properties of the proposed auction mechanism 65 and payment, we obtain the utility of MS k as follows:

U (u k ,v -k ) k = j∈M a (u k ,v -k ) kj • v kj -p (u k ,v -k ) k . (4.23)
With the fact that

a v ij = x * ij + y v ij (
Step 14 in Optimal Algorithm) and Eq. (4.16), Eq. ( 4.24) can be rewritten as

U (u k ,v -k ) k = j∈M y (u k ,v -k ) kj • v kj + j∈M x * kj • v kj - j∈M y (u k ,v -k ) kj • r * kj - j∈M x * kj • r * kj - i∈N \{k} j∈M y v -k ij (v ij -r * ij ) + i∈N \{k} j∈M y (u k ,v -k ) ij (v ij -r * ij ). (4.24)
By substituting the following identical equation

i∈N j∈M y (u k ,v -k ) ij (v ij -r * ij ) ≡ j∈M y (u k ,v -k ) kj • v kj - j∈M y (u k ,v -k ) kj • r * kj + i∈N \{k} j∈M y (u k ,v -k ) ij (v ij -r * ij ), (4.25)
into Eq. (4.24) and some mathematical manipulations, we have

U (u k ,v -k ) k = j∈M x * kj • v kj - j∈M x * kj • r * kj - i∈N \{k} j∈M y v -k ij (v ij -r * ij ) + i∈N j∈M y (u k ,v -k ) ij (v ij -r * ij ). (4.26)
Similarly, we get the utility U

(v k ,v -k ) k
when MS k bid truthfully as follows:

U (v k ,v -k ) k = j∈M x * kj • v kj - j∈M x * kj • r * kj - i∈N \{k} j∈M y v -k ij (v ij -r * ij ) + i∈N j∈M y (v k ,v -k ) ij (v ij -r * ij ).
(4.27)

ỹv ij (v ij -r * ij ). (4.31)
Note that ỹv is a feasible solution to problem (4.15). That is, ỹv satisfies all the constraints of problem (4.15). From Eq. (4.15b), we obtain

i∈N ỹv ij ≤ C i - i∈N x * ij , ∀j ∈ M. (4.32)
From Eq. (4.15c), we obtain that ∀i ∈ N \ {k},

j∈M ỹv ij • v ij ≤ B i - j∈M x * ij • r * ij . (4.33) Note that j∈M ỹv kj • v kj = 0 ≤ B i - j∈M x * ij • r * ij . ( 4
ỹv ij • v ij ≤ B i - j∈M x * ij • r * ij , ∀i ∈ N . ( 4
ỹv ij (v ij -r * ij ) ≤ i∈N j∈M y v ij (v ij -r * ij ). (4.37)
By substituting Eq. ( 4.25) into Eq. (4.16), we have

p v k = j∈M y v kj • v kj + j∈M x * kj • r * kj + i∈N \{k} j∈M y v -k ij (v ij -r * ij ) - i∈N j∈M y v ij (v ij -r * ij ). (4.38)
By substituting Eq. ( 4.31) into Eq. (4.38), we have

p v k = j∈M y v kj • v kj + j∈M x * kj • r * kj + i∈N j∈M ỹv ij (v ij -r * ij ) - i∈N j∈M y v ij (v ij -r * ij ). (4.39)
Due to Eq. (4.37), we have

p v k ≤ j∈M y v kj • v kj + j∈M x * kj • r * kj . (4.40)
From Eq. (4.14c), we obtain that p v k ≤ B k .

Lemma 9. The proposed auction mechanism with final allocation matrix a v and payment vector p v , satisfy the property of individual rationality. That is, if MS k bids truthfully with valuation vector v k , it will get a nonnegative utility U

(v k ,v -k ) k ≥ 0.
Proof. By substituting Eq. (4.31) into Eq. (4.37), we obtain

i∈N \{k} j∈M y v -k ij (v ij -r * ij ) ≤ i∈N j∈M y v ij (v ij -r * ij ). ( 4
U (v k ,v -k ) k ≥ j∈M x * kj • v kj - j∈M x * kj • r * kj . (4.42)
From Lemma 6, we get

j∈M x * kj • v kj ≥ j∈M x * kj • z kj = j∈M x * kj • r * kj . ( 4
(v k ,v -k ) k ≥ 0.
Lemma 10. The proposed auction mechanism with final allocation matrix a z and payment vector p z , satisfies the property of worst case optimality. That is n k=1 p z k ≤ n k=1 p v k , which means that the revenue of MNO under valuation matrix z (obtained by Optimal Algorithm) is smaller than that under v ∈ U.

Proof. We first construct an allocation matrix ỹv ∈ R (n-1)×m based on y v ∈ R n×m , where

ỹv -k ij = y v ij , ∀i ∈ N \ {k}, ∀j ∈ M. (4.44)
Thus, we have the identical equation

i∈N \{k} j∈M y v ij (v ij -r * ij ) ≡ i∈N \{k} j∈M ỹv -k ij (v ij -r * ij ). (4.45)
In the following, we show that ỹv is a feasible solution to problem (4.14). From Eq. (4.14b), we obtain that ∀j ∈ M,

i∈N \{k} ỹv -k ij = i∈N \{k} y v ij ≤ C i - i∈N \{k} x * ij . (4.46)
From Eq. (4.14c), we obtain that ∀i ∈ N \ {k},

j∈M ỹv -k ij • v ij = j∈M y v ij • v ij ≤ B i - j∈M x * ij • r * ij . (4.47)
From Eq. (4.14d), we obtain that ∀i ∈ N \ {k}, With Lemmas 2 -5, we complete the proof of Theorem 3.

j∈M ỹv -k ij = j∈M y v ij ≤ D j - j∈M x * ij . ( 4
ỹv -k ij (v ij -r * ij ) ≤ i∈N \{k} j∈M y v -k ij (v ij -r * ij ). ( 4
y v ij (v ij -r * ij ) ≤ i∈N \{k} j∈M y v -k ij (v ij -r * ij ). ( 4

Chapter 5 Population Game Based Workload Balancing in Mobile Edge Computing

In this chapter, we propose a population game based approach to investigate workload balancing problem for MEC in IoT. Population game is envisioned as a powerful tool to model strategic interactions among large amounts of agents [START_REF] Barreiro-Gomez | Distributed population dynamics: Optimization and control applications[END_REF][START_REF] Quijano | The role of population games and evolutionary dynamics in distributed control systems: The advantages of evolutionary game theory[END_REF]. Specifically, we model the offloading decision making problem among large amounts of competing IoTDs as a population game, wherein IoTDs are self-interested agents and make offloading decisions individually. The main contributions of this chapter are summarized as follows:

• Population game model formulation: We formulate MEC workload balancing problem as a population game and propose an IoT Device classification model. We design an inference affected queueing model that can capture the inference among IoTDs. We use α-utility function to implement different kinds of workload balancing.

• Evolutionary game dynamics analysis: We calculate NE dynamically, i.e., IoTDs can change their offloading decisions through some learning mechanism. The learning mechanism is defined as a revision protocol that allows IoTDs to adjust their offloading decisions based on decisions of other IoTDs in proximity. The evolutionary process of IoTDs's offloading strategies can be modeled by evolutionary game dynamics (i.e., a differential equation). The evolutionary game dynamics describes the variation of IoTDs's offloading decisions until an NE is obtained.

• Workload balancing algorithms: We propose two workload balancing algorithms, namely centralized workload balancing algorithm and decentralized workload balancing algorithm, based on the concept of evolutionary dynamics and revision protocols, respectively. We show that these algorithms can achieve an NE. Simulation results illustrate the evolutionary dynamics and show that the proposed algorithms can achieve efficient workload balancing in BSs and edge clouds.

The remainder of this chapter is organized as follows. Section 5.1 introduces the system model of MEC workload balancing. Section 5.2 proposes α-utility based workload balancing model. Section 5.3 proposes two population game based workload balancing algorithms. Section 5.4 shows the evolutionary dynamics of three revision protocols and evaluate the performance of our proposed algorithms. Finally, we offer the conclusion in Section 5.5.

D

B C N C n C 1 D q1 B q1 D q2 B q2 D q3 B q3 D q4 B q4

System Model

We consider a cellular network consisting of a set M = {1, 2, • • • , M } of BSs. We denote IoTDs within the coverage area of these BSs by a set Q = {1, 2, • • • , Q}. Note that each IoTD can only offload mobile tasks to BSs in proximity. The set M q , ∀q ∈ Q denotes the available BSs that can execute tasks for IoTD q. Thus, we decompose the set Q into a finite number of classes N = {1, 2, • • • , N }. IoTDs who can offload tasks to the same set of BSs belong to the same class, since they have the same offloading strategies. For example, if IoTD p1 and IoTD p2 belong to class Q n , n ∈ N , then M q1 = M q2 . For simplicity, we use M n to denote the available BSs for all IoTDs in class n. The number of IoTDs in class n is denoted by Z n ; thus, n∈N Z n = Q. Each IoTD makes the offloading decision based on the network information and task information (that will be explained later). We first define the class state as a distribution of the number of IoTDs choosing different BSs, denoted by

a n = [a n 1 , • • • , a n M n ],
where a n m , m ∈ M n represents the number of IoTDs in class n choosing remote execution in BS m. Note that m∈M n a n m = Z n . Then, we can represent the population state (the offloading decisions of all IoTDs) with the class states, i.e., the population state a = [a 1 , • • • , a N ] is a Cartesian product of all class states.

IoT Device Classification

We classify IoTDs into different classes according to their locations and task-related data. The location of IoTD q is denoted by L(q), where L(q) ∈ R 2 is a plane coordinate. The task of IoTD q is denoted by J q (B q , D q ), where B q represents size of data including computational input data and execution codes. D q denotes the required CPU cycles to execute task J q . Note that IoTDs located in the same place have similar network environment (e.g., network traffic and link capacity). We consider that IoTDs with the same ratio of Dq Bq belong to a same class, i.e., Q n = {q ∈ Q| Dq Bq = C n and L(q) = L n }. Q n represents the set of IoTDs in class n. C n and L n , capture the characteristics of class n, represent the computational density per unit size of data and the location of class n, respectively. As illustrated in Fig. 5.2, all IoTDs in a same class fall in a same line and the slope of the line denotes the computational density of the class.

Population game requires that all IoTDs coming from the same class are homogeneous. Previous classification cannot preserve this property, since two IoTDs may have different data size even if they are in a same class. In order to solve this problem, we need to reconsider IoTDs' tasks and recalculate the class size. The basic idea is to divide the larger data size (and CPU cycles) into a number of minimum data size (and CPU cycles). We first select the IoTD with minimum data size (and corresponding minimum CPU cycles) in a class as a benchmark, denoted as minIoT D. Then, we consider that all the other IoTDs are composed of multiple minIoT Ds. For example, if q1 is minIoT D of class n and B q2 = 2B q1 , then q2 can be replaced by 2 minIoT Ds. Since all IoTDs in a class is replaced by minIoTDs, the homogeneous property is preserved. We can recalculate the class size and population size as follows:

Ẑn = q∈Qn B q B n min , Q = n∈N Ẑn , (5.1)
where B n min = min q∈Qn B q is the data size of minIoT D in class n. Ẑn and Q denote the class size and population size after replacement, respectively. Note that Ẑn may not be integer while Z n is integer. Unless otherwise specified, we will use this new population model in the following discussion.

Task Execution Model

Tasks generated by IoTDs will be transferred to a BS and then executed in the corresponding edge cloud, as shown in Fig. 5.3. We assume that IoTDs in class n generate tasks according to a Poisson Point Process with rate λ n . We further assume that the data size and CPU cycles of class n follow the exponential distributions with average values of B n and D n , respectively. Note that B n and D n correspond to the data size and CPU cycles of minIoT D of class n. We define the traffic generation density of an IoTD in class n as θ n = λ n B n . Thus, the traffic generation density of class n is denoted by θ n = Ẑn θ n , which is simply the multiplication of the number of IoTDs and the traffic generation density of an IoTD in class n. Similarly, we can define the computation generation density of an IoTD in class n as η n = λ n D n .

We first introduce the communication model between IoTDs in class n and BS m. We consider that IoTDs in the same class have the same data rate, while IoTDs in different classes can have different data rates. The data rate between an IoTD in class n and BS m is defined as follows:

R n m (a) = W m a n m log 2 1 + a n m P n l H n m δ + k∈N n m a k m P k l H k m , (5.2)
where

N n m = k ∈ N \ {n} : m ∈ M k , a n m = 0.
W m denotes the total bandwidth of BS m. P n l and P k l represent the average transmission power of IoTDs in class n and class k, respectively. H n m and H k m are the average channel gain between BS m and IoTDs in class n and class k, respectively. We use δ to denote the noise power. The interference from other classes is k∈N n m a k m P k l H k m , where N n m denotes the set of classes whose available BSs including BS m; thus these classes may generate interference to BS m. We don't consider the interference among IoTDs in a same class, since these IoTDs (or minIoT Ds ) are identical and may come from a single IoTD. If no IoTDs in class n selects BS m, i.e., a n m = 0, there is no need to calculate R n m (a). Thus, we assume that a n m = 0 in Eq. (5.2). The traffic load density of BS m serving class n is defined as

Ṫ n m (a) = θ n R n m (a)
, and denotes the time fraction of BS m serving class n. The utilization of BS m is the aggregation of system load density of BS m serving class n, which is defined as

ρm (a) = n∈N Ṫ n m (a)a n m = n∈N θ n a n m R n m (a) = n∈N θ n (a n m ) 2 W m log 2 1 + a n m P n l H n m δ+ k∈N n m a k m P k l H k m . (5.3)
We then introduce the computation model when offloading tasks of class n to edge cloud m.

The computation load density of edge cloud m (connected to BS m) serving class n is defined as T n m = η n Fm , where F m is the computational capability (in CPU cycles/second) of edge cloud m. T n m represents the time fraction of edge cloud m serving class n. The utilization of edge cloud m is the aggregation of system load density of edge cloud m serving class n, which is defined as

ρm = n∈N T n m a n m = n∈N η n a n m F m . (5.4)

Workload Balancing Model

The utilization levels of BS m and edge cloud m are described by ρm (a) and ρm , respectively. In order to implement different load balancing for BSs and edge clouds, we take advantage of α-fair utility function [START_REF] Kim | Distributed α-optimal user association and cell load balancing in wireless networks[END_REF] that we will maximize as follows:

T(α, ρ) =            - m∈M (1 -ρ m ) 1-α -1 α -1 , α = 1, - m∈M ln 1 1 -ρ m , α = 1, (5.5)
where ρ = {ρ m } m∈M denotes the utilization status of BSs (when ρ m = ρm (a)) or edge clouds (when ρ m = ρm ). The load balancing factor α can have four different values resulting in four load balancing policies. For example, if α = 0, then T(α, ρ) = m∈M ρ m . The offloading decision is only based on IoTDs' perspective and this policy is called rate-optimal policy. If α = 2, then T(α, ρ) = -m∈M ρm 1-ρm . Note that ρm 1-ρm can represent the length of queue in BS m or edge cloud m. The negative sign is used to maximize α-fair utility function, since we aim to minimize the total length of queue m∈M ρm 1-ρm . When α = 2, T(α, ρ) is called delay-optimal policy. Moreover, α = 1 and α = ∞ denote throughput-optimal policy and equalizing-load policy, respectively [START_REF] Kim | Distributed α-optimal user association and cell load balancing in wireless networks[END_REF]. Paper [START_REF] Guo | α-Fair Power Allocation in Spectrum-Sharing Networks[END_REF] shows that α ≥ 0 can take more values except for the above cases. Thus, we can implement many kinds of load balancing in BSs and edge clouds by using different values of α.

Population Game Based Workload Balancing

In this section, we first propose a social welfare maximization problem that can implement efficient load balancing in BSs and edge clouds. Then, we define the payoff function of population game and introduce three basic evolutionary dynamics that can capture the evolution of population state.

Social Welfare Maximization

Our social welfare maximization aims to jointly implement load balancing in BSs and edge clouds and is defined as follows:

max T( α, α, ρ(a), ρ) = T( α, ρ(a)) + ξT(α, ρ) (5.6) s.t. ρm (a) < 1 ∀m ∈ M (5.7) ρm < 1 ∀m ∈ M (5.8) m∈M n a n m = Ẑn ∀n ∈ N . (5.9)
The α-fair utility function for BSs is denoted by T( α, ( ρ)(a)). By replacing the input parameters of Eq. (5.5), we obtain that

T( α, ρ(a)) =            - m∈M (1 -ρm (a)) 1-α -1 α -1 , α = 1, - m∈M ln 1 1 -ρm (a) , α = 1.
(5.10)

Similarly, we can obtain the α-fair utility function for edge clouds as follows:

T(α, ρ) =            - m∈M (1 -ρm ) 1-α -1 α -1 , α = 1, - m∈M ln 1 1 -ρm , α = 1.
(

Since we jointly optimize the load balancing for BSs and edge clouds, ξ > 0 is a trade off of these two objectives. Larger ξ implies higher priority in load balancing for edge clouds.

Constraints (5.7) and (5.8) indicate that the utilization of BSs and edge clouds can not exceed the maximum bandwidth and computational capability, respectively. Constraint (5.9) requires that the number of IoTDs in a class remains stable. Instead of solving this optimization problem directly, we propose a population game based method to solve the load balancing problem.

Population Game Formulation

In order to solve the optimization problem (5.6), we describe IoTDs' offloading decisions (choosing appropriate BSs) as a population state a. The core of population game is the socalled payoff function. Payoff function defines IoTDs' payoffs based on a population state and is composed of a collection of marginal payoff functions, i.e., F (a) = {F n m (a) : m ∈ M n , n ∈ N }, F n m (a) is defined as follows:

F n m (a) = -   η n ξ F m (1 -ρm ) α + θ n 2 -g( SIN R n m ) R n m (a)(1 -ρm (a)) α   , (5.12)
where,

g( SIN R n m ) = SIN R n m ( SIN R n m + 1) ln( SIN R n m + 1) , (5.13)
SIN R n m = a n m P n l H n m δ + k∈N n m a k m P k l H k m . (5.14)
SIN R n m denotes the Signal-to-Interference-plus-Noise Ratio and g( SIN R n m ) represents the effect of SIN R n m on load balancing. To better understanding the definition of F n m (a), we consider one simple case where α = α = 0. In this case,

F n m (a) = -   η n ξ F m + θ n 2 -g( SIN R n m ) R n m (a)   . Recall that Ṫ n m (a) = θ n R n m (a)
denotes the time fraction of BS m serving class n and T n m = η n Fm is the time fraction of edge cloud m serving class n (see Section 5.1.2). We further obtain that

F n m (a) = -ξ T n m + Ṫ n m (a) 2 -g( SIN R n m ) ,
which has a similar structure of Eq. (5.6) except that the effect of SINR is obvious now.

F n m (a) is the payoff of IoTDs from class n choosing BS and edge cloud m (or the payoff of a n m ). We can see that the time for transmission is affected by SINR and the load of BSs and edge clouds is not considered in this case. When α > 0 and α > 0, the load of BSs and edge clouds will affect the payoff of IoTDS, since ρm and ρm (a) will be reserved in payoff function.

Moreover, we propose the following theorem to analyze the effect of 2g( SIN R n m ) in payoff function.

Theorem 4. Time fraction T n m (a) = θ n R n m (a) 2 -g( SIN R n m ) increases from θ n R n m (a) to 2θ n R n m (a) , when SIN R n m increases from 0 to +∞. Theorem 4 implies that when SIN R n m = 0, T n m (a) = Ṫ n m (a). As SIN R n m increases, time fraction T n m (
a) increases. This is because higher SIN R n m implies higher data rate from IoTDs in class n; thus resulting in higher bandwidth utilization of BS m. However, T n m (a) should be less than 2θ n R n m (a) , even if the transmission power is much larger than inference and noise power. The proof of Theorem 1 is given in Section 5.6. Potential game always has an NE and the finite improvement property. The proof of Theorem 5 is given in Section 5.7.

Evolutionary Dynamics

NE is the solution concept of population game. By using the framework of evolutionary dynamics [START_REF] William | Population games and deterministic evolutionary dynamics[END_REF], we can analyze how population state evolves in time and converges to NE. The evolutionary dynamics is defined as follows:

ȧ n m = k∈M n a n k ρ n km (a, F (a)) -a n m k∈M n ρ n mk (a, F (a)). (5.15)
ρ n km (a, F (a)), called revision protocol, represents the switch rate of IoTDs in class n changing offloading decision from BS k to BS m based on population state a and payoff function F (a). Larger value of ρ n km (a, F (a)) implies higher probability that IoTDs in class n changing offloading decision from BS k to BS m. The first term and second term of Eq. (5.15) denote the inflow rate of IoTDs choosing BS m and the outflow rate of IoTDs choosing any BS except for BS m, respectively. Thus, the difference of inflow rate and outflow rate describes the evolution of a n m . We consider three types of revision protocols, namely Smith, Logit and BNN [START_REF] Quijano | The role of population games and evolutionary dynamics in distributed control systems: The advantages of evolutionary game theory[END_REF][START_REF] William | Population games and deterministic evolutionary dynamics[END_REF]. For simplicity, we use IoT D n m to represent an IoTD in class n choosing BS m. Thus, a n m is the number of IoT D n m s. The function [x] + returns x if x ≥ 0. Otherwise, it returns 0. Smith protocol, defined in Eq. (5.16), describes that the switch rate of IoT D n k changing current offloading decision from BS k to BS m is the payoff difference between m and k. For example, if IoT D n k knows that IoT D n m has higher payoff, i.e., BS m is a better choice than BS k for class n, then IoT D n k will change his offloading decision to BS m with switch rate ρ n km (a, F (a)). IoT D n k will not change his offloading decision if IoT D n m has lower payoff.

ρ n km (a, F (a)) = [F n m (a) -F n k (a)] + . (5.16)
Logit protocol is defined in Eq. (5.17), where ω > 0 is the noise level. ω represents the rationality of IoTDs. For ω = 0, IoTDs are completely rational and choose the best offloading decision. As ω increases, IoTDs become less rational and may choose non-optimal decision.

ρ n km (a, F (a)) = exp (ω -1 F n m (a)) k∈M n exp (ω -1 F n k (a))
.

(5.17)

Workload Balancing Algorithms

79

BNN protocol, defined in Eq. (5.18), describes that IoT D n k compares IoT D n m 's payoff with the average payoff of class n. If IoT D n m 's payoff exceeds the average payoff, then IoT D n k will change his offloading decision to m with switch rate ρ n km (a, F (a)).

ρ n km (a, F (a)) = F n m (a) - 1 Ẑn l∈M n a n l F n l (a) + . (5.18)
Note that these protocols describe how IoTDs change their offloading decisions until an NE is reached. Smith uses less decision information compared to Logit and BNN. Smith needs only the payoff of one BS, while Logit and BNN need the payoffs of all BSs in M n . However, this leads to Smith has lower convergence speed than Logit and BNN. By substituting these revision protocols into Eq. ( 5.15), we can get Smith dynamics, Logit dynamics and BNN dynamics in Eqs. (5.19), (5.20) and (5.21), respectively.

ȧ n m = k∈M n a n k [F n m (a) -F n k (a)] + -a n m k∈M n [F n k (a) -F n m (a)] + . (5.19)
ȧ n m = a n m exp (ω -1 F n m (a)) k∈M n a n k exp (ω -1 F n k (a)) -a n m . (5.20)
ȧ n m = F n m (a) + - a n m Ẑn k∈M n F n k (a) + , (5.21)
where

F n m (a) = F n m (a) - 1 Ẑn l∈M n a n l F n l (a).
These evolutionary dynamics can generate an NE in iteration methods. We will propose a load balancing algorithm based on evolutionary dynamics in next section.

Workload Balancing Algorithms

In this section, we will proposes two workload balancing algorithms, namely, CWB (Centralized Workload Balancing) algorithm and DWB (Decentralized Workload Balancing) algorithm. CWB is based on the evolutionary dynamics and DWB is based on Theorem 5.

Centralized Workload Balancing

Our CWB algorithm consists of two phases. The first phase (Steps 1 -10 ) is to calculate an NE based on evolutionary dynamics. Smith, Logit and BNN dynamics can converge to an NE with different converge speed (as shown in Section). However, the resulting NE only shows how many IoTDs in class n will choose BS m, i.e., a n m , without specifying which IoTD in class n will choose BS m. Thus, we use the second phase (Steps 11 -23 ) to implement the IoTDs' offloading decisions. The main idea to randomly select IoTDs from class n for BS m; the number of IoTDs should be no more than a n m . The randomness of selection can implement fair offloading decisions for IoTDs. Note that we need to replace minIoT Ds with original IoTD when calculating offloading decisions (see Steps 18 -20 ).

Algorithm 7 CWB (Centralized Workload Balancing)

Phase 1: Calculate an NE. 1: Initialize a with arbitrary value satisfying Constraint (5.9) 2: a ← 0 3: while a = a do end for 23: end for

while Q = ∅ ∧ a > 0 do 17: i ← N ext(Q) 18: if B i B n min ≤ a then 19: a ← a -B i B n min , Q ← Q \ {i}, A(i) ← m

Decentralized Workload Balancing

Our DWB algorithm is a distributed algorithm consisting of two parts of algorithms running in IoTDs and BSs separately. Each IoTD can change his current offloading decision whenever "stochastic update clock" rings. IoTD randomly chooses several candidate BSs and choose the BS with highest switch rate. IoTD only changes his offloading decision when the highest switch rate is positive; implying higher payoff. With the property of potential game, any better update of offloading decision is guaranteed to reach an NE. Note that IoTD's algorithm (Part 1 in Algorithm 8) does not exactly follow the switch rates of Smith, Logit and BNN protocols. However, it captures the main features of these revision protocols: 1) randomness is ensured by Step 2, K can be any value between 1 and M n , we choose K = M n 2 ; 2) higher switch rate implying higher probability of changing offloading decision is guaranteed by Steps 3 -9. BS's algorithm (Part 2 in Algorithm 8) is to first collect current IoTDs' offloading decisions and then broadcast the utilization level of BSs and edge clouds to IoTDs. IoTDs will use these information to improve their offloading decisions. Calculate ρm and ρm by Eqs. (5.3) and (5.4), respectively.

14:

Broadcast ρm and ρm to IoTDs within coverage of BS m 15: end for

Performance Evaluation

In this section, we evaluate the performance of our proposed workload balancing algorithms by numerical studies. We compare our work with other two contributions: BRUTE [START_REF] Moon | Brute: Energy-efficient user association in cellular networks from population game perspective[END_REF] and TWB (Towards Workload Balancing) [START_REF] Fan | Towards workload balancing in fog computing empowered IoT[END_REF]. BRUTE uses αfair function to implement energy-efficient traffic allocation among BSs. BRUTE considers the energy consumption in BSs without considering the load in edge clouds. TWB considers the traffic load in BSs and computation load in edge clouds. However, none of them considers the effect of SINR in load balancing.

Without loss of generality, we consider the scenario where 400 IoTDs compete for the communication resources of 3 BSs and computation resources in 3 edge clouds. We randomly select the parameter's value from the normal distribution for different cases. The average value of these parameters are illustrated as follows [START_REF] Xu | Decentralized computation offloading game for mobile cloud computing[END_REF][START_REF] Meskar | Energy aware offloading for competing users on a shared communication channel[END_REF][START_REF] Liu | Data offloading in mobile cloud computing: A Markov Decision Process approach[END_REF][START_REF] Deng | Computation Offloading for Service Workflow in Mobile Cloud Computing[END_REF]. The data size B n is set to 800KB and the number of required CPU cycles D n is set to 1000M egacycles. We set the allocated computational capability F n m to 100GHz and the bandwidth of BS to 5M Hz. The channel gain between IoTD n and BS m is

H n m = (d m n ) -θ
, where θ is the pass loss factor and d m n is the distance between them. θ is set to 4 and H n m is randomly selected from [5m -100m] [109]. The wireless transmission power P n l is set to 100mW atts.

Illustration of Evolutionary Dynamics

We first compare the evolutionary dynamics of Smith, Logit and BNN. We observe that Smith converges more slowly than Logit and BNN, as shown in Figs. 5.4, 5.5 and 5.6. We also observe that the arrows of Smith approach the NE in a less angular, more gradual fashion. This is because that Smith changes its offloading decision based on the payoff of one BS, while BNN and Logit change the offloading decision based on all the payoff of BSs.

Generally, using more payoff information to make offloading decisions can achieve better performance. Thus, BNN and Logit converge faster than Smith. Moreover, these three evolutionary dynamics can achieve the same NE.

Then, we investigate the resulting NE, i.e., the percentage of IoTDs choosing three BSs, denoted by black point in the figures. Note that the distance between black point and the vertex of triangle denotes the percentage of IoTDs choosing the corresponding BS; smaller distance represents higher percentage. The NE is (0.35, 0.45, 0.20) in our settings. We observe that the NE is located close to BS 2 (i.e., the black point is close to vertex 2). This is because BS 2 and edge cloud 2 have the highest communication and computation capabilities in our settings. Consequently, more IoTDs prefer to offload tasks to BS 2.

Comparison of Different Algorithms

To investigate the performance of workload balancing of different algorithms, we consider a scenario where 1000 IoTDs compete for communication and computation resources of 5 BSedge-cloud pairs. Fig. 5.7 shows that CWB and DWB achieve better performance than TWB and BRUTE in traffic load balancing. We observe that the difference of traffic load among 5 BSs achieved by CWB and DWB are smaller than those achieved by TWB and BRUTE. This is because CWB and DWB use inference affected queueing model where SINR dynamically changes with population state, while TWB and BRUTE use static SINR model where SINR is estimated as location-dependent static value. We further observe that BRUTE achieves higher performance for traffic load balancing than TWB, since BRUTE does not consider the computation load balancing in edge clouds. Thus, BRUTE does not need to sacrifice the load balancing among BSs to implement load balancing among edge clouds. Fig. 5.8 shows the computation load among edge clouds. We observe that CWB and DWB achieve better performance than TWB and BRUTE in computation load balancing. This is because TWB and BRUTE do not consider the affect of dynamic inference among IoTDs. Furthermore, BRUTE achieves worst performance without considering the computation load balancing in edge clouds.

Conclusion

In this chapter, we analyze the workload balancing problem for MEC in IoT. IoTDs can offload computation intensive tasks to nearby BSs. We propose a population game based approach to investigate this problem and show that the game always has an NE. We consider two kinds of revision protocols, namely, Replicator and BNN. Numerical results illustrate the evolutionary dynamics of the revision protocols and demonstrate the validation of our offloading mechanism.

Proof of Theorem 1

Proof. In order to proof Theorem 1, we need investigate the properties of inference function g( SIN R n m ).

Inference Function is a Monotonic Function

We first calculate the derivative of g( SIN R n m ) with respect to SIN R n m as follows:

g ( SIN R n m ) = ( SIN R n m + 1) ln( SIN R n m + 1) ( SIN R n m + 1) 2 ln 2 ( SIN R n m + 1) - SIN R n m (ln( SIN R n m + 1) + 1) ( SIN R n m + 1) 2 ln 2 ( SIN R n m + 1) (5.22)
= ln( SIN R n m + 1) -SIN R n m ( SIN R n m + 1) 2 ln 2 ( SIN R n m + 1)
.

(5.23)

Note that the domain of

g( SIN R n m ) is { SIN R n m ∈ R| SIN R n m > 0}, since g( SIN R n m
) has no definition when SIN R n m = 0. We will discuss the case where SIN R n m = 0 later. Obviously, ln( SIN R n m + 1) -SIN R n m < 0 for all SIN R n m > 0. According to Eq. (5.23), we know that g ( SIN R n m ) < 0. Thus, g( SIN R n m ) is a strictly decreasing function.

The Limit of Inference Function

We next consider the value of

lim SIN R n m →0 g( SIN R n m ). lim SIN R n m →0 g( SIN R n m ) (5.24) = lim SIN R n m →0 SIN R n m ( SIN R n m + 1) ln( SIN R n m + 1) (5.25) = lim SIN R n m →0 SIN R n m ln( SIN R n m + 1) lim SIN R n m →0 1 SIN R n m + 1 (5.26) = lim SIN R n m →0 SIN R n m ln( SIN R n m + 1)
(Applying l'Hopital's rule) (5.27)

= lim SIN R n m →0 d d SIN R n m ( SIN R n m ) d d SIN R n m (ln( SIN R n m + 1)) (5.28) = lim SIN R n m →0 ( SIN R n m + 1) (5.29) = 1. (5.30)
Without causing ambiguity, we say that g( SIN R n m ) = 1, when SIN R n m = 0.

The Range of Inference Function

Since g( SIN R n m ) is strictly decreasing and g(0) = 1, we know that

max SIN R n m ≥0 g( SIN R n m ) = g(0) = 1. (5.31)
Moreover, it is easy to verify that g( SIN R n m ) > 0 for all SIN R n m ≥ 0 and lim SIN R n m →+∞ g( SIN R n m ) = 0. Thus, the range of

g( SIN R n m ) is [0, 1].
Based on the above discussions, we know that g( SIN R n m ) decreases from 1 to 0 when SIN R n m increases from 0 to +∞. Thus, 2g( SIN R n m ) increases from 1 to 2 when SIN R n m increases from 0 to +∞. Finally, time fraction

T n m (a) = θ n R n m (a) 2 -g( SIN R n m ) increases from θ n R n m (a) to 2θ n R n m (a)
, when SIN R n m increases from 0 to +∞.

Proof of Theorem 2

In order to prove that T( α, α, ρ(a), ρ) is the potential function of population game F (a), we need to derive that (5.32)

Partial Derivatives of Load Balancing in Edge Clouds

We first calculate the partial derivatives of T(α, ρ) in two cases based on the value of α.

Case 1: α = 1,

∂T(α, ρ) ∂a n m = ∂ ∂a n m - m∈M (1 -ρm ) 1-α -1 α -1 (5.33) = 1 - α (α -1)(1 -ρm ) α • ∂ ρm ∂a n m (5.34) = -η n F m (1 -ρm ) α . (5.35)
Based on Eq. (5.11), we have Eq. (5.33). According to Eq. ( 5.4), we can obtain that ∂ ρm

∂a n m = η n
Fm . Thus, we can get Eq. (5.35) from Eq. (5.34). Similarly, we can calculate the partial derivatives of T(α, ρ) when α = 1.

Case 2: α = 1, ∂T(α, ρ) ∂a n m = ∂ ∂a n m - m∈M ln 1 1 -ρm (5.36) = 1 -ρm (1 -ρm ) 2 • -∂ ρm ∂a n m (5.37) = -η n F m (1 -ρm ) . (5.38)
Note that Eq. (5.38) is equal to Eq. (5.35) when α = 1. Thus, we can say that

∂T(α, ρ) ∂a n m = -η n F m (1 -ρm )
α , ∀α ≥ 0.

(5.39)

Partial Derivatives of Load Balancing in BSs

We next calculate the partial derivatives of T( α, ρ(a)) based on different values of α.

∂ ρm (a) (5.49)

∂a n m = ∂ ∂a n m       n∈N θ n (a n m ) 2 W m log 2 1 + a n m P n l H n m δ+ k∈N n m a k m P k l H k m       = θ n ln(2) W m • ∂ ∂a n m       (a n m ) 2 ln 1 + a n m P n l H n m δ+ k∈N n m a k m P k l H k m       (5.40) = θ n ln(2)       2a n m ln a n m P n l H n m k∈N n m a k m P k l H k m + δ + 1 - (a n m ) 2 P n l H n m ( k∈N n m a k m P k l H k m + δ) a n m P n l H n m k∈N n m a k m P k l H k m + δ + 1       W m ln 2 a n m P n l H n m k∈N n m a k m P k l H k m + δ + 1 (5.41) = θ n       2a n m log 2 a n m P n l H n m k∈N n m a k m P k l H k m + δ + 1 - (a n m ) 2 P n l H n m ln(2)( k∈N n m a k m P k l H k m + δ) a n m P n l H n m k∈N n m a k m P k l H k m + δ + 1       W m log 2 2 a n m P n l H n m k∈N n m a k m P k l H k m + δ + 1 . ( 5

Partial Derivatives of the Untilization of BSs

The partial derivatives ∂ ρm(a)

∂a n m are calculated as follows. Eq. (5.40) is the result of replacing ρm (a) with Eq. (5.3). By using derivative rules, we get Eq. (5.41) from Eq. (5.40). With some basic mathematical manipulation, we rewrite Eq. (5.41) as Eq. (5.42)

= θ n 2 -g( SIN R n m ) R n m (a)
.

(5.54)

Finally, we can obtain the partial derivatives of T( α, α, ρ(a), ρ) as follows:

∂T( α, α, ρ(a), ρ) ∂a n m = ξ • ∂T(α, ρ) ∂a n m + ∂T( α, ρ(a)) ∂a n m (5.55) = -η n ξ F m (1 -ρm ) α + -1 (1 -ρm (a)) α • θ n 2 -g( SIN R n m ) R n m (a) (5.56) = -   η n ξ F m (1 -ρm ) α + θ n 2 -g( SIN R n m ) R n m (

Chapter 6

Conclusions and Future Work

Conclusions

In this thesis, we presented the research background, the state of the art and three contibutions for the doctoral thesis entitled Mobile data and computation offloading in mobile cloud computing. The first two contributions are related to mobile data offloading, while the third contribution is related to mobile computation offloading.

In the first contribution, we study mobile data offloading problem under the architecture of mobile cloud computing, where mobile data can be delivered by WiFi network and deviceto-device communication. In order to minimize the overall cost for data delivery task, it is crucial to reduce cellular network usage while satisfying delay requirements. In our proposed model, we formulate the data offloading task as a finite horizon Markov Decision Process. We first propose a hybrid offloading algorithm for mobile data with different delay requirements. Moreover, we establish the sufficient conditions for the existence of threshold policy. Then, we propose a monotone offloading algorithm based on threshold policy in order to reduce the computational complexity. The simulation results show that the proposed offloading approach can achieve minimal communication cost compared with other three offloading schemes.

In the second contribution, we consider a mobile data offloading market where mobile network operator (MNO) can sell bandwidth made available by the access points to increase MNO's profit. We formulate the offloading problem as a multi-item auction and study MNO's profit maximization problem. We discuss the conditions to (i) offload the maximum amount of data traffic, (ii) foster the participation of mobile subscribers (MSs) (individual rationality), (iii) prevent market manipulation (incentive compatibility) and (iv) preserve budget feasibility of MSs. Then, we propose a robust optimization based method to implement multi-item auction mechanism. We further propose two iterative algorithms that efficiently solve the offloading problem. The simulation results show the efficiency and robustness of our proposed methods for cellular data offloading.

In the third contribution, we investigate the workload balancing problems to minimize the transmission latency and computation latency in task offloading process while considering the limited bandwidth resources of BSs and computation resources in edge clouds. We formulate the workload balancing problem as a population game in order to analyze the aggregate offloading decisions. We analyze the aggregate offloading decisions of mobile users Chapter 6. Conclusions and Future Work through evolutionary game dynamics and show that the game always admits a Nash equilibrium (NE). We further propose two workload balancing algorithms based on evolutionary dynamics and revision protocols. Simulation results show that our proposed workload balancing algorithms can achieve better performance than other two works.

Future Work

Distributed Algorithms for Offloading Decision Making

Current computation offloading models use lots of information, e.g., profiles of mobile devices, states of cloud servers, and network conditions, to make offloading decision. The more information they use, the better offloading decision they make. However, managing too much information may increase the overhead of offloading decision making, which may offset the benefits of offloading computation intensive tasks. To solve this problem, the overhead of these offloading decision methods needs to be analyzed. One of the possible method is to decrease the overhead by ignoring trivial information. To reduce the overhead of mobile devices, we can further offload the task of offloading decision making from mobile devices to trusted cloud servers or edge clouds. In the future, we will consider a distributed offloading model where offloading decision algorithms are implemented between mobile devices and cloud/edge servers.

Failure Recovery and Admission Control for Computation Offloading

We will consider the situation where the edge cloud can also decide whether to accept an offloading request or not. Since the number of mobile devices is much greater than the number of edge clouds, one edge cloud may receive too many offloading requests from nearby mobile devices. However, one edge cloud may overflow if too many offloading requests are sent to it. One possible solution is to choose the mobile tasks with higher priority. Some offloading requests may be refused because of the limited computation and storage resources in edge clouds, which is different from offloading to cloud servers, where there are virtually unlimited computing and storage resources. The offloading requests will always be accepted. Due to the uncertain wireless environment, we will propose new methods to deal with offloading failure.

Programming Model for Mobile Cloud Computing

Programming model can remove the burden of distributed execution details from programmers by providing simple interfaces. Programmers can use these interfaces to pay more attention to implement the main logic of an application without caring about the detailed implementation of distributed execution.

Although simple interfaces may result in some algorithms hard to be implemented, the programming model can greatly improve the software productivity. Traditional programming model only executes tasks in cloud servers and does not support the tasks running in mobile devices. This restricts programming models, such as MapReduce, to be implemented in mobile cloud computing directly. Many researches adapted MapReduce from clusters to other architecture, such as GPUs and FPGA. This may result in some problems when we adopt programming models in cloud computing to mobile cloud computing due to the mobility of mobile devices and the unbalance architecture.

We plan to design a new programming model for mobile cloud computing. The purpose of this work is to improve the service of quality in mobile cloud computing by extending the concept of programming model from cloud computing to mobile cloud computing. As a by-product, we can improve the overall performance of mobile devices and cloud servers.

There are many problems to solve in order to achieve this goal.

Chapter 7

Résumé en Français

Dans ce chapitre, nous présenterons brièvement le travail de thèse en français. MDO consiste à utiliser des technologies de réseau complémentaires et des techniques innovantes pour la fourniture de données initialement ciblées pour les réseaux cellulaires afin de réduire la congestion et de mieux utiliser les ressources de réseau disponibles. L'objectif est de maintenir la qualité de service pour les clients et de réduire le coût des services sur le réseau sans fil. MDO deviendra une technique clé dans l'industrie, car le trafic de données sur les réseaux mobiles continue à augmenter rapidement.

Introduction

Cloud

Cellular BS MS

MDP Pour MDO

Dans cette section, nous proposons deux systèmes de transfert de données mobiles basés sur le processus de décision finie à horizon de Markov (FHMDP). Notre objectif est de minimiser les coûts de communication liés à la transmission de données mobiles avec contraintes de délai via plusieurs réseaux sans fil, c'est-à-dire un réseau cellulaire, un réseau WiFi et la communication D2D. Les principales contributions de cette section peuvent être résumées comme suit:

• Nous proposons un modèle hybride de déchargement, dans lequel plusieurs réseaux sans fil sont utilisés pour transférer des données mobiles. MNO peut minimiser le coût total de la communication en sélectionnant différents réseaux.

• Nous formulons les données du problème de déchargement dans les réseaux sans fil hybrides sous la forme d'un modèle FHMDP, et proposons un algorithme de déchargement qui peut prendre en charge différentes exigences de délai.

• Nous prouvons qu'il existe des structures de seuil de sortie dans la politique optimale et proposons un algorithme de surfaçage monotone pour générer une politique monotone avec une complexité de calcul simple.

• Les résultats de la simulation démontrent que les schémas que nous proposons génèrent les coûts de communication les plus bas par rapport à trois des autres schémas.

Dans notre modèle, nous considérons que les appareils mobiles peuvent accéder aux services en nuage via plusieurs réseaux sans fil, comme indiqué dans Fig. 7.4. Nous proposons un algorithme, appelé algorithme de déchargement hybride, pour calculer la politique de déchargement optimale. La fonction objective est définie comme suit:

Cloud

Cellular BS MS

min π∈Π i∈M E π i m i,1 D d=1 c d m π i i,d , π i (m π i i,d , d) + c D+1 (m π i i,D+1 ) . (7.1)
Avant de présenter notre algorithme de déchargement, nous définissons la fonction de valeur comme suit:

V * d (m i ) = min a i ∈A(l i ,u i ) Q d (m i , a i ), (7.2)
where

Q d (m i , a i ) = m i ∈M i P(m i |m i , a i ) • c d (m i , a i ) + V * d+1 (m i ) = c d (m i , a i ) + m i ∈M P(m i |m i , a i ) • V * d+1 (m i ) = ν l i a i • T • χ a i + l i ∈L k i ∈K P(l i |l i ) • P(k i |l i , u i , k i , a i ) • V * d+1 (l i , u i , k i ) = ν l i a i • T • χ a i + l i ∈L P(l i |l i ) • V * d+1 (l i , u i , (k i -ν l i a i T )). (7.3)
La politique optimale est définie comme Nous comparons les mesures de performance de différents schémas avec une taille de données K. Sur la Fig. • Le problème optimal des enchères multi-articles étant difficile à résoudre, nous proposons en outre deux ventes aux enchères gourmandes qui peuvent résoudre le problème du marché du déchargement en temps polynomial, tout en préservant les propriétés de faisabilité budgétaire, de compatibilité des incitations et de rationalité individuelle. Ces deux enchères gourmandes se surpassent dans différents scénarios de réseau.

π * d (m i ) = argmin a i ∈A(l i ,u i ) Q d (m i , a i ). ( 7
• Nous effectuons une analyse numérique et une évaluation comparative des solutions optimales et enchères gourmandes, en considérant des scénarios de réseau réalistes. Nous illustrons en outre que les mécanismes de déchargement proposés peuvent améliorer les performances de déchargement de données cellulaires et sont plus robustes que les enchères Myerson.

Un scénario de déchargement de données entre plusieurs points d'accès et MS est présenté dans la Fig. 7.8, L'ensemble de l'incertitude est construit comme suit:

U j = (v 1j , . . . , v nj ) -Γ ≤ n i=1 v ij -n • µ j √ n • δ j ≤ Γ . (7.5)
Le problème optimal de conception des enchères, basé sur les contraintes de propriété cidessus, est formulé comme un problème d'optimisation robuste, avec pour objectif de maximiser le revenu de MNO pour toutes les évaluations de l'ensemble U. Étant donné que les opinions de MNO sur les évaluations des états membres sont modélisées comme un ensemble d'incertitudes, nous nous concentrons sur la maximisation des revenus les plus défavorables. Les contraintes de réseau, y compris les contraintes de bande passante des AP et les contraintes de demande des MS, sont également formulés dans le problème d'optimisation.

max x v ,p v W (7.6a) s.t. W - i∈N p v i ≤ 0, ∀v ∈ U (7.6b) p v i ≤ j∈M v ij • x v ij , ∀i ∈ N , ∀v ∈ U (7.6c) p v i ≤ B i , ∀i ∈ N , ∀v ∈ U (7.6d) j∈M v ij • x (u i ,v -i ) ij -x (v i ,v -i ) ij + p (u i ,v -i ) i -p (v i ,v -i ) i ≥ 0, ∀i ∈ N , (7.6e)
∀(v i , v -i ) ∈ U, ∀(u i , v -i ) ∈ U i∈N x v ij ≤ C j , ∀j ∈ M, ∀v ∈ U (7.6f) j∈M x v ij ≤ D i , ∀i ∈ N , ∀v ∈ U (7.6g) x v ij ≥ 0, ∀i ∈ N , ∀j ∈ M, ∀v ∈ U (7.6h) p v i ≥ 0, ∀i ∈ N , ∀v ∈ U. ( 7

Algorithm 9 Greedy MatchingAP Scheme

Input: b, d, M, N , C Output: a, p 1: M ← Sort(j ∈ M,

C j |N j | , "non -decreasing ) 2: N ← N 3: while M = ∅ ∧ N = ∅ do 4: j ← N ext(M ), M ← M \ {j} 5: N j ← Sort(i ∈ N j , b i , "non -decreasing ) 6: while i∈N j a ij ≤ C j ∧ N j = ∅ do 7: i ∈ N ext(N j ) 8: if j∈M a ij = 0 ∧ d i + i∈N j a ij ≤ C j then 9: a ij ← d i 10: N ← N \ {i} 11: end if 12:
end while 13: end while 14: for all j ∈ M do 15:

p k ← max {i∈N j |a ij =0} b i 16: for all i ∈ N j ∧ a ij = d i do 17: p i ← p j • d i 18:
end for 19: end for Algorithm 10 Greedy MatchingMS Scheme

Input: b, d, M, N , C Output: a, p 1: N ← Sort(i ∈ N , max j∈M b ij , "non -decreasing ) 2: M ← M 3: while M = ∅ ∧ N = ∅ do 4: i ← N ext(N ), N ← N \ {i} 5: M i ← Sort(j ∈ M i , C j , "non -decreasing ) 6: while j∈M a ij < d i ∧ M i = ∅ do 7: j ∈ N ext(M i ) 8: if d i + i∈N j a ij ≤ C j then 9: a ij ← d i 10: M ← M \ {j} 11: end if 12:
end while 13: end while 14: for all j ∈ M do 15:

p k ← max {i∈N j |a ij =0} b i 16: for all i ∈ N j ∧ a ij = d i do 17: p i ← p j • d i 18:
end for 19: end for pour objectif de sélectionner les MS pour chaque AP capable de décharger le trafic de données mobile. La phase de paiement calcule le prix payé par chaque gagnant en prenant en compte l'enchère maximum des états membres non gagnants. Dans ce qui suit, nous présentons l'algorithme glouton illustré dans Algorithme 10 pour MatchingMS; il a la même structure d'algorithme que le schéma MatchingAP. Il comprend également les phases d'allocation et de paiement. En particulier, le schéma MatchingMS a la même règle de paiement que le schéma MatchingAP.

Nous évaluons les performances du mécanisme de vente aux enchères proposé pour la vente de la bande passante des points d'accès aux états membres situés à proximité. Plus spécifiquement, notre objectif est d'évaluer l'impact de la densité d'AP (le nombre d'AP), de la contrainte budgétaire et de l'ensemble d'évaluations d'incertitude sur la performance des mécanismes proposés afin de mettre en place un marché efficace de déchargement de données mobiles. Nous évaluons ensuite le nombre de soumissionnaires gagnants de différents systèmes. Figues. 7.10(b), 7.11(b) et 7.12(b) montront que le schéma optimal regroupe le plus grand nombre de MS gagnants; cela indique qu'un schéma optimal peut mettre en oeuvre une meilleure allocation d'équité entre plusieurs états membres. La figure 7.12(b) montre que le nombre de MS gagnantes pour tous les schémas augmente de manière linéaire avec le nombre de MS. En effet, une densité de points d'accès élevée implique une bande passante suffisante pour répondre à la demande de trafic des MS. Cependant, ce n'est pas le cas pour une densité de PA faible et moyenne, où la bande passante totale des points d'accès n'est pas suffisante pour prendre en charge un grand nombre de MS. En comparant les Figs. 7.12(a) et 7.12(b), nous constatons que MatchingMS génère des revenus plus élevés que MatchingAP, même lorsque deux régimes gourmands ont le même nombre de MS gagnants. Cette observation implique que deux systèmes gourmands allouent de la bande passante à différents ensembles de MS et MatchingMS peut sélectionner l'ensemble de MS ayant des valeurs d'enchères plus élevées dans un scénario de densité élevée de points d'accès. Nous avons enfin étudié l'impact de la densité AP sur les performances de déchargement des données. Nous traçons le trafic déchargé par rapport au nombre de MS dans Figues. 7.10(c), 7.11(c) et 7.12(c). Nous constatons que le schéma optimal atteint la taille la plus élevée du trafic déchargé et que le schéma MDP surpasse deux schémas gloutons, car le schéma MDP vise à maximiser la taille du trafic déchargé. Cependant, comme illustré sur les Fig. 7.10, 7.11 et 7.12, nous observons que deux systèmes gourmands génèrent des revenus plus élevés que le système MDP, même si le système MDP peut décharger davantage de trafic de données. Cela est dû au fait que le régime MDP ne profite pas de la concurrence des états membres pour obtenir des revenus. La figure 7.12(c) montre que tous les schémas atteignent la même taille de trafic déchargé, puisque toutes les demandes de trafic des MS sont satisfaites (voir Fig. 7.12(b)).

Jeux de Population Pour MEC

Dans cette section, nous proposons une approche basée sur le jeu de la population pour examiner le problème d'équilibrage de la charge de travail de MEC dans l'IoT. Le jeu de la population est considéré comme un outil puissant pour modéliser les interactions stratégiques entre de grandes quantités d'agents [START_REF] Barreiro-Gomez | Distributed population dynamics: Optimization and control applications[END_REF][START_REF] Quijano | The role of population games and evolutionary dynamics in distributed control systems: The advantages of evolutionary game theory[END_REF]. Spécifiquement, nous modélisons le problème de prise de décision flottant parmi un grand nombre d'IoTD concurrents comme un jeu de population, dans lequel les IoTD sont des agents intéressés et prennent des décisions flottantes individuellement. Les principales contributions de cette section se résument comme suit:

• Formulation d'un modèle de jeu de population: Nous formulons le problème d'équilibrage de la charge de travail de MEC en tant que jeu de population et proposons un modèle de classification de dispositifs IoT. Nous concevons un modèle de mise en file d'attente affecté qui peut capturer l'inférence entre IoTD. Nous utilisons la αfonction d'utilité pour implémenter différents types d'équilibrage de charge.

• Analyse de la dynamique de jeu évolutive: Nous calculons les NE de manière dynamique, c'est-à-dire que les IoTD peuvent modifier leurs décisions en cours de vol grâce à un mécanisme d'apprentissage. Le mécanisme d'apprentissage est défini comme un protocole de révision qui permet aux IoTD d'ajuster leurs décisions de vol en fonction des décisions prises par d'autres IoTD à proximité. Le processus évolutif des stratégies de déchargement des IoTD peut être modélisé par une dynamique de jeu évolutive (c'est-à-dire une équation différentielle). La dynamique de jeu évolutive décrit la variation des décisions flottantes des IoTD jusqu'à ce qu'un NE soit obtenu.

• Algorithmes d'équilibrage de la charge de travail: Nous proposons deux algorithmes d'équilibrage de la charge de travail, à savoir l'algorithme d'équilibrage de la charge de travail centralisé et l'algorithme d'équilibrage de la charge de travail décentralisé, basés sur le concept de dynamique évolutive et de protocoles de révision, respectivement. Nous montrons que ces algorithmes peuvent atteindre un NE. Les résultats de la simulation illustrent la dynamique évolutive et montrent que les algorithmes proposés peuvent réaliser un équilibrage efficace de la charge de travail dans les stations de base et les nuages de bord.

Les tâches générées par les IoTD seront transférées vers une BS puis exécutées dans le nuage de bord correspondant, comme indiqué dans la Fig. Nous évaluons la performance de nos algorithmes d'équilibrage de la charge de travail proposés par des études numériques. Nous comparons notre travail avec deux autres contributions: BRUTE [START_REF] Moon | Brute: Energy-efficient user association in cellular networks from population game perspective[END_REF] et TWB (Vers l'équilibrage de la charge de travail) [START_REF] Fan | Towards workload balancing in fog computing empowered IoT[END_REF]. BRUTE utilise la fonction αfair pour mettre en oeuvre une allocation de trafic économe en énergie entre les stations de base. BRUTE considère la consommation d'énergie dans les stations de base sans tenir compte de la charge dans les nuages de bord. TWB prend en compte la charge de trafic dans les BS et la charge de calcul dans les nuages de bord. Cependant, aucun d'entre eux ne considère l'effet du SINR sur l'équilibrage de charge.

Conclusions et Travaux Futurs

Dans ce rapport, nous avons présenté trois contributions.

• Dans la première contribution, nous étudions le problème de déchargement de données mobiles sous l'architecture du cloud computing mobile, où les données mobiles peuvent être transmises via le réseau WiFi et la communication entre appareils. Afin de minimiser le coût global de la tâche de livraison des données, il est essentiel de réduire l'utilisation du réseau cellulaire tout en satisfaisant aux exigences de délai. Dans notre modèle proposé, nous formulons la tâche de déchargement des données en tant que processus de décision de Markov à horizon fini. Nous proposons tout d'abord un algorithme de déchargement hybride pour les données mobiles avec des exigences de délai différentes. De plus, nous établissons les conditions suffisantes pour l'existence d'une politique de seuil. Ensuite, nous proposons un algorithme de déchargement monotone basé sur une politique de seuil afin de réduire la complexité de calcul. Les résultats de la simulation montrent que l'approche de déchargement proposée permet d'obtenir un coût de communication minimal par rapport aux trois autres schémas de déchargement.

• Dans la deuxième contribution, nous considérons un marché flou de données mobiles où l'opérateur de réseau mobile (MNO) peut vendre la bande passante mise à disposition par les points d'accès afin d'accroître le profit de MNO. Nous formulons le problème du flot comme une enchère comportant plusieurs articles et étudions le problème de la maximisation du profit de MNO. Nous discutons des conditions pour (i) déterminer le volume maximal de trafic de données, (ii) encourager la participation des abonnés mobiles (rationalité individuelle), (iii) éviter les manipulations de marché (compatibilité incitative) et (iv) préserver la faisabilité budgétaire des états membres. Ensuite, nous proposons une méthode d'optimisation robuste pour mettre en oeuvre un mécanisme d'enchères à articles multiples. Nous proposons en outre deux algorithmes itératifs qui résolvent efficacement le problème de déchargement. Les résultats de la simulation montrent l'efficacité et la robustesse des méthodes proposées pour le flot de données cellulaires.

• Dans la troisième contribution, nous examinons les problèmes d'équilibrage de la charge de travail afin de minimiser les temps de latence de transmission et de calcul dans la tâche de processus de déchargement, tout en tenant compte des ressources en bande passante limitées des stations de base et des ressources de calcul dans les nuages de contour. Nous formulons le problème de l'équilibrage de la charge de travail comme un jeu de population afin d'analyser l'ensemble des décisions flotter. Nous analysons l'ensemble des décisions prises par les utilisateurs mobiles au travers de la dynamique de jeu évolutive et montrons que le jeu admet toujours un équilibre de Nash (NE). Nous proposons en outre deux algorithmes d'équilibrage de la charge de travail basés sur des protocoles de révision et de dynamique évolutive. Les résultats de la simulation montrent que les algorithmes d'équilibrage de la charge de travail proposés permettent d'atteindre de meilleures performances que les deux autres.

Il existe trois directions intéressantes pour les recherches futures.

• Plusieurs méthodes de déchargement ont été proposées. La caractéristique de ces

ix List of Figures 1 . 1

 11 WiFi offloading. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 D2D offloading. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Mobile edge computing in software defined network. BS denotes Base Station and MU represents Mobile User. . . . . . . . . . . . . . . . . . . . . . . . . . .3.1 The system model of mobile data offloading. . . . . . . . . . . . . . . . . . . . 3.2 A sample reduced state transition for MS, where the first component is the location of MS l, and the second component is data size k. Here, L = {l 1 , l 2 , l 3 } and K = 4. Action a 1 can transfer 1 data unit each time, while a 2 can transfer 2 data units each time. The state with double circle is the terminal state, i.e., state (l i , 0), i ∈ L. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.3 Monotone policy in l ∈ L 1 : K = 30 M bytes and D = 30 seconds. The dots (•) and triangles ( ) represent the waiting and cellular action, respectively. . . . 3.4 Monotone policy in l ∈ L 3 : K = 30 M bytes and D = 30 seconds. The dots (•), triangles ( ), and stars ( ) represent the waiting, cellular and D2D action, respectively. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Performance comparison of Hybrid and Monotone Policies. . . . . . . . . . . 3.6 Performance comparison versus data size K. . . . . . . . . . . . . . . . . . . . 3.7 Performance comparison versus deadline D. . . . . . . . . . . . . . . . . . . . 3.8 Total completion time comparison for different schemes, with same data size K = 400 Mbytes and different deadline D. . . . . . . . . . . . . . . . . . . . . . 3.9 Data transmitted comparison for different schemes, with same data size K = 400 Mbytes and different deadline D. . . . . . . . . . . . . . . . . . . . . . . . . 4.1 An illustration of data offloading auction model. WiFi APs are managed by a single MNO that provides network access to its mobile subscribers (e.g., MS1). The network capacity of WiFi access points (e.g., AP1) is allocated to MSs for data traffic offloading. In this scenario, MS1, MS2 and MS3 bid for bandwidth (i.e., AP1, AP2 and AP3) with different valuations. Considering the coverage area of each AP, MS2 can bid for three APs, while MS1 and MS3 can bid for two APs. MNO who is the auctioneer allocates different APs' bandwidth to MSs. The winning MSs can use bandwidth determined by MNO. 4.2 Flow chart of the proposed Optimal Algorithm. The left column denotes the nominal allocation phase, while the right column denotes the final allocation phase. Note that set Q = {B, C, D, M, N } contains the information of MSs' budgets and demands, as well as the capacity constraints of APs. . . . . . . . 4.3 Performance comparison with low AP density (m = 5). . . . . . . . . . . . . . 4.4 Performance comparison with medium AP density (m = 10). . . . . . . . . . . 4.5 Performance comparison with high AP density (m = 20). . . . . . . . . . . . . 4.6 Performance comparison with low capacity (C j = 5 Mbps) . . . . . . . . . . .

x 4 . 7

 47 Performance comparison with medium capacity (C j = 25 Mbps) . . . . . . . . 4.8 Performance comparison with high capacity (C j = 40 Mbps) . . . . . . . . . . 4.9 Performance comparison with budget constraint (n = 30, m = 10) . . . . . . . 4.10 Performance comparison with budget constraint (n = 30, m = 5). . . . . . . . 4.11 Robustness comparison with different deviation . . . . . . . . . . . . . . . . . 4.12 Robustness comparison with different expectation . . . . . . . . . . . . . . . . 4.13 Scalability comparison among different schemes . . . . . . . . . . . . . . . . . 5.1 MEC workload balancing model. n IoTDs offload computation intensive tasks to m edge clouds by BSs. The available offloading strategies depends on the location of IoTDs, e.g., IoTD1 can only offload tasks to BS1, while IoTD2 can offload tasks to BS1 or BS2, since IoTD can only access BSs in proximity. . . . 5.2 Illustration of IoTDs classification model. We consider that four IoTDs q1, q2, q3 and q4 are located in the same place, i.e., L(q1) = L(q2) = L(q3) = L(q4). Due to different computational density per size of data, e.g., C 1 = D q3 B q3 = D q4 B q4 and C N = D q1 B q1 = D q2 B q2 , IoTDs are classified into two classes. Note that each line can represent a class and the slope of the line denotes the computational density of the class. Thus, q1, q2 ∈ Q N and q3, q4 ∈ Q 1 . . . . . . . . . . . . . . . . . . . 5.3 Queueing model for MEC workload balancing. This figure illustrates that three classes of IoTDs offload tasks to three edge clouds. The processing delay consists of transmission delay in BS and computation delay in edge cloud. Load balancing mechanism can shorten the processing delay. . . . . . . . . . 5.4 La dynamique évolutive de Smith protocol. . . . . . . . . . . . . . . . . . . . . 5.5 La dynamique évolutive de Logit protocol. . . . . . . . . . . . . . . . . . . . . 5.6 La dynamique évolutive de BNN dynamics. . . . . . . . . . . . . . . . . . . . 5.7 Traffic load versus different BSs. . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8 Computation load versus different edge clouds. . . . . . . . . . . . . . . . . . 7.1 Déchargement WiFi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Déchargement D2D. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 MEC en SDN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Le modèle système de MDO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 La politique monotone dans l ∈ L 1 : K = 30M bytes et D = 30seconds. Les dots (•) et triangles ( ) represent the waiting et cellular action, respectivement. . 7.6 La politique monotone dans l ∈ L 3 : K = 30 M bytes et D = 30 seconds. Les dots (•), triangles ( ), et stars ( ) represent the waiting, cellular et D2D action, respectivement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.7 Performance comparison versus deadline D. . . . . . . . . . . . . . . . . . . . xi 7.8 Illustration du modèle de vente aux enchères avec déchargement de données.

  droite indique la phase d'allocation finale. Notez que set Q = {B, C, D, M, N } contient les informations sur les budgets et les demandes des états membres, ainsi que les contraintes de capacité des points d'accès. . . . . . . . . . . . . . . . . . . . . 7.10 Comparaison des performances avec une faible densité de AP (m = 5). . . . . 7.11 Comparaison des performances avec une moyenne densité de AP (m = 10). . 7.12 Comparaison des performances avec une élevée densité de AP (m = 20). . . . 7.13 Modèle en file d'attente dans MEC. Cette figure montre que trois classes d'IoTD déchargent des tâches sur trois nuages périphériques. Le délai de traitement comprend le délai de transmission dans la station de base et le délai de calcul dans le nuage de bord. Le mécanisme d'équilibrage de la charge peut raccourcir le délai de traitement. . . . . . . . . . . . . . . . . . . . . . . . . . . 7.14 La dynamique évolutive de Smith protocol. . . . . . . . . . . . . . . . . . . . . 7.15 La dynamique évolutive de Logit protocol. . . . . . . . . . . . . . . . . . . . . 7.16 La dynamique évolutive de BNN protocol. . . . . . . . . . . . . . . . . . . . . xiii List of Tables 1.1 Comparison of WiFi offloading and D2D offloading . . . . . . . . . . . . . . . 1.2 Comparison of MCC and MEC . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Classification of contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Notations for Mobile Data Offloading . . . . . . . . . . . . . . . . . . . . . . . 3.2 Different offloading schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Notation used in the chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Classification des contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . xv

FIGURE 1 . 1 :

 11 FIGURE 1.1: WiFi offloading.

FIGURE 1 . 2 :

 12 FIGURE 1.2: D2D offloading.

FIGURE 3 . 1 :

 31 FIGURE 3.1: The system model of mobile data offloading.

1 d

 1 All grids are classified into four disjoint categories at decision epoch d based on available WiFi or D2D connections. L denotes the grids covered by only cellular network, L 2 d contains the grids covered by both cellular and WiFi networks, L 3 d represents the grids covered by both cellular network and D2D communication, and L 4 d denotes the grids covered by cellular, WiFi networks and D2D communication. Due to the mobility of MHs, L 2 d , L 3 d and L 4 d change over decision epoch d. The state parameter u ∈ U = {1, 2, • • • , U } represents the mobile user type (e.g. loose delay or tight delay), where U represents the number of different user types. We consider that different user types have different delay requirements resulting in different deadlines. To simplify the model, we consider two sets of user types, each of which has different QoS requirements. More specifically, user types that are delay-sensitive are in set U 1 ; the other types (e.g. software update) are in set U 0 . Thus, U = U 0 ∪ U 1 .

14 :

 14 Set d ← 1 and k ← K 15: while d < D + 1 and k > 0 do 16: Get current location l d i of MS 17:

3. 4 . 29 From

 429 Monotone Policy and Offloading Algorithm Eq.(3.14) and the definition of action cost, we get Eq. (3.13).

. 20 )

 20 Subtracting Eq. (3.19) from Eq. (3.20), we get Eq. (3.21a). Since ν 2 < ν 3 , let ν 3 = ν 2 + δ and δ > 0. Replacing ν 3 with ν 2 + δ in Eq. (3.21a), we get Eq. (3.21b).

Lemma 5 .Theorem 2 .

 52 If f (m, a) is a superadditive function in M × A, then the function g(a) defined below is monotone increasing in m. g(a) = argmin a∈A f (m, a). (3.26) Lemma 4 shows that the sum of two superadditive functions satisfies superadditive property. Lemma 5 states that a superadditive function including two variables can be considered as a monotone increasing function having one variable, which implies the theoretical basic of Chapter 3. Markov Decision Process Based Mobile Data Offloading monotone policy. In our model, we consider Q d (l, u, k, a) as a superadditive function in K × A and D × A. The monotone policy in dimensions k and d is summarized as follows. The optimal monotone policy Π * = π * d (l, u, k) = a * , ∀ l ∈ L, u ∈ U, k ∈ K, d ∈ D has threshold structure in both k and d as follows: (a) For location l ∈ L 1 with only cellular network and u ∈ U, we get A(l, u) = {1, 2} by Eq.(3.1). There is one threshold for both k and d. That is ∀d ∈ D,

  waiting), otherwise. (3.28) (b) For location l ∈ L 2 with cellular and WiFi networks, and u ∈ U, we get A(l, u) = {1, 2, 3} by Eq.(3.1). If ν 2 > ν 3 > ν 4 , there is one threshold for both k and d. That is ∀d ∈ D,

. 30 )

 30 (c) For location l ∈ L 3 with cellular network and D2D communication, and u ∈ U 0 , we get A(l, u) = {1, 2, 4} by Eq. (3.1). If ν 2 > ν 4 , there are two thresholds for both k and d. That is ∀d ∈ D,

(3. 32 )

 32 (d) For location l ∈ L 4 with cellular network, WiFi network and D2D communication, and u ∈ U 0 , we get A(l, u) = {1, 2, 3, 4} by Eq.(3.1). If ν 2 > ν 4 > ν 3 , there are two thresholds for both k and d. That is ∀d ∈ D,

  .37) Since Eq. (3.37) satisfies the definition of superadditive function (Definition 2), c d (s, a) is superadditive in M × A.

66 FIGURE 3 . 3 :

 6633 FIGURE 3.3: Monotone policy in l ∈ L 1 : K = 30M bytes and D = 30seconds. The dots (•) and triangles ( ) represent the waiting and cellular action, respectively.

FIGURE 3 . 4 :

 34 FIGURE 3.4: Monotone policy in l ∈ L 3 : K = 30 M bytes and D = 30 seconds. The dots (•), triangles ( ), and stars ( ) represent the waiting, cellular and D2D action, respectively.

Theorem 1 ,

 1 WiFi action is the dominant action in l ∈ L 2 d ∪ L 4 d . The optimal policies having threshold structures in L 1 d and L 3 d , based on Theorem 2 (a) and (c), are shown in Figs. 3.3 and 3.4, respectively.

Fig. 3 .

 3 Fig. 3.3 illustrates the optimal policy for MSs in l ∈ L 1 d , where A(l, u) = {1, 2}. Thus, MNO has two actions, i.e., waiting action and cellular action. As shown in Fig. 3.3, a single threshold exits in dimension d. It shows that cellular action is selected when d is large enough. Otherwise, MNO chooses the waiting action. For example, in Fig. 3.3(a), given k = 10, the optimal action changes from waiting action to cellular action when d > 26. The single

  3.3(a) and 3.3(b).

Fig. 3 .

 3 Fig.3.4(a) shows that MNO chooses D2D action when d or k is small, instead of waiting action (see Fig.3.3(c)), with the same knowledge of network setting (i.e., n w = 0 and n h = 66). Since χ 4 < χ 2 , MNO chooses D2D action to minimize the transmission cost. However, when d or k is large, cellular action is selected to ensure that data transmission will be completed before deadline, due to the fact that ν 2 > ν 4 . Figs. 3.4(b) and 3.4(c) show that two thresholds separate three actions (waiting action, cellular action and D2D action.) in dimensions k and d, since l ∈ L 3 d and A(l, u) = {1, 2, 4}. Compared with two actions (D2D and cellular actions) shown in Fig. 3.4(a), additional waiting action occurs in Figs. 3.4(b) and 3.4(c) with the knowledge of potential WiFi offloading. Both D2D and cellular action areas in Fig. 3.4(c) are smaller than those in Fig. 3.4(b), while the waiting action area in Fig. 3.4(c) is larger than that in Fig. 3.4(b); this can be explained by the fact that there are more WiFi APs in the case of Fig. 3.4(c).

  Total cost versus data size K (M bytes), the deadline D is 200 seconds.

  Offloading ratio versus data size K (M bytes), the deadline D is 200 seconds.

FIGURE 3 . 5 :

 35 FIGURE 3.5: Performance comparison of Hybrid and Monotone Policies.

Fig. 3 .

 3 Fig.3.6(b) shows that TUP increases with data size, since it takes longer to transmit data of larger size. We observe that TUP of non-delayed schemes (i.e., N D4 and N D3) are smaller than that of delayed schemes (i.e., D4 and D3). This is because delayed schemes use additional time to wait for offloading opportunities. TUP of D4 is smaller than that of D3, since D4 can use D2D action to offload mobile data when D3 is waiting for another WiFi connection. Fig.3.6(c) shows that the offloading ratio decreases when data size increases except for N D3. This is because N D3 transmits data based on the available networks without considering current data size k and decision epoch d. We observe that the offloading ratio of D3

  Time usage percentage versus data size K for D = 140 seconds. Offloading ratio versus data size K for D = 140 seconds. Total cost versus data size K for D = 100 seconds.

FIGURE 3 . 6 :

 36 FIGURE 3.6: Performance comparison versus data size K.

Chapter 3 .

 3 Markov Decision Process Based Mobile Data Offloading Offloading ratio versus deadline D for K = 400 Mbytes.

FIGURE 3 . 7 :

 37 FIGURE 3.7: Performance comparison versus deadline D.

  K = 400 Mbytes, and D = 400 seconds.

FIGURE 3 . 8 :

 38 FIGURE 3.8: Total completion time comparison for different schemes, with same data size K = 400 Mbytes and different deadline D.

FIGURE 3 . 9 :

 39 FIGURE 3.9: Data transmitted comparison for different schemes, with same data size K = 400 Mbytes and different deadline D.

FIGURE 4 . 1 :

 41 FIGURE 4.1: An illustration of data offloading auction model. WiFi APs are managed by a single MNO that provides network access to its mobile subscribers (e.g., MS1). The network capacity of WiFi access points (e.g., AP1) is allocated to MSs for data traffic offloading. In this scenario, MS1, MS2 and MS3 bid for bandwidth (i.e., AP1, AP2 and AP3) with different valuations. Considering the coverage area of each AP, MS2 can bid for three APs, while MS1 and MS3 can bid for two APs. MNO who is the auctioneer allocates different APs' bandwidth to MSs. The winning MSs can use bandwidth determined by MNO.

) 9 :

 9 for k ∈ N do 10: y v -k ← solving problem (4.15) 11: end for 12: for i ∈ N do 13:

Fig. 4 .

 4 Fig. 4.2 shows the relationship among different optimization problems in Optimal Algorithm. Optimal Algorithm consists of two phases, the phase of nominal allocation (Steps 1 -7, left column of Fig. 4.2) and the phase of final allocation (Steps 8 -19, right column of Fig 4.2). The aim of nominal allocation is to calculate the reservation price r * = {r ij } i∈N ,j∈M and the nominal allocation x * = {x ij } i∈N ,j∈M . MS i has to bid at least r ij in order to use the bandwidth provided by AP j. x * represents the best allocation in worst case scenario, which is part of the final allocation calculated in the phase of final allocation. Reservation price is obtained by calculating problems[START_REF] Mach | Mobile edge computing: A survey on architecture and computation offloading[END_REF] and (13) sequentially. Final allocation calculates the real allocation a v and final payment p v based on a specific bid matrix v. The final allocation a v = x * + y v , where y v = {y v ij } i∈N ,j∈M , called adapted allocation, denotes the best allocation for a specific bid matrix v. Final allocation is based on the results of optimization problems

FIGURE 4 . 2 :

 42 FIGURE 4.2: Flow chart of the proposed Optimal Algorithm. The left column denotes the nominal allocation phase, while the right column denotes the final allocation phase. Note that set Q = {B, C, D, M, N } contains the information of MSs' budgets and demands, as well as the capacity constraints of APs.

  .13c) The decision variables ξ * = {ξ * j } j∈M , η * = {η * i } i∈N , λ * = {λ * i } i∈N and θ * = {θ * i } i∈N correspond to the constraints (4.10c), (4.10b), (4.10d) and (4.11), respectively. Step 2 calculates the solution of dual problem (4.13) used to obtain the reservation price r * in Steps 3 -7, where r * ij represents the minimum price that MS i should bid in order to use bandwidth of AP j.

FIGURE 4 . 3 :

 43 FIGURE 4.3: Performance comparison with low AP density (m = 5).

FIGURE 4 . 4 :

 44 FIGURE 4.4: Performance comparison with medium AP density (m = 10).

FIGURE 4 . 5 :

 45 FIGURE 4.5: Performance comparison with high AP density (m = 20).

FIGURE 4 . 6 :

 46 FIGURE 4.6: Performance comparison with low capacity (C j = 5 Mbps)

FIGURE 4 . 7 :

 47 FIGURE 4.7: Performance comparison with medium capacity (C j = 25 Mbps)

FIGURE 4 . 8 :

 48 FIGURE 4.8: Performance comparison with high capacity (C j = 40 Mbps)

Chapter 4 .

 4 Multi-Item Auction Based Mechanism for Mobile Data Offloading

FIGURE 4 . 9 :

 49 FIGURE 4.9: Performance comparison with budget constraint (n = 30, m = 10)

FIGURE 4 . 10 :

 410 FIGURE 4.10: Performance comparison with budget constraint (n = 30, m = 5).

  Figs.4.6(a), 4.7(a) and4.8(a) show the variation of revenue with the number of APs. We observe that the revenues of all schemes increase with the number of APs. As more APs participate in the auction, MNO has more bandwidth provided to MSs, leading to higher revenue. We find that optimal scheme outperforms the other schemes in all scenarios. MatchingMS achieves higher revenue than MatchingAP when AP bandwidth is low, as shown in Figure4.6(a). Note that with low bandwidth 5 Mbps, each AP can serve one MS at most, since the minimum demand of MS is 3 Mbps. In this scenario, the final payment of winning MS is the same as its bid value, since the only bidder is the winning MS itself. According to the sorting rule of MatchingMS (see Algorithm 6), MS with a higher bid value has higher chance of winning the auction, resulting in a higher revenue.

  Figs. 4.6(b), 4.7(b) and 4.8(b) show that the number of winning MSs increase with the the number of APs, since large number of APs increases the potential of satisfying the demand of MSs. We observe that the optimal scheme has the highest number of winning MSs. The curves, as shown in Figs. 4.6(c), 4.7(c) and 4.8(c), follow similar trends as Figs. 4.6(b), 4.7(b) and 4.8(b), respectively, due to the fact that the offloaded traffic increases with the number of winning MSs.

5 FIGURE 5 . 1 :

 551 FIGURE 5.1: MEC workload balancing model. n IoTDs offload computation intensive tasks to m edge clouds by BSs. The available offloading strategies depends on the location of IoTDs, e.g., IoTD1 can only offload tasks to BS1, while IoTD2 can offload tasks to BS1 or BS2, since IoTD can only access BSs in proximity.

FIGURE 5 . 2 : 3 FIGURE 5 . 3 :

 52353 FIGURE 5.2: Illustration of IoTDs classification model. We consider that four IoTDs q1, q2, q3 and q4 are located in the same place, i.e., L(q1) = L(q2) = L(q3) = L(q4). Due to different computational density per size of data, e.g., C 1 = D q3 B q3 = D q4 B q4 and C N = D q1 B q1 = D q2 B q2 , IoTDs are classified into two classes. Note that each line can represent a class and the slope of the line denotes the computational density of the class. Thus, q1, q2 ∈ Q N and q3, q4 ∈ Q 1 .

Definition 1 .Theorem 5 .

 15 A population game F : R N ×M + → R N ×M is a potential game if there exists a continuously differentiable function T : R N ×M + → R, called a potential function, satisfying ∇T(a) = F (a) for all a ∈ R N ×M + , or ∂T ∂a n m (a) = F n m (a) for all m ∈ M and n ∈ N . Definition 1 shows that the partial derivatives of the potential function are the payoff functions of the population game. Our proposed population game F (a) = {F n m (a) : m ∈ M n , n ∈ N } is a potential game. The potential function is T( α, α, ρ(a), ρ).

Phase 2 :

 2 Calculate offloading decisions. 11: Initialize decision vector A ← 0 12: for all n ∈ N do

Algorithm 8 Part 1 : 1 :Part 2 :

 8112 DWB (Decentralized Workload Balancing) For all IoT D n m for all "stochastic update clock" rings do 2: K ← randomly choose K IoTDs from M n For all BS m 11: for all "stochastic update clock" rings do 12: Collect current population state â 13:

FIGURE 5 . 4 :

 54 FIGURE 5.4: La dynamique évolutive de Smith protocol.

FIGURE 5 . 5 :

 55 FIGURE 5.5: La dynamique évolutive de Logit protocol.

FIGURE 5 . 6 :

 56 FIGURE 5.6: La dynamique évolutive de BNN dynamics.

FIGURE 5 . 7 :

 57 FIGURE 5.7: Traffic load versus different BSs.

FIGURE 5 . 8 :

 58 FIGURE 5.8: Computation load versus different edge clouds.

F

  n m (a) = ∂T( α, α, ρ(a), ρ) ∂a n m = ξ • ∂T(α, ρ) ∂a n m + ∂T( α, ρ(a)) ∂a n m .

. 42 )= 1 -

 421 Chapter 5. Population Game Based Workload Balancing in Mobile Edge Computing Case 1: α = 1, ρm (a) (1ρm (a)) 2 • -∂ ρm (a) . (5.45) and (5.48) are equivalent when α = 1. Thus, we obtain that ∂T( α, ρ(a))

1 ,

 1 a)(1ρm (a)) The population game F (a) = {F n m (a) : m ∈ M n , n ∈ N } is a potential game and the potential function is T( α, α, ρ(a), ρ).

FIGURE 7 . 1 :

 71 FIGURE 7.1: Déchargement WiFi.

FIGURE 7 . 4 : 100 Chapter 7 .

 741007 FIGURE 7.4: Le modèle système de MDO.

. 4 )

 4 La politique monotone est montrée dans Figs.7.5 and 7.6. n w = 0, n h = 66

FIGURE 7 . 5 : 66 FIGURE 7 . 6 :

 756676 FIGURE 7.5: La politique monotone dans l ∈ L 1 : K = 30 M bytes et D = 30 seconds. Les dots (•) et triangles ( ) represent the waiting et cellular action, respectivement.

  Offloading ratio versus deadline D for K = 400 Mbytes.

FIGURE 7 . 7 :

 77 FIGURE 7.7: Performance comparison versus deadline D.

108 Chapter 7 FIGURE 7 . 10 :

 1087710 FIGURE 7.10: Comparaison des performances avec une faible densité de AP (m = 5).

FIGURE 7 . 11 :

 711 FIGURE 7.11: Comparaison des performances avec une moyenne densité de AP (m = 10).

FIGURE 7 . 12 :

 712 FIGURE 7.12: Comparaison des performances avec une élevée densité de AP (m = 20).

7 . 13 . 3 FIGURE 7 . 13 :Theorem 6 . 7 . 20 )Phase 1 :Phase 2 :Chapter 7 .Part 1 : 1 :Part 2 : 14 : 2 W m log 2 1

 713371367201271121421 FIGURE 7.13: Modèle en file d'attente dans MEC. Cette figure montre que trois classes d'IoTD déchargent des tâches sur trois nuages périphériques. Le délai de traitement comprend le délai de transmission dans la station de base et le délai de calcul dans le nuage de bord. Le mécanisme d'équilibrage de la charge peut raccourcir le délai de traitement.

FIGURE 7 .

 7 FIGURE 7.14: La dynamique évolutive de Smith protocol.

FIGURE 7 .

 7 FIGURE 7.15: La dynamique évolutive de Logit protocol.

FIGURE 7 .

 7 FIGURE 7.16: La dynamique évolutive de BNN protocol.

TABLE 1 . 1 :

 11 Comparison of WiFi offloading and D2D offloading

		Coverage Area	Delay	Mobility Data Size Security
	WiFi offloading	Medium	Low	No	Large	Medium
	D2D offloading	Small	Medium	Yes	Small	Low

TABLE 1 .

 1

2: Comparison of MCC and MEC

Capability

Latency Scalability Architecture Location Security

	MCC	Strong	High	Low	Centralized Far	High
	MEC	Medium	Low	High	Decentralized Close	Low

Table 1

 1

.3. Chapter 1. Introduction

TABLE 1 .

 1

		3: Classification of contributions
	Contributions	Mobile Technique	Computing Paradigm
	Chapter 3	Mobile Data Offloading Markov Decision Process, Paper [1] Mobile Cloud Computing
	Chapter 4	Mobile Data Offloading Multi-Item Auction, Robust Optimization, Paper [2] Heterogeneous Network
	Chapter 5	Mobile Computation Offloading	Mobile Edge Computing

  1.4. Organization on the uncertainty set and the MSs' budgets; this can prevent market manipulation. Our proposed auction is implemented by robust optimization. Instead of requiring the full knowledge of MSs' valuations, robust optimization uses few information of MSs' valuations and can obtain a global -optimal solution.

TABLE 3 .

 3 1: Notations for Mobile Data Offloading K Total size of mobile data to be transmitted. D Total length of time for data transmission. k Size of mobile data that is not transmitted. d Decision epoch: time for making offloading decision. A Set of transmission actions. U Set of mobile user types. a Transmission action. u Mobile user type. L Total number of grids. T Length of one time slot. µ Stable factor: probability of MS staying at the same location in two sequential decision epochs. ν l

a Data rate for action a at grid l. χ a Unit price for transmitting data by action a.

  Calculate Threshold States 1: Calculate threshold states in dimension k 2: if l ∈ L 1 d , set numT hreshold ← 1 and a 1 ← 2 endif if l ∈ L 3 d , set numT hreshold ← 2 , a 1 ← 4 and a 2 ← 2 endif 3: for i ← {1, ..., numT hreshold} do

		4:	Set k ← k * i (l, u, d + 1) and f lag ← 0
	4:	Call Calculate Threshold States Algorithm
	5: end for
	6: Running Phase
	7: Set d ← 1 and k ← K 8: while d < D + 1 and k > 0 do
	9:	Get the location of MS as l
	10: 11:	if l ∈ L 2 d ∪ L 4 d , set a ← 3 by Theorem 1, end if if l ∈ L 1 d , choose action by Theorem 2.a, end if

1: Planning Phase 2: Initialize V * d+1 (s) with Eq. (3.3) and Π ← ∅ 3: for l ∈ L, u ∈ U, d ← {D, ..., 1} do 12: if l ∈ L 3 d , choose action by Theorem 2.c, end if 13: k ← kν a , d ← d + 1 14: end while Algorithm 3 5: while k ≤ K and f lag == 0 do 6:

TABLE 3 .

 3

		2: Different offloading schemes
	Abbreviation Schemes
	D4	Delayed optimal offloading with 4 actions
	D3	Delayed optimal offloading with 3 actions
	ND4	Non-Delayed offloading with 4 actions
	ND3	Non-Delayed offloading with 3 actions
	NO	No Offloading
	each scheme includes a digit that indicates the available actions for a system state (i.e., 4
	indicates that A = {1, 2, 3, 4} and 3 indicates that A = {1, 2, 3}). The benchmark schemes in-clude: (1) optimal delayed WiFi offloading scheme (D3) [41]; (2) on-the-spot WiFi offloading
	scheme (N D3) [90]: data transmission is switched between WiFi and cellular networks. WiFi
	network is used whenever available; and (3) on-the-spot WiFi and D2D offloading scheme

(N D4): WiFi network is used wherever available; D2D communication is used when MH is available and MS's state satisfies k < ν2 * (Dd). (4) no offloading scheme (N O): MS only uses cellular network. The results are averaged for a single MS.

TABLE 4 .

 4

		1: Notation used in the chapter
	N M U	Set of Mobile Subscribers Set of Access Points Uncertainty set of v

  The network constraints, including APs' bandwidth constraints and MSs' demand constraints, are also formulated in Chapter 4. Multi-Item Auction Based Mechanism for Mobile Data Offloading the optimization problem.

	max x v ,p v W			(4.9a)
	s.t. W -	i∈N	p v i ≤ 0, ∀v ∈ U	(4.9b)

  .[START_REF] Guo | Collaborative Mobile Edge Computation Offloading for IoT over Fiber-Wireless Networks[END_REF] The proposed auction mechanism with final allocation matrix a v and payment vector p v , satisfies the property of incentive compatibility. That is

	k∈N	p z k =	k∈N j∈M	x * kj • z * kj	(4.22)
	Proof. Lemma 6 can be proved by considering a reduced version of problem (4.10), where
	we set v = z. Thus, the original bilinear optimization problem (4.10) is reduced to a new
	linear optimization problem, since the only variable is x. The relations (4.18), (4.19), (4.20)
	and (4.21) that z and x * satisfy are derived directly from the constraints (4.10b), (4.10c),
	(4.10d) and (4.10e), respectively. Eq. (4.22) is derived from the objective function of problem
	(4.10).
	Lemma 7.

  .43)

	Chapter 4. Multi-Item Auction Based Mechanism for Mobile Data Offloading
	This implies that U

  in order to simplify the result. For the sake of clarity, we useIN n m = δ + k∈N n

	m P k l H k m to denote the m a k sum of noise and inference from other classes. The Signal-to-Interference-plus-Noise Ratio
	a n m P n l H n m δ+ k∈N n a k m P k l H k m m as Eq. (5.50). Note that Wm is denoted by SIN R n m . With these two variables, Eq. (5.42) can be rewritten

  It has been proved that programming model has played an important role in cloud computing. MapReduce proposed by Google and Dryad proposed by Microsoft are two famous programming models. More importantly, the open-source implementation of Hadoop is playing an important roleSince mobile cloud computing can augment the computational ability of mobile devices, mobile devices can execute sophisticated applications. From the perspective of mobile cloud computing, mobile devices only execute light tasks. Furthermore, the purpose of cloud computing is to promote the thin-client software deployment, which is suitable for mobile devices which are deployed with limited resources. Mobile cloud computing is a natural extension of cloud computing; it changes the execution mode of traditional mobile applications and proposes new challenges for cloud computing.Basically, there are two kinds of mobile cloud computing application development methods. One is to develop mobile applications traditionally and execute them with new application models, such as CloneCloud. Developers know nothing about how applications are executed. They don't know whether the application is executed locally or remotely. The selection of where to run an application is based on the offloading decision maker. Even with the same application, the decision maker may calculate different execution plans according to different environments. Another one is to develop mobile applications with distributedaware platform. Developers know that mobile applications will run in a distributed environment and they can easily develop new applications with the help of platform. Most of the applications in the future will run in distributed environment, so we think it is worth to design such a platform to improve the performance of mobile devices and cloud servers. Before the implementation of new platform, we need to design a new programming model for this platform.

	6.2. Future Work	93
	in cloud computing. MapReduce programming model has a great influence on scientific
	and industry areas.

  Selon le réseau complémentaire, il existe deux types de MDO, le déchargement WiFi et le déchargement D2D, illustré dans Figs.[START_REF] Cheng | Offloading multiple mobile data contents through opportunistic device-to-device communications[END_REF].1 and 7.2, respectivement. Le déchargement WiFi utilise un réseau WiFi pour transférer des données initialement ciblées vers un réseau cellulaire, tandis que le déchargement D2D utilise un assistant mobile pour transférer des données à un utilisateur mobile.Le réseau WiFi peut réduire efficacement le trafic cellulaire. Bien que le WiFi puisse fournir un meilleur débit que le réseau cellulaire, sa zone de couverture est plus petite que celle du réseau cellulaire. Avec des milliards d'appareils mobiles et de connexions ajoutés ces dernières années, la communication D2D devient un système de transmission de données important. Cependant, le débit de données de la communication D2D est faible et les profils de mobilité des MH ou des MS sont difficiles à prédire.MCO peut transférer une partie des tâches de calcul d'appareils mobiles vers des serveurs distants ou des serveurs locaux. MCO peut améliorer les performances des appareils mobiles. De plus, MCO réduira la consommation d'énergie des appareils mobiles. L'objectif de MCO est de minimiser le délai de traitement d'application mobile, afin de minimiser la consommation d'énergie des appareils mobiles. Il existe trois types de MCO.• Non-déchargement: le calcul est exécuté sur des appareils mobiles;• Déchargement complet: le calcul est exécuté sur des serveurs;• Déchargement partiel: une partie du calcul est exécutée sur des appareils mobiles, tandis que le reste est exécuté sur des serveurs.MCC introduit un délai important pour MCO. En particulier, le délai du longue distance entre les utilisateurs de téléphonie mobile et le centre de cloud rend le calcul du flot peu adapté à de nombreuses applications en temps réel. L'idée principale de MEC est d'amener les ressources de calcul et de stockage en périphérie du réseau mobile avec une courte distance de transmission des données. Mettre le calcul à la disposition des utilisateurs mobiles est le concept clé de MEC. Fig.7.3 illustre le modèle de MEC.

	MS	Cellular BS
		Cloud
	MH B		D2D connection
			Cellular connection
		MH A	WiFi connection MS moving trace
	FIGURE 7.2: Déchargement D2D.

Bien que MDO réduit considérablement le trafic cellulaire, il est difficile d'obtenir un MDO efficace entre plusieurs appareils mobiles. Ainsi, la manière d'allouer efficacement cette bande passante à des périphériques mobiles devient un problème clé à résoudre.

  7.7(a), nous observons que le coût total de D3 est supérieur à celui de Dans cette section, nous nous concentrons sur la conception d'un mécanisme efficace de vente aux enchères permettant d'allouer la bande passante des points d'accès à plusieurs MS. ceci est considéré comme un problème d'enchères à articles multiples. MNO qui possède l'infrastructure réseau agit en tant que commissaire-priseur et vend la bande passante aux appareils mobiles par le biais d'une vente aux enchères. Nous avons formulé le problème des enchères en nous basant sur une optimisation robuste qui modélise les propriétés souhaitables (faisabilité budgétaire, compatibilité des incitations et rationalité individuelle) des enchères optimales permettant au commissaire-priseur d'utiliser des données historiques ou une connaissance préalable des évaluations. L'incertitude des évaluations d'éléments est modélisée comme un ensemble d'incertitudes, qui est construit sur la base des théorèmes limites de la théorie des probabilités. Les principales contributions de cette section peuvent être résumées comme suit:• Nous caractérisons l'interaction entre les opérateursde réseaux mobiles et les états membres lors d'une enchère comportant plusieurs articles et visant à maximiser les revenus de l'opérateur de réseau mobile et le volume de trafic déchargé provenant d'abonnés mobiles. Notre enchère multi-articles proposée calcule les prix de réservation en fonction du jeu d'incertitude et des budgets des états membres. cela peut empêcher la manipulation du marché. Notre enchère proposée est mise en oeuvre par une optimisation robuste. Au lieu d'exiger la connaissance complète des évaluations des états membres, L'optimisation robuste utilise peu d'informations sur les évaluations des états membres et permet d'obtenir une solution globaleoptimal.

N D4 lorsque D < 300 Mbytes. Cependant, la situation change lorsque D > 300 Mbytes. En effet, D3 utilise une stratégie d'attente pour rechercher des opportunités de déchargement WiFi; des délais plus longs impliquent plus d'opportunités de déchargement WiFi. Notez que D4 engendre le coût total minimum par rapport aux autres régimes.

7.3 MIA Pour MDO

  Nous comparons d'abord la dynamique évolutive de Smith, Logit et BNN. Nous observons que Smith converge plus lentement que Logit et BNN, comme indiqué sur les Fig. 7.14, 7.15 et 7.16. Nous observons également que les flèches de Smith approchent le NE de manière moins angulaire et plus progressive. En effet, Smith modifie sa décision de déchargement en fonction du gain d'un BS, tandis que BNN et Logit modifient la décision de déchargement en fonction de tous les gains des BS. En règle générale, utiliser plus d'informations de gain pour prendre des décisions de déchargement peut améliorer les performances. Ainsi, BNN et Logit convergent plus rapidement que Smith. De plus, ces trois dynamiques évolutives

de données et de calculs mobiles dans le mobile cloud Le trafic mobile augmente considérablement en raison de la popularité des appareils mobiles et des applications mobiles. Le déchargement de données mobiles est une solution permettant de réduire la congestion du réseau cellulaire. Le déchargement de calcul mobile peut déplacer les tâches de calcul d'appareils mobiles vers le cloud. Dans cette thèse, nous étudions d'abord le problème du déchargement de données mobiles dans l'architecture du cloud computing mobile. Afin de minimiser les coûts de transmission des données, nous formulons le processus de déchargement des données sous la forme d'un processus de décision de Markov à horizon fini. Nous proposons deux algorithmes de déchargement des données pour un coût minimal. Ensuite, nous considérons un marché sur lequel un opérateur de réseau mobile peut vendre de la bande passante à des utilisateurs mobiles. Nous formulons ce problème sous la forme d'une enchère comportant plusieurs éléments afin de maximiser les bénéfices de l'opérateur de réseau mobile. Nous proposons un algorithme d'optimisation robuste et deux algorithmes itératifs pour résoudre ce problème. Enfin, nous nous concentrons sur les problèmes d'équilibrage de charge afin de minimiser la latence du déchargement des calculs. Nous formulons ce problème comme un jeu de population. Nous proposons deux algorithmes d'équilibrage de la charge de travail basés sur la dynamique évolutive et des protocoles de révision. Les résultats de la simulation montrent l'efficacité et la robustesse des méthodes proposées Mots clés : informatique mobile -informatique dans les nuages -théorie des jeux -Markov, processus de.

  7.5. Conclusions et Travaux Futurs117 méthodes est de collecter des informations aussi détaillées que possible sur les appareils mobiles et les serveurs cloud, ainsi que sur l'état du réseau. Habituellement, plus nous pouvons obtenir d'informations sur l'environnement en cours d'exécution, meilleure est notre décision. Cependant, trop d'informations à exécuter risque d'augmenter les frais généraux des périphériques mobiles, ce qui pourrait compenser les avantages, en particulier les économies d'énergie, que nous pouvons obtenir de manière inoffensive. Pour résoudre le problème, il faut analyser le surcoût de ces méthodes de décision évolutives. Nous pouvons réduire les frais généraux en ignorant les informations triviales. Pour améliorer les performances des appareils mobiles, nous pouvons même abandonner le processus décisionnel courant des appareils mobiles aux serveurs cloud de confiance. À l'avenir, nous proposerons un nouveau modèle de déchargement qui sera mis en oeuvre entre les appareils mobiles et les serveurs Cloud/Edge connectés. Le modèle que nous proposons peut transférer une partie des tâches de décision flottantes des appareils mobiles vers le cloud ou la périphérie. En outre, le nuage périphérique peut améliorer les performances des réseaux cellulaires. Nous établirons un cadre mathématique pour étudier ce problème. • Nous examinerons la situation dans laquelle le cloud d'extrémité peut également décider d'accepter ou non une demande de déchargement. Étant donné que le nombre d'appareils mobiles est généralement beaucoup plus élevé que le nombre de nuages de bord, un nuage de bord peut recevoir de nombreuses demandes de déchargement à partir d'appareils mobiles à proximité. De plus, chaque appareil mobile effectuera un déchargement des tâches une fois que ce processus pourra améliorer les performances ou économiser de l'énergie. Cependant, un nuage périphérique peut déborder si trop de demandes de déchargement lui sont envoyées. De cette manière, le nuage périphérique peut choisir d'exécuter les tâches mobiles avec une priorité plus élevée. Certaines des demandes de déchargement peuvent être refusées en raison des ressources de calcul et de stockage limitées dans les nuages périphériques. Cela diffère du déchargement sur des serveurs cloud. Dans le cloud computing, nous supposons qu'il existe des ressources informatiques et de stockage pratiquement illimitées. Les demandes de déchargement seront toujours acceptées. En raison de l'environnement sans fil incertain, nous proposerons de nouvelles méthodes pour faire face aux échecs de déchargement. • Nous voulons concevoir un nouveau modèle de programmation pour le cloud computing mobile. Le but de ce travail est d'améliorer le service de qualité dans le cloud computing mobile en élargissant le concept de modèle de programmation du cloud computing au cloud computing mobile. En tant que sous-produit, nous pouvons améliorer les performances globales des appareils mobiles et des serveurs cloud. Il existe de nombreux problèmes à résoudre pour atteindre cet objectif.

	Déchargement

nw=200,nh=300 nw=300,nh=300 nw=400,nh=400 nw=500,nh=500 nw=800,nh=800 (f) Completion time versus data size K for D = 150 seconds.

The budget information can be extended to private situation by uncertainty set with extra computaional complexity.

Acknowledgements xix

Acknowledgements

I would like to thank all people who have encouraged me, in various ways, to pursue my

higher budget increases the winning probability of MSs who have higher valuations and larger bandwidth demands. Thus, the total revenue increases while the number of winning MSs decreases when B i ≥ 15.

Robustness and Scalability Analysis

Now we illustrate the robustness and scalability of the proposed optimal offloading method.

In order to show the robustness of the proposed method, we consider the scenario where the assumed distributions of MSs' valuations differ from the practical distributions, i.e., MNO's belief on the value of µ j and δ j is different from the realized value of µ * j and δ * j . We compare optimal scheme with Myerson auction [START_REF] Tang | Optimal mechanisms with simple menus[END_REF] that is an optimal auction with reservation price. Myerson auction calculates the reservation price by solving the following equation.

Note that y

is the optimal solution of problem (4.14), while y

is a feasible solution of problem (4.14). Thus, we obtain j∈M y

which demonstrates that U

, due to Eq. (4.28).

Lemma 8. The proposed auction mechanism with final allocation matrix a v and payment vector p v , satisfies the property of budget feasibility. That is p v k ≤ B k , which implies that the payment of MS k is smaller than its budget.

Proof. We first construct an allocation matrix ỹv ∈ R n×m based on y v -k ∈ R (n-1)×m , where

Thus, we can obtain the following identical equation:

Control BS Edge Cloud

Small Cell BS1 La suite de cette thèse est organisée comme suit.

• La section 7.2 présente MDO Basé Sur MDP.

• La section 7.3 présente un mécanisme de MIA Pour MDO.

• La section 7.4 présente l'équilibrage de charge de trafic basé sur les jeux de population dans MEC.

• Le section 7.5 présente les contributions et les travaux futurs.

Chapter