线缆布线优化算法研究与应用

作     者：魏传佳 

作者单位：武汉工业学院 

学位级别：硕士

导师姓名：周康

授予年度：2011年

学科分类：0810[工学-信息与通信工程] 08[工学] 081001[工学-通信与信息系统] 

主      题：线缆布线 线缆交叉 图论 顶点着色 极大独立集 

摘      要：线缆布线是随着计算机网络兴起而快速发展起来的一种工程技术,在布线总体框架上有了比较成熟的综合布线技术,对计算机网络规模的扩充起到了重要的作用。以往线缆布线主要考虑如何节省线缆和整洁外观,对于线槽中的线缆交叉问题考虑的比较少。尤其对于大型网络来说,如广域网,这种线缆交叉问题会对网络性能产生极大的影响以及维护起来相当困难。 在广域网中需要线缆来连接各个节点以实现节点间的信息交换,在以往对于小型的网络,需要的线缆数量比较少,布线比较容易,产生的线缆交叉问题对整体网络的性能影响不大,但对于节点众多的广域网来说,线缆交叉对网络性能会产生重大的影响,甚至会影响整个广域网的稳定性和高效性。为此本文根据广域网建设中的线缆布线问题,建立一个分层布线的模型,并利用图论的相关知识建立算法求解,最后对比工程实际建设来说明此算法的正确性和有效性。 本文针对节点众多的广域网中的线缆布线交叉问题,提出一种线缆分层算法,使得线缆按照层次进行布线施工,这样就可以避免或减少线缆交叉问题给整体网络性能所带来的影响,维护起来也非常方便。从而在广域网布线建设中,解决众多节点的线缆布线施工问题。对于解决顶点着色和极大独立集的问题,本文给出了一个基于探针的DNA算法和改进贪婪算法,这两种算法使得求解顶点着色和极大独立集简单,快捷,复杂度低,利用软件编程实现起来非常方便,并在工程实践中产生了非常好的效果,给广域网的线缆布线建设提供了很大的帮助。