朱素文，曾憲華*，胡　夢(mèng)

（1.重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶400065；2.計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400065）

改進(jìn)的局部保持典型相關(guān)分析的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法*

朱素文1，2，曾憲華1，2*，胡夢(mèng)1，2

（1.重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶400065；2.計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400065）

利用接收信號(hào)強(qiáng)度（RSSI）進(jìn)行無線傳感器網(wǎng)絡(luò)（WSN）定位是一類低成本定位方法。局部保持典型相關(guān)分析定位（LE-LPCCA）算法能通過節(jié)點(diǎn)間RSSI數(shù)據(jù)的相似度信息近似擬合WSN結(jié)構(gòu)，取得了較高定位精度。但該算法只使用節(jié)點(diǎn)間相似性信息未保留信號(hào)空間和物理空間的相關(guān)性信息，且求解未知節(jié)點(diǎn)坐標(biāo)時(shí)使用粗糙的質(zhì)心法。針對(duì)以上問題，提出改進(jìn)的局部保持典型相關(guān)分析定位（LE-ILPCCA）算法，該算法在樣本訓(xùn)練階段用平衡參數(shù)將數(shù)據(jù)的相似性和相關(guān)性信息進(jìn)行融合，求取RSSI內(nèi)在低維坐標(biāo)表示的投影變換；在定位階段，求解已知節(jié)點(diǎn)位置坐標(biāo)和RSSI內(nèi)在低維坐標(biāo)之間存在的線性轉(zhuǎn)換關(guān)系，獲得未知節(jié)點(diǎn)的坐標(biāo)。實(shí)驗(yàn)結(jié)果表明，本文算法與LE-LPCCA和LE-CCA相比定位精度高、穩(wěn)定性強(qiáng)。

無線傳感器網(wǎng)絡(luò)；定位；典型相關(guān)分析；局部保持投影

EEACC：6150；7230doi：10.3969/j.issn.1004-1699.2016.10.019

無線傳感器網(wǎng)絡(luò)系統(tǒng) WSN（Wireless Sensor Networks）主要應(yīng)用于事件的監(jiān)測(cè)，而事件發(fā)生的位置對(duì)檢測(cè)來說是至關(guān)重要的。目前應(yīng)用最為廣泛的全球定位系統(tǒng)GPS（Global Position System）在衛(wèi)星信號(hào)能到達(dá)的場(chǎng)所可以取得較好的定位效果，但其局限性較大，在室內(nèi)環(huán)境或遮擋較嚴(yán)重的場(chǎng)所就不再適用。此外，GPS設(shè)備成本和能量消耗都較高，無線傳感器網(wǎng)絡(luò)又是一個(gè)資源受限的網(wǎng)絡(luò)，能耗要求極為嚴(yán)格［1］。因此，利用網(wǎng)絡(luò)中部分已知位置節(jié)點(diǎn)的信息對(duì)未知節(jié)點(diǎn)的位置進(jìn)行估測(cè)的方法具有非常重要的研究?jī)r(jià)值。定位的目的是根據(jù)節(jié)點(diǎn)在全網(wǎng)絡(luò)中收集到的接收信號(hào)強(qiáng)度 RSSI（Received Signal Strength Indicator）等數(shù)據(jù)，確定節(jié)點(diǎn)在網(wǎng)絡(luò)中的物理位置。與其它定位技術(shù)相比，RSSI技術(shù)用于WSN定位中，所消耗的設(shè)備功率和成本較低，因此基于RSSI的定位算法被廣泛應(yīng)用。本文主要研究基于RSSI信息的定位方法。

借助統(tǒng)計(jì)學(xué)和流形學(xué)習(xí)對(duì)定位問題進(jìn)行建模和算法設(shè)計(jì)一直是研究熱點(diǎn)［2-7］。近年來，隨著機(jī)器學(xué)習(xí)的發(fā)展，Pan Junfeng等提出基于核典型相關(guān)分析定位LE-KCCA（Location Estimation-Kernel Canonical Correlation Analysis）算法［8］，它集合CCA和核函數(shù)，對(duì)信號(hào)空間和物理空間求出一個(gè)統(tǒng)一的非線性映射，但未考慮WSN復(fù)雜多變的拓?fù)浣Y(jié)構(gòu)。顧晶晶等提出局部保持典型相關(guān)分析定位LE-LPCCA（Location Estimation-Locality Preserving Canonical Correlation Analysis）算法［9］，該算法將數(shù)據(jù)的局部結(jié)構(gòu)信息引入到CCA中，能較好的擬合WSN結(jié)構(gòu)，取得較高定位精度。陳祠等提出基于主成分分析的室內(nèi)指紋定位模型［10］，它將對(duì)定位精度影響最大的一組“成分”作為指導(dǎo)定位的指紋，在減少計(jì)算量的同時(shí)提高定位精度。Lee等提出一種基于多維尺度支持向量回歸的非測(cè)距定位算法［11］，該算法與標(biāo)準(zhǔn)支持向量回歸不同，在不轉(zhuǎn)化為多點(diǎn)定位問題的前提下實(shí)現(xiàn)多個(gè)輸出，具有較好的魯棒性和較高的定位精度。曾憲華等提出多粒度流形學(xué)習(xí)的定位方法［12］，該方法可以通過不同的篩選半徑獲得網(wǎng)絡(luò)的不同粒度，靈活地刻畫網(wǎng)絡(luò)結(jié)構(gòu)，降低計(jì)算復(fù)雜度的同時(shí)提高了定位精度。

文獻(xiàn)［9］中提出的LE-LPCCA算法利用節(jié)點(diǎn)間RSSI相似度信息，即信號(hào)數(shù)據(jù)本身的內(nèi)在特性，能夠近似擬合復(fù)雜的WSN拓?fù)浣Y(jié)構(gòu)，從而取得較高的定位精度。但該算法只使用節(jié)點(diǎn)間相似性信息，未保留信號(hào)量和位置數(shù)據(jù)的相關(guān)性信息，這將導(dǎo)致數(shù)據(jù)相關(guān)性信息丟失、訓(xùn)練數(shù)據(jù)信息不夠豐富，進(jìn)而使RSSI內(nèi)在低維坐標(biāo)表示的投影變換求解不精準(zhǔn)；且計(jì)算未知節(jié)點(diǎn)坐標(biāo)時(shí)使用粗糙的計(jì)算方法—質(zhì)心法，不能精確地獲得未知節(jié)點(diǎn)的物理坐標(biāo)。針對(duì)以上問題，本文做以下兩點(diǎn)改進(jìn)：（1）在訓(xùn)練階段，目標(biāo)函數(shù)中使用平衡參數(shù)α對(duì)樣本的相似性信息和相關(guān)性信息進(jìn)行融合，樣本訓(xùn)練時(shí)數(shù)據(jù)信息會(huì)更為豐富、完整，可以使得到的RSSI內(nèi)在低維坐標(biāo)表示的投影變換更加精準(zhǔn)；（2）在定位階段，用訓(xùn)練階段得到的投影變換對(duì)已知數(shù)據(jù)中高維的信號(hào)強(qiáng)度矩陣進(jìn)行維度約減，求取已知節(jié)點(diǎn)位置坐標(biāo)矩陣和降維后的信號(hào)量矩陣之間存在的較為精確的線性轉(zhuǎn)換關(guān)系，未知節(jié)點(diǎn)的估測(cè)坐標(biāo)將通過這一轉(zhuǎn)換關(guān)系得到。與質(zhì)心法相比，精確的線性轉(zhuǎn)換關(guān)系在提高定位精度上起較大的作用。

1　相關(guān)工作

在節(jié)點(diǎn)功率相同、傳送模式相似的前提下，傳感器網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)若相鄰，則接收到同一信標(biāo)節(jié)點(diǎn)所發(fā)射的信號(hào)強(qiáng)度也相似，所以物理空間和信號(hào)空間存在一一映射關(guān)系［8］。以本文其中一個(gè)實(shí)驗(yàn)的數(shù)據(jù)集來說明這一映射關(guān)系的合理性，表1為傳感器網(wǎng)絡(luò)節(jié)點(diǎn)位置與接收信號(hào)強(qiáng)度向量關(guān)系表。這里取8個(gè)點(diǎn)作為參考，其中信標(biāo)節(jié)點(diǎn)個(gè)數(shù)為5，表1中1～2列為節(jié)點(diǎn)的橫縱坐標(biāo)、3～7列為每個(gè)節(jié)點(diǎn)的5維接收信號(hào)強(qiáng)度值，從表中很容易看出，位置相近的點(diǎn)接收信號(hào)強(qiáng)度向量也十分相似。無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)定位問題可以看作是：在RSSI向量構(gòu)成的信號(hào)空間和縱橫坐標(biāo)（這里考慮二維空間定位）構(gòu)成的物理空間尋找一個(gè)合適的映射關(guān)系。一旦找出該映射關(guān)系，就能通過未知節(jié)點(diǎn)的RSSI向量得到該節(jié)點(diǎn)的物理位置坐標(biāo)。

表1　傳感器網(wǎng)絡(luò)節(jié)點(diǎn)位置與接收信號(hào)強(qiáng)度向量關(guān)系表

對(duì)于一個(gè)無線傳感器網(wǎng)絡(luò)，大量的傳感節(jié)點(diǎn)部署在區(qū)域C?R2內(nèi)，其中m個(gè)接入點(diǎn)（AP）向非接入點(diǎn)周期性發(fā)送信號(hào)。尋求映射關(guān)系，需要收集n個(gè)位置已知的節(jié)點(diǎn)組成的位置坐標(biāo)矩陣L=（l1，l2，…，ln）∈R2×n及其對(duì)應(yīng)的從m個(gè)接入點(diǎn)接收到的信號(hào)強(qiáng)度向量組成的信號(hào)強(qiáng)度矩陣S=（s1，s2，…，sn）∈Rm×n；或某一移動(dòng)節(jié)點(diǎn)沿某一軌跡移動(dòng)，記錄這一軌跡上n個(gè)坐標(biāo)已知的位置并組成位置坐標(biāo)矩陣L=（l1，l2，…，ln）∈R2×n及經(jīng)過這n個(gè)位置點(diǎn)時(shí)所對(duì)應(yīng)的信號(hào)強(qiáng)度向量，并組成信號(hào)強(qiáng)度矩陣S=（s1，s2，…，sn）∈Rm×n。以上為求解映射關(guān)系時(shí)所使用到的訓(xùn)練數(shù)據(jù)，當(dāng)對(duì)未知節(jié)點(diǎn)求解時(shí)（即定位階段），輸入任一未知節(jié)點(diǎn)g的接收信號(hào)強(qiáng)度向量sg=（s1g，s2g，…，smg）T∈Rm×1，依據(jù)映射關(guān)系，就能求得該節(jié)點(diǎn)的位置估測(cè)坐標(biāo)。

在機(jī)器學(xué)習(xí)領(lǐng)域，典型相關(guān)分析CCA（CanonicalCorrelation Analysis）［14］是構(gòu)建兩組數(shù)據(jù)間映射的經(jīng)典方法，它是利用綜合變量對(duì)之間的相關(guān)關(guān)系來反映兩組指標(biāo)之間的整體相關(guān)性的多元統(tǒng)計(jì)分析方法。給定一組成對(duì)樣本（X，Y），其中X=［x1，x2，…，xn］∈Rs×n，Y=［y1，y2，…，yn］∈Rt×n，這里假定樣本已中心化。CCA旨在為 X和Y分別尋找兩組基向量（wx∈Rs，wy∈Rt），使隨機(jī)變量wxTx和wyTy之間的相關(guān)程度最大。具體來講，表示為求解式（1）相關(guān)系數(shù)ρ的最大值問題［14］：

式（1）定義的相關(guān)函數(shù)ρ關(guān)于wx和wy尺度無關(guān)，則CCA可表示為式（2）優(yōu)化問題的解［14］：

求解該最優(yōu)化問題，文獻(xiàn)［14］給出了詳細(xì)的方法。通?？梢缘玫揭唤M基向量對(duì)（wxi，wyi）（i=1，…，d）及其對(duì)應(yīng)的特征值，并將它們組成兩個(gè)投影矩陣：Wx=［wx1，wx2，…，wxd］和 Wy=［wy1，wy2，…，wyd］。CCA可以為尋求信號(hào)空間和物理空間之間的映射關(guān)系提供依據(jù)，但它只能提取兩組數(shù)據(jù)之間的線性關(guān)系，根據(jù)求得的投影矩陣使典型變量之間的相關(guān)性達(dá)到最大，而WSN定位問題中所使用的數(shù)據(jù)多數(shù)為高維、非線性的。

文獻(xiàn)［9］中的LE-LPCCA算法針對(duì)LE-KCCA［8］對(duì)信號(hào)空間和物理空間求出一個(gè)統(tǒng)一的非線性映射、無法體現(xiàn)網(wǎng)絡(luò)的分布特性這一不足，通過局部保持投影LPP（Locality Preserving Projections）［13］將網(wǎng)絡(luò)的局部結(jié)構(gòu)信息引入到CCA中，將原來的全局非線性問題轉(zhuǎn)變成若干個(gè)局部的線性問題，計(jì)算每個(gè)鄰域內(nèi)的典型相關(guān)問題，通過優(yōu)化目標(biāo)函數(shù)計(jì)算得到一組投影基向量。LPP方法主要是通過一定的性能目標(biāo)來尋找線性變換以實(shí)現(xiàn)對(duì)高維數(shù)據(jù)的降維，它注重?cái)?shù)據(jù)內(nèi)在的特性，即：復(fù)雜多變的無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)，旨在尋求隱含在高維數(shù)據(jù)中的低維流形結(jié)構(gòu)，LE-LPCCA正是利用LPP這一特性，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的學(xué)習(xí)。下面具體介紹LE-LPCCA算法。

LE-LPCCA算法的輸入為n個(gè)已知節(jié)點(diǎn)的位置坐標(biāo)矩陣L=（l1，l2，…，ln）∈R2×n及其對(duì)應(yīng)的接收信號(hào)強(qiáng)度矩陣S=（s1，s2，…，sn）∈Rm×n，未知節(jié)點(diǎn)g的接收信號(hào)強(qiáng)度向量sg=（sg1，sg2，…，sgm）T∈Rm×1；輸出為未知節(jié)點(diǎn)g的位置坐標(biāo)。

式中，ts和tl分別表示信號(hào)空間和物理空間的平均距離，這樣的取法是為了使相似度矩陣更好地模擬網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。其中，

根據(jù)以上描述，WSN定位問題的目標(biāo)函數(shù)為：

其中，GSL，GSS和 GLL的計(jì)算如下：GSL=SCSLLT，GSS=SCSSST，GLL=LCLLLT。CSL=DSL-GS°GL，CSS= DSS-GS°GS，CLL=DLL-GL°GL。符號(hào) °為算子；DSS（DLL，DSL）是大小為n×n的對(duì)稱陣，其第i個(gè)對(duì)角元素等于矩陣GS°GS（GL°GL，GS°GL）第i行（因其對(duì)稱性，或第i列）元素之和。

其次，優(yōu)化目標(biāo)函數(shù)，求出投影矩陣WS和WL以及廣義特征值λ，并對(duì)已知數(shù)據(jù)｛S，L｝作線性變換：，使數(shù)據(jù)降到二維空間，同樣對(duì)未知數(shù)據(jù)進(jìn)行線性變換，得到用式（5）計(jì)算未知點(diǎn)g與所有已知節(jié)點(diǎn)在線性變換后帶有權(quán)重的歐式距離［8］：

其中，di表示第i個(gè)已知節(jié)點(diǎn)與g點(diǎn)的距離；λj表示第i個(gè)特征值的第 j個(gè)分量；表示第i個(gè)已知節(jié)點(diǎn)作線性變化后第 j個(gè)分量；表示g點(diǎn)作線性變化后的第 j個(gè)分量。

最后，計(jì)算未知節(jié)點(diǎn)K近鄰節(jié)點(diǎn)：K個(gè)di（i=1，…，n）（第i個(gè)已知節(jié)點(diǎn)與g點(diǎn)的距離）的最小值及對(duì)應(yīng)節(jié)點(diǎn)的物理坐標(biāo)｛y1，y2，…，yK｝，其質(zhì)心即為未知節(jié)點(diǎn)g的物理坐標(biāo)。

該算法優(yōu)化目標(biāo)函數(shù)時(shí)只使用節(jié)點(diǎn)間相似度信息未保留信號(hào)空間和物理空間的相關(guān)性信息（協(xié)方差），數(shù)據(jù)間相關(guān)性信息的丟失會(huì)導(dǎo)致RSSI內(nèi)在低維坐標(biāo)表示的投影變換求解不精；且算法最后一步求解未知節(jié)點(diǎn)坐標(biāo)時(shí)采用粗糙的計(jì)算方法—質(zhì)心法，不能用較為精確的方式求解出未知節(jié)點(diǎn)坐標(biāo)。

2　LE-ILPCCA定位算法

LE-LPCCA能夠?qū)W習(xí)節(jié)點(diǎn)間相似度信息，進(jìn)而對(duì)無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)近似擬合，從而取得相對(duì)高的定位精度，但該算法的目標(biāo)函數(shù)只使用數(shù)據(jù)相似性信息未保留信號(hào)空間和物理空間的相關(guān)性信息，且求解過程中使用粗糙的計(jì)算方法—質(zhì)心法。針對(duì)以上問題，本文提出改進(jìn)的局部保持典型相關(guān)分析定位 LE-ILPCCA（Location Estimation-Improved Locality Preserving Canonical Correlation Analysis）算法，該算法分為兩個(gè)階段：訓(xùn)練階段和定位階段。訓(xùn)練階段，用一個(gè)平衡參數(shù)將數(shù)據(jù)的相似性和相關(guān)性信息進(jìn)行融合，對(duì)收集到的已知節(jié)點(diǎn)數(shù)據(jù)進(jìn)行訓(xùn)練，從而求解目標(biāo)函數(shù)得到合適的參數(shù)，即：較為精確的RSSI內(nèi)在低維坐標(biāo)表示的投影變換矩陣；定位階段，根據(jù)已知節(jié)點(diǎn)數(shù)據(jù)和訓(xùn)練階段得到的參數(shù)，求解已知節(jié)點(diǎn)位置坐標(biāo)和RSSI內(nèi)在低維坐標(biāo)之間存在的較為精確的線性轉(zhuǎn)換關(guān)系，并利用這一轉(zhuǎn)換關(guān)系對(duì)未知節(jié)點(diǎn)的位置坐標(biāo)進(jìn)行計(jì)算。

2.1訓(xùn)練階段

訓(xùn)練階段是通過收集到的信號(hào)空間的RSSI數(shù)據(jù)和物理空間的位置坐標(biāo)數(shù)據(jù)，計(jì)算兩空間數(shù)據(jù)的相似性和相關(guān)性信息，在目標(biāo)函數(shù)中用平衡參數(shù)將數(shù)據(jù)相似性和相關(guān)性信息進(jìn)行融合，后對(duì)其進(jìn)行優(yōu)化求解，求取較為精確的RSSI內(nèi)在低維坐標(biāo)表示的投影變換矩陣。

訓(xùn)練階段輸入數(shù)據(jù)為：n個(gè)已知節(jié)點(diǎn)的位置坐標(biāo)矩陣L=（l1，l2，…，ln）∈R2×n及其對(duì)應(yīng)的接收信號(hào)強(qiáng)度矩陣S=（s1，s2，…，sn）∈Rm×n，p個(gè)未知節(jié)點(diǎn)的接收信號(hào)強(qiáng)度矩陣Sg=（sg1，sg2，…，sgp）∈Rm×p。

首先用式（6）分別計(jì)算信號(hào)矩陣和位置矩陣的集合內(nèi)協(xié)方差矩陣CovSS、CovLL及兩矩陣的集合間協(xié)方差矩陣CovSL。

綜上所述，WSN定位問題的目標(biāo)函數(shù)為：

為了簡(jiǎn)化公式復(fù)雜性并方便接下來的求解運(yùn)算，令：

則式（7）可簡(jiǎn)化為式（9）：

對(duì)式（9）利用拉格朗日乘數(shù)法及消元解方程法，可得到如下特征值方程組：

最終得到如下廣義特征值方程：

解方程并求解出更為精確的RSSI內(nèi)在低維坐標(biāo)表示的投影變換矩陣WS。以上為WSN定位問題中求解合適參數(shù)的訓(xùn)練階段。

2.2定位階段

當(dāng)輸入新的數(shù)據(jù)如：p個(gè)未知節(jié)點(diǎn)的接收信號(hào)強(qiáng)度矩陣Sg=（sg1，sg2，…，sgp），即進(jìn)入WSN定位階段時(shí)，使用訓(xùn)練階段得到的投影矩陣WS對(duì)訓(xùn)練數(shù)據(jù)中高維的信號(hào)強(qiáng)度矩陣S進(jìn)行維度約減，將其降到二維空間，作為候選二維信號(hào)強(qiáng)度矩陣PS。當(dāng)對(duì)信號(hào)強(qiáng)度矩陣Sg中對(duì)應(yīng)的每個(gè)未知節(jié)點(diǎn)gi（i=1，…，p）進(jìn)行位置估測(cè)時(shí)，首先使用投影矩陣WS將高維信號(hào)強(qiáng)度向量sgi降到二維空間，再用式（5）計(jì)算gi和所有已知點(diǎn)（訓(xùn)練數(shù)據(jù)點(diǎn)）之間帶有權(quán)重的歐氏距離［8］，并選取其中最短的K個(gè)距離所對(duì)應(yīng)的候選二維信號(hào)強(qiáng)度矩陣和二維位置坐標(biāo)矩陣中的K個(gè)列向量，分別組成兩組含有K個(gè)元素的矩陣PS_K和L_K。通過以下推導(dǎo)建立這兩個(gè)矩陣之間的線性轉(zhuǎn)換關(guān)系W。gi的估測(cè)坐標(biāo)將通過這一轉(zhuǎn)換關(guān)系W得到。

設(shè)xi和分別表示二維位置坐標(biāo)矩陣L_K和對(duì)應(yīng)的二維信號(hào)強(qiáng)度矩陣PS_K，則它們之間的關(guān)系可以表示為xi=Wyi+b。其中，W是坐標(biāo)轉(zhuǎn)換矩陣，b是偏移量，是二維的，則：

分別任取xi和yi中的一個(gè)點(diǎn)做以下處理：

設(shè)yvs代表未知節(jié)點(diǎn)xv（v≠1，…，n）轉(zhuǎn)換后的二維信號(hào)強(qiáng)度向量，則未知節(jié)點(diǎn)xv的位置坐標(biāo)xvl求法為：

2.3LE-ILPCCA定位算法描述

文獻(xiàn)［9］中提出的LE-LPCCA算法結(jié)合LPP將網(wǎng)絡(luò)分布的局部信息和全局信息引入CCA中。然而，現(xiàn)有的LE-LPCCA存在信號(hào)空間和物理空間相關(guān)性信息丟失及求解未知節(jié)點(diǎn)坐標(biāo)時(shí)使用粗糙質(zhì)心法等問題。為彌補(bǔ)上述缺陷，本文提出改進(jìn)的局部保持典型相關(guān)分析定位（LE-ILPCCA）算法，在LE-LPCCA算法的目標(biāo)函數(shù)中增加信號(hào)空間和物理空間的相關(guān)性信息，用一個(gè)平衡參數(shù)將節(jié)點(diǎn)間相似性信息和兩空間的相關(guān)性信息融合起來，進(jìn)而求取一種RSSI內(nèi)在低維坐標(biāo)表示的投影變換，并根據(jù)已知節(jié)點(diǎn)位置坐標(biāo)和RSSI內(nèi)在低維坐標(biāo)之間存在的較為精確的線性轉(zhuǎn)換關(guān)系，獲得未知節(jié)點(diǎn)的坐標(biāo)。LE-ILPCCA算法的步驟如下：

算法1　LE-ILPCCA定位算法

圖1為L(zhǎng)E-ILPCCA定位算法示意圖，灰色部分代表算法的訓(xùn)練階段，主要是利用已知節(jié)點(diǎn)的數(shù)據(jù)和融合了協(xié)方差信息和相似度信息的目標(biāo)函數(shù)，求解數(shù)據(jù)內(nèi)在低維坐標(biāo)表示的投影變換矩陣；藍(lán)色部分代表算法的定位階段，該階段通過訓(xùn)練階段得到的投影矩陣，計(jì)算訓(xùn)練數(shù)據(jù)及未知數(shù)據(jù)的二維空間表示，并利用帶權(quán)值的歐氏距離求解未知節(jié)點(diǎn)的K個(gè)近鄰點(diǎn)組成的信號(hào)強(qiáng)度矩陣和位置坐標(biāo)矩陣，再根據(jù)這兩個(gè)矩陣間的轉(zhuǎn)換關(guān)系求得相對(duì)精確的線性轉(zhuǎn)換關(guān)系矩陣，最后用轉(zhuǎn)換關(guān)系矩陣和未知數(shù)據(jù)的二維空間表示得到該未知節(jié)點(diǎn)的位置坐標(biāo)。

圖1　LE-ILPCCA定位算法示意圖

3　實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證算法的性能，本文在兩組模擬數(shù)據(jù)和一組真實(shí)數(shù)據(jù)上做實(shí)驗(yàn)，并分別與LE-LPCCA和典型相關(guān)分析定位（Location Estimation-Canonical Correlation Analysis，LE-CCA）算法作對(duì)比，LE-CCA是為了實(shí)驗(yàn)比較而設(shè)計(jì)的算法。為保證實(shí)驗(yàn)更細(xì)致地進(jìn)行，本次試驗(yàn)中采用的變換間隔Δα為0.001，共循環(huán)1 001次。

兩組模擬數(shù)據(jù)分別模擬的是平方區(qū)域C內(nèi)隨機(jī)分布及均勻分布的無線傳感網(wǎng)絡(luò)，網(wǎng)絡(luò)中信號(hào)傳播模型選擇規(guī)則網(wǎng)絡(luò)模型，無線電射程為環(huán)形，兩網(wǎng)絡(luò)的通信半徑均為200 m。該模型與對(duì)數(shù)衰減模型（式（16））相比沒有遮擋因子，式（16）中Pr（dist），Pr（d0），η，dist，Xσ分別表示與發(fā)射器距離為dist時(shí)的接收信號(hào)功率、距離為d0時(shí)從發(fā)射器接收到的功率、路徑衰減指數(shù)、接收器與發(fā)射器之間的距離、遮擋影響因子［16］。兩模擬網(wǎng)絡(luò)中節(jié)點(diǎn)的接收信號(hào)功率可用式（17）表示。其中，Pt，Pl（d0）分別表示發(fā)射功率（0）、距離為d0（1 m）時(shí)的路徑衰減功率（取值55），其中η取值為4。C內(nèi)隨機(jī)分布及均勻分布的網(wǎng)絡(luò)中接入點(diǎn)個(gè)數(shù)分別為90和44，網(wǎng)絡(luò)中所有節(jié)點(diǎn)個(gè)數(shù)分別為900和441。兩網(wǎng)絡(luò)分布圖如圖2和圖3所示，其中紅色點(diǎn)代表接入點(diǎn)，藍(lán)色點(diǎn)代表非接入點(diǎn)。

圖2　平方區(qū)域C內(nèi)隨機(jī)網(wǎng)絡(luò)分布圖

圖3　平方區(qū)域C內(nèi)均勻網(wǎng)絡(luò)分布圖

真實(shí)數(shù)據(jù)來源于瑞典皇家理工學(xué)院計(jì)算機(jī)科學(xué)與通信系。實(shí)驗(yàn)場(chǎng)景設(shè)置在400 m2的辦公場(chǎng)所，其中包括一個(gè)走廊和若干個(gè)辦公室。實(shí)驗(yàn)中一個(gè)具有可拆式外置天線的Wi-Fi接入點(diǎn)固定在試驗(yàn)場(chǎng)景內(nèi)作為無線信號(hào)發(fā)射器，五個(gè)相同型號(hào)（TP-Link TL-WN722N）并裝有可拆式外置天線的小型USB無線網(wǎng)絡(luò)適配器安裝在KUKA youBot上。這些無線網(wǎng)絡(luò)適配器作為無線信號(hào)接收器與接入點(diǎn)通過2.4 GHz頻率帶寬的IEEE 802.11n相連接，無線適配器的通信半徑為50 m。收集數(shù)據(jù)時(shí)，機(jī)器人以小于0.2 m/s的速度行駛并記錄某些時(shí)刻的位置及其對(duì)應(yīng)的無線信號(hào)強(qiáng)度值（dBm）［17］。

本文采用文獻(xiàn)［18］的誤差判定標(biāo)準(zhǔn)，通過所有節(jié)點(diǎn)的平均誤差評(píng)判算法的性能。平均誤差定義如式（18），其中，n，r，li，l?i分別表示未知節(jié)點(diǎn)的個(gè)數(shù)、節(jié)點(diǎn)間單跳最大通信距離、未知節(jié)點(diǎn)的真實(shí)坐標(biāo)和未知節(jié)點(diǎn)的估測(cè)坐標(biāo)。

ave_error越小代表定位算法的精度越高。為了保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，每組實(shí)驗(yàn)都重復(fù)運(yùn)行了20次以上。每組實(shí)驗(yàn)中，用作驗(yàn)證算法有效性的測(cè)試樣本從未參與訓(xùn)練，且數(shù)量占總樣本比例的30%。

3.2轉(zhuǎn)換關(guān)系矩陣W及平衡參數(shù)α對(duì)平均定位誤差的影響

以兩組模擬數(shù)據(jù)集及一組真實(shí)數(shù)據(jù)為例，本文分析轉(zhuǎn)換關(guān)系矩陣W及平衡參數(shù)α對(duì)定位精度的影響。當(dāng)參數(shù)α為0時(shí)，本文算法可簡(jiǎn)化成與LE-CCA相近的算法，即與其唯一的不同之處在于求解未知節(jié)點(diǎn)坐標(biāo)時(shí)使用較為精確的轉(zhuǎn)換矩陣W而非質(zhì)心法；同理當(dāng)α為1時(shí)，本文算法可簡(jiǎn)化成與LE-LPCCA近似的算法，唯一的不同之處也和上述陳述一樣。本文算法采用的鄰域K是算法LE-ILPCCA（α=1）性能最優(yōu)時(shí)的值，訓(xùn)練樣本比例不同時(shí)K值也不同。每一個(gè)K值都對(duì)應(yīng)一個(gè)最優(yōu)的α值，當(dāng)K值相同時(shí)，本文算法總是優(yōu)于其它兩種對(duì)比算法。

圖4～圖9中縱坐標(biāo)均表示所有未知節(jié)點(diǎn)的平均定位誤差，橫坐標(biāo)均表示訓(xùn)練樣本百分比，它以10%為間隔從30%增加到70%。圖4、圖6、圖8中藍(lán)色曲線和紅色曲線分別代表法算法LE-CCA和LE-ILPCCA（α=0）的平均定位誤差變化趨勢(shì)，圖5、圖7、圖9中藍(lán)色曲線表示算法LE-LPCCA的平均定位誤差走勢(shì)，紅色曲線表示算法LE-ILPCCA（α=1）的平均定位誤差變化情況。圖4～圖6的實(shí)驗(yàn)數(shù)據(jù)均為模擬數(shù)據(jù)，圖8～圖9為真實(shí)環(huán)境下的數(shù)據(jù)。模擬數(shù)據(jù)中，藍(lán)色曲線和紅色曲線在不同訓(xùn)練樣本比例下平均定位誤差的差值較為明顯，差值為［0.061 2～0.690 2］；真實(shí)環(huán)境下平均定位誤差的差值為［0.001 4～0.001 9］，雖然沒有模擬數(shù)據(jù)中明顯，但紅色曲線依舊位于藍(lán)色曲線之下。以下六個(gè)圖中，對(duì)藍(lán)色曲線和紅色曲線走勢(shì)分析發(fā)現(xiàn)：無論樣本比例怎樣變化，每個(gè)圖中紅色曲線總是低于藍(lán)色曲線，即：使用轉(zhuǎn)換關(guān)系矩陣W后平均定位誤差整體降低。由此可以看出，無論α=0還是α=1轉(zhuǎn)換關(guān)系矩陣W在提高定位精度上都起著重要的作用。

圖4　轉(zhuǎn)換矩陣W對(duì)算法LE-CCA的影響圖（隨機(jī)網(wǎng)絡(luò)）

圖5　轉(zhuǎn)換矩陣W對(duì)算法LE-LPCCA的影響圖（隨機(jī)網(wǎng)絡(luò)）

圖6　轉(zhuǎn)換矩陣W對(duì)算法LE-CCA的影響圖（均勻網(wǎng)絡(luò)）

圖7　轉(zhuǎn)換矩陣W對(duì)算法LE-LPCCA的影響圖（均勻網(wǎng)絡(luò)）

圖8　轉(zhuǎn)換矩陣W對(duì)算法LE-CCA的影響圖（真實(shí)數(shù)據(jù)）

圖9　轉(zhuǎn)換矩陣W對(duì)算法LE-LPCCA的影響圖（真實(shí)數(shù)據(jù)）

平衡參數(shù)α將數(shù)據(jù)的相似度信息和協(xié)方差信息結(jié)合起來，既使用信號(hào)空間和物理空間的相似性信息，又保留兩空間之間的相關(guān)性信息，使訓(xùn)練樣本信息更加豐富、完整。表2～表4為平衡參數(shù)α對(duì)平均定位誤差的影響表，為了簡(jiǎn)化表格，平均誤差值都用AEV（Average Error Value）表示。表2～表4的實(shí)驗(yàn)數(shù)據(jù)分別為隨機(jī)網(wǎng)絡(luò)、均勻網(wǎng)絡(luò)和真實(shí)環(huán)境。

表2　平衡參數(shù)對(duì)平均定位誤差的影響表（隨機(jī)網(wǎng)絡(luò)）

表3　平衡參數(shù)對(duì)平均定位誤差的影響表（均勻網(wǎng)絡(luò)）

表4　平衡參數(shù)對(duì)平均定位誤差的影響表（真實(shí)環(huán)境）

分析3個(gè)表格的每一行（即在同一訓(xùn)練樣本比例下），可以看出第4列最小的AEV總是比第2列和第3列都小，這表明在轉(zhuǎn)換關(guān)系矩陣W減少了定位誤差的基礎(chǔ)上，平衡參數(shù)α又進(jìn)一步提高了定位精度。

3.3實(shí)驗(yàn)結(jié)果

圖10～圖12中，橫坐標(biāo)均表示訓(xùn)練樣本百分比（30%～70%），縱坐標(biāo)表示所有未知節(jié)點(diǎn)的平均定位誤差。藍(lán)色曲線、綠色曲線和紅色曲線分別表示算法LE-CCA、LE-LPCCA和LE-ILPCCA在訓(xùn)練樣本密度不斷增加的情況下節(jié)點(diǎn)平均定位誤差的變化趨勢(shì)。圖10和圖11都是模擬數(shù)據(jù)下的3種算法平均誤差對(duì)比圖，其區(qū)別在于圖10是隨機(jī)分布的網(wǎng)絡(luò)，圖11是均勻分布的網(wǎng)絡(luò)。圖12是真實(shí)數(shù)據(jù)下3種算法平均誤差對(duì)比圖。

圖10　隨機(jī)網(wǎng)絡(luò)中3種算法平均誤差對(duì)比圖

圖11　均勻網(wǎng)絡(luò)中3種算法平均誤差對(duì)比圖

圖12　真實(shí)數(shù)據(jù)中3種算法平均誤差對(duì)比圖

訓(xùn)練樣本比例從30%以10%為增量增加到70%時(shí)，圖10中，算法LE-CCA、LE-LPCCA和LE-ILPCCA的平均定位誤差變化范圍依次為［0.467 0～0.193 1］、［0.435 9～0.188 6］、［0.172 2～0.106 0］；圖11中，3種算法的平均定位誤差變化區(qū)間依次為［1.087 5～0.459 2］、［0.862 0～0.458 5］、［0.323 7～0.252 3］；圖12中，3種算法的平均定位誤差變化范圍依次為［0.170 2～0.132 4］、［0.168 6～0.127 7］、［0.161 9～0.124 9］。圖10和圖11中平均定位誤差的變化范圍表示，LE-ILPCCA算法的平均定位誤差明顯低于LE-CCA和LE-LPCCA，圖12中3種算法的平均定位誤差之間的差值沒有圖10和圖11明顯，但LE-ILPCCA算法的平均定位誤差仍舊低于其它兩種。通過對(duì)比以上三個(gè)圖可以看出，不論在模擬數(shù)據(jù)集還是真實(shí)數(shù)據(jù)集上，隨著訓(xùn)練樣本比例不斷增加，節(jié)點(diǎn)的平均定位誤差整體上都呈現(xiàn)不斷減小的趨勢(shì)，這是因?yàn)殡S著訓(xùn)練樣本數(shù)量的增加，用作訓(xùn)練投影矩陣的樣本信息更加豐富，從而對(duì)網(wǎng)絡(luò)的分布特性和兩空間之間映射關(guān)系的學(xué)習(xí)更準(zhǔn)確。無論訓(xùn)練樣本比例怎樣變化，每一個(gè)圖中的紅色曲線都低于綠色曲線和藍(lán)色曲線，這表示本文算法（LE-ILPCCA）在定位精度和算法穩(wěn)定性上總是優(yōu)于其它兩種算法（LE-CCA和LE-LPCCA）。

最后，定量分析本文算法（LE-ILPCCA）與對(duì)比算法相比平均誤差降低的百分比。表5～表7表示LE-ILPCCA與LE-CCA和LE-LPCCA相比平均定位誤差降低的百分比數(shù)值，三個(gè)表的實(shí)驗(yàn)數(shù)據(jù)分別來源于：隨機(jī)網(wǎng)絡(luò)、均勻網(wǎng)絡(luò)和真實(shí)環(huán)境。平均定位誤差降低的百分比計(jì)算方法為：對(duì)比算法的平均定位誤差減去本文算法的平均定位誤差再除以對(duì)比算法的平均定位誤差。為簡(jiǎn)化表格，平均誤差降低百分比用AERP（Average Error Reduction Percentage）表示。分析三個(gè)表格中平均定位誤差降低的百分比數(shù)值可以看出，LE-ILPCCA與對(duì)比算法相比：在模擬數(shù)據(jù)中，平均誤差降低的百分比維持在39%～71%之間；在真實(shí)環(huán)境中，降低的百分比在1.06%～7.65%之間。真實(shí)環(huán)境中本文算法與對(duì)比算法相比平均誤差降低的百分比沒有模擬數(shù)據(jù)中高，這是因?yàn)檎鎸?shí)環(huán)境的數(shù)據(jù)訓(xùn)練樣本數(shù)量較多，LE-CCA和LE-LPCCA得出的平均定位誤差已較低，維持在0.125 0～0.175 0之間，本文算法能進(jìn)一步降低平均誤差，但效果沒有模擬數(shù)據(jù)中明顯。

表5　本文算法與對(duì)比算法相比平均誤差降低的百分比（隨機(jī)網(wǎng)絡(luò)）

表6　本文算法與對(duì)比算法相比平均誤差降低的百分比（均勻網(wǎng)絡(luò)）

表7　本文算法與對(duì)比算法相比平均誤差降低的百分比（真實(shí)環(huán)境）

4　結(jié)論

本文提出改進(jìn)的局部保持典型相關(guān)分析定位LE-ILPCCA）算法，主要是針對(duì)局部保持典型相關(guān)分析定位（LE-LPCCA）算法存在的兩點(diǎn)不足：①訓(xùn)練階段，目標(biāo)函數(shù)中未保留信號(hào)空間和物理空間的相關(guān)性信息、僅使用節(jié)點(diǎn)間相似度信息，導(dǎo)致數(shù)據(jù)相關(guān)性信息丟失、數(shù)據(jù)內(nèi)在低維坐標(biāo)表示的投影變換不夠準(zhǔn)確；②定位階段，求解節(jié)點(diǎn)位置坐標(biāo)時(shí)使用較為粗糙的計(jì)算方法—質(zhì)心法，不能精確地求解出節(jié)點(diǎn)位置坐標(biāo)。本文算法彌補(bǔ)以上兩點(diǎn)不足，主要改進(jìn)之處在于：在樣本訓(xùn)練階段，同時(shí)使用已知數(shù)據(jù)的相似性信息和相關(guān)性信息，用平衡參數(shù)將兩者融合起來，求取較為精確的數(shù)據(jù)內(nèi)在低維坐標(biāo)表示的投影變換；在定位階段，根據(jù)已知節(jié)點(diǎn)位置坐標(biāo)矩陣和RSSI內(nèi)在低維坐標(biāo)之間存在的線性轉(zhuǎn)換關(guān)系，求解未知節(jié)點(diǎn)的坐標(biāo)。本文在兩組模擬數(shù)據(jù)及一組真實(shí)數(shù)據(jù)上做了實(shí)驗(yàn)，結(jié)果表明本文算法與LE-LPCCA和LE-CCA相比平均定位誤差較低、性能較穩(wěn)定。本文算法雖然克服以上兩個(gè)缺點(diǎn)，但未找到一個(gè)魯棒的算法來計(jì)算使節(jié)點(diǎn)平均定位誤差最小的平衡參數(shù)，且該算法適用于二維空間定位問題，未擴(kuò)展到三維空間中去，未來工作將在以上兩個(gè)方面做改進(jìn)。

［1］王營(yíng)冠，王智.無線傳感器網(wǎng)絡(luò)［M］.北京：電子工業(yè)出版社，2012.

［2］Shang Y，Ruml W，Zhang Y，et al.Localization from Mere Connectivity［C］//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking&Computing，Annapolis，Maryland，USA，2003：201-212.

［3］Patwari N，Hero I I I，Alfred O.Manifold Learning Algorithms for Localization in Wireless Sensor Networks［C］//International of Conference Acoustics，Speed，and Signal Processing，Quebec，Canada，2004：857-860.

［4］Samadian R，Noorhosseini S M.Probabilistic Support Vector Machine Localization in Wireless Sensor Networks［J］.ETRI Journal，2011，33（6）：924-934.

［5］Pan J J，Pan S J，Yin J，et al.Tracking Mobile Users in Wireless Networks via Semi-Supervised Colocalization［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（3）：587-600.

［6］陳淑敏，喬曉田，毛佳，等.基于接收信號(hào)強(qiáng)度（RSSI）的室內(nèi)二次定位方法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（4）：572-577.

［7］楊文鉑，邢鵬康，劉彥華.一種基于自適RSSI測(cè)距模型的無線傳感器網(wǎng)絡(luò)定位方法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（1）：137-141.

［8］Pan J J，Kwok J T，Yang Q，et al.Multidimensional Vector Regression for Accurate and Low-Cost Location Estimation in Pervasive Computing［J］.IEEE Transactions on Knowledge and Data Engineering，2006，18（9）：1181-1193.

［9］顧晶晶，陳松燦，莊毅.用局部保持典型相關(guān)分析定位無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)［J］.軟件學(xué)報(bào)，2010，21（11）：2883-2891.

［10］陳祠，牟楠，張晨.基于主成分分析的室內(nèi)指紋定位模型［J］.軟件學(xué)報(bào)，2013，24（S1）：98-107.

［11］Lee J，Choi B，Kim E.Novel Range-Free Localization Based on Multidimensional Support Vector Regression Trained in the Primal Space［J］.IEEE Transactions on Neural Networks and Learning Systems，2013，24（7）：1099-1113.

［12］曾憲華，唐勝枰.基于多粒度流形學(xué)習(xí)的無線傳感器網(wǎng)絡(luò)定位方法［J］.傳感技術(shù)學(xué)報(bào)，2013，26（8）：1152-1158.

［13］He X F，Niyogi P.Locality Preserving Projections（LPP）［C］//Neural Information Processing Systems，Vancouver，American，2004：96-103.

［14］Hardoon D R，Szedmak S，Shawe-Taylor J.Canonical Correlation Analysis：An Overview with Application to Learning Methods［J］.Neural Computation，2004，16（12）：2639-2664.

［15］Sun T K，Chen S C.Locality Preserving CCA with Applications to Data Visualization and Pose Estimation［J］.Image and Vision Computing，2007，25（5）：531-543.

［16］Rappaport T S.Wireless Communications：Principles and Practice［M］.New Jersey：Prentice Hall PTR，1996.

［17］Ramviyas Parasuraman，Sergio Caccamo，F(xiàn)redrik Baberg，Petter O-gren，CRAWDAD dataset kth/rss（v.2016 01 05），traceset：indoor，downloaded from http：//crawdad.org/kth/rss/20160105/indoor，doi：10.15783/C7088F，Jan 2016.

［18］王成群.基于學(xué)習(xí)算法的無線傳感器網(wǎng)絡(luò)定位問題研究［D］.浙江：浙江大學(xué)，2009.

朱素文（1991-），女，重慶郵電大學(xué)計(jì)算機(jī)學(xué)院碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)定位、流形學(xué)習(xí)等，zhusuwen@foxmail.com；

曾憲華（1973-），男，四川攀枝花人，2009年獲得北京交通大學(xué)計(jì)算機(jī)軟件與理論專業(yè)博士，現(xiàn)任重慶郵電大學(xué)計(jì)算機(jī)學(xué)院教授，碩士生導(dǎo)師，計(jì)算機(jī)學(xué)會(huì)會(huì)員，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺等，zengxh@cqupt.edu.cn；

胡夢(mèng)（1992-），女，重慶郵電大學(xué)計(jì)算機(jī)學(xué)院碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)定位、流形學(xué)習(xí)等，humeng1016@foxmail.com。

Improved Locality Preserving Canonical Correlation Analysis Node Localization Method in Wireless Sensor Networks*

ZHU Suwen1，2，ZENG Xianhua1，2*，HU Meng1，2
（1.College of Computer Science and Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China；2.Chongqing Key Laboratory of Computational Intelligence，Chongqing 400065，China）

Location methods in wireless sensor networks（WSN）by received signal strength indicator（RSSI）are relatively inexpensive.Location Estimation-Locality Preserving Canonical Correlation Analysis（LE-LPCCA）can fit the structure of WSN approximately using RSSI similarity among nodes and achieve high localization accuracy，but it only uses data similarity while ignoring data dependency between signal and physical space，and employs rough centroid method.As to problems above，this paper proposes Location Estimation-Improved Locality Preserving Canonical Correlation Analysis（LE-ILPCCA）method.In training phrase，it combines data similarity and dependency using a balance parameter to compute more precise projection transformation of RSSI inner lower dimensional coordinates；in localization phrase，it calculates location of unknown nodes utilizing accurate transformational relation between position coordinates and RSSI inner lower dimensional coordinates of known nodes.Experimental results show that our method has a higher accuracy and stability than LE-LPCCA and LE-CCA.

wireless sensor networks；localization；canonical correlation analysis；locality preserving projections

TP393

A

1004-1699（2016）10-1579-10

項(xiàng)目來源：國(guó)家自然科學(xué)基金項(xiàng)目（61075019）；2015年重慶市研究生科研創(chuàng)新項(xiàng)目（CYS15173）

2016-03-20修改日期：2016-04-21