
116
Wireless Ad Hoc and Sensor Networks
connected, the PNM enables the employment of lossy links by introducing the TSR
value on each lossy link. In this chapter we focus on constructing a minimum-sized
CDS while its reliability satisfies a preset application-dependent threshold. We prove
that
σ
-RMCDS is an NP-hard problem and propose a GA with immigrants schemes
to address the problem. The simulation results show that compared to the traditional
MCDS algorithm, RMCDS-GA can find a more reliable CDS without increasing the
size of a CDS.