CN104684045B - 一种无线网状网中的联合协作路由与信道分配方法 - Google Patents

Abstract

本发明公开了一种无线网状网中的联合协作路由与信道分配方法，包括以下步骤：根据网络结点的广播信息，获取整个网络的原始拓扑结构和链路状态信息；根据协作模块虚拟化的方法构建基于虚拟结点和虚拟链路的新的网络拓扑结构。新的网络拓扑图建立多并发流下无线网状网中各条业务流满意度之和的目标函数模型，初步确定业务流的协作传输路径和传输路径上链路的工作信道；对结果进行局部的信道调整，使得所有的结点分配到的信道数量都不超过其配置的射频数量，并为业务流确定最终的协作路由和信道分配方案。本发明的方法在充分利用协作通信带来的空间分集增益的同时，能有效降低同信道干扰，达到最大化网路整体吞吐量的目的。

Description

一种无线网状网中的联合协作路由与信道分配方法

技术领域

本发明涉及无线网络中协作路由和信道分配技术，特别是指在多并发流无线网状网中的联合协作路由和信道分配方法。

背景技术

无线网状网是一种动态自组织的多跳网络，它能够在城市环境中为用户提供廉价的高带宽网络服务。但由于密集的楼宇和复杂的建筑结构使得无线网状网面临严重的多径衰减效应，极大影响了无线信号的传输质量。协作通信技术作为一种克服信道衰落，提高无线传输容量和降低传输能耗的有效方法，近年来得到越来越多地关注，将其与无线网状网融合成为未来无线网络发展的一种趋势。

协作通信技术通过将多用户环境下的单天线用户组成虚拟的MIMO系统来取得空间分集增益。协作路由则是将物理层协作通信技术和网络层路由选择结合起来的跨层路由方案，它通过选择合适的协作中继结点参与路由中的某一跳或某几跳传输，提高无线传输的容量或降低传输的能耗，为无线用户提供更好的网络服务。

举例说明协作通信的基本思想：协作通信的本质是发射端将同一信息的多个复本通过不同的路径发送给接收端来获取分集增益。图1显示了经典的三点协作传输模型，S，R和D分别表示发送结点，中继协作结点和接收结点。S在向D发送信号过程中，R会监听到同样的信号，然后R也会将发送给D，最终，D会将来自S和R的两路信号按照最大比率组合的方式合成一束更强的信号。因此，协作通信在发送功率固定的情况下，可以带来更高的链路传输速率。协作通信有多种实现方式，其中，相比其它协作通信实现方式，AF-RAKE可以在提升链路传输容量同时最小化同信道干扰，因此，本发明也采用基于AF-RAKE的协作传输模式。此外，由于协作中继结点的参与，协作通信除了能提高无线传输速率以外，还会增加传输的干扰范围。在直接传输中，只有源结点S和目的结点D参与传输，整个传输的干扰范围是S和D的干扰范围的并集，如图2(a)。而在协作传输中，整个传输的干扰范围是S，R和D三个结点的干扰范围的并集，如图2(b)。因此，在相同的网络环境中，相较于直接传输，协作传输的干扰范围会有所扩大。

相对于传统路由，协作路由在增强无线网络性能方面具有诸多优势，但是，无线传输的同信道干扰引起的传输冲突会造成数据的丢失和重传，严重制约了协作路由对多跳无线网状网吞吐量的提高。而多射频多信道技术可以降低同信道干扰，将其与协作通信技术相结合，可以在充分利用协作通信带来的分集增益同时，降低无线传输的同信道干扰，提升网络整体吞吐量。此外，随着无线网卡成本的降低和对高网络带宽的需求，配置多射频路由结点的无线网状网开始被大量部署，因此，研究多射频多信道下的协作路由对于提高无线网状网中的吞吐量具有重要理论意义和应用价值。

在多射频无线网状网中，协作路由和信道分配策略的选择决定了网络的性能。现有的协作路由方法没有考虑结点射频和信道数量限制下的信道分配问题，无法充分利用多射频多信道的优势，而已有的信道分配方法主要是针对直接传输网络，没有考虑协作传输的特性，无法直接扩展到协作传输网络。因此，如何在两者之中取得一个平衡是将协作通信技术应用到无线网状网中需要解决的重要问题。

发明内容

本发明所要解决的技术问题是，针对现有技术不足，提供一种无线网状网中的联合协作路由与信道分配方法，通过为每条业务流确定最优的协作路由和信道分配方案来最大化网络整体吞吐量。

为解决上述技术问题，本发明所采用的技术方案是：一种无线网状网中的联合协作路由与信道分配方法，包括以下步骤：

1)根据网络结点的广播信息，获取整个网络的原始拓扑结构和链路状态信息；

2)根据协作模块虚拟化的方法构建基于虚拟结点和虚拟链路的新的网络拓扑结构。

3)新的网络拓扑图建立多并发流下无线网状网中各条业务流满意度之和的目标函数模型，初步确定业务流的协作传输路径和传输路径上链路的工作信道；

4)对步骤3)的结果进行局部的信道调整，使得所有的结点分配到的信道数量都不超过其配置的射频数量，并为业务流确定最终的协作路由和信道分配方案。

本发明具体实现过程如下：

1)用G(V,E)表示一个无线网状网拓扑图，V表示结点集合，E表示链路集合；

2)利用基于协作通信模块虚拟化的方法，将每个协作通信模块可能发生的协作传输链路加入到网络拓扑图中，为G中的每个协作通信模块增加虚拟结点和虚拟链路，构建新的网络拓扑图G’；

3)基于新的网络拓扑图G’建立多并发流下无线网状网中各条业务流满意度之和的目标函数模型：

st.

其中，s.t表示约束条件；ch(u,v,k,c)表示链路(u,v)在信道c上业务流k的速率，s(k)表示业务流k的源结点，d(k)表示业务流k的目的结点，r(k)表示业务流k最终的转发速率,C(u,v)表示链路(u,v)的传输速率：C(t,w)表示链路(t,w)的传输速率；CH表示正交信道集合；F表示业务流集合；I(u)表示结点配置的射频数量；IR(u,v)表示链路(u,v)干扰范围内的链路集合；V^s表示虚拟结点集合；E^s表示虚拟链路集合；

4)对上述目标函数模型求最优解，如果最优解中ch(u,v,k,c)>0，就代表链路(u,v)使用信道c为业务流k的数据，通过ch(u,v,k,c)的解得到每条业务流的传输链路以及使用的正交信道，从而确定业务流的协作路由和信道分配初步方案；

5)对于初步方案中分配到的信道数量超过其配置的射频数量的结点进行局部信道调整，具体过程为：

(a)选择出境速率最大并且信道数量超过射频数量的结点u；

(b)从u的信道列表中，选择两个信道C₁，C₂进行合并：用表示Ec(u)中的链路在信道C上的使用率之和，即：

C₁，C₂就是值最小的两个信道，将相关链路的信道从C₁调整成C₂；

(c)如果网络中还有结点的信道数量超过射频数量，重复步骤(a)和步骤(b)，直至所有结点的信道数量不超过射频数量。

与现有技术相比，本发明所具有的有益效果为：本发明的方法同时利用多射频技术和协作通信技术，在充分利用协作通信带来的空间分集增益的同时，能有效降低同信道干扰，达到最大化网路整体吞吐量的目的。本方法具有较强的拓扑无关性和稳定性；与传统的路由选择和信道分配方法相比，在不同并发流数量下，本发明的方法可以提升网络整体吞吐量55％到120％，在不同射频数量下，可以提升网络整体吞吐量20％到190％，在不同信道数量下，可以提升网络整体吞吐量25％到280％，在不同结点密度下，可以提升网络整体吞吐量10％到210％。

附图说明

图1是经典的三点协作传输模式；

图2(a)是无线传输直接传输的干扰范围；图2(b)无线传输协作传输的干扰范围；

图3是多并发流下的协作传输与信道分配；

图4(a)是原始的协作通信模块；图4(b)是增加了虚拟结点和虚拟链路后的协作通信模块；

图5(a)是初步的信道分配结果；图5(b)是调整后的信道分配结果；

图6是本发明中不同数量并发流下的吞吐量；

图7是本发明中不同射频数量下的网络吞吐量；

图8是本发明中不同信道数量下的网络吞吐量；

图9是本发明中不同结点密度下的吞吐量。

具体实施方式

协作通信在带来空间分集增益的同时会引入额外的同信道干扰，而多射频多信道技术可以有效降低同信道干扰，同时利用两者的技术优势，可以为业务流提供更加优质的网络服务。如图3，网络中每个结点配置了2个射频，可以使用4个独立的正交信道，总共有3条业务流。带箭头的线段组成的路径表示业务流使用的转发路径，线段上的数字表示为链路分配的正交信道。从图中可以看出，每条业务流使用了协作路由或多射频多信道技术，其中流2和流3同时使用了两种技术。这样就可以在利用协作通信的空间分集增益的优势同时，有效减少无线传输干扰，提升网络整体吞吐量。

但实际上，在多射频多信道无线网状网中同时求解协作路由和信道分配的最优策略非常复杂。已有的研究成果表明，在不考虑协作通信的情况下，多射频多信道网络中的联合信道分配和路由选择问题已是一个NP难问题；而在不考虑多信道的情况下，联合中继结点分配的协作路由选择问题同样是一个NP难问题，因此，将协作路由选择和信道分配联合起来一起解决是一个极其复杂的问题。针对上述问题，本文提出了一种多项式时间内的联合协作路由选择和信道分配算法，通过为每条业务流确定最优的协作路由和信道分配方案来最大化网络吞吐量。

用G(V,E)表示一个无线网状网拓扑图，V表示结点集合，E表示链路集合；用CH表示正交信道集合；用F表示业务流集合；用I(u)表示结点u∈V配置的射频数量。我们将首先通过协作通信模块虚拟化的表示方法，将联合协作路由选择和信道分配问题简化为联合直接路由和信道分配问题，然后，给出相关的资源约束和路由约束条件，建立问题的优化模型，并对模型的最优解给出局部的调整，最终确立业务流的协作路由选择和信道分配方案。

1.协作通信模块的虚拟化表示。

在协作路由中，每个通信模块是由三个相互连通的结点组成，每条业务流会使用一个或多个协作通信模块来传输数据。为了降低算法复杂度，将协作路由和信道分配问题简化为传统路由和信道分配问题，本方法提出了一种新的协作通信模块的虚拟化表示方法。

一个协作通信模块在路由过程中可能发生的协作传输最多有三种。如图4(a)，A，B，C三个结点可以组成一个协作通信模块，可能发生的协作传输有(A,B)->C,(A,C)->B以及(B,C)->A，为了将这些可能发生数据传输的链路清晰地表示出来，我们为其增加(A,B)，(A,C)，(B,C)三个虚拟结点，(A,B)->C，(A,C)->B，(B,C)->A三条协作链路，以及A->(A,B)，B->(A,B)，B->(B,C)，C->(B,C)，A->(A,C)，C->(A,C)六条超级链路，如图4(b)。之所以称其它六条边为超级链路，是因为在协作传输中，这些链路的发送端和接收端可以看作是在同一时刻收到信号，它们的MAC层传输速率趋向于无穷大。在增加虚拟结点和虚拟链路后，我们就可以按照直接路由的寻路方式来选择协作路由了。为网络中的每个可能的协作通信模块增加虚拟结点和虚拟链路后，网络就变成G(V’,E’)，V'＝V∪V^s,E'＝E∪E^s，其中，V^s表示虚拟结点集合，E^s表示虚拟链路集合，联合协作路由和信道分配的问题就可以简化为联合传统路由和信道分配问题。

2.协作路由和信道分配约束条件。

a)业务流必须遵守流守衡定律。

其中,chf(u,v,k,c)表示链路(u,v)在信道c上业务流k的速率，s(k)表示业务流k的源结点，d(k)表示业务流k的目的结点，r(k)表示业务流最终的转发速率。该式表示业务流的源结点只有出境流量，目的结点只有入境流量，而在其它中间结点，入境流量必须等于出境流量。

b)链路传输速率必须满足同信道干扰限制。

由于结点配置多个射频，在每个时槽内，链路(u,v)和它干扰范围内工作在相同信道下链路最多只能有一条链路传输数据，即：

而链路可以同时活跃在多个信道上，由于射频数量的限制，链路(u,v)和它干扰范围内的链路在同一时槽内能活跃的的链路最大数量不超过结点的射频数量限制，即：

当流传输处于长期稳定状态时，链路(u,v)和它干扰范围内的链路在单个信道上的使用率之和要不超过1：

而其在所有信道上的使用率之和要小于结点射频数量I(u),即:

c)协作通信模块内的结点必须使用相同的信道传输数据：

3.优化目标函数。

假定每条业务流对带宽的需求为d(k)，用r(k)/d(k)表示业务流的满意度，为了让每条流能公平地使用网络，我们用业务流满意度之和作为目标函数：

在给出约束条件和目标函数后，联合协作路由和信道分配问题可以形式化表示如下：

st.

跟传统网络的链路状态路由一样，每个结点会向整个网络广播自己与邻居结点的连接和信道状态信息，连通信息包括邻居结点列表，向邻居结点发送数据的速率，以及从邻居结点接收信号时的信噪比。通过收集其它的结点链路状态信息，每个结点就可以获取整个网路的拓扑状态信息，并在此基础上为业务流寻找协作传输路由和为链路分配信道。第一个约束条件表示业务流必须遵守流守恒定律，即业务流的源结点只有出境流量，目的结点只有入境流量，而在其它中间结点，入境流量必须等于出境流量；第二个约束条件表示当流传输处于长期稳定状态时，链路(u,v)和它干扰范围内的链路在单个信道上的使用率之和要不超过1；第三个约束表示链路(u,v)和它干扰范围内的链路在所有信道上的使用率之和要小于结点射频数量I(u)；第四个约束条件表示协作通信模块内的结点必须使用相同的信道传输数据。具体方法是：根据(8)求得chf(u,v,k,c)的最优解，如果chf(u,v,k,c)>0，就代表链路(u,v)使用信道c为业务流k的数据。因此，通过chf(u,v,k,c)的解就可以得到每条业务流的传输链路以及使用的正交信道，从而确定业务流的协作路由和信道分配方案。

但是，每条链路的发送结点和接收结点配置的射频数量有限，为其分配的信道的数量不能超过两端结点射频数量，而(8)并没有对此进行严格约束，可能会导致有些链路被分配的信道数量超过其两端结点配置的射频数量。因此，需要对(8)确定的信道分配方案进行局部调整，使得所有链路被分配的信道数量符合射频数量的限制要求。

接下来，我们对求信道分配的局部策略进行介绍。

4.信道分配策略调整

图5(a)显示了某个网络根据(8)得到的局部信道分配结果，从图中可以看出，链路(a,v)，(u,a)和(b,v)可以使用2个信道传输数据，其它链路则使用1个信道传输数据。由于每个结点只配置了2个射频，而u，a，c，v分配了3个信道，因此，需要对它们的信道进行调整，调整的结果必须保证每个结点发出链路使用信道的总数量不超过结点配置的射频数量。

如图5(a),用Ec(u)表示从u发出的链路集合。从图中我们可以看到，u总共分配了1，2，3三个信道，而其只配置了两个射频，因此，需要对其信道进行调整。假设我们选择将Ec(u)中使用信道3的链路的信道变成2，链路(u,a)的的工作信道由1和3变为1和2，链路(u,d)的工作信道将由3变为2。这时，结点u所发出的链路已经满足射频数量约束条件。同时，为了避免由此引起其它结点违反射频数量约束条件，发生改变的链路的另一端结点所发出的链路也需要发生同样的变化，例如，链路(a,v)的工作信道将变为1和2，链路(d,v)的工作信道会变为1和2，如图5(b)，最终所有的结点分配的信道数量都满足了射频数量的约束条件。当网络结点和信道数量较多时，可能需要通过多次这样的调整才能完全满足射频数量的限制要求。为了保证虚拟结点和其组成的普通结点的信道分配保持同步，每当虚拟结点的信道发生合并时，其组成的普通结点的信道也要相应地进行类似的调整，反之亦然。

具体的调整过程如下：

a)选择出境速率最大并且信道数量超过射频数量的结点u。

b)从u的信道列表中，选择两个信道C₁，C₂进行合并。用表示Ec(u)中的链路在信道C上的使用率之和，即：

C₁，C₂就是值最小的两个信道，按照前面讲述的方式，将相关链路的信道从C₁调整成C₂。

c)如果网络中还有结点的信道数量超过射频数量，重复(a)，(b)步骤，直至所有结点的信道数量符合限制要求。

最后，根据前面描述的方法，我们确定最终的联合协作路由和信道分配算法如下：

5)根据网络结点的广播信息，获取整个网络的原始拓扑结构和链路状态信息。

6)根据协作模块虚拟化的方法构建基于虚拟结点和虚拟链路的新的网络拓扑结构。

7)在新的网络拓扑结构基础上，根据公式(8)对问题进行建模，初步确定业务流的协作传输路径和传输路径上链路的工作信道。

8)对步骤(3)的结果进行局部的信道调整，使得所有的结点分配到的信道数量都不超过其配置的射频数量，并为业务流确定最终的协作路由和信道分配方案。

性能比较：

我们的实验场景是在600m*600m的区域内均匀地分布若干无线结点，每个结点的固定发送功率都设置为0.22W，每个信道的带宽都为22MHZ，干扰距离和传输距离都为150m。为了简单起见，假定h_sd仅包括s和d之间传播增益，取值为|hsd|²＝||s-d||^-4，其中||s-d||表示s和d之间的距离，4表示路径衰减指数；结点的噪音方差都为10^-10W。

为了评估算法的性能，我们用L-JCRCA表示本发明提出的方法，并从多个角度同以下三种方法得到的吞吐量进行对比：

Uni_ETT：统一信道分配+最短期望传输时间路由。

Ran_ETT：随机信道分配+最短期望传输时间路由。

Tra_ETT：传统信道分配+最短期望传输时间路由。

1)不同数量并发流下的吞吐量比较

为了分析业务流数量对算法的影响，我们在网络中均匀分布25个结点，每个结点都配置了2个射频，每个射频可以工作3个正交信道上。图6显示了在不同数量的并发流下，网络吞吐量的变化情况。从图中可以看出，在不同数量并发流下，L-JCRCA比Uni_ETT的吞吐量要提高55％到110％，比Ran_ETT的吞吐量要提高65％到120％，比Tra_ETT的吞吐量要提高135％到190％。提高的主要原因有两个，一是L-JCRCA采用了协作通信技术，可以有效提高单条链路的传输速率，从而带来整个网路吞吐量的提升；二是L-JCRCA将路由选择和信道分配两个问题合并成一个问题去求解，同时考虑了协作通信带来的分集增益和额外同信道干扰问题，因此它可以在充分利用协作通信带来的分集增益的同时降低链路之间的同信道干扰，所以网络的吞吐量会有所提高。

2)不同射频数量下的吞吐量比较

这一部分将分析射频数量对算法性能的影响。在网络中均匀部署25个结点，每个结点配置相同数量的射频，每个射频可以使用6个正交信道，随机选择5条业务流的源结点和目的结点。图7显示了不同数量的射频下，网络总吞吐量的变化情况。从图中可以看出，L-JCRCA比Uni_ETT的吞吐量要提高20％到90％，比Ran_ETT的吞吐量要提高20％到110％，比Tra_ETT的吞吐量要提高80％到190％。提高的原因同样是因为L-JCRCA平衡了协作通信的分集增益和同信道干扰。

3)不同信道数量下的吞吐量比较

在网络中均匀部署25个结点，每个结点配置2个射频，随机选择5条业务流的源结点和目的结点。图8显示了在不同数量的可用正交信道下，网络吞吐量的变化情况。从图中可以看出，L-JCRCA比Uni_ETT的吞吐量要提高25％到115％，比Ran_ETT的吞吐量要提高25％到180％，比Tra_ETT的吞吐量要提高75％到280％。

4)不同结点密度下的吞吐量比较

图9显示了在不同网络结点密度下，网络吞吐量的变化情况。网络中的每个结点配置了2个射频，每个射频可以工作在3个正交信道上，随机选择5条业务流的源结点和目的结点。从图9中可以看出，网络吞吐量会随着结点数量的增加而逐步增加，L-JCRCA比Uni_ETT的吞吐量要提高10％到75％，比Ran_ETT的吞吐量要提高30％到95％，比Tra_ETT的吞吐量要提高35％到210％。

Claims (1)

1.一种无线网状网中的联合协作路由与信道分配方法，其特征在于，包括以下步骤：

1)根据网络结点的广播信息，获取整个网络的原始拓扑结构和链路状态信息；

2)根据协作模块虚拟化的方法构建基于虚拟结点和虚拟链路的新的网络拓扑图；

3)新的网络拓扑图建立多并发流下无线网状网中各条业务流满意度之和的目标函数模型，初步确定业务流的协作传输路径和传输路径上链路的工作信道；

4)对步骤3)的结果进行局部的信道调整，使得所有的结点分配到的信道数量都不超过其配置的射频数量，并为业务流确定最终的协作路由和信道分配方案；

该方法具体实现过程如下：

1a)用G(V,E)表示一个无线网状网拓扑图，V表示结点集合，E表示链路集合；

2a)利用基于协作通信模块虚拟化的方法，将每个协作通信模块可能发生的协作传输链路加入到网络拓扑图中，为G中的每个协作通信模块增加虚拟结点和虚拟链路，构建新的网络拓扑图G’；

3a)基于新的网络拓扑图G’建立多并发流下无线网状网中各条业务流满意度之和的目标函数模型：

s.t

其中，s.t表示约束条件；ch(u,v,k,c)表示链路(u,v)在信道c上业务流k的速率，s(k)表示业务流k的源结点，d(k)表示业务流k的目的结点，h(k)表示业务流k最终的转发速率,C(u,v)表示链路(u,v)的传输速率：C(t,w)表示链路(t,w)的传输速率；CH表示正交信道集合；F表示业务流集合；I(u)表示结点配置的射频数量；IR(u,v)表示链路(u,v)干扰范围内的链路集合；V^s表示虚拟结点集合，E^s表示虚拟链路集合；V′、E′分别为新的网络拓扑图的结点集合、链路集合，V′＝V∪V^s，E′＝E∪E^s；ch(v,t,k,c)表示链路(v,t)在信道c上业务流k的速率，ch(t,w,k,c)表示链路(t,w)在信道c上业务流k的速率，ch(t,u,k,c)表示链路(t,u)在信道c上业务流k的速率；

4a)对上述目标函数模型求最优解，如果最优解中ch(u,v,k,c)>0，就代表链路(u,v)使用信道c为业务流k的数据，通过ch(u,v,k,c)的解得到每条业务流的传输链路以及使用的正交信道，从而确定业务流的协作路由和信道分配初步方案；

5a)对于初步方案中分配到的信道数量超过其配置的射频数量的结点进行局部信道调整，具体过程为：

(a)选择出境速率最大并且信道数量超过射频数量的结点u；

(b)从u的信道列表中，选择两个信道C₁，C₂进行合并：用表示Ec(u)中的链路在信道c上的使用率之和，即：

C₁，C₂就是值最小的两个信道，将相关链路的信道从C₁调整成C₂；Ec(u)表示从u发出的链路集合；

(c)如果网络中还有结点的信道数量超过射频数量，重复步骤(a)和步骤(b)，直至所有结点的信道数量不超过射频数量。