A novel two phase heuristic routing technique in digital microfluidic biochip

摘要

Efficient routing and cross-contamination minimization are two interrelated challenging areas in Digital Microfluidic Biochip (DMFB). This paper proposes a two phase heuristic technique for routing droplets on a two-dimensional DMFB. Initially it attempts to route maximum number of nets in a concurrent fashion depending on the evaluated value of a proposed function named Interfering Index (II). Next the remaining nets having interfering index values higher than threshold will be routed considering various constraints in DMFB framework. Our method will check all the conflict arises between various routing paths from same assay or from different assays and also with the unsuccessful routing paths from the first phase (if any). If conflict occurs it determines the conflict zone on the chip as Critical Region(CR). Another metric named Routable Ratio (RR) is proposed and depending on RR metric, our method prioritized the routing order among conflicting paths(nets) to avoid deadlock from there onwards till the droplet reaches its target location. Experimental results on Benchmark suites III show our proposed technique reduces latest arrival time upto certain extent but significantly reduces average assay execution time and number of used cell compared to earlier routing methods for DMFB.