Many real-world systems can be modeled as graphs, where nodes store and consume entities, actively produce them, or have them emerge naturally, and edges transport them between nodes. This paper studies the networked control problem on such large-scale systems, aiming to decide production and transportation over time to maximize long-term profits, subject to node or edge capacity constraints. Existing SOTAs either fail to guarantee feasibility or cannot scale to large-scale systems. We propose a two-stage policy that integrates a constrained optimization layer after a neural network to explicitly enforce constraints and ensure feasibility. By leveraging the problem structure to obtain expert actions and designing a decision-focused and differentiable loss to enable imitation learning, our method significantly improves efficiency and scalability. In small-scale systems with action dimensions in the order of 10, our method achieves 60x sample efficiency over SOTAs on average. In large-scale systems with action dimensions ranging from 100 to 100000, where SOTAs fail to train, our method converges quickly and outperforms non-learning-based baselines significantly.

Space Situational Awareness (SSA) relies on Low Earth Orbit (LEO) satellites to capture continuous, highresolution imagery critical for identifying space threats. The vast volume of SSA images overwhelms satellite network throughput, hindering timely transmission and processing. This paper presents a reinforcement learning (RL)-driven distributed sparse coding framework that integrates novel compression algorithms with orbital RL to address these challenges. First, we introduce an Aggregated Dictionary Learning (ADL) algorithm and a Context-aware Adaptive Binary Arithmetic Coding (CABAC) algorithm, achieving a 93.78% compression ratio by exploiting the high sparsity and spatiotemporal redundancy of SSA images. Second, the proposed compression workflow is deployed across LEO satellites in a distributed manner, where both overlapping and non-overlapping regions of images are dynamically partitioned and processed in parallel to optimize resource utilization and reduce latency. An Orbital Double Deep Q-Network (DQN) framework is proposed to optimize task offloading decisions by (1) integrating orbital dynamics into the state space, and (2) adaptively partitioning images based on visible LEO resources. Evaluations demonstrate that our framework achieves 100% task completion under visibility constraints and a 51.61% reduction on CPU and RAM occupation time compared to centralized processing.

Robotic swarm coordination holds transformative potential for applications such as warehouse automation, search & rescue, and entertainment. However, approaches relying on wearable devices or vision-based systems are often constrained by hardware-intensive, high computational requirements, reliance on line-of-sight, and privacy concerns. Wireless sensing, particularly using Channel State Information (CSI), offers a promising alternative by translating environmental perturbations into CSI variation data. Nevertheless, existing CSI-based systems face significant challenges in domain adaptation, resource limitation, and scalability issues. This paper introduces MaestroBot, a hierarchical motion coordination system that combines distributed CSI-based wireless sensing with domain-adaptive learning to address these limitations. For leader robots, the system features a lightweight hand gesture recognition model, built on a “Hybrid-Single” knowledge distillation framework, achieving up to 95.87% accuracy while maintaining adaptability across diverse domains. For follower robots, the hierarchical motion propagation model leverages localized CSI analysis and dual-layer error correction mechanisms to deliver 97.2% accuracy with a low latency of 0.085 seconds, even in multi-row formations. Additionally, its cost-effective hardware design ensures practical scalability and real-world deployability. These results position MaestroBot as an efficient, robust, and privacy-preserving solution for large-scale robotic swarm coordination in dynamic environments.

Tiny cameras are ubiquitous in embedded devices like smart glasses and drones. On-device learning technique empowers these resource-constrained devices to adapt to changing environments locally. However, existing camera modules rely on diverse programming environments and APIs. This heterogeneity impedes the validation and deployment of practical on-device learning algorithms. In this work, we introduce CamOL, the first full-stack on-device learning scheme for heterogeneous tiny cameras. CamOL integrates a complete workflow encompassing preprocessing, learning, inference, and visualization. For learning, CamOL adopts a library-free code design for maximum portability and programmability, and incorporates a proposed staged training method for efficient full-parameter fine-tuning. For inferring, we have developed a suite of operators and achieved operator fusion for minimal latency. We demonstrate CamOL with a compact, low-cost (<$10) prototype that features an engaging and interactive visualization. This allows participants to intuitively experience the entire on-device learning pipeline for different applications in real-time. Moreover, CamOL can also serve as a handy testbed for embedded vision intelligence.

This paper presents Serafin, the first full-stack, sub-mW, and versatile Bluetooth-enabled RF sensor that brings transparent RF sensing to any mobile and IoT device: it independently conducts the whole RF sensing process from RF signal reception to sensing result computation in a wide variety of sensing tasks with only negligible power consumption. At the core of Serafin are our two designs that address the challenge posed by the stringent sub-mW power constraint to jointly achieving versatility and full stackness. Specifically, (i) we utilize the ambient Bluetooth advertising signal as the signal for sensing, and extract the phase difference of the sensing signals received by each antenna pair from the amplitude of their sum signal, which avoids power-hungry hardware components and intensive computation, and (ii) we employ low-power MCU as the computation hardware, and suppress its power consumption by activating it adaptively only when necessary and customizing a light-weight neural network model that still ensures satisfactory inference accuracy. Our extensive experiments on 6 representative sensing tasks show that Serafin achieves competitive sensing performance, but consumes only around 500–900μW power, which is 3–4 orders of magnitude lower than those of existing full-stack and versatile counterparts.

This paper demonstrates Serafin, the first full-stack, sub-mW, and versatile Bluetooth-enabled RF sensor that brings transparent RF sensing to mobile and IoT device: it independently conducts the whole RF sensing process from RF signal reception to sensing result computation in a wide variety of sensing tasks with only negligible power consumption. At the core of Serafin are our two designs that address the challenge posed by the stringent sub-mW power constraint to jointly achieving versatility and full stackness. Specifically, (i) we utilize the ambient Bluetooth advertising signal as the signal for sensing, and extract the phase difference of the sensing signals received by each antenna pair from the amplitude of their sum signal, which avoids power-hungry hardware components and intensive computation, and (ii) we employ low-power MCU as the computation hardware, and suppress its power consumption by activating it only when necessary and customizing a light-weight yet versatile neural network model.

With the development of quantum blockchain, the quantum consensus protocols have garnered increasing attention, which play a crucial role in driving the implementation of quantum blockchains. However, existing protocols, derived from the classical consensus algorithms, face practical application challenges due to current quantum technology limitations. The first challenge is the bottleneck in generating large-scale entangled quantum states. The second challenge arises from the generation of malicious quantum states. The final challenge involves privacy concerns. To address these challenges, we propose a practical iterative QUantum consensus protocol with sharding construction, namely, Q-Union. In fact, Q-Union employs an iterative consensus algorithm where participating nodes are divided into multiple smaller shards, with the consensus process occurring within the current shard, and new shards are involved only if consensus is not achieved. Leveraging Greenberger-Horne- Zeilinge states and Aharonov states, Q-Union harnesses the advantages of quantum mechanics to achieve anonymous consensus, protecting the private information of participating nodes. Additionally, by integrating state verification, Q-Union ensures the correctness of the consensus procedure in the presence of malicious nodes generating adversarial quantum states. Finally, it is proven that Q-Union can also defend against Byzantine attacks from adversarial nodes, maintaining the same security level as traditional non-sharded consensus protocols. Specifically, it consistently outputs the correct consensus when the fraction of adversaries among participating nodes is less than 1/2 with synchronous communication. Both the theoretical analysis and performance illustration demonstrate the superior performance of the proposed Q-Union compared to state-of-the-art protocols.

The best arm identification problem in multi-armed bandit model has been widely applied into many practical applications, such as spectrum sensing, online advertising, and cloud computing. Although lots of works have been devoted into this area, most of them do not consider the cost of pulling actions, i.e., a player has to pay some cost when she pulls an arm. Motivated by this, we study a ratio-based best arm identification problem, where each arm is associated with a random reward as well as a random cost. For any \(\delta\in(0,1)\) , with probability at least \(1-\delta\) , the player aims to find the arm with the largest ratio of expected reward to expected cost using as few samplings as possible. Specifically, we consider two settings: (1) the precise setting, i.e., identifying the precise optimal one; (2) the Probably Approximate Correct (PAC) setting, which identifies the \(\epsilon\) -optimal one. For the precise setting, we design the elimination-type algorithms and provide a fundamental lower bound which asymptotically matches the upper bound, while in the PAC setting, an UCB-type algorithm which amed \(\epsilon\) -RCB algorithm is proposed. We show that for all algorithms, the sample complexities, i.e., the pulling times for all arms, grow logarithmically as \(\frac{1}{\delta}\) increases. Moreover, compared to existing works, the running of our algorithms is independent of the arm-related parameters, which is more practical. Finally, we validate our theoretical results through numerical experiments.

Harnessing the benefits of blockchain, such as decentralization, immutability, and transparency, to bolster the credibility and security attributes of federated learning (FL) has garnered increasing attention. However, blockchain-enabled FL (BFL) still faces several challenges. The primary and most significant issue arises from its essential but slow validation procedure, which selects high-quality local models by recruiting distributed validators. The second issue stems from its incentive mechanism under the transparent nature of blockchain, increasing the risk of privacy breaches regarding workers’ cost information. The final challenge involves data eavesdropping from shared local models. To address these significant obstacles, this paper proposes a Blockchain-enabled Incentivized and Secure Federated Learning (BIT-FL) framework. BIT-FL leverages a novel loop-based sharded consensus algorithm to accelerate the validation procedure, ensuring the same security as non-sharded consensus protocols. It consistently outputs the correct local model selection when the fraction of adversaries among validators is less than$1/2$with synchronous communication. Furthermore, BIT-FL integrates a randomized incentive procedure, attracting more participants while guaranteeing the privacy of their cost information through meticulous worker selection probability design. Finally, by adding artificial Gaussian noise to local models, it ensures the privacy of trainers’ local models. With the careful design of Gaussian noise, the excess empirical risk of BIT-FL is upper-bounded by$\mathcal {O}(\frac{\ln n_{\min}}{ n_{\min}^{3/2}}+\frac{\ln n}{n})$, where$n$represents the size of the union dataset, and$n_{{\min}}$represents the size of the smallest dataset. Our extensive experiments demonstrate that BIT-FL exhibits efficiency, robustness, and high accuracy for both classification and regression tasks.

Due to the progress in computer hardware and network technologies, federated learning (FL), a decentralized training method in machine learning, has garnered widespread attention. In this approach, individuals share local model parameters rather than raw training data to protect their privacy. However, the inherent heterogeneity of practical computing devices poses challenges to the efficiency and performance of FL. In this paper, we explore the landscape of heterogeneous FL frameworks and introduce ChronusFed, a reinforCement-based adaptive partial training method for heterogeneous Federated learning. ChronusFed employs a dynamic epoch adjustment mechanism (DEA) and a customizable partial training framework (CPT) to optimize model training efficiency. By integrating DEA and CPT, ChronusFed effectively tackles the straggler issues that arise from limited hardware resources, while simultaneously enhancing the model performance. More specifically, DEA leverages deep reinforcement learning (DRL) to model the current state of the global model and determine optimal local training epochs, while CPT utilizes our proposed maximum coverage algorithm to handle device heterogeneity and accelerate model convergence. Theoretical analysis of training convergence validates the effectiveness of ChronusFed, and comprehensive experimental evaluations demonstrate that ChronusFed outperforms state-of-the-art methods across various learning tasks, showcasing its robustness and superiority in heterogeneous FL scenarios.

Fast and accurate sand trash detection and localization is extremely important for trash cleaning, and at present, it still mainly depends on sanitation workers to carry out manual detection. Existing computer vision-based methods cannot detect the shallowly-buried trash. Besides, it is difficult and costly to use ground penetrating radar to detect. To overcome these limitations, we design and implement a novel detection system for shallowly buried trash in sandy land, which integrates the commercial IR-UWB radar into the intelligent unmanned vehicle. By controlling the movement of the vehicle, the radar scans the targeted sandy land and synthesizes the signal into the radar heat-map to detect and locate the shallowly buried trash. Experimental results show that the detection accuracy of the system reaches 92.3% with the radar is 75cm from the ground and the angle perpendicular to the ground is 20°. In the direction parallel to the ground, the farthest trash can be detected is 4.2m away from the radar. Within the range of 4.5m2, it can detect and locate up to 9 trash at the same time.

Achieving optimal order dispatching has been a long-standing challenge for online ride-hailing platforms. Early methods would make shortsighted matchings as they only consider order prices alone as the edge weights in the driver-order bipartite graph, thus harming the platform's revenue. To address this problem, recent works evaluate the value of the order's destination region to be the long-term income a driver could obtain in average in such region and incorporate it into the order's edge weight to influence the matching results. However, they often result in insufficient driver supplies in many regions, as the values evaluated in different regions vary greatly, mainly because the impact of one region's value on the future number of drivers and revenue in other regions is overlooked. This paper models such impact within a cooperative Markov game, which involves each value's impact over the platform's revenue with the goal to find the optimal region values for revenue maximization. To solve this game, our work proposes a novelgoal-reaching collaboration (GRC) algorithm that realizes credit assignment from a novel goal-reaching perspective, addressing the difficulty for accurate credit assignment with large-scale agents of previous methods and resolving the conflict between credit assignment and offline reinforcement learning. Specifically, during training, GRC predicts the city's future state through an environment model and utilizes a scoring model to rate the predicted states to judge their levels of profitability, where high-scoring states are regarded as the goal states. Then, the policies in the game are updated to promote the city to stay in the goal states for as long as possible. To evaluate GRC, we deploy a baseline policy online in several cities for three weeks to collect real-world dataset. Training and testing results on the collected dataset indicate that our GRC consistently outperforms the baselines in different cities and peak periods.

Nowadays, unmanned aerial vehicles (UAVs) are widely applied in crowd sensing. For UAV-enabled crowd sensing (UAVCS) systems, the sensing outcome and charging cost are two primary concerns. To achieve a satisfactory sensing outcome under the charging budget, we exploit joint moving, sensing, and charging scheduling of UAVs, as they all have critical impacts on such two objectives. However, the dynamically generated sensing targets and the variety of sensing tasks a UAVCS system may face make farsighted scheduling of UAVs rather challenging. To this end, we propose a novel multi-task constrained multi-agent reinforcement learning (MARL) method to help UAVs make distributed moving, sensing, and charging decisions. Specifically, we design a multi-task MARL framework to learn a single generic policy for a large collection of tasks, and propose a primal-dual training algorithm that alternates between improving the overall sensing outcome and reducing each task's constraint violation. Theoretically, we show that our algorithm provably converges, and analyze the optimality gap and constraint violation of the trained policy on unseen tasks. Extensive experiments on an incident dataset in New York City demonstrate that our method outperforms strong baselines in sensing outcome maximization and budget satisfaction, and also generalize well to unseen tasks.

\textit{Dataset condensation} is a newborn technique that generates a small dataset that can be used in training deep neural networks (DNNs) to lower storage and training costs. The objective of dataset condensation is to ensure that the model trained with the synthetic dataset can perform comparably to the model trained with full datasets. However, existing methods predominantly concentrate on classification tasks, posing challenges in their adaptation to time series forecasting (TS-forecasting). This challenge arises from disparities in the evaluation of synthetic data. In classification, the synthetic data is considered well-distilled if the model trained with the full dataset and the model trained with the synthetic dataset yield identical labels for the same input, regardless of variations in output logits distribution. Conversely, in TS-forecasting, the effectiveness of synthetic data distillation is determined by the distance between predictions of the two models. The synthetic data is deemed well-distilled only when all data points within the predictions are similar. Consequently, TS-forecasting has a more rigorous evaluation methodology compared to classification. To mitigate this gap, we theoretically analyze the optimization objective of dataset condensation for TS-forecasting and propose a new one-line plugin of dataset condensation for TS-forecasting designated as Dataset \textbf{Cond}ensation for \textbf{T}ime \textbf{S}eries \textbf{F}orecasting (CondTSF) based on our analysis. Plugging CondTSF into previous dataset condensation methods facilitates a reduction in the distance between the predictions of the model trained with the full dataset and the model trained with the synthetic dataset, thereby enhancing performance. We conduct extensive experiments on eight commonly used time series datasets. CondTSF consistently improves the performance of all previous dataset condensation methods across all datasets, particularly at low condensing ratios.

We are witnessing a rapid growth of electric vehicles in both individual and public transportation. Many large-scale company-built electric bus charging stations have been established to facilitate public transportation, while these electric bus charging stations are not accessible to private vehicles. The motivation for this work comes from the possibility of opening surplus resources in electric bus charging stations to alleviate the charging resource shortage and gain extra profit for the electric bus charging station. The operation facing private vehicles, however, also encounters obstacles including serious congestion induced by absorbing private vehicles and delays of bus lines due to private vehicles occupying charging points. To jointly solve these challenges, we propose a real-time control mechanism to maximize the long-term net profit of an electric bus charging station based on Lyapunov optimization theory and generalized benders decomposition, while maintaining the congestion level and ensuring timetables of buses. We demonstrate through rigorous theoretical proof that the proposed mechanism can be arbitrarily close to the optimal solution. Comprehensive evaluation experiments with real-world data sets have been conducted to show the credibility of the mechanism in reducing congestion, ensuring bus timetables, and maximizing the long-term net profit.

A networked time series (NETS) is a family of time series on a given graph, one for each node. It has a wide range of applications from intelligent transportation to environment monitoring to smart grid management. An important task in such applications is to predict the future values of a NETS based on its historical values and the underlying graph. Most existing methods require complete data for training. However, in real-world scenarios, it is not uncommon to have missing data due to sensor malfunction, incomplete sensing coverage, and so on. In this article, we study the problem of NETS prediction with incomplete data . We propose networked time series Imputation Generative Adversarial Network (NETS-ImpGAN), a novel deep learning framework that can be trained on incomplete data with missing values in both history and future. Furthermore, we propose Graph Temporal Attention Networks , which incorporate the attention mechanism to capture both inter-time series and temporal correlations. We conduct extensive experiments on four real-world datasets under different missing patterns and missing rates. The experimental results show that NETS-ImpGAN outperforms existing methods, reducing the Mean Absolute Error by up to 25%.

Ride-hailing platforms (e.g., Uber and Didi Chuxing) have become increasingly popular in recent years.Efficiencyhas always been an important metric for such platforms. However, only focusing on efficiency inevitably ignores thefairnessof driver incomes, which could impair the sustainability of ride-hailing systems. To optimize such two essential objectives,order dispatchinganddriver repositioningplay an important role, as they impact not only the immediate, but also the future order-serving outcomes of drivers. In practice, the platform offers monetary incentives to drivers for completing the repositioning and has a budget for the repositioning cost. Therefore, in this paper, we aim to exploit joint order dispatching and driver repositioning to optimize both long-term efficiency and fairness in ride-hailing under the budget constraint. To this end, we propose JDRCL, a novel multi-agent reinforcement learning framework, which integrates a group-based action representation that copes with the variable action space, and a primal-dual iterative training algorithm to learn a constraint-satisfying policy that maximizes both the worst and the overall incomes of drivers. Furthermore, we prove the asymptotic convergence rate of our training algorithm. Extensive experiments based on three real-world ride-hailing order datasets show that JDRCL outperforms state-of-the-art baselines on both efficiency and fairness.

The quality of surface water is closely related to human’s production and livelihood. Water salinity is one of the key indicators of water quality assessment. Recently, there has been an increased salinization problem of surface water in many regions of the world, making it necessary to timely monitor the salinity of surface water. Water salinity sensing could be challenging when it comes to surface water with complicated basin and tributaries, where existing methods fail to satisfy both efficiency and accuracy requirements. To address this problem, we propose a novel water salinity sensing system USalt, which leverages the high mobility of UAV and the contactless sensing ability of IR-UWB radar, and realizes fast and accurate water salinity sensing for surface water. Specifically, we design novel methods to eliminate the contamination in raw received radar signals and extract salinity-related features from radar signals. Furthermore, we adopt a neural network model ssNet to precisely estimate water salinity using the extracted features. To efficiently adapt ssNet to different environments, we customize meta learning and design a meta-learning framework mssNet. Extensive real-world experiments carried out by our UAV-based system illustrate that USalt can accurately sense the salinity of water with an MAE of 0.39 g/100 mL.

Mobile crowd sensing (MCS) has emerged as an increasingly popular sensing paradigm due to its cost-effectiveness. This approach relies on platforms to outsource tasks to participating workers when prompted by task publishers. Although incentive mechanisms have been devised to foster widespread participation in MCS, most of them focus only on static tasks (i.e., tasks for which the timing and type are known in advance) and do not protect the privacy of worker bids. In a dynamic and resource-constrained environment, tasks are often uncertain (i.e., the platform lacks a priori knowledge about the tasks) and worker bids may be vulnerable to inference attacks. This paper presents an incentive mechanism HERALD*, that takes into account the uncertainty and hidden bids of tasks without real-time constraints. Theoretical analysis reveals that HERALD* satisfies a range of critical criteria, including truthfulness, individual rationality, differential privacy, low computational complexity, and low social cost. These properties are then corroborated through a series of evaluations.

In recent years, multi-agent reinforcement learning (MARL) has presented impressive performance in various applications. However, physical limitations, budget restrictions, and many other factors usually impose constraints on a multi-agent system (MAS), which cannot be handled by traditional MARL frameworks. Specifically, this paper focuses on constrained MASes where agents work cooperatively to maximize the expected team-average return under various constraints on expected team-average costs, and develops a constrained cooperative MARL framework, named DeCOM, for such MASes. In particular, DeCOM decomposes the policy of each agent into two modules, which empowers information sharing among agents to achieve better cooperation. In addition, with such modularization, the training algorithm of DeCOM separates the original constrained optimization into an unconstrained optimization on reward and a constraints satisfaction problem on costs. DeCOM then iteratively solves these problems in a computationally efficient manner, which makes DeCOM highly scalable. We also provide theoretical guarantees on the convergence of DeCOM's policy update algorithm. Finally, we conduct extensive experiments to show the effectiveness of DeCOM with various types of costs in both moderate-scale and large-scale (with 500 agents) environments that originate from real-world applications.

Recently, improving the robustness of policies across different environments attracts increasing attention in the reinforcement learning (RL) community. Existing robust RL methods mostly aim to achieve the max-min robustness by optimizing the policy’s performance in the worst-case environment. However, in practice, a user that uses an RL policy may have different preferences over its performance across environments. Clearly, the aforementioned max-min robustness is oftentimes too conservative to satisfy user preference. Therefore, in this paper, we integrate user preference into policy learning in robust RL, and propose a novel User-Oriented Robust RL (UOR-RL) framework. Specifically, we define a new User-Oriented Robustness (UOR) metric for RL, which allocates different weights to the environments according to user preference and generalizes the max-min robustness metric. To optimize the UOR metric, we develop two different UOR-RL training algorithms for the scenarios with or without a priori known environment distribution, respectively. Theoretically, we prove that our UOR-RL training algorithms converge to near-optimal policies even with inaccurate or completely no knowledge about the environment distribution. Furthermore, we carry out extensive experimental evaluations in 6 MuJoCo tasks. The experimental results demonstrate that UOR-RL is comparable to the state-of-the-art baselines under the average-case and worst-case performance metrics, and more importantly establishes new state-of-the-art performance under the UOR metric.

The rapid development of connected autonomous vehicles (CAVs) makes it foreseeable that CAVs will dominate future road traffic. To manage CAV traffic, researchers developed a revolutionary paradigm, which uses intelligent intersection managers (IMs) for a finer-grained control of CAVs' cruising at intersections than traditional traffic lights. However, existing IM-based methods mostly focus on optimizing the single-intersection CAV traffic efficiency, without solving the fundamental problem of maximizing the global efficiency of a multi-intersection road network. Therefore, we address such problem by proposing a system architecture that decomposes each IM into an oracle and a valve, where the oracle ensures safe and efficient crossing at individual intersections, and the valve selects some of the approaching CAVs for the oracle to control and postpones the crossing of the unselected ones. We further focus on distributed decision making for the valves, and propose a multi-agent reinforcement learning framework, spatial-aware multi-agent actor-credit (SMAC). Specifically, SMAC integrates a novel credit assignment method that captures agents' spatially decaying influences to stimulate agent cooperation, and a novel graph convolutional mixing network to capture the graph-structured inter-agent relationships in a road network. We conduct extensive experiments on three traffic flow datasets, and show that SMAC outperforms state-of-the-art baselines.

Data with missing values is ubiquitous in many applications. Recent years have witnessed increasing attention on prediction with only incomplete data consisting of observed features and a mask that indicates the missing pattern. Existing methods assume that the training and testing distributions are the same, which may be violated in real-world scenarios. In this paper, we consider prediction with incomplete data in the presence of distribution shift. We focus on the case where the underlying joint distribution of complete features and label is invariant, but the missing pattern, i.e., mask distribution may shift agnostically between training and testing. To achieve generalization, we leverage the observation that for each mask, there is an invariant optimal predictor. To avoid the exponential explosion when learning them separately, we approximate the optimal predictors jointly using a double parameterization technique. This has the undesirable side effect of allowing the learned predictors to rely on the intra-mask correlation and that between features and mask. We perform decorrelation to minimize this effect. Combining the techniques above, we propose a novel prediction method called StableMiss. Extensive experiments on both synthetic and real-world datasets show that StableMiss is robust and outperforms state-of-the-art methods under agnostic mask distribution shift.

Machines with rotary parts are prevalent in industrial systems and our daily lives. Rotation speed measurement is a crucial task for monitoring machinery health. Previous approaches for rotation speed sensing are constrained by limited operation distance, strict requirement for illumination, or strong dependency on the target object’s light reflectivity. In this work, we propose mRotate, a practical mmWave radar-based rotation speed sensing system liberated from all the above constraints. Specifically, mRotate separates the target signal reflected by the rotating object from the mixed reflection signals, extracts the high-quality rotation related features, and accurately obtains the rotation speed through the customized radar sensing mode and algorithm design. We implement mRotate on a commercial mmWave radar and extensively evaluate it in both lab environments and in a machining workshop for field tests. mRotate achieves an MAPE of 0.24% in accuracy test, which is 38% lower than that produced by the baseline device, a popular commercial laser tachometer. Besides, our experiments show that mRotate can measure a spindle whose diameter is only 5mm, maintain a high accuracy with a sensing distance as far as 2.5m, and simultaneously measure the rotation speeds of multiple objects.

For-hire vehicle-enabled crowd sensing (FVCS) has become a promising paradigm to conduct urban sensing tasks in recent years. FVCS platforms aim to jointly optimize both the order-serving revenue as well as sensing coverage and quality. However, such two objectives are often conflicting and need to be balanced according to the platforms’ preferences on both objectives. To address this problem, we propose a novel cooperative multi-objective multi-agent reinforcement learning framework, referred to as MOVDN, to serve as the first preference-configurable order dispatch mechanism for FVCS platforms. Specifically, MOVDN adopts a decomposed network structure, which enables agents to make distributed order selection decisions, and meanwhile aligns each agent’s local decision with the global objectives of the FVCS platform. Then, we propose a novel algorithm to train a single universal MOVDN that is optimized over the space of all preferences. This allows our trained model to produce the optimal policy for any preference. Furthermore, we provide the theoretical convergence guarantee and sample efficiency analysis of our algorithm. Extensive experiments on three real-world ride-hailing order datasets demonstrate that MOVDN outperforms strong baselines and can support the platform in decision-making effectively.

This paper presents EmoRI, a novel single-chip mmWave radar-based egomotion estimation approach that works in challenging scenarios where moving objects exist in radar's Field of View (FoV). Essentially, estimating a mobile platform's egomotion using an on-board mmWave radar requires inferring the relative motion between radar and the points of the stationary objects (PSOs) in the radar point cloud. However, in practice, there could be no PSOs because of the blockage of moving objects. Even if PSOs exist, precisely identifying them is still challenging due to (i) the large quantity of points generated by the moving objects, and (ii) the huge angle estimation errors of the conventional point cloud generation algorithm. We empower EmoRI to overcome the above challenges incurred by moving objects with three core techniques, which include (i) a hybrid FFT-MUSIC algorithm that improves the angle estimation accuracy of single-chip mmWave radar, (ii) a multiple stationary target consensus algorithm that precisely selects the PSOs from the radar point cloud, and (iii) a simultaneous fusion and calibration mechanism that introduces an IMU as the auxiliary sensor, meticulously calibrates IMU accelerations with radar measurements, and complimentarily fuses these two modalities to obtain the 6-DoF egomotion. Our extensive experiments validate that EmoRI pushes the limit of single-chip mmWave radar-based egomotion estimation with moving objects in radar's FoV by reducing the per-meter destination error from decimeter to centimeter level.

Recent years have witnessed a vastly increasing popularity of location-based social networks (LBSNs), which facilitates studies on the next Point-of-Interest (POI) recommendation problem. A user’s POI visiting behavior shows the sequential transition correlation with previous successive check-ins and the global spatial-temporal correlation with those check-ins that happened a long time ago at a similar time of day and in geographically close areas. Although previous POI recommendation methods attempted to capture these two correlations, several limitations remain to be solved: (1) RNNs are widely adopted to capture the sequential transition correlation, whereas training an RNN is rather time-consuming given the long input check-in sequence. (2) The pairwise proximities on time of day and geographical area of check-ins are crucial for global spatial-temporal correlation learning, but have not been comprehensively considered by previous methods. To tackle these issues, we propose a novel next POI recommendation framework named STA-TCN. Specifically, instead of RNNs, STA-TCN augments the Temporal Convolutional Network with gated input injection to learn sequential transition correlation. Furthermore, STA-TCN fuses two novel grid-difference and time-sensitivity learning mechanisms with attention network to learn the pairwise spatial-temporal proximities among a user’s check-ins. Extensive experiments are conducted on two large-scale real-world LBSN datasets, and the results show that STA-TCN outperforms the best state-of-the-art baseline with an average improvement of 9.71% and 7.88% on hit rate and normalized discounted cumulative gain, respectively.

The drastic increase of metro passengers in recent years inevitably causes the overcrowdedness in the metro systems. Accurately predicting passenger flows at metro stations is critical for efficient metro system management, which helps alleviate such overcrowdedness. Compared to the prevalent next-step prediction, multi-step passenger flow prediction could prominently increase the prediction duration and reveal finer-grained passenger flow variations, which better helps metro system management. Thus, in this paper, we address the problem ofmulti-step metro station passenger (MSP) flow prediction. In light of MSP flows’ unique spatial-temporal characteristics, we proposeSTP-TrellisNets+, which for the first time augments the newly-emerged temporal convolutional frameworkTrellisNetfor multi-step MSP flow prediction. The temporal module of STP-TrellisNets+ (namedCP-TrellisNetsED) employs a Closeness TrellisNet followed by aPeriodicity TrellisNets-based Encoder-Decoder (P-TrellisNetsED)to jointly capture the short- and long-term temporal correlation of MSP flows. In parallel to CP-TrellisNetsED, its spatial module (namedGC-TrellisNetsED) adopts a novel transfer flow-based metric to characterize the spatial correlation among MSP flows, and implements another TrellisNetsED on multiplediffusion graph convolutional networks (DGCNs)in time-series order to capture the dynamics of such spatial correlation. Extensive experiments with two large-scale real-world automated fare collection datasets demonstrate that STP-TrellisNets+ outperforms the state-of-the-art baselines.

Recent years have witnessed the increasing popularity of electric buses (e-buses) around the globe due to their environment friendly nature. However, various factors, such as the prohibitive purchasing costs and the scarcity of large-scale charging facilities, hinder the wider adoption of e-buses. Thus, to effectively cut the cost of building and maintaining urban e-bus systems, we optimize the dispatching strategy for urban e-bus systems to satisfy public transportation demands with the minimum e-bus fleet. Specifically, we propose to systematically exploit at city-scale cross-line dispatching, a smart dispatching strategy allowing one bus to serve multiple bus lines when necessary. Technically, we construct a novel and generalizable graph-theoretic model for urban e-bus systems integrating e-buses non-negligible charging time, the spatio-temporal constraints of bus trips, and various other real-world factors. We prove that it is NP-hard, and has no$(2-\epsilon)$-approximation algorithm. Next, we propose a polynomial-time algorithm solving the problem with a guaranteed approximation ratio. Furthermore, we conduct extensive experiments on a large-scale real-world bus dataset from Shenzhen, China, which validate the effectiveness of our algorithms. As shown by our experimental results, to serve 300 bus lines, our dispatching strategy needs 38.2% less e-buses than the one currently used in practice.

Nowadays, the rapid development of self-driving technology and its fusion with the current vehicle electrification process has given rise to electric self-driving taxis (es-taxis). Foreseeably, es-taxis will become a major force that serves the massive urban mobility demands not far into the future. Though promising, it is still a fundamental unsolved problem of effectively deciding when and where a city-scale fleet of es-taxis should be charged, so that enough es-taxis will be available whenever and wherever ride requests are submitted. Furthermore, charging decisions are far from isolated, but tightly coupled with the order dispatch process that matches orders with es-taxis. Therefore, in this paper, we investigate the problem of joint order dispatch and charging in es-taxi systems, with the objective of maximizing the ride-hailing platform’s long-term cumulative profit. Technically, such problem is challenging in a myriad of aspects, such as long-term profit maximization, partial statistical information on future orders, etc. We address the various arising challenges by meticulously integrating a series of methods, including distributionally robust optimization, primal-dual transformation, and second order conic programming to yield far-sighted decisions. Finally, we validate the effectiveness of our proposed methods though extensive experiments based on two large-scale real-world online ride-hailing order datasets.

The ride-hailing service offered by mobility-on-demand platforms, such as Uber and Didi Chuxing, has greatly facilitated people's traveling and commuting, and become increasingly popular in recent years. Efficiency (e.g., gross merchandise volume) has always been an important metric for such platforms. However, only focusing on the efficiency inevitably ignores the fairness of driver incomes, which could impair the sustainability of the overall ride-hailing system in the long run. To optimize the aforementioned two essential metrics, order dispatching and driver repositioning play an important role, as they impact not only the immediate, but also the future order-serving outcomes of drivers. Thus, in this paper, we aim to exploit joint order dispatching and driver repositioning to optimize both the long-term efficiency and fairness for ride-hailing platforms. To address this problem, we propose a novel multi-agent reinforcement learning framework, referred to as JDRL, to help drivers make distributed order selection and repositioning decisions. Specifically, to cope with the variable action space, JDRL segments the action space into a fixed number of action groups, and fixes the policy output dimension for order selection as the number of action groups. In terms of the fairness criterion, JDRL adopts the max-min fairness, and augments the vanilla policy gradient to an iterative training algorithm that alternates between a minimization step and a policy improvement step to maximize both the worst and the overall performance of agents. In addition, we provide the theoretical convergence guarantee of our JDRL training algorithm even under non-convex policy networks and stochastic gradient updating. Extensive experiments are conducted with three public real-world ride-hailing order datasets, including over 2 million orders in Haikou, China, over 5 million orders in Chengdu, China, and over 6 million orders in New York City, USA. Experimental results show that JDRL demonstrates a consistent advantage compared to state-of-the-art baselines in terms of both efficiency and fairness. To the best of our knowledge, this is the first work that exploits joint order dispatching and driver repositioning to optimize both the long-term efficiency and fairness in a ride-hailing system.

Emerging crowdsensing paradigm enables a large number of sensing applications, where much attention is drawn to the fundamental problems of data collection and truth inference. Existing works have devised manifold techniques to discover truth from collected noisy data, but they frequently ignore various expertise of workers and dynamic information of crowdsensing system, thus leading to error-prone estimated truth and unqualified sensing data. In this paper, we design an online location-aware crowdsensing system to accurately estimate truth and efficiently assign tasks. Specifically, we unify diverse types of numerical and categorical tasks based on probabilistic graphical model, and then propose unsupervised learning methods which can dynamically infer ground truth and various worker expertise at the same time. Furthermore, we develop online task allocation schemes to gradually gather high quality data considering location awareness and inferred worker expertise. In particular, we convert the complicated task allocation into the additive form of probability improvement and entropy reduction, thereby solving the allocation problem via linearly selecting worker-task pair with low computation complexity. We finally carry out extensive evaluations using two datasets collected by our smartphones, where results demonstrate the superiority of our algorithms over the state-of-the-art approaches.

Urban traffic flow forecasting is a critical issue in intelligent transportation systems. Due to the complexity and uncertainty of urban road conditions, how to capture the dynamic spatiotemporal correlation and make accurate predictions is very challenging. In most of existing works, urban road network is often modeled as a fixed graph based on local proximity. However, such modeling is not sufficient to describe the dynamics of the road network and capture the global contextual information. In this paper, we consider constructing the road network as a dynamic weighted graph through attention mechanism. Furthermore, we propose to seek both spatial neighbors and semantic neighbors to make more connections between road nodes. We propose a novel Spatiotemporal Adaptive Gated Graph Convolution Network ( STAG-GCN ) to predict traffic conditions for several time steps ahead. STAG-GCN mainly consists of two major components: (1) multivariate self-attention Temporal Convolution Network ( TCN ) is utilized to capture local and long-range temporal dependencies across recent, daily-periodic and weekly-periodic observations; (2) mix-hop AG-GCN extracts selective spatial and semantic dependencies within multi-layer stacking through adaptive graph gating mechanism and mix-hop propagation mechanism. The output of different components are weighted fused to generate the final prediction results. Extensive experiments on two real-world large scale urban traffic dataset have verified the effectiveness, and the multi-step forecasting performance of our proposed models outperforms the state-of-the-art baselines.

Recent years have witnessed the proliferation of electric vehicles (EVs) that enable environment-friendly commuting and traveling. However, the increasing number of EVs inevitably create massive charging demands that are challenging to satisfy. Oftentimes in practice, EVs have to wait in queues for a long time outside charging stations before chargers become available. To address this challenge, we fully capture the elasticity of EVs’ charging demands in response to the charging prices, and propose a dynamic charging pricing mechanism that jointly controls the lengths of the demand queues at multiple charging stations and maximizes the charging platform’s long-term profit for offering charging services. Clearly, such an approach is more feasible than the financially and temporally expensive way of constructing extra charging facilities. Technically, we augment the Lyapunov stochastic optimization technique to decompose the challenging long-term decision-making problem into a series of single-time-slot optimization programs which require zero knowledge of future system parameters. However, due to the correlation of charging demands among different stations, the aforementioned optimization program in each time slot is non-convex. We handle the non-convexity by jointly constructing independent sets of charging stations and adapting the block coordinate descent method to iteratively obtain approximately optimal charging prices. Through rigorous theoretical analysis and extensive simulations based on the real-world dataset in the Chinese city Shenzhen which consists of 4000 taxis and 171 charging stations, we demonstrate that our control policy ensures an arbitrarily close-to-optimal profit with a flexible trade-off between the profit and queue lengths, has a low computational complexity, and requires zero knowledge of future system dynamics.

Mobile edge computing enables resource-limited edge clouds (ECs) in federation to help each other with resource-hungry yet delay-sensitive service requests. Contrary to common practice, we acknowledge that mobile services are heterogeneous and the limited storage resources of ECs allow only a subset of services to be placed at the same time. This paper presents a jointly optimized design of cooperative placement and scheduling framework, named JCPS, that pursuessocial cost minimizationover time while ensuring diverse user demands. Our main contribution is a novel perspective on cost reduction by exploiting thespatial-temporal diversitiesinworkload and resource costamong federated ECs. To build a practical edge cloud federation system, we have to consider two major challenges:user deadline preferenceandECs’ strategic behaviors. We first formulate and solve the problem of spatially strategic optimization without deadline awareness, which is proved$\mathcal {NP}$-hard. By leveraging user deadline tolerance, we develop a Lyapunov-baseddeadline-drivenjoint cooperative mechanism under the scenario where the workload and resource information of ECs are known for one-shot global cost minimization. Theservice priorityimposed by deadline urgency drives time-critical placement and scheduling, which, combined with cooperative control, enables workloads migrated across different times and ECs. Given selfishness of individual ECs, we further design an auction-based cooperative mechanism to elicittruthful bidson workload and resource cost. Rigorous theoretical analysis and extensive simulations are performed, validating the efficiency of JCPS in realizing cost reduction and user satisfaction.

Nowadays, most of the taxi drivers have become users of the relocation recommendation service offered by online ride-hailing platforms (e.g., Uber and Didi Chuxing), which could oftentimes lead drivers to places with profitable orders. At the same time, electric taxis (e-taxis) are increasingly adopted and gradually replacing gasoline taxis in today’s public transportation systems due to their environmental-friendly nature. Though effective for traditional gasoline taxis, existing relocation recommendation schemes are rather suboptimal for e-taxi drivers’ user experience. On one hand, the existing schemes take no account of taxis’ refueling decisions, as the refueling durations of gasoline taxis are usually short enough to be ignored. However, the charging duration of the e-taxis spent at charging stations can be as long as hours. Obviously, an e-taxi’s battery could be easily depleted by the continuous relocations suggested by existing schemes, and thus will have to be charged for a long time afterwards, making the e-taxi driver miss numerous order-serving opportunities. On the other hand, charging posts are typically sparsely and unevenly distributed across a city. With no consideration of charging opportunities, existing schemes could probably send an e-taxi to an area with no charging post around, even though its battery is running low. To optimize e-taxi drivers’ user experience, in this paper, we design a jointcharging and relocation recommendation system for e-taxi drivers (CARE). We take the perspective of e-taxi drivers and formulate their decision making as a multi-agent reinforcement learning problem where each e-taxi driver aims to maximize his own cumulative rewards. More specifically, we propose a novelmulti-agent mean field hierarchical reinforcement learning (MFHRL)framework. The hierarchical architecture of MFHRL helps the proposed CARE provide far-sighted charging and relocation recommendations for e-taxi drivers. Besides, we integrate each hierarchical level of MFHRL separately with the mean field approximation to incorporate e-taxis’ mutual influences in decision making. We set up a simulator with one of the largest real-world e-taxi datasets in Shenzhen, China, which contains the GPS trajectory data and transaction data of 3848 e-taxis from June 1st to June 30th, 2017, coupled with 165 charging stations including 317 fast charging posts and 1421 slow charging posts. We adopt this simulator to generate 6 dynamic urban environments, which reflect the different real-world scenarios faced by e-taxi drivers. In all of these environments, we conduct extensive experiments to validate that the proposed MFHRL framework greatly outperforms all baselines by significantly increasing the rewards obtained by e-taxi drivers. Besides, we also show that the charging policy learned by MFHRL can effectively reduce the range anxiety of e-taxi drivers, which significantly boosts e-taxi drivers’ quality of experience.

As a critical part of the intelligent transportation system, traffic prediction is challenging due to the time-evolving cascading behavior, i.e., the fluctuation of traffic conditions on one road will affect neighboring roads in the future. To address this issue, we propose a novel learning framework, which is able to extract the most relevant historical information for prediction by capturing the underlying cascading behavior. An encoder-decoder architecture is adopted, where the historical contextual information of each road is encoded into a sequence of historical embeddings. A spatiotemporal attention mechanism is devised to model the cascading behavior in the embedding space so that the most relevant information for prediction is concentrated. Extensive experiments on a real-world large-scale highway dataset verify the effectiveness of our proposed approach, observing 3% ~ 5% improvement over state-of-the-art methods.

Nowadays, the urban vehicle sharing (UVS) service offered by online platforms such as Car2Go and Zipcar has become an attractive choice for short-term mobility demands of city residents. Such way of shared mobility also demonstrates its potential in addressing various urban traffic problems (e.g., congestion, exhaust gas emission). However, the power of UVS systems could not be fully unleashed, unless the demand-supply gaps, incurred by the uneven spatial-temporal distributions of vehicle sharing orders and available vehicles, are effectively bridged. In this paper, we propose to resolve such problem by performing joint order dispatch and repositioning, which eventually maximizes the UVS platform's long-term cumulative profit. Specifically, we have addressed the various arising challenges, including capturing the interactive effect between order dispatch and repositioning, incorporating properly vehicles' fuel levels in our model, and dealing with stochastic demand with partially known statistical information. Technically, the problem is formulated as a stochastic dynamic program, and by integrating a series of methods, involving distributionally robust optimization, primal-dual transformation, as well as second order conic programming, we finally yield long-term optimal decisions. Furthermore, we validate our proposed methods using a large-scale real-world UVS dataset with over 300 vehicles and 300 thousand orders spanning overall 18 months.

Electric self-driving taxis (es-taxis) draw great attention nowadays and hold the promise for future transportation due to their convenient and environment-friendly nature. However efficiently managing large-scale es-taxis remains an open problem. In this paper, we focus on scheduling es-taxis under charging budget constraint. Specifically, we design safe-controller to guarantee the satisfaction of budget constraint, and propose HAT framework to enlarge the sight for decision-making on deactivating es-taxis. As for the non-stationary induced by HAT, we analyze and limit its influence with theoretical guarantees. The overall framework Safe-HAT achieves superior performance in real-world data against other strong baselines.

Recently, vehicular crowd sensing (VCS) that leverages sensor-equipped urban vehicles to collect city-scale sensory data has emerged as a promising paradigm for urban sensing. Nowadays, a wide spectrum of VCS tasks are carried out by for-hire vehicles (FHVs) due to various hardware and software constraints that are difficult for private vehicles to satisfy. However, such FHV-enabled VCS systems face a fundamental yet unsolved problem of striking a balance between the order-serving and sensing outcomes. To address this problem, we propose a novel graph convolutional cooperative multi-agent reinforcement learning (GCC-MARL) framework, which helps FHVs make distributed routing decisions that cooperatively optimize the system-wide global objective. Specifically, GCC-MARL meticulously assigns credits to agents in the training process to effectively stimulate cooperation, represents agents' actions by a carefully chosen statistics to cope with the variable agent scales, and integrates graph convolution to capture useful spatial features from complex large-scale urban road networks. We conduct extensive experiments with a real-world dataset collected in Shenzhen, China, containing around 1 million trajectories and 50 thousand orders of 553 taxis per-day from June 1st to 30th, 2017. Our experiment results show that GCC-MARL outperforms state-of-the-art baseline methods in order-serving revenue, as well as sensing coverage and quality.

Vehicular urban sensing (VUS), which uses sensors mounted on crowdsourced vehicles or on-board drivers' smartphones, has become a promising paradigm for monitoring critical urban metrics. Due to various hardware and software constraints difficult for private vehicles to satisfy, for-hire vehicles (FHVs) are usually the major forces for VUS systems. However, FHVs alone are far from enough for fine-grained spatio-temporal sensing coverage, because of their severe distribution biases. To address this issue, we propose to use a hybrid approach, where a centralized platform not only leverages FHVs to conduct sensing tasks during their daily movements of serving passenger orders, but also controls multiple dedicated sensing vehicles (DSVs) to bridge FHVs' coverage gaps. Specifically, we aim to achieve fine-grained spatio-temporal sensing coverage at the minimum long-term operational cost by systematically optimizing the repositioning policy for DSVs. Technically, we formulate the problem as a stochastic dynamic program, and solve various challenges, including long-term cost minimization, stochastic demand with partial statistical knowledge, and computational intractability, by integrating distributionally robust optimization, primal-dual transformation, and second order conic programming methods. We validate the effectiveness of our methods using a real-world dataset from Shenzhen, China, containing 726,000 trajectories of 3848 taxis spanning overall 1 month in 2017.

Nowadays, crowdsourcing has become an increasingly popular paradigm for large-scale data collection, annotation, and classification. Today's rapid growth of crowdsourcing platforms calls for effective worker selection mechanisms, which oftentimes have to operate with a priori unknown worker reliability. We discover that the empirical entropy of workers' results, which measures the uncertainty in the final aggregated results, naturally becomes a suitable metric to evaluate the outcome of crowdsourcing tasks. Therefore, this paper designs a worker selection mechanism that minimizes the empirical entropy of the results submitted by participating workers. Specifically, we formulate worker selection under sequentially arriving tasks as a combinatorial multi-armed bandit problem, which treats each worker as an arm, and aims at learning the best combination of arms that minimize the cumulative empirical entropy. By information theoretic methods, we carefully derive an estimation of the upper confidence bound for empirical entropy minimization, and leverage it in our minimum entropy upper confidence bound (ME-UCB) algorithm to balance exploration and exploitation. Theoretically, we prove that ME-UCB has a regret upper bound of O(1), which surpasses existing submodular UCB algorithms. Our extensive experiments with both a synthetic and real-world dataset empirically demonstrate that our ME-UCB algorithm outperforms other state-of-the-art approaches.

The rapid development of information and communication technologies has given rise to mobility-on-demand (MoD) systems (e.g., Uber, Didi) that have fundamentally revolutionized urban transportation. One common feature of today's MoD systems is the integration of ridesharing due to its cost-efficient and environment-friendly natures. However, a fundamental unsolved problem for such systems is how to serve people's heterogeneous transportation demands with as few vehicles as possible. Naturally, solving such minimum fleet problem is essential to reduce the vehicles on the road to improve transportation efficiency. Therefore, we investigate the fleet minimization problem in ridesharing-aware MoD systems. We use graph-theoretic methods to construct a novel order graph capturing the complicated inter-order shareability, each order's spatial-temporal features, and various other real-world factors. We then formulate the problem as a tree cover problem over the order graph, which differs from the traditional coverage problems. Theoretically, we prove the problem is NP-hard, and propose a polynomial-time algorithm with a guaranteed approximation ratio. Besides, we address the online fleet minimization problem, where orders arrive in an online manner. Finally, extensive experiments on a city-scale dataset from Shenzhen, containing 21 million orders from June 1st to 30th, 2017, validate the effectiveness of our algorithms.

Recent years have witnessed the rising popularity of urban vehicular crowd sensing (UVCS) systems that leverage drivers' mobile devices equipped with on-board sensors for various urban sensing tasks. Because of the importance of ensuring satisfactory spatio-temporal sensing coverage in such UVCS systems, most existing work has focus on designing efficient scheduling mechanisms to maximize the task completion rate under drivers' traveling constraints. Different from prior work, we propose Hector, a joint trajectory scheduling and incentive mechanism for spatio-temporal UVCS systems, which concentrates on capturing the interactive effects between scheduling and incentive mechanisms. Technically, we first reduce the dimensions of the original scheduling problem by mapping it into an augmented set cover problem with spatio-temporal constraints. Then, based on reverse combinatorial auctions, we design Hector, whose incentive mechanism with the presence of uncertain future trajectory information makes scheduling and compensation decisions in real-time. Specifically, Hector is truthful, individual rational and computationally efficient. Furthermore, the social cost yielded by Hector is close-to-optimal, and the approximation ratio is Hm. The advantageous properties of Hector are verified by both rigorous theoretical analysis and extensive simulations based on the real world datasets in the Chinese city Shenzhen which consists of 726,000 taxi trajectories.

Urban traffic flow forecasting is a critical issue in intelligent transportation systems. It is quite challenging due to the complicated spatiotemporal dependency and essential uncertainty brought about by the dynamic urban traffic conditions. In most of existing methods, the spatial correlation is captured by utilizing graph neural networks (GNNs) throughout a fixed graph based on local spatial proximity. However, urban road conditions are complex and changeable, which leads to the interactions between roads should also be dynamic over time. In addition, the global contextual information of roads are also crucial for accurate forecasting. In this paper, we exploit spatiotemporal correlation of urban traffic flow and construct a dynamic weighted graph by seeking both spatial neighbors and semantic neighbors of road nodes. Multi-head self-attention temporal convolution network is utilized to capture local and long-range temporal dependencies across historical observations. Besides, we propose an adaptive graph gating mechanism to extract selective spatial dependencies within multi-layer stacking and correct information deviations caused by artificially defined spatial correlation. Extensive experiments on real world urban traffic dataset from Didi Chuxing GAIA Initiative have verified the effectiveness, and the multi-step forecasting performance of our proposed models outperforms the state-of-the-art baselines. The source code of our model is publicly available at https://github.com/RobinLu1209/STAG-GCN.

Recent years have witnessed a drastic increase in the number of urban metro passengers, which inevitably causes the overcrowdedness in the metro systems of many cities. Clearly, an accurate prediction of passenger flows at metro stations is critical for a variety of metro system management operations, such as line scheduling and staff preallocation, that help alleviate such overcrowdedness. Thus, in this paper, we aim to address the problem of accurately predicting metro station passenger (MSP) flows. Similar to other traffic data, such as road traffic volume and highway speed, MSP flows are also spatial-temporal in nature. However, existing methods for other traffic prediction tasks are usually suboptimal to predict MSP flows due to MSP flows' unique spatial-temporal characteristics. As a result, we propose a novel deep learning framework STP-TrellisNets, which for the first time augments the newly-emerged temporal convolutional framework TrellisNet for spatial-temporal prediction. The temporal module of STP-TrellisNets (named CP-TrellisNets) employs two TrellisNets in serial to jointly capture the short- and long-term temporal correlation of MSP flows. In parallel to CP-TrellisNets, its spatial module (named GC-TrellisNet) adopts a novel transfer flow-based metric to characterize the spatial correlation among MSP flows, and implements multiple diffusion graph convolutional networks (DGCNs) in time-series order with their outputs connected to a TrellisNet to capture the dynamics of such spatial correlation. Clearly, GC-TrellisNet essentially integrates TrellisNet with graph convolution, and empowers TrellisNet with the ability to capture dynamic graph-structured correlation. We conduct extensive experiments with two large-scale real-world automated fare collection datasets, which contain respectively about 1.5 billion records in Shenzhen, China and 70 million records in Hangzhou, China. The experimental results demonstrate that STP-TrellisNets outperforms the state-of-the-art baselines.

Integration of information on road transverse geometric features such as cross slope and superelevation in digital maps can widen the scope of its applications, which is primarily navigation, by enabling driving safety and efficiency applications such as Advanced Driver Assistance Systems (ADAS). The huge scale and dynamic nature of road networks make sensing such road geometric features a challenging task. Traditional methods oftentimes suffer from high cost, limited scalability and update frequency, as well as poor sensing accuracy. To overcome these problems, we propose a cost-effective and scalable road transverse slope estimation framework using sensor data from smartphones. Based on error characteristics of smartphone sensors, we intelligently combine data from accelerometer, gyroscope and GPS to estimate road transverse slope profile of a road segment. To improve accuracy and robustness of the system, the estimations of road transverse slope from multiple sources/vehicles are crowd-sourced to compensate for the effects of varying quality of sensor data from different sources. Extensive experimental evaluation on a test route of 9km demonstrates the superior performance of our proposed method, achieving 350% improvement on road transverse slope estimation accuracy over existing methods, with 90% of errors below 0.5°.

Nowadays, ridesharing has become one of the most popular services offered by online ride-hailing platforms (e.g., Uber and Didi Chuxing). Existing ridesharing platforms adopt the strategy that dispatches orders over the entire city at a uniform time interval. However, the uneven spatio-temporal order distributions in real-world ridesharing systems indicate that such an approach is suboptimal in practice. Thus, in this paper, we exploit adaptive dispatching intervals to boost the platform's profit under a guarantee of the maximum passenger waiting time. Specifically, we propose a hierarchical approach, which generates clusters of geographical areas suitable to share the same dispatching intervals, and then makes online decisions of selecting the appropriate time instances for order dispatch within each spatial cluster. Technically, we prove the impossibility of designing constant-competitive-ratio algorithms for the online adaptive interval problem, and propose online algorithms under partial or even zero future order knowledge that significantly improve the platform's profit over existing approaches. We conduct extensive experiments with a large-scale ridesharing order dataset, which contains all of the over 3.5 million ridesharing orders in Beijing, China, received by Didi Chuxing from October 1st to October 31st, 2018. The experimental results demonstrate that our proposed algorithms outperform existing approaches.

The best arm identification problem in multi-armed bandit model has been widely applied into many practical applications, such as spectrum sensing, online advertising, and cloud computing. Although lots of works have been devoted into this area, most of them do not consider the cost of pulling actions, i.e., a player has to pay some cost when she pulls an arm. Motivated by this, we study a ratio-based best arm identification problem, where each arm is associated with a random reward as well as a random cost. For any δ ∈ (0, 1), with probability at least 1-δ, the player aims to find the optimal arm with the largest ratio of expected reward to expected cost using as few samplings as possible. To solve this problem, we propose three algorithms: 1) a genie-aided algorithm GA; 2) the successive elimination algorithm with unknown gaps SEUG; 3) the successive elimination algorithm with unknown gaps and variance information SEUG-V, where gaps denote the differences between the optimal arm and the suboptimal arms. We show that for all three algorithms, the sample complexities, i.e., the pulling times for all arms, grow logarithmically as 1/δ increases. Moreover, compared to existing works, the running of our elimination-type algorithms is independent of the arm-related parameters, which is more practical. In addition, we also provide a fundamental lower bound for sample complexities of any algorithms under Bernoulli distributions, and show that the sample complexities of the proposed three algorithms match that of the lower bound in the sense of log 1/δ. Finally, we validate our theoretical results through numerical experiments.

Mobile crowdsening (MCS) recently has been regarded as a newly-emerged sensing paradigm, which consists of a centralized cloud-based platform, some data demanders and some workers. However, since the platform needs to process tons of sensory data which is requested by the demanders and submitted by a large number of workers, this traditional MCS system may cause a heavy latency and serious network congestion, and thus can not be employed to some real-time and large-scale applications. Therefore, a new MCS system has been proposed recently by combining the edge computing, where some edge nodes (e.g., the base stations, laptops, smartphones) are added between the platform and workers to offload some operations from the platform to the network edges. Similar to the traditional MCS system, since participating in such edge-assisted MCS system is costly, it is important to attract more participation. However, this is more difficult since the platform and workers do not have direct communications with each other, which makes the edge nodes arbitrarily manipulate the information they transfer. Therefore, unlike the prior arts, we propose a novel incentive mechanism, namely, CHASTE, for such edge-assisted MCS system consisting of multiple demanders, some edge nodes and a crowd of workers where all of them behave strategically to maximize their own utility. Specifically, CHASTE is able to stimulate the participation, and satisfies the three-party truthfulness, three-party individual rationality, budget balance, as well as high social welfare. The desirable properties of CHASTE are validated through both theoretical analysis and extensive simulations.

Exploiting the computing capability of mobile devices with specialized engines (e.g., Neural Engine in iPhone), an attractive paradigm of federated learning that combines the mobile crowdsensing (MCS) has been deeply investigated recently (e.g., Google AI and Nvidia), where the training task is offloaded to the mobile crowd. However, this new paradigm still has numerous problems. Since executing the training task is costly for individual workers, the first problem is how to attract more participants. Following the incentive requirement, the second is how to preserve the workers' bid privacy since the reported costs are usually sensitive. Finally, the third problem is to guarantee the privacy protection on locally training models in the federated learning which involve the private information of local data. In this paper, we propose an incentivized federated learning with differential privacy in MCS system, namely, SHIELD, to solve the three significant problems. In fact, SHIELD satisfies the truthfulness and individual rationality while preserving the differential privacy of workers' bids and locally training models. Furthermore, for accuracy, the excess empirical risk of 1 SHIELD is proved to be upper bounded by O((ln(Knmin))1/2/Knmin+ ln(Knmin)/K2nmin2), where a special case for totally distributed scenario leads to a much sharper bound O( log(n)/n2) than the latest result O(ln(mnmin)/m2nmin2). Finally, comparing with the state-of-art apmin proaches, SHIELD illustrates superior performance by numerous experiments in classification and regression tasks.

Cooperative offloading in mobile edge computing enables resource-constrained edge clouds to help each other with computation-intensive tasks. However, the power of such offloading could not be fully unleashed, unless trust risks in collaboration are properly managed. As tasks are outsourced and processed at the network edge, completion latency usually presents high variability that can harm the offered service levels. By jointly considering these two challenges, we propose OLCD, an Online Learning-aided Cooperative offloaDing mechanism under the scenario where computation offloading is organized based on accumulated social trust. Under co-provisioning of computation, transmission, and trust services, trust propagation is performed along the multi-hop offloading path such that tasks are allowed to be fulfilled by powerful edge clouds. We harness Lyapunov optimization to exploit the spatial-temporal optimality of long-term system cost minimization problem. By gap-preserving transformation, we decouple the series of bidirectional offloading problems so that it suffices to solve a separate decision problem for each edge cloud. The optimal offloading control can not materialize without complete latency knowledge. To adapt to latency variability, we resort to the delayed online learning technique to facilitate completion latency prediction under long-duration processing, which is fed as input to queued-based offloading control policy. Such predictive control is specially designed to minimize the loss due to prediction errors over time. We theoretically prove that OLCD guarantees close-to-optimal system performance even with inaccurate prediction, but its robustness is achieved at the expense of decreased stability. Trace-driven simulations demonstrate the efficiency of OLCD as well as its superiorities over prior related work.

When filling out privacy-related forms in public places such as hospitals or clinics, people usually are not aware that the sound of their handwriting leaks personal information. In this paper, we explore the possibility of eavesdropping on handwriting via nearby mobile devices based on audio signal processing and machine learning. By presenting a proof-of-concept system, WritingHacker, we show the usage of mobile devices to collect the sound of victims' handwriting, and to extract handwriting-specific features for machine learning based analysis. WritingHacker focuses on the situation where the victim's handwriting follows certain print style. An attacker can keep a mobile device, such as a common smartphone, touching the desk used by the victim to record the audio signals of handwriting. Then, the system can provide a word-level estimate for the content of the handwriting. To reduce the impacts of various writing habits and writing locations, the system utilizes the methods of letter clustering, dictionary filtering and letter time length based offsetting. Moreover, if the relative position between the device and the handwriting is known, a hand motion tracking method can be further applied to enhance the system's performance. Our prototype system's experimental results show that the accuracy of word recognition reaches around 70 - 80 percent under certain conditions, which reveals the danger of privacy leakage through the sound of handwriting.

Data-enabled smart transportation has attracted a surge of interest from machine learning and data mining researchers nowadays due to the bloom of online ride-hailing industry and rapid development of autonomous driving. Large-scale high quality route data and trading data (spatiotemporal data) have been generated every day, which makes AI an urgent need and preferred solution for the decision making in intelligent transportation systems. While a large of amount of work have been dedicated to traditional transportation problems, they are far from satisfactory for the rising need. We propose a half-day workshop at CIKM 2019 for the professionals, researchers, and practitioners who are interested in mining and understanding big and heterogeneous data generated in transportation, and AI applications to improve the transportation system. We plan to have several invited talks from both academia and industry. This workshop would be organized by Shanghai Jiao Tong University, Didi Chuxing and Pennsylvania State University.

Microservice, an architectural design that decomposes applications into loosely coupled services, is adopted in modern software design, including cloud-based scientific workflow processing. The microservice design makes scientific workflow systems more modular, more flexible, and easier to develop. However, cloud deployment of microservice workflow execution systems doesn't come for free, and proper resource management decisions have to be made in order to achieve certain performance objective (e.g., response time) within constraint operation cost. Nevertheless, effective online resource allocation decisions are hard to achieve due to dynamic workloads and the complicated interactions of microservices in each workflow. In this paper, we propose an adaptive resource allocation approach for microservice workflow system based on recent advances in reinforcement learning. Our approach (1) assumes little prior knowledge of the microservice workflow system and does not require any elaborately designed model or crafted representative simulator of the underlying system, and (2) avoids high sample complexity which is a common drawback of model-free reinforcement learning when applied to real-world scenarios. We show that our proposed approach automatically achieves effective policy for resource allocation with limited number of time-consuming interactions with the microservice workflow system. We perform extensive evaluations to validate the effectiveness of our approach and demonstrate that it outperforms existing resource allocation approaches with read-world emulated workflows.

The recent proliferation of human-carried mobile devices has given rise to mobile crowd sensing (MCS) systems, where a myriad of data requesters outsource their sensing tasks to a crowd of workers via a cloud-based platform. In order to incentivize participation, requesters typically compensate workers with specific amount of payments. Clearly, setting an appropriate task price is critical for a requester to attract enough worker participation without unnecessary expenses. Therefore, we investigate the problem of task pricing in MCS systems with multi-requester price competition, and also dynamically arriving workers. Task pricing in such scenario is challenging, because of each requester's incomplete information about the others, uncertainty of future information, etc. So as to address these challenges, we use Markov game to model requesters' competitive task pricing, and Markov correlated equilibrium (MCE) as the solution concept. We propose that the platform uses the social cost-minimizing MCE to coordinate requesters' prices, which is self-enforcing, and optimizes the system-wide objective of social cost. Technically, we propose a computationally efficient algorithm to compute an approximately optimal MCE. Furthermore, through extensive performance evaluation, we show numerically that our algorithm yields close-to-minimum social cost in very short running time.

360 video streaming is gaining popularity because of the new type of experience it creates. Tile-based approaches have been widely used in VoD 360 video streaming to save the network bandwidth. However, they cannot be extended to the case of live streaming because they assume the 360 videos stitched offline before streaming. Instead, stitching has to be done in real-time in live 360 video streaming. More importantly, the stitching speed as shown in our experiments is one order of magnitude lower than the network transmission speed, making stitching more of a deciding factor of the overall frame rate than the network transmission speed. In this paper, we design a stitching algorithm for tile-based live 360 video streaming that adapts stitching quality to make the best use of the timing budget. There are two main challenges. First, existing tile-based approaches do not consider various semantic information in different scenarios. Second, the decision of tiling schemes for tile-based stitching is non-trivial. To solve the above two challenges, we present an event-driven stitching algorithm for tile-based 360 video live streaming, which consists of such an event-driven model to abstract various semantic information as events and a tile actuator to make tiling scheme decisions. We implement a streaming system based on event-driven stitching called LiveTexture. To evaluate the proposed algorithm, we compare LiveTexture with other baseline systems and show that LiveTexture adapts well to various timing budgets by meeting 89.4% of the timing constraints. We also demonstrate that LiveTexture utilizes the timing budget more efficiently than others.

Traffic signal control is an emerging application scenario for reinforcement learning. Besides being as an important problem that affects people's daily life in commuting, traffic signal control poses its unique challenges for reinforcement learning in terms of adapting to dynamic traffic environment and coordinating thousands of agents including vehicles and pedestrians. A key factor in the success of modern reinforcement learning relies on a good simulator to generate a large number of data samples for learning. The most commonly used open-source traffic simulator SUMO is, however, not scalable to large road network and large traffic flow, which hinders the study of reinforcement learning on traffic scenarios. This motivates us to create a new traffic simulator CityFlow with fundamentally optimized data structures and efficient algorithms. CityFlow can support flexible definitions for road network and traffic flow based on synthetic and real-world data. It also provides user-friendly interface for reinforcement learning. Most importantly, CityFlow is more than twenty times faster than SUMO and is capable of supporting city-wide traffic simulation with an interactive render for monitoring. Besides traffic signal control, CityFlow could serve as the base for other transportation studies and can create new possibilities to test machine learning methods in the intelligent transportation domain.

Recent years have witnessed the emergence of mobile crowd sensing (MCS) systems, which leverage the public crowd equipped with various mobile devices for large scale sensing tasks. In this paper, we study a critical problem in MCS systems, namely, incentivizing worker participation. Different from existing work, we propose an incentive framework for MCS systems, named Thanos, that incorporates a crucial metric, called workers' quality of information (QoI). Due to various factors (e.g., sensor quality and environment noise), the quality of the sensory data contributed by individual workers varies significantly. Obtaining high quality data with little expense is always the ideal of MCS platforms. Technically, our design of Thanos is based on reverse combinatorial auctions. We investigate both the single- and multi-minded combinatorial auction models. For the former, we design a truthful, individual rational, and computationally efficient mechanism that ensures a close-to-optimal social welfare. For the latter, we design an iterative descending mechanism that satisfies individual rationality and computational efficiency, and approximately maximizes the social welfare with a guaranteed approximation ratio. Through extensive simulations, we validate our theoretical analysis on the various desirable properties guaranteed by Thanos.

The recent proliferation of human-carried mobile devices has given rise to mobile crowd sensing (MCS) systems that outsource sensory data collection to the public crowd. In order to identify truthful values from (crowd) workers' noisy or even conflicting sensory data, truth discovery algorithms, which jointly estimate workers' data quality and the underlying truths through quality-aware data aggregation, have drawn significant attention. However, the power of these algorithms could not be fully unleashed in MCS systems, unless workers' strategic reduction of their sensing effort is properly tackled. To address this issue, in this paper, we propose a payment mechanism, named Theseus, that deals with workers' such strategic behavior, and incentivizes high-effort sensing from workers. We ensure that, at the Bayesian Nash Equilibrium of the non-cooperative game induced by Theseus, all participating workers will spend their maximum possible effort on sensing, which improves their data quality. As a result, the aggregated results calculated subsequently by truth discovery algorithms based on workers' data will be highly accurate. Additionally, Theseus bears other desirable properties, including individual rationality and budget feasibility. We validate the desirable properties of Theseus through theoretical analysis, as well as extensive simulations.

Recent years have witnessed the success of mobile crowd sensing systems, which outsource sensory data collection to the public crowd equipped with various mobile devices in a wide spectrum of civilian applications. We envision that crowd sensing could as well be very useful in a whole host of mission-driven scenarios, such as peacekeeping operations, non-combatant evacuations, and humanitarian missions. However, the power of crowd sensing could not be fully unleashed in mission-driven crowd sensing (MiCS) systems, unless workers are effectively incentivized to participate. Therefore, in this paper, taking into consideration workers' diverse quality of information (QoI), we propose Squadron, a quality-aware incentive mechanism for MiCS systems. Squadron adopts the reverse auction framework. It approximately minimizes the platform's total payment for worker recruiting in a computationally efficient manner, and recruits workers who potentially could provide high quality data. Furthermore, it also satisfies the desirable properties of truth-fulness and individual rationality. Through rigorous theoretical analysis, as well as extensive simulations, we validate the various aforementioned desirable properties held by Squadron.

Currently, the surveillance camera-based person re-identification is still challenging because of diverse factors such as people’s changing poses and various illumination. The various poses make it hard to conduct feature matching across images, and the illumination changes make color-based features unreliable. In this article, we present SKEPRID, 1 a skeleton-based person re-identification method that handles strong pose and illumination changes jointly. To reduce the impacts of pose changes on re-identification, we estimate the joints’ positions of a person based on the deep learning technique and thus make it possible to extract features on specific body parts with high accuracy. Based on the skeleton information, we design a set of local color comparison-based cloth-type features, which are resistant to various lighting conditions. Moreover, to better evaluate SKEPRID, we build the PO8LI 2 dataset, which has large pose and illumination diversity. Our experimental results show that SKEPRID outperforms state-of-the-art approaches in the case of strong pose and illumination variation.

The recent proliferation of increasingly capable mobile devices has given rise to mobile crowd sensing (MCS) systems that outsource the collection of sensory data to a crowd of participating workers that carry various mobile devices. Aware of the paramount importance of effectively incentivizing participation in such systems, the research community has proposed a wide variety of incentive mechanisms. However, different from most of these existing mechanisms which assume the existence of only one data requester, we consider MCS systems with multiple data requesters, which are actually more common in practice. Specifically, our incentive mechanism is based on double auction, and is able to stimulate the participation of both data requesters and workers. In real practice, the incentive mechanism is typically not an isolated module, but interacts with the data aggregation mechanism that aggregates workers' data. For this reason, we propose CENTURION, a novel integrated framework for multi-requester MCS systems, consisting of the aforementioned incentive and data aggregation mechanism. CENTURION's incentive mechanism satisfies truthfulness, individual rationality, computational efficiency, as well as guaranteeing non-negative social welfare, and its data aggregation mechanism generates highly accurate aggregated results. The desirable properties of CENTURION are validated through both theoretical analysis and extensive simulations.

The recent proliferation of human-carried mobile devices has given rise to mobile crowd sensing (MCS) systems that outsource sensory data collection to the public crowd. In order to identify truthful values from (crowd) workers' noisy or even conflicting sensory data, truth discovery algorithms, which jointly estimate workers' data quality and the underlying truths through quality-aware data aggregation, have drawn significant attention. However, the power of these algorithms could not be fully unleashed in MCS systems, unless workers' strategic reduction of their sensing effort is properly tackled. To address this issue, in this paper, we propose a payment mechanism, named Theseus, that deals with workers' such strategic behavior, and incentivizes high-effort sensing from workers. We ensure that, at the Bayesian Nash Equilibrium of the non-cooperative game induced by Theseus, all participating workers will spend their maximum possible effort on sensing, which improves their data quality. As a result, the aggregated results calculated subsequently by truth discovery algorithms based on workers' data will be highly accurate. Additionally, Theseus bears other desirable properties, including individual rationality and budget feasibility. We validate the desirable properties of Theseus through theoretical analysis, as well as extensive simulations.

When filling out privacy-related forms in public places such as hospitals or clinics, people usually are not aware that the sound of their handwriting leaks personal information. In this paper, we explore the possibility of eavesdropping on handwriting via nearby mobile devices based on audio signal processing and machine learning. By presenting a proof-of-concept system, WritingHacker, we show the usage of mobile devices to collect the sound of victims' handwriting, and to extract handwriting-specific features for machine learning based analysis. WritingHacker focuses on the situation where the victim's handwriting follows certain print style. An attacker can keep a mobile device, such as a common smart-phone, touching the desk used by the victim to record the audio signals of handwriting. Then the system can provide a word-level estimate for the content of the handwriting. To reduce the impacts of various writing habits and writing locations, the system utilizes the methods of letter clustering and dictionary filtering. Our prototype system's experimental results show that the accuracy of word recognition reaches around 50% - 60% under certain conditions, which reveals the danger of privacy leakage through the sound of handwriting.

Recent years have witnessed the proliferation of mobile crowd sensing (MCS) systems that leverage the public crowd equipped with various mobile devices (e.g., smartphones, smartglasses, smartwatches) for large scale sensing tasks. Because of the importance of incentivizing worker participation in such MCS systems, several auction-based incentive mechanisms have been proposed in past literature. However, these mechanisms fail to consider the preservation of workers' bid privacy. Therefore, different from prior work, we propose a differentially private incentive mechanism that preserves the privacy of each worker's bid against the other honest-but-curious workers. The motivation of this design comes from the concern that a worker's bid usually contains her private information that should not be disclosed. We design our incentive mechanism based on the single-minded reverse combinatorial auction. Specifically, we design a differentially private, approximately truthful, individual rational, and computationally efficient mechanism that approximately minimizes the platform's total payment with a guaranteed approximation ratio. The advantageous properties of the proposed mechanism are justified through not only rigorous theoretical analysis but also extensive simulations.

The recent proliferation of human-carried mobile devices has given rise to mobile crowd sensing (MCS) systems that outsource the collection of sensory data to the public crowd equipped with various mobile devices. A fundamental issue in such systems is to effectively incentivize worker participation. However, instead of being an isolated module, the incentive mechanism usually interacts with other components which may affect its performance, such as data aggregation component that aggregates workers' data and data perturbation component that protects workers' privacy. Therefore, different from past literature, we capture such interactive effect, and propose INCEPTION, a novel MCS system framework that integrates an incentive, a data aggregation, and a data perturbation mechanism. Specifically, its incentive mechanism selects workers who are more likely to provide reliable data, and compensates their costs for both sensing and privacy leakage. Its data aggregation mechanism also incorporates workers' reliability to generate highly accurate aggregated results, and its data perturbation mechanism ensures satisfactory protection for workers' privacy and desirable accuracy for the final perturbed results. We validate the desirable properties of INCEPTION through theoretical analysis, as well as extensive simulations.

Recent years have witnessed the emergence of mobile crowd sensing (MCS) systems, which leverage the public crowd equipped with various mobile devices for large scale sensing tasks. In this paper, we study a critical problem in MCS systems, namely, incentivizing user participation. Different from existing work, we incorporate a crucial metric, called users' quality of information (QoI), into our incentive mechanisms for MCS systems. Due to various factors (e.g., sensor quality, noise, etc.) the quality of the sensory data contributed by individual users varies significantly. Obtaining high quality data with little expense is always the ideal of MCS platforms. Technically, we design incentive mechanisms based on reverse combinatorial auctions. We investigate both the single-minded and multi-minded combinatorial auction models. For the former, we design a truthful, individual rational and computationally efficient mechanism that approximately maximizes the social welfare with a guaranteed approximation ratio. For the latter, we design an iterative descending mechanism that achieves close-to-optimal social welfare while satisfying individual rationality and computational efficiency. Through extensive simulations, we validate our theoretical analysis about the close-to-optimal social welfare and fast running time of our mechanisms.

The paper describes a novel algorithm for timely sensor data retrieval in resource-poor environments under freshness constraints. Consider a civil unrest, national security, or disaster management scenario, where a dynamic situation evolves and a decision-maker must decide on a course of action in view of latest data. Since the situation changes, so is the best course of action. The scenario offers two interesting constraints. First, one should be able to successfully compute the course of action within some appropriate time window, which we call the decision deadline. Second, at the time the course of action is computed, the data it is based on must be fresh (i.e., within some corresponding validity interval). We call it the freshness constraint. These constraints create an interesting novel problem of timely data retrieval. We address this problem in resource-scarce environments, where network resource limitations require that data objects (e.g., pictures and other sensor measurements pertinent to the decision) generally remain at the sources. Hence, one must decide on (i) which objects to retrieve and (ii) in what order, such that the cost of deciding on a valid course of action is minimized while meeting data freshness and decision deadline constraints. Such an algorithm is reported in this paper. The algorithm is shown in simulation to reduce the cost of data retrieval compared to a host of baselines that consider time or resource constraints. It is applied in the context of minimizing cost of finding unobstructed routes between specified locations in a disaster zone by retrieving data on the health of individual route segments.

In mission-based mobile environments such as airplane maintenance, workflow-based mobile sensor networks emerge, where mobile users (MUs) with sensing devices visit sequences of mission-driven locations defined by workflows, and demand the gathering of sensory data within mission durations. To satisfy this demand in a cost-efficient manner, mobile access point (AP) deployment needs to be part of the overall solution. Therefore, we study the mobile AP deployment in workflow-based mobile sensor networks. We categorize MUs' workflows according to a priori knowledge of MUs' staying durations at mission locations into complete and incomplete information workflows. In both categories, we formulate the cost-minimizing mobile AP deployment problem into multiple (mixed) integer optimization problems, satisfying MUs' QoS constraints. We prove that the formulated optimization problems are NP-hard and design approximation algorithms with guaranteed approximation ratios. We demonstrate using simulations that the AP deployment cost calculated using our algorithms is 50-60% less than the stationary baseline approach and fairly close to the optimal AP deployment cost. In addition, the run times of our approximation algorithms are only 10-25% of those of the branch-and-bound algorithm used to derive the optimal AP deployment cost.

Market based spectrum trading has been extensively studied to realize efficient spectrum utilization in cognitive radio networks (CRNs). In this paper, we utilize the concept of insurance in spectrum trading so as to improve spectrum efficiency in CRNs. We show that by additionally purchasing a specifically designed insurance contract from a PU, an SU can improve its utility since it will be insured against the potential accident, i.e., transmission failure incurred by excessively low SINR. Therefore insurance provides SUs more incentive to purchase PUs' channels and spectrum utilization in CRNs can be improved. In this paper, the original spectrum market including multiple PUs and multiple SUs are modeled as a hybrid market consisting of a spectrum market and an insurance market. In this hybrid market PUs serve as spectrum sellers as well as insurers and SUs act as spectrum buyers as well as insureds. We further model the hybrid market game as a four-stage Bayesian game between PUs and SUs. We characterize the second-best Pareto optimal (SBPO) market allocations and players' perfect Bayesian equilibrium (PBE) strategies. Furthermore, through extensive simulation, we have demonstrated that at the PBE, high risk and low risk SUs will respectively experience improvement in their utilities for approximately 23.5% and 4.6%.

In this paper, we deal with possible data transmission congestion on the sink node in wireless sensor networks (WSNs). We consider a scenario in which all the sensor nodes have a certain amount of storage space and acquire data from the surroundings at heterogeneous speed. Because receiving bandwidth of the sink node is limited, a proper bandwidth allocation mechanism should be implemented to avoid possible congestion or data loss due to the overflow of some sensor nodes. To address this problem, we firstly design a novel bandwidth allocation mechanism, SWM, that can maximize the social utility, an indicator of every sensor node's satisfaction degree and the social fairness. Furthermore, we model the allocation process under the SWM as a noncooperative game and figure out the unique Nash Equilibrium. The uniqueness of the equilibrium demonstrates that this network will actually approach to a fair and stable state.