无线网络规划包括很多应该考虑的重要问题。尤其是许多研究者试图提出各种方案来提高网络的性能和效率:通过寻找最佳规划的蜂窝网络，选择节点在无线局域网(Wlans)的位置和访问类型，以及将基站和节点放置在中的多目标网络中。　　对于提高网络的效率及性能鲁棒性、自我管理、灵活性和任务支持，无线网络基础设施的管理起着非常重要和关键的作用。　　基础设施位置的设定可分为基站布置问题和天线的布置问题。前者与基站的位置有关，而后者与对某些特定候选基站的节点天线分配有关。本论文所述无线节点布置问题是一个天线问题。基站布置问题和天线的布置问题，就目前所知，都是NP难的。即在P≠NP的假设下，没有确定的算法可以在多项式时间内解决这一问题。　　值得一提的是，布置一个新的天线非常昂贵，不仅仅是因为设备上的花费，还有正确的设备安装方法和系统规划的花费，这使得通过常规的方法（如单元分裂）增加系统容量不具有吸引力。此外，由于有限的无线带宽，网络无法同时支持大量用户，尤其是对于需要大量、快速的数据传输速率的应用程序。　　无线网络集成也许可以以较高数据传输率提供服务，同时节约成本。然而，无线局域网的信号覆盖范围很小（特别是在城市地区），只能向在其覆盖面积内的用户，通过固定的接入点方式提供服务。为了克服这一缺点，使其能够为大多数用户服务，必须要部署高密度的无线局域网接入点。但是，此解决方案会导致成本增加，并降低固定基础设施的效率。　　无线节点布置问题就是构建一个优化的基础设施，即确定发射站的最佳位置——要考虑到覆盖面、成本、容量、干扰和切换这些特定因素。这些元素在问题模型中通常被定为目标、约束或两者都是，并会受到无线网络类型的影响，例如，数据通信或电信。己知这个问题是NP难的。　　在下文中，我们将详细描述节点布置问题，在本论文中使用的模型是基于这样一个模型——它与我们解决该问题的目标相适应，问题的说明与有关常数如下:　　候选站E:考虑给定一组有限的候选站{e1，e2，……，eE｝,D可用通信设备的总数。这些候选站eu的位置为（αu，βu）(V)u通信设备D:考虑给定一组有限的通信设备{d1，d2，……，dD｝,D是可用设备的总数。每个设备dv有功率pv，容量sv,消耗Cv，类型tv和功率范围wv接收器R:考虑有一组有限的接收器｛r1，r2……，rR｝被置于位置（αg，βg），R为接收器总数通信设备dv可能被给定与其相关的接收器rg不同的信号阈值θdg和信号强度Svg, i，u。信号阈值和信号强度一起，决定了节点覆盖范围。σdg是接收器rg从设备dv.索要数据的数据率节点N:节点集{n1，n2,……，nN｝，N为需要布置的节点总数一个网络由从候选站点列表中的选定的站点和设备（从通信设备中选择不同的给定的数目和位置）组成。任务是在服务范围内布置一组节点ni，即使在有小干扰发生的情况下，所有与这些节点相关联的接收器rg都能被覆盖。　　在本论文中，我们要处理异构网络的节点布置问题，我们必须优化节点位置，使其通信能够覆盖新建立的网络，此外我们解决了新的节点部署问题和将它们组合到原有基础设施的问题。　　每个节点的ni有一组特定的标识，比如:成本为c，功率和容量等等。我们在本文中有两个假设:首先，如果有一个新的基础设施，并想要在其中配置一组节点必须要考虑我们的目标和约束条件:其次，我们假设我们通过现有网络的时间范围知道了需求分布，同时我们想要部署新节点，并通过现有的基础设施将其组合进去。　　现有的基础设施架构是一个同质或异质的节点集合，这些节点与稳定的分层网络关联，并连接每个通信设备类型。这些构成了现有网络的节点有一系列特征如:功率、计算能力和覆盖范围的大小。此外，我们必须有一个现有网络基础设施的主要集，定义为Hd，其中基础设施与每个通信设备dv相关联。只有在有需要时，我们才添加这些额外节点。此外，这些额外的节点应满足系统的限制，还应该能够通过网络进行协作、通信和协商。我们提供了我们知道的通信设备dv和节点集N。我们的主要目标是在特定区域的覆盖范围中找到最佳位置、数目、通信类型和连接。　　进一步的，我们还解释了节点和通信设备D，候选站点M及其它节点ni之间的通信过程。　　与通信设备相关联的节点我们认为，为每个节点ni可分配给一组通信设备D。也就是说，对于每个节点的ni可以通过一些通信设备dv连接到不同的通信网络。通信设备dv特征由不同的参数设定。我们的模型提出考虑了功率、容量、成本、通信设备类型、功率范围和带宽，每个通信设备dv可以描述为六元组τ=(p、s、c、t、w、b)，其中p表示要将节点连接到接收器的功率，s表示节点提供的控制测试点的数据需求的带宽或者能力，c表示通讯设备成本，t表示通信设备类型，在这里，我们只使用一种类型，w表示要连接网络中的节点所需的功率范围，b表示两个连接网络的节点之间的带宽。　　与候选站点相关联的节点我们还必须考虑候选站点集E与空间坐标(αu，βu)来表示节点的可能位置。每个节点ni应该只与一个候选站点eu通信。我们还用一组接收器rg来模拟流量通信需求，这些接收器为了连接到通信网络需要特=特别的信号强度，该强度来自通信设备d。我们可以标识这些测试点作为一个或一组移动终端用来做覆盖。在我们的案例研究中，接收器rg都假定通过这片区域能够得到均匀分配和用于最大化我们的网络通信覆盖。我们认为每个接收器rg具有空间坐标（αg，βg），它从节点获得无线信号。无线连通性通过数据速率需求θdg和信号阈值σde来评价，以保持服务质量。　　目标　　在规划无线网络基础设施时有几个影响因素。对于网络运营商来说，安装一个新的节点或额外节点通常是非常昂贵的。为此，本文的主要目标是优化节点数量，通过考虑4个事情:覆盖、成本、容量和重叠。其中覆盖和重叠是考虑节点的位置，成本与节点数量有关，容量则受节点和通信设备类型的影响。　　覆盖优化通常包括两个目的:尽量减少信号质量差的地区和提高整个服务区的平均信号质量。覆盖范围的最大化是融合网络的主要问题。就我们的问题来说，我们考虑了一大组接收器来最大化通信覆盖。第二个目标是尽量减少网络的建造成本，即安装节点和与它相关联的通信设备的成本。在我们问题中，使得节点放置数最小，同时实现重叠率最低的全覆盖，使得安置成本最小化。第三个目标是最小化最大带宽，网络设计模型必须提供足够的数据速率（带宽）给用户用户，这一目标的主要问题是最大化网络的最小带宽容量。换句话说，我们需要尽量减小通信设备带宽和覆盖接收器的数据速率需求的总和的绝对差额。第四个目标是尽量减少重叠，这个目标函数旨在减少引起通信设备之间的重叠覆盖的网络干扰。可以通过接收器由多个通信设备覆盖数目来确定网络中的重叠。此外所有以前的目标，我们处理一些约束时必须满足符合我们模型问题的可行的解决方案。第一个约束是与特定的通信设备连接到的任何节点的所有指定接收器的总数据速率需求的总和应该小于或等于该通讯设备的能力，第二个约束是为每个节点可以分配多个通信设备，第三项约束就是每个分配给多个候选站点的节点，第四个约束是大多数一个节点分配给每个候选站点，第五的约束是每个接收器最多可以被一个节点连接到通讯设备。　　主要有三个通过使用进化的技术解决优化问题的方法:基于算法的帕累托最优实现、基于算法的指标和基于算法的分解。帕累托优势算法，因为解决了MOPs，所以实现了很好的性能，但在应用于多目标问题（超过4个目标）时，性能很差。性能的下降随着非优势解的增长是呈指数增长的，所有人体在群体中都不会有帕累托优势，即使在如所述的早期。超体积指标的频繁使用表明目标为7个时技术规模比较好，虽然仅当指标能被评估时才发生。分解方法:似乎是一个求解多目标优化问题的不错的选择。它能简单的实现和解决多个单目标问题。这种方法的主要优点是良好的可扩展性和考虑目标的数目情况下的计算效率。举个例子，基于分解(MOEA/D)的多目标进化算法解决PF逼近问题时，通过将多目标优化问题分解为若干个标量的优化子问题，同时优化它们。MOEA/D使用切比雪夫分解方法来近似Pareto Front(PF)问题转化成大量标量优化子问题。每个子问题利用其相邻的子问题用于优化的信息来做优化，它通过众多的解发展，同时解决优化问题。在每一代中，群体包括了每个子问题目前为止找到的最优解。这些子问题的邻接关系是它们聚集系数向量之间的距离。两个相邻的子问题的最优解应该很近。　　保存可行性解的补偿函数使得可行和不可行的解和混合方法的分离。基于当前解决方案中可行解的数目，并考虑到亲子群体的联合，约束问题的搜索过程可以分为三个阶段:1）不可行解2）至少一个可行解和3）结合亲子群体比下一代父群体有更多可行解。多年来在处理EAs中的各种约束条件后，已可以提供了各种约束处理技术。这些技术之间的差别是在这三个搜索阶段中如何处理不可行个体。　　虽然解决约束单目标优化问题已经研究了几十年，但在求解约束多目标优化问题上取得的进展很少。　　MOEA/D需要两个参数:小生境参数和定义邻域的补偿参数——必须要设置正确。此外，MOEA/D的作者并不建议任何有效的程序，通过MOEA/D处理约束，此后一个修正的模型CMOEA/D-DE-ATP被引入用来处理在多目标优化问题中的约束，它调节MOEA/D的替换和更新方案，修改后的方案提出了补偿函数用来拒绝不可行解。补偿函数应用阈值管理补偿量，不可行解依靠一个由MOEA/D提出了更新方案中的自适应门限值。我们已经使用由MOEA/D算法的实现的方法来解决我们的多目标问题。　　CMOEA/D-DE-ATP需要将MOP分解为一系列子问题。对于节点的问题，在四个目标约束条件下，它将问题分解成m标量优化子问题。我们建议采用CMOEA/D-DE-ATP作为解决多目标最优化问题的方案来解决节点布局问题。　　此外，被提出的代表性、选择性、交叉性和突变性，被提出的算法可以自动搜索适当的节点数，并优化它的位置——通过最大化覆盖、最小化成本、最大化容量满意度和最小化重叠来考虑约束在异构的网络基础设施中的问题。主要问题应该被考虑到——即当我们要解决的问题是节点数时，应该灵活一点，同时问题解决者应考虑带约束的多目标情形。　　陈述　　候选方案，也就是一组额外节点N被编码到一条染色体。对于每个属于N的节点被表示为长度为n的子串，该子串由位置Z组成（Z与不同的可用通信设备D的数目有关），在网络中用Y代表，候选站点用X表示。一般CMOEA/D-DE-ATP的方法CMOEA/D-DE-ATP算法的第1步是初始化。初始解由一个特定问题启发式生成或随机生成，本论文提出使用一个均匀的随机样本来生成n个解来初始化内部群体。　　在步骤2-1，新的解通过使用遗传算法算子用来生成解。第一是选定算子，它决定某个个体将影响下一代的生成。论文提出使用锦标赛选择算子（第3.4.2节将详细介绍）。第二个算子是交叉度，它需要一定数量的父代重组它们，并创造新数目的子代。本论文提出均匀交叉算子（第3.3节将介绍）。第三个算子是突变算子，它旨在在搜索空间中生成新的解——现有解的变体而来（第3.5节）。　　第二个和第三个算子用于步骤2-2，在这一步中启发式算子增加了节点的个体利用率。它创建解Z，通过在步骤2-3中使用DE算子，Z能用于更新种群，如果y元素超出边界，通过随机选择步骤2-4边界内的值重置y，并求y值。在步骤2-5，为每个解zj更新种群。　　在步骤2-6中考虑所有的ith子问题的邻居，y是否比xj实现更好。来考虑jth子问题，它用yo替换xj。在步骤3中，检查终止准则，以决定搜索应该停止还是继续，以便让我们的算法将在一定代数后停止。在步骤4中，增加代gen=gen+l。许多进化算法实验者不断变换算法的关键参数和相关的特征值（图5.2）试图确定对于一个特定的问题实例或类最有效，最高效的实现。　　种群初始化　　种群初始化是所有EA的第一也是首要任务。一般来说，这些搜索技术开始通过一些初始解（初始种群），尝试在一些最优的解的方向改善它们。当一些预定义的标准满足是停止搜索进程。如果有关该解的预先信息不存在，我们通常则以随机解开始。除其他外，计算时间是与这些从最优解初始推测的距离有关。为了提高我们一开始就得到更靠近（更适合）解的机会，就要同时检查相反解。在这之后，更合适的解（估计或相反估计）可以选择作为初始解。现在重要的是注意到假设某一问题是一个单目标优化问题，则最好的解是种群中’最高适应值’的解决。另一方面，假设问题是一个多目标优化问题，则该算法将在多目标域中检查两个解的”基于方法的帕累托”。　　初始种群在染色体中随机生成的子串分配，对于某一候选站点特定位置的子串的数量是从一个可能的索引[1，2,…，M]中随机选取的，对于某一特定通信设备类型从一组通信设备集[1，2，…，D]中选取，对于一定数量的被连接的其他节点则随机的从[1,…，|Zd|]中创建。然后调整每个染色体来验证我们的约束问题，并因此提出一套可行解来表示我们初始解。　　随机生成初始种群后，进化算法改善其中的3个算子:等效于适者生存的选择算子，引入个体之间交配的交叉算子，生成随机修饰的突变算子。　　1.1选择算子就MOP而言选择算子是最重要的一点。通过使用适合函数值来选择的最佳染色体。因此，选择可以被认为是“适者生存”的生存部分。选择将主要是选择在生存的有序列表中具有更高的适应值的个体，但也有一些选择方案，其中有一些具有较低的适应值的个体在以一定的水平在有序列表中求生存。当“好”的染色体被需要时，列表的上部会被额外使用，而对于“坏”的染色体则使用列表的下部。　　选择总是在种群上实现第一个算子。选择算子在一个种群中选择好的一系列种群同时构建了一个交配池。这就是选择操作有时作为繁殖操纵算子的理由之一。正常选择的选择操纵基因方法导致这些个体编码成功的结构来更规律地创建副本。在对于遗传算法(GA)中的用于选择染色体的几种方法已演变成，轮盘选择父母来与他们的适应性一致。　　更好的染色体将有更多的机会来选择。该染色体将被选择的机会与它的适应性是成正比的。排名选择，首先，跻身种群和在这之后，每个染色体接收来自这个排名的适应性。最好将拥有等于N的适应性，其中N表示种群中的染色体数目。最坏的适应性会有等于1的适应性，第二个最差的适应性等于2等等。这里的想法是根据他们的适应值安排染色体的递减顺序。　　然后在安排的集合中来对每两条染色体应用选择。以这种方式，遗传算法将在强染色体之间或弱染色体之间使用。这意味着没有机会在弱和强染色体之间运用遗传算法，本次选择的稳定选择的主要目标是染色体的很大一部分，其为将要生存并且遗传给下一代。GA然后以下面方式的执行。　　对于创建一个新的后代，在每一代中选择几个（良好适应度高）的染色体。最后竞争，但在这里我们会处理竞争。竞争选择是从中种群随机选择某些数量的个体，并从该组复制最佳个体到使用进化算法的选择方法的中间种群。对于最简单的竞争选择是选择从种群中随机选择两个随机个体来展开竞争以决定哪一个体当选。此外，它可以被有效地执行。　　步骤2中的遗传算法用于产生一个新的解，特别是在CMOEA/D-DE-ATP步骤2.1的第i个循环，这里的选择算子的主要目标是选择M模式最近的子问题的两个亲本染色体，通过计算它们的权重[λ1……，λM]中的欧氏距离来找到一个子问题i在Pint中，并找到Xis邻居中，它们在一个交配中为竞争的关系，意味着我们的问题选择算子将选择对于节点最好的两个位置，其节点与竞争的位置和所选择的父母将提交到杂交基因之后的通信设备均相关。　　1.2交叉算子通过选择算法选择了2对父母后。交叉是结合了2对父母来构建一个新的后代染色体的操作。交叉的主要概念是，由于可能得到了父母双方最好的特征，新的染色体可能比父母双方更好。　　有几种方法介绍了交叉操作，首先是单点交叉，它是最常使用的交叉技术，单点交叉式进行随机的选择交叉点。第二个父母的第二部分是一个链接，该链接通过第一个父母的第一部来创造第一个后代。第二个父母的第一部分和第一个父母的第二部分来进行连接去建立第二个后代。　　两点交叉式是在父母有机体字符串中选择2点。它连接了三部分，染色体开始的二进制字符串到第一个交叉点是从一个父母中派生出来的，第一个点到第二个交叉点的部分是从第二个父母和它第一个父母衍生品中派生出来的。　　第三、均匀交叉式是这样的一个交叉操作:允许染色体的比特位从第一个父母或者第二个父母进中进行混合。　　中间交叉:中间产生的后代使用了父母的加权平均值。中间交叉依赖于一个参数的比例。　　如果比例是在(0，1)范围内，之后创建的后代位置是在父母位置相反的顶点上。　　最后是算术交叉:在算术交叉中(AC)，算法生成的孩子，这些孩子是2个父母的加权算术平均值。孩子与线性约束和边界无关是可行的。Alpha是在(O，1)中随机选择的一个数。如果是父母，则是一个最适合的值，该函数返回孩子。　　在步骤2.1中，2对父母随机的进行交叉配对来产生一个新的解决方案。尤其是在我们的问题中，交叉会改变节点与候选网站和通信设备进行联系的位置。　　1.3突变算子执行交叉操作后，变化的操作应用于单个解决方案，该解决方案是一个基因会在小概率的情况下进行随机改变，最后生成一个新的染色体。该操作的主要目标是维持种群的多样性、增加不丢失任何潜在方案的机会、保持全局最优，而交叉操作则是搜索空间的一个快速探测方法。突变在无性繁殖中是一个很常见的，它通常在为保持多样性的人群中和抑制早熟的集合中执行作为一个位的翻转。在这个算法中，我们维持了突变的速率，每一位都有概率进行翻转。　　选择和突变（没有进行交叉）生成一些低概率的部分，这些部分会有一些进行位的翻转。突变仅仅是在搜索空间中产生了一个随机的搜索。　　该算法的性能已经通过一系列不同测试问题的评估，我们在9个测试实例中设置了不同的问题，每个测试实例有两个问题需要解决1）确定异构网络基础设施中节点的位置2）同时最优化我们关心的四个对象:覆盖率、开销、能力和重叠性，同时考虑约束性条件。三个通讯设备各自的覆盖半径为13、15和17千米内性能分别为150，160，170 Mb/s，（随机数据传输速率的要求对于所有的设备只有一种类型存在）但是各自开销分别是3500，4500，5500。节点和接收器的增益提前被设定，两个节点间的带宽为500MHz，波长是0.025km。所有的接收器阈值为1，所有节点的成本各不相同。　　测试用例被分为两类:接收器所在位置区域的大小和及接收器密度的大小;根据接收器不同的密度和区域大小的参数结合，共有9个测试实例;所有的用例都是可用的，并且为单独实现的30倍。当迭代次数超过最大次数300次时，算法停止运行或者运行到目标函数不在扩大。在100次迭代之后表现出30人的规模。此外在我们的问题类中设置了种群数量为随机数。　　我们在MatLAb上实现这个算法，实验环境为Windows7平台Intel(R) CoreTMi5-2450QM CPU，2.50GHz，4G内存。　　实验结果表明MOEA/D在合理的运行时间内表现出很好的性能。更重要的是，比较的结果表明我们算法的性能都在预期目标内有效率。结果证明所提出的解决方案是有效的，此外我们还研究了该模型的性能以及9个测试用例与第一个对象之间的关系，发现覆盖率和测试点之间呈现正相关。随着测试点的增加（测试点是通过一些测试问题实例设定三个不同区域大小来呈现），第一个对象将增加到可以覆盖整个网络中所有的这些测试点。　　很明显一个网络规划最重要的目标是成本最小化（在我们的模型中节点数代表成本）因此我们运行算法寻求一种最实惠的解决方案，这个方案给出每个节点的位置的同时也能达到其他所有目标的需求。此外我们还研究了该模型的性能以及9个测试用例与第二个对象之间的关系，说明了不同测试问题实例的成本之间的关系。很明显，成本与覆盖区域的大小之间是存在比例关系的。　　实验结果表明，通过将我们算法针对MOGA算法（该算法解决同一节点放置问题）的解决方案与同样的问题实例中引入的相同的3个第一目标函数的解决方案进行比较，与此同时，我们增加了重叠的目标函数和使用的5个重要约束条件，其适用于我们的问题。　　实验结果阐述具有带宽不同的测试问题实例之间的关系，其中，在各个问题的情况下，几乎所有的测试点覆盖，而且他们的条件均被满足，我们可以观察到，对于我们必须覆盖的测试点，由于用于通信设备带宽的局限性，对于我们的位置获得更少的带宽，因此带宽目标与覆盖区的大小成反比。通过改变测试点的数量，我们观察到的节点数量增加时，测试点的数量增加。这是由于连接网络和分别提供更多带宽的需要所致。　　如果通信装置之间存在过多的重叠，干扰将会非常大而且频谱效率会很差。相反的是，对于移动性管理重叠是必需的。因此，我们需要不过大的重叠。实验结果示出了使用Z4不同测试问题实例之间的关系，很显然，重叠与覆盖的区域的大小成比例，另外，该重叠与额外的测试点和区域也相关联，很明显，随着不同区域的大小的测试点增加，第四个目标（重叠）也将增加。　　我们将我们的解决方案与推出了同样问题的同一目标函数进行对比，而且我们增加了重叠的目标函数和使用的5个重要约束条件，其适用于我们的问题。结果表明，我们的算法在所有3个目标的应用中比MOGA算法要号很多，此外我们介绍另一个客观值，由于CPU时间与目标数量和问题规模是相关的，因此我们的算法超过MOGA算法0.983039秒的平均CPU时间。　　最后，在本文给出的结果可以很容易地扩展到以下的情况，在其中我们有一个现有的网络，我们想要通过放置一些新节点将其展开。即假定，我们知道对于已经存在的网络通过一定时间范围为其进行需求分配，我们想要部署新的节点和通过现有的基础设施将它们结合起来。这个现有的基础设施是一组同构和异构的节点，其与固定和分层网络相关联，并将其连接到每个通信设备类型。我们仅当有需要时放置这些额外的节点。