The　recent　advances　of　compressive　sensing　(CS)　have　witnessed　a　great　potential　of　traffic　condition　estimation　in　road　networks.　In　this　paper,　we　propose　a　traffic　estimation　approach　that　applies　compressive　sensing　technique　to　achieve　a　city-scale　traffic　estimation　with　only　a　small　number　of　vehicle　probes.　In　particular,　we　construct　a　new　type　of　random　matrix　for　CS　which　can　significantly　reduce　the　number　of　vehicle　probes　for　traffic　estimation.　Furthermore,　we　also　propose　a　novel　representation　matrix　to　better　exploit　the　correlations　of　road　network　to　improve　the　accuracy　of　traffic　estimation.　We　analyze　the　incoherence　between　random　measurement　matrix　and　sparsity　representation　basis.　Finally,　we　validate　the　effectiveness　of　the　proposed　approach　through　extensive　simulations　by　real-world　dataset.　©　2017　IEEE.