Fig. 1 The 2-user wireless system.
Channel-aware scheduling is called opportunistic scheduling. We assume the network controller can observe S ( t ) \mathcal{S}(t) S(t) at the beginning of each slot t t t before making a transmission decision. Queueing dynamics are given by
Q k ( t + 1 ) = max [ Q k ( t ) − b ^ k ( p ( t ) , S ( t ) , 0 ] + a k ( t ) ∀ k ∈ { 1 , 2 , ⋯ } Q_k(t+1)=\max[Q_k(t)-\hat{b}_k(p(t),\mathcal{S}(t),0]+a_k(t)\quad \forall k\in\{1,2,\cdots\} Qk(t+1)=max[Qk(t)−b^k(p(t),S(t),0]+ak(t)∀k∈{1,2,⋯}
Denote p ˉ k \bar{p}_k pˉk as the time average power expenditure.
The objective is to minimize the time average power expenditure, and the problem is subject to queue stability, which is formulated as
The designed algorithm based on our theory is utilized to make decisions
p
(
t
)
∈
P
\bm{p}(t)\in \mathcal{P}
p(t)∈P every slot
t
t
t, without requiring a priori knowledge of the probabilities associated with the arrival and channel processes
a
(
t
)
\bm{a}(t)
a(t) and
S
(
t
)
\bm{S}(t)
S(t). Decouple? Furthermore,
O
(
V
)
O(V)
O(V) is a tradeoff for the average queue backlog and delay.
We assume that the arrival process a ( t ) \bm{a}(t) a(t) can be controlled by a flow control mechanism. Thus the decision vectors are the power allocation vector p ( t ) \bm{p}(t) p(t) and the data admission vector a ( t ) \bm{a}(t) a(t). Denote a ˉ k \bar{a}_k aˉkas the time average admission rate (in bits/slot) of user k k k.
A problem that aims to maximize a weighted sum of throughput subject to average power constraints is formulated as
SUBJECT TO TIME AVERAGE POWER CONSTRAINTS
The objective is to maximize a concave function of throughput, i.e., utility function (效用函数). 效用函数是严格凹函数并且非递减函数比如 g ( a ) = log ( 1 + a ) g(a)=\log(1+a) g(a)=log(1+a)。这意味着随着 a a a 的增大，效用函数值增加的速度是放缓的，即受到了一个diminsbing returns。在本问题中，当 a ˉ 1 < a ˉ 2 \bar{a}_1 < \bar{a}_2 aˉ1<aˉ2 时，增大 a ˉ 1 \bar{a}_1 aˉ1 比 增大 a ˉ 2 \bar{a}_2 aˉ2 使目标函数值上升更多。效用函数的构造涉及比例公平。
上述举例的问题仅考虑了在平均时间约束下优化平均时间，现在我们提出更一般的随机优化问题。考虑一个随机网络及多个个离散的时隙，网络能被描述为队列积压集合，即
Q
(
t
)
=
{
Q
1
(
t
)
,
⋯
,
Q
K
(
t
)
}
\mathcal{Q}(t)=\{Q_1(t),\cdots,Q_K(t)\}
Q(t)={Q1(t),⋯,QK(t)}。
K
=
0
K=0
K=0 表示系统无队列。首先定义三个属性向量
其中，
ω
(
t
)
\omega(t)
ω(t) 是在时隙
t
t
t 被观测到的随机事件（例如新数据包的到达或信道状态），
α
(
t
)
\alpha(t)
α(t) 是动作。令
x
ˉ
m
,
y
ˉ
l
,
e
ˉ
j
\bar{x}_m, \bar{y}_l, \bar{e}_j
xˉm,yˉl,eˉj 分别代表
x
m
(
t
)
,
y
l
(
t
)
,
e
j
(
t
)
x_m(t),y_l(t),e_j(t)
xm(t),yl(t),ej(t) 的平均时间。
问题1：
问题2（其中f（x），g（x）是凸函数）：
上述两个问题都属于随机规划。即使不存在队列时，也可以构造虚拟队列来确保满足时间平均约束。低效率的控制策略将会导致某一队列中较大的积压，这些积压可以作为下一控制策略的充分的统计数据，从而使我们不需要事先知道随机网络中的事件发生的概率。
首先构造虚拟队列，然后定义Lyapunov函数作为网络拥挤程度的度量标量，函数值越小表明所有队列都不拥挤，越大则表明至少存在一个队列拥挤。定义差值delta代表不同时隙Lyapunov函数值的变化量。如果控制策略是基于在每个时隙t最小化delta优化的，那么队列积压会持续倾向于较低的拥挤水平，从而使整个网络维持稳定。最小化delta也称为最小化 Lyapunov drift。然而，目前为止我们仅考虑利用虚拟队列和李雅普诺夫漂移来确保满足平均时间约束，最小化目标函数并没有联合考虑。因此，我们需要将目标函数映射到合适的惩罚函数，最小化 drift-plus-penalty：
Δ ( t ) + V × p e n a l t y ( t ) \varDelta (t)+V\times penalty(t) Δ(t)+V×penalty(t)
其中， V V V 是非负的控制因子。通过调整V的大小来获得积压减小和惩罚最小化的折中。该方法仅用知道当前网络状态而不需要去获取未来随机事件发生的概率。
与其他工作相比，该方法的优势是明确的收敛分析和性能界限使performance-delay 得到权衡。
之前考虑的惩罚项仅包含时隙t的动作和随机事件（事件仅与当前决策有关，与过去无关），需要指出随机队列积压未包含在惩罚项中。现在我们考虑一个改进的惩罚项结构，将z（t）纳入惩罚项中，z（t）是一个可控的马尔科夫链（可能与队列积压相关），其状态转移概率取决于动作。运用李雅普诺夫优化理论时并不受极大收敛时间，高度复杂性，大型网络的不准确估计等“维数诅咒”的影响。
时延和动态规划
动态规划和马尔科夫决策过程结构都被认为是单队列的能量和时延优化问题。In 【82-86】单队列的问题在一些已知的工作中考虑了严格的期限和对未来事件的先知。在【90】中，作者考虑了在时延限制的约束下最小化能量问题for 多队列无线系统，其中，当信道是静态时，问题能被转化为最短路问题；当信道动态变化但是功率函数是线性函数时，问题被转化为带有一个阈值的多维动态规划的简单结构；当信道状态变化更复杂时，需要用到启发式算法来解决该问题。
协同网络的时延优化算法
顺序优化的时延调度和队列组合
网络繁忙和衰减指数
有一项工作涉及到 "重载 "情况下的渐进延迟优化，在这种情况下，输入率被推到非常接近容量区域的边界。由于状态空间崩溃的现象，延迟在这种重载制度下通常更容易理解。当然，如果输入率被推向容量边界，延迟就会趋近于无限大，我们需要设计一种算法使渐进增长系数最小。
移动网络中能力和时延的权衡
通过简单的逐项相消可以证明该定律。这是李雅普诺夫漂移论证的主要思想：通过控制函数在每一步的变化可以控制函数的最终值。
外层是对Y求期望，内层是对给定Y的X的条件期望。
考虑与环境的互动，环境以某一概率分布生成一个随机变量w，我们观察到w后从动作集A中选择一个控制动作a。邓毅成本函数从c（w，a），我们目标是使成本函数的期望值最小化。假设对于给定的结果w，A中总存在一个a_min使成本最小，那么我们根据该思路，对于每次观测到的w执行相应的a_min，就可以使成本总期望最小。
X为有限凸集，f为凸函数。
