The performance of autonomous vehicles could be drastically improved if ad-hoc networking and suitable real-time coordination is employed to optimize and improve the joint behavior of multiple autonomous units. However, due to ad-hoc connections and the real-time interaction the correctness and safety of such coordinated autonomous units is very hard to ensure. In this paper we present how service-oriented real-time coordination can be employed to achieve this goal. Based on the proper real-time coordination between two or more vehicles captured by a service contract, we focus on structural changes and the instantiation and termination of service contracts which is a crucial prerequisite for a safe system operation. We present how the structural changes and the service contract creation/deletion can be modeled by a well-defined UML subset consisting of class and object diagrams with collaborations as well as well-defined behavioral rules can be verified taking the dynamic structural changes due to the ad-hoc networking as well as the real-time coordination into account. The new verification technique is outlined and the application of the technique for an application example is presented.