基于自組織特征映射的移動傳感器網(wǎng)絡(luò)控制

趙曉萌, 王朝立

(上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

基于自組織特征映射的移動傳感器網(wǎng)絡(luò)控制

趙曉萌, 王朝立

(上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

針對概率型感知模型的移動傳感器網(wǎng)絡(luò)中覆蓋區(qū)域?yàn)闀r變的情況,提出了一種基于自組織特征映射的實(shí)時覆蓋算法.其中自組織特征映射依據(jù)實(shí)時采樣的樣本點(diǎn)來對覆蓋目標(biāo)區(qū)域進(jìn)行拓?fù)溆成?并依據(jù)多智能體系統(tǒng)中的一致性控制算法使移動傳感器載體形成預(yù)定編隊(duì),完成覆蓋任務(wù).最后通過實(shí)驗(yàn)仿真驗(yàn)證了該算法的優(yōu)良性能.

移動傳感器網(wǎng)絡(luò);自組織特征映射;編隊(duì)控制;時變覆蓋區(qū)域

移動傳感器網(wǎng)絡(luò)(mobile sensing networks)是由多個移動傳感器載體構(gòu)成的整個網(wǎng)絡(luò)拓?fù)?載體之間可有部分的信息交換,即系統(tǒng)具有通訊拓?fù)浣Y(jié)構(gòu).這樣通過傳感器獲得的數(shù)據(jù)以及載體之間的信息交互達(dá)成最大化利用傳感器檢測到的信息來完成預(yù)定任務(wù).傳感器覆蓋問題則體現(xiàn)了整個網(wǎng)絡(luò)監(jiān)測水準(zhǔn)[1],是在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目、網(wǎng)絡(luò)計(jì)算能力等約束下使得無線傳感器網(wǎng)絡(luò)的資源得到合理分配.對于傳統(tǒng)的靜態(tài)覆蓋問題,文獻(xiàn)[2-7]通過提出不同的目標(biāo)函數(shù)和約束條件來建立優(yōu)化問題,應(yīng)用粒子群算法、遺傳算法、模擬退火算法、蟻群算法及魚群算法等啟發(fā)式隨機(jī)搜索算法來解決這一問題.但對于動態(tài)覆蓋問題,啟發(fā)式搜索算法由于算法的復(fù)雜度過高使得網(wǎng)絡(luò)不能滿足很好的實(shí)時性要求.文獻(xiàn)[8]研究了移動傳感器網(wǎng)絡(luò)的覆蓋問題,提出了質(zhì)心泰森多邊形分區(qū)(centroidal voronoi partitions)的方法,并從理論上證明了算法的可行性.文獻(xiàn)[9-10]通過采用不同的優(yōu)化目標(biāo)來改進(jìn)算法,分別是異同的感知半徑與能量消耗優(yōu)化兩個方面.文獻(xiàn)[11-12]則從群集控制的角度來研究覆蓋算法.文獻(xiàn)[11]引入了信息函數(shù)來測量傳感器的傳感質(zhì)量,通過群集算法使得整個網(wǎng)絡(luò)保持連通且使傳感器覆蓋范圍最大.文獻(xiàn)[12]則采用連續(xù)的一致性卡爾曼濾波器(Kalman-consensus filtering)使得移動傳感器網(wǎng)絡(luò)能夠估計(jì)出帶覆蓋區(qū)域位置信息.文獻(xiàn)[13]建立了一種基于梯度法且保持網(wǎng)絡(luò)連通的分布式覆蓋算法,并研究了覆蓋區(qū)域中存在多邊形障礙的情況.

本文假設(shè)所有傳感器檢測范圍相等,故單個傳感器覆蓋區(qū)域是一半徑為傳感器最大檢測距離的圓形區(qū)域,這樣對于多傳感器覆蓋問題,即是在使得指定區(qū)域覆蓋面積最大且重復(fù)覆蓋區(qū)域面積最小的目標(biāo)下,尋找最優(yōu)的傳感器節(jié)點(diǎn)部署位置.但事實(shí)上,對于傳感器檢測半徑全部相等的情況,區(qū)域覆蓋問題中節(jié)點(diǎn)部署最優(yōu)解的部署形態(tài)基本是類似的,即形如正三角形這種子結(jié)構(gòu).這種子結(jié)構(gòu)的特點(diǎn)是可以無盲區(qū)地進(jìn)行拼接,通常覆蓋區(qū)域遠(yuǎn)遠(yuǎn)大于單個傳感器覆蓋范圍,所以,對于已經(jīng)指定的區(qū)域,按子結(jié)構(gòu)依次拼接直到覆蓋指定區(qū)域即可,這樣盲區(qū)只會在覆蓋邊界產(chǎn)生.同時,對于移動傳感器網(wǎng)絡(luò),指定覆蓋區(qū)域可以是移動的,甚至是隨著時間變化的,采用傳統(tǒng)的啟發(fā)式搜索算法由于算法的復(fù)雜度過高使得網(wǎng)絡(luò)不能滿足很好的實(shí)時性要求,因此,有必要尋找一種快速的適用于動態(tài)覆蓋區(qū)域的自適應(yīng)算法來實(shí)時地求得傳感器部署位置.

1 系統(tǒng)模型

1.1 探測區(qū)域模型

考慮待測監(jiān)測區(qū)域?yàn)閚維空間內(nèi)一個閉合連通域Ω?瓗n,在實(shí)際應(yīng)用中,n取2或3對應(yīng)平面及立體覆蓋區(qū)域.為了能夠方便算法映射出傳感器部署期望位置,將Ω離散化,在區(qū)域內(nèi)按離散步長τ平行于坐標(biāo)軸方向依次從區(qū)域Ω內(nèi)提取覆蓋熱點(diǎn),考慮到覆蓋區(qū)域可能是平移移動的,則從熱點(diǎn)中隨機(jī)選擇一個熱點(diǎn)為目標(biāo)熱點(diǎn)位置矢量c0∈瓗n,作為綁定在該區(qū)域上的移動坐標(biāo)系原點(diǎn).設(shè)一個連通域集合珚Ω={Ω1,Ω2,…,ΩM},并假設(shè)覆蓋區(qū)域具有切換時刻t1,t2,…,tM.

1.2 載體模型

有N個標(biāo)號為1～N自治移動載體,每個移動載體搭載1個傳感器,并假設(shè)載體質(zhì)心位置與傳感器質(zhì)心位置重合.載體模型為=ui,i=1,2,…, N,xi∈瓗n,xi為載體i的位置矢量,ui∈瓗n,ui為載體i的控制矢量.假設(shè)其中僅有部分載體能夠獲得待監(jiān)測覆蓋區(qū)域中的目標(biāo)熱點(diǎn)的相對自身位置,并假設(shè)此目標(biāo)熱點(diǎn)具有模型=f0,f0∈瓗n,f0為目標(biāo)熱點(diǎn)虛擬速度矢量控制項(xiàng).其余熱點(diǎn)在目標(biāo)熱點(diǎn)移動時與目標(biāo)熱點(diǎn)距離始終是有界的,即存在以有限半徑為R的球域,使得下式成立:

ci(t)-c0(t)≤R,i=1,2,…,p-1,?t＞0(1)式中,ci(t)為覆蓋區(qū)域內(nèi)熱點(diǎn)位置矢量,p為區(qū)域內(nèi)熱點(diǎn)總數(shù).

1.3 感知模型

傳統(tǒng)的感知模型分為兩種:第一種為確定性感知模型,即認(rèn)為傳感器感知半徑為硬性邊界,小于等于該感知半徑的熱點(diǎn)即被認(rèn)為以概率1檢測到,而大于該感知半徑的熱點(diǎn)認(rèn)為檢測不到;第二種為概率性感知模型,即不再是以概率1檢測到熱點(diǎn),而是服從一定的概率分布.

本文采用第2種傳感器感知模型,假設(shè)所有傳感器感知模型一致,并定義為高斯概率型,具體形式為

假設(shè)單個熱點(diǎn)被每個傳感器感知是相互獨(dú)立的,則單個節(jié)點(diǎn)被整個傳感器網(wǎng)絡(luò)感知的概率為

當(dāng)σ→0時,概率性感知模型將轉(zhuǎn)變?yōu)榇_定性感知模型,即可認(rèn)為確定性模型為概率性模型的一種形式.

2 自組織特征映射

自組織特征映射(self-organizing feature map,簡稱SOFM)是一種無監(jiān)督競爭學(xué)習(xí)神經(jīng)網(wǎng)絡(luò),可以通過神經(jīng)元之間的競爭實(shí)現(xiàn)大腦神經(jīng)系統(tǒng)中的近興奮遠(yuǎn)抑制功能,并具有將高維輸入向量映射到低維向量的能力.與普通競爭神經(jīng)網(wǎng)絡(luò)不同,SOFM具備模擬輸入向量拓?fù)浣Y(jié)構(gòu)的特性,即輸入拓?fù)溆成涞墓δ?因此,本文使用SOFM對覆蓋區(qū)域進(jìn)行拓?fù)溆成湟源_定傳感器空間部署位置.

依據(jù)覆蓋區(qū)域的維數(shù)n,制定相應(yīng)的神經(jīng)元權(quán)重向量wi∈瓗n,i=1,2,…,N,即神經(jīng)元數(shù)目與傳感器數(shù)目一致.則覆蓋區(qū)域內(nèi)熱點(diǎn)作為SOFM的輸入樣本,逐次輸入到SOFM中,神經(jīng)元之間展開競爭,競爭的目的是尋找與當(dāng)前輸入cj最為匹配的神經(jīng)元權(quán)值wi,輸入與權(quán)值間的匹配規(guī)則采用歐氏距離度量,即尋找滿足下式的神經(jīng)元:

按照此鄰域函數(shù),設(shè)計(jì)神經(jīng)元l的權(quán)系數(shù)更新策略為

3 算法設(shè)計(jì)

借助于SOFM的實(shí)時映射能力,現(xiàn)介紹設(shè)計(jì)步驟.

步驟1 獲取初始覆蓋區(qū)域Ω?瓗n,將區(qū)域離散化,取得熱點(diǎn)集C=[c|c∈Ω],并任意選取一個熱點(diǎn)作為目標(biāo)熱點(diǎn)c0.

步驟2 如果t=tk,tk為覆蓋區(qū)域拓?fù)淝袚Q時刻,則重新獲取覆蓋區(qū)域熱點(diǎn)集C并隨機(jī)選擇目標(biāo)熱點(diǎn)c0;否則,轉(zhuǎn)步驟3.

步驟3 將熱點(diǎn)集C以目標(biāo)熱點(diǎn)c0作坐標(biāo)平移變換,將變換后的熱點(diǎn)集合作為SOFM的輸入訓(xùn)練SOFM,具體流程如下:

式中,m為反饋系數(shù),m＞0;Ni(t)表示t時刻載體i的鄰接載體集合;hi表示載體i是否能夠獲取目標(biāo)熱點(diǎn)的相對位置信息,即hi＞0,表示能夠獲取目標(biāo)熱點(diǎn)信息.

步驟5 對各個傳感器載體施加控制,轉(zhuǎn)步驟2.

從上述算法可以看出,整個動態(tài)覆蓋控制策略大致分為兩步:第1步由SOFM確定出傳感器部署位置;第2步由控制器來使傳感器載體跟蹤到預(yù)定部署位置.

式(8)中出現(xiàn)w·i并不是說在覆蓋區(qū)域未切換時SOFM權(quán)值還在更新,而是為了描述在切換拓?fù)鋾r刻間的熱點(diǎn)的連續(xù)線性變換(如熱點(diǎn)的旋轉(zhuǎn)、放縮及翻轉(zhuǎn)等).事實(shí)上,這里的wi即表示了SOFM中神經(jīng)元的權(quán)值向量,又表示了由SOFM映射出的預(yù)定部署位置向量.

上述算法沒有確定出傳感器數(shù)目N,在實(shí)際應(yīng)用中,考慮到覆蓋區(qū)域的時變特性,N的數(shù)目是無法確定的.但若已知連通域集合珚Ω內(nèi)各個覆蓋區(qū)域的面積,則可依據(jù)下式給出確定的傳感器數(shù)目[14]:

a.按照正三角形的拼接子結(jié)構(gòu)來構(gòu)成競爭層神經(jīng)元權(quán)值拓?fù)涑踔?迭代步數(shù)k′=0;

b.從離散化的覆蓋區(qū)域中隨機(jī)選擇熱點(diǎn)cj作為SOFM輸入;

c.根據(jù)式(5)確定獲勝神經(jīng)元i,并依據(jù)式(7)來更新所有神經(jīng)元的權(quán)值及鄰域函數(shù)和學(xué)習(xí)率;

式中,N為節(jié)點(diǎn)數(shù)量;Ra為監(jiān)控區(qū)域面積;Rs為節(jié)點(diǎn)感知半徑(確定性模型).

在感知模型為概率型時,為確保網(wǎng)絡(luò)的覆蓋率,可取Rs=μ-3σ.

4 理論分析

考慮一有向連通圖G=(V,E),其中,V={ν1, ν2,…,νn}為節(jié)點(diǎn)集合,E?{(i,j):νi,νj∈V}為邊集合.用圖G來表示傳感器載體的通訊拓?fù)?即節(jié)點(diǎn)來表示載體,而邊則表示載體間通訊是否建立.本文假設(shè)通訊拓?fù)錇楣潭ㄓ邢虻那覐?qiáng)連通,定義載體i的鄰接載體集合為Ni={j∈V:(i,j)∈瓗},且有向圖G的鄰接矩陣A=[aij],其中

5 仿真研究

在實(shí)際應(yīng)用中,很少載體能夠滿足一階積分模型,不過大多數(shù)載體可簡化為如下模型:

式中,xi,yi分別為載體i的位置和朝向角度;vi, θi分別為載體i的速度和角速度.

若假設(shè)載體為一差動驅(qū)動小車,則上述變換實(shí)質(zhì)上是將載體模型的質(zhì)點(diǎn)位置由載體兩輪輪距中點(diǎn)位置移動到了垂直于車軸前方距離b的A點(diǎn),如圖1(a)所示,因此,可假設(shè)傳感器位置安裝在圖中A點(diǎn)處,那么,前述算法完全適用于此類型的載體.

仿真設(shè)置待覆蓋區(qū)域?yàn)閳A形、三角形和正方形這3種形狀的閉區(qū)域Ω1,Ω2和Ω3,切換時間設(shè)定為t1=10 s,t2=20 s.取區(qū)域中心為目標(biāo)熱點(diǎn)c0,且有=[cos t,sin t]T,c0(0)=[4,0].Ω1和Ω2為平移區(qū)域,即只作平移變換,而Ω3既作平移變換又作旋轉(zhuǎn)變換,3個區(qū)域均為時變區(qū)域.通訊拓?fù)鋱D為有向圈,如圖1(b)所示,即滿足強(qiáng)連通條件.設(shè)置傳感器載體數(shù)目為25,初值在[-3,3]×[-3,3]區(qū)域以均勻分布隨機(jī)生成,迭代步長為0.02 s.

圖1(c)為SOFM對圓形覆蓋區(qū)域的映射結(jié)果,可以看出圖中的近似正三角形的組態(tài)子結(jié)構(gòu).圖1(d),1(e),1(f)分別為不同時刻不同形狀覆蓋區(qū)域的覆蓋結(jié)果,由圖中SOFM可靈活地映射出不同形狀的區(qū)域,且傳感器載體可精確地跟蹤到指定覆蓋地點(diǎn)完成區(qū)域覆蓋工作.

圖1 仿真結(jié)果Fig.1 Simulation results

6 結(jié) 論

首先對帶覆蓋區(qū)域進(jìn)行離散化,并定義熱點(diǎn)與目標(biāo)熱點(diǎn)的概念,然后通過對覆蓋區(qū)域的離散點(diǎn)采樣來訓(xùn)練SOFM的參數(shù),使得SOFM的權(quán)值能夠映射出帶覆蓋區(qū)域的形態(tài),再由SOFM的權(quán)值信息通過一致性算法解決移動傳感器網(wǎng)絡(luò)對時變覆蓋區(qū)域的實(shí)時覆蓋問題.仿真結(jié)果表明了該算法的可靠性及高效性.

[1] Meguerdichian S,Koushanfar F,Potkonjak M,et al. Coverage problems in wireless ad-hoc sensor networks [C]∥Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies.Anchorage,AK:IEEE,2001:1380-1387.

[2] Kulkarni R V,Venayagamoorthy G K.Particle swarm optimization in wireless-sensor networks:a brief survey[J].IEEE Transactions on Systems,Man,andCybernetics,Part C:Applications and Reviews,2011, 41(2):262-267.

[3] Jin SY,Zhou M,Wu AS.Sensor network optimization using a genetic algorithm[C]∥Proceedings of the 7th World Multiconference on Systemics,Cybernetics and Informatics,2003:109-116.

[4] Kannan A A,Mao G O,Vucetic B.Simulated annealing based localization in wireless sensor network[C]∥The IEEE Conference on Local Computer Networks, 2005:513-514.

[5] Zou M,Ping Z,Zheng S J,et al.A novel energy efficient converage control in WSNs based on ant colony optimization[C]∥International Symposium on Computer Communication Control and Automation, 2010:523-527.

[6] 劉麗麗,陳瑋.基于高斯優(yōu)化的精英魚群算法研究[J].上海理工大學(xué)學(xué)報,2014,36(3):295-298.

[7] 袁光輝,樊重俊,張惠珍,等.一種新的粒子群算法與人工魚群算法的混合算法[J].上海理工大學(xué)學(xué)報, 2014,36(3):223-226,238.

[8] Cortes J,Martinez S,Karatas T,et al.Coverage control for mobile sensing networks[J].IEEE Transactions on Robotics and Automation,2004,20 (2):243-255.

[9] Baghdad Abad H M,Moezzi K,Aghdam AG,et al.Selfdeployment algorithms for field coverage in a network of nonidentical mobile sensors[C]∥2011 IEEE International Conference on Communications,2011: 1-6.

[10] Mahboubi H,Momeni A,Aghdam A G,et al.Optimal target tracking strategy with controlled node mobility in mobile sensor networks[C]∥American Control Conference,2010:2921-2928.

[11] Jalalkamali P,Olfati-Saber R.Information-driven selfdeployment and dynamic sensor coverage for mobile sensor networks[C]∥American Control Conference, 2012:4933-4938.

[12] Olfati-Saber R,Jalalkamali P.Coupled distributed estimation and control for mobile sensor networks[J]. IEEE Transactions on Automatic Control,2012,57 (10):2609-2614.

[13] Zhong M,Cassandras C G.Distributed coverage control and data collection with mobile sensor networks[J].IEEE Transactions on Automatic Control,2011,56(10):2445-2455.

[14] Williams R.The geometrical foundation of natural structure:a source book of design[M].New York: Dover Publications Mineola,1979.

[15] Godsil C D,Royle G,Godsil C D.Algebraic graph theory[M].New York:Springer,2001.

[16] Qu Z.Cooperative control of dynamical systems: applications to autonomous vehicles[M].London: Springer,2009.

[17] Das A,Lewis F L.Distributed adaptive control for synchronization of unknown nonlinear networked systems[J].Automatica,2010,46(12):2014-2021.

(編輯:石 瑛)

Mobile Sensor Networ ks Control Using Self-organizing Feature Map

ZHAOXiaomeng, WANGChaoli
(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

Focusing on the time-varying coverage region for mobile sensor networks of probabilistic model of perception,a real-time coverage algorithm was proposed based on the self-organizing feature map which is used for mapping the target coverage region in the light of real-time sampling points.Based on the consensus control algorithm in multi-agent system,the coverage algorithm drives the networks to form a predetermined formation to coverage task region.The simulation experiments verify the excellent performance of the algorithm.

mobile sensing networks;self-organizing feature map;formation control; time-varying coverage region

TP 24

A

1007-6735(2015)03-0251-06

10.13255/j.cnki.jusst.2015.03.009

2014-01-10

國家自然科學(xué)基金資助項(xiàng)目(61374040);上海市教委科技創(chuàng)新項(xiàng)目(13ZZ115);上海市研究生創(chuàng)新項(xiàng)目(5413302102);上海市重點(diǎn)學(xué)科建設(shè)資助項(xiàng)目(S30501)

趙曉萌(1988-),男,碩士研究生.研究方向:多智能體系統(tǒng)、神經(jīng)網(wǎng)絡(luò)控制.E-mail:zxiaomzxm@163.com

王朝立(1965-),男,教授.研究方向:非線性控制、魯棒控制、機(jī)器人動力學(xué)控制.E-mail:clclwang@126.com