Dramatic and rapid advances in mobile communication and networking technologies have presented challenges and opportunities not previously thinkable. One such development is the emergence of small-scale mobile networks that require support for "whole-network" mobility. This paper describes a first service discovery protocol and framework specifically designed to address the new requirement. After exploring alternative approaches to learn underlying mobile network structures, we introduce the concept of virtual service registries as a method to exploit the whole-network mobility for enhanced service discovery and interactions. The feasibility and effectiveness of our approach are validated through a prototype implementation and performance study. © 2012 International Information Institute.