In this paper, the authors address the problem of optimal sensor placement in road transportation networks. The performance of the sensors is measured in terms of estimation error covariance of the best linear unbiased estimator of cumulative flows in the network over a long period. Sensors are to be placed in such a way that the sum of the error covariance and of a cost penalizing the number of sensors is minimized. The problem, inherently combinatorial, is relaxed using the concept of virtual variance. The resulting problem can be cast as a convex problem, whose computational load is much lower than the original combinatorial problem.