基于判別分類和回歸計算的傳感器節點定位

朱東進，王 婷

(1.江蘇電子信息職業學院 計算機與通信學院，江蘇 淮安 223003；2.大連海洋大學 應用技術學院，遼寧 大連 116300)

0 引言

在傳感器節點定位問題中，無線電或光信號強度的一個重要特性是信號衰減與距離的函數關系[1-4]，這種關系構成了大量定位算法的基礎。這些算法大致包含2個主要步驟：① 基于2個傳感器之間發送/接收信號的信號強度來估計2個傳感器之間的距離；② 通過三角測量或最小二乘誤差方法，基于距離估計值來獲得傳感器節點位置[5-8]。近年來，已經提出了各種方法通過無線傳感器網絡跟蹤區域中移動的一個或多個目標的算法[9-12]。

傳感器網絡可以看作是一種分布式模式識別系統。在模式識別方法中，不是將傳感器位置和傳感器讀數轉換為世界坐標系中的歐氏坐標，而是直接采用物理傳感器給出的非歐氏讀數。這些讀數可以看作是對核函數的近似，而且所得到的函數空間可以看作是一個用于預測各種外部感興趣量的協變量空間，可采用統計算法進行回歸和分類。文獻[13]提出了采用基于機器學習回歸模型直接尋找移動用戶在網絡中的地理坐標。文獻[14]提出了一種標簽多伯努利目標跟蹤與分類算法，把分類算法用于跟蹤移動車輛。文獻[15]在深入分析了RSS信號分布特性的基礎上，提出了基于RSS信號變化率的子區域劃分算法以及改進的AP近鄰傳播算法。文獻[16]利用核方法進行統計分類和回歸，從而為任意一對傳感器位置提供一種廣義的相似性度量。文獻[17] 針對現有室內定位算法存在低精度,低實用性和低傳感器利用率等問題,提出了一種基于多傳感器融合的粒子濾波室內定位技術。

本文提出了一種完全繞開測距步驟的方法。首先將粗粒度定位問題作為一種判別分類問題，采用統計機器學習工具如支持向量機(Support Vector Machine,SVM)來求解，然后通過第二次應用粗粒度定位技術來實現細粒度定位。具體來說，定位算法包括2個階段：首先，是一個訓練階段，選擇一個合適的判別函數來使用任意構造的邊界對位置進行分類。此階段在少量位置已知的傳感器(本文稱為基本傳感器)上在線或離線進行；其次，一旦訓練階段結束，其他位置未知的大量低功率傳感器可以通過回歸計算來局部確定自己的位置，從而實現傳感器網絡的節點定位。

1 核分類算法原理

對于核分類算法(如SVM)，其核心是核函數K(x,x′)的概念，它給出了X中2個數據點x和x′之間的相似性度量。從技術上講，要求K是一個對稱的半正定核。對于平移不變核，即K(x,x′)=h(x-x′)，對于某個函數h，如果h的傅里葉變換是非負的，則K是半正定核。對于這樣的函數，Mercer定理指出，一定存在一個特征空間{Φ(x)|x∈X}，在這個特征空間中，K為內積，即K(x,x′)=〈Φ(x),Φ(x′)〉。然后，SVM和基于核的相關算法在這個特征空間中選擇一個線性函數f(x)=〈w,Φ(x)〉，使得對于某個常數B有‖w‖≤B，并使得訓練誤差最小，即：

(1)

式中，φ表示一個為凸的合適的損失函數，且對于0-1損失，指示函數II(y≠sign(f(x)))是一個上界。指示函數II(·)定義為如果A為真，則II(A)=1，否則為0。如SVM算法基于損失φ(yf(x))=(1-yf(x))+(下角標“+”表示x+=max(x,0))。f(x)也可以直接用核函數K表示：

(2)

存在大量核函數滿足SVM算法所要求的半正定特性，如對于衰減參數σ和常數γ的高斯核：

K(x,x′)=exp[-(‖x-x′‖2/σ)]，

(3)

以及多項式核：

K(x,x′)=(γ+‖x-x′‖)-σ。

(4)

這2個核函數隨距離‖x-x′‖的增加而衰減，這是大多數基于信號強度模型共有的一個特性。特別地，無線電信號模型式(1)具有類似于多項式核的形式。文獻[9]表明采用聲能模型進行定位是合適的，該模型具有高斯核的形式。這就激發了直接采用信號強度來構造一個合適的半正定核函數，然后將它用于尋找一個判別函數，以達到定位的目的。由于僅對訓練和測試數據點的K(x,x′)的值感興趣，所以只需要確保Gram矩陣K=(K(xi,xj)ij)為半正定矩陣。

核方法的使用也使得合并多模態信號變得簡單明了。實際上，假設有D種類型的感知信號，每種都可以用于定義一個核函數Kd(x,x′)(d=1,2，…,D)，則Kd的任何二次組合都會得到一個新的半正定核：

(5)

根據經驗，通常選擇參數βd>0。

2 基于判別分類和回歸的定位算法

2.1 算法描述

本文研究的定位問題是基于少量傳感器(稱為基本傳感器)的已知位置來確定大量位置未知的傳感器的位置，所以算法不需要關于網絡拓撲的假設。假設有大量的傳感器密集部署在一個地理區域。算法的輸入是一組m個傳感器，令X1,X2,…,Xm表示m個傳感器的位置，即xi表示傳感器Xi在R2(二維)中的位置。假設前n個傳感器位置已知，即X1=x1,X2=x2,…,Xn=xn(n<

(6)

注意，f(xj)的值是已知的，因為核K(xi,xj)的值是已知的，盡管現在還不知道xj本身的位置。

下面來確定核矩陣K=(K(xi,xj))1≤i,j≤m。對于傳感器節點的定位問題，本文選擇：

(1) 簡單地定義K(xi,xj)=s(xi,xj)，將它稱之為第一層核。這隱含地假設矩陣S=(s(xi,xj))1≤i,j≤m是一個Gram矩陣(即對稱半正定)。這對于真實的信號矩陣是一個合理的近似；

(2) 定義K=STS，稱之為第二層線性核，K總是對稱半正定的。也可以說K是歐氏特征空間{Φ(x)}的內積，數據點xi的特征空間定義為：

Φ(xi)=(s(xi,x1),s(xi,x2),…,s(xi,xm))。

(7)

(3) 可以在歐氏特征空間{Φ(x)}上計算任何半正定核(如高斯核)。這將得到一個對稱半正定矩陣，稱之為第二層高斯核。

上述分類構建的特點是，訓練點對應于基本傳感器，因此在數量上是有限的，由于可以自由選擇區域C來學習，因此問題實際上變得容易求解。

其次，獲得定位的細粒度估計。用前面獲得的粗粒度解作為傳感器Xj(j=n+1,…,m)的定位算法的子過程，具體實現為：在傳感器網絡中生成許多重疊區域Cβ(β=1,2,…,U)，對于每個β，對類Cβ構建一個相應的分類問題，并預測是否Xj∈Cβ。因此，Xj必須位于包含它的區域的交叉部分，例如，可以將它的位置xj指定為這個交叉部分的中心。假定為區域Cβ選擇合適的粒度和形狀，如果大多數分類標簽是正確的，那么就能夠獲得對xj的良好估計。

2.2 算法實現細節和計算成本分析

在與每個粗粒度定位子過程相聯系的訓練階段，即關于固定區域Cβ的分類，基于前面描述的基本傳感器位置構建訓練數據集。在系統級，通過使全部基本傳感器將信號矩陣記錄s(xi,xj)及其已知位置發送給中心站來實現，它包含在中心站接收和存儲n2+n個數和中心站調用定位算法。需要求解以下最優化問題：

(8)

式中，f(x)=〈w,Φ(x)〉；φ(yf(x))=(1-yf(x))+；c是一個固定的參數。這是一個凸優化問題，其對偶形式如下[9]：

(9)

一旦訓練階段完成，每個基本傳感器需要存儲n個參數(α1,α2,…,αn)，以便對新的(位置未知的)傳感器進行分類。如果采用第一層核，新的傳感器Xj(j=n+1,…,m)接收來自ns個基傳感器i∈{1,2,…,n}的信號s(xi,xj)以及非零值αi，導致在時間和存儲上的成本為O(ns)；如果采用第二層線性核或第二層高斯核，則新的傳感器Xj從ns個基本傳感器i∈{1,2,…,n}接收有n個元素的信號向量(s(xi,x1),…,s(xi,xn))，導致在時間和存儲上的成本為O(nns)。然后，K(xi,xj)可以從接收到的信號s(xi,xj)中以O(1)、O(n)、O(n2)的時間分別計算出第一層核、第二層線性核和第二層高斯核，再通過一個簡單的計算(式(6))確定傳感器Xj是否位于區域C。顯然，定位步驟在局部(以分布式方式)進行，只需線性(對于第一層和第二層線性核)或二次(對于第二層高斯核)時間和存儲空間(以n表示)。由于定位是根據需要進行的，其時間和存儲成本不依賴于網絡中傳感器的總數目m。

(10)

2.3 算法定位誤差分析

假設大小為L×L的傳感器網絡被半徑為R的k2個圓盤均勻覆蓋，則傳感器網絡中任意給定點被大約π(Rk/L)2個圓盤覆蓋。每個圓盤用于確定區域分類問題的區域。為了獲得全部剩余傳感器Xj(j=n+1,…,m)的細粒度位置估計值，需要求解k2個區域分類問題。令eβ(β=1,2,…,k2)為訓練誤差，則：

(11)

由于區域的大小和形狀由算法來決定，例如，圓/橢圓形狀特別適合于高斯或多項式核。定義ε為全部訓練誤差的上限：

(12)

因此，定位誤差的預期上界為：

(13)

(14)

如果基本傳感器位置對于全部k2個圓盤在特征空間{Φ(x)}中是線性可分的，即ε=0，則定位誤差為O(L1/3R2/3n-1/6)。

上述分析保證了隨著傳感器的更加密集分布，定位性能得到改善。此外，分析還揭示了R和k對定位誤差的影響：定位誤差隨著R的減小而減小。由于隨著R的減小，k的最優值增大，導致計算量增加，因為有k2個圓盤需要分類。因此，R的改變意味著算法的定位精度和計算復雜度之間的權衡。這在后面的仿真中也得到了證實。

3 算法實驗結果

3.1 粗粒度定位

3.1.1 仿真設置

考慮一個大小為10×10平方單位的網絡，基本傳感器均勻分布在類似網格的結構中，總共有n2個這樣的傳感器，沿每個維度的基本傳感器數量為n。目標是識別一個由信號讀數s(xi,x)(i=1,2，…,n)給出的傳感器位置x是否位于待確定的區域C中。

首先定義信號模型，在該模型的基礎上產生傳感器接收到的信號值。假設位置x1的傳感器從位于x2的傳感器接收到一個遵循衰落信道模型的信號值：

s(x1,x2)=exp[-(‖x1-x2‖2+N(0,ε))/σ]，

(15)

式中，N(0,ε)表示獨立生成的具有標準偏差ε的正態隨機變量，這個信號模型是高斯核的隨機形式，而信號強度模型是多項式核的隨機形式：

s(x1,x2)=[‖x1-x2‖+N(0,ε)]-σ。

(16)

其次,確定待識別的區域C。C由全部位置x構成，滿足(x-v)TH1(x-v)≤R且(x-v)TH2(x-v)≤R，其中v=[5 5]T，H1=[2 -1;-1 1]，H2=[2 1;1 1]，這些特定的選擇意味著C是一個相當復雜的形狀，半徑R用來描述C的大小。對于每個仿真設置(n,R,σ,ε)，學習一個判別函數f，采用基本傳感器位置提供的訓練數據來描述區域C。一旦學習到f，就在網絡中均勻分布的傳感器位置上對分類進行測試。

3.1.2n對定位性能的影響

圖1所示為采用隨機高斯核模型得到的與網絡中部署的基本傳感器數量相關的測試誤差，橫軸表示沿網絡每個維度的傳感器數目，縱軸表示測試誤差，測試誤差定義為在網格中均勻分布的位置中，錯誤識別點數與位于C(R)內的點數之比。仿真中固定噪聲參數ε=0、影響核函數隨距離的增加而衰減的衰減參數σ=1和σ=7，改變n。圖1表明，隨著傳感器網絡的密集分布，定位誤差減小。如果需要識別一個特定的區域，只需在邊界周圍的區域放置基本傳感器，因為這些區域是支持向量的可能位置。

(a) 衰減參數σ=1

(b) 衰減參數σ=7圖1 采用隨機高斯核模型的仿真結果Fig.1 Simulation results using random Gaussian kernel model

3.1.3σ和ε對定位性能的影響

衰減參數σ用來描述信號強度關于傳感器距離的靈敏度。對于高斯核，小的σ值意味著對于遠距離的傳感器，信號衰減就快。信號噪聲參數ε描述信號強度的噪聲，它不是關于距離的確定性函數。圖2所示為ε和σ對定位性能的影響。

圖2 衰減參數σ和信號噪聲參數ε對定位性能的影響Fig.2 Effects of attenuation parameter σ and signal-noise parameter ε on positioning performance

在這組仿真中，將每個維度上的基本傳感器數目固定為10，C的半徑R=2，同時改變ε和σ。可以看到，隨著噪聲參數ε的增大，定位性能會下降，而對于更敏感的信號即σ較小時，退化越嚴重。此外，在固定ε時，當σ變小時，定位性能會提高。

3.2 細粒度定位

3.2.1 仿真設置

網絡設置與前面相同，只是n2個基本傳感器現在整個區域內隨機均勻分布，這意味著每個基本傳感器最初放置在L×L(L=10單位長)正方形的一個網格點上，然后受到高斯噪聲N(0,L/2n)的擾動。剩余的其他位置未知傳感器的位置將采用本文的算法來確定。同樣假設信號強度遵循高斯核模型的隨機形式，信號噪聲參數ε=0.2。

將第2節的算法應用于細粒度定位。算法包括對覆蓋整個網絡的多個區域重復應用粗粒度定位。選擇這些區域為半徑為R的圓盤，并在整個網絡中均勻分布。令k為沿每個維度的圓盤數量，因此總共有k2個圓盤需要識別。仿真研究R、k和基本傳感器數目n對定位性能的影響。

3.2.2n對定位性能的影響

圖3所示為得到的仿真結果。可以看到，隨著網絡中增加更多的基本傳感器，定位誤差均值減小，這與2.3的理論分析相吻合，說明算法特別適用于足夠密集的傳感器網絡。

圖3 基本傳感器數目對細粒度定位誤差均值的影響Fig.3 Effect of the number of basic sensors on the mean value of fine-grained positioning error

3.2.3R和k對定位性能的影響

圖4所示為得到的R和k對定位性能的影響。定位誤差均值是在隨機生成的20個傳感器網絡上仿真求平均得到。實驗中保持ε=0.2、σ=2和n=10不變，改變R和k。2.3節的分析表明，對于每個R值，存在一個最佳的k值隨著R的減小而增大。由于有k2個分類問題需要求解，計算成本一般會隨著R的減小而增加；另一方面，最佳定位誤差均值隨R的減小而減小，這在圖4中得到了證實。通過R和k的特性，可以清楚地看到計算成本和定位精度之間存在的權衡。

圖4 圓盤半徑R和圓盤數量k2對細粒度定位誤差均值的影響Fig.4 Effects of disk radius R and disk number k2 on the mean value of fine-grained positioning error

3.3 與采用基于測距的定位算法的比較

3.3.1 實驗設置

實驗中采用TE Connectivity 微型傳感器模塊構建一個真實的傳感器網絡來比較本文算法和文獻[8]的基于測距的定位算法的定位性能。具體是根據網絡中的一些基本傳感器接收到的光信號強度來估計光源的位置。硬件平臺由25個基本傳感器構成，放置在5×5的網格上，彼此相距10 cm。每個傳感器模塊由一個運行于3.5 MHz的Intel 8位處理器(具有128 Kb 的閃存和4 Kb 的RAM)、RFM TR1000 無線電、EEprom和一個傳感器板(包括光、溫度、麥克風傳感器和一個探測器)構成。放置在基本傳感器上的光源位置給出訓練數據，把需要估計的81個光源位置均勻分布在9×9的網格中，網格分布在整個網絡上。

3.3.2 實驗結果

文獻[8]的算法包括2個主要步驟：① 測距過程，建立基本傳感器接收到的信號強度與到光源的距離之間的映射；② 定位過程，采用最小二乘法得到距離估計值。本文算法采用3種核，第一種是采用信號矩陣的第一層對稱半正定近似，第二種和第三種是從信號矩陣構造的特征向量上定義的第二層線性核和高斯核。對于細粒度定位，將粗粒度定位重復應用于半徑R=20 cm的圓盤，覆蓋部分網絡區域。這些圓盤中心在2個維度上相距5 cm，沿每個維度有10個圓盤(即k=10)。

表1所示為對于全部81個未知位置，本文算法采用3種不同核所得到的定位誤差和文獻[8]的基于測距算法得到的定位誤差比較。可以看到，本文算法的定位誤差明顯低于文獻[8]的算法的定位誤差；在3種可供選擇的信號核中，從信號矩陣構造的特征向量上定義的第二層線性核和高斯核要比簡單的第一層核的定位效果要好。

表1 定位誤差比較Tab.1 Comparison of positioning errors

4 結束語

本文針對自組織無線傳感器網絡提出了一種基于判別分類和回歸計算的定位算法。算法避免了復雜的測距計算和傳感器網絡建模，測距計算需要精確的信號模型且很難校準。相反，本文算法采用信號強度或者直接為基于核的分類算法定義基函數，或者通過在信號強度測量值之上生成派生核間接地定義基函數；算法特別適合密集分布的傳感器網絡，在基本傳感器上執行預處理，而定位步驟可以以線性時間在每個位置未知的傳感器上進行。