Algorithms for Droplet Routing in Digital Microfluidic biochip: Managing deadlock, Route Storage and Contamination

Abstract

Digital microfluidics Biochip (DMFB) is a miniature hand-held device capable of automating biochemical assays. It is used extensively in genetic research and medical diagnostics. Droplet routing in biochemical synthesis using DMFB is very challenging. It needs a physical movement of various droplets to implement a specified operation in the synthesis. Droplet routing aims to move droplets from a source cell to a destination cell and maintain fluidic constraints all the time. The tasks include handling issues like deadlock contamination and minimizing execution time and number of cells used. The total execution time (latest arrival time) is mainly impacted by deadlock. Detection of the deadlock early can enable preemptive action to be taken to minimize the LAT. To achieve this, the bound boxes of the droplets are checked for overlapping. Various deadlock scenarios are analyzed, and four deadlock conditions are defined. The simulation result also shows a reduction in LAT. A bidirectional route exploration mechanism is proposed to reduce the route exploration time. The proposed method treats the DMFB as a rectilinear grid. The route exploration is performed by using two waveforms- source and destination wave. The source wave originates from the source cell and moves towards the destination cell. The destination wave begins at the destination cell and moves towards the source cell. Every cell visited by any cell is marked with an alphanumeric value. Both the cells intersect at pivot cells markedby both waveforms. These pivot cells act as boundary cells and convert the DMFB to a bipartite graph. Each pivot cell is assigned a pivot value by summing the numeric values of the marking. The pivot cell with minimum value is given as the pivot value of the droplet. The droplets are then sorted in ascending order to generate the droplet order. The routes of each droplet are validated by selecting a pivot cell using four user-defined heuristics. Two ants are generated from each pivot cell and sent to the source and destination. When these ants reach their destination, the route they follow is extracted from their header. The routes of all the droplets are then compacted to get the final parallel moving sequence. The simulation result shows an improvement in the latest arrival time. A flooding-based droplet routing mechanism is proposed for biochemical synthesis. In the route exploration phase, flood the whole biochip with scout packets. A duplicate copy of the scout packet is forwarded to each of the neighbors of the current cell. The scout packets are discarded if it has the same origin cell, or the current cell is already in its header. When a scout packet reaches its destination cell, the route is extracted from its header and added to the route list. Each route is validated by a Hello packet. The hello packet is sent from the destination cell to the source cell along the route in the reverse direction. When the hello packet reaches the source cell, the route is added to the validated route list. The routes are then sorted in ascending order by route length. The droplet with the least route length is assigned the highest priority. The route compaction is performed based on the droplet order. An improvement of 12.25% and 20.5% in LAT is observed for free and virtual topology. A 3-tuple representation method for droplet routes to minimize memory/space requirement is proposed. The proposed method assumes the route of a droplet is a set of smaller sub-routes. In the route exploration phase, a rectangle is created by intercepting two L-lines drawn in opposite directions. A rectangle is drawn for every droplet. This converts the droplet routing into a rectangle overlapping problem. Two edges from every rectangle need to be removed, transforming into an edge optimization problem. The space/memory requirement is minimized by using a 3-tuple representation method: <S, M, E>. S, M, and E are the addresses of the source, middle, and end cells. The performance of the proposed method is compared against three well-known droplet routing protocols. The latest arrival time shows an improvement of 13.83% and 21.31% in free and virtual topology, respectively. Similarly, a 32.47% reduction in memory requirement is also noted. A proactive wash droplet routing algorithm is proposed for contamination problems in biochemical synthesis using DMFB. Fluid droplets of heavier molecules, such as protein, leave some residue while traversing their route. This residue acts as a contamination source for any other fluid droplet visiting these cells in a later time cycle. It results to an unwanted mixing, leading to a contamination problem. Wash droplets are introduced to clean this residue before the arrival of any other fluid droplets. The proposed method proactively cleans all the contamination cells/spots by appending a wash droplet behind every fluid droplet. The fluid and wash droplets are moved using a stop-and-wait manner. The wash capacity is taken into consideration. The capacity is reduced by 1 for every contamination cell it visits. A wash droplet becomes dirty as its capacity is reduced to 0. The droplets start moving along their route, and a wash droplet follows it by maintaining a gap of at least one cell. When the wash droplet becomes dirty, it is moved to the nearest waste reservoir, and a new wash droplet is replaced. The performance of the proposed method is mapped against three popular protocols. The simulation result shows total cleaning is achieved, and an improvement of 3.122% is recorded for the latest arrival time.