基于蜂窩網(wǎng)絡(luò)拓?fù)涞臒o線傳感網(wǎng)定位算法

任秀麗，劉 瑩

(遼寧大學(xué) 信息學(xué)院，遼寧 沈陽 110036)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)的節(jié)點(diǎn)定位技術(shù)是其關(guān)鍵支撐技術(shù)之一[1-5]。目前，節(jié)點(diǎn)定位算法主要分為兩類：基于測(cè)距[6-10]和基于非測(cè)距[11-16]。

在基于非測(cè)距的定位算法中，運(yùn)用最廣泛的是DV-HOP算法，但其定位精度低，對(duì)此很多學(xué)者都提出過改進(jìn)方案。文獻(xiàn)[17]提出基于DV-Hop 測(cè)距修正的對(duì)數(shù)搜索(improved DV-Hop ranging-based logarithmic search，DH-RLS)定位算法，其估計(jì)跳距誤差后修正跳距值，過于依賴信標(biāo)節(jié)點(diǎn)，計(jì)算量大且耗能多。文獻(xiàn)[18]提出改進(jìn)的DV-Hop定位算法(improved DV-Hop localization algorithm，IDVH-LA)，對(duì)一跳距離加權(quán)校準(zhǔn)，依據(jù)跳距作用域計(jì)算距離。雖硬件開銷小，但能耗較高且計(jì)算誤差較大。文獻(xiàn)[19]提出全局跳數(shù)優(yōu)化與跳距誤差修正的DV-Hop 改進(jìn)算法(improved DV-Hop algorithm based on global hop count optimization and hop distance error correction，IDVH-HCHEC)，對(duì)跳數(shù)值協(xié)同優(yōu)化并修正平均跳距以提升精度，但仍不能改善DV-Hop算法因?yàn)榫W(wǎng)絡(luò)環(huán)路導(dǎo)致的較大誤差。

針對(duì)上述算法的不足，本文提出了基于蜂窩網(wǎng)絡(luò)拓?fù)涞亩ㄎ凰惴?location algorithm based on cellular network topology，LABCNT)。該算法僅需兩個(gè)信標(biāo)節(jié)點(diǎn)即可定位監(jiān)測(cè)區(qū)域內(nèi)所有節(jié)點(diǎn)的位置，解決了其它算法在信標(biāo)節(jié)點(diǎn)極少、未知節(jié)點(diǎn)過多的情況下定位效率低，甚至無法定位的問題。首先篩選網(wǎng)絡(luò)中全部節(jié)點(diǎn)，設(shè)計(jì)并構(gòu)造一個(gè)蜂巢網(wǎng)絡(luò)結(jié)構(gòu)模型，通過模型確定結(jié)構(gòu)上節(jié)點(diǎn)的位置，最后利用最小二乘法對(duì)域內(nèi)其它節(jié)點(diǎn)進(jìn)行定位。實(shí)驗(yàn)結(jié)果表明，該算法定位精度高，計(jì)算量小且對(duì)信標(biāo)節(jié)點(diǎn)數(shù)依賴性極小。

1 網(wǎng)絡(luò)模型

本文針對(duì)無線傳感網(wǎng)中信標(biāo)節(jié)點(diǎn)密度低、未知節(jié)點(diǎn)密度高的環(huán)境下進(jìn)行定位研究。網(wǎng)絡(luò)模型如下假設(shè)：①全部節(jié)點(diǎn)都具有相同的通信范圍，選取合適的通信半徑r作為全部節(jié)點(diǎn)的固定通信半徑；②每一個(gè)節(jié)點(diǎn)都有其唯一ID，以便將其記錄到結(jié)構(gòu)鏈表當(dāng)中；③節(jié)點(diǎn)間可以通過測(cè)距技術(shù)獲取距離信息，網(wǎng)絡(luò)測(cè)距技術(shù)采用接收信號(hào)強(qiáng)度指示(RSSI)；④本文所用的RSSI信號(hào)傳播模型為對(duì)數(shù)常態(tài)分布模型，如式(1)所示

(1)

其中：RSSI(d)是未知節(jié)點(diǎn)的接收功率；RSSI(d0)是參考距離d0點(diǎn)對(duì)應(yīng)的接收功率；d是未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的距離；d0是參考距離；α為與環(huán)境有關(guān)的路徑損耗指數(shù)，一般取默認(rèn)值；為表示標(biāo)準(zhǔn)差為σ的正態(tài)隨機(jī)變量。

2 LABCNT算法

LABCNT算法適用于信標(biāo)節(jié)點(diǎn)數(shù)量極少，且存在大量未知節(jié)點(diǎn)的環(huán)境。在不改變?cè)璂V-Hop算法理論的基礎(chǔ)上，引入RSSI技術(shù)，對(duì)算法執(zhí)行過程進(jìn)行了3個(gè)方面的改進(jìn)：一是在定位開始階段對(duì)跳距進(jìn)行規(guī)范，減少在定位后期的誤差積累；二是在定位過程中有向篩選出一些特征節(jié)點(diǎn)繼而搭建構(gòu)成一個(gè)相對(duì)有序的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，避免原DV-Hop算法因?yàn)榄h(huán)路和曲路導(dǎo)致的較大誤差；三是利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)域內(nèi)所有節(jié)點(diǎn)進(jìn)行最小二乘算法定位，減小原始算法中因迭代而產(chǎn)生的累積誤差。

LABCNT算法主要思想分為兩個(gè)階段：一是蜂巢搭建階段，二是馬蜂回巢階段。在蜂巢搭建階段，對(duì)網(wǎng)絡(luò)中全部節(jié)點(diǎn)進(jìn)行篩選，篩選完畢后，使用所有滿足特定要求的節(jié)點(diǎn)構(gòu)造出一個(gè)結(jié)構(gòu)模型，且在該模型中所有節(jié)點(diǎn)位置均為相對(duì)位置。模型搭建完成后，進(jìn)入第二階段，即馬蜂回巢階段。在馬蜂回巢階段要修正該模型中全部節(jié)點(diǎn)的相對(duì)位置，并通過蜂巢搭建階段所構(gòu)筑的網(wǎng)絡(luò)結(jié)構(gòu)將整個(gè)偵測(cè)區(qū)域劃分為若干個(gè)大小相等的三角形區(qū)域，最終通過計(jì)算獲取全部未知節(jié)點(diǎn)的準(zhǔn)確位置。

2.1 蜂巢搭建

蜂巢搭建階段分為4個(gè)步驟：選點(diǎn)、編號(hào)、劃域和定點(diǎn)。首先對(duì)網(wǎng)絡(luò)中全部節(jié)點(diǎn)進(jìn)行篩選，對(duì)選中的節(jié)點(diǎn)構(gòu)造蜂巢網(wǎng)絡(luò)拓?fù)淠Ｐ停⑵浒凑找?guī)定的方法進(jìn)行編號(hào)。最后，對(duì)拓?fù)渚W(wǎng)絡(luò)中全部節(jié)點(diǎn)進(jìn)行分區(qū)域處理，并對(duì)各區(qū)域內(nèi)節(jié)點(diǎn)位置進(jìn)行相對(duì)定位。

2.1.1 選點(diǎn)

定義1 節(jié)點(diǎn)的度。節(jié)點(diǎn)i的度是它的鄰居節(jié)點(diǎn)的個(gè)數(shù)，即與它相鄰的節(jié)點(diǎn)個(gè)數(shù)。

選點(diǎn)，即選取構(gòu)筑蜂窩網(wǎng)絡(luò)的特征節(jié)點(diǎn)。選點(diǎn)前，匯聚節(jié)點(diǎn)(Sink節(jié)點(diǎn))判斷網(wǎng)絡(luò)中各信標(biāo)節(jié)點(diǎn)的度，選取節(jié)點(diǎn)度最大的信標(biāo)節(jié)點(diǎn)作為起始節(jié)點(diǎn)，確保起始節(jié)點(diǎn)找到滿足要求的節(jié)點(diǎn)。特征節(jié)點(diǎn)的選取方法如下：以起始節(jié)點(diǎn)(信標(biāo)節(jié)點(diǎn))為中心，在半徑為r的圓形通信范圍內(nèi)，選擇最接近圓內(nèi)接正六邊形的6個(gè)節(jié)點(diǎn)，即任意兩個(gè)相鄰節(jié)點(diǎn)間距離盡可能接近固定通信半徑r。隨后再分別以這6個(gè)被選中的節(jié)點(diǎn)為中心，用同種方式再次對(duì)這些節(jié)點(diǎn)進(jìn)行特征節(jié)點(diǎn)的選取，以此方法進(jìn)行類推拓?fù)?，?gòu)筑蜂巢拓?fù)浣Y(jié)構(gòu)。若在構(gòu)造拓?fù)浣Y(jié)構(gòu)的過程中，出現(xiàn)特殊情況，即找不到足夠多滿足條件的節(jié)點(diǎn)，則把缺少節(jié)點(diǎn)的六邊形頂點(diǎn)設(shè)為虛擬節(jié)點(diǎn)，不影響其它節(jié)點(diǎn)拓?fù)洹?/p>

圖1為監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)構(gòu)筑蜂巢網(wǎng)絡(luò)結(jié)構(gòu)的示意圖，其中圖1(a)為監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)的分布。在監(jiān)測(cè)區(qū)域內(nèi)選擇某一信標(biāo)節(jié)點(diǎn)按選點(diǎn)步驟進(jìn)行拓?fù)?，得到一個(gè)由正六邊形拼接的內(nèi)外多層的蜂巢網(wǎng)絡(luò)結(jié)構(gòu)，如圖1(b)所示。

圖1 構(gòu)筑蜂巢網(wǎng)絡(luò)結(jié)構(gòu)

2.1.2 編號(hào)

定義2 孤點(diǎn)。在各層正六邊形網(wǎng)絡(luò)結(jié)構(gòu)中，各邊兩個(gè)端點(diǎn)位置的節(jié)點(diǎn)稱為孤點(diǎn)，起始信標(biāo)節(jié)點(diǎn)也作為孤點(diǎn)，如圖2(a)所示。

定義3 交點(diǎn)。在各層正六邊形網(wǎng)絡(luò)結(jié)構(gòu)中，除孤點(diǎn)外的節(jié)點(diǎn)稱為交點(diǎn)。

定義4 子節(jié)點(diǎn)。由節(jié)點(diǎn)拓?fù)涑龅耐鈱庸?jié)點(diǎn)為其子節(jié)點(diǎn)。

定義5 順序位孤點(diǎn)。只被孤點(diǎn)拓?fù)涑龅淖訉庸曼c(diǎn)為其順序位孤點(diǎn)。

將經(jīng)過選點(diǎn)過程得到的蜂窩網(wǎng)絡(luò)結(jié)構(gòu)圖抽象出一個(gè)蜂窩層次結(jié)構(gòu)圖，如圖2(b)所示。各層節(jié)點(diǎn)的個(gè)數(shù)為其層號(hào)的6倍。LABCNT采用層序坐標(biāo)表示法對(duì)拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)中的全部節(jié)點(diǎn)位置進(jìn)行描述，即通過節(jié)點(diǎn)在蜂巢網(wǎng)絡(luò)結(jié)構(gòu)中所屬的層號(hào)與層內(nèi)序號(hào)表示該節(jié)點(diǎn)的位置。

圖2 蜂巢層次結(jié)構(gòu)

層序坐標(biāo)表示法如下：

(1)層號(hào)編號(hào)規(guī)則：從起始信標(biāo)節(jié)點(diǎn)開始，由內(nèi)向外依次編號(hào)為0，1，2，3，4…n；

(2)層內(nèi)序號(hào)編號(hào)規(guī)則：以第一層任意孤點(diǎn)為起點(diǎn)，逆時(shí)針依次編號(hào)為0，1，2，3，4，5。其后的每一層均以第一層0號(hào)孤點(diǎn)在該層的順序位孤點(diǎn)為該層的編號(hào)起點(diǎn)，逆時(shí)針方向?qū)?jié)點(diǎn)進(jìn)行編號(hào)。層內(nèi)序號(hào)示意圖，如圖3所示。

圖3 層內(nèi)序號(hào)

根據(jù)層序坐標(biāo)表示法，網(wǎng)絡(luò)中任意節(jié)點(diǎn)表示為：Li(n,x)。 其中，i是節(jié)點(diǎn)的ID號(hào)，n是該節(jié)點(diǎn)i在拓?fù)浣Y(jié)構(gòu)中的層號(hào)；x是節(jié)點(diǎn)i在此層的序號(hào)。

節(jié)點(diǎn)編號(hào)示意圖，如圖4所示。以第一層到第三層的拓?fù)浣Y(jié)構(gòu)為例，Li(1,0) 單獨(dú)發(fā)現(xiàn)的節(jié)點(diǎn)為Li(2,0)；Li(2,0) 單獨(dú)發(fā)現(xiàn)的節(jié)點(diǎn)為Li(3,0)； 即每層0號(hào)節(jié)點(diǎn)單獨(dú)發(fā)現(xiàn)下層0號(hào)節(jié)點(diǎn)。Li(1,1) 單獨(dú)發(fā)現(xiàn)的節(jié)點(diǎn)為Li(2,2)；Li(2,2) 單獨(dú)發(fā)現(xiàn)的節(jié)點(diǎn)為Li(3,3)；Li(1,2) 單獨(dú)發(fā)現(xiàn)Li(2,4)；Li(2,4) 單獨(dú)發(fā)現(xiàn)Li(3,6)； 即每層孤點(diǎn)單獨(dú)發(fā)現(xiàn)的節(jié)點(diǎn)下層順序位孤點(diǎn)。Li(1,0) 與Li(1,1) 共同發(fā)現(xiàn)的節(jié)點(diǎn)為Li(2,1)；Li(2,0) 和Li(2,1) 共同發(fā)現(xiàn)的節(jié)點(diǎn)為Li(3,1)， 即0號(hào)位和1號(hào)位同時(shí)發(fā)現(xiàn)的節(jié)點(diǎn)為下一層1號(hào)節(jié)點(diǎn)。Li(2,1) 與Li(2,2) 同時(shí)發(fā)現(xiàn)Li(3,2)， 即除第一層外，各層1號(hào)位和2號(hào)位同時(shí)發(fā)現(xiàn)的節(jié)點(diǎn)為下一層2號(hào)節(jié)點(diǎn)。此外，Li(1,0) 共發(fā)現(xiàn)3個(gè)節(jié)點(diǎn)，分別為Li(2,11)，Li(2,0)，Li(2,1)；Li(2,0) 共發(fā)現(xiàn)3個(gè)節(jié)點(diǎn)，分別為Li(3,17)，Li(3,0)，Li(3,1)； 即孤點(diǎn)發(fā)現(xiàn)其子層的順序位孤點(diǎn)與子層兩個(gè)交點(diǎn)。Li(2,11) 共發(fā)現(xiàn)兩個(gè)節(jié)點(diǎn)，分別為Li(3,16) 與Li(3,17)；Li(2,1) 共發(fā)現(xiàn)兩個(gè)節(jié)點(diǎn)，分別為Li(3,1) 與Li(3,2)； 即交點(diǎn)發(fā)現(xiàn)其兩個(gè)子層交點(diǎn)。

圖4 節(jié)點(diǎn)編號(hào)

2.1.3 劃域

將節(jié)點(diǎn)編號(hào)后的網(wǎng)絡(luò)進(jìn)行劃域，如圖5所示。網(wǎng)絡(luò)劃分為6個(gè)區(qū)域，分別標(biāo)記為A1、A2、A3、A4、A5、A6。對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)，確定其所屬區(qū)域。將起始信標(biāo)節(jié)點(diǎn)作為極點(diǎn)；從起始信標(biāo)節(jié)點(diǎn)出發(fā)，向外依次連接各層0號(hào)位孤點(diǎn)后形成的射線作為初始假定極軸，以逆時(shí)針為正方向，則第一層各孤點(diǎn)及其順序位孤點(diǎn)形成的射線方向分別為：0，π/3，2π/3，π，4π/3，5π/3。網(wǎng)絡(luò)劃分的6個(gè)區(qū)域分別為：A1[0,π/3)，A2[π/3,2π/3)，A3[2π/3,π)，A4[π,4π/3)，A5[4π/3,5π/3)，A6[5π/3,2π)。

圖5 網(wǎng)絡(luò)區(qū)域劃分

2.1.4 定點(diǎn)

在該階段，利用節(jié)點(diǎn)的編號(hào)以及所屬區(qū)域，計(jì)算出它在地圖上的相對(duì)坐標(biāo)，相對(duì)坐標(biāo)采用極坐標(biāo)表示法，即Pi(ρ,θ)。 其中，i表示節(jié)點(diǎn)ID號(hào)，ρ為極徑，即節(jié)點(diǎn)距起始信標(biāo)節(jié)點(diǎn)的距離；θ為相對(duì)角度，即極徑與其初始假定極軸之間的夾角(極角)。

圖6所示為節(jié)點(diǎn)定點(diǎn)后的示意圖，圖中節(jié)點(diǎn)可分為兩類：處于各區(qū)域邊界射線上的點(diǎn)與處于各區(qū)域內(nèi)的點(diǎn)。孤點(diǎn)處于各區(qū)域邊界射線上；交點(diǎn)處于各劃分區(qū)域內(nèi)。

圖6 節(jié)點(diǎn)定點(diǎn)

對(duì)于不同類別的節(jié)點(diǎn)，位置的計(jì)算各有不同。任意節(jié)點(diǎn)的類別通過層內(nèi)序號(hào)x是否是層n的整數(shù)倍判斷，若層內(nèi)序號(hào)x是層n的整數(shù)倍，則節(jié)點(diǎn)i為孤點(diǎn)；否則節(jié)點(diǎn)i為交點(diǎn)。

不同類型的節(jié)點(diǎn)到起始信標(biāo)節(jié)點(diǎn)的距離(極徑)ρ，極徑與其初始假定極軸之間的夾角θ(相對(duì)角度)的計(jì)算方法如下：

(1)孤點(diǎn)

ρ=n×r

(2)

(3)

其中，n為節(jié)點(diǎn)所在層數(shù)；r為蜂巢節(jié)點(diǎn)的固定通訊半徑。

(2)交點(diǎn)

對(duì)于交點(diǎn)位置的計(jì)算，首先判斷該節(jié)點(diǎn)所屬的區(qū)域，然后推算其所屬區(qū)域內(nèi)起始孤點(diǎn)序號(hào)，最后在區(qū)域內(nèi)根據(jù)勾股定理，計(jì)算它與起始信標(biāo)節(jié)點(diǎn)的空間距離ρ以及極徑與初始假定極軸的夾角θ(相對(duì)角度)

(4)

(5)

(6)

其中，n為節(jié)點(diǎn)所在層數(shù)；r為蜂巢節(jié)點(diǎn)的固定通訊半徑；x為節(jié)點(diǎn)的層內(nèi)序號(hào)；m表示該點(diǎn)所屬區(qū)域的起始孤點(diǎn)序號(hào)。

2.2 馬蜂回巢

蜂窩拓?fù)浣Y(jié)構(gòu)搭建完成后，運(yùn)用假定的極坐標(biāo)系計(jì)算出各個(gè)未知節(jié)點(diǎn)的相對(duì)位置。但由于是相對(duì)坐標(biāo)，在實(shí)際定位中節(jié)點(diǎn)的具體位置并不能確定，因此，通過蜂巢網(wǎng)絡(luò)結(jié)構(gòu)中第二個(gè)信標(biāo)節(jié)點(diǎn)，即馬蜂節(jié)點(diǎn)來確定網(wǎng)絡(luò)中所有節(jié)點(diǎn)的絕對(duì)坐標(biāo)。

馬蜂回巢階段分為坐標(biāo)校準(zhǔn)與全局定位兩個(gè)部分，坐標(biāo)校準(zhǔn)是根據(jù)蜂巢網(wǎng)絡(luò)結(jié)構(gòu)中的馬蜂節(jié)點(diǎn)進(jìn)行坐標(biāo)更正；全局定位是將已經(jīng)確定位置的節(jié)點(diǎn)升級(jí)為協(xié)作節(jié)點(diǎn)，輔助其它未確定位置的節(jié)點(diǎn)定位。

2.2.1 坐標(biāo)校準(zhǔn)

坐標(biāo)校準(zhǔn)是確定真實(shí)的極軸，并調(diào)整拓?fù)浣Y(jié)構(gòu)上各節(jié)點(diǎn)的角度的過程，即將整個(gè)拓?fù)渚W(wǎng)絡(luò)所在的極坐標(biāo)系進(jìn)行調(diào)整。將原零度線方向(初始假定極軸)替換為兩信標(biāo)節(jié)點(diǎn)的連線方向，即將兩信標(biāo)節(jié)點(diǎn)的連線方向作為新極軸。此時(shí)，各個(gè)節(jié)點(diǎn)的距離并未發(fā)生變化，但是各個(gè)節(jié)點(diǎn)的角度要做出相應(yīng)的調(diào)整。坐標(biāo)校準(zhǔn)后的馬蜂節(jié)點(diǎn)與起始信標(biāo)節(jié)點(diǎn)將拓?fù)渚W(wǎng)絡(luò)中全部節(jié)點(diǎn)定格在地圖上，如圖7所示。初始假定極軸方向?yàn)?°方向，A點(diǎn)為馬蜂節(jié)點(diǎn)?，F(xiàn)將A點(diǎn)所在角度設(shè)為0°方向，則原坐標(biāo)中B點(diǎn)位置調(diào)整到B′點(diǎn)，即B點(diǎn)相對(duì)角度θ，調(diào)整為現(xiàn)坐標(biāo)軸B′點(diǎn)的相對(duì)角度φ。節(jié)點(diǎn)坐標(biāo)校準(zhǔn)的計(jì)算方法如下所示：

圖7 校準(zhǔn)節(jié)點(diǎn)

設(shè)馬蜂節(jié)點(diǎn)的相對(duì)角度為θt，節(jié)點(diǎn)修正后的角度為φ，則節(jié)點(diǎn)的修正坐標(biāo)為Pi(ρ,φ)

(7)

2.2.2 全局定位

通過執(zhí)行上述蜂巢搭建以及坐標(biāo)校準(zhǔn)步驟后，對(duì)各層上六邊形節(jié)點(diǎn)已完成定位。對(duì)于其它未在拓?fù)浣Y(jié)構(gòu)上的節(jié)點(diǎn)采用區(qū)域化處理，即將需要被偵測(cè)區(qū)域的各正六邊形分割為若干個(gè)等邊三角形，如圖6所示。將蜂窩拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)中已經(jīng)確定位置的節(jié)點(diǎn)升級(jí)為協(xié)作節(jié)點(diǎn)，根據(jù)最小二乘法對(duì)各區(qū)域內(nèi)的未知節(jié)進(jìn)行定位。至此，監(jiān)測(cè)區(qū)域內(nèi)所有節(jié)點(diǎn)的位置均可以確定。

2.3 LABCNT算法的實(shí)現(xiàn)步驟

LABCNT算法分為兩個(gè)階段：一是蜂巢搭建階段，二是馬蜂回巢階段。算法的具體實(shí)現(xiàn)過程如下：

步驟1 初始化網(wǎng)絡(luò)。Sink節(jié)點(diǎn)廣播初始化消息，監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)確定自身位置信息及自身的度，未知節(jié)點(diǎn)將自身位置信息設(shè)為NULL。各節(jié)點(diǎn)向Sink節(jié)點(diǎn)發(fā)送位置信息以及自身的度。

步驟2 選點(diǎn)拓?fù)?。Sink節(jié)點(diǎn)接收到各節(jié)點(diǎn)的消息后，選取度最大的信標(biāo)節(jié)點(diǎn)作為起始信標(biāo)節(jié)點(diǎn)，起始信標(biāo)節(jié)點(diǎn)根據(jù)2.1.1節(jié)選點(diǎn)要求進(jìn)行網(wǎng)絡(luò)拓?fù)溥x點(diǎn)。

步驟3 編號(hào)劃域。拓?fù)浣Y(jié)構(gòu)建立后，對(duì)拓?fù)浣Y(jié)構(gòu)中的節(jié)點(diǎn)采用層序坐標(biāo)法編號(hào)并劃分節(jié)點(diǎn)所屬區(qū)域。

步驟4 計(jì)算相對(duì)位置。根據(jù)節(jié)點(diǎn)的類別對(duì)拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn)計(jì)算其相對(duì)位置。

步驟5 計(jì)算絕對(duì)位置。通過2.2節(jié)馬蜂回巢，運(yùn)用拓?fù)渚W(wǎng)絡(luò)中第二個(gè)信標(biāo)節(jié)點(diǎn)，將拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn)完全定格在地圖上。利用坐標(biāo)校準(zhǔn)修正相對(duì)坐標(biāo)，得出絕對(duì)坐標(biāo)。

步驟6 全局定位。將蜂窩拓?fù)渚W(wǎng)絡(luò)中已經(jīng)確定位置的節(jié)點(diǎn)升級(jí)為協(xié)作節(jié)點(diǎn)，區(qū)域化處理后，確定各區(qū)域內(nèi)其它未知節(jié)點(diǎn)坐標(biāo)。

3 性能評(píng)估與分析

為了評(píng)估本文提出的LABCNT算法的性能，使用NS-2仿真環(huán)境，對(duì)本文的LABCNT算法同DH-RLS算法、IDVH-LA算法、IDVH-HCHEC算法進(jìn)行比較。將節(jié)點(diǎn)隨機(jī)部署在100m×100m的監(jiān)測(cè)區(qū)域內(nèi)，假設(shè)所有節(jié)點(diǎn)都具有相同的通信半徑，節(jié)點(diǎn)通過自組織形成一個(gè)無線傳感器網(wǎng)絡(luò)。仿真參數(shù)見表1。

表1 仿真參數(shù)

本文從三方面來驗(yàn)證各算法的性能。節(jié)點(diǎn)定位誤差error如式(8)所示

(8)

其中，n為節(jié)點(diǎn)總數(shù)；m為信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)； (x′i,y′i) 為未知節(jié)點(diǎn)定位后的估計(jì)坐標(biāo)； (xi,yi) 為未知節(jié)點(diǎn)的實(shí)際坐標(biāo)位置。

從圖8可知，隨著信標(biāo)節(jié)點(diǎn)數(shù)量的逐漸增加，節(jié)點(diǎn)的定位誤差逐漸降低；LABCNT算法的定位精度明顯高于其它3種算法。LABCNT算法使用兩個(gè)信標(biāo)節(jié)點(diǎn)定位，對(duì)信標(biāo)節(jié)點(diǎn)的數(shù)量依賴性較小，在信標(biāo)節(jié)點(diǎn)數(shù)量較少時(shí)定位精度較高，且在定位開始階段規(guī)范跳距，減少在定位后期的誤差積累。DH-RLS算法過于依賴信標(biāo)節(jié)點(diǎn)數(shù)量，信標(biāo)節(jié)點(diǎn)數(shù)量少時(shí)，誤差過大。IDVH-LA和IDVH-HCHEC算法注重對(duì)信標(biāo)節(jié)點(diǎn)平均跳距的修正，依賴信標(biāo)節(jié)點(diǎn)的分布的均勻程度，信標(biāo)節(jié)點(diǎn)比例過小時(shí)，網(wǎng)絡(luò)區(qū)域信標(biāo)節(jié)點(diǎn)可能分布不夠均勻，誤差較大。

圖8 信標(biāo)節(jié)點(diǎn)數(shù)量與定位誤差之間的關(guān)系

如圖9可知，監(jiān)測(cè)區(qū)域內(nèi)4種算法的定位精度隨著節(jié)點(diǎn)總數(shù)的增加而提升，最終定位精度均趨于穩(wěn)定，LABCNT算法的定位精度明顯高于其它3種算法。LABCNT算法篩選出的特征節(jié)點(diǎn)構(gòu)建而成的蜂窩拓?fù)浣Y(jié)構(gòu)，限制了拓?fù)浣Y(jié)構(gòu)上兩個(gè)傳感器節(jié)點(diǎn)之間的距離，減少了由于實(shí)際跳距不均等而引起的累計(jì)定位誤差，也避免DV-Hop算法因?yàn)榄h(huán)路和曲路導(dǎo)致的較大誤差。DH-RLS算法采用搜索定位算法進(jìn)行后期處理，節(jié)點(diǎn)總數(shù)增加而收斂程度較弱，定位誤差較高。IDVH-LA算法對(duì)信標(biāo)節(jié)點(diǎn)的平均跳距進(jìn)行修正，但節(jié)點(diǎn)增多導(dǎo)致跳數(shù)增加，產(chǎn)生了大量的累計(jì)誤差。IDVH-HCHEC算法雖然改進(jìn)了跳距和跳數(shù)，但由節(jié)點(diǎn)增多導(dǎo)至產(chǎn)生的環(huán)路結(jié)構(gòu)不可避免，因此誤差率較高。

圖9 網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)與定位誤差之間的關(guān)系

如圖10可知，4種算法的定位精度隨通信半徑的增大而提升。此次實(shí)驗(yàn)參數(shù)設(shè)置為節(jié)點(diǎn)總數(shù)130個(gè)，信標(biāo)節(jié)點(diǎn)密度取8%。節(jié)點(diǎn)半徑增大，各節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)增多，提升了網(wǎng)絡(luò)的連通性，因此各算法定位精度提升。LABCNT算法對(duì)信標(biāo)節(jié)點(diǎn)的依賴性較小，首先確定了蜂窩拓?fù)渚W(wǎng)絡(luò)中的未知節(jié)點(diǎn)位置，然后利用RSSI技術(shù)與拓?fù)浣Y(jié)構(gòu)對(duì)域內(nèi)全部節(jié)點(diǎn)進(jìn)行區(qū)域化的最小二乘法定位，避免了DV-Hop算法中因迭代而產(chǎn)生的冗余誤差。DH-RLS算法依賴信標(biāo)節(jié)點(diǎn)，隨著半徑增大，質(zhì)心定位算法的定位誤差增大；IDVH-LA算法雖然優(yōu)化了平均跳距及其作用域，但忽略了計(jì)算所產(chǎn)生的累計(jì)誤差，節(jié)點(diǎn)通信半徑增加，累積誤差隨之增加；IDVH-HCHEC算法大量使用未知節(jié)點(diǎn)的信息，節(jié)點(diǎn)間半徑增大，更多未知位置的節(jié)點(diǎn)參與定位，使得算法誤差率有所上升。

圖10 節(jié)點(diǎn)通信半徑與定位誤差之間的關(guān)系

4 結(jié)束語

本文針對(duì)傳統(tǒng)定位算法存在的過于依賴信標(biāo)節(jié)點(diǎn)個(gè)數(shù)且定位精度低的缺陷，提出了基于蜂窩網(wǎng)絡(luò)拓?fù)涞臒o線傳感網(wǎng)定位算法(LABCNT)。該算法通過對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的有向篩選，利用選中的節(jié)點(diǎn)構(gòu)造蜂巢網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，得到節(jié)點(diǎn)的相對(duì)位置；利用拓?fù)浣Y(jié)構(gòu)中的第二個(gè)信標(biāo)節(jié)點(diǎn)確定網(wǎng)絡(luò)中節(jié)點(diǎn)的絕對(duì)位置，并將節(jié)點(diǎn)升級(jí)為協(xié)作節(jié)點(diǎn)；利用協(xié)作節(jié)點(diǎn)采用最小二乘法對(duì)各域內(nèi)所有節(jié)點(diǎn)進(jìn)行定位。仿真結(jié)果表明，本文提出的LABCNT算法與DH-RLS算法、IDVH-LA算法、IDVH-HCHEC算法相比，使用較少的信標(biāo)節(jié)點(diǎn)即可達(dá)到較高的定位精度，定位過程中的能量消耗較小，延長了整個(gè)網(wǎng)絡(luò)的生存周期。