介電濕潤晶片現在已成為實現針腳限制生物晶片的重要技術，在介電濕潤晶片的設計流程中，晶片可靠度是一個相當重要的議題，可靠度會直接的影響到生物實驗的成敗。根據參考文獻，影響可靠度最主要的因素是滯留電荷的問題，滯留電荷的造成起因於使用太大的驅動電壓去驅動晶片上的電極。除此之外，為了符合針腳限制的設計，使用同一訊號源驅動多個電極是不可避免地，若沒有好好分配驅動電壓也會產生滯留電荷的問題。除了滯留電荷問題之外，繞線的問題也增加了晶片設計的複雜度。現今還沒有相關的研究同時探討繞線的問題以及滯留電荷的問題，這使得產生出來的晶片有較高的機會在運作中失敗，也有可能因為繞線的複雜度太高而無法完成設計。因此，我們在這篇論文中針對可靠的針腳限制生物晶片提出基於網路流的演算法，我們的方法不只能夠將滯留電荷的影響減到最少，還提供一個全面的繞線結果。實驗結果映證了我們的演算法是有效的且可行的。

Electrowetting-on-dielectric (EWOD) chips have become the most promising technology to realize pin-constrained digital microfluidic biochips (PDMFBs). In the design flow of EWOD chips, reliability is a critical challenge as it directly affects execution of bioassays. The major factor to degrade chip reliability is the trapped charge problem, which is induced by excessive applied voltage. Nevertheless, to comply with the pin constraint for PDMFBs, signal merging is inevitably involved, and thereby incurring trapped charges due to unawareness of applied voltage. Except for the trapped charge problem, wire routing to accomplish electrical connections increases the design complexity of pin-constrained EWOD chips. Unfortunately, no existing works tackle the problems of excessive applied voltage and wire routing, and thus the resultant chip will have more probabilities to fail during execution or can not be realized because of wire routing problem. In this thesis, we present a network-flow based algorithm for reliability-driven pin-constrained EWOD chips. Our algorithm not only minimizes the reliability problem induced by signal merging but also provides a comprehensive routing solution for EWOD chip-level designs. The experimental results demonstrate the effectiveness of proposed algorithm on real-life chips.

[1] Shaun Berry, Jakub Kedzierski, and Behrouz Abedian "Irreversible Electrowetting on Thin Fluoropolymer Films," ACS J. Langmuir, no. 23, pp. 12429-12435, 2007.

[2] K. Chakrabarty, "Towards fault-tolerant digital microfluidic lab-on-chip: defects, fault modeling, testing, and recon figuration," Proc. IEEE ICBCS, pp. 329-332, 2008.

[3] J.-W. Chang, T.-W. Huang, and T.-Y. Ho, "An ILP-based obstacle-avoiding routing algorithm for pin-constraint EWOD chips," Proc. ASP-DAC, pp. 67-72, 2012.

[4] 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.

[5] A. I. Drygiannakis, A. G. Papathanasiou, and A. G. Boudouvis, "On the connection between dielectric breakdown strength, trapping of charge, and contact angle saturation in electrowetting," ACS J. Langmuir, no. 25, pp. 147-152, 2009.

[6] R. B. Fair, "Digital microfluidics: is a true lab-on-a-chip possible?,"Microfluidics and Nanofluidics, vol. 3, no. 3, pp. 245-281, 2007.

[7] 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.

[8] 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.

[9] 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.

[10] T.-W. Huang, S.-Y. Yeh, and T.-Y. Ho, "A network-
ow based pin-count aware routing algorithm for broadcast electrode-addressing EWOD chips," Proc. IEEE/ACM ICCAD, pp. 425-431, 2010.

[11] 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.

[12] Y. Y. Lin, R. D. Evans, E. Welch, B. N. Hsu, A. C. Madison, R. B. Fair, "Low voltage electrowetting-on-dielectric platform using multi-layer in-sulators," Sensor. Actuat. B-Chem. 150, pp. 465-470, 2010.

[13] P. Y. Paik, V. K. Pamula, M. G. Pollack and K. Chakrabarty, "Coplanar digital microfluidics using standard printed circuit board processes,"Proc. MicroTAS, pp. 566-568, 2005.

[14] 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.

[15] F. Su, K. Chakrabarty, and R. B. Fair, "Microfluidics based biochips: Technology issues, implementation platforms, and design-automation challenges," IEEE TCAD, pp. 211-223, 2006.

[16] H. J. J. Verheijen and M. W. J. Prins, "Reversible electrowetting and trapping of charge: model and experiments," ACS J. Langmuir, no. 15, pp. 6616-6620, 1999.

[17] T. Yan and M. D. F. Wong, "A correct network flow model for escape routing," Proc. ACM/IEEE DAC, pp. 332-335, 2009.

[18] T. Xu and K. Chakrabarty, "Broadcast electrode-addressing for pin-constrained multi-functional digital microfluidic biochips," Proc. IEEE/ACM DAC, pp. 173-178, 2008.

[19] T. Xu and K. Chakrabarty, "Fault Modeling and Functional Test Methods for Digital Microfluidic Biochips," IEEE Transactions on Biomedical Circuits and Systems, vol. 3, no. 4,pp. 241-253, 2009.