Digital Twin Placement in Network

Abstract

Digital Twins (DTs) are software representations of physical systems (PSs) that interact with other entities on behalf of their real-world counterparts. To ensure accurate representation and effective interaction, DTs must remain synchronized with their PSs through timely updates—a process known as DT synchronization. This thesis addresses key challenges related to DT synchronization to optimize performance metrics, including the synchronization period and Age of Information (AoI).

In the first part, we address the challenge of optimally placing DTs on execution servers (ESs) to minimize both the data request-response delay experienced by applications and the synchronization period between PSs and their DTs, while satisfying communication and computation constraints. We formulate the DT placement problem in two ways. First, we model it as an integer quadratic program (IQP) aiming to minimize the maximum application response delay subject to maximum data age target constraints at the DTs and the application server. Due to the NP-completeness of the problem, we develop practical polynomial-time approximation algorithms that offer trade-offs between application latency and data age targets. Second, we tackle the Minimum Synchronization Period (MSP) problem by modeling it as a multi-commodity quickest flow evacuation problem, considering synchronization data and processing tasks as network flows with flow dependent edge delays. This innovative approach allows us to use well-established techniques from flow network theory to efficiently find the quickest flow solution. An unsplittable flow rounding procedure ensures that each DT is assigned to a single ES. Simulation results demonstrate the effectiveness of our proposed algorithms in both methods, compared to optimal solutions serving as lower bounds.

In the second part, we address DT migration in vehicular systems, where maintaining acceptable AoI is challenging due to high mobility and frequent handoffs between cellular domains. We formulate the optimal initiation time for migrating a vehicle's DT as a Markov decision process, aiming to minimize the time-averaged AoI at the DT. An online optimal migration initiation algorithm is proposed using dynamic programming and optimal stopping problem. We also develop a more computationally intensive adaptive version of this algorithm, which recalculates the decision policy at each time step for improved performance. Additionally, we introduce a best-in-expectation algorithm that offers a balance between computational efficiency and AoI performance. These algorithms are compared with heuristic approaches, such as immediate migration and migration at handoff, as well as an offline algorithm providing a theoretical lower bound on the average AoI. Performance evaluations show that our proposed algorithms significantly enhance the efficiency of DT migrations while minimizing the time-averaged AoI compared to other methods.