文摘

多目标优化方法在静态路由无线网状网络(WMNs),与一个以上的QoS测量优化,非常具有挑战性。优化性能对于一个给定的端到端路由在静态网络,最常见的指标需要优化或有界的路径容量和端到端延迟。在这项工作中,我们注重结合理想的属性这两个指标通过最小化加权指标和通过Dijkstra-based算法。方法是针对快速收敛而不是最优。结果表明,生成的算法提供了令人满意的结果比简单Dijkstra-based修剪算法的同时实现大容量和小延迟。改变的影响权重因子对该算法性能研究。

1。介绍

无线网状网络(WMNs)由网格路由器,主要是固定在多次反射并为客户提供无线接入环境。他们发现广泛应用社会网络、企业网络、和最后一英里接入网络到互联网。是静态的,他们没有移动也没有功耗问题[1]。服务质量(QoS)路由WMNs已经吸引了相当多的研究多年。提出了多种路由度量WMNs提供路由算法具有较高的灵活性最好的路径选择。一般来说,路由问题可以看作是一个多目标优化问题最常见的指标需要优化或有界的路径容量或率和端到端延迟。率是每秒的比特数的路径(bps)可以发送源目的地的路径。QoS指标优化通常是通过有意义的取舍由于interconflicting自然。

值得注意的是,延迟最小化和最大化路径容量或吞吐量关心单个应用程序的性能,即优化给定的端到端路径性能在静态网络。相比之下,其他指标有优化非静态的WMNs如移动ad hoc网络,导致网络吞吐量最大化,最小化能耗,平均分配的交通负荷。这些指标体系的目标,专注于整个网络的性能(2]。在这项工作中,我们注重静态WMNs。

我们使用动态规划解决路由问题(DP)的方法(3- - - - - -5]。DP是一种非常强大的算法模式,通过识别一系列的子问题是解决一个问题,解决一个接一个,最小的首先,使用小问题的答案来解决更大的(5]。在这种情况下,路由的概念密切相关,找到一个有向图中最短路径(DG)通过DP技术。让被考虑的DG,是顶点的集合(网络节点)和是一组顶点之间的边(网络链接)。在WMNs,边缘是双向的,成本分配给他们。任意两个顶点之间的最短路径是由连续的边缘总成本的最小化。有各种适用的DP算法路由当单个指标最小化或优化,如Dijkstra算法、bellman和Floyd-Warshall技术(6,7]。这些不同的处理时间和需要收集的信息从其他节点,使每个人都方便特定的路由场景。

Multiconstrained优化路径选择的方法,与多个指标优化,非常具有挑战性,已被证明是np完备性(5,8]。一个问题是np完全如果所有的决定可以在多项式时间验证5]。

实现简略优化路由,迪杰斯特拉算法可以应用于网络。这个算法发现两个节点之间的最短路径的发展路径的路径长度增加。它的优点是快最短路径确定和计算的复杂性,在那里节点的数量,使其有效使用相对较大的网络。

第一次尝试多目标优化,一个可能会考虑一个简单的修剪程序。这包括优化指标(例如路径容量)使用Dijksta丢弃算法,然后修剪树图的树枝(路径),违反一组绑定到另一个度量(例如延迟)。还有许多其他的例子多目标优化路由的文学。例如,在[9),QoS multiconstrained路由算法提出了基于模拟退火(SA-RA)。该算法首先使用一个能量函数多个QoS指标转化为单一指标,然后通过模拟退火试图找到一条可行的路径。后者是一般随机逼近方法能够处理多个相互冲突的需求(多目标优化)10]。提出了一种遗传算法的路由方法称为这种在11)应对multiconstrained QoS路由问题。算法,然而,患有过早收敛与大多数计算复杂GA算法,和SA-RA方法(9是超越它。然而,即使模拟退火(SA)收敛速度慢的弱点;典型值是1 100个节点和1000 - 20秒女士节点网络(10]。出于这个原因,我们专注在这个工作在其他方面多目标优化的QoS路由,即结合理想性能的两个指标通过最小化加权指标和通过Dijkstra-based算法。但必须指出,这种方法是针对快速收敛而非最优;无法充分探索解空间,以强大的气体可以获得一个最优的解决方案。

加权和法是最常见的多目标优化方法。我们将展示的迪杰斯特拉算法加权和度量提供了令人满意的结果比简单的修剪算法的同时实现高路径容量和小端到端的延迟。我们还将分析算法性能的考虑和研究的影响改变了权重因子和源目的地双路由最优。

剩下的纸是组织如下:部分2讨论迪杰斯特拉算法用一个指标(延迟或能力)的概念并解释修剪的一步多目标优化QoS路由。部分3描述了加权和方法,以及如何将它与迪杰斯特拉算法并给出了其可行性和可行性的深刻的理由。各种结果证明该算法性能介绍和讨论部分4和结论部分5。

2。迪杰斯特拉算法

虽然迪杰斯特拉算法的最短路径的确定是建立在文献[6),我们发现它方便给一个简短的说明如下。(1)到目前为止的组节点由源节点和初始路径成本相邻节点只是成本的联系: (2)不是在邻近的节点从节点的最小路径然后发现节点纳入。也将是事件在该节点和边缘节点导致的路径 添加来随着事件的边缘贡献了代价最小的组件。(3)从节点之间的路径成本进行了比较网络中的任何节点和节点的路径成本的总和到节点(是另一个网络中的节点)和节点之间的链路成本节点考虑,选择最低: (4)步骤和重复,直到最终的路径已经分配给网络中的所有节点。该算法当所有节点已结束。该算法的运行时间在哪里是网络中节点的数量。

个人路径成本的路径可能是添加剂(如端到端延迟)成本计算整个路径,或者他们可以比较发现他们的最大或最小值(容量),并将这个值分配给整个路径。在某些情况下,成本的联系代表概率的错误,例如,成本增加的联系(12]找到相应的路径错误的概率。

算法1是一个伪代码说明如何Dijkstra算法找到最优路线的QoS测量能力。从节点的路径吗来,是它的速度。同样的,节点之间的联系吗和和是它的速度。星号表示最优表示连接。

延迟Dijkstra算法的优化算法将几乎相同的优化能力,除了成本添加的联系而不是找到整个路径成本相比。对于延迟的优化,总成本实际上是“最小化”术语符合一般的最短路径。

一步多目标优化路由,我们可以使用Dijkstra算法计算高容量的技术路径,同时边界端到端延时上限。这是实现如下。之前的决定包括注册节点的节点集,延迟路径的节点被认为是,如果发现超过绑定,这个节点是漠视和其他节点,首先是喜欢,是整合。这就是所谓的修剪。违反的路径延迟绑定修剪了通过比较路径之间的利率决定算法1然后比较延迟。后者比较可能会改变产生的决策。Dijkstra算法与修剪保留所有相应的优势,如快速最短路径计算和相对较小的计算复杂度。然而,其有效性在优化两个指标所示是有限的部分结果。

3所示。Dijkstra-Based加权和最小化(DWSM)算法

之前的Dijkstra-based加权和最小化(DWSM)算法,这是本文的重点,我们首先讨论的一般概念与多目标优化。

3.1。多目标优化问题

这个问题说明如下: 在哪里是目标函数的数量,不等式约束的数量,是平等的数量限制。是一个向量的设计变量(也称为决策变量),在哪里是独立变量的数量(13]。在一个网络中,x代表每个与路径链接或根据上下文节点。目标函数是一个向量。也称为目标或成本函数。网络中,它们代表路径容量,端到端延迟,等等。这些指标不同的路径,所以他们实际上是函数表示的网络路径x。可以认为是边界约束对啤酒花的数量等指标。

简略优化相比,没有单一的全球解决多目标优化问题。常常需要确定一个点集,所有符合预定的一个最佳的定义。这被称为帕累托最优(13]。一个点x(或路径)是帕累托最优如果没有其他点,提高了至少一个目标函数没有损害到另一个函数。点是弱帕累托最优,如果没有花药,同时改善所有的目标函数。帕累托最优的角度也弱帕累托最优,但反过来是不正确的。

3.2。加权和方法

这是最常见的多目标优化方法: 如果所有的重量都是正的,上述方程的最小是帕累托最优14]。权重设置等 相对的权重值反映了目标的相对重要性和优先级。一个先验权重的选择并不一定保证最终的解决方案是可以接受的。这个问题可能要解决新的权重。

3.3。提出DWSM算法

一个路由度量是一个函数,分配一个给定的路径和成本自然其个人链接。各种文献中介绍了联合路由度量,但针对特定应用领域如路由在multiradio多次反射WMNs [15和认知无线ad hoc网络路由16]。这些延迟最小化和最大化的概率数据在非静态WMNs交付。他们不关心最大化吞吐量能力或在静态WMN对于一个给定的端到端路径。我们提出的路由度量特征一个链接的网络只是加权和的形式链接的延迟和链接的逆能力。设计的性能指标的最小化,减少延迟和吞吐量最大化路径同时不是经常评估或研究在文献中由于逆吞吐量和延迟通常有不同的数量级(17]。在这工作,但是,我们表明,该优化是可能的在许多情况下,至少证明它是优于简单的修剪方法,多目标优化。该指标是由 体重的因素是一个可调参数的话题按照(6)。

上面的加权平均可以看作是试图平衡延迟和能力提供两者之间权衡。当Dijkstra算法相结合的算法,最短路径发现最小化度规沿着这条道路。度规是添加剂沿着一条路径。如果,同等重量能力和延迟。设置选择链接仅仅基于能力,而设置选择链接基于延迟;也就是说,只有延迟进行了优化。因此,指标选择路径优化延迟较低(更大的延迟)和高容量(较小的第二个任期)较低,反之亦然。总网络容量是通过使用低价值的最大化增加为代价的端到端延迟。然而,延迟还是优化虽然不明显的方式比能力和选择比单位Dijkstra算法的路由算法对延迟时统一标准算法优化能力。

在部分结果,我们简单的路由度量的(7)将尝试说明不同的影响路由算法的性能。这是最简单的改进多目标优化的修剪方法,提供大的多样性产生更好的吞吐量和端到端延迟与限制的修剪方法优化的性质。由此产生的算法还保留Dijkstra算法的快速收敛性和技术的优势相对较小的计算复杂度,但它仍然不提供全球最佳概念,只有达到帕累托最优。

如果我们假设,路径度量的能力逆路径的链接。这些都是指定的在下面。迪杰斯特拉最短路径时发现,这个和将被最小化,和它的逆矩阵(指定的下图)最大化: 自,,最大小于最小链接能力。因此,最大表明最优路径的能力。后者是最大化算法1通过最大化最小链接路径的能力。相反,在我们的算法中,一个量是最大化容量小于最小链接。所以我们可以推断,我们选择的指标也几乎导致最大化最小链路容量的能力允许的路径。因此,我们的指标是几乎和概念上可行路径容量以及路径延迟。最小化的路径延迟自然发生在一个简单的方式在使用(7)作为路由度量。

4所示。结果

我们模型WMN描述每个链接的链接速度或延迟能力和链接。在所有的实验中,在MATLAB 8.1编写仿真程序。实验装置的仿真分析是基于50代节点随机分布在一个区域的1000 * 1000²。随机分布是固定的,第一,为目的的算法之间的比较和仿真场景。网络拓扑结构确保节点覆盖范围是200米。因此有些节点的覆盖范围。分配的链路延迟(ms)和链路容量(Mbps)遵循均匀分布。这种特性使网络中链接的多样性和不影响结论的普遍性。

选择的拓扑,简略Dijkstra算法优化的结果所描述的算法1如图路径的能力1,这说明了产生1源节点和目的节点之间的最短路径15。优化路径容量是5.7 Mbps和相应的端到端延迟是86.8771毫秒。图2显示了简略的端到端延迟的结果优化使用相同的算法,但考虑的差异确定总体指标沿着一条路径。节点之间的最短路径1和图15所示的优化延迟是51.7216毫秒和相应的路径容量是1.4 Mbps。

修剪算法涉及到优化结果的能力和边界延迟取得了不同的延迟边界值和相同的源和目的节点上面使用。这些数字所示3和4值的路径延迟和优化能力和延迟绑定数据表示。延迟绑定减少、优化能力降低。

DWSM算法与实现和显然收益率相同的结果作为简略Dijkstra算法的优化能力和延迟,分别。的中间值正在尝试使用相同的源和目的节点和结果列在表吗1连同所有先前的结果比较的目的。我们注意到,获得的结果与DWSM远远优于修剪的延迟和能力。例如,我们获得相同的优化路径容量与修剪在75毫秒的延迟绑定,但更短的端到端延迟。这种情况下是描绘在图5与图相比4。此外,我们甚至可以用更少的链接获得更好的优化最短路径与DWSM(跳数)。这也是清晰的从图5从表,以及1。啤酒花确保减少的数量的最小化浪费网络资源,如计算能力。最后两个表中的行1显示结果DWSM之前相同的值但一双不同源目的地。

延迟和容量的值表示的数据是典型的WMNs可能会发现在1,18名字,但几个实例。延迟和容量逆值不相同的数量级,这就是为什么我们不能改变在一个广泛而得到不同的结果,即使是不同的路径。的值,区别只在0到0.3之间。所有链接延迟我们的拓扑除以5仍然提供了典型的延迟值但允许DWSM性能更好。它允许我们有所不同更自由地调查更全面地对多目标优化的影响。所有结果重复delay-modified拓扑和如表所示2。我们发现的值0和0.7之间,改变一些路径;也就是说,可能的范围增加了变异为更好的多目标优化。

在类比比较数据4和5、多目标修剪和DWSM算法相比可能会通过检查数据6和7的两个算法已经应用于不同的拓扑验证。这个新的拓扑有46个节点随机分布的均匀分布链接不同的样本实现和不同能力和延迟。节点也分布在1000 * 1000的一个领域²。DWSM算法的优点更加突出在这比较。在图7,DWSM和,我们获得较大容量的优化路径,较短的延迟,和链接或跳数少于修剪算法体现在图6在70毫秒的延迟绑定。

最优权重发现实验的帮助下表。很明显,通过适当加权路由目标按照网络环境和与性能方面,其重要性WMN路由性能的显著提高而简略和多目标修剪算法。原因是后者的机制算法几乎没有意识到感兴趣的多个性能目标。

5。结论

这项工作路径延迟的处理结合的性质和容量QoS措施通过最小化加权指标和通过Dijkstra-based算法(DWSM)在静态WMNs实现多目标路由。已经表明,DWSM算法的性能远优于简单Dijkstra-based修剪方面的延迟和能力,除了减少啤酒花的数量。

共同的价值观最典型的延迟和容量,权重因子的变化及其对DWSM性能的影响研究,发现不同在一个相当广泛可以提供多样化的同时优化的结果延迟和能力。这些结果平衡在文学评论的适用性有限加权和最小化的多目标优化路由由于容量逆和延迟有不同的数量级。

最后,值得注意的是尽管在WMN DWSM算法很容易变现环境和计算简单的优点,因此快速收敛,它不能提供的灵活性和质量解决方案获得更强大的,但计算气体等昂贵的技术。

利益冲突

作者宣称没有利益冲突有关的出版。