趙春暉，許云龍，黃 輝

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

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

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

無線傳感器網(wǎng)絡(luò)定位方法分為基于測距的（range－based）和無需測距的（range－free）定位兩類.典型的測距定位算法主要有：基于測距的定位通過測量距離進行定位，如接收信號強度（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］等.顯然，基于測距的算法需要與信標節(jié)點直接通信，明顯不滿足條件③，而無需測距的算法也大部分不符合上述3個條件.已知滿足以上條件的比較有代表性的算法有：Diffusion、LSVM 和LSRC算法，文獻［11］已經(jīng)證明了LSVM 算法比Diffusion算法性能優(yōu)越很多，因此本文將以LSVM 算法和LSRC 算法作為對比算法.

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

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

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

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

1 CS 和Centroid

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

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

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

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

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

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

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

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

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

2.2 定位算法原理

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

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

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

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

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

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

2.3 協(xié) 議

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

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

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

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

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

3 改進的NLCS（INLCS）

3.1 改進原理

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

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

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

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

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

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

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

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

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

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

3.3 算法的能量分析與對比

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

4 實驗結(jié)果與分析

假設(shè)有1 000個傳感器節(jié)點隨機分布于大小為100m×100m的區(qū)域內(nèi)，其中信標節(jié)點的比例分別為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算法有更小的定位誤差標準差.這些是由于NLCS算法估計節(jié)點的位置利用的是質(zhì)心算法，能夠充分地體現(xiàn)出目標節(jié)點與信標節(jié)點的空間相關(guān)性，因此NLCS算法的定位性能較LSVM 和LSRC算法更優(yōu)異.此外，由于INLCS 算法利用偽跳數(shù)改進了連通信息，使各個節(jié)點到信標節(jié)點的連通信息更加準確，因此目標節(jié)點將能更準確地被信標節(jié)點所描述，從而進一步提升了算法的性能.

為了更準確地比較INLCS、NLCS、LSRC 和LSVM 算法的性能，檢驗各個算法的適應(yīng)性，下面將考慮在較小的網(wǎng)絡(luò)中的定位性能.假設(shè)有250個傳感器節(jié)點隨機分布于大小為50m×50m的區(qū)域內(nèi)，其中信標節(jié)點的比例分別為5%，10%，15%，20%，節(jié)點通信半徑R＝6m.表1是INLCS、NLCS、LSRC與LSVM 4種算法的定位性能對比，從表1中可以看出：在4種信標節(jié)點的比例下，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

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

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

圖4為在1 000個傳感器節(jié)點隨機分布于大小為100m×100m的區(qū)域內(nèi)，其中信標節(jié)點的比例分別為5%、10%、15%、20%，節(jié)點通信半徑R＝6m，并存在如圖3a、圖3b所示的網(wǎng)絡(luò)空洞下的定位性能對比圖.從圖4中可以看出：在4種信標節(jié)點的比例下，INLCS、NLCS算法的定位性能都優(yōu)于LSVM、LSRC 算法，INLCS 算法的定位精度遠優(yōu)于其他3種算法，而NLCS算法稍優(yōu)于LSRC和LSVM 算法，但是在節(jié)點比例較低時，NLCS算法也將遠優(yōu)于LSRC 和LSVM 算法，這就說明NLCS算法的定位精度對信標的節(jié)點個數(shù)的依賴沒有LSVM 和LSRC算法強.而在信標節(jié)點比例較高時，LSVM 和LSRC 算法的定位精度接近于NLCS算法，這是由于信標節(jié)點的比例越高，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)，隨機地分布著500個傳感器節(jié)點，其中信標節(jié)點的比例分別為5%、10%、15%、20%，節(jié)點通信半徑R＝6m，并存在1個位置信息錯誤的信標節(jié)點時，4種算法定位性能對比如表2所示.由表2可以看出，在有1個錯誤的指標節(jié)點存在時，INLCS和NLCS的定位性能比LSVM 和LSRC 更為優(yōu)勝，尤其是在信標節(jié)點比例較低時.這是由于LSVM 和LSRC的分類模型的建立需要所有信標節(jié)點的位置信息，一個錯誤的位置信息將使分類模型不準確，從而影響了所有的普通節(jié)點的定位性能，而在INLCS和NLCS中計算相關(guān)度時，只利用了連通信息，即相關(guān)系數(shù)的計算式是正確的，這樣即使有錯誤的位置信息，也只是影響了靠近這個錯誤信標節(jié)點的普通節(jié)點的定位精度.

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

5 結(jié) 論

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

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

［1］孫穎.基于蟻群算法的能量均衡傳感網(wǎng)地理信息路由［J］.沈陽大學學報：自然科學版，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］楊新宇，孔慶茹，戴湘軍.一種改進的加權(quán)質(zhì)心定位算法［J］.西安交通大學學報，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］金堅，谷源濤，梅順良.壓縮采樣技術(shù)及其應(yīng)用［J］.電子與信息學報，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.