Abstract The search for improvements in the ability to deliver services that meet user requests has led to the develo-pment of numerous projects aimed at service discovery, which is an important stage in the composition process. This discovery has required adaptations aimed at finding suitable devices for accessing services and increasing its capacity. This has led to advances toward the concept of ubiquitous computing. This paper presents a mechanism which uses the concepts of user preferences, device specifications, and delivery context, in order to assist the discovery of services in ubiquitous environments. The proposed discovery mechanism works based on BPEL processes, which represents the services available in the ubiquitous network. They are abstracted to a formal representation of Graphs in order to move the BPEL files matching problem towards Gra-phs matching. This makes it possible to obtain an approximate matching in the absence of a service that totally matches user requirements.