Gérard Le Lann

A Collision-Free MAC Protocol for Fast Message Dissemination in Vehicular Strings

Keywords: vehicular networks, automated vehicles, string control, safety, V2V communications, MAC protocols, timebounded channel access, time-bounded message dissemination I

The focus of this paper is on safety-critical intervehicular communications in strings circulating on highways and main roads. The bounded channel access delay (BCAD) and the time-bounded message acknowledgment (TBMA) problems are specified. We present a collision-free deterministic directional MAC protocol that solves both problems. At the same time, that protocol minimizes string-wide message dissemination delays, in the presence of message and acknowledgement losses. Analytical expressions of various time bounds are given and illustrated with numerical examples.

INTRODUCTION

This paper presents a MAC protocol which might be of interest to standardization bodies in charge of safety-critical (SC) vehicle-to-vehicle (V2V) communications. Our focus is on strings. A single lane instance of a VANET (vehicular ad hoc network), a string may be pre-planned, a.k.a. platoon [START_REF] Shladover | Longitudinal control of automated guideway transit vehicles within platoons[END_REF], or fully ad hoc/opportunistic. Strings happen to instantiate most frequent highway/road driving regimes. We assume large sections without road-side units (V2I communications can be resorted to only for non-SC message passing). Numerous safety problems-prevention of accidents and fatalities-that arise with vehicular networks are open. SC communications serve to enforce hazard-free motions of vehicles. SC messages are defined in IEEE 802.11p, and similar to Cooperative Awareness Messages defined in ETSI ITS-G5. Deliveries of such messages and acknowledgements (acks) must be performed within known bounded (non-stochastic) delays, under worst-case conditions regarding channel contention and losses. Therefore, one must solve the MAC-level bounded channel access delay (BCAD) and the time-bounded message acknowledgment (TBMA) problems. Acceptable solutions shall achieve small time bounds. For example, with the MAC protocol presented in this paper, a vehicle member of a string travelling at 108 km/h would move by 27 cm while a SC message is being sent and delivered successfully, assuming no losses, and by 75 cm assuming 2 losses (see Subsection V.E.3).

Neither BCAD nor TBMA are solved with existing V2V communications standards, which are based on medium range omnidirectional communications, radio range (RR) in the order of 250 m, interference range (IR) in the order of 400 m, CSMA-CA at the MAC level, and the RTS/CTS scheme. On a crowded highway (1 vehicle every 12.5 m), 3 lanes each direction, any vehicle may experience interferences from up to 384 vehicles, yielding unacceptably high channel access delays. We speculate that there are no solutions to BCAD or to TBMA with medium range omnidirectional communications (see Section IV). Our rationale is to follow a divide-andconquer approach, addressing safety issues in strings (e.g., longitudinal control, string stability, prevention of rear-end collisions) separately from issues that arise with multilane maneuvers (lateral control, prevention of collisions in the course of, e.g., lane changes, lane merging, zipper merging). Moreover, we look for a MAC protocol whereby string-wide SC message dissemination can be performed reliably in very small time bounds.

Safety with autonomous and future automated vehicles rests on diversified redundancy, based on on-board (OB) robotics that achieves 360° and longitudinal line-of-sight (LOS) visibility, thanks to, e.g., radars, lidars, lasers, cameras, and 360° V2V communications. Diversified redundancy is also mandatory for achieving longitudinal LOS visibility in vehicular strings. Thus, in addition to OB robotics, longitudinal V2V communications are necessary. Since collisions can only occur among vehicles sufficiently close to each other, shortrange V2V communications should suffice. As for lateral short range V2V communications (out of the scope of this paper), power controlled MIMO solutions have been explored. We believe that optical communications are very promising for lateral short range SC V2V communications (on-going work to appear in forthcoming publications). The MAC protocol presented here is aimed at longitudinal short range SC V2V communications. This protocol could be the basis for novel (IEEE, ETSI) standards, while some other future standards would define optics-based protocols for short range lateral communications across strings (multilane clusters). Non-SC V2X communications will rest on existing standards, as well as on, e.g., LTE, WiFi, and 5G. Main contributions of this paper are specifications of BCAD, TBMA, and SWIFT, a deterministic directional MAC protocol that solves BCAD and TBMA altogether, along with analytical formulae of worst-case bounds for channel access, acknowledged message delivery, and string-wide message dissemination, in the presence of losses (messages and acks).

II. SYSTEM MODEL

Thanks to OB robotics, gaps between 2 contiguous vehicles (neighbors) are expected to be small, continuously monitored with rather good accuracy. Therefore, range/power controlled antennas can be considered, since the problem of computing a "good" antenna power level as a function of range can be easily solved (contrary to the general problem with omnidirectional communications). Let s qp (v) (resp., s pq (v)) stand for the spacing between neighbors Q and P, at velocity v, measured by Q (resp., P), meeting lower and upper bounds s min (v) and s max (v)-see Fig. 2. With fully automated driving, gaps commonly considered are in the order of 1 m at low speed (e.g., v = 10), of 10 m at high speed (e.g., v = 140), v in km/h. Rear-end collisions may occur in case of a "brick wall" condition (sudden stopping). The best objective in such a case is to minimize the number of vehicles involved in rear-end collisions. The cohort construct originates from this concern [START_REF] Lann | Cohorts and groups for safe and efficient autonomous driving on highways[END_REF], [START_REF] Lann | Integrated Safety and Efficiency in Intelligent Vehicular Networks: Issues and Novel Constructs[END_REF]. A smallest spacing S(v) > s max (v) is enforced between any 2 cohorts, such that a cohort head never collides with a cohort tail. For the same reason, a cohort shall comprise a limited number of members, denoted n, varying according to join and leave maneuvers, such that n ≤ n*(v). In strings, one can take advantage of SISO directional antennas. Every vehicle is equipped with a backward looking and a forward looking directional antenna, small beamwidth (e.g., 25°), short-range (e.g., up to 20 m), possibly steerable in order to accommodate lane curvatures. SC messages are exchanged as neighbor-to-neighbor (N2N) messages. They may carry all types of safety data, such as, e.g., "lane blocking ahead,", "new velocity set to 60 km/h", "move to left lane asap". A message received from a neighbor is acknowledged and forwarded to the opposite neighbor, if any. SC data carried in messages are short. Acks are piggybacked within messages. Consequently, N2N messages have a small length, of known largest value denoted ml, of highest transmission and processing time denoted θ. A N2N message is generated by a string member whenever posted a SC event (local condition, delivery of a SC V2V message). Thus, N2N message arrival laws are arbitrary. Since antenna lobes may encompass adjacent lanes, contention occurs among members of a given string as well as with nearby members of adjacent strings, thus the need for a MAC protocol. A cohort head or an isolated vehicle assigns itself rank 1. Insertion of vehicle Y behind some member ranked r leads to re-ranking: Y assigns itself rank r+1, and new Y's followers, if any, increment their previous ranks. Re-ranking (-1) is also performed in case some member leaves a cohort. Re-ranking rests on N2N messaging. Network partitioning (loss of a N2N link) leads to a physical partitioning of a cohort, a feature referred to as a split, i.e. creation of spacing S(v). Besides voluntary decisions, a split occurs when the number of losses experienced while transmitting a N2N message and its ack exceeds some parameter φ, as commonly considered with most protocols (e.g., TCP, HDLC).

String control has been mostly studied in control theory and by the robotics community. String stability (minimization of "shock wave" phenomena) is a good example [START_REF] Swaroop | String stability of interconnected systems[END_REF]. Adaptive Cruise Control (ACC) has known limitations. Higher string stability is achieved with Cooperative ACC (CACC), where a string leader broadcast V2V messages to tell string members what to do. However, V2V message losses and contention issues are ignored, with few exceptions. Also, data collected in platooning experiments show that it is inappropriate to rely on V2V broadcast from a lead vehicle [START_REF] Bergenhem | V2V communication quality: Measurements in a cooperative automotive platooning application[END_REF]. In fact, rather than shock waves mitigation, prevention seems preferable. This is doable, provided that cyber precedes physics, rather than the opposite-most roboticist approaches. For example, in [START_REF] Lann | Safety in vehicular networks-On the inevitability of short-range directional communications[END_REF], we have presented a distributed algorithm (Π) that solves the timebounded message dissemination problem in strings, assuming a MAC protocol other than SWIFT. Thanks to Π (thanks to SWIFT here), all string members are made aware of the occurrence of a SC event in split-second delays, prior to performing the corresponding physical maneuver, at the same UTC time. This is how shock waves can be eliminated.

III. BCAD AND TBMA IN STRINGS

Upstream (by decreasing ranks) and downstream (by increasing ranks) string-wide dissemination of N2N messages and acks need be considered, Under the CACC paradigm, only downstream dissemination is considered (from head to tail). This does not match common SC scenarios where some vehicle (e.g., an ambulance) arriving from behind a string broadcasts a V2V emergency message which is received by a string tail, not heard by a string head (out of V2V radio range or loss). In IEEE 1609, messages are assigned priorities. In our model, priorities can be integers or deadlines. Messages are scheduled according to highest-priority-first in the former case, earliest-deadline-first in the latter case. Let M stand for a message of highest priority, ta(M) be the time at which M reaches rank 1 in a waiting queue, and ts(M) be the time at which a channel access for transmitting M is collision-free. -Arbitrary sets of vehicles circulate in lanes adjacent to k.

-Every vehicle is equipped with a front-looking and a back-looking short-range directional antenna.

-GNSS space coordinates may be inaccurate.

-N2N communications over η radio channels.

-N2N messages are of highest length ml.

-Every vehicle may attempt a message transmission anytime, upstream and/or downstream.

-Antenna lobes may encompass adjacent lanes.

-Concurrent channel accesses performed by Γ's members as well as by nearby vehicles in lanes k+1 and k-1 result in destructive collisions.

-Collisions are not detected by active vehicles (senders); they are not detected uniformly by non-active vehicles.

-Unreliable communications (messages/acks can be lost).

Prescribed properties

For every N2N message M transmitted by a member of Γ:

-Timeliness: Under worst-case contention conditions, a channel access attempt succeeds in λ time units. In the absence of losses, M is delivered in λ+θ time units and M's delivery is acknowledged in 2λ time units.

-Symmetry: Bound λ holds for upstream and downstream communications.

-Safety related acceptability: Distance travelled during λ+θ at high velocities is an order of magnitude smaller than average vehicle size. Let λ stand for the highest value of ts(M) -ta(M) in worstcase conditions (λ does not include M's transmission duration). Safety being at stake, λ must be known in advance (prior to deploying VANETs). It follows that λ should not depend on n. Since n may end up being large, this is also an imperative condition for meeting the Timeliness requirement optimally. A N2N communication involves exactly 2 members. Hence, ARQ (automatic repeat request) protocols can be considered, and unique names can be assigned to N2N messages, in the form of id x = {rank of sender X, sequence number}, used for acks. Let Λ(κ) stand for the highest delay elapsed while transmitting a N2N message and receiving an ack, in the presence of κ losses, κ < φ (no string split). Bounds λ and Λ(κ) shall hold whatever the transmission direction (the Symmetry property), and their numerical values shall be small enough for meeting the Safety related acceptability requirement.

Informal specifications of BCAD and TBMA are given in Tables I and II, respectively. Moreover, since string control implies string-wide message dissemination, we look for a MAC protocol that minimizes ∆ r (n,f), the worst-case delay incurred with a string-wide message dissemination in the presence of f losses, r standing for the initiator's rank. That MAC protocol shall meet string-wide requirements identical to those stated for BCAD and TBMA, namely Timeliness and Symmetry (∆ r (n,f) holds for upstream and disseminations), and Safety related acceptability: distance travelled during ∆ r (n,f) at high velocities smaller than average vehicle size. BCAD and TBMA differ from traditional MAC problems. Furthermore, since they do not minimize ∆ r (n,f)contention issues are addressed irrespective of what messages are used for-traditional MAC protocols cannot be considered.

IV. RELATED WORK

A. Reliable V2V Communications

According to current standards, V2V omnidirectional communications in broadcast mode are not acknowledged, so as to avoid the "broadcast storm" problem [START_REF] Ni | The broadcast storm problem in a mobile ad hoc network[END_REF]. Consequently, failed deliveries go unnoticed, which is not acceptable. ARQ protocols have been proposed for broadcast/multicast/unicast modes [START_REF] Ros | Acknowledgment-based broadcast protocol for reliable and efficient data dissemination in vehicular ad hoc networks[END_REF]. However, reliance on such protocols may well be inappropriate for SC messages, given that loss ratios may be high [START_REF] Karlsson | Field measurements of IEEE 802.11p communication in NLOS environments for a platooning application[END_REF]. Consider messages/acks exchanged for coordinating a lane change. An acceptable time budget for striking an intervehicular agreement-a cyber phase precedes the SC physical change maneuver-would be in the order of 400 ms (10 m at 90 km/h). Since radio links may be garbled much longer than 400 ms, resending messages and/or acks is useless.

B. MAC Protocols 1) Omnidirectional Communications

With MAC protocols based on variations of CSMA-CA, collisions are neither avoided nor resolved deterministically. It follows that MAC level delays are probabilistic quadratic functions in the number of contenders, which number can be very high under realistic worst-case assumptions, e.g. hundreds of contenders, which is not uncommon with large multilane highways and dense traffic [START_REF] Tang | Real-time misbehavior detection in IEEE 802.11-based wireless networks: An analytical approach[END_REF]. Moreover, since these protocols do not induce bi-directional channel access orderings that would match bi-directional string member ranking, they fail to achieve the String-wide symmetry property. MAC protocols based on reservations, on accurate space coordinates (e.g., STDMA, SDMA, and LCA), or situational awareness, have known weaknesses (reliance on accurate GNSS space coordinates, in particular), not to be detailed here. As for TDMA protocols, we refer the interested reader to [START_REF] Hadded | TDMA-Based MAC protocols for vehicular ad hoc networks: A survey, qualitative analysis, and open research issues[END_REF].

2) Directional Communications

MAC protocols which rest on approaches similar to those contemplated for omnidirectional communications, e.g., [START_REF] Ramanathan | Ad hoc networking with directional antennas: A complete system solution[END_REF], [START_REF] Shihab | A distributed asynchronous directionalto-directional MAC protocol for wireless ad hoc networks[END_REF], [START_REF] Korakis | A MAC protocol for full exploitation of directional antennas in ad hoc wireless networks[END_REF], [START_REF] Choudhury | On designing MAC protocols for wireless networks using directional antennas[END_REF], CSMA-CA in particular, cannot be considered. A similar conclusion applies to adaptive range or power controlled directional MAC protocols such as, e.g., [START_REF] Bazan | A survey on MAC protocols for wireless adhoc networks with beamforming antennas[END_REF], [START_REF] Takai | Adaptive range control using directional antennas in mobile ad hoc networks[END_REF], [START_REF] Chen | A range-adaptive directional MAC protocol for wireless ad hoc networks with smart antennas[END_REF]. Deafness is one of the major difficulties [START_REF] Choudhury | Deafness: A MAC problem in ad hoc networks when using directional antennas[END_REF]. This problem can be ignored with strings since neighbors have their sending/receiving antennas always aligned correctly (limited steering may be helpful). Calculations of optimal transmission power are notoriously difficult in general settings. In strings, they can be reasonably accurate since transmission power is adjusted according to spacing with targeted neighbor. Published directional TDMA protocols have weaknesses similar to those relative to omnidirectional TDMA protocols. Consider losses for example. In case an ack is not received, a retransmission is attempted after y slots, y = 0 in the best case (targeted receiver owns the slot which follows sender's slot), or y = n in the worst case (targeted receiver owns the slot which precedes sender's slot). Λ(κ) would be neither unique nor symmetrical. Moreover, since the problem of how to adjust a TDMA frame accurately enough (no wasted slots) when n varies is still open, bounds λ achieved by such protocols cannot be optimal.

The MAC protocol presented here rests on alternated directional interference-free communications-thanks to shortrange power controlled antennas, and synchronous time slotted channels, thus the name SWIFT, which stands for Synchronous Wireless Interference Free Transmissions. In [START_REF] Lann | Fast distributed agreements and safety-critical scenarios in VANETs[END_REF], we show how SWIFT is used to perform fast SC distributed agreements within strings. Inter-vehicular agreements are necessary (atop dissemination) due to the existence of concurrent, possibly conflicting, SC events. Numerous concurrency issues related to safety have not been addressed yet.

Problem assumptions -Up to φ losses (message, ack) may be experienced over a N2N link, without leading to a string split.

-Others same as for BCAD. Prescribed properties For every message transmitted over a N2N link: -Timeliness: The additional latency due to κ losses, κ ≤ φ, is bounded, equal to Λ(κ) time units.

-Symmetry: Λ(κ) holds for upstream and downstream communications.

-Safety related acceptability: Distance travelled during Λ(φ) at high velocities is an order of magnitude smaller than average vehicle size.

V. THE SWIFT MAC PROTOCOL

A. Design Assumptions

Antennas technology being out of the scope of this paper, we adopt a simple linear model for radio and interference ranges, where IR < ρ RR, real ρ > 1. Parameter ρ can be computed out of SINR models [START_REF] Gupta | The capacity of wireless networks[END_REF] or more sophisticated models [START_REF] Ogierman | Competitive MAC under adversarial SINR[END_REF], [START_REF] Kandukuri | Optimal power control in interferencelimited fading wireless channels with outage-probability specifications[END_REF]. Consider neighbors P and Q again, Q the transmitter (Fig. 2). Ideally, it suffices to have RR qp = s qp (v). Given that the received signal power should be above the minimum sensitivity level, and power control can only be approximate, one must write: s qp (v) < RR qp < αs qp (v), real α > 1. Parameters ρ and α may be assigned stochastic or nonstochastic (e.g., the disc model) values. Performance figures established for hypothesized values do not hold in case of violations. How is performance impacted? This issue is barely addressed. Here, we follow a deterministic approach where IR qp < ρ αs qp (v). (Violations of valued ρ and α are addressed in Subsection V.G.6.) String members that are at least IR away from each other can perform nondestructive concurrent transmissions in the same direction. String heads (resp., tails) do not perform upstream (resp., downstream) communications. Since inter-string gaps S(v) are much larger than s max (v), communications conducted within different strings in the same lane do not interfere with each other. Radio channel 1 (resp., 2) is to be used by vehicles circulating in odd (resp., even) numbered lanes.

B. Principles of SWIFT

Let integer h stand for the highest number of vehicles within IR of each other, transmitter included. A string comprises ω = n/h groups, last group possibly comprising less than h members. We consider a time slotted channel, every slot of duration θ. A SWIFT frame comprises 2h slots. Every member owns 2 slots in every frame, one slot for each direction. Members assigned the same rank modulo h transmit in the same slots. Let T* stand for some recurring UTC time boundary such as, e.g., the start time of every UTC second, of every even numbered UTC second, of every UTC minute. A SWIFT round is comprised between 2 successive occurrences of T*. A round lasts U time units, encompassing F frames, such that F = U/2hθ. For example, assuming U = 1 s, h = 4, and θ = 1 ms, we have F = 125. In case U and θ would be such that F ≠ U/2hθ, θ could be augmented by less than θ/F, since at most 2(h-1) slots need be amortized so as to have F = U/2hθ. Let T x = T*+(x-1)2hθ, x ∈ [1, F], stand for the start time of the x th frame in a round. Slots comprised between T x and T x +(h+1)θ are used for downstream transmissions, and slots comprised between T x +(h+1)θ and T x +2hθ are used for upstream transmissions. Downstream slots allocated to member ranked r th start at UTC times denoted dt x (r), and upstream slots owned by that member start at UTC times denoted ut x (r). Let us write i = r-1 mod h and j = h-i. We have:

dt x (r) = T x + iθ, for r ≠ n (string tail), (1)
ut x (r) = T x + (h+j mod h)θ, for r ≠ 1 (string head). ( 2)

Fig. 1 illustrates how SWIFT works, with h = 3. B, L and P transmit at the same UTC times, ditto for their respective successors θ later, and so on. In the absence of losses, a message of highest priority crosses h hops every 2h hops. Times dt x and ut x are owned by ω or ω-1 members. Thus, ω or ω-1 N2N messages are transmitted concurrently within a frame, collision-free, in the same direction. Acks for messages sent in one direction are piggybacked on messages sent in the opposite direction. See Fig. 1 where message M 4,b issued by B is acknowledged by L. Priority inheritance [START_REF] Sha | Priority inheritance protocols: An approach to real-time synchronization[END_REF] is exercised. A message of priority u 1 which carries an ack for a message M of priority u 2 > u 1 has its priority raised to u 2 until it reaches the sender of M. See also the case with B at dt x+1 (.), which forwards M 3,s received from its predecessor rather than its own message (pending) of lower priority.

Unlike conventional TDMA frames, SWIFT frames need not be reorganized when n changes in order to achieve highest channel utilization ratios. Stated differently, the start times of slots allocated to a member of a given rank need not be changed when n changes. Similarly, the durations of a SWIFT frame, of a round, do not depend on n. These are valuable properties for opportunistic/ad hoc vehicular strings, be they long-lived or short-lived. The rationale for having T* as a recurrent UTC time referential is double. New members joining a string must be able to synchronize with existing members. They can do so in no more than U time units. Moreover, OB systems may be oblivious. They can resynchronize on the next upcoming T*.

C. Informal Specification of SWIFT

SWIFT pseudo-code in Table IV is given for member R, rank r, n > 1, F > 1. R manages 2 message waiting queues, denoted W d and W u , one for each neighbor. State idle is entered when an OB system is restarted (e.g. due to a transitory failure) or when a member assigns itself a new rank (when string membership is modified). Symbol ← is the store symbol. State active is entered at the beginning of every round (times T*). Time interval counters C dt and C ut , and timers Y dt and Y ut , serve to signal the start times of R's slots in the first frame of every round. Timers Z dt and Z ut serve to signal the start times of R's slots in every subsequent frame. Counter CF stores the number of frames left until reaching the end of the current round. Events are defined as follows:

• event e 1 : T* read on on-board clock (new round)

• event e 2 : timer Y dt awakes; event e 3 : timer Y ut awakes

• event e 4 : timer Z dt awakes; event e 5 : timer Z ut awakes

• event e 6 : synchronization is lost When R receives a message M\id n issued by its predecessor (resp., successor), M\id n is stored in W d (resp., W u ), and then relayed to its successor (resp., predecessor). When R generates a message M\id r , M\id r is stored in W d and W u (no W u , for r = 1, no W d for r = n). In Table IV, messages ranked 1 st in W d and W u are denoted M r = {M, id r , id n }. In case there is no message pending and no ack to be returned, message M r is empty.

D. Worst-Case Conditions

Let vl stand for vehicle length and vsl(v) stand for the size of a vehicular slot (on asphalt) at velocity v, defined as follows: vsl(v) = vl + spacing(v) with predecessor. Smallest vl is denoted vl 0 . Consider Fig. 2, where P precedes Q. When about to transmit a message to P, Q adjusts the power of its front-looking antenna according to s qp (v). (Given the modest values of RR, side and back lobes are not shown.) When string stability is achieved, members move at comparable velocities, i.e. all inter-neighbor gaps are approximately equal to s qp (v). Under worst-case conditions, the spacing between P and Q is s max (v), and spacing between vehicles ahead of P is s min (v), yielding smallest vehicular slots vsl 0 (v) = vl 0 + s min (v). Recall that IR < ρ αs qp (v). Let z stand for the highest number of vehicles which may experience interferences due to transmitter Q, i.e. the highest number of vehicular slots vsl 0 (v) included in (ρα-1) s max (v), that is:

z = (ρα-1) s max (v)/(vl 0 +s min (v)),
and h = z+1 (h includes the transmitter).

Highest authorized velocities v* must be considered for quantifying h. The difference s max (v)-s min (v) is small with automated vehicles. For the sake of illustration, let us assume the following numerical figures: vl 0 ≈ 5, α ≈ 2, ρ ≈ 1.5 (according to current V2V standards). Additionally, let us assume s max (v*) = s min (v*) = 10, and s max (v*) = 12, s min (v*) = 8. Notations:

-n: number of string members -s qp (v): spacing between neighbors Q and P at velocity v η: number of radio channels -ml: highest N2N message length, framing included θ: channel slot duration (transmission of longest N2N message, guard times and CRC processing included) -RR: radio range; IR: interference range; IR = ρ RR λ: worst-case channel access delay φ: highest number of losses that may be experienced while transmitting and acknowledging a message across a N2N link without incurring a cohort split -Λ(κ): additional latency due to κ losses over a N2N link -f: number of losses that may be experienced while disseminating a message throughout a string -∆(n,f): worst-case end-to-end string-wide dissemination delay in the presence of f losses -∆ r (n,f): ∆(n,f) when member ranked r th is the initiator -T*: start time (UTC) of a round ω = n/h -F = U/2hθ (number of frames in a round) Initialization %counters and timers are uploaded% C dt ← iθ; C ut ← (h+j mod h)θ; % Eq. ( 1) and Eq. ( 2 In both cases, one finds h = 3. With more conservative values for ρα, one would have h = 4, the case shown in Fig. 2. Members Q and K can transmit simultaneously successfully.

)% Y dt ← C dt ; Y ut ← C ut ; Z dt ← 2hθ; Z ut ← 2hθ; switch to idle -------------------------------------------------------------------------------------------------------- idle \

E. Properties Relative to BCAD and TBMA

SWIFT is simple, so are the proofs for collision freedom. (Proofs are by contradiction, omitted due to space limitations.)

1) Timeliness

Consider a N2N message of highest priority. Worst-case delay λ(h) for a channel access is the largest latency until current time reads dt x (r) or ut x (r), i.e. 2hθ-see Eq. ( 1) and Eq. ( 2). In the presence of κ losses, κ round trips across h neighbors are lost. Thus, worst-case bounds are as follows:

-Channel access delay λ(h) = 2hθ -N2N message delivery delay (to neighbor) = λ(h) + θ -Round trip N2N message and ack delivery delay = 2λ(h) -Additional latency due to κ losses over a link: Λ(κ) = 2κhθ

2) Symmetry By construction, SWIFT handles upstream and downstream communications identically. Therefore, bounds λ(h) and Λ(κ) hold for both directions.

3) Safety related acceptability

Variables that appear in bounds must be valued, lengths in meters and times in ms. Let us choose the following realistic figures: ml < 5 Kbits, processing delays < 0.150, channel throughput = 6 Mbits/s. Assume θ = 1 and h = 4 (conservative values). With SWIFT, distances travelled during λ(h)+θ and λ(h)+θ+Λ(f) can be significantly smaller than vehicle sizes, even at high velocities. With our numerical figures, a vehicle travelling at 108 km/h would move by 27 cm by the time a message is delivered, assuming no losses, by 75 cm assuming 2 losses. Observe that λ(h)+θ is much smaller than the 100 ms bound commonly stipulated (not proved) for SC message deliveries, assuming no losses.

4) Channel utilization efficiency and spatial reuse

Channel utilization efficiency γ matters. Assume that every member has a message pending. Let σ stand for the average slot occupancy ratio. When 1 < n < h, γ = σn/h and γ = σ when n ≥ h (every slot is utilized). If n = ωh, every slot is utilized by ω members. If n < ωh, up to h-1 slots would be utilized by ω-1 members. Thanks to spatial reuse, actual channel throughput can be as high as ω times the nominal channel throughput.

F. Properties Relative to String-Wide Dissemination

De facto, in addition to being a MAC protocol, SWIFT is an algorithm tailored for performing fast reliable string-wide message dissemination. It turns out that bounds ∆ r (n,f) achieved by SWIFT are smaller than bounds established for algorithm Π [START_REF] Lann | Safety in vehicular networks-On the inevitability of short-range directional communications[END_REF]. Bound denoted ∆(n,f) is ∆ r (n,f) when a dissemination is initiated by a string head or a string tail. Since up to φ losses may be experienced over a N2N link, without leading to a string split, we have 0 ≤ f < (n-1) φ.

1) Timeliness and symmetry

Integer π(r) = max {r-1, n-r} is the longest path (in hops) between a tail or a head and a member ranked r th . A series of h

G. Assessment of Assumptions 1) Number of channels is η = 2

The adjacent channel interference problem is a minor concern with short-range power controlled directional antennas operating on frequency bands sufficiently apart from each other. SWIFT works also with η = 1, in which case Γ's members are assigned channel slots or frames of the same parity as that of lane k, and vehicles in lanes adjacent to k are assigned channel slots or frames of opposite parity. Strings in adjacent lanes may have different velocities, hence different inter-neighbor gaps. This does not invalidate our calculation of h, which is given for worst-case conditions, i.e. highest gap between a sender and its predecessor (it suffices to assume an upper bound on legal velocities, easily enforced by automated vehicles), and smallest gaps for other preceding vehicles.

2) Lobes of directional antennas span adjacent lanes

This assumption has led to choosing η = 2. In case lobes would also span lanes adjacent to adjacent lanes, the design of SWIFT would remain unchanged, with η > 2.

3) Up to φ losses over a N2N link A string split is undertaken in case φ is violated. Note that φ may be assigned values dynamically via string-wide dissemination, according to observed frequency of violations.

4) Safety messages have bounded length ml

Non-SC messages larger than ml are fragmented and fragments reassembled à la TCP/IP. They are assigned lowest priorities. Likely, transmissions of SC messages are not needed at frequencies as high as 1/λ(h) or 1/Λ(φ). Thus, there should be plenty of channel time available for non-SC messages.

5) Channel/lane mapping is known

Lane level positioning is performed by OB robotics capabilities. Knowledge of lane numbering and channel/lane mapping is available via emaps, via cloudlets in the future. Moreover, neighbors in lane number k may exchange N2N beacons carrying k more or less periodically, so as to cope with vehicles that would get confused about their lane number.

6) IR < ρα RR

At times, RR or IR may be higher than expected, in which case message collisions, hence losses, would occur. This would lead to string splits initiated in no more than Λ(φ). Bounds achieved by SWIFT hold despite such violations (the number of members in resulting strings gets smaller). Safety is preserved, at the expense of (temporary) sub-optimal asphalt occupancy (s qp (v) replaced by S(v)). For minimizing such string split occurrences, conservative values can be chosen for ρα. With ρα = 4 (rather than 3), we still have h = 3 assuming s max (v*) = s min (v*) = 10, and h = 4 assuming s max (v*) = 12 and s min (v*) = 8. Highest values for h are computed for worst-case conditions, and assuming smallest vehicle sizes. In realistic settings, h's values smaller than 4 should suffice.

7) Channel slotting aligned with UTC

A UTC aligned slotted channel can be built, inter-slot intervals of size 2τ, with OB clocks of inaccuracy and instability smaller than τ. Affordable clocks achieve accuracy and stability figures in the order of 1x10 -7 and 1x10 -6 , achieving τ in the order of 1 µsec/minute, which permits to cope with 1 minute long (d = 60) GNSS outages. With θ in the order of 1 ms, slotting overhead is quite marginal.

VI. PERSPECTIVES

The future of autonomous/automated driving depends on whether safety issues are addressed rigorously, and at which pace. As for SC communications, deterministic MAC protocols are essential. SWIFT is an example. Other algorithmic problems related to safety need be investigated. For example, can we achieve instantaneous renaming without infringing on privacy? Is there an algorithmic solution to the following problem: fully automated zipper merging at high velocities?

  Bound n*(v) is an inverse function of v, and v.n*(v) is bounded by b. For example, with b = 2,200, n*(15) = 146 and n*(108) = 20. In the sequel, string and cohort are used interchangeably.

Fig. 1 .

 1 Fig. 1. Principles of SWIFT illustrated-View of the x th frame

Fig. 2 .

 2 Fig. 2. RR, IR, and interference-free groups consecutive transmissions are conducted every 2hθ, in any given direction. Given that the highest number of series needed to encompass π(r) hops is π(r)/h, we have: ∆ r (n,f) ≤ 2hθ {f+1+ π(r)/h}. ∆(n,f) holds whenever r = 1 or r = n, i.e. π(r) = n-1. Obviously, bounds ∆(n,f) and ∆ r (n,f) hold for both directions.

2 )

 2 Safety related acceptability Assuming n = 20 and f = 6, one finds ∆(20,6) ≤ 96. When the initiator is ranked 8 th , ∆ 8 (20,6) ≤ 80. Assume now that every message must be repeated at most once (φ = 1). No more than f = 19 losses may occur. Therefore, ∆(20,19) ≤ 200. In Section II, bound b > v.n*(v) has been introduced, illustrated with b = 2,200, which yields n*(108) ≤ 20. In less than 200 ms (n = 20), less than 6 m are travelled at 108 km/h. The safety related acceptability requirement is met. If h = 3, bounds given above would be reduced by 12 ms. Note that comparable (stochastic) bounds cannot be achieved with existing V2V standards, even under moderate contention conditions.

TABLE I .

 I

INFORMAL SPECIFICATION OF BCAD Problem assumptions -Set Γ of n vehicles of various sizes circulating in lane k at velocity v, forming a string, n ≤ n*(v).

TABLE II .

 II INFORMAL SPECIFICATION OF TBMA

TABLE III .

 III DESIGN ASSUMPTIONS

TABLE IV .

 IV STATE/EVENT TRANSITIONS IN SWIFT