Article - preprint
In Bianco et al. (2001), the authors present the Sensor Location Problem: that of locating the minimum number of traffic sensors at intersections of a road network such that the traffic ow on the entire network can be determined. They offer a necessary and sufficient condition on the set of monitored nodes in order for the ow everywhere to be determined. In this paper, we present a counterexample that demonstrates that the condition is not actually sufficient (though it is still necessary). We present a stronger necessary condition for ow calculability, and show that it is a sufficient condition in a large class of graphs in which a particular subgraph is a tree. Many typical road networks are included in this category, and we show how our condition can be used to inform traffic sensor placement.
© 2011 Susan Martonosi
David R. Morrison, Susan E. Martonosi: Characteristics of Optimal Solutions to the Sensor Location Problem CoRR abs/1106.0349: (2011). arXiv:1106.0349v1 [math.OC]