硕士论文-时间依赖的无向中国邮路问题分支切割算法

大连理工大学硕士学位论文时间依赖的无向中国邮路问题分支切割算法姓名：武雪平申请学位级别：硕士专业：计算机软件与理论指导教师：谭国真20091217时间依赖的无向中国邮路问题分支切割算法作者：武雪平学位授予单位：大连理工大学相似文献(10条)1.学位论文李旸基于粒度计算智能的计算机网络路由研究2007计算智能是借用自然界(生物界)的一些规律的启迪，根据其原理，模仿设计求解问题。它是以模型(计算模型、数学模型)为基础，以分布．并行计算为特征，模拟人的智能求解问题的理论和方法。在不同的抽象层次上观察、理解、表示现实世界问题并进行分析、综合、推理，是人类求解问题过程中的一个明显特征，也是人类求解问题能力的强有力表现。从一定意义上来说，这就是人类求解问题过程中的智能所在。针对人类求解问题的这种能力和特征，人工智能研究者对其进行了深入研究，并建立了各种模型。张钹院士和张铃教授从仿生学的观点提出的基于商粒度空间的问题求解理论，符合人类求解问题的思维模式。对于网络路由复杂系统的研究，本文认为，利用粒度空间的问题求解理论，从不同层次、不同角度，把定性的思维和定量的分析有机地统一起来，来分析和处理路由策略问题，将是一个较有应用前景的课题。路由策略是计算机网络的核心技术之一，Internet的迅速发展使得路由策略的研究成为计算机科学的一个重要研究方向。路由策略的研究成为新一代网络体系结构和协议理论中的关键性理论课题。本文总结了以往的研究在这个方向上取得的成果，进一步改进了现有的路由策略及其实现算法。具体而言，本文在粒度理论的基础上对OSPF路由策略进行了分析，在此分析的基础上，对计算机网络路由策略开展了一些新的研究工作，提出了一些新的算法与模型。本文的研究主线是基于商粒度空间的计算智能及其在计算机网络路由策略中的应用，研究的主要内容包括：1．本文介绍了粒度计算智能的理论、方法及其应用，讨论了商粒度空间理论下的推理模型以及论域的合成理论，分析了商粒度空间理论在计算机网络路由领域应用的意义。进一步，笔者开展了将商空间理论应用于OSPF路由算法的研究，提出了本文所研究的基于商空间的计算智能方法在实际网络路由研究中的应用和实现。2．本文研究比较分析了网络负载均衡资源优化的路由算法、基于链路流量分配权值的路由算法以及基于自适应遗传算法的OSPF链路权重优化算法，在此基础上，笔者建立了基于商空间粒度理论的计算机网络路由簇、区、组粒度模型，给出了基于粒度智能的动态计算机网络路由算法并在OSPF网络环境下进行了算法仿真，本文的研究结果表明粒度路由理论大大缩小了问题求解的粒度搜索空间，在实际应用中降低了计算的复杂度，对于提高传统的OSPF路由效能具有一定的指导意义。3．本文介绍了近年来在信息技术领域广泛应用的Multi-agent系统的思想方法和一些新的理论应用。笔者考虑到Multi-agent是一个非常复杂的系统，因此提出了基于商空间粒度理论的Multi-agent应用于大型复杂动态网络路由的方法，建立了Multi-agent的商空间粒度模型。利用无标度网络不断递减的层次关系所内涵的固有性质，将agent进行粒度划分为簇、区、组agent，这样不但解决了难以把握信念随时间变化的不确定性问题，同时也降低了系统的复杂度，大大地减少了计算量。笔者认为，将这种方法应用于当前的复杂动态网络路由策略研究领域，可以有效改进网络路由效能，从而为路由选择问题的求解提供新的思路和方法。本文的试验结果表明，本文所提出的理论模型和算法适合于解决动态大型网络的路由问题，对于网络路由系统的收敛响应及系统的路由效能具有一定的改善。应用是推动科学进步的最有效的手段。商空间理论以其坚实的理论基础和较为完美的数学模型，在问题求解领域中有着广泛的应用。本文所研究的基于商空间的计算智能及其在路由选择策略中的应用还是初步的，将商粒度空间理论与其它理论进行结合，将是计算智能研究领域中的一个值得深入研究的方向。笔者相信，以后随着基于商空间计算智能方法研究的深入，抽取计算机网络的某些固有特征，逐步将这些方法应用到计算机网络路由算法领域，将给计算机网络路由的研究发展带来新的贡献。2.会议论文红轮赤峰电业局网络路由及VLAN配置2003赤峰电业局1998年正式初步建立小型局域网,经过短短四年时间,整个网络扩大并不断完善.路由在这个网络中起着非常重要的作用.3.学位论文王新风网络路由和地址转换算法研究2008计算机网络性能是衡量计算机网络运行状态的各项指标的综合。计算机网络因其发展的高速度和各自为政的研究体制，以及兼容性等诸多问题，出现了一些和总体发展趋势及未来需求不太和谐的技术，造成了网络性能效率低和不稳定。本文通过对地址分配的不合理性、协议数据的冗余度及ARP广播问题的分析，提出若干优化网络性能的策略。主要内容及结果如下：(1)研究了计算机网络整体性能优化的着眼点，总结归纳了计算机网络性能可以进行优化的几个方面；(2)深入分析了计算机网络体系结构中网络层现有工作方式的不足，提出了有针对性的优化方法和策略——IP地址分配地理相关性和位置驱动路由算法，论证了这种方法的可行性，并通过仿真实验证明了该算法的路由效率远高于传统路由算法:(3)通过合理缩减帧数据的冗余度提高链路层效率，简单分析了当前数据链路层数据冗余度过高的问题，并给出了解决办法；(4)分析了降低链路层效率的主要因素是ARP技术的使用，以及由于这一技术的使用带来的其它问题；提出了利用交换机探寻算法获取转发表，从而取消ARP技术的使用，从根本上解决链路层效率和ARP欺骗等问题。最后，本文对所做的研究工作做了总结，并对今后网络性能优化方法的研究进行了展望。4.会议论文胡晨鹏.郑康锋.罗群基于网络处理器的IP网络仿真系统2008网络仿真是进行网络协议设计和测试认证时普遍采用的方法。本文介绍了网络仿真的相关概念,并基于IntelIXP2400平台讨论了网络仿真技术的具体实现(主要包括系统路由表的生产与拥塞控制策略的仿真两部分),最后总结了现在技术的不足和将来的工作方向。5.学位论文杭成宝OSPFv3协议的互操作性测试研究2009OSPF协议是内部网关协议，为了更好的支持基于IPv6下一代互联网的发展，OSPFv3协议在不断的更新。为了保证OSPFv3协议实现按照协议描述稳定可靠的运行，需要对OSPFv3协议进行协议测试。考虑到OSPFv3协议的复杂性和特点，仅仅依靠协议一致性测试是不够的，需要对其进行协议互操作性测试的研究。协议_瓦操作性测试是检验同一种或同一类协议的不同实现之间互连互通的能力。本文对OSPFv3协议的互操作性测试进行了研究。主要内容如下：br　　⑴研究了协议一致性测试与协议互操作性测试的差异，并进一步研究了目前协议互操作性测试方法的发展状况。在此基础上针对OSPFv3协议不确定性的互操作性测试提出了自己的见解。br　　⑵在OSPFv3协议互操作性测试的形式化建模方面，考虑到OSPFv3协议测试的复杂性和并发性，本文采用扩展后的Petri网，对其进行了建模。针对模型，结合OSPFv3协议RFC标准文档，分析了OSPFv3协议互操作性测试中存在的不确定性。为了进一步分析OSPFv3协议的互操作Petri网模型，采用Petri网可达图对其分析研究，并给出测试生成方法。br　　⑶根据测试需要，将生成的测试例与国家通信行业标准路由协议互操作性测试方法及美国新罕布什尔大学互操作实验室关于OSPFv3互操作性测试中的测试例进行分析比较，确定对于OSPFv3协议进行互操作性测试的测试例。对于确定的测试例，根据测试目的以及提出的测试架构，开发测试工具，搭建测试环境，进行OSPFv3协议互操作性测试的实践工作，并对测试结果进了分析，给出了测试报告。6.学位论文陈金明嵌入式SOC应用于下一代网络语音网关中的研究与设计2005目前，市场上有众多的支持多机上网的路由器，能实现基于IPv4的主机访问Internet；也有各种IP电话终端设备，能实现IP语音通信。这些路由器和IP电话设备功能单一，往往不具备支持基于IPv6的下一代网络的功能。RISC与DSP有机结合的嵌入式片上系统（SOC）是嵌入式硬件系统的最新技术，具有强大的处理功能。嵌入式SOC和基于IPv6语音网关研究是当前的研究热点。本文将当前的两个热点研究方向结合起来，设计并实现了一个嵌入式SOHO（ESH）系统，该系统将路由和IP电话功能二者结合，提供多种网络服务，并能支持下一代网络环境。同时具有很好的市场应用价值，能够带来较好的社会效益。主要研究内容包括：⑴硬件系统设计：ESH系统主要包括各种接口子系统、主控系统以及电磁屏蔽等设计内容。其中，接口子系统包括ETHERNET、SLIC、TRUNC等；主控系统除处理器子系统之外，还包括采用FPGA/CPLD实现的系统逻辑控制等任务；在EMC/EMI问题方面，通过电子工程设计方法对PCB布局问题做了详尽的研究和设计，提出了一系列的工程解决方法。⑵软件系统设计：ESH系统的软件设计主要包括BSP、系统内存管理、接口驱动、应用软件层等设计内容。首先，本文定义了下一代语音网关的功能模型，并对其进行了功能分解；其次，在分析IP包转发效率、IPv4与IPv6兼容等问题的研究基础上，提出了保证语音数据的QoS传输的设计思路和解决方法。此外，在系统的软硬件接口和功能扩展性方面性方面，也做了相关的论述。⑶系统安全问题：安全问题在嵌入式系统中得到越来越多的重视。针对ESH系统，它是连接家庭和外部网络的关键设备，本文研究了其中可能存在的安全问题，并尝试性地提出了一些解决策略。7.期刊论文闵应骅计算机网络路由研究综述-计算机学报2003,26(6)网络路由一直是网络的关键问题.今天的计算机网络非常庞大、高速,传载着各种多媒体信息,因此,网络路由面临新的挑战.路由算法层出不穷,目的都是为了寻找最优路径(或者满足要求的路径)来传递信息,提高服务质量,同时,提高网络整体资源利用率.该文试图综述计算机网络路由研究目前面对的问题及解决这些问题的进展,包括多计算机系统路由、有线网络路由及无线网络路由,并提出如何在计算机网络路由研究方面创新的一些看法.8.学位论文李延斌网络拓扑的分层算法设计与仿真2008设计一个大型通信网络需要多种概算与评估。需要预测各种服务需求和维护规划的假定。由于供应商的频繁升级，配置设备站点的数量和位置以及设备的容量通常是不确定的。因此，与其在早期的设计阶段做详细的链路规划还不如根据不同的实际情况快速评估干线的损耗，用动态的方法把小型网络整合为更大的网络。随着计算机运算性能的提高，互连网络的性能也在不断改善。而计算机网络规模的越来越大，使网络互连问题变得日趋严重。这些问题促使分层网络拓扑的研究不断前进和深入。本文要研究的课题表现为一类可以运用在计算机网络、道路交通等拓扑结构上的优化设计问题。在分层拓扑网络算法设计中，假设建立一个有n个节点的网络，要求使用最优化设计使得所有节点互连节点所使用的消耗最小。同时网络应满足：网络直径限制最大值为d、节点度数限制最大值为△，以及单链路的失效网络必须仍然是连通的等。本文所做的主要工作有以下几个方面：(1)介绍了网络拓扑与图论的相关概念以及路由算法的基本原理，研究并分析了网络拓扑分层算法的实现思路和过程，讨论了网络节点的度，网络直径和可生存性等问题;(2)根据分层网络拓扑模型和算法，引入图论的相关知识和概念，在解决典型网络问题时把隐枚举法应用在网络拓扑最优设计中，给出了可以设计出满足约束条件的网络拓扑结构所使用的隐枚举法的一般舍弃测试方法，并给出解决通用问题的计算机算法程序，针对典型网络进行了仿真；(3)针对现有网络分层算法在空闲端口及主干网度计算上的不足，给出了网络拓扑结构分层的改进算法，并通过仿真实验证明了改进算法的可行性，讨论了直径为2的连通图的性质，并将其应用在本文的拓扑网络中，从而进一步改进了算法的递归方程；(4)最后针对分层网络拓扑结构及其算法设计，研究网络的扩展算法和路由算法，给出扩展算法的一般步骤，同