Wireless Ad Hoc and Sensor Networks

Constructing Load-balanced Data Aggregation Trees

 165

Consequently, LBPNA can be formulated as an integer linear programming

ILP

LBPNA

as follows:

max

ϑ

= min{

α

i

=



v

j

∈L(v

i

)\{v

i

}



B

γ

i



1

ι

ij

+

ϕ

i

|∀v

i

∈D}

s.t.



v

i

∈N

1

(v

j

)

β

i

ξ

ij

= 1, ∀v

j

/∈ D

ξ

ij

∈{0, 1}.

(ILP

LBPNA

)

The objective function

ϑ

is the minimum actual load (

α

i

) among all the non-

leaf nodes. The first constraint states that each leaf node can be allocated to only

one non-leaf node, whereas the second constraint indicates that

ξ

ij

is a binary vari-

able. According to Definition 7.8, the number of leaf child nodes and the number

of non-leaf child nodes both contribute to the actual load of a non-leaf node. The

leaf child ...