logo资料库

无线网络通信网络中的频率分配算法.doc

发布时间：2022-06-10 发布人：admin 分类：说明书 资料大小：0.16M 资料格式：doc 举报 版权申诉
第1页 / 共17页
第2页 / 共17页
第3页 / 共17页
第4页 / 共17页
第5页 / 共17页
第6页 / 共17页
第7页 / 共17页
第8页 / 共17页
资料共17页，剩余部分请下载后查看
    第一章 引言
    1.1文章的研究背景，目的和意义
    1.2信道分配的概念
    1.3无线通信网络中的频率分配基本模型
    1.3.1频率分配的概述
    1.3.2基本模型的简述
    第二章．贪心算法与在线算法概述
    2.1 贪心算法概述
    2.1.1贪心算法的性质
    2.2在线算法和竞争比的定义
    2.2.1在线算法
    2.2.2 竞争比和渐进竞争比的定义
    2.3 k-look-ahead在线算法
    2.4 1-look-ahead在线算法
    第三章 线性网络频率分配算法
    3.1贪心算法分析
    第四章 算法Hybrid在蜂窝网络中的性能分析
    4.1 概述
    4.2 绝对竞争比
    第五章 结论
    参考文献
    摘要 本文中我们研究了几个在线算法的竞争比问题。对于 k-look-ahead 在线算法我们 证明了该算法的竞争比下界至少为(k+2)/(k+1)，我们还给出了一个竞争比为 2 的 1-look-ahead 算法。对于贪心算法我们着重分析了贪心算法在 Without Deletion 模型的 前提下，证明了贪心算法在线性网络中的竞争比是 3/2；证明了不存在绝对竞争比小 于 3/2 的在线算法， 最后在蜂窝网络中对算法 hybrid 进行了性能分析。 无线通信；在线算法；竞争比；Without deletion 模型 关键词 Abstract In this article we studied several online algorithm competitions to compare the question.We had proven regarding the k-look-ahead online algorithm this algorithm competition compares the world of mortals is (k+2)/(k+1) at least, we returned to give back to a competition ratio are 2 1-look-ahead algorithms.We have analyzed the greedy algorithm emphatically regarding the greedy algorithm in Without under the Deletion model premise, had proven the greedy algorithm in the linear network competition ratio is 3/2; Had proven does not exist competes absolutely compared to is smaller than 3/2 online algorithm, finally has carried on the performance analysis in the honeycomb network to algorithm hybrid. Key word Wireless correspondence; Online algorithm; Competition ratio; Without deletion model I
    目 录 第一章 引言............................................................................................................................................... 1 1.1 文章的研究背景，目的和意义.................................................................................................. 1 1.2 信道分配的概念.......................................................................................................................... 1 1.3 无线通信网络中的频率分配基本模型 ......................................................................................1 1.3.1 频率分配的概述.............................................................................................................. 1 1.3.2 基本模型的简述.............................................................................................................. 1 第二章．贪心算法与在线算法概述......................................................................................................... 3 2.1 贪心算法概述 .............................................................................................................................. 3 2.1.1 贪心算法的性质................................................................................................................ 3 2.2 在线算法和竞争比的定义 ........................................................................................................... 4 2.2.1 在线算法 ............................................................................................................................ 4 2.2.2 竞争比和渐进竞争比的定义 ...........................................................................................4 2.3 k-look-ahead 在线算法 ................................................................................................................. 4 2.4 1-look-ahead 在线算法 ................................................................................................................. 5 第三章 线性网络频率分配算法 ............................................................................................................... 8 3.1 贪心算法分析 .............................................................................................................................. 8 第四章 算法 Hybrid 在蜂窝网络中的性能分析....................................................................................11 4.1 概述 ............................................................................................................................................11 4.2 绝对竞争比................................................................................................................................11 第五章 结论 ..............................................................................................................................................14 参考文献 ....................................................................................................................................................15 致谢 ........................................................................................................................... 错误！未定义书签。 II
    无线通信网络中的频率分配的在线算法 第一章 引言 1.1 文章的研究背景，目的和意义 随着社会进步、经济和科技的发展，特别是计算机程控交换、数字通信的发展， 移动通信系统以其显著的特点和优势得以迅猛发展，应用在社会各个方面。以 GSM 为代表的移动通信网络飞速发展，导致无线频率资源很快就会被用殆尽，各个国家都 意识到这点，因此，如何有效的利用有限的带宽来完成更多的通信成为在通信、计算 机、甚至数学领域中得到广泛研究成为一个非常热的问题。本论文正是围绕有限的频 率资源如何得到有效分配而展开分析的。 1.2 信道分配的概念 信道是信号的传输媒质，可分为有线信道和无线信道两类。有线信道包括明线、 对称电缆、同轴电缆及光缆等。无线信道有地波传播、短波电离层反射、超短波或微 波视距中继、人造卫星中继以及各种散射信道等。如果我们把信道的范围扩大，它还 可以包括有关的变换装置，比如：发送设备、接收设备、馈线与天线、调制器、解调 器等，我们称这种扩大的信道为广义信道，而称前者为狭义信道。信道分配就是把这 两类信道（有线信道和无线信道）在允许的条件下进行分配。 1.3 无线通信网络中的频率分配基本模型 1.3.1频率分配的概述 首先，关于无线通信网络中的在线分配问题，从频率分配的角度来考虑不同的模 型，它们都有着下面所描述的两个共性： ●当两个用户端需要建立通信时，系统必须通过无线设备分别为这两个用户 分配频率 (信道)来建立一条通信链接。这条通信链接的两端是无线 设备与用户之间的无线链 接，而中间部分是高速的有线网络连接 。 ●当建立两条无线通信链接的频率满足下面的两个条件时，它们之间会出现 干 扰 现 象，这会导致通信质量的下降。 -两个频率在无线频谱中非常接近，彼此之间会产生干扰现象。 -当两个无线 通信链接在地理分布上非常接近时，如果干扰频率的能量很大 ，它也 会对信号频率造成干扰。 1.3.2基本模型的简述 为了更清楚的分析无线通信网络的频率分配问题，下面我们分别给出两个频率分 配问题所研究的模型。在这两个模型中，我们研究的目的都是为了使系统的频率使用 效率尽可能的高，也即，在满足所有的通信请求时，使占用到的频率数量尽可能的少。 ●Without Deletion模型 1
    在这个模型中，我们假设每个通话的时长都是无限，即，当给一个通话分配好频 率之后，这个通话将一直占有这个频率。 ●With Deletion模型 在这个模型中，每个通话的时长都为有限，即，任何通话在进行了一段时间都会 终止，它占用到的频率会被释放。 2
    第二章．贪心算法与在线算法概述 2.1 贪心算法概述 在贪心算法（greedy method）中采用逐步构造最优解的方法。在每个阶段，都 作出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅 是在某种意义上的局部最优解。决策一旦作出，就不可再更改。作出贪婪决策的依据 称为贪心准则（greedy criterion）。 例 2-1 一个小孩买了价值少于 1 美元的糖，并将 1 美元的钱交给售货员。售货 员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为 25 美分 10 美分、 5 美分及 1 美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择 硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行 性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所 需的数目。 假设需要找给小孩 67 美分，首先入选的是两枚 25 美分的硬币，第三枚入选的不 能是 25 美分的硬币，否则硬币的选择将不可行（零钱总数超过 67 美分），第三枚应 选择 10 美分的硬币，然后是 5 美分的，最后加入两个 1 美分的硬币。 贪心算法就是这样每次都作出当前认为最好的选择，于是我们考虑怎样的问题适 合用贪心算法解呢？ 2.1.1 贪心算法的性质 对于一个问题，我们怎么知道可否用贪心算法求解，以及能否得到一个问题的最 优解，这个问题很难给与肯定的回答，但是从许多可以用贪心算法求解的问题中，我 们看到它们一般具有两个重要的性质：贪心选择的性质和最优子结构性质。 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择， 即贪心选择来达到，这是贪心算法可行的第一基本要素，也是贪心算法与动态规划算 法的主要区别，在动态规划算法中每步所作的选择往往依赖于相关子问题的解，因而 只有在解出相关子问题后才能作出选择，而在贪心算法中，凭着当前的状态，就作出 在当前看来是最好的选择，即局部最优选择。然后再去解作出这个选择后产生的相应 子问题。贪心算法所作的贪心选择可以依赖于以往所作过的选择，但绝不依赖于将来 所作的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底 向上的方式解各子问题，而贪心算法则通常是自顶向下以迭代的方式作出相继的贪心 选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。 最优子结构性质 若一个问题的最优解包含着它的子问题的最优解，则称此问题具有最优子结构性 质。问题所具有的这个性质是该问题可用动态规划算法或贪心算法的一个关键特若一 个问题的最优解包含着它的子问题的最优解，则称此问题具有最优子结构性质。问题 3
    所具有的这个性质是该问题可用动态规划算法或贪心算法的一个关键特征 2.2 在线算法和竞争比的定义 2.2.1 在线算法 在线算法（on line algorithm）就是当未来发生的事件是不可预知的时候，在线算 法对每个到达的数据必须作出即时处理(计算机即时响应)并要求对已作出的处理在 后续的处理过程中不得更改。 由于对后续没有完整的信息可用，在此时看似正确合理的处理，但在之后可能就 会产生偏差。因此，从这个意义上在线算法都是近似算法（approximation algorithm） 即不能保证产生最优解。 2.2.2 竞争比和渐进竞争比的定义 竞争比就是这样一个比值，对于在线算法来说，其输入随时间而不断增加。对每 个时刻的输入，算法都必须在不知道未来输入的情况下产生相应的输出。此时得到的 最终结果设为 X，对同一问题的离线算法得到的最终结果设为 Y，我们称 X/Y 的比 值就为竞争比。 渐进竞争比就是当我们要处理的未来发生的事件的数量趋向于无穷时的这样一 个竞争比。不难理解，在现实中，算法的渐进竞争比较之竞争比应用更广泛。 2.3 k-look-ahead 在线算法 在我们分析 k-look-ahead 在线算法前，我们引入“时间槽”的概念，时间槽就是 将时间槽分成等长的单位时间，其中每一份单位时间就相当于一个时间槽，如果一个 算法可以看到未来的 k 个时间槽：我们称其为 k-look-ahead 在线算法。接下来我们将 证明任何 k-look-ahead 在线算法都不可能是(k+2)/(k+1)-competitive 的，证明一个好的 下界其实是要设计一个好的 adversary。一个 adversary 是一组输入序列,在线算法在这 些输入面前将(相比离线最优解)表现得很糟糕。直观上讲,我们要找的 adversary 就是 在线算法的最坏情况。回到我们的问题,我们看到在线算法是短视的——k-look-ahead 的在线算法无法看到未来第 k+1 个时间槽和其后的任何信息，一个“残酷”的 adversary 会充分利用这一点，针对在线算法可能的不同行为给出不同的输入。 定理 2.1 所有 k-look-ahead 在线算法的竞争比至少是(k+2)/(k+1)。 证明：关键的一点是注意到一个短视的在线算法永远也不会知道最优解保持的传 输速率是多大，考虑一个由 k+1 个容量为 1 的时间槽构成的输入序列,在线算法会给 第 1 个时间槽赋什么值呢?假设这个值是 x，根据这个值，adversary 会给出第 k+2 个 时间槽的容量： 1 如果 x>(k+1)/(k+2)adversary 会给出一个容量为 x-ε的时间槽，于是离线最优 解是(x-ε)(k+2),而在线算法最多得到 x(k+1)。 4
    ② 如果 x≤(k+1)/(k+2)，adversary 会给出一个容量为 1 的时间槽于是离线最优解 是 k+2，另一方面,若 x>0，在线算法最多得到 x+k 或 x(k+2)(两者均小于 k+1)；若 x=0，在线算法最多得到 k+1 任一情况下竞争比都不小于(k+2)/(k+1)。 证毕 2.4 1-look-ahead 在线算法 下面我们将看到,即便是最少量的前瞻—向前看 1—就能使在线算法相当的 “competitive”了。我们的算法可以看做是数据传输器在当前时间槽处用来做决定的 “策略”。数据传输器的策略很简单；它只根据 3 个值来决定当前的(传输速率：1)上 一个时间槽的值(prevUsage；2)当前时间槽的容量(currCap；3)下一个时间槽的容量 nextCap(也就是它向前看到的)。 定理 2.2 下面的算法是 2-competitive 的 ·prevUsage=0 -nextCap≥2×currCap set to 0· -3/4currCap≤nextCap0 -prevUsage>currCap set to 0· -prevUsage≤currCap *nextCap≥2×prevUsage set to 0· *nextCap<2×prevUsage set toprevUsage· 证明：首先看算法做了什么，直观地讲，如果上一个时间槽值非零，则我们只有 两个选择：保持或置零如果 prevUsage>currCap，那么只能置零(我们可以放心置零， 因为在给上一个时间槽赋值时已经考虑到这一点)如果 prevUsage≤currCap，可以考虑 保持 prevUsage 这个值。但是考虑到万一下一个时间槽太大,可能因此丧失改变速率的 时机而无法 competitive 因此合理的做法是设定一个上限，也就是算法中的“2”同理 在 prevUsage=0 的情况下我们也设定了同样的上限。在该情况下,其实有更大的自由， 因为可以选择任何在 0 到 currCap 间的值一种想法是取 currCap 与 nextCap 中小的一 个，这样可以保持这个值至少一个时间槽，但是如果这个值(相对)太小,也许应当放弃 5
    它而把大的置满。这样就有了“3/4”这个下限。直观的感觉也许这两个阈值应该互 为倒数,但很容易证明，如果把 3/4 降低到 1/2 则算法就不是 2-competitive 的了。 下面分析该算法首先注意到，算法实际上将输入序列分成了一段一段的周期，在每 个周期中，时间槽都有基本相同的形状,而算法对它们的分配也基本一样假设第 2 个 时间槽的容量大于上限，那么算法会将第 1 个时间槽置零，算法会继续置零，直到发 现当前时间槽与下一时间槽的容量相差不，这时当前槽就将成为第 1 个非零的时间 槽。此后,当前槽的值将被保持一段时间,直到出现一个容量小于此值的时间槽或者是 两个相差很大的时间槽，这时就又出现了被置零的槽，从而进入了一个新的周期，图 2.4.1 和图 2.4.2 是两个周期的例子，从中我们可以看到周期开头和结尾的两种可能。 周期的划分极大地方便了对算法的分析，因为只要算法在每个周期内都是 2-competitve 的，那么它在全局范围内就也是 2-competitv 的这是因为任何全局解在每 个周期内也是可行解，所以 adversary 在每个周期内只会有更大的自由。 图 2.4.1 一个周期 图 2.4.2 另一个周期 为了分析算法的竞争比,必须找出算法表现最坏的情况，首先我们注意到,在每个 周期的保持部分算法显然是 2-competitve 的,因为被保持的值至少是容量的一半，于 是,下面这个不等式告诉我们: if a/c0) then a/c<[（a+ b）/（c+ d）]
    分享到：
    赞 收藏

    相关推荐

    资料库

    网络技术

    共收录2367份资料，累计7个分类，关注成员有19位，主要包括：综合布线,网管软件,网络监控,网络设备,其它,系统集成,网络基础

    热门标签

    综合布线 网管软件 网络监控 网络设备 其它 系统集成 网络基础

    最新资料