论文部分内容阅读
在这篇文章中，我们研究了无线通信网络中的在线频率分配问题。无线通信网络通常将整个覆盖区域划分为很多小区，每个小区通过一个基站与小区内的移动用户进行无线信号的通讯。当一个通讯请求出现在某小区时，无线通信系统必须立即为其分配一个频率。为了避免干扰，同一小区内或者在两个相邻小区内的通话不能被分配同一个频率。我们的目标是使用最少的频率来满足所有的通话。 对于频率分配问题，本文中给出了两个模型：Without Deletion模型和With Deletion模型。针对这两个模型，我们着重研究了线性网络和蜂窝网络中的在线频率分配，分别被简称为FAL和FAC。 在Without Deletion模型下，我们首先详细分析研究了贪心算法(Greedy)，将其在蜂窝网络中的竞争比从介于[17／7，2.5)之间[28]固定到了17／7。更进一步的，我们证明了Greedy对于FAL来说是一个最优的在线算法。随后，我们还证明了对于一个即使是可以2着色的网络结构，Greedy使用的频率数量与最优解的比值可以是任意大。 其次，我们给出了一个解决FAC和FAL的新算法HYBRID，这个算法是Greedy(贪心算法)和FAA(固定频率分配，Fixed Allocation Assignment)的结合。算法HYBRID正面回答了在[28]中提出的未解决问题，即，对于FAC来说，存在着竞争比为2的在线算法(HYBRID)。随后，我们给出了竞争比下界是2的证明。这样，我们提出的算法HYBRID在FAC中是最优的。我们同样可以证明HYBRID的是解决FAL的一个最优在线算法。这个算法还可以扩展到κ可着色图上，可以证明在κ可着色图中，我们可以设计出竞争比是(κ+1)／2的在线算法。当小区中的通话数大量增加时，我们研究了FAC和FAL中的渐进竞争比。对于FAL，我们证明了其渐进竞争比的下界是4／3，在将HYBRID更加一般化后，给出了一个渐进竞争比为1.382的在线算法，这大大改善了之前竞争比为1.5的算法。对于FAC，我们证明了其渐进竞争比的下界是1.5，同样，在将HYBRID扩展后，得到了一个渐进竞争比为1.913的在线算法，较之于之前的竞争比为2的算法，其性能得到了改善。 在With Deletion模型下，我们首先证明了贪心算法Greedy在FAL和FAC中的竞争比分别是2和3。 在FAL中，我们给出了一个竞争比为5／3的在线算法MG，并且证明了5／3是FAL中竞争比的下界。因此，算法MG在解决FAL问题上是最优的。同时，我们还证明了在FAL中，其渐进竞争比的下界是14／9。 最后，在FAC中，我们分别证明了解决这个问题在线算法的绝对竞争比和渐进竞争比的下界分别是19／9和2。