## I Introduction

For a set in dimensions, a quantizer is given by reproduction or quantization points
associated with quantization regions
, defining a partition of .
To measure the quality of a given quantizer, the Euclidean distance between the source samples and reproduction points
is commonly used as the distortion function. We will study quantizers with parameter depending distortion functions
which minimize the average distortion over for a given continuous source sample distribution , as investigated for example in [Erdem16, KJ17, KKSS18] with a fixed set of parameters.
Contrary to a fixed parameter selection, we will assign to each quantization point variable parameters to control the
distortion function of the each quantization point individually. Such controllable distortion functions widens the
scope of quantization theory and allows one to apply quantization techniques to many parameter dependent network and
locational problems.
In this work, we will consider for the distortion function of a Euclidean square-distance, which is
multiplicatively weighted by some and additively weighted by some . Furthermore, we exponentially weight
all distortion functions by some fixed exponent . To minimize the average distortion, the optimal
quantization regions are known to be generalized Voronoi (Möbius) regions, which can be non-convex and disconnected sets
[BWY07].
In many applications, as in sensor or vehicle deployments, the optimal weights and parameters are usually unknown, but
adjustable, and one wishes therefore to optimize the deployment over all admissible parameter values, see for example
[ML].
We will characterize such *quantizers with parameterized distortion measures* over one-dimensional convex target
regions, i.e., over closed intervals. As a motivation, we will demonstrate such a parameter driven quantizer for an
unmanned aerial vehicle (UAV) deployment to provide energy-efficient communication to ground terminals in a given target
region . Here, the parameters relate to the UAVs flight heights.

#### Notation

By we denote the first natural numbers, . We will write real numbers in

by small letters and row vectors by bold letters. The Euclidean norm of

is given by . The open ball in centered at with radius is denoted by . We denote by the complement of the set . The positive real numbers are denoted by . Moreover, for two points , we denote the generated half space between them, which contains , as .## Ii System model

To motivate the concept of parameterized distortion measures, we will investigate the deployment of UAVs positioned at to provide a wireless communication link to ground terminals (GTs) in a given target region . Here, the th UAV’s position, , is given by its ground position , representing the quantization point, and its flight height , representing its distortion parameter. The optimal UAV deployment is then defined by the minimum average communication power (distortion) to serve GTs distributed by a density function in with a minimum given data rate . Hereby, each GT will select the UAV which requires the smallest communication power, resulting in so called generalized Voronoi (quantization) regions of , as used in [Erdem16, GJ, GJcom18, GJ18, KJ17, ML, MLCS, KKSS18]. We also assume that the communication between all users and UAVs is orthogonal, i.e., separated in frequency or time (slotted protocols).

In the recent decade, UAVs with directional antennas have been widely studied in the literature [BJL, MSF, HA, KMR, HSYR, MWMM], to increase the efficiency of wireless links. However, in [BJL, MSF, HA, KMR, HSYR, MWMM], the antenna gain was approximated by a constant within a 3dB beamwidth and set to zero outside. This ignores the strong angle-dependent gain of directional antennas, notably for low-altitude UAVs. To obtain a more realistic model, we will consider an antenna gain which depends on the actual radiation angle from the th UAV at to a GT at , see Fig. (1). To capture the power falloff versus the line-of-sight distance along with the random attenuation and the path-loss, we adopt the following propagation model [Gol05, (2.51)]

(1) |

where is a unitless constant depending on the antenna characteristics, is a reference distance, is the terrestrial path-loss exponent, and

is a Gaussian random variable following

. This air-to-ground or terrestrial path-loss model is widely used for UAV basestations path-loss models [MSBD16a]. Practical values of are between and and depend on the Euclidean distance of GT and UAV(2) |

For common practical measurements, see for example [AG18]. Typically maximal heights for UAVs are m, due to flight zone restrictions of aircrafts. Hence, the received power at UAV can be represented as , where and are the antenna gains of the transmitter and the receiver, respectively. Here, we assume perfect omnidirectional transmitter GT antennas with an isotropic gain and directional receiver UAV antennas. The angle dependent antenna gains are

(3) |

see [Bal05a, p.52]. The combined antenna intensity is then proportional to , see Fig. (1).

Accordingly, the received power can be rewritten as

(4) |

To achieve a reliable communication between GT and UAV with bit-rate at least for a channel bandwidth and noise power density , the Shannon formula requires . The minimum transmission power to UAV is then given by

(5) |

with expectation

(6) |

where the independent and fixed parameters are given by

(7) |

Since our goal is to minimize the average transmission power (6) we define
the th *parameter distortion function* as

(8) |

where and . As can be seen from (8), the distortion is a function of the parameter in addition to the distance between the reproduction point and the represented point . From a quantization point of view, one can start with the distortion function (8) without knowing the UAV power consumption formulas in this section. This is what we will do in the next section. For simplicity, we will set from here on , since it will not affect the quantizer.

## Iii Optimizing Quantizers with parameterized distortion measures

The communication power cost (8) defines, with and fixed , a parameter-dependent
distortion function for . For a given source sample GT density in and UAV deployment, the average
power is the average distortion for given *quantization and parameter points* with quantization sets
, which is called the *average distortion* of the quantizer

(9) |

The quantization sets, which minimize the average distortion for given quantization and parameter points , define a generalized Voronoi tessellation

(10) |

where the *generalized Voronoi regions* are defined as the set of sample points with
smallest distortion to the th quantization point with parameter . Minimizing the *average
distortion* over all parameter and quantization points can be seen as an *facility
locational-parameter optimization problem* [GJ, GJcom18, GJ18, OBSC00]. By the definition of the Voronoi regions
(10), this is equivalent to the minimum average distortion over all level parameter quantizers

(11) |

which we call the *level parameter optimized quantizer*.
To find local extrema of (10) analytically, we will need that the objective function be
continuously differentiable at any point in , i.e., the gradient should exist and be a continuous
function. Such a property was shown to be true for piecewise continuous non-decreasing distortion functions in the
Euclidean metric over [CMB05, Thm.2.2] and weighted Euclidean metric [GJ]. Then the necessary
condition for a local extremum is the vanishing of the gradient at a critical point^{1}^{1}1Note, if is not continuous in than any jump-point is a potential critical point and has to be checked
individually..
First, we will derive the generalized Voronoi regions for convex sets in dimensions for any parameters
for the quantization points , which are special cases of *Möbius diagrams
(tessellations)*, introduced in [BWY07].

###### Lemma 1.

Let for be the quantization points and the associated parameters. Then the average distortion of over all samples in distributed by for some exponent

(12) |

has generalized Voronoi regions , where the dominance regions of quantization point over are given by

(13) |

and center and radii of the balls are given by

(14) |

Here, we introduced the parameter ratio of the th and th quantization point as

(15) |

Remark. It is also possible that two quantization points are equal, but have different parameters. If the parameter ratio is very small or very large, one quantization point can become redundant, i.e., if its optimal quantization set is empty. In fact, if we optimize over all quantizer points, such a case will be excluded, which we will show for one-dimension in Lemma (3).

###### Proof.

The minimization of the distortion functions over defines an assignment rule for a generalized Voronoi diagram where

(16) |

is the th generalized Voronoi region, see for example [OBSC00, Cha.3]. Here we denoted the weights by the positive numbers

(17) |

which define a *Möbius diagram* [BK06b, BWY07]. The bisectors of Möbius diagrams are circles or lines
in as we will show below.
The th Voronoi region is defined by inequalities, which can be written as the intersection of the
*dominance regions* of over , given by

(18) |

If then and , such that , the left half-space between and . For we can rewrite the inequality as

where the center point is given by

(19) |

where we introduced the *parameter ratio* of the th and th quantization point as

(20) |

If , which is equivalent to , then this defines a ball (disc) and for its complement. Hence we get

(21) |

where the radius square is given by

(22) |

The second summand can be written as

(23) |

For any , we have if and else. In both cases (23) is positive, which implies a radius whenever . Inserting (23) in (22) yields the result.

Example 1. We plotted in Fig. (1), for and

, the GT regions for a uniform distribution with UAVs placed on

(24) |

If the second UAV reaches an altitude of , its Voronoi region will be empty and hence become “inactive“.

### Iii-a Local optimality conditions

To find the optimal level parameter quantizer (10), we have to minimize the average distortion
(9) over all possible quantization-parameter points, i.e., we have to solve a non-convex
*facility locational-parameter optimization problem*,

(25) |

where are the Möbius regions given in (13) for each fixed . A point with Möbius diagram is a critical point of (25) if all partial derivatives of are vanishing, i.e., if for each it holds

(26) | ||||

(27) |

For the integral regions will not depend on or and since the integral kernel is continuous differentiable, the partial derivatives will only apply to the integral kernel. For , the conservation-of-mass law, can be used to show that the derivatives of the integral domains will cancel each other out, see also [CMB05].

Remark. The shape of the regions depend on the parameters, which if different for each quantization point (heterogeneous), generate spherical and not polyhedral regions. We will show later, that homogeneous parameter selection with polyhedral regions will be the optimal regions for .

### Iii-B The optimal level parameter quantizer in one-dimension for uniform density

In this section, we discuss the parameter optimized quantizer for a one-dimensional convex source , i.e., for an interval given by some real numbers . Under such circumstances, the quantization points are degenerated to scalars, i.e., . If we shift the interval by an arbitrary , then the average distortion, i.e., the objective function, will not change if we shift all quantization points by the same number . Hence, if we set , we can shift any quantizer for to where without loss of generality. Let us assume a uniform distribution on , i.e. . To derive the unique level parameter optimized quantizer for any , we will first investigate the case .

###### Lemma 2.

Let and . The unique level parameter optimized quantizer with distortion function (8) is given for a uniform source density in by

where is the unique minimizer of

(28) |

which is for fixed a continuous and convex function over . For the minimizer can be derived in closed form as

(29) |

###### Proof.

See Appendix (A).

Remark. The convexity of can be also shown by using extensions of the Hermite-Hadamard inequality [ZC10], which allows to show convexity over any interval. Let us note here that for any fixed parameter , the average distortion is strictly monotone increasing in . Hence, is the unique minimizer for any . We will use this decoupling property repeatedly in the proofs [GWJ18b].

To derive our main result, we need some general properties of the optimal regions.

###### Lemma 3.

Let for some . The level parameter optimized quantizer for a uniform source density in has optimal quantization regions with and optimal quantization points for , i.e., each region is a closed interval with positive measure and centroidal quantization points.

###### Proof.

See Appendix (B).

Remark. Hence, for an level parameter optimized quantizer, all quantization points are used, which is intuitively, since each additional quantization point should reduce the distortion of the quantizer by partitioning the source in non-zero regions.

###### Theorem 1.

Let , for some , and . The *unique level parameter optimized quantizer*
is the uniform scalar quantizer with identical parameter values, given for by

(30) |

with minimum average distortion

(31) |

For , the closed form is provided in (29).

###### Proof.

See Appendix (C).

Example 2. We plot the optimal heights and optimal average distortion for a uniform GT density in over various and in Fig. (3). Note that the factor will play a crucial role for the height and distortion scaling. Moreover, the distortion decreases exponentially in if .

## Iv Llyod-like Algorithms and Simulation Results

In this section, we introduce two Lloyd-like algorithms, Lloyd-A and Lloyd-B, to optimize the quantizer for two-dimensional scenarios. The proposed algorithms iterate between two steps: (1) The reproduction points are optimized through gradient descent while the partitioning is fixed; (ii) The partitioning is optimized while the reproduction points are fixed. In Lloyd-A, all UAVs (or reproduction points) share the common flight height while Lloyd-B allows UAVs at different flight heights.

In what follows, we provide the simulation results over the two-dimensional target region with uniform and non-uniform density functions. The non-uniform density function is a Gaussian mixture of the form , where the weights, , are , , , the means, , are , ,

, the standard deviations,

, are , , and , respectively.To evaluate the performance of the proposed algorithms, we compare them with the average distortion of random deployments (RDs). Figs. ((a)a) and ((b)b), show that the proposed algorithms outperform the random deployment on both uniform and non-uniform distributed target regions. From Fig. ((a)a), one can also find that the distortion achieved by Lloyd-A and Lloyd-B are very close, indicating that the optimality of the common height, as proved for the one-dimensional case in Section (III), might be extended to the two-dimensional case when the density function is uniform. However, one can find a non-negligible gap between Lloyd-A and Lloyd-B in Fig. ((b)b) where the density function is non-uniform. For instance, given UAVs and the path-loss exponent , Lloyd-A’s distortion is while Lloyd-B obtains a smaller distortion, , by placing UAVs at different heights. Figs. ((a)a) and ((b)b) illustrate the UAV ground projections and their partitions on a uniform distributed square region. As the number of UAVs increases, the UAV partitions approximate hexagons which implies that the optimality of congruent partition (Theorem (1)) might be extended to uniformly distributed users for two-dimensional sources. However, the UAV projections in Figs. ((a)a) and ((b)b) show that congruent partition is no longer a necessary condition for the optimal quantizer when distribution is non-uniform.

## V Conclusion

We studied quantizers with parameterized distortion measures for an application to UAV deployments. Instead of using the traditional mean distance square as the distortion, we introduce a distortion function which models the energy consumption of UAVs in dependence of their heights. We derived the unique parameter optimized quantizer – a uniform scalar quantizer with an optimal common parameter – for uniform source density in one-dimensional space. In addition, two Lloyd-like algorithms are designed to minimize the distortion in two-dimensional space. Numerical simulations demonstrate that the common weight property extends to two-dimensional space for a uniform density.

## Appendix A Proof of Lemma (2)

To find the optimal level parameter quantizer for a uniform density , we need to
satisfy (27), i.e., for^{2}^{2}2Note, there is no optimizing over the regions, since there is only
one.

(33) |

Substituting by we get

(34) |

Since the integral kernel is an odd function in

and , it must hold(35) | |||

by substituting by we get | |||

(36) |

Hence for any choice of it must hold , which is equivalent to . To find the optimal parameter, we can just insert into the average distortion

(37) | ||||

where we substituted again and inserted . By substituting with and with we get | ||||

(38) |

where for each the integral kernel is a convex function in over . Let us rewrite as

(39) |

Clearly, is a convex and continuous function in over and since with is a strictly increasing continuous function, the concatenation is a strict convex and continuous function over . Hence, for any we have

(40) |

for all . But then we have also for any and

(41) |

Considering the following inequality

and (41), we will have

(42) |

for every . Hence, the integral kernel is a strictly convex function for every , and since the infinite sum (integral) of convex functions is again a convex function, for , we have shown convexity of . Note, is continuous in since it is a product of the continuous functions and , and so is . Therefore, the only critical point of will be the unique global minimizer

(43) |

which is defined by the vanishing of the first derivative:

(44) |

Hence, can only vanish if , which is an upper bound on . The optimal parameter for minimizing the average distortion (37) is then

(45) |

Analytical solutions for are possible for integer valued . Let us set in (44), then for , the integrand in (44) will be a polynomial in of degree and in of degree . For the integrand will be

(46) | ||||

(47) | ||||

Comments

There are no comments yet.