关键字 |
| NSGA-II算法、路由算法、网状网络,目标函数 |
介绍 |
| 随着网络技术的发展和基于网络的应用程序的日益普及,计算机网络正在广泛应用于科学研究、商业、教育、国防等领域[1,2]。它也作为一个重要的技术领域的工业流程管理(3,4,5,6,7,8,9,10)。几个工业组织如ISA[11],哈特[12]和无线个域网[13]一直在积极推动无线技术在工业自动化中的应用路由是一个通用的网络设计问题,最优分配的网络链路容量和线路的最佳选择是在合理的时间内确定。 |
| 如今,实时系统在许多不同的应用领域包括:汽车电子、航空电子设备、计算机网络、电信、空间系统、医学成像和消费电子产品。在所有这些领域中,快速的技术进步。接收数据的实时系统控制的环境,处理,并返回结果足够迅速地影响环境。系统是实时的,如果总操作的正确性不仅取决于它的逻辑正确性,而且在执行的时间。实时系统,以及他们的最后期限,是分类的结果错过了某事的最后期限: |
| •努力:错过了某事的最后期限是总系统故障。 |
| •公司:罕见的期限的失误都可以忍受,但可能降低系统的服务质量。结果的有用性是零后的最后期限。 |
| •软:截止日期后的结果的有用性降低,从而降低系统的服务质量。 |
| 因此,硬实时系统的目标是确保所有的最后期限,但对软实时系统的目标成为会议的某些子集期限以优化一些特定于应用程序的标准。优化取决于应用程序的特定标准,但一些典型的例子包括期限的数量最大化,最小化任务和最大化的迟到高优先级任务的数量满足他们的最后期限。 |
相关工作 |
| 实时应用程序在使用无线网络。[14]提出了一种实时全双工无线电设计使用信号反演和自适应取消。田他等[15]提出了一种实时通信协议,也就是速度。速度是一种高效且可伸缩的传感器网络的协议。沈等。[16]应用禁忌搜索算法在计算机网络路由和容量分配问题。 |
| 进化算法已被广泛用于许多领域如集群、图像处理和路由问题。遗传算法是一种进化算法启发从自然选择和遗传的过程。遗传算法获得了相当大的关注近年来为解决各种优化问题。林等。[17]基于遗传算法(GA)的方法应用于路由选择和流量分配能力。许多论文已经证明了基于GA方法的有效性在传感器网络(18、19、20、21)。[20]的工作集中在推导一个节能方案,满足所需的探测概率使用分布式遗传算法[21]。[20]的工作主要集中在寻找一个最佳的交通分配来提高多传感器网络的生命周期。基于GA方法层的传感器网络路由是在[22]提出,只有使用能源优化最大化网络的生命周期。追求[23]是一种路由协议,它使用多目标遗传算法找到路径在一个平面(集群)的无线传感器网络。 |
| 拓扑是一个最重要的参数影响吞吐量和网络的效率。网格是一种常见的拓扑结构,广泛应用于计算机网络。在网状拓扑中,每个网络节点(计算机和其他设备)是相互关联的。每个节点不仅发送自己的信号,还从其他节点传递数据。事实上真正的网状拓扑结构,每个节点连接到所有其他节点network.Fig。1显示了如何通过网状拓扑节点相连。网状拓扑的优点可以列为: |
| •拓扑的比较像公交车如果一位客户未能进行,其他的可以继续他们的工作。 |
| •数据可以同时从不同的设备。这种拓扑可以承受高流量。 |
| •扩张和修改拓扑可以在不影响其他节点完成 |
| 在本文中,我们提出了一种新的实时路由算法基于NSGA-II无线网状网络。Nondominated排序遗传算法(NSGA)是一种多目标进化算法是遗传算法的扩展为多个目标函数优化。 |
NSGA-II算法 |
| 的目标NSGA-II[24]算法是提高自适应人口的候选解决方案的帕累托面前受到一组目标函数。NSGA-II是一个以前的算法改进,由同一作者叫NSGA。NSGA算法等功能: |
| •这些算法并不认为精英主义策略的使用,防止失去良好的解决方案,因此可以加快搜索的一个关键因素。 |
| •额外的参数必须设置为确保多样性,主要是借助一个共享参数 |
| •NSGA适合连续优化问题 |
| 图2显示了NSGA-II过程寻找优化解决方案的流程图。NSGA-II算法首先随机人口。每个单独的人口被认为是一个染色体。每个染色体包含解决方案,我们正试图找到它的。染色体将评估目标函数到预期的答案是报道或达到最大迭代。制作解决方案之间的多样性,交叉和变异的过程中包含的算法。用帕累托前面方法NSGA-II各种解决方案。在这种方法中,人口将排序基于nondomination到每个面前。第一个前是完全非惯用设置在当前人口和第二战线正在由个人在第一前线。每个在每个方面排名(健身)将被分配。 Also another value is given to each chromosome based on which front they belong to. Individuals in first front are given a fitness value of 1 and individuals in second are assigned fitness value as 2. |
算法 |
| 路由被认为是一个复杂的非线性规划问题有许多限制条件,它是np完全(25、26)。路由问题的目标是找到的链接将包从发送节点到接收方。网络层的路由算法部分软件负责决定路线的每个数据包从源节点到目的地基于网络拓扑。这里的动力是提供一组NSGA-II帕累托最优解的算法和给它灵活地从这组选择最好的解决方案。我们的路由算法的设计目标: |
| 1。保持每个数据包的平均延迟或消息低于给定的水平 |
| 2。保持理想的可靠性在整个网络 |
| 计算机网络可以建模为一个无向图G = (N, L)的集节点N, L代表计算机网站的链接和通信电缆。下面的图显示了一个示例的一个网络图模型。 |
| 一个样例染色体以上网络在我们的算法如图4所示。路径(路径)是由清单编码节点从源到目的地的基于网络的拓扑结构。 |
| 对可靠性指标,我们使用ETX[27]计算路径的可靠性。ETX被定义为预期的传输(包括重传)对于一个成功的端到端数据转发和敌手承认。下面的表达式显示了如何计算的ETX度量路径: |
 |
| •浮点除:远期交货率测量的概率是一个数据包成功到达收件人 |
| •rdv:反向交货率的概率是ACK数据包成功接收端到端延迟是衡量以下方程: |
 |
| 在我们的方法中,事业的真正的时机,如果延迟时间超过了最长时间的解决方案被认为是失败了。 |
| 确定染色体生存和繁衍后代的能力,情商Eq。(1)和(2)作为目标函数。当我们应用气体n目标优化问题,我们必须评估n的值目标函数为每个解决方案。使用加权和客观评价染色体。的方式将目标函数的值中的每个字符串x一代的健身价值是将两个目标函数如下: |
 |
| •Fi健身价值的染色体数量(我) |
| •W1和W2的值在0和1之间(0 < W1 W2 < 1) |
仿真结果 |
| 提出的路由算法是基于NSGA-II算法及其应用是通过网状网络实时优化路由。提出的处理方法是在上面的部分中解释的那样,现在,在本节中,我们给出了该系统的实验结果的算法在MATLAB中实现。MATLAB是数值计算的高级语言和交互式环境,可视化和编程。图5显示了主要类开发的实现方法。类描述为如下: |
| •拓扑类开发网无线网络。 |
| •运行类是用于控制真正的计时系统 |
| •操作类负责控制路由算法,客户喜欢发送和接收状态 |
| 表1显示了结果的对比NSGA-II算法和特设距离向量(AODV)的需求。该算法是评估在不同的场景和节点。实验结果证明,NSGA-II可以在更少的时间进行比较AODV。 |
| 下面的图中显示通过迭代平均延迟时间。AODV和NSGA-II算法之间的比较。平均延迟时间提出NSGA-II小于AODV路由算法。这个因素展示了数据包丢失和包转发形成是减少NSGA-II实时路由算法。 |
| NSGA-II参数的值被分配为: |
| •生成的数量= 10 |
| •=单点交叉方法 |
| •变异方法=一些字符串翻转 |
| •人口= 100 |
结论和未来的工作 |
| 在本文中,我们研究了实时无线网状网络的路由问题。我们的目标是优化可靠性和端到端延迟。该方法是基于NSGA-II算法是一个多目标进化算法和该算法的目标是改善自适应人口的候选解决方案的帕累托面前受到一组目标函数。进化算法使用一个进化过程与代理人的运营商包括选择、遗传交叉,基因突变。我们实现了在MATLAB算法。进行了比较NSGA-II实时特设按需距离矢量路由算法和(AODV)。在结果中观察到实验分析: |
| •执行时间寻找理想的AODV算法中路径 |
| •减少发送数据包的延迟时间 |
| •在AODV进行比较,更少数量的丢失和放下包被观察到 |
|
表乍一看 |
 |
| 表1 |
|
|
数据乍一看 |
|
|
|
引用 |
- l . Baccouche和h . Eleuch Rt-Dbp:多优先级分配方案实时任务调度”,Appl.Math。正,科学。,Vol. 6, No. 11, pp. 382–388 (2012).
- 一个。Jemai, A . Mastouri和h . Eleuch“禁忌搜索算法在计算机网络路由和容量分配问题”,达成。数学。正,科学。5卷,第3号,第667 - 655页(2011)。
- Andreas实证分析”,最近在无线工业通信和新兴的话题:一个选择,“IEEE反式。工业信息,2007年。
- 迪克·卡罗,无线网络为工业自动化、ISA出版社,2004年。
- j .歌曲,汉族,a . k . Mok d . Chen m·卢卡斯·m·尼克松和w·普拉特,“WirelessHART:应用无线技术在实时工业浮选控制,“在区域贸易协定,2008年。
- 亚历桑德罗·D 'Innocenzo Rajeev Alur,卡尔·h·约翰逊,乔治J。帕帕斯,维斯基拉,“种控制网络的建模和分析,在区域贸易协定,2009年。
- 维斯基拉,拉杰夫Alur,阿尔夫j .法甲和卡尔·h·约翰逊,“可伸缩的无线网络控制系统的调度算法,”的情况下,2009年。
- Pablo Soldati Joonas Pesonen,张叫海波,米凯尔·约翰逊,”方法和工具controller-networking WirelessHART合作设计,“在ETFA, 2009。
- Shahid Raza Adriaan Slabbert, Thiemo沃伊特和案发Landern¨,“无线hart协议的安全考虑,”在ETFA, 2009。
- 加布里埃尔Fiore也好Ercoli,阿尔夫j .伊萨克松案发Landern¨,和玛丽亚Domenica Di Benedetto”多次反射多通道无线控制调度WirelessHART网络,“ETFA, 2009。
- “是”,http://www.isa.org/。
- “HART通信”,http://www.hartcomm.org。
- “无线个域网联盟”,http://www.zigbee.org
- Jain, M。,Choi, J. I., Kim, T., Bharadia, D., Seth, S., Srinivasan, K., ... & Sinha, P. (2011, September). Practical, real-time, full duplex wireless. In美国17年移动计算和网络国际会议(页301 - 312)。ACM。
- Coello, C.A.C.拉蒙特,G.B.,Van Veldhuisen, D.A.: Evolution-ary Algorithms for Solving Multi-Objective Problems. Springer,Berlin (2007)
- 彭剑沈、福永徐和郑,”研究无线传感器网络中的关键pre-distribution方案:BROSK中(使用WSNet)”、电脑和运筹学,32卷,11号,第2800 - 2785页(2005)。
- 林肖惠,Yu-Kwong郭,文森特K.N. Lau)“基于遗传算法的方法路线选择和容量流任务”,计算机通信,26卷,第974 - 961页(2003)
- Ataul巴里,Shamsul Wazed, Arunita Jaekel, Subir Bandyopadhyay,“基于遗传算法的方法对节能溃败ing)传感器网络”,特设网络,第七卷,2009年,665 - 676
- Navrati Saxena,阿布罗伊,Jitae Shin,“追求:传感器算法节能路由协议”,无线通信和移动计算杂志,2009年,vol.9,没有。3,417 - 426
- x y,刘,“节能寿命最大化和睡眠调度支持多传感器数据融合和QoS网”,信号处理,2007年,Vol.87 (12), 2949 - 2964
- 问:秋问:吴d·伯恩斯,d . Holzhauer“终生意识到资源
- 管理传感器网络使用分布式遗传算法”,ISLPED’06, ACM出版社,纽约,纽约,2006年,191 - 196
- EkbataniFard, g . Hossein et al。“基于多目标遗传算法的方法在层的无线传感器网络节能QoS-routing。”无线普适计算(ISWPC), 2010年第五届IEEE国际研讨会。IEEE 2010。
- Navrati Saxena,阿布罗伊,Jitae Shin,“追求:传感器算法节能路由协议”,无线通信和移动计算杂志,2009年,vol.9,没有。3,417 - 426
- k . Deb普拉塔普,美国Agarwal, t . Meyarivan。一个快速和精英多目标遗传算法:Nsga-ii。进化计算IEEE 6(2): 182 - -197, 2002年4月。
- 光明,黄Chengbo Shaobin詹,鑫Lu和Yunting Lu”排名选择遗传算法为基础能力流作业”,通信计算机和信息科学,107卷,第107 - 97页(2010)。
- 埃米利奥C.G.威利,马可Mellia、埃米利奥Leonardi马可Ajmone Marsan,“Lagrangean放松方法QoS网络CFA问题”,国际期刊的电子和通信(AEU), 63卷,第753 - 743页(2009)。
- 道格拉斯·s·j·库托De丹尼尔Aguayo,约翰•Bicket和罗伯特·莫里斯,“高通量路径度量种无线路由”,无线网络,2005年,Vol.11 (4)
|
菜单
