分布式約束優(yōu)化在傳感器網(wǎng)絡目標跟蹤問題中的應用研究.pdf

1、分布式約束優(yōu)化問題（DCOP）是一種用于解決多Agent系統(tǒng)協(xié)作優(yōu)化問題的重要建模方式，具有隱私性、信息局部性、控制分散化等特點。目前對該領域的研究主要是算法理論方面的研究，應用研究較少。在DCOP的應用研究中，傳感器網(wǎng)絡是一個主要的應用領域。傳感器網(wǎng)絡中目標跟蹤問題較適用于DCOP建模，受到了廣泛關注。但是目前對該問題的DCOP建模存在一些問題，例如模型定義不清晰或缺乏現(xiàn)實物理意義。本文針對該問題，為一類傳感器網(wǎng)絡的目標跟蹤問題提出了

2、一種具有現(xiàn)實物理意義的DCOP模型，并提出了適用于該模型的求解算法，具體研究工作如下：
　　1.介紹了傳感器網(wǎng)絡目標跟蹤問題的研究現(xiàn)狀，并對使用非分布式方式和使用DCOP建模這兩種方式在該問題上研究的重點進行了分析和比較。然后，具體介紹了DCOP的基本定義以及其約束圖表述，并較詳細地介紹了DSA和MGM兩種DCOP近似求解算法。此外，詳細描述了傳感器網(wǎng)絡目標跟蹤問題的幾類DCOP建模方法，并闡述了這些模型的優(yōu)缺點。
　　2.

3、將一類傳感器網(wǎng)絡目標跟蹤問題抽象為一種圖多著色問題，并針對圖多著色問題提出兩種不同的DCOP模型：ACSV和ACMV。ACSV模型采用一個agent控制一個變量的方式，它的最大特點是變量的取值是一個顏色集合，而不是一個單獨的值；ACMV模型采用一個agent控制多變量的方式，它的最大特點是每個變量不僅僅需要考慮外部約束，同時必須滿足內(nèi)部約束。然后對這兩種模型的優(yōu)缺點進行比較。
　　3.基于DSA和MGM，提出了兩種用于解決圖多著色

4、問題的分布式約束優(yōu)化算法MGCDSA和MGCMGM。針對圖多著色問題，MGCDSA和MGCMGM添加了新的預處理過程：“剪枝”和“降維”。剪枝用于忽略每個agent中沒有外部約束關系的變量，降維可以減小兩個變量之間約束代價矩陣的維度。實驗證明了這兩種算法都可以較好地解決圖多著色問題。
　　4.對現(xiàn)有的分布式約束優(yōu)化問題平臺DCOPSolver進行了擴充，添加了傳感器網(wǎng)絡目標跟蹤問題對應的圖多著色問題生成和解析模塊，并對平臺中的通信