Printer Friendly

Energy-optimal algorithms for computing aggregative functions in random networks.

We investigate a family of algorithms minimizing energetic effort in random networks computing aggregative functions. In contrast to previously considered models, our results minimize maximal energetic effort over all stations instead of the average usage of energy. Such approach seems to be much more suitable for some kinds of networks, in particular ad hoc radio networks, wherein we need all stations functioning and replacing batteries after the deployment is not feasible. We analyze also the latency of proposed energy-optimal algorithms.

We model a network by placing randomly and independently n points in a d-dimensional cube of side-length [n.sup.1/d]. We place an edge between vertices that interact with each other. We analyze properties of the resulting graphs in order to obtain estimates on energetic effort and latency of proposed algorithms.

Keywords: random network, k-NNG, energy-efficiency

1 Introduction

In this paper we consider the problem of computing a function of distributed data in a specific node of the network. More precisely, each node of the network has some value and a function of a collected raw data is required at some specific node called root (Note that the investigated problem can be in some sense "inverted" - we can think of dissemination of information with the single origin at the root).

The system we have in mind is a large network of sensing nodes communicating by a radio channel. Typically such system is deployed in order to work for a very long time and one of its aims is to detect some dangers like fire or flood. All nodes are battery-supplied and their batteries cannot be easily replaced. In such a scenario some data (e.g. the average temperature over all nodes) has to be possibly quickly delivered to some specific point. One of the problems is that the cost of transmitting a message is a superlinear function of the range of transmission. Thus, from the energy-saving point of view, it is better to transmit a message over a longer distance via a sequence of intermediate nodes. This, however, leads to lengthening the time of message delivery.

Another problem in the considered model is caused by peculiarities of radio communication - each station can successfully receive at most one message at the same time. That is, if two or more nodes in the range of a particular potential receiver transmit, then none of the messages can be assumed to be correctly received. Such situation is called collision. For that reason some naive solutions like "flooding" are completely inadequate. Thus we have to deal with an optimization problem where some energy usage/time of computation are solicited under strict constraints that are present in the model.

In our paper we assume that nodes are placed randomly in the region and can control the range of their transmission, however, the energetic effort of each transmission is superlinear with its range. Thus the investigated problem and obtained results may be seen as a counterpart of the paper Balister et al's. [2] for a modified model. The first fundamental difference is that we assume that a transmitted message is received by all stations in the range of transmission (provided that only one station in the range of the receiver transmits). That is, the transmission affects all stations in some "ball" with the transmitting station at its center. Such asumption is realistic in significant number of real-life scenarios, whenever omnidirectional antennas are used. One can note that to by-pass such problem the so-called orthogonal codes can be used. We argue, however, that this is quite difficult in the systems of a very constrained devices, especially in dense networks whenever we need to handle frequent, multiple collisions.

The second fundamental difference when compared to [2] is that as the metric of energetic complexity we use the maximal energetic effort over all stations instead of the total (or average) energetic effort. Such approach seems to be more adequate in the case of long-lasting battery-supplied nodes, since for proper functioning of the system we often need all stations working. Such energy metric is commonly used for example in [15, 12] . We do not claim that our model is better or more realistic in general. Nevertheless, it seems to be more adequate for some real systems.

Despite similarities to [2], our approach leads to completely different construction of protocols. Moreover, in many cases analysis of new algorithms is substantially different. Even though we use very often similar mathematical tools, to the best of our knowledge, the results from [2] cannot be transferred to our model in any obvious manner.

Similarly to most of previous papers (including [2]) we restrict our attention to some class of functions (that are to be computed at the root) called aggregative functions ([22]). Roughly speaking, they should be associative, commutative and the length of the result should be comparable to maximal length of all inputs (e.g. the sum, the maximum). Nevertheless, the class of functions that fits to our framework is even richer.

The primary motivation for our research are sensor networks (with particular focus on ad hoc systems). Nevertheless, we believe that it can be applied for other distributed systems composed of devices with constrained energy resources.

1.1 Previous and Related Work

Our paper can be seen as a counterpart of [2] wherein authors also investigate an energy/latency trade-off for network built on top of a random graph. The difference comparing to [2] is a substantially different definition of energy-efficiency and a modified communication model that takes into account collisions of transmissions.

There is a well--developed body of research on other data processing in sensor networks. In [6] Giridhar and Kumar presented a general framework for in-network computation of some classes of functions and analyzed scaling property of capacity as the network size grows. There are also a few papers considering trade-offs between energy and latency - [17, 31, 28, 19] and significant number of papers focused on aggregative functions in sensor networks. An extensive survey can be found in [23] and a few latest results are given in [14].

Our result is also similar to [4] wherein authors investigate MST-building problem in similar network of randomly placed stations. They present a lower bound [ohm](log(n)) for energy and an optimal algorithm (in expectation). We should also mention [30], wherein energy scaling laws in randomly placed networks for routing are considered. Another recent paper considering latency/energy trade off is [16] wherein authors consider SINR communication model and assume that stations can be arbitrarily placed.

Despite all papers mentioned above are more or less similar to ours, to the best of our knowledge the results presented here cannot be transfered to previous work in any straightforward manner. The main reason are different metrics (e.g. a sum of energies of all stations is taken into account in energy-efficiency definition of other papers) and different communication model. This leads to substantially different analysis. References to some other works loosely connected to our results can be found in [2].

In our paper we use some technical tools regarding random structures described in [27, 3, 24, 25]. We extensively use properties of k - NNG (k-Nearest Neighbor Graphs), the graphs constructed by joining each station to its k nearest neighbors (see [3]).

Let us also remind that we use the maximal expenditure of energy over all stations as a general metrics of energetic efficiency of the given algorithm. Such approach is not new and has been used in many previous papers (e.g. [15, 13, 12]).

1.2 Results and Organization of the Paper

The paper is organized as follows. In Section 2, we introduce basic definitions, notation and a formal model of the network. In Section 3, we discuss the connectivity of the so-called k-Nearest-Neighbor-Graph in our model and explain its relation to algorithms that minimize energetic effort. Then we define the family of algorithms that compute aggregative function at the root transmitting data along the edges of a k-Nearest-Neighbor-Graph for carefully chosen k. We also show that their energy consumption is of the order [theta]([log.sup.v/d] (n)), where n is the number of stations placed in a d-dimensional cube of volume n, and [nu] is the so-called path loss exponent. We show also that energy [ohm]([log.sup.v/d] (n)) is necessary, thus the presented algorithms are energy-optimal.

In Section 4 we present a lower bound for latency of energy-optimal algorithms [ohm] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then we present an asymptotically energy-optimal algorithm and investigate its latency. We show that its latency is optimal up to a polylogarithmic factor. Some of our numerical experiments confirming theoretical results are presented in Section 5. In Section 6, we briefly summarize our results and state a few open questions.

2 Model

2.1 Communication and Propagation Model

We consider the problem of computing a function (which depends on the measurements of all the nodes) at the root of a wireless network. All the nodes are treated as random points in Euclidean space. The algorithm is executed in rounds and stations are synchronized as they have access to a global clock. In a single round every single station can either transmit or listen. If the transmission range of the node is r, then the signal reaches all nodes at the distance at most r. In a single round a station successfully receives a message if it is in a listening mode and if it is covered by the transmission range of exactly one transmitting station. Station cannot transmit and receive any message in the same round. Note that the aforementioned assumptions seem to be adequate for example for some ad hoc radio networks with omnidirectional antennas.

2.2 Network Model

Significant part of the model as well as the notation is exactly like in [2]. More precisely, let d be a natural, positive number. Let [Q.sub.n] = [[0, [n.sup.1/d]].sup.d] [subset] [R.sup.d] be a d-dimensional hypercube of volume n. (Despite throughout this paper we concentrate on the realistic cases d = 2 and d = 3, some calculations are conducted in general for d [greater than or equal to] 1.) We have n stations placed randomly and independently in [Q.sub.n]. Let [V.sub.n] = {[V.sub.1],..., [V.sub.n]} be the set of their locations (with station i located at [V.sub.i] [member of] [R.sup.d]). Let also [Y.sub.n] = {[Y.sub.1],..., [Y.sub.n]} be the set of their local values (station i keeps Yi [member of] y, where y is some set). In practice such value can be a measurement of a sensing device.

The root node, where finally our function of measurements has to be computed, will be denoted by r (located at [V.sub.r] [member of] [V.sub.n]). The desirable function of values will be denoted by [PSI] = [PSI]([Y.sub.n]).

2.3 Metrics

In the analysis of protocols we consider two metrics: latency and energy. While constructing a protocol one usually aims at minimizing one of them or finding some reasonable trade-off. Let [pi] be the policy (algorithm) that we consider.

Energy of transmission between i-th and j-th sensor is defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where e = {[V.sub.i], [V.sub.j]}, [R.sub.e] = ||[V.sub.i] - [V.sub.j]|| is the Euclidean distance between [V.sub.i] and [V.sub.j] and [nu] is a path loss exponent - usually one assumes that for sensor networks [nu] [member of] [2, 6] or just [nu] = 2 (e.g. [8]). However, we allow any [nu] [greater than or equal to] 1.

We assume that the energetic cost of transmitting a message does not depend on its size. Such assumption is realistic for computing aggregative functions. ([22])

Energetic effort of a single station is the sum of energies spent on all its transmissions during the execution of the protocol.

Latency is the number of rounds necessary to complete the algorithm (i.e., the minimal number of rounds after which [PSI] is computable at the root). Formally we can define latency of [pi] by

[L.sup.[pi]] = inf{t : [PSI]([Y.sub.n]) is computable at r at time t}.

Here we consider a single shot function computation. Consequently, the scheme of communication is a fixed one.

We define energy by the maximal energetic effort over all stations. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (a communication graph of [pi]) denote the set of links used for inter-node communication by the policy [pi]. Then the energy of [pi] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [f.sub.e] is the number of transmissions that take place along the edge e during the protocol. As we already mentioned in Introduction, our metrics of energy usage is different from the one presented in [2]. Indeed, in [2] the total energy consumption of all nodes is considered. Note that in the latter case one does not care about the energetic effort of a single station (which is in practice bounded by the power of its battery). Therefore we find our approach (considering maximal energy usage over all stations) much more suitable for some kinds of networks (in particular, radio networks, wherein we need all stations functioning and replacing batteries after the deployment is not feasible).

2.4 Function Computation Model

The aim of the protocol is to compute a function [PSI] at the root, provided that it requires inputs kept by all the nodes in the network. Note that if no other assumptions are made on [PSI], then all the nodes need to deliver their measurements to the root without any in-network computation. Since typically the functions required in various network applications are of a specific kind (e.g. sum, minimum, maximium, etc.) we restrict our problem to the class of aggregative functions. As we already said in Introduction, an aggregative function is associative, comutative and the length of its result is comparable to the maximal length of any input. Without loss of generality we may assume that [PSI] is of a form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Clearly, with such assumptions in every algorithm it is enough that each node transmits exactly once.

2.5 Energy-optimal algorithm

Our aim is to find and analyze an energy-optimal algorithm ensuring that an aggregative function [PSI] of measurements is computable at the root r when the algorithm terminates. Let F([PSI]) be the set of valid aggregation policies, i.e.,

F([PSI]) = {[pi] : [PSI]([Y.sub.n]) is computable at r}.

The energy-optimal algorithm [pi]* will be the one that minimizes E[[E.sup.[pi]]] over the set of valid policies F([PSI]), i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the expectation is over the locations [V.sub.n] of n nodes placed randomly and independently in [Q.sub.n].

3 Optimal Algorithm Minimizing Energy Consumption

In this section we analyze the energy usage of an energy-optimal algorithm. Its latency is discussed in the next section. Our aim is to find a policy that minimizes the expectation of the energy understood as described in Section 2. Therefore we are going to analyze the algorithms in which each node transmits exactly once (thus for each edge e we have [f.sub.e] = 1 in formulas above). More precisely, we need to indicate a policy [pi] with a graph of communication [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that minimizes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

over the set of valid policies F([PSI]). This value will be called energetic complexity.

Note that if each node transmits exactly once during the protocol we do not need to know the [pi] itself to derive the above value. It is enough to know its communication graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Throughout the rest of this section we are going to restrict our considerations to the family of k-Nearest-Neighbor-Graphs (k-NNG). We construct such a graph by joining each station to its k nearest neighbors. (For the definition and basic properties see e.g. [3].) Below we briefly explain that we do not lose generality considering only this family.

Of course, G[pi] needs to be connected if we want to complete the algorithm successfully. It turns out that the threshold for connectivity of k-NNG for d = 2, 3 (in terms of k) is of the order [theta](log n). The proof that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [square root of (3/3)] [less than or equal to] [delta] [less than or equal to] 1, is in the second dimension connected w.h.p. may be found later as a part of the proof of Lemma 5 (analogous calculations may be conducted for d = 3). In this Section we prove that the expected length of the longest edge in [[xi].sub.n]-NNG is of the order [theta]([log.sup.1/d] (n)). By Lemma 6 from Appendix B we get that it is optimal result for d = 2,3 among the graphs on n vertices which are connected w.h.p. Therefore w.l.o.g. we may consider only the family of k-NNG with k = |C log n] where C is chosen such that it guarantees connectivity w.h.p.

3.1 Minimizing energetic complexity

Let [[xi].sub.n] = [Clogn], where C is a constant chosen such that [[xi].sub.n]-NNG is connected w.h.p. W.l.o.g. let us assume that C [greater than or equal to] 1. Having a connected communication graph we can always construct a naive, yet energy-efficient protocol for computing [PSI] at the root. That is, we can subsequently send values to the root using any spanner. Now, we are going to analyze the energetic complexity of the algorithms whose communication graph is [[xi].sub.n]-NNG and in which each node transmits exactly once.

Theorem 1 Let [K.sub.n] be a [[xi].sub.n]-NNG. For d = 2, 3 and [nu] > 1 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: Let us fix w [member of] [R.sup.d]. Let [x.sub.1], [x.sub.2],... , [x.sub.n-1] be chosen randomly and independently from [Q.sub.n] and ordered such that [||w - [x.sub.1]||.sup.[nu]] [less than or equal to] [||w - [x.sub.2]||.sup.[nu]] [less than or equal to]... [less than or equal to] [||w - [x.sub.n-1]||.sup.[nu]]. Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

By diamQ we denote the diameter of [Q.sub.n]. Integrating by parts we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [B.sub.r] be the ball of radius r centered at the root. Let [V.sub.r] = [B.sub.r] [intersection] [Q.sub.n] and |[V.sub.r]| be its volume. Obviously, |[V.sub.r] | [less than or equal to] c[r.sup.d] for some positive constant c since it is at most the volume of a d-dimensional sphere of radius r. Let also [X.sub.r] be the number of sensors in [V.sub.r]. Clearly, [X.sub.r] has a binomial distribution with parameters n and |[V.sub.r]|/n. In particular E[[X.sub.r]] = |[V.sub.r]|.

Note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Substituting this formula into above equation we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [epsilon] be such that [5/6c] < [epsilon] < [1/c] and [y.sub.n] = [(1/c - [epsilon]).sup.1/d][(log n).sup.1/d]. Recall that C [greater than or equal to] 1. We have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

One can calculate in a straightforward manner

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Clearly, to complete the proof of Theorem 1 it is sufficient to show that the second integral of (2) tends to 0 with n tending to infinity. One can easily check that for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the assumed [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we have log n [greater than or equal to] 6 * E[X.sub.r] whenever r [less than or equal to] [y.sub.n] . Thus, using one of Chernoff's inequalities (see Fact 2 in Appendix A) we get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all r [member of] [0, [y.sub.n]]. Therefore we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Recalling equality (1) we finally obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 2 Let [K.sub.n] be a [[xi].sub.n]-NNG. For d = 2, 3 and [nu] [greater than or equal to]1we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof:

Recall that [[xi].sub.n] = |C log n|. Let again [V.sub.r] = [B.sub.r] [intersection] [Q.sub.n], where [B.sub.r] is the ball of radius r centered at the root and |[V.sub.r] | the volume of [V.sub.r]. Recall that |[V.sub.r] | < c[r.sup.d] for some constant c. We also have |[V.sub.r] | [greater than or equal to] c[r.sup.d] for some constant c (see proof of Lemma 2 in [2]) (i). Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [y.sub.n] = [(1/c + [epsilon]).sup.1/d][(log n).sup.1/d]. As in the proof of Theorem 1 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let us now investigate the second integral of (3). We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The first inequality follows from the Chernoff bound (see Fact 3 in Appendix A) by substituting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [EPSILON][[X.sub.r] ] = |Vr |. For correctness of aforementioned reformulations we need to prove that 0 [less than or equal to] [delta] [less than or equal to] 1. Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since we consider only r > [y.sub.n]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since we assumed [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we get [delta] > 0. On the other hand

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

To complete the proof of Theorem 2 it is enough to show that the integral (*) is of the order O[((log(n)).sup.[nu]/d]). Substituting [x.sub.2] = [r.sup.d] we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

where [K.sub.[alpha]](z) is the Bessel function of the 2nd kind (described e.g. in [26]). Moreover, from [1] or [26] one can get that for all [alpha] > 0

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Applying this to (4) we finally get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] []

From Theorems 1 and 2 we instantly get the following corollary:

Corollary 1 Any algorithm from F([PSI]) in which each node transmits at most constant number of times and which has a communication graph [K.sub.n] = [[xi].sub.n]-NNG has asymptotically optimal energetic complexity equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for d = 2, 3 and [nu] [greater than or equal to] 1.

The set of algorithms from F([PSI]) in which each node transmits at most constant number of times and which have a communication graph [K.sub.n] = [[xi].sub.n]-NNG will be denoted by [F.sub.Kn] ([Y.sub.n]).

4 Latency of algorithms from [Q.sub.Kn]([Y.sub.n])

In this section we analyze the expected latency of the energy-optimal algorithms from [O.sub.Kn] ([Y.sub.n]). Recall that latency is the number of rounds that we need to complete the algorithm, i.e., the minimal number of rounds after which the function [PSI] is computable at the root. First, we show a lower bound [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for the latency for every algorithm from [G.sub.Kn](Yn). Then we present a simple protocol from [G.sub.Kn]([Y.sub.n]) and prove that it is close to optimal and has latency [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let us divide the set of vertices of our communication graph [[xi].sub.n]-NNG into disjoint layers. Let [S.sub.0] be the set containing only the root. The set [S.sub.i+1] for i [greater than or equal to] 0 is defined as the set of all nodes having neighbors in [S.sub.i] and not being included in any of the previous layers. Moreover, let S be the number of the last nonempty layer. Clearly, the i-th layer [S.sub.i] contains all sensors that are at edge distance equal to i from the root (by the edge distance between two vertices we understand the number of edges of the shortest path joining them). The root itself is a layer number 0, all neighbors of the root form the first layer, and so on.

Let L be the latency of the fastest algorithm from [G.sub.Kn] ([Y.sub.n]). Note that L [greater than or equal to] S, since we need at least S rounds to pass the information from the last layer to the root.

4.1 Lower bound

Before we prove the lower bound let us state two lemmas.

Lemma 1 Let [K.sub.n] be a [[xi].sub.n]-NNG. For d = 2, 3 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: The proof comes directly from Corollary 1, Jensen's inequality and the convexity of the function 1/x on (0, [infinity]). []

Lemma 2 W.h.p. at least half of stations are placed at the distance at least 1/5[n.sup.1/d] from the root.

Remark. In the above lemma any constant from the interval (0,1/4) instead of 1/5 would work as well. We chose 1/5 as the first convenient for further calculations constant smaller than 1/4.

Proof: See Appendix B.[]

Now, let us move on to the lower bound for the expectation of latency of any algorithm from [Q.sub.Kn] ([Y.sub.n]).

Theorem 3 For L being the random variable denoting latency of any algorithm from [G.sub.Kn]([Y.sub.n]) and for d = 2, 3

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: Recall that S is the random variable denoting the number of disjoint layers in [[xi].sub.n]-NNG ([K.sub.n]). Let us recall that L [greater than or equal to] S. Let us choose arbitrary vertex v from the last, S-th layer. Recall that r is the root. By Lemma 2 we know that w.h.p. at least half of vertices lie at distance at least [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from the root. Therefore w.h.p.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let us choose any path (r = [v.sub.0], [v.sub.1], [v.sub.2],... , [v.sub.S-1],[v.sub.S] = v) such that [v.sub.i] belongs to the ith layer for any 0 [less than or equal to] i [less than or equal to] S . Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the length of our path. Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

On the other hand w.h.p.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(Note that [max.sub.e[member of]][K.sub.n] [R.sub.e] = 0 with probability 1.) Therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By Lemma 1 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus finally we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] []

4.2 Upper bound

In the rest of this section we present an energy-optimal algorithm from [G.sub.Kn] ([Y.sub.n]) and analyze its latency. The following lemma will be helpful later on.

Lemma 3 [V.sub.n] is the set of vertices of [[xi].sub.n]-NNG. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: By the definition of [[xi].sub.n]-NNG we have deg(v) [greater than or equal to] [Clogn] for all v and this instantly follows E[max.sub.e[member of]] deg(v)] = [omega](logn).

Now, let v be the vertex that maximizes the value deg(v) over the set of [V.sub.n]. Let [GAMMA](v) denote the neighborhood of v. Let also R = [max.sub.e[member of]][GAMMA](v) ||[V.sub.w] - [V.sub.v]||. By Theorem 2 there exists a constant a such that R [less than or equal to] a(logn)1/d. Let VR = BR[intersection][Q.sub.n], where BR is the ball of radius R centered at the vertex v. Let, as in the proof of Theorem 1, XR be the number of stations in VR. Recall that XR has a binomial distribution with parameters n and |VR|/n ( |VR| is the volume of VR and |VR| < cRd for some constant c ). Note that deg(v) [less than or equal to] XR thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Algorithm description The idea of the algorithm is to schedule transmission of all stations layer by layer in such a way that the aggregated messages are finally de[l.sub.i]vered to [S.sub.0] (which contains only the root). The problem is that the message cannot be transmitted by all stations in a single layer during the same round since it leads to col[l.sub.i]sons and failed communication. For that reason we need to apply more advanced schedu[l.sub.i]ng avoiding col[l.sub.i]sons.

Let us label all vertices of [S.sub.i] by unique numbers from the set {1, 2,..., |[S.sub.i]|} in an arbitrary way. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the j-th node in the [S.sub.i]. For each 1 [less than or equal to] i [less than or equal to] S we need to partition the set [S.sub.i] = [union]... [union] [S.sub.i]. I.e., [S.sub.i] for j = 1,..., [l.sub.i] are pairwise disjoint and nonempty.

Let us recall that [GAMMA](v) denotes the set of all neighbors of the vertex v and let [GAMMA](V) = [GAMMA](v). Following algorithm is executed for each layer. We construct S,..., [S.sub.i]i applying sequentially following algorithms for partition of the layer i.
Algorithm 1 Layer partition algorithm (for the i-th layer)

for j = 1 to |[S.sub.i]| do
   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
end for
for k = 1,..., |[S.sub.i]| do
   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
end for
   [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]


The algorithm for transmitting is based on layer partitions defined by the Algorithm 1. It consists of S phases executed consecutively from i = S to 1. In the i-th phase we expect that all the stations from layer i will transmit their (possibly aggregated) message to their neighbors in the (i - 1)-st layer. Finally, all messages are de[l.sub.i]vered to the root in the layer So. Pseudocode for the j -th round (1 [less than or equal to] j [less than or equal to] [l.sub.i]) is described below (in Algorithm 2).
Algorithm 2 Algorithm for data transmission

for i = S to 1 do
 for j = 1 to [l.sub.i] do
  All [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
   transmit
  All [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
   listen to the channel and aggregate received data
 end for
end for


Analysis

Lemma 4 In Algorithms 1 and 2

1. each station transmits exactly once;

2. all the transmissions are correctly received;

3. for each 1 [less than or equal to] i [less than or equal to] S the number of rounds in the i-th phase satisfies [l.sub.i] = O(log n).

Proof: The first point follows instantly from the construction of the partition.

To obtain the second point it is enough to see that two nodes can transmit in the same round if and only if they are both from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. However (by the construction of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) nodes from Si cannot have a common neighbor.

The third point is the consequence of the following observation. A node v is assigned to some [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if and only if in each subset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] there is already at least one node from [GAMMA](v) or from [GAMMA]([GAMMA](v)). Since |[GAMMA](v)| = O(log n) (see Lemma 3) we have [GAMMA]([GAMMA](v)) = O((logn)2) and therefore [l.sub.i] = O(log n). []

Let us investigate the upper bound for the number of layers S.

Lemma 5 For S being the random variable denoting the number of disjoint layers in [[xi].sub.n]-NNG (Kn) and for d = 2, 3 w.h.p.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Remark. The proof presented below covers more than just a statement of the above lemma. Namely, in the same way one may prove that [[xi].sub.n]-NNG for [[xi].sub.n] = [(1 + [delta])9(Ylog(n)+O(1))2], where 3/3 [less than or equal to][delta][less than or equal to]1 is connected w.h.p. The proof follows partially the arguments from [3] for connectivity of k-NNG in the Poisson model.

Proof: Here we present the proof for d = 2. For d = 3 the calculations are analogous.

Let us partition the square [Q.sub.n] into small squares Pi of area [theta](logn) such that the side-length of Pi divides the side-length of [Q.sub.n] (1 [less than or equal to] i [less than or equal to] [m.sub.n] = [theta](n/ log n)). The probabi[l.sub.i]ty that there are no stations in a single Pi is of the order ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) . Thus the order of the probabi[l.sub.i]ty that there is at least one station in each Pi is at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus w.h.p. there is at least one station in each Pi.

Now, let X denote the number of stations in P, a square formed from 9 adjacent Pi's. Clearly, EX = 9(logn - O(1)). Throughout this paper we work with [[xi].sub.n] that ensures connectivity of [[xi].sub.n]-NNG w.h.p. Setting

[[xi].sub.n] = [(1 + [delta])9( v log(n) + O(1)) ],

where 3/3 [less than or equal to] [delta] [less than or equal to] 1 is a proper choice (which is substantiated below). Applying Chernoff bounds (see Fact 4 in Appendix A) we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus the probabi[l.sub.i]ty that in each such square (of area 9(logn - O(1))) there are less than [[xi].sub.n] stations is of the order at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus w.h.p. every station contained in [P.sub.i] is joined to every other station in [P.sub.i] and to every other station from any of 8 squares adjacent to [P.sub.i] (note that also each station from any "boundary" square is joined to every other station from any of its adjacent "inner" square). This is enough to make [[xi].sub.n]-NNG connected w.h.p. and to prove that S is w.h.p. of the order at most O[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] []

Theorem 4 For L being the random variable denoting latency of the algorithm [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and for d = 2, 3

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: Clearly, L [less than or equal to] S * T, where T is the maximal (over indices i = S,..., 1) number of rounds necessary to transmit signals from all stations from [S.sub.i] to their neighbors in [S.sub.i-1]. Clearly, from Lemma 4, T = [theta](log (n)).

By Lemma 5 we know that w.h.p.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which together with T = [theta](log (n)) implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Remark This algorithm is also efficient in the model wherein the energetic complexity is measured by the number of rounds during which the nodes listen to the channel. Indeed, each station listens during at most [theta](log n) rounds. Detailed analysis is, however, beyond the scope of this paper.

Remark In our paper we concentrated on aggregative functions in the sense explained for example in [22] (associative, commutative, with short representation for any number of arguments). However some of our considerations can be applied for holistic functions ([7]) that cannot be computed in a distributed manner (e.g., quantiles over values hold by individual nodes).

In principle applicability of our algorithm to computing such functions depends on several factors. First, our analysis and algorithms do not change if the energy and time spent for communication do not depend on the size of the message. Such assumption is justified in case of system wherein the messages have to be long enough to be sent due to technical requirements.

In another natural scenario, when the energy is proportional to the length of the message it is easy to see that the problem is harder, thus all our lower bounds hold also for the problem of computing holistic functions. The situation is more complex when we try to investigate efficient protocols. One can note that the complexity of the problem depends on the nature of the function to be computed. In the most difficult case we need to have all arguments delivered to a single node wherein the final computations are performed. Clearly in this case we can utilize our algorithm by sending all messages independently. This can increase the energy by at most factor n. In some graphs latency can be of order [theta](n) as well. However finding an average case for random placement of nodes seems to be nontrivial.

[FIGURE 5 OMITTED]

5 Experimental Results

We have performed a number of experiments to confirm our theoretical results. All obtained results are consistent with our theoretical analysis. Moreover, in some cases the constants hidden in the asymptotic notation are much better than expected even for very small sizes of the network (e.g., 50 nodes). Below we present some chosen experimental results to depict the general tendency. We limited our discussion to dimensions d = 2, 3 that seem to be most important for real life networks.

Connectivity

It has been proved that k = C log n is the theshold for connectivity of k-NNG graphs. Our experiments show that already the small values of C are sufficient to have a connected graph w.h.p. (In fact k = ln n was always sufficient.) In each of the experiments presented in figures 1a,1b,1c, we generated at least 10000 instances of graphs and checked their connectivity.

Energetic Complexity

We have also performed some experiments to investigate the energetic complexity. We have limited our experimental research to the case v = 1. In figure 2 we show frequency histograms of energetic complexity for small and moderate network. Note that the results are close to expected (log n)1/2. A very good concentration of the energy around its mean is worth to underlining.

Latency

We have also performed numerical experiments to check the latency of the algorithm. Some chosen results are presented in Figure 3.

Again, all results correspond well to the formal analysis.

[FIGURE 2 OMITTED]

6 Remarks and open questions

Throughout this paper we assumed that the root was placed randomly. This may not be true in some real-life scenarios. However, let us note that one can easily see that the root in fact can be placed in any fixed point without significant changes of the analysis and the result (we would need at most one extra round for getting to the root node, since other nodes are densely placed over [Q.sub.n] w.h.p.).

The model presented in our paper assumes that the sent signal can be heard within a certain range, moreover that the signal collision always causes the message loss. In some cases however SINR model is more realistic. In SINR model the signal is successfully received by a receiver v if the ratio of signal strength at v and the combined interference from other transmitters along with ambient noise exceeds v's antenna gain.

Clearly, our analysis cannot be simply applied to SINR model. It would need more elaborated discussion about the realistic assumptions with respect to the strength of the signal and its relation to energy that is spent. This is particularly important for establishing any non-trivial lower bounds. Some papers show that the characteristics of SINR model may differ significantly from that obtained by using graph-based models (e.g. for capacity, connectivity and minimizing the scheduling complexity characteristics of SINR, see [19, 20]). Since in SINR model receiver may recover the signals from multiple simultaneous senders, we should expect that it will lead to much reduced latency but increased energy effort (clearly, the best algorithm for SINR model cannot be worse in any reasonable model). Another issue that prevents us from using methods from this paper is the non-locality of SINR model. Nevertheless discussing SINR model in the context of latency and maximal energetic effort seems to be very natural direction of research. We would expect that the approach from the paper [16] (in which energy-latency trade-off in SINR model is considered, but the metric of energetic complexity is taken to be the average energetic effort) can be a promising starting point.

We have assumed also that we need to gather the values from all stations to compute the aggregative function at the root. One may consider a relaxed version of this problem, when already [delta] * n (for some 0 < [delta] < 1) values collected at the root are sufficient (e.g. to find a good estimator of temperature). It seems that the optimal algorithm can be much faster and less energy consuming then in the model considered in our paper.

[FIGURE 3 OMITTED]

Another interesting open question is, how the parameters of the algorithm would improve if the stations could move by not more than some previously fixed distance [epsilon]. One may also ask, how the family of energy-optimal algorithms would substantially change if the length of the message was taken into consideration (e.g. if we payed for each single transmitted bit).

These questions are left as a future work.

References

[1] Milton Abramowitz and Irene Stegun. 1964. Handbook of Mathematical Functions (fifth ed.). Dover.

[2] Paul Balister, Bela Bollobas, Animashree Anandkumar, and Alan S. Willsky. 2011. Energy-latency tradeoff for in-network function computation in random networks. In INFOCOM. IEEE, 1575-1583.

[3] Paul Balister, Bela Bollobas, Amites Sarkar, and Mark Walters. 2005. Connectivity of random k-nearestneighbor graphs. Adv. in Appl. Probab. 37 (2005), 1-24.

[4] Yongwook Choi, Maleq Khan, V.S. Anil Kumar, and Gopal Pandurangan. 2008. Energy-optimal Distributed Algorithms for Minimum Spanning Trees. In Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures (SPAA '08). ACM, New York, NY, USA, 188-190. DOI:http://dx.doi.org/10.1145/1378533.1378569

[5] Grigorii Mikhailovich Fichtenholz. 1965. The fundamentals of mathematical analysis. Pergamon Press, Oxford.

[6] Arvind Giridhar and P. R. Kumar. 2005. Computing and communicating functions over sensor networks. IEEE Journal on Selected Areas in Communications 23, 4 (2005), 755-764.

[7] Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, and Hamid Pirahesh. 1997. Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals. Data Min. Knowl. Discov. 1, 1 (1997), 29-53. DOI:http://dx.doi.org/10.1023/A:1009726021843

[8] Wendi B. Heinzelman, Anantha P. Chandrakasan, and Hari Balakrishnan. 2002. An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications 1, 4 (2002), 660-670.

[9] Wassily Hoeffding. 1963. Probability Inequalities for Sums of Bounded Random Variables. J. Amer. Statist. Assoc. 58, 301 (1963), 13-30.

[10] Oscar H. Ibarra and Louxin Zhang (Eds.). 2002. Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings. Lecture Notes in Computer Science, Vol. 2387. Springer.

[11] INFOCOM2006 2006. INFOCOM 2006. 25th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 23-29 April 2006, Barcelona, Catalunya, Spain. IEEE. http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4146652

[12] Tomasz Jurdzinski, MirosLaw KutyLowski, and Jan Zatopianski. 2002. Energy-Efficient Size Approximation of Radio Networks with No Collision Detection, See [10], 279-289.

[13] Tomasz Jurdzinski, MirosLaw KutyLowski, and Jan Zatopianski. 2003. Weak communication in single-hop radio networks: adjusting algorithms to industrial standards. Concurrency and Computation: Practice and Experience 15, 11-12 (2003), 1117-1131.

[14] Marek Klonowski, MichaL Koza, and MirosLaw KutyLowski. 2013. Efficient and robust data aggregation using untrusted infrastructure. In SIN. Atilla Elc,i, Manoj Singh Gaur, Mehmet A. Orgun, and Oleg B. Makarevich (Eds.). ACM, 123-130.

[15] Marek Klonowski, MirosLaw KutyLowski, and Jan Zatopianski. 2012. Energy efficient alert in single-hop networks of extremely weak devices. Theor. Comput. Sci. 453 (2012), 65-74.

[16] Hongxing Li, Chuan Wu, Dongxiao Yu, Qiang-Sheng Hua, and Francis C. M. Lau. 2013. Aggregation Latency-Energy Tradeoff in Wireless Sensor Networks with Successive Interference Cancellation. IEEE Trans. Parallel Distrib. Syst. 24, 11 (2013), 2160-2170.

[17] Stephanie Lindsey, Cauligi Raghavendra, and Krishna Sivalingam. 2001. Data Gathering in Sensor Networks using the Energy*Delay Metric. In In Proc. of IPDPS Workshop on Issues in Wireless Networks and Mobile Computing. IEEE Computer Society, San Fransisco, USA, 924-935.

[18] Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.

[19] Thomas Moscibroda and Roger Wattenhofer. 2006. The Complexity of Connectivity in Wireless Networks, See

[11]. http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4146652

[20] Thomas Moscibroda, Roger Wattenhofer, and Aaron Zollinger. 2006. Topology control meets SINR: the scheduling complexity of arbitrary topologies. In Proceedings of the 7th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2006, Florence, Italy, May 22-25, 2006. Sergio Palazzo, Marco Conti, and Raghupathy Sivakumar (Eds.). ACM, 310-321. DOI:http://dx.doi.org/10.1145/1132905.1132939

[21] NIST 2016. NIST Digital Library of Mathematical Functions. (2016). http://dlmf.nist.gov

[22] David Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications.

[23] Ramesh Rajagopalan and Pramod K. Varshney. 2006. Data-aggregation techniques in sensor networks: A survey. IEEE Communications Surveys and Tutorials 8, 1-4 (2006), 48-63.

[24] Goel Sanatan, Rai Bhaskar, Krishnamachari, Ashish Goel, Sanatan Rai, and Bhaskar Krishnamachari. 2005. Sharp Thresholds for Monotone Properties in Random Geometric Graphs Ashish.

[25] Andrzej Rucinski Svante Janson, Tomasz Luczak. 2000. Random Graphs. John Wiley & Sons.

[26] Eric W. Weisstein. 2000. Modified Bessel Function of the Second Kind. Wolfram. http://mathworld.wolfram.com/ModifiedBesselFunctionoftheSecondKind.html

[27] F. Xue and P.R. Kumar. 2004. The number of neighbors needed for connectivity of wireless networks. Wireless Networks 10 (2004), 169-181.

[28] Yang Yu, Bhaskar Krishnamachari, and Viktor K. Prasanna. 2004. Energy-Latency Tradeoffs for Data Gathering in Wireless Sensor Networks. In INFOCOM.

[29] Marek Zakrzewski. 2013. Markowe wykLady zmatematyki. GiS.

[30] Qing Zhao and Lang Tong. 2005. Energy efficiency of large-scale wireless networks: proactive versus reactive networking. IEEE Journal on Selected Areas in Communications 23, 5 (2005), 1100-1112.

[31] Michele Zorzi and Ramesh R. Rao. 2003. Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Energy and Latency Performance. IEEE Trans. Mob. Comput. 2, 4 (2003), 349-365.

Marek Klonowski

Malgorzata Sulkowska

Department of Computer Science, WrocLaw University of Science and Technology, Poland.

received 14th Oct. 2014, revised 3rd July 2016, accepted 12th July 2016.

(*) Partially supported by National Science Center - Poland decision number DEC- 2013/09/B/ST6/02258

([dagger]) Emails: {Marek.Klonowski, Malgorzata.Sulkowska}@pwr.edu.pl

7 Appendix A

Below we recall the collection of the most important facts that we use in our paper.

Fact 1 The volume of d-dimensional sphere of radius l is equal

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [GAMMA] is the Euler Gamma function .

Proof: See e.g. [5, 29] . []

The following versions of Chernoff bound can be found in [18]:

Fact 2 Let X have a binomial distribution. For every R [greater than or equal to] 6E[X] we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Fact 3 Let X have a binomial distribution. For any 0 [less than or equal to] [delta] [less than or equal to] 1 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Fact 4 Let X have a binomial distribution. For any 0 [less than or equal to] [delta] [less than or equal to] 1 we have

Fact 5 Let X have a binomial distribution. For any [delta] > 0 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We also use the following version of Hoeffding's Inequality (see [9]).

Fact 6 Let [X.sub.1], [X.sub.2], ... [X.sub.n] be i.i.d random variables such that E[Xi] = [mu] and P [a [less than or equal to] Xi [less than or equal to] b] = 1 . Then for any [epsilon] > 0

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

8 Appendix B

Below we present the proofs of some facts and lemmas used throughout the paper.

8.1 Disconnectivity of random geometric graphs

Lemma 6 Let Vn be the set of n vertices placed randomly and independently in a square Qn = [0, n] . Let Gn = (Vn, E) be the graph such that {v, w} [member of] E if and only if||v - w|| < log n/[PI]. Then Gn is disconnected w.h.p.

Proof: (Sketch.) The proof is just a classic application of the second moment method to the random variable X denoting the number of isolated vertices in [G.sub.N]. Let Xi, 1 [less than or equal to] i [less than or equal to] n, be the indicator random variables such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the number of isolated vertices in [G.sub.N]. Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Since the probability that two vertices are not joined by an edge is equal to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (and therefore the area covered by their ranges is[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) we may write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

Finally, by 5, 6, 7 and the second moment method we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

Thus w.h.p.there exists at least one isolated vertex which implies that [G.sub.N] is disconnected w.h.p. []

8.2 Fact about the Bessel function of the 2nd kind

Fact 7 For any A, B, C > 0

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where K[alpha] (z) is the Bessel function of the 2nd kind [26].

Proof: From [21] (Formula 10.32.10) we know that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for any positive real z. Thus, substituting [alpha] = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and z = 2 * B * C we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Substituting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and doing simple reformulations we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Finally,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Extracting the integral and putting all the other terms to the right side of the equality completes the proof. []

8.3 Proof of Lemma 2

Proof:

Let us consider the case when the ball B([V.sub.r], 1/[5n.sup.1/d]) of radius 1/[5n.sup.1/d] centered at the root is whole included in [Q.sub.n]. Then the probability that we consider is the smallest possible. We have |[Q.sub.n]| = n and for some constant a, when a = a * (1/5) the volume of the ball satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let us define a random variable X that denotes the number of stations placed outside B([V.sub.r], 1/[5n.sup.1/d]) . Clearly X has binomial distribution with parameters n and 1 - a. We need to prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] = 1 which is equivalent to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [GAMMA] is the Euler Gamma function (see Fact 1 in Appendix A), we get a < 1/2. Let [epsilon] = 1 - a - 1/2 > 0 . We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Applying Hoeffding's inequality (see Fact 6 in Appendix A) with parameters a = 0 and b = 1 we instantly get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [].

(i) For d=2:c = [pi], c= 1/2. For d = 3 : c = 4[pi]/3, c = 1/(3[square root of (3)])
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Klonowski, Marek; Sulkowska, Malgorzata
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:8782
Previous Article:Edge disjoint Hamilton cycles in Knodel graphs.
Next Article:On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters