Digital Twin Placement in Vehicular Networks Using Dynamic Flow Network Evacuation

A digital twin (DT) is a software version of a physical system (PS) that interacts with other objects on its behalf. In order to do so, changes in the PS must be communicated to the DT in a timely fashion, and this updating is referred to as DT synchronization. This paper addresses the Minimum Synchronization Period (MSP) problem in vehicular networks, which seeks to place DTs on execution servers (ESs) so as to minimize the maximum synchronization period for all physical systems and their DTs (PS-DT pairs), while satisfying communication and computation requirements. A novel solution is proposed by modelling the MSP problem as a multi-commodity quickest flow evacuation problem, which treats the synchronization data and processing as flow network inputs to be evacuated in the shortest possible time. Transmission and computation components are represented as network flows with linear edge delays, which enables the use of well-known techniques to find the quickest flow solution. To ensure that each DT is placed at a single execution server, an unsplittable flow rounding procedure is used that assigns DTs to servers without significantly increasing the synchronization objective. Simulation results demonstrate the quality of the MSP solutions produced by our algorithm using the optimal fractional solution as a lower bound for the optimal integral solution.