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

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

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

根據是否需要測量實際節點間的距離將定位算法分為基于距離定位和與距離無關的定位算法[1].基于距離的方法又分為：基于到達時間的測距；基于到達時間差的測距；基于達到角度的測距;基于接收信號強度的測距[2].距離無關的定位方法分為：質心算法；DV-HOP算法；Amorfous算法；APIT算法[3].三邊測量法是基于距離的基本定位方法，質心算法是距離無關方法的典型代表.為分析這兩種定位方法的精度，本文對三邊測量法和質心算法這兩種基本的定位方法進行了介紹，并進行了定位仿真實驗.

1 三邊測量定位法

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

圖1 三邊測量法示意圖 圖2 質心定位算法圖示

根據兩點間距離計算公式，得：

(1)

求解方程組(1)就可以求得D點的定位坐標(簡稱定位節點)為[4]：

(2)

因此，借助參考點A、B、C和距離測量，就可以求得未知盲節點D的位置坐標.

2 質心算法定位

質心算法就是采用未知盲節點所在區域的質心作為估計位置.

如圖2所示.設未知盲節點(x，y)所在的區域內可以感知的參考信標節點為(x1，y1)，(x2，y2)，…，(xN，yN)，其中N為未知盲節點在周邊區域內可感知節點總數，r0為未知盲節點通信感知半徑，且滿足：

(3)

則取：

(4)

作為未知盲節點的定位坐標.

3 定位算法的仿真實驗

3.1 三邊測量法仿真

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

圖3 三邊測量法定位結果

圖4 質心算法定位結果

3.2 質心算法仿真

在區域1000米×1000米矩形區域隨機分布1000個位置已知的參考節點，隨機分布200個位置

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

4 分析

從三邊測量法與質心算法實驗可見，基于測距的三邊測量定位法定位準確性高，而與距離無關的質心定位法誤差大.這是因為基于測距的定位方法是通過感知區域內三個參考節點及其精確的測距，由數學精確求解得到唯一確定的定位坐標.而基于距離無關的質心算法定位是采用感知區域內的參考節點進行計算，一旦區域內感知參考節點確定，則質心也確定了，而區域內的未知節點位置卻是不確定的.質心算法正是采用質心代替區域內未知節點的定位坐標，因而誤差較大.通過縮小區域，盡管可以提高質心算法的精度，但未知節點在區域內的位置仍然是不定的，因而總是存在誤差.

定位具有實際的意義.本文簡介了兩類基本的定位算法，通過仿真結果可見基于距離的定位方法相對于距離無關定位方法精度高.這為進一步開展新的定位算法和定位技術提供了積極的指導意義.

參考文獻：

[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的無線傳感器網絡定位技術的研究[J].微計算機信息，2010，26(10):82～84.

[3]王永才，趙千川，鄭大鐘.傳感器網絡自身定位方法的設計與實現[J]，計算機工程與應用，2005(13).

[4]孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京：清華大學出版社，2005.