沈才樑， 杜煥強(qiáng)

(1.浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州310027； 2.浙江工業(yè)職業(yè)技術(shù)學(xué)院 設(shè)計(jì)與藝術(shù)分院， 浙江 紹興 312000)

計(jì)算與測(cè)試

基于概率閾值通信感知的WSNs目標(biāo)跟蹤算法*

沈才樑1,2， 杜煥強(qiáng)2

(1.浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州310027； 2.浙江工業(yè)職業(yè)技術(shù)學(xué)院 設(shè)計(jì)與藝術(shù)分院， 浙江 紹興 312000)

針對(duì)移動(dòng)Sink節(jié)點(diǎn)目標(biāo)跟蹤定位時(shí)間長(zhǎng)，能耗大等問題，提出基于概率閾值通信感知的WSNs目標(biāo)跟蹤算法。采用離散數(shù)據(jù)傳輸方式，并定義目標(biāo)信息傳輸概率閾值來確定是否將節(jié)點(diǎn)當(dāng)前位置信息由傳感器節(jié)點(diǎn)傳輸?shù)絊ink節(jié)點(diǎn)。若當(dāng)前位置信息不傳輸?shù)絊ink節(jié)點(diǎn)中，則使用最近一次通報(bào)的目標(biāo)位置信息進(jìn)行目標(biāo)定位。然后開啟目標(biāo)周圍相關(guān)傳感器節(jié)點(diǎn)來有效降低算法數(shù)據(jù)傳輸量，并保持足夠的定位精度。仿真結(jié)果顯示：該方法比預(yù)測(cè)跟蹤算法降低數(shù)據(jù)傳輸量87 %左右，比動(dòng)態(tài)目標(biāo)跟蹤算法降低跟蹤時(shí)間33.7 %左右。

概率閾值； 通信感知； 無線傳感器網(wǎng)絡(luò)； 目標(biāo)跟蹤； 能耗節(jié)省

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)常用作目標(biāo)探測(cè)，如戰(zhàn)場(chǎng)監(jiān)測(cè)，野生動(dòng)物監(jiān)測(cè)等[1,2]。移動(dòng)Sink節(jié)點(diǎn)跟蹤目標(biāo)是最小化跟蹤時(shí)間和數(shù)據(jù)傳輸消耗[3～4]。傳統(tǒng)方法多基于連續(xù)時(shí)域，此方法會(huì)短期內(nèi)消耗大量能量，降低網(wǎng)絡(luò)壽命[5～6]。

目前，僅有較少文獻(xiàn)對(duì)移動(dòng)Sink節(jié)點(diǎn)WSNs定位進(jìn)行研究，如 Kosut O等人[7]以目標(biāo)二維晶格隨機(jī)游走方式，大幅降低數(shù)據(jù)傳輸量，但由于數(shù)據(jù)溝通不及時(shí)，存在Sink節(jié)點(diǎn)移動(dòng)的盲目性。Tsai H W等人[8]提出更加復(fù)雜的定位跟蹤模型，首先目標(biāo)節(jié)點(diǎn)位置信息被傳遞到信標(biāo)節(jié)點(diǎn)處，然后引導(dǎo)Sink節(jié)點(diǎn)移向目標(biāo)。文獻(xiàn)[9]中也提出類似方法，并且考慮了目標(biāo)速度和方向變化，但模型過于復(fù)雜，反而不利于節(jié)省能耗。

為進(jìn)一步提高算法性能，在啟發(fā)式優(yōu)化規(guī)則[10]和不確定性方法[11]基礎(chǔ)上，結(jié)合預(yù)測(cè)跟蹤方法[12]，本文提出一種基于概率閾值通信感知的WSNs目標(biāo)跟蹤(PTCP-WSNs)算法，通過僅開啟能探測(cè)預(yù)測(cè)目標(biāo)位置的傳感器節(jié)點(diǎn)，在根本上降低能耗。

1 PTCP-WSNs算法

1.1 算法描述

該算法基于離散時(shí)間序列，目標(biāo)和Sink節(jié)點(diǎn)各自向某個(gè)方向移動(dòng)，最大移動(dòng)速度vmax已知，目標(biāo)運(yùn)動(dòng)方向隨機(jī)，Sink節(jié)點(diǎn)移動(dòng)方向根據(jù)WSNs信息確定。在每個(gè)時(shí)段內(nèi)，Sink節(jié)點(diǎn)可到達(dá)位置(xS,yS)滿足速度約束

(1)

d[(xS,yS),(xD,yD)]=min,

(2)

令(xC,yC)為當(dāng)前探測(cè)目標(biāo)位置，由于僅在特定時(shí)段才將目標(biāo)信息傳遞到Sink節(jié)點(diǎn)，因此，若在坐標(biāo)(xD,yD)更新時(shí)，信息被傳送，那么,(xD,yD)=(xC,yC)。而其他情況下，Sink節(jié)點(diǎn)移向坐標(biāo)(xD,yD)，此時(shí),(xD,yD)≠(xC,yC)。令dir(x,y)為Sink節(jié)點(diǎn)移向(x,y)的方向，P[dir]為Sink節(jié)點(diǎn)移向該方向時(shí)與最近通報(bào)目標(biāo)位置(xD,yD)距離減小概率。給定條件

P[dir(xC,yC)]-P[dir(xD,yD)]≥threshold.

(3)

若滿足條件，坐標(biāo)(xC,yC)傳入Sink節(jié)點(diǎn)，并計(jì)算P[dir]，給出目標(biāo)可能出現(xiàn)位置

A={(x,y):tT(x,y)≤tS(x,y)},

(4)

式中tT(x,y)為目標(biāo)移向(x,y)最短時(shí)間，tS(x,y)為Sink節(jié)點(diǎn)移向(x,y)最短時(shí)間。

令(xS,yS)C,(xS,yS)D為Sink節(jié)點(diǎn)下一刻分別沿dir(xC,yC),dir(xD,yD) 進(jìn)入的區(qū)段。區(qū)域A可定義兩子集：AC為與(xS,yS)C更近區(qū)域，AD為與(xS,yS)D更近區(qū)域,可表示為

(5)

則概率值P[dir]的計(jì)算公式為

(6)

如圖1，目標(biāo)和Sink節(jié)點(diǎn)分別為“T”和“S”。目標(biāo)速度1格/每時(shí)段，Sink節(jié)點(diǎn)速度2格/每時(shí)段?；疑珵镾ink節(jié)點(diǎn)可跟蹤區(qū)域 。方向箭頭1為dir(xC,yC)，方向箭頭2為dir(xD,yD)，則Sink節(jié)點(diǎn)分別沿方向1，2的下一時(shí)刻坐標(biāo)為

(7)

圖1中，灰色1區(qū)域?yàn)樽蛹疉C，灰色2區(qū)域?yàn)樽蛹疉D,則在該圖例中，|A|=26,|AC|=11，|AD|=10。根據(jù)公式(6)可得P[dir(xC,yC)]=0.42，P[dir(xD,yD)]=0.38。

圖1 概率值算例

1.2 對(duì)比算法選取與設(shè)計(jì)

預(yù)測(cè)跟蹤算法[12]和動(dòng)態(tài)目標(biāo)跟蹤算法[13]是控制移動(dòng)Sink節(jié)點(diǎn)移向移動(dòng)目標(biāo)較有效的控制策略，選取作為對(duì)比算法。跟蹤操作偽代碼與傳輸條件如表1所示。

表1 對(duì)比算法

(8)

預(yù)測(cè)跟蹤算法目標(biāo)位置信息在每個(gè)時(shí)段都會(huì)傳遞給Sink節(jié)點(diǎn)，這種方式存在問題是數(shù)據(jù)傳輸量大。動(dòng)態(tài)目標(biāo)跟蹤算法中，Sink節(jié)點(diǎn)會(huì)移向信標(biāo)節(jié)點(diǎn)(xD,yD)，并將當(dāng)前探測(cè)到的目標(biāo)位置(xC,yC)設(shè)為新信標(biāo)節(jié)點(diǎn)，此方式數(shù)據(jù)傳輸量相比預(yù)測(cè)算法小。

2 仿真實(shí)驗(yàn)與分析

2.1 模擬環(huán)境實(shí)驗(yàn)

仿真區(qū)域?yàn)?00m×100m方形區(qū)域，在1m×1m小方格中設(shè)置1只無線傳感器，則共有10 000只無線傳感器，每個(gè)傳感器可達(dá)覆蓋周圍4個(gè)方格。目標(biāo)速度1方格/每時(shí)段，Sink節(jié)點(diǎn)速度2方格/每時(shí)段。基于9個(gè)隨機(jī)目標(biāo)，如圖2。Sink節(jié)點(diǎn)初始位置(5，5)m，目標(biāo)初始位置(50,50)m。選取信息傳輸最短路徑來計(jì)算跳數(shù)(hop)。

選取跟蹤時(shí)間和hop數(shù)為評(píng)價(jià)指標(biāo)，概率閾值范圍threshold∈[0,0.9]，如圖3所示。

圖3 仿真對(duì)比數(shù)據(jù)

圖3可看出:本文算法在平均hop數(shù)和跟蹤時(shí)間上均優(yōu)于對(duì)比算法，并且圖中給出了概率閾值變化對(duì)評(píng)價(jià)指標(biāo)影響情況：隨概率閾值增大，算法平均hop數(shù)先減小，后達(dá)到飽和，而平均跟蹤時(shí)間先不變，在達(dá)到觸發(fā)點(diǎn)后(threshold≈0.3)，隨著概率閾值增大而增大。與預(yù)測(cè)跟蹤算法相比，動(dòng)態(tài)目標(biāo)跟蹤算法能夠降低平均hop數(shù)87 %左右，而本文算法在threshold=0.2時(shí)，平均hop數(shù)也相比降低87 %左右，但動(dòng)態(tài)目標(biāo)跟蹤算法所需跟蹤時(shí)間要高出預(yù)測(cè)跟蹤算法52 %左右。總體上，在threshold∈[0,0.9]范圍內(nèi)，本文算法在上述兩個(gè)指標(biāo)均要明顯優(yōu)于所對(duì)比算法。

圖4(a),(b)分別給出各算法在隨機(jī)移動(dòng)目標(biāo)中的跟蹤時(shí)間和hop數(shù)分布情況。根據(jù)圖3仿真結(jié)果，選取概率閾值為threshold=0.2，從圖中可看出:本文算法的hop數(shù)都是最少的，和動(dòng)態(tài)目標(biāo)跟蹤算法所需hop數(shù)基本一致，而所需跟蹤時(shí)間與預(yù)測(cè)跟蹤算法近似，互有高低。這說明本文算法在有效降低通信消耗的前提下，并未增加跟蹤算法的執(zhí)行時(shí)間，相比對(duì)比算法優(yōu)勢(shì)明顯。

圖4 各目標(biāo)仿真結(jié)果

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

考慮到成本等因素(共需10 000只傳感器)，上述實(shí)驗(yàn)是模擬實(shí)現(xiàn)的，為對(duì)比少量節(jié)點(diǎn)網(wǎng)絡(luò)和實(shí)際環(huán)境條件下的目標(biāo)跟蹤結(jié)果，構(gòu)建實(shí)際仿真環(huán)境如圖5所示。

圖5 實(shí)驗(yàn)環(huán)境構(gòu)建

表2 評(píng)價(jià)指標(biāo)對(duì)比數(shù)據(jù)

從表2可看出:本文算法在平均跟蹤時(shí)間上，略差于預(yù)測(cè)跟蹤算法，而在平均hop數(shù)上略差于動(dòng)態(tài)目標(biāo)跟蹤算法，但差距不明顯。在少量節(jié)點(diǎn)情況下，本文算法的平均跟蹤時(shí)間相比動(dòng)態(tài)目標(biāo)跟蹤算法降低39 %左右，而平均hop數(shù)相比預(yù)測(cè)跟蹤算法降低77 %左右，因此，本文算法在綜合評(píng)價(jià)指標(biāo)全面性上要好于對(duì)比算法。圖6給出本文算法在實(shí)際環(huán)境下的跟蹤路線，圖中點(diǎn)畫線為目標(biāo)移動(dòng)軌跡，實(shí)線(圖中抖動(dòng)曲線)為Sink節(jié)點(diǎn)移動(dòng)軌跡，跟蹤軌跡抖動(dòng)是由小車的晃動(dòng)引起的。從圖中可看出:Sink節(jié)點(diǎn)能夠快速有效地跟蹤到目標(biāo)軌跡，從而驗(yàn)證了算法有效性。

圖6 移動(dòng)Sink節(jié)點(diǎn)跟蹤軌跡

3 結(jié)束語

本文提出一種基于概率閾值通信感知的WSNs目標(biāo)跟蹤算法，通過目標(biāo)信息傳輸概率閾值，來確定Sink節(jié)點(diǎn)開啟的目標(biāo)位置傳感器，以此來降低開啟傳感器數(shù)量和降低數(shù)據(jù)傳輸量，有效解決了移動(dòng)Sink節(jié)點(diǎn)目標(biāo)跟蹤定位時(shí)間過長(zhǎng)，能耗較大的問題。由于實(shí)驗(yàn)條件所限，僅實(shí)現(xiàn)少量無線傳感器條件下的實(shí)際環(huán)境測(cè)試。

WSNs target tracking algorithm based on probability

threshold communication perception*SHEN Cai-liang1,2, DU Huan-qiang2

(1.School of Computer Science and Technology,Zhejiang University,Hangzhou 310027,China; 2.Department of Design and Art,Zhejiang Industry Polytechnic College,Shaoxing 312000,China)

Aiming at problem of long time of target tracking and localization and high energy consumption of mobile sink node,WSNs target tracking algorithm based on probability threshold communication perception is proposed.Adopt discrete data transmission mode,and define probability threshold of target information transmission to determine whether transmit current location information of node from sensor nodes to sink node or not.If current position information is not transmitted to the Sink node,the recent notification of target positioning information is used.Then the related wireless sensor nodes around the target are opened,through this way the amount of data transmission is reduced,and sufficient positioning precision is maintained.The simulation results show that,the method can reduce data transmission quantity about 87 %,compared with the forecast tracking algorithm,and reduce the tracking time about 33.7 %,compared with the dynamic target tracking algorithm.

probability threshold; communication perception; wireless sensor networks(WSNs); target tracking; energy saving

2015—01—15

國家自然科學(xué)基金資助項(xiàng)目(60970076)

10.13873/J.1000—9787(2015)04—0111—04

TP 212

A

1000—9787(2015)04—0111—04

沈才樑(1973-)，男，浙江紹興人，碩士，教授，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、無線信息安全。