The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Time-triggered offline scheduling is a cost-efficient way to guarantee low communication end-to-end latency and minimal jitter for communication networks in real-time systems. The schedule is generated pre-runtime and indicates the transmission times of time-triggered frames such that contention is prevented. The synthesis of such offline schedules is a bin-packing problem, known to be NP-complete,...
In this article a new task model, called DGMF, is proposed to improve scheduling analysis of dependent tasks in radio stations that embed a TDMA communication protocol. TDMA is a channel access protocol that allows several stations to communicate in a same network, by dividing time into several time slots. This protocol has an impact on task release times, execution times, and deadlines, which needs...
The paper is devoted to Time Division Multiple Access Link Scheduling Protocols in wireless sensor networks for full duplex (two-way) communication, where each sensor is scheduled on an incident link as a transmitter and as a receiver in two different time slots. We formulate the full duplex link scheduling problem (FDLSP) as distance-2 edge coloring in bi-directed graphs. We proves that there exists...
The growing demand for mobile wireless access has stimulated the emergence of new communication technologies. Opportunistic Spectrum Access (OSA) is viewed as a promising alternative to overcome the problems caused by static spectrum assignment. Opportunistic access allows dynamic mapping of the transmission needs and communication opportunities. However, performing this task efficiently is not trivial...
Heterogeneity in resources pervades all modern computing platforms. How do the effects of heterogeneity depend on which resources differ among computers in a platform? Some answers are derived within a formal framework, by comparing heterogeneity in computing power (node-heterogeneity) with heterogeneity in communication speed (link-heterogeneity). The former genre of heterogeneity seems much easier...
A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the system recovers from this catastrophic situation without external intervention in finite time. In this paper, we consider the problem of constructing self-stabilizingly a locally maximizable task (such as constructing a maximal independent set, a maximal matching,...
The Controller Area Network (CAN) protocol is widely employed in the development of distributed embedded systems. Building on the CAN protocol, previous studies have illustrated how “Shared-Clock” (S-C) algorithms can be used in conjunction with off-the-shelf microcontrollers to create high-reliability distributed systems at low cost. In such studies, it has generally been assumed that S-C designs...
Given a graph G = (V, E), an edge-coloring of G is a function from the set of edges E to colors {1, 2. .., k} such that any two adjacent edges are assigned different colors. In this paper, we propose a self-stabilizing edge-coloring algorithm in a polynomial number of moves. The protocol assumes the unfair central d??mon and the coloring is a (Δ + 1)-edge-coloring of G, where Δ is the maximum degree...
In wireless networks, mutual interference prevents wireless devices from correctly receiving packages from others and becomes one of the challenges in the design of protocols for wireless networks. Spatial-reuse time division multiple access (STDMA) has been used to cope with this problem. In this scheme, links are assigned to several time slots and in each slot all the links can transmit simultaneously...
This paper will firstly analyze Ditian algorithm and Chi-fu Huang algorithm, pointing out the advantages and disadvantages for both of them, then propose a new algorithm called DSA combining the two algorithms, which can self-adapt its algorithm complexity and communication cost based on the density variation for the nodes in the network.
Event schedulers, well-known from groupware and social software, typically share the problem that they disclose detailed availability patterns of their users. This paper distinguishes event scheduling from electronic voting and proposes a privacy-enhanced event scheduling scheme. Based on superposed sending and Diffie-Hellman key agreement, it is designed to be efficient enough for practical implementations...
Fast turnaround time of vessels and high berth productivity are paramount factors by which a container terminal holds its competitive advantage in the shipping industry. The berth allocation plays an important role in ensuring the terminal to have high berth productivity. Most of the methods employed to tackle berth allocation problem adopt scheduling algorithms based on centralized control. This...
In a distributed system, the environment is described by the scheduler (also called adversary or demon). Through an example related to stabilization, we show that a formal proof that does not use a formal definition of a scheduler is pointless. As a matter of fact, we show that the same algorithm, according to the scheduler, can be either correct or incorrect and in the cases where it is correct,...
Three applications in wireless networks where model-free stochastic learning is applicable, are discussed. The learning based optimization problems are formulated and simulation results are presented. Some open issues are also discussed.
With the increase of network bandwidth, high performance protocol processing has shown its importance in network systems. Experimental results show that some advances in computer architecture, such as faster processors and larger cache, are not enough for TCP/IP processing (Markatos, 2002). In this paper, we present a formal analysis on I-cache behavior of batch protocol processing. We prove that...
We study two parallel scheduling problems and their use in designing parallel algorithms. First, we define a novel scheduling problem; it is solved by repeated, rapid, approximate reschedulings. This leads to a first optimal PRAM algorithm for list ranking, which runs in logarithmic time. Our second scheduling result is for computing prefix sums of logn bit numbers. We give an optimal parallel algorithm...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.