This paper presents a new routing strategy for heterogeneous mobile ad hoc networks. We refer to this strategy as on-demand utility-based routing protocol (OUBRP). This protocol introduces a utility-based route discovery strategy, which aims to minimise the number of control packets disseminated into the network during route discovery by efficiently using available resources at each node. Furthermore, we propose a new strategy to eliminate uni-directional links during the route discovery phase. We refer to this strategy as uni-directional link elimination (ULE). We performed a simulation study to compare the performance of OUBRP with a number of different routing protocols proposed for MANETs. Our results show that OUBRP compared to other routing strategies produces significantly fewer control packets and achieves higher levels of successful packet delivery with increasing number of nodes. Furthermore, we propose a number of alternative uni-directional link elimination strategies.