Biomedical Engineering Reference
In-Depth Information
Scheduling algorithm for droplet routing
1. Start from the droplet closest to the boundary of the array, whose initial moving direction
facing the inner of the array. Mark its initial moving direction as the starting direction.
We chose such a droplet as a starting point since it is most likely to be far away from all the
other droplets.
2. Move this droplet along its pathway until it shares the same column/row with the starting
point of another droplet moving in the same direction. Move the two droplets in parallel.
By this means, the farthest droplet is “pulled” closer to other droplets, thereby improving
the alignment and increasing the probability of concurrent manipulation.
3. Repeat Step 2 and keep adding new droplets for parallel movement until a droplet in the
set of droplets moving in parallel confronts either a turn or another droplet in its pathway.
4. Count the number of droplet movements oriented in each of the three directions other than
the reverse of the starting direction at the current column or row, and store these numbers
in a candidate moving set S.
5. Choose the direction of the next droplet manipulation corresponding to the largest number
of unfinished droplet movements in S.
6. Repeat Steps 2-5 until no droplet can be moved in the three directions other than the
reverse of the starting direction. The reverse direction of the starting direction is excluded
in this step because allowing a droplet to move in this direction may cause a dead loop.
Therefore, we handle such movement separately in Step 8.
7. Repeat Steps 1-6 starting from the reverse of the starting direction. This step schedules the
leftover droplet movements from Step 6.
8. Add the routing schedule from Step 7 to the end of the schedule obtained from Steps 1-6 in
the first iteration to obtain the schedule for the entire routing snapshot.
Figure 3.22
Pseudocode of a scheduling algorithm for droplet routes.
D
1
D
4
D
2
D
5
D
3
Figure 3.23
A routing example to illustrate the scheduling algorithm.
after each manipulation step. Each checking operation takes O(
M
) time.
Step 4 calculates the number of droplet movements in different directions
and stores this information in
S
. This step takes O(
M
)
time in the worst case.
Step 5 also takes O(
M
) time. Note that Steps 2-5 can be repeated.
However, the number of repetitions is bounded by the sum of the lengths
of all the droplet pathways; that is, in the worst case, Steps 2-5 are repeated
for each single droplet movement. Therefore, the time taken by Steps 2-5 is
