Reinforcement learning (RL) with delays is challenging as sensory perceptions lag behind the actual events: the RL agent needs to estimate the real state of its environment based on past observations. State-of-the-art (SOTA) methods typically employ recursive, step-by-step forecasting of states. This can cause the accumulation of compounding errors. To tackle this problem, our novel belief estimation method, named Directly Forecasting Belief Transformer (DFBT), directly forecasts states from observations without incrementally estimating intermediate states step-by-step. We theoretically demonstrate that DFBT greatly reduces compounding errors of existing recursively forecasting methods, yielding stronger performance guarantees. In experiments with D4RL offline datasets, DFBT reduces compounding errors with remarkable prediction accuracy. DFBT’s capability to forecast state sequences also facilitates multi-step bootstrapping, thus greatly improving learning efficiency. On the MuJoCo benchmark, our DFBT-based method substantially outperforms SOTA baselines. Code is available at https://github.com/QingyuanWuNothing/DFBT.

We propose a framework to compute the optimal routes for multi-drones to minimize the delivery time in the last-mile delivery service. We mainly focus on a notion of the landing exclusion zone that appears during the landing phase; an area around the drop-off site is blocked until a drop-off is completed. Such zones affect the delivery time as other drones need to detour or hover around the site unnecessarily. We formulate the Mixed-Integer Linear Programming (MILP) problem by explicitly modeling the landing phase. Then, we present the heuristic algorithm that iteratively solves a sequence of single-drone delivery problems according to the delivery priorities. A delivery priority is determined according to the spatiotemporal occupancy that quantifies the significance of the size of the landing exclusion zone and its blocking period. We designed the experiment for 48 urban delivery scenarios with varying density and distribution of delivery destinations, departure points, and order quantities. Our experiment results show that the heuristic computes the routes significantly faster than the original MILP, and the delivery time is 5% higher from the optimal solution (lower-bound), and 60% lower from the general requirement of a single package per round-trip (upper-bound).

This work demonstrates a 12-bit SAR ADC using a machine-learning-based LLM-LMS calibration processor to estimate the capacitor mismatch in the background. Three techniques–Learning Rate Decay (LRD), Learning Rate Dynamic-Adjustment (LRDA) and Momentum–were used to enhance the convergence speed of SAR ADC calibration. The LRD technique accelerates the preliminary convergence by gradually reducing the learning rate. The LRDA technique dynamically changes the learning rate based on the magnitude of the gradient, allowing the algorithm to respond quickly to environmental changes and to make precise adjustments as the gradient decreases. The Momentum technique simulates inertia by incorporating the influence of previous updates, which accelerates convergence and minimizes oscillations. Together, these techniques successfully improve the convergence speed and overall performance of the SAR ADC calibration process. Monte Carlo simulation results show that the worst ENOB improves from 8.3 bits to 10.4 bits, after using the proposed LLM-LMS calibration.

Deep reinforcement learning (DRL) based vehicle controllers have shown excellent performance in autonomous driving. While these controllers deliver high performance, their computational demands often require task offloading to external servers. Yet, communication delays can hinder this process, forcing reliance on a simpler local module and compromising driving efficiency. To address this, we propose a framework that integrates action smoothing and local action prediction to enhance performance while ensuring safety under offloading delays. By incorporating a smoothing term into the reinforcement learning reward and introducing a polynomial based smoothing and prediction method, our approach ensures smoother transitions and robust driving. Experiments in the CARLA simulator demonstrate improved vehicle speed, reduced center deviations, and higher track completion rates under imperfect communication conditions.

Intelligent vehicles are systems tightly integrating computation, communication, and physical behavior. The recent proliferation of artificial intelligence, machine learning, the Internet of Things (IoT), and edge-fog–cloud computing envisions that intelligent vehicles are capable of innovative solutions to change our lifestyles. However, the potential benefits come along with new challenges and concerns on security and privacy. This special issue consists of 12 papers and covers broad research contributions, including 1) intrusion detection from in-vehicular networks to connected vehicles, drones, and global positioning systems; 2) authentication with matchmaking encryption, certificateless cryptography, and blockchains for Internet of Vehicles; 3) privacy protection with data sharing and cross-vehicle federated learning; and 4) secure data analysis supported by the cloud. The special issue seeks to assist theoretical analysis, system architecture design, emerging applications, and social impacts of intelligent vehicles.

Reinforcement learning (RL) is challenging in the common case of delays between events and their sensory perceptions. State-of-the-art (SOTA) state augmentation techniques either suffer from state space explosion or performance degeneration in stochastic environments. To address these challenges, we present a novel *Auxiliary-Delayed Reinforcement Learning (AD-RL)* method that leverages auxiliary tasks involving short delays to accelerate RL with long delays, without compromising performance in stochastic environments. Specifically, AD-RL learns a value function for short delays and uses bootstrapping and policy improvement techniques to adjust it for long delays. We theoretically show that this can greatly reduce the sample complexity. On deterministic and stochastic benchmarks, our method significantly outperforms the SOTAs in both sample efficiency and policy performance. Code is available at https://github.com/QingyuanWuNothing/AD-RL.

As vehicular technology advances, vehicles become more connected and autonomous. Connectivity provides the capability to exchange information between vehicles, and autonomy provides the capability to make decisions and control each vehicle precisely. Connectivity and autonomy realize many evolutional applications, such as intelligent intersection management and cooperative adaptive cruise control. Electric vehicles are sometimes combined to create more use cases and business models. However, these intelligent features make the design process more complicated and challenging. In this talk, we introduce several examples of automotive design automation, which is required to improve the design quality and facilitate the design process. We mainly discuss the rising incompatibility issue, where different original equipment manufacturers and suppliers are developing systems, but the designs are confidential and thus incompatible with other players' designs. The incompatibility issue is especially critical with autonomous vehicles because no human driver resolves incompatible scenarios. We believe that techniques and experiences in electronic design automation can provide insights and solutions to automotive design automation.

Intersections are a major source of traffic accidents and congestion. The development of Connected and Autonomous Vehicles (CAVs) is expected to improve safety and traffic efficiency at intersections, but there will be a lengthy period with the existence of Human-driven Vehicles (HVs). For mixed-traffic intersection management, an iconic reservation-based scheduling approach, H-AIM [1], introduces a concept of "active green trajectory" and has a noteworthy performance. However, the traffic model of H-AIM schedules traffic lights for different roads in a rotating manner, which causes lower scheduling flexibility. Therefore, we propose a trigger-based scheduling approach which allows an Intersection Manager (IM) to detect HVs on lanes and trigger the traffic lights correspondingly. Besides, to encourage CAV adoption for more efficient traffic, we propose principles of designing the combinations of turning policies favoring CAVs. The experimental results show that our proposed trigger-based scheduling approach outperforms H-AIM [1], and the turning policy assignment provides insights to mixed-traffic intersection management.

In environments with delayed observation, state augmentation by including actions within the delay window is adopted to retrieve Markovian property to enable reinforcement learning (RL). Whereas, state-of-the-art (SOTA) RL techniques with Temporal-Difference (TD) learning frameworks commonly suffer from learning inefficiency, due to the significant expansion of the augmented state space with the delay. To improve the learning efficiency without sacrificing performance, this work novelly introduces Variational Delayed Policy Optimization (VDPO), reforming delayed RL as a variational inference problem. This problem is further modelled as a two-step iterative optimization problem, where the first step is TD learning in the delay-free environment with a small state space, and the second step is behaviour cloning which can be addressed much more efficiently than TD learning. We not only provide a theoretical analysis of VDPO in terms of sample complexity and performance, but also empirically demonstrate that VDPO can achieve consistent performance with SOTA methods, with a significant enhancement of sample efficiency (approximately 50\% less amount of samples) in the MuJoCo benchmark.

Connected Autonomous Vehicles (CAVs) are expected to enable reliable, efficient, and intelligent transportation systems. Most motion-planning algorithms for multi-agent systems implicitly assume that all vehicles/agents will execute the expected plan with a small error and evaluate their safety constraints based on this fact. This assumption, however, is hard to keep for CAVs since they may have to change their plan (e.g., to yield to another vehicle) or are forced to stop (e.g., a CAV may break down). While it is desired that a CAV never gets involved in an accident, it may be hit by other vehicles and, sometimes, preventing the accident is impossible (e.g., getting hit from behind while waiting at a red light). Responsibility-Sensitive Safety (RSS) is a set of safety rules that defines the objective of CAVs to blame, instead of safety. Thus, instead of developing a CAV algorithm that will avoid any accident, it ensures that the ego vehicle will not be blamed for any accident it is a part of. Original RSS rules, however, are hard to evaluate for merge, intersection, and unstructured road scenarios, plus RSS rules do not prevent deadlock situations among vehicles. In this article, we propose a new formulation for RSS rules that can be applied to any driving scenario. We integrate the proposed RSS rules with the CAV’s motion planning algorithm to enable cooperative driving of CAVs. We use Control Barrier Functions to enforce safety constraints and compute the energy optimal trajectory for the ego CAV. Finally, to ensure liveness, our approach detects and resolves deadlocks in a decentralized manner. We have conducted different experiments to verify that the ego CAV does not cause an accident no matter when other CAVs slow down or stop. We also showcase our deadlock detection and resolution mechanism using our simulator. Finally, we compare the average velocity and fuel consumption of vehicles when they drive autonomously with the case that they are autonomous and connected.

Intersection management systems, with the assistance of vehicular networks and autonomous vehicles, have the potential to perform traffic control more precisely than contemporary signalized intersections. However, as infrastructural intersection management controllers do not directly activate motions of vehicles, it is possible that the vehicles fail to follow the instructions from controllers, undermining system properties such as deadlock-freeness and traffic performance. In this article, we consider a class of robustness issues, the time violations, which stem from possible discrepancies between scheduled orders and real executions. We refine a graph-based intersection model to build our theoretical foundations and analyze potential deadlocks and their resolvability. We develop solutions that mitigate negative effects of time violations. In particular, we propose a Robustness-Aware Greedy Scheduling algorithm for robust scheduling and evaluate the deadlock-free robustness of different intersection models and scheduling algorithms. Experimental results show that the Robustness-Aware Greedy Scheduling algorithm is able to significantly improve robustness and keep a good balance with traffic performance.

Cooperative Adaptive Cruise Control (CACC) is a fundamental connected vehicle application. In CACC, a vehicle coordinates its longitudinal movements to safely and efficiently follow the vehicle in front. The follower vehicle relies on a combination of sensory and communication inputs to identify the position, velocity, and acceleration of the preceding vehicle. Malicious subversion of these inputs can cause catastrophic accidents, string instability, and disruption in the transportation infrastructure. In this paper, we develop a security system, ReCAP, to provide real-time resiliency in CACC against adversarial subversion of both sensory and communication inputs. ReCAP makes use of a combination of techniques based on kinematics and machine learning to detect anomalous inputs, narrow down the source of subversion, and perform mitigation. We provide extensive simulations to demonstrate the effectiveness of ReCAP against a diverse spectrum of attacks under complex, multi-channel adversaries.

Connected and autonomous vehicles (CAVs) can realize many revolutionary applications, but it is expected to have mixed-traffic including CAVs and human-driving vehicles (HVs) together for decades. In this paper, we target the problem of mixed-traffic intersection management and schedule CAVs to control the subsequent HVs. We develop a dynamic programming approach and a mixed integer linear programming (MILP) formulation to optimally solve the problems with the corresponding intersection models. We then propose an MILP-based approach which is more efficient and real-time-applicable than solving the optimal MILP formulation, while keeping good solution quality as well as outperforming the first-come-first-served (FCFS) approach. Experimental results and SUMO simulation indicate that controlling CAVs by our approaches is effective to regulate mixed-traffic even if the CAV penetration rate is low, which brings incentive to early adoption of CAVs.

Neural-network-based (NN-based) planners have been increasingly used to enhance the performance of planning for autonomous vehicles. However, it is often difficult for NN-based planners to balance efficiency and safety in complicated scenarios, especially under real-world communication disturbance. To tackle this challenge, we present a safety-guaranteed framework for NN-based planners in connected vehicle environments with communication disturbance. Given any NN-based planner with no safety-guarantee, the framework generates a robust compound planner embedding the NN-based planner to ensure overall system safety. Moreover, with the aid of an information filter for imperfect communication and an aggressive approach for the estimation of the unsafe set, the compound planner could achieve similar or better efficiency than the given NN-based planner. A comprehensive case study of unprotected left turn and extensive simulations demonstrate the effectiveness of our framework.

The goal of intersection management is to organize vehicles to pass the intersection safely and efficiently. Due to the technical advance of connected and autonomous vehicles, intersection management becomes more intelligent and potentially unsignalized. In this paper, we propose a reinforcement-learning-based methodology to train a centralized intersection manager. We define the intersection scheduling problem with a graph-based model and transform it to the job-shop scheduling problem (JSSP) with additional constraints. To utilize reinforcement learning, we model the scheduling procedure as a Markov decision process (MDP) and train the agent with the proximal policy optimization (PPO). A grouping strategy is also developed to apply the trained model to streams of vehicles. Experimental results show that the learning-based intersection manager is especially effective with high traffic densities. This paper is the first work in the literature to apply reinforcement learning on the graph-based intersection model. The proposed methodology can flexibly deal with any conflicting scenario and indicate the applicability of reinforcement learning to Intelligent intersection management.

Aviation industry is moving towards more electric aircraft, where both non-propulsive and propulsive loads are electrified. While bringing in various benefits, electric propulsion system (EPS) introduces extra complexity and weight to aircraft, as well as raises the reliability concern. New design and analysis tools are required to size the EPS while meeting stringent reliability requirements. This paper investigates how to consolidate readability into the EPS sizing process and makes two-fold contributions. First, a probabilistic algorithm is proposed to assess the reliability of the EPS admitting a directed acyclic graph topology. The algorithm reduces the directed acyclic graph to a layered tree, which simplifies the calculation of joint probability of nodes in each layer. Second, we formulate the reliability-based EPS sizing as an integer nonlinear programming problem, where the reliability requirements are posed as constraints. Preliminary simulation validates the proposed method.

Platooning is a representative application of connected and autonomous vehicles. The information exchanged between connected functions and the precise control of autonomous functions provide great safety and traffic capacity. In this paper, we develop an advanced consensus-based approach for platooning. By applying consensus-based fault detection and adaptive gains to controllers, we can detect faulty position and speed information from vehicles and reinstate the normal behavior of the platooning. Experimental results demonstrate that the developed approach outperforms the state-of-the-art approaches and achieves small steady state errors and small settling times under scenarios with faults.

A weakly-hard fault model can be captured by an (m,k) constraint, where 0≤ m ≤ k , meaning that there are at most m bad events (faults) among any k consecutive events. In this article, we use a weakly-hard fault model to constrain the occurrences of faults in system inputs. We develop approaches to verify properties for all possible values of (m,k) , where k is smaller than or equal to a given K , in an exact and efficient manner. By verifying all possible values of (m,k) , we define weakly-hard requirements for the system environment and design a runtime monitor based on counting the number of faults in system inputs. If the system environment satisfies the weakly-hard requirements, then the satisfaction of desired properties is guaranteed; otherwise, the runtime monitor can notify the system to switch to a safe mode. This is especially essential for cyber-physical systems that need to provide guarantees with limited resources and the existence of faults. Experimental results with discrete second-order control, network routing, vehicle following, and lane changing demonstrate the generality and the efficiency of the proposed approaches.

5G Millimeter Wave (mmWave) technology holds great promise for Connected Autonomous Vehicles (CAVs) due to its ability to achieve data rates in the Gbps range. However, mmWave suffers from a high beamforming overhead and requirement of line of sight (LOS) to maintain a strong connection. For Vehicle-to-Infrastructure (V2I) scenarios, where CAVs connect to roadside units (RSUs), these drawbacks become apparent. Because vehicles are dynamic, there is a large potential for link blockages. These blockages are detrimental to the connected applications running on the vehicle, such as cooperative perception and remote driver takeover. Existing RSU selection schemes base their decisions on signal strength and vehicle trajectory alone, which is not enough to prevent the blockage of links. Many modern CAVs motion planning algorithms routinely use other vehicle’s near-future path plans, either by explicit communication among vehicles, or by prediction. In this paper, we make use of the knowledge of other vehicle’s near future path plans to further improve the RSU association mechanism for CAVs. We solve the RSU association algorithm by converting it to a shortest path problem with the objective to maximize the total communication bandwidth. We evaluate our approach, titled B-AWARE, in simulation using Simulation of Urban Mobility (SUMO) and Digital twin for self-dRiving Intelligent VEhicles (DRIVE) on 12 highway and city street scenarios with varying traffic density and RSU placements. Simulations show B-AWARE results in a 1.05× improvement of the potential datarate in the average case and 1.28× in the best case vs. the state-of-the-art. But more impressively, B-AWARE reduces the time spent with no connection by 42% in the average case and 60% in the best case as compared to the state-of-the-art methods. This is a result of B-AWARE reducing nearly 100% of blockage occurrences.

Different types of lane-changing assistance systems are usually developed separately by different automotive makers or suppliers. A lane-changing model can meet its own requirements, but it may be incompatible with another lane-changing model. In this paper, we verify if two lane-changing models are compatible so that the two corresponding vehicles on different lanes can exchange their lanes successfully. We propose a methodology and an algorithm to perform the verification on the combinations of four lane-changing models. Experimental results demonstrate the compatibility (or incompatibility) between the models. The verification results can be utilized during runtime to prevent incompatible vehicles from entering a lane-changing road segment. To the best of our knowledge, this is the first work considering the compatibility issue for lane-changing models.

We propose a Colored Timed Petri Net (CTPN) based model for intersection management. With the expressiveness of the CTPN-based model, we can consider timing, vehicle-specific information, and different types of vehicles. We then design deadlock-free policies and guarantee deadlock-freeness for intersection management. To the best of our knowledge, this is the first work on CTPN-based deadlock analysis and prevention for intersection management.

Intelligent intersection management aims to schedule vehicles so that vehicles can pass through an intersection efficiently and safely. However, inaccurate control, imperfect communication, and malicious information or behavior lead to robustness issues of intelligent intersection management. In this work, we focus on improving robustness against deadlocks by changing the trajectories of vehicles. To guarantee the resolvability of deadlocks, we limit the number of vehicles in an intersection to be smaller than or equal to an intersection-specific value called the maximal deadlock-free load. We develop an algorithm to compute the maximal deadlock-free load. We further reduce the computation time by computing the loads which are pessimistic (smaller) but still deadlock-free. Since the maximal deadlock-free load only depends on the given intersection, it can be integrated with different scheduling algorithms. Experimental results demonstrate that, by changing the trajectories of vehicles and limiting the number of vehicles under maximal deadlock-free loads, our approach can guarantee deadlock-freeness and maintain good traffic efficiency.

Vehicles can utilize their sensors or receive messages from other vehicles to acquire information about the surrounding environments. However, the information may be inaccurate, faulty, or maliciously compromised due to sensor failures, communication faults, or security attacks. The goal of this work is to detect if a lane-changing decision and the sensed or received information are anomalous. We develop three anomaly detection approaches based on deep learning: a classifier approach, a predictor approach, and a hybrid approach combining the classifier and the predictor. All of them do not need anomalous data nor lateral features so that they can generally consider lane-changing decisions before the vehicles start moving along the lateral axis. They achieve at least 82% and up to 93% F1scores against anomaly on data from Simulation of Urban MObility (SUMO) [1] and HighD [2]. We also examine system properties and verify that the detected anomaly includes more dangerous scenarios.

As automotive systems become more intelligent than ever, they need to handle many functional tasks, resulting in more and more software programs running in automotive systems. However, whether a software program should be executed depends on the environmental conditions (surrounding conditions). For example, a deraining algorithm supporting object detection and image recognition should only be executed when it is raining. Supported by the advance of over-the-air (OTA) updates and plug-and-play systems, adaptive automotive systems, where the software programs are updated, activated, and deactivated before driving and during driving, can be realized. In this paper, we consider the upcoming environmental conditions of an automotive system and target the corresponding software selection problem during runtime. We formulate the problem as a set cover problem with timing constraints and then propose a heuristic approach to solve the problem. The approach is very efficient so that it can be applied during runtime, and it is a preliminary step towards the broad realization of adaptive automotive systems.

The rise of machine learning technology inspires a boom of its applications in electronic design automation (EDA) and helps improve the degree of automation in chip designs. However, manually crafted machine learning models require extensive human expertise and tremendous engineering efforts. In this work, we leverage neural architecture search (NAS) to automate the development of high-quality neural architectures for routability prediction, which can help to guide cell placement toward routable solutions. Our search method supports various operations and highly flexible connections, leading to architectures significantly different from all previous human-crafted models. Experimental results on a large dataset demonstrate that our automatically generated neural architectures clearly outperform multiple representative manually crafted solutions. Compared to the best case of manually crafted models, NAS-generated models achieve 5.85% higher Kendall's$T$in predicting the number of nets with DRC violations and 2.12% better area under ROC curve (ROC-AUC) in DRC hotspot detection. Moreover, compared with human-crafted models, which easily take weeks to develop, our efficient NAS approach finishes the whole automatic search process with only 0.3 days.

In a mandatory lane-changing scenario, vehicles need to move to their target lanes before the end of a road segment. Mandatory lane changing usually happens near a highway ramp, and it is one major source of traffic congestion and delay. The advance of connected and autonomous vehicles supports to solve the problem in a centralized and precise way. We formulate a mandatory lane-changing problem and propose a Mixed-Integer Linear Programming (MILP) approach to find an optimal solution. We then propose an MILP-based incremental-window algorithm to solve the problem efficiently. Experimental results show that the MILP-based incremental-window algorithm can take much less computation time and achieve almost the same solution quality, compared with the original MILP approach. The advantage of efficiency yet sufficient effectiveness matches the need of high-level control (decision of passing order) well.

We introduce SAW, a tool for safety analysis of weakly-hard systems, in which traditional hard timing constraints are relaxed to allow bounded deadline misses for improving design flexibility and runtime resiliency. Safety verification is a key issue for weakly-hard systems, as it ensures system safety under allowed deadline misses. Previous works are either for linear systems only, or limited to a certain type of nonlinear systems (e.g., systems that satisfy exponential stability and Lipschitz continuity of the system dynamics). In this work, we propose a new technique for infinite-time safety verification of general nonlinear weakly-hard systems. Our approach first discretizes the safe state set into grids and constructs a directed graph, where nodes represent the grids and edges represent the reachability relation. Based on graph theory and dynamic programming, our approach can effectively find the safe initial set (consisting of a set of grids), from which the system can be proven safe under given weakly-hard constraints. Experimental results demonstrate the effectiveness of our approach, when compared with the state-of-the-art. An open source implementation of our tool is available at https://github.com/551100kk/SAW . The virtual machine where the tool is ready to run can be found at https://www.csie.ntu.edu.tw/~r08922054/SAW.ova .

In the past decades, the evolution of Industrial Inter-net of Things (IIoT) and Industry 4.0 faces several challenges, and one of them is the proprietary network which causes a rising cost due to the interoperability, compatibility, and strict requirements. To deal with the challenge, industry advocates an open Ethernet-based standard under the IEEE 802.1 family, named Time-Sensitive Networking (TSN), to support real-time and critical applications, where the routing with TSN is still an open and ongoing research problem. Although there are some existing routing approaches, they are offline algorithms and thus not suitable for future industrial automation that needs to support dynamic reconfiguration. Also, they consider either only TSN traffic or only AVB traffic to determine the routing paths, which limits the overall solution space and fails to make the best use of TSN features. To address the issues above, we aim to explore an online routing problem considering both TSN and AVB traffic in a TSN network. It is very first to investigate the online routing problem considering both TSN and AVB traffic. We propose an Ant Colony Optimization (ACO) based approach with a low time complexity to solve the problem. Experimental results show that the proposed algorithm outperforms a well-known solution in terms of the schedulability, performance, number of rerouted streams, and computational efficiency.

Lane merging is one of the major sources causing traffic congestion and delay. With the help of vehicle-to-vehicle or vehicle-to-infrastructure communication and autonomous driving technology, there are opportunities to alleviate congestion and delay resulting from lane merging. In this paper, we first summarize modern features and requirements for lane merging, along with the advance of vehicular technology. We then formulate and propose a dynamic programming algorithm to find the optimal solution for a two-lane merging scenario. It schedules the passing order for vehicles while minimizing the time needed for all vehicles to go through the merging point (equivalent to the time that the last vehicle goes through the merging point). We further extend the problem to a consecutive lane-merging scenario. We show the difficulty to apply the original dynamic programming to the consecutive lane-merging scenario and propose an improved version to solve it. Experimental results show that our dynamic programming algorithm can efficiently minimize the time needed for all vehicles to go through the merging point and reduce the average delay of all vehicles, compared with some greedy methods.

The rapid development of vehicular network and autonomous driving technologies provides opportunities to significantly improve transportation safety and efficiency. One promising application is centralized intelligent intersection management, where an intersection manager accepts requests from approaching vehicles (via vehicle-to-infrastructure communication messages) and schedules the order for those vehicles to safely crossing the intersection. However, communication delays and packet losses may occur due to the unreliable nature of wireless communication or malicious security attacks (e.g., jamming and flooding), and could cause deadlocks and unsafe situations. In our previous work, we considered these issues and proposed a delay-tolerant intersection management protocol for intersections with a single lane in each direction. In this work, we address key challenges in efficiency and deadlock when there are multiple lanes from each direction, and propose a delay-tolerant protocol for general multi-lane intersection management. We prove that this protocol is deadlock free, safe, and satisfies the liveness property. Furthermore, we extend the traffic simulation suite SUMO with communication modules, implement our protocol in the extended simulator, and quantitatively analyze its performance with the consideration of communication delays. Finally, we also model systems that use smart traffic lights with various back-pressure scheduling methods in SUMO, including the basic back-pressure control, the capacity-aware back-pressure control, and the adaptive max-pressure control. We then compare our delay-tolerant intelligent intersection protocol with smart traffic lights that use the three back-pressure scheduling methods, in the case of a network of interconnected intersections. Simulation results demonstrate that our approach significant outperforms the smart traffic lights under normal operation (i.e., when the communication delay is not too large).

In this paper, we propose a game theoretical adversarial intervention detection mechanism for reliable smart road signs. A future trend in intelligent transportation systems is “smart road signs” that incorporate smart codes (e.g., visible at infrared) on their surface to provide more detailed information to smart vehicles. Such smart codes make road sign classification problem aligned with communication settings more than conventional classification. This enables us to integrate well-established results in communication theory, e.g., error-correction methods, into road sign classification problem. Recently, vision-based road sign classification algorithms have been shown to be vulnerable against (even) small scale adversarial interventions that are imperceptible for humans. On the other hand, smart codes constructed via error-correction methods can lead to robustness against small scale intelligent or random perturbations on them. In the recognition of smart road signs, however, humans are out of the loop since they cannot see or interpret them. Therefore, there is no equivalent concept of imperceptible perturbations in order to achieve a comparable performance with humans. Robustness against small scale perturbations would not be sufficient since the attacker can attack more aggressively without such a constraint. Under a game theoretical solution concept, we seek to ensure certain measure of guarantees against even the worst case (intelligent) attackers that can perturb the signal even at large scale. We provide a randomized detection strategy based on the distance between the decoder output and the received input, i.e., error rate. Finally, we examine the performance of the proposed scheme over various scenarios.

With Cooperative Adaptive Cruise Control (CACC) systems, vehicles are allowed to communicate and cooperate with each other to form platoons and improve the traffic throughput, traffic performance, and energy efficiency. In this paper, we take into account the braking factors of different vehicles so that there is a desired platoon sequence which minimizes the platoon length. We formulate the vehicle sequence reordering problem and propose an algorithm to reorder vehicles to their desired platoon sequence.

Advanced driver assistance systems (ADAS), autonomous functions, and connected applications bring a revolution to automotive systems, but they also make automotive design, especially software and electronics, more complex than ever. The complexity introduces significant challenges to automotive industry, and thus design automation, model-based design, and platform-based design can assist system designers to verify design correctness, improve design quality, accelerate design development, reduce design cost, and prevent redesign or recall. Sharing similar concepts with electronic design automation, automotive design automation can be categorized into three core parts: modeling, design (including synthesis and optimization), and analysis (including verification, simulation, and testing).

Emerging applications in connected vehicles have tremendous potential for advances in safety, navigation, traffic management and fuel efficiency, while also posing new security challenges such as false information attacks. This paper targets the problem of securing critical information that is disseminated among nearby vehicles for safety and traffic efficiency purposes through distributed consensus. We present a consensus algorithm, which uses a "proof of eligibility" test to establish that a group of vehicles are actually within the vicinity of the information source. With the presence of a limited number of compromised (Byzantine faulty) participants, our algorithm provides correct consensus among healthy vehicles in real time. The algorithm provides fast and reliable consensus group formation and private key distribution without privileged members, trusted setup, or leader election. In addition to proving a safety property of our consensus algorithm, we have implemented it on top of a widely-used vehicle simulation environment (SUMO, OMNeT++ and Veins) and evaluated its performance on a model of the streets in a real midtown area. Simulation results demonstrate that the algorithm can reach consensus very efficiently (within 9.5s) and with up to 30% of compromised vehicles in a given area. The simulations also demonstrate the ability of our algorithm to more quickly disseminate information about a traffic accident and more efficiently route traffic around the accident site, as compared to previous robust information dissemination approaches.

Intersection management is one of the most representative applications of intelligent vehicles with connected and autonomous functions. The connectivity provides environmental information that a single vehicle cannot sense, and the autonomy supports precise vehicular control that a human driver cannot achieve. Intersection management solves the fundamental conflict resolution problem for vehicles—two vehicles should not appear at the same location at the same time, and, if they intend to do that, an order should be decided to optimize certain objectives such as the traffic throughput or smoothness. In this paper, we first propose a graph-based model for intersection management. The model is general and applicable to different granularities of intersections and other conflicting scenarios. We then derive formal verification approaches which can guarantee deadlock-freeness. Based on the graph-based model and the verification approaches, we develop a centralized cycle removal algorithm for the graph-based model to schedule vehicles to go through the intersection safely (without collisions) and efficiently without deadlocks. Experimental results demonstrate the expressiveness of the proposed model and the effectiveness and efficiency of the proposed algorithm.

We propose a new information-driven intersection control to enhance the quality of transportation by using communication between vehicles and roadside units. The state-of-the-art solutions for intersection control only have access to the sensor data that is collected by vehicles or roadside units. However, congestion at intersections can have different impact on different drivers, and yet such an impact cannot be measured by sensors. An effective intersection control can consider such driver-exclusive differences based on the information reported by the drivers, which can substantially enhance the quality of transportation. However, such information is driver-exclusive, i.e., not verifiable easily, and therefore prone to be misreported strategically. We propose strategy-proof intersection control addressing such issues via a payment-based incentive-compatible mechanism. Particularly, vehicles at close proximity of the intersection report their driver-exclusive utility functions that they want to maximize (not necessarily truthfully), while the roadside unit seeks to maximize the sum of those utilities, i.e., social welfare, by scheduling intersection usage and charging each vehicle an amount of time-tokens corresponding to their impact on other drivers. This approach, based on the Vickrey-Clarke-Groove mechanism, guarantees truthful utility reporting by the vehicles and, correspondingly, maximizes the social welfare. The proposed scheme is universal such that it can be implemented based on various utility functions or intersection control constraints. We also provide a practical implementation to analyze the performance via numerical simulations.

The paradigm of connected vehicles is fast gaining lot of attraction in the automotive industry. Recently, a lot of technological innovation has been pushed through to realize this paradigm using vehicle to cloud (V2C), infrastructure (V2I) and vehicle (V2V) communications. This has also opened the doors for efficient delivery of data/service to the vehicles via edge devices that are closer to the vehicles. In this work, we propose an optimization framework that can be used to deliver data/service to the connected vehicles such that a bandwidth cost objective is optimized. For the first time, we also integrate a vehicle flow model in the optimization framework to model the traffic flow in the coverage area of the edges. Using the optimization framework, we study the variation of the optimal bandwidth cost for varying problem sizes and vehicle flow model parameter values for both data and service delivery.

Advanced driver-assistance systems (ADAS), autonomous driving, and connectivity have enabled a range of new features, but also made automotive design more complex than ever. Formal verification can be applied to establish functional correctness, but its scalability is limited due to the sheer complexity of a modern automotive system. To manage high complexity and limited development resources, one alternative is to apply runtime monitoring techniques to detect when the system transitions into an unsafe state (i.e., one where it violates a critical safety requirement). In this paper, we report on our experience integrating runtime monitoring into a development workflow and present practical design considerations on languages and tools from an industrial perspective. Using signal temporal logic (STL) [12] and the Breach [6] monitoring tool, we perform a case study showing how monitoring can be used to detect undesirable interactions between two ADAS features called Cooperative Pile-up Mitigation System (CPMS) and False-Start Prevention System (FPS). This is an initial step to utilize runtime monitoring to achieve high assurance in the design of intelligent vehicles.

Connected vehicle applications such as autonomous intersections and intelligent traffic signals have shown great promises in improving transportation safety and efficiency. However, security is a major concern in these systems, as vehicles and surrounding infrastructures communicate through ad-hoc networks. In this paper, we will first review security vulnerabilities in connected vehicle applications. We will then introduce and discuss some of the defense mechanisms at network and system levels, including (1) the Security Credential Management System (SCMS) proposed by the United States Department of Transportation, (2) an intrusion detection system (IDS) that we are developing and its application on collaborative adaptive cruise control, and (3) a partial consensus mechanism and its application on lane merging. These mechanisms can assist to improve the security of connected vehicle applications.

We introduce a novel notion of quotient set for a pair of contracts and the operation of quotient for assume-guarantee contracts. The quotient set and its related operation can be used in any compositional methodology where design requirements are mapped into a set of components in a library. In particular, they can be used for the so called missing component problem, where the given components are not capable of discharging the obligations of the requirements. In this case, the quotient operation identifies the contract for a component that, if added to the original set, makes the resulting system fulfill the requirements.

We study collaborative adaptive cruise control as a representative application for safety services provided by autonomous cars. We provide a detailed analysis of attacks that can be conducted by a motivated attacker targeting the collaborative adaptive cruise control algorithm, by influencing the acceleration reported by another car, or the local LIDAR and RADAR sensors. The attacks have a strong impact on passenger comfort, efficiency and safety, with two of such attacks being able to cause crashes. We also present two detection methods rooted in physical-based constraints and machine learning algorithms. We show the effectiveness of these solutions through simulations and discuss their limitations.

A desirable feature of a development tool for SoC design is that, given the important applications in the domain to be targeted by the SoC, a powerful hardware-software partitioning engine is available to determine which function(s) shall be mapped to hardware. However, to provide high-quality partitioning, this engine must be able to consider a rich design space of possible alternate hardware and software implementations for each program region candidate for hardware acceleration, in turn making the task of finding the optimal mapping very difficult given the number of design points to consider and the need for accurate modeling of latency, power and area.

With the fast development of autonomous driving and vehicular communication technologies, intelligent transportation systems that are based on VANET (Vehicular Ad-Hoc Network) have shown great promise. For instance, through V2V (Vehicle-to-Vehicle) and V2I (Vehicle-to-Infrastructure) communication, intelligent intersections allow more fine-grained control of vehicle crossings and significantly enhance traffic efficiency. However, the performance and safety of these VANET-based systems could be seriously impaired by communication delays and packet losses, which may be caused by network congestion or by malicious attacks that target communication timing behavior. In this paper, we quantitatively model and analyze some of the timing and security issues in transportation networks with VANET-based intelligent intersections. In particular, we demonstrate how communication delays may affect the performance and safety of a single intersection and of multiple interconnected intersections, and present our delay-tolerant intersection management protocols. We also discuss the issues of such protocols when the vehicles are non-cooperative and how they may be addressed with game theory.

With the rapid advancement of autonomous driving and vehicular communication technology, intelligent intersection management has shown great promise in improving transportation efficiency. In a typical intelligent intersection, an intersection manager communicates with autonomous vehicles wirelessly and schedules their crossing of the intersection. Previous system designs, however, do not address the possible communication delays due to network congestion or security attacks, and could lead to unsafe or deadlocked systems. In this work, we propose a delay- tolerant protocol for intelligent intersection management, and develop a modeling, simulation and verification framework for analyzing the protocol's safety, liveness and performance. Experiments demonstrate the advantages of our proposed protocol over traditional traffic light control, and more importantly, demonstrate the importance and effectiveness of using this framework to address timing (delay) in vehicular network applications. This work is the first step towards a comprehensive delay-aware design and verification framework for practical vehicular network applications.

As the complexity of vehicular distributed systems increases rapidly, several hundreds of devices are being placed in a modern automotive system. With the increase in wiring cables connecting these devices, the weight of a vehicle increases significantly and degrades the fuel efficiency during driving. In order to reduce the wiring weight, wireless communication has been introduced to replace wiring cables between some devices. However, the extra energy consumption and the transmission delay due to wireless communication need to be considered because they may result in frequent maintenance (e.g., recharging of batteries) and deadline violation, respectively. In this paper, we propose an intravehicle network routing algorithm to simultaneously minimize the wiring weight and the wireless transmit power while considering the transmission delay in automotive systems. Experimental results show that the proposed method can effectively minimize the wiring weight and the wireless transmit power and satisfy other design constraints.

Safety is traditionally the most relevant property for automotive systems, and it is further enhanced by Advanced Driver Assistance Systems (ADAS) in modern automotive systems. To support ADAS and other advanced autonomous functions, automotive electronic systems become more distributed and connected than ever, with in-vehicle architecture or Vehicle-to-X (V2X) communication. These connections create a variety of interfaces which become breeding grounds for security attacks. Accordingly, security becomes a rising issue for automotive systems. In this paper, we address safety and security together, especially their interactions, in Ethernet-based automotive networks which are believed to be the next-generation automotive networks since they are able to provide high bandwidths, certain timing guarantees, and well-developed technologies. We discuss the interactions between safety and security in three problems: secret key management, frame replication and elimination, and Virtual Local Area Network (VLAN) segmentation. We demonstrate that safety and security can work together, but sometimes there is a trade-off between them. This indicates that safety cannot stand alone without considering security, and network security is a necessary component of system security. Towards safer and securer automotive systems, safety and security should be considered together during design stages of automotive systems.

Next-generation autonomous and semi-autonomous vehicles will not only precept the environment with their own sensors, but also communicate with other vehicles and surrounding infrastructures for vehicle safety and transportation efficiency. The design, analysis and validation of various vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) applications involve multiple layers, from V2V/V2I communication networks down to software and hardware of individual vehicles, and concern with stringent requirements on multiple metrics such as timing, security, reliability and fault tolerance. To cope with these challenges, we have been developing CONVINCE, a cross-layer modeling, exploration and validation framework for connected vehicles. The framework includes mathematical models, synthesis and validation algorithms, and a heterogeneous simulator for inter-vehicle communications and intra-vehicle software and hardware in a holistic environment. It explores various design options with respect to constraints and objectives on system safety, security, reliability, cost, etc. A V2V application is used in the case study to demonstrate the effectiveness of the proposed framework.

Optional software-based features are increasingly becoming an important cost driver in automotive systems. These include features pertaining to active safety, infotainment, etc. Currently, these optional features are integrated into the vehicles at the factory during assembly. This severely restricts the flexibility of the customer to select and use features on-demand and therefore, the customer will either have to be satisfied with an available set of feature options or pre-order a car with the required features from the manufacturer resulting in considerable delay. In order to increase flexibility and reduce the delay, it is necessary to provide the option to configure the vehicle on-demand at the dealership or remotely. In this paper, we present our vision and challenges involved in developing a platform infrastructure that allows on-demand deployment of automotive safety features and ensures their correct execution.

As the complexity of vehicular distributed systems increases rapidly, several hundreds of devices (sensors, actuators, etc.) are being placed in a modern automotive system. With the increase in wiring cables connecting these devices, the weight of a car increases significantly, which degrades the fuel efficiency in driving. In order to reduce the weight of a car, wireless communication has been introduced to replace wiring cables between some devices. However, the extra energy consumption for packet transmissions by wireless devices requires frequent maintenance, e.g., recharging of batteries. In this paper, we propose an intra-vehicle network routing algorithm to simultaneously minimize the wiring weight and the transmit power for wireless communication. Experimental results show that the proposed method can effectively minimize the wiring weight and the transmit power for wireless communication.

As the complexities of automotive systems increase, designing a system is a difficult task that cannot be done manually. In this paper, we focus on wire routing and wire sizing for weight minimization to deal with more and more connections between devices in automotive systems. The wire routing problem is formulated as a minimal Steiner tree problem with capacity constraints, and the location of a Steiner vertex is selected to add a splice which is used to connect more than two wires. We modify the Kou-Markowsky-Berman algorithm to efficiently construct Steiner trees and propose an integer linear programming (ILP) formulation to relocate Steiner vertices and satisfy capacity constraints. The ILP formulation is relaxed to a linear programming (LP) formulation which has the same optimal objective and can be solved more efficiently. Besides wire routing, wire sizing is also performed to satisfy resistance constraints and minimize the total wiring weight. To the best of our knowledge, this is the first work in the literature to formulate the automotive routing problem as a minimal Steiner tree problem with capacity constraints and perform wire routing and wire sizing for weight minimization. An industrial case study shows the effectiveness and efficiency of our algorithm which provides an efficient, flexible, and scalable approach for the design optimization of automotive systems.

In this article, we address both security and safety requirements and solve security-aware design problems for the controller area network (CAN) protocol and time division multiple access (TDMA)-based protocols. To provide insights and guidelines for other similar security problems with limited resources and strict timing constraints, we propose a general security-aware design methodology to address security with other design constraints in a holistic framework and optimize design objectives. The security-aware design methodology is further applied to solve a security-aware design problem for vehicle-to-vehicle (V2V) communications with dedicated short-range communication (DSRC) technology. Experimental results demonstrate the effectiveness of our approaches in system design without violating design constraints and indicate that it is necessary to consider security together with other metrics during design stages.

As the complexities of automotive systems increase, designing a system is a difficult task that cannot be done manually. In this paper, we propose an algorithm for weight minimization of wires used for connecting electronic devices in a system. The wire routing problem is formulated as a Steiner tree problem with capacity constraints, and the location of a Steiner vertex is selected for adding a splice connecting more than two wires. Besides wire routing, wire sizing is also done to satisfy resistance constraints and minimize the total wiring weight. Experimental results show the effectiveness and efficiency of our algorithm.

Cyber-security has become a critical issue for realtime distributed embedded systems in domains such as automotive, avionics, and industrial automation. However, in many of such systems, tight resource constraints and strict timing requirements make it difficult or even impossible to add security mechanisms after the initial design stages. To produce secure and safe systems with desired performance, security must be considered together with other objectives at the system level and from the beginning of the design. In this paper, we focus on security-aware design for Time Division Multiple Access (TDMA) based real-time distributed systems. The TDMA-based protocol we consider is an abstraction of many time-triggered protocols that are being adopted in various safety-critical systems for their more predictable timing behavior, such as FlexRay, Time-Triggered Protocol, and Time-Triggered Ethernet. To protect against attacks on TDMA-based real-time distributed systems, we apply a message authentication mechanism with time-delayed release of keys, which provides a good balance between security and computational overhead but needs sophisticated network scheduling to ensure that the increased latencies due to delayed key releases will not violate timing requirements. We propose formulations and an algorithm to optimize the task allocation, priority assignment, network scheduling, and key-release interval length during the mapping process, while meeting both security and timing requirements. Experimental results of an automotive case study and a synthetic example show the effectiveness and efficiency of our approach.

A clock tree typically consumes substantial dynamic power, and thus the considerable heat generated by itself can cause serious clock-skew variations. In this paper, we propose a self-heating-aware buffered clock tree synthesis flow. A mixed integer linear programming (MILP) formulation is proposed to simultaneously model heat spreading, place buffers, and determine a temperature-aware clock tree topology. The formulation is then transformed into a succession of low-complexity feasibility problems to further reduce the runtime. In addition, a fast superposition approach is proposed to incrementally update thermal profiles to reduce simulation time. Experimental results show that our synthesis flow can achieve averagely 50.57% worst-case clock skew reduction, compared with the original symmetrical clock tree.

Cyber-security is a rising issue for automotive electronic systems, and it is critical to system safety and dependability. Current in-vehicles architectures, such as those based on the Controller Area Network (CAN), do not provide direct support for secure communications. When retrofitting these architectures with security mechanisms, a major challenge is to ensure that system safety will not be hindered, given the limited computation and communication resources. We apply Message Authentication Codes (MACs) to protect against masquerade and replay attacks on CAN networks, and propose an optimal Mixed Integer Linear Programming (MILP) formulation for solving the mapping problem from a functional model to the CAN-based platform while meeting both the security and the safety requirements. We also develop an efficient heuristic for the mapping problem under security and safety constraints. To the best of our knowledge, this is the first work to address security and safety in an integrated formulation in the design automation of automotive electronic systems. Experimental results of an industrial case study show the effectiveness of our approach.

As the process technology advances to the nanometer nodes, Optical Proximity Correction (OPC) is the most popular Resolution-Enhancement Technique (RET) in industry for subwavelength lithography, and the inter-level dielectric (ILD) thickness variation caused by the planarization step of the Chemical-Mechanical Polishing (CMP) process also plays a key role for interconnect yield. Considering the OPC and CMP effects simultaneously during the routing stage can significantly alleviate the width and thickness variations (and thus the whole 3D geometry variations) of post-layout RET and CMP operations. In this paper, we first present an efficient, yet sufficiently accurate closed-form formula for printed width computation and dummy-insertion-aware routing cost derivation. The formula provides a cost modeling for post-layout OPC and CMP optimization during routing. Incorporating the OPC and CMP costs, the router can be guided to optimize the effects of layout correction and planarization. Compared with the state-of-the-art OPC-friendly router, QL-MGR (which does not consider CMP), the experimental results show that our approach can achieve respective 19% and 6% reductions in the maximum and average layout distortions. Compared with the state-of-the-art CMP-aware router, TTR (which does not consider OPC), the experimental results show that our approach can achieve respective 19% and 25% reductions in the peak-to-peak thickness and thickness variance. These results indicate that our simultaneous OPC- and CMP-aware router contributes a significant improvement for layout integrity.

Real-Time Calculus (RTC) is a modular performance analysis framework for real-time embedded systems. It can be used to compute the worst-case and best-case response times of tasks with general activation patterns and configurations, such as pipelines of tasks that are connected via finite buffers. In this paper, we extend the existing RTC framework to analyze arbitrary graph configurations of tasks and messages, with mixed periodic and event-based activation models and finite buffers between any pair of nodes. Our extension also improves upon several sources of pessimism in the existing analysis. We present an application of the extended RTC to the Loosely Time-Triggered Architecture (LTTA) implementation of synchronous models, commonly used in the development of embedded automotive, avionics and control systems. We show how our method can be used to model scheduling and communication delays in an LTTA mapping, which gives tighter analysis bounds on the output rate and the latency compared to existing techniques. The evaluation on automotive workloads shows that our approach is scalable and outperforms existing techniques in terms of analysis accuracy.

The flip-chip package is introduced for modern integrated circuit (IC) designs with higher integration density and larger I/O counts. In this paper, we consider the pre-assignment flip-chip routing problem with predefined connections between driver pads and bump pads. This problem has been shown to be much more difficult than the free-assignment one, but is more popular in real-world designs because the connections between driver pads and bump pads are typically predetermined by IC or packaging designers. Based on the concept of routing sequence exchange, we propose a very efficient approach to guide the global routing by computing the longest common subsequence and the maximum planar subset of chords for pre-assignment flip-chips. We observe that the existing work over-constrains the capacity of a routing tile, which might miss some critical solution space with a better routing solution (e.g., smaller wirelength), and provide a remedy for this insufficiency to identify a better solution in a more complete solution space. We also develop a constant-time routability analyzer to check if a given set of wires can pass through a tile. Experimental results show that our router can achieve a$125\times$speedup with even better solution quality (same routability with slightly smaller wirelength), compared with a state-of-the-art flip-chip router based on integer linear programming.

Optical Proximity Correction (OPC) is the most popular technique to handle design shape distortions arising from subwavelength lithography. Existing OPC models are typically very computationally expensive and thus not efficient to be incorporated for layout optimization. In this paper, we present an efficient, yet sufficiently accurate OPC cost model which can predict the optimal location of a wire segment for OPC optimization and give an upper bound of the interference amount, guaranteeing that the interference amount is never underestimated. Based on this cost model, we propose an OPC-aware wire perturbation algorithm for post-layout interconnect optimization. We show that the effects of wire perturbation have the concavity or monotonicity property which can dramatically reduce the search space for finding the optimal location of each wire for OPC optimization. Further, we can incrementally update the OPC cost of a wire by recomputing only the affected wires because of the property of superposition of our model. Experimental results show that our algorithm can efficiently obtain much better OPC results than a state-of-the-art OPC-friendly router, based on a leading commercial OPC tool.

This paper presents an automatic parallax adjustment method that considers the border effect to produce more realistic stereo images on a stereoscopic augmented reality system. Three-dimensional (3D) imaging is an emerging method of displaying three-dimensional information and providing an immersive and intuitive experience with augmented reality. However, the protruding parts of displayed stereoscopic images may be blurry and cause viewing discomfort. Furthermore, the border effect may make it difficult for an imaging system to display regions next to screen borders, even with considerable negative parallax. This paper proposes a method of automatically adjusting the parallax of displayed stereo images by analyzing the feature points in regions near screen borders to produce better stereo effects. Experimental results and a subjective assessment of human factor issues indicate that the proposed method makes stereoscopic augmented reality systems significantly more attractive and comfortable to view.

In this paper, we propose a combined SVC-MDC (scalable video coding & multiple description coding) video coding scheme using the multi-core parallel programming paradigm for P2P video streaming, which is denoted Co-SVC-MDC. To date, P2P video streaming applications are widely popular and emphasized, e.g., PPstream and PPlive, because of higher transmission speed and data availability. However, in the heterogeneous P2P network environment, users are able to utilize PDA, notebook or desktop computer through distinct network interfaces to get on-demand videos ubiquitously. To provide distinct spatial-resolution/fidelity videos and flexible video transmission (playback) over P2P networks, a brand new coding architecture needs to be devised. In the proposed Co-SVC-MDC coding scheme, distinct MDC descriptions contain distinct portions of raw video frames, and each raw frame can be compressed as base layer and SVC enhancement layers. In our experiments, a real implementation of Co-SVC-MDC is exhibited and corresponding performances, e.g., PSNR and decoding speeds, are compared with original SVC in distinct congestion-level P2P networks.

The flip-chip package is introduced for modern IC designs with higher integration density and larger I/O counts. In this paper, we consider the pre-assignment flip-chip routing problem with predefined connections between driver pads and bump pads. This problem has been shown to be much more difficult than the free-assignment one, but is more popular in real-world designs because the connections between driver pads and bump pads are typically pre-determined by IC or packaging designers. Based on the concept of routing sequence exchange, we propose a very efficient global routing algorithm by computing the weighted longest common subsequence (WLCS) and the maximum planar subset of chords (MPSC) for pre-assignment flip-chips. We observe that the existing work over constrains the capacity of a routing tile, which might miss some critical solution space with a better routing solution (e.g., smaller wirelength), and provide a remedy for this insufficiency to identify a better solution in a more complete solution space. We also develop a constant-time routability analyzer to check if a given set of wires can pass through a tile. Experimental results show that our router can achieve a 122X speedup with even better solution quality (same routability with slightly smaller wire-length), compared with a state-of-the-art flip-chip router based on integer linear programming (ILP).

In order to adapt the quality of an on-demand video stream over a time-varying bandwidth channel, a network-aware bandwidth estimation and rate control scheme are required. This paper proposes a predictive video-on-demand (VoD) bandwidth management and a feedback-based buffer control scheme for streaming fine granular scalability videos over wired/WLAN/3G networks. The predictive VoD bandwidth management includes two parts: bandwidth estimation and rate adaptation. According to the measured information of packet round-trip-time, loss-rate, delay jitter and received bit-rate, an improved Kalman filter is proposed to predict an available bandwidth recursively, and to determine a proper transmission rate in consideration of buffer fullness of a decoder. The optimal parameters of the Kalman filter, e.g. a transition matrix and error covariances, can be initialized, converged and adapted to characteristics of the current network. In our experiments, distinct network traffic models are simulated in comparison with pathChirp and one Republic of China patent. The corresponding estimation results with respect to network information are also exhibited in the real networks.

Synchronous audiovisual streaming and playout are two of the major issues in the multimedia communication network. However, the past corresponding researches of media synchronization mainly focused on the mono-quality and single-layer (nonscalable) audiovisual data. To overcome challenges of ubiquitous multimedia streaming, a scalable audiovisual coder that can provide flexible scalabilities and adaptive streaming control to adapt to complicated network situations are both required. This paper proposes a multilayered audiovisual streaming scheme to deliver layered audiovisual data synchronously, which is called ML-AVSS. Fine-granular scalability (FGS) and bit-sliced arithmetic coding (BSAC) techniques are used to segment video and audio data into one base-layer and multiple enhancement-layer bitstreams. With advantages of audiovisual layer coding, a de-jitter procedure, a conditional retransmission mechanism and a playout synchronization mechanism are designed to transmit hybrid multilayered audiovisual bitstreams in consideration of the result of a network bandwidth adaptation and the distinct decoding time-complexity. Experimental results show that the proposed ML-AVSS is a feasible streaming scheme to overcome challenges of ubiquitous multimedia streaming, e.g., constrained channel bandwidth, quality degradation, unsmooth playout, etc.

For a ubiquitous multimedia streaming, an adaptive multimedia streaming scheme with multiple layered audiovisual (AV) coding is required over heterogeneous networks. This paper proposes a multiple layered audiovisual streaming scheme denoted ML-AVSS to deliver layered audiovisual data. Fine-granular scalability (FGS) and bit sliced arithmetic coding (BSAC) techniques are used to segment video and audio data into individual base-layer and multiple enhancement-layer bitstreams. With advantages of layered coding, two phases of streaming synchronization, including a human-perceptual based transmission scheme, de-jitter procedure, conditional retransmission and play- out synchronization, are proposed to transmit hybrid multiple layered audiovisual bitstreams. Experiment results show that the proposed ML-AVSS is a feasible streaming scheme to overcome challenges of the ubiquitous multimedia streaming, e.g., constrained available bandwidth, quality degradation, unsmooth playback, etc.

This paper describes the design and implementation of a 1.5 bit 5thorder CT/DT delta sigma class D amplifier. This chip integrated a 1.5 bit delta sigma modulator and full bridge power stages with programmable dead time control circuits. With the proposed 1.5 bit delta sigma modulator and dead time calibration techniques, 0.02% THD+N ratio, 16 dB dynamic range and 8% power efficiency improvement are achieved in a 0.35 um polycide CMOS technology. This chip consumes 7.8 mA and works at 3 V to 5.5 V supply range. The die area is 6 mm2.

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called the Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity, and thus, most previous works suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph, this paper presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction. Unlike previous heuristics, our algorithm guarantees to find an optimal OARSMT for any two-pin net and many higher pin nets. Extensive experiments show that our algorithm results in significantly shorter wirelengths than all state-of-the-art works.

Given a set of pins and a set of obstacles on routing layers, a multilayer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) connects these pins by rectilinear edges within layers and vias between layers and avoids running through any obstacle to construct a Steiner tree with a minimal total cost. The ML-OARSMT problem is very important for many very large scale integration designs with pins being located in multiple routing layers that contain numerous routing obstacles incurred from IP blocks, power networks, prerouted nets, etc. As a fundamental problem with extensive practical applications to routing and wirelength/congestion/timing estimations in early design stages, it is desired to develop an effective algorithm for the ML-OARSMT problem to facilitate the design flow. However, there is no existing work on this ML-OARSMT problem. In this paper, we first formulate the ML-OARSMT problem with rectangular obstacles and then identify key different properties of this problem from its single-layer counterpart. Based on the multilayer obstacle-avoiding spanning graph, we present the first algorithm to solve the ML-OARSMT problem. Our algorithm can guarantee an optimal solution for any two-pin net and many multiple-pin nets. Experiments show that our algorithm results in 33% smaller total costs on average than a construction-by-correction heuristic which is widely used for Steiner-tree construction in the recent literature.

The electrostatic discharge (ESD) problem has become a challenging reliability issue in nanometer-circuit design. High voltages that resulted from ESD might cause high current densities in a small device and burn it out, so on-chip protection circuits for IC pads are required. To reduce the design cost, the protection circuit should be added only for the IC pads with an ESD current path, which causes the ESD current path analysis problem. In this paper, we first introduce the analysis problem for ESD protection in circuit design. We then model the circuit as a constraint graph, decompose the ESD connected components (ECCs) linked with the pads, and apply breadth-first search (BFS) to identify the ECCs in each constraint graph and, thus, the current paths. Experimental results show that our algorithm can very efficiently and economically detect all ESD paths. For example, our algorithm can detect all ESD paths in a circuit with more than 1.3 million vertices in 1.39 s and consume only 44-MB memory on a 3.0-GHz Intel Pentium 4 PC. To the best of our knowledge, our algorithm is thefirstpointtoolavailable to the public for the ESD analysis.

As IC process geometries scale down to the nanometer territory, the industry faces severe challenges of manufacturing limitations. To guarantee yield and reliability, physical design for manufacturability and reliability has played a pivotal role in resolution and thus yield enhancement for the imperfect manufacturing process. In this paper, we introduce major challenges arising from nanometer process technology, survey key existing techniques for handling the challenges, and provide some future research directions in physical design for manufacturability and reliability.

Given a set of pins and a set of obstacles on routing layers, a multi-layer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) connects these pins by rectilinear edges within layers and vias between layers, and avoids running through any obstacle to construct a Steiner tree with a minimal total cost. The ML-OARSMT problem is very important for many VLSI designs with pins being located in multiple routing layers that contain numerous routing obstacles incurred from IP blocks, power networks, prerouted nets, etc. Therefore, it is desired to develop an effective algorithm for the ML-OARSMT problem. However, there is no existing work on this ML-OARSMT problem. In this paper, we first formulate the ML-OARSMT problem and identify key different properties of the problem from its single-layer counterpart. Based on the multilayer obstacle-avoiding spanning graph (ML-OASG), we present the first algorithm to solve the ML-OARSMT problem. Our algorithm can guarantee an optimal solution for any 2-pin net and many higher-pin nets. Experiments show that our algorithm results in 33% smaller total costs on average than a construction-by-correction heuristic which is widely used for Steiner-tree construction in the recent literature.

In order to adapt the quality of videos streamed over a time-varying bandwidth channel, a network-aware bandwidth management and rate control are required. This paper proposes the well-designed bandwidth estimation and active buffer control for streaming H.264 FGS videos over heterogeneous wired/ wireless/3G networks. According to the information of measured packet round-trip-time, loss-rate and delay jitter, an improved Kalman filter is proposed to predict the throughput recursively, and determine the transmission rate in consideration of buffer fullness of a decoder. The optimal parameters of the Kalman filter, e.g., transition matrix and error covariance, can be initialized, converged and adapted to the current network, even when the session handoff occurs. In our real experiments, distinct network traffic models are simulated, and corresponding estimation results w.r.t. network information are also exhibited.

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity, and thus most previous works suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph (OASG), this paper presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction. Unlike previous heuristics, our algorithm guarantees to find an optimal OARSMT for any 2-pin net and many higher-pin nets. Extensive experiments show that our algorithm results in significantly shorter wirelengths than all state-of-the-art works.

Bit-rate control plays a major role In video coding and multimedia streaming. A well-designed bit-rate control mechanism can achieve line visual qualities and avoid network congestion over a time-varying channel. This paper proposes an H.264 bit-rate control using a 4D perceptual quantization modeling (PQrc), including two major encoding modules: the perceptual frame-level bit-allocation using a 1D temporal pattern and the macroblock-level quantizer decision using a 3D rate pattern. The temporal pattern is used to predict frame complexity and determine proper budget bits further. The rate pattern is depicted as a bit-complexity-quantization (B.C.Q.) model, in which a tangent slope of a B.C.Q. curve is a piece of unique information to find a proper quantizer. For newly generated video clips, the B.C.Q. model is updated continuously using a weighted least-square estimation. In comparison with the latest H.264 JM10.2, our experiment results show that the proposed PQrc can: 1) keep stable buffer fullness and 2) improve the SNR quality and control accuracy effectively.

Bit-rate control has a critical influence in video coding and multimedia streaming. This paper proposes a novel H.264 bit-rate control using a 3D perceptual quantization modeling (PQrc), including two major encoding modules: the perceptual frame-level bit-allocation and the fast macroblock-level quantizer decision. The frame-level budget bit depends on the frame complexity (isin) and buffer fullness, in which e is weighted by the predicted mean-absolute-difference (MAD) and the just-noticeable-difference (JND) PSNR. Considering the MB- level quantizer decision, the 3-D bits-complexity-quantization, which is denoted as B.C.Q., model is established, in which the B.C.Q. curve's tangent slope is a piece of unique information to find a proper quantizer. In comparison with the latest H.264 JM10.2, our experiment results show that the proposedPQrccan improve the SNR quality and keep the stable buffer fullness with less computational cost.

The electrostatic discharge (ESD) problem has become a challenging reliability issue in nanometer circuit design. High voltages resulted from ESD might cause high current densities in a small device and burn it out, so on-chip protection circuits for IC pads are required. To reduce the design cost, the protection circuit should be added only for the IC pads with an ESD current path, which arises the ESD current path analysis problem. In this paper, we first introduce the analysis problem for ESD protection in circuit design. We then model the circuit as a constrained graph, decompose ESD connected components linked with the pads, and apply the breadth-first search (BFS) to identify the ESD connected components in each constrained graph and thus the current paths. Experimental results show that our algorithm can detect all ESD paths very efficiently and economically. To our best knowledge, our algorithm is the first point tool available to the public for the ESD analysis.

In this paper, we propose concurrently searching for correlated mobile users in mobile communications networks. Previous work either focuses on locating a single mobile user or assumes that the locations of mobile users are statistically independent. We first propose a mobility model in which the movements of mobile users are statistically correlated. Next, we use the theory of Markov chain to derive the joint probability density function of the locations of mobile users. In addition, we propose a novel approach to discover the correlations among the locations of mobile users without explicitly calculating the joint probability density function. Our simulation results indicate that exploring the correlations among the locations of mobile users could significantly reduce the average paging delay and increase the maximum stable throughput.