Design of Fluidic-Level Synthesis and Error Recovery Algorithms for Digital Microfluidic Biochips

Abstract

Digital microfluidic biochips (DMFBs) are a class of lab-on-a-chip (LOC) devices and micro-electro-mechanical systems (MEMS). DMFBs use the electrowetting-on dielectric (EWOD) property to manipulate discrete droplets on a two-dimensional grid of electrodes. The analog microfluidic devices deal with continuous-flow fluids under the influence of micro-pumps and micro-valves. Analog microfluidic devices are cumbersome and complicated. DMFBs offer miniaturization, automation (reduces human effort), portability, efficiency, and software programmability. A few applications of DMFBs are point-of-care diagnostics, DNA analysis, enzymatic analysis, proteomic analysis, and environmental toxicity monitoring. DMFBs face similar challenges faced by any micro-electronic equipment. Several synthesis techniques have been proposed to cope with increasing design complexity for correct, efficient, and fault tolerant assay execution. The existing synthesis techniques have several drawbacks. Being application-specific, they cannot schedule all kinds of assays and are not scalable. A few algorithms are fault-tolerant and can resynthesize based on error feedback. The need for concurrent execution of multiple assays with accuracy has increased the design complexity of DMFBs. Thus there is a requirement for efficient and fault-tolerant synthesis algorithms. The research work documented in this thesis presents several online and offline fluidic-level synthesis and error recovery algorithms for DMFBs. A heterogeneous earliest finish time based online scheduling algorithm called DMHEFT is proposed. A novel upward ranking mechanism is used to prioritize the operations. The earliest finish time (EFT) and least recently used (LRU) policy are used for module allocation. Two meta-heuristic approaches– artificial bee colony hybridized with generalized N-point crossover (ABC-GNX) and invasive weed optimization (IWO) based perturbation techniques are further used to improve the quality of solutions for offline scheduling. Proposed algorithms DMHEFT, ABC-GNX, and IWO are tested on 26 notable benchmarks. Both ABC-GNX and IWO achieve better assay completion times and shorter execution times compared to state-of-the-art algorithms. A unified approach is proposed to solve resource binding, scheduling, and placement problems in a coordinated manner. It attempts to minimize assay completion times and the maximum area used simultaneously. A linear time complexity algorithm known as the flow scan (FS) method is employed for free space management and determining the initial placement of modules. A fast simulated annealing (FSA) algorithm is used to improve the placement quality. Defective cells are treated as blockages for placement. Reconfiguration is used to relocate modules if cells become faulty during assay execution. Reconfiguration uses free space information provided by the FS algorithm. The proposed algorithm is evaluated on different variants of protein and in-vitro benchmarks. Experimental results show that the proposed algorithm is able to produce reduced assay completion times and maximum areas used than existing methods. Reinforcement learning (RL) based droplet routing algorithms are proposed. Q-learning and double deep Q-network (DDQN) based route discovery between a pair of source and target is presented. Stalling and detours are used for route compaction after route discovery. RL-based schemes find shorter routes despite increased blockages (active modules) and guarantee a path if one exists. An ϵ􀀀greedy policy is employed to obtain a trade-off between exploration and exploitation for better routes. Compared to existing algorithms, proposed RL-based routing achieves better cell utilization and arrival times. A quasi-static scheduling based error-recovery (QSSER) method is proposed to reduce assay completion time with tolerance for a maximum number of possible transient faults. Online error-recovery algorithms have high response times, and offline error-recovery algorithms are infeasible. Considering this, a quasi-static approach is introduced, combining the benefits of online and offline strategies. The proposed QSSER can work with sensor-based and CCD camera-based error detection methods. Mixed time-space redundancy based recovery schedules are used to reduce assay completion times. QSSER determines a quasi-static tree of schedules and a set of switching points between corresponding schedules depending on the error scenario. Then the schedules are fed to the microcontroller. The tree size is limited using a tree reduction technique so that it can fit in the available memory of the micro-controller. The proposed algorithm is evaluated on three real-life assays: PDNA, Exponential dilution of protein assay, and interpolation dilution of protein assay. Experimental results shows that proposed method is able to schedule assays with varied number of injected errors under deadlines efficiently over compared methods.