We propose an energy-efficient service discovery protocol for heterogeneous wireless sensor networks that interact with the users in open and dynamic environments. Our solution exploits a cluster overlay, where the clusterhead nodes form a distributed service registry. A service lookup results in visiting only the clusterhead nodes. We aim for minimising the communication costs during discovery of services and maintenance of a functional distributed service registry. To achieve these objectives we propose a clustering algorithm which makes decisions based on 1-hop neighbourhood information, avoids chain reactions and constructs a set of sparsely distributed clusterheads. We analyse how the properties of the clustering structure influence the performance of the service discovery protocol, by comparing theoretically and through simulations our proposed clustering algorithm with distributed mobility-adaptive clustering (DMAC). To validate our simulations we implement the proposed solution on resource-constraint sensor nodes and we measure the performance of the protocol running on different testbeds.