The connection of ad-hoc networks to the Internet is typically established via gateways. To start an Internet connection, in a first step gateways have to be discovered by the mobile nodes within the ad-hoc cluster. Several algorithms to perform the gateway discovery have been studied in the literature up to now. This paper describes an approach for gateway discovery based on HELLO packets of the AODV protocol. The performance of the new algorithm in terms of the discovery time and the handover delay is compared to the well known methods using NS-2 simulations. Conclusions are drawn from the simulations to further improve the performance of common gateway discovery algorithms.