The Smith method has been used to control physical plants with dead time components, where plant states after the dead time is elapsed are predicted and a control input is determined based on the predicted states. We extend the method to the symbolic control and design a symbolic Smith controller to deal with a nondeterministic embedded system. Due to the nondeterministic transitions, the proposed controller computes all reachable plant states after the dead time is elapsed and determines a control input that is suitable for all of them in terms of a given control specification. The essence of the Smith method is that the effects of the dead time are suppressed by the prediction, however, which is not always guaranteed for nondeterministic systems because there may exist no control input that is suitable for all predicted states. Thus, in this paper, we discuss the existence of a deadlock-free symbolic Smith controller. If it exists, it is guaranteed that the effects of the dead time can be suppressed and that the controller can always issue the control input for any reachable state of the plant. If it does not exist, it is proved that the deviation from the control specification is essentially inevitable.

Road traffic collisions are an extremely serious and often fatal issue. One promising approach to mitigate such collisions is the use of connected car services that share road traffic information obtained from vehicles and cameras over mobile networks. In connected car services, it is important for data chunks to arrive at a destination node within a certain deadline constraint. In this paper, we define a flow from a vehicle (or camera) to the same vehicle (or camera) via an MEC server, as a mission critical (MC) flow, and call a deadline of the MC flow the MC deadline. Our research objective is to achieve a higher arrival ratio within the MC deadline for the MC flow that passes through both the radio uplink and downlink. We previously developed a deadline-aware scheduler with consideration for quality fluctuation (DAS-QF) that considers chunk size and a certain deadline constraint in addition to radio quality and utilizes these to prioritize users such that the deadline constraints are met. However, this DAS-QF does not consider that the congestion levels of evolved NodeB (eNB) differ depending on the eNB location, or that the uplink congestion level differs from the downlink congestion level in the same eNB. Therefore, in the DAS-QF, some data chunks of a MC flow are discarded in the eNB when they exceed either the uplink or downlink deadline in congestion, even if they do not exceed the MC deadline. In this paper, to reduce the eNB packet drop probability due to exceeding either the uplink and downlink deadline, we propose a deadline coordination function (DCF) that adaptively sets each of the uplink and downlink deadlines for the MC flow according to the congestion level of each link. Simulation results show that the DAS-QF with DCF offers higher arrival ratios within the MC deadline compared to DAS-QF on its own

Recently proposed irregular networks can reduce the latency for both on-chip and off-chip systems with a large number of computing nodes and thus can improve the performance of parallel applications. However, these networks usually suffer from deadlocks in routing packets when using a naive minimal path routing algorithm. To solve this problem, we focus attention on a lately proposed theory that generalizes the turn model to maintain the network performance with deadlock-freedom. The theorems remain a challenge of applying themselves to arbitrary topologies including fully irregular networks. In this paper, we advance the theorems to completely general ones. Moreover, we provide a feasible implementation of a deadlock-free routing method based on our advanced theorem. Experimental results show that the routing method based on our proposed theorem can improve the network throughput by up to 138 % compared to a conventional deterministic minimal routing method. Moreover, when utilized as the escape path in Duato's protocol, it can improve the throughput by up to 26.3 % compared with the conventional up*/down* routing.

Pre-weighting based Contention Resolution Diversity Slotted ALOHA-like (PW-CRDSA-like) schemes with joint multi-user multi-slot detection (JMMD) algorithm are proposed to improve the throughput of random access (RA) in geostationary earth orbit (GEO) satellite networks. The packet and its replicas are weighted by different pre-weighting factors at each user terminal, and are sent in randomly selected slots within a frame. The correlation of channels between user terminals and satellite node in different slots are removed by using pre-weighting factors. At the gateway station, after the decoding processing of CRDSA, the combinations of remained signals in slots that can construct virtual multiple-input multiple-output (MIMO) signal models are found and decoded by the JMMD algorithm. Deadlock problems that can be equivalent to virtual MIMO signal models in the conventional CRDSA-like schemes can be effectively resolved, which improves the throughput of these CRDSA-like schemes. Simulation results show that the PW-CRDSA-like schemes with the JMMD significantly outperform the conventional CRDSA-like schemes in terms of the throughput under equal packet loss ratio (PLR) conditions (e.g. PLR =10-2), and as the number of the transmitted replicas increases, the throughput of the PW-CRDSA-like schemes also increases, and the normalized maximum throughput of the PW-CRDSA-5 (i.e., PW-CRDSA with 5 replicas) scheme can reach 0.95.

The Infrastructure as a Service (IaaS) Clouds are emerging as a promising platform for the execution of resource demanding and computation intensive workflow applications. Scheduling the execution of scientific applications expressed as workflows on IaaS Clouds involves many uncertainties due to the variable and unpredictable performance of Cloud resources. These uncertainties are modeled by probability distribution functions in past researches or totally ignored in some cases. In this paper, we propose a novel robust deadline constrained workflow scheduling algorithm which handles the uncertainties in scheduling workflows in the IaaS Cloud environment. Our proposal is a static scheduling algorithm aimed at addressing the uncertainties related to: the estimation of task execution times; and, the delay in provisioning computational Cloud resources. The workflow scheduling problem was considered as a cost-optimized, deadline-constrained optimization problem. Our uncertainty handling strategy was based on the consideration of knowledge of the interval of uncertainty, which we used to modeling the execution times rather than using a known probability distribution function or precise estimations which are known to be very sensitive to variations. Experimental evaluations using CloudSim with synthetic workflows of various sizes show that our proposal is robust to fluctuations in estimates of task runtimes and is able to produce high quality schedules that have deadline guarantees with minimal penalty cost trade-off depending on the length of the interval of uncertainty. Scheduling solutions for varying degrees of uncertainty resisted against deadline violations at runtime as against the static IC-PCP algorithm which could not guarantee deadline constraints in the face of uncertainty.

As real-time embedded systems are required to accommodate various tasks with different levels of criticality, scheduling algorithms for MC (Mixed-Criticality) systems have been widely studied in the real-time systems community. Most studies have focused on MC uniprocessor systems whereas there have been only a few studies to support MC multiprocessor systems. In particular, although the ZL (Zero-Laxity) policy has been known to an effective technique in improving the schedulability performance of base scheduling algorithms on SC (Single-Criticality) multiprocessor systems, the effectiveness of the ZL policy on MC multiprocessor systems has not been revealed to date. In this paper, we focus on realizing the potential of the ZL policy for MC multiprocessor systems, which is the first attempt. To this end, we design the ZL policy for MC multiprocessor systems, and apply the policy to EDF (Earliest Deadline First), yielding EDZL (Earliest Deadline first until Zero-Laxity) tailored for MC multiprocessor systems. Then, we develop a schedulability analysis for EDZL (as well as its base algorithm EDF) to support its timing guarantee. Our simulation results show a significant schedulability improvement of EDZL over EDF, demonstrating the effectiveness of the ZL policy for MC multiprocessor systems.

Accurate pedestrian navigation remains a challenge in urban environments. GNSS receiver behaves poorly because the reflection and blockage of the GNSS signals by buildings or other obstacles. Integration of GNSS positioning and Pedestrian Dead Reckoning (PDR) could provide a more smooth navigation trajectory. However, the integration system cannot present the satisfied performance if GNSS positioning has large error. This situation often happens in the urban scenario. This paper focuses on improving the accuracy of the pedestrian navigation in urban environment using a proposed altitude map aided GNSS positioning method. Firstly, we use consistency check algorithm, which is similar to receiver autonomous integrity monitoring (RAIM) fault detection, to distinguish healthy and multipath contaminated measurements. Afterwards, the erroneous signals are corrected with the help of an altitude map. We called the proposed method altitude map aided GNSS. After correcting the erroneous satellite signals, the positioning mean error could be reduced from 17 meters to 12 meters. Usually, good performance for integration system needs accurately calculated GNSS accuracy value. However, the conventional GNSS accuracy calculation is not reliable in urban canyon. In this paper, the altitude map is also utilized to calculate the GNSS localization accuracy in order to indicate the reliability of the estimated position solution. The altitude map aided GNSS and accuracy are used in the integration with PDR system in order to provide more accurate and continuous positioning results. With the help of the proposed GNSS accuracy, the integration system could achieve 6.5 meters horizontal positioning accuracy in urban environment.

Inter-switch networks for HPC systems and data-centers can be improved by applying random shortcut topologies with a reduced number of hops. With minimal routing in such networks; however, deadlock-freedom is not guaranteed. Multiple Virtual Channels (VCs) are efficiently used to avoid this problem. However, previous works do not provide good trade-offs between the number of required VCs and the time and memory complexities of an algorithm. In this work, a novel and fast algorithm, named ACRO, is proposed to endorse the arbitrary routing functions with deadlock-freedom, as well as consuming a small number of VCs. A heuristic approach to reduce VCs is achieved with a hash table, which improves the scalability of the algorithm compared with our previous work. Moreover, experimental results show that ACRO can reduce the average number of VCs by up to 63% when compared with a conventional algorithm that has the same time complexity. Furthermore, ACRO reduces the time complexity by a factor of O(|N|⋅log|N|), when compared with another conventional algorithm that requires almost the same number of VCs.

Petri Net (PN) is a frequently-used model for deadlock detection. Among various detection methods on PN, reachability analysis is the most accurate one since it never produces any false positive or false negative. Although suffering from the well-known state space explosion problem, reachability analysis is appropriate for small- and medium-scale programs. In order to mitigate the explosion problem several kinds of techniques have been proposed aiming at accelerating the reachability analysis, such as net reduction and abstraction. However, these techniques are for general PN and do not take the particularity of application into consideration, so their optimization potential is not adequately developed. In this paper, the feature of mutual exclusion-based program is considered, therefore several strategies are proposed to accelerate the reachability analysis. Among these strategies a customized net reduction rule aims at reducing the scale of PN, two marking compression methods and two pruning methods can reduce the volume of reachability graph. Reachability analysis on PN can only report one deadlock on each path. However, the reported deadlock may be a false alarm in which situation real deadlocks may be hidden. To improve the detection efficiency, we proposed a deadlock recovery algorithm so that more deadlocks can be detected in a shorter time. To validate the efficiency of these methods, a prototype is implemented and applied to SPLASH2 benchmarks. The experimental results show that these methods accelerate the reachability analysis for mutual exclusion-based deadlock detection significantly.

As the semiconductor technology continues to develop, hundreds of cores will be deployed on a single die in the future Chip-Multiprocessors (CMPs) design. Three-Dimensional Network-on-Chips (3D NoCs) has become an attractive solution which can provide impressive high performance. An efficient and deadlock-free routing algorithm is a critical to achieve the high performance of network-on-chip. Traditional methods based on deterministic and turn model are deadlock-free, but they are unable to distribute the traffic loads over the network. In this paper, we propose an efficient, adaptive and deadlock-free algorithm (EAR) based on a novel routing selection strategy in 3D NoC, which can distribute the traffic loads not only in intra-layers but also in inter-layers according to congestion information and path diversity. Simulation results show that the proposed method achieves the significant performance improvement compared with others.

This paper presents a parallelization method utilizing dead time to implement higher precision feedback control systems in multicore processors. The feedback control system is known to be difficult to parallelize, and it is difficult to deal with the dead time in control systems. In our method, the dead time is explicitly represented as delay elements. Then, these delay elements are distributed to the overall systems with equivalent transformation so that the system can be simulated or executed in parallel pipeline operation. In addition, we introduce a method of delay-element addition for parallelization. For a spring-mass-damper model with a dead time, parallel execution of the model using our technique achieves 3.4 times performance acceleration compared with its sequential execution on an ideal four-core simulation and 1.8 times on a cycle-accurate simulator of a four-core embedded processor as a threaded application on a real-time operating system.

Web Service Business Process Execution Language (BPEL) has become the de facto standard for developing instant service-oriented workflow applications in open environment. The correctness and reliability of BPEL processes have gained increasing concerns. However, the unique features (e.g., dead path elimination (DPE) semantics, parallelism, etc.) of BPEL language have raised enormous problems to it, especially in path feasibility analysis of BPEL processes. Path feasibility analysis of BPEL processes is the basis of BPEL testing, for it relates to the test case generation. Since BPEL processes support both parallelism and DPE semantics, existing techniques can't be directly applied to its path feasibility analysis. To address this problem, we present a novel technique to analyze the path feasibility for BPEL processes. First, to tackle unique features mentioned above, we transform a BPEL process into an intermediary model — BPEL control flow graph, which is proposed to abstract the execution flow of BPEL processes. Second, based on this abstraction, we symbolically encode every path of BPEL processes as some Satisfiability formulas. Finally, we solve these formulas with the help of Satisfiability Modulo Theory (SMT) solvers and the feasible paths of BPEL processes are obtained. We illustrate the applicability and feasibility of our technique through a case study.

In Worldwide interoperability for Microwave Access (WiMAX) network, QoS(quality of service) is provided for service flows. For this, five classes of services are defined in IEEE 802.16. They are Unsolicited Grant Service (UGS), Extended Real-Time Polling Service (ertPS), Real-Time Polling Service (rtPS), Non Real-Time Polling Service (nrtPS) and Best Effort (BE). For real-time classes, the sent packet has a deadline. As the transmission delay is over the limitation of deadline, the packet becomes useless and will be discarded. Thus, they will be served earlier and have higher probability. Nevertheless, non-real-time packets need also to be served from time to time. The scheduler should assign proper bandwidth for non-real-time flows and send the real-time packets before they are discarded. To deicide the right allocated bandwidth, the arrival rate of each flow is a good parameter for assignment. The average µ and standard deviation σ of arrival rate correspond to the long term need and variation of load for one flow. Thus, we proposed a scheduling algorithm named BAcSOA in which µ+kσ is used as a reference to allocate bandwidth with weighted round robin for one flow [5]. Different classes of flows will be given different values of k which corresponds to the priorities of classes. In this algorithm, flow with higher priority should have larger value of k. The value of k will decide the performance of this class. In this paper, we revise the algorithm to EBAcSOA and propose a mathematical way to decide the value of k for a required performance. Then, a simulation platform is proposed to decide k such that a required performance can be obtained for an operating system. This approach may be different from other researches in which there is no required performance and the performance results are obtained only for several operating points. However, the approach proposed is more practical from the view of an operator and may become an attractive point for other researchers.

Pedestrian dead reckoning (PDR) is an effective positioning means that can be used in urban-canyon environments where the accuracy of GPS is significantly degraded. Magnetic disturbances caused by artificial objects affect the accuracy of positioning if the PDR system uses a magnetometer to estimate the heading direction. Conventional PDR systems consider magnetic disturbances as unpredictable error sources, but the error becomes predictable and removable if the amount of the deviation in the magnetic field can be calculated at any position. In this study, we propose a method to correct the heading direction by referring to a map of magnetic deviation. The experimental results show that our method reduced the error in the heading direction caused by magnetic disturbances. Our approach removed the error components that differ depending on the position, and consequently, the resultant trajectory represented better the shape of the true trajectory.

Petri nets are a kind of formal language that are widely applied in concurrent systems associated with resource allocation due to their abilities of the natural description on resource allocation and the precise characterization on deadlock. Weighted System of Simple Sequential Processes with Resources (WS3PR) is an important subclass of Petri nets that can model many resource allocation systems in which 1) multiple processes may run in parallel and 2) each execution step of each process may use multiple units from a single resource type but cannot use multiple resource types. We first prove that the liveness problem of WS3PR is co-NP-hard on the basis of the partition problem. Furthermore, we present a necessary and sufficient condition for the liveness of WS3PR based on two new concepts called Structurally Circular Wait (SCW) and Blocking Marking (BM), i.e., a WS3PR is live iff each SCW has no BM. A sufficient condition is also proposed to guarantee that an SCW has no BM. Additionally, we show some advantages of using SCW to analyze the deadlock problem compared to other siphon-based ones, and discuss the relation between SCW and siphon. These results are valuable to the further research on the deadlock prevention or avoidance for WS3PR.

With the fast development of mobile communication technologies, mobile multimedia services like mobile Video on Demand (VOD) are becoming prevalent. However, VOD streaming requires dedicated bandwidth to satisfy Quality of Service (QoS), and the limited wireless bandwidth will become insufficient to support the increasing number of mobile VOD users. In order to solve the problem, this paper proposes a Call Admission Control (CAC) approach which can accept new users even when the system bandwidth is insufficient. Our approach also guarantees continuous playback for subscribers by taking into account the service end time and the delay bound of the users. Simulation results demonstrate that the proposed scheme can increase the number of concurrent users and reduce the connection blocking probability significantly without playback interruption.

This paper presents a novel chunk selection strategy for peer-to-peer video streaming, called enr-first selection policy, which simultaneously considers both block rarity and playback deadline. The policy intends to boost overall network-wide streaming performance, while ensuring good playback continuity of individual peers. The efficacy of the proposed scheme is validated through our performance evaluation study that demonstrates a substantial gain.

Manufacturing defects in the deep sub-micron VLSI process and aging resulted problems of devices during lifecycle are inevitable, and fault-tolerant routing algorithms are important to provide the required communication for NoCs in spite of failures. The proposed algorithm, referred to as scalable and reconfigurable fault-tolerant distributed routing (RFDR), partitions the system into nine regions using the concept of divide-and-conquer. It is a distributed algorithm, and each router guarantees fault-tolerance within one's own region and the system can be still sustained with multiple fault areas. The proposed RFDR has excellent scalability with hardware cost keeping constant independent of system size. Also it is completely reconfigurable when new nodes fail. Simulations under various synthetic traffic patterns show its better performance compared to Extended-XY routing algorithm. Moreover, there is almost no hardware overhead compared to Logic-Based Distributed Routing (LBDR), but the fault-tolerance capacity is enhanced in the proposed algorithm. Hardware cost is reduced 37% compared to Reconfigurable Distributed Scalable Predictable Interconnect Network (R-DSPIN) which only supports single fault region.

This paper presents a novel charge transfer CMOS readout circuit for an X-ray time delay and integration (TDI) array with a depth of 64. In this study, a charge transfer readout scheme based on CMOS technology is proposed to sum 64 stages of the TDI signal. In addition, a dead pixel elimination circuit is integrated within a chip, thus resolving the weakness of TDI arrays related to defective pixels. The proposed method is a novel CMOS solution for large depth TDI arrays. Thus, a high signal-to-noise ratio (SNR) can be acquired due to the increased TDI depth. The readout chip was fabricated with a 0.6 µm standard CMOS process for a 15064 CdTe X-ray detector array. The readout circuit was found to effectively increase the charge storage capacity up to 1.6108 electrons, providing an improved SNR by a factor of approximately 8. The measured equivalent noise charge resulting from the readout circuit was 1.68104 electrons, a negligible value compared to the shot noise from the detector.

Pedestrian dead reckoning (PDR) based on human gait locomotion is a promising solution for indoor location services, which independently determine the relative position of the user using multiple sensors. Most existing PDR methods assume that all sensors are mounted in a fixed position on the user's body while walking. However, it is inconvenient for a user to mount his/her mobile phone or additional sensor modules in a specific position on his/her body such as the torso. In this paper, we propose a new PDR method and a prototype system suitable for indoor navigation systems on a mobile phone. Our method determines the user's relative position even if the sensors' orientation relative to the user is not given and changes from moment to moment. Therefore, the user does not have to mount the mobile phone containing sensors on the body and can carry it in a natural way while walking, e.g., while swinging the arms. Detailed algorithms, implementation and experimental evaluation results are presented.