王小樂 黃宏斌 鄧蘇 劉明星

(國防科學(xué)技術(shù)大學(xué) 信息系統(tǒng)工程重點實驗室，湖南 長沙 410073)

有限的節(jié)點能量和網(wǎng)絡(luò)帶寬制約著無線傳感器網(wǎng)絡(luò)(WSN)的性能.在觀測物理系統(tǒng)時，節(jié)點所獲的感知信息存在大量冗余，系統(tǒng)僅需選擇部分節(jié)點的感知數(shù)據(jù)就能估計出系統(tǒng)狀態(tài).因此，采取合理的節(jié)點選擇或調(diào)度策略，可以在保證估計精度的同時節(jié)約節(jié)點能量和網(wǎng)絡(luò)帶寬.文中研究了具有層次結(jié)構(gòu)的WSN 節(jié)點選擇問題(SSP:Sensor Selection Problem［1］or Sensor Scheduling Problem［2］).系統(tǒng)演化的不確定性和傳感器觀測過程的不確定性使SSP 的建模與求解變得非常復(fù)雜.SSP 研究如何從n 個傳感器中選擇m(1 ＜m ＜n)個傳感器，使得融合中心根據(jù)這m 個傳感器的觀測數(shù)據(jù)估計出的目標(biāo)系統(tǒng)狀態(tài)最精確，該問題具有NP 難的復(fù)雜度［3］.例如:從n 個傳感器中選擇m 個傳感器，總共有Cmn 種可能的組合，n 和m 較小時可以通過窮舉搜索獲得最優(yōu)解，但是當(dāng)兩者較大時求最優(yōu)解所花費的時間是目前的計算機無法承受的.例如，當(dāng)n =100，m =25 時大約有1023種可能的解［1］，解空間呈指數(shù)增長.文獻(xiàn)［4-5］采用貪婪策略提出了一種按順序選擇的算法即貪婪序列選擇算法(GSS).從理論上講GSS 并不能獲得最優(yōu)解，但文獻(xiàn)［4］認(rèn)為通過GSS 算法獲得的解為最優(yōu)解.

目前，求解SSP 的主要方法有:凸優(yōu)化方法［1，6］、分支定界方法［7］、信息熵［2，8］、動態(tài)規(guī)劃［9］、卡爾曼濾波［10］、粒子濾波［11］、隨機場估計［12］等方法.Siddharth 等［1］給出了一種基于凸優(yōu)化的啟發(fā)式傳感器選擇算法，并給出了選擇的最優(yōu)傳感器子集和最優(yōu)性能上界，該算法并不能保證總能夠獲得與最優(yōu)解差距較小的解，但是實驗結(jié)果說明在大多數(shù)情況下所獲得的解均與最優(yōu)解差距較小.Mo 等［6］假設(shè)傳感器的通訊開銷遠(yuǎn)大于感知開銷，提出了一種多階段傳感器選擇策略，即在多個時刻調(diào)度傳感器使其卡爾曼濾波器的誤差協(xié)方差矩陣最小，并采用松弛凸優(yōu)化的方法進(jìn)行求解.Maciej 等［13］研究了通過傳感器觀測數(shù)據(jù)估計分布式系統(tǒng)參數(shù)的問題，目標(biāo)是使用最少的傳感器節(jié)點獲得最精確的估計，他對問題建立多目標(biāo)優(yōu)化模型，并通過基于分支定界的序列二次規(guī)劃方法對模型進(jìn)行了求解.Zhen等［8］研究了信息物理融合系統(tǒng)(CPS)最優(yōu)觀測問題，并通過Fisher 信息熵的方法對問題進(jìn)行建模與求解.Andrey 等［14］考慮了物理過程的不確定性和傳感器噪聲干擾，采用博弈類型的Riccati 微分方程和動態(tài)規(guī)劃方程對問題進(jìn)行求解.文獻(xiàn)［5］提出了一種分布式在線貪婪算法，以效用函數(shù)滿足子模塊性的報酬遞減特性為前提，在模型未知的情況下，通過在線學(xué)習(xí)的方法優(yōu)化目標(biāo)函數(shù).文獻(xiàn)［4］研究了任意時間卡爾曼濾波器(AKF)中的度量選擇問題，為了獲得最佳狀態(tài)估計，選擇過程可以被建模為一個雙積分器，該文假設(shè)GSS 算法所提供的選擇為最優(yōu)選擇，但是該假設(shè)并未經(jīng)過理論證明，在文中僅通過一個特例說明在原文實驗中成立.傳感器選擇主要應(yīng)用于目標(biāo)跟蹤［15-17］、最優(yōu)覆蓋［18］、信息物理融合系統(tǒng)的最優(yōu)觀測［8，19］等問題中.傳感器選擇問題的最新研究包括可移動傳感器的路徑規(guī)劃［7，20］、帶天線的有向傳感器網(wǎng)絡(luò)中面向目標(biāo)跟蹤的傳感器調(diào)度［21］等.

文中研究了GSS 算法在求解SSP 上的有效性，通過反例證明該算法并不保證獲得最優(yōu)解.通過理論分析了初始解對GSS 算法性能的影響，提出了選擇更加有效的初始解的GSS 改進(jìn)方法，通過仿真實驗驗證GSS 改進(jìn)算法的有效性.并以目標(biāo)跟蹤問題為實例進(jìn)行仿真實驗.

1 模型與問題描述

1.1 觀測模型

將被觀測系統(tǒng)稱為目標(biāo)系統(tǒng)，假設(shè)傳感器網(wǎng)絡(luò)中包含n 個傳感器，用集合S ={s1，s2，…，sn}表示.假設(shè)單個傳感器的觀測模型描述為

yi=HiX+vi，i=1，2，…，n.

式中:yi為傳感器i(i=1，2，…n)，的測量值，可能是數(shù)值，也可能是列向量;vi∈Rl(i =1，2，…n)，為第i傳感器的高斯白噪聲干擾，其均值為零，協(xié)方差矩陣為Σi，即vi～N(0，Σi);X 表示目標(biāo)系統(tǒng)的狀態(tài)，X∈Rd;l 為觀測向量的維度，Hi(i=1，2，…n)為l×d 維觀測矩陣.如果觀測模型是非線性模型，可以通過泰勒展開的方法將其近似為線性模型.

1.2 狀態(tài)估計與評價

狀態(tài)估計就是在目標(biāo)狀態(tài)X 未知的情況下，如何通過觀測數(shù)據(jù)Y=(y1，y2，…，yn)T和觀測矩陣Hi(i=1，2，…，n)構(gòu)造系統(tǒng)狀態(tài)X 的最優(yōu)估計函數(shù)(Y)(簡寫為).文中假設(shè)融合中心對系統(tǒng)狀態(tài)X并無先驗知識，采用最小二乘估計，即通過對殘差函數(shù)G 求導(dǎo)，令其導(dǎo)數(shù)矩陣為零，在解線性方程組便可獲得估計函數(shù)，過程如下:

估計誤差的協(xié)方差為

1.3 傳感器選擇問題

根據(jù)1.2 中分析，可將傳感器選擇問題描述為

由傳感器選擇問題的模型可知，進(jìn)行傳感器選擇的依據(jù)是每個傳感器的觀測矩陣和噪聲的協(xié)方差矩陣，根據(jù)不同的選擇計算出目標(biāo)函數(shù)J(z)，使其最大的選擇為最優(yōu)選擇.從問題P0可以看出，SSP 為一個組合優(yōu)化問題，除了窮舉搜索算法，通過其他優(yōu)化算法均不能保證獲得最優(yōu)解.因此，可通過啟發(fā)式方法尋求一種盡可能好的次優(yōu)解.

2 GSS 算法分析及改進(jìn)

2.1 GSS 算法基本思想

GSS 算法是所選傳感器個數(shù)逐次遞增的方法，每次迭代增選一個傳感器，使本次迭代增加的傳感器與已選傳感器構(gòu)成的子集的標(biāo)函數(shù)最大，通過依次迭代直到選夠m 個傳感器就可以獲得傳感器選擇的一個解.GSS 算法如下所示:

給定被選擇集合S ={s1，s2，…，sn}，初始選擇集S'0=，已知m.

文獻(xiàn)［4］提出了一個假設(shè)，認(rèn)為通過GSS 算法能夠獲得最優(yōu)解，但并沒有給出理論證明，該假設(shè)是否成立以及這種算法到底是否有效，現(xiàn)有文獻(xiàn)并未肯定或否定.文中將通過理論和實驗兩個方面說明GSS 算法并非保證能獲得最優(yōu)解，但是一種有效的傳感器選擇算法.

GSS 算法從選擇一個傳感器開始每次迭代增選一個傳感器直到選夠m 個傳感器，因此，從n 個傳感器中選擇m 個傳感器的時間復(fù)雜度為

由式(4)可知，GSS 為線性時間復(fù)雜度，它與傳感器總數(shù)n 呈線性關(guān)系.

2.2 GSS 最優(yōu)性分析

定義1(最優(yōu)k 子集):在傳感器選擇問題中，將選擇k 個傳感器的最優(yōu)選擇子集稱為最優(yōu)k 子集，其中n≥k≥1.

假設(shè)1 最優(yōu)k 子集一定包含最優(yōu)k-1 子集.

定理1 假設(shè)1 成立則GSS 算法為最優(yōu)選擇算法.

證明顯然當(dāng)?shù)谝徊竭x擇的是最優(yōu)的子集，后面每次增加的都能保證最優(yōu)，那么最終選擇也一定為最優(yōu).

一般情況下，傳感器觀測噪聲的統(tǒng)計特征相同，假設(shè)Σi=1 (i=1，2，…，n).

以式(5)為條件通過數(shù)學(xué)推導(dǎo)很難獲得式(6)，但是可以通過舉反例很容易證明假設(shè)1 不成立.假設(shè)d=2，l=1 時，找到如下一組傳感器觀測向量數(shù)據(jù)H，采用窮舉搜索其最優(yōu)選擇子集，獲得的選擇結(jié)果見表1，H 中第i(1≤i≤10)列表示傳感器i 的觀測矩陣Hi，

表1 觀測矩陣為H 的傳感器選擇結(jié)果Table 1 Sensor selection results of observation matrix H

從表1 中的選擇結(jié)果可以看出:最優(yōu)3 子集中不含9，最優(yōu)2 子集與最優(yōu)3 子集之間的關(guān)系違反了假設(shè)1，因此假設(shè)1 是不成立的.如果在最優(yōu)3 子集中選擇了傳感器4 和9，那么所獲得的3 子集就不是最優(yōu)3 子集1、3、4，從而可以看出GSS 算法并不保證所獲得的傳感器是最佳選擇.

2.3 GSS 算法改進(jìn)

GSS 算法的起點是從選擇1 個傳感器開始的，這對于目標(biāo)系統(tǒng)狀態(tài)是數(shù)值(d =1)的情況是成立的.但是，如果系統(tǒng)狀態(tài)是向量，并且其維度d≥l時，選擇1 個傳感器根本無法估計出系統(tǒng)的狀態(tài)，更談不上減小誤差了，此時目標(biāo)函數(shù)J 為負(fù)無窮大，那么就無法比較選擇哪個傳感器更好，因此導(dǎo)致GSS算法的起點等同于隨機選擇.

南方丘陵區(qū)旱地水稻種植自然水資源微循環(huán)灌溉系統(tǒng)試驗研究…………………………………………………… 汪躍宏(17.57)

定理2 當(dāng)傳感器觀測值為數(shù)值(即l=1)時，對于任意一個傳感器選擇子集S'，當(dāng)|S'| ＜d 時，對于任何感知矩陣Hi(i=1，2，…，n)都有

證明 定理2 可以理解為當(dāng)變量個數(shù)大于方程個數(shù)時，方程有無窮多解.

對于觀測為向量的情況(即l ＞1)時，可以將每個傳感器認(rèn)為是由l 個子傳感器構(gòu)成，其中每個子傳感器只有1 個觀測值.在進(jìn)行傳感器選擇時，增加約束條件:這些子傳感器要么同時被選擇，要么都不選.此時，容易獲得推論1.

給定被選擇集合S ={s1，s2，…，sn}，初始選擇集S'0=，已知m.

此處k 較小，一般時間復(fù)雜度約為O(nk)，一般情況下k≤4.

3 仿真結(jié)果分析

3.1 GSS 改進(jìn)算法的有效性實驗

前文中雖然通過反例證明了GSS 算法并不保證獲得最優(yōu)選擇，但在實際中仍是一種高效的算法.假設(shè)觀測值是數(shù)值，目標(biāo)系統(tǒng)狀態(tài)向量為2 維向量.

(1)隨機產(chǎn)生觀測向量，對n = {5，6，7，8，9，10}，m={3，4，…，n-1}通過matlab 進(jìn)行交叉仿真測試.此處之所以如此設(shè)置，是因為測試中需要用窮舉搜索計算最優(yōu)選擇以便對比，如果參數(shù)n 較大會導(dǎo)致仿真時間過長.進(jìn)行每組參數(shù)設(shè)置，進(jìn)行1 000次蒙特卡洛仿真，根據(jù)定理1 只要違反假設(shè)1 就不能用GSS 獲得最優(yōu)解，否則就一定能獲得最優(yōu)解.因此，計算違反假設(shè)1 的次數(shù)，實驗結(jié)果如圖1所示.

圖1 GSS 改進(jìn)算法有效性測試Fig.1 Validity test of improved GSS algorithm

從圖1 可以看出，隨著選擇個數(shù)的增加，違反次數(shù)遞減，隨著傳感器總數(shù)的增加違反次數(shù)增大，但是1000 次實驗中最多違反次數(shù)為80 次，也就是有920次都符合假設(shè)1，這說明GSS 改進(jìn)算法在大多數(shù)情況下都能獲得最優(yōu)選擇.

(2)如果違反假設(shè)，GSS 改進(jìn)算法所獲得的傳感器選的目標(biāo)函數(shù)值與最優(yōu)選擇的目標(biāo)函數(shù)值之間的差反應(yīng)了GSS 算法所獲近似解的近似程度.假設(shè)在n = {9，10，11，12，13，14，15}的情況下分別對m={3，4，5，6，7，8}幾組數(shù)據(jù)各進(jìn)行1 000 次測試，計算目標(biāo)函數(shù)J 與最優(yōu)選擇目標(biāo)函數(shù)的誤差百分比，結(jié)果如圖2 所示.目標(biāo)函數(shù)之差的百分比Q 計算由式(7)得到:

式中:J'i表示第i 次蒙特卡洛仿真GSS 改進(jìn)算法所獲得的目標(biāo)函數(shù)，表示第i 次蒙特卡洛仿真的最優(yōu)目標(biāo)函數(shù).

圖2 GSS 改進(jìn)算法最優(yōu)性測試結(jié)果Fig.2 Optimal test results of improved GSS algorithm

從圖2 可以看出，GSS 改進(jìn)算法與最優(yōu)算法的目標(biāo)函數(shù)之差的百分比小于0.35%，而且隨著選擇數(shù)目的增加GSS 獲得的解更接近于最優(yōu)解，當(dāng)選擇數(shù)大于5 時誤差小于0.05%，可見GSS 改進(jìn)算法非常近似于最優(yōu)解.從圖2 中也可以看出傳感器總數(shù)變化對GSS 改進(jìn)算法的最優(yōu)性影響并不大.

3.2 GSS 與其改進(jìn)算法的對比

傳感器選擇常用于目標(biāo)跟蹤問題中.在本實驗中，假設(shè)平面上隨機均勻部署了多個傳感器節(jié)點.目標(biāo)是勻速直線運動(CV 模型)，其系統(tǒng)可以描述為Xk+1=FXk+wk.其中:Xk=(px，vx，py，vy)T，p、v 分別為目標(biāo)的位置和速度;wk為隨機干擾;F 為目標(biāo)系統(tǒng)狀態(tài)轉(zhuǎn)移矩陣，在CV 模型中，

式中:ΔT 表示離散化運動模型后的時間片長度;wk為環(huán)境噪聲干擾，為高斯白噪聲，其均值為零，協(xié)方差矩陣為R.

該實驗采用的傳感器模型為DoA 模型，DoA 模型的傳感器觀測量是目標(biāo)到傳感器的方位角，如式(8)所示:

設(shè)置傳感器總數(shù)n 為50，每個時刻選擇6 個傳感器，目標(biāo)從(0，0)點開始以速度(10 m/s，12 m/s)勻速運動，傳感器抽樣頻率為1 s，系統(tǒng)仿真為50 s，對GSS 算法、GSS 改進(jìn)算法和距離最近優(yōu)先選擇算法這3 種算法進(jìn)行傳感器選擇實驗，將選擇的目標(biāo)函數(shù)、位置估計誤差的均方根(RMSE)進(jìn)行對比，如圖3 所示.圖中的最小參考誤差是指不進(jìn)行選擇而將所有傳感器都激活得到的估計誤差，這是系統(tǒng)能達(dá)到的最小誤差.

圖3 目標(biāo)跟蹤誤差對比Fig.3 Comparison of target tracking error

從圖3 中誤差對比可以看出，總體誤差基本在1 m 左右，相對目標(biāo)運動速度根據(jù)所選擇的傳感器估計出的目標(biāo)位置比較精確，改進(jìn)GSS 算法比原始算法精度要高.圖3 中兩邊的誤差較大，原因是:在目標(biāo)跟蹤問題中，傳感器部署在平面區(qū)域上，而目標(biāo)軌跡的前端和后端由于傳感器部署密度相對較小且并沒有環(huán)繞目標(biāo)，因此造成這種情況的出現(xiàn).這也恰好說明了案例的合理性.

根據(jù)文獻(xiàn)［13］可知，觀測模型越靈敏所提供的信息量越大，因此，基于距離的傳感器選擇算法也是有效的，但是SSP 不僅僅看單個傳感器靈敏性，還考慮所選傳感器之間的組合效應(yīng)，基于距離的方法在這方面沒有考慮，因此較文中所研究的兩種方法稍差.

對所選傳感器個數(shù)m 對估計精度的影響進(jìn)行了實驗分析，設(shè)置傳感器總數(shù)n =100，所選傳感器個數(shù)m 從2 增加到22，分別進(jìn)行100 次仿真，計算估計誤差的平均值，結(jié)果如圖4 所示.

圖4 選擇個數(shù)與估計精度的關(guān)系Fig.4 Relationship between selection number and evaluation precision

由圖4 可以看出，當(dāng)傳感器較少時，增加傳感器個數(shù)對降低誤差的貢獻(xiàn)非常大，這也就是SSP 問題的子模塊性［22］.從圖中還可以看出，存在一個較好的傳感器數(shù)?=6，當(dāng)選擇傳感器數(shù)大于? 時，再增加傳感器數(shù)對估計誤差減少的影響并不明顯，稱之為Carathéodory 界限［6］，該界限的存在恰好說明了進(jìn)行傳感器選擇的意義.

4 結(jié)語

SSP 是具有NP 難復(fù)雜度的多維組合優(yōu)化問題，通過分步?jīng)Q策進(jìn)行選擇的GSS 算法是求解SSP 的有效方法.文中對GSS 算法進(jìn)行分析研究，通過反例證明了GSS 算法不保證得到最優(yōu)解.GSS 算法的第一步選擇影響著算法的最優(yōu)性，通過分析筆者認(rèn)為如果第一步能夠采用窮舉搜索獲得最優(yōu)的初始傳感器選擇，就能提高算法的最優(yōu)性.在此基礎(chǔ)上提出了一種GSS 的改進(jìn)算法，GSS 改進(jìn)算法仍為多項式時間復(fù)雜度.GSS 改進(jìn)算法在大多數(shù)情況下能夠獲得最優(yōu)解;即便不能獲得最優(yōu)解，所獲得的次優(yōu)解也非常接近于最優(yōu)解;這證明了GSS 改進(jìn)算法的有效性.最后將文中算法應(yīng)用于目標(biāo)跟蹤應(yīng)用實例，實驗表明，GSS 改進(jìn)算法較原算法獲得的選擇子集估計精度更高.

［1］Siddharth Joshi，Stephen Boyd.Sensor selection via convex optimization［J］.IEEE Transactions on Signal Processing，2009，57(2):451-462.

［2］Miao Lifeng，Stefanos Michael，Narayan Kovvali，et al.Multi-source neural activity estimation and sensor scheduling:algorithms and hardware implementation［J］.Journal of Signal Processing Systems，2013，70(2):145-162.

［3］Yoo Tae-Sic，St phane Lafortune.NP-Completeness of sensor selection problems arising in partially observed discrete-event systems［J］.IEEE Transactions on Automatic Control，2002，47(9):1495-1499.

［4］Nima Moshtagh，Chen Lingji，Raman Mehra.Optimal measurement selection for any-time Kalman filtering with processing constraints［C］∥John Ballieul，Gao Lei.Proceedings of the Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference.Shanghai:IEEE，2009:5074-5081.

［5］Manohar Shamaiah，Siddhartha Banerjee，Haris Vikalo.Greedy Sensor selection under channel uncertainty［J］.IEEE Wireless Communications Letters，2012，1(4):376-379.

［6］Mo Yilin，Ambrosino Roberto，Sinopoli Bruno.A convex optimization approach of multi-step sensor selection under correlated noise ［C］∥Vincent Conitzer.Proceedings of Forty-Seventh Annual Allerton Conference Allerton House.Champaign:IEEE，2009:187-193.

［7］Christophe Tricaud.Optimal sensing and actuation policies for networked mobile agents in a class of cyber-physical systems［D］.Logan:ECE Department，Utah State University，2010:45-52.

［8］Zhen S，Chen Y Q，Chellury R S，et al.Optimal observation for cyber-physical systems［M］.New York:Springer，2009:14-25.

［9］Li Y，Krakow L W，Chong E K P，et al.Approximate sto-chastic dynamic programming for sensor scheduling to track multiple targets ［J］.Digital Signal Processing，2009，19(6):978-989.

［10］Xiao W D，Wu J K，Xie L H，et al.Sensor scheduling for target tracking in networks of active sensors［J］.Acta Automatica Sinica，2006，32(6):922-928.

［11］Muhammad Naeem，Udit Pareek，Daniel C Lee.Swarm intelligence for sensor selection problems ［J］.IEEE Sensors Journal，2012，12(8):2577-2584.

［12］Weng Y，Xie L H，Xiao W.Sensor selection for random field estimation in wireless sensor networks［J］.Journal of System Science and Complex，2012，25(1):46-59.

［13］Maciej Patan，Dariusz Uciński.Resource-aware sensor activity scheduling for parameter estimation of distributed systems［C］∥George A Bekey，George N Saridis.Proceedings of the 18th IFAC World Congress.Milano:International Federation of Automatic Control (IFAC)，2011:9984-9989.

［14］Andrey V Savkin，Robin J Evans，Efstratios Skafidas.The problem of optimal robust sensor scheduling ［J］.Systems ＆ Control Letters，2001，43(2):149-157.

［15］Zoghi M，Kahaei M H.Adaptive sensor selection in wireless sensor networks for target tracking［J］.IET Signal Process，2010，4(5):530-536.

［16］Tharmarasa R，Kirubarajan T，Sinha A，et al.Decentralized sensor selection for large-scale multisensor-multitarget tracking［J］.IEEE Transactions on Areospace and Electronic Systems，2011，47(2):1307-1324.

［17］Chen Y C，Wen C Y.Decentralized cooperative TOA/AOA target tracking for hierarchical wireless sensor networks［J］.Sensors，2012，12(5):15308-15337.

［18］Gil J M，Han Y H.A target coverage scheduling scheme based on genetic algorithms in directional sensor networks［J］.Sensors，2011，11(2):1888-1906.

［19］Zhen S，Chellury R S，Nazif Cihan Tas，et al.Feasibility analysis on optimal sensor selection in cyber-physical systems［C］∥Chiasson John，Karlene A Hoo.Proceedings of 2009 American Control Conference.Hyatt Regency Riverfront.St.Louis:AACC，2009:5368-5373.

［20］Xing G L，Wang J P，Yuan Z H，et al.Mobile scheduling for spatiotemporal detection in wireless sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2010，21(12):1851-1866.

［21］Cai Y L，Lou W，Li M L，et al.Target-oriented scheduling in directional sensor networks［C］∥Robert L Baldwin，Qiao Chunming.Proceedings of IEEE INFOCOM 2007.Anchorage:IEEE，2007:1550-1558.

［22］Andreas Krause.Optimizing sensing［D］.Pittsburgh:School of Computer Science，Carnegie Mellon University，2008:3-15.