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

1、WSN距離無(wú)關(guān)定位算法許星星（先進(jìn)制造學(xué)院,S151301015）摘要無(wú)線傳感器網(wǎng)絡(luò)是一種集成了傳感器、微機(jī)電系統(tǒng)和網(wǎng)絡(luò)三大技術(shù)而形成全新的信息獲取和處理技術(shù),在許多領(lǐng)域有著重要的科研和使用價(jià)值,節(jié)點(diǎn)定位技術(shù)是傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)之一,具有十分重要的地位.目前已有較為成熟的無(wú)線傳感網(wǎng)定位技術(shù)可以被分為需要測(cè)距的定位技術(shù)和與測(cè)距無(wú)關(guān)的定位技術(shù).本文作者分別介紹了基于測(cè)距的定位技術(shù)的基本原理,然后在此基礎(chǔ)上著重綜述了近年來(lái)該領(lǐng)域具有代表性的算法及系統(tǒng)的原理和特點(diǎn),并指出未來(lái)的研究方向.關(guān)鍵詞:無(wú)線傳感網(wǎng)絡(luò);節(jié)點(diǎn)定位;距離無(wú)關(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 算法性能評(píng)價(jià)標(biāo)準(zhǔn)42 距離無(wú)關(guān)(range-free)定位算法62.1 典型的算法63結(jié)論9參考文獻(xiàn)100 引言近年來(lái),無(wú)線傳感網(wǎng)絡(luò)(Wireless Sens

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

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

8、離相關(guān)(range-based)算法,分析這算法中的典型定位算法,對(duì)這算法原理、性能和優(yōu)缺點(diǎn)進(jìn)行了的分析,并指出現(xiàn)有算法存在的問(wèn)題。最后總結(jié)全文,對(duì)未來(lái)無(wú)線傳感網(wǎng)絡(luò)定位技術(shù)進(jìn)行了展望。1 算法性能評(píng)價(jià)標(biāo)準(zhǔn)a) 定位精度:通常也可以成為定位誤差。該標(biāo)準(zhǔn)是評(píng)價(jià)定位算法的主要標(biāo)準(zhǔn)之一,它是通過(guò)估算位置與實(shí)際位置間的差值和節(jié)點(diǎn)通信半徑之間的比例得到的。b) 規(guī)模:不同的定位系統(tǒng)或算法也許可在園區(qū)內(nèi)、建筑物內(nèi)、一層建筑物或僅僅是一個(gè)房間內(nèi)實(shí)現(xiàn)定位。另外,給定一定數(shù)量的基礎(chǔ)設(shè)施或在一段時(shí)間內(nèi),一種技術(shù)可以定位多少目標(biāo)也是一個(gè)重要的評(píng)價(jià)指標(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)用會(huì)比普通節(jié)點(diǎn)高兩個(gè)數(shù)量級(jí),這意味著即使僅有10%的節(jié)點(diǎn)是錨節(jié)點(diǎn),整個(gè)網(wǎng)絡(luò)的價(jià)格也將增加10倍。因此,錨節(jié)點(diǎn)密度也是評(píng)價(jià)定位系統(tǒng)和算法性能的重要指標(biāo)之一。d) 節(jié)點(diǎn)密度:在 WSN 中,雖然在一定范圍內(nèi),定位算法的精度與節(jié)點(diǎn)密度成正相關(guān)關(guān)系,但與此同時(shí),也造成用來(lái)進(jìn)行網(wǎng)絡(luò)部署的開(kāi)銷。此外,節(jié)點(diǎn)密度過(guò)大將增加網(wǎng)絡(luò)內(nèi)定位數(shù)據(jù)包的發(fā)送,這將較少網(wǎng)絡(luò)的利用率。因此,在實(shí)際中要參考實(shí)際應(yīng)用的需求在定位精度和節(jié)點(diǎn)密度直接做出權(quán)衡。e) 容錯(cuò)性和自適應(yīng)性:本論文以及相關(guān)文獻(xiàn)中研究的算法大都是在理想環(huán)境

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

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

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

13、圖形質(zhì)心來(lái)估算H標(biāo)節(jié)點(diǎn)坐標(biāo)2。在一個(gè)系統(tǒng)通信環(huán)境內(nèi)部署錨節(jié)點(diǎn),錨節(jié)點(diǎn)周期性的廣播自身信息,信息包括本身的ID和其坐標(biāo)。其周圍的未知節(jié)點(diǎn)收到這些信標(biāo)節(jié)點(diǎn)發(fā)來(lái)的信號(hào)后,即可確定自己處于那幾個(gè)信標(biāo)節(jié)點(diǎn)周圍。在一段時(shí)間后,未知節(jié)點(diǎn)將搜集到的信標(biāo)信號(hào)進(jìn)行統(tǒng)計(jì),當(dāng)其個(gè)數(shù)超過(guò)閾值后,則可以判斷其周圍有哪些信標(biāo)節(jié)點(diǎn)。求得連通節(jié)點(diǎn)位置坐標(biāo)點(diǎn)組合起來(lái)形成的幾何圖形的質(zhì)心,即為未知節(jié)點(diǎn)的估算坐標(biāo),如圖2-1-3所示。圖2-1-3（3）APIT定位算法類似于測(cè)距定位算法,APIT也需要有自己的鋪節(jié)點(diǎn),區(qū)別是APIT算法使用的是基于區(qū)域的節(jié)點(diǎn)定位技術(shù),其原理是將錯(cuò)節(jié)點(diǎn)的區(qū)域劃分成一個(gè)個(gè)三角形區(qū)域,通過(guò)判斷未知節(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測(cè)試。該方法每次判斷目標(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)所在范圍。最后可以得到一個(gè)較小的多邊形范圍,然后在利用質(zhì)心算法計(jì)算目標(biāo)節(jié)點(diǎn)的坐標(biāo)。（4）基于移動(dòng)錨節(jié)點(diǎn)的距離無(wú)關(guān)定位算法從前面的分析可以看出成本和錨節(jié)點(diǎn)稀疏問(wèn)題是目前定位算法最需要進(jìn)一步解決的問(wèn)題。如何以較少的成本獲得較多的錨節(jié)點(diǎn)位置信息,同時(shí)處理錨節(jié)點(diǎn)稀疏問(wèn)題是定位算法的一個(gè)重要的課題,有學(xué)者提出利用移動(dòng)錨節(jié)點(diǎn)來(lái)進(jìn)行定位。在這些方案中,

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

16、位無(wú)線傳感器的位置一直是近年來(lái)的研究熱點(diǎn)。對(duì)現(xiàn)有的無(wú)線傳感網(wǎng)絡(luò)定位算法距離無(wú)關(guān)定位算法進(jìn)行了對(duì)比分析,從各種性能指標(biāo)來(lái)看, 距離無(wú)關(guān)定位算法的問(wèn)題在于錨節(jié)點(diǎn)稀疏問(wèn)題和算法的通信與計(jì)算開(kāi)銷,因此研究趨勢(shì)集中在低復(fù)雜度、低開(kāi)銷、低能耗和能夠解決錨節(jié)點(diǎn)稀疏問(wèn)題的節(jié)點(diǎn)定位算法。與此同時(shí),研究提出基于移動(dòng)錨節(jié)點(diǎn)定位技術(shù),對(duì)于解決錨節(jié)點(diǎn)稀疏問(wèn)題有一定得效果,但是還需要進(jìn)一步的研究其移動(dòng)路徑問(wèn)題以及不適合使用移動(dòng)錨節(jié)點(diǎn)環(huán)境下的解決方案。參考文獻(xiàn)1 王福豹,史龍,任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的白定位系統(tǒng)和算法J.軟件學(xué)報(bào),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ú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究，D大連海事大學(xué)，碩士論文，20134 郭明杰，無(wú)線傳感器網(wǎng)絡(luò)自身定位算法研