It is estimated that there are more than 7 billion mobile phone devices active worldwide. This radical growth of mobile technology is starting to be exploited by experts for cheap large-scale data collection. In this work, we are interested in environmental data, such as radiation, noise and air pollution, which is crucial for public health. The traditional approach of collecting environmental data typically requires equipment that is expensive to obtain and maintain, as well as a number of environmental sciences experts to administer them. On the other hand, by exploiting the wide availability of mobile devices, fine grained sensor data can be collected in cities. This data can be used to create detailed maps providing insight to experts about the environmental phenomenon, which in turn will assist the authorities in decision making and urban planning. In more detail, we are interested in the concept of participatory sensing, where people contribute information from the mobile devices they carry with them. However, even though collecting data through people's mobile devices is effective and cheap, people are often self-interested actors that only have local information about the environment and pursue their own agenda. This means measurements may be taken in a suboptimal way. In particular, participants often do duplicate work, i.e., different people take a number of measurements at the same location and time, or they do not explore the whole map of interest, which leads to a partial or false picture of the environment. ii To address these challenges, a coordination system is needed to guide or suggest when, where and who should take measurements. Specifically, the use of intelligent algorithms can solve this problem by coordinating and assisting humans to take more informative measurements as well as ll the gaps for areas that are not covered yet and avoid duplicate work. Moreover, since humans are often predictable in their daily routines the system can exploit this fact in order to make more informative suggestions to people. In particular, a key aim in this work is to ensure that people can get suggestions about taking measurements at times and locations that are least intrusive to their daily life. However, people might not provide the measurements suggested or worse provide false information for their own reasons. Against this background, we provide a complete participatory sensing framework with algorithms for coordinating measurements for environmental monitoring. Our algorithms use local search, heuristics, clustering techniques and stochastic simulations to map participants to observations that need to be taken. In particular, our algorithms intelligently search through the space of possible solutions to find mappings that will maximise the total information learned about the environment in a given time period. The main contributions of this thesis are three algorithms that solve the problem with different requirements. Specifically, the first algorithm, Local Greedy Search, LGS, deals with more deterministic scenarios, in terms of participants' mobility patterns and behaviour. The second algorithm, adaptive Best-Match, aBM, deals with uncertainty in participants' mobility patterns and behaviour, in terms of taking the suggested measurements. Finally, the third algorithm, Trust-based adaptive Best-Match, TaBM, deals with coordinating participants in the presence of malicious users, who attempt to alter the overall picture of the environment by submitting false measurements. We empirically evaluate our algorithms on real-world human mobility and air quality data. Our results show that our algorithms outperform the state of the art in terms of utility gain and accuracy, while being faster at runtime. This indicates that coordinating measurements has a significant benefit in participatory sensing applications in terms of understanding environmental phenomena.