Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-02-17
2004-03-09
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S254000, C370S392000, C370S400000, C455S445000, C709S242000, C709S243000
Reexamination Certificate
active
06704283
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique for the assignment and use of node addresses in a small, wireless data communications network or a small, wireless sub-network of a larger network and, more particularly, to a technique which permits network configuration data to be sent with every message without the need for complex routing protocols and without adding significant overhead to the network communications.
2. Description of the Prior Art
Conventional wireless networks typically permit nodes to communicate only if they are within range of each other (i.e., in the same “cell”). Sophisticated software protocols are typically required to control message traffic to permit communication from one cell to another. Such protocols typically add substantial overhead to the network communications. Also, to provide sufficient communications range, such systems typically require each node to have relatively powerful transmitters to communicate with all nodes in that cell. However, even when relatively powerful transmitters are used, communications may be interrupted when the source node or a destination node leaves the cell. Moreover, such systems are limited by the distance and direction to the destination node from the source node, and, as a result, complicated routing information must be transmitted periodically to all nodes in the network.
There has been a lot of work in the field of routing protocols in wireless networks. Conventional systems address the problem of routing protocols in small to large networks in which the nodes are not known beforehand by identifying the nodes identified only by their “IP addresses”. The associated routing protocols attempt to obtain a route from source to destination for packet communication. Such wireless networks can be classified under two broad categories: cellular network and ad hoc network.
In a cellular network there are few special nodes (commonly referred to as base stations) spread over an area. These “special nodes” can communicate amongst themselves via wired network, satellite, higher transmit power, etc. The users which normally have lower transmit power communicate with one of these special nodes. If there is a need to communicate with other wireless nodes, then message data is exchanged via other special nodes. However, there are several protocols to keep track of, such as, where the nodes are and what happens when moving nodes move from one cell to another.
In an ad hoc network on the other hand, there are no known special nodes. The network among the nodes has to first establish itself. Nodes exchange “Hello” messages to find neighbors and other information about neighbors. Some protocols require frequent exchanges of their own positions, links, etc. and, based on that information, all nodes attempt to keep optimized updated routes to all nodes in the network. Other sets of protocols do not keep updated route information, but when a source node needs to communicate with a specific destination, the destination node will be searched for.
It is desired to provide a communications system with simple software protocols for controlling message traffic which are concise enough to be appended to each message without adding significant over head to the communications system. Such protocols should also allow ad hoc communications among the nodes in an ad hoc wireless network without regard to the proximity of the other members of the network, particularly the destination node. The present invention has been designed to meet these needs in the art.
SUMMARY OF THE INVENTION
The present invention addresses the above-mentioned needs in the art by providing a technique for the assignment and use of addresses in a small, wireless data communications network or a small, wireless sub-network of a larger network where the endpoints of the network are widely dispersed relative to the range of their transmitters, which may be either radio, infrared, or other wireless media. The endpoints may be in motion and the path between any two endpoints may change over time.
In particular, the present invention relates to a method of transmitting a message from a source node to a destination node in a small, wireless network having up to N nodes in which each message has appended thereto concise network configuration data which eliminates the need for complex routing protocols without adding significant overhead to the network communications. The method guides the data packets to the destination without requiring the source and/or relay nodes to know the precise route to the destination. Rather, the source and/or relay nodes guide data packets to the destination via an appropriate neighboring node. Such a method in accordance with the invention includes the steps of creating for each node a route table containing a count of the number of transmission hops necessary to reach each other node in the network and a node number of a neighboring node forming a next link in a chain of hops to each other node, where the node number identifies a unique bit in an N bit address mask. Routing data is appended to the message data which includes an N bit destination word identifying the destination node or nodes, an N bit route word including a logical OR of the address mask of the relay node or nodes, and a route update message identifying what the current node knows about the network configuration. The number of N bit words in the route update message determines a maximum number of transmission hops away from the current node that the current node could know about the network configuration. Upon receipt of such message data and its routing data, all receiving nodes update their route tables from the route update message. Then, if the receiving node is a destination node, the message data is processed. Also, if the receiving node is a relay node, then the receiving node replaces the route word and route update message with data from its updated route table and retransmits the message data with the destination word, the replaced route word and the replaced route update message as its routing data.
In a preferred embodiment of the invention, the route from the source node to the destination node or nodes is determined by selecting a route with a minimum number of transmission hops. The address mask of the first node in the route is then selected as the route word. The destination word, on the other hand, is created by taking a logical “OR” of the address masks of each destination node, while the transmission node is typically determined using time, frequency, or code division techniques.
Upon receipt of a route update message, the route table of each node is updated by setting a relay word in the row of the route table in which the transmitting node is the destination node to the address mask of the transmitting node and setting a transmission hop count in the row of the route table in which the transmitting node is the destination node to
1
to indicate that the current node is directly connected to the transmitting node. Then, for route update messages having two or more N bit words, each N bit word in the route update message is stacked vertically from first to last. A column of bits corresponding to the unique bit in the N bit address of the destination node is then selected, and the number of transmission hops to the destination node is determined as the binary number in the column defined by reading the bits in the column downward from the stacked first to last N bit words in the route update message. The route table is then updated by performing the following steps for each column in the stacked N bit words of the route update message:
setting the destination node to correspond to the node identified by the column position in the stacked N bit words of the route update message;
selecting a row of the route table corresponding to the destination node;
if all bits in the column are “0” or all bits in the column are “1”, then if the selected row's relay node corresponds to the relay word, setting the transm
Newman Nisha Pauline
Stephens William Edward
Stiller Thomas Michael
Burke William J.
Hsu Alpus H.
Sarnoff Corporation
LandOfFree
Traffic routing in small wireless data networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Traffic routing in small wireless data networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Traffic routing in small wireless data networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3259381