分布式约束优化在传感器网络目标跟踪问题中的应用研究

摘要

分布式约束优化问题（DCOP）是一种用于解决多Agent系统协作优化问题的重要建模方式，具有隐私性、信息局部性、控制分散化等特点。目前对该领域的研究主要是算法理论方面的研究，应用研究较少。在DCOP的应用研究中，传感器网络是一个主要的应用领域。传感器网络中目标跟踪问题较适用于DCOP建模，受到了广泛关注。但是目前对该问题的DCOP建模存在一些问题，例如模型定义不清晰或缺乏现实物理意义。本文针对该问题，为一类传感器网络的目标跟踪问题提出了一种具有现实物理意义的DCOP模型，并提出了适用于该模型的求解算法，具体研究工作如下：
　　1.介绍了传感器网络目标跟踪问题的研究现状，并对使用非分布式方式和使用DCOP建模这两种方式在该问题上研究的重点进行了分析和比较。然后，具体介绍了DCOP的基本定义以及其约束图表述，并较详细地介绍了DSA和MGM两种DCOP近似求解算法。此外，详细描述了传感器网络目标跟踪问题的几类DCOP建模方法，并阐述了这些模型的优缺点。
　　2.将一类传感器网络目标跟踪问题抽象为一种图多着色问题，并针对图多着色问题提出两种不同的DCOP模型：ACSV和ACMV。ACSV模型采用一个agent控制一个变量的方式，它的最大特点是变量的取值是一个颜色集合，而不是一个单独的值；ACMV模型采用一个agent控制多变量的方式，它的最大特点是每个变量不仅仅需要考虑外部约束，同时必须满足内部约束。然后对这两种模型的优缺点进行比较。
　　3.基于DSA和MGM，提出了两种用于解决图多着色问题的分布式约束优化算法MGCDSA和MGCMGM。针对图多着色问题，MGCDSA和MGCMGM添加了新的预处理过程：“剪枝”和“降维”。剪枝用于忽略每个agent中没有外部约束关系的变量，降维可以减小两个变量之间约束代价矩阵的维度。实验证明了这两种算法都可以较好地解决图多着色问题。
　　4.对现有的分布式约束优化问题平台DCOPSolver进行了扩充，添加了传感器网络目标跟踪问题对应的图多着色问题生成和解析模块，并对平台中的通信逻辑以及结果展示模块进行了完善。

目录

1 绪论

1.1 研究背景、目的及意义

1.2 国内外研究现状

1.3 本文的主要研究内容与创新之处

1.4 论文的组织结构

2 分布式约束优化问题与应用的研究基础

2.1分布式约束优化问题（DCOP）

2.2 DCOP求解算法的基本描述

2.3 传感器网络目标跟踪问题中已有的DCOP建模方法

3 特定传感器网络目标跟踪问题的DCOP建模

3.1 引言

3.2 问题描述与图多着色问题的引入

3.3 前提与假设

3.4 模型描述

3.5 本章小结

4 适用于agent控制多变量模型的DCOP求解近似算法

4.1 引言

4.2 预处理策略

4.3 算法描述

4.4 仿真实验

4.5 本章小结

5 DCOPSolver平台模块实现

5.1 引言

5.2 DCOPSolver平台简介

5.3 传感器网络目标跟踪模块

5.4 本章小结

6 总结与展望

6.1 论文工作总结

6.2 工作展望

致谢

参考文献

附录

A. 作者在攻读研究生学位期间发表及录用的论文目录

B. 作者在攻读硕士学位期间参加的科研项目