改進(jìn)的無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法

胡必玲,仝 鈺, 郭玉堂

(合肥師范學(xué)院 計(jì)算機(jī)學(xué)院，安徽 合肥 236032)

作為一種智能信息采集系統(tǒng)，傳感器網(wǎng)絡(luò)應(yīng)用在許多領(lǐng)域，而提供事件發(fā)生的位置對(duì)于大部分應(yīng)用來說都是系統(tǒng)必須滿足的一項(xiàng)服務(wù).傳感器網(wǎng)絡(luò)中事件發(fā)生的位置通常確定為檢測(cè)到事件的傳感器節(jié)點(diǎn)的位置.因此對(duì)傳感器節(jié)點(diǎn)進(jìn)行定位成為傳感網(wǎng)應(yīng)用中的基本問題[1].

無線傳感器網(wǎng)絡(luò)中的定位技術(shù)一般分為基于測(cè)距的定位和無需測(cè)距的定位兩種.基于測(cè)距的定位通常需要對(duì)節(jié)點(diǎn)之間的角度數(shù)據(jù)或者距離信息進(jìn)行測(cè)量，如接收信號(hào)強(qiáng)度(RSSI)[2]、信號(hào)傳播時(shí)間(TOA、TDOA、RTOF)[3]等.此種定位算法一般能獲得比較高的定位準(zhǔn)確度，但定位過程中節(jié)點(diǎn)能量消耗較大，同時(shí)對(duì)網(wǎng)絡(luò)的硬件設(shè)備要求較高，會(huì)增加網(wǎng)絡(luò)計(jì)算量和通信成本.無需測(cè)距的定位一般基于節(jié)點(diǎn)間跳數(shù)信息、網(wǎng)絡(luò)連通情況等實(shí)現(xiàn)節(jié)點(diǎn)自身定位，主要有質(zhì)心定位算法[4]、DV-HOP 定位算法[5]、MDS_MAP[6]等.相比基于測(cè)距的定位，該類算法定位精度較低，但是由于不需要對(duì)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的距離或者角度進(jìn)行精確計(jì)算，降低了定位過程中節(jié)點(diǎn)能量的消耗和網(wǎng)絡(luò)的硬件設(shè)備要求，減少了網(wǎng)絡(luò)的計(jì)算量和通信成本，因而在實(shí)際應(yīng)用中比較廣泛.

本文針對(duì)傳統(tǒng)質(zhì)心定位算法中由于錨節(jié)點(diǎn)密度分布不均而引起的定位誤差，提出了一種結(jié)合三角形內(nèi)點(diǎn)測(cè)試和未知節(jié)點(diǎn)優(yōu)化的質(zhì)心定位算法.將所提出的算法與質(zhì)心定位算法[7]、基于RSSI的加權(quán)質(zhì)心定位算法[13]、增強(qiáng)的質(zhì)心定位算法[14]進(jìn)行對(duì)比，從而證明所提出算法的優(yōu)勢(shì).

1 質(zhì)心定位算法

在質(zhì)心定位算法中網(wǎng)絡(luò)的錨節(jié)點(diǎn)會(huì)向通信范圍內(nèi)的鄰居節(jié)點(diǎn)周期性廣播信標(biāo)信號(hào)，其中包含自身位置信息和ID.未知節(jié)點(diǎn)根據(jù)一段時(shí)間內(nèi)偵聽到的來自錨節(jié)點(diǎn)的信標(biāo)信號(hào)數(shù)量判斷是否與此錨節(jié)點(diǎn)連通，并將所有和其連通的錨節(jié)點(diǎn)構(gòu)成的多邊形幾何質(zhì)心確定為自身位置.

假設(shè)與未知節(jié)點(diǎn)U相連通的錨節(jié)點(diǎn)有M1,M2,…,Mk,其坐標(biāo)為(Xm1,Ym1), (Xm2,Ym2),…, (Xmk,Ymk)，未知節(jié)點(diǎn)的實(shí)際位置為(X,Y),其對(duì)自身的估計(jì)位置(Xest,Yest)，R為通信半徑，則

Xest=(Xm1+Xm2+…+Xmk)/k，
Yest=(Ym1+Ym2+…+Ymk)/k.

(1)

定位誤差率為E,其計(jì)算公式如下：

(2)

質(zhì)心定位算法的特點(diǎn)是簡(jiǎn)單、計(jì)算量小，其計(jì)算過程完全依據(jù)網(wǎng)絡(luò)的連通性，在錨節(jié)點(diǎn)分布均勻的情況下，會(huì)獲得比較滿意的仿真定位精度.但通常情況下錨節(jié)點(diǎn)分布較為隨機(jī)，質(zhì)心定位算法的定位結(jié)果會(huì)呈現(xiàn)較大誤差.

2 相關(guān)改進(jìn)工作

針對(duì)質(zhì)心定位準(zhǔn)確度低的問題，目前已有相關(guān)改進(jìn)工作.文獻(xiàn)[7]考慮到錨節(jié)點(diǎn)距離對(duì)節(jié)點(diǎn)定位的影響而引入接收信號(hào)強(qiáng)度對(duì)質(zhì)心的位置進(jìn)行加權(quán)計(jì)算；文獻(xiàn)[8]利用質(zhì)心定位算法獲得未知節(jié)點(diǎn)估計(jì)位置后，又將未知節(jié)點(diǎn)通信范圍內(nèi)的所有其它未知節(jié)點(diǎn)的估計(jì)位置納入考慮,得到首次估計(jì)位置和自身位置求和取平均值，作為自身最終的估計(jì)位置；文獻(xiàn)[9]以初始連通信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的地理位置關(guān)系確定算法的迭代收斂條件, 然后通過N個(gè)連通信標(biāo)節(jié)點(diǎn)的坐標(biāo)及其與未知節(jié)點(diǎn)間的接收信號(hào)強(qiáng)度計(jì)算當(dāng)前連通信標(biāo)節(jié)點(diǎn)所圍成的區(qū)域質(zhì)心的坐標(biāo)及其與未知節(jié)點(diǎn)間的距離,并用計(jì)算得到的質(zhì)心節(jié)點(diǎn)替代與未知節(jié)點(diǎn)距離最遠(yuǎn)的連通信標(biāo)節(jié)點(diǎn),縮小未知節(jié)點(diǎn)的所在區(qū)域,同時(shí)進(jìn)行多次迭代以此提高節(jié)點(diǎn)定位精度;文獻(xiàn)[10]應(yīng)用人工魚群算法對(duì)質(zhì)心定位進(jìn)行優(yōu)化，將參考節(jié)點(diǎn)的位置和信號(hào)接收強(qiáng)度計(jì)算出的距離和作為適應(yīng)度函數(shù),雖然提升了定位準(zhǔn)確性,但是增加了計(jì)算量；文獻(xiàn)[11]基于RSSI測(cè)距技術(shù)計(jì)算傳感器各節(jié)點(diǎn)之間的距離，然后構(gòu)建以未知節(jié)點(diǎn)坐標(biāo)為參數(shù)的數(shù)學(xué)模型，模型的建立以距離未知節(jié)點(diǎn)最近的3個(gè)錨節(jié)點(diǎn)和已定位節(jié)點(diǎn)為基礎(chǔ)，求解時(shí)在PSO算法的基礎(chǔ)上利用混沌優(yōu)化思想避免搜索過程陷入局部極小，結(jié)合雞群算法進(jìn)一步優(yōu)化.

3 優(yōu)化的質(zhì)心定位算法

3.1 算法基本思想

質(zhì)心定位算法中如果未知節(jié)點(diǎn)通信范圍內(nèi)存在的錨節(jié)點(diǎn)個(gè)數(shù)較少或分布不均，則未知節(jié)點(diǎn)不位于由錨節(jié)點(diǎn)構(gòu)成的幾何圖形范圍之內(nèi)會(huì)導(dǎo)致定位效果偏差較大.為提升錨節(jié)點(diǎn)隨機(jī)分布情況下的定位精度，提出了一種結(jié)合三角形內(nèi)點(diǎn)測(cè)試(PIT)和通信范圍內(nèi)已定位未知節(jié)點(diǎn)的優(yōu)化質(zhì)心定位算法，如圖1和圖2所示.

圖1 優(yōu)化的質(zhì)心定位算法定位圖例(1)

圖2 優(yōu)化的質(zhì)心定位算法定位圖例(2)

優(yōu)化質(zhì)心定位算法的核心思想是:未知節(jié)點(diǎn)首先獲取自己通信范圍內(nèi)的錨節(jié)點(diǎn)數(shù)量，若不低于3個(gè)，則任選3個(gè)錨節(jié)點(diǎn)構(gòu)成三角形，并進(jìn)一步判定自己是否位于此三角形內(nèi)；如果未知節(jié)點(diǎn)處于n個(gè)由其通信范圍內(nèi)的錨節(jié)點(diǎn)組成的三角形范圍之內(nèi)，則用每個(gè)三角形錨節(jié)點(diǎn)的信號(hào)強(qiáng)度進(jìn)行加權(quán)得出每個(gè)三角形質(zhì)心，取所有質(zhì)心的平均值作為自己的位置;如果未知節(jié)點(diǎn)獲取到的通信范圍內(nèi)錨節(jié)點(diǎn)的個(gè)數(shù)小于3個(gè)或不處于任一錨節(jié)點(diǎn)所組成三角形范圍內(nèi)，則增加其通信范圍內(nèi)已經(jīng)定位的未知節(jié)點(diǎn)作為新的錨節(jié)點(diǎn)，繼續(xù)判定其位于哪幾個(gè)三角形范圍內(nèi)，取三角形質(zhì)心的平均值為其位置.如果未知節(jié)點(diǎn)不處于任一由其通信范圍內(nèi)的錨節(jié)點(diǎn)和已定位的未知節(jié)點(diǎn)組成的三角形范圍之內(nèi)，則取其通信范圍內(nèi)的所有錨節(jié)點(diǎn)和已經(jīng)定位的未知節(jié)點(diǎn)坐標(biāo)的平均值作為其位置；如果引入已定位未知節(jié)點(diǎn)(新的錨節(jié)點(diǎn))后，周圍的錨節(jié)點(diǎn)個(gè)數(shù)仍小于3個(gè)，則該未知節(jié)點(diǎn)不能被定位.

圖1中U1為待定位的未知節(jié)點(diǎn),M1、M2、M3和M4為在U1通信范圍內(nèi)的錨節(jié)點(diǎn),依據(jù)質(zhì)心定位算法U1對(duì)自身的估計(jì)位置為M1、M2、M3和M4的幾何質(zhì)心，即E1點(diǎn).在優(yōu)化的質(zhì)心定位算法中，U1首先確定自己處于由三角形M1M3M4和三角形M2M3M4范圍之內(nèi)，然后取兩個(gè)三角形的加權(quán)質(zhì)心平均值E點(diǎn)作為其估計(jì)位置.從圖中可以看出采用優(yōu)化的質(zhì)心定位算法得到的位置E比原質(zhì)心算法更接近真實(shí)位置.

圖2為未知節(jié)點(diǎn)不處于其通信范圍內(nèi)的錨節(jié)點(diǎn)所組成的任一三角形范圍之中.同樣，U1為待定位的未知節(jié)點(diǎn),M1、M2和M3為在U1通信范圍內(nèi)的錨節(jié)點(diǎn),依據(jù)質(zhì)心定位算法定位U1的估計(jì)位置為M1、M2和M3的幾何質(zhì)心，即E1.利用優(yōu)化的質(zhì)心定位算法，U1判定自己并不屬于其通信范圍內(nèi)的3個(gè)錨節(jié)點(diǎn)組成的三角形范圍之內(nèi)，于是和其通信范圍內(nèi)的另外兩個(gè)未知節(jié)點(diǎn)交換信息，得到估計(jì)位置E2和E3，可以判斷出自己處于三角形M1M3E2、M1E2E3、M2M3E2、M2E2E3范圍之內(nèi)，取4個(gè)三角形的質(zhì)心平均值點(diǎn)E作為自己的估計(jì)位置.從圖2中可以看出采用優(yōu)化的質(zhì)心定位算法得到的位置E更接近真實(shí)位置.

3.2 算法流程

步驟1：每個(gè)未知節(jié)點(diǎn)搜索自己通信范圍內(nèi)的錨節(jié)點(diǎn)，判斷節(jié)點(diǎn)數(shù)量是否大于3，如果大于3轉(zhuǎn)步驟2，否則轉(zhuǎn)步驟4；

步驟2：任意組合3個(gè)錨節(jié)點(diǎn)形成若干個(gè)三角形，判斷未知節(jié)點(diǎn)是否至少處于一個(gè)三角形中，并統(tǒng)計(jì)個(gè)數(shù)，如果是，轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟4；

步驟3：根據(jù)接收信號(hào)強(qiáng)度對(duì)各個(gè)三角形的加權(quán)質(zhì)心進(jìn)行計(jì)算，并求平均值，作為未知節(jié)點(diǎn)坐標(biāo)；

步驟4：未知節(jié)點(diǎn)搜索其通信范圍內(nèi)已被定位出的其它未知節(jié)點(diǎn)，將這些節(jié)點(diǎn)設(shè)置為新錨節(jié)點(diǎn)使用.繼續(xù)判斷錨節(jié)點(diǎn)個(gè)數(shù)是否超過3個(gè)，如果超過3個(gè)，轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟7；

步驟5：任意選取3個(gè)錨節(jié)點(diǎn)(包括其通信范圍內(nèi)的錨節(jié)點(diǎn)和已經(jīng)被定位的其它未知節(jié)點(diǎn))組成三角形，判斷未知節(jié)點(diǎn)是否至少位于一個(gè)三角形中，如果是，轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟6；

步驟6：未知節(jié)點(diǎn)取其通信范圍內(nèi)的所有錨節(jié)點(diǎn)和已經(jīng)定位的未知節(jié)點(diǎn)坐標(biāo)的平均值作為其位置；

步驟7：未知節(jié)點(diǎn)通信范圍內(nèi)錨節(jié)點(diǎn)和新增錨節(jié)點(diǎn)(已經(jīng)定位的未知節(jié)點(diǎn))個(gè)數(shù)小于3，節(jié)點(diǎn)不能被定位；

步驟8：將整個(gè)網(wǎng)絡(luò)范圍內(nèi)所有未知節(jié)點(diǎn)的定位誤差求和取平均值作為網(wǎng)絡(luò)的總體定位誤差.

為了對(duì)優(yōu)化的質(zhì)心定位算法有個(gè)清晰的描述，圖3給出了算法的流程圖.

圖3 算法流程圖

4 仿真實(shí)驗(yàn)及結(jié)果分析

為了測(cè)試本文算法在定位方面的性能，利用matlabR2014b將其與質(zhì)心定位算法、RSSI加權(quán)質(zhì)心定位算法、增強(qiáng)的質(zhì)心定位算法進(jìn)行仿真對(duì)比，討論在相同的環(huán)境下，錨節(jié)點(diǎn)個(gè)數(shù)、通信半徑、節(jié)點(diǎn)總數(shù)對(duì)不同定位算法性能的影響，使用定位誤差率衡量各個(gè)算法的性能.

4.1 信號(hào)傳播模型

最常用和簡(jiǎn)單的無線電信號(hào)傳輸模型是Regular Model.在 d0m 處的功率是 PL(d0)dBm,則在 dm 的功耗是：

(3)

其中，η定義為射頻信道衰減指數(shù)，在自由空間一般取值為2，郊區(qū)或者城市中一般取值為3到6之間.然而由于傳播介質(zhì)和器件特性的因素，節(jié)點(diǎn)的信號(hào)強(qiáng)度在不同方向存在不可忽略的不規(guī)則性，(1)式所定義的模型較為理想，與實(shí)際測(cè)量的信號(hào)之間存在偏差.文獻(xiàn)[12]介紹了無線電信號(hào)不規(guī)則(Radio Irregularity Model，RIM)模型，RIM模型是在簡(jiǎn)單的二進(jìn)制不規(guī)則模型DOI的基礎(chǔ)上提出的.在RIM模型中，作者引入了系數(shù)Ki表示不同方向的路徑損耗，即Ki是第i個(gè)方向的系數(shù)，同時(shí)為了描述無線模型的不規(guī)則度，引入DOI參數(shù).DOI定義為無線電傳播方向上每單位度數(shù)變化的最大路徑損失百分比變化，Ki的計(jì)算公式為：

(4)

RIM模型可用(5)式表示,式中Xσ表示信號(hào)衰減的固定部分.

(5)

本文的仿真實(shí)驗(yàn)使用這個(gè)更加精細(xì)的模型來評(píng)估定位算法的性能.

4.2 仿真環(huán)境參數(shù)

仿真環(huán)境參數(shù)如表1所列.

表1 仿真環(huán)境參數(shù)表

4.3 仿真結(jié)果

在仿真實(shí)驗(yàn)中，將傳感器節(jié)點(diǎn)隨機(jī)分布在1 000 m×1 000 m的區(qū)域,當(dāng)傳感器節(jié)點(diǎn)的總個(gè)數(shù)為300、錨節(jié)點(diǎn)比例為0.2、通信半徑為200 m時(shí)，傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的分布如圖4所示.其中錨節(jié)點(diǎn)用星號(hào)表示，未知節(jié)點(diǎn)表示為圓圈.節(jié)點(diǎn)鄰居關(guān)系如圖5所示.

圖4 傳感器節(jié)點(diǎn)分布圖

圖5 節(jié)點(diǎn)鄰居關(guān)系

在部署區(qū)域內(nèi)部隨機(jī)散布300個(gè)傳感器節(jié)點(diǎn)，通信半徑為200，當(dāng)錨節(jié)點(diǎn)的比例從0.1變化到0.3時(shí)，比較錨節(jié)點(diǎn)個(gè)數(shù)對(duì)定位誤差率的影響.不同情況下的定位誤差率結(jié)果如圖6-圖8所示.從圖6可以看出，隨著錨節(jié)點(diǎn)比例增加，傳統(tǒng)質(zhì)心定位算法，基于RSSI的加權(quán)定位算法和文獻(xiàn)[8]所提出的增強(qiáng)質(zhì)心定位算法以及本文算法的定位誤差率都呈現(xiàn)下降趨勢(shì).其中傳統(tǒng)質(zhì)心定位算法的誤差率在0.3 916～0.2 358之間，而本文算法定位誤差率最低.增強(qiáng)質(zhì)心定位算法在錨節(jié)點(diǎn)密度為0.15時(shí)定位誤差開始大于傳統(tǒng)質(zhì)心定位算法，出現(xiàn)定位惡化情況.

圖6 通信半徑為200,節(jié)點(diǎn)總數(shù)為300的定位誤差率

圖7 通信半徑為200,錨節(jié)點(diǎn)比例為0.2的定位誤差率

圖8 錨節(jié)點(diǎn)比例為0.2，節(jié)點(diǎn)總數(shù)為300的定位誤差率

節(jié)點(diǎn)通信半徑為200，錨節(jié)點(diǎn)的比例固定為0.2，比較節(jié)點(diǎn)總數(shù)從200變化到400時(shí)對(duì)定位誤差率的影響如圖7所示.從圖7可以看出，隨著節(jié)點(diǎn)總數(shù)增加，以上幾種算法其定位誤差率都在減少，當(dāng)節(jié)點(diǎn)總數(shù)增加到250時(shí)，定位誤差率趨于穩(wěn)定，其中傳統(tǒng)質(zhì)心定位算法的誤差率在0.3 373～0.2 673范圍之間，本文算法定位誤差率最低.

節(jié)點(diǎn)總數(shù)為300，錨節(jié)點(diǎn)比例為0.2，比較節(jié)點(diǎn)通信半徑由100變化到300的過程中幾種定位算法的誤差率如圖8所示.從圖8可以看出，隨著節(jié)點(diǎn)通信半徑的增加，以上幾種定位算法的誤差率都在降低，但增強(qiáng)質(zhì)心定位算法在通信半徑為200左右時(shí)，定位誤差開始大于傳統(tǒng)質(zhì)心定位算法，出現(xiàn)定位惡化情況.在通信半徑為300時(shí)，傳統(tǒng)質(zhì)心定位算法的定位誤差率為0.1 848，而文獻(xiàn)[8]的定位誤差率為0.2 661，本文算法誤差率可降低到0.1 374，定位準(zhǔn)確度明顯提升.

5 結(jié)語

本文提出的優(yōu)化質(zhì)心定位算法結(jié)合三角形內(nèi)點(diǎn)測(cè)試和通信范圍內(nèi)已定位的未知節(jié)點(diǎn)的坐標(biāo)，實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)的定位，算法充分考慮了錨節(jié)點(diǎn)位置對(duì)未知節(jié)點(diǎn)定位的影響，與傳統(tǒng)質(zhì)心定位算法的不同之處在于：其首先對(duì)未知節(jié)點(diǎn)所處的區(qū)域進(jìn)行判定，計(jì)算其所在的多個(gè)由錨節(jié)點(diǎn)所組成的三角形的質(zhì)心平均值，將其作為未知節(jié)點(diǎn)的估計(jì)位置；在錨節(jié)點(diǎn)個(gè)數(shù)缺乏和判定出未知節(jié)點(diǎn)不處于任一錨節(jié)點(diǎn)所組成的三角形區(qū)域之后，將已定位的未知節(jié)點(diǎn)加入錨節(jié)點(diǎn)中，實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)進(jìn)行定位.基于仿真實(shí)驗(yàn)結(jié)果可以看出本文所提出的算法在定位精度方面具有更好的精準(zhǔn)率.