Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems.Environmental monitoring is important, as it allows authorities to understand the impact of potentially harmful environmental phenomena, such as air pollution, noise or temperature, on public health. To achieve this effectively, participatory sensing is a promising paradigm for large-scale data collection. In this approach, ordinary citizens (non-expert contributors) collect environmental data using low-cost mobile devices. However, these participants are generally self-interested agents having their own goals and making local decisions about where and when to take measurements, if any at all. This can lead to a highly inefficient outcome, where observations are either taken redundantly or do not provide sufficient information about key areas of interest. To address these challenges, a coordination system is necessary to guide and to coordinate participants. This paper proposes such a participatory sensing framework and presents a novel algorithm based on entropy and mutual information criteria, called Local Greedy Search (LGS), that takes into consideration knowledge about human mobility patterns and the inconvenience cost that is incurred by taking measurements. In particular, the algorithm uses a local search technique to map participants to measurements that need to be taken. We empirically evaluate our algorithm on real-world human mobility and air quality data and show that our coordination algorithm outperforms the state-of-the-art greedy and myopic algorithms. In particular, LGS gains 33.4% more information than the best benchmark in realistic city-scale scenarios with hundreds of agents.