A Network Tomography Approach for Traffic Monitoring in Smart Cities

A Network Tomography Approach for Traffic Monitoring in Smart Cities

Various urban planning and managing activities required by a Smart City are feasible because of traffic monitoring. As such, this project proposes a network tomography-based approach that can be applied to road networks to achieve a cost-efficient, flexible, and scalable monitor deployment. Due to the algebraic approach of network tomography, the selection of monitoring intersections can be solved through the use of matrices, with its rows representing paths between two intersections, and its columns representing links in the road network. Because the goal of the algorithm is to provide an inexpensive monitor set, this problem can be translated into a minimization problem over a matroid, which can be solved efficiently by a greedy algorithm. This approach is applied to both real road networks, based on downtown San Francisco, and synthetic, QuadTree-based road networks. The solution retrieved by the proposed approach is compared to the results of Clarkson’s algorithm, a greedy 2-approximation algorithm designed to solve the weighted vertex cover problem.