基于网络演算的无线Mesh网时延上界_魏德宾.pdf

基金项目:国家自然科学基金(61931004)收稿日期:20210420修回日期:20210429第 40 卷第 2 期计算机仿真2023 年 2 月文章编号:10069348(2023)02040307基于网络演算的无线 Mesh 网时延上界魏德宾1，2，3，程健1，2，杨力1，3，颜佐任1，2(1 大连大学通信与网络重点实验室，辽宁 大连 116622;2 大连大学信息工程学院，辽宁 大连 116622;3 南京理工大学自动化学院，江苏 南京 210094)摘要:无线 Mesh 网是一种新型宽带接入通信网络，端到端时延上界分析的准确性会直接影响网络的 QoS 保障。针对无线Mesh 网传统时延边界分析方法没有考虑当前节点处理时延对后一个节点到达曲线的影响，造成时延上界计算不紧致的问题，利用(，)模型作为数据流到达曲线，延迟速率函数 L 作为数据流服务曲线，同时考虑前一个节点的处理时延对后一个节点到达曲线的影响，推导出无线 Mesh 网中单节点、单路径和多路径传输时延上界，并利用数值分析方法得到网络服务速率、流量分配方式、多路径数目等因素对时延上界的影响。仿真结果表明，与传统方法相比，以上计算得到的无线 Mesh网时延上界更接近实际仿真值。关键词:网络演算;多路径;时延上界中图分类号:TP391.9文献标识码:BThe Upper Bound of the Time Delay of Wireless Mesh NetworkBased on Network CalculusWEI Debin1，2，3，CHENG Jian1，2，YANG Li1，3，YAN Zuoren1，2(1 Communication and Network Laboratory，Dalian University，Dalian Liaoning 116622，China;2 Information and Engineering College，Dalian University，Dalian Liaoning 116622，China;3 School of Automation，Nanjing University of Science and Technology，Nanjing Jinagsu 210094，China)ABSTACT:The wireless mesh network is a new type of broadband access communication network The accuracy ofthe endtoend delay upper bound analysis will directly affect the network s QoS guarantee The traditional delayboundary analysis method of wireless Mesh network does not consider the influence of the processing delay of the cur-rent node on the arrival curve of the next node，which causes the problem of incompact calculation of the delay upperbound To solve this problem，using the(，)model as the data flow arrival curve and the delayrate function L asthe data flow service curve，while considering the impact of the processing delay of the previous node on the arrivalcurve of the next node，the single node，single path and multiple nodes in the wireless Mesh network are derived Theupper bound of the path transmission delay is used to obtain the influence of factors such as network service rate，traf-fic distribution method，and the number of multipath on the upper bound of the delay using numerical analysis meth-ods The simulation experiment shows that，compared with the traditional method，the upper bound of the wirelessMesh network delay calculated in this paper is closer to the actual simulation valueKEYWODS:Network calculus;Multipath;Upper bound of delay1引言无线 Mesh 网(Wireless Mesh Networks，WMNs)作为一种宽带接入技术，与传统无线网络相比，它具有节点移动灵活、接入方式多样等优势，近些年备受研究人员关注1。该网络主要由三层构成，分别是 Internet 接入层、核心网层和输出接入层。核心网层介于 Internet 接入层与输出接入层之间，是影响 WMNs 性能的关键，针对核心网性能的分析将为 WMNs架构设计、网络优化等带来参考。304端到端时延是分析研究核心网网络性能的重要指标，也是衡量网络服务质量(QoS)和用户体验的重要参数，时延上界的求解对 WMNs 的发展和应用具有现实意义。它主要受到链路上各节点的服务延迟、链路节点个数、调度策略、网络拓扑、流量分配方式等综合因素的影响。端到端时延上界分析的准确性直接影响到网络 QoS 保障水平，同时也是网络接纳控制、路由优化的重要依据。网络演算(Network Calculus，NC)是一种有效计算端到端时延上界的数学工具，很多学者对此进行深入研究。文献 2 基于 NC 理论对单、多两种节点形成两种不同的到达和服务曲线模型对时延上界进行紧致计算评估。李庆华等人3 针对无线自组网，基于已存在的链路吞吐量模型，运用网络演算计算了节点的端到端时延上界、时延抖动上界等结果。陈志刚等人4 利用网络演算理论，通过模拟实验和数值分析，对无线多跳网进行推导，从而确保了无线多跳网络的QoS，从而证实了理论结果的正确性。文献 5从降低端到端时延上界的计算复杂度角度出发，提出 LAC(Loacl ArrivalCurve)组合分析方法，但是此方法计算的时延上界紧密度却低于 NC 理论。在新型应用上，文献 6 利用随机网络演算，推导了物联网业务流的到达曲线和服务曲线，求解了机器业务流的端到端时延上界。文献 7 运用 NC 对软件定义车联网(SDIoV)中传输数据建立模型并引入遗传算法，最终设计出符合 SDIoV 的路由算法进行路径传输。文献 8针对5G 蜂窝移动通信技术中的云无线接入网，对不同优先级的业务流计算了其端到端时延及数据积压上界。文献 9 研究了卫星 5G 一体化网络中各组件之间连接关系的串联模型，并基于该模型给出了端到端延迟计算函数。无线 Mesh 网的早期考虑到网络易于管理和配置，主要使用单径传输。但由于通信需求的增加，单径传输易导致流量集中在某条路径形成“热线”，端到端时延会变得很大。多径传输10 可规避形成单路径“热线”情况，降低网络端到端时延，提高网络效率。为了体现 WMNs 多径路由的优势，文献 11提出优化的 Fortified Ant 协议，其创新之处在于将排序算法纳入传统蚁群算法中，同时兼并多径传输协议，且端到端时延性能提升在仿真中确实得到验证。与以上研究有异曲同工之妙的是，李伟等人12 为了提高 WMNs 全局收敛速度，在传统蚁群算法中融合细菌觅食算法，仿真实现了 WMNs 高可靠低时延和规避局部最优的效果。文献 13 基于传统的队列模型方法，考虑了无线 mesh网络的无线特性，分析了网关节点的时延，但是未考虑其链路不确定性和网络演算的理论分析使模拟实验无法反映网络的实际 QoS 性能。文献 14基于网络演算理论分析了数据包在无线 Mesh 网络单路径传输系统中的端到端时延上界以及多路径传输系统中的不同路径间时延抖动上界，然而并未考虑并计算多路径传输系统的端到端时延上界性能。刘宴兵等人15 提出了一种针对云服务网络的参数建模分析方法，从路径时延组成上明确给出了端到端时延上界和数据积压上界的定量数学解析式，但是并未讨论单节点时延，而且也未与实际仿真值作对比分析。以上文献都未考虑当前节点的处理时延对下一个节点的到达曲线产生影响从而导致时延上界计算不紧致的问题。本文主要研究的是无线 Mesh网端到端时延近似上界，是对文献1315等研究的一个拓展。本文内容结构组织如下:第 2 节简介网络演算的基本定义、定理;第 3 节是无线 Mesh 网端到端时延上界分析计算过程，从单节点到单路径传输系统，再到多路径传输系统层层递进分析，计算和验证端到端时延上界;第 4 节是对第 3 节结论的数值分析;第 5 节是结束语。2网络演算基础2.1网络演算的基本定义与定理由 Cruz 开创并由 Chang 和 Boudec 等人完善的网络演算理论是一种新型数学工具，是基于最小加代数理论的一组结论，主要作用是分析网络队列系统性能，它最初是为了保障网络服务质量，解决资源预留等问题，目前主要应用于网络的 QoS 分析和保障。网络演算的基本定义以及积压界限和时延界限等介绍如下16:定义 1(广义增函数):设 f 是一个函数，如果对于任意的0 xy，都有 f(x)f(y)，则称 f 为广义增函数。定义 2(最小加卷积):设 f 和 g 为广义增函数，f 和 g 的最小加卷积运算为(f g)(t)=infs 0，t f(t s)+g(s)，t 00，t 0其中 inf 表示函数的下确界。用 A(t)和 A*(t)分别表示(0，t 时间内数据流相对某一系统的到达过程和离开过程。定义 3(到达曲线):给定一个广义增函数(t)，若对于所有的 0st，若数据流到达过程 A(t)，满足 A(t)A(s)(ts)，则称 是 A(t)的到达曲线。定义 4(服务曲线):设数据流具有到达过程 A(t)和离开过程 A*(t)，(t)为广义增函数，若对于所有的 0t0t，存在 A*(t)A(t0)(tt0)，则称系统为数据流提供服务曲线(t)。端到端的数据流往往经过了多个网络节点，这些网络节点作为整体提供的服务曲线可由各个网络节点的服务曲线计算得到。定理 1(节点串联):假设一个数据流依次穿过服务曲线分别为 1(t)，2(t)，n(t)的 n 个网络节点，则这 n 个网络节点串联后提供的总服务曲线为=12n。定理 2(积压界限):假设一个数据流受限于到达曲线，通过一个提供服务曲线 的系统来传输，则系统的积压上界为到达曲线与服务曲线之间的最大垂直距离，即404B(t)=v(，)=sup0inf(u)(u)定理 3(时延界限):假定一个数据流受限于到达曲线，通过一个提供服务曲线 的系统来传输，则系统的时延上界为到达曲线与服务曲线之间的最大水平距离，即d(t)h(，)=sups0inf T:T 0 and(s)(s+T)2.2数据流到达曲线基于定义 3，设 是数据流的平均到达速率，是数据流的最大突发量，以(t)=t+为到达曲线的数据流量称为(，)模型。此模型形象描绘了信息流传输过程中的平均行为，模型的到达曲线数学表达式为(t)=t+，t 00other