• 一种基于车辆ad hoc网络拓扑结构的时间同步方法

    • 摘要:

      本发明公开了一种基于车辆ad hoc网络拓扑结构的时间同步方法.根据车辆总体分布呈现I型、T型或者X型的特点,以具有GPS设备的车辆作为初始时间服务器,按照分级的思想,以路由表中的邻居节点数目为标准,边进行同步,边选出最佳的次一级时间服务器.选出的次一级服务器符合道路形状的特点,且满足具有最多个尚未同步的下一级邻居节点.本发明的特点在于:同步和次一级服务器的选择同时进行,防止快速变化的路由造成选出的次级服务器失效.采用了多播和较短的同步信息进行对时,当网络进行全局同步时,使网络产生冲突而瘫痪的机会降低.服务器仅进行一次插入排序过程,其他运算完全由其他节点分担,降低了服务器的运算量.

    • 专利类型:

      发明专利

    • 申请/专利号:

      CN200910080664.2

    • 申请日期:

      2009.03.25

    • 公开/公告号:

      CN101534551

    • 公开/公告日:

      2009-09-16

    • 发明人:

      杨扬 侯国梁 周贤伟 安建伟 杨裕亮

    • 申请人:

      北京科技大学

    • 主分类号:

      H04W56/00(2009.01)I

    • 主权项:

      1. 一种基于车辆ad hoc网络拓扑结构的时间同步方法,其特征在于:依照以下步骤实现,步骤1:带有GPS设备的节点根服务器A在一个同步周期内,当其速度低于某一个门限值VT时启动同步,VT值由环境进行人工调整,首先从其路由表中提取当前所有邻居节点的ID号,并从GPS设备上获得时间信息,同时向邻居节点广播当前的发送时刻TA0和所有邻居节点的ID号Bi(i=1,2,……,m);步骤2:当次级节点Bi接收到根服务器A的消息后,立即记下当前收到消息的时刻TBi0,并存储该消息发来的发送时间TA0,提取自身的邻居列表,去掉A发来的邻居列表中的已存在的节点,计算出剩余邻居节点个数NBi(i=1,2,……,m),将自己的ID号Bi和NBi发还给根服务器A并同时记录发送时的时刻TBi1,当某些节点在本同步周期内已经被其他GPS同步过,或存在包含GPS设备的其他节点时,向A返回拒绝参与的消息,他们将不参与任何同步过程;当一个尚未完成同步的节点在同步过程中收到多个服务器的消息,则取最先发来的消息服务器为其上一级服务器;步骤3:服务器A收到了节点Bi的回应消息时,记录接收时刻TABi1(i=1,2,……,m),Bi和NBi,并根据NBi的大小进行插入排序Max~Min(NBi)={NBw,NBx,NBw,NBz……};令排序后的NBi最大的4个节点SB1=Bw,SB2=Bx,SB3=By,SB4=Bz,暂定为次一级服务器;对SBi(i=1,2,3,4)发送消息接受时刻TABi1,本消息发送时刻TABi2,以及暂定次一级服务器的ID号SBi(i=1,2,……,m);对其他非暂定服务器节点Bi,仅发送原发来消息的接受时刻TABi1,本消息发送时刻TABi2;步骤4:节点Bi获得了消息后进行本地对时,假设时间差为δ,即δ=TServer-Tclient,则其中,TABi1为服务器接收消息时刻TServer,TBi1为客户端发送消息时刻Tclient,dCSi为消息从客户端到服务器的传输和处理时间,δi为A与Bi的时间误差,dSCi为消息从服务器到客户端的传输和处理时间;假设dCSi=dSCi=di,即消息往返的处理、传输时间相同则消去di得即Bi只需用已知的TABi1、TABi2、TBi1、TBi2计算出δi并对当前时间进行修正,获得标准时间;同时,通过比较TA0-TBi0与TABi2-TBi2来验证链路的稳定性,当差距非常大时,表示链路不稳定,采取其他技术措施,稳定链路,或进行多次同步取平均;步骤5:对于暂定服务器的节点SBi,从其路由表中提取当前所有邻居节点的ID号并减去已经同步过的节点集合Bi得到次一级尚未同步节点Ci(i=1,2,……,m),并从本地获得时间信息,同时向邻居节点广播当前的发送时刻TSBi和Ci(i=1,2,……,m)以及A节点指定的暂定服务器的ID号SBi和SBj(j=1,2,3,4,j≠i),对于非暂定服务器,则完成同步工作,返回确认信息;步骤6:其他暂定服务器SBj(j=1,2,3,4,j≠i)若能收到SBi广播的消息,则将发来节点的集合与本地节点尚未同步的邻居节点集合Ci(i=1,2,……,m)进行交集和并集运算,交集节点数目占并集节点数目的一半,即相似度在50%以下时,确立自己的次一级服务器地位,并在与A同步后,按照服务器A的工作方式重复步骤2~步骤7,向自身次一级的节点进行逐级同步;若相似度在50%以上甚至完全包含时,说明该节点与SBi距离很近,直接回复拒绝信息给服务器A,且暂定服务器按照服务器顺序,有拒绝的优先权,拒绝排序靠后的暂定服务器;若未收到SBi的消息,说明该节点与SBi距离很远,符合次一级服务器的条件;等待服务器A对其同步时的委派信息,正式委派后按照服务器A的工作方式重复步骤2~步骤7,向C级、D级、E级、……的节点进行逐级同步;步骤7:服务器A若收到拒绝信息则立即在原NBi排列顺序中标记被拒绝的节点,选择NBi最大的四个未标记节点,修正为暂定服务器的ID;按照先暂定服务器后普通节点的顺序继续步骤3~步骤7,直到完成所有的同步工作.