基于動(dòng)態(tài)簇的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心跟蹤算法

吳 斌,衣 曉

(海軍航空工程學(xué)院電子信息工程系,煙臺(tái) 264001)

基礎(chǔ)理論

基于動(dòng)態(tài)簇的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心跟蹤算法

吳 斌,衣 曉

(海軍航空工程學(xué)院電子信息工程系,煙臺(tái) 264001)

提出了一種適用于無線傳感器網(wǎng)絡(luò)中基于動(dòng)態(tài)簇的目標(biāo)跟蹤算法,解決了無線傳感器網(wǎng)絡(luò)跟蹤過程中目標(biāo)信息傳輸及狀態(tài)估計(jì)算法復(fù)雜度高的問題。該算法通過對(duì)目標(biāo)周圍的傳感器節(jié)點(diǎn)臨時(shí)組簇,避免了大規(guī)模喚醒節(jié)點(diǎn)從而降低網(wǎng)絡(luò)壽命的問題。在目標(biāo)狀態(tài)的估計(jì)中,該算法基于探測到目標(biāo)的聲信號(hào)強(qiáng)度動(dòng)態(tài)的調(diào)整節(jié)點(diǎn)的閾值,通過不同閾值所對(duì)應(yīng)到目標(biāo)的距離作為權(quán)值,由探測節(jié)點(diǎn)的位置作為目標(biāo)所在多邊形的各頂點(diǎn)進(jìn)行加權(quán)質(zhì)心定位算法。在硬件配置受限的無線傳感器網(wǎng)絡(luò)中,該算法復(fù)雜度低,對(duì)于節(jié)點(diǎn)的硬件不高。在仿真環(huán)境中,此跟蹤算法的有效性也得到了驗(yàn)證。

無線傳感器網(wǎng)絡(luò)；目標(biāo)跟蹤；分簇；加權(quán)質(zhì)心

0 引 言

無線傳感器網(wǎng)絡(luò)是一門新興學(xué)科，其交叉結(jié)合了半導(dǎo)體、微電子、軟件等學(xué)科理論。作為改變世界的重要新技術(shù)，無線傳感器網(wǎng)絡(luò)的發(fā)展與研究漸漸成為社會(huì)熱點(diǎn)。其在災(zāi)害預(yù)警、檢測和決策支持等方面應(yīng)用前景巨大。與此同時(shí)，其在軍方面的應(yīng)用前景也相當(dāng)巨大。結(jié)合無線傳感器網(wǎng)絡(luò)的特點(diǎn)，其在目標(biāo)監(jiān)測、預(yù)警、跟蹤等發(fā)面具有很大的潛力。

利用無線傳感器網(wǎng)絡(luò)跟蹤目標(biāo)首先要確立網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，即明確網(wǎng)絡(luò)的覆蓋范圍，感知信息的傳輸路徑，然后根據(jù)獲得的信息進(jìn)行目標(biāo)的狀態(tài)估計(jì)。由于傳感器節(jié)點(diǎn)數(shù)量大、密度高，無線傳感器網(wǎng)絡(luò)常采用簇形結(jié)構(gòu)分布式管理。目前無線傳感器網(wǎng)絡(luò)分簇算法主要可以分為集中式和分布式。然而，集中式跟蹤需要節(jié)點(diǎn)向管理節(jié)點(diǎn)發(fā)送信息，節(jié)點(diǎn)的大部分能量消耗在通信上。為了克服集中式跟蹤的缺點(diǎn)，很多學(xué)者研究利用分簇結(jié)構(gòu)進(jìn)行分布式跟蹤[1-6]，文獻(xiàn)[7]介紹了基于節(jié)點(diǎn)剩余能量和探測信號(hào)強(qiáng)度的動(dòng)態(tài)分簇算法。文獻(xiàn)[8]介紹了基于簇頭分布式調(diào)度，簇內(nèi)節(jié)點(diǎn)集中式調(diào)度，利用多節(jié)點(diǎn)分時(shí)跟蹤的方法，該方法定位精度好，但對(duì)節(jié)點(diǎn)密度要求高。文獻(xiàn)[9]介紹了基于無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)分簇的構(gòu)建方法及基于線性規(guī)劃的跟蹤算法。文獻(xiàn)[10]介紹了基于固定簇頭的無線傳感器網(wǎng)絡(luò)分簇方法。本文結(jié)合文獻(xiàn)[9]提出了一種新的跟蹤算法。

1 目標(biāo)跟蹤結(jié)構(gòu)

N個(gè)聲音傳感器節(jié)點(diǎn)均勻布置在監(jiān)視區(qū)域內(nèi)，節(jié)點(diǎn)通信半徑為r，為了使網(wǎng)絡(luò)的壽命延長，除了監(jiān)視區(qū)域邊界的節(jié)點(diǎn)一直處于激活狀態(tài)外，內(nèi)部節(jié)點(diǎn)通常處于休眠狀態(tài)，只有收到激活信號(hào)時(shí)，才會(huì)進(jìn)入激活狀態(tài)。由文獻(xiàn)[5]，目標(biāo)的聲信號(hào)強(qiáng)度一般隨距離成指數(shù)衰減，當(dāng)目標(biāo)進(jìn)入監(jiān)視區(qū)域后，節(jié)點(diǎn)i在t時(shí)刻采樣的聲信號(hào)強(qiáng)度可表示為

式中：s表示目標(biāo)信號(hào)源的聲強(qiáng)度，di（t）是t時(shí)刻目標(biāo)與節(jié)點(diǎn)i的距離，α是信號(hào)強(qiáng)度隨距離的衰減指數(shù)，一般取2，εi是背景噪聲，可以近似為高斯白噪聲，節(jié)點(diǎn)采用三閾值檢測，檢測閾值記為E1，E2，E3。當(dāng)目標(biāo)經(jīng)過節(jié)點(diǎn)i時(shí)，其過程一般是從靠近到遠(yuǎn)離。根據(jù)式（1），節(jié)點(diǎn)i的探測信號(hào)強(qiáng)度也會(huì)是一個(gè)從弱到強(qiáng)再到弱的過程，信號(hào)的峰值則意味著此時(shí)目標(biāo)處在與節(jié)點(diǎn)i最近的距離上。

本文提出的目標(biāo)跟蹤過程大致分為以下幾步：

（1）布置傳感器節(jié)點(diǎn)，邊界節(jié)點(diǎn)發(fā)現(xiàn)目標(biāo)，臨時(shí)組簇，粗計(jì)算目標(biāo)速度、運(yùn)動(dòng)方向；

（2）目標(biāo)進(jìn)入監(jiān)視區(qū)域，由內(nèi)部節(jié)點(diǎn)進(jìn)行精確跟蹤；

（3）簇頭根據(jù)探測到的目標(biāo)信息估計(jì)目標(biāo)的狀態(tài)并匯報(bào)給管理節(jié)點(diǎn)。

2 動(dòng)態(tài)簇的建立

該過程包括探測到目標(biāo)的邊緣傳感器節(jié)點(diǎn)競選簇頭和簇成員征集，網(wǎng)絡(luò)內(nèi)部傳感器節(jié)點(diǎn)競選簇頭和簇成員征集，具體過程如下：

（1）探測到目標(biāo)的節(jié)點(diǎn)定義為i，i=1，2，3，….N1，節(jié)點(diǎn)當(dāng)前測量到的信號(hào)強(qiáng)度為ei，節(jié)點(diǎn)當(dāng)前電量為pi，定義

為參與競選簇頭的時(shí)延，其中e0為節(jié)點(diǎn)探測目標(biāo)信號(hào)強(qiáng)度的上限，p0為節(jié)點(diǎn)攜帶的最大能量，α，β為參數(shù)，tmax為組簇的最大時(shí)延。目標(biāo)離節(jié)點(diǎn)越近，節(jié)點(diǎn)剩余電量越高，ti就越小，成為簇頭的概率越大。

（2）節(jié)點(diǎn)i在ti結(jié)束前收到其他節(jié)點(diǎn)廣播成為簇頭的消息，取消自身ti時(shí)間，并向簇頭發(fā)送自身位置信息。若節(jié)點(diǎn)i在ti結(jié)束前未收到其他節(jié)點(diǎn)廣播成為簇頭的消息，則在ti結(jié)束時(shí)廣播自身成為簇頭的信息，信息包括成為簇頭、自身位置等。

（3）處于簇內(nèi)休眠狀態(tài)的節(jié)點(diǎn)收到其他簇頭當(dāng)選的信息后，轉(zhuǎn)入激活狀態(tài)，并向簇頭發(fā)送自身的位置信息。

從動(dòng)態(tài)簇建立的過程來看，距離目標(biāo)越近，剩余能量越大的節(jié)點(diǎn)，時(shí)延越小，因而成為簇頭的概率越大。簇成員包括在競選簇頭中落選的節(jié)點(diǎn)以及在簇頭通信范圍內(nèi)的休眠節(jié)點(diǎn)。由于節(jié)點(diǎn)的通信半徑為感知半徑的兩倍，保證了只會(huì)形成一個(gè)簇。

當(dāng)目標(biāo)靠近監(jiān)測區(qū)域時(shí)，最先是由處在網(wǎng)絡(luò)邊緣的工作節(jié)點(diǎn)發(fā)現(xiàn)并計(jì)算目標(biāo)的各項(xiàng)參數(shù)，具體如圖1所示。

當(dāng)目標(biāo)恰好出現(xiàn)在邊緣節(jié)點(diǎn)1的最大感知半徑上，此時(shí)節(jié)點(diǎn)1向其鄰居節(jié)點(diǎn)發(fā)出廣播，激活休眠節(jié)點(diǎn)，因?yàn)檫吘壒?jié)點(diǎn)時(shí)刻處于工作狀態(tài)，為更好地節(jié)約邊緣節(jié)點(diǎn)的能量，選擇距離探測到目標(biāo)的邊緣節(jié)點(diǎn)最近的鄰居節(jié)點(diǎn)2作為第一個(gè)動(dòng)態(tài)簇的簇頭。假設(shè)目標(biāo)下個(gè)時(shí)刻以任意角度方向駛向監(jiān)視區(qū)域，令目標(biāo)進(jìn)入監(jiān)視區(qū)域的距離為R，A為目標(biāo)進(jìn)入監(jiān)視區(qū)域的位置，B為AC的中點(diǎn)，為節(jié)約網(wǎng)絡(luò)能量，盡量減少簇頭更換頻率，由于簇頭擔(dān)負(fù)計(jì)算和信息傳輸?shù)娜蝿?wù)，其能量消耗會(huì)大大增加，所以也不能使簇頭工作過長時(shí)間，由圖可知，由于節(jié)點(diǎn)1，2間距較短，可以近似的認(rèn)為A到鄰居節(jié)點(diǎn)2的距離為R，當(dāng)目標(biāo)運(yùn)動(dòng)到A點(diǎn)時(shí)，距離目標(biāo)為r的節(jié)點(diǎn)并不全部包含在以鄰居節(jié)點(diǎn)2為圓心，半徑為R的圓中，所以在目標(biāo)到達(dá)A之前，網(wǎng)絡(luò)至少再形成一個(gè)簇才能達(dá)到精確跟蹤的目的。取AC的中點(diǎn)B

圖1 邊緣節(jié)點(diǎn)示意圖

3 目標(biāo)狀態(tài)估計(jì)

假設(shè)目標(biāo)在監(jiān)視區(qū)域內(nèi)做隨機(jī)運(yùn)動(dòng)，估計(jì)間隔時(shí)間較短時(shí)，目標(biāo)在此間隔時(shí)間內(nèi)可以近似的認(rèn)為做直線運(yùn)動(dòng)。假定在某估計(jì)間隔時(shí)間內(nèi)有n個(gè)節(jié)點(diǎn)探測到聲信號(hào)強(qiáng)度的變化，其順序依次記為e1，e2，…，en，下面探討如何根據(jù)這n個(gè)節(jié)點(diǎn)估計(jì)目標(biāo)的狀態(tài)。

節(jié)點(diǎn)依次記錄目標(biāo)經(jīng)過時(shí)信號(hào)強(qiáng)度的最大值ei（t）max和最小值ei（t）min，并發(fā)送給簇頭，由簇頭選取其中的最大值和最小值，

本文提出一個(gè)閾值半徑的概念，即目標(biāo)的信號(hào)強(qiáng)度達(dá)到某個(gè)閾值時(shí)，節(jié)點(diǎn)激活，此時(shí)目標(biāo)位置就在以該閾值為探測信號(hào)強(qiáng)度所求的距離半徑上。定義式（3）為閾值最大半徑R，e（t）min為閾值E1。

本文提出一個(gè)基于多閾值半徑加權(quán)質(zhì)心算法，當(dāng)目標(biāo)信號(hào)強(qiáng)度到達(dá)閾值En且不超過閾值En+1時(shí)，認(rèn)為目標(biāo)與節(jié)點(diǎn)距離為En的閾值半徑。加權(quán)質(zhì)心算法具體如下（為方便表示，下文將不再使用閾值，直接以與閾值相對(duì)應(yīng)的閾值半徑表示）

目標(biāo)運(yùn)動(dòng)到閾值范圍內(nèi)即可激活傳感器進(jìn)行工

可得到目標(biāo)的位置，如圖2所示。然而這樣求出的目標(biāo)位置與實(shí)際目標(biāo)位置偏差較大，并且目標(biāo)處在閾值內(nèi)的節(jié)點(diǎn)可能不止一個(gè)，按上述算法會(huì)使節(jié)點(diǎn)的大部分能量消耗在計(jì)算目標(biāo)位置上，可能使得節(jié)點(diǎn)能量提前耗盡，因此提出基于多閾值目標(biāo)跟蹤算法，來解決大量運(yùn)算帶來的能量消耗過大問題。

圖2 節(jié)點(diǎn)探測示意圖

考慮到目標(biāo)的位置，會(huì)存在估計(jì)偏大的問題，如圖3所示，目標(biāo)處在某個(gè)距離閾值內(nèi)部，靠近下一個(gè)閾值較近，但是計(jì)算權(quán)值卻是用較大的距離權(quán)值，這樣也會(huì)導(dǎo)致計(jì)算目標(biāo)位置產(chǎn)生較大誤差，所以再一次進(jìn)行位置估算，將權(quán)值改為1，，如式（8）：

圖3 目標(biāo)位置圖

將上述兩式所求的坐標(biāo)求和取中點(diǎn)可解決定位誤差較大的問題，所求得的目標(biāo)最終位置如下：

當(dāng)目標(biāo)經(jīng)過節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)記錄所獲取信號(hào)強(qiáng)度最大值及最小值，并上報(bào)給簇頭，簇頭根據(jù)所獲得的的信息選取其中的最大值和最小值。當(dāng)有節(jié)點(diǎn)探測到的最大值大于之前簇頭選取的最大值時(shí)，或最小值小于之前簇頭選取的最小值時(shí)，簇頭將采用此節(jié)點(diǎn)的最大值或最小值用來重新計(jì)算E1，E2，E3，R，并發(fā)送消息給簇內(nèi)節(jié)點(diǎn)，通知改變閾值。

節(jié)點(diǎn)1和節(jié)點(diǎn)n是一個(gè)估計(jì)時(shí)間間隔內(nèi)第一個(gè)和最后一個(gè)探測到目標(biāo)的節(jié)點(diǎn)，記時(shí)間為tn，假設(shè)此過程中e（t）max或e（t）min發(fā)生變化，由此帶來R變化，記Rˊ，設(shè)與目標(biāo)距離為ˊ的節(jié)點(diǎn)為（），個(gè)數(shù)為nˊ，距離為ˊ的節(jié)點(diǎn)為（，個(gè)數(shù)為mˊ，距離為R′的節(jié)點(diǎn)為（，個(gè)數(shù)為gˊ。記目標(biāo)的位置為

4 能量損耗過程

在該無線傳感器網(wǎng)絡(luò)工作過程中，能量損耗主要集中在組簇、簇內(nèi)節(jié)點(diǎn)探測和發(fā)送信息、簇頭損耗三個(gè)方面。組簇的能量損耗是由探測到目標(biāo)的節(jié)點(diǎn)進(jìn)行臨時(shí)組簇的能量損耗，包括探測到目標(biāo)節(jié)點(diǎn)的探測損耗，競選簇頭損耗，簇頭廣播通知簇內(nèi)節(jié)點(diǎn)成簇的通信損耗及簇內(nèi)節(jié)點(diǎn)發(fā)送自身信息的通信損耗。簇內(nèi)節(jié)點(diǎn)探測和發(fā)送信息的能量損耗包括簇內(nèi)探測節(jié)點(diǎn)的能量損耗，節(jié)點(diǎn)發(fā)送目標(biāo)信息的通信損耗。簇頭損耗包括接收目標(biāo)信息的能量損耗，計(jì)算目標(biāo)信息的能量損耗。

節(jié)點(diǎn)發(fā)送l bit信息的能耗ETX（l，d）為

節(jié)點(diǎn)接收l bit信息的能耗ERX（l）為

簇頭進(jìn)行數(shù)據(jù)處理和融合時(shí)，處理l bit數(shù)據(jù)，需要消耗的能量為Eda-fu（l）

EDA為融合單位比特信息的能耗。

5 目標(biāo)跟蹤性能仿真及結(jié)論

為驗(yàn)證跟蹤算法的有效性，本文進(jìn)行了兩組仿真，分別研究了目標(biāo)斜向穿過監(jiān)測區(qū)域及網(wǎng)絡(luò)剩余能量。仿真條件設(shè)置如下，1000個(gè)傳感器節(jié)點(diǎn)均勻分布在500×500 m的二維監(jiān)視區(qū)域內(nèi)，節(jié)點(diǎn)的探測半徑r=20 m，信號(hào)強(qiáng)度s∈[6，100]，衰減系數(shù)α= 2，背景噪聲均值ε=4，目標(biāo)速度為5 m/s，探測及通信損耗為0.00005 J，系統(tǒng)總能量為10 J。仿真結(jié)果如圖4，5所示。

圖4 誤差對(duì)比圖

由圖5可知，基于多閾值的目標(biāo)跟蹤算法定位誤差顯然更小，其誤差大概分布在[2，6]m之間，相對(duì)于節(jié)點(diǎn)20 m的探測距離，這樣的誤差值是可以接受的。理論上講，隨著時(shí)間的推移，定位精度應(yīng)該越來越高，因?yàn)殡S著不斷地探測計(jì)算，目標(biāo)的狀態(tài)信息會(huì)更加精確，但是考慮到節(jié)點(diǎn)分布的不確定性，所以在中間時(shí)刻會(huì)出現(xiàn)一些定位誤差偏高的情況，總體來說，在部署節(jié)點(diǎn)數(shù)量為1000個(gè)時(shí)，該算法的定位誤差在2至4m左右，當(dāng)節(jié)點(diǎn)數(shù)量增多時(shí)，定位誤差會(huì)更小，這是因?yàn)殡S著節(jié)點(diǎn)的密度變大，探測不到目標(biāo)的概率會(huì)大大降低。從圖6中可以看出，基于本文算法的網(wǎng)絡(luò)剩余能量是最大的。相比較于全網(wǎng)工作與固定簇工作，基于動(dòng)態(tài)組簇能充分利用探測到目標(biāo)的節(jié)點(diǎn)，而不是盲目的大范圍的喚醒其周圍的節(jié)點(diǎn)進(jìn)行工作，從而節(jié)省了網(wǎng)絡(luò)的能量。

圖5 剩余能量對(duì)比圖

6 結(jié) 語

目標(biāo)跟蹤是無線傳感器網(wǎng)絡(luò)的重要應(yīng)用之一，包括網(wǎng)絡(luò)組織和信號(hào)處理兩個(gè)方面。增強(qiáng)系統(tǒng)生命力、延長網(wǎng)絡(luò)壽命和提高跟蹤精度是設(shè)計(jì)目標(biāo)跟蹤系統(tǒng)的重要目標(biāo)。本文提出了基于動(dòng)態(tài)組簇的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心跟蹤算法。該跟蹤算法具有計(jì)算復(fù)雜度低和跟蹤精度高等優(yōu)點(diǎn)。

[1] ZHAO F，LIU J.Information-Driven Dynamic Sensor Collaboration[J].IEEE Signal Processing Magazine，2002，19（2）：61-72.

[2] LID，HU Y H.Energy Based Collaborative Source Localization Using Acoustic Micro-sensor Array[J].Journal EUROSIPApplied Signal Processing，2003（4）：321-337.

[3] JING T，et al.Binary Variational Filtering for Target Tracking in Sensor Networks[C].Proc of 14th IEEE/SP Workshop on Statistical Signal Processing.Madsion，2007：685-689.

[4] DURIC PM，et al.Target Tracking by Particle Filtering in Binary Sensor Networks[J].IEEE Trans on signal Processing，2008，56（6）：2229-2238.

[5] 孫超，趙路路，張影等.無線傳感器網(wǎng)絡(luò)分簇拓?fù)涞母采w區(qū)域節(jié)點(diǎn)調(diào)度優(yōu)化算法[J].傳感技術(shù)學(xué)報(bào)，2010（1）：166-121.

[6] 衣曉，鄧露，劉瑜.基于基站劃分網(wǎng)格的無線傳感器網(wǎng)絡(luò)分簇算法[J].控制理論與應(yīng)用，2012，29（2）：145-150.

[7] 周紅波，邢昌風(fēng)，萬福.面向目標(biāo)跟蹤的無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)分簇[J].電光與控制，2013（20）：14-18.

[8] 李迅，李洪峻.基于簇結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)移動(dòng)目標(biāo)精確跟蹤[J].傳感技術(shù)學(xué)報(bào)，2009，22（12）：1814-1817.

[9] 鄧克波，劉中.基于無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)簇的目標(biāo)跟蹤[J].兵工學(xué)報(bào)，2008，29（10）：1197-1202.

[10]鄧露.無線傳感器網(wǎng)絡(luò)分簇算法研究[D].山東煙臺(tái)：海軍航空工程學(xué)院，2010

[11]Rappaport T，Wireless Communications：Principle& Practice[M].Englewood Cliff，NJ：Prentice-Hall，1996.

吳 斌(1992—),男,江蘇泰州人,碩士研究生,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤；

E-mail：1031927070@qq.com

衣 曉(1976—),男,山東煙臺(tái)人,教授,碩士研究生導(dǎo)師,主要研究方向?yàn)樾畔⑷诤?、無線傳感器網(wǎng)絡(luò)。

A W ireless Sensor Network-weighted-centroid Tracking A lgorithm Based on the Dynam ic Cluster

WU Bin，YIXiao
（Naval Aeronautical Engineering Institute，Department Of Electronic And Information Engineering，Shandong Yantai264001，China）

A suitable algorithm which is based on dynamic cluster forwireless sensor network in the target tracking is proposed to solve the problem of high complexity algorithm，which is target information transmission and state estimation in the process of wireless sensor network.By setting of sensor nodes of the cluster around the target temporarily，the algorithm avoidswaking up nodesmassively which will lead to reduce the network life.In the target state estimation，the algorithm based on the detected target acoustic signal intensity dynamically adjusts node’s threshold，through the different thresholds corresponded to the distance to the target as a weight，and by detecting node location as a target in each vertex weighted centroid of polygon for localization algorithm.In the limited hardware configuration of wireless sensor network，the algorithm complexity is low，and the node demand is not high.In the simulation environment，the effectiveness of the algorithm is proved.

wireless sensor network；target tracking；cluster；weighted centroid

TP393

A

1673-5692（2015）04-355-06

10.3969/j.issn.1673-5692.2015.04.005

2015-05-25

2015-07-30