协同定位网络测距性能探究

仇 凯，王 前

协同定位网络测距性能探究

仇 凯，王 前

（河海大学 地球科学与工程学院，南京 210000）

针对协同定位方法带来的网络节点之间争用信道的问题，提出一种适用于多节点协同定位网络的测距方法：立足载波侦听多路访问/冲突避免（CSMA/CA）协议在通信网络和协同定位网络的不同，通过减少单次测距时间、避免重复测距、减少节点竞争接入信道的次数，优化测距过程；并提出一种时延修正算法对传播时延进行估计和修正。实验结果表明，该方法可以在有效提高整个网络测距频度的同时，有效降低传播时延对于测距精度的影响，提高测距精度。

载波侦听多路访问/冲突避免（CSMA/CA）协议；协同定位网络；测距精度；测距频度；马尔可夫模型

0 引言

协同定位通过引入未知节点之间的测量使得位置参数的提供者从锚节点扩展到整个协同定位网络[1-2]，在带来高精度定位的同时也会带来网络层次的问题[3]，对此需要设计合理的多路访问控制协议[4-5]。尤其是在森林覆盖、隧道等环境下，卫星信号易受到干扰或者阻断，使得定位精度下降甚至定位失败；加上环境的遮蔽、节点自身的电能储备等因素，很有可能出现某些节点无法正常工作以及需要新增节点的情况。这就迫切需要一种灵活多变的协同定位方法。本文就此应用需求从测距性能方面对协同定位网络进行研究。

目前定位网络中基于时分多址（time division multiple access，TDMA）协议的研究较为成熟，该协议可以确保定位网络测距稳定进行，但灵活性较差——当网络出现新节点加入或者旧节点退出的情况无法及时调整。而载波侦听多路访问/冲突避免（carrier sense multiple access with collision avoid，CSMA/CA）协议在具有高灵活性的同时还有较高的效率[6-7]，非常适合用作协同定位网络的控制协议。但目前基于CSMA/CA协议的研究大部分集中于通信网络，针对基于协同定位网络的CSMA/CA协议的研究较少。这2种网络的CSMA/CA协议的区别如下：

1）二者最终目的以及节点间关系不同。前者的目的是为了实现多节点向接收站传播数据，多节点之间只有竞争；而后者目的是为了实现所有节点之间都完成测距，节点间既有竞争又有合作。

2）二者节点的要求不一样。前者的过程就是多个节点竞争，向一个接收站发送数据，节点是发送方；后者节点间需要相互发送信息进行测距，每个节点既是发送方又是接收方，整个协同定位网络的过程就是多个节点之间相互发送数据。

3）二者的着重点有区别。数据帧是前者的重中之重，需要尽可能保证数据帧的完好；而在后者重要的是测距频度和测距精度。

4）二者的运行流程不同。前者的流程为网络中的节点竞争向接收站发送信号，节点成功发送后仍会继续竞争接入信道；而后者某一节点与目标完成测距后，会退出与该目标测距的竞争行列。

双边双向测距（double-sided two-way ranging，DS-TWR）因无视时间同步问题并在有时钟偏差的情况下拥有较高的测距精度[8]的缘故常用作定位网络的测距方法，但目前基于DS-TWR的研究忽略了信号在信道中传播的时间对于测距精度的影响。

本文立足CSMA/CA协议在通信网络和协同定位网络的区别，建立马尔可夫模型对协同定位网络中节点间单次测距的理论值进行分析；接着给出基于CSMA/CA的协同定位网络完成测距的流程，并通过引进“RTS-CTS”（请求发送（request to send，RTS）和允许发送（clear to send，CTS））、改进退避算法、引进“REPORT（通过节点回应避免重复测距）”机制和“中心站”的方法对测距频度进行改进；然后分析信号在信道中的传播时间对于测距精度的影响，并提出一种时延修正算法以减少测距误差。

1 基于单次测距时间理论值分析

在CSMA/C协议中有一些参数可供用户选择，可在不同情况下对参数进行调节来提高性能，这些参数对于CSMA/CA协议有不同的影响。为了便于从理论上了解这些参数与CSMA/CA协议的联系，本文引用应用广泛的二维马尔可夫（Markov）模型[9]，对基于CSMA/CA的协同定位网络的单次测距时间进行分析。

本文马尔可夫模型的建立必须满足以下几个假设条件：

1）信道传输的误码率为0；

2）网络中不存在隐终端（2个互不在对方通信范围内的节点向同一个目标发送信号时误以为信道空闲而产生碰撞的情况）以及暴露终端（2个互在对方通信范围内的节点向不同目标发送信号时误以为信道繁忙而暂停发送从而降低信道利用率的情况）的问题；

3）每个节点在任意时刻都有信息等待发送；

4）节点数不会发生变化；

5）每个节点产生碰撞的概率均为（定值）；

6）每个节点的重传次数无上限。

二维马尔可夫模型如图1所示。

图1 退避机制的马尔可夫模型

在该模型中单步转移概率为

其中

根据马尔可夫模型可知，当节点的退避次数为，退避时间为时，有

综合上式，有

令初始竞争窗口为32，最大退避次数为10，求出碰撞概率与节点数的关系如图2所示。

图2 碰撞概率与节点数的关系

2个节点完成一次测距所需的时间为

2 基于CSMA/CA的协同定位网络测距过程

将网络中个节点中的一个节点（例如从节点1开始）作为测距对象，即除了节点1以外的其余－1个节点开始竞争对节点1发送数据，竞争成功的节点与节点1进行双边双向测距，待测距完成之后节点1会发送一个确认帧（acknowledge character，ACK），广播整个网络告知测距已经完成，那么其余节点的冷冻期就会结束，与此同时节点也会暂时退出竞争至新的节点作为测距对象。流程如图3所示。

图3 基于CSMA/CA的协同定位网络测距流程

式中：为第n个大组中第i个小组的单次测距时间的理论值。基础方法完成一次测距的过程为：节点i等待一个分布式帧间间隙（distributed inter-frame space，DIFS）后竞争向测距目标发送一个数据帧，若竞争成功，测距目标会回应节点i一个ACK，告知全网接下来由该节点与自己进行测距；收到ACK的节点i向测距目标发送第一个测量帧，测距目标接收到第一个测量帧后等待一个时间后回应第二个测量帧；节点i接收到第二个测量帧后等待一个时间后，再次向测距目标发送第三个测量帧；测距目标接收到第三个测量帧后等待一个短帧间间隔（short inter-frame space，SIFS）时间后回应一个ACK告知本次测距顺利完成；节点i接收后暂时退出信道竞争，其他节点开始竞争。单次测距的过程如图4所示。

3 基于测距频度的改进

3.1 “RTS-CTS”改进

“RTS-CTS”机制的引进会使得整个网络的额外开销增大，从而降低网络的效率[10]；但他们的长度与附带大量数据信息的数据帧相比较短，可用小碰撞来代替大碰撞，减少碰撞概率和碰撞损失，尽可能地保护后续帧的传输。并且“RTS-CTS”机制的4次握手与双边双向测距的信息交互完美契合：前3次握手进行双边双向测距，最后一次ACK告知网络本次测距已完成。

因此本文在双边双向测距的基础上，基于CSMA/CA协议将节点间单次测距所需的信息交互流程设置为“测量请求、测量应答、测量进行以及测量确定”，其中前3次信息交互构成一个完整的双边双向测距，并将RTS和CTS 2个控制帧优化为携带测量功能的帧，将ACK优化为携带数据功能的帧，具体的流程为：

1）该节点想与测距目标进行测距，按照协议要求，它必须先侦听信道是否处于空闲状态，如果信道空闲且等待一个DIFS后仍空闲，就会向测距目标发送一个携带测量帧以及计时信息的测量请求帧。计时信息的作用是告知其他节点信道已被占用，且会让其他节点进入冷冻期，并且会有一个计时倒数的功能，只有计时归0其他节点才能尝试接入信道。

2）测距目标在接收到节点发送的测量请求之后，等测量请求的计时器归0时会向该节点发送一个测量答复，并且也携带一个NAV信息，进而避免别的节点对这次测量造成影响。

3）节点收到测量答复之后等计时归0后，发送携带测量帧的数据帧。

4）测距目标收到节点发送的数据帧后，将以广播的形式将携带与本次测距有关的时间戳的ACK发送给该节点，同时其他处于冷冻期的节点也可以接收到该ACK，此时它们得知本次测距已经顺利完成，则结束冷冻期，重新参与信道接入竞争。节点工作流程如图5所示。

图5 节点工作流程

3.2 退避机制的改进

二进制退避（binary exponential back off，BEB）算法[11]使得不同节点在经历退避后随机选择的退避时间尽可能不同，减少多个节点同时竞争接入信道的概率；但是退避机制也存在不足。由于通信网络与协同定位网络的不同，原本在通信网络中退避算法的缺点在协同定位网络中不一定适用。具体包括：

1）BEB算法会使得通信网络中的节点出现不公平的现象。

2）BEB算法会造成竞争窗口的震荡。

因为与通信网络注重数据传播且需要不断传播不同，协同定位网络的目的是完成节点间的测距，所以当一个节点已经竞争接入信道与当前的测距目标完成测距，那么在下一个测距目标出现前，该节点都不需要参与竞争，这样就不会出现上述2个问题。

但是在协同定位网络的CSMA/CA协议的退避算法仍存在以下不足：

1）无论协同定位网络中的节点数是多还是少，BEB算法的初始退避时间范围固定不变。

目前对于退避窗口的改进大多集中于重设节点竞争成功之后的竞争窗口，但根据前文的分析，这些改进显然并不适用于协同定位网络。对此本文提出以下2点改进方法：

1）基于BEB算法灵活性不强的缺点，本文提出根据网络的节点规模设定初始CW的办法。在进行协同定位测距时先对不同节点数下的最佳初始竞争窗口的值进行仿真模拟，然后将最佳初始竞争窗口设为最初的竞争窗口。

3.3 “REPORT”机制的引进

整个网络测距的过程中仍存在着重复测距，节点间的信息交互过程还存在优化的空间。为解决上述的问题，本文引入“REPORT”机制（将引入该机制的方法简称为R-CSMA/CA）。

令节点号（identification，ID）小于的节点为节点的前驱节点，节点ID大于的节点为节点的后继节点。假设此时节点为测距目标，节点的前驱节点无须参与竞争与节点测距，只有节点的后继节点需要竞争接入信道与节点进行测距。引入“REPORT”机制前后节点间测距情况如图6所示。

引入“REPORT”机制后协同定位网络中不会出现重复测距，即大组的个数不变，仍是个，但小组的个位不再是固定不变的－1，而是－（为已经作为测距目标的节点ID），这样整个网络完成测距所需要的测距次数减少了一半，并减少了高节点数下进行竞争的次数，减少了竞争所浪费的时间，提高了协同定位的测距频度。整个网络完成测距的时间为

3.4 中心站的引进

随着节点数的增加，节点接入信道产生冲突退避的次数也会随之增加，而高节点数情况下退避时间相当长，这样退避次数和退避时间的同时增加会大大增加协同定位网络完成测距所需要的时间。

对此本文提出一种新的方法（简称为N-CSMA/CA）：在以个未知节点组成的协同定位网络中引入一个中心站作为竞争信道的媒介，个节点通过向中心站发送数据来竞争接入信道，一旦有一个节点竞争成功，那么其他节点就会进入冷冻期不会抢占信道，而竞争成功的节点就会与其他未与自己完成测距的节点进行信息交互测距；当该节点完成测距后，该节点会退出接入信道的竞争，而处于冷冻期的节点恢复并继续竞争接入信道；以此类推至所有节点间都完成测距。

这次改进后大组的个数没变，仍是个，但是每个小组的节点成功竞争接入信道的次数减少了，那么N-CSMA/CA完成测距所需的时间为

与之前改进方法不同，N-CSMA/CA在带来更高测距频度的同时，也带来了更高的要求，包括：须增加中心站的额外支出；中心站关乎到整个网络的正常运作，若中心站出现故障，整个网络将无法正常运行。

本节立足CSMA/CA协议在通信网络和协同定位网络的不同，通过引进“RTS-CTS”和改进退避算法减少单次测距时间，引进“REPORT”避免重复测距，以及引进中心站减少竞争接入信道的次数来缩短整个网络完成测距所需的时间，进而提高测距频度。

4 基于测距精度的改进

目前基于双边双向测距的测距精度与时钟偏差的关系往往会忽略传播信号在信道传播中的时间[12]，如图7所示。

图7 协同定位网络测距过程

综上所述可得

使用时延修正后得到的传输时间误差为：

可以看出本文的实验修正算法确实可以有效减少由信号在信道中的传播时间引起的测距误差，达到提高测距精度的效果。

5 实验与结果分析

本文使用MATLAB软件对上述方法的测距时间以及测距误差进行仿真验证。

5.1 基于测距时间的仿真及分析

仿真参数如表1所示。

表1 数值分析参数

本文的仿真参数取值均依据IEEE802.11协议（控制帧、测量帧、数据帧、帧间间隔的大小）[13-14]以及DW1000仪器的设置[15]（双边双向测距中等待时间）。

由于MATLAB无法创建同一个对象的多个实例，无法并行处理每个节点的需求，所以本文以时隙为单位循环处理多个节点的操作。单次测距的仿真流程如图8所示。

基础方法单次测距的仿真结果与马尔可夫模型的理论值对比如图9所示。

可以看出本文的仿真结果与基于马尔可夫模型的理论值相近，且二者的单次测距时间都随节点数的增加呈平缓增加的趋势，说明本文的实验结果是可靠的；而图中基础方法的测距时间也会用于下文改进前后的测距时间对比。

“RTS-CTS”机制的引进和退避机制的改进均是通过基于单次测距的改进来提高测距频度，所以将这2种方法放在一起与基础方法进行仿真对比（退避机制的改进是在“RTS-CTS”引进的基础上进行的）。这2种改进方法与基础方法的单次测距时间以及整个网络完成测距的时间对比如图10所示。

图8 单次测距的仿真流程

图9 单次测距的仿真结果与理论值对比

图10 3种方法的单次测距时间以及整个网络测距时间

R-CSMA/CA（3.3节的方法）并未在单次测距方面进行改进，而是通过减少重复测距来提高测距频度，R-CSMA/CA与前3种方法每个大组完成测距的时间和整个网络完成测距的时间对比如图11所示。

可以看到在“REPORT”机制引进前，每个大组完成测距的时间是相近的，均存在重复测距。在引进“REPORT”机制后，避免了重复测距，随着大组ID的增加，大组内单次测距次数减少，从而导致大组完成测距所需时间减少，最终提高整个网络的测距频度。

N-CSMA/CA方法通过减少节点竞争接入信道的次数来减少大组完成测距的时间，该方法与其他方法每个大组和整个网络完成测距的时间对比如图12所示。

图12 5种方法整个网络完成测距的时间

在节点数较多的情况下竞争接入信道是一个很大的时间开支，N-CSMA/CA通过引入中心站的方法，使得每个大组完成测距所需的竞争成功次数减少为1，减少了每个大组竞争接入信道所需的时间，最终减少整个网络完成测距所需的时间。

5.2 基于测距精度的仿真及分析

图13 时延修正前后测距误差

6 结束语

本文立足CSMA/CA协议在通信网络和协同定位网络中的区别，提出一种适用于多节点的协同定位测距方法。首先建立马尔可夫模型，确定CSMA/CA参数对于测距时间的影响以及单次测距的理论值。其次，通过引入“RTS-CTS”机制、优化退避机制、引入“REPORT”机制，以及引进中心站的方法优化测距过程。接着提出一种时延修正算法对传播时延进行估计和修正。最后，基于IEEE802.11协议的标准在MATLAB软件平台进行实验验证，结果表明本文提出的方法确实可以提高测距频度和测距精度。

[1] Zhang G, Xu B, Ng H F, et al. GNSS RUMS: GNSS realistic urban multi-agent simulator for collaborative positioning research[J]. Preprints, 2020.

[2] Jiang H Z. A review of collaborative positioning technology[J]. Telecom Power Technology, 2017.

[3] Zhang L, Tang L, Jia S, et al. A collaborative simplification method for multiple coastlines based on the hierarchical triangulation network partition[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(2): 93-104.

[4] Ge W U, Pengfei J I, Zhang Z, et al. Low time-delay MAC protocol based on asynchronous scheduling for WSNs[J]. Transducer and Microsystem Technologies, 2019.

[5] Bin, Huang, Zheng, et al. Distributed GNSS collaborative positioning algorithms and performance analysis[C]//第六届中国卫星导航学术年会. 西安: 中国电科20所, 2015.

[6] 洪家军. Ad Hoc网络中隐藏节点问题的仿真与分析[J]. 榆林学院学报, 2021, 31(4): 4.

[7] 曾言圣. ALOHA防冲突算法的研究与改进[D]. 天津大学, 2017.

[8] 孙宏伟, 曹雪虹, 焦良葆, 等. DS-TWR算法室内定位批量测距系统的优化研究[J]. 电信科学, 2022, 38(1): 73-82.

[9] Fourati, Hend, Idoudi, et al. Intelligent slots allocation for dynamic differentiation in IEEE 802.15.6 CSMA/CA[J]. Ad Hoc Networks, 2018, 72 (Apr.): 27-43.

[10] Al-Sarraf M. Simulation of performance analysis of the IEEE 802.11 DCF[J]. IOSR Journal of Electrical and Electronics Engineering, 2022 (1): 17.

[11] 李莉, 李进, 路晨贺, 等. 水声传感器网络MAC协议UW-CSMA/CA的NAV优化[J]. 无线电工程, 2022(3): 52.

[12] 袁枫, 焦良葆, 陈楠, 等. 室内定位中DS-TWR测距算法的优化[J]. 计算机与现代化, 2021(10): 7.

[13] Almohammedi A A, Shepelev V, Darshi S, et al. Cost and efficiency analysis of steganography in the IEEE 802.11ah IoT Protocol[J]. Computers, Materials and Continua, 2022(8): 15.

[14] Aijaz A, Kulkarni P. Simultaneous transmit and receive operation in next generation IEEE 802.11 WLANs: a MAC protocol design approach[J/OL]. IEEE Wireless Communications. (2017-06-23). http://www.doc88.com/p-6728413879387.html.

[15] 李园园, 李勇. 基于DW1000的室内定位系统设计与测距优化方法[J]. 无线互联科技, 2016(21): 76-78.

Discussion on ranging performance of collaborative positioning network

QIU Kai, WANG Qian

（School of Earth Science and Engineering, Hohai University, Nanjing 210000, China）

Aming at the problem of competing channels between nodes in the network brought by the co-location method, the paper proposed a ranging method suitable for multi-node co-location network: based on the difference between communication networks and co-location networks for carrier sense multiple access with collision avoid (CSMA/CA) protocol, the ranging process was improved by reducing the single ranging time, avoiding repeated ranging, and reducing the number of nodes competing to access channels; and a delay correction algorithm was put forwarded to estimate and correct the propagation delay. Experimental result showed that the proposed method could effectively not only improve the ranging frequency of the entire network, but also reduce the influence of propagation delay on the ranging accuracy, and improve the ranging accuracy.

carrier sense multiple access with collision avoid (CSMA/CA) protocol; collaborative positioning network; ranging accuracy; ranging frequency; Markov model

P228

A

2095-4999(2023)02-0186-10

仇凯, 王前. 协同定位网络测距性能探究[J]. 导航定位学报, 2023, 11(2): 186-195.（QIU Kai, WANG Qian. Discussion on ranging performance of collaborative positioning network[J]. Journal of Navigation and Positioning, 2023, 11(2): 186-195.）DOI:10.16547/j.cnki.10-1096.20230222.

2022-11-18

仇凯(1997—)，男，江苏南通人，硕士研究生，研究方向为协同定位。

王前(1978—)，男，江苏扬州人，博士，副研究员，研究方向为导航定位。