基于概率閾值通信感知的WSNs目標跟蹤算法*

沈才樑， 杜煥強

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

計算與測試

基于概率閾值通信感知的WSNs目標跟蹤算法*

沈才樑1,2， 杜煥強2

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

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

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

0 引 言

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

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

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

1 PTCP-WSNs算法

1.1 算法描述

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

(1)

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

(2)

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

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

(3)

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

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

(4)

式中tT(x,y)為目標移向(x,y)最短時間，tS(x,y)為Sink節(jié)點移向(x,y)最短時間。

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

(5)

則概率值P[dir]的計算公式為

(6)

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

(7)

圖1中，灰色1區(qū)域為子集AC，灰色2區(qū)域為子集AD,則在該圖例中，|A|=26,|AC|=11，|AD|=10。根據(jù)公式(6)可得P[dir(xC,yC)]=0.42，P[dir(xD,yD)]=0.38。

圖1 概率值算例

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

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

表1 對比算法

(8)

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

2 仿真實驗與分析

2.1 模擬環(huán)境實驗

仿真區(qū)域為100m×100m方形區(qū)域，在1m×1m小方格中設(shè)置1只無線傳感器，則共有10 000只無線傳感器，每個傳感器可達覆蓋周圍4個方格。目標速度1方格/每時段，Sink節(jié)點速度2方格/每時段?；?個隨機目標，如圖2。Sink節(jié)點初始位置(5，5)m，目標初始位置(50,50)m。選取信息傳輸最短路徑來計算跳數(shù)(hop)。

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

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

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

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

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

2.2 真實環(huán)境實驗

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

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

表2 評價指標對比數(shù)據(jù)

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

圖6 移動Sink節(jié)點跟蹤軌跡

3 結(jié)束語

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

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

國家自然科學基金資助項目(60970076)

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

TP 212

A

1000—9787(2015)04—0111—04

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