基于全局式優(yōu)化策略的無線傳感器網(wǎng)絡節(jié)點定位方法

1.基于全局式優(yōu)化策略的無線傳感器網(wǎng)絡節(jié)點定位方法，其特征在于，包括步驟如下：
步驟S1：通過測量得到無線傳感器網(wǎng)絡中1跳節(jié)點間的距離和相對角度；
步驟S2：利用1跳節(jié)點間的距離和相對角度計算無線傳感器網(wǎng)絡內(nèi)2跳節(jié)點間的距離；
步驟S3：節(jié)點間通過通訊選取1跳節(jié)點最多的節(jié)點作為初始點；
步驟S4：將古典多維尺度測量與極大似然估計相結合計算無線傳感器網(wǎng)絡中節(jié)點的相對坐標和全局優(yōu)化策略對無線傳感器網(wǎng)絡中所有節(jié)點位置進行定位；
對無線傳感器網(wǎng)絡中所有節(jié)點位置進行定位包括步驟如下：
步驟S41：利用古典多維尺度測量方法計算初始點及其1跳節(jié)點形成的子網(wǎng)絡中節(jié)點的相對坐標并建立相對坐標系，并把這些節(jié)點稱為已定位節(jié)點，其余未計算出自身相對坐標的節(jié)點稱為未定位節(jié)點；
步驟S42：已定位的節(jié)點向周圍未定位的節(jié)點廣播自身的坐標，最遠傳到已定位節(jié)點的2跳節(jié)點為止；
步驟S43：設定n＞1的初始點n跳節(jié)點，根據(jù)接收到的已定位的(n-1)跳和(n-2)跳節(jié)點的相對坐標，再利用極大似然估計法計算初始點的n跳節(jié)點的相對坐標，計算出自身相對坐標的節(jié)點為已定位節(jié)點，其余未計算出自身相對坐標的節(jié)點稱為未定位節(jié)點，當(n-2)為0時，表示初始點本身；
步驟S44：若無線傳感器網(wǎng)絡內(nèi)的所有節(jié)點都已完成定位或滿足預先設定的停止條件，則轉入步驟S45，否則返回步驟S42；
步驟S45：無線傳感器網(wǎng)絡內(nèi)的每個節(jié)點基于其1跳節(jié)點和2跳節(jié)點的相對坐標建立目標函數(shù)，采用最速下降法對無線傳感器網(wǎng)絡中所有節(jié)點的相對坐標估計進行全局優(yōu)化，當滿足誤差設定條件時轉入步驟S46；
步驟S46：利用裝有全球定位系統(tǒng)的參考節(jié)點的已知絕對坐標及其通過計算獲得的相對坐標求取相對坐標系到絕對坐標系的變換矩陣；
步驟S47：利用變換矩陣將無線傳感器網(wǎng)絡節(jié)點的相對坐標轉換為絕對坐標。
2.根據(jù)權利要求1的定位方法，其特征在于，當無線傳感器網(wǎng)絡中所有節(jié)點的相對坐標都計算出后或滿足預先設定的停止條件時，開始對無線傳感器網(wǎng)絡中所有節(jié)點的相對坐標進行全局優(yōu)化。
3.根據(jù)權利要求1的定位方法，其特征在于，所述全局優(yōu)化策略是利用1跳節(jié)點或2跳節(jié)點間的距離，建立整個網(wǎng)絡的全局優(yōu)化目標函數(shù)f為：
其中節(jié)點i和節(jié)點j均為無線傳感器網(wǎng)絡中的節(jié)點且互為1跳或2跳節(jié)點，dij表示1跳節(jié)點間的實測距離或根據(jù)1跳節(jié)點間距離和相對角度計算出的2跳節(jié)點間距離，pij為節(jié)點i和j間的估計距離：
上式中(xi，yi，zi)和(xj，yj，zj)分別為節(jié)點i和j的相對估計坐標。
4.根據(jù)權利要求1的定位方法，其特征在于，采用最速下降法優(yōu)化節(jié)點i的相對坐標，節(jié)點i的相對坐標的第k+1次優(yōu)化估計值(xi(k+1)，yi(k+1)，zi(k+1))表示為：
其中Δ表示修正系數(shù)； 為目標函數(shù)相對于xi，yi，zi的偏導數(shù)；無線
傳感器網(wǎng)絡中所有節(jié)點經(jīng)過第k+1次修正后計算目標函數(shù)f(k+1)并判斷是否滿足式：
|f(k)-f(k+1)|≤ε，若滿足，則結束優(yōu)化過程，否則各節(jié)點發(fā)布其第k+1次優(yōu)化估計值，繼續(xù)進行優(yōu)化，其中ε為一個小的正實數(shù)值，k≥0。

基于全局式優(yōu)化策略的無線傳感器網(wǎng)絡節(jié)點定位方法\n技術領域\n[0001] 本發(fā)明屬于無線傳感器網(wǎng)絡領域，涉及無線傳感器網(wǎng)絡中節(jié)點的相對定位和絕對定位方法。\n背景技術\n[0002] 無線傳感器網(wǎng)絡中的定位方法可分為非距離式定位和距離式定位兩類。非距離式定位是利用節(jié)點間的跳(英文名為hop)數(shù)或求區(qū)域質心來計算節(jié)點的坐標。N.Bulusu和J.Heidemann提出了一種非距離式定位的中心算法。傳感器網(wǎng)絡中包含參考節(jié)點和普通節(jié)點，通過計算k個參考節(jié)點的中心來估計普通節(jié)點的位置或坐標。這種方法誤差較高，要得到較高的定位精度需要很多參考節(jié)點且均勻分布在網(wǎng)絡的外圍。T.He和C.Huang提出的APIT(Approximation Point-in-Triangulation Test)方法是通過計算不同三角形的重疊區(qū)域的中心來確定節(jié)點的坐標。APIT適用于節(jié)點隨機分布且不要求各節(jié)點通訊能力完全一樣的情況，定位精度在很大程度上取決于參考節(jié)點的數(shù)量和重疊區(qū)域的大小。距離式定位一般利用節(jié)點間的距離來計算節(jié)點的相對位置，定位精度在很大程度上取決于節(jié)點間測距的精度。D.Niculescu和B.Nath提出了一種估計節(jié)點間距離的方法，這種方法適用于節(jié)點規(guī)則分布的情況，在節(jié)點隨機分布的情況下估計距離會產(chǎn)生較大誤差。Y.Shang和W.Ruml提出了利用MDS計算節(jié)點坐標的方法：MDS-MAP(C)、MDS-MAP(C，R)、MDS-MAP(P)和MDS-MAP(P，R)。這四種方法在節(jié)點的連通度高和參考節(jié)點比例大時可取得很好的定位效果。此外也有利用移動參考節(jié)點對網(wǎng)絡中固定節(jié)點進行定位的方法。非距離式定位方法的定位精度較低，現(xiàn)有的距離式定位方法的精度雖然比非距離式定位方法的高，但由于在估計節(jié)點距離時利用了最短路徑等方法而不是直接測量或計算得到的，因此精度也不是很高。\n發(fā)明內(nèi)容\n[0003] 為了解決現(xiàn)有技術精度不高的問題，本發(fā)明目的是利用測量獲得的無線傳感器網(wǎng)絡中1跳節(jié)點間的距離和相對角度信息，通過計算方法實現(xiàn)對網(wǎng)絡中所有節(jié)點進行相對定位或絕對定位，為此本發(fā)明提供一種基于全局式優(yōu)化策略的無線傳感器網(wǎng)絡節(jié)點定位方法。\n[0004] 為達到所述的目的，本發(fā)明提供的基于全局式優(yōu)化策略的無線傳感器網(wǎng)絡節(jié)點定位方法，首先要測量無線傳感器網(wǎng)絡中1跳節(jié)點之間的距離和相對角度，利用1跳節(jié)點之間的距離和相對角度計算2跳節(jié)點之間的距離，再根據(jù)以上信息，利用古典多維尺度計算方法(MDS方法)和極大似然估計相結合的方法計算所有節(jié)點的相對坐標，利用全局優(yōu)化策略對所有節(jié)點的相對坐標進行優(yōu)化，通過坐標變換將相對坐標轉換為絕對坐標。\n[0005] 本發(fā)明的有益效果：本發(fā)明在定位過程中是直接測量得到的距離(1跳節(jié)點間的距離)或通過測量值計算(2跳節(jié)點間的距離)得到的，與估計距離相比有更高的精度，因此節(jié)點的定位精度就更高。此外，在計算節(jié)點的相對坐標時，除了初始點及其1跳節(jié)點利用古典多維尺度計算方法外，其余節(jié)點的相對坐標都是用極大似然估計法計算得到的，計算量要小。\n附圖說明\n[0006] 圖1是本發(fā)明基于全局式優(yōu)化策略的無線傳感器網(wǎng)絡節(jié)點定位算法流程；\n[0007] 圖2是本發(fā)明無線傳感器網(wǎng)絡中2跳節(jié)點間的距離；\n具體實施方式\n[0008] 下面結合附圖對基于全局式優(yōu)化策略的無線傳感器網(wǎng)絡的節(jié)點定位方法進行詳細說明。\n[0009] 在圖1中給出了算法的流程。在圖2中給出了節(jié)點間關系。圖2中A、B、C表示無線傳感器網(wǎng)絡中3個節(jié)點，節(jié)點A與節(jié)點B之間可以直接通訊，節(jié)點B與節(jié)點C之間可以直接通訊，節(jié)點A與節(jié)點C之間無法直接通訊但可以經(jīng)節(jié)點B轉發(fā)一次實現(xiàn)相互通訊。節(jié)點A與節(jié)點B，節(jié)點B與節(jié)點C互為1跳節(jié)點；節(jié)點A與節(jié)點C互為2跳節(jié)點。n跳節(jié)點則指該節(jié)點至少經(jīng)過(n-1)個不同節(jié)點的轉發(fā)才可與另一節(jié)點實現(xiàn)相互通訊，這兩個節(jié)點互為n跳節(jié)點。\n[0010] 基于全局式優(yōu)化策略的無線傳感器網(wǎng)絡節(jié)點定位方法，其算法步驟包括：\n[0011] 步驟S1：通過測量得到無線傳感器網(wǎng)絡1跳節(jié)點間的距離和相對角度；\n[0012] 無線傳感器網(wǎng)絡節(jié)點間距離的測量可以采用TOA、TDOA或RSSI等測量方法；而無線傳感器網(wǎng)絡1跳節(jié)點間的相對角度的測量主要可以通過接收陣列或多個接收機確定發(fā)射節(jié)點信號的到達方向來計算相對角度。\n[0013] 步驟S2：利用1跳節(jié)點間的距離和相對角度計算傳感器網(wǎng)絡內(nèi)2跳節(jié)點間的距離；\n[0014] 如附圖2所示，節(jié)點A和節(jié)點C都是節(jié)點B的1跳節(jié)點，節(jié)點A和節(jié)點C互為2跳節(jié)點，因此通過1跳節(jié)點間的距離和相對角度，利用余弦定理可以計算出2跳節(jié)點間的距離。節(jié)點B接收到的節(jié)點A發(fā)射信號的到達角度為α，節(jié)點B接收到的節(jié)點C發(fā)射信號的到達的角度為β，∠ABC表示為γ，則有：\n[0015] \n[0016] 由于1跳節(jié)點間距離可測，所以可設節(jié)點A和節(jié)點B間的距離為d1，節(jié)點B和節(jié)點C間的距離為d2，由余弦定理可計算出2跳節(jié)點A和節(jié)點C間的距離d，如下式所示：\n[0017] \n[0018] 根據(jù)上述公式，無線傳感器網(wǎng)絡內(nèi)的所有2跳節(jié)點間的距離都可以計算。進而利用所有1跳節(jié)點間和2跳節(jié)點間的這些距離信息可以計算各節(jié)點的相對坐標。\n[0019] 步驟S3：節(jié)點間通過通訊選取1跳節(jié)點最多的節(jié)點作為初始點；\n[0020] 隨機選擇一個節(jié)點X，節(jié)點X向其1跳節(jié)點傳播節(jié)點數(shù)目信息和地址信息并將自身的置位寄存器由0置位為1，節(jié)點數(shù)目信息包括節(jié)點X的1跳節(jié)點數(shù)目和節(jié)點標號X，地址信息包括發(fā)送信息的節(jié)點X；節(jié)點X的1跳節(jié)點接收到信息后，查看自身的置位寄存器。\n[0021] 若置位寄存器為0，向節(jié)點X傳播“receive”信號，并保留接收到的信息，如果剛接收到信息的節(jié)點的1跳節(jié)點數(shù)目大于收到的節(jié)點數(shù)目信息中的1跳節(jié)點數(shù)目，則用自身的1跳節(jié)點數(shù)目替換節(jié)點數(shù)目信息中的1跳節(jié)點數(shù)目，并用自身的節(jié)點標號替換節(jié)點數(shù)目信息中的節(jié)點標號；如果自身的1跳節(jié)點數(shù)目不大于收到的節(jié)點數(shù)目信息中的1跳節(jié)點數(shù)目，則節(jié)點數(shù)目信息不變；再在地址信息中加入自身節(jié)點標號，然后將自身的置位寄存器由\n0置位為1，并向周圍傳播節(jié)點數(shù)目信息和地址信息；\n[0022] 若置位寄存器已經(jīng)為1，則刪除收到的信息。\n[0023] 這樣從節(jié)點X開始，節(jié)點數(shù)目信息和地址信息逐漸向外傳播并進行更新。當一個節(jié)點在傳播信息后未收到“receive”信號，說明它的1跳節(jié)點都已接受到了節(jié)點數(shù)目信息和地址信息。未收到“receive”信號的節(jié)點按照地址信息中記錄的節(jié)點標號將節(jié)點數(shù)目信息傳送回X節(jié)點。X節(jié)點接收到一個返回的節(jié)點數(shù)目信息后，設定一段延遲時間，在這段時間中如果接收到其他的返回節(jié)點數(shù)目信息，則重新計時延遲時間；如果沒有接收到其他的返回節(jié)點數(shù)目信息，X節(jié)點則停止接收。X節(jié)點比較接收到的節(jié)點數(shù)目信息中的1跳節(jié)點數(shù)目，選取1跳節(jié)點數(shù)目最大的節(jié)點標號，并向1跳節(jié)點數(shù)目最大的節(jié)點發(fā)送“初始點”信號，將1跳節(jié)點數(shù)目最大的節(jié)點作為初始點。\n[0024] 步驟S4:利用古典多維尺度測量、極大似然估計和全局優(yōu)化策略對無線傳感器網(wǎng)絡中所有節(jié)點位置進行定位。\n[0025] 步驟S41：利用古典多維尺度測量方法(MDS方法)計算初始點及其1跳節(jié)點形成的子網(wǎng)絡中節(jié)點的相對坐標并建立相對坐標系，并把這些節(jié)點稱為已定位節(jié)點，其余未計算出自身相對坐標的節(jié)點稱為未定位節(jié)點；\n[0026] 在一個r(r＝2或3)維空間中，假設任意兩個節(jié)點i和節(jié)點j的距離都已知，則(2)\n距離矩陣D是一個主對角線上元素都為0，其它元素都不為0的對稱矩陣，D 是由距離的平方構成的矩陣為：\n[0027] \n[0028] 其中 表示節(jié)點i與節(jié)點j間距離的平方。設B＝-0.5×JD(2)J，其中J＝\n-1\nIn×n-n 1n×n，In×n為單位矩陣，1n×n為全1矩陣。對矩陣B進行奇異值分解，可得B＝QAQ′，\n1/2\n則節(jié)點的相對坐標X＝QA 。在計算過程中，矩陣B的奇異值可能存在負值或0，此時選取矩陣B的最大的r個奇異值及對應的奇異向量計算相對坐標\n[0029] \n[0030] 當距離矩陣D沒有誤差或誤差很小時，Xr基本反映了節(jié)點在網(wǎng)絡中的相對位置。\n[0031] 步驟S42：已定位的節(jié)點向周圍未定位的節(jié)點廣播自身的坐標，最遠傳到已定位節(jié)點的2跳節(jié)點為止；\n[0032] 步驟S43：初始點的n跳(n>1)節(jié)點根據(jù)接收到的已定位的(n-1)跳和(n-2)跳節(jié)點的坐標，利用極大似然估計法計算初始點的n跳節(jié)點自身的相對坐標，當(n-2)為0時，表示初始點本身，并稱這些剛計算出自身相對坐標的節(jié)點為已定位節(jié)點，其余未計算出自身相對坐標的節(jié)點稱為未定位節(jié)點；\n[0033] 設在三維環(huán)境中，未知節(jié)點坐標為X(x，y，z)，收到的k(k≥4)個坐標分別為(x1，y1，z1)，(x2，y2，z2)，...，(xk，yk，zk)，它們到未知節(jié)點的距離分別為d1，d2，...，dk，則有[0034] \n[0035] 從第一個方程開始分別減去最后一個方程，得：\n[0036] \n[0037] 上述線性方程可表示為：AX＝b，其中\(zhòng)n[0038] \n[0039] \n[0040] 使用最小均方差估計方法可以得到節(jié)點的坐標為：\n[0041] \n[0042] 步驟S44：若無線傳感器網(wǎng)絡內(nèi)的全部節(jié)點都已完成定位或滿足預先設定的遞推計算次數(shù)停止條件，則轉入步驟S45，否則返回步驟S42；\n[0043] 預先設定的遞推計算次數(shù)停止條件是當遞推計算次數(shù)達到(與初始節(jié)點間跳數(shù)最大的節(jié)點的跳數(shù)-1)次時即滿足停止條件。\n[0044] 步驟S45：無線傳感器網(wǎng)絡內(nèi)的每個節(jié)點基于其1跳節(jié)點和2跳節(jié)點的相對坐標建立目標函數(shù)，采用最速下降法對無線傳感器網(wǎng)絡中所有節(jié)點的相對坐標估計進行優(yōu)化，當滿足誤差設定條件時轉入步驟S46；\n[0045] 當網(wǎng)絡中所有節(jié)點都已完成定位或滿足預先設定的遞推計算次數(shù)停止條件時，開始對無線傳感器網(wǎng)絡中的所有節(jié)點的相對坐標進行優(yōu)化。優(yōu)化時只利用1跳節(jié)點或2跳節(jié)點間的距離，整個無線傳感器網(wǎng)絡的全局優(yōu)化目標函數(shù)f為：\n[0046] \n[0047] 其中節(jié)點i和節(jié)點j均為無線傳感器網(wǎng)絡中的節(jié)點且互為1跳或2跳節(jié)點，dij表示節(jié)點間的實測距離(1跳節(jié)點間的距離)或根據(jù)1跳節(jié)點間距離和相對角度計算出的距離(2跳節(jié)點間的距離)，節(jié)點i和節(jié)點j間的估計距離pij表示為：\n[0048] \n[0049] 上式中(xi，yi，zi)和(xj，yj，zj)分別為節(jié)點i和j的相對估計坐標。\n[0050] 采用最速下降法，將目標函數(shù)f對節(jié)點i的坐標xi，yi，zi分別求導可得：\n[0051] \n[0052] 則節(jié)點i相對坐標的第k+1(k≥0)次優(yōu)化估計值(xi(k+1)，yi(k+1)，zi(k+1))可表示為\n[0053] \n[0054] 其中Δ表示修正系數(shù)，可取值為0.001。無線傳感器網(wǎng)絡中所有節(jié)點經(jīng)過第k+1次修正后計算目標函數(shù)f(k+1)并判斷是否滿足式：\n[0055] |f(k)-f(k+1)|≤ε，若滿足，則結束優(yōu)化過程；否則各節(jié)點發(fā)布其第k+1(k≥0)次優(yōu)化估計值，繼續(xù)進行優(yōu)化；\n[0056] 其中ε為一個小的正實數(shù)值，可取值為0.001。\n[0057] 步驟S46：利用裝有全球定位系統(tǒng)的參考節(jié)點的已知絕對坐標及其通過計算獲得的相對坐標求取相對坐標系到絕對坐標系的變換矩陣；\n[0058] 設T＝[T1，T2，T3，…，Tn]3×n表示n個節(jié)點在絕對坐標系下的絕對坐標，R＝[R1，R2，R3，…，Rn]3×n表示這n個節(jié)點對應的在相對坐標系下的相對坐標。若已知參考節(jié)點1，\n2，3，4的絕對坐標和相對坐標，則根據(jù)線性變換存在Q3×3使得\n[0059] [T1-T1，T2-T1，T3-T1，T4-T1]＝Q[R1-R1，R2-R1，R3-R1，R4-R1]\n[0060] 由上式可以求出相對坐標系到絕對坐標系的變換矩陣Q：\n[0061] Q＝[T2-T1，T3-T1，T4-T1]/[R2-R1，R3-R1，R4-R1]\n[0062] 步驟S47：利用變換矩陣將無線傳感器網(wǎng)絡節(jié)點的相對坐標轉換為絕對坐標。\n[0063] 節(jié)點i的絕對坐標可依據(jù)下式獲得：\n[0064] Ti＝Q[Ri-R1]+T1\n[0065] 其中Ti為節(jié)點i的絕對坐標，Ri為節(jié)點i的相對坐標，T1為已知參考節(jié)點1的絕對坐標，R1為參考節(jié)點1的相對坐標，Q為相對坐標系到絕對坐標系的變換矩陣。\n[0066] 以上所述，僅為本發(fā)明中的具體實施方式，但本發(fā)明的保護范圍并不局限于此，任何熟悉該技術的人在本發(fā)明所揭露的技術范圍內(nèi)，可理解想到的變換或替換，都應涵蓋在本發(fā)明的包含范圍之內(nèi)，因此，本發(fā)明的保護范圍應該以權利要求書的保護范圍為準。