Antonio Fernández Anta

Alessia Milani
email: alessia.milani@lip6.fr

Miguel A Mosteiro
email: mosteiro@cs.rutgers.edu

Shmuel Zaks
email: zaks@cs.technion.ac.il

Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony ⋆

The topic of this paper is the study of Information Dissemination in Mobile Ad-hoc Networks by means of deterministic protocols. We characterize the connectivity resulting from the movement, from failures and from the fact that nodes may join the computation at different times with two values, α and β, so that, within α time slots, some node that has the information must be connected to some node without it for at least β time slots. The protocols studied are classified into three classes: oblivious (the transmission schedule of a node is only a function of its ID), quasi-oblivious (the transmission schedule may also depend on a global time), and adaptive. The main contribution of this work concerns negative results. Contrasting the lower and upper bounds derived, interesting complexity gaps among protocolclasses are observed. More precisely, in order to guarantee any progress towards solving the problem, it is shown that β must be at least n -1 in general, but that β ∈ Ω(n 2 / log n) if an oblivious protocol is used. Since quasi-oblivious protocols can guarantee progress with β ∈ O(n), this represents a significant gap, almost linear in β, between oblivious and quasi-oblivious protocols. Regarding the time to complete the dissemination, a lower bound of Ω(nα + n 3 / log n) is proved for oblivious protocols, which is tight up to a polylogarithmic factor because a constructive O(nα + n 3 log n) upper bound exists for the same class. It is also proved that adaptive protocols require Ω(nα + n 2 ), which is optimal given that a matching upper bound can be proved for quasi-oblivious protocols. These results show that the gap in time complexity between oblivious and quasioblivious, and hence adaptive, protocols is almost linear. This gap is what we call the profit of global synchrony, since it represents the gain the network obtains from global synchrony with respect to not having it.

Introduction

A Mobile Ad-hoc Network (aka MANET) is a set of mobile nodes which communicate over a multihop radio network, without relying on a stable infrastructure. In these networks, nodes are usually battery-operated devices that can communicate via radio with other devices that are in range. Due to unreliable power supply and mobility, nodes may have a continuously changing set of neighbors in that range. This dynamic nature makes it challenging to solve even the simplest communication problems in general. Hence, proposed protocols often have strong synchronization and stability requirements, like having a stable connected network for long enough time.

Current trends in networking-architecture developments, like delay and disruption tolerant networks, and opportunistic networking [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF][START_REF] Pelusi | Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[END_REF], aim to deal with the disconnections that naturally and frequently arise in wireless environments. Their objective is to allow communication in dynamic networks, like a MANET, even if a route between sender and receiver never exists in the network. The result is that multi-hop communication is provided through opportunistic communication, in which the online route of a message is followed one link at a time, as links in the route become available. While the next link is not available, the message is held in a node. With opportunistic communication, strong connectivity requirements are no longer needed. Furthermore, in some cases mobility is the key to allow communication (e.g., consider two disconnected static nodes, where communication between them is provided by a device that, due to mobility, sometimes is in range of one and sometimes of the other).

In this paper, we formally define a particular class of MANET which is suited for opportunistic communication, and which we call potentially epidemic. A MANET is potentially epidemic if the changes in the communication topology are such that an online route exists among any two nodes that wish to communicate.

The network is potentially epidemic because the actual propagation of the information on the online routes, and then the possibility for a node to affect another node, depends on the stability of each communication links of the online route.

In this context, we define and study the deterministic solvability of a problem that we call Dissemination. In this problem, at a given time a source node holds an information that must be disseminated to a given set of nodes belonging to the MANET. The nodes elected to eventually receive the information are the ones that satisfy a given predicate. Depending on this predicate, the Dissemination problem can instantiate most of the common communication problems in distributed systems, such as Broadcast, Multicast, Geocast, Routing, etc.

In particular, we determine assumptions on link stability and speed of nodes under which a distributed deterministic protocol exists that solves Dissemination in potentially epidemic networks. Moreover, we relate the time complexity of the solution to the speed of movement and to the information that protocols may use.

The Dissemination Problem

We study the problem of disseminating a piece of information, initially held by a distinguished source node, to all nodes of a given set in the network. Formally, Definition 1. Given a MANET formed by a set V of n nodes, let P be a predicate on V and s ∈ V a node that holds a piece of information I at time t 1 (s is the source of dissemination). The Dissemination problem consists of distributing I to the set of nodes V P = {x ∈ V :: P(x)}. A node that has received I is termed covered, and otherwise it is uncovered. The Dissemination problem is solved at time slot t 2 ≥ t 1 if, for every node v ∈ V P , v is covered by time slot t 2 .

The Dissemination problem abstracts several common problems in distributed systems. E.g. Broadcast, Multicast, Geocast, Routing etc., are all instances of this problem for a particular predicate P. In order to prove lower bounds, we will use one of these instances: the Geocast problem. The predicate P for Geocast is P(x) = true if and only if, at time t 1 , x is up and running, and it is located within a parametric distance d > 0 (called eccentricity) from the position of the source node at that time.

Model

We consider a MANET formed by a set V of n mobile nodes deployed in R 2 , where no pair of nodes can occupy the same point in the plane simultaneously. It is assumed that each node has data-processing and radio-communication capabilities, and a unique identificator number (ID) in [n] {1, . . . , n}.

Time. Each node is equipped with a clock that ticks at the same uniform rate ρ but, given the asynchronous activation, the clocks of different nodes may start at different times. A time interval of duration 1/ρ is long enough to transmit (resp. receive) a message. Computations in each node are assumed to take no time. Starting from a time instant used as reference, the global time is slotted as a sequence of time intervals or time slots 1, 2, . . . , where slot i > 0 corresponds to the time interval [(i -1)/ρ, i/ρ). Without loss of generality [START_REF] Roberts | Aloha packet system with and without slots and capture[END_REF] all node's ticks are assumed to be in phase with this global tick.

Node Activation. We say that a node is active if it is powered up, and inactive otherwise. It is assumed that, due to lack of power supply or other unwanted events that we call failures, active nodes may become inactive. Likewise, due also to arbitrary events such as replenishing their batteries, nodes may be re-activated. We call the temporal sequence of activation and failures of a node the activation schedule. The activation schedule for each node is assumed to be chosen by an adversary, in order to obtain worst-case bounds. Most of the lower-bound arguments included in this paper hold, even if all nodes are activated simultaneously and never fail (which readily provide a global time), making the results obtained stronger.

We assume that a node is activated in the boundary between two consecutive time slots. If a node is activated between slots t -1 and t we say that it is activated at slot t, and it is active in that slot. Upon activation, a node immediately starts running from scratch an algorithm previously stored in its hardware, but no other information or status is preserved while a node is inactive. Consequently, it is possible that a covered node does not hold the information I, because it has been inactive after receiving it. To distinguish a covered node that does not hold the information from one that holds it, we introduce the following additional terminology: we say that a node p is informed at a given time t if it holds the information I at time t, otherwise p is said to be uninformed.

Radio Communication.

Nodes communicate via a collision-prone single radio channel. A node v can receive a transmission of another node u in time slot t only if their distance is at most the range of transmission r during the whole slot t. The range of transmission is assumed to be the same for all nodes and all time slots. If two nodes u and v are separated by a distance at most r, we say that they are neighbors. In this paper, no collision detection mechanism is assumed, and a node cannot receive and transmit at the same time slot. Therefore, an active node u receives a transmission from a neighboring node v at time slot j if and only if v is the only node in u's neighborhood transmitting at time slot j. Also, a node cannot distinguish between a collision and no transmission. In general, we say that a node v ∈ V ′ transmits uniquely among the nodes of set V ′ ⊆ V in a slot t if it is the only node in V ′ that transmits in t.

Link stability. We assume that nodes may move on the plane. Thus, the topology of the network is time dependent. For simplicity, we assume that the topology only changes in the boundaries between time slots. Then, at time slot t nodes u and v are connected by a link in the network topology iff they are neighbors during the whole slot t. An online route between two nodes u and v is a path u = w 0 , w 1 , . . . , w k = v and a sequence of time slots t 1 < t 2 < • • • < t k such that the network has a link between w i-1 and w i at time slot t i . Observe that in order to be able to solve an instance of Dissemination, it is necessary that the network is potentially epidemic. I.e. after the initial time t 1 , there is an online route from the source s to every node in V P . However, as argued in [START_REF] Clementi | Communication in dynamic radio networks[END_REF], worst-case adversarial choice of topologies for a dynamic network precludes any deterministic protocol from completing Broadcast, even if connectivity is guaranteed. Note that Broadcast is an instance of Dissemination, and that if there is connectivity then there are online routes between all nodes. Thus, the property that the network is potentially epidemic as described is not sufficient to solve Dissemination, and further limitations to the adversarial movement and activation schedule are in order. While respecting a bound on the maximum speed v max , which is a parameter, the adversarial movement and activation schedule is limited by the following connectivity property: Definition 2. Given a Mobile Ad-hoc Network, an instance of the Dissemination problem that starts at time t 1 , and two integers α ≥ 0 and β ≥ 0, the network is (α, β)connected if, for every time slot t ≥ t 1 at which the problem has not yet been solved, there is a time slot t ′ such that the following conditions hold:

-the intersection of time intervals [t, t + α) and [t ′ , t ′ + β) is not empty, and -there is a pair of nodes p, p ′ , such that at t ′ p is informed and p ′ is uncovered, and they are active and neighbors the whole time interval

[t ′ , t ′ + β).
It is of the utmost importance to notice that (α, β)-connectivity is a characterization that applies to any model of dynamic network, given that for any mobility and activation schedule, and any pair of nodes, there is a minimum time they are connected (even if that time is 0) and a maximum time they are disconnected (even if that time is very large). Thus, any dynamic network model used to study the Dissemination problem has its own α and β values.

Due to the same argument, (α, β)-connectivity does not guarantee by itself that the network is epidemic (i.e. that the information is eventually disseminated); instead, an (α, β)-connected network is only potentially epidemic. Consider for instance the source node. Thanks to the (α, β)-connectivity, at most every α slots, the source s is connected to other nodes of the network for at least β time slots. But, we have progress only if the protocol to solve Dissemination is able to use the β slots of connectivity to cover some uncovered node. As a consequence of the above discussed, impossibility results only restrict β, whereas α only constrains the running time, as it is shown in this paper.

Protocols for Dissemination

We consider distributed deterministic protocols, i.e., we assume that each node in the network is preloaded with its own and possibly different deterministic algorithm that defines a schedule of transmissions for it. Even if a transmission is scheduled for a given node at a given time, that node will not transmit if it is uninformed.

Following the literature on various communication primitives [START_REF] Kowalski | On selection problem in radio networks[END_REF][START_REF] Kowalski | Time complexity of radio broadcasting: Adaptiveness vs. obliviousness and randomization vs. determinism[END_REF], a protocol is called oblivious if, at each node, the algorithm's decision on whether or not to schedule a transmission at a given time slot depends only on the identifier of the node, and on the number of time slots that the node has been active. Whereas, if no restriction is put on the information that a node may use to decide its communication schedule, the protocol is called adaptive. Additionally, in this paper, we distinguish a third class of protocols that we call quasi-oblivious. In a quasi-oblivious protocol the sequence of scheduled transmissions of a node depends only on its ID and a global time. Quasioblivious protocols have sometimes been called oblivious, since the model assumed simultaneous activation, and hence a global time was readily available. However we prefer to make the difference explicit, as done in [START_REF] Peleg | Time-efficient broadcast in radio networks[END_REF], because we found a drastic gap between this class and fully oblivious protocols.

Previous Work

A survey of the vast literature related to Dissemination is beyond the scope of this article. We overview in this section the most relevant previous work. Additionally, a review of relevant related work for static and dynamic networks beyond MANETs can be found in [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF].

The Dissemination problem abstracts several common problems in Radio Networks. When some number 1 ≤ k ≤ n of active nodes hold an information that must be disseminated to all nodes in the network, the problem is called k-Selection [START_REF] Kowalski | On selection problem in radio networks[END_REF] or Manyto-all [START_REF] Chlebus | On many-to-many communication in packet radio networks[END_REF]. If k = 1 the problem is called Broadcast [START_REF] Bar-Yehuda | On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization[END_REF][START_REF] Kushilevitz | An Ω(D log(N/D)) lower bound for broadcast in radio networks[END_REF], whereas if k = n the problem is known as Gossiping [START_REF] Chlebus | Oblivious gossiping in ad-hoc radio networks[END_REF][START_REF] Farach-Colton | Sensor network gossiping or how to break the broadcast lower bound[END_REF]. Upper bounds for these problems in mobile networks may be used for Dissemination, and even those for static networks may apply if the movement of nodes does not preclude the algorithm from completing the task (e.g., round-robin). On the other hand, if only the subset of k nodes have to receive the information, the problem is known as Multicast [START_REF] Chlebus | On many-to-many communication in packet radio networks[END_REF][START_REF] Gasieniec | Deterministic m2m multicast in radio networks[END_REF], and if only nodes initially located at a parametric distance from the source node must receive the information the problem is called Geocast [START_REF] Jinag | A review of geocasting protocols for a mobile ad hoc network[END_REF], defined in Section 1.1.

Deterministic solutions for the problems above have been studied for MANETs. Their correctness rely on strong synchronization or stability assumptions. In [START_REF] Mohsin | Reliable broadcast in wireless mobile ad hoc networks[END_REF], deterministic Broadcast in MANETs was studied under the assumption that nodes move in a one-dimensional grid knowing their position. Two deterministic Multicast protocols for MANETs are presented in [START_REF] Gupta | An adaptive protocol for reliable multicast in mobile multihop radio networks[END_REF][START_REF] Pagani | Reliable broadcast in mobile multihop packet networks[END_REF]. The solutions provided require the network topology to globally stabilize for long enough periods to ensure delivery of messages, and they assume a fixed number of nodes arranged in some logical or physical structure. Leaving aside channel contention, a lower bound of Ω(n) rounds of communication was proved in [START_REF] Prakash | A lower bound for broadcasting in mobile ad hoc networks[END_REF] for Broadcast in MANETs, even if nodes are allowed to move only in a two-dimensional grid, improving over the Ω(D log n) bound of [START_REF] Bruschi | Lower bounds for the broadcast problem in mobile radio networks[END_REF], where D is the diameter of the network. This bound was improved to Ω(n log n) in [START_REF] Dessmark | Broadcasting in geometric radio networks[END_REF] without using the movement of nodes, but the diameter of the network in the latter is linear. Recently, deterministic solutions for Geocast were proposed in [START_REF] Baldoni | Mobility versus the cost of geocasting in mobile ad-hoc networks[END_REF] for a one-dimensional setting and in [START_REF] Fernández Anta | Bounds for deterministic reliable geocast in mobile ad-hoc networks[END_REF] for the plane. In the latter work, the authors concentrate in the structure of the Geocast problem itself, leaving aside communication issues such as the contention for the communication channel.

Our Results

The main contribution of this work concerns negative results. Contrasting the lower bounds obtained with upper bounds derived by careful combination of previous techniques, interesting complexity gaps among protocol-classes are observed.

For a model where nodes may fail, there is no global clock, and nodes may be activated at different times, we show in Theorem 6 that any oblivious protocol takes, in the worst case, Ω((α

+ n 2 / ln n)n) steps to solve the Geocast problem if v max > πr/6(α + ⌊(n/3)(n/3 -1)/ ln(n/3(n/3 -1))⌋ -2).
Given the upper bound of n(α + 4n(n-1) ln(2n)) for Dissemination established in Theorem 8 by means of an oblivious deterministic protocol based on Primed Selection [START_REF] Anta | Deterministic communication in the weak sensor model[END_REF], this lower bound is tight up to a poly-logarithmic factor.

Moreover, for the same model, Theorem 5 shows that, even if nodes are activated simultaneously and do not fail, and an adaptive protocol is used, any Geocast protocol takes, in the worst case, Ω(n(α + n)) if v max > πr/(3(2α + n -4)). This result should be contrasted with the quasi-oblivious protocol based on Round-Robin that solves Dissemination in at most n(α + n) steps as established in Theorem 7.

The latter results are asymptotically tight and show that full adaptiveness does not help with respect to quasi-obliviousness. The first lower bound and the last upper bound, show an asymptotic separation almost linear between oblivious and quasi-oblivious protocols. In a more restrictive model, where nodes are activated simultaneously, there exists an oblivious protocol (e.g. Round Robin) that solves Dissemination in at most n(α + n) steps. Hence, the lower bound proved in Theorem 6 shows the additional cost of obliviousness when nodes are not simultaneously activated. This gap is what we call the profit of global synchrony, since it represents the gain the network obtains from global synchrony with respect to not having it. Moreover, the quasi-oblivious protocol derived shows that for the Dissemination problem, the simultaneous activation performance can be achieved by distributing the time elapsed since the source started the dissemination. For a discussion of the importance of node-activation schedule in distributed computing refer to [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF].

Additionally, it is shown in Theorem 1 that no protocol can solve the Geocast problem (and hence Dissemination) in all (α, β)-connected networks unless β ≥ n -1.

Interestingly, it is shown in Theorem 2 that this bound becomes β > ⌊(n -1)(n -3)/4 ln((n -1)(n -3)/4)⌋ if the protocol is oblivious. Comparing these bounds with the requirements of the protocols presented above, the quasi-oblivious protocol required β ≥ n, which is almost optimal, while the oblivious protocol required β ∈ Ω(n 2 log n), which is only a polylogarithmic factor larger than the lower bound. These results also expose another aspect of the profit of global synchrony mentioned before: while β = n is enough for quasi-oblivious protocols to solve Dissemination, oblivious protocols require a value of β almost a linear factor larger.

Finally, for an arbitrary small bound on node speed, we show in Theorem 3 the existence of an (α, β)-connected network where Geocast takes at least α(n -1) steps, even using randomization; and the existence of an (α, β)-connected network where any deterministic protocol that transmits periodically takes at least n(n -1)/2 steps, even if nodes do not move, in Theorem 4.

Paper Organization

The rest of the paper is organized as follows. In Section 2 we introduce some technical lemmas that will be used to prove our main results; in Section 3 we prove the lower bounds on link stability and on the time complexity to solve the Dissemination problem with respect to some important aspects of the system (e.g. speed of movement of nodes and their activation schedule) and of the protocols (e.g., obliviousness versus adaptiveness). We finally present the corresponding upper bounds in Section 4.

Auxiliary Lemmas

The following lemmas will be used throughout the analysis. A straightforward consequence of the pigeonhole principle is established in the following lemma. Lemma 1. For any time step t of the execution of a Dissemination protocol, where a subset V ′ of k informed nodes do not fail during the interval [t, t + k -2], there exists some node v ∈ V ′ such that v does not transmit uniquely among the nodes in

V ′ during the interval [t, t + k -2].
In the following lemma, we show the existence of an activation schedule such that, for any oblivious deterministic protocol, within any subset of at least 3 nodes, there is one that does not have a unique transmission scheduled within a period roughly quadratic in the size of the subset. The proof, based on the probabilistic method, is omitted for brevity and can be found in [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF].

Lemma 2. For any deterministic oblivious protocol that solves Dissemination in a

MANET of n nodes, where nodes are activated possibly at different times, and for any subset of k nodes, k ≥ 3, there exists a node-activation schedule such that, for any time slot t and letting m = ⌊k(k -1)/ ln(k(k -1))⌋, each of the k nodes is activated during the interval [t -m + 1, t], and there is one of the k nodes that is not scheduled to transmit uniquely among those k nodes during the interval [t, t + m -1].

If there is at least one node in V P -{s} at least one time slot is needed to solve Dissemination, since the source node has to transmit at least once to pass the information. Furthermore, if all nodes in V P are neighbors of s, one time slot may also be enough if the source node transmits before neighboring nodes are able to move out of its range. On the other hand, if the latter is not possible, more than one time slot may be needed. Let us consider the Geocast problem. Given that the specific technological details of the radio communication devices used determine the minimum running time when the eccentricity is d ≤ r, all efficiency lower bounds are shown for d > r unless otherwise stated.

Link Stability Lower Bounds

The following theorem shows a lower bound on the value of β for the Geocast problem.

Theorem 1. For any V max > 0, d > r, α > 0, and any deterministic Geocast protocol Π, if β < n -1, there exists an (α, β)-connected MANET of n nodes such that Π does not terminate, even if all nodes are activated simultaneously and do not fail.

Proof. Consider three sets of nodes A, B, and C deployed in the plane, each set deployed in an area of size ε arbitrarily small, such that 0 < ε < r and d ≥ r + ε. The invariant in this configuration is that nodes in each set form a clique, every node in A is placed within distance r from every node in B, every node in B is placed at most at distance ε from every node in C, and every node in A is placed at some distance r < δ ≤ r + ε from every node in C. At the beginning of the first time slot, the adversary places n -1 nodes, including the source node s, in the set C, the remaining node x in set A, and activates all nodes. The set B is initially empty. Given that d ≥ r + ε, x must become informed to solve the problem. Also, ε is set appropriately so that a node can move ε distance in one time slot without exceeding V max .

For any protocol Π for Geocast, let t be the first time slot where the source node is the only node to transmit in the set C. Adversarially, let t be the first time slot when the source is informed. Thus, (α, β)-connectivity is preserved up to time slot t for any α. At time slot t, all nodes placed in C are informed.

After time slot t, the adversary moves the nodes as follows. Given that the problem was not solved yet and nodes in C do not fail, according to Lemma 1, there exists a node y ∈ C that does not transmit uniquely among the nodes in C during the interval [t + 1, t + n -2]. Given that Π is a deterministic protocol, and the adversary knows the protocol and defines the movement of all nodes, the adversary knows which is the node y.

Assume, for the sake of contradiction, that β ≤ n -2. Then, the adversary places y in B for all time slots in the interval [t + 1, t + β]. Additionally, for each time slot t ′ ∈ [t + 1, t + β] where y transmits, the adversary moves to B some node z ∈ C that transmits at t ′ to produce a collision. At the end of each time slot t ′ the adversary moves z back to C. Such a node z exists since y does not transmit uniquely during the interval [t+1, t+n-2] and n-2 ≥ β. At the end of time slot t+β, the adversary moves y back to C and the above argument can be repeated forever preserving the (α, β)-connectivity and precluding Π from solving the problem. Therefore, β must be at least n -1.

Building upon the argument used in the previous theorem, but additionally exploiting the adversarial node activation, the following theorem shows a lower bound on the value of β for the Geocast problem if the protocol used is oblivious. The idea of the proof is to split evenly the nodes of set C in the proof of Theorem 1 in two groups, so that alternately the nodes in one group are activated while the nodes in the other group produce collisions. The details are omitted for brevity and can be found in [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF].

Theorem 2. For any V max > 0, d > r, n ≥ 8, α > 0, and any deterministic oblivious protocol for Geocast Π, if β ≤ m = ⌊(n -1)(n -3)/4 ln((n -1)(n -3)/4)⌋, there exists an (α, β)-connected MANET of n nodes such that Π does not terminate.

Time Complexity Lower Bounds versus Speed, Activation and Obliviousness

Exploiting the maximum time α that a partition can be disconnected, a lower bound on the time efficiency of any protocol for Geocast, even regardless of the use of randomization and even for arbitrarily slow node-movement, can be proved. The following theorem establishes that bound. The proof is omitted for brevity and can be found in [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF]. Theorem 3. For any V max > 0, d > r, α > 0, and β > 0, there exists an (α, β)connected MANET of n nodes, for which any Geocast protocol takes at least α(n -1) time slots, even if all nodes are activated simultaneously and do not fail.

The linear lower bound for Geocast proved in Theorem 3 was shown exploiting the maximum time of disconnection between partitions. Exploiting the adversarial schedule of node activation, even if nodes do not move nor fail, the same bound can be simply proved for arbitrary Geocast protocols, while a quadratic bound can be shown for the important class of equiperiodic protocols. The protocol definition and the theorem for the latter follows. The proof is omitted for brevity and can be found in [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF].

Definition 3. A protocol of communication for a Radio

Network is equiperiodic if for each node, the transmissions scheduled are such that the number of consecutive time steps without transmitting, call it T -1, is always the same. We say that T is the period of transmission of such a node. Theorem 4. For any V max ≥ 0, d > r, α > 0, β > 0, and any deterministic equiperiodic Geocast protocol Π, there exists an (α, β)-connected MANET of n nodes, for which Π takes at least n(n -1)/2 time slots to solve the problem, even if nodes do not fail and do not move.

In Theorems 3 and 4 we showed lower bounds for Geocast for arbitrarily small values of V max . We now show that, by slightly constraining V max , a quadratic lower bound can also be shown for arbitrary deterministic protocols. Theorem 5. For any V max > πr/(3(2α + n -4)), d > r, α > 0, β > 0, and any deterministic Geocast protocol Π, there exists an (α, β)-connected MANET of n nodes, for which Π takes Ω((α + n)n) time slots to solve the problem, even if all nodes are activated simultaneously and do not fail.

Proof. The following adversarial configuration and movement of nodes shows the claimed lower bound. Consider six sets of nodes A, A ′ , B, B ′ , C, and C ′ , each deployed in an area of size ε arbitrarily small, such that 0 < ε < r and d ≥ r + ε, and four points, x, y, x ′ , and y ′ placed in the configuration depicted in Figure 1(a). The invariant in these sets is that nodes in each set form a clique; each node in A ′ is placed at some distance > r and ≤ r + ε from the points x, y ′ , and each node in B; each node in A is placed at some distance > r and ≤ r + ε from the points x ′ , y, and each node in B; each node in B is placed within distance r of points x, y, x ′ , and y ′ , and each node in C and C ′ ; each node in C is placed at some distance > r and ≤ r + ε from the point x; each node in C ′ is placed at some distance > r and ≤ r + ε from the point x ′ ; and each node in B ′ is placed within distance ε of each node in B and within distance r of each node in C and C ′ . 6At the beginning of the first time slot, the adversary places n/2 nodes, including the source node s, in set B ′ , the remaining n/2 nodes in the set A, and starts up all nodes. (For clarity, assume that n is even.) All the other sets are initially empty. (See Figure 1(b).)Given that d ≥ r + ε, all nodes must be covered to solve the problem. Also, ε is set appropriately so that a node can be moved ε distance in one time slot without exceeding V max , and so that a node can be moved from set A to point x through the curved parts of the dotted line (see Figure 1(a)),of length less than π(r + ε)/6, in α + n/2 -2 time slots without exceeding V max . (To see why the length bound is that, it is useful to notice that the distance between each pair of singular points along each of the circular dotted lines is upper bounded by (r + ε)/2.) Let t be the first time slot when the source is scheduled to transmit. Adversarially, let t be the first time slot when the source is informed. Nodes stay in the positions described until t and, consequently, all the other n/2-1 nodes in set B ′ receive it. Starting at time slot t + 1, the adversary moves the nodes so that only one new node every α + n/2 steps becomes informed. First we give the intuition of the movements and later the details. (See Figure 1(b).)Nodes that are not in B or B ′ are moved following the dotted lines. Some of the nodes in B ′ are moved back and forth to B. Nodes initially in A are moved clockwise to A ′ , except for one of them, say u, which is moved simultaneously counterclockwise to the point x. Upon reaching A ′ nodes are moved counter-clockwise back to A, except for one of them, say v, which is moved simultaneously clockwise to the point x ′ , while the node u is also moved simultaneously to the point y. Upon reaching A, the remaining nodes repeat the procedure while u keeps moving towards C and v keeps moving towards C ′ through y ′ respectively. Nodes initially in A are moved in the above alternating fashion, one to C and the next one to C ′ , until all nodes become informed. Movements are produced so that (α, β)-connectivity is preserved. The details follow.

A A ′ B B ′ C C ′ x x ′ y y ′ ≤ r ≤ ε r < • ≤ r + ε r < • ≤ r + ε r < • ≤ r + ε r < • ≤ r + ε (a) Distances invariant. A A ′ B B ′ C C ′ x x ′ y y ′ s (b) Initial configuration.
The movement of each node u moved from A to C is carried out in three phases of at least α + n/2 -2 time slots each as follows. (As explained below, some nodes initially in A will be moved instead to C ′ , but the movement is symmetric. For clarity, we only describe the whole three phases for one node. The movement is illustrated in Figure 4 in [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF], which is omitted here for brevity.) Phase 1 During the first α -2 time slots, u is moved counterclockwise from A towards the point x maintaining a distance > r and ≤ r + ε with respect to every node in B. In the (α -1)-th time slot of this phase, u is moved within distance r of every node in set B preserving (α, β)-connectivity. Nodes in B ′ stay static during this interval.

Given that only nodes in B ′ are informed and the distance between them and u is bigger than r, u does not become covered during this interval.

During the following n/2 -1 time slots of the first phase, the counterclockwise movement of node u towards the point x continues, but now maintaining a distance at most r with respect to every node in B. In the last time slot of the second phase, u is moved to point x. During this interval, nodes in B ′ are moved back and forth to B as described in Theorem 1 to guarantee that u does not become covered before reaching point x. Upon reaching point x, u and all the other nodes in the network not in B or B ′ remain static. Phase 1 ends the time slot before u becomes covered. Simultaneously, along the first α + n/2 -2 time steps of this phase, the remaining nodes initially in A are moved clockwise to A ′ . Then, even if u becomes informed immediately upon reaching point x, u cannot inform nodes in A ′ because they are separated by a distance > r. Phase 2 During this phase, u is moved counterclockwise towards point y maintaining a distance at most r with respect to every node in B and B ′ . Simultaneously, nodes that were in A ′ at the end of the second phase are moved counterclockwise to A except for one node v that moves in its own first phase to x ′ .

Nodes moving from A ′ to A maintain a distance > r with respect to u. Thus, even if u becomes covered the information cannot be passed to the former. At the end of this phase v is placed in point x ′ . Thus, even if v becomes covered in the first step of its second phase, v cannot inform nodes in A because they are separated by a distance > r. Phase 3 During this phase, u is moved counterclockwise towards set C maintaining a distance at most r with respect to every node in B and B ′ . Simultaneously, nodes that were in A at the end of the second phase are moved clockwise to A ′ except for one node w that moves in its own first phase to x. Also simultaneously, v continues its movement towards set C ′ in its own second phase. Nodes moving from A to A ′ maintain a distance > r with respect to v. Thus, even if v becomes covered the information cannot be passed to the former. Also, nodes u and w are moved maintaining a distance > r between them. Thus, u cannot inform w. At the end of this phase u has reached set C, v is placed in point y ′ , and w is placed in point x. Thus, even if w becomes covered in the first step of its second phase, w cannot inform nodes in A because they are separated by a distance > r. Upon completing the third phase, u stays static in C forever so that (α, β)connectivity is preserved.

The three-phase movement detailed above is produced for each node initially in A, overlapping the phases as described, until all nodes have became covered. Given that when a node u reaches the point x, its phase 1 is stretched until the time step before u becomes covered by a node v in B and all other nodes remain static, the next node w that will be moved from A ′ to x ′ does not become covered by v, because w stays in A ′ until u becomes covered. In each phase of at least α + n/2 -2 time slots every node is moved a distance at most π(r + ε)/6 + ε. Thus, setting ε appropriately, the adversarial movement described does not violate V max . Given that n/2 nodes initially in A are covered one by one, each at least within α + n/2 -2 time slots after the previous one, the overall running time is lower bounded as claimed, even if t = 1.

The quadratic lower bound shown in Theorem 5 holds for any deterministic protocol, even if it is adaptive. Building upon the argument used in that theorem, but additionally exploiting the adversarial node activation, the following theorem shows a roughly cubic lower bound for oblivious protocols, even relaxing the constraint on V max . The proof is omitted for brevity, the details can be found in [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF]. Theorem 6. For any n ≥ 9, d > r, α > 0, β > 0, V max > πr/6(α + ⌊(n/3)(n/3 -1)/ ln(n/3(n/3 -1))⌋ -2), and any oblivious deterministic Geocast protocol Π, there exists an (α, β)-connected MANET of n nodes, for which Π takes Ω((α + n 2 / ln n)n) time slots to solve the problem.

as an (α, β)-connected MANET, and not even for specific instances of Dissemination. In this section, a quasi-oblivious protocol and an oblivious one that solve Dissemination, both based on known algorithms particularly suited for our setting, are described and their time efficiency proved. The first bound is asymptotically tight with respect to the more powerful class of adaptive protocols.

A Quasi-Oblivious Protocol. The idea behind the protocol is to augment the wellknown Round-Robin protocol with the synchronization of the clock of each node with the time elapsed since the dissemination started, which we call the global time. This is done by embedding a counter τ , corresponding to the global time, in the messages exchanged to disseminate the information I. Given that the schedule of transmissions of a node depends only on its ID and the global time, the protocol is quasi-oblivious. More details about the algorithm can be found in [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF].

It can be proved that this quasi-oblivious algorithm solves Dissemination for arbitrary values of V max in at most n(α + n) time steps. The details are omitted for brevity and can be found in [START_REF] Fernández Anta | Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony[END_REF]. Formally, Theorem 7. Given an (α, β)-connected MANET where β ≥ n, there exists a quasioblivious deterministic protocol that solves Dissemination for arbitrary values of V max in at most n(α + n) time steps.

Recall that β ≥ n -1 is required for the problem to be solvable as shown in Theorem 1. This upper bound is asymptotically tight with respect to the lower bound for general deterministic Geocast protocols when V max > πr/(3(2α + n -4)) shown in Theorem 5. Thus, we can conclude that having extra information in this case does not help.

An Oblivious Protocol. We finally describe how to implement an oblivious protocol for Dissemination, based on Primed Selection, a protocol presented in [START_REF] Anta | Deterministic communication in the weak sensor model[END_REF] for the related problem of Recurrent Communication. Given that in this protocol the schedule of transmissions of a node depends only on its ID, the protocol is oblivious. This upper bound is only a poly-logarithmic factor away from the lower bound shown in Theorem 6.

In order to implement Primed Selection, one of n prime numbers is stored in advance in each node's memory, so that each node holds a different prime number. Let p ℓ denote the ℓ-th prime number. We set the smallest prime number used to be p n , which is at least n, because Primed Selection requires the smallest prime number to be at least the maximum number of neighbors of any node, which in our model is unknown. The algorithm is simple to describe, upon receiving the information, each node with assigned prime number p i transmits with period p i .

It was shown in [START_REF] Anta | Deterministic communication in the weak sensor model[END_REF] that, for any Radio Network formed by a set V of nodes running Primed Selection, for any time slot t, and for any node i such that the number of nodes neighboring i is k -1, 1 < k < n, i receives a transmission without collision from each of its neighbors within at most k max j∈V p j steps after t. Given that in our setting the biggest prime number used is p 2n-1 , that p x < x(ln x + ln ln x) for any x ≥ 6 as shown in [START_REF] Rosser | Approximate formulas for some functions of prime numbers[END_REF], and that due to mobility all nodes may get close to i in the worst case, we have that k max j∈V p j < n(2n -1)(ln(2n -1) + ln ln(2n -1)), for n ≥ 4. Which is in turn less than 4n(n -1) ln(2n) for n ≥ 3. Hence, given that in the worst case all nodes must be covered at least one at a time and that the network is (α, β)-connected, the overall running time is less than n(α + 4n(n -1) ln(2n)). We formalize this bound in the following theorem. Recall that β > ⌊(n -1)(n -3)/4 ln((n -1)(n -3)/4)⌋ is required for the problem to be solvable when n ≥ 8 as shown in Theorem 2.

Theorem 8. Given an (α, β)-connected MANET, where β ≥ n(2n -1)(ln(2n -1) + ln ln(2n -1)) and n ≥ 4, there exists an oblivious deterministic protocol that solves Dissemination for arbitrary values of V max in at most n(α + 4n(n -1) ln(2n)) time steps.

Fig. 1 .

 1 Fig. 1. Illustration of Theorem 5. A small empty circle depicts a point in the plane. A small black circle depicts a node. A big empty area depicts an empty set. A big shaded area depicts a non-empty set.

During some periods of time a given set could be empty, we mean that x is separated (within) that distance from any point in the area designated to the set X

Upper BoundsSolving the Dissemination problem under arbitrary node-activation schedule and nodemovement is not a trivial task. To the best of our knowledge, deterministic protocols for such scenarios were not studied before, not even for potentially epidemic networks such

⋆ This research was partially supported by Spanish MICINN grant no. TIN2008-06735-C02-01, Comunidad de Madrid grant no. S2009TIC-1692, EU Marie Curie International Reintegration Grant IRG 210021, NSF grant no. 0937829, ANR grant R-DISCOVER, and by the Israel Science Foundation, grant no. 1249/08.


José Javier Anaya
email: jj.anaya@upm.es

Pierre Merdrignac

Oyunchimeg Shagdar

Fawzi Nashashibi

José E Naranjo

Vehicle to Pedestrian Communications for Protection of Vulnerable Road Users

Vehicle and pedestrian collisions often result in fatality to the vulnerable road users, indicating a strong need of technologies to protect such vulnerable road users. Wireless communications have potential to support road safety by enabling road users to exchange information. In contrast to vehicle to vehicle (V2V) and vehicle to infrastructure (V2I) communications for avoidance of inter-vehicle collisions, very limited efforts are made on communication mechanisms for pedestrian safety. This paper addresses the issue in a concrete way. We first formulate the requirement of the minimum information exchange distance for providing road users to have the necessary amount of time to perceive the situation and react. We then report our field tests and measurement based analysis to investigate if a Wi-Fi system can satisfy the application requirement. We also introduce a pedestrian protection application, V2ProVu, which provides the functionalities of the Wi-Fi communications, risk calculation, and hazard alarming. Our study discloses several useful insights including 1) information exchange for a velocity of 80 km/h has to be made before vehicle to pedestrian (V2P) distance is below 72 meters and 2) while this requirement is not too hard for radio communications technologies, the V2P communication range is greatly reduced if the signal is blocked by a human body.

I. INTRODUCTION

Vulnerable Road Users are defined as "non-motorized road users, such as pedestrians and cyclists as well as motorcyclists and persons with disabilities or reduced mobility and orientation" [1]. According to the statistics [START_REF] Who | Global Status Report On Road Safety 2013: supporting a decade of action[END_REF], more than 3000 people die daily due to dangerous driving, and half of them are vulnerable road users. The main reason of accidents is the inability of road users to detect and perceive oncoming dangers before a sufficient amount of time so that reactions for accident avoidance can be taken. Much attention has been put in detecting pedestrians and predicting the possibility of collisions using sensors and computer vision techniques [START_REF] Gandhi | Pedestrian Protection Systems: Issues, Survey, and Challenges[END_REF]. Such sensor based approaches however do not perform well in poor visibility conditions e.g., at night time, in bad weather conditions, or the pedestrian is not close enough (e.g. within few tens meters) or in non-line-of-sight (NLOS) position w.r.t the sensor [START_REF] Gandhi | Pedestrian Protection Systems: Issues, Survey, and Challenges[END_REF]. Therefore it is necessary to study and develop different technologies to fill the missing gap towards zero fatalities. One of such technologies is the radio communications technology that has a potential to provide an extended "view" to the road users even in NLOS conditions.

Although safe driving support is one of the hot R&D subjects in the telecommunications field, the majority of the work has a focus on the V2V and V2I communications for avoidance of inter-vehicle collisions. An important achievement of these activities is the specification of the IEEE 802.11p amendment, Wi-Fi dedicated to ITS applications [START_REF]IEEE Standard for Information technology -Telecommunications and information exchange between systems -Local and metropolitan area networks -Specific requirement[END_REF]. However, we believe that it is realistic to apply a technology, which is available in handheld devices, for V2P communications. Indeed, studies on the applicability of such technologies to the V2P communications have been carried out [START_REF] David | Car-2-x and pedestrian safety[END_REF], [START_REF] Sugimoto | Prototype of pedestrian-to-vehicle communication system for the prevention of pedestrian accidents using both 3g wireless and wlan communication[END_REF]. The authors of [START_REF] David | Car-2-x and pedestrian safety[END_REF] and [START_REF] Sugimoto | Prototype of pedestrian-to-vehicle communication system for the prevention of pedestrian accidents using both 3g wireless and wlan communication[END_REF] independently investigated the delay performances of Wi-Fi and cellular systems and showed that Wi-Fi can provide at least one order of magnitude shorter delay than that of the cellular systems (10 and 400 ms of delay in Wi-Fi and 3G systems, respectively [START_REF] Sugimoto | Prototype of pedestrian-to-vehicle communication system for the prevention of pedestrian accidents using both 3g wireless and wlan communication[END_REF]). An important lesson provided by [START_REF] David | Car-2-x and pedestrian safety[END_REF] and [START_REF] Sugimoto | Prototype of pedestrian-to-vehicle communication system for the prevention of pedestrian accidents using both 3g wireless and wlan communication[END_REF] is that without denying the possibilities of using both the systems in a combined way, Wi-Fi seems to be the primary choice especially for low-latency direct V2P communications.

To this end, we study Wi-Fi based V2P communications for pedestrian safety support. Vehicle and pedestrian collision can be avoided by informing the driver of the existence of the pedestrians and/or by informing the pedestrians of the existence of the oncoming vehicles. The majority of the existing work on computer vision and telecommunications fields [START_REF] Gandhi | Pedestrian Protection Systems: Issues, Survey, and Challenges[END_REF], [START_REF] David | Car-2-x and pedestrian safety[END_REF], [START_REF] Andreone | Cooperative Systems for vulnerable road users: The Concept Of The WATCH-OVER Project[END_REF] targets the former approach. We believe that for zero fatalities, it is also necessary that pedestrians have information and react for their own safety. Therefore, leaving the former approach to our future work, this paper focuses on the latter approach i.e., vehicles inform pedestrians of their existence. Since a very limited effort is made on V2P communications for pedestrian safety, we address the issue in a concrete way. Specifically, we first formulate the requirement on the minimum information exchange distance for allowing pedestrians to have necessary time to perceive and react. Because the minimum distance is a function of the positioning accuracy and the communication range, we carry out real-world experiments and investigate the performances. The GPS measurements show that 10 m of positioning error should be expected even in a good weather condition. Although, connection time for V2P communications might be long, we assume vehicles and pedestrians have initially been connected to the same network and are exchanging information within this network. Hence, the Wi-Fi performances are measured in terms of packet delivery ratio (PDR) and packet inter-reception time (PIR) for different scenarios, where the pedestrian carries the handheld device in different manners. The results imply that communication coverage can be reduced by a hundred meter if the radio signal is blocked by the human body. Nevertheless, we show that Wi-Fi can satisfy the application requirement with a condition that the transmission frequency is higher than 1 Hz. Finally, we developed an application, V2ProVu, for vehicle on-board and pedestrian handheld devices providing functionalities of the Wi-Fi communication, risk calculation, and hazard alarming. For the risk calculation and hazard alarming, we define a geographical area (GDA: geographical destination area) w.r.t the vehicle on which pedestrians have to be informed of the oncoming vehicle.

The paper is organized as follows. Section II highlights the related work. Section III defines the application requirement followed by performance investigation of V2P communication system in Section IV. Section V introduces the calculation of GDA and our application, V2ProVu, which is developed to investigate the feasibility of pedestrian safety supported by V2P communications. Finally, Section VI concludes our paper.

II. RELATED WORK

Pedestrian safety has been an issue for many years in the automotive field. Solutions based on vehicle embedded sensors (e.g. camera, laser, and radar) and computer vision technologies have been proposed [START_REF] Gandhi | Pedestrian Protection Systems: Issues, Survey, and Challenges[END_REF], [START_REF] Gate | Centralized fusion for fast people detection in dense environment[END_REF]. Reference [START_REF] Wang | WalkSafe : A Pedestrian Safety App for Mobile Phone Users Who Walk and Talk While Crossing Roads Categories and Subject Descriptors[END_REF] introduces Walk-Safe application, which detects oncoming vehicles using the camera embedded in smartphones. As mentioned earlier, sensor and computer vision techniques have strong constraints regarding sensor locations (for example Walk-Safe cannot be used if the smartphone is e.g., in a pocket or if the camera is facing to the ground or the sky), coverage and field of view.

Projects such as WATCH-OVER [START_REF] Andreone | Cooperative Systems for vulnerable road users: The Concept Of The WATCH-OVER Project[END_REF] and Ko-TAG [START_REF]Ko-tag -kooperative transponder[END_REF] rely on pedestrian to vehicle communications to enhance safety. Within this projects, methods based on radio signal propagation have been applied to estimate precisely V2P distance. However, such methods require the development of specific electronic devices for pedestrians who are already carrying handheld devices with many capabilities. The authors of [START_REF] Liebner | Active Safety for Vulnerable Road Users based on Smartphone Position Data[END_REF] carried out a detailed study targeting the GPS receivers embedded in handheld devices and concluded that assistance can only be given in scenarios with low requirements on the GPS accuracy. Therefore, we considered performances of such GPS systems in our work.

In August 2013, Honda announced its development of a V2P communications technology based on DSRC (Dedicated Short Range Communication) on 5.9 GHz for pedestrian safety [START_REF]Honda demonstrates advanced vehicle-to-pedestrian and vehicle-to-motorcycle safety technologies[END_REF]. Assuming that the mentioned DSRC is the IEEE 802.11p, a use of the IEEE 802.11p for V2P is somehow questionable because 1) users already carry handheld devices which have the capabilities of short, medium, and long range communications (Bluetooth, Wi-Fi, and 3/4G) and 2) the frequency channel of IEEE 802.11p (especially the control channel, which is for safety applications) is expected to have a serious channel congestion due to V2V communications in a dense road environment. Nevertheless, the IEEE 802.11p, is a Wi-Fi technology, and hence we believe that our study, which is carried out using the IEEE 802.11g, is generally valid for the IEEE 802.11p too. General Motors is developing a V2P communications system based on WiFi-Direct which is already available in smartphones [START_REF]Gm developing pedestrian safety technology that spots smartphones[END_REF]. Unfortunately none of [START_REF]Honda demonstrates advanced vehicle-to-pedestrian and vehicle-to-motorcycle safety technologies[END_REF] and [START_REF]Gm developing pedestrian safety technology that spots smartphones[END_REF] provided information about their mechanisms to protect vulnerable road users.

The authors of [START_REF] David | Car-2-x and pedestrian safety[END_REF] and [START_REF] Sugimoto | Prototype of pedestrian-to-vehicle communication system for the prevention of pedestrian accidents using both 3g wireless and wlan communication[END_REF] investigated the performances of Wi-Fi and cellular systems, and show that Wi-Fi can show significantly shorter communications delay. Furthermore, [START_REF] David | Car-2-x and pedestrian safety[END_REF] defined a requirement to V2X communications for road safety applications, assuming that positioning is perfectly accurate. We extend the requirement for V2P communications with no assumption on positioning accuracy. The authors of [START_REF] Sugimoto | Prototype of pedestrian-to-vehicle communication system for the prevention of pedestrian accidents using both 3g wireless and wlan communication[END_REF] proposed a mechanism to use both of the cellular and Wi-Fi systems for pedestrian safety. The key player of the mechanism is a control centre that communicates with vehicles and pedestrians using the cellular network. If the control centre detects a risk of collision between a pedestrian and a vehicle, it asks the pair of vehicle and pedestrian to communicate directly using Wi-Fi. We also believe the number of traffic accidents can be greatly reduced by using different communication systems. However the proposed approach in [START_REF] Sugimoto | Prototype of pedestrian-to-vehicle communication system for the prevention of pedestrian accidents using both 3g wireless and wlan communication[END_REF] is too much "centralized" so that processing and communications at the control centre could be the bottleneck of the overall system, resulting in a scalability problem. Most importantly, because a very little is known about the applicability of Wi-Fi for pedestrian safety, we decided to first focus on Wi-Fi systems. The key contributions of our work in contrast to the existing work are as follows: 1) we formulated the application requirement for the pedestrian safety 2) we investigated the GPS and Wi-Fi performances and achieved useful insights especially regarding the impact of the blockage by a human body 3) we carried out measurement-based analysis to investigate if the Wi-Fi system can satisfy the application requirement, and finally 5) we developed an application with the functionalities of Wi-Fi communications, risk calculation, and hazard alarming.

III. APPLICATION REQUIREMENT Similar to inter-vehicle communications, collisions between vehicles and pedestrians can be largely avoided by enabling vehicles to periodically broadcast information on their position, velocity, moving direction, and etc. ETSI defined such a type of messages as Cooperative Awareness Message (CAM). In this section, we define the application requirement to CAM delivery in V2P scenarios.

The authors of [START_REF] David | Car-2-x and pedestrian safety[END_REF] defined system available time t sta which refers to the remaining time excluding that for communications, driver's perception and reaction. Since we are interested in the case, where pedestrians receive CAMs and react accordingly, we re-define t sta :

t sta = d v -t p -t r , ( 1
)
where v is the velocity of the vehicle and d is the distance between the vehicle and the pedestrian at the time, when the pedestrian receives a CAM from the vehicle. t p and t r are the time required for perception (i.e., the pedestrian recognizes the existence of the oncoming vehicle) and reaction. Obviously, for collision avoidance, it is required that t sta > 0.

It is realistic to expect that in order to estimate collision risk, upon reception of a CAM, the pedestrian (the device) calculates the distance (d) based on the position information included in the CAM and its own position. Therefore the application is largely dependent on the accuracy of the position information and the transmission delay of the V2P communication. Letting gnss errcar and gnss err ped be the positioning error at the vehicle and the pedestrian, respectively, and t tx be the transmission delay, the pedestrian may over-estimate the distance: d = d calgnss errcargnss err pedv × t tx , where d cal is the calculated distance based on the GPS information. Finally, following t sta > 0, we get d cal > d min , where

d min = v × (t p + t r + t tx ) + gnss errcar + gnss err ped . (2)

IV. PERFORMANCE INVESTIGATION OF V2P

COMMUNICATIONS SYSTEM Motivated by the application requirement, we investigate the GPS accuracy and the PDR and PIR of performances of the IEEE 802.11g.

A. System description

Vehicle to pedestrian communications are evaluated using a Citroen C1, equipped with a communication device, NexCom, which is installed with the IEEE 802.11g and a conventional GPS chip. The vehicle also has a separate Real Time Kinematic (RTK) GPS receiver, which is used as a ground-truth for the vehicle's positioning (see Fig. 1). The pedestrian carries Samsung Galaxy Tab2 10.1 with version 4.0.4 of Android OS.

B. GPS Accuracy

The worst scenario regarding position information is probably the case, where no GPS information is available due to e.g., a bad weather condition. We investigate rather a "good-case" positioning performance, i.e., the accuracy of a "conventional" GPS on a sunny day. Specifically, we run Citroen C1 at Inria site, collected the position information provided by the GPS receiver of NexCom, and compared it with that of RTK GPS, whose positioning information is corrected by a reference station, providing centimeter-level accuracy. Similarly to the authors of [START_REF] Liebner | Active Safety for Vulnerable Road Users based on Smartphone Position Data[END_REF], we notice that GPS error on lateral direction is larger than that of longitudinal. Besides, if we consider 95% of the GPS error in distance, then we determine GPS error is approximately 10 m. To this end, our experiments confirmed that the GPS devices of vehicles' onboard systems and pedestrians' hand-held show GPS error that is not generally satisfactory for safety applications, even in "good case" conditions.

C. Wi-Fi Performance

In order to collect a sufficient amount of data for varying distances, the vehicle is parked on a road and the pedestrian walks away from the vehicle (at around 1 m/s speed) following the 500 meters road as illustrated in Fig. 1. An initital connection is established between the vehicle and the pedestrian. Because a conventional GPS provides position update every 1 s, the vehicle broadcasts 110 Bytes of packets every 1 second with 12.0 Mbps coding rate at 27 dBm transmission power. The tablet of the pedestrian collects the received packets for investigation of PDR and PIR performances. The performance measurements are made for the following two scenarios.

• Scenario 1: Pedestrian holds the tablet in his front close to his body. In this scenario, the human body blocks the signal emitted from the vehicle.

• Scenario 2: Pedestrian carries the tablet in his backpack, resulting in the signal is blocked only by the cotton tissue of the backpack. 1) Packet Delivery Ratio (PDR): Figure 3 shows the packet delivery performance for the two scenarios. As can be seen in the figure, the V2P communication is achievable over 400 meters of distance. PDR at 400 m is only 30% for scenario 1, whereas it is 60% for scenario 2, clearly indicating the significant impact of the signal blockage by the human body. Finally, as we expect, PDR degrades with the increase of the distance for both the scenarios. The results show that in order to achieve e.g., 80% of PDR, the distance needs to be smaller than 130 m (resp. 305 m) for scenario 1 (resp. scenario 2).

2) Packet Inter Reception (PIR) Time: In our experiments, we observed very short transmission delay (appx. 10 ms) without depending on the V2P distance. An important performance metric for safety applications is packet inter-reception increases with the increase of d th and it is larger for smaller k. Finally, we observe that the probability of not receiving more than 6 consecutive CAMs is very small, and hence it can be neglected.

D. Measurement based study on the applicability of Wi-Fi for pedestrian protection

Based on our experimental results, we first calculate the minimum required information exchange distance, d min (see Eq. ( 2)). According to our results and that presented in [START_REF] Liebner | Active Safety for Vulnerable Road Users based on Smartphone Position Data[END_REF], gnss errcar ≈ err ped ≈ 10 m. Following [START_REF] David | Car-2-x and pedestrian safety[END_REF], we expect human needs appx. 0.83s to perceive the "meaning" of the information provided by the V2P communications system (t p =0.83 s). The reaction time, i.e., the time required to react (e.g., avoid) depends on the situation. However, for the worst case, we can imagine that the pedestrian was in the middle of the road and t r is the time required to cross the half of the road. Therefore, setting the road width to e.g., 3 m and the velocity of the pedestrian to 1 m/s, the reaction time, t r =1.5 s. Moreover, according to our experiments and the results provided in [START_REF] Sugimoto | Prototype of pedestrian-to-vehicle communication system for the prevention of pedestrian accidents using both 3g wireless and wlan communication[END_REF], the transmission delay is approximately 10 ms. Wrapping everything up, we get d min is equal to 39.5, 52.3, and 72.0 m, when the velocity of the vehicle is 30, 50, 80 km/h, respectively.

Inspired by [START_REF] Martelli | A Measurementbased Study of Beaconing Performance in IEEE 802 . 11p Vehicular Networks[END_REF], we take a measurement-based analysis to investigate whether the Wi-Fi system can satisfy the application requirement. Since vehicles periodically broadcast CAMs, we can say that the transmission of message i is occurred at the V2P distance, d i . Therefore the message reception status at a given d, where d i+1 > d > d i (note that if i > j, then d i > d j ), is same as that at d i+1 . Now it is realistic to define that at a given V2P distance d (d i+1 > d > d i ), if none of the k consecutive messages, i + k, i + k -1, ... i + 2, i + 1, is received, then the pedestrian is not "informed" of the existence of the vehicle. Since the probability of message reception at d i is P DR(d i ), the probability of being informed at d min is

p(d min ) = 1 -p(d min ) = 1 - k i=1 (1 -P DR(d i )), ( 3
)
where

d i = d min + v × i f tx . ( 4
)
Here f tx is the CAM generation frequency. It should be noted that since we cannot expect that a transmission occurs at exactly d i (in ( 4)), the P DR(d i ) in ( 3) is the average PDR corresponding to the range ]d i-1 ,d i ].

Figure 5 draws the probability of being informed at d min for different values of k. Here, f tx is 1 Hz. As can be seen in the figure, the probability of being informed is very high (larger than 0.8) for any speed and scenario. In order to have 1, however, k needs to be larger than 3, implying a need for increased transmission frequency. We end this section by concluding that 1) Wi-Fi can be used for V2P communications for pedestrian safety; 2) for further performance improvement, the message generation frequency has to be larger than 1 Hz. While it is important to alert pedestrians of oncoming dangers, an attention has to be paid to over-alarming. Specifically, pedestrians can receive messages from many vehicles around them. However, not all of the vehicles influence pedestrians' safety. Thus, messages sent by vehicles should be "filtered" such that a focus is given to only the vehicles, which have risks of collisions. For such message filtering, we define GDA, which is calculated based on the kinematics of the vehicle and indicates that the pedestrians in the GDA has a collision risk with the vehicle. This section defines GDA and introduces our application, V2ProVu, which uses GDA for risk calculation.

A. Geographical Destination Area calculation

GDA can be determined based on the vehicle's kinematics, especially, the vehicle's position, speed, and yaw rate, length, and width. It should be noted that speed and yaw rate can normally be obtained from the CAN bus of the vehicle, but they can be measured by external sensors or simply be calculated from the GPS information. The shape of GDA is different if the near-future moving direction of the vehicle is straight or turning as illustrated in Figure 6. In order to determining GDA, first, the latitude and longitude positions of the vehicle and the pedestrian are transformed into in a cartesian coordinate system using usual world geodetic system (wgs84). Then, the vehicle's trajectory is represented using the bicycle model (with 2 tires). A local coordinate system (O V , X V , Y V ), which is centered at the rear tire is built as shown in figure 7(a). Based on the coordinate and the available information (specifically, velocity (V = V G ) and yaw rate (ω)), the radius to the gravity center (R S ), the Ackerman angle (the vehicle steering angle ǫ r ), and the Instantaneous Center of Rotation (ICR) I S (X S ,Y S ) can be found:

R S = V ω , ǫ r = L R S X S = 0, Y S = Rs × cos ǫr 2 .
(5)

Finally, using the above-calculated values, the right and left boundaries of GDA (green lines in Fig. 6(a) and 6(b)) can be calculated following the parametric equation (due to the lack of space, the equations are not presented). Once a vehicle calculates the GDA, it can include a representation of the GDA in its CAM so that pedestrians determine whether they are in the GDA. However, as can be seen in Fig. 6(b), GDA can have a complicated shape, thus a representation of the shape and including the information in CAMs would increase processing and transmission overhead. Therefore, in our application, we took an equivalent approach, where pedestrians calculate time-to-collision (TTC) that determines if the pedestrians are in the GDA. The intersection point between the pedestrian and vehicle's trajectories, P int , is calculated based on the vehicle's trajectory and the line that connects I S and the pedestrian position, P ped (see Figure 7(b)). Then, TTC, i.e., the time required for the vehicle to reach P int , is calculated by applying the bicycle model to estimate the near-future trajectory. Finally, we consider that there is a risk of collision, if the pedestrian can reach P int before the vehicle arrives. In other words, i.e, letting d be the distance between P int and P ped , there is a risk of collision if d < V pmax × T T C, where V pmax is the typical value of the maximum velocity of pedestrians. The detail of the algorithm is provided in Algorithm 1.

Algorithm 1 Pedestrian Alert System Input: V, ω: Vehicle speed and yaw rate X ped ,Y ped : Pedestrian position in vehicle coordinate system Parameters: L, W: Vehicle length and width V pmax : Maximum pedestrian speed Output: Packet is accepted or not Calculate R S , ǫ r , X S and Y S using Eq. ( 5)

θ ← atan2( Y ped -Y S R S , X ped -X S R S ) T T C ← θ-ǫr 2 + π 2 ω X int ← R S × cos θ + ǫr 2 -π 2 + X S Y int ← R S × sin θ + ǫr 2 -π 2 + Y S d ← (X ped -X int ) 2 + (Y ped -Y int ) 2 Accept if d < V pmax × T T C

B. Application Design and Operational Test

As a proof of concept we developed a Java application, called V2ProVu, which consists of the transmitter and receiver sides. The transmitter V2ProVu permanently collects information on the position and the kinematics of the vehicle and periodically generates CAMs and transmits over Wi-Fi interface using UDP. The receiver V2ProVu receives the CAMs and if itself is in the GDA, it provides an alarm to the pedestrian. The transmitter V2ProVu is implemented in a Linux system (that of NexCom) and the receiver V2ProVu is implemented in the Android system of the Samsung Galaxy.

Furthermore, we also considered the timing of triggering alarms to the pedestrian. Let us imagine the scenario illustrated in Fig. 6. In Fig. 6(a), the vehicle's near-future trajectory is straight, therefore, the pedestrian, P2, was in the GDA. However, after some period of time (Fig. 6(b)), the vehicle changes its trajectory (turns left), resulting in P2 be out of GDA. Obviously, if the system triggers alarm as soon as the pedestrian is in the GDA, the system would cause many false alarms. Therefore, we divide a GDA to two sub-areas using TTC. If TTC is above a given threshold, t th , the pedestrian is only informed of the presence of the vehicle. However, if TTC is below t th , then the pedestrian receives an alert. We formulate t th in Eq. ( 6) using the requirement defined in Section III, and k th , the number of consecutive packets that should be sent to ensure that the pedestrian is informed with a high probability (see Section IV-C).

t th = t p + t r + t tx + k th f tx (6)
Finally, we carried out a number of experiments to verify the functionalities implemented in V2ProVu. In the experiments, a vehicle, which is equipped with the V2ProVu transmitter, approaches a pedestrian who stands still on the side edge of the road holding the V2ProVu receiver (the tablet). Based on the results in Figure 5 we set k th to 4. With the values of t p , t r , t tx and f tx from Section IV-C, we find t th =6.5 s. Figure 8 illustrates one of our experiments. In the figure, the positions of the vehicle at the time, t 1 , t 2 , and t 3 , (t 1 < t 2 < t 3 ) and the corresponding screen snapshots of the V2ProVu receiver are shown. At t = t 1 , the distance is 65.31 m and the color of HMI is green, indicating the pedestrian is outside of the GDA. On the other hand, at t = t 2 (resp. t = t 3 ), the pedestrian is inside the GDA, the V2P distance is 34.63 m (resp. 19.86 m), TTC=8.5s (resp. TTC=4s) which is above (resp. below) t th and thus the HMI is yellow (resp. red), indicating a potential danger (resp. a high collision risk). VI. CONCLUSION Wireless communications technology has a potential to support safety of vulnerable road users by enabling information exchange between pedestrians and vehicles. This paper introduces our study on pedestrian safety support by Wi-Fi based V2P communications. We formulated the requirement of the minimum information exchange distance for V2P communications for pedestrian protection and conducted a study on the applicability of Wi-Fi based V2P communications system. The real-world experiments show that it is necessary to consider 10 m of GPS error even in a good weather condition. Moreover while 400 m of communication coverage is achievable, if the signal is blocked by the human body, the communications distance would be significantly shorter. Nevertheless, by measurement based analytical study, we showed that the Wi-Fi system can satisfy the application requirement, with the condition of increased transmission frequency (larger than 1 Hz). Finally, V2ProVu, which is an application for pedestrian protection by providing the functionalities of Wi-Fi communications, risk calculation, and hazard alarming, is introduced. Our future work includes an extended experimental study on pedestrian to vehicle communication mechanisms for safety of vulnerable road users. Moreover, we also plan to investigate the interference issue in the non-ISM band (e.g., 2.4 GHz) having in mind of the possibility of applying DSRC for V2P communications.

Fig. 1 :

 1 Fig. 1: Experimental setup.

Fig. 2 :

 2 Fig. 2: Histogram of GPS error in longitudinal and lateral position, and in distance

Fig. 3 :

 3 Fig. 3: Packet Delivery Ratio (PDR)

Fig. 4 :

 4 Fig. 4: Probability of not receiving more than k consecutive packets.

Fig. 5 :

 5 Fig. 5: Probability of being informed at d min .

  (a) Vehicle is moving straight. (b) Vehicle is turning.

Fig. 6 :

 6 Fig. 6: Geographical destination area (GDA) for straight and left-turning vehicles.

  (a) Bicycle model (b) Pedestrian alert system

Fig. 7 :

 7 Fig. 7: Model to calculate GDA.

Fig. 8 :

 8 Fig. 8: Example of V2ProVu HMI for a vehicle approaching a pedestrian

ACKNOWLEDGMENT

This work benefits from a financial support of French funding "financement par le plan d'Avenir" and Spanish national project TRA2010-15645.