数字微流控芯片主要应用在生物医学等生化领域中，因而对安全指标要求严格，例如：临床诊断，传染性疾病的健康检查、空气质量监测、食品安全测试等。 因此，可靠性是数字微流控生物芯片一项重要的性能指标，而保证系统可靠的重要措施之一就是对芯片进行测试。这种测试不仅存在于芯片生产制造后，生化实验前也要不断地进行测试，以保证系统工作的稳定可靠。 如何对测试液滴的测试路径进行调度是减少芯片测试应用时间的关键问题，而数字微流控芯片阵列测试液滴的调度为资源**下的调度问题，属于NP难问题。 1 数字微流控芯片测试相关背景介绍 数字微流控芯片的测试研究主要集中于故障分类和故障建模，并针对相应故障进行测试诊断。 数字微流控芯片的故障分为突变性故障和参数性故障。突变性故障会使液滴不能移动而造成系统无法工作，如绝缘体击穿，相邻电极短路，电极板断路等故障。 参数性故障主要造成系统运行时出现较大的偏差，如尺寸参数误差，液滴包容介质的黏性变化等。针对这些故障，相关文献指出可通过将液滴在芯片的阵列单元上移动实现故障检测。 有文献提出基于整数线性规划法和基于汉密尔顿图的测试方法，然而这两种方法都无法检测出电极短路故障。 因此另外有文献提出了基于欧拉回路的测试方法，该方法虽然能够侦测到电极短路故障，但是由于采用单个液滴进行测试，应用花费时间较长。 另外有文献提出一种并行扫描式的测试方法，即采用多个测试液滴对芯片阵列进行并行扫描，虽能有效地减少测试时间，但该方法更适合用于离线测试。 还有文献提出过一种并行在线测试方法，将芯片阵列等分为多个子阵列，在不干扰生化实验的**下，利用实验的空隙时间，对空闲子阵列进行合并和调度，实现芯片阵列的并行测试，有效缩短在线测试应用时间。 上述提到的测试方案都是针对芯片的所有阵列单元进行液滴遍历，然而这种测试需要花费更长的测试时间和更多的储液池、废液池等硬件消耗。且随着芯片阵列规模的增加，全芯片测试花费的时间也呈指数增长。 然而实际的生化实验中，实验液滴仅会在综合后的路径上传输。因此在线测试也仅需对实验所需的阵列单元群进行测试，防止实验液滴由于故障而在运输路径上停止，而无需花费多余的时间测试未使用的阵列单元。 对此，本文提出一种针对实验路径测试的方案，该方案采用并行液滴测试，能够大量减少芯片的测试应用时间且适用于在线测试。 由于芯片的实验路径具有灵活性高，路径与路径之间纵横交错等特点， 较类似于网络节点，而蚁群算法作为群体智能的一个典型，具有正反馈、易于作分布式计算、以及建设性的“贪婪”启发式应用特性，能较好地解决此类问题， 因此本文采用蚁群算法优化测试液滴的调度。 2 蚁群算法方案介绍 由上文的研究可知，数字微流控芯片的测试是利用微控制器对电极施加时序电压从而控制和追踪测试液滴的运动来检测故障。 测试液滴从储液池出发，遵循测试规则，通过遍历阵列单元最终到达测试终点。在终点端增加电容检测电路，以电容电压变化判断测试液滴到达，即完成故障测试。 如若存在故障单元，则测试液滴停止在故障单元位置，而无法到达检测电路，从而表明存在故障，反之检测到液滴到达表明芯片测试正常，具体流程如图 1 所示。 图1 数字微流控生物芯片及其测试过程 所以数字微流控生物芯片的测试是对芯片阵列单元的遍历，以检测电极与液滴之间的控制是否存在故障，因此该种遍历问题可转换为网络问题，即将阵列单元结构抽象为图论中的图模型。 测试模型 将芯片经过综合后的实验模块和路径映射为二维带权图G(V，E)，其中V 表示实验中的液滴储液池、废液池、融合区等实验模块;E表示各模块之间的路径，若两模块之间有路径相连，则相应的节点连通，路径上的权值表示两模块之间所经过的阵列单元数，如图2 所示。 图2 生化实验对应的二维带权图 由于图 G(V，E)为非完全连通图，所以将图 G 中任意两点间的最短长度作为两点间边的权值，并以此构造出一个完全连通图 G’。 采用 Floyd算法求此最短路径。具体步骤如下： (1)从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 (2)对于每一对顶点U和V，是否存在一个顶点W 使得从U 到W 再到V 的路径长度比已知的更短，如果存在则更新。将得到的无向完全图 G’ 作为问题模型，利用蚁群算法寻找多条优化测试路径。 蚁群算法搜索测试路径 针对大规模的数字微流控生物芯片，单液滴测试会耗费较长的应用时间，因此需采用多液滴并行测试提高效率。 经过上文所述的模型映射后，芯片的测试问题可以转换为 MTSP 问题，即m个测试液滴从起点出发，根据分配的多组测试路径，分头去访问 n-2 个节点，最终到达终点。 而蚁群算法中，每只蚂蚁均可构造问题的一个解，因此将采用m组蚂蚁共同搜索并行测试路径，每组蚂蚁有k只。 并行策略 对于第i(i=1，2，…，m)组的蚂蚁j(j=1，2，…，k)，从储液池出发，访问mij个节点后到达废液池，其中mij是蚂蚁j出发之前按一定规则随即生成的整数，表示其能经过的节点数。因此mij需满足 该式表示蚂蚁所经过的节点数必须超过2个，且一组蚂蚁所经过的节点需覆盖除储液池和废液池外的全部阵列单元。 同时，为第i(i =1，2，…，m)组的每一只蚂蚁 j(j =1，2，…，k)分配路径表eij，记录蚂蚁j当前已遍历的节点。当eij中的元素个数等于mij时，蚂蚁停止搜索并直接到达废液池。 当所有的路径{ei1，ei2，…，eik}，(i =1，2，…，m)完成后，即可构成了相应的测试路径。每次迭代中m组蚂蚁可生成m组解。 概率选择策略 选择策略采用伪随机比例规则既可利用关于问题 的先验知识，即关于节点之间距离长度的启发信息以及以信息素形式存储已经获得的信息，又可进行有倾向性的探索，使蚂蚁寻找出更多可能的路径，保证解的多样性，提高全局搜索的能力。 因此定义如下：时刻t时每只蚂蚁在单元i选择下一个即将遍历的单元j时按照伪随机比例规则选择 其中，α和β分别决定了信息素和启发式信息的相对影响力；allowedk表示位于节点 i 的蚂蚁下一步可以选择的节点的集合；ηij(t)为启发函数，ηij(t) = 1/ dij ；q是均匀分布在区间［0，1］的一个随机变量，参数q0决定算法对新路径的探索度(0≤q0≤1)；J为根据式(3)的概率所选择的阵列单元。 信息素更新策略 信息素更新分为局部更新和全局更新。蚂蚁每从点 i 移动到 j，就会减少(i，j)上一定量的信息素，以增加蚂蚁探索其他路径的可能性，这一过程称为信息素局部更新 其中，ξ和τ0是两个参数；ξ表示信息素挥发因子，满足0 ＜ξ＜1；τ0是信息素的初始值，当为 1/( nCnn) 时，算法具有较好的性能；n为所需遍历的阵列单元中的所有节点数；Cnn表示由最近邻方法得到的路径长度。局部更新规则可有效地避免蚂蚁收敛到同一条路径。 信息素的挥发和信息素的释放只在至今最优解路径上进行。当所有的蚂蚁都构建出一条完整路径后，只更新至今最优蚂蚁所走路径的信息素，该过程叫信息素全局更新 其中，Tbs为全局最优的路径;Lbs为全局最优路径的长度。 算法流程图如图3 所示。 图3 算法流程图 3 实验与分析 以相关生化实验模型为例，进行该测试方法的图解说明和有效性验证。已知一个二维平面数字微流控生物芯片，如图 4 所示。 该模型中4个液滴 a，b，c，d 分别需要移动到相应的目标点。测试目标即为利用 k 组测试液滴从起点开始实施并行测试，使得测试液滴能够覆盖所有行进路径，最终到达终点。 图4 实验模型及运行路径 该模型的路径可转换为网络节点图，其中权值为节点与节点之间所经过的电极单元数。 获得模型的网络节点图后，利用Floyd算法求各节点之间最短路径，转换为完全连通图，表1为该图的邻接矩阵。 表1 各节点之间连通路径长度 假设Dc为起始点，Sa为终点，利用蚁群算法寻找多条并行测试路径，以实现液滴并行测试。实验各参数为 m= 40，q0 = 0. 9，α= 1，β= 2，ξ= 0. 1，ρ= 0. 1，NC =1000。当 k 取2，3，4时获得结果如表 2 所示，其中路径长度为液滴所经过的电极单元总数。 表2 各分组路径长度 当 k=3 时，即3条并行测试路径，其中，蚁群算法分配到每组的节点后，将各组节点之间的路径分配到未使用的路径上，如若存在未分配到的路径，则测试液滴再由起始点出发，遍历该路径后回到终点。 另外由于数字微流控芯片中两液滴不能处于直接邻近或对角邻近的阵列单元，否则会导致液滴融合，所以需保证液滴之间有一定的间隔距离。 因此各组测试液滴之间存在优先级，权值最大，即路径长度最长的液滴拥有最高优先级，该液滴具有优先遍历电极单元的级别，其他低等级的液滴若相遇则进入等待状态，依次类推。最终测试路径如图 5 所示，花费时间分别为 26、30、36个单位时间。单位时间是液滴移动到相邻阵列单元所花费的时间。 图5 3条并行测试路径选择 4 实验结果 实验结果表明，基于蚁群算法的并行测试方法能够灵活、有效地减少针对实验路径测试所花费的时间。 本方法还可以利用测试液滴**的特性进行测试优化，以减少重复路径的遍历。例如图5中可对交叉点 e，f，g，h进行液滴优化，使2倍体积的测试液滴在该处**为两个1倍体积的液滴并行测试以减少行走重复路径所花费的时间。 本文对该芯片以全阵列测试和实验路径测试两种测试形式进行实验结果比较。选取Dc端为出发点，Da端为终点。实验结果如表3所示，本文提出针对实验路径的测试策略运用在实际实验中，能够大量减少测试时间，加快实验的工作流程、节约液滴容量、降低实验消耗。 表 3 实验结果对比 5 结束语 本文主要进行了基于蚁群算法的数字微流控芯片的并行测试研究。目前其他的研究文献都是对数字微流控芯片全阵列进行测试，花费时间长，算法负杂度高。 本文提出的方法有针对性的对实际实验中已经经过综合后的实验路径进行测试，采用蚁群算法，利用其分布式计算的特性，寻找多液滴测试路径，完成对路径的测试，测试花费时间大幅减少，对于大规模的数字微流控芯片，测试效果更加明显。 本文转载于微信公众号: MEMS技术(wwzhifudianhua)，更多微信文章请扫描关注公众号: |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
