Agent-Based Cloud computing is emerging as a paradigm in many domains, including service discovery, service composition and service negotiation, etc. It achieves autonomous resource allocation and resource management by delegating requests to agents. Agents utilized the obsolete acquaintance network and Service Capability Tables (SCTs) to record and schedule agents for service discovery. These approaches are unable to perform global search under the intermittent and volatile cloud computing environment. In this paper, we propose a robust service discovery approach with local and global service discovery capabilities. We validate the proposed approach in different granularity of agent network scale. Experimental results demonstrate that our approach outperforms the SCTs based approaches in the aspect of data availability consistently.