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

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

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

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

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