基于改進型粒子群優化的節點自定位算法

劉志坤，劉忠，唐小明

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

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

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

1 改進型粒子群優化算法

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

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

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

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

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

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

以往的研究通常使用logistic映射產生混沌擾動，但是根據文獻[14]的結論，Tent映射的遍歷均勻性優于logistic映射，可以獲得更高的搜索尋優效率，因此本文采用Tent映射作為混沌擾動產生器，它的表達式如下[15]：

產生混沌點列的過程如下：

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

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

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

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

2 節點自定位算法

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

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

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

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

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

(5)當迭代次數達到設定值后，退出循環，輸出全局極值對應的坐標。

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

3 試驗及結果分析

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

3.1 改進型PSO與PSO的性能比較

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

(1)Rastrigrin函數

(2)Rosebrock函數

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

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

3.2 改進型PSO定位算法與最小二乘估計法比較

在驗證了改進型PSO算法相對普通PSO算法性能提高后，將其應用在節點自定位領域，將新定位算法與被廣泛采用的最小二乘估計法進行比較。試驗場景設置為一個100 m×100 m×100 m的三維空間，網絡規模為200個節點，信標節點隨機布放在此區間，節點的通信半徑設為60 m，慣性權重c0取為0.729 8，加速常數c1和c2取為1.496 2，最大速度為5。試驗結果的優劣用平均定位誤差來評估，平均定位誤差定義為：

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

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

在實際應用中，測量節點間的距離信息不可能做到嚴格準確，現有的測距方法一般都會伴隨一定的誤差。因此有必要測試測距誤差對定位算法的影響。試驗中誤差依次取真實距離的5%，10%，15%，20%，25%，30%，信標節點數取30。試驗結果如圖1所示。

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

(2)不同信標節點數量情況下基于改進型PSO的定位算法與最小二乘估計法比較。

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

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

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

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

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

表2 不同信標節點數量時2種算法的平均定位誤差Table 2 Average localization error of two algorithms in different anchor nodes number

4 結論

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

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

[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的多維定標迭代定位算法[J].東北大學學報,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].傳感器與微系統,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]焦磊,邢建平,張軍,等.一種非視距環境下具有魯棒特性TOA無線傳感網絡定位算法[J].傳感技術學報,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]周書旺,王英龍,郭強,等.基于微粒群算法的無線傳感器網絡節點定位方法[J].山東大學學報: 理學版,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]呂振肅,侯志榮.自適應變異的粒子群優化算法[J].電子學報,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]李兵,蔣慰孫.混沌優化方法及其應用[J].控制理論與應用,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]單良,強浩,李軍,等 基于 Tent影射的混沌優化算法[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映射的混沌混合粒子群優化算法[J].系統工程與電子技術,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.