The ability to describe, locate, choose, and interact with services is an integral part of pervasive computing. Compared to previous computing environments, pervasive computing environments are more dynamic and transient while services and clients in these environments are diverse in type and function. In order to effectively facilitate communication and computation in these environments, protocols must be able to these characteristics. This work concentrates on our approach to two of the four components of service discovery, service description and dissemination. We introduce and compare the performance of our schemes to that of existing industrial and research approaches.