Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-03-14
2004-11-09
Yao, Kwang Bin (Department: 2667)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S255000
Reexamination Certificate
active
06816460
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
Related subject matter is disclosed in the co-pending, commonly assigned, U.S. Patent application of Ahmed et al., entitled “A Topology Sensing Scheme for Networks with Mobile Nodes,” Application No. 09/513,325, filed on Feb. 25, 2000.
FIELD OF THE INVENTION
This invention relates generally to communications and, more particularly, to wireless systems.
BACKGROUND OF THE INVENTION
An “ad-hoc” mobile network (ad-hoc network) is a wireless network that comprises a collection of nodes whose positions are continually changing. Unlike a regular wireless network, one can view an ad-hoc network as a network with no fixed infrastructure. For example, all the nodes function as routers and perhaps as base stations; and the mobility of the nodes causes frequent changes in network topology.
It is the varying network topology of an ad-hoc network that causes difficulty in applying routing techniques used in a conventional wireless network. In the latter, the nodes in the network are stationary and the links connecting the nodes go down infrequently. As such, it is possible to maintain the whole network topology at each node by sending topology-related information to all the nodes in the network via, what is known in the art as, “link-state,” updates. Since nodes go down infrequently—link-state updates are infrequent—and this approach works quite well in a conventional wireless network. However, in an ad-hoc network link-state changes are more frequent because of the shifting topology, thus generating many more link-state update messages throughout the ad-hoc network—and consuming valuable bandwidth in the process. Also, construction of consistent routing tables is difficult because of the delay involved in propagating link-state information.
Considering these factors, routing protocols for ad-hoc networks can be classified broadly into two categories: “table-driven” and “source initiated on-demand.” Table-driven routing protocols are similar to the above-mentioned conventional wireless routing approach, i.e., each node attempts to maintain consistent, up-to-date, routing information for all other nodes in the network. Examples of table driven routing protocols are “Destination-Sequenced-Distance-Vector” (DSDV), “Clusterhead Gateway Switch Routing” (CGSR), and the “Wireless Routing Protocol” (WRP) protocols. In contrast, source initiated on-demand routing protocols create routing information only when a source node needs a route to a given destination. Examples of source initiated on-demand routing protocols include “Ad-Hoc On-Demand Distance Vector” (AODV), “Dynamic Source Routing” (DSR), “Temporally Ordered Routing Algorithm” (TORA), and the “Zone Routing Protocol” (ZRP) protocol.
As an illustration of a source initiated on-demand protocol consider ZRP. In ZRP, each node maintains the whole network topology for a local area, or zone, around it. As such, if the node (i.e., the source node) has to send a packet to a destination address in the zone, that routing information is already available. However, if the source node has to send a packet to a destination address outside their zone, then the node initiates a query to all the nodes in the edge of its zone (i.e., edge nodes). If one of these edge nodes has the routing information for the destination address, then that routing information is passed on back to the source node.
SUMMARY OF THE INVENTION
We have observed that the above-mentioned forms of ad-hoc network routing protocols generally require a node maintaining accurate information, in one form or another, about how to route to a node in regions that are far away from it. As such, if the number of nodes is large and spread over a large geographical area, and if there is reasonable mobility of the nodes, getting this information becomes difficult—if not impractical. Therefore, and in accordance with the invention, a source node uses a geometry-based routing protocol (GRP) to route traffic to a destination node. In the GRP, a source node routes a packet to a destination node outside of its local node topology (referred to herein as the local topology) as a function of the distance to the destination node.
In an embodiment of the invention, a source node maintains location information and routing information for all nodes in a local area, or local topology, and at least approximate location information for at least some nodes outside the local area. If the source node has to send a packet to a destination node in their local area, that routing information is already available. However, if the source node has to send a packet to a destination node outside their local area, then the source node uses the approximate location information of the destination node to identify which node in the local area is closest to the destination node in the local topology. If the identified local node is different from the source node, the latter transmits the packet to the identified local node, which then attempts to route the packet to the destination node. Otherwise, the packet is dropped.
REFERENCES:
patent: 5253248 (1993-10-01), Dravida et al.
patent: 5412654 (1995-05-01), Perkins
patent: 5596719 (1997-01-01), Ramakrishnan et al.
patent: 5610904 (1997-03-01), Eng et al.
patent: 5652751 (1997-07-01), Sharony
patent: 5737318 (1998-04-01), Melnik
patent: 5959568 (1999-09-01), Woolley
patent: 5987011 (1999-11-01), Toh
patent: 6046978 (2000-04-01), Melnik
patent: 6304556 (2001-10-01), Haas
patent: 6307843 (2001-10-01), Okanoue
patent: 6366560 (2002-04-01), Ohiwane et al.
patent: 6456599 (2002-09-01), Elliott
patent: 6535498 (2003-03-01), Larsson et al.
Camara, Daniel et al., “A Novel Routing Algorithm for Ad Hoc Networks”, Proceedings of the Hawaii International Conference.*
Basagni, Stefano et al., “A Distance Routing Algorithm for Mobility”, Erik Johnson School of Engineering University of Texas, Mobicom, 1998.*
Amouris, K. N. et al., “A Position-Based Multi-Zone Routing Protocol for Wide Area Mobile Ad-Hoc Networks”, Houston, Tx, May 16-20, 1999, New York, IEEE.*
S. Corson, J. Macker, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations”, RFC 2501, The Internet Society, Jan. 1999.
Z. J. Haas, M. R. Pearlman, The Zone Routing Protocol (ZRP) for AD Hoc Networks, IETF internet draft, Nov. 1997.
J. Broch, D. B. Johnson, D. A. Maltz, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks”, IETF internet draft, Oct. 1999.
D. Camara et al, “A Novel Routing Algorithm For Ad Hoc Networks”,Proceedings of HICSS33: Hawaii International Conference on System Sciences, vol. 2, Jan. 4-7, 2000, pp. 1-8, Maui, Hawaii.
S. Basagni et al, “A Distance Routing Effect Algorithm For Mobility (DREAM)”, Dallas, TX, Oct. 25-30, 1998, New York, New York:ACM, US, Oct. 25, 1998, pp. 76-84.
Jerzy et al, “Relative Neighborhood Graphs and Their Relatives”,Proceedings of the IEEE, vol. 80, No. 9, Sep. 9, 1992, pp 1502-1517.
Amouris, K. N., et al: “A Position-Based Multi-Zone Routing Protocol for Wide Area Mobile Ad-Hoc Networks”, Houston, TX, May 16-20, 1999, New York, NY: IEEE, US, vol. CONF. 49, May 16, 1999, pp. 1365-1369; p. 1365, col. 2, paragraph 3; p. 1366, col 1, line 5 “The choice of link-state CRP is arbitrary.” p. 1366, col 2, line 28-line 34; p. 1367, col 1, line 12-line 17, step 1, Step 2, p. 1367, col 2.
Rahul Jain, Anuj Puri, Raja Sengupta: “Geographical Routing Using Partial Information for Wireless Ad Hoc Networks”, Internet, “Online!” 20 De. 1999, retrieved from the Internet: <URL:http://citeseer.nj.nec.com/336698.htm1> retrieved on Apr. 2, 2001, p. 4, paragraph 4.1-p. 5, p. 6, paragraph 4.1.2.
Ahmed Walid
Jiang Hong
Kodialam Muralidharan Sampath
Monogioudis Pantelis
Rege Kiran M
Lucent Technologies - Inc.
Yao Kwang Bin
LandOfFree
Location based routing for mobile ad-hoc 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 Location based routing for mobile ad-hoc networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Location based routing for mobile ad-hoc networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3343778