Mobile Ubiquitous Network (MUN) is an integrated network that consists of cellular network, gateways (GWs), as well as local networks. In such heterogeneous environment, GWs deserve much attention since they act as bridges to connect local networks and cellular network to realize global communication. In this paper, we study the issue of GW discovery and especially focus on the scope of GW information advertising. That is, how far for each GW to broadcast its GWINFO to meet the target of good connectivity with low overhead. Generally speaking, cellular link between GW and Base Station (BS), is bottleneck of the whole universal route, and distribution of local nodes decides the total overhead of GW discovery. Therefore, both of them are well studied and considered in the proposed method. Simulation results verified that the method can improve the network performance in terms of data transmission ratio, end-to-end packet delay, average GW discovery time, as well as normalized routing load.