Algorithm 1 Distributed Algorithm (at each node Si, i E N)

Input: the neighbor set N(Si), the neighboring schedules, the critical

location set Pi that Si covers, the importance factor of each location Pi, i E Pi, network lifetime L, battery life Bi, Si is initially unlabeled

Output: the state (label or unlabel), the optimal schedule if Si is labled

Procedure:

I: calculate the maximum additional coverage it can provide, i.e.,

llqnax = Sim·sataxr t jEL:R( i) W(j) x llTj, and the optimal schedule

2: broadcast msg(i, UP D, Null, llCfax) to its neighbors

3: while llCfax > 0 do

4: if Si has the largest llCfax among its neighbors then

5: Si labels itself, broadcasts msg(i, LAB, sch, llCfax), and exits.

6: end if

7: if msg(k, LAB, sch, llCk'ax) is received then

8: update the schedule of its neighbor Sk, recalculate llCfax, and

broadcast msg(i, UP D, Null, llCfax). Go to 3

9: end if

10: ifmsg(k,UPD,Null,llCk'ax) is received then

I I: update the coverage metric of its neighbor Sk and Go to 3.

12: end if

13: end while

rubberman 1,355