再上一篇:7.5  本征值分析概述
上一篇:7.6  连接矩阵的 λ1的推导
主页
下一篇:8. 2  集成 TDMA 通信系统的数据吞吐量最大化
再下一篇: 第 9 章  点模式匹配
文章列表

第 8 章  电  信

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

为了提供现有的和正在形成的电信服务,要用到某些形式的计算智能。虽然传统的方法已经得到了非常成功的应用,然而对更快捷、更可靠的传输的不断增长的需要呼唤着新方法的出现。计算智能在电信中的应用包括异步传输方式(ATM)宽带网络的交通管制、网络管理、信道均衡、数据和视频压缩、参数估计、路由选择、卫星通信、波传播建模以及无线通信。本章将向读者介绍一些实际应用的例子,其中有卫星广播调度[19]和集成通信系统中的数据传输率最大化问题[166]。更多的应用可参见文献[1,14,15,28,38,40,41,42,47,69,74,78,79,111,113,114,121,126,147,151,160,165,167,175]。

8. 1  卫星广播调度

优化一组卫星对一组地面站的广播时间,即卫星广播调度问题(SBS),是低空卫星通信系统中必须解决的重要问题。波莱特(Bourret)等人在文献[34,35]中用一个三层相连神经元模型来求解这一问题,其顺序搜索是由一个基于卫星的动态优先权竞争激活机制来控制的。在局域进行的顺序搜索也十分耗时。此外还需要两个附加的先决条件: 一组互不相同的卫星优先权和一组在解决大型问题时很难确定的适当要求。

在这一节中,介绍另外一种基于均场退火的更加有效的解决SBS 问题的方法。这个方法不需要前述的两个附加条件。它没有采取文献[132]介绍的特殊神经元模型(分级神经元)以缩小解答空间并避免破坏性的冗余度,而是使用了由一个结合矩阵箝位的通用神经元模型。这一常用于学习算法[13][116][128]的箝位技术可以大大减小解答空间。由于Sigmoid函数的非线性,存在一个所谓的临界温度Tc。可推导估算Tc的公式以便取代决定Tc的试错法。

8.1.1  SBS 问题的神经网络表达

自从第一颗商用卫星“远星”在60年代被成功发射以来,卫星通信工业的年产值已增长为数十亿美元。尽管还不能覆盖远北纬[154],发射成本高,且需要很大天线等,但多数商用系统都已被发射到对地球静止的轨道上。对地球静止的轨道的优点是卫星与地面站呈静态,因而不需要从一个卫星到另一个卫星的“交接”。选用对地球静止的轨道主要是为了适应国际长途电话的大通信量。当各种电信应用变得越来越复杂时,有时需要用不是对地球静止的轨道。在这种情况下,就需要对从一个卫星到另一个卫星的“交接”[134]加以调度。这正是本章所要介绍的内容。因为低空卫星的发射数目很小,而且多数是用于监视和数据采集的专有或保密卫星,只有很少人涉及这一问题。不过,低空卫星具有卫星能耗低、天线减小、传播延迟变短以及图象分辨率高等潜在优点,这正促使工业界建立一个这样的卫星

#第74页-

系统。因此卫星广播调度成为一个重要问题。对于当前已经和正在开发的用于个人通信系统的现代化卫星,文献[6]给出了较为详尽的综述。

求解SBS问题的目的是将每个卫星的广播时间最大化,并使如下约束条件得到满足:

(1) 一个卫星不能同时向多于一个地面站广播;

(2) 一个地面站不能同时从多于一个卫星接收信息;

(3) 一个卫星的播出必须离要求时间尽可能接近,而且系统不能分配比要求时间还长的时间,除非其它卫星的要求时间都得到完全满足;

(4) 卫星只当它能被地面站接收时才播出。

下列术语用于表述SBS问题:

(1) s= {a,b,c,d,…}= {1,2,3, …,i,…,Ns}是由Ns 个元素(卫星)组成的卫星集合,其中a,b,c,d,…表示不同的卫星,每一个都用在1和Ns之间的整数i编号。

(2) a= {z,y,x,w,…}= {1,2,3,…,j,…,Na}是由Na 个元素(地面站)组成的地面站集合,其中z,y,x,w,…表示不同的地面站,每一个都用在1和Na 之间的整数j 编号。

(3) t= {1,2,3,…,k,…,Nt}是由Nt 个元素(时间段)组成的时间段集合。

(4) = [ 1, 2,…, N ]T 是一个向量,表示一个给定问题所要求的时间段数集合。它

r r r r s

包括Ns 个元素(时间段)。这里,r1,r2,…,rNs分别为卫星1,2,3,…,Ns的时间段个数。

(5) = [ 1, 2,…, N ]T 是一个向量,表示一个系统对每个卫星所分配的时间段数

u u u u s

集合。它包括Ns个元素(时间段)。这里,u1,u2,…,uN 分别是分配给卫星1,2,3,…,Ns 的

s

时间段个数。

求解的目标是给每一个卫星都尽可能地分配所需时间段,以同时满足下列两个准则:

(1) 调度方案必须合理,亦即满足所有约束;

(2) 向量u和r 之间的距离必须被最小化。

1. 神经元编码

用sijk表示神经元。sijk的“激活”或“抑制”是由卫星i在k时间段是否被分配给地面站j 来决定的。因此,sijk的数学定义为

sijk= 1  如果卫星i在k时间段被分配给地面站j (8.1)

0  其它

2. 结合矩阵

从上面定义的神经元可以清楚地看到,基于前述约束条件(4),一些神经元的值恒定为零。这是因为即使所有地面站都不工作,也没有一个地面站对该卫星是可见的。通常,因约束条件(4)而取值为零的神经元数目很大。通过在整个优化过程中将不满足约束条件(4)的神经元箝制为零,这一约束条件可以被吸纳到神经元网络中去。下面NsNa 行Nt 列的结合矩阵A正是为此而定义的。

a111 a112 … a11Nt

A1 ┆ ┆ ┆ ┆

A2 a1N 1 a1N 2 … a1N N

A= = a a a t (8.2)

┆ ┆ ┆ ┆ ┆

ANs

aNsNa1 aNsNa2 … aNsNaNt

#第75页-

其中Ai是一个Na Nt 的子矩阵。它与加在卫星i上的约束关联,且有

sijk = 1  如果卫星i在k时间段可被地面站j 接收 (8.3)

0  其它

从A的定义和问题的约束条件出发,可以得到两个重要的关系:

(1) 卫星i所要求的最大时间段个数rmax(i)必须小于或等于子矩阵Ai中的非零列数,亦即

Nt

rmax(i) ≤∑(Ai中的非零列) (8.4)

k=1

(2) 可用的时间段ui必须小于或等于rmax(i),亦即

Na Nt

ui= ∑∑sijk ≤rmax(i) (8.5)

j k

上述关系会在检验解答是否合理时用到。

3. 能量函数

将一个有约束的最优化问题转化为无约束的最优化问题而得到的SBS 问题的能量函数由一个代价项和一些反映约束的惩罚项构成,即

E = w0E0+ w1E1 + w2E2 + w3E3 (8.6)其中拉格朗日参数w0,w1,w2,w3 分别为E0,E1,E2,E3 项的权重。作为代价项的第一项为

Ns Na Nt

E0 = - 1 (sijk ¡¤sijk) (8.7)

2∑∑∑

i j k

这一项的目的是使总播出时间最大,其中的负号表示要将E0 项最小化。根据4个约束定义以下的惩罚项:

(1) 一个卫星不能同时向多于一个地面站广播。可以证明这一约束条件的惩罚项为

Ns Nt Na Na

E1 = ∑∑∑∑(sijk ¡¤sij k) (8.8)

i k j j ≠j 1

1

(2) 一个地面站不能同时从多于一个卫星接收信息。约束(2)与约束(1)对偶。它的惩罚项类似地定义为

Na Nt Ns Ns

E2 = ∑∑∑∑(sijk ¡¤si1jk) (8.9)

j k i i1≠i

(3) 一个卫星的播出必须离要求时间段尽可能接近,而且系统不能分配比要求时间还长的时间,除非其它卫星的要求时间都得到完全满足。上面所述的前一部分表明u与r之间的距离应为最小。因而,与之对应的惩罚项为

Ns Na Nt Ns

2 2

E3 = ∑ ∑∑sijk - ri = ∑(ui- ri) (8.10)

i j k i

(4) 一个卫星只有当它能被一个地面站可见时才能播出。这一约束由结合矩阵将神经元的取值箝制为零来实现。

8.1.2  SBS 问题的均场公式

对于二值神经元变量sijk∈{0,1},可得与(5.14)式类似的SBS问题的均场公式,即

#第76页-

vijk= 1 + 1tanh - 1 E (8.11)

2 2 2T vijk

其中vijk是与神经元sijk对应的均场变量。把上述将神经元的取值箝制为零的技术引入(8.11)式,SBS问题的均场公式成为

1 1 - 1 E

vijk= aijk 2 + 2tanh 2T vijk (8.12)这一等式事实上已将前一小节所述约束(4)包含在内。

8.1.3  算法的参数

需要规定的参数包括拉格朗日参数(w0,w1,w2,w3)、临界温度、饱和温度和退火流程。本节主要介绍拉格朗日参数。

一般来讲,好的解答可从w0,w1,w2,w3 空间的一个合理的较大范围内获得。然而,为了确保所选的参数落在这一范围之内,一些指导性原则还是需要的。在均场域中,用vijk简单地取代(8.7)式~(8.10)式中的sijk,能量函数E0,E1,E2,E3 成为均场变量的函数:

Ns Na Nt

E0 = - 1 (vijk ¡¤vijk) (8.13)

2∑∑∑

i j k

Ns Nt Na Na

E1 = ∑∑∑∑(vijk ¡¤vij k) (8.14)

i k j j ≠j 1

1

Na Nt Ns Ns

E2 = ∑∑∑∑(vijk ¡¤vijk) (8.15)

j k i i≠i 1

1

Ns Na Nt

E3 = vijk - ri 2 (8.16)

∑i ∑j∑k

均场域中总能量函数的微分为

E = w0 E0 + w1 E1 + w2 E2 + w3 E3 (8.17)

vijk vijk vijk vijk vijk

参数w0 用于平衡代价项与约束条件项。参数w1,w2,w3 则反映了约束(1)到(3)之间的相对重要性。因为 E1与 E2性质相近且比其它项重要得多,它们被赋予相对较大的相同权

vijk vijk

值。例如,可选w0= 0.4,w1= 2.0,w2= 2.0。

在考虑每一个单独参数对任意均场变量的影响时,从(8.14)式和(8.15)式可知 E1

vijk与 E2总为正值,因而根据(8.12)式,它们使 ijk的值趋向于“0”。从(8.13)式可见 E0总为

vijk v vijk负数并使 ijk的值趋向于“1”。基于所需时间段是否得到满足, E3既可为正亦可为负,从

v vijk

而使神经元的值相应地趋向于“0”或“1”。

假定约束条件(1)和(2)已被满足,亦即 1= 2= 0 E1= E2= 0。下面要做的就是

E E vijk vijk

决定w0 和w3之间的关系。在vijk为0或1的特殊情况下,对于每一个特定的i,如果取值为1的均场变量个数大于所需时间段数(见(8.16)式),这表明系统已经分配了比需要还

#第77页-

多的时间段。因此,系统应在此时试图“抑制(置0)”一个均场变量。注意,“激活”的均场变

Na Nt

量满足 E0= - 1(见(8.13)式)与 E3= 2 vijk- ri ≥2(见(8.16)式),这是因为系

vijk vijk ∑∑

j k

Na Nt

统分配了比需要还多的时间段。也就是说, ∑∑vijk- ri ≥1。要抑制一个均场变量,需

j k

有(见(8.17)式)

E E0 E3

vijk > 0 w0 vijk + w3 vijk > 0

Na Nt

w0(- 1) + 2w3 vijk - ri > 0 (8.18)

∑j∑k

w0(- 1) + 2w3 > 0

w3 > 0.5w0

在另一个特殊情况下,网络分配的时间段个数小于所需时间段数。这时网络应试图激

E0 E3 E活一个均场变量。注意, 抑制”的均场变量有 vijk= 0且 vijk< 0。因此,只要w3> 0, vijk<0,均场变量被“激活”。

总之,对于SBS 问题,给出以下经验值:

w0 = 0.4, w1 = w2= 2, w1> w3> 0.5w0 (8.19)8.1.4  临界温度Tc

为了深入了解求解过程的动态特性,均场等式可被改写如下:

1 1 1 E

vijk - aijk = tanh - aijk (8.20)

2 2 2T vijk

在SBS问题中能量函数对于均场变量的偏导具有下列线性形式:

(E) = m(vijk - α) (8.21)

vijk

其中m 和α是常数。从(8.20)式可以很容易看出,除了被结合矩阵强制为零的神经元之外,所有其它神经元在高温下的取值都为0.5。不过,随着温度的下降,非线性tanh(・)渐进于一个Signum 函数,且均场变量开始稳定在“0”和“1”处。这里要确定的参数是具有显著状态转移的临界温度,这时系统能量急剧下降。由于未被强行箝制为零的神经元的起始值都为0.5,从而上述显著状态转移发生在神经元开始竞争取值为1或0时,因此可以给出临界温度的定义。

定义8.1  临界温度是至少一个均场变量vijk从起始状态值(亦即0.5)达到1或0的最高温度。

基于上述定义,临界温度可由下面的引理加以估计。

引理8.1  SBS 问题的临界温度Tc可由下式近似:

Tc= m(2α- β- 1) (8.22)

其中m,α和β可从下列方程组得到:

#第78页-

2vijk- 1= β

1 (8.23)

- 2Tm(vijk- α) = β

证明: 由定义8.1,在至少一个均场变量vijk从起始状态值0.5达到1或0的条件下,

求解(8.20)式中的参数T 可得到临界温度。由于(8.20)式中有非线性项tanh(・),推导

出它的严格数学解答即使可能也是非常困难的。下面将 - x 在 = 0处泰勒展

tanh 2T x

开,对(8.20)式做近似处理,即

x x 1 x 3

tanh - 2T = - 2T + 24 2T + … (8.24)

取其第一项而得到

2vijk- 1= - 1 E (8.25)

2T vijk

这里,没有考虑均场变量被强行置零的情况,即aijk= 1。将(8.21)式引入上述结果可得

2vijk- 1= - m (vijk- α) (8.26)

2T

因此,求解方程组(8.23)可得临界温度。这里,因为显著状态转移发生在神经元取值从起

始温度0.5达到1或0时,所以β为+ 1或- 1,亦即vijk= 1或0 β= ±1。进一步讲,如

果 α> 1且m> 0,则稳态解① 为vijk= 1(β= 1);如果α< 1且m> 0,则稳态解为 vijk= 0

(β= - 1)。从取值0.5的起始状态出发,下表列出了m,α和β之间的关系:

α> 0.5 α< 0.5 t

m> 0 β= + 1 β= - 1

m< 0 β= - 1 β= + 1

严格地讲,当0< α< 1时,vijk不会取值0或1。然而,在数次迭代后,这一特定vijk将收

敛于0或1。对于不同的均场变量vijk,α的取值可以是不同的。不过,只要临界温度的估计

值比实际临界温度值高,退火理论保证系统可以收敛于一个(接近)全局最优。因此,对于

一个给定的结合矩阵A,每一个均场变量对应的α都应由(8.21)式计算出来,最大的α值

将被选用。

退火流程  这里采用下列线性退火流程:

T(n+ 1) = 0.9T(n) (8.27)

其中T(0)= Tc。退火过程的停止准则由网络饱和时的温度(饱和温度)定义。网络在满足

下列条件时饱和:

(1) 所有神经元的值都在[0.0,0.2]或[0.8,1.0]范围内,无一例外。

1 2

(2) ∑i∑j∑k(vijk) > 0.95, 其中N 是取值在[0.8, 1.0]范围内的均场变量

N

个数。

1 1 m -

① 由 + - (v - α) 估值的稳态解应该达到0或1。

tanh ijk

2 2 2T

#第79页-

8.1.5  一个示例

上面提出的方法已被应用于解决多种不同需求量的SBS问题。需求播出时间小于系统可分配最大容量的情况被称为小需求型;而需求播出时间大于网络最大容量的情况被称为大需求型。这里以一个具有108个神经元(其中44个神经元未被强制置零)的网络示范求解小需求型和大需求型的例子。

设有4颗卫星、3个地面站和9个时间段,且此SBS问题的第4项约束条件由下面结合矩阵定义:

1 1 0 1 0 1 1 0 1

0 0 1 0 0 0 0 1 0

1 0 0 1 1 1 1 1 0

1 1 1 1 0 0 0 0 1

0 0 1 0 0 0 1 1 0

A= 0 0 0 1 0 1 0 0 1 (8.28)

1 0 1 0 0 1 1 0 1

0 0 0 0 0 0 0 0 1

0 0 0 0 1 1 1 1 0

0 1 1 0 0 0 0 0 1

0 0 0 0 0 0 0 1 1

1 0 0 1 0 0 0 1 1

已知所需时间段为r= [2,2,2,2]T。符合需求且满足约束条件的时间段分配如图8.1(a)所示。当所需时间段 = [9,8,7,6]T 明显超出系统容量时,解答如图8.1( )所示,且时间

r b

段分配为u= [6,5,4,3]T。虽然系统不能满足所有需求,但它仍在给定约束条件下提供了

图8.1  小需求情况和大需求情况的广播调度

每个方块代表被分配的时间;每行代表一个地面站;每列代表一个时间段。

#第80页-

最大播出时间。在更大运算代价下,对更大需求问题的求解给出了一致性的结果。建议读者用不同的例子进行实验。其它例如收敛性等问题的讨论可见文献[19]。