Wireless Ad Hoc and Sensor Networks

Constructing Load-balanced Data Aggregation Trees

 155

give the formal definition of the parent node assignment for leaf nodes to non-leaf

nodes as follows:

Definition 7.6 Parent node assignment for leaf nodes (A

L

). For a probabilistic

WSN represented by graph G(V,E,P(E)) and a CMIS D = {v

1

,v

2

,···,v

m

}, we need

to find m disjoint sets on V, denoted by L(v

1

),L(v

2

),···,L(v

m

), such that:

1. Each set L(v

i

)(1 ≤i ≤m) contains exactly one non-leaf node v

i

.

2.



m

i=1

L(v

i

)=V,andL(v

i

)



L(v

j

)=∅ (1 ≤i = j ≤ m).

3. ∀v

u

∈ L(v

i

)(1 ≤i ≤m) and v

u

= v

i

, such that (v

u

,v

i

) ∈ E.

4. Assign v

i

(1 ≤i ≤ m) as the parent node of the nodes in L(v

i

)\{v

i

}.Aparent

node assignment for leaf ...