© 2016 IEEE. This paper presents a highly sensitive, energy efficient, and low-cost distributed methane (CH4) sensor system (DMSS) for continuous monitoring, detection, and localization of CH4leaks in natural gas infrastructure, such as transmission and distribution pipelines, wells, and production pads. The CH4sensing element, a key component of the DMSS, consists of a metal-oxide nanocrystal functionalized multi-walled carbon nanotube mesh, which, in comparison with the existing literature, shows stronger relative resistance change while interacting with lower parts per million concentration of CH4. A Gaussian plume triangulation algorithm has been developed for the DMSS. Given a geometric model of the surrounding environment, the algorithm can precisely detect and localize a CH4leak as well as estimate its mass emission rate. A UV-based surface recovery technique making the sensor recover ten times faster than the reported ones is presented for the DMSS. A control algorithm based on the UV-accelerated recovery is developed, which facilitates faster leak detection.