Skip to Content

Chandler May

Picture of Chandler May.


Verification of Solutions to the Sensor Location Problem

Susan E. Martonosi
Second Reader(s)
Kimberly Kindred


Traffic congestion is a serious problem with large economic and environmental impacts. To reduce congestion (as a city planner) or simply to avoid congested channels (as a road user), one might like to accurately know the flow on roads in the traffic network. This information can be obtained from traffic sensors, devices that can be installed on roads or intersections to measure traffic flow. The sensor location problem is the problem of efficiently locating traffic sensors on intersections such that the flow on the entire network can be extrapolated from the readings of those sensors. I build on current research concerning the sensor location problem to develop conditions on a traffic network and sensor configuration such that the flow can be uniquely extrapolated from the sensors. Specifically, I partition the network by a method described by Morrison and Martonosi (2010) and establish a necessary and sufficient condition for uniquely extrapolatable flow on a part of that network that has certain flow characteristics. I also state a different sufficient but not necessary condition and include a novel proof thereof. Finally, I present several results illustrating the relationship between the inputs to a general network and the flow solution.


The Sensor Location Problem

Additional Materials


Data or Source Code