Wireless Ad Hoc and Sensor Networks

Approximation Algorithms for Load-balanced Virtual Backbone

 83

Pr[y ≥(1 +

μ

)

α

(y

∗

+

ϕ

)] = n

1

n

3

=

1

n

2

. (4.25)

Again,



n>0

1

n

2

is a particular case of the Riemann zeta function, which is bounded.

Thus, according to the Borel-Cantelli lemma, Pr[y ≥ (1 +

μ

)

α

(y

∗

+

ϕ

)] ∼ 0, where

α

=

3log(n)

min{a

∗

ij

|a

∗

ij

>0}

. This implies that Algorithm 5 yields a solution of performance

O(log(n))y

∗

,wherey

∗

is the optimal solution.

Subsequently, we consider the probability that a non-backbone node v

j

∈V\B is

not allocated to a backbone node in its one-hop neighborhood at iteration j.Thatis,

α



k=1



v

i

∈N

1

(v

j

), v

i

∈B

Pr[b

i

a

ij

= 0 at iteration k] (4.26)

≤

α



k=1,a

∗

ij

>0

(1 −b

i

a

∗

ij

) (4.27)

≤ e

b

i

a

∗