The Internet of Things (IoT) is connecting people and smart devices on a scale that was once unimaginable. One major challenge for the IoT is to handle vast amount of sensing data generated from the smart devices that are resource-limited and subject to missing data due to link or node failures. By exploring cloud computing with the IoT, we present a cloud-based solution that takes into account the link quality and spatio-temporal correlation of data to minimize energy consumption by selecting sensors for sampling and relaying data. We propose a multiphase adaptive sensing algorithm with belief propagation (BP) protocol (ASBP), which can provide high data quality and reduce energy consumption by turning on only a small number of nodes in the network. We formulate the sensor selection problem and solve it using both constraint programming (CP) and greedy search. We then use our message passing algorithm (BP) for performing inference to reconstruct the missing sensing data. ASBP is evaluated based on the data collected from real sensors. The results show that while maintaining a satisfactory level of data quality and prediction accuracy, ASBP can provide load balancing among sensors successfully and preserves 80% more energy compared with the case where all sensor nodes are actively involved.