随机网络优化：通信与队列系统中的Lyapunov控制与稳定性分析

网络优化

需积分: 50 131 浏览量更新于2024-07-18 2 收藏 1.66MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

《随机网络优化：通信与队列系统的应用》是一本由Michael J. Neely编著的专业书籍，版权属于Morgan & Claypool出版社，于2010年发行。该书主要探讨了随机网络优化这一领域，特别关注其在通信和队列系统中的实际应用。书中深入解析了网络优化的核心概念，包括queue stability（队列稳定性）的多种定义，这些定义对于理解网络系统的性能至关重要。随机排队网络模型是研究的核心内容，它模拟了现实世界中如互联网、电信网络等系统中的数据传输和处理过程，通过随机性来描绘服务请求的不确定性和资源分配的随机特性。作者通过实例分析，展示了如何运用概率论和统计方法来分析这些复杂的网络动态。本书重点介绍了一种名为“最小drift”网络控制算法的设计原理。Drift，作为Lyapunov drift理论的一部分，是一种衡量系统性能变化速度的重要指标。在随机网络优化中，最小drift策略旨在通过调整网络参数，最小化系统状态的不稳定性或性能退化，确保网络在面对不确定性时能够维持高效运行。 Lyapunov drift系统分析是书中不可或缺的一部分，它是一种强大的数学工具，用于证明网络系统在稳定状态下具有长期性能保证。通过Lyapunov函数的构建和Lyapunov不等式的应用，作者揭示了如何通过Lyapunov优化来设计有效的网络控制策略。此外，该书还提到了资金支持来源，包括DARPA IT-MANET项目、NSFC Career基金等，这反映出该领域的研究与实际应用之间的紧密联系，并强调了基础研究在推动技术发展和创新中的作用。《随机网络优化：通信与队列系统的应用》不仅涵盖了理论层面的深度剖析，还提供了实践指导，为网络工程技术人员、研究人员以及对随机网络系统感兴趣的学生提供了宝贵的参考资源。读者可以从中学习到如何在不断变化的网络环境中，利用随机优化方法提高网络的效率和稳定性。

资源详情

资源推荐

4 1. INTRODUCTION

For any given continuous and concave utility functions, our theory enables the design of

an algorithm that meets all desired constraints and provides throughput-utility within O(1/V) of

optimality, with a tradeoff in average backlog and delay that is O(V).

We emphasize that these three problems are just examples. The general theory can treat

many more types of networks. Indeed, the examples and problem set questions provided in this text

include networks with probabilistic channel errors, network coding, data compression, multi-hop

communication, and mobility. The theory is also useful for problems within operations research and

economics.

1.2 GENERAL STOCHASTIC OPTIMIZATION PROBLEMS

The three example problems considered in the previous section all involved optimizing a time

average (or a function of time averages) subject to time average constraints. Here we state the

general problems of this type. Consider a stochastic network that operates in discrete time with

unit time slots t ∈{0, 1, 2,...}. The network is described by a collection of queue backlogs, written

in vector form

Q(t) = (Q

(t),...,Q

(t)), where K is a non-negative integer. The case K = 0

corresponds to a system without queues. Every slot t, a control action is taken, and this action affects

arrivals and departures of the queues and also creates a collection of real valued attribute vectors

x(t),

y(t), e(t):

x(t) = (x

(t),...,x

(t))

y(t) = (y

(t), y

(t),...,y

(t))

e(t) = (e

(t),...,e

(t))

for some non-negative integers M, L, J (used to distinguish between equality constraints and two

types of inequality constraints).The attributes can be positive or negative,and they represent penalties

or rewards associated with the network on slot t, such as power expenditures, distortions, or packet

drops/admissions. These attributes are given by general functions:

(t) =ˆx

(α(t), ω(t)) ∀m ∈{1,...,M}

(t) =ˆy

(α(t), ω(t)) ∀l ∈{0, 1,...,L}

(t) =ˆe

(α(t), ω(t)) ∀j ∈{1,...,J}

where ω(t) is a random event observed on slot t (such as new packet arrivals or channel conditions)

and α(t) is the control action taken on slot t (such as packet admissions or transmissions).The action

α(t) is chosen within an abstract set

ω(t)

that possibly depends on ω(t).Letx

, y

, e

represent

the time average of x

(t), y

(t), e

(t) under a particular control algorithm. Our ﬁrst objective is to

对于那些给出的连续的和凹的绩效函

数，我们的理论启用了一个算法的设

计，该算法满足所有的需要的约束并

且提供了优化的在O(1/v)内的吞吐量

绩效，并且在平均积压和O(v)延迟之

间存在一个交易

流动性

多跳

一般

离散

非负

处罚

支出

失真

1.3. LYAPUNOV DRIFT AND LYAPUNOV OPTIMIZATION 5

design an algorithm that solves the following problem:

Minimize:

(1.1)

Subject to: 1)

≤ 0 for all l ∈{1,...,L} (1.2)

= 0 for all j ∈{1,...,J} (1.3)

3) α(t) ∈

ω(t)

∀t (1.4)

4) Stability of all Network Queues (1.5)

Our second objective, more general than the ﬁrst, is to optimize convex functions of time

averages.

Speciﬁcally, let f(x), g

(x),...,g

(x) be convex functions from R

to R, and let X

be a closed and convex subset of R

.Letx = (x

,...,x

) be the vector of time averages of the

(t) attributes under a given control algorithm. We desire a solution to the following problem:

Minimize:

+ f(x

) (1.6)

Subject to: 1)

+ g

(x) ≤ 0 for all l ∈{1,...,L} (1.7)

= 0 for all j ∈{1,...,J} (1.8)

x ∈ X (1.9)

4) α(t) ∈

ω(t)

∀t (1.10)

5) Stability of all Network Queues (1.11)

These problems (1.1)-(1.5) and (1.6)-(1.11) can be viewed as stochastic programs, and are

analogues of the classic linear programs and convex programs of static optimization theory. A solution

is an algorithm for choosing control actions over time in reaction to the existing network state, such

that all of the constraints are satisﬁed and the quantity to be minimized is as small as possible. These

problems have wide applications, and they are of interest even when there is no underlying queueing

network to be stabilized (so that the “Stability” constraints in (1.5) and (1.11) are removed).However,

it turns out that queueing theory plays a central role in this type of stochastic optimization. Indeed,

even if there are no underlying queues in the original problem, we can introduce virtual queues as

a strong method for ensuring that the required time average constraints are satisﬁed. Inefﬁcient

control actions incur larger backlog in certain queues. These backlogs act as “sufﬁcient statistics” on

which to base the next control decision. This enables algorithms that do not require knowledge of

the probabilities associated with the random network events ω(t).

1.3 LYAPUNOV DRIFT AND LYAPUNOV OPTIMIZATION

We solve the problems described above with a simple and elegant theory of Lyapunov drift and

Lyapunov optimization. While this theory is presented in detail in future chapters, we brieﬂy describe

it here. The ﬁrst step is to look at the constraints of the problem to be solved. For example, for the

A set X ⊆ R

is convex if the line segment formed by any two points in X is also in X . A function f(x) deﬁned over a convex

set X is a convex function if for any two points x

, x

∈ X and any two probabilities p

≥ 0 such that p

+ p

= 1,we

have f(p

+ p

) ≤ p

f(x

) + p

f(x

). A function f(x) is concave if −f(x) is convex. A function f(x) is afﬁne if it

is linear plus a constant, having the form: f(x) = c



m=1

解决方案是一种用于随着时间的

推移选择控制动作以反应现有网

络状态的算法，

子集

产生

低效

6 1. INTRODUCTION

problem (1.1)-(1.5), the constraints are (1.2)-(1.5). Then construct vir tual queues (in a way to be

speciﬁed) that help to meet the desired constraints. Next, deﬁne a function L(t) as the sum of

squares of backlog in all virtual and actual queues on slot t. This is called a Lyapunov function, and

it is a scalar measure of network congestion. Intuitively, if L(t) is “small,” then all queues are small,

and if L(t) is “large,” then at least one queue is large. Deﬁne (t) = L(t +1) − L(t), being the

difference in the Lyapunov function from one slot to the next.

If control decisions are made every

slot t to greedily minimize (t), then backlogs are consistently pushed towards a lower congestion

state, which intuitively maintains network stability (where “stability” is precisely deﬁned in the next

chapter).

Minimizing (t) every slot is called minimizing the Lyapunov drift. Chapter 3 shows this

method provides queue stability for a particular example network, and Chapter 4 shows it also

stabilizes general networks. However, at this point, the problem is only half solved: The virtual

queues and Lyapunov drift help only to ensure the desired time average constraints are met. The

objective function to be minimized has not yet been incorporated. For example, y

(t) is the objective

function for the problem (1.1)-(1.5). The objective function is mapped to an appropriate function

penalty(t). Instead of taking actions to greedily minimize (t), actions are taken every slot t to

greedily minimize the following drift-plus-penalty expression:

(t) + V × penalty(t)

where V is a non-negative control parameter that is chosen as desired. Choosing V = 0 corresponds

to the original algorithm of minimizing the drift alone. Choosing V>0 includes the weighted

penalty term in the control decision and allows a smooth tradeoff between backlog reduction and

penalty minimization. We show that the time average objective function deviates by at most O(1/V )

from optimality, with a time average queue backlog bound of O(V ).

While Lyapunov techniques have a long history in the ﬁeld of control theory, this form

of Lyapunov drift was perhaps ﬁrst used to construct stable routing and scheduling policies for

queueing networks in the pioneering works (7)(8) byTassiulas and Ephremides.These works used the

technique of minimizing (t) every slot, resulting in backpressure routing and max-weight scheduling

algorithms that stabilize the network whenever possible. The algorithms are particularly interesting

because they only require knowledge of the current network state, and they do not require knowledge

of the probabilities associated with future random events. Minimizing (t) has had wide success

for stabilizing many other types of networks, including packet switch networks (9)(10)(11), wireless

systems (7)(8)(12)(13)(14), and ad-hoc mobile networks (15). A related technique was used for

computing multi-commodity network ﬂows in (16).

We introduced the V × penalty(t) term to the drift minimization in (17)(18)(19)tosolve

problems of joint network stability and stochastic utility maximization, and we introduced the virtual

queue technique in (20)(21) to solve problems of maximizing throughput in a wireless network

The notation used in later chapters is slightly different. Simpliﬁed notation is used here to give the main ideas.

如果控制决定在每时隙内都最小化

∆

(t)，就会将队列积压推向一个较

低的拥塞状态，这样就会比较直观

地保持了队列的稳定。

拥塞

偏离

1.4. DIFFERENCES FROM OUR EARLIER TEXT 7

subject to individual average power constraints at each node. Our previous text (22) uniﬁed these

ideas for application to general problems of the type described in Section 1.2.

1.4 DIFFERENCES FROM OUR EARLIER TEXT

The theory of Lyapunov drift and Lyapunov optimization is described collectively in our previous

text (22). The current text is different from (22) in that we emphasize the general optimization

problems ﬁrst, showing how the problem (1.6)-(1.11) can be solved directly by using the solution

to the simpler problem (1.1)-(1.5). We also provide a variety of examples and problem set questions

to help the reader. These have been developed over several years for use in the stochastic network

optimization course taught by the author. This text also provides many new topics not covered in

(22), including:

• A more detailed development of queue stability theory (Chapter 2).

• Variable-V algorithms that provide exact optimality of time averages subject to a weaker form

of stability called “mean rate stability” (Section 4.7).

• Place-holder bits for delay improvement (Sections 3.2.4 and 4.8).

• Universal scheduling for non-ergodic sample paths (Section 4.9).

• Worst case delay bounds (Sections 5.6 and 7.6.1).

• Non-convex stochastic optimization (Section 5.5).

• Approximate scheduling and full throughput scheduling in interference networks via the Jiang-

Walrand theorem (Chapter 6).

• Optimization of renewal systems and Markov decision examples (Chapter 7).

• Treatment of problems with equality constraints (1.3) and abstract set constraints (1.9) (Section

5.4).

1.5 ALTERNATIVE APPROACHES

The relationship between network utility maximization,Lagrange multipliers, convex programming,

and duality theory is developed for static wireline networks in (2)(23)(24) and for wireless networks

in (25)(26)(27)(28)(29) where the goal is to converge to a static ﬂow allocation and/or resource

allocation over the network. Scheduling in wireless networks with static channels is considered

from a duality perspective in (30)(31). Primal-dual techniques for maximizing utility in a stochastic

wireless downlink are developed in (32)(33) for systems without queues. The primal-dual technique

is extended in (34)(35) to treat networks with queues and to solve problems similar to (1.6)-(1.11)

in a ﬂuid limit sense. Speciﬁcally, the work (34) shows the primal-dual technique leads to a ﬂuid

替代方法

拉格朗日乘数

二元理论

有线

原对偶

8 1. INTRODUCTION

limit with an optimal utility, and it conjectures that the utility of the actual network is close to this

ﬂuid limit when an exponential averaging parameter is scaled. It makes a statement concerning weak

limits of scaled systems. A related primal-dual algorithm is used in (36) and shown to converge to

utility-optimality as a parameter is scaled.

Our drift-plus-penalty approach can be viewed as a dual-based approach to the stochastic

problem (rather than a primal-dual approach), and it reduces to the well known dual subgradient

algorithm for linear and convex programs when applied to non-stochastic problems (see (37)(22)(17)

for discussions on this). One advantage of the drift-plus-penalty approach is the explicit convergence

analysis and performance bounds,resulting in the [O(1/V ),O(V )]performance-delay tradeoff.This

tradeoff is not shown in the alternative approaches described above.The dual approach is also robust

to non-ergodic variations and has “universal scheduling” properties, i.e., properties that hold for sys-

tems with arbitrary sample paths, as shown in Section 4.9 (see also (38)(39)(40)(41)(42)). However,

one advantage of the primal-dual approach is that it provides local optimum guarantees for problems

of minimizing f(

x) for non-convex functions f(·) (see Section 5.5 and (43)). Related dual-based ap-

proaches are used for “inﬁnitely backlogged” systems in (31)(44)(45)(46) using static optimization,

ﬂuid limits, and stochastic gradients, respectively. Related algorithms for channel-aware scheduling

in wireless downlinks with different analytical techniques are developed in (47)(48)(49).

We note that the [O(1/V),O(V )] performance-delay tradeoff achieved by the drift-plus-

penalty algorithm on general systems is not necessarily the optimal tradeoff for particular networks.

An optimal [O(1/V ), O(

√

V)] energy-delay tradeoff is shown by Berry and Gallager in (50) for a

single link with known channel statistics, and optimal performance-delay tradeoffs for multi-queue

systems are developed in (51)(52)(53) and shown to be achievable even when channel statistics are

unknown. This latter work builds on the Lyapunov optimization method, but it uses a more aggres-

sive drift steering technique. A place-holder technique for achieving near-optimal delay tradeoffs is

developed in (37) and related implementations are in (54)(55).

1.6 ON GENERAL MARKOV DECISION PROBLEMS

The penalties ˆx

(α(t), ω(t)), described in Section 1.2, depend only on the network control action

α(t) and the random event ω(t) (where ω(t) is generated by “nature” and is not inﬂuenced by

past control actions). In particular, the queue backlogs

Q(t) are not included in the penalties. A

more advanced penalty structure would be ˆx

(α(t), ω(t), z(t)), where z(t) is a controlled Markov

chain (possibly related to the queue backlog) with transition probabilities that depend on control

actions. Extensions of Lyapunov optimization for this case are developed in Chapter 7 using a

drift-plus-penalty metric deﬁned over renewal frames (56)(57)(58).

A related 2-timescale approach to learning optimal decisions in Markov decision problems is

developed in (59), and learning approaches to power-aware scheduling in single queues are developed

in (60)(61)(62)(63). Background on dynamic programming and Markov decision problems can be

found in (64)(65)(66), and approximate dynamic programming, neuro-dynamic programming, and

Q-learning theory can be found in (67)(68)(69). All of these approaches may suffer from large

猜想

指数

梯度

收敛

强大的

性能

随意的

扩展

神经

剩余210页未读，继续阅读

破网站一生黑

粉丝: 0
资源: 1

随机网络优化：通信与队列系统中的Lyapunov控制与稳定性分析

Stochastic Network Optimization with Application to Communication

Lyapunov.m:使用 Lyapunov Drift-Plus-Penalty 技术的随机网络优化-matlab开发

Lyapunov Stability

下载 pdf stochastic network optimization with application to communication a

Lyapunov随机优化理论

随机优化理论能解决的问题

复杂网络的随机网络模型的研究

matlab神经网络优化对比图

神经网络中优化方法有() A:梯度下降法 B:随机梯度下降法 C： Adam D：随机下降法

鲸鱼算法优化随机森林

BP神经网络优化结构

使用网络搜索来优化随机森林模型Python代码

MalConv使用反向传播算法和随机梯度下降优化算法

matlab 基于遗传算法的bp神经网络优化

使用网络搜索做随机森林模型

遗传算法对bp神经网络优化python

神经网络解决优化问题

用自己的话介绍神经网络优化之后得到结论一千字

随机配置网络matlab

卷积神经网络优化器的作用是什么，什么最常用

最新资源