Alexandre Maurer
email: alexandre.maurer@lip6.fr

Sébastien Tixeuil
email: sebastien.tixeuil@lip6.fr

On Byzantine Broadcast in Planar Graphs

We consider the problem of reliably broadcasting information in a multihop asynchronous network in the presence of Byzantine failures: some nodes may exhibit unpredictable malicious behavior. We focus on completely decentralized solutions. Few Byzantine-robust algorithms exist for loosely connected networks. A recent solution guarantees reliable broadcast on a torus when D > 4, D being the minimal distance between two Byzantine nodes.

In this paper, we generalize this result to 4-connected planar graphs. We show that reliable broadcast can be guaranteed when D > Z, Z being the maximal number of edges per polygon. We also show that this bound on D is a lower bound for this class of graphs. Our solution has the same time complexity as a simple broadcast. This is also the first solution where the memory required increases linearly (instead of exponentially) with the size of transmitted information.

Introduction

As modern networks grow larger, they become more likely to fail, as nodes may be subject to crashes, attacks, transient bit flips, etc. To encompass all possible cases, we consider the most general model of failure: the Byzantine model [START_REF] Lamport | The byzantine generals problem[END_REF], where the failing nodes can exhibit arbitrary malicious behavior. In other words, tolerating Byzantine nodes implies guaranteeing they are not able to cause problems in the correct part of the network.

In this paper, we study the problem of reliably broadcasting information in a multihop network. In the ideal case, the source node sends the information to its neighbors, that in turn send it to their own neighbors, and so forth (this is denoted in the sequel as a "simple broadcast"). However, a single Byzantine node can forward a false information and lie to the entire network. Our goal is to design a solution that guarantees reliable broadcast in the presence of Byzantine retransmitters.

Related works. Many Byzantine-robust protocols are based on cryptography [START_REF] Castro | Practical byzantine fault tolerance[END_REF][START_REF] Vadim Drabkin | Efficient byzantine broadcast in wireless ad-hoc networks[END_REF]: the nodes use digital signatures to authenticate the sender across multiple hops. However, as the malicious nodes are supposed to ignore some cryptographic secrets, their behavior cannot be considered as entirely arbitrary. Besides, manipulating asymmetric cryptography requires important resources, which may not always be available. The most important point is that cryptography requires some degree of trusted infrastructure to initially distributes public and private keys: therefore, if this initial infrastructure fails, the whole network fails. Yet, we want to design a totally decentralized solution, where any element can fail independently without compromising the whole system. For these reasons, we focus on non-cryptographic solutions.

Cryptography-free solutions have first been studied in completely connected networks [START_REF] Lamport | The byzantine generals problem[END_REF][START_REF] Attiya | Distributed Computing: Fundamentals, Simulations, and Advanced Topics[END_REF][START_REF] Malkhi | Diffusion without false rumors: on propagating updates in a Byzantine environment[END_REF][START_REF] Malkhi | Efficient update diffusion in byzantine environments[END_REF][START_REF] Minsky | Tolerating malicious gossip[END_REF]: a node can directly communicate with any other node, which implies the presence of a channel between each pair of nodes. Therefore, these approaches are hardly scalable, as the number of channels per node can be physically limited. We thus study solutions in multihop networks, where a node must rely on other nodes to broadcast informations.

A notable class of algorithms tolerates Byzantine failures with either space [START_REF] Masuzawa | Stabilizing link-coloration of arbitrary networks with unbounded byzantine faults[END_REF][START_REF] Nesterenko | Tolerance to byzantine faults[END_REF][START_REF] Sakurai | A self-stabilizing link-coloring protocol resilient to byzantine faults in tree networks[END_REF] or time [START_REF] Masuzawa | Bounding the impact of unbounded attacks in stabilization[END_REF][START_REF] Dubois | Maximum metric spanning tree made byzantine tolerant[END_REF][START_REF] Dubois | Bounding the impact of unbounded attacks in stabilization[END_REF][START_REF] Dubois | On byzantine containment properties of the min+1 protocol[END_REF][START_REF] Dubois | The impact of topology on byzantine containment in stabilization[END_REF] locality. Space local algorithms try to contain the fault as close to its source as possible. This is only applicable to the problems where the information from distant nodes is unimportant: vertex coloring, link coloring, dining philosophers, etc. Also, time local algorithms presented so far can hold at most one Byzantine node, and are not able to mask the effect of Byzantine actions. Thus, this approach is not applicable to reliable broadcast.

In [START_REF] Dolev | The Byzantine generals strike again[END_REF], it was shown that, for agreement in the presence of up to k Byzantine nodes, it is necessary and sufficient that the network is (2k + 1)-connected, and that the number of nodes in the system is at least 3k + 1. However, this solution assumes that the topology is known to every node, and that the network is synchronous. Both requirements have been relaxed in [START_REF] Nesterenko | Discovering network topology in the presence of byzantine nodes[END_REF]: the topology is unknown and the scheduling is asynchronous. Yet, this solution retains 2k + 1 connectivity for reliable broadcast and k + 1 connectivity for failure detection.

Another existing approach is based on the fraction of Byzantine neighbors per node. Solutions have been proposed for nodes organized on a lattice [START_REF] Koo | Broadcast in radio networks tolerating byzantine adversarial behavior[END_REF][START_REF] Bhandari | On reliable broadcast in a radio network[END_REF]. Reliable broadcast was shown possible if every node has strictly less than a 1/4 fraction of Byzantine neighbors. This result was later generalized to other topologies [START_REF] Pelc | Broadcasting with locally bounded byzantine faults[END_REF], assuming that each node knows the global topology.

All aforementioned approaches are hardly applicable to loosely connected networks, where each node has a limited (possibly upper bounded by a constant) number of neighbors. For instance, on a torus topology (see Figure 1), no existing solution can tolerate more than one Byzantine node. Efficient solutions have been proposed for such networks [START_REF] Maurer | Limiting byzantine influence in multihop asynchronous networks[END_REF][START_REF] Maurer | A scalable byzantine grid[END_REF], but only give probabilistic guarantees, and require the nodes to know their position in the network. This last requirement was relaxed in [START_REF] Maurer | On byzantine broadcast in loosely connected networks[END_REF]: reliable broadcast is guaranteed on a torus when D > 4, D being the minimal number of hops between two Byzantine nodes. Our contribution. In this paper, we generalize the result of [START_REF] Maurer | On byzantine broadcast in loosely connected networks[END_REF] to 4-connected planar graphs (see Figure 1). We show that reliable broadcast can be guaranteed when D > Z, Z being the maximal number of edges per polygon. We also show that this bound is tight: if we only have D ≥ Z, no algorithm can guarantee reliable broadcast for this class of graphs.

Then, if we assume that the delay between two activations of a same process is bounded, we show that reliable broadcast can be achieved in O(d) time units, d being the network diameter. So, tolerating Byzantine failures yields the same time complexity as a simple broadcast.

Finally, we show that, unlike previous solutions [START_REF] Koo | Broadcast in radio networks tolerating byzantine adversarial behavior[END_REF][START_REF] Bhandari | On reliable broadcast in a radio network[END_REF][START_REF] Pelc | Broadcasting with locally bounded byzantine faults[END_REF][START_REF] Maurer | Limiting byzantine influence in multihop asynchronous networks[END_REF][START_REF] Maurer | A scalable byzantine grid[END_REF][START_REF] Maurer | On byzantine broadcast in loosely connected networks[END_REF], the local memory required for broadcasting is O(M ) (instead of O(2 M )), M being the maximal size of an information message.

Organization of the paper In Section 2, we present the hypotheses and describe the broadcast protocol. In Section 3, we prove the condition for reliable broadcast, and show its tightness. In Section 4, we establish the time complexity. Finally, in Section 5, we discuss about the memory requirements.

Setting

In this section, we present our hypotheses and describe the broadcast protocol.

Hypotheses

Topology Let G = (G, E) be a graph representing the topology of the network. G denotes the nodes, and E denotes the edges connecting two nodes. The graph G is planar : there exists a bi-dimensional representation of this graph where edges do not cross. Besides, we assume that the graph is 4-connected: to disconnect the graph, at least 4 nodes must be removed (see Definition 2). From this hypothesis, each node connects at least 4 edges.

As the graph is planar, the edges delimit polygons (see Figure 1 and Definition 3). Let Z ≥ 3 be the maximal number of edges per polygon, and let Y ≥ 4 be the maximal number of edges per node. Z is a parameter of the algorithm.

Network Two nodes (or processes) connected by an edge (or channel ) are called neighbors. A node can only send messages to its neighbors. Some nodes are correct and follow the protocol described thereafter. The other nodes are Byzantine, and have a totally unpredictable behavior. The correct nodes do not know which nodes are Byzantine.

We consider an asynchronous network: any message sent is eventually received, but it can be at any time. We assume that, in an infinite execution, any process is activated infinitely often; however, we make no hypothesis on the order of activation of the processes. Finally, we assume authenticated channels (or "oral" model): each node has a unique identifier, and knows the identifier of its neighbors. Therefore, when a node receives a message from a neighbor p, it knows that p is the actual author of the message.

Protocol

Preliminaries An arbitrary correct node, called the source, wants to broadcast an information m 0 in the network. We say that a correct node multicasts a message when it sends it to all its neighbors, and delivers m when it permanently considers that m was broadcast by the source. We say that we achieve reliable broadcast if all correct nodes eventually deliver m 0 .

Principle of the protocol We use the same underlying principle as in [START_REF] Maurer | On byzantine broadcast in loosely connected networks[END_REF]: to actually deliver an information message, a node must receive it from a direct neighbor q, but also (indirectly) from another node located at at most Z -2 hops. The intuitive idea is that, if two Byzantine nodes are distant from more than Z hops, they can never cooperate to make a correct node deliver a false information.

Besides generalizing the aforementioned protocol to planar graphs, our new protocol improves memory efficiency. Indeed, instead of storing all received messages in a set Rec, a correct node uses a variable Rec(q) for each neighbor q, storing only the last message received from q. This modification enables to reduce the memory required by the nodes (see Section 5).

The messages exchanged in the protocol are tuples of the form (m, S), where m is the information broadcast by the source (or pretending to be it), and S is a set containing the identifiers of the nodes already visited by the message.

Description of the protocol

• The source multicasts an arbitrary information m 0 .

• The correct nodes that are neighbors of the source wait until they receive an information m from the source, then deliver m and multicast (m, ø).

• The other correct nodes have the following behavior:

-When (m, S) is received from a neighbor q, with q / ∈ S and card(S) ≤ Z -3: assign the value (m, S) to Rec(q) and multicast (m, S ∪ {q}).

-When there exists m, p, q and S such that q = p, q / ∈ S, Rec(q) = (m, ø) and Rec(p) = (m, S): deliver m, multicast (m, ø) and stop.

Condition for reliable broadcast

In this section, we prove the main result of the paper: if D > Z, we achieve reliable broadcast. We also show that this bound on D is tight: if we only have D ≥ Z, no algorithm can guarantee reliable broadcast on this class of graphs.

Definitions

Definition 1 (Path and circular path). A path is a sequence of nodes (u 1 , . . . , u n ) such that u i and u i+1 are neighbors. This path is circular if u 1 and u n are also neighbors. Unless we mention it, we do not require that these nodes are distinct.

Definition 2 (Node-cut and k-connected network). As set S of nodes is a node-cut if the graph G -S is disconnected, that is: there exists a pair of nodes {p, q} / ∈ S such that no path connects p and q in G -S. The network is k-connected if no node-cut contains less than k nodes.

Definition 3 (Polygon).

A polygon is a circular path that does not surround any node in the bidimensionnal representation of the planar graph.

Definition 4 (Neighbor and adjacent polygons). Two polygons are neighbors if they share at least one node, and adjacent if they share an edge.

Definition 5 (Polygonal path).

A polygonal path is a sequence of polygons (P 1 , . . . , P n ) such that P i and P i+1 are adjacent.

Definition 6 (Connected polygons).

A set S of polygons is connected if, for each pair of polygons (P, Q) of S, there exists a polygonal path (P, P 1 , . . . , P n , Q) in S.

Definition 7 (Correct and Byzantine polygons).

A polygon is correct if all its nodes are correct. Otherwise, it is Byzantine.

Main theorem

Let us show that, if D > Z, we achieve reliable broadcast (Theorem 1). Lemma 1. Let us suppose that D > Z. Then, if two polygons are neighbors, the set of their nodes contains at most one Byzantine node.

Proof. The proof is by contradiction. Let us suppose the opposite: there exist two neighbor polygons P and Q, and the set of their nodes contains two distinct Byzantine nodes b 1 and b 2 .

As P and Q are neighbors, let u be a node shared by P and Q. Let (u, p 1 , . . . , p n ) be a circular path on P , and let (u, q 1 , . . . , q m ) be a circular path on Q. Therefore, (u, p 1 , . . . , p n , u, q 1 , . . . , q m ) is a circular path containing all the nodes of P and Q.

As this circular path contains at most 2Z hops, two nodes of this path are distant of at most Z hops. In particular, b 1 and b 2 are distant of at most Z hops, which contradicts D > Z. Hence, the result.

Lemma 2. Let v be a node, and let V be the set of polygons containing v. Then, v is the only node common to these polygons.

Proof. Let us suppose the opposite: the exists a node w = v common to these polygons. Let P be a polygon containing v. Let q 1 and q 2 be the two neighbors of v contained by P . Let Q 1 (resp. Q 2 ) be the polygon adjacent to P containing v and q 1 (resp. q 2 ). Let S be the set of nodes contained by P . As a polygon contains at least 3 nodes, S -{v, w} contains at least one node. Then, as w is also common to P , Q 1 and Q 2 , {v, w} is a node-cut isolating S -{v, w} from the rest of the network. This is impossible, as the network is 4-connected. Hence, the result. Lemma 3. If D > Z, each correct node belongs to at least one correct polygon.

Proof. Let us suppose the opposite: there exists a correct node v that does not belong to any correct polygon. Let V be the set of polygons containing v. Let P 1 and P 2 be two polygons of V . As P 1 and P 2 are Byzantine, according to Lemma 1, they share the same Byzantine node b Therefore, by induction, all the polygons of V share the same Byzantine node b. But according to Lemma 2, v is the only node shared by the polygons of V . Therefore, b = v, and v is Byzantine: contradiction. Hence, the result. Lemma 4. Let v be a node, and let V be the set of polygons containing v. Let X be the set of nodes contained by the polygons of V . Then, there exists a circular path (q 1 , . . . , q m ) such that nodes {q 1 , . . . , q m } are distinct and that contains all nodes of X -{v}, and only contains nodes of X.

Proof. Let (e 1 , . . . , e n ) be the edges connected to v, ordered clockwise, and let e n+1 = e 1 . Let u i be the node connected to v by e i . If, ∀i ∈ {1, . . . , n}, there exists a polygon containing the edges e i and e i+1 , go to paragraph 1. Else, go to paragraph 2.

1. Let P i be the polygon containing the edges e i and e i+1 . Let (v, u i , p i 1 , p i 2 , . . . , u i+1 ) be a circular path on P i , ordered clockwise. We define a path (u 1 , p 1 1 , p 1 2 , . . . , u 2 , p 2 1 , p 2 2 , . . . , u n+1 ) = (q 1 , . . . , q m+1 ), containing all the nodes of X -{v}. Let us show that the nodes {q 1 , . . . , q m } are distinct. Let us suppose the opposite: there exists k and k > k such that u k = u k . Then, {u k , v} is a node-cut disconnecting {u k+1 , . . . , u k -1 } from the rest of the network, which is impossible as the network is 4-connected. Thus, the nodes are distinct. Hence, the result.

2. Let k be the first integer such that e k and e k+1 do not belong to any polygon. Let us notice that there is no other integer k > k satisfying this property -otherwise, {v} would be a node-cut isolating u k from u k . Then, let (e 1 , . . . , e n ) be the edges connected to v, clockwise, such that e 1 = e k+1 .

Let P i be the polygon containing the edges e i and e i+1 . Let (v, u i , p i 1 , p i 2 , . . . , u i+1 ) be a circular path on P i , ordered clockwise. We define a path (u 1 , p 1 1 , p 1 2 , . . . , u 2 , p 2 1 , p 2 2 , . . . , u n ) = (q 1 , . . . , q m-1 ), containing all nodes of X -{v}. For the same reasons as in paragraph 1, the nodes {q 1 , . . . , q m-1 } are distinct. Hence, the result, if we take q m = v. Lemma 5. Let v be a node, and let V be the set of polygons containing v. Let S be the set of polygons that are not is V , but are neighbors with a polygon of V . Then, S is connected.

Proof. Let (q 1 , . . . , q m ) be the circular path of Lemma 4. Then, S = S 1 ∪ • • • ∪ S m , where S i is the set of polygons containing q i . If each set S i is connected, as S i and S i+1 share a polygon containing q i and q i+1 , S is connected. Now, let us suppose that there exists a k such that S k is not connected.

S k contains only two disconnected parts, otherwise {v} would be a node-cut. Let (q 1 , . . . , q m ) be a circular path containing nodes {q 1 , . . . , q m }, ordered clockwise, such that q 1 = q k . Let S 1 (resp. S m+1 ) be the part of S k containing the node q 2 (resp. q m ). ∀i ∈ {2, . . . , m}, let S i be the set of polygons containing q i. Then,

S = S 1 ∪ • • • ∪ S m = S 1 ∪ • • • ∪ S m+1 .
Let us prove the following property P i by induction, ∀i ∈ {1, . . . , m + 1}:

S 1 ∪ • • • ∪ S i is connected. • P 1 is true, as S 1 is connected.
• Let us suppose that P i is true, for i ∈ {1, . . . , m}. Let us suppose that S 1 ∪ • • • ∪ S i+1 is not connected. It implies that S i+1 is not connected. S i+1 contains only two disconnected parts, otherwise {q i+1 } would be a node-cut. Let S A i+1 be the part containing the node q i , and let S B i+1 be the other part. Then, {q 1 , v, q i+1 } is a node-cut isolating S 1 ∪ . . . S i ∪ S A i+1 from S B i+1 , which is impossible as the network is 4-connected. Thus, P i+1 is true.

Therefore, P m+1 is true, and S is connected. Lemma 6. Let us suppose that D > Z. Let (P, P 1 , . . . , P n , Q) be a polygonal path such that P and Q are correct, and {P 1 , . . . , P n } are Byzantine. Then, there exists a polygonal path

(P, Q 1 , . . . , Q m , Q) such that {Q 1 , . . . , Q m } are correct.
Proof. According to Lemma 1, P i and P i+1 share the same Byzantine node b. Therefore, by induction, the polygons {P 1 , . . . , P n } share the same Byzantine node b.

Let V be the set of polygons containing b, and let S be the set of polygons that are not in V , but are neighbors to a polygon of V . As V contains P 1 and P n , by definition, S contains P and Q. According to Lemma 5, S is connected: there exists a polygonal path (P, Q 1 , . . . , Q m , Q) in S. To complete the proof, let us show that the polygons of S are correct.

Let us suppose the opposite: there exists a polygon P of S that is Byzantine. Let b be the Byzantine node contained by P . Then, as P has a neighbor polygon in V , according to Lemma 1, b = b. It implies that P belongs to V : contradiction. Thus, the polygons of S are correct. Hence, the result. Lemma 7. If D > Z, the set of correct polygons is connected.

-If u i+1 has stopped, u i+1 has necessarily delivered an information. As D ≥ Z, according to Lemma 8, this information was m 0 . Thus, according to the protocol, u i+1 has already multicast (m 0 , ø), and P i+1 is true if we take S i+1 = ø.

-Otherwise, as card(S i ) ≤ Z -3, u i+1 multicasts (m 0 , S i ∪ {u i }). Thus, P i+1 is true if we take S i+1 = S i ∪ {u i }.

Therefore, P n-2 is true, and u n-1 receives (m 0 , S n-2 ) from u n-2 , with S n-2 ⊆ {u 1 , . . . , u n-2 } and card(S n-2 ) ≤ n -3 ≤ Z -3. Thus, for the node u n-1 , Rec(u n-2 ) = (m 0 , S n-2 ), with u n / ∈ S n-2 . Thus, as we already have Rec(u n ) = (m 0 , ø), according to the protocol, u n-1 delivers m 0 .

If E 1 is the first event to occur, by a perfectly symmetric reasoning, we show that u 2 delivers m 0 . Hence, the result. Lemma 10. Let us suppose that D ≥ Z. Let P be a correct polygon, and let p 1 and p 2 be two neighbor nodes of P that deliver m 0 . Then, all the nodes of P deliver m 0 .

Proof. Let z ≤ Z be the number of nodes of P . Let us prove the following property P i by induction, for 1 ≤ i ≤ z -1: there exists a path of i + 1 nodes of P that deliver m 0 .

• P 1 is true, as (p 1 , p 2 ) is a path of 2 nodes that deliver m 0 .

• Let us suppose that P i is true for i < z -1. Let (u 1 , . . . , u i+1 ) be a path of i + 1 nodes that deliver m 0 . Let {q 1 , . . . , q n } be n nodes such that (u 1 , . . . , u i+1 , q 1 , . . . , q n , u 1 ) is a circular path on P . Then, (u i+1 , q 1 , . . . , q n , u 1 ) is a path of correct nodes where u i+1 and u 1 deliver m 0 . Therefore, according to Lemma 9, at least one of the nodes q 1 and q n deliver m 0 . Thus, at least one of the paths (q n , u 1 , . . . , u i+1 ) and (u 1 , . . . , u i+1 , q 1 ) contains i + 2 nodes of P that deliver m 0 , and P i+1 is true.

Therefore, P z-1 is true, and the z nodes of P deliver m 0 .

Theorem 1. If D > Z, we achieve reliable broadcast.

Proof. Let s be the source and let p be a correct node. According to Lemma 3, s belongs to a correct polygon P and p belongs to a correct polygon P . According to Lemma 7, there exists a correct polygonal path (Q 1 , . . . , Q n ) such that Q 1 = P and Q n = P .

Let us prove the following property P i by induction, for 1 ≤ i ≤ n: all the nodes of Q i deliver m 0 .

• First, let us show that P 1 is true. Let q be a neighbor of s on Q 1 . As Q 1 is correct, according to the protocol, q delivers m 0 . Then, according to Lemma 10, P 1 is true.

• Let us suppose that P i is true, for i < n. Let u 1 and u 2 be the two nodes shared by Q i and Q i+1 . As P i is true, u 1 and u 2 deliver m 0 . Then, according to Lemma 10, P i+1 is true.

Thus, P n is true, and p delivers m 0 . Hence, the result.

Bounds tightness

Let us show that the bound on D (Theorem 1) cannot be improved. As there is a perfect symmetry between the 2 correct nodes and the 2 Byzantine nodes, the outer nodes can never determine m 0 with certitude, and reliable broadcast is impossible. This contradiction achieves the proof.

Nevertheless, notice that it does not make the condition D > Z necessary for all graphs: the necessary and sufficient condition to achieve byzantine resilient broadcast may be more complex than the distance between Byzantine failures. We leave this as an open question.

Time complexity

In this section, we assume that the delay between two activations of the same process has an upper bound T . Then, we show that reliable broadcast is achieved in O(d) time units, d being the diameter of the network. This is the same time complexity as a simple broadcast, where any information received is retransmitted without verification.

Lemma 11. Let p be a node located a L ≥ 1 hops from the source. Then, there exists a correct polygonal path of at most Y 3 ZL polygons connecting p to the source.

Proof. Let P be a correct polygon containing the source s, and let P be a correct polygon containing p. Such polygons exist, according to Lemma 3. Let (u 1 , . . . , u L+1 ) be a path connecting s and p, and let U i be the set of polygons containing u i . Each set U i is connected, otherwise {u i } would be a node-cut. Therefore,

U = U 1 ∪ • • • ∪ U L+1 is connected. As each set U i contains at most Y polygons, U contains at most Y (L + 1) polygons.
Therefore, there exists a polygonal path (P 1 , . . . , P n ) of at most Y(L+1) polygons, with P 1 = P and P n = P . If this path is correct, the result is trivial. Otherwise, let (P N , . . . , P M ) be a sequence of Byzantine nodes, as defined in Lemma 7.

Let us consider the proof of Lemma 5. The circular path (q 1 , . . . , q m ) contains at most Y Z nodes, and each set S i contains at most Y polygons. Thus, the set S = S 1 ∪ • Proof. Let us suppose that the source broadcasts m 0 at a date t 0 .

Let Q be a correct polygon, and let us suppose that two nodes of Q have delivered m 0 at a date t.

Then, according to the proof of Lemma 10, a third node delivers m 0 before t + ZT , and so forth. Thus, all nodes of Q deliver m 0 before t + Z 2 T . Similarly, all nodes of P deliver m 0 before t 0 + Z 2 T .

According to Lemma 11, for any node p located at L ≥ 1 hops from the source, there exists a correct polygonal path of Y 3 ZL polygons connecting this node to the source. Thus, according to the proof of Theorem 1, p delivers m 0 before t 0 + Y 3 Z 3 LT .

Therefore, as L ≤ d, reliable broadcast is achieved in Y 3 Z 3 T d time units. Thus, as Y , Z and T are bounded, reliable broadcast is achieved in a O(d) time.

Required memory

In this section, we show that our solution is the first Byzantine resilient broadcast in sparse multihop networks where the used memory increases linearly with the size of informations, and not exponentially.

Indeed, the existing solutions [START_REF] Koo | Broadcast in radio networks tolerating byzantine adversarial behavior[END_REF][START_REF] Bhandari | On reliable broadcast in a radio network[END_REF][START_REF] Nesterenko | Discovering network topology in the presence of byzantine nodes[END_REF][START_REF] Maurer | Limiting byzantine influence in multihop asynchronous networks[END_REF][START_REF] Maurer | On byzantine broadcast in loosely connected networks[END_REF][START_REF] Maurer | A scalable byzantine grid[END_REF], the nodes are supposed to store as many information messages m as necessary. However, the Byzantine nodes can potentially broadcast all possible false informations m = m 0 . This strategy is referred to as exhaustion in the literature [START_REF] Sousa | How resilient are distributed f fault/intrusion-tolerant systems[END_REF][START_REF] Sousa | Proactive resilience revisited: The delicate balance between resisting intrusions and remaining available[END_REF]. Therefore, the correct nodes implicitly require O(2 M ) bits of memory to ensure reliable broadcast, M being the maximal number of bits of an information m.

In our protocol, we made the following modification : instead of storing all the messages received, we only store the last message received from a neighbor q in the variable Rec(q). Thus, the nodes only require O(M ) bits of memory. More precisely, let us consider a finite network, and let X be the maximal number of bits of a node identifier. As the largest tuple (m, S) that a correct node can accept verifies card(S) ≤ Z, each variable Rec requires at most M + ZX bits. Thus, each correct node requires at most Y (M + ZX) bits of memory.

Concerning the memory required in channels, the problem is the same for all solutions: we must assume that the delay between two activations of a same process belongs to an interval [T 1 , T 2 ], T 1 > 0 -otherwise, the memory is impossible to bound. Indeed, let N be the smallest integer such that N > T 2 /T 1 . Then, as a node receives all the messages of its channels when activated, a channel connecting two correct nodes contains at most N tuples (m, S). Besides, if a channel is connected to a Byzantine node, it can be overflowed without consequences: it is unimportant that a Byzantine node receives messages, and the messages received from a Byzantine node are already unpredictable. Thus, each channel requires at most N (M + XZ) bits of memory.

Therefore, the local memory required in now O(M ) instead of O(2 M ).

Conclusion

We generalized the condition on the distance between Byzantine nodes to a class of planar graphs, and shown its tightness. Our solution has the same time complexity as a basic broadcast, and requires less memory than the previous solutions.

Figure 1 :

 1 Figure 1: Torus (left) and 4-connected planar graph (right)

Theorem 2 .

 2 If D ≥ Z, no algorithm can guarantee reliable broadcast on 4-connected planar graphs. Proof. Let us suppose the opposite: there exists an algorithm guaranteeing reliable broadcast on 4-connected planar graphs for D ≥ Z. Let us consider the network of Figure 2.

Figure 2 :

 2 Figure 2: Critical case for D ≥ Z

  the correct path thus obtained contains at most Y 2 Zn/2 ≤ Y 2 ZY (L + 1)/2 ≤ Y 3 ZL polygons. Theorem 3. Reliable broadcast is achieved in O(d) time units.

• • ∪ S m contains at most Y 2 Z polygons.

Therefore, according to the proof of Lemma 7, (P N , . . . , P M ) can be replaced by a sequence of at most Y 2 Z polygons. As the number of Byzantine sequences in (P 1 , . . . , P n ) is strictly inferior to n/2,

An open problem is to find more involved criteria for the placement of Byzantine failures, and to extend it to more general graphs. Also, even if we already have a linear time complexity, some optimizations could be made to further reduce the time to deliver genuine information.

Proof. Let P and Q be two correct polygons, and let (P, P 1 , . . . , P n , Q) be a polygonal path. If {P 1 , . . . , P n } are correct, the result is trivial. Otherwise, let us consider the following process.

Let N be the smallest integer such that P N is Byzantine, and let M be the smallest integer greater than N such that P M +1 is correct. Then, according to Lemma 6, there exists a polygonal path (P N -1 , Q 1 , . . . , Q m , P M +1 ) such that the polygons {Q 1 , . . . , Q m } are correct. Therefore, we can replace the sequence (P N , . . . , P M ) by (Q 1 , . . . , Q m ). We repeat this process until all the polygons of the path are correct. Lemma 8. Let us suppose that D ≥ Z. Then, if a correct node delivers an information, it is necessarily m 0 .

Proof. The proof is by contradiction. Let us suppose the opposite: D ≥ Z, yet at least one correct node delivers m = m 0 . Let u be the first correct node to deliver m . It implies that there exists p, q and S such that q = p, q / ∈ S, Rec(q) = (m , ø) and Rec(p) = (m , S).

Rec(q) = (m , ø) implies that u received (m , ø) from a neighbor q. Let us suppose that q is correct. Then, as q sent (m , ø), it implies that q delivered m . This is impossible, as u is the first correct node to deliver m . So q is necessarily Byzantine. Besides, according to the protocol, Rec(p) = (m , S) implies that card(S) ≤ Z -3.

Let us prove the following property P i by induction, for 0 ≤ i ≤ card(S): a correct node p i , located at i + 2 hops or less from q, sent (m , S i ) with card(S i ) = card(S) -i.

• First, let us show that P 0 is true. Rec(p) = (m , S) implies that p sent (m , S). Let us suppose that p is Byzantine. Then, as q is also Byzantine, D ≤ 2, which is impossible as D ≥ Z ≥ 3. So p is necessarily correct, and P 0 is true if we take p 0 = p and S 0 = S. If Z = 3, ignore the following step.

• Let us suppose that P i is true, with i < card(S). As card(S i ) = card(S)-i ≥ 1, p i necessarily received (m , S i+1 ) from a node p i+1 located at i+3 hops or less from q, with S i = S i+1 ∪{p i+1 } and p i+1 / ∈ S i+1 . Thus, we have card(S i+1 ) = card(S i ) -1 = card(S) -i -1. Let us suppose that p i+1 is Byzantine. Then, as q is also Byzantine, D ≤ i + 3 ≤ card(S) + 2 < Z, which is impossible as D ≥ Z. So p i+1 is necessarily correct, and P i+1 is true. Therefore, P card(S) is true, and p card(S) sent (m , ø), as card(S card(S) ) = card(S) -card(S) = 0. According to the protocol, it implies that p card(S) delivered m before u, which contradicts our initial hypothesis. Hence, the result. Lemma 9. Let us suppose that D ≥ Z. Let (u 1 , . . . , u n ) be a path of distinct correct nodes, with 3 ≤ n ≤ Z, such that u 1 and u n deliver m 0 . Then, at least one of the nodes u 2 and u n-1 delivers m 0 .

Proof. As u 1 and u n deliver m 0 , and therefore multicast (m 0 , ø), let E 1 and E 2 be the two following events: (E 1 ) u 2 receives (m 0 , ø) from u 1 and (E 2 ) u n-1 receives (m 0 , ø) from u n . Let us suppose that E 2 is the first event to occur. As u n delivers m 0 , according to the protocol, u n stops. Therefore, for the node u n-1 , Rec(u n ) = (m 0 , ø) until the end of the execution.

Let us prove the following property P i by induction, for 1 ≤ i ≤ n -2: u i multicasts (m 0 , S i ), with S i ⊆ {u 1 , . . . , u n-2 } and card(S i ) ≤ i -1.

• As u 1 delivers m 0 , u 1 multicasts (m 0 , ø). Therefore, P 1 is true if we take S 0 = ø • Let us suppose that P i is true, for i < n -2. Then, u i+1 receives (m 0 , S i ) from u i , with card(S i ) ≤ i -1 < n -3 ≤ Z -3. When it does, two possibilities:


Cindie Andrieu
email: cindie.andrieu@ifsttar.fr

Guillaume Saint
email: guillaume.saintpierre@ifsttar.fr

Xavier Bressaud
email: bressaud@math.univ-toulouse.fr

A moving fixed-interval filter/smoother for estimation of vehicle position using odometer and map-matched GPS

published or not. The documents may come

A moving fixed-interval filter/smoother for estimation of vehicle position using odometer and map-matched GPS

Introduction

The development of Field Operational Test (FOT) and Naturalistic Driving Study (NDS) allow to collect large databases that provide a wealth of information regarding driving behavior and more generally the interactions between driver, vehicle and/or environment factors (e.g. the SHRP 2 NDS with about 3000 vehicles in the United States for 2 years [START_REF]SHRP 2 Naturalisting Driving Study[END_REF], and the EuroFOT project with about 1000 vehicles in Europe for 1 year [START_REF]EuroFOT project[END_REF]). These mass data, generally collected from Floating Car Data (FCD), can be used both to study global effects by calculating aggregated indicators such as mean or median, and also effects at a more local scale by studying individual speed or accelerate profiles. Some studies have shown that space-speed profiles (speed versus vehicle position) are very informative to study driver behavior and the effects of some infrastructure elements (for example, behavioral studies at a signalised intersection [START_REF] Laureshyn | Automated video analysis and behavioural studies based on individual speed profiles[END_REF], or effects of traffic calm-ing measures such as speed humps and speed cushions [START_REF] Barbosa | A model of speed profiles for traffic calmed roads[END_REF]). Such studies require relatively accurate location information. Global navigation satellite systems (GNSS), such as the Global Positioning System (GPS), are commonly used for vehicle positioning and are based on measurements of the propagation time of a signal between each visible satellites and the receiver. However, GNSS performance is highly dependent on the environment, and in urban environments the signal is affected by many errors due to satellite masking and multipath. A common solution is to use additional sensors such to overcome the weaknesses of GNSS. In practice, the reliability of vehicle positioning is obtained by the coupling of GNSS that provide absolute positioning, with dead reckoning (DR) system, such as odometer and gyroscope, that provides vehicle's position relative to an initial position [5,6,7]. However, in the long term the performance of DR systems is poor due to the accumulation of measurements errors over time. Thus, positioning information from GNSS and DR systems are complementary. Many methods exist for multi-sensor vehicle navigation (e.g. neural networks [8], fuzzy logic [START_REF] Loebis | Adaptive tuning of a kalman filter via fuzzy logic for an intelligent auv navigation system[END_REF], particle filter [START_REF] Boucher | Nonlinear filtering for land vehicle navigation with gps outage[END_REF]) but Kalman filtering/smoothing techniques are the most used for their speed and ease of implementation [6,[START_REF] Ramjattan | A kalman filter model for an integrated land vehicle navigation system[END_REF][START_REF] Da | Nonlinear smoothing of dead reckoning data with gps measurements[END_REF]5,7]. The Kalman filter/smoother is a recursive algorithm to estimate a signal from noisy measurements, based on a compromise between a predictive dynamic model and a measurement model. The Kalman filter is a realtime estimator that uses only the past observations y(k) (0 ≤ k ≤ t) to estimate the state vector x(t) at the time t. The basic Kalman filter ( [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF]), based on least squares approach, is an optimal estimator under the assumptions of linearity of the system and the gaussian distribution of the errors. Some ex-1 tensions algorithms have also been developed, such as the Extended Kalman Filter (EKF) and the Unscented Kalman Filter (UKF), in the case of nonlinear systems. However, in Naturalistic Driving Studies, data are usually post-processed and it is desirable to dispose all the measurement data of the experiment in order to achieve better estimation accuracy. Estimators that take into account both past and future observations are often called smoothers. Fixed-Interval Smoothing (FIS) algorithms, based on Kalman filtering/smoothing theory, involve measurements over a given fixed time interval [0, T ] and use all the measurements y(k) (0 ≤ k ≤ T, T > t) to estimate the state vector x(t). Fixed-interval smoothers are generally two-filter smoothers based on a combination of a forward and a backward estimate : a forward pass that processes a Kalman filter, and a backward pass that operates backward in time by using the measurements after the time t. The most popular fixed-interval smoothing algorithms are the Rauch-Tung-Striebel (RTS) smoother [START_REF] Rauch | Maximum likelihood estimates of linear dynamic systems[END_REF], the Main-Fraser smoother [START_REF] Dq Mayne | A solution of the smoothing problem for linear dynamic systems[END_REF][START_REF] Fraser | A new technique for the optimal smoothing of data[END_REF] and the Wall-Willsky-Sandell smoother [START_REF] Wall | On the fixed-interval smoothing problem[END_REF]. The main drawback of these smoothers is that they require the operation of two filters. This paper presents some optimal real-time and post-processing estimators of the distance traveled by a vehicle on a road segment relative to an initial position, using odometer and map-matched GPS measurements. The main contributions of this paper are to propose a simple error model of the sensors which makes the model generalizable to other applications while being efficient, and to propose moving fixed interval filter/smoother which allow flexibility of use. In section 2, the statistical model is explained and the construction of the estimators are developed. Firstly, two real-time estimators are exposed: an asymptotically minimum variance unbiased estimator and an optimal moving fixed interval filter. Then, a generalization of the two previous filters in the post-processing case, leads to the construction of two moving fixed interval smoothers. The effectiveness of these estimators is tested and a comparison with the Kalman filter is performed in section 3 with simulated and real data. Finally, a discussion about the results is proposed.

Methodology

Statistical modelisation

The aim of this study is to estimate the vehicle position x(t i ) at time t i on a road segment. We denote {X(t) : t ∈ [0, T ]} the continuous random process representing the vehicle position on the time interval [0, T ], and {X(t i ) : i = 1, ..., n} the sampled process. Let {x(t 1 ), ..., x(t n )} a realization of this random process. Our aim is to estimate this realization from odometer and GPS noisy data. Let n and m, two integers with m ≤ n, the number of measurements respectively provided by the odometer and the GPS. In the remainder of this paper, it is assumed that the GPS measurements are map-matched, so that the vehicle is positioned on the correct road segment. Many map-matching algorithms have been developed to identify the correct road segment on which the vehicle is travelling. Most of these algorithms use navigation data from GPS and digital spatial road network data and current map-matching algorithms are described in [START_REF] Quddus | Current map-matching algorithms for transport applications: State-of-the art and future research directions[END_REF], but the choice of the correct road segment is not the subject of this study. We suppose that the correct road segment have been identified and we search to determine the vehicle location on that segment. For example, [START_REF] Taylor | Gps accuracy estimation using map-matching techniques: Applied to vehicle positioning and odometer calibration[END_REF] developed in [START_REF] Taylor | Gps accuracy estimation using map-matching techniques: Applied to vehicle positioning and odometer calibration[END_REF] a map-matching algorithm called OMMGPS that combine GPS pseudorange observations and odometer positions to provide a vehicle position at 1s epochs. In this study, the map-matched GPS measurements denoted (y gps (t 0 ), . . . , y gps (t m )) represent the curvilinear abscissa of the vehicle on the studied road segment (absolute location). GPS position data are affected by many errors including atmospheric and ionospheric errors, satellite orbit errors, satellite clock errors, and multipath errors. We represent these errors by a white Gaussian noise which is a classical hypothesis especially in Kalman filtering ( [START_REF] Grewal | Global Positioning Systems, Inertial Navigation, and Integration[END_REF], [START_REF] Scott | An optimal mapaided position estimator for tracking motor vehicles[END_REF]), even if current studies have shown that noises are non centered Gaussian distributions in urban environments but rather Gaussian mixture ( [START_REF] Viandier | Gnss pseudorange error density tracking using dirichlet process mixture[END_REF]). The odometer measurements denoted (y od (t 0 ), . . . , y od (t n )) represent the distance traveled by the vehicle from the initial position x(t 0 ) (relative location). Odometer data are affected by many errors which are divided into two categories: systematic errors related to the properties of the vehicle (mainly unequal wheel diameters and uncertainty about the wheelbase) and nonsystematic errors related to the environment (mainly wheel slippage due to slippery roads, over-acceleration, ...)( [START_REF] Borenstein | Measurement and correction of systematic odometry errors in mobile robots[END_REF]). Nonsystematic errors are very difficult to estimate because any unexpected irregularity can introduce a huge error, while systematic errors accumulate constantly over time. In our study, we propose a simple modeling of odometer errors and we represented them by a cumulative sum of centered Gaussian distributions. So the discretized observation model of these two sensors can be written as the following system:

       y od (t i ) = x(t i ) -x(t 0 ) + i k=1 ε od,k with t i = iT n , i = 1, ..., n y gps (t j ) = x(t j ) + ε gps,j with t j = jT m , j = 1, ..., m (2.1)
where ε od,i and ε gps,j are independent gaussian centered errors with respective variance σ 2 od and σ 2 gps . To simplify the model, we assume that the initial position x(t 0 ) is zero. Thus, the odometer model and the GPS model described in (2.1) differ only by measurement errors and sampling rate: a high sampling rate with accumulating errors for the odometer, and generally a lower sampling rate without accumulating errors for the GPS. The construction of an estimator x(t i ) of the vehicle position x(t i ) at the sampling time t i , i = 1, . . . , n from noisy measurements of GPS and odometer will take into account advantages and disadvantages of these two sensors. Later in the paper, we will denote λ = f od fgps the ratio between the odometer and GPS sampling frequencies (in practice, λ ≥ 1) and we will assume that λ ∈ N * , i.e. that for some time t i we have both odometer and GPS measurements.

Real-time estimator

In this section, vehicle position is estimated in realtime, i.e. the position x(t i ) at a given sampling time t i is estimated using only measurements obtained up to time t i .

Asymptotically minimum variance unbiased estimator

The main idea is to use odometer measurements, which has the advantage of having a high sampling rate and provide good accuracy in the short term, and to readjust with the GPS measurements, when they are available, to compensate for the accumulation of positional errors. Our estimator is then defined as follows:

Definition 2.1. Let λ = f od fgps ∈ N * . The estimator x ∞ RT (t i ) is a real-time estimator of the vehicle position at the given sampling time t i , i = 1, . . . , n, defined recursively as follows: For i = 1, . . . , n,

       x ∞ RT (t i ) = w 1 [ x ∞ RT (t i-1 ) + y od (t i ) -y od (t i-1 )] + w 2 y gps (t i ) if i ≡ 0 (mod λ) Otherwise, x ∞ RT (t i ) = x ∞ RT (t i-1 ) + y od (t i ) -y od (t i-1 ) (2.2) where w 1 + w 2 = 1.
In practice, the initial position is unknown, so we suppose that:

x ∞ RT (t 0 ) = y gps (t 0 ) if y gps (t 0 ) is available y od (t 0 ) otherwise
Theorem 2.1. The real-time estimator x ∞ RT defined in definition 2.1 with the following weights:

w 1 = λ r+2- √ λ r(λ r+4) 2 and w 2 = -λ r+ √ λ r(λ r+4) 2 where r = σ 2 od σ 2
gps is the ratio between the odometer and GPS variances, is an asymptotically minimum variance unbiased estimator. The asymptotic variance can be written as follows:

V ar[ x ∞ RT (t i )] → σ 2 od λ w 2 1 + 1 r w 2 2 1 -w 2 1 when t i → ∞ (2.3)
The recursive definition of the estimator given in definition 2.1 has the advantage of being simple to compute. However, in general, recursive algorithms require more computational resource than iterative algorithms. So, we give a non-recursive expression of the real-time estimator with asymptotically minimum variance x ∞ RT defined in definition 2.1. Definition 2.2. Let λ = f od fgps ∈ N * and x the floor function. The estimator x ∞ RT (t i ) is a real-time estimator, with asymptotically minimum variance, of the vehicle position at the given sampling time t i , i = 1, . . . , n, defined as follows:

x ∞ RT (t i ) = N j=1 w - j x - j (t i ) with N = i λ + 1 (2.4) 3
where for j = 1, ..., N ,

x - j (t i ) = y gps (t g - i (j) ) + i k=g - i (j)+1 (y od (t k ) -y od (t k-1 )) with g - i (j) = λ i λ -λ(j -1) (2.5)
and the weights w - j are defined by w - j = w 2 w j-1

1 if j < N w - N = w N -1 1
with (w 1 , w 2 ) the weights defined in theorem 2.1.

The equivalence with the recursive expression of the estimator x ∞ RT given in definition 2.1 is easily demonstrated by recursion. 1. It is easy to check that the sum of weights w - j is equal to one.

2. For a given sampling time t i , the estimators x - j (t i ), j = 1, . . . , N , are also estimators of the vehicle position at time t i , each estimator being associated with the j-th GPS measurement obtained before time t i as shown in Figure 1. The real-time estimator x ∞ RT is a weighted sum of these estimators.

[Figure 1 about here.] The estimator x ∞ RT defined in both (2.1) and (2.4) uses all measurements obtained up to time t i . However, with the non-recursive expression (2.4), it is possible to fix an integer N < i λ + 1 in order to obtain a "truncated" estimator that can be more advantageous to calculate from a computational point of view. In this case, the integer N represents the number of GPS measurements (available before the time t i ) used in the computation of the estimator x ∞ RT . The choice of the value of N is entirely defined by the user which implies a high flexibility in practice. We then deduce an expression of the variance of the estimator x ∞ RT with N fixed, at each sampling time t i .

Theorem 2.2. Let

N ≥ 1 an integer, r = σ 2 od σ 2 gps and λ = f od fgps ∈ N * . Let x - j , j = 1, . . . , N and w - j , j = 1, . .

. , N respectively the estimators and the weights defined in definition 2.2. Then the variance of the real-time estimator x ∞

RT at a sampling time t i , i = 1, . . . , n is written in matrix form as follows:

V ar[ x ∞ RT (t i )] = ( w -) T Σ -w - (2.6)
where w -= ( w - 1 , . . . , w - N ) T and Σ -is the N × N covariance matrix of the estimators x - j . The covariance matrix Σ -can be decomposed as follows:

Σ -= σ 2 gps (I N + rA N (d i )) (2.7)
where I N is the identity matrix of size N ,

d i = i -λ i λ is

the number of odometer measurements between t i and the first time of a GPS measurement before t i , and

A N (d i ) is a N × N matrix, function of d i , defined by: AN(di) =       di di di • • • di di di + λ di + λ • • • di + λ di di + λ di + 2λ • • • di + 2λ . . . . . . . . . . . . . . . di di + λ di + 2λ • • • di + (N -1)λ       (2.8)

Then, we can also deduce a linear form of the variance of the real-time estimator x ∞

RT at a sampling time t i , i = 1, . . . , n as follows:

V ar[ x ∞ RT (t i )] = σ 2 gps [ (1 -w 1 ) 2 + 2w 2N -1 1 (1 -w 1 ) 1 -w 2 1 + r(d i + λ w 2 1 -w 2N 1 1 -w 2 1
)]

(2.9)

where

w 1 = λ r+2- √ λ r(λ r+4) 2
is the asymptotically optimal weight defined in theorem 2.1.

Note that for a fixed N, the variance function defined in (2.9) is periodic with period λ. Moreover, since x ∞ RT is an asymptotically minimum variance estimator, the weights w - j , j = 1, . . . , N , defined in definition 2.2 are optimal when N tends to infinity, i.e. when we have an infinite number of measurements. Thus, if we assume d i = 0 and if N tends to infinity in the variance expression (2.9), we find the expression of the asymptotically variance given in (2.3). The speed of convergence of the variance of x ∞ RT defined in (2.9) to the asymptotically variance defined in (2.3) will be examined in the section 3. However, the estimator x ∞ RT is an asymptotically minimum variance estimator and it is not optimal for estimating the vehicle position at a sampling time t i close to the initial time t 0 . Therefore we have also constructed an optimal real-time estimator with minimum variance at each sampling time t i .

Minimum variance unbiased estimator for a fixed N

In the definition 2.2, we have written a real-time estimator of the vehicle position as a weighted average of the estimators x - j (j = 1, . . . , N ) and we have determined the optimal weights w - j (j = 1, . . . , N ) that minimize the asymptotic variance. In this section, we consider the same real-time estimator but we search the optimal weights w - j (j = 1, . . . , N ) that minimize the variance at each sampling time t i . Theorem 2.3. Let N ≥ 1 an integer and b = (1, . . . , 1) T a vector of length N. Assume that x - j , j = 1, . . . , N are the estimators defined in definition 2.2 and Σ -is the N × N covariance matrix of these estimators defined in theorem 2.2. The estimator x opt RT (t i ) is a real-time estimator of the vehicle position at the given sampling time t i , i = 1, . . . , n, defined as follows:

x opt RT (t i ) = N j=1 w - j x - j (t i ) (2.10)
where the weight vector w -= ( w - 1 , . . . , w - N ) T satisfies:

w -= 1 c rt (Σ -) -1 b with c rt = b T (Σ -) -1 b a constant.
(2.11)

Then, x opt RT (t i ) is a minimum variance unbiased estimator of the vehicle position at the sampling time t i , and its variance at time t i is the following:

V ar[ x opt RT (t i )] = 1 c rt (2.12)
The variance function defined in (2.12) depends on d i and is periodic with period λ. The estimator x opt RT is a minimum variance unbiased estimator at each sampling time t i for a fixed N. However, determining the optimal weights w - j requires the inversion of the covariance matrix Σ -which is inconvenient in practice. Furthermore, the expressions of the optimal weights and the variance of x opt RT are not given explicitly in terms of the integer N, which makes it difficult to study the properties of this estimator depending on N. Thus, in some cases, it may be more advantageous to use the "truncated" estimator x ∞ RT with a fixed N that have a simpler expression of weights and variance.

Post-processing estimator

In this section, we assume that data are postprocessed and we can use all the GPS and odometer measurements available on the studied time interval [0, T ]. Thus, unlike the previous section where we were restricted to use only measurements obtained up to time t i to estimate the vehicle position at the sampling time t i , the objective of this section is to use all available information to construct a more accurate estimator than the real-time estimators defined in the section 2.2.

Minimum variance unbiased estimator for a fixed N

The general idea is to extend the real-time estimator defined in definition 2.2 in case we also have measurements obtained after the sampling time t i .

Definition 2.3. Let λ = f od fgps ∈ N * and x the floor function. Assume that N ≥ 1 is a fixed integer. The estimator x P P (t i ) is a post-processing estimator of the vehicle position at the given sampling time t i , i = 1, . . . , n, defined as follows:

x P P (t i ) = N j=1 (w - j x - j (t i ) + w + j x + j (t i )) with N j=1 (w - j + w + j ) = 1 (2.13)
where for j = 1, ..., N ,

x - j (t i ) = y gps (t g - i (j) ) + i k=g - i (j)+1 (y od (t k ) -y od (t k-1 )) with g - i (j) = λ i λ -λ(j -1)
(2.14)

and x + j (t i ) = y gps (t g + i (j) ) - g + i (j) k=i+1 (y od (t k ) -y od (t k-1 )) with g + i (j) = λ i λ + λ j (2.

15)

A graph of the estimators x - j and x + j is represented in Figure 2.

In this case, the integer N represents the number of GPS measurements (available before and after the time t i ) used in the computation of the estimator (i.e. a total of 2N GPS measurements around t i ).

[Figure 2 about here.]

The following lemma gives a general expression of the variance of the post-processing estimator defined in (2.13).

Lemma 2.1. Let N ≥ 1 an integer and x - j and x + j , j = 1, . . . , N , the estimators defined in definition 2.3. Let w = ( w - 1 , . . . , w - N , w + 1 , . . . , w + N ) T the weight vector of length 2N . The variance of the post-processing estimator x P P defined in definition 2.3 can be written as follows:

V ar[ x P P (t i )] = w T Σ w (2.16)
where Σ is the 2N × 2N covariance matrix of the estimators x - j and x + j defined by Σ = Σ -0 0 Σ + with Σ -and Σ + respectively the N × N covariance matrix of the estimators x - j and x + j . Furthermore, we can decomposed Σ -and Σ + as follows:

Σ -= σ 2 gps (I N + rA N (d i )) and Σ + = σ 2 gps (I N + rA N (λ -d i )) (2.17)
where I N is the identity matrix of size N ,

d i = i -λ i
λ is the number of odometer measurements between t i and the first time of a GPS measurement before t i , and

A N (d i ) is a N × N matrix, function of d i , defined in (2.8).
Then, we search the optimal weights (w - j , w + j ) (j = 1, . . . , N ) that minimize the variance of the post-processing estimator x P P at each sampling time t i . Intuitively, we give more weight to the estimators x - j (t i ) and x + j (t i ) associated with GPS measurements obtained at times close to t i . The minimum variance unbiased estimator x opt P P (t i ) of the vehicle position at the sampling time t i is similar to the minimum variance unbiased estimator x opt RT (t i ) defined in theorem 2.3 by taking w = ( w - 1 , . . . , w - N , w + 1 , . . . , w + N ) T as weight vector, Σ defined in lemma 2.1 as covariance matrix, and b = (1, . . . , 1) T a vector of length 2N . Thus the constant c rt becomes the constant c pp = b T (Σ) -1 b. However, as in the case of the real-time estimator, the computation of the optimal weights w - j and w + j requires the inversion of the covariance matrix Σ which is inconvenient in practice. Thus, we study the post-processing estimator with asymptotically minimum variance.

Asymptotically minimum variance unbiased estimator

Theorem 2.4.

Let N ≥ 1 an integer, r = σ 2 od σ 2
gps and λ = f od fgps ∈ N * . Let x - j and x + j , j = 1, . . . , N , the estimators defined in definition 2.3. Assume that (w 1 , w 2 ) are the weights defined in theorem 2.1. Then x ∞ P P (t i ) is an asymptotically minimum variance unbiased estimator of the position of the vehicle at the sampling time t i , defined as follows:

x ∞ P P (t i ) = w 1 x - P P (t i ) + w 2 x + P P (t i ) (2.18)
where

x - P P (t i ) = N j=1
w - j x - j (t i ) and

x + P P (t i ) = N j=1 w + j x + j (t i ) (2.19) with w - j = w + j = w 2 w j-1 1 for j < N w - N = w + N = w N -1 1 .
The weights ( w 1 , w 2 ) whose sum is equal to one, can be written as follows:

w 1 = V ar[ x + P P (t i )] V ar[ x - P P (t i )] + V ar[ x + P P (t i )]
and

w 2 = V ar[ x - P P (t i )] V ar[ x - P P (t i )] + V ar[ x + P P (t i )]
where

V ar[ x - P P (t i )] = σ 2 gps [ (1 -w 1 ) 2 + 2w 2N -1 1 (1 -w 1 ) 1 -w 2 1 + r(d i + λ w 2 1 -w 2N 1 1 -w 2 1
)] and

V ar[ x + P P (t i )] = σ 2 gps [ (1 -w 1 ) 2 + 2w 2N -1 1 (1 -w 1 ) 1 -w 2 1 + r(λ 1 -w 2N 1 1 -w 2 1 -d i )].
Then, we deduce the following expression for the variance of the estimator x ∞ P P :

V ar[ x ∞ P P (t i )] = V ar[ x - P P (t i )]V ar[ x + P P (t i )] V ar[ x - P P (t i )] + V ar[ x + P P (t i )]
(2.20)

As for the asymptotically minimum variance realtime estimator, when N is fixed, we obtain a truncated estimator. The asymptotic variance is obtained when N tends to infinity in the expression (2.20).

Data processing and discussion

In this section, we present simulation and real data results and a comparison of the different estimators defined in the previous section with a classical Kalman filter. They have been obtained on a DELL T3400 workstation equipped with a Intel E8400 core 2 duo processor. The Kalman filter is constructed using only the odometer and GPS measurements in order to fairly compare this Kalman filter with the real-time estimators defined in the section 2.2. Thus, the state vector is only composed with one component x i where x i is the distance traveled by the vehicle at time t i from the initial position x 0 . The dynamic equation is given by:

x i+1 = x i + (y od,i+1 -y od,i ) + ε od,i (3.1)
where y od,i is the odometer measurement at time t i and ε od,i ∼ N (0, σ 2 od ). The measurement equation using only GPS measurement is given by:

y gps,i+1 = x i+1 + ε gps,i (3.2)
where y gps,i is the GPS measurement at time t i and ε gps,i ∼ N (0, σ 2 gps ). Then the step prediction is performed as follows:

x i+1|i = x i|i + (y od,i+1 -y od,i ) P i+1|i = P i|i + σ 2 od (3.3)
where x i|i is the state estimate at time t i knowing the measures until t i , and P i|i is the related covariance matrix of the estimation error (here, P i|i is a real number). The update step is performed as follows:

   K i+1 = P i+1|i (P i+1|i + σ 2 gps ) -1 x i+1|i+1 = x i+1|i + K i+1 (y gps,i+1 -x i+1|i ) P i+1|i+1 = (1 -K i+1 )P i+1|i (3.
4) The filter is initialized as follows:

x 0|0 = y gps (t 0 ) P 0|0 = σ 2 gps (3.5)
Later in the document, the Kalman filter will be denoted x KF RT . More details on the Kalman filter can be found in [START_REF] Chui | Kalman filtering with real-time applications[END_REF] and [START_REF] Grewal | Kalman Filtering: Theory and Practice Using MATLAB[END_REF].

Simulation results

Given a reference vehicle trajectory length of 4000m and traveled in about 300s, the odometer and mapmatched GPS data were simulated from the model 2.1 with an odometer error standard deviation σ od equal to 0.05m and a GPS error standard deviation σ gps equal to 3m. These sensor simulated data represent the measurement data y od (t i ) and y gps (t i ) at each time t i used in the calculation of each estimators. We suppose that the odometer and GPS frequencies are respectively equal to 10Hz and 1HZ, so that the ratio λ is equal to 10. 100 simulations of GPS and odometer measurements were generated, each simulation involved generating a new set of sensor data of the reference distance traveled and computing the estimated location at each time t i with each estimators defined in the previous section (real-time estimators and post-processing estimators) and with a Kalman filter. For each estimator, the Root Mean Square Error (RMSE) for all 100 simulations was computed every second (i.e. at each time t i for which a GPS measurement is available). The RMSE is a good measure of the accuracy of an estimator and has the advantage of being expressed in the same units as the quantity being estimated (i.e. in meters). The RMSE of an estimator X of a vector X is defined as follows:

RM SE( X) = M SE( X) = E(( X -X) T ( X -X)) = 1 n n i=1 ( X i -X i ) 2 (3.6)
where X i (resp. X i ) is the i-th component of the vector X (resp. X). There are other types of errors (e.g. mean absolute error, geometric average error), but the choice of the MSE is justified by its interpretation in terms of bias and variance:

M SE( X) = [Bias( X)] 2 + V ar( X) (3.7)
where Bias( X) = E[ X] -X. Thus, the best estimator between two unbiased estimators is the one that has the smallest variance, and an unbiased estimator of minimum variance is generally regarded as the best estimator possible. It is moreover well as real-time estimator x opt RT and post-processing estimator x opt P P were built.

Figures 3 and4 contain the RMSE of the vehicle location obtained with each estimator. In these two figures, the RMSE of the simulated sensors are represented by green circles for GPS and blue dots for the odometer. Each estimator (real-time and post-processing) is compared with the Kalman filter x KF RT defined in the beginning of the section 3 (denoted x_hat_RT_KF in Figure 3 and4) and represented by orange dashed line. Figure 3 presents the comparaison between the RMSE of the vehicle location obtained with the real-time estimators defined in section 2.2 and the Kalman filter x KF RT . The chocolate dashed line represent the asymptotically minimum variance estimator x ∞ RT (denoted x_hat_RT_inf in Figure 3) defined recursively in theorem 2.1 and initialized with x ∞ RT (t 0 ) = y gps (t 0 ). The turquoise line represented the truncated estimator x ∞ RT with a fixed N defined in theorem 2.2 (and denoted x_hat_RT_inf_Nfix in Figure 3) and the red line represent the minimum variance estimator x opt RT for a fixed N defined in theorem 2.3 (and denoted x_hat_RT_opt_Nfix in Figure 3). These two estimators depending on N were computed for three different values of N:

• N=4 is a small value chosen at random;

• N=20 is the threshold above which the difference between the standard deviation of the minimum variance estimator V ar[ x opt RT (t i )] defined in theorem 2.3 (with d i = 0 since the time step is 1s and the GPS frequency is 1Hz) and the square root of the asymptotic variance of x ∞ RT defined in (2.3) is less than 0.1m; • N=40 is the threshold above which the difference between the standard deviation of the truncated asymptotically minimum variance estimator V ar[ x ∞ RT (t i )] with N fixed defined in theorem 2.2 (with d i = 0) and the square root of the asymptotic variance of x ∞ RT defined in (2.3) is less than 0.1m.

Figure 3 shows that the Kalman filter is the best estimator of the vehicle location, mainly at each time t i of the beginning of the path, but after around 50s the RMSE curve of the Kalman filter and that of the asymptotically minimum variance estimator x ∞ RT are merged. Similarly, when N=20, the RMSE curve of the minimum variance estimator

V ar[ x opt RT (t i )] is approximately merged with the RMSE curve of the Kalman filter, and it is the same for the truncated version of the estimator x ∞ RT when N=40. The average and maximum RMSE of each estimator represented in Figure 3 are given in Table 1. These values confirm the results described in Figure 3. The asymptotic standard deviation achieved by all estimators and equal to V ar[ x ∞ RT (t i )] when t i → ∞ can be calculated with the formula given in (2.3). We then obtained an optimal standard deviation equal to 0.68m which corresponds approximatively to the RMSE obtained with each estimator after 50s when N is sufficiently large.

[Figure 3

about here.]

[Table 1 about here.] Figure 4 and Table 2 are similar to Figure 3 and Table 1 but with a comparison between the Kalman filter and the post-processing estimators defined in section 2.3. Thus, the turquoise line represents the truncated estimator x ∞ P P with a fixed N defined in theorem 2.4 (and denoted x_hat_PP_inf_Nfix in Figure 4) and the red line represents the minimum variance estimator x opt P P for a fixed N defined after the lemma 2.1 (and denoted x_hat_PP_opt_Nfix in Figure 4). These two estimators depending on N were computed for N=4 as in the real-time case and also for the two following values:

• N=17 is the threshold above which the difference between the standard deviation of the minimum variance estimator V ar[ x opt P P (t i )] (with d i = 0) and the square root of the asymptotic variance of x ∞ P P obtained in (2.20) when N tend to infinity, is less than 0.1m;

• N=36 is the threshold above which the difference between the standard deviation of the truncated asymptotically minimum variance estimator V ar[ x ∞ P P (t i )] with N fixed defined in theorem 2.4 (with d i = 0) and the square root of the asymptotic variance of x ∞ P P obtained in (2.20) when N tend to infinity, is less than 0.1m. Figure 4 and Table 2 show that when we use measurements obtained after time t i (post-processing case), the accuracy of the estimate of the position of the vehicle is improved and is better than using the Kalman filter except at the end of the path where a side effect appears. The asymptotic standard deviation achieved by all estimators when N is sufficiently large, except on the boundaries, and corresponding to V ar[ x ∞ P P (t i )] when N → ∞ in (2.20), is equal to 0.49m.

[Figure 4 about here.]

[Table 2 about here.]

Real data results

In this section, real data collected from a trip provided on test tracks at Versailles-Satory (France) were used. The trip length was around 4000m and a travel time of 300s. The odometer measurements have been collected on CAN (Controller Area Network) bus of the vehicle and have been provided at a 10Hz sampling frequency. Two GPS were also located on the roof of the vehicle: A GlobalSat BR-355 GPS receiver (with SIRF Star III) and a Thales Sagitta RTK-GPS receiver. The BR-355 GPS provides position measurements at a 1Hz sampling frequency with a 10m accuracy and the RTK-GPS (Real-Time Kinematic Global Positioning System) provides position measurements at a 10Hz sampling frequency with a centimeter accuracy. Thus, the RTK-GPS measurements were used as the "true" locations of the vehicle and were considered as the reference trajectory. A simple map-matching algorithm was used in order to project the GPS measurements on the road, and the position measurements from the odometer and the two GPS were synchronized in time. According to the accuracy of the sensors, we assume that the standard deviations of the errors of the odometer σ od and the GPS σ gps are respectively equal to 0.03m and 3m. The ratio λ between the odometer and GPS sampling frequencies is equal to 10 as in the previous section. Tables 3.a and 3.b contain the RMSE of the vehicle location of each estimator on the complete trip, and the total computation time of the estimated positions with each estimator at each time t i with a sampling frequency of 10Hz. The Kalman filter is compared with the real-time estimators in Table 3.a. For comparaison, the values of N are the same as in the previous section with simulated data. Contrary to previous results obtained with simulated data, Table 3.a shows that the minimum variance estimator x opt RT and the truncated version of the estimator x ∞ RT with a fixed N are better than the Kalman filter and the asymptotically minimum variance estimator x ∞ RT . However the results show that the GPS is more accuracy (RMSE=3.07m) than all the real-time estimators except the minimum variance estimator x opt RT with N=4 (RMSE=2.59m). Furthermore, increasing the interval smoothing (i.e. increase the value of N) does not improve the accuracy of the real-time estimators that depend on N. Table 3.b shows that all the post-processing estimators are better than the real-time estimators and are more accuracy than the GPS. However the computational time of the post-processing estimators are bigger than the realtime estimators mainly when N is large.

[Table 3 about here.]

Discussion

The asymptotically minimum variance estimator x ∞ RT is similar to the Kalman filter x KF RT with a fixed gain K which is optimal when the estimation time t i tends to infinity. Indeed, the weights (w 1 , w 2 ) defined in definition 2.1 and theorem 2.1 are fixed which saves computation time (twice as fast as the Kalman filter with the real data). Furthermore, the construction of x ∞ RT provides a simple expression of the asymptotic variance (equation (2.3)). However, the optimality of these weights only at infinity implies a poor accuracy of the estimator x ∞ RT at the beginning of the trip, even if its convergence to the optimal estimator is relatively fast (50s with the simulated data). Thus, when the vehicle distance traveled to be estimated is quite long in time, the estimator x ∞ RT can be more effective. By definition, the estimator x opt RT is the optimal estimator at each time t i for a N fixed and the Kalman filter x KF RT is the optimal estimator using all measurements available up to t i . Therefore, at a given time t i , the Kalman filter x KF RT (t i ) is similar to the estimator x opt RT (t i ) with N = i λ + 1 (corresponding to use all measurements up to time t i ). The Kalman filter x KF RT (t i ) then corresponds to x opt RT with a non-fixed interval filtering which increases over time. However, contrary to the simulation results, the real data results have shown that increasing the size of the interval filtering, by increasing N, does not improve the accuracy of the estimator x opt RT . Indeed, adding too much information to estimate the position at a sampling time t i can bias the estimation. Measurements obtained at times close to t i are supposed to contain the most accurate information to estimate the position at time t i unless such measures are very noisy. In the case of noisy measurements around t i , it is better to increase the interval filtering (or the interval smoothing in the post-processing case) even if the computational time increase. Thus, the best estimator could be an estimator with a variable interval filtering that would be optimal at each time t i even if the computation time of such an estimator would certainly be large. However, it is important to note that Tables 3.a and 3.b give the computational time to estimate the whole trip, i.e. a vector of size n containing the estimated distance traveled at each time t i , which benefits recursive estimators as the Kalman filter. But if we want only one estimated distance traveled at a given time t i , a recursive expression requires to compute all the estimated distance up to t i , which can significantly increase the computational time when t i is large. For example, with the real data used in section 3.2, the computational time of the estimated position at time t i = 300s is respectively 6.30ms for the Kalman filter and 2.45ms for the estimator x opt RT with N = 20. Thus, in some cases, the estimator x opt RT (t i ) is faster to compute, even if the computational time depends on the size of the interval filtering or smoothing. Finally, the estimator x opt RT (resp. x opt P P ) is accurate but requires the inversion of a matrix of size N × N (resp. 2N × 2N ) which can be a disadvantage when N is large. In such cases, the truncated version of x ∞ RT (resp. x ∞ P P ) with a fixed N can be a good alternative. Indeed, this estimator is faster to compute than x opt RT (resp. x opt P P ) for the same N and converge to the optimal estimator when N tends to infinity, even if it is on average less accuracy.

Conclusion

Some real-time and post-processing estimators of the distance traveled by a vehicle on a road segment was developed and compared to a classic Kalman filter. These estimators were based on a simple statistical error model of the odometer and the GPS which makes the model generalizable to other ap-plications. Firstly, a recursive asymptotically minimum variance filter, similar to the Kalman filter with a fixed gain K which is optimal when time tends to infinity, was developed. This estimator is two times faster to compute than the Kalman filter and converges quickly to the optimal estimator (error less than 1m after 50s with simulated data). Then, two more flexible filters was developed using only measurements included in a moving fixedinterval: an optimal filter that requires the inversion of the covariance matrix, and a truncated version of the asymptotically minimum variance filter that is less accurate but have a simpler expression of weights and variance. Real-data results have shown the interest of using moving fixed-interval filter instead of recursive filter such as the Kalman filter: the error can be averaged less than 3m with a good choice of filtering window size. Finally, two moving fixed-interval smoothers derived from the two previous filters was also developed for post-processing cases. These smoothers estimate the vehicle position at a time t by using the measurement over a specified window around t. Taking into account both past and future observations allows to achieve better estimation accuracy (error less than 2m with real data). In future work, the robustness of the estimators presented in this paper will be tested. Furthermore, this work have shown the interest of using moving fixed-interval filter/smoother but the choice of the best filtering/smoothing windows size for the whole trip is difficult. The development of a nonfixedinterval filter/smoother with an optimal windows size at each time t could be a good alternative even if it would certainly be at the expense of a higher computation time.

Calculation of asymptotically optimal weights:

The sum of weights is equal to one. Thus, the asymptotic variance can be written as a function of one variable defined on [0, 1] as follows:

ϕ(w 1 ) = σ 2 od λ w 2 1 + 1 r (1-w1) 2 1-w 2 1
. Since ϕ is convex on [0, 1], ϕ has a global minimum which satisfies the quadratic equation ϕ (w 1 ) = 0. This equation has only one solution on [0, 1]:

w 1 = λ r+2- √ λ r(λ r+4) 2 .

Proof of Theorem 2.2:

The matrix form 2.6 of the variance of x ∞ RT is derived from the definition 2.4. Furthermore, for a given sampling time t i and for j = 1, . . . , N , V ar[ x - j (t i )] = σ 2 gps +(d i +(j -1)λ) σ 2 od according to the definition of the estimators x - j given in 2.14, and

Cov( x - j (t i ), x - j (t i )) = V ar[ i k=g - i (j)+1 ε od,k ] = (d i + (j -1)λ) σ 2
od by independence of ε od,i , which proves the expression 2.17 of the covariance matrix Σ -. Now, it remains to show the linear expression 2.9 of the variance of x ∞ RT . We have shown that:

V ar[ x ∞ RT (t i )] = ( w -) T Σ -w -= σ 2 gps [( w -) T w -+ r ( w -) T A N (d i ) w -] where ( w -) T w -= N j=1 ( w - j ) 2 = w 2 2 N -1 j=1 (w 2 1 ) j-1 + (w 2 1 ) N -1 = (1 -w 1 ) 2 1-(w 2 1 ) N -1 1-w 2 1 + (w 2 1 ) N -1 = (1-w1) 2 +2w 2N -1 1 (1-w1) 1-w 2 1 and ( w -) T A N (d i ) w - = ( w -) T (d i H N + λ∆ N ) w -with H N =    1 • • • 1 . . . . . . . . . 1 • • • 1    and
∆ N =          0 • • • • • • • • • 0 . . . 1 • • • • • • 1 . . . . . . 2 • • • 2 . . . . . . . . . . . . . . . 0 1 2 • • • N -1          .
We prove easily that ( w -) T H N w - = ( N j=1 ( w - j )) 2 = 1 and if we decompose ∆ N as follows:

∆ N =       0 • • • • • • 0 . . . 1 • • • 1 . . . . . . . . . . . . 0 1 • • • 1       +          0 • • • • • • • • • 0 . . . 0 • • • • • • 0 . . . . . . 1 • • • 1 . . . . . . . . . . . . . . . 0 0 1 • • • 1          + • • • +      0 • • • • • • 0 . . . . . . . . . . . . 0 • • • • • • 0 0 • • • 0 1      = C 1 + C 2 + . . . + C N-1
we obtain that:

( w -) T ∆ N w - = N -1 k=1 (( w -) T C k w -) = N -1 k=1 ( N j=k+1 ( w - j )) 2 = N k=2 ( N j=k ( w - j )) 2 where N j=k w - j = N -1 j=k w 2 w k-1 1 1-w N -k 1 1-w1 + w N -1 1 = w k-1 1 (1 -w N -k 1 ) + w N -1 1 = w k-1 1 . Then we deduce that ( w -) T ∆ N w - = N k=2 w 2(k-1) 1 = w 2 1 -w 2N 1 1-w 2 1
which completes the proof of the expression 2.9.

Proof of Theorem 2.3:

We search the optimal weights w - = ( w - 1 , . . . , w - N ) T that minimize the variance of the estimator under the condition that the sum of weights is equal to 1, i.e. the following constraint optimization problem:

min w w T Σ -w subject to w T b = 1
This is an optimization problem of a quadratic function with an equality constraint. The Lagrange multiplier method is used to solve this optimization problem. The Lagrangian function is L(w, λ) = w T Σ -w + λ(1 -w T b) where λ is the Lagrange multiplier. The first optimality condition is:

∂L ∂w = 0 ⇔ 2Σ -w -λb = 0 ⇔ w = 1 2 λ(Σ -) -1 b
(6.1) Note that the covariance matrix Σ -is symmetric positive definite and so invertible. Adding the con-straint, we obtain:

w T b = 1 ⇔ b T w = 1 ⇔ λb T (Σ -) -1 b = 2 ⇔ λ = 2 c rt where c rt = b T (Σ -) -1 b is a constant.
Finally, substituting in (6.1), we obtain the optimal weights w -= 1 crt (Σ -) -1 b. Then, since V ar[ x opt RT (t i )] = ( w -) T Σ -w -, we deduce the expression of the variance, which completes the proof.

Proof of Lemme 2.1:

The estimators x - j and x + j are independent, so Cov( x - j (t i ), x + j (t i )) = 0, and then:

V ar[ x P P (t i )] = N j=1 {(w - j ) 2 V ar[ x - j (t i )] + (w + j ) 2 V ar[ x + j (t i )]} + 2 1≤j<j ≤N {w - j w - j Cov( x - j (t i ), x - j (t i )) + w + j w + j Cov( x + j (t i ), x + j (t i ))}
with ∀j = 1, . . . , N and j < j , the expression of V ar[ x - j (t i )] and Cov( x - j (t i ), x - j (t i )) have been proven in theorem 2.

(t i ), x + j (t i )) = V ar[ g + i (j) k=i+1 ε od,k ] = (jλ- d i ) σ 2
od by independence of ε od,i .

Proof of Theorem 2.4:

The estimator x - P P (t i ) is equivalent to the estimator x ∞ RT (t i ) defined in definition 2.2. Thus, by symmetry, we deduce the expression of x + P P (t i ) and then that the estimator x ∞ P P (t i ) defined in (2.18) is an asymptotically minimum variance unbiased estimator of the position of the vehicle at the sampling time t i . Since N j=1 w - j = N j=1 w + j = 1, we normalize x ∞ P P (t i ) weighting by ( w 1 , w 2 ) such that their sum is equal to one. The expression of weights ( w 1 , w 2 ) are then deduce by the weighted least squares method. Finally, the expression of the variance of x - P P (t i ) is derived from the equivalence between this estimator and x ∞ RT (t i ). Thus, V ar[ x - P P (t i )] = V ar[ x ∞ RT (t i )] whose expression is given in (2.9), and the expression of V ar[ x + P P (t i )] is deduced using lemma 2.1: V ar[ x + P P (t i )] = ( w -) t Σ + w -= ( w -) t σ 2 gps (I N + r A N (λ -d i )) w - which completes the proof. q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q c) RMSE when N=40

  [5] A. Lahrech, C.Boucher, and J.C. Noyer. Fusion of gps and odometer measurements for map-based vehicle navigation. In Industrial Technology, 2004. IEEE ICIT'04. 2004 IEEE International Conference on, volume 2, pages 944-948. IEEE, 2004. [6] A.N. Kealy, M. Tsakiri, and M. Stewart. Land vehicle navigation in the urban canyona kalman filter solution usingintegrated gps, glonass and dead reckoning. In Proceedings of the 12th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GPS 1999), pages 509-518, 1999. [7] L. Zhao, W.Y. Ochieng, M.A. Quddus, and R.B. Noland. An extended kalman filter algorithm for integrating gps and low cost dead reckoning system data for vehicle performance and emissions monitoring. Journal of Navigation, 56(2):257-275, 2003. [8] K.W. Chiang and N. El-Sheimy. Ins/gps integration using neural networks for land vehicle navigation applications. In Proceedings of the 15th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GPS 2002), pages 535-544, 2001.

Figure 1 :

 1 Figure 1: Graph of estimators x - j , j = 1, . . . , N .

Figure 2 :

 2 Figure 2: Graph of estimators x - j and x + j , j = 1, . . . , N .

Appendix B: Proofs of The- orems

  (y od (t k+1 )-y od (t k ))]+ w 2 y gps (t λj ), j = 1, . . . , m. Thus, the variance of the estimator can be represented as an arithmetico-geometric sequence: V ar[ x ∞

	r	ratio between the variance of the
	5 Appendix A: Nomenclature x(t i ) vehicle position at time t i , t i ∈ [0, T ] y od (t i ), y gps (t i ) odometer and map-matched GPS measurements at time t i , t i ∈ [0, T ] σ 2 od , σ 2 gps variances of the odometer and the k=λ(j-1) RT (t λj )] = odometer and the variance of the GPS λ ratio between the sampling fre-quency of the odometer and the sampling frequency of the GPS d i Number of odometer measure-ments between the time t i and the first time of a GPS measurement before t i N Number of GPS measurements used in the computation of the fixed-interval filter/smoother x KF RT (t i ) Kalman filter estimator of the ve-hicle position at time t i x ∞ RT (t i ) Real-time unbiased estimator of the vehicle position at time t i with asymptotically minimum variance x opt RT (t i ) Real-time unbiased estimator of the vehicle position at time t i with minimum variance for a fixed N x ∞ P P (t i ) Post-processing unbiased estima-tor of the vehicle position at time t i with asymptotically minimum variance x opt P P (t i ) Post-processing unbiased estima-tor of the vehicle position at time t i with minimum variance for a fixed N 6 Proof of Theorem 2.1: Unbiased: Since ε od,i and ε gps,j are centered er-rors, it is easy to prove that E[ x ∞ RT (t i ) -x(t i )] = 0, i.e. the estimator is unbiased. Convergence of variance: Considering only the sampling time where we have both odometer and GPS measurements, the two equations defined in (2.2) can be written as follows: x ∞ RT (t λj ) = w 1 [ x ∞ RT (t λ(j-1) )+ λj-1 w 2 1 V ar[ x ∞ RT (t λ(j-1) )] + w 2 1 λ σ 2 od + w 2 2 σ 2 gps , j = 1, ..., m. Since |w 2 1 | < 1, the sequence converges and its limit is σ 2 od λ w 2 1 + 1 r w 2 2 1-w 2 1 where r = σ 2 od gps σ 2 .
	GPS

Table 1 :

 1 Figure 3: RMSE of real-time estimators ( x ∞ RT and x opt RT ) and Kalman filter. Mean and maximum RMSE of the real-time estimators compared to the Kalman filter.

	q	x_gps	x_hat_RT_inf	x_hat_RT_opt_Nfix
		x_odo	x_hat_RT_inf_Nfix	x_hat_RT_KF

Table 2 :

 2 Mean and maximum RMSE of the post-processing estimators compared to the Kalman filter.

	22

Table 3 :

 3 RMSE and computing time of the real-time and post-processing estimators compared to the Kalman filter.

List of Figures

Distance (m) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q a) RMSE when N=4 Distance (m) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q b) RMSE when N=20 Distance (m) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 50 100 150 200 250 300

Time (s)

Distance (m) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q a) RMSE when N=4 Distance (m) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q b) RMSE when N=17 Distance (m) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q c) RMSE when N=36