徐琨　劉宏立　馬子驥　胡久松

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；到達(dá)時(shí)間；定位；線性規(guī)劃；迭代

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：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

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

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

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

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

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

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

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

4 結(jié) 論

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

參考文獻(xiàn)

[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.