计算机学报-2010-修改稿
线接口。后者是指两条物理链路不共享同一无线接口,但它们不能同时在两个重叠频带上成
功地传输数据。为了避免接口冲突,时间需要划分为多个时槽,共享同一无线接口的任何两
条物理链路必须被分配到不同的时槽中,也就是保证接口约束条件(无共享同一无线接口的
两条物理链路同时活跃)。注意对于只满足接口约束的链路调度来说,一些相互间存在信号
干扰的物理链路可能被分配到同一时槽中。如果在时槽t内物理链路e和ê之间存在信号干扰,
那么就说(ê,t)∈I(e,t)。对于有向网络图G(R,E),为每个时槽t定义相应的干扰图G
I
t
(E
t
,I
t
),其
中E
t
∈E为时槽t内活跃链路的集合,并且若(ê,t)∈I(e,t)或(e,t)∈I(ê,t),则干扰图G
I
t
符号
中顶点e和ê
间存在一条无向边。
关于其它形式化表示,将在下文中详述。表 1 中列出了本文中所有相关符号。
表 1 符号
定义
V
无线 Mesh 网中 Mesh 路由器(节点)的集合
K
网关节点的集合
L
无线 Mesh 路由器间有向逻辑链路的集合
L
+
终止于节点 v 的有向逻辑链路集合
(v)
L
-
起始于节点 v 的有向逻辑链路集合
(v)
R
n 个无线接口的集合(网络图中的顶点集合)
E
不同 Mesh 路由器的无线接口之间的 m 条有向物理链路集合(网络图中的有向
边集合)
Δ
无线 Mesh 网中共享同一无线接口的最大物理链路数目,即有向网络图 G(R,E)
的度数
E
时槽 t 内活跃的有向物理链路集合
t
I
时槽 t 内有向物理链路间 m(t)对干扰关系的集合
t
(ê,t)∈I(e,t)
物理链路 e 和 ê 均活跃在时槽 t 内,且如果其频带重叠,那么它们之间存在信号
干扰
λ
在所有路由器中实际流量与需求负载之比的最小值
r
源节点 v 实际得到满足的总流量
v
S
来自源节点 v 的总流量需求
v
g
in
流入节点 v 的总流量
(v)
g
out
从节点 v 流出的总流量
(v)
h
有向逻辑链路 l 上的实际被调度的总流量
l
c
有向逻辑链路 l 的容量
l
SNR
有向逻辑链路 l 的信噪比
l
T
每个调度周期的时槽总数
x
时槽 t 与一个调度周期的时间长度之比
t
c
时槽 t 内有向物理链路 e 的容量
e,t
b
时槽 t 内有向物理链路 e 的频带宽度
e,t
f
时槽 t 内有向物理链路 e 的中心频率
e,t
B
连续可用频谱的宽度
基于上述系统模型,下面将从数学上形式化可变宽度的频谱分配和链路调度的联合优化