Efficient two phase heuristic routing technique for digital microfluidic biochip

摘要

Digital microfluidic biochip's (DMFB's) have emerged as an alternative to various in-vitro diagnostic tests and are expected to be closely coupled with cyber physical systems. Efficient-error-free-routing and cross-contamination minimisation are needed during bioassay operations on DMFB. This study 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 (IInet). Then exact routing is attempted based on tabulation minimisation process. Remaining nets having interfering index values higher than threshold will be routed considering various constraints in DMFB framework. In second phase another metric named routable ratio (RR) is proposed and depending on RR metric, the routing order among conflicting paths are prioritised to avoid deadlock from there onwards till the droplet reaches its target location. Finally we formulate droplet movement problem as satisfiability problems and solve with SAT based solver engine if higher number of overlapping (≥5) nets exist. Experimental results on benchmark suite I and III show our proposed technique significantly reduces latest arrival time, average assay execution time and number of used cells as compared with earlier methods.