Wireless Ad Hoc and Sensor Networks

160 

Wireless Ad Hoc and Sensor Networks

P(W

i

)=[(1 −

ω

1

)(1 −

ω

2

)···(1 −

ω

k

i

)(1 −

ω

i

)]

τ

≤ (1 −W )

τ

≤ (1 −min{

ω

∗

i

|v

i

∈

V,

ω

∗

i

> 0})

τ

≤ (e

−min{

ω

∗

i

|v

i

∈V,

ω

∗

i

>0}

)

τ

= e

−

7min{

ω

∗

i

|v

i

∈V,

ω

∗

i

>0}ln(n)

min{

ω

∗

i

|v

i

∈V,

ω

∗

i

>0}

≤ e

−7ln(n)

=

1

n

7

.

Thus, according to the Borel-Cantelli lemma, P(W

i

) ∼0, which implies that there

exists one independent node in the set N

1

(v

i

)



{v

i

} almost surely, i.e., it is almost

sure that the set M = {v

i

|



ω

i

= 1,0 ≤i ≤n}derived from Algorithm 9 is a DS. Then,

it is reasonable that we consider M is a DS of G in the following.

2

2

Based on Lemma 7.1 and Lemma 7.2, the following theorem can be obtained.

Theorem 7.1

The set M = {v

i

|



ω

i

= 1,0 ≤ i ≤ n},where



ω

i

is