To deploy a protocol in a network, a deep performance study has to be curried. In particular, in the case of ad hoc networks, this performance is principally tied to overhead optimization. In fact, bandwidth limitation and frequent collisions in ad hoc networks represent constraints upon deploying applications which overhead is important. In this paper, we are interested in minimizing overhead due to the deployment of an application we think is relevant to be deployed in ad hoc networks. This application, called service location, aims to make it possible for a mobile user to know about provided services in the network. In this context, we propose an analysis to estimate consumed overhead in different service location approaches. Our analysis is motivated by network and ad hoc application modeling and estimation of overhead due to service covering and request handling.