传感器网络中基于蚁群优化的数据查询协议.pptVIP

传感器网络中基于蚁群优化的数据查询协议 一. 蚁群优化算法 1.信息素在蚁群觅食中的作用 2.蚁群算法的相关研究 基本蚁群算法 简单蚁群算法流程 蚁群算法在组合优化中的应用 蚁群算法在传感器网络中的应用研究 图1 蚂蚁觅食过程 蚂蚁虽然没有视觉，但在运动时会通过在路径上释放出一种特殊的 分泌物——信息素（Pheromone）来寻找路径。当它们碰到一个还没 走过的路口时，就随机地挑选一条路径前行，同时释放出与路径长 度有关的信息素。蚂蚁走的路径越长，则释放的信息素量越小，当 后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率 相对较大，这样就形成了一个正反馈机制，最优路径上的信息量越 来越大，而其他路径上的信息量却会随着时间的流逝而逐渐减弱， 由此可见，在蚂蚁觅食中起指导作用的是信息 素，其指导作用表现在两方面：一是蚂蚁之间通 过信息素互相通信，使得蚂蚁能够利用以前的搜 索结果；二是信息素的挥发作用，这使得有哪些信誉好的足球投注网站初 期距离较长的路径对蚂蚁的影响越来越小 2 蚁群算法的相关研究 dij：两个城市i和j之间的距离； ηij：边（i,j）的能见度，反映由城市i转移到城市j的启发程度， ； ：边（i,j）上的信息素轨迹强度； ：蚂蚁k在边(i,j)上留下的单位长度轨迹信息素量； ：蚂蚁k的转移概率，j是尚未访问的城市； 初始时刻， 表示第k只蚂蚁在本次循环中留在路径（i,j）上的信息量。 若第k只蚂蚁在本次循环中经过（i,j），则 = ，式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；Lk表示第k只蚂蚁在本次循环中所走路径的总长度。 其中 表示第k只蚂蚁在时刻（t,t+1）留在 路径（i,j）上的信息素量，其值视蚂蚁表现的优劣 程度而定，路径越短，信息素释放的就越多； 表 示本次循环中路径(i,j)的信息素量的增量，ρ为信息素 轨迹的衰减系数，通常设系数ρ1来避免路径上轨迹量 的无限累加。  谣传协议存在的问题： 1、形成的路径中可能包含回路 2、形成的路径不一定最优 3、形成完整查询路由的概率不是100% 基于蚁群优化的谣传协议(RRACO) 相关定义： 定义1 事件：传感器节点能够感知并能处理的数据。 定义2 事件中心：产生事件的传感器节点。 定义3 事件距离：节点距离事件中心的跳数，用hopevent表示。 定义4 查询距离：节点距离sink节点的跳数，用hopquery表示。 定义5 事件蚂蚁：是由事件区域的传感器节点在感知到事件后产生的数据包。数据包中包含产生感知到该事件的节点的消息、事件消息、节点离事件中心的跳数 、该节点的邻居节点的消息。其中产生事件蚂蚁的节点将自己的跳数设为0，即hopevent=0；邻居节点的消息包括邻居节点的剩余能量、邻居节点离事件中心的距离，这里指距离事件中心的跳数。 定义6 查询蚂蚁：由sink节点发出查询任务后，收到查询任务的节点产生的数据包。数据包中包含节点的ID，查询任务，以及节点距离sink节点的跳数，节点的邻居节点的消息。其中产生查询蚂蚁的节点将自己距离sink节点的跳数设为1，即hopquery=1；邻居节点的消息包括邻居节点的剩余能量、邻居节点离sink节点的距离。 定义7 事件蚂蚁路径：事件蚂蚁随机选择下一跳邻居节点，将事件传播出去的路径，例如图2中实线实心箭头所示的路径就是一条事件蚂蚁路径。 定义8 查询蚂蚁路径：查询蚂蚁随机选择下一跳邻居节点，将查询任务传播出去的路径，如图2中虚线实心箭头所示的路径就是一条查询蚂蚁路径。 定义9 完整的查询路径：当事件蚂蚁路径与查询蚂蚁路径相交时，则产生一条从事件中心到sink节点的路径，这条路径就是完整的查询路径。如图2中虚线空心箭头所示即为一条完整的查询路径。 基于蚁群优化的谣传协议(RRACO) 协议思想： 将蚁群分成两个种群：由收到查询消息的节点产生的查询蚂蚁和由事件中心产生的事件蚂蚁。通过状态转移函数和信息素的更新，查询蚂蚁从sink节点出发向源节点方向寻路，而事件蚂蚁则从源节点出发向sink节点方向寻路，当两个种群的蚂蚁相遇时，则会形成一条sink节点到事件区域的完整路径，此路径则为查询路径。如图2所示。 RRACO状态转移函数： 物理距离： 通信距离： 状态转移概率： 启发函数： 信息素的调整： RRACO协议数据汇聚与路径合并 事件蚂蚁移动步骤： 步骤1：网络初始时，所有节点的hopevent和hopquery均为NULL。 事件中心根据一定的阈值产生事件蚂蚁k，事件蚂蚁k知道自己邻居节点的消息，同时生成一张