An electric power supply is the backbone of development in advanced as well as in developing economies. An integral part of ensuring a secure power supply system is a power communication system. Due to the high and sustained performance requirements of power communication systems, electric companies prefer to construct their own communication networks privately rather than relying solely on a public communication system. The focus of this paper is on the optimal topological design of a power communication network. Based on advanced optimization models in public communication networks, and taking into account the specific Quality of Service, as demanded by various applications, such as protection, SCADA, voice, etc., an optimization model (PC/ISO) has been developed. The PC/ISO requires tedious numerical processing. Hence, a Genetic Algorithm (GA) is proposed to solve the optimization problem. In order to demonstrate the application of the proposed model for a power system communication network design and in order to evaluate GA solver results, a case study on designing the optimal communication network topology of one of the Iranian Regional Electric Companies has been conducted. The results suggest that the PC/ISO model and its GA solver are entirely viable and offer a simple, accurate, and cost effective solution.
Smart grids ; Communication infrastructures ; Optimal design ; Quality of service ; Genetic algorithms
An electric power supply is the backbone of development in advanced as well as in developing economies. A power system supply may become vulnerable in the face of system abnormalities, such as equipment failure, disturbances, faults, and human operation errors. Therefore, keeping the power supply stable and reliable is a critical issue for power system design. A power communication/information system has a central and vital role in continuous and reliable operation of power systems  ,  ,  ,  ,  and  . The future growth of the power industry will be towards the establishing of smart grids. The definition of DOE for a SG grid is shown in Figure 1  . The acronyms are explained in Table 1 .
Smart grid definition.
|AMI||Advanced Metering Infrastructure|
|ATM||Asynchronous Transfer Mode|
|BPL||Broadband Power Line|
|CFA||Capacity and Flow Assignment|
|CRIEPI||Central Research Institute of Electric Power Industry|
|DMS||Distribution Management System|
|DOE||Department of Energy (USA)|
|DPLC||Digital Power Line Carrier|
|EMS||Energy Management System|
|HAN||Home Area Network|
|MIP||Mixed Integer Programming|
|MPLS||Multi Protocol Label Switching|
|MST||Minimum Spanning Tree|
|NAN||Neighborhood Area Network|
|NP-hard||Nondeterministic Polynomial-time hard problem|
|ONDP||Optimal Network Design Problem|
|OPGW||Optical fiber Power Ground Wire|
|OSI||Open System Interconnection|
|PC/IS||Power communication/Information System|
|PC/ISO||Power Communication/Information System Optimization|
|PLC||Power Line Carrier|
|PMU||Phasor Measurement Units|
|QoS||Quality of Service|
|RCC||Regional Control Center|
|SCADA||Supervisory Control And Data Acquisition system|
|TNLLP||Transit Nodes and Links Localization Problem|
|VPN||Virtual Private Networks|
|WAN||Wide Area Network|
|WAMS||Wide Area Measurement Systems|
|YREC||Yazd Regional Electric Company|
The bottom layer is a physical energy infrastructure that distributes energy. A communication infrastructure is defined on the top of the physical energy infrastructure to the entire supply chain. Computing/information technology is above the communication infrastructure for timely decision making. SG applications are on the top to create electrical system/societal values. Security is in another dimension and covers all layers. Generally, SG is a data communications network integrated with the electrical grid that collects and analyzes data captured in near-real-time about power transmission, distribution, and consumption  ,  ,  and  . However, unlike the maturity of the power engineering discipline, power communication system design and its reliability and security aspects are still at a primitive stage, and there are many research challenges in this field  ,  ,  ,  and  .
Transmission of teleprotection signals between adjacent substations, centralized control of important power plants and substations, operational telephony, and few and limited administrative services (administrative telephony, file transfer and so on), have been the main conventional communication and information requirements of power utilities during past years. For technical and regulatory reasons, operational and administrative services have been traditionally regarded as separate, and often have been implemented on dedicated networks. These networks are generally based on old and low capacity communication technologies. Recently, there has been a transition towards switching to new and public communication technologies in power systems  and  .
The new trends in power communication systems in applications from SCADA, EMS, DMS, to SA, DA and advanced teleprotection are becoming critical to the proper operation of power systems and in maintaining system reliability and stability  ,  ,  and  .
Expanding network services, such as real time wide area measurement, monitoring and controlling systems, having embedded intelligent sensors and control devices for high voltage equipment, increasing administrative data communication due to deregulation and restructuring of the power system, and the growing of distribution generation systems are all driving the need for application of more qualitative, quantitative, and integrated information and communication systems in the electric power environment. Implementation of such applications requires a reliable, broadband, fast, digital, integrated, and standard based power communication/information system  ,  ,  ,  and  .
The quality of service requirements (reliability, delay performance, and integrity of data) of PC/IS is generally higher than that of public communication and information systems  .
Advances in information and communication technologies provide an opportunity for upgrading traditional power communication facilities into a modern high speed, pervasive and integrated digital communication/information networks. Transmission medias, such as OPGW and new DPLC systems, packet switching networks, and networking protocols, such as IP and MPLS, are among the most promising technologies in this regard  ,  ,  ,  ,  and  .
The dominant concept in advanced PC/IS design is internetworking. Advanced models for internetworking are based on designing the network layers  ,  ,  and  . Figure 2 shows a modern internetworking model for PC/IS. It consists of three basic levels: core, edge, and access levels. Each level provides an individually defined and specific functionality  ,  ,  and  . The core level switches packets as fast as possible with a minimum of data manipulation. The edge level generally is the boundary between the core and access levels and implements the majority of packet manipulations. The access level is the point at which end users connect with the network.
Advanced internetworking architecture for power communication systems.
General characteristics of network’s layers are:
About one decade ago, it was believed that an optimized approach to internetworking was the use of the IP protocol for the service provision at access level and ATM technology for the high-speed switching and QoS provision at core level  . Trends show that the use of ATM technology is declining, although new approaches and applications for this technology have been emerged during recent years  . The integration of both technologies is possible by several approaches; between them, MPLS has better characteristics than other approaches for PC/IS  and  .
Communication design problems are divided into static and dynamic problems. Topological design of communication networks (designing the topology and allocating capacities for links and nodes in such a way as to carry the volume of data that is needed with the desired performance (delay, loss, reliability)) is a static problem. The effects of the topology design of a communication network are long-term. In contrast to static problems, there are some dynamic and adaptive problems that need real time solutions. The examples are dynamic routing, call admission control and priority control or buffer management  . The focus of this paper is on the static design of a power communication network.
Design of communication networks should be optimal. It is obvious that in optimal design, dimensioning must be economical and, simultaneously, meet QoS requirements. Therefore, the optimal topological design of a power communication network is inherently a multi-objective optimization problem.
The optimal topological design of communication networks is a NP-hard combinatorial optimization problem  . Because of the complexity of the problem, mathematical programming is not a preferred solution, especially for medium to large size networks. Heuristic algorithm population based methods, such as genetic algorithms, have shown themselves to be good candidates for solving such problems  ,  ,  ,  ,  ,  ,  ,  ,  ,  and  . It should be noted that these methods do not give an optimal solution but a near optimal is what, at best, can be expected.
Internetworking architecture for the power communication system described above has led towards using and developing Transit Nodes and Links Localization Problems (TNLLP) as an advanced optimal network design problem model for topology optimization of communication networks, based on layered internetworked architecture  . The TNLLP problem has applications in MPLS networks design. Optimization in TNLLP is based on cost, and QoS requirements are not seen in its formulation. The TNLLP solution is based on mathematical programming, which is very complex and time consuming, especially for large size problems.
Power communication/information system design and optimization is a multidisciplinary problem. Many aspects of power system operation and control, communication technologies and protocols, and also operational research and artificial intelligence should be integrated in order to study, formulate and solve the problem.
In this work, optimal topological design of a power communication network is studied. Based on new concepts in design internetworking and layered architecture, employing TNLLP as an advanced optimization model in public communication networks and taking into account the specific QoS as demanded by various applications, such as protection, SCADA, voice, etc., an optimization model (PC/ISO) has been developed. The PC/ISO requires tedious numerical processing. Hence, a Genetic Algorithm (GA) is proposed to solve the optimization problem.
The rest of this paper is organized as follows: In Section 2 , the literature review is presented. In Section 3 , the formulation of the proposed model is laid down. The design of the GA solver is discussed in Section 4 and Section 5 is devoted to a case study to demonstrate the proposed approach. A follow up discussion on the GA solver is included in Section 6 , and finally, the paper is concluded in Section 7 .
We present a literature review in 2 subsections regarding communication network optimal topological design, and power communication network design.
A network can be modeled as an undirected graph , having node set and link set  . Communication network problems are classified into static and dynamic problems, the first category deals with the design of the topology, capacity, and static flow of traffic  and  , while the second deals with adaptive network design, such as dynamic routing, call admission control, and priority control or buffer management of the network  . The static network design problem is to synthesize a network topology that will satisfy all or some of the requirements, such as “minimize cost”, “maximize flow”, “multi-commodity flow”, “efficient routing”, “sufficient redundancy”, “acceptable delay” and “conservation of flow” [18, Section 3] .
There are different schemes for static network design problems, as below.
In the literature, classical Optimal Network Design Problem (ONDP) has been modeled as a Mixed Integer Programming (MIP) for designing the links of a network with fixed nodes. In the formulation of this problem, the objective is to minimize the (linear) cost of link capacities, under constraints of the fixed cost of actually provided links below the given bound  . Another version of classical ONDP has been modeled with total link costs as the objective function  and  . It is shown that classical ONDP is a NP-complete problem  . This problem has been solved by the branch and bound algorithm  and greedy algorithms  for small size problems. For medium to large size problems, meta heuristic algorithms, especially GA, have been used  and  .
One of the main relevant research problems is ONDP with reliability considerations. A common reliability measure in this kind of problem is all-terminal reliability  ,  ,  ,  ,  ,  ,  ,  ,  ,  and  , although other measures, such as two  or terminal reliability  and single node or link survivability  , are stated in some papers. The exact calculation of all-terminal network reliability is an NP-hard problem, with computational efforts growing exponentially with the number of nodes and links in the network  . Various forms of network design problem with reliability considerations are formulated. Minimizing link numbers under network diameter, node degree constraints and also single node survivability of a particular network  , maximizing reliability of a network under budget constraint  ,  and  , maximizing network fault tolerance under budget constraint  , minimizing cost under minimum overall reliability constraint  ,  ,  ,  ,  ,  and  , and nonlinear combination of reliability and cost as the objective function under usual ONDP constraints  and  are some of them. A variety of methods for network reliability calculation, such as exact analytical methods  and  , Mont Carlo simulation  ,  ,  ,  ,  ,  ,  and  , or upper and lower bound estimations  ,  ,  and  exist. Meta heuristic methods such as Evolutionary and Genetic Algorithms  ,  ,  ,  ,  ,  ,  ,  and  , Ant Colony  , Tabu Search  and  , Simulated Annealing  and  , and Cross Entropy  , besides some artful and combinational methods  ,  and  , have been used to solve ONDP with reliability considerations. As known in the literature, two-connectivity is one of the most important properties of highly reliable networks  and  , so in some references, this property is used to formulate or develop the algorithms for solving the ONDP problem with reliability considerations  ,  ,  ,  and  .
Another form of ONDP problem is formulated by considering the delay of transmitted signals as a constraint  ,  ,  and  or objective function  and  . Delay in a communication network is related to propagation delay, queuing delay, switching delay, between packet delay, and serial delay  , but queuing delay, which is modeled with queue  ,  and  , is more common in the literature. Different versions of this problem are solved by genetic algorithms  ,  and  , artificial neural network  , artificial intelligence and expert systems  , or other heuristic algorithms  .
The last version of ONDP problems deals with minimizing the average packet loss probability as an objective function under cost and other common constraints. To compute the average packet loss rate (that is related to the buffer capacity of nodes), each node is modeled with queuing system. The problem is solved with a genetic algorithm  .
The common characteristic of ONDP problems is that the architecture is based on only one layer and the location of nodes is not variable. Therefore, the links and their capacities and the static flow of traffic are variables of the optimization problem.
The advanced optimal network design problem is related to the design of a network as a hierarchical system consisting of a minimum of two layers. In this problem, the transit nodes, as main switches in the backbone, should be selected in an optimal manner. Although hierarchical network design is a well known concept in recent years, simultaneous access and backbone design is not very common in the literature  and  . The simultaneous access and backbone network design problem has been formulated as a Transit Node and Link Localization Problem (TNLLP)  and  . Overall costs (links and transit nodes)  ,  and  and/or delay  have been modeled as objective functions in the literature. Branch and Bound algorithm  , Estimation of lower bounds on optimal solutions by the Lagrangean relaxation method  , mixed integer programming  , clustering and local optimization  have been used for small problems. Heuristic methods  and  , genetic algorithms  and  , and simulated annealing  have been developed for medium to large size hierarchical network design problems. A practical use of this modeling is Multi Protocol Label Switching (MPLS) networks  and  .
Electric power utility network (traditional).
With the development of power networks towards intelligent grids, its communication infrastructure should be digital, real-time, resilient, intelligent, scalable, flexible, manageable, extensible and also should be interoperable, secure, future proof and cost effective  ,  ,  ,  ,  and  . Such a network should connect all of the actors in the power system consisting of the bulk generation sector, transmission sector, distribution sector, control centers, distributed generators, network operators and also customers as an active part of the power system  ,  and  . In other words, new services, requirements and technologies, in addition to optimization objectives, lead power system communication toward a reliable, dedicated, integrated, distributed, broadband, hierarchical, and mesh type network  ,  ,  ,  ,  and  . The transmission from the old to the new architecture of power communication systems is not going to happen overnight, but will have to be phased in over many years  . At the present time, there is no existing standardized communication infrastructure which has been widely accepted and used to transform the current electrical power grid into a smart grid. So, defining the services, requirements and architecture of the communication/information infrastructure of the power system, besides proper and optimal design techniques for such a network, are live research subjects in this field  ,  ,  and  .
Application of narrowband packet switching networks, based on the X25 protocol, for telecontrol systems, was one of the first steps in this regard  and  . The next step was application of the best effort Internet Protocol (IP) in power communication systems  ,  ,  ,  ,  ,  and  , although other versions of the IP solution with guaranteed QoS have been developed  . Parallel to these efforts, future concepts of utility telecommunication networks based on broadband integrated service digital networks with ATM technology were designed by Criepi in Japan  and  . The idea was accepted and followed by many researchers in that field until some years ago  ,  ,  ,  and  . As it seemed that IP and ATM technologies should coexist in power system communication networks, MPLS technology, which could integrate both of them, was introduced as a promising technology for power communication systems (Figure 4 )  ,  and  .
Configuration of MPLS network.
It is shown that quality of service guarantee and logically segregated communication services can be obtained in the MPLS network by traffic engineering and implementing Virtual Private Networks (VPN)  . At the present time, IP and MPLS with guaranteed QoS are most important networking protocols for power system communication  and  .
Different communication transmission media, such as Optical fiber Power Ground Wire (OPGW)  ,  ,  ,  ,  and  , Digital Power Line Carrier (DPLC) and Broadband Power Line (BPL)  ,  ,  ,  ,  ,  and  , wireless communication  ,  ,  and  and satellite communication  ,  and  may be used in power communication systems, but OPGW and DPLC are more preferable. DPLC and OPGW are the two communication media owned by the power industry, therefore, their operational costs are low, the speed of their repair and maintenance is high, and they do not need any permission and regulatory license to be used. In addition, the use of these two proprietary systems for power communication is usual in related literature  .
Although the characteristics and concept of future power communication and information systems has been described in literature frequently  ,  ,  ,  ,  and  , there are a few references about detail, quantitative, and optimal design of such networks. In addition, numerous literature is related to distribution communication  and also customer side communications (such as AMI)  , which are not at the central point of our study.
Shahraeini et al.  designed a power Communication Infrastructure (CI) for power system control purposes. They compared communication infrastructures for centralized and decentralized control strategies in power grids. Their design is based on finding the Minimum Spanning Tree (MST) as a communication backbone for both centralized and decentralized strategies. They investigated their design in the IEEE 118-bus test network and compared major critical parameters of these two backbone networks, including latency, reliability, and cost. Their results show that, although communication infrastructure investments are almost the same in both cases, the decentralizing strategy is better regarding the latency and reliability of CI.
In recent research, Sharaeini et al.  studied meter placement and its required communication infrastructure for a state estimation program in a Wide Area Measurement System (WAMS). The mentioned two planning problems are jointly formulated and optimized by a single GA model and solver. Their results show that their co-optimization process outperforms the techniques optimizing each section independently.
Saputro et al.  focused on routing issues in the SG communications infrastructure, which consists of different network layers and components, such as Home Area Networks (HANs), Neighborhood Area Networks (NANs) and Wide Area Networks (WANs). They have provided a survey of the existing routing research and analyze the advantages and disadvantages of the proposed protocols with respect to different application areas.
Xiaorong et al.  studied the conceptual architecture of a WAMS communication network, according to the seven layer model of the Open Systems Interconnection (OSI). They have explored the media of a WAMS communication network, network communication protocol and network technology, but they have not specified WAMS’s network topology in their work.
There are two layers in the Transit Nodes and Links Localization Problem (TNLLP), access and backbone layers, whose network topologies are optimized simultaneously.
The TNLLP model is characterized as follows: 
These objectives should be met with minimal cost.
Total network cost is composed of:
In TNLLP, the set of network nodes is divided into two disjoint subsets: the subset of access nodes and the subset of transit nodes. It is assumed that the demands are generated only by the access nodes and that the access nodes cannot transit demand flows. The access nodes can only serve as the end nodes of the network paths and there are no links between them. The installation costs are assigned only to transit nodes, as access nodes are located in advance.
Considering the distribution and transmission substations, generation stations, different control centers, customers, offices, branches, and other utilities as traffic generators or fixed access points to the communication/information infrastructure, we can choose proper locations for transit nodes and links (core network) similar to the TNLLP model. However, there are some special characteristics needed by PC/IS networks that are not considered in the TNLLP model.
PC/IS has a stringent quality of service requirements. Reliability, delay performance and data loss ratio are the most important parameters for this network.
In general, the reliability of connection between two nodes with degree of connectivity ( possible routes between them) and equal reliability for nodes and links is  :
OPGW and DPLC, as two proprietary communication media for power utilities, are considering in the design of PC/IS networks. We consider the reliability of DPLC links as 0.99, the reliability of OPGW links as 0.9999 and the reliability of all of nodes as 1. It can be shown that the reliability requirements of the distribution (access) network (above 0.95) will be met by using each DPLC or OPGW link in a hierarchy type configuration (in the worst case for 3 DPLC links in a direct path ( ), reliability will be 0.97). Providing higher reliability required by the transmission (core) network (above 0.999) is possible by using mesh configuration (minimum 2 degrees of connectivity) and high or medium reliability communication technologies, such as OPGW or DPLC links in the transit network (in the worse case for 3 DPLC links in each one of two disjoint paths ( ), the reliability will be 0.999)  .
Delay performance is another QoS factor that must be considered in the model. With this assumption that queuing delay is the main source of delay in mesh networks  , the model is used for trunk queuing delays. Regarding symbols used in the PC/ISO model (described in the following), the delay expression becomes:
On the other hand, very strict requirements on packet losses are needed for control applications in power systems. Packet losses mostly occur because of the finite buffer capacity of packet switching networks. To compute the average loss rate at each switch, each node is modeled with the queuing system to account for packet losses. Regarding previous research  , the total number of packet losses is estimated as a function of the link flow and the capacity of buffers and links. Using symbols used in PC/ISO problem formulation, the closed form of packet loss will be:
In order to consider the above QoS parameters in the topological design of power communication networks, we have developed the TNLLP model as follows:
PC/ISO (Power communication/information system optimization problem)
Candidate locations for transit (core) nodes.
Fixed set of access node locations that concentrate end user traffic.
The set of candidate links that can be used in networks consists of two sets; (transit links) and (access links).
The index set of all traffic demands.
The set of candidate routes to realize flows of demand .
probability in the network,
if link belongs to path of demand , 0 otherwise,
(for link capacity),
(for buffer capacity),
if node is incident with link , 0 otherwise,
(core) node .
to 1 if route is selected to support demand (binary variable),
if link is installed, 0 otherwise. Links can be established between core (switch) nodes or between access nodes and core nodes (binary variable),
if core node is installed, 0 otherwise (binary variable),
capacity of link (non-negative integer variable),
of link (non-negative integer variable),
flow of link (non-negative integer variable).
Eq. (3) represents the objective function as a multi objective, goal attainment model. It shows the desire to reach the stated goals (budget, delay and loss performance) as in Eqs. , and and in a coordinated manner. It is important to mention that we want to minimize the upper deviation from the goals. This implies that the lower amount for cost, delay and loss, in comparison with ideal amounts, are completely preferable. Eqs. , and reflect this concept. In Eq. (4) , the total cost consists of installing transit (core) node cost , fixed cost of installing link and variable costs of installing link , that are dependent on capacity and buffer capacity of link . In Eq. (5) , average delay is shown by , which must be close to ideal average delay ( ) in network; is a constant for our problem. Since there are multi commodity, multi requirements for different services in PC/IS, can be calculated by the weighted average of the delay requirements of different services. The weights are proportional to the traffic volume of each application service. Eq. (6) shows the deviation of average loss (probability of data loss) in the network. is a constant for the PC/ISO problem and can be calculated in the same way as ideal average delay. Eq. (10) represents the link utilization that is applied to the loss equation, Eq. (11) shows link flow, Eq. (12) says that link utilization must be smaller than 1, Eq. (13) restricts the capacity assignment to the maximum or upper bound capacity of each link, and Eq. (14) restricts the number of routes for carrying each demand traffic to one. Eq. (15) guarantees that before installing each link, , its incident node, , is installed. Eq. (16) implies that before selecting route for carrying the traffic demands of , all links, , in that route must be installed. Eq. (17) provides the necessary condition for the -connectivity of installed transit nodes, , because of reliability requirements. (Providing enough conditions for -connectivity needs further inspection of the designed topology, and is provided by complementary software tools, after designing the initial topology.)
As discussed before, network topology optimization problems are NP-hard. Neither classical mathematics solutions nor local search heuristic algorithms can solve this kind of problem completely, especially for medium or large size problems.
A generic solution for small, medium and large size problems is the evolutionary algorithm, especially genetic algorithms. In this research, a multi objective GA implementation of the PC/ISO problem is developed as follows.
The genetic algorithm, introduced in 1970 by John Holland et al., is inspired by the biological evolution of a species. It is a general purpose, population based search method. GA is capable of finding the global optima of a problem during an iterative process. Inherently discrete in nature, GA can handle both discrete and continuous variables, nonlinear objective functions, and constrained optimization problems. GA can be used for multi-objective optimization. The GA logic is based on the “survival of fitness”. The chromosomes in GA represent design solutions. There are three basic operators in Gas: “selection”, “crossover” and “mutation“. These operators cause chromosomes to evolve during different generations towards the global optima of the problem  . The “crossover” and “mutation” operators, besides the “inversion” operator  , are very powerful exploration and exploitation techniques that are used in GA. Regarding the above mentioned characteristics, GAs have the ability to encounter highly nonlinear, mixed integer optimization problems that are typical of complex engineering systems  . GAs are very popular in academia and in the industry and have been applied successfully for a broad range of problems such as communication network design problems.
The PC/ISO GA solver package consists of 5 main Matlab m. files: loop01.m, ga01.m, check 01.m, shortest.m and netdata.m., which are schematically shown in Figure 5 and described below.
PC/ISO GA solver main modules and their relation.
Ga 01: Ga01 is the heart of the package. Application of this routine is to find the best topology for power communication networks using GA. The best transit nodes and best transit links are selected by this routine. This program uses a multi fitness function. The first (higher priority) function is the delay deviation function. The second (lower priority) fitness function is the cost function. In this implementation of the PC/ISO GA solver, an infinite capacity for link buffers is considered, so the loss due to buffer capacity will be zero and the third objective will be met in any case. The data that are used by this function are loaded from a data file named “netdata”.
Check 01: This function checks whether or not a chromosome (chorom) (each chromosome consists of on–off states of core nodes and core links) can describe an acceptable topology for a power communication network, and, if it can, calculates the fitness functions of this chromosome. Check01 is called by the Ga0l function and returns the result to this function.
Netdata: The data file consists of all information needed to solve the optimal network design problem. This function is run by Ga01.
Shortest : This function solves the shortest route problem with a dynamic programming algorithm. The Input of this function is the distance matrix between points. The output of this function is the shortest route matrix. The shortest function is called by check01 and returns its result to that function.
Loop 01: Loop01 is a function that repeats the Ga01 program for finding the global optimal topology.
Logic of PC/ISO GA solver:
In optimization methods using genetic algorithms, it is necessary to code the variables with chromosomes. We considered the binary variable of a transit nodes situation (installed or not) and a transit links (links between transit nodes) situation (installed or not) as binary elements (genes) of chromosomes. We could code all the transit and access links in the chromosome, but the problem would be very complicated. Therefore, we choose the access links based on the shortest path between them and the installed transit nodes.
In a similar way, we could bring the capacity of the installed links to the chromosome definition, but because of extreme complexity, we preferred to assign capacity based on aggregation of traffic flow on the shortest paths.
In the GA solver, some chromosomes are initially generated randomly (initial population) and after selection of the best of them, crossover, mutation and inversion operators are activated on the population to produce new generations. It must be mentioned that the crossover and mutation are standard operators in every GA solver, but the inversion operator is introduced in only some of the literature  .
The selection process of chromosomes is based on sorting the current population. In this research, the sorting is based on hierarchical analysis of cost and delay (deviation of delay from ideal amount), with a higher priority for delay and a lower priority for cost.
After sorting the chromosomes, each one gets a probability. Giving the probabilities is based on a0 parameter ( ). The formulation is based on geometric distribution as , where is the rank of the sorted chromosome and define the chance of a chromosome to be chosen for the next generation. The final step in the selection process of chromosomes is the use of a roulette wheel. The new population will go for evaluation and other calculations of the program.
To show the application of the PC/ISO model for a power system, and to evaluate the capabilities of this modeling method in answering power communication system problems, a case study on designing the topology of the Yazd Regional Electric Company (YREC) private communication network was conducted. YREC is a relatively small electrical company in the central part of Iran. The choice of this regional company is due to the size of its power network, the diversity of communication system requirements and the mesh configuration of the power system, which make it suitable for such a case study. In addition, the administrative telephony communication network design of this region was studied before  , which could be helpful regarding data collection.
The YREC single line diagram is shown in Figure 6 . To have a reasonable network size for such a case study, we have concentrated the communication requirements of the YREC power system on the power network configuration of a 63 kV level and up. In order to simplify data collection and without putting any restrictions in applying the model for other traffic requirements, in this implementation, only traditional and operational power communication requirements are considered.
YREC single line diagram.
The YREC Regional Control Center (RCC) is located on the Yazd 2 substation and the central administrative building of YREC is adjacent to the university substation. According to standards  and  and considering traditional traffic requirements, the total communication needs of the YREC power system, consisting of speech (digital compressed speech), operational data, digital teleprotection and video surveillance, are summarized in Table 2 . It is obvious that using new and advanced data gathering schemes and technologies in power systems (for example, PMU) can increase the traffic requirements of the network, but do not make any restrictions in the application of the proposed model.
|Substations (access nodes)||W1||W2||W3||W4||W5||W6||W7||W8||W9||W10||W11||W12||W13||W14||W15||W16||W17||W18||W19||W20|
Three important qualities of service parameters are “reliability”, “delay” and “loss performance” in a communication system. By designing the communication system in a minimum two layers (access and core), using OPGW or DPLC and also mesh configuration in the core level, and using DPLC in the access level with hierarchical topology, it is shown that the reliability requirements could be met. The other two parameters (loss and delay performance) are considered in the formulation. According to standards and YREC requirements of Table 2 , traffic types, percentages, and performance requirements (regarding delay and integrity (probability of loss) classes) are mentioned in Table 3 . According to Table 3 , the weighted average delay performance requirement would be 877 ms, and the weighted average loss performance requirement would be 2∗10−10 , which are considered ideal design points for our problem.
|Traffic type||Percentage (%)||Quality of service requirements|
|Delay (ms)||Integrity (loss probability)|
According to the advantages of using private communication media for electric companies, such as mentioned before, we have considered only two main and specialized communication media (OPGW and DPLC) in this implementation of the PC/ISO model. The detailed characteristics are tabulated in Table 4 . It is rather obvious that these communication links must be built over existing power lines.
|Communication system||System capacity||Marginal cost (depended on capacity)a||Variable cost (depend on distance)a||Considerations|
|Power line carrier||32 kbit/s||20,000$||–||The outdoor equipment costs are neglected|
|Fiber optic (OPGW)||2 Mbit/s||1000$||7000$/km||The repeater costs are neglected|
a. Costs are only approximated for this case study.
For the optimal design of YREC power communication network topology with previously mentioned characteristics (single line diagram, communication requirements, available communication media, quality of service requirements and so on), we use the PC/ISO model described and formulated in Section 3 of this paper.
A practical point in PC/ISO model implementation of the YREC network is that we cannot guess the budget needs, so, our first objective is to minimize the total cost of the system. (Not minimize the deviation of the cost from the total budget.)
Therefore, the first objective (cost) is:
The second objective (delay) is:
The constraints 10–17 (mentioned before) must be satisfied for PC/ISO model implementation of the YREC power communication network.
In the YREC optimal network problem, we have 159 binary variables (10 transit node candidates, 33 transit link candidates, and 116 access link candidates). It implies that the solution space consists of 2159 or 7.3∗1047 states. We must add the capacity assignment for each “on” link to this complexity. It is simply seen that for a relatively small power network, the optimal communication network design is a complex or NP-hard problem. Solving these kinds of problems with traditional optimization methods is very tedious, time consuming, and maybe impossible. In the following, we present the results of solving this problem using the genetic algorithm solver that we have developed for this purpose.
The PC/ISO GA solver was applied to the YREC communication network design and two groups of tests have been done on the GA solver. The first group of tests was carried out to tune the parameters of the GA solver (population number, generation number, crossover, mutation, inversion probabilities, and ). As GA is a problem dependent method, these tests are important to be sure about the results of the solver. These tests have been done with constant input data for the problem. The characteristics and best setting parameters of the solver are obtained as shown in Table 5 .
|Chromosome format||Binary string, represent candidate transit nodes and transit links|
|Fitness evaluation method||Sort the population based on (1) Delay (2) cost and then assign their selection probability by using geometric probability function/|
|Crossover type/probability||Single point/|
|Mutation type/probability||Flip bit/|
|Size of population||Pop_size = 30|
|Number of generations||Maxgen = 12|
|Number of different runs||14|
By applying these parameters to the GA solver, The YREC communication network is resulted as shown in Figure 7 .
YREC communication network.
After tuning the parameters, the second group of tests was done. These tests were based on changing the input data and evaluating the results. The trends of the results in the second group of tests complied with our expectations of GA solver behavior.
Verification of results
The node and link optimization network design problem, with more than one objective and based on power system communication lines, has not been formulated and solved before to the best of the authors’ knowledge. Therefore, verification of the model and its results is not possible according to solved and published results.
In addition to the results of different tests that satisfied our expectations from the model behavior, a specific program has been prepared for validation of GA solver results (Check00.m and ga00.m). This specific program is based on only transit node optimization and defines an upper bound for results. The links in this new program are not optimized and are installed everywhere possible, between installed transit nodes. Hence, the possible solution space for this program is definitely small (210 =1024) and so, the results of it are certainly accurate.
To validate our GA solver by this new program, we compared the results obtained by the main GA solver (the result shown in Figure 7 ) with the results of running the new program for the same conditions (traffic, ideal delay, costs…). The results of the new program are equal to $2,700,000 for optimal cost and 0.1411 s for optimal delay. The selected transit nodes are , and . The obtained results of the new solver are an upper bound for the main GA solver and the selected nodes of the new solver are a subset of selected nodes in the main GA solver. Comparisons between the two solvers (Table 6 ) show that the PC/ISO GA solver based on node and link optimization gets completely better results than the new solver based on only node optimization.
|Characteristics and results||Transit nodes and links optimization solver||Transit nodes optimization solver|
|No of genes in chromosome structure||43||10|
|No of transit nodes in optimal solution|
|No of transit links in optimal solution||9||9|
|Optimal delay (ms)||140||141|
The optimal topological design of a power communication network is a multi objective problem and is based on a two layer (transit and access) concept for network architecture.
The model simultaneously selects the set of transit nodes and links, the capacities of transit switches and links, the set of links connecting access nodes to transit nodes and, finally, the primary routes that support network traffic. The criteria used for selecting the preferred design among all design alternatives are: overall network cost, ideal delay performance and ideal loss performance. Reliability is considered in the model by the -connectivity concept.
The communication media and their characteristics may be defined by the user. However, in this implementation, they are DPLC and OPGW systems, as exclusive communication links on possession of the power utilities.
In order to show the application of the PC/ISO model for the power system and to evaluate the PC/ISO GA solver results, a case study on designing the optimal topology of the Yazd Regional Electric Company (YREC) private communication network has been done.
The PC/ISO GA solver takes a single line diagram, traffic needs, and performance requirement data as inputs, and gives the optimal topological design of the power communication network as output. The results of applying the PC/ISO model and its GA solver for designing an optimal power communication network in YREC shows that this model and its solver have a high potential to be presented as a powerful software tool for power communication network design and optimization. Besides accuracy and simplicity, utilities can avoid the extra costs of oversize designs, while they are sure that their quality requirements are met at the end of the design process.
In the future, the results of this paper will be developed by the authors with more precise study of network reliability and resiliency, while providing more compatibility with modern standard communication networks and protocols.
Other related future research subjects are: Modeling and formulating the optimal design of three layer networks regarding buffer capacity in the GA solver, considering propagation and switching delay besides queuing delay, and the redesign of the GA solver without considering any priority between objectives.
The authors would like to thank Professor S.T. Akhavan Niaki for his valuable consultations and comments on this work, Dr. M.R. Arvan for his help in coding the genetic algorithm solver, the Power Technology Research Center of Iran (MATN Co.) for funding this research, and also the honorable reviewers for their valuable comments and suggestions, which provided guidance for improving this paper.