While many standards have been stipulated to control vehicular emissions, current inspection program for examining the engine health of in-use vehicles is practically ineffective and time-consuming. In particular, in-use vehicles are only required for inspection yearly, but huge amount of emissions may have been produced from malfunctioned engines daily. A new wireless inspection and notification system (WINS) is therefore proposed to monitor the vehicle engine health on the street in situ. The principle of WINS is to wirelessly examine some of the engine parameters through radio frequency identification (RFID) and traffic lights. RFID tags are installed on vehicles to collect the engine health information, whereas RFID interrogators are installed on traffic lights for wireless data transmission. Experiments were carried out to evaluate the effectiveness of the proposed WINS, and the results show that the proposed WINS is more convenient and economical than traditional vehicle inspection system. Moreover, as there are more than hundreds of traffic lights in the traffic network of a city, a maximum spanning tree (MAXST) algorithm is proposed to determine the suitable number of RFID devices required in the network so that the implementation cost, system loading and missing rate can be optimized. Different from the typical spanning tree algorithm in operational research, the MAXST algorithm has a domain-specific rule and weight calculation method for this application. To verify the methodology, simulations on the traffic networks of Shenzhen, New York and London were conducted. Results show that only 25–40% of traffic lights of the traffic networks are necessary for installation of RFID interrogators, with a rate of 2–7% that the vehicle owners may be able to escape the location of RFID interrogators.