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

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

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

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

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

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

    本文將粒子群優化算法應用到節點定位過程中，通過對慣性權重的分析，對基于粒子群優化的節點定位算法進行了改進。首先利用節點間的連通性估計未知節點可能存在的約束區域，然后對粒子群優化算法的慣性權重的設置進行了優化。通過仿真比較，改進后算法在定位精度方面有明顯改善，并且受節點分布的影響較小。由于粒子群優化算法通過迭代方式搜索未知節點的最優位置，在測距誤差較大、參數設置不理想等情況下，其計算量會有比較明顯的增加。
參考文獻
[1] KRISHNAMACHARI B. Networking wireless sensors[M].New York: Cambridge University Press, 2005.
[2] 孫利民, 李建中, 陳渝,等. 無線傳感器網絡[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] 林衛星,陳炎海.一種快速收斂的改進粒子群優化算法[J].系統仿真學報, 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] 焦巍, 劉光斌. 基于多樣性反饋的粒子群優化算法[J]. 計算機工程, 2009,35(22):202-204.