时钟时间服务器

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2011,22(Suppl.
(1)):5161http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel/Fax:+86-10-62562563面向车载容迟网络的二维时钟同步算法赵忠华1,2,3+,皇甫伟1,刘燕4,孙利民11(中国科学院软件研究所,北京100190)2(信息安全国家重点实验室,北京100049)3(中国科学院研究生院,北京100049)4(北京大学软件与微电子学院,北京102600)Two-DimensionalClockSynchronizationAlgorithmforVehicularDelayTolerantNetworkZHAOZhong-Hua1,2,3+,HUANGFUWei1,LIUYan4,SUNLi-Min11(InstituteofSoftware,TheChineseAcademyofSciences,Beijing100190,China)2(StateKeyLaboratoryofInformationSecurity,Beijing100049,China)3(GraduateUniversity,TheChineseAcademyofSciences,Beijing100049,China)4(SchoolofSoftwareandMicroelectronics,PekingUniversity,Beijing102600,China)+Correspondingauthor:E-mail:zhaozhonghua@is.
iscas.
ac.
cnZhaoZH,HuangfuW,LiuY,SunLM.
Two-Dimensionalclocksynchronizationalgorithmforvehiculardelaytolerantnetwork.
JournalofSoftware,2011,22(Suppl.
(1)):5161.
http://www.
jos.
org.
cn/1000-9825/11006.
htmAbstract:Invehiculardelaytolerantnetwork(VDTN),vehiclesnodesoftenmovefrequently,whichresultsinexistingnoend-to-endcommunicationpathbetweenanynodesatagivenmoment,andVDTNhasintermittentlyconnectivity.
Theclockoscillatorsinthevehiclenodesarealsosusceptibletoenvironmentfactors,andthecrystalfrequencyfluctuatesinthestateofirregular.
Thereexitsmuchlimitationanddifficulty,whenthetraditionalnetworkclocksynchronizationalgorithmsareintroduceddirectlyintoVDTN.
Atwo-dimensionalclocksynchronizationalgorithmforvehiculardelaytolerantnetworkisproposed,whichincludestwosynchronizationprocessesintheverticaldimensionandinthehorizontaldimension.
Thetwo-dimensionalclocksynchronizationalgorithmreducesthetimesynchronizationerrorandimprovesthesynchronizationaccuracy,comparedwiththeone-waysynchronization.
TheexperimentalresultsshowthatVDTNobtainsahighersynchronizationaccuracythroughthetwo-dimensionalclocksynchronizationalgorithm.
Keywords:vehiculardelaytolerantnetwork;clocksynchronization;busvehicle;twodimensions摘要:车载容迟网络中车辆节点频繁移动使得任意节点之间在特定时刻往往不存在一条端到端的通信路径,网络具有间歇连通性和节点移动等特点,以及车辆节点自身携带的时钟振荡器也易受到周围环境因素的影响,晶振频率处于不规则波动的状态,导致车载容迟网络直接引进传统网络中已有的成熟时钟同步算法时会产生很大的局限性和困难性.
针对上述问题,提出了一种面向车载容迟网络的二维时钟同步算法,该算法包括纵向基金项目:国家自然科学基金(61073014);国家重点基础研究发展计划(973)(2011CB302902);国家科技重大专项(2010ZX03006-007)收稿时间:2011-05-02;定稿时间:2011-07-2952JournalofSoftware软件学报Vol.
22,Supplement(1),October2011维度和横向维度的两个同步过程,与单程同步相比,减少了同步的时间误差,提高了同步精度.
实验结果表明,车载容迟网络通过二维时钟同步后能够获得较高的同步精度.
关键词:车载容迟网络;时钟同步;公交车辆;二维车载容迟网络(vehiculardelaytolerantnetwork,简称VDTN)是容迟网络概念在智能交通中的典型应用.
它主要指车辆在交通道路上移动时随身携带数据,每当车辆相遇或到达路边固定接入设施覆盖区域时,车辆之间、车辆与道路固定接入设施之间进行相互通信,从而形成的一种特殊的移动容迟网络[1].
VDTN的特点为:部分或全部车辆节点频繁移动导致任意节点之间在特定时刻往往不存在一条端到端的通信路径,使得网络具有间歇连通性和节点移动特性,网络的通信模式一般采用"存储-携带-转发"进行;车辆节点的移动受交通道路环境限制;车辆节点移动速度快,网络拓扑动态变化频繁、路径寿命短等.
随着IEEE802.
11(Wi-Fi)系列技术的成熟,相关通信设备的不断涌现,无线接入点(accesspoint,简称AP)在城市中的覆盖越来越密集,Wi-Fi通信以其组网方便、传输速率高、费用低廉等优点,使得其在车载容迟网络的通信方面获得大量关注和研究应用[2].
基于此,在本文研究的车载容迟网络中,车辆之间、车辆与道路固定接入设施之间采用了基于Wi-Fi的无线通信方式.
在车载容迟网络中,数据采集、处理、传输、定位等均具有时序性,这通常要求车载容迟网络中的各节点拥有相同的时间基准,各节点时钟之间保持良好同步性和一致性,因此时钟同步技术是车载容迟网络的重要支撑技术之一.
NTP(networktimeprotocol)[3]是Internet中使用的一种标准时钟同步协议,它可以使计算机对其服务器或时钟源(如石英钟、GPS等)做同步化,提供毫秒级或数十毫秒级精准度的时间校正.
但当把NTP直接用于VDTN时存在很大的挑战:当端到端的通信被打断时,同步操作不得不终止,车辆不得不使用最近一次的同步测量结果来调整自身的时钟,直到它能够再次被连接到时间服务器为止,并且在VDTN的应用场景中,有时恢复到时间服务器的断裂链路可能需要很长的时间;车辆节点自身携带的时钟振荡器易受到周围环境因素的影响,晶振频率处于不规则波动的状态.
因此,车辆节点的硬件时间与标准时间以及不同车辆节点的时钟之间不可避免的存在偏差,并且会随时间的推移而累积增大.
所以,任何被用于车载容迟网络的时钟同步算法必须能够适应车载容迟网络的间歇连通性和节点移动的特性以及时钟晶振工作频率不恒定产生的时间偏差等实际情况,同时并保证时间偏差尽可能的小.
为了解决上述挑战,本文提出了一种面向车载容迟网络的二维时钟同步算法,它包含两个方向的时钟同步过程,第1个过程是当车辆到达路边固定接入设施AP覆盖区域时,车辆通过Wi-Fi和AP接入Internet,然后与时间服务器进行端到端通信,交换与时间相关的消息分组,实现车辆与时间服务器间的同步,我们称之为纵向维度的时钟同步.
但由于车辆与时间服务器之间链路处于中断状态的持续时间经常较长,以及二者通过Internet交互时的往返时延一般在数百毫秒,因此纵向维度时钟同步的精度受限,具体叙述见第2.
4节.
第2个同步过程是当车辆与车辆之间相遇时,彼此交换与时间相关的分组,实现相遇车辆之间时钟同步,我们称之为横向维度时钟同步,利用横向维度时钟同步能够缩小纵向维度时钟同步的同步误差,最终由两方向的时钟同步过程协作实现车载容迟网络的高精度时钟同步.
本文第1节介绍相关工作.
第2节描述二维时钟同步算法的具体过程.
第3节对二维时钟同步算法的性能进行实验分析和验证.
第4节是结束语.
1相关工作时钟同步是所有分布式系统都需要解决的问题,因此有关时钟同步方面的研究已经较为深入.

在传统互联网的时钟同步策略中最具代表性的是NTP和GPS(globalpositioningsystem).
NTP协议[3]是目前互联网上使用的一种标准时钟同步协议,目标是把互联网上计算机的时钟同步于世界标准时间UTC(universaltimecoordinated).
NTP采用层状结构的同步拓扑,每一层均有若干时间服务器,其他均为客户机.
顶层时间服务器通过广播、卫星等方式与世界标准时钟同步;其他层的时间服务器可选择若干个上一层时间服务器赵忠华等:面向车载容迟网络的二维时钟同步算法53及本层时间服务器作为同步源来实现与世界标准时间的间接同步;客户机则可通过指定一个或多个上一层时间服务器来实现与世界标准时间的同步.
互联网具有高度的连通性,NTP的同步操作在同步源和客户机之间能够被连续和频繁地执行.
而在VDTN中这个假设不成立,VDTN中的部分或全部车辆节点频繁移动导致任意节点(车辆、接入设备)之间在特定时刻往往不存在一条端到端的通信路径.
当端到端的通信被打断时,同步操作不得不终止,时间客户端不得不使用最近一次的同步测量结果来调整自身的时钟,从而降低了同步的精度.
另外以GPS为代表的硬件时钟同步方案,从成本、可靠性、安全性等方面考虑,在VDTN中使用时,其代价也是昂贵的和缺乏安全保障的,造成VDTN无法为用户提供低成本、高可用性的通信服务.
在多跳无线网络的时钟同步方面,很多的同步算法和协议已经被提出.
根据是否存在参考节点,目前的时钟同步算法可以被分为两类:基于参考节点的时钟同步和分布式时钟同步.
在基于参考节点的时钟同步中,待同步节点根据参考节点提供的时间信息调整自身的时钟参数,从而实现与参考节点的时钟同步.
如在基于树的协议中,参考节点被称作根[4];在基于簇的协议中,簇头可作为参考节点[5].
在分布式的时钟同步算法中,所有的网络节点运行相同的分布式算法实现全局的时钟同步,而无需参考节点的存在,同步的方式或是每一个节点都分别调整自身的时钟到其当前可察觉到的更快的时钟[6],或对局部节点的时钟取平均值[79],或通过带有权重的平均取值[10]等方式来逐渐减少自身与邻居节点间的时钟误差.
上述时钟同步算法要么仅针对网络拓扑是静止的情况,要么针对允许移动节点存在的情况,但它们都存在共同的假设:网络拓扑的强连通性和节点具有很高的节点度.

而VDTN在多数情况是非全连通的网络,源节点到目的节点间不一定存在端到端的路径,即网络拓扑是一个随时间动态变化的非连通图.
车载容迟网络是一种特殊的DTN网络.
目前在DTN的网络时钟同步方面也已有了不少的研究工作.
瑞士ETHZurich的研究人员提出了时间戳转换协议(timestamptransformationprotocol,简称TTP)[11],TTP解决了稀疏ad-hoc网络中时间顺序和实时的问题,即所谓的传感器融合问题.
TTP协议的执行过程不是同步各节点时钟,而是当消息在网络中逐跳的转发时,在每一个经过的节点处都进行消息时间戳到局部时间戳的转换操作,该操作在一定的误差范围内进行,但实验仿真结果表明TTP时钟误差随着时间和跳数的增加而增加.
成对时间协议(double-pairwisetimeprotocol,简称DTP)[12]是对互联网中NTP协议的改进,然后把改进的同步方案引入到了DTN中,DTP假设在网络中至少存在一个时间服务器,与NTP相比,DTP通过使用具有可控时间间隔的后端到后端消息来估计相对时钟频率,从而实现较好的时钟估计误差.
文献[13]提出了一个用于DTN网络的全局时钟同步协议,该协议能够在DTN的异步、长延时、间歇的网络动态拓扑的环境下,根据被补偿的逻辑时钟信息,使用相对时钟信息和更新存储信息,从来弥补与相遇节点的时间误差,实现全局的时钟同步.

2二维时钟同步算法2.
1网络模型一种典型的车载容迟网络场景如下:公交车辆在城市道路中持续行驶,公交车辆与乘客及路边行人之间、公交车辆与路边的AP设备之间以及公交车辆之间会间断性相遇,这些间断性相遇带来了大量的通信机会;在公交车辆上配备无线通信设备(bus-basedinformationtransceiver,简称BIT),并采用VDTN的相关通信技术,利用间断性相遇实现数据的传输.
图1所示是城市公交车载容迟网络场景的3层架构MOONet[14].
54JournalofSoftware软件学报Vol.
22,Supplement(1),October2011sensornetworksGatewayInformationdistributiondeviceSmartphonePDAAPUnderlyinglayerEquipmentMiddlelayerEquipmentToplayerEquipmentUrbanroadsServerFig.
1Three-Tierframeworkforbus-basedDTN(MOONet)图1城市公交车载容迟网络的3层架构MOONet本文主要关注中间层设备(公交车辆)之间以及中间层设备(公交车辆)与顶层设备(服务器)之间的信息交互.
为此,对上述车载容迟网络抽象如下:车载容迟网络VDTN由一组通信节点组成,通信节点能够通过彼此之间的物理链路以"存储-携带-转发"的方式传递消息.
VDTN可被看成一个随时间变化的有向图G(t)=(N,E(t)),其中N是通信节点的集合,E(t)是在t时刻网络中存在的链路的集合.
假设Ai代表第i个节点,则N=A0,A1,…,An1,|N|=n.
从Ai到Aj存在有向边eij,当且仅当Aj在Ai的通信范围内.
模型假定当eij∈E(t),并且eji和eij是具有相同通信半径R的对称边,则eji∈E(t).
值得注意的是,E(t)随着时间动态变化,原因在于VDTN中车辆节点移动迅速频繁,导致网络拓扑动态变化、路径寿命短,使得网络具有间歇连通性和节点移动等特性.
不失一般性,本文假设在顶层设备中有一个或多个时间服务器有当前正确的UTC或真实时间.
2.
2时钟模型在车载容迟网络VDTN中,每一个通信节点有一个硬件时钟,硬件时钟通常都包含一个晶振和一个计数寄存器,晶振每出现一个振荡脉冲,寄存器的计数值就累加一次,通过读取寄存器的计数值并按一定的换算关系就能得出节点的硬件时间.
时钟的精度受到众多因素的影响,其中最主要因素如环境温度、压力等[15].
假设τ代表时间服务器的时间(UTC或真实时间),ti代表第i个通信节点Ai的时间,则通过如下线性函数便可计算出第i个通信节点的系统时间:iii=at+bτ*,其中,ai代表时钟漂移,它表示Ai的时钟与系统标准时间的偏离程度;bi代表时钟偏移,它代表系统开始时的Ai的初始时间误差.
类似的时钟模型也出现在文献[12]中.
如果Ai的时钟漂移ai和时钟偏移bi能被同时获得,则节点Ai便可被时钟同步.
当ai=1,bi=0时,我们认为Ai的时钟与时间服务器的系统标准时间完全一致.
通常,ai在系统时间的闭包区间内:|ai1|≤p,而晶振的p值大约在0ppm~50ppm之间并呈高斯分布.
2.
3延时模型消息分组传输延迟的不确定性是网络时钟同步算法设计的主要挑战之一,它极易受到处理器负载、网络负载等因素的影响,通常消息分组的传输延迟可分为:发送时间(sendtime)、排队时间(accesstime)、传播时间(propagationtime)和接收时间(receptiontime).
在车载容迟网络VDTN中,随着网络链路处于中断状态的持续时间的增加和消息分组交换频率的降低,由不准确的时钟晶振频率导致的时钟误差随之增加,然而与消息延时相关的时钟误差却基本保持不变[13].
因此,对车辆之间的无线通信来说,由于无线分组在空中传播的速度为光速,车辆之间的源于消息传播延时产生的误差可以忽略不计,即无线分组在发送端的发送时刻和在接收端的接收时刻可以认为是一样的;对车辆与时间服务赵忠华等:面向车载容迟网络的二维时钟同步算法55器之间的信息交互来说,它们之间的往返传输延时可以认为是对称相等的.

2.
4二维时钟同步算法在本文的车载容迟网络模型中,存在两个重叠的信息交互网络:一是由众多安装在公交车辆上的无线通信设备BIT构成,随着公交车辆按预定线路在城市中移动,从而构成车载容迟网络系统的骨干网络;二是在车载容迟网络中,顶层设备主要由服务器组成,负责对网络系统所收集信息的汇总、处理,以及向网络分发有关的信息等功能,BIT设备通过路边开放式的AP接入Internet,进而与顶层服务器设备互联,从而形成了车载容迟网络系统的接入网络.
由于VDTN具有间歇连通性和节点频繁移动性,当BIT设备和时间服务器间的通信被打断时,同步操作不得不终止,BIT设备不得不使用最近一次的同步测量结果来调整自身的时钟,而且在VDTN的应用场景中,有时恢复到时间服务器的断裂链路可能需要很长的时间.
再者,节点的硬件时间与标准时间以及不同节点的时钟之间不可避免的存在偏差,并且会随同步时间间隔的增大而累积增大.
所以仅仅通过BIT设备和时间服务器间的时钟同步所能达到的精度是受限的.
在本文中,我们提出了一种面向车载容迟网络的二维时钟同步算法,如图2所示.
其中,BIT设备和时间服务器之间的时钟同步称为纵向维度时钟同步,BIT设备之间的时钟同步称为横向维度时钟同步,通过二者的合理结合,二维时钟同步算法可以实现高精度的时钟同步.
APClocksynchronizationinverticaldimensionIP网络InternetClocksynchronizationinhorizontaldimensionAPTimeserverFig.
2Two-dimensionalclocksynchronizationprotocol图2二维时钟同步算法下面给出二维时钟同步算法的具体过程.
(1)纵向维度时钟同步在BIT设备与时间服务器之间的一次通信机会中,二者的纵向维度时钟同步如图3所示.
在Ta时刻,BIT设备向时间服务器发送一个消息,在Tb时刻时间服务器接收到该消息;在Tc时刻,时间服务器向BIT设备返回一个56JournalofSoftware软件学报Vol.
22,Supplement(1),October2011应答消息,在Td时刻BIT设备接收到该应答消息.
其中,Ta和Td与BIT设备的时钟相关,Tb和Tc与时间服务器的时钟相关,由延时模型可知:BIT设备的(Ta+Td)/2等于时间服务器的(Tb+Tc)/2.
TdTcTbTaδBITnodeTimeserver(Ta+Td)/2(Tb+Tc)/2δFig.
3Clocksynchronizationinverticaldimension图3纵向维度时钟同步由时钟模型知,通过如下公式可计算出第i个BIT设备的系统时间:iii=at+bτ*,其中,ai代表时钟漂移,bi代表时钟偏移.
如果ai和bi能被同时获得,则第i个BIT设备被纵向维度时钟同步.
如果所有的BIT设备被纵向维度时钟同步,则整个车载容迟网络在纵向维度便被时钟同步.
为了获得第i个BIT设备的时钟漂移和时钟偏移,从第i个BIT设备的第k次纵向维度时钟同步的消息交互中可以推导出如下等式:,,ikiikiatbτ=*+,其中,(),/2ikbcTTτ=+和(),/2ikadtTT=+.
因此,第i个BIT设备在与时间服务器进行完多次的时钟同步交互之后,在第i个BIT设备上可以得到一个用来计算自身时钟漂移和时钟偏移的方程组(1):,1,1,2,2,,iiiiiiiiiiniinatbatbatbτττ*+=*+=*+=#(1)其中,n代表第i个BIT设备的纵向维度时钟同步的次数.
理论上,只要BIT设备和时间服务器间进行足够多次的成功的消息交互,通过上述方程组便可以求解出BIT设备的时钟漂移和时钟偏移.
但由于车载容迟网络具有间歇性连通和网络节点频繁移动等特性,即任意BIT设备与时间服务器之间在特定时刻往往不存在一条直接的通信链路,所以在有限的通信机会里,仅仅通过BIT设备和时间服务器间纵向维度时钟同步所能达到的精度是受限的.
(2)横向维度时钟同步由延时模型可知,对车载容迟网络系统的骨干网络中的两个BIT设备来说,当二者相遇发生通信机会时,两个BIT设备彼此向对方发送一个无线分组,对于同一个无线分组,则接收者的接收时刻和发送者的发送时刻几乎是一样的.
对横向维度的时钟同步来说,当BIT设备i和BIT设备j发生第m次相遇机会时,二者之间相互向对方发送一个包含发送时间内容的无线分组,如图4所示.
赵忠华等:面向车载容迟网络的二维时钟同步算法57tmi,jBITnodeiBITnodejtmj,iFig.
4Clocksynchronizationinhorizontaldimension图4横向维度时钟同步若BIT设备i在tmi时刻接收到了BIT设备j发送来的时间消息分组,则设备i便可从消息分组中提取出消息的发送时间tmj,i(注:tmj,i为BIT设备j使用自身最近一次的同步测量结果调整其时钟后的系统时间),从而在BIT设备i上可以得出如下等式:,mmjiiiitatb=*+.
因此,当BIT设备i与若干BIT设备发生若干次相遇机会后,则在第i个BIT设备上可以得到横向维度时钟同步的方程组(2)如下:,mmiiijiatbt*+=##(2)综上所述,由纵向维度时钟同步方程组(1)和横向维度时钟同步方程组(2)可以得到二维时钟同步的方程组(3)如下:,1,1,2,2,,,iiiiiiiiiiniinmmiiijiatbatbatbatbtτττ*+=*+=*+=*+=###(3)BIT设备可以使用最小二乘法对上述二维时钟同步的方程组进行求解,从而获得自身的时钟漂移和时钟偏移,实现BIT设备与时间服务器之间和BIT设备之间的时钟同步;同时也可对上述二维时钟同步方程组分别在纵向和横向两个维度上赋予不同的权值,然后使用加权的最小二乘法求解加权后的二维时钟同步方程组.

3实验分析3.
1实验的硬件环境实验采用中国科学院软件研究所研发的支持机会通信的车载BIT节点,如图5所示.
硬件配置如下:针对车载环境震动频繁的特点,BIT节点采用了VIACN13000作为工控主板;BIT设备上采用了3个802.
11b/g无线网卡,分别为:运行在Adhoc模式的EdiMax7318USG,驱动程序为Rt73,用于实现BIT节点之间的通信;运行在AP模式的TP-LinkTL-WN510G,驱动程序为MadWifi,用于实现BIT与AP之间的通信;运行在Station模式的EdiMaxEW7317UHG,驱动程序为Zd1205,用于实现BIT为底层设备提供通信服务.
在本文的实验中,我们只关注支持BIT节点之间通信的Adhoc模式、BIT与AP之间通信的AP模式.
BIT节点的供电方式有两种,一是利用行驶过程中的汽车的点烟器接口进行有源供电;二是利用内置的蓄电池提供无源供电.