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

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

2、識碼：AAbstract：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 f

3、ormulate 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 ex

4、isting algorithms.Key words： wireless sensor networks；time of arrival；localization；linear programming；iteration目前，隨著無線通信技術(shù)、嵌入式技術(shù)和網(wǎng)絡(luò)技術(shù)的快速開展，無線傳感網(wǎng)絡(luò)1Wireless Sensor Networks，WSN得到了前所未有的關(guān)注，已經(jīng)成為研究熱點.定位技術(shù)2是WSN中最重要的根底性研究之一，沒有位置信息的WSN應(yīng)用是沒有任何意義的.基于WSN的定位是根據(jù)不同定位技術(shù)的測量值來確定網(wǎng)絡(luò)中傳感節(jié)點的位置，常采用的定位技術(shù)主要有基于到達時間3Time of Ar

5、rival，ToA的定位，基于到達時間差4Time Different of Arrival，TDoA的定位，基于到達角度5Angle of Arrival，AoA的定位和基于接收信號強度6Received Signal Strength Indicator，RSSI的定位等.基于WSN的定位系統(tǒng)被廣泛用于各種實際應(yīng)用中，如環(huán)境監(jiān)測7、工業(yè)自動化過程控制8和家庭醫(yī)療保健9等.基于ToA的定位技術(shù)具有定位精度高、實現(xiàn)簡單等優(yōu)點，得到了國內(nèi)外研究者的廣泛關(guān)注，目前已有很多基于ToA的定位研究方法.最大似然估計方法10Maximum Likelihood，ML是最常用的方法之一，但是，要得到基于To

6、A定位問題的最大似然估計量是一個困難的全局優(yōu)化問題.很多研究者提出了一些替代方法來防止復(fù)雜的全局優(yōu)化問題，文獻11將定位問題轉(zhuǎn)換成一個半正定規(guī)劃松弛問題Semidefinite Programming Relaxation，SDP進展求解，通過采用解決SDP的方法來降低求解ML問題的復(fù)雜度.文獻12提出用線性最小二乘法Linear Least Square，LLS解決定位問題.通過這個方法，可以在測量噪聲較小的情況下得到較好的定位性能.文獻13基于極小極大方法，提出了2個次優(yōu)的方案來解決定位問題，雖然已經(jīng)提出了很多有效的方法可以減少基于ToA的定位問題的復(fù)雜度和得到較好的定位精度，但是它們根本

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