面向航空电子云的混合式时间同步算法

李 铮 李 峭 赵露茜 熊华钢

(北京航空航天大学 电子信息工程学院，北京100191)

航空电子云[1]将美国国家航空航天局[2]和欧盟[3]提出的分布式思想扩展到网络层面，将云计算概念引入航空电子领域，以提高航空电子系统的性能.航空电子云中的节点不但能共享信息，而且能实现处理能力的共享.因此，保持节点之间的时间同步非常重要.由于航空电子云网络拓扑是动态变化的，并且航空电子应用具有时间关键性，因此航空电子云要求时间同步需要同时具备高同步精度、高收敛速度和高鲁棒性3个性能.

针对传统无线时间同步算法，文献[4]提出基于全球定位系统(GPS，Global Position System)的方法，其同步精度高，但是依赖于美国的GPS卫星，缺乏安全保障.文献[5－9]提出集中式同步方法，以根节点[5－8]或簇头[9]为参考节点进行同步.该方法的收敛速度相对较快，但是鲁棒性较差，一旦参考节点或中继节点失效，部分节点将由于接收不到同步消息而失去同步.文献[10]提出协作同步技术，远方节点可直接与参考节点同步.该方法消除了同步误差单跳累加，但是核心思想仍属于集中式同步，参考节点失效将对时间同步产生毁灭性影响.文献[11－14]提出分布式同步方法，节点通过调整自身时钟到其可观察到的更快的时钟[11]，或对邻居节点的时钟取平均值[12－13]，或取带有权重的平均值[14]来实现同步.该方法具有较强的鲁棒性，但是收敛速度较慢[12].

本文建立了航空电子云系统模型，并以此为基础提出了一种混合式时间同步算法.根据邻居节点的状态，网络中各节点能够在集中式和分布式两种同步操作之间动态切换，同时借助贝叶斯估计，提高时间同步精度.该算法在保证高收敛速度和高精度的同时，仍然能够维持较好的鲁棒性，从而适应了航空电子云对时间同步的需求.

1 系统建模

1.1 网络模型

对航空电子云进行抽象，假设网络中有n个节点，通过一定的拓扑结构连接成一个无线网络，并且网络拓扑随时间动态变化.用一个有向连通图G(t)=(V，E(t))来描述此无线网络，其中V表示网络的节点集合，E(t)表示在t时刻网络的边集合.假设 Ai表示第 i个节点，则 V={A1，A2，…，An}.如果在t时刻Aj在Ai的通信范围内，则称Aj是Ai的邻居节点，且存在边eij∈E(t).

1.2 时钟模型

本文采用的时钟模型同时考虑了时钟的偏移和漂移对本地时钟的影响.在航空电子云网络中，每一个节点Ai的本地时钟，均由下式表示:

式中，Ti是本地时钟的读数;αi是本地时钟的漂移;βi是本地时钟的偏移量.

参考节点的时钟存在由漂移引起的误差.通常，参考节点的时钟误差服从均值为0、方差为σ的正态分布[15]，实验测得σ的值为50 ns.

1.3 延时模型

节点同步是通过消息交换实现的，因此消息的传输延迟是产生同步误差的主要原因之一.消息的传输延迟可分为发送处理时间、访问时间、传输时间、传播时间、接收时间和接收处理时间.

通过MAC层打时间戳技术，可以消除发送处理时间和访问时间的影响.通过统一消息长度，可在交换消息过程中抵消传输时间和接收时间的影响.通过距离和无线电波的传播速度，可以计算得到传播时间.节点之间的接收处理时间差异服从均值为0、方差为11.1 μs的正态分布.

2 混合式时间同步算法

本文提出的混合式时间同步算法主要分为集中式同步和分布式一致同步两类操作.

2.1 集中式同步操作

2.1.1 同步流程

集中式同步操作流程可以总结为5个步骤:

1)网络中的所有节点按照时钟精度排序，精度最高的时钟作为主时钟，建立拓扑生成树.

2)主时钟以固定的同步周期定期广播同步消息SYNC到从时钟，该消息包含发送时的时间戳和主时钟位置的经纬度.记主时钟发送第k次SYNC 消息的时间戳为 TSY，Mk，经纬度为(XSY，Mk，YSY，Mk)，从时钟在本地时间TSY，Sk时刻，经纬度(XSY，Sk，YSY，Sk)处接收到该消息.

3)在接收到第k次SYNC消息后，从时钟随机延时一段时间，在本地时间TDR，Sk时刻，经纬度(XDR，Sk，YDR，Sk)处发送延时请求消息 DELAY_REQ到主时钟.

4)主时钟在本地时间 TDR，Mk时刻，经纬度(XDR，Mk，YDR，Mk)处接收到第 k 次延时请求消息，并发送包含该时间戳的应答消息DELAY_RESP到从时钟.

5)从时钟根据上述4个时间戳和位置计算时钟偏移并进行时钟调整，实现与主时钟的同步.

2.1.2 偏移的补偿

从时钟可以通过以下公式计算本地时钟在第k个同步周期内与主时钟之间的偏移βSk:

式中，DSY，Pk和 DSY，Rk分别表示第 k 个 SYNC 消息的传播时间和接收处理时间;DDR，Pk和 DDR，Rk分别表示第k个DELAY_REQ消息的传播时间和接收处理时间.暂时假设 DSY，Rk和 DDR，Rk相同，两者差异可以之后通过贝叶斯估计进行补偿，具体补偿方法见2.3.2 节.则由式(2)和式(3)可得

式中 DSY，Pk和 DDR，Pk可分别由下式计算得到:

式中，111.17是单位地球中心夹角对应的地球表面弧长，单位是km;c是电磁波的传播速度，取值为 0.3 km/μs.

偏移的计算在每个同步周期内进行.从时钟根据偏移调整本地时钟，从而实现与主时钟同步.

2.2 分布式一致同步操作

2.2.1 同步流程

分布式一致同步操作是网络内的节点与邻居节点进行时间消息的融合，调整自身时钟，最终实现全网节点同步到同一个虚拟时钟上.节点Ai和节点Aj之间进行消息融合的流程如下所示:

1)节点Aj以固定的同步周期定期广播同步消息SYNC到节点Ai，该消息包含发送时的时间戳和经纬度.记节点Aj发送第k次SYNC消息的时间戳为 Tj，k，经纬度为(Xj，k，Yj，k)，从时钟在本地时间Ti，k时刻，经纬度(Xi，k，Yi，k)处接收到该消息.

2)节点Ai通过第k－1次和第k次SYNC消息携带的时间戳和经纬度，由下式可以计算得到节点Ai和Aj之间第k个时钟相对漂移量αij，k:

式中，DP，k－1和 DR，k－1分别表示第 k－1 个 SYNC 消息的传播时间和接收处理时间;DP，k和 DR，k分别表示第k个SYNC消息的传播时间和接收处理时间.暂时假设 DR，k－1和 DR，k相同，两者差异可以之后通过贝叶斯估计进行补偿，具体补偿方法见2.3.3节.则式(7)可以化简为

式中 DP，k－1和 DP，k的计算方法同式(5)和式(6).

3)Ai根据αij，k进行时钟漂移与偏移的调整，多次调整后实现全网同步到同一个虚拟时钟上.

2.2.2 漂移和偏移的补偿

记节点Ai对漂移和偏移的第k次补偿分别为 αi，k和 βi，k，补偿后的时钟读数 TCOM，i，k如下式所示:

式中，Ti表示节点 Ai的原始本地时钟读数;αi，k可由下式迭代计算得到:

式中，ρα表示漂移调整参数，0＜ρα＜1;αj，k－1表示节点 Aj对漂移的第k－1次补偿，αi，0和 αj，0的取值为 1.βi，k可由下式迭代计算得到:

式中，ρβ是偏移调整参数，0＜ρβ＜1;βi，0取值为0.

文献[12]证明了通过式(10)和式(11)对节点漂移和偏移进行不断地调整，最终全网节点将同步到同一个虚拟时钟上，证明过程这里不再赘述.

2.3 接收处理时间补偿操作

由于节点之间的接收处理时间差异服从正态分布，因此可以通过贝叶斯估计对其进行补偿.

2.3.1 贝叶斯估计

假设观测值x的概率密度函数满足正态分布p(x|μ) ～N(μ，σ2)，其中 μ 未知，σ2已知.假设 μ的先验概率满足正态分布，其中均已知.根据贝叶斯公式可以得到:

式中

与μ及x无关，为常数，所以p(μ|x)也满足正态分布，令，则有

2.3.2 集中式同步的补偿

在集中式同步过程中，接收处理时间的差异主要影响偏移量的计算，而偏移量则直接影响补偿后的时钟时间.记偏移量补偿后的当前节点时钟时间为TCOM，i，通过贝叶斯估计方法估算的当前节点实际时间为 TBAY，i，则 TBAY，i－1表示通过贝叶斯估计方法估算的上一层节点的实际时间，且服从方差为的正态分布.由 1.3 节中建立的延迟模型可知，接收处理时间的差异服从正态分布 N(0，σ2)，其中σ 取值为 11.1 μs.则由式(14)和式(15)可以计算得到通过贝叶斯估计后的当前节点时间分布，其中

根据1.2节建立的时钟模型，令TBAY，1=T1，σBAY，1取值为50 ns，则上层节点把它的贝叶斯估计时间 TBAY，i－1和估计误差方差传给下层节点后，下层节点可以利用式(16)和式(17)计算出，如此逐级同步从而实现全网同步.

2.3.3 分布式一致同步的补偿

在分布式一致同步过程中，接收处理时间的差异主要影响时钟相对漂移量αij，k的计算.记节点通过贝叶斯估计方法估算的第k－1个时钟相对漂移量为 αBAY，ij，k－1，且服从方差为的正态分布.由1.3节中建立的延迟模型可知，接收处理时间的差异服从正态分布N(0，σ2)，其中σ取值为11.1 μs.则由式(14)和式(15)可以计算得到通过贝叶斯估计后的第k个时钟相对漂移量分布，其中

2.4 混合式同步算法流程

综合上面给出的各操作，本文提出一种混合式时间同步算法，系统时钟的同步流程如下所示:

1)网络中的所有节点按照时钟精度排序，精度最高的时钟作为根节点，建立拓扑生成树，设定所有节点的同步方式为“集中式”，根节点的状态设定为“已同步”，所有从节点的状态设定为“未同步”.

2)采用集中式同步操作对同步方式为“集中式”的从节点时钟进行同步.

3)若从节点的时钟校正值小于预先设定的阈值，则设定此节点的状态为“已同步”，否则设定此节点的状态为“未同步”.

4)状态为“已同步”的节点查询邻居节点的状态，若状态为“已同步”的邻居节点数大于等于预先设定的阈值，则设定此节点的同步方式为“分布式”，否则设定此节点的同步方式为“集中式”.

5)采用分布式一致同步操作对同步方式为“分布式”的节点时钟进行同步.

6)若需要维持全网时间同步状态，则返回第2)步，否则结束同步过程.

3 仿真实验及结果分析

为了评价混合式同步算法的性能，将其与传统的集中式算法[5]和分布式算法[11]进行比较.仿真在基于VC开发的异构通信系统仿真平台下进行，该平台已在具体工程项目中得到应用和验证.仿真场景为飞机和地面站组成的航空电子云网络，网络拓扑如图1所示.

图1 实验网络拓扑Fig.1 Experimental network topology

在网络中共有7个节点，其中节点1为地面站，其余节点为飞机.地面站作为根节点，根节点时钟的漂移量为1，其余节点时钟每秒漂移50 μs.根节点时钟的初始偏移量为0，其余节点时钟的初始偏移量为[－15，15]s之间的均匀分布.同步周期为5 s，调整参数 ρα=0.9，ρβ=0.4，校正值阈值为1 ms，邻居节点数阈值为2，飞机航行速度为[750，800]km/h 之间的均匀分布.

图2比较了3种算法的同步精度.因为跳数和邻居节点数是影响同步误差的主要因素，所以取节点7作为参考.在混合式算法中，稳定后的同步误差最大仅有53 μs，而在集中式算法中，同步误差最小值也达到了125 μs.在分布式算法中，虽然同步误差最小值达到了25 μs，但是抖动较大，最大值达到了319 μs.由仿真结果可知，混合式算法通过贝叶斯估计，明显提高了同步精度.

图2 节点7的不同算法同步精度对比Fig.2 Node 7 synchronization accuracy comparison of different algorithms

图3比较了3种算法的鲁棒性.通过设定网络边集合E(t)中元素失效的概率，观察网络中同步失效的节点数占节点总数比例的变化趋势.由图3可知，集中式算法的鲁棒性最差，因为根节点路径和上级路由路径的失效，会对同步产生较大影响.在链路失效率低于50%时，混合式算法的鲁棒性与分布式算法基本持平;在链路失效率高于50%时，混合式算法的鲁棒性介于集中式算法和分布式算法之间，因为此时部分节点切换为集中式同步操作，但是现实中高链路失效率的情况比较少见.

图3 不同算法鲁棒性对比Fig.3 Robustness comparison of different algorithms

图4比较了3种算法的收敛速度.分布式算法的收敛速度最慢，因为节点之间需要进行多次信息融合才能同步到同一个虚拟时钟上.混合式算法与集中式算法的收敛速度相同，因为混合式算法在同步初期采用的是集中式同步操作.

图4 不同算法收敛速度对比Fig.4 Convergence rate comparison of different algorithms

4 结论

1)针对航空电子云对时间同步的需求，为航空电子云建立了网络模型、时钟模型和延时模型.

2)通过分析集中式和分布式两种同步算法的特点，利用贝叶斯估计方法，提出了一种混合式时间同步算法，给出了系统时钟同步的具体流程.

3)搭建了航空电子云的典型网络，通过仿真实验对混合式时间同步算法的性能进行了分析.实验结果表明，该算法在同步精度上比集中式算法提高了72μs，比分布式算法提高了266 μs，同时该算法具有最高的收敛速度，并且在链路失效率低于50%时，其鲁棒性与分布式算法基本持平.

References)

[1]Li Z，Li Q，Xiong H G.Avionics clouds:a generic scheme for future avionics systems[C]//31st Digital Avionics Systems Conference.Piscataway，NJ:IEEE，2012:6E41 －6E410

[2]Fletcher M.Progression of an open architecture:from Orion to Altair and LSS[R].S65-5000-20-0，2009

[3]Fuchsen R.IMA NextGen:a new technology for the Scarlett program[J].Aerospace and Electronic Systems Magazine，2010，25(10):10－16

[4]Sterzbach B.GPS-based clock synchronization in a mobile，distributed real-time system[J].Real-Time Systems，1997，12(1):63－75

[5]Ganeriwal S，Kumar R，Srivastava M B.Timing-sync protocol for sensor networks[C]//1st International Conference on Embedded Networked Sensor Systems.New York:ACM，2003:138 －149

[6]Su W，Akyildiz I F.Time-diffusion synchronization protocol for wireless sensor networks[J].IEEE/ACM Transactions on Networking，2005，13(2):384 －397

[7]张春梅，白凤山，王平，等.一种改进的TPSN时间同步算法的实现[J].内蒙古大学学报:自然科学版，2013，44(3):316－319

Zhang Chunmei，Bai Fengshan，Wang Ping，et al.Implement of an improved TPSN time synchronization algorithm[J].Journal of Inner Mongolia University:NaturalScienceEdition，2013，44(3):316－319(in Chinese)

[8]师超，仇洪冰.基于脉冲耦合的TPSN时间同步协议[J].应用科学学报，2013，31(1):15 －20

Shi Chao，Qiu Hongbing.TPSN time synchronization protocol based on pulse coupling[J].Journal of Applied Sciences，2013，31(1):15－20(in Chinese)

[9]Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications，2002，1(4):660 －669

[10]Hu A，Servetto S D.On the scalability of cooperative time synchronization in pulse-connected networks[J].IEEE Transactions on Information Theory，2006，52(6):2725 －2748

[11]Zhou D，Lai T H.An accurate and scalable clock synchronization protocol for IEEE 802.11-based multihop ad hoc networks[J].IEEE Transactions on Parallel and Distributed Systems，2007，18(12):1797 －1808

[12]Li Q，Rus D.Global clock synchronization in sensor networks[J].IEEE Transactions on Computers，2006，55(2):214 － 226

[13]师超，仇洪冰，陈东华，等.一种简单的分布式无线传感器网络时间同步方案[J].西安电子科技大学学报，2013，40(1):93－99

Shi Chao，Qiu Hongbing，Chen Donghua，et al.Simple distributed time synchronization scheme for wireless sensor networks[J].Journal of Xidian University，2013，40(1):93 － 99(in Chinese)

[14]Schenato L，Gamba G.A distributed consensus protocol for clock synchronization in wireless sensor network[C]//46th IEEE Conference on Decision and Control.Piscataway，NJ:IEEE，2007:2289 －2294

[15]Lewandowski W，Petit G，Thomas C.Precision and accuracy of GPS time transfer[J].IEEE Transactions on Instrumentation and Measurement，1993，42(2):474 －479