引入虛擬節(jié)點的無線傳感器網(wǎng)絡(luò)ELM定位算法*

劉國繁， 趙天霓

(1.湖南工程學(xué)院 電氣信息學(xué)院，湖南 湘潭 411104；2.湘潭大學(xué) 信息工程學(xué)院，湖南 湘潭 411105)

0 引 言

無線傳感器網(wǎng)絡(luò)節(jié)點自身位置信息的獲取是大多數(shù)應(yīng)用的基礎(chǔ)，節(jié)點定位技術(shù)是無線傳感器網(wǎng)絡(luò)的關(guān)鍵支撐技術(shù)。依據(jù)是否測量距離，定位算法可劃分為基于測距的算法和非測距的算法[1]。前者[2]對距離進(jìn)行直接測量，通常定位精度相對較高，但節(jié)點需要額外硬件的支持，并且定位過程會消耗大量的能量。非測距算法[3]則依靠網(wǎng)絡(luò)連通度等信息即可計算未知節(jié)點的位置，對節(jié)點的硬件要求小。

反向傳播(back propagation,BP)定位算法是將BP神經(jīng)網(wǎng)絡(luò)用于節(jié)點定位的一類算法，但傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)需要人為設(shè)置大量訓(xùn)練參數(shù)，存在訓(xùn)練速度慢并且容易陷入局部最優(yōu)解等問題。極限學(xué)習(xí)機(extreme learning machine，ELM)的輸入權(quán)值和隱含層閾值均隨機產(chǎn)生，僅需要設(shè)置網(wǎng)絡(luò)的隱含層節(jié)點個數(shù)，即可產(chǎn)生唯一最優(yōu)解，并且無需迭代，因而學(xué)習(xí)速度快，具有良好的泛化性能[4～6]。將ELM應(yīng)用于節(jié)點定位可有效避免BP定位算法存在的問題，改善定位性能。

現(xiàn)有的定位算法均表明，錨節(jié)點比例越高，定位的精度越高[3]，但是錨節(jié)點的增多會使無線傳感器網(wǎng)絡(luò)的成本增加。引入虛擬節(jié)點[7～9]及次錨節(jié)點[10,11]等于虛擬地增加錨節(jié)點比例，在不增加硬件成本情況下，提高了無線傳感器網(wǎng)絡(luò)節(jié)點定位精度。本文將ELM用于無線傳感器網(wǎng)絡(luò)的節(jié)點定位，引入虛擬節(jié)點進(jìn)一步提高定位精度，仿真結(jié)果表明：使用ELM定位具有較小的定位誤差，且結(jié)合虛擬節(jié)點可進(jìn)一步減小定位誤差。

1 基于ELM的定位算法

1.1 ELM

對于N個樣本數(shù)組(xi,ti),xi=[xi1,xi2,...,xin]T∈Rn,ti=[ti1,ti2,...,tim]T∈Rm,隱含層節(jié)點數(shù)為L，激活函數(shù)為g(x),ELM模型可表示為

(1)

式中wj=[wj1,wj2,…,wjn]T為連接輸入節(jié)點與第j個隱含層節(jié)點的權(quán)值向量；βj為連接第j個隱含層節(jié)點與輸出節(jié)點間的權(quán)值向量；bj為第j個隱含層節(jié)點的閾值；g(wjxi+bj)是在輸入為xi時第j個隱含層節(jié)點的輸出。SLFNs模型能以零誤差逼近這N個樣本，上述N個等式可以寫為

(2)

式中H為隱含層輸出矩陣，H的第i列為第i個隱含層的節(jié)點對應(yīng)于輸入x1,x2,…,xN的輸出。求解式(2)，可以得到網(wǎng)絡(luò)參數(shù)為

β=H*T=(HTH)-1HTT

(3)

式中H*為隱含層輸出矩陣H的Moore-Penrose廣義逆。

1.2 最小跳數(shù)獲取

每個錨節(jié)點將自己的位置坐標(biāo)、自身ID信息、跳數(shù)(初值為0) 作為一個數(shù)據(jù)包發(fā)送給通信半徑內(nèi)的鄰居節(jié)點。鄰居節(jié)點接收數(shù)據(jù)包后,記錄下到錨節(jié)點的跳數(shù),當(dāng)接收到來自同一個錨節(jié)點的多個跳數(shù)信息時，刪除較大的跳數(shù)信息，保存最小的跳數(shù)信息，跳數(shù)值加1繼續(xù)轉(zhuǎn)發(fā)至鄰居節(jié)點。網(wǎng)絡(luò)中的所有節(jié)點(包括錨節(jié)點)記錄了距每個錨節(jié)點間的最小跳數(shù)。

1.3 ELM估算節(jié)點位置

設(shè)Si=(xi,yi)表示第i個節(jié)點的坐標(biāo)(位置)。Bi=[bi1,bi2,…,bim,…,biM]為各個錨節(jié)點間的最小跳數(shù)，bim為第i個錨節(jié)點與第m個錨節(jié)點間最小跳數(shù)，i=1,2,…,M，m=1,2,…,M，當(dāng)i=m，有bim=0。Bj=[bj1,bj2,…,bjm,…,bjM]為各未知節(jié)點到各錨節(jié)點之間的最小跳數(shù)，bjm為第j個未知節(jié)點與第m個錨節(jié)點間最小跳數(shù)，j=M+1,M+2,…,N，m=1,2,…,M。則估算步驟為：

1)無線傳感器網(wǎng)絡(luò)中隨機放置N個節(jié)點，其中前M個為錨節(jié)點，剩余N-M個為未知節(jié)點。錨節(jié)點向周圍鄰居節(jié)點發(fā)送坐標(biāo)、ID、跳數(shù)信息，網(wǎng)絡(luò)中所有節(jié)點記錄下最小跳數(shù)信息。

2)建立各節(jié)點與錨節(jié)點間最小跳數(shù)與對應(yīng)節(jié)點位置的ELM關(guān)系模型。以各節(jié)點與錨節(jié)點間最小跳數(shù)為輸入，對應(yīng)節(jié)點位置為輸出，將實驗數(shù)據(jù)劃分為訓(xùn)練集和測試集。

3)將Bi=[bi1,bi2,…，bim，…,biM]作為訓(xùn)練集的輸入，對應(yīng)錨節(jié)點的位置Si=(xi,yi)為訓(xùn)練集的輸出，i=1,2,…,M，m=1,2,…,M，對ELM算法進(jìn)行訓(xùn)練，保存訓(xùn)練獲得的參數(shù)H和β。

4)將Bj=[bj1,bj2,…,bjm,…,bjM]作為測試集，測試結(jié)果為對應(yīng)未知節(jié)點的位置Sj=(xj,yj)。輸入測試集，獲取測試結(jié)果并分析。

2 引入虛擬節(jié)點的ELM定位算法

2.1 次錨節(jié)點

文獻(xiàn)[8]將一部分未知節(jié)點升級為次錨節(jié)點實現(xiàn)了未知節(jié)點的定位問題。即網(wǎng)絡(luò)部署階段的部分未知節(jié)點，在定位過程得到較為精確的位置信息，升級為次錨節(jié)點，進(jìn)一步對未知節(jié)點進(jìn)行定位。節(jié)約了網(wǎng)絡(luò)成本并且使網(wǎng)絡(luò)定位精度得到了有效提高。

次錨節(jié)點的選擇，是在對未知節(jié)點進(jìn)行定位后，從中選出定位精度較為準(zhǔn)確的未知節(jié)點升級為次錨節(jié)點。次錨節(jié)點的位置信息是未知節(jié)點定位后得到的估計位置，由于未知節(jié)點的實際位置是未知的，從而無法判斷未知節(jié)點的實際位置與估計位置的誤差。本文使用虛擬節(jié)點來解決這一問題，在所有未知節(jié)點中選出定位誤差相對較小的未知節(jié)點作為次錨節(jié)點。

2.2 虛擬節(jié)點定位

虛擬節(jié)點沒有節(jié)點間的通信和信息交互能力，不能直接獲取虛擬節(jié)點到各錨節(jié)點之間的最小跳數(shù)，但是可以將距離轉(zhuǎn)化為跳數(shù)。假設(shè)虛擬節(jié)點的位置已知，可先求出虛擬節(jié)點與錨節(jié)點間距離，再將距離信息轉(zhuǎn)化為跳數(shù)信息。

如圖1，節(jié)點O為錨節(jié)點，節(jié)點A和B為虛擬節(jié)點，O的通信半徑為R，可知虛擬節(jié)點A和錨節(jié)點O之間距離DOAR，則虛擬節(jié)點B和錨節(jié)點之間距離大于一跳，B和O的最小跳數(shù)要綜合考慮B和周圍鄰居節(jié)點的跳數(shù)信息確定。

圖1 跳數(shù)分析

獲取虛擬節(jié)點與各錨節(jié)點之間最小跳數(shù)信息后，用訓(xùn)練好的ELM估計虛擬節(jié)點的位置信息。

2.3 次錨節(jié)點的選取

將虛擬節(jié)點估計位置與實際位置進(jìn)行比較，選出誤差足夠小的虛擬節(jié)點，刪除其余的虛擬節(jié)點，并記錄虛擬節(jié)點到各錨節(jié)點的最小跳數(shù)。

為了確定次錨節(jié)點，設(shè)到所有錨節(jié)點最小跳數(shù)相同的點位置相近。篩選出虛擬節(jié)點到各錨節(jié)點最小跳數(shù)與到各錨節(jié)點最小跳數(shù)相同的未知節(jié)點，其坐標(biāo)即對應(yīng)虛擬節(jié)點坐標(biāo)，將之升級為次錨節(jié)點。

2.4 引入虛擬節(jié)點的ELM定位算法流程

1)隨機放置N個節(jié)點，其中前M個為錨節(jié)點，剩余N-M個未知節(jié)點。錨節(jié)點向周圍鄰居節(jié)點發(fā)送坐標(biāo)、ID、跳數(shù)信息，網(wǎng)絡(luò)中所有節(jié)點記錄下最小跳數(shù)信息。Si=(xi,yi)表示第i個節(jié)點的坐標(biāo)(位置)。Bi=[bi1,bi2…bim…,biM]為各個錨節(jié)點間的最小跳數(shù)。Bj=[bj1,bj2,…bjm…,bjM]為各未知節(jié)點到各錨節(jié)點之間的最小跳數(shù)。

2)建立各節(jié)點與錨節(jié)點間最小跳數(shù)與對應(yīng)節(jié)點位置的ELM關(guān)系模型。以各節(jié)點與錨節(jié)點間最小跳數(shù)為輸入，對應(yīng)節(jié)點位置為輸出，將實驗數(shù)據(jù)劃分為訓(xùn)練集和測試集。

3)將Bi作為訓(xùn)練集的輸入，對應(yīng)錨節(jié)點的位置Si為訓(xùn)練集的輸出。對ELM算法進(jìn)行訓(xùn)練，保存訓(xùn)練獲得的參數(shù)H和β。

4)在網(wǎng)絡(luò)中設(shè)置C個虛擬節(jié)點，其位置表示為Tp=(xp,yp)，將虛擬節(jié)點與錨節(jié)點間距離轉(zhuǎn)化為跳數(shù)。各虛擬節(jié)點到各錨節(jié)點之間的最小跳數(shù)Bp=[bp1,bp2,…,bpm,…,bpM]，bpm為第p個虛擬節(jié)點與第m個錨節(jié)點間最小跳數(shù)，p=1,2,…,C，m=1,2,…,M。

6)篩選出Bj=[bj1,bj2,…,bjm,…,bjM]與Bq=[bq1,bq2,…bqm,…,bqM]相同的未知節(jié)點，將這P個未知節(jié)點確定為次錨節(jié)點，P≤D。

7)將次錨節(jié)點和錨節(jié)點均作為無線傳感器網(wǎng)絡(luò)的錨節(jié)點為其余未知節(jié)點提供定位信息。此時網(wǎng)絡(luò)中錨節(jié)點個數(shù)為M+P個，未知節(jié)點N-M-P個。

8)重新構(gòu)建各節(jié)點與錨節(jié)點間最小跳數(shù)與對應(yīng)節(jié)點位置的ELM關(guān)系模型。以Bi=[bi1,bi2,…,bim,…,bi(M+P)]，i=1,2…,M+P，m=1,2,…,M+P，為訓(xùn)練集的輸入，對應(yīng)錨節(jié)點的位置Si=(xi,yi)為訓(xùn)練集的輸出訓(xùn)練ELM。

9)令Bj=[bj1,bj2,…,bjm,…,bjM]為測試集，測試結(jié)果為對應(yīng)未知節(jié)點的位置Sj=(xj,yj)，j=M+P+1,M+2,…,N，m=1,2,…,M+P。輸入測試集，獲取測試結(jié)果并分析。

3 仿真分析

為驗證所述方法的性能，對傳統(tǒng)基于距離矢量跳(distance vector-based hop,DV-Hop)定位算法，BP定位算法改進(jìn)的加權(quán)質(zhì)心定位算法基于次級錨節(jié)點(improved weighted centroid localization algorithm for WSNs based on secondary anchor nodes,，IWCLA-SAN)算法[11]，ELM定位算法，以及引入虛擬節(jié)點的ELM算法分別在MATLAB平臺上進(jìn)行仿真。設(shè)所有節(jié)點均隨機分布在100 m×100 m的區(qū)域內(nèi)，每組不同條件的均仿真運行100次，對結(jié)果取平均值進(jìn)行分析比較。

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

對不同的錨節(jié)點比例進(jìn)行仿真對比，共隨機分布200個節(jié)點，通信半徑設(shè)為40 m，其如圖2所示。仿真結(jié)果中每種算法的定位誤差均隨錨節(jié)點所占比例的提升而減小。在錨節(jié)點比例小于10 %時，IWCLA-SAN算法誤差最小。但在錨節(jié)點比例大于等于10 %的情況下，引入虛擬節(jié)點的ELM定位算法較IWCLA-SAN，BP算法及DV-Hop算法誤差小。引入虛擬節(jié)點的ELM算法較ELM算法定位誤差平均下降了3.76 %，說明在錨節(jié)點所占比例不同的情況下，引入虛擬節(jié)點升級次錨節(jié)點對于降低節(jié)點定位誤差有效。

圖2 錨節(jié)點所占比例和定位誤差關(guān)系

3.2 對定位誤差影響

對不同通信半徑進(jìn)行仿真，仿真中共隨機分布200個節(jié)點，錨節(jié)點比例為10 %，仿真結(jié)果如圖3所示。在通信半徑小于35 m的情況下，IWCLA-SAN算法的定位誤差最小，但在通信半徑大于等于35 m的情況下，ELM算法較IWCLA-SAN、BP算法和DV-Hop算法誤差小，且引入虛擬節(jié)點的ELM算法較ELM算法定位誤差平均降低了4.22 %，表明在通信半徑不同的情況下，引入虛擬節(jié)點升級次錨節(jié)點對于降低節(jié)點定位誤差有效。

圖3 通信半徑和定位誤差的關(guān)系

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

對不同總節(jié)點數(shù)目進(jìn)行仿真，仿真通信半徑為40 m，錨節(jié)點比例為10 %，仿真結(jié)果如圖4所示。當(dāng)總節(jié)點數(shù)小于300個時，IWCLA-SAN算法的定位誤差最小，但當(dāng)總節(jié)點數(shù)大于等于300個時，ELM算法較IWCLA-SAN算法，BP算法及DV-Hop算法誤差都要小，且引入虛擬節(jié)點的ELM算法較ELM算法定位誤差平均降低了3.56 %，亦說明在總節(jié)點數(shù)目不同的時，引入虛擬節(jié)點升級次錨節(jié)點對于降低節(jié)點定位誤差有效。

圖4 總節(jié)點數(shù)和定位誤差的關(guān)系

4 結(jié) 論

采用虛擬節(jié)點和ELM算法結(jié)合的算法選出次錨節(jié)點來提高錨節(jié)點比例，降低定位誤差。在錨節(jié)點所占比例，通信半徑，總節(jié)點數(shù)目變化的情況下，均可以減小定位誤差，說明本文算法可以有效減小定位誤差。算法總體較DV-Hop算法和BP定位算法的誤差小，適用于無線傳感器網(wǎng)絡(luò)的定位，但對于錨節(jié)點比例和通信半徑以及總節(jié)點數(shù)目有一定的要求。

參考文獻(xiàn):

[1] 彭 宇，王 彤.無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J].電子測量與儀器學(xué)報，2011,25(5):389-399.

[2] 莫宏偉，董會元，基于光電傳感器的移動機器人室內(nèi)定位[J].自動化技術(shù)與應(yīng)用，2014,33(10)：33-36.

[3] 楊石磊,樊曉平,劉少強,等.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].計算機測量與控制,2008,16(9):1356-1358.

[4] Huang G B,Zhu Q Y,Siew C K.Extreme learning machine:A new learning scheme of feedforward neural networks[C]∥2004 Proceedings of IEEE International Joint Conference on Neural Networks,IEEE,2005:985-990.

[5] Huang G B,Zhu Q Y,Siew C K.Extreme learning machine: Theory and applications[J].Neurocomputing,2006,70(1-3):489-501.

[6] 王 雷，沈龍云，孫毅剛.基于ELM的航空發(fā)動機傳感器故障診斷方法研究[J].傳感器與微系統(tǒng),2015,34(4):16-18.

[7] Liu R,Sun K,Shen J.BP localization algorithm based on virtual nodes in wireless sensor networks[C]∥Proceedings of the 6th International Conference on Wireless Communications,Networking and Mobile Computing,WiCOM’10,2010:351-355.

[8] Zhao L Z,Wen X B,Li D.Amorphous localization algorithm based on BP artificial neural network[C]∥International Confe-rence on Software Intelligence Technologies and Applications & International Conference on Frontiers of Internet of Things,IET,2015.

[9] 龍 佳,卑璐璐,張 申,等.基于虛擬信標(biāo)節(jié)點的改進(jìn)加權(quán)質(zhì)心定位修正算法[J].微電子學(xué)與計算機,2017,34(3):74-78.

[10] 衣 曉，王梓有，薛興亮.一種基于次錨節(jié)點的無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法[J].計算機應(yīng)用與軟件，2013,30(6):116-120.

[11] 張先超,劉興長,張春園.基于次錨節(jié)點的無線傳感器網(wǎng)絡(luò)改進(jìn)加權(quán)質(zhì)心定位算法[J].傳感器與微系統(tǒng),2015,34(2):143-146.