Embedded IoT networks are the backbone of safety-critical systems like smart factories, autonomous vehicles, and airplanes. Therefore, resilience against failures and attacks should be a prior concern already in their design stage. In this study, we introduce a service-based network model as an MILP optimization problem for the efficient deployment of a service overlay to the embedded network by meeting QoS and resilience requirements. We show the complexity and boundaries of the problem and propose several heuristics to relax the service deployment phase and increase the fault-tolerance against node and link failures. Our results indicate that the heuristics achieve results close to the optimum for small sizes of the problem with up to 10^8 time faster solution time. We also show that the heuristics can solve larger problem sizes and can maintain the service availability for 85% of all potential single node failures.