許川佩 陳春艷 汪杰君

1 引言

微流控芯片實驗室又稱微流控芯片、芯片實驗室（Lab-on-a-Chip, LoC）或生物微機電系統（bio-MEMS），而基于離散流體的微流控生物芯片又稱為數字微流控生物芯片（Digital MicroFluidic Biochips,DMFBs）[1]，它代替了笨重和昂貴的實驗室設備，在高通量測序、并行的免疫分析、蛋白質結晶、血液的臨床化學診斷和環(huán)境的毒性檢測等生化領域得到了廣泛的應用[2]，這些領域對可靠性的要求非常嚴格，因此在數字微流控生物芯片工作時，對其進行有效的測試是確保芯片可靠工作不可缺少的重要手段。

數字微流控生物芯片依照引腳的控制方式不同分為直接尋址和引腳受限兩種。直接尋址生物芯片的每個電極對應一個控制引腳，任意一個引腳都能夠單獨激活，因此這種方法允許最大自由操縱液滴，但是引入了過多的控制引腳，顯著增加產品的制造成本。引腳受限的數字微流控生物芯片的多個引腳共用一個電極[35]-，因此可有效降低制造成本。由于引腳受限的芯片電極間存在共用引腳的情況，相比直接尋址的芯片，操縱液滴的自由度受到限制，測試難度更大。本文主要研究引腳受限的數字微流控生物芯片在線測試方法，以保證芯片工作的穩(wěn)定可靠。

2 DMFBs測試研究進展

隨著技術的不斷發(fā)展，數字微流控生物芯片越來越復雜，各種生產故障和物理故障都可能出現在芯片中。針對生產故障，文獻[6]指出可通過帶電的控制和跟蹤液滴的移動來確定故障的位置。但是由于在實驗中也會產生故障，因此，文獻[7]針對實驗中出現的突變性故障提出了一個數字微流控陣列的突變性故障檢測優(yōu)化方法，該方法首先把數字微流控生物陣列轉化為圖論模型，再把圖論模型中的問題用漢密爾頓路徑公式化，但是該方法卻無法檢測到電極短路的故障。因此為測試該類故障，文獻[8]提出了基于歐拉回路的測試方法，該方法可有效地檢測到電極短路的故障。Xu等人[9]提出了一種并行掃描式的測試方法，即多液滴并行的遍歷微流控陣列來實現故障檢測，雖能有效地減少測試時間，但是在線測試時，該方法由于測試路線一定，測試過程中存在的干擾會使測試時間大量增加，降低測試效率。張玲等人[10,11]針對DMFBs在線測試進行了研究，借鑒文獻[12]中的并行測試方法，將芯片陣列分為相同大小的子陣列，在與實驗液滴互不干擾的情況下，對電極陣列進行測試，提高了測試效率。

上述提到的測試方案都是針對直接尋址芯片陣列單元進行遍歷，然而對有引腳約束的芯片卻沒有開展研究。因此，本文提出一種針對引腳約束芯片的在線并行測試方案。鑒于最大最小蟻群算法（MMAS）是對傳統蟻群算法的一種改進，是解決TSP, MTSP等問題最好的蟻群優(yōu)化算法之一[13]，本文將芯片陣列轉換為 TSP或 MTSP模型[14]，將MMAS用于引腳約束數字微流控生物芯片在線并行測試，以獲得最短路徑，提高測試效率。

3 DMFBs測試

3.1 DMFBs工作原理

數字微流控生物芯片利用介電潤濕的原理在 2維的電極陣列中操縱和移動納升級的離散液滴[15]。如圖1所示，數字微流控生物芯片的基本單元包括兩個平板和夾在平板中間的填充（硅油），液滴在填充介質內運行。底板包含一個單獨可控的電極陣列，頂板覆蓋了一層連續(xù)的地線。通過改變沿著電極的一個線性陣列的電勢，液滴可以沿著電極的一條線移動?？梢酝ㄟ^調整控制電壓（0～90 V）來控制液滴的速度，液滴最高能夠以20 cm/s的速度移動?；谶@一原理，液滴能夠很自由地移動到2維陣列的任何位置而不需要微型泵和微型閥。

圖1 芯片的工作原理

3.2 DMFBs測試模型

DMFBs故障主要分為永久性故障和參數故障[6]，其中永久性故障會造成DMFBs系統液滴無法移動，因此可根據測試液滴能否移動判斷是否存在故障，即利用測試液滴從液滴源出發(fā)，在電極陣列單元上移動，如果液滴停留在某單元上不能移動，則該單元為故障單元[6]。因此，DMFBs的永久性故障可以通過液滴遍歷電極陣列單元來檢測，這種遍歷問題可轉換為網絡問題，即將陣列單元結構抽象為圖論中的圖模型。將數字微流控生物芯片的電極陣列單元看成一個無向圖（,）G V E，其中V表示微流控陣列單元，E表示兩個直接鄰近單元之間所構成的邊，以此規(guī)則構造的5×5的微流控電極陣列轉換圖如圖2所示。

圖2 5×5的芯片電極轉換圖

在數字微流控生物芯片測試中，測試目標是在帶權有向圖G中（這里的權值指的是兩條邊的距離），尋找從液滴源出發(fā)，測試完所有的邊E后到達廢液池的最短測試路徑，即最短測試時間。用m個液滴對數字微流控生物芯片的電極陣列進行測試，電極陣列的所有單元都應當至少被訪問1次，表示為

其中， xi表示陣列單元，n表示芯片總的單元數。

由于DMFBs相鄰流體之間存在干擾，共用電極引腳之間存在約束，m個液滴同時對DMFBs進行測試的過程中存在起點和終點、靜態(tài)和動態(tài)流體約束以及共用電極引腳約束。

（1）起點和終點約束： 在每次測試中，液滴從液滴源s出發(fā)，且s只能被訪問1次。液滴完成測試后到達廢液池d，且d只能被訪問1次，可表示為

（2）靜態(tài)和動態(tài)流體約束： 當兩個液滴相鄰時，液滴之間會相互融合，產生干擾，靜態(tài)約束表示兩液滴不能處于直接鄰近或對角鄰近的陣列單元位置。動態(tài)約束表示一個液滴下一步所走的單元不能鄰近另一個液滴，否則會導致另一個液滴附近產生多于一個的激活單元，影響液滴的下一步操作。

定義 Al

t1, Blt1分別為液滴l1在時間t時所在的單元的行與列， Alt2, Blt

2分別為液滴l2在時間t時所在單元的行與列。

則靜態(tài)流體約束表示為

動態(tài)流體約束表示為

（3）共用電極引腳約束： 圖3是一個典型的存在引腳約束的聚合酶鏈反應的芯片[3]。當實驗液滴和測試液滴在圖3中所示位置時，實驗液滴所在的電極由引腳11控制，當該電極被激活時，測試液滴鄰近由引腳11控制的電極也被激活，此時測試液滴就不能向引腳11控制的電極移動。

因此，為避免共用引腳影響液滴的移動，定義Nkt為測試液滴k在t時刻所在單元的電極引腳編號， Net為實驗液滴e在t時刻所在單元的電極引腳編號，則

根據式（5）來避免共用電極引腳對測試液滴的影響。

圖3 共用電極干擾示例

4 基于改進MMAS的引腳約束DMFB在線并行測試

為提高實驗效率，數字微流控生物芯片一般包含多對起始節(jié)點（液滴源）和目標節(jié)點（廢液池），因此，本文采用MMAS安排多個螞蟻同時從起始節(jié)點出發(fā)，對整個芯片進行并行搜索，以此減少測試時間。同時，為避免算法在求解大規(guī)模復雜問題時出現早熟、停滯現象，采用改進MMAS自適應地調整信息素的殘留系數提高算法的全局搜索能力。在此基礎上為保證解的多樣性，對算法的選擇策略進行改進，增加偽隨機比例原則。對芯片的引腳約束和液滴之間的約束，采用禁忌判斷策略實現。

4.1 并行測試策略

當芯片的測試問題轉換成MTSP模型后，采用MMAS對轉換的模型進行測試，即有a組螞蟻（每組螞蟻有m只）同時從a個不同的起始點出發(fā)，訪問所有的邊后到達目標節(jié)點。當a組螞蟻遍歷完陣列單元所有邊后，遍歷完成，螞蟻停止搜索。迭代過程中每組螞蟻都可以生成一組最優(yōu)解，并行測試的最優(yōu)時間是a組遍歷時間的最大值，目標函數如式（6）和式（7）所示：

式（6）表示每組m只螞蟻在迭代完成后的最優(yōu)時間，指的是所有螞蟻對芯片遍歷完成后用時之和的最小值，其中 tk表示第k只螞蟻的遍歷時間，Ti表示第i組螞蟻的最優(yōu)測試時間。式（7）表示a組螞蟻并行搜索的最優(yōu)時間。

4.2 選擇策略的改進

在基本蟻群算法中，t時刻位于單元i的螞蟻根據式（8）選擇下一個單元j。式中α和β是決定信息素和可見性的兩個重要參數。 a ln表示螞蟻下一步所選的單元， ηij（t）為啟發(fā)函數，在本文定義 ηij（t） = 1 /dij，其中 dij表示節(jié)點i和節(jié)點j之間的距離，τij（t）表示在t時刻單元i到單元j上的信息素強度。

為避免螞蟻在開始搜索時以較大的概率集中在當前最優(yōu)路徑上，本文采用偽隨機比例原則選擇路徑。因此，可以讓螞蟻根據式（9）從單元i選擇下一個單元j。

式中 q0∈ （ 0,1）, q是均勻分布在（0,1）的隨機數，J是根據式（8）所選擇的節(jié)點。這樣，在開始就增加螞蟻的選擇單元，確保路徑的多樣性。

4.3 禁忌判斷策略

在線測試的時候，會存在 3.2節(jié)描述的液滴靜態(tài)和動態(tài)的干擾，以及引腳約束的干擾。為了避免干擾出現，首先建立液滴測試禁忌表，把實驗液滴及其下一步所走單元、實驗液滴周圍的對角鄰近和非對角鄰近單元、當前時間實驗液滴所在電極引腳編號存放到禁忌表中，實驗液滴每走一步更改一次禁忌表。測試液滴在測試的過程中每走一步就要判斷其是否在禁忌表中，如果不在禁忌表中，液滴可以繼續(xù)進行測試；如果在禁忌表中，當測試液滴等待時間加上測試液滴運行到這條邊上的權值小于其它邊的權值時，測試液滴選擇等待，反之，選擇向其它權值小的邊運行，等待時間為實驗液滴從一個電極運行到另一個電極的時間。

4.4 信息素更新策略的改進

MMAS只允許其中最優(yōu)路徑更新信息素。更新規(guī)則為

其中， ρ 表示信息素殘留系數； Δ τbij= 1 /f（ sb）,f（ sb）表示為第i次迭代的最優(yōu)路徑sib的長度，或全局最優(yōu)路徑 sgb的長度。

但當測試規(guī)模較大時，信息素殘留系數ρ的存在，使得那些沒有被搜索到的路徑上的信息量逐漸減少，降低算法搜索的全局性。本文通過自適應地調整ρ的大小來解決這一問題，改進方法如式（11）所示。

4.5 信息素限制和初始化

在一次迭代完成后將各條路徑上的信息素限制在[τmin,τmax]之間，超出范圍的值將按照式（12）進行判斷來避免算法過早地收斂于全局最優(yōu)解。

信息素初始化中，設定 τ （0）=τmax來增加螞蟻在初始階段探索新解的能力。其中τmin和τmax定義為

4.6 算法流程

根據上文對算法的描述，基于改進MMAS的引腳約束 DMFB在線并行測試的算法流程如圖 4所示。

5 實驗結果與分析

圖4 MMAS在線并行測試

本文以文獻[3]的引腳約束生物芯片為例驗證本文方法的有效性。如圖5所示，多功能生物鑒定和聚合酶鏈反應（PCR）分別映射到一個15×15的數字微流控生物芯片上。圖 5（a）中，多功能生物鑒定包含一個葡萄糖陣列和一個乳酸鹽陣列，兩組樣本（S1,S2）和試劑（R1, R2）被分發(fā)到陣列中。其中 S1和 R1為葡萄糖檢測實驗液滴，S1中含有葡萄糖，R1中含有氧化酶等反應試劑；S2和R2為乳酸鹽檢測實驗液滴，S2中含有乳酸，R2含有氧化酶等反應試劑。有4 對液滴即（S1, R1）, （S2, R1）, （S1, R2）, （S2, R2）分別進行混合操作（M1-M4），混合后的液滴路由到檢測位置（D1-D4）進行分析檢測。多功能生物鑒定的具體操作流程如圖 6（a）所示。圖 5（b）所示的 PCR 鑒定用于檢測特定 DNA鏈酶的快速擴增，主要是通過溫度變化控制 DNA的變性和復性，并設計引物做啟動子，加入 DNA聚合酶實現特定基因的體外復制。PCR鑒定通過DNA模板解鏈，引物與模板結合，DNA聚合酶催化新生DNA合成3個步驟完成一個循環(huán)，多次循環(huán)后，目的 DNA可得以迅速擴增，具體檢測流程如圖6（b）所示。

圖5 15×15的電極陣列

圖7 是典型的多功能生物鑒定和PCR鑒定的引腳約束的芯片的設計[3]，多功能生物鑒定生物芯片由最初所需的59個電極減少到了25個電極，PCR鑒定生物芯片由最初所需的62個電極減少到14個電極，其中電極上的標號表示電極所用引腳標號，相同標號的電極表示它們共用一個控制引腳。對該生物芯片利用改進MMAS尋找多條并行測試路徑，以實現液滴并行測試。經過多次實驗，將實驗參數設置為：兩組螞蟻（a = 2 ）同時進行測試，每組螞蟻有25只（m = 2 5）, q0=0.9, α=1, β=2, ρ= 0 .95,ρmin= 0 .45, q= 0 .1, τmax= 4 20, τmin= 0 .42,NC= 2 000，在單液滴測試時設置螞蟻數 m = 5 0。

（1）實驗結果分析： 實驗結果如圖8所示，其中縱坐標表示芯片測試所花費的單位時間，這里的單位時間指的是液滴在16 Hz的變換頻率、50 V驅動電壓下從一個陣列單元移動到相鄰的陣列單元所花費的時間，約62.5 ms[16]。對于有引腳約束的數字微流控生物芯片的多功能生物鑒定和PCR鑒定，單液滴離線測試時，由于不存在實驗液滴，因此引腳約束對其無影響，兩者測試都花費456個單位時間；單液滴在線測試時由于存在實驗液滴和引腳約束的影響，多功能生物鑒定花費490個單位時間，PCR鑒定花費494個單位時間；多液滴并行測試多功能生物鑒定花費322個單位時間，相對于單液滴離線和在線測試分別減少 29%和 38%, PCR鑒定花費320個單位時間，相對于單液滴離線和在線測試分別減少30%和35%。由兩種生物鑒定的測試結果可知，基于MMAS的多液滴并行在線測試可以有效地減少測試時間，提高測試效率。

圖6 多功能生物鑒定與PCR鑒定具體操作流程

圖7 DMFB引腳分配

圖8 測試結果

（2）算法收斂性分析： 由于引腳受限多功能生物鑒定和PCR鑒定測芯片結構相似，本文根據多功能生物鑒定實驗下的單液滴離線測試、單液滴在線測試、多液滴并行測試的迭代結果進行算法的收斂性分析。

如圖9所示，橫坐標表示算法迭代次數，縱坐標表示測試單位時間。最大最小蟻群算法初始階段由于缺乏信息素的指引，其收斂速度較慢，但隨著探索新路徑的螞蟻逐漸增加，各條邊上的信息素值的差異逐漸變大，根據最大最小蟻群算法信息素值的限制，算法最終達到收斂狀態(tài)。單液滴在線測試過程中，由于在線測試約束條件的存在，算法在運行到1310代時收斂，收斂速度比在1195代收斂的單液滴離線測試慢。多液滴并行測試中，雖然并行在線測試時也存在約束條件的限制，但是由于多組液滴同時對芯片進行測試，算法在運行646代時收斂，收斂速度要比單液滴在線測試和單液滴離線測試都快，驗證了本文方法的有效性。

圖9 改進MMAS收斂圖

（3）算法效率分析 基于改進 MMAS的單組螞蟻對芯片進行離線和在線測試的空間復雜度S（ n）=O（ n2），多組螞蟻對芯片同時進行測試時，由于芯片總的單元數不變，多組螞蟻遍歷的單元總數與單組螞蟻遍歷的總數相同，所占的存儲容量相同。因此，本文采用的多液滴并行測試方法的空間復雜度不變，即 S （ n ） = O （ n2） 。時間復雜度分析：基于改進MMAS的單組螞蟻對芯片進行離線和在線測試的時間復雜度 T （ n ） = O （ n2） ，本文采用多組螞蟻同時對芯片進行測試，算法的時間復雜度變?yōu)門（ n）=O（ n2）/a（這里的a指的是螞蟻的分組數），縮短了算法運行時間。綜上所述，在空間復雜度相同的情況下，本文方法降低了算法的時間復雜度，提高算法的運行速度。

6 結束語

引腳約束的數字微流控芯片在線并行測試，在禁忌判斷約束下，通過改進MMAS選擇策略，自適應地調整信息素的殘留系數來尋找多液滴并行測試路徑，加快算法的收斂速度。實驗結果表明多液滴并行測試的時間相對單液滴在線測試的時間明顯減少，甚至比單液滴離線測試時間還少。驗證了本文方法適用于芯片的離線和在線測試，可有效地解決數字微流控生物芯片的在線測試問題。

[1] Xu T and Chakrabarty K. Fault modeling and functional test methods for digital microfluidic biochips[J]. IEEE Transactions on Biomedical Circuits and Systems, 2009, 3（4）:241-253.

[2] 楊敬松, 姚振靜, 宋燕星, 等. 數字微流控生物芯片布局的擬人遺傳組合算法[J]. 計算機工程與應用, 2012, 48（31）: 16-20.Yang Jing-song, Yao Zhen-jing, Song Yan-xing, et al..Personification and genetic combinational algorithm for placement problem of digital microfluidics-based biochips[J].Computer Engineering and Applications, 2012, 48（31）: 16-20.[3] Xu T and Chakrabarty K. Broadcast electrode-addressing and scheduling methods for pin-constrained digital microfluidic biochip[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 30（7）:986-999.

[4] Luo Y and Chakrabarty K. Design of pin-constrained general-purpose digital microfluidic biochips[J]. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 2013, 32（9）: 1307-1320.

[5] Grissom D T, McDaniel J, and Brisk P. A low-cost fieldprogrammable pin constrained digital microfluidic biochip[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33（11）: 1657-1670.

[6] Su F, Ozev S, and Chakrabarty K. Testing of droplet-based microelectrofluidics systems[C]. Proceedings IEEE International Test Conference, Charlotte, 2003: 1192-1200.[7] Su F, Ozev S, and Chakrabarty K. Test planning and test resource optimization for droplet-based microfluidic systems[J]. Journal of Electronic Testing: Theory and Applications,2006, 22（2）: 199-210.

[8] Su F, Hwang W, Mukherjee A, et al.. Testing and diagnosis of realistic defects in digital microfluidic biochips[J]. Journal of Electronic Testing: Theory and Applications, 2007, 23（2/3）:219-233.

[9] Xu T and Chakrabarty K. Paralled scan-like test and multiple-defect diagnosis for digital microfluidic biochips[J].IEEE Transactions on Biomedical Circuits and Systtems,2007, 1（2）: 148-158.

[10] 張玲, 鄺繼順, 林靜, 等. 數字微流控生物芯片的并行在線測試[J]. 上海交通大學學報, 2013, 47（1）: 98-102.Zhang Ling, Kuang Ji-shun, Lin Jing, et al.. Parallel on-line testing for digital microfluidic biochip[J]. Jouranl of Shanghai Jiao Tong University, 2013, 47（1）: 98-102.

[11] 張玲, 鄺繼順, 梅軍進, 等. 數字微流控生物芯片測試診斷過程分析和優(yōu)化[J]. 計算機工程與科學, 2014, 36（3）: 411-415.Zhang Ling, Kuang Ji-shun, Mei Jun-jin, et al.. Analysis and optimization of test and diagnosis process for digital microfluidic biochip[J]. Computer Engineering and Science,2014, 36（3）: 411-415.

[12] Su F, Ozev S, and Chakrabarty K. Concurrent testing of droplet-based microfluidic systems for multiplexed biomedical assays[C]. Proceedings IEEE International Test Conference, Charlotte, 2004: 883-892.

[13] 楊延慶, 李鵬飛, 何博. 求解 TSP問題的改進最大最小蟻群算法[J]. 西安工程大學學報, 2010, 24（6）: 818-821.Yang Yan-qing, Li Peng-fei, and He Bo. The solution of TSP based on the improved max-min ant colony algorithm[J].Journal of Xi’an Polytechnic University, 2010, 24（6）:818-821.

[14] 許川佩, 蔡震, 胡聰. 基于蟻群算法的數字微流控生物芯片在線測試路徑優(yōu)化[J]. 儀器儀表學報, 2014, 35（6）: 1417-1424.Xu Chuan-pei, Cai Zhen, and Hu Cong. On-line test path optimization for digital microfluidic biochips based on ant colony algorithm[J]. Chinese Journal of Scientific Instrument,2014, 35（6）: 1417-1424.

[15] Royal M W, Jokerst N M, and Fair R B. Droplet-based sensing: Optical microresonator sensors embedded in digital electrowetting microfluidics systems[J]. IEEE Sensors Journal, 2013, 13（12）: 4733-4742.

[16] Su F, Hwang W, Mukherjee A, et al.. Defect-oriented testing and diagnosis of digital microfluidics-based biochips[C].Proceedings IEEE International Test Conference, Austin,2005: 1-10.