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

趙怡宏，王賾，張海娟

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

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

趙怡宏，王賾，張海娟

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

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

1 引言

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

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

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

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

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

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

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

2.1 Snake-like算法

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

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

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

2.2 Random-walk算法

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

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

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

3 動態(tài)信標(biāo)生成樹算法

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

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

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

3.2 算法設(shè)計

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

3.2.1 選舉root節(jié)點

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

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

3.2.2 估計位置算法

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

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

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

（3）計算target beacon的估計位置。

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

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

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

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

圖2 current beacon形成的OSA

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

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

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

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

3.2.3 信標(biāo)節(jié)點組移動算法

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

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

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

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

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

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

算法循環(huán)：

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

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

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

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

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

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

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

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

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

4 仿真實驗及分析

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

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

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

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

4.2 算法性能分析

（1）節(jié)點定位率隨定位時間的變化

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

圖5 節(jié)點的定位率隨定位時間增加的變化趨勢

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

Snake-like算法，信標(biāo)節(jié)點能量一定，導(dǎo)致能夠遍歷的路徑長度是一定的。因此，δ的值越大，遍歷路徑能夠覆蓋的監(jiān)測區(qū)域的面積就越大，能夠被定位的傳感器節(jié)點的個數(shù)也就越多，定位率也隨之增高。Randomwalk算法是三個算法中定位率最小的一個，并且此算法定位率的增長趨勢又是最無規(guī)律的一個，因為它的定位完全是隨機的。

（2）信標(biāo)節(jié)點移動總距離

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

圖6 信標(biāo)節(jié)點的總移動距離隨節(jié)點密度增加的變化趨勢

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

（3）定位精度

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

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

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

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

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

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

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

（5）定位速度

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

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

5 結(jié)束語

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

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

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

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

2016-10-31

2017-01-02

1002-8331（2018）06-0068-07

A

TP393

10.3778/j.issn.1002-8331.1610-0392

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

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