Service modeling and composition is a fundamental method for offering advanced functionality by combining a set of primitive services provided by the system. Unlike in the case of web services for which there is an abundance of reliable resources, in sensor networks, the resources are constrained and communication among nodes is error-prone and unreliable. Such a dynamic environment requires a continuous adaptation of the composition of services. In this paper, we first propose a graph-based model of sensor services that maps to the operational model of sensor networks and is amenable to analysis. Based on this model, we formulate the process of sensor service composition as a cost-optimization problem, which is NP-complete. We then propose two heuristic methods for its solution, the top-down and the bottom-up, and discuss their centralized and distributed implementations. Using simulations, we evaluate their performance. © 2010 IEEE.