论文部分内容阅读
随着物联网的高速发展,人们对其业务质量和组网技术提出了更高的服务质量(Quality of Service,QoS)要求。目前,面向物联网如何更好的保障QoS,成为物联网行业与产业继续发展壮大的关键,是当前国际家电、IT厂商等业界关注的焦点,同时也是学术界研究的热点问题。根据不同业务类型所提出的QoS要求和网络环境的资源配置,研究高效可行的QoS路由算法,是QoS路由机制有效运行的技术支撑,也是物联网保障QoS的切实可行方案之一。在智能算法、确定性算法和近似算法等QoS路由算法的热点研究中,近似算法以其高效、合理可行的特点,在物联网不同网络环境下的业务应用中表现出一定优势。本论文以“面向物联网的QoS路由算法”为主线,针对工程实践中业务应用的多约束QoS路由、多播保障QoS路由、多播多约束QoS路由和WMN(Wireless Mesh Network)网络保障QoS路由等几个关键问题展开研究。从近似的角度寻找当前性能最优的解,并探讨其在不同网络环境中应用的合理性。本文主要研究内容与贡献如下:(1)通过研究单播多约束QoS最优路由问题,根据不同网络环境分别提出了高效可行的路由算法。首先,针对稳定可靠的网络环境,结合目前最快的确定性算法,通过缩放和取整技术,从近似的角度逼近所有QoS约束,最后找到“最优”路径,相应提出了一种计算时间合理、近似率较高的路由算法;其次,针对时变、不可靠的网络环境,通过寻找每条边上最主要的度量,从近似角度找到“最优”路径并满足QoS约束,相应提出了一种快速计算且可行的路由算法。理论分析并证明了两种算法的时间复杂度和近似率,通过仿真对比现有算法验证了性能。它们分别是工程实践中稳定可靠网络和时变、容错能力差网络环境下的一种合理高效的求解方案。(2)通过研究网络中的多播生成树问题,考虑多播目的节点数量及分布状态,提出了两种高效可行的路由算法。首先,针对多播目的节点数量较多、分布集中情况,结合性能最好的多播生成树算法,基于多播路径共享的思想,让多播目的节点根据优先级顺序加入生成树,从而减少多播生成树总度量值,相应提出了一种高效可行的近似算法;其次,针对多播目的节点数量较少、分布分散情况,根据目的节点与当前生成树距离,调整多播目的节点优先级值,相应提出了一种改进的合理可行的近似算法。理论分析并证明了两种算法的时间复杂度和近似率,均与性能最好的多播生成树算法一致。通过仿真验证了两种算法在不同情况下的优势。多播路由业务中不同目的节点数量及分布状态下,它们是合理可行的求解方案。(3)通过研究多播多约束QoS最优路由问题,根据不同网络环境分别提出了高效可行的多播生成树算法。首先,针对稳定可靠的网络环境,参考性能最好的多播生成树算法,结合目前最快的确定性算法,通过缩放和取整技术,从近似的角度逼近所有QoS约束并找到“最优”多播生成树,相应提出了一种合理计算时间、近似率较高的路由算法;其次,针对时变、不可靠的网络环境,通过选取每条边上最主要的度量,从近似角度在最短时间内找到“最优”多播生成树并满足QoS约束,相应提出了一种快速计算可行的路由算法。理论分析并证明了两种算法的时间复杂度和近似率,通过仿真对比现有算法验证了性能。它们是分别针对工程实践中不同网络环境下的一种合理高效的求解方案。(4)通过研究WMN网络的Anypath路由问题,针对时变特性强、容错能力差的WMN网络,研究高效可行的Anypath路由算法。根据工程实践中的业务应用,提出了新的Anypath路由问题,建立了数学模型。根据Anypath路由的期望度量值,强制一个特定QoS约束下同时逼近其它QoS约束,从近似角度在最短时间内找到Anypath路由最优路径。提出一种时间复杂度与经典Dijkstra算法一致、且近似率合理的Anypath路由算法,该算法对现有热点研究的Anypath路由协议具有较好的兼容性。理论分析并证明了算法的时间复杂度和近似率,通过仿真对比验证了性能。它是工程实践中WMN网络环境下的一种合理高效的求解方案。