分层优化网络资源规划方法之网络规划和设计方法
2)
用模拟退火算法求解 EOM 模型 ： EOM 模型是个有难度的组合优化问题，因为在模型中有很多变量和复杂的约束 [13] 。没有一种优化算法能在合理的时间里求得最优解。在文献 [15] 和 [16] 中报导的建立在模拟退火 (SA) 基础上的算法被用来解决这个问题，并在合理的时间内求得了逼近最优解。
对于求解 NP 完全组合问题的逼近解来说模拟退火是种好方法 [13] 。它已被成功应用于某些领域，如计算机的优化设计 [16] ，图象处理，信道分配 [8][20] 和规划布局问题。算法采用一种迭代方案，它模拟物理退火过程：加热固体直到其融化，然后花最少的能量冷却它使其结晶至基态。
为了用模拟退火过程解决 EOM 问题，需要考虑下面四个方面：配置空间，成本函数，相邻结构和冷却进度表。
a) 配置空间 ：对于 EOM 模型，配置空间 S 是所有满足覆盖约束 (13) 和其它约束 (15)-(20) 可行解 { 
} 的集。
b) 成本函数 ：在实际的系统设计中，首先要考虑覆盖性能。对于给定的小区数量，由于非一致话务分布的存在，如果要满足覆盖和话务两者的要求，没有几个可行解可被求得。因而引入话务约束 (14) 到目标函数，目标函数就从 (12) 变为最小化基站的总设备成本和破坏话务负载后引起的总补偿，即：
(22)
其中函数 [x] 
=max(0,x) 。
因为 (12) 中的系统固定成本 
不影响 EOM 模型的最优解，故在成本函数中不再包含这一项。
c) 相邻结构： 用 N(s) 表示的解 s 的邻域由在满足约束 (15)-(17) 时，移动网格 k 从当前小区 i 到相邻小区 j 时产生。
d) 冷却进度表： 决定 初始温度 t 
以确保可接受转换与提议转换之比的特定接受率 χ 接近 1[15] 。这可以通过从一个小的正数 t 
出发，迭代地变换它直到达到接受率 χ来得到。
Huang[21] 用在某一温度的成本分布的标准偏差来决定下个温度的减小量，并提出下面的 温度递减规则 ：
(23)
其中 
是在温度 t 
的成本分布的标准偏差； 
是发生在两个连续温度 t 
和 t 
之间的平均成本的减少量。为保持准平衡，当 
。 
的典型值 0.7 。
在某个温度 平衡 意味着齐次马尔可夫链的固定成本分布的建立。 Huang 假设了一个关于平衡的成本的正态分布，它们的平均值 
和标准偏差 
都由马尔可夫链估计而来。他们提出了完成固定分布检查的 平衡条件 ：一旦平衡建立，其成本限制在范围 
内可接受的转换次数的比率将达到一个稳定值 μ ＝ erf( 
) ，其中 
介于平均成本 
( 它被称为 次数内 ) 和可接受转换总次数之间， erf(x) 是 x 的误差函数 [22] 。 
的典型值为 0.5 ，从而可得 μ ＝ erf( 
) ＝ 0.38 。两个平衡参数，一个目标 次数内 和一个最大容许偏差极限，都根据问题的大小建立。如果 次数内 在容许偏差次数超过最大极限值以前达到了目标值，我们就认为保持了平衡 [21] 。
对于我们的 EOM 问题，我们设置 次数内 ＝ 0.38*(3*m*n) 和最大容许偏差 = 0.62*(3*m*n) 。
我们说取得了 最后温度 ，如果在那个温度的马而可夫链的整个轨迹里，最大和最小成本的差值等于在那个温度的一次可接受转换里的成本的最大一次变化。
下列伪代码程序描述了解决 EOM 问题的模拟退火过程 (SAEOM) 。
解决 EOM 问题的模拟退火过程 (SAEOM) ：
Begin
初始化 ( 
) ；
k := 0 ；
s := 
；
Repeat
Until 平衡达到 do
Begin
从 N(s) 产生 
；
If ( 
) then s := 
Else
If exp((f(s)-f( 
))/t 
) > random[0,1) then s := 
End ；
k := k+1 ；
计算 t 
；
Until 停止准则成立
End
与 Kirpatrick[16] 提出的模拟退火技巧相比，这个用 Huang 方法 [21] 的新 SA 技巧能通过退火过程动态调节马尔可夫链的长度达到平衡，退火需要的 CPU 时间也大大地下降了。
C. 详细规划和准确的成本估计
在这一层，确定每个小区内的基站位置，诸如天线塔高度，天线增益和发射功率等参数都进一步根据每个小区的地形不规则性的特征，表面覆盖和环境进行调整。从上面两层得到的结果已满足了覆盖性能，并试图满足话务要求。但不管怎样，在某些小区的话务过载可能仍然存在。在这一层，可以用 Hale[6] 和 Gamst[23] 的信道分配策略来提供信道数的下界。把在 [7][8][20] 中提到的固定和动态信道分配策略应用于蜂窝系统的网络规划以提供足够的容量来为预期的话务量服务，并保持无线干扰到最小限度。
如果系统性能在调整后达到了要求，最后的系统设计就确定了，也就可以估计出蜂窝系统的成本。否则在这一层的结果将反馈到第一层和第二层。然后重复整个过程。在这种情况下，可能需要增加小区的数量以满足规定的服务质量。
