（计算机应用技术专业论文）高精度计算机网络时钟同步技术的研究.pdf

摘要 高精度计算机网络时钟同步技术的研究 摘要 时钟同步技术在计算机网络中应用广泛，当今基本每个路由器上 都配有时钟同步的功能；在传感器领域，时钟同步也渐渐兴起与广泛 应用；同时时钟同步又是分布式系统中一个重要的研究方向。时钟同 步是很多基于网络的关键应用的基础，一般来说，时钟同步是指，使 本地计算机的本地时钟同参考时钟源达成一致。达成两个时钟的同步 需要完成两点，相位同步和频率同步，只有当两者与参考源的差值都 达到一个可以接受的极小值，并长期处于较为稳定的状态，才完成整 个时钟同步的过程。 本文首先讨论了时钟源的模型和同步机制，并介绍了网络上应用 最为广泛的网络时间协议n t p ( n e 觚o r kt i m ep r o t o c 0 1 ) 的模型和 工作原理，然后给出了n t p 协议中使用的时间偏移计算算法：时间 过滤算法、选择算法和时钟合并算法自行开发了基于过滤、选择、 合并算法的实验软件平台，并通过该平台的数据采集分析了这些算法 的实现效果，并对时钟同步的精度进行了深入的讨论，提出了基于时 钟服务器的改进方案。然后本文提出了一种带有外部参考源的时间服 务器的同步机制，定义了其中特定的结构和算法，来减少计算机晶振 的频率漂移和测量误差对时钟造成的影响。参考已有的算法，构造计 算机时钟模型，提出一系列提高时钟稳定性和精确性的策略。最后， 北京化工火学硕士学位论文 在一台普通服务器上实现该机制，并向客户端和从属节点提供授时服 务。该机制经过六十小时以上的测试，并人为加入高斯噪声，稳定性 和健壮性得到了评估和证实。 关键词：时钟同步，时钟漂移率，拟合偏移，d t s 算法，频率预测 n a b s t ra c t r e s e a r c ho nh i g h p r e c i s i o nc o m p u t e r n e t w o r kc l o c ks y n c h r o n i z a t i o n a b s t r a ct c l o c ks y n c h r o n i z a t i o ni su s e dw i d e l yi nc o m p u t e rn e t w o r k a t p r e s e n t ，a l m o s te v e r yr o u t e rh a v ec l o c ks y n c h r o n i z a t i o na p p l i c a t i o n s ；i n t h ef i e l do fs e n s o r , s o m ed e v i c e sb e g i nt ou s ec l o c ks y n c h r o n i z a t i o n w h i c hh a sr a p i dd e v e l o p m e n t ；m e a n w h i l e ，c l o c ks y n c h r o n i z a t i o nl e a da v e r yi m p o r t a n t r o l ei nt h e s t u d y o fd i s t r u b u t e d s y s t e m c l o c k s y n c h r o n i z a t i o n i st h ef o u n d m i o no fm a n yk e ya p p l i c a t i o nb a s e do n n e t w o r k g e n e r a l l ys p e a k i n g ，t h ed e f i n i t i o no f c l o c ks y n c h r o n i z a t i o ni st o m a k et h el o c a lc o m p u t e rc l o c kc o n c u r r e n tw i t has t a n d a r dc l o c ks o u r c e t h e r ea r et w os t e p st ok e 印t h et w oc l o c k ss y n c h r o n i z e d ，m a k i n gp h a s e s y n c h r o n i z e da n df r e q u e n c ys y n c h r o n i z e d w h e nt h et w oa s p e c t s a r e m a i n t a i n e dt h ed i f f e r e n c eb e t w e e nt w oc l o c k sb eb o u n d e di naf i x e ds m a l l r a n g ea n dl o n g t e r mi nar e l a t i v e l ys t a b l es t a t e ，t h es y n c h r o n i z a t i o nt a r g e t h a sr e a c h e d a tt h ef i r s to ft h i sp a p e rt h ea n a l y s i sm o d e lo fc o m p u t e rc l o c ki s d i s c u s s e da n dt h ee x i s t i n gs y n c h r o n i z a t i o na l g o r i t h m sa r es u m m a r i z e d i n p a r t i c u l a r , n e t w o r kt i m ep r o t o c o lu s e dm o s tw i d e l yu s e do ni n t e m e ti s d e t a i l e d ，s o m ea l g o r i t h mo fw h i c hf o ri n s t a n c ef i l t e ra l g o r i t h m ，s e l e c t i o n i i i 北京化1 = 人学硕f ：学位论文 a l g o r i t h ma n dc l o c kc o m b i n ea l g o r i t h ma r ei n t r o d u c e di nb r i e f a n dt h e n w ed e v e l o po u ro w nb a s e do nt h ef i l t e r , s e l e c t ，c o m b i n ea l g o r i t h m e x p e r i m e n t a ls o f t w a r ep l a t f o r m ，a n dt h r o u g ht h et h ed a t ac o l l e c t e df r o m t h ep r o g r a mw ea n a l y s i st h e s ea l g o r i t h m s b yi n - d e p t hd i s c u s s i o no ft h e r e s u l t ，w ep r o p o s ei m p r o v e m e n t sb a s e do np r o g r a m c l o c ks e r v e r s u b s e q u e n t l y , t h en e wm e c h a n i s m so fc o m p u t e rc l o c km o d e la n da s y s t e m a t i cs e to fs t r a t e g i e sa r ep r o p o s e d t h ei m p l e m e n t a t i o na l g o r i t h m i sd e s i g n e db a s e do ne x i s t i n ga l g o r i t h mi no r d e rt om a i n t a i na c c u r a c ya n d r o b u s t n e s s f i n a l l y , t h em e c h a n i s m i sd e v e l o p e da n di t sv a l i d a t i o ni sd o n e o nan o r m a lc o m p u t e rs e r v e rw h i c hc a ns u p p l yt h et i m es e r v i c e st ot h e s l a v en o d ea n dc l i e n t t h ep e r f o r m a n c ea n dr o b u s t n e s so ft h em e c h a n i s m i se v a l u a t e db ym o r et h a n6 0h o u r st e s t i n gw i t ha r t i f i c i a lg a u s s i a nn o i s e k e yw o r d s ：c l o c ks y n c h r o n i z a t i o n ，c l o c kd r i f tr a t e ，f i t t i n go f f s e t ， d t s ，f r e q u e n c yp r e d i c t i o n i v 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名： 日期：一鲤! 经兰旦翌鱼 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在上年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者签名：叠堡盔日期： 导师签名：玉数 日期： 第一章绪论 1 1 研究背景和意义 第一章绪论 随着i n t e m e t 技术的迅速发展，以及传感器网络在各个领域的应用，各个终 端的时钟的一致变为必然的要求。股票认证，银行结算，电话计费，都需要时钟 同步；国防工业，分布式计算等，需要精确守时；工厂的运作，机械轴承，化工 实验，一些应用传感器的场合，也需要时间的一致。因此时钟同步这一经典的问 题，随着新时代的到来，网络应用新的需求，分布式应用的普及，以及无线传感 器网络的应用，又被赋予了新的内涵。分布在不同主机或设备的应用要相互协调 工作，共同完成一项任务，就需要在这些系统之间有一个准确、统一的时钟。因 此，分析和研究时钟同步问题具有重要的现实意义。 1 1 1 时钟同步的研究领域 可以对时钟同步的研究进行一个大致的划分，从计算机网络的角度进行，可 以划分成三个领域，互联网领域【l 】，无线传感器网络领域f 2 1 ，分布式系统领域【3 1 1 4 1 。 在互联网领域，一般情况下，都是由一台服务器或类似终端具有一个权威时 间，该终端配有一个特定的硬件时钟或其它较为可靠的时间参考源，例如原子时 钟，g p s 接收终端，电话时钟或者畅通的网络条件到可靠的时钟终端的方式等， 在互联网中，其它终端可以向它发送请求，该终端接收请求并提供校时服务，或 者在某些情况下，这个准确的时钟终端主动向订阅该服务的其它终端，提供准确 的时间信息，这些取决于实际的网络情况和不同的应用【l 】。 在分布式系统领域f 6 】，每一台设备一般都处于平等的地位，对于一个计算机 集群来说，一个与真实时间相近，格外准确的时间并不是特别必要的，而是要求 集群中的每一个终端，都具有一个相同的时间，因此，以哪个终端领导整个集群 【1 6 】，作为领导时钟，或者以部分终端联合领导，作为一个相对准确的时钟的参考 源，就变得格外重要。因此，在这个领域中，一般会通过拜占庭法则来确定哪个 时钟更为准确，并根据法则来判断哪个时间作为主导，通过这样一轮又一轮的判 断和聚类，维护时钟的一致性。 在无线传感器网络领域，在组织形式方面与分布式领域有类似的地方，但由 于无线硬件设备通常小巧，计算能力有限，必须采用更为简洁的传输方式以及算 法来确保时钟的一致性f 3 】。 北京化工大学硕士学位论文 在上述三个领域，各自有着不同的特点，同时，在每个领域中，有符合自身 的优势与算法，都值得借鉴，具有较高的研究价值，在本文中，主要侧重的是互 联网领域，但文中的思想以及处理方案的制定，多处参考和采用了其它领域当中 的算法和思想。 1 1 2 逻辑时钟和物理时钟 逻辑时钟和物理时钟，通常也被称为内部时钟和外部时钟【1 9 1 1 2 0 1 2 1 1 。 逻辑时钟，尽管通常使用“时钟 这个词来表示，但它们并不是传统意义上 的时钟，称它们为计时器更好些，其实它就是几乎所有的计算机以及某些元器件 都有计时电路。计时器是由一个精确的石英晶体制成的，当在其张力限度内时， 石英晶体以一定的频率振荡，这种频率取决于晶体本身如何切割及其收到的张力 的大小。与每个晶体相关的是两个寄存器，一个计数器和一个保持寄存器。每次 振荡时使计数器减l ，当计数器减为0 时，产生一次中断，计数器重新从保持寄 存器中装入起始值，通过这种方法可以编程使得一个计时器每秒能产生6 0 个中 断或以其他希望的频率产生中断成为可能，每次中断都称作一个时钟点( c l o c k t i c k ) 。当系统刚启动时，要求操作者输入日期和时间，然后将它们转换成某一已 知起始时间后的时钟值，并将它存储在存储器中。在每个时钟点，中断服务程序 将此值加l ，用这种方法进行( 软) 时钟计时。在单机单时钟中，如果这个时钟被 瞬间关闭的问题不会太大，因为这台机有的进程都使用同一时钟，那么它们仍将 内在地保持一致。一旦引入了多c p u 系统，每个c p u 将拥有自己的时钟，情况 将发生变化。尽管每个晶体的振荡频率总是相当稳定，但保证不同计算机上的晶 体以完全相同的频率震荡是不太现实的。实际上，当系统有1 1 台计算机时，所有 n 个晶体将以略微不同的速度振荡，导致( 软) 时钟逐渐不同步，当同时读这些 时钟时，也将得到不同的值，这种在时间值上的不同称作时钟偏移( c l o c ks k e w ) 。 对于多数引用来说，所有机器在同一时间上达到一致就足够了，但这里的时间并 不一定要与广播中每小时报告一次的真实时间一样，故对于某一类算法，重要的 是内部各时钟的一致，而不是它们是否与真实时间接近，这类算法中通常将时钟 称为逻辑时钟【2 8 】【2 9 1 。 物理时钟与逻辑时钟不同，在一些实时系统中，实际时间非常重要，对这些 系统需要用到外部的精确时钟，来提高效率和冗余性。自1 7 世纪发明了机械时 钟以来，人们用过天文宇宙方法测量时间，也用过原子钟来测量时间。经过很长 时问的发展。u t c 时间( u n i v e r s a lt i m ec o o r d i n a t e d ) 是所有现代人使用的时间， 它基本上取代了老标准一格林威治天文时间。大多数电力公司是基于u t c ，用 6 0 h z 或5 0 h z 时钟计时，宣布闰秒后，电力公司分别将时钟频率增加到6 1 h z 2 第一章绪论 或5 1 h z ，以便于在他们的分布式地区中时钟超前，因为在计算机中1 秒是一个 相当大的时间间距，为了保持精确的时间，操作系统在一年里必须用专用的软件 记秒。到现在为止，u t c 中引入闰秒的所有次数大约有3 0 次。为需要精确时间 的人们提供u t c ，国际时间标准化组织( n l s t ) 使用了一个在f o r tc o l l i n s ， c o l o r a d o 的称为删自身的短波广播站。w w v 在每u t c 秒的开始处广播一 个很小的脉冲。w w v 精确度为l 毫秒，但由于空气起伏的随机性会影响到信 号传输路径长度，实际精确度在1 0 毫秒。英格兰的m s f 站在r u g b y ， w a r w i c k s h i r e 提供了一个相同的服务，一些其他的国家也有这样的站点。几个地 区卫星也提供u t c 服务，地址环境操作卫星能够提供精确到0 5 毫秒的u t c ， 还有的卫星甚至更好。使用短波广播或卫星服务要求对发送者和接受者的相对位 置有较精确的了解，这是为了对信号传输进行补偿。在市场上可以买到接受 w 、v v 、g e o s 及其它u t c 源信号的广播接收器，其价格从几千元套到几万元 套，也可以通过电话从f o r tc o l l i n s 的n i s t 得到更便宜的u t c ，但不是很精确。 不过这里也需要对信号的传输延迟及m o d e m 的速度进行校正，这种校正产生了 一些不确定性，使得很难获得精度较高的时间。 1 1 3 同步时钟方案 时钟同步，其目的是维护一个全局一致的物理或逻辑时钟，以使得系统中的 信息、事件及各关节点与时间有关的行为有一个全局一致的解释；或者是提供一 种仿真时间的推进机制，以确保节点发送和接收消息在时间逻辑上是正确的。 时钟同步可以通过硬件或软件来实现。硬件时钟同步一般通过在每一个处理 机上使用特殊的同步硬件，以及一种专用的网络来实现处理器时钟之间的精确同 步。软件时钟同步算法通常使用标准的计算机网络或通信网络，通过相互交换即 时时间的同步消息，获取即时偏差，并以此对本地节点进行时钟调整来达到时钟 同步的目的。因此从软硬件角度进行划分，可以分为软件主导的时钟，软硬件结 合的时钟。 一般来说，时钟的同步模型有两种：外部时钟同步模型和内部时钟同步模型。 对于外部时钟同步模型来说，即采用物理时钟，拥有一个可靠的时钟基是至关重 要的。这个时钟基通常被叫做参考时钟服务器或主时钟服务器。这些服务器通常 使用无线接收设备从标准的时间信号源接收标准时间，例如全球定位系统( g l o b a l p o s i t i o ns y s t e m ) 。而对于内部时钟同步模型来说，即采用逻辑时钟，并不存在一 个标准的时间基，所以时钟同步算法需要根据部分或全部的时钟信息来为每个时 钟计算修正值。 在时钟同步的方案中，外部参考源是可选的。确定是否采用外部参考源，选 3 北京化工丈学硕十学位论文 用怎样的外部参考源来提高时钟同步准确性，是第一个步骤，以在互联网领域的 常用外部参考源为例，有原子钟，i n t e r a c t 时间服务，电话拨号时间服务，无线 电时钟，g p s 时钟等。从这些参考源当中，按照一定的协议，读取时间信号，并 且以一定的机制进行合理地筛选，校正本地时钟。 时间信号的传输在同步时钟的过程中起到了至关重要的作用，大多采用两类 基本的时间信号的传输机制：单向广播( u n i d i r e c t i o n a lb r o a d c a s t ) 同步和双向成对 ( b i d i r e c t i o n a lp a i r - w i s e ) 同步，单向广播是由时钟参考源发起，向各个终端提供服 务，将时间信息发给各个终端，接收到时间信息之后，各个终端根据自身网络的 情况，对该时间信息的准确性和合理性进行分析，通过不同的算法或者再确认， 对时间信息求精后，用来校正自身的时钟。双向成对同步一般是由各个终端向时 钟参考源的服务器或其它设备发起请求信息，在信息中包含自身的时间信息，参 考源得到该请求后，将自身的时间信息分别返回给各个请求的终端，当这些信息 到达终端后，记下到达那一刻的自身的时间信息，根据发出请求时的时间信息， 参考源设备的时间信息，信息返回那一刻的时间信息，综合得到一个相对时间偏 移，根据这个时间偏移，采用不同的算法机制，经过处理后校正自身的时钟。 由于基于异步通信网络的时钟同步过程是通过网络上的信息传输完成的，而 网络传输延迟的不确定性和突发性使得时钟同步问题变得非常复杂，阻碍了时钟 同步技术的发展和应用。因此，如何有效地避免网络延迟和抖动对时钟同步的影 响，减少偶然过大即时偏差的干扰，提高客户端时钟同步的稳定性，成为了一个 亟待解决的问题。 1 2 相关领域的历史、现状和前沿发展情况 1 9 7 4 年，美国科学家a r v i n d 首先在“i e e et r a n so fp a r a l l e la n dd i s t r i b u t e d s y s t e m s 发表了与时钟同步相关的研究文章“p r o b a b i l i s t i cc l o c ks y n c h r o n i z a t i o n i nd i s t r i b u t e ds y s t e m s ”。预示着对时钟同步问题的研究进入到了一个崭新的领域。 1 9 7 5 年7 月，l e s l i el a m p o r t 在“c o m m u n i c a t i o no f t h e a c m ”发表的论文“t i m e ， c l o c k ，a n dt h eo r d e r i n go f e v e n t si nad i s t r i b u t e ds y s t e m ”就比较系统地阐述了时 钟同步技术的原理、方法以及时钟同步在分布式系统中的应用。同时还特别阐述 了逻辑时钟在带时序的分布式事件处理中的作用。进入上个世纪八十年代后，随 着计算机的普及和发展，在时钟同步方面的研究取得了很大的进展，目前经典的 时钟同步算法有l a m p o r t 逻辑时钟同步算法、群集( c l u s t 嘶n g ) 算法【1 1 、c r i s t i a n 算 法f 2 2 1 、b e r k e l e y 算法【2 6 1 、平均值算法等。 与此同时，许多有关时钟同步问题的研究都受到政府各种基金的资助。例如 在美国，美国国防部高级研究计划局d a r p a 、美国国家科学基金n s f 和美国海 4 第一章绪论 军水面武器中心n s w c 资助德拉瓦大学的d a v i d l m i l l s 教授进行时间同步项目 的研究【2 5 1 。 最早的网络时间同步技术于1 9 8 1 年提出的因特网时钟协议( i n t e r i n e tc l o c k p r o t o c 0 1 ) 。该协议使用i c m p ( 因特网控制消息协议i n t e m e tc o n t r o lm e s s a g e p r o t o c 0 1 ) 协议的时问戳消息和时间戳响应消息来完成因特网中的主机间的时间 查询和时钟同步。另外，该协议也可以使用g g p ( 网关至网关协议， g a t e w a y - g a t e w a yp r o t o c 0 1 ) 的e c h o 消息和e c h o 响应消息实现时钟同步。 1 9 8 3 年提出时间协议( t i m ep r o t o c 0 1 ) ，该协议可以在t c p 协议或u d p 协议 之上，通过端口3 7 进行通信，来实现网络中时间的查询和同步，可以精确到一 秒。除此之外，还出现了d a y t i m e 协议、m 时间戳选项等网络时间同步技术。 1 9 8 8 年美国航空航天局发布的技术备忘录( n a s a t c c h n i c a lm e m o r a n d u m ) 中 就有专门讨论时钟同步问题的综述性论文“as u r v e yo fc o r r e e tf a u l t - t o l e r a n t c l o c k ss y n c h r o n i z a t i o nt e c h n i q u e s 。这篇论文不仅详细地论述当前各种时钟同步 技术和方法，而且还特别论述了有关时钟容错和修正方法问题。最后论文还出了 时钟同步领域未来的研究方向。同年还正式提出了网络时问协议( n e t w o r k t i m ep r o t o c 0 1 ) 。其后，网络时间协议通过不断地改进和完善，使得精确度和稳定 性有了进一步的提高。 1 9 9 2 年，德拉瓦大学的d a v i d l m i l l s 教授正式提出的n t p ( n e t w o r kt i m e p r o t o c 0 1 ) 协议第3 版，是目前广泛使用的网络时间协议版本。其后又陆续发布 了简单网络时间协议s n t p 第4 版( 这是网络时间协议的简化版本) 、n t p 第4 版。作为一个应用层的i n t e m e t 标准协议，网络时间协议是工作在i p 协议和u d p 协议之上的。该协议通过c r i s t i a n 算法【2 6 1 来估计传递时间信息的报文在网络传输 中花费的时间的估计值。另外，网络时间协议还通过统计学技术提高时间估计的 有效性，通过多个时间参考源来保证时间同步应用的可靠性。由于网络时间协议 能够提供较高精度的时间同步机制，而且在实践中被证明是一种稳定、高效的时 间同步方式，因而在世界上获得了广泛的应用，并成为当今国际网络中许多时间 同步机制的标准。目前，基于n t p 的网络时间服务在国外已经相当普及，在中 国，国家授时中心提供时间服务，与此同时c e r n e t 的服务也正在开展。首先 清华大学、北京邮电大学、北京大学和东南大学将共同组建稳定的核心时间服务 系统。并将逐步完善网络时间服务系统的管理和监控，为关键性的网络服务提供 准确的时间来源。 1 9 9 3 年，b l i s c o v 在其文章“p r a c t i c a lu s e so fs y n c h r o n i z e di nd i s t r i b u t e d s y s t e m ”中指出：“时钟同步能够有效地提高分布式算法的性能。1 9 9 5 年在美国 c a l i f o m i a 大学，两位在时钟同步研究领域具有很大影响力c h r i s t o ff e t z e r 和 5 北京化工大学硕士学位论文 f l a v i u ec r i s t i a n 发表了一篇名为“a no p t i m a li n t e r n e t ec l o c ks y n c h r o n i z a t i o n a l g o r i t h m 学术报告。报告中所采用的收敛函数“微分容错中点收敛函数 能 够保证最大限度地优化系统的修正、评估最大漂移率和最大偏差。 2 0 0 0 年，欧盟各国联合实施了一项“欧米伽 计划( 用超长波授时取代了短 波授时) ，它的主要目的就是要促进时钟同步技术的改进和发展，进一步为实际 应用和研究提供更高精度的时钟。该计划提供的授时精度为1 0 u s 左右，同时加 快了欧盟数字同步通信网的建设。其后，出现了长波授时，授时精度可达到u s ， 接着g p s 的出现解决了全球覆盖问题，并且如果使用超短波传播信号，其授时 精度可达i o n s 左右。 现在时钟同步技术又成为当下的学术研究热点，当前时钟同步研究领域也根 据不同的应用朝着多元化发展。在以太网领域，r f c 1 3 0 5 中有软件为主的n t p 协议【l 】；有软硬件结合，对总线要求较高的i e e e l 5 8 8 中的p t p 协议【2 】；在无线 传感器网络方面，自2 0 0 2 年j e l s o n 和k a yr o m e r 在h o t n e t s 这一影响未来网络 研究发展方向的国际权威学术会议上提出无线传感器网络中的时间同步这一研 究课题以来【3 1 ，该方向的理论也层出不穷。由于各个领域对软硬件，计算能力， 以及参考源和传输介质的要求不同，产生的理论和算法也有着各自不同特点。在 无线传感器网络中，元器件的计算能力有限，要求低能耗，无法采用其它大型授 时参考源，因此产生的算法往往短小有效。在p c 机为主的互联网中，受线程调 度，系统调用等限制，取得本身硬件时钟耗费较大，精度难以保证，因此经常采 用外部的参考源。但对于两者来说，面对了两个共同的问题，第一，由于温度、 压力、电源电压等外界环境变化引起的时钟频率漂移造成的失步；第二，由于硬 件中断，线程上下文切换，造成读取时间的失准。因此，两个领域都采用了减小 这些影响的相应算法，均具有参考意义。 1 3 课题的难点和创新点 课题来源于基金项目：国家自然科学基金项目( 6 0 5 7 3 1 3 7 ) ：教育部重点科学 技术研究项目( 1 0 6 0 2 1 ) 资助。 课题主要的难点在于： ( 1 ) 同步机制的构建以及时间信息的读取及筛选。 ( 2 ) 时间信息的筛选聚类等统计算法。 ( 3 ) 保持时间服务器的统一的频率及稳定的精度。 课题的主要创新点在于 ( 1 ) 对时间数据的筛选拟合算法，克服误差。 ( 2 ) 采用频率预测的方法回馈进行时间信息的拜占庭选择。 6 第一章绪论 ( 3 ) 构建自己的时间服务应用。 1 4 论文的研究内容和组织结构 1 4 1 论文的主要研究内容 本论文主要研究时钟同步的各种算法以及实现效果，最后提出自己的方案并 实施。首先的工作是研究时钟同步模型及其理论，然后详细介绍了n t p 协议， 以及一些经典的网络时钟同步算法，在这基础之上，提出合适的网络时钟同步的 模型，根据现有算法，制定新的同步机制，引入外部物理时钟参考源，通过新的 方式采集数据，并进行仿真实验的过程，人为地加入噪声干扰，验证新的同步算 法的可靠性和稳定性。 1 4 2 论文的组织 本论文内容共分为七章： 第一章论述了本论文的研究背景和意义、研究历史和现状、课题的难点和 创新点等。 第二章研究时间参考源模型的理论基础，数学模型以及列举实际的参考源 的各项与时钟同步相关的性能参数。 第三章介绍时钟同步机制和现有算法。在本章会对现存的同步方式进行一 个大略的介绍以及进行部分的比较。 第四章对n t p 的模型结构及同步方法进行了详细的描述。 第六章介绍时间服务器的配置以及g p s 设备的搭建，为实验和研究做准备。 第六章对同步算法进行深入的实验和研究，制定同步机制以及算法，引入 参考源，采集数据，进行仿真实验，并对自己的工作的工作进行讨论和总结。 第七章，描述所有实验及研究所得出的结论。 1 5 本章小结 在第一章中，第一节首先总体介绍了时钟同步的研究领域，主要分为互联网 领域，分布式系统领域，和传感器领域2 7 1 。在这三个不同领域当中，各自都有相 应的特点，比如说互联网领域需要有一个严格的时钟源来作参考，而分布式系统 需要维护自己的时钟基，而传感器领域对于算法的简单有效的要求较高。接着简 单介绍了逻辑时钟和物理时钟的定义，标准时间源的发展主要经历了三个阶段， 7 北京化工大学硕士学位论文 每个阶段有不同的主导时间。 ( 1 ) 格林威治天文时 ( 2 ) 标准国际原子时间( i n t e r n a t i o n a la t o m i ct i m e ) ，简称t a i ( 3 ) 统一协调时( u n i v e r s a lt i m ec o o r d i n a t e d ) ，简称u t c 每种时间标准都在上一类的基础上有所发展。明确了时钟基准时钟种类之 后，就可以谈时钟同步的方案了，即计算机或其它终端和时钟基保持一致的问题， 在第一节中作了阐述。 接着，介绍了时钟同步的历史，现状和前沿的研究方向。从上世纪七十年代 到现在，从国外到国内，时钟同步技术都飞快地发展，期间不同的协议和算法也 层出不穷。随着时钟同步领域的新的发展，各个新的议题也被提了出来。对于时 钟同步来说，面对了两个共同的问题，第一，由于温度、压力、电源电压等外界 环境变化引起的时钟频率漂移造成的失步；第二，由于硬件中断，线程上下文切 换，造成读取时间的失准。各个领域均有不同的算法和方案去解决，所以每个领 域算法都具有相当的参考意义。 本课题来源于基金项目和教育部重点科学技术研究项目资助，该课题存在着 自身的难点和创新点，在第一章中作了简短的罗列。在本章末尾，最后介绍了本 论文的研究内容和组织结构，方便读者的阅读和参考。 8 第二章时钟同步系统模型 2 1 系统时钟 第二章时钟同步系统模型 通用计算机一般自带两个时钟源，分别为硬件时钟和软件时钟。硬件时钟通 常又叫做r t c ( r e a lt i m ec l o c k ) 时钟或c m o s 时钟，它是p c 主板上一块依靠 电池供电的芯片，即标准石英晶体振荡器( q u a r t zo s c i l l a t o r ) ，它的频率为 1 1 9 3 1 8 m h z ，即使系统断电，r t c 也可以维持日期和时间，它为整个计算机提 供一个计时标准，是最底层的时钟数据。由于访问硬件时钟的开销较大，而且得 到的结果的质量受平台相关性( 硬件和软件) 限制，所以一般只是在系统启动时 读取，运行通常不使用。软件时钟不是本质意义上的时钟，它实际上是硬件( 定 时计数器) 和软件( 时钟中断处理程序) 结合的产物，是调度系统任务和用户 任务的计时依据，它依据定时器中断计数来完成计时，在系统中时钟中断处理器 需要花费时间来执行，限制了精度不可能优于时钟中断处理器的执行时间，加上 线程上下文切换时间，还有当时间变化时调用函数进行检查的时间，造成结果不 稳定，故软件时钟分辨率不高，仅为1 0 m s 这一的数量级【l 引。 2 2 外部参考源 2 2 1 常用参考源 同步时钟源是进行外同步的系统的重要组成部分，它提供绝对物理时钟同步 所需要的当前时间。对同步时钟源的要求是它应该尽量准确。外部物理时钟的获 取有以下途径： ( 1 ) 原子钟( a t o m i cc l o c k ) 原子钟是可能获得的准确度最高的物理时钟，高精度原子钟的准确度可以做到每 天不超过1 纳秒。但由于它太昂贵，因而在一般的系统中不会直接使用。 ( 2 ) i n t c r n e t 时间设置服务 在i n t e r n e t 上有一些称为时间服务器的主机通过由r f c ( r e q u e s tf o rc o m m e n t s ) 定义的一系列标准时间协议为网络上的客户机提供同步时钟源。客户机与 i n t e r n e t 连接后，只要安装相应的客户端软件或按协议要求进行网络编程就可以 获取相应格式的服务器时间。目前在i n t e r n e t 上存在很多提供时间服务的主机， 其中最常用的是美国国家技术标准局( n a t i o n a li n s t i t u t eo fs t a n d a r d sa n d 9 北京化t 大学硕士学位论文 t e c h n o l o g y ，n i s t ) 维护的多个一级( s t r a t u m1 ) 时间服务器，在地址 h t t p ：w w w b o u l d e r n i s t g o v t i m e f r e q s e r v i c e t i m e - s e r v e r s h t m l 列出了这些服务器的 d n s 名字、m 地址与真实地址。 ( 3 ) 电话拨号( d i a lu p ) 时间设置服务 这是由n i s t 自1 9 8 8 年起，通过一种称为自动计算机时间服务( a u t o m a t e d c o m p u t e rt i m es e r v i c e ，a c t s ) 的系统提供的一种同步时钟源。计算机在安装了 相应的软件后，就可以通过调制解调器联入模拟电话网，获取由a c t s 提供的时 间。a c t s 系统每秒向联入该系统的计算机提供一次由a s c i i 码表示的时间信息。 考虑到线路延迟及信息在慢速调制解调器中的发送延迟等因素，a c t s 系统采用 回馈( l o o p b a c k ) 等技术来对线路进行校准。经过线路校准后，a c t s 提供的 时间准确度可以做到小于1 0 毫秒。 ( 4 ) 无线电时钟( r a d i oc l o c k ) 除了通过上述的网络或电话连接的方式外，通过无线的方式是获取高精度同步时 钟源的一种最常用的方法。世界上很多国家都建有无线电时间信号广播台站，这 些站一般拥有高精度的铯原子钟，可以获得精确的时间。每隔一定的时间，它们 就将编码后的高精度时间信息通过一定频率的无线电信号对外广播，提供标准时 间与频率服务。由于无线电时钟一般采用u t c 时间，因此也称无线电时钟为u t c 时钟。 ( 5 ) 美国的g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) 系统用标准的铯和铷原子频率来维持 g p s 时间，并对外广播时间、位置和g p s 系统数据。g p s 接收机通过接收未加 密的l 1 载波( 1 5 7 5g h z ) 的广播c a ( c o u r s ea c q u i s i t i o n ) 编码就可以获得准确度 为l s 间隔的同步到u t c 的时钟。 表2 1 时钟源参数精度表 时间同步技术准确度 覆盖范围 短波授时1 1 0 毫秒全球 长波授时1 毫秒区域 g p s5 0 0 纳秒全球 电话拨号授时1 0 0 毫秒 全球 互联网授时1 5 0 毫秒全球 s d h 传输网授时1 0 0 纳秒长途 表2 1 中描述了各类时钟参考源本身精度以及覆盖范围的参考。 l o 第二章时钟同步系统模型 2 2 2 参考源信息采集方式 由于读取硬件时钟和软件时钟存在各自的局限性，随着硬件技术水平的不断 提高，外部时间源或时间服务的价格逐渐减少，对于较高精度的时间需求，可以 采用外部时间源的方案。使用外部时间源通常采用直接传递技术。直接时间传递 的参考源有g p s 接收机，电话授时，短波授时等。总的来说，这些技术主要分 为三种类型，第一种是编码型，主要是r s 2 3 2 c 串行口时间编码和i r i g b 时统 编码两种方式，其特征是将时间信息以二进制、b c d a s c i i 编码方式定义到被传 递的电平位和字节中去，通常以异步方式，采用标准接口，使用方便简洁。第二 种类型是脉冲型，是周期产生的脉冲，有严格的上升沿宽度和脉冲宽度，其上升 沿严格与u t c 保持优于l u s 的同步准确度。第三种类型是频率参照信号，往往 是一种伴生调制信号。 通常p c 机采用的方式是编码型，嵌入式系统采用脉冲方式居多，对于本文 采用的g p s 接收机，输出信号通过解码转换后，一个通道输出l p p s ，它是时隔l s 的 脉冲信号，其脉冲前沿与u t c 的同步，另一通道为串口输出，在每个脉冲发出后， 广播绝对时间，即年、月、日，遵循g n 8 0 协议，以一定的波特率输出( 通常 为9 6 0 0 b i v s 或4 8 0 0 b i t s ) ，因此前两种方式均可，但无论那种方式，当集成到一 个固有系统当中时，都受到了波特率，硬件中断和线程调度等方面的局限。本文 主要介绍了一种应用r s 2 3 2 端口的g p s 接收天线作为参考时钟源，对系统时钟 的求精和容错算法机制，并将带有该参考源的计算机或服务器作为一级服务器， 向客户机或下层服务器提供相应的授时服务。该机制也可为其它时钟源的应用， 提供参考。 2 3 时钟模型 2 3 1u t c 时间模型 u t c 是协调世界时( u n i v e r s a lt i m ec o o r d i n a t e d ) 英文缩写，是由国际无线电 咨询委员会规定和推荐，并由国际时间局( b i h ) 负责保持的以秒为基础的时间标 度。u t c 是有自己的时间模型，而g p s 等设备都采用该模型【2 9 1 ，即： 1 c ( t ) = c ( t o ) + r ( t o ) ( t 一) + 寺孝( 岛) o t o ) 2 + p ( 2 一1 ) 二 其中，t 是时间变量，c o ) 是从时间气开始到当前时间t 的时钟偏移， r ( t o ) 是时钟频率或者称为速率，当它发生改变时，称为时钟漂移，善( 岛) 是由于 计算机的频率振荡器的变化而引起的，是时钟漂移的一阶导数，称为漂移率。e 北京化工大学硕上学位论文 是系统产生的随机误差。 2 3 2 计算机晶振模型 在计算机系统当中，时钟通常由晶体振荡器的振荡脉冲来衡量： c 0 ) = 尼【缈( f ) d r + c ( 龟) ( 2 - 2 ) 其中是缈( f ) 晶振的频率；k 是依赖于晶振物理特性的常量( 通常为可变频率 的倒数) ：t 是真实时间变量，c 渺是构造的本地时钟，间隔c 何一c o o ) 被用来度量 时问。 可以发现，上述这两种时钟的模型，在本质上其实是一致的，由于在计算机 领域，时间被描述为离散的脉冲或者其他信号，因此前者只不过是后者的泰勒级 数的展开，而u t c 模型更容易离散化，并给出相应的误差。 参考u t c 时钟模型，对于理想的时钟，存在 ，( f ) ：空掣：l 也就是说，理想时钟的变化速率r ( o 为l ，但在工程实践中，由于温度、压力外界环 境的变化，导致晶振频率产生波动。因此，构造理想时钟比较困难，但晶振频率 的波动幅度并非任意的，而是局限在一定的范围之内。按晶振的波动以及精度的 不同需求，又可将时钟模型分为三大类【1 5 】： ( 1 ) 速率恒定模型 ，、d e ( t ) 速率恒定模型假定时钟速率厂【”2 矿是恒定的，即晶振频率没有波动 发生。使用于时钟精度远低于频率波动导致的偏差的情况。 ( 2 )