無線傳感器網絡定位理論和算法研究

趙立新

摘 要：無線傳感器網絡在目前社會發展和個人生活中有著廣泛的應用，作為無線傳感器網絡設計實現及應用當中的關鍵組成部分，定位技術承擔了提供位置信息服務的重要作用，屬于無線傳感器網絡的支撐技術之一。本文首先對無線傳感器網絡定位理論進行敘述，分析了目前定位系統及算法的不足，然后結合當前典型定位算法設計思想及適用范圍，對其網絡定位理論及算法的未來研究方向進行探索。

關鍵詞：無線傳感網絡 定位理論 算法

中圖分類號：TP212.9 文獻標識碼：A 文章編號：1672-3791（2018）03（b）-0007-02

無線傳感網絡能夠實現物理世界與網絡世界的相互連接，目前廣泛應用于軍事與民用領域，為了提高傳感器在外界信息獲取的準確程度，形成具體的物理事件，需要采取定位算法來實現精準定位，但是在某些特定領域的定位計算中仍舊存在一定的誤差，同時忽略了各節點之間可能存在的潛在聯系，影響定位結果的精度。基于以上情況，需要在對無線傳感器網絡定位理論進行分析的基礎上，研究高性能定位算法，保證定位結果的精確程度。

1 無線傳感網絡和定位技術概述

1.1 無線傳感網絡

無線傳感網絡是由部署在需要監控區域中大量微型傳感器節點所形成的，根據實際檢測需求，這些傳感器由人工或者飛機播撒的方式進行部署，其主要作用是對該區域感知對象的信息進行采集，然后通過無線網絡將所收集到的信息傳輸給觀察者。無線傳感網絡主要包括檢測節點、匯聚節點、網絡和終端[1]。對于傳感器網絡節點來說，其作用包括數據采集、數據處理、數據傳輸和電源，根據檢測需求，監測節點中傳感器包括溫度、濕度、振動、壓力和熱量等模塊。

1.2 定位技術

定位技術在監測節點中起著至關重要的作用，依靠定位技術，能夠準確獲得位置信息，沒有位置信息的監測數據無法解釋成具體物理事件，缺乏可用性。在另外一個方面，定位技術也可以為其他網絡模塊提供服務，比如：采用定位技術輔助路由，路由表不需要節點進行儲存和維護，從而實現無狀態路由。總的來說，由于節點無法準確獲得自身的位置，所以需要在部署傳感器之后進行實時準確的定位，而定位技術就是根據一些已知的位置節點，按照特定算法計算出自身位置的過程[2]。

2 定位技術基本概念

2.1 錨節點

錨節點也被稱為信標節點，指的是能夠直接獲取自身位置信息的節點。

2.2 未知節點

除了錨節點之外的節點被稱為未知節點。當此節點需要特殊定位的情況下，未知節點也被稱為目標節點。一些定位成功的未知節點也被稱為偽錨節點。

2.3 參考節點

當對某些節點進行定位的時候，需要借助其臨近節點位置信息來進行，這樣的節點就是參考節點。錨節點和未知節點都可以作為參考節點來使用[3]。

2.4 測距圖

測距圖G一般用來表示給定網絡，測距信息G=（V，E），其中的V是網絡節點，邊（i，j）∈E為i節點與j節點之間的距離。通過V節點與E來表示測距信息，通過這兩個信息獲得未知節點的位置，這個圖G就是測距圖。

2.5 可定位網絡

針對對應的定位問題，一個定位成功的網絡是可解的。

2.6 可定位節點

在給定網絡及相應測距圖的基礎上，通過錨節點和測距信息獲得最大可定位節點，這樣的節點就被成為可定位節點，其他節點為不可定位節點，這些不可定位節點不能用任何定位算法進行定位[4]。

2.7 定位問題

在給定網絡和測距圖的情況下，計算可定位節點物理位置的問題就是定位問題。

2.8 定位算法性能。

給定網絡和測距圖，定位問題能夠采用這個定位算法順利解決，其性能就是根據定位可定位節點的比例來確定的。

3 無線傳感器網絡定位理論分析

3.1 定位理論基本定義

根據以上定位技術的基本定義可以看出，在給定網絡與測距圖的情況下，通過錨節點與測距信息，來對臨近節點進行定位，并且將已經定位的節點當作參考節點，進行下一次的未知節點定位，直到成功定位所有可定位節點為止，這樣重復的定位過程顯得更加復雜，在此基礎上，如果錨節點和測距信息不能同時獲得，或者得到的信息并不精準，相應定位問題將變得更加復雜。當前普遍通過剛性理論描述網絡可定位性，相關定義如下：

（1）基礎圖。在測距圖GN中的邊合集EN中增加所有錨節點所連接的邊，所得出的G'N=V，EN∪（i，j），這樣圖就是基礎圖。

（2）剛性。測距圖頂點間距離不改變的情況下，不能連續進行形變，說明此圖是剛性的。

（3）冗余剛性。在圖G為剛性的情況下，刪除途中任何一條邊，圖G仍然是剛性的，說明圖G是冗余剛性。

（4）點行。在基礎圖當中，d維空間中點的合集定義為P，所對應的點形為Fp，Fp=（p，L），L為對應基礎圖邊合集的鏈接合集。點形Fp只能確定唯一基礎圖，以此來表示點與點之間的連接屬性[5]。

3.2 網絡可定位條件分析

結合以上定位..理論基本定義中的剛性理論，可以知道網絡可定位的條件包括這些方面：在給定d（d=2，3）維空間網絡N的情況下，包括m個錨節點，對應位置為p，其中包括n—m個錨節點，表示為（m+1），（m+2）···，n，對應位置P為Pm+1，Pm+2···，Pn，如果d=3，m≥4，可以用典型Fp來表示網絡N，這樣的網絡N能夠被定位，同時對于Fp是剛性的。但是，在二維空間d中，同樣存在一些特殊情況，能夠使剛性圖不完全滿足剛性，這樣的特殊情況包括翻轉和折轉，針對折轉來說，網絡N中的一些錨節點翻轉到鏡像位置，從而發生形變，導致剛性圖不能完全滿足剛性。

4 無線傳感器網絡定位算法分析

目前關于無線傳感器網絡定位算法的研究有很多，根據定位需求選擇不同的定位算法，結合定位過程，對節點之間的距離進行測量是不是必要的，目前的定位算法可以分成基于硬件測距的定位算法和不需要硬件測距的定位算法。

4.1 基于硬件測距的定位算法

基于硬件測距的定位算法，是一種測量節點之間距離來進行定位的，而硬件測距工具和相關測量技術決定了定位精度，主要體現在以下幾個方面。

（1）基于時間測距的定位。基于時間測距的定位技術，也就是通過無線信號的傳播時間，和已知無線信號傳播速度，計算兩個節點之間的距離，也就是信號發射到信號接收之間的距離，然后對錨節點距離進行計算，從而得出相應的參考節點，目前基于時間測距的定位算法包括三邊測量法[6]。目前這種算法是最常用的定位算法，其主要原因是對成本和硬件要求較低，但是影響測距精度的因素有很多，首先，大氣環境條件會影響無線信號傳播速度，噪聲、傳播路徑和環境差異也會在一定程度上影響測量精確度，所以，在采用此方法進行測量的情況下，需要在最大程度上控制好環境及硬件測量工具條件，以此來有效提高定位精度。

（2）基于到達時間差距的定位技術。這種定位技術與基于時間測距定位技術有著相似之處，主要是通過兩種速率不同信號的傳輸時間差，結合其傳輸速度，來對節點之間的距離進行測定，其算法體如下。

比如兩種不同速度的信號被同時發出，速度為C1、C2、接收器接收信號到達時間為T1、T2、兩節點之間距離測定公式為：

（T2-T1）×（C1C2/C1-C2） （1）

基于信號強度測距的定位技術。從信號發射器發射相應無線信號，記錄信號發射時的強度，然后在接收到信號時候，將其信號強度與信號發射強度進行對比，結合信號傳播衰減模型，計算信號傳輸損耗規律，從而得出兩個節點之間的距離。在有相關模型的情況下，這樣的定位技術較為簡單，但是容易受到非視距和噪聲的影響，適合精度要求低的節點定位。

4.2 基于非硬件測距的定位算法

4.2.1 質心算法

質心為幾何多邊形的中心，質心坐標位置就是多邊形定點坐標的平均值，假設質心坐標為（x，y），多邊形A、B、C、D、E的頂點坐標分別為A（x1，y1），B（x2，y2），C（x3，y3），D（x4，y4），E（x5，y5），質心坐標（x，y）=（x1+x2+x3+x4+x5/5，y1+y2+y3+y4+y5/5）。在進行質心算法的過程中，Anchor node能夠不斷地向鄰近節點發送信息，包括Anchor node的位置信息，在對這些信息進行接收的過程中，會設置相應閾值，當不符合閾值要求的情況下，能夠自動停止接收數據，根據接收到的坐標位置信息，根據以上公式進行計算，得出質心坐標，也就是錨節點的位置。

4.2.2 基于DC的定位算法

DC（delaunay complex）是三角剖分的擴展，DC能夠對整個網絡進行劃分，在網絡是完全剛性的情況下，可以先對網絡邊界和中軸進行識別，然后選取地標節點，構建相應的DC，進行平面鑲入，最后結合節點位置，實現節點定位。

5 結語

定位技術在無線傳感網絡中占據了非常終于重要的位置，需要根據實際適用領域需求，選擇合適的定位算法，當前定位算法仍舊存在著算法定位能力與理論上限處于同一水平、復雜程度過高、精確程度不足和誤差處理影響性能等問題，結合定位算法剛性理論，未來的定位算法存在極大研究空間，期待定位算法的提升完善能夠推動無線傳感網絡的快速發展。

參考文獻

[1] 王小平，羅軍，沈昌祥.無線傳感器網絡定位理論和算法[J].計算機研究與發展，2011，48（3）：353-363.

[2] 王剛剛，王正.無線傳感器網緒定位算法原理與研究進展概述[J].木工機床，2016（2）：18-20.

[3] 張可.無線傳感器網絡分布式定位算法研究[D].燕山大學，2012.

[4] 宮月.無線傳感器網絡定位算法研究[D].華北電力大學，2013.

[5] 李牧東，熊偉，梁青，等.無線傳感器網絡DV-Hop定位算法研究[J].空軍工程大學學報：自然科學版，2012，13（4）：75-79.

[6] 張欣慧，徐晶晶，許必宵，等.無線傳感器網絡三維定位算法研究[J].計算機技術與發展，2016，26（12）：195-199.