徐莎莎，周 芳，李楊劍，蔣俊正，3

(1.桂林電子科技大學(xué) 信息與通信學(xué)院，廣西壯族自治區(qū) 桂林 541004；2.桂林電子科技大學(xué) 生命與環(huán)境科學(xué)學(xué)院，廣西壯族自治區(qū) 桂林 541004；3.桂林電子科技大學(xué) 廣西無線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室，廣西壯族自治區(qū) 桂林 541004)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)是由大量微小的傳感器構(gòu)成的自組織網(wǎng)絡(luò)[1]。無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)可以檢測(cè)監(jiān)控區(qū)域中的物理信息并進(jìn)行數(shù)據(jù)處理，并將處理后的數(shù)據(jù)以無線通信的方式傳送到基站[1]。無線傳感器網(wǎng)絡(luò)有許多應(yīng)用，如醫(yī)學(xué)應(yīng)用中的病人檢測(cè)[2]，環(huán)境應(yīng)用中火山檢測(cè)[3]，家庭應(yīng)用中用水檢測(cè)等[4]。在上述廣泛應(yīng)用中，檢測(cè)到的信息需要與傳感器節(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]。之后采用測(cè)距技術(shù)，如接收信號(hào)強(qiáng)度(Received-Signal-Strength，RSS)、到達(dá)時(shí)間(Time-Of-Arrival，TOA)、到達(dá)角(Angle-Of-Arrival，AOA)等測(cè)得無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)之間的距離[5]。然后使用定位算法估計(jì)出無線傳感器網(wǎng)絡(luò)中LU節(jié)點(diǎn)的位置。

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

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

1 定位問題的描述

1.1 圖模型

無線傳感器網(wǎng)絡(luò)是自組織網(wǎng)絡(luò)，可以通過無向圖G=(V，E)來描述。其中，V=V1∪V2，V1={1，2，3，…，n}表示無線傳感器網(wǎng)絡(luò)中LU節(jié)點(diǎn)集合；V2={1，2，3，…，m}表示無線傳感器網(wǎng)絡(luò)中LA節(jié)點(diǎn)集合；E={eiλ，eij}，(i=1，2，3，…，n；j=1，2，3，…，n；λ=1，2，3，…，m)表示節(jié)點(diǎn)之間邊的集合。其中，eiλ表示LU節(jié)點(diǎn)i與LA節(jié)點(diǎn)λ之間可以直接通信；eij表示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)

Gs=(Vs，Es) ，

(2)

圖1 子圖分解示意圖

其中，Vs=Vs1∪Vs2，Vs1表示子圖Gs中LU節(jié)點(diǎn)的集合，Vs2表示子圖Gs中LA節(jié)點(diǎn)集合，Es表示子圖Gs中節(jié)點(diǎn)之間邊的集合。如圖1所示，傳感器節(jié)點(diǎn)分布在[-0.5，0.5]2單位區(qū)域內(nèi)，其中，圓圈表示LU節(jié)點(diǎn)，實(shí)心菱形表示LA節(jié)點(diǎn)，虛線圓表示以LU節(jié)點(diǎn)為圓心，R為半徑，劃分出的部分重疊的子圖。

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

在監(jiān)控區(qū)域Rd(d≥1)維空間中部署大量的傳感器節(jié)點(diǎn)，這些節(jié)點(diǎn)構(gòu)成無線傳感器網(wǎng)絡(luò)。無線傳感器網(wǎng)絡(luò)中共有N個(gè)節(jié)點(diǎn)，其中有m個(gè)LA節(jié)點(diǎn)，n個(gè)LU節(jié)點(diǎn)?？紤]傳感器節(jié)點(diǎn)部署在d=2的二維歐幾里得空間中。LA節(jié)點(diǎn)位置表示為aλ，λ=1，2，3，…，m；LU位置表示為xi，i=1，2，3，…，n。LU節(jié)點(diǎn)i與LU節(jié)點(diǎn)j之間的歐氏距離表示為dij，dij=dji[8]；LU節(jié)點(diǎn)i與LA節(jié)點(diǎn)λ之間的歐式距離表示為diλ。假設(shè)傳感器節(jié)點(diǎn)的最大通信半徑為R，則對(duì)于每個(gè)LU節(jié)點(diǎn)i定義兩個(gè)集合：Ni={j，dij≤R，j=1，2，3，…，n}和Mi={λ，diλ≤R，λ=1，2，3，…，m}，其中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個(gè)LA節(jié)點(diǎn)的位置信息、節(jié)點(diǎn)的鄰居信息和節(jié)點(diǎn)之間帶噪聲的距離信息，估計(jì)出n個(gè)LU節(jié)點(diǎn)xi(i=1，2，3，…，n)的位置。因此，WSN中節(jié)點(diǎn)定位問題可以歸結(jié)為一個(gè)無約束的優(yōu)化問題[5-6]：

(3)

其中，ωij和ωiλ是權(quán)重。因?yàn)閐ij和diλ是帶噪聲的測(cè)距，因此給可信度較高的測(cè)距設(shè)置較大的權(quán)重；反之，給可信度較低的測(cè)距設(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)造為

(4)

其中，Es為子圖Gs中節(jié)點(diǎn)之間邊的集合，dij和diλ分別為子圖Gs中LU節(jié)點(diǎn)之間以及LU節(jié)點(diǎn)與LA節(jié)點(diǎn)之間的距離。使用RSS技術(shù)測(cè)得的距離包含噪聲，噪聲模型如式(5)、式(6)所示[6-8]。且LA節(jié)點(diǎn)即使加上GPS模塊，由于受到電離層誤差、對(duì)流層誤差等多種誤差的影響，得到的LA位置也是有噪聲的，噪聲模型如式(7)所示[7]。

dij=‖xi-xj‖2|1+τ1εij| ，

(5)

diλ=‖xi-aλ‖2|1+τ1εiλ| ，

(6)

(7)

式(4)中ωij和ωiλ是子圖Gs中根據(jù)節(jié)點(diǎn)之間距離的反比取的歸一化權(quán)重。兩個(gè)節(jié)點(diǎn)之間相距越近，使用RSS技術(shù)測(cè)得的距離可信度越高[11]，應(yīng)賦予較高權(quán)重，反之，應(yīng)賦予較低權(quán)重[5，10]。權(quán)重分別為

(8)

(9)

(10)

(11)

其中，

A=(ei1-ej1)(ei1-ej1)T+(ei2-ej2)(ei2-ej2)T，

(12)

(13)

(14)

(15)

(16)

式(4)可以改寫為

(17)

fs(x)的梯度向量?fs(x)為

(18)

2.2 子圖求解

2.2.1 初始定位

在獲得WSN中節(jié)點(diǎn)之間測(cè)距信息后，采用簡(jiǎ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個(gè)LA節(jié)點(diǎn)1，2，3，…，m，坐標(biāo)分別為(x1，y1)，(x2，y2)，(x3，y3)，…，(xm，ym)。使用RSS測(cè)距法測(cè)得D點(diǎn)至m個(gè)LA節(jié)點(diǎn)的測(cè)距分別為d1，d2，d3，…，dm。則測(cè)得的距離與D點(diǎn)坐標(biāo)和m個(gè)LA節(jié)點(diǎn)坐標(biāo)之間有以下關(guān)系：

(19)

將前m-1個(gè)方程與第m個(gè)方程相減，得到以下方程組：

( 20)

式(20)可寫為矩陣形式：

AX=b。

(21)

最小二乘解即為LU節(jié)點(diǎn)D的估計(jì)值：

(22)

在實(shí)際情況中，傳感器節(jié)點(diǎn)隨機(jī)部署，且受到通信半徑R的限制，很難保證每個(gè)LU節(jié)點(diǎn)都有3個(gè)及以上的LA鄰居。因此，筆者使用以下規(guī)則估計(jì)LU節(jié)點(diǎn)的初始位置：① 當(dāng)LU節(jié)點(diǎn)有3個(gè)及以上的LA鄰居時(shí)，使用最大似然估計(jì)法計(jì)算LU節(jié)點(diǎn)的初始位置；② 當(dāng)LU節(jié)點(diǎn)有低于3個(gè)LA鄰居時(shí)，將距離LU節(jié)點(diǎn)最近的LA節(jié)點(diǎn)的位置作為其初始位置；③ 當(dāng)LU節(jié)點(diǎn)沒有LA鄰居時(shí)，將傳感器節(jié)點(diǎn)分布區(qū)域的中心作為LU節(jié)點(diǎn)的初始位置，這樣最大的初始定位誤差為區(qū)域?qū)蔷€的一半。

2.2.2Barzilai-Borwein梯度法

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

xk+1=xk-αk?f(xk) 。

(23)

可將上式寫為

xk+1=xk-Fk?f(xk) ，

(24)

其中，F(xiàn)k=αkI。利用擬牛頓法割線方程的性質(zhì)[14]，求解以下最小二乘問題：

(25)

可以得到步長

(26)

如果k=0，則通過回溯直線搜索法確定步長α0，設(shè)置參數(shù)μ=0.2，β=0.5，α0=1，若下式成立，則令α0=βα0，繼續(xù)循環(huán)，直到下式不成立：

fs(xk+α0Δxk)>fs(xk)+μα0?fs(xk)TΔxk。

(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：qk=-?fs(xk)；

(3) 計(jì)算步長：如果k=0，則通過回溯直線搜索法確定步長α0；否則通過式(27)計(jì)算步長αk；

(4) 更新子圖Gs中LU節(jié)點(diǎn)位置：xk+1=xk+αkqk；

2.3 子圖融合

在構(gòu)建圖模型時(shí)，將WSN構(gòu)成的無向圖G以LU節(jié)點(diǎn)為中心分解為n個(gè)部分重疊的子圖。如圖1所示，同一個(gè)LU節(jié)點(diǎn)會(huì)位于不同的子圖中。因此，對(duì)每個(gè)子圖優(yōu)化求解后，對(duì)于相同的LU節(jié)點(diǎn)會(huì)有不同的估計(jì)值。需要對(duì)子圖進(jìn)行融合，從而得到每LU節(jié)點(diǎn)的估計(jì)值。而且可能會(huì)出現(xiàn)某個(gè)子圖由于可用的信息較少，導(dǎo)致估計(jì)出的LU節(jié)點(diǎn)位置誤差較大的問題。子圖融合可以有效地降低這部分節(jié)點(diǎn)的誤差，從而提高整體WSN的定位精度。子圖融合公式如下：

(28)

經(jīng)過上述分析，分布式定位算法的整體流程如算法1所示。

算法1分布式定位算法。

準(zhǔn)備工作：將N個(gè)傳感器隨機(jī)部署在檢測(cè)區(qū)域內(nèi)，其中有m個(gè)LA節(jié)點(diǎn)，n個(gè)LU節(jié)點(diǎn)，通信半徑為R。以LU節(jié)點(diǎn)為中心，通信半徑內(nèi)與LU節(jié)點(diǎn)直接相連的節(jié)點(diǎn)為鄰居節(jié)點(diǎn)，構(gòu)成一個(gè)子圖。從而將WSN劃分為n個(gè)部分重疊的子圖。令t=0。

輸入：使用節(jié)2.2.1中采用的極大似然估計(jì)法及相關(guān)規(guī)則，對(duì)LU節(jié)點(diǎn)進(jìn)行粗略的初始定位，定位結(jié)果為p(t)。將其作為步驟(1)中進(jìn)行優(yōu)化求解的初始值；

(1) 采用節(jié)2.2.2的Barzilai-Borwein梯度法對(duì)劃分好的子圖進(jìn)行優(yōu)化求解；

(2) 采用節(jié)2.3提出的子圖融合的方法，對(duì)部分重疊的子圖進(jìn)行融合，得到第t+1次迭代的定位結(jié)果p(t+1)；

輸出：p(t+1)作為最終定位結(jié)果。

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

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

(29)

表1 實(shí)驗(yàn)參數(shù)的設(shè)置與說明

實(shí)驗(yàn)3為了研究文中算法在不同網(wǎng)絡(luò)規(guī)模和噪聲情況下的定位效果，本次實(shí)驗(yàn)節(jié)點(diǎn)分布區(qū)域?yàn)閇-0.5，0.5]2，改變節(jié)點(diǎn)總數(shù)N、通信半徑R、LA位置噪聲因子τ2進(jìn)行仿真，并與文獻(xiàn)[5，7-8]進(jìn)行對(duì)比。仿真參數(shù)設(shè)置和定位結(jié)果如表2所示?？梢钥闯觯谙嗤?guī)模的無線傳感器網(wǎng)絡(luò)中，對(duì)LA位置添加噪聲后，各算法的定位精度均會(huì)下降。在小規(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ò)中，并且有較高的定位精度。

圖2 不同錨節(jié)點(diǎn)數(shù)目下的平均定位誤差

表2 文中算法與文獻(xiàn)[5，7-8]算法在不同參數(shù)下實(shí)驗(yàn)結(jié)果對(duì)比

4 結(jié)束語

針對(duì)無線傳感器網(wǎng)絡(luò)定位精度較低、擴(kuò)展性不高問題，筆者提出了一種分布式定位算法。首先將整個(gè)無線傳感器網(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)有分布式定位算法相比，有更高的定位精度?？梢姽P者提出的算法具備一定的優(yōu)勢(shì)，可以為無線傳感器網(wǎng)絡(luò)的經(jīng)濟(jì)、高效、實(shí)用性發(fā)展提供可靠的技術(shù)支持，進(jìn)而促進(jìn)無線傳感器網(wǎng)絡(luò)在環(huán)境科學(xué)、醫(yī)療健康等多個(gè)領(lǐng)域的應(yīng)用。