Multiplex communications – Pathfinding or routing
Reexamination Certificate
2000-10-27
2004-09-07
Nguyen, Chau (Department: 2667)
Multiplex communications
Pathfinding or routing
C370S400000
Reexamination Certificate
active
06788670
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of forwarding information through multi-hop networks.
2. Description of Related Art
In a multihop communications approach, information is transmitted in multiple hops or segments between a source and a destination instead of directly (e.g., 1-hop). This approach can offer advantages such as lower power consumption and greater information throughput.
Bellman Ford and associated prior art routing techniques build up and define a multihop route from a source to a destination. This is done by passing routing cost information around to form a routing table. The cost information can include, for example, message delays, cumulative power consumption, and hop count. This information can be entered or summarized in the routing table. Within the system, each node or station uses the routing table to make independent decisions. Bellman Ford (also called “distance vector”) based routing leads to existence of a single route for each source-destination pair. However, as topology changes due to mobility, this single route (per source-destination pair) will pass different nodes over time.
Changes or fluctuations within the system imply that optimal routing can change based on current conditions in the system. In other words, fluctuation of system properties or characteristics over time, can create windows or peaks of opportunity that enable signal transmissions to be more successful than at other times and conditions. System properties subject to change can include, for example, path quality, noise, interference, and message traffic load. The prior art routing techniques such as Bellman Ford, do not recognize these windows of opportunity, because the stations in the system do not each store relative information.
In contrast, opportune routing techniques exploit opportunities that fluctuation provides. In the context of wireless routing in particular, overall system performance suffers when quality of links within the system varies rapidly over time (for example, due to Rayleigh fading). However, opportune routing partially offsets this loss of performance by using the windows or peaks of opportunity that the variation also provides. When opportune routing is employed, there is not a single route for each source-destination pair. Instead, data packets follow a route that is somewhat random, leading from the source to the destination. Consequently, when Bellman Ford is used, consecutive packets in Bellman Ford will be sent over the same route (provided topology of the network does not change in the meantime), whereas when opportune routing is used, consecutive packets may be routed over different paths but in the same direction.
U.S. Pat. No. 6,097,703, and also PCT International Application PCT/GB98/01651, published on Dec. 10, 1998 with International Publication Number WO 98/56140, describe an opportune routing system wherein each station in a network, monitors the activity of other stations in the network. Each station decides, independently and opportunistically, and at the time of transmission, which of the other stations it will use to relay a message. For example, a first station selects one of several candidate stations, and then forwards the message to the selected candidate. If this transmission is successful, then the selected candidate in turn selects one of several candidate stations, and the cycle repeats. If the transmission from the first station to the first selected candidate station is unsuccessful, then the first station sends the message to another of the candidate stations. If none of the candidate stations successfully receives the message, then the first station tells the previous station that it cannot forward data. In this situation the previous station will attempt to forward the data via another of its own candidate stations. Thus the cycles repeat, and the message either advances or falls back, depending on how the candidate stations respond.
In summary, disclosed opportune routing techniques appear to simply be faster forwarding algorithms put on top of a traditional, pro-active routing information protocol that itself is inherently slow. For example, in the text
Routing in Communication Networks
, edited by Martha E. Stenstrup, copyright Prentice Hall 1995, on page 388 it is stated that “An approach that avoids this problem uses multiple routing algorithms, working at different timescales: fast algorithms which work with local information but which produce suboptimal routes, and slower algorithms which use more global information to generate better routes.” And on page 353, “The need for rapid response means that multiple algorithms working at different timescales are required (fast algorithms that work with local information, and longer-term algorithms that use more global information).”
By way of further example, general monitoring disclosed in U.S. Pat. No. 6,097,703 and International Publication Number WO 98/56140 is a slow process. Monitoring is either handled by listening in on messages passing by, or by actively sending out probes. When a probe is sent out, a response is expected back that includes information, for example regarding path loss. When there is a delay between the return of a probe and a data transmission, then the information provided by the return of the probe may become obsolete by the time the data is transmitted. One undesirable consequence is that existing opportune routing techniques, and also Bellman Ford based routing techniques, do not handle possible diversity effects gracefully. Accordingly, better techniques are needed that perform quickly and handle diversity effects gracefully and effectively.
SUMMARY OF THE INVENTION
In accordance with exemplary embodiments of the invention, in order to transmit a data message in a multi-hop environment, a first station broadcasts or multicasts a transmission to other stations or receivers nearby. After one or more of the stations replies to the first station, the first station selects one of the stations that replied and transmits a command message to the selected station to assume responsibility for forwarding the data message. The data message can accompany the first transmission from the first station, or can accompany the command message. In addition, the replies to the first station can include information regarding costs of routing the data message to its destination.
In another variation, the first transmission can include both the data message and a command message designating one of the nearby stations, so that when the designated station receives the first transmission it can immediately forward the data message and then later reply to the first station. If the designated station does not reply to the first station within a time interval, then other stations that also received the data message can reply to the first station, and the first station can select and command one of them to forward the data message.
Both branch diversity and the capture effect can be used to enhance the data forwarding process. In particular, branch diversity provided by the broadcast/multicast reduces the need to use interleaved data together with coding to combat fading channels, and this in turn means less delay and therefore higher data throughput. The capture effect refers to a phenomenon wherein only the stronger of two signals that are at or near the same frequency, is demodulated, and the weaker signal is completely suppressed and rejected as noise. In conjunction with multiple receiving nodes or stations, the capture effect provides a high degree of robustness when data transmissions collide by maximizing the probability that at least one of the nodes will successfully receive the desired transmission. Exemplary embodiments of the invention are particularly effective when the data message or data information are larger than the signaling data.
REFERENCES:
patent: 5736933 (1998-04-01), Segal
patent: 5949760 (1999-09-01), Stevens et al.
patent: 5963559 (1999-10-01), Ohki
patent: 6028862 (2000
Nguyen Chau
Telefonaktiebolaget LM Ericsson (publ)
Wong Blanche
LandOfFree
Method for forwarding in multi-hop 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 Method for forwarding in multi-hop networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for forwarding in multi-hop networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3234165