傳感器選擇問題的GSS算法有效性分析與改進*

王小樂 黃宏斌 鄧蘇 劉明星

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

有限的節(jié)點能量和網(wǎng)絡帶寬制約著無線傳感器網(wǎng)絡(WSN)的性能.在觀測物理系統(tǒng)時，節(jié)點所獲的感知信息存在大量冗余，系統(tǒng)僅需選擇部分節(jié)點的感知數(shù)據(jù)就能估計出系統(tǒng)狀態(tài).因此，采取合理的節(jié)點選擇或調度策略，可以在保證估計精度的同時節(jié)約節(jié)點能量和網(wǎng)絡帶寬.文中研究了具有層次結構的WSN 節(jié)點選擇問題(SSP:Sensor Selection Problem［1］or Sensor Scheduling Problem［2］).系統(tǒng)演化的不確定性和傳感器觀測過程的不確定性使SSP 的建模與求解變得非常復雜.SSP 研究如何從n 個傳感器中選擇m(1 ＜m ＜n)個傳感器，使得融合中心根據(jù)這m 個傳感器的觀測數(shù)據(jù)估計出的目標系統(tǒng)狀態(tài)最精確，該問題具有NP 難的復雜度［3］.例如:從n 個傳感器中選擇m 個傳感器，總共有Cmn 種可能的組合，n 和m 較小時可以通過窮舉搜索獲得最優(yōu)解，但是當兩者較大時求最優(yōu)解所花費的時間是目前的計算機無法承受的.例如，當n =100，m =25 時大約有1023種可能的解［1］，解空間呈指數(shù)增長.文獻［4-5］采用貪婪策略提出了一種按順序選擇的算法即貪婪序列選擇算法(GSS).從理論上講GSS 并不能獲得最優(yōu)解，但文獻［4］認為通過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)解差距較小的解，但是實驗結果說明在大多數(shù)情況下所獲得的解均與最優(yōu)解差距較小.Mo 等［6］假設傳感器的通訊開銷遠大于感知開銷，提出了一種多階段傳感器選擇策略，即在多個時刻調度傳感器使其卡爾曼濾波器的誤差協(xié)方差矩陣最小，并采用松弛凸優(yōu)化的方法進行求解.Maciej 等［13］研究了通過傳感器觀測數(shù)據(jù)估計分布式系統(tǒng)參數(shù)的問題，目標是使用最少的傳感器節(jié)點獲得最精確的估計，他對問題建立多目標優(yōu)化模型，并通過基于分支定界的序列二次規(guī)劃方法對模型進行了求解.Zhen等［8］研究了信息物理融合系統(tǒng)(CPS)最優(yōu)觀測問題，并通過Fisher 信息熵的方法對問題進行建模與求解.Andrey 等［14］考慮了物理過程的不確定性和傳感器噪聲干擾，采用博弈類型的Riccati 微分方程和動態(tài)規(guī)劃方程對問題進行求解.文獻［5］提出了一種分布式在線貪婪算法，以效用函數(shù)滿足子模塊性的報酬遞減特性為前提，在模型未知的情況下，通過在線學習的方法優(yōu)化目標函數(shù).文獻［4］研究了任意時間卡爾曼濾波器(AKF)中的度量選擇問題，為了獲得最佳狀態(tài)估計，選擇過程可以被建模為一個雙積分器，該文假設GSS 算法所提供的選擇為最優(yōu)選擇，但是該假設并未經(jīng)過理論證明，在文中僅通過一個特例說明在原文實驗中成立.傳感器選擇主要應用于目標跟蹤［15-17］、最優(yōu)覆蓋［18］、信息物理融合系統(tǒng)的最優(yōu)觀測［8，19］等問題中.傳感器選擇問題的最新研究包括可移動傳感器的路徑規(guī)劃［7，20］、帶天線的有向傳感器網(wǎng)絡中面向目標跟蹤的傳感器調度［21］等.

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

1 模型與問題描述

1.1 觀測模型

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

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 表示目標系統(tǒng)的狀態(tài)，X∈Rd;l 為觀測向量的維度，Hi(i=1，2，…n)為l×d 維觀測矩陣.如果觀測模型是非線性模型，可以通過泰勒展開的方法將其近似為線性模型.

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

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

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

1.3 傳感器選擇問題

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

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

2 GSS 算法分析及改進

2.1 GSS 算法基本思想

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 GSS 算法改進

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

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

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

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

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

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

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

3 仿真結果分析

3.1 GSS 改進算法的有效性實驗

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

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

圖1 GSS 改進算法有效性測試Fig.1 Validity test of improved GSS algorithm

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

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

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

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

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

3.2 GSS 與其改進算法的對比

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

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

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

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

圖3 目標跟蹤誤差對比Fig.3 Comparison of target tracking error

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

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

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

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

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

4 結語

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

［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.