A recent feasibility study suggests that a Service Oriented Architecture (SOA) will be used within the NATO Network Enabled Capabilities information infrastructure. An important element of a SOA is the service discovery process. Traditional registry-based service discovery solutions are a viable option in some, but not all military networks. Therefore we suggest to use a service discovery mechanism built on top of a robust Peer-to-Peer (P2P) network as a complement to the registries. Unfortunately, existing P2P search algorithms necessary to implement the service discovery are not tailored to the specifics of battlefield communication networks. Available search algorithms have high bandwidth requirements which cannot be supported by low-bandwidth links in tactical networks. This paper describes a new search algorithm named Search+ which is designed for tactical networks with limited bandwidth resources. The evaluation of Search+ presented in this paper shows that it outperforms existing search algorithms in terms of bandwidth consumption while achieving comparable search success rates.