Background technology
Wireless Ad Hoc network is to be collectively constituted by multiple terminal nodes with radio transmission-receiving function, communication between them is not required to the support of the network infrastructure (such as base station or focus) fixed, each terminal node directly can communicate with other nodes in the range of less radio-frequency, and (jumping) can be forwarded to realize more telecommunication by information between node, node in network can move freely, and the wireless topologies of network can arbitrarily change and cannot predict.In general, the route between Ad Hoc network interior joint comprises multi-hop (repeatedly forwarding), and the most this network is also referred to as multi-hop wireless Ad Hoc network.
Performance and the mode of the time synchronized between Wireless Ad Hoc network interior joint are affected greatly by the working method of wireless MAC (medium access control), the existing wireless MAC for building Wireless Ad Hoc network mainly has Wi-Fi, ZigBee and bluetooth (Bluetooth, BT).In current Wireless Ad Hoc network, most of time synchronous protocol is based on synchronous mode two-by-two.In this mode, carry out between two nodes synchronizing at least to need a synchronization message.In whole network range, to realize time synchronized, can node between constantly repeat this process, until oneself local clock or time are adjusted by each node according to reference clock or time.Mainly there are following three kinds of methods of synchronization:
1) only by a message when simplest time synchronized two-by-two is to synchronize between the two nodes.As it is shown in figure 1, the t1 moment, node i sends a time synchronization information to node j, and is embedded as timestamp by time t1.When receiving message, node j obtains a local time stamp t2 from local clock.Using the difference of two timestamps of t1, t2 as a tolerance of the time migration δ between node i and node j, D represents unknown propagation delay, node i timing sends this time synchronization information to node j continuously, node j can calculate the local clock frequency deviation relative to node i, thus adjust the clock of oneself, it is achieved Tong Bu with the clock of node i.
2) the another kind method of synchronization more accurately is to use two synchronization messages.As in figure 2 it is shown, comprise replying message of timestamp t2, t3 at t3 moment node j to node i one.In the t4 moment, node i receives and replies message, and node i determines propagation delay and frequency deviation more accurately by following equation, and is shared by follow-up message and node j.
3) also having a kind of synchronous method is the time difference according to the different node of same message arrival to realize synchronizing.Different from the synchronous mode of above-mentioned transmission-reception, receiving terminal-receiving terminal is used to synchronize criterion agreement, in broadcast environment (broadcast does not comprise timestamp), these nodes are nearly simultaneously received message, and receiving node can calculate time deviation each other by exchanging the respective reception time.As it is shown on figure 3, have two receiving nodes j, k, as long as three message can realize synchronizing between node j, k.
The precision of the current time synchronized between Wireless Ad Hoc network interior joint is the highest, can only achieve several us (microsecond), main cause is that the time delay of radio communication is uncertain caused, specifically includes forward delay interval, reception delay, access time delay and propagation delay.Occur that wireless channel uses MAC layer timestamp at present, eliminated the impact on synchronizing of forward delay interval and reception delay.Accessing time delay is the time delay that sending node accesses physical channel, depends primarily on MAC protocol, and current wireless MAC protocols can be divided into two classes according to its mode controlling to access medium: uncontested medium access protocol and medium access protocol based on competition.Uncontested medium access protocol typically uses TDMA (time division multiple acess) agreement, and node is before the message, it is necessary to wait that within a frame period that time slot belonging to it arrives.Medium access protocol based on competition, CSMA/CA (csma/conflict avoidance) such as ieee802.11 (Wi-Fi), having to wait for channel idle could access, when there being multiple node visit channel simultaneously, conflict can cause longer time delay.Propagation delay seems the least in current sync pattern, usually can ignore.
The present invention devises a kind of new wireless MAC protocols, and node need not intercept carrier wave before the message or channel is the most idle, directly transmits, and eliminates the impact accessing time delay to synchronizing.Use a kind of new synchronization mechanism and calculation, and inter-node synchronous information mutual message is little, make in network the timing tracking accuracy between local nodes reach several ns (nanosecond) level.So can determine internodal accurate distance by calculating propagation delay, provide approach for going out each internodal relative position based on trigonometric calculations.
Summary of the invention
In Ad Hoc network described in the invention, the interference difference caused due to the distribution situation difference of the surroundings nodes of node, and the transmitting power of difference node is different, causes the situation occurring single-pass between some node, only one can receive the information of the opposing party.So there will be two kinds of connection status between node in network: one is to be bi-directionally connected, and node both sides can directly receive the data cube computation of counter-party information.Another kind is unidirectional connection, and node both sides only have a data cube computation that can directly receive counter-party information.
The module principle block diagram of node as shown in Figure 4, has a sendaisle and N number of reception passage.Node can be set up be bi-directionally connected or unidirectional connection with surrounding K neighbor node simultaneously, and quantity N receiving passage continues on for monitoring in turn the state of other wireless channels more than K, remaining channel ((N-K) is individual) by software arrangements.The signal format of the system wireless channel of the present invention is as shown in Figure 5, signal is made up of the frame signal that the cycle is identical, and each frame serial number (F) identifies, more each frame is divided into P time slot, the solution of the present invention requires that P must be prime number, so system channel quantity maximum is P.It is different from the method for channel allocation of traditional TDMA agreement, each channel in the solution of the present invention is not to take fixing time slot, the timeslot number (Ts) taken is relevant to channel number (S) and frame number (F), and the time slot that channel takies in each frame is determined by following equation:
Ts=(S*F) Mod P (formula one)
In formula: Ts---timeslot number, span: 0～P-1.
S----channel number, span: 0～P-1.
F----frame number, from 0 serial number started, it is possible to using 0～M-1 rotation number, M takes the multiple of P.
P----prime number, by it is determined that the number of timeslots of system and channel quantity.
*----multiplication operator.
Mod----modulo operator, the remainder of round numbers division.
Can draw from above-mentioned formula one, timeslot number Ts starts to repeat after P frame, and cycle period is P.The sendaisle of each node takies a channel, the most just has a set of different time slot to send sequence.Through proving and emulation, the maximum likelihood that any two sequence of time slots produced in aforementioned manners clashes in time determines that, data can be correctly recovered, so the frame signal between each node is without requiring synchronization, as long as the cycle is identical by intertexture, repeated encoding technology.Corresponding to the reception passage of different channels on each node, only it is to be understood that currently receive the frame number corresponding to data message time slot, it is assured that frame boundary position and the time location of each time slot follow-up of this channel by formula one.The data form of each time slot as shown in Figure 6, is exactly current frame number after preamble synchronization code, and duplicate acknowledgment.So the frame signal using the node of this communication means to be easily achieved again between node synchronizes, realize time precise synchronization for the whole network and be possibly realized.Wireless signal strength owing to launching on node is far longer than the intensity receiving signal, so typically can not carry out receiving and transmitting signal in identical frequency band simultaneously.Each channel has different time slot and sends sequence and solve signal sending and receiving collision problem on node, simultaneously chnnel coding use that CDMA (CDMA) technology allows on node each receive passage and can distinguish the data sent from different nodes.So difference of each channel of system only has 2 points: different time slots sends sequence and the good spread-spectrum pseudorandom codes of mutually orthogonal characteristic.Each node can take any one wireless channel by the sendaisle of software arrangements oneself.Equally, the reception passage of node can also receive the signal of any one wireless channel by software arrangements.Chnnel coding uses CDMA (CDMA) technology to achieve node signal sending and receiving and uses same radio band, making transceiver channel radio transmission model characteristic between any two nodes identical, the most full symmetric, this brings convenience to node networking.
Node synchronization method in Ad Hoc network described in the invention uses traditional master-slave synchronisation mode, must have a time root node (time reference node) in network, and time root node is typically specified some special nodes to serve as by system.Such as this node is equipped with Big Dipper time service module or GPS time service module, it is also possible to forcing to specify some node is network time root node.If system does not specify time root node, the node in network also can automatically generate time root node according to the length adding network time.The node directly following the tracks of time root node is referred to as one level temporal node.Equally, the node following the tracks of one level temporal node is referred to as two grades of timing nodes.By that analogy, according to from time root node progression number, network has three grades, the timing node such as level Four successively.Time root node is referred to as zero level timing node.
Being formed multi-frame by multiple basic frames of signal as shown in Figure 5, multi-frame as shown in Figure 7 is made up of M basic frame, and the time span of multi-frame is the time span sum of M basic frame.Time reference position is set to the original position of No. zero frame of each multi-frame, and reality is exactly and the boundary position of a upper multi-frame.Each node in network broadcasts the temporal information of this node to surroundings nodes, including time source, source state, follows the tracks of progression, multi-frame number and frame header deviation.
Time source: represent that node currently selects the time source synchronized.Available item sorts by priority specifies time and free oscillation into Big Dipper time (BDT), gps time, system.When the initial time of Big Dipper time is 1 day zero January in 2006.When the initial time of GPS is 22 days zero August in 1999 at present.If it is time root node that system needs to specify node, when initial time is set to 1 day zero March in 2015.If system does not specify time root node, then time source is just set to free oscillation, the time that initial time just powers on for node, and multi-frame number counts from zero.
Source state: the state of the time source that expression node is current, including tracking, holding, interim and free oscillation.Tracking mode represents that the clock of current time root node is in the lock state.The clock of hold mode express time root node once locked oversampling clock source, is currently in clock source lost condition, also keeps regular hour accuracy.Transitory state is a transitive state, represents that the state of clock source changes, and is used for notifying surroundings nodes.The clock of free-running operation express time root node never locked any clock source, and the accuracy of time is insincere.
Follow the tracks of progression: representing and start to present node from time root node, clock have passed through how many grades of tracking.This is the important evidence that node selects reference clock.
Multi-frame number: represent node time span from the beginning of the initial time of time source, in units of the time span of multi-frame, the time reference position to current multi-frame of calculating.Be equivalent to the initial time from time source start to current reframing time reference position to experienced by altogether how many multi-frames.
Frame header deviation: representing time reference position and the time reference location comparison of time root node multi-frame of the current multi-frame of node, the time span of skew, in units of the time span of basic frame.
As shown in Figure 7 and Figure 8, time root node, with the time span of multi-frame as cycle, repeats to send temporal information as corresponding in Fig. 8 node synchronizing process in Ad Hoc network described in the invention.The tracking progression of time root node is set to 0, and frame header deviation is generally 0, and other are arranged according to practical situation.Multi-frame number 29160004 represents the multi-frame number of the initial time (during 1 day zero January in 2006) of current reframing time reference position distance Big Dipper time, if reframing time length corresponding to 29160004 quantity is 10 seconds, experienced by the time of 291600040 seconds altogether, be about as much as the time of 9 years 3 months.Other nodes in network receive the temporal information that surroundings nodes sends, the general upper level timing node selecting oneself according to following principle: be first to compare time source, the source priority orders of the time of acquiescence is that Big Dipper time (BDT), gps time and system specify the time, can also adjust according to demand, judge clock status, the timing node that prioritizing selection is in the lock state simultaneously.Next to that compare tracking progression, it is necessary to select to follow the tracks of the node that progression is minimum.
If whole network system does not specify time root node, it is in the initial time that the timing node of free-running operation does not give.The time that initial time just powers on for node, multi-frame number counts from zero, and multi-frame number at this moment means that this node is from the persistent period started that powers on.The free-running node that is in network receives the temporal information around sent equally, the multi-frame number in comparison information all in free-running node.Without finding the node bigger than local multi-frame number, the tracking progression arranging oneself immediately is 0, and source state is free oscillation, upgrade oneself for the time root node in subrange, amended temporal information is sent to surroundings nodes.If it find that around have the node bigger than the multi-frame number of oneself, then compare their tracking progression, it is necessary to select the upper level timing node following the tracks of the minimum node of progression as oneself.
Node chooses upper level timing node, the clock of local clock synchronized tracking immediately to upper level clock node, keeps the demarcation line of basic frame to align, and the present node represented such as dotted line in Fig. 7 and the basic frame boundary line of upper level clock node keep alignment.Extracting alignment basic frame frame number (Mn) and the temporal information of upper level timing node, temporal information includes time source, source state, follows the tracks of progression (H), multi-frame number (No) and frame header deviation amount (Sh).Time source and source state in present node temporal information can directly copy from upper level timing node, and the tracking progression of present node follows the tracks of progression plus 1 equal to upper level.The multi-frame number of present node and the calculating of frame header deviation follow these steps to carry out:
1) frame header deviation Sh (adjacent): Sh (adjacent) that first calculate present node and upper level timing node deducts Mn (currently) equal to Mn (upper level).Mn (upper level) and Mn (currently) is the basic frame frame number that boundary line is aligned with each other.
2) if the result of Sh (adjacent) is negative, then result adds M.M is the number including basic frame in multi-frame.
3) step 2) result Sh (adjacent) plus upper level timing node frame header deviation Sh (upper level).
4) judge step 3) result of calculation, if greater than or equal to M, then result deducts M.The multi-frame number (No) of present node is equal to the multi-frame number of upper level clock node plus 1 simultaneously, and otherwise, the multi-frame number (No) of present node is equal to the multi-frame number of upper level clock node.
5) the frame header deviation Sh (currently) of present node be equal to step 4) result of calculation.
Being illustrated in figure 8 the flow chart of above-mentioned calculating, result, as it is shown in figure 9, node is assembled into same temporal information message result of calculation sends toward surroundings nodes, constantly repeats, arrives each node in network.
Owing in network, the status of time root node is extremely important, it usually needs backup, the time root node of backup is undertaken by one level temporal node about in real time.Time root node is when its normal condition, and around one level temporal node determines the backup level (Gn) of oneself according to the information that time root node is broadcasted, and can sort with the size of the distance of Distance Time root node or channel number, Gn is 1,2,3,4 natural numbers such as grade.One level temporal node, in addition to passing time root node time and clock, also to monitor the state of time root node the moment.
When the one level temporal node that backup level is Gn finds drop-out time root node, it is interim for arranging source state immediately, continue the source state in Gn*Td (Td is a period of time that system defines) time observation surroundings nodes temporal information, if all transitory state, explanation time root node disappears, the tracking progression then arranging oneself is 0, and source state changes into keeping, and upgrades oneself for time root node.If the source state that this one level temporal node was observed in surroundings nodes temporal information within the lasting Gn*Td time the most all becomes transitory state, there are two kinds of situations, a kind of situation is that the source state in surroundings nodes temporal information becomes hold mode, explanation time root node disappears, and other one level temporal nodes existing are upgraded to time root node.Another kind of situation is that the source state in surroundings nodes temporal information continues as tracking mode, and the time root node of explanation moves, it is possible to according to the movement of other information auxiliary acknowledging time root node.Under both of these case, this one level temporal node needs again to select from surroundings nodes upper level timing node.Owing to each one level temporal node uses the different observation waiting time, it is to avoid competition becomes time root node and causes network upheaval.
Network do not has upper level timing node except time root node, other all nodes have upper level timing node, in order to realize the whole network node time precise synchronization, the clock of these nodes must synchronize with the clock of upper level timing node, and to align in the demarcation line of basic frame.The basic frame boundary line of channel on the sendaisle illustrating node of Figure 10 and the corresponding relation of the channel basic frame boundary line on reception passage.Figure 11 illustrates the two same channel position relationship in corresponding node.T and T ' in Figure 10 and Figure 11 are the basic frame periods, and nominal value is equal, several milliseconds, is far longer than the internodal signal lag of the two.Assume that Figure 10 represents that be that node A, Figure 11 represent is node B, and node A is the upper level timing node of node B.Δ T and Δ T ' in two figures are tried to achieve by following equation:
Δ T=DsB+DrA+Dp-δt
Δ T '=DsA+DrB+Dp+δt
In formula: the propagation delay between Dp---A, B node.
DsA---the forward delay interval of node A.
DrA---the reception delay of node A.
DsB---the forward delay interval of node B.
DrB---the reception delay of node B.
The demarcation line of the δ t---basic frame of node A is relative to the marginal phase offset of the basic frame of node B.
Ds in above-mentioned formulaA、DrA、DsBAnd DrBIt is all the constant time lag of node wireless MAC, can eliminate as systematic error.When designing this wireless MAC, the receive-after-transmit time delay making node is equal, DsA=DrA, DsB=DrB.So above-mentioned two formula just becomes:
Δ T=DsA+DsB+ DP-δ t (formula two)
Δ T '=DsA+DsB+ Dp+ δ t (formula three)
Each node in network measures the demarcation line time delay relative to the basic frame boundary line of the channel on sendaisle of the basic frame on all reception passages in real time, and timing fixed news issues surroundings nodes the forward delay interval value of these delay values He this node.The content of fixed news such as Figure 12 illustrates.Equally, after each node receives the delayed data relevant with oneself, do following process:
δ t=(Δ T '-Δ T)/2 (formula four)
Dp=(Δ T '+Δ T-2DsA-2DsB)/2 (formula five)
Adjust the local clock of node, make the δ t in formula four tend to 0, it is achieved the clock of present node and upper level timing node synchronizes, and realize the demarcation line alignment of basic frame.Formula five, for calculating the propagation delay of internodal wireless signal, measures internodal accurate distance.When actual application is easy to occur measuring Δ T and Δ T ', do not use a pair of identical basic frame boundary line, introduce the participation of basic frame period and calculate, cause result mistake.So the most first synchronizing with traditional synchronous method, judging that measured value arrives suitable scope with formula two or formula three, then using formula four instead.
This superior and the subordinate synchronous mode needs to know mutually Δ T or the Δ T ' value that the other side measures, so the time synchronized in network is to set up transmission between the node being bi-directionally connected.If the whole network time is the most synchronized, δ t tends to 0, and recipient's node of unidirectional connection also directly can accurately calculate the distance of the other side with formula three.Although the whole network time synchronized is through multi-hop, there is the biggest accumulated error, but the error of (jumps or a few jumping) is the least in subrange, more much more accurate than traditional distance-finding method using signal intensity to decay with propagation distance.
In node synchronization method in the wireless Ad Hoc network that the present invention program introduces, have employed new wireless MAC protocols, eliminate the impact accessing time delay to synchronizing.Use the method the most accurately passing time that the multi-frame of a kind of length and short basic frame are worked in coordination simultaneously, arrive each node in network.The production method of time root node and particularly also have innovation in time precise synchronization method between downstream site under the redundancy approach, node free-running operation of time root node.It is thus possible to realize the whole network time precise synchronization, the autgmentability of network does not therefore suffers from limiting.
Specific embodiment:
With the time synchronization process of a concrete Wireless Ad Hoc network interior joint, the synchronous method that the present invention introduces is described below.
31 wireless channels are had in Ad Hoc network system described in the invention, have employed 31 different gold (Gold) codes to be determined by following equation to the data modulating on different channels, the timeslot number (Ts) that each channel takies in basic frame as channel code:
Ts=(S*F) Mod 31
In formula: Ts---timeslot number, span: 0～30.
S----channel number, span: 0～30.
The basic frame number of F----, scheme uses 496 basic frame composition multi-frames, so F is from 0～495 circulations.
So each channel in system is distinguished by different sequence of time slots and different gold (Gold) codes, solves the signal transmitting and receiving conflict on same node simultaneously and each receives passage and can distinguish the data sent from different nodes.Each node can take any one wireless channel by the sendaisle of software arrangements oneself, and equally, the reception passage of node can also receive the signal of any one wireless channel by software arrangements.The multiframe period of designed system channel is 10s, about 20.16ms of basic frame period.
Node M AC that system uses has a sendaisle and 16 reception passages.Node is set up be bi-directionally connected or unidirectional connection with 6 neighbor node of surrounding the most simultaneously, remains 10 passages by software arrangements for monitoring the state of other wireless channels in turn.
A node in network is equipped with Big Dipper time service module, naturally time root node is become, when initial time is 1 day zero January in 2006, timing nodes at different levels were broadcasted the time source in temporal information, source state and tracking progression 31 times within a multiframe period, it is ensured that certain real-time.Multi-frame number and frame header deviation amount are only broadcasted 1 time, represent the time location of current multi-frame starting point.Channel basic frame boundary line delayed data requirement of real-time on node transceiver channel is higher, and about 10 times per second.And node forward delay interval information, send out once in a multi-frame.
New node does not the most send signal, searches for surroundings nodes, only receives surroundings nodes signal, and surroundings nodes does not has information to exchange, and is in fact a kind of unidirectional connection on 31 wireless channels that system is whole.According to receiving the time source of surroundings nodes, source state and following the tracks of progression information and choose oneself upper level timing node, first measure the basic frame boundary line time delay of the other side's channel, (node in system is the most the same with oneself forward delay interval value for set the other side, forward delay interval value is 1.6us), substantially determine oneself and send the position, demarcation line of the basic frame of channel, send signal, carry out synchronizing step the most again.Owing to generally using precision and degree of stability preferable TCX0 crystal oscillator on node, the frequency difference between any node is probably at 1,2 ppm, and adjustment amount is the least.Whether real-time judge measured value Δ T ' arrives suitable scope, once less than 4us (3.2us receive-after-transmit time delay adds some propagation delays), uses following equation instead and follows the tracks of synchronization.
δ t=(Δ T '-Δ T)/2
After network clocking synchronizes, δ t tends to 0.Recipient's node of signal lag and unidirectional connection between the node being bi-directionally connected calculates the computing formula of the signal lag of the other side:
Dp (being bi-directionally connected)=(Δ T '+Δ T-6.4us)/2
Dp (unidirectional connection)=(Δ T '-3.2us)/2
Node is while synchronizing upper level clock node, also to process the alignment basic frame frame number (Mn) and temporal information extracted from upper level clock node, temporal information includes time source, source state, follows the tracks of progression (H), multi-frame number (No) and frame header deviation amount (Sh).Time source and source state in present node temporal information can directly copy from upper level timing node, and the tracking progression of present node follows the tracks of progression plus 1 equal to upper level.The multi-frame number of present node and the calculating of frame header deviation follow these steps to carry out:
1) frame header deviation Sh (adjacent): Sh (adjacent) that first calculate present node and upper level timing node deducts Mn (currently) equal to Mn (upper level).If the result of Sh (adjacent) is negative, then result adds 496.
2) 1) result plus upper level timing node frame header deviation, result of calculation if greater than or equal to 496, then result deducts 496, and result is the frame header deviation Sh (currently) of present node.Multi-frame number No (currently) of present node is equal to the multi-frame number of upper level clock node plus 1 simultaneously, and otherwise, multi-frame number No (currently) of present node is equal to the multi-frame number of upper level clock node.
Node is assembled into same temporal information message result of calculation and sends toward surroundings nodes, constantly repeats, and arrives each node in network.
Node owing to being bi-directionally connected with time root node is all one level temporal node, between the node of time root node broadcast during basic frame boundary line delayed data Δ T, each one level temporal node can receive, the size of Δ T illustrates distance between time root node and one level temporal node, each one level temporal node determines the backup level (Gn) of oneself according to the size order of Δ T, and Gn is 1,2,3,4 natural numbers such as grade.The time Td of system definition is about 322ms (times of 16 basic frames).When time root node in mobile network, the source state in other node time information of observing does not changes, or tracking mode.Turning off time root node power supply, after a while, the source state in other node time information all becomes keeping, and multi-frame number and frame header deviation do not have ANOMALOUS VARIATIONS.
First remove the node of configuration Big Dipper time service module, close other all node power in network, opened each node power successively every one minute.Observing the node turned on the power at first and have been at time root node status, multi-frame number is gradually increased, and initial time is the time turned on the power.Finally opening the power supply of the node of configuration Big Dipper time service module, time root node is quickly transferred on this node, and the temporal information content of other nodes the most all switches.
In sum, node synchronization method in the Wireless Ad Hoc network that the present invention introduces, realize time precise synchronization for the node in wireless Ad Hoc network and provide new approach, the basis of time precise synchronization is that each internodal clock synchronizes, so the clock synchronizing method between radio node is also the key component of the present invention, the method for the boundary line alignment of particularly basic frame.