一種用于室內定位的線性規(guī)劃算法

徐琨　劉宏立　馬子驥　胡久松

摘 要：針對基于ToA定位中存在的信標節(jié)點較少和發(fā)送時間不能提前預知的問題，提出了一種新的應用于無線傳感網絡室內定位的線性規(guī)劃算法.通過考慮測量值的最小平均絕對值誤差，利用線性逼近方法，將一個復雜的、非凸的室內定位問題轉換為一個簡單的線性規(guī)劃問題，并用迭代求精的方法求出最優(yōu)解.仿真結果表明，提出算法計算復雜度低，收斂速度快，可以快速地求出未知節(jié)點的坐標；通過和已有的定位算法相比，提出算法在信標節(jié)點較少的情況下，仍能保持很好的定位精度，利用較少的節(jié)點資源達到比已有算法更好的定位性能.

關鍵詞：無線傳感器網絡；到達時間；定位；線性規(guī)劃；迭代

中圖分類號：TP393 文獻標識碼：A

Abstract：To solve the problem of fewer beacon nodes and unknown transmission time in Time of Arrival （ToA） based localization， a new linear programming algorithm was proposed to approximate nonlinear localization estimation problems. We consider the least-mean absolute errors of the residual and formulate the nonconvex localization problem as a simple linear programming by using linear approximation. Simulation results demonstrate that the proposed algorithm can maintain good positioning accuracy under fewer beacon nodes and achieve better performance by using less node resources than the existing algorithms.

Key words： wireless sensor networks；time of arrival；localization；linear programming；iteration

目前，隨著無線通信技術、嵌入式技術和網絡技術的快速發(fā)展，無線傳感網絡[1]（Wireless Sensor Networks，WSN）得到了前所未有的關注，已經成為研究熱點.定位技術[2]是WSN中最重要的基礎性研究之一，沒有位置信息的WSN應用是沒有任何意義的.基于WSN的定位是根據不同定位技術的測量值來確定網絡中傳感節(jié)點的位置，常采用的定位技術主要有基于到達時間[3]（Time of Arrival，ToA）的定位，基于到達時間差[4]（Time Different of Arrival，TDoA）的定位，基于到達角度[5]（Angle of Arrival，AoA）的定位和基于接收信號強度[6]（Received Signal Strength Indicator，RSSI）的定位等.基于WSN的定位系統(tǒng)被廣泛用于各種實際應用中，如環(huán)境監(jiān)測[7]、工業(yè)自動化過程控制[8]和家庭醫(yī)療保健[9]等.

基于ToA的定位技術具有定位精度高、實現(xiàn)簡單等優(yōu)點，得到了國內外研究者的廣泛關注，目前已有很多基于ToA的定位研究方法.最大似然估計方法[10]（Maximum Likelihood，ML）是最常用的方法之一，但是，要得到基于ToA定位問題的最大似然估計量是一個困難的全局優(yōu)化問題.很多研究者提出了一些替代方法來避免復雜的全局優(yōu)化問題，文獻[11]將定位問題轉換成一個半正定規(guī)劃松弛問題（Semidefinite Programming Relaxation，SDP）進行求解，通過采用解決SDP的方法來降低求解ML問題的復雜度.文獻[12]提出用線性最小二乘法（Linear Least Square，LLS）解決定位問題.通過這個方法，能夠在測量噪聲較小的情況下得到較好的定位性能.文獻[13]基于極小極大方法，提出了2個次優(yōu)的方案來解決定位問題，雖然已經提出了很多有效的方法能夠減少基于ToA的定位問題的復雜度和得到較好的定位精度，但是它們基本上都要求部署較多的信標節(jié)點和提前知道信號的發(fā)送時間，沒有考慮信標節(jié)點較少和發(fā)送時間未知的情況.

在實際應用中，不可能在一個區(qū)域內部署大量的信標節(jié)點，而且這些信標節(jié)點也基本上不能提前知道目標節(jié)點發(fā)送信號的初始時間.本文針對信標節(jié)點部署較少、發(fā)送時間未知的情況，提出了一種新的基于線性規(guī)劃的定位優(yōu)化算法，通過多個信標節(jié)點接收到的ToA測量值，消除發(fā)送時間未知對定位的影響；考慮殘差的最小平均絕對值誤差，將一個原始形式為非凸優(yōu)化的定位問題轉換成線性規(guī)劃問題（Linear Programming，LP）.線性規(guī)劃結構簡單，計算復雜度低，可以采用迭代求精的方法快速求出最優(yōu)解，得到未知節(jié)點的坐標.仿真結果證明了提出的算法具有很好的定位性能，特別是在信標節(jié)點較少的情況下，提出算法的定位性能明顯優(yōu)于已有的定位算法.

從圖1可以看出，在不同的測量噪聲和信標節(jié)點個數下，提出算法要明顯優(yōu)于LLS算法，具有和SDR算法相似的定位精度.不管部署多少個信標節(jié)點，當測量噪聲較小時，3種不同的定位算法都能得

到較好的定位性能，但隨著測量噪聲的增大，3種定位算法的定位誤差也會跟著提高，信標節(jié)點部署較多時，定位誤差增長的程度會降低，其中，LLS算法的定位誤差增加的程度最為明顯.當信標節(jié)點個數較少時，即使在測量噪聲很小的情況下，LLS算法和SDR算法依然具有較高的定位誤差，本文提出算法明顯優(yōu)于LLS算法和SDR算法.

不同信標節(jié)點個數對定位精度也有影響，圖2表示了測量噪聲標準差σ=2 m的情況下，不同算法的定位精度隨信標節(jié)點個數的影響.由圖2可知，隨著信標節(jié)點的增多，3種定位算法的定位精度都會得到提高，其中，LLS算法受信標節(jié)點個數的影響最大，當信標節(jié)點個數增加到一定程度后，對定位精度的影響會慢慢趨于飽和.當部署的信標節(jié)點較少時，提出算法依然能夠得到較好的定位性能，遠遠勝過LLS算法和SDR算法的定位精度，其中，LLS算法的定位誤差最大.

信標節(jié)點個數對于提出算法，需要計算式（5）中平均絕對值誤差‖R-D‖1的值.設R-D=e，隨機選擇一個初始點u0，通過仿真可以計算出算法的收斂速度.設迭代次數為10，重復運行算法10次.其平均絕對值誤差和收斂性之間關系如圖3所示.圖3表示在有4個信標節(jié)點，測量噪聲標準差為2 m的情況下，提出算法完成一次定位運算的收斂速度，可以很清楚地看到，提出算法在信標節(jié)點較少的情況下，收斂速度非?？?，只需要3次迭代就收斂了.

4 結 論

針對基于ToA定位中存在的信標節(jié)點少和發(fā)送時間不能提前預知的問題，提出了一種新的解決室內定位的線性規(guī)劃算法，通過提出的算法，可以快速有效地解決目標節(jié)點的定位問題.計算仿真表明，本文提出的算法具有較好的定位性能，尤其在信標節(jié)點較少的情況下，提出算法明顯優(yōu)于已有的定位算法.

參考文獻

[1] CHIARA B，ANDREA C，DAVIDE D，et al.An overview on wireless sensor networks technology and evolution[J].Sensors， 2009， 9（9）：6869-6896.

[2] CONTI M，WILLEMSEN J，CRISPO B.Providing source location privacy in wireless sensor networks： a survey[J]. IEEE Communications Surveys and Tutorials，2013，15（3）：1238-1280.

[3] HUANG J， XUE Y， YANG L. An efficient closed-form solution for joint synchronization and localization using ToA[J]. Future Generation Computer Systems，2013，29（3）：776-781.

[4] GHOLAMI M R，GEZICI S，STROM E G.TDOA based positioning in the presence of unknown clock skew[J].IEEE Transactions on Communications， 2013，61（6）：2522-2534.

[5] MALAJNER M，PLANINSIC P，GLEICH D.Angle of arrival estimation using RSSI and omnidirectional rotatable antennas[J].IEEE Sensors Journal， 2012，12（6）：1950-1957.

[6] SAHU P K，WU E H K，SAHOO J.DURT： Dual RSSI trend based localization for wireless sensor networks[J].IEEE Sensors Journal，2013， 13（8）：3115-3123.

[7] ZHAO J，XI W，HE Y，et al.Localization of wireless sensor networks in the wild：pursuit of ranging quality[J].IEEE/ACM Transactions on Networking， 2013，21（1）：311-323.

[8] RAWAT A S，ANAND P，CHEN H，et al.Collaborative spectrum sensing in the presence of Byzantine attacks in cognitive radio networks[J]. IEEE Transactions on Signal Processing，2011，59（2）：774-786.

[9] LI K J，BIGHAM J，BODANESE E L，et al.Outdoor location estimation in changeable environments[J].IEEE Communications Letters，2013，17（11）： 2072-2075.

[10]MOHAMMAD R G，SINAN G，ERIK G S.Improved position estimation using hybrid tw-ToA and TDoA in cooperative networks[J]. IEEE Transactions on Signal Processing， 2012，60（7）：3770-3785.

[11]WANG G， LI Y M， WANG R D. New semidefinite relaxation method for acoustic energy-based source localization[J].IEEE Sensor Journal，2013， 13（5）：1514-1521.

[12]YANG L，HO K C.An approximately efficient TDoA localization algorithm in closed-form for locating multiple disjoint sources with erroneous sensor positions[J].IEEE Transactions on Signal Processing，2009，57（12）：4598-4615.

[13]XU E，DING Z，DASGUPTA S.Reduced complexity semidefinite relaxation algorithms for source localization based on time difference of arrival[J].IEEE Transactions on Mobile Comput，2011，10（9）：1276-1282.