The number of cars participating in highway traffic is still growing as well as the necessity of quick and fluent transport between different locations. Therefore, ensuring the fluency and safety in highway traffic is becoming an essential problem in recent times. If only the driver knew about a danger waiting behind the bend, he would slow down; if someone got the information about a traffic jam 10 km earlier, he would probably take a different road or stop. This paper aims at providing transport telematics solutions which ensure simple, fast and efficient means for highway traffic management. The ad hoc algorithms presented concern broadcasting within highway traffic and assume the collisions detection and a single hop network. Installing a simple transmitter and receiver on every car is considered. Energy efficient size approximation algorithms and a leader selection procedure are presented and discussed, including simulations.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In the paper triangular graphs are discussed. The class of triangular graphs is of special interest as unifying basic features of complete graphs and trees. The main issue addressed in the paper is to characterize class of triangular graphs (defined globally) by local means. Namely, it is proved that any triangular graph can be constructed from a singleton by successive extensions with nodes having complete neighborhoods. Next, the proved theoretical properties are applied for designing some local algorithms for triangular graphs: for elections a leader and for constructing their spanning trees. The fairness of these algorithms is proved, which means that any node can be elected and any spanning tree can be constructed by execution of these algorithms.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We consider the leader election problem in a ring whose nodes have possibly nonunique labels. Every node knows a priori its own label and two integers, m and M, which are, respectively, a lower and an upper bound on the (unknown) size n of the ring. The aim is to decide whether leader election is possible and to perform it, if so. We consider both the synchronous and the asynchronous version of the problem and we are interested in message complexity in both cases. For the synchronous version we present an algorithm using O(n logn) messages and working in time O(M). Moreover, our algorithm uses O(n) messages when all identifiers are distinct. For the asynchronous version we show an Ω(nM) lower bound on message complexity for this problem, and present an algorithm for it using O(nM) messages.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.