兩種基本定位算法仿真分析

陳 帥，張水鋒，束仁義，2，鄭曉東

(1.淮南師范學(xué)院 電氣信息工程學(xué)院，安徽 淮南 232038;2.安徽大學(xué) 電子信息工程學(xué)院，安徽 合肥 230039)

根據(jù)是否需要測量實(shí)際節(jié)點(diǎn)間的距離將定位算法分為基于距離定位和與距離無關(guān)的定位算法[1].基于距離的方法又分為：基于到達(dá)時(shí)間的測距；基于到達(dá)時(shí)間差的測距；基于達(dá)到角度的測距;基于接收信號強(qiáng)度的測距[2].距離無關(guān)的定位方法分為：質(zhì)心算法；DV-HOP算法；Amorfous算法；APIT算法[3].三邊測量法是基于距離的基本定位方法，質(zhì)心算法是距離無關(guān)方法的典型代表.為分析這兩種定位方法的精度，本文對三邊測量法和質(zhì)心算法這兩種基本的定位方法進(jìn)行了介紹，并進(jìn)行了定位仿真實(shí)驗(yàn).

1 三邊測量定位法

設(shè)未知盲節(jié)點(diǎn)(簡稱盲節(jié)點(diǎn))D(x，y)可以感知三個(gè)節(jié)點(diǎn)A(xa，ya)，B(xb，yb)，C(xc，yc)，且未知盲節(jié)點(diǎn)到該三個(gè)節(jié)點(diǎn)的距離分別為da，db，dc，如圖1所示.

圖1 三邊測量法示意圖 圖2 質(zhì)心定位算法圖示

根據(jù)兩點(diǎn)間距離計(jì)算公式，得：

(1)

求解方程組(1)就可以求得D點(diǎn)的定位坐標(biāo)(簡稱定位節(jié)點(diǎn))為[4]：

(2)

因此，借助參考點(diǎn)A、B、C和距離測量，就可以求得未知盲節(jié)點(diǎn)D的位置坐標(biāo).

2 質(zhì)心算法定位

質(zhì)心算法就是采用未知盲節(jié)點(diǎn)所在區(qū)域的質(zhì)心作為估計(jì)位置.

如圖2所示.設(shè)未知盲節(jié)點(diǎn)(x，y)所在的區(qū)域內(nèi)可以感知的參考信標(biāo)節(jié)點(diǎn)為(x1，y1)，(x2，y2)，…，(xN，yN)，其中N為未知盲節(jié)點(diǎn)在周邊區(qū)域內(nèi)可感知節(jié)點(diǎn)總數(shù)，r0為未知盲節(jié)點(diǎn)通信感知半徑，且滿足：

(3)

則取：

(4)

作為未知盲節(jié)點(diǎn)的定位坐標(biāo).

3 定位算法的仿真實(shí)驗(yàn)

3.1 三邊測量法仿真

在區(qū)域1000米×1000米矩形區(qū)域隨機(jī)分布1000個(gè)位置已知的參考節(jié)點(diǎn)，隨機(jī)分布200個(gè)位置未知盲節(jié)點(diǎn).假設(shè)每個(gè)未知節(jié)點(diǎn)任意獲取三個(gè)參考節(jié)點(diǎn)的位置坐標(biāo)，計(jì)算這三點(diǎn)間的距離，然后采用三邊測量法進(jìn)行自身的定位計(jì)算.定位結(jié)果如圖3，可見盲節(jié)點(diǎn)通過三邊測量法計(jì)算的定位與盲節(jié)點(diǎn)重合很好，表明精度較高.

圖3 三邊測量法定位結(jié)果

圖4 質(zhì)心算法定位結(jié)果

3.2 質(zhì)心算法仿真

在區(qū)域1000米×1000米矩形區(qū)域隨機(jī)分布1000個(gè)位置已知的參考節(jié)點(diǎn)，隨機(jī)分布200個(gè)位置

未知盲節(jié)點(diǎn).假設(shè)每個(gè)未知盲節(jié)點(diǎn)取在感知范圍內(nèi)的參考節(jié)點(diǎn)的位置坐標(biāo)來進(jìn)行質(zhì)心算法定位計(jì)算，取感知半徑r0=100米.先計(jì)算未知節(jié)點(diǎn)到所有參考節(jié)點(diǎn)的距離，取出距離小于r0的所有參考節(jié)點(diǎn)，然后采用質(zhì)心算法進(jìn)行定位計(jì)算.定位結(jié)果如圖4，可見盲節(jié)點(diǎn)通過質(zhì)心算法計(jì)算的定位與盲節(jié)點(diǎn)有許多不重合，表明存在較大誤差.

4 分析

從三邊測量法與質(zhì)心算法實(shí)驗(yàn)可見，基于測距的三邊測量定位法定位準(zhǔn)確性高，而與距離無關(guān)的質(zhì)心定位法誤差大.這是因?yàn)榛跍y距的定位方法是通過感知區(qū)域內(nèi)三個(gè)參考節(jié)點(diǎn)及其精確的測距，由數(shù)學(xué)精確求解得到唯一確定的定位坐標(biāo).而基于距離無關(guān)的質(zhì)心算法定位是采用感知區(qū)域內(nèi)的參考節(jié)點(diǎn)進(jìn)行計(jì)算，一旦區(qū)域內(nèi)感知參考節(jié)點(diǎn)確定，則質(zhì)心也確定了，而區(qū)域內(nèi)的未知節(jié)點(diǎn)位置卻是不確定的.質(zhì)心算法正是采用質(zhì)心代替區(qū)域內(nèi)未知節(jié)點(diǎn)的定位坐標(biāo)，因而誤差較大.通過縮小區(qū)域，盡管可以提高質(zhì)心算法的精度，但未知節(jié)點(diǎn)在區(qū)域內(nèi)的位置仍然是不定的，因而總是存在誤差.

定位具有實(shí)際的意義.本文簡介了兩類基本的定位算法，通過仿真結(jié)果可見基于距離的定位方法相對于距離無關(guān)定位方法精度高.這為進(jìn)一步開展新的定位算法和定位技術(shù)提供了積極的指導(dǎo)意義.

參考文獻(xiàn)：

[1]He T，Huang C，Blum B M，et al.Range-free localization schemes for large scale sensor networks[C]//Proc 9th Annual Int'l Conf on Mobile Computing and Networking(MobiCom)，San Diego，CA.，2003：81-95.

[2]車云舟，須文波.基于RSSI的無線傳感器網(wǎng)絡(luò)定位技術(shù)的研究[J].微計(jì)算機(jī)信息，2010，26(10):82～84.

[3]王永才，趙千川，鄭大鐘.傳感器網(wǎng)絡(luò)自身定位方法的設(shè)計(jì)與實(shí)現(xiàn)[J]，計(jì)算機(jī)工程與應(yīng)用，2005(13).

[4]孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.