王天荊，李秀琴，白光偉，沈航

（南京工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211816）

1 引言

近年來(lái)，基于無(wú)線傳感器網(wǎng)絡(luò)（WSN, wireless sensor network）的多目標(biāo)定位技術(shù)已被廣泛應(yīng)用于機(jī)器人導(dǎo)航、地理路由、公共安全、環(huán)境監(jiān)測(cè)、車輛跟蹤等多個(gè)領(lǐng)域[1-5]，其中，高精度、高效率的定位算法一直是研究熱點(diǎn)之一。傳統(tǒng)的多目標(biāo)定位算法可分為基于測(cè)距和基于非測(cè)距兩類，前者需要節(jié)點(diǎn)有測(cè)距功能，主要有基于到達(dá)時(shí)間[6]、基于到達(dá)時(shí)間差[7]等定位算法；后者通過(guò)網(wǎng)絡(luò)的連通性實(shí)現(xiàn)多目標(biāo)定位，主要有加權(quán)質(zhì)心定位算法[8]、修正權(quán)值網(wǎng)格質(zhì)心定位算法[9]等。上述算法雖簡(jiǎn)單易行，但需要額外的輔助設(shè)備，且定位精度易受到復(fù)雜環(huán)境下無(wú)線電波波動(dòng)的干擾。為了不增加硬件設(shè)施成本，基于接收信號(hào)強(qiáng)度(RSS, received signal strength)的多目標(biāo)定位技術(shù)根據(jù)傳感器節(jié)點(diǎn)可以獨(dú)立測(cè)量接收信號(hào)強(qiáng)度的特性，通過(guò)檢測(cè)監(jiān)測(cè)區(qū)域內(nèi)RSS來(lái)確定目標(biāo)位置。文獻(xiàn)[10]在離線階段使用核函數(shù)特征提取方法獲得 RSS 信號(hào)特征，構(gòu)成位置指紋空間；在線定位階段采集在線位置指紋數(shù)據(jù)，利用改進(jìn)的加權(quán)k近鄰算法匹配位置指紋空間中的數(shù)據(jù)，估計(jì)待測(cè)目標(biāo)位置。但是，基于位置指紋的定位技術(shù)需要對(duì)大量的數(shù)據(jù)進(jìn)行測(cè)量、處理和存儲(chǔ)，然而傳感器節(jié)點(diǎn)的能量、內(nèi)存和通信能力均受限。不同于RSS定位技術(shù)，文獻(xiàn)[11]提出的語(yǔ)義目標(biāo)定位算法通過(guò)節(jié)點(diǎn)間大量的信息交互來(lái)探知監(jiān)測(cè)環(huán)境，再利用環(huán)境信息估計(jì)目標(biāo)位置。這兩類方法中大量信息的傳遞消耗了有限的網(wǎng)絡(luò)資源，因此減少數(shù)據(jù)傳輸和資源消耗是多目標(biāo)定位亟待解決的問(wèn)題之一。

近年來(lái)，興起的壓縮感知（CS, compressive sensing）技術(shù)[12]為多目標(biāo)定位帶來(lái)了新的機(jī)遇。WSN中的多目標(biāo)定位問(wèn)題具有天然的稀疏性，因此可以利用CS理論大幅減少節(jié)點(diǎn)采樣的數(shù)據(jù)量，減少資源消耗。文獻(xiàn)[13]將WSN的監(jiān)測(cè)區(qū)域離散成若干個(gè)網(wǎng)格，并依據(jù)CS理論將多目標(biāo)定位問(wèn)題轉(zhuǎn)化成一個(gè)K-稀疏信號(hào)的重構(gòu)問(wèn)題，由sink節(jié)點(diǎn)利用l1最優(yōu)化從觀測(cè)向量中重構(gòu)出目標(biāo)位置。文獻(xiàn)[14]以目標(biāo)節(jié)點(diǎn)與錨節(jié)點(diǎn)連通度為觀測(cè)值，運(yùn)用最小化l1范數(shù)法，通過(guò)高計(jì)算量的梯度下降法求解目標(biāo)位置。針對(duì)l1最優(yōu)化重構(gòu)算法計(jì)算復(fù)雜度高的問(wèn)題，文獻(xiàn)[15]利用貪婪匹配追蹤（GMP, greedy matching pursuit）算法實(shí)現(xiàn)多目標(biāo)定位，但該算法的定位誤差需要進(jìn)一步改善。文獻(xiàn)[16]改進(jìn)了GMP算法，提出使用貪婪匹配殘差優(yōu)化算法重構(gòu)K-稀疏信號(hào)，提高了定位精度。基于貪婪法的定位算法雖計(jì)算復(fù)雜度低，但需要信號(hào)的稀疏度作為先驗(yàn)條件，即需要預(yù)知目標(biāo)個(gè)數(shù)。然而，實(shí)際應(yīng)用中節(jié)點(diǎn)不僅無(wú)法獲知目標(biāo)個(gè)數(shù)，而且無(wú)法確定滿足CS重構(gòu)條件所需的采樣數(shù)據(jù)量。因此，如何確定最優(yōu)觀測(cè)次數(shù)以克服因采樣數(shù)據(jù)量未知而導(dǎo)致的不充分采樣或過(guò)度采樣問(wèn)題，是多目標(biāo)定位的挑戰(zhàn)之一。

通常，基于CS的定位方法用固定網(wǎng)格劃分監(jiān)測(cè)區(qū)域[14-17]。為了保證辨識(shí)出每個(gè)目標(biāo)的位置，只能將網(wǎng)格劃分得十分細(xì)小，這大大增加了最優(yōu)化模型的規(guī)模及重構(gòu)算法的計(jì)算復(fù)雜度，從而存在加大定位誤差的風(fēng)險(xiǎn)。為了解決此問(wèn)題，文獻(xiàn)[17]提出了一種基于稀疏貝葉斯學(xué)習(xí)的網(wǎng)格自適應(yīng)多源定位算法，該算法設(shè)計(jì)的自適應(yīng)網(wǎng)格能使定位誤差低于固定網(wǎng)格劃分下定位誤差的理論下界。文獻(xiàn)[18]提出了一種兩階段的目標(biāo)定位算法：在粗定位階段利用l1最優(yōu)化重構(gòu)出目標(biāo)的初始候選網(wǎng)格；在細(xì)定位階段依次四分每個(gè)初始候選網(wǎng)格，在越來(lái)越小的子網(wǎng)格內(nèi)確定目標(biāo)的精確位置。上述定位算法雖解決了在大范圍內(nèi)以高計(jì)算代價(jià)估計(jì)目標(biāo)位置的問(wèn)題，但在細(xì)定位時(shí)依然要求所有節(jié)點(diǎn)傳輸感知數(shù)據(jù)至sink，這種集中式的定位方法易使節(jié)點(diǎn)因通信量大而過(guò)早失效，從而導(dǎo)致網(wǎng)絡(luò)拓?fù)涞牟环€(wěn)定性。根據(jù)目標(biāo)在監(jiān)測(cè)區(qū)域內(nèi)的稀疏性，如何建立分布式的多目標(biāo)定位方法是熱點(diǎn)問(wèn)題之一。

針對(duì)以上問(wèn)題，本文提出了一種基于自適應(yīng)網(wǎng)格的多目標(biāo)定位算法，該算法分為2個(gè)階段：在大尺度網(wǎng)格定位階段，采用序貫壓縮感知（SCS,sequential compressed sensing）原理選擇最優(yōu)觀測(cè)次數(shù)，通過(guò)lp最優(yōu)化重構(gòu)出目標(biāo)所在的初始網(wǎng)格位置；在小尺度網(wǎng)格定位階段，根據(jù)CS重構(gòu)要求自適應(yīng)劃分目標(biāo)所在的初始網(wǎng)格，再次采用SCS原理選擇最優(yōu)觀測(cè)次數(shù)，通過(guò)lp最優(yōu)化確定目標(biāo)在初始網(wǎng)格中的精確位置。本文主要貢獻(xiàn)如下。

1) 基于大尺度網(wǎng)格的定位方法在監(jiān)測(cè)區(qū)域內(nèi)區(qū)分目標(biāo)存在和不存在的子區(qū)域；基于小尺度網(wǎng)格的定位方法在目標(biāo)存在的子區(qū)域估計(jì)目標(biāo)的位置，使目標(biāo)定位更有針對(duì)性和高效性。

2) 利用 SCS數(shù)據(jù)采集方法和lp最優(yōu)化稀疏重構(gòu)方法共同減少節(jié)點(diǎn)的觀測(cè)數(shù)據(jù)量，從而大大降低網(wǎng)絡(luò)資源開銷。

3) 實(shí)驗(yàn)仿真結(jié)果表明，與傳統(tǒng)的基于CS的多目標(biāo)定位算法相比，在保證定位精度的同時(shí)，本文算法所需的觀測(cè)次數(shù)大大減少，定位的時(shí)間開銷顯著降低。

2 相關(guān)背景及準(zhǔn)備工作

2.1 壓縮感知

CS技術(shù)可用遠(yuǎn)低于奈奎斯特采樣率(Nyquist sampling frequency)的速率對(duì)K-稀疏信號(hào)進(jìn)行采樣，并利用如式(1)所示的l0最優(yōu)化問(wèn)題重構(gòu)出K-稀疏信號(hào)*

x。

其中，觀測(cè)矩陣P滿足有限等距性質(zhì)（RIP, restricted isometry property）[19]。正交匹配追蹤算法（OMP, orthogonal matching pursuit）[20]、分段正交匹配追蹤算法（StOMP, stagewise orthogonal matching pursuit）[21]等貪婪算法都可求解式(1)問(wèn)題，但是它們均需要信號(hào)稀疏度作為先驗(yàn)條件，且重構(gòu)誤差較大。于是，文獻(xiàn)[22]將l0最優(yōu)化問(wèn)題松弛為l1最優(yōu)化問(wèn)題，如式(2)所示。

式(2)所示的問(wèn)題可由梯度投影法（GPM, gradient projection method）、基追蹤算法（BP, basis pursuit）[23]、子空間追蹤算法（SP, subspace pursuit）[24]、迭代收縮閾值法（ISTA, iterative shrinkage-thresholding algorithm）等求解，但易于收斂到次優(yōu)稀疏解，且計(jì)算復(fù)雜度高。

2.2 CS定位問(wèn)題描述

假設(shè)在WSN監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)部署了M個(gè)位置已知的傳感器節(jié)點(diǎn)和K個(gè)位置未知的目標(biāo)，則基于CS的多目標(biāo)定位系統(tǒng)將此區(qū)域離散為N(N=n×n)個(gè)網(wǎng)格，并設(shè)每個(gè)目標(biāo)只出現(xiàn)在某個(gè)網(wǎng)格的中心位置，如圖1所示。

不妨定義K個(gè)目標(biāo)的位置向量為x=(x1, … ,xN)，其中，若第j個(gè)網(wǎng)格存在目標(biāo)，則xj=1，否則xj= 0 。根據(jù)強(qiáng)度-距離損耗模型[25]，第i個(gè)節(jié)點(diǎn)在理想情況下接收到第j個(gè)網(wǎng)格中目標(biāo)發(fā)出的RSS值為其中，pt表示在參考距離d0處的接收信號(hào)強(qiáng)度，dij為第i個(gè)節(jié)點(diǎn)與第j個(gè)目標(biāo)之間的歐式距離，路徑衰減指數(shù)η一般為 2～5。監(jiān)測(cè)區(qū)域內(nèi)M個(gè)節(jié)點(diǎn)采用觀測(cè)矩陣獲得觀測(cè)向量y=Px，并將之傳輸給sink；接收到y(tǒng)后，sink可以由觀測(cè)信息重構(gòu)出K-稀疏向量x*來(lái)估計(jì)目標(biāo)的位置，因?yàn)閤*中非零元素的位置對(duì)應(yīng)著K個(gè)目標(biāo)在N個(gè)網(wǎng)格中的位置。

圖1 基于CS的多目標(biāo)定位系統(tǒng)模型

傳統(tǒng)的基于CS的定位方法主要利用l0最優(yōu)化或l1最優(yōu)化來(lái)重構(gòu)目標(biāo)位置，很少考慮利用lp(0 ＜p＜ 1 )最優(yōu)化[26]完成定位任務(wù)；而lp范數(shù)對(duì)向量稀疏性的度量?jī)?yōu)于l0范數(shù)和l1范數(shù)，因此本文通過(guò)求解如式(4)所示的lp(0 ＜p＜ 1 )最優(yōu)化問(wèn)題實(shí)現(xiàn)多目標(biāo)定位。

充分的觀測(cè)數(shù)據(jù)量是求解問(wèn)題式(4)的前提條件，然而在實(shí)際場(chǎng)景下，定位系統(tǒng)無(wú)法預(yù)知目標(biāo)個(gè)數(shù)，即無(wú)法獲知向量x的稀疏度，因此無(wú)法確定重構(gòu)所需的觀測(cè)次數(shù)。若觀測(cè)次數(shù)過(guò)多，對(duì)提高重構(gòu)精度的貢獻(xiàn)有限，但增加了采樣成本；若觀測(cè)次數(shù)過(guò)少，則無(wú)法精確重構(gòu)出*x。

2.3 基于SCS的最優(yōu)采樣

SCS技術(shù)克服了因觀測(cè)數(shù)據(jù)量未知而導(dǎo)致的不充分或過(guò)度采樣問(wèn)題，其基本思想是在初始m個(gè)觀測(cè)值上疊加T個(gè)觀測(cè)值，使以的概率得到的重構(gòu)誤差滿足式(5)。

于是，當(dāng)重構(gòu)誤差的估計(jì)值Est(m,T)小于門限值τ時(shí)，停止接受新的觀測(cè)值；否則，以T為步長(zhǎng)，序貫增加觀測(cè)次數(shù)直至Est(m,T)滿足門限要求，獲得最優(yōu)觀測(cè)向量m+STy。

3 基于自適應(yīng)網(wǎng)格的多目標(biāo)定位算法

由上述討論可知監(jiān)測(cè)區(qū)域的網(wǎng)格劃分影響著式(4)所示問(wèn)題的求解。若網(wǎng)格劃分的尺度過(guò)小，則使式(4)所示問(wèn)題中欠定線性方程組的規(guī)模急劇增加，從而大大增加重構(gòu)算法的計(jì)算量，延長(zhǎng)定位時(shí)間；若網(wǎng)格劃分的尺度過(guò)大，則一個(gè)網(wǎng)格中可能存在多個(gè)目標(biāo)，定位時(shí)容易出現(xiàn)目標(biāo)丟失。由此，設(shè)置合理的網(wǎng)格尺度可提高定位的準(zhǔn)確性、及時(shí)性及降低系統(tǒng)的計(jì)算復(fù)雜度。通常，網(wǎng)格尺度的劃分依賴于目標(biāo)的先驗(yàn)信息，但WSN無(wú)法獲知這些信息。不過(guò)某些實(shí)際場(chǎng)景下多個(gè)目標(biāo)會(huì)分別聚集在小區(qū)域內(nèi)，如圖2所示。于是，本文分別采用大尺度網(wǎng)格劃分和小尺度網(wǎng)格劃分這2個(gè)階段實(shí)施多目標(biāo)定位，具體過(guò)程如下。

圖2 實(shí)際的多目標(biāo)定位場(chǎng)景

3.1 大尺度網(wǎng)格定位

WSN啟動(dòng)多目標(biāo)定位任務(wù)時(shí)，為了減少感知開銷，首先用大尺度劃分監(jiān)測(cè)區(qū)域，以確定存在目標(biāo)的子區(qū)域，如圖3所示。假設(shè)面積為S=a0×a0的監(jiān)測(cè)區(qū)域被劃分為N0=n0×n0個(gè)初始網(wǎng)格, 第i(i∈{ 1,…,N0})個(gè)初始網(wǎng)格的狀態(tài)向量定義為其中為初始網(wǎng)格的中心位置，或分別表示該初始網(wǎng)格中存在或不存在目標(biāo)。根據(jù)SCS原理，在區(qū)域內(nèi)隨機(jī)選擇m0+T0個(gè)節(jié)點(diǎn)進(jìn)行目標(biāo)感知，且將觀測(cè)值傳送給sink；sink計(jì)算重構(gòu)誤差的估計(jì)值 E st(m0,T0)確定是否繼續(xù)接收新的觀測(cè)值，經(jīng)過(guò)S0-1次的序貫接收，最終獲得最優(yōu)觀測(cè)向量利用式(6)所示的l最優(yōu)p化重構(gòu)出稀疏向量

對(duì)預(yù)設(shè)的門限值γ，當(dāng)時(shí)，說(shuō)明第i個(gè)初始網(wǎng)格中可能存在著多個(gè)目標(biāo)，且元素的幅值是多個(gè)目標(biāo)位置信息的累加；反之，不存在目標(biāo)，此時(shí)只需簇頭周期性地監(jiān)測(cè)子區(qū)域，成員節(jié)點(diǎn)暫時(shí)休眠，以減少網(wǎng)絡(luò)資源開銷。

圖3 大尺度網(wǎng)格劃分下多目標(biāo)定位模型

下面，本文重點(diǎn)對(duì)存在目標(biāo)的K0個(gè)子區(qū)域進(jìn)行基于自適應(yīng)網(wǎng)格的目標(biāo)定位。

3.2 自適應(yīng)網(wǎng)格定位

為了在第i(i∈ {L1, … ,LK0})個(gè)初始網(wǎng)格中進(jìn)一步確定目標(biāo)的精確位置，需要自適應(yīng)調(diào)整尺度來(lái)重新劃分初始網(wǎng)格，其中，子列 {L1, …,LK0} ? {1,…,N0}是存在目標(biāo)的初始網(wǎng)格的序號(hào)。

因?yàn)榇司W(wǎng)格中目標(biāo)個(gè)數(shù)未知，第一步假設(shè)只存在一個(gè)目標(biāo)，記個(gè)數(shù)為由 CS原理可知，通常精確重構(gòu)出稀疏解所需的觀測(cè)次數(shù)應(yīng)至少滿足M=4K[27]，則劃分初始網(wǎng)格后的小尺度網(wǎng)格個(gè)數(shù)需滿足即（如圖 4(a)所示）。sink隨機(jī)激發(fā)初始網(wǎng)格中的個(gè)節(jié)點(diǎn)進(jìn)行聚類和感知，成員節(jié)點(diǎn)將觀測(cè)值發(fā)送給簇頭。如果簇頭由SCS計(jì)算的估計(jì)值 E st(mi,Ti1)＜τ，則增加新的觀測(cè)值。如果每次固定增加T個(gè)觀測(cè)值，則由SCS無(wú)法較快地確定最終的觀測(cè)次數(shù)。為了快速分析出所需增加的觀測(cè)值，不妨定義比值如式(7)所示。

ii例如，在圖4(a)中計(jì)算得到Δ(mi,Ti1) ＞ 0 ，為了提高定位效率，需將初始網(wǎng)格重新劃分成個(gè)小網(wǎng)格，且需滿足圖 4(b)顯示3× 3的網(wǎng)格被劃分為5× 5，而非4×4的網(wǎng)格。由CS重構(gòu)條件可知，使用3× 3的網(wǎng)格至多可識(shí)別出2個(gè)目標(biāo)，即3× 3 ＞ 8 = 4 × 2 ；而使用5×5的網(wǎng)格至多可識(shí)別出6個(gè)目標(biāo)，即5× 5 ＞ 2 4 = 4 × 6 。因CS中壓縮比不易過(guò)高，考慮5× 5 ＞ 1 6 = 4 × 4 。于是，簇頭新接收Ti2= 1 2個(gè)觀測(cè)值，總觀測(cè)次數(shù)為

圖4 第i個(gè)初始網(wǎng)格的自適應(yīng)劃分示意

第二步，簇頭計(jì)算重構(gòu)誤差的估計(jì)值Est(m,T1+T2)，若此估計(jì)值仍大于τ，則重新劃

iii分網(wǎng)格且接收Ti3個(gè)觀測(cè)值；反之，則停止接收新的觀測(cè)值。簇頭由式(8)所示的lp最優(yōu)化重構(gòu)出稀疏向量

傳統(tǒng)的 CS定位方法一般采用集中式處理方式，消耗了大量的信道資源和傳輸開銷。同時(shí)，節(jié)點(diǎn)實(shí)時(shí)感知不存在目標(biāo)的子區(qū)域會(huì)產(chǎn)生過(guò)多的感知開銷。本文設(shè)計(jì)的定位方法較好地解決了上述問(wèn)題，初始階段基于大尺度網(wǎng)格的集中式定位方法在監(jiān)測(cè)區(qū)域內(nèi)區(qū)分目標(biāo)存在和不存在的子區(qū)域，后續(xù)階段基于小尺度網(wǎng)格的分布式定位方法并行地對(duì)存在目標(biāo)的多個(gè)子區(qū)域進(jìn)行精細(xì)定位。這種全局與局部結(jié)合、集中式與分布式結(jié)合及粗定位與細(xì)定位結(jié)合的方式為高精度、高效率的多目標(biāo)定位提供了一種新的思路，更易應(yīng)用于現(xiàn)行的分層結(jié)構(gòu)的WSN，并推廣至不同場(chǎng)景下的多目標(biāo)定位問(wèn)題。

根據(jù)上述討論，本文提出的基于自適應(yīng)網(wǎng)格的多目標(biāo)定位算法的流程如圖5所示。

圖5 基于自適應(yīng)網(wǎng)格的多目標(biāo)定位算法流程

3.3 初始網(wǎng)格的合并與定位

初始階段，sink由重構(gòu)向量x0確定了每個(gè)初始網(wǎng)格的狀態(tài)向量并獲得了位置向量ID0= (L1, … ,LK0)，其中，所在的網(wǎng)格位置序號(hào)。如前文所述，監(jiān)測(cè)子區(qū)域內(nèi)聚集著多個(gè)目標(biāo)，所以不難發(fā)現(xiàn)ID0中目標(biāo)所在的初始網(wǎng)格常常相互鄰近。如果聯(lián)合這些相鄰網(wǎng)格一起進(jìn)行基于自適應(yīng)網(wǎng)格的細(xì)定位，相比于單個(gè)初始網(wǎng)格各自進(jìn)行定位可以大大減少感知、傳輸和計(jì)算開銷。

如圖6所示，大尺度網(wǎng)格定位將監(jiān)測(cè)區(qū)域劃分為N0= 5× 5 個(gè)初始網(wǎng)格，并確定了存在目標(biāo)的初始網(wǎng)格，其中存在3種初始網(wǎng)格相鄰情況。下面分別討論合并初始網(wǎng)格后的自適應(yīng)網(wǎng)格定位方法。

Case 1 3個(gè)初始網(wǎng)格相鄰。將圖6 (a)中c1區(qū)域擴(kuò)展為4個(gè)初始網(wǎng)格且假設(shè)目標(biāo)個(gè)數(shù)為首先，由SCS將子區(qū)域劃分為個(gè)小網(wǎng)格，并在子區(qū)域及周圍隨機(jī)選擇個(gè)節(jié)點(diǎn)進(jìn)行觀測(cè)，計(jì)算估計(jì)值及比值此時(shí)有需要接收較多的觀測(cè)值。于是將子區(qū)域重新劃分為個(gè)小網(wǎng)格，獲取新的次觀測(cè)。然后，簇頭重新計(jì)算估計(jì)值及比值此時(shí)有簇頭從觀測(cè)向量中由最優(yōu)化重構(gòu)出稀疏向量個(gè)非零系數(shù)所在的網(wǎng)格中心即為個(gè)目標(biāo)的估計(jì)位置，坐標(biāo)為其中

圖6 合并且自適應(yīng)劃分目標(biāo)所在的相鄰初始網(wǎng)格

Case 2 2個(gè)初始網(wǎng)格直接相鄰。將圖6(a)中c2區(qū)域擴(kuò)展為 2個(gè)初始網(wǎng)格且假設(shè)目標(biāo)個(gè)數(shù)為首先，由SCS將子區(qū)域內(nèi)每個(gè)初始網(wǎng)格劃分為3× 3個(gè)小網(wǎng)格，共個(gè)小網(wǎng)格，并在子區(qū)域及周圍隨機(jī)選擇m+T1=8個(gè)節(jié)點(diǎn)進(jìn)行觀測(cè)，計(jì)算估計(jì)c1c2值及 比值此 時(shí)有只需接收少量新的觀測(cè)值，取次觀測(cè)。然后，簇頭重新計(jì)算估計(jì)值及比值此時(shí)有不需要再接收新的觀測(cè)值。簇頭從觀測(cè)向量中由最優(yōu)化重構(gòu)出稀疏向量個(gè)非零系數(shù)所在的網(wǎng)格中心即為個(gè)目標(biāo)的估計(jì)位置，坐標(biāo)為

Case 3 2個(gè)初始網(wǎng)格對(duì)角相鄰。將圖6(a)中c3區(qū)域擴(kuò)展為 4個(gè)初始網(wǎng)格且假設(shè)目標(biāo)個(gè)數(shù)為首先，由SCS將子區(qū)域劃分為個(gè)小網(wǎng)格，并在子區(qū)域及周圍隨機(jī)選擇個(gè)節(jié)點(diǎn)進(jìn)行觀測(cè)，計(jì)算估計(jì)值和比值此時(shí)時(shí)，需要接收較多的觀測(cè)值，于是將子區(qū)域重新劃分成個(gè)小網(wǎng)格, 再接收次觀測(cè)。然后，簇頭計(jì)算估計(jì)值和比值此時(shí)有簇頭從觀測(cè)向量中由最優(yōu)化重構(gòu)出稀疏向量其中，個(gè)非零系數(shù)所在的網(wǎng)格中心即為個(gè)目標(biāo)的估計(jì)位置，坐標(biāo)記為

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

下面對(duì)本文提出的WSN中基于自適應(yīng)網(wǎng)格的多目標(biāo)定位算法進(jìn)行仿真實(shí)驗(yàn)，主要分為兩部分：首先，分別與基于CS的多目標(biāo)定位算法和基于兩階段的多目標(biāo)定位算法進(jìn)行對(duì)比，驗(yàn)證本文算法具有更優(yōu)的定位性能；然后，對(duì)比不合并和合并初始網(wǎng)格的定位性能，驗(yàn)證合并初始網(wǎng)格的高效性。

4.1 仿真場(chǎng)景

在Matlab中進(jìn)行仿真實(shí)驗(yàn)。假設(shè)在正方形監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)高密度部署大量的傳感器節(jié)點(diǎn)，K個(gè)待定位的目標(biāo)隨機(jī)分布在區(qū)域內(nèi)的任意位置。參照文獻(xiàn)[18]，仿真參數(shù)的設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

為了評(píng)估定位性能，定義多目標(biāo)定位誤差為

其中，tcen為大尺度網(wǎng)格劃分下的定位時(shí)間，tdis為小尺度網(wǎng)格劃分下的定位時(shí)間；若ti為自適應(yīng)劃分第i個(gè)初始網(wǎng)格的定位時(shí)間，則tdis=max{t1, … ,ti,…,tK0}。

4.2 基于自適應(yīng)網(wǎng)格的多目標(biāo)定位算法的性能分析

4.2.1 大尺度網(wǎng)格的定位性能分析

WSN啟動(dòng)多目標(biāo)定位后，大尺度網(wǎng)格的設(shè)置影響著后續(xù)自適應(yīng)網(wǎng)格的設(shè)置。下面實(shí)驗(yàn)分析不同的大尺度網(wǎng)格劃分對(duì)定位性能的影響。將K=7個(gè)目標(biāo)和M=50個(gè)節(jié)點(diǎn)隨機(jī)部署在不同面積的監(jiān)測(cè)區(qū)域內(nèi)，定義平均定位時(shí)間作為評(píng)估指標(biāo)，其中，Nt= 5 0表示蒙特卡洛實(shí)驗(yàn)的次數(shù)，TIi為第i次實(shí)驗(yàn)的多目標(biāo)定位時(shí)間。

針對(duì)不同的大網(wǎng)格尺度劃分，圖7顯示不同監(jiān)測(cè)區(qū)域面積下平均定位時(shí)間隨著網(wǎng)格尺度變小而減小，但當(dāng)初始網(wǎng)格數(shù)量達(dá)到一定規(guī)模時(shí)，平均定位時(shí)間又會(huì)增加。這是因?yàn)槌跏季W(wǎng)格尺度設(shè)置過(guò)大時(shí)，自適應(yīng)網(wǎng)格定位階段會(huì)進(jìn)行多次網(wǎng)格細(xì)劃分操作，增加了計(jì)算時(shí)間；而初始網(wǎng)格尺度設(shè)置過(guò)小，存在目標(biāo)的初始網(wǎng)格就過(guò)多，增加了自適應(yīng)網(wǎng)格定位的計(jì)算時(shí)間?？梢钥闯觯?種監(jiān)測(cè)區(qū)域面積對(duì)應(yīng)的最佳大網(wǎng)格劃分分別為8× 8、9×9、9×9、10× 10，則網(wǎng)格劃分尺度n0與監(jiān)測(cè)區(qū)域邊長(zhǎng)a0比值分別約為 16%、13%、10%、9%，因此可以按照8%～18%比例來(lái)確定大網(wǎng)格的尺度。

4.2.2 對(duì)比基于CS的多目標(biāo)定位算法

在上述實(shí)驗(yàn)的基礎(chǔ)上，本文分析了50 m×50 m的監(jiān)測(cè)區(qū)域內(nèi)不同CS定位算法的性能。傳統(tǒng)的基于CS的定位算法直接將監(jiān)測(cè)區(qū)域細(xì)劃分成20×20的網(wǎng)格，應(yīng)用BP算法、OMP算法或GMP算法對(duì)K個(gè)目標(biāo)進(jìn)行定位，而本文算法在8× 8的初始網(wǎng)格劃分下實(shí)施自適應(yīng)網(wǎng)格定位，估計(jì)K個(gè)目標(biāo)的精確位置。定義平均定位誤差來(lái)評(píng)估不同定位算法的定位性能。

圖7 不同監(jiān)測(cè)區(qū)域面積下平均定位時(shí)間與初始網(wǎng)格規(guī)模的關(guān)系

由圖8(a)可知，隨著目標(biāo)個(gè)數(shù)的增加，本文算法均獲得了最佳定位結(jié)果，其平均定位誤差遠(yuǎn)遠(yuǎn)小于BP算法、OMP算法和GMP算法。例如，當(dāng)K=8時(shí)，本文算法的定位精度比BP算法、OMP算法和GMP算法分別提高了85%、89.6%和83.6%。這不僅因?yàn)榛趌p最優(yōu)化的稀疏重構(gòu)精度優(yōu)于l0最優(yōu)化和l1最優(yōu)化，而且分為全局和局部2個(gè)階段定位目標(biāo)比直接全局定位目標(biāo)更精確、更符合實(shí)際場(chǎng)景。圖 8(b)顯示本文算法的平均定位時(shí)間少于 BP算法和GMP算法，雖高于OMP算法，但為了提高定位精度，可容忍增加37%的平均定位時(shí)間。圖8(c)顯示了感知節(jié)點(diǎn)個(gè)數(shù)隨著目標(biāo)個(gè)數(shù)變化的情況，與其他3種算法相比，本文算法可大大減少感知節(jié)點(diǎn)個(gè)數(shù)，即重構(gòu)所需的觀測(cè)次數(shù)。

圖9給出了K=7時(shí)4種算法的定位示意，可以看出，本文算法的定位準(zhǔn)確性最高。利用BP算法、OMP算法和GMP算法重構(gòu)稀疏解時(shí)，其非零元素的位置都出現(xiàn)了偏差，因而出現(xiàn)了漏檢目標(biāo)和虛假目標(biāo)的情況。

基于CS 的多目標(biāo)定位易受環(huán)境的影響，為驗(yàn)證本文算法的抗噪性能，將K=10個(gè)目標(biāo)和M=60個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在監(jiān)測(cè)區(qū)域內(nèi)。圖10(a)顯示隨著信噪比的增加，節(jié)點(diǎn)接收的目標(biāo)信號(hào)強(qiáng)度準(zhǔn)確性顯著提高，因此4種定位算法的平均定位誤差均呈下降趨勢(shì)，其中，本文算法的定位精度明顯優(yōu)于其他3種算法。當(dāng)SNR從-6 dB變化到24 dB時(shí)，本文算法的平均定位誤差分別比BP算法、OMP算法和GMP算法最多降低了77.0%、82.5%、65.0%；當(dāng)SNR大于20 dB時(shí)，本文算法的定位精度在0.5 m以內(nèi)，而此時(shí)其他3種算法的定位精度分別在2 m、3 m和1.8 m以內(nèi)。圖10(b)顯示隨著信噪比的增加，4種定位算法的平均定位時(shí)間均逐漸減少，本文算法的平均定位時(shí)間明顯小于BP算法和GMP算法，但大于OMP算法。為了提高定位精度，可以容忍一定程度上增加定位時(shí)間。因此，本文算法的抗噪性能優(yōu)于傳統(tǒng)的CS定位算法。

圖8 不同目標(biāo)個(gè)數(shù)下4種定位算法的定位性能比較

圖9 4種定位算法的多目標(biāo)定位示意

圖10 不同信噪比下4種定位算法的定位性能

隨著“萬(wàn)物相連”的物聯(lián)網(wǎng)的廣泛應(yīng)用，WSN作為其基礎(chǔ)設(shè)施，規(guī)模越來(lái)越大，因此傳統(tǒng)的多目標(biāo)定位算法不再適用于大規(guī)模的 WSN。當(dāng)監(jiān)測(cè)區(qū)域面積不斷增加時(shí)，傳統(tǒng)的基于CS的定位算法劃分出的網(wǎng)格數(shù)量急劇增加，使重構(gòu)算法的計(jì)算復(fù)雜度大大增加，從而影響了目標(biāo)定位精度。例如，在K= 1 5，M=90，SNR=20 dB情況下，分別將50m× 50m、80m× 80m、100m× 100m、120m× 120m的監(jiān)測(cè)區(qū)域劃分為20×20、25×25、30× 30、35× 35的網(wǎng)格。圖 11(a)顯示隨著監(jiān)測(cè)區(qū)域面積的增加，BP算法、OMP算法和GMP算法的平均定位誤差均有大幅增長(zhǎng)。然而，本文算法首先大尺度劃分監(jiān)測(cè)區(qū)域，避免了在大范圍內(nèi)以高計(jì)算代價(jià)重構(gòu)目標(biāo)位置，然后對(duì)存在目標(biāo)的小區(qū)域進(jìn)行自適應(yīng)網(wǎng)格定位，大幅提高了定位精度，減少了平均定位時(shí)間，如圖 11(b)所示。例如，監(jiān)測(cè)區(qū)域?yàn)?20 m× 120 m時(shí)，本文算法的平均定位誤差比 BP算法、OMP算法和GMP算法分別降低了77.2%、81.8%和 87.2%；相應(yīng)的平均定位時(shí)間分別減少了81.4%、56.2%和86.3%。

圖11 不同監(jiān)測(cè)區(qū)域面積下4種定位算法定位性能比較

4.2.3 對(duì)比基于兩階段的多目標(biāo)定位算法

為了提高定位精度，文獻(xiàn)[18]設(shè)計(jì)了基于兩階段的多目標(biāo)定位算法（下文中稱為對(duì)比算法），該算法按次對(duì)每個(gè)候選網(wǎng)格進(jìn)行多次四分操作來(lái)確定目標(biāo)位置，花費(fèi)較長(zhǎng)的定位時(shí)間。本文算法并行地對(duì)所有存在目標(biāo)的子區(qū)域進(jìn)行自適應(yīng)網(wǎng)格定位，大大減少了定位時(shí)間。下面的實(shí)驗(yàn)比較了在50 m×50 m的監(jiān)測(cè)區(qū)域內(nèi)不同信噪比下 2種分階段定位算法的性能。圖 12(a)顯示隨著信噪比的增加，2種定位算法的平均定位誤差均逐漸減小，然而在所有 SNR下本文算法的平均定位誤差均遠(yuǎn)遠(yuǎn)小于對(duì)比算法，約減少了72%～88%。相應(yīng)地，隨著信噪比的增加，圖12(b)中2種定位算法的平均定位時(shí)間均逐漸減少，但本文算法的平均定位時(shí)間比對(duì)比算法減少了約 83%～94%。當(dāng)K=8， S NR為- 6 ～ - 2 dB時(shí)，本文算法的平均定位誤差比對(duì)比算法降低了 62%～60%，而平均定位時(shí)間比對(duì)比算法減少了90%～88%。因此在低SNR下本文算法仍然可以及時(shí)、精準(zhǔn)地確定出多個(gè)目標(biāo)的位置，為復(fù)雜無(wú)線環(huán)境下的多目標(biāo)定位提供有力的保障。

目標(biāo)個(gè)數(shù)的增加（即位置向量x的稀疏度降低）直接影響著從觀測(cè)向量中重構(gòu)目標(biāo)位置的性能，所以本文分析信噪比為5 dB和-5 dB下目標(biāo)個(gè)數(shù)對(duì)定位結(jié)果的影響。在監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)部署M= 9 0個(gè)傳感器，圖 13(a)顯示隨著目標(biāo)個(gè)數(shù)的增加，2種分階段定位算法的平均定位誤差均逐漸增大，但本文算法的平均定位誤差遠(yuǎn)遠(yuǎn)小于對(duì)比算法，最多減少了 73%。同時(shí)，圖 13(b)顯示其平均定位時(shí)間也遠(yuǎn)遠(yuǎn)小于對(duì)比算法，最多減少了93%。這是因?yàn)閷?duì)比算法按次對(duì)每個(gè)候選網(wǎng)格進(jìn)行多次四分定位，隨著目標(biāo)個(gè)數(shù)的增加，定位時(shí)間必然會(huì)大大增加。然而，本文算法對(duì)存在目標(biāo)的初始網(wǎng)格并行地進(jìn)行自適應(yīng)網(wǎng)格定位，可大大減少定位時(shí)間?？梢?jiàn)在目標(biāo)個(gè)數(shù)較多時(shí)，本文算法具有更好的準(zhǔn)確性、及時(shí)性。

圖12 不同信噪比下2種分階段多目標(biāo)定位算法的定位性能

4.3 自適應(yīng)合并初始網(wǎng)格的性能分析

對(duì)每個(gè)初始網(wǎng)格進(jìn)行自適應(yīng)定位，必然使WSN出現(xiàn)較多的分簇，引起過(guò)多的資源開銷。如果將相鄰的初始網(wǎng)格合并，可以更高效地實(shí)現(xiàn)子區(qū)域的目標(biāo)定位。為此，將K=10個(gè)目標(biāo)隨機(jī)分布在圖14中40 m×40 m的監(jiān)測(cè)區(qū)域內(nèi)，并將之先劃分成6×6的網(wǎng)格。sink根據(jù)SCS收集m+3T= 3 0(m=6,T=8)個(gè)觀測(cè)值，利用lp最優(yōu)化確定出存在目標(biāo)的初始網(wǎng)格，并依據(jù)稀疏解中非零元素的位置合并初始網(wǎng)格，如圖14中黑色線框所示。自適應(yīng)網(wǎng)格定位階段，表2顯示合并初始網(wǎng)格的定位方法比不合并初始網(wǎng)格的定位方法在定位時(shí)間上具有明顯優(yōu)勢(shì)，而且當(dāng)合并的初始網(wǎng)格個(gè)數(shù)越多，定位時(shí)間的減少越明顯。例如，c1區(qū)域合并 3個(gè)相鄰的初始網(wǎng)格后，其定位時(shí)間比不合并初始網(wǎng)格減少了71.5%。

圖13 不同目標(biāo)個(gè)數(shù)下2種分階段多目標(biāo)定位算法的定位性能比較

圖14 自適應(yīng)合并目標(biāo)所在初始網(wǎng)格的實(shí)景

表2 2種小尺度網(wǎng)格定位方法的定位時(shí)間比較

5 結(jié)束語(yǔ)

本文提出了一種WSN中基于自適應(yīng)網(wǎng)格的多目標(biāo)定位算法，將大尺度網(wǎng)格確定目標(biāo)大致位置與小尺度網(wǎng)格確定目標(biāo)精確位置相結(jié)合。與傳統(tǒng)的基于CS的定位算法相比，本文算法減少了網(wǎng)絡(luò)的采樣開銷，且具有良好的抗噪性能。仿真實(shí)驗(yàn)表明本文算法在保證定位精度的同時(shí)有效地降低了定位時(shí)間開銷。目前，尚沒(méi)有在OPNET或OMNET++等仿真平臺(tái)上進(jìn)行實(shí)驗(yàn)，因此對(duì)于本文算法在實(shí)際傳感器網(wǎng)絡(luò)中的驗(yàn)證有待下一步解決。