Betweenness centrality is one of the key centrality measures in many applications including community detections in biological networks, vulnerability detections in communication networks, misinformation filtering in social networks, etc. The top-K group betweenness centrality problem is to find a group of K nodes from a network so that the total fraction of shortest paths that pass through the K nodes is maximized. Existing studies proposed randomized sampling algorithms for the problem. We notice that the existing studies ensured that, the maximum deviation of the estimated centrality of every group from its expectation is no greater than a small given threshold for all potential groups with no more than K nodes, thereby generating too many samples, as the number of such groups is prohibitively large. In contrast, in this paper we first devise a novel algorithm that enables to estimate the centrality of a tentative group adaptively, and the algorithm immediately stops once the centrality is large enough; otherwise, the algorithm uses more samples to find a better group. We then theoretically show that, even the proposed algorithm uses much less samples, it still can find a performance-guaranteed group with high probability. Experimental results with real-world networks demonstrate that the number of samples used by the proposed algorithm is up to 36 times smaller than the state-of-the-art, while the centrality of the group found by the algorithm is no more than 4.5% smaller than the latter.

The Internet of Things (IoT) is gathering paces in the new era of Industry 4.0, and the Digital Twin (DT) technology bridges the gap between the bursting amounts of data generated by IoT devices and the user requirements for real-time data processing. DT services maintain living digital models of physical objects, and a DT network enables comprehensive service provisioning with the global knowledge of a group of DTs. On the other hand, exposing serverless computing at network edges, the recent advances in Mobile Edge Computing (MEC) introduce new inspirations to the DT landscape that ensure fine-grained resource management and low network-wide delay of DT services. However, social relationships among IoT devices and DT data privacy impact DT orchestrations. In this paper, we first design a differential privacy-based federated learning framework to build a DT network for DT services in response to user requests in an MEC, thereby enhancing the Quality of Services (QoS). Built upon the proposed framework, we then formulate two novel social-aware DT placement problems: the static social-aware S_DT placement problem, and the dynamic social-aware S_DT placement problem, respectively. We also show the NP-hardness of the defined problems. Then, we formulate an Integer Linear Program (ILP) solution to the static social-aware S_DT placement problem when the problem size is small; otherwise we develop an approximation algorithm with a provable approximation ratio for it. Third, we study the dynamic social-aware S_DT placement problem when requests arrive one by one without the knowledge of future request arrivals over the time horizon, for which we devise an online algorithm with a provable competitive ratio. Finally, we conduct simulations to evaluate the performance of the proposed algorithms. Simulation results show that the proposed algorithms outperform their counterparts, improving the performance compared with their baselines by no less than 14.9%.

Artificial Intelligence Generated Content (AIGC) models typically have hundreds of billions of parameters, and developers experience prohibitively long pulling time from a central model registry to their local environments. Peer-to-peer (P2P)-enabled model distribution that pulls models from local peers within a cluster instead of the central model registry is emerging as a promising technique to reduce model pulling time. Nonetheless, such model distribution systems have to handle bursty concurrent pulling tasks. This may occupy the network bandwidth of some peers for a long time, thereby making the peers unable to respond to further pulling tasks. We thus aim to design a lightweight and scalable model distribution system to balance the network resource usage of peers, by proposing learning-driven algorithms to accurately predict network status between peers and implementing the design in real production environments. Specifically, we first propose a lightweight network measurement mechanism that combines active delay probing and passive bandwidth inference with low resource overhead. We also propose a learning-driven task scheduling algorithm based on a structural graph representation with a varied-multi-hop attention mechanism, to predict bursty patterns of concurrent pulling tasks. We then design an asynchronous model training and inference method to enable seamless incremental learning based on the dynamic network status data. We finally implement our system design and the learning-driven algorithm in a Cloud Native Computing Foundation (CNCF) projectDragonflythat has already been publicly released since its version$v2.1.0$. Real experiments in the Ant Group’s production environment show that our system reduces the total completion time by at least 10% and increases the average bandwidth utilization of peers by 20%, compared with mainstream systems and algorithms.

Digital twin is emerging as a key technology to monitor the status of complex industry systems. Valuable insights, such as running statuses and anomalies, can be analyzed from the collected system status timely. Considering that the data updating from each system component (known as a physical object) to its digital twin is performed continuously, timely and accurate streaming analytics based on machine learning models is a key technology to analyze such data efficiently. In this paper, we focus on enabling low-delay yet highly-accurate streaming analytics for digital twin applications in mobile edge computing (MEC) networks. Specifically, we formulate a fundamental optimization problem of digital twin placements and model selections for streaming analytics, with the aim of minimizing both the analytic loss and the processing delay. To this end, we first consider the problem with a single query, for which, we propose an approximation algorithm with provable approximation ratio for a special case, and then devise an efficient algorithm for the original problem with a single query. We then study the online digital twin placement and model selection problem for streaming analytics with multiple queries under real scenarios, where resource demands of arrival queries and resource availability of MEC network are uncertain. We propose an online learning algorithm with a bounded regret to make admission policies. We finally evaluate the performance of the proposed algorithms by extensive simulations. Results show that the weighted sums of the total processing delay and the cumulative loss in the solution delivered by the proposed algorithms outperform their counterparts by 12.5% with a single query and 13.3% with multiple queries, respectively.

Big data analytics for Earth observation has been playing an increasingly important role in supporting environmental monitoring, disaster early warning, and sustainable development through timely analysis of massive multi-source data collected by satellites. With the growing need for such timely Big Data analysis, Space Edge Computing (SEC) networks have been proposed to provide in-orbit analytic services for users worldwide, by integrating computing capability through Low-Earth-Orbit (LEO) satellites. However, the monitoring frequency of LEO satellites over specific target areas remains limited due to orbital constraints, making it difficult to meet the high-frequency data acquisition demands of Big Data analytics. Satellite inclination maneuver is a promising method to cover a wide range of target areas and enhance monitoring frequency by adjusting orbital inclination of satellites. Although such maneuvering enables satellites to timely process datasets, reducing energy wastage caused by inter-satellite data transmission, it consumes propulsion fuel, which is limited and difficult to replenish in a timely manner. Therefore, balancing the energy consumed for data processing and the fuel consumed for maneuvering is essential for efficient and sustainable Big Data analytics in SEC networks. In this paper, we aim to optimize Big Data query evaluation problem with satellite maneuver in an SEC network, focusing on minimizing the weighted sum of energy consumed for processing and fuel consumed for maneuvering. Specifically, we consider that each Earth observation service needs to guarantee a certain level of monitoring frequency, which may not always be satisfied by the original orbital coverage of LEO satellites. In such cases, some satellites will be selected to perform inclination maneuvers for additional monitoring and processing to guarantee the quality of Earth observation services. To this end, we first propose an approximation algorithm with a provable approximation ratio for the offline query evaluation problem, which leverages a customized auxiliary graph to jointly minimize energy and fuel consumption. We then devise an online learning algorithm, referred to as the customized Lipschitz bandit learning algorithm, with a bounded regret for the online Big Data query evaluation problem in an SEC network. We finally evaluate the performance of the proposed algorithms in a real SEC network topology. Experiment results show that the performance of the proposed algorithms achieve 11% lower energy consumption and 10.6% lower fuel consumption than those of their comparison counterparts.

Data stream processing is a functionality of various AI applications to obtain continuous insights from data streams. Serverless edge computing (SEC) is a key solution for implementing data stream processing requests by deploying serverless functions into cloudlets. However, existing data stream processing methods focus more on processing delay, ignoring fault tolerance and complex dependencies among functions, resulting in critical events being missed in the event of any fault and processing inefficiency. Besides, due to the uncertainty of data streams, existing function deployment methods may not be suitable for their newly changed data rates, causing resource waste or shortages. To address these problems, we first propose an optimization framework to enable efficient and fault tolerant function deployment, such that the delay of data stream processing is minimized while meeting its fault tolerant requirements and resource capacity constraints of cloudlets in an SEC network. We then design an online learning algorithm that predicts data rate changes through a multi-timescale machine learning method and proactively adjusts instance locations and numbers to absorb data rate uncertainty. Experimental results in a real test-bed show that our proposed algorithms outperform their counterparts by 13.5% on the average delay and 26.3% on the average fault tolerance.

Serverless computing are invented to free developers of analytic services from the management of cloud resources. Developers only need to submit their code to a serverless edge cloud (SEC) and the cloud platform matches the submitted code to itsserverless functions, enabled by the paradigm of Function as a Service (FaaS). However, serverless functions usually are short-lived with limited resources. In this paper, we aim to address the challenge of how to fully utilize the short-lived serverless functions to enable continuous analysis of the most freshly-generated big data. We first formulate an optimization problem of age-aware big data query evaluation in an SEC network so that theage of datais minimized, where the age of data is the duration between the generation time of the data and the current time. We then propose approximation algorithms for the age-aware big data query evaluation problem of a single query, by proposing a parameterized virtualization technique that smartly handles the large resource demands of big data queries in short-lived and resource-constraint serverless functions. We further consider the scenario where big data queries arrive into the system one-by-one and their resource demands are uncertain. To this end, we devise an online learning algorithm with bounded regret by leveraging a memory repacking mechanism to improve resource utilization, for the problem of online age-aware big data query evaluation. We evaluate the performance of the proposed algorithms through extensive simulations to testify their performances in large scales. We also validate the effectiveness of the proposed mechanism in a real test-bed built on Kubernetes and OpenWhisk with TPC-DS benchmarks. Experimental results show that the proposed algorithms outperform the state-of-the-arts, by reducing the age of data by$8.82\%$on average.

Metaverse, as the cyberspace against the real world, offers various immersive services enabling users to entertain, learn and work. The digital twin (DT) technology acts as a fundamental enabler of Metaverse services by mapping user devices to DTs and timely analyzing the status of user devices. Mobile edge computing (MEC) significantly improves the QoS of DT-empowered Metaverse services because it can deploy DTs in cloudlets closer to user devices. However, each user device often has a complex structure with multiple interdependent subsystems that frequently communicate. Further, the resources in MEC network are highly distributed and limited. Thus, provisioning DT-empowered Metaverse services in MEC networks faces the challenge of efficiently mapping intertwining subsystems in user devices to DTs, maximizing admitted service requests and resource utilization. In this paper, we first formulate throughput maximization problems for DT-empowered Metaverse services in an MEC network, with the aim to maximize the total data rate of service requests of Metaverse services while meeting resource capacity constraints of the MEC network. We then propose an approximation algorithm with a provable approximation ratio for the problem with a given set of service requests if both monitoring and analytical DTs are consolidated into a single edge server. Otherwise, we devise an efficient heuristic for the problem with monitoring and analytical DTs possibly being placed into different edge servers. We also consider a dynamic throughput maximization problem of Metaverse service provisioning for a given monitoring period, in which service requests arrive into the system dynamically without the knowledge of future arrivals, service resource demands, and service delay requirements, for which we devise an online learning algorithm. We finally evaluate the performance of the proposed algorithms by extensive simulations. Simulation results show that the throughputs of the proposed algorithms outperform their comparison counterparts by at least 50 %.

UAVs (Unmanned Aerial Vehicles) are promising tools for disaster monitoring, by obtaining valuable information of important PoIs (Points of Interest) with onboard cameras. Since people trapped at some PoIs are more likely in danger than people in other PoIs, different PoIs have different monitoring priorities, so that the PoIs with high monitoring priorities should be visited more often than those with low priorities. Unlike existing studies that assumed a UAV is required to fly to the location of a PoI to monitor the PoI, we observe that the a UAV can monitor a PoI as long as it hovers at any location around the PoI (e.g., 200 m away horizontally), thereby reducing the flying time of the UAV. In this paper, we first study a problem of finding a sequence of monitoring tours for an energy-constrained UAV to monitor PoIs in a disaster area for a monitoring period T (e.g., 72 hours) persistently, such that the maximum weighted monitoring interval of PoIs is minimized, where the weight associated with a PoI is its monitoring priority, and the monitoring interval of a PoI is the longest time between its two consecutive visits in period T. We then propose a novel approximation algorithm for the problem. We finally evaluate the algorithm performance based on both a real testbed and the simulation. The experimental results show that the maximum weighted monitoring interval by the proposed algorithm is up to 30% shorter than those by existing algorithms.

Betweenness centrality is one of the key centrality measures in many applications including community detections in biological networks, vulnerability detections in communication networks, misinformation filtering in social networks, etc. The top-$K$group betweenness centrality problem is to find a group of$K$nodes from a network so that the total fraction of shortest paths that pass through the$K$nodes is maximized. Existing studies proposed randomized sampling algorithms for the problem. We notice that the existing studies ensured that, the maximum deviation of the estimated centrality of every group from its expectation is no greater than a small given threshold for all potential groups with no more than$K$nodes, thereby generating too many samples, as the number of such groups is prohibitively large. In contrast, in this paper we first devise a novel algorithm that enables to estimate the centrality of a tentative group adaptively, and the algorithm immediately stops once the centrality is large enough; otherwise, the algorithm uses more samples to find a better group. We then theoretically show that, even the algorithm uses much less samples, it still can find a performance-guaranteed group with a large success probability. Experimental results with real-world networks demonstrate that the number of samples used by the proposed algorithm is from 2 to 18 times smaller than the state-of-the-art, while the centrality of the group found by the algorithm is no more than 4% smaller than the latter.

Collaborative inference (Co-inference) across end devices and edge servers has emerged as a promising approach to satisfy the growing demand for computationally intensive and latency sensitive deep learning tasks. However, the limited computational capabilities and the bandwidth constraints of devices and edge servers pose significant challenges on co-inference. Current pertinent solutions either rely on predefined partition points and compression ratios or support only limited dimensions of dynamic adjustment, resulting in insufficient flexibility to adapt to diverse user requirements and network conditions. To address these challenges, we propose a novel framework that enhances co-inference through adaptive intermediate feature compression and efficient resource allocation. Specifically, we design a sophisticated feature compression method that incorporates channel pruning, spatial downsampling, and quantization, enabled by a weight-shared dynamic neural network architecture for efficient compression parameter switching without model reloading. Then, we formulate a constrained accuracy-maximization problem and develop a dynamic programming-based solution to jointly optimize partition points, compression parameters, and resource allocation, while meeting diverse user requirements. Experimental results show that our approach is capable of achieving up to a 22.8% improvement in inference accuracy compared to the state-of-the-art method in multi-user scenarios, demonstrating our superiority.

With the advance of mobile edge computing (MEC) and the Internet of Things (IoT), digital twin (DT) has become an emerging technology for provisioning IoT services between the real world and the cyber world. In this paper, we consider the state updating of DTs in an MEC network through synchronizing DTs with their physical objects. We make use of an energy-constrained UAV for data collection in a sensor network, as an illustrative example for the DT state updating of each object (sensor), and then use the DT data of objects (sensors) later for fidelity-aware query services. To this end, we first formulate a novel DT state staleness minimization, under a given update budget per update round. We then propose an optimal algorithm for a special case of the problem where the budget per update round is exactly$K$objects synchronizing with their DTs. We then devise an algorithm for the DT state staleness minimization problem by reducing to the award collection maximization problem, assuming that the volume of the update data generated by each object per update round is given. Otherwise, we adopt a deep learning method to predict the volume of the update data. To demonstrate the importance of the DT state staleness in practical applications, we consider fidelity-aware query services in the MEC network, and we develop a cost-effective evaluation plan for each query. We finally evaluate the performance of the proposed algorithms through simulations. Simulation results demonstrate that the proposed algorithms are promising.

The integration of Artificial Itelligence (AI) and edge computing has sparked significant interest in edge inference services. In this paper, we consider delay-sensitive, differential accuracy inference services in a Mobile Edge Computing (MEC) network while meeting user stringent delay and accuracy requirements. We formulate two novel profit maximization problems under static and dynamic settings of service request arrivals, with the aim of maximizing the accumulative profit of admitted requests. We assign differential accuracy service requests to the corresponding resolution instances of their requested service models, assuming that each resolution instance can serve up to$L\geq 1$the same type of service requests. Since the profit maximization problem is NP-hard, we first formulate an Integer Linear Program (ILP) solution if the problem size is small or medium; otherwise, we devise a constant randomized algorithm with high probability. Then, we consider dynamic service request admissions without the knowledge of future request arrivals for a given finite time horizon, for which we develop a simple yet effective prediction mechanism to accurately predict the number of different resolution instances of each model needed, and pre-deploy the predicted number of resolution instances into cloudlets to reduce instantiating delays. We then devise an online algorithm with a provable competitive ratio for the dynamic profit maximization problem by leveraging the primal-dual dynamic updating technique. Finally, we evaluate the performance of the proposed algorithms by simulations. The simulation results demonstrate that the proposed algorithms are promising.

In this paper, we study a connected submodular function maximization problem, which arises from many applications including deploying UAV networks to serve users and placing sensors to cover Points of Interest (PoIs). Specifically, given a budget K, the problem is to find a subset S with K nodes from a graph G, so that a given submodular function$f(S)$on S is maximized and the induced subgraph$G[S]$by the nodes in S is connected, where the submodular function f can be used to model many practical application problems, such as the number of users within different service areas of the deployed UAVs in S, the sum of data rates of users served by the UAVs, the number of covered PoIs by placed sensors, etc. We then propose a novel$\frac {1-1/e}{2h+2}$-approximation algorithm for the problem, improving the best approximation ratio$\frac {1-1/e}{2h+3}$for the problem so far, through estimating a novel upper bound on the problem and designing a smart graph decomposition technique, where e is the base of the natural logarithm, h is a parameter that depends on the problem and its typical value is 2. In addition, when$h=2$, the algorithm approximation ratio is at least$\frac {1-1/e}{5}$and may be as large as 1 in some special cases when$K\le 23$, and is no less than$\frac {1-1/e}{6}$when$K\ge 24$, compared with the current best approximation ratio$\frac {1-1/e}{7}\left ({{=\frac {1-1/e}{2h+3}}}\right)$for the problem. Finally, experimental results in the application of deploying a UAV network demonstrate that, the number of users within the service area of the deployed UAV network by the proposed algorithm is up to 7.5% larger than those by existing algorithms, and the throughput of the deployed UAV network by the proposed algorithm is up to 9.7% larger than those by the algorithms. Furthermore, the empirical approximation ratio of the proposed algorithm is between 0.7 and 0.99, which is close to the theoretical maximum value one.

Pretrained Foundation Models (PFMs) are regarded as a promising accelerator for the development of various Artificial Intelligence (AI) applications, and have recently been widely fine-tuned to satisfy users' personalized inference demands. As many users are attracted to PFM-based AI applications, remote data centers are increasingly unable to solely bear the enormous computational demands and meet the delay requirements of inference requests. Mobile edge computing (MEC) offers a viable solution for delivering low-latency inference services by pulling fine-tuned PFMs from the remote data center to cloudlets in the proximity of users. However, a fine-tuned PFM typically comprises billions of model parameters, which are highly resource-intensive, time-consuming, and cost-prohibitive to execute at the edge. To address this, we investigate a novel joint large model selection and pulling problem in MEC networks. The novelty of our study lies in exploring parameter sharing among fine-tuned PFMs based on their common knowledge. Specifically, we first formulate a Non-Linear Integer Programming (NLIP) for the problem to minimize the total delay of implementing all inference requests. We then transform the NLIP into an equivalent Integer Linear Program (ILP) that is much simpler to solve. We further propose a randomized algorithm with a provable approximation ratio for the problem. We also consider the online version of the problem with uncertain request demand, and develop an online learning algorithm with a bounded regret. The crux of the online algorithm is the adoption of the multi-armed bandit technique with restricted context for dynamic admissions of inference requests. We finally conduct extensive experiments based on real datasets. Experimental results demonstrate that our algorithms reduce at least 38% in total delays and average costs, while achieving a 5% improvement in average accuracies.

Given an untrimmed video and a sentence query, video moment retrieval using language (VMR) aims to locate a target query-relevant moment. Since the untrimmed video is overlong, almost all existing VMR methods first sparsely down-sample each untrimmed video into multiple fixed-length video clips and then conduct multi-modal interactions with the query feature and expensive clip features for reasoning, which is infeasible for long real-world videos that span hours. Since the video is downsampled into fixed-length clips, some query-related frames may be filtered out, which will blur the specific boundary of the target moment, take the adjacent irrelevant frames as new boundaries, easily leading to cross-modal misalignment and introducing both boundary-bias and reasoning-bias. To this end, in this paper, we propose an efficient approach, SpotVMR, to trim the query-relevant clip. Besides, our proposed SpotVMR can serve as plug-and-play module, which achieves efficiency for state-of-the-art VMR methods while maintaining good retrieval performance. Especially, we first design a novel clip search model that learns to identify promising video regions to search conditioned on the language query. Then, we introduce a set of low-cost semantic indexing features to capture the context of objects and interactions that suggest where to search the query-relevant moment. Also, the distillation loss is utilized to address the optimization issues arising from end-to-end joint training of the clip selector and VMR model. Extensive experiments on three challenging datasets demonstrate its effectiveness.

In this paper, we study a connected submodular function maximization problem, which arises from many applications including deploying UAV networks to serve users and placing sensors to cover Points of Interest (PoIs). Specifically, given a budget$K$, the problem is to find a subset$S$with$K$nodes from a graph$G$so that a given submodular function$f (S)$on$S$is maximized while the induced subgraph$G[S]$by the nodes in$S$is connected, where the submodular function$f$can be used to model many practical application problems, such as the number of users within different service areas of the deployed UAVs in$S$, the sum of data rates of users served by the UAVs, the number of covered PoIs by placed sensors, etc. We then propose a novel$\frac{1-1/e}{2h+2}$-approximation algorithm for the problem, improving the best approximation ratio$\frac{1-1/e}{2h+3}$for the problem so far, through estimating a novel upper bound on the problem and designing a smart graph decomposition technique, where$e$is the base of the natural logarithm,$h$is a parameter depends on the problem and its typical value is 2. In addition. when$h= 2$, the algorithm approximation ratio is at least$\frac{1-1/e}{5}$and may be as large as 1 in some special cases when$K$≤21, and is no less than$\frac{1-1/e}{6}$when$K$≥ 22, compared with the current best approximation ratio$\frac{1-1/e}{7}(= \frac{1-1/e}{2h+3})$for the problem. We finally evaluate the algorithm performance in the application of deploying a UAV network. Experimental results demonstrate the number of users within the service area of the deployed UAV network by the proposed algorithm is up to 7.5% larger than those by existing algorithms, and its empirical approximation ratio is between 0.7 and 0.99, which is close to the theoretical maximum value one.

Video Moment Retrieval (VMR) targets to retrieve the specific moment corresponding to a sentence query from an untrimmed video. Although recent respectable works have made remarkable progress in this task, they implicitly are rooted in the closed-set assumption that all the given queries as video-relevant. Given an OOD query in open-set scenarios, they still utilize it for wrong retrieval, which might lead to irrecoverable losses in high-risk scenarios, e.g., criminal activity detection. To this end, we creatively explore a brand-new VMR setting termed Open-Set Video Moment Retrieval (OS-VMR), where we should not only retrieve the precise moments based on ID query, but also reject OOD queries. In this paper, we make the first attempt to step toward OS-VMR and propose a novel model OpenVMR, which first distinguishes ID and OOD queries based on the normalizing flow technology, and then conducts moment retrieval based on ID queries. Specifically, we first learn the ID distribution by constructing a normalizing flow, and assume the ID query distribution obeys the multi-variate Gaussian distribution. Then, we introduce an uncertainty score to search the ID-OOD separating boundary. After that, we refine the ID-OOD boundary by pulling together ID query features. Besides, video-query matching and frame-query matching are designed for coarse-grained and fine-grained cross-modal interaction, respectively. Finally, a positive-unlabeled learning module is introduced for moment retrieval. Experimental results on three VMR datasets show the effectiveness of our OpenVMR.

The Internet of Things (IoT) is gathering paces in the new era of Industry 4.0, and the Digital Twin (DT) technology bridges the gap between the bursting amounts of data generated by IoT devices and the user requirements for real-time data processing. DT services maintain living digital models of physical objects, and a DT network enables comprehensive service provisioning with the global knowledge of a group of DTs. On the other hand, exposing serverless computing in network edges, the recent advances in Serverless Edge Computing (SEC) introduce new inspirations to the DT landscape that ensure fine-grained resource management and low network-wide delay of DT services. However, social relationships among IoT devices and DT data privacy impact the orchestration of DTs. In this paper, we design a differential privacy-based federated learning framework to build a DT network for DT services in response to user DT service requests in SEC, thereby enhancing the Quality of Services (QoS). To this end, we first formulate a novel social-aware problem for placing DTs in an SEC network, and show its NP-hardness. We then provide an Integer Linear Program (ILP) solution to the problem when the problem size is small; otherwise, we design an approximation algorithm with a provable approximation ratio. We finally evaluate the algorithm performance through simulations. Simulation results demonstrate the proposed algorithm is promising, which improves by no less than 21.1 % of the performance of benchmarks.

Federated continual learning (FCL) is emerging as a key technology for time-sensitive applications in highly adaptive environments including autonomous driving and industrial digital twin. Each FCL trains machine learning models using newly-generated datasets as soon as possible, to obtain a highly accurate machine learning model for new event predictions. Theage of data, defined as the time difference between the generation time of a dataset and the current time, is widely adopted as a key criterion to evaluate both timeline and quality of training. In this paper, we study the problem of age-aware FCL in a mobile edge computing (MEC) network. We not only investigate optimization techniques that optimize the data selection and aggregator placement for FCL but also implement a real system as a prototype for age-aware FCL. Specifically, we first propose an approximation algorithm with a provable approximation ratio for the age-aware data selection and aggregator placement problem for FCL with a single request. In real application scenarios, there are usually multiple FCL requests that require to train models, and delays in the MEC network are usually uncertain. We then study the problem of age-aware data selection and aggregator placement problem for FCL with uncertain delays and multiple requests, by devising an online learning algorithm with a bounded regret based on contextual bandits. We finally implement a prototype for FCL in an MEC network, with various heterogeneous user equipments (UEs) and cloudlets with different computing capabilities in the network. Experiment results show that the performance of the proposed algorithms outperform existing studies, by achieving 47% lower age of data and 12% higher model accuracy.

Mobile Edge Computing (MEC) has been identified as a desirable computing paradigm that provides efficient and effective services for various applications, while meeting stringent service delay requirements. Orthogonal to the MEC computing paradigm, Network Function Virtualization (NFV) technology is another enabling technology that provides the network resource management with great flexibility and scalability, where the instances of Virtual Network Functions (VNFs) are deployed in edge servers as Service Function Chains (SFCs) for SFC-enabled services. Although reliable service provisioning in MEC environments is fundamentally important, the deployed VNF instances usually are not reliable, which can be affected by their software implementation, their execution duration, the workload among edge servers, and so on. Empowered by digital twin techniques, the states of VNF instances can be maintained by their digital twins in a real-time manner and their reliability can be accurately predicted through their digital twins. In this paper, we study digital twin-assisted, SFC-enabled reliable service provisioning in MEC networks by exploiting the dynamics of VNF instance reliability. We concentrate on two novel optimization problems of reliable service provisioning: the service cost minimization problem, and the dynamic service admission maximization problem. We first show their NP-hardness. We then formulate an Integer Linear Program (ILP) solution, and devise an approximation algorithm with a constant approximation ratio for the service cost minimization problem. We thirdly provide an ILP solution to the offline version of the dynamic service admission maximization problem. Built upon this offline ILP solution, we also develop an online algorithm with a provable competitive ratio for the problem, by adopting the primal-dual dynamic updating technique. We finally evaluate the performance of the proposed algorithms via simulations. Simulation results demonstrate that the proposed algorithms outperform their comparison benchmarks, and improve the performance of their comparison counterparts by no less than$10.2 \%$.

Digital twins are poised to enter our lives with Industry 4.0. The Digital Twin Network (DTN) paradigm is projected to deliver upon the promise of efficient collaboration among digital twins to enable complicated and systematic services across many domains, through depicting an overall picture of a group of physical objects. To achieve timely data processing of digital twins, Mobile Edge Computing (MEC) shifts the computational power towards the network edge, and network slicing is well-suited to bundle heterogeneous physical resources to build logical networks based on edge servers for accommodating DTNs. In light of this, in this paper we investigate DTN slicing-enabled service provisioning in MEC, where each DTN slice consists of one master digital twin and a set of worker digital twins, and each worker digital twin is synchronized through collecting data from a respective object periodically. The master digital twin aggregates the processed data from worker digital twins to model the DTN continuously for user query services, whilst meeting delay requirements of users. We capture the utility gain of a DTN slicing request based on the DTN model quality at its master digital twin that is impacted by the Age of Information (AoI), and we focus on two novel optimization problems: the utility maximization problem for a single DTN slicing request, and the dynamic utility maximization problem for multiple DTN slicing requests. We propose an approximation algorithm for the former, and an online algorithm with a provable competitive ratio for the latter. We also evaluate the performance of the proposed algorithms through simulations. Experimental results demonstrate that the proposed algorithms are promising, outperforming their counterparts by at least 10.2%.

Satellite-terrestrial networks are emerging as the next-generation networking paradigm for Beyond-5 G (B5G) and 6 G networks. Meanwhile, Mobile Edge Computing (MEC) is envisioned as the key technology to provide network services within the proximity of users, by deploying computing resource in ground locations that are close to users. With the fast deployment of Low-Earth-Oribt (LEO) satellites, a new paradigm of MEC is emerging by enabling LEO satellites serving as edge servers in lower orbits that are close to ground users. In this way, the ground users can be further served by LEO satellites in lower orbits instead of conventional high-orbit satellites. Also, since LEO satellites provide shorter paths from users to services, the performance is enhanced compared with ground MEC networks. In this paper, we aim to enable low-latency network services in a Satellite Edge Computing (SEC) network that integrates the MEC and satellite-terrestrial networks. In particular, we consider that each network service is composed of a sequence of Virtualized Network Functions (VNFs), where the traffic of user requests has to be processed by the VNFs in a service chain in the specified order before reaching its destination. To this end, we first formulate a delay-aware service chaining problem in an SEC network to minimize the average delay of implementing a user request, by jointly placing VNFs to LEO satellites in the SEC network and routing the traffic of each user request from its source to destination. We then devise an approximation algorithm with an approximation ratio for the problem in an SEC network with a single user request, by devising a novel concept ofchaining orbitand auxiliary graph construction technique. We also design an online algorithm for the online delay-aware service chaining problem in an SEC network, if user requests arrive into the system without the knowledge of their arrivals and the network delays are uncertain. We finally evaluate the performance of the proposed algorithms using real satellite network topologies, and results show that the proposed algorithms achieve 28.5% lower delay than their counterparts.

To unveil the hidden value in the datasets of user equipments (UEs) while preserving user privacy, federated learning (FL) is emerging as a promising technique to train a machine learning model using the datasets of UEs locally without uploading the datasets to a central location. Customers require to train machine learning models based on different datasets of UEs, through issuing FL requests that are implemented by FL services in a mobile edge computing (MEC) network. A key challenge of enabling FL in MEC networks is how to minimize the energy consumption of implementing FL requests while guaranteeing the accuracy of machine learning models, given that the availabilities of UEs usually are uncertain. In this paper, we investigate the problem of energy minimization for FL in an MEC network with uncertain availabilities of UEs. We first consider the energy minimization problem for a single FL request in an MEC network. We then propose a novel optimization framework for the problem with a single FL request, which consists of (1) an online learning algorithm with a bounded regret for the UE selection, by considering various contexts (side information) that influence energy consumption; and (2) an approximation algorithm with an approximation ratio for the aggregator placement for a single FL request. We third deal with the problem with multiple FL requests, for which we devise an online learning algorithm with a bounded regret. We finally evaluate the performance of the proposed algorithms by extensive experiments. Experimental results show that the proposed algorithms outperform their counterparts by reducing at least 13% of the total energy consumption while achieving the same accuracy.

Digital twin (DT) has been emerging as an enabling technology to provide seamless interactions between the virtual cyber world and the real world. The explosion of IoT devices (objects) further fuels the development of the DT technology, and paves the way to real-time monitoring, behavior simulations and decisive predictions on objects through their digital counterparts. Meanwhile, mobile edge computing (MEC) has been envisioned as a promising computing paradigm for various IoT applications with stringent delay requirements. In this paper, we study mobility-aware, delay-sensitive service provisioning in a DT-empowered MEC network with the mobility of both users and objects through DT replica placements of mobile objects. To this end, we first formulate two novel optimization problems: the DT replica placement problem and the dynamic DT replica placement problem, respectively, and show NP-hardness of the two problems. We then formulate an Integer Linear Programming (ILP) solution to the DT replica placement problem when the problem size is small or medium; otherwise we devise a randomized algorithm with high probability, provided that the mobility profiles of each object and each user are given. Meanwhile, We also develop an online algorithm for the dynamic DT replica placement problem, where for a given time horizon, service requests arrive one by one without the knowledge of future arrivals, each arrived request must be responded immediately by accepting or rejecting it. However, the heterogeneity and dynamics of user requests on resource demands may lead to the removals and re-instantiations of DT instances frequently. To mitigate this, we propose an efficient prediction mechanism to reserve a certain number of DTs for future by introducing the timestamp concept. We finally evaluate the performance of the proposed algorithms by simulations. Simulation results show that the proposed algorithms are promising, and outperform the performance of other comparison counterparts.

This article studies the multimedia problem of temporal sentence grounding (TSG), which aims to accurately determine the specific video segment in an untrimmed video according to a given sentence query. Traditional TSG methods mainly follow the top-down or bottom-up framework and are not end-to-end. They severely rely on time-consuming post-processing to refine the grounding results. Recently, some transformer-based approaches are proposed to efficiently and effectively model the fine-grained semantic alignment between video and query. Although these methods achieve significant performance to some extent, they equally take frames of the video and words of the query as transformer input for correlating, failing to capture their different levels of granularity with distinct semantics. To address this issue, in this article, we propose a novelHierarchicalLocal-GlobalTransformer (HLGT) to leverage this hierarchy information and model the interactions between different levels of granularity and different modalities for learning more fine-grained multi-modal representations. Specifically, we first split the video and query into individual clips and phrases to learn their local context (adjacent dependency) and global correlation (long-range dependency) via a temporal transformer. Then, a global-local transformer is introduced to learn the interactions between the local-level and global-level semantics for better multi-modal reasoning. Besides, we develop a new cross-modal cycle-consistency loss to enforce interaction between two modalities and encourage the semantic alignment between them. Finally, we design a brand-new cross-modal parallel transformer decoder to integrate the encoded visual and textual features for final grounding. Extensive experiments on three challenging datasets (ActivityNet Captions, Charades-STA and TACoS) show that our proposed HLGT achieves a new state-of-the-art performance, demonstrating its effectiveness and computational efficiency.

Blockchain has revolutionized a variety of fields by providing decentralization, immutability, transparency, and auditability. This paper designs Blockchained Edge Resource Auction (BERA) for edge computing systems to allocate computing resources to application service providers (ASP) in a secure manner. BERA comprises two key components: Blockchain-based Sealed-Bid Auction (BSBA) and Graph Neural Network (GNN)-based Fraud Detection (GFD). BSBA designs smart contracts to realize sealed-bid auctions overhead blockchain. It incorporates the homomorphic commitment technique to guarantee the transactional privacy of ASPs’ bidding information and performs interval membership zero-knowledge proof to verify the legitimacy of auction results. While the privacy-preserving property of BSBA is desirable, the veiled bidding information tends to breed fraudulent behaviors. Therefore, GFD is further proposed to identify abnormal auction behaviors in BSBA without revealing bidding information of ASPs. GFD converts the blockchain data of BSBA to an auction behavioral graph of ASPs, and uses GNN to discover stealth frauds based on interactive patterns. In addition, we design a subgraph extraction scheme for GFD to improve its scalability. We implement BERA on a private Ethereum blockchain and successfully realize edge resource auctions. We simulate several types of auction frauds and identify them with GFD. The experimental results show that our method outperforms other benchmarks.

This paper addresses the temporal sentence grounding (TSG). Although existing methods have made decent achievements in this task, they not only severely rely on abundant video-query paired data for training, but also easily fail into the dataset distribution bias. To alleviate these limitations, we introduce a novel Equivariant Consistency Regulation Learning (ECRL) framework to learn more discriminative query-related frame-wise representations for each video, in a self-supervised manner. Our motivation comes from that the temporal boundary of the query-guided activity should be consistently predicted under various video-level transformations. Concretely, we first design a series of spatio-temporal augmentations on both foreground and background video segments to generate a set of synthetic video samples. In particular, we devise a self-refine module to enhance the completeness and smoothness of the augmented video. Then, we present a novel self-supervised consistency loss (SSCL) applied on the original and augmented videos to capture their invariant query-related semantic by minimizing the KL-divergence between the sequence similarity of two videos and a prior Gaussian distribution of timestamp distance. At last, a shared grounding head is introduced to predict the transform-equivariant query-guided segment boundaries for both the original and augmented videos. Extensive experiments on three challenging datasets (ActivityNet, TACoS, and Charades-STA) demonstrate both effectiveness and efficiency of our proposed ECRL framework.

The emerging digital twin technique enhances the network management efficiency and provides comprehensive insights on network performance, through mapping physical objects to their digital twins. The user satisfaction on digital twin-enabled service relies on the freshness of digital twin data, which is measured by the Age of Information (AoI). Due to long service delays, the use of the remote cloud for delay-sensitive service provisioning faces serious challenges. Mobile Edge Computing (MEC), as an ideal paradigm for delay-sensitive services, is able to realize real-time data communication between physical objects and their digital twins at the network edge. However, the mobility of physical objects and dynamics of user query arrivals make seamless service provisioning in MEC become challenging. In this paper, we investigate dynamic digital twin placements for improving user service satisfaction in MEC environments, by introducing a novel metric to measure user service satisfaction based on the AoI concept and formulating two user service satisfaction enhancement problems: the static and dynamic utility maximization problems under static and dynamic digital twin placement schemes. To this end, we first formulate an Integer Linear Programming (ILP) solution to the static utility maximization problem when the problem size is small; otherwise, we propose a performance-guaranteed approximation algorithm. We then propose an online algorithm with a provable competitive ratio for the dynamic utility maximization problem, by considering dynamic user query services. Finally, we evaluate the performance of the proposed algorithms via simulations. Simulation results demonstrate that the proposed algorithms outperform the comparison baseline algorithms, improving the algorithm performance by at least$10.7\%$, compared to the baseline algorithms.

The Mobile Edge Computing (MEC) paradigm gives impetus to the vigorous advancement of the Internet of Things (IoT), through provisioning low-latency computing services at network edges. The emerging digital twin technique has been explosively growing in the IoT community, which bridges the gap between physical objects and their digital representations in an MEC network, enabling real-time monitoring and analysis, simulations on the dynamics of systems, accurate predictions on behaviours of objects, and optimization on network resource allocation. In this paper, we consider AoI-aware query services in an MEC network empowered by digital twin technology for diverse IoT applications. We aim to maximize the weighted sum of the accumulative freshness of query results measured by the Age of Information (AoI) and the total query service delay of admitted requests. To this end, we first formulate a novel minimization problem that explores nontrivial trade-offs between the two conflicting optimization objectives: the freshness of query results and service delays, and we show the NP-hardness of the problem. Then, we propose an approximation algorithm with a provable approximation ratio for the problem, at the expense of bounded computing capacity violations. We also develop a heuristic for the problem without any capacity violations. We finally evaluate the performance of the proposed algorithms via simulations. The simulation results demonstrate that the proposed algorithms are promising, and outperform the comparison benchmarks.

In this paper, we study the deployment of$K$heterogeneous UAVs to monitor Points of Interest (PoIs) in a disaster zone, where a PoI may represent a school building or an office building, in which people are trapped. A UAV can take images/videos of PoIs and send its collected information back to a nearby rescue station for decision-making. Unlike most existing studies that focused on only homogeneous UAVs, we here study the scheduling of$K$heterogeneous UAVs, where different UAVs have different energy capacities and functionalities that lead to different monitoring qualities (monitoring rewards) of each PoI. For example, one type of UAVs can take only visual images while the other type of UAVs can take both visual and thermal infrared images. In this paper, we investigate a problem of scheduling$K$heterogeneous UAVs to monitor PoIs so that the sum of monitoring rewards received by all UAVs is maximized, subject to energy capacity on each UAV. We propose the very first$\frac {1}{3}$-approximation algorithm for this scheduling problem. We also evaluate the performance of the proposed algorithm, using real parameters of commercial UAVs. Experimental results show that the performance of the proposed algorithm is promising, which is improved by 25%, compared with existing algorithms.

In the coming era of Metaverse, Augmented Reality (AR) has become a key enabler of diverse applications including healthcare, education, smart cities, and entertainments. To provide users with interactive and immersive experience, most AR applications require extremely high responsiveness and ultra-low processing latency. Mobile edge computing (MEC) has demonstrated great potentials in meeting such stringent latency requirements and resource demands of AR applications, by implementing AR requests in edge servers within the proximity of users. In this paper, we investigate the reward maximization problem for AR applications with uncertain resource demands in an MEC network, such that the accumulative reward of services provided for AR applications is maximized, while ensuring that the responsiveness of AR applications is enhanced, subject to network resource capacity. To this end, we formulate an exact solution when the problem size is small, otherwise we devise an efficient approximation algorithm with a provable approximation ratio for the problem. We also develop an online learning algorithm with a bounded regret for the dynamic reward maximization problem without the knowledge of future arrivals of AR requests, by adopting the Multi-Armed Bandits (MAB) technique. Considering maximizing the reward may defer the implementations of some urgent yet low-award requests, we propose a fairness-aware online learning algorithm for the dynamic reward maximization problem, through a data rate prediction mechanism that adopts a multi-task and multi-timescale Long Short-Term Memory (MT2-LSTM) method. Finally, we evaluate the performance of the proposed algorithms for AR applications by building a real test bed. Experimental results show that the proposed algorithms outperform existing studies by improving the award by 13%.

Unmanned Aerial Vehicles (UAVs) have gained increasing attention by both academic and industrial communities, due to their flexible deployment and efficient line-of-sight communication. Recently, UAVs equipped with base stations have been envisioned as a key technology to provide 5G network services for mobile users. In this article, we provide timely services on the data streams of mobile users in a UAV-aided Mobile Edge Computing (MEC) network, in which each UAV is equipped with a 5G small-cell base station for communication and data processing. Specifically, we first formulate a flow-time minimization problem by jointly caching services and offloading tasks of mobile users to the UAV-aided MEC with the aim to minimize the flow time, where the flow time of a user request is referred to the time duration from the request issuing time point to its completion point, subject to resource and energy capacity on each UAV. We then propose a spatial-temporal learning optimization framework. We also devise an online algorithm with a competitive ratio for the problem based upon the framework, by leveraging the round-robin scheduling and dual fitting techniques. Finally, we evaluate the performance of the proposed algorithms through experimental simulation. The simulation results demonstrate that the proposed algorithms outperform their comparison counterparts, by reducing the flow time no less than 19% on average.

In the past decades, explosive numbers of Internet of Things (IoT) devices (objects) have been connected to the Internet, which enable users to access, control, and monitor their surrounding phenomenons at anytime and anywhere. To provide seamless interactions between the cyber world and the real world, Digital twins (DTs) of objects (IoT devices) are key enablers for real time monitoring, behaviour simulations, and predictive decisions on objects. Compared to centralized cloud computing, mobile edge computing (MEC) has been envisioning as a promising paradigm for low latency IoT applications. Accelerating the usage of DTs in MEC networks will bring unprecedented benefits to diverse services, through the co-evolution between physical objects and their virtual DTs, and DT-assisted service provisioning has attracted increasing attention recently. In this article, we consider novel DT placement and migration problems in an MEC network with the mobility assumption of objects and users, by jointly considering the freshness of DT data and the service cost of users requesting for DT data. To this end, we first propose an algorithm for the DT placement problem with the aim to minimize the sum of the DT update cost of objects and the total service cost of users requesting for DT data, through efficient DT placements and resource allocation to process user requests. We then devise an approximation algorithm with a provable approximation ratio for a special case of the DT placement problem when each user requests the DT data of only one object. Meanwhile, considering the mobility of users and objects, we devise an online, two-layer scheduling algorithm for DT migrations to further reduce the total service cost of users within a given finite time horizon. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results show that the proposed algorithms are promising.

With the emergence of various short video platforms such as TikTok and Instagram, coupled with the accelerated pace of people's lives, people are spending more time sharing and watching online videos than ever before, and they gradually turn their attention to short videos with short duration and novel content. Browsing and watching short videos by users with their energy-capacitated devices, such as phones and tablets, have become one of the main ways for users to entertain online. Timely response and high quality online video delivery are of the utmost importance to guarantee the quality of service (QoS) experienced by users. Caching videos at locations close to the video demanders can significantly improve the QoS by reducing the access delay of high quality videos. Together with an explosive growth of mobile devices and great demand for bandwidth, Device-to-Device (D2D) network is emerging as a promising technology to enable ultra-low latency communications, by allowing mobile devices to communicate with each other with or without the involvement of network infrastructures. Caching videos in D2D networks can further reduce video response delays of high quality videos, thereby improving the QoS experienced by users when watching short videos. However, how to cache the most appropriate videos at strategic mobile devices is crucial to satisfy the QoS requirements of users. Specifically, the QoS experienced by users depends on many intertwining factors from both users and the D2D network, such as videos characteristics, various users’ demands for different videos, different communities of users, and energy levels of devices. Motivated by these facts, we investigate the video caching problems in a D2D network. The novelty of our study is to jointly consider the intertwining factors from both users and the D2D network when users access short videos. Specifically, we first formulate an optimization problem of video caching with the objective to minimize the average delay experienced by mobile devices, subject to the cache storage capacity and energy budget of each mobile device. We then propose an approximation algorithm with an approximation ratio for the offline video caching problem. We further devise an online learning algorithm for the online context-aware video caching problem. We finally conduct extensive experiments based on real datasets compared with existing similar studies. Experimental results demonstrate that our algorithms can achieve better average performance with confidence levels. For instance, our algorithms achieve 86% lower average delay experienced by users and 20% average energy consumption of each device, as well as 7% higher average hit ratio and 1.3 times more residual cache storage resource, than their counterparts.

Internet-of-Things (IoT) applications from many industries, such as transportation (maritime, road, rail, air) and fleet management, offshore monitoring, and farming are located in remote areas without cellular connectivity. Such IoT applications continuously generate stream data with hidden values that need to unveiled in real time. Streaming analytics is emerging as a popular type of Big Data analytics to process large volume of stream data for IoT applications in remote regions. Built upon terrestrial-satellite integrated networks, Satellite Edge Computing (SEC) equipped with computing resource in satellites has been envisioning as a key enabling technology to timely analyze stream data of IoT applications in remote regions on the Earth. Considering the dynamically-moving property of satellites in an SEC network, it is vital to optimize the responsiveness of each Big Data analytical query, such that none of such queries takes much longer time to wait for available satellites with sufficient computing resource. Furthermore, the uncertain data volumes of Big Data queries in SEC networks make the resources in satellites fragmented, particularly when the collaboration among satellites is intermittent. Therefore, directly application of existing methods may not guarantee the timelineness of streaming analytics in an SEC network. To address the afore-mentioned unique challenges of streaming analytics in SEC networks, it is urgent to design new algorithms and methods for timely Big Data processing. Specifically, we use theflow timeto capture the responsiveness of streaming analytics in satellite edge computing, which is the time between the generation of the first unit of a dataset and the finish time of the data processing. We consider the flow time minimization problem for query evaluation of Big Data analytics in an SEC network with the aim of minimizing the average flow time of Big Data analytical queries, under an assumption of uncertain volumes of datasets. To this end, we first propose an approximation algorithm with a provable approximation ratio for the offline version of the flow time minimization problem. We then devise an online learning algorithm, referred to the customized Lipschitz bandit learning algorithm, with a bounded regret for the online version of the problem. We finally evaluate the performance of the proposed algorithms in a real SEC network topology. Experiment results show that the performance of the proposed algorithm outperforms its counterparts by at least 13% in terms of flow time.

Mobile Edge Computing (MEC) has emerged as a promising platform to provide various services for mobile applications at the edge of core networks while meeting stringent service delay requirements of users. Digital twin (DT) that is a mirror of a physical object in cyberspace now becomes a key player in smart cities and the Metaverse, which can be used to simulate or predict the behaviours of the object in future. To enable such a simulation or predication to be more accurate and robust, the state of the digital twin needs to be synchronized (updated) with its object quite often. The quality of inference services in a DT-empowered MEC network usually is determined by the state freshness of service models, while a service model further is determined by the state freshness of its source DT data. It is vital to refresh the states of service models frequently in order to provide high quality inference services. In this paper, we study how to maximize the state freshness of both digital twins and a set of inference service models that are built upon digital twins in an MEC network, while the state freshness of a DT or a service model is achieved through frequent synchronizations between the DT and its physical object. Specifically, we first study a novel cost-aware average model freshness maximization problem with the aim to maximize the average freshness of the states of inference service models while minimizing the cost of achieving the model freshness, and show the NP-hardness of the problem. We then formulate an integer linear programming solution for the offline version of the problem, and devise a performance-guaranteed approximation algorithm for a special case of problem when the monitoring period consists of a single time slot only. Also, we develop an efficient online algorithm for the problem through scheduling objects to upload their update data to their digital twins in the network at each time slot efficiently. We finally evaluate the performance of the proposed algorithms through simulations. Simulation results demonstrate that the proposed algorithms are promising.

The advance of Digital Twin (DT) technology sheds light on seamless cyber-physical integration with the Industry 4.0 initiative. Through continuous synchronization with their physical objects, DTs can power inference service models for analysis, emulation, optimization, and prediction on physical objects. With the proliferation of DTs, Digital Twin Network (DTN) slicing is emerging as a new paradigm of service providers for differential quality of service provisioning, where each DTN is a virtual network that consists of a set of inference service models with source data from a group of DTs, and the inference service models provide users with differential quality of services. Mobile Edge Computing (MEC) as a new computing paradigm shifts the computing power towards the edge of core networks, which is appropriate for delay-sensitive inference services. In this paper we consider Age of Information (AoI)-aware inference service provisioning in an MEC network through DTN slicing requests, where the accuracy of inference services provided by each DTN slice is determined by the Expected Age of Information (EAoI) of its inference model. Specifically, we first introduce a novel AoI-aware inference service framework of DTN slicing requests. We then formulate the expected cost minimization problem by jointly placing DT and inference service model instances, and develop efficient algorithms for the problem, based on the proposed framework. We also consider dynamic DTN slicing request admissions where requests arrive one by one without the knowledge of future arrivals, for which we devise an online algorithm with a provable competitive ratio for dynamic request admissions, assuming that DTs of all objects have been placed already. Finally, we evaluate the performance of the proposed algorithms through simulations. Simulation results demonstrate that the proposed algorithms are promising, and the proposed online algorithm improves the number of admitted requests by more than 6% than its counterpart.

In this paper we study the deployment of a UAV (unmanned aerial vehicle) network that consists of multiple UAVs to provide emergent communication services to people trapped in a disaster area, where each UAV is equipped with a base station that has limited computing capacity and power supply, and thus can only serve a limited number of users. Unlike most existing studies focusing on homogenous UAVs, we consider the deployment of heterogeneous UAVs, where different UAVs have different computing capacities. We study a problem of deploying$K$heterogeneous UAVs in the air to form a connected UAV network such that the number of users served by the UAVs is maximized, subject to the constraint that the number of users served by each UAV is no greater than its service capacity, assuming that the maximum number of users can be served by a UAV is given. We then propose a novel$O(\sqrt{\frac{s}{K}})$-approximation algorithm for the problem, where$s$is a given positive integer, e.g.,$s=3$. We finally evaluate the performance of the approximation algorithm. Experimental results show that the number of users served by all UAVs in the approximate solution is improved by 22% compared with the solutions delivered by state-of-the-arts.

This paper addresses the challenging task of language-driven moment retrieval. Previous methods are typically trained to localize the target moment corresponding to a single sentence query in a complicated video. However, this specific moment generally delivers richer contents than the query, i.e., the semantics of one query may miss certain object details or actions in the complex foreground-background visual contents. Such information imbalance between two modalities makes it difficult to finely align their representations. To this end, instead of training with a single query, we propose to utilize the diversity and complementarity among different queries corresponding to the same video moment for enriching the textual semantics. Specifically, we develop a Teacher-Student Moment Retrieval (TSMR) framework to fill this cross-modal information gap. A teacher model is trained to not only encode a certain query but also capture extra complementary queries to aggregate contextual semantics for obtaining more comprehensive moment-related query representations. Since the additional queries are inaccessible during inference, we further introduce an adaptive knowledge distillation mechanism to train a student model with a single query input by selectively absorbing the knowledge from the teacher model. In this manner, the student model is more robust to the cross-modal information gap during the moment retrieval guided by a single query. Experimental results on two benchmarks demonstrate the effectiveness of our proposed method.

With increasingly strict data privacy regulations, federated learning (FL) has become one of the most often heard machine learning techniques due to its privacy-preserving trait. To efficiently implement the FL intelligence, researchers recently resort to a newly emerged computing paradigm, mobile-edge computing (MEC), and bring about a burst of works. However, most existing works neglect practical issues in MEC systems, e.g., device heterogeneity, unstable channel conditions, and unknown user mobility. Any of them, if not handled properly, can cause fatal failures to FL. This article proposed a novel FL framework, called multicore FL (MC-FL), to help FL intelligence land successfully on realistic MEC systems. A distinct feature of MC-FL is maintaining and training multiple global models (GMs) that exhibit different tradeoffs between learning performances and computational complexity. While this modification seems simple, it can effectively handle the device heterogeneity and device status variations, and improve the compatibility and robustness of FL. Furthermore, MC-FL employs a partial client participation scheme that allows participating clients to vary across time. This enables MC-FL to function under uncertain mobile environments. We rigorously prove the convergence of the designed MC-FL framework. In particular, we propose an online client scheduling scheme for MC-FL to judiciously schedule clients for training multiple GMs in a manner that minimizes the completion time of MC-FL. We also provide a service provisioning scenario with MC-FL to show how service subscribers could benefit from multiple GMs and improve their Quality of Experience (QoE). We evaluate our method on real-world data sets, and the results show that MC-FL outperforms state-of-the-art benchmarks.

Mobile-edge computing (MEC) is a new computing paradigm that enables cloud computing and information technology (IT) services to be delivered at the network’s edge. By shifting the load of cloud computing to individual local servers, MEC helps meet the requirements of ultralow latency, localized data processing, and extends the potential of the Internet of Things (IoT) for end-users. However, the crosscutting nature of MEC and the multidisciplinary components necessary for its deployment have presented additional security and privacy concerns. Fortunately, artificial intelligence (AI) algorithms can cope with excessively unpredictable and complex data, which offers a distinct advantage in dealing with sophisticated and developing adversaries in the security industry. Hence, in this article, we comprehensively provide a survey of security and privacy in MEC from the perspective of AI. On the one hand, we use European Telecommunications Standards Institute (ETSI) MEC reference architecture as our-based framework while merging the software-defined network (SDN) and network function virtualization (NFV) to better illustrate a serviceable platform of MEC. On the other hand, we focus on new security and privacy issues, as well as potential solutions from the viewpoints of AI. Finally, we comprehensively discuss the opportunities and challenges associated with applying AI to MEC security and privacy as possible future research directions.

With the rapid growth of Internet of Things (IoT), smart home develops rapidly in these years, which could assist people who need family medical support. It could integrate health care with ambient assisted living (AAL) technologies and provide activities of daily life (ADLs) to the people who need care. This paper proposes a smart home and cross-cloud-and-edge computing based nursing system (NS). In general, a good NS requires low latency, high stability, and the real-time analysis and response, where the conventional centralized cloud computing based approaches cannot meet those requirements very well. To this end, we introduce a novel distributed joint edge-cloud structure to better satisfy these requirements. Moreover, to deal with the security and privacy issues, we introduce the blockchain to verify the identity of data exchanging and differential-privacy (DP) in the NS to protect the healthcare takers’ data privacy. In a word, we propose a privacy-preserving context-aware multi-armed bandit based online learning approach for edge-cloud-enabled NS via blockchain in IoTs. Additionally, our system with a novel top-down expanding tree based structure can support dynamically increasing health care datasets. Extensive experimental and numerical results demonstrate our solution can achieve accurate recommendation results with sublinear regret performance.

Serverless computing is emerging as an enabling technology for elastic and low-cost AI applications in the edge of core networks. It allows AI developers to decompose a complex training and time-sensitive inference task into multiple functions with dependency, and upload the task to a Multi-access Edge Computing platform (MEC) for execution. Serverless computing adopts a popular design principle: the disaggregation of storage and computation, making the functions ‘stateless’. However, most AI applications are ‘stateful’ and rely on an external storage service to manage their states (ephemeral data). This will incur a prohibitively long delay for delay-sensitive AI applications if external services storing the states are far from the serverless functions. Motivated by this critical issue, in this paper we investigate a fundamental problem in serverless computing – the stateful serverless application placement problem, for which, we first propose an efficient heuristic algorithm, and then devise an approximation algorithm with a provable approximation ratio for one of its special cases. We also consider the online version of the problem, and develop an online learning-driven algorithm with a bounded regret. The crux of the online algorithm is the adoption of the multi-armed bandits technique for dynamic admissions of inference requests, under the uncertainty of both data volumes of requests and network delays. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results show that the proposed algorithms outperform their counterparts, reducing at least 32% in the total cost and 27% of the average delay.

Temporal sentence grounding (TSG) is an important yet challenging task in video-based information retrieval. Given an untrimmed video input, it requires the machine to predict the interested video segment semantically related to a given sentence query. Most existing TSG methods train well-designed deep networks to align the semantic between video-query pairs for activity grounding with a large amount of data. However, we argue that these works easily capture the selection biases of video-query pairs in a dataset rather than showing the robust reasoning abilities to handle the rarely appeared pairs (i.e., few-shot contents). To alleviate such limitation of the off-balance data distribution during the network training, in this paper, we propose a novel memory-augmented network called Memory-Guided Semantic Learning Network (MGSL-Net) to handle the few-shot TSG task for enhancing the model generalization ability. Specifically, given the matched video-query input, we first employ a graph attentive cross-modal interaction module to align their semantics in a cycle-consistent manner. Then, we develop the memory modules in both video and query domains to record the cross-modal shared semantic features in the domain-specific persistent memory. At last, a heterogeneous attention module is utilized to integrate the memory-enhanced multi-modal features in both video and query domains with further feature calibration. During training, the memory modules are dynamically associated with both common and rare cases to memorize all appeared contents, alleviating the issue of forgetting the few-shot contents. Therefore, in testing, the rare cases can be enhanced by retrieving the stored memories, improving the generalization ability of the model. Experimental results on three benchmarks (ActivityNet Caption, Charades-STA and TACoS) show the superiority of our method on both effectiveness and efficiency.

Mobile Edge Computing (MEC) has emerged as a promising paradigm catering to overwhelming explosions of mobile applications, by offloading compute-intensive tasks to MEC networks for processing. The surging of deep learning brings new vigor and vitality to shape the prospect of intelligent Internet of Things (IoT), and edge intelligence arises to provision real-time deep neural network (DNN) inference services for users. To accelerate the processing of the DNN inference of a user request in an MEC network, the DNN inference model usually can be partitioned into two connected parts: one part is processed in the local IoT device of the request, and another part is processed in a cloudlet (edge server) in the MEC network. Also, the DNN inference can be further accelerated by allocating multiple threads of the cloudlet to which the request is assigned. In this paper, we study a novel delay-aware DNN inference throughput maximization problem with the aim to maximize the number of delay-aware DNN service requests admitted, by accelerating each DNN inference through jointly exploring DNN partitioning and multi-thread execution parallelism. Specifically, we consider the problem under both offline and online request arrival settings: a set of DNN inference requests is given in advance, and a sequence of DNN inference requests arrives one by one without the knowledge of future arrivals, respectively. We first show that the defined problems are NP-hard. We then devise a novel constant approximation algorithm for the problem under the offline setting. We also propose an online algorithm with a provable competitive ratio for the problem under the online setting. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising

In this paper, we study sensing data collection of IoT devices in a sparse IoT-sensor network, using an energy-constrained Unmanned Aerial Vehicle (UAV), where the sensory data is stored in IoT devices while the IoT devices may or may not be within the transmission range of each other. We formulate two novel data collection problems to fully or partially collect data stored from IoT devices using the UAV, by finding a closed tour for the UAV that consists of hovering locations and the sojourn duration at each of the hovering locations such that the accumulative volume of data collected within the tour is maximized, subject to the energy capacity on the UAV, where the UAV consumes energy on both hovering for data collection and flying from one hovering location to another hovering location. To this end, we first propose a novel data collection framework that enables the UAV to collect sensory data from multiple IoT devices simultaneously if these IoT devices are within the coverage range of the UAV, through adopting the orthogonal frequency division multiple access (OFDMA) technique. We then formulate two data collection maximization problems to deal with full or partial data collection from IoT devices at each hovering location, and show that both defined problems are NP-hard. We instead devise approximation and heuristic algorithms for the problems. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrated that the proposed algorithms are promising.

Mobile Edge Computing (MEC) promises to provide mobile users with delay-sensitive services at the edge of network, and each user service request usually is associated with a Service Function Chain (SFC) requirement that consists of Virtualized Network Functions (VNFs) in order. The satisfaction of a user on his requested service is heavily impacted by the service reliability. In this paper, we study user satisfaction on services provided by an MEC network through introducing a submodular function based metric to measure user satisfaction. We first formulate a novel user satisfaction problem with the aim to maximize the accumulative user satisfaction, assuming that all available computing resource in the MEC network can be used for service reliability enhancement. We show that the problem is NP-hard, and devise an approximation algorithm with a provable approximation ratio for it. We then consider the problem under a given computing resource budget constraint, for which we devise an approximation algorithm with a provable approximation ratio, at the expense of moderate budget violations. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms outperform the comparison baseline algorithms, improving the performance by more$16.1\%$in comparison with the baseline algorithms.

In this paper, we study the employment of a mobile charger to charge lifetime-critical sensors under the multi-node partial-charging model, in which the charger can simultaneously charge the sensors within its charging range and each sensor may be partially charged each time. We notice that existing studies only scheduled the charger to minimize the number of dead sensors, but did not consider the charging scheduling for the sensors that have already run out of their energy, and the dead sensors will be last charged by the mobile charger. Then, their dead durations may be very long. In this paper, we consider not only how to minimize the number of dead sensors but also reduce the dead durations of sensors. To this end, we first formulate a sensor lifetime maximization problem, which is to find a charging tour for a mobile charger to charge sensors, such that the sum of sensor lifetimes is maximized. We then propose a novel$\frac{1}{3}$-approximation algorithm for the problem. We finally evaluate the performance of the proposed algorithm through experiments. Experimental results show that both the average and maximum sensor dead durations by the proposed algorithm are up to 70% shorter than those by existing algorithms.

Multi-access edge computing (MEC) enables extreme low-latency AI services, such as Augmented Reality (AR) and Virtual Reality (VR), by deploying cloudlets in locations close to users. Meanwhile, a 5G hierarchical service market is emerging with both large-scale and small-scale network service providers competing for both computing and network bandwidth resources of an infrastructure provider. In this paper, we investigate the problem of caching services originally deployed in remote clouds to cloudlets in an MEC network in a hierarchical service market. For the service caching problem, we first propose a novel approximation-restricted framework that guarantees the stability of the 5G service market. Under the proposed framework, we first propose an approximation algorithm with a provable approximation ratio for the problem with non-selfish network service providers. We then design an efficient Stackelberg congestion game with selfish network service providers, and analyze the Price of Anarchy (PoA) of the proposed Stackelberg congestion game to measure the efficiency loss of the game due to selfishness of network service providers. Considering that the request rate of each service may not be given in advance, we study the service caching problem with the uncertainlity of request rates, and propose an approximation algorithm and a Stackelberg game via leveraging the randomized rounding technique. We finally evaluate the performance of the proposed algorithms and mechanisms by both simulations and implementations in a real test-bed. Results show that the performance of our proposed mechanisms achieve around 9.2% less cost than those of existing approaches.

With the development of 5G technology, mobile edge computing is emerging as an enabling technique to reduce the response latency of network services by deploying cloudlets at 5G base stations to form mobile edge cloud (MEC) networks. Network service providers now shift their services from remote clouds to cloudlets of MEC networks in the proximity of users. However, the permanent placement of network services into an MEC network is not economic due to limited computing and bandwidth resources imposed on its cloudlets. A smart way is to cache frequently demanded services from remote clouds to cloudlets of the MEC network. In this paper, we study the problem of service caching in an MEC network under a service market with multiple network service providers competing for both computation and bandwidth resources in terms of Virtual Machines (VMs) in the MEC network. We first propose an Integer Linear Program (ILP) solution and a randomized rounding algorithm, for the problem without VM sharing among different network service providers. We then devise a distributed and stable game-theoretical mechanism for the problem with VM sharing among network service providers, with the aim to minimize the social cost of all network service providers, through introducing a novel cost sharing model and a coalition formation game. We also analyze the performance guarantee of the proposed mechanism, Strong Price of Anarchy (SPoA). We third consider the cost- and delay-sensitive service caching problem with temporal VM sharing, and propose a mechanism with provable SPoA. We finally evaluate the performance through extensive simulations and a real world test-bed implementation. Experimental results demonstrate that the proposed algorithms outperform existing approaches by achieving at least$40\%$lower social cost via service caching and resource sharing among different network service providers.

This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given$K$UAVs in the top of a disaster area such that the number of users served by the UAVs is maximized. The deployed UAV network must be connected, since the received data by a UAV from its served users need to be sent to the Internet through relays of other UAVs. Motivated by this application, in this paper we study a more generalized problem – the$h$-hop independently submodular maximization problem, where the MCCP problem is one of its special cases with$h=4$. We propose a$\frac {1-1/e}{2h+3}$-approximation algorithm for the$h$-hop independently submodular maximization problem, where$e$is the base of the natural logarithm. Then, one direct result is a$\frac {1-1/e}{11}$-approximate solution to the MCCP problem with$h=4$, which significantly improves its currently best$\frac {1-1/e}{32}$-approximate solution. We finally evaluate the performance of the proposed algorithm for the MCCP problem in the application of deploying UAV networks, and experimental results show that the number of users served by deployed UAVs delivered by the proposed algorithm is up to 12.5% larger than those by existing algorithms.

Federated learning (FL) is a distributed machine learning technique that enables model development on user equipments (UEs) locally, without violating their data privacy requirements. Conventional FL adopts a single parameter server to aggregate local models from UEs, and can suffer from efficiency and reliability issues – especially when multiple users issue concurrentFL requests. Hierarchical FL consisting of a master aggregator and multiple worker aggregators to collectively combine trained local models from UEs is emerging as a solution to efficient and reliable FL. The placement of worker aggregators and assignment of UEs to worker aggregators plays a vital role in minimizing the cost of implementing FL requests in a Mobile Edge Computing (MEC) network. Cost minimization associated with joint worker aggregator placement and UE assignment problem in an MEC network is investigated in this work. An optimization framework for FL and an approximation algorithm with an approximation ratio for a single FL request is proposed. Online worker aggregator placements and UE assignments for dynamic FL request admissions with uncertain neural network models, where FL requests arrive one by one without the knowledge of future arrivals, is also investigated by proposing an online learning algorithm with a bounded regret. The performance of the proposed algorithms is evaluated using both simulations and experiments in a real testbed with its hardware consisting of server edge servers and devices and software built upon an open source hierarchical FedML (HierFedML) environment. Simulation results show that the performance of the proposed algorithms outperform their benchmark counterparts, by reducing the implementation cost by at least 15% per FL request. Experimental results in the testbed demonstrate the performance gain using the proposed algorithms using real datasets for image identification and text recognition applications.

The real-time communication requirement of the Internet of Things (IoT) applications promotes the convergence of IoT and Mobile Edge Computing (MEC). The MEC paradigm greatly shortens the IoT service delay by leveraging cloudlets (edge servers) of MEC in the proximity of IoT devices. Considering limited computing and storage resources in an MEC network, it is challenging to provide efficient IoT-enabled service provisioning in such a network. In this article, we study the service home identification problem of service provisioning for multi-source IoT applications in an MEC network, by identifying a service home (cloudlet) of each multi-source IoT application for its data processing, querying and storage. Each multi-source IoT application consists of multiple sources located at different geographical locations and each source uploads its data stream via a gateway (its nearby access point) to the MEC network and the uploaded data then is aggregated with the stream data of the other sources of the IoT application at the service home. We here focus on two novel service home identification problems: the service operational cost minimization problem with the aim to minimize the total service operational cost by admitting as many multi-source IoT applications as possible, and the online throughput maximization problem with the aim to maximize the number of multi-source IoT application requests admitted. We first show that both the problems are NP-hard. We then formulate an Integer Linear Programming (ILP) solution to the service operational cost minimization problem, and propose a randomized algorithm with high probability and a deterministic approximation algorithm respectively, at moderate resource capacity violations. We third develop an efficient heuristic algorithm for the problem without any resource violation. Furthermore, we deal with the online throughput maximization problem under an assumption that multi-source IoT application requests arrive one by one without the knowledge of future arrivals, for which we formulate an Integer Linear Programming (ILP) solution to its offline version, followed by devising an online algorithm with competitive ratio. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising, and outperform their comparison counterparts.

Temporal sentence grounding (TSG) is crucial and fundamental for video understanding. Although existing methods train well-designed deep networks with large amount of data, we find that they can easily forget the rarely appeared cases during training due to the off-balance data distribution, which influences the model generalization and leads to unsatisfactory performance. To tackle this issue, we propose a memory-augmented network, called Memory-Guided Semantic Learning Network (MGSL-Net), that learns and memorizes the rarely appeared content in TSG task. Specifically, our proposed model consists of three main parts: cross-modal interaction module, memory augmentation module, and heterogeneous attention module. We first align the given video-query pair by a cross-modal graph convolutional network, and then utilize memory module to record the cross-modal shared semantic features in the domain-specific persistent memory. During training, the memory slots are dynamically associated with both common and rare cases, alleviating the forgetting issue. In testing, the rare cases can thus be enhanced by retrieving the stored memories, leading to better generalization. At last, the heterogeneous attention module is utilized to integrate the enhanced multi-modal features in both video and query domains. Experimental results on three benchmarks show the superiority of our method on both effectiveness and efficiency, which substantially improves the accuracy not only on the entire dataset but also on the rare cases.

Temporal video grounding (TVG) aims to localize a target segment in a video according to a given sentence query. Though respectable works have made decent achievements in this task, they severely rely on abundant video-query paired data, which is expensive to collect in real-world scenarios. In this paper, we explore whether a video grounding model can be learned without any paired annotations. To the best of our knowledge, this paper is the first work trying to address TVG in an unsupervised setting. Considering there is no paired supervision, we propose a novel Deep Semantic Clustering Network (DSCNet) to leverage all semantic information from the whole query set to compose the possible activity in each video for grounding. Specifically, we first develop a language semantic mining module, which extracts implicit semantic features from the whole query set. Then, these language semantic features serve as the guidance to compose the activity in video via a video-based semantic aggregation module. Finally, we utilize a foreground attention branch to filter out the redundant background activities and refine the grounding results. To validate the effectiveness of our DSCNet, we conduct experiments on both ActivityNet Captions and Charades-STA datasets. The results demonstrate that our DSCNet achieves competitive performance, and even outperforms most weakly-supervised approaches.

This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given K UAVs in the top of a disaster area such that the number of users served by the UAVs is maximized. The deployed UAV network must be connected, since the received data by a UAV from its served users need to be sent to the Internet through relays of other UAVs. Motivated by this application, in this paper we study a more generalized problem – the h-hop independently submodular maximization problem, where the MCCP problem is one of its special cases with h = 4. We propose a $\frac{{1 - 1/e}}{{2h + 3}}$-approximation algorithm for the h-hop independently submodular maximization problem, where e is the base of the natural logarithm. Then, one direct result is a $\frac{{1 - 1/e}}{{11}}$-approximate solution to the MCCP problem with h = 4, which significantly improves its currently best $\frac{{1 - 1/e}}{{32}}$-approximate solution. We finally evaluate the performance of the proposed algorithm for the MCCP problem in the application of deploying UAV networks, and experimental results show that the number of users served by deployed UAVs delivered by the proposed algorithm is up to 12.5% larger than those by existing algorithms.

The age of data (AoD) is identified as one of the most novel and important metrics to measure the quality of big data analytics for Internet-of-Things (IoT) applications. Meanwhile, mobile edge computing (MEC) is envisioned as an enabling technology to minimize the AoD of IoT applications by processing the data in edge servers close to IoT devices. In this paper, we study the AoD minimization problem for IoT big data processing in MEC networks. We first propose an exact solution for the problem by formulating it as an Integer Linear Program (ILP). We then propose an efficient heuristic for the offline AoD minimization problem. We also devise an approximation algorithm with a provable approximation ratio for a special case of the problem, by leveraging the parametric rounding technique. We thirdly develop an online learning algorithm with a bounded regret for the online AoD minimization problem under dynamic arrivals of IoT requests and uncertain network delay assumptions, by adopting the Multi-Armed Bandit (MAB) technique. We finally evaluate the performance of the proposed algorithms by extensive simulations and implementations in a real test-bed. Results show that the proposed algorithms outperform existing approaches by reducing the AoD around 10%.

By placing popular contents on the network edges, edge caching becomes a promising technique to improve the quality of experience (QoE) of the end users and reduce backhaul link congestion. In this paper, we examine an open market of crowdsourced video edge caching, where within each time slot, the newcome private edge devices strategically declare their own bids to the Video Content Provider (VCP) operator for contributions; and the operator optimally recruits caching devices among the newcome and existing served devices to maximize the expected QoE, under a budget constraint. From the perspective of newcome edge devices, we propose and study a novel pricing problem, namely Pri-CVEC, to determine the bid prices for profit maximization. The problem is challenging due to the importing of strategic interactions between the newcome devices and the VCP operator, and competition between the newcome and the existing served devices.We formulate it as a stackelberg knapsack problem. By leveraging the dynamic programming and linear programming-relaxation method, we propose Pri-DP and Pri-LPR algorithm, respectively. We extensively conduct simulation experiments to verify the advantages of our approaches.

Crowd counting is a regression task that estimates the number of people in a scene image, which plays a vital role in a range of safety-critical applications, such as video surveillance, traffic monitoring and flow control. In this paper, we investigate the vulnerability of deep learning based crowd counting models to backdoor attacks, a major security threat to deep learning. A backdoor attack implants a backdoor trigger into a target model via data poisoning so as to control the model's predictions at test time. Different from image classification models on which most of existing backdoor attacks have been developed and tested, crowd counting models are regression models that output multi-dimensional density maps, thus requiring different techniques to manipulate. In this paper, we propose two novel Density Manipulation Backdoor Attacks (DMBA- and DMBA+) to attack the model to produce arbitrarily large or small density estimations. Experimental results demonstrate the effectiveness of our DMBA attacks on five classic crowd counting models and four types of datasets. We also provide an in-depth analysis of the unique challenges of backdooring crowd counting models and reveal two key elements of effective attacks: 1) full and dense triggers and 2) manipulation of the ground truth counts or density maps. Our work could help evaluate the vulnerability of crowd counting models to potential backdoor attacks.

X-armed bandits have achieved the state-of-the-art performance in optimizing unknown stochastic continuous functions, which can model many machine learning tasks, specially in big data-driven personalized recommendation. However, bandit algorithms are vulnerable to adversarial attacks. Existing works mainly focus on attacking multi-armed bandits in discrete setting; nevertheless, the attacks against X-armed bandits in continuous setting have not been well explored. In this paper, we aim to bridge this gap and investigate the robustness problem for the X-armed bandits. Specifically, we consider data poisoning attack and propose an attack algorithm named Confidence Poisoning Attack algorithm, which could hijack the clean tree-based X-armed bandits algorithm, i.e., high confidence tree (HCT) and make it choose the nodes including the arm targeted by the attacker very frequently with a sub-linear attack cost, i.e., O(Tα)(0 <α< 1), where T is the total number of rounds. We evaluate the efficiency of our proposed attack algorithm through theoretical analysis and experiments.

As a continuous variant of Multi-armed bandits (MAB), $\mathcal{X}$-armed bandits have enriched many applications of online machine learning like personalized recommendation system. However, the attack and defense to the $\mathcal{X}$-armed bandits remain largely unexplored, though the MAB has proved to be vulnerable. In this paper, we aim to bridge this gap and investigate the robustness analysis for the $\mathcal{X}$-armed bandits. Specifically, we consider action-manipulation attack, which is practical but harder than the existing reward-manipulation attack. We propose an attack algorithm based on a lower bound tree (LBT), which can continuously hijack the learner’s action by perturbing $\mathcal{X}$-armed bandits’ high confidence tree (HCT) construction. As a result, the nodes including the arm targeted by the attacker is selected frequently with a sublinear attack cost. To defend against the LBT attack, we propose a robust version of the HCT algorithm, called RoHCT. We theoretically analyze that the regret of RoHCT is related to the upper bound of the total cost Q and still sublinear to total number of rounds T. We carry out experiments to evaluate the effectiveness of LBT and RoHCT.

Mobile edge computing (MEC) is an enabling technology for low-latency AI applications, by caching AI services originally deployed in remote data centers to 5G base stations in network edge. Due to limited computing resource of 5G base stations, not all services can be cached in base stations to meet the resource demands of user requests. Also, if the workload of a 5G base station reaches to its resource capacity, the energy consumption of the base station will be pushed up exponentially. To reduce the energy consumption and overcome resource limitations on base stations, an alternative is to allow the base stations to collaborate with each other to admit user requests. In this paper, we investigate the problem of collaborative service caching and request offloading between a 5G-enabled MEC and remote data centers, while meeting the quality of service (QoS) requirements of users, and resource capacities on base stations that are operated by multiple selfish network service providers. We aim to maximize the total payoff of all base stations. To this end, we first propose a two-stage optimization framework: In the first stage, we develop a mechanism that adopts a best-reply rule for dynamically distributed coalition formation. In the second stage, we propose a near-optimal payoff allocation method by devising a randomized algorithm with a provable approximation ratio. We then evaluate the performance of the proposed optimization framework by extensive experimental simulations. Simulation results show that the proposed framework outperforms its counterparts by achieving at least 30% higher payoff and 20% lower energy consumption of base stations.

In this paper, we study the employment of multiple Unmanned Aerial Vehicles (UAVs) to monitor Points of Interests (PoIs) in a disaster area, e.g., collapsed buildings after an earthquake, where the UAVs can take photos and videos for the people trapped at PoIs, because such valuable information is imperative to make rescue decisions. Unlike most existing studies that ignored the monitoring time of PoIs and simply minimized the longest flying distance among the UAVs, we observe that it takes time to monitor the PoIs. Then, it is possible that the flying distance of a UAV in its flying tour may not be too long, the tour however contains many densely-located PoIs. Therefore, it will take a very long time for the UAV to monitor the PoIs in its tour. In this paper, we first formulate a problem of finding flying tours for$K$given UAVs to collaboratively monitor PoIs in a disaster area, such that the maximum spent time of the$K$UAVs among their tours is minimized, where the spent time of a UAV in its tour consists of the flying time and the PoI monitoring time. We then propose a novel$5\frac{1}{3}$-approximation algorithm for the problem, improving the best approximation ratio 6 so far for the problem of minimizing the longest flying distance among the UAVs. In addition, we extend the proposed algorithm to the case that each UAV may not be able to monitor all PoIs assigned to it, due to its limited maximum flying time (e.g., 30 minutes), and the UAV must return to its depot to replace its battery. We finally evaluate the performance of the proposed algorithms via simulation environments, and experimental results show that the proposed algorithms are very promising. Especially, the maximum spent times of the$K$UAVs in their tours by the proposed algorithms are up to 30 percent shorter than those by existing algorithms. In addition, the empirical approximation ratios of the proposed algorithms are no more than 2.4, which are much smaller than their theoretical approximation ratios that are at least$5\frac{1}{3}$.

Provisioning reliable network services for mobile users in edge computing environments is the top priority of network service providers, as unreliable services will result in tremendous losses of revenues and customers. In this paper, we study a novel service reliability augmentation problem in a mobile edge computing (MEC) network, where mobile users request network services with service function chain (SFC) and reliability expectation requirements. To enhance the service reliability of user requests, it is a common practice to make use of redundant virtualized network function (VNF) instance placement in case the primary VNF instance fails. We aim to augment the service reliability of each admitted request to its specified reliability expectation, subject to computing capacity on each cloudlet. To this end, we first formulate a novel service reliability augmentation problem for each request with an SFC and a reliability expectation requirement, by augmenting its reliability through redundant VNF instance deployment. We then show that the problem is NP-hard, and provide an admission framework of user requests by placing primary VNF instances of network functions in the SFC to different cloudlets. We then deal with the service reliability augmentation problem of an admitted request under the assumption that all secondary VNF instances of each primary VNF instance must be placed into the cloudlets no more than$l$hops from the cloudlet of its primary VNF instance for a fixed$l$with$1\leq l \leq n-1$, where$n$is the number of cloudlets in the network, for which we formulate an integer linear program solution, and develop a randomized algorithm with a good approximation ratio and high probability, at the expense of moderate resource constraint violations. We also devise a deterministic heuristic for the problem without any resource violation. We third study the service reliability augmentation problem for a set of admitted requests by extending the proposed algorithm for the service reliability augmentation problem for a single request admission. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and their empirical results are superior to their analytical counterparts.

More and more 5G and AI applications demand flexible and low-cost processing of their traffic through diverse virtualized network functions (VNFs) to meet their security and privacy requirements. As such, the Network Function Virtualization (NFV) market has been emerged as a major service market that allows network service providers to trade their network services among customers. Since each service market usually involves complex interplays among players with different roles, efficient mechanisms that guarantee stable and efficient operations of the NFV market are urgently needed. One fundamental problem in the NFV market is how to maximize the social welfare of all players so that all players have incentives to participate in the activities of the market. In this paper, we first formulate a novel social welfare maximization problem in an NFV market of a multi-tier edge cloud network, with the aim to maximize the total revenue collected from all players, and we implement VNF services on Virtual Machines (VMs) leased by service providers to fulfill customers with service requests, where the edge cloud network consists of both cloudlets in edge networks and remote data centers in the core network. We then design an efficient incentive-compatible mechanism for the problem, and analyze the existence of a Nash equilibrium of the mechanism. Also, we consider an online social welfare maximization problem with uncertain values of customers and without the knowledge of future request arrivals, for which we devise an online learning algorithm by adopting the Multi-Armed Bandits (MAB) method with a bounded regret. We finally evaluate the performance of the proposed mechanisms through simulations and a testbed. Results show that the proposed mechanisms deliver up to 27% higher social welfare than those of existing studies

In this paper, we study the deployment of Unmanned Aerial Vehicles (UAVs) to collect data from IoT devices, by finding a data collection tour for each UAV. To ensure the ‘freshness’ of the collected data, the total time spent in the tour of each UAV that consists of the UAV flying time and data collection time must be no greater than a given delay$B$, e.g., 20 minutes. In this paper, we consider a problem of deploying the minimum number of UAVs and finding their data collection tours, subject to the constraint that the total time spent in each tour of any UAV is no greater than$B$. Specifically, we study two variants of the problem: one is that a UAV needs to fly to the location of each IoT device to collect its data; the other is that a UAV is able to collect the data of an IoT device if the Euclidean distance between them is no greater than the wireless transmission range of the IoT device. For the first variant of the problem, we propose a novel 4-approximation algorithm, which improves the best approximation ratio$4\frac {4}{7}$for it so far. For the second variant, we devise the very first constant factor approximation algorithm. We also evaluate the performance of the proposed algorithms via extensive experiment simulations. Experimental results show that the numbers of UAVs deployed by the proposed algorithms are from 11% to 19% less than those by existing algorithms on average.

We are embracing an era of Internet of Things (IoT). The latency brought by unstable wireless networks caused by limited resources of IoT devices seriously impacts the quality of services of users, particularly the service delay they experienced. Mobile Edge Computing (MEC) technology provides promising solutions to delay-sensitive IoT applications, where cloudlets (edge servers) are co-located with wireless access points in the proximity of IoT devices. The service response latency for IoT applications can be significantly shortened due to that their data processing can be performed in a local MEC network. Meanwhile, most IoT applications usually impose Service Function Chain (SFC) enforcement on their data transmission, where each data packet from its source gateway of an IoT device to the destination (a cloudlet) of the IoT application must pass through each Virtual Network Function (VNF) in the SFC in an MEC network. However, little attention has been paid on such a service provisioning of multi-source IoT applications in an MEC network with SFC enforcement. In this article, we study service provisioning in an MEC network for multi-source IoT applications with SFC requirements and aiming at minimizing the cost of such service provisioning, where each IoT application has multiple data streams from different sources to be uploaded to a location (cloudlet) in the MEC network for aggregation, processing, and storage purposes. To this end, we first formulate two novel optimization problems: the cost minimization problem of service provisioning for a single multi-source IoT application, and the service provisioning problem for a set of multi-source IoT applications, respectively, and show that both problems are NP-hard. Second, we propose a service provisioning framework in the MEC network for multi-source IoT applications that consists of uploading stream data from multiple sources of the IoT application to the MEC network, data stream aggregation and routing through the VNF instance placement and sharing, and workload balancing among cloudlets. Third, we devise an efficient algorithm for the cost minimization problem built upon the proposed service provisioning framework, and further extend the solution for the service provisioning problem of a set of multi-source IoT applications. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising.

The Internet of Things (IoT) technology provisions unprecedented opportunities to evolve the interconnection among human beings. However, the latency brought by unstable wireless networks and computation failures caused by limited resources on IoT devices prevents users from experiencing high efficiency and seamless user experience. To address these shortcomings, the integrated Mobile Edge Computing (MEC) with remote clouds is a promising platform to enable delay-sensitive service provisioning for IoT applications, where edge-clouds (cloudlets) are co-located with wireless access points in the proximity of IoT devices. Thus, computation-intensive and sensing data from IoT devices can be offloaded to the MEC network immediately for processing, and the service response latency can be significantly reduced. In this paper, we first formulate two novel optimization problems for delay-sensitive IoT applications, i.e., the total utility maximization problems under both static and dynamic offloading task request settings, with the aim to maximize the accumulative user satisfaction on the use of the services provided by the MEC, and show the NP-hardness of the defined problems. We then devise efficient approximation and online algorithms with provable performance guarantees for the problems in a special case where the bandwidth capacity constraint is negligible. We also develop efficient heuristic algorithms for the problems with the bandwidth capacity constraint. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising in reducing service delays and enhancing user satisfaction, and the proposed algorithms outperform their counterparts by at least 10.8 percent.

More and more artificial intelligence (AI) applications, such as virtual reality (VR) and video analytics, are rapidly progressing towards enterprise and end-users with the promise of bringing immersive experience. Driven by the desire to improve users’ experience and promote business scenarios, such AI applications have unprecedented requirements for ultra-low latency as well as abundant computing resource in networks. Data centers in the core network can meet these demands by deploying various AI services and providing abundant resources. However, data transmission delay from data centers to end-users is too time-consuming because of traffic congestion in the core network, which compromises the performance of the AI applications. 5G and edge computing are emerging technologies to guarantee the timeliness for the delay-sensitive applications. The delay experienced by AI users can be significantly reduced, by ‘caching’ various services that are initially deployed at data centers to cloudlets in edge networks. Although ubiquitous edge service caching is always preferable for improving user experiences, it is impractical to cache all services from data centers to edge cloudlets, due to often limited caching budget of service providers and resource capacity constraints of cloudlets. Therefore, a service provider has to cautiously decide how many instances of a service can be cached, and where to cache the service instances. In this article, we investigate a fundamental problem ofservice cachingfrom remote data centers to edge cloudlets in a multi-tiered edge cloud network. We first develop two approximation algorithms with approximation ratios to solve the problem for users demanding a single type of service. We then devise an efficient heuristic to solve the problem that users require different types of services. We finally conduct extensive experiments on a real test-bed to evaluate the performance of the proposed algorithms, and experimental results demonstrate that our algorithms can outperform some existing algorithms significantly.

This paper addresses the task of segmenting class-agnostic objects in semi-supervised setting. Although previous detection based methods achieve relatively good performance, these approaches extract the best proposal by a greedy strategy, which may lose the local patch details outside the chosen candidate. In this paper, we propose a novel spatiotemporal graph neural network (STG-Net) to reconstruct more accurate masks for video object segmentation, which captures the local contexts by utilizing all proposals. In the spatial graph, we treat object proposals of a frame as nodes and represent their correlations with an edge weight strategy for mask context aggregation. To capture temporal information from previous frames, we use a memory network to refine the mask of current frame by retrieving historic masks in a temporal graph. The joint use of both local patch details and temporal relationships allow us to better address the challenges such as object occlusions and missing. Without online learning and fine-tuning, our STG-Net achieves state-of-the-art performance on four large benchmarks, demonstrating the effectiveness of the proposed approach.

Network Function Virtualization (NFV), characterized by implementing hardware network functions as software in virtual machines (VMs), is a promising technique to provide flexible and agile network services. Meanwhile, mobile edge cloud (MEC) is envisioned as an enabling technology for providing extreme low-latency network services by deploying cloudlets within the proximity of mobile users. However, it is challenging to find an optimal placement for VNFs when considering service chaining requirements in an MEC with cloudlets having limited computing capacity and users having stringent delay requirements. In addition, security requirements of network services in the MEC makes the problem even harder. In this paper, we investigate the problem of trust-aware throughput maximization problem in an MEC, by incorporating QoS, trust requirements of user requests and allowing VNF being shared among mobile users. We first devise an exact solution to the problem by formulating an Integer Linear Program. Due to the inscalability of ILPs for large problem sizes, we propose an efficient heuristic algorithm based on a randomized rounding technique. We finally evaluate the performance of our proposed algorithms against the state-of-the-art by simulations. Results show that the proposed algorithms achieve higher system throughput than their counterparts by 10%.

This paper addresses the problem of temporal sentence grounding (TSG), which aims to identify the temporal boundary of a specific segment from an untrimmed video by a sentence query. Previous works either compare pre-defined candidate segments with the query and select the best one by ranking, or directly regress the boundary timestamps of the target segment. In this paper, we propose a novel localization framework that scores all pairs of start and end indices within the video simultaneously with a biaffine mechanism. In particular, we present a Context-aware Biaffine Localizing Network (CBLN) which incorporates both local and global contexts into features of each start/end position for biaffine-based localization. The local contexts from the adjacent frames help distinguish the visually similar appearance, and the global contexts from the entire video contribute to reasoning the temporal relation. Besides, we also develop a multi-modal self-attention module to provide fine-grained query-guided video representation for this biaffine strategy. Extensive experiments show that our CBLN significantly outperforms state-of-thearts on three public datasets (ActivityNet Captions, TACoS, and Charades-STA), demonstrating the effectiveness of the proposed localization framework. The code is available at https://github.com/liudaizong/CBLN.

Augmented Reality (AR) has various practical applications in healthcare, education, and entertainment. To provide a fully interactive and immersive experience, AR applications require extremely high responsiveness and ultra-low processing latency. Mobile edge computing (MEC) has shown great potential in meeting such stringent requirements and demands of AR applications by implementing AR requests in edge servers within the close proximity of these applications. In this paper, we investigate the problem of reward maximization for AR applications with uncertain demands in an MEC network, such that the reward of provisioning services for AR applications is maximized and the responsiveness of AR applications is enhanced, subject to both network resource capacity. We devise an exact solution for the problem if the problem size is small, otherwise we develop an efficient approximation algorithm with a provable approximation ratio for the problem. We also devise an online learning algorithm with a bounded regret for the dynamic reward maximization problem without the knowledge of the future arrivals of AR requests, by adopting the technique of Multi-Armed Bandits (MAB). We evaluate the performance of the proposed algorithms through simulations. Experimental results show that the proposed algorithms outperform existing studies by 17 % higher reward.

With the fast development of next-generation networking techniques, a Network Function Virtualization (NFV) market is emerging as a major market that allows network service providers to trade various network services among consumers. Therefore, efficient mechanisms that guarantee stable and efficient operations of the NFV market are urgently needed. One fundamental problem in the NFV market is how to maximize the social welfare of all players, so they have incentives to participate in activities of the market. In this paper, we first formulate the social welfare maximization problem, with an aim to maximize the total revenue of all players in the NFV market. For the social welfare maximization problem, we design an efficient incentive-compatible mechanism and analyze the existence of a Nash equilibrium of the mechanism. We also consider an online social welfare maximization problem without the knowledge of future request arrivals. We devise an online learning algorithm based on Multi-Armed Bandits (MAB) to allow both customers and network service providers to make decisions with uncertainty of customers' strategy. We evaluate the performance of the proposed mechanisms by both simulations and test-bed implementations, and the results show that the proposed mechanisms obtain at most 23% higher social welfare than existing studies.

In this paper, we study the deployment of Unmanned Aerial Vehicles (UAVs) to collect data from IoT devices, by finding the data collection tour of each UAV. To ensure the `freshness' of the collected data, a strict requirement is that the total time spent in the tour of each UAV, which consists of UAV flying time and data collection time, must be no greater than a given maximum data collection delay B, e.g., 20 minutes. In this paper, we consider a problem of using the minimum number of UAVs and finding their data collection tours, subject to the constraint that the total time spent in each tour is no greater than B. We study two variants of the problem, one is that a UAV needs to fly to the location of each IoT device to collect its data; the other variant is that a UAV is able to collect the data of the IoT device as long as their Euclidean distance is no greater than a given wireless transmission range. For the first variant of the problem, we propose a novel 4-approximation algorithm, which improves the best approximation ratio 4 4/7 so far. For the second variant, we design the first constant factor approximation algorithm. In addition, we evaluate the performance of the proposed algorithms via extensive experiments, and experimental results show that the average numbers of UAVs deployed by the proposed algorithms are from 11% to 19% less than those by existing algorithms.

Mobile Edge Computing (MEC) has emerged as a promising paradigm catering to overwhelming explosions of mobile applications, by offloading the compute-intensive tasks to an MEC network for processing. The surging of deep learning brings new vigor and vitality to shape the prospect of intelligent Internet of Things (IoT), and edge intelligence arises to provision real-time deep neural network (DNN) inference services for users. To accelerate the processing of the DNN inference of a request in an MEC network, the DNN inference model usually can be partitioned into two connected parts: one part is processed on the local IoT device of the request; and another part is processed on a cloudlet (server) in the MEC network. Also, the DNN inference can be further accelerated by allocating multiple threads of the cloudlet in which the request is assigned.In this paper, we study a novel delay-aware DNN inference throughput maximization problem with the aim to maximize the number of delay-aware DNN service requests admitted, by accelerating each DNN inference through jointly exploring DNN model partitioning and multi-thread parallelism of DNN inference. To this end, we first show that the problem is NP-hard. We then devise a constant approximation algorithm for it. We finally evaluate the performance of the proposed algorithm through experimental simulations. Experimental results demonstrate that the proposed algorithm is promising.

Mobile Edge Computing (MEC) has emerged as a promising networking paradigm that provides delay-sensitive service for mobile users at the edge of core networks, where mobile users can offload their computing-intensive tasks to MEC networks for processing on no time. Furthermore, with the advance of communication and fabrication technologies, mobile devices now have adequate computing and storage processing capabilities. The device-to-device (D2D) offloading as a new offloading technique enables mobile users to offload their tasks to other mobile devices (referred as helper mobile devices) for processing, thereby alleviating the processing burden on servers in MEC. However, fully utilizing the D2D technique in an MEC network for task offloading service is challenging. Particularly, the mobility of both mobile users and their helper mobile devices makes efficient offloading service placement become difficult. In this paper, we study a novel Mobility-aware Dynamic Offloading Service Placement (MDOSP) problem in a D2D-assisted MEC environment with the aim to minimize the total cost of offloading task services that consists of the computing cost, communication delay cost and migration cost, without the knowledge of future mobility information of mobile users and helper mobile devices. We first formulate an Integer Nonlinear Programming (INP) for the offline setting of the problem. We then prove the NP-hardness and develop an online algorithm with a provable competitive ratio for the problem. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, compared with existing baseline algorithms.

Energy harvesting rates of sensors in renewable (e.g., solar energy) wireless sensor networks are not only lower than their energy consumption rates but also temporally varying. Existing studies exploited spatial data correlations among sensors to reduce their energy consumptions, where the data correlations mean that the sensing data of nearby sensors have high similarities. They assumed that the sensing data of nearby sensors are very likely to highly correlated. They adopted a coarse-grained spatial-correlation model, in which sensors are partitioned into different clusters such that the sensors in the same cluster have high data similarities with each other. Then, only the sensor with the maximum residual energy in each cluster sends its sensing data, while the other sensors do not. We, however, notice that the data similarities among nearby sensors in real sensor networks may vary significantly, i.e., ranging from very similar to not similar at all. Since the existing algorithms require that the sensors in the same cluster have high data similarities with each other, the sensors in a network may be partitioned into many clusters and each cluster consists of only a few sensors, where two nearby sensors belong to two different clusters if the sensing data of the two sensors are not highly correlated. Therefore, in the existing studies, many sensors have to send all their data as there are many clusters. Unlike the existing studies, in this article, we first propose a fine-grained spatial correlation model, in which sensors are partitioned into only a few clusters and each cluster consists of many sensors. Then, each cluster master sensor sends all its data to the sink, while the majority of other sensors in the cluster transmit only their nonredundant data, thereby significantly saving sensor energy consumptions. We formulate a novel sensor clustering problem under the proposed model, which is to partition sensors into different clusters and choose a representative sensor for each cluster such that the amount of suppressed redundant data transmissions is maximized. We propose a randomized (0.5-ε)-approximation algorithm for the clustering problem, where E is a given constant with 0 <; ε ≤ 0.5. To further reduce sensor energy consumption, we consider temporal data correlations, where the sensing data by a sensor in a short period are likely to be highly correlated. We investigate a data utility maximization problem that allocates sensor data rates and routing so that the accumulative utility of both spatially and temporally correlated data received by the sink is maximized. We devise a near-optimal algorithm for the problem. We finally evaluate the performance of the proposed algorithms through experiments. the experimental results show that the proposed algorithms are very promising.

Internet-of-Things-enabled E-health system, which could monitor and collect the personal health information (PHI), has gradually transformed the clinical treatment to a more personalized way with in-home monitoring smart devices. Then, with the collected PHI, clinical decision support systems (CDSSs), which are based on data mining techniques and historical electronic medical records (EMRs) to help clinicians make proper treatment decisions, have attracted considerable attention. To address issues, such as network congestion and low rate of responsiveness for traditional methods when implementing CDSSs, we integrate the technologies mobile-edge computing (MEC) and software-defined networking for exploiting the computation resources and storage capacities among edge nodes (ENs) (i.e., MEC servers) in our model. Based on this integrated system, each edge node will deploy a double deep Q-network (DDQN) to obtain a stable and sequential clinical treatment policy. It is enabled by a novel fully decentralized federated framework (FDFF) for aggregating models of DDQN and extracting the knowledge from EMRs across all ENs. Furthermore, we discuss the convergence of FDFF in resource-constrained environments. However, since most EMRs are faced with stringent privacy concerns, we adopt two additively homomorphic encryption schemes to prevent leakage of EMRs' privacy during the training process of FDFF. Finally, we measure the time cost of our additively homomorphic encryption schemes and validate DDQN with experiments on large data sets based on FDFF, which shows promising performance on clinician treatment.

Mobile edge computing becomes a promising technology to mitigate the latency of various cloud services. In addition, network function virtualization (NFV) has been shown a great potential in reducing the operational cost of cloud services while enhancing the flexibility of virtual network function deployments, by implementing dedicated hardware network functions as pieces of software in generic servers. Recently, the GPU acceleration has been investigated to speed up flow processing in virtual network functions (VNFs), by leveraging the parallelism of GPUs. VNFs that need accelerations prefer to stay at cloudlets (locations) equipped with GPUs. However, little attention has been paid for the VNF placement that takes into account GPU-affinity in cloudlets of mobile edge clouds. In this paper, we consider the affinity-aware throughput maximization problem in a mobile edge cloud via leveraging the parallelism on GPUs for user requests with VNF requirements. We consider two types of affinities in the VNF placement: Thesoft-affinitythat allows VNFs to be executed by either CPUs or GPUs in cloudlets; and thehard-affinitythat only allows VNFs to be placed to the GPUs of a specified set of cloudlets. We formulate two corresponding VNF placement problems in a mobile edge cloud. Specifically, we first propose an exact solution to the soft-affinity throughput maximization problem by formulating an Integer Linear Program (ILP). We then propose an efficient algorithm for the problem, by proposing a randomized algorithm with a provable approximation ratio for the hard-affinity-aware throughput maximization problem and extending the proposed approximation algorithm to the soft-affinity throughput maximization problem. Furthermore, assuming that user requests arrive into the mobile edge cloud one by one without the knowledge of future arrivals, we devise an online algorithm with a good competitive ratio for this dynamic hard-affinity-aware throughput maximization problem. Finally, we evaluate the performance of the proposed algorithms, through simulations and implementations in a real test-bed. Experimental results show that the performance of the proposed algorithms outperform their existing counterparts and achieve higher throughput.

Conventional Internet of Things (IoT) applications involve data capture from various sensors in environments, and the captured data then is processed in remote clouds. However, some critical IoT applications (e.g., autonomous vehicles) require a much lower response latency and more secure guarantees than those offered by remote clouds today. Mobile edge clouds (MEC) supported by the network function virtualization (NFV) technique have been envisioned as an ideal platform for supporting such IoT applications. Specifically, MECs enable to handle IoT applications in edge networks to shorten network latency, and NFV enables agile and low-cost network functions to run in low-cost commodity servers as virtual machines (VMs). One fundamental problem for the provisioning of IoT applications in an NFV-enabled MEC is where to place virtualized network functions (VNFs) for IoT applications in the MEC, such that the operational cost of provisioning IoT applications is minimized. In this paper, we first address this fundamental problem, by considering a special case of the IoT application placement problem, where the IoT application and VNFs of each service request are consolidated into a single location (gateway or cloudlet), for which we propose an exact solution and an approximation algorithm with a provable approximation ratio. We then develop a heuristic algorithm that controls the resource violation ratios of edge clouds in the network. For the IoT application placement problem for IoT applications where their VNFs can be placed to multiple locations, we propose an efficient heuristic that jointly places the IoT application and its VNFs. We finally study the performance of the proposed algorithms by simulations and implementations in a real test-bed, Experimental results show that the performance of the proposed algorithms outperform their counterparts by at least 10 percent.

In this article we study a generalized team orienteering problem (GTOP), which is to find service paths for multiple homogeneous vehicles in a network such that the profit sum of serving the nodes in the paths is maximized, subject to the cost budget of each vehicle. This problem has many potential applications in IoTs and smart cities, such as dispatching energy-constrained mobile chargers to charge as many energy-critical sensors as possible to prolong the network lifetime. In this article, we first formulate the GTOP problem, where each node can be served by different vehicles, and the profit of serving the node is a submodular function of the number of vehicles serving it. We then propose a novel (1 - (1/e)1/2+e)-approximation algorithm for the problem, where ε is a given constant with 0 <; ε ≤ 1 and e is the base of the natural logarithm. In particular, the approximation ratio is about 0.33 when ε = 0.5. In addition, we devise an improved approximation algorithm for a special case of the problem where the profit is the same by serving a node once and multiple times. We finally evaluate the proposed algorithms with simulation experiments, and the results of which are very promising. Especially, the profit sums delivered by the proposed algorithms are up to 14% higher than those by existing algorithms, and about 93.6% of the optimal solutions.

With increasing focus on Artificial Intelligence (AI) applications, Deep Neural Networks (DNNs) have been successfully used in a number of application areas. As the number of layers and neurons in DNNs increases rapidly, significant computational resources are needed to execute a learned DNN model. This ever-increasing resource demand of DNNs is currently met by large-scale data centers with state-of-the-art GPUs. However, increasing availability of mobile edge computing and 5G technologies provide new possibilities for DNN-driven AI applications, especially where these application make use of data sets that are distributed in different locations. One fundamental process of a DNN-driven application in mobile edge clouds is the adoption of “inferencing” - the process of executing a pre-trained DNN based on newly generated image and video data from mobile devices. We investigate offloading DNN inference requests in a 5G-enabled mobile edge cloud (MEC), with the aim to admit as many inference requests as possible. We propose exact and approximate solutions to the problem of inference offloading in MECs. We also consider dynamic task offloading for inference requests, and devise an online algorithm that can be adapted in real time. The proposed algorithms are evaluated through large-scale simulations and using a real world test-bed implementation. The experimental results demonstrate that the empirical performance of the proposed algorithms outperform their theoretical counterparts and other similar heuristics reported in literature.

The rise of big data brings extraordinary benefits and opportunities to businesses and governments. Enterprise users can analyze their consumers' data and infer the business value obtained, such as purchasing goods correlations, customer preferences, and hidden patterns. Meanwhile, with the emerge of big data processing frameworks, such as Hadoop and Tensor-flow, more and more mobile users are embracing big data analytics by issuing queries to analyze their data. In this paper, we investigate the problem of Quality-of-Service (QoS) aware query evaluation for big data analytics in a mobile edge cloud to maximize the system throughput while minimizing the query evaluation time of each admitted query, by exploring the materialization of intermediate query results. We consider dynamic big-data query evaluations where user queries arrive one by one without the knowledge of future arrivals, and the system needs to respond to each query by accepting or rejecting the query immediately. We propose an online algorithm for query admissions within a finite time horizon, the proposed algorithm can intelligently determine whether some immediate results during a query evaluation need to be materialized for later use of other queries, by making use of the Reinforcement Learning (RL) method with predictions. We finally investigate the performance of the proposed algorithm by simulations, and results show that the performance of the proposed algorithm is promising, by achieving a higher system throughput while reducing the average evaluation cost per query by from 20% to 52% compared to the comparison benchmarks.

Mobile edge computing (MEC) is emerging as an enabling technology of low-latency network services, such as Augmented Reality (AR) and Virtual Reality (VR), by deploying cloudlets in locations close to users. In MEC networks, telcooperators can place their services to cloudlets, such that the service accessing delay of users is minimized. In this paper, we investigate a fundamental problem of caching services that are originally deployed in remote clouds to cloudlets in an MEC network within the proximity of users. Specifically, we focus on the service caching problem in a two-tiered MEC network with both remote clouds and cloudlets that are close to users, in which multiple network service providers competing computing and bandwidth resources. This setting is significantly different from existing studies that focused on offloading user tasks from mobile devices to cloudlets in MEC networks that typically do not consider a service market with multiple network service providers. For the service caching problem in a two-tiered MEC network, we propose a novel approximation-restricted framework that guarantees the stableness of the service market. Under the proposed framework, an approximation algorithm with an approximation ratio for the problem with non-selfish players and an efficient, stable Stackelberg congestion game with selfish players have been proposed. We also analyze the Price of Anarchy (PoA) of the proposed Stackelberg congestion game to measure the efficiency of the proposed game degrades due to selfish behavior of network service providers. We finally evaluate the performance of our mechanism on both simulated environments and a real test-bed. Results show that the performance of our proposed mechanism is promising.

Mobile edge computing (MEC) is envisioned as an enabling technology for extreme low-latency services in the next generation 5G access networks. In a 5G-enabled MEC, computing resources are attached to base stations. In this way, network service providers can cache their services from remote data centers to base stations in the MEC to serve user tasks in their close proximity, thereby reducing the service latency. However, mobile users usually have various dynamic hidden features, such as their locations, user group tags, and mobility patterns. Such hidden features normally lead to uncertainties of the 5G-enabled MEC, such as user demand and processing delay. This poses significant challenges for the service caching and task offloading in a 5G-enabled MEC. In this paper, we investigate the problem of dynamic service caching and task offloading in a 5G-enabled MEC with user demand and processing delay uncertainties. We first propose an online learning algorithm for the problem with given user demands by utilizing the technique of Multi-Armed Bandits (MAB), and theoretically analyze the regret bound of the algorithm. We also propose a novel architecture of Generative Adversarial Networks (GAN) to accurately predict the user demands based on small samples of hidden features of mobile users. Based on the proposed GAN model, we then devise an efficient heuristic for the problem with the uncertainties of both user demand and processing delay. We finally evaluate the performance of the proposed algorithms by simulations based on a realistic dataset of user data. Experiment results show that the performance of the proposed algorithms outperform existing algorithms by around 15%.

In this paper we study a team orienteering problem, which is to find service paths for multiple vehicles in a network such that the profit sum of serving the nodes in the paths is maximized, subject to the cost budget of each vehicle. This problem has many potential applications in IoT and smart cities, such as dispatching energy-constrained mobile chargers to charge as many energy-critical sensors as possible to prolong the network lifetime. In this paper, we first formulate the team orienteering problem, where different vehicles are different types, each node can be served by multiple vehicles, and the profit of serving the node is a submodular function of the number of vehicles serving it. We then propose a novel (1 - (1/e)1/2+ε)approximation algorithm for the problem, where c is a given constant with 0 ≤ ε ≤ 1 and ε is the base of the natural logarithm. In particular, the approximation ratio is no less than 0.32 when ε = 0.5. In addition, for a special team orienteering problem with the same type of vehicles and the profits of serving a node once and multiple times being the same, we devise an improved approximation algorithm. Finally, we evaluate the proposed algorithms with simulation experiments, and the results of which are very promising. Precisely, the profit sums delivered by the proposed algorithms are approximately 12.5% to 17.5% higher than those by existing algorithms.

With the development of 5G technology, mobile edge computing is emerging as an enabling technique to promote Quality of Service (QoS) of network services. In particular, the response latency of network services can be significantly reduced by deploying cloudlets at 5G base stations in mobile edge clouds. Network service providers that usually deploy their services in remote clouds now shift their services from the remote clouds to the network edge in the proximity of users. However, the permanent placement of their services into edge clouds may not be economic, since computing and bandwidth resources in edge clouds are limited and relatively expensive. A smart way is to cache the services that are frequently requested by mobile users in edge clouds. In this paper, we study the problem of service caching in mobile edge network under a mobile service market with multiple network service providers completing for both computation and bandwidth resources of the edge cloud. We propose an Integer Linear Program (ILP) and a randomized rounding algorithm, for the problem without resource sharing among the network service providers. We also devise a distributed and stable game-theoretical mechanism for the problem with resource sharing among the network service providers, with the objective to minimize the social cost of all network service providers, by introducing a novel cost sharing model and a coalition formation game. We analyze the performance of the mechanism by showing a good guaranteed gap between the solution obtained and the optimal one, i.e., Strong Price of Anarchy (SPoA). We finally evaluate the performance of our algorithms by extensive simulations, and the obtained results show that the social cost of all players can be reduced significantly via allowing cooperation among network service providers in service caching.

We are embracing an era of Internet of Things (IoTs). However, the latency brought by unstable wireless networks and computation failures caused by limited resources on IoT devices seriously impacts the quality of service of user experienced. To address these shortcomings, the Mobile Edge Computing (MEC) platform provides a promising solution for the service provisioning of IoT applications, where edge-clouds (cloudlets) are co-located with wireless access points in the proximity of IoT devices, and the service response latency can be significantly reduced. Meanwhile, each IoT application usually imposes a service function chain enforcement for its data transmission, which consists of different service functions in a specified order, and each data packet transfer in the network from the gateways of IoT devices to the destination must pass through each of the service functions in order.In this paper, we study IoT-driven service provisioning in an MEC network for various IoT applications with service function chain requirements, where an IoT application consists of multiple data streams from different IoT sources that will be uploaded to the MEC network for aggregation, processing, and storage. We first formulate a novel cost minimization problem for IoT-driven service provisioning in MEC networks. We then show that the problem is NP-hard, and propose an IoT-driven service provisioning framework for IoT applications, which consists of streaming data uploading from multiple IoT sources to the MEC network, data stream aggregation and routing, and Virtual Network Function (VNF) instance placement and sharing in cloudlets in the MEC network. In addition, we devise an efficient algorithm for the problem, built upon the proposed service framework. We finally evaluate the performance of the proposed algorithm through experimental simulations. Experimental results demonstrate that the proposed algorithm is promising, compared with the lower bound on the optimal solution of the problem and another comparison heuristic.

Query-based moment localization is a new task that localizes the best matched segment in an untrimmed video according to a given sentence query. In this localization task, one should pay more attention to thoroughly mine visual and linguistic information. To this end, we propose a novel Cross- and Self-Modal Graph Attention Network (CSMGAN) that recasts this task as a process of iterative messages passing over a joint graph. Specifically, the joint graph consists of Cross-Modal interaction Graph (CMG) and Self-Modal relation Graph (SMG), where frames and words are represented as nodes, and the relations between cross- and self-modal node pairs are described by an attention mechanism. Through parametric message passing, CMG highlights relevant instances across video and sentence, and then SMG models the pairwise relation inside each modality for frame (word) correlating. With multiple layers of such a joint graph, our CSMGAN is able to effectively capture high-order interactions between two modalities, thus enabling a further precise localization. Besides, to better comprehend the contextual details in the query, we develop a hierarchical sentence encoder to enhance the query understanding. Extensive experiments on four public datasets demonstrate the effectiveness of our proposed model, and GCSMAN significantly outperforms the state-of-the-arts.

Temporal language localization in videos aims to ground one video segment in an untrimmed video based on a given sentence query. To tackle this task, designing an effective model to extract ground-ing information from both visual and textual modalities is crucial. However, most previous attempts in this field only focus on unidirectional interactions from video to query, which emphasizes which words to listen and attends to sentence information via vanilla soft attention, but clues from query-by-video interactions implying where to look are not taken into consideration. In this paper, we propose a Fine-grained Iterative Attention Network (FIAN) that consists of an iterative attention module for bilateral query-video in-formation extraction. Specifically, in the iterative attention module, each word in the query is first enhanced by attending to each frame in the video through fine-grained attention, then video iteratively attends to the integrated query. Finally, both video and query information is utilized to provide robust cross-modal representation for further moment localization. In addition, to better predict the target segment, we propose a content-oriented localization strategy instead of applying recent anchor-based localization. We evaluate the proposed method on three challenging public benchmarks: ActivityNet Captions, TACoS, and Charades-STA. FIAN significantly outperforms the state-of-the-art approaches.

With the development of deep learning technologies, attribute recognition and person re-identification (re-ID) have attracted extensive attention and achieved continuous improvement via executing computing-intensive deep neural networks in cloud datacenters. However, the datacenter deployment cannot meet the real-time requirement of attribute recognition and person re-ID, due to the prohibitive delay of backhaul networks and large data transmissions from cameras to datacenters. A feasible solution thus is to employ mobile edge clouds (MEC) within the proximity of cameras and enable distributed inference.

The Internet of Things (IoT) technology offers unprecedented opportunities to interconnect human beings. However, the latency brought by unstable wireless networks and computation failures caused by limited resources on IoT devices prevents users from experiencing high efficiency and seamless user experience. To address these shortcomings, the integrated MEC with remote clouds is a promising platform, where edge-clouds (cloudlet) are co-located with wireless access points in the proximity of IoT devices, thus intensive-computation and sensing data from IoT devices can be offloaded to the MEC network for processing, and the service response latency can be significantly reduced. In this paper, we study delay-sensitive service provisioning in an MEC network for IoT applications. We first formulate two novel optimization problems, i.e., the total utility maximization problems under both static and dynamic offloading task request settings, with the aim to maximize the accumulative user satisfaction of using the services provided by the MEC. We then show that the defined problems are NP-hard. We instead devise efficient approximation and online algorithms with provable performance guarantees for the problems. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising.

Machine learning (ML) has been penetrating into our daily life by facilitating many daily applications, e.g., self-driving, cloud gaming, product fault detection and drones. Meanwhile, there is an emerging trend that adopts ML methods into network optimization problems, such as flow classification, traffic engineering, routing, and etc. Conventional ML methods need careful training for a specific application of a given network structure, and the trained model normally cannot be applied to other applications and network structures. In this paper, we aim to design adaptive ML methods for network optimization problems, with the trained models having the ability of being deployed to any similar problems. In particular, we consider the virtualized network function (VNF) provisioning problem as our target optimization problem. We first propose a deep Q-learning-based optimization framework for VNF provisioning in a mobile edge network with network capacity constraints, by devising an adaptive graph feature embedding method. We then propose a series of deep Q-learning based learning algorithms for the problems of service chaining and the throughput maximization, based on the proposed learning-based optimization framework. We also propose a novel design of master-slave dual neural network that enables the decisions on both cloudlet selections and routing path finding. To stabilize and accelerate the convergence of the proposed methods, we devise a novel environment generation and termination strategy and a new structure for the replay buffer. We also evaluate the performance of the proposed framework and algorithms by extensive simulations. Results show that the proposed algorithms outperform existing methods by around 12%, and the trained model in a network can be directly adapted to other network structures and settings.

The increasing Internet-of-Things (IoT) devices have produced large volumes of data. A deep learning technique is widely used to analyze the potential value of these data due to its unprecedented performance in both the academic and industrial communities. However, the data generated from the IoT devices are distributed among different users. Directly combining these data to a central server will cause privacy leakage, especially for personal sensitive data. Rather than centralized training by getting access to all these raw data, an alternative is to collaboratively learn a model in a distributed manner. However, there exist two main challenges in a distributed learning setting. The first one is how to preserve the privacy of users. The second one is to reduce the communication burden (e.g., mobile users have limited bandwidth) due to high-frequent data exchange. To address these two challenges, we design a communication efficient and privacy-preserving framework to enable different participants to distributively learn a model with a privacy protection guarantee. In particular, we develop a differentially private approximate mechanism for the distributed deep learning. In addition, we design a new gradient sparsification method to, at the first time, reduce both upload and download communication costs. The performance of the proposed framework is tested under different neural network structures for different data sets including, image classification and mobile sensor data. The experimental results demonstrate that we can reduce the communication up to only 2% compared to the full gradients exchange and achieve up to 16% accuracy increase compared to the previous works.

Telecommunication networks are undergoing a disruptive transition toward distributed mobile edge networks with virtualized network functions (VNFs) [e.g., firewalls, intrusion detection systems (IDSs), and transcoders] within the proximity of users. This transition will enable network services, especially Internet-of-Things (IoT) applications, to be provisioned as network slices with sequences of VNFs, in order to guarantee the performance and security of their continuous data and control flows. In this article, we study the problems of delay-aware network slicing for multicasting traffic of IoT applications in edge networks. We first propose exact solutions by formulating the problems into integer linear programs (ILPs). We further devise an approximation algorithm with an approximation ratio for the problem of delay-aware network slicing for a single multicast slice, with the objective to minimize the implementation cost of the network slice subject to its delay requirement constraint. Given multiple multicast slicing requests, we also propose an efficient heuristic that admits as many user requests as possible, through exploring the impact of a nontrivial interplay of the total computing resource demand and delay requirements. We then investigate the problem of delay-oriented network slicing with given levels of delay guarantees, considering that different types of IoT applications have different levels of delay requirements, for which we propose an efficient heuristic based on reinforcement learning (RL). We finally evaluate the performance of the proposed algorithms through both simulations and implementations in a real testbed. The experimental results demonstrate that the proposed algorithms are promising.

With the rapid development of the Internet-of-Things (IoT) networks, millions of IoT services provided through wireless networks are waiting for people’s exploration. Such a large number of heterogeneous IoT services produce huge amounts of data in almost real time, known asbig data, many of which cannot be measured or quantified. Hence, a recommended system that aims to deal with the unquantifiable big data is urgently needed. To solve the problem, we propose a novel quantile contextual tree-based multiarmed bandits algorithm to support the large-scale recommendation with both quantifiable and unquantifiable data. Furthermore, the high failure rate of communication has a serious influence on the recommendation accuracy of our system with the widely used D2D technology in today’s IoT network. To improve recommendation accuracy under the D2D communication, we take into account the feedback of historical service receivers and the historical successful delivery rate (SDP) of data transmission at the same time for the service recommendation system. We give theoretical analysis to prove a sublinear bound of the regret. Numerical experiments with tremendously large data sets show that we can balance the regret with the system time cost and guarantee a high SDP.

With advances in wireless communication technology, more and more people depend heavily on portable mobile devices for business, entertainments and social interactions. This poses a great challenge of building a seamless application experience across different computing platforms. A key issue is the resource limitations of mobile devices due to their portable size, however this can be overcome by offloading computation-intensive tasks from the mobile devices to clusters of nearby computers called cloudlets through wireless access points. As increasing numbers of people access the Internet via mobile devices, it is reasonable to envision in the near future that cloudlet services will be available for the public through easily accessible public wireless metropolitan area networks (WMANs). However, the outdated notion of treating cloudlets as isolated data-centers-in-boxes must be discarded as there are clear benefits to connecting multiple cloudlets together to form a network. In this paper we investigate how to balance the workload among cloudlets in an WMAN to optimize mobile application performance. We first introduce a novel system model to capture the response time delays of offloaded tasks and formulate an optimization problem with the aim to minimize the maximum response time of all offloaded tasks. We then propose two algorithms for the problem: one is a fast heuristic, and another is a distributed genetic algorithm that is capable of delivering a more accurate solution compared with the first algorithm, but at the expense of a much longer running time. We finally evaluate the performance of the proposed algorithms in realistic simulation environments. The experimental results demonstrate the significant potential of the proposed algorithms in reducing the user task response time, maximizing user experience.

Mobile edge computing and network function virtualization (NFV) paradigms enable new flexibility and possibilities of the deployment of extreme low-latency services for Internet-of-Things (IoT) applications within the proximity of their users. However, this poses great challenges to find optimal placements of virtualized network functions (VNFs) for data processing requests of IoT applications in a multi-tier cloud network, which consists of many small- or medium-scale servers, clusters, or cloudlets deployed within the proximity of IoT nodes and a few large-scale remote data centers with abundant computing and storage resources. In particular, it is challenging to jointly consider VNF instance placement and routing traffic path planning for user requests, as they are not only delay sensitive but also resource hungry. In this article, we consider admissions of NFV-enabled requests of IoT applications in a multi-tier cloud network, where users request network services by issuing service requests with service chain requirements, and the service chain enforces the data traffic of the request to pass through the VNFs in the chain one by one until it reaches its destination. To this end, we first formulate the throughput maximization problem with the aim to maximize the system throughput. We then propose an integer linear program solution if the problem size is small; otherwise, we devise an efficient heuristic that jointly takes into account VNF placements to both cloudlets and data centers and routing path finding for each request. For a special case of the problem with a set of service chains, we propose an approximation algorithm with a provable approximation ratio. Next, we also devise efficient learning-based heuristics for VNF provisioning for IoT applications by incorporating the mobility and energy conservation features of IoT devices. We finally evaluate the performance of the proposed algorithms by simulations. The simulation results show that the performance of the proposed algorithms is promising.

Mobile Edge Computing (MEC) reforms the cloud paradigm by bringing unprecedented computing capacity to the vicinity of end users at the mobile network edge. This provides end users with swift and powerful computing and storage capacities, energy efficiency, and mobility- and context-awareness support. Furthermore, Network Function Virtualization (NFV) is another promising technique that implements various network functions for many applications as pieces of software in servers or cloudlets in MEC networks. The provisioning of virtualized network services in MEC can improve user service experiences, simplify network service deployment, and ease network resource management. However, user requests arrive dynamically and different users demand different amounts of resources, while the resources in MEC are dynamically occupied or released by different services. It thus poses a significant challenge to optimize the performance of MEC through efficient computing and communication resource allocations to meet ever-growing resource demands of users. In this paper, we study NFV-enabled multicasting that is a fundamental routing problem in an MEC network, subject to resource capacities on both its cloudlets and links. Specifically, we first devise an approximation algorithm for the cost minimization problem of admitting a single NFV-enabled multicast request. We then develop an efficient algorithm for the throughput maximization problem for the admissions of a given set of NFV-enabled multicast requests. We third devise an online algorithm with a provable competitive ratio for the online throughput maximization problem when NFV-enabled multicast requests arrive one by one without the knowledge of future request arrivals. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising.

Stringent delay requirements of many mobile applications have led to the development of mobile edge clouds, to offer low latency network services at the network edges. Most conventional network services are implemented via hardware-based network functions, including firewalls and load balancers, to guarantee service security and performance. However, implementing hardware-based network functions usually incurs both a high capital expenditure (CAPEX) and operating expenditure (OPEX). Network Function Virtualization (NFV) exhibits a potential to reduce CAPEX and OPEX significantly, by deploying software-based network functions in virtual machines (VMs) on edge-clouds. We consider a fundamental problem of NFV-enabled multicasting in a mobile edge cloud, where each multicast request has both service function chain and end-to-end delay requirements. Specifically, each multicast request requires chaining of a sequence of network functions (referred to as a service function chain) from a source to a set of destinations within specified end-to-end delay requirements. We devise an approximation algorithm with a provable approximation ratio for a single multicast request admission if its delay requirement is negligible; otherwise, we propose an efficient heuristic. Furthermore, we also consider admissions of a given set of the delay-aware NFV-enabled multicast requests, for which we devise an efficient heuristic such that the system throughput is maximized, while the implementation cost of admitted requests is minimized. We finally evaluate the performance of the proposed algorithms in a real test-bed, and experimental results show that our algorithms outperform other similar approaches reported in literature.

Driven by stringent delay requirements of mobile applications, the mobile edge cloud has emerged as a major platform to offer low latency network services from the edge of networks. Most conventional network services are implemented via hardware-based network functions, such as firewalls and load balancers, to guarantee service security and performance. However, implementing such hardware-based network functions incurs high purchase and maintenance costs. Network function virtualization (NFV) as a promising technology exhibits great potential to reduce the purchase and maintenance costs by implementing network functions as software in virtual machines (VMs). In this paper, we consider a fundamental problem of NFV-enabled multicasting in a mobile edge cloud, where each multicast request requires to process its traffic in a specified sequence of network functions (referred to as a service chain) before the traffic from a source to a set of destinations. We devise a provable approximation algorithm with an approximation ratio for the problem if requests do not have delay requirements; otherwise, we propose an efficient heuristic for it. We also evaluate the performance of the proposed algorithms against the state-of-the-art NFV-enabled multicasting algorithms, and results show that our algorithms outperform their counterparts.

Multicasting is a fundamental functionality of many network applications, including online conferencing, event monitoring, video streaming, and so on. To ensure reliable, secure, and scalable multicasting, a service chain that consists of network functions (e.g., firewalls, intrusion detection systems, and transcoders) usually is associated with each multicast request. We refer to such a multicast request with service chain requirement as an network function virtualization (NFV)-enabled multicast request. In this paper, we study NFV-enabled multicasting in a software-defined network (SDN) with an aim to maximize network throughput while minimizing the implementation cost of admitted NFV-enabled multicast requests, subject to network resource capacity, where the implementation cost of a request consists of its computing resource consumption cost in servers and its network bandwidth consumption cost when routing and processing its data packets in the network. To this end, we first formulate two NFV-enabled multicasting problems with and without resource capacity constraints and one online NFV-enabled multicasting problem. We then devise two approximation algorithms with an approximation ratio of $2M$ for the NFV-enabled multicasting problems with and without resource capacity constraints, if the number of servers for implementing the service chain of each request is no greater than a constant $M$ (≥1). We also study dynamic admissions of NFV-enabled multicast requests without the knowledge of future request arrivals with the objective to maximize the network throughput, for which we propose an efficient heuristic, and for the special case of dynamic request admissions, we devise an online algorithm with a competitive ratio of $O(\log n)$ for it when $M=1$ , where $n$ is the number of nodes in the network. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising and outperform existing heuristics.

Pushing the cloud frontier to the network edge close to mobile users has attracted tremendous interest not only from cloud operators but also from network service providers. In particular, the deployment of cloudlets in metropolitan area networks enables network service providers to provide low-latency services to mobile users through implementing their specified virtualized network functions (VNFs) while meeting their Quality-of-Service (QoS) requirements. In this paper, we formulate a novel task offloading problem in a mobile edge-cloud network, where each offloading task requests a specified network function with a tolerable delay. We aim to maximize the number of requests admitted while minimizing the operational cost of admitted requests within a finite time horizon, through either sharing existing VNF instances or creating new VNF instances in cloudlets. We first show that the problem is NP-hard, and then devise an efficient online algorithm for the problem by reducing it to a series of minimum weight maximum matching problems. Considering dynamic changes of task offloading request patterns over time, we further develop an effective prediction mechanism for new VNF instance creations and idle VNF instance releases to further lower the operational cost of the network service provider. Also, we devise an online algorithm with a competitive ratio for a special case of the problem where the delay requirements of requests are negligible. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results indicate that the proposed algorithms are promising.

Traditional networks employ expensive dedicated hardware devices as middleboxes to implement Service Function Chains of user requests by steering data traffic along middleboxes in the service function chains before reaching their destinations. Network Function Virtualization (NFV) is a promising virtualization technique that implements network functions as pieces of software in servers or data centers. The integration of NFV and Software Defined Networking (SDN) further simplifies service function chain provisioning, making its implementation simpler and cheaper. In this paper, we consider dynamic admissions of delay-aware requests with service function chain requirements in a distributed cloud with the objective to maximize the profit collected by the service provider, assuming that the distributed cloud is an SDN that consists of data centers located at different geographical locations and electricity prices at different data centers are different. We first formulate this novel optimization problem as a dynamic profit maximization problem. We then show that the offline version of the problem is NP-hard and formulate an integer linear programming solution to it. We third propose an online heuristic for the problem. We also devise an online algorithm with a provable competitive ratio for a special case of the problem where the end-to-end delay requirement of each request is negligible. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are promising.

Enterprise users at different geographic locations generate large-volume data that is stored at different geographic datacenters. These users may also perform big data analytics on the stored data to identify valuable information in order to make strategic decisions. However, it is well known that performing big data analytics on data in geographical-located datacenters usually is time-consuming and costly. In some delay-sensitive applications, the query result may become useless if answering a query takes too long time. Instead, sometimes users may only be interested in timely approximate rather than exact query results. When such approximate query evaluation is the case, applications must sacrifice timeliness to get more accurate evaluation results or tolerate evaluation result with a guaranteed error bound obtained from analyzing the samples of the data to meet their stringent timeline. In this paper, we study quality-of-service (QoS)-aware data replication and placement for approximate query evaluation of big data analytics in a distributed cloud, where the original (source) data of a query is distributed at different geo-distributed datacenters. We focus on the problems of placing data samples of the source data at some strategic datacenters to meet stringent query delay requirements of users, by exploring a non-trivial trade-off between the cost of query evaluation and the error bound of the evaluation result. We first propose an approximation algorithm with a provable approximation ratio for a single approximate query. We then develop an efficient heuristic algorithm for evaluating a set of approximate queries with the aim to minimize the evaluation cost while meeting the delay requirements of these queries. We finally demonstrate the effectiveness and efficiency of the proposed algorithms through both experimental simulations and implementations in a real test-bed, real datasets are employed. Experimental results show that the proposed algorithms are promising.

Software Defined Networking (SDN) is envisioned as a novel technology to enable reliable and scalable network management by decoupling the control plane and data plane. As the network scale increases, multiple controllers have been proposed to solve the problems of scalability and reliability caused by single controller. Although some controller placement schemes based on controller replication have been proposed to recover the controller failure in SDNs, few of them can solve the failure with the existing controllers. In this paper, we propose a QoS and cost aware fault tolerant scheme in multi-controller SDNs by exploring a fine-grained trade-off between controller cost and recovery time. With considering the controlle cost, load and communication delay in the failure recovery, we propose a heuristic algorithm to select backup controllers aiming to minimize the average recovery time, meanwhile avoiding the load oscillation in switch migration. Extensive simulations highlight that our scheme can improve the recovery efficiency compared with some other existing approaches.

Traditional networks employ expensive dedicated hardware devices as middleboxes to implement Service Chains (SC) of user requests by steering data traffic along the middleboxes in the service chains. Network Function Virtualization (NFV) is a promising virtualization technique by implementing network functions as pieces of software in servers or data centers. By leveraging the technique of Software Defined Networking (SDN), NFV can be further enabled in a flexible and dynamic way. In this paper, we consider dynamic admissions of delay-aware NFV-enabled requests in SDNs by leveraging pre-installed NFV instances in data centers. We first formulate a novel revenue maximization problem, and show that the problem is NP-hard. We then propose an online heuristic for the problem. We also devise an online algorithm with a provable competitive ratio for a special case of the problem where the end-to-end delay requirement of requests can be neglected. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are promising.

Traditional network functions (NFs) such as firewalls are implemented in costly dedicated hardware. By decoupling NFs from physical devices, network function virtualization enables virtual network functions (VNF) to run in virtual machines (VMs). However, VNFs are vulnerable to various faults such as software and hardware failures. To enhance VNF fault tolerance, the deployment of backup VNFs in stand-by VM instances is necessary. In case of stateful VNFs, stand-by instances require constant state updates from active instances during its operation. This will guarantee a correct and seamless handover from failed instances to stand-by instances after failures. Nevertheless, such state updates to stand-by instances could consume significant network bandwidth resources and lead to potential admission failures for VNF requests. In this paper, we study the fault-tolerant VNF placement problem with the optimization objective of admitting as many requests as possible. In particular, the VNF placement of active/stand-by instances, the request routing paths to active instances, and state transfer paths to stand-by instances are jointly considered. We devise an efficient heuristic algorithm to solve this problem, and propose a bicriteria approximation algorithm with performance guarantees for a special case of the problem. Simulations with realistic settings show that our algorithms can significantly improve the request admission rate compared to conventional approaches.

Cloud computing built on virtualization technologies promises provisioning elastic computing and bandwidth resource services for enterprises that outsource their IT services as virtual networks. To share the cloud resources efficiently among different enterprise IT services, embedding their virtual networks into a distributed cloud that consists of multiple data centers, poses great challenges. Motivated by the fact that most virtual networks operate on long-term basis and have the characteristics of periodic resource demands, in this paper we study the virtual network embedding problem of embedding as many virtual networks as possible to a distributed cloud such that the revenue collected by the cloud service provider is maximized, while the service level agreements (SLAs) between enterprises and the cloud service provider are met. We first propose an efficient embedding algorithm for the problem, by incorporating a novel embedding metric that accurately models the dynamic workloads on both data centers and inter-data center links, provided that the periodic resource demands of each virtual network are given and all virtual networks have identical resource demand periods. We then show how to extend this algorithm for the problem when different virtual networks may have different resource demand periods. Furthermore, we also develop a prediction mechanism to predict the periodic resource demands of each virtual network if its resource demands are not given in advance. We finally evaluate the performance of the proposed algorithms through experimental simulation based on both synthetic and real network topologies. Experimental results demonstrate that the proposed algorithms outperform existing algorithms from 10 to 31 percent in terms of performance improvement.

Wireless energy transfer technology based on magnetic resonant coupling has emerged as a promising technology for wireless sensor networks, by providing controllable yet continual energy to sensors. In this paper, we study the use of a mobile charger to wirelessly charge sensors in a rechargeable sensor network so that the sum of sensor lifetimes is maximized while the travel distance of the mobile charger is minimized. Unlike existing studies that assumed a mobile charger must charge a sensor to its full energy capacity before moving to charge the next sensor, we here assume that each sensor can be partially charged so that more sensors can be charged before their energy depletions. Under this new energy charging model, we first formulate two novel optimization problems of scheduling a mobile charger to charge a set of sensors, with the objectives to maximize the sum of sensor lifetimes and to minimize the travel distance of the mobile charger while achieving the maximum sum of sensor lifetimes, respectively. We then propose efficient algorithms for the problems. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are very promising. Especially, the average energy expiration duration per sensor by the proposed algorithm for maximizing the sum of sensor lifetimes is only 9 percent of that by the state-of-the-art algorithm while the travel distance of the mobile charger by the second proposed algorithm is only about from 1 to 15 percent longer than that by the state-of-the-art benchmark.

Data transfer in contemporary networks usually is associated with strict policy enforcement for data transfer security and system performance purposes. Such a policy is represented by a service chain consisting of a sequence of network functions such as firewalls, intrusion detection systems, transcoders, etc. Due to the high cost and inflexibility of managing hardware-based network functions, network function virtualization (NFV) has emerged as a promising technology to meet the stringent requirement imposed on the service chain of each data transfer request in a low-cost and flexible way. In this paper, we study policy-aware unicast request admissions with and without end-to-end delay constraints in a software defined network. We aim to minimize the operational cost of admitting a single request in terms of both computing resource consumption for implementing the NFVs in the service chain and bandwidth resource consumption for routing its data traffic, or maximize the network throughput for a sequence of requests without the knowledge of future request arrivals. We first formulate four novel optimization problems and provide a generic optimization framework for the problems. We then develop efficient algorithms for the admission of a single NFV-enabled request with and without the end-to-end delay constraint, where NFV-enabled requests are defined as the requests with policy enforcement requirements. We also devise online algorithms with a guaranteed performance for dynamic admissions of requests without the knowledge of future arrivals. In particular, we provide the very first online algorithm with a provable competitive ratio for the problem without the end-to-end delay requirement. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the proposed algorithms are promising and outperform existing heuristics.

Mobile edge-cloud (MEC) aims to support low latency mobile services by bringing remote cloud services nearer to mobile users. However, in order to deal with dynamic workloads, MEC is deployed in a large number of fixed-location micro-clouds, leading to resource wastage during stable/low workload periods. Limiting the number of micro-clouds improves resource utilization and saves operational costs, but faces service performance degradations due to insufficient physical capacity during peak time from nearby micro-clouds. To efficiently support services with low latency requirement under varying workload conditions, we adopt the emerging network function virtualization (NFV)-enabled MEC, which offers new flexibility in hosting MEC services in any virtualized network node, e.g., access points, routers, etc. This flexibility overcomes the limitations imposed by fixed-location solutions, providing new freedom in terms of MEC service-hosting locations. In this paper, we address the questions on where and when to allocate resources as well as how many resources to be allocated among NFV-enabled MECs, such that both the low latency requirements of mobile services and MEC cost efficiency are achieved. We propose a dynamic resource allocation framework that consists of a fast heuristic-based incremental allocation mechanism that dynamically performs resource allocation and a reoptimization algorithm that periodically adjusts allocation to maintain a near-optimal MEC operational cost over time. We show through extensive simulations that our flexible framework always manages to allocate sufficient resources in time to guarantee continuous satisfaction of applications' low latency requirements. At the same time, our proposal saves up to 33% of cost in comparison to existing fixed-location MEC solutions.

With the development of cloud computing, virtual machine migration is emerging as a promising technique to save energy, enhance resource utilizations, and guarantee Quality of Service (QoS) in cloud datacenters. Most of existing studies on the virtual machine migration, however are based on a single virtual machine migration. Although there are some researches on multiple virtual machines migration, the author usually does not consider the correlation among these virtual machines. In practice, in order to save energy and maintain system performance, cloud providers usually need to migrate multiple correlated virtual machines or migrate the entire virtual datacenter (VDC) request. In this paper, we focus on the efficient online live migration of multiple correlated VMs in VDC requests, for optimizing the migration performance. To solve this problem, we propose an efficient VDC migration algorithm (VDC-M). We use the US-wide US National Science Foundation (NSF) network as substrate network to conduct extensive simulation experiments. Simulation results show that the performance of the proposed algorithm is promising in terms of the total VDC remapping cost, the blocking ratio, the average migration time and the average downtime.

Data transfers in contemporary networks depend upon network functions for ensuring data security and system performance. These policies are represented by a service chain that consists of different network functions such as firewalls, Intrusion Detection Systems (IDSs), transcoders, etc. Network Function Virtualization (NFV) has emerged as a promising technology to meet the stringent requirement imposed on the service chain. In this paper, we study NFV-enabled unicasting in SDNs with and without end-to-end delay constraints. We aim to maximize the network throughput for a sequence of NFV-enabled unicast requests without the knowledge of future arrivals. We first formulate the problems as novel optimization problems in terms of both computing and bandwidth resource consumptions, and provide a generic optimization framework. We then develop an online algorithm with guaranteed performance without the delay requirement and a heuristic with the delay requirement. We finally evaluate the performance of the proposed algorithms through experimental simulations. The results of the experimental simulations show that the proposed algorithms are promising.

Enterprise users at different geographic locations generate large-volume data and store their data at different geographic datacenters. These users may also issue ad hoc queries of big data analytics on the stored data to identify valuable information in order to help them make strategic decisions. However, it is well known that querying such large-volume big data usually is time-consuming and costly. Sometimes, users are only interested in timely approximate rather than exact query results. When this approximation is the case, applications must sacrifice either timeliness or accuracy by allowing either the latency of delivering more accurate results or the accuracy error of delivered results based on the samples of the data, rather than the entire set of data itself. In this paper, we study the QoSaware data replications and placements for approximate query evaluation of big data analytics in a distributed cloud, where the original (source) data of a query is distributed at different geo-distributed datacenters. We focus on placing the samples of the source data with certain error bounds at some strategic datacenters to meet users' stringent query response time. We propose an efficient algorithm for evaluating a set of big data analytic queries with the aim to minimize the evaluation cost of the queries while meeting their response time requirements. We demonstrate the effectiveness of the proposed algorithm through experimental simulations. Experimental results show that the proposed algorithm is promising.

Network function virtualization (NFV) has been emerging as a new paradigm to enable elastic and inexpensive network services in modern computer networks, through deploying flexible virtualized network functions (VNFs) running in virtual computing platforms. Different VNFs can be chained together to form different service chains, to meet various user data routing demands for different network services. In this paper we consider provisioning network services in an NFV-enabled network that consists of data centers for implementing VNF instances of service chains and switches. We study the throughput maximization problem with the aim to admit as many user requests as possible while minimizing the implementation cost of the requests, assuming that limited numbers of instances of each service chain have been stored in data centers. We first propose an optimal algorithm for the problem if all requests have identical packet rates; otherwise, we devise two approximation algorithms with probable approximation ratios, depending on whether the packet traffic of each request is splittable. We finally conduct experiments to evaluate the performance of the proposed algorithms by simulations. Experimental results show that the proposed algorithms achieve at least 15% more throughput than that of a greedy algorithm.

Multicasting is a fundamental functionality of networks for many applications including online conferencing, event monitoring, video streaming, and system monitoring in data centers. To ensure multicasting reliable, secure and scalable, a service chain consisting of network functions (e.g., firewalls, Intrusion Detection Systems (IDSs), and transcoders) usually is associated with each multicast request. Such a multicast request is referred to as an NFV-enabled multicast request. In this paper we study NFV-enabled multicasting in a Software-Defined Network (SDN) with the aims to minimize the implementation cost of each NFV-enabled multicast request or maximize the network throughput for a sequence of NFV-enabled requests, subject to network resource capacity constraints. We first formulate novel NFV-enabled multicasting and online NFV-enabled multicasting problems. We then devise the very first approximation algorithm with an approximation ratio of 2K for the NFV-enabled multicasting problem if the number of servers for implementing the network functions of each request is no more than a constant K (1). We also study dynamic admissions of NFV-enabled multicast requests without the knowledge of future request arrivals with the objective to maximize the network throughput, for which we propose an online algorithm with a competitive ratio of O(log n) when K = 1, where n is the number of nodes in the network. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms outperform other existing heuristics.

Pushing the cloud frontier to the network edge has attracted tremendous interest not only from cloud operators of the IT service/software industry but also from network service operators that provide various network services for mobile users. In particular, by deploying cloudlets in metropolitan area networks, network service providers can provide various network services through implementing virtualized network functions to meet the demands of mobile users. In this paper we formulate a novel task offloading problem in a metropolitan area network, where each offloaded task requests a specific network function with a maximum tolerable delay and different offloading requests may require different network services. We aim to maximize the number of requests admitted while minimizing their admission cost within a finite time horizon. We first show that the problem is NP-hard, and then devise an efficient algorithm through reducing the problem to a series of minimum eight maximum matching in auxiliary bipartite graphs. We also consider dynamic changes of offloading request patterns over time, and develop an effective prediction mechanism to release and/or create instances of network functions in different cloudlets for cost savings. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results indicate that the proposed algorithms are promising.

With more and more businesses and organizations outsourcing their IT services to distributed clouds for cost savings, historical and operational data generated by the services have been growing exponentially. The generated data that are referred to as big data, stored at different geographic datacenters, now become an invaluable asset to these businesses and organizations, as they can make use of the data through analysis to identify business advantages and make strategic decisions. Big data analytics thus has been emerged as a main research topic in cloud computing. To efficiently evaluate a big data analytic query in a distributed cloud consisting of multiple datacenters at different geographic locations interconnected by the Internet, it poses great challenges: (i) the source data of the query typically are located at different datacenters; and (ii) the resource demands of the query may be beyond the supplies of any single datacenter at that moment. In this paper, we formulate an online query evaluation problem for big data analytic queries in distributed clouds, with an objective to maximize the query acceptance ratio while minimizing the accumulative query evaluation cost, for which we first propose a novel metric to model the usages of different resources in the distributed cloud, by incorporating the capacities and workloads of different datacenters and links, as well as resource demands of different queries. We then devise efficient online algorithms for query evaluations under both unsplittable and splittable source data assumptions. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms. Experimental results demonstrate that the proposed algorithms are promising, and outperform other heuristics at 95% confidence intervals.

Today's computer networks rely on a wide spectrum of specialized middleboxes to improve network security and performance. A promising emerging technique to implementing traditional middleboxes is the consolidated middlebox technique, which implements the middleboxes as software in virtual machines in software-defined networks (SDNs), offering economical, and simplified management for middleboxes. This however poses a great challenge, that is, how to find a cost-optimal routing path for each user request such that the data traffic of the request will pass through the middleboxes in their orders in the service chain of the request, with the objective to maximize the network throughput, subject to various resource capacity constraints in SDNs. In this paper, we study the network throughput maximization problem in an SDN under two different scenarios: one is the snapshot scenario where a set of requests at one time slot is given, we aim to admit as many requests in the set as possible to maximize the network throughput; another is the online scenario in which requests arrive one by one without the knowledge of future arrivals. Given a finite time horizon consisting of T equal time slots, the system must respond to the arrived requests in the beginning of each time slot, by either admitting or rejecting the requests, depending on the resource availabilities in the network. For the snapshot scenario, we first formulate an integer linear program (ILP) solution, we then devise two heuristics that strive for fine tradeoffs between the quality of a solution and the running time of obtaining the solution. For the online scenario, we show how to extend the proposed algorithms for the snapshot scenario to solve the online scenario. We finally evaluate the performance of the proposed algorithms through experimental simulations, based on both real and synthetic network topologies. Experimental results demonstrate that the proposed algorithms admit more requests than the baseline algorithm and the quality of the solutions delivered by heuristics is comparable to the exact solution by the ILP in most cases.

Wireless energy transfer has emerged as a promising technology for wireless sensor networks to power sensors with controllable yet perpetual energy. In this paper, we study sensor energy replenishment by employing a mobile charger (charging vehicle) to charge sensors wirelessly in a rechargeable sensor network, so that the sum of charging rewards collected from all charged sensors by the mobile charger per tour is maximized, subject to the energy capacity of the mobile charger, where the amount of reward received from a charged sensor is proportional to the amount of energy charged to the sensor. The energy of the mobile charger will be spent on both its mechanical movement and sensor charging. We first show that this problem is NP-hard. We then propose approximation algorithms with constant approximation ratios under two different settings: one is that a sensor will be charged to its full energy capacity if it is charged; another is that a sensor can be charged multiple times per tour but the total amount of energy charged is no more than its energy demand prior to the tour. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are very promising, and the solutions obtained are fractional of the optimum. To the best of our knowledge, the proposed algorithms are the very first approximation algorithms with guaranteed approximation ratios for the mobile charger scheduling in a rechargeable sensor network under the energy capacity constraint on the mobile charger.

Software-Defined Networking (SDN) has emerged as the paradigm of the next-generation networking through separating the data control plane from the data plane. The forwarding routing table at each of its switch nodes is usually implemented by expensive and power-hungry Ternary Content Addressable Memory (TCAM) that only has limited number of entries, and the bandwidth at each of its links is bounded too. Under this new network architecture, providing a quality service to users by admitting user requests to meet their resource demands is challenging, and very little attention has ever been paid in this regard. In this paper, we will study online unicast and multicast request admissions in SDNs with the aim to maximize the network throughput under both critical network resources and user bandwidth demand constraints, for which we first propose a novel model to characterize the usage costs of node and link resources. We then devise efficient online algorithms for unicast and multicast requests. We also analyze the competitive ratios of the proposed online algorithms, which are O(log n) and O(Kϵlog n) for unicasting and multicasting, respectively, where n is the network size, K is the maximum number of members in a multicast request, and ϵ is a constant with 0 <; e ≤ 1. We finally evaluate the proposed algorithms empirically through simulations. The simulation results demonstrate that the proposed algorithms are very promising.

With advances in wireless communication technology, more and more people depend heavily on portable mobile devices for businesses, entertainments and social interactions. Although such portable mobile devices can offer various promising applications, their computing resources remain limited due to their portable size. This however can be overcome by remotely executing computation-intensive tasks on clusters of near by computers known as cloudlets. As increasing numbers of people access the Internet via mobile devices, it is reasonable to envision in the near future that cloudlet services will be available for the public through easily accessible public wireless metropolitan area networks (WMANs). However, the outdated notion of treating cloudlets as isolated data-centers-in-a-box must be discarded as there are clear benefits to connecting multiple cloudlets together to form a network. In this paper we investigate how to balance the workload between multiple cloudlets in a network to optimize mobile application performance. We first introduce a system model to capture the response times of offloaded tasks, and formulate a novel optimization problem, that is to find an optimal redirection of tasks between cloudlets such that the maximum of the average response times of tasks at cloudlets is minimized. We then propose a fast, scalable algorithm for the problem. We finally evaluate the performance of the proposed algorithm through experimental simulations. The experimental results demonstrate the significant potential of the proposed algorithm in reducing the response times of tasks.

Today's computer networks rely on a wide spectrum of specialized middleboxes to improve their security and performance. Traditional middleboxes that are implemented by dedicated hardware are expensive and hard to manage. A promising technique of consolidated middleboxes - implementing traditional middleboxes in Virtual Machines (VMs) - offers economical yet simplified management of middleboxes in Software-Defined Networks (SDNs). However there are still challenges to realizing user routing requests with network function enforcement (a sequence of middleboxes) while maximizing the network throughput, due to various resource constraints on SDNs, such as forwarding table capacity at each switch, bandwidth resource capacity at each link, and computing resource capacity at each server (Physical Machine). In this paper, we study the problem of maximizing the network throughput of an SDN by admitting as many user requests as possible, where each user request has both bandwidth and computing resource demands to implement its network functions (consolidated middleboxes). We first formulate the problem as a novel network throughput maximization problem. We then provide an Integer Linear Program (ILP) solution for it if the problem size is small, otherwise, we devise two heuristics that strive for the fine tradeoff between the accuracy of solutions and the running times of achieving the solutions. We finally evaluate the performance of the proposed algorithms by simulations, based on real and synthetic network topologies. Experimental results demonstrate that the proposed algorithms are very promising.

The wireless energy transfer technology based on magnetic resonant coupling has emerged as a promising technology for wireless sensor networks, by providing controllable yet perpetual energy to sensors. In this paper we study the use of a mobile charger to wirelessly charge sensors in a rechargeable sensor network so that the sum of sensor lifetimes is maximized while the traveling distance of the mobile charger is minimized. Unlike existing studies that assumed a mobile charger must charge a sensor to its full energy capacity before moving to charge the next sensor, in this paper we assume that each sensor can be partially charged so that more sensors can be charged by the mobile charger before their energy depletions. Under this new charging model, we first formulate a novel optimization problem of scheduling the mobile charger to charge life-critical sensors with an objective to maximize the sum of sensor lifetimes, while minimizing the traveling distance of the mobile charger. Due to NP-hardness of the problem, we then propose an efficient algorithm for it. We finally evaluate the performance of the proposed algorithm through experimental simulations. Simulation results demonstrate that the proposed algorithm is very promising.

With the advancement of information and communication technology, data are being generated at an exponential rate via various instruments and collected at an unprecedented scale. Such large volume of data generated is referred to as big data, which now are revolutionizing all aspects of our life ranging from enterprises to individuals, from science communities to governments, as they exhibit great potentials to improve efficiency of enterprises and the quality of life. To obtain nontrivial patterns and derive valuable information from big data, a fundamental problem is how to properly place the collected data by different users to distributed clouds and to efficiently analyze the collected data to save user costs in data storage and processing, particularly the cost savings of users who share data. By doing so, it needs the close collaborations among the users, by sharing and utilizing the big data in distributed clouds due to the complexity and volume of big data. Since computing, storage and bandwidth resources in a distributed cloud usually are limited, and such resource provisioning typically is expensive, the collaborative users require to make use of the resources fairly. In this paper, we study a novel collaboration- and fairness-aware big data management problem in distributed cloud environments that aims to maximize the system throughout, while minimizing the operational cost of service providers to achieve the system throughput, subject to resource capacity and user fairness constraints. We first propose a novel optimization framework for the problem. We then devise a fast yet scalable approximation algorithm based on the built optimization framework. We also analyze the time complexity and approximation ratio of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. Experimental results demonstrate that the proposed algorithm is promising, and outperforms other heuristics.

Mobile cloud computing is emerging as a main ubiquitous computing platform to provide rich cloud resources for various applications of mobile devices. Although most existing studies in mobile cloud computing focus on energy savings of mobile devices by offloading computing-intensive jobs from mobile devices to remote clouds, the access delays between mobile users and remote clouds usually are long and sometimes unbearable. Cloudlet as a new technology is capable to bridge this gap, and can enhance the performance of mobile devices significantly while meeting the crisp response time requirements of mobile users. In this paper, we study the cloudlet placement problem in a large-scale Wireless Metropolitan Area Network (WMAN) consisting of many wireless Access Points (APs). We first formulate the problem as a novel capacitated cloudlet placement problem that places$K$cloudlets to some strategic locations in the WMAN with the objective to minimize the average access delay between mobile users and the cloudlets serving the users. We then propose an exact solution to the problem by formulating it as an Integer Linear Programming (ILP). Due to the poor scalability of the ILP, we instead propose an efficient heuristic for the problem. For a special case of the problem where all cloudlets have identical computing capacities, we devise novel approximation algorithms with guaranteed approximation ratios. We also devise an online algorithm for dynamically allocating user requests to different cloudlets, if the$K$cloudlets have already been placed. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising and scalable.

Virtual Network Mapping (VNM) has been a key issue for network virtualization need to be addressed. A traditional substrate network is usually managed by multicast InPs, and many applications in the substrate network can be characterized by hybrid virtual networks with both unicast and multicast requests. However, to the best of our knowledge, few researches focus on the problem of hybrid virtual network mapping across multiple domains (HVNMMD). In this paper, we investigate the HVNMMD problem and propose two algorithms to solve this problem efficiently: i) the decomposition-based algorithm, HVNMMD_D; and ii) the spectral clustering based algorithm, HVNMMD_SC. We evaluate the performance of our algorithms through conducting simulation experiments. The simulation results show that the proposed algorithms perform better than existing approaches.

Distributed clouds, consisting of multiple data centers located at different geographical locations, provide a plethora of services to users. They however consume enormous amounts of electricity to power their data centers. The electricity bill is almost 30%-50% of their operational costs. Minimizing the electricity cost of distributed clouds thus is crucial to reduce the operational cost of their cloud service providers. In this paper, we study the problem of minimizing the electricity cost of a distributed cloud, by exploring the heterogeneities of cloud resources and user demands, and time-varying electricity prices, for which we first propose a two-stage optimization framework: dispatching user task requests to different data centers by incorporating the resource demands of the task requests, the workload, and the electricity price in each data center, and energy consumption profiles of different servers in each data center; followed by further energy optimization within each data center through consolidating Virtual Machines (VMs) to different servers to improve the resource utilization ratio. One critical constraint on such task dispatch and VM consolidation is to meet various user Service Level Agreements (SLAs), which include average task scheduling delays and resource demand violation limitations. Under the proposed framework, we then devise efficient scheduling algorithms for task dispatching and VM consolidations, while keeping both the average scheduling delay and resource demand violation limitation of each admitted task met. We finally evaluate the performance of the proposed algorithms through experimental simulations, using real data sets - the real electricity prices and task traces. Experimental simulation results demonstrate that the proposed algorithms are promising.

In this paper we study the cloudlet placement problem in a large-scale Wireless Metropolitan Area Network (WMAN) that consists of many wireless Access Points (APs). Although most existing studies in mobile cloud computing mainly focus on energy savings of mobile devices by offloading computing-intensive jobs from them to remote clouds, the access delay between mobile users and the clouds usually is large and sometimes unbearable. Cloudlet as a new technology is capable to bridge this gap, and has been demonstrated to enhance the performance of mobile devices significantly while meeting the crisp response time requirements of mobile users. In this paper we consider placing multiple cloudlets with different computing capacities at some strategic local locations in a WMAN to reduce the average cloudlet access delay of mobile users at different APs. We first formulate this problem as a novel capacitated cloudlet placement problem that places K cloudlets to some locations in the WMAN with the objective to minimize the average cloudlet access delay between the mobile users and the cloudlets serving their requests. We then propose a fast yet efficient heuristic. For a special case of the problem where all cloudlets have the identical computing capacity, we devise a novel approximation algorithm with a guaranteed approximation ratio. In addition, We also consider allocating user requests to cloudlets by devising an efficient online algorithm for such an assignment. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are promising and scalable.

Cloud computing built on virtualization technologies promises provisioning elastic computing and communication resources to enterprise users. To share cloud resources efficiently, embedding virtual networks of different users to a distributed cloud consisting of multiple data centers (a substrate network) poses great challenges. Motivated by the fact that most enterprise virtual networks usually operate on long-term basics and have the characteristics of periodic resource demands, in this paper we study the virtual network embedding problem by embedding as many virtual networks as possible to a substrate network such that the revenue of the service provider of the substrate network is maximized, while meeting various Service Level Agreements (SLAs) between enterprise users and the cloud service provider. For this problem, we propose an efficient embedding algorithm by exploring periodic resource demands of virtual networks, and employing a novel embedding metric that models the workloads on both substrate nodes and communication links if the periodic resource demands of virtual networks are given; otherwise, we propose a prediction model to predict the periodic resource demands of these virtual networks based on their historic resource demands. We also evaluate the performance of the proposed algorithms by experimental simulation. Experimental results demonstrate that the proposed algorithms outperform existing algorithms, improving the revenue from 10% to 31%.

Cooperative communication effectively enhances the channel capacity of wireless networks by allowing some single-antenna nodes to relay data for other nodes. In such a communication scheme, choosing appropriate relay nodes is critical to maximize the overall network performance. In this paper, we consider the assignment problem of relay nodes in a cooperative wireless network, where physical relay infrastructures and relay supporting services (relay assignment) are independently operated by different selfish entities, each of which is driven by its own benefit. We first formulate the problem as a repeated double auction by taking into account the benefits of all entities in the system. That is, we consider a system consisting of a set of source-to-destination pairs, relay nodes, group agents, and the auctioneer, where source nodes are grouped into different groups and each group is represented by a group agent. The source nodes and group agents seek opportunities to maximize their own benefits through untruthful bidding, colluding with each other, and so on. We then show that these behaviors will jeopardize the social benefit of all entities in the system. To mitigate the effect of such behaviors, we devise a truthful repeated double auction that is able to bound the collusion probability of each entity. We finally conduct experiments by simulations to evaluate the performance of the proposed auction mechanism. Empirical results show that the proposed auction is effective in collusion-resistance with bounded collusion probabilities. To our best knowledge, this is the first auction mechanism for relay assignment in wireless networks that is truthful, collusion-resistant, budget-balance and individual-rational.

Data centers, serving as infrastructures for cloud services, are growing in both number and scale. However, they usually consume enormous amounts of electric power, which lead to high operational costs of cloud service providers. Reducing the operational cost of data centers thus has been recognized as a main challenge in cloud computing. In this paper we study the minimum operational cost problem of fair request rate allocations in a distributed cloud environment by incorporating the diversity of time-varying electricity prices in different regions, with an objective to fairly allocate requests to different data centers for processing while keeping the negotiated Service Level Agreements (SLAs) between request users and the cloud service provider to be met, where the data centers and web portals of a cloud service provider are geographically located in different regions. To this end, we first propose an optimization framework for the problem. We then devise a fast approximation algorithm with a provable approximation ratio by exploiting combinatorial properties of the problem. We finally evaluate the performance of the proposed algorithm through experimental simulation on real-life electricity price data sets. Experimental results demonstrate that the proposed algorithm is very promising, which not only outperforms other existing heuristics but also is highly scalable.

In this paper we consider a remote monitoring scenario where the monitoring center is geographically located far away from the region of the deployed sensor network, and the sensing data by the sensors is transmitted to the monitoring center through a third party telecommunication service, thus a cost associated with this service will be incurred, which is related to the amount of data successfully received by the monitoring center within a specified period. For this scenario, we first formulate a novel optimization problem, namely, the throughput guaranteed service cost minimization problem with an objective to minimize the service cost while the specified network throughput requirement is guaranteed. We show that the problem is NP-complete. We then propose a heuristic for it. The key ingredients of the heuristic include identifying gateways and finding an energy-efficient forest of routing trees rooted at the gateways. Finally, we conduct experiments by simulation to evaluate the performance of the proposed heuristic. The experimental results demonstrate the proposed algorithm outperforms other two mentioned algorithms in terms of both service cost and the network lifetime.

To deploy a wireless sensor network for the purpose of large-scale monitoring, in this paper, we propose a heterogeneous and hierarchical wireless sensor network architecture. The architecture consists of sensor nodes, gateway nodes, and mobile sinks. The sensors transmit their sensing data to the gateway nodes for temporary storage through multihop relays, while the mobile sinks travel along predetermined trajectories to collect data from nearby gateway nodes. Under this paradigm of data gathering, we formulate a novel constrained optimization problem, namely, the capacitated minimum forest (CMF) problem, for the decision version of which we first show NP-completeness. We then devise approximation algorithms and provide upper bounds for their approximation ratios. We finally evaluate the performance of the proposed algorithms through experimental simulation. In our experiments, the approximation ratio delivered by the proposed algorithms is always less than 2. In the case of arbitrary gateway capacities, this contrasts our theoretical results which show that the approximation ratio is at most linear in the number of gateways. Our experiments thus indicate that for realistic inputs, our worst case analysis of the approximation ratio is very conservative. The proposed algorithms are the first approximation algorithms for the CMF problem, and our techniques may be applicable to other constrained optimization problems beyond wireless sensor networks.

In this paper we investigate the network lifetime maximization problem in a delay-tolerant wireless sensor network with a mobile sink by exploiting a nontrivial tradeoff between the network lifetime and the data delivery delay. We formulate the problem as a joint optimization problem that consists of finding a trajectory for the mobile sink and designing an energy-efficient routing protocol to route sensing data to the sink, subject to the bounded delay on data delivery and the given potential sink location space. Due to NP-hardness of the problem, we then propose a novel optimization framework, which not only prolongs the network lifetime but also improves the other performance metrics including the network scalability, robustness, and the average delivery delay. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm against other heuristics. The experimental results demonstrate that the proposed algorithm outperforms the others significantly in terms of network lifetime prolongation.

Deployment of relay nodes to existing wireless net-works recently has received much attention since the channel capacity from sources to destinations through the cooperation of relay nodes is greatly enhanced. However, choosing appropriate relay nodes is critical to maximize the overall network performance. In this paper, we consider the assignment problem of relay nodes in a cooperative wireless network, where physical relay infrastructures and relay supporting services (relay assignment) are independently operated by different selfish entities with each being driven by its own benefit. We first formulate the problem as a repeated double auction by taking into account the benefits of all entities. Specifically, we consider a system that consists of a set of source-to-destination pairs, where the source nodes are grouped into groups and each of them is represented by a group agent. We assume that both the source nodes and the group agents seek opportunities to maximize their own benefits through various means including untruthful bidding and collusion with each other, and so on. To maximize the social benefit of the system that include the benefits of the source nodes, the relay nodes and the auctioneer, we devise an auction which we refer it to as the repeated multi-heterogeneous-item double auction with collusion resistance. We also analytically show that this auction is not only truthful but also collusion resistant. The experimental results indicate that the proposed auction is effective in collusion-resistance.

As an important part of the smart space, body sensor networks (BSNs) provide continuous health monitoring and automation assistance for smart environment residents. A high degree of security and reliability for BSN is extremely required. An adaptive and flexible intrusion-tolerant scheme for BSN, namely ITFBS, is proposed. ITFBS dynamically detects intrusions according to the collected intrusion-related information, and it can provide an adaptive intrusion-tolerant strategy with passive replication by utilising two-step threshold-based intrusion detection and replicas classification. The correctness and effectiveness of ITFBS is theoretically proved, and the experimental results show that ITFBS can effectively tolerate intrusions with low power consumption and high adaptability.