Wireless Ad Hoc and Sensor Networks

Reliable and Energy Efficient Target Coverage

 187

8.4.1 α-RMSC Heuristic Algorithm Overview

Our heuristic algorithm (see Algorithm 11) takes S (sensor set), T (target set), e

(sensor lifetime granularity), where e ∈ (0,1],and

α

(the pre-set threshold) as the

input parameters. Consequently, the algorithm returns all possible sensor covers

C

1

,C

2

,···,C

k

.

Algorithm 11 recursively builds sensor covers from lines 6 to 19. The set SEN-

SORS maintains the list of sensors that have residual energy greater than zero; thus

these sensors can participate in additional sensor covers. At each step, a target is

selected, in line 6, to be covered. Once the target has