This paper analyzes a non-isolated bidirectional converter with hand-in-hand fractional-stage conversion for battery storage applications. This converter contains two partial power conversion units. Each unit consists of a non-isolated converter, and its output port is serially connected to a set of batteries. Meanwhile, the two series-connected partial power conversion units are connected in parallel. In this configuration, the batteries of one unit are operated as the source of the converter in the other unit, forming a hand-in-hand structure that enables mutual support for correct operation. Due to the unique series-parallel connection of the converter, partial power conversion is achieved using simple non-isolated converters, making the converter feature high efficiency and high power density. Moreover, the special structure of the analyzed converter endows it with the ability to regulate the voltage and current and manage the battery energy through the coordinated operation of the two non-isolated converters. To demonstrate the effectiveness and correctness of the converter, the simulation and experimental verification results are presented in this paper.

In this paper, we consider the large-scale Area Under the Precision-Recall Curve (AUPRC) maximization problem for the imbalanced data classification task. Existing optimization methods for AUPRC maximization only focus on the single-machine setting, which are not applicable to the distributed data. To address this problem, we propose a novel decentralized stochastic compositional gradient descent method for large-scale AUPRC maximization. Our theoretical analysis shows that it can achieve a better sample complexity 𝒪 (1/ϵ4) than 𝒪 (1/ϵ6) of existing decentralized methods, but has the same communication complexity 𝒪 (1/ϵ4). To further reduce the communication cost, we developed a novel communication-efficient decentralized stochastic compositional gradient descent method, whose communication complexity is improved to 𝒪 (1/ϵ4–4α) (where α ∈ (0,1/4)). To the best of our knowledge, this is the first work achieving such favorable sample and communication complexities. Finally, we conduct extensive experiments for imbalanced data classification and the empirical results confirm the superior performance of our proposed methods.

Deep Neural Networks (DNNs) have been widely deployed in mobile applications. DNN inference latency is a critical metric to measure the service quality of those applications. Collaborative inference is a promising approach for latency optimization, where partial inference workloads are offloaded from mobile devices to cloud servers. Model partition problems for collaborative inference have been well studied. However, little attention has been paid to optimizing offloading pipeline for multiple DNN inference jobs. In practice, mobile devices usually need to process multiple DNN inference jobs simultaneously. We propose to jointly optimize the DNN partitioning and pipeline scheduling for multiple inference jobs. We theoretically analyze the optimal scheduling conditions for homogeneous chain-structure DNNs. Based on the analysis, we proposed near-optimal partitioning and scheduling methods for chain-structure DNNs. We also extend those methods for general-structure DNNs. In addition, we extend our problem scenario to handle heterogeneous DNN inference jobs. A layer-level scheduling algorithm is proposed. Theoretical analyses show that our proposed method is optimal when computation graphs are tree-structure. Our joint optimization methods are evaluated in a real-world testbed. Experiment results show that our methods can significantly reduce the overall inference latency of multiple inference jobs compared to partition-only or schedule-only approaches.

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.

Sizes of data processing jobs in cloud clusters have been growing rapidly in the big data era. It is critical to execute those jobs efficiently. The average job completion time (JCT) is a widely used metric to measure executing efficiency. JCT refers to the length of the time interval between a job's arrival to its completion. Typically, a data processing job contains multiple stages with complex precedence constraints. Carefully scheduling the processing sequence of stages within a job may significantly reduce its JCT. Our objective is to minimize the average JCT for online arrival jobs. The computation graphs of those jobs are usually directed acyclic graphs (DAGs). It makes the scheduling problem challenging. Recent works have shown that reinforcement learning (RL) agents can adaptively adjust the scheduling policies by dynamically assigning priorities for job stages. However, we notice that other factors besides stage priories may impact the JCT significantly. In particular, we observe that inserting idle slots before large jobs may reduce the waiting time of small jobs that arrive slightly later and reduce the average JCT. We analyze the benefits of inserting idle time for simple cases theoretically and show the condition in which idle slots should be inserted for two adjacent jobs. In addition, we adapt the RL-based scheduler by integrating the observation. Experiment results on both real-world and synthetic datasets show the efficiency of our scheduler. Also, a perturbation-based method is applied to demonstrate the contribution of each proposed feature.

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.

Deep Neural Network (DNN) models have been widely deployed in a variety of applications. Driven by privacy concerns and great improvement in the computational power of mobile devices, the idea of training machine learning models on mobile devices has become more and more important. Directly applying parallel training frameworks designed for data center networks to train DNN models on mobile devices may not achieve the ideal performance, since mobile devices usually have multiple types of computation resources such as ASIC, neural engine, and FPGA. Moreover, the communication time is not negligible when training on mobile devices. With the objective of minimizing DNN training time, we propose to extend the pipeline parallelism, which can hide the communication time behind computation for DNN training by integrating the resource allocation. Fine-tuning the ratio of resources allocated to forward and backward propagation can improve resource utilization. We focus on homogeneous workers and theoretically analyze the ideal cases where resources are linearly separable. We also discuss the model partition and resource allocation for a more realistic case. Additionally, we investigate the heterogeneous worker case. Trace-based simulation results show that our scheme can efficiently reduce the time cost of a training iteration.

Bike-sharing systems usually suffer from out-of-service events due to bike underflow or overflow. We propose to recruit workers to rebalance station loads. We partition the complex rebalancing problem in temporal and spatial domains. The temporal domain is divided into a sequence of slices with a fixed duration. In each slice, we allocate a pair of overflow/underflow stations to a worker such that the cost is minimized, which is NP-hard. A 3-approximation algorithm is proposed. We further investigate the worker shortage case and extend the matching algorithm to consider the number of unsatisfied users. Then, the configuration dynamic in the sequence of slices is captured by determining the rebalancing target for each rebalancing operation. We investigate heuristic approaches to minimize the total number of bike movements. Furthermore, we extend our scheme to dockless BSSs using clustering techniques. We simulate our algorithms on both real-world and synthetic datasets. Experiment results show that our approaches can reduce the average total detour per slice. In worker shortage, considering the number of unsatisfied users could improve the long-term performance of rebalancing. Besides, we find that our scheme could maintain worker satisfaction over multiple time slices, which indicates the sustainability of our rebalancing scheme.

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.

Reducing the inference time of Deep Neural Networks (DNNs) is critical when running time sensitive applications on mobile devices. Existing research has shown that partitioning a DNN and offloading a part of its computation to cloud servers can reduce the inference time. The single DNN partition problem has been extensively investigated recently. However, in real-world applications, a mobile device usually generates multiple DNN inference jobs simultaneously, and little attention has been paid to this case. We aim to minimize the makespan of multiple DNNs by jointly optimizing their partitioning and scheduling. Our observations show that the local computation time on a mobile device follows an increasing function, while the communication workload for offloading is usually decreasing as more DNN layers are computed. Based on this, we first relax our problem on continuous domain and show that partitioning all line-structure DNNs at the same layer is sufficient for makespan optimization. Then, for the discrete domain, two types of partitions are sufficient when the time difference between two adjacent partition layers is not drastic, subject to a given condition. An algorithm based on the binary search that efficiently finds optimal partition layers is illustrated. We also extend our approach to general-structure DNNs and offer a heuristic solution. Experiments have been conducted to evaluate the performance of different partition and scheduling methods on sample DNNs. Results validate the optimality of our theoretical results.

The quality of service (QoS) of intelligent applications on mobile devices heavily depends on the inference speed of Deep Neural Network (DNN) models. Cooperative DNN inference has become an efficient way to reduce inference latency. In cooperative inference, a mobile device offloads a part of its inference task to cloud servers. The large communication volume usually is the bottleneck of such systems. Priory research focuses on reducing the communication volume by finding optimal partition points. We notice that the computation and communication resources on mobile devices can work in pipeline, which can hide the communication time behind computation and further reduce the inference latency. Based on the observation, we formulate the offloading pipeline scheduling problem. We aim to find the optimal sequence of DNN execution and offloading for mobile devices such that the inference latency is minimized. If we use a directed acyclic graph (DAG) to model a DNN, the complex precedence constraints in DAGs bring challenges to our problem. Notice that most DNN models have independent paths or tree structures, we present an optimal path-wise DAG scheduler and an optimal layer-wise scheduler for tree-structure DAGs. Then, we proposed a heuristic based on topological sort to schedule general-structure DAGs. The prototype of our offloading scheme is implemented on a real-world testbed, where we use Raspberry Pi as the mobile device and lab PCs as the cloud. Various DNN models are tested and our scheme can reduce their inference latencies in different network environments.

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.

Lots of privacy and security issues in the current cloud-based data markets will be eliminated by taking advantage of blockchain-based decentralized storage services, which can provide a new paradigm for safe data outsourcing and correct remote search. However, existing data markets are also questioned on their inflexible and opaque pricing, where the value of data ownership and the cost of query search are mixed. Thus, a better pricing model is necessarily needed in an emerging decentralized data market. In this paper, we envision an Ethereum-based data market, in which the pricing model for each query includes two parties: owner (paid for his data ownership) and miner (rewarded by query search). We study a new cooperative search scheme through a proxy to reduce cost on the client (user) side. Suppose each user query is charged based on the number of keywords in the query. The cost reduction is based on combining multiple queries into a group subject to the constraint that the resulting combined query is not significantly larger than any of its original query in terms of the number of keywords. The total price is based on total number of keywords in all groups. As the optimal grouping depends on the pricing of both owner and miner, we build a small testbed to analyze how price setting will affect grouping results. Since it is a cooperative model with shared resources, we also study various incentive properties on the client side, thereby yielding a cost sharing mechanism to split joint cost in a truth-revealing and fair manner.

User dynamics in both spatial and temporal domains bring uncertainty to bike-sharing systems (BSSs) and usually lead to bike imbalance. This may generate out-of-service events due to bike underflow or overflow, at a bike station. In this paper, we recruit workers through crowdsourcing to rebalance loads among bike stations. We assume that workers have their individual sources and destinations, and assign them to move bikes from overflow stations to underflow stations. We partition the complex spatial and temporal problem into a sequence of slices with a fixed duration in the temporal domain. In each slice, we focus on the spatial domain and allocate a pair of overflow/underflow stations to a worker such that the summation of detour cost among workers is minimized. The hardness of finding the min-cost allocation is shown by a reduction from a 3-dimensional matching problem (i.e., matching among workers, overflow stations, and underflow stations). We propose a 3-approximation algorithm for the problem when the detour cost is proportional to the detour distances. Then, the configuration dynamic in the sequence of slices is captured by carefully determining the rebalancing frequency and target for each rebalancing operation. We investigate heuristic approaches to decide rebalancing frequencies and targets over a sequence of slices in order to minimize the total number of bike movements (i.e., the total number of workers), and hence to derive the average total detours per slice. We simulate our algorithms on both real-world and synthetic datasets based on different time-slice granularities. The experiment results show that our approaches can reduce the average total detour per slice.

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.

The ride-hailing system has become popular around the world. The Service Providers (SPs) such as Uber and Didi dispatch passenger orders based on their location information. However, one concern from the public is whether the SPs could protect the location privacy of passengers. In this paper, we propose an order dispatch scheme that could preserve the location privacy of passengers based on their requirements. Our scheme uses cloaking regions in which the SPs cannot distinguish actual locations of passengers. The trade-off is the loss of matching performance or social welfare, i.e., the increase in the overall pick-up distance. We formulate the problem as maximizing the social welfare (or minimizing the overall pick-up distances) under privacy requirements of passengers. A bipartite-matching-based scheme is investigated, and we provide a theoretical bound on the matching performance under specific privacy requirements. Nevertheless, minimizing the overall pick-up distances does not consider the interest of each individual passenger. Passengers with low privacy requirements may be matched with drivers far from them. Therefore, we further propose a pricing scheme that could make up for the individual loss by allocating discounts on their riding fares. Especially, three discount allocation strategies are proposed in this paper. Experiments on both real-world and synthetic datasets show the efficiency of our scheme.

Recently, the development of Bike Sharing Systems (BSSs) brings environmental and economic benefits to the public. However, BSSs frequently suffer from the imbalanced bike distribution, including dock-less BSSs. The underflow or overflow of bikes in a region may lead to a lower service level to BSSs or congestion to the city. In the paper, we consider rebalancing the dock-less BSS by providing users with monetary incentives. The long-term objective is to maximize the number of satisfied users who successfully complete their rides over a period of time. The operator of the dock-less BSS can not only encourage a user to rent bikes at the neighborhood of its source with a source incentive, but also incentivize them to return bikes at the neighborhood of its destination with a destination incentive. To learn the differentiated incentive price for rebalancing bikes across time and space, we extend a novel deep reinforcement learning framework for user incentive. The source and destination incentives are integrated in an adaptive way by adjusting the detour level at the source and/or destination by avoiding bike underflow and overflow. In the experiment, we evaluate our approach in comparison with two existing pricing schemes. The locations of sources and destinations are abstracted from a selected dataset from Mobike. The experiment results show that our adapted learning algorithm outperforms the original one that only considers source incentive as well as another state-of-the-art approach in maximizing the long-term number of satisfied users.

With the bloom of the sharing economy, bike sharing systems have earned increasing attention, and a great amount of bike sharing systems have been established in major cities. Users of these systems mainly conduct one-way trips, which leads to an unbalanced distribution of the bikes over time and space. The system operators could hire a fleet of vehicles to move bikes among bike stations for rebalancing. We focus on a routing schedule problem for each vehicle used in the rebalancing process and aims to minimize its moving distance. For the problem, we propose a greedy algorithm which can be easily extended to a parallel version. The scheduled route for a vehicle is adapted from the Hamiltonian path covering all unbalanced bike stations. The algorithm greedily adjusts the route if the vehicle cannot moving along the Hamiltonian path due to capacity limitation violation. Different from previous approaches, our algorithm has a more flexible tradeoff between running time consumption and optimality of the output. Finally, we conduct experiments on both real-world and synthetic datasets and compare the performance of our algorithm with a classic approach.

The rapidly increasing number of vehicles in roads leads to numerous problems in metropolitan areas. Several researchers show that carpooling can be an efficient solution to relieve the pressures caused by large numbers of cars. Previous research on carpools introduces several additional constraints to simplify the problem, but some of them are unreasonable in reality. In this paper, we focus on removing the static capacity constraint. Doing so allows a vehicle to carry more passengers than vehicle's capacity, which is possible if some people are dropped off and new passengers take their places during the journey. A greedy approach based on multi-round matching is proposed, and it is further improved by taking advantage of geometry properties. We apply our algorithms to both simulated and real world datasets, and experiment results show that our algorithms have better performances than existing approaches.

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.