In this paper we study the problem of basic communication in ad-hoc mobile networks where the deployment area changes in a highly dynamic way and is unknown. We call such networks highly changing ad-hoc mobile networks. For such networks we investigate an efficient communication protocol which extends the idea (introduced in [WAE01,POMC01]) of exploiting the co-ordinated motion of a small part of an ad-hoc mobile network (the ``runners support") to achieve very fast communication between any two mobile users of the network. The basic idea of the new protocol presented here is, instead of using a fixed sized support for the whole duration of the protocol, to employ a support of some initial (small) size which adapts (given some time which can be made fast enough) to the actual levels of traffic and the (unknown and possibly rapidly changing) network area by changing its size in order to converge to an optimal size, thus satisfying certain Quality of Service criteria. We provide here some proofs of correctness and fault tolerance of this adaptive approach and we also provide analytical results using Markov Chains and random walk techniques to show that such an adaptive approach is, for this class of ad-hoc mobile networks, significantly more efficient than a simple non-adaptive implementation of the basic ``runners support" idea.