Deriving the Upper Bound of the Number of Sensors Required to Know All Link Flows in a Traffic Network

Abstract

It is demonstrated that the minimum number of sensors required to know all link flows in a traffic network can be determined only if path information is available. However, not all paths need to be enumerated but, at most, a small subset defining the rank <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">rw</i> of the link-path incidence matrix W. If this rank for a reduced subset of paths is already <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</i> - <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> , where <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</i> and <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> are the number of links and noncentroid nodes, respectively, we can conclude that <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</i> - <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> sensors are sufficient. It is also shown that the formulas providing the dependent link flows in terms of the independent link flows can be obtained by the node-based or path-based approaches with the same results only when <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">rw</i> = <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</i> - <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> . Finally, an algorithm to obtain the small subsets of linearly independent path vectors is given. The methods are shown by a parallel network example and the Ciudad Real and Cuenca networks, for which the savings in link counts with respect to the <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</i> - <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> bound are larger than 16%. The corresponding savings in path enumeration are larger than 80%.