何 濤， 包亮強， 趙長財

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

關于無線傳感器網絡定位算法仿真*

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

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

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

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

0 引 言

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

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

因此，本文用粒子群優(yōu)化(particle swarm optimization,PSO)算法作為量子神經網絡(quantum neural network,QNN)的學習機制[6,7],提出了一種PSO-QNN的WSNs定位算法。通過將兩種算法相結合，構造了一個學習時間短、收斂速度快、尋優(yōu)精度高的節(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廣播自身在網絡中的位置信息和跳數，設跳數的初始值為0，待定位節(jié)點記錄每個錨節(jié)點的最小跳數值，并將跳數值加1并轉發(fā)給鄰居節(jié)點，此刻所有節(jié)點通過距離矢量交換協(xié)議得到自身到錨節(jié)點的最小跳數；2)每個錨節(jié)點根據階段一記錄的與其他錨節(jié)點的位置信息和相距跳數，計算每個錨節(jié)點與其他錨節(jié)點之間的平均每跳實際距離

(1)

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

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

2.1 量子神經網絡[9～11]

2.1.1 經典反射傳播神經網絡模型

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

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

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

(2)

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

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

(3)

式中對應關系f為Sigmoid函數(也稱為S型生長曲線)即f(x)=(1+e-x)-1;X為神經網絡的輸入，輸入層的神經元為ai，隱含層的神經元為br，輸出層的神經元為cj。Wir為輸入層神經元到隱含層神經元之間的連接權值;Vrj為隱含層神經元到輸出層神經元之間的連接權;θ為隱含層的閾值;φ為輸出層的閾值。

2.1.2 量子神經網絡模型

將多個Sigmoid函數進行疊加，一個隱含層神經元即可表示多個量級，從而構建成多層結構的激勵函數，使得該網絡的模糊性大幅增加，則此時隱含層輸出為

(4)

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

多層激勵函數的量子神經網絡模型訓練算法仍采用梯度下降法。在該訓練過程中，更新的內容包括不同層神經元之間的連接權值和隱含層各個神經元之間的量子間隔。其中連接權值的更新與BP神經網絡無異，隱含層神經元的量子間隔更新算法如下：

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

(5)

(6)

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

(7)

式中η為學習率;αm為陡度因子。

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

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

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

(8)

飛行速度為

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

(9)

適應值為

fitnessp=f(Lp)

(10)

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

(11)

(12)

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

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

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

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

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

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

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

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

2.4 算法具體描述

2.4.1 PSO訓練QNN算法

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

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

設訓練的樣本數量為N，則網絡的MSE

(13)

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

2.4.3 三邊或多邊測距

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

(14)

X=(ATA)-1ATB

(15)

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

3 仿真結果

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

圖3 節(jié)點分布

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

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

(16)

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

圖4 定位誤差對比

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

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

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

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

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

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

4 結束語

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

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

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

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

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

[5] 張 品，毛文敏，徐 靜.一種基于迭代投票的無線傳感器網絡安全定位算法[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)化與控制中的應用[D].哈爾濱：哈爾濱工業(yè)大學，2009.

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

[9] 張翼鵬，陳 亮，郝 歡.一種改進的量子神經網絡訓練算法[J].電子與信息學報，2013,35(7)：1630-1635.

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

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

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

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

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

[15] 王 穎，石昊旸.改進的無線傳感器網絡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 。