Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
1995-09-07
2001-02-20
Olms, Douglas W. (Department: 2603)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S462000
Reexamination Certificate
active
06192053
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to wireless data communications, and more particularly to a method and apparatus for establishing at a given wireless node, the availability of neighboring nodes for communications and certain characteristics of these neighboring nodes.
It is desirable to provide wireless data communications services comparable to those available via wired links. However, the physical limitations inherent in wireless communications prevent the ready adaptation of protocols developed in the wired context to wireless applications. In particular, protocols that require nodes in a network to collect and take advantage of information about the other nodes with which they may communicate do not readily transfer to the wireless context.
One example of a wired communications protocol unsuitable for wireless application is the CSMA/CD multiple access protocol commonly used to resolve shared media contention in local area networks (LANs). This link layer protocol takes advantage of so-called carrier sensing to reduce the frequency of collisions on a shared medium. When one node coupled to the shared medium is transmitting, other nodes can sense this and stay off the medium until it is free.
Radio-based protocols, despite relying on a shared medium, cannot usually rely on carrier sensing. In the first place, it is fairly difficult and time consuming to determine in a wireless context whether or not a transmitter is active. Furthermore, another obstacle to the successful application of carrier sensing techniques is that the physical medium used by wireless communications is not shared in the same sense as the LAN medium is shared. In the LAN context, a node that can talk to one node, can talk to and be heard by all nodes. In the wireless context, a node A may be able to communicate with a node B that itself can communicate with a node C while node A cannot itself communicate with node C. Thus, a transmission from node C to node B could interfere with a transmission from node A to node B, even though node A cannot hear node C and thus would not know to inhibit itself from transmitting while node C is transmitting. This is the so-called hidden terminal problem. If only node C can communicate with a node D, another problem would arise in that a transmission from B to A would inhibit a transmission from C to D even though D would not be able to hear B. This is the so-called exposed terminal problem.
Another such protocol unsuitable for wireless application is the Address Resolution Protocol (ARP). ARP is a network layer protocol belonging to the Internet Protocol (IP) suite and is widely used to translate IP addresses into LAN addresses. Typically, to support address translation by ARP, a node connected to a LAN that needs to translate an IP address into a LAN link layer address sends out an ARP broadcast message specifying the IP address. The LAN node having that IP address then responds to the ARP broadcast message with a message including the IP address and LAN address. Unfortunately, broadcasting ARP messages to acquire link layer addresses is impractical in the wireless context because all nodes cannot hear a single broadcast and thus the ARP messages would have to be endlessly relayed, causing congestion and degradation of network performance.
Other problems related to knowledge of neighboring nodes arise in the area of routing protocols. Protocols used to establish routing information in wired systems such as the Open Shortest Path First (OSPF) protocol used in IP require complex synchronization of routing information between adjacent nodes and do not take into account the less reliable nature of wireless links, in that some connections may be asymmetric (one way channel), and that wireless links in general will have a high bit error rate. Nor do they take into account that, for wireless links, transmission and processing delays vary on a per link basis.
SUMMARY OF THE INVENTION
The invention provides an Adjacency Detection Protocol (ADP) whereby a node in a wireless network may collect information about its neighbors. The collected information enables the efficient establishment of link layer connectivity between a node and its neighbors and also is useful for translating network layer addresses into link layer addresses. The collected information finds further use in preventing medium contention among adjacent nodes and in handling collisions.
According to a first aspect of the invention, a selected node in a wireless network listens for certain link layer protocol messages from its neighbors. The link layer protocol message may be a broadcast message sent out for this purpose, a targeted message sent to the selected node for this purpose, or a link layer protocol message having some other purpose. If one is received, the selected node creates an entry in a link table for the originating node, sets a timer, and sends a reply specifically addressed to the originating node. If an acknowledgement is received from the originating node prior to expiration of the timer, the link is marked as a good link.
The acknowledgement may include certain useful parameters of the originating node relating to its latency time in processing messages.
According to a second aspect of the invention, a protocol for resolving medium contention in a wireless network is enhanced by taking advantage of stored information about the message processing time of neighbors. A first node in the wireless network receives a packet from a second node that includes parameters relating to the second node's message processing time. Thereafter, when the first node overhears a ready-to-send packet sent by a third node to the second node, it responds by inhibiting its own transmitter for long enough to allow the second node to respond with a clear-to-send packet. In accordance with the invention, this inhibition time incorporates the second node's latency time. Alternatively, if the first node overhears a clear-to-send packet sent by a third node to the second node, it inhibits its own transmitter for long enough to allow the second node respond by transmitting data. This inhibition time also incorporates the second node's latency time.
According to a third aspect of the invention, a selected node in a wireless network collects network layer address information about its neighbors. When a link to a neighbor is created in accordance by the link layer, the network layer is notified of the new link and responds by invoking a network layer protocol that obtains network layer address information about the selected node. The network layer address information is then available to network layer protocols for routing and other purposes.
The invention will be better understood by reference to the following detailed description in connection with the accompanying drawings.
REFERENCES:
patent: 5077732 (1991-12-01), Fischer et al.
patent: 5231534 (1993-07-01), Giles et al.
patent: 5231624 (1993-07-01), Giles et al.
patent: 5274841 (1993-12-01), Natarajan et al.
patent: 5276703 (1994-01-01), Budin et al.
patent: 5384777 (1995-01-01), Ahmadi et al.
patent: 5502724 (1996-03-01), Chen et al.
Karn, P., “MACA—A New Channel Access Method for Packet Radio,” (Conference Paper from Sep. 22, 1990 ARRL Conference in London, Ontario), pp. 134-140.
Chepponis, M., and Karn, P., “The KISS TNC: A Simple Host-to-TNC Communications Protocol,” 6th ARRL Computer Networking Conference, Aug. 29, 1987, Redondo Beach, CA, pp. 38-43.
Karn, P., and Lloyd , B., “Link Level Protocols Revisited,” Proceedings from the ARRL 5th Annual Computer Networking Conference, 1987., pp. 5.25-5.37.
Moy, J., Internet Engineering Task Force Network Working Group, RFC 1247, Jul. 1991, pp. 33-37.
Angelico Dean
Hayes James Alan
Ngo Ricky Q.
Olms Douglas W.
Trial & Technology Law Group
Wireless Networks, Inc.
LandOfFree
Enhanced adjacency detection protocol for wireless applications does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced adjacency detection protocol for wireless applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced adjacency detection protocol for wireless applications will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2588563