
Load-balanced CDS Construction in Wireless Sensor Networks
49
3. min{|B|
p
,|A |
p
}.
We claim that the LBCDS problem is NP-hard, since it still belongs to the MCDS
problem. Based on Definition 3.6, the key issue of the LBCDS problem is to seek a
tradeoff between the minimum-sized CDS, the load-balance of a constructed CDS,
and a dominatee allocation scheme. GAs are population-based search algorithms,
which simulate biological evolution processes and have successfully solved a wide
range of NP-hard optimization problems [56][57]. Additionally, GAs have shown
themselves to be very good at discovering good solutions with a reasonable amount
of time and computation ...