基于IEEE 802.16技术的WiMAX WMN(wireless mesh networks)^[1]能够为非视距范围内的固定终端、移动终端提供高效无线连接,与其他接入技术相比,WiMAX WMN具有投资少、传输速率高、建设快、组网灵活、布置方便等一系列优点,受到了业界的积极响应和支持.

IEEE 802.16标准中定义了三种时隙分配机制以满足网络的QoS需求^[1]:协调分布式调度、非协调分布式调度以及集中式调度.但现有802.16规范中仅定义了时隙分配过程中的信令交互格式,并没有规定具体的调度和带宽分配方法,而将这些问题留给协议实现厂商来解决.由于在调制方式固定的情况下,最短的传输帧长对应最大的网络吞吐量,因此,应尽可能使互不干扰的链路在相同时隙中进行传输,通过链路的并行传输来提高时隙复用率,减少网络调度帧的长度.

由于无线网络的干扰可以用干扰图^[2]来描述,文献^{[3, 4]}中提出了若干基于图着色的启发式求解方法以寻找无冲突的链路调度机制,但由于WMN的无线多跳特性,各链路除了需要传输自身的流量外,还需要对沿途子节点的流量进行转发,这会导致各链路具有不同的时隙需求.由于WMN节点具有中继转发特性,文献^{[5, 6]}将链路调度与路由进行协同考虑,提出了面向跨层优化的链路调度机制,但这些算法均致力于减少路径干扰,并没有考虑链路选择顺序对网络性能的影响,因而时隙复用率较低.基于此,文献^{[7, 8]}着重对链路单次调度问题进行研究,并分别提出了最大加权干扰度优先及两跳邻居优先的调度次序选择策略,但上述算法要求任意链路在每次调度中只能传输一次,这会导致时隙复用率的下降.针对链路多次传输情况,文献^[9]提出了近BS节点优先、远BS节点优先的链路排序原则.其他链路排序策略还包括上下行链路统一调度的跳数最少优先和跳数最多优先链路排序机制^[10]等.

本文从全局角度对全网的最优调度顺序进行求解,提出基于干扰度排序的链路调度优化机制;另外,通过设计基于节点与链路分解的扩展图模型,本文算法能有效满足WMN的中继特性需求,从而构建了链路单次与多次传输的统一调度框架.

假设网络中含有1个BS节点和n个SS节点,全网建模为有向通信图G=(V,E),V={v₁,v₂,…,v_n,v_n+1}表示WMN中节点集合,v_n+1为BS节点,v₁,…,v_n为SS节点.有向链路集E= {e₁,e₂,…,e_m}表示网络中有向边集合,e(l_ij)∈E,当且仅当d(i,j)≤R_c,i为发送方,j为接收方,R_c为通信半径,d(i,j)表示节点i和j之间的欧氏距离.认为网络中各节点具有相同的发射功率,即各节点具有相同的通信半径R_c.

考虑到WMN的多跳中继特性,结合节点的初始带宽请求G={g₁,…,g_n}及路由树G′(V,E′),E′⊆E,可求得SS节点i的请求带宽ř_i为

同理,可求G=(V,E)中链路e_j的带宽需求ř_ej为

进一步,由带宽需求与OFDM码元及传输速率的对应关系,可求得在TDMA机制下,各个链路在每帧中的时隙需求r_ej为

为了保证数据的可靠传输,任意两条相互干扰的链路需在不同的时隙中传输.以协议干扰模型来描述链路的干扰情况,定义干扰半径以R_I表示(R_I通常是R_c的Q倍,Q≥1).为了消除网络干扰,在链路(v_i,v_j)通信时,需要确保区域D(v_i,R_I)∪D(v_j,R_I)中所有节点都处于静止状态,D(v_i,RI)表示以节点v_i为圆心,半径为R_I的圆.

引入冲突图G_c(V_c,E_c)描述G(V,E)中链路干扰情况,G(V,E)中的通信链路E对应冲突图G_c(V_c,E_c)中的顶点集V_c,

定义数据传输帧中时隙编号为M=[0,1,…,T-1]^T,链路E与时隙M的映射关系可以使用矩阵I:E×M→{0,1}表示.

无干扰传输需要保证干扰链路不能在同一时隙传输,即

本文主要关注在给定各链路传输需求的条件下,如何使最终分配的各链路时隙数尽可能接近带宽请求值,并通过时隙复用获得最短的调度周期.

给定WMN的通信图G(V,E)及链路传输需求向量R=[r_e1,r_e2,…,r_em]^T,吞吐量最优的链路调度问题即为寻找一种最短时隙数的映射矩阵I,在满足无干扰传输条件下,满足链路传输需求R,并获得最大的网络吞吐量.不失一般性,该问题可以描述为

其中,优化目标希望该调度结果具有最大的网络吞吐量,即数据帧中时隙数量最少;保证分配给链路的时隙数与其请求R相等; , ∀e(i)∈E保证为各链路最终分配的时隙小于调度周期,同时还需要满足无干扰传输条件.

由于WMN的多跳中继特性,当中间节点存在带宽需求时,全网各链路将具有不同的时隙需求.为了寻求有效的链路调度机制,首先对单位时隙需求的链路调度优化算法进行求解;引入扩展图模型,建立了链路单次传输与多次传输的统一求解框架,使得单位时隙需求的调度算法能满足传输次数与时长不定的环境.

给定有向连通图G(V,E),根据如下原理构造扩展图G_e(V_e,E_e):对G(V,E)中的任意节点u∈V,时隙需求w_u≥0,则在G_e(V_e,E_e)中,u将分解为w_u个节点,命名为u¹,...,u^w_u,且分解后的节点uⁱ具有与原节点u相同的位置;对G(V,E)中的任意链路(u,v)∈E,如果节点u是节点v的第m个子节点,则经过分解G(V,E)中的节点u和节点v,E_e将包含w_u条相互干扰的链路,分别为

G_e(V_e,E_e)中的任意链路最多只能属于一条路径,从而使得利用扩展图G_e(V_e,E_e)进行路由选择时,每个节点都可以使用父节点分解的子节点作为单独的转发节点,且各节点、各链路的时隙需求均为1.另外,对原链路(u,v)的带宽需求r(u,v)与分解后的各链路带宽需求r(uⁱ,vⁱ)还满足:

可见,虽然WMN的中继特性使得有向图G(V,E)中各节点与链路具有不同时隙需求,但经节点与链路分解后,G_e(V_e,E_e)中所有节点与链路仅具有单位时隙需求,这就为使用算法1确定G_e(V_e,E_e)中各分解链路的时隙创造条件.

考虑到经过扩展图中各链路传输需求均为1,此时对应链路调度的最简单情况,即网络中仅端节点初始时具有单位时隙需求,中间转发节点的初始时隙需求均为0.由于当前单位时隙链路调度机制并没有考虑链路调度顺序对网络性能的影响,为此,以链路干扰度作为排序准则,提出针对单位时隙需求的启发式调度算法.对任意待调度链路l_i,为其分配没有被干扰图G_c中的邻居节点所使用的最小时隙作为该链路的通信时隙,以尽可能增加时隙复用度,提高链路并行传输特性.另外,还需要判断每次新分配时隙是否大于网络周期T,如果大于网络周期T,则将T更新,以保证周期T总能满足所有链路带宽需求.基于扩展图的调度算法伪代码如算法1所示.
算法 1 Scheduling algorithm based on expanded graph model
输入:link list O={l₁,...,l_m} and communication graph G(V,E)
输出:link-time vector A and scheduling period T

1) using the routing algorithm on G(V,E) and initial slot w′ _i to calculate final slot demand w_i;

2) build the expanded graph G_e(V_e,E_e)based on graph G and slot demand w_i;

3) construct a conflict graph G_c(V_c,E_c) based on G_e(V_e,E_e) using the interference model;

4) while G_c is not empty do

5) find the vertex with the smallest degree in G_c;

6) remove this vertex from G_c and all its incident edges;

7) let e_k denote the(m-k+1)th vertex removed;

8) let T=1;

9) for each link e(u,v)∈E_e

10) let assign=false;

11) find e∈E_e satisfies d_e∋e_a^k,d_e ⊂ E_A;

12) for slot t=1:T

13) if e(u,v) do not conflict its neighbors in G_c in slot t

14)  assign e(u,v)with slot t;

15)   assign=true;

16)    break;

17) if assign== false

18) T=T+1;

19) assign e(u,t) slot T;

20) assign e(u,v) all the slots used by

算法执行过程中,首先根据节点初始需求及路由树构建扩展图G_e(V_e,E_e),再使用启发式机制确定扩展图中各链路的时隙分配,最终再通过扩展图G_e(V_e,E_e)和G(V,E)的对应关系,确定G(V,E)中各链路的时隙分配情况.

为了验证算法的有效性,首先考察链式拓扑情况下的链路调度算法性能情况.9个节点以链式方式部署于区域中,BS节点位于链的端点.每个节点的通信半径为R_c=100m,各节点初始各链路需求 R =[1,2,3,1,2,3,2,2]进行对比.

图 1中矩形区域中的颜色表示数据所属的信源,同颜色矩形的不同线条(直线、虚线或者星号线)则表示同一信源的不同时隙.图 1为Nearest First获得的时隙分配结果,图 2为采用本文算法 后获得的时隙分配结果.可见本文提出的方法通过细化各链路的传输过程与优化调度顺序,能有效减少调度周期,提高网络的吞吐量.

图 1(Figure 1)

Fig. 1

图1 链式拓扑结构下Nearest First调度算法结果 Fig. 1 Scheduling results of the Nearest First algorithm in chain topology

图 2(Figure 2)

Fig. 2

图2 链式拓扑结构下本文算法调度结果 Fig. 2 Scheduling results of our algorithm in chain topology

考察网格部署模型中算法的性能情况.36个Mesh节点以网格方式均匀分布于500m×500m区域中,BS节点位于全网中心.节点通信半径R_c=100m,R_I=R_c,使用Dijkstra算法查找跳数最少的路径作为各节点和BS节点的通信路径.初始时,路由树中链路长度m=36.

图 3展示了在不同网络信源数及不同资源申请数量条件下,算法性能的对比情况.当网络信源数目较少时,由于链路间相互干扰机会较少,因此,利用算法所具有的良好的时隙复用特性,在需求较少的情况下,算法性能较为接近.但随着网络信源数目增加,链路时隙需求及网络整体干扰度增强,需要更多的时隙来满足全网链路的调度需求.

图 3(Figure 3)

Fig. 3

图3 不同网络负载条件下算法性能比较 Fig. 3 Performance comparison with different network traffic load

进一步考察在此拓扑环境中,基于扩展图的链路调度算法与非拆分链路调度算法^[7]的性能对比情况.设网络信源节点数为20,各节点时隙申请为rand(3),rand(5)及rand(9)时的性能对比如表 1所示.

表1

Table 1

表1(Table 1)

表1 基于扩展图的拆分调度与非拆分调度的性能对比 Table 1 Scheduling performance comparison of the expanded graph with and without link division 申请时隙 调度算法 调度周期T rand(3) 拆分调度 20 非拆分调度 25 rand(5) 拆分调度 42 非拆分调度 62 rand(9) 拆分调度 76 非拆分调度 103

表1 基于扩展图的拆分调度与非拆分调度的性能对比 Table 1 Scheduling performance comparison of the expanded graph with and without link division

从表 1中可见,基于扩展图的链路调度算法能够获得更短的网络调度周期.这种性能提升的主要原因在于节点完全分解进一步细化了各链路、各节点的传输情况,提高了链路的并行传输性,最终促使网络性能的提升.

本文研究了WiMax WMN的链路调度问题,对吞吐量最优的无干扰链路调度问题进行建模分析,提出了针对单时隙需求的最优调度算法,设计了节点与链路分解的扩展图模型.通过细化网络传输过程,建立了链路单次传输与多次传输的统一调度框架.仿真实验表明，本文算法能够有效减少网络调度周期,提高网络吞吐量,具有优异的性能.