CN101977433B - Averaging Clock Synchronization Method for Wireless Sensor Networks - Google Patents
Averaging Clock Synchronization Method for Wireless Sensor NetworksDownload PDFInfo
- Publication number
- CN101977433B CN101977433BCN 201010538765CN201010538765ACN101977433BCN 101977433 BCN101977433 BCN 101977433BCN 201010538765CN201010538765CN 201010538765CN 201010538765 ACN201010538765 ACN 201010538765ACN 101977433 BCN101977433 BCN 101977433B
- Authority
- CN
- China
- Prior art keywords
- node
- network
- nodes
- time
- wireless sensor
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Synchronisation In Digital Transmission Systems (AREA)
- Mobile Radio Communication Systems (AREA)
Abstract
Description
Translated fromChinese技术领域technical field
本发明属于无线传感器网络技术领域，涉及一种平均时钟同步方法，该方法可用于解决无线传感器网络通信中，如何使网络节点分布式的快速的达到时间同步，提高网络的可扩展性，有效减少能源损耗和延长无线传感器网络寿命的问题。The invention belongs to the technical field of wireless sensor networks, and relates to an average clock synchronization method, which can be used to solve the problem of how to make network nodes distributed and quickly achieve time synchronization in wireless sensor network communication, improve network scalability, and effectively reduce Problems of energy loss and extending the lifetime of wireless sensor networks.
背景技术Background technique
在当今信息技术飞速发展的时代，微电子技术、计算技术和无线通信技术等的进步，推动了低功耗多功能传感器的快速发展，使其在微小体积内能够集成信息采集、数据处理和无线通信等多种功能。无线传感器网络(wireless sensor network，WSN)就是由部署在检测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。人们可以通过传感网络直接感知客观世界，从而极大地扩展现有网络的功能和人类认识世界的能力。WSN的应用前景非常广阔，能够广泛应用于军事、环境检测和预报，健康护理，智能家居、建筑物状态监控、复杂机械监控、城市交通、空间探索、大型车间和仓库管理，以及机场、大型工业园区的安全检测等领域。随着传感器网络的深入研究和广泛应用，传感器网络将逐渐深入到人类生活的各个领域。In today's era of rapid development of information technology, advances in microelectronics technology, computing technology, and wireless communication technology have promoted the rapid development of low-power multifunctional sensors, enabling them to integrate information collection, data processing, and wireless sensors in a small volume. Communication and other functions. Wireless sensor network (wireless sensor network, WSN) is composed of a large number of cheap micro-sensor nodes deployed in the detection area, a multi-hop self-organizing network system formed through wireless communication, and its purpose is to cooperatively perceive, collect and process Information about perceived objects in the network coverage area and sent to observers. People can directly perceive the objective world through sensor networks, thus greatly expanding the functions of existing networks and the ability of human beings to understand the world. WSN has a very broad application prospect and can be widely used in military, environmental detection and forecasting, health care, smart home, building status monitoring, complex machinery monitoring, urban traffic, space exploration, large workshop and warehouse management, as well as airports, large industrial Park security testing and other fields. With the in-depth research and wide application of sensor networks, sensor networks will gradually penetrate into various fields of human life.
传感器节点由一些低功耗设备组成，所以不像传统网络，WSN有它自己的资源约束，包括有限的能源，小的通信范围，低带宽和每个节点有限的处理和存储能力；同时WSN还有设计约束，即基于监测的环境和对于应用依赖性。传感器网络中多数节点是无人值守的，每个节点电池组仅携带少量有限的能量，是传感器节点的主要能源，即使是进行侦听通信也会消耗大量能量。由于上述的那些局限性，使得能量的消耗成为问题，在复杂的环境里不能轻易更换电池或传感器节点，当电量耗尽时，传感器节点就无法进行正常工作，会影响网络的寿命，所以能量的保存有很重要的作用。Sensor nodes are composed of some low-power devices, so unlike traditional networks, WSN has its own resource constraints, including limited energy, small communication range, low bandwidth, and limited processing and storage capabilities of each node; at the same time, WSN also There are design constraints that are based on the monitored environment and dependencies on the application. Most of the nodes in the sensor network are unattended, and the battery pack of each node only carries a small amount of limited energy, which is the main energy source of the sensor nodes. Even listening communication will consume a lot of energy. Due to the above limitations, energy consumption becomes a problem. In complex environments, batteries or sensor nodes cannot be easily replaced. When the battery is exhausted, sensor nodes cannot work normally, which will affect the life of the network. Therefore, energy Preservation plays an important role.
在无线传感器网络中节点时钟同步是一个公开的研究课题，这对于路由发送和节能是非常重要的。当信号冲突和重复传送都很少时可以节省能量，节点是间歇性工作时也可以节省能量。传感器所获得的数据必须具有准确的时间和位置信息，否则采集的信息也是不完整的。此外，传感器节点的数据融合、时分多址TDMA的定时、休眠周期的同步等都要求传感器节点具有统一的时间。全局时间同步允许节点间协作并按预定时间顺序传送数据。在节点间时间同步的基础上，用时间序列的目标位置检测可以估计目标的运行速度和方向，通过测量声音的传播时间能够确定节点到声源的距离或声源的位置。Node clock synchronization in wireless sensor networks is an open research topic, which is very important for routing and energy saving. Energy can be saved when signal collisions and repeated transmissions are rare, and energy can also be saved when nodes are intermittently operating. The data obtained by the sensor must have accurate time and location information, otherwise the collected information is incomplete. In addition, the data fusion of sensor nodes, the timing of time division multiple access TDMA, and the synchronization of sleep cycles all require sensor nodes to have a unified time. Global time synchronization allows nodes to cooperate and deliver data in predetermined time order. On the basis of time synchronization between nodes, the speed and direction of the target can be estimated by using time series target position detection, and the distance from the node to the sound source or the position of the sound source can be determined by measuring the propagation time of the sound.
NTP(Network Time Protocol)协议是Internet上广泛使用的网络时间协议，但只适用于结构相对稳定、链路很少失败的有线网络系统；GPS系统能够以纳秒级精度与世界标准时间UTC(Universal TimeCoordinated)保持同步，但需要配置固定的高成本接收机，同时在室内、森林或水下等有掩体的环境中无法使用GPS系统。因此，考虑到传感器网络的特点，以及能量、价格和体积等方面的约束，它们都不适合应用在传感器网络中。Jeremy Elson和Kay Romer在2002年8月的Hot Nets-I国际会议上首次提出和阐述了传感器网络中的时间同步机制的研究课题，在传感器网络研究领域引起了关注。大学和科研机构纷纷开始对这个领域进行深入研究，提出了多种时间同步机制，其中RBS(Reference BroadcastSynchronization)、TINY/MINI-SYNC和TPSN(Timing-sync Protocol forSensor Networks)被认为是三种基本的同步机制。RBS机制是基于接受者-接受者的时钟同步：一个节点广播时钟参考分组，广播域内的两个节点分别采用本地时钟记录参考分组的到达时间，通过交换记录时间来实现它们之间的时钟同步。广播域内的所有节点不得不共享接收信标的时间信息，需要交换大量的数据。TINY/MINI-SYNC是简单的轻量级的同步机制：假设节点的时钟漂移遵循线性变化，那么两个节点之间的偏移也是线性的，可通过交换时标分组来估计两个节点间的最优匹配偏移量。精确的估计不确定的时钟参数。TPSN采用层次结构实现整个网络节点的时间同步：所有节点按照层次结构进行逻辑分级，通过基于发送者-接受者的节点对方式，每个节点能够与上一级的某个节点进行同步，从而实现所有节点都与根节点的时间同步。其它一些同步机制还有延迟测量时间同步(delay measurement time synchronization，DMTS)机制，lightweighttree-based synchronization(LTS)同步算法，Flooding Time SynchronizationProtocol(FTSP)，Pairwise broadcast synchronization(PBS)等等。在传统的同步操作中，两个节点进行信息交换要传递两次数据包，数据包中包含有节点接收到信息时的本地时间和信息里的时间值，在第二次数据包被接收到时才有足够的信息计算包延时和节点间的时间差值，具体通信过程如图2所示。这样的工作机制使得网络节点的通信只能是阶梯状结构，也就是网络节点时间值都只能同步于一个根节点的时钟。一般来说，这些同步协议的工作机制是使用网络外部节点作为参考基点(携带有GPS的硬件时间同步器件或UTC协调世界时间)，或是使用网络内部的节点作为根节点，网络中其他节点通过与这些参考节点进行通信，交换数据包信息，最终同步于这些参考节点，形成阶梯结构。NTP (Network Time Protocol) protocol is a network time protocol widely used on the Internet, but it is only suitable for wired network systems with relatively stable structure and few link failures; TimeCoordinated) to maintain synchronization, but it needs to configure a fixed high-cost receiver, and at the same time, the GPS system cannot be used in environments with shelters such as indoors, forests or underwater. Therefore, considering the characteristics of sensor networks, as well as the constraints of energy, price and volume, they are not suitable for application in sensor networks. Jeremy Elson and Kay Romer first proposed and expounded the research topic of time synchronization mechanism in sensor network at the Hot Nets-I International Conference in August 2002, which attracted attention in the field of sensor network research. Universities and scientific research institutions have begun to conduct in-depth research in this field, and proposed a variety of time synchronization mechanisms, among which RBS (Reference Broadcast Synchronization), TINY/MINI-SYNC and TPSN (Timing-sync Protocol for Sensor Networks) are considered to be three basic synchronization mechanism. The RBS mechanism is based on receiver-receiver clock synchronization: a node broadcasts a clock reference packet, and two nodes in the broadcast domain use their local clocks to record the arrival time of the reference packet, and achieve clock synchronization between them by exchanging the recorded time. All nodes in the broadcast domain have to share the time information of receiving the beacon, which requires exchanging a large amount of data. TINY/MINI-SYNC is a simple lightweight synchronization mechanism: assuming that the clock drift of the node follows a linear change, then the offset between the two nodes is also linear, and the time-scale packet exchange between the two nodes can be estimated. Optimal match offset. Accurate estimation of uncertain clock parameters. TPSN adopts a hierarchical structure to realize time synchronization of the entire network nodes: all nodes are logically classified according to the hierarchical structure, and each node can be synchronized with a node of the upper level through the node pair based on the sender-receiver, thereby realizing All nodes are synchronized with the time of the root node. Some other synchronization mechanisms include delay measurement time synchronization (DMTS) mechanism, lightweighttree-based synchronization (LTS) synchronization algorithm, Flooding Time Synchronization Protocol (FTSP), Pairwise broadcast synchronization (PBS) and so on. In the traditional synchronous operation, two nodes need to transmit two data packets to exchange information. The data packet contains the local time when the node receives the information and the time value in the information. When the second data packet is received There is enough information to calculate the packet delay and the time difference between nodes. The specific communication process is shown in Figure 2. Such a working mechanism makes the communication of network nodes only have a ladder structure, that is, the time value of network nodes can only be synchronized with the clock of one root node. Generally speaking, the working mechanism of these synchronization protocols is to use the external nodes of the network as the reference point (hardware time synchronization device with GPS or UTC coordinated universal time), or use the internal nodes of the network as the root node, and other nodes in the network pass Communicate with these reference nodes, exchange data packet information, and finally synchronize with these reference nodes to form a ladder structure.
综上所述，现有的时钟同步协议由于采用上述的这种级层结构逐层进行同步，因而对于大规模的网络来说，随着层数的增加，使得节点间通信时延误差累积增加，不仅影响了同步精度和收敛速度，而且也限制了网络的可扩展性；同时由于这种结构还要求每个网络节点的所有邻居节点之间都能够相互进行通信，使得这种结构仅适用于同步边密度较大的高密度网络，限制了对边密度较小的低密度网络的同步实现。To sum up, the existing clock synchronization protocol adopts the above-mentioned hierarchical structure to synchronize layer by layer. Therefore, for large-scale networks, as the number of layers increases, the cumulative increase in communication delay errors between nodes , which not only affects the synchronization accuracy and convergence speed, but also limits the scalability of the network; at the same time, because this structure also requires all neighbor nodes of each network node to be able to communicate with each other, this structure is only suitable for A high-density network with a high density of synchronous edges limits the synchronization implementation of a low-density network with a small density of opposite edges.
发明内容Contents of the invention
本发明的目的在于克服上述现有协议的不足，提出了一种适用于任意的高密度或低密度网络的无线传感器网络的平均时钟同步方法，以减少节点间通信时延误差的累积，提高同步精度和收敛速度，增强网络的可扩展性。The purpose of the present invention is to overcome the deficiencies of the above-mentioned existing protocols, and proposes an average clock synchronization method suitable for wireless sensor networks of arbitrary high-density or low-density networks, so as to reduce the accumulation of communication delay errors between nodes and improve synchronization accuracy and convergence speed, and enhance the scalability of the network.
为实现上述目的，本发明的技术方案包括如下步骤：To achieve the above object, the technical solution of the present invention comprises the following steps:
(1)将无线传感器网络的拓扑结构抽象成图模型，绘制出这个图模型G；(1) Abstract the topology structure of the wireless sensor network into a graph model, and draw this graph model G;
(2)对图模型G＝{N，V，E}中的节点进行随机编号1，2，...，N，其中，N表示网络中传感器节点总数，V表示传感器节点集，E表示所有无向边的集合；(2) Randomly number the nodes in the graph model G={N, V, E} 1, 2, ..., N, where N represents the total number of sensor nodes in the network, V represents the sensor node set, and E represents all set of undirected edges;
(3)将初始时刻网络节点的时钟值作为节点初始值，标记为T1(0)，T2(0)，...，TN(0)；(3) Take the clock value of the network node at the initial moment as the initial value of the node, marked as T1 (0), T2 (0), ..., TN (0);
(4)在对图模型G的操作流程中，由切换信号s(k)控制的边集合{eij}所对应的节点按如下步骤同时进行通信，并保证不会引起通信冲突，其中k是生成边集合{eij}的迭代次数，k的取值不同对应的边集合{eij}也不同，当网络中所有的边都通信了一次时，将k置1，重新迭代：(4) In the operation process of the graph model G, the nodes corresponding to the edge set {eij } controlled by the switching signal s(k) communicate simultaneously according to the following steps, and ensure that no communication conflicts will be caused, where k is The number of iterations to generate the edge set {eij }, the value of k corresponds to a different edge set {eij }, when all the edges in the network have communicated once, set k to 1 and iterate again:
(4a)边集合{eij}中的边eij对应的节点i与j进行通信，节点i将它自己的本地时间Ti1发送给节点j，节点j在Tj1时刻接收到这个数据包；(4a) The node i corresponding to the edge eij in the edge set {eij } communicates with j, node i sends its own local time Ti1 to node j, node j receives this data packet at time Tj1 ;
(4b)节点j接收到来自节点i的数据包后，将自己此时的本地时间Tj1回复给节点i，节点i在Ti2时刻接收到这个数据包后，计算并更新本地时间为：T′i2＝(Tj1+Ti2+tau(1))/2，其中tau(1)是节点j发送给节点i数据包时的传递时间；(4b) After node j receives the data packet from node i, it will reply its own local time Tj1 to node i at this time. After node i receives this data packet at Ti2 time, it will calculate and update the local time as: T ′i2 =(Tj1 +Ti2 +tau(1))/2, where tau(1) is the delivery time when node j sends data packets to node i;
(4c)节点i在更新本地时间的同时，将自己此时的本地时间Ti2回复给节点j，当节点j在Ti2时刻接收到这个数据包后，计算并更新本地时间为：T′j2＝(Ti2+Tj2+tau(2))/2，其中tau(2)是节点i发送给节点j数据包时的传递时间；(4c) While updating the local time, node i replies its current local time Ti2 to node j. When node j receives the data packet at Ti2 time, it calculates and updates the local time as: T′j2 =(Ti2 +Tj2 +tau(2))/2, wherein tau(2) is the transfer time when node i sends to node j data packets;
(5)重复执行步骤(4)，直到网络节点间的最大差量渐进趋于一个允许范围内的误差，网络达到平均时钟同步，网络节点持续工作，稳定保持时钟同步状态。(5) Step (4) is repeated until the maximum difference between network nodes gradually tends to an error within the allowable range, the network reaches the average clock synchronization, the network nodes continue to work, and maintain a stable clock synchronization state.
上述的方法中，步骤(1)所描述的图模型，用以表示无线传感器网络的拓扑结构，图中设有N个节点，每一个节点i代表一个传感器，记录本地时钟，其中i＝1，2，...，N，节点间的连接边eij代表节点间能传递数据包进行通信，其中j＝1，2，...，N，i≠j。In the above-mentioned method, the graphical model described in step (1) is used to represent the topology of the wireless sensor network. In the figure, there are N nodes, each node i represents a sensor, and records the local clock, wherein i=1, 2, . . . , N, the connection edge eij between nodes represents that data packets can be transmitted between nodes for communication, where j=1, 2, . . . , N, i≠j.
上述的方法中，步骤(4)所述的切换信号s(k)，用来控制边集{eij}在同一时刻分别进行通信，保证了平均时钟同步的分布式操作。In the above method, the switching signal s(k) in step (4) is used to control the edge set {eij } to communicate separately at the same time, which ensures the distributed operation with average clock synchronization.
本发明由于不依赖于任何参考节点，网络内部任意一个节点都可作为起始节点开启分布式的平均时钟同步操作，所以适合任意的高密度或低密度网络；同时由于本发明采用折中求平均的方法，即通过更新本地时间的公式，使节点时间收敛于中间平均值，所以能较稳定的保持同步状态，减少节点间通信时延误差的累积，提高了网络的可扩展性。Since the present invention does not depend on any reference node, any node in the network can be used as a starting node to start a distributed average clock synchronization operation, so it is suitable for any high-density or low-density network; at the same time, because the present invention uses a compromise average The method, that is, by updating the formula of the local time, the node time converges to the average value, so it can maintain a stable synchronization state, reduce the accumulation of communication delay errors between nodes, and improve the scalability of the network.
附图说明Description of drawings
图1是本发明的流程框图；Fig. 1 is a block flow diagram of the present invention;
图2是现有方法的时钟同步示意图；Fig. 2 is the clock synchronization schematic diagram of existing method;
图3是本发明的平均时钟同步示意图；Fig. 3 is a schematic diagram of average clock synchronization of the present invention;
图4是本发明实施例中无线传感器网络的图模型；Fig. 4 is the graph model of wireless sensor network in the embodiment of the present invention;
图5是本发明实施例中网络节点的本地时钟达到同步时的变化曲线图；Fig. 5 is a change curve diagram when the local clocks of the network nodes are synchronized in the embodiment of the present invention;
图6是本发明仿真实验采用的20节点的不同边密度的网络图；Fig. 6 is the network diagram of the different edge densities of 20 nodes that the simulation experiment of the present invention adopts;
图7是图6对应的仿真实验结果图；Fig. 7 is the simulation experiment result diagram corresponding to Fig. 6;
图8是本发明仿真实验采用的随机生成的50节点的不同边密度的网络图；Fig. 8 is the network diagram of the different edge densities of the randomly generated 50 nodes that the simulation experiment of the present invention adopts;
图9是图8对应的仿真实验结果图。FIG. 9 is a graph of simulation experiment results corresponding to FIG. 8 .
具体实施方式Detailed ways
本发明主要包括两个部分：初始化节点，分布式平均时钟同步。具体的步骤，参照图1描述如下：The present invention mainly includes two parts: initialization node and distributed average clock synchronization. The specific steps are described as follows with reference to Figure 1:
步骤1.初始化节点。
本实施例主要针对一个具体的无线传感器网络实现平均时钟同步，该网络的图模型如图4所示，用以表示无线传感器网络的拓扑结构，图4中有10个节点，每一个节点i代表一个传感器，记录本地时钟，其中i＝1，2，...，10，图4中的边eij代表节点间能传递数据包进行通信，其中j＝1，2，...，10，i≠j；对该图4中的10个节点进行随机编号1，2...，10，并随机生成一组服从均值为0.5，方差为1的高斯分布的值作为节点初始值，即-0.9676，0.4115，1.0992，0.3438，0.3712，1.5497，0.3698，-0.7042，1.7921，0.0491。This embodiment is mainly aimed at a specific wireless sensor network to achieve average clock synchronization. The graph model of the network is shown in Figure 4, which is used to represent the topology of the wireless sensor network. There are 10 nodes in Figure 4, and each node i represents A sensor records the local clock, where i=1, 2, ..., 10, the edge eij in Figure 4 represents the ability to transmit data packets between nodes for communication, where j = 1, 2, ..., 10, i≠j; randomly number the 10 nodes in Figure 4 1, 2..., 10, and randomly generate a set of values that obey a Gaussian distribution with a mean of 0.5 and a variance of 1 as the initial value of the node, namely - 0.9676, 0.4115, 1.0992, 0.3438, 0.3712, 1.5497, 0.3698, -0.7042, 1.7921, 0.0491.
步骤2.分布式平均时钟同步。
切换信号s(k)用来控制边集{eij}在同一时刻分别进行通信，即s(k)＝{eij}，以保证不会引起通信冲突，实现平均时钟同步的分布式操作，其中k是生成边集合{eij}的迭代次数，取值为1，2，3，4，5。The switching signal s(k) is used to control the edge set {eij } to communicate separately at the same time, that is, s(k)={eij }, so as to ensure that there will be no communication conflicts and realize the distributed operation of the average clock synchronization. Where k is the number of iterations to generate the edge set {eij }, and the values are 1, 2, 3, 4, 5.
2.1)当k＝1时，s(1)＝{e12，e34，e57，e8，10}，即节点1与节点2，节点3与节点4，节点5与节点7，节点8与节点10同时按如下步骤传递数据包进行通信，为方便叙述，用i表示1，3，5，8，相对应的j的取值分别为2，4，7，10：2.1) When k=1, s(1)={e12 , e34 , e57 ,
2.1a)如图3所示，节点i将它的本地时间Ti1发送给节点j，节点j在本地时间为Tj1时接收到数据Ti1；2.1a) As shown in Figure 3, node i sends its local time Ti1 to node j, and node j receives data Ti1 when the local time is Tj1 ;
2.1b)节点j接收到来自节点i的数据后，将自己的本地时间Tj1回复给节点i，节点i在Ti2时刻接收到这个数据包后，计算并更新本地时间为：T′i2＝(Tj1+Ti2+tau(1))/2，其中tau(1)是节点j发送给节点i数据包时的传递时间；2.1b) After node j receives the data from node i, it replies its own local time Tj1 to node i. After node i receives this data packet at Ti2 time, it calculates and updates the local time as: T′i2 = (Tj1 +Ti2 +tau(1))/2, where tau(1) is the delivery time when node j sends a packet to node i;
2.1c)节点i在更新本地时间的同时，将自己的本地时间Ti2回复给节点j，节点j在Tj2时刻接收到这个数据包后，计算并更新本地时间为：T′j2＝(Ti2+Tj2+tau(2))/2，其中tau(2)是节点i发送给节点j数据包时的传递时间；2.1c) While updating the local time, node i replies its own local time Ti2 to node j. After receiving the data packet at Tj2 , node j calculates and updates the local time as: T′j2 =(Ti2 +Tj2 +tau(2))/2, where tau(2) is the delivery time when node i sends the packet to node j;
2.2)当k＝2时，s(2)＝{e23，e48，e9，10}，即节点2与节点3，节点4与节点8，节点9与节点10同时按步骤2.1b)～2.1d)传递数据包进行通信，为方便叙述，用i表示2，4，9，相对应的j的取值分别为3，8，10，完成节点本地时间的更新；2.2) When k=2, s(2)={e23 , e48 , e9 , 10 }, that is,
2.3)当k＝3时，s(3)＝{e26，e7，10}，即节点2与节点6，节点7与节点10同时按步骤2.1b)～2.1d)传递数据包进行通信，为方便叙述，用i表示2，7，相对应的j的取值分别为6，10，完成节点本地时间的更新；2.3) When k=3, s(3)={e26 , e7 , 10 }, that is,
2.4)当k＝4时，s(4)＝{e58}，即节点5与节点8按步骤2.1b)～2.1d)传递数据包进行通信，为方便叙述，用i表示5，相对应的j的取值分别为8完成节点本地时间的更新；2.4) When k=4, s(4)={e58 }, that is,
2.5)当k＝5时，s(5)＝{e67}，即节点6与节点7按步骤2.1b)～2.1d)传递数据包进行通信，为方便叙述，用i表示6，相对应的j的取值分别为7，完成节点本地时间的更新；2.5) When k=5, s(5)={e67 }, that is, node 6 and
2.6)在网络中所有的边都通信了一次后，将k置1，重复执行步骤2.1)～2.5)，直到网络节点渐进趋于一个允许范围内的误差，网络达到平均时钟同步，网络节点持续工作，保持时钟同步状态。2.6) After all the edges in the network have communicated once, set k to 1, and repeat steps 2.1) to 2.5), until the network nodes gradually tend to an error within the allowable range, the network reaches the average clock synchronization, and the network nodes continue to work, keeping the clock synchronized state.
步骤2.6)执行结束后，得到如图5所示的同步结果，其中图5(a)是网络节点的本地时间随迭代次数的变化曲线，图5(b)是网络节点的本地时间与均值的差量随迭代次数的变化曲线，图5中迭代次数是指网络中所有边都通信一次时网络达到同步所经历的代数。由于传感器节点的本地时钟是随时间变化的，所以图5(a)所示的同步曲线呈线性增加现象；各个节点在同一个时刻的本地时间与均值的差量是趋于零的，达到了平均时钟同步，即图5(b)所示曲线。Step 2.6) After the execution is completed, the synchronization result as shown in Figure 5 is obtained, wherein Figure 5 (a) is the curve of the local time of the network node with the number of iterations, and Figure 5 (b) is the curve of the local time of the network node and the mean value The change curve of the difference with the number of iterations. The number of iterations in Figure 5 refers to the number of generations that the network has experienced to achieve synchronization when all edges in the network communicate once. Since the local clock of the sensor node changes with time, the synchronization curve shown in Figure 5(a) increases linearly; the difference between the local time and the mean value of each node at the same moment tends to zero, reaching The average clock synchronization is the curve shown in Figure 5(b).
本发明的效果可以通过以下仿真实验进一步说明：Effect of the present invention can be further illustrated by following simulation experiments:
1.仿真条件：1. Simulation conditions:
在CPU为core22.4GHZ、内存2G、WINDOWS XP系统上使用MATLAB进行了仿真。The simulation is carried out using MATLAB on the CPU core22.4GHZ, memory 2G, WINDOWS XP system.
2.仿真内容：2. Simulation content:
仿真实验分成两组进行：The simulation experiments are divided into two groups:
第一组实验采用20个节点不同边密度的网络作为实验对象，网络图如图6所示，其中图6(a)为20节点，边密度为0.1632的网络图，图6(b)为20节点，边密度为0.5105的网络图，图6(c)为20节点，边密度为0.6579的网络图；The first group of experiments used a network with 20 nodes and different edge densities as the experimental object. A network graph with a node and edge density of 0.5105, and Figure 6(c) is a network graph with 20 nodes and an edge density of 0.6579;
第二组实验采用随机生成的网络作为实验对象，即分别对随机生成的20，50，100，150和200个节点，不同边密度的网络进行实验，其中50节点的网络图如图8所示，其中图8(a)为随机生成的50节点，边密度为0.3的网络图，图8(b)为随机生成的50节点，边密度为0.5的网络图，图8(c)为随机生成的50节点，边密度为0.8的网络图。The second group of experiments uses a randomly generated network as the experimental object, that is, randomly generated 20, 50, 100, 150 and 200 nodes, respectively, and conducts experiments on networks with different edge densities. The network diagram of 50 nodes is shown in Figure 8 , where Figure 8(a) is a randomly generated network graph with 50 nodes and an edge density of 0.3, Figure 8(b) is a randomly generated network graph with 50 nodes and an edge density of 0.5, and Figure 8(c) is a randomly generated network graph A network graph with 50 nodes and an edge density of 0.8.
实验中随机生成的节点初始时间值服从均值为0.5，方差为1的高斯分布；每一次通信的时延tau是随机生成的，服从均值为1.0000e-003，标准差为1.0000e-006的高斯分布；设定的精度阈值为1.0000e-006。In the experiment, the randomly generated node initial time value obeys a Gaussian distribution with a mean value of 0.5 and a variance of 1; the delay tau of each communication is randomly generated, and obeys a Gaussian distribution with a mean value of 1.0000e-003 and a standard deviation of 1.0000e-006 distribution; the set accuracy threshold is 1.0000e-006.
3.仿真结果3. Simulation results
第一组实验的仿真实验结果如图7所示，其中图7(a)是图6(a)对应的网络节点本地时间与均值的差量随迭代次数的变化曲线，图7(b)是图6(a)对应的网络节点的本地时间随迭代次数的变化曲线，图7(c)是图6(b)对应的网络节点本地时间与均值的差量随迭代次数的变化曲线，图7(d)是图6(b)对应的网络节点的本地时间随迭代次数的变化曲线，图7(e)是图6(c)对应的网络节点本地时间与均值的差量随迭代次数的变化曲线，图7(f)是图6(c)对应的网络节点的本地时间随迭代次数的变化曲线。The simulation results of the first group of experiments are shown in Figure 7, where Figure 7(a) is the curve of the difference between the local time and the mean value of the network node corresponding to Figure 6(a) with the number of iterations, and Figure 7(b) is Figure 6(a) corresponds to the change curve of the local time of the network node with the number of iterations, and Figure 7(c) is the change curve of the difference between the local time and the mean value of the network node corresponding to Figure 6(b) with the number of iterations, Figure 7 (d) is the change curve of the local time of the network node corresponding to Figure 6(b) with the number of iterations, and Figure 7(e) is the change of the difference between the local time and the mean value of the network node corresponding to Figure 6(c) with the number of iterations Curve, Fig. 7(f) is the change curve of the local time of the network node corresponding to Fig. 6(c) with the number of iterations.
第二组实验中50节点的网络图的仿真实验结果如图9所示，其中图9(a)是图8(a)对应的网络节点本地时间与均值的差量随迭代次数的变化曲线，图9(b)是图8(a)对应的网络节点的本地时间随迭代次数的变化曲线，图9(c)是图8(b)对应的网络节点本地时间与均值的差量随迭代次数的变化曲线，图9(d)是图8(b)对应的网络节点的本地时间随迭代次数的变化曲线，图9(e)是图8(c)对应的网络节点本地时间与均值的差量随迭代次数的变化曲线，图9(f)是图8(c)对应的网络节点的本地时间随迭代次数的变化曲线。The simulation experiment results of the network diagram of 50 nodes in the second group of experiments are shown in Figure 9, wherein Figure 9(a) is the curve of the difference between the local time and the mean value of the network node corresponding to Figure 8(a) with the number of iterations, Figure 9(b) is the change curve of the local time of the network node corresponding to Figure 8(a) with the number of iterations, and Figure 9(c) is the difference between the local time and the mean value of the network node corresponding to Figure 8(b) with the number of iterations , Figure 9(d) is the change curve of the local time of the network node corresponding to Figure 8(b) with the number of iterations, and Figure 9(e) is the difference between the local time of the network node corresponding to Figure 8(c) and the mean Figure 9(f) is the change curve of the local time of the network node corresponding to Figure 8(c) with the number of iterations.
两组实验具体的实验数据如表1、表2所示，其中表1中数据是对第一组实验进行测试统计的实验结果，注释1代表对相同的时间初始值测试10次求平均，注释2代表随机生成10组时间初始值测试10次求平均。The specific experimental data of the two groups of experiments are shown in Table 1 and Table 2. The data in Table 1 are the experimental results of the test statistics for the first group of experiments.
表2中数据是对第二组实验进行测试统计的实验结果。The data in Table 2 are the experimental results of the test statistics for the second set of experiments.
表1本实验方法第一组的实验结果Table 1 The experimental results of the first group of this experimental method
表2本实验方法第二组的实验结果Table 2 The experimental results of the second group of this experimental method
从仿真实验结果图和表1、表2中都可以看出，本发明对于任意的高密度或低密度网络，都能够达到平均时钟同步，而且不依赖于任何外部基点或某个根节点；网络节点收敛于节点的时间平均值，能较稳定的保持同步状态，使本发明更具有鲁棒性和合理性；减少了节点间通信时延误差的累积，可适用于大规模网络，提高了网络的可扩展性。As can be seen from the simulation experiment result diagram and Table 1 and Table 2, the present invention can achieve average clock synchronization for any high-density or low-density network, and does not depend on any external base point or a certain root node; the network The node converges to the time average value of the node, which can maintain the synchronization state more stably, which makes the present invention more robust and rational; reduces the accumulation of communication delay errors between nodes, is applicable to large-scale networks, and improves the network scalability.
Claims (2)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN 201010538765CN101977433B (en) | 2010-11-09 | 2010-11-09 | Averaging Clock Synchronization Method for Wireless Sensor Networks |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN 201010538765CN101977433B (en) | 2010-11-09 | 2010-11-09 | Averaging Clock Synchronization Method for Wireless Sensor Networks |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101977433A CN101977433A (en) | 2011-02-16 |
| CN101977433Btrue CN101977433B (en) | 2013-03-20 |
Family
ID=43577271
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN 201010538765Expired - Fee RelatedCN101977433B (en) | 2010-11-09 | 2010-11-09 | Averaging Clock Synchronization Method for Wireless Sensor Networks |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN101977433B (en) |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102196554A (en)* | 2011-06-10 | 2011-09-21 | 西安电子科技大学 | Method for realizing average clock synchronization of wireless sensor network through cluster averaging |
| CN103178917B (en)* | 2011-12-26 | 2015-11-11 | 中国移动通信集团公司 | A kind of clock synchronizing method of collaboration communication, system and information taken node |
| CN102833853B (en)* | 2012-08-31 | 2015-08-12 | 北京联合大学 | Based on the node of the wireless sensor network that Embedded GPS module clock corrects |
| CN103945524B (en)* | 2014-04-30 | 2017-11-10 | 中国科学院上海微系统与信息技术研究所 | Distributed wireless Sensor Network method for synchronizing time |
| CN110278047A (en)* | 2018-03-16 | 2019-09-24 | 阿里巴巴集团控股有限公司 | The method, device and equipment of synchronous for clock, setting Streaming Media frame pts value |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101483908A (en)* | 2009-02-18 | 2009-07-15 | 王翥 | Wireless sensor network node |
| CN101511099A (en)* | 2009-04-01 | 2009-08-19 | 南京邮电大学 | Collection method for wireless sensor network data based on time series prediction model |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8824449B2 (en)* | 2009-03-05 | 2014-09-02 | Chess Et International Bv | Synchronization of broadcast-only wireless networks |
- 2010
- 2010-11-09CNCN 201010538765patent/CN101977433B/ennot_activeExpired - Fee Related
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101483908A (en)* | 2009-02-18 | 2009-07-15 | 王翥 | Wireless sensor network node |
| CN101511099A (en)* | 2009-04-01 | 2009-08-19 | 南京邮电大学 | Collection method for wireless sensor network data based on time series prediction model |
Also Published As
| Publication number | Publication date |
|---|---|
| CN101977433A (en) | 2011-02-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN104519563B (en) | One kind layering wireless sensor network time synchronization method | |
| Lasassmeh et al. | Time synchronization in wireless sensor networks: A survey | |
| CN102196554A (en) | Method for realizing average clock synchronization of wireless sensor network through cluster averaging | |
| CN101977433B (en) | Averaging Clock Synchronization Method for Wireless Sensor Networks | |
| Qiu et al. | STETS: A novel energy-efficient time synchronization scheme based on embedded networking devices | |
| CN103178917B (en) | A kind of clock synchronizing method of collaboration communication, system and information taken node | |
| CN103647629B (en) | A kind of Internet of Things method for synchronizing time based on feedback mechanism | |
| Chalapathi et al. | E-SATS: An efficient and simple time synchronization protocol for cluster-based wireless sensor networks | |
| Khediri et al. | Analysis study of time synchronization protocols in wireless sensor networks | |
| CN102970677B (en) | Wireless communication method based on monitoring Gossip average common view technology | |
| Chaudhari et al. | Energy-efficient estimation of clock offset for inactive nodes in wireless sensor networks | |
| CN103916952B (en) | A kind of coal mine underground Internet of Things time synchronized and energy control method | |
| Zhou et al. | Time synchronization in industrial internet of things: A survey | |
| Aissaoua et al. | A distributed consensus-based clock synchronization protocol for wireless sensor networks | |
| Mirza et al. | Energy-efficient ranging for post-facto self-localization in mobile underwater networks | |
| Merkel et al. | Firefly-inspired synchronization for energy-efficient distance estimation in mobile ad-hoc networks | |
| Xiong et al. | Randomized and Efficient Time Synchronization in Dynamic Wireless Sensor Networks: A Gossip‐Consensus‐Based Approach | |
| Nayyer et al. | A comparative study of time synchronization protocols in wireless sensor network | |
| Li et al. | An improved hybrid time synchronization approach in wireless sensor networks for smart grid application | |
| He et al. | Clock synchronization for random mobile sensor networks | |
| Ni et al. | Semantic Sensor Net: an extensible framework | |
| CN104540212B (en) | On-demand clock synchronization method for wireless sensor network based on AODV routing protocol | |
| Fang et al. | ELOTS: Energy-efficient local optimization time synchronization algorithm for WirelessHART networks | |
| Khan et al. | Time synchronization for mobile wireless sensor network | |
| Guo et al. | An Improved Clock Synchronization Algorithm for Wireless Sensor Network of Underground Water Supply Pipline |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | Granted publication date:20130320 Termination date:20181109 | |
| CF01 | Termination of patent right due to non-payment of annual fee |