無(wú)線傳感器網(wǎng)絡(luò)基于2階段聚合的目標(biāo)跟蹤算法

任倩倩 劉紅陽(yáng) 劉 勇 李金寶 王 楠

(黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 哈爾濱 150080) (黑龍江省數(shù)據(jù)庫(kù)與并行計(jì)算重點(diǎn)實(shí)驗(yàn)室(黑龍江大學(xué)) 哈爾濱 150080)

無(wú)線傳感器網(wǎng)絡(luò)基于2階段聚合的目標(biāo)跟蹤算法

任倩倩 劉紅陽(yáng) 劉 勇 李金寶 王 楠

(黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 哈爾濱 150080) (黑龍江省數(shù)據(jù)庫(kù)與并行計(jì)算重點(diǎn)實(shí)驗(yàn)室(黑龍江大學(xué)) 哈爾濱 150080)

(renqianqian@hlju.edu.cn)

研究無(wú)線傳感器網(wǎng)絡(luò)中能量有效的移動(dòng)目標(biāo)跟蹤問(wèn)題.1)定義了一個(gè)基于網(wǎng)格的網(wǎng)絡(luò)模型，該模型使處于網(wǎng)格頂點(diǎn)附近的節(jié)點(diǎn)工作、其他節(jié)點(diǎn)睡眠以節(jié)省能量,同時(shí)保證跟蹤質(zhì)量.2)分析了目標(biāo)出現(xiàn)位置與網(wǎng)格單元的關(guān)系，針對(duì)每種位置關(guān)系給出了一個(gè)通用的定位算法.在此基礎(chǔ)上，設(shè)計(jì)了一個(gè)基于2階段聚合的目標(biāo)定位算法，對(duì)單個(gè)網(wǎng)格內(nèi)定位結(jié)果進(jìn)行優(yōu)化.3)提出了一個(gè)基于順逆時(shí)針機(jī)制的最短路徑選擇算法傳輸目標(biāo)定位的結(jié)果，保證最小化參與傳輸?shù)墓?jié)點(diǎn)數(shù)目.4)通過(guò)大量實(shí)驗(yàn)驗(yàn)證了所提出算法在能源節(jié)省和跟蹤質(zhì)量方面的有效性.

移動(dòng)目標(biāo)跟蹤；聚合；網(wǎng)格；定位；時(shí)鐘規(guī)則

無(wú)線傳感器網(wǎng)絡(luò)在人們?nèi)粘Ｉ钪邪缪葜豢苫蛉钡慕巧鼜V泛地應(yīng)用于戰(zhàn)場(chǎng)監(jiān)測(cè)、生態(tài)環(huán)境監(jiān)測(cè)、災(zāi)難預(yù)測(cè)和智能交通等諸多領(lǐng)域[1-2].在傳感器網(wǎng)絡(luò)的諸多應(yīng)用中，移動(dòng)目標(biāo)跟蹤都是一項(xiàng)基本功能.在監(jiān)測(cè)戰(zhàn)場(chǎng)上敵軍車輛運(yùn)動(dòng)軌跡、野生動(dòng)物生活習(xí)性、森林火災(zāi)的蔓延程度，以及高速公路上車輛的運(yùn)行狀態(tài)等應(yīng)用中都需要用到目標(biāo)跟蹤功能[3-4].然而，傳感器網(wǎng)絡(luò)能量供應(yīng)有限的特性使得基于傳感器網(wǎng)絡(luò)的目標(biāo)跟蹤研究面臨著許多挑戰(zhàn).基于移動(dòng)目標(biāo)跟蹤的應(yīng)用往往需要網(wǎng)絡(luò)持續(xù)工作，為了盡量延長(zhǎng)傳感器網(wǎng)絡(luò)的工作時(shí)間，節(jié)省并平衡節(jié)點(diǎn)能耗，最大化網(wǎng)絡(luò)生命周期是一個(gè)關(guān)鍵問(wèn)題.許多文獻(xiàn)介紹了一系列能源有效的方法來(lái)減少傳感器網(wǎng)絡(luò)的能源消耗[5-7].在這些方法中，使節(jié)點(diǎn)輪流工作是一個(gè)有效的方法.其核心思想是在給定的時(shí)間內(nèi)，使小部分節(jié)點(diǎn)工作而其他節(jié)點(diǎn)睡眠.

在目標(biāo)跟蹤的過(guò)程中，保證目標(biāo)周圍的節(jié)點(diǎn)工作而其他節(jié)點(diǎn)睡眠是一種直觀有效的節(jié)能方式，然而目標(biāo)運(yùn)動(dòng)軌跡的隨意性使得很難事先獲得目標(biāo)位置信息從而確定工作節(jié)點(diǎn).本文在目標(biāo)跟蹤的過(guò)程中引入了節(jié)點(diǎn)睡眠調(diào)度機(jī)制，所提方法不需要通過(guò)預(yù)測(cè)目標(biāo)位置確定工作節(jié)點(diǎn)，而是構(gòu)建了一個(gè)基于網(wǎng)格的網(wǎng)絡(luò)模型.該模型使處于網(wǎng)格頂點(diǎn)的節(jié)點(diǎn)工作、其他的節(jié)點(diǎn)進(jìn)入睡眠狀態(tài).為了平衡節(jié)點(diǎn)能耗，可以周期性重新構(gòu)建網(wǎng)格，使網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)輪流成為網(wǎng)格頂點(diǎn).網(wǎng)格的尺寸設(shè)計(jì)保證目標(biāo)在網(wǎng)格的任意位置都有足夠節(jié)點(diǎn)為目標(biāo)定位.考慮到目標(biāo)可能出現(xiàn)在單個(gè)網(wǎng)格單元內(nèi)或2個(gè)網(wǎng)格單元公共邊上，本文系統(tǒng)分析了目標(biāo)與網(wǎng)格單元的位置情況，給出了通用的定位算法.針對(duì)目標(biāo)處于網(wǎng)格單元公共邊上定位的情況，本文對(duì)算法進(jìn)行優(yōu)化，設(shè)計(jì)了一個(gè)基于2階段聚合的定位方法，以緩解每個(gè)網(wǎng)格單元內(nèi)的部分定位結(jié)果誤差對(duì)整體定位結(jié)果的影響.為了及時(shí)有效地傳輸定位結(jié)果，本文設(shè)計(jì)了一個(gè)基于順逆時(shí)針的最短路徑選擇機(jī)制，該方法可以與目標(biāo)跟蹤過(guò)程相結(jié)合，不需要較多的額外工作量，同時(shí)最小化參與路由的節(jié)點(diǎn)數(shù)目.

本文的主要貢獻(xiàn)有4點(diǎn)：1)構(gòu)建了一個(gè)基于網(wǎng)格的網(wǎng)絡(luò)模型，在目標(biāo)跟蹤的過(guò)程中引入睡眠調(diào)度機(jī)制；2)設(shè)計(jì)了一個(gè)基于2階段聚合的移動(dòng)目標(biāo)跟蹤算法，分析目標(biāo)在網(wǎng)格內(nèi)出現(xiàn)的各種情況，給出了通用的目標(biāo)定位算法，并采用聚合方法對(duì)定位結(jié)果進(jìn)行優(yōu)化；3)設(shè)計(jì)了一個(gè)基于順逆時(shí)針的轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇策略，在網(wǎng)格中使用最短路徑選擇機(jī)制傳輸目標(biāo)定位的結(jié)果到Sink；4)搭建了一個(gè)大規(guī)模的實(shí)驗(yàn)室環(huán)境模擬平臺(tái)，驗(yàn)證了所提出算法的有效性，并與其他優(yōu)秀目標(biāo)跟蹤算法進(jìn)行比較.

1 相關(guān)工作

在傳感器網(wǎng)絡(luò)中，移動(dòng)目標(biāo)跟蹤技術(shù)已經(jīng)有了廣泛的研究[7-18].下面將簡(jiǎn)單地介紹與本文最相關(guān)的工作.

文獻(xiàn)[7]定義了一個(gè)基于覆蓋率模型的“覆蓋范圍”定義，在此基礎(chǔ)上該文給出2個(gè)劃分傳感器節(jié)點(diǎn)的方法，使得劃分后的節(jié)點(diǎn)滿足覆蓋集條件，并且采用覆蓋集中的節(jié)點(diǎn)輪流工作方式以達(dá)到最大化系統(tǒng)壽命的目的.文獻(xiàn)[12]提出了一個(gè)2層的數(shù)據(jù)傳輸模型，此模型適用于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)和多個(gè)移動(dòng)Sink的場(chǎng)景中.隨著目標(biāo)的每次運(yùn)動(dòng)，模型將建立1個(gè)新的網(wǎng)格實(shí)施目標(biāo)跟蹤和信息傳輸.該機(jī)制能夠平衡網(wǎng)絡(luò)中能量負(fù)載，然而維護(hù)網(wǎng)絡(luò)拓?fù)湫枰馁M(fèi)一定的能量.文獻(xiàn)[13]提出了一個(gè)基于2層網(wǎng)格的移動(dòng)目標(biāo)定位方法.該方法簡(jiǎn)單又節(jié)省能量，然而該文并沒(méi)有給出目標(biāo)監(jiān)測(cè)數(shù)據(jù)的收集方法和數(shù)據(jù)傳輸方法.

MCTA給出了一個(gè)最小輪廓跟蹤算法，在最小化工作節(jié)點(diǎn)數(shù)量的同時(shí)，保證目標(biāo)跟蹤的質(zhì)量[14].文獻(xiàn)[15]在目標(biāo)跟蹤過(guò)程中使用節(jié)點(diǎn)選擇方法，選擇最有利的節(jié)點(diǎn)參與跟蹤.文獻(xiàn)[16]設(shè)計(jì)了一個(gè)協(xié)作信號(hào)處理機(jī)制跟蹤目標(biāo)，其主要思想是使用被監(jiān)測(cè)區(qū)域內(nèi)4個(gè)網(wǎng)格中被激活的節(jié)點(diǎn)監(jiān)測(cè)目標(biāo)，并且這些節(jié)點(diǎn)發(fā)送傳感數(shù)據(jù)給管理節(jié)點(diǎn)，管理節(jié)點(diǎn)負(fù)責(zé)定位目標(biāo)并且預(yù)測(cè)目標(biāo)未來(lái)的位置.

文獻(xiàn)[17]提出了一個(gè)基于預(yù)測(cè)的能量有效的目標(biāo)跟蹤算法，首先預(yù)測(cè)目標(biāo)的軌跡以及目標(biāo)即將出現(xiàn)的位置，然后激活網(wǎng)絡(luò)中的這部分節(jié)點(diǎn)用于目標(biāo)跟蹤，同時(shí)保持其他節(jié)點(diǎn)睡眠以節(jié)省節(jié)點(diǎn)的能量.文獻(xiàn)[18]提出了一個(gè)適用于分布式傳感器網(wǎng)絡(luò)定位的融合機(jī)制.該機(jī)制首先將網(wǎng)絡(luò)分為若干個(gè)小的子網(wǎng)，每個(gè)子網(wǎng)盡可能地在自己區(qū)域內(nèi)定位目標(biāo).該機(jī)制不參考全局坐標(biāo)基準(zhǔn)，因此計(jì)算復(fù)雜度較低.

上述方法都考慮了在移動(dòng)目標(biāo)跟蹤的過(guò)程中節(jié)省能量，使節(jié)點(diǎn)輪流工作是一個(gè)非常有效的節(jié)能方法.然而目標(biāo)軌跡具有一定的隨機(jī)性，因此很難提前預(yù)測(cè)出目標(biāo)即將出現(xiàn)的區(qū)域，從而確定參與工作節(jié)點(diǎn).本文采用基于網(wǎng)格的睡眠調(diào)度機(jī)制，該機(jī)制在網(wǎng)絡(luò)中構(gòu)建網(wǎng)格模型，使處于網(wǎng)格頂點(diǎn)附近的節(jié)點(diǎn)工作而其他的節(jié)點(diǎn)睡眠來(lái)節(jié)省能量，從而避免預(yù)測(cè)目標(biāo)軌跡.網(wǎng)格的設(shè)計(jì)保證目標(biāo)在任意位置都能夠有工作的節(jié)點(diǎn)監(jiān)測(cè)到，并且工作的節(jié)點(diǎn)數(shù)目盡量小.

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

Fig. 1 An example of network model圖1 網(wǎng)絡(luò)模型的一個(gè)示例

2.2 感知模型

當(dāng)跟蹤目標(biāo)出現(xiàn)在傳感器網(wǎng)絡(luò)的監(jiān)測(cè)區(qū)域內(nèi)，位于目標(biāo)周圍的傳感器節(jié)點(diǎn)會(huì)產(chǎn)生感知數(shù)據(jù).用di表示傳感器節(jié)點(diǎn)i與跟蹤目標(biāo)的距離(1≤i≤N,N為網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)個(gè)數(shù)).用“1”表示節(jié)點(diǎn)i作出“監(jiān)測(cè)到跟蹤目標(biāo)”的決策，而“0”表示節(jié)點(diǎn)i作出“未監(jiān)測(cè)到跟蹤目標(biāo)”的決策.由于網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)獨(dú)立作出決策，因此傳感器節(jié)點(diǎn)i的決策si可以表示為

(1)

作出決策為“1”的節(jié)點(diǎn)進(jìn)一步向其管理節(jié)點(diǎn)傳送信息，第3節(jié)將詳細(xì)說(shuō)明.

3 基于2階段聚合的移動(dòng)目標(biāo)跟蹤算法

本文將給出目標(biāo)跟蹤算法的詳細(xì)設(shè)計(jì).根據(jù)目標(biāo)在網(wǎng)格內(nèi)出現(xiàn)的位置，分3種情況進(jìn)行討論，即目標(biāo)出現(xiàn)在1個(gè)網(wǎng)格單元內(nèi)部、目標(biāo)出現(xiàn)在2個(gè)網(wǎng)格單元的公共邊上和目標(biāo)出現(xiàn)在網(wǎng)格單元頂角附近.

定義1. 跟蹤管理節(jié)點(diǎn).即參與本次移動(dòng)目標(biāo)定位的管理節(jié)點(diǎn).

3.1 預(yù)備知識(shí)

當(dāng)目標(biāo)進(jìn)入網(wǎng)絡(luò)的時(shí)候，它可能出現(xiàn)在網(wǎng)絡(luò)的任意位置.即目標(biāo)可能出現(xiàn)在一個(gè)網(wǎng)格單元內(nèi)部，或者出現(xiàn)在相鄰2個(gè)網(wǎng)格單元的公共邊上(目標(biāo)位于4個(gè)網(wǎng)格單元的公共邊的情況也包含在內(nèi))，如圖2所示.目標(biāo)出現(xiàn)在網(wǎng)絡(luò)的不同位置，使得監(jiān)測(cè)到目標(biāo)的節(jié)點(diǎn)的數(shù)目不同.在下面篇幅中，我們將討論目標(biāo)位置和監(jiān)測(cè)到目標(biāo)節(jié)點(diǎn)數(shù)目的關(guān)系.

Fig. 2 Target location examples in different cases圖2 不同情況下的目標(biāo)位置示例

定理1. 如果目標(biāo)只被4個(gè)邊界節(jié)點(diǎn)監(jiān)測(cè)到，那么這些邊界節(jié)點(diǎn)是同一個(gè)網(wǎng)格單元的4個(gè)邊界點(diǎn).

證明. 由于目標(biāo)只能位于網(wǎng)格單元內(nèi)，或者位于2個(gè)網(wǎng)格單元的公共邊上，我們將分別針對(duì)每種情形給出此定理的證明.

情形1. 目標(biāo)位于1個(gè)網(wǎng)格單元內(nèi)部，如圖2(a)所示.根據(jù)感知范圍的定義，目標(biāo)所在網(wǎng)格單元內(nèi)的4個(gè)邊界節(jié)點(diǎn)一定能夠監(jiān)測(cè)到目標(biāo).

情形2. 目標(biāo)不位于1個(gè)網(wǎng)格單元內(nèi)部，則目標(biāo)位于2個(gè)網(wǎng)格單元的公共邊上，如圖2(b)(c)所示.目標(biāo)所在公共邊上的2個(gè)節(jié)點(diǎn)一定可以監(jiān)測(cè)到目標(biāo).1條公共邊連接2個(gè)網(wǎng)格單元，根據(jù)節(jié)點(diǎn)感知范圍定義可知這2個(gè)網(wǎng)格單元內(nèi)的剩余4個(gè)邊界節(jié)點(diǎn)也可以監(jiān)測(cè)到目標(biāo).此時(shí)監(jiān)測(cè)到目標(biāo)的節(jié)點(diǎn)數(shù)目為6，這與假設(shè)目標(biāo)只被4個(gè)邊界節(jié)點(diǎn)監(jiān)測(cè)到矛盾.所以情形2不滿足定理?xiàng)l件.

證畢.

定理2. 如果監(jiān)測(cè)到目標(biāo)的節(jié)點(diǎn)數(shù)目超過(guò)4個(gè)，那么這些節(jié)點(diǎn)一定來(lái)自于多個(gè)(2個(gè)或2個(gè)以上)網(wǎng)格單元.

證明. 因?yàn)?個(gè)網(wǎng)格單元只有4個(gè)邊界節(jié)點(diǎn)，此定理顯然正確.

證畢.

定理3. 目標(biāo)位于2個(gè)網(wǎng)格單元公共邊上，并且距離此邊上任意節(jié)點(diǎn)A的距離滿足如下條件：

(2)

則目標(biāo)能夠被6個(gè)節(jié)點(diǎn)監(jiān)測(cè)到.

證明. 使用反證法來(lái)證明.

假設(shè)滿足式(2)的條件，那么此公共邊連接的2個(gè)網(wǎng)格內(nèi)所有邊界節(jié)點(diǎn)(如圖2(b)所示總計(jì)6個(gè)節(jié)點(diǎn))都能夠監(jiān)測(cè)到目標(biāo).假定另外有一個(gè)最近的節(jié)點(diǎn)C能夠監(jiān)測(cè)到目標(biāo)，則節(jié)點(diǎn)C和跟蹤目標(biāo)的距離可定義為

distance(C,target)=distance(C,A)+

(3)

根據(jù)假設(shè)有：

(4)

推導(dǎo)得到：

(5)

證畢.

定理4. 目標(biāo)位于2個(gè)網(wǎng)格單元公共邊上，并且距離此邊上任意節(jié)點(diǎn)A的距離滿足如下條件：

(6)

或者

(7)

則監(jiān)測(cè)到目標(biāo)的節(jié)點(diǎn)數(shù)量是7.

證明. 首先考慮式(6)的情況.此時(shí)假定距離目標(biāo)較近的節(jié)點(diǎn)C能夠監(jiān)測(cè)到目標(biāo)(如圖2(c))，那么節(jié)點(diǎn)C到目標(biāo)的距離滿足：

distance(C,target)≤distance(C,A)+

(8)

進(jìn)一步假設(shè)距離目標(biāo)較遠(yuǎn)的節(jié)點(diǎn)D和節(jié)點(diǎn)E也能夠監(jiān)測(cè)到目標(biāo)(如圖2(c))，它們到目標(biāo)的距離分別為

(9)

(10)

式(7)的情況與式(6)類似，除了目標(biāo)所在公共邊連接的2個(gè)網(wǎng)格上6個(gè)節(jié)點(diǎn)能夠監(jiān)測(cè)到目標(biāo)外，只有節(jié)點(diǎn)F可以監(jiān)測(cè)到目標(biāo)，因此能夠監(jiān)測(cè)到目標(biāo)的節(jié)點(diǎn)數(shù)量是7.

證畢.

3.2 移動(dòng)目標(biāo)監(jiān)測(cè)和定位

本節(jié)將給出目標(biāo)監(jiān)測(cè)算法，分3種情況討論目標(biāo)的定位問(wèn)題，并給出定位算法.

定義2. 代理節(jié)點(diǎn).距離Sink最近的管理節(jié)點(diǎn)稱為代理節(jié)點(diǎn).代理節(jié)點(diǎn)可以直接與Sink通信.

情況1. 目標(biāo)在1個(gè)網(wǎng)格單元內(nèi).

根據(jù)定理1，網(wǎng)格單元的4個(gè)邊界節(jié)點(diǎn)能夠監(jiān)測(cè)到目標(biāo)，如圖2(a)所示.這些節(jié)點(diǎn)監(jiān)測(cè)到目標(biāo)后作出決策“1”，并將決策傳輸給它們的管理節(jié)點(diǎn).管理節(jié)點(diǎn)根據(jù)決策進(jìn)行目標(biāo)定位(3.3節(jié)算法1)，并傳輸定位結(jié)果給代理節(jié)點(diǎn)，代理節(jié)點(diǎn)最終發(fā)送數(shù)據(jù)給Sink.

情況2. 目標(biāo)在網(wǎng)格公共邊上.

根據(jù)定理2～4，如果目標(biāo)出現(xiàn)在網(wǎng)格的公共邊上，那么多個(gè)網(wǎng)格的邊界節(jié)點(diǎn)將監(jiān)測(cè)到目標(biāo)，如圖2(b)和圖2(c)所示.這些節(jié)點(diǎn)作出決策“1”并將自己的決策傳輸給所在網(wǎng)格的管理節(jié)點(diǎn).每個(gè)管理節(jié)點(diǎn)獨(dú)立地定位目標(biāo).所有管理節(jié)點(diǎn)向距離代理節(jié)點(diǎn)最近的管理節(jié)點(diǎn)發(fā)送定位結(jié)果，該管理節(jié)點(diǎn)聚合部分定位結(jié)果得到最終定位結(jié)果，并經(jīng)過(guò)代理節(jié)點(diǎn)發(fā)送定位結(jié)果給Sink.

情況3. 目標(biāo)在網(wǎng)格單元的頂角附近.

如圖2(d)所示，目標(biāo)處于陰影扇形區(qū)域內(nèi)(近似于扇形)，目標(biāo)被它所在網(wǎng)格內(nèi)的4個(gè)邊界節(jié)點(diǎn)監(jiān)測(cè)到，同時(shí)目標(biāo)被鄰居網(wǎng)格內(nèi)的最近的一個(gè)節(jié)點(diǎn)監(jiān)測(cè)到.定位過(guò)程與情況2相同.

3.3 移動(dòng)目標(biāo)定位

一旦接收到了感知數(shù)據(jù)，管理節(jié)點(diǎn)執(zhí)行定位算法進(jìn)行目標(biāo)定位.現(xiàn)存的許多定位算法都適用于本文的跟蹤過(guò)程中.本文實(shí)驗(yàn)以簡(jiǎn)單靈活的質(zhì)心算法為例[19]，實(shí)驗(yàn)結(jié)果表明質(zhì)心算法在本文所提出網(wǎng)絡(luò)模型上具有很好的定位效果，而且無(wú)額外硬件需求.

定義3. 聚合管理節(jié)點(diǎn).執(zhí)行聚合操作的跟蹤管理節(jié)點(diǎn)為聚合管理節(jié)點(diǎn).通常，選擇距離代理節(jié)點(diǎn)較近的跟蹤管理節(jié)點(diǎn)作為聚合管理節(jié)點(diǎn).

(11)

算法1. 基于2階段聚合的移動(dòng)目標(biāo)跟蹤算法.

輸入：節(jié)點(diǎn)的決策、時(shí)刻t；

輸出：時(shí)刻t目標(biāo)位置.

步驟1. 每個(gè)監(jiān)測(cè)到目標(biāo)的節(jié)點(diǎn)傳輸自己決策給所在網(wǎng)格的管理節(jié)點(diǎn)；

步驟2. 收到?jīng)Q策的管理節(jié)點(diǎn)獨(dú)立地計(jì)算目標(biāo)的位置，得到部分定位結(jié)果；

步驟3. 所有計(jì)算得到部分定位結(jié)果的管理節(jié)點(diǎn)廣播自己的結(jié)果給鄰居管理節(jié)點(diǎn)；

步驟4. 判斷是否接收到鄰居管理節(jié)點(diǎn)發(fā)送給自己的定位結(jié)果；

IF沒(méi)有接收到

傳輸定位結(jié)果給Sink；

ELSE

找出聚合管理節(jié)點(diǎn)k，并且把自己的部分定位結(jié)果發(fā)給k；

END IF

步驟5. 節(jié)點(diǎn)k對(duì)收到的結(jié)果執(zhí)行加權(quán)定位，計(jì)

3.4 最短路徑選擇算法

當(dāng)管理節(jié)點(diǎn)獲得目標(biāo)的最終位置信息后，將通過(guò)路由發(fā)送位置信息給代理節(jié)點(diǎn)，最終到達(dá)Sink.本節(jié)將提出一個(gè)基于順逆時(shí)針的最短路徑選擇算法.算法的核心思想是向代理節(jié)點(diǎn)發(fā)送數(shù)據(jù)的管理節(jié)點(diǎn)使用時(shí)針機(jī)制選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，重復(fù)這一個(gè)過(guò)程直到數(shù)據(jù)到達(dá)代理節(jié)點(diǎn).

例如圖3中代理節(jié)點(diǎn)在當(dāng)前管理節(jié)點(diǎn)的右下方，管理節(jié)點(diǎn)選擇右圓為參考圓，陰影節(jié)點(diǎn)為轉(zhuǎn)發(fā)節(jié)點(diǎn).

Fig. 3 Clockwise scheme diagram圖3 順時(shí)針機(jī)制示意圖

Fig. 4 Anticlockwise scheme diagram圖4 逆時(shí)針機(jī)制示意圖

定義5. 逆時(shí)針機(jī)制.管理節(jié)點(diǎn)i按照逆時(shí)針?lè)较驑?gòu)造3個(gè)直徑為d的圓，分別稱作上圓、左圓和下圓；i選擇圓心距離代理節(jié)點(diǎn)最近的圓為參考圓.沿著參考圓邊緣逆時(shí)針?lè)较虺霭l(fā)遇到的第1個(gè)鄰居節(jié)點(diǎn)即為轉(zhuǎn)發(fā)節(jié)點(diǎn).該機(jī)制稱為逆時(shí)針機(jī)制.

當(dāng)代理節(jié)點(diǎn)位于管理節(jié)點(diǎn)右邊的時(shí)候，管理節(jié)點(diǎn)采用順時(shí)針機(jī)制選擇下一跳傳輸節(jié)點(diǎn).當(dāng)代理節(jié)點(diǎn)位于管理節(jié)點(diǎn)左邊的時(shí)候，管理節(jié)點(diǎn)采用逆時(shí)針機(jī)制選擇下一跳傳輸節(jié)點(diǎn).

步驟1. 當(dāng)前需要傳輸數(shù)據(jù)的管理節(jié)點(diǎn)i首先檢查自己或者自己的鄰居管理節(jié)點(diǎn)是否是代理節(jié)點(diǎn).如果是，算法跳到步驟4.

步驟2.i檢查代理節(jié)點(diǎn)與自己的位置關(guān)系.如果代理節(jié)點(diǎn)在自己的左側(cè)，i采用逆時(shí)針機(jī)制選擇轉(zhuǎn)發(fā)節(jié)點(diǎn).如果代理節(jié)點(diǎn)在自己的右側(cè)，i采用順時(shí)針機(jī)制選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)；否則，i與代理節(jié)點(diǎn)在同一列，直接選擇同列距離代理節(jié)點(diǎn)更近的節(jié)點(diǎn)為轉(zhuǎn)發(fā)節(jié)點(diǎn).

Fig. 5 The distribution of energy consumption圖5 總能量消耗示意圖

步驟3.i向轉(zhuǎn)發(fā)節(jié)點(diǎn)j傳輸數(shù)據(jù).節(jié)點(diǎn)j收到數(shù)據(jù)后，執(zhí)行步驟1繼續(xù)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn).

步驟4. 如果管理節(jié)點(diǎn)i是代理節(jié)點(diǎn)，它直接傳輸數(shù)據(jù)給Sink；否則管理節(jié)點(diǎn)i的鄰居是代理節(jié)點(diǎn)，i傳輸數(shù)據(jù)給鄰居代理節(jié)點(diǎn)k，k再傳輸數(shù)據(jù)給Sink.

最短路徑選擇算法的偽代碼如算法2所示.

算法2. 最短路徑選擇算法.

輸入：當(dāng)前管理節(jié)點(diǎn)位置、代理節(jié)點(diǎn)位置.

步驟1. 判斷當(dāng)前節(jié)點(diǎn)或者其鄰居是否代理節(jié)點(diǎn)：

IF是

轉(zhuǎn)入步驟2;

ELSE

② 發(fā)送數(shù)據(jù)給轉(zhuǎn)發(fā)節(jié)點(diǎn);

③ 轉(zhuǎn)發(fā)節(jié)點(diǎn)接收到數(shù)據(jù)后轉(zhuǎn)入步驟1;

END IF

步驟2. 傳輸數(shù)據(jù)給Sink或代理節(jié)點(diǎn).

4 節(jié)點(diǎn)能量消耗分析

本節(jié)將分析網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗.用E表示節(jié)點(diǎn)的初始總能量，在目標(biāo)跟蹤的過(guò)程中發(fā)送、接收數(shù)據(jù)包以及其他部分的能量消耗(例如初始化能耗)分別表示為Esend，Ercv，Eoth.節(jié)點(diǎn)總能量消耗如式(12)所示：

(12)

每個(gè)傳感器節(jié)點(diǎn)將1 b的信息傳輸100 m消耗的能量等同于傳感器節(jié)點(diǎn)執(zhí)行3 000條CPU指令的能量消耗[19-20].考慮到簡(jiǎn)單信息處理對(duì)整體能量消耗影響不大，我們?cè)诜治龉?jié)點(diǎn)整體能耗時(shí)主要考慮通信的能耗而忽略掉信息處理的能量消耗.

式(12)中，Esend是移動(dòng)目標(biāo)跟蹤的過(guò)程中發(fā)送數(shù)據(jù)包的總能量消耗.如式(13)所示，Esend主要包括以下3個(gè)方面的能量消耗：1)每個(gè)監(jiān)測(cè)到目標(biāo)的邊界節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)包給它們的管理節(jié)點(diǎn)的能量消耗Esre；2)這些管理節(jié)點(diǎn)向聚合管理節(jié)點(diǎn)發(fā)送定位結(jié)果，并且為了獲得更好的定位精度聚合管理節(jié)點(diǎn)聚合這些結(jié)果的能量消耗Esagg；3)聚合節(jié)點(diǎn)采用本文提出的最短路徑選擇算法傳輸最終的定位結(jié)果給Sink的能量消耗:

(13)

同理，接收數(shù)據(jù)包的能量消耗Ercv定義與Esend類似，如式(14)所示.

(14)

式(12)中最后一項(xiàng)Eoth是初始化的能量消耗，它由3個(gè)部分組成：1)Sink選擇代理節(jié)點(diǎn)的能量消耗；2)選擇管理節(jié)點(diǎn)的能量消耗；3)構(gòu)造網(wǎng)格的能量消耗.假定每個(gè)節(jié)點(diǎn)接收或發(fā)送1個(gè)數(shù)據(jù)包都消耗1個(gè)單位的能量.

在本文后面的實(shí)驗(yàn)中，我們比較了不同網(wǎng)格大小和目標(biāo)在不同運(yùn)動(dòng)速度下目標(biāo)定位和傳輸?shù)哪芰肯?圖5顯示了連續(xù)執(zhí)行2次移動(dòng)目標(biāo)跟蹤時(shí)，節(jié)點(diǎn)分別執(zhí)行定位、路由和其他操作所消耗能量占總能耗的百分比.

從圖5可以看出，目標(biāo)定位和目標(biāo)沿著最短路徑傳輸?shù)哪芎姆浅Ｏ嘟鼈兛傆?jì)占總能耗的65%;其余35%的能量消耗在其他部分.這說(shuō)明本文的定位算法和最短路徑傳輸算法具有很高的能量利用率，特別適用于網(wǎng)絡(luò)需要長(zhǎng)期工作的應(yīng)用.

Fig. 7 The influence of grid size on tracking performance with velocity 30 cells圖7 目標(biāo)移動(dòng)速度為30cells時(shí)網(wǎng)格尺寸對(duì)跟蹤性能的影響

5 實(shí)驗(yàn)和評(píng)估

為了驗(yàn)證算法，本文在Win7系統(tǒng)上使用VC++ 6.0搭建了一個(gè)模擬平臺(tái).實(shí)驗(yàn)評(píng)估了網(wǎng)格大小和目標(biāo)運(yùn)行的速度等參數(shù)對(duì)算法性能的影響，并就跟蹤準(zhǔn)確性和能量消耗情況與文獻(xiàn)[21]提出的算法(以下記為dis算法)進(jìn)行對(duì)比.該算法是一個(gè)高效的能源有效移動(dòng)目標(biāo)定位算法.本實(shí)驗(yàn)中，400個(gè)節(jié)點(diǎn)均勻部署在一個(gè)1300×600單元的區(qū)域.圖6顯示了節(jié)點(diǎn)部署的一種情況.

Fig. 6 Plan view of simulation laboratory with node deployment圖6 部署節(jié)點(diǎn)下的模擬實(shí)驗(yàn)室平面圖

5.1 系統(tǒng)參數(shù)對(duì)跟蹤準(zhǔn)確性的影響

本組實(shí)驗(yàn)分析了目標(biāo)移動(dòng)速度和網(wǎng)格大小對(duì)目標(biāo)跟蹤性能的影響.我們分別設(shè)置目標(biāo)運(yùn)動(dòng)速度是30cells和50cells.圖7和圖8顯示了網(wǎng)格的大小在45～80個(gè)單位區(qū)間內(nèi)變化時(shí)本文定位算法和dis定位算法的性能變化情況.所有實(shí)驗(yàn)結(jié)果示意圖中橫縱坐標(biāo)分別代表目標(biāo)在二維空間的位置坐標(biāo)，其中橫軸代表x軸，縱軸代表y軸.

Fig. 8 The influence of grid size on tracking performance with velocity 50 cells圖8 目標(biāo)移動(dòng)速度為50cells時(shí)網(wǎng)格尺寸對(duì)跟蹤性能的影響

從圖7可以看出，在絕大多數(shù)情況下本文算法的定位誤差要小于dis算法.本文算法在目標(biāo)速度為30cells、網(wǎng)格大小在45個(gè)單位的運(yùn)動(dòng)軌跡定位時(shí)可以實(shí)現(xiàn)0誤差，并且本文算法的最小定位誤差始終不超過(guò)3個(gè)單位.

從圖7和圖8也可以看出，隨著網(wǎng)格的增大，本文定位算法的精度略微降低.然而網(wǎng)格大小為50個(gè)單位時(shí)的定位精度要比其他網(wǎng)格大小(包括網(wǎng)格大小是45)的定位精度更好，這主要是由節(jié)點(diǎn)的布置不同以及聚合步驟所決定.

從圖7和圖8中我們還可以發(fā)現(xiàn)目標(biāo)做隨機(jī)游走運(yùn)動(dòng)時(shí)(圖7和圖8中的折線部分)，本文算法更優(yōu)于dis算法，尤其dis算法在左側(cè)折線部分定位誤差很大.這是由于dis算法選取監(jiān)測(cè)到目標(biāo)的傳感器節(jié)點(diǎn)感知范圍相交弧的中點(diǎn)作為目標(biāo)的估算位置，當(dāng)目標(biāo)在網(wǎng)絡(luò)邊緣時(shí)該方法存在較大弊端.

5.2 算法能量消耗對(duì)比

圖9比較了使用本文提出的最短路徑算法傳輸數(shù)據(jù)的能量消耗和其他基于網(wǎng)格的路由算法能量消耗[13]，該方法是目前最好的直接應(yīng)用于目標(biāo)跟蹤過(guò)程而不需要過(guò)多額外工作量的路由方法.從圖9可以看出本文的最短路徑算法比其他網(wǎng)格路由算法節(jié)省了五分之一甚至更多的能量.從圖9可以看出，隨著網(wǎng)格增大,本文提出算法能量消耗減少.這是因?yàn)檩^大的網(wǎng)格所配置管理節(jié)點(diǎn)數(shù)目更少，傳輸路徑中的傳輸跳數(shù)也越少.

Fig. 9 Transmission energy consumption圖9 傳輸能量消耗圖

圖10比較了本文所提出定位算法(簡(jiǎn)稱為our localization)和dis算法定位目標(biāo)的能量消耗.從圖10可以看出，本文所提出算法在能耗節(jié)約上具有更好的效果，尤其目標(biāo)移動(dòng)速度較快的情況比目標(biāo)移動(dòng)速度較慢時(shí)消耗的能量更少.在采樣頻率固定的情況下，固定時(shí)間間隔內(nèi)目標(biāo)移動(dòng)速度快導(dǎo)致被定位的次數(shù)變少，從而定位消耗的能量也相應(yīng)地減少.

Fig. 10 Localization energy consumption圖10 定位的能量消耗

6 結(jié)束語(yǔ)

本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)能量有效的移動(dòng)目標(biāo)跟蹤算法.1)在移動(dòng)目標(biāo)跟蹤的過(guò)程中引入網(wǎng)格模型，使處于網(wǎng)格頂點(diǎn)附近的節(jié)點(diǎn)工作、其他節(jié)點(diǎn)睡眠以此節(jié)省能量.2)分析了目標(biāo)在網(wǎng)格內(nèi)出現(xiàn)的各種位置關(guān)系，針對(duì)每種位置關(guān)系給出適用的定位算法.為了優(yōu)化目標(biāo)定位結(jié)果，本文進(jìn)一步給出了一個(gè)基于2階段聚合的移動(dòng)目標(biāo)跟蹤算法，以緩解單個(gè)網(wǎng)格內(nèi)定位誤差對(duì)整體定位結(jié)果的影響.3)提出了一個(gè)基于順逆時(shí)針機(jī)制的最短路徑選擇算法傳輸目標(biāo)跟蹤結(jié)果，該算法可以很好地融入到本文所提出目標(biāo)跟蹤過(guò)程，不必增加過(guò)多的額外能耗，同時(shí)保證參與路由的節(jié)點(diǎn)數(shù)目最少.4)進(jìn)行了大量的實(shí)驗(yàn)驗(yàn)證了系統(tǒng)參數(shù)包括網(wǎng)格大小、目標(biāo)運(yùn)動(dòng)速度對(duì)跟蹤性能的影響.

[1]Li Zhanqing, Nadon S, Cihlar J. Satellite detection of canadian boreal forest fires: Development and application of the algorithm[J]. International Journal of Remote Sensing, 2000, 21(16): 3057-3069

[2]Gupta V, Kim J, Pandya A, et al. Nano-CF: A coordination framework for macro-programming in wireless sensor networks[C]Proc of the 8th Annual IEEE Communications Society Conf on Sensor, Mesh and Ad Hoc Communications and Networks. Piscataway, NJ: IEEE, 2011: 467-475

[3]Duarte M, Hu Yuhen. Vehicle classification in distributed sensor network[J]. Journal of Parallel & Distributed Computing, 2004, 64(7): 826-838

[4]Spenza D, Magno M, Basagni S, et al. Beyond duty cycling: Wake-up radio with selective awakenings for long-lived wireless sensing systems[C]Proc of IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2015: 522-530

[5]Aslam M, Shah T, Javaid N, et al. CEEC: Centralized energy efficient clustering a new routing protocol for WSNs[C]Proc of the 9th Annual IEEE Communications Society Conf on Sensor, Mesh and Ad Hoc Communications and Networks. Piscataway, NJ: IEEE, 2012: 103-105

[6]Peng Yang, Li Zi, Qiao Daji, et al. I2C: A holistic approach to prolong the sensor network lifetime[C]Proc of IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2013: 2670-2678

[7]Liu Xuefeng, Cao Jiannong, Tang Shaojie, et al. A generalized coverage-preserving scheduling in WSNs: A case study in structural health monitoring[C]Proc of IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2014: 718-726

[8]Zheng Zhongming, Liu Anfeng, Cai Lin et al. ERCD: An energy-efficient clone detection protocol in WSNs[C]Proc of IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2013: 2436-2444

[9]Liu Xiang, Luo Jun, Vasilakos A. Compressed data aggregation for energy efficient wireless sensor networks[C]Proc of the 8th Annual IEEE Communications Society Conf on Sensor, Mesh and Ad Hoc Communications and Networks.Piscataway, NJ: IEEE, 2011: 46-54

[10]Luo Yu, Pu Li, Zheng Peng, et al. Effective relay selection for underwater cooperative acoustic networks[C]Proc of the 10th Int Conf on Mobile Ad-Hoc and Sensor Systems. Piscataway, NJ: IEEE, 2013: 104-112

[11]Wang Yi, Krishnamachari B, Annavaram M. Semi-Markov state estimation and policy optimization for energy efficient mobile sensing[C]Proc of the 9th Annual IEEE Communications Society Conf on Sensor, Mesh and Ad Hoc Communications and Networks. Piscataway, NJ: IEEE, 2012: 533-541

[12]Ye Fan, Luo Haiyun, Cheng Jerry, et al. A two-tier data dissemination model for large-scale wireless sensor networks[C]Proc of the 8th Annual Int Conf on Mobile Computing and Networking. New York: ACM, 2002: 148-159

[13]Tang Guoming, Xie Yi, Tang Daquan. An adaptive grid division algorithm for target location in wireless sensor networks[C]Proc of Conf on Anthology. Piscataway, NJ: IEEE, 2013: 1-6

[14]Jeong J, Hwang T, He Tian, et al. MCTA: Target tracking algorithm based on minimal contour in wireless sensor networks[C]Proc of IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2007: 2371-2375

[15]Arienzo L, Longo M.Energy-efficient collaborative tracking in wireless sensor networks[J]. International Journal of Sensor Networks, 2011, 9(3): 124-138

[16]Li Dan, Wong K, Hu Yuhen, et al. Detection, classification and tracking of targets in distributed sensor networks[J]. IEEE Signal Processing Magazine, 2002, 19(2): 17-29

[17]Deldar F, Yaghmaee M. Energy efficient prediction-based clustering algorithm for target tracking in wireless sensor networks[C]Proc of Conf on Intelligent Networking and Collaborative Systems. Piscataway, NJ: IEEE, 2010: 315-318

[18]Motevallian S, Xia Lu, Anderson B. A new splitting-merging paradigm for distributed localization in wireless sensor networks[C]Proc of Int Conf on Communication. Piscataway, NJ: IEEE, 2013: 1454-1458

[19]Kim W, Kirill M, Jeung Y. On tracking objects with binary proximity sensors[C]Proc of Conf on Information Processing in Sensor Networks. Piscataway, NJ: IEEE, 2005: 301-308

[20]Iyer R, Kleinrock L.QoS control for sensor networks[C]Proc of Int Conf on Communications. Piscataway, NJ: IEEE, 2003: 517-521

[21]Wang Zijian, Bulut E, Szymanski B. Distributed energy-efficient target tracking with binary sensor networks[J]. ACM Trans on Sensor Networks, 2010, 6(4): 2084-2095

Ren Qianqian, born in 1980. Associate professor at Heilongjiang University. Member of CCF. Her main research interests include database and wireless sensor networks.

Liu Hongyang, born in 1991. Master from Heilongjiang University. Her main research interests include wireless sensor networks and target tracking.

Liu Yong, born in 1975. Associate professor at Heilongjiang University. Member of CCF. His main research interests include data mining and social network.

Li Jinbao, born in 1969. Professor and PhD supervisor at Heilongjiang University. Senior member of CCF. His main research interests include sensor networks, mobile social network and big data.

Wang Nan, born in 1980. PhD candidate at Heilongjiang University. Her main research interests include sensor networks and social network.

A Two-Tier Aggregation Based Tracking Algorithm in Wireless Sensor Networks

Ren Qianqian，Liu Hongyang，Liu Yong，Li Jinbao，and Wang Nan

(SchoolofComputerScienceandTechnology,HeilongjiangUniversity,Harbin150080) (KeyLaboratoryofDatabaseandParallelComputingofHeilongjiangProvince,Harbin150080)

Mobile target tracking is an important issue in wireless sensor networks. This paper discusses the energy efficient tracking problem in networks. We first construct a grid based network model, which makes nodes near the vertexes of grid cells work and others sleep to save energy with tracking quality guarantee. We analyze the relationship between target appearance position and grid cells in the network, classify the three cases of target detection and give a general target localization method applied to each case. Then, We propose a two-tier aggregation based target tracking algorithm. The algorithm implements aggregation on partial localization results to obtain the optimized final localization result. After that, a clockwiseanticlockwise scheme based shortest path selection algorithm is presented to transmit localization result to sink with minimum involved sensor nodes. Finally, a comprehensive set of simulations are presented and the experimental results show that the proposed target tracking algorithm can yield excellent performance in terms of tracking accuracy and energy saving in wireless sensor networks.

mobile target tracking; aggregation; grid; localization; clock scheme

2016-08-22；

2016-12-29

國(guó)家自然科學(xué)基金項(xiàng)目(61300225,61370222,81273649)；黑龍江省自然科學(xué)基金項(xiàng)目(F2017022,F201430,F201434)；黑龍江省高校青年創(chuàng)新人才基金項(xiàng)目(UNPYSCT-2015017)；哈爾濱市科技創(chuàng)新人才專項(xiàng)基金項(xiàng)目(2016RAQXJ028) This work was supported by the National Natural Science Foundation of China(61300225, 61370222, 81273649), the Natural Science Foundation of Heilongjiang Province (F2017022, F201430, F201434), the Innovation Talents Foundation of Heilongjiang Educational Committee (UNPYSCT-2015017), and the Science Innovation Talents Foundation of Harbin (2016RAQXJ028).

劉勇(acliuyong@sina.com)

TP391