改進的無線傳感器網絡質心定位算法

胡必玲,仝 鈺, 郭玉堂

(合肥師范學院 計算機學院，安徽 合肥 236032)

作為一種智能信息采集系統，傳感器網絡應用在許多領域，而提供事件發生的位置對于大部分應用來說都是系統必須滿足的一項服務.傳感器網絡中事件發生的位置通常確定為檢測到事件的傳感器節點的位置.因此對傳感器節點進行定位成為傳感網應用中的基本問題[1].

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

本文針對傳統質心定位算法中由于錨節點密度分布不均而引起的定位誤差，提出了一種結合三角形內點測試和未知節點優化的質心定位算法.將所提出的算法與質心定位算法[7]、基于RSSI的加權質心定位算法[13]、增強的質心定位算法[14]進行對比，從而證明所提出算法的優勢.

1 質心定位算法

在質心定位算法中網絡的錨節點會向通信范圍內的鄰居節點周期性廣播信標信號，其中包含自身位置信息和ID.未知節點根據一段時間內偵聽到的來自錨節點的信標信號數量判斷是否與此錨節點連通，并將所有和其連通的錨節點構成的多邊形幾何質心確定為自身位置.

假設與未知節點U相連通的錨節點有M1,M2,…,Mk,其坐標為(Xm1,Ym1), (Xm2,Ym2),…, (Xmk,Ymk)，未知節點的實際位置為(X,Y),其對自身的估計位置(Xest,Yest)，R為通信半徑，則

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

(1)

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

(2)

質心定位算法的特點是簡單、計算量小，其計算過程完全依據網絡的連通性，在錨節點分布均勻的情況下，會獲得比較滿意的仿真定位精度.但通常情況下錨節點分布較為隨機，質心定位算法的定位結果會呈現較大誤差.

2 相關改進工作

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

3 優化的質心定位算法

3.1 算法基本思想

質心定位算法中如果未知節點通信范圍內存在的錨節點個數較少或分布不均，則未知節點不位于由錨節點構成的幾何圖形范圍之內會導致定位效果偏差較大.為提升錨節點隨機分布情況下的定位精度，提出了一種結合三角形內點測試(PIT)和通信范圍內已定位未知節點的優化質心定位算法，如圖1和圖2所示.

圖1 優化的質心定位算法定位圖例(1)

圖2 優化的質心定位算法定位圖例(2)

優化質心定位算法的核心思想是:未知節點首先獲取自己通信范圍內的錨節點數量，若不低于3個，則任選3個錨節點構成三角形，并進一步判定自己是否位于此三角形內；如果未知節點處于n個由其通信范圍內的錨節點組成的三角形范圍之內，則用每個三角形錨節點的信號強度進行加權得出每個三角形質心，取所有質心的平均值作為自己的位置;如果未知節點獲取到的通信范圍內錨節點的個數小于3個或不處于任一錨節點所組成三角形范圍內，則增加其通信范圍內已經定位的未知節點作為新的錨節點，繼續判定其位于哪幾個三角形范圍內，取三角形質心的平均值為其位置.如果未知節點不處于任一由其通信范圍內的錨節點和已定位的未知節點組成的三角形范圍之內，則取其通信范圍內的所有錨節點和已經定位的未知節點坐標的平均值作為其位置；如果引入已定位未知節點(新的錨節點)后，周圍的錨節點個數仍小于3個，則該未知節點不能被定位.

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

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

3.2 算法流程

步驟1：每個未知節點搜索自己通信范圍內的錨節點，判斷節點數量是否大于3，如果大于3轉步驟2，否則轉步驟4；

步驟2：任意組合3個錨節點形成若干個三角形，判斷未知節點是否至少處于一個三角形中，并統計個數，如果是，轉步驟3，否則轉步驟4；

步驟3：根據接收信號強度對各個三角形的加權質心進行計算，并求平均值，作為未知節點坐標；

步驟4：未知節點搜索其通信范圍內已被定位出的其它未知節點，將這些節點設置為新錨節點使用.繼續判斷錨節點個數是否超過3個，如果超過3個，轉步驟5，否則轉步驟7；

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

步驟6：未知節點取其通信范圍內的所有錨節點和已經定位的未知節點坐標的平均值作為其位置；

步驟7：未知節點通信范圍內錨節點和新增錨節點(已經定位的未知節點)個數小于3，節點不能被定位；

步驟8：將整個網絡范圍內所有未知節點的定位誤差求和取平均值作為網絡的總體定位誤差.

為了對優化的質心定位算法有個清晰的描述，圖3給出了算法的流程圖.

圖3 算法流程圖

4 仿真實驗及結果分析

為了測試本文算法在定位方面的性能，利用matlabR2014b將其與質心定位算法、RSSI加權質心定位算法、增強的質心定位算法進行仿真對比，討論在相同的環境下，錨節點個數、通信半徑、節點總數對不同定位算法性能的影響，使用定位誤差率衡量各個算法的性能.

4.1 信號傳播模型

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

(3)

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

(4)

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

(5)

本文的仿真實驗使用這個更加精細的模型來評估定位算法的性能.

4.2 仿真環境參數

仿真環境參數如表1所列.

表1 仿真環境參數表

4.3 仿真結果

在仿真實驗中，將傳感器節點隨機分布在1 000 m×1 000 m的區域,當傳感器節點的總個數為300、錨節點比例為0.2、通信半徑為200 m時，傳感器網絡中節點的分布如圖4所示.其中錨節點用星號表示，未知節點表示為圓圈.節點鄰居關系如圖5所示.

圖4 傳感器節點分布圖

圖5 節點鄰居關系

在部署區域內部隨機散布300個傳感器節點，通信半徑為200，當錨節點的比例從0.1變化到0.3時，比較錨節點個數對定位誤差率的影響.不同情況下的定位誤差率結果如圖6-圖8所示.從圖6可以看出，隨著錨節點比例增加，傳統質心定位算法，基于RSSI的加權定位算法和文獻[8]所提出的增強質心定位算法以及本文算法的定位誤差率都呈現下降趨勢.其中傳統質心定位算法的誤差率在0.3 916～0.2 358之間，而本文算法定位誤差率最低.增強質心定位算法在錨節點密度為0.15時定位誤差開始大于傳統質心定位算法，出現定位惡化情況.

圖6 通信半徑為200,節點總數為300的定位誤差率

圖7 通信半徑為200,錨節點比例為0.2的定位誤差率

圖8 錨節點比例為0.2，節點總數為300的定位誤差率

節點通信半徑為200，錨節點的比例固定為0.2，比較節點總數從200變化到400時對定位誤差率的影響如圖7所示.從圖7可以看出，隨著節點總數增加，以上幾種算法其定位誤差率都在減少，當節點總數增加到250時，定位誤差率趨于穩定，其中傳統質心定位算法的誤差率在0.3 373～0.2 673范圍之間，本文算法定位誤差率最低.

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

5 結語

本文提出的優化質心定位算法結合三角形內點測試和通信范圍內已定位的未知節點的坐標，實現對未知節點的定位，算法充分考慮了錨節點位置對未知節點定位的影響，與傳統質心定位算法的不同之處在于：其首先對未知節點所處的區域進行判定，計算其所在的多個由錨節點所組成的三角形的質心平均值，將其作為未知節點的估計位置；在錨節點個數缺乏和判定出未知節點不處于任一錨節點所組成的三角形區域之后，將已定位的未知節點加入錨節點中，實現對未知節點進行定位.基于仿真實驗結果可以看出本文所提出的算法在定位精度方面具有更好的精準率.