介電濕潤晶片現在已成為實現針腳限制生物晶片的重要技術，隨著生化檢驗複雜度上升，針腳限制介電濕潤晶片的晶片層級設計廣泛地被使用，此設計包含了電極驅動訓號和繞線的規劃。此外，為了處理需要高速反應的生化檢驗，例如醫療上的快速篩檢，人們需要一個高頻率的介電濕潤晶片以達到高速反應的需求。 然而，根據參考文獻，當電極驅動與不驅動狀態的切換次數過高，將會使得電極與液珠之間接觸角變小，而此現象將會影響介電濕潤晶片的可靠度。 因此，在介電濕潤晶片的晶片層級設計中，晶片可靠度、驅動訊號分配、以及繞線問題需要同時考量。我們在這篇論文中針對可靠的針腳限制生物晶片層級設計提出基於網路流的演算法，藉著加入驅動切換次數的限制，電極的驅動切換次數可以有效的降低進而減少接觸角問題所帶來的影響。我們採用循序式地分配驅動訊號與繞線的演算法以克服複雜的繞線問題。實驗結果顯示，我們提出的方法有效率地降低接觸角問題。此外，我們所產生的晶片層級設計除了具有可靠度之外，也是一個可繞線的設計，而且符合指定的針腳限制。

Nowadays, electrowetting-on-dielectric (EWOD) chips have become the most popular actuator for droplet-based digital microfluidic biochips.
As the complexity of biochemical assay increases, the chip-level design of EWOD chips which integrates electrode addressing and wire routing are widely adopted.
Furthermore, to finish many time-sensitive bioassays such as incubation and emerging flash chemistry in a specific time, a high-frequency EWOD is used to satisfy the demand.
However, the reliability of the EWOD chip degrades due to the contact angle reduction problem incurred by huge number of switching times of an electrode.
Thus, the reliability issue, electrode addressing, and wire routing problem should be considered together in the chip-level design of an EWOD chips.
In this thesis, a graph-based chip-level design algorithm is presented.
By setting the switching-time constraint,
the number of switching times can be limited to minimize the impact of contact angle reductions problem.
Also, a progressive addressing and routing approach is proposed to overcome the challenge of complex wire routing problem.
Experimental results show that the influence of contact angle reduction problem can be effectively minimized by proposed algorithm.
A reliable chip-level design with feasible wire routing solution can be generated with number of pins are satisfied.

[1] http://en.wikipedia.org/wiki/Maximal independent set
[2] J.-W. Chang, T.-W. Huang, and T.-Y. Ho, “An ILP-based obstacle- avoiding Routing algorithm for pin-constrained EWOD chips,” Proc. IEEE/ACM ASPDAC, pp. 67–72, 2012.
[3] K. Chakrabarty, “Towards fault-tolerant digital microfluidic lab-on- chip: defects, fault modeling, testing, and reconfiguration,” Proc. IEEE ICBCS, pp. 329–332, 2008.
[4] R. B. Fair, “Digital microfluidics: is a true lab-on-a-chip possible?,” Microfluidics and Nanofluidics, vol. 3, no. 3, pp. 245–281, 2007.
[5] Shih-Kang Fan, Tsung-Han Hsieh and Di-Yu Lin “General digital microfluidic platform manipulating dieletric and conductive droplets by dielectrophoresis and electrowetting,” Lab on chip, pp. 1236–1242, 2009
[6] J. Gong and C. J. Kim, “Direct-referencing two-dimensional-array digital microfluidics using multilayer printed circuit board,” IEEE J. MEMS, no. 2, pp. 257–264, 2008.
[7] T.-Y. Ho, J. Zeng, and K. Chakrabarty, “Digital microfluidic biochips: A vision for functional diversity and more than Moore,” IEEE/ACM ICCAD, pp. 578–585, 2010.
[8] T.-W. Huang, S.-Y. Yeh, and T.-Y. Ho, “A network-flow based pin-count aware routing algorithm for broadcast electrode-addressing EWOD chips,” Proc. IEEE/ACM ICCAD, pp. 425–431, 2010.
[9] T.-W. Huang, H.-Y. Su and T.-Y. Ho, “Progressive Network-Flow Based Power-Aware Broadcast Addressing for Pin-Constrained Digital Microfluidic Biochips,” Proc. IEEE/ACM DAC, pp. 741–746, 2011.
[10] T.-W. Huang, K. Chakrabarty, and T.-Y. Ho, “Reliability-oriented broadcast electrode-addressing for pin-constrained digital microfluidic biochips,” Proc. IEEE/ACM ICCAD, pp. 448–455, 2011.
[11] L. Huang, B. Koo, and C. J. Kim, “Evaluation of anodic Ta2 O5 as the dielectric layer for EWOD devices,” IEEE MEMS, pp. 428-431, 2012.
[12] C. C.-Y. Lin and Y.-W. Chang, “ILP-based pin-count aware design methodology for microfluidic biochips,” Proc. ACM/IEEE DAC, pp. 258–263, 2009.
[13] Y. Luo, K. Chakrabarty, and T.-Y. Ho “Design of cyberphysical digital microfluidic biochips under Completion-Time Uncertainties in Fluidic Operations,” Proc. ACM/IEEE DAC, 2013
[14] P. Paik, V. Pamula, and R. Fair, “Rapid droplet mixers for digital mi- crofluidic systems”, Lab on a Chip, vol.3, pp. 253–259, 2003.
[15] M. G. Pollack, A. D. Shenderov, and R. B. Fair, “Electrowetting-based actuation of droplets for integrated microfluidics,” Lab on chip, pp. 96– 101, 2002.
[16] J. H. Song, R. Evans, Y. Y. Lin, B. N. Hsu, and R. B. Fair, “A scaling model for electrowetting-on-dielectric microfluidic actuators,” Microfluidics and Nanofluidics, pp. 75–89, 2009.
[17] F. Su, K. Chakrabarty, and R. B. Fair, “Microfluidics based biochips: technology issues, implementation platforms, and design-automation challenges,” IEEE Trans. on CAD, pp. 211–223, 2006.
[18] T. Xu and K. Chakrabarty, “Broadcast electrode-addressing for pin-constrained multi-functional digital microfluidic biochips,” Proc. ACM/IEEE DAC, pp. 173–178, 2008.
[19] S.-H. Yeh, J.-W. Chang, T.-W. Huang, T.-Y. Ho, “Voltage-aware chip- level design for reliability-driven pin-constrained EWOD chips”, Proc. IEEE/ACM ICCAD, pp. 353–360, 2012.
[20] T. Yan and M. D. F. Wong, “A correct network flow model for escape routing”, Proc. ACM/IEEE DAC, pp. 332–335, 2009.
[21] S. K. Cho, H. Moon, and C.-J. Kim, “Creating, transporting, cutting, and merging liquid droplets by electrowetting-based actuation for digital microfluidic biochips,” Journal of Microelectromechanical Systems, vol. 12, pp. 70–80, 2003.
[22] L. Young, “Anodic oxides films,” New York, NY: Academic Press Inc., 1961.
[23] Y. Zhao and K. Chakrabarty, “Co-optimization of droplet routing and pin assignment in disposable digital microfluidic biochips,” Proc. ACM ISPD, pp. 69–76, 2011.