Network Coding in Smart Grids
Network Coding in Smart Grids
Network Coding in Smart Grids
net/publication/228450535
CITATIONS READS
17 563
3 authors, including:
Some of the authors of this publication are also working on these related projects:
Crossfire: Cooperation techniques with Network Coding for Mobile Networks View project
All content following this page was uploaded by Daniel E. Lucani on 30 January 2015.
Abstract—Seeking to meet the resilience, efficiency and security mission media characteristics, including signal fading, noise,
challenges of smart grid communications, we present a set of and path loss. Both of these communication strategies rely
strategies that leverage the benefits of network coding. The key on accessible transmission mediums and are thus subject to
idea is for intermediate nodes in the electrical power grid to store
and send linear combinations of data packets they receive or security issues, including potential malicious attacks [8] and
overhear, thus ensuring that critical data can be shared reliably provision of privacy guarantees [9].
with the grid control system even when some of the connections These challenges call for a system architecture that can ex-
break down. The impact of network coding on the reliability
of multicast channels for control messages is also addressed.
ploit the available communication channels and the distributed
Our preliminary analysis of the achievable connectivity with nature of the electrical power grid to the fullest, including the
different topologies and communication technologies (power-line broadcast property of power lines and wireless medium as well
and wireless) indicates that network coding techniques are well as the storage capabilities of individual nodes in the network,
suited for smart grid communications. particularly at medium voltage. In this paper, we make a
I. I NTRODUCTION case for network coding as a key enabler of such a system
architecture. By allowing intermediate nodes in the network
By leveraging advanced communications and control tech- to mix different packets through algebraic operations, network
niques to enhance operational and economic efficiency, electric coding breaks with the ruling store-and-forward principle
distribution systems are experiencing a change in paradigm. As of traditional communication networks [10], [11]. By now,
emphasized in [1], this evolution involves two main visions. the throughput and resilience benefits of network coding in
On the one hand, the goal is to enable advanced metering to wireless broadcast scenarios are well understood [12], leading
collect measurements from individual meters at a base station, to new system designs that have already been implemented and
which in turn sends general information, such as pricing and tested successfully [13]. However, the use of network coding
tariffs, directly to the consumers and their devices. On the in the context of a power-line communication infrastructure to
other hand, the vision is to empower advanced distribution the best of our knowledge has not yet been addressed by the
system management with functionalities [2] that require (i) the scientific community. Other encouraging factors towards inves-
collection of measurements from distributed sensors to enable tigating the potential impact of network coding in smart grid
state estimation for distribution systems and (ii) control mes- architectures include the increased robustness and efficiency
sages from one or several control centers to individually con- that network coding techniques have brought to distributed
trollable devices, e.g. for price-responsive demand, automated storage systems [14] and sensor networks [15].
substations, microgrids, or distributed energy storage [3].
Aiming at a deeper understanding of how network coding,
To support these exchanges of sensor information and
explained in more detail in Section II, can improve smart grid
control messages, several communication technologies have
communications, we make the following contributions:
been proposed [4]. They can be broadly classified in three
categories, namely power line communication (PLC), cable • Design Principles: Based on the requirements of essential
communication (copper or optical fiber), and wireless com- smart grid services, outlined in Section III, we show in
munication (ad-hoc, mesh and cellular architectures). Since how network coding techniques can improve performance
cable communication involves the development of a dedicated at various stages of the overall system.
infrastructure with high capital costs, PLC and wireless com- • Network Coding Strategies: We propose in Section IV
munications are considered by many utility companies to be a basic system architecture and a number of strategies
the most promising alternatives [1]. Nevertheless, practical to leverage the benefits of network coding for data
issues pertaining to these technologies are currently delaying storage, information gathering and multicasting of control
the large-scale deployment of smart meters in distribution messages. Security issues are also briefly addressed.
systems. In particular, PLC techniques may fail to connect • Topology Issues: Using an IEEE standard test case, we
every single household (or substation) of the grid due to the discuss in Section V the impact of wireless communi-
strong attenuation of the communication signal [5]. Further- cations and power-line communications on the topology
more, interference is a salient issue for PLC in distribution of the network and discuss how this affects the expected
grids as the spectrum is unregulated [6], [7]. As for wireless benefits of network coding.
communication, the main challenges are related with trans-
any of the individual destinations. Most importantly, routing
alone is in general not sufficient to achieve this fundamental
limit — intermediate nodes are required to mix the data units
they receive from their neighbors using non-trivial coding
operations. It has also been shown that linear codes are suffi-
cient to achieve the multicast capacity, yielding the algebraic
framework for network coding that has since fueled a strong
surge in network coding research.
Although establishing the information-theoretic limits of
communication networks with multiple unicast or multicast
sessions still seems a distant goal, there is reasonable evidence
that network coding allows for a trade-off of communica-
tion versus computational costs. Furthermore, network coding
brings noticeable benefits in terms of throughput, reliability
and fault tolerance in a variety of relevant networking scenar-
ios beyond multicast. A node that has several packets in its
buffer can choose judiciously how to combine the packets for
Fig. 1. A typical wireless network coding example. the next broadcast transmission. This decision may depend on
several factors including the delay or bandwidth requirements,
the available knowledge about the communication channels,
the network topology, or feedback about the buffer states of
II. N ETWORK C ODING F UNDAMENTALS
neighboring nodes.
The main concept behind network coding is that data Moving from the binary field to larger field sizes, allows the
throughput and network robustness can be considerably im- nodes in the network to perform more sophisticated operations
proved by allowing the intermediate nodes in a network to on the incoming packets. If the network is large or highly
mix different data flows through algebraic combinations of dynamic, computing the network code in a centralized fashion
multiple datagrams. This key idea is illustrated in Fig. 1. To may quickly become infeasible. Fortunately, it is possible to
exchange messages a and b, nodes A and B must route their perform network coding in a fully distributed way, by allowing
packets through node S. Clearly, the traditional scheme shown the nodes to choose their linear coefficients independently and
on top would require four transmissions. However, if S is uniformly at random over all elements of the finite field F .
allowed to perform network coding with simple exclusive-or This approach achieves the multicast capacity of the network
(XOR) operations, as illustrated in the lower diagram, a ⊕ b provided that the field size is sufficiently large. From a more
can be sent in one single broadcast transmission (instead of practical point of view, random linear network coding can
one transmission with b followed by another one with a). be implemented effectively in packet oriented networks by
By combining the received data with the stored message, (1) segmenting the payload into data symbols that can be
A which possesses a can recover b and B can recover a viewed as elements of F , (2) computing the required linear
using b. Consequently, in this scenario, network coding saves combinations on a symbol-by-symbol basis using random
one transmission (thus saving energy) and one time slot coefficients, (3) placing the resulting symbols on the payload
(thus reducing the delay). More sophisticated network coding of the outgoing packet, and (4) updating the header with the
protocols view packets as a collection of symbols from a random coefficients required for decoding.
particular finite field and forward linear combinations of these Upon receiving a sufficient number of packets, each desti-
symbols across the network, thus leveraging basic features of nation node can obtain the coding matrix from the headers of
linear codes such as erasure correction capability and well the incoming packets and recover the original data symbols.
understood encoding and decoding algorithms. Notice that due to the mixing operations, each packet loses
The resulting techniques seem particularly useful for highly its individuality in the sense that the information of a single
volatile networks, such as mobile ad-hoc networks, sensor original packet is spread over multiple instances. Thus, as
networks, and peer-to-peer communications, where stringent long as there are enough degrees of freedom to decode the
constraints due to power restrictions, limited computation original symbols, the destination is not particularly concerned
capabilities or unpredictable user dynamics can be countered with obtaining a specific packet.
by broadcasting encoded packets to multiple nodes simulta-
neously until the destination has enough degrees of freedom III. S MART G RID S ERVICES AND R EQUIREMENTS
to decode and recover the original data, as illustrated by the
example in Fig. 1. A. Services
Using information-theoretic reasoning, it is possible to Smart operation of a distribution system relies on four main
prove that the multicast capacity of a network is equal to communication services corresponding to two applications and
the minimum of the maximum flows between the source and two directions.
On the one hand, commercial functionalities, including functionalities require a very high level of reliability. This
smart metering, involve periodic information exchanges be- also applies to Services B1 and B2, which enable criti-
tween multiple terminals and a single base station with a cal functionalities, even though relying on multiple dis-
typical resolution of 15 minutes [1]. tributed resources for smart grid operation decreases the
• Service A1: Each node in the distribution network has impact of isolated failure of one-to-one communications.
to send measurements (e.g. average demand, maximal An occasional lack of reliability might be compensated
load, minimal load) to the base station. This service by a robust data storage, enabling data exchanges through
corresponds to a many-to-one communication scheme. an alternative path.
• Service A2: The base station provides daily general • Security and privacy: All services under consideration
information, on hourly prices and tariffs for example, to deal with sensitive information and critical control loops,
the smart meters (one-to-many communication). which impose stringent requirements in terms of cyber-
From a long-term perspective, other types of one-to-one com- security and consumer privacy. The communication archi-
munication are expected to arise. In particular, commercial tecture must ensure that unauthorized agents are unable
information provided by the base station to individual meters to access the data collected by grid devices and that
(e.g. record of individual consumption, individual offers and active attacks capable of disrupting critical services and
billing) may involve a significant quantity of information with operations are prevented, detected and mitigated.
high reliability requirements.
IV. N ETWORK C ODING S TRATEGIES FOR S MART G RIDS
On the other hand, technical services related with man-
agement of advanced distribution systems, i.e a close-to-real A basic medium-voltage system architecture for smart grid
time monitoring and control of the distribution grid, requires communication on which network coding protocols and algo-
communicating measurements and settings in a time frame of rithms are expected to run is illustrated in Fig. 2. A server
a few seconds [16]. placed at the substation plays simultaneously the role of base
• Service B1: To enable distribution state estimation, mea- station and control center. It collects the data sent by the
surements (e.g. real and reactive power demand, voltage, secondary substations, which aggregate metering information
current) must be reported from the nodes to the base and sensor readings originating in the low-voltage segments.
station (many-to-one communication). Each of these secondary substations is equipped with a data
• Service B2: Advanced control functionalities require the storage unit (i.e. a cache or buffer) and modem capable of
transmission of alerts and control settings from the base providing communication services using the power line, a
station to the nodes (one-to-many and one-to-one com- wireless link or both kinds of channels. The substation uses
munications). the same communications medium to send control messages
to the secondary substations, which may be directed to a
B. Requirements single substation (unicast) or multiple substations (multicast).
The smart grid services have the following requirements in It is assumed that bidirectional communication over PLC or
terms of communication. wireless channels is possible, such that a feedback link is
• Data rates: the data rates involved in smart grid commu- available for acknowledging the received data packets. More-
nications are unlikely to exceed 10 kbps. For example, over, an adequate medium access protocol (e.g. carrier sense
advanced meter reading by steps of 15 minutes for multiple access / collision avoidance, CSMA/CA) deals with
a distribution network with 200 secondary substations interference and packet collisions in a satisfactory manner. In
connecting 50 households each, corresponds to a data the following, we elaborate on how network coding techniques
flow of the order of a few tens of bits per second to can be used to improve and secure the information flows within
each secondary substation and about 1 kbps to the base this smart grid system.
station. In the context of advanced management func-
tionalities for the same network, the distribution system A. Data Gathering
state estimation may require measurements by steps of To collect the data from each node, a typical substation
10 seconds, leading to information rates of the order of currently relies on a simple master-slave mechanism, in which
1 kbps for a low-voltage (LV) control unit, and several the master (in this case, the substation) requests data from each
kbps for a medium-voltage (MV) control center, which slave (the secondary substation) in a Round Robin fashion.
would deal only with measurements on the MV network. The process begins with the master sending a data-request
• Time criticality: whereas advanced distribution system packet to the intended slave, followed by a transmission of
management has tight delay constraints and requires data from the slave. If the data is received correctly, the master
prompt transmission of information (transmission system proceeds to the next slave. Otherwise, the master repeats the
operation typically considers communication delays of process. The key difference between wireless and PLC in
two seconds [17]), advanced metering functionalities are this straightforward strategy is that the former may need to
not time critical, i.e. they can occasionally suffer a delay. determine the shortest, multi-hop path to communicate to each
• Reliable communication: As they are the link between terminal, whereas the latter often allows for communication in
consumers and energy providers, advanced metering a single hop.
A more elaborate approach would be to form a data aggre- 3) To increase the overall robustness of the system, sec-
gation tree, such that data packets from downstream nodes can ondary substations can share random linear combina-
be merged at intermediate nodes. Since, the electrical power tions of the data among themselves using network coded
grid already provides a tree structure for PLC, it is not difficult flooding mechanisms. The random coding coefficients
to determine which nodes can act as aggregation points of the are send in the packet header.
network. On the other hand, when using wireless communica- 4) Upon receiving a request from the substation, a down-
tions, optimizing the data aggregation tree (e.g. with respect stream node will send one or more packets with linear
to throughput or delay) can become a key challenge. combinations and coding coefficients back to the substa-
In both cases, PLC and wireless communications, we can tion, which is able to recover the data once it receives
leverage the broadcast property of the channel. More specifi- enough degrees of freedom to decode.
cally, since the signals sent by one of the secondary substation By storing random linear combinations of the data, the
are likely to be heard by one or more neighboring substations, data caches in the secondary substation form a more robust
nodes can operate in an opportunistic fashion by storing all distributed storage system, because it is always possible to
the packets they can detect and decode, even when they are recover the data from a sufficiently large set of linear combi-
not the intended receiver. This approach greatly increases the nations even if some of the links fail or some of the substations
robustness and flexibility of the system, because the master are out of reach. As long as the nodes that are still connected
is no longer forced to query every secondary substation or offer enough degrees of freedom, the substation will be able
send request to specific aggregation points, which may be to obtain the pertinent data sets. Moreover, when collecting a
temporarily unavailable due to poor channel conditions, as it random combination of packets from a randomly chosen node,
often happens in PLC and wireless communications. It suffices there is high probability of obtaining a linearly independent
to broadcast a list of data requests identifying the respective packet in each time. In the case of wireless communications,
secondary substations, because any node that has all or part network coding can significantly reduce the required number
of the data in question can then forward it to the base station. of transmissions and the data gathering delay, as has been
The main advantage of network coding is that it can explore extensively documented in prior work. Since the data picked
both the opportunistic use of the broadcast medium and the up by different substations is likely to be correlated, joint
distributed storage of sensor data in an even more sophisti- source-network coding techniques can be used to optimize the
cated way, thus increasing the robustness and efficiency of communication rates.
the overall system. The key operations can be described as
follows: B. Control Traffic
1) Each secondary substation transmits a packet over the If the substation wishes to send short control messages to
channel according to a prescribed schedule, which can a single node in a unicast session, then network coding is
result in periodic transmission or opportunistic channel not likely to be useful even if communication occurs over
accessing (i.e. when the channel quality is above a multiple hops. Likewise if the substation is sending only
certain threshold). one control message to a number of receivers then standard
2) Every node listens to the medium and stores random multicast solutions are sufficient. However, if a larger flow
linear combinations of the packets it receives from other of messages is addressed to multiple receivers, then network
substations. This can be done within a certain time frame coding offers a throughput optimal solution. A straightforward
or generation of packets, so that outdated information approach without network coding would be to flood the
can be discarded. network by having each node broadcast at least once every data
packet it receives. Controlled flooding mechanisms mitigate so
called broadcast storms by adding rules and restrictions to the
forwarding process at each node. Network coded flooding calls
for nodes to broadcast linear combinations of packets, which
greatly reduces the problem of redundant transmissions that is
typical of traditional flooding approaches.
As an alternative to coded flooding, a network routing
algorithm can be used to find a sub-graph of communication
links over which network coding operations can be carried
out. It has been shown that this can be done in polynomial
time, whereas searching for multicast routing trees is an NP-
complete problem (also known as the Steiner Tree problem).
Automated repeat request protocols are often used to enable
reliable communication by means of packet acknowledge-
ments and retransmissions in case of failure. Although this
is known to be ineffective in multicast scenarios with delay
Fig. 2. Basic elements of the system architecture. constraints, the picture changes when network coding is used
at the transmitter. Based on the acknowledgements it receives if there is a direct electrical connection of two nodes. It
from the different destination nodes, the transmitter can send constitutes a subgraph of the distribution network graph.
coded packets that are maximally useful for all receivers based • The wireless network graph relies on the geographical
on the packets they already have stored in their buffers. The position of the nodes to determine the possible wireless
delay benefit comes from the fact that the transmitter can serve links. Its topology is likely to be different from the under-
the retransmission needs of multiple receivers at the same time, lying electrical grid topology. In particular, we expect it
rather than re-sending duplicates of packets that are only useful to have a meshed structure, whereas the grid is designed
for a subset of the receivers. as a tree.
For both graphs, the connectivity Ci,j of every couple of
C. Security Aspects
nodes (i, j) ∈ {0, . . . , N }2 is considered 1 if the electrical
Network coding offers a number of security properties that (PLC) or geographical (wireless) distance d(i, j) between the
can be used to help avert cyber-attacks on the smart grid nodes determines is lower than a transmission range r.
communication infrastructure. Some of the most devastating
network attacks are caused by active attackers inside the !
network capable of injecting bogus traffic. The main difference 1 if d(i, j) ≤ r
Ci,j = (1)
to the vulnerabilities of standard routing protocols comes from 0 if d(i, j) > r
the fact that network coding mixes packets along the network
The described methodology was carried out on the IEEE 123
through algebraic operations. Therefore, the errors of a single
node test feeder represented in Fig. 3(a), which is described
corrupted packet can propagate among an entire generation
in [20] as a 4.16 kV network with N = 123 nodes. We have
and inhibit the decoders from recovering the correct source
located the base station at bus 149, close to the HV/MV sub-
information [18]. Nevertheless, there is more than one way
station. The length of the power lines and cables is provided
to face this threat: (a) legitimate nodes can add redundancy to
in [20]. The feeder has four voltage regulators, which are
their information flows and reduce the damage of active attacks
modeled as electric cables whose lengths are proportional to
by means of network error correction; (b) hash functions can
the regulators’ impedance (i.e. 0.8, 0.16, 0.16, and 0.32 km
be used to detect bogus packets efficiently, so that legitimate
for regulator 149-150, 9-14, 25-26, and 67-160, respectively).
nodes can be alerted and units controlled by active attackers
In addition, every switch is modeled as a 30 meter long
can be isolated from the network. With respect to consumer
power line. The geographical distances between the nodes are
privacy, it has been shown that there exist linear network codes
inferred from Fig. 3(a), with a scaling factor such that the
that are information-theoretically secure against eavesdroppers
distance between bus 149 and bus 114 is equal to 2.1 km.
with partial access to the available links. A stronger threat by
which the eavesdropper has access to all of the traffic can For illustrative purpose, Fig. 3(b) and 3(c) depict the con-
be dealt with efficiently by exploiting the properties of linear nectivity of the test system with a transmission range of 500
network coding in combination with classical cryptography. meters. In addition, Fig. 4 depicts the minimal, average, and
The main idea is to encrypt only the linear coefficients and maximal nodes’ degree of the PLC and wireless communi-
not the payload [19]. cation graphs as a function of the transmission range. It can
be observed that, at a given transmission range, the level of
V. T OPOLOGY I SSUES connectivity is higher with wireless communication, which
Since network topology is well known to have a significant involves intrinsically shorter distances than PLC. Those figures
impact on the performance benefits of network coding, we should however be compared with care, as it might be more
provide a preliminary case study covering both PLC and difficult to reach a transmission range of several hundreds of
wireless links in the context of a medium voltage distribution meters with wireless communications than with PLC.
system. After describing the basic network models for both Clearly, in both cases we get highly clustered networks in
communication technologies and the chosen test system, we which the broadcast property can be fully exploited by network
analyze the node degree and discuss its implications for the coding. This becomes even more evident, when we analyze
use of network coding. Based on the available information of how the node degree (minimum, average and maximum) varies
the electrical grid, including the geographical position of the as a function of the transmission range both for PLC and
terminals and the length of the cables connecting them, it is wireless communications (see Fig. 4). For reasonable values
possible to obtain two different communication graphs, one of the range, most nodes will be able to hear the transmissions
for PLC and one for wireless communications. The method- of and send coded packets to five or more neighbors.
ology described below delivers a coarse approximation of the VI. C ONCLUSIONS
physical system, which incorporates enough of the limitations This paper presents network coding as an alternative com-
of the two chosen technologies to allow for some conclusions munication strategy for smart grids. It describes how network
to be drawn with respect to the suitability of network coding coding can be applied to PLC and wireless communication
under the resulting topologies: networks and emphasizes that the performance that can be
• The power-line communication graph is determined from achieved with this technique depends on the topology of the
the electrical grid topology as a PLC link can only exist communication network. A case study on the IEEE 123 node
(a) (b) (c)
Fig. 3. Electrical graph of the IEEE 123 node test feeder (a), connectivity graph with PLC (b) and wireless communications (c), with transmission range of
r = 500m.