Abstract: Future ad hoc networks are expected to provide mobile hosts with access to a wide range of multimedia services. Mobility, however, poses a challenge towards providing adequate support to Quality of Service (QoS) routing. This paper considers ways of enhancing ad hoc routing by seeking means to quantify, model and exploit knowledge of various user mobility profiles. In this context, we investigate the use of a simple spatial probabilistic model for relatively low speed mobile hosts. Using the model, we examine combinatorial aspects of two basic routing problems: assessing the likelihood that a given end-to-end route exists, and selecting a highly probable route that balances nodal loads among a number of hosts. We devise efficient approximate solutions to both problems, and discuss possible ways of using the solutions in some existing on-demand routing protocols.