Low-field portable magnetic resonance imaging (pMRI) devices address a crucial requirement in the realm of healthcare by offering the capability for on-demand and timely access to MRI, especially in the context of routine stroke emergency. Nevertheless, images acquired by these devices often exhibit poor clarity and low resolution, resulting in their reduced potential to support precise diagnostic evaluations and lesion quantification. In this paper, we propose a 3D deep learning based model, named Stroke-Aware CycleGAN (SA-CycleGAN), to enhance the quality of low-field images for further improving diagnosis of routine stroke. Firstly, based on traditional CycleGAN, SA-CycleGAN incorporates a prior of stroke lesions by applying a novel spatial feature transform mechanism. Secondly, gradient difference losses are combined to deal with the problem that the synthesized images tend to be overly smooth. We present a dataset comprising 101 paired high-field and low-field diffusion-weighted imaging (DWI), which were acquired through dual scans of the same patient in close temporal proximity. Our experiments demonstrate that SA-CycleGAN is capable of generating images with higher quality and greater clarity compared to the original low-field DWI. Additionally, in terms of quantifying stroke lesions, SA-CycleGAN outperforms existing methods. The lesion volume exhibits a strong correlation between the generated images and the high-field images, with R=0.852. In contrast, the lesion volume correlation between the low-field images and the high-field images is notably lower, with R=0.462. Furthermore, the mean absolute difference in lesion volumes between the generated images and high-field images ( $1.73\pm 2.03$ mL) was significantly smaller than the difference between the low-field images and high-field images ( $2.53\pm 4.24$ mL). It shows that the synthesized images not only exhibit superior visual clarity compared to the low-field acquired images, but also possess a high degree of consistency with high-field images. In routine clinical practice, the proposed SA-CycleGAN offers an accessible and cost-effective means of rapidly obtaining higher-quality images, holding the potential to enhance the efficiency and accuracy of stroke diagnosis in routine clinical settings. The code and trained models will be released on GitHub: SA-CycleGAN.

The vigorous development of IoT technology has spawned a series of applications that are delay-sensitive or resource-intensive. Mobile edge computing is an emerging paradigm that provides services between end devices and traditional cloud data centers to users. However, with the continuously increasing investment of demands, it is nontrivial to maintain a higher quality-of-service (QoS) under the erratic activities of mobile users. In this paper, we investigate the service provisioning and updating problem under the multiple-users scenario by improving the performance of services with long-term cost constraints. We first decouple the original long-term optimization problem into a per-slot deterministic one by using Lyapunov optimization. Then, we propose two service updating decision strategies by considering the trajectory prediction conditions of users. Based on that, we design an online strategy by utilizing the committed horizon control method looking forward to multiple slots predictions. We prove the performance bound of our online strategy theoretically in terms of the trade-off between delay and cost. Extensive experiments demonstrate the superior performance of the proposed algorithm.

In this paper, we describe the experimental test-bed we are developing to evaluate the efficacy of computation offloading for cooperative inference without in-depth architectural changes to the models under consideration. We describe our test-bed design, functionalities, and work in progress features. We demonstrate a simple use case of the test-bed, consisting of the identification of a split layer in an AlexNet for a particular hardware scenario and the validation of those results.

We observe that accurate and fast tracking in Internet of Things (IoT) devices is still a challenging problem. Several deep learning models have emerged which provide higher accuracy scores in object detection and tracking, however, due to their computationally expensive nature they are not useful in enabling real-time tracking at IoT devices. Correlation filters have emerged to show better speed in real-time tracking and provide good tracking results in cases of occlusion, rotation, illumination and other distractions. To get better speed as well as accuracy we use combination of correlation filter and deep learning methods. We propose a distributed tracking and verifying (DTAV) framework. Specifically, we run two object tracking algorithms, one on the client and another on the server. The algorithm run on the client is referred to as the Tracker, which is based on correlation filter and runs easily in real-time. The server hosts the verifier algorithm which performs high accuracy verification. Thus, while the client performs fast object tracking, the server's tracking algorithm verifies the output and corrects the server whenever required to maintain the accuracy of the model. We present our edge computing-based framework and discuss the motivation, system setup and series of experiments performed for the framework and present our experimental results. DTAV achieved 7.78% improvement on accuracy and 15% improvement in FPS.

Abstract Fog computing is an emerging paradigm that supplies storage, computation, and networking resources between traditional cloud data centers and end devices. This article focuses on the resource provisioning problem in collaborative fog computing for multiple delay‐sensitive users. Our goal is to implement a resource provisioning strategy for network operators to minimize the total monetary cost by considering the deadline and capacity constraints. Two scenarios are considered: unlimited‐processor fog nodes (UPFN) and limited‐processor fog nodes (LPFN). In either scenario, we prove that the resource provisioning problem is NP‐hard. First, we consider the UPFN scenario that the processors of fog nodes are unlimited and users' requests can be ideally processed in parallel. Two algorithms are proposed which greedily delete fog nodes based on the local or global collaborative influences until there is no feasible provisioning to guarantee the deadline of users. Then we extend the resource provisioning problem to a more realistic and complicated scenario LPFN in which the scheduling delay cannot be ignored. Two types of tasks are considered. One is the arbitrarily divided tasks, and a near‐optimal solution bounded by has been found. m is the number of fog nodes, and is the upper bound on the Lipschitz constant of the delay function. Another one is the application‐driven tasks, and we propose a heuristic algorithm. Extensive experiments validate the efficiency of the proposed algorithms.

Urban tracking plays a vital role for people’s urban life in intelligent transportation systems, e.g., public safety, case investigation, finding missing items, etc. However, the current tracking methods consume a large amount of communication and computing resources since they mainly offload all related sensing data, i.e., videos, generated by widely deployed cameras to the cloud where data are stored, processed, and analyzed. In this paper, we propose a graph optimized data offloading algorithm leveraging a crowd-AI hybrid method to minimize the data offloading cost and ensure the reliable urban tracking result. To be specific, we first formulate a crowd-AI hybrid urban tracking scenario, and prove the proposed data offloading problem in this scenario is NP-hard. Then, we solve it by decomposing the problem into two parts, i.e., trajectory prediction and task allocation. The trajectory prediction algorithm, leveraging the state graph, computes possible tracking areas of the target object, and the task allocation algorithm, using the dependency graph, chooses the optimal set of crowds and cameras to cover the tracking area while minimizing the data offloading cost separately. Finally, the extensive simulations with large real world data set are conducted showing that the proposed algorithm outperforms benchmarks in reducing data offloading cost while ensuring the tracking success rate in intelligent transportation systems.

With the rapid development of Internet-of-Things (IoT) and the explosive advance of deep learning, there is an urgent need to enable deep learning inference on IoT devices in Mobile Edge Computing (MEC). To address the computation limitation of IoT devices in processing complex Deep Neural Networks (DNNs), computation offloading is proposed as a promising approach. Recently, partial computation offloading is developed to dynamically adjust task assignment strategy in different channel conditions for better performance. In this paper, we take advantage of intrinsic DNN computation characteristics and propose a novel Fused-Layer-based (FL-based) DNN model parallelism method to accelerate inference. The key idea is that a DNN layer can be converted to several smaller layers in order to increase partial computation offloading flexibility, and thus further create the better computation offloading solution. However, there is a trade-off between computation offloading flexibility as well as model parallelism overhead. Then, we investigate the optimal DNN model parallelism and the corresponding scheduling and offloading strategies in partial computation offloading. In particular, we propose a Particle Swarm Optimization with Minimizing Waiting (PSOMW) method, which explores and updates the FL strategy, path scheduling strategy, and path offloading strategy to reduce time complexity and avoid invalid solutions. Finally, we validate the effectiveness of the proposed method in commonly used DNNs. The results show that the proposed method can reduce the DNN inference time by an average of 12.75 times compared to the legacy No FL (NFL) algorithm, and is very close to the optimal solution achieved by the Brute Force (BF) algorithm with the difference of less than 0.04%.

With the development of Internet of Things (IoT) and the advance of deep learning, there is an urgent need to enable deep learning inference on IoT devices. To address the computation limitation of IoT devices in processing complex Deep Neural Networks (DNNs), partial computation offloading is developed to dynamically adjust computation offloading assignment strategy in different channel conditions for better performance. In this paper, we take advantage of intrinsic DNN computation characteristics, and propose a novel Fused-Layer-based (FL-based) DNN model parallelism method to accelerate inference. The key idea is that a DNN layer can be converted to several smaller layers to increase partial computation offloading flexibility, and thus further create better computation offloading solution. However, there is a trade-off between parallelism computation offloading flexibility and model parallelism overhead. Then, we discuss the optimal DNN model parallelism and the corresponding scheduling and offloading strategies in partial computation offloading. In particular, we present a Minimizing Waiting (MW) method, which explores both the FL strategy, the path scheduling strategy, and the path offloading strategy to reduce time complexity. Finally, we validate the effectiveness of the proposed method in commonly used DNNs. The results show that the proposed method can reduce the DNN inference time by an average of 18.39 times compared with No FL (NFL) algorithm, and is very close to the optimal solution Brute Force (BF) with greatly reduced time complexity.

Service mesh is a promising micro-services architecture due to its excellent governance capabilities. Unlike traditional service invocation, configurations for governance need to be issued in the service mesh. However, we find that the control-plane traffic of governance is distributed in full by default, i.e., each service in the data plane receives all configurations. The vast majority of the configurations are redundant for a specific service. Hence, it is important and challenging to make the control plane aware of the calling relationships between services. In this paper, we propose a traffic management mechanism named DATM. Using this mechanism, the entire cluster can be dynamically controlled and services can be configured on demand. It is implemented through a dependency-aware controller and monitors. The controller first processes the information listened to by the monitors and then analyzes the connection between the metrics and the service requests through intelligent algorithms. Finally, the control traffic for regulating the control plane is generated. Our proposed mechanism is experimentally compared with the default strategy and existing work across a wide set of load scenarios in a testbed based on Istio service mesh and Kubernetes. Experimental results demonstrate that our mechanism can save the storage resources of a single agent by 40% to 60%, and the number of cluster updates can be greatly reduced. From the perspective of the whole cluster, the optimization results are even better.

The vigorous development of IoT technology has spawned a series of applications that are delay-sensitive or resource-intensive. Mobile edge computing is an emerging paradigm which provides services between end devices and traditional cloud data centers to users. However, with the continuously increasing investment of demands, it is nontrivial to maintain a higher quality-of-service (QoS) under the erratic activities of mobile users. In this paper, we investigate the service provisioning and updating problem under the multiple-users scenario by improving the performance of services with long-term cost constraints. We first decouple the original long-term optimization problem into a per-slot deterministic one by using Lyapunov optimization. Then, we propose two service updating decision strategies by considering the trajectory prediction conditions of users. Based on that, we design an online strategy by utilizing the committed horizon control method looking forward to multiple slots predictions. We prove the performance bound of our online strategy theoretically in terms of the trade-off between delay and cost. Extensive experiments demonstrate the superior performance of the proposed algorithm.

Nowadays, vehicles have been increasingly adopted in many spatial crowdsourcing (SC) applications. Similar to other SC applications, location privacy is of great concern to vehicle workers as they are required to disclose their own location to servers to facilitate the service utilities. Traditional location privacy protection mechanisms cannot be applied to vehicle-based SC since they assume workers’ mobility on a 2-dimensional plane without considering the network-constrained mobility features of vehicles. Accordingly, in this paper, we aim at addressing issues related to Vehicle-based spatial crowdsourcing Location Privacy (VLP) over road networks. Our objective is to design a location obfuscation strategy to minimize the quality loss due to obfuscation withgeo-indistinguishabilitysatisfied. Considering the computational complexity of VLP, by resorting to discretization, we first approximate VLP to a linear programming problem that can be solved by well-developed approaches. To further improve the time-efficiency, we conduct constraint reduction for VLP by exploiting key features of geo-indistinguishability in road networks and problem decomposition based on VLP’s constraint structure. Finally, we carry out both trace-driven simulation and real-world experiments, where our experimental results demonstrate the superiority of our approach over a known state-of-the-art location obfuscation strategy in terms of both quality-of-service and privacy.

The rapid growth in pervasive Internet-of-Things (IoT) and Deep Learning (DL) is creating a huge demand for applying DL on IoT systems. However, it is non-trivial to train highly accurate DL models in such scenarios due to the following two challenges: (1) individual IoT devices may not have sufficient training data, and (2) simply combining all sensory data across all devices may cause performance degradation due to data imbalance and varying temporal patterns across different devices. The objective of this paper is to achieve high-accurate prediction models for each device in an IoT system. We propose a federated learning approach for IoT systems driven by trend-based clustering for energy demand prediction for Electric Vehicle (EV) charging station network. We first apply a time-series clustering method to identify stations with similar temporal demand patterns. Using time-series data from stations in a cluster, a single Long-Short Term Memory (LSTM) network is trained using FedAvg algorithm for energy demand prediction for all the stations in the cluster. Experimental results on a real-world energy usage dataset from an EV charging station network show that our proposed approach is very competitive against baseline federated learning approaches. In particular, the energy demand prediction error decreases by 80%.

Computation offloading is proposed to solve one obstacle of enabling high-accurate and real-time deep inference in resource-constrained Internet of Things (IoT) devices. Cooperative deep inference is proposed recently to further trade-off the introduced communication latency in computation offloading, which partitions a Deep Neural Network (DNN) model into two parts and utilizes the IoT end device and the server to process the DNN model cooperatively. We observe one important but ignored fact in all previous works: DNN computation and communication processing cbe conducted simultaneously in cooperative deep inference. As a result, the DNN layer-wise processing schedule has an impact on inference latency and it is non-trivial to find the optimal schedule in State-Of-The-Art (SOTA) DNNs with Directed Acyclic Graph (DAG) computational architectures. The contributions of this paper are as follows. (1) The proposed Deep Inference Optimization with Layer-wise Schedule, Deep-Inference-L, is a unique pipeline-based DAG schedule problem, which turns out to be NP-hard. (2) We categorize SOTA DNNs into three different categories and discuss the corresponding optimal processing schedule in special cases and efficient heuristic schedules in the general case. (3) The proposed solutions are extensively tested via a proof-of-concept prototype. (4) Results indicate that our algorithms can achieve an 8x speedup compared with local inference in the best case.

With the progress of mobile devices and the successful forms of using the wisdom of crowds, spatial crowdsourcing has attracted much attention from the research community. The idea of spatial crowdsourcing is recruiting a set of available crowds to finish the spatial tasks located in crowdsourcing locations, e.g., landmarks, by using their handheld devices. This paper addresses the worker recruitment problem in spatial crowdsourcing under the coverage and workload-balancing requirements. The coverage constraint means that any crowdsourcing location should be visited by at least one of the recruited workers to satisfy the Quality-of-Service requirement, e.g., traffic monitoring or climate forecast. In addition, we argue that each crowdsourcing operation has a cost in reality, e.g., data traffic or energy consumption and the resource may be limited at each crowdsourcing location. The objective of this paper is to solve a Coverage and Balanced Crowdsourcing Recruiting (CBCR) problem, which ensures the coverage requirement and minimizes the maximum crowdsourcing cost for any crowdsourcing location. We prove that the CBCR problem is NP-hard in the general case. Then, we discuss the CBCR problem in the 1-D scenario. In the 1-D scenario, we first propose a directionally coverage scheme and further extend it to a Polynomial-Time Approximation Scheme (PTAS) to trade-off the computation complexity and the performance. The performance can be bounded to 2 + ε, where ε can be an arbitrary small value. Then, we found that there exists a sub-optimal structure, and thus the dynamic programming approach is proposed to find the optimal solution in the 1-D scenario. In the general 2-D scenario, we first prove that it has a sub-modular property and thus the naive greedy algorithm has an approximation ratio of lnn+ 1. In addition, we propose a randomized rounding algorithm with an expectation bound of O(logn/ log logn). Extensive experiments on realistic traces demonstrate the effectiveness of the proposed algorithms.

As data center clusters need to process quintillion bytes of data per day, it becomes a critical problem that efficiently scheduling jobs to improve resource utilization. However, the data analysis job usually contains multiple stages with dependent relationships, which brings challenges for scheduling. Those stages are modeled as Directed Acyclic Graphs (DAGs) and the general DAG scheduling problem is NP-hard. In this paper, we notice that in some parallel computing frameworks such as Spark, the execution of each stage could be divided into multiple phases that use different resources. We observe that interleaving different resources in a pipelined manner could improve resource utilization. Based on this observation, we propose to minimize the job makespan by exploiting resource pipeline. We first theoretically analyze the scheduling for perfectly parallel stages. In this case, our scheduling problem is equivalent to a DAG shop problem which is NP-hard. A contention-free scheduler is proposed and its approximation properties are analyzed. Stages of real-world jobs are usually not perfectly parallel. For general jobs, a reinforcement learning (RL) based scheduler is proposed to adaptively adjust the resource contention. We evaluate our contention-free and RL-based schedulers on a Spark cluster deployed on the Amazon EC2. Experiments on real-world and synthetic datasets show our RL-based scheduler can improve the CPU and network utilization by 33.0% and 29.7%, respectively.

Ride-sharing companies such as Didi and Uber have served billions of passenger requests from all over the world. The efficiency of the ride-sharing is highly depended on the order dispatch system which assigns passenger requests to idle drivers. However, designing such a dispatch system is challenging because of the spatial-temporal dynamic of passenger requests, and the trade-off between the benefits for passengers and drivers. Existing order dispatch systems use either a system-assigning approach or a driver-grabbing approach. However, either approach has its own flaws. In this paper, we propose to combine the two existing approaches and jointly considers both passengers'' and drivers'' interest. In our approach, a passenger request is broadcast to the drivers in a dispatch region chosen by the system. The size of the dispatch region could iteratively increase until the request is accepted. We formulate an optimization problem to determine the increase speed of the dispatch region. Drivers'' idle driving distances and passengers'' waiting time are jointly considered. We propose a dynamic programming algorithm to optimally solve the increase ratio of the size of the dispatch region for a case that different dispatch regions are not overlapped. We further investigate the overlapped case and modify the dynamic programming algorithm correspondingly. We provide a discussion on the effect of the overlapping in a spatial case, where the driver and passenger locations are uniformly distributed. Experiments are conducted based on the synthetic dataset and the real-world dataset from Didi Inc. Results show that our approach can effectively reduce the expected driver pickup distance and keep the dispatching time short, which balances both passengers'' and drivers'' interests.

Using a mobile charger to wirelessly charge sensors is a promising yet not well-solved technique. Existing trajectory planning schemes for wireless charger either (1) fail to optimize the one-to-many characteristic of wireless charging or (2) fail to jointly optimize the charger movement cost and the charging cost. The objective of this paper is to find the optimal trajectory planning for a mobile charger in terms of energy minimization in the quadratic attenuation charging model. There exists a trade-off between charging efficiency and trajectory distance. If the mobile charger comes close to sensors, the charging efficiency is high, but the entire charging trajectory of the charger will be long and vice versa. To address this trade-off, we propose the idea of charging bundle and optimize the charger's trajectory based on the charging bundle rather than each sensor. The optimal charging bundle generation problem and the bundle trajectory optimization problem are discussed gradually. Both of them are proven to be NP-hard. Then, we first propose a greedy bundle generation algorithm with an approximation ratio of lnn, where n is the number of sensors. After that, we propose a TSP-based solution and further optimize the TSP-trajectory by jointly considering the adjacent charging locations. Theorems are proposed to effectively find the optimal location. Extensive experiments show that our scheme achieves a much better performance than traditional schemes.

Fog computing is an emerging paradigm that brings the computing capabilities close to distributed IoT devices, which provides networking services between end devices and traditional cloud data centers. One important mission is to further reduce the monetary cost of fog resources while meeting the ever-growing demand of multiple users. In this paper, we focus on minimizing the total cost for multiple mobile users to provide an efficient resource provisioning scheme in fog computing. The total cost includes two aspects: the replication cost and the transmission cost. We consider two cases for the resource provision problem by focusing on different cost models. First, one simple case where users can only upload one replication is discussed, and an optimal solution is proposed by converting the original problem into one of bipartite graph matching. Then we consider a more complicated case that each user can upload multiple replications on fog nodes in the resource provisioning. For different transmission cost models, the transmission cost is related to the distance of each pair of fog nodes. This problem is proven to be NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2/3W+1/3OPT. Another 3+ε-approximation algorithm is proposed based on local search, which has better performance with higher complexity. Extensive simulations also prove the efficiency of our schemes.

With the progress of mobile devices and the successful usage of the wisdom of crowds, spatial crowdsourcing has attracted much attention from the research community. This paper addresses the efficient worker recruitment problem under the task coverage constraint. The efficiency of worker recruitment is measured by the total quality collected by a set of workers and the corresponding cost, e.g., proportional to the overall trajectory length of workers. Specifically, we consider two different scenarios, 1-D line topology and general 2-D topology, in which workers may have either homogeneous or heterogeneous crowdsourcing quality (e.g., the quality of videos or photos for an object at a particular location). In the 1-D scenario, we propose two dynamic programming approaches to find the optimal solution in both homogeneous and heterogeneous cases. In the general 2-D scenario, the proposed problem turns out to be NP-hard even in the homogeneous case. We first prove that the simple nearest assignment has an approximation ratio of 1/(2n), where n is the number of the workers. Therefore, the nearest assignment cannot be scalable. We further propose a novel assignment approach based on the minimum spanning tree. The proposed approach is proved to be close to the optimal solution in the homogeneous case and 1/ρ in the heterogeneous case, where ρ is the maximum quality ratio between two workers. The effectiveness of the proposed algorithm is verified using a real mobility trace: Uber pick-up trace in the New York City.

Motivated by many Online Social Network (OSN)applications such as viral marketing, the Social Influence Maximization Problem (SIMP)has received tremendous attention. SIMP aims to select k initially-influenced seed users to maximize the number of eventually-influenced users. Under the independent cascade model, the SIMP has been proved to be NP-hard, monotone, and submodular. Therefore, a naive greedy algorithm that maximizes the marginal gain obtains an approximation ratio of 1-e-1. This paper extends the SIMP by considering the crowd influence which is combined group influence in additional to individual influence among a given crowd. Our problem is proved to be NP-hard and monotone, but not submodular. It is proved to be inapproximable within a ratio of |V|ε-1for any ε > 0. However, since user connections in OSNs are not random, approximations can be obtained by leveraging the structural properties of OSNs. We prove that the supmodular degree, denoted as Δ. of most OSNs has the following property lim|V|→∞[Δ/O(|V|)] = 0, i.e., Δ ∈ o(|V|) for most OSNs. The supermodularity, denoted by \triangle, is used to measure to what degree our problem violates the submodularity. Two approximation algorithms have been applied with ratios of 1/(Δ+2) and 1-e-1/(Δ+1), respectively. Experiments demonstrate the efficiency and effectiveness of our algorithms.

In cellular traffic offloading through opportunistic mobile networks, existing schemes rely on the assumption that data can be entirely transmitted at each contact. However, transmission probability exponentially decreases as data size increases. That is, the contact duration in each contact might be insufficient for delivering large data. The objective of this paper is to find an optimal traffic offloading scheme through data partitioning so that the data delivery latency is minimized. There is a trade- off in data partitioning. Each small chunk in a path has a higher delivery probability than original data, and consequently, has a shorter delivery latency under the persistent transmission model with re-transmission. However, the destination needs to receive all the chunks in multiple paths to retrieve the data. A delay in any path will lead to a longer delivery latency. We formulate the optimal cellular traffic offloading problem and propose an approach to generate forwarding paths with possible heterogeneous data chunks. Specifically, we discuss the optimal solution for single-hop direct forwarding with multiple offloading helpers and optimal chunk sizes. Then, we propose using the node's social-feature to generate multiple edge-disjoint multi-hop forwarding paths. Extensive experiments on realistic traces show that our scheme achieves a much better performance than those without partitioning.

Recently, fog computing has become a highly virtualized platform that provides computation, storage, and networking services between end devices and traditional cloud data centers. In this paper, we address the resource provision (RP)problem for delay-sensitive users in cooperative fog computing. Our objective is to find a feasible provision scheme that minimizes the total monetary cost proportional to the number of fog nodes for network operators under the deadline and capacity constraints by considering the cooperation of fog nodes. We consider two cases of our RP problem: the Unlimited-Processor Fog Nodes (UPFN)case and the Limited-Processor Fog Nodes (LPFN)case. For the UPFN case, each fog node has unlimited processors. The requests on each fog node can be processed in parallel ideally, i.e. with no scheduling delay. The LPFN case corresponds to a more realistic scenario where the scheduling delay is non-eligible. In either case, our RP problem is proven to be NP-hard. For the UPFN case, we propose two greedy algorithms which iteratively remove fog nodes according to their global or local cooperative influences until there is no feasible provision that can guarantee users' deadlines. For the LPFN case, it is not trivial to check the existence of a feasible provision due to the interactive influence on the scheduling delay for requests. We find a near-optimal solution with bound [8/3]OPT+[(ε2)/(8mα)] using the continuous congestion game and check the feasibility, where m is the number of fog nodes and α is a constant value related to the delay function. Extensive simulations demonstrate the efficiency of our schemes.

Commercial cloud providers, e.g., Amazon EC2, offer the volume discount for large instance reservation in a time slot, and the majority of cloud jobs are delay-tolerant and do not need to be processed intermittently. These two features create an opportunity for the cloud brokerage service which aggregates and schedules cloud users' rental requests to earn volume discounts from cloud providers and sell to cloud users at a cheap price. A challenge for the broker is to properly schedule delay-tolerant jobs in order to maximize the volume discount amount over time. The scheduling idea is to generate several job bundles so each job bundle can get discount. In this paper, we discuss this problem from the homogeneous model first, where each job has the same processing time and delay-tolerant time, and we propose a dynamic programming approach. Then, we extend the model into the heterogeneous model, where the job processing time and the job deadline can be arbitrary values. In the heterogeneous scenario, we prove that the proposed problem is NP-hard even when the job processing time is unit. Then, we propose a greedy approach which turns out to have an approximation of O(lnn), where n is the total job number. Extensive trace-driven experiments from Google cluster trace demonstrates that our schemes achieve good performances.

In opportunistic mobile networks, existing schemes rely on the assumption that data can be entirely transmitted at each contact. However, in an opportunistic mobile network, the transmission probability exponentially decreases as the data size increases. That is, the contact duration in each contact might be insufficient to deliver large data. Therefore, it is reasonable to partition original data into small data chunks and each chunk is forwarded through an opportunistic path. The objective of this paper is to find an optimal data partition strategy where the data delivery ratio is maximized under a given deadline. There is a trade-off in data partitioning. Each small chunk in a path has a higher delivery probability than the original data, and consequently, a shorter delivery latency under the persistent transmission model with re-transmission. However, the destination needs to receive all chunks in multiple paths (a path is a sequence of contacts) to retrieve the data. A delay in any path will lead to a longer delivery latency. We formulate the data partitioning problem and propose solutions in blind flooding. In the blind flooding scenario, we find the optimal data partitioning size. Network coding technique is used to the proposed method to further improve the performance. Extensive experiments on realistic traces show that our scheme achieves a much better performance than those without partitioning.

To improve the user experience in multi-party online applications, i.e., low gaming lag in online gaming, the maximum latency between any pair of users should be minimized. Considering the multiple preferences of users, i.e., which group a user can join, we address the User Latency Minimization (ULM) problem by performing an optimal matchmaking. This paper proves that the ULM problem is NP-hard if users have more than two preferences. We prove that the ULM problem has the sub-modular property and we apply the classic greedy algorithm with an approximation ratio of 1+ n, where n is the number of users with multiple preferences. Furthermore, we observe that a matchmaking priority for users in different locations exists and thus we propose a revised greedy algorithm with an approximation bound and discuss its performance in the tree structure and the general structure. Specifically, the revised greedy algorithm achieves an approximation ratio of m/2 with lower complexity in the tree structure, where m is the number of preferences in the general structure. Finally, we develop a disstributed greedy approach which converges quickly. Extensive trace-driven experiments from Internet measurements demonstrates that our schemes achieve good performances.

Considering the heterogeneous subscriptions of the subscribers in the content-based publish/subscribe (pub/sub) system, the subscription aggregation technique is used to optimize the system performance, e.g., reducing the routing table, simplifying the matching procedure. However, introducing this technique also has disadvantages. If some subscribers leave the network, the brokers which aggregate subscriptions should re-configure the subscription aggregation strategy with its descendants. During this period false-positive publications, which are no longer needed by subscribers, are still propagated into the network. Therefore, it becomes paramount to examine the issue of how to conserve network resources through subscription aggregation, while simultaneously minimizing the false positive publication propagation. In this paper, we first prove the above problem is NP-hard. Then, we provide the dynamic programming approach when the re-configuration delay can be regarded as constant time. In the general case, we propose a greedy algorithm, and the corresponding performance bound is analyzed. Finally, we propose an overlay construction scheme to further fit the subscription aggregation. Extensive experimental results show that proposed algorithms achieve a good performance.

The increasing traffic demand has become a serious concern for cellular networks. To solve the traffic explosion problem in a vehicular network environment, there have been many efforts to offload the traffic from cellular links to Roadside Units (RSUs). Compared with the cost of downloading from cellular link, downloading through RSUs is considered practically free. In most cases, we have to wait for one or several RSUs to download the entire data, which causing huge delays. However, people can always download data from the cellular network. In reality, people are sensitive to the downloading delay but would like to pay little money for downloading the data. As the result, there exists a delay-cost trade-off. In this paper, we unify the downloading cost and downloading delay as the user's satisfaction. The objective of this paper is to maximize the user's satisfaction. A user will be unsatisfied if they are paying too much for data, or if they wait for a long time. We analyze the optimal solution under the condition that the encountering time between vehicles and RSUs follows the exponential and Gaussian distributions. Generally, we propose an adaptive algorithm. A downloading strategy is made based on the historical encountering situation between the vehicle and multiple RSUs. After a period of time, if the real situation is different with the initial prediction, the data downloading strategy will be correspondingly adjusted. Extensive real-trace driven experiment results show that our algorithm achieves a good performance.

The topic-based mobile publish/subscribe (pub/sub) system has shown the potential applications in many scenarios, e.g., product coupon distribution. In this paper, we focus on the budget-constrained data dissemination services with a pre-determinated total amount of copy. A mobile user may subscribe data under different topics, but receiving a copy in any topic is enough. This is the mutually exclusive delivery requirement in many scenarios. In light of the different amounts of data and the different popularity levels of data in each topic, deciding which data should be forwarded to mobile users becomes an important problem. This paper aims to design an efficient data dissemination scheme in the aforementioned scenario, which minimizes the maximum dissemination delay, and incurs small communication overhead at the same time. We start with the offline message dissemination problem, and the corresponding optimal solution is proposed. Later, we consider the online situation, and propose a distributed data forwarding algorithm, which considers both the amount of data in different topics, mobile users' subscription, and their data forwarding abilities, respectively. The real trace driven experiments show that the proposed scheme achieves a good performance.

This paper considers underwater wireless sensor networks (UWSNs) for surveillance and monitoring. Sensors are distributed in several key sections along the seafloor to record the surrounding environment, for example, monitoring oil pipelines and submarine volcanoes. Due to the need for timely data reporting and the fact that underwater communications suffer from a significant signal attenuation, homogeneous autonomous underwater vehicles (AUVs) are sent to retrieve information from the sensors, and periodically surface to report the collected data to the sink. In this paper, considering the huge energy consumption of surfacing and diving, our objective is to determine a trajectory schedule for the AUVs so that the total amount of surfacing for all the AUVs are minimized, and the data is reported to sink within the deadline. We first investigate the influence of different movement directions of AUVs, and provide the optimal solution to minimize the amount of surfacing for multiple AUVs within the same sensor section. Then, we propose a greedy detouring scheme to collaboratively schedule the AUVs in adjacent sensor sections. Extensive experiments show that our trajectory scheduling improves performance significantly.

In this paper, a general data and acknowledgement dissemination mechanism is proposed in mobile social networks (MSNs). Most existing dissemination schemes in MSNs only consider data transmission. However, receiving acknowledgement has many potential applications in MSNs (e.g., mobile trade and incentive mechanism). Challenging problems thus arise due to this type of mixed messages (i.e., data and acknowledgement) dissemination problem. The buffer constraint and time constraint for data and acknowledgement make this problem even harder to handle in a practical scenario. In order to maximize the research objective (e.g., low delay and high delivery ratio), we have to identify the priority of each message in the network. We propose a general priority-based compare-split routing scheme to solve the above buffer exchange problem. During each contact opportunity, first, nodes compare their abilities to send data and acknowledgements based on two types of criteria. They are the contact probability and the social status, which estimate the nodes' direct and indirect relationship with destinations respectively. Nodes then decide which message to exchange, and thus maximize the combined probability. Second, an adaptive priority-based exchange scheme is proposed within each type of message, and so is the relative priority between two types of messages, as to decide the order of exchange. The message with a high priority will be forwarded first, and thus maximize the research objectives. The effectiveness of our scheme is verified through the extensive simulations in synthetic and real traces.