Rohit Babu| Saurav Raj| Bishwajit Dey| Biplab Bhattacharyya

1Department of Electrical and Electronics

Engineering, Lendi Institute of Engineering and Technology,Jonnada, Andhra Pradesh,India

2Department of Electrical Engineering, Institute of Chemical Technology– Mumbai,Marathwada Campus, Jalna, Maharashtra,India

3Department of Electrical Engineering, Indian

Institute of Technology,Dhanbad, Jharkhand,India

Abstract Safe operation of the power grid requires a complete and robust control network to ensure full observability. However, redundancy measurements can create problems in expense, management, and control. The optimal phasor measurement unit (PMU)positioning problem (OPPP) is proposed to limit the number of PMUs deployed in the power grid and ensure the whole grid's observability in the meantime.A modified branchand-bound algorithm (MBBA) to unravel the OPPP is presented. Original BBA, which uses a single search order to create a binary tree, gives only one solution to the OPPP,although more than one optimal solution exists.The proposed MBBA method consists of two different stages:the vertexes in the search tree are investigated by depth-first search(DFS)in stage 1,and the search route continues as the breadth-first search.In stage 1,the LP relaxing problems are solved by dual simplex,and in stage 2,the basic viable solution from stage 1 is used to configure the primary simplex until the optimum solution is found.OPPP is formulated as a binary decision variable MBBA model,minimizing linear objective function subject to linear matrix observability constraints.The MBBA model is unravelled using a linear integer-based external approximation scheme.IEEE test systems are used to check the feasibility of the proposed approach. Matlab software performs simulation based on a number of graph theory-based methods such as DFS, graphtheoretical method, simulated annealing, and recursive N-algorithms. These algorithms are compared to the algorithmic perspective of the proposed MBBA method.IEEE test network results confirm the validity of the proposed methodology.

1 | INTRODUCTION

Reliable and immediate control of electricity grids has been needed from the outset. Factual information on the working environment of the power grid is required to confirm the safety and optimum operation of the networks. The scope of the state estimation(SE)of the power grid is proposed in this regard. Mainly, SE is the procedure to assess a network operating condition information, provided by a set of placed measurements. SE is necessary to attain effective interoperability, higher scalability, and stability of the power grid [1].Formerly, supervisory control and data acquisition (SCADA)frameworks were used to conduct these operations [2].SCADA offers non-synchronized measurements dominating misestimating of network status[3,4].Also,the data scan rate of about two to six samples per cycle, which is quite slow,makes them indecisive about catching the sub-second directive's limited disturbance on the grid. These issues can be solved by incorporating the phasor measurement unit (PMU)in the power grid. PMU is an essential component of a widearea measurement system is used in complex power grid monitoring, preservation, and control operations [5]. PMU tests the network condition, that is, voltage magnitude and phase angle of a given position at several samples per second.Data is time-stamped by a global positioning system (GPS)technology.

PMUs are becoming particularly relevant to electrical engineers, academicians, and scientists. PMU can provide coordinated sub-second measurements of actual phasors and current phasors using GPS technology [6, 7]. They are widely used in various utilities for several purposes, such as postmortem investigation, adaptive preservation, network preservation design,and SE[8].By utilizing the PMU measurements in various power grid fields, such as preservation, online monitoring, SE [9], load shedding, voltage instability, efficacy,and robustness,are expected to be enhanced[10].Some PMUs are already installed for various applications such as postmortem analysis, adaptive security, device protection schemes,and state estimation.One of the significant problems that require to be focused on the developing technology of PMU is an optimal or strategic location.

In the present situation, the installation of PMU has been progressing slowly due to significant investments required for the placement sites [11]. Placement sites need to provide a communication infrastructure for the PMU to function and a limited percentage of placement sites that impede its installation. Furthermore, the cost of the PMU itself is prohibitive;however,it is expected that the price will be lowered if there is more demand in the future. Recent research has shown that using the PMU attributes and the implementation of Kirchhoff's current law (KCL) and Ohm's law, the PMUs number required to achieve the power grid's full monitoring can be minimized if the PMUs are strategically sited[12].Therefore to reach the price benchmark and the planned PMU operations,the formulation of the optimal phasor measurement unit placement problem(OPPP)is appropriate.The purpose of this research is to unravel the OPPP in the context of a merger strategy.

Several methods have recently been suggested utilizing separate groups of optimization strategies to evaluate the OPPP. Optimization approaches used to unravel the OPPP can be classified as deterministic and stochastic algorithms[13,14].Among the wide ranges of different algorithms of the stochastic method,the multi-objective evolution algorithms are powerful stochastic methods to unravel the OPPP [15–19]. In[20], an ambitious work was done between the linear programming (ILP) with binary-valued variables and non-mixed integer LP technique. The ILP with binary-valued variables is solved with a branch and bound with one order, whereas the inherent tree structure is being solved. Different optimizers have been adopted. Each one leads to a different optimal solution including the radial buses, and the innovation of this work was the two-phase branch and bound,which depends on the initial point.

Ref. [21] proposed the adaptive genetic algorithm for OPPP. However, the obtained results are not optimal. In ref.[22], the author has employed the differential evolution method for OPPP to achieve the full observability of the network, but failed to show the scalability of the proposed method. Work in [23], a two-step integer ILP approach was proposed. Also, because OPPP is a combination optimization challenge, the authors have not shown several solutions. The author suggested a regular binary variant of the particle swarm optimization (BPSO) to identify the OPPP [24].However, the traditional BPSO suffered from premature convergence and is stuck in local minima, particularly in complex combination problems. A stochastic and deterministic approach has been proposed to minimize PMU in [25].Two strategy-based mechanisms are proposed in [26]. First,the conventional objective function is known to mitigate the number of PMUs and, later, minimize the expense of PMUs and their communication facilities. A related study is also introduced in [27].

In [28], to overcome the OPPP, the updated form of the binary-ILP was proposed. In addition, a line voltage stability index system was established to classify the weakest bus and,at the same time,to attach the PMU for improved tracking.Related study work has also been done in[29,30].The only distinction being the fastest voltage stability index used to evaluate the weakest vertex. Hybridization of a branch-and-bound and genetic algorithm has been presented in [31] for unravelling the OPPP. In [32], the improved OPPP approach, taking into consideration bounded shortcomings in the distribution of observability, is predicted by presenting the idea of partial observability. Ref.[33] developed a new formulation of a zero injection bus (ZIB) in OPPP. Simple scenario, PMU loss, line outage, and channel restriction were also considered. Work in[34] proposed the numerical methodology to solve the OPP problem considering various contingencies considering partial observability, that is, depth-of-one and depth-of-two unobservability based on binary integer linear programming(BILP).

In ref. [35], dynamic multi-stage PMU positioning is developed and the validation of the proposed model is often tested in both probabilistic and deterministic contexts. Ref.[36] used deterministic methods, mixed-ILP and non-LP, to unravel the OPPP.In particular,power transfer,ZIB modelling along with communication infrastructure limitations, PMU outage, and restricted channel capability contingencies were analyzed. In ref. [37], a multi-objective probabilistic coordinated approach for SE in the power grid, considering the optimum location of PMUs in the case of bad data and incomplete measurements, was described. Ref. [38] proposed semi-definite binary programming, taking into consideration different contingencies such as line and PMU outage. Redundancy measurement is often taken into account in the rating of solutions. In [39], a risk-based PMU installation approach has been suggested. The mentioned approach target was twofold,precisely the probability of the lack of observability and the severity of its subsequent repercussions for the OPPP technique. Authors in [40] investigated the quality restrictions of fault localization using PMU measurements. Chen et al. [41]proposed the approach for unravelling the OPPP in the presence of contingencies is modelled in a simplified form that allows an examination of N-1 or N-2.

From a succinct guide to PMUs, it can be acknowledged that it is possible to explicitly check the power grid's performance by installing PMUs on all buses without using a state estimator [42, 43]. However, it is uneconomical. Further,considering the monetary value, the increasing size of the power grid also makes it a tedious task to control and manage so many PMUs if they are placed on each bus.Therefore,it is also unwise to install the PMU throughout all buses.Our main goal is to achieve a full power grid observability through as few PMUs as possible, that is, the OPPP. The contribution of the work mainly focuses on the assessment of the proposed MBBA method with depth-first search (DFS), graph-theoretic procedure (GTP), simulated annealing method (SAM), and recursive security N algorithm (RSNA) considering merging strategy for ZIBs and radial buses. The effectiveness and efficiency of these algorithms are analyzed and compared in theory and via simulation with the proposed method.

The remaining structure of this study is as follows: Section 2 explains observability analysis using PMUs and the formulation of OPPP. The interpretation of the proposed method for the OPPP is given in Section 3.Section 4 exhibits the simulation results of unravelling OPPP and provides an analysis of the results and followed by the final remark in Section 5.

2 | OBSERVABILITY ANALYSIS USING PMUs AND THE MATHEMATICAL FORMULATION OF OPPP

The target of the OPPP is to confirm that the power grid is completely observable. In the OPPP, it is important to check the network's observability before the final solution to the problem, or rather the final implementation of PMUs is concluded. In this manner, the power grid's observability can be verified since the power grid's measurements can create a full spanning tree of this network; the network is completely measurable [42]. The observability of a given grid depends on the form and position of the measurements available and the structure topology [44]. Thus, the study of power grid observability uses network-related graph theory, their corresponding equations, and solutions [43, 44].

For observability analysis, the network can be considered as a graph with set of vertexes N and edges E,respectively,and it can be given as

where each edge has two distinct terminal vertexes.A subgraph can be defined as

where N′⊆N and E′⊆E.

In observability analysis, the OPPP can be changed into the problem of determining a minimum subgraph, which fulfills N ⊆N′if the subgraph is explained via Equation (2).Therefore, a set of observability requirements for evaluating the measurable areas in a network after a PMU is placed on a bus as follows [43, 45]:

Criteria I.For a bus with the PMU,the voltage and current phasors of each branch connected to that bus are identified;

Criteria II.If the voltage and current phasors at a bus are identified, the voltage phasor at the other buses linked to this bus can be computed via Ohm's Law; and

Criteria III. If voltage phasors at two linked buses are identified, then the current phasor at the branch linking two buses can be computed.

Here, the first criterion is known as direct measurements,and the second and third criteria are known as pseudo measurements.

2.1 | OPPP formulation

OPPP's key target is to minimize the PMU's placement cost.For an n-bus system, it may be formulated as

where ciis the cost of placing a PMU at bus i,xi=1if PMU is positioned at the bus and xi=0 or else, f(X) signifies the observability constraint, A represents the binary vertex-tovertex matrix and is defined as

where aijillustrates the element placed at the ithrow and the jthcolumn in A and I is a vector who has n entries and whose elements are all 1 if our objective is only to ensure the power grid's observability completely.For bus i in n-bus system,the corresponding constraint function fican be given as

If fi(X)≠0,that is,if aij=1 and xj=1(j=1, 2,…,n),the bus i is observable.If all buses are observable,especially,if all fi(X) in F(X) are non-zero, which also must be greater than 1, the network is entirely observable.

Let us suppose that ci=1, Equation (3) can be written as

Generally,Equation(6)is used when there is no significant difference in the costs of place on any bus.

2.2 | Redundancy measurement in observability

According to the rule mentioned in Section 2.1, if a bus j can make bus i observable(i ≠j),then bus j must be bordering to bus i and PMU is positioned at bus j,that is,xj=1.Therefore,if bus j can make bus i observable (i ≠j), aijxj=1 must be fulfilled, that is, for a n-bus system, the equation∑aijxj∀j ∈N; 1 ≤j ≤n; j ≠i shows how many bus j exist to back bus i observable.Meantime,bus i is also observable if a PMU is positioned at that bus. Based on Equation (4),aii=1.

Hence, aiixiindicates, bus i is observable with a PMU equipped bus.Also,Equation(5)shows however many sources there are to help the bus i to be observable.Thus,if a full bus in the power grid is observable, the inequality f(X)≥I must be satisfied. In fact, there is often more than one source to confirm the observability of all buses, so that all buses can be detected when one source is missing [34, 42]. In this case,Equation (3) I needs the modifications in constraint inequalityf(X)≥I. Then, it can be given as

where b is (n×1) vector whose elements bi≥1. If for any bus in a network,there are at least two sources who can make that bus observable, the constraint inequality in Equations (3)and(6)can be given as Equation(7)where b is a n by 1 vector whose entries are all 2 and n is the number of buses in that system.

2.3 | Modelling of zero injection buses for OPPP

A bus is termed zero injection when neither load nor generator bus is connected to it[46].Consideration of ZIBs complicates OPPP.The following criterion is taken into account for ZIBs:

Criteria IV.For a ZIB without a PMU,except for one,an unknown outgoing current can be evaluated through KCL.

Criteria V.For a ZIB,assuming that the voltage phasors of buses associated with this bus are identified, the voltage phasor of this bus can be determined with the help of Kirchhoff's Voltage Law (KVL); and

Criteria VI. In the case of a group of linked ZIBs, if the voltage phasors of buses linked to this cluster of buses are identified,the voltage phasors of this cluster of buses can be evaluated using KVL.

Criteria IV–VI are termed as extended measurements considering ZIBs [43, 47]. These criteria can be further summarized as if all but one of a ZIB and its nearby buses are observable, then the ZIB and all its neighbouring buses are observable.Commissioning these three criteria, a more OPPP solution may be achieved compared with that only using the criteria I–III, as given in Section 2.1.

As shown in Figure 1, conferring to criteria I–III (as mentioned in Section 2.1),at least two PMU is needed to make a network fully observable, since at most three buses are deemed measurable if a PMU is positioned in the power grid.According to criteria IV–VI(considering ZIBs),a PMU placed at bus 2 is necessary to render the power grid entirely observable. If a PMU is positioned at bus 2, then bus 1 and 3 are considered observable. Buses 2 and 3 are observable according to criteria I–III and bus 4 is observable by calculation using KCL and KVL as bus 3 is a ZIB. In this study, for the formulation of the OPPP considering ZIB, the merging strategy is used.That is to merge individual ZIB into one of its neighbouring buses.As per criteria IV–VI,if all ZIBs adjoining buses are observed,ZIB is also observed.The merging strategy aims to make all of the individual ZIB neighbouring buses observable, and then individual ZIB is guaranteed to be observable.

Case 1 Merging ZIBs on graph

In [47–49], the authors discussed that a network's observability can be found by commissioning Equation (3) to analyze the modified vertex–vertex matrix of the network in which individual ZIB is merged into one of its neighbouring buses.The author here discusses that this method sometimes is operable but may lead to undesirable outcomes. Figure 2b is obtained by merging bus 4 into bus 3.Therefore,the vertex-tovertex matrix can be built according to Figure 2b and can be used to examine Figure 2a network observability.On the other hand, according to Equation (3), Figure 2b can be completely observable by placing a PMU at bus 3′,which is a nonexistent bus in Figure 2a.

Here, two conditions arise to analyze these situations:Condition 1,place a PMU at either bus 3 or 4 in Figure 2a;or Condition 2,place a PMU at each of bus 3 and 4 in Figure 2a.In condition 1,it is evident that placing a PMU either at bus 3 or 4 is not able to make the network entirely observable.Mazlumi et al. [49] discussed that considering ZIBs is nonexistent after each of them is merged into one of its neighbouring buses, as shown in Figure 2. PMU placed at bus 3 makes the original network completely observable. Since PMU is positioned at bus 3′can ensure the full observability of the modified networks.Here,their theory does not fit.Condition 2 can guarantee the network's observability. However, it results in redundancy in a situation as displayed in Figure 3. The network presented in Figure 3 can be wholly observable by deploying a PMU on any bus.Though,considering condition 2 and the merging strategy, at least two PMU are needed to observe the network thoroughly.

There is still a condition 3 for coping with the situations,as set out in Figures 2 and 3.That is,positioning a PMU on every bus created by the merger strategy is unwise.While condition 3 unravels the OPPP in Figures 2 and 3,it still causes duplication in some situations, as depicted in Figure 4.

The modified 4-bus network is obtained through merging bus 3 into bus 2.If PMU is not permitted to be placed at bus 2′, then to ensure the whole network's observability, PMU must be positioned at buses 1 and 4. It is evident that a PMU positioned at bus 3 is enough to certify the original network's observability. In summary, the author here explains that it is not a very reliable method to analyze the original network's observability through analyzing the modified network where individual ZIB is merged into one of its neighbouring buses.

Case 2 Merging ZIBs constraint equations

This method schemes to consider a pseudo measurement placed on the line between a ZIB and one of its neighbouring buses and then deal with ZIBs as normal buses[43].According to criteria IV and V,conceding that all buses but one linked to a ZIBs are observable, then this cluster of buses are observable if either of that one bus or the ZIB is observable. From Figure 4, three assumptions can be stated as follows:

FIGURE 1 Example of commissioning zero injection bus in optimal phasor measurement unit placement problem

1). If buses 1 and 2 are measurable, then the grid is totally observable if at least one of the ZIBs,that is,buses 3 and 4 are observable;

2). If buses 1 and 4 are measurable,then the grid is completely observable if at least one of the ZIB,that is,buses 2 and 3 are observable; and

3). If buses 2 and 4 are measurable, then the grid is wholly observable if at least one of the ZIB,that is,buses 1 and 3 is observable.

From the above illustration, when a bus linked to the ZIB is preferred to pair up with the ZIB, the power network will come to be entirely observable if at least one of these two buses is observable and the other but not these two buses are observable.Hence,the pair of ZIB and one of its neighbouring buses can be treated as a group and have the same constraint function about their observability; and the constraint function is obtained via merging the two buses [42, 43]. Therefore, the vertex-to-vertex matrix of the original 4-bus network, as displayed in Figure 4a can be written as

FIGURE 2 Zero injection bus merging strategy:(a)original 5-bus network and(b)modified 5-bus network

FIGURE 3 Redundancy triggered by zero injection bus merging strategy: (a) original 3-bus network, (b) modified 3-bus network, and(c)original 3-bus network with phasor measurement unit equipped buses 1 and 2

FIGURE 4 Redundancy caused by zero injection bus merging strategy: (a) original 4-bus network and (b) modified four-bus network

and it can be modified as

conceding that bus 2 is preferred to pair up with the ZIB,that is,bus 3.Then,the modified vector constraint equation can be given as

It is to be noted that in Equation (10), there are always repetitive constraints among fiof which F′(X) is composed since individual ZIB and one of its neighbouring buses have the same constraint. For that reason, F′can be further simplified by removing one from the individual pair of two repetitive constraints in order to improve the scalability.However, Equation (10) is not an essential condition to a network's complete observability since a ZIB is often assumed to have the same constraint as its neighbouring buses. This means that the full observability of the grid does not ensure that the inequalities in Equation (10) are resolved, since the observability of the ZIB may be ensured by another bus, but not by the selected one. For example, If two PMUs are positioned at buses 2 and 4, respectively, as shown in Figure 4a,then the power grid is considered not wholly observable because bus 1 is unobservable.

Nevertheless, bus 1 is observable through KCL and KVL conferring to criteria IV and V. Therefore, conceding that the merger strategy is used on PMU-equipped bus 1 to render the whole power grid observable; thus, redundancy occurs.

不断完善水利施工质量管理，可以进一步指导水利工程施工企业正确开展施工行为，同时提高水利施工企业的经济效益。通过质量管理制度的建设和加强，可以有效地实现工程建设的“三控制、两管理、一协调”。监理单位在具体施工管理中，利用长期在工程建设实践中所形成的工作经验，建立起一套完整严密的组织机构、工作制度、控制程序和方法，加强对工程质量的控制，构建工程建设项目的质量控制体系，强化工程质量的管理。因此，必须深化对水利施工质量管理核心地位的认识，从而增强对工程质量的监管，推动水利工程建设。

2.4 | Development of OPPP model

The main elements in the OPPP model are as follows:

2.4.1 | Data

ℑ: set of buses

n: number of buses

ci: PMU cost

aij: entries are as shown in Equation (4)

a(i): the set of buses associated through lines to bus i.

2.4.2 | Variables

The decision variables involved in this OPPP are

2.4.3 | Constraints

The inequality constraints are

2.4.4 | Function to be minimized

The total cost

subject to constraints points (ii)–(iii).

3 | INTERPRETATION OF THE PROPOSED METHOD FOR THE OPPP

Since OPPP was suggested, a variety of stochastic and deterministic approaches have been formulated. Many of the proposed optimization approaches are not always guaranteed to find the optimum solution for OPPP. The factors that lead to these ideal outcomes are often different. Integer programming (IP) and some local search algorithms, besides imprecise constraint functions, can also be trapped in local minima or local maxima in practice and therefore skip the optimal global solution [50, 51]. In this research work, DFS,GTP, SAM, and RSNA are compared with the proposed MBBA method.

3.1 | Depth-first search

DFS is an algorithm for tree or graph data structures to traverse or explore.DFS explores a tree from an ancestor vertex to the current vertex and then from another descendant vertex until no descendant vertex exists[43,52].Then,it will return to the parent vertex a level above the current vertex and search from another descendant vertex to the current vertex.Figure 5 displays the path of vertex visits in DFS while searching for a tree [43].

Whenever a PMU is installed at a bus, this bus position should be reported; and the final solution is listed. DFS only uses Equation(3)or criteria I–III to construct a constraint for finding network observability and does not consider ZIB.From the flowchart, it is to be noted that the algorithmic perspective of DFS is the same as the greedy method. Specifically, DFS here still looks for local solutions instead of global solutions. Greedy algorithms are typically quicker, but the obtained solutions are not optimal [22]. DFS seeks solutions very quickly with this simple, linear equation plus the greedy heuristic algorithm employed by DFS. The cost is,however, the optimality of the solution it seeks. Figure 7 depicts the implementation flowchart of DFS in OPPP.

3.2 | Graph-theoretic procedure

GTP's algorithmic mechanism is the same as DFS,except that GTP considers ZIB in OPPP.When unravelling the OPPP for complete observability of the power network, GTP adopts some approach to assessing ZIB [45, 53]. In this study, a merging strategy is proposed for ZIBs. Further, the new vertex-to-vertex matrix can be obtained either by merging ZIBs on a graph or merging ZIBs constraint, as illustrated in Section 2.3.However,both approaches may cause redundancy and,therefore,be incapable of determining the OPPP solution.In Section 2.3, several examples have been given. From these examples,it is to be noted that if an incorrect approach is applied to deal with ZIBs in certain instances, a bad solution would be found. And when merging is followed, the bad solutions are more likely to be obtained because this method uses a very unreliable restriction vector function as given in Equation (10). Henceforth, GTP will not necessarily determine a better solution than DFS in some circumstances,mainly when utilizing the merging strategy. Though GTP has a similar pattern in how to expand child vertexes, comparing to DFS,GTP may be able to unravel the OPPP solutions using the revising method. The cost, however, is that the revised constraint vector function f(X) can be used to build and compute more resources.

3.3 | Simulated annealing method

SAM is focused on the comparison of simulating strong annealing and unravelling broad combinatorial optimization problems[54].SAM is a type of stochastic method,local search.To grasp the basic idea of local search,consider the problem's situations,as depicted in Figure 8[55].The individual point in the graph has an ‘elevation’, well-defined via an objective function.If ascent coincides with an objective function,then the goal is to determine the topmost peak,a global maximal,and the process termed hill climbing(HC).If ascent coincides with cost,then the goal is to determine the lowermost basin, a global minimal,and the procedure known as gradient descent[55].

The algorithmic perspective of the SAM is similar to HC[55].But,the HC search stuck at the local solution and therefore may fail to reach the global solution.In metallurgy, during the process of annealing,SAM simulates the motivation of atoms.In the course of searching,SAM accepts a bad solution in probability if no better solution is found[43].SAM is anticipated to be able to determine the global solution in some probability through leaping out from the corral caused by the local solution[43,55].The SAM in OPPP was originally proposed in[45].The algorithmic perspective of the SAM is described in Figure 9.In this flowchart,an upper limit and lower limit are set to constrain the search space. The upper limit signifies the possible maximum number of PMUs assumed to make the power grid wholly observable, and the lower limit defines the possible minimum number of PMUs assumed.The pseudo-code of the SAM for OPPP is given in Algorithm 1.

Algorithm 1 Pseudo-code of the SAM for OPPP Initiate Estimate coverage of OPPP solution set S Ea : n- no. of buses in the area under observation T : =15 K : =min｛0.002�n ��vtest , Kmax for i: =1 to 40 carry out for j: =1 to K carry out choose a PMU randomly save the position of the assigned PMU bus choose a non-PMU bus arbitrarily estimate coverage of the adjusted positioning set Ea(new) : n-no. of buses in the area under observation if Ea(new)=0 then return to 'grid observable'

FIGURE 5 Path in which vertexes are visited while depth-first search is used

FIGURE 6 Flowchart of the depth-first search scheme

?

FIGURE 7 Depth-first search algorithmic process flowchart for optimal phasor measurement unit placement problem

FIGURE 8 Local search algorithm

FIGURE 9 Flowchart for the algorithmic perspective of simulated annealing method

The SAM proposed in [45] has a lesser probability to determine the OPPP solution since it may fail to reach the optimal solution by underestimating the possible number of PMUs in the OPPP. The author in [43] proposed a modified SAM in which a new perturb function is implemented to increase the randomness and increase the probability of determining OPPP solutions. Various improvements to SAM have been suggested to dates, such as pragmatic multi-stage SAM [56], novel multi-stage SAM[57], hybrid SAM [58], and hybrid genetic algorithm and SAM [59] to escalate the prospect of SAM for determination of the global solution within a reasonable timeframe.But stochastic and local search combination will make it still hard to find the best global solution for OPPP for every modified SAM.

3.4 | Recursive security N algorithm

The method of finding the best solution to OPPP is also the method of finding out the least subgraph of G=｛N, E｝, as described in Section 2. The Prim algorithm is a standard algorithm for finding the minimum spanning tree (MST) of a given graph [60]. In the Prim algorithm, all of the lines in a graph are first deleted, then any vertex is chosen as the vertex that was initially added. Then, by repeatedly implementing an‘unintroduced’ vertex, an MST is created by restoring a line with a minimum weight between the‘unintroduced’vertex and an introduced vertex currently connected by only one line[43].When MST is used in OPPP, the observable region with present PMUs will be maximized. Besides that, this approach is complicated to accomplish because the constraint function is nonlinear considering ZIBs.

In a system with N number of buses, when the Prim algorithm is used,at least N MST must be created using each bus as the initial place where the first PMU is placed. Authors in[61]proposed a revamped MST method and termed an RSNA.Figures 10 and 11 show the flow chart for MST and RSNA,respectively.RSNA's algorithmic viewpoint is the same as DFS,replicated as much as a vertex number. For generating MSTs,ZIBs are not considered in RSNA.

Nevertheless, RSNA maximizes the observable region only by placing PMUs at the buses that are not observable with PMU equipped buses. To further limit the quantity of the generated MSTs, RSNA only does the revamped DFS N times for a network with N buses, and initial buses are chosen to place the PMU. Though the trees generated in this stage are not inevitably the true MST, the total developed MST needs to be stored for the following authentication and fathoming.

As MSTs are generated, numerous PMU employments are achieved. RSNA needs to check if any alternative pattern search exists for each placement. The MST generation is successively clarified for further enhancement, as illustrated in Figure 12.

Individually, each exclusive set of PMU is replaced by the buses linked to the vertex where a PMU was initially created.This form of ‘small signal’ differential is checked to deliver other strategies that can offer functional advantages for the optimum physical implementation of PMUs. In different alternate pattern searching strategies, PMUs based on lone lines connecting to the power grid are interchanged on neighboring buses. This operation provides direct current measurements, which can minimize error variance.

If there are no pure transit vertexes in the method, the mechanism stops at the first stage. Otherwise, the last real set filtering is done by eliminating individual PMU and checking that the device stays measurable,as seen in Figure 13.To boost scalability, the algorithmic method proved to be operational when extended only to solution sets with a minimum number of PMUs.

RSNA reduces the time and space complexity of the MST algorithm when implemented in OPPP and can obtain many OPPP solutions. But as the network's scale grows, RSNA's scalability can be undermined.In this study,a modified branchand-bound algorithm (BBA) is proposed to address the scalability problem.

FIGURE 1 0 MST flowchart. MST, minimum spanning tree

3.5 | Modified branch-and-bound algorithm

Land and Doig developed BBA in 1960 for binary problems.It is limited to IP problems.It can be tested with different kinds of problems. It is based on the belief that the complete set of possible solutions can be split into small-scale subsets of solutions. These small-scale subsets can then be measured analytically until the most exceptional solution is found.When the BBA is tested for an IP problem,it is used in combination with the simple non-integer solution method. The BBA flowchart is shown in Figure 14. This work proposes a modified BBA for OPPP,which combines both DFS and BFS(best-first search) executed by mixed-integer non-LP branchand-bound (minlpBB) optimizer within TOMLAB [62, 63].MBBA is utilized in finding solutions for both integer-IP(ILP)and mixed-integer non-LP (MINLP) issues.

FIGURE 1 1 RSNA flow chart for OPPP. OPPP, optimal phasor measurement unit placement problem; RSNA, recursive security N algorithm

MBBA is a tacit enumeration methodology by which the global optimum solution can be obtained.This algorithm deals with ILP, mixed-ILP, and binary-ILP problems [64]. The algorithmic procedure is explained with constant variables,and weak constraints replace integer constraints. If the obtained explanation is an integer in nature,then the algorithmic process is concluded. If one of the particular integer variables ykis constant,two new sub-problems with maximum yk≤|yk|and minimum limit restriction yk≥|yk|+1 are solved [65]. This branching process means that potential integer answers are not eradicated.

Branching is the technique of splitting a mixed-ILP into sub-problems. There are three basic methods in ‘MBBA’ [66].First, the usable search space must be separated such that the latest sub-problems are not mixed-ILP. The meaning of this process is that linear inequalities constraints develop the subproblems. Second, adding the sub-problems' usable search space could cover at least one strategic solution.Third,because the essential purpose of the branching is to improve the whole lower bound, it is beneficial that the small solution is not included in either the partition representatives or the whole lower bound would be exacerbated. These added restrictions explain the branching dilemma. Branching includes the result of more than one sub-problems such as an ILP.The method is continued until a plausible discrete integer explanation is sought.These found results agree to the maximum limit of the objective function for minimalization of the issue.

Furthermore,in branching,if any branch has the objective function worth more than the maximum limit, the vertex iseliminated. If the objective function value is less than the full limit value,the value is upgraded.Methodology proceeds until all vertexes are searched.The minimal objective function value for the possible integer discrete alternative provides the optimal objective function value.Figure 15 displays the MBBA flowchart.

FIGURE 1 2 Pictorial representation of alternative pattern search using recursive security N algorithm

FIGURE 1 3 Pictorial image of filtering in pure vertexes

FIGURE 1 4 Branch-and-bound algorithm flowchart

The number of ILP sub-problems created to build the whole tree varies from strategy to strategy [67]. In respect of the tree search strategy,BFS is used.Also,DFS,as well as BFS,are executed. BFS is the fundamental technique for searching the undirected graph, while DFS is an alternative mode of crisscrossing the graph.DFS picks the succeeding candidate to be a vertex at the thoroughgoing depth in the intrinsic tree framework.The search methods can be static and hybrid.The static BBA method applies an existing rule to pick the next sub-problem for optimization. The abovementioned BBA is used for the determination of the search order to assemble the intrinsic tree framework.

Further, the developed MBBA approach 2(y,z) changes from plan′y′to plan′z′as given in[68].The MBBA executes a DFS before a distinct solution is sought and move to BFS.Starting from the transformation of the MINLP into LP relaxation issues, the optimal solution is determined with MBBA, as explained above [66]. In stage first, an initial possible solution to initialize the optimization issue is determined. The second stage is to determine the optimal solution utilizing a BFS [69]. Optimization involves enumerating each integer point,removing difficult ones,estimating the objective function at all enumerated integer points, and deciding the optimal value point [66].

In MBBA, LP relaxation executes a necessary process to evaluate each sub-problem using a dual simplex to optimize it from the parent vertex's optimum basis. This approach minimizes the number of simplex iterations to determine the child's vertex and speeds up the complete computing capabilities. The original simplex calculated the exact solution point from a potential primal basis. Any iteration of the initial simplex approach transfers from a BFS to another BFS can never raise the objective feature before an optimum point is reached [70]. In this study, utilizing the TOMLAB/minlpBB optimizer engine, the MBBA includes two stages: In stage 1, DFS examines vertexes in the search tree, and the iterative procedure BFS follows the search path. In stage 1, the problems of LP relaxation are determined by double simplex. The first stage uses the possible basic solution to initialize the primal simplex until the best solution is achieved [70]. The BFS flowchart is shown in Figure 16.

FIGURE 1 5 The modified branch-and-bound algorithm flowchart

FIGURE 1 6 The flowchart for breadth-first search

In this study, assumed a graph which is undirected depicting the connected power network, the problem of determining the OPPP to install on the edges such that the graph is wholly monitored,is considered.The MBBA based on integrating both DFS and BFS methods to determine the solutions for the OPPP is proposed. Moreover,this work solves the OPPP in an MINLP framework with discrete variables executed by the proposed method of eliminating radial buses.In consequence of that, the different strategy of MBBA is examined to optimize the OPP problem. Individually, BBA follows a separate process for the determination of the search order. Determining a potential incumbent solution enables initial fathoming and hence the extension of a smaller search tree leading to several optimal solution sets, as found in this work.

During the process, the proposed method is implemented by a suitable optimizer engine called minlpBB of the TOMLAB optimization package. DFS explores vertexes in the exploration tree in stage 1, and the repeated technique pursues a search route as BFS [63]. In stage 1, the LP relaxation issues are resolved by dual simplex. In stage 2, the possible solution from stage 1 is used to initialize the primal simplex until the most promising clarification is obtained [66].

4 | RESULTS AND DISCUSSION

Here, the author has used benchmark networks,IEEE 14,30,57, 118 and New England 39 bus system, respectively, for observability analysis.The simulations are carried out ignoring redundant observability; and for bus i, ciis assumed to be 1,the cost of installing a PMU on every bus is assumed to be the same.The OPPP is solved through the following steps:(i)read the network branch/bus data(IEEE data),(ii)form the binary connectivity matrix and the PMU cost coefficient vector, (iii)form the right-hand side unity vector,and(iv)solve the OPPP.The author has used DFS, GTP, SAM, RSNA, and MBBA approaches for unravelling the OPPP [71]. For the simulation purpose Matlab (R2013b) with PC having a configuration of 2.0 GHz, i3-5005U CPU and 8 GB RAM is used.

The number and location of radial and ZIBs for IEEE 14,30, 57, 118 and New England 39 bus systems are shown in Tables A1 and A2, respectively. Tables A4–A7 describes the connection of ZIBs for IEEE 14, 30, 57, 118 and New England 39 bus systems, respectively.

From Tables 1–5, it can be noted that the consistency of the OPPP solution is very low when GTP is employed using a merging strategy. It is much worse than DFS, which does not care at all about ZIBs. This finding also shows thatredundancy is very likely to be triggered by the merging strategy. And this property does not make the OPPP solution illustrated by GTP using the merging process better or worse than that found by DFS. The functionality of ZIBs could not be used successfully by the merging strategy.When dealing with ZIBs, the method of merging, which is listed in several articles as a useful process, is merely ineffective. Also, both of the two techniques are very fast. Their existence as a greedy algorithm will guarantee that the complexity of their time is minimal. As a matter of fact, the optimality of the solution carried out by an algorithm is a more important condition for evaluating the algorithm.Taking these conditions into consideration, both DFS and GTP methods are not ideal for OPPP; relative to SAM,RSNA, and MBBA, the optimality of the solutions described by them is not good.

TABLE 1 OPPP solution for 14-bus system using DFS, GTP, SAM, RSNA, and MBBA

SAM uses a nonlinear constraint to cope up with ZIBs.The simulation was carried out 20 times for all test systems to evaluate SAM probabilities to find optimal solutions.Tables 1–5 show the most optimal solutions SAM has sought.It can be recognized from Tables 1–5 that SAM did not do very well.In the case of the IEEE 118-bus test method,SAM did not even find any placement better than the initial placement obtained via GTP. The suggested MBBA approach, on the other hand,outperforms other algorithms in the optimality of the best locations found and the scalability is very high. However,MBBA can find the best solution in polynomial-time relative to either DFS or GTP, or SAM.

In this study, RSNA is also used to unravel OPPP for IEEE 14,30,57,118 and New England 39 bus systems based on a minimal tree span. Tables 1–5 documents the RSNA simulation. From Tables 1–5, RSN performed very well between DFS, GTP, and SAM algorithms. It is a reliable algorithm that will always return the same outcome for a given method within an appropriate timeframe.RSNA implemented here uses the symmetric reverse Cuthill-McKee permutation to reverse the adjacency matrix in the first position. Only attempts to obtain optimal placements by removing pure transit vertexes from those placements have alternative patterns, as depicted in Figure 12. The authors indicated in [61] that only 31 PMUs are needed for the IEEE 118 bus system using the RSNA algorithm. However, the author did not achieve such a successful placement through RSNA. On the other hand,MBBA provides the best performance for IEEE 118 test systems (28 OPPP locations) at a reasonable time given the merging approach.

The initial BBA was developed for a hypothetical distinct ILP variable problem to find a globally optimal solution. The initial BBA offers global optimality, but just one solution [72].OPPP in MINLP is a Boolean convex problem defined by the proposed procedure. Based on a novel MBBA algorithm,minlpBB clarifies the optimization process, as discussed in Section 3.5. The MBBA has two levels. If the inherent tree network grows, DFS selects the successful candidate to be a vertex at a higher depth in the tree.

When developing the enumeration tree, a potential integer solution is calculated. The second stage accelerates the tree, shifting search order from DFS to BFS. LP relaxations are explained before the OPP problem is discovered[70]. Simplex methods investigate the vertexes in theenumeration tree. Whenever the enumerative approach recapitulates, the minlpBB solver is called a distinct starting point to define the number of separate ideal solution sets.This is an essential advantage for the other ILP routines to validate alternate solutions. The BBA considers a non-unique global minimum starting point, while the user-defined duality gap 0 is reached [63].

TABLE 2 OPPP solution for 30-bus system using DFS, GTP, SAM, RSNA, and MBBA

TABLE 3 OPPP solution for 39-bus system using DFS, GTP, SAM, RSNA, and MBBA

TOMLAB/minlpBB is MATLAB-compatible and used to execute OPPP on five IEEE test systems. Starting with separate original points desired inside vector boundaries [0, 1] the minlpBB routine produces more than one solution set. Each set has the same amount of PMUs.

Tables 1–5 describes the OPPP solution identified by MBBA,which relies on an ILP-based methodology consideringmerging strategy for both test systems.Observability investigation confirms that usable measures are adequate without ambiguity to explain state estimation.The suggested approach offers several OPPP solutions, as seen in Tables 1–5. Tables 1–5 computational time demonstrates that the proposed process preserves the scale of the inherent tree structure as minimal as feasible,findingtheoptimumpointinfinitestages.Thesuggested approach is versatile compared to DFS,GTP,RSNA,and SAM.

TABLE 4 OPPP solution for 57-bus system using DFS, GTP, SAM, RSNA, and MBBA

Finally, as per comparative review, the findings obtained suggest that from a global optimization point of view, the MBBA ensures solution points where DFS, GTP, SAM, and RSNA fail. The topological observability study is checked based on observability parameters to achieve state measurement solvency.Thus,the suggested MBBA solution establishes a global minimum in polynomial time to ensure maximum observability for reliable power monitoring.

5 | CONCLUSION

OPPP,also known as the power-dominating set problem,consists of finding the minimum number of PMUs installed on the vertices such that the graph is completely observed,that is,the network state is known. Polynomial-time algorithms and mathematical techniques are vital approaches to OPPP solution.This study solves the OPPP in a mixed-integer LP method with the binary-valued variables implemented by the novel MBBA,which is more probable than other methods to achieve an optimal or sub-optimal position. The proposed solution took two stages.In stage 1,the pure mixed-integer LP is unravelled by DFS.Once a first integer solution has been discovered,stage 2 requires BFS to find the solution point.Here,the rules and the formulation of the OPPP are introduced in depth based on topological observational analysis. As a result, four types of OPPP algorithms, including DFS, GTP, SAM, and RSNA, are explored to simplify the OPPP scheme. Simulation for IEEE 14-bus,30-bus,57-bus,and 118-bus and New England 39-bus systems using the four algorithms has been carried out. From the simulation, DFS and GTP are seen to be the fastest algorithm of all,but the bad solution is provided for OPPP.SAM is seen to do better than DFS and GTP, but not in a reasonable timeframe. RSNA as a method for the notion of a minimal spanning tree in OPPP works pretty well in the simulation.Also,the simulation shows that the proposed MBBA works better than other approaches and is computationally efficient.MBBA guarantees non-unique globally optimal polynomial-time solutions that prove that OPPP is a P-class problem.Starting from a randomized initial vector, MBBA locates potential solutions

Abbreviations: DFS, depth-first search; GTP, graph-theoretic procedure; MBBA, modified branch-andbound algorithm; OPPP, optimal phasor measurement unit placement problem;PMU, phasor measurement unit; RSNA, recursive security N algorithm; SAM, simulated annealing method.

TABLE 5 OPPP solution for 118-bus system using DFS, GTP, SAM, RSNA, and MBBA with an optimum objective function value for all case studies.Thus,the proposed approach seeks a global minimum in polynomial time to guarantee its observability and to prove the efficacy of its reliable power monitoring scheme.

ORCID

Rohit Babu https://orcid.org/0000-0003-4128-4428

Saurav Raj https://orcid.org/0000-0002-1875-3903

Bishwajit Dey https://orcid.org/0000-0001-9761-9480

Biplab Bhattacharyya https://orcid.org/0000-0003-0348-7283

APPENDIX A

Number and location of a radial bus A

A bus is termed as a radial bus when only one bus is connected to it. Table A1 shows the number of radial buses with their positions in the IEEE 14,30,57,118 and New England 39 bus systems, respectively.

TABLE A1 Radial buses

Number and location of ZIB A

The number of ZIBs with their positions in the IEEE 14, 30,57,118,New England 39 bus systems,respectively,are shown in Table A2.

TABLE A2 ZIBs

Abbreviation: ZIB, zero injection bus.

Connection of ZIBs in IEEE 14 bus A

The connection of ZIB with other buses in the IEEE 14-bus system is shown in Table A3.

TABLE A3 Buses connected with ZIB in IEEE 14-bus system

Connection of ZIBs in IEEE 30 bus A

The connection of ZIB with other buses in the IEEE 30-bus system is shown in Table A4.

TABLE A4 Buses connected with ZIB in IEEE 30-bus system

Connection of ZIBs in New England 39 bus A

The connection of ZIB with other buses in the New England 39-bus system is shown in Table A5.

TABLE A5 Buses connected with ZIB in New England 39-bus system

Connection of ZIBs in IEEE 57 bus A

The connection of ZIB with other buses in the IEEE 57-bus system is shown in Table A6.

TABLE A6 Buses connected with ZIB in IEEE 57-bus system

Connection of ZIBs in IEEE 118 bus A

The connection of the ZIB with other buses in the IEEE 118-bus system is shown in Table A7.

TABLE A7 Buses connected with ZIB in IEEE 118-bus system