基于動(dòng)態(tài)分簇的移動(dòng)目標(biāo)追蹤方法

2017-04-17 05:19:28毛鶯池王龍寶陳小麗

計(jì)算機(jī)應(yīng)用 2017年1期

關(guān)鍵詞：信息

包威，毛鶯池，王龍寶，陳小麗

(河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京 211100)

(*通信作者電子郵箱maoyingchi@gmail.com)

基于動(dòng)態(tài)分簇的移動(dòng)目標(biāo)追蹤方法

包威，毛鶯池*，王龍寶，陳小麗

(河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京 211100)

(*通信作者電子郵箱maoyingchi@gmail.com)

針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSN)中目標(biāo)追蹤的準(zhǔn)確性低、網(wǎng)絡(luò)能耗過(guò)高和網(wǎng)絡(luò)生命周期短等問(wèn)題，提出基于動(dòng)態(tài)分簇的移動(dòng)目標(biāo)追蹤技術(shù)。首先，構(gòu)建了雙層環(huán)狀動(dòng)態(tài)分簇的拓?fù)淠Ｐ?TRDC)，并提出了動(dòng)態(tài)分簇的更新算法；其次，在質(zhì)心定位算法基礎(chǔ)上，考慮到節(jié)點(diǎn)的能量，提出了基于功率級(jí)別的質(zhì)心定位(CLPL)算法；最后，為了進(jìn)一步減小網(wǎng)絡(luò)的能耗，改進(jìn)CLPL算法，提出了隨機(jī)性定位算法。在仿真實(shí)驗(yàn)中，與靜態(tài)簇相比，網(wǎng)絡(luò)周期延長(zhǎng)了22.73%；與非環(huán)狀簇相比，丟失率降低了40.79%；而追蹤準(zhǔn)確性與基于接受信號(hào)強(qiáng)度值(RSSI)算法相差不大。所提的追蹤技術(shù)能夠有效保證追蹤準(zhǔn)確度，同時(shí)降低網(wǎng)絡(luò)能耗，減小目標(biāo)丟失率。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)；雙層環(huán)狀；目標(biāo)追蹤；動(dòng)態(tài)簇；質(zhì)心定位

0 引言

目標(biāo)追蹤是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(Wireless Sensor Network, WSN)最具代表性和基礎(chǔ)性的應(yīng)用之一。大量的微型傳感器節(jié)點(diǎn)部署在監(jiān)測(cè)區(qū)域內(nèi)，通過(guò)無(wú)線(xiàn)通信方式形成一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)稱(chēng)為無(wú)線(xiàn)傳感器網(wǎng)絡(luò)[1-2]。目標(biāo)追蹤在各個(gè)領(lǐng)域都有所涉及：如在軍事上，對(duì)敵人坦克、裝甲車(chē)進(jìn)行定位和跟蹤；在災(zāi)難預(yù)測(cè)方面，定位泥石流的發(fā)生地點(diǎn)以及擴(kuò)散速度等信息；在動(dòng)物遷徙監(jiān)測(cè)方面，需要追蹤遷徙的動(dòng)物，獲得其位置和種群等信息。移動(dòng)目標(biāo)追蹤技術(shù)幾乎涉及到無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的各個(gè)應(yīng)用領(lǐng)域，在環(huán)境監(jiān)測(cè)[3]、軍事監(jiān)控[4]和基建保護(hù)[5]等領(lǐng)域都被廣泛應(yīng)用，體現(xiàn)了巨大的科學(xué)意義和應(yīng)用前景。

目前，移動(dòng)目標(biāo)追蹤技術(shù)采用的拓?fù)浣Y(jié)構(gòu)，在監(jiān)測(cè)較快的移動(dòng)目標(biāo)時(shí)，存在著定位不夠準(zhǔn)確問(wèn)題，容易出現(xiàn)丟失追蹤目標(biāo)，導(dǎo)致重新定位目標(biāo)，消耗較大的能量，直接影響追蹤目標(biāo)的及時(shí)性，導(dǎo)致較長(zhǎng)的網(wǎng)絡(luò)延遲。現(xiàn)有的質(zhì)心定位算法，在網(wǎng)絡(luò)節(jié)點(diǎn)部署不均勻時(shí)，追蹤目標(biāo)時(shí)會(huì)出現(xiàn)較大的誤差，追蹤不夠精確，而且網(wǎng)絡(luò)中能量不同的節(jié)點(diǎn)對(duì)定位目標(biāo)有較大的影響。此外，連續(xù)不斷地定位追蹤目標(biāo)，雖然可以提供較為準(zhǔn)確的目標(biāo)定位，但是付出了較大的能耗代價(jià)。總之，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的移動(dòng)目標(biāo)追蹤都要面對(duì)兩個(gè)挑戰(zhàn)：一是設(shè)計(jì)追蹤模型，保證目標(biāo)定位和移動(dòng)軌跡描述的準(zhǔn)確性；二是盡量減少目標(biāo)追蹤模型的能量消耗，延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期。

針對(duì)這兩個(gè)問(wèn)題，本文主要工作如下：

1)一般的動(dòng)態(tài)分簇監(jiān)測(cè)較快的移動(dòng)目標(biāo)時(shí)，容易丟失目標(biāo)，提出雙層環(huán)狀動(dòng)態(tài)分簇的拓?fù)淠Ｐ?Two-Ring Dynamic Clustering, TRDC)；為適應(yīng)目標(biāo)的隨機(jī)性移動(dòng)，提出了動(dòng)態(tài)簇的更新算法。

2)在質(zhì)心定位算法的基礎(chǔ)上進(jìn)行改進(jìn)，將節(jié)點(diǎn)的能量考慮在內(nèi)，提出了基于功率級(jí)別的質(zhì)心定位(Centroid Localization based on Power-Level, CLPL)算法；為了減少網(wǎng)絡(luò)的能耗，進(jìn)一步優(yōu)化CLPL算法，結(jié)合目標(biāo)移動(dòng)的相關(guān)性，提出了隨機(jī)性定位算法。

3)通過(guò)實(shí)驗(yàn)，得出基于環(huán)狀動(dòng)態(tài)分簇的移動(dòng)目標(biāo)追蹤技術(shù)，在追蹤準(zhǔn)確度、能耗和丟失率等方面具有優(yōu)勢(shì)。

1 研究現(xiàn)狀

傳感器監(jiān)測(cè)用戶(hù)感興趣的事件，節(jié)點(diǎn)間相互協(xié)作，計(jì)算出移動(dòng)事件的軌跡，回傳給基站。基站根據(jù)計(jì)算出來(lái)的軌跡，對(duì)移動(dòng)事件進(jìn)行追蹤。目前，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的移動(dòng)目標(biāo)追蹤技術(shù)一般可以歸納為：

1)基于二元傳感器網(wǎng)絡(luò)的目標(biāo)追蹤技術(shù)。如CTBD(Cooperative Tracking with Binary-Detection)[6]、BPS(Binary Proximity Sensors)[7]。追蹤目標(biāo)處于傳感器節(jié)點(diǎn)感知范圍內(nèi)或感知范圍外，二元傳感器節(jié)點(diǎn)的功能非常有限，只能根據(jù)目標(biāo)是否在節(jié)點(diǎn)的感知范圍內(nèi)作出決策，而無(wú)法測(cè)量目標(biāo)與節(jié)點(diǎn)的距離。

2)基于節(jié)點(diǎn)選擇協(xié)作的目標(biāo)追蹤技術(shù)。通過(guò)選擇合適的節(jié)點(diǎn)協(xié)作執(zhí)行追蹤任務(wù)，減少網(wǎng)絡(luò)內(nèi)工作節(jié)點(diǎn)數(shù)目，降低數(shù)據(jù)傳輸量，從而節(jié)省能耗和通信帶寬。信息驅(qū)動(dòng)的節(jié)點(diǎn)協(xié)作機(jī)制[8]根據(jù)節(jié)點(diǎn)通信、獲取目標(biāo)位置信息以及處理監(jiān)測(cè)數(shù)據(jù)的能耗三方面信息，選擇下一時(shí)刻的跟蹤節(jié)點(diǎn)。由于節(jié)點(diǎn)可以選擇后繼追蹤節(jié)點(diǎn)，因此該機(jī)制能夠有效減少參與追蹤任務(wù)的節(jié)點(diǎn)數(shù)量。

3)可容錯(cuò)的目標(biāo)追蹤技術(shù)。由于傳感器節(jié)點(diǎn)可能失效、感知部件精度有限和環(huán)境干擾等因素，WSN存在各種不確定性。容錯(cuò)機(jī)制可降低網(wǎng)絡(luò)不確定性對(duì)目標(biāo)追蹤質(zhì)量的影響，基于不可靠節(jié)點(diǎn)序列的目標(biāo)追蹤方法[9]，考慮到感知范圍和環(huán)境噪聲的不規(guī)則性等因素，將追蹤問(wèn)題轉(zhuǎn)化為節(jié)點(diǎn)序列的最優(yōu)化匹配問(wèn)題。此外，引入睡眠調(diào)度機(jī)制[10]，使活躍節(jié)點(diǎn)協(xié)同工作對(duì)目標(biāo)進(jìn)行定位，此方法充分考慮了信息丟失和感知誤差帶來(lái)的非確定性。

4)基于特定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的目標(biāo)追蹤技術(shù)。通過(guò)采用特定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，協(xié)助節(jié)點(diǎn)完成目標(biāo)的監(jiān)測(cè)和追蹤任務(wù)。如基于分布式動(dòng)態(tài)分簇的目標(biāo)追蹤方法[11]，該方法假設(shè)能力較強(qiáng)的特殊傳感器節(jié)點(diǎn)擔(dān)當(dāng)簇頭節(jié)點(diǎn)，當(dāng)簇頭節(jié)點(diǎn)監(jiān)測(cè)到信號(hào)強(qiáng)度超過(guò)預(yù)定義閾值后，即轉(zhuǎn)入活躍狀態(tài)，并向鄰居節(jié)點(diǎn)廣播數(shù)據(jù)以召集簇內(nèi)節(jié)點(diǎn)，簇頭節(jié)點(diǎn)接收簇內(nèi)成員的感知信息，并估算追蹤目標(biāo)位置。

5)基于預(yù)測(cè)模型的目標(biāo)追蹤技術(shù)。根據(jù)目標(biāo)此時(shí)的位置，預(yù)測(cè)目標(biāo)下一時(shí)刻的位置，調(diào)度節(jié)點(diǎn)處于工作狀態(tài)或睡眠狀態(tài)，節(jié)省網(wǎng)絡(luò)能耗。由于目標(biāo)的運(yùn)動(dòng)軌跡具有連續(xù)性，無(wú)法從單個(gè)時(shí)間間隔內(nèi)預(yù)測(cè)目標(biāo)移動(dòng)軌跡，無(wú)縫數(shù)據(jù)挖掘(Seamless Data Mining, SDM)算法[12]能夠發(fā)現(xiàn)移動(dòng)目標(biāo)的時(shí)間運(yùn)動(dòng)模式，并提出了基于時(shí)間運(yùn)動(dòng)模式的目標(biāo)定位算法，有效減少預(yù)測(cè)誤差。

2 系統(tǒng)模型

目標(biāo)在區(qū)域內(nèi)移動(dòng)，能夠被傳感器節(jié)點(diǎn)監(jiān)測(cè)的區(qū)域稱(chēng)為追蹤區(qū)域。為了簡(jiǎn)化起見(jiàn)，本文對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)模型作出了如下假設(shè)：

1)追蹤區(qū)域S為二維平面區(qū)域；節(jié)點(diǎn)一旦部署不再移動(dòng)；只有一個(gè)sink節(jié)點(diǎn)，其存儲(chǔ)能力和計(jì)算能力不受限制；

2)節(jié)點(diǎn)均勻分布，每個(gè)節(jié)點(diǎn)有一個(gè)ID，從1到n標(biāo)識(shí)；

3)節(jié)點(diǎn)通過(guò)GPS(Global Position System)或其他機(jī)制[13]獲得自己的坐標(biāo)信息，每個(gè)感知節(jié)點(diǎn)都能獲得sink節(jié)點(diǎn)的坐標(biāo)信息；

4)節(jié)點(diǎn)的感知功率級(jí)別是可調(diào)的，感知半徑隨功率級(jí)別動(dòng)態(tài)變化[14]；

5)節(jié)點(diǎn)有四種狀態(tài)：休眠(sleep)、等待(wait)、工作(work)和κ級(jí)別工作(κ_work)。工作狀態(tài)的節(jié)點(diǎn)可正常感知和通信；休眠狀態(tài)的節(jié)點(diǎn)不工作；等待狀態(tài)的節(jié)點(diǎn)感知半徑較小；κ級(jí)別工作是感知功率級(jí)別增大κ(κ≥1，κ=1時(shí)為正常工作狀態(tài))倍后的狀態(tài)，具有較大的感知半徑。節(jié)點(diǎn)信息表如表1所示。

表1 節(jié)點(diǎn)信息表

在目標(biāo)未進(jìn)入節(jié)點(diǎn)感知范圍內(nèi)，節(jié)點(diǎn)采取節(jié)能的工作機(jī)制[15]。當(dāng)目標(biāo)進(jìn)入感知范圍內(nèi)后，為了提高監(jiān)測(cè)的準(zhǔn)確率，應(yīng)使更多的節(jié)點(diǎn)加入監(jiān)測(cè)，但不能監(jiān)測(cè)到目標(biāo)的節(jié)點(diǎn)仍采取節(jié)能機(jī)制，避免不必要的能耗。因此，在保證監(jiān)測(cè)準(zhǔn)確率的同時(shí)，又能降低節(jié)點(diǎn)的能耗，本文采用動(dòng)態(tài)分簇的拓?fù)浣Y(jié)構(gòu)。

3 動(dòng)態(tài)分簇

3.1 雙層環(huán)結(jié)構(gòu)動(dòng)態(tài)簇

在構(gòu)建動(dòng)態(tài)簇前，先對(duì)網(wǎng)絡(luò)進(jìn)行初始化。分為兩階段：第一階段，將節(jié)點(diǎn)都設(shè)為等待狀態(tài)，sink節(jié)點(diǎn)以最大功率進(jìn)行廣播，給定合適的閾值，若節(jié)點(diǎn)收到的信號(hào)強(qiáng)度大于閾值，則進(jìn)入工作狀態(tài)并置q為1，向sink節(jié)點(diǎn)報(bào)告其ID和剩余能量，sink節(jié)點(diǎn)將這些信息登記到sink候選簇頭表中(表2)；反之，則進(jìn)入休眠狀態(tài)。第二階段，工作狀態(tài)的節(jié)點(diǎn)調(diào)整通信功率至一跳范圍距離(表3)，進(jìn)行消息廣播，收到消息的節(jié)點(diǎn)進(jìn)入工作狀態(tài)，并將其ID和剩余能量回傳，同時(shí)調(diào)整通信功率至一跳范圍距離，進(jìn)行消息廣播，鄰居節(jié)點(diǎn)互相登記信息到鄰居節(jié)點(diǎn)信息表。

表2 sink節(jié)點(diǎn)候選簇頭表

雙層環(huán)結(jié)構(gòu)動(dòng)態(tài)簇的構(gòu)建分為以下步驟：

1)等待就緒。目標(biāo)出現(xiàn)在追蹤區(qū)域之前，節(jié)點(diǎn)以等待狀態(tài)監(jiān)測(cè)網(wǎng)絡(luò)中可能出現(xiàn)的移動(dòng)目標(biāo)。

2)構(gòu)建內(nèi)層環(huán)結(jié)構(gòu)。當(dāng)目標(biāo)進(jìn)入追蹤區(qū)域后，所有能監(jiān)測(cè)到目標(biāo)出現(xiàn)的節(jié)點(diǎn)進(jìn)入正常工作狀態(tài)，加入內(nèi)層環(huán)集合，同時(shí)根據(jù)鄰居節(jié)點(diǎn)信息表，通知鄰居節(jié)點(diǎn)，如果鄰居節(jié)點(diǎn)已經(jīng)處于內(nèi)層環(huán)集合，則不作回應(yīng)。

3)構(gòu)建外層環(huán)結(jié)構(gòu)。收到通知的非內(nèi)層環(huán)集合的鄰居節(jié)點(diǎn)，首先調(diào)整至正常工作狀態(tài)，然后再將功率增大至κ倍，感知范圍增大。此時(shí)，如果鄰居節(jié)點(diǎn)能夠監(jiān)測(cè)到移動(dòng)目標(biāo)，則加入外層環(huán)集合，進(jìn)入κ級(jí)別工作狀態(tài)；反之，鄰居節(jié)點(diǎn)降低功率，進(jìn)入等待狀態(tài)。

表3 i節(jié)點(diǎn)一跳范圍內(nèi)鄰居節(jié)點(diǎn)信息表

如圖1所示，1所在的是外環(huán)，2所在的是內(nèi)環(huán)。虛線(xiàn)表示內(nèi)外環(huán)之間的一跳關(guān)系。

圖1 雙層環(huán)結(jié)構(gòu)動(dòng)態(tài)簇

3.2 簇內(nèi)工作機(jī)制

簇內(nèi)成員節(jié)點(diǎn)監(jiān)測(cè)移動(dòng)目標(biāo)，實(shí)時(shí)向簇頭節(jié)點(diǎn)匯報(bào)數(shù)據(jù)和剩余能量。簇頭節(jié)點(diǎn)的工作主要是：

1)估計(jì)移動(dòng)目標(biāo)當(dāng)前位置。簇頭節(jié)點(diǎn)收到數(shù)據(jù)后，執(zhí)行數(shù)據(jù)處理，估算目標(biāo)的位置。

2)更新簇內(nèi)信息。簇頭節(jié)點(diǎn)收到簇內(nèi)成員的能量信息后，將數(shù)據(jù)登記到臨時(shí)簇成員信息表(由成員ID和剩余能量組成)，每隔一段時(shí)間后，廣播臨時(shí)簇成員信息表數(shù)據(jù)，簇內(nèi)成員收到數(shù)據(jù)后，查詢(xún)臨時(shí)簇成員信息表，在鄰居節(jié)點(diǎn)信息表中更新此鄰居節(jié)點(diǎn)信息。

3)向sink節(jié)點(diǎn)傳送數(shù)據(jù)。簇頭節(jié)點(diǎn)通過(guò)單跳或多跳的路由方式[16]將目標(biāo)位置數(shù)據(jù)和能量信息發(fā)送到sink節(jié)點(diǎn)， sink節(jié)點(diǎn)收到信息后，查詢(xún)sink節(jié)點(diǎn)候選簇頭信息表，如果存在此簇頭節(jié)點(diǎn)信息，則更新sink節(jié)點(diǎn)候選簇頭信息表；否則只接收位置數(shù)據(jù)。

3.3 分簇動(dòng)態(tài)更新

隨著目標(biāo)的隨機(jī)移動(dòng)或追蹤區(qū)域的改變，簇結(jié)構(gòu)也發(fā)生變化，因此動(dòng)態(tài)簇需要定期更新，主要考慮以下三方面：新監(jiān)測(cè)到移動(dòng)目標(biāo)的節(jié)點(diǎn)加入、不能監(jiān)測(cè)到移動(dòng)目標(biāo)的節(jié)點(diǎn)退出和簇頭節(jié)點(diǎn)移交。

3.3.1 新節(jié)點(diǎn)加入動(dòng)態(tài)簇

目標(biāo)在不停地移動(dòng)，追蹤區(qū)域內(nèi)處于等待狀態(tài)的節(jié)點(diǎn)會(huì)監(jiān)測(cè)到目標(biāo)，將這些節(jié)點(diǎn)加入動(dòng)態(tài)簇。

對(duì)于任意一個(gè)非簇內(nèi)節(jié)點(diǎn)i，即i?Cdyn，當(dāng)目標(biāo)進(jìn)入感知范圍內(nèi)，節(jié)點(diǎn)i發(fā)送加入動(dòng)態(tài)簇的廣播請(qǐng)求REQin。等待Δt時(shí)間后，如果收到簇頭節(jié)點(diǎn)j的同意信息ANSin，則節(jié)點(diǎn)i加入簇Cj，簇頭節(jié)點(diǎn)j將節(jié)點(diǎn)i信息登記到臨時(shí)簇成員信息表；如果沒(méi)有收到任何信息，則進(jìn)入構(gòu)建動(dòng)態(tài)簇的步驟。節(jié)點(diǎn)i根據(jù)鄰居節(jié)點(diǎn)信息表，通知一跳范圍內(nèi)的鄰居節(jié)點(diǎn)k，節(jié)點(diǎn)k進(jìn)入κ級(jí)別工作狀態(tài)，如果能監(jiān)測(cè)到移動(dòng)目標(biāo)，則申請(qǐng)加入簇Cj，否則進(jìn)入等待狀態(tài)。

新節(jié)點(diǎn)加入動(dòng)態(tài)簇算法如算法2所示。

算法1intJoin(i,j)算法。

輸入：節(jié)點(diǎn)i，當(dāng)前簇頭節(jié)點(diǎn)j的動(dòng)態(tài)簇Cj。輸出：節(jié)點(diǎn)i加入Cj。

/*Si表示節(jié)點(diǎn)i是否監(jiān)測(cè)到目標(biāo)：值0表示未監(jiān)測(cè)到，值1表示監(jiān)測(cè)到；i.id、i.energy分別為節(jié)點(diǎn)i的編號(hào)和剩余能量；Cdyn為動(dòng)態(tài)簇；T_CM為臨時(shí)簇成員信息表*/

IfSi=1

NodeisendREQinto sink nodej

Wait for Δttime

If nodeireceive theANSinfrom sinkj

Then

Cj=Cj+i

//加入動(dòng)態(tài)簇Cj

Sinknodejrecordi.id,i.energyto T_CM

Return 1

10)

Else

11)

Create a dynamic cluster

12)

Return 0

13)

End

14)

End

算法2 新節(jié)點(diǎn)加入動(dòng)態(tài)簇算法。

輸入：移動(dòng)的目標(biāo)、新節(jié)點(diǎn)和動(dòng)態(tài)簇。輸出：新節(jié)點(diǎn)加入動(dòng)態(tài)簇。

//i.state為節(jié)點(diǎn)i的狀態(tài)

Foreachnodei(i?Cdyn)

Join(i,j)

//節(jié)點(diǎn)i加入動(dòng)態(tài)簇成功或構(gòu)建動(dòng)態(tài)簇

Nodeiinform neighbors in T_NET

For eachkofi’s neighbors

k.state←κ_work

//進(jìn)入κ級(jí)別工作狀態(tài)

If(Join(k,j)==0)

k.state←wait

End

10)

End

11)

End

3.3.2 失效節(jié)點(diǎn)退出動(dòng)態(tài)簇

處于工作狀態(tài)的簇內(nèi)節(jié)點(diǎn)，當(dāng)目標(biāo)移出其感知范圍，不能監(jiān)測(cè)到移動(dòng)目標(biāo)，這些節(jié)點(diǎn)退出動(dòng)態(tài)簇。

對(duì)于任意一個(gè)簇內(nèi)節(jié)點(diǎn)i，即i∈Cdyn,當(dāng)目標(biāo)移出其感知范圍，向簇頭j發(fā)送退出動(dòng)態(tài)簇的請(qǐng)求REQout。簇頭節(jié)點(diǎn)j收到請(qǐng)求后，在臨時(shí)簇成員信息表中刪除相關(guān)信息，返回同意信息ANSout。節(jié)點(diǎn)i收到同意信息后，進(jìn)入等待狀態(tài)，退出簇Cj；如果等待Δt時(shí)間后，沒(méi)有收到信息，則自動(dòng)退出簇Cj。

失效節(jié)點(diǎn)退出動(dòng)態(tài)簇算法如算法3所示。

算法3 失效節(jié)點(diǎn)退出動(dòng)態(tài)簇算法。

輸入：移動(dòng)的目標(biāo)，動(dòng)態(tài)簇Cj。輸出：失效節(jié)點(diǎn)退出動(dòng)態(tài)簇。

ForeachnodeiinCj,i∈Cdyn:

IfSi=0

SendREQoutto sink nodej

If sink nodejreceive theREQout

Delete the items ofifrom T_CM

Sink nodejsend backANSoutto nodei

End

IfnodeireceivetheANSout

Then

10)

i.state←wait

11)

Cj=Cj-i

//節(jié)點(diǎn)i退出

12)

Else

13)

WaitforΔttime

14)

Cj=Cj-i

15)

End

16)

End

17)

End

3.3.3 簇頭節(jié)點(diǎn)移交

簇頭節(jié)點(diǎn)可能因?yàn)楸O(jiān)測(cè)不到目標(biāo)而失效，使整個(gè)動(dòng)態(tài)簇失效，導(dǎo)致追蹤結(jié)束，因此，簇頭節(jié)點(diǎn)的移交是非常重要。對(duì)于目前以i為簇頭的動(dòng)態(tài)簇Ci中：

1)新加入簇的節(jié)點(diǎn)j，簇頭節(jié)點(diǎn)i查詢(xún)sink節(jié)點(diǎn)的候選簇頭信息表。如果節(jié)點(diǎn)j屬于sink候選簇頭集合，則選擇節(jié)點(diǎn)j為新的簇頭。節(jié)點(diǎn)i將所有信息移交給簇頭節(jié)點(diǎn)j，然后作為簇內(nèi)成員節(jié)點(diǎn)繼續(xù)工作。簇頭節(jié)點(diǎn)j向簇內(nèi)成員廣播簇頭信息。至此，動(dòng)態(tài)簇成為以節(jié)點(diǎn)j為簇頭的簇Cj。

2)如果節(jié)點(diǎn)j不屬于sink候選簇頭集合，則節(jié)點(diǎn)i繼續(xù)作為簇頭。同時(shí)，簇頭節(jié)點(diǎn)i將節(jié)點(diǎn)j登記到簇內(nèi)候選簇頭信息表中。當(dāng)簇頭節(jié)點(diǎn)i不能監(jiān)測(cè)到目標(biāo)時(shí)，立即查找簇內(nèi)候選簇頭信息表，選擇剩余能量Ek(0

簇頭節(jié)點(diǎn)移交算法如算法4所示。

算法4 簇頭節(jié)點(diǎn)移交算法。

輸入：移動(dòng)的目標(biāo)、動(dòng)態(tài)簇Ci。輸出：失效節(jié)點(diǎn)退出動(dòng)態(tài)簇。

/*CM為簇內(nèi)成員，CH為簇頭；T_S_CH為sink節(jié)點(diǎn)候選簇頭表；T_CM_CH為簇內(nèi)候選簇頭信息表*/

//情況1：選取新節(jié)點(diǎn)為簇頭節(jié)點(diǎn)

Instageone：

ForeachnewCMjinCi(j∈Cdyn)：

Ifj∈T_S_CH

Then

Nodejis elected to the CH

Nodeisend T_CM，T_CM_CH to nodej

Ci←Cj

//動(dòng)態(tài)簇變?yōu)镃j

10)

CHjbroadcast the message inCj

11)

Else

12)

CH record nodejto the T_CM_CH

13)

End

14)

End

15)

//情況2：選取簇內(nèi)候選簇頭里的節(jié)點(diǎn)為簇頭

16)

In stage two：

17)

IfSi=0

18)

Choose nodekfor the CH from T_CM_CH whose energy is the most

19)

Nodeisend T_CM，T_CM_CH to nodek

20)

i.state←wait

21)

Ck←Ci

//動(dòng)態(tài)簇變?yōu)镃k

22)

Ck=Ck-i

23)

CHkbroadcast the message inCk

24)

End

分簇動(dòng)態(tài)更新如圖2所示，虛線(xiàn)圈是前一個(gè)時(shí)刻的簇情況，實(shí)線(xiàn)圈是當(dāng)前時(shí)刻的簇情況。隨著目標(biāo)的移動(dòng)，節(jié)點(diǎn)1，2，3和4失效，退出了動(dòng)態(tài)簇。節(jié)點(diǎn)5加入了動(dòng)態(tài)簇，并通知一跳范圍內(nèi)的三個(gè)鄰居節(jié)點(diǎn)，進(jìn)入κ級(jí)別工作狀態(tài)。

圖2 動(dòng)態(tài)簇更新示意圖

4 基于環(huán)狀分簇的目標(biāo)追蹤技術(shù)

4.1 基于功率級(jí)別的質(zhì)心定位算法

質(zhì)心定位算法將質(zhì)心作為移動(dòng)目標(biāo)的位置，容易實(shí)現(xiàn)且成本低。但在本文的應(yīng)用場(chǎng)景中，各節(jié)點(diǎn)與目標(biāo)之間距離差異較大，節(jié)點(diǎn)能量也會(huì)影響定位精確度，針對(duì)這些問(wèn)題，在質(zhì)心定位算法上改進(jìn)，提出了基于功率級(jí)別的質(zhì)心定位算法。

定義1 質(zhì)心O(x,y)。規(guī)則多邊形的幾何中心稱(chēng)為質(zhì)心。假設(shè)一個(gè)規(guī)則多邊形的頂點(diǎn)坐標(biāo)為(x1,y1)，(x2,y2)，…，(xn,yn)，則：

(1)

定義2 內(nèi)環(huán)集合SIR(Inner Ring Set, IRS)。對(duì)于任意的節(jié)點(diǎn)i，i∈Cdyn，若節(jié)點(diǎn)i主動(dòng)監(jiān)測(cè)到移動(dòng)目標(biāo)，則i∈SIR，SIR?Cdyn。

定義3 外環(huán)集合SOR(Outer Ring Set, ORS)。對(duì)于任意的節(jié)點(diǎn)i，i∈Cdyn，若節(jié)點(diǎn)i被動(dòng)進(jìn)入工作狀態(tài)，即節(jié)點(diǎn)j通知節(jié)點(diǎn)i進(jìn)入工作狀態(tài)，j∈SIR，則i∈SOR，SOR?Cdyn。

外環(huán)節(jié)點(diǎn)的功率是內(nèi)環(huán)節(jié)點(diǎn)的功率的κ倍，由于功率的不同，內(nèi)外環(huán)節(jié)點(diǎn)的感知范圍和初始發(fā)射能量也不同。對(duì)質(zhì)心定位算法進(jìn)行改進(jìn)，結(jié)合功率因素，提出基于功率級(jí)別的質(zhì)心定位算法。公式如下：

(2)

其中：k是內(nèi)環(huán)節(jié)點(diǎn)的數(shù)目，q是外環(huán)節(jié)點(diǎn)的數(shù)目，β是內(nèi)外環(huán)節(jié)點(diǎn)的權(quán)值，由于內(nèi)環(huán)節(jié)點(diǎn)離移動(dòng)目標(biāo)更近，內(nèi)環(huán)節(jié)點(diǎn)得出的位置坐標(biāo)占有較大的權(quán)重，所以β取值范圍：1/2≤β<1。式(2)還可以進(jìn)一步簡(jiǎn)化，令α=β/(1-β)，可以得到：

基于功率級(jí)別的質(zhì)心定位(CLPL)算法如算法5所示。

算法5 基于功率級(jí)別的質(zhì)心定位算法。

輸入：內(nèi)環(huán)集合SIR，外環(huán)集合SOR，動(dòng)態(tài)簇Cdyn。輸出：目標(biāo)位置。

//CH為簇頭；μIR存放內(nèi)環(huán)集合結(jié)果； μO(píng)R存放外環(huán)集合結(jié)果；

ForeachnodeiinSIR

CHcalculateasbelow

μIRx=μIRx+xi

μIRy=μIRy+yi

k++

End

ForeachnodejinSOR

CHcalculateasbelow

10)

μO(píng)Rx=μO(píng)Rx+xj

11)

μO(píng)Ry=μO(píng)Ry+yj

12)

q++

13)

End

14)

CHgetthetarget’sposition:

//結(jié)合兩層集合，得出目標(biāo)位置

4.2 隨機(jī)性定位算法

Trace=(TS(1),TS(2),…,TS(n))

(4)

其中，TS(i)∈TSet，序列Trace是有序的，代表移動(dòng)路徑，起點(diǎn)是TS(1)，終點(diǎn)是TS(n)。

在基于功率級(jí)別定位算法中，簇頭節(jié)點(diǎn)持續(xù)性定位，不間斷計(jì)算位置信息，并傳送給sink節(jié)點(diǎn)，能耗較大。本文提出了改進(jìn)的算法——隨機(jī)性定位算法，簇頭節(jié)點(diǎn)能夠隨機(jī)性定位移動(dòng)目標(biāo)。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中存在著時(shí)空相關(guān)性[17]，可以根據(jù)目標(biāo)移動(dòng)的相關(guān)性，隨機(jī)性定位。隨機(jī)不是無(wú)規(guī)律狀態(tài)，而是隨目標(biāo)情況而定。例如某一時(shí)刻，目標(biāo)移動(dòng)緩慢，則位置信息可以默認(rèn)為上一時(shí)刻的信息，簇頭不進(jìn)行定位；而在目標(biāo)移動(dòng)較快時(shí)，簇頭開(kāi)始不間斷定位。目標(biāo)的移動(dòng)相關(guān)性可以通過(guò)動(dòng)態(tài)簇的改變獲取，動(dòng)態(tài)簇的改變體現(xiàn)在簇內(nèi)成員節(jié)點(diǎn)加入或退出。在此，給出一個(gè)動(dòng)態(tài)簇改變的狹義定義。

定義5ε-threshold簇改變。在一個(gè)時(shí)間序列T{t1,t2,…,tn}中，在Δt時(shí)間段內(nèi)，在簇頭沒(méi)有移交的情況下，有τ1個(gè)節(jié)點(diǎn)退出動(dòng)態(tài)簇，有τ2個(gè)節(jié)點(diǎn)加入動(dòng)態(tài)簇，如果τ1+τ2>ε，則認(rèn)為動(dòng)態(tài)簇改變。

根據(jù)定義5，提出隨機(jī)性定位算法如下：

1)在簇頭節(jié)點(diǎn)中定義一個(gè)計(jì)數(shù)值count，置初值為0。

2)在簇頭節(jié)點(diǎn)沒(méi)有移交情況下，有簇內(nèi)成員節(jié)點(diǎn)退出，count++；同樣，新節(jié)點(diǎn)加入動(dòng)態(tài)簇，count++。

3)如果count>ε，則認(rèn)為動(dòng)態(tài)簇改變，簇頭節(jié)點(diǎn)進(jìn)行定位計(jì)算，并將相關(guān)信息發(fā)送給sink節(jié)點(diǎn)。同時(shí)，置count為0。

4)如果簇頭節(jié)點(diǎn)進(jìn)行了移交，則動(dòng)態(tài)簇改變，新的簇頭節(jié)點(diǎn)進(jìn)行定位計(jì)算，并將相關(guān)信息發(fā)送給sink節(jié)點(diǎn)，同時(shí)，置count為0。

隨機(jī)性定位算法如算法6所示。

算法6 隨機(jī)性定位算法。

輸入：移動(dòng)的目標(biāo)，動(dòng)態(tài)簇Cdyn；給定的閾值ε；CH簇頭節(jié)點(diǎn)。輸出：目標(biāo)位置。

//計(jì)數(shù)器count

While(there is node join into theCdynor exit theCdyn)

count++

Ifcount>ε

CHexecuteCLPL

CHsendresulttosinknode

count=0

End

If CH is changed

10)

New CH execute CLPL

11)

New CH send result to sink node

12)

count=0

13)

End

14)

End

4.3 算法分析

4.3.1 能耗分析

根據(jù)能耗模型[18]，本文假設(shè)追蹤區(qū)域中節(jié)點(diǎn)的平均分布密度為ρ，則節(jié)點(diǎn)感知區(qū)域內(nèi)的節(jié)點(diǎn)個(gè)數(shù)為ρπr2。內(nèi)環(huán)節(jié)點(diǎn)在監(jiān)測(cè)目標(biāo)過(guò)程中，單位時(shí)間消耗的能量為δ；外環(huán)節(jié)點(diǎn)單位時(shí)間消耗的能量為κδ。

由于一個(gè)分簇內(nèi)，節(jié)點(diǎn)之間的距離基本上在一跳之內(nèi)，所以簇內(nèi)成員節(jié)點(diǎn)與簇頭通信的能耗基本上忽略不計(jì)。在單位時(shí)間內(nèi)，簇頭節(jié)點(diǎn)與sink節(jié)點(diǎn)通信消耗的能量為ES。

因此，每次分簇定位目標(biāo)位置所需要的總能耗為：

E=δρπr2+κδρπr2+ES

(5)

4.3.2 能耗均衡性分析

從動(dòng)態(tài)分簇和數(shù)據(jù)傳輸兩個(gè)階段分別分析能耗均衡性。

在動(dòng)態(tài)分簇階段，為了能夠?qū)σ苿?dòng)目標(biāo)進(jìn)行實(shí)時(shí)監(jiān)測(cè)，本文提出了分簇動(dòng)態(tài)更新算法。隨著目標(biāo)移動(dòng)，分簇結(jié)構(gòu)動(dòng)態(tài)更新，必然會(huì)使整個(gè)網(wǎng)絡(luò)達(dá)到良好的能耗均衡性。在網(wǎng)絡(luò)初始化過(guò)程中，為了保護(hù)低能量節(jié)點(diǎn)，sink節(jié)點(diǎn)備選了通信良好的候選簇頭，避免產(chǎn)生多余的跳距，消耗過(guò)多能量。

在數(shù)據(jù)傳輸階段，處于內(nèi)環(huán)節(jié)點(diǎn)監(jiān)測(cè)負(fù)擔(dān)比較重，能耗較高。為了均衡分簇的能量結(jié)構(gòu)，外環(huán)節(jié)點(diǎn)工作功率調(diào)為κ級(jí)別。在基于功率級(jí)別的定位算法中，外環(huán)節(jié)點(diǎn)分擔(dān)內(nèi)環(huán)監(jiān)測(cè)的任務(wù)，均衡整個(gè)分簇的能量結(jié)構(gòu)，同時(shí)擴(kuò)大了對(duì)移動(dòng)目標(biāo)的追蹤范圍，避免因目標(biāo)移動(dòng)較快而丟失的情況。

4.3.3 網(wǎng)絡(luò)延遲和監(jiān)測(cè)概率分析

目標(biāo)監(jiān)測(cè)延遲定義為在網(wǎng)絡(luò)中一個(gè)移動(dòng)目標(biāo)o從發(fā)生到被監(jiān)測(cè)到的時(shí)間長(zhǎng)度的期望值。目標(biāo)監(jiān)測(cè)概率定義為在網(wǎng)絡(luò)中一個(gè)移動(dòng)目標(biāo)o至少被一個(gè)工作節(jié)點(diǎn)監(jiān)測(cè)到的概率。

在LEACH(Low Energy Adaptive Clustering Hierarchy)協(xié)議[16]中，假設(shè)在網(wǎng)絡(luò)生命周期里，事件發(fā)生概率相等且持續(xù)時(shí)間大于(m-1)×T(T表示LEACH協(xié)議運(yùn)行一輪的時(shí)間長(zhǎng)度，m表示節(jié)點(diǎn)狀態(tài)進(jìn)行一個(gè)調(diào)度循環(huán)所經(jīng)需的輪數(shù))。若一個(gè)事件e發(fā)生在監(jiān)測(cè)區(qū)域中某點(diǎn)p，點(diǎn)p可以被s個(gè)傳感器節(jié)點(diǎn)所覆蓋。在此網(wǎng)絡(luò)場(chǎng)景下，一個(gè)事件的監(jiān)測(cè)延遲受到三個(gè)因素影響：時(shí)間長(zhǎng)度T、輪數(shù)m和覆蓋節(jié)點(diǎn)數(shù)s。如果T增大或m增加，事件平均監(jiān)測(cè)延遲也增加；相反，點(diǎn)數(shù)s增加，事件平均監(jiān)測(cè)延遲就減少。

本文提出的基于環(huán)狀分簇移動(dòng)目標(biāo)追蹤模型，與上述模型類(lèi)似。唯一區(qū)別的是，如果移動(dòng)目標(biāo)的瞬時(shí)速度v較快，分簇定位到目標(biāo)的概率較低，目標(biāo)定位的時(shí)間較長(zhǎng)。

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)環(huán)境

為了觀(guān)察基于環(huán)狀動(dòng)態(tài)分簇的目標(biāo)追蹤技術(shù)的執(zhí)行效率，本文通過(guò)Matlab仿真平臺(tái)進(jìn)行仿真實(shí)驗(yàn)。

目標(biāo)在剛進(jìn)入追蹤區(qū)域時(shí)，定位誤差會(huì)比較大，這是不可避免的情況，在實(shí)驗(yàn)仿真中，不考慮目標(biāo)進(jìn)入或退出追蹤區(qū)域的情況。假設(shè)移動(dòng)目標(biāo)是一個(gè)圓點(diǎn)，不考慮其大小。基本參數(shù)設(shè)置如表4所示。

表4 仿真參數(shù)設(shè)置

在100m×100m的二維追蹤區(qū)域內(nèi)，隨機(jī)均勻部署了100個(gè)傳感器節(jié)點(diǎn)，在追蹤區(qū)域內(nèi)，模擬目標(biāo)隨機(jī)移動(dòng)的一種路徑，軌跡方程為：

Trace(x,y,t)=

(6)

其中，參數(shù)t從0.01增至2，間隔為0.01。

5.2 實(shí)驗(yàn)結(jié)果與分析

本文從環(huán)狀分簇結(jié)構(gòu)和追蹤算法兩方面進(jìn)行實(shí)驗(yàn)仿真，環(huán)狀結(jié)構(gòu)方面包括：動(dòng)態(tài)簇與靜態(tài)簇比較、功率κ值分析及速度對(duì)追蹤的影響；追蹤算法方面包括：權(quán)值α比較與定位算法誤差。

5.2.1 動(dòng)態(tài)簇與靜態(tài)簇比較

圖3展示了本文的動(dòng)態(tài)簇模型和一種靜態(tài)簇模型——網(wǎng)格模型[19]在生存時(shí)間上對(duì)比結(jié)果。實(shí)驗(yàn)假定，當(dāng)網(wǎng)絡(luò)中能夠工作的節(jié)點(diǎn)數(shù)小于總節(jié)點(diǎn)數(shù)一半時(shí)，整個(gè)網(wǎng)絡(luò)的生命周期完結(jié)。靜態(tài)簇是一種在網(wǎng)絡(luò)運(yùn)作前選好簇頭的模型，每一個(gè)簇的地位是平等的。

由圖3可知，動(dòng)態(tài)簇模型在生存周期的長(zhǎng)度上顯然要好于靜態(tài)簇，動(dòng)態(tài)簇比靜態(tài)簇能夠節(jié)省更多的能量消耗。從圖3可以看出，在相同的追蹤區(qū)域內(nèi)，部署的節(jié)點(diǎn)越多，網(wǎng)絡(luò)的生存時(shí)間越長(zhǎng)；在相同節(jié)點(diǎn)數(shù)情況下，動(dòng)態(tài)簇的生存時(shí)間是明顯長(zhǎng)于靜態(tài)簇。與靜態(tài)簇相比，動(dòng)態(tài)簇的平均網(wǎng)絡(luò)周期延長(zhǎng)了22.73%。

5.2.2 功率κ值分析

如圖4所示，節(jié)點(diǎn)的功率級(jí)別不一樣，感知半徑也不同，那么感知覆蓋的區(qū)域也不一樣，定位的精確度也會(huì)受到影響。在κ值小于1.7時(shí)，移動(dòng)目標(biāo)的定位平均誤差隨著功率級(jí)別κ值增大而降低；在κ值大于1.7時(shí)，平均誤差隨著功率級(jí)別κ值呈增大趨勢(shì)。在κ值為1.1的時(shí)候，誤差值有個(gè)上升，這是由于外環(huán)節(jié)點(diǎn)的加入，此時(shí)，外環(huán)節(jié)點(diǎn)的數(shù)目相對(duì)于內(nèi)環(huán)節(jié)點(diǎn)來(lái)說(shuō)比較少，定位結(jié)果以?xún)?nèi)環(huán)節(jié)點(diǎn)為主導(dǎo)。隨著功率級(jí)別κ值增大，越來(lái)越多的外環(huán)節(jié)點(diǎn)加入分簇，定位結(jié)果更具有均衡性；在κ值增至1.7之后，外環(huán)節(jié)點(diǎn)的數(shù)目較多，從而起到主導(dǎo)作用，目標(biāo)定位誤差增大。

圖3 動(dòng)態(tài)簇與靜態(tài)簇生存時(shí)間

圖4 功率級(jí)別κ與追蹤誤差關(guān)系

κ值對(duì)追蹤準(zhǔn)確性有較大的影響，當(dāng)取值不合理時(shí)，誤差甚至超過(guò)1.2 m。在κ值為1時(shí)，內(nèi)外環(huán)節(jié)點(diǎn)具有相同的能量，此時(shí)的定位誤差為1.2 m，產(chǎn)生較大的誤差，對(duì)比κ值為1.7時(shí)，誤差不到0.6 m，在可接受范圍內(nèi)，可見(jiàn)κ值對(duì)定位誤差有較大影響；當(dāng)κ值超過(guò)2時(shí)，誤差超過(guò)1 m，對(duì)定位精度產(chǎn)生很大的影響。

因此，不是功率級(jí)別κ越大，移動(dòng)目標(biāo)的定位越準(zhǔn)確；但功率級(jí)別越大，分簇的結(jié)構(gòu)越大，移動(dòng)目標(biāo)的丟失率越小。

5.2.3 速度對(duì)追蹤的影響

如圖5所示，對(duì)于環(huán)狀分簇和非環(huán)狀分簇模型，當(dāng)目標(biāo)的移動(dòng)速度越大，移動(dòng)目標(biāo)追蹤的丟失率越大，準(zhǔn)確度越低。在目標(biāo)的移動(dòng)速度相等時(shí)，環(huán)狀分簇模型比非環(huán)狀分簇模型丟失率低，追蹤的準(zhǔn)確度高。當(dāng)目標(biāo)的移動(dòng)速度低于4m/s的時(shí)候，采用環(huán)狀分簇模型對(duì)移動(dòng)目標(biāo)追蹤，丟失率可以忽略不計(jì)；高于4m/s時(shí)，丟失率急劇增加。與非環(huán)狀簇相比，在速度小于4m/s時(shí)丟失率降低了61.09%，速度大于4m/s時(shí)丟失率降低了34.02%，總體平均降低了40.79%。

由此可知，基于環(huán)狀分簇的目標(biāo)追蹤算法，目標(biāo)的丟失率較低，可以減少因目標(biāo)丟失而重構(gòu)分簇帶來(lái)的能耗。

圖5 目標(biāo)移動(dòng)速度與丟失率關(guān)系

5.2.4 定位算法的誤差

圖6顯示，CLPL算法和基于接受信號(hào)強(qiáng)度值(ReceivedSignalStrengthIndicator,RSSI)定位算法[20]誤差比較。目標(biāo)在追蹤區(qū)域移動(dòng)時(shí)間為40s，分簇每秒對(duì)移動(dòng)目標(biāo)定位一次。CLPL算法得出的定位誤差，是外環(huán)節(jié)點(diǎn)為1倍功率級(jí)別的情況。最小誤差是0.2m，最大誤差是3.1m，平均誤差是1.29m。基于RSSI定位算法，最小誤差是0.8m，最大誤差是1.6m，平均誤差是1.16m。

由此可知，基于RSSI的定位算法，路徑精確度稍微高點(diǎn)，誤差值比較穩(wěn)定。但是，基于RSSI的定位算法，需要獲取詳細(xì)精確的距離與角度信息，對(duì)硬件的要求比較高。CLPL算法，對(duì)硬件要求可以忽略不計(jì)，相較于基于RSSI定位算法1.16m的誤差，1.29m的誤差也是比較樂(lè)觀(guān)的。

圖6 CLPL與RSSI目標(biāo)定位誤差

5.2.5 權(quán)值α與平均誤差分析

圖7顯示了在外環(huán)節(jié)點(diǎn)感知半徑設(shè)為9.9 m的情況下，權(quán)值α對(duì)應(yīng)移動(dòng)目標(biāo)定位的平均誤差值。如圖7所示，α值在2～2.5，移動(dòng)目標(biāo)定位的平均誤差值較小。由式(3)可知，α值較大，得到的定位結(jié)果偏向于內(nèi)環(huán)節(jié)點(diǎn)；α較小，得到的定位結(jié)果偏向于外環(huán)節(jié)點(diǎn)。當(dāng)α值為1時(shí)，內(nèi)外環(huán)節(jié)點(diǎn)具有相同的權(quán)重，此時(shí)誤差較大，接近1.4 m，可見(jiàn)不合適的α值，對(duì)定位精確度影響較大。

由此可知，α值直接影響移動(dòng)目標(biāo)的定位準(zhǔn)確度，合適的α值很重要。

5.2.6 隨機(jī)性定位算法對(duì)平均誤差的影響

圖8展示了隨機(jī)性定位算法對(duì)目標(biāo)追蹤平均誤差的影響。當(dāng)ε值為0的時(shí)候，隨機(jī)性定位算法未介入追蹤算法，此時(shí)平均誤差即為CLPL算法得出的定位誤差，為1.29 m；當(dāng)ε值大于0的時(shí)候，隨機(jī)性定位算法開(kāi)始介入追蹤算法，隨著ε值增大，平均誤差也在增大，以ε值為2為分界點(diǎn)，在之前平均誤差增大趨勢(shì)較緩，之后誤差增大趨勢(shì)較陡。

由此可知，設(shè)定合適的ε閾值，對(duì)于追蹤的影響還是比較明顯的，需尋求能耗代價(jià)與追蹤精確度的折中點(diǎn)。

圖7 權(quán)值α對(duì)應(yīng)的平均誤差

圖8 ε值與平均誤差關(guān)系

6 結(jié)語(yǔ)

本文提出雙層環(huán)狀動(dòng)態(tài)分簇的拓?fù)淠Ｐ停⒔o出了動(dòng)態(tài)分簇的更新算法，以解決目標(biāo)移動(dòng)隨機(jī)性很大和分簇的監(jiān)測(cè)任務(wù)較重等問(wèn)題。在質(zhì)心定位算法的基礎(chǔ)上，提出了基于功率級(jí)別的質(zhì)心定位算法。考慮到網(wǎng)絡(luò)的能耗問(wèn)題，對(duì)基于功率級(jí)別的質(zhì)心定位算法進(jìn)行改進(jìn)，提出了隨機(jī)性定位算法。最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了基于環(huán)狀動(dòng)態(tài)分簇的移動(dòng)目標(biāo)追蹤技術(shù)，在追蹤準(zhǔn)確度、能耗和丟失率等方面的優(yōu)勢(shì)。

References)

[1] 孫利民,李建中,陳渝,等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005:135-155.(SUN L M, LI J Z, CHEN Y, et al.Wireless Sensor Network [M].Beijing: Tsinghua University Press, 2005:135-155.)

[2] BRANCH J W, GIANNELLA C, SZYMANSKI B, et al.In-network outlier detection in wireless sensor networks [J].Knowledge and Information Systems, 2013, 34(1): 23-54.

[3] MO L, HE Y, LIU Y, et al.Canopy closure estimates with GreenOrbs: sustainable sensing in the forest [C]// Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems.New York: ACM, 2009: 99-112.

[4] HE T, KRISHNAMURTHY S, LUO L, et al.VigilNet: an integrated sensor network system for energy efficient surveillance [J].ACM Transactions on Sensor Networks, 2006, 2(1):1-38.

[5] HACKMANN G, GUO W, YAN G, et al.Cyber-physical codesign of distributed structural health monitoring with wireless sensor networks [J].IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1): 63-72.

[6] MECHITOV K, SUNDRESH S, KWON Y, et al.Cooperative tracking with binary-detection sensor networks [C]// Proceedings of the 1st International Conference on Embedded Networked Sensor Systems.New York: ACM, 2003: 332-333.

[7] KIM W, MECHITOV K, CHOI J Y, et al.On target tracking with binary proximity sensors [C]// IPSN 2005: Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks.Piscataway, NJ: IEEE, 2005: 301-308.

[8] ZHAO F, SHIN J, REICH J.Information-driven dynamic sensor collaboration for tracking applications [J].IEEE Signal Processing Magazine, 2002, 19(2): 61-72.

[9] ZHONG Z, ZHU T, WANG D, et al.Tracking with unreliable node sequences [C]// INFOCOM 2009: Proceedings of the 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies.Piscataway, NJ: IEEE, 2009: 1215-1223.

[10] WANG Z J, BULUT E, SZYMANSKI B K.Distributed energy-efficient target tracking with binary sensor networks [J].ACM Transactions on Sensor Networks, 2010, 6(4): Article No.32.

[11] KHALIL E A, ATTEA B A.Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks [J].Swarm and Evolutionary Computation, 2011, 1(4): 195-203.

[12] LIN K W, HSIEH M H, TSENG V S.A novel prediction-based strategy for object tracking in sensor networks by mining seamless temporal movement patterns [J].Expert Systems with Applications, 2010, 37(4):2799-2807.

[13] SUN K, NING P, WANG C.Secure and resilient time synchronization in wireless sensor networks [C]// Proceedings of the 13th ACM Conference on Computer and Communications Security.New York: ACM, 2006: 264-277.

[14] JEONG J, HWANG T, HE T, et al.MCTA: target tracking algorithm based on minimal contour in wireless sensor networks [C]// INFOCOM 2007: Proceedings of the 26th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies.Piscataway, NJ: IEEE, 2007: 2371-2375.

[15] VICAIRE P, HE T, CAO Q, et al.Achieving long-term surveillance in VigilNet [J].ACM Transactions on Sensor Networks, 2009, 5(1): Article No.39.

[16] TYAGI S, KUMAR N.A systematic review on clustering and routing techniques based upon LEACH protocol for wireless sensor networks [J].Journal of Network and Computer Applications, 2013, 36(2): 623-645.

[17] BROOKS R R, RAMANATHAN P, SAYEED A M.Distributed target classification and tracking in sensor networks [J].Proceedings of IEEE, 2003, 91(8):1163-1171.

[18] YANG H, SIKDAR B.A protocol for tracking mobile targets using sensor networks [C]// Proceedings of the 2003 IEEE International Workshop on Sensor Network Protocols and Applications.Piscataway, NJ: IEEE, 2003: 71-81.

[19] BULUSU N, ESTRIN D, GIROD L, et al.Scalable coordination for wireless sensor networks: self-configuring localization systems [C]// ISCTA 2001: Proceedings of the 6th International Symposium on Communication Theory and Applications.Ambleside, UK: [s.n.], 2001: 1-6.

[20] 陳維克,李文鋒,首珩,等.基于RSSI的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J].武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版),2006,30(2):265-268.(CHEN W K, LI W F, SHOU H, et al.Weighted centroid localization algorithm based on RSSI for wireless sensor networks [J].Wuhan Science University of Technology (Transportation Science and Engineering), 2006, 30(2): 265-268.)

This work is partially supported by the National Natural Science Foundation of China (U1301252), the National Science and Technology Support Program (2013BAB06B04), the Technology Project of China Huaneng Group Company Headquarters (HNKJ13-H17-04), the Science and Technology Project of Yunnan Province (2014GA007), the Special Fund for Basic Scientific Research of Central Universities (2015B22214).

BAO Wei, born in 1990, M.S.candidate.His research interests include wireless sensor network, distributed computing, parallel processing.

MAO Yingchi, born in 1976, Ph.D., associate professor.Her research interests include distributed computing and parallel processing, distributed data management.

WANG Longbao, born in 1977, lecturer.His research interests include intelligent data processing, project management.

CHEN Xiaoli, born in 1993, M.S.candidate.Her research interests include wireless sensor network, distributed computing.

Moving target tracking scheme based on dynamic clustering

BAO Wei, MAO Yingchi*, WANG Longbao, CHEN Xiaoli

(CollegeofComputerandInformation,HohaiUniversity,NanjingJiangsu211100,China)

Focused on the issues of low accuracy, high energy consumption of target tracking network and short life cycle of network in Wireless Sensor Network (WSN), the moving target tracking technology based on dynamic clustering was proposed.Firstly, a Two-Ring Dynamic Clustering (TRDC) structure and the corresponding TRDC updating methods were proposed; secondly, based on centroid localization, considering energy of node, the Centroid Localization based on Power-Level (CLPL) algorithm was proposed; finally, in order to further reduce the energy consumption of the network, the CLPL algorithm was improved, and the random localization algorithm was proposed.The simulation results indicate that compared with static cluster, the life cycle of network increased by 22.73%; compared with acyclic cluster, the loss rate decreased by 40.79%; there was a little difference from Received Signal Strength Indicator (RSSI) algorithm in accuracy.The proposed technology can effectively ensure tracking accuracy and reduce energy consumption and loss rate.

Wireless Sensor Network (WSN); two-ring clustering; target tracking; dynamic cluster; centroid localization

2016-07-20;

2016-08-05。

國(guó)家自然科學(xué)基金資助項(xiàng)目(U1301252)；國(guó)家科技支撐計(jì)劃項(xiàng)目(2013BAB06B04)；中國(guó)華能集團(tuán)公司總部科技項(xiàng)目(HNKJ13-H17-04)；云南省科技計(jì)劃項(xiàng)目(2014GA007)；中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目(2015B22214)。

包威(1990—)，男，江蘇淮安人，碩士研究生，主要研究方向：無(wú)線(xiàn)傳感器網(wǎng)絡(luò)、分布式計(jì)算、并行處理；毛鶯池(1976—)，女，上海人，副教授，博士，CCF會(huì)員，主要研究方向：分布計(jì)算與并行處理、分布式數(shù)據(jù)管理；王龍寶(1977—)，男，江蘇鹽城人，講師，主要研究方向：智能數(shù)據(jù)處理、項(xiàng)目管理；陳小麗(1993—)，女，河南洛陽(yáng)人，碩士研究生，主要研究方向：無(wú)線(xiàn)傳感器網(wǎng)絡(luò)、分布式計(jì)算。

1001-9081(2017)01-0065-08

10.11772/j.issn.1001-9081.2017.01.0065

TP393.02