Since gateways are generally used to integrate the Internet with MANET (Mobile Ad Hoc Networks), gateway discovery is important for MANET mobile nodes to obtain the route to a gateway. The hybrid gateway discovery approach can be configured by adjusting a single parameter, the advertisement TTL. This paper aims to develop an adaptive gateway discovery algorithm to adjust the advertisement TTL by estimating the control overhead. Thus, the control overhead generation can be adjusted in the integrated network. The simulation results indicate that this adaptive gateway discovery algorithm can adjust the appropriate advertisement TTL in different numbers of mobile nodes which desire to access the Internet.