蚁群算法及其在数据获取技术中的应用研究

摘要

蚁群优化算法作为群集智能领域应用最为广泛的算法之一，已受到越来越多研究者的关注。近年来，其理论研究正在不断充实，其应用领域亦在进一步拓展，在解决NP难题和网络路由等方面的优越性已被广泛证实。由于网络环境的动态性和网络应用的多样性，一些网络中的关键应用已不能适应传统的算法，需要提出新的针对具体网络应用的解决方案。蚁群优化为网络中数据资源的获取提供了一个好的解决思路。 本文首先介绍了群集智能的主要理论研究及典型应用，概述了网络数据获取中的任播和查询两大关键技术，在此基础上对基于群集智能的蚁群优化算法及其在分布式网络环境下任播和查询两大关键数据获取技术中的应用进行了系统和深入的研究，所做主要工作归纳如下： (1)在缺乏全局网络信息的情况下，针对因特网多约束任播这一NP难题，提出了一种基于多蚁群优化的任播路由算法MACA。该算法仅需局部网络信息，通过蚂蚁释放信息素来改变网络环境，从而间接引导其它蚂蚁根据信息素强度动态调整自身的选路行为。仿真实验表明，具有正反馈效应的分布式MACA算法使得各蚂蚁能以较高的概率选择满足自身QoS约束的较优路径，有效降低路由时延，显著提高任播请求的接受率。 (2)在节点位置信息未知的情况下，针对无线传感器网络多约束任播路由问题，结合蚁群路由和蚁群聚类思想，提出了一种基于蚁群优化的可靠任播路由算法ARMCA。该算法兼顾节点能量和路由时延双重约束，引入带正反馈特征的蚁群优化来为每个数据包寻找自源节点至相应Sink节点的较优路径，以降低路由传输时延，节省路由能耗。算法同时引入基于蚁群聚类思想的自恢复机制来应对网内簇头或Sink节点的失效，通过平滑过渡到新的稳定态来自动消除节点失效造成的负面影响。仿真实验表明，在相同QoS约束条件下，随着网络规模的增大，ARMCA算法在能耗和时延两方面的优越性更为显著。在遭遇节点失效时，ARMCA算法仅需相对较短的时间便可恢复至新的稳定状态，从而保证了网络数据的可靠传输。 (3)在网络拓扑结构动态变化的情况下，针对移动自组网多约束任播，提出了一种基于蚁群优化的任播算法AMMCA。该算法充分考虑节点的移动性，引入信息素扩散模型以增大对较优路径周边的节点扩散信息素，从而降低因节点移动导致的路径断裂；同时，通过构建多路径路由以均衡网络负载，进一步减轻因节点移动造成数据传输中断带来的负面影响。仿真实验表明，在平均数据包接受率及端到端路由时延等方面，与其它移动自组网任播路由算法相比，AMMCA算法具有良好的性能优势。 (4)对于能量等资源受限的规模较大的无线传感器网络，如何节能地处理多个查询节点发起的并行式复制数据查询是一个挑战性难题。本文提出了一种基于多蚁群优化的节能复制数据查询处理算法MACQP。该算法首先执行事件数据的随机复制，然后在查询节点发送前向蚂蚁搜索到达事件某一副本的较优路径，搜索过程具有一定的智能性。当找到目标数据后，产生后向蚂蚁原路返回并执行事件数据二次复制，使得后继查询蚂蚁能沿信息素强度较大的较优路径在更近的节点找到目标事件数据，缩短了搜索路径的长度，使得总搜索能耗显著降低，整体上降低了查询总能耗。理论分析和仿真实验表明，MACQP算法通过蚁群协作产生的智能搜索和动态复制，在节能性方面优势明显。 (5)针对大规模无线传感器网络的实时应用，兼顾查询处理的节能性和实时性，提出了一种基于多蚁群优化的实时查询处理算法ARTQP。该算法采用一种优化的分簇方法和分环存储策略，使得查询能区分处理不同优先级的事件数据，实时性越高的事件具有更大的概率被前向蚂蚁所探知，搜索过程具有较好的智能性。当找到目标事件后，产生后向蚂蚁返回并执行事件动态二次复制，使得后继查询蚂蚁能沿较优路径在更近的存储节点找到目标事件数据，以显著缩短搜索路径的平均长度和平均查询时延，降低查询总能耗。理论分析和仿真实验表明，与已存查询处理算法相比，ARTQP算法在实时性和节能性方面性能增益明显，且网络规模越大，性能优势越显著，在QoS要求较严格的情况下，亦能取得良好的性能。

目录

文摘

英文文摘

论文说明：图表目录

声明

第1章绪论

1.1研究背景及意义

1.2群集智能模型及经典算法

1.2.1群集智能模型概述

1.2.2蚁群优化算法

1.2.3粒子群优化算法

1.3蚁群算法的发展与研究现状

1.3.1蚁群算法的发展

1.3.2国内外研究现状

1.4网络数据获取及其关键技术

1.4.1网络数据获取概述

1.4.2网络任播路由技术

1.4.3网络查询处理技术

1.5论文主要工作及组织结构

1.5.1论文主要工作

1.5.2论文组织结构

第2章相关研究综述

2.1蚁群优化算法的理论研究

2.1.1蚁群算法求解问题一般思路

2.1.2蚁群算法收敛性探讨

2.2蚁群优化算法典型应用研究

2.3网络任播路由算法研究

2.3.1因特网任播算法概述

2.3.2传感器网络任播算法概述

2.3.3移动自组网任播算法概述

2.4网络查询处理相关研究

2.5小结

第3章基于蚁群优化的因特网多约束任播路由研究

3.1引言

3.2基于多蚁群算法的因特网任播路由

3.2.1网络拓扑结构

3.2.2服务请求的产生及管理机制

3.2.3路径选择策略

3.2.4信息素更新规则

3.2.5算法具体步骤

3.3仿真实验与分析

3.3.1实验1：网络拓扑固定

3.3.2实验2：目标节点分散

3.3.3实验3：网络拓扑随机

3.4小结

第4章基于蚁群优化的传感器网络可靠任播路由研究

4.1引言

4.2蚁群路由及聚类模型

4.2.1蚁群路由模型

4.2.2蚁群聚类模型

4.3网络环境与问题描述

4.3.1 WSN网络模型

4.3.2数据产生与聚合

4.3.3问题描述

4.4基于蚁群算法的传感器网络可靠任播路由

4.4.1蚂蚁的定义及管理

4.4.2算法初始化

4.4.3路径构建策略

4.4.4信息素更新规则

4.4.5算法自修复方法

4.4.6算法具体步骤

4.5仿真实验与分析

4.5.1实验环境与参数设置

4.5.2实验结果与分析

4.6小结

第5章基于蚁群优化的移动自组网任播路由研究

5.1引言

5.2蚁群优化的信息素扩散模型

5.2.1蚁群算法信息素扩散初始模型

5.2.2移动自组网信息素扩散新模型

5.3基于蚁群算法的移动自组网任播路由

5.3.1移动模型分析

5.3.2蚂蚁定义及管理

5.3.3路径构建策略

5.3.4信息素更新规则

5.3.5算法具体步骤

5.4仿真实验与分析

5.4.1实验环境与参数设置

5.4.2实验结果与分析

5.5小结

第6章传感器网络中基于蚁群优化的复制查询处理

6.1引言

6.2网络模型及问题描述

6.3事件聚合及编码

6.3.1事件数据聚合

6.3.2事件数据编码

6.4网内事件数据随机复制策略

6.5基于多蚁群算法的传感器网络节能复制查询处理

6.5.1传感器网络拓扑萃取

6.5.2查询请求的管理

6.5.3路径选择策略

6.5.4信息素更新规则

6.5.5动态二次复制策略

6.5.6算法具体步骤

6.6算法理论分析

6.6.1复制能耗分析

6.6.2搜索能耗分析

6.6.3总能耗及性能对比分析

6.7仿真实验

6.7.1实验环境及设置

6.7.2实验结果与分析

6.8小结

第7章传感器网络中基于蚁群优化的实时查询处理

7.1引言

7.2网络模型及问题描述

7.3基于事件优先级的分环储存策略

7.4基于多蚁群算法的传感器网络实时查询处理

7.4.1实时查询处理网络环境

7.4.2查询请求的管理

7.4.3路径选择策略

7.4.4信息素更新规则

7.4.5动态二次复制策略

7.4.6算法具体步骤

7.5算法理论分析

7.5.1复制能耗分析

7.5.2搜索能耗分析

7.5.3查询时延分析

7.6仿真实验

7.6.1实验环境及设置

7.6.2查询能耗比较及分析

7.6.3查询时延比较及分析

7.6.4查询成功率比较及分析

7.7小结

结论及展望

参考文献

致 谢

附录