Determining Network-wide Link Flows through Strategic Sensor Deployment without Path Enumeration

摘要

Sensors are becoming increasingly critical elements in contemporary transportation systems, gathering essential(real-time) traffic information for the planning, management and control of these complex systems. In a recentpaper, Hu, Peeta and Chu introduced the interesting problem of determining the smallest subset of links in a trafficnetwork for counting sensor installation, in such a way that it becomes possible to infer the flows on all remaininglinks. The problem is particularly elegant because of its limited number of assumptions. Unfortunately, pathenumeration was required, which – as recognized by the authors – is infeasible for large-scale networks withoutfurther simplifying assumptions (that would destroy the assumption-free nature of the problem). In this paper, wepresent a reformulation of this link observability problem, requiring only node enumeration. Using this node-basedapproach, we prove a conjecture made by Hu, Peeta and Chu by deriving an explicit relationship between thenumber of nodes and links in a transportation network, and the minimum number of sensors to install in order to beable to infer all link flows. In addition, we demonstrate how the proposed method can be employed for roadnetworks that already have sensors installed on them. Numerical examples are presented throughout.