對于大多數(shù)應用，知道傳感器節(jié)點的位置是至關重要的。無線傳感器網(wǎng)絡節(jié)點定位算法可以分為兩類[1-2]：基于測距技術的定位（Range-based）和無需測距技術的定位（Range-free）。Range-based算法的定位精度在一定程度上依賴于測量技術本身的精度。通常測距誤差越小，定位算法獲得的定位精度越高。常見的測距方式包括TDOA、AOA、RSSI、TOA等[2]。Range-free算法則無需專門測量節(jié)點間距離和角度信息，僅根據(jù)網(wǎng)絡連通性等信息即可實現(xiàn)。由于功耗和成本因素，并且大多數(shù)應用對定位精度的要求并不高，無需測距的定位算法也具有很大的使用空間，典型的無需測距的算法有APIT算法[3]、DV-hop算法[4]、質(zhì)心定位法[5]、凸規(guī)劃法[6]等。

    粒子群優(yōu)化算法[7]PSO(Particle Swarm Optimization)早期是模擬一些簡單的社會群落生物，如鳥群、魚群等模型，是一種基于群體的演化算法。PSO算法簡單，易于實現(xiàn)，需調(diào)參數(shù)少，是解決非線性連續(xù)優(yōu)化、組合優(yōu)化等問題的有效工具。
    參考文獻[8]將粒子群優(yōu)化算法應用到無線傳感器網(wǎng)絡的節(jié)點定位過程中，根據(jù)節(jié)點間的測距信息構成目標函數(shù)，將節(jié)點自定位轉(zhuǎn)化成非線性優(yōu)化問題，用粒子群優(yōu)化算法對其進行求解，并且指出在定位精度方面要優(yōu)于多邊定位法、模擬退火算法等。參考文獻[9]根據(jù)離散線性系統(tǒng)的穩(wěn)定性理論，推出了保證粒子群優(yōu)化算法收斂性的參數(shù)設置區(qū)域，參考文獻[10-12]對粒子群優(yōu)化算法的慣性權重進行了改進,分別提出了線性遞減、非線性遞減以及反饋動態(tài)調(diào)節(jié)的慣性權重取值策略，提高了算法尋優(yōu)精度以及收斂速度。本文根據(jù)慣性權重對粒子搜索能力的影響，并結合節(jié)點間連通性對慣性權重的設置進行改進，使其更加適應無線傳感器網(wǎng)絡節(jié)點定位。
1 粒子群優(yōu)化算法
    PSO算法在一定區(qū)域中隨機選取一組位置坐標，作為粒子群的初始粒子。粒子通過代入目標函數(shù)來計算適應度，從而得到粒子本身所找到的最優(yōu)位置Ppbest和整個種群目前找到的最優(yōu)位置Pgbest，通過更新迭代，最終獲得滿足要求的最優(yōu)目標位置。
   
 

    在傳統(tǒng)的粒子群優(yōu)化算法中，未知節(jié)點可能存在的區(qū)域是根據(jù)所有節(jié)點布設的范圍來估計的，粒子在該區(qū)域內(nèi)初始化并且不斷更新，搜索最優(yōu)位置，對粒子更新提供的約束信息非常有限,經(jīng)過上述對節(jié)點間連通度的利用，很大程度上縮小了未知節(jié)點可能存在的區(qū)域,為粒子群的初始化、個體最優(yōu)位置Pipbest和群體最優(yōu)位置Pgbest的更新提供了更加精確的范圍限制。改進后算法的粒子種群可以在相交區(qū)域內(nèi)隨機選取,利用區(qū)域?椎的中心坐標作為Pgbest，在粒子的更新階段,相交區(qū)域可以為粒子更新速度提供約束條件，要求更新后粒子不應跳出相交區(qū)域。
2.2 改進慣性權重設置
　　慣性權重w的大小體現(xiàn)了對粒子當前速度繼承的程度。參考文獻[10]指出較小的w可加強局部搜索能力，而較大的w則有助于在全局范圍內(nèi)搜索，并且將慣性權重w設計為隨迭代次數(shù)線性遞減的函數(shù)，在算法的初期使用較大慣性權重以跳出局部最優(yōu)解，而在后期則使用較小慣性權重，提高局部搜索能力以加快收斂速度。即：

    根據(jù)節(jié)點連通性的約束，在一定程度上縮小了未知節(jié)點可能存在的區(qū)域。在比較小的區(qū)域內(nèi)利用粒子群優(yōu)化算法估計未知節(jié)點坐標，選用較大的w可能使粒子跳出有效區(qū)域，此時更加倚重較小的w來加強局部搜索能力，而式(6)的慣性權重下降速率是恒定的，不利于更快速準確地獲得最優(yōu)位置估計。因此本文將w設計成前期較大的慣性權重下降速率較快、較小的慣性權重下降速率較慢的非線性遞減函數(shù)。

    為了表述方便，將本文提出的改進后粒子群優(yōu)化算法記作PSO-U，并與前文提到的PSO、多邊定位法[2]等位置估計算法進行性能比較。圖3是在錨節(jié)點密度設定為30%，通過調(diào)節(jié)節(jié)點通信距離來控制平均連通度變化的情況下，對三種算法平均定位誤差的比較。圖中隨著節(jié)點平均連通度的增大，各算法的平均定位誤差逐漸下降，其中PSO-U算法的下降幅度最小，相對于另外兩種算法受平均連通度變化的影響較小，在較小連通度的情況下就可以達到比較高的定位精度。圖4是在平均連通度設定為13，錨節(jié)點密度從20%線性增加的情況下，對三種算法平均定位誤差的比較。圖中各算法的平均定位誤差隨著錨節(jié)點密度的增大而逐漸變小，相對于平均連通度的變化,錨節(jié)點密度對平均定位誤差的影響較小。

    粒子群優(yōu)化是一種迭代搜索方法，迭代次數(shù)是該算法計算量的重要體現(xiàn)，以下對改進后粒子群優(yōu)化算法的迭代次數(shù)進行仿真分析。圖5是錨節(jié)點密度分別取20%、30%、40%的條件下，PSO-U和PSO的平均迭代次數(shù)比較。從兩圖中可以看出，本文提出的PSO-U算法的平均迭代次數(shù)明顯小于PSO算法。但是綜合分析改進前后的粒子群優(yōu)化算法，PSO-U算法需要對相交區(qū)域進行估算，這相對于PSO算法是額外的計算量，并且慣性權重在形式上要更為復雜。因此，整體來看，本文提出的PSO-U算法在定位精度上有明顯的優(yōu)勢，但在算法復雜度上有所增加，適用于對精度要求較高的WSN應用中。

    本文將粒子群優(yōu)化算法應用到節(jié)點定位過程中，通過對慣性權重的分析，對基于粒子群優(yōu)化的節(jié)點定位算法進行了改進。首先利用節(jié)點間的連通性估計未知節(jié)點可能存在的約束區(qū)域，然后對粒子群優(yōu)化算法的慣性權重的設置進行了優(yōu)化。通過仿真比較，改進后算法在定位精度方面有明顯改善，并且受節(jié)點分布的影響較小。由于粒子群優(yōu)化算法通過迭代方式搜索未知節(jié)點的最優(yōu)位置，在測距誤差較大、參數(shù)設置不理想等情況下，其計算量會有比較明顯的增加。
參考文獻
[1] KRISHNAMACHARI B. Networking wireless sensors[M].New York: Cambridge University Press, 2005.
[2] 孫利民, 李建中, 陳渝,等. 無線傳感器網(wǎng)絡[M]. 北京:清華大學出版社, 2005.
[3] TIAN H, CHENGDU H, BRIAN M B, et al. Range-free localization schemes in large scale sensor networks[A]. In: Proceedings of the 9th annual international conference  on mobile computing and networking (MobiCom’03)[C], San Diego, California, USA, 2003:81-95.
[4] NIEULESEU D, NATH B. DV based positioning in ad hoc networks[J]. Journal of Telecommunica- tion Systems,2003,22(1):267-280.
[5] BULUSU N, JOHN H, ESTRIN D. GPS-less Low cost outdoor localization for very small devices[J]. IEEE Journal of Personal Communications, 2000,7(5):28-34.
[6] DOHERTY L,PISTER K S J,GHAOUI L E. Convex position estimation in wireless sensor networks-[A]. In: Proceedings of the IEEE INFOCOM 2001[C], 2001(3):1655-1663.
[7] KENNEDY J, EBERHART R C. Particle swarm optimization[C]. Proceedings of IEEE International Conference on  Neural Networks, Perth, Australia, 1995:1942-1948.
[8] GOPAKUMLAR A, JACOB L. Localization in wireless sensor networks using particle swarm optimization[C]. IET International Conference on Wireless, Mobile and Multimedia Networks, 2008(1):227-230.
[9] 林衛(wèi)星,陳炎海.一種快速收斂的改進粒子群優(yōu)化算法[J].系統(tǒng)仿真學報, 2011,23(11):2406-2411.
[10] SHI Y H, EBERAHRT R C. Parameter selection in particle swarm optimization[J]. Lecture Notes in Computer Science, 1998, 47(14): 591-600.
[11] CHATTERJEE A, SIARRY P. Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization[J]. Computers & Operations Research, 2006,33(3):859-871.
[12] 焦巍, 劉光斌. 基于多樣性反饋的粒子群優(yōu)化算法[J]. 計算機工程, 2009,35(22):202-204.