动态保证服务质量的无线移动自组织网络的路由装置及方法

具体实施方式：

以下详细分析本发明方法中涉及的主要功能模块、应用流服务质量的描述、QoS协商机制的控制方式和协商算法、以及应用流的传输控制，最后介绍本发明的应用场景。

1.主要功能模块

如图1所示，本发明涉及的研究内容为图1中的灰色部分，功能模块包括QoS映射、QoS协商、QoS资源、路由表计算、传输控制。QoS映射将用户QoS表示为计算机可处理的描述形式；QoS协商模块运行QoS协商机制，QoS协商机制是基于网络的有效资源和应用流的不同QoS需求而建立协商规则；路由表计算模块运行QoS路由协议来寻找路径；传输控制模块运行在应用层，其控制各个应用流的传输，并维护一张应用流传输表；QoS资源模块用于测量获得网络带宽资源、链路的状态信息，并且维护网络资源的信息。

整体功能模块之间的操作过程，如图1中的数字箭头所示。下面说明实现过程：

步骤1：外部的角色是用户，用户QoS描述用户传输应用流的QoS需求，并传给QoS映射模块；

步骤2：QoS映射将用户QoS表示为计算机可处理的描述形式，并将结果传给QoS协商模块；

步骤3：QoS资源也将测量的链路状态信息、及网络有效带宽信息传给QoS协商模块；

步骤4：基于前面两个信息的基础上，运行QoS协商机制，得出网络可以接入的应用流和可以满足的QoS指标；

步骤5：路由计算模块依据QoS协商后的QoS指标，寻找路由，找到满足不同应用流QoS需求的不同路径；

步骤6：传输控制模块根据QoS协商后的应用流、QoS指标的信息(如图1中的箭头6.1)，以及路由表计算模块得出的对应QoS指标的下一跳信息(如图1中的箭头6.2)，建立一个应用流的传输映射表；

步骤7：从应用层来的应用流根据步骤6得出的传输映射表，向下发送。

2.应用流服务质量的描述

用户服务质量描述的工作是将用户对应用流的QoS需求表示为计算机可处理的描述形式。这部分工作由图1中的QoS映射模块来实现。在应用程序的开始阶段，用户可以提出对应用流的QoS需求，包括各个应用流的级别，QoS指标及其范围、以及传输应用流时用户获得的收益和不进行传输下遭受的损失。

应用流s_i的级别可用变量level_i表示，level_i取[1，n]中间的自然数。不同level_i的应用流s_i有对应不同的权重w_i，w_i的值取(0，1)之间的小数。级别和权重都反映了应用流s_i在n个应用流中的优先级，即相对重要性。

当应用流s有N个QoS指标时，QoS指标可以描述为Q_n(s)。Q_n(s)是L个QoS指标的集合。第n个应用流的QoS需求可以描述为以下形式：

Q_n(s)＝(q_n(1，min)，q_n(1，max)，q_n(2，min)，q_n(2，max)，…q_n(L，min)，q_n(L，max))其中n＝1，…N，q_n(L，min)和q_n(L，max)是用户描述的第L级别应用流的QoS指标要求的最小值和最大值。L的值越小，QoS指标的级别越高，说明应用流s对该QoS指标的要求严格。

此外，用变量Win_n(s)描述传输应用流s时用户所获得的收益，用Loss_n(s)描述应用流s传输不成功时用户造成的损失值。每个应用流具有不同的效益/损失函数，这取决于用户的需求和数据的内容。

在传输n个应用流情况下，用户获得的收益和可以表示为以下形式：

其中i＝1，…n

同样在应用流传输不成功时，带给用户的损失函数表示为以下形式：

其中i＝1，…n

使用效益(benefit)函数B(Q_n(s))描述用户在传输n个应用流具有Q_n(s)的服务质量下的总的受益情况，其值为总的收益值Win(s)减去总的Loss(s)，反映了不同传输方式下的受益情况。B(Q_n(s))值在(1，100)范围之间，其值越大表示用户该传输方式下所获得的效益越高。效益函数可用在资源有限的情况下对QoS参数的限制。效益函数B(Q_n(s))的计算公式可以表示为如下形式：

B(Q_n(s))＝Win(s)-Loss(s)   其中n∈(1，2，…N)

此外，假设应用流s_i在满足Q_n(s)指标下需要分配的网络资源为r_i，假定总的有效带宽资源为R_total，则资源使用的限制条件为如下表达式：

$\underset{1}{\overset{n}{\mathrm{\Σ}}}{r}_i\left(Q_n\left(s\right)\right)\≤R_{\mathrm{total}}$其中i＝1，...n

下面以文件传输为例，说明应用流s的QoS需求的表示方式。文件传输对可靠性要求严格，吞吐量的要求次之，对延时和抖动的较弱，根据IETF草案《rfc1193：Client requirementsfor real-time communication services》，文件传输流的各项QoS指标为如下表所示：

表1

注：其中的-表示没有上限或者下限制

按照上面所述的QoS描述形式可以表示为：

Q₁(S)＝(q₁(1，95％)，q₁(1，100％)，q₂(2，728)，q₂(2，-)，q₃(3，-)，q₃(3，1500)，q₄(4，-)，q₄(4，1500))

Win₁＝60，Loss₁＝30，w1＝0.40

3.QoS的协商机制的控制方式以及协商算法

QoS协商机制必须在节点间采取集中控制、或者分布式控制的方式实现。由于本发明适用于小规模的语音视频等多媒体流传输的场景，如小组的视频会议，因此本发明采用集中控制的方式。如图2所示，由移动节点1、2、3、4、5组成的无线移动自组织网络，节点之间通过无线链路进行通信，控制节点A收集网络中其他节点的传输应用流的QoS需求，获得各节点测量得到的网络带宽资源、链路状态信息，并且由控制节点A运行QoS协商机制。在此方案中控制节点要求与网络中的其他节点保持实时通信。

QoS协商机制的原则是：保证传输不同级别应用流下网络获得最大的效益函数，同时尽力保证不同应用流的QoS指标，在无法满足最优的QoS指标下也满足其次优的QoS指标。

QoS协商算法的流程图如图3所示，其中用到的一些参数如下所示：

s_i；表示第i条应用流s；

r_i：表示第i条应用流s的传输流量需求；

R_total：表示初始给定的网络有效带宽资源；

R_reserve：表示分配给预留的资源；

R_alloc：表示分配给请求流的资源；

R_used：表示当前使用的总资源；

R_avail：表示可以分配的有效资源，其值等于(R_total-R_used)；

Ψ(r_i)：表示降级服务的资源需求，值可以为r_i/k，其中k为一个常系数。

设应用流s1、s2、s3的优先级分别为1、2、3。下面结合图3说明协商算法的过程，步骤如下：

步骤1：首先获得各应用流QoS的需求，以及网络带宽资源和链路状态信息。

步骤2：判断请求接入的应用流的总资源需求量是否小于网络有效资源的总量，即判断下列不等式：

$\underset{1}{\overset{3}{\mathrm{\Σ}}}{r}_i\left(Q_n\left(s\right)\right)\≤R_{\mathrm{total}}$

步骤3：如果步骤2的不等式成立，则传输控制模块没有降级服务地、按照3个流的优先级顺序分别接入s1、s2、s3。如果不等式不成立，则执行步骤4。

步骤4：计算应用流所有可能的接入组合方式，设应用流允许接入为+，拒绝为-，有以下接入方式：

(-s1，+s2，+s3)、(+s1，-s2，+s3)、(+s1，+s2，-s3)、

(-s1，-s2，+s3)、(-s1，+s2，-s3)、(+s1，-s2，-s3)

步骤5：基于步骤4中的各种接入方式，计算下列公式的值：

将接入某应用流的Win(s)减去拒绝其它应用流的损失Loss(s)，计算所有B(Q_n(s))可能值，计算公式如下：

B(Q_n(s))＝Win(s)-Loss(s)

计算接入应用流需要的网络资源，满足应用流所需的网络带宽资源小于剩余的网络总带宽资源，即如下约束条件：

$\underset{1}{\overset{n}{\mathrm{\Σ}}}{r}_i\left(Q_n\left(s\right)\right)\≤R_{\mathrm{total}}$

计算单位资源的效益值，取单位资源的效益值最大值，利用如下公式：

$\max \left\{\frac{B\left(Q_n\left(s\right)\right)}{\underset{1}{\overset{n}{\mathrm{\Σ}}}{r}_i\left(Q_n\left(s\right)\right)}\right\}$

步骤6：确定产生上述步骤5中，单位资源的效益值最大值下应用流的的传输方式。分配网络资源，利用下面公式计算使用的网络资源以及剩余的有效资源：

${R_{\mathrm{alloc}}}^{*}\←\underset{i}{\mathrm{\Σ}}{r}_i$

${R_{\mathrm{used}}}^{*}\←R_{\mathrm{used}}+\underset{i}{\mathrm{\Σ}}{r}_i$

R_avail^*←R_total-R_used

注：上面公式中加^*号表示中间结果。

步骤7：在完成上述分配方案后如果还有剩余的网络带宽资源，即R_avail^*≥0，则对剩余的应用流进行降级接入。

R_alloc←Ψ(R_reserve)

R_used←R_used+R_alloc

degraded＝1

注：上式中ψ(R_reserve)∈(0，r_i)，即满足降级后分配的网络资源小于初定的资源需求。Degraded＝1表示降级标志。

如果剩余应用流的降级服务级别存在，则分配剩余资源；否则，拒绝剩余的应用流接入。

4.应用流传输控制

传输控制模块的功能是控制应用流的发送。传输控制模块需要维护一张应用流的传输映射表，描述针对允许接入的应用流s_i在满足某QoS指标下，到达目的的下一跳地址。

下面分析传输控制模块如何维护着一张传输映射表。如图4所示，QoS协商机制指导QoS路由协议的寻径，即路由计算；路由计算后，路由协议将对应某QoS指标(如带宽、延时、抖动等)的下一跳地址信息、以及本地信息(包括本地地址)，写入到传输映射表中；QoS协商模块也写入其他QoS信息。最后的传输映射表包含的信息有：应用流的ID、流类型、本地地址、目的地址、QoS指标、下一跳。

本发明中采用应用层转发的方式。应用流去查询应用层的传输映射表进行下一跳的转发。

5.本发明的应用场景

本发明可适用于小规模网络中多节点对之间传输不同应用流、以及单节点对之间传输多应用流的情况。如图5和图6中，多个移动终端(可以是笔记本或者移动终端PDA)搭建的无线移动自组织网络，节点通过无线链路进行通信，每个节点上通过无线自组织网络的路由协议进行寻径、转发报文。图5的场景表示的是多对源节点和目的节点之间传输不同的应用流，图6的场景表示的是单对节点对之间应用流的传输，所示的场景图中传输的应用流可以有文件流、语音、视频(图片等)。

针对不同的应用流，用户关注的服务质量是不同的，如文件传输对可靠性要求严格，带宽次之，而对延时、抖动要求较弱；语音流对抖动的要求严格，带宽次之，对延时、可靠性要求较弱；视频流也对抖动、带宽要求严格，对延时、可靠性要求较弱。采用本发明的动态QoS协商机制来指导QoS路由协议，可以寻找满足不同QoS指标的路径，如图5和图6中所示的不同颜色路径。

以上所述仅是本发明动态保证服务质量的无线移动自组织网络路由方法的优选实施方式，应当指出，对于本技术领域的技术人员来说，在不脱离本发明方法原理的前提下，还可以作出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。