论文部分内容阅读
【摘要】蚁群算法是近年发展起来的,受自然界蚂蚁搜寻食物行为启发得到的并行优化算法。本文采用蚁群算法作为低压电力载波网络的自适应路由算法,使其自动搜索最优路径,使整个低压电力载波网络成为一个稳定可靠的网络系统。
【关键词】蚁群算法 电力载波 路由算法
【中图分类号】G434 【文献标识码】A 【文章编号】1009-9646(2008)08-0188-02
The researching of the Low-voltage power line carrier adaptive routing algorithm owning to the ACA
WangLi Yang Chun-yan Chen yue
(1.HLJ Vocztional Institute of information technology Haerbin 150086 2. Armor Techique Institute of PLA ChangChun 130117 3.Harbin Normal UniversityHaerbin 150080)
ABSTRACT: The ACA is a Parallel Optimization Algorithm, developed in recent years inspired by the nature searching food of Ant.We made the ACA as the Adaptive routing algorithm of the Low-voltage power line carrier. It will Automatic search the optimal path and made the whole Low-voltage power line carrier network to be a Stable and reliable network.
Key Words:ant colony algorithm(ACA);Power line carrier ;the Routing algorithm
基于低压电力载波的集抄网络系统由于是利用家庭电力线来传送数据,因此因节省了大量的布线而具有广阔的发展空间。但由于我国低压配电网络具有高衰变,高噪声,高时变等特殊特性,对于远端节点只能通过中继来完成。然而以往的固定中继算法虽然中继深度可达5级,但往往由于无限枚举方式时间过长而陷入死循环。因此,本文采用蚁群算法来自动的搜索网络节点。该算法是一种性能优良的启发式随机优化算法,采用正反馈机制实现分布式全局优化,通过信息素的不断更新达到最终收敛于最优路径上,算法无需进行大量的概率计算或建立复杂的数学模型来进行系统预测,可应用于通信网络中的组合优化求解,大大提高系统的可靠性和抗干扰能力。
1 蚁群算法的原理
蚁群算法是模仿真实世界蚁群的行为而提出的。为了说明蚁群算法的原理,先从蚂蚁搜索食物的过程谈起。像蚂蚁、蜜蜂等群居昆虫,虽然单个昆虫的行为极其简单,但是由单个简单的个体所组成的群体却表现出极其复杂的行为。真实的蚂蚁在没有视觉的情况下,能找到从食物源到蚁巢的最短路径。同时,它们能适应环境的改变,例如,由于原最短路径中出现障碍物时能够重新发现一条新的最短路径。究其原因是因为蚂蚁个体之间是通过一种称为信息素(pheromon或stigmergy)的物质进行信息传递的。蚂蚁在运动过程中,能够在它所经过的路径上留下该物质,而且蚂蚁在运动过程中能够感知这种物质的存在及其强度,并以此指导自己的运动方向,蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流进行路径的最优选择从而达到搜索食物的目的。
2 蚁群算法的实现步骤
蚁群算法的寻优过程是一个递推迭代过程,其实现步骤可伪代码表述如下。
Ant-cycle system程序的伪代码(设NCMAX是定义好的循环次数):
①初始化:Set t=0. NC=0,每条边上的,随机放置m个蚂蚁到n个城市上;
②令s=1 (s是tabu list的下标) For k=1 to m do把第k个蚂蚁的初始城市号码放置到tabu k(s)中;
③重复本步骤直到tabu list被填满(这个步骤重复n-1次)
Set s=s+l
For k=1 to m do
根据概率来选择下一步应该到达的城市j.在时刻t蚂蚁k在城市i=tabu k(s-1),将第k个蚂蚁移到城市j,并将j插入到tabu k(s)中;
④For k=1 to m do
将第k个蚂蚁从城市tabu k(n)移到tabu k (1),计算第k个蚂蚁的总路径长度Lk,更新找到的最短路径。
For k=1 to m do更新边上的信息素浓度;
⑤对每一条边计算
Set t=t+nSet NC=NC+1Set
⑥如果(NC那么,清空所有的tabu list转到第②步 否则打印出最短路径,终止整个程序。
3 基于蚁群算法的自适应路由算法问题描述
对于任意链路,定义四种度量,如下所示(表示正实数集,表示非负实数集):(1)延时函数delay(e):,网络延时是指数据包在网络上传输平均所需的时间;(2)延时抖动函数delay-jitter(e):,网络抖动是指数据包传输时由于电力载波高时变,高噪声所导致的传输时间长短的变化;以上两个函数是可能导致网络节点丢失的因素;(3)带宽函数bandwidth(e):,网络带宽是减少节点丢失的决定因素;(4)费用函数cost(e):;
对于任一网络节点,定义三种度量,如下所示(表示正实数集,表示非负实数集):(1)延时函数delay(n):;(2)延时抖动函数delay_jitter(n):;(3)包丢失率函数packet_loss(n):,数据包在传送过程中有可能损坏或被丢失/丢弃,如果丢失率过高将会使得数据受到明显损害。
给出一个路由请求L,即建立给定源节点(集中器与目的节点间的路由),路由算法如果能够找到一条最优路径,即求mincost=cost(e),同时满足下述要求,此路由请求L就可接受;
(1)带宽约束要求:bandwidth(e)≥B,在L的路由的每条链路e上;
(2)延时约束要求:,在L的路由上;
(3)延时抖动约束要求:
,在L的路由上;(4)包丢失率约束要求:,在L的路由的每个节点n上,其中,B,D, DJ和PL分别代表网络要求的带宽、延时、延时抖动和包丢失率约束:EL是L的路由的链路集合,VL是L的路由的节点集合。
4 基于蚁群算法的自适应路由算法仿真
考虑小型网络拓扑,如图1,对其进行仿真。假定有三个单播路由请求(1,6),(2,6)和(3,8),要求:B=70,D=8,DJ=5,PL=0.0001.算法中基本参数选择为:,,。图1为网络模型的各个节点及边的连线和位置图。通过用NS2仿真软件得出的结果由表1可以看出,采用蚁群算法对不稳定的网络进行路由选择,可以对全局进行优化,找到全局最优解。
5 结语
本文通过算例验证了所提出的算法能够较好的解决载波网络中的路由问题。但是,不足之处在于,本文所引用的算例是较小的网络,还有待在较大的网络上进行研究验证。
参考文献
[1] 汤效军.电力线载波通信技术的发展及特点.电力系统通信,2003(1):47-51.
[2] 张纪会.徐心和,一种新的进化算法:蚁群算法.系统工程理论与实践,1999,19(3):84-87.
[3] 汪镭,吴启迪.蚁群算法在连续空间寻优问题求解中的应用.控制与决策,2003(2):23-27.
[4] 许毅,李腊元.基于蚁群算法的QoS多播路由优化算法.计算机应用,2005,3(1):183-185.
[5] 胡小兵,黄席抛,张著洪.一种新的自适应蚁群算法及其应用.计算机仿真,2004,6(20):108-111.
[6] Colorni A,Dorigo M, Maniezzo V Ant system for job-shop scheduling.Belgian Journal of Operations Research,Statistics and Computer Science,1994,34(1):39-54.
[7] Dorigo M,Maniezzo v, Colorni A. i he ant sysiem: optimization by a colony of cooperating agents.IEEE Transactions on Systems, Man,and Cybernetics-Part B,1996,26(1):28-41.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
【关键词】蚁群算法 电力载波 路由算法
【中图分类号】G434 【文献标识码】A 【文章编号】1009-9646(2008)08-0188-02
The researching of the Low-voltage power line carrier adaptive routing algorithm owning to the ACA
WangLi Yang Chun-yan Chen yue
(1.HLJ Vocztional Institute of information technology Haerbin 150086 2. Armor Techique Institute of PLA ChangChun 130117 3.Harbin Normal UniversityHaerbin 150080)
ABSTRACT: The ACA is a Parallel Optimization Algorithm, developed in recent years inspired by the nature searching food of Ant.We made the ACA as the Adaptive routing algorithm of the Low-voltage power line carrier. It will Automatic search the optimal path and made the whole Low-voltage power line carrier network to be a Stable and reliable network.
Key Words:ant colony algorithm(ACA);Power line carrier ;the Routing algorithm
基于低压电力载波的集抄网络系统由于是利用家庭电力线来传送数据,因此因节省了大量的布线而具有广阔的发展空间。但由于我国低压配电网络具有高衰变,高噪声,高时变等特殊特性,对于远端节点只能通过中继来完成。然而以往的固定中继算法虽然中继深度可达5级,但往往由于无限枚举方式时间过长而陷入死循环。因此,本文采用蚁群算法来自动的搜索网络节点。该算法是一种性能优良的启发式随机优化算法,采用正反馈机制实现分布式全局优化,通过信息素的不断更新达到最终收敛于最优路径上,算法无需进行大量的概率计算或建立复杂的数学模型来进行系统预测,可应用于通信网络中的组合优化求解,大大提高系统的可靠性和抗干扰能力。
1 蚁群算法的原理
蚁群算法是模仿真实世界蚁群的行为而提出的。为了说明蚁群算法的原理,先从蚂蚁搜索食物的过程谈起。像蚂蚁、蜜蜂等群居昆虫,虽然单个昆虫的行为极其简单,但是由单个简单的个体所组成的群体却表现出极其复杂的行为。真实的蚂蚁在没有视觉的情况下,能找到从食物源到蚁巢的最短路径。同时,它们能适应环境的改变,例如,由于原最短路径中出现障碍物时能够重新发现一条新的最短路径。究其原因是因为蚂蚁个体之间是通过一种称为信息素(pheromon或stigmergy)的物质进行信息传递的。蚂蚁在运动过程中,能够在它所经过的路径上留下该物质,而且蚂蚁在运动过程中能够感知这种物质的存在及其强度,并以此指导自己的运动方向,蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流进行路径的最优选择从而达到搜索食物的目的。
2 蚁群算法的实现步骤
蚁群算法的寻优过程是一个递推迭代过程,其实现步骤可伪代码表述如下。
Ant-cycle system程序的伪代码(设NCMAX是定义好的循环次数):
①初始化:Set t=0. NC=0,每条边上的,随机放置m个蚂蚁到n个城市上;
②令s=1 (s是tabu list的下标) For k=1 to m do把第k个蚂蚁的初始城市号码放置到tabu k(s)中;
③重复本步骤直到tabu list被填满(这个步骤重复n-1次)
Set s=s+l
For k=1 to m do
根据概率来选择下一步应该到达的城市j.在时刻t蚂蚁k在城市i=tabu k(s-1),将第k个蚂蚁移到城市j,并将j插入到tabu k(s)中;
④For k=1 to m do
将第k个蚂蚁从城市tabu k(n)移到tabu k (1),计算第k个蚂蚁的总路径长度Lk,更新找到的最短路径。
For k=1 to m do更新边上的信息素浓度;
⑤对每一条边计算
Set t=t+nSet NC=NC+1Set
⑥如果(NC那么,清空所有的tabu list转到第②步 否则打印出最短路径,终止整个程序。
3 基于蚁群算法的自适应路由算法问题描述
对于任意链路,定义四种度量,如下所示(表示正实数集,表示非负实数集):(1)延时函数delay(e):,网络延时是指数据包在网络上传输平均所需的时间;(2)延时抖动函数delay-jitter(e):,网络抖动是指数据包传输时由于电力载波高时变,高噪声所导致的传输时间长短的变化;以上两个函数是可能导致网络节点丢失的因素;(3)带宽函数bandwidth(e):,网络带宽是减少节点丢失的决定因素;(4)费用函数cost(e):;
对于任一网络节点,定义三种度量,如下所示(表示正实数集,表示非负实数集):(1)延时函数delay(n):;(2)延时抖动函数delay_jitter(n):;(3)包丢失率函数packet_loss(n):,数据包在传送过程中有可能损坏或被丢失/丢弃,如果丢失率过高将会使得数据受到明显损害。
给出一个路由请求L,即建立给定源节点(集中器与目的节点间的路由),路由算法如果能够找到一条最优路径,即求mincost=cost(e),同时满足下述要求,此路由请求L就可接受;
(1)带宽约束要求:bandwidth(e)≥B,在L的路由的每条链路e上;
(2)延时约束要求:,在L的路由上;
(3)延时抖动约束要求:
,在L的路由上;(4)包丢失率约束要求:,在L的路由的每个节点n上,其中,B,D, DJ和PL分别代表网络要求的带宽、延时、延时抖动和包丢失率约束:EL是L的路由的链路集合,VL是L的路由的节点集合。
4 基于蚁群算法的自适应路由算法仿真
考虑小型网络拓扑,如图1,对其进行仿真。假定有三个单播路由请求(1,6),(2,6)和(3,8),要求:B=70,D=8,DJ=5,PL=0.0001.算法中基本参数选择为:,,。图1为网络模型的各个节点及边的连线和位置图。通过用NS2仿真软件得出的结果由表1可以看出,采用蚁群算法对不稳定的网络进行路由选择,可以对全局进行优化,找到全局最优解。
5 结语
本文通过算例验证了所提出的算法能够较好的解决载波网络中的路由问题。但是,不足之处在于,本文所引用的算例是较小的网络,还有待在较大的网络上进行研究验证。
参考文献
[1] 汤效军.电力线载波通信技术的发展及特点.电力系统通信,2003(1):47-51.
[2] 张纪会.徐心和,一种新的进化算法:蚁群算法.系统工程理论与实践,1999,19(3):84-87.
[3] 汪镭,吴启迪.蚁群算法在连续空间寻优问题求解中的应用.控制与决策,2003(2):23-27.
[4] 许毅,李腊元.基于蚁群算法的QoS多播路由优化算法.计算机应用,2005,3(1):183-185.
[5] 胡小兵,黄席抛,张著洪.一种新的自适应蚁群算法及其应用.计算机仿真,2004,6(20):108-111.
[6] Colorni A,Dorigo M, Maniezzo V Ant system for job-shop scheduling.Belgian Journal of Operations Research,Statistics and Computer Science,1994,34(1):39-54.
[7] Dorigo M,Maniezzo v, Colorni A. i he ant sysiem: optimization by a colony of cooperating agents.IEEE Transactions on Systems, Man,and Cybernetics-Part B,1996,26(1):28-41.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”