第40卷 第2期吉林大学学报(信息科学版)Vol.40 No.22022年3月Journal of Jilin University (Information Science Edition)Mar.2022文章编号:1671⁃5896(2022)02⁃0247⁃06
WSNs 中基于锚节点优先级节点定位算法
收稿日期:2021⁃04⁃10
基金项目：高等学校创新能力提升基金资助项目(2019B⁃197)；兰州文理学院服务地方经济社会发展计划基金资助项目(2021FWDF13)作者简介：黄珍(1980 )，女，湖北黄冈人，兰州文理学院副教授，主要从事网络通信㊁图像处理㊁模式识别等研究,(Tel)86⁃177****6090(E⁃mail)h2⁃㊂
黄 珍a ，潘 颖a ，苑 毅b
(兰州文理学院a.数字媒体学院;b.传媒工程学院，兰州730000)摘要：实际环境中，因信号衰减㊁阴影以及干扰等原因，节点的通信区域并非是规则的圆形㊂同时，不同锚节点产生的测距精度也不尽相同，为此，提出基于锚节点优先级的质心定位算法(PACL:Priority⁃Anchor node⁃bad Centroid Localization)㊂首先,PACL 算法在定位过程中考虑了节点通信区域的不规则性，并建立基于不规则程度的信号传输模型㊂然后，计算锚节点的平均跳距，并依据锚节点平均跳距值设定锚节点的优先级，使优先级高的节点优先参与定位阶段，进而提高定位精度㊂仿真结果表明，与传统的非测距定位算法相比,PACL
算法降低了平均定位误差㊂
关键词：无线传感网络；非测距定位；锚节点优先级；平均跳距；质心定位
中图分类号:TPT393文献标识码:A Priority⁃Anchor Node⁃Bad Centroid Localization Algorithm in Wireless Sensor Network送老师的八种礼品
HUANG Zhen a ,PAN Ying a ,YUAN Yi b
(a.School of Digital Media;b.School of Media Engineering,Lanzhou University of Arts and Science,Lanzhou 730000,China)Abstract :Most localization algorithms assume that communication region of node is a circular and the ranging accuracy of all anchor nodes is the same.However,in the real environment,due to signal attenuation,shadow and interference,the communication area of the node is not a regular circle.The ranging accuracy from different anchor node is also different.Therefore,PACL (Priority⁃Anchor node⁃bad Centroid Localization)algorithm is
propod.First,PACL algorithm considers the irregularity of the node communication region in the localization process,and establishes the signal transmission model bad on the degree of irregularity.Then,the average hop distance of anchor nodes is calculated,and the priority of anchor n
odes is t according to the average hop distance of anchor node,so that the nodes with higher priority take part in the localization process to improve the positioning accuracy.The simulation results show that PACL algorithm can reduce the positioning error compared with the traditional non⁃ranging positioning algorithm.
ppt加密Key words :wireless nsor network (WSNs);range⁃free localization;priority of anchor node;average hop distance;centroid localization 0 引 言
由大量微型能量受限的具有数据感知能力的传感节点组成的无线传感网络(WSNs:Wireless
Sensor Networks)[1⁃2]已在医疗㊁环境监测和军事等领域得到广泛应用㊂WSNs 中节点先感知环境，再获
842吉林大学学报(信息科学版)第40卷
取环境数据，然后将数据传输至汇聚节点，进而实现对环境的监测㊂节点的位置信息对数据所产生的价值有重要影响㊂若没有准确的位置信息，数据就没有应用价值㊂因此，定位成为WSNs的一项关键技术[3⁃4]㊂
由于节点常处于恶劣环境中，且节点本身属微型设备，因此其能量以及数据处理能力有限㊂这些特性
对节点定位提出了挑战㊂研究人员针对定位问题，提出许多不同的定位算法㊂这些算法可分为测距定位㊁非测距定位以及混合定位算法㊂
虽然测距定位算法的定位精度较高，但其定位复杂度高，并不适宜低功耗的WSNs网络㊂因此，非测距定位算法在WSNs中广泛应用，该非测距定位算法主要分为两类：启发式和分析式定位算法[5⁃6]㊂DV⁃Hop(Distance Vector⁃Hop)就是典型的启发式算法，其通过未知节点与锚节点间的跳数估计它们间的距离㊂而分析式算法是利用理论分析推导锚节点与未知节点间的距离[6⁃7]㊂
基于节点连通定位算法就属典型的非测距定位算法㊂该算法利用锚节点间的连通信息估计未知节点的位置[7]㊂基于跳数和质心定位算法常用于该定位算法中，如DV⁃Hop[8]㊁PMDV⁃Hop(Path Match DV⁃Hop)[9]㊂这些算法假定两节点间距离与它们间跳数成正比㊂
在实际环境中，特别是异构环境，这些算法的定位精度并不高㊂障碍物以及跳数估计误差导致测距误差较大㊂王改云等[10]采用质心定位算法，通过未知节点周围的锚节点构建三角形或六边形，并将这些形状的质心位置作为未知节点的估计位置㊂刘雨等[11]提出加权的质心定位算法，其将跳数作为权重，并且离未知节点越近的节点的权重越大㊂但这些算法并没有考虑到锚节点的差异性㊂由于不同的锚节点分布在不同的网络区域，它们可能对测距精度的影响也不尽相同㊂
为此，笔者提出基于锚节点优先级的质心定位算法(PACL:Priority⁃Anchor node⁃bad Centroid Locali
zation)㊂利用不规则程度构建信号传输模型，使信号传输模型更符合实际应用场景；考虑到锚节点的差异性，该算法利用锚节点的平均跳距值设置锚节点的优先级；并通过仿真分析了PACL算法的性能㊂
1 网络模型
N个传感节点随机分布于ι×ι二维(2⁃D)网络，如图1所示，其中锚节点占比为p%，未知节点占比为(100-p)%㊂令αi为第i个锚节点，其位置坐标为(xαi,yαi)；令s j为第j个未知节点，其位置坐标为(x j,y j)㊂
考虑到障碍物以及干扰等因素㊂假定节点的通信区域为不规则区域，如图1所示㊂现存的多数定位算法仍假定节点通信区域形状为圆形，这与实际环境不符㊂
假设所有节点具有不同的传输功率㊂节点间通信受障碍物影响，如树，建筑物等㊂为此，引用文献[12⁃13]的基于不规则程度(DOI:Degree of Irregularity)的无线信号传输模型㊂依据
=P0-(1+λDOI)η(1)
怎么查找别人手机位置
R RSS
i
蜂蜜的正确吃法
计算节点i所获取的信号功率㊂其中P0为发射功率;η为路径衰减因子;λDOI为不规则程度㊂图2给出λDOI=0和λDOI=0.02两种情况下的节点通信区域㊂
图1 网络模型 图2 节点通信区域
Fig.1 Network model Fig.2 Node communication area
2 PACL 定位算法
现存多数定位算法通常假设网络中节点间的跳距是均匀分布的㊂但在实际环境中，跳距受多种因素影响，如不规则形状㊁障碍物等[14⁃15]㊂为减少这些因素的影响，笔者提出PACL 算法㊂2.1 最小跳数每个锚节点向其邻居节点广播通告包ACK_Packet，其包含锚节点的位置以及该数据包被转发的
跳数N Hop ㊂最初,N Hop =0㊂该数据包ACK_Packet 被转发一次，跳数N Hop 就加1，即N Hop ←N Hop +1㊂一旦收到ACK_Packet，节点先判断是否之前收到过该数据包㊂若首次收到，就从中提取锚节点信息，并存储该锚节点的位置以及跳数信息㊂若不是首次收到，就将最新收到的ACK_Packet 中的跳数信息与存储的跳数信息进行比较，并保存最小跳数值㊂然后，节点将跳数N Hop 加1，并更新ACK_Packet 中值，再向其邻居节点转发㊂重复上述步骤，直到网络内所有节点获取其周围锚节点的信息㊂图3给出
传输ACK_Packet 的流程
㊂图3 处理锚节点的通告包的流程
Fig.3 Process of handling notification packets for anchor nodes 2.2 锚节点间的平均跳距由于锚节点位置信息是已知的，先计算锚节点间的平均跳距㊂锚节点αi 利用
A AHD i =∑N αj =1[d ij /N Hop (i ,j )], i ≠j (2)
计算平均跳距㊂其中d ij 为锚节点αi 与锚节点αj 间的欧氏距离，即d ij =(x αi -x αj )2+(y αi -y αj )2;N α为锚节点数，即N α=N ×p%;N Hop (i ,j )为锚节点αi 与锚节点αj 间的最小跳数㊂
2.3 锚节点的优先级计算了平均跳距A AHD i 信息后，锚节点αi 就向未知节点广播A AHD i 信息㊂未知节点获取了其邻近的锚节点的A AHD i 信息后，就计算锚节点的优先级㊂具体过程如下㊂
第1步先对A AHD i 信息进行归一化处理
A ^AHD i
=A AHD i A AHD max (3)其中A AHD max 为N α个锚节点中最大的平均跳距，即A AHD max =max 1≤i ≤N αA AHD i ㊂第2步计算所有锚节点的平均跳距的均值
A ~A HD a =
如何获得北京户口
A ^AHD i N α(4)
第3步依据R rank i =Round(1-10A ~A HD a -A ^AHD i
)(5)942第2期黄珍，等:WSNs 中基于锚节点优先级节点定位算法
计算每个锚节点的优先级㊂其中R rank i 为锚节点αi 的优先级;Round(㊃)为取整函数㊂
2.4 基于权重因子的质心定位算法笔者考虑的是二维空间㊂因此，未知节点至少获取离3个锚节点的
距离信息,
才能利用质心算法
图4 质心定位算法Fig.4 Centroid location algorithm 估计自身的位置㊂未知节点从其邻近的锚节点
中选择
优先级前三的3个锚节点，并利用离这3个锚节点的
距离信息估计自身的位置㊂
假设未知节点s i 依据优先级选择了3个锚节点:
α1㊁α2㊁α3㊂令r 1㊁r 2㊁r 3分别为离未知节点s i 的距离㊂
这3个锚节点以自身位置为圆心以离未知节点的距离
为半径形成3个圆㊂令O 1㊁O 2㊁O 3为这3个圆的交点，如图4所示㊂
然后，计算这3个交点的坐标㊂令(X o 1,Y o 1)㊁(X o 2,Y o 2)㊁(X o 3,Y o 3)分别为3个交点坐标㊂再计算3个交点所形成的三角形的质心坐标，如下所示X 1=X o 1+X o 2+X o 33Y 1=Y o 1+Y o 2+Y o 3ìîíïïïï3(6)最终，将(X 1,Y 1)作为未知节点s i 的位置估计值㊂3 性能仿真3.1 仿真环境
利用Matlab 2018a 软件建立仿真平台,700个节点随机分布于300m×300m 区域，其中锚节点数比例p %从10%~40%变化;λDoI 从0~0.16变化；节点的传输功率从-5~-15dBm 变化，具体仿真参数
如表1所示㊂表1 仿真参数Tab.1 Simulation parameter 网络区域/m 300×300
不规则程度λDoI 0~0.16
节点总数800
节点传输功率/dBm -5~-15锚节点数占比p /%10~40
节点的平均通信半径/m 15路径衰落指数4 为更好地分析PACL 定位算法的性能，选用同类算法DV⁃Hop [8]㊁QWCRC(Quadrilateral Weighted Centroidthm Bad on Ranging Correction)算法[11]进行比较，并分析它们的平均定位误差
A ALE =∑m i =1(x i -^x
豆腐蛋糕
i )2+(y i -^y i )()
2~Rm (7)
其中m 为未知节点数，即m =N -N ×p%;~R 为节点的平均通信半径㊂3.2 平均定位误差性能首先，分析未知节点数对平均定位误差性能的影响，如图5所示，其中节点数从200~800变化，步长为100，锚节点数占比p%=20%;λDoI =0.06㊂
从图5可知，节点数的增加有利于降低平均定位误差㊂其原因在于节点数越多，相应地锚节点数也随之增加㊂锚节点数越多，未知节点获取的测距信息越多，定位精度越高㊂此外，相比于DV⁃Hop 和
QWCRC 算法,PACL 算法的降低了平均定位误差㊂052吉林大学学报(信息科学版)第40卷
下面分析参数λDoI 对平均定位误差的影响㊂其中节点数为300，锚节点数占比p%=20%，结果如
图6所示㊂由于DV⁃Hop 和QWCRC 算法是假设节点的通信半径为圆形，即λDoI =0，并没有考虑节点通信区域的不规则性㊂因此，它们的平均定位误差不随λDoI 变化㊂ 图5 节点数对平均定位误差性能的影响 图6 参数λDoI 对平均定位误差的影响Fig.5 Average positioning error affected by number of nodes Fig.6 Average positioning error affected by λDoI 相比于DV⁃Hop 和QWCRC 算法,PACL 算法控制了平均定位误差，即使在λDoI =0.15时,PACL 算法的平均定位误差也小于DV⁃Hop 和QWCRC 算法的平均定位误差㊂3.3 平均定位误差的CDF 曲线最后，分析平均定位误差的累积分布函数(CDF:Cumulative Distribution Function)曲线㊂CDF 值越接图7 平均定位误差的CDF 曲线
Fig.7 CDF of average positioning error 近1，定位准度越高，可定位的节点数越多，如图7所
示㊂其中节点数为300，锚节点数占比p %=20%,
λDoI =0.06㊂从图7可知,PACL 算法中有接近99%的节点可
青春的绽放
以达到相同的定位精度㊂但QWCRC 和DV⁃Hop 算法
只能分别达到61%和43%㊂其原因在于PACL 算法
考虑了节点通信区域的不规则性，而QWCRC 和DV⁃Hop 算法未考虑，它们在估计节点位置时，只是简单地假设节点的通信区域为圆形区域，没有考虑到信号
衰减问题㊂4 结 语针对无线传感网络中传统定位算法未能充分考虑节点通信区域的不规则性问题，笔者提出基于锚节点优先级的质心定位算法㊂PACL 算法依据锚节点的平均跳距，优先选择参与质心定位算法的锚节点㊂锚节点的优先级越高，其平均跳距越短㊂利用这些锚节点的距离信息所估计的未知节点位置越高㊂仿真结果表明，笔者提出的PACL 算法降低了平均定位误差，同时也具有抵御不规则通信区域的能力㊂参考文献:
[1]郭会军，王宏江.基于弧参数约束的无线传感网络定位算法[J].传感技术学报,2018(4):620⁃624.
GUO Huijun,WANG Hongjiang.An Improved Arch Parameter Constraint⁃Bad Localization Algorithm for Wireless Sensor
Network [J].Chine Journal of Sensors and Actuators,2018(4):620⁃624.[2]余修武，周利兴，余齐豪，等.基于刚分簇与鸡群优化的深井无线传感网络定位算法[J].西南交通大学学报,2019,54(4):870⁃87
8.YU Xiuwu,ZHOU Lixing,YU Qihao,et al.Localization Algorithm for Mine Wireless Sensor Network Bad on Rigid Cluster and Chicken Swarm Optimization [J].Journal of Southwest Jiaotong University,2019,54(4):870⁃878.
啫喱膏[3]胡中栋，张康，王振东.基于马鞍地形的无线传感器网络节点定位算法[J].传感技术学报,2018,31(11):137⁃141.
HU Zhongdong,ZHANG Kang,WANG Zhendong.The Node Location Algorithm for Wireless Sensor Networks Bad on Saddle Topography [J].Chine Journal of Sensors and Actuators,2018,31(11):137⁃141.152第2期黄珍，等:WSNs 中基于锚节点优先级节点定位算法
