Service-Oriented Architectures (SOAs) are increasingly being used for designing and building large-scale networked and distributed systems. Catering to the complex and dynamically varying needs of business applications/clients, these systems must usually be realized by dynamically composing a variety of network-available services. Evaluation of large-scale SOAs, particularly on dynamic network platforms, such as Mobile Ad-hoc Networks (MANETs), is a non-trivial problem that requires not only a correct modeling of SOAs and the network platform, but also their relationships.