SA的初始解及控制参数设计优化

对于形如式（7.4）的优化问题，文献[10]分析了多种求解方法。然而，面向互联网的视频组播系统存在数据传输时延较大、往返时延不对称等特点，一般的求解方法在精度及实时性方面难以满足要求。事实上，当优化问题的规模较小时，经典的启发式算法，如构造法、最近邻近法等就能得到满足要求的解。但对于多速率组播拥塞控制这类NP问题，随着节点数量的增多，问题的复杂性也成几何级数增加，传统的启发式算法已不具备实用性。考虑到模拟退火算法与其他算法相比，具有收敛速度快、可求出全局最优解的优点[11]，本书采用模拟退火（Simulated Annealing，SA）算法求解形如式（7.4）的多速率组播拥塞控制问题。

模拟退火算法的理论基础为Boltzmann 概率分布和metropolis准则。为便于求解，首先将式（7.4）转化为以下形式：

其中，ρ为惩罚因子本质上，上式为一无约束优化问题。首先，为保持解集的完备性，将解集S 定义为S =｛b（rp）｝，其中0 ≤p≤Q。初始解x=｛r0，r1，…，rp｝，其中r0 =r1 =…rp=0.75Bupload/n，Bupload 为传输链路的带宽，n 为接收端节点个数。

此外，新解是通过对当前解的扰动得到的，为提高收敛速度，采用与文献[12]中VFSA算法相同的方式求取新解，即

其中，λ为0 至1 之间的随机数，[l，h]为解的取值范围，T为当前温度，sgn（）为取符号函数，x′表示求得的新解。显然，在本书的组播拥塞控制模型中，各接收端的请求速率不会超过各链路容量，即有l=0，h=C（ei）。本质上，式（7.5）、（7.6）将SA中的模型扰动作为Cauchy分布进行计算，以便SA在执行过程中能够迅速跳出局部极值，加快收敛速度。(www.xing528.com)

类似地，为提高算法的实时性，将初始温度T0 取为Bupload n，其中n 为接收端的节点数量。相应的退火计划，即温度的衰减参数Tk表示为

其中，α为温度衰减率，本书取0.95。Markov链长度Lm，也即同一温度下的迭代次数，取Lm=nβ，其中β 为常数，这里取100。

此外，按照metropolis准则，与新解相对应的接收概率为

其中， 为接收端节点的数量。