Optimal Network Partition and Edge Server Placement for Distributed State Estimation

Lyuzerui Yuan; Jie Gu; Jinghuan Ma; Honglin Wen; Zhijian Jin

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

Optimal Network Partition and Edge Server Placement for Distributed State Estimation PDF

- ORCID：
Lyuzerui Yuan
✉
- ORCID：
Jie Gu
✉
- ORCID：
Jinghuan Ma
✉
- ORCID：
Honglin Wen
✉
- ORCID：
Zhijian Jin
✉

the School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Updated：2022-11-20

DOI：10.35833/MPCE.2021.000512

Abstract

This paper investigates network partition and edge server placement problem to exploit the benefit of edge computing for distributed state estimation. A constrained many-objective optimization problem is formulated to minimize the cost of edge server deployment, operation, and maintenance, avoid the difference in the partition sizes, reduce the level of coupling between connected partitions, and maximize the inner cohesion of each partition. Capacities of edge server are constrained against underload and overload. To efficiently solve the problem, an improved non-dominated sorting genetic algorithm III (NSGA-III) is developed, with a specifically designed directed mutation operator based on topological characteristics of the partitions to accelerate convergence. Case study validates that the proposed formulations effectively characterize the practical concerns and reveal their trade-offs, and the improved algorithm outperforms existing representative ones for large-scale networks in converging to a near-optimal solution. The optimized result contributes significantly to real-time distributed state estimation.

Keywords

Network partition; edge server placement; distributed state estimation; edge computing; non-dominated sorting genetic algorithm (NSGA).

I. Introduction

AS an essential task for monitoring and controlling power systems, state estimation should provide a real-time estimate of system states, where real-time means that the response time of estimation operation is within two seconds [

1]. This requirement, however, is hardly satisfied in a large-scale network, as its control center spends considerable computational time on dealing with high-dimensional state variables. To address the issue, a mainstream countermeasure is distributed state estimation (DSE), which divides the overall estimation problem into many low-dimensional subproblems and then solves them in parallel [2]-[8]. Although the control center is capable of parallel computing, it still suffers from great communication burdens caused by the massive measurements transmitted from remote data sources. This will result in long delays to increase the response time of DSE [9].

Fortunately, the emerging edge computing can provide strong technical support for the real-time DSE [

10]. It moves the estimation subproblems from the control center into multiple edge servers (ESs) that are distributed near data sources, to deliver low communication delays and timely data processing [11]. Based on this, we should decompose a large-scale network into several subareas, where an ES is placed in each subarea as the local controller to acquire information and perform DSE [12]. In this scenario, the network partition and the ES placement are two critical factors to facilitate the real-time performance of DSE, as the network partition can balance the sizes of subareas to shorten the runtime of DSE [13], and the ES placement aims to shorten the average distance between ES and data sources to reduce communication delays [11].

Existing works have studied the network partition with fixed network size [

13]-[15] or the ES placement based on potential locations [16]-[18], while coupling of the two factors, as a non-negligible impact on the performance of DSE, has not be fully addressed. Specifically, a partition scheme that ignores ES placement is unfavorable for reducing delays of servers, since the potential ES locations in subareas could be remote from some data sources. In contrast, without considering network partition, the determined ES locations may be unevenly distributed to result in unbalanced partition sizes. Hence, their coupling should be considered to enhance real-time DSE operation.

In this paper, we propose to combine the two factors to form an integrated optimization problem of network partition and edge server placement (NPESP). Concerns on network partition are characterized by the coupling of subareas and the state variable balance. The coupling of subareas indicates the extent of connections between subareas, which is minimized to reduce exchanged information and communication burden [

15]. We also minimize the state variable balance that refers to the difference in sizes of subareas, to lead to shorter runtime of DSE [13]. Next, a metric named cohesion of served nodes, i.e., the ratio of subarea density and the average distance between ESs and data sources, is used to represent the timeliness of communication in a subarea. It is maximized to reduce delays of ESs. Economic concern, which refers to the costs of purchasing, operating and maintaining ESs, is also characterized by a metric of cost. The metric is minimized for obtaining economical ES placement scheme. In addition, we constrain capacities of ES within a range to prevent underload and overload. Hence, coupling of the two factors, i.e., trade-off between the network partition and the ES placement, can be indicated by a negative correlation between the number of subareas and the cost of ES related issues, the impact of partitions on the determination of ES locations, and the restriction on the size of subareas posed by capacities of ES.

Based on the above-mentioned four criteria, we formulate a many-objective optimization problem (MaOP), which refers to the optimization problem with more than three objectives [

19], constrained by the maximum and minimum capacities of ES, of which the objectives are to minimize the cost, the coupling of subareas, and the state variable balance, while maximizing the cohesion of served nodes. The proposed MaOP is a non-convex mixed-integer nonlinear program that is not tractable by continuous relaxation [19]. Thus, we choose the non-dominated sorting genetic algorithm III (NSGA-III), which has competitive convergence and diversity for MaOPs, as a basic solution algorithm [20], [21]. To enhance the efficiency of NSGA-III in dealing with large-scale MaOPs, we modify the basic NSGA-III to an improved one. Specifically, the real-number encoding is applied to map the decision variable matrix for saving computational resources. Conforming to topological characteristics of partitions, we design a directed mutation operator for accelerating convergence. Besides, a gene restriction is established to readily guarantee the feasiblility of offspring solutions.

Experiments are implemented on the IEEE 118-bus system [

22] and the Polish 2383-bus system [23]. The results illustrate that there are trade-offs among the four objectives, whereas the proposed MaOP can provide various sub-optimal NPESP schemes to achieve a compromise between objectives without degrading any of them. Under NPESP schemes, the runtimes of distributed weighted least squares (DWLS) [7], distributed unscented Kalman filter (DUKF) [3], [4], and distributed particle filter (DPF) [6] are shortened. Moreover, the exceptional convergence, diversity, and evenness of the improved NSGA-III for large-scale networks are testified by two popular metrics, i.e., inverse generational distance (IGD) and spacing [21].

The main contributions of this study are summarized as follows. ① We present an integrated NPESP problem in the scenario where DSE is supported by edge computing. ② We formulate the NPESP problem as a constrained MaOP, in which the coupling between network partition and ES placement is considered. ③ We design an improved NSGA-III with rapid convergence for the proposed MaOP in large-scale networks. ④ The trade-offs between objectives are demonstrated, i.e., the four criteria are indispensable for NPESP to acquire a compromise scheme without sacrificing any one of the real-time DSE, the economy of ESs, or the strength of partition.

This paper is organized as follows. Section II reviews the related work. Section III introduces the DSE model based on edge computing framework. A constrained NPESP MaOP is proposed in Section IV. Section V presents the solution algorithm. Section VI uses case study to evaluate the proposed MaOP and show the performance of the improved NSGA-III. Conclusion is drawn in Section VII.

II. Related Work

Network partition is a basic problem in multiple distributed scenarios such as distributed optimal power flow [

24], [25], distributed energy resource aggregation [26], DSE, etc. Since real time is a main concern on state estimation, researchers mostly focus on state variable balance. Reference [14] adopts the branch-line layer method and postorder-traversal algorithm to develop a graph-based partition approach that can ensure balance of subarea sizes. Reference [15] proposes a single-objective optimization problem solved by genetic algorithm (GA) to obtain size-balanced subareas. In addition, the effect of coupling between subareas on communication time of DSE is mentioned in [27]. To balance subarea sizes and reduce coupling level, the studies in [13] and [28] use K-means and spectral clustering to cluster nodes into several subareas, respectively. Nevertheless, the interaction between coupling and the number of subareas is ignored due to the predetermined number of clusters. For observable networks, [29] develops a heuristic method which combines the integer-linear-programming eigenvector based approach and interchange method to obtain several observable subareas. In [30], a network is transformed into a spanning tree that is traversed and partitioned based on Markov chains to guarantee the observability of subareas. However, the partition strategies are invalid in case of unobservable networks.

The ES placement has been investigated in communication field recently. The concerns mainly include cost of service, delay, and communication network robustness. In [

16], the service cost is represented by the sum of resource usage cost and one-time deployment cost. Then a constrained single-objective optimization problem is formulated to address the trade-off between cost and user coverage. Reference [17] proposes a prediction-mapping optimization heuristic algorithm to minimize the user cost that consists of calculation cost and migration cost. For delay reduction, [18] aims to minimize the response time and maximize the response time fairness of base stations through a game-theory-based method, where the response time is calculated as the sum of communication delays and task execution delays. Reference [31] formulates a multi-objective constraint optimization problem to minimize communication delays and to balance the workload difference between ESs, which is solved by GA and local search algorithm. Communication network robustness is proposed in [32], which is assessed by a metric that refers to the number of mobile users co-covered by two ESs, and a compromise programming is formulated to trade off communication network robustness and user coverage. In these studies, some concerns (e.g., user coverage [16], [32], response time fairness [18], and migration cost [17]) on the basis of mobile edge computing, are non-essential in the scenario presented in this paper, since power system has high-speed fiber-optic private network and fixed workload [33].

Furthermore, the coupling between network partition and ES placement is disregarded in aforementioned studies. This paper will take it into consideration to formulate a constrained NPESP MaOP. However, the above-mentioned solution methods such as GA and K-means are not adept in dealing with MaOPs. The reason is that more than one objective have to be changed into a single objective by weighted summation, which may result in non-equivalence between the original MaOP and weighted single-objective problem [

34]. Hence, an efficient solution method for the proposed MaOP needs to be developed.

III. DSE Model Baesd on Edge Computing Framework

In this section, we integrate DSE into a general three-level framework of edge computing in [

11]. As shown in the left side of Fig. 1, the left part of the three-level framework is the perceptual layer, where abundant edge devices, e.g., phasor measurement unit (PMU) and feeder terminal unit (FTU), are deployed on nodes to collect measurements for DSE. The middle is the edge layer with several ESs distributed near edge devices. An ES can receive measurements from its associated edge devices, communicate with other ESs, execute DSE algorithms, etc. There is a significant reduction of communication delays because of the ES close to data sources. In addition, some sensitive information such as residential electricity consumption can be processed by ESs rather than being sent to the remote data center, which means better data security and privacy. The right part is the cloud layer with a large data center to perform global applications, e.g., power system security analysis, based on all DSE results. Since global applications in the cloud layer are not the focus of this paper, they are not mentioned below.

Fig. 1 A three-level edge computing framework for DSE and IEEE 118-bus network with three partitions.

As shown in the right side of Fig. 1, a tripartite IEEE 118-bus test system [

22] is considered as the intended scenario. Three ESs, denoted as ES

i

(

i = 1,2, 3

), are located at node

17

49

, and

100

as local controllers of subareas

1

2

, and

3

, respectively. In terms of DSE approaches [2]-[8], ES

i

should receive local measurements

z_{i}

in subarea

i

and shareable measurements

z_{c j} (j \neq i)

from ES

j

. Then, it calculates the optimal estimation

{\hat{x}}_{i}

of state variable vector

x_{i}

in two steps. Firstly, the local estimation

{\hat{x}}_{i}^{l}

is acquired by minimizing the error between measurement functions

h_{i} (x_{i})

(i.e., power flow equations [7]) and local measurements

z_{i}

, i.e.,

{\hat{x}}_{i}^{l} = \underset{x_{i}}{a r g m i n} r_{i} (x_{i})

(1)

r_{i} (x_{i}) = z_{i} - h_{i} (x_{i})

(2)

Secondly, ${\hat{x}}_{i}^{l}$ is corrected into the optimal estimation ${\hat{x}}_{i}$ , i.e.,

{\hat{x}}_{i} = {\hat{x}}_{i}^{l} + Δ x_{i}

(3)

Δ x_{i} = g_{i} (χ_{i}) χ_{i} \in {z_{c j}, {\hat{x}}_{j}^{l}, Θ, j = 1,2, 3}

(4)

where $Θ$ is the other shareable information except measurements; and $g_{i} (\cdot)$ is the function mapping $χ_{i}$ to $Δ x_{i}$ . The dimension of ${\hat{x}}_{i}$ , which has a significant impact on DSE runtime, is determined by network partition. The ES placement influences communication delays of ESs receiving or delivering $z_{i}$ and $χ_{i}$ . To realize real-time DSE under edge computing, NPESP problem should be paid attention to.

Before formulating the problem, we present some basic notations. An undirected graph $G = {V, E}$ is applied to describe the topology of a network. $V = {v_{i} | i = 1,2, \dots, n}$ is the set of nodes, where $v_{i}$ represents node $i$ and $n$ is the total number of nodes. $Y = (y_{i j})_{n \times n}$ is the adjacency matrix of $G$ . We denote the distance matrix of $G$ as $D = (d_{i j})_{n \times n}$ , where $d_{i j}$ calculated by Dijkstra’s algorithm is the minimum number of edges between $v_{i}$ and $v_{j}$ . In addition, the workload vector of the network is represented as $W = [w_{1}, w_{2}, \dots, w_{n}]^{T}$ , where $w_{i}$ ( $i = 1,2, \dots, n$ ) is the amount of measurements in $v_{i}$ at a timestamp. To indicate partitions and ES locations, a binary matrix $A = (a_{i j})_{n \times n}$ named NPESP matrix is defined, i.e.,

a_{i j} = \{\begin{array}{l} 1 & v_{i} i s s e r v e d b y t h e E S a t v_{j} \\ 0 & v_{i} i s n o t s e r v e d b y t h e E S a t v_{j} \end{array}

(5)

When $i = j$ , $a_{i i} = 1$ means that $v_{i}$ has an ES. Thus, the number of ESs is represented by the trace of $A$ , i.e., $t r a c e (A) = \sum_{i = 1}^{n} a_{i i}$ .

IV. Constrained NPESP MaOP

In this section, a constrained NPESP MaOP is proposed, in which the objectives and constraints characterize essential practical concerns on NPESP. To simply deliver the basic idea, we make three assumptions: ① the partition is non-overlapping and each subarea has one ES; ② referring to [

31], [32], the price, capacity, and hardware performance of ESs are supposed to be the same, as they have little influence on problem formulation; ③ since measurement devices are usually inadequate for DSE in large-scale power systems, both actual and pseudo measurements are considered as the workload to meet the observability of network.

A. Cost Minimization

Economic concerns on purchasing, operating, and maintaining ESs can be represented by a cost minimization. The purchasing cost contains the prices of an ES and related hardware accessories and application softwares. The operating cost and maintaining cost refer to the discounted values of daily operation expenses and estimated breakdown maintenance costs within service life of an ES, respectively. We denote the sum of three costs of an ES as $P_{c o s t}$ . The cost minimization function is expressed as:

m i n F_{1} = \sum_{i = 1}^{n} P_{c o s t, i} a_{i i} = P_{c o s t} \cdot t r a c e (A)

(6)

where $P_{c o s t, i}$ is the sum of the purchasing, operating, and maintaining costs of the i^th ES.

B. High Cohesion

The topology of each subarea is required to be connected and preferably densely connected [

14]. In addition, we should shorten the average distance between an ES and the served nodes [11]. A metric named cohesion of served nodes (called cohesion hereafter) is designed to judge both the density of topology and the average distance. Inspired by the intra-cluster density [34], the density of subarea topology is defined as:

ρ_{i} = \{\begin{array}{l} \frac{\frac{1}{2} \sum_{j = 1}^{n} (\sum_{k = 1}^{n} a_{k i} y_{k j}) a_{j i}}{\sum_{k = 1}^{n} a_{k i}} a_{i i} = 1 \\ 0 a_{i i} = 0 \end{array}

(7)

Nodes in the subarea with larger $ρ_{i}$ are denser. The average distance between an ES and its served nodes is calculated as:

γ_{i} = \{\begin{array}{l} \frac{\sum_{k = 1}^{n} a_{k i} d_{k i}}{\sum_{k = 1}^{n} a_{k i}} a_{i i} = 1 \\ \infty a_{i i} = 0 \end{array}

(8)

A smaller $γ_{i}$ represents that the ES at $v_{i}$ is closer to its data sources. Consequently, the cohesion can be defined as:

δ_{i} = \{\begin{array}{l} \frac{ρ_{i}}{γ_{i}} a_{i i} = 1 \\ 0 a_{i i} = 0 \end{array}

(9)

To make subareas cohesive and reduce communication delays, we minimize the reciprocal of the average cohesion, i.e.,

m i n F_{2} = \frac{t r a c e (A)}{\sum_{i = 1}^{n} δ_{i}}

(10)

C. Low Coupling

The coupling of subareas (called coupling hereafter), which is a criterion for network partition, estimates the extent to which the subareas are connected. Based on inter-cluster density [

34], the coupling is measured by the number of tie lines that equals the total number of lines in the network minus the number of internal lines. Since the low level of coupling indicates less exchanged information and communication resource consumption [27], the third objective is to minimize the coupling, i.e.,

\begin{array}{l} m i n F_{3} = \frac{1}{2} \sum_{i = 1}^{n} \sum_{j = 1}^{n} y_{i j} - \frac{1}{2} \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k = 1}^{n} a_{k i} y_{k j} a_{j i} = \\ \frac{1}{2} t r a c e (Y^{T} Y) - \frac{1}{2} t r a c e (A^{T} Y A) \end{array}

(11)

D. State Variable Balance

State variables refer to voltage magnitudes and phase angles estimated in the DSE. Thus, the number of state variables are twice that of nodes. For improving the real-time performance of DSE, a network should be partitioned into several similarly-sized subareas to balance the computational burden of subareas. We use a metric named state variable balance, i.e., the largest difference between subarea sizes, to evaluate the impact of network partition on the runtime of DSE. Thus, the last objective is to minimize state variable balance, i.e.,

m i n F_{4} = \underset{j \in Ψ}{m a x} (\sum_{i = 1}^{n} a_{i j}) - \underset{j \in Ψ}{m i n} (\sum_{i = 1}^{n} a_{i j})

(12)

where $Ψ = {j | a_{j j} = 1, j = 1,2, \dots, n}$ is the set of node numbers for ES locations.

E. Constraints

1)　Partition Constraints

Considering non-overlapping subareas, each row of the NPESP matrix has one and only one element equal to $1$ , i.e.,

\{\begin{array}{l} \sum_{j = 1}^{n} a_{i j} = 1 \\ a_{i j} \in {0,1} i, j = 1,2, \dots, n \end{array}

(13)

In each column, we need to ensure $a_{i j} = 0 (\forall v_{i} \in V)$ when no ES is deployed at $v_{j}$ and $a_{j j} = 1$ when the measurements of $v_{i}$ are allocated to the ES at $v_{j}$ . The other partition constraint can be expressed as:

a_{j j} - a_{i j} \geq 0 i, j = 1,2, \dots, n

(14)

2)　Capacity Constraints

Due to finite measurements received by an ES in a timestamp, the maximum workload capacity $C_{m a x}$ and the minimum workload capacity $C_{m i n}$ are set to prevent overload and underload of ES, respectively, i.e.,

a_{j j} \sum_{i = 1}^{n} w_{i} a_{i j} \leq α C_{m a x} j = 1,2, \dots, n

(15)

a_{j j} \sum_{i = 1}^{n} w_{i} a_{i j} \geq (β C_{m i n} {+ 1)}^{a_{j j}} - 1 j = 1,2, \dots, n

(16)

where $α$ ( $0 < α < 1$ ) and $β$ ( $β > 0$ ) are the maximum and minimum capacity margins, respectively.

V. Solution Algorithm

This section presents an improved NSGA-III with a designed directed mutation for the proposed MaOP.

A. Basic NSGA-III

NSGA-III, as a variant of GA, is one of the best heuristic algorithms for MaOPs [

20], [21]. It has the same procedures as GA, i.e., encoding, crossover, mutation, and selection, in which the selection operator is quite different from GA. Thus, its selection operator is introduced briefly. We denote an MaOP as

F = {m i n f_{i} (x), i = 1,2, \dots, k, k > 3}

, where

f_{i} (x)

is the i^th objective function. The three basic definitions about the MaOP are given below.

1) Definition 1: Pareto domination. Supposing there are two different feasible solutions ( $π_{a}$ , $π_{b}$ ) for $F$ , we deem that $π_{a}$ dominates $π_{b}$ if $π_{a}$ and $π_{b}$ satisfy the following conditions:

\{\begin{array}{l} f_{i} (π_{a}) \leq f_{i} (π_{b}) \forall f_{i} \in F \\ f_{j} (π_{a}) < f_{j} (π_{b}) \exists f_{j} \in F \end{array}

(17)

2) Definition 2: non-dominated solutions. Let $Π$ denote the feasible solution set of $F$ . We deem that $π^{*}$ is a non-dominated solution, i.e., Pareto solution, of $F$ when $π^{*}$ dominates $π$ , given the condition of $\forall π \in Π$ and $π \neq π^{*}$ .

3) Definition 3: non-dominated level. Based on $k$ objectives, the members, each of which represents a solution of $F$ , are sorted in accordance with Pareto domination. The final non-dominated solutions are recorded as a non-dominated level.

The selection operator of NSGA-III classifies members of the population into different non-dominated levels by reference-point-based non-dominated sorting and then selects elite members. Specifically, the parent population with $z$ members in the $t$ ^th generation is denoted as $P^{t} = {p_{i}^{t}, i = 1,2, \dots, z}$ , and the offspring population $O^{t}$ with $z$ members is created from $P^{t}$ by crossover and mutation operators. To generate the next generation $P^{t + 1}$ , we should select $z$ elite members from the combined parent and offspring population $R^{t} = P^{t} ⋃ O^{t}$ (with size of 2 $z$ ). First, we sort $R^{t}$ into different non-dominated levels $R_{1}^{t}, R_{2}^{t}, \dots, R_{r}^{t}$ , where the members of $R_{i}^{t}$ dominate anyone of $R_{i + 1}^{t}$ . Next, superior members are selected into $P^{t + 1}$ starting from $R_{1}^{t}$ , until the size of $P^{t + 1}$ equals $z$ . There is no extra work when the size of $R_{S}^{t} = R_{1}^{t} ⋃ R_{2}^{t} ⋃ \dots ⋃ R_{s}^{t}$ $(s < r)$ is equal to $z$ . In most situations, however, the size of $R_{S - 1}^{t}$ denoted as $u$ is smaller than $z$ , while the size of $R_{S}^{t}$ is larger than $z$ . Therefore, $z - u$ members have to be chosen from the last accepted level $R_{s}^{t}$ . To maximize diversity of members in the $s$ ^th level, the elitist selection strategy based on the reference point is proposed. For further details, please refer to [

35].

B. Improved NSGA-III

The basic NSGA-III converges slowly when solving MaOPs with high-dimensional decision variables. Hence, an improved NSGA-III is presented. We use real-number encoding to compress the sparse NPESP matrix. The capacity and partition constraints are easily calculated by penalty function and gene restriction, respectively. To accelerate convergence, a directed mutation operator is designed with regard to topological characteristic of partitions.

1)　Real-number Encoding

Since the NPESP matrix $A$ has numerous zero elements to occupy storage and computing resources, we adopt real-number encoding to compress it into one-dimensional sequence with $n$ real numbers. The chromosome of a member in $P^{t}$ , i.e., a real-coded form of $A$ , is represented as:

p_{i}^{t} = (p_{i j}^{t})_{1 \times n} p_{i j}^{t} \in Ω, i = 1,2, \dots, z, j = 1,2, \dots, n

(18)

where $p_{i j}^{t} = l$ means that $v_{j}$ is served by the ES at $v_{l}$ ; and $Ω$ is the set of potential ES locations. In this paper, we set the nodes with more than three degrees as the potential ES locations.

2)　Penalty Function

The capacity constraints in (15) and (16) are represented by the penalty function, i.e.,

P F = \{\begin{array}{l} 0 \forall a_{j j}, (β C_{m i n} {+ 1)}^{a_{j j}} - 1 \leq a_{j j} \sum_{i = 1}^{n} w_{i} a_{i j} \leq α C_{m a x} \\ \infty \exists a_{j j}, a_{j j} \sum_{i = 1}^{n} w_{i} a_{i j} < (β C_{m i n} {+ 1)}^{a_{j j}} - 1 o r a_{j j} \sum_{i = 1}^{n} w_{i} a_{i j} > α C_{m a x} \end{array}

(19)

As a result, the final objectives of the proposed MaOP are to minimize $F_{1}, F_{2}, F_{3}, F_{4}$ , and $P F$ .

3)　Gene Restriction

The gene restriction is used to simplify the partition constraints, which makes $p_{i j}^{t}$ equal to $j$ on condition of $p_{i l}^{t} = j (v_{l} \in V)$ . It only corresponds to the constraint in (14), as the constraint in (13) is naturally satisfied by the real-number encoding. We perform the gene restriction after each mutation operator.

4)　Directed Mutation

There are multiple mutation operators, e.g., uniform mutation and inversion mutation, which randomly mutate members to lead to slow evolution. Therefore, we design a new mutation operator named directed mutation based on the topological characteristic of partitions. For the directed mutation of a chromosome, we randomly select an initial mutation node $v_{i}$ and sort its distance sequence ${d_{i j}, j = 1,2, \dots, n}$ in ascending order to get the corresponding node number sequence $N_{a} (v_{i})$ . Next, the potential ES location $v_{n_{f}}$ closest to $v_{i}$ is found according to $N_{a} (v_{i})$ and $Ω$ . Finally, the genes corresponding to the first $η$ nodes in $N_{a} (v_{i})$ are changed into $n_{f}$ , where the mutation scale $η$ determines the number of mutated genes. This step ensures that the $η$ nodes closest to $v_{i}$ are assigned to the same subarea. Through directed mutation operator, partial genes of the chromosome are mutated purposely, accelerating the evolution of population towards the targets. Algorithm 1 conducts the procedure of the directed mutation for the t^th generation. The flowchart of the improved NSGA-III is shown in Fig. 2. Furthermore, we present an analysis of the computational complexity of the algorithm in Appendix A.

Fig. 2 Flowchart of impoved NSGA-III.

Algorithm 1 : directed mutation for the $t$ ^th generation
Input: parent population $P^{t} = {p_{i}^{t}, i = 1,2, \dots, z}$ ; mutation rate $ζ \in (0,1)$ ; mutation scale $η \in {1,2, \dots, n}$ ; set of potential ES locations $Ω$ ; distance matrix $D$
Output: filial population $P^{t + 1}$
1: $k = 0$
2: repeat
3: $k = k + 1$
4: generate a random integer $ω$ from $[0,1]$
5: if $ω > ζ$ then
6: $p_{k}^{t + 1} = p_{k}^{t}$
7: else
8: generate a random number $i$ from $[1, n]$ as the initial mutation node number
9: find the potential ES location closest to $v_{i}$ and record its number as $n_{f}$
10: sort ${d_{i j}, j = 1,2, \dots, n}$ in ascending order to get the corresponding sequence of node numbers $N_{a} (v_{i})$
11: $j = 0$
12: repeat
13: $j = j + 1$ , $l = N_{a} (v_{i}) [j]$ , $p_{k l}^{t + 1} = n_{f}$ , where $N_{a} (v_{i}) [j]$ is the j^th element of $N_{a} (v_{i})$
14: until $j = η$
15: end if
16: until $k = z$

VI. Case Study

In this section, the test results based on IEEE 118-bus system and Polish 2383-bus system are used to validate the enhancement in real-time DSE by the NPESP schemes and reveal trade-offs among four objectives of the proposed MaOP. The performance of the improved NSGA-III for large-scale networks is illustrated as well. The simulations are run on a computer with Intel-i5-10400F CPU and 16 GB memory.

A. Metrics

The four proposed objectives in (6), (10), (11), and (12) are considered as metrics for NPESP schemes. To measure the impact of NPESP schemes on real-time performance of DSE, the time to perform a DSE approach is used, i.e.,

t_{D S E} \approx t_{a r e a, m a x} + t_{c o r r e c t i o n}

(20)

where $t_{a r e a, m a x}$ is the runtime of local state estimation in the largest subarea; and $t_{c o r r e c t i o n}$ is the execution time to correct local estimations. Besides, a popular metric in community detection, i.e., modularity $Q$ [

36], is applied to evaluate the strength of partition of a network into subareas, which can be calculated as:

Q = \frac{1}{2 m} \sum_{i \neq j} (y_{i j} - \frac{k_{i} k_{j}}{m}) δ_{i j}

(21)

where $m = \sum_{i, j} y_{i j}$ ; $k_{j} = \sum_{i} y_{i j}$ ; and $k_{i} = \sum_{j} y_{i j}$ . The situation that $v_{i}$ and $v_{j}$ are in the same subarea is represented by $δ_{i j} = 1$ ; otherwise, by $δ_{i j} = 0$ . The partitions with higher $Q$ have more internal lines but less tie lines.

To assess performance of the improved NSGA-III, we select two metrics named IGD and spacing [

21]. The IGD can be used to estimate both convergence and diversity of solutions to MaOP, i.e.,

I G D (P, P^{*}) = \frac{1}{| P^{*} |} \sum_{x \in P^{*}} (\underset{y \in P}{m i n} d i s (x, y))

(22)

where $d i s (x, y) = | | x - y | |_{2}$ ; and $P$ and $P^{*}$ are the obtained solutions and the target points uniformly distributed on Pareto-optimal surface, respectively. We approximate $P^{*}$ with all obtained solutions after ten times of optimization. The smaller IGD indicates the better convergence and diversity of solutions. The spacing measures the standard deviation of the minimum distance from each solution to other solutions, i.e.,

S p a c i n g (P) = \sqrt[]{\frac{1}{| P | - 1} \sum_{m = 1}^{| P |} ({\bar{d}}_{P} - d_{m})^{2}}

(23)

d_{m} = \underset{j}{m i n} \{\sum_{i = 1}^{k} |f_{i} (x_{m}) - f_{i} (x_{j})|, x_{m}, x_{j} \in P\}

(24)

{\bar{d}}_{P} = \frac{1}{| P |} \sum d_{m}

(25)

The smaller spacing represents the better evenness of solutions.

B. IEEE 118-bus System

The IEEE 118-bus system integrated with five distributed generators (DGs), as shown in Fig. 1, is selected as a test network. With reference to [

37], its hybrid measurement system consists of

54

PMUs and a supervisory control and data acquisition (SCADA) system. PMUs acquire voltage phasors of buses and current phasors of branches, and the SCADA system can collect voltage magnitudes, injection power of buses, and power flow of branches. We assume that the measurements from SCADA system cover 50% buses and branches, whereas the pseudo injection power measurements are generated for the remaining 50% buses to guarantee the observability of subareas. The total workload in the test network is 728.

Three popular partition schemes of IEEE 118-bus network are chosen as benchmarks, i.e., three partitions in [

22], six partitions in [8], and eight partitions in [3], which are denoted as REF118-3, REF118-6, and REF118-8, respectively. However, the locations of ESs, i.e., local control centers, are not specified in [3] or [8]. For the convenience of comparison, we consider the node with the shortest average distance in each subarea as the ES location. Table I provides the details of the three benchmarks. To compare runtimes of DSE under different NPESP schemes, three DSE algorithms, i.e., DWLS [7], DUKF [3], [4], and DPF [6], are adopted as testing algorithms. The maximum iterations for each DWLS estimation is

10

, and the number of particles in DPF are

100

. We apply the finite-time average consensus to modify local estimations [3]. Other parameters for the three algorithms can be referred to [3].

Table I Details of Three Benchmarks

Benchmark	ES location	Subarea size
REF118-3	S1: $v_{17}$ ; S2: $v_{49}$ ; S3: $v_{100}$	S1: 35; S2: 38; S3: 45
REF118-6	S1: $v_{12}$ ; S2: $v_{28}$ ; S3: $v_{37}$ ; S4: $v_{80}$ ; S5: $v_{59}$ ; S6: $v_{100}$	S1: 16; S2: 10; S3: 32; S4: 18; S5: 17; S6: 25
REF118-8	S1: $v_{12}$ ; S2: $v_{19}$ ; S3: $v_{27}$ ; S4: $v_{49}$ ; S5: $v_{59}$ ; S6: $v_{80}$ ; S7: $v_{89}$ ; S8: $v_{103}$	S1: 16; S2: 17; S3: 13; S4: 16; S5: 19; S6: 13; S7: 14; S8: 10

In terms of the workload, $C_{m a x}, C_{m i n}, α$ , and $β$ of an ES are set to be $500$ , $50$ , $0.9$ , and $1.1$ , respectively, which are appropriate to obtain NPESP schemes with the same number of partitions as benchmarks. Without loss of generality, $P_{c o s t}$ is set to be $1$ . An NPESP scheme is represented as NPESP118- $j$ , where $j$ is the number of subareas. In the improved NSGA-III, we apply the partial-mapped crossover operator [

20], and set the mutation rate and scale of directed mutation operator to be

0.8

and

10

, respectively. The population size can be three to six times the network size, and more than

40

iterations are recommended via extensive simulations. To obtain robust solutions, the test cases are iterated

100

times with

700

members.

1)　NPESP Scheme Analysis

The non-dominated solutions to the proposed MaOP contain $21$ NPESP schemes, from which six schemes are selected for comparison. The details about the six schemes are given in Appendix B. As shown in Table II, the real-time performance of DWLS, DUKF, and DPF under NPESP schemes exceeds that under the corresponding benchmarks, e.g., the runtimes of DWLS under NPESP118-3, NPESP118-6, and NPESP118-8 are reduced by 19.25%, 36.93%, and 20.00% compared with those under REF118-3, REF118-6, and REF118-8, respectively. Besides, NPESP118-5 outperforms REF118-6 by 11.50%, 17.72%, and 11.08% on runtimes of DWLS, DUKF, and DPF, respectively, while it costs less than REF118-6 according to their $F_{1}$ values. A similar situation occurs in NPESP118-7 and REF118-8. Hence, the proposed MaOP can provide cost-effective schemes to facilitate real-time DSE.

Table II Comparison of Six NPESP Schemes and Benchmarks

Scheme	Runtime (s)			F₁	F₂	F₃	Q	F₄
Scheme	DWLS	DUKF	DPF	F₁	F₂	F₃	Q	F₄
NPESP118-3	0.495	0.264	1.870	3	1.71	9	0.62	4
REF118-3	0.613	0.282	2.111	3	1.74	8	0.61	10
NPESP118-4	0.373	0.190	1.492	4	1.70	20	0.64	9
NPESP118-5	0.254	0.130	1.035	5	1.61	22	0.67	11
NPESP118-6	0.181	0.109	0.702	6	1.60	27	0.68	12
REF118-6	0.287	0.158	1.164	6	1.63	29	0.64	22
NPESP118-7	0.011	0.007	0.318	7	1.45	28	0.69	6
NPESP118-8	0.008	0.006	0.157	8	1.43	32	0.70	3
REF118-8	0.010	0.007	0.306	8	1.64	48	0.59	9

In case of the same ES costs ( $F_{1}$ ), most NPESP schemes have higher cohesion ( $F_{2}$ ) and lower coupling ( $F_{3}$ ) compared with benchmarks, e.g., $F_{2}$ and $F_{3}$ values of NPESP118-8 are 12.8% and 31.25% less than those of REF118-8, respectively. This indicates that NPESP schemes are stronger with enhanced connectivity within a subarea and weakened connections between subareas. It is further testified by the modularity $Q$ , as $Q$ values of NPESP118-3, NPESP118-6, and NPESP118-8 are 1.62%, 5.88%, and 16.05% better than those of REF118-3, REF118-6, and REF118-8, respectively. Nevertheless, we find that the modularity increases with larger $F_{1}$ , which implies a trade-off between the ES cost and the strength of partition. From the perspective of state variable balance, $F_{4}$ values in NPESP118-3, NPESP118-6, and NPESP118-8 are reduced by 60.00%, 45.45%, and 66.67% compared with those in REF118-3, REF118-6, and REF118-8, respectively. With the fixed number of subareas, the proposed MaOP has the ability to balance the computational burdens of ESs. This is the main reason why the runtimes of DSE in NPESP schemes are shorter than those in the corresponding benchmarks. To sum up, the proposed MaOP provides a set of near-optimal NPESP schemes, in which we can select a suitable one to satisfy a single or weighted target without degrading other objectives.

2)　Trade-offs Among Four Objectives

We use the ordinary least square method to fit Pareto front of the proposed MaOP. As shown in Fig. 3, there are linear correlations among the ES cost ( $F_{1}$ ), the cohesion ( $F_{2}$ ), and the coupling ( $F_{3}$ ). Although the state variable balance ( $F_{4}$ ) is not significant correlated with other objectives according to Fig. 3(d), (e) and (f), it has an effect on them, e.g., one NPESP scheme has small $F_{2} (1.452)$ , $F_{4} (2)$ but large $F_{1} (8)$ , $F_{3} (32)$ , whereas another NPESP scheme has small $F_{1} (5)$ , $F_{2} (1.618)$ , $F_{3} (19)$ but large $F_{4} (30)$ . To further demonstrate their trade-offs, we remove one objective of the proposed MaOP in turn to generate four multi-objective optimization problems (MoOPs), i.e., $T_{1} = {F_{2}, F_{3}, F_{4}}$ , $T_{2} = {F_{1}, F_{3}, F_{4}}$ , $T_{3} = {F_{1}, F_{2}, F_{4}}$ , and $T_{4} = {F_{1}, F_{2}, F_{3}}$ . Through the improved NSGA-III, the Pareto fronts of $T_{1}$ , $T_{2}$ , $T_{3}$ , and $T_{4}$ are obtained as illustrated in Fig. 4.

Fig. 3 Pareto fronts of proposed MaOP in IEEE 118-bus network. (a) $F_{1}$ and $F_{2}$ . (b) $F_{1}$ and $F_{3}$ . (c) $F_{2}$ and $F_{3}$ . (d) $F_{1}$ and $F_{4}$ . (e) $F_{2}$ and $F_{4}$ . (f) $F_{3}$ and $F_{4}$ .

Fig. 4 Pareto fronts of four MoOPs in IEEE 118-bus network. (a) Pareto front of T₁. (b) Pareto front of T₂. (c) Pareto front of T₃. (d) Pareto front of T₄.

In Fig. 4(a), $F_{1}$ values are quite dense in the range of $8$ to $14$ , whereas those in Fig. 3 vary between $1$ and $10$ . Thus, $F_{1}$ is not well optimized in $T_{1}$ . The Pareto front in Fig. 4(b) is lack of diversity, as $F_{1}$ values are equal to $3$ and those of $F_{2}$ are greater than $2$ . We can infer that $T_{2}$ fails to trade off the cost against the cohesion. Compared with Fig. 3, Fig. 4(c) shows smaller $F_{2}$ but larger $F_{3}$ , which indicates that the cohesion and the coupling are not balanced in $T_{3}$ . In Fig. 4(d), the solutions are sparse and perform poorly on $F_{4}$ . In summary, the solutions to each MoOP are unsatisfactory on the abandoned objective, i.e., the four objectives are indispensable in the NPESP problem due to their trade-offs.

3)　Performance of Improved NSGA-III

We compare the improved NSGA-III with three evolutionary algorithms, i.e., traditional GA [

15], GA with directed mutation (GADM), and the basic NSGA-III. Since GA and GADM are single-objective GAs, their objective is set to be

m i n F_{G A} = F_{1} + 4 F_{2} + 0.5 F_{3} + F_{4} + P F

, where

4

and

0.5

are coefficients to modify the order of magnitude differences. Based on the number of non-dominated solutions, we regard the first

100

members with the smallest

F_{G A}

as solutions of GA and GADM. The changes in IGD and spacing of four algorithms, as illustrated in Fig. 5, validate that the solutions solved by the improved NSGA-III have the best convergence, diversity, and evenness, followed by GADM.

Fig. 5 Changes in IGD and spacing of four evolutionary algorithms based on IEEE 118-bus network. (a) IGD. (b) Spacing.

C. Polish 2383-bus Test System

To verify effectiveness of the improved NSGA-III for large-scale networks, the Polish 2383-bus system in Matpower [

23] is selected as a test network. It has six zones, in which there are only

8

buses in the sixth zone. We assign the

8

buses to other five zones with regard to electrical connections. It is assumed that PMUs are only placed on the buses with generators or DGs. The proportions of SCADA measurements and pseudo measurements are the same with those in IEEE 118-bus system. Table III provides the details about the modified zones. For the improved NSGA-III, the population sizes and iterations in zones

1

2

, and

5

are set to be

1500

and

150

, respectively, whereas those in zones

3

and

4

are

3000

and

150

, respectively. Others are referred to the parameter setting in IEEE 118-bus network.

Table III Modified Zones of Polish 2383-bus Test System

Zone	Bus number
1	367 buses with 1875 workloads: 1-22, 187-195,197-299, 301-312, 314-398, 400-423, 425-429, 431-469, 471-538
2	283 buses with 1587 workloads: 23-55, 181, 183, 300, 424, 430, 539-656, 658-774, 776-785
3	887 buses with 4651 workloads: 56-110, 180, 184, 185, 399, 470, 657, 775, 786-1601, 1745, 1802, 1803, 1872, 2043, 2083, 2088, 2089, 2092
4	570 buses with 3122 workloads: 111-154, 182, 186, 196, 1602-1744, 1746-1801, 1804-1871, 1873-2042, 2044-2082, 2084-2087, 2090, 2091, 2093-2115, 2176, 2192, 2197, 2201, 2202, 2215, 2217, 2237, 2244, 2247, 2253, 2273, 2274, 2278, 2289, 2310, 2333, 2346, 2376, 2383
5	276 buses with 1482 workloads: 155-179, 313, 1842, 2054, 2116-2175, 2177-2191, 2193-2196, 2198-2200, 2203-2214, 2216, 2218-2236, 2238-2243, 2245, 2246, 2248-2252, 2254-2272, 2275-2277, 2279-2288, 2290-2309, 2311-2332, 2334-2345, 2347-2375, 2377-2382

Figure 6 demonstrates the performance of the four evolutionary algorithms in the largest zone, i.e., zone $3$ . In terms of IGD and spacing, the improved NSGA-III still has the fastest convergence and its solutions are the most diverse and well-distributed, compared with other three algorithms. Furthermore, GA and the basic NSGA-III fail to converge within $150$ iterations, while GADM and the improved NSGA-III have found local optimal solutions after $106$ and $75$ iterations, respectively. This indicates that the directed mutation operator can remarkably promote convergence of high-dimensional NPESP MaOP.

Fig. 6 Changes in IGD and spacing of four evolutionary algorithms based on zone 3 of Polish 2383-bus network. (a) IGD. (b) Spacing.

Trade-offs among the four objectives, which have been demonstrated in Section VI-B, are further proven by Pareto fronts of the five zones, as shown in Figs. 7 and 8. Specifically, in addition to the remarkable correlations between $F_{1}$ , $F_{2}$ , and $F_{3}$ , Fig. 8(d) and (f) presents that $F_{4}$ is negatively correlated with $F_{1}$ and $F_{3}$ , respectively. The relationship between $F_{2}$ and $F_{4}$ is not obviously illustrated, which may result from the complex and discontinuous expressions of $F_{2}$ and $F_{4}$ on decision variables.

Fig. 7 Pareto fronts of proposed MaOP for zones $1$ , $2$ , $4$ , and $5$ of Polish 2383-bus network. (a) Zone 1. (b) Zone 2. (c) Zone 3. (d) Zone 4.

Fig. 8 Pareto front of proposed MaOP for zone $3$ of Polish 2383-bus network. (a) $F_{1}$ and $F_{2}$ . (b) $F_{1}$ and $F_{3}$ . (c) $F_{2}$ and $F_{3}$ . (d) $F_{1}$ and $F_{4}$ . (e) $F_{2}$ and $F_{4}$ . (f) $F_{3}$ and $F_{4}$ .

VII. Conclusion

Based on DSE supported by edge computing, this paper proposed an NPESP problem to find satisfactory partitions and ES locations in a large-scale network. We formulated NPESP as a constrained MaOP which considers the economy of ES placement, cohesion within each subarea, coupling of subareas, and state variable balance. Then, an improved NSGA-III was developed for the proposed problem in large-scale networks. The experiments, which were implemented on IEEE 118-bus system and Polish 2383-bus system, testified that the solutions to the proposed problem can trade off the objectives and significantly reduce the runtime of DSE. Finally, we evaluated the excellent convergence, diversity, and evenness of the improved NSGA-III by two popular metrics, i.e., IGD and spacing. In future, we will take the convergence of DSE and the reliability of ESs into account in the proposed NPESP problem, and demonstrate the impacts of edge computing on the scalability and response time of DSE.

Appendix

Appendix A

For the basic NSGA-III with the population of size $z$ and $k (k \geq 3)$ objective functions, its worst-case complexity at one generation is $O (z^{2} k)$ or $O (z {(l g z)}^{k - 2})$ , whichever is larger [

35]. The presented solution method modifies the basic NSGA-III by adding real-number encoding and gene restriction, and replacing the random mutation operator with the designed mutation operator. Hence, we should analyze the computational complexity of the modified parts, and compare it with

O (z^{2} k)

and

O (z {(l g z)}^{k - 2})

. The real-number encoding and the gene restriction require

O (z)

and

O (z^{2})

computations, respectively. The directed mutation operator with the maximum mutation scale, i.e,

η = n

in Algorithm 1, requires

O (z n^{2} l g n)

computations, where

n

is equal to the number of genes of a chromosome. The value of

z

is generally several times that of

n

. With all above computations considered, the worst-case complexity of the improved NSGA-III is

O (z {(l g z)}^{k - 2})

O (z n^{2} l g n)

, whichever is larger.

The proposed NPESP problem has four objectives and one penalty function, i.e., $k = 5$ . To solve it, the basic NSGA-III and the improved NSGA-III require no more than $O (z^{2})$ and $O (z n^{2} l g n)$ computations at each generation, respectively. The improved NSGA-III has larger computational complexity, since the worst-case complexity of its directed mutation operator is $O (z n^{2} l g n)$ , which is larger than $O (z^{2})$ . Hence, rapid convergence of the improved NSGA-III is achieved by sacrificing the computational complexity.

Appendix B

Table BI shows the partitions and ES locations of the six competitive NPESP schemes for IEEE 118-bus system.

Table BI Partitions and ES Locations of Six Competitive NPESP Schemes for IEEE 118-bus System

Scheme	Subarea	Node number	ES location	Subarea size	Number of tie lines
NPESP118-3	1	1-33, 71-73, 113-115, 117	v₁₇	40	5
	2	34-69, 116	v₄₉	37	7
	3	70, 74-112, 118	v₁₀₀	41	6
NPESP118-4	1	1-20, 33-37, 117	v₁₂	25	9
	2	18, 21-32, 38, 69, 70-76, 113-115, 118	v₃₂	26	13
	3	39-68, 77, 78, 116	v₄₉	33	14
	4	79-112	v₉₄	34	4
NPESP118-5	1	1-16, 33, 36, 117	v₁₂	19	7
	2	17-32, 113-115	v₃₂	19	8
	3	34, 35, 37-45, 49-67	v₄₉	30	10
	4	46-48, 68-84, 96, 97, 116, 118	v₆₉	24	13
	5	85-95, 98-112	v₁₀₀	26	6
NPESP118-6	1	1-20, 117	v₁₂	21	7
	2	21-23, 25-32, 38, 65, 113-115	v₂₅	16	10
	3	24, 33-37, 43-48, 68-75, 116	v₄₇	21	15
	4	39-42, 49-64, 66, 67	v₄₉	22	8
	5	76-82, 95-99, 118	v₈₀	13	9
	6	83-94, 100-112	v₁₀₀	25	5
NPESP118-7	1	1-16, 117	v₁₂	17	5
	2	17, 20-23, 25-32, 113-115	v₃₂	16	7
	3	18, 19, 33-44	v₃₇	14	8
	4	48-67	v₄₉	20	7
	5	24, 45-47, 68-75, 116, 118	v₆₉	14	11
	6	76-87, 94-97, 99	v₇₇	17	11
	7	88-93, 98, 100-112	v₁₀₀	20	7
NPESP118-8	1	1-12, 14, 16, 117	v₁₂	15	4
	2	13, 15, 17-20, 30, 33-39	v₁₅	14	12
	3	21-29, 31, 32, 72, 113-115	v₃₂	15	6
	4	40-49, 65-,68, 81, 116	v₄₉	16	14
	5	50-64	v₅₆	15	6
	6	69-71, 73-80, 82, 96, 97, 118	v₇₅	15	11
	7	83-95, 101, 102	v₉₂	15	6
	8	98-100, 103-112	v₁₀₀	13	5

References

A. Monticelli, “Electric power system state estimation,” Proceedings of the IEEE, vol. 88, no. 2, pp. 262-282, Feb. 2000. [Baidu Scholar]

Q. Li, L. Cheng, W. Gao et al., “Fully distributed state estimation for power system with information propagation algorithm,” Journal of Modern Power Systems and Clean Energy, vol. 8, no. 4, pp. 627-635, Jul. 2020. [Baidu Scholar]

J. Yang, W. Zhang, and F. Guo, “Dynamic state estimation for power networks by distributed unscented information filter,” IEEE Transactions on Smart Grid, vol. 11, no. 3, pp. 2162-2171, May 2020. [Baidu Scholar]

J. Zhao, L. Mili, and A. Gomez-Exposito, “Constrained robust unscented kalman filter for generalized dynamic state estimation,” IEEE Transactions on Power Systems, vol. 34, no. 5, pp. 3637-3646, Sept. 2019. [Baidu Scholar]

W. Zheng, Z. Li, X. Liang et al., “Decentralized state estimation of combined heat and power system considering communication packet loss,” Journal of Modern Power Systems and Clean Energy, vol. 8, no. 4, pp. 646-656, Jul. 2020. [Baidu Scholar]

P. Chavali and A. Nehorai, “Distributed power system state estimation using factor graphs,” IEEE Transactions on Signal Processing, vol. 63, no. 11, pp. 2864-2876, Jun. 2015. [Baidu Scholar]

G. N. Korres, “A distributed multiarea state estimation,” IEEE Transactions on Power Systems, vol. 26, no. 1, pp. 73-84, Feb. 2011. [Baidu Scholar]

Y. Sun, M. Fu, B. Wang et al., “Dynamic state estimation for power networks using distributed MAP technique,” IEEE Transactions on Power Systems, vol. 73, no. 1, pp. 27-37, Nov. 2016. [Baidu Scholar]

F. Wu, K. Moslehi, and A. Bose, “Power system control centers: past, present, and future,” Proceedings of the IEEE, vol. 93, no. 11, pp. 1890-1908, Nov. 2005. [Baidu Scholar]

Y. Wang, P. Yemula, and A. Bose, “Decentralized communication and control systems for power system operation,” IEEE Transactions on Smart Grid, vol. 6, no. 2, pp. 885-893, Mar. 2015. [Baidu Scholar]

T. Taleb, K. Samdanis, B. Mada et al., “On multi-access edge computing: a survey of the emerging 5G network edge cloud architecture and orchestration,” IEEE Communications Surveys Tutorials, vol. 19, no. 3, pp. 1657-1681, May 2017. [Baidu Scholar]

M. Cosovic, A. Tsitsimelis, D. Vukobratovic et al., “5G mobile cellular networks: enabling distributed state estimation for smart grids,” IEEE Communications Magazine, vol. 55, no. 10, pp. 62-69, Oct. 2017. [Baidu Scholar]

D. Du, X. Li, W. Li et al., “ADMM-based distributed state estimation of smart grid under data deception and denial of service attacks,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 49, no. 8, pp. 1698-1711, Aug. 2019. [Baidu Scholar]

T. Zhang, P. Yuan, Y. Du et al., “Robust distributed state estimation of active distribution networks considering communication failures,” International Journal of Electrical Power & Energy Systems, vol. 118, no. 1, p. 105732, Jun. 2020. [Baidu Scholar]

Z. Zhao, H. Yu, P. Li et al., “Optimal placement of PMUs and communication links for distributed state estimation in distribution networks,” Applied Energy, vol. 256, no. 1, p. 113963, Dec. 2019. [Baidu Scholar]

H. Yin, X. Zhang, H. Liu et al., “Edge provisioning with flexible server placement,” IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 4, pp. 1031-1045, Aug. 2017. [Baidu Scholar]

K. Xiao, Z. Gao, Q. Wang et al., “A heuristic algorithm based on resource requirements forecasting for server placement in edge computing,” in Proceedings of 2018 IEEE/ACM Symposium on Edge Computing (SEC), Seattle, USA, Oct. 2018, pp. 354-355. [Baidu Scholar]

K. Cao, L. Li, Y. Cui et al., “Exploring placement of heterogeneous edge servers for response time minimization in mobile edge-cloud computing,” IEEE Transactions on Industrial Informatics, vol. 17, no. 1, pp. 494-503, Jan. 2021. [Baidu Scholar]

S. Burer and A. N. Letchford, “Non-convex mixed-integer nonlinear programming: a survey,” Surveys in Operations Research and Management Science, vol. 17, no. 2, pp. 97-106, Jul. 2012. [Baidu Scholar]

Q. Liu, X. Liu, J. Wu et al., “An improved NSGA-III algorithm using genetic K-means clustering algorithm,” IEEE Access, vol. 7, pp. 185239-185249, Dec. 2019. [Baidu Scholar]

H. Seada and K. Deb, “A unified evolutionary optimization procedure for single, multiple, and many objectives,” IEEE Transactions on Evolutionary Computation, vol. 20, no. 3, pp. 358-369, Jul. 2016. [Baidu Scholar]

H. Li, A. Bose, and V. M. Venkatasubramanian, “Wide-area voltage monitoring and optimization,” IEEE Transactions on Smart Grid, vol. 7, no. 2, pp. 785-793, Mar. 2016. [Baidu Scholar]

R. D. Zimmerman, C. E. Murillo-Sánchez, and R. J. Thomas, “MATPOWER: steady-state operations, planning, and analysis tools for power systems research and education,” IEEE Transactions on Power Systems, vol. 28, no. 4, pp. 12-19, Nov. 2011. [Baidu Scholar]

A. Nawaz and H. Wang, “Risk-aware distributed optimal power flow in coordinated transmission and distribution system,” Journal of Modern Power Systems and Clean Energy, vol. 9, no. 3, pp. 502-515, May 2021. [Baidu Scholar]

W. Zheng, W. Wu, B. Zhang et al., “A fully distributed reactive power optimization and control method for active distribution networks,” IEEE Transactions on Smart Grid, vol. 7, no. 2, pp. 1021-1033, Mar. 2016. [Baidu Scholar]

L. Wang, W. Wu, Q. Lu et al., “Optimal aggregation approach for virtual power plant considering network reconfiguration,” Journal of Modern Power Systems and Clean Energy, vol. 9, no. 3, pp. 495-501, May 2021. [Baidu Scholar]

G. N. Korres, A. Tzavellas, and E. Galinas, “A distributed implementation of multi-area power system state estimation on a cluster of computers,” Electric Power Systems Research, vol. 102, pp. 20-32, Sept. 2013. [Baidu Scholar]

J. Guo, G. Hug, and O. K. Tonguz, “Intelligent partitioning in distributed optimization of electric power systems,” IEEE Transactions on Smart Grid, vol. 7, no. 3, pp. 1249-1258, Oct. 2016. [Baidu Scholar]

I. O. Habiballah and V. H. Quintana, “Integer-linear-programming eigenvector-based approach for multipartitioning power system state-estimation networks,” IEEE Proceedings: Generation, Transmission & Distribution, vol. 141, no. 1, pp. 11-18, Jan. 1994. [Baidu Scholar]

I. O. Habiballah, R. Ghosh-Roy, and M. R. Irving, “Markov chains for multipartitioning large power system state estimation networks,” Electric Power Systems Research, vol. 45, no. 2, pp. 135-140, May 1998. [Baidu Scholar]

S. K. Khan, M. K. Kasi, K. R. Ali et al., “Heuristic edge server placement in industrial Internet of Things and cellular networks,” IEEE Internet of Things Journal, vol. 8, no. 13, pp. 10308-10317, Jul. 2021. [Baidu Scholar]

G. Cui, Q. He, F. Chen et al., “Trading off between user coverage and network robustness for edge server placement,” IEEE Transactions on Cloud Computing. doi: 10.1109/TCC.2020.3008440 [Baidu Scholar]

P. Kansal and A. Bose, “Bandwidth and latency requirements for smart transmission grid applications,” IEEE Transactions on Smart Grid, vol. 3, no. 3, pp. 1344-1352, May 2012. [Baidu Scholar]

S. E. Schaeffer, “Graph clustering,” Computer Science Review, vol. 1, no. 1, pp. 84-93, Jan. 2007. [Baidu Scholar]

K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: solving problems with box constraints,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 4, pp. 577-601, Aug. 2014. [Baidu Scholar]

M. E. J. Newman, “Modularity and community structure in networks,” Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577-8582, Jun. 2006. [Baidu Scholar]

P. Yang, Z. Tan, A. Wiesel et al., “Power system state estimation using PMUs with imperfect synchronization,” IEEE Transactions on Power Systems, vol. 28, no. 4, pp. 4162-4172, Nov. 2013. [Baidu Scholar]

Address:No.19 Chengxin Avenue, Jiangning District, Nanjing 211106, China

E-mail: mpce@alljournals.cn

Tel:86-25-81093060

Fax:86-25-81093040

Home

Introduction

Editorial Board

For Author

Call For Papers

APC

Sponsor & Publisher

Optimal Network Partition and Edge Server Placement for Distributed State Estimation PDF

Abstract

Keywords

I. Introduction

II. Related Work

III. DSE Model Baesd on Edge Computing Framework

IV. Constrained NPESP MaOP

A. Cost Minimization

B. High Cohesion

C. Low Coupling

D. State Variable Balance

E. Constraints

V. Solution Algorithm

A. Basic NSGA-III

B. Improved NSGA-III

VI. Case Study

A. Metrics

B. IEEE 118-bus System

C. Polish 2383-bus Test System

VII. Conclusion

Appendix

Appendix A

Appendix B

References