蚁群算法在WSN中的应用

WSN中的蚁群路由算法一、拟解决的问题:优化路由寻址方式，寻找总体距离最短的路径来传递数据，借此大幅度的降低传输过程 中的能量损耗和延时。利用蚁群算法的总体优化概念，采用随机性选择，通过模拟蚂蚁的信 息素的挥发规则并行试探产生源节点到汇集节点的最优路径。在算法实现过程中，信息素综 合考虑了能量、距离和延时三个因素。因为时间问题，仿真中只考虑了距离和能量限制，其 中距离限制由传感器射频距离R来控制，能量限制主要考虑残余能量的分布。仿真结果表明 新型算法的使用带来了良好的路由性能。无线传感器网络（Wireless sensor network,WSN）是由部署在监控区域内大量的廉价 微型传感器节点组成，通过无线通信方式形成的一个多跳的、自组织的网络系统。具有大规 模、自组织、动态性、可靠性、应用相关性、以数据为中心等特点，其目的是协作地感知、 采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。传感器网络以应用为目标，在不同的应用场合其网络路由不是惟一的。所以要根据不 同的应用目的，选择最优的路由策略。从无线传感器网络的特点来看,与蚂蚁算法的系统特 征有非常的类似之处，故在蚂蚁算法的基础上，以网络生命周期、节能和减少延时方面达到一 定平衡为目标，采用一种改进的动态自适应调整信息素的蚁群算法。路由算法的基本思想： 采用了确定性选择和随机性选择相结合的选择策略,并在搜索过程中动态调整状态转移概率, 并行试探来产生源节点（source）到汇集节点（sink）的最优路径。在算法实现过程中，信息 素更新综合考虑了能量、距离和延时三个因素。仿真结果表明新型算法的使用带来了良好 的路由性能，并在一定程度上节省了能量。2.1、蚁群算法简介蚁群算法又称蚂蚁算法。蚁群算法的基本原理可大致描述如下：蚂蚁属于群居昆虫，个 体行为极其简单，而群体行为却相当复杂。相互协作的一群蚂蚁很容易找到从蚁穴到食物源 的最短路径，而单个蚂蚁则不能。人们通过大量的研究发现，蚂蚁之所以可以做到这一点， 是因为蚂蚁个体之间是通过在其所经过的路径上留下一种可称之为信息素的物质来进行信 息传递。蚂蚁可以嗅到这种信息素，而且可以根据信息素的浓度来指导自己对前进方向的选 择。同时，该信息素会随着时间的推移逐渐挥发掉，于是路径的长短及该路径上通过的蚂蚁 的多少就对残余信息素的强度产生影响。反过来信息素的强弱又指导着其它蚂蚁的行动方 向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂 蚁群体行为表现出的一种信息正反馈现象。蚂蚁个体之间就是通过这种信息交流快速找到食 物源或蚁穴的。信息素主要有两个方面的作用：一是蚂蚁之间通过信息素相互通信，使得蚂蚁能够利用 以前的搜索结果；二是信息素的挥发作用，这使得搜索初期的距离较长的旅行路线对蚂蚁的 影响逐渐减小。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同 时释放出与路径长度有关的信息素。路径越长，释放的信息素浓度越低。当后来的蚂蚁再次 碰到这个路口的时候，选择信息素浓度较高路径概率就会相对较大。这样形成了一个正反馈。 最优路径上的信息素浓度越来越大，而其它路径上信息素浓度却会随着时间的流逝而消减。蚁群算法是借助于各蚂蚁之间所形成的正反馈作用而实现优化问题求解的，其基本原理 如图1所示。图中节点A、E分别表示蚂蚁穴和食物源。开始时，从A放出若干只蚂蚁到E， 这时它们会以相等的概率选A-B-E、A-C-E和A-D-E支路。每只蚂蚁在所经过的路径上要释放一 定数量的信息素，这些信息素以一定的速率挥发，蚂蚁判断前进的道路时选择信息素强度最 大的道路。这样，如图一种，当选择A-D-E支路的蚂蚁按原路返回到A时，因为其余两条路 径的长度较长，从A点出发的蚂蚁还没有返回到A点，这时，A-D-E上的信息素强度高于其 余两条支路上的信息素强度，因此后续蚂蚁选择A-D-E支路的概率就变得最大。这样A-D-E 支路上的信息素强度就会越来越大，而其余两条支路随着蚂蚁访问次数的减少，信息素就会 变得越来越少，最终，所有的蚂蚁都选择了长度最短的A-D-E支路。1.21112.ini3.2m2.8m3.3rti2.5m囹一基本蛇群算法三、 实现：【描述代码实现方式】（宋体，5号字）3.1路径选择问题描述WSN可以用图G=（V,E）来表示，其中V代表节点集合（包括传感器节点和sink节点），E 代表边的集合。在无线传感器网络中，如果两个节点是相邻的，则表明这两个点在彼此有效 通信距离之内。假定相邻节点之间只存在一条链路，则传感器网络的拓扑结构可以看作是一 个无向图。对于一个路由请求Q，路由算法如果能够找到一条最优路径，同时满足以下一个 约束条件，则此路由请求Q就可接受。在Q的路由的每条路径L上，相邻节点距离限制为D < Dmax，其中Dma表示节点的通信半径，（本文设定通信半径R=35m）D =（x x）2+（y y）2为两节点间的欧氏距 ij 、' i j i j离。为了实现不同节点的能量消耗相对均衡，必须对原始的蚁群算法进行不同路径上的数据 包分流，以免使各个节点都通过同一条最优路径使得该路径数据包流量过大而能量耗光。改 进算法加速收敛的同时避免出现收敛于最优路径。为了避免算法易于陷入局部最优解，通过自适应地改变算法的信息素浓度，将蚂蚁的寻路消耗与节点 的能量消耗都作为影响信息素浓度的因素。在此算法中，将蚂蚁要访问的节点的剩余能量作为影响信息素 浓度的一个参数。时心 q）FqFt）I £ 8k*m（t，GF0q Jk Ct）其中是从节点T到节点q的距离的倒数;JJ。是蚂蚊k 还未访问的节点的集合；B是寻路消耗和信息素相对重要程度 的常数，,般取2：冬是第k只蚂蚁信息素浓度与下访问节 点剩余能量的运算因子：穿 Ug*W（q）£ w（v）veu（t）式中f 是蚂蚊k的信息素:驼是节点1的剩余能量u是蚂 蚁k所在节点的所有将被访问的下节点的集合，3.2信息素的更新规则算法初始化中，所有的边都被赋予一定的信息素。在每次搜索开始时，蚂蚁从随机选择 的节点中开始寻找路径，各自开始自己的搜索过程。在搜索中，蚂蚁倾向于沿着信息素水平 较高的边访问下一个节点。当所有蚂蚁完成了搜索后，进行全局信息素更新：所有连接边的 信息素都有一部分挥发出去，然后每只蚂蚁根据它们已经完成寻路的消耗参数更新它们走过 的边的信息素水平。蚂蚁消耗参数越低，信息素水平增加就越显著。然后所有蚂蚁重新选择 出发的节点，重新开始搜索。假设一只蚂蚁正处于节点t，他选择下一节点q进行访问的概率Pk（, ）使用以下公式确定的:（1）T (t, p) * H (t, q川*,小 Z T(t, p) * M, q川 5 q k蛙 0()V其中T是信息素数量；H =结是从节点t到q的距离的倒数；Jk（t）是还未访问节点 的集合；0是调整消耗参数和信息素相对重要程度的常数，一般取2。信息素全局更新按照式（2）进行：t（,p）= （1a）*t（t,p）+a*Z AT（t,q）（2）kL（t，q）是蚂蚁k走过的边0k其他信息素挥发参数，在蚁群算法中一般取0.9。Lk是蚂蚁5完成寻路的消耗参数。四、实验环境介绍：【无需介绍matlab平台，5号字）C=x y;N=50或者100或者400Nc_max=100;m=60;着重介绍仿真的网络配置，比如节点数量、部署方式等】（宋体，Alpha=1.5;Beta=2;Rho=0.1;%n个城市的坐标，n*2的矩阵%由输入参数决定%最大迭代次数% m表示蚂蚁的个数（取决于节点的个数，N=5 0， m=60;N=100,m=130;N=400,m=500%表示信息素重要程度的参数%表征启发式因子重要程度的参数%信息素蒸发系数还有城市可满足停止条件读入节点数据输出最优路径更新信息素拒阵，即更新每条边上的信息素的里随机诫置蚂蛇到N个节点上每个蚂蛇随机迭择下一个节点初始化算法参数 悬公共变量 n返回初始化城市绘制节疽位置（1）首先初始化，设迭代的次数为Nc。初始化Nc=0（2）将m个蚂蚁置于n个顶点上（3）m只蚂蚁按概率函数选择下一座城市，完成各自的周游每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条回路。蚂蚁的任务是访问 所有的城市后返回到起点，生成一条回路。设蚂蚁k当前所在的顶点为i，那么，蚂蚁k由 点i向点j移动要遵循规则而不断迁移，按不同概率来选择下一点。（4）设节点初始能量为10，计算出迭代后的剩余能量，记录本次迭代最佳路线（5）全局更新信息素值应用全局信息素更新规则来改变信息素值。当所有m个蚂蚁生成了 m个解，其中有一条 最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息素值进行更新。全局信息素更新的目的是在最短路线上注入额外的信息素，即只有属于最短路线的弧上 的信息素才能得到加强，这是一个正反馈的过程，也是一个强化学习的过程。在图中各弧上， 伴随着信息素的挥发，全局最短路线上各弧的信息素值得到增加。（6）终止若终止条件满足，则结束；否则NC=NC+1，转入步骤（2）进行下一代进 化。终止条件可指定进化的代数，也可限定运行时间，或设定最短路长的下限。（7）输出结果五、仿真结果与分析：【若能与以往或现有国内外相关成果做比较加分】（宋体，5号字） 5.1、N=50时的仿真图100 r0102030405060708090100N ET5.2、N=100时的仿真图o o141260o o4 21.91.81.71.61.51.41.31.2原始各节点剩余能量1.91.81.71.61.51.41.31.21.1051015202530354045501.551.51.451.41.351.31.251.10510152025303540455005101520253035404550六、结论:由仿真结果可知，采用蚁群算法后，选择的路径距离明显下降了，改进算法在加快收敛 的同时能量损耗更加均衡，达到延长无线传感器网络寿命的要求。七、参考文献1 Dorigo M ,Gambardella L M. Ant colonies for the traveling salesman problemJ .BioSystems ,1997 ,43 (2) :73 - 812 Milan Simek, Patrik Moravek， Jorge sa Silva， Wir