论文部分内容阅读
无线传感器网络WSN是由许多传感器节点协同组织起来的，具有无线通信、数据采集和处理、协同合作等功能的网络系统。它的节点可以随机或者特定地布置在目标环境中，它们之间通过特定的协议自组织起来，能够获取周围环境的信息并且相互协同工作完成特定任务。蚁群算法在求解复杂优化问题方面具有一定的优势，本文首先对基本蚁群算法进行了改进。仿照自然界种群中个体的多样性，在蚁群优化算法中引入了群体多样性选路策略。使ACO算法的全局搜索能力和收敛速度得到了增强，可提高解的质量。根据无线传感器网络所具有能量受限、网络节点不断变化的特性，利用蚁群算法在无线传感器网络动态路由中求解最佳路径。
一、 蚁群算法的改进
（一） 基本蚁群算法
基本蚁群算法可以简单表述如下：初始化，将m个蚂蚁随机放在n个城市上，城市间的每一条边都有初始化信息素，每个蚂蚁的禁忌表Tabu（k）的第一个元素设置为其初始城市。然后每只蚂蚁开始选路，即选择下一步要去的城市。在选路中蚂蚁依据概率函数选择将要去的城市，这个概率取决于城市间的距离和信息素的强度。在选路中蚂蚁依据概率函数
p■■=■0， 其它 j?缀allowed■ （1）
选择将要去的城市，这个概率取决于城市间的距离和信息素的强度。其中?子■t表示边弧（i，j）上信息素的强度（i为出发城市，j为到达城市）；?浊■表示城市间距离因子，通常取值为1/dij（dij为两个城市间的距离）；α表示信息素在选择概率上的作用；β是指路径长度在选择概率上的作用。在n次循环后，所有蚂蚁的禁忌表都已填满，此时计算每个蚂蚁走过的路径的长度，并找到最短路径保存，记录此路径并更改信息素。重复这一过程直至达到最大周游值结束。
信息素更新的公式是：
?子ij（t+n）=ρ?子ij（t）+?荭?子ij . （2）
?荭?子ij=■ ?荭?子■■ （3）
其中?荭?子ij表示在某条边上的累加新增信息素的和，ρ表示信息素消散的等级，?荭?子■■表示t和t+n之间第k个蚂蚁在此边上留下的信息素的数量。?荭?子■■的计算公式为：
?荭?子■■= ■，如果在t和t+n之间第k个蚂蚁使用此边0，其它 （4）
其中Q 为常量，Lk为第k个蚂蚁周游的路径长度。
（二） 改进的蚁群算法
1、群体行为多样性策略
我们在基本的蚁群算法中引入了群体行为多样性，群体中的每个蚂蚁选路的概率函数p中的参数α、β值并非完全相同，而且还将在算法每轮循环执行后不断变化。在这种算法中蚂蚁的行为策略是多样性的。
我们将改进的蚁群算法叫做HSIV算法。在此算法的每轮循环中，修改得到最优解的蚂蚁的α、β参数，渐进加重信息素在选路的概率函数p中的作用，相应减小距离在选路的概率函数p中的作用，我们称这种方法为奖励机制,同时修改得到最差解得的。这种机制可以在蚁群中实现不同选路策略的蚂蚁协同工作。
2、群体多样性算法HSIV算法实现
我们在算法中以文献[2]提出的算法HBACA模型为基础，在算法中定义了四种行为模式：
（1） 使公式（1）中的参数α为0，参数β为0。
（2） 按公式（1）进行选路。
（3） 按个体差异策略进行选路，提高α的值，增大信息素在选路中的作用；同时降低β的值，减小距离因子在选路中的作用。
将四种策略按0.05：0.1：0.4：0.45的比例来设置蚁群的行为策略，算法的性能最好。
HSIV算法可描述如下：
步骤1：初始化各参数;
步骤2：将m个蚂蚁按照不同行为策略随机放到n个城市
步骤3：for 每个蚂蚁k
Repeat
按选路策略选择下个城市；将蚂蚁k所在的城市放到蚂蚁k的禁忌表
Until 禁忌表满 ； End for
步骤4：选择走过路径最短的蚂蚁min； 根据禁忌表计算蚂蚁min 的路径长度Lk；
更新当前最短路径Lmin；
步骤5：
将当前最短路径上的每条边上的信息素按公式（3）更新?荭?子i
if (ANT[min].alpha>=5)ANT[min].alpha：= ANT[min].alpha+5；
elseANT[min].alpha:=5；ANT[min].beta：=1；
步骤6：
if（NC<预定迭代次数）and（无退化行为）then 清空禁忌表，回到步骤3
else 打印最短路径 ；算法结束
二、无线传感器网络
（一）无线传感器网络的概念
无线传感器网络由多个功能相同或不同的无线传感器节点组成，每个节点在网络中可以充当数据采集者、数据中转站或类头节点。作为数据采集者，节点可以收集周围环境的数据，通过通信路由协议直接或间接将数据传输给基站或网关节点；作为数据中转站，节点除了完成采集任务外，还要接收邻居节点的数据，将其转发给距离基站更近的邻居节点或者直接转发到基站或网关节点；作为类头节点，节点负责收集该类内所有节点采集的数据。
（二）无线传感器网络的相关数据计算
在传感网络中，称两个节点是相邻的，当且仅当此两个节点在彼此有效通信距离之内。假定相邻节点之间只存在一条链路，则传感网络的拓扑结构可以看作是一个无向图G=（V，E），其中V为所有传感节点构成的顶点集合，E为所有链路构成的边集合。由传感网络节点部署的稠密性，本文假定图G是连通的。
定义1 （相邻节点）：设节点w和节点u在彼此有效通信距离之内。称为相邻节点，简称相邻。
定义2（物理距离）：设节点w 和节点u相邻，则w到u的实际距离，称为w和u的物理距离，表示为：L。其中w（x，y）是w的坐标，u（x，y）是u的坐标。L=sqrt（（w.x-u.x）2+（w.y-u.y）2）
定义3（临界电压）使传感器能够正常工作的最小电压值称为临界电压。
定义4（通信距离）：设节点w和节点u相邻，称WL为w和u的通信距离。WL=K?觹（L）2
其中，K为比例系数，K=1/（V0-Vmin），其中V0是传感器当前工作电压值，Vmin是临界电压且Vmin是常量。公式WL=K*（L）2考虑到节点间传播信息所消耗的能量与节点间距离的平方成正比例，并且考虑了K值的收敛速度。
1、每节点物理位置坐标：可以人为设置或由全球定位系统（GPS）获得。
2、物理距离：设有两个节点w，u 是相邻节点。w（x，y）是w 的坐标，u（x，y）是u 的坐标。L=sqrt（（w.x-u.x）2+（w.y-u.y）2）。
3、V0：V0是传感器节点的当前工作电压值（初始化时为3V）。当系统运行时，V0是由无线传感器节点定时向汇节点发送自身的电压值。
4、Vmin：Vmin是临界电压值（初始化时为2.7V）。
5、通信距离：WL= K*（L）2，K=1/（V0-Vmin）。
三、改进的蚁群算法在无线传感器网络中的应用
（一） 算法的基本思路
（1）通过一组“蚂蚁”人工代理遍历网络节点来产生Sink节点到达目标节点的最优路径；（2）通过蚂蚁的局部搜索以递增的方式来建立路径；（3）使用试探获得的信息来指导各个蚂蚁的搜索，使各路径趋于汇合，最终达到数据汇集的目的。（4）算法不需要网络中各传感节点维护全局网络状态；（5）蚂蚁不必遍历节点拓扑图中的所有节点。因而具备更好的可伸缩性。测试结果也表明新路由算法具有较好的路由性能。
（二）算法实现
1、初始化过程
Q=200；α=1；β=4；ρ=0.5；iAntCount=20；
iMoteCount=30；iItCount=500；将m只蚂蚁置于起始节点。
2、初始化网络节点拓扑图；
3、循环开始并设置最大循环次数。
4、所有蚂蚁依次遍历网络节点；
5、计算每个蚂蚁的路径长度，将最优解存储到全局变量中。
6、对每个蚂蚁更新信息素。
7、重复3，直到输出结果。
四、结论
不同的参数对最优解和循环次数有着不同的影响。算法中对蚂蚁个数要求有较宽松的范围，取节点的个数即可。参数α对循环次数不敏感，对解路径的长度影响较大。参数β和Q正相反，对解路径影响不大，但是对循环次数反应较为灵敏。因此在传感器网络的路由问题中应该着重留意。对于无线传感器网络中的路由问题，蚁群算法可以在较少的循环之内取得比较满意的最优解或次优解。由于改进的蚁群算法不要求蚂蚁必须遍历所有的网络节点便可以找到最优或次优解，而且收敛速度较快，当数据采集区域内分布着较多的节点时，可以较好地适应实时的数据传输要求。
参考文献：
[1]周春光，梁艳春.计算智能.吉林大学出版社，2001.
[2]胡小兵，黄席樾.基于混合行为蚁群算法的研究[J].控制与决策，2004.
[3] Dorige M，Maniezzo V，Colorni A. Ant system： Optimization by a colony of cooperating agents.IEEE Trans. on SMC. 1996.
（作者简介：赵艳伟（1968-），女，汉族，吉林长春人，副教授，硕士学历，吉林工商学院信息工程分院，研究方向：算法及其应用。）
注：本文是吉林省教育厅“十一五”科学技术研究项目,项目名称：改进的蚁群算法在优化问题上的应用，项目编号：吉教科合字[2008]第411号。
一、 蚁群算法的改进
（一） 基本蚁群算法
基本蚁群算法可以简单表述如下：初始化，将m个蚂蚁随机放在n个城市上，城市间的每一条边都有初始化信息素，每个蚂蚁的禁忌表Tabu（k）的第一个元素设置为其初始城市。然后每只蚂蚁开始选路，即选择下一步要去的城市。在选路中蚂蚁依据概率函数选择将要去的城市，这个概率取决于城市间的距离和信息素的强度。在选路中蚂蚁依据概率函数
p■■=■0， 其它 j?缀allowed■ （1）
选择将要去的城市，这个概率取决于城市间的距离和信息素的强度。其中?子■t表示边弧（i，j）上信息素的强度（i为出发城市，j为到达城市）；?浊■表示城市间距离因子，通常取值为1/dij（dij为两个城市间的距离）；α表示信息素在选择概率上的作用；β是指路径长度在选择概率上的作用。在n次循环后，所有蚂蚁的禁忌表都已填满，此时计算每个蚂蚁走过的路径的长度，并找到最短路径保存，记录此路径并更改信息素。重复这一过程直至达到最大周游值结束。
信息素更新的公式是：
?子ij（t+n）=ρ?子ij（t）+?荭?子ij . （2）
?荭?子ij=■ ?荭?子■■ （3）
其中?荭?子ij表示在某条边上的累加新增信息素的和，ρ表示信息素消散的等级，?荭?子■■表示t和t+n之间第k个蚂蚁在此边上留下的信息素的数量。?荭?子■■的计算公式为：
?荭?子■■= ■，如果在t和t+n之间第k个蚂蚁使用此边0，其它 （4）
其中Q 为常量，Lk为第k个蚂蚁周游的路径长度。
（二） 改进的蚁群算法
1、群体行为多样性策略
我们在基本的蚁群算法中引入了群体行为多样性，群体中的每个蚂蚁选路的概率函数p中的参数α、β值并非完全相同，而且还将在算法每轮循环执行后不断变化。在这种算法中蚂蚁的行为策略是多样性的。
我们将改进的蚁群算法叫做HSIV算法。在此算法的每轮循环中，修改得到最优解的蚂蚁的α、β参数，渐进加重信息素在选路的概率函数p中的作用，相应减小距离在选路的概率函数p中的作用，我们称这种方法为奖励机制,同时修改得到最差解得的。这种机制可以在蚁群中实现不同选路策略的蚂蚁协同工作。
2、群体多样性算法HSIV算法实现
我们在算法中以文献[2]提出的算法HBACA模型为基础，在算法中定义了四种行为模式：
（1） 使公式（1）中的参数α为0，参数β为0。
（2） 按公式（1）进行选路。
（3） 按个体差异策略进行选路，提高α的值，增大信息素在选路中的作用；同时降低β的值，减小距离因子在选路中的作用。
将四种策略按0.05：0.1：0.4：0.45的比例来设置蚁群的行为策略，算法的性能最好。
HSIV算法可描述如下：
步骤1：初始化各参数;
步骤2：将m个蚂蚁按照不同行为策略随机放到n个城市
步骤3：for 每个蚂蚁k
Repeat
按选路策略选择下个城市；将蚂蚁k所在的城市放到蚂蚁k的禁忌表
Until 禁忌表满 ； End for
步骤4：选择走过路径最短的蚂蚁min； 根据禁忌表计算蚂蚁min 的路径长度Lk；
更新当前最短路径Lmin；
步骤5：
将当前最短路径上的每条边上的信息素按公式（3）更新?荭?子i
if (ANT[min].alpha>=5)ANT[min].alpha：= ANT[min].alpha+5；
elseANT[min].alpha:=5；ANT[min].beta：=1；
步骤6：
if（NC<预定迭代次数）and（无退化行为）then 清空禁忌表，回到步骤3
else 打印最短路径 ；算法结束
二、无线传感器网络
（一）无线传感器网络的概念
无线传感器网络由多个功能相同或不同的无线传感器节点组成，每个节点在网络中可以充当数据采集者、数据中转站或类头节点。作为数据采集者，节点可以收集周围环境的数据，通过通信路由协议直接或间接将数据传输给基站或网关节点；作为数据中转站，节点除了完成采集任务外，还要接收邻居节点的数据，将其转发给距离基站更近的邻居节点或者直接转发到基站或网关节点；作为类头节点，节点负责收集该类内所有节点采集的数据。
（二）无线传感器网络的相关数据计算
在传感网络中，称两个节点是相邻的，当且仅当此两个节点在彼此有效通信距离之内。假定相邻节点之间只存在一条链路，则传感网络的拓扑结构可以看作是一个无向图G=（V，E），其中V为所有传感节点构成的顶点集合，E为所有链路构成的边集合。由传感网络节点部署的稠密性，本文假定图G是连通的。
定义1 （相邻节点）：设节点w和节点u在彼此有效通信距离之内。称为相邻节点，简称相邻。
定义2（物理距离）：设节点w 和节点u相邻，则w到u的实际距离，称为w和u的物理距离，表示为：L
定义3（临界电压）使传感器能够正常工作的最小电压值称为临界电压。
定义4（通信距离）：设节点w和节点u相邻，称WL
其中，K为比例系数，K=1/（V0-Vmin），其中V0是传感器当前工作电压值，Vmin是临界电压且Vmin是常量。公式WL
1、每节点物理位置坐标：可以人为设置或由全球定位系统（GPS）获得。
2、物理距离：设有两个节点w，u 是相邻节点。w（x，y）是w 的坐标，u（x，y）是u 的坐标。L
3、V0：V0是传感器节点的当前工作电压值（初始化时为3V）。当系统运行时，V0是由无线传感器节点定时向汇节点发送自身的电压值。
4、Vmin：Vmin是临界电压值（初始化时为2.7V）。
5、通信距离：WL
三、改进的蚁群算法在无线传感器网络中的应用
（一） 算法的基本思路
（1）通过一组“蚂蚁”人工代理遍历网络节点来产生Sink节点到达目标节点的最优路径；（2）通过蚂蚁的局部搜索以递增的方式来建立路径；（3）使用试探获得的信息来指导各个蚂蚁的搜索，使各路径趋于汇合，最终达到数据汇集的目的。（4）算法不需要网络中各传感节点维护全局网络状态；（5）蚂蚁不必遍历节点拓扑图中的所有节点。因而具备更好的可伸缩性。测试结果也表明新路由算法具有较好的路由性能。
（二）算法实现
1、初始化过程
Q=200；α=1；β=4；ρ=0.5；iAntCount=20；
iMoteCount=30；iItCount=500；将m只蚂蚁置于起始节点。
2、初始化网络节点拓扑图；
3、循环开始并设置最大循环次数。
4、所有蚂蚁依次遍历网络节点；
5、计算每个蚂蚁的路径长度，将最优解存储到全局变量中。
6、对每个蚂蚁更新信息素。
7、重复3，直到输出结果。
四、结论
不同的参数对最优解和循环次数有着不同的影响。算法中对蚂蚁个数要求有较宽松的范围，取节点的个数即可。参数α对循环次数不敏感，对解路径的长度影响较大。参数β和Q正相反，对解路径影响不大，但是对循环次数反应较为灵敏。因此在传感器网络的路由问题中应该着重留意。对于无线传感器网络中的路由问题，蚁群算法可以在较少的循环之内取得比较满意的最优解或次优解。由于改进的蚁群算法不要求蚂蚁必须遍历所有的网络节点便可以找到最优或次优解，而且收敛速度较快，当数据采集区域内分布着较多的节点时，可以较好地适应实时的数据传输要求。
参考文献：
[1]周春光，梁艳春.计算智能.吉林大学出版社，2001.
[2]胡小兵，黄席樾.基于混合行为蚁群算法的研究[J].控制与决策，2004.
[3] Dorige M，Maniezzo V，Colorni A. Ant system： Optimization by a colony of cooperating agents.IEEE Trans. on SMC. 1996.
（作者简介：赵艳伟（1968-），女，汉族，吉林长春人，副教授，硕士学历，吉林工商学院信息工程分院，研究方向：算法及其应用。）
注：本文是吉林省教育厅“十一五”科学技术研究项目,项目名称：改进的蚁群算法在优化问题上的应用，项目编号：吉教科合字[2008]第411号。