高级检索

    流路径驱动的微流控生物芯片任意角度布线算法

    Any-Angle Routing for Microfluidic Biochips Driven by Flow Path

    • 摘要: 连续微流控生物芯片(continuous-flow microfluidic biochips,CFMBs)由于其能够自动高效的执行生化应用,成为近年来的研究热点. PathDriver+首次将实际的流体运输需求考虑进CFMBs设计流程中,并实现了实际的流体运输和去除,并为每个运输任务规划独立的流路径,而这些问题在之前的工作中被忽略了. 但是,由于PathDriver+仅考虑了网格模型下总体布线的线长优化,而未考虑详细布线,没有充分利用CFMBs布线的灵活性. 此外,PathDriver+仅考虑X型布线方式,而任意角度布线能够更有效的利用布线资源,从而缩短流通道长度. 针对上述问题,提出了流路径驱动的任意角度布线算法,在考虑实际的流体运输需求的同时,提高布线资源的利用率,减少流通道的长度. 首先基于Delaunay三角剖分构建搜索图,从而在保证布线质量的同时,提高布线解的搜索效率. 然后,在构建的搜索图上,使用基于Dijkstra的流路径布线方法,以快速生成具有较短线长的布线结果. 在布线过程中针对流通道复用和流通道交叉点数量优化问题,分别提出了通道复用策略和交叉优化策略,以进一步提高布线结果的质量. 实验结果表明,与最新工作PathDriver+相比,算法在布线总线长、流层端口使用数量、通道交叉点数量分别降低了33.21%,11.04%,44.79%,通道复用率平均提高了26.88%,交叉点处引入阀门的总数量平均减少了42.01%,这表明算法的有效性和优越性.

       

      Abstract: Continuous-flow microfluidic biochips (CFMBs) have become a hot research topic in recent years due to their ability to perform biochemical assays automatically and efficiently. For the first time, PathDriver+ takes the requirements of the actual fluid transportation into account in the design process of CFMBs and implements the actual fluid transport and removal, and plans separate flow paths for each transport task, which have been neglected in previous work. However, PathDriver+ does not take full advantage of the flexibility of CFMBs routing because it only considers the optimization of flow channel length for the global routing in the mesh model, but not the detailed routing. In addition, PathDriver+ only considers the X architecture, while the existing work shows that the any-angle routing can utilize the routing resources more efficiently and shorten the flow channel length. To address the above issues, this paper proposes a flow path-driven arbitrary angle routing algorithm, which can improve the utilization of routing resources and reduce the flow channel length while considering the actual fluid transportation requirements. The proposed algorithm constructs a search graph based on constrained Delaunay triangulation to improve the search efficiency of routing solutions while ensuring the routing quality. Then, a Dijkstra-based flow path routing method is used on the constructed search graph to generate a routing result with a short channel length quickly. In addition, in the routing process, channel reuse strategy and intersection optimization strategy are proposed for the flow path reuse and intersection number optimization problems, respectively, to further improve the quality of routing results. The experimental results show that compared with the latest work PathDriver+, the length of channels, the number of ports used, and the number of channel intersections are significantly reduced by 33.21%, 11.04%, and 44.79%, respectively, and the channel reuse rate is improved by 26.88% on average, and the total number of valves introduced at intersections is reduced by 42.01% on average, which demonstrates the effectiveness of the algorithm in this paper.

       

    /

    返回文章
    返回