λ-Augmented Tree for Robust Data Collection in Advanced Metering Infrastructure

Abstract

Tree multicast configuration of smart meters (SMs) can maintain the connectivity and meet the latency requirements for the Advanced Metering Infrastructure (AMI). However, such topology is extremely weak as any single failure suffices to break its connectivity. On the other hand, the impact of a SM node failure can be more or less significant: a noncut SM node will have a limited local impact compared to a cut SM node that will break the network connectivity. In this work, we design a highly connected tree with a set of backup links to minimize the weakness of tree topology of SMs. A topology repair scheme is proposed to address the impact of a SM node failure on the connectivity of the augmented tree network. It relies on a loop detection scheme to define the criticality of a SM node and specifically targets cut SM node by selecting backup parent SM to cover its children. Detailed algorithms to create such AMI tree and related theoretical and complexity analysis are provided with insightful simulation results: sufficient redundancy is provided to alleviate data loss at the cost of signaling overhead. It is however observed that biconnected tree provides the best compromise between the two entities.

1. Introduction

Advanced Metering Infrastructure (AMI) is a hierarchically heterogeneous communication infrastructure whose aim is to maintain the interaction between electrical power utility and power consumers. Home Area Network (HAN) is the low level of AMI whereby smart appliances (SA) connect within a short range star communication network with the smart meter (SM) that acts as the smart home gateway.

At the intermediate level, in the neighborhood area network (NAN), smart meters rely on each other to report their power demand to the utility [1]. The NAN is segmented in autonomous NAN Building Blocks (NANBBs) and smart homes connect within a tree network configuration of the SMs rooted at the dedicated router gateway (RG). The various RGs at the intermediate level connect in a full wireless mesh network and merge all the various autonomous NANBBs into an AMI Wireless Network (AWN) centered around the dedicated collector base station (CBS) at the substation (Figure 1).

Figure 1

AMI Wireless Network (AWN).

In a WMN topology every node is connected to every other node in the network (Figure 2), so that a new node can be added to an active communication path to remediate another node or link failure without the need of an external action (self-healing and configuring). It is thus immune against single point of failure. Here, every node not only sends its own signals but also relays information from other nodes (for flooding or routing mechanism) which makes the topology very expensive as there are many redundant connections. Consequently, WMN is difficult to maintain and suffers from bandwidth waste as well as delay and signaling overhead due to aforementioned redundancy [2]. Almost 50% of the gross data rate has to be used for overhead to guarantee links stability and uninterrupted data transmission. In addition, another 50% of the available data rate has to be reserved for the backup path. As such, radios are sending the same data twice. Smart meters (SMs) are sensor-like devices that are limited in storage and computational capability and are not good candidates for mesh network structure compared to the RGs. WMN is thus unlikely to deliver the speed necessary to fulfill the latency requirement of AMI although it can maintain the connectivity as any SM node or link failure does occur [3–5].

Figure 2

Mesh-based NANBB network.

Tree multicast configuration of smart meters is appropriate to maintain a connected network topology and meet the latency requirement for the AMI. It is easy to set up and it is decent in terms of delay, signaling overhead, and bandwidth waste compared to its mesh counterpart. In order to further satisfy the delay constraint of AMI, hop-constrained or shallow trees may be established. However, such network topology is extremely weak as failure of any single node or link could cause the network to partition into separate blocks [2], which may lead to significant loss of data.

This prompts the design of a novel network architecture that merges the advantages of both tree and mesh topology to satisfy the latency requirement while providing a minimum redundancy to ease the connectivity recovery from link failure [6–9] (e.g., Figures 4 and 5). Furthermore, node failure can still have more or less significant impact on such augmented tree connectivity depending on its location: a leaf SM or noncut SM will have a local limited impact compared to a cut SM that will partition the network into disjoint blocks such that some SMs are not able to report to the RG. Such cut SM node is considered of significant criticality. For example, in Figure 9, the network remains connected after any of the leaf smart meters such as $S M_{3}$ or noncut smart meter like $S M_{10}$ fails. However, the loss of any cut smart meter like $S M_{1}$ or $S M_{14}$ disconnects the AMI and prevents all the descendant smart meters from reporting to the utility.

Many existing research works on network link connectivity and reliability have focused on the cellular network backhaul augmentation which in the context of AMI corresponds to the data aggregator unit (i.e., Collection Base Station or CBS) interconnection. Dutta and Kubat in [10] propose the use of self-healing rings for the backbone network. In [11], Charnsripinyo and Tipper use a two-phase approach, one to determine the minimum cost network design to satisfy traffic demand and QoS and the other one to consider a problem of incremental network design for minimum cost network to augment the topology with backup link to the backhaul. On the node failure connectivity, existing research works on sensor networks take advantage of the node mobility to propose topology repair schemes in which nodes react to failure by relocating and isolating the failing node to maintain the network connectivity. In [12], Abbasi et al. rely on the view of a node in its neighborhood to design a recovery scheme that relocates the minimum number of nodes while ensuring conservation of path length between any pair of nodes. In [13, 14], predetermined criteria to involve any node in the connectivity recovery effort are maintained in a table for neighboring one- or two-hop node. All the aforementioned schemes rely on the node mobility. In AMI, SM nodes are not movable.

In this paper, we focus our work on the low level end-user's communication network, the neighborhood area network (NAN) reliability: an algorithm is designed to select a set of backup links to augment the NANBB tree based topology from 1-edge-connected tree to λ-edge-connected tree, where $λ > 1$ (an integer) is a design parameter. A set of disjoint paths will be created between the RG and any SM. The topology is said to be λ-augmented and will sustain the connectivity after as many as $λ - 1$ adjacent links fail [15, 16]. For example, if we set $λ = 2$ , the augmented tree would have a biconnected topology. As a result, there will exist at least two disjoint paths in any cut that separates the RG from any SM nodes as noticeable in Figure 4; likewise, triconnected tree network corresponds to $λ = 3$ such that there are no two adjacent communication links whose disability can break the NANBB as can be seen in Figure 5. This scheme has the advantage of significantly reducing the signaling overhead and the radio bandwidth waste compared to mesh networks. However, our proposed scheme lacks in root redundancy so that any RG's defection will disconnect the corresponding AMI building block. Since RGs are well maintained by utility companies, we assume they are free of failures.

In the AMI, SM nodes are not mobile and cannot relocate as proposed in previous works. To address the impact of a SM node failure on the connectivity of the augmented tree network, a proactive topology repair scheme is proposed. It relies on a loop detection scheme to define the criticality of a SM node and specifically targets the cut SM nodes by selecting a set of backup parents to all the immediate children SM nodes. These links come into action immediately after the cut SM fails such that the AMI network mutates and recovers the connectivity by isolating the failing critical SM node.

The rest of this paper is organized as follows. In Section 2, motivating examples are provided to illustrate the minimum redundancy and showcase the ease of connectivity recovery in biconnected and triconnected topologies from link failure. Section 3 studies the basic case of biconnected tree topology for NANBB. A depth first search based algorithm is proposed to solve the biconnected tree augmentation. Section 4 enumerates major change to the DFS algorithm to accommodate the λ-connected tree algorithm to suit higher level of connectivity. Section 5 presents the topology repair scheme to address the impact of the node failure and connectivity recovery in augmented tree network. In Section 6, a study is proposed to evaluate the complexity of the algorithm in terms of the size of the network and the target connectivity. In Section 7, IEEE 802.11 MAC handshake protocol is employed as basis to simulate and assess the effectiveness of the augmented tree topology in terms of signaling overhead and data loss. Section 8 summarizes the work.

2. Link Failure Connectivity Recovery: Motivating Examples

In this section, we focus on studying two basic augmented NANBB tree based topologies. Specifically we describe and outline the reliability improvement of augmented tree based NANBB for $λ = 2$ (biconnected) and $λ = 3$ (triconnected).

Connectivity is a predominant concept in a communication network; it refers to the network ability to sustain its full operation despite link failure [17]. For a connected NANBB network, its spanning tree is a configuration through which all the SMs are connected with $λ = 1$ (Figure 3).

Figure 3

Tree based NANBB network (degree 3).

Figure 4

Double link failures recovery in a biconnected NANBB.

Figure 5

Triple link failures recovery in a triconnected NANBB.

The goal of this work is to mitigate the weakness of the NANBB spanning tree based communication topology by assigning backup links to thwart against single point of failure and increase its reliability [18]. This may be measured by the probability that the network remains connected despite link failure; that is, any SM somehow remains capable of transmitting its power demand to the RG under link failure, provided that other SMs are operative.

Consider the two augmented tree based NANBBs: biconnected (Figure 4) and triconnected (Figure 5). In the biconnected tree (Figure 4), each SM maintains at least two disjoint paths to the RG. Upon failure of any single communication link (red star), the adjacent backup communication links take over to maintain the connectivity of the corresponding SMs ( $S M_{3}, S M_{12}$ ) to the dedicated RG through the disjoint path (red dotted links): no single link failure can break the connectivity as it is systematically the case for the spanning tree topology. In general, a biconnected tree can recover from any single communication link failure. In addition, it may recover from more than a single nonadjacent links failure. Examples of recovery by redirecting the traffic through backup links are shown for a double nonadjacent links failure (double red stars) in Figure 4.

Figure 5 shows three-failure recovery for $S M_{1}$ , $S M_{4}$ , and $S M_{12}$ in a triconnected NANBB. Here, there exist at least up to three disjoint paths in between any single SM and the root RG so that two adjacent links failures cannot disconnect any SM from the root RG as it is the case in the biconnected NANBB (Figure 4). In triconnected NANBB (Figure 5), $S M_{1}$ , $S M_{4}$ , and $S M_{12}$ remain connected through the third disjoint communication paths (red link) as both other links fail simultaneously. In the context of this paper, the challenge is to find the minimum λ-connected tree based topology that improves the reliability of the NANBB communication network by randomly or deterministically assigning backup parent SM.

3. Link Failure Connectivity Recovery: Biconnected Tree

In this paper, we make the following assumptions: (1) only one-node SM or communication link failure occurs at a time in the network, the rationale being that multiple simultaneous failures are less likely; (2) a SM node would transmit at its maximum power to increase the chance of being in range with multiple neighbors; (3) the wireless nature of the medium prompts considering link cost generally specified in terms of delay, packet loss rate, bit error rate, guaranteed bit rate, and so on. On the other hand, undesirable connectivity augmentation due to RF signal propagation is worth investigating; communication security scheme involving key distribution and management is a good candidate solution [2]: only SM nodes sharing a secret key can communicate such that radio signals from other nodes in range are simply ignored.

3.1. Problem Formulation and Definitions

A NANBB communication network can be represented by a graph $X = G (V, E)$ (Figure 2), where V is the set of smart meters ( ${S M}_{i}$ ) and E is the set of communication links ( $l_{i j} = [{S M}_{i}, {S M}_{j}]$ ) between pair of smart meters. Firstly, depth first search (DFS) algorithm (Section 3.2.1) can be run on the graph $G (V, E)$ to generate a tree $T (V, Γ)$ (Figure 3) that spans all the SMs in the NANBB network.

The router gateway (RG) is the root to which any SM directs its data. Given a smart meter $S M_{i}$ , the path to the root is denoted by $p (R G, {S M}_{i})$ and the connectivity of ${S M}_{i}$ is defined as the maximum number of disjoint paths to the RG [19]. Thus, the connectivity is 1 for a NANBB tree topology since no common internal edge exists between the distinct paths.

The tree based NANBB connection reliability problem can be formulated as identifying the minimum set of links to be considered as candidate backup link to a backup parent SM. In other words, the goal is to find additional backup SM through which each individual SM can rely on for connecting to the tree root RG as its original parent SM is out of reach due to link failure. At the detection of the failure, it could take step to activate the backup link and remain connected [15].

The connectivity augmentation in a NANBB tree network $T (V, Γ)$ can be defined such that, given a function, $λ : V \times V \to N, (R G, {S M}_{i}) \to λ (R G, {S M}_{i})$ ; find the set K of edges in $E - Γ$ such as in $ϵ = Γ + K$ : $ℵ_{p (R G, {S M}_{i})} \geq λ (R G, {S M}_{i})$ , $\forall i$ , where $ℵ_{p (R G, {S M}_{i})}$ is the number of disjoint paths. In the case of uniform requirement where $λ (R G, S M_{i}) = λ$ for all SMs, it simply becomes a problem of λ-edge-connectivity.

Let $N_{T} (S M_{i})$ denote the set of neighbors of $S M_{i}$ in the NANBB tree network $(T)$ . The path $p (S M_{i}, S M_{j})$ between $S M_{i}$ and any $S M_{j} \in N_{T} (S M_{i})$ is simply the edge $l_{i j} = [{S M}_{i}, S M_{j}]$ . The degree of ( $S M_{i}$ ) ${d e g}_{S M_{i}}$ is the size of the neighbor set $N_{T} (S M_{i})$ (i.e., ${d e g}_{{S M}_{i}} = |N_{T} ({S M}_{i})|$ ) [18].

The following definitions for NANBB tree network topology are introduced: (i)

A leaf smart meter denoted as $(l S M)$ has no descendant SMs and $L (l S M)$ denotes the set of $l S M s$ .

(ii)

A cut smart meter $(c S M)$ disconnects the network in as many parts as its degree when deleted.

(iii)

A stem smart meter $(s S M)$ has only $l S M s$ as descendant.

From the motivating example described above (Section 2) the following significant observations are made: (i)

Leaf smart meters $(l S M s)$ are exclusively subject to additional backup parent SM for connectivity augmentation.

(ii)

Connectivity augmentation requires at least ${d e g}_{s S M} - 1$ additional edges per stem smart meter $(s S M)$ .

The following categories [15] describe the set from which a backup SM derives: (i)

Uncle: the set of the backup SMs contains the sibling of the parent SM. The root RG has no brother and, as such, its children SMs have no uncle and thus no backup SM either.

(ii)

Cousin: this set of backup SMs is made of the uncle's children SMs. Here also, the root has no brother. This makes it impossible to the root's children to have backup SM as well.

3.2. NANBB Biconnected Tree Link Augmentation

In this section, we present an algorithm for solving communication link augmentation based on the observation in Section 2 and algorithms in [20]. Prior to that, we describe the depth first search (DFS) algorithm to derive the NANBB tree topology. Breath First Search (BFS) is another search scheme where each node is visited and numbered with access to all of its neighbors at the same time; the neighbors are likewise visited next all together in turn, and so on [21, 22]. In both cases, the root RG is first located where the search starts. They all have similar performance cost in terms of time and space. However, the nodes order produced by the DFS is more appropriate for our scheme in Section 3.2.2 that we survey in [20].

3.2.1. Depth First Search (DFS) Algorithm

The root is chosen and its immediate rightmost child SM is explored; the search progresses recursively until reaching a set goal or hitting the last rightmost SM node. From there, the search backtracks and resumes at the last rightmost descendant SM not completely explored [23]. Here each SM is required to have at most λ children (i.e., ${d e g}_{S M}_{i} = | N_{x} ({S M}_{i}) | ⩽ λ + 1$ (Figure 3) for $λ = 2$ , ${d e g}_{S M_{i}} ⩽ 3$ ).

Data Structures (i)

$l S M$ : leaf SM.

(ii)

$c S M$ : cut SM.

(iii)

$T_{c {S M}_{i}}$ : subtree rooted at $c {S M}_{i}$ .

(iv)

$s S M$ : stem SM.

(v)

$N_{X} ({S M}_{i})$ : neighbor SM set of ${S M}_{i}$ in the graph X [18].

(vi)

$p ({S M}_{i}, {S M}_{i + 1})$ : communication path between two SMs.

(vii)

$ℵ_{p ({S M}_{i}, {S M}_{i + 1})}$ : number of disjoint paths between them.

(viii)

State: a SM is sequentially unvisited, discovered, visited, and finished when the DFS withdraws.

An appropriate description of a DFS for a NANBB network is in terms of the spanning tree of SMs as the search ends. Its mechanism in a NANBB perspective is based on setting and getting the labels of SMs and communication links of the spanning tree.

3.2.2. Algorithm: NANBB Biconnected Tree Network

Here, the problem is to find the smallest set of links which in addition to the NANBB spanning tree communication network makes it biconnected so as no single link failure can disconnect any single SM (Figure 4).

Initially the algorithm calls the NANBB network and identifies its root which in this case is the data aggregator unit RG. The NANBB tree network topology is issued resulting from the DFS (Section 3.2.1). The NANBB network is a simple tree that spans all the SMs. A single communication link failure suffices to break the network connectivity, whereas a single SM failure results in the segmentation of the network in a number equal to its degree, whichever case prevents a set of SMs from communicating with the root RG (Figures 3 and 7).

Consider $q [L (l S M)]$ the partitioning of the set $L (l S M)$ of leaf smart meters ( $l S M s$ ) of the NANBB tree network T

\begin{matrix} q [L (l S M)] \subseteq \{L (c S M_{i}) ∣ \forall l S M_{i} \in L (c S M_{i}), \exists! c S M_{i} \in p (l S M_{i}, l S M_{i + 1}), {d e g}_{c S M_{i}} = 3\} . \end{matrix}

(1)

For example, in the NANBB tree (Figure 3), the set of leaves $L (l S M)$ comprises the SMs, $S M_{15}$ , $S M_{13}$ , $S M_{12}$ , $S M_{11}$ , $S M_{8}$ , $S M_{7}$ , $S M_{4}$ , and $S M_{3}$ with the partition set $q [L (l S M)]$ below. Each partition set $L (l S M)$ can be augmented to become biconnected (i.e., subset $L (c S M_{2}) = {S M_{3}, S M_{4}}$ in Figure 4 is augmented with 3 incident edges: $[S M_{3}, S M_{6}]$ , $[S M_{4}, S M_{7}]$ , and $[S M_{5}, S M_{8}]$ ).

Upon augmentation of the first partition $L (c S M_{2})$ , the network becomes a biconnected component tree where each node is either a SM or a biconnected component (e.g., biconnected subtree $T_{c S M_{1}}$ rooted at $S M_{1}$ in Figure 4). The biconnected component is thereafter contracted into its root $(S M_{1})$ that will be considered a new leaf SM in the next partitioning followed by a new augmentation

\begin{matrix} q [L (l S M)] \subseteq \{L (R G) = \{S M_{15}\}, L (c S M_{14}) = \{S M_{13}\}, L (c S M_{10}) = \{S M_{12}, S M_{11}\}, L (c S M_{6}) = \{S M_{8}, S M_{7}\}, L (c S M_{2}) = \{S M_{4}, S M_{3}\}\} . \end{matrix}

(2)

The recursive process proceeds following a rightmost DFS technique until the entire network reduces to a single SM (i.e., RG).

4. Link Failure Connectivity Recovery: λ-Augmented Tree

In this section, we study the NANBB tree λ-augmentation based on the requirement that the source NANBB network is a full mesh of at least degree λ (i.e., each node including the RG in the NANBB mesh has at least λ disjoint communication paths to any other node) and we enumerate the different changes to enhance Algorithms 1 and 2.

Algorithm 1:DFS (depth first search).

Input: NANBB Mesh Network $G = (V, E)$

Output: NANBB Tree Network $T (V, Γ)$

(1) $Γ = \{\}$

(2) for $({S M}_{i}, l_{i j}) \in G (V, E)$ do

(3) Mark label ${S M}_{i}$ : unvisited;

(4) Mark label $l_{i j}$ : unvisited;

(5) Select RG, DFS's root.

(6) Mark label RG: visited

(7) DFS $(G, R G)$

(8) for ${S M}_{i} \in N_{G}$ (RG) do

(9) Select ${S M}_{i}$ rightmost unvisited descendant

(10) if Get label $({S M}_{i})$ = unvisited then

(11) ${S M}_{i}$ ← opposite $(R G, l_{i r})$

(12) Mark label $(l_{i r})$ : discovered

(13) Add $l_{i r}$ to $Γ_{i}$

(14) Mark label $l_{i r}$ : visited

(15) Mark label ${S M}_{i}$ : visited

(16) Add $l_{i r}$ to Γ

(17) else

(18) Set the label of $(l_{i r})$ as: back-edge.

(19) if $| Γ_{i} | ⩾ \dots 2$ then

(20) DFS $(G, {S M}_{i})$

(21) return $T (V, Γ)$

Algorithm 2:AMI biconnected tree communication network.

Input: NANBB Mesh Network $G = (V, E)$

Output: NANBB Biconnected Tree $H = T (V, ϵ)$

(1) $T (V, Γ) = D F S$ (RG, $V)$ ( $^{*}$ RG is the root of Tree $T (V, Γ)^{*}$ )

(2) $ϵ = Γ$

(3) $H = T (V, ϵ)$

(4) Mark $l_{i j} \in E - Γ$ : unvisited

(5) Mark ${S M}_{i} \in V - L (l S M)$ : unvisited

(6) while $| L (l S M) | > 2$ do

(7) Compute $q [L (l S M)]$ ( $^{*}$ partition of $L (l S M)^{*}$ )

(8) Select rightmost $L {(l S M)}_{i} \in q [L (l S M)]$

(9) for $l {S M}_{i} \in L {(l S M)}_{i}$ do

(10) Compute $L_{i} = \{l_{i j} \in E - Γ$ , $l_{i j}$ incident to $l {S M}_{i}\}$

(11) if $| L_{i} | = 1$ then

(12) Add $l_{i j}$ to ϵ

(13) Mark $l_{i j}$ : visited

(14) Mark ${S M}_{j}$ ← opposite ( $l {S M}_{i}, l_{i j}$ ): visited

(15) else

(16) for $l_{i j} \in L_{i}$ do

(17) Compute ${S M}_{j}$ ← opposite ( $l {S M}_{i}, l_{i j}$ )

(18) if ${S M}_{j}$ : unvisited then

(19) Compute weight of $l_{i j}$

(20) Mark $l_{i j}$ : visited

(21) Add least weighted $l_{i j}$ to ϵ

(22) Mark ${S M}_{j}$ ← opposite ( $l {S M}_{i}, l_{i j}$ ): finished

(23) Identify biconnected subtree $T_{c {S M}_{i}}$ , $(^{*} c {S M}_{i}$ , subtreeroot $^{*}$ )

(24) Contract $T_{c {S M}_{i}}$ into its root $c {S M}_{i}$

(25) Update $H = T (V, ϵ)$

(26) else

(27) Add edge $l_{i j} = [l {S M}_{i}, l {S M}_{j}]$ to ϵ

(28) Mark $l_{i j}$ : visited

(29) Update $H = T (V, ϵ)$

(30) return $H = T (V, ϵ)$

4.1. DFS Algorithm

DFS Algorithm 1 has to be modified to output a NANBB tree of degree at most $λ + 1$ .

Specifically, in its line (19), DFS Algorithm 1 has to be changed into If $| Γ_{i} | ⩾ λ$ then.

Figure 7 shows the example DFS output for $λ = 3$ ; here each node is at most degree 4 with at most 3 descendants.

4.2. NANBB λ-Connected Tree Communication Network

Algorithm 2 is upgraded into Algorithm 3 to accommodate higher degree tree topology (i.e., Figure 7 for $λ = 3$ ) and output higher λ-connected NANBB tree network as desired (Figure 8 for $λ = 3$ ).

Algorithm 3:AMI λ-connected tree network.

Input: AMI Mesh Network $G = (V, E)$

Output: AMI λ-Connected Tree Netw. $H = T (V, ϵ)$

(1) $T (V, Γ) = D F S (G, R G)$ ( $^{*}$ RG root of Tree $T (V, Γ)^{*}$ )

(2) $ϵ = Γ$

(3) $H = T (V, ϵ)$

(4) Mark $l_{i} \in E - Γ$ : unvisited

(5) Mark ${S M}_{i} \in V - L (l S M)$ : unvisited

(6) while $| L (l S M) | > λ$ do

(7) Compute $q [L (l S M)] \subseteq \{L (c {S M}_{i}) ∣ \forall l {S M}_{i} \in L (c {S M}_{i}), \exists p (l {S M}_{i}, c {S M}_{i}), \deg_{cS M_{i}} = λ + 1\}$ ( $^{*}$ partition of $L (l S M)^{*})$

(8) Select rightmost $L (c {S M}_{i}) \in q [L (l S M)]$

(9) for $l {S M}_{i} \in L (c {S M}_{i})$ do

(10) Compute $L_{i} = \{l_{i j} \in E - ϵ$ , $l_{i j}$ incident to $l {S M}_{i}\}$

(11) $ϵ_{i} = \{l\}$ , $l \in Γ$ , incident to $l {S M}_{i}$ , $| ϵ_{i} | = 1$

(12) while $|ϵ_{i}| < λ$ do

(13) if $| L_{i} | = λ - 1$ then

(14) Add $L_{i}$ to $ϵ_{i}$

(15) Mark $l_{i j} \in L_{i}$ : visited

(16) Mark ${S M}_{j}$ ← opposite $(l {S M}_{i}, l_{i j} \in L_{i})$ : visited

(17) else

(18) for $l_{i j} \in L_{i}$ do

(19) Compute ${S M}_{j}$ ← opposite $(l {S M}_{i}, l_{i j})$

(20) if ${S M}_{j}$ : unvisited then

(21) Compute weight $l_{i j}$

(22) Mark $l_{i j}$ : visited

(23) Add the least weighted $l_{i j}$ to $ϵ_{i}$

(24) Mark ${S M}_{j}$ ← opposite $(l {S M}_{i}, l_{i j})$ : visited

(25) Add $ϵ_{i}$ to ϵ

(26) Identify λ-connected subtree $T_{c {S M}_{i}}$ , ( $^{*} c {S M}_{i}$ , subtree root $^{*}$ )

(27) Contract $T_{c {S M}_{i}}$ into its root $c {S M}_{i}$

(28) Update $H = T (V, ϵ)$

(29) else

(30) Add edge $l_{i j} = [l {S M}_{i}, l {S M}_{j}]$ to ϵ

(31) Mark $l_{i j}$ : visited

(32) Update $H = T (V, ϵ)$

(33) return $H = T (V, ϵ)$

The following changes can be seen in Algorithm 3 NANBB λ-connected tree network: (1)

In line (7), the partition of leaf SM is done with consideration of λ for the degree of $c S M$ :

\begin{matrix} q [L (l S M)] \subseteq \{L (c S M_{i}) ∣ \forall l S M_{i} \in L (c S M_{i}), \exists! c S M_{i} \in p (l S M_{i}, l S M_{i + 1}), {d e g}_{c S M_{i}} = λ\} . \end{matrix}

(3)

(2)

Lines (11) and (12) are added to identify the incident link in the spanning tree.

(3)

Line (13) is added to ensure up to $λ - 1$ links augmentation per leaf SM.

(4)

Lines (28) and (29) are used to create and identify the rightmost λ-connected subtree.

5. SM Node Failure Connectivity Recovery

The scheme developed above can certainly generate multiple disjoint paths to mitigate the weakness of the tree topology and improve the robustness of AMI. However, these paths are seldomly node disjoint as they cross over at numerous SM nodes whose failure can more or less significantly affect the connectivity of such augmented tree network: a leaf SM or noncut SM will have a local limited impact compared to a cut SM that will partition the network into disjoint blocks such that some SMs are not able to report to the RG. Such cut SM nodes are critical for the network connectivity. For example, in Figure 9, the network remains connected after any of the leaf smart meters such as $S M_{3}$ or noncut smart meter like $S M_{10}$ fails. However, the loss of any cut smart meter (critical) like $S M_{1}$ or $S M_{14}$ disconnects the AMI and prevents all the descendant smart meters from reporting to the utility.

In this section, we describe a proactive topology repair scheme to reconfigure the augmented tree network in response to SM node failure. It mostly targets the critical nodes as previously mentioned: a loop detection mechanism is used to define a critical SM node (e.g., $S M_{1}$ in Figure 9) as a choking point in the path to the RG and select supplemental SMs as backup parents to its children SMs ( $S M_{2}$ and $S M_{6}$ in Figure 9).

Each SM node in addition to the routing table maintains a loop detection table to record the packets forwarding activities. The node can use the packet identifier to detect a returning packet and conclude on the existence of a loop.

5.1. Loop Detection Mechanism

The loop detection mechanism as depicted in Figure 9 mimics the depth first search algorithm. In this mechanism, the purpose is not to route the packet to the best candidate next hop in the routing table, but instead to check each next hop to determine if it belongs to a loop.

When a node creates a packet that it wants to use for loop detection, it appends its address to a sequence number to create an identifier that it stores in its loop detection table. The identifier is unique and can be used to trace the packet in the entire network. The address of the next node is also stored in the table. However, the destination field of such packet is always loaded with the router gateway (RG) address.

The loop detection is a per node scheme (i.e., each node initiates the detection and determines if it is a choking point). After a node has created the packet as previously mentioned, it forwards it to its rightmost child in the augmented tree NANBB network, where the packet follows a normal forwarding mechanism per the underlying routing protocol. Hence, it is assumed that there exists a control plane that continuously finds and fills up the $r o u t i n g$ table at each SM node with the best paths to the RG. Any time the initiating node receives a packet to forward, it checks in its loop table to match a preexisting identical identifier. If it is a match, it concludes this is a returning packet, and it confirms a loop.

A packet loss can occur during the loop detection scheme in which case the acknowledgment message is not received back at the forwarding node. After a specified waiting time, the node proceeds to reroute the packet by forwarding it to the next child in the augmented tree.

The illustration of loop detection for node $S M_{1}$ is shown in Figure 9 and described below: (i)

Node $S M_{1}$ creates a packet designated to RG. The packet whose identification is stored in the loop table is forwarded to its rightmost child $S M_{2}$ .

(ii)

Node $S M_{2}$ upon reception notices the source address which prevents sending the packet back to $S M_{1}$ but an acknowledgment message. It then selects the best next path in its routing table and forwards the packet to node $S M_{3}$ .

(iii)

Node $S M_{2}$ fails to receive acknowledgment message after a specified waiting time due to link failure $l_{12} = [S M_{1}, S M_{2}]$ and chose to reroute the packet. It chose to forward the packet to node $S M_{5}$ .

(iv)

Node $S M_{5}$ cannot send the packet back to $S M_{3}$ but an acknowledgment message. The packet is thereafter sent to node $S M_{7}$ from where it naturally flows back through $S M_{6}$ and $S M_{1}$ toward RG.

(v)

Node $S M_{1}$ has initiated the loop detection. At the reception of a packet it checks its loop table and detects a loop as it notices a returning packet. It takes action to notify its status as critical to its children SMs.

(vi)

All the one-hop SM nodes in the neighborhood update their loop table to include the information on the criticality of node $S M_{1}$ .

5.2. SM Node Failure Detection

SM nodes periodically broadcast heartbeat messages to neighbors to notify that they are up and operational and as well report changes to their one-hop neighbors. By means of missing heartbeat messages, active SM nodes can conclude the failure of a neighbor.

At the detection of such failure, the one-hop neighbors of the failing SM node would determine the impact, that is, whether the failing node is critical to network connectivity. They will do so by means of lookup in their loop table to see if the failing SM node is a choking point as previously described. The children of such critical SM node will react to such failure by redirecting their communication to the backup SM parent node, thus isolating the failing cut SM node (like $S M_{1}$ in Figure 10).

6. Algorithm Computational Complexity

The above scheme follows the procedure of the depth first search (DFS) algorithm which is a search that sequentially explores the tree network in a descendant fashion. That is, each SM is visited by the algorithm and at each step all the incident communication links to a given cut smart meter ( $c S M$ ) are explored to determine if they connect to a leaf smart meter ( $l S M$ ) in which case $λ - 1$ back edges are selected to cover the corresponding $l S M$ and create a local λ-connected subtree. The following is the inventory of operations in a tree with n nodes: (i)

n nodes are visited.

(ii)

$n - 1$ links in the tree are visited.

(iii)

$λ - 1$ links are visited and chosen to cover each $l S M$ .

Consider $| l S M | = k$ , size of the set of leaf SM in the spanning tree. The visitation cost for Algorithm 3 (the λ-connected tree) can be evaluated as $[n + n + 1 + k * (λ - 1)]$ . On the other hand, there are $n * (n - 1)$ communication links in the full mesh network with population n nodes, and they are all together visited during the DFS such that the visitation cost due to Algorithm 1 is $[n + n * (n - 1)]$ .

The total combined visitation for both Algorithms 1 and 3 will be $[n + n + 1 + k * (λ - 1)] + [n + n * (n - 1)] = [n^{2} + 2 * n + 1 + k * (λ - 1)]$ and the computational complexity is of order $n^{2}$ (i.e., $◯ (n^{2})$ ).

7. Simulation Results

In this section, we assess the performance of the proposed scheme. The analysis is twofold. Firstly, we use the IEEE 802.11 MAC handshake protocol to compare the efficiency of mesh, tree, and augmented tree NANBB network configuration in terms of signaling overhead. We also use Matlab simulation to provide a comparative representation of average data loss due to communication link failure in those NANBB network configurations.

Assuming the handshake request as well as reply packets of size 20 bytes each and also given a 36% successful rate for the aloha handshake protocol, the signaling overhead for a successful handshake can be estimated to $φ = 120$ bytes per link [24].

The NANBB tree communication network augmentation is mostly about covering each and every leaf smart meter with up to ( $λ - 1$ ) backup edges (Figures 6 and 8). On the other hand, DFS algorithm is deigned to issue a NANBB tree of degree at least λ depending on the level of the desired connectivity λ (Figures 3 and 7). It can also be seen that the number of leaf smart meters in a full degree λ NANBB tree is estimated to $N = λ^{(λ + 1)}$ such that the augmentation process induces additional $(λ - 1) * λ^{(λ + 1)}$ links. Considering the ( $n - 1$ ) links in the original NANBB tree with (n) SMs, the total link maintained in the λ-augmented NANBB tree is estimated to $τ = (n - 1) + (λ - 1) * λ^{(λ + 1)}$ such that given a bidirectional communication link the overall handshake signaling overhead can be expressed as follows:

\begin{matrix} {O v e r h e a d}_{λ - A u g} = φ * [(n - 1) + (λ - 1) * λ^{(λ + 1)}] = 120 * [(n - 1) + (λ - 1) * λ^{(λ + 1)}] . \end{matrix}

(4)

In a full mesh network with n nodes, there are

n (n - 1) / 2

bidirectional communication links in between all the active SMs; also each SM individually communicates with the NAN gateway data aggregator RG so the summary of the handshake signaling can be expressed as

\begin{matrix} O v e r h e a d_{m e s h} = \frac{φ * n (n - 1)}{2} + χ * n, \end{matrix}

(5)

where φ is the SM-to-SM link signaling and χ is the signaling between the gateway data aggregator and any smart meter. Consider

φ = χ = 120

bytes.

Figure 6

Backup SM category in a biconnected tree NANBB.

Figure 7

Tree based NANBB network (degree 4).

Figure 8

Triconnected tree NANBB.

Figure 9

Critical node, loop detection in biconnected tree NANBB.

Figure 10

Critical node, failure recovery in biconnected tree NANBB.

Figures 11, 12, and 13 show signaling overhead comparison with regard to different size of NANBB and connectivity level. We have the following observations: (i)

Regardless of the size of the NANBB network, the signaling overhead difference between the tree and the biconnected tree is insignificant; in fact it is less than 5%.

(ii)

The signaling overhead increases reasonably for connectivity up to 3 and as connectivity approaches 4 it increases significantly to almost 80% for $λ = 5$ in Figure 13.

Figure 11

Signaling overhead comparison for $λ \leq 3$ .

Figure 12

Signaling overhead comparison for $λ \leq 4$ .

Figure 13

Signaling overhead comparison for $λ \leq 5$ .

The simulation result in Figure 14 clearly shows the extremely poor performance of the full mesh NANBB when it comes to signaling overhead. In fact, the overhead increases exponentially with the number of smart meters.

Figure 14

Mesh, biconnected tree, and tree overhead comparison.

On the other hand, the NANBB tree topology shows a very steady slow overhead increase with the number of SMs. It clearly outperforms its mesh counterpart as it barely approaches the 5% ratio at 100-SM population. The performance of the biconnected tree NANBB topology lies in between with a strong similarity to that of the tree. It barely exceeds 50% as the number of SMs grows to a hundred.

For the data loss, the comparative average packet loss for 1-, 2-, and 3-communication link failure is shown in Figure 15. It can be noticed that, in the case of the biconnected tree NANBB topology, there is no data loss until 2 communication links fail all together whereas, for the spanning tree, data loss occurs as soon as a single communication link fails. The robustness of the biconnected tree remains significantly prevalent compared to spanning tree as the number of link failures increases reasonably to 3.

Figure 15

Tree, augmented tree data loss comparison.

8. Conclusions

A framework for tree based communication network augmentation is proposed to improve the robustness of data collection in neighborhood area network building blocks of AMI. It merges the virtues of mesh as well as tree based network topologies: signaling overhead increases reasonably not exceeding 15% for connectivity up to 3. It grows significantly to almost 80% as connectivity approaches 5 (Figure 13). Sufficient redundancy is also provided to mitigate the tree single point of failure such that no data loss occurs until λ adjacent links fail simultaneously. Thus, with the connectivity, while the data loss decreases on one hand, the signaling overhead increases on the other hand, which prompts the search for a trade-off topology to fulfill all together the real-time and availability requirements of AMI. Biconnected tree NANBB ( $λ = 2$ ) performance is in close similarity to that of spanning tree in terms of signaling overhead; regardless of the size of the NANBB network, the signaling overhead difference between the tree and the biconnected tree is less than 5% (Figures 11, 12, and 13). It also provides minimum redundancy as data loss occurs only when up to 2 adjacent links fail all together which is rare (Figure 15).

A proactive topology repair scheme is proposed to address the impact of SM node failure on the augmented tree network connectivity. It relies on a loop detection scheme (Figure 9) to define the criticality of a SM node and specifically targets the cut SM node by selecting a set of supplemental parents as backup to all its children SM nodes. These links come into action immediately after the cut SM fails. By this means, the topology mutates and the AMI network recovers the connectivity by isolating the failing critical SM node (Figure 10).

The proposed scheme however lacks in root redundancy so that any faulty RG will disconnect the corresponding NANBB. Fortunately, many existing research works such as [11] on network reliability in the context of AMI have focused on the cellular network backhaul augmentation that corresponds to the data aggregator unit (i.e., RG) interconnection.

Footnotes

Disclosure

The US Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the NSF, DOE, or the Office of the Assistant Secretary of Defense for Research and Engineering (OASD (R&E)) or the US Government.

Competing Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The first author is supported by the HBGI Scholarship. This research work is supported in part by the US National Science Foundation (NSF 1238859), the US DOE NNSA Sam P. Massie Chair Program, and the Office of the Assistant Secretary of Defense for Research and Engineering (OASD (R&E)) under Agreement no. FA8750-15-2-0119.

References

Qian

R. Q.

Energy efficient self-sustaining wireless neighborhood area network design for smart grid

IEEE Transactions on Smart Grid 2015 6 1 220 229

10.1109/TSG.2014.2344659

2-s2.0-84919913993

Kamto

Qian

Fuller

Attia

Qian

Key Distribution and management for power aggregation and accountability in Advance Metering Infrastructure

Proceedings of the IEEE 3rd International Conference on Smart Grid Communications (SmartGridComm '12)

November 2012

Tainan, Taiwan

360 365

10.1109/smartgridcomm.2012.6486010

2-s2.0-84876013503

Qian

Kamto

Secure anonymous routing in wireless mesh networks

International Conference on E-Business and Information System Security (EBISS '09)

May 2009

1 5

Akyildiz

I. F.

Wang

A survey on wireless mesh networks

IEEE Communications Magazine 2005 43 9 S23 S30

10.1109/MCOM.2005.1509968

2-s2.0-27844590384

Siddiqui

M. S.

Hong

C. S.

Security issues in wireless mesh networks

Proceedings of the International Conference on Multimedia and Ubiquitous Engineering (MUE ’07)

April 2007

Seoul, South Korea

717 722

10.1109/MUE.2007.187

Parks

R. C.

Advanced Metering Infrastructure Security Considerations 2007

Albuquerque, NM, USA

Sandia National Laboratories

http://www.energy.gov/sites/prod/files/oeprod/DocumentsandMedia/20-AMI_Security_Considerations.pdf

AMI System Security Requirements V1.01 2008

AMI SEC Task Force

http://energy.gov/oe/downloads/ami-system-security-requirements-v101-1

Ishii

Graph augmentation problem with diameter requirements

Proceedings of the 3rd International Conference on emphNetworking and Computing (ICNC '12)

December 2012

393 398

Watanabe

Higashi

Nakamura

An approach to robust network construction from graph augmentation problems

Proceedings of the IEEE International Symposium on Circuits and Systems

May 1990

IEEE

2861 2864

2-s2.0-0025642204

10.

Dutta

Kubat

Design of partially survivable networks for cellular telecommunication systems

European Journal of Operational Research 1999 118 1 52 64

10.1016/S0377-2217(98)00281-1

ZBL0937.90012

2-s2.0-0032656387

11.

Charnsripinyo

Tipper

Topological design of 3G wireless backhaul networks for service assurance

Proceedings of the 5th International Workshop on Design of Reliable Communication Networks

October 2005

12.

Abbasi

A. A.

Younis

M. F.

Baroudi

U. A.

Recovering from a node failure in wireless sensor-actor networks with minimal topology changes

IEEE Transactions on Vehicular Technology 2013 62 1 256 271

10.1109/TVT.2012.2212734

2-s2.0-84883690948

13.

Younis

Lee

Gupta

Fisher

A localized self-healing algorithm for networks of moveable sensor nodes

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '08)

December 2008

New Orleans, La, USA

1 5

10.1109/glocom.2008.ecp.9

2-s2.0-67249164556

14.

Akkaya

Senel

Thimmapuram

Uludag

Distributed recovery from network partitioning in movable sensor/actor networks via controlled mobility

IEEE Transactions on Computers 2010 59 2 258 271

10.1109/tc.2009.120

MR2750529

2-s2.0-75149155111

15.

Silber

Sahu

Sing

Liu

Augmenting overlay trees for failure resiliency

Proceedings of the Global Telecommunications Conference (GLOBECOM '04)

December 2004

IEEE

1525 1531

10.1109/GLOCOM.2004.1378238

16.

Zhang

Zheng

Incremental network design with topology augmentation on backup path provisioning in WDM mesh networks

Proceedings of the Asia Communications and Photonics Conference and Exhibition (ACP '10)

December 2010

Shanghai, China

IEEE

276 277

10.1109/acp.2010.5682726

2-s2.0-79851495885

17.

Diestel

Graph Theory 2010 173 4th

Springer

18.

Jain

S. P.

Gopal

On network augmentation

IEEE Transactions on Reliability 1986 35 5 541 543

2-s2.0-0022894550

19.

Fukunaga

Nagamochi

Approximating a generalization of metric TSP

IEICE Transactions on Information and Systems 2007 E90-D 2 432 439

10.1093/ietisy/e90-d.2.432

2-s2.0-33847137655

20.

Khuller

Vishkin

Biconnectivity approximations and graph carvings

Journal of the Association for Computing Machinery 1994 41 2 214 235

10.1145/174652.174654

MR1369200

ZBL0822.68082

21.

Knuth Donald

The Art of Computer Programming 1997 1 3rd

Boston, Mass, USA

Wesley

22.

BFS

Breadth first search and depth first search

February 1996, https://www.ics.uci.edu/~eppstein/161/960215.html

23.

Cormen

T. H.

Leiserson

C. E.

Rivest

R. L.

Stein

Depth-first search

Introduction to Algorithms 2001 2nd

New York, NY, USA

MIT Press, McGraw-Hill

540 549

24.

Leon-Garcia

Widjaja

Communication Networks, Fundamental Concepts and Key Architectures 2003 2nd

McGraw-Hill