Service discovery in Ubiquitous Computing is a task which has to be done frequently due to dynamically changing environments. The limited battery power of mobile devices requires us to optimize frequent and energy costly tasks, especially the ones incurring in communication activities. In this paper we present a novel service discovery algorithm based on node clustering. Nodes within a cluster may sleep to save energy when idle. A clusterhead node is always active and answers discovery requests on behalf of other nodes to achieve low discovery latencies. Simulation experiments show energy savings of up to 66% compared to an approach where all nodes are permanently active while the discovery latencies were not increased.