Abstract:
A protocol for assignment, by an assigning node, of slots for full duplex communication in a dynamic distributed, multi-channel, time division environment is disclosed. The protocol is suitable for use with a dynamic assignment protocol such as USAP. The protocol can identify slots available for allocation for unicast communications or for allocation for broadcast communications. Nodes of the network share communication slot scheduling information. A node having data to communicate can examine the shared information and thereby identify those communication slots that are available for full-duplex communication with a selected neighboring node.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     Cross-reference is made to related U.S. application Ser. No. 08/539,396, entitled Dynamic Distributed, Multi-Channel Time Division Multiple Access Slot Assignment Method for a Network of Nodes, filed Oct. 5, 1995 (now U.S. Pat. No. 5,719,868, issued Feb. 17, 1998). 
    
    
     FIELD OF THE INVENTION 
     The present invention generally relates to an improved dynamic assignment protocol for a radio network, more particularly relates to a protocol for full-duplex communication, and even more particularly relates to an extension to USAP for enabling full-duplex communication. 
     BACKGROUND OF THE INVENTION 
     Mobile multi-hop packet radio networks are known for rapid and convenient deployment, self-organization, mobility, and survivability. Many applications require self-organizing, wireless networks that can operate in dynamic environments and provide peer-to-peer, multi-hop, multi-media communications. Key to this technology is the ability of neighboring nodes to transmit without interference. Neighboring nodes transmit without interference by choosing time slots and channels that do not cause collisions at the intended unicast or multicast receivers. 
     Receivers are generally capable of processing only one transmission at a time. When using such receivers, simultaneous transmissions (also known as collisions, contentions or conflicts) can be avoided by assigning a specific transmission time slot to each communicating node. Several approaches have been developed for assigning communication slots to nodes. The approach chosen for a particular application is generally related to the type of network application (broadcast, multicast, unicast, datagrams, virtual circuits, etc.) being implemented. 
     The Unifying Slot Assignment Protocol (USAP), which is disclosed in U.S. Pat. No. 5,719,868, provides a protocol establishing one such contention avoidance system. USAP is a dynamic assignment protocol that monitors the RF environment and allocates channel resources on demand. It automatically detects and resolves contention between nodes for time slots, such contention arising for example from changes in connectivity. U.S. Pat. No. 5,719,868, issued Feb. 17, 1998, is hereby incorporated herein by reference in its entirety, including all drawings and appendices. 
     USAP permits a node to assign itself transmit slots based on information it has regarding when it is assigned to transmit and receive and when a neighboring node is scheduled to transmit. The original USAP embodiments were designed for use with half-duplex radios and therefore do not support full-duplex communication. Since a full-duplex radio can transmit and receive at the same time, the use of full-duplex radios presents the potential of doubling network throughput relative to half-duplex radios. As a result, there exists a need for a dynamic assignment protocol that can support full-duplex radios. This need is addressed and fulfilled by the detailed description provided below. 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to provide an improved dynamic assignment protocol. 
     It is a feature of the present invention to utilize an assignment formula particularly suited to the support of full-duplex radios. 
     It is an advantage of the present invention to enable a dynamic assignment protocol such as USAP to be used in a network containing full-duplex radios. 
     The present invention provides an improved dynamic assignment protocol suitable for use with full-duplex radios. It is carried out in a “contention-less” manner such that collisions between communications transmitted between full-duplex radios are avoided. The invention includes embodiments for determining unicast and broadcast communication slot allocations. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The invention may be more fully understood by reading the following description of the invention, in conjunction with the appended drawings wherein: 
     FIG. 1 is a diagram illustrating a node activation form of communication. 
     FIG. 2 is a diagram illustrating a link activation form of communication. 
     FIG. 3 is a diagram of a time division multiple access structure suitable for use with the present invention. 
    
    
     DETAILED DESCRIPTION 
     Prior to the development of USAP, a heuristic approach was typically taken to design an application specific protocol that both chose the number of time slots to assign to each neighboring node and coordinated their activation. The USAP approach separates the slot assignment mechanism from the heuristic and creates a single generalized protocol for reliably choosing the slots and coordinating their activation. A dynamic assignment protocol such as USAP can be used to support higher level heuristics. 
     A node can transmit to its neighbors via essentially one of two different methods. One method, node activation, allows only one active transmitter in a neighborhood in a given time slot. The other method, link activation, can permit more than one simultaneous transmission in the same time slot. 
     In the node activation technique, a single transmitting node communicates data to all of its neighbors simultaneously rather than on an individual basis. Node activation, also known as multicast or broadcast communication, is especially well suited for applications like address resolution and conferencing. 
     The node activation technique is illustrated in FIG.  1 . In FIG. 1, a transmitting node N 15  is simultaneously sending  100 ,  102 ,  104 ,  106 ,  108  the same broadcast communication to each of its neighbor nodes N 14 , N 16 , N 17 , N 18  and N 19 . 
     In the link activation technique, the transmitting node has only one intended receiver. Link activation, also known as unicast communication, better serves high volume point-to-point traffic. The link activation technique is illustrated in FIG.  2 . In FIG. 2, three unicast transmissions are occurring simultaneously. Node N 15  is transmitting a unicast message  200  to node N 14 , node N 17  is transmitting a unicast message  202  to node N 16  and node N 19  is transmitting a unicast message  204  to node N 18 . In a full-duplex embodiment, each of the receiving nodes N 14 , N 16 , N 18  can also be simultaneously transmitting back to its respective transmitting node N 15 , N 17 , N 19 . 
     Referring to FIG. 3, a time multiplex structure  300  suitable for use with the present invention is depicted. The time multiplex structure  300  of FIG. 3 is a time division multiple access structure. One cycle  302  of the structure  300  includes “N” frames  304 . The number of frames  304  required for a particular embodiment is determined by the specifics of the underlying application. 
     FIG. 3 also illustrates the structure of a representative frame of the cycle. The time allocated to the representative frame is shown divided into “M” distinct time slots  306 . It will be appreciated that different numbers of time slots can be used in the various embodiments of the invention. The first slot of each frame  304  of the cycle  302  is a broadcast slot  308  for network management control packets. One of the N broadcast slots  308  is assigned to each node in the network. Therefore, for a network having N nodes, each node will transmit its control packet once during each cycle  302 . More than one broadcast slot per frame can be used if it is desired that each node transmit multiple control packets per cycle  302 . Further, the broadcast slots can be dynamically assigned using the USAP approach described herein. 
     Each frame  304  can also include multiple frequency channels  310 . In FIG. 3, “F” different frequency channels are illustrated in the representative frame. Different embodiments of the invention include different numbers of time slots  306 , channels  310  and/or frames  304 . 
     In USAP, specific constraints on communication slot allocation are included to avoid interference at any node located within two hops of the transmitting node. Other embodiments of USAP can require three, four or more hops of isolation before reuse of a slot is permitted. For a system, such as USAP, including multiple frequency channels, an allocation involves specification of both a time slot and a frequency channel. For a USAP unicast transmission from a node i to a neighboring node j, the transmit slot allocation is a slot: 
     that has not been already assigned to node i or node j, 
     in which node i&#39;s neighboring nodes are not receiving, and 
     in which node j&#39;s neighboring nodes are not transmitting. 
     For a multicast communication originating from a node i, the transmit slot allocation by node i is one: 
     that has not already been assigned to node i or any of node i&#39;s 
     neighboring nodes; and 
     in which none of node i&#39;s neighbors&#39; neighbors are transmitting. 
     A node such as node i can insure that its allocation s satisfy the above constraints by sharing the following USAP slot sets with its neighboring nodes: 
     STi—allocations in which node i is transmitting; 
     SRi—allocations in which node i is receiving; and 
     NTi—allocations in which node i&#39;s neighbors are transmitting. 
     The size of the above-defined slot sets will vary according to network density and the number of slots and channels being managed. To minimize the size of the control packet, the slot set information can be encoded, for example, as bit maps or as lists. Sharing of the slot set information via the control packets enables USAP to 1) select non-conflicting allocations consistent with the most recent topology measurements, and 2) detect and report conflicts caused by topology changes. 
     After a transmit allocation is selected, a node has the option of transmitting immediately or waiting until a confirmation is received from each neighbor. The unconfirmed mode is appropriate when it is acceptable to have momentary conflicts due to coincident changes in connectivity or conflicting allocations. The confirmed mode verifies that all neighbors are aware of the allocation and that nothing has occurred to make the allocation inconsistent with the current topology or the other nodes&#39; allocations. 
     To allocate a communication slot for full-duplex communication, a node first generates the set of slots that are not available because they are already in use locally. In the description that follows, the subscript “i” denotes information about the node performing the allocation and “j” denotes the corresponding information reported by a neighboring node. 
     The assignments are represented by: 
     S=set of time slots s; 
     F=set of frequency channels f. 
     For a given time slot and channel pair (s, f, the allocating node&#39;s transmit/receive sets are: 
     STNi(s, f)=set of neighbors to which node i transmits on (s, f) 
     SRNi(s, f)=set of neighbors from which node i receives on (s, f). 
     The following sets are then derived: 
     STi(s, f)=1 if STNi(s, f) not empty, else 0 
     SRi(s, f)=1 if SRNi(s, f) not empty, else 0. 
     The neighbor node transmit/receive sets are: 
     STj(s, f)=the STi(s, f) reported by a neighbor node j 
     SRj(s, f)=the SRi(s, f) reported by a neighbor node j. 
     Next, the following sets can be derived: 
     NTi(s, f)=∪STj(s, f) over all neighbors j of node i 
     NRi(s, f)=∪SRj(s, f) over all neighbors j of node i 
     NTj(s, f)=the NTi(s, f) reported by a neighbor node j. 
     If a node i is already transmitting or its neighbor node j is already receiving in slot s on any channel, both nodes are blocked from performing any other communication during slot s. In addition, if node i is receiving or node j is transmitting on any particular channel in slot s, both are likewise blocked. To this end, the following derived sets are useful: 
     Bi(s)=STi(s) ∪SRi(s,f) 
     Bj(s)=STj(s, f) ∪SRj(s). 
     To decide which slots and channels are available for full-duplex unicast allocation, a node i constructs the blocked allocations for transmitting to node j by excluding allocations: 
     that have been already assigned to node i or node j: Bi(s) ∪Bj(s) 
     in which node i&#39;s neighbors are receiving: NRi(s, f) 
     in which node j&#39;s neighbors are transmitting: NTj(s, f) 
     This information is combined as follows: 
     Blocked(i,j,s,f)=Bi(s) ∪Bj(s) ∪NRi(s, f) ∪NTj(s, f) 
     Blocked(i,j,s,f)=1 if node i cannot transmit to node j in (s, f), else 
     Blocked(i,j,s,f)=0. 
     To decide which slots and channels are available for full-duplex broadcast allocations, a node i constructs the blocked allocations for transmitting to all of its neighbors by excluding allocations: 
     that have been already assigned to node i: Bi(s) 
     that have been already assigned to any of node i&#39;s neighbors: ∪ ∀nε{i&#39;s     —     nbrs} Bj(s) 
     in which any of node i&#39;s neighbors&#39; neighbors are transmitting: ∪ ∀nε{i&#39;s     —     nbrs} NTj(s, f). 
     This information is combined as follows: 
     Blocked(i,s,f)=Bi(s)∪ ∀nε{i&#39;s     —     nbrs} Bj(s)∪ ∀nε{i&#39;s     —     nbrs} NTj(s,f) 
     Blocked(i,s,f)=1 if i cannot transmit to any of its neighbors in (s,f), else 
     Blocked(i,s,f)=0. 
     The slots not contained in Blocked(i, s, f) are available for use by node i to transmit to its neighbors. When node i allocates one of the available slots for such a purpose, it can receive therein a transmission from any of its neighbor nodes j, without creating conflicts for any other potential receivers in its neighborhood. 
     It is thought that the method and apparatus of the present invention will be understood from the description provided throughout this specification and the appended claims, and that it will be apparent that various changes may be made in the form, construct steps and arrangement of the parts and steps thereof, without departing from the spirit and scope of the invention or sacrificing all of their material advantages. The forms herein described are merely exemplary embodiments thereof.