Wireless sensor networks (WSNs) are widely used in environmental applications where the aim is to sense physical phenomena, such as temperature and air pollution. A careful deployment of sensors is necessary in order to get a better knowledge of these physical phenomena while ensuring the minimum deployment cost. In this paper, we focus on using WSN for air pollution mapping and tackle the optimization problem of sensor deployment. Unlike most of the existing deployment approaches that are either generic or assume that sensors have a given detection range, we define an appropriate coverage formulation based on an interpolation formula that is adapted to the characteristics of air pollution sensing. We derive, from this formulation, two deployment models for air pollution mapping using the integer linear programming while ensuring the connectivity of the network and taking into account the sensing error of nodes. We analyze the theoretical complexity of our models and propose the heuristic algorithms based on the linear programming relaxation and binary search. We perform extensive simulations on a dataset of the Lyon city, France, in order to assess the computational complexity of our proposal and evaluate the impact of the deployment requirements on the obtained results.