趙怡宏，王賾，張海娟

天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津300387

基于動(dòng)態(tài)信標(biāo)生成樹(shù)的傳感器定位算法

趙怡宏，王賾，張海娟

天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津300387

CNKI網(wǎng)絡(luò)出版：2017-03-13,http://kns.cnki.net/kcms/detail/11.2127.TP.20170313.1638.022.html

1 引言

近年來(lái)，隨著微機(jī)電系統(tǒng)（MEMS）、無(wú)線通信技術(shù)及傳感器技術(shù)的發(fā)展和相互融合，無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）[1-2]日趨成熟。WSNs是集信息采集、傳輸、處理于一體的綜合智能信息系統(tǒng)，具有廣闊的應(yīng)用發(fā)展前景。傳感器節(jié)點(diǎn)具有傳感、驅(qū)動(dòng)控制、計(jì)算及通信能力，能夠?qū)崟r(shí)監(jiān)測(cè)、感知和采集目標(biāo)區(qū)域中監(jiān)測(cè)對(duì)象的各種信息，從而實(shí)現(xiàn)計(jì)算機(jī)世界、物理世界以及人類社會(huì)三元世界的連通[3-5]。WSNs憑借其節(jié)點(diǎn)體積小、成本低、功耗低、自組網(wǎng)絡(luò)等優(yōu)勢(shì)，已被廣泛應(yīng)用在軍事領(lǐng)域、環(huán)境監(jiān)測(cè)、工農(nóng)業(yè)、生物醫(yī)療、智能交通等各個(gè)領(lǐng)域[6-8]。

現(xiàn)有的理論成果有效地推動(dòng)了相關(guān)研究的發(fā)展，在無(wú)線傳感器定位方面，文獻(xiàn)[1]和文獻(xiàn)[2]首先描述了無(wú)線傳感器網(wǎng)絡(luò)的定位基礎(chǔ)知識(shí)，著重介紹了無(wú)線傳感器網(wǎng)絡(luò)生命周期，能量消耗，節(jié)點(diǎn)移動(dòng)速度等因素對(duì)傳感器節(jié)點(diǎn)定位的影響。文獻(xiàn)[9]引入了移動(dòng)信標(biāo)節(jié)點(diǎn)輔助定位機(jī)制，這是一個(gè)典型的方法，通過(guò)使用有限數(shù)量的移動(dòng)信標(biāo)節(jié)點(diǎn)大大降低了網(wǎng)絡(luò)的部署實(shí)施成本。文獻(xiàn)[10-11]介紹了一種anchor-guiding機(jī)制，通過(guò)規(guī)劃信標(biāo)節(jié)點(diǎn)的移動(dòng)路徑，有效地引導(dǎo)移動(dòng)信標(biāo)節(jié)點(diǎn)沿著一個(gè)有效的路徑移動(dòng)，從而節(jié)省定位所需的時(shí)間。文獻(xiàn)[12]提出了DREAMS算法，在該算法中信標(biāo)節(jié)點(diǎn)的移動(dòng)信標(biāo)節(jié)點(diǎn)借助圖的深度優(yōu)先遍歷（DFT）思想來(lái)規(guī)劃路徑。

在監(jiān)測(cè)區(qū)域中，無(wú)線傳感器節(jié)點(diǎn)往往是通過(guò)拋撒的方式來(lái)隨機(jī)部署的，導(dǎo)致的結(jié)果就是傳感器節(jié)點(diǎn)的分布往往是疏密不均的。以往的對(duì)信標(biāo)節(jié)點(diǎn)移動(dòng)路徑進(jìn)行規(guī)劃的算法[9]大多把研究方向放在如何通過(guò)規(guī)劃路徑來(lái)覆蓋更多的區(qū)域，以此來(lái)確保更高的定位率，這樣整體的定位率雖然得以提高，但是定位時(shí)間、定位精度和能量開(kāi)銷的優(yōu)化無(wú)法同時(shí)得到有效保證。再者，現(xiàn)有的算法并不把網(wǎng)絡(luò)節(jié)點(diǎn)密度作為定位的參考依據(jù)。如此一來(lái)，在節(jié)點(diǎn)分布少的區(qū)域和節(jié)點(diǎn)分布密集的區(qū)域采用相同的定位方法，就會(huì)導(dǎo)致節(jié)點(diǎn)分布密集的區(qū)域定位精度低，節(jié)點(diǎn)分布相對(duì)較少的區(qū)域定位率低下，信標(biāo)節(jié)點(diǎn)能量得不到最大化利用等問(wèn)題的產(chǎn)生。

針對(duì)上述問(wèn)題，文中提出了基于網(wǎng)絡(luò)節(jié)點(diǎn)密度來(lái)定位的生成信標(biāo)樹(shù)算法（GBT）。GBT算法的主旨思想主要來(lái)源于圖的深度優(yōu)先遍歷（DFT），在網(wǎng)絡(luò)中構(gòu)建一個(gè)信標(biāo)節(jié)點(diǎn)組，通過(guò)對(duì)當(dāng)前信標(biāo)節(jié)點(diǎn)廣播區(qū)域內(nèi)傳感器節(jié)點(diǎn)的一跳未被定位的鄰居節(jié)點(diǎn)的個(gè)數(shù)的比較，在網(wǎng)絡(luò)中動(dòng)態(tài)生成一棵深度優(yōu)先信標(biāo)樹(shù)（DFBT），以此來(lái)規(guī)劃信標(biāo)節(jié)點(diǎn)組的移動(dòng)路徑，從而達(dá)到全網(wǎng)節(jié)點(diǎn)的精確定位。

通過(guò)仿真實(shí)驗(yàn)，證明了GBT算法在節(jié)點(diǎn)定位精度，定位時(shí)間和信標(biāo)節(jié)點(diǎn)能量的最大化利用等問(wèn)題上都具有比其他規(guī)劃信標(biāo)節(jié)點(diǎn)移動(dòng)路徑算法有更好的優(yōu)越性。

2 傳統(tǒng)的動(dòng)態(tài)信標(biāo)節(jié)點(diǎn)輔助定位算法

動(dòng)態(tài)信標(biāo)節(jié)點(diǎn)可以在網(wǎng)絡(luò)中任意移動(dòng)，通過(guò)使用內(nèi)嵌的GPS或者其他定位系統(tǒng)對(duì)自己的位置進(jìn)行感知，然后在網(wǎng)絡(luò)中以特定的頻率或在設(shè)計(jì)好的位置進(jìn)行包含自己地理位置信息的信標(biāo)信息的廣播[10-11]。網(wǎng)絡(luò)中的待定位普通傳感器節(jié)點(diǎn)通過(guò)接收信標(biāo)節(jié)點(diǎn)廣播的信標(biāo)信息對(duì)自己進(jìn)行定位[13]。

2.1 Snake-like算法

Snake-like算法[14]，利用一個(gè)移動(dòng)信標(biāo)節(jié)點(diǎn)，它的開(kāi)始位置被設(shè)置在監(jiān)測(cè)區(qū)域的左上角，然后向下呈直線狀在監(jiān)測(cè)區(qū)域內(nèi)進(jìn)行遍歷，到達(dá)下邊界后向右轉(zhuǎn)向，移動(dòng)一定距離后，再向上呈直線狀行走，如此反復(fù)，直到信標(biāo)節(jié)點(diǎn)的遍歷路徑已經(jīng)完全覆蓋整個(gè)監(jiān)測(cè)區(qū)域或者信標(biāo)節(jié)點(diǎn)的能量耗盡而不得不停止移動(dòng)。圖1描述了Snakelike算法的遍歷方式。

圖1 信標(biāo)節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi)使用Snake-like算法生成的遍歷軌跡

在監(jiān)測(cè)區(qū)域較小時(shí)，該算法可以完成對(duì)整個(gè)監(jiān)測(cè)區(qū)域的遍歷，但如果監(jiān)測(cè)區(qū)域較大時(shí)，信標(biāo)節(jié)點(diǎn)的能量往往在移動(dòng)過(guò)程中就會(huì)被消耗殆盡。如此一來(lái)，信標(biāo)節(jié)點(diǎn)的能量是確定的，那么兩條遍歷軌跡間的距離就決定了信標(biāo)節(jié)點(diǎn)遍歷所能覆蓋的監(jiān)測(cè)區(qū)域面積。

2.2 Random-walk算法

Random-walk算法，該算法模型較為簡(jiǎn)單，將信標(biāo)節(jié)點(diǎn)隨機(jī)部署在一個(gè)監(jiān)測(cè)區(qū)域內(nèi)。將信標(biāo)節(jié)點(diǎn)的移動(dòng)速度和信標(biāo)信息廣播包的發(fā)送頻率設(shè)為定值，但是信標(biāo)節(jié)點(diǎn)的移動(dòng)方向是隨機(jī)的。

在這種情況下，信標(biāo)節(jié)點(diǎn)的移動(dòng)軌跡具有隨機(jī)性，很可能會(huì)導(dǎo)致節(jié)點(diǎn)一直在同一片區(qū)域中打轉(zhuǎn)，造成節(jié)點(diǎn)的定位效率具有很大的波動(dòng)性，那么定位效率就完全取決于信標(biāo)節(jié)點(diǎn)移動(dòng)軌跡所能覆蓋的監(jiān)測(cè)區(qū)域面積。

針對(duì)傳統(tǒng)動(dòng)態(tài)信標(biāo)節(jié)點(diǎn)輔助定位算法存在的問(wèn)題，本文引入了基于節(jié)點(diǎn)密度的定位算法。下一章將對(duì)該算法進(jìn)行詳細(xì)的介紹。

3 動(dòng)態(tài)信標(biāo)生成樹(shù)算法

3.1 網(wǎng)絡(luò)模型描述

假定大量靜態(tài)普通傳感器節(jié)點(diǎn)被隨機(jī)拋撒在監(jiān)測(cè)區(qū)域內(nèi)，同時(shí)將一個(gè)包含四個(gè)信標(biāo)節(jié)點(diǎn)的信標(biāo)節(jié)點(diǎn)組部署在網(wǎng)絡(luò)的正中心。普通傳感器節(jié)點(diǎn)無(wú)法直接獲取自己的位置信息，需要信標(biāo)節(jié)點(diǎn)來(lái)對(duì)其進(jìn)行輔助定位[15-16]。所有網(wǎng)絡(luò)節(jié)點(diǎn)的通信半徑均為r。信標(biāo)節(jié)點(diǎn)的通信半徑可根據(jù)定位需求情況進(jìn)行相應(yīng)改變。為了計(jì)算方便，定位過(guò)程中將節(jié)點(diǎn)的圓形通信區(qū)域的外接正方形確定為節(jié)點(diǎn)定位的約束區(qū)域范圍。比如t時(shí)刻信標(biāo)節(jié)點(diǎn)在坐標(biāo)(x,y)處以r為半徑進(jìn)行廣播，通過(guò)建立平面直角坐標(biāo)系來(lái)進(jìn)行描述，數(shù)軸的正方向設(shè)為向上和向右的方向，則該信標(biāo)節(jié)點(diǎn)所能形成的廣播約束區(qū)域在[(x-r,y+r),(x+r,y-r)]t內(nèi)。

網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都會(huì)有自己唯一相應(yīng)的ID，以此來(lái)對(duì)不同的傳感器節(jié)點(diǎn)進(jìn)行區(qū)分。通過(guò)發(fā)送“Hello”信息，傳感器節(jié)點(diǎn)以此來(lái)維護(hù)它們之間的鄰居關(guān)系。在定位過(guò)程中，傳感器節(jié)點(diǎn)之間會(huì)發(fā)送含有特定定位信息的message以此來(lái)進(jìn)行定位[12]。

3.2 算法設(shè)計(jì)

基于節(jié)點(diǎn)密度定位算法的主旨思想是：根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)密度分布，規(guī)劃信標(biāo)節(jié)點(diǎn)組的移動(dòng)路徑，從而完成對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的精確定位。該算法主要借鑒的思想是圖的深度優(yōu)先遍歷（Depth-First Traversal，DFT），設(shè)計(jì)了生成信標(biāo)樹(shù)算法（Generate Beacon-based Tree，GBT），在網(wǎng)絡(luò)中動(dòng)態(tài)地生成一棵深度優(yōu)先信標(biāo)樹(shù)（Depth-First Beacon-based Tree，DFBT），從而指導(dǎo)信標(biāo)節(jié)點(diǎn)組進(jìn)行移動(dòng)。這棵信標(biāo)樹(shù)上除根節(jié)點(diǎn)root外的其余節(jié)點(diǎn)，均需要調(diào)用估計(jì)位置算法（Estimate Location，EL）和信標(biāo)節(jié)點(diǎn)組移動(dòng)算法（Beacon Group Moving，BGM）。

3.2.1 選舉root節(jié)點(diǎn)

網(wǎng)絡(luò)初始化時(shí)，首先構(gòu)造一個(gè)以節(jié)點(diǎn)通信半徑r的2倍為邊長(zhǎng)的正方形，分別將四個(gè)信標(biāo)節(jié)點(diǎn)放置在正方形的四個(gè)頂點(diǎn)上，組成一個(gè)信標(biāo)節(jié)點(diǎn)組，并將該正方形放置在網(wǎng)絡(luò)的中心位置。這四個(gè)信標(biāo)節(jié)點(diǎn)可以任意移動(dòng)，當(dāng)且僅當(dāng)任一信標(biāo)節(jié)點(diǎn)的廣播半徑內(nèi)存在有數(shù)量大于1的未被定位的普通傳感器節(jié)點(diǎn)后，信標(biāo)節(jié)點(diǎn)組停止移動(dòng)。確定這個(gè)通信范圍內(nèi)具有普通節(jié)點(diǎn)數(shù)大于1的信標(biāo)節(jié)點(diǎn)的位置，以此位置的坐標(biāo)為中心，以r為半徑廣播信標(biāo)信息，從而形成廣播約束區(qū)。指定該信標(biāo)節(jié)點(diǎn)為根信標(biāo)節(jié)點(diǎn)（root），也就是DFBT的根節(jié)點(diǎn)。

如果信標(biāo)節(jié)點(diǎn)在相同時(shí)刻發(fā)現(xiàn)存在數(shù)量大于1的未被定位的普通節(jié)點(diǎn)，則通信范圍內(nèi)節(jié)點(diǎn)數(shù)最多的信標(biāo)節(jié)點(diǎn)被指定為root；如果發(fā)現(xiàn)時(shí)間和數(shù)量都相同，則隨機(jī)選取任一信標(biāo)節(jié)點(diǎn)為root。

3.2.2 估計(jì)位置算法

在找到root節(jié)點(diǎn)后，在生成信標(biāo)樹(shù)的過(guò)程中還需要使用估計(jì)EL算法。EL算法可以分為以下三個(gè)步驟：

（1）確定目標(biāo)統(tǒng)計(jì)區(qū)域（Object Statistical Area，OSA），找出下級(jí)目標(biāo)信標(biāo)節(jié)點(diǎn)（target beacon）。

（2）確定target beacon的估計(jì)區(qū)域。

（3）計(jì)算target beacon的估計(jì)位置。

為了實(shí)現(xiàn)以網(wǎng)絡(luò)節(jié)點(diǎn)密度為參考依據(jù)來(lái)對(duì)全網(wǎng)節(jié)點(diǎn)完成定位，GBT算法需要統(tǒng)計(jì)對(duì)比current beacon的OSA內(nèi)，普通節(jié)點(diǎn)周圍未被定位的一跳鄰居的數(shù)量，從而保證信標(biāo)節(jié)點(diǎn)組總是朝著待定位節(jié)點(diǎn)分布最為稠密區(qū)域的方向移動(dòng)。current beacon代表的是當(dāng)前需要廣播信標(biāo)信息來(lái)輔助定位的普通傳感器節(jié)點(diǎn)。

統(tǒng)計(jì)OSA內(nèi)普通傳感器節(jié)點(diǎn)周圍未被定位的一跳鄰居的個(gè)數(shù)，current beacon對(duì)個(gè)數(shù)進(jìn)行比較，找出其中的最大值。指定這個(gè)最大值節(jié)點(diǎn)為target beacon。在確定target beacon的估計(jì)位置后，它會(huì)成為新的current beacon，與此同時(shí)形成新的OSA，再次統(tǒng)計(jì)新的OSA內(nèi)普通傳感器節(jié)點(diǎn)周圍未被定位的一跳鄰居節(jié)點(diǎn)的個(gè)數(shù)。以此類推，直至終結(jié)。

注意到，當(dāng)target beacon的估計(jì)位置與current beacon所在的位置比較相近時(shí)，它升級(jí)為current beacon后形成的新的OSA與原來(lái)的上級(jí)current beacon的OSA重合區(qū)域會(huì)比較多。這就會(huì)導(dǎo)致只有少量新的未被統(tǒng)計(jì)過(guò)一跳鄰居數(shù)量的節(jié)點(diǎn)添加到新的OSA內(nèi)，將會(huì)使信標(biāo)節(jié)點(diǎn)組向網(wǎng)絡(luò)節(jié)點(diǎn)分布稠密區(qū)域移動(dòng)的速度大大減弱，進(jìn)而影響全網(wǎng)節(jié)點(diǎn)定位所需的時(shí)間成本。

為了避免或減小這樣的情形，將具有相同質(zhì)心的、邊長(zhǎng)為r的正方形區(qū)域從current beacon構(gòu)建的廣播約束區(qū)域中剔除掉，如圖2所示，用OSA來(lái)表示剩余的陰影區(qū)域。

圖2 current beacon形成的OSA

接下來(lái)要對(duì)target beacon的估計(jì)位置進(jìn)行確定。在OSA區(qū)域的四個(gè)頂點(diǎn)上分別放置信標(biāo)節(jié)點(diǎn)，然后分別以四個(gè)頂點(diǎn)為中心，以r為半徑廣播信標(biāo)信息。這時(shí)，普通傳感器節(jié)點(diǎn)在current beacon廣播約束區(qū)域內(nèi)的估計(jì)約束區(qū)域?qū)p小到3r×r，并將擁有一跳鄰居數(shù)最多的傳感器節(jié)點(diǎn)范圍確定在大小為的區(qū)域內(nèi)。

當(dāng)current beacon為root節(jié)點(diǎn)時(shí)，可以得出EL算法的執(zhí)行次數(shù)和target beacon估計(jì)區(qū)域之間的關(guān)系，如表1所示。

假設(shè)當(dāng)前target beaconS′使用EL算法得到的估計(jì)位置坐標(biāo)為(xest,yest)，其真實(shí)的位置坐標(biāo)為(xreal,yreal)，則可以用式（1）來(lái)表示節(jié)點(diǎn)S′的定位誤差：

表1 當(dāng)current beacon為root節(jié)點(diǎn)時(shí)，EL算法的執(zhí)行次數(shù)n和target beacon估計(jì)區(qū)域大小之間的關(guān)系

3.2.3 信標(biāo)節(jié)點(diǎn)組移動(dòng)算法

在對(duì)target beacon進(jìn)行定位的過(guò)程中，信標(biāo)節(jié)點(diǎn)組的移動(dòng)是具有一定規(guī)律的。確定下一時(shí)刻信標(biāo)節(jié)點(diǎn)組用于廣播信標(biāo)信息的位置需要以下幾方面因素：當(dāng)前形成target beacon所在估計(jì)區(qū)域的信標(biāo)節(jié)點(diǎn)的坐標(biāo)，當(dāng)前信標(biāo)節(jié)點(diǎn)組所在正方形區(qū)域的中心坐標(biāo)，以及當(dāng)前信標(biāo)節(jié)點(diǎn)組用于廣播信標(biāo)信息的半徑之間的關(guān)系。在本文中，將這種算法叫作信標(biāo)節(jié)點(diǎn)組移動(dòng)算法BGM。用一個(gè)三元消息串來(lái)表示用于確定信標(biāo)節(jié)點(diǎn)組下一時(shí)刻位置的信息，記作其中“||”表示消息串聯(lián)，表示當(dāng)前形成target beacon所在估計(jì)區(qū)域的信標(biāo)節(jié)點(diǎn)的坐標(biāo)，表示當(dāng)前信標(biāo)節(jié)點(diǎn)組所在的正方形區(qū)域的中心坐標(biāo)，表示當(dāng)前信標(biāo)節(jié)點(diǎn)組用于廣播信標(biāo)信息的半徑。

在本文中，形成的約束區(qū)域的頂點(diǎn)的坐標(biāo)，用有序組V來(lái)表示，記作V v1,v2,v3,v4,…；在約束區(qū)域頂點(diǎn)處廣播信標(biāo)信息的信標(biāo)組的有序集合，用有序組B來(lái)表示，記作B b1,b2,…,bi；相應(yīng)于有序組B中的信標(biāo)節(jié)點(diǎn)組的坐標(biāo)的有序集合，用有序組G來(lái)表示，記作G g1,g2,…,gi，其中i的范圍均為1≤i≤4。有序組中的元素對(duì)應(yīng)于約束區(qū)域頂點(diǎn)的順序是由左到右、由上到下。

初始化網(wǎng)絡(luò)時(shí)，假設(shè)root節(jié)點(diǎn)為信標(biāo)節(jié)點(diǎn)d，其現(xiàn)在所在的位置坐標(biāo)為(x,y)。信標(biāo)節(jié)點(diǎn)d以(x,y)為中心，以r為半徑進(jìn)行廣播，形成正方形的約束區(qū)域。約束區(qū)域四個(gè)頂點(diǎn)坐標(biāo)的集合可由信標(biāo)節(jié)點(diǎn)所在位置和通信半徑之間的關(guān)系得出。假設(shè)信標(biāo)節(jié)點(diǎn)組此時(shí)以有序組B a,b,c,d在四個(gè)頂點(diǎn)處分布，則當(dāng)四個(gè)信標(biāo)節(jié)點(diǎn)分別以當(dāng)前位置為中心，以r為半徑進(jìn)行廣播后，如果圖3所示的IV區(qū)域中存在一跳未被定位鄰居傳感器節(jié)點(diǎn)的數(shù)量最多，則根據(jù)BGM算法，用于確定信標(biāo)節(jié)點(diǎn)組下一時(shí)刻位置的信息為由此可以得出下一時(shí)刻信標(biāo)節(jié)點(diǎn)組將在坐標(biāo)處廣播信標(biāo)信息。如果信標(biāo)節(jié)點(diǎn)在移動(dòng)過(guò)程中遵循就近原則，可以使信標(biāo)節(jié)點(diǎn)組中的每個(gè)信標(biāo)節(jié)點(diǎn)，移動(dòng)路徑最短并且減小信標(biāo)節(jié)點(diǎn)的能量消耗。在圖3中，current beacon d的OSA是一個(gè)方形環(huán)，該方形環(huán)是由邊長(zhǎng)為2r，去掉具有相同質(zhì)心、邊長(zhǎng)為r的正方形得來(lái)的，所以在IV區(qū)域?qū)arget beacon的定位只需放置三個(gè)信標(biāo)節(jié)點(diǎn)在頂點(diǎn)處。依照就近原則，信標(biāo)節(jié)點(diǎn)b和c分別在正方形邊長(zhǎng)上移動(dòng)長(zhǎng)度為r的距離，保持信標(biāo)節(jié)點(diǎn)d位置不變，可以得到節(jié)點(diǎn)信標(biāo)組下一時(shí)刻，以為通信半徑廣播信標(biāo)信息的有序組為B b,c,d。

圖3 假設(shè)target beacon當(dāng)前位于由信標(biāo)節(jié)點(diǎn)d形成的IV約束區(qū)域內(nèi)

3.2.4 生成信標(biāo)樹(shù)算法

以上的算法描述了生成DFBT上的一個(gè)節(jié)點(diǎn)的過(guò)程，接下來(lái)詳細(xì)描述一下怎樣在網(wǎng)絡(luò)中生成一棵完整的DFBT。

算法循環(huán)：

步驟1統(tǒng)計(jì)current beacon S通信區(qū)域內(nèi)包含的普通傳感器節(jié)點(diǎn)未被定位的一跳鄰居節(jié)點(diǎn)的個(gè)數(shù)，匯總上報(bào)給current beacon S，經(jīng)過(guò)比較，S找出擁有一跳未被定位鄰居數(shù)最多的節(jié)點(diǎn)S′，將S′指定為S的target beacon，即S′為S的目標(biāo)孩子節(jié)點(diǎn)。

步驟2執(zhí)行EL算法，確定S′可能所在的區(qū)域，并將S′的估計(jì)位置放置在估計(jì)區(qū)域的質(zhì)心。升級(jí)S′為S。

步驟3重復(fù)以上步驟，直至S通信范圍內(nèi)不存在普通傳感器節(jié)點(diǎn)擁有一跳未被定位鄰居節(jié)點(diǎn)后停止，即當(dāng)前信標(biāo)節(jié)點(diǎn)S為這棵DFBT的葉子節(jié)點(diǎn)。

步驟4此時(shí)S將指向它的parent節(jié)點(diǎn)，即上級(jí)current beacon節(jié)點(diǎn)，查看它的parent節(jié)點(diǎn)的通信范圍內(nèi)的S′，對(duì)其執(zhí)行EL算法。

步驟5當(dāng)S發(fā)現(xiàn)自己沒(méi)有parent節(jié)點(diǎn)時(shí)，即S為root節(jié)點(diǎn)，算法終止。

生成信標(biāo)樹(shù)算法主旨是利用深度優(yōu)先遍歷的思想遍歷所有節(jié)點(diǎn)，所以其算法主要時(shí)間復(fù)雜度集中在深度優(yōu)先遍歷上，由此可得其時(shí)間復(fù)雜度大致為O()n，其中n為傳感器節(jié)點(diǎn)的個(gè)數(shù)。

網(wǎng)絡(luò)初始化時(shí)，S在root節(jié)點(diǎn)處開(kāi)始，根據(jù)DFT思想，通過(guò)不斷地執(zhí)行EL算法，在此過(guò)程中會(huì)生成一棵DFBT。當(dāng)全網(wǎng)節(jié)點(diǎn)都實(shí)現(xiàn)定位后，S會(huì)再回到root節(jié)點(diǎn)的位置。

在執(zhí)行EL算法時(shí)，S′周圍的未被定位的傳感器節(jié)點(diǎn)存在被定位的可能，這就會(huì)造成S通信范圍中的普通傳感器節(jié)點(diǎn)的未被定位的一跳鄰居節(jié)點(diǎn)數(shù)量處在一種變動(dòng)的狀態(tài)中；而對(duì)于已經(jīng)形成估計(jì)區(qū)域的傳感器節(jié)點(diǎn)，其估計(jì)區(qū)域的大小可能會(huì)隨著EL算法的執(zhí)行而減小，而這些并不通過(guò)執(zhí)行EL算法來(lái)減小估計(jì)區(qū)域的傳感器節(jié)點(diǎn)，在接下來(lái)的定位算法中很可能被升級(jí)為target beacon，并用來(lái)進(jìn)行輔助定位。綜上所述，為了減少定位時(shí)間成本和計(jì)算開(kāi)銷，在S通信范圍內(nèi)的每個(gè)有一跳未被定位鄰居節(jié)點(diǎn)的傳感器都會(huì)被生成一條記錄，在該記錄中存儲(chǔ)當(dāng)前未被定位的一跳鄰居節(jié)點(diǎn)的個(gè)數(shù)和當(dāng)前形成的估計(jì)區(qū)域的范圍。在執(zhí)行EL算法時(shí)，一旦發(fā)現(xiàn)S通信范圍內(nèi)的節(jié)點(diǎn)擁有的一跳未被定位的鄰居節(jié)點(diǎn)數(shù)量減少或者其相應(yīng)的估計(jì)區(qū)域減小，就將變化動(dòng)態(tài)地記錄下來(lái)。圖4描述了生成DFBT算法的基本流程。

圖4 生成DFBT算法的基本流程

4 仿真實(shí)驗(yàn)及分析

本章將對(duì)前面提出的GBT算法性能進(jìn)行相關(guān)仿真測(cè)評(píng)。與之比較的算法是：Snake-like算法和Randomwalk算法。

4.1 仿真環(huán)境設(shè)置

網(wǎng)絡(luò)仿真環(huán)境設(shè)置如下：監(jiān)測(cè)區(qū)域的大小為500×500units，其中隨機(jī)分布的傳感器節(jié)點(diǎn)的個(gè)數(shù)為100～300。網(wǎng)絡(luò)初始化時(shí)，在監(jiān)測(cè)區(qū)域的中心放置信標(biāo)節(jié)點(diǎn)組，并將其移動(dòng)速度設(shè)為定值。網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)的通信半徑均被設(shè)置為50。在何時(shí)廣播信標(biāo)節(jié)點(diǎn)信標(biāo)信息和普通節(jié)點(diǎn)何時(shí)發(fā)送message的問(wèn)題上，GBT算法中有相應(yīng)的規(guī)定，但是在Snake-like和Randomwalk算法中，并沒(méi)有對(duì)信標(biāo)節(jié)點(diǎn)和普通節(jié)點(diǎn)做出相應(yīng)要求，為了模擬實(shí)際情況，假定信標(biāo)節(jié)點(diǎn)的廣播信息和普通節(jié)點(diǎn)的messages都以相同的頻率發(fā)送，設(shè)定發(fā)送時(shí)間間隔為1+θ個(gè)仿真單位時(shí)間，θ的值是隨機(jī)的，取值范圍為[]

-0.3,+0.3。為了提高實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，在完成對(duì)網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的隨機(jī)部署后，每次都要將算法執(zhí)行50次，取其平均值進(jìn)行比較。在執(zhí)行Snake-like算法時(shí)，通過(guò)設(shè)定參數(shù)δ，用來(lái)調(diào)整Snake-like兩條遍歷軌跡之間的距離。

4.2 算法性能分析

（1）節(jié)點(diǎn)定位率隨定位時(shí)間的變化

如圖5所示，從整體來(lái)看，本文提出的GBT算法在定位率上要優(yōu)于Snake-like算法和Random-walk算法，并且最終總能達(dá)到全網(wǎng)定位。

圖5 節(jié)點(diǎn)的定位率隨定位時(shí)間增加的變化趨勢(shì)

這是因?yàn)镚BT算法是根據(jù)節(jié)點(diǎn)密度來(lái)規(guī)劃路徑的，通信范圍內(nèi)節(jié)點(diǎn)的密度越大，每次被定位的節(jié)點(diǎn)的數(shù)量就越多，相應(yīng)的定位率也就越大。

Snake-like算法，信標(biāo)節(jié)點(diǎn)能量一定，導(dǎo)致能夠遍歷的路徑長(zhǎng)度是一定的。因此，δ的值越大，遍歷路徑能夠覆蓋的監(jiān)測(cè)區(qū)域的面積就越大，能夠被定位的傳感器節(jié)點(diǎn)的個(gè)數(shù)也就越多，定位率也隨之增高。Randomwalk算法是三個(gè)算法中定位率最小的一個(gè)，并且此算法定位率的增長(zhǎng)趨勢(shì)又是最無(wú)規(guī)律的一個(gè)，因?yàn)樗亩ㄎ煌耆请S機(jī)的。

（2）信標(biāo)節(jié)點(diǎn)移動(dòng)總距離

如圖6所示，對(duì)于本文提出的GBT算法，隨著傳感器節(jié)點(diǎn)密度的增加，信標(biāo)節(jié)點(diǎn)移動(dòng)軌跡的總長(zhǎng)度趨于定值，這是由GBT算法的定位機(jī)制造成的。該算法的每次定位都是利用信標(biāo)節(jié)點(diǎn)廣播信標(biāo)信息所構(gòu)成的約束區(qū)域進(jìn)行的，所以當(dāng)節(jié)點(diǎn)密度達(dá)到某一數(shù)值后，所生成的DFBT的深度和各層所有節(jié)點(diǎn)的度數(shù)之和都會(huì)趨于定值，導(dǎo)致信標(biāo)節(jié)點(diǎn)的移動(dòng)軌跡總長(zhǎng)度也會(huì)趨于水平，達(dá)到定值。

圖6 信標(biāo)節(jié)點(diǎn)的總移動(dòng)距離隨節(jié)點(diǎn)密度增加的變化趨勢(shì)

對(duì)于Snake-like算法，信標(biāo)節(jié)點(diǎn)所擁有的能量值是確定的，其移動(dòng)路徑也是提前規(guī)劃好的。所以，無(wú)論傳感器節(jié)點(diǎn)在網(wǎng)絡(luò)中如何分布，信標(biāo)節(jié)點(diǎn)所能移動(dòng)的距離都是固定的。理論上講，Random-walk算法移動(dòng)距離應(yīng)該與Snake-like算法相等。但從實(shí)驗(yàn)結(jié)果來(lái)看，Randomwalk算法信標(biāo)節(jié)點(diǎn)移動(dòng)軌跡的總距離總是小于Snake-like算法的，并且其值不固定，會(huì)上下波動(dòng)。這是Randomwalk中信標(biāo)節(jié)點(diǎn)的不定向移動(dòng)消耗能量造成的。

（3）定位精度

為了表示全網(wǎng)的定位精度，使用平均定位誤差來(lái)刻畫(huà)算法的定位精度，同時(shí)為了計(jì)算簡(jiǎn)便，對(duì)公式（1）做出了簡(jiǎn)化處理，表示為這里的m指的是網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的個(gè)數(shù)。

如圖7所示，從整體上看，在定位精度上Snake-like和Random-walk算法是要低于GBT算法的。雖然三種算法定位的方式都是基于約束條件的，但GBT算法使用的是信標(biāo)節(jié)點(diǎn)組，并且信標(biāo)節(jié)點(diǎn)組廣播信標(biāo)信息的半徑是可變的，所以在信標(biāo)節(jié)點(diǎn)組對(duì)target beacon進(jìn)行定位時(shí)，可變的信標(biāo)廣播半徑增加了約束區(qū)域的多樣性，所以處在這些信標(biāo)節(jié)點(diǎn)組周圍的普通傳感器節(jié)點(diǎn)的定位精度會(huì)更高。GBT算法的定位精度受target beacon估計(jì)位置的影響，執(zhí)行EL算法的次數(shù)n越大，target beacon的估計(jì)位置越精確，繼而全網(wǎng)節(jié)點(diǎn)的定位平均錯(cuò)誤率就越低，定位精度也就越高。對(duì)于Snake-like和Random-walk算法，隨著網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)密度增大，隨之變化的是平均錯(cuò)誤率也在提升。而對(duì)于Snake-like算法，通過(guò)遍歷覆蓋的監(jiān)測(cè)區(qū)域面積大小與δ有關(guān)，隨著δ值的增長(zhǎng)，覆蓋區(qū)域越大，其間能夠定位的傳感器節(jié)點(diǎn)數(shù)就越多，平均定位錯(cuò)誤率相對(duì)較低。

（4）節(jié)點(diǎn)定位率與信標(biāo)節(jié)點(diǎn)能量開(kāi)銷的關(guān)系

如圖8所示，通常情況下，節(jié)點(diǎn)定位率會(huì)隨著信標(biāo)節(jié)點(diǎn)廣播信息次數(shù)的增加呈上升趨勢(shì)。信標(biāo)節(jié)點(diǎn)廣播信標(biāo)信息產(chǎn)生的能量消耗和節(jié)點(diǎn)在網(wǎng)絡(luò)中移動(dòng)產(chǎn)生的能量消耗是傳感器節(jié)點(diǎn)能量消耗的主要來(lái)源。GBT算法雖然也要廣播信標(biāo)信息，但是它們廣播信息的位置和移動(dòng)路徑是經(jīng)過(guò)計(jì)算的，并不是以某一固定頻率不斷發(fā)送，移動(dòng)方向不具有盲目性，并且當(dāng)完成對(duì)所有待定位節(jié)點(diǎn)的定位后，信標(biāo)節(jié)點(diǎn)隨即停止移動(dòng)，不再產(chǎn)生額外的能量消耗。所以從整體來(lái)看，當(dāng)節(jié)點(diǎn)能量消耗一定時(shí)，GBT算法的定位率是更加優(yōu)于Snake-like和Randomwalk算法的，并且隨著能量消耗的增加，會(huì)呈現(xiàn)出更加明顯的優(yōu)勢(shì)。對(duì)于Snake-like算法，δ的值越大，在相同能量消耗的情況下，定位率會(huì)越高。

圖7 節(jié)點(diǎn)的定位精度隨節(jié)點(diǎn)密度增加的變化趨勢(shì)

圖8 節(jié)點(diǎn)的定位率隨信標(biāo)節(jié)點(diǎn)能量開(kāi)銷增加的變化趨勢(shì)

圖9 節(jié)點(diǎn)的定位時(shí)間與網(wǎng)絡(luò)中節(jié)點(diǎn)密度分布的關(guān)系

（5）定位速度

如圖9所示，在實(shí)際環(huán)境中Snake-like和Randomwalk算法是無(wú)法實(shí)現(xiàn)全網(wǎng)絡(luò)所有節(jié)點(diǎn)定位的。所以在這里只討論在節(jié)點(diǎn)密度分布相同的情況下，Snake-like算法達(dá)到60%的節(jié)點(diǎn)定位率，Random-walk算法達(dá)到25%的節(jié)點(diǎn)定位率和GBT算法達(dá)到全網(wǎng)節(jié)點(diǎn)定位各自所需的時(shí)間。圖9中橫坐標(biāo)表示的是網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的數(shù)量與監(jiān)測(cè)區(qū)域面積的關(guān)系，例如80%-70%表示的是網(wǎng)絡(luò)中80%的傳感器節(jié)點(diǎn)分布在70%的監(jiān)測(cè)區(qū)域中。

觀察圖中曲線的走向可以得出，隨著網(wǎng)絡(luò)中節(jié)點(diǎn)密度的增加，GBT算法實(shí)現(xiàn)全網(wǎng)節(jié)點(diǎn)定位所需的時(shí)間隨之減小，說(shuō)明定位速度越來(lái)越快。在相同節(jié)點(diǎn)密度的條件下，Snake-like算法達(dá)到60%節(jié)點(diǎn)定位率和Random-walk算法達(dá)到25%節(jié)點(diǎn)定位率所花費(fèi)的時(shí)間是要高于GBT算法達(dá)到全網(wǎng)節(jié)點(diǎn)定位所花費(fèi)的時(shí)間的，出現(xiàn)這種現(xiàn)象的原因是這兩種算法在進(jìn)行節(jié)點(diǎn)定位時(shí)，沒(méi)有將網(wǎng)絡(luò)中的節(jié)點(diǎn)密度作為參考依據(jù)，很可能將許多時(shí)間和能量都消耗在節(jié)點(diǎn)稀疏的區(qū)域。δ的值同樣對(duì)Snake-like算法的定位率有影響，隨著δ值的越大，達(dá)到相同定位率所需的時(shí)間會(huì)越短。

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

文中提出了一種使用動(dòng)態(tài)信標(biāo)節(jié)點(diǎn)組進(jìn)行定位的自適應(yīng)算法GBT。該算法中的信標(biāo)節(jié)點(diǎn)組具有可移動(dòng)性、廣播通信半徑可變的特點(diǎn)，借鑒圖的深度優(yōu)先遍歷思想，通過(guò)收集比較網(wǎng)絡(luò)中節(jié)點(diǎn)的一跳未被定位的鄰居節(jié)點(diǎn)的數(shù)量，以此來(lái)生成一棵具有動(dòng)態(tài)自適應(yīng)的深度優(yōu)先信標(biāo)樹(shù)DFBT，通過(guò)其來(lái)規(guī)劃信標(biāo)節(jié)組的移動(dòng)路徑。通過(guò)該算法可以實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的定位工作，并且在節(jié)點(diǎn)的定位時(shí)間，定位精度和信標(biāo)節(jié)點(diǎn)能量的最大化利用等問(wèn)題上都有較大的改善。為了進(jìn)一步地減少定位時(shí)間，加快網(wǎng)絡(luò)的收斂速度，如何在GBT算法的基礎(chǔ)上做出改進(jìn)，論證多信標(biāo)樹(shù)協(xié)同定位，是接下來(lái)要研究的主要任務(wù)。

[1] Chen J，Xu W，He S，et al.Utility-based asynchronous flow control algorithm for wireless sensor networks[J].IEEE Journal on Selected Areas in Communications，2010，28（7）：1116-1126.

[2] He Shibo，Chen Jiming，Sun Youxian，et al.On optimal information capture by energy-constrained mobile sensors[J].IEEE Transactions on Vehicular Technology，2010，59（5）：2472-2484.

[3] 景博，張劼，孫勇.智能網(wǎng)絡(luò)傳感器與無(wú)線傳感器網(wǎng)絡(luò)[M].北京：國(guó)防工業(yè)出版社，2011.

[4] 王汝傳，孫麗娟.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].北京：人民郵電出版社，2011.

[5] 余成波，李洪兵，陶紅艷.無(wú)線傳感器網(wǎng)絡(luò)實(shí)用教程[M].北京：清華大學(xué)出版社，2012.

[6] Kwon O，Lee E，Bahn H.Sensor-aware elevator scheduling for smart building environments[J].Building and Environment，2014，72：332-342.

[7] Bottero M，Chiara B D，Deflorio F P.Wireless sensor networks for traffic monitoring in a logistic centre[J].Transportation Research Part C，2013，26：99-124.

[8] Bhuiyan M Z A，Wang Guojun，Cao Jiannong，et al.Deploying wireless sensor networks with fault-tolerance for structural health monitoring[J].IEEE Transactions on Computers，2015，64（2）：382-395.

[9] Halder S，Ghosal A.A survey on mobile anchor assisted localizationtechniquesinwirelesssensornetworks[J].Wireless Networks，2015，60（7）：1-20.

[10] Chang C T，Chang C Y.Anchor-guiding mechanism for beacon-assisted localization in wireless sensor networks[J].IEEE Sensors Journal，2012，12（5）：1098-1111.

[11] Cui Huanqing，Wang Yinglong.Four-mobile-beacon assisted localization in three-dimensional wireless sensor networks[J].Computers and Electrical Engineering，2012，38：652-661.

[12] Li X，Mitton N，Simplot-Ryl I，et al.Dynamic beacon mobility scheduling for sensor localization[J].IEEE Transactions on Parallel and Distributed Systems，2012，23（8）：1439-1452.

[13] Guo Z，Guo Y，Hong F，Perpendicular intersection：Locating wireless sensors with mobile beacon[J].IEEE Transactions on Vehicular Technology，2010，59（7）：3501-3509.

[14] Ou C H，He W L.Path planning algorithm for mobile anchor-based localization in wireless sensor networks[J].IEEE Sensors Journal，2013，13（2）：466-475.

[15] Iqbaln A，Murshed M.On demand-driven movement strategy for moving beacons in sensor localization[J].Journal of Network and Computer Applications，2014，44（9）：46-62.

[16] Rezazadeh J，Moradi M，Ismail A S，et al.Superior path planning mechanism for mobile beacon-assisted localizationinwirelesssensornetworks[J].IEEESensors Journal，2014，14（9）：3052-3064.

[17] 鄧彬偉，黃光明.WSN中的質(zhì)心定位算法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2010，27（1）：213-214.

ZHAO Yihong,WANG Ze,ZHANG Haijuan.Dynamic beacon spanning tree algorithm for sensor localization.Computer Engineering andApplications,2018,54（6）：68-74.

ZHAO Yihong,WANG Ze,ZHANG Haijuan

School of Computer Science&Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China

Node localization in wireless sensor networks is a basic but very important research field.In practical application,sensor nodes are distributed randomly resulting in node density disproportion in the region.The existing localization algorithms of node are not sensitive to distribution density.Hence,if the algorithm applies the same strategy to locate nodes in regions with different node density,it will cause position accuracy low in dense area and location rate decreasing in sparse regions and the beacon node energy is not to maximize utilization.This paper puts forward a spanning tree algorithm of beacon based on node distribution density called GBT.Nodes in beacon group are traversed by planned path to complete node location.The simulation results show that the improved algorithm has better performance on decreasing time expend for locating node,enhancing accuracy of node location by taking advantage of beacon efficiently compared with previous algorithms.

wireless sensor networks;sensor localization;dynamic beacon node;route planning;node density;Generate Beacon-based Tree（GBT）algorithm

節(jié)點(diǎn)定位是無(wú)線傳感器網(wǎng)絡(luò)中一個(gè)基礎(chǔ)但十分重要的研究方向。實(shí)際應(yīng)用場(chǎng)景中，傳感器節(jié)點(diǎn)大多被隨機(jī)部署，分布往往疏密不均?，F(xiàn)存的定位算法對(duì)節(jié)點(diǎn)的分布密度沒(méi)有敏感性，如果算法在節(jié)點(diǎn)密集區(qū)域和稀疏區(qū)域使用相同的定位策略，就會(huì)造成密度大的區(qū)域定位精度低，分布相對(duì)稀疏的區(qū)域定位率低，信標(biāo)節(jié)點(diǎn)的能量得不到最大化利用等問(wèn)題。針對(duì)這些問(wèn)題，提出了一種基于節(jié)點(diǎn)密度進(jìn)行定位的生成信標(biāo)樹(shù)算法（GBT）。信標(biāo)節(jié)點(diǎn)組沿著規(guī)劃好的路徑對(duì)節(jié)點(diǎn)進(jìn)行遍歷，實(shí)現(xiàn)節(jié)點(diǎn)的全定位。通過(guò)與其他規(guī)劃動(dòng)態(tài)信標(biāo)節(jié)點(diǎn)路徑算法比較，證明了GBT算法在定位時(shí)間、定位精度和對(duì)信標(biāo)節(jié)點(diǎn)能量的充分利用上均有所改善。

無(wú)線傳感器網(wǎng)絡(luò)；傳感器節(jié)點(diǎn)定位；動(dòng)態(tài)信標(biāo)節(jié)點(diǎn)；路徑規(guī)劃；節(jié)點(diǎn)密度；生成信標(biāo)樹(shù)算法

2016-10-31

2017-01-02

1002-8331（2018）06-0068-07

A

TP393

10.3778/j.issn.1002-8331.1610-0392

國(guó)家自然科學(xué)基金（No.60970016）；天津市自然科學(xué)基金（No.11JCYBJC00800）；天津市科技重大專項(xiàng)與工程項(xiàng)目（No.15ZXHLGX00390）。

趙怡宏（1988—），男，碩士，主研領(lǐng)域：無(wú)線傳感器定位，E-mail：332851167@qq.com；王賾（1976—），男，博士，副教授，主研方向：計(jì)算機(jī)網(wǎng)絡(luò)與安全，企業(yè)信息化，多媒體通信等；張海娟（1990—），女，碩士，主研方向：無(wú)線傳感器定位。