基于四面體模型RSSI的優(yōu)化加權(quán)質(zhì)心定位算法?

李京燏 毛永毅 徐 萍

（1.西安郵電大學(xué)電子工程學(xué)院 西安 710061）（2.火箭軍工程大學(xué)理學(xué)院 西安 710061）

1 引言

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）［1］隨著技術(shù)的發(fā)展已經(jīng)在軍事、智能交通、智能家居、健康醫(yī)療、環(huán)境監(jiān)控等現(xiàn)實(shí)場(chǎng)景中廣泛應(yīng)用。在實(shí)際應(yīng)用中，無(wú)線傳感器節(jié)點(diǎn)在網(wǎng)絡(luò)中隨機(jī)部署，大部分節(jié)點(diǎn)位置無(wú)法事先確定，而位置信息是傳感器節(jié)點(diǎn)采集數(shù)據(jù)中不可或缺的一部分，沒(méi)有位置信息的數(shù)據(jù)幾乎沒(méi)有意義，確定采集數(shù)據(jù)的節(jié)點(diǎn)位置及事件發(fā)生的地點(diǎn)是傳感器網(wǎng)絡(luò)基本功能之一［2］。節(jié)點(diǎn)定位根據(jù)其定位機(jī)制可分為測(cè)距（Range-based）技術(shù)和非測(cè)距（Range-free）技術(shù)本兩類［3］，基于測(cè)距技術(shù)定位算法主要有 RSSI（Re?ceived Signal Strength Indication）、TOA（Time of Ar?rival）、TDOA（Time Difference of Arrival）和 AOA（Arrival of Angle）等；基于非測(cè)距技術(shù)僅根據(jù)網(wǎng)絡(luò)連通性等實(shí)現(xiàn)定位。

基于RSSI測(cè)距的定位算法因其實(shí)現(xiàn)簡(jiǎn)單、不需要額外開(kāi)銷和耗能少的特點(diǎn)應(yīng)用十分廣泛。在實(shí)際環(huán)境中，由于多徑、繞射、傳播障礙物等因素，影響了定位精度［4］。就如何有效減小定位誤差，提高定位精度，許多RSSI測(cè)距定位改進(jìn)算法取得了一定的研究成果。文獻(xiàn)［5］在傳統(tǒng)的三維質(zhì)心定位算法和APIT-3D定位算法的基礎(chǔ)之上，提出基于四面體模型的三維質(zhì)心算法。文獻(xiàn)［6］建立四面體模型，通過(guò)修正加權(quán)系數(shù)，采用質(zhì)心加權(quán)求和定位算法，達(dá)到提高定位精度的目的。文獻(xiàn)［7］對(duì)優(yōu)選后的RSSI數(shù)據(jù)通過(guò)修正加權(quán)質(zhì)心算法獲得了精度較高的未知節(jié)點(diǎn)位置。上述研究結(jié)果表明，針對(duì)質(zhì)心算法中的加權(quán)系數(shù)進(jìn)行優(yōu)化，選取合適的權(quán)值系數(shù)，能夠有效地提高加權(quán)質(zhì)心算法的定位精度。

本文提出一種基于RSSI測(cè)距的優(yōu)化權(quán)值質(zhì)心加權(quán)定位算法，通過(guò)信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)構(gòu)成的四面體，求得多個(gè)未知節(jié)點(diǎn)估計(jì)位置，再采用優(yōu)化后的權(quán)值對(duì)多個(gè)節(jié)點(diǎn)估計(jì)位置進(jìn)行加權(quán)質(zhì)心求解節(jié)點(diǎn)位置，實(shí)現(xiàn)定位精度的提高。

2 RSSI定位傳輸模型

RSSI測(cè)距定位技術(shù)原理［8～9］是已知信標(biāo)節(jié)點(diǎn)發(fā)射信號(hào)的強(qiáng)度，根據(jù)未知節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度，通過(guò)無(wú)線信號(hào)傳播模型轉(zhuǎn)換為兩個(gè)節(jié)點(diǎn)的距離值，通過(guò)定位算法來(lái)實(shí)現(xiàn)節(jié)點(diǎn)位置的確定。

RSSI測(cè)距研究依賴于無(wú)線信號(hào)傳播模型，常用模型有：自由空間傳播模型、對(duì)數(shù)--常態(tài)分布模型、Shadowing模型等。鑒于無(wú)線信號(hào)在傳輸過(guò)程受空間環(huán)境中不確定因素的影響較大，因而在實(shí)際仿真環(huán)境搭建中，Shadowing模型因其綜合性強(qiáng)被廣泛采用［9］。

Shadowing模型［11］由兩部分組成：損耗模型（Pass Loss）和對(duì)數(shù)正態(tài)分布模型。損耗模型［12］是用一個(gè)已知參考距離r0及r0上的接收功率PL(r0)預(yù)測(cè)出未知距離r處的平均接收功率PL(r)，其表達(dá)式為

式中，q為路徑損耗系數(shù)，范圍在2～6之間且隨著障礙物的增多而增大。而對(duì)數(shù)正態(tài)分布模型［13］反映的是在固定距離上，接收能量符合對(duì)數(shù)正態(tài)隨機(jī)變化，即以dB作為計(jì)量單位時(shí)，Shadowing模型滿足高斯分布。其表達(dá)式為

式（2）中，PL(d0)為參考節(jié)點(diǎn)d0處的信號(hào)強(qiáng)度，PL(d)為在距離d處的未知節(jié)點(diǎn)的信號(hào)強(qiáng)度，k為路徑損耗系數(shù)。Xσ是標(biāo)準(zhǔn)差為σ的零均值的高斯隨機(jī)變量，對(duì)計(jì)算結(jié)果的影響不大。

3 三維修正加權(quán)質(zhì)心定位算法

3.1 節(jié)點(diǎn)位置估計(jì)

質(zhì)心算法［14］是通過(guò)未知節(jié)點(diǎn)接收所有通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)的信息，將這些信標(biāo)節(jié)點(diǎn)的幾何質(zhì)心作為自己的估計(jì)位置［8］。為反映信標(biāo)節(jié)點(diǎn)位置對(duì)未知節(jié)點(diǎn)位置的影響，提出加權(quán)質(zhì)心算法［15～16］，引入加權(quán)因子來(lái)體現(xiàn)各個(gè)信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的位置決定權(quán)，反映其自身位置對(duì)未知節(jié)點(diǎn)的影響程度［9］。

由4個(gè)節(jié)點(diǎn)A、B、C、D構(gòu)成的四面體，位置如圖1所示。

圖1 加權(quán)質(zhì)心定位算法示意圖

其中A、B、C、D為信標(biāo)節(jié)點(diǎn)，P為未知節(jié)點(diǎn)。當(dāng)未知節(jié)點(diǎn)P從信標(biāo)節(jié)點(diǎn)A、B、C、D接收到無(wú)線信號(hào)時(shí)，根據(jù)式（2）可以計(jì)算出未知節(jié)點(diǎn)與四個(gè)信標(biāo)節(jié)點(diǎn)的距離｛d1，d2，d3，d4｝，根據(jù)傳統(tǒng)加權(quán)質(zhì)心定位算法，可求得基于四面體ABCD的未知節(jié)點(diǎn)估計(jì)位置P（x，y，z）。傳統(tǒng)加權(quán)質(zhì)心算法所得節(jié)點(diǎn)估計(jì)位置P的坐標(biāo)為

其中，wi表示第i個(gè)信標(biāo)節(jié)點(diǎn)對(duì)應(yīng)的權(quán)重系數(shù)，通常取信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)距離的倒數(shù)，即：

當(dāng)兩節(jié)點(diǎn)不能通信時(shí)，權(quán)值為0。

3.2 優(yōu)化權(quán)值

對(duì)于信標(biāo)節(jié)點(diǎn)A、B、C、D、E，可以順序構(gòu)成四面體ABCD和四面體BCDE，依據(jù)上述方法可以求得兩個(gè)未知節(jié)點(diǎn)位置估計(jì)值P1和P2。節(jié)點(diǎn)最終位置O（Ox，Oy，Oz）可通過(guò)估計(jì)位置P1（x，y，z）和P2（x，y，z）再次進(jìn)行優(yōu)化加權(quán)質(zhì)心求解。從信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)的位置關(guān)系考慮，突出強(qiáng)化近距離信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的權(quán)值決定權(quán)［17～8］。提出自身位置優(yōu)化權(quán)值，求解節(jié)點(diǎn)最終位置O。優(yōu)化權(quán)值如下：

式（7）中，估計(jì)位置P1對(duì)應(yīng)的權(quán)值由其所在四面體ABCD中各節(jié)點(diǎn)與未知節(jié)點(diǎn)距離冪級(jí)數(shù)和的倒數(shù)決定，避免了單一可能誤差距離數(shù)據(jù)對(duì)結(jié)果產(chǎn)生較大影響［18～19］。整個(gè)優(yōu)化算法具體如下

其中，估計(jì)位置 Pi對(duì)應(yīng)加權(quán)系數(shù)通過(guò)冪函數(shù)改善了權(quán)值的決定權(quán)［20］。RSSI值隨收發(fā)節(jié)點(diǎn)間距離的增大而非線性減小，距離信標(biāo)節(jié)點(diǎn)越近，應(yīng)具有更大的權(quán)值決定力［20］。n為權(quán)值修正系數(shù)，取正整數(shù)，通過(guò)調(diào)整n的大小來(lái)調(diào)整結(jié)果的修正程度，統(tǒng)計(jì)多次實(shí)驗(yàn)結(jié)果可以獲得當(dāng)前環(huán)境下的最佳修正系數(shù)［21］。

3.3 算法流程

本文算法具體實(shí)現(xiàn)流程如下：

1）m個(gè)信標(biāo)節(jié)點(diǎn)以相同功率周期性地向周圍環(huán)境廣播當(dāng)前的ID和位置信息；對(duì)m個(gè)信標(biāo)節(jié)點(diǎn)信息，建立一個(gè)m個(gè)信標(biāo)節(jié)點(diǎn)集合｛（x1，y1，z1），…，（xm，ym，zm）｝；

2）根據(jù)式（2）可得未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離集合｛d1，d2，d3，…，dm｝；

3）設(shè)｛d1，d2，d3，d4｝為未知節(jié)點(diǎn)到四面體ABCD各節(jié)點(diǎn)的距離，由式（3）、式（4）、式（5）和式（6），可得該四面體模型中的未知節(jié)點(diǎn)的估計(jì)位置P1；設(shè)｛d2，d3，d4，d5｝為未知節(jié)點(diǎn)與四面體BCDE各節(jié)點(diǎn)的距離，可得該四面體模型中的未知節(jié)點(diǎn)的位置P2；對(duì)于m個(gè)信標(biāo)節(jié)點(diǎn)，根據(jù)上述方法可依次求得m個(gè)未知節(jié)點(diǎn)O的估計(jì)位置｛P1，P2，P3，…，Pm｝；

5）計(jì)算未知節(jié)點(diǎn)定位誤差。

4 仿真結(jié)果與分析

用Matlab進(jìn)行算法仿真，基本初始條件是在100m×100m×100m的三維無(wú)線傳感器網(wǎng)絡(luò)空間，一共隨機(jī)分布20個(gè)信標(biāo)節(jié)點(diǎn)，10個(gè)未知節(jié)點(diǎn)，式（2）中路徑損耗系數(shù)k取3，并根據(jù)式（2）生成RSSI數(shù)據(jù)，添加均值為0，方差為10m2的隨機(jī)噪聲作為傳播環(huán)境干擾。按照上述算法流程進(jìn)行定位仿真，仿真結(jié)果如圖2。

圖2 修正加權(quán)質(zhì)心定位算法仿真結(jié)果

傳統(tǒng)加權(quán)質(zhì)心定位算法仿真結(jié)果如圖3：

圖3 傳統(tǒng)加權(quán)質(zhì)心定位算法仿真結(jié)果

從仿真結(jié)果可以看出，對(duì)信標(biāo)節(jié)點(diǎn)劃分四面體區(qū)域后所得節(jié)點(diǎn)估計(jì)位置進(jìn)行修正加權(quán)定位誤差比單一的傳統(tǒng)加權(quán)質(zhì)心算法的定位誤差有明顯減小，所得未知節(jié)點(diǎn)更接近實(shí)際位置。在多次實(shí)驗(yàn)中，當(dāng)修正指數(shù)n=3時(shí)，定位精度達(dá)到最高，同時(shí)實(shí)驗(yàn)結(jié)果較穩(wěn)定。

對(duì)修正加權(quán)質(zhì)心算法與傳統(tǒng)加權(quán)質(zhì)心定位算法進(jìn)行平均誤差統(tǒng)計(jì)，結(jié)果如圖4。

圖4 平均定位誤差

根據(jù)平均定位誤差結(jié)果可以看出，修正后的加權(quán)質(zhì)心定位算法平均定位誤差相對(duì)傳統(tǒng)加權(quán)質(zhì)心定位算法提高了0.2935m，定位精度提高了5.89%。即修正后的加權(quán)質(zhì)心算法定位精度有所提高。

5 結(jié)語(yǔ)

將冪函數(shù)應(yīng)用于權(quán)值優(yōu)化可以小范圍地改善權(quán)值影響力，針對(duì)四面體劃分后所得節(jié)點(diǎn)近似位置，采用冪函數(shù)優(yōu)化權(quán)值對(duì)其進(jìn)行修正，修正權(quán)值充分強(qiáng)化了近距離信標(biāo)節(jié)點(diǎn)的權(quán)值影響力，可以避免局部誤差對(duì)整體結(jié)果產(chǎn)生較大影響，從而有效提高定位精度。所給算法復(fù)雜度低且高效，可適用于多個(gè)未知節(jié)點(diǎn)，利于硬件實(shí)現(xiàn)。

［1］夏少波，許娥.無(wú)線傳感器網(wǎng)絡(luò)WSN探究［J］.通信技術(shù)，2010（8）：18-20，23.

XIA Shaobo，XU E.Discussion on Wireless Sensor Net?work［J］.Communications Technology，2010（8）：18-20，23.

［2］Chan Y W E，Soong B H.A New Lower Bound on Range-Free Localization Algorithms in Wireless Sensor Networks［J］.IEEE Communications Letters，2011，15（1）：16-18.

［3］蔡曉宇，張愛(ài)清，葉新榮.基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究［J］.通信技術(shù)，2014，47（6）：634-641.

CAI Xiaoyu，ZHANG Aiqing，YE Xinrong.RSSI-based Node Self-Localization Algorithm in Wireless Sensor Net?work［J］.Communications Technology，2014，47（6）：634-641.

［4］王雅雋.基于RSSI技術(shù)的無(wú)線空間定位系統(tǒng)設(shè)計(jì)［J］.計(jì)算機(jī)與數(shù)字工程，2016，44（1）：64-67.

WANG Yajuan.Space for Wireless Positioning System De?sign Based on RSSI［J］.Computer and Digital Engineer?ing，2016，44（1）：64-67.

［5］王長(zhǎng)征，湯文亮，徐燕.無(wú)線傳感器網(wǎng)絡(luò)中四面體三維質(zhì)心定位算法［J］.傳感器與微系統(tǒng)，2012，31（8）：141-143.

WANG Changzheng，TANG Wenliang，XU Yan.3D cente?oid in-tetrahedron location algorithm for wireless sensor networks［J］.Transducer and Microsystem Technologies，2012，31（8）：141-143.

［6］王帥，于勁松，粱沛，等.基于四面體模型的三維加權(quán)質(zhì)心定位算法［J］.計(jì)算機(jī)工程，2012，38（9）：90-92.

WANG Shuai，YU Jinsong，LIANG Pei，et al.Three-di?mensionalWeighed Centroid Localization Algorithm Based on Tetrahedral Model［J］.Computer Engineering and Applications，2012，38（9）：90-92.

［7］葛斌，鄭建寶，韓江洪，等.RSSI輔助的三維空間坐標(biāo)四面體質(zhì)心定位算法［J］.計(jì)算機(jī)科學(xué)，2015，42（4）：81-84.

GE Bin，ZHENG Jianbao，HAN Jianghong，et al.RSSI As?sisted Coordinate-tetrahedron Centroid Localization Algo?rithm in Three-dimensional Space［J］.Computer Science，2015，42（4）：81-84.

［8］宋月超，肖宏艷，馬婷婷，等.移動(dòng)終端定位導(dǎo)航系統(tǒng)分類與定位原理分析［J］.計(jì)量與測(cè)試技術(shù)，2016，43（9）：40-42.

SONG Yuechao，XIAO Hongyan，MA Tingting，et al.Oper?ational Principle Analysis and Classification for Different Positioning System of Mobile Terminal［J］.Metrology&Measurement Technique，2016，43（9）：40-42.

［9］劉鎮(zhèn)，劉軍偉.基于RSSI的WSN定位算法的研究［J］.電子設(shè)計(jì)工程，2015（4）：124-126.

LIU Zhen，LIU Junwei.Research of WSN localization algo?rithm based on RSSI［J］.Electronic Design Engineering，2015（4）：124-126.

［10］余俊.基于RSSI的室內(nèi)無(wú)線定位算法研究［D］.武漢：華中科技大學(xué)，2013.

YU Jun.Research on indoor wireless localization algo?rithm based on RSSI［D］.Wuhan：Huazhong University of Science and Technology，2013.

［11］劉云，劉菁原.基于RSSI的加權(quán)質(zhì)心定位算法優(yōu)化研究［J］.華中師范大學(xué)學(xué)報(bào)（自科版），2016，50（3）：358-362.

LIU Yun，LIU Jingyuan.Optimization research on weight?ed centroid location algorithm based on RSSI［J］.Journal of Huazhong Normal University（Natural Science Edi?tion），2016，50（3）：358-362.

［12］施偉，高軍.無(wú)線傳感器網(wǎng)絡(luò)中基于RSSI的改進(jìn)加權(quán)質(zhì)心定位算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2015，32（12）：68-70，104.

SHI Wei，GAO Jun.An Improved Weighted Centroid Lo?calisation Algorithm Based On Rssi For Wireless Sensor Networks［J］.Computer Applications and Software，2015，32（12）：68-70，104.

［13］張正華，戴磊，黎家文，等.基于RSSI的優(yōu)化加權(quán)質(zhì)心定位算法研究［J］.電子設(shè)計(jì)工程，2013，21（7）：171-173.

ZHANG Zhenghua，DAI Lei，LI Jiawen，et al.Research on optimization weighted centroid localization algorithm based on RSSI［J］.Electronic Design Engineering，2013，21（7）：171-173.

［14］崔法毅，邵冠蘭.基于RSSI多邊定位誤差的加權(quán)質(zhì)心定 位 算 法［J］.紅 外 與 激 光 工 程 ，2015，44（7）：2162-2168.

CUI Fayi，SHAO Guanlan.Weighted centroid localiza?tion algorithm based on multilateral localization error of received signal strength indicator［J］.Infrared and Laser Engineering，2015，44（7）：2162-2168.

［15］王琦.基于RSSI測(cè)距的室內(nèi)定位技術(shù)［J］.電子科技，2012，25（6）：64-66，78.

WANG Qi.Research on an Indoor Positioning Technolo?gy Based on RSSI Ranging［J］.Electronic Science and Technology，2012，25（6）：64-66，78.

［16］劉信新，陳鯤.基于RSSI與TDOA的混合測(cè)距加權(quán)定位算法［J］.計(jì)算機(jī)與數(shù)字工程，2011，39（4）：25-28.

LIU Xinxin，CHEN Kun.A Weighted Localization Algo?rithm Using a Hybrid of RSSI and TDOA Range Technol?ogies［J］.Computer and Digital Engineering，2011，39（4）：25-28.

［17］任維政，徐連明，鄧中亮，等.基于RSSI的測(cè)距差分修正 定 位 算 法［J］.傳 感 技 術(shù) 學(xué) 報(bào) ，2008，21（7）：1247-1250.

REN Weizheng，XU Lianming，DENG Zhongliang，et al.Distance Difference Localization Algorithm Based on RS?SI for Wireless Sensor Networks［J］.Chinese Journal of Sensors and Actuators，2008，21（7）：1247-1250.

［18］劉運(yùn)杰，金明錄，崔承毅.基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)修正加權(quán)質(zhì)心定位算法［J］.傳感技術(shù)學(xué)報(bào)，2010，23（5）：717-721.

LIU Yunjie，JIN Minglu，CUI Chengyi.Modified Weight?ed Centroid Localization Algorithm Based on RSSI for WSN［J］.Chinese Journal of Sensors and Actuators，2010，23（5）：717-721.

［19］陳昌祥，達(dá)維，周潔，等.基于RSSI的無(wú)線傳感器網(wǎng)絡(luò)距離修正定位算法［J］.通信技術(shù)，2011，44（2）：65-66，69.

CHEN Changxiang，DA Wei，ZHOU Jie，et al.RSSI-based Range Collation Localization Algorithm in WSN［J］.Communications Technology，2011，44（2）：65-66，69.

［20］朱忠記，何熊熊，章曉，等.基于RSSI的四邊測(cè)距改進(jìn)加權(quán)質(zhì)心定位算法［J］.杭州電子科技大學(xué)學(xué)報(bào)，2014，34（1）：17-20.

ZHU Zhongji，HE Xiongxiong，ZHANG Xiao，et al.The Quadrilateral and Improved Weighted Centroid Localiza?tion Algorithm Based on RSSI［J］.Journal of Hangzhou Dianzi University，2014，34（1）：17-20.

［21］王振朝，張琦，張峰，等.基于RSSI測(cè)距的改進(jìn)加權(quán)質(zhì)心定位算法［J］.電測(cè)與儀表，2014，51（21）：63-66.

WANG Zhenchao，ZHANG Qi，ZHANG Feng，et al.Im?proved Weighted Centroid Positioning Algorithm Based on RSSI Ranging［J］.Electrical Measurement&Instru?mentation，2014，51（21）：63-66.