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

1、长江大学计算机科学学院长江大学计算机科学学院 传感器网络中基于蚁群优化的传感器网络中基于蚁群优化的 数据查询协议数据查询协议 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 二二.谣传协议谣传协议 三三.相关定义相关定义 四四.算法思想算法思想 目录目录 一一. .蚁群优化算法蚁群优化算法 五五.状态转移函数状态转移函数 六六. .算法步骤算法步骤 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 一一. 蚁群优化算法蚁群优化算法 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 在自然界中，蚂蚁的食物总是随机散布于蚁巢的周在自然界中，蚂蚁的食物总是随机散布于蚁

2、巢的周 围，根据昆虫学家的观察和研究发现，蚂蚁有能力围，根据昆虫学家的观察和研究发现，蚂蚁有能力 在没有任何可见提示下找到从蚁穴到食物的最短路在没有任何可见提示下找到从蚁穴到食物的最短路 径，并且能随环境的变化而变化搜索新的路径，产径，并且能随环境的变化而变化搜索新的路径，产 生新的选择。生新的选择。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 图1 蚂蚁觅食过程 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 蚂蚁虽然没有视觉，但在运动时会通过在路径上释放出一种特殊的蚂蚁虽然没有视觉，但在运动时会通过在路径上释放出一种特殊的 分泌物分泌物信息素（信息素（phero

3、monepheromone）来寻找路径。当它们碰到一个还没）来寻找路径。当它们碰到一个还没 走过的路口时，就随机地挑选一条路径前行，同时释放出与路径长走过的路口时，就随机地挑选一条路径前行，同时释放出与路径长 度有关的信息素。蚂蚁走的路径越长，则释放的信息素量越小，当度有关的信息素。蚂蚁走的路径越长，则释放的信息素量越小，当 后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率 相对较大，这样就形成了一个正反馈机制，最优路径上的信息量越相对较大，这样就形成了一个正反馈机制，最优路径上的信息量越 来越大，而其他路径上的信息量却会随着

4、时间的流逝而逐渐减弱，来越大，而其他路径上的信息量却会随着时间的流逝而逐渐减弱， 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 由此可见，在蚂蚁觅食中起指导作用的是信息由此可见，在蚂蚁觅食中起指导作用的是信息 素，其指导作用表现在两方面：一是蚂蚁之间通素，其指导作用表现在两方面：一是蚂蚁之间通 过信息素互相通信，使得蚂蚁能够利用以前的搜过信息素互相通信，使得蚂蚁能够利用以前的搜 索结果；二是信息素的挥发作用，这使得搜索初索结果；二是信息素的挥发作用，这使得搜索初 期距离较长的路径对蚂蚁的影响越来越小期距离较长的路径对蚂蚁的影响越来越小 长江大学计算机科学学院长江大学计算机科学学院

5、 崔艳荣崔艳荣 2 蚁群算法蚁群算法的相关研究的相关研究 b bi i(t)(t)：t t时刻位于城市时刻位于城市i i的蚂蚁个数；的蚂蚁个数； m m：蚁群中蚂蚁的数量，：蚁群中蚂蚁的数量，m= m= ； n i i tb 1 )( 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 dij：两个城市：两个城市i和和j之间的距离；之间的距离； ij：边（：边（i,j）的能见度，反映由城市）的能见度，反映由城市i转移到城市转移到城市j 的启发程度，的启发程度， ； ：边（：边（i,j）上的信息素轨迹强度；）上的信息素轨迹强度； ：蚂蚁：蚂蚁k在边在边(i,j)上留下的单位长度轨迹信息素

6、上留下的单位长度轨迹信息素 量；量； ：蚂蚁：蚂蚁k的转移概率，的转移概率，j是尚未访问的城市；是尚未访问的城市； 初始时刻，初始时刻， 表示第表示第k只蚂蚁在本次循只蚂蚁在本次循 环中留在路径（环中留在路径（i,j）上的信息量。）上的信息量。 ij d/ 1 ij ij ij k ij p 0) 0 ( ij )(t k ij 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 若第若第k只蚂蚁在本次循环中经过（只蚂蚁在本次循环中经过（i,j），则），则 = ，式中，式中，q表示信息素强度，它在一定程表示信息素强度，它在一定程 度上影响算法的收敛速度；度上影响算法的收敛速度；lk表示

7、第表示第k只蚂蚁在只蚂蚁在 本次循环中所走路径的总长度。本次循环中所走路径的总长度。 )(t k ij k lq/ 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 k alloweds ijij ijijk ij allowedj tt tt p k , )()( )()( 蚂蚁在城市i选择城市j的转移概率式(1): : 和和为两个参数，分反映了蚂蚁在运动过程中为两个参数，分反映了蚂蚁在运动过程中 所积累的信息和启发信息在蚂蚁选择路径中的相所积累的信息和启发信息在蚂蚁选择路径中的相 对重要性。对重要性。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 为了避免残留信息素

8、过多引起残留信息素淹没启发信为了避免残留信息素过多引起残留信息素淹没启发信 息，在每只蚂蚁走完一步或者完成对所有息，在每只蚂蚁走完一步或者完成对所有n n个城市的遍个城市的遍 历后，要对残留信息进行更新处理。各路径上的信息历后，要对残留信息进行更新处理。各路径上的信息 素量根据式素量根据式(2)(2)、式、式(3)(3)调整：调整： ) 1,()(.) 1(tttt ijijij (2)(2) m k k ijij tttt 1 ) 1,() 1,( (3)(3) 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 其中其中 表示第表示第k k只蚂蚁在时刻（只蚂蚁在时刻（t,t+1t,

9、t+1）留在）留在 路径（路径（i,ji,j）上的信息素量，其值视蚂蚁表现的优劣）上的信息素量，其值视蚂蚁表现的优劣 程度而定，路径越短，信息素释放的就越多；程度而定，路径越短，信息素释放的就越多； 表表 示本次循环中路径示本次循环中路径( (i,ji,j) )的信息素量的增量，的信息素量的增量，为信息素为信息素 轨迹的衰减系数，通常设系数轨迹的衰减系数，通常设系数11来避免路径上轨迹量来避免路径上轨迹量 的无限累加。的无限累加。 ) 1,(tt k ij ) 1, ( t t ij 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 二、谣传协议二、谣传协议 谣传协议适用于数据传输量

10、较少或者已知事件区谣传协议适用于数据传输量较少或者已知事件区 域域 的传感器网络中，它利用事件区域中的传感器节的传感器网络中，它利用事件区域中的传感器节 点点 产生代理（产生代理（agentagent）消息，代理消息沿随机路径向）消息，代理消息沿随机路径向 外扩散传播，同时汇聚节点发送的查询消息也沿外扩散传播，同时汇聚节点发送的查询消息也沿 随随 机路径在网络中传播，当代理消息和查询消息的机路径在网络中传播，当代理消息和查询消息的 传传 输路径交叉在一起时，就形成一条汇聚节点到事输路径交叉在一起时，就形成一条汇聚节点到事 件件 区域的完成路径。区域的完成路径。 长江大学计算机科学学院长江大学计

11、算机科学学院 崔艳荣崔艳荣 谣传协议存在的问题：谣传协议存在的问题： 1、形成的路径中可能包含回路、形成的路径中可能包含回路 2、形成的路径不一定最优、形成的路径不一定最优 3、形成完整查询路由的概率不是、形成完整查询路由的概率不是100% 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 基于蚁群优化的谣传协议基于蚁群优化的谣传协议(rraco) 相关定义：相关定义： v定义定义1 事件：传感器节点能够感知并能处理的数事件：传感器节点能够感知并能处理的数 据。据。 v定义定义2 事件中心：产生事件的传感器节点。事件中心：产生事件的传感器节点。 v定义定义3 事件距离：节点距离事件中

12、心的跳数，用事件距离：节点距离事件中心的跳数，用 hopevent表示。表示。 v定义定义4 查询距离：节点距离查询距离：节点距离sink节点的跳数，用节点的跳数，用 hopquery表示。表示。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 v定义定义5 事件蚂蚁：是由事件区域的传感器节点在事件蚂蚁：是由事件区域的传感器节点在 感知到事件后产生的数据包。数据包中包含产生感知到事件后产生的数据包。数据包中包含产生 感知到该事件的节点的消息、事件消息、节点离感知到该事件的节点的消息、事件消息、节点离 事件中心的跳数事件中心的跳数 、该节点的邻居节点的消息。其、该节点的邻居节点的消息

13、。其 中产生事件蚂蚁的节点将自己的跳数设为中产生事件蚂蚁的节点将自己的跳数设为0，即，即 hopevent=0；邻居节点的消息包括邻居节点的；邻居节点的消息包括邻居节点的 剩余能量、邻居节点离事件中心的距离，这里指剩余能量、邻居节点离事件中心的距离，这里指 距离事件中心的跳数。距离事件中心的跳数。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 v定义定义6 查询蚂蚁：由查询蚂蚁：由sink节点发出查询任务后，节点发出查询任务后， 收到查询任务的节点产生的数据包。数据包中包收到查询任务的节点产生的数据包。数据包中包 含节点的含节点的id，查询任务，以及节点距离，查询任务，以及节点距

14、离sink节节 点的跳数，节点的邻居节点的消息。其中产生查点的跳数，节点的邻居节点的消息。其中产生查 询蚂蚁的节点将自己距离询蚂蚁的节点将自己距离sink节点的跳数设为节点的跳数设为1， 即即hopquery=1；邻居节点的消息包括邻居节点；邻居节点的消息包括邻居节点 的剩余能量、邻居节点离的剩余能量、邻居节点离sink节点的距离。节点的距离。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 v 定义定义7 事件蚂蚁路径：事件蚂蚁随机选择下一跳邻居节点，事件蚂蚁路径：事件蚂蚁随机选择下一跳邻居节点， 将事件传播出去的路径，例如图将事件传播出去的路径，例如图2中实线实心箭头所示的中实

15、线实心箭头所示的 路径就是一条事件蚂蚁路径。路径就是一条事件蚂蚁路径。 v 定义定义8 查询蚂蚁路径：查询蚂蚁随机选择下一跳邻居节点，查询蚂蚁路径：查询蚂蚁随机选择下一跳邻居节点， 将查询任务传播出去的路径，如图将查询任务传播出去的路径，如图2中虚线实心箭头所示中虚线实心箭头所示 的路径就是一条查询蚂蚁路径。的路径就是一条查询蚂蚁路径。 v 定义定义9 完整的查询路径：当事件蚂蚁路径与查询蚂蚁路径完整的查询路径：当事件蚂蚁路径与查询蚂蚁路径 相交时，则产生一条从事件中心到相交时，则产生一条从事件中心到sink节点的路径，这节点的路径，这 条路径就是完整的查询路径。如图条路径就是完整的查询路径。

16、如图2中虚线空心箭头所示中虚线空心箭头所示 即为一条完整的查询路径。即为一条完整的查询路径。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 基于蚁群优化的谣传协议基于蚁群优化的谣传协议(rraco) 协议思想：协议思想： 将蚁群分成两个种群：由收到查询消息的节点产将蚁群分成两个种群：由收到查询消息的节点产 生的查询蚂蚁和由事件中心产生的事件蚂蚁。通生的查询蚂蚁和由事件中心产生的事件蚂蚁。通 过状态转移函数和信息素的更新，查询蚂蚁从过状态转移函数和信息素的更新，查询蚂蚁从 sink节点出发向源节点方向寻路，而事件蚂蚁则节点出发向源节点方向寻路，而事件蚂蚁则 从源节点出发向从源节点出

17、发向sink节点方向寻路，当两个种群节点方向寻路，当两个种群 的蚂蚁相遇时，则会形成一条的蚂蚁相遇时，则会形成一条sink节点到事件区节点到事件区 域的完整路径，此路径则为查询路径。如图域的完整路径，此路径则为查询路径。如图2所所 示。示。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 rracorraco状态转移函数：状态转移函数： 物理距离物理距离： 通信距离通信距离： 状态转移概率状态转移概率： 22 )()( jiji vvvvp yyxxd 2 1 p residual vv d e d ji kj kj ta

18、buv vvvv vvvv k vv tabuifv tabuifv tt tt tp kj jiji jiji ji , 0 , )()( )()( )( （6 6） 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 启发函数启发函数： 信息素的调整：信息素的调整： ji j ji vv residualv vv d e t _ )( )()()1 ()(ttnt jijiji vvvvvv m k k vvvv tt jiji 1 )()( ，否则 过只蚂蚁在本次循环中经若第 0 ),(, )( ji k k vv vvk l q t ji （8 8） 长江大学计算机科学学院长江

19、大学计算机科学学院 崔艳荣崔艳荣 rracorraco协议数据汇聚与路径合并协议数据汇聚与路径合并 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 事件蚂蚁移动步骤：事件蚂蚁移动步骤： v 步骤步骤1：网络初始时，所有节点的：网络初始时，所有节点的hopevent和和hopquery均均 为为null。 v 事件中心根据一定的阈值产生事件蚂蚁事件中心根据一定的阈值产生事件蚂蚁k，事件蚂蚁，事件蚂蚁k知知 道自己邻居节点的消息，同时生成一张禁忌表道自己邻居节点的消息，同时生成一张禁忌表tabuk，事，事 件中心节点将自己距离事件中心的跳数设为件中心节点将自己距离事件中心的跳数设为0，

20、即，即 hopevent=0，同时加入到，同时加入到tabuk； v 步骤步骤2：事件蚂蚁计算到邻居节点的通信距离，根据邻居：事件蚂蚁计算到邻居节点的通信距离，根据邻居 节点的剩余能量，利用式（节点的剩余能量，利用式（6.6）选择自己的下一跳邻居）选择自己的下一跳邻居 节点：节点： 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 v 若下一跳邻居节点的若下一跳邻居节点的hopevent=null，则选择该邻居，则选择该邻居 节点作为自己的下一跳，并将下一跳邻居节点距离事件中节点作为自己的下一跳，并将下一跳邻居节点距离事件中 心的跳数加心的跳数加1，即，即hopevent=hopev

21、ent+1； v 若下一跳邻居节点的若下一跳邻居节点的hopevent不为空，即该节点已经在不为空，即该节点已经在 tabuk中，状态转换概率为中，状态转换概率为0，则从该节点以外的其它邻，则从该节点以外的其它邻 居节点中选择自己的下一跳；居节点中选择自己的下一跳； v 若该节点的所有邻居节点均在若该节点的所有邻居节点均在tabuk中，而还没遇到查中，而还没遇到查 询蚂蚁，则事件蚂蚁回退一步，再去选择下一跳节点。询蚂蚁，则事件蚂蚁回退一步，再去选择下一跳节点。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 v步骤步骤3：若事件蚂蚁遇到查询蚂蚁或者是遇到：若事件蚂蚁遇到查询蚂蚁或者

22、是遇到 sink节点节点,则形成完整查询路径；否则转步骤则形成完整查询路径；否则转步骤2； v步骤步骤4：利用（：利用（8）式更新所经过边的信息素。）式更新所经过边的信息素。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 查询蚂蚁移动步骤：查询蚂蚁移动步骤： v步骤步骤1：sink节点发出查询消息后，收到查询消节点发出查询消息后，收到查询消 息的邻居节点产生查询蚂蚁息的邻居节点产生查询蚂蚁s，并将自己的，并将自己的 hopquery设置为设置为1，同时生成一张禁忌表，同时生成一张禁忌表tabus， 将自己加入到表中将自己加入到表中; v步骤步骤2：查询蚂蚁计算到邻居节点的通信距离

23、，：查询蚂蚁计算到邻居节点的通信距离， 根据邻居节点的剩余能量，利用式（根据邻居节点的剩余能量，利用式（6）选择自）选择自 己的下一跳邻居节点：己的下一跳邻居节点： 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 v 若下一跳邻居节点的若下一跳邻居节点的hopquery=null，则选择该邻居，则选择该邻居 节点作为自己的下一跳，并将下一跳邻居节点距离节点作为自己的下一跳，并将下一跳邻居节点距离sink 节点的跳数加节点的跳数加1，即，即hopquery=hopquery+1； v 若下一跳邻居节点的若下一跳邻居节点的hopquery不为空，即该节点已经不为空，即该节点已经 在在t

24、abus中，则状态转换概率为中，则状态转换概率为0，那么就从该节点以外，那么就从该节点以外 的其它邻居节点中选择自己的下一跳；的其它邻居节点中选择自己的下一跳； v 若该节点的所有邻居节点均在若该节点的所有邻居节点均在tabus中，而还没遇到事中，而还没遇到事 件蚂蚁或者是事件中心，则查询蚂蚁回退一步，然后再去件蚂蚁或者是事件中心，则查询蚂蚁回退一步，然后再去 选择下一跳节点。选择下一跳节点。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 v步骤步骤3：若遇到事件蚂蚁或者是遇到事件中心节：若遇到事件蚂蚁或者是遇到事件中心节 点点,则形成完整查询路径；否则转步骤则形成完整查询路径；

25、否则转步骤2。 v步骤步骤4：利用（：利用（8）式更新所经过边的信息素。）式更新所经过边的信息素。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 rracorraco算法分析：算法分析： rraco算法可以形成完整的查询路由算法可以形成完整的查询路由 v证明：证明：monte-carlo模拟显示，在一个有限的模拟显示，在一个有限的 矩形区域，两条直线相交的概率是矩形区域，两条直线相交的概率是69%，这就，这就 意味着意味着5条事件蚂蚁路径遇到一条查询蚂蚁路径条事件蚂蚁路径遇到一条查询蚂蚁路径 的概率是的概率是99.7%。已经假设了节点是分布在矩。已经假设了节点是分布在矩 形区域，

26、就算节点分布的区域不一定是矩形，事形区域，就算节点分布的区域不一定是矩形，事 件蚂蚁路径和查询蚂蚁路径也不一定是直线，也件蚂蚁路径和查询蚂蚁路径也不一定是直线，也 不影响结果的正确性。则事件蚂蚁遇到查询蚂蚁不影响结果的正确性。则事件蚂蚁遇到查询蚂蚁 的概率很大，很容易形成完整的查询路由。的概率很大，很容易形成完整的查询路由。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 v如果事件蚂蚁总是遇不到查询蚂蚁，事件蚂蚁会如果事件蚂蚁总是遇不到查询蚂蚁，事件蚂蚁会 一直寻找下一跳节点传播事件，直到遇到一直寻找下一跳节点传播事件，直到遇到sink节节 点为止，算法终止；如果查询蚂蚁遇不到事

27、件蚂点为止，算法终止；如果查询蚂蚁遇不到事件蚂 蚁，查询蚂蚁也会一直寻找下一跳节点传播查询蚁，查询蚂蚁也会一直寻找下一跳节点传播查询 任务，直到找到源节点。不管是那一种情况，都任务，直到找到源节点。不管是那一种情况，都 可以形成一条完整的查询路由。证毕。可以形成一条完整的查询路由。证毕。 长江大学计算机科学学院长江大学计算机科学学院 崔艳荣崔艳荣 v rraco算法中不会形成回路算法中不会形成回路 v 证明：事件蚂蚁移动步骤和查询蚂蚁移动步骤虽然细节上有所不同，证明：事件蚂蚁移动步骤和查询蚂蚁移动步骤虽然细节上有所不同， 但寻找下一跳节点的规则是相同的，以事件蚂蚁移动为例进行证明。但寻找下一跳

28、节点的规则是相同的，以事件蚂蚁移动为例进行证明。 如图如图4所示，事件蚂蚁所示，事件蚂蚁k当前所在位置为节点当前所在位置为节点a，则其，则其hopa_event=2， 则事件蚂蚁则事件蚂蚁k到了节点到了节点c时，其时，其hopc_event=4，且节点，且节点a、b、c均均 在其禁忌表中，即，假设事件蚂蚁在节点在其禁忌表中，即，假设事件蚂蚁在节点c处可以选节点处可以选节点a作为其下作为其下 一跳邻居节点，则会构成一跳邻居节点，则会构成ab-bc-ca这样的回路，但这是不可能的，这样的回路，但这是不可能的， 因为此时因为此时hopa_event=2不为不为null，且因为，且因为a在其蚂蚁在其蚂蚁k的禁忌表中，的禁忌表中， 根据式（根据式（6）选择）选择a作为节点作为节点c的下一跳的概率是的下一跳的概率是0，所以出现矛盾。，所以出现矛盾。 则节点则节点c会选节点会选节点a、b以外的其他节点比如节点以外的其他节点