物聯(lián)網(wǎng)目標(biāo)定位算法的MATLAB仿真

陳向陽，柯偉，杜煉，劉培，徐瑩，沈超

1.武漢工程大學(xué)計算機(jī)科學(xué)與工程學(xué)院，湖北 武漢 430205；2.武漢工程大學(xué)郵電與信息工程學(xué)院，湖北 武漢 430205；3.湖北省檔案局（館）科技處，湖北 武漢 430071

物聯(lián)網(wǎng)目標(biāo)定位算法的MATLAB仿真

陳向陽1，柯偉1，杜煉2，劉培2，徐瑩3，沈超1

1.武漢工程大學(xué)計算機(jī)科學(xué)與工程學(xué)院，湖北 武漢 430205；2.武漢工程大學(xué)郵電與信息工程學(xué)院，湖北 武漢 430205；3.湖北省檔案局（館）科技處，湖北 武漢 430071

為了解決物聯(lián)網(wǎng)定位中面臨的諸多問題，對經(jīng)典定位算法進(jìn)行了仿真研究，并通過對仿真結(jié)果進(jìn)行對比分析得到將最小二乘法、最大似然估計與拉格朗日日乘法結(jié)合起來使用的估計目標(biāo)位置方法，即統(tǒng)一地利用加權(quán)最小二乘法／受限制的加權(quán)最小二乘法來計算各種算法.根據(jù)測量結(jié)果得到的非線性方程能夠轉(zhuǎn)化為線性方程，而這些線性方程應(yīng)用加權(quán)最小二乘法與拉格朗日乘法來處理，這種方法可以很容易應(yīng)用到其他算法上.在噪聲相對較小時，上述算法性能已經(jīng)可以達(dá)到克拉美羅下界和無偏性.

定位算法；最小二乘法；最大似然估計；拉格朗日日乘法

0 引言

基于物聯(lián)網(wǎng)的無線定位算法是由已知坐標(biāo)信息的錨節(jié)點和未知節(jié)點構(gòu)成，各節(jié)點可以通過相互協(xié)調(diào)工作來發(fā)送、接受、處理、存儲數(shù)據(jù)，通過無線方式連接，進(jìn)而共同完成特定的應(yīng)用任務(wù).算法允許位置任意存放，靈活度較高，相比于基于非測距的節(jié)點相比，由于可隨意放置，精確度較高而用途廣泛.因為存在一定的冗余度，即使大部分不能工作，只要還有少許節(jié)點正常工作，仍可以獲得較高的定位精度.基于非測距定位算法，以大量簡單的定位節(jié)點獲得估計定位置，而基于測距的定位算法以少量復(fù)雜的定位節(jié)點換取較高的定位精度［1-2］.通過MATLAB軟件仿真結(jié)果對比得到了實用的基于測距的目標(biāo)定位算法即TOA、TDOA、AOA、RSS及TDOA-AOA聯(lián)合算法.

在定位系統(tǒng)中全球衛(wèi)星定位系統(tǒng)（GPS）占全球定位應(yīng)用中絕大部分市場，但由于成本、體積等因素限制使得這四大系統(tǒng)均不適用于低成本的物聯(lián)網(wǎng)應(yīng)用，為此需要針對物聯(lián)網(wǎng)定位區(qū)域相對較小、低成本等特性設(shè)計合適的定位算法及其應(yīng)用.

無線定位算法可大體分為兩類，基于測距的定位算法和基于非測距的定位算法.

基于非測距的定位算法主要有質(zhì)心算法、DV-Hop算法、凸規(guī)劃定位算法、APIT算法.著重介紹基于測距的定位算法TOA、DTOA、RSS、AOA及TDOA-AOA算法.具體實現(xiàn)的主要功能如下:

主要實現(xiàn)基于測距的算法，包含TOA、DTOA、RSS、AOA及TDOA-AOA算法的定位，每個算法首先會建立相應(yīng)的模型，考慮誤差以便更加符合實際情況.其次用TOA、DTOA、RSS、DTOA-AOA測量的值運用受限地加權(quán)最小二乘法（CWLS）建立方程，接下來利用AOA結(jié)合加權(quán)最小二乘法、拉格朗日乘法來建立方程，以及最大似然估計等方法處理方程，這樣定位點比較精確.通過求定位誤差方差的克拉美羅下界（CRLB）來比較定位算法性能［3-4］.

1 定位算法的模型

1.1 TDOA定位算法

TDOA算法定位原理是首先選擇一個基站為參考基站，運動站方發(fā)送無線信號，可以獲得這個參考基站BS1與其他每個基站BSi接收信號的時間差，從而知道了BSi與BS1基站到移動站之間的距離差.通過這些幾何關(guān)系建立BSi與BS1之間雙曲線，雙曲線焦點為這兩個基站，根據(jù)雙曲線的點到焦點距離差為一個定值，可以確定運動站的可能存在軌跡，通過兩個以上的雙曲線即可確定移動站的坐標(biāo).TDOA算法幾何模型如圖1所示.

圖1 TDOA幾何模型Fig.1 The geometric model of TDOA

假設(shè)將第一個基站作為參考基站，將模型歸納成公式（1）形式:

而nTDOA，i代表噪聲、即每個測量距離差值的誤差．如果rTDOA，i直接由DOA處獲得的數(shù)據(jù)獲得，那么

如果沒有誤差，可將公式（1）改寫成

將以上對所有的i，方程改成矩陣的形式

其中：

而參數(shù)向量g＝［x-x1，y-y1，R］T

同時（x2-x1）2+（y2-y1）＝R2，可以將此公式改寫成

其中M＝diag（［1，1，-1］）．如此一來，對于受限制的加權(quán)最小二乘法的矩陣轉(zhuǎn)化為拉格朗日乘法來求解．

求出此方程極值點，取值使公式（7）最小時的g即可．

1.2 RSS定位算法

nRSS，i代表著誤差，如果a＝1，那么該模型RSS與DOA模型一樣．如果RSS定位算法沒有測量誤差，公式（9）可以變成公式（10）形式［6］:

對其公式（10）轉(zhuǎn)變得

其中:

參照TDOA方法，由于Aθ＝b無解，對其進(jìn)行受限制的加權(quán)最小二乘法的方差進(jìn)行處理，得到公式（13）為

其中:

求式（12）最小值，應(yīng)用拉格朗日乘法列方程如下:

求出方程（14）極值點，取值使公式（13）最小時的g即可．

1.3 AOA定位算法

AOA算法測量的由移動站發(fā)送到基站i的信號方向，這個方向與（x，y）及（xi，yi）相關(guān)，方向角度有φi表示，有公式（15）［7-8］:

圖2為AOA算法角度測量幾何圖形．

圖2 AOA算法定位的幾何圖形Fig.2 The geometric model of AOA algorithm localization

一般來說，φi由第i個基站到移動站之間的直線與x軸之間形成的夾角，如果存在誤差，那么測量的角度由rAOA，i表示，可以根據(jù)測量的角度建立如下模型:

其中nAOA，i代表著測量rAOA，i時附帶的誤差．對于AOA算法，如果沒有出現(xiàn)誤差干擾，則公式（16）可以寫成:

可以將公式（17）轉(zhuǎn)化為

對于所有的i，以向量的形式寫出來，可以得到公式（19）:

其中:

如同TDOA，RSS一樣，為了提高運動站定位精度，用加權(quán)最小二乘法，可以建立如下方程:

其中Ω-1是加權(quán)矩陣，x＝（x，y）T，根據(jù)最佳線性無偏估計（BLUE）來求Ω．

1.4 TDOA-AOA定位算法

顯而易見，若把兩者算法混合，很可能提高算法的精度，或者可以減少使用基站的數(shù)量．在可能混合算法中，AOA和TDOA最容易混合起來，為了能夠定位，需要重寫公式（17）定位模型，兩邊同時加變量:yicos(rAOA，1)-xisin(rAOA，n)得到如下等式［9-10］:

把式（3）和式（17）合并到一個向量中，可以轉(zhuǎn)化為如下的等式:

式（23）中:

其中:

0n指n×1的零向量，要求合適的g只需保證取值最?。?/p>

并保證約束條件

其中，矩陣w是相應(yīng)的加權(quán)矩陣．

然后根據(jù)第1．1節(jié)求TDOA中g(shù)的過程來求TDOA-AOA中的g．同樣的道理，把AOA與RSS，或者TOA結(jié)合，也可以提高單個算法的精度．

1.5 各種定位算法的克拉美羅下界

對于方差達(dá)到克拉美羅下界（CRLB）的無偏估計稱為有效方差．克拉美羅下界表示定位誤差的最小值，通過比較克拉美羅下界和提出的算法來驗證算法的精度．

2 定位算法仿真及分析

下面的仿真結(jié)果由于要比較各種定位算法在噪聲較小時的定位精度，故對仿真圖片圖3進(jìn)行放大．由圖4可看出，當(dāng)噪聲較小時，RSS定位精度比較準(zhǔn)確，甚至超過了TDOA-AOA聯(lián)合算法，但是RSS定位算法對誤差也很敏感，當(dāng)干擾功率大于-30dB時，定位誤差突然變大，但同比其他算法，誤差也基本保持比較低，整體上說該算法仍是性能比較好的算法．接著定位第二準(zhǔn)確的是TDOAAOA，由圖4所示，TDOA-AOA算法定位精度相對于TDOA算法、AOA算法都有所提高，在AOA部分測量誤差干擾為-30dB，該算法誤差也比較低，精度比較好．TDOA-AOA、TDOA，AOA算法對噪聲有一定的抵抗力，當(dāng)噪聲功率提高時，定位精度也隨之平穩(wěn)地下降．當(dāng)誤差較大時，RSS與AOA定位誤差相對較小，即精度較高．

圖3 各種算法定位坐標(biāo)變化Fig.3 The coordinate variation of localization algorithms

圖4 各種算法的定位噪聲與定位誤差變化Fig.4 The positioning noise and positioning error variation of positioning algorithms

因此，總的來講當(dāng)噪聲都充分小時，TDOAAOA算法、TDOA算法、AOA算法、RSS算法定位都可以很好地定位．當(dāng)噪聲變大時誤差超過-30 dB，相當(dāng)于測量距離誤差定位精度都嚴(yán)重下降．在實際工程運用中，就要根據(jù)實際情況選擇定位算法．當(dāng)噪聲較小時，選擇RSS算法比較好，當(dāng)噪聲相對較大時，選擇TDOA-AOA算法合適些．雖然給出了DOA算法的模型，但是由于當(dāng)a＝1時，RSS算法即轉(zhuǎn)化為DOA算法處理過程，故不在本文中推導(dǎo)算法處理過程．算法處理思想是根據(jù)測量結(jié)果得到的非線性方程轉(zhuǎn)化為線性方程．而這些線性方程應(yīng)用加權(quán)最小二乘法與拉格朗日乘法來處理［10-13］．

3 總結(jié)及展望

現(xiàn)有實現(xiàn)定位的兩類算法:基于測距（Range-Based）和基于非測距（Range-Free）各有千秋．若僅采用基于非測距的算法雖然無需根據(jù)角度和距離等信息，可僅根據(jù)網(wǎng)絡(luò)連通性等約束條件實現(xiàn)節(jié)點定位，節(jié)約了開支，但以犧牲了精度為代價．而基于測距的定位算法一般利用自身所配置的設(shè)備所擁有的一定測量技術(shù)來測量相關(guān)信息，例如距離、信號到達(dá)角度、深度等信息，它雖然能提供定位精度很高的定位效果，但是實現(xiàn)定位成本相對較高．因此通過比較與仿真得出了統(tǒng)一的用加權(quán)最小二乘法／受限制的加權(quán)最小二乘法來解決TDOD算法、AOA算法、RSS算法及TDOA-AOA算法．該算法是將根據(jù)測量結(jié)果得到的非線性方程轉(zhuǎn)化為線性方程，而這些線性方程應(yīng)用加權(quán)最小二乘法與拉格朗日乘法來處理，它可以很容易擴(kuò)展到TDOA-AOA算法中.仿真結(jié)果已經(jīng)證明了所述算法在噪聲相對較小時，算法的性已經(jīng)可以達(dá)到克拉美羅下界（CRLB）和無偏性和準(zhǔn)確性.當(dāng)然仍有部分內(nèi)容有待進(jìn)一步探討和研究，如可將TDOA、RSS、TOD中受限制的加權(quán)最小二乘法轉(zhuǎn)換成不受限制的算法改進(jìn).

致謝

本文得到湖北省教育科學(xué)“十二五”規(guī)劃2013年度立項課題:地方性高校新興交叉學(xué)科建設(shè)的研究--以網(wǎng)絡(luò)科學(xué)為例（2013B060）項目資助，在此表示衷心的感謝.

［1］Akyildiz I．F．，．Su W，．Sankarasubramaniam Y，et al．A survey on sensor networks［J］．Communications Magazine IEEE，2002，40（8）:102-114．

［2］張興如．無源定位及定位性能的分析［D］．成都:電子科技大學(xué)，2001．

ZHANG Xingru．Analysis of passive location and positioning performance．［D］.Chengdu:University of Electronic Science and Technology of China，2001．（in chineses）

［3］劉書靜，羅海勇，吳彬．基于最小二乘測距定位算法信標(biāo)最優(yōu)部署模型［J］．計算機(jī)學(xué)報，2013，36（3）:562-576．

LIU Shu jing，LUOHaiyong，WUBing．Optimal landmark deployment patterns for range-based least squares localization［J］．Chinese Journal of Computers，2013，36（3）:562-576．（in chineses）

［4］馬祖長，孫怡寧，梅濤．無線傳感器網(wǎng)絡(luò)綜述［J］．通信學(xué)報，2004，25（4）:114-124.

MA Zuchang，SUN Yining，MEI Tao．Survey on wireless sensors network［J］．Journal on Communications，2004，25（4）:114-124．（in chineses）

［5］趙春梅，歐吉坤，袁運斌．基于單點定位模型的GALILEO及GPS-GALILEO組合系統(tǒng)的定位精度和可靠性的仿真分析［J］．科學(xué)通報，2005，50（8）: 811-818.

ZHAO Chunmei，OU Jikun，YUAN Yunbin．Single pointpositioningmodelbasedonGALILEO，The positioning accuracy of GPS-GALILEO combination systemandReliabilityanalysisofsimulation［J］．Chinese Science Bulletin，2005，50（8）:811-818．（in chineses）

［6］何佳鴻，張小明，王永恒．基于物聯(lián)網(wǎng)空間劃分的定位算法［J］．計算機(jī)應(yīng)用，2012，32（12）:3517-3520．

HE Jiahong，ZHANG Xiaoming，WANG Yongheng．Positioning algorithm based on Internet of things spatial meshing［J］．JournalofComputerApplications，2012，32（12）:3517-3520．（in chineses）

［7］王文秀．無線傳感器網(wǎng)絡(luò)自定位算法研究［D］．大慶:東北石油大學(xué)，2013.

WANG Wenxiu．Research on localization algorithm for wireless sensor networks［D］．Daqing:Northeast Petroleum University，2013．（in chineses）

［8］郭龍江，李建中，李金寶．無線傳感器網(wǎng)絡(luò)若干定位算法的研究［J］．計算機(jī)工程與設(shè)計，2006，27（12）: 2114-2118.

GUO Longjiang，LI Jianzhong，LI Jinbao．Study to severalpositioningalgorithmsonwirelesssensor networks［J］．Computer Engineering and Design，2006，27（12）:2114-2118．（in chineses）

［9］金純，葉誠，韓志斌，等．無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)［J］．計算機(jī)工程與設(shè)計，2013，34（2）:45-54．

JIN Chun，YE Cheng，HAN Zhibin etc．DV-Hop localization algorithm improvements in wireless sensor networks［J］．Computer Engineering and Design，2013，34（2）:45-54．（in chineses）

［10］李冬．基于DV-Hop的無線傳感器網(wǎng)絡(luò)定位［D］．南京:南京理工大學(xué)，2013．

LI Dong，Positioning based on DV-Hop for wireless sensor network［D］．Nanjing:Nanjing University of Science and Technology，2013．（in chineses）

［11］楊冕，秦前清．對傳感器網(wǎng)絡(luò)定位技術(shù)現(xiàn)狀的研究［J］．微機(jī)發(fā)展，2005，15（3）:26-28．

YANG Mian，QIN Qianqing．Researchon current localization technology of sensor networks［J］．Microcomputer Development，2005，15（3）:26-28．（in chineses）

［12］Cheung K W，So H C．A multidimensional scaling framework for mobile location using time - of - arrival measurements［J］．IEEE Transactions on Signal Processing，2005，53（2）:460-470．

［13］Cheung K W，So H C，Ma W-K．A constrained Least squares approach to mobile positioning:algorithms and optimality，signal processing［J］．IEEE Transactions，2014，62（11）:2999-3012．

Simulation of target location algorithm for Internet of Things in Matlab

CHEN Xiang-yang1，KE wei1，DU Lian2，LIU Pei2，XU Ying3，SHEN Chao1
1.School of Computer Science and Engineering，Wuhan Institute of Technology，Wuhan 430074，China；2.The college of Post and Telecommunication of Wuhan Institute of Technology，Wuhan 430074，China；3.Science and Technology Department，Hubei Provincial Archives Bureau，Wuhan 430071，China

To solve the many problems faced in the location of Internet of Things，the classic positioning methods are studied．By the comparative analysis of the simulation results，an effectively method of estimated target location（least squares，maximum likelihood estimation and Lagrange combined positioning algorithm）were got，and an generalized weighted least square method／limited weighted least square method can be used to calculate various algorithm．The nonlinear equation obtained from the result of measurement can be transformed to linear equation．And then the linear equation can be solved with weighted Least squares and Lagrange algorithm．This method can be easily applied to other algorithm too．When noise is relatively low，the performance of the algorithm can reach the Cramer Rao lower bound and be unbiased．

positioning algorithm；least squares；maximum likelihood estimation；lagrange algorithm

TN643

A

10.3969/j.issn.1674-2869.2015.03.014

1674-2869（2015）03-0068-06

本文編輯：陳小平

2015-01-16

湖北省教育科學(xué)“十二五”規(guī)劃2013年度立項課題（2013B060）

陳向陽（1969-），男，河南開封人，副教授，碩士.研究方向:網(wǎng)絡(luò)通信工程、復(fù)雜網(wǎng)絡(luò)、生物信息等．