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

2、識(shí)碼：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目前，隨著無(wú)線通信技術(shù)、嵌入式技術(shù)和網(wǎng)絡(luò)技術(shù)的快速開展，無(wú)線傳感網(wǎng)絡(luò)1Wireless Sensor Networks，WSN得到了前所未有的關(guān)注，已經(jīng)成為研究熱點(diǎn).定位技術(shù)2是WSN中最重要的根底性研究之一，沒(méi)有位置信息的WSN應(yīng)用是沒(méi)有任何意義的.基于WSN的定位是根據(jù)不同定位技術(shù)的測(cè)量值來(lái)確定網(wǎng)絡(luò)中傳感節(jié)點(diǎn)的位置，常采用的定位技術(shù)主要有基于到達(dá)時(shí)間3Time of Ar

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

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

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