Search

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.

Due to the additive property of most machine learning objective functions, the training can be distributed to multiple machines. Distributed machine learning is an efficient way to deal with the rapid growth of data volume at the cost of extra inter-machine communication. One common implementation is the parameter server system which contains two types of nodes: worker nodes, which are used for calculating updates, and server nodes, which are used for maintaining parameters. We observe that inefficient communication between workers and servers may slow down the system. Therefore, we propose a graph partition problem to partition data among workers and parameters among servers such that the total training time is minimized. Our problem is NP-Complete. We investigate a two-step heuristic approach that first partitions data, and then partitions parameters. We consider the trade-off between partition time and the saving in training time. Besides, we adopt a multilevel graph partition approach to fit the bipartite graph partitioning. We implement both approaches based on an open-source parameter server platform—PS-lite. Experiment results on synthetic and real-world datasets show that both approaches could significantly improve the communication efficiency up to 14 times compared with the random partition.

Fog computing is an emerging paradigm that brings computing capabilities closer 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 demands 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 three 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 a bipartite graph matching. Then we consider a more complicated case in which each user can upload multiple replications on fog nodes in the resource provisioning. Specifically, two models are discussed: the 0–1 transmission cost model and the different transmission cost model. For the 0–1 transmission cost model, each user can upload multiple replications with a constant transmission cost, and one optimal greedy solution is proposed. For the different transmission cost model, 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 3 W + 1 3 O P T . 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 quick development of the sharing economy, ride-hailing services have been increasingly popular worldwide. Although the service provides convenience for users, one concern from the public is whether the location privacy of passengers would be protected. Service providers (SPs) such as Didi and Uber need to acquire passenger and driver locations before they could successfully dispatch passenger orders. To protect passengers’ privacy based on their requirements, we propose a cloaking region based order dispatch scheme. In our scheme, a passenger sends the SP a cloaking region in which his/her actual location is not distinguishable. The trade-off of the enhanced privacy is the loss of social welfare, i.e., the increase in the overall pick-up distance. To optimize our scheme, we propose to maximize the social welfare under passengers’ privacy requirements. We investigate a bipartite matching based approach. A theoretical bound on the matching performance under specific privacy requirements is shown. Besides passengers’ privacy, we allow drivers to set up their maximum pick-up distance in our extended scheme. The extended scheme could be applied when the number of drivers exceeds the number of passengers. Nevertheless, the global matching based scheme does not consider the interest of each individual passenger. The passengers with low privacy requirements may be matched with drivers far from them. To this end, a pricing scheme including three strategies is proposed to make up for the individual loss by allocating discounts on their riding fares. Extensive experiments on both real-world and synthetic datasets show the efficiency of our scheme.

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.

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.

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.

Nowadays, large cities face numerous problems caused by the rapidly increasing number of vehicles on road. Carpooling has been shown as an efficient solution to ease the traffic pressure. The objec...