基于動態信標生成樹的傳感器定位算法

趙怡宏，王賾，張海娟

天津工業大學計算機科學與軟件學院，天津300387

基于動態信標生成樹的傳感器定位算法

趙怡宏，王賾，張海娟

天津工業大學計算機科學與軟件學院，天津300387

CNKI網絡出版：2017-03-13,http://kns.cnki.net/kcms/detail/11.2127.TP.20170313.1638.022.html

1 引言

近年來，隨著微機電系統（MEMS）、無線通信技術及傳感器技術的發展和相互融合，無線傳感器網絡（Wireless Sensor Networks，WSNs）[1-2]日趨成熟。WSNs是集信息采集、傳輸、處理于一體的綜合智能信息系統，具有廣闊的應用發展前景。傳感器節點具有傳感、驅動控制、計算及通信能力，能夠實時監測、感知和采集目標區域中監測對象的各種信息，從而實現計算機世界、物理世界以及人類社會三元世界的連通[3-5]。WSNs憑借其節點體積小、成本低、功耗低、自組網絡等優勢，已被廣泛應用在軍事領域、環境監測、工農業、生物醫療、智能交通等各個領域[6-8]。

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

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

針對上述問題，文中提出了基于網絡節點密度來定位的生成信標樹算法（GBT）。GBT算法的主旨思想主要來源于圖的深度優先遍歷（DFT），在網絡中構建一個信標節點組，通過對當前信標節點廣播區域內傳感器節點的一跳未被定位的鄰居節點的個數的比較，在網絡中動態生成一棵深度優先信標樹（DFBT），以此來規劃信標節點組的移動路徑，從而達到全網節點的精確定位。

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

2 傳統的動態信標節點輔助定位算法

動態信標節點可以在網絡中任意移動，通過使用內嵌的GPS或者其他定位系統對自己的位置進行感知，然后在網絡中以特定的頻率或在設計好的位置進行包含自己地理位置信息的信標信息的廣播[10-11]。網絡中的待定位普通傳感器節點通過接收信標節點廣播的信標信息對自己進行定位[13]。

2.1 Snake-like算法

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

圖1 信標節點在監測區域內使用Snake-like算法生成的遍歷軌跡

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

2.2 Random-walk算法

Random-walk算法，該算法模型較為簡單，將信標節點隨機部署在一個監測區域內。將信標節點的移動速度和信標信息廣播包的發送頻率設為定值，但是信標節點的移動方向是隨機的。

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

針對傳統動態信標節點輔助定位算法存在的問題，本文引入了基于節點密度的定位算法。下一章將對該算法進行詳細的介紹。

3 動態信標生成樹算法

3.1 網絡模型描述

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

網絡中的每個節點都會有自己唯一相應的ID，以此來對不同的傳感器節點進行區分。通過發送“Hello”信息，傳感器節點以此來維護它們之間的鄰居關系。在定位過程中，傳感器節點之間會發送含有特定定位信息的message以此來進行定位[12]。

3.2 算法設計

基于節點密度定位算法的主旨思想是：根據網絡節點密度分布，規劃信標節點組的移動路徑，從而完成對網絡中所有節點的精確定位。該算法主要借鑒的思想是圖的深度優先遍歷（Depth-First Traversal，DFT），設計了生成信標樹算法（Generate Beacon-based Tree，GBT），在網絡中動態地生成一棵深度優先信標樹（Depth-First Beacon-based Tree，DFBT），從而指導信標節點組進行移動。這棵信標樹上除根節點root外的其余節點，均需要調用估計位置算法（Estimate Location，EL）和信標節點組移動算法（Beacon Group Moving，BGM）。

3.2.1 選舉root節點

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

如果信標節點在相同時刻發現存在數量大于1的未被定位的普通節點，則通信范圍內節點數最多的信標節點被指定為root；如果發現時間和數量都相同，則隨機選取任一信標節點為root。

3.2.2 估計位置算法

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

（1）確定目標統計區域（Object Statistical Area，OSA），找出下級目標信標節點（target beacon）。

（2）確定target beacon的估計區域。

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

為了實現以網絡節點密度為參考依據來對全網節點完成定位，GBT算法需要統計對比current beacon的OSA內，普通節點周圍未被定位的一跳鄰居的數量，從而保證信標節點組總是朝著待定位節點分布最為稠密區域的方向移動。current beacon代表的是當前需要廣播信標信息來輔助定位的普通傳感器節點。

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

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

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

圖2 current beacon形成的OSA

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

當current beacon為root節點時，可以得出EL算法的執行次數和target beacon估計區域之間的關系，如表1所示。

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

表1 當current beacon為root節點時，EL算法的執行次數n和target beacon估計區域大小之間的關系

3.2.3 信標節點組移動算法

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

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

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

圖3 假設target beacon當前位于由信標節點d形成的IV約束區域內

3.2.4 生成信標樹算法

以上的算法描述了生成DFBT上的一個節點的過程，接下來詳細描述一下怎樣在網絡中生成一棵完整的DFBT。

算法循環：

步驟1統計current beacon S通信區域內包含的普通傳感器節點未被定位的一跳鄰居節點的個數，匯總上報給current beacon S，經過比較，S找出擁有一跳未被定位鄰居數最多的節點S′，將S′指定為S的target beacon，即S′為S的目標孩子節點。

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

步驟3重復以上步驟，直至S通信范圍內不存在普通傳感器節點擁有一跳未被定位鄰居節點后停止，即當前信標節點S為這棵DFBT的葉子節點。

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

步驟5當S發現自己沒有parent節點時，即S為root節點，算法終止。

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

網絡初始化時，S在root節點處開始，根據DFT思想，通過不斷地執行EL算法，在此過程中會生成一棵DFBT。當全網節點都實現定位后，S會再回到root節點的位置。

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

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

4 仿真實驗及分析

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

4.1 仿真環境設置

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

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

4.2 算法性能分析

（1）節點定位率隨定位時間的變化

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

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

這是因為GBT算法是根據節點密度來規劃路徑的，通信范圍內節點的密度越大，每次被定位的節點的數量就越多，相應的定位率也就越大。

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

（2）信標節點移動總距離

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

圖6 信標節點的總移動距離隨節點密度增加的變化趨勢

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

（3）定位精度

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

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

（4）節點定位率與信標節點能量開銷的關系

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

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

圖8 節點的定位率隨信標節點能量開銷增加的變化趨勢

圖9 節點的定位時間與網絡中節點密度分布的關系

（5）定位速度

如圖9所示，在實際環境中Snake-like和Randomwalk算法是無法實現全網絡所有節點定位的。所以在這里只討論在節點密度分布相同的情況下，Snake-like算法達到60%的節點定位率，Random-walk算法達到25%的節點定位率和GBT算法達到全網節點定位各自所需的時間。圖9中橫坐標表示的是網絡中傳感器節點的數量與監測區域面積的關系，例如80%-70%表示的是網絡中80%的傳感器節點分布在70%的監測區域中。

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

5 結束語

文中提出了一種使用動態信標節點組進行定位的自適應算法GBT。該算法中的信標節點組具有可移動性、廣播通信半徑可變的特點，借鑒圖的深度優先遍歷思想，通過收集比較網絡中節點的一跳未被定位的鄰居節點的數量，以此來生成一棵具有動態自適應的深度優先信標樹DFBT，通過其來規劃信標節組的移動路徑。通過該算法可以實現對網絡中所有節點的定位工作，并且在節點的定位時間，定位精度和信標節點能量的最大化利用等問題上都有較大的改善。為了進一步地減少定位時間，加快網絡的收斂速度，如何在GBT算法的基礎上做出改進，論證多信標樹協同定位，是接下來要研究的主要任務。

[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] 景博，張劼，孫勇.智能網絡傳感器與無線傳感器網絡[M].北京：國防工業出版社，2011.

[4] 王汝傳，孫麗娟.無線傳感器網絡技術與應用[M].北京：人民郵電出版社，2011.

[5] 余成波，李洪兵，陶紅艷.無線傳感器網絡實用教程[M].北京：清華大學出版社，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中的質心定位算法研究[J].計算機應用與軟件，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

節點定位是無線傳感器網絡中一個基礎但十分重要的研究方向。實際應用場景中，傳感器節點大多被隨機部署，分布往往疏密不均。現存的定位算法對節點的分布密度沒有敏感性，如果算法在節點密集區域和稀疏區域使用相同的定位策略，就會造成密度大的區域定位精度低，分布相對稀疏的區域定位率低，信標節點的能量得不到最大化利用等問題。針對這些問題，提出了一種基于節點密度進行定位的生成信標樹算法（GBT）。信標節點組沿著規劃好的路徑對節點進行遍歷，實現節點的全定位。通過與其他規劃動態信標節點路徑算法比較，證明了GBT算法在定位時間、定位精度和對信標節點能量的充分利用上均有所改善。

無線傳感器網絡；傳感器節點定位；動態信標節點；路徑規劃；節點密度；生成信標樹算法

2016-10-31

2017-01-02

1002-8331（2018）06-0068-07

A

TP393

10.3778/j.issn.1002-8331.1610-0392

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

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