普适环境下基于区间值模糊理论的指纹定位算法

钱梦竹,杨新凯

(上海师范大学 信息与机电工程学院,上海 200234)

1 背景简介

自Weiser[1-3]于1991年首次提出了一个新的计算时代——普适计算时代,到目前,有关普适计算的研究也越来越多,它最主要的特点就是将计算变成了以人为中心,而不是以计算机为中心的计算,将传统的计算设备溶入生活中,即计算机既对人们“隐身”而又“无处不在”.用户和计算机之间将以一种很自然的方式进行交流.当然,这也就使得普适计算成为现今乃至未来计算的主流.

普适计算针对的主要数据对象是上下文信息,上下文[4]就是能用来描述实体状态的信息,它可以是人、时间、位置或者它们之间的相互关系等.其中位置上下文是非常重要的一类上下文信息,它是连接虚拟和现实世界的桥梁[5].因此,定位系统的研究也就成了普适计算的重要研究课题之一.定位可定义为是一种确定实体之间位置关系的机制.而定位系统就是通过相关的设备获取系统的空间方位属性,然后运用一些算法确定位置信息.而本文作者主要研究的是普适计算环境下室内无线定位[6]技术,它主要是依据接收到的无线电信号的时间、强度、相位等参数,通过一定的算法来计算移动用户的位置.

2 普适环境下的室内定位系统简介

目前,普适计算环境下的室内定位系统种类繁多并且差异很大,但其一般的框架是相同的,可大体分为信号测量、位置估算和位置求精这3个阶段.

2.1 信号测量阶段

第一个阶段是信号测量阶段,首先通过一些信号媒体测出未知节点与参考点之间的距离或角度关系,进而估算两节点之间的直线距离.目前的信号测量技术主要有4种,分别是TOA、TDOA、AOA、RSSI,前3种技术对设备的要求都比较高,像TOA是通过测量两点之间的传播时间来确定距离,那么就会产生时钟同步误差和传播不均的误差,对精度影响较大.TDOA虽然消除了DOA产生的误差,但是仍对时钟同步的要求很高.AOA的定位精度则会受天线测角精度影响.而RSSI技术利用信号衰减原理.通过检测信号接收端的接收功率,得到传播耗损模型,计算节点间的距离.由于是利用无线网络技术,因此成本较低,所以本文作者选用在WiFi环境下测量RSSI值(Received Signal Strength Indicator)的方法来进行信号测量,确定待测定节点的坐标[7].

2.2 位置估算阶段

第2个阶段是位置估算阶段,知道了未知节点到3个(或3个以上)参考点的距离,就可以用定位估算的方法来确定未知节点的坐标.一般在三维空间中,需要知道到4个参考点的距离[8],例如全球定位系统(GPS),但是在普适计算的环境下,坐标系大多是二维空间,只需要知道到3个参考点的距离就可以确定定位点的坐标.位置估算的方法主要分为3种:三边测量法、场景分析和附近定位.

2.3 位置求精阶段

第3个阶段是位置求精阶段,也是作者重点研究的阶段,本阶段要对求得的节点坐标进行位置求精,尽可能地减少误差,提高定位精度.该阶段的算法种类很多,由于WiFi具有部署方便、高速的特点,并且目前在笔记本电脑、手机等通信设备上都得到广泛应用.由于基于WiFi的室内定位算法具有数据高维的特性、信号本身的不稳定性、测量本身的误差，使得定位过程中所使用的数据没有固定的属性,也就是说具有模糊性,因此对该过程中的模糊性进行探究,引入区间值模糊理论,在原有的基于WiFi的指纹定位算法[9]的基础上,提出了一种基于区间值模糊理论的指纹定位算法.

3 基于区间值模糊理论的指纹定位算法

WiFi无线局域网技术从20世纪末开始发展,目前应用最广泛的是IEEE 802.11系列技术标准.基于WiFi的室内定位系统主要包括3个部分:终端无线网卡、位置固定的WiFi热点和定位平台.本系统采用基于信号强度的指纹定位技术.在算法实施上分为离线和在线两个阶段:离线阶段基于区间值模糊理论建立模糊指纹库;在线阶段对客户端进行实时模糊决策定位.其一般模型如图1所示.

图1 基于WiFi的室内定位离线建库阶段原理图

3.1 模糊指纹库的建立

首先,将整个区域划分网格(正方形),它们的的位置用xOy坐标轴在数据库中标定,把固定的节点安装在已知的坐标上,然后在每个网格中收集RSSI值并与它的坐标一起存入数据库.这个阶段是非常费时的.

为了算法的精确,至少需要设置3个固定节点(作者选取了4个固定节点)并且以相同的方法计算指纹(三边测量法),移动终端与固定节点之间的距离是已知的,由无线电传播模型计算得到[10].

将离线阶段4个固定节点测得的每一个参考点的RSSI值,记为xi(1≤xi≤n),n为定位区域内设置参考点的数目,即xi=(R1i,R2i,R3i,R4i)，其中xi为样本点,R为测得的RSSI值,设指纹库的样本空间为X={x1,x2,…,xn},注意一个样本点不能被严格地划分给某一个区间,定义样本点xi属于第j个区间的程度为xij(0≤xij≤1),其中xij为模糊隶属度,1≤j≤c,c为模糊区间数,样本空间X的模糊区间用模糊矩阵W=(wij)表示,其中wij为矩阵W的第i行第j列元素,代表第i个样本点隶属于第j个区间的隶属度.W具有以下性质:

wijwij∈[0,1] ，

(1)

(2)

(3)

(4)

定义目标函数为Jλ(w,z),则:

(5)

(6)

(7)

式中,λ为模糊指数,λ>1,zj表示第j个区间的区间中心,式(6)表示样本点xi到区间中心zj的线距离.模糊区间的划分计算目标函数在(1)～(3)式的约束条件下的最小值.其流程图如图2所示.

图2 确定模糊区间的算法流程

通过图2的迭代过程,可以完成对于离线阶段采集的RSSI值的模糊区间的划分:共分为n个区间,每个区间中都有k(1≤k≤n)个样本值,且第j个区间中心为zj.这n个区间的数据一起构成了本定位系统的模糊指纹库.该指纹库详细描述了特定环境中无线信号的RSSI值与空间位置之间的对应关系并存储在中心服务器中.

3.2 模糊决策定位

该阶段定位系统开始监控移动设备并收集RSSI指纹.进行匹配指纹,并储存下RSSI的值.如果获得的测量值与存储的指纹相匹配,就实现了定位.本算法计算的是最邻近的数值,如果对应的坐标有两个,那么就用两坐标的平均值来表示.把指纹匹配问题类比于模糊决策的问题,并运用模糊决策理论进行建模,来获得更为准确的定位结果,并且增强了室内定位系统的抗干扰能力.

在线阶段,首先进行区间的匹配,将测得的移动端的4组RSSI值记为xm(m≥1的整数,x表示第m个移动客户端),即xm={r1m,r2m,r3m，r4m},其中r表示在线阶段测得的RSSI值.通过计算得到的xm和数据库中c个区间的模糊隶属度,然后,选取最大模糊隶属度所对应的第j个区间,并在此区间中进行模糊决策,实现移动客户端位置的确定.

分别计算实际测量得到的xm中的4个数值,以及指纹库第j个区间个参考值xi中对应的4个数值之间的欧式距离vpq,vpq为因素指标值,即

vpq=|rlm-Rli|,l=1,2,3,4 .

(8)

把计算所得的所有因素指标值构成如下的因素指标矩阵:

(9)

计算相对偏差值μpq,即

(10)

(11)

根据具体的情况设定一个门限值θ,令

(12)

选取dp≤θ时的K个值所对应的参考点,然后,根据式(13)计算其对应坐标的平均值,作为移动客户端的估算位置:

(13)

设移动客户端的实际位置坐标为(x′,y′)和估算位置坐标(x,y)之间的距离为其定位误差,用Δ表示:

(14)

Δ的大小可以评估定位系统的性能,Δ的值越小,则说明系统的性能越好.

4 实 验

在一个300 m2的楼层的4个位置固定上4个无线接入点(AP,Access Point),采用IEEE 802.11标准的移动设备,构建一个基于区间值模糊理论的WiFi室内定位系统实验平台.

图3是楼层的结构图,黑色的虚线表示实验路径,黑点表示参考点,间隔大约为5 m,用模糊理论的方法建立指纹库;移动端沿着实验路径约1 m/s的速度收集AP的RSSI值,进行WiFi定位,如图3所示.

通过图4和图5的对比,可以看出加入了区间值模糊理论,定位路径更加接近真实的实验路径,定位精度提高了很多.

图3 试验路径图

图4 传统的指纹定位图

图5 基于区间值模糊理论的指纹定位图

5 结束语

在普适计算的环境下,本文作者提出了一种基于区间值模糊理论的高精度、低开销的实时指纹定位算法.该算法选取无线环境(WiFi)下的RSSI值作为参数,分两个阶段来实现室内定位:离线模糊建库阶段和在线实时模糊决策阶段来实现对移动客户端位置的确定.并通过对比发现,该算法具有更高的定位精度和可靠性,为普适计算环境下的各类研究提供更为精确的位置上下文信息.

参考文献:

[1] WEISER M.The computer for the twenty first century[J].Scientific American,1991,265(3):94-104.

[2] WEISER M.Some computer science issues in ubiquitous computing[J].Communications of the ACM,1993,36(7):74-78.

[3] WEISER M.Hot topics-ubiquitous computing[J].IEEE computer,1993,26(10):71-72.

[4] WEI L,XUE L,DAO L H.A survey on context awareness[C].Computer science and Science system(CSSS) International Conference,Nanjing:IEEE,2011.

[5] ESTRIN D,CULLER D,PRISTER K,et al.Connecting the physical world with pervasive network[J].Pervasive Computing,2002,1(11):59-69.

[6] 付维权,孙志仁,曹奇英. 普适计算及其定位感知系统[J].计算机工程与设计,2004,25(7):1200-1203.

[7] ABOODI A,WAN T.Evalution of WiFi-based indoor(WBI) positioning algorithm[C].Moblie Ubiquitous and Interlligent Computing(MUSIC) Third FTRA International Conference,Vancouver BC:IEEE,2012.

[8] HIGHTOWER J,BORRIELLO G,WANT R.Spot ON:An Indoor 3D location sensing technology based on RF singal strenghth[R].Techical Report UW CSE Seattle WA,USA:University of Washington,2000:1-16.

[9] SABHAN F,HASBULLAH H,et al.Tndoor positioning inBluetooth networks using fingerprinting and lateration approach[C].International Conference on Information Science and Applications International Conference,Jeju Island:IEEE,2011.

[10] LIU H,DARABI H,BANERJEE P,et al.Survey of wireless indoor positioning techniques and systems[J].IEEE Transcations on System Man and Cybernetics Part C:Applications and Reviews,2007,37(6):1067-1080.