無線傳感器網絡中一種改進的加權質心定位算法研究

張 丹, 董雷剛, 李 梓

(大慶師范學院 計算機科學與信息技術學院，黑龍江 大慶 163712)

無線傳感器網絡中一種改進的加權質心定位算法研究

張 丹, 董雷剛, 李 梓

(大慶師范學院 計算機科學與信息技術學院，黑龍江 大慶 163712)

在無線傳感器網絡的應用中節(jié)點的定位信息是非常重要的。本論文提出一種改進的加權質心算法，該算法是基于平面多邊形定點凹凸性原理進行實現(xiàn)的，算法中選擇自由傳播模型和對數(shù)距離路徑分布模型來計算無線電波傳播過程。改進的質心算法能夠提高定位的精度，仿真實驗驗證了該算法的平均定位誤差，仿真實驗結果表明，在相同的條件下，該算法的定位精度高于加權質心算法。

無線傳感器網絡；加權質心定位；節(jié)點定位；頂點凹凸性

0 引言

隨著微電子技術的迅猛發(fā)展，WSN(Wireless Sensor Networks)即無線傳感器網絡技術得到了很大的增長。它對人們的生產、生活都產生了很大的影響，而且廣泛應用在環(huán)境、軍事、健康醫(yī)療、農業(yè)、家庭、交通運輸和其它商業(yè)領域。無線傳感器網絡中有大量的傳感器節(jié)點，這些節(jié)點體積小、價格低、計算能力低、有限的能源資源，它們被隨機地部署在監(jiān)測區(qū)域中。這些傳感器節(jié)點的位置信息在無線傳感器網絡中起到了關鍵的作用，在無線傳感器網絡中沒有位置信息的節(jié)點是沒有任何意義的。GPS(Global Positioning System) 即全球定位系統(tǒng)是傳感器節(jié)點獲得定位信息的一種非常有效的方法，但是由于GPS的成本高、體積和重量大，如果為每一個傳感器節(jié)點都配備GPS是不可行的。與此同時，它會使節(jié)點的成本大大增加、體積也隨之增大。因此近些年，無線傳感器網絡中節(jié)點的定位問題得到了廣泛的關注。根據(jù)在定位的過程中是否需要測量網絡中節(jié)點之間的距離將定位算法分為兩種，分別是距離相關的定位算法和距離無關的定位算法兩種。

根據(jù)無線傳感器網絡中的節(jié)點是否知道自身位置分為信標節(jié)點和未知節(jié)點，信標節(jié)點一般是通過人工部署或者GPS定位來獲取位置信息的，這種節(jié)點在無線傳感器網絡中的比例較少，它們的作用是幫助未知節(jié)點獲得位置信息的。未知節(jié)點一般是隨機部署的，它們的位置信息是未知的，通過信標節(jié)點來計算自身的位置信息。計算未知節(jié)點位置信息中的距離相關的定位算法通過獲得節(jié)點之間的距離或者角度信息來進行，這些算法主要有TDOA(Time Difference of Arrival)到達時間差法[1]、AOA(Angle of Arrival)到達角度法[2]、RIPS(Radio Interferometry Positioning System)無線電干涉定位系統(tǒng)和RSSI(Received Signal Strength Indication)接收信號強度指示定位系統(tǒng)。這些算法具有很高的定位精度，但是需要額外的硬件支持來進行精確地測量。距離無關的定位算法不需要知道節(jié)點間的絕對距離和角度信息，根據(jù)節(jié)點之間的連通性信息來實現(xiàn)自身信息的計算。距離無關的定位算法主要有APIT(Approximate Point-in-Triangulation test algorithm)近似三角形內點測試法[3]、DV-Hop算法[4]、Amorphous算法、質心算法。由于基于距離的定位算法的費用高，因此距離無關的定位算法得到廣泛的應用。在距離無關的定位算法中，質心算法簡單、開銷低、易于實現(xiàn)，因此應用比較廣泛。然而質心算法的鄰居信標節(jié)點的密度、一致性和連通度對未知節(jié)點的定位精度有很大的影響，因此在本論文中提出一種改進的質心定位算法，該算法無需額外的硬件，可以提高定位的精度。

1 質心定位算法原理

1.1 質心定位算法

質心定位算法是在2000年由N. Bulusu和J. Heidemann提出的，質心定位算法中的未知節(jié)點的位置信息是通過網絡中的信標節(jié)點的位置信息進行計算的。這種算法的過程包括三個階段，首先無線傳感器網絡中的未知節(jié)點向鄰居節(jié)點廣播定位請求。然后接收到這個請求的信標節(jié)點將它們的id以及接收的信號強度發(fā)送給未知節(jié)點，未知節(jié)點根據(jù)接收到的信號強度模型，每個節(jié)點計算出與鄰居節(jié)點的距離。最后當未知節(jié)點接收道德信息超過3個則可以計算出它自身的未知。

未知節(jié)點的坐標通過公式(1)進行計算。

(1)

其中(xestyest)為未知節(jié)點的坐標。假設有n個信標節(jié)點，它們的坐標分別為(xi，yi)(i=1，2，…，n)，它們分布在未知節(jié)點的周圍。

質心算法的基本原理圖如圖1所示。圖中黑色圓點為信標節(jié)點，白色圓點為未知節(jié)點。顯而易見，質心算法的原理比較簡單，而且比較容易計算。然而當無線傳感器網絡中節(jié)點的連通度低，未知節(jié)點周圍的信標節(jié)點的密度低時，質心算法的定位精度將大大降低。

圖1 質心算法原理圖

1.2 測距原理

信號在傳播的過程中，其強度是隨著距離的改變發(fā)生變化的，根據(jù)這個變化就可以得出信號強度的衰減與傳播距離的關系。目前在無線傳感器網絡中比較常用的模型是傳播損耗模型。在無線傳感器網絡中，節(jié)點被分散在開放的空間，所以本文選擇自由傳播模型和對數(shù)距離路徑分布模型來計算電波傳播過程。自由空間傳播損耗模型方程如下：

PL(d0)=32.44+10nlg(d0)+10nlg(f)

(2)

在方程(2)中，d0為參考距離，f為接收信號強度指示系統(tǒng)的信號強度，PL(d0)為距離為d0的接收信號強度損耗，n為損耗因子。由于周圍的環(huán)境因素，自由空間傳播損耗模型將受到建筑、傳輸公里和障礙物的高度等的影響。因此，對數(shù)距離分布模型更具有實用性。對數(shù)距離分布模型方程如方程(3)所示。

PL(d)[dB]=PL(d0)+10nlog(d0)+X0

(3)

在方程(3)中，PL(d)指的傳播距離為d米的傳播損耗；X0為一個平均值為0的高斯隨機變量。未知節(jié)點接收到的信號強度如方程(4)所示。

RSSI=Psend+Pamplify-PL(d)

(4)

在方程(4)中，Psend為傳輸功率，Pamplify為天線增益。

2 改進的質心算法

2.1 加權質心定位算法原理

為了提高質心定位算法的定位精度，加權質心定位算法被提出，它的原理如方程(5)所示。

(5)

其中wi為權值，它的值一般可以用方程(6)表示。d是發(fā)送者和接收者之間的距離[5]。

(6)

在質心算法中，當未知節(jié)點周圍的信標節(jié)點分布不均勻，定位精度將下降。在本文針對在未知節(jié)點周圍的鄰居信標節(jié)點所組成的圖形是凸的或者凹的多邊形這兩種情況，提出了改進的加權質心算法。

2.2 平面多邊形定點凹凸性判別

在無線傳感器網絡中，未知節(jié)點周圍通信半徑內都存在一些信標節(jié)點，它們被稱為鄰居信標節(jié)點，這些信標節(jié)點通常會構成一個簡單的多邊形，下面將描述平面多邊形頂點凸凹性的原理。

假設未知節(jié)點接收到n個信標節(jié)點的坐標信息，它們分別是：V1(X1，Y1)，V2(X2，Y2)，…Vn(Xn，Yn)。VA(XA，YA)為距離未知節(jié)點最遠的鄰居信標節(jié)點，這個點必然是這些信標節(jié)點所組成的多邊形的一個凸點。對其余頂點凸凹性的判斷可以采用以下原則。取頂點Vi(Xi，Yi)的兩個相鄰頂點分別為Vi-1，Vi+1，連接點Vi-1和點Vi+1，判斷點Vi和A是否在Vi-1Vi+1的同一側，如果他們是在Vi-1Vi+1的同一個側面則Vi(Xi，Yi)是凹點，否則是凸點?？梢岳帽磉_式(7)判斷頂點的凹凸性。

(7)

△>0，A和Vi在Vi-1Vi+1的同一側，Vi為凹點?！?0，A和Vi不在Vi-1Vi+1的同一側，Vi為凸點?！?0，A和Vi在Vi-1Vi+1上。

2.3 改進的質心定位算法

假設傳感器節(jié)點被部署在一個二維平面上，而且所有的節(jié)點都是靜止的。整個改進質心算法的流程如圖2所示。

圖2 改進質心算法的流程圖

無線傳感器網絡中的未知節(jié)點向鄰居節(jié)點廣播定位請求。然后接收到這個請求的信標節(jié)點將它們的id、坐標以及接收的信號強度發(fā)送給未知節(jié)點。計算未知節(jié)點與鄰居信標節(jié)點之間的距離，選擇距離未知節(jié)點最遠的信標節(jié)點，該點一定是一個凸點。依次判斷每一點是否是一個凸點。如果它是一個凹點，將這個點從鄰居信標節(jié)點中刪除。如果剩余的鄰居信標節(jié)點的數(shù)量超過三個，則使用加權質心定位算法來估計未知節(jié)點的坐標。否則，將選擇另一種算法。

3 算法仿真實驗結論

為了比較改進的質心算法和加權質心算法的效率，進行了仿真，并對實驗結果進行了分析。假定有100個傳感器節(jié)點隨機分布在100米×100米的區(qū)域，信標節(jié)點的比例可根據(jù)網絡通信連通性進行調整。仿真是在MATLAB 2012中進行的，實驗中說明了當信標節(jié)點密度為5%和10%兩種情況下節(jié)點的定位精度，信標節(jié)點密度為5%時節(jié)點的定位精度小于信標節(jié)點密度為10%的定位精度。但是當信標節(jié)點密度相同時，本文提出的加權質心定位算法的定位精度明顯高于傳統(tǒng)的質心定位算法，改進的質心定位算法比加權質心定位算法更精確、更有效。這兩種算法的定位精度與網絡中的信標節(jié)點密度密切相關。當信標定密度增大時，兩種算法的定位誤差都會減小。因此，本文所提出的定位算法具有一定的實用意義。

4 結 語

在本文中，提出了一種改進的加權質心定位算法，此算法是基于無線傳感器網絡的平面多邊形頂點凹凸性原理進行實現(xiàn)的。在分析無線電波傳播損耗模型的基礎上，選擇自由傳播模型和對數(shù)距離路徑分布模型來計算無線電波傳播過程。定位精度通過由未知節(jié)點周圍的鄰居信標節(jié)點組成的平面多邊形的頂點凸凹性的原則來改進質心算法。仿真實驗驗證了該算法的平均定位誤差的效果，仿真結果表明，改進后的算法比加權質心定位算法更有效。而且網絡中的信標節(jié)點的密度越高，定位誤差越小。

[1] Ergut S，Rao R R，Dural O，et al．Localization via TDOA in a UWB Sensor Network using Neural Networks[J]．IEEE International Conference on Communications，2008：2398- 2403．

[2] Lee YS，Park JW，Barolli L．A localization algorithm based on AOA for ad-hoc sensor networks[J]．Mobile Information Systems，2012，8(8)：61-72．

[3] Yong Zhou，Xin Ao，Shixiong Xia．An Improved APIT Node Self-localization Algorithm in WSN[J]．World Congress on Intelligent Control & Automation，2008：7582-7586．

[4] Tomic S，Mezei I．Improved DV-Hop localization algorithm for wireless sensor networks[J]．IEEE Jubilee International Symposium on Intelligent Systems and Informatics．2012，62(6) ：389-394．

[5] Dong Q，Xu X．A Novel Weighted Centroid Localization Algorithm Based on RSSI for an Outdoor Environment[J]．Journal of Communications，2014，9(9)：279-285．

[責任編輯：崔海瑛]

(英文摘要略)

Research on an improved weighted centroid localization algorithm in wireless sensor networks

Zhang Dan, Dong Lei-gang, Li Zi

(Computer Science and Information Technology DepartmentDaqing Normal University, Daqing 163712, China)

張丹(1979-)，女，黑龍江大慶人，副教授，從事嵌入式系統(tǒng)設計方向研究。

大慶師范學院青年基金項目“基于互聯(lián)網+人臉識別技術的學生身份認定系統(tǒng)”(15ZR07)。

TP302.1

A

2095-0063(2016)06-0033-04

2016-07-14

DOI 10.13356/j.cnki.jdnu.2095-0063.2016.06.009