一种多并发流无线网状网中的机会路由方法

摘要

本发明公开了一种多并发流无线网状网中的机会路由方法，将候选节点视作资源，在分析资源约束和路由约束的情况下，将多并发流中的机会路由问题建模为一个凸优化问题，基于对偶和子梯度方法，提出了联合候选节点选择和速率分配的分布式算法。该算法迭代进行流量速率分配，并通过速率分配来决定节点是否作为流的候选节点，以在保证公平性前提下最大化网络吞吐量。实验结果表明，与基于ETX和EAX指标的机会路由方式相比，本发明的方法更能提升网络汇聚吞吐量，平均比ETX和EAX提高33.4%和27.9%。

说明书

技术领域

本发明涉及无线网络中机会路由技术，特别是指在多并发流无线网状网 中的机会路由方法。

背景技术

机会路由是多跳无线网络中新兴的路由方式，它利用无线媒介广播性质 和多用户分集，不事先确定路由的下一跳，直接广播发送数据包，周围可能 有多个邻居节点都正确收到数据包。在收到数据包的节点间进行某种协调， 由其中一个离目的节点最“近”的节点继续转发。当然并不是所有的节点都 参与，机会路由按某种规则选择其中的一部分参加，这些被选中的邻居节点 称为候选节点或候选转发节点。经多方验证，与只有一个预先设定下一跳的 传统固定路由相比，机会路由这种使用多个候选节点转发数据包的方式更能 适应不可靠的无线链路，尤其能充分利用远距离和高丢失率的无线链路，能 明显提升多跳无线网络，尤其是无线网状网的端到端吞吐量。

举例说明机会路由的基本思想，如图1所示的链式的多跳无线网络中存在 5个节点，节点间边上的值表示两节点间链路的包投递率（Packet Delivery  Ratio，PDR），即数据包通过此链路正确接收的概率。PDR的计算方法为一定 时间范围内，目的节点正确接收数据包数量和发送节点发送的所有数据包数 量之比，距离越远链路包投递率越低。节点0需要发送数据给节点4。

采用传统路由（Traditional Routing，TR）存在多种不同的路由路径。如 节点0以一跳直接发送到节点4，因为链路的丢失可能需要为每个包发送多次； 或者节点0经过节点1、2和3以四跳发送到节点4，因为多跳传输每个包也需要 传输多次。当节点0直接传给节点4时，节点4可能没有收到，但因为无线是广 播媒介，节点1、2甚至节点3可能正确偷听（overhear）到数据包，而且节点1、 2和3是否正确偷听到数据包是相互独立的，即多用户分集特性。那么由正确 偷听到数据包的节点1或节点2或节点3重发数据包给节点4应该要比节点0重 发更好。当采用四跳传输时，节点2、节点3甚至节点4可能正确偷听到节点0 给节点1发送的部分数据包，如果节点1再转发这些数据包给它们就造成了冗 余，导致信道资源的浪费。

机会路由发掘多用户间的差异性，充分利用传输的机会，不预先设定一 个固定的下一跳转发节点而是设定多个候选节点或候选转发节点（Candidate  Forwarder），在发送数据包后，根据候选节点的实际接收数据包情况，在所有 正确接收的候选节点中选择距离目的节点最近的候选节点作为真正的转发节 点，以达到减少传输次数提高吞吐量的目的。本例中节点4、3、2和1都是节 点0的候选节点。当节点0发送某个数据包后，节点2和1正确接收但节点3和节 点4未正确接收，距离目的节点最近的节点2成为这个数据包真正的转发节点。 当节点0发送下一个数据包后，节点4、2和1都正确接收，节点4就是目的节点 本身就不需要再转发。

现有的机会路由一般计算从源节点到目的节点可能经过的所有路径上产 生的期望传输次数、期望传输时间、路由效用或开销，来进行机会路由选择。 但是，这些路由指标都是在不考虑流分布情况下来进行路径选择和确定候选 节点，即在任何流分布和节点负载情况下，所选择的路径都是一样的。由于 网络数据流分布的局部性，数据流在时间和空间上的分布往往很不均匀，因 此，不考虑流分布的路径选择可能导致多个数据流集中经过某一些区域，使 得某些候选节点过载而其它节点空闲。

一方面，候选节点负载不均衡将阻止网络提供健康公平的服务。重负载 将耗尽候选节点的带宽，处理能力和内存资源。一旦过载的候选节点发生拥 塞，将造成数据包丢失和缓存溢出，这些节点成为端到端的性能瓶颈，导致 长延时和吞吐量下降。另外充分利用未使用的空闲路径和候选节点可以进一 步提升网络吞吐量。因此需要均衡分配网络候选节点资源。另一方面当网络 中存在多个并发流时，一个节点可能成为多条流的候选节点，这个节点如何 为多条流服务，节点为每条流服务的流量速率如何分配才能获得更好的吞吐 量是未知的问题。这些问题可以通过引入联合候选节点选择和速率分配的多 流机会路由算法解决。

发明内容

本发明所要解决的技术问题是，针对现有技术不足，提供一种多并发流 无线网状网中的机会路由方法，在保证公平性前提下最大化网络吞吐量，能 有效避免某些距离较远、跳数较多的流饿死情况的发生。

为解决上述技术问题，本发明所采用的技术方案是：一种多并发流无线 网状网中的机会路由方法，该方法为：

1）将多并发流无线网状网对应成一个无向图G=(V,E)，所述无向图包含N 个节点，其中V为节点集，E为节点间链路的矩阵，存在K条多并发流，源 节点和目的节点分别为{(s_k,d_k),k=1..K}；

2）建立多并发流无线网状网中各条网络流吞吐量λ_k之积的目标函数模型 $\max \mathrm{imize}\underset{k\in [1,K]}{\Pi }{\lambda }_k,\max \mathrm{imize}\underset{k\in [1,K]}{\Pi }{\lambda }_k$等价为$\max \mathrm{imize}\underset{k\in [1,K]}{\Sigma }1n\left({\lambda }_k\right):$

$\left(\begin{array}{c}\max \mathrm{imize}\underset{k\in [1,K]}{\Sigma }1n\left({\lambda }_k\right)\\ s.t.{\alpha }_{\mathrm{uv}}^k={\beta }_u^k*{\beta }_v^k*{\mathrm{BH}}_{\mathrm{uv}},\forall k\in [1,K],\forall (u,v)\in E\\ \underset{v}{\Sigma }{\alpha }_{\mathrm{uv}}^k{r}_k(u,v)-\underset{w}{\Sigma }{\alpha }_{\mathrm{wu}}^k{r}_k(w,u)=h_k\left(u\right),\forall k\in [1,K],\forall u\in V\\ {\alpha }_{\mathrm{uv}}^k{r}_k(u,v)=r_k(u,v)\forall k\in [1,K],\forall (u,v)\in E\\ \underset{k\in [1,K]}{\Sigma }{\beta }_u^k{b}_k\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right)}{\Sigma }{\beta }_v^k{b}_k\left(v\right)\le C,\forall u\ne s_k\\ {\beta }_u^k{b}_k\left(u\right)=b_k\left(u\right),\forall k\in [1,K],\forall u\in V\\ b_k\left(u\right)*p(u,v)\ge r_k(u,v),\forall k\in [1,K],\forall (u,v)\in E\\ {\alpha }_{\mathrm{uv}}^k=\left\{\mathrm{0,1}\right\},\forall k\in [1,K],\forall (u,v)\in E\\ {\beta }_u^k=\left\{\mathrm{0,1}\right\},\forall k\in [1,K],\forall u\in V\\ 0\le r_k(u,v)\le C,\forall k\in [1,K],\forall (u,v)\in E\\ 0\le b_k\left(u\right)\le C,\forall k\in [1,K],\forall u\in V\end{array}\right)\text{;}$

其中，s.t.表示约束条件；表示节点u是否作为第k条流的候选转发节点， 若节点u作为第k条流的候选转发节点，则为1，否则为0；表示节点v 是否作为第k条流的候选转发节点，若节点v作为第k条流的候选转发节点， 则为1，否则为0；表示节点u和v之间的链路是否为第k条流所用，若 节点u和v之间的链路是否作为第k条流所使用，则为1，否则为0；BH_uv表 示节点u和v的邻居关系，u和v互为邻居时BH_uv值为1，否则为0；r_k(u,v)表 示第k条流在链路(u,v)上的流速率；r_k(w,u)表示第k条流在链路(w,u)上的流速 率；λ_k表示第k条流的吞吐量；b_k(v)为节点v的平均广播 速率；b_k(u)为节点u的平均广播速率，表示节点u在 第t个调度时槽是否为第k条流传输数据，为1表示发送，否则为0； T为调度时槽个数；C为MAC层的容量；b_k(v)为节点v的平均广播速率;p(u,v) 表示链路(u,v)的包投递率；

3）将上述目标函数模型的等价表达式转化为以下优化模 型：

$\left(\begin{array}{c}\max \mathrm{imize}\underset{k\in [1,K]}{\Sigma }1n\left({\lambda }_k\right)\\ s.t.b_k\left(u\right)*p(u,v)\ge r_k(u,v),\forall k\in [1,K],\forall (u,v)\in E\\ \underset{v}{\Sigma }{r}_k(u,v)-\underset{w}{\Sigma }{r}_k(w,u)=h_k\left(u\right),\forall k\in [1,K],\forall u\in V\\ \underset{k\in [1,K]}{\Sigma }{b}_k\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right)}{\Sigma }{b}_k\left(v\right)\le C,\forall u\ne s_k\\ 0\le r_k(u,v)\le C,\forall k\in [1,K],\forall (u,v)\in E\\ 0\le b_k\left(u\right)\le C,\forall k\in [1,K],\forall u\in V\end{array}\right);$

4）将上述优化模型转化为以下标准形式：

$\left(\begin{array}{c}\min \mathrm{imize}-\underset{k\in [1,K]}{\Sigma }1n\left({\lambda }_k\right)\\ s.t.r_k(u,v)-b_k\left(u\right)*p(u,v)\le 0,\forall k\in [1,K],\forall (u,v)\in E\\ \underset{v}{\Sigma }{r}_k(u,v)-\underset{w}{\Sigma }{r}_k(w,u)=\mathrm{hk}\left(u\right),\forall k\in [1,K],\forall u\in V\\ \underset{k\in [1,K]}{\Sigma }{b}_k\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right)}{\Sigma }{b}_k\left(v\right)-C\le 0,\forall u\ne s_k;\\ 0\le r_k(u,v)\le C,\forall k\in [1,K],\forall (u,v)\in E\\ 0\le b_k\left(u\right)\le C,\forall k\in [1,K],\forall u\in V\end{array}\right)$

5）初始化，设定i为0，随机设定初始参数其中和x⁽ⁱ⁾(u)分别表示和的对偶参数；

6）设定i为1；

7）为步骤4）中的模型引入对偶参数，建立拉格朗日函数，其中约束条 件的对偶参数是x(u),约束条件 的对偶参数是y_k(u,v)，根据对偶和子梯度 法求解方法，利用下式更新对偶参数：

$\left(\begin{array}{c}{x}^{\left(i\right)}\left(u\right)=\max (0,x^{(i-1)}\left(u\right)+\eta M_u^{(i-1)})\\ y_f^{\left(i\right)}(u,v)=\max (0,y_k^{(i-1)}(u,v)+\eta H_{(k,u,v)}^{(i-1)})\\ M_u^{(i-1)}=\underset{f\in [1,F]u\ne s_k}{\Sigma }{b_k^{(i-1)}\left(u\right)}^{}+\underset{f\in [1,F]}{\Sigma }\underset{v\in R\left(u\right),u\ne s_k}{\Sigma }{b}_k^{(i-1)}\left(v\right)-C\\ H_{(k,u.v)}^{(i-1)}={r_k}^{(i-1)}(u,v)-b_k^{(i-1)}\left(u\right)p(u,v)\end{array};\right)$

其中，x^(i-1)(u)和为第i-1次迭代的对偶参数，η为步长，分别为x(u)和y_k(u,v)的对偶梯度，为第i-1次迭代中节点u的平均广播速 率，为第i-1次迭代中链路(u,v)在第k条流上的流速率；

8）根据第i次迭代的对偶参数，计算第i次迭代中第k条流在链路(u,v) 上的流速率和节点u的平均广播速率

$b_k^{\left(i\right)}\left(u\right)b_k^{(i-1)}\left(u\right)+\frac{1}{2ϵ}(\underset{(u,v)\in E}{\Sigma }{y}_k^{\left(i\right)}(u,v)p(u,v)-x^{\left(i\right)}\left(u\right)u\ne s_k-\underset{v\in R\left(u\right),v\ne s_k}{\Sigma }{x}^{\left(i\right)}\left(v\right))$

其中：为第i次迭代中第k条流的流速率；π为第k 条流源节点到目的节点的任意一条路径；为第i次迭代链路(u,v)的对偶 参数，即链路(u,v)的开销；为第i次迭代中第k条流中开销最小的路径的 开销；若链路$(u,v)\in \underset{\pi }{\arg \min }\underset{(u,v)\in \pi }{\Sigma }{y}_k^{\left(i\right)}(u,v),$则${r_k}^{\left(i\right)}(u,v)={\Gamma }_k^i;$否则${r_k}^{\left(i\right)}(u,v)=0;$

9)计算第i次迭代中第k条流在链路(u,v)上的平均流速率计算第i次迭代中节点u的平均广播速率的平均值判断前后两次迭代的差是否小于10^-4，若是， 进入10）；否则，令i=i+1，返回7），直到当前迭代次数i大于最大迭代次数 run，run>0，得到收敛后的进入10）；；

10）利用收敛后的根据下式得到最大的目标函数值

11）利用收敛后的和根据下式得到和

${\alpha }_{\mathrm{uv}}^k=\left(\begin{array}{c}1{{,\tilde{r}}_k}^{\left(i\right)}(u,v)\ne 0\\ 0,{{\tilde{r}}_k}^{\left(i\right)}(u,v)=0\end{array},,\forall k\in [1,K],\forall (u,v)\in E;\right)$

${\beta }_u^k=\left(\begin{array}{c}1,{{\tilde{b}}_k}^{\left(i\right)}\left(u\right)\ne 0\\ 0,\mathrm{otherwise}\end{array},\forall k\in [1,K]\right).$

与现有技术相比，本发明所具有的有益效果为：本发明的方法能在保证 公平性前提下最大化网络吞吐量，有效避免某些距离较远、跳数较多的流饿 死情况的发生；本发明的方法具有较强的拓扑无关性和稳定性；与基于ETX 和EAX指标的机会路由方式相比，本发明的方法更能提升网络汇聚吞吐量， 平均比ETX和EAX提高33.4%和27.9%。

附图说明

图1机会路由基本原理示意图；

图2是多并发流通信场景下的机会路由选择；图2(a)未考虑流分布的机会 路由选择；图2(b)考虑流分布的机会路由选择；

图3是本发明中16个节点拓扑图1；

图4是本发明中三条并发流吞吐量随轮数变化图；

图5是本发明中16个节点拓扑图2；

图6是本发明中六条并发流吞吐量随轮数变化图；

图7是本发明中流均衡指标示意图；

图8是本发明中汇聚吞吐量。

具体实施方式

当无线网状网中存在多条并发流时，需要为所有并发流选择路由和候选 节点。如图2(a)所示，s表示源节点，d表示目的节点，R表示可作为候选节 点的中间节点。存在两条并发流，分别从s₀到d₀和s₁到d₁。每条流的源节点、 目的节点和相应所用到候选节点被用虚线框标出，实线箭头表示第一条流的 数据流向，虚线箭头表示第二条流的数据流向。由于两条流的源和目的节点 位置靠近，使用ETX或EAX它们会同时选择相同的几个节点作为候选节点。 如图2(a)，两条流同时选择了节点R₂，R₄，R₇，第二条流还选择了节点R₅， 节点R₁，R₃，R₆，R₈未被选择。这样导致部分候选节点空闲部分候选节点过 载，不能充分提升网络吞吐量。考虑流分布后的候选节点选择结果如图2(b) 所示，两条流充分利用了所有可用的候选节点。另外，同时为两个流服务的 节点如R₄，合理分配为两条流服务的时间，也就是转发的速率，将会达到更 好的吞吐量性能。因此我们要解决的是如何根据流分布均衡分配网络节点和 速率资源，保证数据流之间的公平性前提下最大化吞吐量。

我们将这一场景描述成一个对应无向图G=(V,E)，包含N个节点，其中V 为N个节点集，E为表示节点间链路的矩阵。只有当两节点间的链路包投递 率大于某阈值才认为它们之间的直接链路存在，互为邻居。也就是说对于任 何一条链路l(u,v)∈E都有一个对应的链路包投递率p(u,v)，表示在无干扰情况下链 路正确接收数据包成功率，这个值可以通过传播模型计算获得。假设任意节 点的链路包投递率都是独立的。定义节点u的一跳的邻居R(u)为p(u,v)≥P₀的节点 集合，其中P₀<<1。对于剩下的任何不属于R(u)的节点v，链路包投递率为0， 即p(u,v)=0。无线网状网中，存在K条流，源节点和目的节点分别为{(s_k,d_k), i=1..K}。

需解决的问题是为这K条流寻找机会路由的路径和每个候选节点为每条 流的最优转发速率，保证数据流之间的公平性同时最大化所有流的吞吐量。

我们对这一问题进行形式化描述，先给出多流环境机会路由约束和其它 相关约束，然后提出优化网络性能的目标和形式化表述，最后为了方便问题 求解，根据参数的依赖关系对问题进行转化。

1.多流环境机会路由约束

网络中每条流的源节点、目的节点和候选节点构成一个子图，包含在第k 条流路径的节点和链路将组成一个子图G(V_k,E_k)。

用表示节点u是否作为第k条流的候选转发节点。如式(1)所示，定 义为：节点u作为第k条流的候选转发节点，则为1；否则为0。

用表示节点u和v之间的链路是否作为第k条流所使用。如式(2)所示， 节点u和v之间的链路是否作为第k条流所使用，则为1；否则为0。

只有当节点u和节点v同时作为第k条流的转发节点，且节点u和v互为 邻居时，节点u和v间的链路才会被第k条流所使用，如式(3)所示。

${\alpha }_{\mathrm{uv}}^k={\beta }_u^k*{\beta }_v^k*{\mathrm{BH}}_{\mathrm{uv}},\forall k\in [1,K],\forall (u,v)\in E---\left(3\right)$

其中，BH_uv表示节点u和v的邻居关系，互为邻居时BH_uv值为1；否则为 0。

2.机会路由其它相关约束

1)流守恒约束

每个节点都必须满足流守恒约束，即对于每一条流的中间节点流出的流 速率等于流入的流速率。每条流的源节点流出的流速率是该流的吞吐量，目 的节点流入的流速率是该流的吞吐量，方向相反。

$\underset{v}{\Sigma }{\alpha }_{\mathrm{uv}}^k{r}_k(u,v)-\underset{w}{\Sigma }{\alpha }_{\mathrm{wu}}^k{r}_k(w,u)=h_k\left(u\right),\forall k\in [1,K],\forall u\in V---\left(4\right)$

其中，表示第k条流在链路(u,v)上的流速率， λ_k,s_k,d_k分别表示第k条流的吞吐量、源节点和目的节点。

进一步，只有当链路参与流的传输，链路上的流速率才不为0；否则，链 路的流速率一定为0。这一约束可用式(5)表达：

${\alpha }_{\mathrm{uv}}^k{r}_k(u,v)=r_k(u,v),\forall k\in [1,K],\forall (u,v)\in E---\left(5\right)$

2)MAC层广播速率约束

由于无线媒介的共享性，节点按照媒介接入层协议顺序或竞争使用信道 资源。节点占有信道资源的时间和广播速率由MAC层协议决定。考虑一个无 竞争的基于时槽的MAC广播，可推广到802.11MAC层。用(u)表示节点u 在第t个时槽是否为第k条流传输数据，1为发送，否则为0。如节点u未参 与第k条流，即为0时，一定为0，因为节点u不会在任何时槽为第k 条流传输数据。R(u)表示节点u传输范围内的节点集合。为了不相互干扰，任 何时刻节点u的传输范围内只允许出现一个接收者，包括它自己，见式(6)。

因为源节点不用接收来自任何节点的数据，所以需要排除源节点。

$\underset{k\in [1,K]}{\Sigma }{\beta }_u^k{B}_k^t\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right)}{\Sigma }{\beta }_v^k{B}_k^t\left(v\right)\le 1,\forall u\ne s_k---\left(6\right)$

考虑如果存在T（T>0）个调度时槽，根据公式(6)可以得到：

$\frac{C}{T}\underset{t\in [1,T]}{\Sigma }\underset{k\in [1,K]}{\Sigma }{\beta }_u^k{B}_k^t\left(u\right)+\frac{C}{T}\underset{t\in [1,T]}{\Sigma }\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right)}{\Sigma }{\beta }_v^k{B}_k^t\left(v\right)\le C,\forall u\ne s_k---\left(7\right)$

其中，C为MAC层的容量是一个节点无干扰时的最大MAC层广播速率 （C有固定取值，比如1Mbps，2Mbps或11Mbps）。节点的平均广播速率可 以通过来计算，那么公式(7)就可以写成：

$\underset{k\in [1,K]}{\Sigma }{\beta }_u^k{b}_k\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right)}{\Sigma }{\beta }_v^k{b}_k\left(v\right)\le C,\forall u\ne s_k---\left(8\right)$

进一步，根据与的关系，可以得到b_k(u)与的关系。只有当节点 参与流的传输，节点平均广播速率才可能不为0；否则，节点平均广播速率一 定为0。这一约束可用式(9)表示：

${\beta }_u^k{b}_k\left(u\right)=b_k\left(u\right),\forall k\in [1,K],\forall u\in V---\left(9\right)$

3)编码约束

本发明中的机会路由的实现采用带编码的机会路由如MORE，节点的转 发速率不受转发顺序的影响，只受对应链路的链路质量约束。因此链路的实 际流速率必然小于发送节点的平均广播速率和链路包投递率之积，即满足下 式中的直接网络编码模型。

$b_k\left(u\right)*p(u,v)\ge r_k(u,v)\forall k\in [1,K],\forall (u,v)\in E---\left(10\right)$

其中，p(u,v)表示链路(u,v)的包投递率。虽然这一约束不是很严格，但也能 近似描述一个实际无线网状网的行为。虽然还存在更精确的约束模型，但却 是指数性的约束，会导致问题很难解。

3.问题形式化描述

本发明要解决的机会路由问题是，在有K条流存在的无线网状网中，通 过为每条流确定机会路由并进行速率分配，来最大化所有流的吞吐量同时还 要保证数据流之间的公平性。为了能保证公平性的前提下最大化所有网络流 的聚合吞吐量，而且能有效避免某些距离较远、跳数较多的流饿死情况的发 生，我们设计目标函数为最大化各条网络流吞吐量之积，即已 经证实，目标函数采用乘积形式可以达到资源分配公平性并最大化聚合吞吐 量的目的。但与现有技术不同的是，现有技术是在确定机会路由情况下，进 行速率分配以达到资源分配公平性并最大化聚合吞吐量的目的，而本发明需 要同时进行机会路由选择和速率分配。

因为可以等价于因此本发明的问题可以形 式化描述如下：

$\left(\begin{array}{c}\max \mathrm{imize}\underset{k\in [1,K]}{\Sigma }1n\left({\lambda }_k\right)\\ s.t.{\alpha }_{\mathrm{uv}}^k={\beta }_u^k*{\beta }_v^k*{\mathrm{BH}}_{\mathrm{uv}},\forall k\in [1,K],\forall (u,v)\in E\\ \underset{v}{\Sigma }{\alpha }_{\mathrm{uv}}^k{r}_k(u,v)-\underset{w}{\Sigma }{\alpha }_{\mathrm{wu}}^k{r}_k(w,u)=h_k\left(u\right),\forall k\in [1,K],\forall u\in V\\ {\alpha }_{\mathrm{uv}}^k{r}_k(u,v)=r_k(u,v)\forall k\in [1,K],\forall (u,v)\in E\\ \underset{k\in [1,K]}{\Sigma }{\beta }_u^k{b}_k\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right)}{\Sigma }{\beta }_v^k{b}_k\left(v\right)\le C,\forall u\ne s_k\\ {\beta }_u^k{b}_k\left(u\right)=b_k\left(u\right),\forall k\in [1,K],\forall u\in V\\ b_k\left(u\right)*p(u,v)\ge r_k(u,v),\forall k\in [1,K],\forall (u,v)\in E\\ {\alpha }_{\mathrm{uv}}^k=0\mathrm{or}1,\forall k\in [1,K],\forall (u,v)\in E\\ {\beta }_u^k=0\mathrm{or}1,\forall k\in [1,K],\forall u\in V\\ 0\le r_k(u,v)\le C,\forall k\in [1,K],\forall (u,v)\in E\\ 0\le b_k\left(u\right)\le C,\forall k\in [1,K],\forall u\in V\end{array}\right)\text{---}\left(11\right)$

其中参数包括α,β,r,b。由于问题中包含非线性的约束，难于求解，我们将 根据参数之间的关系，对问题进行转化。

4.问题转化

问题(11)中存在着两组非线性约束(4)(5)和(8)(9)。我们根据约束中参数之 间的依赖关系，将它们转化成线性约束。根据约束(5)中与r_k(u,v)之间的关 系，约束(4)和约束(5)可写成约束(12)和(13)。链路流速率不为0时，链路一定 参与了该流的传输。

$\underset{v}{\Sigma }{r}_k(u,v)-\underset{w}{\Sigma r_k}(w,u)=h_k\left(u\right),\forall k\in [1,K],\forall u\in V---\left(12\right)$

${\alpha }_{\mathrm{uv}}^k=\left(\begin{array}{c}1,r_k(u,v)\ne 0\\ 0,r_k(u,v)=0\end{array},,\forall k\in [1,K],\forall (u,v)\in E---\left(13\right)\right)$

根据约束(9)中与b_k(u)之间的关系，约束(8)和约束(9)可写成约束(14) 和(15)。节点平均广播速率不为0时，节点一定参与了该流的传输。

$\underset{k\in [1,K]}{\Sigma }{b}_k\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right)}{\Sigma }{b}_k\left(v\right)\le C,\forall u\ne s_k---\left(14\right)$

的计算公式为：${\beta }_u^k=\left(\begin{array}{cc}1,& b_k\left(u\right)\ne 0\\ 0,& \mathrm{otherwise}\end{array},,\forall k\in [1,K]---\left(15\right)\right)$

修改约束后，参数α,β只由r和b的取值决定。因此参数α,β可以暂不参 与到最终的模型中，确定r和b的值后，再通过约束(13)和(15)来确定α,β。这 样所有约束都为线性约束，使用前面定义的目标函数，(11)中的问题可以转化 如下：

$\left(\begin{array}{c}\max \mathrm{imize}\underset{k\in [1,K]}{\Sigma }1n\left({\lambda }_k\right)\\ s.t.\left(10\right)\left(12\right)\left(14\right)\\ 0\le r_k(u,v)\le C,\forall k\in [1,K],\forall (u,v)\in E---\left(16\right)\\ 0\le b_k\left(u\right)\le C,\forall k\in [1,K],\forall u\in V\end{array}\right)$

其中，变量包括r,b。

节点通过发送速率来决定自己是否参与到流中，是否为流转发。这一凸 优化模型可以通过内点法、单纯型法求解，但这种集中式的算法对于无线网 状网而言是不合适的，因此我们给出一个分布式的算法。

以下阐述本发明分布式的算法的技术原理：

通过分析发现问题(16)是凸优化问题，具有累加分解性。根据分解化思想 ^[15]，可以把全局最优问题分解到各个节点和链路上进行求解。然后根据对偶 和子梯度方法，通过解对偶问题，得到对偶变量的迭代更新方式。通过更新 后的对偶变量，再求解分解后的问题，迭代得收敛到最优解。根据求解的步 骤，设计分布式迭代算法。

1.基于对偶和子梯度方法的求解

为得到分布式算法，我们首先将问题(16)写成凸优化问题的标准形式问题 (17)。

$\left(\begin{array}{c}\min \mathrm{imize}-\underset{k\in [1,K]}{\Sigma }1n\left({\lambda }_k\right)\\ s.t.r_k(u,v)-b_k{\left(u\right)}^{*}p(u,v)\le 0,\forall k\in [1,K],\forall (u,v)\in E\\ \underset{v}{\Sigma }{r}_k(u,v)-\underset{w}{\Sigma }{r}_k(w,u)=h_k\left(u\right)\forall k\in [1,K],\forall u\in V\\ \underset{k\in [1,K]}{\Sigma }{b}_k\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right)}{\Sigma }{b}_k\left(v\right)-C\le 0,\forall u\ne s_k\\ 0\le r_k(u,v)\le C,\forall k\in [1,K],(u,v)\in E\\ 0\le b_k\left(u\right)\le C,\forall k\in [1,K],\forall u\in V\end{array}---\left(17\right)\right)$

通过引入对偶变量，我们可以得到满足约束(12)问题(17)的拉格朗日函数， 如下式。

$\left(\begin{array}{c}L(r,b,x,y)=-\underset{k\in [1,K]}{\Sigma }1n\left({\lambda }_k\right)+\underset{\mathrm{ueV}}{\Sigma }x\left(u\right)(\underset{k\in [1,K],u\ne \mathrm{sk}}{\Sigma }{b}_k\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right),u\ne s_k}{\Sigma }{b}_k\left(v\right)-C)\\ +\underset{k\in [1,K]}{\Sigma }\underset{(u,v)\in E}{\Sigma }{y}_k(u,v)(r_k(u,v)-b_k\left(u\right)p(u,v))\\ =-\underset{k\in [1,K]}{\Sigma }1n\left({\lambda }_k\right)+\underset{k\in [1,K]}{\Sigma }\underset{(u,v)\in E}{\Sigma }{y}_k(u,v)r_k(u,v)+\underset{k\in [1,K]}{\Sigma }\underset{u\in V,u\ne s_k}{\Sigma }x\left(u\right)b_k\left(u\right)+\\ \underset{k\in (1,K)}{\Sigma }\underset{u\in V}{\Sigma }\underset{v\in R\left(u\right),v\ne s_k}{\Sigma }x\left(v\right)b_k\left(u\right)-\underset{u\in V}{\Sigma }x\left(u\right)C-\underset{k\in [1,K]}{\Sigma }\underset{(u,v)\in E}{\Sigma }{y}_k(u,v)b_k\left(u\right)p(u,v)\end{array}---\left(18\right)\right)$

因此可以将L(r,b,x,y)在参数(r,b)上进行划分，问题(17)可以分解成为两个 子问题：

1)关于第k条流的流速率子问题L₁

$\left(\begin{array}{c}\min \mathrm{imize}-1n\left({\lambda }_k\right)+\underset{(u,v)\in E}{\Sigma }{y}_k(u,v)r_k(u,v)\\ s.t.\underset{v}{\Sigma }{r}_k(u,v)-\underset{w}{\Sigma }{r}_k(w,u)=h_k\left(u\right),\forall u\in V\\ 0\le r_k(u,v)\le C,\forall (u,v)\in E\end{array}---\left(19\right)\right)$

2)关于第k条流节点u的平均广播速率子问题L₂

$\left(\begin{array}{cc}\min \mathrm{imize}& b_k\left(u\right)({x\left(u\right)}_{u\ne \mathrm{sk}}+\underset{v\in R\left(u\right),v\ne \mathrm{sk}}{\Sigma }x\left(v\right)-\underset{(u,v)\in E}{\Sigma }{y}_k(u,v)p(u,v))\\ s.t.& 0\le b_k\left(u\right)\le C,\forall k\in [1,K]---\left(20\right)\end{array}\right)$

用最小梯度法联合解问题(19)(20)可以得到一个分布式的算法。

拉格朗日对偶函数是拉格朗日函数的最小值，满足约束(12)。

$G(x,y)=\underset{r,b}{\inf }\left\{L(r,b,x,y)\right\}---\left(21\right)$

问题(17)的对偶问题为maximize G(x,y)。根据对偶分解的方法，能够得到对 偶变量。第i轮的对偶参数如下式(22)更新，对偶变量的子梯度分别为M,H。

$\left(\begin{array}{c}\forall u\in V,x^{\left(i\right)}\left(u\right)=\max (0,x^{(i-1)}\left(u\right)+\eta M_u^{(i-1)})\\ \forall (u,v)\in E,y_k^{\left(i\right)}(u,v)=\max (0,y_k^{(i-1)}(u,v)+\eta H_{(k,u,v)}^{(i-1)})\end{array}---\left(22\right)\right)$

其中，

$\left(\begin{array}{c}{M}_u^{(i-1)}=\underset{k\in [1,K],u\ne s_k}{\Sigma }{b_k}^{(i-1)}\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right),u\ne s_k}{\Sigma }{b_k}^{(i-1)}\left(v\right)-C\\ H_{(k,u,v)}^{(i-1)}={r_k}^{(i-1)}(u,v)-{b_k}^{(i-1)}\left(u\right)p(u,v)\end{array}---\left(23\right)\right)$

1)子问题L₁求解

子问题L₁的目标函数为严格凸函数，可以基于流路径模型^[10]，将其转化为 等价问题(24)。

其中，P为第k条流源节点s_k到目的节点d_k之间的所有单路径集合，γ_k(π)是 第k条流在π路径上的流速率，明显这一等价问题的最优解总 是最小的路径，因此我们可将y_k(u,v)视作链路的开销，这就是一个选 择最小开销路径的问题，可以通过分布式最短路径算法得到。我们使用Γ_k表 示单路径上的流速率，问题就转化成问题(25)。

其中，是最小开销路径的开销值。目标函数为凸函数， 问题容易被解出如果链路(u,v)位于最小开销的路径上，那么问题(25) 解的值就为问题(24)中的值，否则问题(24)中的为0。因此每一条 第k条流都可以通过分布式最短路径算法来计算

2)子问题L₂求解

子问题L₂的目标函数为线性，收敛过程中可能抖动，我们加上一个部分使 之成为严格凸函数，取ε>0且足够小，使趋近于0，问题(26) 的解趋近于子问题L₂(20)的解。

$\left(\begin{array}{c}{\min \mathrm{imizeb}}_k^{\left(i\right)}\left(u\right)(x^{\left(i\right)}\left(u\right)u\ne \mathrm{sk}+\underset{v\in R\left(u\right),v\ne s_k}{\Sigma }{x}^{\left(i\right)}\left(v\right)-\underset{(u,v)\in E}{\Sigma }{y}_k^{\left(i\right)}(u,v)p(u,v))+ϵ\left|\right|b_k^{\left(i\right)}\left(u\right)-b_k^{(i-1)}\left(u\right){\left|\right|}^2\\ s.t.0\le b_k^{\left(i\right)}\left(u\right)\le C,\forall k\in [1,K]\end{array},---\left(26\right)\right)$

在每一轮，按如下方式更新：

$b_k^{\left(i\right)}\left(u\right)=b_k^{(i-1)}\left(u\right)\frac{1}{2ϵ}(\underset{(u,v)\in E}{\Sigma }{y}_k^{\left(i\right)}(u,v)p(u,v)-x^{\left(i\right)}\left(u\right)u\ne \mathrm{sk}-\underset{v\in R\left(u\right),v\ne s_k}{\Sigma }{x}^{\left(i\right)}\left(v\right))---\left(27\right)$

2.分布式算法

由于在每一轮求解问题(22)时，链路或者为某条流服务，或者不为，所以 的值或者为0，或者不为0，不能表示一段时间内链路为流服务的情况， 因此我们使用多轮的平均值来表示。同样为表示一段时间内节点为流服务的 情况，我们使用多轮平均值来表示节点的广播速率。第i轮平均的流速率和平 均广播速率如式(28)(29)所示。

${\tilde{r}}_k^{\left(i\right)}(u,v)=\frac{1}{i}\underset{m=0}{\overset{i}{\Sigma }}{r}_k^{\left(m\right)}(u,v)i\ge 1---\left(28\right)$

${\tilde{b}}_k^{\left(i\right)}\left(u\right)=\frac{1}{i}\underset{m=0}{\overset{i}{\Sigma }}{b}_k^{\left(m\right)}\left(u\right),i\ge 1---\left(29\right)$

根据上述问题(16)基于对偶和子梯度方法的求解步骤，本发明所设计的完 整的分布式多流机会路由算法ORMf如表1所示。

在第i轮，每个节点根据第i-1轮自己和邻居的平均广播速率和与自己相关 链路的流速率，通过式(30)更新本轮的对偶参数，接着每个节点根据本轮的对 偶变量(x⁽ⁱ⁾,y⁽ⁱ⁾)求解子问题L₁的等价问题(31)决定与自己相关链路的流速率，用 式(32)求解子问题L₂决定自己的平均广播速率，然后进入下一轮。

由于每个节点保存每轮自己的平均广播速率(b(u))、与自己相关链路的流 速率(r(u,v))、自己的对偶变量(x(u))和与自己相关链路的对偶变量(y(u,v))，根 据算法每个节点可在本地执行算法进行计算，不需要全局的信息：

1)在步骤1中，节点u计算对偶变量x⁽ⁱ⁾(u)时，节点u需要它自己和一跳邻居 的平均广播速率，自身的平均广播速率节点本地有保存，一跳邻居的平均广 播速率可通过邻居节点局部交互获得；节点u计算与自己相关链路在第k条流 的对偶变量时，节点u需要自己相关链路(u,v)在第k条流上的流速率和自 己的广播速率，这两类值节点本地都已保存。

2)在步骤2.1中，节点通过求解问题(31)计算流速率时可以采用分布式最 短路径算法来求解。链路开销是指链路对应的对偶参数y的值。这样定义的原 因是根据求解子问题L₁，我们基于流路径模型将问题L₁转换成路径模型的等价 问题。这一等价问题的最优解总是最小的路径，因此我们将y_k(u,v)视 作链路的开销，这就是一个选择最小开销路径的问题，可以通过分布式最短 路径算法得到。利用分布式最短路径算法（如Bellman-ford）通过节点间的信 息交互，节点可以得到第k条流的最小开销的路径的开销，这样就可以解问题 (31)，得到流速率。在步骤2.2中计算节点平均广播速率，根据式(32)节点需要 一跳邻居的对偶变量x信息，通过邻居节点的局部交互可收集获得。

3)参数的初始化值(r⁽⁰⁾,b⁽⁰⁾,x⁽⁰⁾,y⁽⁰⁾)在取值范围内随机设定，也可以通过分布 式方式协商。

4)算法中我们采用同步机制^[16]，每一轮为固定的时间，所有节点同时进 入下一轮。在每一轮中，需要进行对偶参数x、y的更新和r、b的计算。其中步 骤1中需要收集一跳邻居的平均广播速率信息，至多需要最大邻居数 {max|R(u)|,u∈V}个广播周期，R(u)为一跳邻居的集合；步骤2需要进行分布式最短 路径算法和一跳邻居的对偶变量x信息。前者至多需要节点个数|V|个广播周 期，后者可以在步骤1中同时获得。因此每一轮的时间是{max|R(u)|,u∈V}+|V|个广 播周期。

表1本发明的分布式算法

i从1开始直到i>run，重复执行1，2：

1.节点更新对偶参数x⁽ⁱ⁾,y⁽ⁱ⁾

$\left(\begin{array}{c}{x}^{\left(i\right)}\left(u\right)=\max (0,x^{(i-1)}\left(u\right)+\eta M_u^{(i-1)})\\ y_f^{\left(i\right)}(u,v)=\max (0,y_k^{(i-1)}(u,v)+\eta H_{(k,u,v)}^{(i-1)})\\ M_u^{(i-1)}=\underset{f\in [1,F]u\ne S_k}{\Sigma }{b_k^{(i-1)}\left(u\right)}^{}+\underset{f\in [1,F]}{\Sigma }\underset{v\in R\left(u\right),u\ne S_k}{\Sigma }{b}_k^{(i-1)}\left(v\right)-C\\ H_{(k,u.v)}^{(i-1)}={r_k}^{(i-1)}(u,v)-b_k^{(i-1)}\left(u\right)p(u,v)\end{array};\right)$

其中，x^(i-1)(u)和为上一轮的对偶参数，η为步长，为上一轮节点平均广 播速率，为上一轮链路(u,v)在第k条流上的流速率。

2.节点求解子问题L1和L2获得流速率和平均广播速率r⁽ⁱ⁾,b⁽ⁱ⁾

2.1子问题L₁求解获得r⁽ⁱ⁾

求解问题

其中，为本轮第k条流的流速率，π为第k条流的路 径，为本轮的对偶参数即链路的开销，为本轮第f条流开销最小的路径的 开销。

若链路$(u,v)\in \underset{\pi }{\arg \min }\underset{(u,v)\in \pi }{\Sigma }{y}_k^{\left(i\right)}(u,v),$则$r_k^{\left(i\right)}(u,v)={\Gamma }_k^i;$否则$r_k^{\left(i\right)}(u,v)=0$

2.2子问题L₂求解获得b⁽ⁱ⁾

$b_k^{\left(i\right)}\left(u\right)=b_k^{(i-1)}\left(u\right)+\frac{1}{2ϵ}(\underset{(u,v)\in E}{\Sigma }{y}_k^{\left(i\right)}(u,v)p(u,v)-x^{\left(i\right)}\left(u\right)u\ne s_k-\underset{v\in R\left(u\right),v\ne s_k}{\Sigma }{x}^{\left(i\right)}\left(v\right))---\left(33\right)$

5)算法分布式实现时，需要通过控制包来完成上述步骤1)、2)中节点间的 信息交换，主要存在于路由计算阶段。因此网络中存在两种类型的包，用于 路由计算的控制包和实际数据流的数据包。在路由计算阶段，为了算法的计 算，节点之间需要交换信息（如一跳邻居的平均广播速率和对偶变量x），这 些信息通过控制包进行传输。算法计算的平均广播速率是路由计算完成后， 节点为业务流的数据包进行传输时的速率。控制包的广播速率采用恒定速率， 不受所计算的速率影响。算法收敛后，将不再需要进行计算信息交互，也就 不需要发送控制包。

根据收敛后的值我们可以根据式(13)和(15)得到α,β，节点通过流速率 和平均广播速率来表明自己是否参与到流中，而不是事先决定是否参与数据 流转发，再确定转发的速率。

因此，本发明方法的特点是，通过分布式迭代执行的方法完成机会路由 的选择，每轮迭代过程中，迭代分配节点为流进行数据转发的流速率，所有 迭代过程中没有为流进行转发的节点就不作为该流的候选节点。

下面分析本发明方法的性能。

定理1使用本发明的方法（简称为ORMf），对偶变量 可以收敛到一个最优的解决方案x*,y*，而且此时对应的 主优化变量r*,b*为问题(17)的全局最优解。

证明：

因为主问题(17)的两个子问题(19)、(26)和其拉格朗日对偶问题(21)满足强 对偶的条件（strong duality），因此，我们可以通过设计分布式梯度算法解对 偶问题来获得问题的解。基于Danskin’s Theorem^[17]，可以得到：

$\left(\begin{array}{c}\frac{\partial \left(L(r^{\left(i\right)},b^{\left(i\right)},x^{\left(i\right)},y^{\left(i\right)})\right)}{\partial x^{\left(i\right)}\left(u\right)}=\underset{k\in [1,K]}{\Sigma }{b}_k^{\left(i\right)}\left(u\right)+\underset{k\in [1,K]}{\Sigma }\underset{v\in R\left(u\right),u\ne s_k}{\Sigma }{b}_k^{\left(i\right)}\left(v\right)-C,\forall u\in V\\ \frac{\partial \left(L(r^{\left(i\right)},b^{\left(i\right)},x^{\left(i\right)},y^{\left(i\right)})\right)}{\partial y_k^{\left(i\right)}(u,v)}=r_k^{\left(i\right)}(u,v)-b_k^{\left(i\right)}\left(u\right)p(u,v),\forall k\in [1,K],\forall (u,v)\in E\end{array}\right)---\left(33\right)$

因此，算法中式(30)是解对偶问题(21)的梯度投影算法（gradient projection  algorithm）。因为对偶目标函数是一个凸函数，因此，存在一个步长η，满足 可以收敛到最优x*,y*。

更进一步，因为主问题(17)的两个子问题(19)、(26)是一个凸优化问题而 且式(21)有唯一的解，因此r*,b*是问题的全局最优解。

我们通过实验来说明所本发明方法的性质。首先评估本发明方法的收敛 性，然后比较本发明方法与现有方法的性能。在分布式情况下获得的实验结 果表明本发明的方法能有效提高网络吞吐量。在300*300米的区域内随机放置 节点，只要两节点之间的投递率大于P₀(P₀=0.1)就存在一条链路。随机产生拓 扑，随机选择1到8对源节点和目的节点对组成并发流。在ORMf计算过程中， 取ε为0.05。更新的步长为我们预设收敛阈值为10^-4，当前后两轮端 到端吞吐量的差值绝对值小于10^-4就认为算法已经收敛，进入稳定状态。传播 模型使用shadowing模型，具体参数如表2所示。根据设定的传播模型参数，节 点通信范围为160米。当两点之间距离到达160米时，节点之间的包到达率就 只为0.1，到达我们设定的阈值P₀。

表2参数设置

收敛性分析：

我们通过二个不同拓扑和并发流个数的例子来考察本发明方法的收敛 性。在如图3所示的节点分布下，存在三条并发流，源节点分别为1，5，12， 目的节点分别为15，10，14。所有节点采用广播方式进行数据包发送，业务 为UDP，只要允许就尽力发送数据。其中本发明的方法中，源节点的发包速 率和别的节点的转发速率受算法中r和b限制。每条流吞吐量随计算轮数的变化 如图4所示，经过290轮迭代后，每条流的吞吐量变化都小于10^-4趋于平稳，算 法收敛，进入稳定状态。每个流的吞吐量分别约为1.72，1.27，1.03Mbps，汇 聚吞吐量约为4.02Mbps。每条流在三种不同的路由选择方式下所使用的候选 节点见表3，明显ORMf比ETX和EAX使用更多的候选节点。虽然EAX也选择 了多个候选节点，但它是在认为所有节点的负载相同的情况下进行选择，尽 可能选择对流最有益的节点。而且这样多条流可能都选择相同的某一些节点。 机会路由的性能由候选节点决定，本发明方法考虑将流的负载尽可能均衡得 分配给网络中的所有节点，因此所选择的候选节点数目会比EAX多。流量负 载能分配到更多的候选节点上，所以能达到更高的吞吐量。

表3三条并发流的候选节点

第二个例子是在如图5所示节点分布下，存在六条并发流的情况，源节点 分别为6，5，12，10，13，2，目的节点分别为16，3，14，1，4，9。如图6 所示，经过220轮迭代后，每条流的吞吐量变化都小于10^-4趋于平稳，算法收 敛，进入稳定状态。每条流的吞吐量分别约为0.32，0.72，1.50，0.45，0.80， 0.59Mbps，汇聚吞吐量约为4.38Mbps。每条流在三种不同的路由选择方式下 所使用的候选节点见表4，大多数时候ORMf比ETX和EAX使用更多的候选节 点，但对于最后一条流，ORMf没有选择本身已是源节点的6和12作为候选节 点，以获得更高的吞吐量。

表4六条并发流的候选节点

进一步，从图4和图6可以看出，无论在三条流的网络拓扑还是在六条流 的网络拓扑下，本发明的机会路由方法都可以达到最优的收敛状态。而且， 收敛速度与拓扑分布和并发流个数无关。这都说明本发明提出算法具有较强 的拓扑无关性和稳定性。

性能比较：

我们将ORMf与期望传输次数(ETX)和期望任意传输次数(EAX)作比较。

1)ETX

链路的ETX是链路包投递率的倒数。源节点到目的节点的ETX是最短路径 上链路的ETX之和。

ETX(u,v)=1/p(u,v)      (34)

ETX(s,d)=ETX(s,c)+ETX(c,d)    (35)

其中，p(u,v)为链路(u,v)的包投递率，s为源节点，d为目的节点，c为s到d 的下一跳。选择比当前节点ETX值小的邻居作为候选转发节点。

2)EAX

EAX考虑了多个候选节点为传输所做的贡献，源节点到目的节点的EAX 是源节点所有候选节点的EAX按优先级权重之和。只要至少1个候选节点收到 数据包，源节点的传输就算成功可以继续转发。而候选节点只有当比自己优 先级高的节点没有收到数据包时，才负责转发，这样EAX可迭代地表示为式 (36)，

$\mathrm{EAX}(s,d)=\frac{1+{\Sigma }_i\mathrm{EAX}(\mathrm{ci},d)p_i{\Pi }_{j-1}^{i-1}(1-\mathrm{pj})}{1-{\Pi }_{i\in J}(1-p_i)}---\left(36\right)$

其中，s为源节点，d为目的节点，J为候选节点集，c_i表示J中优先级为i 的节点，p_i表示s到c_i链路包投递率。公式(36)中代表s到候选节 点集J需要的传输次数，即需要J中至少有一个节点能成功接受。为节点c_i成功接收而优先级比i高的节点没有成功接收的概率，EAX(ci,d)表示节 点c_i到目的节点所需要的机会传输次数，两者之积再对i求和就是通过候选节 点集J转发到目的节点需要的机会传输次数。

比较的指标为不同路由选择方式下获得的流均衡指标和汇聚吞吐量。流 均衡指标：为3.3中定义的目标值，是所有流的吞吐量之积的对数。所有流获 得的吞吐量值之间越均衡，流均衡指标值越大。汇聚吞吐量：所有流吞吐量 之和。

随机产生4个拓扑，每个拓扑下随机选择10组源节点和目的节点对组成并 发流，顺序使用3种机会路由方式可获得的流均衡指标和汇聚吞吐量，然后取 平均值。并发流数目从一个开始逐步增加，直到所有节点都成为源节点或目 的节点。

流均衡指标随并发流个数从1到8的变化如图7所示。总体来看，不管在并 发流个数是多少情况下，ORMf方法的均衡性都要大于ETX和EAX。平均而言， ORMf算法产生的流均衡指标比ETX和EAX高28%和21.5%。

汇聚吞吐量随并发流个数从1到8的变化如图8所示。总体来看，随着并发 流的数据增加汇聚吞吐量也逐步增加，除6个和7个并发流时稍微比5个并发流 时少，这与流的源节点目的节点位置分布有关。ORMf算法产生的汇聚吞吐量 比ETX和EAX高33.4%和27.9%。

ORMf在进行路由选择的时候是在所有可用的节点和链路中为并发流进 行分配，而不是事先通过ETX或EAX对每条流所能使用的节点和链路进行 限定，这样所有流的数据包只能经过由ETX或EAX为其选择的节点和链路， 对这些已经限定了节点和链路的流而言其节点资源和流速率的分配都是受限 的，因此ORMf能获得更高的流均衡指标和汇聚吞吐量。