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

1、WSN距離無關(guān)定位算法許星星（先進(jìn)制造學(xué)院,S151301015）摘要無線傳感器網(wǎng)絡(luò)是一種集成了傳感器、微機(jī)電系統(tǒng)和網(wǎng)絡(luò)三大技術(shù)而形成全新的信息獲取和處理技術(shù),在許多領(lǐng)域有著重要的科研和使用價值,節(jié)點(diǎn)定位技術(shù)是傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)之一,具有十分重要的地位.目前已有較為成熟的無線傳感網(wǎng)定位技術(shù)可以被分為需要測距的定位技術(shù)和與測距無關(guān)的定位技術(shù).本文作者分別介紹了基于測距的定位技術(shù)的基本原理,然后在此基礎(chǔ)上著重綜述了近年來該領(lǐng)域具有代表性的算法及系統(tǒng)的原理和特點(diǎn),并指出未來的研究方向.關(guān)鍵詞:無線傳感網(wǎng)絡(luò);節(jié)點(diǎn)定位;距離無關(guān)Introduction on location algorithms in

2、 wireless sensor networks (Institute of advanced manufacturing，S151301015)AbstractWireless sensor network (WSN) is a kind of integrated with sensor, micro-electro-mechanical system and network technology and the formation of a new information acquisition and processing technology, has important scie

3、ntific research in many fields and use value, is a key technology of sensor network node localization technology, plays a very important position. There are relatively mature wireless sensor network positioning technology can be divided into needs ranging positioning technology and has nothing to do

4、 with the distance positioning technology. Respectively in this paper, the author introduces the positioning technology based on distance and without the basic principle of ranging localization algorithm, analysis and comparison of these two kinds of algorithm, and then on the basis of the focus on

5、the typical algorithms in this field in recent years were reviewed and the principle and characteristics of system, and points out the future research direction.Keywords: WSN; node location algorithm; range-free目錄0 引言41 算法性能評價標(biāo)準(zhǔn)42 距離無關(guān)(range-free)定位算法62.1 典型的算法63結(jié)論9參考文獻(xiàn)100 引言近年來,無線傳感網(wǎng)絡(luò)(Wireless Sens

6、or Networks, WSNS)已經(jīng)獲得了廣泛的關(guān)注,特別是微機(jī)電系統(tǒng)(Micro-Electro-Mechanical Systems, MEMS)技術(shù)的不斷涌現(xiàn),推動了智能傳感器的發(fā)展。 無線傳感網(wǎng)絡(luò)綜合了傳感器技術(shù)、計(jì)算技術(shù)、現(xiàn)代網(wǎng)絡(luò)及無線通信技術(shù)、分布式信息處理技術(shù)等,能夠通過各類集成化的微型傳感器協(xié)作地實(shí)時監(jiān)測、感知和采集各種環(huán)境或監(jiān)測對象的信息。 無線傳感器網(wǎng)絡(luò)的定位技術(shù)在許多領(lǐng)域具有重要的應(yīng)用價值,無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)所采集到的數(shù)據(jù)必須結(jié)合其在測量坐標(biāo)系內(nèi)的位置信息才有意義。在定位領(lǐng)域中,無線傳感網(wǎng)絡(luò)的節(jié)點(diǎn)可以分為兩類:一類是己知自身坐標(biāo)的節(jié)點(diǎn),被稱為信標(biāo)節(jié)點(diǎn)或銷節(jié)點(diǎn),該節(jié)點(diǎn)通

7、常是通過GPS或人工部署的方式得到節(jié)點(diǎn)坐標(biāo)的;另一類是位置坐標(biāo)節(jié)點(diǎn),被稱為未知節(jié)點(diǎn)(Unknow Node),該類節(jié)點(diǎn)則是需要我們通過周圍的描節(jié)點(diǎn)所提供的信息來估算出自身節(jié)點(diǎn)的坐標(biāo)信息。目前無線傳感網(wǎng)絡(luò)的節(jié)點(diǎn)定位算法有許多不同的分類的原則,如:基于有無錨點(diǎn)可以分為有錨點(diǎn)算法和無錨點(diǎn)算法;基于測距方式可以分為距離相關(guān)算法和距離無關(guān)算法;基于計(jì)算方式可以分為集中式算法和分布式算法;基于計(jì)算次數(shù)可以分為一次計(jì)算算法和循環(huán)求精算法。因?yàn)楣?jié)點(diǎn)的定位算法就是為了確定各個節(jié)點(diǎn)的位置信息,因此主要研究基于測距方式的分類:距離相關(guān)(range-based)算法和距離無關(guān)(range-free)算法。本文研究了距

8、離相關(guān)(range-based)算法,分析這算法中的典型定位算法,對這算法原理、性能和優(yōu)缺點(diǎn)進(jìn)行了的分析,并指出現(xiàn)有算法存在的問題。最后總結(jié)全文,對未來無線傳感網(wǎng)絡(luò)定位技術(shù)進(jìn)行了展望。1 算法性能評價標(biāo)準(zhǔn)a) 定位精度:通常也可以成為定位誤差。該標(biāo)準(zhǔn)是評價定位算法的主要標(biāo)準(zhǔn)之一,它是通過估算位置與實(shí)際位置間的差值和節(jié)點(diǎn)通信半徑之間的比例得到的。b) 規(guī)模:不同的定位系統(tǒng)或算法也許可在園區(qū)內(nèi)、建筑物內(nèi)、一層建筑物或僅僅是一個房間內(nèi)實(shí)現(xiàn)定位。另外,給定一定數(shù)量的基礎(chǔ)設(shè)施或在一段時間內(nèi),一種技術(shù)可以定位多少目標(biāo)也是一個重要的評價指標(biāo)。c) 錨節(jié)點(diǎn)密度:錨節(jié)點(diǎn)定位通常依賴人工部署或 GPS 實(shí)現(xiàn)。人工

9、部署錨節(jié)點(diǎn)的方式不僅受網(wǎng)絡(luò)部署環(huán)境的限制,還嚴(yán)重制約了網(wǎng)絡(luò)和應(yīng)用的可擴(kuò)展性。而使用 GPS 定位,錨節(jié)點(diǎn)的費(fèi)用會比普通節(jié)點(diǎn)高兩個數(shù)量級,這意味著即使僅有10%的節(jié)點(diǎn)是錨節(jié)點(diǎn),整個網(wǎng)絡(luò)的價格也將增加10倍。因此,錨節(jié)點(diǎn)密度也是評價定位系統(tǒng)和算法性能的重要指標(biāo)之一。d) 節(jié)點(diǎn)密度:在 WSN 中,雖然在一定范圍內(nèi),定位算法的精度與節(jié)點(diǎn)密度成正相關(guān)關(guān)系,但與此同時,也造成用來進(jìn)行網(wǎng)絡(luò)部署的開銷。此外,節(jié)點(diǎn)密度過大將增加網(wǎng)絡(luò)內(nèi)定位數(shù)據(jù)包的發(fā)送,這將較少網(wǎng)絡(luò)的利用率。因此,在實(shí)際中要參考實(shí)際應(yīng)用的需求在定位精度和節(jié)點(diǎn)密度直接做出權(quán)衡。e) 容錯性和自適應(yīng)性:本論文以及相關(guān)文獻(xiàn)中研究的算法大都是在理想環(huán)境

10、下的仿真。但是在現(xiàn)實(shí)中,總會出現(xiàn)各種無法預(yù)料的情境：比如多徑傳播以及通信盲區(qū)等會影響測量精度；同時網(wǎng)絡(luò)節(jié)點(diǎn)的安全性以及電能的供應(yīng)也會對測量精度造成影響；而且高精度的測量方法或替換節(jié)點(diǎn)一般是不可行的。所以,良好的自適應(yīng)性和容錯性對定位算法來說至關(guān)重要,它能進(jìn)一步提高定位精度。f) 功耗:通常傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)大都分布于交通不便、人煙稀少的地方,并且節(jié)點(diǎn)的規(guī)模都較大,能源耗盡也就表示節(jié)點(diǎn)失效,大規(guī)模的節(jié)點(diǎn)失效會造成網(wǎng)絡(luò)癱瘓,導(dǎo)致網(wǎng)絡(luò)喪失基本功能。所以,傳感器的功耗也應(yīng)該作為重要的考慮因素之一。g) 代價:定位系統(tǒng)或算法的代價可從幾個不同方面來評價。時間代價包括一個系統(tǒng)的安裝時間、配置時間、定位所需

11、時間?？臻g代價包括一個定位系統(tǒng)或算法所需的基礎(chǔ)設(shè)施和網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量、硬件尺寸等。資金代價則包括實(shí)現(xiàn)一種定位系統(tǒng)或算法的基礎(chǔ)設(shè)施、節(jié)點(diǎn)設(shè)備的總費(fèi)用。2 距離無關(guān)(range-free)定位算法2.1 典型的算法（1）Bounding-Box 定位算法Bounding-Box算法是目前定位系統(tǒng)中應(yīng)用最為廣泛的算法之一,它有著精度高、計(jì)算容易和擴(kuò)展性好等優(yōu)點(diǎn)。Bounding-Box算法類似于三邊定位算法,通過傳輸距離損耗模型分別計(jì)算出鋪節(jié)點(diǎn)到被定位點(diǎn)的距離di。以di為半徑,錨節(jié)點(diǎn)為圓心做圓,并進(jìn)一步做出該圓形區(qū)域的外接正方形,從而獲得被定位點(diǎn)所在的一個二維正方形區(qū)域,如圖2-1-1所示。圖2-1

12、-1定位系統(tǒng)中通常會有大于兩個鋪節(jié)點(diǎn)存在,所以會得到至少兩個被定位點(diǎn)所在的二維正方形區(qū)域。由子被定位點(diǎn)同時在兩個二維正方形區(qū)域中,故被定位點(diǎn)必然在兩個正方形區(qū)域的公共區(qū)域中,如圖2-1-2所示。圖2-1-2Bounding-Box定位算法的優(yōu)勢在于其易于擴(kuò)展,并且描節(jié)點(diǎn)的包含被定位點(diǎn)的正方形越多得到的公共正方形的區(qū)域就越小,則估算就越精確。除此之外,該算法的計(jì)算過程與圓沒有關(guān)系,相比三邊定位算法更加方便計(jì)算。得到公共區(qū)域的公式后,用質(zhì)心法取公共區(qū)域的質(zhì)心,即被定位點(diǎn)X的估計(jì)坐標(biāo)。（2）質(zhì)心算法質(zhì)心算法的原理是通過獲取網(wǎng)絡(luò)中節(jié)點(diǎn)間的連通關(guān)系來估算連通節(jié)點(diǎn)問的距離,從而進(jìn)一步利用連通節(jié)點(diǎn)組成的幾何

13、圖形質(zhì)心來估算H標(biāo)節(jié)點(diǎn)坐標(biāo)2。在一個系統(tǒng)通信環(huán)境內(nèi)部署錨節(jié)點(diǎn),錨節(jié)點(diǎn)周期性的廣播自身信息,信息包括本身的ID和其坐標(biāo)。其周圍的未知節(jié)點(diǎn)收到這些信標(biāo)節(jié)點(diǎn)發(fā)來的信號后,即可確定自己處于那幾個信標(biāo)節(jié)點(diǎn)周圍。在一段時間后,未知節(jié)點(diǎn)將搜集到的信標(biāo)信號進(jìn)行統(tǒng)計(jì),當(dāng)其個數(shù)超過閾值后,則可以判斷其周圍有哪些信標(biāo)節(jié)點(diǎn)。求得連通節(jié)點(diǎn)位置坐標(biāo)點(diǎn)組合起來形成的幾何圖形的質(zhì)心,即為未知節(jié)點(diǎn)的估算坐標(biāo),如圖2-1-3所示。圖2-1-3（3）APIT定位算法類似于測距定位算法,APIT也需要有自己的鋪節(jié)點(diǎn),區(qū)別是APIT算法使用的是基于區(qū)域的節(jié)點(diǎn)定位技術(shù),其原理是將錯節(jié)點(diǎn)的區(qū)域劃分成一個個三角形區(qū)域,通過判斷未知節(jié)點(diǎn)位于哪

14、些三角形區(qū)域內(nèi),進(jìn)一步縮小定位范圍。利用描節(jié)點(diǎn)本身的坐標(biāo)即可進(jìn)一步得出目標(biāo)點(diǎn)的位置。圖2-1-4其中常用于減小目標(biāo)節(jié)點(diǎn)所在區(qū)域范圍的算法叫PIT測試。該方法每次判斷目標(biāo)節(jié)點(diǎn)是否在由信標(biāo)節(jié)點(diǎn)所組成的三角形內(nèi),從而利用信標(biāo)節(jié)點(diǎn)的坐標(biāo),即三角形的定點(diǎn)坐標(biāo),縮小目標(biāo)點(diǎn)所在范圍。最后可以得到一個較小的多邊形范圍,然后在利用質(zhì)心算法計(jì)算目標(biāo)節(jié)點(diǎn)的坐標(biāo)。（4）基于移動錨節(jié)點(diǎn)的距離無關(guān)定位算法從前面的分析可以看出成本和錨節(jié)點(diǎn)稀疏問題是目前定位算法最需要進(jìn)一步解決的問題。如何以較少的成本獲得較多的錨節(jié)點(diǎn)位置信息,同時處理錨節(jié)點(diǎn)稀疏問題是定位算法的一個重要的課題,有學(xué)者提出利用移動錨節(jié)點(diǎn)來進(jìn)行定位。在這些方案中,

15、一個移動錨節(jié)點(diǎn)在網(wǎng)絡(luò)中移動并周期地發(fā)送含有錨節(jié)點(diǎn)位置信息的信標(biāo)信號,未知節(jié)點(diǎn)接受這些信標(biāo)信號并通過特定的算法估算自己的位置。距離無關(guān)的移動錨節(jié)點(diǎn)定位方法,無需測距。目前對基于鄰近關(guān)系研究的較多,因?yàn)橐苿渝^節(jié)點(diǎn)可以解決錨節(jié)點(diǎn)稀疏問題。而在錨節(jié)點(diǎn)大密度均勻分布時,鄰近關(guān)系算法精度高同時計(jì)算和通信開銷都較小,要求的節(jié)點(diǎn)密度也低。Sangho等提出了一種基于幾何約束的移動錨節(jié)點(diǎn)定位算法,當(dāng)位置節(jié)點(diǎn)接收到足夠多的信息之后,就可以通過一定的幾何約束條件,從而估計(jì)出自己的位置信息。Hu中也提出了一種基于三邊測量方法的移動錨節(jié)點(diǎn)定位算法。3結(jié)論無線傳感器網(wǎng)絡(luò)在軍事和民用領(lǐng)域都具有極大的應(yīng)用前景,怎樣快速準(zhǔn)確定

16、位無線傳感器的位置一直是近年來的研究熱點(diǎn)。對現(xiàn)有的無線傳感網(wǎng)絡(luò)定位算法距離無關(guān)定位算法進(jìn)行了對比分析,從各種性能指標(biāo)來看, 距離無關(guān)定位算法的問題在于錨節(jié)點(diǎn)稀疏問題和算法的通信與計(jì)算開銷,因此研究趨勢集中在低復(fù)雜度、低開銷、低能耗和能夠解決錨節(jié)點(diǎn)稀疏問題的節(jié)點(diǎn)定位算法。與此同時,研究提出基于移動錨節(jié)點(diǎn)定位技術(shù),對于解決錨節(jié)點(diǎn)稀疏問題有一定得效果,但是還需要進(jìn)一步的研究其移動路徑問題以及不適合使用移動錨節(jié)點(diǎn)環(huán)境下的解決方案。參考文獻(xiàn)1 王福豹,史龍,任豐原.無線傳感器網(wǎng)絡(luò)中的白定位系統(tǒng)和算法J.軟件學(xué)報,2005,16(5):857-868.2 Ren FY, Huang HN, Lin C. Wireless sensor networks. Journal of Software, 2003,14(2):11481157 (in Chinese with English abstract)3 龍婧，無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究，D大連海事大學(xué)，碩士論文，20134 郭明杰，無線傳感器網(wǎng)絡(luò)自身定位算法研