We present a fully self-organizing approach for creating and maintaining a reference coordinate system for self-localization in Sensor and Actor Networks (SANETs). GPS technology has become a de facto standard for outdoor localiza- tion, however, self-localization in GPS denied scenarios is still extremely challenging. Typically, anchor nodes or global state information are used to update the nodes’ location information. In contrast, we present a fully self-organizing strategy to generate a distributed reference coordinate system. In particular, we use autonomous robot systems to span and maintain this coordinate system. In particular, we investigated the capabilities of the Mass-Spring-Relaxation (MSR) algorithm, which is frequently used for fault-tolerant and robust localization. Unfortunately, this algorithm needs certain globally valid state information. We extended the MSR algorithm in two ways: First, we made the algorithm independent of a priori global knowledge, and, secondly, we provide extensions that make the algorithm more reliable and robust, and to reduce the number of necessary information exchanges between the nodes. As can be seen from the simulation results, our advanced MSR is very accurate and clearly outperforms the classical MSR for increasing network sizes. We also validated the simulations in an experimental setting. The obtained results confirm the very high localization accuracy.