關(guān)于無線傳感器網(wǎng)絡(luò)定位算法仿真*

何 濤， 包亮強， 趙長財

(1.蘭州交通大學(xué) 自動化與電氣工程學(xué)院，甘肅 蘭州 730070； 2.卡斯柯信號有限公司，上海 200071； 3.蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

關(guān)于無線傳感器網(wǎng)絡(luò)定位算法仿真*

何 濤1， 包亮強2， 趙長財3

(1.蘭州交通大學(xué)自動化與電氣工程學(xué)院，甘肅蘭州730070；2.卡斯柯信號有限公司，上海200071；3.蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅蘭州730070)

針對無線傳感器網(wǎng)絡(luò)(WSNs)節(jié)點定位的問題，提出了一種通過構(gòu)建粒子群機制的量子神經(jīng)網(wǎng)絡(luò)模型優(yōu)化距離矢量跳躍(DV-HOP)的定位算法(PSO-QNN),根據(jù)傳統(tǒng)DV-HOP所得到的平均距離和實測節(jié)點距離構(gòu)建量子神經(jīng)網(wǎng)絡(luò)模型，并通過粒子群算法對平均距離進行訓(xùn)練，從而得到較優(yōu)平均值，實現(xiàn)了對DV-HOP算法的優(yōu)化。算法縮短了傳統(tǒng)人工神經(jīng)網(wǎng)絡(luò)的訓(xùn)練時間，并且加快了收斂速度。仿真結(jié)果表明：與傳統(tǒng)DV-HOP算法相比，所提出的PSO-QNN算法能夠減少約20 %的定位誤差，定位精度顯著提高。

無線傳感器網(wǎng)絡(luò)； 量子神經(jīng)網(wǎng)絡(luò)； 粒子群優(yōu)化算法； 距離矢量跳躍算法

0 引 言

近年來，無線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSNs)的研究成果在環(huán)境檢測、目標(biāo)跟蹤、軍事等領(lǐng)域廣泛使用[1]。隨著WSNs理論研究和實際應(yīng)用的深入結(jié)合[2,3]，目前對于WSNs的研究主要在網(wǎng)絡(luò)節(jié)點的能耗、節(jié)點部署和節(jié)點定位三個方面，其中節(jié)點定位的研究是傳感器網(wǎng)絡(luò)在很多應(yīng)用中的前提[4]。

在WSNs的定位過程中根據(jù)節(jié)點位置是否需要測量，將定位算法分為基于測距的(range-based)定位算法和無需測距的(range-free)定位算法[5]。典型的無需測距的定位算法有質(zhì)心(Centroid)法、近似三角形內(nèi)點測試(approximate point-in-triangulation test,APIT)、距離矢量跳躍(distance vector-hop,DV-HOP)[6]、Amorphous等,具有實現(xiàn)簡單、不需要額外的硬件、網(wǎng)絡(luò)生存能力強、成本低等特點，經(jīng)常被用于WSNs定位中。本文主要針對無須測距的DV-HOP算法進行相關(guān)研究。傳統(tǒng)DV-HOP算法在實現(xiàn)WSNs節(jié)點定位的過程中主要依靠對平均跳距的估計來實現(xiàn)定位。網(wǎng)絡(luò)中的不良節(jié)點會導(dǎo)致獲取的跳數(shù)信息不合理，以致于根據(jù)跳數(shù)信息所得到的平均跳距存在較大誤差，從而使得WSNs節(jié)點定位的精度和效率急劇下降，定位過程具有模糊性和不確定性。

因此，本文用粒子群優(yōu)化(particle swarm optimization,PSO)算法作為量子神經(jīng)網(wǎng)絡(luò)(quantum neural network,QNN)的學(xué)習(xí)機制[6,7],提出了一種PSO-QNN的WSNs定位算法。通過將兩種算法相結(jié)合，構(gòu)造了一個學(xué)習(xí)時間短、收斂速度快、尋優(yōu)精度高的節(jié)點定位模型。通過訓(xùn)練，量子神經(jīng)網(wǎng)絡(luò)得到最佳的初始化權(quán)值和閾值。將該模型結(jié)合運用到DV-HOP算法中，得到較優(yōu)平均跳距值，從而提高了節(jié)點的定位精度。通過Matlab仿真證明該算法在定位精度和效率方面有了很大的改善。

1 DV-HOP算法[8]

圖1為跳距原理的具體示意。

圖1 跳距原理

圖1中A為錨節(jié)點，通信半徑為r，I,II,III分別為錨節(jié)點A的1,2,3跳的約束區(qū)域。

DV-HOP算法具體分為3個階段：1)錨節(jié)點向整個WSNs廣播自身在網(wǎng)絡(luò)中的位置信息和跳數(shù)，設(shè)跳數(shù)的初始值為0，待定位節(jié)點記錄每個錨節(jié)點的最小跳數(shù)值，并將跳數(shù)值加1并轉(zhuǎn)發(fā)給鄰居節(jié)點，此刻所有節(jié)點通過距離矢量交換協(xié)議得到自身到錨節(jié)點的最小跳數(shù)；2)每個錨節(jié)點根據(jù)階段一記錄的與其他錨節(jié)點的位置信息和相距跳數(shù)，計算每個錨節(jié)點與其他錨節(jié)點之間的平均每跳實際距離

(1)

式中 (xi,yi),(xj,yj)分別為節(jié)點i和j的位置坐標(biāo);hij為錨節(jié)點i和j,i≠j之間的跳段數(shù)，然后將每跳平均距離作為校正值在整個WSNs內(nèi)廣播，當(dāng)待定位節(jié)點接收到第一個校正值后,保存，之后不再接收其他校正值，根據(jù)校正值，將待定位節(jié)點到錨節(jié)點的最小跳數(shù)換算為到錨節(jié)點的距離；3)待定位節(jié)點得到三個或者三個以上的錨節(jié)點的位置時，通過三邊或者多邊測量法得到待定位節(jié)點的位置。

2 基于PSO-QNN的DV-HOP算法

2.1 量子神經(jīng)網(wǎng)絡(luò)[9～11]

2.1.1 經(jīng)典反射傳播神經(jīng)網(wǎng)絡(luò)模型

反向傳播(back propagation,BP)神經(jīng)網(wǎng)絡(luò)由三層結(jié)構(gòu)組成：輸入層、隱含層和輸出層。在該模型中輸入層LA由m個節(jié)點組成，輸出層LC有n個節(jié)點，隱含層 LB的節(jié)點數(shù)目為p。 同層節(jié)點之間不相連，相鄰層節(jié)點全互連。

傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)隱含層LB的節(jié)點輸出為

br=f(WTX-θ),r=1,2,3,…,p

(2)

輸出層LC的節(jié)點輸出為

cj=f(VTB-φ),j=1,2,3,…,n

(3)

式中對應(yīng)關(guān)系f為Sigmoid函數(shù)(也稱為S型生長曲線)即f(x)=(1+e-x)-1;X為神經(jīng)網(wǎng)絡(luò)的輸入，輸入層的神經(jīng)元為ai，隱含層的神經(jīng)元為br，輸出層的神經(jīng)元為cj。Wir為輸入層神經(jīng)元到隱含層神經(jīng)元之間的連接權(quán)值;Vrj為隱含層神經(jīng)元到輸出層神經(jīng)元之間的連接權(quán);θ為隱含層的閾值;φ為輸出層的閾值。

2.1.2 量子神經(jīng)網(wǎng)絡(luò)模型

將多個Sigmoid函數(shù)進行疊加，一個隱含層神經(jīng)元即可表示多個量級，從而構(gòu)建成多層結(jié)構(gòu)的激勵函數(shù)，使得該網(wǎng)絡(luò)的模糊性大幅增加，則此時隱含層輸出為

(4)

式中ns為量子間隔數(shù)目，ns的選擇與故障數(shù)目相同;αm為陡度因子;θγ為量子間隔。

多層激勵函數(shù)的量子神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練算法仍采用梯度下降法。在該訓(xùn)練過程中，更新的內(nèi)容包括不同層神經(jīng)元之間的連接權(quán)值和隱含層各個神經(jīng)元之間的量子間隔。其中連接權(quán)值的更新與BP神經(jīng)網(wǎng)絡(luò)無異，隱含層神經(jīng)元的量子間隔更新算法如下：

對于模式類矢量Cm(m為模式類數(shù)目，即輸入層的神經(jīng)元個數(shù))，那么隱含層第j個神經(jīng)元的輸出變量為

(5)

(6)

式中Oj,k為輸入矢量為xk時，隱含層第j個神經(jīng)元的輸出。

(7)

式中η為學(xué)習(xí)率;αm為陡度因子。

2.2 粒子群優(yōu)化算法[12]概述

假設(shè)有一個N維的目標(biāo)搜索空間，由m個粒子組成，第p個粒子在d維空間中的位置為

Lp=[lp1,lp2,lp3,…,lpd],p=1,2,…,m

(8)

飛行速度為

Vp=[vp1,vp2,vp3,…,vpd],p=1,2,…,m

(9)

適應(yīng)值為

fitnessp=f(Lp)

(10)

該算法中具有2個極值：各個粒子本身所找到的最優(yōu)解pbest；整個粒子群所發(fā)現(xiàn)的最好位置gbest。在該算法中的粒子p在d維空間中位置和速度按照如下迭代方程進行更新

(11)

(12)

圖2 粒子群優(yōu)化算法流程

2.3 算法實現(xiàn)步驟

設(shè)錨節(jié)點為P個，待定位節(jié)點為M個，則整個WSNs節(jié)點定位的步驟如下：

2)利用PSO算法極強的尋優(yōu)能力，搜尋每個粒子的全局最優(yōu)解gbest；

3)建立模型之后，將錨節(jié)點和待定位節(jié)點在WSNs中進行分布，每個錨節(jié)點定時在WSNs中廣播自身的相關(guān)參數(shù)，包括節(jié)點坐標(biāo)、量子神經(jīng)網(wǎng)絡(luò)參數(shù)。所有節(jié)點通過距離矢量交換協(xié)議得到自身到錨節(jié)點的最小跳數(shù)；

4)根據(jù)所記錄的每個錨節(jié)點到其他錨節(jié)點的位置信息和跳數(shù)，利用式(1)計算平均每跳實際距離；

7)當(dāng)待定位節(jié)點接收并保存第一個校正值后，將其轉(zhuǎn)發(fā)給相鄰節(jié)點，待定位節(jié)點根據(jù)校正值根據(jù)已記錄的跳數(shù)信息計算與每個錨節(jié)點的跳段距離值；

8)待定位節(jié)點得到3個或者3個以上的錨節(jié)點的位置時，通過三邊或者多邊測量法得到待定位節(jié)點的位置。

2.4 算法具體描述

2.4.1 PSO訓(xùn)練QNN算法

2.4.2 優(yōu)化QNN的初始權(quán)值及量子間隔

首先要選取對應(yīng)的數(shù)據(jù)對QNN進行學(xué)習(xí)和訓(xùn)練[13]，以此形成實踐模型應(yīng)用于WSNs定位中。本文通過PSO對QNN的參數(shù)進行訓(xùn)練。其中需要訓(xùn)練的參數(shù)為隱含層節(jié)點所包含的對QNN的參數(shù)即為m×p個θ和p個λ，輸出層節(jié)點包含的n×p個θ和n個λ。其中，m為輸入層節(jié)點的個數(shù)，p為隱含層節(jié)點的個數(shù)，n為輸出層節(jié)點的個數(shù)，θ為連接神經(jīng)元之間的權(quán)值，λ為閾值。將神經(jīng)元之間的連接權(quán)值映射為PSO算法中的粒子的位置，則此時粒子群的維度就是m×p+n×p+p+n。初始化種群之后，按照算法步驟進行迭代。直到產(chǎn)生均方差(mean square error,MSE)最小的粒子位置，此時該粒子位置的各維度值就是得到的最優(yōu)的初始權(quán)值和閾值。

設(shè)訓(xùn)練的樣本數(shù)量為N，則網(wǎng)絡(luò)的MSE

(13)

式中tij為樣本i在第j個輸出端的的期望輸出值。

2.4.3 三邊或多邊測距

在三邊或者多邊測量法中設(shè)待定位節(jié)點的坐標(biāo)為(x，y)，錨節(jié)點的坐標(biāo)為(x1，y1)，(x2，y2)，(x3，y3),…,(xk，yk)，則待定位節(jié)點到各錨節(jié)點的距離為d1，d2，d3,…,dk

(14)

X=(ATA)-1ATB

(15)

由式(15)可得待定位節(jié)點的位置坐標(biāo)。

3 仿真結(jié)果

實驗在 Intel(R) Core(TM)i3—2370M CPU，主頻2.40,2.40 GHz，4 GB 內(nèi)存平臺，Matlab7.0仿真環(huán)境中進行。仿真實驗中，構(gòu)建100 m×100 m的節(jié)點定位檢測區(qū)域。該區(qū)域中部署150個傳感器節(jié)點，節(jié)點的通信半徑r=25 m，節(jié)點隨機部署在該區(qū)域中。在PSO算法中，種群的初始化數(shù)目為m=40，最大迭代次數(shù)為Q=100,學(xué)習(xí)因子c1=c2=1.8，錨節(jié)點和待定位節(jié)點分布如圖3。

圖3 節(jié)點分布

3.1 錨節(jié)點數(shù)對定位誤差的影響

根據(jù)本文算法的實施步驟對節(jié)點進行定位，根據(jù)仿真結(jié)果得到平均定位誤差[14,15]，其中平均定位誤差定義為

(16)

由圖4可以看出：在相同環(huán)境下,本文算法的定位誤差較傳統(tǒng)DV-HOP算法的誤差要低很多。選擇加權(quán)質(zhì)心算法作為對比算法，可以看出3種算法隨著錨節(jié)點個數(shù)的增加平均定位誤差均呈現(xiàn)下降的趨勢。本文算法的平均定位誤差約為26 %，加權(quán)質(zhì)心算法的平均定位誤差約為38 %，傳統(tǒng)DV-HOP算法的平均定位誤差約為48 %。本文算法較傳統(tǒng)DV-HOP算法的平均定位誤差降低了約20 %。

圖4 定位誤差對比

3.2 待定位節(jié)點數(shù)對定位誤差的影響

由于跳數(shù)轉(zhuǎn)換為距離的過程會產(chǎn)生較大誤差，因此,該算法在實施過程中要求待定位節(jié)點需要很高的密度。仿真結(jié)果如圖5所示，隨著待定位節(jié)點的密度增加，3種算法所需的持續(xù)時間也隨之下降，而本文算法所需的時間較傳統(tǒng)DV-HOP算法減少了約100 ms。

圖5 待定位節(jié)點密度對算法持續(xù)時間的影響

3.3 連通度對定位誤差的影響

在DV-HOP算法中，節(jié)點之間可以直接通信傳輸信息。連通度主要反映了錨節(jié)點數(shù)量及通信半徑兩者的關(guān)系，實驗通過分析連通度的變化比較定位誤差。由圖6可以看出，隨著連通度的增加，三者的平均定位誤差大體上呈下降趨勢。在相同的連通度下，本文算法的定位誤差在三者中最小。

圖6 不同連通度對平均定位誤差的影響

4 結(jié)束語

針對基于DV-HOP算法在WSNs節(jié)點定位過程中易受外界環(huán)境因素影響而導(dǎo)致測量距離數(shù)據(jù)存在較大誤差的問題，提出了PSO-QNN算法，與傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)相比，QNN加快了算法的收斂速度，在模糊性方面的表現(xiàn)更為突出。本文通過將PSO算法作為QNN的學(xué)習(xí)算法，構(gòu)建了PSO-QNN網(wǎng)絡(luò)模型，進一步對DV-HOP算法進行改進。通過仿真實驗對所得到的數(shù)據(jù)從三方面進行分析，結(jié)果表明：本文算法的定位精度有了很大的提升，可達20 %左右，證明了本文算法在節(jié)點定位方面的有效性。

[1] Shi H,Wang W.Game theory for wireless sensor networks:A survey[J].Sensors,2012,12(7):9055-9097.

[2] 馬祖長，孫怡寧，梅 濤.無線傳感器網(wǎng)絡(luò)綜述[J].通信學(xué)報，2004,25(4)：114-124.

[3] 李鵬程，廖 波，羅 娟，等.無線傳感器網(wǎng)絡(luò)中一種移動節(jié)點定位算法[J].小型微型計算機系統(tǒng)，2008,29(11)：2051-2054.

[4] 王 學(xué)，李 蒙，宋書中.錨節(jié)點選擇和距離修正的DV-HOP定位算法[J].計算機測量與控制，2012,20(12)：3317-3320.

[5] 張 品，毛文敏，徐 靜.一種基于迭代投票的無線傳感器網(wǎng)絡(luò)安全定位算法[J].傳感器與微系統(tǒng)，2015,34(12)：118-120.

[6] ZeKavat Buehrer．Handbook of position location:Theory,practice and advance[M].NJ:Wiley & Sons,2012:359-395．[7] 李盼池.量子計算及其在智能優(yōu)化與控制中的應(yīng)用[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2009.

[8] 石為人，賈傳江，梁煥煥.一種改進的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報，2011,24(1)：83-87.

[9] 張翼鵬，陳 亮，郝 歡.一種改進的量子神經(jīng)網(wǎng)絡(luò)訓(xùn)練算法[J].電子與信息學(xué)報，2013,35(7)：1630-1635.

[10] 蓋懷存，張小鋒，江澤濤.基于量子神經(jīng)網(wǎng)絡(luò)的人臉識別技術(shù)研究[J].計算機工程與應(yīng)用，2010,46(8)：187-189.

[11] 付麗輝.一種基于改進的量子神經(jīng)網(wǎng)絡(luò)的語音降噪方法[J].信息與控制，2010,39(4)：466-471.

[12] 李 曉,黃 純.電力系統(tǒng)故障診斷的量子粒子群優(yōu)化算法[J].電力系統(tǒng)及其自動化學(xué)報，2011,23(4)：61-66.

[13] 石曉偉，張會清，鄧貴華.基于 BP 神經(jīng)網(wǎng)絡(luò)的距離損耗模型室內(nèi)定位算法研究[J].計算機測量與控制，2012,20(7)：1944-1947.

[14] 陶志勇，魏 強，劉 影.多功率錨節(jié)點輔助的DV-Hop定位算法[J].計算機工程與應(yīng)用，2014,50(21)：121-124.

[15] 王 穎，石昊旸.改進的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].計算機工程，2012，38(7)：66-69.

SimulationstudyonlocalizationalgorithmforWSNs*

HE Tao1, BAO Liang-qiang2, ZHAO Chang-cai3

(1.SchoolofAutomationandElectricalEngineering,LanzhouJiaotongUniversity，Lanzhou730070，China;2.CASCOSignalCoLtd，Shanghai200071，China;3.SchoolofElectronicandInformationEngineering,LanzhouJiaotongUniversity，Lanzhou730070，China)

Aiming at wireless sensor networks(WSNs)node localization problem,a new localization algorithm is proposed by building quantum neural network model for particle swarm mechanism to optimize localization algorithm of DV-HOP,particle swarm optimization-quantum neutral network(PSO-QNN).The algorithm constructs quantum neural network model according to average distance obtained by traditional DV-HOP and distance of measured actual node,and through the particle swarm algorithm to train the average distance,so as to get better average,value to achieve the optimization of DV-HOP algorithm.The combination algorithm shortens the training time of the traditional artificial neural network,and speeds up the convergence rate.Simulation results show that compared with the traditional DV-HOP algorithm,the proposed PSO-QNN algorithm can reduce the positioning error of about 20 %,and the positioning precision is significantly improved.

wireless sensor networks(WSNs); quantum neural network(QNN); particle swarm optimization(PSO)algorithm; DV-HOP algorithm

10.13873/J.1000—9787(2017)11—0143—04

TP 393

A

1000—9787(2017)11—0143—04

2017—01—05

中國鐵路總公司資助項目(2016X003—H)

何 濤(1977 -)，男，博士，教授，主要從事交通信息工程及控制研究工作,E—mail:hetao@mail.lzjtu.com。

趙長財(1991-)，男，通訊作者，碩士研究生，主要研究方向為電子與通信工程，E—mail:1193702476@qq.com 。