基于壓縮感知的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法

趙春暉，許云龍，黃 輝

（哈爾濱工程大學(xué) 信息與通信工程學(xué)院，黑龍江 哈爾濱 150001）

無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）是一種全新的信息獲取平臺，可以在廣泛的應(yīng)用領(lǐng)域內(nèi)實(shí)現(xiàn)復(fù)雜的大范圍監(jiān)測和追蹤等任務(wù).其中，網(wǎng)絡(luò)節(jié)點(diǎn)自身定位是一個關(guān)鍵的問題，它是確定網(wǎng)絡(luò)路由協(xié)議［1］、實(shí)現(xiàn)目標(biāo)定位與追蹤等的前提.然而無線傳感器網(wǎng)絡(luò)是由廉價的能量有限的感知器組成，只有少部分的感知器節(jié)點(diǎn)知道自身的位置.因此，通過這些少量的位置信息去準(zhǔn)確、有效、快速地定位所有節(jié)點(diǎn)的位置已經(jīng)成為研究熱點(diǎn).

目前，已有許多算法來解決節(jié)點(diǎn)自身定位問題.但是，大多數(shù)算法通常只適合某類應(yīng)用，而不是通用的算法.因此，為了保證算法的可靠性、有效性及通用性，解決定位問題必須滿足以下3個條件：①依靠節(jié)點(diǎn)自身的通信設(shè)備來進(jìn)行節(jié)點(diǎn)定位，可以有效地降低定位的成本；②存在著少量的信標(biāo)節(jié)點(diǎn)，可以有效地提升定位精度，保證算法的有效性和可靠性；③節(jié)點(diǎn)不需要與信標(biāo)節(jié)點(diǎn)直接通信，可以有效地降低節(jié)點(diǎn)傳輸距離的要求及節(jié)點(diǎn)的通信能耗，同時保證算法的通用性.

無線傳感器網(wǎng)絡(luò)定位方法分為基于測距的（range－based）和無需測距的（range－free）定位兩類.典型的測距定位算法主要有：基于測距的定位通過測量距離進(jìn)行定位，如接收信號強(qiáng)度（RSSI）［2］、信號傳 播時間（TOA，TDOA）［3－4］、接收信號方向（AOA）［5］等.基于測距的定位一般精度較高，但是需要額外的測距設(shè)備.典型的距離無關(guān)定位算法主要有質(zhì)心算法（Centroid）［6－8］、APIT［9］、Diffusion［10］、LSVM［11］、LSRC［12］和WHEEL［13］等.顯然，基于測距的算法需要與信標(biāo)節(jié)點(diǎn)直接通信，明顯不滿足條件③，而無需測距的算法也大部分不符合上述3個條件.已知滿足以上條件的比較有代表性的算法有：Diffusion、LSVM 和LSRC算法，文獻(xiàn)［11］已經(jīng)證明了LSVM 算法比Diffusion算法性能優(yōu)越很多，因此本文將以LSVM 算法和LSRC 算法作為對比算法.

LSVM、LSRC算法將分類的原理應(yīng)用到節(jié)點(diǎn)定位中，必須建立分類模型，它們存在以下三個缺點(diǎn)：①在分類模型中，二者均是利用二叉樹分類結(jié)構(gòu)進(jìn)行定位，但是其在估計節(jié)點(diǎn)坐標(biāo)時，是把x，y 軸坐標(biāo)分開估計的，沒有更好地體現(xiàn)出節(jié)點(diǎn)之間連通信息的空間特征，因此定位精度不高.②分類模型的建立過程相當(dāng)復(fù)雜并且依賴信標(biāo)節(jié)點(diǎn)的位置信息，任意一個信標(biāo)節(jié)點(diǎn)的位置信息不正確，都將導(dǎo)致LSVM 和LSRC 算法的失效.③在LSVM 算法中需要選擇一個信標(biāo)節(jié)點(diǎn)當(dāng)作頭信標(biāo)結(jié)點(diǎn)去建立分類模型，將使這個頭信標(biāo)節(jié)點(diǎn)消耗較大，這對能耗要求較高的傳感器網(wǎng)絡(luò)是很不利的.

本文提出了兩種新的節(jié)點(diǎn)定位算法——基于壓縮感知的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法（node localization algorithm based on compressed sensing，NLCS）和 改 進(jìn)的 NLCS（improved NLCS，INLCS）.NLCS算法是一種無需測距的定位算法，其通過壓縮感知（compressed sensing，CS）［14］算法得到目標(biāo)節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的相關(guān)程度，并由相關(guān)程度去決定信標(biāo)節(jié)點(diǎn)對目標(biāo)節(jié)點(diǎn)定位的權(quán)值大小，最后得出目標(biāo)節(jié)點(diǎn)的估計位置.

相比于LSVM、LSRC算法，NLCS算法有以下幾個優(yōu)勢：①在估計節(jié)點(diǎn)的位置時，利用的是質(zhì)心算法，充分體現(xiàn)了目標(biāo)節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的空間相關(guān)性，從而提升了算法的定位精度.②在節(jié)點(diǎn)定位過程中，計算信標(biāo)節(jié)點(diǎn)對普通節(jié)點(diǎn)的權(quán)值影響時，并不使用信標(biāo)節(jié)點(diǎn)的位置，而僅僅使用節(jié)點(diǎn)間的連通信息，因此即使存在少數(shù)信標(biāo)節(jié)點(diǎn)的位置不正確，也不會影響信標(biāo)節(jié)點(diǎn)得到的采樣原子，這樣對于大多數(shù)目標(biāo)節(jié)點(diǎn)的定位并不會產(chǎn)生影響.③由于采樣字典是由各個信標(biāo)節(jié)點(diǎn)自身得到的采樣原子組成，這將更好地平衡網(wǎng)絡(luò)中各節(jié)點(diǎn)的能耗.

此外，針對LSVM、LSRC 和NLCS算法中，計算連通信息均采用的是最小跳數(shù)，這樣會導(dǎo)致目標(biāo)節(jié)點(diǎn)被信標(biāo)節(jié)點(diǎn)不準(zhǔn)確地描述，從而影響定位算法的精度，提出了偽跳數(shù)的概念，來進(jìn)一步改進(jìn)NLCS算法，得到INLCS算法.

1 CS 和Centroid

CS理論表明，如果信號是可壓縮的或在某個變換域是稀疏的，就可以通過一個滿足約束等距性條件（restricted isometry property，RIP）［15］的觀測矩陣將變換所得的高維信號投影成一個低維信號，最后通過求解一個優(yōu)化問題以高概率重構(gòu)出原信號.在CS模型中先對信號f 進(jìn)行稀疏變換，如下式所示：

式中，u，f 是N×1的向量；Ψ 是N×N的稀疏矩陣.如果Ψ 是滿秩的，且系數(shù)向量u中僅有k（k?N）個非零系數(shù)，則認(rèn)為信號u 在Ψ 上k 稀疏的.之后通過觀測矩陣Φ 得到信號f的觀測值y如下：

式中，y 是M×1的觀測向量；Φ 是M×N（M?N）的觀測矩陣，令A(yù)＝ΦΨ，它為CS信息算子.上述稀疏求解問題可以表示為下式：

由于上式l0－norm 問題是一個NP難題，無法直接求解.由于u 是稀疏的，因此可以把式（3）的問題轉(zhuǎn)化為l1－norm［16］或l2－norm［17］優(yōu)化問題，得到其稀疏解.

Centroid的主要思想是：未知節(jié)點(diǎn)以所有在其通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)的幾何質(zhì)心作為自己的估計位置.具體定位過程為：信標(biāo)節(jié)點(diǎn)周期性向鄰居節(jié)點(diǎn)廣播一個信標(biāo)信號，該信標(biāo)信號中包含有信標(biāo)節(jié)點(diǎn)自身的ID 和位置信息，當(dāng)未知節(jié)點(diǎn)在一段時間偵聽到來自信標(biāo)節(jié)點(diǎn)的信標(biāo)信號數(shù)量超過某一預(yù)設(shè)的門限值時，就認(rèn)為該信標(biāo)節(jié)點(diǎn)是未知節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，未知節(jié)點(diǎn)就把自己的位置確定為與之相鄰的所有信標(biāo)節(jié)點(diǎn)組成的多邊形的質(zhì)心，顯然，Centroid算法無法滿足前言第二段中的條件③.

本文借鑒Centroid的思想，通過信標(biāo)節(jié)點(diǎn)的連通信息線性分解普通節(jié)點(diǎn)的連通信息，來挖掘普通節(jié)點(diǎn)和所有信標(biāo)節(jié)點(diǎn)的相關(guān)程度，基于此決定每個信標(biāo)節(jié)點(diǎn)對質(zhì)心坐標(biāo)的權(quán)值大小，最后通過加權(quán)Centroid算法定位普通節(jié)點(diǎn)的坐標(biāo).

2 基于壓縮感知的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法（NLCS）

2.1 傳感器網(wǎng)絡(luò)模型

假設(shè)在［0，X］×［0，Y］（X，Y＞0）區(qū)域內(nèi)，存在N 個節(jié)點(diǎn)，分別用S1，S2，…，SN表示，其中k（k＜N）個節(jié)點(diǎn)的位置已知，稱這k 個節(jié)點(diǎn)S1，S2，…，Sk為信標(biāo)節(jié)點(diǎn)，稱其余N－k 個位置未知節(jié)點(diǎn)SN－k＋1，…，SN－k＋i，…，SN為普通節(jié)點(diǎn).假設(shè)所有的節(jié)點(diǎn)都有相同的通信半徑R，如果一個節(jié)點(diǎn)處在另一個節(jié)點(diǎn)的通信半徑R 之內(nèi)可以直接通信，稱之為單跳.用h（Si，Sj）（i，j＝1，2，…，N）表示節(jié)點(diǎn)Si和Sj之間的最短跳數(shù).文中假設(shè)存在k（k＜N）個信標(biāo)節(jié)點(diǎn)，它們知道自己的位置和到達(dá)對方的最佳路徑.需要設(shè)計一個分布式算法，通過這k 個節(jié)點(diǎn)去估計其余N－k 個節(jié)點(diǎn)的位置.現(xiàn)有的很多定位技術(shù)要求這N－k 個節(jié)點(diǎn)的通信范圍內(nèi)，必須有一些或全部單跳信標(biāo)節(jié)點(diǎn).而本文的算法則沒有這樣的要求，只需要每個節(jié)點(diǎn)可以與信標(biāo)節(jié)點(diǎn)通信，無論其是通過多跳路徑還是單跳路徑.因此，文中提出的方法，將更適用于傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)自定位.

2.2 定位算法原理

假設(shè)［x（Si），y（Si）］為第i個信標(biāo)節(jié)點(diǎn)的地理位 置，φi＝［h（Si，S1），h（Si，S2），…，h（Si，Sk）］T∈Rk×1（i＝1，2，…，k）為第i個信標(biāo)節(jié)點(diǎn)與所有k 個信標(biāo)節(jié)點(diǎn)的連通信息，其中，h（Si，Si）＝0，即節(jié)點(diǎn)到自身的跳數(shù)為0.將這些信標(biāo)節(jié)點(diǎn)的連通信息組合成稀疏變換矩陣Ψ：

同理，fj＝［h（Sj，S1），h（Sj，S2），…，h（Sj，Sk）］T（j＝N－k＋1，…，N）表示第j個普通節(jié)點(diǎn)與所有k 個信標(biāo)節(jié)點(diǎn)的連通信息.依據(jù)稀疏變換基Ψ，fj能夠被稀疏分解為：

式中，μj＝（μj，1，…，μj，i，…，μj，k）T是一個列向量，μj，i是第j 個普通節(jié)點(diǎn)在稀疏分解基下與第i 個信標(biāo)節(jié)點(diǎn)之間的相關(guān)程度.通常兩個節(jié)點(diǎn)位置越接近，則它們的相關(guān)程度可能越大，反之將很小，甚至為0.并且，第j個普通節(jié)點(diǎn)的連通信息的主要成分將被靠近其的少數(shù)幾個信標(biāo)節(jié)點(diǎn)的連通信息所描述，它們的系數(shù)將較大，而遠(yuǎn)離第j個普通節(jié)點(diǎn)的大多數(shù)信標(biāo)節(jié)點(diǎn)，它們的系數(shù)都接近于0或者等于0，這也就是說，μj是稀疏的.因此，通過CS可以準(zhǔn)確地重構(gòu)出這些相關(guān)系數(shù).

依據(jù)式（3），CS信息算子A 和壓縮連通信息yj可以分別表示為：

通過CS理論，式（7）中μj將被準(zhǔn)確地重構(gòu)，并利用μj得到第i 個信標(biāo)節(jié)點(diǎn)對第j 個普通節(jié)點(diǎn)的權(quán)值ωi，j，其表達(dá)式如下：

最后，通過加權(quán)質(zhì)心算法可以得到第j 個普通節(jié)點(diǎn)的估計位置［x（Sj），y（Sj）］為

2.3 協(xié) 議

根據(jù)以上所述，定位一個普通節(jié)點(diǎn)Sj的關(guān)鍵是通過壓縮感知算法得到第j 個普通節(jié)點(diǎn)和k 個信標(biāo)節(jié)點(diǎn)的相關(guān)程度.普通節(jié)點(diǎn)的定位協(xié)議可以分為三個階段：

（1）數(shù)據(jù)收集階段.首先使用典型的泛洪擴(kuò)散協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得距離信標(biāo)節(jié)點(diǎn)的最小跳數(shù).每個信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)發(fā)送一個消息Hello｛ID，h｝，ID 包括該信標(biāo)節(jié)點(diǎn)的標(biāo)號和其地理位置，h為跳數(shù)，其初始值為1.此后，為了防止消息的無限循環(huán)，各個接收節(jié)點(diǎn)只記錄到每個信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，忽略來自同一信標(biāo)節(jié)點(diǎn)的大跳數(shù)信息，然后將跳數(shù)值加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn).通過這一機(jī)制，使網(wǎng)絡(luò)中的所有節(jié)點(diǎn)知道到每一個信標(biāo)節(jié)點(diǎn)的最小跳數(shù).

（2）廣播階段.第i個信標(biāo)節(jié)點(diǎn)根據(jù)收到連通信息φi，對其進(jìn)行壓縮，得到采樣字典A的原子Ai.然后向整個網(wǎng)絡(luò)廣播Ai.

（3）定位階段.第j 個普通節(jié)點(diǎn)首先對自身到所有信標(biāo)節(jié)點(diǎn)的連通信息fj，通過測量矩陣Φ進(jìn)行壓縮，然后根據(jù)接收到的采樣字典A，并結(jié)合壓縮感知算法，得到其與所有信標(biāo)節(jié)點(diǎn)的相關(guān)程度μj，最后使用權(quán)值質(zhì)心算法計算其坐標(biāo)，得到其估計位置［x（Sj），y（Sj）］.

NLCS算法收集的連通信息均是各個節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，它們均為整數(shù)，這樣在較為鄰近的節(jié)點(diǎn)的連通信息就非常相似，因此，可能造成由所有信標(biāo)節(jié)點(diǎn)的連通信息組成的稀疏變換基，對目標(biāo)節(jié)點(diǎn)的連通信息進(jìn)行分解時，得到的稀疏分解結(jié)果不夠準(zhǔn)確.例如有兩個信標(biāo)節(jié)點(diǎn)接近于目標(biāo)節(jié)點(diǎn)，這兩個信標(biāo)節(jié)點(diǎn)的連通信息很相近，目標(biāo)節(jié)點(diǎn)就無法判斷出跟哪個更接近，這樣就可能會出現(xiàn)最接近目標(biāo)節(jié)點(diǎn)的信標(biāo)節(jié)點(diǎn)的相關(guān)程度可能不會是最大的，而較接近的將變成最大相關(guān)程度的信標(biāo)節(jié)點(diǎn).因此，它得到的稀疏分解肯定不是最優(yōu)的，這樣由它得到的目標(biāo)節(jié)點(diǎn)的定位精度也將受到影響.

3 改進(jìn)的NLCS（INLCS）

3.1 改進(jìn)原理

NLCS、LSRC和LSVM 算法中，由于各個節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的跳數(shù)值只能是整數(shù)，這樣它們彼此之間的跳數(shù)與它們之間距離的關(guān)系將不是很準(zhǔn)確，從而使得連通關(guān)系與距離的對應(yīng)關(guān)系不夠準(zhǔn)確，進(jìn)而影響稀疏分解的準(zhǔn)確性.基于此，文中提出了偽跳數(shù)的概念，來得到更精確的節(jié)點(diǎn)連通關(guān)系.偽跳數(shù)是使用信號強(qiáng)度來確定彼此之間的跳數(shù)關(guān)系，能使節(jié)點(diǎn)間的跳數(shù)與距離更好地對應(yīng)，使連通信息更加準(zhǔn)確.

偽跳數(shù)的獲?。好總€節(jié)點(diǎn)發(fā)送一個信號強(qiáng)度為P0的信號，這樣該節(jié)點(diǎn)的一跳節(jié)點(diǎn)將會接收到該信號，接收到的信號強(qiáng)度為Pi，之后各個一跳節(jié)點(diǎn)把該信號接收強(qiáng)度Pi反饋給這個節(jié)點(diǎn)，這樣該節(jié)點(diǎn)就得到了所有一跳節(jié)點(diǎn)信號接收強(qiáng)度.由于噪聲的存在，兩個鄰居節(jié)點(diǎn)得到的彼此接收信號強(qiáng)度不一樣，因此可以取這兩個彼此的信號接收強(qiáng)度值的平均值作為這兩個節(jié)點(diǎn)之間的信號接收強(qiáng)度值.之后利用泛洪擴(kuò)散協(xié)議，把每個節(jié)點(diǎn)得到的信號接收強(qiáng)度值中的最小值和最大值在網(wǎng)絡(luò)中進(jìn)行信息交換，得到整個網(wǎng)絡(luò)中所有節(jié)點(diǎn)中的信號接收強(qiáng)度的最大值Pmax與最小值Pmin.之后每個節(jié)點(diǎn)利用這些信號強(qiáng)度接收值來計算到其一跳節(jié)點(diǎn)的偽跳數(shù)，偽跳數(shù)計算公式如下：

式中，Phopi，j為第i 個節(jié)點(diǎn)與第j 個節(jié)點(diǎn)的偽跳數(shù)，且第i個節(jié)點(diǎn)與第j 個節(jié)點(diǎn)為鄰居節(jié)點(diǎn)，Pi，j為兩個節(jié)點(diǎn)之間的信號接收強(qiáng)度值.

基于上述原理，可以得到各個節(jié)點(diǎn)到其鄰居節(jié)點(diǎn)的偽跳數(shù)，之后利用這些偽跳數(shù)來得到各個節(jié)點(diǎn)到所有信標(biāo)節(jié)點(diǎn)的連通信息.由于連通信息是通過偽跳數(shù)取得，因此每個節(jié)點(diǎn)到所有信標(biāo)節(jié)點(diǎn)的連通信息將是非常準(zhǔn)確的.在INLCS 算法中，只需要對NLCS算法中的數(shù)據(jù)收集階段進(jìn)行修改，得到各個節(jié)點(diǎn)到所有信標(biāo)節(jié)點(diǎn)的更準(zhǔn)確的連通信息即可，修改的數(shù)據(jù)收集階段協(xié)議如下.

首先獲取每個節(jié)點(diǎn)與其一跳節(jié)點(diǎn)之間的偽跳數(shù).之后使用典型的泛洪擴(kuò)散協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)獲得距離信標(biāo)節(jié)點(diǎn)的最小偽跳數(shù)信息.每個信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)發(fā)送一個消息Hello｛ID，h｝，ID 包括該信標(biāo)節(jié)點(diǎn)的標(biāo)號和其地理位置，h為其到各個鄰居節(jié)點(diǎn)的偽跳數(shù)信息集合.此后，為了防止消息的無限循環(huán)，各個接收節(jié)點(diǎn)只記錄到每個信標(biāo)節(jié)點(diǎn)的最小偽跳數(shù)值，忽略來自同一信標(biāo)節(jié)點(diǎn)的大偽跳數(shù)值，其中，兩個節(jié)點(diǎn)間的偽跳數(shù)值為連通兩個節(jié)點(diǎn)的路徑上偽跳數(shù)的和值.然后節(jié)點(diǎn)把到每個信標(biāo)節(jié)點(diǎn)的最小偽跳數(shù)值和信標(biāo)節(jié)點(diǎn)ID 轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn).通過這一機(jī)制，使網(wǎng)絡(luò)中的所有節(jié)點(diǎn)知道到每一個信標(biāo)節(jié)點(diǎn)的最小偽跳數(shù)值.最后把這些最小偽跳數(shù)值組成每個節(jié)點(diǎn)的連通信息.

3.2 算法的有效性分析與對比

假設(shè)有1 000個傳感器節(jié)點(diǎn)隨機(jī)分布于大小為100m×100m的區(qū)域內(nèi)，其中信標(biāo)節(jié)點(diǎn)的比例為5%，節(jié)點(diǎn)通信半徑R＝6m，隨機(jī)選取其中一個普通節(jié)點(diǎn)，仿真出的該節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的相關(guān)系數(shù)示意圖如圖1所示.

圖1 節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的相關(guān)系數(shù)示意圖Fig.1 Schematic of the correlation coefficient between the node and beacon nodes

由圖1中可以發(fā)現(xiàn)，相關(guān)系數(shù)較大的項(xiàng)，總是對應(yīng)那些在幾何位置上比較靠近目標(biāo)節(jié)點(diǎn)的信標(biāo)節(jié)點(diǎn)，而大部分離目標(biāo)節(jié)點(diǎn)比較遠(yuǎn)的信標(biāo)節(jié)點(diǎn)的相關(guān)系數(shù)都等于0.此外，從圖1 中還可以看出，相關(guān)系數(shù)較大的節(jié)點(diǎn)非常少，大部分節(jié)點(diǎn)的相關(guān)系數(shù)為0或者接近于0，即相關(guān)系數(shù)向量是稀疏的.因此，通過壓縮感知算法能夠準(zhǔn)確地重構(gòu)出普通節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)的相關(guān)度，進(jìn)而較好地估計出普通節(jié)點(diǎn)的位置.

此外，通過對比圖1a和圖1b 可以看出，在INLCS算法中最靠近目標(biāo)節(jié)點(diǎn)的信標(biāo)節(jié)點(diǎn)的相關(guān)程度遠(yuǎn)大于其他信標(biāo)節(jié)點(diǎn)，而在NLCS 算法下，離目標(biāo)節(jié)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)所得的相關(guān)程度與離目標(biāo)節(jié)點(diǎn)較遠(yuǎn)的幾個信標(biāo)節(jié)點(diǎn)的相關(guān)程度值差不多，通過對比兩個分解圖可以看出在INLCS算法下的稀疏分解比NLCS 更準(zhǔn)確.因此，INLCS算法的定位精度將高于NLCS.

3.3 算法的能量分析與對比

從上面的分析可知，相比于NLCS 算法，INLCS算法中在數(shù)據(jù)收集階段需要每個節(jié)點(diǎn)獲取彼此之間的偽跳數(shù)，這個過程會帶來更多的能量消耗，而其他的過程是一樣的.但是，通過上節(jié)的算法分析可以看出，相比于NLCS 算法，INLCS算法提高了稀疏分解的準(zhǔn)確性，提高了算法的定位精度，并且下一節(jié)的實(shí)驗(yàn)結(jié)果也表明，相比較于NLCS算法來說，INLCS算法無論是平均定位誤差還是定位誤差標(biāo)準(zhǔn)差均得到了進(jìn)一步的改善，也就是說INLCS算法的定位性能要優(yōu)于NLCS算法.因此，在實(shí)際應(yīng)用中，需要均衡地考慮能量消耗和定位性能來選擇哪種算法更適合.

4 實(shí)驗(yàn)結(jié)果與分析

假設(shè)有1 000個傳感器節(jié)點(diǎn)隨機(jī)分布于大小為100m×100m的區(qū)域內(nèi)，其中信標(biāo)節(jié)點(diǎn)的比例分別為5%，10%，15%，20%，同時取兩個不同的通信半徑R＝6m 和R＝12m，得到了如圖2所示的INLCS、NLCS、LSRC、LSVM 算法的定位性能對比圖.

圖2 4種算法的定位性能對比Fig.2 Comparison of positioning performance of the four algorithms

由圖2a可以看出INLCS算法有最小的平均定位誤 差，NLCS 次 之，LSRC 和LSVM 相 對 較差.在R＝12m 時，NLCS算法的平均定位誤差甚至接近LSVM 算法在R＝6m的平均定位誤差.而對于INLCS算法，在R＝12m 時，其平均定位誤差優(yōu)于LSVM 和LSRC算法在R＝6m的平均定位誤差.從圖2b也很容易看出相比于LSVM和LSRC算法，NLCS和INLCS算法有更小的定位誤差標(biāo)準(zhǔn)差.這些是由于NLCS算法估計節(jié)點(diǎn)的位置利用的是質(zhì)心算法，能夠充分地體現(xiàn)出目標(biāo)節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的空間相關(guān)性，因此NLCS算法的定位性能較LSVM 和LSRC算法更優(yōu)異.此外，由于INLCS 算法利用偽跳數(shù)改進(jìn)了連通信息，使各個節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的連通信息更加準(zhǔn)確，因此目標(biāo)節(jié)點(diǎn)將能更準(zhǔn)確地被信標(biāo)節(jié)點(diǎn)所描述，從而進(jìn)一步提升了算法的性能.

為了更準(zhǔn)確地比較INLCS、NLCS、LSRC 和LSVM 算法的性能，檢驗(yàn)各個算法的適應(yīng)性，下面將考慮在較小的網(wǎng)絡(luò)中的定位性能.假設(shè)有250個傳感器節(jié)點(diǎn)隨機(jī)分布于大小為50m×50m的區(qū)域內(nèi)，其中信標(biāo)節(jié)點(diǎn)的比例分別為5%，10%，15%，20%，節(jié)點(diǎn)通信半徑R＝6m.表1是INLCS、NLCS、LSRC與LSVM 4種算法的定位性能對比，從表1中可以看出：在4種信標(biāo)節(jié)點(diǎn)的比例下，INLCS和NLCS算法的定位性能都優(yōu)于LSRC和LSVM 算法.因此，在小網(wǎng)絡(luò)中NLCS和INLCS算法仍然是更好的選擇.

表1 小網(wǎng)絡(luò)下的4種算法的性能對比Table 1 Performance comparison of four algorithms in small network

在實(shí)際應(yīng)用場合中，無線傳感器網(wǎng)絡(luò)中存在著網(wǎng)絡(luò)空洞，下文將進(jìn)一步驗(yàn)證INLCS、NLCS、LSRC和LSVM 算法的適應(yīng)性，考察網(wǎng)絡(luò)中存在網(wǎng)絡(luò)空洞時各個算法的定位性能.如圖3所示為存在著網(wǎng)絡(luò)空洞時的節(jié)點(diǎn)分布圖，圖3a為在網(wǎng)絡(luò)中心存在著一個網(wǎng)絡(luò)空洞時的節(jié)點(diǎn)分布圖，網(wǎng)絡(luò)空洞的圓心為網(wǎng)絡(luò)感知區(qū)域中心（50m×50m），R＝25m，圖3b為在網(wǎng)絡(luò)中心存在著一個大的網(wǎng)絡(luò)空洞和網(wǎng)絡(luò)的4角存在著4個小的網(wǎng)絡(luò)空洞時的節(jié)點(diǎn)分布圖，中心的網(wǎng)絡(luò)空洞的圓心為網(wǎng)絡(luò)感知區(qū)域中心（50m×50m），半徑為100／6m，4個角上的空洞半徑為100／12m.

圖3 空洞下的網(wǎng)絡(luò)節(jié)點(diǎn)分布圖Fig.3 Distribution of network nodes with holes

圖4為在1 000個傳感器節(jié)點(diǎn)隨機(jī)分布于大小為100m×100m的區(qū)域內(nèi)，其中信標(biāo)節(jié)點(diǎn)的比例分別為5%、10%、15%、20%，節(jié)點(diǎn)通信半徑R＝6m，并存在如圖3a、圖3b所示的網(wǎng)絡(luò)空洞下的定位性能對比圖.從圖4中可以看出：在4種信標(biāo)節(jié)點(diǎn)的比例下，INLCS、NLCS算法的定位性能都優(yōu)于LSVM、LSRC 算法，INLCS 算法的定位精度遠(yuǎn)優(yōu)于其他3種算法，而NLCS算法稍優(yōu)于LSRC和LSVM 算法，但是在節(jié)點(diǎn)比例較低時，NLCS算法也將遠(yuǎn)優(yōu)于LSRC 和LSVM 算法，這就說明NLCS算法的定位精度對信標(biāo)的節(jié)點(diǎn)個數(shù)的依賴沒有LSVM 和LSRC算法強(qiáng).而在信標(biāo)節(jié)點(diǎn)比例較高時，LSVM 和LSRC 算法的定位精度接近于NLCS算法，這是由于信標(biāo)節(jié)點(diǎn)的比例越高，LSVM 和LSRC的樣本數(shù)越多，其分類就越精確，從而使LSVM 和LSRC算法的精度得到了較大的提高.同時從圖4和圖2對比可以看出，空洞對4種算法均無較大的影響.

圖4 存在空洞時4種算法的定位性能對比Fig.4 Comparison of positioning performance of the four algorithms

假設(shè)在一個大小為100m×100m的區(qū)域內(nèi)，隨機(jī)地分布著500個傳感器節(jié)點(diǎn)，其中信標(biāo)節(jié)點(diǎn)的比例分別為5%、10%、15%、20%，節(jié)點(diǎn)通信半徑R＝6m，并存在1個位置信息錯誤的信標(biāo)節(jié)點(diǎn)時，4種算法定位性能對比如表2所示.由表2可以看出，在有1個錯誤的指標(biāo)節(jié)點(diǎn)存在時，INLCS和NLCS的定位性能比LSVM 和LSRC 更為優(yōu)勝，尤其是在信標(biāo)節(jié)點(diǎn)比例較低時.這是由于LSVM 和LSRC的分類模型的建立需要所有信標(biāo)節(jié)點(diǎn)的位置信息，一個錯誤的位置信息將使分類模型不準(zhǔn)確，從而影響了所有的普通節(jié)點(diǎn)的定位性能，而在INLCS和NLCS中計算相關(guān)度時，只利用了連通信息，即相關(guān)系數(shù)的計算式是正確的，這樣即使有錯誤的位置信息，也只是影響了靠近這個錯誤信標(biāo)節(jié)點(diǎn)的普通節(jié)點(diǎn)的定位精度.

表2 存在錯誤節(jié)點(diǎn)位置時4種算法的性能對比Table 2 Performance comparison of four algorithms when there is an error node position

5 結(jié) 論

文中提出了兩種新的定位算法——NLCS和INLCS.NLCS算法通過壓縮感知和質(zhì)心算法相結(jié)合來估計節(jié)點(diǎn)的位置，充分體現(xiàn)了節(jié)點(diǎn)間的空間相關(guān)性，因此NLCS算法不論在平均定位誤差還是定位標(biāo)準(zhǔn)差均能表現(xiàn)出良好的定位性能.同時通過實(shí)驗(yàn)可以發(fā)現(xiàn)NLCS 算法對信標(biāo)節(jié)點(diǎn)比例的依賴性不強(qiáng)，在較小的比例下就能取得較好的定位性能，換句話說，該算法可降低網(wǎng)絡(luò)的定位成本，能更為廣泛地適用于無線傳感器網(wǎng)絡(luò)定位.另外，NLCS算法在節(jié)點(diǎn)定位過程中，計算信標(biāo)節(jié)點(diǎn)對目標(biāo)節(jié)點(diǎn)的權(quán)值影響時，并不使用信標(biāo)節(jié)點(diǎn)的位置，而僅僅使用節(jié)點(diǎn)間的連通信息，這樣少數(shù)位置信息不準(zhǔn)確的信標(biāo)節(jié)點(diǎn)對大多數(shù)普通節(jié)點(diǎn)的定位并不會產(chǎn)生太大的影響，因此NLCS算法具有更好的魯棒性.同時，由于采樣字典由各個信標(biāo)節(jié)點(diǎn)自身的采樣原子組成并進(jìn)行了壓縮，這將降低網(wǎng)絡(luò)中各節(jié)點(diǎn)的能耗，進(jìn)而降低了整個網(wǎng)絡(luò)的通信消耗.而且不需要頭信標(biāo)節(jié)點(diǎn)去建立定位模型，因此能更好地均衡網(wǎng)絡(luò)的能耗.

同時，為了進(jìn)一步提升算法的定位性能，文中提出了利用偽跳數(shù)來改進(jìn)NLCS 算法，得到了INLCS算法.該算法在繼承NLCS算法優(yōu)點(diǎn)的情況下，利用偽跳數(shù)來更精確地描述各個節(jié)點(diǎn)之間的空間連通關(guān)系，從而使稀疏分解更加準(zhǔn)確，因此算法的性能得到了進(jìn)一步地提升.當(dāng)然，在實(shí)際應(yīng)用中還應(yīng)該進(jìn)一步考慮節(jié)點(diǎn)的能量，相比NLCS算法，INLCS算法要消耗更多的能量去獲取偽跳數(shù).因此，對定位性能與節(jié)點(diǎn)能量的均衡考慮將是我們進(jìn)一步的研究方向.

［1］孫穎.基于蟻群算法的能量均衡傳感網(wǎng)地理信息路由［J］.沈陽大學(xué)學(xué)報：自然科學(xué)版，2012，24（2）：57－61.（Sun Y.Geographic Routing of Energy Balance Sensor Network based on Ant Colony Algorithm［J］.Journal of Shenyang University：Natural Science，2012，24（2）：57－61.）

［2］Xu Y X，Gao X，Sun Z Y.WSN Node Localization Algorithm Design Based on RSSI Technology［C］∥International Conference on Intelligent Computation Technology and Automation（ICICTA ），2012.Zhangjiajie：［Unknown］556－559.

［3］Zhu S H，Ding Z G.Joint Synchronization and Localization Using TOAs：A Linearization Based WLS Solution［J］.IEEE Journal on Selected Areas in Communications，2010，28（7）：1017－1025.

［4］Shi H Y，Gao J Z.A New Hybrid Algorithm on TDOA Localization in Wireless Sensor Network［C］∥IEEE International Conference on Information and Automation（ICIA），2011.Shenzhen：［Unknown］，606－610.

［5］Chan F K，Wen C Y.Adaptive AOA／TOA Localization Using Fuzzy Particle Filter for Mobile WSNs［C］∥IEEE Vehicular Technology Conference，2011.Budapest：［Unknown］，1－5.

［6］Bulusu N，Heidemann J，Estrin D.GPS－less Low Cost Outdoor Localization for Very Small Devices［J］.IEEE Personal Communications Magazine，2000，7（5）：28－34.

［7］Wang J，Urriza P，Han Y X.Weighted Centroid Localization Algorithm：Theoretical Analysis and Distributed Implementation［J］.IEEE Transactions on Wireless Communications，2011，10（10）：3403－3413.

［8］楊新宇，孔慶茹，戴湘軍.一種改進(jìn)的加權(quán)質(zhì)心定位算法［J］.西安交通大學(xué)學(xué)報，2010，44（8）：1－4.（Yang X Y，Kong Q R，Dai X J.An Improved Weighted Centroid Location Algorithm ［J］.Journal of Xi’an Jiaotong University，2010，44（8）：1－4.）

［9］He T，Huang C，Blum B M.Range－free Localization Schemes for Large Scale Sensor Networks［C］∥Proceedings in MobiCom'03，San Diego，CA，USA.New York：ACM，81－95.

［10］Meertens L，F(xiàn)itzpatrick S.The Distributed Construction of a Global Coordinate System in a Network of Static Computational Nodes from Inter－Node Distances［R］.Palo Alto，CA，USA：Kestrel Institute，2004.

［11］Tran D A，Nguyen T.Localization in Wireless Sensor Networks Based on Support Vector Machines［J］.IEEE Transaction on Parallel and Distributed Systems，2008，19（7）：981－994.

［12］Qiu J F，Zhang H R.A Dictionary Classification Approach For Wireless Sensor Network Localization［C］∥Proceedings of IEEE Youth Conference Information，Computing and Telecommunication，2009.Beijing：［Unknown］，23－26.

［13］Yang Z，Liu Y H，Li X Y.Beyond Trilateration：On the Localizability of Wireless Ad－h(huán)oc Networks［J］.IEEE／ACM Transactions on Networking，2010，18（6）：1806－1814.

［14］金堅(jiān)，谷源濤，梅順良.壓縮采樣技術(shù)及其應(yīng)用［J］.電子與信息學(xué)報，2010，32（2）：470－475.（Jin J，Gu Y T，and Mei S L.An Introduction to Compressive Sampling and Its Applications［J］.Journal of Electronics ＆ Information Technology，2010，32（2）：470－475.）

［15］Canfes E，Plan Y.A Probabilistic and RIP Less Theory of Compressed Sensing ［J］.IEEE Transactions on Information Theory，2011，57（11）：7235－7254.

［16］Chen S B，Donoho D L，Saunders M A.Atomic Decomposition by Basis Pursuit［J］.SIAM Journal on Scientific Computing，1998，20（1）：33－61.

［17］Mallat S，Zhang Z.Matching Pursuit with Timefrequency Dictionaries［J］.IEEE Transactions on Signal Processing，1993，41（12）：3397－3415.