再上一篇:7.6  连接矩阵的 λ1的推导
上一篇: 第 8 章  电  信
主页
下一篇: 第 9 章  点模式匹配
再下一篇:9. 2  模拟退火框架
文章列表

8. 2  集成 TDMA 通信系统的数据吞吐量最大化

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

在集成分时多路存取(TDMA)通信系统中,语音和数据通过多路复用来分享一个共同的传输通道。时间轴被分为许多帧,每帧又由一定数目的定长时段组成。每一帧的时段都有特定部分用于语音,剩下的则用于数据。许多科技文献都将语音业务量用有损系统,而将数据量用排队系统作为模型。因此在信号到达时,如果不能获得有效时段,语音业务量就被阻断而不进行传输,而数据则会被排队,并在数据时段有空时按先来先送的规则传送。故此,系统设计的目标是将语音业务量被阻断的概率和数据量排队的延迟最小化。通常用到的是定长边界(FB)或可变边界(MB)两种方法之一。在定长边界法中,TDMA 的帧被划分为各有特定数目时段的两个区:一个给语音,另一个给数据。分配给语音的但不在工作的时段不能用来传输数据。显然,这种方法不能充分利用系统资源。相反,可变边界法利用剩余语音时段传送数据。这在很多时候可以减小排队延迟。为了充分利用集成系统的资源,已有许多多路复用策略被提出(文献[37,52,72,173])。

文献[37]中使用了一种数据传输的分段ALOHA随机存取协议。它不构成一个长队而是在出现冲突(当两个或更多数据包在同一时段被传送)时,数据被重传。最大数据吞吐量可以通过搜索语音与数据在帧中相对位置的最优构形来获得。这是一个NP 完全约束下的最优化问题。作为又一个电信应用的示例,均场退火算法在数据吞吐量最大化中的应用体现了它在性能和计算复杂度之间很好的折衷。

8.2.1  多路复用方案与数据吞吐量

这里介绍的均场退火方法采用了与文献[37]中相同的假定和多路复用策略。在TDMA的传输通道中,语音以同步方式传输,数据则以争用方式传输。一个由N 个定长时段组成的帧格式如图8.2所示。因为这里所用的是MB多路复用方式,数据传输既可使用数据时段也可利用即时可用的剩余语音时段。下面列出一些术语:

图8.2  一个由N 个时段组成的帧,其中Nd个分配给数据

Nd 是在一个给定帧中可被数据包所用的时段数;

ki是第i个可用数据时段的时段序号,且1≤ki≤N,1≤i≤Nd;

si是第i个数据时段与紧接其后的第(i+ 1)个数据时段的间距,且

#第81页-

si= ki+ 1 - ki 如果i= 1,2,…,Nd - 1 (8.29)

k1+ N - kNd 如果i= Nd

s= (s1,s2,…,sNd)在集成通信系统中被称为帧模式。

从帧的格式可以很容易看出,

s1 + s2+ …+ sNd = N (8.30)为了使问题变得在数学上易解,引进下列假定:

(1) 语音传输的通话时间比帧长大得多,因而数据对一个给定帧模式的排队状态可达到稳态。

(2) 分段ALOHA 随机存取协议[145]用作数据传输。总数据流通量(包括新的和重传)符合平均到达率为G包/时段的泊松(Poisson)过程。

在间距si上没有冲突的概率为在该时间段上没有泊松数据流通量被生成的概率。故此,

- G¡¤si

Pr(在间距si上没有冲突) = e (8.31)

- G¡¤si

Pr(数据包在si上成功传送) = G¡¤si¡¤e (8.32)规一化的吞吐量为

Nd

1 - G¡¤s

γs = G¡¤si¡¤e i (8.33)

Nd∑

i=1

数据吞吐量在很大程度上受语音和数据相对位置的影响。为了将数据吞吐量最大化,数据流通量被授予使用帧中 d 个时段的较高优先权。因此,给定 和 d,存在 N 个帧模

N N N C d

式。例如,假定在最大化数据吞吐量时有 = 50且 d= 15,总共可以有的帧模式数为 50

N N C= 82.25 1012。随着待解问题变大,利用穷举搜索在所有帧模式中寻找最优帧模式会变得难以处理。

8.2.2  数据吞吐量的最大化

数据吞吐量的最大化等价于找出一个特别的帧模式 opt使得

s

Nd

opt 1 - G¡¤si

γs = maxγs = max ∑G¡¤si¡¤e (8.34)

s∈S s∈S Nd

i=1

且有约束

Nd

∑si= N (8.35)

i=1

其中1≤si≤N- Nd+ 1。

运用均场退火求解这一有约束条件的最优化问题的步骤可以归纳如下:

(1) 构造一个既能最大化数据吞吐量又能满足约束条件的能量函数。

(2) 选择能在数据吞吐量最大化和满足约束条件之间保持平衡的拉格朗日参数。

(3) 确定临界温度Tc。

(4) 确定退火流程。

(5) 定义收敛准则。

#第82页-

(6) 进行迭代操作直至找到最优解:

① 将神经元i的均值初始化为vi= 0.5+ 0.001 rand[- 1,1]," i,且从临界温度开始退火;

② 在每个温度T 处,按照均场等式更新vi," i,直到满足一定准则。在固定温度下对所有神经元的全部更新称为一次扫描。

③ 根据退火流程降温,重复步骤直到收敛准则被满足。在每个温度下,进行一系列扫描。

vi" i的值在退火结束时对应于帧模式。

将这一最优化问题映射到均场退火的框架中去,上述步骤中所需参数的确定方式如下:

1. 能量函数

N w N N′

d 2 2 d

w1 - G¡¤s w2

E(s) = - Gsie i+ si- N + w3 sij(1- sij) (8.36)

Nd∑ 2 ∑ ∑∑

i= 1 i=1 i=1 j=1

N′

其中 i= ∑ ij2j- 1, l> 0( = 1,2,3), ij∈{0,1},

s j= 1s w l s

log2(N - Nd - 1) + 1 如果 log2(N - Nd - 1) = log2(N - Nd - 1)N′=

log2(N - Nd - 1) 其它

(8.37)式中 ・ 是取上整数操作。

第i个数据时段与紧接其后的第(i+ 1)个数据时段的间距由si表示。因为si是一个整数,且1≤si≤N- Nd+ 1,si可用N 个二值神经元sij的各项表达。换句话说,sij对应于si的N 位二值表示。第一项是权值为负的数据吞吐量,因而最大数据吞吐量对应于最小负吞吐量。第二项引进了对违反约束的惩罚。如果(8.35)式给出的约束被满足,则第二项对应的能量为零。第三项仅当所有神经元都收敛于0或1时为零。如果适当选取拉格朗日参数(w1,w2,w3),退火过程会将系统引向一个对应于最优帧模式的最小能量构形。

2. 拉格朗日参数

退火过程将系统松弛到具有最小能量的状态并同时满足所有的约束条件。一个违背约束的状态(帧模式)s′应该具有比满足约束的一个状态 s 的能量更大的能量, 亦即E(s′)> E(s)。考虑状态s满足(8.35)式给出的约束条件,且每个神经元都已收敛到0或1的情况。如果s的邻近状态s′与其只有一个元素之差但却违背约束从而使得

Nd

si= N - 1≠N (8.38)

∑i= 1

Nd

w1 - G¡¤s′ w2

E(s′) = - G¡¤s′i¤e i+ (8.39)

Nd∑ 2

i= 1

Nd

w1 - G¡¤s′

E(s) = - G¡¤si¡¤e i (8.40)

Nd∑

i= 1

#第83页-

其中

s′i= sk - 1 如果i= k,对于一定k (8.41)

si " i,除非i= k

因此,

ΔE = E(s′) - E(s)

Nd Nd

w1 - G¡¤s′ w2 w1 - G¡¤s

= - G¡¤si¡¤e i+ + G¡¤si¡¤e i

Nd∑ 2 Nd∑

i=1 i=1

w2 w1 ¡¤G - G¡¤s′ - G¡¤s

= - s′ke k - sk ¡¤e k

2 Nd

w2 w1 ¡¤G G

- G¡¤sk

> 2 - Nd ¡¤e (sk - 1) ¡¤e - (sk - 1)

w2 w1

≥ - ¡¤(1- e- G) ¡¤e- 1 ≥0

2 Nd

2w1 - G - 1

w2 ≥ Nd ¡¤(1- e ) ¡¤e (8.42)在此仅考虑了一种特殊情况,表明w1 和w2 的选择是与G和Nd 有关的。要取得更好的解答,必须根据G和Nd 调整拉格朗日参数。w3 项是一个弱约束,在后面介绍的模拟实验中取w3= 1。

3. 均场公式

与SBS问题相似,这一问题的均场等式为

1 1 - 1 E(v,t)

vij = 2 + 2tanh 2T vij , " i,j (8.43)其中对于1< i< Nt, 1≤j≤N′, vij= < sij> T,且

v= {v1,v2,…,vNd},  vi= {vi1,vi2,…,viN′}

4. 临界温度

临界温度被定义为剧烈状态转移开始稳定于0或1处时的温度。从(8.43)式可以看到,每个vij在高温时都在1/2左右浮动,且状态转移是慢的。因此存在一个快速状态转移开始变为稳定状态的临界温度。这里没有像在SBS问题中那样导出一个闭式解的估值,而是用试错法获得临界温度。也就是使温度从很高处缓慢下降,在每个温度处只作一次扫描,在每次扫描结束时,计算平均绝对误差

N N′

1 d

ε= ∑∑©¦ij(t+ δt) - vij(t)©¦ (8.44)

Nd ¡¤N′i=1 j=1

其中t 为扫描开始的时间,而t+ δt是扫描结束的时间。当ε≥0.1时,上述步骤停止,且对应温度即为临界温度。

5. 退火流程

在此用到下列退火流程:

Tn+1 = Tn (8.45)

1+ α¡¤n

#第84页-

其中α是一个小的正数,n是迭代变量。

6. 终止准则

有两个终止准则。一个是在每个温度处扫描的终止准则,另一个是整个退火过程的终止准则。

在每个温度下,每个神经元的取值都依据(8.43)式更新。扫描在ε≤δ1 时终止,其中1 是一个小的正数。另外,在某个温度下,这一情况可能在很多次扫描后仍不会出现。为了避免无穷无尽的扫描,扫描进程在扫描次数达到一个给定数值时被强行终止。然后,降低温度,一个新的迭代过程开始。

所有vij在稳态时都应收敛于0或1。因此,采用下列收敛准则

N N′

1 d

∑∑vij(1- vij) < δ2 (8.46)

Nd ¡¤N′i= 1 j= 1

其中δ2是一个小的正值。当准则被满足时,所有神经元的取值都为1或0,且最优帧模式的间距为

N′

si= vij - 0.5 2j- 1, " i (8.47)

∑j= 1

7. 仿真结果

作为一个示例,图8.3给出了用均场退火从下列参数得到的数据吞吐量:

N = 40, Nd = 5, Tc= 5, δ1 = 0.05, δ2 = 0.01, 且α= 0.01

图8.3  数据吞吐量与通话量的关系曲线

(8.37)式中w1 和w2 的关系是G和Nd 的函数。有实验表明w2 不能随意设为一个大的正值,即使满足(8.42)式。一个大的w2 会给约束太大的权重。在这种情况下,退火过程可能会把系统带到一个虽满足约束但能量较高的状态。其结果是一个局部最优解。在这里的仿真中,这些参数凭经验选为: 当G≥0.4时,w1= 750,w3= 1,且 w2= 750;当G< 0.4时,w2= 6.5。仿真结果表明均场退火方法给出的结果是或接近于全局最优。定义拉格朗日参数间更严格的关系并且根据G和Nd 动态调整这些参数依然是一个挑战性的研究课题。

#第85页-

8.3  总结

本章通过介绍均场退火在两类远程通信最优化问题中的应用,概述了将待解问题映射到可由均场退火求解的框架中去的方法,并推导和讨论了诸如拉格朗日参数和临界温度等与问题本身有关的关键参数。随着VLSI(超大规模集成电路)技术的飞速发展,适于实时应用的均场退火方法正在由可能变为现实。

均场退火可应用于许多其它通信问题,例如卫星通信网络的管理[15]和分组无线广播网络的播出调度[167]。IEEE Journal on SelectedAreasin Communications 的专集[151]集中探讨了计算智能在高速网中的应用。

8.4  习题

8.1  证明(8.8)式的有效性。

8.2  推导(8.12)式给出的SBS 问题的均场等式。

8.3  利用引理8.1估计8.1.5节描述的SBS 问题的临界温度。

8.4  用模拟退火求解本章给出的两个例子。

#第86页-