With the vigorous construction of the digital new power system, the traditional power communication network is gradually transforming into a more robust, resilient, and multi-service-bearing all-time and all-domain communication network. To address the issue of difficult-to-guarantee deterministic latency for time-sensitive services due to the simultaneous access of multiple types of terminal services and massive data transmission in the all-time and all-domain communication network, a deterministic latency guarantee technology is proposed for all-time and all-domain communication networks based on Time-Sensitive Networking(TSN). Firstly, based on the analysis of the characteristics, importance, periodicity, and latency requirements of various types of services in the all-time and all-domain power communication network, the corresponding service models are established and prioritized. Then, a traffic scheduling mechanism based on TSN perception and shaping is proposed to ensure that the calculation of the gate control schedule meets the deterministic low-latency transmission of time-sensitive flows within the transmission cycle. To achieve the goal of minimizing end-to-end latency, a combined algorithm based on genetic algorithm and tabu search algorithm is employed to calculate the gate control list of time-sensitive flows. The average end-to-end latency is reduced by 15% compared with single optimization algorithm, and the latency jitter of time-sensitive flows is controlled at about 2 μs. This improves the scheduling performance and provides strong support for the stable and safe operation of the all-time and all-domain power communication network.