Abstract:
The present invention is directed to a network communications system the purpose of which is to foster cooperation between synergistic nodes. Such a network is designed specifically to support information gathering and dissemination and is not intended as a general-purpose communications network. In particular, network communications involve transmitting nodes “blindly” broadcasting information in all directions without consideration for the identity of receiving nodes; and receiving nodes “blindly” receiving information, accepting all transmissions on a pre-defined frequency regardless of, and without knowledge of, origin.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application claims priority to U.S. Provisional Application No. 60/497,427, filed Aug. 22, 2003, the entire contents and substance of which are hereby incorporated in total by reference. 
     
    
     FIELD OF THE INVENTION  
       [0002]     This application relates to the field of wireless data communication networks, and more particularly to establishing a communication network to support incoherent broadcasts between unnamed nodes. In such communications transmitting nodes “blindly” broadcast information in all directions without consideration for the identity of receiving nodes; and receiving nodes “blindly” receive information, accepting all transmissions on a pre-defined frequency regardless of, and without knowledge of, origin.  
       BACKGROUND OF THE INVENTION  
       [0003]     Three general types of communication network systems are commonly used today: Broadcast networks, Telecommunications Networks and Server-Based Computer Networks. Broadcast networks communicate information from sources to receivers as incoherent wireless broadcasts. This communication technique may be used to convey information to millions of receivers with a single broadcast. An additional advantage of wireless broadcast networks is that they require no infrastructure outside of the transmitter and receivers. Telecommunication networks use directed communications to support bi-directional information flow allowing individual nodes to both transmit and receive information. Another advantage of telecommunications networks is that they allow for communication between nodes that cannot directly communicate. A specialized case of telecommunications networks is the computer network; a distinguishing feature of which is the ability to support the asynchronous transfer of information through the use of servers. There exist situations in which such general purpose communication systems are not well suited. One example is a situation in which the primary goal of the system is to gather and disseminate information that is being acquired by nodes of the system. In such a situation the network need not support explicit communications between arbitrary nodes; rather, information should be disseminated appropriately across the network. The present invention relates to such a communication network having a primary function of gathering and disseminating information. In this network a transmitting node blindly broadcasts information in all directions without concern of who the recipients are. The communication system of the present invention is particularly applicable in situations where information is being transferred between cooperating intelligent and semi-intelligent entities. Moreover, the present invention permits such signaling to be performed in a highly dynamic environment. Examples of such situations are: cars that wish to provide their drivers with traffic conditions of the road ahead and ad hoc collections of unmanned vehicles on a search and destroy mission. Further applications relate to communications involving cooperative entities that use heterarchical control including, but not limited to entities that use: swarm behavior, potential fields and Markov blankets.  
       SUMMARY OF THE INVENTION  
       [0004]     The present invention is directed to a network communications system the purpose of which is to foster cooperation between synergistic nodes. Such a network is designed specifically to support information gathering and dissemination and is not intended as a general-purpose communications network. That is, the communication system of the present invention network is not intended to specifically support explicit communications between arbitrary nodes; rather, it enables information to be disseminated appropriately across the network. Additionally, because the intended use of the network is to foster cooperation in a highly dynamic environment (e.g. cars moving on a roadway system), the present invention creates a network that is highly robust and supports ad hoc formation.  
         [0005]     To achieve these various goals, the communications network of the present invention exhibits various features derived from one or more of the prior art communications networks noted above. In particular, it exhibits the following desired features: 
        Transmit efficiently,     Transfer information between nodes that are not in direct communication,     Use no infrastructure other than nodes;     Support bi-directional transmission of information, and     Support asynchronous transfer of information.        
 
         [0011]     The networking mechanism used in the present invention to satisfy these conditions shall be referred to herein as a propagation network. In such a propagation network, incoherent broadcasts occur between unnamed nodes. That is, transmitting nodes blindly broadcast information in all directions without consideration for the identity of receivers; and receiving nodes blindly receive information, accepting all transmissions on a pre-defined frequency regardless of, and without knowledge of, origin. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]     Various embodiments of the present invention will now be described in detail in conjunction with the annexed drawings, in which:  
         [0013]      FIG. 1  illustrates an embodiment of the invention having a three-layer communication structure;  
         [0014]      FIG. 2  illustrates an exemplary format for data transmitted by a network node and,  
         [0015]      FIG. 3  illustrates an embodiment of the invention in which the network comprises three nodes. 
     
    
     DETAILED DESCRIPTION  
       [0016]     In one embodiment of the invention the network comprises a collection of nodes, each having the capability of wireless transmitting and receiving of information. Further, at least some of these nodes are capable of gathering information through sensors.  FIG. 1  illustrates an embodiment of the invention in which the depicted propagation network comprises a three-layer architecture. Two nodes are illustrated, each having this three layer structure. As illustrated with respect to Node  1 , the architecture&#39;s lowest layer is the coordination layer  102 . The coordination layer is responsible for assuring that proximate nodes in the network transmit at differing times. As defined herein, the term proximate node is intended to mean a node that is sufficiently close to a subject node that either the subject node can “hear” a transmission of the proximate node and/or the proximate node can “hear” a transmission of the subject node (i.e. proximate nodes are nodes whose communications are capable of interfering with one another).  
         [0017]     The middle layer is the data link layer  104 . Similar to the data link layer in an Open System Interconnection (OSI) model, this layer is responsible for packing and unpacking packetized information transmitted between cooperating entities. Thus, as illustrated in  FIG. 1 , data  110  is communicated at this level between node  1  and node  2 .  
         [0018]     The upper layer is the knowledge layer  106 . The knowledge layer is responsible for maintaining the node&#39;s knowledge base, a repository of “known” facts. The knowledge layer uses facts received from other nodes as well as facts organically derived from within the nodes (e.g. observations from sensors) to populate the knowledge base. In addition, the knowledge layer is responsible for determining when and what information should be transmitted. Each of these three layers will now be discussed in greater detail.  
         [heading-0019]     Coordination Layer  
         [0020]     In an embodiment of the invention, the principle function of the coordination layer is to time-multiplex communicating nodes so that they make use of time available for communications while preventing simultaneous transmission. In this embodiment, secondary functions of the coordination layer are to determine the duration of allowable transmission bursts and to determine the density of proximate nodes. The density of proximate nodes is used by the knowledge layer to determine when, and what, knowledge should be transmitted.  
         [0021]     To accomplish these functions, the coordination layer  102  periodically sends a transmit now (t) signal to the data link layer  104  indicating the data link layer may transmit after a fixed delay (ε t ). Along with this t signal, the coordination layer also supplies the data link layer with the two transmission parameters: the maximum permitted length of transmission (L t ) and the current node count (N t ). These parameters are determined for each individual node by essentially listening and counting the number of synchronization pulses signals emanating from neighboring, proximate nodes. That is, each node periodically transmits a short synchronization pulse signal  108 . In a further embodiment of the invention, such pulse signals are sent by all nodes at a frequency (ω i ). Overlapping transmissions are avoided by engendering phase distribution across communicating nodes by utilizing the well-known principle of coupled oscillation. By way of example, one embodiment of the invention has each node adjust its phase θ i  in accordance with the equation: 
 
θ i ′=θ i   +K   1   /N   t (Σ(cos( K   2 θ j )); 
 
 where θ i  denotes the “next” θ i ; K 1  and K 2  are constants, N t  is the number of nodes “heard” and θ j  is the phase (as indicated by a received pulse) of a neighboring node. 
 
         [0023]     In an additional embodiment the length of transmission L t  is derived from the equation: 
 
 L   t   =ω   i   /K   3   N   t  where  K   3  is a constant. 
 
         [0024]     It should be noted that N t  will not only vary as a function of time but will vary between nodes. That is, as the present invention contemplates mobile nodes whose positions change relative to one another, the number of neighboring nodes whose transmissions are capable of being heard will vary. Values for K 1 , K 2  and K 3  are determined to synchronize communications in a way that is frequency locked and anti-phase. In various embodiments of the invention, these K&#39;s are set to initial values based on characteristics of the network (e.g., number of nodes, range of node communications, size of information to be communicated at a given time, etc.).  
         [heading-0025]     Data Link Layer  
         [0026]     In an embodiment of the invention the data link layer  104  transmits data between nodes. The data being communicated relates to beliefs. A belief is data that has some degree of truth and is assumed to be true. In this embodiment of the invention the nodes have synergistic goals and operate on the same belief system.  
         [0027]     By way of example, in a network where nodes monitor traffic conditions, each node might be a car having its speedometer and Global Positioning System as its sensors. In this example a slow speed on a section of interstate highway would be used to form the belief that “traffic is heavy at mile marker  109 .” 
         [0028]     The data link layer  104  transmits this data in bursts. Bursts are a continuous stream of bytes whose time of transmission is less than L t . As depicted in  FIG. 2 , a burst  201  consists of a sequence of one or more beliefs ( 206 ,  208 , . . . ) preceded by a burst id  202  and a belief count  204 . In one embodiment of the invention the burst id is simply a sequential, 8-bit counter (that resets to 0 after 256 transmissions). Each belief consists of a label  210 , which identifies the type of belief; a value  212  for the label; and a time field  214  associated with the belief, where this time is relative to the time of transmission. In further embodiments of the invention, this time field is optional.  
         [0029]     In additional embodiments of the invention transmission, reliability may be enhanced by borrowing receipt acknowledgement strategies for point-to-point communications commonly used in computer networks to the data link layer. Transmission security may be enhanced in the data link layer by encoding packets with encryption based upon a one-time pad; a one time pad that is provided to each cooperating entity at deployment. Public-key private key encryption strategies are not applicable to this type of network as nodes are unnamed.  
         [heading-0030]     Knowledge Layer  
         [0031]     In this embodiment of the invention the knowledge layer  106  is focused upon the administration of an internal representation of known facts known as the knowledge base. The nature of knowledge and the mechanisms for fusing and reducing knowledge are well-known and vary with a network&#39;s particular application. As the propagation networks of the present invention are intended for a wide variety of applications, the nature of knowledge will not be addressed here. Rather this description of the present invention will focus upon the construction and requirements necessary for the knowledge layer to fulfill its role.  
         [0032]     The knowledge layer performs two functions. First, the knowledge layer accepts beliefs and merges them into the knowledge base. Beliefs may be accepted from the node&#39;s sensors or from transmissions received through the data link layer. In merging the beliefs the knowledge layer must resolve contradictory beliefs and (as necessary) reduce the complexity of the knowledge base by various well-known techniques such as compression, removal of less important knowledge, and aggregation.  
         [0033]     The second role of the knowledge layer is the generation of beliefs to be transmitted. Beliefs are transmitted in two forms: partial transmissions, in which only select beliefs determined by the knowledge layer to be of particular importance are transmitted; and complete beliefs in which all beliefs within the knowledge base are transmitted. When newly received information changes the belief state, the list of beliefs that have changed is sent to the data link layer. Also, when a new cooperating entity arrives (as indicated by a rise in the node count N t ) a list of all currently held beliefs is sent to the data link layer. Upon receiving a list of beliefs the data link layer decomposes the list into one or more bursts. Beliefs are transmitted according to the following simple algorithm: 
        If N t &lt;1 then Transmit nothing     Else if N t &gt;N t-1  then Transmit complete belief     Else Transmit ∀belief i  for which (belief i  at time t)≠(belief at time t-1).        
 
         [0037]      FIG. 3  illustrates an example of the present invention in which three nodes n 1 , n 2  and n 3  of a propagation network are depicted. Each of these nodes is depicted as a center of a circle, the area of which (A 1 , A 2  and A 3 , respectively) represents its area of communication. In this example, the broadcast range of each node&#39;s transmitter is assumed to be equal to the range of its ability to receive signals, these ranges are equal for all three depicted nodes, and these ranges are depicted as being symmetric circles with the node at the center. These assumptions are not meant to imply any limitations on the present invention but are merely invoked to simplify the drawing.  
         [0038]     In this example and as described previously above, each of the nodes periodically transmits a synchronization pulse  108 . As illustrated by the depicted communication ranges, node n 1 , being in n 2 &#39;s area of communication, hears the synchronization pulse of node n 2  but not that of n 3 . Consequently at time t depicted in  FIG. 3 , N t  of node n; is 1.  FIG. 3  also depicts an arrow, D, indicating the direction of motion of n 3  relative to n 1 . Accordingly, at some future time N t , n 3  will be “heard” by n 1  and N t′ =2. Upon this increase in N t , the above described algorithm will trigger n 1  to broadcast its complete belief list to all of its proximate nodes (to include n 3 ). Similarly n 3  will at some point recognize that it has an additional proximate node and will transmit its complete belief list. In this manner information is shared between new members on the scene.  
         [0039]     The communication algorithms above also describe how a changed belief would be transmitted. Thus by way of example, information gathered by n 2 &#39;s sensor may trigger it to communicate a changed belief. Receiving this information may cause n 1  to similarly broadcast a changed belief—perhaps to one of its proximate nodes which may not be in the communication range of n 2 . In this manner communication propagates throughout the network without any infrastructure other than the nodes.  
         [0040]     While the invention has been described with reference to the preferred embodiment thereof, it will be appreciated by those of ordinary skill in the art that modifications can be made to the structure and elements of the invention without departing from the spirit and scope of the invention as a whole.