2024年6月10日发(作者：)

(19)中华人民共和国国家知识产权局

(12)发明专利说明书

(21)申请号 CN2.2

(22)申请日 2009.03.25

(71)申请人 北京科技大学

地址 100083 北京市海淀区学院路30号

(72)发明人 杨扬 侯国梁 周贤伟 安建伟 杨裕亮

(74)专利代理机构

代理人

(51)

H04W56/00

H04W84/18

(10)申请公布号 CN 101534551 A

(43)申请公布日 2009.09.16

权利要求说明书 说明书 幅图

(54)发明名称

一种基于车辆ad hoc网络拓扑结构

的时间同步方法

(57)摘要

本发明公开了一种基于车辆ad hoc

网络拓扑结构的时间同步方法。根据车辆

总体分布呈现I型、T型或者X型的特

点，以具有GPS设备的车辆作为初始时间

服务器，按照分级的思想，以路由表中的

邻居节点数目为标准，边进行同步，边选

出最佳的次一级时间服务器。选出的次一

级服务器符合道路形状的特点，且满足具

有最多个尚未同步的下一级邻居节点。本

发明的特点在于：同步和次一级服务器的

选择同时进行，防止快速变化的路由造成

选出的次级服务器失效。采用了多播和较

短的同步信息进行对时，当网络进行全局

同步时，使网络产生冲突而瘫痪的机会降

低。服务器仅进行一次插入排序过程，其

他运算完全由其他节点分担，降低了服务

器的运算量。

法律状态

法律状态公告日

法律状态信息

法律状态

权 利 要 求 说 明 书

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，

则

T

ABi1=T

w>Bi1+d

>CSi+δi

>TABi2

>+dSCi=

b>TBi2+

ub>δi

>

其中，TABi1为服务器接收消息时刻TServer，

TBi1为客户端发送消息时刻Tclient，dCSi为

消息从客户端到服务器的传输和处理时间，δi为A与Bi的

时间误差，dSCi为消息从服务器到客户端的传输和处理时间；

假设dCSi＝dSCi＝di，即消息往返的处理、传

输时间相同则消去di得

δi=<

mfrac>TABi1

sub>+TABi2<

/msub>-

TBi1-

TBi2

w>2

即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，直到完成所有的同

步工作。

说 明 书

技术领域

一种基于车辆ad hoc(自组织)网络拓扑结构的时间同步方法是属于移动ad hoc网络

时间同步研究领域。

技术背景

ad hoc网络是一种无基础设施的分布式网络，这类网络由无线移动节点组成自治系

统，每个节点既是主机，又是路由器，不存在集中式的网络管理，可以灵活地适应

拓扑结构的变化。每个节点的处理机具有高度的自治性，又相互协同，甚至有时需

要共享系统中的所有软硬件资源。而时间是分布式网络中重要的坐标，是一个不可

缺少的参数。通常情况下，任何一个时钟和标准时间之间都会存在偏差，而且各个

时钟的速率都有所不同，于是，人们需要经常地为网络各节点进行对时，与标准时

间保持同步。

车载ad hoc网络是一种分布式网络，它具有节点移动速度快、路由变化快的特点，

解决车载ad hoc网络的时间同步问题，有助于设计基于时间的路由算法并提高

QoS(Quality ofService，服务质量)。如果要参考有线IP网络的时间同步服务器的方

法，则需要高性能的设备作为服务器，但是该服务器既不可能跟随车辆移动，国家

或企业也没有计划在路边设置这种专用服务器。另外，虽然IP网络的NTP(网络时

间协议)对网络定时精度较高，但是运算复杂，同步过程漫长，且该协议是一种由

客户端发起的点对点的时间同步法，不适用于路由变化快的车载ad hoc网络的全

局同步；无线传感器网络的同步问题已经有很多机构进行了研究，这种网络是一种

无线分布式网络，与车载ad hoc网络有很多相似之处，但是，移动传感器网络一

般应用在移动速度较慢的特定环境，邻居相对稳定，拓扑结构相对稳定，同样不适

合车载ad hoc网络。

有些轿车配备了GPS导航设备，GPS是一种基于精确时间坐标的定位系统，但由

于种种原因不可能每辆车都安装GPS设备。本发明把具有GPS设备的节点作为一

个时间服务器，从GPS设备中提取时间和速度信息。带有GPS设备的节点虽然有

助于车辆进行同步，但是从实际的角度，作为时间服务器需要付出能量和带宽，从

分布式网络的概念来讲，也不应该使某些节点负荷过重，因为在一个处理机能力基

本相同的网络中，一个奇点可能打破网络的平衡，导致整体性能下降。

因此如何根据车辆行驶的特点，设计一种能适应路由快速变化的车载ad hoc网络

的时间同步方法，是解决车载ad hoc网络协同工作的关键问题之一。

发明内容

本发明提供了一种基于ad hoc网络邻居节点数目，结合车辆行驶的道路形状，对

车载adhoc网络设备进行同步的方法。它依照以下步骤实现：

步骤1：带有GPS设备的节点根服务器A在一个同步周期内，当其速度低于某一

个门限值VT时启动同步，VT值可由环境进行人工调整，

如：市区20km/h，郊区30km/h。首先从其路由表中提取当前所有邻居节点的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，

则

T

ABi1=T

w>Bi1+d

>CSi+δi

>TABi2

>+dSCi=

b>TBi2+

ub>δi

>

其中，TABi1为服务器接收消息时刻TServer，

TBi1为客户端发送消息时刻Tclient，dCSi为

消息从客户端到服务器的传输和处理时间，δi为A与Bi的

时间误差，dSCi为消息从服务器到客户端的传输和处理时间，

假设dCSi＝dSCi＝di，即消息往返的处理、传

输时间相同则消去di可得

δi=<

mfrac>TABi1

sub>+TABi2<

/msub>-

TBi1-

TBi2

w>2

即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，直到完成所有的同

步工作。

附图说明：

图1：车载ad hoc网络示意图

A：带有GPS的根时间服务器

SBi(i＝1，2，3，4)：暂定服务器

Ci：SBi所覆盖的下一级的未同步节点

图2：服务器A参与的同步过程

A：带有GPS的根时间服务器的ID号

Bi(i＝1，2，……，m)：A邻居节点的ID号

SBi(i＝1，2，3，4)：本地暂定服务器节点的ID号

SBj(j＝1，2，3，4，j≠i)：非本地暂定服务器节点的ID号

Ci：SBi所覆盖的下一级未同步节点的ID号

T*(*为任意下标字符)：节点发送和接受消息的本地时钟时刻

d：消息传递和处理时间

NBi：Ci个数

图3：服务器A与非服务器节点同步过程

A：带有GPS的根时间服务器ID号

Bi(i＝1，2，……，m)：A邻居节点的ID号

T*(*为任意下标字符)：节点发送和接受消息的本地时钟时刻

d：消息传递和处理时间

NBi：Ci个数

图4：服务器SB启动服务的衔接过程

A：带有GPS的根时间服务器的ID号

Bi(i＝1，2，……，m)：A邻居节点的ID号

SBi(i＝1，2，3，4)：暂定服务器的ID号

Ci：SBi所覆盖的下一级未同步节点的ID号

T*(*为任意下标字符)：节点发送和接受消息的本地时钟时刻

d：消息传递和处理时间

NBi：Ci个数

NCi：SCi所覆盖的下一级尚未同步节点个数

图5：车载ad hoc网络选举结果例图1

SB1：暂定服务器1

图6：车载ad hoc网络选举结果例图2

A：带有GPS的根时间服务器

SBi(i＝1，2，3，4)：暂定服务器

具体实施方式：

如图1所示，在一个真实的较为复杂的十字路口，直观的分析图中所标识的节点为

最佳次级服务器。根据本发明的算法，可以达到同样的效果，参照图2、3、4，具

体实施方式如下：

1.服务器A在低于某一速度的时刻向其信号覆盖范围(假设为一个标准圆)广播其时

间及其路由中的邻居列表信息，发起同步。低速节点很可能处于某一交通路口，能

够直接同步更多的节点。采取这种多播的方式，虽然消息长，但是效率较高，所有

邻居节点均可收到该消息。

2.接收到消息的各节点进行集合的减运算，即用本地邻居列表减去接收到的列表，

从而得到A节点通过本节点两跳可达的节点。立即回复运算结果的个数和自己的

ID号。虽然采取这种方式可能造成消息传递数量突然增加，但是由于消息的长度

非常短，甚至节点ID号也可省略，由报头获得，因此减小了网络产生严重冲突的

概率。

3.服务器A在接受消息的同时，进行插入排序，服务器A根据排序结果的顺序回

复各个节点发来消息的接受时刻和本消息发送时刻，对于排序靠前的4个节点暂定

为服务器，并在给暂定服务器的消息中包含暂定服务器的ID号。由于优先回复时

间服务器的节点收发消息的时间间隔较短，链路变化一般较小，算法中

dCSi＝dSCi＝di的假设成立的概率更大，因此

对次级服务器的对时精度高于其他普通节点。

4.各个节点根据回复信息进行计算与服务器的时间差，然后根据时间差进行时钟修

正。同步的计算工作完全在各个节点进行，服务器不需要进行复杂的计算工作。另

外，本方法提供了一次检验链路稳定性的措施。

5.次级服务器广播当前发送时刻的时间、自己信号覆盖范围内的次一级未同步节点

ID和4个次级服务器的ID号。这样一次广播完成了三个任务，即对服务器A委派

的汇报、发起其作为服务器的初始化报文和与其他次级服务器进行联系，极大地提

高了效率。

6.次级服务器收到其他次级服务器的委任消息后，对照自己的未同步列表，进行相

似度比较。当相似度很高时，立即回复拒绝消息给根服务器A，A对下一服务器进

行对时的时候，更新次级服务器ID号，直到确定所有的次级服务器或邻居列表中

标记去掉了所有的节点为止。当处于非十字路口的结构时，将会出现找不到4个暂

定服务器的情况，此时达到了道路形状的自适应特征。因此，将次一级服务器个数

定义为4，符合车载ad hoc网络拓扑结构。并且，在最坏情况下(节点分布极不平

均)服务器A每次对某节点发起1次委派信息，将拒绝3个节点，收敛较快。

例如图5中，直观的观察第一次委任的很可能是路口北侧的某四个节点，但是当第

一个次级服务器广播其邻居节点时，其余三个暂定服务器都会给根服务器A发送

拒绝信息，拒绝自己，致使服务器A修改暂定服务器ID，当A修改后，委任服务

器很可能是如图6所示的情况。此时，对SB2进行同步时，包含了新

的暂定服务器ID，这时，由于SB1的等级较高，当它发现自己与

SB2周围未同步节点相似度非常高甚至处于包含状态时，将向A发送

拒绝信息，拒绝SB2。此时，服务器A更新暂定节点ID号，变更为图

1所示，由于他们相似度不高，甚至完全不能直接通信。服务器的委任工作完毕，

此时，服务器A只需完成其他节点的同步工作即可。

7.次级服务器履行服务器职能，对周围节点按照根节点的方式进行同步，一级一级

地沿道路拓扑进行扩展。当某些节点近期已经被其他GPS同步过，或存在其他

GPS设备时，它们返回拒绝参与消息，将不参与任何同步过程。这样避免了同步

信息的不必要的反向传递。