Real-time video analytics (VA) presents challenges due to its computational intensity and latency sensitivity, especially when processed on mobile devices with limited local resources. We propose to offload VA tasks to edge servers with diverse computational capabilities. We present a "detect + track" approach with on-device object tracking and edge-assisted object detection. We formulate a long-term nonlinear integer programming to maximize the overall accuracy within detection frequency and latency constraints. We then design a queue-based online optimization algorithm to solve it: relax the original problem from the integer domain to the real domain, then employ a queue-based adaptation and randomized rounding strategy. Via rigorous proof, both dynamic regret regarding detection accuracy and the real-time requirement are ensured. Evaluation results also demonstrate the effectiveness of our approach.

The demand for video analytics is increasing rapidly. Due to the limited computational and network resources on edge servers, adjusting video configurations such as resolution and frame rate has become an effective strategy to reduce computational and transmission costs. However, this can also compromise detection accuracy, necessitating a balance between resource consumption and analytics accuracy. Also, the dynamic availability of edge servers and variability in their energy consumption further complicates making offloading decisions and configuration selection. In this paper, we first model the problem as a mixed planning program. Then we propose a volatile MAB-based configuration selection algorithm, VACS, which aims to maximize video analytics accuracy while reducing the overall energy consumption. Rigorous proof measures the gap between online decisions and the optimum. Extensive experiments validate the effectiveness of VACS.

Edge Video Analytics (EVA) significantly reduces response time by executing analytical tasks at the edge. However, it inevitably faces accuracy loss when dealing with highly complex analytical scenarios. To overcome this, we propose offloading the most complex video frames to the cloud while processing other frames at the edge. Nevertheless, determining both the quantity and the specific selection of frames for offloading poses challenges due to edge-cloud bandwidth constraints and the dynamic nature of video content. To tackle this problem, we present a Discerning and Elastic Offloading Framework (DEOF), which consists of an Accuracy Predictor and an Offloading Scheduler. The former identifies the detection complexity of each frame by predicting its F1-score gain based on multidimensional information, enabling it to discern and select the most complex frames for offloading. The latter determines the optimal proportion of frames to process in the cloud and at the edge by designing a Lyapunov-optimization-based algorithm, which elastically adjusts this proportion in response to time-varying video content and resource conditions, thus ensuring both adaptability and efficiency. We have implemented DEOF fully based on COTS hardware, and the experimental results demonstrate the effectiveness of DEOF, showing that our system can reduce offloaded data volume by$7.1 \%-36.3 \%$, decrease latency by$\mathbf{2. 6 \% - 1 9. 5 \%}$, and improve accuracy by$\mathbf{2. 6 \%}$3.2 % compared to alternative methods.

With the proliferation of edge computing and the Internet of Things (IoT), inference-driven intelligent cameras are increasingly deployed for resource-efficient and privacypreserving processing. In real-world scenarios, such as traffic surveillance, cameras deployed at different locations (e.g., intersections or corners) experience imbalanced inference workloads, leading to latency bottlenecks and resource underutilization. To address this, we propose ReMO, an adaptive framework for collaborative video analytics. Unlike full-frame offloading, ReMO divides video frames into regions to reduce data transmission and enable fine-grained load balancing. It consists of two key components: a Region Generator that analyzes scene features to identify regions with varying detection needs, and a Region Scheduler that formulates scheduling as an integer nonlinear problem, solved via an adaptive online algorithm based on Lyapunov optimization and Markov approximation. Experimental results demonstrate that ReMO effectively reduces latency by$9.3-26.3 \%$while maintaining high accuracy, outperforming baseline strategies.

Video analytics pipelines migrating to edge deployments are facing performance bottlenecks under limited bandwidth. Non-uniform intra-frame encoding emerges to further compress pixels without affecting the output of the server deep neural network (DNN), while it is inefficient in high-resolution video streaming at low bandwidth. The detail enhancement capability of neural super-resolution (SR) permits resolution downsampling and aggressive compression on edge devices for low-latency transmission. To exploit its accuracy potential, DNN-oriented non-uniform encoding is expected to be additionally aware of SR models. However, traditional codecs struggle to cope with both quality optimization for SR and global semantic features for DNN. We advocate neural codecs for coordinated encoding and enhancement, enabling analytic-oriented video streaming with optimal accuracy-delay tradeoffs. Our system, VidIQ, achieves quality-enhanced real-time video analytics by 1) improving the network architecture of neural codecs (at two granularity) to integrate SR models into a DNN-oriented analytics pipeline, and 2) adapting the multi-scale encoder and SR-decoder to scene dynamics (i.e., content and bandwidth variations) with the help of the monolithic controller to hold a performance advantage. Extensive evaluations showcase that VidIQ reduces end-to-end delay by 35.8% and improves analytics accuracy by 21.2% compared to the recent video compression, enhancement, and streaming baselines.

Video analytics pipelines (VAPs) have been a paradigm for large-scale video analytics. Due to temporal redundancy in video, frame filtering is widely used in VAPs to reduce analysis workload. However, existing works overlook a limitation: while inference operates only on selected frames, decoders must still process many redundant frames due to codec dependencies, leading to over-decoding trap. This limitation stems from the reference-based design in modern codecs, which require decoding preceding frames to reconstruct any selected one. As a result, over-decoding has become the practical bottleneck in VAPs using modern decoders, highlighting a critical but under-explored problem. To address this issue, we propose ParaDeco, a high-throughput video analytics framework featuring a novel frame-level parallel generative decoder. Unlike traditional decoders, ParaDeco adopts a decode-what-matters approach with decoupled frame dependencies. To decode arbitrary frames independently, ParaDeco generates frame-wise features as standalone skeletons using compressed video metadata, then predicts pseudo frames maintaining semantic consistency with original frames. Moreover, ParaDeco identifies which frames truly matter for analysis via delicate contribution-based frame filtering. We implement ParaDeco on a cloud server and evaluate it on large-scale real-world video datasets. Our experimental results show that ParaDeco achieves a 2.76× speedup on average compared to state-of-the-art VAPs.

As large language models (LLMs) are gaining increasing popularity across a wide range of web applications, it is of great importance to optimize service-level objectives (SLOs) for LLM inference services to enhance user satisfaction and improve the competitiveness of cloud vendors. In this paper, we observe that adjusting the parameters of LLM inference engines can improve service performance, and the optimal parameter configurations of different services are different. Therefore, we propose SCOOT, an automatic performance tuning system to optimize SLOs for each LLM inference service by tuning the parameters of the inference engine. SCOOT jointly exploits single-objective and multiple-objective Bayesian optimization (BO) techniques to handle various optimization objectives via exploration and exploitation. Moreover, SCOOT prunes the search space with known constraints and adopts a random forest to learn hidden constraints during the tuning process to mitigate invalid exploration. To improve the tuning efficiency, SCOOT utilizes the parallel suggestion to accelerate the tuning process. Extensive experiments demonstrate that SCOOT considerably outperforms existing tuning techniques in SLO optimization while greatly improving the tuning efficiency. Moreover, SCOOT is universally applicable to various LLM inference engines including vLLM and TensorRT-LLM. Currently, SCOOT has already been implemented in the production environment at Ant Group.

We are now embracing an era of edge computing and artificial intelligence, and the combination of the two has spawned a new field of research called edge intelligence. Massive amounts of data is generated at the edge of network, which relies on artificial intelligence to realize its potential. Meanwhile, artificial intelligence is able to flourish when processing diverse edge data. However, the computation and storage resources of edge servers are not unlimited. For some large-scale intelligent applications, it is difficult to meet their service quality requirements by directly offloading the entire application to a nearby server for processing. Due to the heterogeneity of server resources in edge environments, how to balance the workload among edge servers to provide better services also becomes complicated. The goal of this paper is to minimize the total cost of offloading large-scale applications consisting of many dependent tasks in an edge system. We formulate the Dependent task Offloading with Service Caching (DOSC) problem, which is proved to be NP-hard. A dynamic planning-based algorithm is introduced to solve fixed-DOSC, in which some services are pre-configured on the edge server, and other services can not be downloaded from the remote cloud. We also present a theoretical analysis on the performance guarantee of the dynamic planning-based algorithm. Then, we propose a near-optimal algorithm using the Gibbs sampling to solve the general DOSC problem. Testbed experiments and trace-driven simulations are conducted to verify the performance of our algorithm. Our algorithm, shown to be the most effective in terms of cost, considers both service caching and task dependencies when task offloading in comparison to other baseline algorithms.

To enable edge AI providers to recruit edge devices and use them to deploy AI models and provision inference services, we conduct a comprehensive mathematical and algorithmic study on a novel incentive and optimization mechanism based on repeated auctions. We first model and formulate a time-cumulative social cost optimization problem to capture the challenges of the trade-off between cost and accuracy, the dependency between adjacent auctions, and the need of achieving desired economic properties. Then, to solve this intractable non-linear integer program in an online manner, we design a set of polynomial-time algorithms that work together. Our approach dynamically chooses and switches winning bids under careful control, incorporates online learning to overcome posterior inference accuracy and workload queue dynamics, and leverages randomization to strategically convert fractional decisions of model placement and query dispatch into integers. We also allocate payments to meet the necessary and sufficient conditions for the desired economic properties. Further, we rigorously prove the constant competitive ratio, the sub-linear regret and fit, and the truthfulness and individual rationality for our proposed approach. Finally, through extensive experiments using real devices, AI models, and data traces, we have validated the substantial advantages of our proposed approach compared to the baselines and the state-of-the-art methods.

Massively deployed cameras form a tightly connected network which generates video streams continuously. Benefiting from advances in computer vision, automated real-time analytics of video streams can be of practical value in various scenarios. As cameras become more dense, cross-camera video analytics has emerged. Combining video contents from multiple cameras for analytics is certainly more promising than single-camera analytics, which can realize cross-camera pedestrian tracking and cross-camera complex behavior recognition. Some works focused on optimization of cross-camera video analytic applications, but most of them ignore specific network situation between cameras and edge servers. Furthermore, most of them ignore the super resolution technique, which is proven to be a source of efficiency. In this paper, we first verify the potential gain of super resolution on cross-camera video analytic tasks. Then, we design and implement a cross-camera real-time video streaming analytic system,${\mathsf {Scrava}}$, which leverages super resolution to augment low-resolution videos and simultaneously reduce bandwidth consumption.${\mathsf {Scrava}}$enables real-time cross-camera video analytics and enhances video segments with the SR module under poor network conditions. We take cross-camera pedestrian tracking as an example, and experimentally verifies the effectiveness of super resolution on real-time cross-camera video analytics. Compared with using low-resolution video segments,${\mathsf {Scrava}}$can improve the F1 score by 47.16%, verifying the feasibility of exploiting super resolution to improve the performance of real-time cross-camera video analytic systems.

Deep neural network (DNN)-based real-time video analytics service, as a core module for numerous crucial applications such as augmented reality (AR), has garnered increasing research attention, where mobile edge computing (MEC) is often leveraged to mitigate its real-time processing burden on resource-constrained user devices. For Quality of Experience (QoE) optimization, latest works employ reinforcement learning (RL)-based methods to adaptively adjust configurations (e.g., resolution and frame rate), yet still presenting significant challenges. Firstly, we observe a substantial diversity in QoE patterns among users. Given that existing methods integrate a fixed QoE pattern in parameter training, it is intuitive to customize a policy network for each user. However, this necessitates significant training investment, failing to support on-the-fly deployment for new users. Secondly, given the dual dynamics from both the network and video content in edge video analytics system, existing methods often fall into the dilemma of fitting newly emerged and diverse system states with offline-trained fixed parameters. While it is promising to employ online learning algorithms, most of them struggle to catch up with the high dynamics. We hence proposeMystique. In real-time edge video analytics domain, it is the first meta-RL-based user-level configuration adaptation framework. Mystique establishes an initial model in offline meta training with model-agnostic meta-learning (MAML), enabling swift online adaptation to new users and system states through limited gradient updates from initial parameters. Comprehensive experiments illustrate that Mystique can improve QoE by 42% on average compared to prior works.

With the development of large-scale artificial intelligence services, edge devices are becoming essential providers of data and computing power. However, these edge devices are not immune to malicious attacks. Federated learning (FL), while protecting privacy of decentralized data through secure aggregation, struggles to trace adversaries and lacks optimization for heterogeneity. We discover that FL augmented with Differentiable Architecture Search (DARTS) can improve resilience against backdoor attacks while compatible with secure aggregation. Based on this, we propose a federated neural architecture search (NAS) framwork named SLNAS. The architecture of SLNAS is built on three pivotal components: a server-side search space generation method that employs an evolutionary algorithm with dual encodings, a federated NAS process based on DARTS, and client-side architecture tuning that utilizes Gumbel softmax combined with knowledge distillation. To validate robustness, we adapt a framework that includes backdoor attacks based on trigger optimization, data poisoning, and model poisoning, targeting both model weights and architecture parameters. Extensive experiments demonstrate that SLNAS not only effectively counters advanced backdoor attacks but also handles heterogeneity, outperforming defense baselines across a wide range of backdoor attack scenarios.

Edge video analytics typically rely on conventional encoding standards to transmit device visual data for server-side inference. Unfortunately, general-purpose compression solutions retain unnecessary visual data that does not contribute to accuracy, resulting in significant latency throughout Video Analytics Pipeline (VAP). While previous approaches have made partial progress, they cannot systematically eliminate VAP redundancy due to uncoordinated subsystem-level optimization. Achieving complete redundancy elimination presents a major challenge, as a lack of spatio-temporal coordination risks offsetting latency gains with computational overhead (associated with redundancy elimination).Crucioovercomes these limitations with an end-to-edge framework that integrates temporally adaptive frame filtering and coordinated video compression. It leverages redesigned asymmetric autoencoders to synchronize inter-frame temporal compression with intra-frame spatial feature extraction. Additionally,Crucioemploys a one-pass decoding mechanism for encoded critical frames and dynamically adjusts batching scales to minimize latency. Empirical results demonstrateCrucio's superiority, outperforming existing solutions (e.g., DDS, Reducto, and STAC) by over a 31% reduction in end-to-end latency at 0.9 accuracy thresholds.

Running deep neural networks (DNNs) on large-scale videos from widely distributed cameras presents two significant challenges. Firstly, video quality for analytical purposes is severely impacted by the camera deployment environment, which is termed Pixel Recession in this paper. Secondly, low-latency video streaming from the source camera to edge servers is greatly hindered by the rapid expansion of video traffic. Despite numerous efforts such as enhancing the video structure, uneven encoding, and filtering frames captured on camera, these methods have proven insufficient to address the challenges at hand. We propose Spliceosome, a novel video analytics system that effectively overcomes the pixel recession and streaming bottlenecks. In brief, Spliceosome 1) recovers from pixel recession by adaptive video knobs (i.e., brightness and contrast) tuning in ARP (anchor region proposal) granularity, and 2) lowers the transmission volume by video thinning, which uses only single-channel information for video encoding. We implemented Spliceosome using only commercial off-the-shelf hardware. Our experimental results demonstrate that Spliceosome outperforms other alternative designs by 4.71-14.47%, 40.94-58.71%, and 14.28% in detection accuracy, end-to-end delay, and efficiency of DNNs inference, respectively.

Increased videos captured by widely deployed cameras are being analyzed by computer vision-based Deep Neural Networks (DNNs) on servers rather than being streamed for humans. Unfortunately, the conventional codecs (e.g., H.26x and MPEG-x) originally designed for video streaming lack content-aware feature extraction and hinder machine-centric video analytics, making it difficult to achieve the required high accuracy with tolerable delay. Neural codecs (e.g., autoencoder) now hold impressive compression performance and have been widely advocated in video streaming. While autoencoder shows transformative potential, the application in video analytics is hampered by low accuracy in detecting small objects of high-resolution videos and the serious challenges posed by multi-video streaming. To this end, we propose AdaStreamer with adaptive neural codecs to enable real machine-centric high-accuracy multi-video analytics. We also investigate how to achieve optimal accuracy under delay constraints via careful scheduling in Compression Ratios (CRs, the ratio of the compressed size to the original data size) and bandwidth allocation, and further propose a Markov-based Adaptive Compression and Bandwidth Allocation algorithm (MACBA). We have practically developed a prototype of AdaStreamer, based on which extensive experiments verify its accuracy improvement (up to 15%) compared to state-of-the-art coding and streaming solutions.

In recent years, many crowdsourcing platforms have emerged, using the resources of recruited workers to perform diverse outsourcing tasks, where the video analytics attracts much attention due to its practical implications. For maximum profits, platforms carefully choose the workers and determine the video analytics configurations to ensure accuracy; meanwhile, workers possess the flexibility to tailor the configurations for their indivi-dual gains, which makes it hard for platforms to optimize their profits considering the platform-worker conflicts. In this paper, we design an incentive mechanism for Multi-leader game-based video Analytics upon CROwdsourcing, named MACRO, to over-come the above situation. Under that mechanism, we first formu-late the utility optimization problems for platforms and workers, respectively. We then propose a dual ascent-based method to op-timally determine the video analytics configurations for a multi-platform game, ensuring Pareto efficiency. Moreover, in the context of a multi-leader game involving platform-worker conflicts, we design an incentive function with its incentive factor update strategy and propose an ADMM-based approach for maximizing incentives that motivate workers to contribute to the platforms' profits. Rigorous proofs demonstrate the linear convergence of the MACRO to the multi-leader Stackelberg equilibrium. Trace-driven experiments show that MACRO improves the Pareto efficiency by 26.3%, outperforming other approaches.

In this paper, we investigate the competitive content placement problem in Mobile Edge Caching (MEC) systems, where Edge Data Providers (EDPs) cache appropriate contents and trade them with requesters at a suitable price. Most of the existing works ignore the complicated strategic and economic interplay between content caching, pricing, and content sharing. Therefore, we propose a joint Mean-Field Game framework for mobile edge Caching and Pricing (MFG-CP) in large-scale dynamic MEC systems, which can facilitate distributed optimal decision-making based on the mean-field game theory. Specifi-cally, we first formulate the competitive content placement issue among EDPs as a non-cooperative stochastic differential game. To significantly reduce the communication and computation complexity, we further devise a mean-field model to approximate the collective impact of all EDPs on caching, trading, and sharing, by which each EDP can quickly estimate some unknown information without considerable interactions. Then, we develop a distributed best response scheme based on iterative learning, enabling each EDP to solely customize its optimal caching strategy and pricing policy. Besides, we theoretically prove the existence of a unique MFG equilibrium. Finally, trace-driven simulations demonstrate the effectiveness of MFG-CP compared with some baselines.

Nowadays, large language models (LLMs) are published as a service and can be accessed by various applications via APIs, also known as language-model-as-a-service (LMaaS). Without knowing the generation length of requests, existing serving systems serve requests in a first-come, first-served (FCFS) manner with a fixed batch size, which leads to two problems that affect batch serving efficiency. First, the generation lengths of requests in a batch vary, and requests with short generation lengths must wait for requests with long generation lengths to finish during the batch serving procedure. Second, requests with longer generation lengths consume more memory during serving. Without knowing the generation lengths of batched requests, the batch size is always set small to avoid the out-of-memory (OOM) error, thus preventing the GPU from being fully utilized. In this paper, we find that a significant number of popular applications in the LMaaS scenario have a positive correlation between the generation length and the length of raw user input. Based on this observation, we propose Magnus, which can accurately predict the request generation length with the user input length, application-level, and user-level semantic features. Accordingly, Magnus can achieve high request throughput by batching requests of similar generation lengths together with adaptive batch sizes. Besides, Magnus can also schedule batches with the highest response ratio next (HRRN) policy to reduce request response time. Experiments conducted on our testbed show that Magnus improves request throughput by up to 234% and reduces response time by up to 89.7% compared to baselines.

Recent years have witnessed the unprecedented performance of convolutional networks in image super-resolution (SR). SR involves upscaling a single low-resolution image to meet application-specific image quality demands, making it vital for mobile devices. However, the excessive computational and memory requirements of SR tasks pose a challenge in mapping SR networks on a single resource-constrained mobile device, especially for an ultra-high target resolution. This work presents TileSR, a novel framework for efficient image SR through tile-granular parallel offloading upon multiple collaborative mobile devices. In particular, for an incoming image, TileSR first uniformly divides it into multiple tiles and selects the top-K tiles with the highest upscaling difficulty (quantified by mPV). Then, we propose a tile scheduling algorithm based on multi-agent multiarmed bandit, which attains the accurate offload reward through the exploration phase, derives the tile packing decision based on the reward estimates, and exploits this decision to schedule the selected tiles. We have implemented TileSR fully based on COTS hardware, and the experimental results demonstrate that TileSR reduces the response latency by 17.77-82.2% while improving the image quality by 2.38-10.57% compared to other alternatives.

There is an increasing demand for analyzing live surveillance video streams via large-scale camera networks, particularly for applications in public safety and smart cities. To address the conflict between resource-intensive detection models and limited capabilities of cameras, a detection-with-tracking framework has gained prominence. However, since trackers are vulnerable to occlusions and new object appearances, frequent detections are required to calibrate the results, leading to varying detection demands that depends on video content. Consequently, we propose a mechanism for content-aware analytics on collaborative cameras, denoted as VisFlow, to increase the quality of detections and achieve the latency requirement by fully utilizing camera resources. We formulate such a problem as a non-linear, integer program with a long-term perspective, aimed at maximizing detection accuracy. An online mechanism, underpinned by a queue-based algorithm and randomized rounding, is then devised to dynamically orchestrate detection workloads among cameras, thus adapting to fluctuating detection demands. Via rigorous proof, both dynamic regret regarding overall accuracy and the transmission budget are ensured in the long run. The testbed experiments on Jetson Kits demonstrate that VisFlow improves accuracy by 18.3% over the baselines.

Increased videos captured by widely deployed cameras are being analyzed by computer vision-based Deep Neural Networks (DNNs) on servers rather than being streamed for humans. Unfortunately, the conventional codecs (e.g., H.26x and MPEG-x) originally designed for video streaming lack content-aware feature extraction and hinder machine-centric video analytics, making it difficult to achieve the required high accuracy with tolerable delay. Neural codecs (e.g., autoencoder) now hold impressive compression performance and have been widely advocated in video streaming. While autoencoder shows transformative potential, the application in video analytics is hampered by low accuracy in detecting small objects of highresolution videos and the serious challenges posed by multivideo streaming. To this end, we propose AdaStreamer with adaptive neural codecs to enable real machine-centric highaccuracy multi-video analytics. We also investigate how to achieve optimal accuracy under delay constraints via careful scheduling in Compression Ratios (CRs, the ratio of the compressed size to the original data size) and bandwidth allocation, and further propose a Markov-based Adaptive Compression and Bandwidth Allocation algorithm (MACBA). We have practically developed a prototype of AdaStreamer, based on which extensive experiments verify its accuracy improvement (up to 15%) compared to stateof-the-art coding and streaming solutions.

Video Analytics Pipeline (VAP) usually relies on traditional codecs to stream video content from clients to servers. However, such analytics-agnostic codecs preserve considerable pixels not relevant to achieving high analytics accuracy, incurring a large end-to-end delay. Despite the significant efforts of pioneers, they fall short as they resisted complete redundancy elimination. Achieving such a goal is extremely challenging, and naive design without coordination can result in the benefits of redundancy elimination being counterbalanced by intolerable delays introduced. We present CRUCIO, an end-to-end coordinated spatio-temporal redundancy elimination system for edge video analytics. CRUCIO leverages reshaped asymmetric autoencoders for end-to-end frame filtering (temporally) and coordinated intra-frame (spatially), inter-frame (temporally) compression. Furthermore, CRUCIO can decode the compressed key frames all in one go and support adaptive VAP batch size for delay optimization. Extensive evaluations reveal significant end-to-end delay reductions (at least 31% under an accuracy target of 0.9) in CRUCIO compared to the state-of-the-art VAP redundancy elimination methods (e.g., DDS, Reducto, STAC, etc).

Over the last decade, the mobile crowdsourcing has become a paradigm to conduct the manual annotation and further analytics by recruited workers, with their rewards depending on the result quality. Existing dispatchers cannot precisely capture the resource-quality trade-off for video analytics, because the configurations supported by recruited workers are limited, and workers’ availability changes over time. To determine the most suitable configurations as well as workers for video analytics, we formulate a non-linear mixed program in long term, maximizing the crowdsourcing profit. Based on previous results under various configurations and workers, we design an algorithm via a series of subproblems to decide the configurations adaptively upon the prediction of workers’ feedbacks. Such prediction is based on volatile multi-armed bandit to capture workers’ availability and stochastic changes on resource uses. Furthermore, we extend the proposed algorithms to the multi-worker selection scenario where the platform needs to determine a candidate worker set instead of a single worker for video analytics. Via rigorous proof, the regret is ensured upon the Lyapunov optimization and the bandit, measuring the gap between the online decisions and the offline optimum. Extensive trace-driven experiments show that our proposed algorithm improves the profit by 37% compared with other algorithms.

Mobile Edge Computing (MEC) is a promising solution to enhance the computing capability of resource-limited networks. A fundamental problem in MEC is efficiently offloading tasks from user devices to edge servers. However, there still exists a gap to deploy in real-world environments: 1) traditional centralized approaches needs complete information of edge network, ignoring the communication costs generated by synchronization, 2) previous works do not consider concurrent computation on edge servers, which may cause dynamic changes in the environment, and 3) the scheduling algorithm should deliver individualized decisions for different users independently and with high efficiency To solve this mismatch, we studied a multi-user task offloading problem where user devices make offloading decisions independently. We consider the concurrent execution of tasks and formulate a non-divisible and delay-aware task offloading problem to jointly minimize the dropped task ratio and long-term latency. We propose a decentralized task scheduling algorithm based on DRL that makes offloading decisions without knowing the information of other user devices. We employ Double-DQN, Dueling-DQN, Prioritized Replay Memory, and Recurrent Neural Network (RNN) techniques to improve the algorithm's performance. The results of simulation experiments show that our method can significantly reduce the long-term latency and dropped task ratio compared to the baseline algorithms.

Deep convolutional neural network (NN)-based object detectors are not appropriate for straightforward inference on high-resolution videos at edge devices, as maintaining high accuracy often brings about prohibitively long latency. Although existing solutions have attempted to reduce on-device inference latency by selecting a cheaper configuration (e.g., choosing a more lightweight NN or scaling a frame to a smaller size before inference) or eliminating a background containing no object, they often ignore various high-resolution features and fail to optimize for those videos. We thus present AdaPyramid, a framework to reduce as much on-device inference latency as possible, especially for high-resolution videos, while achieving the accuracy demand approximately. We observe that the cheapest configuration to achieve the accuracy demand varies significantly across both different frames and different regions in a frame. The underlying reason is that object features (e.g., the location, size and category of objects) are more uneven in high-resolution videos, both temporally and spatially. Moreover, we observe that the object size presents a prominent hierarchical distribution in high-resolution frames. AdaPyramid thus partitions each frame hierarchically just like a pyramid and chooses a content-aware configuration for each region, which is adapted online based on the feedback. We evaluate the performance of AdaPyramid on a public dataset and our collected real-world videos. The obtained results show that under comparable accuracy to the state-of-the-art solutions, AdaPyramid can decrease inference latency by 40% on average, with up to 2.5× speed-up.

With the explosive spread of smart mobile devices, Mobile CrowdSensing (MCS) has been becoming a promising paradigm, by which a platform can coordinate a group of workers to complete large-scale data collection tasks using their mobile devices. In this paper, we investigate the incentive mechanism design in MCS systems, taking the freshness of collected data and social benefits into consideration. First, the Age of Information (AoI) metric is introduced to measure the freshness of data. Then, we model the incentive mechanism design with AoI guarantees as an incomplete information two-stage Stackelberg game with multiple constraints. Next, we consider the scenario that all participants share the public utility function parameters of the Stackelberg game. By deriving the optimal remuneration paid by the platform and the optimal data update frequency for each worker, and proving the existence of a unique Stackelberg equilibrium, we propose an AoI-guaranteed Incentive Mechanism (AIM) that enables the platform and all workers to maximize their utilities simultaneously. Furthermore, we extend AIM to a general scenario where each participant has no prior knowledge of the utility function parameters of the game. By resorting to the Deep Reinforcement Learning (DRL) technique and modeling the two-stage Stackelberg game as a Markov decision process, we propose a DRL-based Incentive Mechanism (DIM) with AoI guarantees, which makes each participant effectively seek its optimal strategy through trial and error. Meanwhile, the system can guarantee that the AoI values of all data uploaded to the platform are not larger than a given threshold. Finally, numerical experiments on real-world traces are conducted to validate the efficacy and efficiency of AIM and DIM.

The detection of objects via neural networks plays a key role in various video analytics, but consumes huge resources. Due to the limited computing capability at edges, such real-time detections should be precisely used for the objects that need the most attention. Unfortunately, as the target objects keep moving, existing systems fail to consider both the distribution of objects and object movements over regions, and existing tracking mechanisms are easily affected by background content. Therefore, we propose spatial and temporal detection with attention for analytics, to increase the quality of detections for those targets. However, the attention shift over regions, the uncertainty of detections, and the constrained edge resources essentially hamper us from efficient analytics. We propose an adaptive partition planner to divide the frame into regions to achieve spatial attention. Afterwards, we design a detection planner to orchestrate the detection model temporally for each region by an online mechanism, via a queue-based adaptation. The spatial and temporal attention are integrated to maximize the accumulative detection accuracy. Via rigorous proof, both dynamic regret regarding detection accuracy and the real-time requirement for the video analytics are ensured. The testbed experiments confirm the superiority of our approach over multiple state-of-the-art algorithms.

The usage of live streaming services has led to a substantial increase in live video traffic. However, the perceived quality of experience of users is frequently limited by variations in the upstream bandwidth of streamers. To address this issue, several adaptive bitrate (ABR) algorithms have been developed to mitigate bandwidth variations. Nevertheless, the ability of users to enjoy high-quality live streams remains limited. While neural-enhanced approaches, such as super-resolution, offer significant quality improvements, frame-oriented super-resolution leads to excessive inference delay that violates the real-time feature of live streaming. In response, we propose ViChaser, which examines block-oriented super-resolution for live streaming. ViChaser performs neural super-resolution on potential blocks of interest in the media server, corresponding to the user’s viewpoint, and uses online learning to adapt to the dynamic content of the video. Additionally, ViChaser utilizes the Lyapunov framework to efficiently allocate uplink bandwidth for original low-quality live video and high-quality labels. The experimental results demonstrate that ViChaser achieves 1.2–1.5 dB higher video quality in Peak-Signal-to-Noise-Ratio than WebRTC and increases processing speed by 11–16 fps relative to LiveNAS.

Deploying microservice instances in geo-distributed edge clouds which are located at the network edge and in proximity to end-users can provide on-site processing, thereby improving the quality of service (QoS). To accommodate the time-varying request arrival rate of each edge cloud, the deployment scheme of microservice instances is dynamically adapted, which is called microservice autoscaling. However, existing studies on microservice autoscaling at the edge either only optimize the QoS without considering the cost of deploying microservice instances or simply focus on the cost per individual timeslot, and thus always severely violate the long-term budget constraint. To solve this problem, in this article, we propose GeoScale, a novel method that aims to optimize the average request response time under the long-term cost budget constraint. GeoScale first utilizes the Lyapunov optimization framework to decompose the long-term optimization problem into a series of per-timeslot sub-problems and then applies a signomial geometric programming (SGP)-based algorithm to obtain a near-optimal solution to each NP-hard sub-problem. Through extensive trace-driven experiments, we validate the superiority of GeoScale. The experimental results show that compared with existing strategies and designed baselines, GeoScale can improve QoS by reducing the average request response time up to 87.8% while significantly mitigating the violation of the long-term cost budget constraint.

Network visualization is essential for network operators to diagnose ongoing network failures and understand the quality of the network. In-Band Network Telemetry (INT) supports network visualization by inserting P4 switch state information (e.g., queue length, hop latency, and link utilization) into the specific INT packets. In order to achieve network-wide coverage, paths of INT packets need to be delicately designed to ensure non-overlapping, high performance, and low overhead. However, existing INT path planning solutions ignore capturing the dynamic network status and fail to obtain the optimum. In this paper, we model the INT path planning based on the directed Edge Cover problem upon the dynamic network status, with the objective of minimizing the INT path latency. Although it is actually a non-linear integer program problem, by adopting delicate transformations, we design approximation algorithms with performance guarantees. We implement our system prototype INTView based on INTCollector upon real devices, i.e., Barefoot Wedge100BF and Inspur Rack. Extensive evaluation upon realistic settings shows that our proposed algorithm achieves 2x performance improvement regarding the completion time, compared with state-of-the-art schemas.

The widespread use of 5G and artificial intelligence applications has led to strong momentum in Mobile Edge Computing (MEC). With MEC, we can offload compute-intensive tasks to edge servers that are closer to the user, thereby reducing the long latency incurred by data transmission via WAN. Although many works have investigated task offloading decisions under service caching, the state of services is an equal, if not more important, research area of MEC, yet receive much less attention. In general, the arrival of tasks exhibit a distribution over time. Besides the necessary energy consumption in processing tasks offloaded to edge servers, a large amount of energy is required for maintaining services cached on servers. When more and more services become idle, they will incur a non-negligible additional energy. In this paper, we focus on an interesting but currently less studied problem in MEC, namely online service caching and state management in MEC. We propose DCSO, a bounded online algorithm that considers dynamic service caching and state management of services to minimize long-term cost in MEC systems. Meanwhile, our algorithm achieves a 2 competitive ratio in state management. Trace-driven simulations show that our algorithm reduces the overall cost efficiently while keeping low computation latency.

Many crowdsourcing platforms are emerging, leveraging the resources of recruited workers to execute various outsourcing tasks, mainly for those computing-intensive video analytics with high quality requirements. Although the profit of each platform is strongly related to the quality of analytics feedback, due to the uncertainty on diverse performance of workers and the conflicts of interest over platforms, it is non-trivial to determine the dispatch of tasks with maximum benefits. In this paper, we design a decentralized mechanism for a Crowd of Crowdsourcing platforms, denoted as Crowd2, optimizing the worker selection to maximize the social welfare of these platforms in a long-term scope, under the consideration of both proportional fairness and dynamic flexibility. Concretely, we propose a video analytics dispatch algorithm based on multi-agent bandit, for which the more accurate profit estimates are attained via the decoupling of multi-knapsack based mapping problem. Via rigorous proofs, a sub-linear regret bound for social welfare of crowdsourcing profits is achieved while both fairness and flexibility are ensured. Extensive trace-driven experiments demonstrate that Crowd2improves the social welfare by 36.8%, compared with other alternatives.

Deploying deep convolutional neural network (CNN) to perform video analytics at edge poses a substantial system challenge, as running CNN inference incurs a prohibitive cost in computational resources. Model partitioning, as a promising approach, splits CNNs and distributes them to multiple edge devices in closer proximity to each other for serial inferences, however, it causes considerable cross-edge delay for transmitting intermediate feature maps. To overcome this challenge, we present ResMap, a new edge video analytics framework that significantly improves the cross-edge transmission and flexibly partitions the CNNs. Briefly, by exploiting the sparsity of the intermediate raw or residual feature map, ResMap effectively removes the redundant transmission, thereby decreasing the cross-edge transmission delay. In addition, ResMap incorporates an Online Data-Aware Scheduler to regularly update the CNN partitioning scheme so as to adapt to the time-varying edge runtime and video content. We have implemented ResMap fully based on COTS hardware, and the experimental results show that ResMap reduces the intermediate feature map volume by 14.93-46.12% and improves the average processing time by 17.43-30.6% compared to other alternative designs.

Mobile CrowdSensing (MCS) is a mobile computing paradigm, through which a platform can coordinate a crowd of workers to accomplish large-scale data collection tasks using their mobile devices. Information freshness has attracted much focus on MCS research worldwide. In this paper, we investigate the incentive mechanism design in MCS systems that take the freshness of collected data and social benefits into concerns. First, we introduce the Age of Information (AoI) metric to measure the freshness of data. Then, we model the incentive mechanism design with AoI guarantees as a novel incomplete information two-stage Stackelberg game with multiple constraints. Next, we derive the optimal strategies of this game so as to determine the optimal reward paid by the platform and the optimal data update frequency for each worker. Moreover, we prove that these optimal strategies form a unique Stackelberg equilibrium. Based on the optimal strategies, we propose an AoI-Aware Incentive (AIAI) mechanism for the MCS system, whereby the platform and all workers can maximize their utilities simultaneously. Meanwhile, the system can ensure that the AoI values of all data uploaded to the platform are not larger than a given threshold to achieve high data freshness. Extensive simulations on real-world traces are conducted to demonstrate the significant performance of AIAI.

In-band Network Telemetry (INT) is proposed to detect networks via injecting specific probes to collect the hop-by-hop metadata within programmable switches. But there exist multiple challenges to conducting INT at Computing Power Network, such as control decisions of different INT frequencies, and the unforeseeable INT query workloads. In this study, we formulate an online non-linear time-varying integer programming problem that aims to maximize the overall quality of service through both frequency selection and INT query workload distribution. To achieve this, we propose an online learning, INTService, which utilizes a primal-dual mechanism to make fractional decisions. At last, extensive evaluations show that our proposed INTService exhibits up-lift performance 40% on average over other state-of-the-art algorithms.

Interactive mobile augmented reality (MAR) applications such as Connected Lens are becoming popular, which often rely on deep neural network (NN)-based video analytics techniques to understand the real world. However, performing computation-intensive NN inference on resource-constrained mobile devices is impractical. It is thus proposed to offload the workloads to edge servers with the help of mobile edge computing (MEC). Existing works often focus on system-wide offloading solutions, optimizing the personalized user experience for interactive applications in dynamic environments is yet rarely studied, where multiple challenges remain to be solved. First, the user has to decide the configuration for video analytics, where the inherent accuracy-cost trade-off exists. Second, it is intractable to decide the target server for offloading, since each server supports limited configurations, and a user needs to balance the experience of analytics service and the quality of interaction with others at the same time. Third, the fluctuating network information is often undisclosed to the users, and the candidate servers also vary over time. Therefore, in this paper, we propose an online user-managed server selection and configuration adaptation scheme (OSCA). Via Lyapunov optimization, we aim to maximize the long-term service experience, under the interactive quality constraint with other users. Besides, volatile multi-armed bandit (MAB) is utilized to handle the network fluctuation and the variance of the candidate servers. We conduct rigorous theoretical analysis, and the deviations of both the service experience and the interactive quality are bounded. Through extensive trace-driven experiments, we demonstrate the superior performance of OSCA.

The multi-armed bandit (MAB) models have always received lots of attention from multiple research communities due to their broad application domains. The optimal selection problem with unknown rewards in advance, such as ad recommendation in social networks, spectrum access in the cognitive radio field, etc., can be efficiently solved by using MAB models. In an MAB model, given$N$arms whose rewards are unknown in advance, the player selects exactly one arm in each round, and his goal is to maximize the cumulative rewards over a fixed horizon. Further, a more general model called combinatorial MAB (i.e., CMAB), where$K$arms can be played simultaneously in each round, is put forward. However, the existing CMAB models neglect the strategic behaviors of the$N$arms, which indicates that one arm might report false information to increase its own profits. In fact, in many applications such as user selection in crowdsensing, the arms are not the feelingless machines but the rational individuals. To this end, we combine the upper confidence bound (UCB) with auction theory to develop a new algorithm called auction-based UCB (AUCB). We divide the auction-based CMAB problem into two sub-problems: winning arm selection and payment computation problems. For AUCB, we derive an upper bound on regret and prove the truthfulness in one round, individual rationality, and computational efficiency. In addition, we consider an extended situation that some arms may be unavailable in some rounds and the arms will bid inconsistently in different rounds. We devise another algorithm called eAUCB to solve this problem. Extensive simulations are conducted to show the significant performance of the proposed algorithms.

In this paper, we investigate the incentive problem in Spatial Crowdsourcing (SC), where mobile social-aware workers have unknown qualities and can share their answers to tasks via social networks. The objectives are to recruit high-quality workers and maximize all parties’ utilities simultaneously. However, most existing works assume that the qualities of workers are known in advance or cannot take all parties’ utilities into account together, especially having not considered the impact of social networks. Thus, we propose an incentive mechanism based on the multi-armed bandit and three-stage Stackelberg game, called TACT. We first design a greedy arm-pulling scheme to recruit workers, which not only can solve the exploration-exploitation dilemma but also takes workers’ social relations into account. Based on the recruitment results, we further design the utility functions incorporating with social benefits for workers, and model the payment computation problem as a three-stage Stackelberg game among all participants. Next, we derive the optimal strategy group so that each party can maximize its own utility to form a multi-win situation. Moreover, we theoretically prove the unique existence of Stackelberg equilibrium and the worst regret bound. Finally, we conduct extensive simulations on a real trace to corroborate the performance of TACT.

With the dawn of 5G network, a new set of requirements for site spectrum monitoring, location-based services (LBS), network construction, and cellular planning are emerging, all of which are relying on fine-grained signal map. Although with significant importance, the traditional signal map construction, e.g., through full site survey, could be time-consuming and labor-intensive as the signal varies frequently over time and the accuracy requirement grows rapidly with the emergence of new applications. The state-of-the arts usually employ crowdsourcing scheme and matrix completion algorithm to solve the dilemma. However, the crowdsourcing scheme usually suffers from uneven distributed and inadequate participants, while the matrix completion methods do not take the specific signal map features into account, thus suffering from sub-optimal recovery results. To this end, in this paper, we study how to effectively reconstruct and update the signal map in the case of partially measured signal maps with smaller cost and propose a GAN-based active signal map reconstruction method (GSMAC). Our method is mainly innovative in two parts: GSMC, GAN-based signal map construction, and ACS, an active crowdsourcing scheme. Specifically, GSMC can effectively update the signal map with only a small number of observations while also fully using the incomplete historical signals to effectively update the signal map online. Meanwhile, ACS consists of a reinforce learning-based active query mechanism which quantitatively evaluates the most valuable measurement site for reconstruction, which further reduces the measurement cost to minimum. The simulation results and real implemented data driven experiments demonstrate the advantages and effectiveness of our approach in both accuracy and cost.

Conducting federated learning across distributed sites with In-Band Network Telemetry (INT) based data collection faces critical challenges, including control decisions of different frequencies, convergence of the models being trained, and resource provisioning coupled over time. To study this problem, we formulate a non-linear mixed-integer program to optimize the long-term INT overhead, resource cost, and federated learning cost. We then design polynomial-time online algorithms to solve this problem with only observable inputs on the fly, featuring laziness-aware resource adaption, online-learning-based INT flow selection and model aggregation control, as well as expectation-preserving randomized dependent rounding. We rigorously prove the parameterized-constant competitive ratio of our approach against the offline optimum, and the time-averaged constraint violation that vanishes in the long run. With extensive trace-driven evaluations, we confirm the superiority of our approach over other alternative approaches for reducing total cost and the efficacy of our trained models for solving real machine learning problems, reducing the real-time cost by 34% on average.

Deploying microservice instances on the edge device close to end users can provide on-site processing thus reducing request response time. Each microservice has multiple instances that can process requests in parallel. To achieve high processing efficiency, the number of these instances is scaled according to the workload, which is also known as autoscaling. Previous studies of microservice autoscaling in the edge computing environment lack in-depth consideration of time-varying workload, they assume that the workload of each microservice always depends on that of its upstream. However, through an analysis of Alibaba's microservice trace with hundreds of millions of records, we find that the assumption is impractical thus hurting autoscaling effectiveness. To solve this problem, we propose ProScale, a prediction-driven proactive autoscaling framework for microservices at the edge. ProScale proactively forecasts the workload for each individual microservice per timeslot. Then it utilizes an efficient online algorithm to leverage the predicting results to determine the instance number for each microservice jointly with making placement decisions. For each microservice instance deployed on the edge device, ProScale handles burst requests using a designed offloading strategy. In addition, ProScale can also balance the load for multiple instances of each microservice. Extensive trace-driven experiments show that ProScale has great scalability. It can reduce average response time by 96.7% and resource usage by 96.5% compared with existing strategies and designed baselines.

In past years, artificial intelligence related services and applications have boomed, which require high computation, high bandwidth and low latency. Edge computing is regarded as an appropriate solution for them, especially video analytics. In this paper, we study the multi-server multi-user heterogeneous video analytics offloading problem, where users select appropriate edge servers and then offload their raw video data to the servers for essential analytics. To deal with the cooperation and conflicts among users and get a stable situation where each user has no incentive to change the offloading decision unilaterally, we formulate the video analytics offloading problem as a multiplayer game. Based on the goal of minimizing the overall delay, we design the potential optimal server selection strategy and then propose a game theory-based algorithm, through which the Nash equilibrium can be reached. Furthermore, we analyze its near-optimal performance via rigorous proof. Finally, extensive trace-driven experiments show that our method improves the overall delay by 48% on average, compared with other algorithms.

Crowdsourcing enables a paradigm to conduct the manual annotation and the analytics by those recruited workers, with their rewards relevant to the quality of the results. Existing dispatchers fail to capture the resource-quality trade-off for video analytics, since the configurations supported by various workers are different, and the workers’ availability is essentially dynamic. To determine the most suitable configurations as well as workers for video analytics, we formulate a non-linear mixed program in a long-term scope, maximizing the profit for the crowdsourcing platform. Based on previous results under various configurations and workers, we design an algorithm via a series of subproblems to decide the configurations adaptively upon the prediction of the worker rewards. Such prediction is based on volatile multi-armed bandit to capture the workers’ availability and stochastic changes on resource uses. Via rigorous proof, the regret is ensured upon the Lyapunov optimization and the bandit, measuring the gap between the online decisions and the offline optimum. Extensive trace-driven experiments show that our algorithm improves the platform profit by 37%, compared with other algorithms.

Edge computing is a new computing paradigm rising gradually in recent years. Applications, such as object detection, virtual reality and intelligent cameras, often leverage Deep Neural Networks (DNN) inference technology. The traditional paradigm of DNN inference based on cloud suffers from high delay because of the limited bandwidth. From the perspective of service providers, caching DNN models on the edge brings several benefits, such as efficiency, privacy, security, etc.. The problem we concerned in this paper is how to decide the cached models and how to allocate processors of edge servers to reduce the overall system cost. To solve it, we model and study the DNN Model Caching and Processor Allocation (DMCPA) problem, which considers user-perceived delay and energy consumption with limited edge resources. We model it as an integer nonlinear programming (INLP) problem, and prove its NP-Completeness. Since it is considered as a long-term average optimization problem, we leverage the Lyapunov framework to develop a novel online algorithm DMCPA-GS-Online with Gibbs Sampling. We give the theoretical analysis to prove that our algorithm is near-optimal. In experiments, we study the performance of our algorithm and compare it with other baselines. The simulation results with the trace dataset from real world demonstrate the effectiveness and adaptiveness of our algorithm.

The growing demands for cloud computing have led to high power consumption in data centers. To save power, existing works attempt to reduce the number of active servers via scheduling or migrating VMs. Meanwhile, owing to the lightweight, highly-portable and scalable properties, containers have been widely used in data centers. However, comparing with VMs, containers show the migratability property, i.e., some containers can not be consolidated by migration. Thus, one has to take this property into consideration when making scheduling and migrating decisions. To this end, this paper studies the energy-efficient container orchestration problem in data centers. We frame container scheduling and migration as a single problem, and take the migratability of containers into account. We propose an online container orchestration algorithm, based on Lyapunov optimization and Markov approximation. It works without requiring future information and achieves a provable performance guarantee. Simulation results show that our algorithm can effectively reduce the power consumption of data centers.

Federated learning is emerging as a major learning paradigm, which enables multiple devices to train a model col-laboratively and to keep the privacy of data. However, substantial computation-intensive iterations are performed on devices before the training completion, which incurs heavy consumption of the energy. Along with the stabilization of those model parameters being trained, such on-device training iterations are redundant gradually over time. Thus, we propose to scale the update results obtained from reduced iterations as the substitute for on-device training, based on current model status and device heterogeneity. We thus formulate a time-varying integer program, to minimize cumulative energy consumption over devices, subject to a long-term constraint regarding the model convergence. We then design a polynomial-time online algorithm upon system dynamics, which essentially balances the energy consumption and the model quality being trained. Via rigorous proofs, our approach only incurs sub linear regret, compared with its optimum, and ensures related model convergence. Extensive testbed experiments for real training confirm the superiority of our approach, over multiple alternatives, under various scenarios, decreasing at least 30.2% energy consumption, while preserving the accuracy of the model.

The detection of objects via neural networks plays a key role in various video analytics, but consumes huge resources. Due to the limited on-device computing capability, such real-time detections should be precisely used for the objects that need the most attention. Unfortunately, as the target objects keep moving, existing systems fail to conduct adaptive detections over multiple regions in a video, and existing tracking mechanisms are easily affected by background contents. Therefore, we propose to design attention-aware on-device detection for analytics, to increase the quality of detections for those targets. However, the uncertainty of detections, the attention shift over regions, and the provisioning of on-device resources essentially hamper us from efficient analytics. We formulate such a scenario as a non-linear integer program in long-term scope, to maximize the detection accuracy. Afterwards, we design an online mechanism to orchestrate the detection model for each region in the video to cope with the moves of the targets, via a queue-based adaptation and the randomized rounding. Via rigorous proof, both dynamic regret regarding detection accuracy and the real-time requirement for the video analytics are ensured. The testbed experiments confirm the superiority of our approach over multiple state-of-the-art algorithms.

Mobile CrowdSensing (MCS), through which a requester can coordinate a crowd of workers to accomplish some data collection tasks, has been recognized as a promising paradigm for large-scale data acquisition in recent years. Many researches focus on the worker recruitment problem in MCS, but most of them either have the assumption that workers’ qualities are known ahead of time or cannot ensure that workers report costs honestly. In this paper, we propose an incentive mechanism based on Combinatorial Multi-Armed Bandit and reverse Auction, called CMABA, to solve the multiple unknown workers recruitment problem in MCS. Our objective is to determine a recruiting strategy to maximize the total sensing quality under a limited budget, while ensuring truthfulness and individual rationality of sensing workers. We theoretically prove that our CMABA mechanism achieves truthfulness and individual rationality, and then analyze the regret of the mechanism. Based on CMABA, we ulteriorly propose an adaptive incentive mechanism, called ACMABA, to recruit workers via the alternative worker recruitment and quality update, which can achieve a higher total sensing quality and lower regret. Additionally, we also demonstrate significant performances of the CMABA and ACMABA mechanisms through extensive simulations on real-world data traces.

Major cities worldwide have millions of cameras deployed for surveillance, business intelligence, traffic control, crime prevention, etc. Real-time analytics on video data demands intensive computation resources and high energy consumption. Traditional cloud-based video analytics relies on large centralized clusters to ingest video streams. With edge computing, we can offload compute-intensive analysis tasks to nearby servers, thus mitigating long latency incurred by data transmission via wide area networks. When offloading video frames from the front-end device to an edge server, the application configuration (i.e., frame sampling rate and frame resolution) will impact several metrics, such as energy consumption, analytics accuracy and user-perceived latency. In this paper, we study the configuration selection and bandwidth allocation for multiple video streams, which are connected to the same edge node sharing an upload link. We propose an efficient online algorithm, called JCAB, which jointly optimizes configuration adaption and bandwidth allocation to address a number of key challenges in edge-based video analytics systems, including edge capacity limitation, unknown network variation, intrusive dynamics of video contents. Our algorithm is developed based on Lyapunov optimization and Markov approximation, works online without requiring future information, and achieves a provable performance bound. We also extend the proposed algorithms to the multi-edge scenario in which each user or video stream has an additional choice about which edge server to connect. Extensive evaluation results show that the proposed solutions can effectively balance the analytics accuracy and energy consumption while keeping low system latency in a variety of settings.

In the multi-access edge computing environment, app vendors deploy their services and applications at the network edges, and edge users offload their computation tasks to edge servers. We study the user-perceived delay-aware service placement and user-allocation problem in edge environment. We model the MEC-enabled network, where the user-perceived delay consists of computing delay and transmission delay. The total cost in the offloading system is defined as the sum of service placement, edge server usage and energy consumption cost, and we need to minimize the total cost by determining the overall service-placing decision and user-allocation decision, while guaranteeing that the user-perceived delay requirement of each user is fulfilled. Our considered problem is formulated as a Mixed Integer Linear Programming problem, and we prove its NP-hardness. Due to the intractability of the considered problem, we propose a LOCal-search based algorithm for USer-perceived delay-aware service placement and user-allocation in edge environment, named LOCUS, which starts with a feasible solution and then repeatedly reduces the total cost by performing local-search steps. After that, we analyze the time complexity of LOCUS and prove that it achieves provable guaranteed performance. Finally, we compare LOCUS with other existing methods and show its good performance through experiments.

Efficiently analyzing geo-distributed datasets is emerging as a major demand in a cloud-edge system. Since the datasets are often generated in closer proximity to end users, traditional works mainly focus on offloading proper tasks from those hotspot edges to the datacenter to decrease the overall completion time of submitted jobs in a one-shot manner. However, optimizing the completion time of current job alone is insufficient in a long-term scope since some datasets would be used multiple times. Instead, optimizing the data distribution is much more efficient and could directly benefit forthcoming jobs, although it may postpone the execution of current one. Unfortunately, due to the throwaway feature of data fetcher, existing data analytics systems fail to re-distribute corresponding data out of hotspot edges after the execution of data analytics. In order to minimize the overall completion time for a sequence of jobs as well as to guarantee the performance of current one, we propose to re-distribute the data along with task offloading, and formulate corresponding ε-bounded data-driven task scheduling problem over wide area network under the consideration of edge heterogeneity. We design an online schemarunData, which offloads proper tasks and related data via piggybacking to the datacenter based on delicately calculated probabilities. Through rigorous theoretical analysis,runData is proved concentrated on its optimum with high probability. We implementrunData based on Spark and HDFS. Both testbed results and trace-driven simulations show that run Data re-distributes proper data via piggybacking and achieves up to 37 percent reduction on average response time compared with state-of-the-art schemas.

Mobile Edge Computing (MEC) has become an attractive solution to enhance the computing and storage capacity of mobile devices by leveraging available resources on edge nodes. In MEC, the arrivals of tasks are highly dynamic and are hard to predict precisely. It is of great importance yet very challenging to assign the tasks to edge nodes with guaranteed system performance. In this article, we aim to optimize the revenue earned by each edge node by optimally offloading tasks to the edge nodes. We formulate the revenue-driven online task offloading (ROTO) problem, which is proved to be NP-hard. We first relax ROTO to a linear fractional programming problem, for which we propose the Level Balanced Allocation (LBA) algorithm. We then show the performance guarantee of LBA through rigorous theoretical analysis, and present the LB-Rounding algorithm for ROTO using the primal-dual technique. The algorithm achieves an approximation ratio of$2(1+\xi)\ln (d+1)$with a considerable probability, where$d$is the maximum number of process slots of an edge node and$\xi$is a small constant. The performance of the proposed algorithm is validated through both trace-driven simulations and testbed experiments. Results show that our proposed scheme is more efficient compared to baseline algorithms.

To exploit the vast amount of distributed data across edge devices, Federated Learning (FL) has been proposed to learn a shared model by performing distributed training locally on participating devices and aggregating the local models into a global one. The existing FL algorithms suffer from accuracy loss due to that data samples across all devices are usually not independent and identically distributed (non-i.i.d.). Besides, devices might lose connection during the training process in wireless edge computing. Thus, we advocate one-shot Neural Architecture Search technique as a basis to propose a solution which can deal with non-i.i.d. problem and is robust to the intermittent connection issue. We adopt a large network as the global model which includes all the candidate network architectures. The non-i.i.d. problem is alleviated by two steps: (1) identify and train the candidate networks which are potentially high performance and trained with less bias using a heuristic sampling scheme; (2) search for the final model with the highest accuracy rate from the candidate networks. Experimental results show that the model trained by our proposed method is robust to non-i.i.d. problem and can achieve 84% reduced communication overhead compared with the baselines.

With the rapid development of edge computing, edge clusters need to deal with a tremendous amount of tasks, making some edge clusters overloaded, which further translates into task completion lag. Previous works usually copy the tasks from overloaded edges to idle edges so as to reduce the task queuing and computing delay. However, the completion delay of tasks copied to different edges cannot be predicted before the replication decision is made, which affects the overall task replication performance. In this paper, we propose an online task replication algorithm based on the predictions derived from multi-armed bandit. Via rigorous proof, the regret is ensured to be sub-linear upon the bandit, measuring the gap between the online decisions and the offline optimum. Extensive simulations are conducted to confirm the superiority of the proposed algorithm over state-of-the-art replication strategies.

Operating federated learning optimally over distributed cloud-edge networks is a non-trivial task, which requires to manage data transference from user devices to edges, resource provisioning at edges, and federated learning between edges and the cloud. We formulate a non-linear mixed integer program, minimizing the long-term cumulative cost of such a federated learning system while guaranteeing the desired convergence of the machine learning models being trained. We then design a set of novel polynomial-time online algorithms to make adaptive decisions by solving continuous solutions and converting them to integers to control the system on the fly, based only on the predicted inputs about the dynamic and uncertain cloud-edge environments via online learning. We rigorously prove the competitive ratio, capturing the multiplicative gap between our approach using predicted inputs and the offline optimum using actual inputs. Extensive evaluations with real-world training datasets and system parameters confirm the empirical superiority of our approach over multiple state-of-the-art algorithms.

The multi-armed bandit (MAB) model has been deeply studied to solve many online learning problems, such as rate allocation in communication networks, Ad recommendation in social networks, etc. In an MAB model, given N arms whose rewards are unknown in advance, the player selects exactly one arm in each round, and his goal is to maximize the cumulative rewards over a fixed horizon. In this paper, we study the budget-constrained auction-based combinatorial multi-armed bandit mechanism with strategic arms, where the player can select K (<; N) arms in a round and pulling each arm has a unique cost. In addition, each arm might strategically report its cost in the auction. To this end, we combine the upper confidence bound (UCB) with auction to define the UCB-based rewards and then devise an auction-based UCB algorithm (called AUCB). In each round, AUCB selects the top K arms according to the ratios of UCB-based rewards to bids and further determines the critical payment for each arm. For AUCB, we derive an upper bound on regret and prove the truthfulness, individual rationality, and computational efficiency. Extensive simulations show that the rewards achieved by AUCB are at least 12.49% higher than those of state-of-the-art algorithms.

Real-time on-device object detection for video analytics fails to meet the accuracy requirement due to limited resources of mobile devices while offloading object detection inference to edges is time-consuming due to the transference of video data over edge networks. Based on the system with both on-device object tracking and edge-assisted analysis, we formulate a non-linear time-coupled program over time, maximizing the overall accuracy of object detection by deciding the frequency of edge-assisted inference, under the consideration of both dynamic edge networks and the constrained detection latency. We then design a learning-based online algorithm to adjust the threshold for triggering edge-assisted inference on the fly in terms of the object tracking results, which essentially controls the deviation of on-device tracking between two consecutive frames in the video, by only taking previously observable inputs. We rigorously prove that our approach only incurs sub-linear dynamic regret for the optimality objective. At last, we implement our proposed online schema, and extensive testbed results with real-world traces confirm the empirical superiority over alternative algorithms, in terms of up to 36% improvement on detection accuracy with ensured detection latency.

Performing federated learning continuously in edge networks while training data are dynamically and unpredictably streamed to the devices faces critical challenges, including the global model convergence, the long-term resource budget, and the uncertain stochastic network and execution environment. We formulate an integer program to capture all these challenges, which minimizes the cumulative total latency of stream learning on device and federated learning between devices and the edge server. We then decouple the problem, design an online learning algorithm for controlling the number of local model updates via a convex-concave reformulation and rectified gradient-descent steps, and design a bandit learning algorithm for selecting the edge server for global model aggregations by incorporating the budget information to strike the exploit-explore balance. We rigorously prove the sub-linear regret regarding the optimization objective and the sub-linear constraint violation regarding the maximal on-device load, while guaranteeing the convergence of the global model trained. Extensive evaluations with real-world training data and input traces confirm the empirical superiority of our approach over multiple state-of-the-art algorithms.

Distributed Interactive Applications (DIAs) such as virtual reality and multiplayer online game usually require fast processing of tremendous data and timely exchange of delay-sensitive action data and metadata. This makes traditional mobile-based or cloud-based solutions no longer effective. Thanks to edge computing, DIA Service Providers (DSPs) can rent resources from Edge Infrastructure Providers (EIPs) to place service entities that store user states and run computation-intensive tasks. One fundamental problem for a DSP is to decide where to place service entities to achieve low-delay pairwise interactions between DIA users, under the constraint that the total placement cost is no more than a specified budget threshold. In this article, we formally model the service entity placement problem and prove that it is NP-complete by a polynomial reduction from the set cover problem. We present GPA, an efficient algorithm for service entity placement, and theoretically analyze its performance. We evaluated GPA with both real-world data trace-driven simulations, and observed that GPA performs close to the optimal algorithm and generally outperforms the baseline algorithm. We also output a curve showing the trade-off between the weighted average interaction delay and the budget threshold, so that a DSP can choose the right balance.

Mobile crowdsensing is a new paradigm by which a platform can recruit mobile workers to perform some sensing tasks by using their smart mobile devices. In this paper, we focus on a privacy-preserving unknown worker recruitment issue. The platform needs to recruit some workers without knowing the qualities of them completing tasks. Meanwhile, these quality information also needs to be protected from disclosure. To tackle these challenges, we model the unknown worker recruitment as a Differentially Private Multi-Armed Bandit (DP-MAB) game by seeing each worker as an arm of DP-MAB and the task completion quality contributed by each worker as the reward of pulling arm. Then, recruiting workers is equivalent to designing a bandit policy of pulling DP-MAB arms. Under this model, we propose a Differentially Private ϵ-First-based arm-pulling (DPF) algorithm and a Differentially Private UCB-based arm-pulling (DPU) algorithm, which can achieve the nearly optimal expected accumulative rewards under a given budget. We also analyze the regrets of the DPF and DPU algorithms and prove that both of them are δ-differentially private on the task completion qualities (δ > 0δ). Finally, we conduct extensive simulations to verify the significant performances of DPF and DPU based on both the real-trace and synthetic datasets.

Instead of relying on remote clouds, today's Augmented Reality (AR) applications usually send videos to nearby edge servers for analysis (such as objection detection) so as to optimize the user's quality of experience (QoE), which is often determined by not only detection latency but also detection accuracy, playback fluency, etc. Therefore, many studies have been conducted to help adaptively choose best video configuration, e.g., resolution and frame per second (fps), based on network bandwidth to further improve QoE. However, we notice that the video content itself has significant impacts on the configuration selection, e.g., the videos with high-speed objects must be encoded with a high fps to meet the user's fluency requirement. In this article, we aim to adaptively select configurations that match the time-varying network condition as well as the video content. We design Cuttlefish, a system that generates video configuration decisions using reinforcement learning (RL). Cuttlefish trains a neural network model that picks a configuration for the next encoding slot based on observations collected by AR devices. Cuttlefish does not rely on any pre-programmed models or specific assumptions on the environments. Instead, it learns to make configuration decisions solely through observations of the resulting performance of historical decisions. Cuttlefish automatically learns the adaptive configuration policy for diverse AR video streams and obtains a gratifying QoE. We compared Cuttlefish to several state-of-the-art bandwidth-based and velocity-based methods using trace-driven and real world experiments. The results show that Cuttlefish achieves a 18.4-25.8 percent higher QoE than the others.

The booming of Convolutional Neural Networks (CNNs) has empowered lots of computer-vision applications. Due to its stringent requirement for computing resources, substantial research has been conducted on how to optimize its deployment and execution on resource-constrained devices. However, previous works have several weaknesses, including limited support for various CNN structures, fixed scheduling strategies, overlapped computations, high synchronization overheads, etc. In this article, we present DeepSlicing, a collaborative and adaptive inference system that adapts to various CNNs and supports customized flexible fine-grained scheduling. As a built-in functionality, DeepSlicing has supported typical CNNs including GoogLeNet, ResNet, etc. By partitioning both model and data, we also design an efficient scheduler, Proportional Synchronized Scheduler (PSS), which achieves the trade-off between computation and synchronization. Based on PyTorch, we have implemented DeepSlicing on the testbed with real-world edge settings that consists of 8 heterogeneous Raspberry Pi's. The results indicate that DeepSlicing with PSS outperforms the existing systems dramatically, e.g., the inference latency and memory footprint are reduced up to 5.79× and 14.72×, respectively.

Crowdsourcing data trading is a novel paradigm in which the crowdsourcing technology is adopted to collect big data for trading. At present, existing crowdsourcing data trading systems usually depend on a trusted broker and haven't considered the truthfulness and the quality of data (QoD) simultaneously. Besides, copyright protection is the another issue that has not been properly addressed. To tackle these problems, we propose a Copyright-Preserving crowdsourcing data trading framework based on Blockchain, named CPchain, which mainly includes a smart contract. We design an auction algorithm based on semantic similarity to guarantee the truthfulness and individual rationality while ensuring QoD. Moreover, we combine digital fingerprint technology with blockchain to protect data copyright without a third-party certification authority. Furthermore, we develop a simple prototype of our proposed trading framework on the Ethereum test network. We have carried out a lot of experiments to demonstrate the significant performances of our framework.

Federated learning achieves the privacy-preserving training of models on mobile devices by iteratively aggregating model updates instead of raw training data to the server. Since excessive training iterations and model transferences incur heavy usage of computation and communication resources, selecting appropriate devices and excluding unnecessary model updates can help save the resource usage. We formulate an online time-varying non-linear integer program to minimize the cumulative resource usage over time while achieving the desired long-term convergence of the model being trained. We design an online learning algorithm to make fractional control decisions based on both previous system dynamics and previous training results, and also design an online randomized rounding algorithm to convert the fractional decisions into integers without violating any constraints. We rigorously prove that our online approach only incurs sub-linear dynamic regret for the optimality loss and sub-linear dynamic fit for the long-term convergence violation. We conduct extensive trace-driven evaluations and confirm the empirical superiority of our approach over alternative algorithms in terms of up to 27% reduction on the resource usage while sacrificing only 4% reduction on accuracy.

In this paper, we consider a fundamental problem: given one mobile charger that can charge multiple sensor nodes simultaneously, how we can schedule it to charge a given WSN to maximize the energy usage effectiveness (EUE)? We propose a novel charging paradigm-Overlapped Mobile Charging (OMC)- the first of its kind to the best of our knowledge. Firstly, OMC clusters sensor nodes into multiple non-overlapped sets using k-means evaluated by the Davies-Bouldin Index, such that the sensor nodes in each set have similar recharging cycles. Secondly, for each set of sensor nodes, OMC further divides them into multiple overlapped groups, and charges each group at different locations for different time durations to make sure that each overlapped sensor node just receives its required energy from multiple charging locations.

With the development of deep learning, artificial intelligence applications and services have boomed in the recent years, including recommendation systems, personal assistant and video analytics. Similar to other services in the edge computing environment, artificial intelligence computing tasks are pushed to the network edge. In this paper, we consider the multi-user edge-assisted video analytics task offloading (MEVAO) problem, where users have video analytics tasks with various accuracy requirements. All users independently choose their accuracy decisions, satisfying the accuracy requirement, and offload the video data to the edge server. With the utility function designed based on the features of video analytics, we model MEVAO as a game theory problem and achieve the Nash equilibrium. For the flexibility of making accuracy decisions under different circumstances, a deep reinforcement learning approach is applied to our problem. Our proposed design has much better performance compared with some other approaches in the extensive simulations.

Federated Learning (FL) is a newly-emerging distributed ML model, where a server can coordinate multiple workers to cooperatively train a learning model by using their private datasets, while ensuring these datasets not to be revealed to others. In this paper, we focus on the incentive mechanism design for FL systems. Taking the incentives into consideration, we first design two utility functions for the server and workers, respectively. Then, we model the corresponding utility optimization problem as a two-stage Stackelberg game by seeing the server as a leader and the workers as some followers. Next, we derive an optimal Equilibrium solution for the both stages of the whole game. Based on this solution, we design an incentive mechanism that can ensure the server to achieve the optimal utility, while stimulating workers to do their best to train the ML model. Finally, we conduct extensive simulations to demonstrate the significant performance of the proposed mechanism.

Real-time analytics on video data demands intensive computation resources and high energy consumption. Traditional cloud-based video analytics relies on large centralized clusters to ingest video streams. With edge computing, we can offload compute-intensive analysis tasks to the nearby server, thus mitigating long latency incurred by data transmission via wide area networks. When offloading frames from the front-end device to the edge server, the application configuration (frame sampling rate and frame resolution) will impact several metrics, such as energy consumption, analytics accuracy and user-perceived latency. In this paper, we study the configuration adaption and bandwidth allocation for multiple video streams, which are connected to the same edge node sharing an upload link. We propose an efficient online algorithm, called JCAB, which jointly optimizes configuration adaption and bandwidth allocation to address a number of key challenges in edge-based video analytics systems, including edge capacity limitation, unknown network variation, intrusive dynamics of video contents. Our algorithm is developed based on Lyapunov optimization and Markov approximation, works online without requiring future information, and achieves a provable performance bound. Simulation results show that JCAB can effectively balance the analytics accuracy and energy consumption while keeping low system latency.

Edge service entity placement is a fundamental issue in mobile edge computing, which tries to place service entities on edge servers to achieve better economic benefits and quality of service for users. Most existing studies towards this issue usually deploy application services separately; however, we observe that many application services can be broken down into smaller service components/entities, which may enable us to share these smaller entities between application services. Therefore, in this paper, we propose the concept of service entity chain, which is a chain of ordered service entities that represent an application service. We study the problem of placing service entities in the form of chains on edge servers within a given cost budget, so as to minimize the total latency experienced by users. We provide a formal problem formulation and design an efficient algorithm for it. Extensive simulations are conducted to demonstrate the advantages of the proposed algorithm compared with two state-of-the-art algorithms.

Provisioning machine learning inference as a service at the mobile network edge for distributed users in an online setting faces multiple challenges, including the accuracy-resource trade-off for model selection, the time-coupled decision for model distribution, and the unpredictable user inference workload. To overcome such challenges, we firstly model an online time-varying non-linear integer program of maximizing the overall service's inference accuracy through dynamic model instance selection, delivery and workload distribution. Afterwards, we design an online learning algorithm to make fractional control decisions, which alternates between minimizing an outer problem and maximizing an inner problem of an equivalent convex-concave formulation by only taking previously observable inputs. We further design a randomized rounding algorithm to convert the fractional decisions into integers. We rigorously prove that our approach only incurs sub-linear dynamic regret for the optimality loss and sub-linear dynamic fit for the long-term constraints violation. Finally, we conduct extensive evaluations with real- world data and confirm the empirical superiority of our approach over state-of-the-art algorithms in terms of up to 30% reduction on accuracy loss and 34% reduction on constraints violation.

Along with the generation of Internet of Things (IoT), the values of tremendous volumes of sensing data will be slowly unlocked. Thus, crowd-sensed data trading as a new business paradigm has recently attracted increasing attention. A typical data trading system contains a platform, data consumers, and crowd workers. The platform recruits crowd workers to collect data and then sells the data to consumers. In this article, we design a differentially private crowd-sensed data trading mechanism, called DPDT, to preserve the identity privacy of consumers and the task privacy against crowd workers during the data collection process, simultaneously. DPDT consists of a differentially private auction-based data pricing algorithm and a differentially private data collection algorithm. The data pricing algorithm achieves a good approximation to the maximum revenue. Meanwhile, it guarantees (e2- 1)ϵ-truthfulness and 2ϵ-differential privacy, where ϵ > 0 is a small constant. The data collection algorithm is able to effectively protect the data collection task privacy against crowd workers. We prove that this data collection algorithm achieves δ-approximate ϵ-differential privacy, where δ <; 1/e is a small constant, and meanwhile guarantees a tight bound of the expected approximation ratio. At last, extensive simulations are conducted to verify the significant performance of DPDT.

Mobile Augmented Reality (MAR) applications usually contain computation-intensive tasks which far outstrip the capability of mobile devices. One way to overcome this is offloading computation-intensive MAR tasks to remote clouds. However, the wide area network delay is hard to reduce. Thanks to edge computing, we can offload MAR tasks to nearby servers. Prior studies focus on either single-task MAR applications offloading or dependent tasks offloading for a single user. In this article, we study the offloading decision of MAR applications from multiple users, each of which is comprised of a chain of dependent tasks, over a generic cloud-edge system consisting of a group of heterogeneous edge servers and remote clouds. We formulate the Multi-user Multi-task MAR Application Scheduling (M3AS) problem, which is NP-hard. We present Mutas, an efficient scheduling algorithm that jointly optimizes server assignment and resource management. We also consider the online version of M3AS and present OnMutas. Extensive evaluations demonstrate that both Mutas and OnMutas can significantly reduce the service delays of MAR applications when compared to three other heuristics.

Mobile crowdsensing is a new paradigm in which a requester can recruit a group of mobile users via a platform and coordinate them to perform some sensing tasks by using their smartphones. In mobile crowdsensing, each user might perform multiple tasks with different sensing qualities. Meanwhile, the users participating in the crowdsensing will ask for sufficient rewards to compensate for their expenditures. Hence, an important problem is how to recruit the users with minimum cost while achieving a satisfactory sensing quality for each task. Furthermore, in order to ease users' worries about privacy disclosures, the user recruitment process needs to protect each user's sensing quality and recruitment cost information from being revealed to other users or to the platform. In this paper, we propose two secure user recruitment problems for the cases where the recruitment costs of users are homogeneous and heterogeneous. After proving the NP-hardness of the problems, we design two secure user recruitment protocols by using secret sharing scheme. Both of the proposed protocols adopt greedy strategies, which can recruit nearly optimal users while ensuring that the total sensing quality of each task is no less than a given threshold. The difference lies in that the two greedy strategies are based on two unique utility functions. We analyze the approximation ratios of the two protocols and prove the security under the semi-honest model. Finally, we demonstrate the significant performance of the proposed protocols through extensive simulations and executions on real smartphones.

Virtualization techniques help edge environments separate the role of the traditional edge providers into two: edge infrastructure providers (EIPs), who manage the physical edge infrastructure, and edge service providers (ESPs), who aggregate resources (especially, compute resources) from multiple EIPs to place service entities and offer value-added services to end users (EUs). In such an environment, end users submit their data analysis jobs to ESPs; ESPs process the data analysis jobs using their service entities. One fundamental and critical problem for an ESP is to decide how much compute resources to rent from each edge server under the constraint that the total amount of rental resources is no more than a specified budget threshold, so that the average makespan of the data analysis jobs submitted to it is minimized. This Edge Resource Allocation (ERA) problem is proven to be NP-complete by reducing the set cover problem to a special case of it. To design an approximation algorithm for ERA, we perform two transformations on ERA: first, we transform ERA into mERA by replacing minimization with maximization; second, we transform mERA into dmERA by limiting the possible amounts of rental resources to a finite set of values. We find that dmERA has several tractable properties that allow us to design Hermes, a provably efficient algorithm that approximates the optimal allocation. We demonstrate that the gap between Hermes and the optimum in simulations and Android-based testbed experiments are no larger than 4.78% and 12.43%, respectively. Hermes can also output a curve showing the trade-off between the average makespan and the budget threshold, so that an ESP can choose the right balance.

Computation offloading makes sense to the interaction between users and compute-intensive applications. Current researches focused on deciding locally or remotely executing an application, but ignored the specific offloading proportion of application. A full offloading cannot make the best use of client and server resources. In this paper, we propose an innovative reinforcement learning (RL) method to solve the proportional computation problem. We consider a common offloading scenario with time-variant bandwidth and heterogeneous devices, and the device generates applications constantly. For each application, the client has to choose locally or remotely executing this application, and determines the proportion to be offloaded. We formalize the problem as a long-term optimization problem, and then propose a RL-based algorithm to solve it. The basic idea is to estimate the benefit of posible decisions, of wihch the decision with the maximum benefit is selected. Instead of adopting the original Deep Q Network (DQN), we propose Advanced DQN (ADQN) by adding Priority Buffer Mechanism and Expert Buffer Mechanism, which improves the utilization of samples and overcomes the cold start problem, respectively. The experimental results show ADQN's high feasibility and efficiency compared with several traditional policies, such as None Offloading Policy, Random Offloading Policy, Link Capacity Optimal Policy, and Computing Capability Optimal Policy. At last, we analyse the effect of expert buffer size and learning rate on ADQN's performance.

Signal map is of great importance, especially in the dawn of 5G network, for site spectrum monitoring, location-based services (LBS), network construction, and cellular planning. Despite its significance, the traditional signal map construction, e.g., through full site survey, could be time-consuming and labor-intensive as the signal varies frequently over time and the accuracy requirement grows rapidly with the emergence of new applications. Even with crowdsourcing scheme, the participants tend to be unevenly distributed in space while the encouragement budgets for the participants could be far from enough to collect adequate high-quality measurements. Therefore, the signal map constructed by crowdsourcing is often sparse and incomplete. To this end, in this paper, we study how to effectively reconstruct and update the signal map in the case of partially measured signal maps with minimum cost and propose an auto-encoder-based active signal map reconstruction method (AER). Our method is mainly innovative in three parts. Firstly, AER can effectively update the signal map with only a small number of observations while also fully using the incomplete historical signals to effectively update the signal map online. Secondly, AER consists of an active query mechanism which quantitatively evaluates the most valuable measurement site for reconstruction, which further reduces the measurement cost to a large extent. Thirdly, to cope with the measurement dynamics, we give a new signal map model describing not only the signal strength but also the signal dynamics, based on which an advanced AER algorithm is proposed. The simulation results demonstrate the advantages and effectiveness of our approach in both accuracy and cost.

Popular data analytics systems including Apache Hadoop, Dryad, and Apache Spark abstract jobs as directed acyclic graphs (DAGs). Speeding up completions for DAG jobs matter in practice in order to support real-time decisions. State-of-the-art works propose clairvoyant schedulers to optimize these goals, however, they assume complete job information as a prior knowledge which includes the precise DAG structure, and fine-grained resource requirement and duration time of each task. This assumption limits their applicability. In this paper, to be more practical, we relax the complete prior knowledge assumption and rely solely on partial prior information, based on which, we design a semi-clairvoyant task scheduler Cobra operating within each job. When managing resources for a job, Cobra adaptively adjusts its resource desires in a multiplicative-increase multiplicative-decrease manner on the basis of the its current resource utilization and the presence of current waiting tasks. When assigning tasks to run on the allocated resources, Cobra strives to satisfy task locality preference by tolerating each task waiting for some time that is bounded by a parameterized threshold. Even with the partial prior job information, when a set of jobs in which each employing Cobra as its task scheduler, run on a cluster that employs the fair job scheduler, we theoretically prove the produced makespan and average job response time are O(1)-competitive in different settings. We implement our design in Spark on YARN system, and use experiments from both real deployments and simulations on Google's trace to verify the performance promotion and sensitivity of Cobra.

In this paper, we focus on the use of linear sensor networks (LSNs) to monitor underwater pipelines. We propose the use of autonomous underwater vehicles (AUVs) to move along pipeline segments and collect data from the sensor nodes (SNs). Each AUV then delivers the collected data to the surface sink at the end of the corresponding LSN segment. In turn, the surface sink transmits the collected data to the network control center using any of the communication technologies that are available in the area such as WiMAX, cellular, and satellite. The use of AUVs for data collection offers considerable advantages including flexibility in SN placement, considerable energy savings and reduced interference, hidden terminal problems, and collisions. We also provide, different AUV movement strategies and analyze the effect of various network design parameters on network performance metrics such as packet delivery ratio and end-to-end delay.

Wireless energy transfer has been widely studied in recent decades, with existing works mainly focused on maximizing network lifetime, optimizing charging efficiency, and optimizing charging quality. All these works use a charging model with the linear superposition, which may not be the most accurate. We apply a nonlinear superposition model, and we consider the Fast Charging Scheduling problem (FCS): Given multiple chargers and a group of sensors, how can the chargers be optimally scheduled over the time dimension so that the total charging time is minimized and each sensor has at least energy E ? We prove that FCS is NP-complete and propose a 2-approximation algorithm to solve it in one-dimensional (1D) line. In a 2D plane, we first consider a special case of FCS, where the initial phases of all chargers are the same, and propose an algorithm to solve it, which has a bound. Then we propose an algorithm to solve FCS in a general 2D plane. Unlike other algorithms, our algorithm does not need to calculate the combined energy of every possible combination of chargers in advance, which greatly reduces the complexity. Extensive simulations demonstrate that the performance of our algorithm performs almost as good as the optimal algorithm.

Edge computing is one of the emerging technologies aiming to enable timely computation at the network edge. With virtualization technologies, the role of the traditional edge providers is separated into two: edge infrastructure providers (EIPs), who manage the physical edge infrastructure, and edge service providers (ESPs), who purchase slices of physical resources (e.g., CPU, bandwidth, memory space, disk storage) from EIPs and then cache service entities to offer their own value-added services to end users. When an ESP caches a service entity in an edge server, the ESP has to pay some fees (i.e, the cache cost) to the EIP that owns the edge server. One of the fundamental problems in edge virtualization is the so-called service entity caching problem, i.e., where to place service entities for an ESP to minimize the cache cost. In this paper, we study the service entity caching problem from the utility perspective. We use `utility' to denote the positive impact on a client from caching a service entity in an edge server, and the exact meaning of utility can vary depending on specific scenarios. We formulate the Utility-based Service Entity Caching (UtilitySEC) problem, which can be generalized to many existing problems by modifying the `utility'. We prove that the UtilitySEC problem is NP-complete and design an approximation algorithm for it. Extensive simulations are conducted to evaluate the performance of the proposed framework.

Edge computing is gaining popularity these years, more service providers are shifting their services from clouds to the edge for better QoS provision. Recent studies in NFV also tend to deploy Network Function Virtualization (NFV) services in the edge network. However, the NFV deployment in the edge network is a challenging problem and differs from the similar problem in data centers. We mainly focus on a new NFV Chain Placement (NCP) problem in the paper. It is well known that the edge of the network is dynamic, and edge computing aims to utilize the physical edge resources efficiently and quickly. We first prove that the NCP problem is NP-complete. Then we propose a novel metric that can better measure the balance condition of the physical resources. We also analyze its advantages. Finally, we design an efficient algorithm, MINI, based on this metric. We evaluate MINI using extensive simulations. The results show that MINI has great advantages over a genetic algorithm (GA) in terms of physical resource utilization, acceptance rate, and running time.

In data center networks (DCN), large scale flows produced by parallel computing frameworks form many coflows semantically. Most inter-coflow schedulers only focus on the remaining data of coflows and attempt to mimic Shortest Job First (SJF). However, a coflow may consist of multiple stages. In this paper, we consider the Multi-stage Inter-Coflow Scheduling problem and try to give an efficient online scheduling scheme. We first explore a short-sighted algorithm with the greedy strategy. This gives us an insight into utilizing the network resources. Based on that, we propose a far-sighted heuristic, which schedules sub-coflows to occupy network bandwidth in turn. Through simulations in various network environments, we show that, compared to a state-of-the-art scheduler - Varys, a multi-stage aware scheduler can reduce the coflow completion time by up to \pmb4.81× even though it is short-sighted. Moreover, the far-sighted scheduler can improve the performance by nearly \pmb7.95 × reduction.

Many organizations and companies have deployed not only datacenters but also large number of geo-distributed heterogeneous edges to provide fast data analytics services. Since large volume of data transmission across WAN can be costly, existing works mainly focus on pre-processing data in-place to avoid transmission. However, the heterogeneity of edges on either local computing capacity or network bandwidth limits the efficient use on scarce resource, which may result in long task completion time. To cope with dynamic demands on scarce resource, we take the heterogeneity of both computing capacity and network bandwidth of geo-distributed edges into consideration when assigning data analytical tasks and their associated data between the central datacenter and edges such that the overall latency can be reduced. We formulate the geo-distributed data-task joint scheduling problem (GJS), show its NP-hardness, and propose a near-optimal randomized scheduling algorithm (ran-GJS). ran-GJS can be proved concentrated around its optimum value with high probability, i.e., 1--O(e--t2) where t is the concentration bound by using Martingale Analysis. The experimental results obtained form both extensive simulations and Yarn-based prototype show that ran-GJS significantly speeds up the geo-distributed analytics with a gain on average completion time of at least 28% over state-of-the-art baseline algorithms.

Typical data analytics systems abstract jobs as directed acyclic graphs (DAGs). It is crucial to maximize throughput and speedup completions for DAG jobs in practice. Existing works propose clairvoyant schedulers optimizing these goals, however, they assume complete job information as a prior knowledge which limits their applicability. Instead, we remove the complete prior knowledge assumption and rely solely on a partial prior information, which is more practical. And we design a semi-clairvoyant task scheduler Cobra working within each job. Cobra adaptively adjusts its resource desires in a multiplicative-increase multiplicative-decrease (MIMD) manner according to nearly past resource utilizations and the current waiting tasks. On the other hand, Cobra seeks to satisfy task locality preferences by allowing each task to wait for some time that is bounded by a parameterized threshold. Surprisingly, even with the partial prior job information, we theoretically prove, Cobra, when working with the widely used fair job scheduler, is O(1)-competitive with respect to both makespan and average job response time. We experimentally validate that the performance promotion of Cobra in both real system deployment and trace-driven simulations.

Electric vehicle (EV) is a promising technological tool for diminishing environmental impact caused by gasoline-consumed transportation. Due to the limited battery capacity, EVs need to be charged frequently in a static charging station and thus waste large amounts of time being out of service. Research previously conducted in this topic have proposed solutions for deployment of charging lanes that can charge in-motion EVs. However, they cannot guarantee that every EV can be operational in their respective entire route. Meanwhile, we observe that EVs have repetitive motions and may cyclically encounter with each other which no prior research having been investigated. In addition, the development on the circuit design of energy transmit antennas can render EVs to be able to bi-directionally, highly efficiently transfer energy between themselves. These two observations enable us to distribute energy among EVs in a collaborative and interactive manner. We consider the cases of both loss-less and lossy energy transfer between EVs. In both cases, we formulate the problem of minimizing the time needed (or energy transferred) to reach a given energy distribution into a series of linear programming problems. When compared with a state-of-the-art algorithm, extensive simulation results show that the proposed algorithms can reduce the balancing time and energy loss by up to 70.60% and 36.59%, respectively.

Nowadays, breakthroughs in wireless power transfer make it possible to transfer energy over a long distance. Existing works mainly focused on maximizing network lifetime, optimizing charging efficiency, and optimizing charging quality. All these works use a charging model with the linear superposition, which may not be the most accurate in a real life situation. We use a concurrent charging model, which has a nonlinear superposition, and we consider the Fast Charging Scheduling problem (FCS): given multiple chargers and a group of sensor nodes, how can the chargers be optimally scheduled over the time dimension so that the total charging time is minimized and each sensor node has at least energy E? We prove that FCS is NP-complete and propose algorithms to solve the problem in 1D line and 2D plane respectively. Unlike other algorithms, our algorithm does not need to calculate the combined energy of every possible combination of chargers in advance, which greatly reduces the complexity. We obtain a bound in 2D cases when chargers and sensors are uniformly distributed. Extensive simulations demonstrate that the performance of our algorithm is almost as good as the optimal algorithm when the distribution of chargers is not very dense.

Recent breakthroughs in wireless power transfer make it possible to charge sensors over a long distance. Existing works have mainly focused on maximizing network lifetime, optimizing charging efficiency, and optimizing charging quality. All these works use a linear superposition charging model, which may not be accurate in real life situations. We use the actual charging model, which has a nonlinear super-position and we consider the charging scheduling problem (CSP): given multiple chargers and a group of sensor nodes, how can the chargers be optimally scheduled so that the total charging time is minimized and each sensor node has at least energy E? We prove that CSP is NP-hard, and propose a weight-greedy algorithm to solve the problem. Unlike the algorithm proposed before, ours does not need to calculate all charger groups utility in advance, which reduces the complexity. Extensive simulations demonstrate that the performance of our algorithm with sparse network is almost as good as the optimal algorithm. In general cases, our algorithm outperforms the random algorithm. Furthermore, our algorithm obtains the best solution in two special cases.

Wireless power transfer is a promising technology used to extend the lifetime of, and thus enhance the usability of, energy-hungry battery-powered devices. It enables energy to be wirelessly transmitted from power chargers to energy-receiving devices. Existing studies have mainly focused on maximizing network lifetime, optimizing charging efficiency, minimizing charging delay, etc. In this paper, we consider wireless charging service provision in a two-dimensional target area and focus on optimizing charging quality, where the power of each charger is adjustable. We first consider the charger Placement and Power allocation Problem with Stationary rechargeable devices (SP3): Given a set of stationary devices and a set of candidate locations for placing chargers, find a charger placement and a corresponding power allocation to maximize the charging quality, subject to a power budget. We prove that SP3is NP-complete, and propose an approximation algorithm. We also show how to deal with mobile devices (MP3), cost-constrained power reconfiguration (CRP), and optimization with more candidate locations. Extensive simulation results show that, the proposed algorithms perform very closely to the optimum (the gap is no more than 4.5, 4.4, and 5.0 percent of OPT in SP3, MP3, and CRP, respectively), and outperforms the baseline algorithms.

The lines between IaaS, PaaS, and SaaS are becoming blurred as datacenter providers seek to create cloud platforms that can widen their appeal to developers. With this kind of hybrid datacenter, resource requests from tenants are increasingly transforming into hybrid requests that may simultaneously demand IaaS, PaaS, and SaaS resources. This paper tackles the challenge of modeling and deploying hybrid tenant requests in datacenter networks, for which we coin ``networklet" to represent a set of VMs that collaboratively provide some PaaS or SaaS service. Through extracting networklets from tenant requests and thus sharing them between multiple tenants, we can achieve a win-win situation for datacenter providers and tenants. Extensive evaluations show that, the proposed model and deployment algorithm indeed improve DCN resource utilization while maintaining performance guarantee.

In today's datacenters, resource requests from tenants are increasingly transforming into hybrid requests that may simultaneously demand IaaS, Paas, and SaaS resources. This paper tackles the challenge of modeling and deploying hybrid tenant requests in datacenters, for which we coin "networklet" to represent a set of VMs that collaboratively provide a PaaS or SaaS service. Through extracting networklets from tenant requests and thus sharing them between tenants, we can achieve a win-win situation for datacenter providers and tenants.

Mobile crowdsensing is a new paradigm in which a requester can recruit a group of mobile users via a platform and coordinate them to perform some sensing tasks by using their smartphones. In mobile crowdsensing, each user might perform multiple tasks with different sensing qualities. An important problem is recruiting the minimum number of users while achieving a satisfactory sensing quality for each task. Meanwhile, in order to ease users' worries about privacy disclosures, the user recruitment process needs to protect each user's sensing quality information from being revealed to other users or to the platform. We prove that this problem is NP-hard. To solve this problem, we first propose a Basic User Recruitment (BUR) protocol based on a greedy strategy, which can recruit nearly the minimum amount of users while ensuring that the total sensing quality of each task is no less than a given threshold. Based on BUR, we further propose a Secure User Recruitment (SUR) protocol by using secret sharing schemes. We analyze the approximation ratio and prove the security of the SUR protocol in the semi-honest model. Moreover, we extend SUR to deal with a more general case where the total sensing quality of each task might be an increasing submodular function. Finally, we demonstrate the significant performance of the proposed protocol through extensive simulations and execution in real smartphones.

The various flows in production datacenters usually can be classified into two types: bandwidth-hungry and delay-sensitive. To improve their performance, datacenter networks require effective load balancing and flow control protocols, respectively. However, as the two techniques are typically employed separately in current datacenters, they are unable to optimize the network in a coordinated way. In this work, we argue that the adaptive routing, in load balancing sense, and the flow control, in congestion control sense, could be tightly coupled at the transport layer to handle the complex datacenter traffic. We design OmniFlow, a novel transfer protocol which aims to achieve a proper balance between throughput and latency in a datacenter. Firstly, it can simultaneously and precisely measure the queueing latencies on multiple paths between two hosts, which enables it to have more visibility of the path congestion and have better control of the transmission states. Secondly, OmniFlow adaptively integrates the load balancing and flow control modules and shares the same congestion metrics (i.e. queueing latencies) between them. Based on different network conditions, it either dynamically reroutes flows to utilize the bisection bandwidth or proactively adjusts flow rates to bound queueing occupancies. The results of extensive experiments show that OmniFlow can provide both low average and tail latency for small flows without sacrificing the throughput of elephant flows.

Wireless power transfer provides a promising way to extend the battery lifetime of our energy-hungry rechargeable devices. Previous studies have envisioned using mobile vehicles/robots/drones equipped with high capacity batteries as mobile chargers to replenish those devices, and they mainly focus on maximizing network lifetime, optimizing efficiency of charging scheduling, minimizing total charging delay, etc. However, existing methods may be insufficient and inflexible when the energy consumption of rechargeable devices fluctuates overtime, or when rechargeable devices are sparse. In this paper, we consider how to efficiently provide flexible wireless charging using pre-planned charging itineraries. We present the Itinerary Selection and Charging Association (ISCA) problem: given a set of rechargeable devices and a set of candidate charging itineraries, how can we select itineraries and determine a corresponding charging association to minimize the amount of energy which is due to mobile chargers' movement and wireless charging loss, so that every device gets its required energy. We prove that ISCA is NP-complete by reducing the set cover problem to it. We start solving this problem by first looking at the case in which an itinerary can only be used once, and we propose an algorithm with approximation ratio of O (lnM) and a practical heuristic algorithm, where M is the number of devices. For the general case in which an itinerary may be used multiple times, we propose an approximation algorithm of factor 10 using the Primal-Dual schema. Evaluations results from real field experiments and extensive simulations show that the proposed algorithms have near-optimal performance and PDA reduces the amount of wasted energy by up to 65 percent compared with a set cover-based algorithm.

Existing data center transport protocols are usually based on the Processor Sharing (PS) policy and/or the Shortest Remaining Processing Time (SRPT) policy. PS divides link bandwidth equally between competing flows, thus it fails to achieve optimal average flow completion time (FCT). SRPT prioritizes flows that have the shortest remaining processing time and provides near-optimal average FCT, but it may cause long flows to suffer unfair delays, or even starve them. In fact, these two types of policies represent two directions in the design space: PS prefers fairness (in terms of starvation freedom) while SRPT favors efficiency (in terms of average FCT). In this paper, we propose a novel metric, expansion ratio, which enables us to strike a balance between SRPT and PS. We design MERP that achieves efficient flow scheduling without starvation. MERP takes care of both average and tail FCTs by minimizing the expansion ratio of competing flows in a lexicographically manner. MERP controls the sending rate of competing flows via synchronized virtual deadlines and routes flows in a downstream-aware manner that reacts quickly to link failures. We evaluate MERP using extensive NS2-based simulations. Results show that, under various traffic loads, MERP reduces the tail FCT significantly with a negligible increase of average FCT compared with pFabric, and MERP reduces the average FCT notably compared with ECMP and CONGA when link failures occur.

In this paper, we propose OmniFlow, a novel transport protocol which combines load balancing and flow control at the transport layer to optimize datacenter transfers. OmniFlow outweighs previous solutions in two aspects. Firstly, it can simultaneously and precisely measure the queueing latencies on multiple paths between two hosts. Secondly, OmniFlow adaptively integrates the load balancing and flow control modules and shares the same congestion metrics (i.e. queueing latencies) between them. Based on different network conditions, it either dynamically reroutes flows to utilize the bisection bandwidth or proactively adjusts flow rates to bound queueing occupancies. Our results show that OmniFlow can provide both low latency for small flows without sacrificing the throughput of elephant flows.

Virtualization technology has brought new vitality to data centers but also brought some thorny issues. Virtualization technology creates an abstract intermediate layer, separating the upper layer applications from the underlying infrastructure, which cause some difficulties to the upper layer applications for the effective use of resources. Based on this observation, we propose a dynamic load balancing system in virtualized environment. The system adjusts the weights of virtual machines in real-time in order to balancing physical servers' load and improve data center efficiency. In addition, by monitoring physical machine failure information, we can evacuate physical machines as soon as they failed to ensure high availability of the data center. We design a virtualized environment monitoring system and propose an efficient algorithm. We evaluate the proposed system with real implementations which show DLB has rather good performance.

Mobile devices are undergoing explosive proliferation today. Although they are gaining more and more capabilities, they still fall short to execute complex applications. One possible solution to alleviate this limitation is offloading tasks to remote clouds. However, it may require persistent connectivity to the Internet and thus is not always available or affordable. An alternative solution is taking advantage of pervasive mobile devices and their pairwise encounters. In this paradigm, complex tasks from mobile devices are processed in a distributed and collaborative fashion on all mobile devices that are loosely-connected. Working towards this vision, this paper studies the following problem: given a task that originates at some node in a Disruption Tolerant Network (DTN), how are we to disseminate the task's workload during the pairwise contacts among mobile devices to achieve makespan minimization? We first imagine access to an oracle that has global and future knowledge of node mobility, and we design a provably-optimal centralized polynomial-time solution as the benchmark for comparison. With the insights obtained from the centralized solution, we then develop a distributed dissemination algorithm, D2, which maintains certain neighborhood information at individual nodes. D2 makes dissemination decisions based on the estimations of the potential computational capacities and the future workloads of mobile nodes. Extensive trace-driven simulations confirm the effectiveness of D2.

In computing clouds, burstiness of a virtual machine (VM) workload widely exists in real applications, where spikes usually occur aperiodically with low frequency and short duration. This could be effectively handled through dynamically scaling up/down in a virtualization-based computing cloud; however, to minimize energy consumption, VMs are often highly consolidated with the minimum number of physical machines (PMs) used. In this case, to meet the dynamic runtime resource demands of VMs in a PM, some VMs have to be migrated to some other PMs, which may cause potential performance degradation. In this paper, we investigate the burstiness-aware server consolidation problem from the perspective of resource reservation, i.e., reserving a certain amount of extra resources on each PM to avoid live migrations, and propose a novel server consolidation algorithm, QUEUE. We first model the resource requirement pattern of each VM as a two-state Markov chain to capture burstiness, then we design a resource reservation strategy for each PM based on the stationary distribution of a Markov chain. Finally, we present QUEUE, a complete server consolidation algorithm with a reasonable time complexity. We also show how to cope with heterogenous spikes and provide remarks on several extensions. Simulation and testbed results show that, QUEUE improves the consolidation ratio by up to 45 percent with large spike size and around 30 percent with normal spike size compared with the strategy that provisions for peak workload, and achieves a better balance between performance and energy consumption in comparison with other commonly-used consolidation algorithms.

To improve users' experience, TCP short flows that are heavily used in interactive services should be completed as soon as possible. In current data centers, large flows and head-of-line blocking in switches hinder short flows from completion, which leads to long-tailed flow completion times (FCT). Replicating short flows with multiple equal-cost paths is a promising way to reduce FCT. However, the original flow and its replicated one are quite likely to be routed to the same path (ECMP hash collision), which increases both the mean and 99-percentile FCT significantly. What's more, inadequate replication leaves many other less-congested equal-cost paths unused and limits the performance while excess replication degrades throughput of large flows. To solve these problems, we propose SmartRep, a scheme consisting of an efficient and effective traceroute based hash collision avoidance method and an algorithm to decide the optimal number of replicated flows for different short flows. SmartRep can be easily implemented in software and readily deployed in data centers. Extensive NS2 simulations show that our approach improves previous replication-based work by 25%-50% in both mean and 99th percentile FCT, and meanwhile imposes negligible impact on large flows.

Wireless power transfer is a promising technology to extend the lifetime of, and thus enhance the usability of, the energy-hungry battery-powered devices. It enables energy to be wirelessly transmitted from power chargers to energy receiving devices. Existing studies have mainly focused on maximizing network lifetime, optimizing charging efficiency, minimizing charging delay, etc. Different from these works, our objective is to optimize charging quality in a 2-D target area. Specifically, we consider the following charger Placement and Power allocation Problem (P3): Given a set of candidate locations for placing chargers, find a charger placement and a corresponding power allocation to maximize the charging quality, subject to a power budget. We prove that P3is NP-complete. We first study P3with fixed power levels, for which we propose a (1-1/e)-approximation algorithm; we then design an approximation algorithm of factor 1-1/e / 2L for P3, where e is the base of the natural logarithm, and L is the maximum power level of a charger. We also show how to extend P3in a cycle. Extensive simulations demonstrate that, the gap between our design and the optimal algorithm is within 4.5%, validating our theoretical results.

Wireless sensor networks (WSNs) is an area of research that has been getting a lot of attention lately. This is due to the rapid advancements in the design of wireless devices which have increasingly more processing, storage, memory, and networking capabilities. In addition, the cost of sensors is constantly decreasing making it possible to use large quantities of these sensors in a wide variety of important applications in environmental, military, commercial, health care, and other fields. In order to monitor certain types of infrastructures, many of these applications involve lining up the sensors in a linear form, making a special class of these networks which are defined in this work as Linear Sensor Networks (LSNs). In a previous paper, we introduced the concept of LSNs along with a classification of the different types of LSNs, a sample of their applications and the motivation for designing specialized protocols that take advantage of the linearity of the network to enhance their communication efficiency, reliability, fault tolerance, energy savings, and network lifetime. This paper presents a graph-search-based topology discovery algorithm for LSNs. New definitions for important structure and design parameters are introduced. The proposed protocol allows the nodes to identify some nodes to be included in a backbone, which can be used by the other nodes to send data to the sink at the end of the LSN or LSN segment. This backbone discovery increases the efficiency, and robustness of the network. It also allows for significant improvement in the scalability of the communication process in the LSN which can contain a very large number of nodes (e.g. Hundreds or thousands). In addition, the linearity of the structure and the discovered backbone can enhance the routing reliability by "jumping" over failed nodes by increasing the range. Furthermore, the protocol does not require the nodes to have location detection capabilities such as GPS, which would lead to a more complex design and higher cost of the sensor nodes.

The limited battery capacity of sensor nodes has become one of the most critical impediments that stunt the deployment of wireless sensor networks (WSNs). Recent breakthroughs in wireless energy transfer and rechargeable lithium batteries provide a promising alternative to power WSNs: mobile vehicles/robots carrying high volume batteries serve as mobile chargers to periodically deliver energy to sensor nodes. In this paper, we consider how to schedule multiple mobile chargers to optimize energy usage effectiveness, such that every sensor will not run out of energy. We introduce a novel charging paradigm, collaborative mobile charging, where mobile chargers are allowed to intentionally transfer energy between themselves. To provide some intuitive insights into the problem structure, we first consider a scenario that satisfies three conditions, and propose a scheduling algorithm, PushWait, which is proven to be optimal and can cover a one-dimensional WSN of infinite length. Then, we remove the conditions one by one, investigating chargers’ scheduling in a series of scenarios ranging from the most restricted one to a general 2D WSN. Through theoretical analysis and simulations, we demonstrate the advantages of the proposed algorithms in energy usage effectiveness and charging coverage.

Today's public cloud providers typically deploy their small sized data centers in multiple geographically different locations, so as to improve data center power usage effectiveness and locate resources closer to users. A major challenge is resource allocation. Many results have been reported regarding this issue from the perspectives of virtual machine consolidation, network-aware virtual machine placement, traffic engineering, dynamic capacity provisioning, and so on. However, there has not been any focus on stable resource allocations, where no resource request or data center has any migration incentives. To the best of our knowledge, this paper is the first attempt at gaining a better understanding of the structure of the Stable rEsource Allocation (SEA) problem. We introduce a formal problem statement and develop two algorithms for the 1-dimensional (1-D) and 2-D cases, respectively. Simulation results show that the proposed algorithms have good scalability and convergence.

Virtual networks that allow tenants to explicitly specify their computing as well as networking resources are recently proposed to be better interfaces between cloud providers and tenants. Many virtual networks have time-varying resource demands, as evidenced in prior studies [1-3]. New opportunities emerge when such variation is exploited. In this paper, we design a novel resource demand model for tenants to flexibly trade off between application performance and cost, and propose a work-conserving allocation algorithm, WCA, for deploying virtual networks with time-varying resource demands. WCA places virtual nodes in a first-fit fashion, and places virtual links through path-splitting. In each physical node or link, by opportunistically sharing physical resources among multiple variable parts of resource demands, physical utilization can be improved, and more virtual networks can be deployed concurrently. Our evaluation results show that WCA achieves a 4% higher physical resource utilization and rejects 18% less virtual network requests than a state-of-the-art algorithm [4].

Internetware challenges distributed systems in aspects from operating platforms, programming models, to engineering approaches, etc. Cloud computing based on virtualization is now a popular paradigm which can meet the dynamic resource allocation requirements of Internetware. Software entities dispersed on distributed nodes over the Internet, now are evolving into self-contained, autonomous software services. These software entities which are often deployed on virtual machines (VMs), are coordinated dynamically to achieve flexible design objectives. To improve the utilization of infrastructure resource, VMs processing components of a software should be consolidated to fewer physical machines (PMs). However, as the increasing trends of communication-intensive softwares, data traffic among VMs should be considered as well. And for the sake of safety and QoS (Quality of Service), certain VMs (e.g. backup nodes) are mutually-exclusive which means some VMs require to be placed on different PMs. In this paper, we investigate the online software placement problem with the target to minimize the network traffic cost, while taking into account the mutually-exclusiveness of VMs. We provide a formal problem description and its NP-hardness analysis. The proposed algorithm places the VMs that have heavy traffic on the same PM, while isolating the mutually-exclusive VMs simultaneously, which can guarantee high effectiveness and reliability for softwares in Internetware, respectively. The simulations show our algorithm reduces the traffic cost by 29% compared against the existing approaches.

Network virtualization has emerged as a promising approach to overcome the ossification of the Internet. A major challenge in network virtualization is the so-called virtual network embedding problem, which deals with the efficient embedding of virtual networks with resource constraints into a shared substrate network. A number of heuristics have been proposed to cope with the NP-hardness of this problem; however, all of the existing proposals reserve fixed resources throughout the entire lifetime of a virtual network. In this paper, we re-examine this problem with the position that time-varying resource requirements of virtual networks should be taken into consideration, and we present an opportunistic resource sharing-based mapping framework, ORS, where substrate resources are opportunistically shared among multiple virtual networks. We formulate the time slot assignment as an optimization problem; then, we prove the decision version of the problem to be NP-hard in the strong sense. Observing the resemblance between our problem and the bin packing problem, we adopt the core idea of first-fit and propose two practical solutions: first-fit by collision probability (CFF) and first-fit by expectation of indicators' sum (EFF). Simulation results show that ORS provides a more efficient utilization of substrate resources than two state-of-the-art fixed-resource embedding schemes.

Many environmental, commercial, military, and structural monitoring applications of wireless sensor networks (WSNs) involve lining up the sensors in a linear form, and making a special class of these networks; we defined these in a previous paper as Linear Sensor Networks (LSNs), and provided a classification of the different types of LSNs. A multihop approach to routing the data from the individual sensor nodes to the sink can be used in an LSN. However, this can result in a rapid depletion of the sensor energy, due to the frequent transmissions performed by the sensors to transmit their own, as well as other sensor data. In addition, in many applications, the distance between the sensors deployed to monitor the linear structure might be much greater than the communication range leading to a disconnected network where the multihop approach cannot be used. This paper presents a framework for monitoring linear infrastructures using ferry-based LSNs (FLSNs). The data that is collected by the sensors is assumed to be delay-tolerant. In such a system, a moving robot, vehicle, or any other mobile node (named a ferry), can move back and forth along the linear network, and collect data from the individual sensors when it comes within their communication range; The ferry can deliver the collected sensor data when it reaches the sink. It can also perform other functions, such as data processing, and aggregation, and can also transport messages from the sink to the sensor nodes (SNs). Four different ferry movement approaches are presented, simulated, and analyzed.

This paper poses the following problem: given a task that originates at some node in a Delay Tolerant Network (DTN), how are we to disseminate the workload during pairwise contacts to minimize the makespan? We first investigate the scenario in which each node has access to an oracle that knows global and future knowledge of node mobility, and we propose a centralized polynomial-time optimal algorithm. We then develop a distributed dissemination protocol, D2, which maintains r-hop neighborhood information at individual nodes. D2 makes dissemination decisions based on the estimations of the potential computational capacities and the future workloads of DTN nodes. Using trace-driven simulations, we show that, D2 with only 1-hop information is already near-optimal in a wide variety of environments, and the performance gap becomes smaller as the amount of information maintained at individual nodes increases.

Network virtualization has been the focus of intense research interest and is a promising approach to overcome the ossification of the Internet. A major challenge with network virtualization is virtual network embedding, which deals with the efficient embedding of virtual networks with resource constraints into a substrate network. Many research results have been reported regarding this problem. However, there hasn't been any focus on virtual network embedding with substrate support for parallelization, i.e., the substrate network supports parallel computation and allows a virtual node to be mapped into multiple substrate nodes. This paper is the first attempt at gaining a better understanding on how parallelization benefits embedding. We present a formal problem description and propose two algorithms that capitalize parallelism. Several extensions are developed to complement the proposed algorithms. From experimental results, the effectiveness and usefulness of the algorithms and extensions are confirmed.

Network virtualization provides a promising way to overcome Internet ossification. A major challenge is virtual network mapping, i.e., how to embed multiple virtual network requests with resource constraints into a substrate network, such that physical resources are utilized in an efficient and effective manner. Since this problem is known to be NP-complete, a variety of heuristic algorithms have been proposed. In this paper, we re-examine this problem and propose a virtual network mapping framework, ORS TA, which is based on Opportunistic Resource Sharing and Topology-Aware node ranking. Opportunistic resource sharing is taken into consideration at the entire network level for the first time and we develop an online approximation algorithm, FFA, for solving the corresponding time slot assignment problem. To measure the topology importance of a substrate node, a node ranking method, MCRank, based on Markov chain is presented. We also devise a simple and practical method to estimate the residual resource of a substrate node/link. Extensive simulation experiments demonstrate that the proposed framework enables the substrate network to achieve efficient physical resource utilization and to accept many more virtual network requests over time.

The limited battery capacity of sensor nodes has become the biggest impediment to wireless sensor network (WSN) applications. Two recent breakthroughs in the areas of wireless energy transfer and rechargeable lithium batteries promise the use of mobile vehicles, with high volume batteries, as mobile chargers that transfer energy to sensor nodes wirelessly. In this paper, for the first time, we envision a novel charging paradigm: collaborative mobile charging, where mobile chargers are allowed to charge each other. We investigate the problem of scheduling multiple mobile chargers, which collaboratively recharge sensors, to maximize the ratio of the amount of payload energy to overhead energy, such that every sensor will not run out of energy. We first consider the uniform case where all sensors consume energy at the same rate, and propose a scheduling algorithm, PushWait, which is proven to be optimal in this case and can cover a one-dimensional WSN of infinite length. Then, in the non-uniform case, which is conjectured to be NP-hard, we first present two observations from space and time aspects to remove some impossible scheduling choices, and we propose our heuristic algorithm, ClusterCharging(β), which clusters sensors into groups and divides a scheduling cycle into charging rounds. Its approximation ratio is also presented. Extensive evaluations confirm the efficiency of our algorithms.

Network virtualization has emerged as a powerful way to fend off the current ossification of the Internet. A major challenge is virtual network mapping, which is to assign substrate resources to virtual networks (VNs) such that some predefined constraints are satisfied and substrate resources are utilized in an effective and efficient manner. Due to the NP-completeness of this problem, a variety of heuristic algorithms have been proposed. However, existing solutions rarely consider the inefficient utilization of bandwidth resources due to the network traffic fluctuation. In this paper, we study the opportunistic bandwidth sharing in a single physical link among multiple virtual links from different VNs. We formulate the problem of assigning time slots to dispensable sub-flows with constraints on the performance guarantee and the objective of minimizing the number of time slots used, as an optimization problem. Two heuristic algorithms HA-I and HA-II, which consider the problem from different perspectives, are presented. Extensive simulations are conducted to evaluate the effectiveness and efficiency of our algorithms.

Network virtualization has emerged as the most promising approach to overcome the current ossification of the Internet. A key problem in it is how to efficiently and effectively make use of the substrate network resources by embedding multiple virtual networks with various constraints. Due to its NP-hardness, many heuristic approaches have been proposed. However, most of them simplify the problem by relaxing some constraints, resulting in their designs in conflict with practical limitations. Furthermore, some other important design issues, like load balancing and the response time requirements of different applications, have been usually ignored as well. In this paper, we propose FELL, a Flexible virtual network Embedding algorithm with guaranteed Load baLancing for the general problem. Based on simulated annealing, FELL can flexibly control the tradeoff between results accuracy and running time to meet various requirements of different applications by changing parameters. Load balancing enables substrate network to avoid resource fragmentation and further increases the profit of infrastructure providers. A novel cost criterion that reflects the impact of distribution of allocated resources for an embedding is designed to conduct embedding process to guarantee it. The splittable flow is supported to obtain better resource utilization by making use of small pieces of available bandwidth. We also design some key functions including generating initial and neighbor solutions. The effectiveness of our algorithm is finally validated by our simulations.

A lot of network services and applications are being designed to support quality-of-service (QoS) routing. One of the key problems is to find a feasible path that satisfies multiple QoS requirements, i.e., Multi-Constrained Path (MCP) problem which is known to be NP-complete. Many heuristic and approximation algorithms have been proposed to solve this problem. However, most of them converted it into the classic shortest path problem by transforming multiple QoS weights into single weight. In this paper, we propose a binary graph reduction (BGR) algorithm to convert network graph into a simplified graph by removing redundant edges before constructing a routing path. BGR improves system performance from two aspects: i) BGR decreases the decision-making time, which then decreases the delay of end users; ii) BGR removes some abnormal anti-heuristic redundant edges from network graph, so that the actual routing algorithm could get a better result. We use a multimedia delivery system to illustrate these advantages in this paper. Simulation results also approve the efficiency of the proposed BGR algorithm.

Service composition is an effective approach for multimedia delivery in pervasive environment. In previous works, there is one fixed functional path which is composed of several underlying services in a certain order. Actually, there are several functional paths delivering different quality level multimedia from the source to the end user. Due to the dynamicity and mobility of pervasive space, system should generate a reliable and low-delay service path for multimedia delivery in real-time. Since some multimedia service components change the data transmission volume which has a deep impact on the transmission delay, it makes the media delivery problem equal to Multi-Constrained Path problem which is known to NP-Complete. We propose an efficient algorithm LD/RPath(Lowest Delay/Reliability Path) for adaptive multimedia delivery. LD/RPath generates a low-delay service path based on several functional paths with reliability guarantee. Experiment results show that LD/RPath has a good performance and it is an effective algorithm for multimedia delivery in pervasive space.

Service composition is an effective approach for large- scale multimedia delivery. One of the challenge issues is how to choose services to build a multimedia delivery path from source to destination based on user's requirements. In previous works, user's requirement is represented as one fixed functional path which is composed of several functional components in a certain order. Actually, there may be several functional paths (deliver different quality level multimedia data, e.g. image pixel, frame rate) that can meet one request. And due to the diversity of devices and connections in pervasive environment, system should choose a suitable media quality delivery path in accordance with context, instead of based on one fix functional path. This paper proposes LDpath which aims at delivering multimedia data to end users with lowest delay. It chooses services to build delivery path hop-by-hop and the generated path matches one of the possible functional paths, which essentially achieves the context aware multimedia delivery. Furthermore, the amount of data transmission deeply affects delay, thus, LDpath considers data volume changing as one of the metrics of service selection. Experimental results show that LDpath is an effective approach for multimedia delivery in pervasive space.