一種新的傳感器節(jié)點(diǎn)分布式定位算法

　　摘要:大規(guī)模無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)定位問題可以歸結(jié)為高度非線性非凸的優(yōu)化問題，該問題在大規(guī)模無線傳感器網(wǎng)絡(luò)中難以直接求解。因此提出了一種新的傳感器節(jié)點(diǎn)分布式定位算法，首先將大規(guī)模無線傳感器網(wǎng)絡(luò)構(gòu)成的全局無向圖分解為一系列部分重疊的子圖，進(jìn)而將全局的優(yōu)化問題分解為一系列小規(guī)模的子圖內(nèi)優(yōu)化問題，每個子圖內(nèi)的優(yōu)化問題可以獨(dú)立進(jìn)行迭代求解。新的傳感器節(jié)點(diǎn)分布式定位算法每步迭代包含兩個步驟，首先使用 Barzilai-Borwein 梯度法估計(jì)出劃分好的部分重疊子圖中節(jié)點(diǎn)的位置，使用的 Barzilai-Borwein 梯度法具備收斂速度較快，計(jì)算復(fù)雜度較低的特點(diǎn)，然后再對不同部分重疊的子圖內(nèi)的同一個傳感器節(jié)點(diǎn)進(jìn)行融合求平均。通過理論分析和仿真結(jié)果表明，新的傳感器節(jié)點(diǎn)分布式定位算法與已有算法相比較，新的傳感器節(jié)點(diǎn)定位算法具有較高的擴(kuò)展性，可以在大規(guī)模無線傳感器網(wǎng)絡(luò)中有較高的定位精度，能滿足大規(guī)模的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位需求。

　　徐莎莎; 周芳; 李楊劍; 蔣俊正， 西安電子科技大學(xué)學(xué)報(bào) 發(fā)表時間：2021-09-18

　　關(guān)鍵詞: 無線傳感器網(wǎng)絡(luò);定位;分布式算法;圖模型;Barzilai-Borwein 梯度法

　　無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSN)是由大量微小的傳感器構(gòu)成的自組織網(wǎng)絡(luò)[1]。無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)可以檢測監(jiān)控區(qū)域中的物理信息并進(jìn)行數(shù)據(jù)處理，并將處理后的數(shù)據(jù)以無線通信的方式傳送到基站[1]。無線傳感器網(wǎng)絡(luò)有許多應(yīng)用，如醫(yī)學(xué)應(yīng)用中的病人檢測[2]，環(huán)境應(yīng)用中火山檢測[3]，家庭應(yīng)用中用水檢測等[4]。在上述廣泛應(yīng)用中，檢測到的信息需要與傳感器節(jié)點(diǎn)的位置結(jié)合起來，才能提供更有效的數(shù)據(jù)信息。因此，可以在傳感器中嵌入中國北斗衛(wèi)星導(dǎo)航系統(tǒng)(BeiDou Navigation Satellite System, BDS)模塊或全球定位系統(tǒng)(Global Positioning System, GPS)模塊。但這些模塊成本高，功耗大，無法適用于大規(guī)模的無線傳感器網(wǎng)絡(luò)。因此，選擇少量的傳感器節(jié)點(diǎn)嵌入中國北斗衛(wèi)星導(dǎo)航系統(tǒng)或全球定位系統(tǒng)模塊，這些傳感器節(jié)點(diǎn)稱為錨節(jié)點(diǎn)或已知位置(Location-Aware, LA)節(jié)點(diǎn)，可以獲得較精確的位置信息，其他傳感器節(jié)點(diǎn)則稱為未知位置(Location-Unaware, LU)節(jié)點(diǎn)[5]。之后采用測距技術(shù)，如接收信號強(qiáng)度 (Received-Signal-Strength, RSS)、到達(dá)時間(Time-Of-Arrival, TOA)、到達(dá)角(Angle-Of--Arrival, AOA)等測得無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)之間的距離[5]。然后使用定位算法估計(jì)出無線傳感器網(wǎng)絡(luò)中LU 節(jié)點(diǎn)的位置。

　　目前，已有很多定位算法被提出。從數(shù)據(jù)處理角度，可以將定位算法分為集中式定位算法和分布式定位算法。集中式定位算法將定位所需信息通過多跳的方式傳遞給存儲、計(jì)算能力較強(qiáng)的中央處理器進(jìn)行處理。文獻(xiàn)[5]將定位問題歸結(jié)為無約束的優(yōu)化問題，并采用修正牛頓法進(jìn)行求解，得到了較好的定位精度和定位速率[5]。但該算法計(jì)算復(fù)雜度較高。文獻(xiàn)[6]提出了一種集中式定位算法，將定位問題采用半正定規(guī)劃松弛的方法進(jìn)行求解，將結(jié)果作為初始值，進(jìn)而采用梯度下降法得出LU 節(jié)點(diǎn)的位置，提高了定位精度[6]。總之，集中式定位算法使用了全部的定位信息，定位精度較高，但通信代價也較高。離中央處理器較近的傳感器需要傳輸大量的信息，會較早地消耗完電量，導(dǎo)致整個無線傳感器網(wǎng)絡(luò)無法工作。而且，集中式定位算法計(jì)算復(fù)雜度較高，導(dǎo)致擴(kuò)展性較低，無法在大規(guī)模無線傳感器網(wǎng)絡(luò)中使用。而分布式定位算法使用傳感器節(jié)點(diǎn)自帶的處理器，對收集到的局部信息進(jìn)行處理，有效降低了通信代價和計(jì)算復(fù)雜度，具備良好的擴(kuò)展性，可用于大規(guī)模無線傳感器網(wǎng)絡(luò)。文獻(xiàn)[7]將非凸的定位問題松弛為凸的二階錐規(guī)劃問題，利用 LU 節(jié)點(diǎn)及其鄰居信息，設(shè)計(jì)分布式二階錐規(guī)劃定位算法進(jìn)行求解[7]。該算法可用于大規(guī)模無線傳感器網(wǎng)絡(luò)中，但定位精度較低。文獻(xiàn)[8]提出了一種分布式定位算法，在每個 LU 節(jié)點(diǎn)上，將非凸的定位問題松弛為凸的定位問題，并使用梯度法進(jìn)行求解，在通信半徑較小的情況下也有較好的定位效果，降低了通信代價[8]。但該算法需要將LU 節(jié)點(diǎn)部署在LA 節(jié)點(diǎn)的凸包中，才能有好的定位精度。文獻(xiàn)[9]將WSN 劃分為子圖，每個子圖滿足文中提出的剛性條件，用多維標(biāo)度算法對每個子圖定位，再將局部坐標(biāo)映射到全局坐標(biāo)系統(tǒng)[9]。該算法所需的LA 節(jié)點(diǎn)數(shù)目較少，且劃分的子圖數(shù)目較少，定位精度較高。但當(dāng)通信半徑較小，子圖無法滿足剛性條件時，無法定位。文獻(xiàn)[10]提出了一種基于超級節(jié)點(diǎn)的分布式傳感器節(jié)點(diǎn)定位算法，該算法將 LA 節(jié)點(diǎn)作為超級節(jié)點(diǎn)，對無線傳感器網(wǎng)絡(luò)進(jìn)行子圖劃分，并進(jìn)行求解[10]。該算法有較好的定位精度，但該劃分方法難以保證劃分的子圖能覆蓋中所有節(jié)點(diǎn)。

　　為了使定位算法有較高的擴(kuò)展性和定位精度，能夠有效用于大規(guī)模無線傳感器網(wǎng)絡(luò)中，筆者提出了一種新的分布式定位算法。首先將無線傳感器網(wǎng)絡(luò)看作一個圖模型，將整個圖分解為部分重疊的子圖，進(jìn)而將定位問題分解為一系列子圖中的優(yōu)化問題。然后提出一種分布式定位算法，迭代地求解 LU 節(jié)點(diǎn)位置，每次迭代包含兩個關(guān)鍵步驟：一是LU 節(jié)點(diǎn)位置估計(jì)，使用Barzilai-Borwein 梯度法求解子圖中小規(guī)模優(yōu)化問題，得到子圖中 LU 節(jié)點(diǎn)的估計(jì)位置;二是子圖融合，對部分重疊的子圖進(jìn)行融合，從而得到 LU 節(jié)點(diǎn)的估計(jì)位置。筆者所提算法與集中式定位算法相比，有近似的定位精度，并通過對算法計(jì)算復(fù)雜度分析，表明這種算法計(jì)算復(fù)雜度更低，可用于大規(guī)模無線傳感器網(wǎng)絡(luò)中。與分布式定位算法相比，筆者提出的算法有更高的定位精度，而且對部署區(qū)域邊界的LU 節(jié)點(diǎn)也有較好的定位效果。

　　1 定位問題的描述

　　1.1 圖模型

　　無線傳感器網(wǎng)絡(luò)是自組織網(wǎng)絡(luò)，可以通過無向圖 G V E = ( , ) 來描述。其中， V V V = ?1 2 ， 1 V n ={1,2,3, , } 表示無線傳感器網(wǎng)絡(luò)中LU 節(jié)點(diǎn)集合; 2 V m ={1,2,3, , } 表示無線傳感器網(wǎng)絡(luò)中LA 節(jié)點(diǎn)集合; { , } E e e = i ij ? ，i j n m , 1,2,3, , , 1,2,3, , = = ?表示節(jié)點(diǎn)之間邊的集合，其中， i? e 表示LU 節(jié)點(diǎn) i 與 LA 節(jié)點(diǎn)?之間可以直接通信， ij e 表示LU 節(jié)點(diǎn) i 和LU 節(jié)點(diǎn) j 之間可以直接通信。由于受到傳感器節(jié)點(diǎn)功率的限制，傳感器節(jié)點(diǎn)只能與通信半徑 R 內(nèi)的節(jié)點(diǎn)直接通信。這樣可以將無線傳感器網(wǎng)絡(luò)構(gòu)成的無向圖劃分為部分重疊的子圖，采用以LU 節(jié)點(diǎn)為中心將WSN 劃分為部分重疊的子圖： 1 = s s V G ? G (1) ( , ) G V E s s s = (2) 其中， V V V s s s = ?1 2，Vs1 表示子圖 Gs 中LU 節(jié)點(diǎn)的集合， Vs2 表示子圖 Gs 中LA 節(jié)點(diǎn)集合， E s 表示子圖 Gs 中節(jié)點(diǎn)之間邊的集合。如圖1 所示，傳感器節(jié)點(diǎn)分布在 2 [ 0.5,0.5] − 單位區(qū)域內(nèi)，其中，圓圈表示LU 節(jié)點(diǎn)，實(shí)心菱形表示LA 節(jié)點(diǎn)，虛線圓表示以LU 節(jié)點(diǎn)為圓心， R 為半徑，劃分出的部分重疊的子圖。

　　1.2 定位問題的歸結(jié)

　　在監(jiān)控區(qū)域 ( 1) d R d ?維空間中部署大量的傳感器節(jié)點(diǎn)，這些節(jié)點(diǎn)構(gòu)成無線傳感器網(wǎng)絡(luò)。無線傳感器網(wǎng)絡(luò)中共有 N 個節(jié)點(diǎn)，其中有 m 個 LA 節(jié)點(diǎn)， n 個 LU 節(jié)點(diǎn)。考慮傳感器節(jié)點(diǎn)部署在 d = 2 的二維歐幾里得空間中。LA 節(jié)點(diǎn)位置表示為 a? , 1,2,3, , ? = m ;LU 位置表示為 , 1,2,3, , i x i n = 。LU 節(jié)點(diǎn) i 與節(jié)點(diǎn) j 之間的歐氏距離表示為 ij d ，d d ij ji = [8];LU 節(jié)點(diǎn) i 與 LA 節(jié)點(diǎn)?之間的歐式距離表示為 i? d 。假設(shè)傳感器節(jié)點(diǎn)的最大通信半徑為 R ，則對于每個 LU 節(jié)點(diǎn) i 定義兩個集合: { , , 1,2,3, , } N j d R j n i ij = ? = 和 { , , 1,2,3, , } M d R m i i = ? = ? ? ?，其中 Ni 表示在通信半徑 R 內(nèi)，可以直接和節(jié)點(diǎn) i 通信的 LU 節(jié)點(diǎn)鄰居集合; Mi 表示在通信半徑 R 內(nèi)，可以直接和節(jié)點(diǎn) i 通信的LA 節(jié)點(diǎn)鄰居集合。定位問題可以描述為：利用 m 個 LA 節(jié)點(diǎn)的位置信息，節(jié)點(diǎn)的鄰居信息和節(jié)點(diǎn)之間帶噪聲的距離信息，估計(jì)出 n 個 LU 節(jié)點(diǎn) xi , 1,2,3, , i n = 的位置。因此，WSN 中節(jié)點(diǎn)定位問題可以歸結(jié)為一個無約束的優(yōu)化問題[5,6]： 2 2 2 2 2 2 2 2 2 2 , 1,2,3, , 1 1 minimize i i i n n ij i j ij i i i i n i j N i M d d ? ? ??? ? = = ? = ?? ? ? ? − − + − − x x x x a (3) 其中，?ij 和?i?是權(quán)重。因?yàn)?ij d 和 i d ?是帶噪聲的測距，因此給可信度較高的測距設(shè)置較大的權(quán)重;反之，給可信度較低的測距設(shè)置較小的權(quán)重[5,6]。

　　2 分布式定位算法

　　2.1 子圖內(nèi)定位問題的描述

　　根據(jù)節(jié)1.1，將無線傳感器網(wǎng)絡(luò)構(gòu)成的無向圖以LU 節(jié)點(diǎn)為中心劃分為部分重疊的子圖后，可以將定位問題式(3)近似地重新構(gòu)造為

　　其中，E s 為子圖 Gs 中節(jié)點(diǎn)之間邊的集合， ij d 和 i d ?分別為子圖 Gs 中 LU 節(jié)點(diǎn)之間以及 LU 節(jié)點(diǎn)與 LA 節(jié)點(diǎn)之間的距離。使用 RSS 技術(shù)測得的距離包含噪聲，噪聲模型如式(5)、(6)所示[6-8]。而且 LA 節(jié)點(diǎn)即使加上GPS 模塊，由于受到電離層誤差、對流層誤差等多種誤差的影響，得到的LA 位置也是有噪聲的，噪聲模型如式(7)所示[7]。 1 2 = − ? + x x 1 ? ? ij i j ij d (5) 2 1 x a 1 ? ? ? = − ? +? ? i i i d (6) 2 1 ? ? ? a a = ? +? ? (7) 其中， 1 ? ?[0,1] 是距離噪聲因子，用于控制測距之間的噪聲強(qiáng)度;? a 是LA 節(jié)點(diǎn)的真實(shí)位置; 2 ? ?[0,1] 是 LA 節(jié)點(diǎn)位置噪聲因子，用于控制 LA 節(jié)點(diǎn)位置的噪聲強(qiáng)度; ij ? 、 i??和??是隨機(jī)噪聲，是一個正態(tài)隨機(jī)變量 N(0,1) 。

　　式(4)中?ij 和?i?是子圖 Gs 中根據(jù)節(jié)點(diǎn)之間距離的反比取的歸一化權(quán)重。兩個節(jié)點(diǎn)之間相距越近，使用 RSS 技術(shù)測得的距離可信度越高[11]，應(yīng)該賦予較高的權(quán)重，反之，應(yīng)該賦予較低的權(quán)重[5,10]。權(quán)重分別為： 1 1 1 ( , ) ( , ) s s ij ij ij i i j E i E d d d ??? − − − ? ? = ? ? + (8) 1 1 1 ( , ) ( , ) s s i i ij i i j E i E d d d ????? − − − ? ? = ? ? + (9) 使用 1 1s n V = 表示子圖 Gs 中 LU 節(jié)點(diǎn)數(shù)目; 2 2s n V = 表示子圖 Gs 中 LA 節(jié)點(diǎn)數(shù)目; 1 2 [ , ] i i i x = x x 表示 LU 節(jié)點(diǎn) i x 的坐標(biāo); 1 2 [ , ] a a a? ? ? = 表示LA 節(jié)點(diǎn) a?的坐標(biāo); 1 T 2 1 1 2 3 1 [ , , , , ] n n R ? x x x x x = ?表示子圖 Gs 中所有 LU 節(jié)點(diǎn)坐標(biāo)構(gòu)成的列向量; 2 T 2 1 1 2 3 2 [ , , , , ] n n R ? a a a a a = ?表示子圖 Gs 中所有 LA 節(jié)點(diǎn)坐標(biāo)構(gòu)成的列向量; 1 2n I 表示 1 1 2 2 n n ?的單位矩陣; 2 2n I 表示 2 2 2 2 n n ?的單位矩陣; i1 e 和 i2 e 分別表示 1 2n I 的第 2 1 i − 列和第 2i 列;?1 e 和? 2 e 分別表示 2 2n I 的第 2 1 ? − 列和第 2?列。根據(jù)上述定義， T i i 1 1 x = e x ， T i i 2 2 x = e x ， T 1 1 a? ? = e a ， T 2 2 a? ? = e a 。則節(jié)點(diǎn)間的真實(shí)距離可寫為 2 T 2 x x x Ax i j − = (10) 2 T T T T i ? 2 x a x Bx x Ca a Dx a Ea − = − − + (11) 其中， T T 1 1 1 1 2 2 2 2 A e e e e e e e e = − − + − − ( )( ) ( )( ) i j i j i j i j (12) T T B e e e e = + i i i i 1 1 2 2 (13) T T C e e e e = + i i 1 1 2 2 ? ? (14) T T D e e e e = + ? ? 1 1 2 2 i i (15) T T E e e e e = + ? ? ? ? 1 1 2 2 (16) 式(4)可以寫為 1 2 T 2 2 2 T T T T 2 2 , ( , ) ( , ) minimize ( ) ( ) ( ) i s s s s ij ij i i i V i j E i E f d d ? ??? ??? ? x x x Ax x Bx x Ca a Dx a Ea = − + − − + − ? ? (17) ( ) s f x 的梯度向量? ( ) x s f 為 2 T 2 2 T T T T 2 T ( , ) ( , ) ( ) 4 ( )( ) 2 ( )(2 ) s s s ij ij i i i j E i E f d d ? ??? ?? ?? = − + − − + − − − x x Ax Ax x Bx x Ca a Dx a Ea Bx Ca D a ?

　　2.2 子圖求解

　　2.2.1 初始定位 ?

　　在獲得 WSN 中節(jié)點(diǎn)之間測距信息后，采用簡單的極大似然估計(jì)法獲得 LU 節(jié)點(diǎn)的估計(jì)值[12]。目的是為了得到好的初始值。

　　假設(shè)D 點(diǎn)為LU 節(jié)點(diǎn)，坐標(biāo)為 ( , ) x y ，在D 點(diǎn)的通信半徑 R 內(nèi)有 m 個LA 節(jié)點(diǎn) 1,2,3, ,m ，坐標(biāo)分別為 1 1 2 2 3 3 ( , ),( , ),( , ), ,( , ) m m x y x y x y x y 。使用 RSS 測距法測得 D 點(diǎn)至 m 個 LA 節(jié)點(diǎn)的測距分別為 1 2 3 , , , , m d d d d 。則測得的距離與D 點(diǎn)坐標(biāo)和 m 個LA 節(jié)點(diǎn)坐標(biāo)之間有以下關(guān)系： 2 2 2 1 1 1 2 2 2 2 2 2 2 2 2 ( ) ( ) ( ) ( ) ( ) ( ) m m m d x x y y d x x y y d x x y y = − + − ?? = − + − ??? = − + − ?? (19) 將前 m−1 個方程與第 m 分方程相減，得到以下方程組： 2 2 2 1 1 1 1 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2( ) 2( ) 2( ) 2( ) m m m m m m m m m m x x x y y y x x y y d d x x x y y y x x y y d d − + − = − + − − + − + − = − + − − + 2 2 1 1 1 2 2 2 2 1 1 2( ) 2( ) m m m m m m m m m m x x x y y y x x y y d d − − − − − ?????????? − + − = − +? − − + ?? ( 20) 式(20)可寫為矩陣形式： AX b = (21) 最小二乘解即為LU 節(jié)點(diǎn)D 的估計(jì)值： T 1 T ˆ X A A A b ( )− = (22) 在實(shí)際情況中，傳感器節(jié)點(diǎn)隨機(jī)部署，且受到通信半徑 R 的限制，很難保證每個LU 節(jié)點(diǎn)都有3 個及以上的 LA 鄰居。因此，本文使用以下規(guī)則估計(jì) LU 節(jié)點(diǎn)的初始位置：(1) 當(dāng)LU 節(jié)點(diǎn)有 3 個及以上的 LA 鄰居時，使用最大似然估計(jì)法計(jì)算LU 節(jié)點(diǎn)的初始位置;(2)當(dāng)LU 節(jié)點(diǎn)有低于3 個LA 鄰居時，將距離LU 節(jié)點(diǎn)最近的 LA 節(jié)點(diǎn)的位置作為其初始位置;(3)當(dāng) LU 節(jié)點(diǎn)沒有 LA 鄰居時，將傳感器節(jié)點(diǎn)分布區(qū)域的中心作為LU 節(jié)點(diǎn)的初始位置，這樣最大的初始定位誤差為區(qū)域?qū)蔷€的一半。

　　2.2.2 Barzilai-Borwein 梯度法

　　將無線傳感器網(wǎng)絡(luò)劃分為部分重疊的子圖后，子圖中定位問題式(4)規(guī)模遠(yuǎn)小于原定位問題式(3)的規(guī)模，而且使用極大似然估計(jì)法可以得到較好的初始值。因此，可以用簡單的梯度法進(jìn)行優(yōu)化求解，梯度法中步長的選擇會影響收斂速度[13]。采用Barzilai-Borwein 梯度法，此方法不需要進(jìn)行線性搜索，僅使用當(dāng)前點(diǎn)和前一次迭代點(diǎn)的信息確定步長。在每次迭代中，只需要少量的存儲和簡單的梯度計(jì)算，降低了計(jì)算量。而且與傳統(tǒng)的最速下降法相比，很大程度上加快了梯度法的收斂速度[13]。梯度法迭代公式如下： 1 ( ) k k k k ? f x x x + = − ? (23) 可將上式寫為 1 ( ) k k k k f x x F x + = − ? (24) 其中，F(xiàn) I k k =? 。利用擬牛頓法割線方程的性質(zhì)[14]，求解以下最小二乘問題可以得到步長： 2 1 1 1 2 minimize ( ) ( ( ) ( )) k k k k k k f f ? − F x x x x − − ? − ? − − (25) 步長為 T 1 1 T 1 1 ( ) ( ) ( ) ( ( ) ( )) x x x x x x x x ? − − − − − − = − ? − ? k k k k k k k k k f f (26)

　　如果 k = 0 ，則通過回溯直線搜索法確定步長?0 ，設(shè)置參數(shù)? = 0.2，? = 0.5 ， 0 ? =1 ，若下式成立，則令? ?? 0 0 = ，繼續(xù)循環(huán)直到下式不成立。 T 0 0 ( ) ( ) ( ) s k k s k s k k f f f x x x x x + ? ? + ? ? ? ?? (27) 綜上所述，子圖中使用Barzilai-Borwein 梯度法進(jìn)行優(yōu)化求解的步驟如下： (1)使用極大似然估計(jì)法，粗略獲得 LU 節(jié)點(diǎn)的初始值，提取子圖 Gs 中 LU 節(jié)點(diǎn)的位置 xk ，作為初始值。設(shè) k = 0 ，表示第 k 次迭代; (2)計(jì)算搜索方向 qk ：q x = −? ( ) k s k f ; (3)計(jì)算步長：如果 k = 0 ，通過回溯直線搜索法確定步長?0 ;否則通過式(27)計(jì)算步長?k ; (4)更新子圖 Gs 中LU 節(jié)點(diǎn)位置： 1 x x q k k k k + = +?; (5)判斷迭代終止條件：如果滿足 1 ( ) ( ) 1 ( ) x x x ? + − ? + s k s k s k f f f ( ?是一個很小的正數(shù)，設(shè)置為? = − 1 10 e )，或 k ?100 ，則終止迭代， k+1 x 即為迭代結(jié)果，否則令 k k = +1 返回到(2)。

　　2.3 子圖融合

　　在構(gòu)建圖模型時，將 WSN 構(gòu)成的無向圖 G 以 LU 節(jié)點(diǎn)為中心分解為 n 個部分重疊的子圖。如圖 1 所示，同一個 LU 節(jié)點(diǎn)會位于不同的子圖中。因此，對每個子圖優(yōu)化求解后，對于相同的 LU 節(jié)點(diǎn)會有不同的估計(jì)值。需要對子圖進(jìn)行融合，從而得到每個 LU 節(jié)點(diǎn)的估計(jì)值。而且可能會出現(xiàn)某個子圖由于可用的信息較少，導(dǎo)致估計(jì)出的 LU 節(jié)點(diǎn)位置誤差較大的問題，子圖融合可以有效的降低這部分節(jié)點(diǎn)的誤差，從而提高整體WSN 的定位精度。子圖融合公式如下： , 1 ( 1,2,3, , ) i i i s i s N i n N ? x x = = ? (28) 其中， Ni 表示包含LU 節(jié)點(diǎn) i 的子圖索引集合; is, x 表示子圖 Gs 中LU 節(jié)點(diǎn) i 的坐標(biāo); i x 表示LU 節(jié)點(diǎn) i 融合之后的坐標(biāo)。經(jīng)過上述分析，分布式定位算法的整體流程如算法1 所示。

　　算法1 分布式定位算法。準(zhǔn)備工作：將 N 個傳感器隨機(jī)部署在檢測區(qū)域內(nèi)，其中有 m 個LA 節(jié)點(diǎn)， n 個LU 節(jié)點(diǎn)，通信半徑為 R 。以 LU 節(jié)點(diǎn)為中心，通信半徑內(nèi)與 LU 節(jié)點(diǎn)直接相連的節(jié)點(diǎn)為鄰居節(jié)點(diǎn)，構(gòu)成一個子圖。從而將 WSN 劃分為 n 個部分重疊的子圖。令 t = 0 。輸入：使用節(jié)2.2.1 中采用的極大似然估計(jì)法及相關(guān)規(guī)則，對LU 節(jié)點(diǎn)進(jìn)行粗略的初始定位，定位結(jié)果為 ()t p 。將其作為步驟(1)中進(jìn)行優(yōu)化求解的初始值; (1) 采用節(jié)2.2.2Barzilai-Borwein 梯度法對劃分好的子圖進(jìn)行優(yōu)化求解; (2) 采用節(jié)2.3 提出的子圖融合的方法，對部分重疊的子圖進(jìn)行融合，得到第 t +1 次迭代的定位結(jié)果 ( 1) t+ p ; (3) 判斷迭代終止條件。若 ( 1) ( ) 2 max t t i i ? + p p − ? ( ?是一個很小的正數(shù)，本文設(shè)置為 1 2 e − )，其中， i n =1,2,3, , ， ( 1) t i + p 表示LU 節(jié)點(diǎn) i 在第 t +1 次迭代的估計(jì)值， ()t i p 表示LU 節(jié)點(diǎn) i 在第 t 次迭代的估計(jì)值，則 ( 1) t+ p 為最終估計(jì)出的 LU 節(jié)點(diǎn)坐標(biāo)。否則，將 ( 1) t+ p 作為新的初始值，令 t t = +1 ，返回至步驟(1)繼續(xù)迭代。輸出： ( 1) t+ p 作為最終定位結(jié)果。

　　2.4 計(jì)算復(fù)雜度分析

　　采用Barzilai-Borwein 梯度法對子圖進(jìn)行優(yōu)化求解，由于該算法是迭代算法且每個子區(qū)域的節(jié)點(diǎn)個數(shù)可能不同，設(shè) max{ }s s d N = ，因此文中算法的計(jì)算復(fù)雜度為 O dnK ( ) ，其中 d n ? ，n 表示LU 節(jié)點(diǎn)個數(shù)， K 表示算法收斂時的迭代次數(shù)。文獻(xiàn)[5]是集中式算法，采用修正牛頓法對定位問題進(jìn)行優(yōu)化求解，此算法的計(jì)算復(fù)雜度為 3 O n K ( ) 。文獻(xiàn)[8]是分布式算法，采用梯度下降法對 LU 節(jié)點(diǎn)進(jìn)行優(yōu)化求解，此算法的計(jì)算復(fù)雜度為 ( ) O d nK G ，其中 Gd 表示節(jié)點(diǎn)的平均度。通過對計(jì)算復(fù)雜度的分析，可以看出文中算法的計(jì)算復(fù)雜度遠(yuǎn)小于文獻(xiàn)[5]中集中式算法的計(jì)算復(fù)雜度，并且，文中算法的計(jì)算復(fù)雜度與文獻(xiàn)[8]的分布式算法的計(jì)算復(fù)雜度同一個數(shù)量級。因此，筆者提出的分布式定位算法可以有效地適用于大規(guī)模 WSN 中的節(jié)點(diǎn)定位問題。

　　3 仿真結(jié)果及分析

　　為了表明筆者所提分布式算法的性能，這一節(jié)做了一系列仿真實(shí)驗(yàn)。使用軟件 MATLAB R2016a 進(jìn)行仿真實(shí)驗(yàn)，并在3.60 GHz 的Intel i7-7700 處理器和8 GB RAM 的PC 機(jī)上運(yùn)行。為了表明算法的魯棒性，都隨機(jī)進(jìn)行5 次實(shí)驗(yàn)取平均。具體的實(shí)驗(yàn)參數(shù)設(shè)置及說明如表1 所示。為了客觀地評價該分布式定位算法的性能，采用與文獻(xiàn)[7]相同的評價指標(biāo)，即平均定位誤差( err )： 2 1 err n i i i n = − = ? p p (29) 其中， i p 表示定位算法估計(jì)出來的LU 節(jié)點(diǎn)位置; i p 表示LU 節(jié)點(diǎn)的真實(shí)位置; n 表示LU 節(jié)點(diǎn)的數(shù)目。

　　實(shí)驗(yàn) 1 為了研究 LA 節(jié)點(diǎn)數(shù)目對定位精度的影響，文中算法與文獻(xiàn)[5]中的集中式定位算法以及文獻(xiàn) [7-8]中的分布式定位算法在表2 所示的仿真參數(shù)設(shè)置下做對比試驗(yàn)。在本例中節(jié)點(diǎn)數(shù)目 m n + =200，距離噪聲因子? 1=0.10，LA 節(jié)點(diǎn)位置噪聲因子? 2=0.0 ，在固定通信半徑 R = 0.20 的情況下，改變 WSN 中的 LA 節(jié)點(diǎn)所占比例 p 。仿真結(jié)果如圖2 所示，可以看出，隨著LA 數(shù)目所占比例 p 的增加，本文算法的定位精度得到提高。這是因?yàn)?LA 數(shù)目的增加，能夠提供更多的已知位置的信息，使得 LU 節(jié)點(diǎn)有更好的初始位置和更多更準(zhǔn)確的鄰居信息，從而提高了定位精度。文中算法與文獻(xiàn)[5]相比，在相同的 p 下，有近似的定位精度。與文獻(xiàn)[7-8]相比，在相同的 p 下，文中算法的 err 更小，定位精度更高。這意味著，在大規(guī)模 WSN 中，文中算法可以利用較少的LA 節(jié)點(diǎn)數(shù)目，達(dá)到較好的定位效果，從而降低WSN 的部署成本。

　　實(shí)驗(yàn)2 為了研究通信半徑 R 對定位精度的影響，文中算法與文獻(xiàn)[5]中的集中式定位算法以及文獻(xiàn)[7-8] 中的分布式定位算法在表2 所示的仿真參數(shù)設(shè)置下做對比試驗(yàn)。在本例中節(jié)點(diǎn)數(shù)目 m n + =200，距離噪聲因子? 1=0.10，LA 節(jié)點(diǎn)位置噪聲因子? 2=0.0 ，在固定無線傳感器網(wǎng)絡(luò)中LA 節(jié)點(diǎn)所占比例 P=0.15 的情況下，改變通信半徑 R 進(jìn)行仿真。仿真結(jié)果如圖3 所示，可以看出，隨著通信半徑 R 的增加，文中算法的定位精度會得到提高。這是因?yàn)?R 的增加，使得每個LU 節(jié)點(diǎn)有更多鄰居信息可以使用，從而提高了定位精度。文中算法與另外三種算法相比，在相同的 R 下， err 更小，定位精度更高。這意味著，在大規(guī)模WSN 中，文中算法可以使用較小的 R ，達(dá)到較好的定位效果。同時，較小的 R 可以降低傳感器節(jié)點(diǎn)的能量消耗，從而提高整個無線傳感器網(wǎng)絡(luò)的使用壽命。

　　實(shí)驗(yàn) 3 為了研究文中算法在不同網(wǎng)絡(luò)規(guī)模和噪聲情況下的定位效果，本次實(shí)驗(yàn)節(jié)點(diǎn)分布區(qū)域?yàn)?2 [ 0.5,0.5] − ，改變節(jié)點(diǎn)總數(shù) N ，通信半徑 R ，LA 位置噪聲因子 2 ?進(jìn)行仿真，并與文獻(xiàn)[5,7-8]進(jìn)行對比。仿真參數(shù)設(shè)置和定位結(jié)果如表 2 所示。可以看出，在相同規(guī)模的 WSN 中，對 LA 位置添加噪聲后，各算法的定位精度均會下降。在小規(guī)模無線傳感器網(wǎng)絡(luò)( N ? 500 )中，文中算法與文獻(xiàn)[5]提出的集中式定位算法相比，有近似的定位精度，但在大規(guī)模無線傳感器網(wǎng)絡(luò)( N ? 500 )中，集中式定位算法便無法定位，而文中算法仍有較好的定位精度，而且與文獻(xiàn)[7-8]提出的分布式定位算法相比，在相同的仿真參數(shù)下，始終有更好的定位精度。綜上所述，筆者提出的分布式定位算法有良好的擴(kuò)展性，可有效用于大規(guī)模的無線傳感器網(wǎng)絡(luò)中，并且有較高的定位精度。

　　4 結(jié)束語

　　針對無線傳感器網(wǎng)絡(luò)定位精度較低、擴(kuò)展性不高問題，筆者提出了一種分布式定位算法。首先將整個無線傳感器網(wǎng)絡(luò)構(gòu)成的無向圖分解為部分重疊的子圖，并構(gòu)造出子圖的優(yōu)化問題，然后采用筆者所提算法進(jìn)行優(yōu)化求解，求解的過程包括：子圖內(nèi)的位置估計(jì)和部分重疊子圖的融合。仿真實(shí)驗(yàn)證明，與現(xiàn)有集中式定位算法相比，有較高的擴(kuò)展性，可有效用于大規(guī)模無線傳感器網(wǎng)絡(luò)。與現(xiàn)有分布式定位算法相比，有更高的定位精度。可見筆者提出的算法具備一定的優(yōu)勢，可以為無線傳感器網(wǎng)絡(luò)的經(jīng)濟(jì)、高效、實(shí)用性發(fā)展提供了可靠的技術(shù)支持，進(jìn)而促進(jìn)無線傳感器網(wǎng)絡(luò)在環(huán)境科學(xué)、醫(yī)療健康等多個領(lǐng)域的應(yīng)用。