基于序列貪婪優(yōu)化的分布式無(wú)線傳感器網(wǎng)絡(luò)定位算法

1、基于序列貪婪優(yōu)化的分布式無(wú)線傳感器網(wǎng)絡(luò)定位算法摘要：節(jié)點(diǎn)的定位對(duì)大多數(shù)無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用來(lái)說(shuō)是非常必要的。在本文中，我們要考慮在測(cè)量距離、無(wú)線電范圍以及信標(biāo)節(jié)點(diǎn)位置都不確定時(shí)，基于測(cè)距的節(jié)點(diǎn)定位和無(wú)需測(cè)距的節(jié)點(diǎn)定位這兩種定位方式的定位情況。首先，我們將這個(gè)貪婪優(yōu)化算法命名為序列貪婪優(yōu)化(SGO)算法，因?yàn)檫@個(gè)算法跟傳統(tǒng)的非線性高斯-賽德爾算法相比更適合分布式網(wǎng)絡(luò)優(yōu)化。其次，我們提出一個(gè)統(tǒng)一的優(yōu)化框架，可用于基于測(cè)距的定位和無(wú)需測(cè)距的定位，并且在半定規(guī)劃(SDP)松弛技術(shù)的基礎(chǔ)上獲得兩個(gè)凸定位規(guī)劃。第三，我們一方面將SGO算法應(yīng)用到基于邊緣的SDP松弛規(guī)劃中去，通過(guò)分析得出了一個(gè)以二階錐規(guī)劃(

2、SOCP)為基礎(chǔ)的分布式節(jié)點(diǎn)定位算法；另一方面，我們將SGO算法應(yīng)用到非凸定位規(guī)劃中去，同樣也得出了兩個(gè)分布式細(xì)化SGO算法。以上這些定位算法都可以實(shí)現(xiàn)網(wǎng)絡(luò)的部分異步。最后，通過(guò)大量的模擬演示可以展現(xiàn)所提出的這些分布式定位算法的效率和準(zhǔn)確性Qingjiang Shi，Chen He，Hongyang Chen，et al. Distributed Wireless Sensor Network LocalizationVia Sequential Greedy Optimization Algorithm J. IEEE Transactions on Signal Processing，20

3、10，58(6)：3328-3340.。關(guān)鍵詞：分布式優(yōu)化、基于測(cè)距的節(jié)點(diǎn)定位、無(wú)需測(cè)距的節(jié)點(diǎn)定位、二階錐規(guī)劃(SOCP)、半定規(guī)劃(SDP)、序列貪婪優(yōu)化算法(SGO)、無(wú)線傳感器網(wǎng)絡(luò)(WSN)。1、引言無(wú)線傳感器網(wǎng)絡(luò)(WSN)由大量微小的、低功耗的、隨機(jī)部署的傳感器節(jié)點(diǎn)組成，這些節(jié)點(diǎn)都具有傳感、處理和通信能力。大多數(shù)無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用，比如說(shuō)環(huán)境監(jiān)測(cè)、搜索和救援、目標(biāo)追蹤等等，都需要傳感器節(jié)點(diǎn)的位置信息。一般情況下，出于經(jīng)濟(jì)上的考慮，在這些大量的傳感器節(jié)點(diǎn)當(dāng)中，只有一小部分節(jié)點(diǎn)的位置信息是通過(guò)全球定位系統(tǒng)(GPS)測(cè)量得出的或是由手動(dòng)配置得到的(這些節(jié)點(diǎn)通常被稱為信標(biāo)節(jié)點(diǎn))，而其它節(jié)點(diǎn)的

4、位置信息都是通過(guò)定位算法測(cè)算出來(lái)的，這種方式尤其適合在大規(guī)模的傳感器網(wǎng)絡(luò)中使用。因此，開發(fā)出一套高效的節(jié)點(diǎn)自定位算法是無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用的必要條件。傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)定位，主要包括基于測(cè)距的定位和無(wú)需測(cè)距的定位。基于測(cè)距的定位需要獲得節(jié)點(diǎn)之間的測(cè)量距離，這個(gè)測(cè)量距離可以通過(guò)接收到的信號(hào)強(qiáng)度(RSS)或到達(dá)時(shí)間(TOA)等測(cè)距方式獲得，而無(wú)需測(cè)距的定位只需使用連接信息(例如，一個(gè)節(jié)點(diǎn)是否是在另一個(gè)節(jié)點(diǎn)的傳輸范圍內(nèi))就可以實(shí)現(xiàn)，相應(yīng)地，定位算法就可以分為基于測(cè)距的定位算法和無(wú)需測(cè)距的定位算法?；跍y(cè)距的定位算法跟無(wú)需測(cè)距的定位算法相比，定位精度更高，但是無(wú)需測(cè)距的定位算法更加便宜、簡(jiǎn)單，因?yàn)樗恍?/p>

5、要配備特殊的硬件來(lái)完成測(cè)距。另一方面，根據(jù)計(jì)算模式的不同，可以將定位算法分為集中式算法和分布式算法。集中式算法要求將所有的測(cè)量距離或者節(jié)點(diǎn)之間的連通信息都傳送到一個(gè)融合中心(例如，匯聚節(jié)點(diǎn))進(jìn)行處理，這樣一來(lái)就會(huì)產(chǎn)生大量的通信能耗和帶寬消耗，從而縮短整個(gè)網(wǎng)絡(luò)的壽命。分布式算法能源的有效性高，并且隨著網(wǎng)絡(luò)的大小可進(jìn)行擴(kuò)展，分布式節(jié)點(diǎn)定位的總體任務(wù)就是讓所有節(jié)點(diǎn)跟它相鄰的節(jié)點(diǎn)進(jìn)行信息交換。因此，對(duì)大規(guī)模的傳感器網(wǎng)絡(luò)而言，分布式定位算法更具吸引力。目前針對(duì)傳感器網(wǎng)絡(luò)的定位，人們提出了很多定位算法。在無(wú)需測(cè)距的定位算法中，就存在啟發(fā)式的、操作簡(jiǎn)單的、允許分布式實(shí)現(xiàn)的定位算法，但是這些算法一般都是不精確

6、的，并且只在信標(biāo)節(jié)點(diǎn)的定位中使用。Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz三個(gè)人在經(jīng)典多維尺度(MDS)技術(shù)的基礎(chǔ)上，提出了一組定位算法，這組算法可以同時(shí)適用于基于測(cè)距的定位和無(wú)需測(cè)距的定位，并且明顯地優(yōu)于啟發(fā)式的定位算法。在他們所提出的所有這些算法中，MDS-MAP(P，R)算法對(duì)不規(guī)則網(wǎng)絡(luò)的定位能力是最好的，但是這種算法卻非常復(fù)雜、昂貴，最復(fù)雜也最貴的就是它的核心戰(zhàn)略，即首先為每個(gè)節(jié)點(diǎn)建立一個(gè)本地地圖，然后將這些本地地圖合并起來(lái)形成一個(gè)全局地圖，在形成本地地圖的過(guò)程中需要用到集中式算法，所以盡管MDS-MAP(P，R)算法可以在網(wǎng)絡(luò)中實(shí)現(xiàn)，但

7、是卻不適合在大規(guī)模的網(wǎng)絡(luò)中使用。因此，另外一個(gè)算法度量MDS算法隨之被提出，主要適用在基于測(cè)距的定位當(dāng)中，而且這個(gè)算法特別適合用分布式實(shí)現(xiàn)，但是，度量MDS算法是局部收斂的，這就意味著它的定位性能很差，除非能夠提供一個(gè)很好的初始化條件才能提高它的定位性能。在這種情況之下，J. Liu, Y. Zhang和 F. Zhao提出來(lái)一個(gè)強(qiáng)大的基于多邊的迭代定位算法，這種算法適用在基于測(cè)距的定位中，它的權(quán)重很小，因而很適合分布式實(shí)現(xiàn)，但是，這種算法的收斂性沒(méi)有理論保障?；谕箖?yōu)化的定位算法具有很好的全局收斂性，所以在傳感器網(wǎng)絡(luò)定位中很受歡迎。這種定位算法大部分都用在基于測(cè)距的定位中，只有少數(shù)用于無(wú)需測(cè)

8、距的定位中。但是這些定位算法都有一個(gè)相同的處理方式，那就是將定位問(wèn)題看成非線性優(yōu)化問(wèn)題，將由此產(chǎn)生的問(wèn)題看成是凸優(yōu)化問(wèn)題，最后利用高效的內(nèi)點(diǎn)算法來(lái)求解。凸松弛技術(shù)涉及到兩個(gè)算法：二階錐規(guī)劃(SOCP)算法和半定規(guī)劃(SDP)算法。在大規(guī)模網(wǎng)絡(luò)(成千上萬(wàn)個(gè)節(jié)點(diǎn))中使用基于SDP的算法是非常昂貴的，因?yàn)樗兄浅?fù)雜的結(jié)構(gòu)，這就要求它需要必須進(jìn)行集中式計(jì)算。為了減少計(jì)算負(fù)荷，有人提出一種基于集群的SDP定位算法，雖然這種算法可以在網(wǎng)絡(luò)中實(shí)現(xiàn)，但是它并不是一個(gè)很好的分布式算法，原因在于：1、這種算法首先要求形成集群，但是這樣會(huì)產(chǎn)生額外的通信費(fèi)用；2、每個(gè)集群都要使用集中式算法；3、如果沒(méi)有足夠的信標(biāo)

9、節(jié)點(diǎn)，這種算法就會(huì)失效。而減少計(jì)算負(fù)荷的另外一種方法就是近一步讓基于測(cè)距的定位問(wèn)題松弛化，在這個(gè)基礎(chǔ)上提出基于節(jié)點(diǎn)的SDP松弛算法和基于邊緣的SDP松弛算法，雖然這兩個(gè)松弛算法比一般的SDP松弛算法的定位效果要差，但是它們都能保證計(jì)算的有效性和精確性。跟SDP松弛算法相比，SOCP松弛算法雖然定位效果較弱(因此不準(zhǔn)確)，但是它的結(jié)構(gòu)更簡(jiǎn)單，而且允許有效的分布式方式實(shí)現(xiàn)。有人想出了一種基于SOCP算法的完全異步的分布式定位算法，適用于基于測(cè)距的定位，很快地，這個(gè)算法就被擴(kuò)展到無(wú)需測(cè)距的定位中去。但是，提出完全異步的分布式定位算法的作者只在數(shù)值上展示了這個(gè)算法的收斂性，而沒(méi)有展示理論上的收斂性。考

10、慮到測(cè)量距離和節(jié)點(diǎn)之間的連通信息會(huì)產(chǎn)生各種約束限制條件，新的基于不可微優(yōu)化的定位規(guī)劃被提出，可以用在基于測(cè)距的定位和無(wú)需測(cè)距的定位中。不同于基于凸優(yōu)化的定位算法，基于不可微優(yōu)化的定位算法產(chǎn)生的不可微問(wèn)題都可以利用規(guī)范化的遞增梯度(NIS)算法得到有效解決?；贜IS的定位算法跟以往的算法（例如由dwMDS方法細(xì)化的非常強(qiáng)大的SDP方法、MDS-MAP方法等）相比，定位性能更好，但是，這種算法的分布式實(shí)現(xiàn)要求預(yù)先構(gòu)建一條能連通所有節(jié)點(diǎn)的路徑。上述這些定位算法都有準(zhǔn)確的信標(biāo)節(jié)點(diǎn)位置信息，但是事實(shí)上，信標(biāo)節(jié)點(diǎn)位置不能精確得到，原因有兩個(gè)方面，一是民用GPS的精度是有限的，二是人工觀測(cè)會(huì)帶來(lái)一定的誤差

11、。另一方面，節(jié)點(diǎn)的最大無(wú)線電范圍存在不確定性，這是由無(wú)線電的不規(guī)則性決定的。在本文中，我們考慮當(dāng)測(cè)量距離、無(wú)線電范圍及信標(biāo)節(jié)點(diǎn)位置存在不確定性時(shí)，對(duì)基于測(cè)距的定位產(chǎn)生的問(wèn)題和無(wú)需測(cè)距的定位產(chǎn)生的問(wèn)題進(jìn)行研究。在貪婪優(yōu)化算法的基礎(chǔ)上，我們提出了兩種分布式定位算法用于基于測(cè)距的定位和無(wú)需測(cè)距的定位，這兩種分布式定位算法都可以實(shí)現(xiàn)部分的網(wǎng)絡(luò)異步。最后，通過(guò)大量的模擬演示可以展現(xiàn)所提出的這兩種分布式定位算法的效率和準(zhǔn)確性。我們主要的貢獻(xiàn)在于以下三個(gè)方面：（1）提出序列貪婪優(yōu)化（SGO）算法，并對(duì)它的收斂性進(jìn)行了證明和分析。SGO算法是非線性高斯-賽德爾算法的自然延伸，而且它更適應(yīng)網(wǎng)絡(luò)中的分布式優(yōu)化。（

12、2）為無(wú)線傳感器網(wǎng)絡(luò)提出一個(gè)統(tǒng)一的優(yōu)化框架，并在半定規(guī)劃（SDP）松弛技術(shù)的基礎(chǔ)上得到兩個(gè)凸定位規(guī)劃。利用SGO算法，我們首次表明基于邊緣的SDP（ESDP）松弛規(guī)劃在網(wǎng)絡(luò)中產(chǎn)生的問(wèn)題可以用分布式的方法解決，主要就是通過(guò)解決一系列的二階錐規(guī)劃問(wèn)題。（3）我們提出的分布式細(xì)化算法可以進(jìn)一步提高定位精度，它將SGO算法運(yùn)用到非凸定位規(guī)劃中，適用于基于測(cè)距的定位和無(wú)需測(cè)距的定位。本文的其余部分安排如下：在下一節(jié)我們將展示SGO算法并證明它的收斂性。在第三節(jié)中，我們提出用于傳感器網(wǎng)絡(luò)定位的統(tǒng)一的優(yōu)化框架，在此基礎(chǔ)上得到兩個(gè)凸規(guī)劃；另一方面，利用ESDP公式和細(xì)化算法提出分布式定位算法。第四節(jié)提供了多組

13、實(shí)驗(yàn)數(shù)值形象展示所提出的定位算法的性能，第五部分對(duì)整篇論文進(jìn)行總結(jié)。在本文中，我們用大寫黑體字表示向量矩陣，小寫黑體字表示矢量，普通字體表示標(biāo)量。表示n維歐式空間，表示笛卡爾積集。表示集的基數(shù)。下標(biāo)T表示轉(zhuǎn)置，表示零矢量，表示由i個(gè)元素組成的一個(gè)單位列向量，它的大小根據(jù)上下文可知。表示大小的單位矩陣。對(duì)于一個(gè)對(duì)稱矩陣,表示矩陣的第項(xiàng)，表示從行列中提取的主子矩陣。對(duì)于對(duì)稱矩陣A和對(duì)稱矩陣B，表示是正定的，表示矩陣A和矩陣B的Frobenius內(nèi)積。對(duì)于向量a和向量b來(lái)說(shuō)，表示的是判斷不等式，表示向量a和向量b的分支乘法。2.序列貪婪優(yōu)化算法對(duì)多變量問(wèn)題人們已經(jīng)提出了很多優(yōu)化算法，但是這些優(yōu)化算法

14、中大多數(shù)還是屬于基于搜索方向范疇的迭代算法。跟一般的迭代優(yōu)化算法相比，存在一種特殊的迭代算法，這種迭代算法中，決策變量被劃分為一個(gè)個(gè)獨(dú)立的塊，在每次迭代過(guò)程中，目標(biāo)函數(shù)被最小化在區(qū)域中某一個(gè)獨(dú)立塊中，而其余的獨(dú)立塊依舊固定不動(dòng)。這種類型的算法有時(shí)也被稱為交替最小化算法、協(xié)調(diào)下降算法、或非線性高斯賽德爾（NGS）算法。值得注意的是，前兩個(gè)算法(交替最小化算法、協(xié)調(diào)下降算法)是最后一個(gè)算法(NGS算法)的特殊情況，因此，我們只討論NGS算法。NGS算法適用于無(wú)約束最優(yōu)化問(wèn)題或笛卡爾積集約束問(wèn)題，它之所以是貪婪的優(yōu)化算法主要表現(xiàn)在它可以保證目標(biāo)函數(shù)在每一次迭代之后不增加，最重要的一點(diǎn)是，使用NGS算

15、法，一個(gè)復(fù)雜的多變量問(wèn)題可以分解成一系列小規(guī)模的子問(wèn)題，而且這個(gè)分解實(shí)施過(guò)程也很容易實(shí)現(xiàn)，即使是在分布式算法中（把子問(wèn)題分配給不同的處理器）也很容易實(shí)現(xiàn)。在本節(jié)中，我們將NGS算法擴(kuò)展為一個(gè)更一般的形式，也就是把生成算法當(dāng)做SGO算法。在SGO算法中，決策變量并沒(méi)有被嚴(yán)格地分割成獨(dú)立的模塊，換句話說(shuō)，也就是SGO算法允許一些決策變量在不同的子問(wèn)題中獨(dú)立擴(kuò)展，這個(gè)擴(kuò)展是很自然的，因?yàn)樗筍GO算法變得更適合分布式網(wǎng)絡(luò)優(yōu)化。本節(jié)的另外一項(xiàng)重要工作就是使用一階的KarushKuhnTucker(KKT)條件，但是不對(duì)凸目標(biāo)函數(shù)和約束集進(jìn)行假設(shè)，在這種條件下對(duì)SGO算法的收斂性進(jìn)行分析和證明。除此之外

16、，我們還討論在約束耦合(即不是笛卡爾乘積型)條件下，SGO算法在一般優(yōu)化問(wèn)題中的應(yīng)用。A、算法如果一個(gè)優(yōu)化問(wèn)題可以寫成以下形式，我們就說(shuō)它屬于稀疏約束。（1）其中，是一個(gè)正整數(shù)，；是可微函數(shù)；和，是非負(fù)整數(shù)。我們假設(shè)的最小值存在，并且是有限的。請(qǐng)注意，意味著沒(méi)有不等式（等式）條件的約束；尤其當(dāng)所有的和都是0的情況下，公式（1）可以理解為一種特殊的稀疏約束問(wèn)題，即一個(gè)無(wú)約束的優(yōu)化問(wèn)題。在NGS算法中，將子問(wèn)題依次最小化，假設(shè)是每一個(gè)的嚴(yán)格凸函數(shù)。但是，如果給定一個(gè)，就很難獲得子問(wèn)題的全局最優(yōu)解。在這里，我們將使用一個(gè)新的運(yùn)算符“dec”而不是“min”來(lái)描述SGO算法。迭代算法中使用的這個(gè)新的運(yùn)

17、算符的定義如下： （2）其中是一個(gè)可微函數(shù)，表示重復(fù)k次，是的局部最小值，它通過(guò)一定的優(yōu)化方法和來(lái)確定。需要注意的是，一旦選擇了具體的優(yōu)化方法（即，該算法規(guī)則確定了），就唯一確定了。例如，我們可以利用下降法達(dá)到到下降過(guò)程中的一個(gè)局部最小值，式（2）給這個(gè)含義做了一個(gè)很好的定義。除此之外，我們將使用下列符號(hào)來(lái)描述算法：設(shè)是的子集，并且和是第i個(gè)指標(biāo)集。如果，并且那么在SGO 算法中，這就意味著變量不僅能在問(wèn)題1中被優(yōu)化，而且能在子問(wèn)題2和5中被優(yōu)化。SGO算法的描述如下：假設(shè)一個(gè)隨機(jī)初始化變量。在經(jīng)過(guò)k-1次迭代后得到，然后依次執(zhí)行p的貪婪步驟或第k次子迭代。 （3）最后，得到，其中表示第k次迭代后得到的新的()。B收斂性分析和討論一