基于信息准则的多跳无线定位方法

窦如林,方旭明,柳亚男

(金陵科技学院 软件工程学院,江苏 南京 211169)

随着第五代移动通信技术的逐渐普及,移动设备的位置信息变得越来越重要。移动终端的位置信息常为网络路由和覆盖、拓扑控制等提供技术支持[1-4]。无线定位技术一般可分为单跳定位和多跳定位[5]。单跳定位是指待定位节点直接与参考节点(已知位置的节点)通信,卫星定位是典型的单跳定位。统计数据[6]显示,人类有80%以上的时间是在复杂的封闭空间度过,如城市的楼宇、森林等。这种环境下卫星难以与移动终端直接连通,它们需要中继节点辅助进行信息交换。这种间接进行信息交换的定位方法被称为多跳定位。

在多跳定位中,未知节点首先获取到参考节点的相对位置关系,再通过无线网络交换信息和相互配合获得绝对位置信息。因此,依据是否用到距离测量技术又可分为基于测距定位方法和基于非测距定位方法[7]。基于测距定位方法需要在节点上安装特定的硬件,通过将无线信号转换成距离进而获知节点间相对位置关系。基于非测距定位方法不需要安装任何硬件设备,仅仅依靠节点之间的跳数关系,来估算节点间的距离。因此这种方法简单易于实现,对硬件要求相对较低,非常适合大规模场景下的定位应用。

针对不规则网络导致定位性能下降的问题,Shang等[8]提出一种改进DV-hop的算法,即利用到未知节点最近的4个参考节点来对未知节点进行定位估算(本文称此算法为Nearest-4算法)。该算法认为两节点之间跳数距离近,受网络不规则性影响较小。Gui等[9]提出了Selective-3算法,它依据节点间的链接度选择出3个锚节点,并用它们来估计未知节点的位置。Yan等[10]则认为,不规则网络导致节点间距离估计出现异方差问题,进而提出了一种Optimal weighted DV-hop(OWDV-hop)。OWDV-hop首先通过最优权函数消除异方差,然后在估计过程中通过节点几何关系消除估计模糊问题,从而保证定位结果最优。

借助智能算法对定位机制进行建模和设计,已成为近些年的研究热点之一。基于智能算法的定位,通过锚节点间的分布特性与测量信息的对应关系,关联并构建一个映射模型,而后运用该模型估计出未知节点的位置。基于智能算法的定位与以往方法相比较,它能有效地挖掘出数据背后所隐含的网络拓扑结构、相关性等信息,因而能有效地提升定位性能。Lee等[11]提出支持向量机回归定位(Localization through support vector regression,LSVR)。该方法认为,跳数与物理距离之间存在的关系是一种非线性关系。它们利用可支持向量机回归(Support vector regression,SVR)来预测节点间的距离。然而根据Occam’s razor原则[12],模型越是复杂,出现过拟合的几率也就越高。因此,基于SVR的定位方法会随着信标节点数量的增多出现过拟合现象,使得定位精度下降。此外,基于SVR方法还易产生过高的计算复杂度,且LSVR中涉及到的核函数中的核参数均为作者人为设置,造成算法对不同环境的适应性差。

本文受LSVR算法的启发,提出了基于信息准则的多跳无线定位算法(Information criterion-based multi-hop localization,IC-MHL)。IC-MHL首先在赤池信息准则(Akaike’s information criterion,AIC)[13]的帮助下,通过构建锚节点间的跳数与距离建立映射模型;将未知节点到锚节点的跳数输入到映射模型中,获取它们之间的估计距离;最后采用多边法获得未知节点的估计位置。

1 定位算法

1.1 网络模型

设有n节点随机部署在一个平面空间中,它们通过自组路由协议构成一个相互联通的网络,其中前m(m≪n)个节点是锚节点,剩余的n-m个节点为待定位的未知节点。令锚节点a(a∈{1,2,…,m})的真实坐标为ca=(xa,ya),未知节点u(u∈{m+1,m+2,…,n})的真实位置用cu=(xu,yu)来表示。不失一般性,可以对这些节点进行如下假设:

(1)所有节点都安装了全向天线,并且具有同样的发射能力,因此它们具有相同的通信半径r。

(2)节点的通信覆盖范围是以节点为圆心,r为半径的圆。

(3)节点间通过接收或转发消息的方式获得邻居节点的位置信息。假设i和j表示网络中任意两个相互连通的节点,dij表示两个节点之间的距离,dij定义如下

(1)

若节点j不在节点i的覆盖范围内,则通过其他中继节点转发信息来实现通信,转发的中继节点数即它们之间的跳数。通常为了保证通信的能效最低,算法会选择跳数最小的那条链路。

令h(i,j)=hij{0,1,2,…}表示节点i到节点j的最小跳数。节点i与网络中其余连通节点的最小跳数向量为hi=[hi1,hi2,…,hin]T,则整个网络节点间的最小跳数矩阵为H=[h1,h2,…,hn]。至此,多跳定位问题也可被抽象为在锚节点的坐标ca和锚节点a到未知节点u之间的跳数hau的约束下,求解未知节点u的估计坐标的过程。其中,锚节点到未知节点距离估计过程,可以抽象为一个映射函数其中表示锚节点a到未知节点u的估计距离。定位算法的期望是节点u的估算位置尽可能趋近于cu。

1.2 基于信息准则的多跳定位

IC-MHL方法的节点定位分三个阶段:数据收集阶段、模型建立阶段和位置估计阶段。

阶段1:数据收集

在数据采集阶段,程序收集节点间的跳数和距离信息,提供给模型建立阶段使用。对于整个网络而言,任意点i,i∈{1,2,…,m}向网络中其余节点广播消息。消息中包含该节点的编号和跳数信息,锚节点还包含坐标信息。在一段时间后,网络中每个节点都获得了与其他所有节点之间的最小跳数。因此在数据收集阶段需花费O(n2)的通信费用。

这样,网络中的任意锚节点都可以构造一个全局的、锚节点间的最短跳数矩阵H,以及锚节点间的距离矩阵D。

阶段2:建立映射模型

通过数据收集,任意锚节点a搜集到其余m-1个跳数和距离数据对(ha,dk,a),a=1,…,m∩k≠a。假设节点间距离估计的约束条件为一个映射函数f,

(2)

式中:θa为锚节点a到其余m-1个锚节点的映射模型,e为误差向量。

为了防止出现当网络规模、节点通信半径等因素的变化后,跳数与物理距离转换时,数量级不一致的问题,算法事先对数据对(ha,dk,a)进行了标准化处理。

图2为一个典型的多跳网络。假设a为源节点,b为目的节点。从图中的邻居关系可知a到b需经过节点1→2→3→4→5,如此节点间的跳数易存在相关性。因此,在跳数与距离转换过程中,跳数矩阵的向量间极易存在相关性。为了避免跳数矩阵各行(列)间存在相关性导致的病态问题(Ill-posed)[6,18],在模型建立过程中需要进行约束(即对模型进行惩罚)。

为此,对于整个网络而言,距离估计模型的目标函数应被写为

L(λ,θa)=‖da-Haθa‖2+λ‖θa‖2

(3)

式中:λ为惩罚参数,Ha是整个网络各个锚节点间最小跳数矩阵。因此跳数距离映射模型为

(4)

式中:惩罚参数λ的数值越大,那么惩罚项的作用就越明显;λ的数值越小,惩罚参数的作用就越弱。

当λ→0,则式(4)退化为一般最小二乘,图2中可以看出节点间存在着相关性,因此λ=0是不合适的。但如果λ→∞,则损失函数只有惩罚项,此时其最小化的结果必然是θa=0。由此可以看出,惩罚参数λ的选择是构建精准跳数与距离映射关系的关键。

AIC的定义如下

AIC=-2+2p

(5)

式中:p为参数个数,为似然函数,n为锚节点数。易知,单次计算式(5)的复杂度为O(1)。

具有工业价值的外生钼矿床主要有：(1)产于煤系地层中的钼矿床；(2)产于碳质粘土岩及碳、硅质粘土岩(即黑色页岩)中的钼矿床；(3)固体沥青页岩中的钼矿床等。这些外生钼矿床中，主要是与碳质有机成分密切相关，而且往往和铀、钒、锗等有用元素共生。但是由于其中含钼较贫而且赋存状态复杂，所以目前还未能有效提取，只能作为将来研究利用的对象。

文献[11]指出当AIC值最小时,所获得惩罚参数λ为最优。在算法运算过程中,通过Newton-Raphson方法迭代选择AIC值,直到其最小时为止。

阶段3:位置估计

(6)

当m≥3,算法就可以通过多边估计,以分布式的方式估计出自身的位置,其中多边估计的复杂度为O(m3)。图3描述的是整个算法的运行流程图。

2 性能分析

本节通过仿真实验来分析和评价IC-MHL的性能。实验对IC-MHL算法、Nearest-4[8]、Selective-3[9]、OW DV-hop[10]以及LSVR[11]进行了比较。由于LSVR需要设置核参数,但在原文中采用手工设置,这使得算法不具备自适应能力,为此本文采用文献[14]中自适应设置核参数方法。

仿真安排在MATLAB平台上进行,并假设节点随机均匀的部署在不规则拓扑中,节点间的通信模型采用圆盘模型,通信半径参照文献[5]设定为36。针对每种实验条件,仿真实验重复执行100次,然后对结果进行统计分析。仿真实验参数设置如表1所示。

表1 实验参数设置

为了公平起见,本文采用平均误差的开方(RMS)[5]作为平均定位误差的评价依据,RMS的定义如下

(7)

网络的不规则、锚节点数量、运行效率是评价定位算法性能的主要指标,因此本文对这三方面开展了性能评价和统计分析。

2.1 不规则网络的影响

图4(a)和(b)描述的为常被用于评测不规则网络定位性能的网络拓扑形状[8-11]。假设C、Z形网络中存在25个锚节点,它们与未知节点同一分布。图4(c)和(d)分别描述的是IC-MHL在C形和Z形网络中的定位结果。图4中,圆形表示未知节点的实际位置,菱形表示未知节点的估计位置,六角星表示信标节点,直线连接未知节点的真实坐标和它的估计坐标,直线越长,定位误差越大。从图4中可以看出,IC-MHL算法在不同的不规则网络中的定位精度高,估计位置很接近未知节点真实位置。

2.2 锚节点数量的影响

Nearest-4、Selective-3、OW DV-hop、LSVR以及本文所提的IC-MHL中都需要用锚节点估计出节点的每跳大概距离是多少,而在最终的位置估计中,还需要锚节点辅助估计出未知节点的估计位置。因此,锚节点的数量会对定位算法的性能有着至关重要的影响,本节通过设置不同数量的锚节点考察锚节点数目对平均定位误差的影响。

在本节的实验中,假设在不规则区域内信标节点的数目分别为10,15,…,40。如图5所示,本文采用箱形图(Boxplot)描述了100次试验后,不同锚节点数目所获得的平均定位误差分布不同。容易看出OW DV-hop、LSVR以及本文所提出的IC-MHL算法的RMS随着锚节点数量的增多,RMS中位数均单调递减,其中IC-MHL的精度最优,定位性能更稳定(箱形图的跨度较小)。Nearest-4和Selective-3在不同数量锚节点情况下,多次实验的RMS分布宽,且RMS的中位数并不随者锚节点数量的增多而降低,因此可以看出,Nearest-4和Selective-3并不是适合不规则网络中的位置估计。

2.3 运行时间比较

在本组实验中,本文比较了在不同锚节点数量、不同网络拓扑环境下Nearest-4、Selective-3、OW DV-hop、LSVR和IC-MHL的100次实验的运行时间分布。实验安排在Intel Xeon CPU E5-2630 v4 2.20GHz,32G RAM,Windows Server 2008 R2的DELL PC Server 上完成,各算法重复运行多次,最终的统计信息用误差条图(ErrorBar)描述。如图6所示,由于Selective-3采用排列组合的方式选取锚节点,因此随着锚节点数量的增加,其运算时间急剧增大。当锚节点为40时,Selective-3在C、Z形不规则网络中的平均运算时间分别达692.39、681.43,远远大于四个其余同类型算法。而本文所提出的IC-MHL运算时间优于Nearest-4,与OW DV-hop、LSVR接近,仅略微高于后两种算法。IC-MHL运算时间高于OW DV-hop、LSVR两个算法的原因是采用了Newton-Raphson方法迭代选择AIC值,对于本节涉及的网络场景,算法迭代3～4次即完成收敛。

3 结论

本文将多跳定位问题放在回归预测的框架下来研究,进而提出了IC-MHL。该算法的基本思想是通过锚节点跳间的数与距离关系训练出一个骨架模型,使得算法能够有效地抵御网络各向异性问题的影响。算法在训练阶段通过引入矫正的AIC衡量跳数转换距离模型的优良性,改善了模型预测的泛化能力,进而提高了算法的定位精度。多种不规则网络拓扑下的实验比较,均表明本文所提出的IC-MHL不仅能适应不规则网络拓扑环境,而且能够实时获得高精度的估计结果。