數(shù)字微流控生物芯片測(cè)試診斷過(guò)程分析和優(yōu)化

張 玲,鄺繼順,梅軍進(jìn),林 靜

(1.湖北理工學(xué)院計(jì)算機(jī)學(xué)院,湖北 黃石435003;2.湖南大學(xué)計(jì)算機(jī)與通信學(xué)院,湖南 長(zhǎng)沙 410082)

數(shù)字微流控生物芯片測(cè)試診斷過(guò)程分析和優(yōu)化

張 玲1,2,鄺繼順2,梅軍進(jìn)1,林 靜1

(1.湖北理工學(xué)院計(jì)算機(jī)學(xué)院,湖北 黃石435003;2.湖南大學(xué)計(jì)算機(jī)與通信學(xué)院,湖南 長(zhǎng)沙 410082)

針對(duì)數(shù)字微流控生物芯片的測(cè)試和診斷過(guò)程進(jìn)行建模和分析，并根據(jù)并行測(cè)試的分塊數(shù)和單元出錯(cuò)概率為相應(yīng)的測(cè)試和診斷成本建立函數(shù)。通過(guò)Matlab對(duì)測(cè)試診斷成本函數(shù)的分析表明：隨著并行測(cè)試分塊數(shù)的增大，測(cè)試診斷成本的變化趨勢(shì)不明顯，也就是說(shuō)，并行測(cè)試的分塊數(shù)對(duì)測(cè)試診斷成本的影響不大；而隨著單元出錯(cuò)概率p的增加，測(cè)試成本呈明顯的增加趨勢(shì)，且增加的幅度較大。另外，診斷過(guò)程中，根據(jù)單元出錯(cuò)概率對(duì)出錯(cuò)的子陣列再進(jìn)行診斷，診斷過(guò)程必須持續(xù)若干次，直到所有故障定位后才能結(jié)束。在這些診斷中，針對(duì)最后一次定位的診斷成本是最大的，而且與其他次的診斷過(guò)程的成本相差幾十個(gè)數(shù)量級(jí)，決定了總成本的大小。這些結(jié)論為數(shù)字微流控生物芯片的測(cè)試和診斷過(guò)程優(yōu)化提供重要的理論依據(jù)，并為測(cè)試診斷方法的設(shè)計(jì)提供指導(dǎo)。

數(shù)字微流控生物芯片測(cè)試;生物芯片陣列規(guī)模;測(cè)試診斷;測(cè)試成本

1 引言

近幾年，電子測(cè)試已經(jīng)從對(duì)數(shù)字電路和模擬電路的測(cè)試擴(kuò)展到對(duì)基于交叉學(xué)科的微電機(jī)系統(tǒng)的測(cè)試[1]。與傳統(tǒng)的電子電路不同，微電機(jī)系統(tǒng)MEMS(Micro-Electromechanical Systems)涉及多個(gè)學(xué)科，經(jīng)歷多個(gè)能源領(lǐng)域，這樣的微系統(tǒng)更具有破壞性，更容易出現(xiàn)災(zāi)難性故障，其測(cè)試成為一大挑戰(zhàn)。2003年，ITRS(International Technology Roadmap for Semiconductors)認(rèn)定：到2009年，具有破壞性的復(fù)合微系統(tǒng)的測(cè)試為五大測(cè)試挑戰(zhàn)之一[2]。以離散液滴為操作對(duì)象的微流控生化芯片構(gòu)成了一類交叉多個(gè)學(xué)科的MEMS系統(tǒng)。它由電極陣列組成，只要給它們一定的驅(qū)動(dòng)電壓，這些陣列可以驅(qū)動(dòng)液滴按預(yù)定的路徑運(yùn)動(dòng)，以實(shí)現(xiàn)特定的生物檢測(cè)功能。數(shù)字微流控芯片的出現(xiàn)到被應(yīng)用到生命科學(xué)領(lǐng)域，就陸續(xù)有學(xué)者和研究組對(duì)其測(cè)試進(jìn)行針對(duì)性的研究。文獻(xiàn)[3]在2003年首次提出對(duì)數(shù)字微流控芯片進(jìn)行測(cè)試，并對(duì)物理故障進(jìn)行分析，將故障分為型(Parametric)故障，提出從測(cè)試液滴行為上對(duì)數(shù)字微流控芯片陣列進(jìn)行測(cè)試。

2004年，Su F 等人[4]提出將數(shù)字微流控芯片陣列抽象成圖論中的無(wú)向圖，讓單測(cè)試液滴順著Hamiltonian路徑訪問(wèn)所有的電極單元來(lái)檢測(cè)陣列單元是否完好。Su F等人[5]又在2005年通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，對(duì)于短路故障，它是否會(huì)對(duì)液滴的行為產(chǎn)生影響取決于測(cè)試液滴通過(guò)的路徑是否與相鄰短路的兩個(gè)電極垂直。所以,僅對(duì)電極單元測(cè)試是不夠的，還需要對(duì)電極之間的所有邊進(jìn)行測(cè)試。為了測(cè)試所有的陣列單元和陣列單元之間的邊，文獻(xiàn)[6]利用歐拉路徑對(duì)數(shù)字微流控陣列進(jìn)行測(cè)試并利用二分搜索進(jìn)行故障診斷，它首先將數(shù)字微流控陣列抽象成圖，再對(duì)其歐拉化，最后利用單測(cè)試液滴穿越所有的邊。文獻(xiàn)[7，8]也提出改進(jìn)的基于歐拉路徑的微陣列測(cè)試方法。這些單液滴的測(cè)試方法僅用一個(gè)測(cè)試液滴對(duì)整個(gè)陣列進(jìn)行測(cè)試,導(dǎo)致了測(cè)試時(shí)間過(guò)長(zhǎng)。

為了彌補(bǔ)單液滴測(cè)試的測(cè)試時(shí)間過(guò)長(zhǎng)的問(wèn)題，提出了利用多液滴對(duì)數(shù)字微流控芯片陣列進(jìn)行并行測(cè)試的方法[9～12]，它們將數(shù)字微流控芯片陣列劃成不同的子區(qū)，并分別利用一個(gè)測(cè)試液滴對(duì)每個(gè)子區(qū)進(jìn)行訪問(wèn)，達(dá)到測(cè)試的目的。這些多測(cè)試液滴并行測(cè)試的方法都取得了較好的陣列測(cè)試效果，提高了測(cè)試效率，但它們需要同時(shí)對(duì)多個(gè)測(cè)試結(jié)果液滴進(jìn)行檢測(cè)，而數(shù)字微流控芯片上的光學(xué)檢測(cè)器數(shù)量有限，這就涉及如何用數(shù)量有限的光學(xué)檢測(cè)器同時(shí)檢測(cè)多個(gè)結(jié)果液滴的問(wèn)題。

由于數(shù)字微流控芯片的可配置性，不僅需要對(duì)芯片陣列進(jìn)行準(zhǔn)確的測(cè)試，而且要確定發(fā)生故障的確切位置，即所謂的測(cè)試診斷。基于單個(gè)液滴的測(cè)試方法僅用一個(gè)測(cè)試液滴穿越所有的邊，不僅測(cè)試時(shí)間過(guò)長(zhǎng)，而且測(cè)試診斷較復(fù)雜。雖然多液滴并行測(cè)試方法減少了測(cè)試時(shí)間，但會(huì)出現(xiàn)對(duì)無(wú)故障單元進(jìn)行多次測(cè)試的問(wèn)題，即測(cè)試冗余問(wèn)題。為了揭示芯片單元陣列出錯(cuò)概率、測(cè)試時(shí)間，液滴檢測(cè)成本與測(cè)試總成本之間的關(guān)系，本文為測(cè)試和診斷過(guò)程建立數(shù)學(xué)模型，并用Matlab對(duì)其進(jìn)行分析，為測(cè)試診斷過(guò)程提供重要理論依據(jù)和測(cè)試診斷方法指導(dǎo)。

2 測(cè)試診斷過(guò)程建模和成本函數(shù)的計(jì)算

為了對(duì)數(shù)字微流控芯片的測(cè)試診斷過(guò)程進(jìn)行建模，將芯片陣列抽象成圖，并分成相同大小的子陣列。以16×16規(guī)模的芯片為例，采用的分塊過(guò)程描述如下：最簡(jiǎn)單的是單液滴測(cè)試，即不對(duì)陣列分塊，僅用一個(gè)測(cè)試液滴實(shí)現(xiàn)對(duì)整個(gè)陣列單元的測(cè)試，這個(gè)分塊稱為第0輪分塊，即x=0，這時(shí)的陣列稱為0陣列，發(fā)現(xiàn)故障發(fā)生在右半側(cè)如圖1a所示；第一輪分塊，指利用二分法將芯片陣列分成同等大小的兩塊，此時(shí)x=1，對(duì)應(yīng)分塊后的陣列稱為1陣列，如圖2b所示；第二輪分塊指再對(duì)1陣列的故障子陣列進(jìn)行二分法，x=2，對(duì)應(yīng)分塊后的陣列稱為2陣列，如圖2c所示；這樣在每輪診斷中，都針對(duì)故障子陣列再進(jìn)行二分定位，直到確定故障的確切位置。用x表示分塊輪數(shù)，則最壞的情況每輪的每個(gè)子陣列都存在故障，則第m輪分塊后，x=m，芯片陣列被分成2m個(gè)子塊。

Figure 1 Sub-arrays dividing for parallel tesing圖1 并行測(cè)試的分塊過(guò)程

Figure 2 An example of binary divding for diagnosis圖2 二分法診斷過(guò)程的例子

假設(shè)數(shù)字微流控芯片陣列單片的出錯(cuò)概率為p，對(duì)陣列分塊輪數(shù)為x(x=0,1,2,3,…)，則本文討論的測(cè)試診斷過(guò)程所涉及的問(wèn)題可以描述為：測(cè)試診斷成本與出錯(cuò)概率p和分塊輪數(shù)x之間的確切關(guān)系是什么？具體描述為：

給定n×n規(guī)模的數(shù)字微流控陣列，其中每個(gè)單元的出錯(cuò)概率為p，并行測(cè)試的分塊輪數(shù)為x，確定測(cè)試診斷成本與p和x的關(guān)系。

對(duì)于第二個(gè)和第三個(gè)指標(biāo)，其引起的測(cè)試成本跟p有關(guān)，因?yàn)槊看卧\斷不是必須的，只需要針對(duì)有故障的區(qū)域進(jìn)行診斷。本文利用二分診斷方法對(duì)芯片陣列進(jìn)行診斷，以16×16的芯片陣列的單液滴測(cè)試為例，診斷過(guò)程在圖2中給出。如圖2所示，首先用單個(gè)液滴對(duì)芯片陣列進(jìn)行測(cè)試(圖2a)，經(jīng)過(guò)檢測(cè)結(jié)果液滴可以發(fā)現(xiàn)是否存在故障，若存在故障，則需要對(duì)其進(jìn)行再次診斷。仍采用二分法，將出錯(cuò)的子陣列區(qū)域劃分成同等大小的兩個(gè)子區(qū)域，分別用單液滴對(duì)這兩個(gè)子陣列進(jìn)行測(cè)試，經(jīng)過(guò)測(cè)試發(fā)現(xiàn)右側(cè)出現(xiàn)故障，如圖2b所示。再對(duì)右側(cè)進(jìn)行二分診斷，發(fā)現(xiàn)錯(cuò)誤發(fā)生在右上側(cè)，且已經(jīng)確定了故障的存在位置，診斷過(guò)程結(jié)束。

(1-p)n×n/2x+m-1)i×((n×n)/2i+i)

(1-p)n×n/2j-1)i×((n×n)/2i+i)

至此，我們已經(jīng)對(duì)測(cè)試和診斷過(guò)程的相關(guān)測(cè)試成本進(jìn)行了分析建模，即成本函數(shù)描述為：給定n×n規(guī)模的數(shù)字微流控陣列，其中每個(gè)單元的出錯(cuò)概率為p，確定分塊輪數(shù)x，測(cè)試診斷成本與x和p之間的關(guān)系可以表示為成本函數(shù)：

TDcost=(Tcost+Diam)

3 針對(duì)常用規(guī)模芯片陣列的測(cè)試診斷過(guò)程分析

3.1 分析過(guò)程

為了分析數(shù)字微流控芯片測(cè)試診斷成本與分塊輪數(shù)、單元出錯(cuò)概率之間的關(guān)系，本小節(jié)針對(duì)常用規(guī)模的數(shù)字微流控芯片的并行測(cè)試診斷過(guò)程進(jìn)行分析，以減少測(cè)試成本并獲得最優(yōu)的測(cè)試診斷方案，本過(guò)程用Matlab對(duì)測(cè)試診斷成本TDcost進(jìn)行了分析。

Figure 3 Surface Plot of test cost for 16×16 biochip array圖3 16×16芯片陣列測(cè)試成本三維曲面圖

Figure 4 Surface plot of test cost for 32×32 biochip array圖4 32×32芯片陣列測(cè)試成本三維曲線圖的變化

針對(duì)32×32規(guī)模芯片陣列的分析結(jié)果如圖4所示。為了放大觀察分塊輪數(shù)x和單元出錯(cuò)概率p對(duì)測(cè)試成本TDcost的影響，x變化范圍為1～4和4～9的放大圖分別在圖4a和圖4b中給出。從圖4中可以看出，測(cè)試診斷成本仍舊隨著分塊輪數(shù)x的變化無(wú)明顯變化趨勢(shì)，而隨著單元出錯(cuò)概率p的增加呈現(xiàn)明顯的升高趨勢(shì)。我們通過(guò)對(duì)數(shù)據(jù)觀察發(fā)現(xiàn)，無(wú)論x如何變化，診斷成本根據(jù)單元出錯(cuò)概率計(jì)算每一輪的診斷成本，而每輪診斷成本之間相差若干個(gè)、甚至幾十個(gè)數(shù)量級(jí)，診斷成本中包含對(duì)應(yīng)最后一輪診斷的最高數(shù)量級(jí)的成本，所以x的變化對(duì)診斷成本TDcost影響較小。圖4c和圖4d中分別給出了p的變化范圍為0.1～0.5和0.5～0.99對(duì)應(yīng)的測(cè)試成本的曲面圖。從圖4中可以看出，p處在不同的范圍時(shí)，總的測(cè)試成本TDcost的變化趨勢(shì)相同，即隨著p的增大而顯著增大，但不同范圍的測(cè)試成本之間相差多個(gè)數(shù)量級(jí)。

3.2 相關(guān)結(jié)論

從對(duì)16×16和32×32規(guī)模的數(shù)字微流控芯片陣列規(guī)模的測(cè)試診斷成本TDcost的分析結(jié)果來(lái)看，測(cè)試診斷成本TDcost隨著單元故障概率p的增加呈明顯增加的趨勢(shì)，且增加的幅度非常大，相差十幾甚至幾十個(gè)數(shù)量級(jí)。而隨著分塊數(shù)2x的增加，測(cè)試成本沒(méi)有明顯的變化趨勢(shì)，這是因?yàn)闊o(wú)論分成多少塊，都需要根據(jù)單元出錯(cuò)概率對(duì)出錯(cuò)的子陣列再進(jìn)行診斷，診斷過(guò)程必須持續(xù)到最后故障的定位，而針對(duì)定位時(shí)的診斷成本是最大的，也決定了總成本TDcost的大小。所以，分塊輪數(shù)x對(duì)總的測(cè)試診斷成本的影響不大。這些結(jié)論對(duì)數(shù)字微流控芯片的測(cè)試診斷有著重要指導(dǎo)意義，為數(shù)字微流控芯片的測(cè)試診斷方法的設(shè)計(jì)提供了重要依據(jù)。

4 結(jié)束語(yǔ)

本文針對(duì)數(shù)字微流控芯片陣列的測(cè)試診斷過(guò)程進(jìn)行建模和分析，為測(cè)試診斷成本建立函數(shù)，在對(duì)常用規(guī)模的芯片陣列進(jìn)行分析的基礎(chǔ)上發(fā)現(xiàn)：測(cè)試診斷成本隨著單元故障概率的增加呈明顯升高的趨勢(shì)，而隨著并行測(cè)試的分塊數(shù)的增加并無(wú)明顯變化趨勢(shì)。另外，利用二分法進(jìn)行故障診斷的過(guò)程中，每次涉及的故障子陣列的測(cè)試成本之間差別非常大，從幾個(gè)數(shù)量級(jí)到幾十個(gè)數(shù)量級(jí)，因此導(dǎo)致了分塊輪數(shù)x對(duì)測(cè)試診斷成本幾乎沒(méi)有影響。這些結(jié)論為數(shù)字微流控芯片的測(cè)試診斷方法的設(shè)計(jì)提供了重要依據(jù)。

[1] Zhao Y,Chakrabarty K.Testing of low-cost digital microfluidic biochips with non-regular array layouts[C]∥Proc of the 19th IEEE Asian Test Symposium, 2010:27-32.

[2] International technology roadmap for semiconductor (ITRS)[EB/OL].[2003-12-15].http://public.itrs.net/Files/2003ITRS/ Home2003.htm.

[3] Su F, Ozev S, Chakrabarty K.Testing of droplet-based microelectrofluidic systems[C] ∥Proc of the IEEE International Test Conference, 2003:1192-1200.

[4] Su F, Ozev S, Chakrabarty K. Test planning and test resource optimization for droplet-based microfluidic systems[C]∥Proc of the IEEE European Test Symposium, 2004:72-77.

[5] Su F, Hwang W, Mukherjee A, et al. Defect-oriented testing and diagnosis of digital microfluidics-based biochips[C]∥Proc of the IEEE International Test Conference, 2007:21-22.

[6] Mitra D, Ghoshal S, Rahaman H, et al,Testing of digital microfluidic biochips using improved eulerization techniques and the Chinese postman problem[C]∥Proc of the 19th IEEE Asian Test Symposium (ATS), 2010:111-116.

[7] Mitra D, Ghoshal S, Rahaman H, et al. Test planning in digital microfluidic biochips using efficient eulerization techniques[J]. Journal of Electronic Testing:Theory and Applications, 2011,27(5):1-15.

[8] Zhao Y, Chakrabarty K, Bhattacharya B B. Testing of low-cost digital microfluidic biochips with non-regular array layouts[J]. Journal of Electronic Testing, 2012,28(2):243-255.

[9] Zhang L, Kuang J S, Lin J, et al. Parallel on-line testing for digital microfluidic biocip[J]. Journal of Shanghai Jiaotong University(Science),2013,47(1):98-102.(in Chinese)

[10] Su Fei, Ozev S, Chakrabarty K. Concurrent testing of digital microfluidics-based biochips[J].ACM Transactions on Design Automation of Electronic System, 2006, 11(2):442-464.

[11] Xu T, Chakrabarty K. Parallel scan-like testing and fault diagnosis techniques for digital microfluidic biochips[C]∥Proc of the 12th IEEE European Test Symposium, 2007:63-68.

[12] Xu T, Chakrabarty K. Parallel scan-like test and multiple-defect diagnosis for digital microfluidic biochips[J]. IEEE Transactions on Biomedical Circuits and Systems, 2007,1(2):148-158.

附中文參考文獻(xiàn)：

[9] 張玲，鄺繼順，林靜，等.數(shù)字微流控制生物芯片的并行在線測(cè)試[J].上海交通大學(xué)學(xué)報(bào)(自然版)，2013,47(1):98-102.

ZHANG Ling,born in 1980,PhD candidate,lecturer,her research interests include IC testing， and digital microfluidic biochip testing.

Analysis and optimization of test and diagnosis process for digital microfluidic biochip

ZHANG Ling1,2,KUANG Ji-shun2,MEI Jun-jin1,LIN Jing1
(1.School of Computer,Hubei Polytechnic University,Huangshi 435003;2.School of Computer and Communication,Hunan University,Changsha 410082,China)

To achieve the test and diagnosis solution for digital microfluidic biochip, the test and diagnosis process is modeled, and the corresponding diagnosis test cost is computed. The test and diagnosis cost is analyzed by the tools of Matlab, and some important observations are obtained: Firstly, with the increase of the number of sub-arrays divided for parallel testing, the test and diagnosis cost nearly does not change at all. In other words, the number of sub-arrays has less impact on the test and diagnosis cost. Secondly, as the faulty probability of the single biochip cell increases, the test and diagnosis cost increases dramatically. In addition, in the process of the diagnosis, the faulty domain must be diagnosed according to the corresponding faulty probability until all the faults are located. The test and diagnosis cost of the last faulty location is the maximum, dominating the total test and diagnosis cost of the biochip. These observations provide the theory evidence and guidance for digital microfuidic biochip test and diagnosis.

digital microfluidic biochip;biochip array;test and diagnosis;test cost

2013-06-06;

2013-08-29

湖北省教育廳科研項(xiàng)目(B2013061)

1007-130X(2014)03-0411-05

TP302

A

10.3969/j.issn.1007-130X.2014.03.006

張玲(1980-),女,安徽濉溪人，博士生，講師，研究方向?yàn)榧呻娐窚y(cè)試和數(shù)字微流控芯片測(cè)試。E-mail:forry1230@126.com

通信地址：435003 湖北省黃石市湖北理工學(xué)院計(jì)算機(jī)學(xué)院

Address:School of Computer,Hubei Polytechnic University,Huangshi 435003,Hubei,P.R.China