Competitive analysis of partitioned scheduling on uniform multiprocessors

Consider the problem of scheduling a set of sporadically arriving tasks on a uniform multiprocessor with the goal of meeting deadlines. A processor p has the speed Sp. Tasks can be preempted but they cannot migrate between processors. We propose an algorithm which can schedule all task sets that any other possible algorithm can schedule assuming that our algorithm is given processors that are three times faster.

Competitive analysis of static-priority partitioned scheduling on uniform multiprocessors

Consider the problem of scheduling a set of sporadically arriving tasks on a uniform multiprocessor with the goal of meeting deadlines. A processor p has the speed Sp. Tasks can be preempted but they cannot migrate between processors. On each processor, tasks are scheduled according to rate-monotonic. We propose an algorithm that can schedule all task sets that any other possible algorithm can schedule assuming that our algorithm is given processors that are √2 / √2−1 ≈ 3.41 times faster. No such guarantees are previously known for partitioned static-priority scheduling on uniform multiprocessors.

A two-competitive approximate schedulability analysis of CAN

Consider the problem of deciding whether a set of n sporadic message streams meet deadlines on a Controller Area Network (CAN) bus for a specified priority assignment. It is assumed that message streams have implicit deadlines and no release jitter. An algorithm to solve this problem is well known but unfortunately it time complexity is non-polynomial. We present an algorithm with polynomial time-complexity for computing an upper bound on the response times. Clearly, if the upper bound on the response time does not exceed the deadline then all deadlines are met. The pessimism of our approach is proven: if the upper bound of the response time exceeds the deadline then the response time exceeds the deadline as well for a CAN network with half the speed.

The utilization bound of uniprocessor preemptive slack-monotonic scheduling is 50%

Consider the problem of scheduling a set of sporadically arriving implicit-deadline tasks to meet deadlines on a uniprocessor. Static-priority scheduling is considered using the slack-monotonic priority-assignment scheme. We prove that its utilization bound is 50%.

Implementation of a dominance protocol for wireless medium access

Consider the problem of scheduling sporadic message transmission requests with deadlines. For wired channels, this has been achieved successfully using the CAN bus. For wireless channels, researchers have recently proposed a similar solution; a collision-free medium access control (MAC) protocol that implements static-priority scheduling. Unfortunately no implementation has been reported, yet. We implement and evaluate it to find that the implementation indeed is collision-free and prioritized. This allows us to develop schedulability analysis for the implementation. We measure the response times of messages in our implementation and find that our new response-time analysis indeed offers an upper bound on the response times. This enables a new class of wireless real-time systems with timeliness guarantees for sporadic messages and it opens-up a new research area: schedulability analysis for wireless networks.

Collision-free prioritized medium access in the presence of hidden nodes without relying on out-of-band signaling

Consider the problem of sharing a wireless channel between a set of computer nodes. Hidden nodes exist and there is no base station. Each computer node hosts a set of sporadic message streams where a message stream releases messages with real-time deadlines. We propose a collision-free wireless medium access control (MAC) protocol which implements staticpriority scheduling. The MAC protocol allows multiple masters and is fully distributed. It neither relies on synchronized clocks nor out-of-band signaling; it is an adaptation to a wireless channel of the dominance protocol used in the CAN bus. But unlike that protocol, our protocol does not require a node having the ability to receive an incoming bit from the channel while transmitting to the channel. Our protocol has the key feature of not only being prioritized and collision-free but also dealing successfully with hidden nodes. This key feature enables schedulability analysis of sporadic message streams in multihop networks.

A fractional approach for the motion planning of redundant and hyper-redundant manipulators

The trajectory planning of redundant robots through the pseudoinverse control leads to undesirable drift in the joint space. This paper presents a new technique to solve the inverse kinematics problem of redundant manipulators, which uses a fractional differential of order α to control the joint positions. Two performance measures are defined to examine the strength and weakness of the proposed method. The positional error index measures the precision of the manipulator's end-effector at the target position. The repeatability performance index is adopted to evaluate if the joint positions are repetitive when the manipulator execute repetitive trajectories in the operational workspace. Redundant and hyper-redundant planar manipulators reveal that it is possible to choose in a large range of possible values of α in order to get repetitive trajectories in the joint space.

A survey of technologies and applications for climbing robots locomotion and adhesion

The interest in the development of climbing robots has grown rapidly in the last years. Climbing robots are useful devices that can be adopted in a variety of applications, such as maintenance and inspection in the process and construction industries. These systems are mainly adopted in places where direct access by a human operator is very expensive, because of the need for scaffolding, or very dangerous, due to the presence of an hostile environment. The main motivations are to increase the operation efficiency, by eliminating the costly assembly of scaffolding, or to protect human health and safety in hazardous tasks. Several climbing robots have already been developed, and other are under development, for applications ranging from cleaning to inspection of difficult to reach constructions. A wall climbing robot should not only be light, but also have large payload, so that it may reduce excessive adhesion forces and carry instrumentations during navigation. These machines should be capable of travelling over different types of surfaces, with different inclinations, such as floors, walls, or ceilings, and to walk between such surfaces (Elliot et al. (2006); Sattar et al. (2002)). Furthermore, they should be able of adapting and reconfiguring for various environment conditions and to be self-contained. Up to now, considerable research was devoted to these machines and various types of experimental models were already proposed (according to Chen et al. (2006), over 200 prototypes aimed at such applications had been developed in the world by the year 2006). However, we have to notice that the application of climbing robots is still limited. Apart from a couple successful industrialized products, most are only prototypes and few of them can be found in common use due to unsatisfactory performance in on-site tests (regarding aspects such as their speed, cost and reliability). Chen et al. (2006) present the main design problems affecting the system performance of climbing robots and also suggest solutions to these problems. The major two issues in the design of wall climbing robots are their locomotion and adhesion methods. With respect to the locomotion type, four types are often considered: the crawler, the wheeled, the legged and the propulsion robots. Although the crawler type is able to move relatively faster, it is not adequate to be applied in rough environments. On the other hand, the legged type easily copes with obstacles found in the environment, whereas generally its speed is lower and requires complex control systems. Regarding the adhesion to the surface, the robots should be able to produce a secure gripping force using a light-weight mechanism. The adhesion method is generally classified into four groups: suction force, magnetic, gripping to the surface and thrust force type. Nevertheless, recently new methods for assuring the adhesion, based in biological findings, were proposed. The vacuum type principle is light and easy to control though it presents the problem of supplying compressed air. An alternative, with costs in terms of weight, is the adoption of a vacuum pump. The magnetic type principle implies heavy actuators and is used only for ferromagnetic surfaces. The thrust force type robots make use of the forces developed by thrusters to adhere to the surfaces, but are used in very restricted and specific applications. Bearing these facts in mind, this chapter presents a survey of different applications and technologies adopted for the implementation of climbing robots locomotion and adhesion to surfaces, focusing on the new technologies that are recently being developed to fulfill these objectives. The chapter is organized as follows. Section two presents several applications of climbing robots. Sections three and four present the main locomotion principles, and the main "conventional" technologies for adhering to surfaces, respectively. Section five describes recent biological inspired technologies for robot adhesion to surfaces. Section six introduces several new architectures for climbing robots. Finally, section seven outlines the main conclusions.

Fractional dynamics in the trajectory control of redundant manipulators

Under the pseudoinverse control, robots with kinematical redundancy exhibit an undesirable chaotic joint motion which leads to an erratic behavior. This paper studies the complexity of fractional dynamics of the chaotic response. Fourier and wavelet analysis provides a deeper insight, helpful to know better the lack of repeatability problem of redundant manipulators. This perspective for the study of the chaotic phenomena will permit the development of superior trajectory control algorithms.

Multiple Roots of Systems of Equations by Repulsion Merit Functions

In this paper we address the problem of computing multiple roots of a system of nonlinear equations through the global optimization of an appropriate merit function. The search procedure for a global minimizer of the merit function is carried out by a metaheuristic, known as harmony search, which does not require any derivative information. The multiple roots of the system are sequentially determined along several iterations of a single run, where the merit function is accordingly modified by penalty terms that aim to create repulsion areas around previously computed minimizers. A repulsion algorithm based on a multiplicative kind penalty function is proposed. Preliminary numerical experiments with a benchmark set of problems show the effectiveness of the proposed method.

Numerical analysis of the initial conditions in fractional systems

Fractional dynamics is a growing topic in theoretical and experimental scientific research. A classical problem is the initialization required by fractional operators. While the problem is clear from the mathematical point of view, it constitutes a challenge in applied sciences. This paper addresses the problem of initialization and its effect upon dynamical system simulation when adopting numerical approximations. The results are compatible with system dynamics and clarify the formulation of adequate values for the initial conditions in numerical simulations.

Definition of Distribution Network Tariffs Considering Distribution Generation and Demand Response

The use of distribution networks in the current scenario of high penetration of Distributed Generation (DG) is a problem of great importance. In the competitive environment of electricity markets and smart grids, Demand Response (DR) is also gaining notable impact with several benefits for the whole system. The work presented in this paper comprises a methodology able to define the cost allocation in distribution networks considering large integration of DG and DR resources. The proposed methodology is divided into three phases and it is based on an AC Optimal Power Flow (OPF) including the determination of topological distribution factors, and consequent application of the MW-mile method. The application of the proposed tariffs definition methodology is illustrated in a distribution network with 33 buses, 66 DG units, and 32 consumers with DR capacity.

Numerical analysis of the initial conditions in fractional systems

Fractional dynamics is a growing topic in theoretical and experimental scientific research. A classical problem is the initialization required by fractional operators. While the problem is clear from the mathematical point of view, it constitutes a challenge in applied sciences. This paper addresses the problem of initialization and its effect upon dynamical system simulation when adopting numerical approximations. The results are compatible with system dynamics and clarify the formulation of adequate values for the initial conditions in numerical simulations.

Numerical calculation of the left and right fractional derivatives

The calculation of fractional derivatives is an important topic in scientific research. While formal definitions are clear from the mathematical point of view, they pose limitations in applied sciences that have not been yet tackled. This paper addresses the problem of obtaining left and right side derivatives when adopting numerical approximations. The results reveal the relationship between the resulting distinct values for different fractional orders and types of signals.

Allocation of Parallel Real-Time Tasks in Distributed Multi-core Architectures supported by an FTT-SE Network

Distributed real-time systems such as automotive applications are becoming larger and more complex, thus, requiring the use of more powerful hardware and software architectures. Furthermore, those distributed applications commonly have stringent real-time constraints. This implies that such applications would gain in flexibility if they were parallelized and distributed over the system. In this paper, we consider the problem of allocating fixed-priority fork-join Parallel/Distributed real-time tasks onto distributed multi-core nodes connected through a Flexible Time Triggered Switched Ethernet network. We analyze the system requirements and present a set of formulations based on a constraint programming approach. Constraint programming allows us to express the relations between variables in the form of constraints. Our approach is guaranteed to find a feasible solution, if one exists, in contrast to other approaches based on heuristics. Furthermore, approaches based on constraint programming have shown to obtain solutions for these type of formulations in reasonable time.