基于模糊邏輯的WSN節(jié)點(diǎn)自定位算法

段同樂，張冬寧，劉文展

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

?

基于模糊邏輯的WSN節(jié)點(diǎn)自定位算法

段同樂，張冬寧，劉文展

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

摘要：對無線傳感器定位方法進(jìn)行了研究，為節(jié)約成本、提高算法實(shí)用性和準(zhǔn)確性，提出一種基于RSS和模糊邏輯的WSN節(jié)點(diǎn)自定位方法。該方法中一個移動未知節(jié)點(diǎn)采集信標(biāo)節(jié)點(diǎn)廣播的自身定位信息及其對應(yīng)的RSS信號，構(gòu)成已知條件，結(jié)合對信標(biāo)節(jié)點(diǎn)的六邊形網(wǎng)格劃分、RSS向量唯一性定理和模糊數(shù)學(xué)中的測度貼近度計(jì)算方法設(shè)計(jì)實(shí)現(xiàn)了基于模糊邏輯的WSN節(jié)點(diǎn)自定位算法。理論分析表明，該算法能夠以較低的計(jì)算開銷滿足WSN節(jié)點(diǎn)常規(guī)精度的定位要求，具有較好的實(shí)用性和準(zhǔn)確性。

關(guān)鍵詞：WSN；自定位；RSS；模糊邏輯

0引言

位置信息是無線傳感器網(wǎng)絡(luò)(WSN)應(yīng)用中需要的一項(xiàng)重要內(nèi)容，它是地理路由和網(wǎng)絡(luò)管理等系統(tǒng)功能的必要基礎(chǔ)信息。在緊急醫(yī)療救助和戰(zhàn)場態(tài)勢偵測等應(yīng)用中，位置信息對這些應(yīng)用的實(shí)施效果起到至關(guān)重要的作用。比如在突發(fā)性災(zāi)難發(fā)生時，災(zāi)難現(xiàn)場區(qū)域廣大，現(xiàn)場混亂，如果能夠在救助中明確傷患者的位置并進(jìn)行顯示，一方面有利于快速、便捷地對傷患者進(jìn)行緊急救治，另一方面有利于救援整體情況的查看和把握，使調(diào)度人員能夠?qū)崟r地了解現(xiàn)場狀況，合理決策，精準(zhǔn)調(diào)度。

鑒于位置信息的重要性，當(dāng)前已經(jīng)有很多關(guān)于定位算法的研究。這些研究中，根據(jù)定位對象的不同，主要分為WSN自身定位和WSN目標(biāo)定位兩類。前者關(guān)注于WSN部署后，根據(jù)其中某些已知位置的節(jié)點(diǎn)(錨節(jié)點(diǎn))來求得其他需要定位的節(jié)點(diǎn)(未知節(jié)點(diǎn))的位置。這一類的定位問題一般也是WSN目標(biāo)定位的依據(jù)和基礎(chǔ)。

已有的WSN自身定位算法可以根據(jù)不同的方式進(jìn)行分類。依據(jù)定位所需信息的粒度可將定位算法和系統(tǒng)分為細(xì)粒度定位和粗粒度定位兩類，前者根據(jù)信號強(qiáng)度或時間等參數(shù)來度量未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的相對位置，結(jié)果較精準(zhǔn)，但所需的代價和運(yùn)算量較大；后者根據(jù)與已知位置的接近度來度量，結(jié)果往往是一個范圍，但所需代價較少，較著名的有Active Badge[1]和凸規(guī)劃[2]等。在很多應(yīng)用中，獲知節(jié)點(diǎn)所在范圍已經(jīng)能夠滿足分簇、位置路由等操作的位置信息需求，且代價較小，有助于延長網(wǎng)絡(luò)壽命。另外，根據(jù)定位算法是否需要進(jìn)行測距，可以分為基于測距技術(shù)(range-based)的定位和無須測距技術(shù)(range-free)的定位兩類[3]，前者通過RSS(received signal strength)[4]、TOA(time of arrival)[5]等測距技術(shù)，運(yùn)用三邊測量、三角測量和最大似然估計(jì)等定位法求得節(jié)點(diǎn)位置[6]，一般定位精度較高，但這些算法中多采用多次測量和循環(huán)定位求精等[7]，導(dǎo)致大量計(jì)算和通信開銷；后者無須距離和角度信息，僅根據(jù)網(wǎng)絡(luò)連通性等信息來實(shí)現(xiàn)，開銷大大減少，更適用于低功耗和低成本的應(yīng)用領(lǐng)域。但目前基于TOA測距的算法對TOA受設(shè)備計(jì)時精度的影響討論較少，無法明確利用無線信號的TOA測距的限制。

1普通節(jié)點(diǎn)定位算法流程

普通節(jié)點(diǎn)(N-Nds)的定位是利用RSS值，通過基于模糊邏輯算法實(shí)現(xiàn)的。N-Nd定位算法流程如圖1所示。在A-Nd定位階段，所有的A-Nd依靠自身裝備的GPS模塊確定自身位置。由于節(jié)點(diǎn)的部署區(qū)域是以固定的六邊形網(wǎng)格方式進(jìn)行劃分的[8]，A-Nd在確定自身位置后能夠判斷自身處于哪個網(wǎng)格。在N-Nd定位階段，A-Nd周期性廣播N-Nd定位信號。所有的N-Nd接收N-Nd定位信號，并通過基于模糊邏輯的粗粒度定位算法估算自身的大概位置。該算法將在下節(jié)進(jìn)行詳細(xì)介紹。上述流程重復(fù)進(jìn)行若干次，從而減少由于信號傳播受到的干擾帶來的誤差。

圖1　N-Nd定位算法流程

2基于模糊邏輯的粗粒度定位算法

在N-Nd定位階段，A-Nd周期性廣播N-Nd定位信號[9]。設(shè)一個普通節(jié)點(diǎn)C可收到A1、A2…ANf共Nf個錨節(jié)點(diǎn)廣播的內(nèi)部定位信號，如圖2所示，錨節(jié)點(diǎn)的坐標(biāo)(xA1,yA1)，(xA2,yA2)…，(xANf,yANf)，(xO,yO)均為已知，且它們的自身坐標(biāo)均包含在其廣播的N-Nd定位信號中。此外，N-Nd定位信號中還包含該信號的發(fā)射功率值。

圖2　普通節(jié)點(diǎn)定位用例

可以證明下述定理：

定理1：在一個區(qū)域內(nèi)，某個點(diǎn)對應(yīng)于3個以上非共線的信標(biāo)節(jié)點(diǎn)所形成的RSS向量唯一地對應(yīng)于該點(diǎn)坐標(biāo)。

證明：在如圖2所示情況中，取Nf=2，即3個信標(biāo)節(jié)點(diǎn)，A1、A2、A3與C的距離為dA1、dA2和dA3。

取無線信號傳播的對數(shù)-常態(tài)分布模型：

(1)

式中，n為路徑損耗指數(shù)，范圍在2~6之間；d0為近地參考距離，通過測試獲得；Xσ為表示誤差的均值為0的高斯隨機(jī)變量。另外有：

RSS(d)=PT-PL(d),

(2)

式中，PT為發(fā)射功率，節(jié)點(diǎn)i接收到N-Nd定位信號，由于發(fā)射功率和接收功率為已知，因此可據(jù)發(fā)射和接收功率的差值求出這些信號的RSS值，根據(jù)RSS值可求出節(jié)點(diǎn)C和A-Nd之間距離的估計(jì)值：

(3)

通過C接收到的相應(yīng)的內(nèi)部定位信號RSS值，利用式(3)可得到方程組：

(4)

可知當(dāng)A1、A2和A3非共線時，方程組(4)的解唯一，且當(dāng)Nf>2時，得到的超定方程組解也唯一。定理1得證。

在本算法中，所有節(jié)點(diǎn)根據(jù)前述過程，可以求得自身的粗略位置，據(jù)此可以對自身所處的網(wǎng)格進(jìn)行初步判斷，節(jié)點(diǎn)可大致估計(jì)出自身所處網(wǎng)格區(qū)域，將該網(wǎng)格區(qū)域及其n級相鄰的網(wǎng)格區(qū)域作為一個定位區(qū)域，將這些網(wǎng)格區(qū)域的6個頂點(diǎn)及中心點(diǎn)作為參照點(diǎn)，根據(jù)預(yù)先定義的六邊形網(wǎng)格半徑r，可求出這Ns個參照點(diǎn)的坐標(biāo)。n級相鄰節(jié)點(diǎn)與某個網(wǎng)格區(qū)域之間相鄰間隔的大小，以圖2中的0號區(qū)域?yàn)槔?級相鄰區(qū)域?yàn)榕c其直接相鄰的1~6號區(qū)域，2級相鄰區(qū)域增加了與1~6號直接相鄰的7~18號區(qū)域。

n的取值根據(jù)網(wǎng)格區(qū)域劃分中確定的網(wǎng)格大小，即r值確定，關(guān)系如下：

(5)

由n可求得定位區(qū)域的網(wǎng)格數(shù)目Ns：

NS=9n2+15n+7。

(6)

取n=1，則Ns=31，不同參照點(diǎn)處收到的來自信標(biāo)節(jié)點(diǎn)的內(nèi)部定位信號RSS組成的向量均不相同[10]，所有參照點(diǎn)的RSS向量組成向量表：

(7)

式中，RSSINsAj的求法如下：

首先根據(jù)參照點(diǎn)i的坐標(biāo)(xi,yi)，求得i與信標(biāo)節(jié)點(diǎn)Aj的距離：

(8)

再根據(jù)式(1)和式(2)求得RSSIiAj。

C收到的來自A1、A2、…ANf、O的內(nèi)部定位信號RSS組成向量：

(9)

根據(jù)模糊數(shù)學(xué)中的測度貼近度計(jì)算方法[11]，利用最大值、最小值貼近度公式計(jì)算貼近度：

(10)

式中，“∧”為取小運(yùn)算，“∨”為取大運(yùn)算。求得C與各個參照點(diǎn)的貼近度序列：

S={s1,s2,…,sNs}。

(11)

之后對S進(jìn)行排序，并取其中貼近度最大的3個參照點(diǎn)坐標(biāo)。可以證明，這3個參照點(diǎn)其質(zhì)心位置為C的定位結(jié)果：

(12)

進(jìn)行M次迭代后，得到M個定位結(jié)果，求這些結(jié)果的平均值，得到最終定位結(jié)果。

3算法復(fù)雜度和精度分析

整個計(jì)算過程中沒有出現(xiàn)高次方程求解，只有一些簡單的大小比較計(jì)算，計(jì)算復(fù)雜度為O(MNs)。

節(jié)點(diǎn)定位精度受網(wǎng)格區(qū)域的大小和參照點(diǎn)數(shù)量的影響。精度定義ρ如下：

(13)

式中，derr為所有節(jié)點(diǎn)定位位置與真實(shí)位置間的平均距離。當(dāng)干擾一定時，參照點(diǎn)數(shù)目NS越大，定位精度越高[12]。而根據(jù)式(5)和式(6)可知，r減小時，n緩慢增加，而NS會隨n而急劇增加。在干擾較小的情況下，當(dāng)NS=66時，精度可穩(wěn)定在0.995 9。當(dāng)相鄰級別n=2時，可求得NS=72，因此一般取n≤2即可滿足大部分定位需求，因此一般至少取r=rmax/2。

4結(jié)束語

提出了一種基于RSS和模糊邏輯算法的WSN節(jié)點(diǎn)自定位方法。相比其他定位算法，本算法利用合適的六邊形網(wǎng)格劃分，采集所有信標(biāo)節(jié)點(diǎn)位置信息和RSS，結(jié)合使用模糊數(shù)學(xué)中的測度貼近度計(jì)算方法，利用基于模糊邏輯的粗粒度定位算法估算自身的大概位置。理論分析證明，所提算法降低了計(jì)算復(fù)雜度，減少了計(jì)算開銷，節(jié)約了成本，提高了定位精度，增強(qiáng)了算法的實(shí)用性。

參考文獻(xiàn)

[1]Want R,Hopper A,Falcao V,et al.The Active Badge Location System.ACM Trans.on Information Systems[J].1992,10(1):91-102.

[2]Doherty L.Algorithms for Position and Data Recovery in Wireless Sensor Networks[MS.Thesis].Berkeley:University of California,2000.

[3]左冬梅.無線傳感器網(wǎng)絡(luò)安全定位技術(shù)研究[D]．哈爾濱：哈爾濱工程大學(xué)，2011，30-35.

[4]Girod L,Bychovskiy V,Elson J,etal.Locating tiny Sensors in Time and Space:A Case Study[C]∥In:Werner B,ed.Proc.of the 2002 IEEE Int’l Conf.on Computer Design:VLSI in Computers and Processors.Freiburg:IEEE Computer Society,2002:214-219.

[5]Harter A,Hopper A,Steggles P,Ward A,Webster P.The Anatomy of a Context-aware Application[C]∥In:Proc.of the 5th Annual ACM/IEEE Int’l Conf.on Mobile Computing and Networking.Seattle:ACM Press,1999:59-68.

[6]王琰,王喆.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究[J].無線電通信技術(shù),2011,37(5):21-23,27.

[7]王輝,熊飛,谷源濤.移動Mesh網(wǎng)絡(luò)定位系統(tǒng)研究[J].無線電通信技術(shù),2012,38(1):12-15.

[8]任明明,謝志軍,金光,等.傳感網(wǎng)絡(luò)中基于移動信標(biāo)的網(wǎng)格掃描定位算法[J].無線電通信技術(shù),2014,40(2):4-6,59.

[9]楊小勇,楊榮,李彬.一種新型無線傳感器網(wǎng)絡(luò)分布式定位算法[J].無線電通信技術(shù),2012,38(3):14-17.

[10]郭龍,熊偉,李牧東.一種基于WSN的機(jī)器人三維精確定位算法[J].無線電工程,2012,42(8):5-7.

[11]Janusz Kacprzyk,Fuzzy reasoning in decision making and optimization[M].Berlin Heidelberg:Springer-Verlag,2002.

[12]高霞,高勇.基于基準(zhǔn)線概率密度的多站多目標(biāo)定位[J].無線電工程,2011,41(9):18-20,33.

WSN Node Self-localization Algorithm Based on Fuzzy Logic

DUAN Tong-le,ZHANG Dong-ning,LIU Wen-zhan

(The 54th Research Institute of CECT,Shijiazhuang Hebei 050081,China)

Abstract：The localization method of wireless sensor network is discussed.Aiming at saving cost and improving its practicability and veracity,a method of wireless sensor network node self-localization based on RSS and fuzzy logic is proposed.In this method,an unknown mobile node collects self-localization information and corresponding RSS signals which beacon nodes broadcast to compose the precondition.By integrating hexagon grid partition of beacon node,uniqueness theorem of RSS vector and algorithm of approximate estimate from fuzzy mathematics,the method of wireless sensor node self-localization based on RSS and fuzzy logic is designed and realized.The theoretical analysis results show that the proposed method can provide fine location accuracy with a relative low computing cost,and it has higher practicality and veracity.

Key words：WSN;self-localization;RSS;fuzzy logic

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

文章編號：1003-3114(2016)02-48-3

作者簡介：段同樂(1975—)，男，高級工程師，主要研究方向：智能信息處理。

收稿日期：2015-11-26

doi:10.3969/j.issn.1003-3114.2016.02.12

引用格式：段同樂，張冬寧，劉文展.基于模糊邏輯的WSN節(jié)點(diǎn)自定位算法[J].無線電通信技術(shù),2016,42(2):48-50,65.