Knowledge Distillation (KD) is considered as an efficient way to replace the parameter averaging in federated learning, aiming to handle the clients with heterogeneous model architectures. Relying on the prepared distillation datasets across clients and the server, KD may encounter impractical difficulties in real-world implementations. Existing works explore the data-free KD in federated learning, which generates the distillation datasets on-site. However, the distillation datasets with global data distribution generated by these state-of-the-art schemes cannot be adapted to local non-IID data. In this article, we propose a new Personalized Data-Free Knowledge Distillation, namely PDKD, for federated learning under heterogeneous models and data. PDKD solves the problem of model drift caused by the inconsistent distribution of distillation datasets and the local data by generating personalized distillation datasets for each client while protecting client data privacy. In addition, we design a distillation dataset update scheme that maximizes the difference between teacher and client outputs on distillation datasets to accomplish deeper knowledge transfer. Furthermore, in order to accomplish the co-evolution of the teacher model and the clients’ model, PDKD incorporates a mutual distillation scheme. Numerous experiments show that PDKD significantly outperforms several state-of-the-art algorithms, with an 18% improvement in prediction accuracy and has a much lower communication cost than the compared algorithms.

Edge AI applications enable edge devices to collaboratively learn a model via repeated model aggregations, aiming to utilize the distributed data on the devices for achieving high model accuracy. Existing methods either leverage a centralized server to directly aggregate the model updates from edge devices or need a central coordinator to group the edge devices for localized model aggregations. The centralized server (or coordinator) has a performance bottleneck and a high cost of collecting the global state needed for making the grouping decision in large-scale networks. In this paper, we propose an Autonomous Model Aggregation (AMA) method for large-scale decentralized learning on edge devices. Instead of needing a central coordinator to group the edge devices, AMA allows the edge devices to autonomously form groups using a highly efficient protocol, according to model functional similarity and historical grouping information. Moreover, AMA adopts a reinforcement learning approach to optimize the size of each group. Evaluation results on our self-developed edge computing testbed demonstrate that AMA outperforms the benchmark approaches by up to 20.71% in accuracy and reduced the convergence time by 75.58%.

Collaborative edge computing enables task execution on the computing resources of geo-distributed edge nodes. One of the key challenges in this field is to realize reliable task offloading by deciding whether to execute tasks locally or delegate them to neighboring nodes while ensuring task reliability. Achieving reliable task offloading is essential for preventing task failures and maintaining optimal system performance. Existing works commonly rely on task redundancy strategies, such as active or passive redundancy. However, these approaches lack adaptive redundancy mechanisms to respond to changes in the network environment, potentially resulting in resource wastage from excessive redundancy or task failures due to insufficient redundancy. In this work, we introduce a novel approach called Hybrid Redundancy for Task Offloading (HRTO) to optimize task latency and reliability. Specifically, HRTO utilizes deep reinforcement learning (DRL) to learn a task offloading policy that maximizes task success rates. With this policy, edge nodes dynamically adjust task redundancy levels based on real-time network load conditions and meanwhile assess whether the task instance is necessary for re-execution in case of task failure. Extensive experiments on real-world network topologies and a Kubernetes-based testbed evaluate the effectiveness of HRTO, showing a 14.6% increase in success rate over the benchmarks.

Collaborative edge computing (CEC) has emerged as a promising paradigm, enabling edge nodes to collaborate and execute tasks from end devices. Task offloading is a fundamental problem in CEC that decides when and where tasks are executed upon the arrival of tasks. However, the mobility of users often results in unstable connections, leading to network failures and resource underutilization. Existing works have not adequately addressed joint mobility-aware dependent task offloading and network flow scheduling, resulting in network congestion and suboptimal performance. To address this, we formulate an online joint mobility-aware dependent task offloading and bandwidth allocation problem, to improve the quality of service by reducing task completion time and energy consumption. We introduce a Mobility-aware Digital Twin-assisted Deep Reinforcement Learning (MDT-DRL) algorithm. Our digital twin model equips the reinforcement learning process by providing future states of mobile users, enabling efficient offloading plans for adapting to the mobile CEC system. Experimental results on real-world and synthetic datasets show that MDT-DRL surpasses state-of-the-art baselines on average task completion time and energy consumption.

Graph representation learning has shown superior performance in numerous real-world applications, such as finance and social networks. Nevertheless, most existing works might make discriminatory predictions due to insufficient attention to fairness in their decision-making processes. This oversight has prompted a growing focus on fair representation learning. Among recent explorations on fair representation learning, prior works based on the adversarial learning usually induce unstable or counterproductive performance. To achieve fairness in a stable manner, we present the design and implementation of graph representation learning based on fairness information bottleneck (GRAFair), a new framework based on a variational graph autoencoder (VGAE). The crux of GRAFair is the conditional fairness bottleneck (CFB), where the objective is to capture the trade-off between the utility of representations and sensitive information of interest. By applying variational approximation, we can make the optimization objective tractable. Particularly, GRAFair can be trained to produce informative representations of tasks while containing little sensitive information without adversarial training. Experiments on various real-world datasets demonstrate the effectiveness of our proposed method in terms of fairness, utility, robustness, and stability.

Edge AI aims to enable distributed machine learning (DML) on edge resources to fulfill the need for data privacy and low latency. Meanwhile, the challenge of device heterogeneity and discrepancy in data distribution requires more sophisticated DML architectures that differ in topology and communication strategy. This calls for a standardized and general programming interface and framework to develop them. Existing frameworks are only meant for specific architectures (e.g., FedML and Flower for Federated Learning) and do not support others by design.

Decentralized task offloading among cooperative edge nodes has been a promising solution to enhance resource utilization and improve users’ Quality of Experience (QoE) in edge computing. However, current decentralized methods, such as heuristics and game theory-based methods, either optimize greedily or depend on rigid assumptions, failing to adapt to the dynamic edge environment. Existing DRL-based approaches train the model in a simulation and then apply it in practical systems. These methods may perform poorly because of the divergence between the practical system and the simulated environment. Other methods that train and deploy the model directly in real-world systems face a cold-start problem, which will reduce the users’ QoE before the model converges. This paper proposes a novel offline-to-online DRL called (O2O-DRL). It uses the heuristic task logs to warm-start the DRL model offline. However, offline and online data have different distributions, so using offline methods for online fine-tuning will ruin the policy learned offline. To avoid this problem, we use on-policy DRL to fine-tune the model and prevent value overestimation. We evaluate O2O-DRL with other approaches in a simulation and a Kubernetes-based testbed. The performance results show that O2O-DRL outperforms other methods and solves the cold-start problem.

Federated learning enables multiple clients to collaboratively learn machine learning models in a privacy-preserving manner. However, in real-world scenarios, a key challenge encountered in federated learning is the statistical heterogeneity among clients. Existing work mainly focused on a single global model shared across the clients, making it hard to generalize well to all clients due to the large discrepancy in the data distributions. To address this challenge, we propose pFedLT , a novel approach that can adapt the single global model to different data distributions. Specifically, we propose to perform a pluggable layer-wise transformation during the local update phase based on scaling and shifting operations. In particular, these operations are learned with a meta-learning strategy. By doing so, pFedLT can capture the diversity of data distribution among clients, therefore, can generalize well even when the data distributions among clients exhibit high statistical heterogeneity. We conduct extensive experiments on synthetic and real-world datasets (MNIST, Fashion_MNIST, CIFAR-10, and Office+Caltech10) under different Non-IID settings. Experimental results demonstrate that pFedLT significantly improves the model accuracy by up to 11.67% and reduces the communication costs compared with state-of-the-art approaches.

Popular ride-hailing products, such as DiDi, Uber and Lyft, provide people with transportation convenience. Pricing, order dispatching and vehicle repositioning are three tasks with tight correlation and complex interactions in ride-hailing platforms, significantly impacting each other’s decisions and demand distribution or supply distribution. However, no past work considered combining the three tasks to improve platform efficiency. In this paper, we exploit to optimize pricing, dispatching and repositioning strategies simultaneously. Such a new multi-stage decision-making problem is quite challenging because it involves complex coordination and lacks a unified problem model. To address this problem, we propose a novelJoint optimization framework ofPricing,Dispatching andRepositioning (JPDR) integrating contextual bandit and multi-agent deep reinforcement learning. JPDR consists of two components, including a Soft Actor-Critic (SAC)-based centralized policy for dispatching and repositioning and a pricing strategy learned by a multi-armed contextual bandit algorithm based on the feedback from the former. The two components learn in a mutually guided way to achieve joint optimization because their updates are highly interdependent. Based on real-world data, we implement a realistic environment simulator. Extensive experiments conducted on it show our method outperforms state-of-the-art baselines in terms of both gross merchandise volume and success rate.

Federated class-incremental learning (FCIL) allows multiple clients in a distributed environment to learn models collaboratively from evolving data streams, where new classes arrive continually at each client. Some existing works in FCIL combine traditional federated learning methods with class-incremental methods. However, the global model affected by data heterogeneity can aggravate local forgetting through the direct combination of traditional methods. To tackle this issue, we propose FCIDF, a novel Federated Class-Incremental learning approach based onDynamic feature extractor Fusion. FCIDF learns personalized and incremental models for each client by introducing personalized fusion rates to integrate global knowledge into local features. Leveragingmeta-learningduring each incremental round, FCIDF ensures involvement of both old and new task knowledge in personalized training. Besides, we further propose a new Storing strategy based on Accumulated Global Feature Means (AGFMS), which helps the model review unbiased old knowledge and compensates for local forgetting. Experiment results show that FCIDF outperforms the baseline methods in both accuracy and forgetting on most settings, and AGFMS improves the performance of FCIDF on most evaluated scales.

Distributed learning on edges aims at training the AI model collaboratively in a network of edge devices via frequent model aggregations. Achieving the desired training performance requires the aggregation structure and frequency to fit well with the dynamic edge environment. Existing works often consider the optimization of either aggregation structure or frequency, assuming that the edge environment is stable and deterministic. In this paper, we propose a novel approach,AutoSF, to automatically optimize the aggregation structure and frequency jointly in dynamic edge computing so as to minimize the global loss function. The main idea of AutoSF is that when the edge environment changes, the automated machine learning approach is triggered to find out the near-optimal aggregation structure and frequency that adapt to time-varying edge resources. When the environment keeps unchanged, a heuristic approach is used to tune the aggregation structure and frequency to further tame the heterogeneity caused by data distributions. We validate the effectiveness of AutoSF via numerical experiments with real datasets on our self-developed edge computing testbed. Evaluation results demonstrate that AutoSF outperforms the benchmark approaches by up to 16.3× speedups in convergence speed and 31.0$\%$increases in training accuracy.

Distributed learning has been increasingly studied in edge computing, enabling edge devices to learn a model collaboratively without exchanging their private data. However, existing approaches assume the private data owned by edge devices are all labeled while the reality is that massive private data are unlabeled and remain to be utilized, which leads to suboptimal performance. To overcome this limitation, we study a new practical problem, Distributed Semi-Supervised Learning (DSSL), to learn models collaboratively with mixed private labeled and unlabeled data on each device. We also propose a novel methodDistMatchthat exploits private unlabeled data by self-training on each device with the help of models from neighboring devices. DistMatch generates pseudo-labels for unlabeled data by properly averaging the predictions of these received models. Furthermore, to avoid self-training with wrong pseudo-labels, DistMatch proposes aconsensus consistencyloss to filter pseudo-labels with high consensus and force the output of the trained model to be consistent with these pseudo-labels. Extensive evaluation results via our self-developed testbed indicate the proposed method outperforms all baselines on commonly used image classification benchmark datasets.

Data heterogeneity across clients is one of the key challenges in Federated Learning (FL), which may slow down the global model convergence and even weaken global model performance. Most existing approaches tackle the heterogeneity by constraining local model updates through reference to global information provided by the server. This can alleviate the performance degradation on the aggregated global model. Different from existing methods, we focus the information exchange between clients, which could also enhance the effectiveness of local training and lead to generate a high-performance global model. Concretely, we propose a novel FL framework named FedCME by client matching and classifier exchanging. In FedCME, clients with large differences in data distribution will be matched in pairs, and then the corresponding pair of clients will exchange their classifiers at the stage of local training in an intermediate moment. Since the local data determines the local model training direction, our method can correct update direction of classifiers and effectively alleviate local update divergence. Besides, we propose feature alignment to enhance the training of the feature extractor. Experimental results demonstrate that FedCME performs better than FedAvg, FedProx, MOON and FedRS on popular federated learning benchmarks including FMNIST and CIFAR10, in the case where data are heterogeneous.

Trustworthy and real-time video surveillance aims to analyze the live camera streams in a privacy-preserving manner for the decision-making of various advanced services, such as pedestrian reidentification and traffic monitoring. In recent years, edge computing has been identified as a promising technology for trustworthy and real-time video surveillance because it keeps confidential video data locally and reduces the latency caused by massive data transmission. Generally, a single edge device can hardly afford the computation-intensive video analytics tasks. Most existing solutions incorporate cloud servers to handle the overloaded tasks. However, such an edge-cloud collaboration approach still suffers from unpredictable latency and privacy concerns because the remote cloud is centralized and distant from the cameras. In this work, we designed a blockchain-based collaborative edge intelligence (BCEI) approach for trustworthy and real-time video surveillance. In BCEI, geo-distributed edge devices form a peer-to-peer network to maintain a permissioned blockchain and share data and computation resources to perform computation-intensive video analytics tasks. The video analytics results are written on the blockchain in an immutable manner to guarantee trustworthiness. To reduce task execution time, we formulate and solve a joint stream mapping and task scheduling problem to schedule video streams and machine learning models among edge devices. A pedestrian reidentification prototype is implemented and deployed based on BCEI with the extensive performance evaluation, indicating the superiority of BCEI in latency reduction and system throughput improvement by leveraging collaboration among edge devices.

Personalized federated learning (PFL) has emerged as a paradigm to provide a personalized model that can fit the local data distribution of each client. One natural choice for PFL is to leverage the fast adaptation capability of meta-learning, where it first obtains a single global model, and each client achieves a personalized model by fine-tuning the global one with its local data. However, existing meta-learning-based approaches implicitly assume that the data distribution among different clients is similar, which may not be applicable due to the property of data heterogeneity in federated learning. In this work, we propose a Group-based Federated Meta-Learning framework, called G-FML , which adaptively divides the clients into groups based on the similarity of their data distribution, and the personalized models are obtained with meta-learning within each group. In particular, we develop a simple yet effective grouping mechanism to adaptively partition the clients into multiple groups. Our mechanism ensures that each group is formed by the clients with similar data distribution such that the group-wise meta-model can achieve “personalization” at large. By doing so, our framework can be generalized to a highly heterogeneous environment. We evaluate the effectiveness of our proposed G-FML framework on three heterogeneous benchmarking datasets. The experimental results show that our framework improves the model accuracy by up to 13.15% relative to the state-of-the-art federated meta-learning.

Federated Learning (FL) has been widely used for distributed machine learning in edge computing. In FL, the model parameters are iteratively aggregated from the clients to a central server, which is inclined to be the communication bottleneck and single point of failure. To solve these drawbacks, hierarchical model training frameworks like Hierarchical Federated Learning (HFL) and E-Tree learning have been proposed. One of the most challenging problems in the hierarchical model training framework is optimizing the aggregation frequencies of the edge devices at various levels. Because, in an edge computing environment, heterogeneity in the resource can introduce synchronization delays caused by waiting for slow workers and significantly impact the training performance. This paper tackles the problem with weak synchronization where edge devices on the same level have different frequencies on local updates and/or model aggregations. Existing works based on weak synchronization lack solutions to quantitatively determine the aggregation frequencies of each edge device. Thus, we propose a resource-based aggregation frequency controlling method, termed RAF, which determines the optimal aggregation frequencies of edge devices to minimize the loss function according to heterogeneous resources. Our proposed method can alleviate the waiting time and fully utilize the resources of the edge devices. Besides, RAF dynamically adjusts the aggregation frequencies at different phases during the model training to achieve fast convergence speed and high accuracy. We evaluated the performance of RAF via extensive experiments with real datasets on our self-developed edge computing testbed. Evaluation results demonstrate that RAF outperforms the benchmark approaches in terms of learning accuracy and convergence speed.

As a key enabler of future 5G network, Service Function Chain (SFC) forwards the traffic flow along a chain of Virtual Network Functions (VNFs) to provide network services flexibility. One of the most important problems in SFC is to deploy the VNFs and schedule arriving requests among computing nodes to achieve low latency and high reliability. Existing works consider a static network and assume that all SFC requests are known in advance, which is impractical. In this paper, we focus on the dynamic 5G network environment where the SFC request arrives randomly following a certain distribution. Computing nodes can redeploy all types of VNF with a time cost. We formulate the problem of SFC scheduling in NFV-enabled 5G network as a mixed integer non-linear programing. The objective is to maximize the number of requests satisfying the latency and reliability constraints. To solve the problem, we propose an efficient algorithm to decide the redundancy of the VNFs while minimizing delay. Then we present a state-of-art Reinforcement Learning (RL) to learn SFC scheduling policy to increase the success rate of SFC requests. The effectiveness of our method is evaluated through extensive simulations. The result shows that our proposed RL solution can increase the success rate by 18.7% over the benchmark algorithms.

Spatial crowdsourcing as a promising computing paradigm has received significant attention recently. A fundamental issue of spatial crowdsourcing is online task assignment, i.e., the platform must make decisions immediately (assign or reject) for newly arriving objects (tasks or workers). Previous studies mostly focus on the rejection-aware assignment, which rarely considers non-rejection assignment for new arrival objects. To solve this new allocation model, in this paper, we first formulate a novel problem, namely Online Non-rejection aware Task Assignment (ONRTA) in spatial crowdsourcing, where an object cannot be rejected by the platform as long as there is a neighbor that satisfies the matching constraint with it. Then, we develop a non-rejection threshold-based random algorithm ONRTA-RT under the adversarial order model while obtaining a theoretical bound on the competitive ratio. More importantly, we consider a more natural random order model and propose a two-stage-based non-rejection aware task assignment approach, ONRTA-Base, which achieves a competitive ratio of$\frac{1}{4}$. Based on this framework, we further devise two non-rejection assignment approaches, ONRTA-OP and ONRTA-Greedy, which are more effective and run faster with a competitive ratio of$\frac{1}{4}$and$\frac{1}{8}$, respectively. Finally, experiments on synthetic and real datasets demonstrate that our proposed methods outperform the representative methods.

Spatial crowdsourcing platforms have become increasingly popular in people's daily life. A fundamental problem in spatial crowdsourcing is task assignment, which assigns spatial tasks to the workers appropriately in order to satisfy certain objectives. Previous studies usually focus on the real-time micro-task allocation, which does not consider the dependency relationships among tasks. To address this limitation, in this article, we define and formulate a new problem, called Online Dependent Task Assignment (ODTA) in preference aware spatial crowdsourcing. We first prove that ODTA is$\mathcal {NP}$-hard. Then, we design a threshold-based algorithm in the adversarial order model and obtain a near-optimal theoretical bound on the competitive ratio. More importantly, considering the random order arrival model, we further present three algorithms based on a two-stage framework, namely ODTA-Greedy, ODTA-Greedy-OP and ODTA-OPT, which are more effective with a constant competition ratio of$\frac{1}{8}$,$\frac{1}{8}$and$\frac{1}{4}$, respectively. Experimental results on both synthetic and real datasets show that our proposed ODTA-OPT approach outperforms the representative approaches in terms of overall utility.

Collaborative edge computing (CEC) is an emerging paradigm enabling sharing of the coupled data, computation, and networking resources among heterogeneous geo-distributed edge nodes. Recently, there has been a trend to orchestrate and schedule containerized application workloads in CEC, while Kubernetes has become the de-facto standard broadly adopted by the industry and academia. However, Kubernetes is not preferable for CEC because its design is not dedicated to edge computing and neglects the unique features of edge nativeness. More specifically, Kubernetes primarily ensures resource provision of workloads while neglecting the performance requirements of edge-native applications, such as throughput and latency. Furthermore, Kubernetes neglects the inner dependencies of edge-native applications and fails to consider data locality and networking resources, leading to inferior performance. In this work, we design and develop ENTS, the first edge-native task scheduling system, to manage the distributed edge resources and facilitate efficient task scheduling to optimize the performance of edge-native applications. ENTS extends Kubernetes with the unique ability to collaboratively schedule computation and networking resources by comprehensively considering job profile and resource status. We showcase the superior efficacy of ENTS with a case study on data streaming applications. We mathematically formulate a joint task allocation and flow scheduling problem that maximizes the job throughput. We design two novel online scheduling algorithms to optimally decide the task allocation, bandwidth allocation, and flow routing policies. The extensive experiments on a real-world edge video analytics application show that ENTS achieves 43% -220% higher average job throughput compared with the state-of-the-art.

The new computation technologies, such as big data analytics, modern machine learning technology, artificial intelligence (AI), blockchain, and security processing, have the great potential to be embedded into network to enable it to be intelligent and trustworthy. On the other hand, Information-Centric Networking (ICN), software-defined network (SDN), network function virtualization (NFV), network slicing, and data center network have emerged as the novel networking paradigms for fast and efficient delivering and retrieving data. Against this backdrop, there is a strong trend to move the computations from the cloud to not only the edges but also the resource-sufficient networking nodes, which triggers the convergence between the emerging networking concepts and the new computation technologies.

Deep Learning (DL) is an essential technology for modern intelligent sensor network and interactive multimedia applications, having problems with user data privacy when training on a central cloud. While Federated Learning (FL) motivates to preserve user privacy, it also causes new problems of lower user terminal usability and training efficiency, which caused substantial energy consumption. This article proposes a novel energy-efficient and privacy-aware decomposition framework to improve user-side FL efficiency under pre-defined privacy requirements with the assistance of Mobile Edge Computing (MEC) and Software Decomposition. It takes the propagation of each neural layer as the migrating unit and considers the tradeoff relationship between privacy and efficiency. We also propose an online scheduling algorithm to optimize the framework’s training performance. Furthermore, we summarize eight privacy-sensitive information classes on which existing privacy attacks base and design configurable privacy preservation mechanisms for each class. Simulations and experiments prove the effectiveness of our framework and algorithm in FL efficiency improvement and the effects of different privacy constraints on the overall training efficiency.

Distributed Machine Learning (DML) at the edge has become an essential topic for providing low-latency intelligence near the data sources. However, both the development and testing of DMLs lack sufficient support. Reusable libraries that abstract the general functionalities of DMLs are needed for rapid development. Moreover, existing physical testbeds are usually small and lack network flexibility, while virtual testbeds like simulators and emulators lack fidelity. This paper proposes a novel hybrid testbed EdgeTB, which provides numerous emulated nodes to generate large-scale and network-flexible test environments while incorporating physical nodes to guarantee fidelity. EdgeTB manages physical nodes and emulated nodes uniformly and supports arbitrary network topologies between nodes through dynamic configurations. Importantly, we propose Role-oriented development to support the rapid development of DMLs. Through case studies and experiments, we demonstrate that EdgeTB provides convenience for efficiently developing and testing DMLs in various structures with high fidelity and scalability.

Computation partitioning is an important technique to improve the application performance by selectively offloading some computations from the mobile devices to the nearby edge cloud. In a dynamic environment in which the network bandwidth to the edge cloud may change frequently, the partitioning of the computation needs to be updated accordingly. The frequent updating of partitioning leads to high state migration cost between the mobile side and edge cloud. However, existing works don’t take the state migration overhead into consideration. Consequently, the partitioning decisions may cause significant network congestion and increase overall completion time tremendously. In this article, with considering the state migration overhead, we propose a set of novel algorithms to update the partitioning based on the changing network bandwidth. To the best of our knowledge, this is the first work on computation partitioning for stateful data stream applications in dynamic environments. The algorithms aim to alleviate the network congestion and minimize the make-span through selectively migrating state in dynamic edge cloud environments. Extensive simulations show our solution not only could selectively migrate state but also outperforms other classical benchmark algorithms in terms of make-span. The proposed model and algorithms will enrich the scheduling theory forstatefultasks, which has not been explored before.

Recent on-demand services, such as Uber and DiDi, provide a platform for users to request services on the spot and for suppliers to meet such demand. In such platforms, demands are dispatched to suppliers round by round, and suppliers have autonomy to decide whether to accept demands or not. Existing approaches dispatch a demand to multiple suppliers in each round, while a supplier can only receive one demand. However, by using these approaches, pended demands can not be fully dispatched in a round specially when suppliers are not sufficient, and thus need to wait for many rounds to be dispatched, leading to long response time. In this paper, we propose a novel demand dispatching model, named by many-to-many model. The novelty of the model is that a supplier could receive multiple demands in a round, such that the demand has high chance to be dispatched and answered within short time. More specifically, we first learn the probability distribution function of the response time of a supplier to a given demand, by considering the features of both the demand and the supplier. Taking the learned results as input, our model generates an optimal matching between the demands and suppliers to minimize the overall response time of the demands via solving an optimization problem. Experiments on real-world datasets show that our model is better than the start-of-art models in terms of successful acceptance rate and response time.

As a key enabler of future 5G network, Service Function Chain (SFC) forwards the traffic flow along a chain of Virtual Network Functions (VNFs) to provide network services flexibility. One of the most important problems in SFC is to deploy the VNFs and schedule arriving requests among computing nodes to achieve low latency and high reliability. Existing works consider a static network and assume that all SFC requests are known in advance, which is impractical. In this paper, we focus on the dynamic 5G network environment where the SFC requests arrive randomly and the computing nodes can redeploy all types of VNF with a time cost. We formulate the problem of SFC scheduling in NFV-enabled 5G network as a mixed integer non-linear programing. The objective is to maximize the number of requests satisfying the latency and reliability constraints. To solve the problem, we propose an efficient algorithm to decide the redundancy of the VNFs while minimizing delay. Then we present a state-of-art Reinforcement Learning (RL) to learn SFC scheduling policy to increase the success rate of SFC requests. The effectiveness of our method is evaluated through extensive simulations. The result shows that our proposed RL solution can increase the success rate by 18.7% over the benchmarks.

Time-Sensitive Networking (TSN) standards were proposed to deliver real-time data with deterministic delay. TSN realizes the deterministic delivery of time-sensitive traffic by establishing virtual channels with specific cycle intervals. However, existing work does not consider the reliable delivery of time-sensitive traffic. In addition, existing work generally considers scheduling in the ideal environment, and cannot handle random events such as network jitter and packet loss. In the paper, we introduce path redundancy and seamless redundancy as the basis of reliability, and propose reliable routing and scheduling problems with objectives to achieve good network throughput and link load balancing. We propose a routing heuristic and a scheduling heuristic to generate redundant transmission paths and schedules for time-sensitive traffic, respectively. Further, we propose a joint optimization algorithm to optimize the feasible solutions produced by routing and scheduling. In particular, we improve the scheduling mechanism of TSN, so that the our scheduling algorithm can adapt to the random and dynamic events in real network. Evaluations were carried out in several test cases with a self-developed TSN testbed. The results show our approaches can efficiently achieve good network throughput and link load balancing while ensuring time-space reliability.

Collaborative edge computing (CEC) is a recently popular paradigm enabling sharing of data and computation resources among different edge devices. Task offloading is an important problem to address in CEC as we need to decide when and where each task is executed. However, it is challenging to solve task offloading in CEC as tasks can be offloaded to a multihop neighboring device leading to bandwidth contention among network flows. Most existing works do not jointly consider network flow scheduling that can lead to network congestion and inefficient performance in terms of completion time. Another challenge is to formulate and solve the problem considering the dependencies among dependent tasks and conflicting network flows. Few recent works have considered multihop computation offloading; however, these works focus on independent tasks and do not jointly consider the dependencies with network flows. In this work, we mathematically formulate the problem of jointly offloading multiple tasks consisting of dependent subtasks and network flow scheduling in CEC to minimize the average completion time of tasks. We have proposed a joint dependent task offloading and flow scheduling heuristic (JDOFH) that considers both dependencies in task directed acyclic graph and start time of network flows. Performance comparison done using simulation for both real application task graph and simulated task graphs shows that JDOFH leads to up to 85% improvement in average completion time compared to benchmark solutions which do not make a joint decision.

Traditionally, Artificial Intelligence (AI) models are trained on the central cloud with data collected from end devices. This leads to high communication cost, long response time, and privacy concerns. Recently Edge-empowered AI, namely, Edge AI, has been proposed to support AI model learning and deployment at the network edge closer to the data sources. Existing research, including federated learning adopts a centralized architecture for model learning, where a central server aggregates the model updates from the clients/workers. The centralized architecture has drawbacks, such as performance bottleneck, poor scalability, and single point of failure. In this article, we propose a novel decentralized model learning approach, namely, E-Tree, which makes use of a well-designed tree structure imposed on the edge devices. The tree structure and the locations and orders of the aggregation on the tree are optimally designed to improve the training convergency and model accuracy. In particular, we design an efficient device clustering algorithm, named by K-Means and average accuracy, for E-Tree by taking into account the data distribution on the devices as well as the network distance. Evaluation results show that E-Tree significantly outperforms the benchmark approaches, such as federated learning and gossip learning under nonindependently and identically distributed (Non-i.i.d.) data in terms of model accuracy and convergency.

Autonomous on-demand services, such as GOGOX (formerly GoGoVan) in Hong Kong, provide a platform for users to request services and for suppliers to meet such demands. In such a platform, the suppliers have autonomy to accept or reject the demands to be dispatched to him/her, so it is challenging to make an online matching between demands and suppliers. Existing methods use round-based approaches to dispatch demands. In these works, the dispatching decision is based on the predicted response patterns of suppliers to demands in the current round, but they all fail to consider the impact of future demands and suppliers on the current dispatching decision. This could lead to taking a suboptimal dispatching decision from the future perspective. To solve this problem, we propose a novel demand dispatching model using deep reinforcement learning. In this model, we make each demand as an agent. The action of each agent, i.e., the dispatching decision of each demand, is determined by a centralized algorithm in a coordinated way. The model works in the following two steps. (1) It learns the demand’s expected value in each spatiotemporal state using historical transition data. (2) Based on the learned values, it conducts a Many-To-Many dispatching using a combinatorial optimization algorithm by considering both immediate rewards and expected values of demands in the next round. In order to get a higher total reward, the demands with a high expected value (short response time) in the future may be delayed to the next round. On the contrary, the demands with a low expected value (long response time) in the future would be dispatched immediately. Through extensive experiments using real-world datasets, we show that the proposed model outperforms the existing models in terms of Cancellation Rate and Average Response Time.

Collaborative edge computing (CEC) is a recent popular paradigm where different edge devices collaborate by sharing data and computation resources. One of the fundamental issues in CEC is to make task offloading decision. However, it is a challenging problem to solve as tasks can be offloaded to a device at multi-hop distance leading to conflicting network flows due to limited bandwidth constraint. There are some works on multi-hop computation offloading problem in the literature. However, existing works have not jointly considered multi-hop partial computation offloading and network flow scheduling that can cause network congestion and inefficient performance in terms of completion time. This article formulates the joint multi-task partial computation offloading and network flow scheduling problem to minimize the average completion time of all tasks. The formulated problem optimizes several dependent decision variables including partial offloading ratio, remote offloading device, start time of tasks, routing path, and start time of network flows. The problem is formulated as an MINLP optimization problem and shown to be NP-hard. We propose a joint partial offloading and flow scheduling heuristic (JPOFH) that decides partial offloading ratio by considering both waiting times at the devices and start time of network flows. We also do the relaxation of formulated MINLP problem to an LP problem using McCormick envelope to give a lower bound solution. Performance comparison done using simulation shows that JPOFH leads to up to 32 percent improvement in average completion time compared to benchmark solutions which do not make a joint decision.

Mobile edge computation partitioning is an effective technique to improve the applications performance on the mobile devices by selectively offloading some computations from the devices to the nearby edge cloud. Most previous works focus on the computation partitioning for a single user. Recent works begin to study the computation partitioning in a multiple user environment in which a number of users compete for the constrained computation resources on the edge cloud. However, these works neglect the fact that the users normally also share the network resources to access the edge cloud, and thus the allocation of bandwidth to the users significantly affects the overall performance of the users. In this paper, we studynetwork aware mobile edge computation partitioning in multi-user environments, i.e., to decide for each user which parts of the application should be offloaded onto the edge cloud, and which others should be executed locally, and meanwhile to allocate the access bandwidth among the users, such that the average application performance of the users is maximized. This problem is new in that we consider the competition among users for the network bandwidth as well as the computation resources in a multi-user environment. With a set of novel models and formulations, we transform the problem into the classic Multi-class Multi-dimensional Knapsack Problem, and develop an effective algorithm, namely Performance Function Matrix based Heuristic (PFM-H), to solve it. We further consider the user mobility and design effective online algorithms that could be easily deployed in practical systems. Comprehensive trace driven simulations show that our proposed algorithm outperforms the benchmark algorithms significantly in the average application performance.

The proliferation of mobile devices and ubiquitous access of the wireless network enable many new mobile applications such as augmented reality, mobile gaming and so on. As the applications are latency sensitive, researchers propose to offload the complex computations of these applications to the nearby edge cloud, in order to reduce the latency. Existing works mostly consider the problem of partitioning the computations between the mobile device and the traditional cloud that has abundant resources. The proposed approaches can not be applied in the context of mobile edge cloud, because both the resources in the mobile edge cloud and the wireless access bandwidth to the edge cloud are constrained. In this paper, we studyjoint computation partitioning and resource allocation problemfor latency sensitive applications in mobile edge clouds. The problem is novel in that we combine the computation partitioning and the two-dimensional resource allocations in both the computation resources and the network bandwidth. We develop a new and efficient method, namely Multi-Dimensional Search and Adjust (MDSA), which is an offline algorithm, to solve the problem. We compare MDSA with the classic list scheduling method and theSearchAdjustalgorithm via comprehensive simulations. The results show that MDSA outperforms the benchmark algorithms in terms of the overall application latency. Moreover, we also design an online method, named by Cooperative Online Scheduling (COS), which can be easily deployed in practical systems. By extensive evaluations, we show that COS outperforms the benchmark methods by 25 percent on average.

Data shuffling can improve the statistical performance of distributed machine learning. However, the obstruction of applying data shuffling is the high communication cost. Existing works use coding technology to reduce communication cost. These works assume a master-worker based storage architecture. However, due to the demand for unlimited storage on the master, the master-worker storage architecture is not always practical in common data centers. In this paper, we propose a new coding method for data shuffling in the decentralized storage architecture, which is built on a fat-tree based data center network. The method determines which data samples should be encoded together and from which the encoded package should be sent to minimize the communication cost. We develop a real-world test-bed to evaluate our method. The results show that our method can reduce the transmission time by 6.4% over the state-of-art coding method, and by 27.8% over Unicasting.

Mobile-edge nodes, as an efficient approach to the performance improvement of wireless sensor networks (WSNs), play an important role in edge computing. However, existing works only focus on connected networks and suffer from high calculational costs. In this article, we propose a rendezvous selection strategy for data collection of disjoint WSNs with mobile-edge nodes. The goal is to achieve full network connectivity and minimize path length. From the perspective of the application scenario, this article is distinctive in two aspects. On the one hand, it is specially designed for partitioned networks which are much more complex than conventional connected scenarios. On the other hand, this article is specially designed for delay-harsh applications rather than usual energy-oriented scenarios. From the viewpoint of the implementation method, a simplified ant colony optimization (ACO) algorithm is performed and displays two characteristics. The first one is the path segmenting mechanism, simplifying the path construction of each part and consequently reducing the computational cost. The second one is the candidate grouping mechanism, reducing the search space and accordingly speeding up the convergence speed. Simulation results demonstrate the feasibility and advantages of this approach.

Connectivity restoration plays an important role in maintaining the long-term operation in wireless sensor networks (WSNs), especially, in environment-harsh cases. However, current solutions lack the ability to handle the second damages and the capacity of designing requirement-different connectivity approaches according to different needs. In this article, we propose a durability-based connectivity establishment (DBCE) scheme for disjoint segments of WSNs. This scheme includes three approaches regarding segment evaluation or segment selection: 1) a segment shape evaluation approach; 2) a region different connectivity approach; and 3) a data traffic transfer approach, for their respective objectives. The unique characteristics of this article are twofold. On the one hand, this is the first attempt to investigate segment shapes, which we demonstrate have great impact on the robustness of the network. On the other hand, distinguished from the existing networks with uniform connectivity rule, the network is divided into two parts and different connectivity sequences and connectivity approaches are designed according to disparate features and requirements of the network. The performance of DBCE is validated through extensive simulation experiments.

Automatic driving services have large volume, location-aware, and time-changing contents, which are suitable to be cached by the edge. However, the traffic on the edge will be extremely high especially in the area with high vehicle density, if the vehicles directly access the contents from the edge as they demand. A hybrid data dissemination model with both vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) disseminations has been proposed to reduce the traffic on the edge, in which the edge (infrastructure) selectively injects data to the vehicles and leverages the vehicle network to disseminate the data. In this article, we study the hybrid data dissemination problem, i.e., to optimally determine when and which vehicle the data are injected into, and whether the vehicle acquires the demanded data directly from the edge or from nearby neighbors, with the aim of minimizing the traffic cost on the edge and meeting the deadlines of acquiring the data. Existing approach prioritizes the selection of V2I disseminations at first and then explores the V2V disseminations which have no conflict with the V2I disseminations. This approach cannot fully take advantage of V2V to reduce the traffic cost on the edge. We propose a new data dissemination algorithm, named the offline algorithm for hybrid data dissemination (OFDD), which seeks the most beneficial V2V broadcasts with priority, and then choose feasible V2I disseminations. Based on OFDD, we develop both the snapshot and prediction-based online algorithms. We follow with extensive simulations to validate the proposed algorithms. The results show that our algorithms significantly outperform the state-of-the-art approaches in terms of data acquisition rate and traffic cost.

Data collection with mobile elements can greatly improve the load balance degree and accordingly prolong the longevity for wireless sensor networks (WSNs). In this pattern, a mobile sink generally traverses the sensing field periodically and collect data from multiple Anchor Points (APs) which constitute a traveling tour. However, due to long-distance traveling, this easily causes large latency of data delivery. In this paper, we propose a path planning strategy of mobile data collection, called the Dual Approximation of Anchor Points (DAAP), which aims to achieve full connectivity for partitioned WSNs and construct a shorter path. DAAP is novel in two aspects. On the one hand, it is especially designed for disconnected WSNs where sensor nodes are scattered in multiple isolated segments. On the other hand, it has the least calculational complexity compared with other existing works. DAAP is formulated as a location approximation problem and then solved by a greedy location selection mechanism, which follows two corresponding principles. On the one hand, the APs of periphery segments must be as near the network center as possible. On the other hand, the APs of other isolated segments must be as close to the current path as possible. Finally, experimental results confirm that DAAP outperforms existing works in delay-tough applications.

Edge computing recently attracts the industry and academic attentions due to its advantage of providing low latency services in a much closer place to the end users. This paper studies the problem of computation partitioning in future 5G-based edge computing environments. Although the problem has been studied a lot in (mobile) cloud computing, the problem in this paper is different with previous works. Traditional partitioning approaches in cloud computing aim to achieve an optimal tradeoff between the network transmission cost and the local computation cost, because the data transmission to cloud is very costly. However, in future 5G-based edge computing, the high bandwidth and low latency will overcome the data transmission challenge. Instead the constrained computation capability of the edge will greatly affect the performance of an partitioned execution of the application. As the challenge changes, we propose a new partitioning model, which parallelizes the computations and fully utilizes the computational resources on the edge and end devices. We develop an off-line solution for partitioning and scheduling the computation to the resources. We prove in theory that our off-line solution achieves the optimal performance. Based on the off-line solution, we further develop a set of online algorithms, and conduct extensive simulations to show that our proposed online algorithms significantly outperform the benchmark algorithms.

The recent trend in the Internet of Things (IoT) is to distribute and move the computation from centralized cloud devices to edge devices which are closer to data sources. Researchers have proposed collaborative edge computing for IoT where the data and computation tasks are shared among a network of edge devices. One of the important problems in collaborative edge computing is to schedule tasks among edge devices to minimize latency and other performance metrics. Compared to existing works in wireless sensor networks and IoT, there are two additional challenges while scheduling tasks in collaborative edge computing. First, we need to consider the transfer of input data required by different tasks as the data is generated by sensing devices which are located at different geographical places. Second, existing works solve the problem of task scheduling without considering network flow scheduling which can lead to network congestion and long completion times. In this paper, we study the data-aware task allocation problem to jointly schedule task and network flows in collaborative edge computing. We mathematically model the joint problem to minimize the overall completion time of the application. We have proposed a multistage greedy adjustment (MSGA) algorithm where the task scheduling is done by considering both placement of tasks and adjustment of network flows. Performance comparison done using simulation shows that MSGA leads to up to 27% improvement in completion time as compared to benchmark solutions.

Privacy is a pivotal issue of mobile apps because there is a plethora of personal and sensitive information in smartphones. Many mechanisms and tools are proposed to detect and mitigate privacy leaks. However, they rarely consider users' preferences and expectations. Users hold various expectation towards different mobile apps. For example, users may allow a social app to access their photos rather than a game app because it goes beyond users' expectation to access personal photos. Therefore, we believe it is practical and beneficial to understand users' privacy expectations on various mobile apps and help them mitigate privacy risks introduced by smartphones. To achieve this objective, we propose and implement PriWe, a system based on crowdsourcing driven by users who contribute privacy permission settings of the apps installed on their smartphones. PriWe leverages the crowdsourced permission settings to understand users' privacy expectations and provides app specific recommendations to mitigate information leakage. We deployed PriWe in the real world for evaluation. According to the feedback of 78 users who evaluated our system and 422 participants who completed our survey, PriWe is able to make proper recommendations which can match participants' privacy expectations and are mostly accepted by users, thereby help them to mitigate privacy disclosure in smartphones.

People nowadays almost want everything at their fingertips, from business to entertainment, and meanwhile they do not want to leak their sensitive data. Strong information protection can be a competitive advantage, but preserving privacy is a real challenge when people use the mobile apps in the smartphone. If they are too lax with privacy preserving, important or sensitive information could be lost. If they are too tight with privacy, making users jump through endless hoops to access the data they need to get their work done, productivity can nosedive. Thus, striking a balance between privacy and usability in mobile applications can be difficult. Leveraging the privacy permission settings in mobile operating systems, our basic idea to address this issue is to provide proper recommendations about the settings so that the users can preserve their sensitive information and maintain the usability of apps. In this paper, we propose an unobtrusive recommendation system to implement this idea, which can crowdsource users' privacy permission settings and generate the recommendations for them accordingly. Besides, our system allows users to provide feedback to revise the recommendations for getting better performance and adapting different scenarios. For the evaluation, we collected users' preferences from 382 participants on Amazon Technical Turks and released our system to users in the real world for 10 days. According to the study, our system can make appropriate recommendations which can meet participants' privacy expectation and mobile apps' usability.

The proliferation of mobile devices and ubiquitous access of the wireless network enables many new mobile applications such as augmented reality, mobile gaming and so on. As the applications are latency sensitive, researchers propose to off load the complex computations of these applications to the nearby mobile edge cloud, in order to reduce the latency. Existing works mostly consider the problem of partitioning the computations between the mobile device and the traditional cloud that has abundant resources. The proposed approaches can not be applied in the context of mobile edge cloud, because both the resources in the mobile edge cloud and the wireless access bandwidth to the edge cloud are constrained. In this paper, we study joint computation partitioning and resource allocation problem for latency sensitive applications in mobile edge clouds. The problem is novel in that we combine the computation partitioning and the two-dimensional resource allocations in both the computation resources and the network bandwidth. We develop a new and efficient method, namely Multi-Dimensional Search and Adjust (MDSA), to solve the problem. We compares MDSA with the classic list scheduling method and the Search Adjust algorithm via comprehensive simulations. The results show that MDSA outperforms the benchmark algorithms in terms of the overall application latency.

Mobile edge cloud has been increasingly concerned by researchers due to its closer distance to mobile users than the traditional cloud on Internet. Offloading computations from mobile devices to the nearby edge cloud is an effective technique to accelerate the applications and/or save energy on the mobile devices. However, the mobile edge cloud usually has limited computation resources and constrained access bandwidth shared by multiple users in its proximity. Thus, allocation of resources and bandwidth among the users is significant to the overall application performance. In this paper, we study network aware multi-user computation partitioning problem in mobile edge clouds, i.e., to decide for each user which parts of the application should be offload onto the edge cloud, and which others should be executed locally, and meanwhile to allocate the access bandwidth among the users, such that the average application performance of the users is maximized. This problem is novel in that we consider the competition among users for both computing resources and bandwidth, and jointly optimizes the partitioning decisions with the allocation of resources and bandwidths among users, while most existing works either focus on the single user computation partitioning or study the multiple user computation partitioning without regard of the constrained network bandwidth. We first formulate the problem, and then transform it into the classic Multi-class Multi-dimensional Knapsack Problem and develop an effective algorithm, namely Performance Function Matrix based Heuristic (PFM-H), to solve it. Comprehensive simulations show that our proposed algorithm outperforms the benchmark algorithms significantly in the average application performance.

Interactive mobile applications attract lots of attentions recently. They utilize complex algorithms (e.g., machine learning) to provide advanced functions (e.g., object recognition), thus lead to long response time while running on mobile devices. To reduce the response time, researchers propose offloading some compute-intensive parts of mobile applications onto cloud. Existing works aim to optimize general performance (e.g., response time), but ignore the enhancement of application quality (e.g., recognition accuracy), which is also critical to user experience. In this paper, we develop AppBooster, a mobile cloud platform which boosts both general performance and application quality for interactive mobile applications. AppBooster jointly leverages the quality adaptation, computation offloading and parallel speedup to boost the comprehensive performance, which is defined by developers based on the metrics of application quality and general performance. Through combining history-based platform-learned knowledge, developer-provided information and the platform-monitored environment conditions (e.g., workload, network), AppBooster manages applications with optimal computation partitioning scheme and tunable parameter setting thus obtain high comprehensive performance. We evaluate AppBooster with an object recognition application in various network conditions and show AppBooster can significantly boost application performance and obtain 1.3 to 3.5 times better performance than existing strategies.

With proliferation of smart phones and an increasing number of services provisioned by clouds, it is commonplace for users to request cloud services from their mobile devices. Accessing services directly from the Internet data centers inherently incurs high latency due to long RTTs and possible congestions in WAN. To lower the latency, some researchers propose to `cache' the services at edge clouds or smart routers in the access network which are closer to end users than the Internet cloud. Although `caching' is a promising technique, placing the services and dispatching users' requests in a way that can minimize the users' access delay and service providers' cost has not been addressed so far. In this paper, we study the joint optimization of service placement and load dispatching in the mobile cloud systems. We show this problem is unique to both the traditional caching problem in mobile networks and the content distribution problem in content distribution networks. We develop a set of efficient algorithms for service providers to achieve various trade-offs among the average latency of mobile users' requests, and the cost of service providers. Our solution utilizes user's mobility pattern and services access pattern to predict the distribution of user's future requests, and then adapt the service placement and load dispatching online based on the prediction. We conduct extensive trace driven simulations. Results show our solution not only achieves much lower latency than directly accessing service from remote clouds, but also outperforms other classical benchmark algorithms in term of the latency, cost and algorithm running time.

As mobile computing increasingly interacts with the cloud, a number of approaches, e.g., MAUI and CloneCloud, have been proposed, aiming to offload parts of the mobile application execution to the cloud. To achieve a good performance by using these approaches, they particularly focus on the application partitioning problem, i.e., to decide which parts of an application should be offloaded to the cloud and which parts should be executed on mobile devices such that the execution cost is minimized. Most works on this problem assume that the offloading cost of each part of the application remains the same as the application is running. Unfortunately, this assumption does not hold in dynamic mobile cloud environments, where the device and network connection status may fluctuate, and thus affects the offloading cost. With the varying offloading cost, the one time partitioning of the application may yield significant performance degradations. In this paper, we study application repartitioning problem which considers updating the partition periodically during the course of application execution. We first propose a framework for run time application repartitioning in dynamic mobile cloud environments. Based on this framework, we take the dynamic network connection to clouds as a case study, and design an online solution, Foreseer, to solve the mobile cloud application repartitioning problem. We evaluate our solution based on real world data traces that are collected in a campus WiFi hotspot testbed. The result shows that our method can achieve significantly shorter completion time over previous approaches.

Elastic partitioning of computations between mobile devices and cloud is an important and challenging research topic for mobile cloud computing. Existing works focus on the single-user computation partitioning, which aims to optimize the application completion time for one particular single user. These works assume that the cloud always has enough resources to execute the computations immediately when they are offloaded to the cloud. However, this assumption does not hold for large scale mobile cloud applications. In these applications, due to the competition for cloud resources among a large number of users, the offloaded computations may be executed with certain scheduling delay on the cloud. Single user partitioning that does not take into account the scheduling delay on the cloud may yield significant performance degradation. In this paper, we study, for the first time, multi-user computation partitioning problem (MCPP), which considers the partitioning of multiple users’ computations together with the scheduling of offloaded computations on the cloud resources. Instead of pursuing the minimum application completion time for every single user, we aim to achieve minimum average completion time for all the users, based on the number of provisioned resources on the cloud. We show that MCPP is different from and more difficult than the classical job scheduling problems. We design an offline heuristic algorithm, namelySearchAdjust, to solve MCPP. We demonstrate through benchmarks thatSearchAdjustoutperforms both the single user partitioning approaches and classical job scheduling approaches by 10 percent on average in terms of application delay. Based onSearchAdjust, we also design an online algorithm for MCPP that can be easily deployed in practical systems. We validate the effectiveness of our online algorithm using real world load traces.

RFID technology has been widely used for object tracking in indoor environment due to their low cost and convenience for deployment. In this paper, we consider RFID reader tracking which refers to continuously locating a mobile object by attaching it with a RFID reader that communicates with passive RFID tags deployed in the environment. One difficulty is that the RFID readings gathered from the environment are often noisy. Existing approaches for tracking with noisy RFID readings are mostly based on using Particle Filter (PF). However, continuous execution of PF has extremely high computational cost, and may be difficult to be done on mostly resource constrained mobile RFID devices. In this paper, we propose a hybrid method which combines PF with Weighted Centroid Localization (WCL) to achieve high accuracy and low computational cost. Our observation is that WCL has the same accuracy with PF with much lower cost if the object's velocity is low. Our method has two critical features. The first feature is adaptive switching between using WCL and PF based on the estimated velocity of the mobile object. The second feature is the further reduction of computational cost by offloading costly PF algorithm onto nearby servers. We evaluate the performance of our method through extensive simulations and experiments in two real world applications, namely, indoor wheelchair navigation and in-station Light Rail Vehicle (LRV) tracking at one of Hong Kong MTR depots. The result shows that our proposed approach has significantly less computational cost than existing PF based methods, while being as accurate as them.

Resource prediction (e.g. CPU/memory utilization) of cloud computing jobs has attracted substantial amount of attention. Existing works use regression methods based on historical information of jobs, with an impractical assumption that the job to be predicted has the same class as the historical jobs. To address this problem, we propose to take the category of the jobs into consideration for effective resource prediction. Existing works on job classification either ignores the temporal variance of resource consumption during job execution or use it in a naive way, resulting in unsatisfactory classification accuracy and/or slow speed. In this paper, we introduce a new and efficient job classification approach, called Bejo. Inspired by the textual document classification methods, which use distribution of text words to describe and classify a document, Bejo treats the job as a document, assigns each collected resource consumption snapshot to a certain "resource word", and uses the distribution of the words to describe and classify a job. An ℓ1norm minimization formulation is used to assign each resource snapshot to a resource word, to especially address the unique challenges of high noise and tight time budget of cloud job classification. We collect a comprehensive dataset for job classification and resource consumption prediction on cloud platforms, and demonstrate superior quality and efficiency of Bejo over state-of-the-art algorithms. Experiments also show the relative error of resource consumption prediction can be dramatically reduced by adding an extra job classification step to the existing regression methods.

With the growing use of RFID-based devices, there are increasing attentions on utilizing RFID technology for localization. In this paper, we consider RFID reader localization which locates an object by attaching it with an RFID reader that communicates with passive RFID tags deployed in the environment. One difficulty in RFID reader localization is that frequent RFID faults can affect localization accuracy. More specifically, in a complex localization environment, metal, water, obstacles, etc., causes some tags to fail to communicate with the reader, and consequently the localization result may deviate from the real location. For permanent faults, existing localization approaches can tolerate only faults that occur at individual tags, by utilizing the redundant information from their neighboring tags. However, these approaches cannot handle permanent faults that occur at a group of neighboring tags in a region, which is referred to as regional permanent fault. They will suffer from serious localization errors if such kind of faults occurs. Moreover, existing work lacks quality measurement of localization results, hence the user may be not aware how serious the localization errors can be. In this paper, we propose an effective fault-tolerant RFID reader localization approach that can handle regional permanent fault, and provide quality measurement of localization results. Our approach is applied to both 2D and 3D localization applications. We further study the network localization problem where some objects know their locations and the other objects determine their locations by measuring the distances to their neighbors. Using the localization results and especially the quality information obtained by our approach, we solve the network localization problem with improved localization accuracy. Evaluation results show that our approach outperforms existing approaches in localization accuracy and can provide additional useful quality information.

The advances in technologies of cloud computing and mobile computing enable the newly emerging mobile cloud computing paradigm. Three approaches have been proposed for mobile cloud applications: 1) extending the access to cloud services to mobile devices; 2) enabling mobile devices to work collaboratively as cloud resource providers; 3) augmenting the execution of mobile applications on portable devices using cloud resources. In this paper, we focus on the third approach in supporting mobile data stream applications. More specifically, we study the computation partitioning, which aims at optimizing the partition of a data stream application between mobile and cloud such that the application has maximum speed/throughput in processing the streaming data. To the best of our knowledge, it is the first work to study the partitioning problem for mobile data stream applications, where the optimization is placed on achieving high throughput of processing the streaming data rather than minimizing the make span of executions in other applications. We first propose a framework to provide runtime support for the dynamic partitioning and execution of the application. Different from existing works, the framework not only allows the dynamic partitioning for a single user but also supports the sharing of computation instances among multiple users in the cloud to achieve efficient utilization of the underlying cloud resources. Meanwhile, the framework has better scalability because it is designed on the elastic cloud fabrics. Based on the framework, we design a genetic algorithm to perform the optimal partition. We have conducted extensive simulations. The results show that our method can achieve more than 2X better performance over the execution without partitioning.

With the growing use of RFID-based devices, RFID reader localization attracts increasing attentions recently. In this technology, an object carrying an RFID reader is located by communicating with some passive RFID tags deployed in the environment. One important problem of RFID reader localization is that frequent occurred RFID faults affect localization accuracy. Specifically, complex localization environment (may include metal, water, obstacles, etc.) makes some tags fail to communicate with the reader, which makes the localization result deviate from the real location. Existing approaches can tolerate the faults occurred in individual tags and lasting for a short time period, but suffer serious localization error if the faults exist in a large region and last for a long time period. Moreover, existing approaches do not provide quality measurement of a localization result. In this paper, we propose an effective fault-tolerant RFID reader localization approach suitable for the above-mentioned situations, and illustrate how to measure the quality of a localization result. We have taken extensive simulations and implemented an RFID-based localization system. In both cases, our solution outperforms existing approaches in localization accuracy and can provide additional quality information.

Passive RFID tags have been widely utilized for object tracking in indoor environment due to their low cost and convenience for deployment. The RFID readings gathered from real world are often noisy. Existing approaches for tracking objects with noisy RFID readings are mostly based on using Particle Filter (PF). However, continuous execution of particle filter will suffer from high computational cost on resource constrained RFID-enabled devices. In this paper, we propose a hybrid method for tracking mobile objects with high accuracy and low computational cost. This is achieved by an adaptively switching between using WCL (Weighted Centroid Localization) and PF according to the estimated velocity of the moving object. We have evaluated the performance of our hybrid method through extensive simulations. We have also validated the performance results by implementing the method in two applications, namely, indoor wheelchair navigation and in-station LRV (Light Rail Vehicle) tracking in one of the Hong Kong MTR depots. The result shows that our proposed method outperforms both WCL and PF in either accuracy or computational cost.