Multiplex communications – Communication over free space – Having a plurality of contiguous regions served by...
Reexamination Certificate
2000-04-03
2004-04-13
Vanderpuye, Kenneth (Department: 2661)
Multiplex communications
Communication over free space
Having a plurality of contiguous regions served by...
C370S338000, C370S348000
Reexamination Certificate
active
06721290
ABSTRACT:
TECHNICAL FIELD
The present invention is related to network communications. More particularly, this specification discloses a method and apparatus for the generation and maintenance of a wireless ad-hoc network for multicasting real-time constant-bit-rate (CBR) data among a plurality of nodes.
BACKGROUND
Wireless ad-hoc networks consist of collections of “peer” mobile nodes, capable of communicating with each other, and forming a dynamically changing network with no infrastructure. In order to route packets to a destination node, each node in a wireless ad-hoc network uses other nodes in the network as relays. Therefore, it is desirable that the nodes in the network establish routing among themselves, and that the routes keep changing as the nodes move, or as the environment changes due to such factors as fading and interference. Many routing protocols have been proposed to enable effective routing in such an environment, examples of which are provided in the articles cited below. In particular, multicasting has received much attention in the Internet community. Most of the development in multicast protocols, however, has addressed wireline, fixed networks having static topologies, and are focused toward Internet applications. The majority of these Internet multicast protocols do not consider the issue of resource reservation, because the available bandwidth is generally not a problem in wireline networks. Recently, the Core-Assisted Mesh Protocol (CAMP) was proposed for effective wireless multicasting of datagram traffic. However, CAMP neither supports real-time traffic nor does it attempt to guarantee any level of quality of service (QoS). No protocol developed to date addresses multicast streaming of real-time data in a wireless ad-hoc network environment.
Most multicast protocols result in the formation of a multicast structure, which is used for transportation of multicast data. Some schemes utilize core nodes or rendezvous points, which are used to collect multicast data from sources (if there are more than one) and then to multicast the data from these nodes to the receivers. The structure built may have the form of a tree or a mesh.
QoS is currently a focal point of attention in both wireline and wireless networks. There are two major ideologies for delivering QoS guarantees: the integrated services model and the differentiated services model. The integrated services model attempts to provide a guaranteed notion of service, which involves reserving bandwidth from the source node to the destination node. RSVP is a signaling protocol, which supports reservation of resources for multicast sessions on the Internet, is part of the integrated services specification. On the other hand, the differentiated services model is based on assigning resources to a user or edge router on a quasi-static basis. The resource is thus reserved based on what is called a service level agreement (SLA) and is then used to carry multiple classes of data. Each class of data receives a particular quality of service in terms of per-hop forwarding at each router. While, the differentiated services model is much simpler to implement than the integrated services model, it does not provide strict end-to-end quality of service guarantees in terms of bandwidth or delay.
Presently, there is a need for a multicasting method and system that is capable of supporting real-time CBR data among the nodes of a wireless network. It is also desirable that the system be distributed, highly adaptive to variations, flexible, and scalable.
References:
1. C. E. Perkins and P. Bhagwat, “Highly dynamic Destination-Sequenced Distance Vector routing (DSDV) for mobile computers”,
Proceedings of SIGCOMM
'94;
2. J. Broch et al, “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols”,
Proceedings of MOBICOM
'98;
3. D. Waitzmann, S. Deering and C. Partridge, “Distance vector multicast routing protocol”,
RFC
1075 (1988);
4. A. J. Ballardie, P. F. Francis and J. Crowcroft, “Core Based Trees”, in Proceedings of ACM SIGCOMM, 1993;
5. J. J. Garcia-Luna-Aceves and E. L. Madruga, “A multicast routing protocol for ad-hoc networks”, in
Proceedings INFOCOM
, 1999
6. P. Ferguson and G. Hutson, “
Quality of Service: Delivering QoS on the Internet and in Corporate Networks
”, John Wiley and Sons, Inc. 1998;
7. P. P. White, “RSVP and integrated services on the Internet: a tutorial”,
IEEE Commun
. Magazine, vol. 35, pp. 100-6, May 1997; and
8. http://pcl.cs.ucla.edu/projects/parsec/.
SUMMARY
A real-time multicast scheduler method and apparatus is presented, to facilitate multicasting of real-time constant bit rate data in wireless ad-hoc networks. Constant bit rate traffic cannot tolerate delay jitter. However, a small amount of packet losses may be tolerable. In order to ensure the provisioning of a desired level of quality of service, bandwidth is reserved on the multicast structure. A goal of the real-time multicast scheduler is to avoid packet collisions and to facilitate color re-use, where “color” is defined as a channel selected as a combination of time-division multiple access (TDMA), frequency-division multiple access (FDMA), and code-division multiple access (CDMA) schemes. The real-time multicast scheduler provides a self-healing network which corrects for disconnections caused by node movement and nodes moving out of range of each other, while accounting for colors already assigned for data transmission in order to prevent packet collisions.
Provided is a method for bandwidth reservation for real-time traffic in a wireless ad-hoc network that includes a plurality of nodes transmitting and receiving data via a plurality of colors. The transmitting and receiving of the data is performed periodically with a data period p. Each one of the nodes has either a connected, disconnected, or a temporarily disconnected connection state, and the plurality of nodes includes a communication origin node from which a data transmission occurs. Each node is further defined as having a frame position fp with respect to the origin node, a set of transmit colors in which the node is currently transmitting, a color in which the node is currently receiving, a set of usable colors, and a set of unusable colors, wherein the node which a particular node receives from is identified as the parent of the particular node, with the particular node identified as the child of the parent node. In what follows, the identification of a node is denoted the node ID.
The reservation method comprises the steps of:
a. periodically transmitting a disconnected maintenance packet from each disconnected node, with each disconnected maintenance packet including the disconnected maintenance packet transmitting node ID, the node ID of a parent node from which disconnected node seeks to receive, the frame position fp of the disconnected maintenance transmitting node, and the color in which the disconnected maintenance packet transmitting disconnected node seeks to receive;
b. periodically transmitting a connected maintenance packet from each connected node, with each connected maintenance packet including the node ID of the connected maintenance packet transmitting node, the node ID of the parent node from which connected node is currently receiving, the frame position fp of the node transmitting the connected maintenance packet, the color in which the connected maintenance packet transmitting node receives, a set of the usable colors in which the connected node may transmit, and a set of unusable colors in which the connected node is prohibited from transmitting;
c. periodically transmitting a temporarily disconnected maintenance packet from each temporarily disconnected node, with each temporarily disconnected maintenance packet including the node ID of the temporarily disconnected maintenance packet transmitting node, the node ID of the parent node from which temporarily disconnected node seeks to receive, the frame position fp of the node transmitting the temporarily disconnected maintenance packet, the color in which the temporarily d
Dao Son
Kondylis George D.
Krishnamurthy Srikanth V.
HRL Laboratories LLC
Tope-McKay & Associates
Vanderpuye Kenneth
LandOfFree
Method and apparatus for multicasting real time traffic in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for multicasting real time traffic in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for multicasting real time traffic in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3220196