【摘 要】
：
在通信网络中,路径的构造及修复优化一直是网络中的关键问题.在无线通信网络运行过程中会存在各种各样的故障问题或者需要考虑成本和能量消耗的权衡问题,本文就无线网络中的局部故障修复问题以及动态限制最短路问题展开研究.为了更有效地恢复通信网络的故障路径,本文提出了修复限制路问题.给定一个具有一些故障边的有向无圈图G=（V（G）,E（G））,其中|V（G）|=n,|E（G）|=m.对给定的正整数D,为了寻找
论文部分内容阅读
在通信网络中,路径的构造及修复优化一直是网络中的关键问题.在无线通信网络运行过程中会存在各种各样的故障问题或者需要考虑成本和能量消耗的权衡问题,本文就无线网络中的局部故障修复问题以及动态限制最短路问题展开研究.为了更有效地恢复通信网络的故障路径,本文提出了修复限制路问题.给定一个具有一些故障边的有向无圈图G=（V（G）,E（G））,其中|V（G）|=n,|E（G）|=m.对给定的正整数D,为了寻找和修复从源点s ∈ V（G）到终点d∈V（G）且长度不超过D的路,我们给出限制修复路算法.本文分别用参数||δ||和|δ|作为故障边影响到的边数和点数.其主要的技术是定义了一对多限制路问题（OSCPP）,该问题在之前没有被提出过.在有向无圈图中从每个点u∈V（G）到终点d的所有最短路都已知的情况下,与时间复杂度为O（||δ||+|δ| log |δ|）的动态最短路算法和时间复杂度为O（m+n）的最短路算法相比,我们提出的限制修复路算法将复杂度降低到O（||δ||+|δ|）.在时变通信网络中,为了在成本约束下提高工作效率,本文研究了在总成本有上限的情况下使总时间最小的问题,其中成本是随时间变化的.在动态网络条件下不仅使该研究更具实用性,而且能够利用延迟时间来节约成本.首先本文通过给定的参数重置传输时间,然后根据新的传输时间构造辅助图,并在原始图中定义相应的传输过程.通过在辅助图中构造所需路径,最终得到了全多项式时间为（?）的（1+ε）近似算法来解决该问题.
其他文献
胃癌是全球最常见的恶行肿瘤之一,由于癌症的异质性,胃癌的表型复杂多样,使得癌症的诊断和治疗十分困难,而且由于多数胃癌患者确诊时已处于癌症晚期,预后较差。因此,针对胃癌异质性的研究和个性化预后模型的构建对于胃癌患者治疗方案的制定和延长胃癌患者的预后具有重要意义。微卫星不稳定性（Microsatellite Instability,MSI）是由DNA错配修复受损导致的一种特殊癌症表型,研究表明,MSI
作为物联网的重要组成部分,应用于多个领域的无线传感网所产生的数据量与日俱增,对这类感知数据压缩的研究一直是物联网应用中最关键的技术之一。由于受到感知节点存储空间、电源能耗、计算能力等限制,如何在低能耗条件下满足应用需求来实现数据压缩成为亟待解决的难题之一。结合感知节点和基站特点,本文针对压缩感知理论处理时空相关性较强的一类感知数据的过程进行改进,实验结果表明本文的改进能够获得较好的压缩效果。论文的
近年来人脸检测被广泛应用在校园门禁、刷脸支付、视频监控和目标追踪等各个方面。同时,人们在实时性、安全性和可靠性上,对基于人脸的特征点定位、检测和识别等相关应用提出了更高的要求。此外,在人脸密集、尺度不一、与背景高度相似以及高度遮挡等复杂场景中,人脸检测经常达不到预期效果,人脸检测技术上的挑战依然存在,复杂场景中的鲁棒人脸检测仍然是国内外的热点研究。为了提高人脸检测在复杂场景中的应用性,针对检测中遇
近年来,由于互联网飞快地发展以及网络信息技术逐渐在各个领域的普及,开发人员研发的电脑应用软件也渐渐的成熟,广泛应用于各行各业中,致力于提高人们的工作效率和生活便利性。因此将Internet、大数据、云计算技术引入到煤矿行业信息化建设中,有助于提高其信息化水平,促进矿区的非常规水资源高效利用,缓解水资源压力,为其科学决策提供理论基础,建设绿色智慧矿山。本文选择以安家岭、安太堡露井联采矿区为研究对象,
随着计算机技术的发展,计算机视觉技术现已成为当前研究的热门问题,已在很多领域得到了应用。虽然目标跟踪技术经过多年的发展,已经取得了长足的进步。但由于跟踪对象运动的不可预知性和所处环境的复杂性,目标跟踪仍然存在许多亟待解决的难点。比如,目标在运动过程中,由于目标跟踪存在遮挡、形变、快速运动等问题。这些因素都会造成目标模型漂移甚至造成目标跟踪的失败。针对复杂环境下运动目标被遮挡时目标丢失问题,本论文对
伴随工业化进程的快速发展,工业化领域的基础设施也在不断完善。在工业生产中,常常存在一些不可见气体,这些气体可能会影响设备的正常运行,一些不可见的有毒气体,甚至会危害作业工人的人身安全。因此,需要对气体（尤其是不可见气体）进行监测。目前,工业过程中在对不可见气体进行监测时,多采用点式探测方法,该方法可以对气体进行有效分类,同时,该方法具有速度快、精度高、成本低和易于操作等优点。但是,该方法存在的缺点
矿井瓦斯事灾害故危害性大、事故后果严重、影响恶劣,给煤矿企业的安全生产造成了严重困扰。通过对矿井瓦斯浓度数据进行有效地挖掘分析、实施准确的瓦斯浓度预测,并以预测所得到的瓦斯浓度数据为基础进行瓦斯浓度预警研究,这对减少矿井瓦斯灾害事故、保障从业人员的生命安全具有重大意义。本文以提高大数据背景下煤矿企业的瓦斯浓度异常预警能力、减少瓦斯事故发生为研究目的,以大数据建模预测分析方法为手段,研究了瓦斯浓度预
刮板输送机在运输过程中,刮板链循环带动物料沿着溜槽移动,使得中部槽极易磨损失效,进而引起刮板输送机的运行故障,造成巨大的经济损失。因此,提高中部槽的耐磨性十分重要。但变因素下（多种煤质因素和多种输运条件因素）中部槽的磨损区域和磨损程度大不相同,只考虑单一矿井条件下中部槽的磨损无法适应不同矿井的需求。因而本文以离散元法为基础,通过仿真模拟刮板输送机的运行过程,研究了变因素下中部槽的磨损特性,设计和制
便携式瓦斯检测仪是一种可连续检测瓦斯浓度的安全型设备。随着社会的进步和科技的发展,煤矿企业对于便携式瓦斯检测仪的自动收发技术及其管理水平逐步提高,但是目前尚停留在需要人工参与的阶段,必须有专门的工作人员在现场完成发放与回收操作。此外,现有的瓦斯检测仪收发系统还存在以下缺点:标识瓦斯检测仪的条形码易磨损、标识员工的条码卡容易丢失、仪表收发记录无法实现远程异地查看,系统的自动化和信息化程度不高。为此,
信息安全关系到国家安全、经济发展、个人隐私和社会生活等诸多方面,而物理不可克隆函数（Physical Unclonable Function,PUF）是一种基于硬件的信息安全技术,被广泛应用于身份识别、密钥生成、设备认证和随机数产生等领域。PUF通过提取硬件系统的物理特征差异（包括制造工艺、制备材料的差异等）,动态地生成随机、唯一且不可预测的“数字指纹”。PUF的安全性在于物理系统内在的复杂性和不