基于改進粒子群優(yōu)化的無線傳感器網(wǎng)絡定位算法

1、基于改進粒子群優(yōu)化的無線傳感器網(wǎng)絡定位算法摘要:無線電干涉定位系統(tǒng)獲取的干涉距離是4個傳感器節(jié)點間距離的線性組合值。針對以兩個節(jié)點間距離作為輸入的傳統(tǒng)定位算法無法直接利用上述干涉距離進行定位的問題，提出一種基于改進粒子群優(yōu)化的定位方法。利用干涉距離的實驗數(shù)據(jù)，分析比較了遺傳算法和改進粒子群優(yōu)化在無線傳感器網(wǎng)絡節(jié)點定位問題中的性能。結(jié)果表明，基于改進粒子群優(yōu)化的定位方法的平均耗費時間遠遠小于基于遺傳算法的定位方法，具有更高的優(yōu)化效率。關鍵詞:無線傳感器網(wǎng)絡；干涉定位；粒子群優(yōu)化；遺傳算法1引言在無線傳感器網(wǎng)絡(WSN)的各種應用中，監(jiān)測到事件之后人們關注的一個重要問題即是該事件發(fā)生的位置。因此，

2、位置信息是傳感器節(jié)點采集數(shù)據(jù)中不可缺少的部分，沒有位置信息的監(jiān)測通常毫無意義。確定事件發(fā)生的位置或采集數(shù)據(jù)的傳感器節(jié)點位置是WSN最基本的功能之一，對WSN應用的有效性起著關鍵的作用。近年來，越來越多的應用對定位精度不斷提出更高的要求，從低精度區(qū)域定位，到米級，甚至厘米級、毫米級的高精度無線空間三維定位。如何提高節(jié)點定位精度已成為當前WSN定位技術的研究熱點。 Maroti等人以新的實現(xiàn)形式將傳統(tǒng)的無線電干涉原理應用到無線傳感器平臺上，組建了無線電干涉定位系統(tǒng)(RIPS)。實驗表明，在多徑效應很小的理想環(huán)境下，該系統(tǒng)的定位精度可達到厘米級，從而證明該原理很有可能實現(xiàn)高精度的定位目標。目前，該方

3、法距離實用化還有一段距離，存在許多關鍵問題需要解決。RIPS中獲得的干涉距離是4個傳感器節(jié)點間距離的線性組合值dABCD，即兩個發(fā)送節(jié)點A和B以及兩個接收節(jié)點c和D間距離的線性組合值，計算方法如圖1所不，其中dij為兩個節(jié)點間的距離，而且是未知的?，F(xiàn)有的定位算法都是以兩個節(jié)點間的距離dij作為輸入，無法直接利用上述干涉距離dABCD計算節(jié)點圖1干涉距離位置。 Maroti等人采用基于遺傳算法的最優(yōu)化方法搜索節(jié)點坐標的近似值，但是遺傳算法的復雜度高且收斂速度較慢。對此，木文采用計算簡單、收斂速度快的粒子群優(yōu)化方法搜索節(jié)點坐標的近似值，并利用干涉距離的實驗數(shù)據(jù)分析比較兩種最優(yōu)化方法在RIPS節(jié)點定

4、位問題中的性能。2基于遺傳算法的RIPS節(jié)點定位21遺傳算法1975年Michigan大學的Holland教授提出了遺傳算法 (GA)，這是一種基于自然選擇和基因遺傳學原理的高度并行性全局搜索算法。GA由代表問題所在解集的一個種群開始，該種群由經(jīng)過基因編碼的一定數(shù)目的個體組成。初始種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解。在每一代，根據(jù)問題域中個體的適應度大小挑選個體，并借助自然遺傳學的遺傳算子進行組合交叉和變異，產(chǎn)生出代表新的解集的種群。如同自然進化一樣，后代種群比前代種群更加適應環(huán)境。該過程循環(huán)執(zhí)行直到滿足結(jié)束條件。末代種群中的最優(yōu)個體經(jīng)過解碼便可作為問題

5、的近似最優(yōu)解。22基于遺傳算法的定位方法給定n個待定位節(jié)點和一組干涉距離測量值M,待定位節(jié)點i的三維坐標為(Xi Yi Zi)。其中:0 XiX_MAX, 0 YiY_MAX, 0ZiZ_MAX,x_max,y_max,z_max為節(jié)點坐標允許的最大取值，由定位算法的搜索空間決定?；跓o線電干涉測距的定位問題可描述為如下的最優(yōu)化問題: 其中:s為GA中的一個個體，即解空間的一個解，亦即所有待定位節(jié)點的坐標集合(Xi Yi Zi)i=1,n; m為M干涉距離的數(shù)量;dABCD為測量得到的干涉距離，dABCD 為根據(jù)s計算得到的干涉距離。 基于GA的定位方法采用式(1)的誤差函數(shù)作為適應度函數(shù).為

6、了獲得充分的定位約束條件，需要對不同的節(jié)點組合進行多次測量.基于GA的定位方法通過搜索尋找使測量得到的干涉距離和計算得到的干涉距離誤差最小的節(jié)點坐標近似值.基于遺傳算法的定位方法具體步驟如下:Step1:生成初始種群，群體規(guī)模大小為populationSize。 Step2:在初始種群中隨機選擇得到被選種群，群體規(guī)模大小為subpopulationSize。 Step3:用式(1)評估被選種群中的所有個體。 Step4:根據(jù)誤差大小對被選種群按升序排列。 Step5:淘汰掉被選種群中最差的20%個體，從最好的20%個體中隨機選擇兩個個體作為父代，利用交叉算子和變異算子生成新的個體，直到獲得新的

7、被選種群。Step6:檢驗是否符合結(jié)束條件，如果當前的迭代次數(shù)達到了預先設定的最大次數(shù)或者達到最小錯誤要求，則輸出最優(yōu)解;否則，轉(zhuǎn)Step2。上述方法中采用了如下的遺傳算子生成新的個體: 1)交叉算子。對于每一個待定位節(jié)點，隨機選擇一個父代個體中的坐標近似值作為新個體s中的坐標。 2)變異算子。用高斯隨機數(shù)，以一定的概率更新每一個待定位節(jié)點的坐標;隨機更新一個待定位節(jié)點的坐標;用高斯隨機數(shù)更新所有待定位節(jié)點的坐標。3基于改進粒子群優(yōu)化的RIPS節(jié)點定位3、1粒子群優(yōu)化算法Kennedy于1995年提出了粒子群優(yōu)化算法，這是一種新的基于群體智能理論的演化計算方法，是對鳥群覓食過程中的遷徙和聚集的

8、模擬，也可以說是對社會心理學的一種模擬。PSO算法首先初始化一群隨機粒子，每個粒子具有位置和速度兩個特征，還有一個由被優(yōu)化函數(shù)決定的適應值，適應值的大小決定了粒子的優(yōu)劣。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己:一個是粒子本身所找到的最好解，即個體極值;另一個是整個粒子群找到的最好解，即全局極值。假設第k代群體中第i個粒子的位置為XKi=XKi,XKi,XKiT，速度為XKi=XKi1,XKi2,.XKiDT，則更新方程為 其中:W為慣性權(quán)重; VKid為粒子i在第k次迭代中第d(屬于1,D)維的速度，被限制在Vmin, Vmax之內(nèi);C1和C2為學習因子或加速系數(shù);rand1和ra

9、nd2為0, 1之間的隨機數(shù);Xkid為粒子i在第k次迭代中第d維的位置，被限制在Xmin，Xmax之內(nèi);pbest為粒子i的個體極值第d維的位置;gbest為全局極值第d維的位置。兩個“極值”在迭代過程中不斷更新，最后輸出的全局極值即是算法得到的最優(yōu)解。上述是全局版PSO算法，雖然收斂快，但有時會陷入局部最優(yōu)。局部版PSO通過保持多個吸引子來避免早熟，用其中一部分作為粒子的鄰居。所有鄰居中的最好解即為局部極值，用lbest表示其位置。粒子通過跟蹤pbest和lbest來更新自己。此外，壓縮因子有助于確保PSO收斂，其速度更新方程為32基于改進粒子群優(yōu)化的定位方法盡管PSO和GA都是基于群體和

10、適應值，但PSO的優(yōu)勢在于結(jié)構(gòu)相對簡單并且沒有許多參數(shù)需要調(diào)整。粒子還有一個重要的特點，就是具有記憶，所有粒子都共享迄今為止問題最好的解。而在GA中，一旦種群改變，問題原來的信息將被破壞。與GA相比，在大多數(shù)情況下，所有的粒子可能更快地收斂于最優(yōu)解。因此本文提出采用基于PSO的最優(yōu)化方法搜索節(jié)點坐標的近似值。通過實驗可以發(fā)現(xiàn)，直接采用上述PSO算法解決RIPS節(jié)點定位問題時，搜索得到的節(jié)點坐標近似值誤差非常大。這是因為，PSO無論是早熟收斂還是全局收斂，粒子群中的粒子都會出現(xiàn)“聚集現(xiàn)象”，所有粒子或者聚集在某一特定位置，或者聚集在某幾個特定位置。要想克服早熟收斂，就必須提高PSO跳出局部最優(yōu)解

11、的能力。從上節(jié)對PSO的分析可見，PSO的信息共享機制不同于GA。在GA中，染色體互相共享信息，整個種群比較均勻地向最優(yōu)區(qū)域移動，遺傳操作中的變異算子可以使GA具有局部的隨機搜索能力并且保持群體的多樣性。而PSO中，只有gbest或lbest給其他粒子傳遞信息，這是單向的信息流動，整個搜索更新過程即是跟隨當前最優(yōu)解的過程。由于所有的粒子都向最優(yōu)解的方向飛去，粒子會趨向同一化，使得后期收斂速度明顯變慢。當收斂到一定精度時，無法繼續(xù)優(yōu)化，所能達到的精度比GA低。針對RIPS節(jié)點定位問題的特點本文提出一種改進粒子群優(yōu)化算法。為了維持種群的活性，這里借鑒GA中變異的思想，在每次迭代時對利用式(3)和(

12、4)更新過的粒子的位置進行如下擾動: For d=1,DIf rand.nextBoolean()Xidk= Xidk+rand.nextGaussian()EndEnd其中=e (s)或者=rand.nextDouble()，兩種情況的概率相等。=e (s)可以保證當誤差函數(shù)值較大時粒子獲得較大的擾動;隨著搜索的進行，誤差函數(shù)值會越來越小，粒子獲得的擾動也變小，從而保證算法收斂。通過對粒子的位置進行微擾，可以防止粒子趨向同一化，更充分地搜索整個空間，即增強了粒子群的全局搜索能力。當然，改進PSO算法的運算量要比基本PSO算法略有增加。 與基于GA的定位方法類似，粒子的位置為解空間的一個解，對

13、應于2.2節(jié)中的s,粒子的適應值也由式(1)決定。Xdmax的取值與基于GA的定位方法相同，Xdmax=0，Vdmax= Xdmax/2,Vdmin=-Xdmin/2， D=3n。基于改進PSO的定位方法具體步驟如下: Step1:生成初始種群，群體規(guī)模大小為pSize。其中，所有粒子的初始速度均設為0，計算所有粒子的適應值;每個粒子的pbest設為其當前位置，pb為其對應的適應值;gbest設為種群中具有最小適應值的粒子的位置，gb為其對應的適應值。 Step2:在初始種群中隨機選擇并得到被選種群，群體規(guī)模大小為spSize;找到被選種群具有最小適應值的粒子，位置為lbest,其對應的適應值

14、為1b。 Step3:被選種群中除lbest以外的粒子均按式(3)和(4)用pbest和lbest更新速度和位置。 Step4:對更新后的粒子位置進行微擾。 Step5:計算被選種群中所有粒子的適應值。如果小于該粒子當前的pb，則將pbest設為其當前位置，并更新pb。 Step6:如果被選種群中具有最小適應值的粒子的pb小于當前整個種群的gb，則將gbest設為具有最小適應值的粒子的位置并更新gb。 Step 7:檢驗是否符合結(jié)束條件。如果當前的迭代次數(shù)達到了預先設定的最大次數(shù)或達到最小錯誤要求，則輸出最優(yōu)解;否則，轉(zhuǎn)Step2。4定位算法性能分析4.1實驗設置Maroti等人采用美國Cro

15、ssbow公司生產(chǎn)的Mica2系列微型傳感器節(jié)點構(gòu)建了RIPS原型系統(tǒng)，并且進行了實驗。RIPS的軟件包括兩部分:在微型傳感器節(jié)點上運行的TinyOS應用程序和在基站上運行的java應用程序。木文利用Maroti等人在足球場測量得到的干涉距離驗證并比較兩種定位方法。 圖2為定位實驗設置。其中:節(jié)點7 788, 2 562,7 551和1 124為錨節(jié)點;待定位節(jié)點的數(shù)量為N=12;干涉距離的數(shù)量為m=7 258。對于基于GA的定位方法，X_max=100 m, y_max=100 m, z_ max=Om;對于基于改進PSD的定位方法，c1=c2=3。表圖2定位實驗設置4.2兩種定位方法的性能

16、分析采用的計算機配置為:CPU-Intel Pentium 3 GHz,內(nèi)存1GB。為了有效地比較兩種優(yōu)化算法應用于RIPS系統(tǒng)時的搜索性能，定義以下評價指標:1)使平均誤差avg E小于給定閾值所需要的平均迭代次數(shù)avgK; 2)使平均誤差avgE小于給定閾值所需要的平均耗費時間avgT(單位為ms)。平均誤差avg E的定義如下:GA和PSO的優(yōu)化質(zhì)量和效率與算法控制參數(shù)的設定有關，需要通過大量的仿真實驗來比較各參數(shù)所對應的算法性能。在不同的仿真設置下，兩種定位方法各運行15次，以計算評價指標的平均值。令populationSize=pSize=pS, subpopulationSize=

17、spSize= spS。表1表3分別給出了pS = 20 & spS = 10, pS=100 & spS=10以及pS=100 & spS=50時時，兩種定位方法的性能比較。從表1表3可以看出: 兩種定位方法都能在有限的進化代數(shù)內(nèi)找到節(jié)點坐標的近似值，其中基于改進PSO的定位方法在較少的進化代數(shù)內(nèi)，其解群便向最優(yōu)解的方向收斂，平均耗費時間遠遠小于基于GA的定位方法。PSO的優(yōu)勢在于計算簡單、易于實現(xiàn)，且沒有很多參數(shù)需要調(diào)整。與PSO相比，GA需要確定較多的參數(shù)。 2)在種群大小不變的情況下(表2和表3),隨著被選種群的增加，兩種定位方法的平均耗費時間都有所減少。這是因為每一次迭代中參與搜索的個體相應增加了。 3)在被選種群大小不變的情況下(表1和表2),隨著種群的增加，兩種定位方法的平均耗費時間都明顯增加。通常種群大小對算法最優(yōu)解的搜索能力具有決定性的作用，但這是以時間的增加為代價。因此應針對具體的應用要求選擇最佳的種群大小。5結(jié)論 RIPS中的干涉距離是兩個發(fā)送節(jié)點和兩個接收節(jié)點間距離的線性組合值。傳統(tǒng)的以兩個節(jié)點間的距離作為輸入的定位算法無法直接利用上述干涉距離計算節(jié)點的位置?；贕A的定位方法雖然可以通過搜索求解節(jié)點坐標的近似值，但是計算復雜度