Federated Deep Reinforcement Learning (FDRL) aims to enable distributed collaborative training of multiple DRL models while preserving privacy. Existing FDRL methods function in static client environments, but real-world scenarios often involve dynamic state transitions, such as noise, which render static model topologies inadequate and result in biased policy loss. This degrades client performance and leads to suboptimal global policies. To address this challenge, we develop a generic solution, referred to as the self-regulating training framework, which can be seamlessly integrated into existing FDRL approaches to address dynamic state transitions. Specifically, we propose a Sparse Training (ST) method that dynamically sparsifies and adjusts the topology of each model during training to maximize model performance and reduce model complexity. Additionally, we introduce an auxiliary model to adaptively regulate the policy loss of client models, mitigating loss bias and facilitating updates that yield improved returns. Experimental results demonstrate that our method enhances six state-of-the-art (SOTA) FDRL approaches across nine tasks in terms of return.

Cooperation among human-driven vehicles (HVs) is essential for traffic safety and efficiency. However, the emergence of autonomous vehicles (AVs) has prompted a new question: Will HVs still cooperate with AVs? Prior studies and narrative reviews yielded inconsistent findings. To answer this question, we conducted the first systematic review and meta-analysis of HV–AV cooperation, synthesizing evidence from 24 articles, 27 samples, 32 effect sizes, and 5,778 participants. Results revealed that people drive less cooperatively when interacting with AVs than with HVs (Hedges’ g = − 0.19, 95% CI [ − 0.31, − 0.07]). The meta-regression revealed a significant link between cooperative driving and the year of publication, with more recent studies showing more cooperation; other moderators (e.g., data collection methods) were not significant. We discuss the implications of less cooperation for AV development, traffic regulations, and human–AI cooperation, and current challenges in theory, replicability, and ecological validity, in addition to offering recommendations for future research.

While autonomous vehicles (AVs) could transform transportation, their “black box” nature often leaves occupants unaware of the rationale for their actions. Providing explanations can enhance transparency and facilitate widespread AV adoption. This study investigated scenario (when) and human factors (who) that influence the Demand of Explanations (DoE) to ensure explanations are provided when needed, followed by exploring the reasons (why) behind these demands. We conducted an online experimental study among 440 participants, who viewed 36 simulated driving scenarios, varying in AV actions, driving styles, time/weather and traffic environments. Results of multilevel and qualitative analysis showed that: (1) DoE was significantly higher when AVs drove aggressively, in urban areas, during turning and merging, and in nighttime or rain; (2) participants who had lower trust in AVs and older adults significantly demanded more explanations; and (3) safety and traffic rules were the primary reasons for seeking explanations.

Deep Reinforcement Learning (DRL) methods have shown remarkable success in many applications, yet their high energy consumption limits their practicability. Recent studies incorporated energy-efficient Spiking Neural Networks (SNNs) to build Spiking DRL methods and lower energy consumption by setting a shorter simulation duration for SNNs to compute fewer gradients. However, these existing Spiking DRL methods fail to sample sufficient high-quality samples within a fixed-size replay buffer and perform poorly when the simulation duration is small, introducing the challenging tradeoff between energy consumption and model performance. Motivated by such observations, we develop a generic resilient experience replay method that can be seamlessly integrated into existing spiking DRL methods to effectively address the above tradeoff. Specifically, we allow the replay buffer to dynamically expand as the number of training samples increases, thereby accommodating more potentially valuable candidate samples for policy training. Meanwhile, we introduce an adaptive approach to manage the buffer size by determining when to shrink the replay buffer and removing redundant samples automatically. This strategy prevents the buffer from expanding unnecessarily, thereby mitigating the potential negative impact on model performance. Extensive experimental results demonstrate that our approach significantly enhances the performance of five state-of-the-art (SOTA) spiking DRL methods across various simulation durations in sixteen tasks, in terms of return, without compromising their energy efficiency.

In the field of Deep reinforcement learning (DRL), enhancing exploration capabilities and improving the accuracy of Q-value estimation remain two major challenges. Recently, double-actor DRL methods have emerged as a promising class of DRL approaches, achieving substantial advancements in both exploration and Q-value estimation. However, existing double-actor DRL methods feature actors that operate independently in exploring the environment, lacking mutual learning and collaboration, which leads to suboptimal policies. To address this challenge, this work proposes a generic solution that can be seamlessly integrated into existing double-actor DRL methods by promoting mutual learning among the actors to develop improved policies. Specifically, we calculate the difference in actions output by the actors and minimize this difference as a loss during training to facilitate mutual imitation among the actors. Simultaneously, we also minimize the differences in Q-values output by the various critics as part of the loss, thereby avoiding significant discrepancies in value estimation for the imitated actions. We present two specific implementations of our method and extend these implementations beyond double-actor DRL methods to other DRL approaches to encourage broader adoption. Experimental results demonstrate that our method significantly improves twenty state-of-the-art (SOTA) DRL methods, including SOTA double-actor DRL methods, across eleven tasks, as measured by return and other metrics.

With the increasing adoption of autonomous vehicles, ensuring the reliability of autonomous driving systems (ADSs) deployed on autonomous vehicles has become a significant concern. Driving simulators have emerged as crucial platforms for testing ADSs, offering realistic, dynamic, and configurable environments. However, existing simulation-based ADS testers have largely overlooked the reliability of the simulators, potentially leading to overlooked violation scenarios and subsequent safety security risks during real-world deployment. In our investigations, we identified that collision detectors in simulators could fail to detect and report collisions in certain collision scenarios, referred to asignored collision scenarios. This paper aims to systematically discover ignored collision scenarios to improve the reliability of autonomous driving (AD) simulators. To this end, we present ICSFuzz, a black-box fuzzing approach to discover ignored collision scenarios efficiently. Drawing upon the fact that the ignored collision scenarios are a sub-type of collision scenarios, our approach starts with the determined collision scenarios. Following the guidance provided by empirically studied factors contributing to collisions, we selectively mutate arbitrary collision scenarios in a step-wise manner toward the ignored collision scenarios and effectively discover them. We compare ICSFuzz with multiple state-of-the-art simulation-based ADS testing methods, by replacing their oracle with our ignored-collision-aware oracle. The evaluation demonstrates that ICSFuzz outperforms ADS testers by finding 7~40x more ignored collision scenarios with a 10~105x speedup. Within the discovered ignored collision scenarios, there are two more types of ignored collision scenarios that ADS testers did not find. All the discovered ignored collisions have been confirmed by developers with one CVE ID assigned.

Autonomous Driving Systems (ADS) are critical components of Intelligent Transportation Systems (ITS), where vehicle-level reliability has a direct bearing on road traffic safety. Evaluating ADS performance in complex environments remains challenging due to the absence of test oracles and the heavy reliance on deep learning. To address these challenges, this study proposes a novel metamorphic testing framework tailored for vision-based ADS. First, causal inference is employed to extract key environmental factors from high-dimensional observational traffic data, thereby reducing the test space. Second, a multi-objective optimization algorithm integrating causal counterfactual reasoning is developed to quantify the challenges associated with specific combinations of causal factors, enabling cost-effective exploration of test conditions. Third, low-risk source images are systematically transformed into hazardous driving scenes through a fine-tuned diffusion model, allowing ADS evaluation to be guided by metamorphic relations (MRs). Empirical experiments show that the proposed method achieves a higher fault detection ratio than the strongest baseline in four out of five ADS models, with relative gains ranging from 18.1% to 88.9%. Data augmentation experiments further demonstrate that incorporating MR-violating test cases can reduce ADS prediction errors by up to 13.67%, with these benefits preserved in real-world road traffic datasets through domain adaptation. This study highlights a new pathway for validating the reliability of vision-based ADS driven by deep learning, thereby supporting the deployment of safer road transportation. The source code for our methods and baselines is available athttps://github.com/SafeDL/AutoMetTest

Digital twin (DT) technology enables smooth integrations of cyber and physical worlds in alignment with the Industry 4.0 initiative. DTs are virtual presentations of physical objects. Through synchronizations with physical objects in real-time, DTs can reflect the states of their objects with high fidelity. Orthogonal to the DT technology, mobile edge computing (MEC) is a promising computing paradigm that shifts computing power to the edge network, which is appropriate for delay-sensitive intelligent services. In this paper, we study fidelity-aware inference services in a DT-assisted MEC environment, where machine learning-based inference models must be continuously retrained using updated DT data in order to provide high-fidelity services for consumers. To this end, we first formulate two novel optimization problems: the initial DT and model placement problem with the aim of minimizing the total cost of various resources consumed, and the cumulative fidelity maximization problem to maximize the long-term cumulative fidelity of service models while minimizing the cost of resource consumption on service model fidelity enhancements over a given time horizon, through jointly scheduling mobile devices to upload their update data to synchronize with their DTs and determining whether DTs and/or models to be migrated at each time slot. We then develop an efficient algorithm for the initial DT and model placement problem, through a reduction to a series of minimum-cost maximum matching problems in auxiliary graphs. We also devise an online algorithm with a provable competitive ratio for the cumulative fidelity maximization problem, by designing an elegant service request admission strategy. Finally, we evaluate the performance of the proposed algorithms via simulations. Simulation results demonstrate that the proposed algorithms are promising, and outperform their baselines by no less than 28%.

The Internet of Things (IoT) is gathering paces in the new era of Industry 4.0, and the Digital Twin (DT) technology bridges the gap between the bursting amounts of data generated by IoT devices and the user requirements for real-time data processing. DT services maintain living digital models of physical objects, and a DT network enables comprehensive service provisioning with the global knowledge of a group of DTs. On the other hand, exposing serverless computing at network edges, the recent advances in Mobile Edge Computing (MEC) introduce new inspirations to the DT landscape that ensure fine-grained resource management and low network-wide delay of DT services. However, social relationships among IoT devices and DT data privacy impact DT orchestrations. In this paper, we first design a differential privacy-based federated learning framework to build a DT network for DT services in response to user requests in an MEC, thereby enhancing the Quality of Services (QoS). Built upon the proposed framework, we then formulate two novel social-aware DT placement problems: the static social-aware S_DT placement problem, and the dynamic social-aware S_DT placement problem, respectively. We also show the NP-hardness of the defined problems. Then, we formulate an Integer Linear Program (ILP) solution to the static social-aware S_DT placement problem when the problem size is small; otherwise we develop an approximation algorithm with a provable approximation ratio for it. Third, we study the dynamic social-aware S_DT placement problem when requests arrive one by one without the knowledge of future request arrivals over the time horizon, for which we devise an online algorithm with a provable competitive ratio. Finally, we conduct simulations to evaluate the performance of the proposed algorithms. Simulation results show that the proposed algorithms outperform their counterparts, improving the performance compared with their baselines by no less than 14.9%.

High-definition (HD) maps provide precise environmental information essential for prediction and planning in autonomous driving (AD) systems. Due to the high cost of labeling and maintenance, recent research has turned to online HD map construction using onboard sensor data, offering wider coverage and more timely updates for autonomous vehicles (AVs). However, the robustness of online map construction under adversarial conditions remains underexplored. In this paper, we present a systematic vulnerability analysis of online map construction models, which reveals that these models exhibit an inherent bias toward predicting symmetric road structures. In asymmetric scenes like forks or merges, this bias often causes the model to mistakenly predict a straight boundary that mirrors the opposite side. We demonstrate that this vulnerability persists in the real-world and can be reliably triggered by obstruction or targeted interference. Leveraging this vulnerability, we propose a novel two-stage attack framework capable of manipulating online constructed maps. First, our method identifies vulnerable asymmetric scenes along the victim AV's potential route. Then, we optimize the location and pattern of camera-blinding attacks and adversarial patch attacks. Evaluations on a public AD dataset demonstrate that our attacks can degrade mapping accuracy by up to 9.9% in average precision, render up to 44% of targeted routes unreachable, and increase unsafe planned trajectory rates—colliding with real-world road boundaries—by up to 27%. These attacks are also validated on a real-world testbed vehicle. We further analyze root causes of the symmetry bias, attributing them to training data imbalance, model architecture, and map element representation. Based on these findings, we propose asymmetric data fine-tuning as a targeted defense, which significantly improves model robustness. To the best of our knowledge, this study presents the first vulnerability assessment of online map construction models and introduces the first digital and physical attack against them.

Anticipating the multimodality of future events lays the foundation for safe autonomous driving. However, multimodal motion prediction for traffic agents has been clouded by the lack of multimodal ground truth. Existing works predominantly adopt the winner-take-all training strategy to tackle this challenge, yet still suffer from limited trajectory diversity and uncalibrated mode confidence. While some approaches address these limitations by generating excessive trajectory candidates, they necessitate a postprocessing stage to identify the most representative modes, a process lacking universal principles and compromising trajectory accuracy. We are thus motivated to introduce ModeSeq, a new multimodal prediction paradigm that models modes as sequences. Unlike the common practice of decoding multiple plausible trajectories in one shot, ModeSeq requires motion decoders to infer the next mode step by step, thereby more explicitly capturing the correlation between modes and significantly enhancing the ability to reason about multimodality. Leveraging the inductive bias of sequential mode prediction, we also propose the EarlyMatch-Take-All (EMTA) training strategy to diversify the trajectories further. Without relying on dense mode prediction or heuristic post-processing, ModeSeq considerably improves the diversity of multimodal output while attaining satisfactory trajectory accuracy, resulting in balanced performance on motion prediction benchmarks. Moreover, ModeSeq naturally emerges with the capability of mode extrapolation, which supports forecasting more behavior modes when the future is highly uncertain.

Deep learning has revolutionized autonomous driving; nevertheless, its inherent opacity hinders explainability, an essential requirement for public trust and regulatory approval. Existing explainable autonomous driving research typically employs a multi-task framework, simultaneously generating driving actions and their corresponding explanations (collectively called categories). Most methods use a two-stage approach: extracting category-related features and modeling category correlations separately. This separation overlooks the potential synergy between these two processes. Moreover, existing approaches often rely on simple linear combinations of task-specific losses, which may fail to optimally balance action and explanation objectives. To address these limitations, we propose Dual-Attention with Multi-Objective optimization (DAMO). DAMO introduces a dual-attention mechanism that alternates between cross-attention for category representation learning and self-attention for category correlation modeling, fostering mutual enhancement. Additionally, we devise a multi-objective optimization algorithm that dynamically balances tasks and achieves Pareto optimality with theoretical guarantees. Extensive evaluations on two benchmarks show that DAMO surpasses state-of-the-art baselines and a large vision-language model, delivering up to 13.9% performance improvement and enhanced generalization across diverse driving scenarios.

Stereo matching achieves significant progress with iterative algorithms like RAFT-Stereo and IGEV-Stereo. However, these methods struggle in ill-posed regions with occlusions, textureless, or repetitive patterns, due to a lack of global context and geometric information for effective iterative refinement. To enable the existing iterative approaches to incorporate global context, we propose the Global Regulation and Excitation via Attention Tuning (GREAT) framework which encompasses three attention modules. Specifically, Spatial Attention (SA) captures the global context within the spatial dimension, Matching Attention (MA) extracts global context along epipolar lines, and Volume Attention (VA) works in conjunction with SA and MA to construct a more robust cost-volume excited by global context and geometric details. To verify the universality and effectiveness of this framework, we integrate it into several representative iterative stereo-matching methods and validate it through extensive experiments, collectively denoted as GREAT-Stereo. This framework demonstrates superior performance in challenging ill-posed regions. Applied to IGEV-Stereo, among all published methods, our GREAT-IGEV ranks first on the Scene Flow test set, KITTI 2015, and ETH3D leaderboards, and achieves second on the Middlebury benchmark. Code is available at https://github.com/JarvisLee0423/GREAT-Stereo.

Collaborative perception, fusing information from multiple agents, can extend perception range so as to improve perception performance. However, temporal asynchrony in real-world environments, caused by communication delays, clock misalignment, or sampling configuration differences, can lead to information mismatches. If this is not well handled, then the collaborative performance is patchy, and what's worse safety accidents may occur. To tackle this challenge, we propose CoDynTrust, an uncertainty-encoded asynchronous fusion perception framework that is robust to the information mismatches caused by temporal asynchrony. CoDynTrust generates dynamic feature trust modulus (DFTM) for each region of interest by modeling aleatoric and epistemic uncertainty as well as selectively suppressing or retaining single-vehicle features, thereby mitigating information mismatches. We then design a multi-scale fusion module to handle multi-scale feature maps processed by DFTM. Compared to existing works that also consider asynchronous collaborative perception, CoDynTrust combats various low-quality information in temporally asynchronous scenarios and allows uncertainty to be propagated to downstream tasks such as planning and control. Experimental results demonstrate that CoDynTrust significantly reduces performance degradation caused by temporal asynchrony across multiple datasets, achieving state-of-the-art detection performance even with temporal asynchrony. The code is available at https://github.com/CrazyShout/CoDynTrust.

To avoid dangerous situations, such as collisions in dynamic environments, autonomous vehicles must predict the risks of the current scene to take safe actions. Traditional rule-based risk prediction methods and existing reinforcement learning (RL) approaches, which typically rely on manually designed driving decision rules or heuristic reward functions, often fail to capture the complexity of real-world dangerous scenarios, leading to suboptimal and unsafe driving decisions. To address this limitation, we develop a novel RL method, called Group Opinion Risk-Aware Reinforcement Learning (GORA-RL), for safer driving decisions that align with real-world conditions. Specifically, we first introduce surveys of human drivers to assess risk in real-world driving situations. Using these real group opinions as training data, we train a risk prediction model, referred to as the risk prediction model with a Transformer (RPT), that captures the crucial characteristics of these scenarios, resulting in more realistic and reliable risk predictions. This model is then integrated as a reward function to train an RL algorithm for making driving decisions in various scenarios. The experiments validate that our approach outperforms two state-of-the-art (SOTA) methods in challenging congested scenarios, such as merging and intersections, in terms of reward and several other metrics. Project site: https://github.com/naiyisiji/RPT.

As end-to-end autonomous driving advances toward real-world deployment, ensuring the safety of autonomous vehicles (AVs) has become a critical requirement for their commercial viability. While rule-based AVs have traditionally undergone rigorous testing in both real-world and simulated environments before deployment, data-driven autonomous models are typically trained on real-world datasets, limiting their generalization to simulation environments. This poses a significant challenge for the development and testing of end-to-end autonomous driving. To address this issue, we propose Retrieval-Augmented Learning for Autonomous Driving (RALAD), a novel framework designed to bridge the real-to-sim gap in a cost-effective manner. RALAD consists of three key components: (1) domain adaptation via an enhanced Optimal Transport (OT) method, which retrieves the most similar scenarios between real and simulated environments; (2) feature fusion across similar scenarios, enabling the construction of a feature mapping between real-world and simulated domains; and (3) feature extraction freezing with fine-tuning on the fused features, allowing the model to learn simulation-specific characteristics through feature mapping. We evaluate RALAD on three monocular 3D object detection models, and the results demonstrate that our approach significantly improves model accuracy in simulation. Additionally, we use real autonomous vehicle for testing in real-world scenarios, and have established simulated scenes similar to reality for further testing, which illustrate the effectiveness of our method.

Synchronization-induced congestion is a critical performance bottleneck in modern distributed machine learning (ML) training, where simultaneous gradient exchanges create bursty traffic patterns. Existing solutions, both reactive and proactive, struggle to balance throughput and latency in the presence of synchronized flows. We propose DeSync, a proactive traffic shaping scheme that introduces structured random delay to de-synchronize communication rounds. Evaluations with DCQCN, HPCC, DCTCP, and TIMELY demonstrate that DeSync significantly improves FCT, job completion times, and congestion metrics, enhancing existing CC mechanisms without specialized hardware.

Monitoring the Mean Opinion Score (MOS) of video conferencing is critical for Internet Service Providers (ISPs) to ensure user satisfaction. However, a significant technical challenge arises: MOS is a subjective measure, while ISPs primarily rely on deep packet inspection (DPI) data for performance monitoring, making direct mapping between MOS and DPI data nearly impossible. To address this gap, we develop DePI-MOSE, a novel solution that leverages sub-application-level video context clues to build machine-learning models. By inferring the type of end devices and identifying the motion level within video content during a conference session, DePI-MOSE can estimate MOS values from DPI data accurately. We implemented and tested DePI-MOSE in a real-world ISP network, and experimental results show that DePI-MOSE is more accurate than state-of-the-art methods. We also built a network resource management platform for ISPs to dynamically adjust users' network resources by precisely monitoring users' video conferencing QoE.

Infrastructure-assisted autonomous driving has emerged as a pivotal technology to overcome the challenges posed by occlusions and limited fields of view for individual vehicles. Vehicles can fuse perception information from the infrastructure with their own in real-time, thereby enhancing their perception ability. However, our real-world experiments demonstrate that such an approach could introduce artifacts such as ghost objects, resulting in unsafe and unreliable planning outcomes. Besides, the system integration complexity and communication overhead are typically considerable, posing challenges to practical deployment. Therefore, we propose VI-Planning, an innovative infrastructure-assisted system that effectively optimizes autonomous vehicle planning in real time. The core idea of VI-Planning is to leverage the scene-level future occupancy grid maps constructed by the infrastructure as future drivable area references to directly optimize planning outcomes of autonomous vehicles. Since VI-Planning operates only at the autonomous vehicle's final output stage, without modifying the vehicle's underlying system architecture, it can be plug-and-play for most autonomous driving systems, whether they are modular or end-to-end architectures. Moreover, VI-Planning employs a novel bitwise encoding mechanism to efficiently compress these maps, enabling practical transmission. We implement VI-Planning end-to-end on a real-world testbed. The results of closed-loop and open-loop experiments indicate that VI-Planning can achieve real-time planning optimization (62.54 ms on average) and 817 × data transmission efficiency compared to the state-of-the-art baseline. A video demo of VI-Planning on our real-world testbed is available at: https://youtu.be/DXl5BhDEvFQ.

We propose VI-Planning, an innovative system that leverages the scene-level future occupancy grid maps predicted by the infrastructure as future drivable area references to directly optimize the planning trajectories of autonomous vehicles in real time. Since VI-Planning operates only at the autonomous vehicle's final output stage, without modifying the underlying system architecture, it can be plug-and-play for most autonomous driving systems. Moreover, VI-Planning employs a novel bitwise encoding mechanism to efficiently compress these maps, enabling practical transmission. The experimental results demonstrate that VI-Planning can achieve real-time planning optimization with extremely low bandwidth consumption, significantly enhancing the driving safety of autonomous systems. The source code and video demonstration of VI-Planning are available on GitHub: https://github.com/YANG-Deep/VI-Planning.

We propose VI-Planning, an innovative system that leverages the scene-level future occupancy grid maps predicted by the infrastructure as future drivable area references to directly optimize the planning trajectories of autonomous vehicles in real time. Since VI-Planning operates only at the autonomous vehicle's final output stage, without modifying the underlying system architecture, it can be plug-and-play for most autonomous driving systems. Moreover, VI-Planning employs a novel bitwise encoding mechanism to efficiently compress these maps, enabling practical transmission. The experimental results demonstrate that VI-Planning can achieve real-time planning optimization with extremely low bandwidth consumption, significantly enhancing the driving safety of autonomous systems. The source code and video demonstration of VI-Planning are available on GitHub: https://github.com/YANG-Deep/VI-Planning.

Adversarial attacks with real objects or lasers on car-borne LiDAR-based object detection are concerning. The existing defense approaches are often designed to address specific attacks and short of considering adaptive attackers who may adapt based on all available information about the deployed defense to maximize attack effect. This paper proposes Hyper3Def, a new defense for the function of detecting vehicle objects, which uses a Hypernet to generate an ensemble of multiple new detection models when needed at run time. The detection results of these models are fused to give the final result. As a dynamic defense, Hyper3Def revokes an important basis of the adaptive attack, i.e., the object detection model is needed to plan effective adversarial perturbations. Evaluation based on open data and real-world experiments with embedded system implementation show that, when confronting adaptive attacks, Hyper3Def outperforms various baseline defenses including the adversarial training, which is often cited as the state of the art.

Safety validation, which assesses the safety of an autonomous system's motion planning decisions, is critical for the safe deployment of autonomous vehicles. Existing input validation techniques from other machine learning domains, such as image classification, face unique challenges in motion planning due to its contextual properties, including complex inputs and one-to-many mapping. Furthermore, current output validation methods in autonomous driving primarily focus on open-loop trajectory prediction, which is ill-suited for the closed-loop nature of motion planning. We introduce REDOUBT, the first systematic safety validation framework for autonomous vehicle motion planning that employs a duo mechanism, simultaneously inspecting input distributions and output uncertainty. REDOUBT identifies previously overlooked unsafe modes arising from the interplay of In-Distribution/Out-of-Distribution (OOD) scenarios and certain/uncertain planning decisions. We develop specialized solutions for both OOD detection via latent flow matching and decision uncertainty estimation via an energy-based approach. Our extensive experiments demonstrate that both modules outperform existing approaches, under both open-loop and closed-loop evaluation settings. Our codes are available at: https://github.com/sgNicola/Redoubt.

In automated warehouses, efficient management and economic benefits hinge on the effective scheduling of automated guided vehicles (AGVs) to transport diverse packets. Emerging technologies such as artificial intelligence and automation control have greatly contributed to the development of packet transport schemes for AGVs. However, the development of the logistics industry results in a massive amount of packets with diverse deadlines, which brings new challenges for the AGV scheduling system. To address this, this paper treats each AGV as an agent and designs a novel hierarchical transformer reinforcement learning (HTRL) framework to generate efficient AGV scheduling policies. Specifically, this framework consists of one encoder and two decoders to produce the packet selection and path improvement actions. These two decoders are equipped with masked self-attention mechanisms to learn efficient packet selection and path improvement policies, facilitating AGV transport efficiency to meet the deadlines of packets. Moreover, we consider the kinetic features of AGVs and design a model predictive control (MPC)-based speed control method for AGVs to prevent frequent stop-and-wait of AGVs and enhance their transport efficiency. We build up a simulated warehouse environment containing packets with different deadlines and conduct extensive experiments. Experimental results validate that the proposed HTRL framework increases the delivered packets within expiration by up to 36.6% compared to other baselines.

With the growing need for a robust network backbone to ensure uninterrupted connectivity in the face of large-scale natural disasters, we introduce the Risk Zone-Diversified Network Design (RZDD) problem. This problem requires diverse paths between source-destination pairs to be risk zone-disjoint, preventing any single disaster from disrupting overall network connectivity. Unlike previous research, we propose an innovative cost framework that considers geographically overlapping links and long-term maintenance costs, providing a comprehensive approach to cost analysis. We prove the intractability of the RZDD problem and present the Risk Zone-Diversified Network Design Algorithm (RZDD-Algorithm). In small-scale networks with a single source-destination pair, our algorithm achieves optimal outcomes. Comparative analysis shows that our method reduces costs by an average of 24% compared to an SRLG algorithm that does not consider the preference of geographically overlapping links. For multiple pairs, our approach maintains a gap ratio within 4% and 7% of optimal solutions. Furthermore, experimental evaluations on large networks demonstrate reductions of 26% and 31% compared to the SRLG baseline for single pairs. We also showcase the efficiency of our method in designing large-scale networks with multiple pairs.

Adaptive Traffic Signal Control (ATSC) has become a popular research topic in intelligent transportation systems. Regional Traffic Signal Control (RTSC) using the Multi-agent Deep Reinforcement Learning (MADRL) technique has become a promising approach for ATSC due to its ability to achieve the optimum trade-off between scalability and optimality. Most existing RTSC approaches partition a traffic network into several disjoint regions, followed by applying centralized reinforcement learning techniques to each region. However, the pursuit of cooperation among RTSC agents still remains an open issue and no communication strategy for RTSC agents has been investigated. In this paper, we propose communication strategies to capture the correlation of micro-traffic states among lanes and the correlation of macro-traffic states among intersections. We first justify that the evolution equation of the RTSC process is Markovian via a system of store-and-forward queues. Next, based on the evolution equation, we propose two GAT-Aggregated (GA2) communication modules—GA2-Naive and GA2-Aug to extract both intra-region and inter-region correlations between macro and micro traffic states. While GA2-Naive only considers the movements at each intersection, GA2-Aug also considers the lane-changing behavior of vehicles. Two proposed communication modules are then aggregated into two existing novel RTSC frameworks—RegionLight and Regional-DRL. Experimental results demonstrate that both GA2-Naive and GA2-Aug effectively improve the performance of existing RTSC frameworks under both real and synthetic scenarios. Hyperparameter testing also reveals the robustness and potential of our communication modules in large-scale traffic networks.

Effective multi-intersection collaboration is crucial for mitigating urban traffic congestion through reinforcement learning (RL)-based traffic signal control (TSC). Existing work mainly considers scenarios involving a single vehicle type, where cooperation is typically limited to neighboring intersections. However, in urban traffic scenarios where high priority vehicles coexist with ordinary vehicles, considering only a limited number of neighboring nodes may be insufficient to ensure the swift passage of high priority vehicles while minimizing the impact on overall traffic efficiency. Therefore, we formulate the multiple intersections’ decision-making process in urban scenarios as a Markov game and propose a novel centralized cooperative RL framework called MATLIT to solve the game. Specifically, we adopt a multi-agent transformer (MAT)-based architecture that facilitates efficient global cooperation among intersections. The attention mechanism and auto-regressive process of the MAT effectively mitigate the curse of the dimensionality problem, which guarantees MATLIT to tackle large-scale traffic scenarios. Meanwhile, the stability and sequence action generation capacity of the MAT-based architecture is further enhanced by incorporating MAT with a gated mechanism. Furthermore, considering the inherent topological constraints in urban traffic scenarios, we utilize graph attention networks (GATs) to capture graph-structured mutual influences. Additionally, in response to the urban traffic scenarios with various types of high priority vehicles that have time-varying priorities, we integrate the soft actor-critic (SAC) algorithm to enhance the exploration capabilities of our framework, allowing it to learn robust strategies in heterogeneous traffic conditions. Extensive experiments demonstrate that our proposed MATLIT framework outperforms all baselines and can reduce high priority vehicles’ waiting time by 24.57% while reducing the average waiting time of all vehicles by 18.51% in realistic urban scenarios.

Video streaming systems are critical for intelligent applications to transmit video data from end devices to servers for real-time analysis. In contrast to traditional human-centric streaming systems, which prioritize user-perceived metrics, machine-centric streaming systems are designed to continuously provide fresh and accurate information for analytics purposes. Although numerous studies have investigated policies to optimize streaming performance, most of them employ the segment-by-segment streaming framework from human-centric systems. Through comprehensive theoretical analysis and experimentation, we uncover that the segmented streaming approach is sub-optimal for machine-centric streaming systems compared to the straightforward frame-by-frame streaming approach. Furthermore, instead of relying on conventional frame-level metrics, we introduce a novel metric called the Age of Semantic Information (AoSI) to evaluate the performance of analytics-oriented streaming systems. This metric balances the quantity and timeliness of the semantic information. Consequently, we propose a compression ratio adaption method tailored to optimize AoSI performance for frame-by-frame streaming systems. This method leverages a deep learning (DL)-based predictor to discover the dynamic, latent relationships between compression and inference accuracy. Evaluated on actual streaming prototypes and real-world datasets, our method significantly surpasses both segmented and frame-by-frame baseline methods in terms of worst-case and average AoSI performance.

Unmanned aerial vehicles (UAVs) play a critical role in disaster response, swiftly gathering information from various points-of-interest (PoIs) across extensive areas. The freshness of this information is measured by the age of information (AoI), representing the time since the latest information acquisition of a specific PoI. However, devising AoI-minimizing routes for UAVs in obstructed post-disaster environments poses unique challenges that have yet to be fully overcome. Obstacles, like post-disaster barriers, can impede direct flight paths between PoIs, and limited battery life requires energy-conscious route planning. Additionally, existing solutions fail to universally minimize varying data freshness requirements. This research addresses the AoI-driven UAV travel problem, seeking to establish periodic routes that optimize AoI metrics while considering energy and general graph constraints. We develop a learning-based algorithm to enhance the current route iteratively, utilizing guidance from a deep reinforcement learning (DRL) agent and executing a series of operations to potentially decrease AoI while adhering to topological and energy constraints. The algorithm is validated on real post-disaster datasets, demonstrating significant improvements in various AoI metrics compared to other learning-based approaches. Furthermore, our algorithm outperforms approximation algorithms and can approach the global optimum when tailored to existing AoI-minimizing problems.

Lifelong deep reinforcement learning (DRL) approaches are commonly employed to adapt continuously to new tasks without forgetting previously acquired knowledge. While current lifelong DRL methods have shown promising advancements in retaining acquired knowledge, they suffer from significant adaptation efforts (i.e., longer training duration) and suboptimal policy when transferring to a new task that significantly deviates from previously learned tasks, a phenomenon known as the few-shot generalization challenge. In this work, we propose a generic approach that equips existing lifelong DRL methods with the capability of few-shot generalization. First, we employ selective experience reuse by leveraging the experience of encountered states, improving adaptation training for new tasks. Then, a relaxed softmax function is applied to the target Q values to improve the accuracy of evaluated Q values, leading to more optimal policies. Finally, we measure and reduce the discrepancy in data distribution between the policy and off-policy samples, resulting in improved adaptation efficiency. Extensive experiments have been conducted on three typical benchmarks to compare our approach with six representative lifelong DRL methods and two state-of-the-art (SOTA) few-shot DRL methods regarding their training speed, episode return, and average return of all episodes. Experimental results substantiate that our method improves the return of six lifelong DRL methods by at least 25%.

Deep reinforcement learning (DRL) has been widely adopted in various applications, yet it faces practical limitations due to high storage and computational demands. Dynamic sparse training (DST) has recently emerged as a prominent approach to reduce these demands during training and inference phases, but existing DST methods achieve high sparsity levels by sacrificing policy performance as they rely on the absolute magnitude of connections for pruning and randomly generating connections. Addressing this, our study presents a generic method that can be seamlessly integrated into existing DST methods in DRL to enhance their policy performance while preserving their sparsity levels. Specifically, we develop a novel method for calculating the importance of connections within the model. Subsequently, we dynamically adjust the sparse network topology by dropping existing connections and introducing new connections based on their respective importance values. Through validation on eight widely used simulation tasks, our method improves two state-of-the-art (SOTA) DST approaches by up to 70% in episode return and average return across all episodes under various sparsity levels.

Deep reinforcement learning (DRL) has been widely applied to various applications, but improving the exploration and the accuracy of Q-value estimation remain key challenges. Recently, the double-actor architecture has emerged as a promising DRL framework that can enhance both exploration and Q-value estimation. Existing double-actor DRL methods sample from the replay buffer to update the two actors; however, the samples used to update each actor are generated by its previous versions and the other actor, resulting in a different data distribution compared with the current actor being updated, which can negatively impact the actor's update and lead to suboptimal policies. To this end, this work proposes a generic solution that can be seamlessly integrated into existing double-actor DRL methods to mitigate the adverse effects of data distribution differences on actor updates, thereby learning better policies. Specifically, we decompose the updates of double-actor DRL methods into two stages, each of which uses the same sampling approach to train a pair of actor-critic. This sampling approach classifies the samples in the replay buffer into distinct categories using a clustering technique, such as K-means, and subsequently employs the Jensen-Shannon (JS) divergence to evaluate the distributional differences between each sample category and the actor currently being updated. Samples are then prioritized from the categories with smaller distribution differences to the current actor to update it. In this way, we can effectively mitigate the distribution difference between the samples and the current actor being updated. Experiments demonstrate that our method enhances the performance of five state-of-the-art (SOTA) double-actor DRL methods and outperforms eight SOTA single-actor DRL methods across eight tasks.

Deep reinforcement learning (DRL) methods, which train a policy to obtain the sequence of actions required to complete a task, have achieved remarkable success across diverse applications. It is a long-standing open issue in the DRL community to make the trained policy gradually approach the theoretically globally optimal policy, and existing research has also explored several challenges, such as exploration-exploitation, to improve the quality of the obtained policy. However, most DRL methods rely solely on the current state for decision-making, leading to short-sightedness and suboptimal learning. To overcome this, we propose a neighboring state-aware policy that enhances existing DRL methods by incorporating a neighboring state sequence in the decision-making process. Specifically, our approach saves multiple past and future states and concatenates them as the neighboring state sequence, along with the current state, and inputs them to the actor to generate an action during the training process. This global perspective, provided by neighboring states, is similar to human decision-making and helps the agent better understand state evolution, leading to improved policy learning. We present two specific implementations of our approach and demonstrate through extensive experiments that it effectively enhances ten representative DRL methods across nine tasks, based on three metrics, including return.

Information freshness, measured by the Age-of-Information (AoI) metric, is a crucial aspect of conventional network systems. However, the emergence of the Artificial Intelligence of Things (AIoT) introduces unique requirements for assessing information freshness, rendering the traditional AoI definition inadequate. This is because the traditional AoI metric operates under the presumption that each data packet bears equal significance. In contrast, AIoT systems must prioritize the transmission of event summaries from smart IoT devices. To promptly capture events as they occur at the sources, we propose a novel information freshness metric called Age of Event (AoE). Subsequently, we thoroughly investigate the problem of AoE-minimizing transmission scheduling. This issue presents a formidable challenge because the event occurrence pattern can be unpredictable, and more crucially, the base station only becomes aware of these occurrences post-transmission. In response, we formulate algorithms and conduct a theoretical analysis applicable to scenarios characterized by complete, zero, or partial knowledge of event occurrences. Evaluations performed on a real traffic event dataset reveal that even in the absence of complete knowledge, our algorithms exhibit competitive performance when compared against the clairvoyant benchmark and markedly outperform AoI baselines.

Lifelong deep reinforcement learning (DRL) methods enable continuous adaptation to new tasks and retention of old knowledge. However, these methods often necessitate large model sizes, leading to substantial computational and storage resource requirements during training and inference. Unfortunately, existing research has not yet provided a lightweight solution to address this issue. This work aims to develop a generic method that can be seamlessly integrated into existing lifelong DRL methods to facilitate their achievement of lightweight models while also yielding higher returns. While sparse training (ST) methods have been extensively used in the DRL community to achieve lightweight models, they exacerbate the issue of catastrophic forgetting and compromise generalization when applied in lifelong DRL. To improve generalization, we develop a gradient optimization method that leverages sharpness-aware minimization (SAM) to smooth the gradient surface of the model without introducing excessive computational complexity. In addition, to alleviate catastrophic forgetting and promote model convergence, we introduce a priority-based approach that samples effective past experiences from the replay buffer. Extensive experiments demonstrate that our approach achieves 90% sparsity in five representative lifelong DRL methods while achieving higher episode return and average return (up to 34% improvement) across all episodes compared to the dense models.

Recent studies have extensively explored the causal connections between emotions and their underlying causes in textual data. Most research aims to identify clauses within documents that are causally related. However, these studies have overlooked the fact that such causal relationships are often context-dependent and valid only within specific contextual clauses. To bridge this gap, we present a novel task of determining the presence of a valid causal relationship between a given pair of emotion and cause clauses in different contexts, while also identifying the specific contextual clauses involved. Since this task is novel and lacks an existing dataset for testing, we manually annotate a benchmark dataset to obtain labels for our task and classify the types of context clauses, which can also be beneficial for other applications. By leveraging negative sampling, we create a balanced final dataset that includes documents with and without causal relationships. Building upon this dataset, we propose an end-to-end multi-task framework that incorporates two innovative modules aimed at achieving the objectives of our task. We introduce a context masking module to identify the contextual clauses that contribute to causal relationships and a prediction aggregation module to refine predictions by determining the reliance of emotion and cause clauses on specific contextual clauses. Extensive comparative experiments and ablation studies validate the effectiveness and robustness of our proposed framework. The annotated dataset provides a novel way for exploring complex reasoning in causal analysis.

Autonomous driving systems rely on precise trajectory prediction for safe and efficient motion planning. Despite considerable efforts to enhance prediction accuracy, inherent uncertainties persist due to data noise and incomplete observations. Many strategies entail formalizing prediction outcomes into distributions and utilizing variance to represent uncertainty. However, our experimental investigation reveals that existing trajectory prediction models yield unreliable uncertainty estimates, necessitating additional customized calibration processes. On the other hand, directly applying current calibration techniques to prediction outputs may yield sub-optimal results due to using a universal scaler for all predictions and neglecting informative data cues. In this paper, we propose Customized Calibration Temperature with Regularizer (CCTR), a generic framework that calibrates the output distribution. Specifically, CCTR 1) employs a calibration-based regularizer to align output variance with the discrepancy between prediction and ground truth and 2) generates a tailor-made temperature scaler for each prediction using a post-processing network guided by context and historical information. Extensive evaluation involving multiple prediction and planning methods demonstrates the superiority of CCTR over existing calibration algorithms and uncertainty-aware methods, with significant improvements of 11%-22% in calibration quality and 17%-46% in motion planning.

With the capability of intelligent control and communicating with surrounding vehicles and infrastructures, connected and automated vehicles (CAVs) can drive cooperatively and have more positive effects on traffic efficiency. Cooperative and real-time path planning for CAVs stands as a pivotal solution to mitigate traffic congestion and augment travel efficiency. However, most of the existing path planning schemes predominantly concentrate on minimizing the travel times of vehicles, sidelining the broader issue of alleviating traffic congestion in urban settings. Therefore, in this paper, we propose a novel collaborative vehicle path planning scheme, leveraging the intelligent control and the communicating ability of CAVs. The primary objective is to reduce traffic congestion within the overall transportation system and improve traffic efficiency. Specifically, we focus on a general urban scenario with various types of vehicles, including CAVs, connected vehicles (CVs), and traditional human-driven vehicles (TVs), To enhance traffic efficiency in such a scenario, we design a collaborative path planning scheme to discover the efficient paths for both CAVs as well as CVs. In this scheme, we treat each CAV as an agent and formulate the multiple CAVs' path-planning problem as a Markov game. To solve the above Markov game, we design a multi-agent convolutional attention reinforcement learning (MACA) framework to generate paths with minimal travel time for CAVs. More concretely, the proposed MACA framework incorporates a convolutional neural network (CNN) layer to capture spatial correlation behind traffic conditions. Additionally, a graph attention network (GAT) layer is employed to integrate the influence of neighboring agents during the path-planning process. To further reduce traffic congestion, we extend the MACA framework into a collaborative MACA (C-MACA) scheme in vehicular networks, where CAVs are empowered to periodically broadcast their path information to surrounding CVs, providing valuable insights for their path planning. Subsequently, to prevent new congestion caused by the aggregation of CVs, we design a heuristic algorithm for CVs to make informed path decisions. We build up a simulator based on a real-world city road map and conduct extensive experiments. The experimental results demonstrate that the proposed scheme can decrease CVs' travel time by up to 10.9 % and reduce the average queue length around junctions by up to 6.5 % over several state-of-the-art approaches, without sacrificing the travel efficiency of CAVs.

Despite considerable advancements in specialized hardware, the majority of IoT edge devices still rely on CPUs. The burgeoning number of IoT users amplifies the challenges associated with performing multiple Deep Neural Network inferences on these resource-limited, CPU-only edge devices. Existing strategies, including model compression, hardware acceleration, and model partitioning, often involve a trade-off in inference accuracy, are unsuitable due to hardware specificity, or lead to inefficient resource utilization. In response to these challenges, this paper introduces L-PIC (Latency Minimized Parallel Inference on CPU)—a framework expressly devised to optimize resource allocation, decrease inference latency, and maintain result accuracy on CPU-only edge devices. A series of comprehensive experiments have verified the superior efficiency and effectiveness of the L-PIC framework in comparison to the state-of-the-art method. Remarkably, compared to the state-of-the-art method, L-PIC can reduce the inference latency of multi-DNN by an average of approximately 30% across all tested scenarios.

In distributed matrix multiplication, stragglers present a significant challenge. Coding techniques are often employed to mitigate this issue; however, their effectiveness is typically limited to handling a fixed number of stragglers. To address the issue of a fluctuating number of stragglers, we propose a novel approach that leverages a variant of Luby transform (LT) codes for distributed matrix multiplication, augmented with a feedback mechanism. This enables the system to tolerate a variable number of stragglers, potentially reducing the redundant computation to complete the task compared with existing coding methods dealing with a fixed number of strangers. Furthermore, we comprehensively analyze the computational complexity associated with the proposed algorithm.

Industrial networks require deterministic and reliable communication, which can be achieved by Time-Sensitive Networking (TSN), a set of standards that enable precise timing and synchronization of data transmission. However, TSN is susceptible to unexpected delays caused by device malfunction, interference or cyber attacks, which can have a domino effect and disrupt multiple data flows. To address this challenge, we propose RobustTSN, a framework that protects TSN against the domino effect of delayed frames and tolerates harmless accident frames using Per-Stream Filtering and Policing (PSFP) mechanism. We develop algorithms to calculate ingress filtering schedules based on local-safe delay and global-safe interval concepts, which decide whether to accept or discard out-of-schedule frames. We use a finite state machine to model the interaction between frames and evaluate frame safety. We build a software-defined networking based system to dynamically monitor network states and reconfigure device filtering after out-of-schedule transmission occurs. We conduct experiments on practical scenario topologies and large groups of random flows to demonstrate the effectiveness and efficiency of our framework.

The Internet of Things (IoT) is gathering paces in the new era of Industry 4.0, and the Digital Twin (DT) technology bridges the gap between the bursting amounts of data generated by IoT devices and the user requirements for real-time data processing. DT services maintain living digital models of physical objects, and a DT network enables comprehensive service provisioning with the global knowledge of a group of DTs. On the other hand, exposing serverless computing in network edges, the recent advances in Serverless Edge Computing (SEC) introduce new inspirations to the DT landscape that ensure fine-grained resource management and low network-wide delay of DT services. However, social relationships among IoT devices and DT data privacy impact the orchestration of DTs. In this paper, we design a differential privacy-based federated learning framework to build a DT network for DT services in response to user DT service requests in SEC, thereby enhancing the Quality of Services (QoS). To this end, we first formulate a novel social-aware problem for placing DTs in an SEC network, and show its NP-hardness. We then provide an Integer Linear Program (ILP) solution to the problem when the problem size is small; otherwise, we design an approximation algorithm with a provable approximation ratio. We finally evaluate the algorithm performance through simulations. Simulation results demonstrate the proposed algorithm is promising, which improves by no less than 21.1 % of the performance of benchmarks.

Simulating realistic behaviors of traffic agents is pivotal for efficiently validating the safety of autonomous driving systems. Existing data-driven simulators primarily use an encoder-decoder architecture to encode the historical trajectories before decoding the future. However, the heterogeneity between encoders and decoders complicates the models, and the manual separation of historical and future trajectories leads to low data utilization. Given these limitations, we propose BehaviorGPT, a homogeneous and fully autoregressive Transformer designed to simulate the sequential behavior of multiple agents. Crucially, our approach discards the traditional separation between "history" and "future" by modeling each time step as the "current" one for motion generation, leading to a simpler, more parameter- and data-efficient agent simulator. We further introduce the Next-Patch Prediction Paradigm (NP3) to mitigate the negative effects of autoregressive modeling, in which models are trained to reason at the patch level of trajectories and capture long-range spatial-temporal interactions. Despite having merely 3M model parameters, BehaviorGPT won first place in the 2024 Waymo Open Sim Agents Challenge with a realism score of 0.7473 and a minADE score of 1.4147, demonstrating its exceptional performance in traffic agent simulation.

This work aims to design a real-time inference scheduler that delivers accurate and timely edge inference ser-vices for dynamic inference arrivals by leveraging dynamic batching and early-exiting techniques. Specifically, we consider an edge inference server that is preinstalled with multiple early-exit Deep Neural Networks (DNNs) that support batch processing. The in-ference tasks with strict deadline requirements arrive at the edge server randomly, and the utility of each timely processed task depends on the achieved accuracy. Therefore, we aim to design an edge inference scheduler that maximizes the system's total utility subject to resource and deadline constraints. We present this problem's mixed integer linear programming formulation. This problem is challenging due to high computational complexity, coupled-decision making, and task randomness. We propose to decompose the original problem into two sub-problems: the task assignment problem and the DNN configuration problem. For the task assignment problem, we develop a greedy task assignment algorithm. For the DNN configuration problem, we propose a Deep Reinforcement Learning-based solution. Simulation results show that the proposed algorithms outperform the state-of-the-art baselines.

MOTIVATION: Genome sequencing technologies reveal a huge amount of genomic sequences. Neural network-based methods can be prime candidates for retrieving insights from these sequences because of their applicability to large and diverse datasets. However, the highly variable lengths of genome sequences severely impair the presentation of sequences as input to the neural network. Genetic variations further complicate tasks that involve sequence comparison or alignment. RESULTS: Inspired by the theory and applications of "spaced seeds," we propose a graph representation of genome sequences called "gapped pattern graph." These graphs can be transformed through a Graph Convolutional Network to form lower-dimensional embeddings for downstream tasks. On the basis of the gapped pattern graphs, we implemented a neural network model and demonstrated its performance on diverse tasks involving microbe and mammalian genome data. Our method consistently outperformed all the other state-of-the-art methods across various metrics on all tasks, especially for the sequences with limited homology to the training data. In addition, our model was able to identify distinct gapped pattern signatures from the sequences. AVAILABILITY AND IMPLEMENTATION: The framework is available at https://github.com/deepomicslab/GCNFrame.

In the domain of Time-Sensitive Networking (TSN), the quest for ultra-reliable low-latency communication is paramount. Current scheduling strategies, which hinge on strict isolation to ensure low latency and jitter, confront the challenges of high overhead in worst-case latency evaluation and consequent limitations in network flow capacity. This paper introduces an innovative framework that transcends traditional isolation constraints, thereby expanding the solution space and augmenting network schedulability. At the heart of this framework lies a novel latency jitter analysis method that assesses the viability of non-isolation scenarios with constant time complexity. This method underpins a heuristic scheduling algorithm that not only boasts the smallest time complexity among existing heuristics but also significantly increases the number of scheduled flows. Complementing this, we integrate a discrete time reference approach to hasten time-intensive scheduling operations, achieving an optimal balance between schedulability and runtime efficiency. The framework further incorporates a workload-shifting technique to enhance online scheduling responsiveness. It adeptly manages the variability in scheduling times caused by disharmonious flow periods, further bolstering the framework’s robustness. Experimental validations demonstrate that our framework can increase the scheduled flows up to 269%. It reduces scheduling runtime by up to 98.44% for medium-scale networks while maintaining a flat runtime growth curve, ensuring predictable performance in online scheduling scenarios.

This work studies the Age-of-Information (AoI) optimization problem in the information-gathering wireless network systems, where time-sensitive data updates are collected from multiple information sources, and each source is equipped with a battery and harvests energy from ambient energy, such as solar, wind, etc. The arrival of the harvested energy can be modeled as the stochastic process, and an information source can deliver its data update only when 1) there is energy in the battery, and 2) this source is selected to transmit its data update based on the transmission policy. This work analyzes how the energy arrival pattern of each source and the transmission policy jointly influence the average AoI among multiple sources. To the best of our knowledge, this is the first work that formally develops the closed-form expression of average AoI in the Stationary Randomized Sampling (SRS) policy space and proposes approximation schemes with constant ratios in multi-source systems under a stochastic energy harvesting model. More specifically, under the perfect wireless channel, the closed-form expression of AoI under the SRS policy space with arbitrary finite battery size is developed. Based on the result, we propose the Max Energy-Aware Weight (MEAW) policy, which is proven to achieve 2-approximation in the full policy space. Under the uncertain wireless channel, we develop the closed-form expression of Whittle’s index to address the target problem. Based on the result, we propose the Energy-aware Whittle’s index policy (EWIP) and prove its approximate performance by using the Lyapunov optimization techniques. Experimental results show that MEAW under the perfect channel setting and EWIP under the uncertain channel setting both perform close to the theoretical lower bound and outperform the state-of-the-art schemes.

Driven by data and models, the digital twin technique presents a new concept of optimizing system design, process monitoring, decision-making and more, through performing comprehensive virtual-reality interaction and continuous mapping. By introducing serverless computing to Mobile Edge Computing (MEC) environments, the emerging serverless edge computing paradigm facilitates the communication-efficient digital twin services and promises agile, fine-grained and cost-efficient provisioning of limited edge resources, where serverless functions are implemented by containers in cloudlets (edge servers). However, the nonnegligible cold start delay of containers deteriorates the responsiveness of digital twin services dramatically and the perceived user service experience. In this paper, we investigate delay-sensitive query service provisioning in digital twin-empowered serverless edge computing by considering user mobility. With digital twins of users deployed in the remote cloud, referred to as primary digital twins, we deploy their digital twin replicas based on serverless functions in cloudlets to mitigate the query service delay while enhancing user service satisfaction that is expressed as a utility function. We study two optimization problems with the aim of maximizing the accumulative utility gain: the digital twin replica placement problem per time slot, and the dynamic digital twin replica placement problem over a finite time horizon. We first formulate an Integer Linear Program (ILP) solution for the digital twin replica placement problem when the problem size is small; otherwise, we propose an approximation algorithm for the problem with a provable approximation ratio. We then design an online algorithm for the dynamic digital twin replica placement problem, and a performance-guaranteed online algorithm for a special case of the problem by assuming each user issues a query at each time slot. Finally, we evaluate the performance of the proposed algorithms for placing digital twin replicas in MEC networks through simulations. The results demonstrate the proposed algorithms are promising, outperforming their counterparts.

In recent years,Coded Edge Computing(CEC) has been greatly studied as a promising technology to effectively mitigate the impact of stragglers and provide confidentiality in edge collaborative computing. It is crucial to verify the correctness of both intermediate results and the final result especially in untrustable and unreliable edge computing scenarios. However, the existing works on verification in CEC always verify and directly discard the whole incorrect intermediate results. In this paper, we propose thePartial Decode and Compare(PDC) verification scheme, which can fully utilize the correct part in the incorrect intermediate results to reduce the complexity and tolerate more abnormal edge devices. The PDC verification scheme consists of two parts:Final Result Verification(FRV) andAbnormal Edge Device Identification(AEDI). By deeply analyzing the decoding impact of the intermediate results on the final result, the PDC verification scheme divides the intermediate results and final results intosubresult vectors. It decodes, compares, and verifies the final result in units of subresult vectors. In this way, the obtained parts which verified to be correct do not need to participate in the following verification. Therefore, it can significantly reduce the verification overhead including both the number of required decoding rounds and the complexity of each decoding round. Based on the correct final result verified by the PDC verification scheme, we also propose anAbnormal Edge Devices Identificationscheme to identify all abnormal edge devices that return incorrect intermediate results. We then present extensive theoretical analyses and simulation experiments of the PDC verification scheme, which demonstrates that the PDC verification scheme can tolerate a higher ratio of incorrect intermediate results and achieve lower verification overhead than the state-of-the-art verification works. Therefore, the proposed PDC verification scheme enables CEC to provide reliable services in unstable and unreliable edge computing scenarios.

Voltage stability assessment is essential for maintaining reliable power grid operations. Stability assessment approaches using deep learning address the shortfalls of the traditional time-domain simulation-based approaches caused by increased system complexity. However, deep learning models are shown to be vulnerable to adversarial examples in the field of computer vision. While this vulnerability has been noticed by the power grid cybersecurity research, the domain-specific analysis on the requirements imposed upon effective attack implementation is still lacking. Although these attack requirements are usually reasonable in computer vision tasks, they can be stringent in the context of power grids. In this paper, we conduct a systematic investigation on the attack requirements and credibility of six representative adversarial example attacks based on a voltage stability assessment application for the New England 10-machine 39-bus power system. We show that (1) compromising about half the transmission system buses’ voltage traces is a rule-of-thumb attack requirement; (2) the universal adversarial perturbations regardless of the original clean voltage trajectory possess the same credibility as the widely studied false data injection attacks on power grid state estimation, while the input-specific adversarial perturbations are less credible; (3) the prevailing strong adversarial training thwarts the universal perturbations but fails in defending certain input-specific perturbations. To advance defense to cope with both universal and input-specific adversarial examples, we propose a new approach that simultaneously estimates the predictive uncertainty of any given input of voltage trajectory and thwarts the attacks effectively.

Multi-agent reinforcement learning (MARL) has proven effective in training multi-robot confrontation, such as StarCraft and robot soccer games. However, the current joint action policies utilized in MARL have been unsuccessful in recognizing and preventing actions that often lead to failures on our side. This exacerbates the cooperation dilemma, ultimately resulting in our agents acting independently and being defeated individually by their opponents. To tackle this challenge, we propose a novel joint action policy, referred to as the consensus action policy (CAP). Specifically, CAP records the number of times each joint action has caused our side to fail in the past and computes a cooperation tendency, which is integrated with each agent’sQ-value and Nash bargaining solution to determine a joint action. The cooperation tendency promotes team cooperation by selecting joint actions that have a high tendency of cooperation and avoiding actions that may lead to team failure. Moreover, the proposed CAP policy can be extended to partially observable scenarios by combining it with DeepQnetwork or actor-critic–based methods. We conducted extensive experiments to compare the proposed method with seven existing joint action policies, including four commonly used methods and three state-of-the-art methods, in terms of episode rewards, winning rates, and other metrics. Our results demonstrate that this approach holds great promise for multi-robot confrontation scenarios.

In many IoT applications, information needs to be gathered from multiple heterogeneous sources to the base station for real-time processing and follow-up actions. Undoubtedly, information freshness, measured by age of information (AoI), is critical in taking responsive actions. Recent studies have taken AoI into the consideration of transmission scheduling over wireless channels. However, existing studies on guaranteeing AoI either assume error-free wireless channels or priorly known link reliability, which is unrealistic. In this paper, we tackle the AoI-guaranteed transmission scheduling problem over an unreliable channel with the aim of throughput maximization, which is modelled as an AoI-Guaranteed Multi-Armed Bandit (AG-MAB) problem. Since the problem has not been studied in the literature even for the oracle case with given link reliability, we first propose an optimal stationary randomized sampling (SRS) policy for the oracle case. For the AG-MAB problem with unknown link reliability, we propose learning algorithms that meet the AoI requirements with probability 1 and incur sublinear regret compared to Oracle SRS, which can also detect the unsatisfiability of the AoI constraint and switch to the fallback policy promptly with guaranteed accuracy. Numerical results show that our algorithm outperforms the AoI-constraint-aware baselines on throughput with per-source AoI requirement guaranteed.

Digital twins are poised to enter our lives with Industry 4.0. The Digital Twin Network (DTN) paradigm is projected to deliver upon the promise of efficient collaboration among digital twins to enable complicated and systematic services across many domains, through depicting an overall picture of a group of physical objects. To achieve timely data processing of digital twins, Mobile Edge Computing (MEC) shifts the computational power towards the network edge, and network slicing is well-suited to bundle heterogeneous physical resources to build logical networks based on edge servers for accommodating DTNs. In light of this, in this paper we investigate DTN slicing-enabled service provisioning in MEC, where each DTN slice consists of one master digital twin and a set of worker digital twins, and each worker digital twin is synchronized through collecting data from a respective object periodically. The master digital twin aggregates the processed data from worker digital twins to model the DTN continuously for user query services, whilst meeting delay requirements of users. We capture the utility gain of a DTN slicing request based on the DTN model quality at its master digital twin that is impacted by the Age of Information (AoI), and we focus on two novel optimization problems: the utility maximization problem for a single DTN slicing request, and the dynamic utility maximization problem for multiple DTN slicing requests. We propose an approximation algorithm for the former, and an online algorithm with a provable competitive ratio for the latter. We also evaluate the performance of the proposed algorithms through simulations. Experimental results demonstrate that the proposed algorithms are promising, outperforming their counterparts by at least 10.2%.

Propelled by recent advances in Mobile Edge Computing (MEC) and the Internet of Things (IoT), the digital twin technique has been envisioned as a de-facto driving force to bridge the virtual and physical worlds through creating digital portrayals of physical objects. In virtue of the flourishing of edge intelligence and abundant IoT data, data-driven modelling facilitates the implementation and maintenance of digital twins, where simulations of physical objects are usually performed based on Deep Neural Networks (DNNs). A significant advantage of adopting digital twins is to enable decisive prediction on the behaviours of objects in near future without waiting for that really happen. To provide accurate predictions, it is vital to keep each digital twin synchronized with its physical object in real-time. However, it is challenging to maintain the real-time synchronization between a digital twin and its physical object due to the dynamics of physical objects and sensing data drift over time, i.e., the live data from a physical object diverge from the model training data of its digital twin. To address this critical issue, continual learning is a promising solution to retrain models of digital twins incrementally. In this paper, we investigate digital twin synchronization issues via continual learning in an MEC environment, with the aim to maximize the total utility gain, i.e., the enhanced model accuracy. We study two novel optimization problems: the static digital twin synchronization problem per time slot and the dynamic digital twin synchronization problem for a finite time horizon. We first formulate an Integer Linear Program (ILP) solution for the static digital twin synchronization problem when the problem size is small; otherwise, we develop a randomized approximation algorithm at the expense of bounded resource violations for it. We also devise a deterministic approximation algorithm with guaranteed performance for a special case of the static digital twin synchronization problem. We thirdly consider the dynamic digital twin synchronization problem by proposing an efficient online algorithm for it. Finally, we evaluate the performance of the proposed algorithms for continuous digital twin synchronization through simulations. Simulation results show that the proposed algorithms are promising, outperforming counterpart benchmarks by no less than 13.2%, in terms of the total utility gain.

A group ofconnected and autonomous vehicleswith common interests can drive in a cooperative manner, namely cooperative driving. In such a networked control system, an efficient message dissemination scheme is critical for cooperative drivings to periodically broadcast their kinetic status, i.e.,beacon. However, most existing researches are designed for a simple or specific scenario, e.g., ignoring the impacts of the complex communication environment and emerging hybrid traffic scenarios. Worse still, the inevitable message transmission interference and the limited interaction among vehicles in harsh communication environments seriously hinder cooperation among cooperative drivings and deteriorate the beaconing performance. In this paper, we formulate the decision-making process of cooperative drivings as a Markov game. Furthermore, we propose acooperative hierarchical attention reinforcement learning (CHA)framework to solve this Markov game. Specifically, the hierarchical structure of CHA leads cooperative drivings to be foresighted. Besides, we integrate each hierarchical level of CHA separately with graph attention networks to incorporate agents' mutual influences in the decision-making process. Moreover, each hierarchical level learns a cooperative reward function to motivate each agent to cooperate with others under harsh communication conditions. Finally, we set up a simulator and conduct extensive experiments to validate the effectiveness of CHA.

In real-world urban environments, hybrid and disorder traffic brings new challenges for the intelligent traffic light control system (ITLCS). Apart from coordinating traffic flows around intersections, the ITLCS is responsive to ensuring high priority vehicles pass through intersections quickly. To this end, we formulate the multiple intersections’ decision-making problem as a Semi-Markov game and propose amulti-agent attention double actor-critic (MAADAC)framework to solve this game, integrating theoptions frameworkwithgraph attention networks (GATs). Specifically, the options framework empowers agents to learn to make a long sequence of satisfactory decisions, such as keeping a reasonable phase for a short period to ensure high priority vehicles pass through intersections quickly. Besides, we adopt GATs to capture graph-structure mutual influences among agents. We set up a simulator based on real-world city road networks and conduct extensive experiments to evaluate the performance of MAADAC. The experimental results show that MAADAC can reduce high priority vehicles’ waiting time in the interval of 18.16%-38.14% versus the density of vehicles in real-world urban scenarios over several state-of-the-art approaches. Also, our framework can guarantee the passing efficiency of high priority vehicles under various traffic conditions with the change in the proportion of high priority vehicles.

The emerging digital twin technique enhances the network management efficiency and provides comprehensive insights on network performance, through mapping physical objects to their digital twins. The user satisfaction on digital twin-enabled service relies on the freshness of digital twin data, which is measured by the Age of Information (AoI). Due to long service delays, the use of the remote cloud for delay-sensitive service provisioning faces serious challenges. Mobile Edge Computing (MEC), as an ideal paradigm for delay-sensitive services, is able to realize real-time data communication between physical objects and their digital twins at the network edge. However, the mobility of physical objects and dynamics of user query arrivals make seamless service provisioning in MEC become challenging. In this paper, we investigate dynamic digital twin placements for improving user service satisfaction in MEC environments, by introducing a novel metric to measure user service satisfaction based on the AoI concept and formulating two user service satisfaction enhancement problems: the static and dynamic utility maximization problems under static and dynamic digital twin placement schemes. To this end, we first formulate an Integer Linear Programming (ILP) solution to the static utility maximization problem when the problem size is small; otherwise, we propose a performance-guaranteed approximation algorithm. We then propose an online algorithm with a provable competitive ratio for the dynamic utility maximization problem, by considering dynamic user query services. Finally, we evaluate the performance of the proposed algorithms via simulations. Simulation results demonstrate that the proposed algorithms outperform the comparison baseline algorithms, improving the algorithm performance by at least$10.7\%$, compared to the baseline algorithms.

The Mobile Edge Computing (MEC) paradigm gives impetus to the vigorous advancement of the Internet of Things (IoT), through provisioning low-latency computing services at network edges. The emerging digital twin technique has been explosively growing in the IoT community, which bridges the gap between physical objects and their digital representations in an MEC network, enabling real-time monitoring and analysis, simulations on the dynamics of systems, accurate predictions on behaviours of objects, and optimization on network resource allocation. In this paper, we consider AoI-aware query services in an MEC network empowered by digital twin technology for diverse IoT applications. We aim to maximize the weighted sum of the accumulative freshness of query results measured by the Age of Information (AoI) and the total query service delay of admitted requests. To this end, we first formulate a novel minimization problem that explores nontrivial trade-offs between the two conflicting optimization objectives: the freshness of query results and service delays, and we show the NP-hardness of the problem. Then, we propose an approximation algorithm with a provable approximation ratio for the problem, at the expense of bounded computing capacity violations. We also develop a heuristic for the problem without any capacity violations. We finally evaluate the performance of the proposed algorithms via simulations. The simulation results demonstrate that the proposed algorithms are promising, and outperform the comparison benchmarks.

Unmanned Aerial Vehicle (UAV) swarm offers extended coverage and is a vital solution for many applications. A key issue in UAV swarm control is to cover all targets while maintaining connectivity among UAVs, referred to as a multi-target coverage problem. With existing dynamic routing protocols, the flying ad hoc network suffers outdated and incorrect route information due to frequent topology changes. This might lead to failures of time-critical tasks. One mitigation solution is to keep the physical topology unchanged, thus maintaining a fixed communication topology and enabling static routing. However, keeping physical topology unchanged may sacrifice the coverage. In this article, we propose to maintain a fixed communication topology among UAVs, which allows certain changes in physical topology, so that to maximize the coverage. We develop a distributed motion planning algorithm for the online multi-target coverage problem with the constraint of keeping communication topology intact. As the communication topology needs to be timely updated when UAVs leave or arrive at the swarm, we further design a topology-management protocol. Experimental results from the ns-3 simulator show that under our algorithms, UAV swarms of different sizes achieve significantly improved delay and loss ratio, efficient coverage, and rapid topology update.

Predicting the future trajectories of surrounding agents is essential for autonomous vehicles to operate safely. This paper presents QCNet, a modeling framework toward pushing the boundaries of trajectory prediction. First, we identify that the agent-centric modeling scheme used by existing approaches requires re-normalizing and re-encoding the input whenever the observation window slides forward, leading to redundant computations during online prediction. To overcome this limitation and achieve faster inference, we introduce a query-centric paradigm for scene encoding, which enables the reuse of past computations by learning representations independent of the global spacetime coordinate system. Sharing the invariant scene features among all target agents further allows the parallelism of multi-agent trajectory decoding. Second, even given rich encodings of the scene, existing decoding strategies struggle to capture the multimodality inherent in agents' future behavior, especially when the prediction horizon is long. To tackle this challenge, we first employ anchor-free queries to generate trajectory proposals in a recurrent fashion, which allows the model to utilize different scene contexts when decoding waypoints at different horizons. A refinement module then takes the trajectory proposals as anchors and leverages anchor-based queries to refine the trajectories further. By supplying adaptive and high-quality anchors to the refinement module, our query-based decoder can better deal with the multimodality in the output of trajectory prediction. Our approach ranks 1ston Argoverse 1 and Argoverse 2 motion forecasting benchmarks, outperforming all methods on all main metrics by a large margin. Meanwhile, our model can achieve streaming scene encoding and parallel multi-agent decoding thanks to the query-centric design ethos.

Multi-modal fusion has shown initial promising results for object detection of autonomous driving perception. However, many existing fusion schemes do not consider the quality of each fusion input and may suffer from adverse conditions on one or more sensors. While predictive uncertainty has been applied to characterize single-modal object detection performance at run time, incorporating uncertainties into the multi-modal fusion still lacks effective solutions due primarily to the uncertainty’s cross-modal incomparability and distinct sensitivities to various adverse conditions. To fill this gap, this paper proposes Uncertainty-Encoded Mixture-of-Experts (UMoE) that explicitly incorporates single-modal uncertainties into LiDAR-camera fusion. UMoE uses individual expert network to process each sensor’s detection result together with encoded uncertainty. Then, the expert networks’ outputs are analyzed by a gating network to determine the fusion weights. The proposed UMoE module can be integrated into any proposal fusion pipeline. Evaluation shows that UMoE achieves a maximum of 10.67%, 3.17%, and 5.40% performance gain compared with the state-of-the-art proposal-level multi-modal object detectors under extreme weather, adversarial, and blinding attack scenarios.

Graph Neural Networks (GNNs) have boosted the performance for many graph-related tasks. Despite the great success, recent studies have shown that GNNs are still vulnerable to adversarial attacks, where adversaries can mislead the GNNs' prediction by modifying graphs. On the other hand, the explanation of GNNs (GnnExplainer for short) provides a better understanding of a trained GNN model by generating a small subgraph and features that are most influential for its prediction. In this paper, we first perform empirical studies to validate that GnnExplainer can act as an inspection tool and have the potential to detect the adversarial perturbations for graphs. This finding motivates us to further investigate a new problem: Whether a graph neural network and its explanations can be jointly attacked by modifying graphs with malicious desires? It is challenging to answer this question since the goals of adversarial attack and bypassing the GnnExplainer essentially contradict with each other. In this work, we give a confirmative answer for this question by proposing a novel attack framework (GEAttack) for graphs, which can attack both a GNN model and its explanations by exploiting their vulnerabilities simultaneously. To the best of our knowledge, this is the very first effort to attack both GNNs and explanations on graph-structured data for the trustworthiness of GNNs. Comprehensive experiments on various real-world datasets demonstrate the effectiveness of the proposed method.

In autonomous driving, an accurate understanding of environment, e.g., the vehicle-to-vehicle and vehicle-to-lane interactions, plays a critical role in many driving tasks such as trajectory prediction and motion planning. Environment information comes from high-definition (HD) map and historical trajectories of vehicles. Due to the heterogeneity of the map data and trajectory data, many data-driven models for trajectory prediction and motion planning extract vehicle-to-vehicle and vehicle-to-lane interactions in a separate and sequential manner. However, such a manner may capture biased interpretation of interactions, causing lower prediction and planning accuracy. Moreover, separate extraction leads to a complicated model structure and hence the overall efficiency and scalability are sacrificed. To address the above issues, we propose an environment representation, Temporal Occupancy Flow Graph (TOFG). Specifically, the occupancy flow-based representation unifies the map information and vehicle trajectories into a homogeneous data format and enables a consistent prediction. The temporal dependencies among vehicles can help capture the change of occupancy flow timely to further promote model performance. To demonstrate that TOFG is capable of simplifying the model architecture, we incorporate TOFG with a simple graph attention (GAT) based neural network and propose TOFG-GAT, which can be used for both trajectory prediction and motion planning. Experiment results show that TOFG-GAT achieves better or competitive performance than all the SOTA baselines with less training time.

Predicting the future trajectories of robots' nearby objects plays a pivotal role in applications such as autonomous driving. While learning-based trajectory prediction methods have achieved remarkable performance on public benchmarks, the generalization ability of these approaches remains questionable. The poor generalizability on unseen domains, a well-recognized defect of data-driven approaches, can potentially harm the real-world performance of trajectory prediction models. We are thus motivated to improve models' generalization ability instead of merely pursuing high accuracy on average. Due to the lack of benchmarks for quantifying the generalization ability of trajectory predictors, we first construct a new benchmark called argoverse-shift, where the data distributions of domains are significantly different. Using this benchmark for evaluation, we identify that the domain shift problem seriously hinders the generalization of trajectory predictors since state-of-the-art approaches suffer from severe performance degradation when facing those out-of-distribution scenes. To enhance the robustness of models against domain shift problem, we propose a plug-and-play strategy for domain normalization in trajectory prediction. Our strategy utilizes the Frenét coordinate frame for modeling and can effectively narrow the domain gap of different scenes caused by the variety of road geometry and topology. Experiments show that our strategy noticeably boosts the prediction performance of the state-of-the-art in domains that were previously unseen to the models, thereby improving the generalization ability of data-driven trajectory prediction methods.

The emerging digital twin technique enhances the network management efficiency and provides comprehensive insights, through mapping physical objects to their digital twins. The user satisfaction on digital twin-enabled query services relies on the freshness of digital twin data, which is measured by the Age of Information (AoI). Because the remote cloud faces challenges in providing data for users due to long service delays, Mobile Edge Computing (MEC), as a promising technology, offers real-time data communication between physical objects and their digital twins at the edge of the core network. However, the mobility of physical objects and dynamic query arrivals make efficient service provisioning in MEC become challenging. In this paper, we investigate the dynamic digital twin placement for improving user service satisfaction in MEC environments. We focus on two user service satisfaction augmentation problems under both static and dynamic digital twin placement schemes: the static and dynamic utility maximization problems. We first formulate an Integer Linear Programming (ILP) solution to the static utility maximization problem when the problem size is small; otherwise, we propose a performance- guaranteed approximation algorithm for it. We then devise an online algorithm for the dynamic utility maximization problem with a provable competitive ratio. Finally, we evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms outperform the comparison baseline algorithms, and the performance improvement is no less than 11.6%, compared with the baseline algorithms.

To meet increasing demands for machine-learning-based applications, pushing inference services to the network edge has been a trend. This work aims to design an on-demand edge inference scheduler with accuracy and deadline guarantee for repetitive tasks. Specifically, we consider an edge server that is preinstalled with multiple early-exit Deep Neural Networks (DNNs), and each DNN-exit pair can provide inference service of different quality. We also consider tasks' diversity in quality of service requirements and related utility. We aim to maximize the system's total utility by optimizing service assignment and time scheduling subject to resource, accuracy, and deadline constraints. We present this problem's integer linear problem formulation and show this problem is NP-hard even for the offline case. This problem is challenging due to the coupled effect of service assignment and time scheduling. To derive low-complexity scheduling solutions, we introduce a task-service graph and convert this problem into a service assignment selection problem with schedulability constraints. Then, we design a polynomial complexity algorithm with$\frac{\rho}{\delta}$-approximation ratio for the offline problem, with$\rho$referring to the task-wise utility ratio,$\delta$referring to the maximum number of concurrent tasks. To handle the online problem, we propose an online heuristic algorithm. Simulation results show that the proposed algorithms outperform the state-of-the-art baseline algorithms.

In recent years, the deployment of unmanned vehicle delivery services has increased unprecedentedly, leading to a need for enhanced security due to the risk of leaving high-value packages to an unauthorized third party during pickup or delivery. Existing authentication methods such as QR code and one-time password are inadequate, as they are susceptible to attacks and provide only one-way authentication. This paper, for the first time to our best knowledge, proposes Wave-for-Safe (W4S) --- a novel mutual authentication system that utilizes multi-modal sensors on both the user's smartphone and the unmanned vehicle. W4S uses random hand-waving by the legitimate user to achieve robust authentication by obtaining highly correlated sensory data measured by the Inertial Measurement Unit (IMU) in the smartphone and sensors in the unmanned vehicle (e.g., mmWave radar and camera). We propose several novel methods to overcome challenges such as heterogeneous data processing, asynchronization, and imitating attacks. The prototype is implemented on an unmanned vehicle and various smartphones, and evaluation in different real-world scenarios shows that W4S achieves an equal error rate below 0.013 against various attacks.

In Shared Autonomous Vehicle (SAV) systems, real-time vehicle repositioning plays a crucial role in meeting time-varying traffic demand, which is normally designed by taking advantage of user demand prediction. Nonetheless, most existing studies only predict traffic demand and schedule SAVs separately, ignoring the tight interaction between the two components, e.g. the potential impact of repositioning results on demand prediction. Such a design lacks a deeply integrated design for both and may lead to inaccurate demand prediction and impaired repositioning performance. To tackle this challenge, we propose DRiVe, a coupling approach to Demand prediction and Repositioning for shared autonomous Vehicle system. Specifically, we consider electric SAVs and adopt model predictive control (MPC) to develop the repositioning strategy with the goal of minimizing the operator’s repositioning costs and passenger dissatisfaction. An online prediction is then introduced which not only implements the traditional demand prediction but also integrates the additional traffic demand generated by repositioning action. The numerical results demonstrate that the proposed DRiVe method achieves better performance in reducing passenger waiting time and idle distance compared to the state-of-the-art repositioning methods.

The development of autonomous driving has led to the proposal of vehicle-to-everything (V2X) to improve the reliability of autonomous driving systems through information sharing among vehicles and infrastructure. However, the high-speed mobility of autonomous vehicles and the dynamic surrounding environment make the V2X network unstable and unreliable. To address this issue, empirically studying the characteristics and predicting the signal intensity of the V2X network is crucial, which can provide more information for further optimizing communication strategies and enhancing driving safety. In this paper, we collect the real-world vehicle-to-infrastructure (V2I) performance under different driving scenarios and build the quantitative relationship between several environmental factors and the V2I performance. We also develop deep learning models to predict the V2I signal intensity based on external environmental conditions. Experimental results in real-world data demonstrate the effectiveness of our model on classification and regression tasks compared to other models. Our study aims to enhance the applications of V2X on autonomous driving and improve driving safety and traffic efficiency.

Image-based Multi-Agent Coverage Path Planning (MACPP) utilizes images as input to control multiple agents touring all nodes in a map, minimizing task duration and node revisiting. State-of-the-art (SOTA) studies have applied Multi-Agent Deep Reinforcement Learning (MADRL) to automate MACPP, primarily focusing on minimizing task duration. However, these approaches overlook the issue of repeated node visits, resulting in longer task durations and limited real-world applicability. To tackle this challenge, we develop a novel MADRL solution, referred to as MADRL with Mask Soft Attention, to minimize task duration and node re-visiting simultaneously. Our method uses mask soft attention to extract key features from raw image observations while masking task-independent features, reducing computational complexity and improving sample efficiency. We also cascade a multi-actor-critic architecture to accommodate even more agents with ease. Each agent is equipped with an actor to learn an action policy, and a shared critic evaluates a state value. To validate our approach, we implement seven SOTA MADRL methods in the MACPP area as baselines. Simulation results show that our method significantly outperforms the baselines regarding task duration and the number of times the node is repeatedly visited.

Recently, many efforts have been devoted to promoting the Emotion-Cause Pair Extraction (ECPE) task, as jointly extracting emotions and their causes is considered more helpful than only identifying the emotions in many applications. Among the existing efforts, end-to-end approaches are getting popular as the main trend, while others like pipeline models have been overlooked due to their potential issues of cascading errors. Nevertheless, the advantages of the pipeline models, such as logically dividing a complicated task into multiple easier subtasks, are underestimated and not well exploited. Moreover, the existing end-to-end approaches fail to capture the implicit co-occurrence or exclusion patterns between multiple pairs of emotions and causes since they are extracted independently. In view of these limitations, we propose a novel two-stage model to address the ECPE task and incorporate reinforcement learning (RL) to tackle the cascading error issue. In particular, our two-stage model first detects emotion clauses and then recognizes cause clauses for each detected emotion clause sequentially. By representing the error of each decision as an explicit reward, our model clearly knows how the error at each stage affects the final performance, hence the model can adjust itself for better performance. Furthermore, the sequential prediction enables our model to use the results achieved in the previous stages as auxiliary information in the subsequent stages. Extensive experiments on the benchmark dataset demonstrate the effectiveness of our proposed two-stage model, and the ablation comparison shows the promising effect of reducing cascading errors by incorporating RL.

Recently, edge computing has demonstrated increasing potential to provide low-latency computing services. Coded edge computing can not only make full use of the resources of heterogeneous edge computing servers, but also significantly reduce the negative effects of slow computing devices on computing time. Nevertheless, since edge servers may be unreliable or untrustworthy, the user will decode and get incorrect computation results even if it uses one incorrect sub-computation result returned by faulty edge servers. In this paper, for the existing coded edge computing schemes, we focus on the distributed matrix-matrix multiplication and design a general and efficientDecode-and-Compare Verification(DCV) scheme to verify the correctness of computation results and identify faulty edge servers by utilizing the properties of coded computing itself. The DCV scheme contains two components: (1) computation result verification,i.e., obtain the computation result and verify its correctness, and (2) faulty edge server identification,i.e., identify the faulty edge servers by verifying the correctness of returned sub-computation results. For both the independent and collusion faulty edge server models, we conduct solid theoretical analyses on the required decoding rounds, the coding redundancy and the successful verification probability to demonstrate that the correct computation result can be efficiently verified. We also conduct a lot of experiments on the DCV scheme from different aspects and the results show that it achieves much less computation time to get the correct computation result compared with other potential schemes, including homomorphic encryption and local computation.

In Deep Reinforcement Learning (DRL) domain, a compound learning task is often decomposed into several sub-tasks in a divide-and-conquer manner, each trained separately and then fused concurrently to achieve the original task, referred to as policy fusion. However, the state-of-the-art (SOTA) policy fusion methods treat the importance of sub-tasks equally throughout the task process, eliminating the possibility of the agent relying on different sub-tasks at various stages. To address this limitation, we propose a generic policy fusion approach, referred to as Policy Fusion Learning with Dynamic Weights and Prior Reward (PFLDWPR), to automate the time-varying selection of sub-tasks. Specifically, PFLDWPR produces a time-varying one-hot vector for sub-tasks to dynamically select a suitable sub-task and mask the rest throughout the entire task process, enabling the fused strategy to optimally guide the agent in executing the compound task. The sub-tasks with the dynamic one-hot vector are then aggregated to obtain the action policy for the original task. Moreover, we collect sub-tasks’s rewards at the pre-training stage as a prior reward, which, along with the current reward, is used to train the policy fusion network. Thus, this approach reduces fusion bias by leveraging prior experience. Experimental results under three popular learning tasks demonstrate that the proposed method significantly improves three SOTA policy fusion methods in terms of task duration, episode reward, and score difference.

Robot visual servoing controls the motion of a robot through real-time visual observations. Kinematics is a key approach to achieving visual servoing. One key challenge of kinematics-based visual servoing is that it requires time-varying parameter configuration throughout the entire process of one task. Parameter tuning is also necessary when applying to different tasks. The existing work on parameter tuning either lacks adaptation or cannot automate the tuning of all parameters. Meanwhile, the transferability of existing methods from one task to another is low. This work develops a Deep Reinforcement Learning (DRL) framework for robot visual servoing, which can automate all parameters tuning for one task and across tasks. In visual servoing, forward kinematics focuses on motion speed, while inverse kinematics focuses on the smoothness of motion. Therefore, we develop two separate modules in the proposed DRL framework. One tunes time-varying Forward Kinematics parameters to accelerate the motion, and the other tunes the Inverse Kinematics parameters to ensure smoothness. Moreover, we customize a knowledge transfer method to generalize the proposed DRL models to various robot tasks without reconstructing the neural network. We verify the proposed method on simulated robot tasks. The experimental results show that the proposed method outperforms the state-of-the-art methods and manual parameter configuration in terms of movement speed and smoothness in one task and across tasks.

To unleash the power of buses, we propose a bus-pooling system that keeps the notion of bus stops and terminals but discards the concept of fixed bus lines by enabling buses to choose the next stop or terminal based on orders submitted by passengers. Each bus, unlike a taxi, must consider the additional delays experienced by the passengers already on board when deciding how to adapt its route to serve new orders. This paper treats each bus as an agent and formulates the buses’ re-routing decision-making process as a Semi-Markov game. Then, we propose a novel double graph attention actor-critic (DGAAC) framework by integrating high-level and low-level actor-critics separately with graph attention networks (GATs) to solve the game. Specifically, GATs embedded in high-level and low-level critics take a large-scale graph covering a city-scale area as input and capture graph-structured mutual influences among buses. In contrast, the high-level and low-level actors equipped with GATs only take the n-hop sub-graph with local information as the input and are employed as the distributed decision module of each bus. We conduct extensive experiments on one of the largest real-world datasets in Shenzhen, China, and validate that the proposed DGAAC framework greatly outperforms all baselines.

Discretionary lane change (DLC) is a basic but complex maneuver in driving, which aims at reaching a faster speed or better driving conditions, e.g., further line of sight or better ride quality. Although modeling DLC decision-making has been studied for years, the impact of human factors, which is crucial in accurately modelling human DLC decision-making strategies, is largely ignored in the existing literature. In this paper, we integrate the human factors that are represented by driving styles to design a new DLC decision-making model. Specifically, our proposed model takes not only the contextual traffic information but also the driving styles of surrounding vehicles into consideration and makes lane-change/keep decisions. Moreover, the model can imitate human drivers’ decision-making maneuvers by learning the driving style of the ego vehicle. Our evaluation results show that the proposed model captures the human decision-making strategies and imitates human drivers’ lane-change maneuvers, which can achieve 98.66% prediction accuracy. Moreover, we also analyze the lane-change impact of our model compared with human drivers in terms of improving the safety and speed of traffic.

As widely used in data-driven decision-making, recommender systems have been recognized for their capabilities to provide users with personalized services in many user-oriented online services, such as E-commerce (e.g., Amazon, Taobao, etc.) and Social Media sites (e.g., Facebook and Twitter). Recent works have shown that deep neural networks-based recommender systems are highly vulnerable to adversarial attacks, where adversaries can inject carefully crafted fake user profiles (i.e., a set of items that fake users have interacted with) into a target recommender system to promote or demote a set of target items. Instead of generating users with fake profiles from scratch, in this article, we introduce a novel strategy to obtain “fake” user profiles via copying cross-domain user profiles, where a reinforcement learning based black-box attacking framework (CopyAttack+) is developed to effectively and efficiently select cross-domain user profiles from the source domain to attack the target system. Moreover, we propose to train a local surrogate system for mimicking adversarial black-box attacks in the source domain, so as to provide transferable signals with the purpose of enhancing the attacking strategy in the target black-box recommender system. Comprehensive experiments on three real-world datasets are conducted to demonstrate the effectiveness of the proposed attacking framework.

In energy harvesting communication systems, it is possible for a transmitter to schedule the transmission by jointly scaling the rate and turning the transmitter ON/OFF adaptively. Such a joint rate and sleep schedule can greatly increase the throughput achieved by the transmitter with battery constraints. However, most existing works on joint rate and sleep scheduling assume the transition between different states does not have any cost, i.e., energy or time consumption. This is not realistic while the energy and time needed for booting a transmitter, i.e., turning a transmitter from OFF to ON, are not small enough to be ignored in most cases. In this paper, we investigate the joint rate and sleep scheduling on system throughput with more general booting consumption considered in energy harvesting communication systems. We first identify the structural properties of the optimal solution for the model with booting consumption considered. Inspired by these observations, we develop an optimal offline algorithm and an online heuristic algorithm to solve the problem. Experimental results from simulations and real tests show that the proposed algorithms can achieve much higher throughput on average in a realistic energy harvesting communication system, compared to those algorithms that only consider rate scheduling or ignore the booting consumption.

Accurately predicting the future motions of surrounding traffic agents is critical for the safety of autonomous ve-hicles. Recently, vectorized approaches have dominated the motion prediction community due to their capability of capturing complex interactions in traffic scenes. How-ever, existing methods neglect the symmetries of the prob-lem and suffer from the expensive computational cost, facing the challenge of making real-time multi-agent motion prediction without sacrificing the prediction performance. To tackle this challenge, we propose Hierarchical Vector Transformer (HiVT) for fast and accurate multi-agent motion prediction. By decomposing the problem into local con-text extraction and global interaction modeling, our method can effectively and efficiently model a large number of agents in the scene. Meanwhile, we propose a translation-invariant scene representation and rotation-invariant spa-tial learning modules, which extract features robust to the geometric transformations of the scene and enable the model to make accurate predictions for multiple agents in a single forward pass. Experiments show that HiVT achieves the state-of-the-art performance on the Argoverse motion forecasting benchmark with a small model size and can make fast multi-agent motion prediction.

An Autonomous Driving System (ADS) uses a plethora of sensors and many deep learning based tasks to aid its perception, prediction, motion planning, and vehicle control. To ensure road safety, those tasks should be synchronized and use the latest sensing data, which is challenging since 1) different sensors have different sensing periods, 2) the tasks are interdependent, 3) computing resource is limited. This work is the first that uses Age of Information (AoI) as the performance metric for task scheduling in an ADS. We show that minimizing AoI is equivalent to jointly minimizing the response time and maximizing the throughput. We formally formulate the AoI-centric task scheduling problem. To derive practical scheduling solutions, we extend the formulation and formulate the optimal AoI-centric periodic scheduling problem with a given cycle. A reinforcement learning-based solution is designed accordingly. With experiments simulated according to the Apollo driving system, we compare the scheduling performance of the AoI-centric task scheduling with Apollo’s schedulers from the perspective of AoI, throughput, and worst case response time. The experiment results show that the maximum AoI in the proposed scheduling solution with 4 cores is lower than that in Apollo’s schedulers with 8 cores.

Since the inception of networking technology, network topology design has been a fundamental step for any interconnected system. This classical problem has diverse forms due to various design criteria. One special criterion, the ease of monitoring the network (termed as monitorability of the network), has recently attracted much attention in the era of Industry 4.0 when many complex private networks need to be built for new industrial services. This paper extends a quantitative measure of network monitorability, k-identifiability, based on which a new form of network topology design problem is formulated. We prove that this network design problem is intractable. To solve it, we systematically analyze the topological features that are helpful for reducing the complexity of network construction. Based on the analysis, we propose a dual-heuristic method that runs two heuristics in parallel and selects the better topology as the preliminary design result. Moreover, we design an integrated algorithm that reduces unnecessary edges as the final design result. We compare our dual-heuristic algorithm with the theoretical optimal solution in small-scale networks where the brute-force search is feasible. The results demonstrate the near-optimality of our method. We also illustrate the capability of our method in designing large-scale networks.

The advances of single-cell DNA sequencing (scDNA-seq) enable us to characterize the genetic heterogeneity of cancer cells. However, the high noise and low coverage of scDNA-seq impede the estimation of copy number variations (CNVs). In addition, existing tools suffer from intensive execution time and often fail on large datasets. Here, we propose SeCNV, an efficient method that leverages structural entropy, to profile the copy numbers. SeCNV adopts a local Gaussian kernel to construct a matrix, depth congruent map (DCM), capturing the similarities between any two bins along the genome. Then, SeCNV partitions the genome into segments by minimizing the structural entropy from the DCM. With the partition, SeCNV estimates the copy numbers within each segment for cells. We simulate nine datasets with various breakpoint distributions and amplitudes of noise to benchmark SeCNV. SeCNV achieves a robust performance, i.e. the F1-scores are higher than 0.95 for breakpoint detections, significantly outperforming state-of-the-art methods. SeCNV successfully processes large datasets (>50 000 cells) within 4 min, while other tools fail to finish within the time limit, i.e. 120 h. We apply SeCNV to single-nucleus sequencing datasets from two breast cancer patients and acoustic cell tagmentation sequencing datasets from eight breast cancer patients. SeCNV successfully reproduces the distinct subclones and infers tumor heterogeneity. SeCNV is available at https://github.com/deepomicslab/SeCNV.

Next-generation sequencing expands the known phage genomes rapidly. Unlike culture-based methods, the hosts of phages discovered from next-generation sequencing data remain uncharacterized. The high diversity of the phage genomes makes the host assignment task challenging. To solve the issue, we proposed a phage host prediction tool-DeepHost. To encode the phage genomes into matrices, we design a genome encoding method that applied various spaced $k$-mer pairs to tolerate sequence variations, including insertion, deletions, and mutations. DeepHost applies a convolutional neural network to predict host taxonomies. DeepHost achieves the prediction accuracy of 96.05% at the genus level (72 taxonomies) and 90.78% at the species level (118 taxonomies), which outperforms the existing phage host prediction tools by 10.16-30.48% and achieves comparable results to BLAST. For the genomes without hits in BLAST, DeepHost obtains the accuracy of 38.00% at the genus level and 26.47% at the species level, making it suitable for genomes of less homologous sequences with the existing datasets. DeepHost is alignment-free, and it is faster than BLAST, especially for large datasets. DeepHost is available at https://github.com/deepomicslab/DeepHost.

To improve safety in public transportation, a major issue is how to avoid traffic accidents. To this end, a recent report has demonstrated that more than 90% of accidents in the United States were due to drivers’ abnormal behaviors. Relevant to this observation, many recent studies have proposed to use different sensors to monitor drivers’ behaviors and apply learning algorithms to detect abnormal behaviors. Nevertheless, most existing systems are expensive and inconvenient to be deployed or significantly affected by the environment. In this article, we propose and develop a novel and effective solution, namely, SafeDriving, that collects signals from electromyography (EMG) sensors and then utilizes an effective deep-learning model to detect abnormal behaviors in real time. Specifically, we first utilize a wearable EMG sensor that can be attached to a driver’s forearm to collect a large amount of sensing data from human drivers, for which we define five typical abnormal driving behaviors (i.e., fetching forward, picking up, turning the steering wheel sharply, turning back, and touching sunroof) and label each sample accordingly. Next, using the labeled data, we design and train multiple state-of-the-art classifiers to improve the performance of SafeDriving, e.g., convolutional neural network (CNN), long short-term memory (LSTM), and gated recurrent unit (GRU). The extensive experiments demonstrate that GRU can lead to the best performance with an average accuracy of 93.94%. Based on this observation, we further investigate other important factors, such as the binding area of the sensor, the tightness of binding, the duration of the sample, etc. The proposed SafeDriving system provides an effective approach to reliably assess drivers’ driving behaviors with affordable commodity sensors and be further used in public safety.

Vehicular communication networks (VCNs) have been widely recognized as promising solutions to support safety-related applications in urban transportation systems. However, constructing and maintaining such networks is quite challenging due to the complex traffic and communication environment. Substantial studies have focused on the design of the networking schemes and message dissemination protocols. Nonetheless, most existing designs only consider the connectivity and rapid end-to-end transmission, regardless of the network coverage and duration. In this article, we propose a novel temporary warning network (TWN) for safety message dissemination in the urban traffic environment, in which both the spatial distribution and temporal duration of the networking scheme are taken into account. Specifically, TWN is constructed by the selection of relay vehicles based on the spatiotemporal correlation of vehicle trajectory so that the safety message can be quickly disseminated within the Regions of Interest (RoIs). To maintain TWN during an accident, a reselection mechanism is also proposed, which enables newly come vehicles in the RoI to receive the messages in time. Finally, we conduct extensive numerical experiments to validate the effectiveness of our method in various traffic scenarios.

Modeling interactions among vehicles is critical in improving the efficiency and safety of autonomous driving since complex interactions are ubiquitous in many traffic scenarios. To model interactions under different traffic scenarios, most existing works consider interaction information implicitly in their specific tasks with hand-crafted features and predefined maneuvers. Extracting interaction representation, which can be commonly used among different downstream tasks, is not explored. In this article, we propose a general and novel graph self-attention network (GSAN) to learn the spatial–temporal interaction representation among vehicles by a framework consisting of pretraining and fine-tuning. Specifically, in the pretraining step, we construct the GSAN module based on a graph self-attention layer and a gated recurrent unit layer, and use trajectory autoregression to learn the interaction information among vehicles. In the fine-tuning step, we propose two different adaptation schemes to utilize the learned interaction information in various downstream tasks and fine-tune the entire model with only a few steps. To illustrate the effectiveness and generality of our spatial–temporal interaction model, we conduct extensive experiments on two typical interaction-related tasks, namely, lane-changing classification and trajectory prediction. The experiment results demonstrate that our approach significantly outperforms the state-of-the-art solutions of these two tasks. We also visualize the impact of surrounding vehicles on the ego vehicle in different interaction scenes. The visualization offers an intuitive explanation on how our model captures the dynamic changing interactions among vehicles and makes good predictions in various interaction-related tasks.

In recent years, many deep learning models have been adopted in autonomous driving. At the same time, these models introduce new vulnerabilities that may compromise the safety of autonomous vehicles. Specifically, recent studies have demonstrated that adversarial attacks can cause a significant decline in detection precision of deep learning-based 3-D object detection models. Although driving safety is the ultimate concern for autonomous driving, there is no comprehensive study on the linkage between the performance of deep learning models and the driving safety of autonomous vehicles under adversarial attacks. In this article, we investigate the impact of two primary types of adversarial attacks, perturbation attacks, and patch attacks, on the driving safety of vision-based autonomous vehicles rather than the detection precision of deep learning models. In particular, we consider two state-of-the-art models in vision-based 3-D object detection: 1) Stereo R-CNN and 2) DSGN. To evaluate driving safety, we propose an end-to-end evaluation framework with a set of driving safety performance metrics. By analyzing the results of our extensive evaluation experiments, we find that: 1) the attack’s impact on the driving safety of autonomous vehicles and the attack’s impact on the precision of 3-D object detectors are decoupled and 2) the DSGN model demonstrates stronger robustness to adversarial attacks than the Stereo R-CNN model. In addition, we further investigate the causes behind the two findings with an ablation study. The findings of this article provide a new perspective to evaluate adversarial attacks and guide the selection of deep learning models in autonomous driving.

To promote cloud computing from current pay-per-request model to truly pay-per-use, tenants are crying for automatic tools to auto-estimate the amount of resources for MapReduce jobs. Such tools call for accurately quantifying the relationship among workload, resources and completion time. Various prediction models have been proposed. However, none of these models takes virtual machines’ (VMs) performance variance during a job's execution into consideration, leading to underestimate the required resources and exceed the job's deadline. To address this problem, we propose a multi-view deep learning model to capture real-time performance variance and automatically scale out the cloud cluster whenever necessary. We implementMarVeLScaler, a prototype system including two useful modules, namely,Scale EstimatorandScale Controller. Scale Estimator preliminarily estimates the required cluster size for a MapReduce job with given a concrete workload and deadline. During the runtime, Scale Controller adjusts the scale of the cluster according to its real-time running status to guarantee the job finished on time. We evaluate the performance of MarVeLScaler based on Hadoop in Alibaba Cloud. Experiments show that MarVeLScaler can provide 98.4 percent accuracy of prediction in determining initial cluster size, and save 30.8 percent of expense while still guaranteeing similar performance compared with the state-of-the-art methods.

In recent years, edge computing has attracted significant attention because it can effectively support many delay-sensitive applications. Despite such a salient feature, edge computing also faces many challenges, especially for efficiency and security, because edge devices are usually heterogeneous and may be untrustworthy. To address these challenges, we propose a unified framework to provide efficiency and confidentiality by coded distributed computing. Within the proposed framework, we use matrix multiplication, a fundamental building block of many distributed machine learning algorithms, as the representative computation task. To minimize resource consumption while achieving information-theoretic security, we investigate two highly-coupled problems, (1) task allocation that assigns data blocks in a computing task to edge devices and (2) linear code design that generates data blocks by encoding the original data with random information. Specifically, we first theoretically analyze the necessary conditions for the optimal solution. Based on the theoretical analysis, we develop an efficienttask allocationalgorithm to obtain a set of selected edge devices and the number of coded vectors allocated to them. Using the task allocation results, we then designsecure coded computingschemes, for two cases, (1) with redundant computation and (2) without redundant computation, all of which satisfy the availability and security conditions. Moreover, we also theoretically analyze the optimization of the proposed scheme. Finally, we conduct extensive simulation experiments to demonstrate the effectiveness of the proposed schemes.

Sampling-based motion planning (SBMP) is a major algorithmic trajectory planning approach in autonomous driving given its high efficiency and outstanding performance in practice. However, driving safety still calls for further refinement of SBMP. In this article we organically integrate algorithmic motion planning with learning models to improve SBMP in highway traffic scenarios from the following two perspectives. First, given the number of points to be sampled, we develop a new model to sample “important” points for SBMP by predicting the intention of surrounding vehicles and learning the distribution of human drivers’ trajectory. Second, we empirically study the relationship between the number of sample points and the environment, which is largely ignored in conventional SBMP. Then, we provide a guideline to select the appropriate number of points to be sampled under different scenarios to guarantee efficiency. The simulation experiments are conducted based on the vehicle trajectory dataset NGSIM. The results show that the proposed sampling strategy outperforms existing sampling strategies in terms of the computing time, traveling time, and smoothness of the trajectory.

Data in many real-world applications such as social networks, users shopping behaviors, and inter-item relationships can be represented as graphs. Graph Neural Networks (GNNs) have shown great success in learning meaningful representations for graphs by inherently integrating node information and topological structure. Data in social recommendations can also be denotes as graph data in the form of user-user social graphs and user-item graphs. In addition, the relationships between items can be denoted as item-item graphs. GNNs provide an unprecedented opportunity to advance social recommendations. However, there are tremendous challenges in building GNNs-based social recommendations where (1) users (items) are simultaneously involved in the user-item graph and user-user social graph (item-item graph); (2) user-item graphs not only contain user-item interactions but also include users’ opinions on items; and (3) the nature of social relations are heterogeneous among users. In this paper, we propose a novel graph neural network framework (GraphRec+) for social recommendations, which is able to coherently model graph data in order to learn better user and item representations. Specifically, we introduce a principled approach for jointly capturing interactions and opinions in the user-item graph and also propose an attention mechanism to differentiate the heterogeneous strengths of social relations. Comprehensive experiments on three real-world datasets show the effectiveness of the proposed framework.

Inferring the bandwidth of internal links from the bandwidth of end-to-end paths, so-termed bandwidth tomography, is a long-standing open problem in the network tomography literature. The difficulty is due to the fact that no existing mathematical tool is directly applicable to solve the inverse problem with a set of$min$-equations. We systematically tackle this challenge by designing a polynomial-time algorithm that returns the exact bandwidth value for all identifiable links and the tightest error bound for unidentifiable links for a given set of measurement paths. When the measurement paths are not given in advance, we prove the hardness of building measurement paths that can be used for deriving the global tightest error bounds for unidentifiable links. Accordingly, we develop a reinforcement learning (RL) approach for measurement path construction, that utilizes the special knowledge in bandwidth tomography and integrates both offline training and online prediction. Evaluation results with real-world ISP topology as well as simulated networks demonstrate that compared to other path construction methods,RandomandDiversity Preferred, our RL-based path construction method can build measurement paths that result in a much smaller average error bound of the link bandwidth.

Live streaming services have gained extreme popularity in recent years. Due to the spiky traffic patterns of live videos, utilizing distributed edge servers to improve viewers' quality of experience (QoE) has become a common practice nowadays. Nevertheless, the current client-driven content caching mechanism does not support pre-caching from the cloud to the edge, resulting in a considerable amount of cache misses in live video delivery. By jointly considering the features of live videos and edge servers, we propose PLVER, a proactive live video push scheme to address the cache miss problem in live video delivery. Specifically, PLVER first conducts a one-to-multiple stable allocation between edge clusters and user groups to balance the load of live traffic over the edge servers. It then adopts proactive video replication algorithms to speed up video replication among the edge servers. We conduct extensive trace-driven evaluation, covering 0.3 million Twitch viewers and more than 300 Twitch channels. The results demonstrate that with PLVER, edge servers can carry 28 and 82 percent more traffic than the auction-based replication (ABR) method and the caching on requested time (CORT) method, respectively.

A group of connected and autonomous vehicles (CAVs) with common interests can drive in a cooperative manner, namely cooperative driving, which has been verified to significantly improve road safety, traffic efficiency, and environmental sustainability. A more general scenario with various types of cooperative driving applications such as truck platooning and vehicle clustering will coexist on roads in the foreseeable future. To support such multiple cooperative drivings, it is critical to design an efficient message dissemination scheduling for vehicles to broadcast their kinetic status, i.e., beacon periodically. Most ongoing researches suggest designing the communication protocols via traffic and communication modeling on top of dedicated short range communications (DSRC) or cellular-based vehicle-to-vehicle (C-V2V) communications as a potential remedy. However, most of the existing researches are designed for a simple or specific traffic scenario, e.g., ignoring the impacts of the complex communication environment and emerging hybrid traffic scenarios. Moreover, some studies design beaconing strategies based on the implication of channel and traffic conditions in the beacons of other vehicles. However, the delayed perception of these information may seriously deteriorate the beaconing performance. In this paper, we take the perspective of cooperative drivings and formulate their decision-making process as a Markov game. Furthermore, we propose a multi-agent hierarchical attention reinforcement learning (MAHA) framework to solve the Markov game. More concretely, the hierarchical structure of the proposed MAHA can lead cooperative drivings to be foresightful. Hence, even without immediate incentives, the well-trained agents can still take favorable actions that benefit their long-term rewards. Besides, we integrate each hierarchical level of MAHA separately with the graph attention network (GAT) to incorporate agents' mutual influences in the decision-making process. Besides, we set up a simulator and adopt this simulator to generate dynamic traffic scenarios, which reflect the different real-world scenarios faced by cooperative drivings. We conduct extensive experiments to evaluate the proposed MAHA framework's performance. The results show that MAHA can significantly improve the beacon reception rate and guarantee low communication delay in all of these scenarios.

Recommender systems, which aim to suggest personalized lists of items for users, have drawn a lot of attention. In fact, many of these state-of-the-art recommender systems have been built on deep neural networks (DNNs). Recent studies have shown that these deep neural networks are vulnerable to attacks, such as data poisoning, which generate fake users to promote a selected set of items. Correspondingly, effective defense strategies have been developed to detect these generated users with fake profiles. Thus, new strategies of creating more `realistic' user profiles to promote a set of items should be investigated to further understand the vulnerability of DNNs based recommender systems. In this work, we present a novel framework CopyAttack. It is a reinforcement learning based black-box attacking method that harnesses real users from a source domain by copying their profiles into the target domain with the goal of promoting a subset of items. CopyAttack is constructed to both efficiently and effectively learn policy gradient networks that first select, then further refine/craft user profiles from the source domain, and ultimately copy them into the target domain. CopyAttack's goal is to maximize the hit ratio of the targeted items in the Top-k recommendation list of the users in the target domain. We conducted experiments on two real-world datasets and empirically verified the effectiveness of the proposed framework. The implementation of CopyAttack is available at https://github.com/wenqifan03/CopyAttack.

Inferring the bandwidth of internal links from the bandwidth of end-to-end paths, so-termed bandwidth tomography, is a long-standing open problem in the network tomography literature. The difficulty is due to the fact that no existing mathematical tool is directly applicable to solve the inverse problem with a set of min-equations. We systematically tackle this challenge by designing a polynomial-time algorithm that returns the exact bandwidth value for all identifiable links and the tightest error bound for unidentifiable links for a given set of measurement paths. When measurement paths are not given in advance, we prove the hardness of building measurement paths that can be used for deriving the global tightest error bounds for unidentifiable links. Accordingly, we develop a reinforcement learning (RL) approach for measurement path construction, that utilizes the special knowledge in bandwidth tomography and integrates both offline training and online prediction. Evaluation results with real-world ISP as well as simulated networks demonstrate that compared to other path construction methods, Random and Diversity Preferred, our RL-based path construction method can build measurement paths that result in much smaller average error bound of link bandwidth.

Matrix factorization is an important representation learning algorithm, e.g., recommender systems, where a large matrix can be factorized into the product of two low dimensional matrices termed as latent representations. This paper investigates the problem of matrix factorization in distributed computing systems with stragglers, those computing nodes that are slow to return computation results. A computation procedure, called coded Alternative Least Square (ALS), is proposed for mitigating the effect of stragglers in such systems. The coded ALS algorithm iteratively computes two low dimensional latent matrices by solving various linear equations, with the Entangled Polynomial Code (EPC) as a building block. We theoretically characterize the maximum number of stragglers that the algorithm can tolerate (or the recovery threshold) in relation to the redundancy of coding (or the code rate). In addition, we theoretically show the computation complexity for the coded ALS algorithm and conduct numerical experiments to validate our design.

Network performance tomography uses a small number of strategically deployed monitors to infer the link performance in a large network. With the limited number of monitors, however, people usually can only estimate the bound rather than the exact values of network link performance. We aim at developing an effective solution to minimize the maximum error bound ($\mathcal{M}\mathcal{E}\mathcal{B}$) over all the links in the network. To achieve this, we develop a method that theoretically guarantees (1) the minimum number of monitors required to bring down the $\mathcal{M}\mathcal{E}\mathcal{B}$ over all unidentifiable links, and (2) the best places where these new monitors should be deployed. Using this method repeatedly, we can push down the $\mathcal{M}\mathcal{E}\mathcal{B}$ gradually until the desired level is reached. In addition, we develop a new sequential measurement technique that reduces the number of measurement paths and in the meantime guarantees the tightest link error bound. With extensive simulation over real-world network topology, we demonstrate the effectiveness and robustness of our solution in reducing the maximum link error bound with network performance tomography.

Vehicle to Vehicle (V2V) communication opens a new way to make vehicles directly communicate with each other, providing faster responses for time-sensitive tasks than cellular networks. Effective V2V routing protocols are essential yet challenging, as the high dynamic road environment makes communication easy to break. Many prediction methods proposed in the existing protocols to address this issue are either flawed or have a poor effect. In this paper, to cope with the two aspects of the problems that cause communication interrupt, i.e., link breaks and route quality degradation, we design an acceleration-based trajectory prediction algorithm to estimate the link lifetime, and a machine learning model to predict route quality. Based on the prediction algorithms, we propose PQR, a Prediction-supported Quality-aware Routing protocol, which can proactively switch to a better route before the current link breaks or the route quality degrades. Especially, considering the limitations of the current routing protocols, we elaborate a new hybrid routing protocol that integrates the topology-based method and location-based method to achieve instant communication. Simulation results show that PQR outperforms the existing protocols in Packet Delivery Ratio (PDR), Roundtrip Time (RTT), and Normalized Routing Overhead (NRO). Specifically, we have also implemented a vehicular testbed to demonstrate PQR’s real-world performance, and results show that PQR achieves almost no packet loss with latency less than 10ms during route handoff for topology change.

Recently, edge computing (EC) has attracted wide attention as a novel and promising computing mode with high real-time and low-latency characteristics. However, users' privacy and the limited resources have become major concerns in the implementation of EC because edge devices are usually heterogeneous and untrustworthy. Although many related works have protected the user's privacy, they did not take the storage resource limitation of heterogeneous edge devices into consideration and their schemes may cause high communication load. In this paper, we propose PCHEC, a Private Coded computation scheme for Heterogeneous Edge Computing, to protect the user's privacy and minimize the communication load. Specifically, PCHEC first gives a storage allocation scheme to minimize the communication load in EC where the heterogeneous edge devices have different storage limits. Secondly, PCHEC utilizes linear coding to mix the target data with other information for the protection of the user's privacy. To evaluate the efficiency of PCHEC, we make theoretically analysis and conduct extensive simulations. The experiments show PCHEC effectively reduces the communication load by up to 70% compared with other schemes.

In recent years, edge computing (EC), as an emerging technology, has been widely used in various industries. It can meet the needs of industries in real-time business, application intelligence, security and privacy protection. However, edge devices may not always be trustworthy in the edge computing environment. Moreover, traditional edge computing systems have ignored the fact that the computation capability of user device can also be used. In this paper, we propose the Minimum Computation Latency Secure Edge Computing (MCLSEC) scheme to minimize computation latency and provide the security of computing data by utilizing linear coding and the resources of both edge devices and user device. Specifically, we consider the matrix multiplication as a computation task, which is an important module in many application operations, such as machine learning, big data analysis, etc. We firstly theoretically analyze the total computation latency of edge devices and user device in the coded edge computing. We then give the design of the MCLSEC scheme, which includes of the coding scheme and the task allocation scheme. Moreover, we also give theoretical analysis to show the proposed MCLSEC scheme is secure and optimal. Finally, we conduct extensive simulation experiments to show the effectiveness of the proposed scheme. Compared with the existing schemes, MCLSEC scheme significantly reduces the computation latency of edge computing while ensuring data confidentiality.

For autonomous driving, an essential task is to detect surrounding objects accurately. To this end, most existing systems use optical devices, including cameras and light detection and ranging (LiDAR) sensors, to collect environment data in real time. In recent years, many researchers have developed advanced machine learning models to detect surrounding objects. Nevertheless, the aforementioned optical devices are vulnerable to optical signal attacks, which could compromise the accuracy of object detection. To address this critical issue, we propose a framework to detect and identify sensors that are under attack. Specifically, we first develop a new technique to detect attacks on a system that consists of three sensors. Our main idea is to: 1) use data from three sensors to obtain two versions of depth maps (i.e., disparity) and 2) detect attacks by analyzing the distribution of disparity errors. In our study, we use real data sets and the state-of-the-art machine learning model to evaluate our attack detection scheme and the results confirm the effectiveness of our detection method. Based on the detection scheme, we further develop an identification model that is capable of identifying up to n-2 attacked sensors in a system with one LiDAR and n cameras. We prove the correctness of our identification scheme and conduct experiments to show the accuracy of our identification method. Finally, we investigate the overall sensitivity of our framework.

As a policy-based routing protocol, the primary purpose of Border Gateway Protocol (BGP) is to exchange routing reachability information to provide sufficient end-to-end Quality-of-Service (QoS). The constant increase of anomalous traffic of BGP affects the connectivity and reachability of routing information among different Autonomous Systems (ASs), which calls for building accurate alerting models to provide stable routing services in the Internet. The previous works classify anomalies without considering the characteristic of multiple time scales, which may lead to inaccurate classification. In this paper, we propose a novel Multi-Scale Long Short-Term Memory (MSLSTM) model to capture the anomalous behaviors from BGP traffic. In our model, a Discrete Wavelet Transform is used to obtain temporal information on multiple scales, and a hierarchical two-layer LSTM architecture is devised where the first layer learns the attentions of different time scales to generate an integrated historical representation, and the second layer captures the temporal dependency in the learned representation. To evaluate the feasibility in different alerting scenarios, we conduct comprehensive experiments based on several BGP data sets collected from real world applications. The results demonstrate that our model achieves a promising performance compared with the state-of-the-art approaches.

In mobile cloud computing, offloading resource-demanded applications from mobile devices to remote cloud servers can alleviate the resource scarcity of mobile devices, whereas long distance communication may incur high communication latency and energy consumption. As an alternative, fortunately, recent studies show that exploiting the unused resources of the nearby mobile devices for task execution can reduce the energy consumption and communication latency. Nevertheless, it is non-trivial to encourage mobile devices to share their resources or execute tasks for others. To address this issue, we construct an auction model to facilitate the resource trading between the owner of the tasks and the mobile devices participating in task execution. Specifically, the owners of the tasks act as bidders by submitting bids to compete for the resources available at mobile devices. We design a distributed auction mechanism to fairly allocate the tasks, and determine the trading prices of the resources. Moreover, an efficient payment evaluation process is proposed to prevent against the possible dishonest activity of the seller on the payment decision, through the collaboration of the buyers. We prove that the proposed auction mechanism can achieve certain desirable properties, such as computational efficiency, individual rationality, truthfulness guarantee of the bidders, and budget balance. Simulation results validate the performance of the proposed auction mechanism.

Sampling-based motion planning (SBMP) is a major trajectory planning approach in autonomous driving given its high efficiency in practice. As the core of SBMP schemes, sampling strategy holds the key to whether a smooth and collision-free trajectory can be found in real-time. Although some bias sampling strategies have been explored in the literature to accelerate SBMP, the trajectory generated under existing bias sampling strategies may lead to sharp lane changing. To address this issue, we propose a new learning framework for SBMP. Specifically, we develop a novel automatic labeling scheme and a 2-Stage prediction model to improve the accuracy in predicting the intention of surrounding vehicles. We then develop an imitation learning scheme to generate sample points based on the experience of human drivers. Using the prediction results, we design a new bias sampling strategy to accelerate the SBMP algorithm by strategically selecting necessary sample points that can generate a smooth and collision-free trajectory and avoid sharp lane changing. Data-driven experiments show that the proposed sampling strategy outperforms existing sampling strategies, in terms of the computing time, traveling time, and smoothness of the trajectory. The results also show that our scheme is even better than human drivers.

Emotion-cause pair extraction (ECPE) aims at extracting emotions and causes as pairs from documents, where each pair contains an emotion clause and a set of cause clauses.Existing approaches address the task by first extracting emotion and cause clauses via two binary classifiers separately, and then training another binary classifier to pair them up.However, the extracted emotion-cause pairs of different emotion types cannot be distinguished from each other through simple binary classifiers, which limits the applicability of the existing approaches.Moreover, such two-step approaches may suffer from possible cascading errors.In this paper, to address the first problem, we assign emotion type labels to emotion and cause clauses so that emotioncause pairs of different emotion types can be easily distinguished.As for the second problem, we reformulate the ECPE task as a unified sequence labeling task, which can extract multiple emotion-cause pairs in an end-to-end fashion.We propose an approach composed of a convolution neural network for encoding neighboring information and two Bidirectional Long-Short Term Memory networks for two auxiliary tasks.Experiment results demonstrate the feasibility and effectiveness of our approaches.

The causal relationships between emotions and causes in text have recently received a lot of attention.Most of the existing works focus on the extraction of the causally related clauses from documents.However, none of these works has considered the possibility that the causal relationships among the extracted emotion and cause clauses may only be valid under a specific context, without which the extracted clauses may not be causally related.To address such an issue, we propose a new task of determining whether or not an input pair of emotion and cause has a valid causal relationship under different contexts, and construct a corresponding dataset via manual annotation and negative sampling based on an existing benchmark dataset.Furthermore, we propose a prediction aggregation module with low computational overhead to fine-tune the prediction results based on the characteristics of the input clauses.Experiments demonstrate the effectiveness and generality of our aggregation module.

Vehicular ad hoc networks (VANETs) have been widely recognized as a promising solution to improve traffic safety and efficiency for the ability to provide situation awareness even though the potential dangers and traffic anomalies are out of the visual range. In VANETs, time-division multiple access (TDMA) based overlay protocols can prevent transmission collisions, and play an important role in providing an efficient communication channel. However, due to high vehicle mobility and time-varying traffic flow, the existing TDMA-based slot allocation approaches cannot fully utilize the channel resources, which may result in high transmission delay and packet collision. To overcome these shortcomings, we propose a traffic-aware TDMA-based MAC (TA-MAC) protocol which utilizes the capability of mobile edge computing (MEC) in this paper. Specifically, based on MEC and vehicle-to-road-side-units (V2R) communications, a traffic-aware mechanism is first proposed to estimate the traffic condition on the road segment. Then, we propose a new slot assignment method that aims at guaranteeing the high channel utilization and low delay of safety message under dynamic traffic conditions. Finally, we conduct extensive experiments to demonstrate the effectiveness of the proposed protocol.

A group of connected and autonomous vehicles (CAVs) with common interests can drive in a cooperative manner, namely cooperative driving, which has been verified to significantly improve road safety, traffic efficiency and environmental sustainability. A more general scenario that various types of cooperative driving applications such as truck platooning and vehicle clustering, will coexist on roads in the foreseeable future. To support such multiple cooperative drivings, it is critical to design an efficient message dissemination scheduling in a shared communication channel. Most ongoing research suggests using the time-division multiple access (TDMA) method on top of IEEE 802.11p as a potential remedy. However, TDMA requires time synchronization and is not flexible, especially in the multiple cooperative drivings scenario where the beacon frequency needs to be updated and the number of cooperative drivings changes to meet the time-varying traffic conditions. In this paper, we focus on the study of the message dissemination protocol for platooning, a typical and well-known cooperative driving pattern. Specifically, we proposed a hybrid message dissemination protocol which aims at guaranteeing the reliable delivery of beacon messages for a multi-platooning system. We first adopt a TDMA-based medium access method for intra-platoon communication to improve the reliability and efficiency of beacon dissemination. We then present a token-passing medium access method for inter-platoon communication, which maps platoons into a token ring to schedule their beacon transmission time. We conduct extensive numerical experiments to validate the effectiveness of our protocol.

Model-Agnostic Meta-Learning (MAML) and its variants are popular few-shot classification methods. They train an initializer across a variety of sampled learning tasks (also known as episodes) such that the initialized model can adapt quickly to new ones. However, current MAML-based algorithms have limitations in forming generalizable decision boundaries. In this paper, we propose an approach called MetaMix, which generates virtual feature-target pairs within each episode to regularize the backbone models. MetaMix can be integrated with any of the MAML-based algorithms and learn the decision boundaries generalizing better to new tasks. Experiments on the mini-ImageNet, CUB, and FC100 datasets show that MetaMix improves the performance of MAML-based algorithms and achieves state-of-the-art result when integrated with Meta-Transfer Learning.

Recent years have seen a rapidly increasing traffic demand for HTTP-based high-quality live video streaming. The surging traffic demand, as well as the real-time property of live videos, make it challenging for content delivery networks (CDNs) to guarantee the Quality-of-Experiences (QoE) of viewers. The initial video segment (IVS) of live streaming plays an important role in the QoE of live viewers, particularly when users require fast join time and smooth view experience. State-of-the-art research on this regard estimates network throughput for each viewer and thus may incur a large overhead that offsets the benefit. To tackle the problem, we propose Rldish, a scheme deployed at the edge CDN server, to dynamically select a suitable IVS for new live viewers based on Reinforcement Learning (RL). Rldish is transparent to both the client and the streaming server. It collects the real-time QoE observations from the edge without any client-side assistance, then uses these QoE observations as real-time rewards in RL. We deploy Rldish as a virtualized network function (VNF) in a real HTTP cache server, and evaluate its performance using streaming servers distributed over the world. Our experiments show that Rldish improves the state- of-the-art IVS selection scheme w.r.t. the average QoE of live viewers by up to 22%.

Edge computing is a promising technology that can fulfill the requirements of latency-critical and computation-intensive applications. To further enhance the performance, coded edge computing has emerged because it can optimally utilize edge devices to speed up the computation. In this paper, we tackle a major security issue in coded edge computing: how to verify the correctness of results and identify attackers. Specifically, we propose an efficient verification scheme, namely Decode-and-Compare (DC), by leveraging both the coding redundancy of edge devices and the properties of linear coding itself. To design the DC scheme, we conduct a solid theoretical analysis to show the required coding redundancy, the expected number of decoding operations, and the tradeoff between them. To evaluate the performance of DC, we conduct extensive simulation experiments and the results confirm that the DC scheme can outperform existing solutions, such as homomorphic encryption and computing locally at the user device.

Modeling the interactions among vehicles has been considered essential in improving efficiency and safety in autonomous driving, since the real traffic scenarios, such as merging lanes, intersection, and lane change, are full of complex interactions. In the literature, interaction is considered implicitly in individual tasks, which makes it hard to extract the interactions for other related downstream tasks. In this paper, we propose a novel Graph Self-Attention Network (GSAN) to quickly capture and quantify the influence of interactions among vehicles from historical trajectories, which can be used as a tool to introduce the impact of interactions into different downstream tasks and further analyze the dominating features affecting the interactions among vehicles. We conduct experiments on the trajectory prediction task as one example to illustrate how to use the spatial-temporal interaction vector to improve the performance of interaction related tasks. The experiment results demonstrate that the GSAN module outperforms the state-of-the-art solutions in terms of the trajectory prediction accuracy. Also, we visualize the effects from all surrounding vehicles on the ego vehicle by heat maps using the trained attention values from the GSAN module.

Canonical Correlation Analysis (CCA) aims to learn the linear projections of two sets of variables where they are correlated maximally, which is not optimal for variables with non-linear relations. Recent years have witnessed great efforts in developing deep neural networks based CCA models, which are able to learn flexible non-linear and highly correlated representations between two variables. In addition to learning representations, generating realistic multi-view samples is also becoming highly desired in many real-world applications. However, the majority of existing CCA models do not provide mechanisms for realistic samples generation. Meanwhile, adversarial learning techniques such as generative adversarial networks have been proven to be effective in generating realistic samples similar to real data distribution. Thus, incorporating adversarial learning techniques has a great potential to advance Canonical Correlation Analysis. In this paper, we harness the power of adversarial learning techniques to equip Canonical Correlation Analysis with the ability of realistic data generation. In particular, we propose a Deep Adversarial Canonical Correlation Analysis model (DACCA), which can simultaneously learn representation of multi-view data but also generate realistic multi-view samples. Comprehensive experiments have been conducted on three real-world datasets and the results demonstrate the effectiveness of the proposed model. Our code is available at https://github.com/wenqifan03/DACCA.

In recent years, the computation security of edge computing has been raised as a major concern since the edge devices are often distributed on the edge of the network, less trustworthy than cloud servers and have limited storage/ computation/ communication resources. Recently, coded computing has been proposed to protect the confidentiality of computing data under edge device's independent attack and minimize the total cost (resource consumption) of edge system. In this paper, for the cooperative attack, we design an efficient scheme to ensure the information-theory security (ITS) of user's data and further reduce the total cost of edge system. Specifically, we take matrix multiplication as an example, which is an important module appeared in many application operations. Moreover, we theoretically analyze the necessary and sufficient conditions for the existence of feasible scheme, prove the security and decodeability of the proposed scheme. We also prove the effectiveness of the proposed scheme through considerable simulation experiments. Compared with the existing schemes, the proposed scheme further reduces the total cost of edge system. The experiments also show a trade-off between storage and communication.

Vehicular communication networking (VCN) has been widely recognized as a promising solution to support safety-related applications in urban transportation systems. In VCN, efficient message dissemination can let vehicles be better aware of the potential risks and traffic anomalies, which is critical to road safety and traffic efficiency. Substantial studies have focused on the design of inter-vehicle message dissemination protocols. Nonetheless, most existing designs only consider the rapid end-to-end transmission, few of which take into account the broadcast coverage. In this paper, we propose a new message dissemination scheme in the urban traffic scenario by considering both the time constraint and the spatial distribution of data dissemination. Specifically, based on the temporal and spatial correlation of vehicle trajectory, relay vehicles are selected to construct a temporary warning network (TWN) for a rapid safety message dissemination in the regions of interest (ROI). Finally, we conduct extensive numerical experiments to validate the effectiveness of our method in various traffic scenarios.

Cyber-security issues on adversarial attacks are actively studied in the field of computer vision with the camera as the main sensor source to obtain the input image or video data. However, in modern cyber-physical systems (CPSs), many other types of sensors are becoming popularly used, such as surveillance sensors, microphones, and textual interfaces. A series of recent works investigates the adversarial attacks and the potential defenses in these noncamera sensor-based CPSs. Therefore, this article provides a systematic discussion on these existing works and serves as a complimentary summary of the adversarial attacks and defenses for CPSs beyond the field of computer vision. We first introduce a general working flow for adversarial attacks on CPSs. On this basis, a clear taxonomy is provided to organize existing attacks effectively and indicate where the defenses can be potentially performed in CPSs as well. Then, we discuss these existing attacks and defenses with detailed comparison studies. Finally, we point out concrete research opportunities to be further explored along this research direction.

Network performance tomography infers performance metrics on internal network links with end-to-end measurements. Existing results in this domain are mainly Boolean-based, i.e., they check whether or not a link is identifiable, and return the exact value on identifiable links. If a link is not identifiable, the Boolean-based solution gives no performance result for the link. In this paper, we extend Boolean-based network tomography to bound-based network tomography where the lower and upper bounds are derived for unidentifiable links. We develop an efficient algorithm to obtain the tightest total error bound, and present a solution that can significantly reduce the total number of measurement paths required for deriving the tightest total error bound. Furthermore, we propose a method to deploy a new monitor such that the total error bound could be maximally reduced. Compared to the random monitor deployment and the monitor deployment that maximizes the total number of identifiable links, our monitor deployment method can lead to up to 15 and 2.4 times more reduction on total error bound, respectively.

In the past decade, unmanned aircraft systems (UASs) have been widely used in various civilian applications, most of which involve only a single unmanned aerial vehicle (UAV). In the near future, more and more UAS applications will be facilitated by the cooperation of multiple UAVs. In such applications, it is desirable to utilize a general control platform for cooperative UAVs. However, existing open-source control platforms cannot fulfill such a demand because (1) they only support the leader-follower mode, which limits the design options for fleet control, (2) existing platforms can support only certain type of UAVs and thus lack compatibility, and (3) these platforms cannot accurately simulate a flight mission, which may cause a big gap between simulation and real-world flight. To address these issues, we propose a general control and monitoring platform for cooperative UAS, namely, CoUAS , which provides a set of core cooperation services of UAVs, including synchronization, connectivity management, path planning, energy simulation, and so on. To verify the applicability of CoUAS, we design and develop a prototype in which an embedded path planning service is provided to complete any task with the minimum flying time while considering the network connectivity and coverage. Experimental results by both simulation and field test demonstrate that the proposed system is viable.

In cloud computing, it is crucial to maintain service continuity, while power outage is one of the most common and serious threats. To improve the resilience of cloud against power outage, a service provider usually deploys emergency energy supply (e.g., UPSs and generators) in a data center. When a power outage at a data center happens, the cloud service provider needs to make the operation decision on which subset of VMs to keep running and which servers to host such VMs to minimize its loss (or maximize its profit) using the emergency energy supply while the selected VMs are running in the affected data center until they are finished, migrated to other data centers, or normal power supply of the affected data center has been restored. No prior research has theoretically studied such a cloud service continuity problem under power outage. In this paper, we tackle this challenge and investigate the cloud service continuity problem. Specifically, we consider that a profit is associated with maintaining the continuity of a service, denoted as service continuity profit. Based on that we first formulate an optimization problem that aims to maximize the total profit subject to energy constrains. After showing the hardness of the problem, we focus on the design of approximation algorithms for solving the problem, where we consider two practical cases. In the first one with sufficient number of servers for re-provisioning, we develop a constant approximation algorithm of which the worst-case performance approaches the optimal solution within a constant factor (≈4.5-6.4). In the second one, we consider the general case with limited number of servers, and we develop an approximation algorithm with an approximation ratio of around 5.7-8. By combining these two algorithms together, we can achieve both good worst-case performance and average performance. Simulation results demonstrate the efficiency in terms of maximizing the service continuity profit of the proposed algorithms.

In recent years, edge computing has attracted increasing attention for its capability of facilitating delay-sensitive applications. In the implementation of edge computing, however, data confidentiality has been raised as a major concern because edge devices may be untrustable. In this paper, we propose a design of secure and efficient edge computing by linear coding. In general, linear coding can achieve data confidentiality by adding random information to the original data before they are distributed to edge devices. To this end, it is important to carefully design code such that the user can successfully decode the final result while achieving security requirements. Meanwhile, task allocation, which selects a set of edge devices to participate in a computation task, affects not only the total resource consumption, including computation, storage, and communication, but also coding design. In this paper, we study task allocation and coding design, two highly-coupled problems in secure coded edge computing, in a unified framework. In particular, we take matrix multiplication, a fundamental building block of many distributed machine learning algorithms, as the representative computation task, and study optimal task allocation and coding design to minimize resource consumption while achieving information-theoretic security.

Edge computing is attracting more and more attention in recent years to fulfill the requirements of latency-critical and computation-intensive applications. By using the coding redundancy, coded edge computing has emerged to optimize the total computation latency. Compared with the servers in cloud computing, edge devices located at the edge of network may not be reliable and trustworthy. In coded edge computing, even one incorrect intermediate result will lead to the incorrect final result. Therefore, considering the low computation capabilities of edge devices and low latency requirements of user, we study the result verification problem for coded edge computing. Specifically, we propose an efficient Orthogonal Mark (OM) verification scheme by the properties of linear space. We also conduct solid theoretical analysis to show the successful verification probabilities under two kinds of attack models, respectively. Finally, we conduct extensive simulations to show the effectiveness of the proposed OM verification scheme when comparing with basic coded edge computing scheme and Decoding Comparison (DC) scheme.

Recent years have witnessed rapid developments on social recommendation techniques for improving the performance of recommender systems due to the growing influence of social networks to our daily life. The majority of existing social recommendation methods unify user representation for the user-item interactions (item domain) and user-user connections (social domain). However, it may restrain user representation learning in each respective domain, since users behave and interact differently in the two domains, which makes their representations to be heterogeneous. In addition, most of traditional recommender systems can not efficiently optimize these objectives, since they utilize negative sampling technique which is unable to provide enough informative guidance towards the training during the optimization process. In this paper, to address the aforementioned challenges, we propose a novel deep adversarial social recommendation framework DASO. It adopts a bidirectional mapping method to transfer users' information between social domain and item domain using adversarial learning. Comprehensive experiments on two real-world datasets show the effectiveness of the proposed framework.

Network performance tomography infers performance metrics on internal network links with end-to-end measurements. Existing results in this domain are mainly Boolean-based, i.e., they check whether or not a link is identifiable, and return the exact value on identifiable links. If a link is not identifiable, Boolean-based solution gives no performance result for the link. In this paper, we extend Boolean-based network tomography to bound-based network tomography where the lower and upper bounds are derived for unidentifiable links. We develop an efficient algorithm to obtain the tightest total error bound, and present a solution that can significantly reduce the total number of measurement paths required for deriving the tightest total error bound. Furthermore, we propose a method to deploy a new monitor over existing ones such that the total error bound could be maximally reduced. Compared to the random monitor deployment and the monitor deployment that maximizes the total number of identifiable links, our monitor deployment method can lead to up to 15 and 2.4 times more reduction on total error bound, respectively.

The success of machine learning in domains such as computer vision and computer games has triggered a surge of interest in applying machine learning in computer networks. This paper tries to answer a broadly-debated question: can we improve the performance of intradomain routing, one of the most fundamental blocks in the Internet, with reinforcement learning (RL)? Due to the complex network traffic conditions and the large action space in routing, it is difficult to give a definite answer for existing RL-based routing solutions. To gain an in-depth understanding on the challenges of RL-based routing, we systematically classify different RL-based routing solutions and investigate the performance of several representative approaches, in terms of scalability, stability, robustness, and convergence. With the lessons learned in evaluating various RL-based routing solutions, we propose two methods, called supervised Q-network routing (SQR) and discrete link weight-based routing (DLWR), which boost the performance of RL-based routing and outperform the de facto shortest path intradomain routing.

Recommender systems are crucial to alleviate the information overload problem in online worlds. Most of the modern recommender systems capture users' preference towards items via their interactions based on collaborative filtering techniques. In addition to the user-item interactions, social networks can also provide useful information to understand users' preference as suggested by the social theories such as homophily and influence. Recently, deep neural networks have been utilized for social recommendations, which facilitate both the user-item interactions and the social network information. However, most of these models cannot take full advantage of the social network information. They only use information from direct neighbors, but distant neighbors can also provide helpful information. Meanwhile, most of these models treat neighbors' information equally without considering the specific recommendations. However, for a specific recommendation case, the information relevant to the specific item would be helpful. Besides, most of these models do not explicitly capture the neighbor's opinions to items for social recommendations, while different opinions could affect the user differently. In this paper, to address the aforementioned challenges, we propose DSCF, a Deep Social Collaborative Filtering framework, which can exploit the social relations with various aspects for recommender systems. Comprehensive experiments on two-real world datasets show the effectiveness of the proposed framework.

BACKGROUND: Identifying splice sites is a necessary step to analyze the location and structure of genes. Two dinucleotides, GT and AG, are highly frequent on splice sites, and many other patterns are also on splice sites with important biological functions. Meanwhile, the dinucleotides occur frequently at the sequences without splice sites, which makes the prediction prone to generate false positives. Most existing tools select all the sequences with the two dimers and then focus on distinguishing the true splice sites from those pseudo ones. Such an approach will lead to a decrease in false positives; however, it will result in non-canonical splice sites missing. RESULT: We have designed SpliceFinder based on convolutional neural network (CNN) to predict splice sites. To achieve the ab initio prediction, we used human genomic data to train our neural network. An iterative approach is adopted to reconstruct the dataset, which tackles the data unbalance problem and forces the model to learn more features of splice sites. The proposed CNN obtains the classification accuracy of 90.25%, which is 10% higher than the existing algorithms. The method outperforms other existing methods in terms of area under receiver operating characteristics (AUC), recall, precision, and F1 score. Furthermore, SpliceFinder can find the exact position of splice sites on long genomic sequences with a sliding window. Compared with other state-of-the-art splice site prediction tools, SpliceFinder generates results in about half lower false positive while keeping recall higher than 0.8. Also, SpliceFinder captures the non-canonical splice sites. In addition, SpliceFinder performs well on the genomic sequences of Drosophila melanogaster, Mus musculus, Rattus, and Danio rerio without retraining. CONCLUSION: Based on CNN, we have proposed a new ab initio splice site prediction tool, SpliceFinder, which generates less false positives and can detect non-canonical splice sites. Additionally, SpliceFinder is transferable to other species without retraining. The source code and additional materials are available at https://gitlab.deepomics.org/wangruohan/SpliceFinder.

The ability to accurately track pedestrians is valuable for various application designs. Although pedestrian tracking has been investigated extensively and owns a well-suited sensing platform, the proposed solutions are far from being mature yet. Pedestrian tracking contains step counting and stride estimation two components. Step counting already has commercial products, but the performance is still unreliable and less trustworthy in practice. Stride estimation even stays in the research stage without ready solutions released on the market. Such a non-negligible gap between the long-term research investigation and technique's actual usage exists due to a series of crucial applicability issues unsolved, including design's vulnerability to interfering activities, extracting purely body's movement from mixed sensor signals, and parameter training without user's intervention. In this paper, we deeply analyze human's gait cycles and obtain inspiring observations to address these issues. We incorporate our techniques into existing pedestrian tracking designs and implement a prototype, PTrack, on LG smartwatch. We find that PTrack effectively enhances the system applicability and achieves promising performance under very practical settings.

In this article, we propose a mobile system, Aware , which turns our wearable or mobile device into a ruler. It can estimate the size of objects that could be large in size and not directly touchable by the user. Such a design will enable a rich set of applications that count on the size information of surrounding environments/objects. Aware purely utilizes the motion sensors on the device for object size measures. It can also integrate with the crowdsourcing feature for both performance improvement and result sharing. We propose a series of key techniques to address three major challenges in the Aware design: (1) user’s angle of line-of-sights to the object is used in the size measure but motion sensors track only the angle of arm’s waving, (2) motion sensors are noisy that require novel and effective data processing techniques, otherwise the errors could easily overwhelm the final result, and (3) in the crowdsourcing mode, Aware needs to identify vicinal objects of similar sizes and effectively fuse the measured sizes that correspond to the same object. We consolidate the above designs and implement Aware on Android platforms. Extensive experiments with four users show that Aware can achieve accurate measurement performance for the objects of various sizes in both indoor and outdoor environments.

It is envisioned that many different types of applications, each requesting a different set of network functions with different quality of service requirements, will run on 5G networks. To accommodate such requests, network slicing, which dynamically creates virtual networks for different types of applications, is proposed in the literature and IETF. A critical issue for the success of network slicing is to determine the amount of resources for a slice to ensure the required quality of service, i.e., the relationship among traffic demand, resource, and delay. This paper aims to tackle this problem. We first study the delay bound for a given traffic distribution and amount of resources using Stochastic Network Calculus (SNC). Then we propose a solution to derive the amount of resources that should be allocated to meet a given delay bound for a given traffic distribution. Extensive simulations show that given the derived amount of resources, the experienced end-to-end delay is less than the given delay bound. However, if only 90% of the derived amount of resources is given, the experienced end-to-end delay is much higher than the allowed delay bound. This demonstrates that the derived amount of resources is close to the minimum amount of resources for ensuring quality of service. The work provides a useful tool for network slice tenants to decide the amount of resources to request from physical network providers.

In the “network-as-a-service” paradigm, network operators have a strong need to know the metrics of critical paths running services to their users/tenants. However, it is usually prohibitive to directly measure the metrics of all such paths due to the measuring overhead. A practical solution is to use network tomography to infer the metrics of such paths based on observations from a small number of monitoring nodes. This problem is termed as path identifiability problem, a new problem that largely differs from existing link identifiability problems. we show that the new problem is harder than link identifiability problems, in the sense that fewer monitors are required for identifying the metrics of given paths than for identifying the metrics of links along the paths. To solve the problem, we develop sufficient and necessary conditions for the identifiability of a given set of interested paths, and design an efficient algorithm that deploys the minimum number of monitors. Experiments show a saving of up to 40% fewer monitors that guarantee the identifiability of a given set of paths.

To protect user privacy, many smartphone systems adopt the permission-based mechanism in which a user can evaluate the risk of requests for private information from a mobile app before installing it. However, recent studies show that the permission based mechanism is vulnerable to application collusion attacks because two apps, which appear to be harmless individually, can establish a covert channel and use it to leak confidential information. Consequently, people have designed some covert channel detection schemes, by checking abnormal status of the phone. In this paper, we point out that existing covert channel detection schemes may fail to detect a new type of collusion attacks referred as user-behavior-based covert channels. We implement three covert channels on Android smartphones. Our work sets a new alarm for the security issue of using smartphones. We then study the countermeasures to this new type of covert channels. Instead of trying to directly detect the proposed new type of covert channels, we propose two mitigation solutions to reduce the effectiveness of such covert channels. The mitigation solutions are also valid to other existing sensor-based side channels and/or covert channels on the phone.

The ability to accurately track pedestrians is valuable for variant application designs. Although pedestrian tracking has been investigated excessively and owned a well-suited sensing platform, the proposed solutions are far from being mature yet. Pedestrian tracking contains step counting and stride estimation two components. Step counting already has commercial products, but the performance is still unreliable and less trustworthy in practice. Stride estimation even stays in the research stage without ready solutions released on the market. Such a non-negligible gap between long-term research investigation and technique's actual usage exists due to a series of crucial applicability issues unsolved, including design vulnerability to interfering activities, extracting purely body's movement from additive sensor signals, and parameter training without user's intervention. In this paper, we deeply analyze human's gait cycles and obtain inspiring observations to address these issues. We incorporate our techniques into existing pedestrian tracking designs and implement a prototype, PTrack, on LG smartwatch. We find PTrack effectively enhances the system applicability and achieves promising performance under very practical settings.

The fast development of mobile networks calls for the massive consumption of materials, land, and energy in building and maintaining infrastructures, which is always intensified by the repetitive constructions of competing network operators. To reduce the resource consumption for social benefit, one business solution, implemented in the Chinese telecom industry, is forming a joint venture responsible for building and maintaining common infrastructures. The novelty of this practice is that the joint venture is shared by the competing operators who also rent infrastructures from the joint venture. We note that such a solution can be potentially generalized to other industries for reducing resource consumption. However, before generalization, an understanding of the pros and cons from the economic perspective of the business model is urgently needed. In this paper, we study this business model from a game theoretic approach. Our results show that if we properly regulate the joint venture, the market can converge to equilibriums with desirable properties which cannot be achieved without the joint venture. Furthermore, we also study the investment reduction in the presence of the joint venture. Our numerical results show that under a moderate user density, the total investment on the infrastructures can be significantly reduced.

In crowdsourcing markets, a requester announces a task and calls for contribution from potential participants. With strategic participants, the requester needs to reward the participants to introduce the incentives of participation. However, it is natural to ask whether it is worth introducing incentives if the total payment for eliciting incentives is too high. This paper addresses such a fundamental concern by designing a frugal mechanism with minimum payment used to procure the total amount of service contributions demanded. We design two mechanisms to provide the incentives of participation while minimizing the payment used by the requester. We first propose a frugal auction-based mechanism, which stimulates participants to truthfully report their information. We theoretically prove that the payment used is not more than the optimal cost (with no incentive considered) plus a bounded additive. We then design a Stackelberg-game-based mechanism, in which the requester fixes a certain total payment at the very beginning so as to encourage the participants to compete for it and participate in the task. We verify the existence of a unique Nash equilibrium (NE) and develop a novel algorithm to find the NE, as well as the optimal payment to extract the NE. Our simulation results show that the payment used in these mechanisms is close to the optimal solution with no incentive considered, while the extra payment caused by introducing truthfulness in auction-based mechanism is about twice that of the NE in Stakelberg-game-based mechanism.

With the advances of Internet of Things technologies, individual vehicles can now exchange information to improve traffic safety, and some vehicles can further improve safety and efficiency by coordinating their mobility via cooperative driving. To facilitate these applications, many studies have been focused on the design of inter-vehicle message dissemination protocols. However, most existing designs either assume individual driving pattern or consider cooperative driving only. Moreover, few of them fully exploit infrastructures, such as cameras, sensors, and road-side units. In this paper, we address the design of message dissemination that supports heterogeneous driving patterns. Specifically, we first propose an infrastructure-assisted message dissemination framework that can utilize the capability of infrastructures. We then present a novel beacon scheduling algorithm that aims at guaranteeing the timely and reliable delivery of both periodic beacon messages for cooperative driving and event-triggered safety messages for individual driving. To evaluate the performance of the protocol, we develop both theoretical analysis and simulation experiments. Extensive numerical results confirm the effectiveness of the proposed protocol.

Energy harvesting communication system enables energy to be dynamically harvested from natural resources and stored in capacitated batteries to be used for future data transmission. In such a system, the amount of future energy to harvest is uncertain and the battery capacity is limited. As a consequence, battery overflow and energy dropping may happen, causing energy underutilization. To maximize the data throughput by using the energy efficiently, a rate-adaptive transmission schedule must address the trade-off between a high-rate transmission which avoids energy overflow and a low-rate transmission which avoids energy shortage. In this paper, we study an online throughput maximization problem without knowing future information. To the best of our knowledge, this is the first work studying the fully-online transmission rate scheduling problem for battery-capacitated energy harvesting communication systems. We consider the problem under two models of the communication channel, a static channel model that assumes the channel status is stable, and a fading channel model that assumes the channel status varies. For the former, we develop an online algorithm that approximates the offline optimal solution within a constant factor for all possible inputs. For the latter, that the channel gains vary in range [hmin; hmax], we propose an online algorithm with a proven ⊖(log(hmax/ hmin))-competitive ratio. Our simulation results further validate the efficiency of the proposed online algorithms.

Network Functions Virtualization (NFV) has recently gained momentum among network operators as a means to share their physical infrastructure among virtual operators, which can independently compose and configure their communication services. However, the spatio-temporal correlation of traffic demands and computational loads can result in high congestion and low network performance for virtual operators, thus leading to service level agreement breaches. In this paper, we analyze the congestion resulting from the sharing of the physical infrastructure and propose innovative orchestration mechanisms based on both centralized and distributed approaches, aimed at unleashing the potential of the NFV technology. In particular, we first formulate the network functions composition problem as a non-linear optimization model to accurately capture the congestion of physical resources. To further simplify the network management, we also propose a dynamic pricing strategy of network resources, proving that the resulting system achieves a stable equilibrium in a completely distributed fashion, even when all virtual operators independently select their best network configuration. Numerical results show that the proposed approaches consistently reduce resource congestion. Furthermore, the distributed solution well approaches the performance that can be achieved using a centralized network orchestration system.

In the field of cloud computing, cloud service composition integrates a group of collaborative sub-services to fulfill a specific business model. Composite cloud service is widely used and is normally implemented by distributed sub-services over the cloud, each modelled as a virtualized function (VF). It is critical that the composite cloud service maintains high Quality of Service (QoS) in the presence of highly-dynamic service requests. The challenge is that each VF has only a myopic view of the whole service process, and scaling up/down individual VF with existing cloud resource auto-scaling strategies does not necessarily lead to better QoS for end users. To solve the problem, this paper proposes an auto-scaling strategy that requires VFs to adjust their cloud resources collaboratively. For collaborative auto-scaling, it is critical to capture the dependence among multiple VFs, and to achieve this goal, we present a novel framework based on copula models to analyze the amount of service calls that may change at different rates for different VFs. We demonstrate how to orchestrate auto-scaling of VFs by predicting future service calls using the temporal dependence captured in the copula model. With real-world trace as well as synthetic data, we demonstrate the benefit of collaborative auto-scaling guided by the copula model.

In recent years, many cross-VM covert channels have been discovered in cloud computing, causing serious security concerns. For such covert channels, some mitigation schemes have been proposed, but usually one mitigation scheme aims at a specific covert channel, which may be inefficient in defending against potential new attacks. In this paper, we propose a generic solution to mitigate the risk of a broad class of timing-based cross-VM covert channels. The design is motivated by our finding that the capacity of most timing-based cross-VM covert channels highly depends on the co-run probability among VMs, where the co-run probability depends not only on how VMs are assigned to servers, but also how VMs are scheduled on a single server, which is related to managing the vCPUs assigned to each VM. We find that the VM co-run probability can be reduced when the number of vCPUs increases, but it also causes extra system overhead in resource utilization. In this paper, we propose a generic VM provisioning and VM scheduling solution to jointly minimize the co-run probability among VMs, meanwhile, maintaining high resource utilization. We experimentally demonstrate that the proposed scheduling algorithm can mitigate the risk of timing-based cross-VM covert channel with lower system overhead. We also conduct simulation of VM provisioning which shows that the proposed solution can achieve the balance between high resource utilization and low risk of information leakage caused by cross-VM covert channels.

Detecting anomalous Border Gateway Protocol (BGP) traffic is significantly important in improving both security and robustness of the Internet. Existing solutions apply classic classifiers to make real-time decision based on the traffic features of present moment. However, due to the frequently happening burst and noise in dynamic Internet traffic, the decision based on short-term features is not reliable. To address this problem, we propose MS-LSTM, a multi-scale Long Short-Term Memory (LSTM) model to consider the Internet flow as a multi-dimensional time sequence and learn the traffic pattern from historical features in a sliding time window. In addition, we find that adopting different time scale to preprocess the traffic flow has great impact on the performance of all classifiers. In this paper, comprehensive experiments are conducted and the results show that a proper time scale can improve about 10% accuracy of LSTM as well as all conventional machine learning methods. Particularly, MS-LSTM with optimal time scale 8 can achieve 99.5% accuracy in the best case.

For many emerging mobile broadband services and applications, the source and destination are located in the same local region. Consequently, it is very important to design access networks to facilitate efficient local data exchange. In the past few years, most existing studies focus on either the wired or wireless domains. In this paper, we aim to exploit both the wired and wireless domains. Specifically, we consider a Fiber-Wireless access network in which a passive optical network (PON) connects densely deployed base stations. In such a scenario, we propose a novel access scheme, namely, NCDA, where the main idea is to utilize both network coding and device association. To understand the potentials of NCDA, we first formulate a mixed integer nonlinear programming (MINLP) to minimize the weighted number of packet transmissions (WNT), which is related to both the system capacity and energy consumption. We then theoretically analyze the tight upper bounds of the minimal WNT in the PON, which helps us to approximate the original problem by a mixed integer linear programming (MILP). Next, we develop efficient algorithms based on linear programming relaxation to solve the optimal NCDA problem. To validate our design, we conduct extensive simulation experiments, which demonstrate the impact of important network parameters and the promising potentials of the proposed scheme.

As a major driving force for adopting cloud computing, continuous cost reduction has been constantly pursued by cloud users. For a group of users with heterogeneous cloud resource demands, it may be possible for them to buy resources in a collaborative way in order to save the purchase cost, which is known as group-buying in business. While group-buying can benefit cloud users in principle, the question is how to design an implementation scheme to support group-buying on the cloud market. In this paper, we address the question by studying a coalition formation game, aiming to design a way under which the users can form stable coalitions for group-buying. It turns out that group-buying on the cloud market is challenging in that most popular solution concepts may fail to constitute stable coalitions. In order to sustain group-buying for cloud services, we propose a new solution concept, contractually group stable, which is an extension of an existing concept in the literature. We show that this new solution concept can guarantee the existence of stable coalitions, making group-buying always possible on the cloud market. We also develop computing algorithms for solving the coalition formation game under our concept. Computational experiments show that our concept can bring in substantial cost reduction for cloud users.

In a participatory sensing system, data sensed from smartphone users are shared with the general public who requests data through submitting tasks. When multiple tasks request the data from a mobile user, the mobile user can make a transmission schedule to achieve the balance between the amount of data transmitted and energy consumption. Intuitively, reducing the amount of data transmitted by making use of data sharing between the tasks can save the energy consumption. However, due to the convexity of rate-power function for rate-adaptive transmitting devices, a schedule purely minimizing the amount of data transmitted may not always be the optimal one minimizing the energy consumption. Thus, there exists a tradeoff between the amount of data transmitted and energy consumption. This paper formulates the problem as a bi-objective optimization problem to simultaneously minimize the amount of data transmitted and the energy consumption. Two task models are studied, first-in-first-out (FIFO) task model and arbitrary deadline (AD) task model, respectively. We first provide optimal algorithms for the off-line case. We then study the online case where requests arrive dynamically without prior information. For FIFO tasks, we develop an online algorithm that is O(ln L)-competitive with respect to both the amount of data transmitted and energy consumption, where L is the longest length of the time duration of the tasks. For AD tasks, we devise an online algorithm that is O(ln2L)-competitive with respect to both the amount of data transmitted and energy consumption. Our simulation results validate the efficiency of our online algorithms.

In-network content caching has been a natural trend in emerging network architectures to handle the exponential growth of video traffic. However, due to the potentially wide attacking surfaces, caching video content in the increasingly untrusted networked environment inevitably raises new concerns on user privacy exposure and unauthorized video access. Existing encrypted protocols like HTTPs either fall short of fully leveraging in-network caching or require decrypting the traffic in the middle without guaranteeing the end-to-end security. In this paper, we present a new networked system for efficient encrypted video delivery while preserving the benefits of in-network caching. As video chunks are encrypted before distribution, we first design a compact, efficient, yet encrypted video fingerprint index to empower the network with a fully controlled capability of locating the cached encrypted chunks for given encrypted requests. We then explain how to deploy the encrypted design in our proposed architecture and present a secure redundancy elimination protocol to enable fast video delivery via leveraging cached encrypted chunks. We further discuss the full support of cache management, adaptive video delivery, and video access control. Rigorous analysis and prototype evaluations demonstrate the security, efficiency, and effectiveness of the design.

Wireless sensor networks (WSNs) are increasingly deployed for mission-critical applications such as emergency management and health care, which impose stringent requirements on the communication performance of WSNs. To support these applications, it is crucial to model and measure the effect of wireless interference, which is the major factor that limits WSN performance. Accurate modeling and measurement of interference faces two key challenges. First, as shown in our experimental results, interference yields considerable spatial and temporal variations of WSN performance, which poses a major challenge for measurement at rum-time. Second, in the unlicensed band, the communication of WSN is interfered by coexisting wireless devices such as smartphones and laptops equipped with 802.11 radios, which lead to cross-technology interference that are difficult to characterize due to the heterogeneous PHY. To tackle these challenges, this paper presents a novel accuracy-aware approach to interference modeling and measurement for WSNs. First, we propose a new regression-based interference model and analytically characterize its accuracy based on statistics theory. Second, we develop a novel protocol called accuracy-aware interference measurement for measuring the proposed interference model with assured accuracy at run time. Third, building on interference modeling, we propose an algorithm that accurately forecasts the performance of WSNs in the presence of cross-technology interference. Our extensive experiments on a testbed of 17 TelosB motes show that the proposed approaches achieve high accuracy of interference modeling and WSN performance forecasting with significantly lower overhead than state-of-the-art approaches.

The continuous growth of media-rich content calls for more efficient and secure methods for content delivery. In this paper, we will address the optimallinear network coding(LNC) design forsecure unicast streamingagainst passive attacks, under the requirement ofinformation theoretical security. The objectives include 1) satisfying the information theoretical security requirement, 2) maximizing the transmission rate of a unicast stream, 3) minimizing the number of additional random symbols, and 4) minimizing the total bandwidth cost of content delivery. To fulfill the first three objectives, we formulate aninformation theoretically secure unicast streaming(ITSUS) problem, and then solve it by transforming it to a maximum network flow problem with node-capacity constraints. Based on the solution of the ITSUS problem, we develop an efficient algorithm that can find the optimal transmission topology with minimum bandwidth cost in a polynomial amount of time. With the optimal transmission topology, we investigate the design of bothdeterministicLNC and random LNC. For thedeterministicLNC design, we not only prove that it achieves the four objectives but also analyze the size of required finite field. Moreover, for the random LNC design, we analyze the probability that a random LNC scheme satisfies the information theoretical security requirement. Finally, extensive simulation experiments have been conducted, and the results demonstrate the effectiveness of the proposed algorithms.

With the booming cloud computing industry, computational resources are readily and elastically available to the customers. In order to attract customers with various demands, most Infrastructure-as-a-service (IaaS) cloud service providers offer several pricing strategies such as pay as you go, pay less per unit when you use more (so called volume discount), and pay even less when you reserve. The diverse pricing schemes among different IaaS service providers or even in the same provider form a complex economic landscape that nurtures the market of cloud brokers. By strategically scheduling multiple customers' resource requests, a cloud broker can fully take advantage of the discounts offered by cloud service providers. In this paper, we focus on how a broker can help a group of customers to fully utilize the volume discount pricing strategy offered by cloud service providers through cost-efficient online resource scheduling. We present a randomized online stack-centric scheduling algorithm (ROSA) and theoretically prove the lower bound of its competitive ratio. Three special cases of the offline concave cost scheduling problem and the corresponding optimal algorithms are introduced. Our simulation shows that ROSA achieves a competitive ratio close to the theoretical lower bound under the special cases. Trace-driven simulation using Google cluster data demonstrates that ROSA is superior to the conventional online scheduling algorithms in terms of cost saving.

To efficiently provide cloud storage services, most providers implement data deduplication schemes so as to reduce storage and network bandwidth consumption. Due to its broad application, many security issues about data deduplication have been investigated, such as data security, user privacy, etc. Nevertheless, we note that the threat of establishing covert channel over cloud storage has not been fully investigated. In particular, existing studies only demonstrate the potential of a single-bit channel, in which a sender can upload one of the two predefined files for a receiver to infer the information of "0" and "1". In this paper, we design a more powerful deduplicationbased covert channel that can be used to transmit a complete message. Specifically, the key features of our design include: (1) a synchronization scheme that can establish a covert channel between a sender and a receiver, and (2) a novel coding scheme that allows each file to represent multiple bits in the message. To evaluate the proposed design, we implement the covert channel and conduct extensive experiments in different cloud storage systems. Our work highlights a more severe security threat in cloud storage services.

Covert channel is a classical threat to cyber security because it aims to transfer data between entities that are not allowed to exchange information. To enhance the security of cyber systems, many covert channels have been identified and investigated, in which IP-timing covert channel is one of the important risks because IP is the dominating communication protocol for computer networks. However, despite the potential risks, existing IP-timing covert channels seem to be less significant because most of them carry information by arbitrary inter-packet delays, which leads to low transmission rates and can be easily detected. In this paper, we identify a novel IP-timing covert channel that can significantly increase the transmission rate. Specifically, we propose a new framework for IP-timing covert channel, where the main idea is to use the routes to carry information. Based on the framework, we present the detailed designs for IP-timing covert channels based on TCP and UDP, in which we develop new technique to reduce the channel error rate. To evaluate the performance of the proposed covert channels, we also implement them in realistic systems and conduct extensive experiments. The experimental results show that the proposed IP-timing covert channel achieves 15 times higher rate than existing channels with less than 0.54% error rate. This study shows that the risk of IP-timing channel can be more serious than expected, which requires more sophisticated countermeasures.

To protect user privacy, many smartphone systems, such as Android and Windows Phone, adopt the permission-based mechanism in which a user can evaluate the request of private information by a mobile app before installing it. However, recent studies show that the permission-based mechanism is vulnerable to application colluding attacks because two apps, which appear to be harmless individually, can establish a covert channel and use it to leak confidential information. In general, existing known covert channels usually work in a way that one app can modify the status of a system component, while the other can read the status. Even though several covert channel detection schemes have been proposed recently to fight against this type of covert channels, we point out that such designed covert channel detection schemes are not sufficient. In this paper, we demonstrate the possibility of establishing novel covert channels that work in quite different ways, in which one app (e.g., a game) can be designed deliberately such that the user will be induced to voluntarily modify the status of a system component (e.g., a motion sensor), while the other app can read the status of the system component. To validate our design, we implement three covert channels on Android. Our experiments show that these channels can bypass existing detection schemes. Moreover, we also measure the achievable throughput, error rate, and energy consumption in devices. The results demonstrate that our covert channels can achieve a transmission with high accuracy and low energy consumption. Our work sets a new alarm for the security issue of using smartphones.

In a wireless system, when multiple applications can share data transmitted by rate-adaptive wireless devices, there exists a trade-off between transmission redundancy and energy efficiency. This paper conducts the first theoretical analysis on such a trade-off. We formulate the problem as a bi-objective optimization problem to simultaneously minimize the transmission redundancy and the energy consumption. In the offline setting that the full information is known in advance, we provide optimal algorithms for the bi-objective optimization problem. In the online setting, we provide an online algorithm with proven performance bound to approximate the optimal solution without relying on any assumed distribution or future information. The proposed online algorithm is proved O(ln T)-competitive with respect to transmission redundancy and also O(ln T)-competitive with respect to energy consumption, where T is the number of time slots. That is, the output of the algorithm always approximates the optimal solution within a logarithmic factor over all possible inputs. Our simulation results further validate the efficiency of our online algorithm.

Network coding (NC) based opportunistic routing has been well studied, but the impact of routing diversity on the performance of NC-based routing remains largely unexplored. Towards understanding the importance of routing diversity in NC-based routing, we study the problems of estimating and minimizing the data delivery cost in NC-based routing. In particular, we propose an analytical framework for estimating the total number of packet transmissions for NC-based routing in arbitrary topologies. We design a greedy algorithm that minimizes the total transmission cost of NC-based routing and determines the corresponding forwarder set for each node. We prove the optimality of this algorithm and show that 1) nodes on the shortest path may not always be favored when selecting forwarders for NC-based routing and 2)the minimal cost of NC-based routing is upper-bounded by the cost of shortest path routing. Based on the greedy, optimal algorithm, we design and implement ONCR, a distributed minimal cost NC-based routing protocol. Using the NetEye sensor testbed, we comparatively study the performance of ONCR and existing approaches such as the single path routing protocol CTP and the NC-based opportunistic routing protocols MORE and CodeOR. Results show that ONCR achieves close to 100% delivery reliability while having the lowest delivery cost among all the protocols and 25-28% less than the second best protocol CTP. This low delivery cost also enables ONCR to achieve the highest network goodput, i.e., about two-fold improvement over MORE and CodeOR. Our findings demonstrate the significance of optimizing data forwarding diversity in NC-based routing for data delivery reliability, efficiency, and goodput.

Virtualization is one of the key enablers in cloud computing. At the same time, though, it is also widely considered as a double-edged sword that may cause information leakage between virtual machines (VM) co-residing on the same physical server via various cross-VM covert channels. In this paper, we first explore the impact of different bystander workloads on cross-VM covert channels. Then, we use a Continuous Time Markov Process to model the impact of bystanders on the cross-VM covert channel in terms of both the work scheduling of the virtualization platform and the intensity of the bystander workloads. Based on empirical study, we quantify the relationship between the influential factors and the transmission quality of the covert channel. A tailored and lightweight VM provisioning strategy, which aims to ensure that bystander workloads on each server can cause sufficiently high error rates to covert channels, is proposed to mitigate the threat of cross-VM covert channels while maintaining the resource efficiency of virtualization. The efficiency and efficacy of the proposed VM provisioning strategy is evaluated through trace-driven simulations.

Cross-VM covert channels leverage physical resources shared between co-resident virtual machines, like CPU cache, memory bus, and disk bus, to leak information. The capacity of cross-VM covert channels varies on different cloud platforms. Thus, it is hard for cloud service providers to estimate the risk of information leakage caused by cross-VM covert channels on their own platforms. In this paper, we develop an Auto Profiling Framework of Covert Channel Capacity (APFC3) to automatically profile the maximum capacities of various cross-VM covert channels on different cloud platforms. The framework consists of automated parameter tuning for various cross-VM covert channels to achieve high data rate and automated capacity estimation of those cross-VM covert channels. We evaluate the proposed framework by constructing fine-tuned cross-VM covert channels on different virtualization platforms and comparing the optimized achievable data rate with the estimated maximum capacity computed using the proposed framework. The experiments show that in most cases, the capacity estimated using APFC3 is very close to the achieved data rate of constructed covert channels with fine-tuned parameters.

Virtualization of network functions and services can significantly reduce capital and operational expenditures of telecommunication operators through the sharing of a single network infrastructure. However, the utilization of the same resources can increase their congestion due to the spatio-temporal correlation of traffic demands and computational loads. In this paper, we propose novel orchestration mechanisms to optimally control and reduce the resource congestion of a physical infrastructure based on the NFV paradigm. In particular, we formulate the network functions composition problem as a nonlinear optimization model to accurately capture the congestion of the physical resources. In order to meet both efficiency and load balancing goals of the physical operator, we introduce two variants of such model to minimize the total and the maximum congestion in the network. Our models allow us to efficiently compute the optimal solution in a short computing time. Numerical results, obtained with real ISP topologies and network instances, show that the proposed approach represents an efficient and practical solution to control the congestion in virtual networks. Furthermore, they indicate that a holistic approach that optimizes the virtual system by jointly considering all elements/components would further improve the performance.

With the booming growth of cloud computing industry, computational resources are readily and elastically available to the customers. In order to attract customers with various demands, most Infrastructure-as-a-service (IaaS) cloud service providers offer several pricing strategies such as pay as you go, pay less per unit when you use more (so called volume discount), and pay even less when you reserve. The diverse pricing schemes among different IaaS service providers or even in the same provider form a complex economic landscape that nurtures the market of cloud brokers. By strategically scheduling multiple customers' resource requests, a cloud broker can fully take advantage of the discounts offered by cloud service providers. In this paper, we focus on how a broker may help a group of customers to fully utilize the volume discount pricing strategy offered by cloud service providers through cost-efficient online resource scheduling. We present a randomized online stack-centric scheduling algorithm (ROSA) and theoretically prove the lower bound of its competitive ratio. Our simulation shows that ROSA achieves a competitive ratio close to the theoretical lower bound under a special case cost function. Trace driven simulation using Google cluster data demonstrates that ROSA is superior to the conventional online scheduling algorithms in terms of cost saving.

Mobile cloud provides smart phone users with unprecedented opportunities to enjoy the abundant computing and storage resources of cloud computing. One viable scheme is to offload computational intensive applications to a mobile phone's agent in the cloud, which could be implemented as a thin virtual machine (VM), also termed as phone clone, in the cloud. Due to shared hardware components (e.g. memory bus and CPU cache) among co-resident VMs, a VM is subject to covert channel attacks and may potentially leak information to other VMs located in the same physical host. Due to the large number of phone clones, it is not practical to guarantee absolute physical isolation of phone clones, and as such a phone clone may have to “dance with strangers” on the same host. In this paper, we address two critical problems in such a computing platform: how to allocate phone clones to minimize the risk of information leakage and how to migrate phone clones whenever the risk becomes higher than a given threshold. We design SWAP: a security aware provisioning and migration scheme for phone clones. Our solution utilizes the spatial and temporal features of phone clones, and by considering the online social connection of mobile users, we greatly simplify the search space of the optimal solution. Experimental results indicate that our algorithms are nearly optimal for phone clone allocation and are effective to maintain low risk with a small number of phone clone migrations.

The increasing demand for media-rich content has driven many efforts to redesign the Internet architecture. As one of the major candidates, information-centric network (ICN) has attracted significant attention, where in-network cache is a key component in different ICN architectures. In this paper, we propose a novel framework for optimal cache management in ICNs which jointly considers caching strategy and content routing. Specifically, we propose a cache management framework for ICNs based on software-defined networking (SDN) where a controller is responsible for determining the optimal caching strategy and content routing via linear network coding (LNC). Under the proposed cache management framework, we formally formulate the problem of minimizing the network bandwidth cost by jointly considering caching strategy and content routing with LNC. We develop an efficient network coding based cache management (NCCM) algorithm to obtain a near-optimal caching and routing solution for ICNs. We further develop a lower bound of the problem and conduct extensive experiments to compare the performance of the NCCM algorithm with the lower bound. Simulation results validate the effectiveness of the NCCM algorithm and framework.

One critical issue for vehicular safety applications is how to timely and reliably disseminate kinetic information, known as beacon, among vehicles. In this paper, we try to improve the beacon dissemination performance in vehicular ad hoc networks (VANETs) especially in drastic disturbance scenarios. To this end, a decentralized beacon dissemination control scheme (DBDCS) is proposed from the cyber-physical system perspective, where both the vehicle dynamics and VANET behaviors are jointly considered. In the envisioned scheme, the control channel interval for beacon dissemination can be adaptively adjusted based on both the current local traffic dynamics and the networking situation. Numerical results show that the proposed scheme can significantly improve the beacon dissemination performance especially in disturbance scenarios.

Network virtualization facilitates sharing and efficient utilization of computing and bandwidth resources of an underlying substrate network. As network virtualization becomes popular, it is important to efficiently map a virtual infrastructure (VI) onto a substrate network, such that the survivability of the former can be guaranteed against failures in the latter. In this paper, we study a virtualization layer approach to survivability, whereby the virtualization layer customizes a VI request with redundant nodes and links according to its reliability requirements and then passes limited information about the augmented VI to the physical layer, where the mapping of the augmented VI takes place. More specifically, we develop a flexible scheme to enhance the original VI graph with K redundant nodes, in order to fight against an arbitrary substrate node failure. In addition, a scenario-based component group (SBCG) concept is proposed to describe resource sharing of enhanced VI requests at the physical layer. We also develop an efficient heuristic that takes advantage of the limited information on SBCG to reduce costs when mapping the enhanced VI to the substrate network. The efficiency of the proposed solution is compared using extensive simulation under various performance metrics. It is shown that the K-redundant-node scheme with SBCG information is more cost efficient than the existing 1-redundant-node solution.

In mobile ad hoc networks (MANETs), it is important to understand the throughput-delay trade-off (TD trade-off) problem in large-scale scenarios. In the literature, the TD tradeoff problem has been studied extensively and many of them are based on the independent and identically distributed (i.i.d.) mobility model, in which each node can randomly move to any place in the network, after every time slot. Although the i.i.d. model has been widely used, it cannot fully represent MANETs in which nodes change positions less frequently. To characterize such MANETs, in this paper, we propose a generalized i.i.d. (g.i.i.d.) mobility model, in which each node moves once after every 1/f (0 < f ≤ 1) time slots, and remains static between two moves. To investigate the TD trade-off under the g.i.i.d. model, we develop a novel multi-relay multi-hop (MRMH) scheme that exploits the opportunities of multi-hop transmissions when the network is static. Furthermore, to enable the multi-hop transmissions, we construct a new percolation highway system, which has not been used in the TD trade-off analysis for MANETs. Using the proposed MRMH scheme, we develop and prove constructive bounds for throughput and delay in MANETs with different scales of f. Our constructive bound is asymptotically optimal for f = 1 (i.e., the i.i.d. model).

To protect user privacy in wireless mesh networks (WMNs), it is important to address two major challenges, namely: flow untraceability and movement untraceability, which prevent malicious attackers from deducing the flow paths and the movement tracks of mobile devices. For these two privacy requirements, most existing approaches rely on encrypting the whole packet, appending random padding, and applying random delay for each message at every intermediate node, resulting in significant computational and communication overheads. Recently, linear network coding (LNC) has been introduced as an alternative but the global encoding vectors (GEVs) of coded messages have to be encrypted so as to conceal the relationships between the incoming and outgoing messages. In this paper, we aim to explore the potential of LNC to ensure the flow untraceability and movement untraceability. Specifically, we first determine the necessary and sufficient condition, with which the two privacy requirements can be achieved without encrypting either GEVs or message contents. We then design a deterministic untraceable LNC (ULNC) scheme to provide flow untraceability and movement untraceability when the sufficient and necessary condition is satisfied. Finally, we discuss the effectiveness of the proposed ULNC scheme against traffic analysis attacks in WMNs.

Lack of proper maintenance is the root cause of anywhere from a third to a half of downtime events in a cloud data center. To help safeguard the uptime of data centers, regular preventive maintenance must be conducted. During the maintenance time, some accommodated virtual machines (VMs) may be re-provisioned to the other available (backup) resource through migration, and some VMs may be terminated. One way that can allow a data center to perform all necessary preventive maintenance activities without causing too much disruption to VMs is to design an appropriate maintenance schedule. In this paper, given the available resource in a data center and the required maintenance activities with their deadlines, we consider the joint VM resource provisioning and maintenance scheduling problem to maximize the revenue of the data center. We tackle the problem by firstly proposing a heuristic for the resource provisioning under a given maintenance schedule. Using such a heuristic algorithm as the building block, we then propose another heuristic algorithm to solve the joint resource provisioning and maintenance scheduling problem and also derive its upper bound. Extensive simulations have shown that our proposed heuristic algorithms can effectively maximize the revenue of the data center.

802.11-based wireless LANs (WLANs) have become an important communication infrastructure for today's pervasive computing applications. Nevertheless, WLAN users often experience various performance issues such as highly variable signal quality. To diagnose such transient service degradations and plan for future network upgrades, it is essential to closely monitor the performance of a WLAN and collect user statistics. This paper proposes a new WLAN performance monitoring approach motivated by the fact that many low-power wireless technologies such as ZigBee and Bluetooth co-exist with WLAN in the same open radio spectrum and are capable of sensing Received Signal Strength (RSS) of 802.11 transmissions. We have developed a ZigBee-based WLAN monitoring system called WizNet. Powered by batteries, ZigBee sensors of WizNet can be deployed in large quantities to monitor the spatial performance of a WLAN in long periods of time. By adopting digital signal processing techniques, WizNet automatically identifies 802.11 signals from ZigBee RSS measurements and associates them with wireless access points. To ensure the monitoring fidelity, WizNet accounts for the significant differences in ZigBee and WLAN radios, such as bandwidth and susceptibility to multipath and frequency-selective fading. A simple yet accurate linear estimator derived from a signal propagation model is used to infer the access points' signal to noise ratio (SNR). Moreover, WizNet can measure the congestion level of the channel and detect rogue APs. WizNet can also collect WLAN client statistics and classify device models based on RSS signatures of 802.11 access point scans. We have implemented WizNet in TinyOS 2.x and extensively evaluated its performance on a wireless testbed. Our results over a period of 140 hours show that WizNet can accurately capture the spatial and temporal performance variability of a large-scale production WLAN.

Epidemic evolution is the spread of a computer or biological virus over a network. The goal is to control the speed of the epidemic evolution with limited network control resources and to study how users in the network can be infected. The epidemic evolution can be modeled by a probabilistic dynamical system over a connected graph. We consider several epidemic evolution models in the literature, and formulate their evolution control under a common framework that requires solving a non convex optimization problem with an objective that is the spectral radius function of a nonnegative matrix. We propose two algorithms to tackle this optimization problem. The first one is a suboptimal but computation ally fast algorithm based on successive convex relaxation, while the second one can compute a global optimal solution using branch-and-bound techniques that leverage some key inequalities in non negative matrix theory.

To efficiently archive and query data in wireless sensor networks (WSNs), distributed storage systems, and multisink schemes have been proposed recently. However, such distributed access cannot be fully supported and exploited by existing routing protocols in a large-scale WSN. In this paper, we will address this challenging issue and propose a distributed geographic $(K)$-anycast routing (GKAR) protocol for WSNs, which can efficiently route data from a source sensor to any $(K)$ destinations (e.g., storage nodes or sinks). To guarantee $(K)$-delivery, an iterative approach is adopted in GKAR where in each round, GKAR will determine not only the next hops at each node, but also a set of potential destinations for every next hop node to reach. Efficient algorithms are designed to determine the selection of the next hops and destination set division at each intermediate node. We analyze the complexity of GKAR in each round and we also theoretically analyze the expected number of rounds required to guarantee $(K)$-delivery. Simulation results demonstrate the superiority of the GKAP scheme in reducing the total duration and the communication overhead for finding $(K)$ destinations, by comparing with the existing schemes, e.g., $(K 1)$-anycast [10].

In this paper, we will address the modeling and optimal design of linear network coding (LNC) for secure unicast with multiple streams between the same source and destination pair. The objectives include 1) satisfying the weakly secure requirements, 2) maximizing the transmission data rate, and 3) minimizing the size of the finite field. To fulfill the first two objectives, we formulate a secure unicast routing problem and prove that it is equivalent to a constrained link-disjoint path problem. Based on this fact, we develop an efficient algorithm that can find the optimal unicast topology in a polynomial amount of time. With the given topology, we investigate the design of both weakly secure deterministic LNC and weakly secure random LNC. In the designs of deterministic LNC and random LNC, we prove that the required size of the finite field decreases with the decrease of the number of intermediate nodes in the topology. Therefore, to meet the third objective, we formulate a problem to minimize the number of intermediate nodes. We prove that this problem is NP-Complete and develop an approximation algorithm to solve it. Finally, extensive simulation experiments have been conducted, and the results demonstrate the effectiveness of the proposed algorithms.

In most existing wireless networks, end users obtain data content from the wired network, typically, the Internet. In this manner, virtually all of their traffic must go through a few access points, which implies that the capacity of wireless network is limited by the aggregated transmission data rate of these access points. To fully exploit the capability of wireless network, we envision that future wireless networks shall be able to provide data content within themselves. In this paper, we address the behavior of such networks from a theoretical perspective. Specifically, we consider that multicast is used for distributed content delivery, and we investigate the asymptotic upper bound of the throughput capacity for distributed content delivery in large-scale wireless ad hoc networks (DCD-WANET). Our analysis shows how the upper bound of throughput capacity is affected by the geometric size of the network, the number of data items, the popularity of the data content, and the number of storage nodes that contain those data items. In particular, our theoretical results show that, if the number of storage nodes exceed a critical threshold, the upper bound grows with the number of storage nodes, according to a power-law where the scaling exponent depends on the popularity of data items. We also provide the data item placement strategy to achieve the upper bound of throughput capacity for DCD-WANET.

Protecting networking infrastructures from malicious attacks is important as a successful attack on a high data rate link can cause the loss or delay of large amounts of data. In this paper, we consider a proactive approach where the ISPs are willing to allocate some (limited) resources to defend the networking infrastructures against the attacks. We aim to answer where and how much the defending resource should be placed so that the expected data loss can be minimized no matter where the attacker may launch the attack. We model the problem as a 2-player zero-sum game where the payoffs are measured by the maximum network flow. In order to overcome the unique challenges of such payoffs, we transform the payoffs into explicit piece-wise functions through multi-parametric linear programming (MP-LP) and divide the entire strategy space into a set of critical regions. We prove that a global Nash Equilibrium (NE) exists when there is only one critical region. However, when the number of critical regions is greater than 1, there is no global NE. We also prove that there exists one and only one local NE in each critical region. We then design a mixed-strategy solution. Our results have shown that to dedicate all defending resources to one min-cut set when there are multiple min-cut sets will not be an optimal solution, however, min-cut strategies will have higher probabilities to be selected in the mixed-strategy solution when the defending resource is limited.

Wireless sensor networks (WSNs) have been increasingly available for critical applications such as security surveillance and environmental monitoring. An important performance measure of such applications is sensing coverage that characterizes how well a sensing field is monitored by a network. Although advanced collaborative signal processing algorithms have been adopted by many existing WSNs, most previous analytical studies on sensing coverage are conducted based on overly simplistic sensing models (e.g., the disc model) that do not capture the stochastic nature of sensing. In this paper, we attempt to bridge this gap by exploring the fundamental limits of coverage based on stochastic data fusion models that fuse noisy measurements of multiple sensors. We derive the scaling laws between coverage, network density, and signal-to-noise ratio (SNR). We show that data fusion can significantly improve sensing coverage by exploiting the collaboration among sensors when several physical properties of the target signal are known. In particular, for signal path loss exponent of (typically between 2.0 and 5.0), ρf= O(ρd1-1/k, where ρfand ρdare the densities of uniformly deployed sensors that achieve full coverage under the fusion and disc models, respectively. Moreover, data fusion can also reduce network density for regularly deployed networks and mobile networks where mobile sensors can relocate to fill coverage holes. Our results help understand the limitations of the previous analytical results based on the disc model and provide key insights into the design of WSNs that adopt data fusion algorithms. Our analyses are verified through extensive simulations based on both synthetic data sets and data traces collected in a real deployment for vehicle detection.

In this paper, we investigate the throughput capacity of large-scale wireless networks, in which three network-assisted coding schemes are considered: (1) multi-point-to-point coding (MPPC); (2) MPPC based network coding (NC); and (3) MPPC based physical-layer network coding (PLNC). This study is based on the generalized physical model, in which the transmission rate depends on the signal to noise and interference ratio (SINR). Such a model has not been used to analyze the behaviors of large-scale wireless networks with the aforementioned coding schemes. To understand the capacity gains of these schemes, we develop constructive lower bounds for one-dimensional (1D) and two-dimensional (2D) networks with size factor w, in which we construct novel wireless highway systems. This study shows that, compared to point-to-point coding (PPC), MPPC can improve the scaling law of network capacity when w exceeds a certain scale. In addition, this study reveals that MPPC based NC and PLNC can improve the capacity by constant factors. Specifically, NC can always obtain a gain of 2 in both 1D and 2D networks. On the other hand, the gain of PLNC can be larger than 2 in 1D networks, and can be up to 2 in 2D networks, depending on w, transmission power, noise, and path-loss of propagation.

Wireless Sensor Networks (WSNs) are increasingly available for mission-critical applications such as emergency management and health care. To meet the stringent requirements on communication performance, it is crucial to understand the complex wireless interference among sensor nodes. Recent empirical studies suggest that the packet-level interference model, also referred to as the packet reception ratio (PRR) versus SINR model or PRR-SINR model, offers significantly improved realism than other simplistic models such as the disc model. However, as shown in our experimental results, the PRR-SINR model yields considerable spatial and temporal variations in reality, which poses a major challenge for accurate measurement at run time. This paper presents a novel accuracy-aware approach to interference modeling and measurement for WSNs. First, we propose a new regression-based PRR-SINR model and analytically characterize its accuracy based on statistics theory. Second, we develop a novel protocol called accuracy-aware interference measurement (AIM) for measuring the proposed PRR-SINR model with assured accuracy at run time. AIM also adopts new clock calibration and in-network aggregation techniques to reduce the overhead of interference measurement. Our extensive experiments on a 17-node testbed of TelosB motes show that AIM achieves high accuracy of PRR-SINR modeling with significantly lower overhead than state of the art approaches.

A major disruption may affect many network components and significantly lower the capacity of a network measured in terms of the maximum total flow among a set of source-destination pairs. Since only a subset of the failed components may be repaired at a time due to e.g., limited availability of repair resources, the network capacity can only be progressively increased over time by following a recovery process that involves multiple recovery stages. Different recovery processes will restore the failed components in different orders, and accordingly, result in different amount of network capacity increase after each stage. This paper aims to investigate how to optimally recover the network capacity progressively, or in other words, to determine the optimal recovery process, subject to limited available repair resources. We formulate the optimization problem, analyze its computational complexity, devise solution schemes, and conduct numerical experiments to evaluate the algorithms. The concept of progressive network recovery proposed in this paper represents a paradigm-shift in the field of resilient and survivable networking to handle large-scale failures, and will motivate a rich body of research in network design and other applications.

In this paper, we study the optimal design of linear network coding (LNC) for secure unicast against passive attacks, under the requirement of information theoretical security (ITS). The objectives of our optimal LNC design include (1) satisfying the ITS requirement, (2) maximizing the transmission rate of a unicast stream, and (3) minimizing the number of additional random symbols. We first formulate the problem that maximizes the secure transmission rate under the requirement of ITS, which is then transformed to a constrained maximum network flow problem.We devise an efficient algorithm that can find the optimal transmission topology. Based on the transmission topology, we then design a deterministic LNC which satisfies the aforementioned objectives and provide a constructive upper bound of the size of the finite field. In addition, we also study the potential of random LNC and derive the low bound of the probability that a random LNC is information theoretically secure.

Flow untraceability is one critical requirement for anonymous communication with network coding, which prevents malicious attackers with wiretapping and traffic analysis abilities from relating the senders to the receivers, using linear dependency of the received packets. There have recently been proposals advocating encryptions on the Global Encoding Vectors (GEV) of network coding to thwart such attacks [1], [2]. Nevertheless, there has been no exploration of the capability of networking coding itself, to constitute more efficient and effective algorithms which guarantee anonymity. In this paper, we design a novel, simple, and effective linear network coding mechanism (ALNCode) to achieve flow untraceability in a communication network with multiple unicast flows. With solid theoretical analysis, we first show that linear network coding (LNC) can be applied to thwart traffic analysis attacks without the need of encrypting GEVs. Our key idea is to mix multiple flows at their intersection nodes by generating downstream GEVs from the common basis of upstream GEVs belonging to multiple flows, in order to hide the correlation of upstream and downstream GEVs in each flow. We then design a deterministic LNC scheme to implement our idea, by which the downstream GEVs produced are guaranteed to obfuscate their correlation with the corresponding upstream GEVs. We also give extensive theoretical analysis on the intersection probability of GEV bases and the influential factors to the effectiveness of our scheme, as well as the algorithm complexity to support its efficiency.

Recent years have witnessed the wide adoption of the RFID technology in many important application domains including logistics, inventory, retailing, public transportation, and security. Though RFID tags (transponders) can be passive, the high power consumption of RFID readers (interrogators) has become a critical issue as handheld and mobile readers are increasingly available in pervasive computing environments. Moreover, high transmission power aggravates interference, complicating the deployment and operation of RFID systems. In this paper, we present an energy-efficient RFID inventory algorithm called Automatic Power Stepping (APS). The design of APS is based on extensive empirical study on passive tags, and takes into consideration several important details such as tag response states and variable slot lengths. APS dynamically estimates the number of tags to be read, incrementally adjusts the transmission power level to use sufficient but not excessive power for communication, and consequently reduces both the energy consumption for reading a set of tags and the possibility of collisions. We design APS to be compatible with the current Class-1 Generation-2 RFID standards so that a reader running APS can interact with existing commercial tags without modification. We have implemented APS both on an NI RFID testing platform and in a high-fidelity simulator. The evaluation shows that APS can save more than 60% energy used by RFID readers while maintaining comparable performance on the read rate.

Real-time detection is an important requirement of many mission-critical wireless sensor network applications such as battlefield monitoring and security surveillance. Due to the high network deployment cost, it is crucial to understand and predict the real-time detection capability of a sensor network. However, most existing real-time analyses are based on overly simplistic sensing models (e.g., the disc model) that do not capture the stochastic nature of detection. In practice, data fusion has been adopted in a number of sensor systems to deal with sensing uncertainty and enable efficient collaboration among resource-limited sensors. However, real-time performance analysis of sensor networks designed based on data fusion has received little attention. In this paper, we bridge this gap by investigating the fundamental real-time detection performance of large-scale sensor networks under stochastic sensing models. In particular, we consider two basic data fusion schemes, i.e., value fusion and decision fusion. Our results show that data fusion is effective in achieving stringent performance requirements such as short detection delay and low false alarm rates. Moreover, value fusion and decision fusion are suitable for low and high signal-to-noise ratio scenarios, respectively. Our results help understand the impact of data fusion and provide important guidelines for the design of real-time wireless sensor networks for intrusion detection. Our analyses are verified through extensive simulations based on both synthetic data sets and data traces collected in a real deployment for vehicle detection. The results show that data fusion can reduce the network density by about 60 percent compared with the disc model while detecting any intruder within one detection period at a false alarm rate lower than five percent.

Service-Oriented Architecture (SOA) is emerging as the next inevitable technology for application developments. One fundamental issue of SOA is service composition, i.e., to seamlessly compose distributed services into more complex applications. In the mobile environment, a service composition may face disruptions caused by the movement of both users and service providers. Thus, a dependable service composition is desired to handle the mobility in the environment. In this paper, we propose to achieve dependable service composition by taking the mobility prediction of the service providers into consideration. We exploit the fact that the service providers can predict their stay time in the current environment. However, some uncertainty may exist in the prediction such that a service provider may move out of the current environment earlier than the prediction. We use two models to characterize the uncertainty, a probability-free model and a probabilistic model. Our objective is to design dependable service composition under these two models such that the service composition solution can have the maximum tolerance to the uncertainty of the mobility prediction. We focus on the case of sequential service composition, prove the NP-hardness of the problem, then present heuristic algorithms, derive the upper and lower bounds of the problem. Simulation results have showcased the effectiveness of the heuristic algorithms.

According to data broadcast, we can satisfy multiple requests for the same data item in a broadcast tick. However, there is no significant breakthrough in performance improvement until recently that some studies proposed to use network coding in data broadcast. After broadcasting an encoded packet which encodes a number of data items, multiple clients can retrieve different requested data items in a broadcast tick. This not only utilizes bandwidth more efficiently, but also improves system performance. In this work, we propose a generalized encoding framework to incorporate network coding into data scheduling algorithms for on-demand broadcast. In the framework, data scheduling can be formulated as a weighted maximum clique problem in a graph where the weight of the clique is defined according to the performance objectives of the applications. Under the proposed framework, existing data scheduling algorithms for on-demand broadcast can be migrated into their corresponding coding versions while preserving their original criteria in scheduling data items. Our simulation results using a number of representative scheduling algorithms show that significant performance improvement can be achieved with coding.

We recently proposed an innovative agile crossbar switch architecture called contention-tolerant crossbar (CTC(N)) and its generalization multi-layer CTC(N) (MCTC(N)) switch. In this paper, we propose several generalizations of CTC(N), including SCTC(N, n) (sparse CTC), SMCTC(N, n) (sparse multi-layer CTC) and MSCTC(N, n) (multi-layer sparse CTC). Through analysis and simulations, we show that these generalizations maintain the same performance of their counterparts CTC(N) and MCTC(N), while reducing the cost from O(N2) to O(N log N).

We recently proposed an innovative agile crossbar switch architecture called contention-tolerant crossbar (CTC(N)) switch, which can tolerate output contentions by a pipelining mechanism, with pipeline stages implemented as buffers in the input ports. These buffers are used to decouple the scheduling task into N independent parts in such a way that N schedulers are located in the N input ports, and they operate independently and in parallel without using any arbiter. In this paper, we present a simple fully distributed scheduling algorithm scheme and show its effectiveness by simulations.

Recently, the hybrid Fiber-Wireless (FiWi) access network integrating passive optical networks (PONs) and wireless mesh networks (WMNs) has been proposed to provide the high bandwidth, low cost and ubiquitous Internet access. Typically, for the PON subnetwork of FiWi networks, a hybrid TDM/WDM architecture has been applied due to its cost efficiency and the high bandwidth provided by multiple wavelengths carried in the optical trunk. In such hybrid TDM/WDM FiWi networks, we aim to maximize the overall network throughput and meanwhile to find an appropriate wavelength assignment scheme of ONUs to achieve the approximate maximal throughput with the minimum number of wavelengths to be used. In this paper, we first obtain the maximal achievable throughput at ONUs and then get the minimal number of wavelength to be used. Given the number of wavelengths, we first use LP-based formulations to estimate the expected traffic load range at each ONU and then proposed the Approximate Wavelength Assignment(AWA) algorithm to calculate the appropriate traffic load at each ONU and obtain the proper wavelength assignment scheme of ONUs. We also verify the efficiency of the wavelength assignment scheme obtained through AWA algorithm. Simulation results strongly validate our algorithm.

We propose an innovative agile crossbar switch architecture called contention-tolerant crossbar, denoted by CTC(N). Unlike the conventional crossbar and the crossbar with crosspoint buffers, which require complex hardware resolvers to grant one out of multiple output requests, CTC(N) can tolerate output contentions by a pipelining mechanism, with pipeline stages implemented as buffers in input ports. These buffers are used to decouple the scheduling task into N independent parts in such a way that $N$ schedulers are located in N input ports, and they operate independently and in parallel. Without using arbiters and/or crosspoint buffers that require additional chip area, the CTC(N) switch is more scalable than existing crossbars. We analyze the throughput of CTC(N) switch without and with internal speedup by building a queuing model. We show that, under Bernoulli i.i.d. uniform traffic, CTC(N) without internal speedup has worst-case throughput of 63%, and CTC(N) achieves 100% throughput with internal speedup 2. Our simulation results validate our theoretical analysis.

In recent years network coding has attracted significant attention in telecommunication. The benefits of network coding to a communication network include the increased throughput as well as secure data transmission. The purpose of this work is to design secure linear network coding against wiretap attack. The problem is to maximize the transmission data rate of multiple unicast streams between a pair of source and destination nodes, under the condition of satisfying the weakly secure requirements. Different from most existing research on network coding that designs the network coding scheme based on a given network topology, we will consider the integrated network topology design and network coding design. Such an integrated approach has not been reported by other researchers. In this paper, we formally introduce the problem, prove the problem is computational intractable, and then develop efficient heuristic algorithms. We first try to find the transmission topology that is suitable for network coding. Based on the topology, we design linear network coding scheme that is weakly secure. We conduct simulations to show that the proposed algorithms can achieve good performance.

Interference modeling is crucial for the performance of numerous WSN protocols such as congestion control, link/channel scheduling, and reliable routing. In particular, understanding and mitigating interference becomes increasingly important for Wireless Sensor Networks (WSNs) as they are being deployed for many data-intensive applications such as structural health monitoring. However, previous works have widely adopted simplistic interference models that fail to capture the wireless realities such as probabilistic packet reception performance. Recent studies suggested that the physical interference model (i.e., PRR-SINR model) is significantly more accurate than existing interference models. However, existing approaches to physical interference modeling exclusively rely on the use of active measurement packets, which imposes prohibitively high overhead to bandwidth-limited WSNs. In this paper, we propose the passive interference measurement (PIM) approach to tackle the complexity of accurate physical interference characterization. PIM exploits the spatiotemporal diversity of data traffic for radio performance profiling and only needs to gather a small amount of statistics about the network. We evaluate the efficiency of PIM through extensive experiments on both a 13-node and a 40-node testbeds of TelosB motes. Our results show that PIM can achieve high accuracy of PRR-SINR modeling with significantly lower overhead compared with the active measurement approach.

Minimizing the worst-case playback delay (WPD) in VoD services is both critical and challenging. Given a fixed amount of bandwidth for broadcasting and patching, there is no prior work on determining the minimum WPD, let alone guaranteeing it. In this work, we propose novel schemes that leverage the unique properties of a TDM-based Passive Optical Network (PON) by performing rebroadcasting and patching at its Optical Network Unit (ONUs). For a given bandwidth available for VoD services in the PON, we derive the minimum worst-case playback delay (WPD), and also design optimal patch scheduling algorithm as well as ONU rebroadcast and patching channel assignment to guarantee such minimum WPD. Numerical results confirm the superiority of the proposed schemes over the existing ones in terms of both worst-case and average performance.

In an integrated fiber and wireless access (FiWi) network, multi-path forwarding may be applied in the wireless subnetwork to improve throughput. Due to the delay difference along multiple paths, reordered packets of a flow may arrive at the Optical Line Terminal (OLT) waiting for dispatching to the Internet, which may deteriorate the TCP performance. As all traffic in a FiWi network is sent out through the OLT, the OLT serves as a convergence node which naturally makes it possible to resequence packets at the OLT before they are sent to the Internet. The fundamental difference between resequencing at the end systems and resequencing at an intermediate node (e.g., the OLT) is that very tight resequencing delay can be tolerated in the latter. Thus, resequencing at the intermediate nodes must be fast enough. In this paper, we propose an integrated flow assignment and resequencing approach which jointly determines the probability of sending packets along each path from the source and needs virtually zero resequencing delay at the OLT to reduce the out-of-order probability when packets are injected to the Internet from the access network. Simulation results validate our analysis and the effectiveness of the proposed integrated flow assignment and resequencing approach.

Linear network coding is a promising technology that can maximize the throughput capacity of communication network. Despite this salient feature, there are still many challenges to be addressed, and security is clearly one of the most important challenges. In this paper, we will address the design of secure linear network coding. Specifically, we will investigate the network coding design that can both satisfy the weakly secure requirements and maximize the transmission data rate of multiple unicast streams between the same source and destination pair, which has not been addressed in the literature. In our study, we first prove that the secure unicast routing problem is equivalent to a constrained link-disjoint path problem. We then develop efficient algorithm that can find the optimal unicast topology in a polynomial amount of time. Based on the topology, we design deterministic linear network code that is weakly secure and can be constructed at the source node. And finally, we investigate the potential of random linear code for weakly secure unicast and prove the low bound of the probability that a random linear code is weakly secure.

In the past few years, the capacity of multicast traffic in large-scale random wireless networks has attracted considerable attention because of the fundamental importance of network capacity and the multicast applications. However, there are still significant gaps between the upper bounds and the constructive lower bounds. In this paper, we develop a novel percolation highway system with which the constructive lower bounds can arbitrarily approach the upper bounds.

Recent years have witnessed the wide adoption of the RFID technology in many important application domains including logistics, inventory, retailing, public transportation, and security. Though RFID tags (transponders) can be passive, the high power consumption of RFID readers (interrogators) has become a critical issue as handheld and mobile readers are increasingly available in pervasive computing environments. Moreover, high transmission power aggravates interference, complicating the deployment and operation of RFID systems. In this paper, we present an energy-efficient RFID inventory algorithm called Automatic Power Stepping (APS). The design of APS is based on extensive empirical study on passive tags, and takes into consideration several important details such as tag response states and variable slot lengths. APS dynamically estimates the number of tags to be read, incrementally adjusts power level to use sufficient but not excessive power for communication, and consequently reduces both the energy consumption for reading a set of tags and the possibility of collisions. We design APS to be compatible with the current Class-1 Generation-2 RFID standards and hence a reader running APS can interact with existing commercial tags without modification. We have implemented APS both on the NI RFID testing platform and in a high-fidelity simulator. The evaluation shows that APS can save more than 60% energy used by RFID readers.

Video on demand (VoD) is one of the most important services for many network operators that deploy and operate optical access networks. It is crucial to design next generation optical access networks that can guarantee a high quality VoD service. In this paper, we address this challenging issue and focus on the worst-case playback delay (WPD), which cannot be guaranteed by Internet-based video streaming, and has not been well addressed previously in optical access networks. Specifically, we first propose an integrated Gigabit Passive Optical Network (GPON) and Wavelength Division Multiplexing PON (WDM PON) architecture. With the proposed architecture, an optical line terminal (OLT) can broadcast popular videos through GPON and deliver other videos through WDM-PON, while the optical network units (ONUs) can conduct patching for their end users. We then elaborate on two minimum-WPD schemes. In the first one, we assume that the video broadcast schedule is fixed at the OLT and develop an optimal patching scheme at each ONU such that the WPD is minimized. In the second one, we consider coordinated OLT broadcast scheduling and ONU patching. A heuristic algorithm which can achieve near-optimal WPD is proposed for coordinated OLT broadcast scheduling and ONU patching. Simulation results confirm the superiority of the proposed schemes over the existing ones in terms of both worstcase and average delay performance.

Recent years have witnessed the deployments of wireless sensor networks in a class of mission-critical applications such as object detection and tracking. These applications often impose stringent Quality-of-Service requirements including high detection probability, low false alarm rate, and bounded detection delay. Although a dense all-static network may initially meet these Quality-of-Service requirements, it does not adapt to unpredictable dynamics in network conditions (e.g., coverage holes caused by death of nodes) or physical environments (e.g., changed spatial distribution of events). This paper exploits reactive mobility to improve the target detection performance of wireless sensor networks. In our approach, mobile sensors collaborate with static sensors and move reactively to achieve the required detection performance. Specifically, mobile sensors initially remain stationary and are directed to move toward a possible target only when a detection consensus is reached by a group of sensors. The accuracy of final detection result is then improved as the measurements of mobile sensors have higher Signal-to-Noise Ratios after the movement. We develop a sensor movement scheduling algorithm that achieves near-optimal system detection performance under a given detection delay bound. The effectiveness of our approach is validated by extensive simulations using the real data traces collected by 23 sensor nodes.

Service-oriented wireless sensor networks have recently been proposed to provide an integrated platform, where new applications can be rapidly developed through flexible service composition. In wireless sensor networks, sensors are periodically switched into the sleep mode for energy saving. This, however, will cause the unavailability of nodes, which, in turn, incurs disruptions to the service compositions requested by the applications. Thus, it is desirable to maintain enough active sensors in the system to provide each required service at any time in order to achieve dependable service compositions for various applications. In this paper, we study the cross-layer sleep scheduling design, which aims to prolong the network lifetime while satisfying the service availability requirement at the application layer. We formally define the problem, prove that the problem is NP-hard, and develop two approximation algorithms based on the LP relaxation and one efficient reordering heuristic algorithm. The proposed work will enhance the dependability of the service composition in service-oriented wireless sensor networks.

This paper focuses on multihop range-free localization in anisotropic wireless sensor networks. In anisotropic networks, geometric distance between a pair of sensor nodes is not always proportional to their hop count distance, which undermines the assumption of many existing range-free localization algorithms. To tolerate network anisotropy, we propose a pattern-driven localization scheme, which is inspired by the observation that in an anisotropic network the hop count field propagated from an anchor exhibits multiple patterns, under the interference of multiple anisotropic factors. Our localization scheme therefore for different patterns adopts different anchor-sensor distance estimation algorithms. The average anchor-sensor distance estimation accuracy of our scheme, as demonstrated by both theoretical analysis and extensive simulations, is improved to be better than 0.4r when the average sensor density is above eight, and the sensor localization accuracy thus is approximately better than 0.5r. This localization accuracy can satisfy the needs of many location-dependent protocols and applications, including geographical routing and tracking. Compared with previous localization algorithms that declares to tolerate network anisotropy, our localization scheme excels in 1) higher accuracy stemming from its ability to tolerate multiple anisotropic factors, including the existence of obstacles, sparse and nonuniform sensor distribution, irregular radio propagation pattern, and anisotropic terrain condition, 2) localization accuracy guaranteed by theoretical analysis, rather than merely by simulations, and 3) a distributed solution with less communication overhead and enhanced robustness to different network topologies.

Many wireless sensor networks require sufficient sensing coverage over long periods of time. To conserve energy, a coverage maintenance protocol achieves desired coverage by activating only a subset of nodes, while allowing the others to sleep. Existing coverage maintenance protocols are often designed based on simplistic sensing models that do not capture the stochastic nature of distributed sensing. We propose a new sensing coverage model based on the distributed detection theory, which captures two important characteristics of sensor networks, i.e., probabilistic detection by individual sensors and data fusion among sensors. We then present three coverage maintenance protocols that can meet the specified event detection probability and false alarm rate. The centralized protocol only activates a small number of sensors, but introduces extremely long coverage configuration delay. The Se-Grid protocol reduces the configuration time by dividing the network into separate fusion groups, but increases the number of active sensors due to the lack of collaboration among sensors in different groups. In contrast, by coordinating overlapping fusion groups, the Co-Grid protocol can effectively reduce the number of active sensors and the coverage configuration time. The advantages of Co-Grid have been validated through simulations and benchmark results on Mica2 motes.

In communication networks, multiple disjoint communication paths are desirable for many applications. Such paths, however, may not exist in a network. In such a situation, paths with minimum link and/or node sharing may be considered. This paper addresses the following two related fundamental questions. First, in case of no solution of disjoint multiple paths for a given application instance, what are the criteria for finding the best solution in which paths share nodes and/or links? Second, if we know the criteria, how do we find the best solution? We propose a general framework for the answers to these two questions. This framework can be configured in a way that is suitable for a given application instance. We introduce the notion of link shareability and node shareability and consider the problem of finding minimum-cost multiple paths subject to minimum shareabilities (MCMPMS problem). We identify 65 different link/node shareability constraints, each leading to a specific version of the MCMPMS problem. In a previously published technical report, we prove that all the 65 versions are mutually inequivalent. In this paper, we show that all these versions can be solved using a unified algorithmic approach that consists of two algorithm schemes, each of which can be used to generate polynomial-time algorithms for a set of versions of MCMPMS. We also discuss some extensions where our modeling framework and algorithm schemes are applicable.

Wireless sensor networks (WSNs) deployed for mission-critical applications face the fundamental challenge of meeting stringent spatiotemporal performance requirements using nodes with limited sensing capacity. Although advance network planning and dense node deployment may initially achieve the required performance, they often fail to adapt to the unpredictability and variability of physical reality. This paper explores efficient use of mobile sensors to address limitations of static WSNs for target detection. We propose a data-fusion-based detection model that enables static and mobile sensors to effectively collaborate in target detection. An optimal sensor movement scheduling algorithm is developed to minimize the total moving distance of sensors while achieving a set of spatiotemporal performance requirements including high detection probability, low system false alarm rate, and bounded detection delay. The effectiveness of our approach is validated by extensive simulations based on real data traces collected by 23 sensor nodes.

Service-oriented wireless sensor network (WSN) has been recently proposed as an architecture to rapidly develop applications in WSNs. In WSNs, a query task may require a set of services and may be carried out repetitively with a given frequency during its lifetime. A service composition solution shall be provided for each execution of such a persistent query task. Due to the energy saving strategy, some sensors may be scheduled to be in sleep mode periodically. Thus, a service composition solution may not always be valid during the lifetime of a persistent query. When a query task needs to be conducted over a new service composition solution, a routing update procedure is involved which consumes energy. In this paper, we study service composition design which minimizes the number of service composition solutions during the lifetime of a persistent query. We also aim to minimize the total service composition cost when the minimum number of required service composition solutions is derived. A greedy algorithm and a dynamic programming algorithm are proposed to complete these two objectives respectively. The optimality of both algorithms provides the service composition solutions for a persistent query with minimum energy consumption.

Nowadays, Fiber-Wireless (FiWi) network is proposed as a hybrid access network that integrates optical access networks (e.g., PONs) with wireless access networks (e.g., WMNs) to provide the high bandwidth, cost-efficient and ubiquitous last mile Internet access. In FiWi networks, besides traffic from wireless mesh clients to the Internet, peer-to-peer communication from one wireless client to another wireless client is introduced due to the recent growth of applications such as multimedia transmissions within community areas. In FiWi networks, such peer-to-peer traffic can be carried either through the wireless path within the wireless mesh subnetwork or through the wireless-optical-wireless mode in which traffic firstly goes from the source client to its closest ONU, and then goes to the ONU closest to the destination client through the PON subnetwork and finally reaches the destination client. Such wireless-opticalwireless mode for peer-to-peer communications can alleviate interferences in the wireless subnetwork, thus improving the network throughput. Considering such mode for peer-to-peer communications, ONUs' placement will have great impact on the achievable network throughput in FiWi networks and will be different from the placement when only traffic to the Internet is considered. In this paper, given the distribution of wireless mesh routers, we study where to place K ONUs in FiWi networks so that the overall network throughput can be maximized when peer-to-peer communications are considered in addition to traffic destinated to the Internet. We first formulate the problem and then propose a tabu search (TS) based heuristic to solve the problem. Simulation results show that compared to the random deployment and the fixed deployment which performs well when only traffic to the Internet is considered, the tabu search heuristic has a much better performance.

A light-trail is a generalization of a lightpath such that multiple nodes can take part in communication along the path. A light-trail exhibits properties of dynamic provisioning, optical multicasting and sub-wavelength grooming and architecturally is analogous to a shared wavelength optical bus with an Out-Of-Band (OOB) control channel. The bus feature results in a node that has a large pass-through loss, and hence restricts the size of a light-trail to metro environments. Within a bus the OOB control channel allows for dynamic real-time arbitration. Due to this limitation, it is difficult to extend the light-trail concept to regional and core networks. In this paper we propose a method to provide multihop communication in light-trails thereby relaxing the limitation in hop count, as well as enhancing reach of communications. We propose node architecture and protocol requirements for creating Multi-hop Light-trails (MLTs). We then discuss design issues for MLTs in regional area networks through problem formulation. A simulations study validates MLTs.

Optical-Wireless (FiWi) access network is a newly emerged access network architecture which integrates passive optical networks (PONs) with wireless mesh networks (WMNs) to provide the ubiquitous, low cost, high bandwidth last mile Internet access. Though the PON subnetwork of FiWi network can provide high bandwidth, the interference in the wireless subnetwork still limits the throughput of FiWi network if all traffic goes online to the Internet. However, when peer-to-peer communication from one wireless client to another wireless client is introduced, the proposed integration of PONs and WMNs can significantly improve the network throughput. In traditional WMNs, peer-to-peer communication from one wireless client to another wireless client is carried in the wireless network, which is subject to interferences in wireless communications. In FiWi network, peer-to-peer communication can be carried through the wireless-optical-wireless mode in which the traffic is sent from the source wireless client to its nearest ONU, which is then sent to the ONU close to the destination wireless client through the PON subnetwork and then delivered to the destination wireless client. Such wireless-optical-wireless communication mode introduced by FiWi networks can sustain the interference in wireless subnetwork, thus improving the network throughput. This paper aims to study the network throughput gain in FiWi network subject to peer-to-peer communications and parameters which can affect the network throughput gain. We first have a fair modeling of FiWi networks and traditional WMNs. We then present an LP based routing algorithm for FiWi networks. Extensive simulations have been carried to study the network throughput gain in FiWi networks subject to peer-to-peer communications compared with traditional WMNs. The work provides insightful observations for fully utilizing advantages brought by the integration of PONs and WMNs in FiWi networks.

Recently, mobility-assisted data collection has been proposed to prolong network lifetime. However, the upper bound of throughput capacity in such mobility-assisted data collection models has not been studied. In this work, we first derive the upper bound of throughput capacity when a mobile sink is available for data collection. Given the traveling speed of the mobile sink and the required delay deadline, we analyze the necessary conditions (e.g., optimal number of clusters, minimum buffer size at each cache, and minimum traveling distance) to achieve the maximum throughput capacity. Our analysis shows that 3W/4n per-node throughput capacity can be achieved at a low traveling speed, which is 3 times of the throughput capacity in a static WSN. We further extend the analysis to the case where multiple mobile devices can assist in data collection. We show that 4 mobile relays are enough to achieve the upper bound of throughput capacity O(W/n). Finally, we derive the throughput capacity under existing mobility-assisted data collection models.

Wireless Mesh Network (WMN) is an emerging communication paradigm to enable resilient, cost-efficient and reliable services for the future-generation wireless networks. In this paper, we study the problem of multipoint-to-multipoint (M2M) multicasting in a WMN which aims to use the minimum number of time slots to exchange messages among a group of k mesh nodes in a multi-hop WMN with n mesh nodes. We study the M2M multicasting problem in a distributed environment where each participant only knows that there are k participants and it does not know who are other k -1 participants among n mesh nodes. It is known that the computation of an optimal M2M multicasting schedule is NP-hard. We present a fully distributed deterministic algorithm for such an M2M multicasting problem and analyze its time complexity. We show that if the maximum hop distance between any two out of the k participants is d, then the studied M2M multicasting problem can be solved in time O(d log2n+k log3n/log k) with a polynomial-time computation, which is an almost optimal scheme due to the lower bound Omega(d+ k log n/log k) given in [5]. Our algorithm also improves the currently best known result with running time O(d log2n + k log4n) in [13]. In this paper, we also propose a distributed deterministic algorithm which accomplishes the M2M multicasting in time O(d+k) with a polynomial-time computation in unit disk graphs. This is an asymptotically optimal algorithm in the sense that there exists a WMN topology, e.g., a line, a ring, a star or a complete graph, in which the M2M multicasting cannot be completed in less than Omega(d+k) units of time.

Reliable multicast in wireless networks has been well studied in the sense to solve the feedback implosion issue, which, however, can not reduce the number of retransmissions in order to recover all lost packets at receivers. Most recently, it has been proposed to use network coding for reliable multicast in wireless LANs to reduce the number of retransmissions. In this paper, we propose two new models to further reduce the number of retransmissions for reliable multicast. In the first model, each retransmission encoding decision is made according to the latest ldquowantedrdquo packet set at all receivers. Thus, the maximum number of receivers can potentially decode out one ldquowantedrdquo packet from each encoded retransmission packet. Such a model is referred to as dynamic multicast retransmission encoding (DMRE) model. This model is a memoryless model where a receiver will not buffer encoded retransmission packets for later use. In the second model, a receiver will buffer all received encoded retransmission packets and decode out their ldquowantedrdquo packets at the end of the retransmission batch. Such a model is referred to as cache-based multicast retransmission encoding(CMRE) model. The problem to minimize the number of retransmissions under both DMRE and CMRE models are NP-hard. Effective heuristic algorithms are proposed in this paper. We analyze the impact of packet delivery ratio on the gain of network coding. We derive the lower bound of the expected number of retransmissions using network coding, which provides the insights of the maximum potential gain using network coding in reliable multicast.

Wireless sensor networks (WSNs) have been increasingly available for critical applications such as security surveil-lance and environmental monitoring. An important per-formance measure of such applications is sensing coverage that characterizes how well a sensing field is monitored by a network. Although advanced collaborative signal process-ing algorithms have been adopted by many existing WSNs, most previous analytical studies on sensing coverage are con-ducted based on overly simplistic sensing models (e.g., the disc model) that do not capture the stochastic nature of sens-ing. In this paper, we attempt to bridge this gap by explor-ing the fundamental limits of coverage based on stochastic data fusion models that fuse noisy measurements of multi-ple sensors. We derive the scaling laws between coverage, network density, and signal-to-noise ratio (SNR). We show that data fusion can significantly improve sensing coverage by exploiting the collaboration among sensors. In particu-lar, for signal path loss exponent of k (typically between 2.0 and 5.0), ρf = O(ρ1−1/kd), where ρf and ρd are the densi-ties of uniformly deployed sensors that achieve full coverage under the fusion and disc models, respectively. Our results help understand the limitations of the previous analytical re-sults based on the disc model and provide key insights into the design of WSNs that adopt data fusion algorithms. Our analyses are verified through extensive simulations based on both synthetic data sets and data traces collected in a real deployment for vehicle detection.

Real-time detection is an important requirement of many mission-critical wireless sensor network applications such as battlefield monitoring and security surveillance. Due to the high network deployment cost, it is crucial to understand and predict the real-time detection capability of a sensor network. However, most existing real-time analyses are based on overly simplistic sensing models (e.g., the disc model) that do not capture the stochastic nature of detection. In practice, data fusion has been adopted in a number of sensor systems to deal with sensing uncertainty and enable the collaboration among sensors. However, real-time performance analysis of sensor networks designed based on data fusion has received little attention. In this paper, we bridge this gap by investigating the fundamental real-time detection performance of large-scale sensor networks under stochastic sensing models. Our results show that data fusion is effective in achieving stringent performance requirements such as short detection delay and low false alarm rates, especially in the scenarios with low signal-to-noise ratios (SNRs). Data fusion can reduce the network density by about 60% compared with the disc model while detecting any intruder within one detection period at a false alarm rate lower than 2%. In contrast, the disc model is only suitable when the SNR is sufficiently high. Our results help understand the impact of data fusion and provide important guidelines for the design of real-time wireless sensor networks for intrusion detection.

Multidimensional data indexing has received much research attention recently in a centralized system. However, it remains a nascent area of research in providing an integrated structure for multiple queries on multidimensional data in a distributed environment. In this paper, we propose a new data structure, called BR-tree (Bloom-filter-based R-tree), and implement such a prototype in the context of a distributed system. The node in a BR-tree, viewed as an expansion from the traditional R-tree node structure, incorporates space-efficient Bloom filters to facilitate fast membership queries. The proposed BR-tree can simultaneously support not only existing point and range queries, but also cover and bound queries that can potentially benefit various data indexing services. Compared with previous data structures, BR-tree achieves space efficiency and provides quick response (lesO(log n)) on these four types of queries. Our extensive experiments in a distributed environment further validate the practicality and efficiency of the proposed BR-tree structure.

Light-trail is proposed as a candidate to carry IP traffic over wavelength division multiplexing (WDM) optical networks given its capability of accommodating multi-granularity traffic by time-division multiplexing (TDM). Light-trail's unidirectional shared-media multicast nature makes it hard to implement distributed access control and restricts that at most one packet transmission can take place at any time. Recently, opportunistic optical hyperchannel was proposed to improve light-trail by permitting easy distributed access control. In this paper, we propose a set of distributed access control protocols, namely, 1-persistent protocols, for opportunistic optical hyperchannels to maximize the throughput and provide fair service among contending nodes by taking their inherent advantage of adaptive space-division multiplexing (SDM). We also point out a possible generalization of opportunistic optical hyperchannels by removing the restriction of linear structure, and demonstrate possible applications of such a generalization.

Light-trail is proposed as a candidate to carry IP traffic over wavelength-division multiplexing optical networks given its capability of enabling high-speed provisioning and accommodating multigranularity traffic. In a light-trail, the optical shutters at the start node and the end node are configured to be in OFF state and the optical shutters at the intermediate nodes are configured to be in ON state. Thus, an optical bus is formed, allowing traffic multiplexing without the state change of any optical shutter. This, however, limits the system throughput and also makes it impossible to implement a fully distributed medium access control (MAC) protocol to assure quality of service (QoS) in a light-trail. With the recent development on ultrafast optical shutter, we propose an improved light-trail architecture, called opportunistic hyperchannel in this paper. In an opportunistic hyperchannel, an intermediate node can dynamically control its optical shutter which makes it possible to design a fully distributed QoS assuring MAC protocol. We then present a QoS assuring distributed dynamic scheduling protocol, namely, minimum source round robin (minSrcRR) protocol, for opportunistic hyperchannels. Theoretical analysis on the effectiveness of the proposed QoS assuring protocol and the worst-case delay bound are also derived in this paper. The simulation results quantitatively demonstrate the advantage of opportunistic hyperchannels and the effectiveness of minSrcRR protocol.

Data center networking (DCNs) is a fast emerging enterprise application that is driving metropolitan bandwidth needs. This paper evaluates the needs of this emerging IT-centric, bandwidth voluminous and service rendering application from a metro optical networking perspective. We identify a set of needs called CAVALIER (consolidation, automation, virtualization, adaptability, latency, integration, economy and reliability) that are underlying requirements for a network to support DCN services. The CAVALIER requirements are met by proposing a metro optical solution which is based on light-trail ROADM technology. Light-trails exhibit properties such as dynamic bandwidth provisioning, optical multicasting, sub-wavelength granular support and low-cost for deployment. Adapting light-trails to DCN needs is discussed in this paper through engineering requirements and network-wide design. Each aspect of the CAVALIER requirement is then mapped on to light-trail technology. Simulation results are shown to lead to performance betterments.

Opportunistic hyperchannel was proposed as an improvement of light-trail to carry IP traffic over wavelength division multiplexing (WDM) optical networks given its capability of enabling high speed provisioning and accommodating multi- granularity traffic. In an opportunistic hyperchannel, the optical shutters at the start node and the end node are configured to be in OFF state and the optical shutters at the intermediate nodes can be self-adjusted to be in ON/OFF according to actual traffic. With this ability, an opportunistic hyperchannel can be dynamically divided into multiple segments, and each segment can independently accommodate a request. Thus, an opportunistic hyperchannel can amplify the system throughput. In this paper, we present a centralized dynamic scheduling protocol named prioritized maximum independent set (PMIS), and introduce a data structure called 2-dimensional priority search tree (2D-PST) that supports PMIS. With 2D-PST, one round of PMIS can be carried out in O(k . log n . log m) time to maximize the system throughput under the constraint of assuring quality of service (QoS) for opportunistic hyperchannels. The simulation results quantitatively demonstrate the effectiveness of PMIS protocol.

Recently, light-trail is becoming an appealing architecture for WDM networks which have been considered as promising backbone of the next generation network. Light-trail can inherently support multicast given its bus nature. In this paper, we study how to use the minimum number of light- trails to form a multicast tree for supporting the given multicast session. The problem for general light-trail WDM networks is proved to be NP-hard. Two auxiliary graphs will be proposed to transform the problem into minimum steiner tree problem that many effective algorithms can be applied. We then show that the same problem in light-trail WDM ring networks can be solved in polynomial time. The simulations show the effectiveness of our work.

In a service overlay network, the services provided by different service providers might span multiple Internet domains. A service provider failure may cause significant performance deterioration. Thus, it is desirable to provide fault tolerant service composition solutions such that the service composition can be switched to the backup service composition solution in case of a service provider failure. To provide 100% protection against a single service provider failure, fault tolerant service composition essentially requires to partition service providers into two disjoint sets, each of them can provide a service composition solution. We study a generalized fault tolerant service composition which aims to find two service composition solutions for each request to minimize the number of shared service providers. Subject to such a primary objective, we also aim to minimize the total service composition cost. We firstly prove that the problem is NP-Complete, and formulate the problem as an integer linear program. We then propose heuristic algorithms to efficiently solve the problem. Simulation results demonstrate the effectiveness of the proposed heuristic algorithms.

Search engine is a critical component in several stages of a pipeline flow in high-performance IP routers. To achieve high performance, it has been proposed to use TCAMs to implement search engines in hardware. In this paper, the state- of-art TCAM-based MSMB-LPT scheme is used as an example to show how to introduce pipelining into TCAM-based search by presenting pipelined scheme P-MSMB-LPT. It is shown that P-MSMB-LPT eliminates the unnecessary hazard that exists in the MSMB-LPT scheme, and achieves near-optimal speedup with almost no additional hardware overhead.

Wireless sensor networks (WSNs) deployed for mission-critical applications face the fundamental challenge of meeting stringent spatiotemporal performance requirements using nodes with limited sensing capacity. Although advance network planning and dense node deployment may initially achieve the required performance, they often fail to adapt to the unpredictability of physical reality. This paper explores efficient use of mobile sensors to address the limitations of static WSNs in target detection. We propose a data fusion model that enables static and mobile sensors to effectively collaborate in target detection. An optimal sensor movement scheduling algorithm is developed to minimize the total moving distance of sensors while achieving a set of spatiotemporal performance requirements including high detection probability, low system false alarm rate and bounded detection delay. The effectiveness of our approach is validated by extensive simulations based on real data traces collected by 23 sensor nodes.

Recent years have witnessed the deployments of wireless sensor networks in a class of mission-critical applications such as object detection and tracking. These applications often impose stringent QoS requirements including high detection probability, low false alarm rate and bounded detection delay. Although a dense all-static network may initially meet these QoS requirements, it does not adapt to unpredictable dynamics in network conditions (e.g., coverage holes caused by death of nodes) or physical environments (e.g., changed spatial distribution of events). This paper exploits reactive mobility to improve the target detection performance of wireless sensor networks. In our approach, mobile sensors collaborate with static sensors and move reactively to achieve the required detection performance. Specifically, mobile sensors initially remain stationary and are directed to move toward a possible target only when a detection consensus is reached by a group of sensors. The accuracy of final detection result is then improved as the measurements of mobile sensors have higher signal-to-noise ratios after the movement. We develop a sensor movement scheduling algorithm that achieves near-optimal system detection performance within a given detection delay bound. The effectiveness of our approach is validated by extensive simulations using the real data traces collected by 23 sensor nodes.

Mission-critical target detection imposes stringent performance requirements for wireless sensor networks, such as high detection probabilities and low false alarm rates. Data fusion has been shown as an effective technique for improving system detection performance by enabling efficient collaboration among sensors with limited sensing capability. Due to the high cost of network deployment, it is desirable to place sensors at optimal locations to achieve maximum detection performance. However, for sensor networks employing data fusion, optimal sensor placement is a non-linear optimizationproblem with prohibitive computational complexity. In this paper, we present fast sensor placement algorithms based on a probabilistic data fusion model.Simulation results show that our algorithms can meet the desired detection performance with a small number of sensors while achieving up to 7-fold speedup over the optimal algorithm.

In a general context, the sharing of intermediate service results among different processes is seldom feasible because parameters are often different and there may be transactional and side effects. However, in a streaming video multicast environment, a large number of users often request various similar processing on the same stream. Therefore, service sharing is feasible, with a large potential of savings in processing cost. In this paper, we study the problem of determining the service invocation orders for multiple service composition requests in a streaming video multicast with the aim of maximizing the service sharing. We first formally define the problem. After proving the problem is NP-complete, we develop an optimal algorithm for the base case of two requests. Then for the general case, we develop two heuristic algorithms, namely,aglobal greedy algorithm and a local greedy algorithm using the optimal algorithm for the base case as the building block. The global greedy algorithm is designed for a system where the existing service composition requests can be recomposed with the arrival of a new request. The local greedy algorithm can be used in a system where the existing service composition requests do not change their service composition solutions with the arrival of a new request. We prove that the global greedy algorithm is a 2-approximation algorithm in terms of maximizing service sharing. Simulation results show that the greedy algorithms can save more service costs compared with a naive algorithm, and are effective compared with the cost lower bound.

In communication networks, multiple communication paths sharing minimum number of links or/and nodes may be desirable for improved performance, resource utilization and reliability. We introduce the notion of link sharability and node sharability, and consider the problems of finding minimum-cost k paths subject to minimum link/node sharability constraints. We identify 65 different link/node sharability constraints, and consider the fundamental problem of finding minimum-cost k paths between a pair of nodes under these constraints. We present a unified polynomial-time algorithm scheme for solving this problem subject to 25 of these different sharability constraints.

Sensor networks are fundamentally deployed to handle extreme behaviors across sensing sites. Service differentiation in information-aware wireless sensor network refers to the ability to provide reliable and low-latency transmissions of critical data. In this paper, we present remote-homing based solutions to support service differentiation in wireless sensor network. For each sensor (source), we designate remote homes that bypass certain layers in a multi-layered sensor network in order to reduce transmission delay, and also identify node-disjoint remote homes in order to provide high reliability. We develop algorithms that identify optimal remote homes, which minimize the total energy consumed for data transmission given a delay and a loss constraint. We evaluate the effectiveness of our dynamic programming-based optimal algorithms using simulation results.

Abstract — In this paper, we study the survivability problem in hierarchical wireless access networks with dual-homed end users, who are connected to two base stations (BSs), a primary BS and a backup BS. The dual homing mechanism is resilient to a single failure of a BS. However, if a failure occurs at the base station controller (BSC) layer or at the mobile switching center (MSC) layer, dual-homing may not prevent connection loss. We address the problem of routing from BSs to BSCs and from BSCs to MSCs, with the objective of minimizing the maximum number of connections lost due to a single failure of BS, BSC, or MSC. We first formulate the problem using Integer Linear Programming (ILP). We then prove that this optimization problem is NP-hard by showing some of its subproblems with relaxed constraints are still NP-hard. A Tabu Search (TS) based heuristic is then proposed for the problem, which provides near optimal results in most cases. I.

In this paper, we propose a scalable multicast protection scheme based on a dual-homing architecture where each destination host is connected to two edge routers. Under such an architecture, there are two paths from the source of a multicast session to each destination host, which provides a certain level of protection for the data traffic from the source to the destination host. The protection level varies from 0 percent to 100 percent against a single link failure, depending on the number of shared links between these two paths. The major advantage of the proposed scheme lies in its scalability due to the fact that the protection is provided by constructing a dual-homing architecture at the access network while keeping the routing protocols in the core network unchanged. The selection of dual edge routers plays an important role in enhancing the protection level. Two problems arise for the proposed dual-homing partial multicast protection scheme. One is to calculate the survivability from the source to any pair of edge routers. The other is to assign a pair of edge routers for each destination host such that the total survivability is maximized for the multicast session subject to the port number constraint of each edge router. We propose an optimal algorithm to solve the first problem. We prove the decision version of the second problem is NP-complete and propose two heuristic algorithms to solve it. Simulation results show that the proposed heuristic algorithms achieve performance close to the calculated lower bound

Dual homing is a fault-tolerance mechanism generally used in IP-based access networks to increase the survivability of the network. In a dual-homing architecture, a host is connected to two different access routers; therefore, it is unlikely that the host will be denied access to the network as the result of a failure in the access network, a failure of the access router, or congestion at the access router. However, dual homing cannot provide survivability with respect to possible failures in the optical core network. To provide survivability in the core network, optical protection and restoration techniques must be used. In the past, dual homing architectures and optical protection schemes have been studied independently of one another. This paper studies coordinated multi-layer survivability techniques that use both dual-homing schemes and optical protection schemes in an IP-based access network over a WDM-based optical core network. Specifically, we investigate the protection design problem in the WDM core network, given that a dual-homing infrastructure is implemented in the access network. Several solutions are proposed, and it is shown that the proposed coordinated survivability schemes can reduce cost compared to the case in which the survivability mechanisms arc not coordinated between the IP layer and the optical layer.

We propose a novel multicast protection scheme based on a dual-homing architecture where each destination host is connected to two edge routers. Under such an architecture, the two paths from the source of the multicast session to the two edge routers provide certain protection for the data traffic from the source to the destination host. Two problems are associated with the proposed dual-homing multicast protection scheme. One is to calculate the individual survivability for a destination host that is connected to two edge routers. The other is to assign two edge routers for each destination host such that the total survivability is maximized for the multicast session subject to the port number constraint of edge routers. We propose an optimal algorithm to solve the first problem and a heuristic algorithm to solve the second problem. Through simulations, we show that the proposed heuristic algorithm achieves a performance close to the calculated lower bound.

A fault-tolerant scheme, called dual homing, is generally used in IP-based access networks to increase the survivability of the network. However, dual homing itself cannot provide survivability with respect to possible failures in the wavelength division multiplexed (WDM) core network. To provide survivability in the core network, protection and restoration techniques must be used. In the past, dual homing architecture and protection are studied separately. This paper observes that the dual homing architecture introduces new issues for protection and restoration design, especially when providing survivability against two independent failures, one in the access network and the other in the core network. This paper provides an integrated solution and studies the protection design problem in the WDM core network, given a dual-homing infrastructure in the access network. Several algorithmic solutions are proposed, and performance of the solutions is compared.

One promising switching technology for wavelength-division multiplexing optical networks is optical burst switching (OBS). However, there are major deficiencies of OBS. (1) The delay offset between a control message and its corresponding data burst is based on the diameter of a network. This affects network efficiency, quality-of-service, and network scalability.( 2) OBS adopts one-way resource reservation scheme, which causes frequent burst collision and, thus, burst loss. We address the above two important issues in OBS. In particular, we study how to improve the performance of delay and loss in OBS. To reduce the end-to-end delay, we propose a hybrid switching scheme. The hybrid switching is a combination of lightpath switching and OBS switching. A virtual topology design algorithm based on simulated annealing to minimize the longest shortest path through the virtual topology is presented. To minimize burst collision and loss, we propose a new routing algorithm, namely, p-routing, for OBS network. The p-routing is based on the wavelength available probability. A path that has higher available probability is less likely to drop bursts due to collision. The probability-based p-routing can reduce the volatility, randomness, and uncertainty of one-way resource reservation. Our studies show that hybrid switching and p-routing are complementary and both can dramatically improve the performance of OBS networks.

We study the problem of wavelength assignment for multicast in order to maximize the network capacity in all-optical wavelength-division multiplexing networks. The motivation behind this work is to minimize the call blocking probability by maximizing the remaining network capacity after each wavelength assignment. While all previous studies on the same objective concentrate only on the unicast case, we study the problem for the multicast case. For a general multicast tree, we prove that the multicast wavelength assignment problem of maximizing the network capacity is NP-hard and propose two efficient greedy algorithms. We also study the same problem for a special network topology, a bidirectional ring network, which is practically the most important topology for optical networks. For bidirectional ring networks, a special multicast tree with at most two leaf nodes is constructed. Polynomial time algorithms for multicast wavelength assignment to maximize the network capacity exist under such a special multicast tree with regard to different splitting capabilities. Our work is the first effort to study the multicast wavelength assignment problem under the objective of maximizing network capacity.

The next generation multimedia applications such as video conferencing and HDTV have raised tremendous challenges on the network design, both in bandwidth and service. As wavelength-division-multiplexing (WDM) networks have emerged as a promising candidate for future networks with large bandwidth, supporting efficient multicast in WDM networks becomes eminent. Different from the IP layer, the cost of multicast at the WDM layer involves not only bandwidth (wavelength) cost, but also wavelength conversion cost and light splitting cost. It is well known that the optimal multicast problem in WDM networks is NP-hard. In this paper, we develop an efficient approximation algorithm consisting of two separate but integrated steps: multicast routing and wavelength assignment. We prove that the problem of optimal wavelength assignment on a multicast tree is not NP-hard; in fact, an optimal wavelength assignment algorithm with complexity of O(NW) is presented. Simulation results have revealed that the optimal wavelength assignment beats greedy algorithms by a large margin in networks using many wavelengths on each link such as dense wavelength-division-multiplexing (DWDM) networks. Our proposed heuristic multicast routing algorithm takes into account both the cost of using wavelength on links and the cost of wavelength conversion. The resulting multicast tree is derived from the optimal lightpaths used for unicast.

The next generation multimedia applications such as video conferencing and HDTV have raised tremendous challenges on the network design, both in bandwidth and service. As wavelength division multiplexing (WDM) networks have emerged as a promising candidate for future networks with large bandwidth, supporting efficient multicast in WDM networks becomes eminent. Different from the IP layer, the cost of multicast at the WDM layer involves not only bandwidth (wavelength) cost but also wavelength conversion cost. In this paper, we study the multicast problem in WDM networks supporting wavelength conversion. In particular, we address the problem of minimizing cost of wavelength conversion in a multicast tree with upper bound on the number of conversions from source to destinations. An efficient optimal wavelength assignment algorithm is presented.