Ioannis Z Emiris
email: emiris@di.uoa.gr

Vasilis Margonis
email: basilis.math@gmail.com

Ioannis Psarros
email: ipsarros@uni-bonn.de

Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of 1

Keywords: 2012 ACM Subject Classification Theory of computation → Nearest neighbor algorithms; Mathematics of computing → Dimensionality reduction Approximate nearest neighbor, Manhattan metric, randomized embedding Digital Object Identifier 10.4230/LIPIcs.APPROX-RANDOM.2019.47

Randomized dimensionality reduction has been recognized as one of the fundamental techniques in handling high-dimensional data. Starting with the celebrated Johnson-Lindenstrauss Lemma, such reductions have been studied in depth for the Euclidean ( 2) metric, but much less for the Manhattan ( 1) metric. Our primary motivation is the approximate nearest neighbor problem in 1. We exploit its reduction to the decision-with-witness version, called approximate near neighbor, which incurs a roughly logarithmic overhead. In 2007, Indyk and Naor, in the context of approximate nearest neighbors, introduced the notion of nearest neighbor-preserving embeddings. These are randomized embeddings between two metric spaces with guaranteed bounded distortion only for the distances between a query point and a point set. Such embeddings are known to exist for both 2 and 1 metrics, as well as for doubling subsets of 2. The case that remained open were doubling subsets of 1. In this paper, we propose a dimension reduction by means of a near neighbor-preserving embedding for doubling subsets of 1. Our approach is to represent the pointset with a carefully chosen covering set, then randomly project the latter. We study two types of covering sets: c-approximate r-nets and randomly shifted grids, and we discuss the tradeoff between them in terms of preprocessing time and target dimension. We employ Cauchy variables: certain concentration bounds derived should be of independent interest.

Introduction

Proximity search is a fundamental computational problem with several applications in Computer Science and beyond. Proximity problems in metric spaces of low dimension have been typically handled by methods which discretize the space and therefore are affected by the curse of dimensionality, making them unfit for high-dimensional spaces. In the past two decades, the increasing need for analyzing high-dimensional data led researchers to devise randomized and approximation algorithms with polynomial dependence on the dimension.

A fundamental proximity problem is Approximate Nearest Neighbor search. By known reductions [START_REF] Har-Peled | Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality[END_REF], one can (up to polylogarithmic factors) focus on the decision version with witness, namely the (c, R)-Approximate Near Neighbor problem: Definition 1 (Approximate Near Neighbor). Let (X, d X ) be a metric space. Given P ⊆ X and reals R > 0, c ≥ 1, build a data structure S that, given a query point q ∈ X, performs as follows:

If the nearest neighbor of q lies within distance at most R, then S is allowed to report any point p * ∈ P such that d X (q, p * ) ≤ cR. If all points lie at distance more than cR from q, then S should return ⊥. In general, S returns either a point at distance ≤ cR or ⊥, even when none of the above two cases occurs.

From now on, we assume R = 1 because we can re-scale the data set, and we refer to this problem as c-ANN, or simply ANN. We focus on subsets of d 1 : the input dataset consists of n vectors in R d and the distance function is the standard 1 norm • 1 . Note that all logarithms are base 2.

Previous work. Some highlights in the study of data structures for high-dimensional normed spaces are the various variants, proofs, and applications of the Johnson Lindenstrauss Lemma (e.g. [START_REF] Achlioptas | Database-friendly Random Projections: Johnson-Lindenstrauss with Binary Coins[END_REF][START_REF] Ailon | The Fast Johnson-Lindenstrauss Transform and Approximate Nearest Neighbors[END_REF][START_REF] Anagnostopoulos | Randomized Embeddings with Slack and High-Dimensional Approximate Nearest Neighbor[END_REF]), sketches based on p-stable distributions [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF], and Locality Sensitive Hashing (e.g. [START_REF] Indyk | Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality[END_REF][START_REF] Andoni | Near-optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions[END_REF][START_REF] Andoni | Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors[END_REF]). In the core of most high-dimensional solutions lies the fact that for certain metric spaces e.g. p , p ∈ [START_REF] Achlioptas | Database-friendly Random Projections: Johnson-Lindenstrauss with Binary Coins[END_REF][START_REF] Ailon | The Fast Johnson-Lindenstrauss Transform and Approximate Nearest Neighbors[END_REF], the distance can be efficiently sketched. Spaces which are considered to be harder in this context, such as ∞ , can also be treated [START_REF] Indyk | On Approximate Nearest Neighbors under l_infinity Norm[END_REF], and are very interesting since they can be used as host spaces for various norms [START_REF] Andoni | Approximate near neighbors for general symmetric norms[END_REF].

Significant amount of work has been undertaken for pointsets of low doubling dimension, since it is today one of the primary paradigms for capturing input structure (formal definitions in the next section). For any finite metric space X of doubling dimension dim(X), there exists a data structure [START_REF] Har-Peled | Fast Construction of Nets in Low Dimensional Metrics, and Their Applications[END_REF][START_REF] Cole | Searching Dynamic Point Sets in Spaces with Bounded Doubling Dimension[END_REF]

with expected preprocessing time O(2 dim(X) n log n), space usage O(2 dim(X) n) (or even O(n)) and query time O(2 dim(X) log n + ε -O(dim(X) ).
In [START_REF] Indyk | Nearest-neighbor-preserving Embeddings[END_REF], they introduced the notion of nearest-neighbor preserving embeddings, and it was proven that in this context one can achieve dimension reduction for doubling subsets of 2 , with the target dimension depending only on the dataset's doubling dimension. Even before, Indyk [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF] had introduced a randomized embedding for dimension reduction in 1 , which is suitable for proximity search purposes, and it achieves target dimension polylogarithmic in the size of the pointset. Naturally, such approaches can be easily combined with any known data structure to be used in the projection space. Randomized embeddings have been recently used in the ANN context [START_REF] Bartal | Approximate Nearest Neighbor Search for p-Spaces (2 < p < ∞) via Embeddings[END_REF], for doubling subsets of p , 2 < p < ∞.

It is known that dimension reduction in 1 cannot be achieved in the same generality as in 2 , even assuming that the pointset is of low doubling dimension [START_REF] Lee | Metric structures in L 1 : dimension, snowflakes, and average distortion[END_REF]: there are arbitrarily large n-point subsets P ⊆ 1 which are doubling with constant 6, such that every embedding with distortion D of P into k 1 requires dimension n Ω(1/D 2 ) . Aiming for more restrictive guarantees, e.g. preserving distances within some pre-defined range, is a relevant workaround. Then, dimension reduction techniques for doubling subsets of p , p ∈ [START_REF] Achlioptas | Database-friendly Random Projections: Johnson-Lindenstrauss with Binary Coins[END_REF][START_REF] Ailon | The Fast Johnson-Lindenstrauss Transform and Approximate Nearest Neighbors[END_REF], exist [START_REF] Bartal | Dimension Reduction Techniques for p, (1 < p < 2), with Applications[END_REF], but they rely on partition algorithms which require the whole pointset to be known in advance. Hence, applicability of such techniques is quite limited and, specifically, it is not clear whether they can be used in an online setting where query points are not known beforehand.

Contribution.

In this paper, we establish two non-linear near neighbor-preserving embeddings for doubling subsets of d 1 . We use a definition which is essentially a modified version of the nearest neighbor preserving embedding of [START_REF] Indyk | Nearest-neighbor-preserving Embeddings[END_REF]: the guarantees which are required are weaker since we consider the decision version of the problem, therefore the embedding depends on some range parameter R > 0.

Definition 2 (Near-neighbor preserving embedding). Let (Y, d Y ), (Z, d Z ) be metric spaces and X ⊆ Y . A distribution over mappings f : Y → Z is a near-neighbor preserving embedding with range R > 0, distortion D ≥ 1 and probability of correctness P ∈ [0, 1] if for every α ≥ D and any q ∈ Y , if x ∈ X is such that d Y (x, q) ≤ R, then with probability at least P,

d Z (f (x), f (q)) ≤ D • R, ∀p ∈ X : d Y (p, q) > D • α • R =⇒ d Z (f (p), f (q)) > α • R.
Considering a pointset P ⊂ d 1 of cardinality n, our results concern k 1 as the target space, where k depends on the doubling dimension of P . We assume that R = 1, since we can rescale the dataset. More specifically:

1. In Theorem 10, we prove that for every ε ∈ (0, 1/2) and c ≥ 1, there is a randomized mapping h : d 1 → k 1 that can be computed in time Õ(dn 1+1/Ω(c) ) and is near neighborpreserving for P with distortion 1+6ε and probability of correctness Ω(ε), where

k = (log λ P • log(c/ε)) Θ(1/ε) /ζ(ε),
for a function ζ(ε) > 0 depending only on ε. Although the mapping h depends on the pointset, the parameter c is user-defined and therefore provides a trade-off between preprocessing time and target dimension.

2.

In Theorem 13, we show that for every ε ∈ (0, 1/2), there is a randomized mapping h : d 1 → k 1 that can be computed in time O(dkn) and is near neighbor-preserving for P with distortion 1+6ε and probability of correctness Ω(ε), where

k = (log λ P • log(d/ε)) Θ(1/ε) /ζ(ε),
for a function ζ(ε) > 0 depending only on ε. In this case, the function h is oblivious to P and well-defined over the whole space, but the target dimension depends on d.

On the low-preprocessing-time extreme, one can embed the dataset in near-linear time, but the target dimension is polynomial in log log n. This is to be juxtaposed to the analogous result by Indyk [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF], which provides with target dimension polynomial in log n, without any assumption on the doubling dimension of the dataset. On the other hand, one can obtain a preprocessing time of dn 1+δ for any constant δ > 0, and target dimension which depends solely on the doubling dimension.

Techniques. Both embeddings consist of two basic components. First, we represent the pointset P with an ε-covering set, and then we apply a random linear projection à la Indyk [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF] to that set, using Cauchy variables.

The role of the covering set is to exploit the doubling dimension of P . In the analogous result for 2 [START_REF] Indyk | Nearest-neighbor-preserving Embeddings[END_REF], no representative sets were used; the mapping was just a random linear projection of P . In the case of 1 however, a similar analysis of a linear projection with Cauchy variables without these representative sets seems to be impossible, since the Cauchy distribution is heavy tailed.

In Theorem 10, we consider c-approximate r-nets as a covering set. Inspired by the algorithm of [START_REF] Eppstein | Approximate Greedy Clustering and Distance Selection for Graph Metrics[END_REF] for 2 , we design an algorithm that computes a c-approximate r-net in 1 in subquadratic -but superlinear-time. On the other hand, Theorem 13 relies on randomly shifted grids, which can be computed in linear time, but are inferior to nets in terms of capturing the doubling dimension of the pointset.

To bound the distortion incurred by the randomized projection, we exploit the 1-stability property of the Cauchy distribution. To this end, we prove a concentration bound for sums of independent Cauchy variables that should be of interest beyond the scope of this paper. To overcome the technical difficulties associated with the heavy tails of the Cauchy distribution, we study sums of square roots of Cauchy variables, where in [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF], Indyk considers sums of truncated Cauchy variables instead. Although our concentration bound is rather weak, it is sufficient for our purposes and its analysis is much simpler compared to Indyk's.

Algorithmic implications. Our results show that efficient dimension reduction for doubling subsets of 1 is possible, in the context of ANN. In particular, these results imply efficient sketches, meaning that one can solve ANN with minimal storage per point. Dimension reduction also serves as a problem reduction from a high-dimensional hard instance to a low-dimensional easy instance. Since the algorithms presented in this paper are quite simple, they should also be of practical interest: they easily extend the scope of any implementation which has been optimized to solve the problem in low dimension, so that it may handle high-dimensional data.

Our embedding can be combined with the bucketing method of [START_REF] Har-Peled | Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality[END_REF] for the (1+ε)-ANN problem in d 1 . For instance, setting c = log n in Theorem 10, yields preprocessing time dn 1+o (1) , space n 1+o (1) and query time O(d)•(log λ P • log log n) O(1/ε) assuming that the doubling dimension is a fixed constant. This improves upon existing results: the query time of [START_REF] Krauthgamer | Navigating Nets: Simple Algorithms for Proximity Search[END_REF] depends on the aspect ratio of the dataset, while the data structures of [START_REF] Har-Peled | Fast Construction of Nets in Low Dimensional Metrics, and Their Applications[END_REF][START_REF] Cole | Searching Dynamic Point Sets in Spaces with Bounded Doubling Dimension[END_REF] support queries with time complexity which depends exponentially on the doubling dimension. However, it is worth noting that one could potentially improve the results of [START_REF] Krauthgamer | Navigating Nets: Simple Algorithms for Proximity Search[END_REF][START_REF] Har-Peled | Fast Construction of Nets in Low Dimensional Metrics, and Their Applications[END_REF][START_REF] Cole | Searching Dynamic Point Sets in Spaces with Bounded Doubling Dimension[END_REF] in the special case of 1 , by employing ANN data structures with fast query time, in order to accelerate the traversal of the net-tree. Hence, while our result gives a simple framework for exploiting the intrinsic dimension of doubling subsets of 1 , it is unlikely that it shall improve upon simple variants of previous results in terms of complexity bounds.

Organization. The next section introduces basic concepts and some relevant existing results. Section 3 establishes a concentration bound on sums of independent Cauchy variables. Section 4, achieves dimensionality reduction by means of representing the pointset by a carefully chosen net, while Section 5 employs randomly shifted grids for the same task. We conclude with discussion of results and potential improvements.

Preliminaries

In this section, we define basic notions about doubling metrics and present useful previous results.

Definition 3. Consider any metric space (X, d X ) and let B(p, r) = {x ∈ X | d X (x, p) ≤ r}. The doubling constant of X, denoted λ X , is the smallest integer λ X such that for any p ∈ X and r > 0, the ball B(p, r) can be covered by λ X balls of radius r/2 centered at points in X.

The doubling dimension of (X, d X ) is defined as log λ X . Nets play an important role in the study of embeddings, as well as in designing efficient data structures for doubling metrics. Definition 4. For c ≥ 1, r > 0 and metric space (V, d V ), a c-approximate r-net of V is a subset N ⊆ V such that no two points of N are within distance r of each other, and every point of V lies within distance at most c•r from some point of N .

Theorem 5. Let P ⊂ d 1 such that |P | = n.
Then, for any c > 0, r > 0, one can compute a c-approximate r-net of P in time Õ(dn 1+1/c ), where c = Ω(c). The result is correct with high probability. The algorithm also returns the assignment of each point of P to the point of the net which covers it.

Proof. We employ some basic ideas from [START_REF] Har-Peled | Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality[END_REF]. An analogous result for 2 is stated in [START_REF] Eppstein | Approximate Greedy Clustering and Distance Selection for Graph Metrics[END_REF]. First, we assume r = 1, since we are able to re-scale the point set. Now, we consider a randomly shifted grid with side-length 2. The probability that two points p, q ∈ P fall into the same grid cell, is at least 1 -p -q 1 /2. For each non-empty grid cell we snap points to a grid: each coordinate is rounded to the nearest multiple of δ = 1/10dc. Then, coordinates are multiplied by 1/δ and each point x = (x 1 , . . . , x d ) ∈ [2δ] d is mapped to {0, 1} 2d/δ by a function G as follows: G(x) = (g(x 1 ), . . . , g(x d )), where g(z) is a binary string of z ones followed by 2/δ -z zeros. For any two points p, q in the same grid cell, let f (p),f (q) be the two binary strings obtained by the above mapping. Notice that,

f (p) -f (q) 1 ∈ (2/δ) • p -q 1 ± 1. Hence, p -q 1 ≤ 1 =⇒ f (p) -f (q) 1 ≤ (2/δ) + 1, p -q 1 ≥ c =⇒ f (p) -f (q) 1 ≥ (2/δ) • c -1.
Now, we employ the LSH family of [START_REF] Har-Peled | Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality[END_REF], for the Hamming space. After standard concatenation, we can assume that the family is (ρ, c ρ, n -1/c , n -1 )-sensitive, where ρ = (2/δ) + 1 and c = Ω(c). Let α = n -1/c and β = n -1 .

Notice that for the above two-level hashing table we obtain the following guarantees. Any two points p, q ∈ P , such that p -q 1 ≤ 1, fall into the same bucket with probability ≥ α/2. Any two points p, q ∈ P , such that p -q 1 ≥ c, fall into the same bucket with probability ≤ β.

Finally, we independently build k = Θ(n 1/c log n) hashtables as above, where the random hash function is defined as a concatenation of the function which maps points to their grid cell id and one LSH function. We pick an arbitrary ordering p 1 , . . . , p n ∈ P . We follow a greedy strategy in order to compute the approximate net. We start with point p 1 , and we add it to the net. We mark all (unmarked) points which fall at the same bucket with p 1 , in one of the k hashtables, and are at distance ≤ cr. Then, we proceed with point p 2 . If p 2 is unmarked, then we repeat the above. Otherwise, we proceed with p 3 . The above iteration stops when all points have been marked. Throughout the procedure, we are able to store one pointer for each point, indicating the center which covered it.

47:6

Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of 1 Correctness. The probability that a good pair p, q does not fall into the same bucket for any of the k hashtables is ≤ (1 -α/2) k ≤ n -10 . Hence, with high probability, the packing property holds, and the covering property holds because the above algorithm stops when all points are marked.

Running time. The time to build the k hashtables is k • n = Õ(n 1+1/c ). Then, at most n queries are performed: for each query, we investigate k buckets and the expected number of false positives is

≤ k • n 2 • β = Õ(n 1+1/c
). Hence, if we stop after having seen a sufficient amount of false positives, we obtain time complexity Õ(n 1+1/c ) and the covering property holds with constant probability. We can repeat the above procedure O(log n) times to obtain high probability of success.

The main result in the context of randomized embeddings for dimension reduction in d 1 is the following theorem, which exploits the 1-stability property of Cauchy random variables and provides with an asymmetric guarantee: The probability of non-contraction is high, but the probability of non-expansion is constant. Nevertheless, this asymmetric property is sufficient for proximity search.

Theorem 6 (Thm 5, [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF]). For any ε ≤ 1/2, δ > 0, ε > γ > 0 there is a probability space over linear mappings f :

d 1 → k 1 ,
where k = (ln (1/δ)) 1/(ε-γ) /ζ(γ), for a function ζ(γ) > 0 depending only on γ, such that for any pair of points p, q ∈ d 1 :

Pr f (p) -f (q) 1 ≤ (1 -ε) p -q 1 ≤ δ, Pr f (p) -f (q) 1 ≥ (1 + ε) p -q 1 ≤ 1 + γ 1 + ε .
Note that the embedding is defined as f (u) = Au/T , where A is a k×d matrix with each element being an i.i.d. Cauchy random variable. In addition, T is a scaling factor defined as the expectation of a sum of truncated Cauchy variables, such that T = Θ(k log (k/ε)) (see Lemma 5 in [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF]).

One key observation here is that given a pointset P in a space of bounded aspect ratio Φ, one can directly employ Theorem 6. The number of points can be upper bounded by a function of λ P and Φ, and hence the new dimension, k, depends only on these parameters. This paper proves better bounds than the ones of Theorem 6 for doubling subsets of d 1 , without any assumption on the aspect ratio.

Concentration bounds for Cauchy variables

In this section, we prove some basic properties of the Cauchy distribution, which serves as our main embedding tool. Let C D denote the Cauchy distribution with density c(x) = (1/π)/(1 + x 2 ). One key property of the Cauchy distribution is the so-called 1-stability property:

Let v = (v 1 , . . . , v k ) ∈ R k and X 1 , . . . , X k be i.i.d. random variables following C D , then k j=1 X i v i is distributed as X• v 1 , where X ∼ C D .
The Cauchy distribution has undefined mean. However, for 0 < q < 1, the mean of the q-th power of a Cauchy random variable can be defined. More specifically, for some X ∼ C D we have

E |X| 1/2 = 2 π ∞ 0 √ x 1 + x 2 dx = 2 π π √ 2 = √ 2.
The following lemma provides a bound for the moment-generating function of |X| 1/2 . Lemma 7. Let X ∼ C D . Then for any β > 1:

E exp (-β|X| 1/2 ) ≤ 2 β .
Proof. For any constant β,

1 0 e -βx 1/2 dx = 2 β 2 1 - β + 1 e β .
Then, for any β > 1,

E exp (-β|X| 1/2 ) = ∞ -∞ e -β|x| 1/2 • c(x) dx = 2 π ∞ 0 e -βx 1/2 • 1 1 + x 2 dx = 2 π 1 0 e -βx 1/2 • 1 1 + x 2 dx + 2 π ∞ 1 e -βx 1/2 • 1 1 + x 2 dx ≤ 2 π 1 0 e -βx 1/2 dx + 2 π ∞ 1 e -β • 1 1 + x 2 dx = 2 π • 2 β 2 1 - β + 1 e β + 1 2e β ≤ 4 πβ 2 + 1 2e β ≤ 2 β . Let S := k j=1 |X j |
where each X j is an i.i.d. Cauchy variable. To prove concentration bounds for S, we study the sum S := k j=1 |X j | 1/2 . By Hölder's Inequality, for any x ∈ R d and p > q > 0,

x p ≤ x q ≤ d 1/q-1/p x p .
Consequently, for x = (X 1 , . . . , X k ) ∈ R k , p = 1 and q = 1/2 we have that S ≤ S2 ≤ k • S, hence for any t > 0,

Pr[S ≤ t] ≤ Pr[ S ≤ √ tk]. ( 1
)
We use the bound on the moment-generating function, to prove a Chernoff-type concentration bound for S, which by Eq. ( 1) translates into a concentration bound for S.

Lemma 8. For every D > 1,

Pr S ≤ E[ S] D ≤ 10 D k .
Proof. Since X j 's are independent, E[ S] = √ 2k. Then, by Lemma 7 and Markov's inequality, for any β > 1, it follows that

Pr S ≤ E[ S] D = Pr exp(-β S) ≥ exp -β • E[ S] D ≤ E[exp(-β S)] exp(-β E[ S]/D) = E[exp(-β|X j | 1/2 )] k exp(-β √ 2k/D) ≤ 2 β k • e √ 2βk/D .
Setting β = D completes the proof.

Net-based dimension reduction

In this section we describe the dimension reduction mapping for 1 via r-nets. Let P ⊂ d 1 be a set of n points with doubling constant λ P . For some point x ∈ R d and r > 0, we denote by B 1 (x, r) the 1 -ball of radius r around x. The embedding is non-linear and is carried out in two steps.

First, we compute a c-approximate (ε/c)-net N of P with the algorithm of Theorem 5. Moreover, the algorithm assigns each point of P to the point of N which covered it. Let g : P → N be this assignment. In the second step, for every s ∈ N and any query point q ∈ d 1 , we apply the linear map of Theorem 6. That is, f (s) = As/T , where A is a k×d matrix with each element being an i.i.d. Cauchy random variable. Recall that value T = Θ(k log (k/ε)). By the 1-stability property of the Cauchy distribution, f (s) is distributed as

s 1 • (Y 1 , . . . , Y k ), where each Y j is i.i.d. and Y j ∼ C D . Hence, f (s) 1 = s 1 • S where S := j |Y j |.
We define the embedding to be h = f • g. We apply h to every point in P , and f to any query point q. It is clear from the properties of the net that g incurs an additive error of ±ε on the distance between q and any point in P , so it is sufficient to consider the distortion of f .

Our analysis consists of studying separately the following disjoint subsets of N : Points that lie at distance at most D 0 from the query and points that lie at distance at least D 0 , for some D 0 > 1 chosen appropriately. For the former set, we directly apply Theorem 6, as it has bounded diameter.

The next lemma guarantees the low distortion for points of the latter set, namely those that are sufficiently far from the query. We consider the sum of the square roots of each |Y j |, i.e., S = j |Y j | 1/2 , in order to employ the tools of Section 3. Lemma 9. Fix a query point q ∈ d 1 . For any ε ≤ 1/2, c ≥ 1, δ ∈ (0, 1), there exists

D 0 = O(log(k/ε)) such that for k = Θ log 2 λ P • log(c/ε) + log(1/δ) , with probability at least 1 -δ, ∀s ∈ N : s -q 1 ≥ D 0 =⇒ f (s) -f (q)) 1 ≥ 4.
Proof. Assume wlog that the query point is the origin (0, . . . , 0). For some D 0 > 1, we define the following subsets of N :

N i := {s ∈ N | D i ≤ s 1 < D i+1 }, D i = 2 2i D 0 , i = 0, 1, 2, . . .
By the definition of doubling constant and the fact that two points of N lie at distance at least ε,

|N i | ≤ λ log(4cDi+1/ε) P ≤ λ 4 log(cDi+1/ε) P .
Therefore, by the union bound, and Eq. ( 1):

Pr ∃i∃s ∈ N i : f (s) 1 ≤ 4 s 1 D i = Pr ∃i∃s ∈ N i : S ≤ 4T D i ≤ ∞ i=0 |N i | Pr S ≤ √ 4kT √ D i = ∞ i=0 |N i | Pr S ≤ E[ S] • 2T k2 2i D 0 . By Lemma 8, for D 0 = 800T /k =Θ(log(k/ε)) and k > 4• log λ P • log(cD 0 /ε) + 2 log(2λ P /δ): ∞ i=0 |N i | Pr S ≤ E[ S] 10 • 2 i+1 ≤ ∞ i=0 λ 4 log (cDi+1/ε) P 1 2 i+1 k = ∞ i=0 2 log(λ P )(4 log (cD0/ε)+2i+2) 2 k(i+1) ≤ ∞ i=0 2 log(λ P )•4 log (cD0/ε) • 2 2 log(λ P )(i+1) 2 (4•log λ P •log(cD0/ε))(i+1) • 2 2 log(2λ P /δ))(i+1) ≤ ∞ i=0 2 -2 log(2/δ))(i+1) = ∞ i=0 δ 2 4 i -1 = δ 2 4 -δ 2 ≤ δ.
Finally, for some large enough constant C, we demand that for a function ζ(ε) > 0 depending only on ε, such that, for any q ∈ d 1 , if there exists p * ∈ P such that p * -q 1 ≤ 1, then, with probability Ω(ε):

k > C (log λ P • log(c log k/ε) + log(1/δ)) > 4 • log λ P • log(cD 0 /ε) + 2 log(2λ P /δ) which is satisfied for k = Θ log 2 λ P • log(c/ε) + log(1/δ) .
h(p * ) -f (q) 1 ≤ 1 + 3ε, ∀p ∈ P : p -q 1 > 1 + 9ε =⇒ h(p) -f (q) 1 > 1 + 3ε.
Set P can be embedded in time Õ(dn 1+1/Ω(c) ), and any query q ∈ d 1 can be embedded in time O(dk).

Proof. Let f, g be the mappings defined in the beginning of the section and D 0 = Θ(log(k/ε)). Assume wlog for simplicity that q = 0 d . Then, by Lemma 9 for k = Θ log 2 λ P • log(c/ε) , with probability at least 1 -ε/5, we have:

∀p ∈ P : p -q 1 ≥ D 0 + ε =⇒ h(p) -f (q) 1 ≥ 4.
By Theorem 6, for γ = ε/10 and δ = ε/(5λ 8 log (cD0/ε) P

), with probability at least 1 -ε/5, we get:

∀p ∈ P : p -q 1 ∈ (1 + 9ε, D 0 + ε) =⇒ h(p) -f (q) 1 > (1 + 8ε)(1 -ε) ≥ 1 + 3ε. Moreover, Pr h(p * ) -f (q) 1 ≤ 1 + 3ε ≥ 1 - 1 + ε/10 1 + ε ≥ 1 -(1 -ε/2).
Then, the target dimension needs to satisfy the following inequality:

k ≥ ln (5λ 8 log (cD0/ε) P /ε) 2/ε ζ(ε) = Θ(log log k • log λ P + log λ P • ln(c/ε)) 2/ε ζ(ε) .
Hence, for k = (log λ P • log(c/ε)) Θ(1/ε) /ζ(ε), we achieve a total probability of success in Ω(ε), which completes the proof.

Dimension reduction based on randomly shifted grids

In this section, we explore some properties of randomly shifted grids, and we present a simplified embedding which consists of a first step of snapping points to a grid, and a second step of randomly projecting grid points. Let w > 0 and t be chosen uniformly at random from the interval [0, w]. The function

h w,t (x) = x -t w
induces a random partition of the real line into segments of length w. Hence, the function

g w (x) = (h w,t1 (x 1 ), ..., h w,t d (x d )),
for t 1 , . . . , t d independent uniform random variables in the interval [0, w], induces a randomly shifted grid in R d . For a set X ⊆ R d , we denote by g w (X), the image of X on the randomly shifted grid points defined by g w . For some x ∈ R d and r > 0, the number of grid cells of g w ( d 1 ) that B 1 (x, r) intersects per axis is independent, and in expectation is 1+2r/w. Then, the expected total number of grid cells that B 1 (x, r) intersects is at most (1+2r/w) d . Now let P ⊂ d 1 be a set of n points with doubling constant λ P and q ∈ d 1 a query point. For w = ε/d, the 1 -diameter of each cell is ε and therefore g w (P ) is an ε-covering set of P . The next lemma shows that, with constant probability, the growth on the number of representatives, as we move away from q, is bounded. Lemma 12. Let {D i } i∈N be a sequence of radii such that, for any i, D i+1 = 4D i . Let A i be the points of g w (P ) within distance D i+1 = 2 2(i+1) D 0 from q. Then, with probability at least 1/3,

∀i ∈ {-1, 0, . . .} : |A i | ≤ 4 i+3 λ 2 log(dDi+1/ε) P . Proof. By Lemma 11, E[|A i |] ≤ 8λ
2 log(dDi+1/ε) P for every i ∈ {-1, 0, . . .}. Then, a union bound followed by Markov's inequality yields

Pr ∃i ∈ {0, 1, . . .} : |A i | ≥ 4 i+1 E[|A i |] ≤ 1/3.
In addition,

Pr |A -1 | ≥ 4 E[|A i |] ≤ 1/4.
* -q 1 ≤ 1, then with probability Ω(ε), h (p * ) -f (q) 1 ≤ 1 + 3ε, ∀p ∈ P : p -q 1 > 1 + 9ε =⇒ h (p) -f (q) 1 > 1 + 3ε.

Any point can be embedded in time O(dk).

Proof. We follow the same reasoning as in the proof of Theorem 10. The embedding is h = f • g ε/d , where f is the randomized linear map defined in Section 4. As before, we apply h to every point in P , and only f to queries. The randomly shifted grid incurs an additive error of ε in the distances between q and P .

Assume wlog that q = 0 d and let A i be the points of g ε/d (P ) within distance D i+1 = 2 2(i+1) D 0 from q. Hence, by Lemma 12,

Pr ∃i∃s ∈ A i : f (s) 1 ≤ 4 s 1 D i ≤ ∞ i=0 |A i | Pr S ≤ 4T D i ≤ ∞ i=0 4 i+3 λ 2 log(dDi+1/ε) P Pr S ≤ √ 4kT √ D i .
As Hence, for k = Ω (log 2 λ P • log(d/ε) , with probability at least 1 -ε/5, we have:

∀p ∈ P : p -q 1 ≥ D 0 + ε =⇒ h (p) -f (q) 1 ≥ 4.
Now, we are able to use Theorem 6 for points which are at distance at most D 0 + ε from q, and the near neighbor. By Lemma 12, with constant probability, the number of grid points at distance ≤ D 0 + ε, is at most 32 • λ 4 log(dD0/ε) P . Hence, by Theorem 6, for γ = ε/10 and δ = ε/(160λ 4 log (dD0/ε) P ), with probability at least 1 -ε/5, it holds:

∀p ∈ P : p -q 1 ∈ (1 + 9ε, D 0 + ε) =⇒ h (p) -f (q) 1 > 1 + 3ε.
Moreover, with probability at least ε/2, we obtain:

h (p * ) -f (q) 1 ≤ 1 + 3ε.
As in Theorem 10, the target dimension needs to satisfy the following: Hence, for k = (log λ P • log(d/ε)) Θ(1/ε) /ζ(ε) we achieve total probability of success Ω(ε).

Conclusion

We have filled in a gap in the spectrum of randomized embeddings with bounded distortion only for distances between the query and a pointset: such embeddings existed for 2 and 1 and for doubling subsets of 2 . Here we settle the case of doubling subsets of 1 with a near neighbor-preserving embedding. In the meantime, we obtain concentration bounds on sums of independent Cauchy variables. Our algorithms are quite simple, therefore they should also be of practical interest. We rely on approximate r-nets or randomly shifted grids. For the former, Theorem 10 provides with a trade-off between the preprocessing time required and the target dimension. On the other hand, Theorem 13 has the advantage of fast preprocessing: any point is embedded in O(dk) time, and the embedding is oblivious to the pointset. In regards to the near-linear preprocessing time, the two results are comparable, since the dimension in Theorem 13 can be substituted by the target dimension of Theorem 6.

Notice that any potential improvements to Theorem 6 should lead to improvements to Theorems 10 and 13. The target dimension in these theorems follows from a direct application of Theorem 6 to the representative data points which lie inside a bounding ball centered at the query.

Theorem 10 .

 10 Let P ⊂ d 1 such that |P | = n. For any ε ∈ (0, 1/2) and c ≥ 1, there is a nonlinear randomized embedding h = f • g : d 1 → k 1 , where k = (log λ P • log(c/ε)) Θ(1/ε) /ζ(ε),

Lemma 11 .

 11 Let R > 1 and P := B 1 (q, R) ∩ P . Then, for w = ε/d E |g w (P )| ≤ 8λ 2 log(dR/ε) P . Proof. By the doubling constant definition, there exists a set of balls of radius ε/d 2 centered at points in P , of cardinality at most λ 2 log(dR/ε) P which covers P . For each ball of radius ε/d 2 , the expected number of intersecting grid cells is (1+2/d) d ≤ e 2 . The lemma follows by linearity of expectation.

2

  in Lemma 9, for D 0 = 800T /k = Θ(log (k/ε)), k ≥ 20 log λ P • log dD0 εδ and δ = ε/5, 2i+6+2 log λ P [log(dD0/ε)+2(i+1)] 2 k(i+1)≤ ε/5.

Theorem 13 .

 13 Let P ⊂ d 1 such that |P | = n. For any ε ∈ (0, 1/2),there is a non-linear randomized embedding h : d 1 → k 1 , where k = (log λ P • log(d/ε)) Θ(1/ε) /ζ(ε), for a function ζ(ε) > 0 depending only on ε, such that for any q ∈ d 1 , if there exists p * ∈ P such that p

Acknowledgements IZE is member of team AROMATH, joint between INRIA Sophia-Antipolis and NKUA. IP thanks Robert Krauthgamer for useful discussions on the topic.

Funding Ioannis Z. Emiris: Partially supported by the European Union's H2020 research and innovation programme under grant agreement No. 734242 (LAMBDA). Ioannis Psarros: Generously supported by the Hausdorff Center for Mathematics.

https://arxiv.org/abs/1902.08815.


Minh-Cong Pham

Reza Razi

Quoc-Tuan Tran

Seddik Bacha

Ahmad Hably

Hossein Iman-Eini

Power management in multi-microgrid system based on energy routers

Keywords: back-to-back converter, energy router, frequency coordination, multi-microgrid, voltage source converter

This paper proposes a peer-to-peer interaction between microgrids based on energy router to handle network congestions and other local microgrid issues in multi-microgrid system. First, an overview of energy routers in the vision of Energy Internet is addressed. Energy routers with Back-to-Back converter technology is considered in this paper due to its appropriate requirement. Next, a master/slave approach for load sharing and synchronization with energy router in multimicrogrid system is investigated. Finally, a strategy for frequency coordination between microgrids is presented. In fact, in case of frequency violation, microgrids in islanded multimicrogrid system can be supported by other microgrids through an energy router interface. A simulation model is built in MATLAB/Simulink environment to evaluate the efficiency of the proposed method.

I. INTRODUCTION

One aspect of smart cities' development is the deployment of microgrids (MGs). They are progressively installed at the distribution level, for example the MGs capacity exceeds 1.8 GW in 2018 in the U.S [START_REF] Lasseter | Smart Distribution: Coupled Microgrids[END_REF], [START_REF] Munsell | US Microgrid Capacity Will Exceed 1.8GW by 2018le[END_REF]. A group of interconnected MGs forms a multi-microgrid (MMG) system which has become a trendy research topic recently [START_REF] Hatziargyriou | MICROGRIDS ARCHITECTURES AND CONTROL[END_REF]- [START_REF] Zeng | Research on islanding partition algorithm for the multi-microgrids[END_REF]. In a MMG system, it is mostly presumed that the power dispatch of MGs must pass through the power network. However, in this paper, MGs in MMG system are able to interact directly with each other. In fact, the adjacent MGs can trade energy directly, which is the key motivation for the development of the MMG system and smart grids.

In term of connection between MGs, in literature, there are two types of interconnection. In the first type, the MGs can be connected with each other's via the AC line with the use of a breaker [START_REF] Liu | General distributed secondary control for multi-microgrids with both PQ-controlled and droop-controlled distributed generators[END_REF], [9]. With an appropriate synchronization algorithm, this type of connection has a low investment cost. However, the main drawback of this method is the difficulty of power management between MGs. In the second type, a common DC line can be used as the interface between physical MGs [START_REF] Kargarian | Multi-microgrid energy systems operation incorporating distribution-interline power flow controller[END_REF]. In this way, each MG can be controlled dependently, which leads to flexible voltages and frequencies in the MMG system. Therefore, in this paper, the connection between MGs is enhanced by a DC line.

On the other hand, Energy Internet (EI) is a concept that has been regarded as a new evolution stage of the smart grid. EI aims to increase the energy transmission efficiency and optimize the energy dispatching in time and space. In [START_REF] Pourbabak | Centralized, decentralized, and distributed control for Energy Internet[END_REF], the EI is defined as an Internet-type network, consisting of all the grid elements, which closely cooperate with others by sharing both energy and information. Agents or components of this network comprise different prosumers and consumers that have the capability to carry out decisions by themselves.

MGs, distributed energy resources (DERs), smart grids, private or governmental energy networks, and any community of prosumers and consumers can be a part of this massive network as agents. In this new system, energy routers (ERs) play a key role [START_REF] Xu | Energy router: Architectures and functionalities toward energy internet[END_REF]. ER is an active technological element in smart grids. ERs dynamically adjust the energy distribution in transmission and distribution networks by rerouting energy flows. In other words, ERs take on two major tasks, dynamic adjustments of energy flows and realtime communications between power devices [START_REF] Xu | Energy router: Architectures and functionalities toward energy internet[END_REF]. In this paper, the methodology for controlling in MMG system through ERs technology is investigated.

The paper is organized as follows. First, an over view of ERs is described in Section II. Next, in Section III, the control of ERs is presented. Section IV indicates the simulation results and concluding remarks are presented in Section V.

II. ENERGY ROUTERS: AN OVERVIEW

A. Functions of Energy Routers

ERs functions can be divided into two main categories: User level and Grid level [START_REF] Xu | Energy router: Architectures and functionalities toward energy internet[END_REF]. In User level, ERs connect directly to the customers and they can act as a central controller in MGs. The main task of ERs in this level is to provide all the energy services for their customers. Thus, the ERs need to enhance the plug-and-play feature of the costumers and communication with customers for providing the services. On the other hand, in the Grid level, each ER is represented for one MG. They are interfaces between the MG and other entities in the grid network such as other MGs or main grid. The objectives of ERs in this level is to manage the operation of the MGs and optimize the energy usage. ERs are able to connect or disconnect from the grid to protect the MGs system. In addition, with a smart energy management system, ERs communicate with each other for exchanging the energy to minimize the operation cost and maximize the income. For instance, by collecting the data from other ERs, MGs can negotiate and buy the surplus energy from other MGs instead of the main grid.

B. Requirements of Energy Routers Architecture

The ER is a technological integration of power electronics, communications and automations. Therefore, its design requirements include the following aspects [START_REF] Xu | Energy router: Architectures and functionalities toward energy internet[END_REF], [START_REF] Wu | Energy router interface model based on bidirectional flow control for intelligent park[END_REF].

Power electronics are fundamental components in the ERs to perform automatic energy distribution and management. Therefore, all the power electronic elements must be able to operate fast and stable to guarantee the correct enforcement of the commands issued by the intelligent management module. In addition, the ERs must have an intelligence module to deal with the information about energy management from the grid system. This module utilizes the information collected through the communication module and determines the control changes to be made in the grid through the ER cooperation. Plug-and-play ability, which is an important requirement feature in smart grid concept, requires the ERs a common standard interface with both energy exchange and communication functions. More particularly, they are expected to quickly analyze different classes of electrical characteristics, distinguish the load, energy storage and power generation equipment. Furthermore, the automatic access or disconnection of energy sources have to follow the user's request. Therefore, ERs architecture have to ensure this plugand-play feature. Finally, the communications between ERs must satisfy three requirements: transmission latency, communication reliability and information security.

C. Topologies of Energy Routers

In the literature, there are three types of ERs: Solid State Transformer (SST)-based ER, DC-link-based ER and Power Line Communication (PLC)-based ER [START_REF] Guo | Review of energy routers applied for the energy internet integrating renewable energy[END_REF].

Fig. 1 (a) presents an ER based on SST. The SST with three stage structure has the features of relatively simple control, high functionality and high reliability. Firstly, the high-voltage AC/DC stage rectifies high-voltage alternating current (HVAC) into medium-voltage direct current (MVDC), which can be used to connect DC grids. Then, the middle DC/DC stage adopts dual active bridge topology to transform the MVDC to a regulated low-voltage direct current (LVDC), which is used to facilitate the DC bus or connect DERs. The employment of high-frequency transformer is a benefit to attain electrical isolating and voltage converting. Finally, DC/AC inverter generates an AC output voltage, which can be used to connect AC grids or loads. Thus, the SST-based ER can present multiple plug-and-play interfaces for access to users. Each interface may connect multiple energy networks or devices, as long as the total power does not exceed the capacity limits of the connected interface. The above SSTbased ERs are appropriate for transmission systems with high voltage and power level.

On the other hand, Fig. 1 (b) presents the PLC-based ERs. The ERs based on PLC are able to transmit energy and information through the same transmission line, which has the benefits of simple wiring and reducing device volume and cost. Nevertheless, the PLC technology performs power transmission and data communication at the same time, which is difficult to implement the time-division and multi-path transmission of power flows.

Finally, DC-link-based ERs shown in Fig. 1 (c) are useful for distribution systems which have a low voltage and power level. In the literature, DC-link-based ERs are witnessed to have a high degree of reuse and integration compared to the SST-based ERs [START_REF] Guo | Review of energy routers applied for the energy internet integrating renewable energy[END_REF]. In this architecture, through power electronic converters and information communication technology, all the components in MMG system are connected to a DC common bus, which acts as an intermediate link of the energy forwarding. The proposed DC-link can provide energy balance among multiple renewable energy sources and loads. In addition, the strategies for energy management and control can be executed directly in the controller of the converter. This paper considers an application of ERs for a low voltage MMG system, so Back-to-Back (BTB) converterbased ERs are the best candidate. The core in ER structure is a Voltage Source Converter (VSC). The details of the selected topology is shown in Fig. 2 and will be discussed in Section III.

III. CONTROL OF ENERGY ROUTERS

A. Control Strategy for Energy Routers 1) Peer-to-peer energy exchange

In this paper, instead of energy trading through the main grid, MGs are able to transfer the energy directly between each other through ERs. The control strategy for ERs in MMG system is based on master/slave strategy.

The rules to choose the master converter are [START_REF] Liu | Interconnecting microgrids via the energy router with smart energy management[END_REF]:  When MMG system is connected to the main grid, VSC related to the main grid is regarded as the master converter and other VSCs are the slave converters;

 When MMG system is disconnected from the main grid, the master converter shall be the VSC in connection with the MG supplying energy to other MGs, while the other VSCs received energy shall be the slave converter. In case there are more than one MG that supply the energy, the MG with highest surplus energy is the master or the system can be run in multi-master strategy. In this paper, the first approach is selected.

With the master VSC, its outer-loop controller works as DC voltage controller to keep the DC-link voltage constant. In fact, when the converter dispatches the power, the DC bus voltage must be stable to maintain the energy balance in the system. In contrast, the other VSCs work in slave mode. Their out-loop controllers work as the active/reactive power controllers, with the purpose being to manage their power. As defined in Table I, VSCs have three control patterns according to the operational condition of their inner and outerloop controllers. The different operational modes of the MGs are figured out by choosing appropriate control patterns for the VSCs, which will also determine the roles of the VSCs (master or slave) in the process of power flow. The master converter works in control pattern 1 and the slave converters can be chosen to work in either pattern 2 or pattern 3, according to the role it plays in the process of power flow.

2) Frequency coordination

The frequency control of the MMG system can be improved by the ERs [START_REF] Yoo | Multi-frequency control in a stand-alone multi-microgrid system using a back-to-back converter[END_REF]. A summarized MMG system is shown in Fig. 3 (a), where an ER is used for interconnecting two adjacent MGs. It is assumed that converter 1 is responsible for the regulation of the DC-link voltage whereas converter 2 is used for regulating the frequencies of two adjacent MGs. The detailed frequency control of converter 2 is shown in Fig. 3 (b), which includes the current control and the multi-frequency control. The real power reference (PBTB) is given by the outer multi-frequency controller, as Equation (1):

𝑃 𝐵𝑇𝐵 = 𝑘 𝑝𝑓 (𝑓 𝑛1 -𝑓 𝑛2 ) + 𝑘 𝑖𝑓 ∫(𝑓 𝑛1 -𝑓 𝑛2 )𝑑𝑡 (1)
where fn1 and fn2 are the normalized frequencies of MGs 1 and 2, respectively; kpf and kif are the proportional and integral gains of Proportional Integral (PI) controller in the multi-frequency controller, respectively. The frequency of MGs is normalized to achieve the unique value of frequency deviation. Equation (2) shows the normalized frequency of MGi.

where, 𝑓𝑖 represents the measured frequency of MGi; fi,,rated is the rated frequency of MGi; fi,max and fi,min are the maximum and minimum frequency limitations, respectively.

B. Dual loop controller for VSC

The controller structure of the voltage source converters (VSCs) is shown in Fig 4. The dual-loop controllers consist of two loops: (1) the inner-loop controller, also known as the current feedback loop; (2) the outer-loop controller, which can be either a DC voltage controller or an active/reactive power controller, depending on the control objective of each VSC [START_REF] Liu | Interconnecting microgrids via the energy router with smart energy management[END_REF].

1) Inner loop controller

The voltage control equations of the VSCi inner-loop controller in rectifier mode can be written as:

𝑣 𝑑𝑖 = -(
where KPi and KIi are the proportional and integral regulation gain in the inner loop, respectively. Similarly, the voltage equations of VSCi working in the inverter mode can be written as:

𝑣 𝑑𝑖 = (𝐾 𝑃𝑖 + 𝐾 𝐼𝑖 𝑠 ) (𝑖 𝑖𝑑𝑟𝑒𝑓 -𝑖 𝑑𝑖 ) -𝜔 𝑖 𝐿 Ʃ𝑖 𝑞𝑖 + 𝑒 𝑑𝑖 ( 4
)
𝑣 𝑞𝑖 = (𝐾 𝑃𝑖 + 𝐾 𝐼𝑖 𝑠 ) (𝑖 𝑖𝑞𝑟𝑒𝑓 -𝑖 𝑞𝑖 ) + 𝜔 𝑖 𝐿 Ʃ𝑖 𝑑𝑖 + 𝑒 𝑞𝑖 (5)

2) Outer-loop controller

The outer-loop is used to generate the inner-loop current reference signal and input to the inner loop control. According to different control objectives, the outer-loop controller can be classified as active/reactive power controller or DC voltage controller.

Active/Reactive Power Controller: The active/reactive power controller is used to keep the VSC working such that its active/reactive power output on the AC side shall follow the reference command value issued by the MG controller, with zero steady-state error. Classical proportional-integral (PI) regulators are used in the outer-loop control to calculate the current commands to the inner-loop with the power deviations. Pi and Qi are compared with their reference inputs Piref and Qiref, respectively, and the result of the comparison is used by the PI controller to calculate the current command value.

DC Voltage Controller:

The DC voltage controller is responsible for keeping the DC-link voltage within an adequate range around the command value issued by the MG controller. For VSCi controlled by the DC voltage controller, the active power Pi exchanged with the AC systems is identical to the DC power Pdc stored in Cdc.

𝑃 𝑑𝑐 = 1 2 𝐶 𝑑𝑐 𝑑𝑢 𝑑𝑐 2 𝑑𝑡 = ∑ 𝑃 𝑖 𝑖=1,2,3 (6)
The current command input to the d-axis of the inner-loop current controller is

𝑖 𝑖𝑑𝑟𝑒𝑓 = (𝐾 𝑃𝑑𝑐 + 𝐾 𝐼𝑑𝑐 𝑠 ) (𝑢 𝑑𝑐𝑟𝑒𝑓 2 -𝑢 𝑑𝑐 2 ) ( 7
)
where KPdc and KIdc are the proportional and integral regulation gains, respectively. With this controller, the d-axis current command is derived.

IV. SIMULATION RESULTS

The detailed model of the MMG system (Fig. 2) is implemented in the MATLAB/Simulink environment. The model is separated into five areas by an ER. In fact, for simplicity, instead of an ER for each MG, one ER is used for all MGs. The simulated system consist of four MGs which can be connected or disconnected from the main grid. Also, MG1 and MG4 have battery energy storage systems (Lithium-Ion batteries).

A. Synchronization 1) Disconnection from the main grid

In the first study, the transient state of the MMG system from grid connected mode to islanded mode is considered. At first, in grid connected mode, the grid converter is in master mode and the rest of converters are in slave mode. The MMG system is supplied by the main grid. At t=5 s, the main grid is disconnected from MMG system via a DC switch. At this moment, among four MGs, thanks to the remaining energy in battery energy storage system (BESS), MG1 has the highest surplus energy (highest SOC), so the converter of MG1 becomes the master converter. The converter of MG1 work in DC link control mode and the others work in P/Q control mode. As a result, MG1 is responsible for supplying its load and other MGs in the system until reaches its limitation (SOC limit). The details of the active power flows and the DC-link voltage variation are demonstrated in Fig. 5.

2

) Reconnection to the main grid

In this scenario, the transient state from islanded mode to grid connected mode is considered, which is shown in Fig. 6. As discussed earlier, the ERs, i.e. BTB converters, also provide isolation between the both sides of the DC link. Therefore, we only need to synchronize the converters in inverting mode by phase locked loop (PLL). At first, MG1 is in master mode and the rest of inverters are in slave mode. At t=5 s, the main grid is connected and MG1 comeback to slave mode. As shown in Fig. 6, when the system is resynchronized again, there are only slight fluctuations in the output power curves, but the fluctuation range of the DC-link voltage at the moment of power transfer is major and the stable state is restored quickly.

B. Energy exchange between microgrids

In this part, the objective of the simulations is to analyze the energy exchange in MMG system. Thus, the main grid is disconnected and the simulated MMG system is considered to work in only stand-alone mode.

1) Scenario 1

This scenario demonstrates the dynamic characteristics of the MMG system during the transient load changes. In this scenario, at t=5 s, MG2 is disconnected from MMG system, while the power demand of MG4 increases. The operational mode of all MGs remains constant, such that MG1 serving as the master converter and other converters working as the slave converters. The variations in power flows, as well as the DClink voltage are demonstrated in Fig. 7 (a), (b) respectively.

2) Scenario 2

In this scenario, it is assumed that the MMG system has to change the master due to the energy constrain which is the state of charge (SOC) of batteries in this case.

To be in master mode in MMG system, the MG must have the highest surplus of energy. Following this strategy, all the MGs can become master, which is depended on network situation. The maximum and minimum values of SOCs of BESS in the simulation are 80% and 20%, respectively. From t=0 s to t=5 s, the BESS of MG1 acts as master converter to control the DC-link. So, BESS in MG1 works in discharging mode. In addition, during this period, BESS in MG4 is allowed to charge until it reaches the upper limit of SOC. On the other hand, at t=5 s, the SOC of BESS in MG1 reaches its lowest limit (20%), so the BESS change from discharge to charge mode. In this condition, the MMG system needs a new master converter. With the SOC of BESS above 50 %, the converter of MG4 becomes a master converter instead of MG1. Therefore, the SOC of BESS in MG4 decreases rapidly in the last period.

8 (a) illustrates the energy exchange in MMG system. At t=5s, the power curve of MG4 overtakes the one of MG1 to become the supplier for the system. There is a small fluctuation of the DC voltage when the system change the master controller (Fig. 8 (b)). The detail of SOCs of MGs is describe in Fig. 8 (c).

C. Frequency coordination

In this study, MG1 and MG4 are investigated for frequency coordination. They use grid-forming converters with conventional frequency droop controller. To show the effectiveness of the multi-frequency control, a comparison study between the multi-frequency control and the single frequency control is presented.

It is assumed that MG1 has a higher load condition than MG4 so the initial frequency of MG1 is lower than MG4. In t=2.5 s and t=3.5 s, more loads are added into the MG1, respectively, which worsens the frequency condition in MG1. Initially, there is different frequencies in steady state. In fact, the frequency of MG4 with single frequency control remains constant because there is no disturbance in MG4. But, with the multi-frequency controller, the frequencies of both MGs are considered in the ER. The disturbance in MG1 can be recognized by the multi-frequency control. Fig. 9 shows frequency waveforms of the MMG system using either single frequency control or the multi-frequency control. In this scenario, it is assumed that the proposed control method is only applied when the MGs reach a critical value (below 48.8 Hz and above 50.2 Hz). Therefore, as shown in Fig. 9, at time t=3.5 s, when MG1 drops in the frequency by 49.8 Hz, the proposed control is activated. The power reserve in MG4 can then be shared accordingly to recover the MG1 frequency. As a result, the frequency of MG4 is deviated by the disturbance in MG1 and the frequency of MG1 has come back to the acceptable value.

V. CONCLUSION

In conclusion, in this paper, the interface between MGs via ERs is developed. Firstly, to cooperate between MGs, the control approaches and interconnections between them are presented. A peer-to-peer control strategy for interaction in the MMG system is selected. Next, the paper introduces the concept of ER as an interface among MGs, with its characteristics, design requirement, functionalities and topologies for implementation. DC-link-based ER technology is chosen to apply in the paper. To verify the ER application, a stand-alone MMG system with ER interface is simulated in MATLAB/SIMULINK environment. In the case transient events such as disconnection/reconnection with the main grid, the ER is able to keep the DC-link voltage stable. In addition, MGs are allowed to exchange the energy directly among them via the ER interface. The energy constraints of the MGs such as the SOC is also investigated. A methodology for frequency coordination through ERs is also introduced in this paper. This approach is implemented when MGs are not able to maintain their standard frequency. With that, MGs can be supported by other MGs, which not only improves the reliability of MGs, but also reduces the cost of ancillary services.

Fig. 1 .

 1 Fig. 1. Different types of the ERs (a) SST-based ERs, (b) PLC-based ERs, (c) DC link-based ERs.

Fig. 2 .

 2 Fig. 2. The chosen topology of the ER.

  -𝑓 𝑖,𝑟𝑎𝑡𝑒𝑑 ) (𝑓 𝑖,𝑚𝑎𝑥 -𝑓 𝑖,𝑟𝑎𝑡𝑒𝑑 ) , (𝑓 𝑖 > 𝑓 𝑖,𝑟𝑎𝑡𝑒𝑑 ) (𝑓 𝑖 -𝑓 𝑖,𝑟𝑎𝑡𝑒𝑑 ) 𝑓 𝑖,𝑟𝑎𝑡𝑒𝑑 -𝑓 𝑖,𝑚𝑖𝑛 ) , (𝑓 𝑖,𝑟𝑎𝑡𝑒𝑑 > 𝑓 𝑖 )

Fig. 3 .

 3 Fig. 3. (a) Frequency control in MMG system using ER and (b) its details [16].

Fig. 4 .

 4 Fig. 4. Control schematic of the Voltage Source Converters (VSCs) [15].

Fig. 5 .Fig. 6 .

 56 Fig. 5. Simulation results of disconnection scenario: (a) Power flow; (b) DC link voltage.

Fig. 8 .Fig. 7 .

 87 Fig. 7. Simulation results of scenario 1: (a) active power; (b) DC link voltage.

TABLE I .

 I CONTROL PATTERNS FOR VSCS UNDER DIFFERENT

	SCENARIOS
	Control Pattern	Inner-loop Controller	Outer-loop Controller
	Pattern 1 (master mode)	Rectifier	DC voltage control
	Pattern 2	Rectifier	P/Q control
	Pattern 3	Inverter	P/Q control

  𝐾 𝑃𝑖 + 𝐾 𝐼𝑖 𝑠 ) (𝑖 𝑖𝑑𝑟𝑒𝑓 -𝑖 𝑑𝑖 ) + 𝜔 𝑖 𝐿 Ʃ𝑖 𝑞𝑖 + 𝑒 𝑑𝑖  (2) 𝑖 𝑖𝑞𝑟𝑒𝑓 -𝑖 𝑞𝑖 ) -𝜔 𝑖 𝐿 Ʃ𝑖 𝑑𝑖 + 𝑒 𝑞𝑖

	𝑣 𝑞𝑖 = -(𝐾 𝑃𝑖 +	𝐾 𝐼𝑖 𝑠	) (

ACKNOWLEDGMENT

This work has been supported by the m2M-GRID project of the joint programming initiative ERA-Net Smart Grids Plus.


Reza Razi

Minh-Cong Pham

Ahmad Hably

Seddik Bacha

Quoc-Tuan Tran

Hossein Iman-Eini

Robust hybrid control of parallel inverters for accurate power-sharing in microgrid

Keywords: Hybrid control, inductive microgrid, impedancepower droop, conventional droop method, parallel inverters, power sharing

The communication link, low reliability, inaccurate power sharing and voltage and frequency deviations are some challenges in control methods of parallel inverters in high voltage microgrids. This paper proposes a hybrid control method using the impedancepower droop and conventional droop methods. In the proposed hybrid method, the impedance-power droop method works as the main strategy in steady state and the conventional droop method is employed as auxiliary strategy during startup and transient states. The notable advantages of the proposed method are low virtual impedances, no need for recognition of system parameters, simple and low calculations. Moreover, the voltage deviation in the steady state is minimized and the frequency deviation is completely eliminated. Finally, the performance of the control method is validated by simulation.

I. INTRODUCTION

In recent years, the operation of parallel inverters has expanded dramatically [START_REF] Lin | An Improved Proportional Load Sharing Strategy for Meshed Parallel Inverters System With Complex Impedances[END_REF], [START_REF] Gaztanaga | Real-Time Analysis of the Control Structure and Management Functions of a Hybrid Microgrid System[END_REF]. In parallel operation, the inverters should be controlled in order to avoid overloading and maintain good power quality requirements [START_REF] Caldognetto | Power-Based Control of Low-Voltage Microgrids[END_REF]. Many studies have been done in the literature for the control of parallel inverters in islanded microgrids. Parallel inverters control methods can be classified into two main categories: communication link-based control [START_REF] Sun | Modeling, analysis, and implementation of parallel multi-inverter systems with instantaneous average-currentsharing scheme[END_REF]- [START_REF] Logenthiran | Intelligent Control System for Microgrids Using Multiagent System[END_REF] and droop characteristics-based control [START_REF] Logenthiran | Intelligent Control System for Microgrids Using Multiagent System[END_REF]- [START_REF] Hossain | Design of Robust Distributed Control for Interconnected Microgrids[END_REF].

In communication link-based control methods, a central controller typically sends control commands to the units via communication links. Voltage and frequency regulations and accurate power sharing are remarkable features of this method. However, high cost for high-bandwidth communication links and low reliability are the main drawbacks of this method. Disconnecting the communication link in this method can lead to inaccuracy or even instability [START_REF] Han | Review of Power Sharing Control Strategies for Islanding Operation of AC Microgrids[END_REF].

On the other hand, in droop characteristic-based control methods, despite of the no need for communication links, there are well-known issues such as voltage and frequency deviations and harmonic current sharing [START_REF] Han | Review of Power Sharing Control Strategies for Islanding Operation of AC Microgrids[END_REF].

Recent studies have tried to use both methods of control, known as hybrid control [START_REF] Yu | Control of Parallel-Connected Power Converters for Low-Voltage Microgrid—Part I: A Hybrid Control Architecture[END_REF]- [START_REF] He | An islanding Microgrid power sharing approach using enhanced virtual impedance control scheme[END_REF]. One of the common hybrid control methods is the secondary control to eliminate the voltage and frequency deviations caused by the conventional droop control method. This method uses central integrated controllers to ensure voltage and frequency stability at the same time [START_REF] Shafiee | Distributed secondary control for islanded microgrids-a novel approach[END_REF]. Therefore, a droop characteristic-based control method is used in which the communication link is required to send AC bus voltage information. This method is inspired by the secondary control of power systems used in local controllers to shift the local droop characteristic [START_REF] Han | Review of Power Sharing Control Strategies for Islanding Operation of AC Microgrids[END_REF]. The disadvantages of this approach are the need for a central controller, and the delay or loss of communication links.

To eliminate the time delay of the secondary controllers, power sharing strategy based on the washout filter has been presented [START_REF] Han | Analysis of Washout Filter-Based Power Sharing Strategy--An Equivalent Secondary Controller For Islanded Microgrid without LBC Lines[END_REF]. The washout filter is a first-order high-pass filter that is equivalent to a secondary controller. This method is a dynamic feedback that, unlike static feedback (or droop control), can maintain the voltage and frequency references against load changes. Another way to replace the secondary control is the control based on Global Positioning System (GPS) synchronization [START_REF] Golsorkhi | A GPS-based control method for load sharing and power quality improvement in microgrids[END_REF]. In this method, each unit is equipped with the GPS receiver that generates a pulse with frequency of 1 Hz.

Although the aforementioned methods partially meet the challenges, but the disconnection of the communication links will disrupt the performance of the methods. In this paper, a combination of control methods is used to cover the problems of both methods as much as possible. In the proposed control method, impedance-power droop controller based on low bandwidth communication link is used, which is replaced with an improved conventional droop controller in emergencies.

In the proposed hybrid controller, the voltage and frequency deviations of the conventional droop method and the need for a communication link in the impedance-power droop method are solved. The simulation results confirm the feasibility of the proposed control method.

In sections II and III, the conventional droop method and impedance-power droop method are presented, respectively. Section IV proposes the hybrid control method for parallel inverters. In section V, the performance of the proposed control algorithm has been investigated by extensive simulations. Finally, section VI concludes the paper.

II. CONVENTIONAL DROOP METHOD

In this paper, the conventional droop method is used for startup operation and replacing the main control method in emergencies. In this regard, two parallel islanded inverters are considered as shown in Fig. 2, which feed the common load. The system parameters are listed in Table I.

Each inverter can be modeled as an ideal voltage source in series with an impedance, which is connected to the load via feeders. In this state, power sharing without any controller is determined based on the total impedance of each path (output impedance and feeder impedance). As a result, a low-capacity inverter with smaller impedances will be forced to take the majority of the load and vice versa. Therefore, the relationship between the power components (active and reactive powers) and the voltage components (amplitude and frequency), called the conventional droop control method, is used to control the power sharing. Implementation of the conventional droop control method for an islanded inverter is shown in Fig. 3 [START_REF] Han | Review of Power Sharing Control Strategies for Islanding Operation of AC Microgrids[END_REF].

The voltage and frequency droop characteristics in an inductive islanded microgrid are given by equation (1): . .

i rated i i i rated i i nP V V m Q       (1)
where i is the index representing each inverter, ωi and ωrated are the output and nominal angular frequency of the distributed generation (DG) unit, Vi and Vrated are the output and reference DG voltage amplitude, Pi and Qi are the average fundamental power measured after low-pass filtering and mi and ni are droop coefficients of the controller, respectively. Typically, the droop coefficients are determined based on the nominal power of inverter and the maximum deviations of the voltage amplitude and frequency.

Finally, the reference signal for controlling the output voltage of the inverter is obtained using the frequency and voltage information of Equation ( 2):

.sin( )

droop i i V V t   (2)
As previously stated, this reference voltage signal confirms only the power sharing at the fundamental frequency. Despite of its simplicity and no need for communication link, this method suffers from the following disadvantages:

 Voltage and frequency deviations,  Inaccuracy in reactive power sharing,  Inappropriate distribution of harmonic power,  Low power quality.

In the present proposed method, both these disadvantages and advantages of the conventional droop method, which are better dynamics and a suitable alternative when disconnecting the link, are taken into account.

III. IMPEDANCE-POWER DROOP METHOD

In literature, the most common way to modify the effective line impedance is to use the virtual impedance in series with the line impedance in accordance with equation (3):

.

ref droop L v V V i Z  ( 3
)
where Vdroop is the reference voltage obtained from the droop controller, iL is output current of the inverter and Zv is virtual impedance.

In the impedance-power droop method, the concept of virtual impedance is also used in the structure of a new algorithm [START_REF] Razi | An Impedance-Power Droop Method for Accurate Power Sharing in Islanded Resistive Microgrids[END_REF]. In this method, the effect of inherent impedances on power sharing is minimized to the extent possible by using a suitable feedforward signal. As a result, power sharing is only affected by the impedance of the lines. In the following, a simple droop method, called the impedance-power droop, is proposed to enable power sharing by setting proper virtual impedances. The impedance-power droop is defined as follows:

+ -

L1 rL1 C1 i C1 i L1 Local Controller VDC1 i C1 i L1 v C1 DG 1 Z L1 + - L2 rL2 C2 i C2 i L2 Local Controller VDC2 i C2 i L2 v C2 DG 2 Z L2 i O Common Load + - v O PCC Feeder 2 Feeder 1
Fig. 3. Structure of the conventional droop control method [START_REF] Mahmood | Strategies for Independent Deployment and Autonomous Control of PV and Battery Units in Islanded Microgrids[END_REF].

new v v Z Z b S    (4)
where b is the droop coefficient, S is injected apparent power of the inverter and Zv is the virtual impedance, which is initially zero. The main purpose of this method is to set the impedances in a specific harmonic (main frequency), so that power sharing at all frequencies is automatically performed to minimize the complexity and volume of the calculations. Considering the desired microgrid in this paper (inductive microgrid), virtual impedances should be applied to the inverter as an inductive impedance. The impedance-power droop method is shown in Fig. 4. In this method, after calculating the apparent powers and applying the droop coefficients, the control signal is multiplied in the pulse train so that the duty cycle is established.

Finally, this method is capable of performing accurate active, reactive, and harmonic power sharing with little voltage change and without frequency deviation [START_REF] Razi | An Impedance-Power Droop Method for Accurate Power Sharing in Islanded Resistive Microgrids[END_REF]. However, dependence on the communication link and compromise between speed and accuracy are the disadvantages of this method. In the proposed hybrid method, it is attempted to cover these two disadvantages using the conventional droop method.

IV. PROPOSED HYBRID METHOD

The proposed control method in this paper consists of two control methods described in the previous sections. In the proposed hybrid method, the impedance-power droop method works as the main method in steady state and the conventional droop method is used as auxiliary method during startup and transient states.

As stated earlier, the impedance-power droop method has the capability of sharing the active, reactive and harmonic powers with the lowest deviations of voltage and frequency. In this method, the determination of b was a compromise between accuracy and speed of power sharing. According to the policies of the proposed method in this paper, b is designed in such a way that precision over speed is dominant. In fact, the dynamics of the impedance-power method are optionally slowed to increase the power sharing accuracy on the other hand. Also, the impedance-power droop method is dependent on the low-bandwidth communication link. Therefore, in transient moments or when there is a communication link fault, auxiliary method is needed. Also, the conventional droop control method is not capable of controlling parallel inverters alone due to considerable weaknesses, despite its simplicity and no need for a communication link. Therefore, in the proposed control method, the conventional droop method is not used alone. It should be noted that the conventional droop method shares the active power with good accuracy in the inductive microgrid, even better than the impedance-power method. Therefore, reactive power can be used instead of apparent power in the impedance-power droop method.

In general, the proposed hybrid method, which is shown in Fig. 5, works as follows:

1. At startup, both control methods work in parallel.

Initially, the conventional droop method, which has better dynamics, shares active power with good accuracy. In the following, with a slight delay, the reactive and harmonic power sharing also improve with the proper tuning of the virtual impedances. It should be noted that the parallel application of both methods improves the dynamics of the impedancepower method.

2. When the steady-state of the impedance-power droop method is reached (fixed virtual impedance), the conventional droop method is deactivated. In this case, the power-sharing accuracy does not change, but the frequency deviation is completely eliminated. The voltage deviation is also reduced and can be easily compensated.

3. If the communication link is disconnected, the conventional droop method will be reactivated. In this situation, the impedance-power droop method will not be updated, but the final virtual impedance will help the conventional droop method. In fact, the droop method with improved virtual impedance is active, which enables greater accuracy and lower voltage and frequency deviations than the conventional droop method.

Fig. 4. Impedance-power droop control method [START_REF] Razi | An Impedance-Power Droop Method for Accurate Power Sharing in Islanded Resistive Microgrids[END_REF]. 4. If the network is restructured, the conventional droop method is also activated and after the virtual impedance in the impedance-power droop method is fixed, the conventional droop method is disabled. In fact, when the virtual impedance in the impedancepower droop method is being updated, the conventional droop method will also be active.

S1=F1(vC1, iL1) v C1 i L1 b 1 Z v1 new ΔL1 L v1 if |ΔL1-ΔL2|>x Lv1 new =Lv1+ΔL1 else Lv1 new =Lv1 0 1 sample one TPulse ΔL2 From controller 2 i O Z L1 Load + - v O Z L2 v ref1 v ref2 inv1 inv2 Z v1 new Z v2 new L v1 new i L1 d/dt S2=F2(vC2, iL2) v C2 i L2 b 2 Z v2 new ΔL2 L v2 if |ΔL1-ΔL2|>x Lv2 new =Lv2+ΔL2 else

Hybrid control method

Impedance

Thus, with the implementation of the proposed method, the problems of both methods are covered. This claim will be confirmed in the simulation section.

V. SIMULATION RESULTS

To examine the effectiveness of the proposed method, different cases are simulated in Matlab/Simulink software. For this purpose, the microgrid shown in Fig. 2 is considered with the specification in Table I. This paper assumes that two equal inverters are connected to the PCC with L1 = 2 mH and L2 = 4 mH, respectively, and feed a linear load consists of a resistor (20 Ω) in series with an inductor (20 mH)

A. Case 1: Transient and steady states of the proposed control method

The performance of the proposed control method for this case is shown in Fig. 6. In this study, the system initially starts without any controller for power sharing. Therefore, the active and reactive powers of the first inverter is twice that of the second inverter due to the line impedances. At t = 0.2s, the conventional droop method is activated. By using this method, the active power is shared with high precision but it is not capable of reactive power sharing. It should be noted that the single activation of the conventional droop method is only for comparison with the proposed control method because it is never used alone. At t = 0.5s, the proposed control method is applied by activating the impedance-power droop method. In this transient mode of the proposed control method, the conventional droop method and the impedance-power droop method work in parallel. After about 0.4 seconds, the active and reactive powers are shared with high accuracy and the virtual impedances are fixed. Therefore, the system reaches steady state and after about 0.1 seconds, the conventional droop method is deactivated. As it can be seen, the impedancepower droop method can well maintain the active and reactive power sharing in steady state. In fact, the purpose of applying the conventional droop method was to increase system dynamics. Fig. 6 (d), (e) and (f) show the RMS voltage, voltage frequency and virtual impedances, respectively. The voltage deviation in the steady state is minimized and the frequency deviation is completely eliminated. In addition, virtual impedances have lower values than feeder impedances, which is one of the significant advantages of the impedance- power droop method over the conventional virtual impedance methods. In this case, by adding of Lv1 = 3.277 mH and Lv2 = 1.616 mH, the proper power sharing is achieved in steady state.

B. Case 2: Disconnection of communication link

In this case, the performance of the proposed control method against communication link fault is examined, which is shown in Fig. 7. Initially, the system is in steady state. Then, at t = 0.5s, the communication link will be disconnected. By disconnecting the communication link, the conventional droop method with remained virtual impedance from impedance-power droop method, called improved virtual impedance method, takes control of the system. This method eliminates the problem of link fault, but it causes voltage and frequency deviations, and the active and reactive powers also change slightly. At t = 0.75s, the common linear load increases one and a half times. The improved virtual impedance method can track system changes and proper power sharing is still in place. Finally, at t = 1s, the communication link is reconnected and the impedance-power droop method is activated in steady state. Thus, the proposed control method is robust against communication link fault.

C. Case 3: Change the system structure

As a final study, the rating power change of an inverter is examined. In this case, first the system is in steady state again. At t = 0.5s, the rating of the second inverter is assumed to be one and a half times. As a result of the system restructuring, the conventional droop method is activated in parallel with the impedance-power droop method. Again, there are slight deviations in voltage and frequency, but the proposed method can achieve power sharing in less than 0.2 seconds. After reaching steady state, the conventional droop method will be disabled and the impedance-power droop method will work alone. In fact, the impedance-power droop method in steady state and checking its virtual impedance is required to activate the conventional droop method in transient state. In this case, by adding of Lv1 = 5.049 mH and Lv2 = 1.174 mH, the proper power sharing is achieved in steady state.

VI. CONCLUSION

The active and reactive power sharing in an uncontrolled microgrid depends upon the line and inherent inverter impedances. In this paper, a hybrid control method is proposed for parallel inverters, which consists of conventional droop method and impedance-power droop method. In fact, impedance-power droop controller based on low-bandwidth communication link is used in steady state, which is replaced with an improved conventional droop controller in emergencies. In the proposed hybrid controller, the voltage and frequency deviations of the conventional droop method and the need for a communication link in the impedancepower droop method are solved. Finally, simulation results, which demonstrate various operating cases, confirm the feasibility of the proposed control method.

Fig. 1 .

 1 Fig. 1. Classification of parallel inverters control methods.

Fig. 2 .

 2 Fig. 2. Islanded microgrid with two DGs.

Fig. 5 .

 5 Fig. 5. Structure of the proposed hybrid control method.

Fig. 7 .

 7 Fig. 7. Performance of the proposed control method under case 2. (a) Active powers, (b) Reactive powers, (c) Output voltage and current, (d) RMS voltage, (e) Frequency, (f) Virtual impedances.

Fig. 6 .

 6 Fig. 6. Performance of the proposed control method under case 1. (a) Active powers, (b) Reactive powers, (c) Output voltage and current, (d) RMS voltage, (e) Frequency, (f) Virtual impedances.

Fig. 8 .

 8 Fig. 8. Performance of the proposed control method under case 3. (a) Active powers, (b) Reactive powers, (c) Output voltage and current, (d) RMS voltage, (e) Frequency, (f) Virtual impedances.

TABLE I

 I

		MICROGRID PARAMETERS
	Symbol	Description	Value
	VDC1, VDC2	Nominal DC link voltages	300 V
	L1, L2	Filter inductances	2 mH
	rL1, rL2	Parasitic resistances of inductors	0.2 Ω
	C1, C2	Filter capacitances	20 µF
	ZL1	Line impedance 1	2 mH
	ZL2	Line impedance 2	4 mH
	vo(rms)	RMS voltage of load	220 V
	f	Fundamental frequency	50 Hz
	K	Current controller gain	36.2
	kp	PR controller-proportional gain	0.125
	kih	PR controller-integral gain	15
	ωc	PR controller-cutoff frequency	5 rad/s

-power droop control method + Modified virtual impedance Conventional droop + Impedance-power droop Conventional droop Steady state Transient state Link fault

ACKNOWLEDGMENT

This work has been supported by the m2M-GRID project of the joint programming initiative ERA-Net Smart Grids Plus.


Martin Pesl

Jan Pribyl

Ivana Acimovic

Aleksandra Vilotic

Sarka Jelinkova

Anton Salykin

Alain Lacampagne

Petr Dvorak

Albano C Meli

Petr Skladal

Atomic force microscopy combined with human pluripotent stem cell derived cardiomyocytes for biomechanical sensing

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.