Multiplex communications – Communication over free space – Message addressed to multiple destinations
Reexamination Certificate
2000-08-29
2004-08-24
Kizou, Hassan (Department: 2662)
Multiplex communications
Communication over free space
Message addressed to multiple destinations
C370S348000, C370S390000, C370S443000
Reexamination Certificate
active
06781967
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to an improved dynamic assignment protocol, more particularly relates to improvements to receiver directed broadcast schemes, and even more particularly relates to implicit reservation and optimized scheduling techniques for receiver directed broadcast schemes.
BACKGROUND OF THE INVENTION
Mobile multi-hop packet radio networks are known for rapid and convenient deployment, self-organization, mobility, and survivability. Such a network is illustrated in
FIG. 1. A
transmission from one node, from node N
1
of
FIG. 1
for example, can be broadcast to all nodes in its “neighborhood.” Ultra-high frequency (UHF) systems generally have a neighborhood defined by nodes located within line of sight of the transmitting node. The nodes of such a neighborhood are said to be located within one “hop” of the transmitting node. In
FIG. 1
, for example, nodes N
1
, N
3
, N
4
, N
5
, N
6
, N
7
and N
8
are members of the neighborhood surrounding node N
1
.
Nodes N
2
, N
9
, N
10
, N
11
and N
12
are each located two hops away from node N
1
and node N
13
can be said to be three hops away from node N
1
. When data transmitted from node N
1
is to be propagated multiple hops, the data must be relayed by one or more of node N
1
's neighbors. For example, data transmitted by node N
1
can be relayed by its neighbor node N
8
to a node such as node N
12
that is located two hops from node N
1
.
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 slots to nodes. The approach chosen for a particular application is generally a consequence of the type of network application (broadcast, multicast, unicast, datagrams, virtual circuits, etc.) at issue. Since the problem of optimally assigning slots is mathematically intractable, a heuristic approach has been applied. This approach resulted in the development of an integrated protocol that both chooses the number of slots to assign to each neighboring node and coordinates their activation in the network.
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.
The Unifying Slot Assignment Protocol (USAP), which is disclosed in U.S. Pat. No. 5,719,868, provides a protocol establishing such a communication 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. In one embodiment of USAP, receiver directed broadcast (RDB), a node can assign itself a receive slot instead of a transmit slot. For example, a node may need to assign itself a receive slot wherein it can receive from one, some or even all of its neighbors. This receiver directed type of assignment is disclosed in application Ser. No. 09/552,144, filed Apr. 19, 2000. The specification, including all drawing figures, of application Ser. No. 09/552,144, filed Apr. 19, 2000, is hereby incorporated herein by reference in its entirety.
There exists a need for further refinements and improvements to dynamic assignment protocol based systems using RDB. In particular, there exists a need for a technique that can implicitly reserve slots, for use in virtual circuits for example. In explicit reservation techniques, slots are taken from idle transmitters and are explicitly reassigned to nodes needing additional transmit capacity. In various applications, however, the use of explicit reservations can lead to an inefficient use of communication resources. Voice or video transmission applications, for example, can often tolerate a degree of initial packet loss and delay.
There is also a need to maximize throughput in systems using RDB schemes. For example, there exists a need for an optimized RDB scheduling technique that is capable, under heavy uniform traffic and for a given number of nodes and channels, of keeping each node busy all of the time. These needs are 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 technique for reserving slots in a receiver directed broadcast environment.
It is a feature of the present invention to utilize an implicit reservation of communication slots.
It is an advantage of the present invention to bring about a significant reduction of overhead by reducing the size of the control packet.
It is another object of the present invention to provide an improved technique for scheduling transmissions in a receiver directed broadcast environment.
It is another feature of the present invention to utilize an optimized RDB scheduling technique.
It is another advantage of the present invention to enable attainment of maximized throughput by keeping substantially every node busy transmitting or receiving nearly all of the time.
Thus, the present invention involves improved receiver directed broadcast systems and methods. The improvements can be carried out in an efficient, “waste-less” manner in the sense that throughput can be maximized or control overhead can be minimized. As noted herein, and as will be appreciated, the invention has several useful and valuable applications.
REFERENCES:
patent: 4504946 (1985-03-01), Raychaudhuri
patent: 4763322 (1988-08-01), Eizenhofer
patent: 5012469 (1991-04-01), Sardana
patent: 5117422 (1992-05-01), Hauptschein et al.
patent: 5245609 (1993-09-01), Ofek et al.
patent: 5295140 (1994-03-01), Crisler et al.
patent: 5396496 (1995-03-01), Ito et al.
patent: 5420858 (1995-05-01), Marshall et al.
patent: 5448698 (1995-09-01), Wilkes
patent: 5450394 (1995-09-01), Gruber et al.
patent: 5457681 (1995-10-01), Gaddis et al.
patent: 5502722 (1996-03-01), Fulghum
patent: 5506848 (1996-04-01), Drakopoulos et al.
patent: 5568477 (1996-10-01), Galand et al.
patent: 5581548 (1996-12-01), Ugland et al.
patent: 5594720 (1997-01-01), Papadopoulos et al.
patent: 5598417 (1997-01-01), Crisler et al.
patent: 5625629 (1997-04-01), Wenk
patent: 5652751 (1997-07-01), Sharony
patent: 5696903 (1997-12-01), Mahany
patent: 5719868 (1998-02-01), Young
patent: 5742593 (1998-04-01), Sharony et al.
patent: 5748362 (1998-05-01), Delacourt et al.
patent: 5920703 (1999-07-01), Campbell et al.
patent: 5949760 (1999-09-01), Stevens et al.
patent: 5953344 (1999-09-01), Dail et al.
patent: 5983259 (1999-11-01), Campbell et al.
patent: 6018528 (2000-01-01), Gitlin et al.
patent: 6031827 (2000-02-01), Rikkinen et al.
patent: 6084888 (2000-07-01), Watanabe et al.
patent: 6084889 (2000-07-01), Murakami
patent: 6094425 (2000-07-01), Auger et al.
patent: 6094429 (2000-07-01), Blanchette et al.
patent: 6157656 (2000-12-01), Lindgren et al.
patent: 6252868 (2001-06-01), Diachina et al.
patent: 6256304 (2001-07-01), Vayrynen
patent: 6256477 (2001-07-01), Eidson et al.
patent: 6275506 (2001-08-01), Fazel et al.
patent: 6304559 (2001-10-01), Jacklin et al.
patent: 6310867 (2001-10-01), Tat et al.
patent: 6314084 (2001-11-01), Kahale et al.
patent: 6317436 (2001-11-01), Young et al.
patent: 6324184 (2001-11-01), Hou et al.
patent: 6331973 (2001-12-01), Young et al.
Eppele Kyle
Jensen Nathan O.
Kizou Hassan
Lee Timothy
Rockwell Collins, Inc.
LandOfFree
Scheduling techniques for receiver directed broadcast... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheduling techniques for receiver directed broadcast..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling techniques for receiver directed broadcast... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3302563