This paper is motivated by the observation that current research in ad hoc networks mostly assumes a physically flat network architecture with the nodes having homogeneous characteristics, roles, and networking- and processing-capabilities (e.g., network resources, computing power, and transmission power). In real-world ad hoc networks however, node heterogeneity is inherent. New mechanisms at the network layer are required for effective and efficient utilization of such heterogeneous networks. We discuss the issues and challenges for routing protocol design in heterogeneous ad hoc networks, and focus on the problem of quickly detecting and avoiding unidirectional links. We propose a routing framework called Early Unidirectionality Detection and Avoidance (EUDA) that utilizes geographical distance and path loss between the nodes for fast detection of asymmetric and unidirectional routes. We evaluate our scheme through ns-2 simulation and compare it with existing approaches. Our results demonstrate that our techniques work well in these realistic, heterogeneous ad hoc networking environments with unidirectional links.