無線傳感器網(wǎng)絡(luò)定位理論和算法研究

趙立新

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

關(guān)鍵詞：無線傳感網(wǎng)絡(luò) 定位理論 算法

中圖分類號：TP212.9 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2018）03（b）-0007-02

無線傳感網(wǎng)絡(luò)能夠?qū)崿F(xiàn)物理世界與網(wǎng)絡(luò)世界的相互連接，目前廣泛應(yīng)用于軍事與民用領(lǐng)域，為了提高傳感器在外界信息獲取的準(zhǔn)確程度，形成具體的物理事件，需要采取定位算法來實現(xiàn)精準(zhǔn)定位，但是在某些特定領(lǐng)域的定位計算中仍舊存在一定的誤差，同時忽略了各節(jié)點(diǎn)之間可能存在的潛在聯(lián)系，影響定位結(jié)果的精度。基于以上情況，需要在對無線傳感器網(wǎng)絡(luò)定位理論進(jìn)行分析的基礎(chǔ)上，研究高性能定位算法，保證定位結(jié)果的精確程度。

1 無線傳感網(wǎng)絡(luò)和定位技術(shù)概述

1.1 無線傳感網(wǎng)絡(luò)

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

1.2 定位技術(shù)

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

2 定位技術(shù)基本概念

2.1 錨節(jié)點(diǎn)

錨節(jié)點(diǎn)也被稱為信標(biāo)節(jié)點(diǎn)，指的是能夠直接獲取自身位置信息的節(jié)點(diǎn)。

2.2 未知節(jié)點(diǎn)

除了錨節(jié)點(diǎn)之外的節(jié)點(diǎn)被稱為未知節(jié)點(diǎn)。當(dāng)此節(jié)點(diǎn)需要特殊定位的情況下，未知節(jié)點(diǎn)也被稱為目標(biāo)節(jié)點(diǎn)。一些定位成功的未知節(jié)點(diǎn)也被稱為偽錨節(jié)點(diǎn)。

2.3 參考節(jié)點(diǎn)

當(dāng)對某些節(jié)點(diǎn)進(jìn)行定位的時候，需要借助其臨近節(jié)點(diǎn)位置信息來進(jìn)行，這樣的節(jié)點(diǎn)就是參考節(jié)點(diǎn)。錨節(jié)點(diǎn)和未知節(jié)點(diǎn)都可以作為參考節(jié)點(diǎn)來使用[3]。

2.4 測距圖

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

2.5 可定位網(wǎng)絡(luò)

針對對應(yīng)的定位問題，一個定位成功的網(wǎng)絡(luò)是可解的。

2.6 可定位節(jié)點(diǎn)

在給定網(wǎng)絡(luò)及相應(yīng)測距圖的基礎(chǔ)上，通過錨節(jié)點(diǎn)和測距信息獲得最大可定位節(jié)點(diǎn)，這樣的節(jié)點(diǎn)就被成為可定位節(jié)點(diǎn)，其他節(jié)點(diǎn)為不可定位節(jié)點(diǎn)，這些不可定位節(jié)點(diǎn)不能用任何定位算法進(jìn)行定位[4]。

2.7 定位問題

在給定網(wǎng)絡(luò)和測距圖的情況下，計算可定位節(jié)點(diǎn)物理位置的問題就是定位問題。

2.8 定位算法性能。

給定網(wǎng)絡(luò)和測距圖，定位問題能夠采用這個定位算法順利解決，其性能就是根據(jù)定位可定位節(jié)點(diǎn)的比例來確定的。

3 無線傳感器網(wǎng)絡(luò)定位理論分析

3.1 定位理論基本定義

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

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

（2）剛性。測距圖頂點(diǎn)間距離不改變的情況下，不能連續(xù)進(jìn)行形變，說明此圖是剛性的。

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

（4）點(diǎn)行。在基礎(chǔ)圖當(dāng)中，d維空間中點(diǎn)的合集定義為P，所對應(yīng)的點(diǎn)形為Fp，F(xiàn)p=（p，L），L為對應(yīng)基礎(chǔ)圖邊合集的鏈接合集。點(diǎn)形Fp只能確定唯一基礎(chǔ)圖，以此來表示點(diǎn)與點(diǎn)之間的連接屬性[5]。

3.2 網(wǎng)絡(luò)可定位條件分析

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

4 無線傳感器網(wǎng)絡(luò)定位算法分析

目前關(guān)于無線傳感器網(wǎng)絡(luò)定位算法的研究有很多，根據(jù)定位需求選擇不同的定位算法，結(jié)合定位過程，對節(jié)點(diǎn)之間的距離進(jìn)行測量是不是必要的，目前的定位算法可以分成基于硬件測距的定位算法和不需要硬件測距的定位算法。

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

基于硬件測距的定位算法，是一種測量節(jié)點(diǎn)之間距離來進(jìn)行定位的，而硬件測距工具和相關(guān)測量技術(shù)決定了定位精度，主要體現(xiàn)在以下幾個方面。

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

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

比如兩種不同速度的信號被同時發(fā)出，速度為C1、C2、接收器接收信號到達(dá)時間為T1、T2、兩節(jié)點(diǎn)之間距離測定公式為：

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

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

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

4.2.1 質(zhì)心算法

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

4.2.2 基于DC的定位算法

DC（delaunay complex）是三角剖分的擴(kuò)展，DC能夠?qū)φ麄€網(wǎng)絡(luò)進(jìn)行劃分，在網(wǎng)絡(luò)是完全剛性的情況下，可以先對網(wǎng)絡(luò)邊界和中軸進(jìn)行識別，然后選取地標(biāo)節(jié)點(diǎn)，構(gòu)建相應(yīng)的DC，進(jìn)行平面鑲?cè)?，最后結(jié)合節(jié)點(diǎn)位置，實現(xiàn)節(jié)點(diǎn)定位。

5 結(jié)語

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

參考文獻(xiàn)

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

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

[3] 張可.無線傳感器網(wǎng)絡(luò)分布式定位算法研究[D].燕山大學(xué)，2012.

[4] 宮月.無線傳感器網(wǎng)絡(luò)定位算法研究[D].華北電力大學(xué)，2013.

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

[6] 張欣慧，徐晶晶，許必宵，等.無線傳感器網(wǎng)絡(luò)三維定位算法研究[J].計算機(jī)技術(shù)與發(fā)展，2016，26（12）：195-199.