This paper presents methods for service discovery in multi-hop Bluetooth ad hoc networks, so called scatternets. Two service discovery protocols based on filtering of service requests are proposed. Extensive simulation results are presented showing that the protocols significantly reduce network traffic. Reducing the network traffic is important as many Bluetooth devices have limited power sources and, therefore, benefit from keeping links idle in power saving modes. It is also explained how the proposed protocols can interact with reactive routing protocols and effectively assist route discovery. Finally, an implementation providing functionality for both searching and browsing for services is suggested, effectively extending the Bluetooth SDP to the scatternet.