張 丹, 董雷剛, 李 梓

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

無線傳感器網(wǎng)絡(luò)中一種改進的加權(quán)質(zhì)心定位算法研究

張 丹, 董雷剛, 李 梓

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

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

無線傳感器網(wǎng)絡(luò)；加權(quán)質(zhì)心定位；節(jié)點定位；頂點凹凸性

0 引言

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

根據(jù)無線傳感器網(wǎng)絡(luò)中的節(jié)點是否知道自身位置分為信標節(jié)點和未知節(jié)點，信標節(jié)點一般是通過人工部署或者GPS定位來獲取位置信息的，這種節(jié)點在無線傳感器網(wǎng)絡(luò)中的比例較少，它們的作用是幫助未知節(jié)點獲得位置信息的。未知節(jié)點一般是隨機部署的，它們的位置信息是未知的，通過信標節(jié)點來計算自身的位置信息。計算未知節(jié)點位置信息中的距離相關(guān)的定位算法通過獲得節(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)。這些算法具有很高的定位精度，但是需要額外的硬件支持來進行精確地測量。距離無關(guān)的定位算法不需要知道節(jié)點間的絕對距離和角度信息，根據(jù)節(jié)點之間的連通性信息來實現(xiàn)自身信息的計算。距離無關(guān)的定位算法主要有APIT(Approximate Point-in-Triangulation test algorithm)近似三角形內(nèi)點測試法[3]、DV-Hop算法[4]、Amorphous算法、質(zhì)心算法。由于基于距離的定位算法的費用高，因此距離無關(guān)的定位算法得到廣泛的應(yīng)用。在距離無關(guān)的定位算法中，質(zhì)心算法簡單、開銷低、易于實現(xiàn)，因此應(yīng)用比較廣泛。然而質(zhì)心算法的鄰居信標節(jié)點的密度、一致性和連通度對未知節(jié)點的定位精度有很大的影響，因此在本論文中提出一種改進的質(zhì)心定位算法，該算法無需額外的硬件，可以提高定位的精度。

1 質(zhì)心定位算法原理

1.1 質(zhì)心定位算法

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

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

(1)

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

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

圖1 質(zhì)心算法原理圖

1.2 測距原理

信號在傳播的過程中，其強度是隨著距離的改變發(fā)生變化的，根據(jù)這個變化就可以得出信號強度的衰減與傳播距離的關(guān)系。目前在無線傳感器網(wǎng)絡(luò)中比較常用的模型是傳播損耗模型。在無線傳感器網(wǎng)絡(luò)中，節(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 改進的質(zhì)心算法

2.1 加權(quán)質(zhì)心定位算法原理

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

(5)

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

(6)

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

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

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

假設(shè)未知節(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的同一側(cè)，如果他們是在Vi-1Vi+1的同一個側(cè)面則Vi(Xi，Yi)是凹點，否則是凸點?？梢岳帽磉_式(7)判斷頂點的凹凸性。

(7)

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

2.3 改進的質(zhì)心定位算法

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

圖2 改進質(zhì)心算法的流程圖

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

3 算法仿真實驗結(jié)論

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

4 結(jié) 語

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

大慶師范學院青年基金項目“基于互聯(lián)網(wǎng)+人臉識別技術(shù)的學生身份認定系統(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