Wireless Ad Hoc and Sensor Networks

236 

Wireless Ad Hoc and Sensor Networks

Algorithm 15: Multi-path Scheduling Algorithm

input : a routing tree T with m leaf nodes

output: a schedule plan for the routing tree T

1 for i = 1;i ≤ m;i ++do

2 while there is some data for transmission on F

i

do

3 P←{P

i

};

4 S←∅;

5 if rd

i

%2 == 1 then

6 S←P

i

o

;

7 rd

i

++;

8 else if rd

i

%2 == 0 then

9 S←P

i

e

;

10 rd

i

++;

11 for j = i + 1; j ≤m; j ++do

12 if P

j

is not intersecting with any path in P && there is some data

for transmission on F

j

then

13 if rd

j

%2 == 1&&all the transmissions in P

j

o

and all the

transmissions in S are interference/collision-free then

14 P←P∪{P

j

};

15 S←S∪P

j

o

;

16 rd

j

++;

17 if rd

j

%2 == 0&&all the transmissions ...