本发明涉及一种群体决策方法，具体涉及基于网络演算的无线多跳mesh网络端到端时延上界获取方法。
背景技术：
：：无线多跳mesh网作为一种宽带接入技术，与传统无线网络相比，它具有节点移动灵活、接入方式多样等优势，近些年备受研究人员关注。该网络主要由三层构成，分别是internet接入层、核心网层和输出接入层。核心网层介于internet接入层与输出接入层之间，是影响无线多跳mesh网络性能的关键，核心网性能的分析将为无线mesh网络架构设计、网络优化等带来参考。端到端时延是网络性能的重要指标，也是衡量网络服务质量qos和用户体验的重要参数。端到端时延上界分析的准确性直接影响到网络qos保障水平，同时也是网络接纳控制、路由优化的重要依据。传统研究方法主要利用网络演算理论分析了无线多跳mesh网络单路径传输中的时延上界以及多路径传输中的路径间时延抖动上界，然而对多路径传输系统端到端时延上界并未考虑，另外网络参数建模方法主要研究的是无线多跳mesh网端到端时延近似上界。技术实现要素：鉴于传统时延上界研究方法未能精确得出无线多跳mesh网络的端到端时延上界问题，故本申请提出一种基于网络演算的端到端时延上界获取方法，以保障网络qos服务。为实现上述目的，本申请的技术方案为：基于网络演算的无线多跳mesh网络端到端时延上界获取方法，包括：获取单节点时延上界；根据所述单节点时延上界利用网络演算理论得出无线多跳mesh网络单路径传输系统端到端时延上界；通过所述单路径传输系统端到端时延上界获取多路径传输系统端到端时延上界。进一步的，获取单节点时延上界之前，假设一个业务流a(t)通过节点p受到达曲线约束，所述到达曲线为：其中，ρ是数据流的平均到达速率，σ是数据流的最大突发量；通过时延—速率函数lr(latency-rate)表示的服务曲线β(t)提供服务，所述服务曲线为：其中r为服务速率，t是数据流在系统中的服务时延，即包处理时延，表示为t＝l/r+l/c。进一步的，单节点时延由系统缓存的排队时延和处理时延构成，其中处理时延为时延参数t，而排队时延dqueue上界看作是最大繁忙间隔，其单节点排队时延上界为：故单节点i时延上界表示为：进一步的，根据所述单节点时延上界利用网络演算理论得出无线多跳mesh网络单路径传输系统端到端时延上界包括两部分：一部分是可变时延，为系统缓冲区排队时延；另一部分是固定时延，包括节点系统处理时延、转发时延和链路传播时延，而对于固定时延，假设n个节点中相邻两个节点之间的固定时延依次为d1,d2,…,dn-1；对于一条包含n个节点的路径，第i个节点数据流的到达曲线为αi(t)＝σi+ρit，传输服务系统能力为βi＝ri[t-ti]+，则节点1到n的单路径端到端时延为1)当n＝1时，由单节点时延上界和式(4)获得端到端时延上界；当n＝2时，由水平偏差定理得出第1个节点的时延上界节点1的输出限制于到达曲线，节点1将数据流传输到链路上，再经过传播到达第2个节点，所以第2个节点到达曲线α(t)＝α*(t)；同理按照单节点时延上界计算公式得到节点2时延上界结合相邻两个节点之间的固定时延，故第1，2个节点之间的端到端时延为：2)假设当n＝k-1时，端到端时延上界为：3)当n＝k时，第k个节点的到达曲线由单节点时延上界得出，第k个节点的时延上界为：含有k个节点的单路径端到端时延上界等于前k-1个节点的时延上界第k-1个节点和第k个节点之间的固定时延dk-1和第k个节点的时延上界三者之和，即进一步的，通过所述单路径传输系统端到端时延上界获取多路径传输系统端到端时延上界，具体为：假设源端节点g与聚合节点a之间存在m条路径，进入网络系统的数据流r(t)，首先会通过源端节点g，然后分为m条路径进行传输，表示为ri(t),i＝1,2,…,m，且有设第i条路径上第j个节点的服务曲线用β(i,j)表示，其中j＝1,2,…,ni，ni表示第i条路径上的节点个数，聚合节点a的服务能力表示为βa；对于聚合节点a，假设该节点的缓存队列区足够大，不会造成数据溢出；节点g到a有m条路径，第i条路径上有ni个节点，各节点的服务能力分别表示为βa＝ra[t-ta]+，β(i,j)＝r(i,j)[t-t(i,j)]+，βg＝rg[t-tg]+，i＝1,2,…,m；j＝1,2,…,ni，因为从g到a数据流未聚合前的多路径传输中时延最大值是传输时延最大的那条路径的传输时延，表示为：由单路径端到端时延可知，第i条路径的输出数据流受曲线约束，假设聚合节点a需要所有的数据流到达后才会对其处理，流量进入聚合节点a需受曲线：的约束，那么经过m条路径传输后，聚合节点的时延上界满足以下关系式其中，ta＝l/ra为聚合节点a的服务时延，ρa＝ρ1+ρ2+…+ρm。综上，得到多路径传输系统端到端时延上界为本发明与已有的方法，在以下方面存在优势：本申请通过求解系统节点的排队时延和处理时延得到单节点时延上界；以及设置节点的到达曲线与服务曲线并结合无线多跳mesh网络研究方法，计算无线多跳mesh网络单传输系统时延上界；再基于单传输系统时延上界获取多传输系统时延上界。通过仿真实验从系统仿真、单传输系统、多传输系统三方面比较，本发明得到的无线多跳mesh网端到端延迟上界接近实际网络端到端时延仿真值，能够保障网络qos服务。附图说明图1到达曲线图；图2单路径传输图；图3多路径传输图；图4单传输系统场景仿真图；图5r＝150mb/s时的端到端时延图；图6两者端到端时延上界分析图；图7单路径端到端时延和链路节点个数的关系图；图8端到端时延和网络服务速率的关系图；图9端到端时延和三种服务权值分配的关系图；图10多路径端到端时延上界和网络服务速率的关系图；图11多路径端到端时延上界和多路径条数的关系图。具体实施方式下面结合附图和具体实施例对本发明作进一步详细的描述：以此为例对本申请做进一步的描述说明。本实施例提供一种基于网络演算的无线多跳mesh网络端到端时延上界获取方法，包括：一、获取单节点时延上界；具体的，单节点的时延由系统缓存的排队时延和处理时延构成，当一个业务流a(t)到达节点时，会受到该节点参数为(ρ,σ)的令牌桶限制，也即受该节点的到达曲线α(t)约束，其中ρ是数据流的平均到达速率，σ是数据流的最大突发量。并通过延迟—速率函数lr(latency-rate)表示的服务曲线β(t)提供服务：其中r为服务速率，t是数据流在系统中的服务延迟，即包处理时延，表示为t＝l/r+l/c。单节点时延由系统缓存的排队时延和处理时延构成，其中处理时延为延迟参数t，而排队时延dqueue上界看作是最大繁忙间隔，其单节点排队延迟上界为所以得到单节点i时延上界为：二、根据所述单节点时延上界利用网络演算理论得出无线多跳mesh网络单路径传输系统端到端时延上界；具体的，无线多跳mesh网络端到端单路径传输如图2所示，包括两部分：一部分是可变时延，主要是系统缓冲区排队时延；另一部分是固定时延，主要包括节点系统处理时延、转发时延和链路传播时延。而对于固定时延，本申请假设n个节点中相邻两个节点之间的固定时延依次为d1,d2,…,dn-1。对于一条包含n个节点的路径，第i个节点数据流的到达曲线为αi(t)＝σi+ρit，传输服务系统能力为βi＝ri[t-ti]+，则节点1到n的单路径端到端延迟为1)当n＝1时，由单节点时延上界和式(4)获得端到端时延上界；当n＝2时，由水平偏差定理得出第1个节点的延迟上界节点1的输出限制于曲线，节点1将数据流传输到链路上，再经过传播到达第2个节点，所以第2个节点到达曲线α(t)＝α*(t)。同理按照单节点时延上界计算公式得到节点2时延上界结合相邻两个节点之间的固定时延，所以第1，2个节点之间的端到端延迟为：2)假设当n＝k-1时，端到端时延上界为：3)当n＝k时，第k个节点的到达曲线由单节点时延上界得出，第k个节点的时延上界为含有k个节点的单路径端到端时延上界等于前k-1个节点的时延上界第k-1个节点和第k个节点之间的固定时延dk-1和第k个节点的时延上界三者之和，即三、通过所述单路径传输系统端到端时延上界获取多路径传输系统端到端时延上界；具体的，多路径传输的情形如图3所示，根据网络演算和单路径传输系统端到端时延上界，假设多路径传输源端节点g与聚合节点a之间存在m条路径，进入网络系统的数据流r(t)，首先会通过源端节点g，然后分为m条路径进行传输，表示为ri(t),i＝1,2,…,m，且有设第i条路径上第j个节点的服务曲线用β(i,j)表示，其中j＝1,2,…,ni，ni表示第i条路径上的节点个数，聚合节点a的服务能力表示为βa。对于聚合节点a，本申请假设该节点的缓存队列区足够大，不会造成数据溢出。上述节点g到a有m条路径，第i条路径上有ni个节点，各节点的服务能力分别表示为βa＝ra[t-ta]+，β(i,j)＝r(i,j)[t-t(i,j)]+，βg＝rg[t-tg]+，i＝1,2,…,m；j＝1,2,…,ni，因为从g到a数据流未聚合前的多路径传输中延迟最大值是传输延迟最大的那条路径的传输延迟，表示为由上述单路径端到端延迟可知，第i条路径的输出数据流受曲线约束，假设聚合节点a需要所有的数据流到达后才会对其处理，流量进入聚合节点a需受曲线的约束，那么经过m条路径传输后，聚合节点的时延上界满足以下关系式其中，ta＝l/ra为聚合节点a的服务延迟，ρa＝ρ1+ρ2+…+ρm。综上，得到多路径传输系统端到端时延上界为：为验证本申请提出的基于网络演算的无线多跳mesh网络端到端时延上界获取方法的有效性和正确性，模拟一个单传输系统以进行端到端时延统计，用opnet仿真工具设置一个单路径传输系统，如图4。实验场景：1000m*1000m，源节点router1的客户端发送速率为120mb/s，各路由器router的服务速率初始值设为150mb/s，节点缓存大小设置为500mtu，router1到router7依次相距250m。其它网络参数采用表1中的设置参数。表1网络实验参数设置table1networkexperimentparametersettings注：最大包长根据计算机网络以太网中规定的mtu(最大传输单元)设置本申请分别从单路径传输系统和多路径传输系统两个角度进行端到端时延上界数值仿真验证。针对单路径传输系统，从两方面分析，一是将基于网络演算理论计算得到的端到端时延上界与仿真端到端时延上界分析比较来验证结果，二是通过以下三种不同特征的数据流来刻画本申请计算的端到端延迟上界在不同条件下的影响。假设x的长期平均速率和突发量分别为120mb/s，200kbits；y的长期平均速率和突发量分别为200mb/s，200kbits；z的长期平均速率和突发量分别为120mb/s，300kbits。1.单路径传输系统端到端时延上界为了保持本发明仿真分析的一致性，统一采用流x中的服务参数，根据图5仿真得到的网络端到端时延上界值，与本申请计算得到的端到端时延上界进行比较，如图6所示，可看出本申请计算的端到端时延上界随着网络服务速率增大，愈加接近仿真时延上界模拟值。另外，图7、图8、图9分别是从链路节点个数、网络服务速率、服务权值分配三个方面对x，y，z三种不同特征的数据流在端到端时延上界的影响。(1).链路节点个数与端到端时延的关系图7显示单路径情况下链路节点个数对端到端时延的影响，可以看出，时延都是随着链路的节点数增大而增大，此结果反映了网络演算和实际时延的特点，即当链路上的节点数越多时，网络演算的卷积值更能反映真实的网络性能。(2).网络服务速率与端到端时延的关系图8显示了端到端时延和网络服务速率之间的关系，不难看出，两者呈负相关，即端到端时延随着网络服务速率增大而减少，这与实际网络情况一致。另外可以看出服务速率小于350mb/s时，端到端时延随着网络服务速率增大下降的幅度较大，大于350mb/s时，下降的幅度趋于平稳。数据流x和z的端到端时延和网络服务速率之间的曲线几乎重叠，这是因为这两种服务拥有相同的，而节点之间的输入输出关系正是随着网络演算的卷积值而变化，主要受突发量的影响，但影响并不大，但是z的时延要略大一点。而x和y的端到端时延和网络服务速率之间的曲线有明显的差别正验证了这点。(3).服务速率权重与端到端时延的关系图9显示了端到端时延在固定链路节点个数的情况下与服务速率权值分配之间的关系。假设总服务速率800mb/s，数据流x、y、z的服务速率分配权值分别为0.2，0.5，0.3。三者端到端时延整体都呈上升趋势，其中x端到端时延最高，y次之，z时延最低，这与分析的结果是一致的。因为在相同到达速率情况下，z分配到的服务速率大于x分配的速率，虽然突发量也会对时延造成影响，但是影响却不大，自然计算出的端到端时延是较小的；而y与x相比时，到达速率大虽有影响，但对于y分配到的最高的服务速率，同样影响就不那么明显了。2.多路径传输系统端到端时延上界多路径情况下主要从路径条数、网络服务速率两个方面分析对端到端时延上界的影响。传输过程中设置源节点g输出的数据经三条路径到达聚合节点a，各链路提供的服务速率分别为90mb/s，100mb/s，110mb/s。同时为了对比分析的方便有效，在多路径下本申请只讨论分析数据流x在不同情况下的端到端时延上界的相应变化情况。(1).流量分配方式与端到端时延的关系图10揭示了多路径情况下网络服务速率和流量分配方式对端到端时延上界的影响，这两种流量分配方式的时延上界都随着服务速率的增加而逐渐减小，另外还可以看出通过权值分配方式的时延更低，说明根据不同链路的服务需求分配合适的流量效果更好，减小了局部链路因负荷大造成网络拥塞从而影响总体端到端时延上界。(2).流量分配方式与端到端时延的关系图11给出了在链路总服务速率设置为300mb/s，源节点和聚合节点服务速率都为500mb/s时，多路径条数和流量分配方式对端到端时延上界的影响，模拟分析数据流x在不同情况下的端到端时延上界的变化情况。可以看出，两种流量分配方式的端到端时延上界都随着多路径条数增加而增加，权值分配获取到的端到端时延上界比平均分配时延上界低，这同样归功于权值分配方式规避了局部链路因负荷大造成网络拥塞从而影响总体端到端时延上界的影响。利用不同指标进行仿真分析表明，本发明提出的基于网络演算的无线多跳mesh网络端到端延迟上界接近实际网络端到端时延仿真值，能够保障网络qos服务。以上所述，仅为本发明创造较佳的具体实施方式，但本发明创造的保护范围并不局限于此，任何熟悉本
技术领域：
：的技术人员在本发明创造披露的技术范围内，根据本发明创造的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明创造的保护范围之内。当前第1页1 2 3 当前第1页1 2 3
技术特征：1.基于网络演算的无线多跳mesh网络端到端时延上界获取方法，其特征在于，包括：
获取单节点时延上界；
根据所述单节点时延上界利用网络演算理论得出无线多跳mesh网络单路径传输系统端到端时延上界；
通过所述单路径传输系统端到端时延上界获取多路径传输系统端到端时延上界。
2.根据权利要求1所述基于网络演算的无线多跳mesh网络端到端时延上界获取方法，其特征在于，获取单节点时延上界之前，假设一个业务流a(t)通过节点p受到达曲线约束，所述到达曲线为：
其中，ρ是数据流的平均到达速率，σ是数据流的最大突发量；
通过时延—速率函数lr表示的服务曲线β(t)提供服务，所述服务曲线为：
其中r为服务速率，t是数据流在系统中的服务时延，即包处理时延，表示为t＝l/r+l/c。
3.根据权利要求2所述基于网络演算的无线多跳mesh网络端到端时延上界获取方法，其特征在于，单节点时延由系统节点的排队时延和处理时延构成，其中处理时延为时延参数t，而排队时延dqueue上界看作是最大繁忙间隔，其单节点排队时延上界为：
故单节点i时延上界表示为：
4.根据权利要求1所述基于网络演算的无线多跳mesh网络端到端时延上界获取方法，其特征在于，根据所述单节点时延上界利用网络演算理论得出无线多跳mesh网络单路径传输系统端到端时延上界包括两部分：一部分是可变时延，为系统缓冲区排队时延；另一部分是固定时延，包括节点系统处理时延、转发时延和链路传播时延，而对于固定时延，假设n个节点中相邻两个节点之间的固定时延依次为d1,d2,…,dn-1；
对于一条包含n个节点的路径，第i个节点数据流的到达曲线为αi(t)＝σi+ρit，传输服务系统能力为βi＝ri[t-ti]+，则节点1到n的单路径端到端时延为
1)当n＝1时，由单节点时延上界和式(4)获得端到端时延上界；当n＝2时，由水平偏差定理得出第1个节点的时延上界节点1的输出限制于到达曲线，节点1将数据流传输到链路上，再经过传播到达第2个节点，所以第2个节点到达曲线α(t)＝α*(t)；同理按照单节点时延上界计算公式得到节点2时延上界结合相邻两个节点之间的固定时延，故第1，2个节点之间的端到端时延为：
2)假设当n＝k-1时，端到端时延上界为：
3)当n＝k时，第k个节点的到达曲线由单节点时延上界得出，第k个节点的时延上界为：
含有k个节点的单路径端到端时延上界等于前k-1个节点的时延上界第k-1个节点和第k个节点之间的固定时延dk-1和第k个节点的时延上界三者之和，即
5.根据权利要求1所述基于网络演算的无线多跳mesh网络端到端时延上界获取方法，其特征在于，通过所述单路径传输系统端到端时延上界获取多路径传输系统端到端时延上界，具体为：假设源端节点g与聚合节点a之间存在m条路径，进入网络系统的数据流r(t)，首先会通过源端节点g，然后分为m条路径进行传输，表示为ri(t),i＝1,2,…,m，且有设第i条路径上第j个节点的服务曲线用β(i,j)表示，其中j＝1,2,…,ni，ni表示第i条路径上的节点个数，聚合节点a的服务能力表示为βa；对于聚合节点a，假设该节点的缓存队列区足够大，不会造成数据溢出；
节点g到a有m条路径，第i条路径上有ni个节点，各节点的服务能力分别表示为βa＝ra[t-ta]+，β(i,j)＝r(i,j)[t-t(i,j)]+，βg＝rg[t-tg]+，i＝1,2,…,m；j＝1,2,…,ni，因为从g到a数据流未聚合前的多路径传输中时延最大值是传输时延最大的那条路径的传输时延，表示为：
由单路径端到端时延可知，第i条路径的输出数据流受曲线约束，假设聚合节点a需要所有的数据流到达后才会对其处理，流量进入聚合节点a需受曲线：
的约束，那么经过m条路径传输后，聚合节点的时延上界满足以下关系式
其中，ta＝l/ra为聚合节点a的服务时延，ρa＝ρ1+ρ2+…+ρm。
综上，得到多路径传输系统端到端时延上界为
技术总结本发明公开了基于网络演算的无线多跳Mesh网络端到端时延上界获取方法，通过求解系统节点的排队时延和处理时延得到单节点时延上界；以及设置节点的到达曲线与服务曲线并结合无线多跳mesh网络研究方法，计算无线多跳mesh网络单传输系统时延上界；再基于单传输系统时延上界获取多传输系统时延上界。通过仿真实验从系统仿真、单传输系统、多传输系统三方面比较，本发明得到的无线多跳mesh网端到端延迟上界接近实际网络端到端时延仿真值，能够保障网络QoS服务。
技术研发人员：魏德宾;杨力;程健;颜佐任
受保护的技术使用者：大连大学
技术研发日：2020.12.11
技术公布日：2021.04.06
