Pin-Constrained Chip Design - Digital Microfluidic Biochips - page 60

influence Droplet 2. However, if these two droplets are moved concurrently,
as determined by the grouping procedure, by the activation of (Column 2,
Row 2) and (Column 3, Row 2), they mix at (3,2). However, manipulations of
this type violate the fluidic constraint given by | P i ( t + 1) − P j ( t + 1)| ≥ 2. Thus,
they cannot exist in a single droplet-manipulation snapshot. Therefore, it is
safe to carry out the droplet manipulations in a single manipulation snap-
shot with an arbitrary ordering.
Although the grouping of droplets based on destination cells reduces the
number of droplets that can be simultaneously moved, this approach pro-
vides more concurrency than the baseline method of moving one droplet
at a time. Compared to direct addressing, an order-of-magnitude reduction
in the number of control pins is obtained. Simulation results in Subsection
3.2.5 show that there is only a small increase in the bioassay processing time
compared to direct addressing. The preceding droplet-manipulation method
is focused on minimizing power consumption because, in each step, only
droplet manipulations that involve a single column or row are carried out.
Additional droplet movements are typically possible, but concurrency is
traded off for power in this method. An extension to allow higher concur-
rency is described in Subsection 3.2.4.
3.2.2.4 Graph-Theoretic Model and Clique Partitioning
We have thus far introduced the basic idea of multiple droplet manipula-
tions based on destination-cell categorization, and shown that the drop-
lets in each group can be moved simultaneously. Assuming that each step
takes constant processing time, the total completion time for a set of droplet
movement operations is determined by the number of groups derived from
the categorization of destination cells. Note, however, that the grouping
need not be unique. For instance, in the example of Figure 3.15, we can form
four groups, that is, {4,9}, {1,2,3}, {5,6}, and {7,8}. However, {1,2,3,4}, {5,6}, {7,8,9}
is also a valid grouping of the droplets. The latter grouping is preferable
because three groups allow more concurrency and, therefore, lower bio-
assay completion time.
The problem of finding the minimum number of groups can be directly
mapped to the clique-partitioning problem from graph theory [56]. To illus-
trate this mapping, we use the droplet-manipulation problem defined in
Figure 3.15. Based on the destinations of the droplets, an undirected graph,
referred to as the droplet-movement graph (DMG), is constructed for each time
step (see Figure 3.18) . Each node in the DMG represents a droplet. An edge
in the graph between a pair of nodes indicates that the destination cells for
the two droplets either share a row or a column. For example, Nodes 1 and 2,
which represent the Droplets 1 and 2, respectively, are connected by an edge
because the destination cells for these droplets are accessed using Column 3
in the array. Similarly, Nodes 4 and 9 are connected by an edge because the
corresponding destination cells are addressed using the same row.