Method of avoiding synchronization between communicating nodes Number:7,522,640 from the United States Patent and Trademark Office (PTO) owispatent

Title: Method of avoiding synchronization between communicating nodes

Abstract: Communicating nodes in a network exchange state variable signals indicating the timing of periodic operations performed at the nodes. Each node autonomously controls the timing of its periodic operation so as to distance the timing from the timing of the periodic operations performed at other nodes. If the periodic operations include data transmission, this arrangement enables the nodes to avoid data collisions. The nodes can also adapt autonomously to changing conditions such as changing priority levels and the addition and removal of nodes.

Patent Number: 7,522,640 Issued on 04/21/2009 to Date,   et al.

---

Inventors:	Date; Masaaki (Osaka, JP), Morita; Yukihiro (Saitama, JP), Tanaka; Hisaaki (Tokyo, JP)
Assignee:	Oki Electric Industry Co., Ltd. (Tokyo, JP) Campuscreate, Co., Ltd. (Tokyo, JP)
Appl. No.:	10/939,489
Filed:	September 14, 2004

---

Foreign Application Priority Data

---

Sep 19, 2003 [JP]			2003-328530

Current U.S. Class:	370/507 ; 375/356
Current International Class:	H04L 12/50 (20060101); H04L 7/02 (20060101); H03D 13/00 (20060101)
Field of Search:	370/503-520,533 375/239,241,242,256,259,260,340,342,352,353,354,356,362,371,373

---

References Cited [Referenced By]

---

U.S. Patent Documents

6888819	May 2005	Mushkin et al.
7460631	December 2008	Date et al.
2002/0073086	June 2002	Thompson et al.
2002/0159130	October 2002	Sakano et al.
2003/0063619	April 2003	Montano et al.
2003/0099218	May 2003	Tillotson
2003/0174779	September 2003	Sugaya et al.
2004/0233852	November 2004	Ochi et al.
2005/0195771	September 2005	Matsunaga et al.
2005/0195827	September 2005	Yao et al.
2006/0114840	June 2006	Date et al.

Foreign Patent Documents

	07143558		Jun., 1995		JP
	2002-359551		Dec., 2002		JP
	WO-2004102887		Nov., 2004		WO

Other References

Waiyaresu LAN Akitekucha (Wireless LAN Architecture) edited by Matsushita et al., Kyoritsu Shuppan, 1996, pp. 47-71. cited by other . Floyd, S., and Jacobson, V., "The Synchronization of Periodic Routing Messages", IEEE/ACM Transactions on Networking, vol. 2, pp. 122-136, Apr. 1994. cited by other . Hartwich et al., Timing in TTCAN Network, 2002, http://web.archive.org/web/20020306003128/http://www.can-cia.de/can/ttcan- /. cited by other.

Primary Examiner: Pham; Chi H
Assistant Examiner: Elallam; Ahmed
Attorney, Agent or Firm: Rabin & Berdo, P.C.

---

Claims

---

What is claimed is:

1. A node used as a first node in a communication system that also includes at least a second node, the first node comprising: a signal communication unit operable to transmit a first state variable signal to the second node and receive a second state variable signal from the second node, the first state variable signal indicating a first operating timing of the first node, the second state variable signal indicating a second operating timing of the second node; and a timing decision unit operable to generate the first operating timing periodically at a basic rate subject to temporary variations, to generate the first state variable, and to adjust the first operating timing so that the first operating timing and the second operating timing are distanced from each other by varying the basic rate according to a rule that makes the first operating timing and the second operating timing mutually repulsive.

2. The node of claim 1, wherein the timing decision unit also varies the basic rate randomly.

3. The node of claim 1, wherein the timing decision unit determines the basic rate according to a processing capability of the first node.

4. The node of claim 1, further comprising a data communication unit for transmitting data at a timing determined from the first operating timing wherein and the timing decision unit determines the basic rate according to a priority of the data to be transmitted.

5. The node of claim 4, wherein the timing decision unit sets the basic rate to a value substantially equal to an integer multiple of a reference value.

6. The node of claim 4, wherein the timing decision unit increases the basic rate as the priority increases.

7. The node of claim 1, further comprising: a steady-state decision unit for deciding whether a steady-state relationship exists between the first operating timing and the second operating timing; and a data communication unit for transmitting data at a timing determined from the first operating timing when said steady-state relationship exists.

8. The node of claim 7, wherein the first state variable signal has a first transmission range controlled by the signal communication unit, the data have a second transmission range controlled by the data communication unit, and the first transmission range differs from the second transmission range.

9. The node of claim 1, wherein the timing decision unit includes a plurality of calculation units each generating a separate first state variable signal.

10. The node of claim 9, wherein the number of calculation units in the timing decision unit depends on a processing capability of the first node.

11. The node of claim 9, further comprising a data communication unit for transmitting data from the first node at timings determined from the first operating timing, wherein the number of calculation units in the timing decision unit depends on a priority of the data to be transmitted.

12. The node of claim 9, wherein the first state variable signals generated by the calculation units indicate different first operating timings.

13. The node of claim 9, wherein the first state variable signals generated by the calculation units are transmitted in different frequency bands.

14. The node of claim 13, further comprising a data communication unit for transmitting data from the first node at timings determined from the first operating timings, in the frequency bands in which the first state variable signals that indicate the first operating timings are transmitted.

15. A communication system comprising a plurality of nodes of the type described in claim 1.

16. A method of controlling a first node and a second node in a network, comprising: transmitting a first state variable signal from the first node to the second node, the first state variable signal indicating a first timing related to a first periodic operation performed at the first node; transmitting a second state variable signal from the second node to the first node, the second state variable signal indicating a second timing related to a second periodic operation performed at the second node; controlling the first timing autonomously at the first node so as to distance the first timing from the second timing; controlling the second timing autonomously at the second node so as to distance the second timing from the first timing; transmitting data from the first node at a timing determined from the first timing; and transmitting data from the second node at a timing determined from the second timing.

17. The method of claim 16, further comprising deciding whether a steady-state relationship exists between the first timing and the second timing, wherein said data are transmitted from the first node and the second node only when the steady-state relationship exists.

18. The method of claim 16, wherein controlling the first timing further comprises: determining a basic rate of the first periodic operation; and varying the basic rate according to a rule that makes the first timing and the second timing mutually repulsive.

19. The method of claim 18, wherein controlling the first timing further comprises randomly varying the basic rate.

20. The method of claim 18, wherein the first operation includes transmitting data from the first node, and determining the basic rate comprises assigning a priority to the data to be transmitted, the basic rate being determined from the priority.

21. A machine-readable medium storing a program for controlling a first node in a network including at least the first node and a second node, the program including instructions for: receiving from the second node a state variable signal indicating a second timing of a second periodic operation performed at the second node; generating a first timing periodically at the first node, at a basic rate subject to temporary variations; adjusting the first timing so that the first timing and the second timing are distanced from each other by varying the basic rate according to a rule that makes the first timing and the second timing mutually repulsive; performing a periodic operation at the first node responsive to the first timing; and transmitting to the second node a state variable signal indicating the first timing.

---

Description

---

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a system such as, for example, a sensor network, a mobile communication network, or a local area network (LAN) having a plurality of communicating nodes. More particularly, the invention relates to the avoidance of unwanted synchronization between nodes, and the avoidance of collisions between transmissions from different nodes.

2. Description of the Related Art

The nodes of concern in the present invention are intelligent devices such as computers, personal digital assistants (PDAs), mobile telephones, or so-called smart sensors, having computational capabilities as well as communication capabilities. Networks of such nodes have become widespread.

In a wireless network, since the nodes share a common communication medium, sometimes referred to as an air interface, they face a problem of collisions between transmissions from different nodes. Two well-known solutions to this problem are time division multiple access (TDMA), in which a central server assigns different time slots to the nodes, and carrier sense multiple access with collision avoidance (CSMA/CA), in which there is no central server but each node checks whether other nodes are transmitting before transmitting itself, detects collisions during transmission, and retransmits at a random time after a collision.

Wired networks such as local area networks may also have a common transmission medium such as a shared cable, with the attendant problem of collisions. The widely used Ethernet LAN communication system has adopted a solution known as carrier sense multiple access with collision detection (CSMA/CD), which is similar to CSMA/CA, except that collisions are detected from an increase in the direct-current component on the cable.

The above solutions are not entirely satisfactory. In the TDMA system, if the central server fails, all of the nodes under its control lose the capability to communicate. Furthermore, when nodes are added or removed, or when a node fails, runs out of power, or is moved to another location, the central server must discover the altered situation and reassign the time slots. This is generally a complex process, and is difficult to carry out rapidly when there are many nodes generating traffic at once. In the CSMA/CA and CSMA/CD systems, as the number of nodes generating traffic increases, so does the amount of overhead included in the traffic, causing an unavoidable loss of communication efficiency.

Transmission collisions, which occur when two nodes transmit simultaneously on the same communication medium, are just one example of the more general problem of unwanted synchronization between nodes. Another well-known example is the periodic transmission of routing information by routers in a network such as the Internet. Even though the router nodes are interconnected by separate cables, if they become synchronized and all transmit routing information at the same times, the network becomes overloaded at these times and communication may be delayed, or data may be lost. This type of synchronization has been shown to occur as an unwanted by-product of almost any type of interaction among nodes.

SUMMARY OF THE INVENTION

An object of the present invention is to provide a method of avoiding collisions in a communication system by autonomous control of the communicating nodes.

Another object of the invention is to enable the nodes to adjust flexibly and autonomously to changing conditions in the communication system.

Yet another object is to enable bandwidth to be apportioned flexibly among nodes.

The invention provides a node having a signal communication unit and a timing decision unit. The signal communication unit transmits a first state variable signal to another node and receives a second state variable signal from the other node. The first state variable signal indicates a first operating timing of the first node; the second state variable signal indicates a second operating timing of the second node. The timing decision unit causes a periodic operation to take place in the first node at a timing responsive to the second state variable signal, and generates the first state variable signal so that the first operating timing is related to the timing of the periodic operation. The timing decision unit adjusts the timing of the periodic operation so that the first operating timing and the second operating timing are mutually distanced from each other, e.g., mutually out of phase.

The invention also provides a machine-readable medium storing a program for controlling the invented node.

The invention further provides a method of controlling a first node and a second node in a network. In this method, a first state variable signal is transmitted from the first node to the second node, indicating a first timing related to a first periodic operation performed at the first node. A second state variable signal is transmitted from the second node to the first node, indicating a second timing related to a second periodic operation performed at the second node. The first periodic operation is controlled autonomously at the first node so as to distance the first timing from the second timing. The second periodic operation is controlled autonomously at the second node so as to distance the second timing from the first timing.

The first and second periodic operations may include data transmission, in which case, by distancing the first and second timings, the nodes can avoid collisions. Alternatively, the first and second periodic operations may be mechanical operations, control operations, data acquisition operations, or internal operations such as the performance of a computational task or the generation of an internal timing signal. Transmission of the first and second state variable signals may also constitute the first and second periodic operations.

If further nodes are added to the network, the nodes can adapt to the changed conditions autonomously by receiving further state variable signals from the added nodes. Each node adjusts the timing of its own periodic operation so as to distance the timing from the timings of periodic operations performed at the other nodes.

Each node may perform its periodic operation at a basic rate determined by the processing capability of the node, the priority of data to be transmitted by the node, or other factors. If the periodic operation involves data transmission, then data transmission takes place in time slots that are apportioned according to the node's processing capability, priority, or other factors.

BRIEF DESCRIPTION OF THE DRAWINGS

In the attached drawings:

FIG. 1 illustrates a plurality of nodes in a wireless communication system;

FIG. 2 is a block diagram showing the internal structure of a node according to a first embodiment of the present invention;

FIG. 3 is a flowchart illustrating the communication method according to the first embodiment;

FIG. 4A illustrates an initial state during communication between two neighboring nodes;

FIG. 4B illustrates a transitional state during communication between the two neighboring nodes;

FIG. 4C illustrates the steady state during communication between the two neighboring nodes;

FIG. 5A illustrates an initial state during communication among three neighboring nodes;

FIG. 5B illustrates a transitional state during communication among the three neighboring nodes;

FIG. 5C illustrates the steady state during communication among the three neighboring nodes;

FIG. 6 is a block diagram showing the internal structure of a node according to a second embodiment of the invention;

FIG. 7 is a block diagram showing the internal structure of a node according to a third embodiment;

FIG. 8 is a flowchart illustrating a communication method used in the third embodiment;

FIG. 9 is a block diagram showing the internal structure of a node according to a sixth embodiment of the invention; and

FIG. 10 is a block diagram showing the internal structure of a node according to a seventh embodiment of the invention.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments of the invention will now be described with reference to the attached drawings, in which like elements are indicated by like reference characters.

First Embodiment

Referring to FIG. 1, a first embodiment of the invention comprises a plurality of spatially distributed nodes A that exchange data by wireless communication.

As shown in FIG. 2, each node A comprises an impulse signal receiving unit 11, a communication timing controller 12, an impulse signal transmitter 13, a steady-state decision unit 14, a data communication unit 15, and a sensor 16. Each node A also has a power supply (not shown) for supplying electrical power to these components.

The impulse signal receiving unit 11 receives an input impulse signal Sin11 and outputs a received impulse signal Spr11 to the communication timing controller 12 and the steady-state decision unit 14.

The communication timing controller 12 generates a phase signal Spr12 and outputs it to the impulse signal transmitter 13, steady-state decision unit 14, and data communication unit 15.

The impulse signal transmitter 13 outputs an output impulse signal Sout11 to the outside world, that is, to other nodes.

The steady-state decision unit 14 generates a steady-state decision signal Spr13 and a slot signal Spr14 and outputs them to the data communication unit 15.

The data communication unit 15 receives observation data Spr15 from the sensor 16, receives an input data signal Sin12 from the outside world (other nodes), and outputs an output data signal Sout12 to the outside world.

The sensor 16 receives environmental information Sin13 from the outside world and outputs observation data Spr15 to the data communication unit 15. The environmental information Sin13 is information about the physical environment of the node, such as the ambient temperature, sound level, level of vibration or seismic magnitude, concentration of a chemical substance, or the like.

The output impulse signal Sout11 and output data signal Sout12 shown in FIG. 2 are baseband signals which are modulated onto a high-frequency carrier signal before being transmitted. The impulse signal transmission means 13 and data communication means 15 in the first embodiment share the same carrier frequency and may therefore share the same circuits (not shown) for generating and modulating the carrier signal. Similarly, the impulse signal receiving means 11 and data communication means 15 may share common circuits for demodulating a high-frequency received carrier signal to obtain the input impulse signal Sin11 and input data signal Sin12.

The impulse signal receiving unit 11 and impulse signal transmitter 13 constitute a state variable signal communication unit. The communication timing controller 12 and impulse signal transmitter 13 constitute a timing decision unit. The state-variable signals are the input impulse signal Sin11 and output impulse signal Sout11. The period operation performed in the first embodiment is the transmission of the output impulse signal Sout11. This periodic operation also establishes an internal timing, referred to below as a time slot, for transmission of the output data signal Sout12, but the output data signal Sout12 is not necessarily transmitted in every time slot.

Each of the constituent elements shown above may be a separate hardware module, but some of the elements, such as the communication timing controller 12, may be implemented as software executed by a general-purpose computing device.

The nodes are not limited to the internal structure shown in FIG. 2; various modifications are possible. For example, elements shown as separate functional blocks in FIG. 2 may be combined into a single hardware or software block, or an element shown as a single functional block may be divided into a plurality of hardware or software blocks. The functional components of a single node may be disposed at physically separate locations.

The functions performed by these units will be described in more detail in the following description of the operation of the first embodiment, which will be based on the flowchart in FIG. 3.

In step 3-1 in FIG. 3, the impulse signal receiving unit 11 receives an output impulse signal Sout11 transmitted by a neighboring node as an input impulse signal Sin11. `Neighboring` means that, for example, the node is within radio transmission range and is in a communication-enabled state. The input impulse signal Sin11 is a timing signal representing timing information but not carrying any data. Ideally the input impulse signal Sin11 is a delta-function signal comprising a pulse of infinite height and infinitesimal width, but in practice the pulse has, for example, a Gaussian waveshape with finite height and positive width.

In step 3-2, the impulse signal receiving unit 11 reshapes the received signal to generate the received impulse signal Spr11. The received signal can be reshaped by using a low-pass filter to remove noise. Alternatively, since the impulse signals exchanged between the nodes have a uniform waveshape defined by a predetermined mathematical function, instead of reshaping the received signal, the impulse signal receiving unit 11 can regenerate a timing signal synchronized with the reception of the input impulse signal Sin11 and having the intended waveshape, and use the regenerated signal as the received impulse signal Spr11.

In step 3-3, the communication timing controller 12 performs calculations to determine the timing of transmission of the output impulse signal Sout11. More specifically, the communication timing controller 12 advances the phase of a state variable .theta..sub.i(t) that models nonlinear oscillation by cycling in the range from zero to 2.pi.. The output impulse signal Sout11 is transmitted when the state variable has a specific phase value .alpha., such as zero radians (.alpha.=0). The rate at which the phase of the state variable .theta..sub.i(t) advances is controlled by, for example, the differential equation (1) below.

This equation (1) is essentially a rule for generating local variations in the basic period of the nonlinear oscillation at the i-th node in response to received impulse signals Spr11 from neighboring nodes. The variable t represents continuous time, and .omega. is a natural angular frequency parameter expressing the basic oscillation period, that is, the basic rhythm with which the periodic operation is performed at the node. It will be assumed in this embodiment that .omega. has a uniform predetermined value throughout the system. The function P.sub.k(t) expresses the value at time t of the received impulse signal Spr11 obtained by reshaping or regenerating the input impulse signal Sin11 received from neighboring node k (k=1 to N). N is the total number of neighboring nodes within spatial receiving range, capable of producing a received impulse signal Spr11. The function R(.theta..sub.i(t), .sigma.(t)) is a phase response function that determines how the basic period or rhythm is varied in response to the received impulse signals Spr11.

d.theta..function.d.omega..times..function..function..theta..function..sig- ma..function..function..theta..function..sigma..function..function..theta.- .function..sigma..function..sigma..function..pi..PHI..function. ##EQU00001## .theta..sub.i(t): phase signal of node i .omega.: natural angular frequency parameter P.sub.k(t): received impulse signal received from node k R(.theta..sub.i(t), .sigma.(t)): phase response function .phi.(t): random noise function

In known art dealing with coupled oscillating systems such as the above in which a plurality of interacting nodes exhibit some type of internal nonlinear oscillating behavior, many ways have been devised of achieving desired effects by shaping the nonlinearity of the oscillating behavior so as to bring neighboring nodes into phase, so that they oscillate in step with one another. Examples can be found in Japanese Unexamined Patent Application Publication No. 2002-359551.

The present invention takes the opposite approach: it shapes the nonlinearity of the oscillating behavior so as to force neighboring nodes out of step with each other, so that, for example, their oscillations are mutually .pi. radians (180.degree.) out of phase. Keeping neighboring nodes in the present embodiment out of phase with each other ensures that their transmitted impulse signals Sout11 do not collide and that, when transmitted, their output data signals Sout12 do not collide either.

In the phase response function R(.theta..sub.i(t), .sigma.(t)), the term .sigma.(t) is the sum of a constant term .pi. and a random function .phi.(t). The constant term .pi. attempts to bring neighboring nodes into complementary phase with each other by distancing the transmission timings of one node as far as possible from the transmission timings of another node. The random function .phi.(t) gives the nonlinear characteristic a random variability by generating noise (random values) according to, for example, a Gaussian probability distribution with a mean value of zero and a standard deviation that can be selected on the basis of experiments.

The random variability is added to keep the system from becoming trapped in a locally stable state (local solution) other than the desired stable state (optimal solution) in which the transmission timings of the output impulse signal Sout11 at neighboring nodes are appropriately out of phase with each other. In a coupled oscillating system there are generally a plurality of stable states (local solutions) other than the optimal solution. Random variability is introduced as a means of jogging the system out of a local solution so that it can reach the optimal solution.

The phase response function R(.theta..sub.i(t), .sigma.(t)) in equation (1) above is a sine function, but the invention is not limited to the use of a sine function, and the constant term is not limited to .pi.. The constant term may be any constant .lamda. other than zero or an even multiple of .pi. (e.g., any value in the range 0<.lamda.<2.pi.). If a constant other than .pi. is used, the result will be that neighboring nodes attempt to assume different but not reverse phases.

Although the above equation (1) takes the sum of the received impulse signals Spr11 received from a plurality of neighboring nodes k, it is also possible to process the received impulse signals Spr11 one by one by removing the summation symbol (.SIGMA.) from the equation.

The calculations required by equation (1) can be carried out by software using well-known numerical analysis methods such as the Runge-Kutta method. (For a Japanese description of the Runge-Kutta method, see UNIX Wakusuteishon ni yoru Kagaku Gijutsu Keisan Handobukku-Kiso-hen C-gengo ban (Handbook of Scientific and Engineering Computation on UNIX Workstations--Basic C Language Edition) by Hayato Togawa, published by Saiensu Co.) Alternatively, the calculations can be carried out by dedicated hardware.

The communication timing controller 12 calculates the phase .theta..sub.i(t) from equation (1) for successive values of the time parameter t, and supplies the result to the impulse signal transmitter 13, steady-state decision unit 14, and data communication unit 15 as the phase signal Spr12. The impulse signal transmitter 13, steady-state decision unit 14, and data communication unit 15 take various actions on the basis of the phase signal Spr12, as described below.

The invention is not restricted to the use of equation (1) or to the use of state variable signals indicating phase. A state variable signal may be any signal indicating the state of a variable that expresses an operating state or operating timing of a node. For example, instead of phase, the state variable signal may express displacement, and the underlying nonlinear oscillation model may not be the locally varied harmonic oscillator described by equation (1) but any other type of nonlinear oscillation, including disorderly or chaotic oscillation.

The above computational operations will be explained in further detail with reference to drawings that show how the phases of two or three nodes are forced apart over time.

FIGS. 4A, 4B, and 4C illustrate this process when there is just one neighboring node j near the node of interest i. FIG. 4A shows an exemplary initial state, when the system starts operating. Nonlinear oscillation is modeled by the motion of the two point masses rotating around a circle, expressing the timing phase of these nodes i, j. If the rotational motion of a point mass is projected onto the vertical axis or horizontal axis, the motion of the projected point exhibits harmonic nonlinear oscillation. From equation (1), a nonlinear characteristic operating on the two mass points attempts to bring them into complementary phases, so with elapse of time the initial state in FIG. 4A passes through a transitional state such as the one in FIG. 4B and finally settles into the steady state shown in FIG. 4C.

The two point masses rotate with a basic angular velocity (equivalent to the basic rate of transitions in the operating states of their nodes) given by the natural angular frequency parameter .omega.. The point masses interact by transmission and reception of output impulse signals Sout11, alter (quicken or slow) their angular velocities as a result of the interaction, and reach a steady state in which a complementary phase relationship is maintained. This process can be understood as operating by mutual repulsion of the two point masses as they rotate.

In FIGS. 5A, 5B, and 5C there are two neighboring nodes j1 and j2 near the node of interest i. FIG. 5A shows an exemplary initial state, FIG. 5B shows a transitional state, and FIG. 5C shows the steady state in which the phases at the three nodes are mutually separated by 2.pi./3 radians. This state can also be thought of as being reached by mutual repulsion of point masses rotating around a circle. Similar operations occur when the number of neighboring nodes is three or more.

If the number of neighboring nodes changes during the course of system operation, the steady state changes adaptively. Assume, for example, that there is now one node neighboring the node of interest, and that a stable phase relationship has been established as in FIG. 4C. Then assume that one new neighboring node is added. The stability of the phase relationship is destroyed, but after passing through a transitional state, the system assumes a new steady state in which there are two neighboring nodes, as in FIG. 5C. Similar adaptation occurs when two or more new neighboring nodes are added, or when a neighboring node is removed or stops functioning. The first embodiment enables all of the nodes constituting the system to form stable phase relationships with their neighboring nodes and adapt to changes flexibly and autonomously.

The operation of the first embodiment can be described in more general terms as follows. Each node generates an internal state variable signal according to a pair of rules, performs a periodic operation at times indicated by the state variable signal, and informs neighboring nodes of the value of its internal state variable by transmitting an output state variable signal from time to time. In the first embodiment, the internal state variable signal is the phase signal Spr12, and the output state variable signal is the output impulse signal Sout11.

The first rule by which the internal state variable signal is generated determines the basic rate at which the operation is performed. In the first embodiment, this rule is given by the natural angular frequency parameter .omega..

The second rule varies the rate at which the operation is performed, in response to state variable information received from neighboring nodes. This rule operates repulsively by driving the internal state of the node away from the internal states of the neighboring nodes. In the first embodiment, the second rule is given by equation (1).

The second rule operates locally; that is, each node controls its own internal state and timing autonomously.

The first rule may be either local or global. In the first embodiment, it is assumed that the first rule is global and constant, i.e., that all nodes have the same constant natural angular frequency parameter .omega., but in the general case, different nodes may operate at different basic rates. For example, the basic rate may vary with the physical location of the node. The basic rates at some nodes may be integer multiples of the basic rates at other nodes. Alternatively, the basic rates of the nodes may all be close to a central value, but may be distributed randomly around the central value according to, for example, a Gaussian probability distribution. The basic rate of a node may also vary over time.

The first and second rules may be based on various nonlinear oscillation models. It is not necessary to model the oscillating mechanism or phenomena exactly; a simplified or abstracted model may be used.

Referring again to FIG. 3, in step 3-4, the impulse signal transmitter 13 transmits the output impulse signal Sout11 according to the phase signal Spr12. That is, it transmits the output impulse signal P.sub.i(t) when the phase signal Spr12 takes on a specific value .alpha.: .theta..sub.i(t)=.alpha. (0.ltoreq..alpha..ltoreq.2.pi.)

The output impulse signal Sout11 or P.sub.i(t), like the above input impulse signal Sin11, is a timing signal having, for example, a Gaussian waveshape. A particular value of .alpha. is uniformly set for the entire system. No generality is lost by assuming that .alpha.=0, so in the following distribution it will be assumed that .alpha.=0 uniformly throughout the system.

In step 3-5, the steady-state decision unit 14 decides whether the transmission timings of the output impulse signals Sout11 at its own node and neighboring nodes are in a transitional state or the steady state. In the steady state, the transmission timings of the output impulse signal Sout11 at these nodes are stabilized in an appropriate non-colliding temporal relationship. The steady-state decision unit 14 observes the timing of the received impulse signal Spr11 and output impulse signal Sout11, and decides that they are in the steady state if the timing difference remains temporally constant, or nearly constant. That is, the steady-state decision unit 14 decides any stable timing relationship as the steady state. The steady-state decision can be carried out, for example, as follows.

(a) The value .beta. of the phase signal Spr12 at the timing of generation of the received impulse signal Spr11 is observed for one basic period of the phase signal Spr12. Let the values .beta. of the phase signal Spr12 obtained as a result of performing the above observation be: .beta..sub.1, .beta..sub.2, . . . , .beta..sub.N (0<.beta..sub.1<.beta..sub.2<. . . <.beta..sub.N<2.pi.)

(b) The differences (phase differences) .DELTA. between adjacent values are calculated from the observed values .beta. of the phase signal Spr12. .DELTA..sub.1=.beta..sub.1, .DELTA..sub.2=.beta..sub.2-.beta..sub.1, . . . , .DELTA..sub.N=.beta..sub.N-.beta..sub.N-1

(c) Processes (a) and (b) above are carried out at intervals of one period of the phase signal Spr12 and the rate of change .gamma. (differences) in the phase difference .DELTA. between adjacent periods are calculated. .gamma..sub.1=.DELTA..sub.1(.tau.+1)-.DELTA..sub.1(.tau.), .gamma..sub.2=.DELTA..sub.2(.tau.+1)-.DELTA..sub.2(.tau.), . . . , .gamma..sub.N=.DELTA..sub.N(.tau.+1)-.DELTA..sub.N(.tau.) where .tau. indicates discrete time in units of one period of the phase signal Spr12.

The steady state is recognized when the above rates of change .gamma. are all smaller than a predetermined value .epsilon.. .gamma..sub.1<.epsilon., .gamma..sub.2<.epsilon., . . . , .gamma..sub.N<.epsilon.

In the example above, the steady state is recognized on the basis of the rate of change in phase difference .DELTA. over two periods. It is also possible, however, to make the steady state decision according to whether the decision condition .gamma..sub.1<.epsilon., .gamma..sub.2<.epsilon., . . . , .gamma..sub.N<.epsilon. is satisfied over M periods (where M is an integer greater than two). The larger the value of M is, the more stable the state must be in order for the steady-state decision unit 14 to decide that the steady state has been reached.

In the example above, the steady-state decision is made on the basis of all received impulse signals Spr11 received in each period of the phase signal Spr12, but the decision may be based on only some of the received impulse signals Spr11.

The steady-state decision unit 14 outputs the steady-state decision signal Spr13 indicating the decision result and the slot signal Spr14 to the data communication unit 15. The slot signal Spr14 gives the value .beta..sub.1 of the phase signal Spr12 at the first received impulse signal Spr11 following phase zero. The steady-state decision signal Spr13 and slot signal Spr14 are output at intervals equal to the period of the phase signal Spr12.

In step 3-6, the sensor 16 senses a property of the physical environment of the node, such as temperature, sound intensity, vibration, chemical concentration, or any other measurable property. The sensed property acts as an input signal Sin, from which the sensor 16 generates observation data Spr15. The sensor 16 sends the observation data Spr15 to the data communication unit 15. The data communication unit 15 also receives the output data signals Sout12 transmitted by neighboring nodes as input data signals Sin12.

In step 3-7, the data communication unit 15 transmits the observation data Spr15 or the input data signal Sin12 (or both) to other nodes as the output data signal Sout12. The output data signal Sout12 is transmitted when the steady-state decision signal Spr13 indicates that the steady state has been recognized, and is not transmitted when the steady-state decision signal Spr13 indicates a transitional state. The output data signal Sout12 and output impulse signal Sout11 are transmitted in the same frequency band. The output data signal Sout12 is transmitted in a time slot (time interval) described below.

The time slot starts at a timing following the transmission of the output impulse signal Sout11, and ends at a timing preceding the generation of the closest received impulse signal Spr11. If the output impulse signal Sout11 is transmitted at phase zero, the output data signal Sout12 is transmitted in a time slot in which the phase .theta..sub.i(t) indicated by the phase signal Spr12 satisfies the following condition. .delta..sub.1<.theta..sub.i(t)<.beta..sub.1-.delta..sub.2

The parameter .delta..sub.1 corresponds to the space of time required for the transmission of the output impulse signal Sout11. The parameter .delta..sub.2 indicates the space of time that must be allowed between the termination of transmission of the output data signal Sout12 and the generation of the closest following received impulse signal Spr11 is generated. Both parameters have experimentally determined values, expressible in radians. The rate at which sensor observations are made may be equal to, faster than, or slower than the basic rate represented by the natural angular frequency parameter .omega.. If necessary, a single time slot may be used to transmit a plurality of sensor observations, or data from a single sensor observation may be transmitted over a series of consecutive time slots. In some time slots, no observation data may be transmitted.

If each node transmits data in time slots satisfying the conditions above, neighboring nodes can share the same frequency band and still avoid collisions of transmitted data.

The transmitted signal strength (signal propagation range) D12 of the output data signal Sout12 is controlled independently of the transmitted signal strength (signal propagation range) D11 of the output impulse signal Sout11. The two signal strengths may have a predetermined relationship: for example, D11 may be twice D12. Alternatively, the relationship may be varied adaptively. An appropriate relationship is one such that any two nodes capable of generating mutually interfering output data signals can also receive each other's output impulse signals and thereby adjust their transmission timing so as to avoid data collisions.

Steps 3-3 to 3-7 in FIG. 3 and can be executed without executing steps 3-1 and 3-2. The communication timing calculations are performed to generate the phase signal Spr12 on a regular basis, regardless of the reception or non-reception of state variable signals from other nodes. If state variable signals are received from other nodes, they will affect the calculations, but if they are not received, the calculations will proceed nevertheless.

In contrast to conventional TDMA systems, in which a centralized server manages all time slot assignments, the present embodiment lets the network nodes determine their own time slot assignments autonomously, on a distributed basis, by mutual interaction among neighboring nodes. Since the present embodiment does not rely on a centralized server, it does not experience the problem of all nodes under the control of a centralized server becoming incapable of communication if the server fails.

In the present embodiment, when nodes are added to or removed from part of the system or when a node fails or moves to another location, the set of nodes affected by the change adapt to the change and readjust their time slots autonomously, while nodes not affected by the change continue data communication without interruption, using their existing time slots.

Because time slots are adjusted locally among neighboring nodes, non-neighboring nodes may transmit data simultaneously. More specifically, nodes with non-overlapping impulse signal propagation ranges may transmit simultaneously to make efficient use of time-slot resources. In the present embodiment, this efficiency is achieved autonomously. If a similar type operation were to be attempted in a system managed by a centralized server, the server would have to keep track of the spatial positional relationships of all nodes and their signal propagation ranges, and would have to modify the time-slot assignments whenever any of these relationships and ranges changed. In a system in which such changes occur frequently, the computational cost of these operations would be high, much additional communication overhead would be necessary, and communication efficiency would suffer accordingly.

In the present embodiment, in contrast, there is no need for complex computations to be carried out by a centralized server, the amount of overhead does not increase even when many nodes generate traffic, and communication efficiency is not lowered as traffic increases. Compared with conventional CSMA/CA systems, the present embodiment offers improvements in the stability, efficiency, adaptability, and cost of data communication.

In a variation of the first embodiment, only nodes that generate data communication traffic transmit the output impulse signal Sout11 (that is, only nodes generating data communication traffic interact with their neighboring nodes). In this case, as some nodes stop generating traffic and other nodes start generating traffic, the time slots are reassigned adaptively so as to make efficient use of communication resources.

In another variation of the first embodiment, the sensor 16 is replaced by another type of device generating data to be transmitted periodically. There is no restriction on the type of data transmitted or the content of the data.

Second Embodiment

Next, a node according to a second embodiment of the invention will be described. Referring to FIG. 6, the second embodiment adds a suspension controller 10 to the node structure in the first embodiment. The suspension controller 10 outputs a suspend signal Spr10 to all the other constituent elements of the node, that is, to the impulse signal receiving unit 11, communication timing controller 12, impulse signal transmitter 13, steady-state decision unit 14, data communication unit 15, and sensor 16.

The second embodiment operates in the same way as the first embodiment, except for the following differences.

The suspension controller 10 switches the operation of each other constituent element in the node on and off periodically. The impulse signal receiving unit 11, communication timing controller 12, impulse signal transmitter 13, steady-state decision unit 14, data communication unit 15, and sensor 16 operate when the suspend signal Spr10 is in the on-state, and stop operating when the suspend signal Spr10 is in the off-state. The ratio of on-time to off-time may be a uniform constant ratio a:b (on-time:off-time=a:b where a and b are positive integers), or the ratio may vary from time to time and from node to node. The on-off cycles at different nodes are not synchronized.

The introduction of the suspension controller 10 causes the nodes to cycle between active and inactive states asynchronously. As seen from one node, the other nodes follow active-inactive cycles that are randomly related. Because of the randomness in the active-inactive cycles, the function .phi.(t) used to provide random variability in equation (1) in the first embodiment is no longer necessary. Equation (1) can accordingly be simplified as follows.

d.theta..function.d.omega..times..function..function..theta..function..fun- ction..theta..function..function..theta..function..pi. ##EQU00002## .theta..sub.i(t): phase signal of node i .omega.: natural angular frequency parameter P.sub.k(t): received impulse signal from node k R(.theta..sub.i(t)): phase response function

The second embodiment provides the same advantages as the first embodiment and the following additional advantage. In the first embodiment the nodes constituting the system are always active and always consume power. In the second embodiment, however, each node becomes active only intermittently. When a node is inactive, it consumes less power. If the nodes are battery-operated, drain on the batteries is reduced and the operating life of the system can be extended.

Third Embodiment

Next, a third embodiment of the present invention will be described. Referring to FIG. 7, a node in the third embodiment comprises a data pulse signal receiving unit 31, a communication timing controller 32, a steady-state decision unit 33, a data pulse signal transmitter 34, and a sensor 35.

The data pulse signal receiving unit 31 receives an input data pulse signal Sin31, outputs a received impulse signal Spr31 to the communication timing controller 32 and steady-state decision unit 33, and outputs a received data signal Spr31 to the data pulse signal transmitter 34. The communication timing controller 32 outputs a phase signal Spr33 to the steady-state decision unit 33 and the data pulse signal transmitter 34. The steady-state decision unit 33 outputs a steady-state decision signal Spr34 to the data pulse signal transmitter 34. The data pulse signal transmitter 34 sends an output data pulse signal Sout31 to the outside world. The sensor 35 inputs environmental information Sin32 and outputs observation data Spr35 to the data pulse signal transmitter 34, operating in the same way as the sensor in the first embodiment.

In the third embodiment, the data pulse signal receiving unit 31 and data pulse signal transmitter 34 function as a state variable signal communication unit. The communication timing controller 32 and data pulse signal transmitter 34 function as a timing decision unit. The data pulse signal transmitter 34 also functions as a data communication unit.

The operation of the third embodiment will be described with reference to the FIG. 8. Mainly, the operations differing from the first embodiment will be described; descriptions of similar operations will be omitted.

First, in step 8-1 the data pulse signal receiving unit 31 receives a data pulse signal transmitted by a neighboring node (for example, another node within radio transmission range) as an input data pulse signal Sin31. The input data pulse signal Sin31 has sufficient pulse width to enable the pulse to be modulated by a data signal. Prior to modulation, the pulse may be a rectangular pulse, or may have a triangular waveshape, a Gaussian waveshape, or any other suitable waveshape, the same waveshape being used throughout the system. The pulse thus includes both a data component and a timing component, the timing component being represented by the timing of the pulse.

In step 8-2, the data pulse signal receiving unit 31 demodulates the received input data pulse signal Sin31, and separates it into an impulse signal representing the timing component and a data signal representing the data component. The separated impulse signal is output to the communication timing controller 32 and steady-state decision unit 33 as the received impulse signal Spr31. The data component is output to the data pulse signal transmitter 34 as a received data signal Spr32.

In step 8-3, the communication timing controller 32 calculates transmitting timings by the method described in the first embodiment. A repeated description will be omitted.

In step 8-4, the steady-state decision unit 33 makes steady-state decisions as described in the first embodiment, but does not generate the slot signal Spr14 described in the first embodiment.

In step 8-5, if the steady-state decision signal Spr34 indicates that the steady state has been reached, the data pulse signal transmitter 34 modulates the observation data Spr36 received from the sensor 35 or the received data signal Sin32 (or both) onto a pulse signal to generate an output data pulse signal Sout31, and transmits the output data pulse signal Sout31 when the phase signal Spr33 takes on a specific value .alpha.. .theta..sub.i(t)=.alpha. (0.ltoreq..alpha.<2.pi.)

If the steady-state decision signal Spr34 indicates a transitional state, the data pulse signal transmitter 34 transmits the pulse signal at the above timing without modulating observation data onto the pulse waveform.

In comparison with the first embodiment, which transmits separate data and timing signals, the third embodiment includes both data and timing information in the same output data pulse signal. In the third embodiment, accordingly, it is only necessary to avoid collisions between these data pulse signals; it is not necessary to avoid collisions between separate data signals. This enables data communication to remain relatively stable even when the number of mutually interacting nodes is extremely large and each node can be allotted only a very brief time for data transmission.

In the third embodiment, as in the first embodiment, even when nodes are added to or removed from part of the system or when a change occurs such as a malfunction or a change in location, a flexible response is made and efficient data communication is maintained.

Fourth Embodiment

Next, a fourth embodiment of the present invention will be described. The nodes in the fourth embodiment have the same structure as in the first embodiment, shown in FIG. 2, but the impulse signal transmitter 13 and data communication unit 15 use different frequency bands. Accordingly, the impulse signal transmitter 13 and data communication unit 15 cannot share transmitting circuitry to the same extent as in the first embodiment; a separate carrier signal must be generated and modulated for each frequency band.

Operations in the fourth embodiment that differ from operations in the first embodiment will be described below.

Since the output impulse signal Sout11 and the output data signal Sout12 are transmitted in different frequency bands in the fourth embodiment, these two signals do not have to be transmitted at separate times. The time slot used to transmit the output data signal Sout12 in the data communication unit 15 therefore starts at the transmission timing of the output impulse signal Sout11, and terminates at a timing preceding the generation of the closest received impulse signal Spr11. This condition can be satisfied by transmitting the output data signal Sout12 in a time slot in which the value .theta..sub.i(t) of the phase signal Spr12 satisfies the following condition. 0<.theta..sub.i(t)<.beta..sub.1-.delta..sub.2

The meaning of the symbols in the above condition is the same as in the first embodiment, and it is assumed, as in the first embodiment, that the output impulse signal Sout11 is transmitted when the phase signal Spr12 indicates zero phase, that is, when .theta..sub.i(t)=0.

The fourth embodiment provides the same effects as the first embodiment. In addition, since the fourth embodiment enables the output impulse signal Sout11 and output data signal Sout12 to be transmitted at overlapping times, it is possible assign wider time slots for the transmission of the output data signal Sout12 than in the first embodiment. This enables the fourth embodiment to continue stable operation at higher data traffic rates than in the first embodiment.

Fifth Embodiment

Next, a fifth embodiment of the present invention will be described. The nodes in the fifth embodiment have the same structure as in the first embodiment, shown in FIG. 2, except that the data communication unit 15 assigns quantified priority levels to the data it transmits, and the communication timing controller 12 dynamically controls the value of the natural angular frequency parameter .omega. (the basic transmission rate) at its own node, according to the quantified priority level. The priority level may represent, for example, a level of necessity, activity, urgency, or the like, and may also be related to the amount of data to be transmitted.

The fifth embodiment adds the following operations to the operations described in the first embodiment with regard to the communication timing calculations (step 3-3 in FIG. 3). Other operations in the fifth embodiment are the same as in the first embodiment.

In step 3-3, the data communication unit 15 quantifies the priority level of the data it receives and notifies the communication timing controller 12 of the priority level. The received data may be the observation data Spr15 received from the sensor 16, or data received from a neighboring node or by human intervention. A quantified priority level is generated each time the data communication unit 15 receives data to be transmitted.

The priority level may be determined from the type, content, attributes, quantity, and other properties of the data to be transmitted. Basically, the priority level represents the urgency with which the data must be transmitted. One exemplary way to generate a quantified priority level is to use a predetermined rule that assigns different priority weights to different types of data, and multiply the amount of data to be transmitted by the priority weight. If the data to be transmitted include several different types of data, a weighted sum may be taken.

The communication timing controller 12 dynamically controls the value of the natural angular frequency parameter .omega. (the basic rate) according to the quantified priority level. In one exemplary scheme, the natural angular frequency parameter .omega. is allowed to take on values that are integer multiples of a reference value equal to a predetermined minimum angular frequency. The minimum angular frequency may be determined experimentally according to the application or other system conditions. The reference value is assigned to the natural angular frequency parameter .omega. when the data communication unit 15 reports the lowest quantified priority value, and higher integer multiples are assigned for higher quantified priority values. As the quantified priority value increases, the natural angular frequency parameter .omega. increases in a series of steps.

In another exemplary scheme, the values of the natural angular frequency parameter .omega. are not limited to exact integer multiples of a reference frequency but may also be values in a predetermined vicinity of an integer multiple of the reference frequency.

In yet another exemplary scheme, each node has a quantified priority level that changes over time, so that .omega. is a function of time.

Regardless of the scheme used, uniform rules for controlling the value of .omega. are set in advance throughout the system. If the values of .omega. are mutually related by integer ratios or near-integer ratios, then even if different neighboring nodes have different values of .omega., a steady state can be reached and maintained in which the timings of the output impulse signals Sout11 transmitted by neighboring nodes are appropriately distanced from one another and data collisions are avoided as in the first embodiment.

The fifth embodiment provides the same effects as the first embodiment, with the further effect that neighboring nodes need not share transmission time on an equal basis; nodes with relatively more urgent needs to transmit data can receive larger shares of transmission time.

In a variation of the fifth embodiment, the value of .omega. is controlled on the basis of the processing power of the node instead of the urgency of the data to be transmitted. In this variation, each node has a fixed value of .omega., but among neighboring no