基于改進(jìn)型粒子群優(yōu)化的節(jié)點自定位算法

劉志坤，劉忠，唐小明

(1.海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢，430033；2.海軍航空工程學(xué)院 信息融合技術(shù)研究所，山東 煙臺，264001)

節(jié)點自定位技術(shù)是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，這是因為在無線傳感器網(wǎng)絡(luò)的應(yīng)用中，各個傳感器所獲取的數(shù)據(jù)必須與位置信息相結(jié)合，只有在確定節(jié)點位置信息后，才能進(jìn)一步指導(dǎo)節(jié)點的行為，靈活地調(diào)整路由，節(jié)約能耗，提高網(wǎng)絡(luò)的性能。雖然通過搭載 GPS(全球定位系統(tǒng))是獲取節(jié)點地理位置信息最便捷的途徑，但是對于一個節(jié)點眾多的無線傳感器網(wǎng)絡(luò)而言，如果給每個節(jié)點都配備GPS將造成驚人的成本，顯然是不現(xiàn)實的。此外，GPS的使用會受限于遮擋條件，在很多環(huán)境下無法使用(例如水下)，因此必

須尋求其他的解決途徑。根據(jù)定位機(jī)制的不同，目前的節(jié)點自定位方法可分為 2類[1?2]：基于距離(Range-based)的方法和距離無關(guān)(Range-free)的方法。相對于距離無關(guān)的方法，基于距離的方法能夠獲得更高的定位精度。這類算法通過接收信號強(qiáng)度(RSSI)[3]、不同信號的到達(dá)時間差(TDOA)[4]、到達(dá)角度(AOA)[5]或是到達(dá)時間(TOA)[6]等方法測得節(jié)點間距離，根據(jù)距離信息進(jìn)行定位。常用的方法有：三邊定位法、改進(jìn)bounding box法、三角定位法和最小二乘估計法等。然而，這幾種方法受測距誤差的影響較大，最小二乘估計法雖然一定程度上降低了這種影響，但是定位精度高。而在實際環(huán)境中，受外在條件的影響，測距誤差非但難以避免，有時甚至較大。這種情況下，以上的幾種方法就顯得無能為力。為了克服測距誤差對定位精度的影響，近年來很多學(xué)者做了大量的工作。文獻(xiàn)[7]提出了一種基于粒子群的節(jié)點自定位算法，一定程度上提高了定位精度。但是由于粒子群優(yōu)化算法(PSO)自身存在進(jìn)化后期易陷入局部極小點、易早熟收斂的缺陷，使得該方法對定位精度提高有限。針對這些缺陷，本文作者對傳統(tǒng)的PSO算法進(jìn)行了改進(jìn)：將混沌搜索引入PSO并將其應(yīng)用于節(jié)點自定位領(lǐng)域，利用混沌搜索具有的規(guī)律性、隨機(jī)性和遍歷性，改善算法的性能，從而提高節(jié)點的定位精度。

1 改進(jìn)型粒子群優(yōu)化算法

粒子群優(yōu)化算法是一種基于種群搜索策略的全局優(yōu)化算法[8?9]，它的優(yōu)勢在于構(gòu)造簡單、易于實現(xiàn)、搜索速度快，因此在科研和工程領(lǐng)域得到了廣泛應(yīng)用。

PSO算法的具體搜索過程是：在空間中初始化一群隨機(jī)粒子，每個粒子代表解空間內(nèi)的一個隨機(jī)解，粒子在搜索空間內(nèi)飛行，根據(jù)其自身經(jīng)驗和整個群體的經(jīng)驗動態(tài)調(diào)整自己的速度，通過迭代找到最優(yōu)解，在每一次迭代中，粒子通過跟蹤2個“極值”來更新自己：一個是粒子本身所能找到的最優(yōu)解，稱為個體極值；另一個極值是整個種群目前找到的最優(yōu)解，稱為全局極值。在找到這2個最優(yōu)值后，每個粒子根據(jù)式(1)和(2)來更新自己的速度和位置[9]，當(dāng)算法執(zhí)行到預(yù)先設(shè)定的最大迭代次數(shù)或者粒子群當(dāng)前搜索到的最優(yōu)解位置滿足預(yù)定最小適應(yīng)度閾值時，停止迭代計算，輸出當(dāng)前的全局最優(yōu)解。

其中，vk為粒子的速度向量；xk為當(dāng)前粒子的位置；pbestk為粒子本身所找到的最優(yōu)解的位置；gbestk為整個種群目前找到的最優(yōu)解的位置；vk+1為vk，pbestk?xk和gbestk?xk矢量和；慣性權(quán)重c0一般取介于(0，1)之間的隨機(jī)數(shù)，用于保持粒子的運動慣性，使其具有擴(kuò)展搜索空間的能力，當(dāng)它取較大值時，有利于跳出局部極小值，當(dāng)它取較小值時，有利于算法收斂。加速常數(shù)c1，c2取(0，2)之間的隨機(jī)數(shù)，分別為將每個粒子推向pbest和gbest位置的統(tǒng)計加速項的權(quán)重。加速權(quán)重較小時，允許粒子在被拉回來之前可以在目標(biāo)區(qū)域外徘徊，值較高時則導(dǎo)致粒子突然沖向或超過目標(biāo)區(qū)域。c0，c1，c2在取值范圍內(nèi)隨機(jī)選定后，在算法執(zhí)行過程中作為常數(shù)出現(xiàn)，不再改變以免造成結(jié)果的不穩(wěn)定，導(dǎo)致無法進(jìn)行相應(yīng)的評估比較。

粒子群算法在搜索過程中利用式(1)和(2)更新自己的速度和位置，其本質(zhì)是利用本身信息、個體極值信息和全局極值3個信息，來指導(dǎo)粒子下一步迭代位置。這實際上是一個正反饋過程，當(dāng)其本身信息和個體極值信息占優(yōu)勢時，該算法很容易陷入局部最優(yōu)解[10?11]。在傳感器網(wǎng)絡(luò)中信標(biāo)節(jié)點數(shù)量較少，搜索區(qū)間較大的情況下，應(yīng)用該算法進(jìn)行節(jié)點自定位，這一問題就更加凸現(xiàn)，將限制定位精度的提高。

根據(jù)最優(yōu)化理論領(lǐng)域的 NFL(No free lunch theorem)定理[12]，沒有一種算法對任何問題的解都是最優(yōu)的。因此，需要分析不同算法的特點，針對某一實際問題，融合不同算法的各自優(yōu)勢，構(gòu)造出適應(yīng)該問題的新算法?；谶@一思路本文對PSO算法進(jìn)行改進(jìn)。

混沌是存在于非線性系統(tǒng)中的一種貌似隨機(jī)的運動形式，是確定性系統(tǒng)內(nèi)在隨機(jī)性的表現(xiàn)，它具有隨機(jī)性，遍歷性和規(guī)律性3個特點[13]。混沌的這些特征，十分有利于PSO的優(yōu)化和改進(jìn)：隨機(jī)性有利于算法獲得大范圍搜索能力，遍歷性使得最終解有能力逼近最優(yōu)解，規(guī)律性可以保證算法使用固定的迭代方程，從而便于編程計算。改進(jìn)后的算法思路是：首先初始化種群，設(shè)定種群數(shù)量n、迭代次數(shù)M、慣性權(quán)重c0、加速常數(shù)c1和c2等。而后計算每個粒子的適應(yīng)度，選出個體極值和全局極值，利用式(1)和(2)開始迭代尋優(yōu)過程。此迭代過程與之前的不同之處在于：當(dāng)運算到預(yù)先設(shè)定的次數(shù)后，啟動混沌搜索，對歷史最優(yōu)解gbest施加混沌擾動，獲得最優(yōu)解gbest′，計算其適應(yīng)值s′并與歷史最優(yōu)解s的適應(yīng)值進(jìn)行比較，如果s′＜s(即加入混沌擾動后的最優(yōu)解優(yōu)于歷史最優(yōu)解)，則選取gbest′作為新的全局最優(yōu)解繼續(xù)迭代計算。

以往的研究通常使用logistic映射產(chǎn)生混沌擾動，但是根據(jù)文獻(xiàn)[14]的結(jié)論，Tent映射的遍歷均勻性優(yōu)于logistic映射，可以獲得更高的搜索尋優(yōu)效率，因此本文采用Tent映射作為混沌擾動產(chǎn)生器，它的表達(dá)式如下[15]：

產(chǎn)生混沌點列的過程如下：

(1)設(shè)粒子的n維位置向量為xi=(xi1，xi2，…，xin)，根據(jù)(4)把xi的每一維xik，k=1，…，n，映射到[0，1]區(qū)間上得到向量yi=(yi1，yi2，…，yin)；

其中，bk和ak分別是第k維變量xik的上界和下界。

(2)yi中的每一維yik根據(jù)式(3)進(jìn)行變異，產(chǎn)生混沌序列；

(3)由式(5)將混沌序列中的點映射回原空間，得到xi經(jīng)過 Tent映射后的混沌點列：

2 節(jié)點自定位算法

本文提出的節(jié)點自定位算法的特點在于充分考慮到了傳統(tǒng)PSO存在的早熟收斂缺陷，對粒子群優(yōu)化計算出新位置進(jìn)行混沌擾動，適當(dāng)擴(kuò)展了粒子的搜索范圍，使解有能力跳出局部極值區(qū)間。由于PSO算法一般是在迭代后期陷入局部最優(yōu)，如果從算法一開始就加入混沌搜索，缺乏必要性而且會增加算法的復(fù)雜度和計算量，因此可根據(jù)實際經(jīng)驗在PSO迭代后期對粒子的最優(yōu)解加入混沌擾動。應(yīng)用在節(jié)點自定位時體現(xiàn)為以相對較少的錨節(jié)點數(shù)目，在更大的布設(shè)范圍內(nèi)，獲取更高的定位精度。其中，混沌擾動按照上節(jié)的描述產(chǎn)生。以三維空間節(jié)點自定位為例，新定位方法的具體實現(xiàn)步驟如下：

(1)在三維空間內(nèi)初始化一定數(shù)量的粒子群，設(shè)定粒子數(shù)為n，隨機(jī)產(chǎn)生n個初始位置和n個初始速度；

(2)計算每個粒子的適應(yīng)值，選擇適應(yīng)值最小的粒子作為全局極值gbest，選擇各個粒子的初始位置作為個體極值pbest。適應(yīng)值的計算公式如下：

其中，ri是未知節(jié)點到第i個信標(biāo)節(jié)點的距離；R是信標(biāo)節(jié)點的覆蓋半徑，距離信息可以通過接收信號強(qiáng)度(RSSI)、到達(dá)時間差(TDOA)、到達(dá)角度(AOA)或是到達(dá)時間(TOA)等方法測得，因此在本文屬已知量。如果未知節(jié)點不在信標(biāo)節(jié)點的覆蓋半徑內(nèi)，適應(yīng)值就取一個設(shè)定好的極大值，使之在迭代計算中被淘汰；

(3)迭代進(jìn)行到預(yù)先設(shè)定的次數(shù)時，啟動混沌搜索，設(shè)此時的歷史最優(yōu)解對應(yīng)的坐標(biāo)向量xik=(xik1，xik2，xik3)，根據(jù)式(3)和(4)，式(5)產(chǎn)生新的坐標(biāo)，，+vk+1，計算這2個位置的適應(yīng)值s和s′。若s′＜s，則??；

(5)當(dāng)?shù)螖?shù)達(dá)到設(shè)定值后，退出循環(huán)，輸出全局極值對應(yīng)的坐標(biāo)。

此算法的特點在于在普通PSO的基礎(chǔ)上，通過引入混沌理論增強(qiáng)了算法的全局搜索能力，避免過早收斂陷入局部極值點，應(yīng)用在節(jié)點自定位時有助于提高定位精度。

3 試驗及結(jié)果分析

為了檢測新算法的定位性能，本文對其進(jìn)行了仿真試驗。在試驗中，首先將改進(jìn)型粒子群優(yōu)化算法與普通粒子群優(yōu)化算法進(jìn)行比較，以驗證前者相對普通算法的性能改善，而后將本文提出的節(jié)點自定位算法與目前節(jié)點自定位領(lǐng)域廣泛使用的最小二乘估計法進(jìn)行定位精度比較。

3.1 改進(jìn)型PSO與PSO的性能比較

試驗中采用2個典型的優(yōu)化測試函數(shù)來比較2種算法的性能。其中，Rastrigrin函數(shù)是一種病態(tài)多峰函數(shù)，具有廣闊的搜索空間，大量的局部極小點，可以有針對性地檢驗新算法的改進(jìn)。Rosebrock函數(shù)則是一個病態(tài)單峰函數(shù)，該函數(shù)為優(yōu)化算法提供的搜索信息較少，使算法難以找到全局極小點，可以用來檢測新算法的執(zhí)行效率。

(1)Rastrigrin函數(shù)

(2)Rosebrock函數(shù)

2個函數(shù)理論上的全局最優(yōu)解都是 0，試驗中取50個粒子，設(shè)慣性權(quán)重c0取為0.729 8，加速常數(shù)c1和c2取為1.496 2，最大速度為5，迭代次數(shù)設(shè)為1 000次。為減小誤差，對每個函數(shù)的測試獨立運行30次取平均值。表1所示為采用PSO和改進(jìn)型PSO分別對2個函數(shù)求解的結(jié)果。

從仿真結(jié)果可以看出：隨著搜索維數(shù)的增加，2個函數(shù)求得的最優(yōu)解距離真實最優(yōu)解的誤差越來越大，這是由于維數(shù)越高，其搜索難度越大。改進(jìn)型PSO的平均搜索結(jié)果在各個維數(shù)級上明顯優(yōu)于PSO算法，這驗證了迭代過程后期的混沌擾動提高了算法的全局搜索能力。測試結(jié)果說明：改進(jìn)型PSO算法有效地提高了搜索精度。

3.2 改進(jìn)型PSO定位算法與最小二乘估計法比較

在驗證了改進(jìn)型PSO算法相對普通PSO算法性能提高后，將其應(yīng)用在節(jié)點自定位領(lǐng)域，將新定位算法與被廣泛采用的最小二乘估計法進(jìn)行比較。試驗場景設(shè)置為一個100 m×100 m×100 m的三維空間，網(wǎng)絡(luò)規(guī)模為200個節(jié)點，信標(biāo)節(jié)點隨機(jī)布放在此區(qū)間，節(jié)點的通信半徑設(shè)為60 m，慣性權(quán)重c0取為0.729 8，加速常數(shù)c1和c2取為1.496 2，最大速度為5。試驗結(jié)果的優(yōu)劣用平均定位誤差來評估，平均定位誤差定義為：

其中：N為參與定位統(tǒng)計的未知節(jié)點數(shù)量，(xireal，yireal，zireal)為第i個未知節(jié)點的真實位置，(xi，yi，zi)為第i個節(jié)點的測量位置。

(1)不同測距誤差情況下基于改進(jìn)型PSO的定位算法與最小二乘估計法比較。

在實際應(yīng)用中，測量節(jié)點間的距離信息不可能做到嚴(yán)格準(zhǔn)確，現(xiàn)有的測距方法一般都會伴隨一定的誤差。因此有必要測試測距誤差對定位算法的影響。試驗中誤差依次取真實距離的5%，10%，15%，20%，25%，30%，信標(biāo)節(jié)點數(shù)取30。試驗結(jié)果如圖1所示。

從圖1可以看出，在各個測距誤差級上，新算法的定位誤差均低于最小二乘估計法，特別是在測距誤差增加到 5%以上時，新算法的優(yōu)勢更為明顯，其定位誤差隨測距誤差增大的上升趨勢也明顯較低。當(dāng)測距誤差在30%以內(nèi)時，新算法的最大定位誤差為7.935 1 m，而最小二乘估計法最大誤差高達(dá)30.926 5 m，在測距誤差不超過15%的情況下，新算法的定位誤差在1 m左右，具有很高的精度。說明利用改進(jìn)型PSO的高效全局搜索能力，提高了節(jié)點自定位算法的魯棒性，在受到測距誤差影響時，獲得了相對較好的定位精度。

(2)不同信標(biāo)節(jié)點數(shù)量情況下基于改進(jìn)型PSO的定位算法與最小二乘估計法比較。

信標(biāo)節(jié)點的數(shù)量是一個評價無線傳感器網(wǎng)絡(luò)性能的重要指標(biāo)，信標(biāo)節(jié)點過多會增加系統(tǒng)成本、功耗，過少會降低定位精度，在信標(biāo)節(jié)點數(shù)量一定的情況下，不同算法的定位精度也會不同。試驗中信標(biāo)節(jié)點的數(shù)量依次為10，20，30，40，50，60個，測距誤差均取10%。試驗結(jié)果見表2。

仿真結(jié)果表明：在信標(biāo)節(jié)點數(shù)量相同時，新算法的平均定位誤差遠(yuǎn)低于最小二乘估計法。信標(biāo)節(jié)點數(shù)量為10和20時，平均定位誤差相對較大，從信標(biāo)節(jié)點數(shù)量為30開始，平均定位誤差急劇下降，之后誤差雖然仍會隨著信標(biāo)節(jié)點的數(shù)量增加而降低，但是降幅趨于平緩。分析原因認(rèn)為是粒子群算法對初始值位置依賴性較大，如果信標(biāo)節(jié)點太少，獲得的初始信息量也少，搜索難度增大，勢必造成誤差增加，但即使在信標(biāo)節(jié)點數(shù)量較少時，新算法的定位精度也遠(yuǎn)遠(yuǎn)高于最小二乘估計法的定位精度，例如，在信標(biāo)節(jié)點數(shù)目為10時，新定位算法的平均定位誤差為1.740 7 m，而最小二乘估計法的平均定位誤差為31.927 8 m。說明新定位算法比最小二乘估計法更適合信標(biāo)節(jié)點比較少的情況。而隨著信標(biāo)節(jié)點的數(shù)目不斷增加，到達(dá)一定數(shù)量后，由于搜索空間范圍不變，此時信標(biāo)節(jié)點數(shù)量的再增加就難以明顯地提升定位精度，因此定位精度趨于穩(wěn)定。

總之，隨著測距誤差的增大，2種算法的平均定位誤差也逐漸增大，在測距誤差相同的情況下，新算法的定位誤差比最小二乘估計法要小，其增長趨勢更緩慢；隨著信標(biāo)節(jié)點數(shù)量的增加，2種算法的平均定位誤差逐漸減小，在信標(biāo)節(jié)點數(shù)量和測距誤差相同的情況下，新算法的平均定位誤差比最小二乘估計法的要低。此外，如果增加新算法的迭代次數(shù)，能進(jìn)一步提高定位精度，但是這將帶來更大的數(shù)據(jù)處理量，實際網(wǎng)絡(luò)搭建中必須權(quán)衡處理。在同等條件下，新的定位算法較之傳統(tǒng)方法極大地提高了對未知節(jié)點的定位精度，性能更為優(yōu)越，能更好地應(yīng)對測距誤差較大、信標(biāo)節(jié)點不多的客觀條件限制。

表1 2種算法的測試結(jié)果Table 1 Test results of two algorithms

圖1 不同測距誤差時2種算法的定位誤差Fig.1 Localization error of two algorithms in different ranging error

表2 不同信標(biāo)節(jié)點數(shù)量時2種算法的平均定位誤差Table 2 Average localization error of two algorithms in different anchor nodes number

4 結(jié)論

(1)針對傳統(tǒng)PSO算法搜索后期易陷入局部極值的缺陷，將混沌搜索引入其中，利用混沌自身的隨機(jī)性，遍歷性和規(guī)律性等特點，提高了PSO算法的全局搜索能力，對Rastrigrin函數(shù)和Rosebrock函數(shù)的測試結(jié)果表明改進(jìn)后的PSO性能得到了提高。

(2)將改進(jìn)型PSO算法運用在無線傳感器網(wǎng)絡(luò)節(jié)點自定位領(lǐng)域，提出了一種基于距離的節(jié)點自定位算法，該算法較好地克服了測距誤差大和信標(biāo)節(jié)點數(shù)目少等因素對定位造成的負(fù)面影響，相比原有的最小二乘估計法大幅提高了定位精度，在無線傳感器網(wǎng)絡(luò)實際應(yīng)用中具有一定的價值。

[1]Girod L,Bychovskiy V,Elson J,et al.Locating tiny sensors in time and space: a case study[C]//Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors.New York: IEEE Press,2002:214?219.

[2]He T,Huang C D,Blum B M,et al.Range-free localization schemes in large scale sensor networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking.New York: ACM Press,2003: 81?95.

[3]鮑喜榮,張立立,張石.基于 RSSI的多維定標(biāo)迭代定位算法[J].東北大學(xué)學(xué)報,2009,30(12): 1694?1697.BAO Xi-rong,ZHANG Li-li,ZHANG Shi.The research of multi-dimensional scaling iterations localization algorithm based on RSSI[J].Journal of Northeastern University： Natural Science,2009,30(12): 1694?1697.

[4]孟令軍,王建亮,潘峰.基于 TDOA 定位機(jī)制的無線傳感器節(jié)點設(shè)計[J].傳感器與微系統(tǒng),2009,28(6):101?103.MENG Ling-jun,WANG Jian-liang,PAN Feng.Design of wireless sensor networks node based on TDOA localization mechanism[J].Transducer and Microsystem Technologies,2009,28(6): 101?103.

[5]Niculescu D,Nath B.Ad Hoc positioning system using AOA[C]//Proceedings of IEEE INFOCOM.San Francisco: IEEE Service Center,2003: 1734?1743.

[6]焦磊,邢建平,張軍,等.一種非視距環(huán)境下具有魯棒特性TOA無線傳感網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報,2007,20(7):1625?1629.JIAO Lei,XING Jian-ping,ZHANG Jun,et al.A new NLOS TOA-based wireless sensor network localization algorithm with robust character[J].Chinese Journal of Sensors and Actuators,2007,20(7): 1625?1629.

[7]周書旺,王英龍,郭強(qiáng),等.基于微粒群算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位方法[J].山東大學(xué)學(xué)報: 理學(xué)版,2009,44(9):52?55.ZHOU Shu-wang,WANG Ying-long,GUO Qiang,et al.Particle swarm optimization-based wireless sensor network nodes localization method[J].Journal of Shandong University: Natural Science,2009,44(9): 52?55.

[8]Kennedy J,Eberhart R.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks IV.Piscataway: IEEE Press,1995: 1941?1948.

[9]Eberhart R,Kennedy J.A new optimizer using particle swarm optimization theory[C]//Proceedings of the 6th International Symposium on Micro Machine and Human Science.Nagoya:IEEE Press,1995: 39?43.

[10]Barskar S,Suganthan P N.A novel concurrent particle swarm optimization[C]//Proceedings of IEEE Congress on Evolutionary Computation.Portland: IEEE Press,2004: 792?796.

[11]呂振肅,侯志榮.自適應(yīng)變異的粒子群優(yōu)化算法[J].電子學(xué)報,2004,32(3): 416?420.Lü Zhen-su,HOU Zhi-rong.Particle swarm optimization with adaptive mutation[J].Acta Electronica Sinica,2004,32(3):416?420.

[12]Wolpert D H,Macready W G.No free lunch theorems for optimization[J].IEEE Trans on Evolutionary Computation,1997,1(1): 67?82.

[13]李兵,蔣慰孫.混沌優(yōu)化方法及其應(yīng)用[J].控制理論與應(yīng)用,1997,14(4): 613?615.LI Bing,JIANG Wei-sun.Chaos optimization method and its application[J].Control Theory and Applications,1997,14(4):613?615.

[14]單良,強(qiáng)浩,李軍,等 基于 Tent影射的混沌優(yōu)化算法[J].控制與決策,2005,20(2): 179?182.SHAN Liang,QIANG Hao,LI Jun,et al.Chaotic optimization algorithm based on Tent map[J].Control and Decision,2005,20(2): 179?182.

[15]程志剛,張立慶,李小林,等.基于Tent映射的混沌混合粒子群優(yōu)化算法[J].系統(tǒng)工程與電子技術(shù),2007,29(1):103?106.CHENG Zhi-gang,ZHANG Li-qing,LI Xiao-lin,et al.Chaotic hybrid particle swarm optimization algorithm based on Tent map[J].Systems Engineering and Electronics,2007,29(1):103?106.