室内定位系统中基于最短路径算法的同步链自动生成

蒋汝雯，楼喜中，金 宁，叶凯枫，王戍斌

(中国计量大学信息工程学院，浙江省电磁波信息技术与计量检测重点实验室，浙江 杭州 310018)

无线定位系统利用已知位置的基站节点与待测节点之间的信息交互计算待测节点的位置，在物联网中的应用日益广泛。系统定位性能与基站同步精度密切相关，特别是对于基于时间测量原理的定位系统，例如，在基于到达时间差(Time Difference of Arrival，TDoA)的超宽带厘米级定位系统中，1ns的时间测量误差可能导致30 cm定位误差[1]。因此，基站间高精度的时间同步是提高TDoA定位性能的关键。

基站的同步采用有线方式，通过部署一个参考时钟及传输设备统一全网时钟来同步[2]，但该方式需布设大量电缆连接所有基站，施工不便且成本高昂。无线定位系统更倾向于采用无线同步方式，即基站节点通过无线信号传递时间戳[3－4]，基于某种规则、协议和算法实现时钟分布式同步[5]。通过传递时间戳消息实现节点时钟同步已经有较多的研究，典型同步协议有:传感器网络时间同步协议(timing-sync protocol of sensor network，TPSN)[6]、泛洪时间同步协议(flooding time synchronization protocol，FTSP)[7]、参考广播同步算法(reference broadcast synchronization，RBS)[8]、IEEE 1588V2协议[9]等，上述协议同步精度仅达微秒级，不适合用于同步精度要求高达纳秒级的定位系统。

基于TDoA的无线定位系统一般由主基站提供全网参考时间，其余基站通过其父基站逐级同步于主基站。O.Jean等人讨论了可扩展网络及其在参考时间下的同步算法[10－11]；也有文献研究基站摆放的几何问题[12]和多基站的同步协调问题[13－14]；彭铎等人通过优化基站间跳数和距离提高同步精度[15]，还可利用基站间的分组通信获得经验值建立延迟估计模型[16]。上述研究着眼于在已确定的同步路径下，如何更精确地计算传播时延、纠正基站之间时钟偏差和漂移。而如何确定父子基站，生成每个基站的同步路径却鲜有文献涉及。目前对于小规模无线定位系统，基本是由人工根据经验指定每个基站的同步链。该方法存在效率低、不能动态自动规划调整、同步质量非最优等问题，对于大规模定位系统这些问题尤为突出。故如何合理高效地自动生成同步链是无线定位系统一个亟待解决的重要工程问题。

本文针对无线定位系统基站之间精确同步的需求，提出一种自动高效生成基站同步链的方法。该方法采用基站间测距方式获得通信质量参数，将该参数作为父子基站成立的判据，并量化为两个节点的边的权重，构建同步网络图。再将基站同步链生成问题抽象为有向图的单源最短路径问题，采用Dijkstra算法和Viterbi算法实现了自动解算。

1 定位系统同步模型

本文研究针对如图1所示的定位系统模型，在特定区域内部署位置已知的基站作为定位节点，这些基站根据同步关系分为参考基站、中继基站和普通基站。参考基站是唯一指定的，是系统参考时间的来源；中继基站将相对于参考基站的时钟偏移通过时分方式广播。除参考基站外，其余基站处理父基站的广播信息，完成与参考基站同步，从而实现全网同步。服务器和参考基站以有线方式相连，实现对定位系统的控制、计算和管理。

图1 定位系统基站同步模型

在图1的模型中，每个基站都有唯一的一条同步链。由于基站在物理空间的位置不同且存在环境障碍物阻挡等因素，使得基站之间的无线信道质量差异比较大，甚至有些基站之间通信不可达。用一个分层的网状图来描述基站之间可能形成的同步路径，如图2所示，假设参考基站A1作为第一层，与A1能够直接通信的基站作为第二层，如图中的A2、A3、A4，能与第二层基站直接通信的基站作为第三层，如图中的A5、A6、A7。如此，以A1为起始节点，将所有基站之间可能构成的同步路径用线连接，构建出系统的同步网络图。在同步网络图中以某种规则或算法确定每个基站的父基站，即为形成同步链的过程，图3是由图2生成的一个同步链示例。

图2 同步网络图

图3 同步链图

基于以上模型部署的定位系统在执行定位任务之前，需要完成基站时钟同步，同步流程如下:①构建同步网络图；②生成同步链，同步链的计算由服务器端完成；③服务器发送父基站配置指令至参考基站，从参考基站开始以多级透传方式下发父基站配置信息至每个基站，并确认成功；④各个基站配置父基站。所有基站完成父基站配置后，服务器发送同步指令；⑤基站接收父基站的同步信息，调整时钟偏移，实现全网基站自动时钟同步。本文主要研究同步网络图的构建方法，以及基于同步网络图的最佳同步链获取算法。

2 同步网络图的构建

2.1 父子基站的评判标准

工程上，基站之间的真实距离是恒定且已知的，在基站配置参数(如晶振相对抖动等)固定的前提下，父子基站之间的信道质量越好意味着时间戳的接收越及时准确，是保障时钟同步精度的关键因素。接收信号强度在发送功率一致时，可以表示单向信道质量，基站之间测距的有效性和准确性可以表征双向信道质量。据此，本文选择了接收信号强度(Received Signal Strength Indicator，RSSI)、测距误差和标准差、测距次数和成功率等参数作为父子基站成立的评判依据，为每个参数设置阈值作为评判标准，如表1所示。两基站之间所有参数都满足表1设定的阈值，才可能成为父子基站。

表1 评价标准

由于距离或障碍物影响可能导致两基站间的测距失败[17]。在RT次测距中，假设成功次数为ST，测距成功率定义为:

测距成功率的阈值根据工程经验，本文设定为100%。测距误差和标准差的阈值设定可以根据系统的同步精度要求推算。基站同步精度受限于基站晶振固有的相对抖动，如果晶振相对抖动为10－6fs，则同步精度理论上只能达到103fs(ns)。假定系统要求达到的同步精度为ASync(ns)，C为光速，RT为测距次数，则测距误差和标准差分别为:

本文实验中，使用规格fs＝10－4ppm的晶振，设定系统同步精度要求是ASync≤0.4 ns，取ASync＝0.4 ns，测距次数RT＝100次，经计算可得测距误差和标准差的阈值分别为:Demax＝12 cm，Dsmax＝1.2 cm。

接收信号强度的阈值定义为[18]，

式中:P T为发射信号功率，f c为信道中心频率，D为发送和接收端的距离。实验选取f c＝4 GHz，P T＝10 dBm，D＝10 m，则RSSImin＝－34.4 dB。

基于以上参数，本文定义两基站的通信质量量化值q计算如下:

式中:d e是两基站的实际测距误差。q越小表示两基站通信质量越好，不满足表1条件基站的q视为∞。

2.2 同步网络图的形成

2.2.1 TWR方法

对于一个无线定位系统，获得基站间通信质量的一个通常方法是双边测距(Two-Way Ranging，TWR)[19]，即基站之间两两测距。设共有N个基站，每个有效测距结果通过RT次测距取平均值得到，总测距次数记为W，有:

由式(6)可得TWR方法测距次数与基站数量的平方成正比。为降低测距次数，本文提出全信息图(full information graph，FIG)方法。

2.2.2 FIG方法

FIG方法的思路是提前找到无法通信的基站对，避免大量无效测距，从而缩短同步网络图的生成时间。利用广播帧测试可以找到这些基站对:一个基站多次发送广播帧，若另一个基站接收不到，则这两个基站可视为非通信基站对。在FIG方法中，首先利用广播帧快速找到非通信基站对，然后仅对通信基站对进行双边测距，得到基站间的通信质量量化值，从而生成同步网络图。方法1给出了FIG的生成步骤，表2为方法1中出现的符号及含义。

方法1 FIG的生成

表2 符号说明

假设共有N个基站，一个基站可以与8个基站通信[20]，分成N/8层，每层基站C28×N/8测距组合；共有(N/8－1)个上下层之间互相测距，每两层之间的测距组合为82；均测距RT次。假设发送BT次广播帧，由于广播所需时间约为测距所需时间的1/4，将发送的广播帧折算为BT×N/4测距帧。计算层数时，不能整除时均向上取整且忽略参考基站。则FIG方法总测距次数W为:

测距完成后，按照表1的限制条件筛选出可能的父子基站对，利用式(5)计算通信质量量化值，即完成了FIG的构建。

2.2.3 KIG方法

两对通信质量相近的基站，同步精度差异可忽略不计。若基站与同层基站的通信质量和另不同层基站相近，则可以忽略同层之间的连接，进一步简化同步网络图。基于此，本文提出了关键信息图(key information graph，KIG)方法，如方法2。

方法2 KIG的生成

KIG消除了同层之间的连接，进一步减少了测距次数。与FIG相比，取消了每层的基站组合N/8。因此，KIG的总测距次数为:

3 基站同步链的生成

将图中基站视为节点，参考基站为源节点，两个基站间的通信质量q视为节点的边的权值，则同步网络图可视为赋权有向图，最佳同步链问题即抽象为有向图的单源最短路径问题。

3.1 经典Dijkstra算法

由荷兰计算机科学家E.W.Dijkstra提出的经典Dijkstra算法能有效解决有向图最短路径问题。该算法基于贪心思想找到从源节点到其他节点的最短路径，产生一个最短路径树(最佳同步链)。针对FIG，经典Dijkstra算法[21]求解基站同步链的步骤如下:

Vi:第i个节点；V0:源点；S:获得最短路径的节点；T:尚未获得最短路径的节点

Step 1 初始化:S＝{V0}

Step 2 从T中选取一个与S中有连线且权值最小的节点Q，加入S；修改T中节点的距离值:加入中间节点Q，从V0到Vi的距离值缩短，则修改成功。

Step 3 重复上述步骤step2，直到S中包含所有节点。

3.2 优化的Dijkstra算法

基站在实际部署中遵循“仅够用”原则，故同步网络图是稀疏图。基于稀疏图论，本文采用堆优化方案，降低经典Dijkstra算法的复杂度。优化部分说明如下:首先，将所有顶点设置为一个小的顶部堆，此时堆顶部必须是起点。在每次迭代中，将堆的顶部元素取出，然后调整堆。重复多次，直到将堆中的所有顶点都添加到S。在此基础上，还可以使用二项式或斐波那契堆降低复杂度[22]。

3.3 Viterbi算法

Viterbi算法是基于动态规划的思想，它用于查找符合隐马尔可夫模型的最短路径[23]。KIG特点为同层之间无连接，符合隐马尔可夫模型，可以用Viterbi算法解算出最佳同步链。

如图4所示，Viterbi算法的流程如下:

图4 KIG的同步网络图解算

Step 1 从点S0开始。对于第一层中的两个节点，计算它们的权重q(S0，A1)，q(S0，A2)。

Step 2 计算S0到B层所有节点的最短距离:min[q(S0，Bj)]＝q(S0，Ai)＋q(Ai，Bj)，i，j＝1，2，3。

Step 3 计算S0到C层所有节点的最短距离:min[q(S0，C j)]＝q(S0，Bi)＋q(Bi，Cj)，i，j＝1，2，3。

以上计算过程表明，当同步网络图有m层，每层有n个节点时，算法的复杂度为O(m×n2)。

4 复杂度和性能分析

本节主要讨论FIG和KIG这两种同步链生成方法的同步性能，测距复杂度，以及相应的最短路径算法复杂度。其中，父子基站评价标准仅改变同步网络图的权值数值，不改变相对大小，因此不影响同步链和同步精度。

4.1 FIG和KIG的性能差异分析

TWR和FIG最终生成的都是全信息图，而KIG取消了同层基站的有向连接，部分信息的丢失可能会导致依据KIG生成的同步链是次优同步链。假设同步网络图如图5所示，实线表示不同层基站之间的连接，虚线表示同层之间的连接；每条边的权重如表3所示。

图5 同步网络图

在本例中，根据表3和图5，FIG和KIG用经典Dijkstra算法，最后均获得了如图6所示的同步链。FIG与KIG相比，FIG的生成复杂度远高于KIG，二者最后获得的最佳同步链基本等价。

表3 图5各条边的权重

图6 FIG/KIG方法的最短路径结果

4.2 生成同步网络图的测距次数分析

假定基站数量N＝1000，测距次数结果如表4所示。与TWR相比，FIG和KIG的复杂度从N2降低到N；FIG的测距效率提高了97.8%，KIG提高了98.6%，KIG比FIG少了4×105次测距。

表4 三种方案测距次数的比较

图7绘制了TWR、FIG和KIG三种方法的总测距次数随基站数量增大的变化趋势，可以看出，随着基站规模的增大，FIG和KIG可以显著提高同步网络图的生成效率。由于取消了部分有向连接，KIG在大规模系统更具有优势。

图7 比较不同方法的测距次数

4.3 基站同步链解算的复杂度分析

表5对比了FIG和KIG两种方案适用的最佳同步链生成算法的复杂度。基站数量为N，边的数量为M，假定N＝1000，则M＝W/RT。根据式(7)和式(8)，以及Vterbi算法推导可知KIG中m＝125，n＝8。

表5 比较求解算法的复杂度

优化后的Dijkstra算法复杂度从N2降低到到N，Vterbi算法则只与每层基站数量相关。对于FIG的最佳同步链解算，优化的Dijkstra算法复杂度比经典算法低96.4%。对于KIG，优化后Dijkstra算法的复杂度比经典Dijkstra算法低97.6%，Viterbi算法的复杂度比经典Dijkstra算法低99.2%。

图8绘制了FIG和KIG最佳同步链的计算复杂度和相应计算时间随基站数量增大的变化趋势。由图可知，KIG-Viterbi的复杂度最低。这是因为KIG与FIG相比，忽略了同层之间的连接，减少了有向图中边的数量，从而减少了搜索路径数，且Viterbi算法是基于动态规划进行路径搜索，其效率更高，当基站数量达到1000时，计算时间仅为1.8 s。结合第4.2节的结论，我们得出KIG-Viterbi是针对大规模定位系统最佳同步链路解算的高性能方法。

图8 比较求解算法的复杂度和运行时间

5 结论

针对大规模无线定位系统中基站同步问题，提出了一种最佳同步链的自动生成方法。该方法首先将基站间的测距结果量化为无线链路的通信质量，并以基站为节点、父子基站之间的连接为边、以通信质量为边的权重，构建基站同步网络图的数学模型。提出了FIG和KIG两种同步网络图的构建方案，与常规的TWR相比，有效减少了测距次数，提高了同步网络图的生成效率。

基于生成的同步网络图，将最佳同步链问题抽象为有向图的单源最短路径问题。通过优化的Dijkstra算法和Viterbi算法分别求解FIG和KIG的最短路径，快速准确地实现基站最佳同步链的解算。该方法生成的同步链在环境因素和基站规模变动时，可以实现动态自适应调整。

本文提出方法的实用性和有效性已经在实际工程中得到检验。在总面积约7200 m2的两层地下车库铺设121个基站，采用DW1000芯片，UWB信号的中心频率为4 GHz。系统采用KIG-Viterbi方式，用时2 min完成同步链计算和配置。最终同步精度为0.4 ns，系统达到的定位精度为0.5 m。