英语原文共 9 页

多速率多跳无线网络中机会路由的端到端吞吐量

摘要——由于无线链路的不可靠性和并发传输的干扰，在多跳无线网络中进行路由是一个巨大的挑战。最近提出了一个新的路由模型，即机会路由（OR），它可以利用无线媒介的广播特性和空间分集性来处理不可靠传输。关于OR的现有研究都是关于单信道速率的网络，而OR在多速率方案下的性能还没有被研究过。此外，尽管模拟仿真和实际运行都显示OR比传统路由有更好的表现，但是还没有关于OR所带来的容量提升或OR的网络容量界限的研究结果。在这篇论文中，我们带来了关于多速率、干扰、候选节点选择和优先级设置对OR的端到端最大吞吐量的影响的详尽研究。考虑到无线干扰，我们提出了一个新的方法来构造传输干扰图——我们对比链路冲突图提出了基于传输节点的冲突图。我们引入了并发传输节点集合的定义，来表示OR中传输冲突所带来的限制。然后我们根据传输冲突的限制，将最大化端到端吞吐量的问题规划为一个最大化流的线性规划问题。我们还提出了一个速率选择机制，并将多速率OR的吞吐量与单速率OR进行了比较。最后，我们通过模拟仿真证实了我们的分析结果，结果显示OR在提升端到端吞吐量上有巨大的潜能，并且系统在多速率情况下可以实现比单速率情况更高的吞吐量。

一、介绍

由于成本低、部署简单、不依赖于现有基础设施以及其广播应用，在战场上的战术通信、军事传感与追踪、震后救援、实时交通监控、野生动物监视和追踪、以及最后一公里网络接入等应用中，多跳无线网络，例如移动自组网（MANETs）、无线传感器网络（WSNs）和无线网格网络（WMNs），都在过去的十年里得到了越来越多的关注。

在多跳无线网络中的路由现在面临巨大挑战的原因主要有以下几点：第一，由于信道衰落[1]，无线链路是不可靠的。第二，由于链路质量于两个邻居节点间的距离和路径损耗有关，不同链路上的可用信道速率可能是不同的。第三，由于无线媒介有广播特性，一条链路上的传输可能会与其他相邻链路上的传输有干扰。

多跳无线网络中的传统路由方案都按照有线网络路由的概念，将无线链路抽象成有线链路，然后找到源节点和目的节点之间的最短路径、消耗最低路径或者最大吞吐量路径。然而，这样的抽象方法忽视了无线媒介特有的广播特性和空间分集性。根据这些无线特性，当一个数据包被单播给网络层中某一特定下一跳节点时，所有在发送节点有效通信范围内的邻居节点都可以在物理层中接收到数据包。所以在特定的下一跳节点没有接收到数据包时，有可能有一些其他的邻居节点接收到了。那么，一个自然的想法就是，“我们可以利用其他邻居节点的成功接收，而不是再次在特定链路上重传数据包，以此来节约宝贵的带宽和能量吗？”

启发于这个灵感，一个新的路由范式，即机会路由（OR）[2]-[5]被提出了。它利用无线媒介的广播特性和空间分集性来减轻无线传输不可靠性的影响。OR基本上是这样运作的：对于每一次本地数据包的转发，都在网络层中选择出一个下一跳转发候选节点集合，然后根据传输时的即时可用性和可到达性，选择集合中的一个节点作为MAC层的实际中继节点。由于有多个候选转发节点都可以帮助转发数据包，至少有一个转发候选节点可以准确接收到数据包，这与传统路由中单一转发节点的情况相比，候选节点接收到数据包的概率大大增加。传输中的转发可靠性增加，降低了重传成本，反过来这也提高了吞吐量[4]-[6]和能量效率[2],[7]。

现有的关于OR的研究主要聚焦于单速率系统。研究学者们提出了许多候选节点选择和优先级设置机制来提高吞吐量或能量效率。然而，缺少对OR可实现的性能界限或吞吐量界限的理论研究。此外，在无线通信中的一个现有趋势是让设备用多种传输速率运转。例如，许多现有的无线网络标准，比如IEEE 802.11a/b/g，都包括多速率性能。在多速率传输中固有的速率和距离之间的权衡对传统路由吞吐量性能有影响[8]-[10]。事实上，低速率传输的覆盖半径都比较大，同时高速率传输都是在近范围内发生。我们自然而然地想到，速率和距离之间的权衡可能也会影响OR的吞吐量。因为不同的传输范围也意味着不同的邻居节点集合，这就会带来不同的空间分集机会。速率、距离和多样性之间的权衡无疑会影响OR的吞吐量，这值得仔细研究。在我们所知范围内，目前还没有解决多速率网络中OR吞吐量问题的研究。

在这篇论文中，我们研究了多速率方案中OR的吞吐量界限和OR的性能，弥补了这些缺失。首先，对于OR，我们提出了并发传输节点集的概念来描述OR中的传输冲突所带来的限制。然后，对于一个已给定机会路由策略（即，候选转发节点选择和优先级设置方案）的给定网络，我们根据传输节点冲突的限制，将最大化端对端吞吐量问题规划为一个最大化流线性规划问题。此最优化问题的解就是OR的性能界限。这个方法为估计不同路由策略和传输速率的OR的性能提供了理论基础。我们还提出了一个速率选择机制，并将多速率OR和单速率OR的吞吐量做了比较。仿真结果显示，对于OR来说，系统在多速率下运转会比在单速率下运转实现更大的吞吐量。

这篇论文剩余部分的内容如下：第二章介绍了系统模型；第三章提出了计算OR吞吐量界限的方案；第四章研究了多速率性能和转发策略对OR吞吐量的影响，并提出了一个利用节点信息的速率和候选选择机制；第五章展示了仿真结果和分析结果；第六章讨论了相关研究；第七章给出了结论。

二、系统模型

我们考虑了一个多跳无线网络，它由个随机分布在飞机上的节点组成。每个节点都能以个不同的速率,,hellip;,传输数据包。当数据包接收率（），记为,大于一个非负阈值时，我们称从节点到存在一条可用链路。我们将等于时发送节点与接收节点之间的距离定义为速率时的有效传输范围。

机会路由的基本模式如图1所示。假设节点要向目的节点传输数据包，我们将在节点的有效传输范围内的节点集合定义为它的邻居节点集，记为。注意，对于不同的传输速率，对应的有效传输范围不同，所以对于节点有不同的邻居节点集，且同一链路上的可能不同。我们将集合定义为候选转发节点集，如图1所示，它是的子集，包括所有被一个特定的选择策略选择出来的节点。是一个有序集，元素的次序即它们在转发接收到的数据包时的优先级。

机会路由中，发送节点向它的候选转发节点集广播数据包，按照中继优先级，其中的一个节点继续转发数据包——如果集合中的第一个节点成功接收到了数据包，它就向目的节点转发数据包，而其他所有节点都抑制重复传输；否则，如果集合中的第二个节点准确接收到了数据包，它将转发数据包；否则是第三个节点继续中继；否则第四个hellip;hellip;等等。候选转发节点只有比它优先级高的所有节点都没有成功传输的情况下，才会转发数据包^[1]。当没有候选转发节点成功接收到数据包时，发送节点在允许重传的情况下将会重传数据包，直到重传次数到达上线，发送节点将丢掉数据包。这样的转发将重复进行，直到数据包被传送到目的地。

图1 节点正在向一个遥远的目的节点传输数据包，

在某传输速率下，节点的候选转发节点集为

三、计算机会路由的吞吐量界限

我们想要解决的第一个基本问题是最大化机会路由的端对端吞吐量。任何高于吞吐量的负载都是不被支持的，甚至会由于过度的媒介竞争而恶化性能。在实时服务的访问控制中，吞吐量的容量可以用来防止过度负载，也可以用来估计不同变量的机会路由的性能。除此之外，知道机会路由吞吐量可能会提出新颖有效的候选选择和优化机制。

在这部分，我们介绍了计算给定网络和机会路由策略下两个端节点之间吞吐量界限的方法（即，给定各节点的转发候选序列、节点中继优先级和各节点的传输速率）。我们首先引入两个概念，传输冲突图和可并发传输集，来表示多跳无线网络中无线传输的干扰约束。接下来，我们提出了计算机会路由可支持的最优吞吐量界限的方法。在本文中，我们假设没有功率控制机制，在链路调度之前已知链路质量^[2]（PRR）。

A.传输干扰和冲突

无线干扰是影响吞吐量的关键因素。现有的无线干扰模型通常分为两类：协议模型和物理模型[13]。在协议模型中，在满足以下条件时认为传输成功：1）接收者在传输者的有效传输范围内；2）传输时，接收者的载波侦听范围内没有节点。这种协议模型只要求接收端无干扰。为了模拟类似于802.11的双向通信，我们可以将协议模型扩展为，同时要求传输端无干扰。在物理模型中，对于一次成功的传输来说，接收者接收的来自所有传输的总功率加上噪声必须小于阈值，才能满足SNR要求。在本文中，我们用“可用”来描述可成功传输的链路。当两个（或更多）的链路不同时可用时，它们产生“冲突”。

链路冲突图是模拟干扰的一个简便工具[10]，[14]。如图3.b所示，在链路冲突图中，每一个顶点在原始连通图中对应一条链路。如果两条链路因干扰而不能同时活跃（例如有“冲突”），则对应的两个顶点间有一条边。然而，由于机会路由的特性，对于一次传输，吞吐量可能存在于多条链路中，所以上述基于链路的冲突图不能直接应用在机会路由网络的容量问题中。吞吐量取决于多条链路，这使随后的最大化流的优化问题更加困难。因此，在本文中，我们提出了一个构造冲突图的新方法，以简化对机会路由吞吐量界限的估算。不同于构造链路冲突图，我们通过传输者（或节点）来研究冲突关系。如图3.c所示，在节点冲突图中，每条边对应原始连通图中的一个节点，每条边都与一个链路集有关，例如节点挑选的转发候选节点的链路。如果两节点因一条或多条不可用链路（如第三部分B中定义）而产生冲突，不能同时传输，则两顶点之间有一条边。

B.并发传输集

我们为机会路由定义了并发传输集CTS。这些定义捕捉了无线传输中干扰的影响和机会路由的机会性特点，是我们计算端对端吞吐量的基础。

1）保守CTS：根据特定的机会路由则略，当一个节点传输时，广播数据包给转发候选节点集中的所有节点。将传输者和它的转发候选节点间的所有链路记为和传输者相联的链路。定义一个传输节点集，当集合里所有节点同时传输时，所有与它们相联的链路都可用，则称为保守CTS（CCTS）。如果在CCTS中加入任何一个节点都不再是CCTS，则称此CCTS为最大CCTS。

保守CTS实际上要求所有可能的接收者在传输中都是无干扰的。这对于某些协议[5]是可行的，在某些协议中，RTS/CTS机制是用来确定传输者/接收者的范围或确认一次成功的接收的。但是这是一个比所需要的更严格的要求，只能给我们一个更低的端对端容量的下界。为了计算出最大的端对端吞吐量，我们定义了下面的贪心CTS。

2）贪心CTS：为了最大化吞吐量，我们允许两个或更多传输者同时传输，甚至在与它们相联的一些链路不可用的情况下。这里的思想是，只要传输者可以给下一跳的候选节点中的一个传输，就允许传输。因此我们定义了贪心CTS，对一个传输者集，至少一条与它们相联的链路可用时，集合中的所有节点都可以同时传输。如果在GCTS中加入任何一个节点都不再是GCTS，则此GCTS称为最大GCTS。

C.有效转发率

在找到CTS后，我们需要确定CTS中每条与节点相联的链路的容量。根据特定的机会路由策略，我们引入了与传输者相联的每条链路的有效转发率的概念。假设节点n_i的候选转发集F_i=lt;n_i1,n_i2hellip;n_irgt;，转发优先级为n_i1gt;n_i2gt;hellip;gt;n_ir。对某一CTS中的n_i：记链路l_iiq的指示函数为Psi;_q，Psi;_q=1表示链路l_iiq可用，Psi;_q=0表示链路l_iiq不可用。那么链路l_iiq的有效转发率定义为（1）式：

其中，R_i是传输节点i的发送速率，p_ii0=0。

在保守CTS中，所有的接收都是无干扰的。因此，在每个CCTS中，与传输者相联的各链路都是可用的，即Psi;=1；各链路的有效转发率都不是零。对某一链路来说，在不同的CCTS中的有效转发率保持不变。有效转发率指示着，根据转发优先级，只有当高优先级的候选中继没有正确接收到数据包时，成功接收到包的低优先级的可用中继才有转发包的机会。注意，这个概念涵盖了传统路由中的单播有效率，即当只有一个候选节点时，有效转发率降低成为单播有效率。

对于贪心模式，一些与传输者相联的链路可能会变得不可用，从而有效转发率为零。此外，当链路处于不同的GCTS中时，有效转发率可能会不同。为了表示可能的差异，我们用来表示链路处于第alpha;个GCTS时的有效

资料编号：[3619]