Crowd sourced sensing over smartphones presents a new paradigm for collecting sensing data over a vast area for real-time monitoring applications. A monitoring application may require different types of sensing data, while under a budget constraint. This paper explores the crucial problem of maximizing the aggregate data utility of heterogeneous sensing tasks while maintaining utility-centric fairness across different tasks under a budget constraint. In particular, we take the redundancy of sensing data into account. This problem is highly challenging given its unique characteristics including the intrinsic trade off between aggregate data utility and fairness, and the large number of smartphones. We propose a fairness-aware distributed approach to solving this problem. To overcome the intractability of the problem, we decompose it to two sub problems of recruiting smartphones under a budget constraint and allocating workloads of sensing tasks. For the first sub problem, we propose an efficient greedy algorithm which has a constant approximation ratio of two. For the second problem, we apply dual based decomposition based on which we design a distributed algorithm for determining the workloads of different tasks on each recruited smartphone. We have implemented our distributed algorithm on a windows-based server and Android-based smartphones. With extensive simulations we demonstrate that our approach achieves high aggregate data utility while maintaining good utility-centric fairness across sensing tasks. © 2015 IEEE.