Martin Rodriguez-Vega
email: martin.rodriguez-vega@gipsa-lab.fr

Carlos Canudas-De-Wit

Hassen Fourati

Location of turning ratio and flow sensors for flow reconstruction in large traffic networks

Keywords: Sensor location, Flow estimation, Large traffic networks

In this work we examine the problem of minimizing the number of sensors needed to completely recover the vehicular flow in a steady state traffic network. We consider two possible sensor technologies: one that allows the measurement of turning ratios at a given intersection and the other that directly measures the flow in a road. We formulate an optimization problem that finds the optimal location of both types of sensors, such that a minimum number is required.

To solve this problem, we propose a method that relies on the structure of the underlying graph, which has a quasi-linear computational complexity, resulting in less computing time when compared to other works in the literature. We evaluate our results using dynamical traffic simulations in synthetic networks.

Introduction

Traffic state monitoring and estimation play a key role in the development of intelligent transportation systems. Because of the high installation and maintenance cost of sensors, it is of great importance to efficiently locate the least amount of sensors that give enough information about the network state. Fortunately, as different sensing technologies start to become available at a smaller cost, heterogeneous data can be incorporated in a cooperative way in order to optimize the information while minimizing the sensing locations.

In this paper, we consider the use of two types of sensing technologies to reconstruct the state of the traffic network. Flow sensors are installed in road segments and return the number of vehicles that passed over the location during a period of time. On the other hand, turning ratio sensors are installed on intersections and can estimate the percentage of vehicles turning to any of the exits of the junction. In contrast to flow sensors, turning ratio sensors are required to measure routing choices, and not necessarily total flow. For instance, [START_REF] Abbott-Jard | Empirical evaluation of Bluetooth and Wifi scanning for road transport[END_REF] and [START_REF] Bhaskar | Bluetooth vehicle trajectory by fusing bluetooth and loops: Motorway travel time statistics[END_REF] studied the use of Bluetooth and WiFi technology to obtain vehicle trajectories, and by identifying entry/exit road pairs in intersections, routing proportions can be estimated. This strategy does not provide the total flow since the penetration rate is usually unknown. A different strategy is the use of data recollection campaigns with mobile flow sensors to construct a database of average routing behavior. Other methods were briefly discussed by [START_REF] Bianco | A Network Based Model for Traffic Sensor Location with Implications on O/D Matrix Estimates[END_REF].

In the literature, different approaches have been considered for the determination of the minimum number of sensors according to the degree of knowledge of the network and the available sensing technologies. [START_REF] Bianco | A Network Based Model for Traffic Sensor Location with Implications on O/D Matrix Estimates[END_REF] defined the region of influence of flow sensors located at intersections, and with the knowledge of turning ratios in the network, they were able to provide necessary conditions for flow observability and some heuristic bounds on the number of sensors. [START_REF] Bianco | Combinatorial aspects of the sensor location problem[END_REF] performed a deeper analysis and determined that the sensor location problem is NP-complete. Some methods, developed by [START_REF] Castillo | The observability problem in traffic models: Algebraic and topological methods[END_REF] and [START_REF] Hu | Identification of vehicle sensor locations for link-based network traffic applications[END_REF] formulated the problem by enumerating all possible paths of the network to construct a matrix of constraints to give bounds on the required number of sensors to achieve flow reconstruction. Furthermore, they analyzed the effect of different network topologies on these bounds. Additionally, if there is available information about unused paths, [START_REF] Castillo | Deriving the upper bound of the number of sensors required to know all link flows in a traffic network[END_REF] and [START_REF] Castillo | Nonplanar hole-generated networks and link flow observability based on link counters[END_REF] provided extensions to reduce the number of possibilities that need to be enumerated. [START_REF] Hu | A generalized sensor location model for the estimation of network origin-destination matrices[END_REF] and [START_REF] Fu | Heterogeneous sensor location model for path reconstruction[END_REF] used these methods to consider the use of not only stationary flow sensors, but also active sensors capable of providing floating car data.

A different alternative was presented by [START_REF] Ng | Synergistic sensor location for link flow inference without path enumeration: A node-based approach[END_REF], who considered the conservation of flow equations at intersections instead of path flows. This method requires no enumeration of paths and is able to calculate the number of sensors as a function of the number of nodes and edges in a graph. Additionally, they proposed an algorithm for flow sensor location. This method was improved by [START_REF] He | A graphical approach to identify sensor locations for link flow inference[END_REF], who provided an efficient algorithm based on the topology of the network and graph theory. However, as this approach uses little assumptions about the network (only topology is used), the number of sensors may be large for real applications [START_REF] Viti | Assessing partial observability in network sensor location problems[END_REF].

More robust approaches to this problem have also been studied. [START_REF] He | A graphical approach to identify sensor locations for link flow inference[END_REF], [START_REF] Viti | Assessing partial observability in network sensor location problems[END_REF] and [START_REF] Rinaldi | Exact and approximate route set generation for resilient partial observability in sensor location problems[END_REF] proposed methods to assess and locate sensors for partial observability, i.e. only some of the flows of the network are reconstructed. Other works such as [START_REF] Xu | Robust network sensor location for complete link flow observability under uncertainty[END_REF] and [START_REF] Lovisari | Density/Flow reconstruction via heterogeneous sources and Optimal Sensor Placement in road networks[END_REF] deal with measurement noise presenting a trade-off between the number of sensors and the quality of flow reconstruction. More complete reviews about models and methods used for flow reconstruction and sensor location can be found in [START_REF] Gentili | Locating sensors on traffic networks: Models, challenges and research opportunities[END_REF] and [START_REF] Castillo | A State-of-The-Art Review of the Sensor Location, Flow Observability, Estimation, and Prediction Problems in Traffic Networks[END_REF].

Our contribution in this paper consists in solving the sensor location problem by considering flow and turning ratio sensors. This allows for a cost trade-off between these sensing technologies which can reduce the total number of sensors. The method only relies on knowledge of network topology, and does not require any knowledge about route choices or O/D paths which may be hard to obtain in certain cases. Additionally, we noted while studying the literature that most Element of matrix A at row i and column j. v(j) j-th component of vector v.

of the proposed methods present a high computational complexity. We propose sensor location algorithms that allow for complete flow reconstruction with the minimal number of sensors, with quasi-linear complexity with respect to the number of intersections and roads. Thus, these algorithms can be used for very large traffic networks.

Notation and definitions

In this paper, calligraphic letters A are used for sets, uppercase letters A are used for matrices, boldface lowercase letters a are used for vectors, and lowercase letters a are used for scalars. Some basic notations used throughout this work are shown in Table 1.

We represent traffic networks by means of a directed graph. The nodes of the graph are partitioned in two disjoint sets C and N: C corresponds to source and sink nodes of the network and N = {1, 2, . . . , n N } represents intersections which are not able to generate or store vehicular flow. The edges E = {1, 2, . . . , n E } represent the set of roads of the network. Denote I(k) as the set of incoming edges to some node k and O(k) as the set of outgoing edges from k. We define a partition of E in three sets: E in = k∈C O(k) are the boundary incoming roads, E out = k∈C I(k) are the boundary outgoing roads, and

E net = E \ (E in ∪ E out )
are the internal roads of the network. Definition 1. A feasible traffic network is a directed graph {C ∪ N, E} such that the following conditions are met:

• Every edge is part of a path that starts with an edge from E in and ends with an edge from E out .

• The graph contains no self loops.

• ∀k ∈ N we have

I(k) ∩ E out = ∅ and O(k) ∩ E in = ∅.
• There is no production or storage of vehicles in the nodes in N.

Definition 2. A turning ratio r i,j is the percentage of vehicular flow in road i ∈ E that turns to road j ∈ E at some intersection k ∈ N for which i ∈ I(k) and j ∈ O(k).

From now on if two roads i and j are not connected to the same node as indicated in Definition 2, we denote r i,j = 0.

Problem statement

Our problem is to locate flow and turning ratio sensors such that the road flows (also known as link or edge flows) of the network can be inferred from the measurements while minimizing the number of sensors. In the literature this is known as the network sensor location problem, [START_REF] Hu | Identification of vehicle sensor locations for link-based network traffic applications[END_REF][START_REF] Hu | Integrated determination of network origin-destination trip matrix and heterogeneous sensor selection and location strategy[END_REF]. We point out that we do not recover path or origin-destination flows in this paper.

To formulate this problem, we must first define the linear constraints that arise from the flow conservation equations.

Flow conservation equations at intersections

As we are considering steady-state, each road e ∈ E is characterized by a unique vehicular flow ϕ e . From the definition of the turning ratios (Definition 2), each of the outgoing flows of any intersection k ∈ N can be expressed as the sum of the contributions of the incoming flows weighted by the corresponding turning ratio:

ϕ j - i∈I(k) r i,j ϕ i = 0 , ∀j ∈ O(k). (1)
Additionally, the flow conservation requires that the total incoming flow must be equal to the total outgoing flow:

j∈O(k) ϕ j - i∈I(k) ϕ i = 0. (2)
Note that these two equations imply that j r i,j = 1. It can be seen that eq. ( 1) can only be used when the turning ratios are known. Let R ⊆ N be the set of intersections equipped with turning ratio sensors. For each of the outgoing edges of the intersections in R, an equation following (1) can be written. Define matrix A(R) as the collection of the resulting equations for all intersections in R:

A(R) i,j = 1 if e i = j -r j,ei else , (3)
where e i is the i-th element of the ordered set k∈R O(k). As an edge can only belong to one source node, it is clear that the sets O(k) for all k ∈ N are mutually disjoint. Therefore, the number of rows of

A(R) is | k∈R O(k)| = k∈R deg out (k)
, where deg out (k) is the out-degree (number of outgoing edges) of node k.

Let U = N \ R be the set of unmeasured intersections. Following a similar discussion to R, each of the intersections in U has assigned an equation analogue to (2). Define matrix B(U) as the collection of resulting equations for each k ∈ U:

B(U) i,j =    1 if j ∈ O(k i ) -1 if j ∈ I(k i ) 0 else , ( 4
)
where k i is the i-th element of the ordered set U. Check that B(U) has size

(n N -n R ) × n E with n R = |R|.

System of linear constraints

To represent the location of flow sensors, let S ⊆ E be the set of roads with cardinality |S| = n s equipped with flow sensors. We define a matrix C(S) ∈ {0, 1} ns×n E such that C(S) i,j = 1 if the i-th sensor is located in the j-th road. Note that we can write

C(S) = [u e1 u e2 • • • u en S ] T
, where e i is the i-th element of the set S. We assume that the elements of S are distinct, and so rank C(S) = n S .

Using these matrices, we can write the linear constraints on the system.

L(R) C(S) ϕ = 0 ϕ m , (5)
where

L(R) = [A(R) T B(U) T ]
T and ϕ m are the measurements given by the flow sensors. {v + , v -} where v + is a source node and v -is a sink node. Additionally, the intersections are denoted by N = {1, 2, . . . , 6} and the roads by E = {1, 2, . . . , 11}. Assume that turning ratio sensors are located at intersection R = {2, 3}, and thus U = {1, 4, 5, 6}. Applying the previous description, the linear constraint matrices are

A(R) = ϕ 1 ϕ 2 ϕ 3 ϕ 4 ϕ 5 ϕ 6 ϕ 7 ϕ 8 ϕ 9 ϕ 10 ϕ 11                     ϕ 3 0 -r 23 1 0 -r 53 0 0 0 0 0 ϕ 6 0 -r 26 0 0 -r 56 1 0 0 0 0 ϕ 4 0 0 0 1 0 0 0 -r 84 -r 94 0 ϕ 5 0 0 0 0 1 0 0 -r 85 -r 95 0 ϕ 7 0 0 0 0 0 0 1 -r 87 -r 97 0 , B(U) = ϕ 1 ϕ 2 ϕ 3 ϕ 4 ϕ 5 ϕ 6 ϕ 7 ϕ 8 ϕ 9 ϕ 10 ϕ 11               1 1 0 -1 -1 0 0 0 0 0 0 0 4 0 0 0 0 0 -1 -1 0 0 1 0 5 0 0 0 0 0 0 0 1 0 0 -1 6 0 0 0 0 0 0 0 0 1 -1 1 .
The first two rows of A(R) correspond to the outgoing edges of intersection 2 (roads 3 and 6), and the last three rows are related to the outgoing edges of intersection 3 (roads 4, 5 and 7). Similarly, each of the rows of B(U) are associated with intersections 1, 4, 5 and 6. Now consider that sensors are located at edges S = {1, 9}. The resulting sensing matrix is

C(S) = ϕ 1 ϕ 2 ϕ 3 ϕ 4 ϕ 5 ϕ 6 ϕ 7 ϕ 8 ϕ 9 ϕ 10 ϕ 11 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 .
Note that the first row of C(S) is u T 1 and the second one is u T 9 . As a specific case, let the turning ratios be such that the input flows 2, 5, 8 and 9 are distributed evenly to their corresponding destinations. It is straightforward to check that rank

    A(R) B(U) C(S)     = 11.
Therefore, this matrix is invertible and flow reconstruction can be done.

It is clear that the system (5) has a solution when the matrix in the left hand side has rank equal to the number of columns (the number of roads in the network n E ). Therefore, the condition for full road flow observability is rank

L(R) C(S) = n E . (6)

Network sensor location problem

Our objective is to find the minimum number of flow and turning ratio sensors and their positions. For the moment, we will consider the scenario where the number of turning ratio sensors |R| is a known number n R and the number of flow sensors |S| is minimized. Later, in Section 6, we will expand the results to the general case where both |R| and |S| are the decision variables.

The problem formulation is to find the optimal sets R * and S * that solve

R * , S * = argmin R,S |S| subject to rank L(R) C(S) = n E |R| = n R , (7)
where n R is a given number of intersections to be equipped with turning ratio sensors.

Proposition 1. For any n R ∈ {0, 1, . . . , n N }, problem (7) has at least one feasible solution.

Proof.

Consider S = E for which C(E) = I n E . It is straightforward that rank L(R) C(E)
= n E for any matrix L(R). This selection of sets R, S satisfies the constraints, hence the feasible set is non empty.

It can be seen that this problem is combinatorial. Using a brute force approach, i.e. calculate the cost for every possible combination and selecting the optimal one, would require O((n N /n R )

n R 2 n E ) operations, which is expensive to solve. Because of this, we consider a partition of this problem into two problems with a lower degree of complexity. The first consists in independently calculating the optimal set of turning ratio sensors as

R * = argmax R rank L(R) subject to |R| = n R . ( 8
)
Once we find the set R * , the second problem consists in finding any set S * that satisfies the following conditions:

find any S * ⊆ E such that rank C(S * ) = n E -rank L(R * ) rank L(R * ) C(S * ) = rank C(S * ) + rank L(R * ) . (9)
Next, we show that solving problems (8) and ( 9) is equivalent to solving problem (7).

Lemma 1. For any given set R * ⊆ N, problem (9) has at least one solution.

Proof. From the definition of L(R * ), it can be seen that

0 < rank L(R * ) ≤ k∈N deg out (k) < n E . Consider S = E so C(E) = I, and rank C(E) = n E . It follows that rank C(E) + rank L(R * ) > n E . However, rank L(R * ) C(E)
= n E , so some rows of C(E) are linear combinations of the other rows. We can find a solution with the following iterative process:

1. Initialize S = E. 2. While rank L(R * ) + rank C(S) > n E 2.1 Find s ∈ S such that the corresponding row of C(S) is linear combi- nation of the other rows of the matrix. 2.2 Assign S ← S \ {s} 3. Define S * ← S
As the process only removes redundant rows, the rank of the augmented matrix is still equal to n E . Additionally, the algorithm only ends when rank L(R * )+ rank C(S) = n E . Therefore, for a given R * , it is always possible to find an S * which satisfies the constraints.

Lemma 2. Let R * , S * be an optimal solution to problem (7). Then, the rows of matrices L(R * ) and C(S * ) are linearly independent.

Proof. We proceed by contradiction. Assume that the rows of C(S * ) are not linearly independent to the rows of L(R * ). There exist at least one row of C(S * ), u T s such that s ∈ S * , which is a linear combination of the rows of

L(R * ) C(S * ) .
Define a new set S = S * \ {s}. Matrix C(S ) is the same as C(S * ) but with row u T s removed. It is evident that rank

L(R * ) C(S ) = n E so the constraints are still satisfied. Additionally, |S | = n * S -1 < |S * |, making S * non optimal, which is a contradiction. Theorem 1. R * , S * is a solution to (7) if and only if R * is a solution to (8) and S * is a solution to (9). Proof. Recall, by construction, rank C(S) = |S| for any S ⊆ E.
First, we prove implication. Assume that R * , S * is a solution to (7). From Lemma 2 and the constraints of ( 7), it is evident that S * is a solution to (9). Assume there exists R , |R | = n R such that rank L(R ) > rank L(R * ). Because of Lemma 1, we can find S satisfying (9). It is easy to check that the pair R , S lie in the feasible region of (7), and that |S | < |S * |. This implies that S * is not an optimal solution. This is a contradiction, so this R cannot exist and therefore, rank

L(R * ) ≥ rank L(R) for any R, |R| = n R , so R * is a solution to (8).
Now we proceed to necessity. Assume that R * is a solution to (8) and S * is a solution to (9), so |S * | = n E -rank L(R * ). Consider that the pair R , S is an optimal solution to ( 7 As these problems can be solved separately, complexity is reduced. However, problem (8) still requires to try out O((n N /n R )

n R ) combinations, and

problem (9) has O(n rank L(R * ) E
) possible combinations which in turns require to calculate the rank of big matrices. In the following sections we provide efficient solutions to these problems.

Optimal location of turning ratio sensors

Theorem 2 (later in this section) allows to write rank of matrix L(R) for any R as a function of the number of intersections in the network and their out-degrees, i.e.

rank L(R) = n N -n R + k∈R deg out (k). ( 10
)
Using this expression, problem (8) can be rewritten as

R * = argmax R k∈R deg out (k) subject to |R| = n R . ( 11
)
To solve this problem, we propose the following algorithm:

Algorithm 1. Location of turning ratio sensors Inputs: Directed graph {C ∪ N, E} and number of turning ratio sensors n R .

Output: Set of intersections R * .

1. Calculate the vector of out-degrees:

d(k) ← deg out (k), ∀k ∈ N.
2. Sort d from highest to lowest and return the sorting vector λ, i.e. λ( 1) is the index of the highest element of d, λ(2) is the index of the second highest, and so on.

3. Construct R * ← {λ(1), λ(2), . . . , λ(n R )}.
Remark: Several solutions are possible depending on the multiplicity of the out-degrees of the nodes of the network, however, all these solutions are optimal.

Example 2. Consider the traffic network shown in Figure 1. Furthermore, assume that n R = 2. By applying Algorithm 1 to these inputs we obtain:

1. The vector of out-degrees is d = [1 2 3 1 1 2] T .
2. After sorting d, the resulting sorting vector is λ = [3 2 6 1 4 5] T . 3. The output is found by selecting the first two elements of λ: R * = {2, 3}.

Note however that there are several nodes with the same out-degree. Because of this, the set {3, 6} would also be a solution to problem (11).

The following propositions show that problem (8) can be converted into problem (11).

Lemma 3. For any feasible traffic network {C ∪ N, E} (see Definition 1) and any set of intersections R ⊆ N, matrix A(R) is full row rank.

Proof. Without loss of generality assume that the ordering of the elements of E is such that the smaller indexes correspond to E in , followed by E net and ending with

E out . Denote |E in | = n in and |E out | = n out .
For now, let R = N. Using the proposed indexing, we can write

A(N) i,j = 1 if i = j + n in -r j,i+nin else , for i = 1, 2, . . . , n E -n in and j = 1, 2, . . . , n E . We can split A(N) = [X Y ]
where Y is a square matrix of size n E -n in and can be written as Y = I -R T with R i,j = r i+nin,j+nin for i, j ∈ {1, 2, . . . , n En in }. Matrix R has the following properties:

1. The diagonal entries of R are zero as r i,i = 0. 2. All roads in E out have no downstream neighbors, so r i,j = 0 , ∀i ∈ E out .

Thus, the last n out rows of R are zero. Nevertheless, by flow conservation, all the other rows of R sum to 1. 3. For every row i of R there is a sequence of nonzero elements of R of the form R i,i1 , R i1,i2 , . . . , R iq,j such that j ∈ E out .

Properties 1 and 2 imply that Y T is weakly diagonally dominant matrix, i.e.

Y i,i ≥ | j =i Y i,j |,
where the strict inequality is true only for the last n out rows. Nevertheless, property 3 states that for every row i, there is a sequence of nonzero elements that connect row i to one of the last n out rows. Because of this, Y T is a special type of matrix called weakly chained diagonally dominant, which is known to be non-singular [START_REF] Shivakumar | A Sufficient Condition for Nonvanishing of Determinants[END_REF]]. Thus all rows of A(N) form a linearly independent set. For any arbitrary R ⊆ N, the resulting matrix A(R) is just a reduced version of A(N) with some of its rows removed. As the rows A(N) are linearly independent, it is straightforward that A(R) is full row rank as well.

Lemma 4. For any feasible traffic network {C ∪ N, E} (see Definition 1) and any set of intersections U ⊆ N, matrix B(U) is full row rank.

Proof. Initially assume that U = N. By construction, each column of B(N) ∈ {-1, 0, 1} n N ×n E has only 2 non-zero entries which sum to 0. The only exceptions are columns corresponding to indexes E in which have only one non-zero element equal to -1, and columns corresponding to indexes E out with one non-zero entry equal to 1. Note that B(N) is the incidence matrix of {N, E}.

We proceed by contradiction. Assume that B(N) is not full rank. This implies that there exist two sets

U 1 ⊂ N and U 2 ⊂ N such that k∈U1 B(N) k,j = -k∈U2 B(N) k,j , ∀j, which is equivalent to k∈U1 O(k) = k∈U2 I(k) and k∈U1 I(k) = k∈U2 O(k).
This means that for every node in U 1 , any downstream neighbor must be a member of U 1 or U 2 . Subsequently, any downstream chain of nodes must be contained in one of these two sets. As every edge is part of path ending in an element of E out , the previous statements imply that there exists a node k ∈ N such that I(k) ∩ E out = ∅, which is a contradiction. Hence, the rows of B(N) form a linearly independent set. Following a similar discussion as at the end of the proof of Lemma 3, we note that for U ⊆ N, the corresponding B(U) implies only the removal of rows from B(N), so the remaining rows are still linearly independent, and thus B(U) is full row rank.

Theorem 2. For any feasible network {C∪N, E}, and sets R ⊆ N and U = N\R, it holds that rank L(R) = rank A(R) + rank B(U).

Proof. For an arbitrary k ∈ N, we can check that 1 T A({k}) = B({k}). This is due to the fact that i r i,j = 1 for all j, and that r i,j = 0 if j is not a downstream neighbor of i. Conversely, 1 T A({k}) and B({p}) share no non-zero

entries for k = p, because O(k) ∩ O(p) = ∅ and I(k) ∩ I(p) = ∅ if k = p.
Thus, for an arbitrary set K ⊆ N, each row of B(K) can be obtained by the combination of unique rows of A(K). As R ∩ U = ∅, no row of B(U) can be written as a combination of rows of A(R), so both matrices have linearly independent rows.

Optimal location of flow sensors

In this section we discuss an efficient solution to problem (9). The following Corollary provides a way to calculate the optimal number of flow sensors n * s . Corollary 1. For any feasible traffic network {C ∪ N, E} and any set of intersections R * ⊆ N with cardinality n R , the minimum number of flow sensors required to infer all flows in the network is

n * s = n E -n N + n R - k∈R * deg out (k). ( 12
)
Proof. Let S * be an optimal solution to (9), so

n * S = |S * | = rank C(S * ) = n E -rank L(R *
). Thus, the corollary follows directly from Theorem 2.

To solve the sensor location problem we require a method that locates the number of sensors indicated in the corollary in such a way that the rows of C(S * ) and the rows of L(R * ) are linearly independent.

Because of the efficiency and simplicity of graph-based approaches such as the one of [START_REF] He | A graphical approach to identify sensor locations for link flow inference[END_REF], we decided to expand these techniques to include partial information of turning ratios. We propose Algorithm 2 which makes use of the topological structure of the traffic network and the information given by the set R * . The algorithm creates spanning trees of the input graph by using the well known Depth First Search (DFS), which is a well known graph traversal algorithm. 1. Replace all nodes in C with a single node v 0 such that E in = O(v 0 ) and

E out = I(v 0 ). 2. Initialize E R ← ∅ and E ← E. For each k ∈ R * : 2.1 Find {e 1 , e 2 , . . . , e q } = O(k). 2.2 Assign E R ← {e 2 , . . . , e q }. 2.3 Assign E ← E \ E R . 3.
Ignoring edge direction, perform a depth first search (DFS) over {N ∪ {v 0 }, E } starting at v 0 . Denote N T and E T as the visited nodes and edges, respectively.

4. While R * \ N T = ∅: 4.1 For each k ∈ R * \ N T : 4.1.1 Construct M k = {m ∈ N | ∃j ∈ O(k) ∩ I(m) ∩ E R }. 4.1.2 If ∃m ∈ M k ∩ N T : 4.1.2.1 Find j ∈ O(k) ∩ I(m). 4.1.2.2 Return k and j. Exit loop. 4.2 Find e 1 ∈ O(k) ∩ E . 4.3 Assign E ← E \ {e 1 } 4.4 Assign E R ← (E R \ {j}) ∪ {e 1 } 4.5
← N T ∪ N k . 4.7 Assign E T ← E T ∪ E k ∪ {j}. 5. Assign S * = E \ E T .
Remark: for the case R * = ∅, only steps 1, 3 and 5 are performed, and our algorithm becomes the same as the one presented in [START_REF] He | A graphical approach to identify sensor locations for link flow inference[END_REF].

The first step of the algorithm aggregates the sources and sinks into a single node. The resulting node will satisfy the flow conservation equations and will make the graph strongly connected.

Step 2 removes all but one of the outgoing edges for each of the nodes in R * . Then, step 3 constructs a tree from the remaining edges. However, because of the removal of edges in step 2, the resulting graph may become disconnected, so the DFS algorithm may not reach all of the nodes in the graph. Step 4 redoes the removal of outgoing edges from R * such that the resulting graph is connected, and finishes the construction of a spanning tree of the original graph. Finally, flow sensors are located in edges which are not included in the spanning tree or the removed edges.

Remark: The removal of links in step 2 and the construction of spanning trees using the DFS algorithm are not unique, and alternative node and edge indexing might yield different sensor configuration. Nevertheless, all multiple solutions provide the same number of sensors, and are thus equally optimal.

Example 3. Consider the traffic network shown in Figure 1. Let R * = {2, 3} as obtained in Example 2. The optimal location of flow sensors is given by Algorithm 2: the application of step 1 will generate the graph shown in Figure 2. During step 2 the algorithm iterates over the elements of R * . For intersection 2, it can be seen that O(2) = {3, 6}, where edge 6 is arbitrarily selected and added to set E R . Similarly for node 3, O(3) = {4, 5, 7}, and edges 4 and 5 are arbitrarily selected and added to E R . Then, E R = {4, 5, 6} is removed from the graph. The resulting graph is shown in Figure 3. Next, step 3 performs a DFS staring at v 0 yielding N T = {v 0 , 1, 2} and E T = {2, 3}. However, it can be seen that the graph of Figure 3 is disconnected and that intersection 3 does not belong to the visited nodes N T . Thus, we proceed with step 4, where we search for a node in R * that has an outgoing edge that connects to one of the nodes in N T , i.e. node 3. Recall that in step 2, edge 7 was arbitrarily selected to remain in the graph. We now remove edge 7 from the graph and add it to E R . Then, we perform a DFS staring from node 3, adding the visited nodes N 3 = {3, 4, 5, 6} and edges E 3 = {8, 10, 11} to N T and E T . Finally, edge 4 is removed from E R and added to E T , hence reconnecting the disconnected components (see Figure 4). After these steps, the visited nodes are N T = {v 0 , 1, 2, 3, 4, 5, 6} and the visited edges are E T = {2, 3, 4, 8, 10, 11}. Figure 4 shows the resulting graph, where the edges belonging to E T are shown in blue and the remaining edges are marked in red. Note that the subgraph {N T , E T } contains all the nodes, is connected, and has no cycles. Thus, it is a spanning tree of the original input. Finally, sensors are located in the remaining edges S * = {1, 9}, shown with boxes in the figure .   In Appendix A we show that the output of Algorithm 2 is indeed a solution to Problem (9).

Cost minimization

Until now, we considered the case where the number of turning ratio sensors was fixed and the number of flow sensors was minimized. Nevertheless, another case of interest might be when the quantities of both sensors are to be decided such that another variable (e.g. installation cost) is the decision criteria. This can be formulated as, argmin

R,S c S |S| + c R |R| subject to rank L(R) C(S) = n E , (13)
where c R , c S are the overall costs of the turning ratio and flow sensors, respectively. For the rest of this section, we will write |S| = n S and |R| = n R to simplify notation.

In the previous sections it was shown that for any fixed n R the minimum number of flow sensors corresponds to

n S = n E -n N + n R - k∈R deg out (k).
Without loss of generality, assume a permutation of the node indexing such that deg out (k) ≥ deg out (k + 1) for all k ∈ N. This can be achieved by the sorting operation used in Algorithm 1. With this indexing, we define

f (k) = k m=1 deg out (m) , k ∈ N. ( 14
)
To solve (13), first find the value of n R that satisfies

argmin n R c S n S + c R n R subject to n S = n E -n N + n R -f (n R ) 0 ≤ n R ≤ n N , (15)
and then use this number as an input to Algorithms 1 and 2. It is straightforward to check that this procedure provides a solution to (13): for any n R , it was shown that the algorithms generate sets S and R that satisfies the constraints of ( 13) and ( 15). Problem ( 15) can be simplified to

argmin n R (c S + c R )n R -c S f (n R ) subject to 0 ≤ n R ≤ n N . (16)
Due to the choice of node indexing, deg out (k) is non-increasing, and therefore, f (k) is concave. The cost function in ( 16) is then convex, so gradient-based approaches are guaranteed to work. After straightforward manipulations we find that the optimal n R is such that

deg out (n R ) ≥ c S + c R c S ≥ deg out (n R + 1). ( 17
)
This problem is easily solved by performing a simple search and returning the corresponding index. To satisfy the constraints, if (c S + c R )/c S is greater than deg out (1), then n R = 0. On the other hand, if this ratio is 1, we let n R to be the largest integer for which deg out (n R ) = 2. This is because locating turning ratio sensors in nodes with only one outbound edge will not provide any useful information.

Note that the case where (c S + c R )/c S is an integer, there may be multiple equally optimal solutions to the problem.

Computational complexity

Sensor location

To solve the original problem postulated in (7), it was shown that it could be split into two simpler problems (8) and ( 9), for which the solutions are given using Algorithms 1 and 2 respectively. Therefore, the total computational complexity of the proposed method is the sum of the complexities of these two algorithms.

For Algorithm 1, the only required operation is the sorting of the vector of out-degrees, which is known to have complexity O(n N log n N ). For Algorithm 2, it can be seen that steps 3 and 4 contain the more complex operations, as they require to perform graph traversing and to search for particular structures. It was discussed that step 2 of Algorithm 2 could generate a disconnected graph with q connected components. As each of the subgraphs must contains at least one node with an outgoing edge the previously connected to another subgraph, it must be that q ≤ n R . For each of the subgraphs {N i , E i }, i = 0, . . . , q -1, a Depth First Search is performed (Steps 3 and 4). As each of this searches has complexity

O(|N i | + |E i |), the total complexity is q-1 i=0 O (|N i | + |E i |) = O q-1 i=0 |N i | + q-1 i=0 |E i | = O(n N + n E ).
On the other hand, step 4 requires to find for every subgraph an edge that connects to the main graph. This search operation has an average complexity of O(log n N ) that must be repeated at most n R times.

By taking into account all the operations from both algorithms, we obtain a total complexity of

O(n N log n N + n E ).
This represents a significant improvement when compared to other works in the literature such as [START_REF] Hu | Identification of vehicle sensor locations for link-based network traffic applications[END_REF] and [START_REF] Ng | Synergistic sensor location for link flow inference without path enumeration: A node-based approach[END_REF] that rely on Gaussian elimination, and have computational complexity of O(n N n 2 E ).

Flow reconstruction

To calculate the flow value for all roads in the network, we use the inversion of system (5). It has been shown that the result of Algorithms 1 and 2 generates

ϕ u , such that ϕ = ϕ u ϕ m . Additionally, consider a partition L(R * ) = [L u L m ],
where L u is a square matrix. Because the matrix

L u L m 0 I is full
rank, it is easy to show that L u is invertible. After straightforward calculations, it can be seen that

ϕ u = -L -1 u L m ϕ m . ( 18
)
As the values of ϕ m are known, the whole flow vector can be reconstructed. This calculation has a computational complexity

O(n 3 N + n 3 R -n 3 S )
, which is a reduction with respect to the original matrix inversion.

These results are comparable with other works in the literature, which also involve matrix inversion. However, it should be noted that the algorithm developed by [START_REF] He | A graphical approach to identify sensor locations for link flow inference[END_REF] was able to reconstruct road flows in quasi-linear complexity, albeit only for the case R = ∅. It is unclear if this method can be extended to the general case R ⊆ N in order to reduce complexity. These extensions are to be analyzed in future research.

Study case 1: grid-like network

In this section, we evaluate the performance of the proposed method by using a randomly generated network, which is shown in Figure 5. This network has a Manhattan-like structure with randomly added and deleted edges to better represent a real urban traffic grid. The network contains 24 source/sink nodes, 117 intersections and 254 roads. For evaluation purposes, we consider two different experiments. In the first one, we analyze the trade-off between the two different sensing technologies. In the second, we evaluate the performance of flow reconstruction, even when the underlying assumption of steady-state condition is not satisfied by using a dynamic traffic simulation.

Location of sensors

For a given value of n R we solved problems ( 9) and ( 11). The process was done iteratively by using different values of n R varying from 0 to |N|. In Figure 6 Figure 6: Trade off between turning ratio and flow sensors for the simulated network. The xaxis represents the ratio of monitored intersections n R /n N and the y-axis is the ratio between flow sensors and roads n S /n E .

we show the required number of flow sensors for each value of n R . It can be seen that when n R = 0, it is required to monitor more than half of the roads, result which is coherent with those shown by [START_REF] Ng | Synergistic sensor location for link flow inference without path enumeration: A node-based approach[END_REF] and [START_REF] Viti | Assessing partial observability in network sensor location problems[END_REF], who estimated that for real networks it is required to monitor up to 60% of all roads. By including the information of turning ratios, we can effectively reduce the number of flow sensors. The different slopes of the plot correspond to the distribution of the out degrees of the nodes in the network. Note that when nodes have several outgoing edges, the rate of decrease of sensors is highest. As expected, when intersections have only one outgoing edge, placing turning ratio sensors give no information at all and the number of sensors stays constant.

As an example, Figure 5 shows the sensor configuration obtained by arbitrarily setting n R = 30 and running the algorithms. With this inputs, 75 flow sensors were required. For comparison purposes, we also implemented the Gaussian reduction method used in [START_REF] Hu | Identification of vehicle sensor locations for link-based network traffic applications[END_REF] and [START_REF] Ng | Synergistic sensor location for link flow inference without path enumeration: A node-based approach[END_REF], which yielded the same number of sensors. The running time of both methods was also measured: our graph based approach took 0.24 seconds in average, whereas the algebraic approach took approximately 0.19 seconds. As the network size is small, the measured times are similar.

Dynamic traffic simulation

To evaluate the performance of the flow reconstruction method, we used this network to perform a dynamic simulation of traffic flows. We use the Cell Transmission Model (CTM) which is a discretization of the well known LWR traffic model [START_REF] Daganzo | The cell transmission model, part II: Network traffic[END_REF]]. In the CTM, each road i ∈ E has associated three variables: upstream flow ϕ up i (t), downstream flow ϕ dn i (t), and vehicular

ρ i (t + ∆t) = ρ i (t) + ∆t L i ϕ up i (t) -ϕ dn i (t) , ( 19
)
where ∆t is the discretized time step and L i is the road length. Furthermore, at each iteration the upstream and downstream flows are must be specified. To do this, the CTM uses the triangular fundamental diagram coupled with a junction model,

ϕ dn (t) = argmax ϕ dn (t) n E i=1 ϕ dn i (t) subject to ϕ dn i (t) ≤ min{v 0 ρ i (t), ϕ max } n E i=1 r i,j ϕ dn i (t) ≤ min{ω(ρ max -ρ j (t)), ϕ max } 0 ≤ ϕ dn i (t) ≤ ϕ max ,
where the free flow speed v 0 , the capacity ϕ max , the jam density ρ max , and the congested wave propagation speed ω, are the parameters of the triangular fundamental diagram. The critical density ρ c = ϕ max /v 0 is defined as the density when traffic flow is at its maximum; all roads with density below ρ c are said to be in free flow, whereas roads with density above ρ c are said to be in congestion. For the simulations we used the values shown in Table 2 1 . The turning ratios used in the simulation where chosen to reflect that most of the congestion is only present in a few main roads, whereas most of the secondary roads are lightly used. The values were calculated in the following manner: initially, all of the possible turns were given the same priority by assigning each one a constant weight. Next, for each source/sink node pair the shortest path was identified. The turns that were contained in these shortest paths were given a higher priority by increasing their values with a predefined amount. Finally, the ratios where normalized such that the condition j r i,j = 1 was satisfied. Because of this choice, vehicular flow is highest by following the shortest paths from the entries of the network towards the exits, but a small percentage takes other directions. Thus, the flow and density distribution of the simulation are non-homogeneous among the roads.

Remark: The selection of turning ratios is a simplification of real world scenarios. For a more realistic modeling, dynamic traffic assignment models should be employed, which determine the routing behavior by taking into account the network state. This choice was made to simplify the simulation.

The methodology described in this article for sensor location and flow reconstruction is based on a steady state network. This can be stated in the condition ϕ up (t) = ϕ dn (t) = ϕ for all t, which in turn implies that there is no evolution in time of the density ρ(t + ∆t) = ρ(t). If this condition is not met, then it is expected to obtain errors in the reconstruction of flows. To evaluate the effect of moderate time-varying network conditions, we performed the following experiment:

1. A step input of constant boundary inflows was applied to the network with zero internal flows and zero density as initial conditions. 2. After a period of time, the network reached an equilibrium state. This state was recorded as ϕ ss for flows and ρ ss for the densities. 3. Using the previous steady-state as an initial condition, a second simulation was performed by adding a sine wave to the boundary inflows: ϕ up i (t) = ϕ ss i + A sin(2πt/T ) for i ∈ E in . The period was chosen to be T = 2 hours. 4. At every time instant, flow measurements are obtained ϕ m (t) = C(S * )ϕ dn (t). 5. Flow estimates are calculated using (18). 6. The error is quantified using the Normalized Root Mean Squared Deviation (NRMSD):

N RM SD(t) = 1 n E n E i=1 [ϕ dn i (t) -φi (t)] 2 1 n E n E i=1 ϕ dn i (t)
.

This process was performed for two different cases, one where all of the roads of the network remain in free flow at every time instant, and another where some of the roads are in congestion.

Free flow case

In the first simulation case, the network was initialized using a constant demand flow of 25% of the capacity, i.e. 600 veh/h. Figure 7 shows the network's equilibrium density, which was obtained 5 minutes after the step impulse was applied. Because of the choice of turning ratios, most of the roads present very light traffic conditions, whereas the shortest paths connecting source and sink nodes (blue dots) present higher densities. Nevertheless, all the roads have densities lesser than the critical value, so the network is in free flow. Using this equilibrium state as an initial condition for a subsequent simulation, the inputs were added a sine wave with an amplitude of 60 veh/h and a period of 2 hours during a total time of 4 hours. Figure 8 shows the network's response to the time-varying input. To simplify the display, only the indexed roads 1-6 in Figure 7 are shown.

From Figure 8 it can be seen that the internal states of the network have a sinusoidal behavior. This is due to two reasons: first, the settling time of the system is very small compared to the wave's period, which causes a quick response of the states to follow the inputs. Second, as the traffic network is in free flow, it can be modeled as a linear system, which explains the propagation of the values of the inputs, albeit in a delayed manner.

To test the reconstruction method, sensors where located using the same configuration as Figure 5, using 30 turning ratio and 75 flow sensors. The NRMSD of the flow reconstruction is shown in Figure 9. As the simulation uses an equilibrium sate as an initial condition, the error at time t = 0 is zero. As time progresses, the error shows a time-varying behavior related to the rate of change of the network's state. When the slope of the input signal is zero, ρ(t + 1) ≈ ρ(t) and the steady-state condition is met, and hence the reconstruction has zero error. However, as the time variation of the system increases, the reconstruction error becomes higher. Nevertheless, even when the basis assumption of our method is not satisfied, we were able to obtain errors under 18%.

Congested case

In an analogous manner to the previous case, we initialized the simulation with zero density for all roads in the network. To obtain a congested situation, the boundary input demands were set to 29.8% of the capacity, i.e 715 veh/h. The network's equilibrium state is shown in Figure 10.

From the figure, it is clear that some of the roads have densities higher than ρ c , so their equilibrium state is in congestion. This causes the settling time to be higher compared to the free flow case, to just under 20 minutes. This is because many of the origin-destination paths use the same roads, generating bottlenecks and vehicle accumulation in some roads. For example, road 1 has density close to the critical value, which limits the number of vehicles from road 2 that want to enter. The congestion in road 2 travels upstream towards the source node (road 3). This situation is similar to the bottleneck in road 4 that limits the maximum flow in road 5. During our testing, we found that using higher input demands would cause the system to develop gridlock conditions.

Using the equilibrium state as an initial condition, the inputs demands were added a sine wave with a period of 2 hours and an amplitude of 36 veh/h. The resulting system response is shown in Figure 11, where only the indexed roads 1 to 6 are shown. The non-linearities of the traffic network are evident: some of the roads present saturation, followed by a rapid transition from congestion to free flow when the input demand decreases. This quick transitions cause very high derivatives in the internal states, which drives the system away from the steady-state condition.

The flow reconstruction error is shown in Figure 12. Albeit the non-linearity of the system, the reconstruction error still approaches zero when the time derivative of the system's states is small. Similarly, the error is highest when the rate of change is at its maximum. The rapid increments of the error and the spikes are associated with the quick transitions between congestion and free flow seen in Figure 11.

Study case 2: city of Grenoble

The GTL-Ville is an initiative of the Scale-FreeBack2 project which consists on the analysis of traffic in the city of Grenoble, France. In this context, we are interested in the location of flow and turning ratio sensors which will allow the estimation of the traffic state in the city.

In this paper, we considered a central section of the city spanning an area of approximately 4 km × 4 km. The traffic network is shown in Figure 13. This section was selected because it contains the regularly congested areas of downtown, and some of the principal roads. The nodes that lie outside of the area are considered as source/sink nodes. Additionally, all internal nodes with only outgoing edges or only incoming edges were also labeled in this category, as they do not satisfy the conservation equations. As a result of this preprocessing, the obtained network presents 92 source/sink nodes, 2924 intersections and 5880 roads. It can be seen that the size of the network is considerable, and many of the tools discussed in the literature would fail to solve the sensor location problem in a reasonable amount of time.

To evaluate the algorithms, we proceeded using a similar process as in Section 8: for every value n R = 0, 1, . . . , n N , we found the locations of turning ratio and flow sensors using the algorithms. Figure 14, shows the corresponding number of flow sensors for each n R ∈ [0, n N ]. From Figs. 6 and 14, it can be seen that the knowledge of turning ratios is most useful in the case of complex traffic networks, which can contain intersections with high outdegree, and thus generate regions of very high rate of decrease of the number of sensors. Additionally, for the presented cases, the absolute minimum number of flow sensors that can be obtained (e.g. R = N) is equal to the number of boundary entering flows |E in |. This result is in agreement with the work of [START_REF] Lovisari | Density/Flow reconstruction via heterogeneous sources and Optimal Sensor Placement in road networks[END_REF]. Figure 14 shows the resulting configuration of turning ratio and flow sensors when n R = 1000 (about 34% of the intersections) and n S = 1041 (about 18% of the roads).

To benchmark the computational complexity of the presented method, the running time of the sensor location algorithms was measured for each iteration. The time values ranged between 5.6 and 7.7 seconds, with a mean of 6.4 sec- onds. For comparison purposes, the method presented in Ng (2012) (which is based on Gaussian reduction) was also implemented for one iteration, yielding a processing time of 32 minutes. This shows that the proposed algorithms are suitable for large traffic networks due to low computational complexity. These times were obtained while using an Intel processor i7-4600U running at 3 GHz clock speed with 8 GB of RAM.

Concluding remarks

In this work, we solved the network sensor location problem by using two types of sensing technologies. This allows to reduce the number of flow sensors that are originally required. We solved this problem by finding the solution of two independent problems: optimally locating a given number of turning ratio sensors, and then, using this result as an input, we locate flow sensors. These problems were shown to have computationally efficient solutions, as the first one only requires vector sorting, and the second one can be solved by the construction of spanning trees. The methods were shown to give an optimal solution to the original problem. The complexity of the proposed algorithms was shown to be O(n N log n N +n E ), where n N is the number of intersections and n E is the number of roads, which is much more efficient than previous methods that rely on algebraic computations providing complexities of O(n N n 2 E ). The proposed methods were tested using two simulated networks. In both cases, it was shown that the knowledge of turning ratios of around 30% on the intersections would require to monitor less than 30% of the roads. Nevertheless, some applications might still find these results to yield unfeasible number of sensors. As future work, we will analyze partial observability to further reduce sensing locations. Additionally, we will investigate on extensions to dynamic traffic networks, in order to be able to reconstruct traffic states in the presence of time-varying input demands. total of k∈R * deg out (k) -n N removed edges. As sensors are to be located in edges not belonging to the tree nor the set of removed edges, we end up with n E +n * R -k∈R * deg out (k)-n N locations, which is the same result as Corollary 1.

Thus, In general, for each j ∈ I(k) for some k ∈ R * , the cycles that connect every outgoing edge of k to j must appear together in the elements of ker L(R * ).

A({k})v =
Theorem 3. The rows of C(S) calculated via the described algorithm and the rows of L(R * ) form a linearly independent set. Proof. The algorithm generates a set S of sensor locations such that this edges do not belong to a constructed spanning tree or a set of removed edges. It is well known that adding an edge s ∈ S to the tree generates a single cycle P s . Additionally, if the corresponding path vector to P s is v s , the collection of v s for s ∈ S is a linearly independent set. Consider a partition of S in S U and S R , such that S U consists of the edges that when added to the tree will generate cycles that do not include any node from R * . Consider one element s 0 ∈ S U . From Lemma 5, v s0 ∈ ker L(R * ). As s 0 ∈ P s0 then v s0 (s 0 ) = 0, therefore u T s0 is linearly independent to the rows of L(R * ). Now define L = [L(R * ) T u s0 ] T . Consider another s 1 ∈ S U , s 0 = s 1 . Because s 1 / ∈ P s0 , it is clear that u s0 (s 1 ) = 0, hence v s1 ∈ ker L . Following the previous reasoning we obtain that u T s1 is linearly independent to the rows of L . Repeating this process iteratively, it can be seen that the collection of u T s for all s ∈ S U is linearly independent to the rows of L(R * ). Now consider one element s 0 ∈ S R which forms a cycle P s0 that includes some k ∈ R * when added to the tree. From Lemma 6, there is at least one vector v in the null space of L(R) such that v(s 0 ) = 0, so u T s0 is linearly independent to L(R * ). Consider another s 1 ∈ S R associated with cycle P s1 such that P s1 also includes node k. If there exist i ∈ O(k) ∩ P s0 and j ∈ O(k) ∩ P s1 with i = j, then Lemma 6 implies that the path vectors v s0 , v s1 form part of the same v ∈ ker L(R * ). Therefore, {u T s0 , u T s1 } and the rows of L(R * ) do not form a linearly independent set. Nevertheless, step 2 of the algorithm removes all but one of the outgoing edges for the intersections in R * , implying that it is not possible to form two cycles P s0 , P s1 that include two different outgoing edges from the same k ∈ R * by only adding elements from S to the tree. Thus, all the path vectors v s for all s ∈ S R are related to linearly independent vectors in the null space of L(R * ). Hence, the collection of u T s for all s ∈ S R are linearly independent to the rows of L(R * ).

Furthermore, note that as the cycles generated by the elements of S U do not include any node from R * , Lemma 6 does not apply to them so they are independent to the cycles formed by the elements of S R . Thus, the the rows of C(S) and the rows of L(R * ) form a linearly independent set.

Example 1 .Figure 1 :

 11 Figure 1: Simple traffic network.

  ), so |S | ≤ |S * |. By construction, it must be that rank L(R * ) ≥ rank L(R ), and by Lemma 2, rank L(R * ) ≥ n E -|S |. This implies that |S * | ≤ |S |, and thus, |S * | = |S |, so the pair R * , S * is also an optimal solution to (7).

Algorithm 2 .

 2 Location of flow sensors Inputs: Directed graph {C ∪ N, E} and set R * ⊆ N. Output: Set of measured edges S * .

Figure 2 :

 2 Figure 2: Graph after Step 1.

Figure 3 :

 3 Figure 3: Graph after Step 2.

Figure 4 :

 4 Figure 4: Graph after Step 4.

  a square matrix L(R * ) C(S * ) with complete rank. Without loss of generality, assume an indexing of roads such that C(S * ) = [0 I]. The flow vector ϕ can be split into two components, namely the measured flows ϕ m and the unmeasured flows

Figure 5 :

 5 Figure 5: Simulated network with 24 source/sink nodes, 117 intersections and 254 edges. Optimal locations of turning ratio and flow sensors are shown for the case n R = 30 and n * S = 75.

Figure 7 :

 7 Figure 7: Equilibrium density obtained with a step input of 25% of the maximum flow. Blue points denote source/sink nodes. All roads are in free flow.

Figure 8 :

 8 Figure8: Response of the system to a time varying input. Despite the periods of higher inflows, all the roads remain in free flow. To simplify visualization, only a selection of roads are shown.

Figure 9 :

 9 Figure 9: Reconstruction error for the time-varying input simulation.

Figure 10 :

 10 Figure10: Response of the system to a step input of 29.8% of the maximum flow. The system stabilizes after 30 minutes, with some of the roads in congestion.

Figure 11 :

 11 Figure 11: Response of the system to a time varying input. To simplify visualization, only a selection of roads are shown.

Figure 12 :

 12 Figure 12: Reconstruction error for the time-varying input simulation.

Figure 13 :

 13 Figure 13: Traffic network of the city of Grenoble, for a section of dimension ≈ 4 km × 4 km. The network has 92 source/sink nodes, 2924 intersections and 5880 roads. The location of flow and turning ratio sensor are presented for the case n R = 1000 and n S = 1041.

Figure 14 :

 14 Figure14: Trade off between turning ratio and flow sensors for the simulated network. The xaxis represents the ratio of monitored intersections n R /n N and the y-axis is the ratio between flow sensors and roads n S /n E .

.

  Thus, A(R * )v = 0, which implies that L(R * )v = 0 finalizing the proof.

Table 1 :

 1 Basic notations used in this work

	Notation Description
	I	Identity Matrix
	1	Vector of ones
	0	Vector of zeros
	u i	Standard basis vector with 1 in the i-th coordinate.
	|A| or n A Cardinality of set A.
	A \ B	Relative complement of sets A and B.
	ker A	Null space (or kernel) of matrix A
	e i ∈ A	i-th element of set A
	A i,j

  Ignoring edge direction, perform a DFS over {N ∪ v 0 , E } starting at k. Denote N k and E k the visited nodes and edges, respectively. 4.6 Assign N T

Table 2 :

 2 Parameters for the dynamic traffic simulation

	Parameter	Symbol	Value
	Road length	L	150 m
	Time step	∆t	0.5 s
	Free flow speed	v 0	60 km/h
	Jam density	ρ max	125 veh/km
	Capacity	ϕ max	2400 veh/h
	Critical density	ρ c	40 veh/km
	Congested wave propagation speed	ω	28.2 km/h
	density ρ

i (t). The equation of the CTM is given as

Because of numerical stability, the parameter ∆t must be chosen such that L/∆t > v 0

Scale-Free control for complex physical network systems, http://scale-freeback.eu.

Acknowledgements

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement 694209), http://scale-freeback.eu.

Appendix A. Validity of Algorithm 2

Algorithm 2 presented in Section 5 constructs a basis for the nullspace of L(R * ) and then locates sensors in such a way that the dimension of ker L(R * ) is reduced to 0. Recall that C(S) can be written as the concatenation of rows u T s for s ∈ S. It can be shown that if there exists any v ∈ ker L(R * ) such that v(i) = 0, then u T i is linearly independent to the rows of L(R * ), and thus, this row reduces the dimension of the nullspace.

In the following propositions, we show that the proposed algorithm provides a solution to problem (9). First, we show that the algorithm locates exactly the optimal number of flow sensors n * s . Subsequently, we show that the collection of u T s for s ∈ S is linearly independent to the rows of L(R * ).

Appendix A.1. Number of sensors Proposition 2. Given any feasible network {C ∪ N, E} and any set R * ⊂ N, the graph {N T , E T } generated by Algorithm 2 is a spanning tree of {N ∪ {v 0 }, E}.

Proof. From the original graph, we know that every edge is part of a directed path that begins with an element of E in and ends with an element of E out . Because of this, step 1 of the algorithm generates a strongly connected graph: for any node k ∈ N, there is a directed path from v 0 to k and another from k to v 0 . As step 2 implies the removal of edges, it is possible that the result is a disconnected graph. For now, consider the case when the graph is connected.

Step 3 performs a DFS over a connected graph, so every node is visited, and thus step 4 is not performed. Therefore, {N T , E T } is a spanning tree of {N ∪{v 0 }, E}. Now consider the case when step 2 generates a disconnected graph. Assume that there are q connected components G i = {N i , E i }, i = 0, 1, . . . , q -1, and let G 0 be the subgraph containing node v 0 . The DFS in step 3 will visit only the nodes in G 0 . In step 4, we begin by searching some k ∈ R that belongs to some G i , i = 0, such that originally there is an edge j ∈ O(k) that would connect G i and G 0 . As the original graph is strongly connected, every node is part of a directed path connecting to v 0 ∈ G 0 , so such k and j must always exist. Next, the single remaining outgoing edge of k is also removed. If this causes G i to become disconnected, denote G q as the new connected component, which will be treated in the following iterations. The DFS starting from k will generate a spanning tree of G i . Then, the addition of edge j connects subgraphs G i and G 0 without creating any cycles. This process is carried out iteratively until all nodes haven been visited, creating a spanning tree of {N ∪ {v 0 }, E}.

Corollary 2. For any set of intersections R * , with cardinality |R * | = n R , the described algorithm locates n * s sensors, where n * s follows Corollary 1.

Proof. From step 1, we start with a graph that has n N + 1 nodes and n E edges. At the end of step 4, the algorithm obtains a spanning tree of this graph, which is known to have n N edges. It follows that there are n E -n N edges not contained in the tree. However, step 2 removes deg out (k) -1 edges for each k ∈ R * , for a Appendix A.2. Linearly independence of sensor locations

The algorithm must also find the location of these sensors such that the rows of C(S) and L(R * ) are linearly independent. To do this, we first discuss the relationship of the null space of matrix L(R * ) with the cycles of the graph. Then, we show that by placing sensors in edges that "break" the cycles we obtain a set of linearly independent rows to matrix L(R * ).

Definition 3. Given a path P ⊂ E, P = {e 1 , e 2 , . . . , e l } such that there are no repeated edges, the corresponding path vector is defined as v ∈ {-1, 0, 1} n E ×1 where v(e 1 ) = 1, v(e i ) = 0 if e i / ∈ P, and v(e i ) = v(e i-1 ) if edges e i , e i-1 have the same direction or v(e i ) = -v(e i-1 ) else.

Lemma 5. Let P be a cycle that does not include any node belonging to R * . The corresponding path vector v belongs to the null space of L(R * ).

Proof. If R * = ∅, then L(∅) = B(N) is the incidence matrix of the graph {N ∪ {v 0 }, E} and the proposition has already been proved by [START_REF] Castillo | Nonplanar hole-generated networks and link flow observability based on link counters[END_REF].

For an arbitrary R * , as the nodes comprised by P do not belong to R * , then each one of them is associated to a row of B(U). As this matrix is just a reduced version of B(N), B(U)v = 0 must hold.

We can see that j ∈ P ⇐⇒ j / ∈ k∈R * O(k) and j / ∈ k∈R * I(k). Therefore, A(R * )v = 0. With these two results, L(R * )v = 0. Lemma 6. Let k ∈ R * such that e 0 ∈ I(k) and O(k) = {e 1 , e 2 , . . . , e q }. Let P i = {e i , . . . , e 0 } for i = 1, . . . , q be a feasible path, with associated path vector v i , such that it does not include any node from R * other than k. Then v = i r e0,ei v i belongs to the null space of L(R * ). Proof. Note that each of the paths P i is a cycle: the path ends with e 0 which is connected via k to the starting edge e i . We have B(U)v i = 0. Also, A(R * \ {k})v i = 0, as there are no shared edges between P i and h∈R * ,h =k O(h) or h∈R * ,h =k I(h). It can be seen that

. . .