基于模糊逻辑的WSN节点自定位算法

段同乐，张冬宁，刘文展

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)



基于模糊逻辑的WSN节点自定位算法

段同乐，张冬宁，刘文展

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

摘要：对无线传感器定位方法进行了研究，为节约成本、提高算法实用性和准确性，提出一种基于RSS和模糊逻辑的WSN节点自定位方法。该方法中一个移动未知节点采集信标节点广播的自身定位信息及其对应的RSS信号，构成已知条件，结合对信标节点的六边形网格划分、RSS向量唯一性定理和模糊数学中的测度贴近度计算方法设计实现了基于模糊逻辑的WSN节点自定位算法。理论分析表明，该算法能够以较低的计算开销满足WSN节点常规精度的定位要求，具有较好的实用性和准确性。

关键词：WSN；自定位；RSS；模糊逻辑

0引言

位置信息是无线传感器网络(WSN)应用中需要的一项重要内容，它是地理路由和网络管理等系统功能的必要基础信息。在紧急医疗救助和战场态势侦测等应用中，位置信息对这些应用的实施效果起到至关重要的作用。比如在突发性灾难发生时，灾难现场区域广大，现场混乱，如果能够在救助中明确伤患者的位置并进行显示，一方面有利于快速、便捷地对伤患者进行紧急救治，另一方面有利于救援整体情况的查看和把握，使调度人员能够实时地了解现场状况，合理决策，精准调度。

鉴于位置信息的重要性，当前已经有很多关于定位算法的研究。这些研究中，根据定位对象的不同，主要分为WSN自身定位和WSN目标定位两类。前者关注于WSN部署后，根据其中某些已知位置的节点(锚节点)来求得其他需要定位的节点(未知节点)的位置。这一类的定位问题一般也是WSN目标定位的依据和基础。

已有的WSN自身定位算法可以根据不同的方式进行分类。依据定位所需信息的粒度可将定位算法和系统分为细粒度定位和粗粒度定位两类，前者根据信号强度或时间等参数来度量未知节点与锚节点的相对位置，结果较精准，但所需的代价和运算量较大；后者根据与已知位置的接近度来度量，结果往往是一个范围，但所需代价较少，较著名的有Active Badge[1]和凸规划[2]等。在很多应用中，获知节点所在范围已经能够满足分簇、位置路由等操作的位置信息需求，且代价较小，有助于延长网络寿命。另外，根据定位算法是否需要进行测距，可以分为基于测距技术(range-based)的定位和无须测距技术(range-free)的定位两类[3]，前者通过RSS(received signal strength)[4]、TOA(time of arrival)[5]等测距技术，运用三边测量、三角测量和最大似然估计等定位法求得节点位置[6]，一般定位精度较高，但这些算法中多采用多次测量和循环定位求精等[7]，导致大量计算和通信开销；后者无须距离和角度信息，仅根据网络连通性等信息来实现，开销大大减少，更适用于低功耗和低成本的应用领域。但目前基于TOA测距的算法对TOA受设备计时精度的影响讨论较少，无法明确利用无线信号的TOA测距的限制。

1普通节点定位算法流程

普通节点(N-Nds)的定位是利用RSS值，通过基于模糊逻辑算法实现的。N-Nd定位算法流程如图1所示。在A-Nd定位阶段，所有的A-Nd依靠自身装备的GPS模块确定自身位置。由于节点的部署区域是以固定的六边形网格方式进行划分的[8]，A-Nd在确定自身位置后能够判断自身处于哪个网格。在N-Nd定位阶段，A-Nd周期性广播N-Nd定位信号。所有的N-Nd接收N-Nd定位信号，并通过基于模糊逻辑的粗粒度定位算法估算自身的大概位置。该算法将在下节进行详细介绍。上述流程重复进行若干次，从而减少由于信号传播受到的干扰带来的误差。

图1　N-Nd定位算法流程

2基于模糊逻辑的粗粒度定位算法

在N-Nd定位阶段，A-Nd周期性广播N-Nd定位信号[9]。设一个普通节点C可收到A1、A2…ANf共Nf个锚节点广播的内部定位信号，如图2所示，锚节点的坐标(xA1,yA1)，(xA2,yA2)…，(xANf,yANf)，(xO,yO)均为已知，且它们的自身坐标均包含在其广播的N-Nd定位信号中。此外，N-Nd定位信号中还包含该信号的发射功率值。

图2　普通节点定位用例

可以证明下述定理：

定理1：在一个区域内，某个点对应于3个以上非共线的信标节点所形成的RSS向量唯一地对应于该点坐标。

证明：在如图2所示情况中，取Nf=2，即3个信标节点，A1、A2、A3与C的距离为dA1、dA2和dA3。

取无线信号传播的对数-常态分布模型：

(1)

式中，n为路径损耗指数，范围在2~6之间；d0为近地参考距离，通过测试获得；Xσ为表示误差的均值为0的高斯随机变量。另外有：

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

(2)

式中，PT为发射功率，节点i接收到N-Nd定位信号，由于发射功率和接收功率为已知，因此可据发射和接收功率的差值求出这些信号的RSS值，根据RSS值可求出节点C和A-Nd之间距离的估计值：

(3)

通过C接收到的相应的内部定位信号RSS值，利用式(3)可得到方程组：

(4)

可知当A1、A2和A3非共线时，方程组(4)的解唯一，且当Nf>2时，得到的超定方程组解也唯一。定理1得证。

在本算法中，所有节点根据前述过程，可以求得自身的粗略位置，据此可以对自身所处的网格进行初步判断，节点可大致估计出自身所处网格区域，将该网格区域及其n级相邻的网格区域作为一个定位区域，将这些网格区域的6个顶点及中心点作为参照点，根据预先定义的六边形网格半径r，可求出这Ns个参照点的坐标。n级相邻节点与某个网格区域之间相邻间隔的大小，以图2中的0号区域为例，其1级相邻区域为与其直接相邻的1~6号区域，2级相邻区域增加了与1~6号直接相邻的7~18号区域。

n的取值根据网格区域划分中确定的网格大小，即r值确定，关系如下：

(5)

由n可求得定位区域的网格数目Ns：

NS=9n2+15n+7。

(6)

取n=1，则Ns=31，不同参照点处收到的来自信标节点的内部定位信号RSS组成的向量均不相同[10]，所有参照点的RSS向量组成向量表：

(7)

式中，RSSINsAj的求法如下：

首先根据参照点i的坐标(xi,yi)，求得i与信标节点Aj的距离：

(8)

再根据式(1)和式(2)求得RSSIiAj。

C收到的来自A1、A2、…ANf、O的内部定位信号RSS组成向量：

(9)

根据模糊数学中的测度贴近度计算方法[11]，利用最大值、最小值贴近度公式计算贴近度：

(10)

式中，“∧”为取小运算，“∨”为取大运算。求得C与各个参照点的贴近度序列：

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

(11)

之后对S进行排序，并取其中贴近度最大的3个参照点坐标。可以证明，这3个参照点其质心位置为C的定位结果：

(12)

进行M次迭代后，得到M个定位结果，求这些结果的平均值，得到最终定位结果。

3算法复杂度和精度分析

整个计算过程中没有出现高次方程求解，只有一些简单的大小比较计算，计算复杂度为O(MNs)。

节点定位精度受网格区域的大小和参照点数量的影响。精度定义ρ如下：

(13)

式中，derr为所有节点定位位置与真实位置间的平均距离。当干扰一定时，参照点数目NS越大，定位精度越高[12]。而根据式(5)和式(6)可知，r减小时，n缓慢增加，而NS会随n而急剧增加。在干扰较小的情况下，当NS=66时，精度可稳定在0.995 9。当相邻级别n=2时，可求得NS=72，因此一般取n≤2即可满足大部分定位需求，因此一般至少取r=rmax/2。

4结束语

提出了一种基于RSS和模糊逻辑算法的WSN节点自定位方法。相比其他定位算法，本算法利用合适的六边形网格划分，采集所有信标节点位置信息和RSS，结合使用模糊数学中的测度贴近度计算方法，利用基于模糊逻辑的粗粒度定位算法估算自身的大概位置。理论分析证明，所提算法降低了计算复杂度，减少了计算开销，节约了成本，提高了定位精度，增强了算法的实用性。

参考文献

[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]左冬梅.无线传感器网络安全定位技术研究[D]．哈尔滨：哈尔滨工程大学，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]王琰,王喆.无线传感器网络节点定位算法研究[J].无线电通信技术,2011,37(5):21-23,27.

[7]王辉,熊飞,谷源涛.移动Mesh网络定位系统研究[J].无线电通信技术,2012,38(1):12-15.

[8]任明明,谢志军,金光,等.传感网络中基于移动信标的网格扫描定位算法[J].无线电通信技术,2014,40(2):4-6,59.

[9]杨小勇,杨荣,李彬.一种新型无线传感器网络分布式定位算法[J].无线电通信技术,2012,38(3):14-17.

[10]郭龙,熊伟,李牧东.一种基于WSN的机器人三维精确定位算法[J].无线电工程,2012,42(8):5-7.

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

[12]高霞,高勇.基于基准线概率密度的多站多目标定位[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

文献标识码：A

文章编号：1003-3114(2016)02-48-3

作者简介：段同乐(1975—)，男，高级工程师，主要研究方向：智能信息处理。

收稿日期：2015-11-26

doi:10.3969/j.issn.1003-3114.2016.02.12

引用格式：段同乐，张冬宁，刘文展.基于模糊逻辑的WSN节点自定位算法[J].无线电通信技术,2016,42(2):48-50,65.