Multiplex communications – Diagnostic testing – Path check
Reexamination Certificate
2002-04-29
2003-09-30
Marcelo, Melvin (Department: 2663)
Multiplex communications
Diagnostic testing
Path check
C370S255000, C370S345000, C455S449000
Reexamination Certificate
active
06628620
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of communication networks, and, more particularly, to mobile ad-hoc wireless networks and related methods.
BACKGROUND OF THE INVENTION
Wireless networks have experienced increased development in the past decade. One of the most rapidly developing areas is mobile ad-hoc networks. Physically, a mobile ad-hoc network includes a number of geographically-distributed, potentially mobile nodes sharing a common radio channel. Compared with other types of networks, such as cellular networks or satellite networks, the most distinctive feature of mobile ad-hoc networks is the lack of any fixed infrastructure. The network may be formed of mobile nodes only, and a network is created “on the fly” as the nodes transmit with each other. The network does not depend on a particular node and dynamically adjusts as some nodes join or others leave the network.
Because of these unique characteristics, routing protocols for governing data flow within ad-hoc networks are required which can adapt to frequent topology changes. Two basic categories of ad-hoc routing protocols have emerged in recent years, namely reactive or “on-demand” protocols, and proactive or table-driven protocols. Reactive protocols collect routing information when a particular route is required to a destination in response to a route request. Examples of reactive protocols include ad-hoc on demand distance vector (AODV) routing, dynamic source routing (DSR), and the temporally ordered routing algorithm (TORA).
On the other hand, proactive routing protocols attempt to maintain consistent, up-to-date routing information from each node to every other node in the network. Such protocols typically require each node to maintain one or more tables to store routing information, and they respond to changes in network topology by propagating updates throughout the network to maintain a consistent view of the network. Examples of such proactive routing protocols include destination-sequenced distance-vector (DSDV) routing, which is disclosed in U.S. Pat. No. 5,412,654 to Perkins; the wireless routing protocol (WRP); and clusterhead gateway switch routing (CGSR). A hybrid protocol which uses both proactive and reactive approaches is the zone routing protocol (ZRP), which is disclosed in U.S. Pat. No. 6,304,556 to Haas.
One challenge to the advancement of ad-hoc network development is that of extending such networks to encompass large numbers of nodes. One prior art attempt to do so utilizes “spine” routing, such as in the optimal spine routing (OSR) approach disclosed by Das et al. in “Routing in Ad-Hoc Networks using Minimum Connected Dominating Sets,”
IEEE Int. Conf. On Commun
. (ICC '97), 1997. In this approach, a spine or “virtual backbone” is defined such that each network node is no more than one hop from a spine node. Global topology (link state) is maintained at each spine node, and a link-state routing algorithm is run at each spine node to produce current routes to every destination.
Another related approach is clustered spine routing (CSR), which is disclosed by Das et al. in “Routing in Ad-Hoc Networks using a Spine,”
IEEE Int. Conf. On Computer Commun. and Networks
(IC3N '97), 1997. this approach is intended to extend the applicability of spine routing to larger network sizes by grouping the nodes in clusters and adding a second hierarchical level to the OSR approach. Yet another approach is known as partial knowledge spine routing (PSR) which is disclosed by Sivakumar et al. in “The Clade Vertebrata: Spines and Routing in Ad-Hoc Networks,”
IEEE Symposium On Computer and Commun
., 1998.
One common characteristic of each of the above prior art cluster/spine approaches is that they each rely on proactive routing. One potential drawback of proactive routing is that it typically requires a significant amount of routing overhead to maintain optimal routes to all destinations at all times. This problem may become particularly acute when applied to ad-hoc networks including a very large number of nodes.
SUMMARY OF THE INVENTION
In view of the foregoing background, it is therefore an object of the present invention to provide a method for sending data in ad-hoc networks that is particularly well suited for networks having a relatively large number of nodes and which provides route error recovery.
This and other objects, features, and advantages in accordance with the present invention are provided by a method for sending data in a mobile ad-hoc network including a plurality of nodes grouped into clusters of nodes and a plurality of wireless links connecting the plurality of nodes, where each cluster has a designated cluster leader node. The method may include sending a cluster-level route request from a source node of a source cluster to a cluster leader node of the source cluster, and determining a cluster-level route through the source cluster and a destination cluster including a destination node responsive to the cluster-level route request and using a plurality of the cluster leader nodes. Furthermore, the method may also include determining node-level routes through each cluster along the cluster-level route to a cluster target node in a next cluster along the cluster-level route, and transferring the data from the source node to the destination node using the node-level routes.
Moreover, if a node-level route failure occurs along a node-level route, a new node-level route may advantageously be determined therefor. Similarly, if a cluster-level route failure occurs between adjacent clusters along the cluster-level route, a cluster-level route error message may be sent to the source node, and new cluster-level and node-level routes determined responsive thereto, at which the data may be transferred using the new node-level routes. More particularly, the node-level routes may be determined using the dynamic source routing (DSR) protocol or the ad-hoc on-demand vector routing (AODV) protocol, for example.
Additionally, the method may also include sending the cluster-level route error message from a cluster target node immediately upstream from where the cluster-level failure occurred to its respective cluster leader node. Further, the cluster-level route error message may then be sent to each cluster leader node upstream therefrom. Determining the cluster-level route may also include storing, at each cluster leader node except the destination cluster leader node, an address of a next cluster leader node along the cluster route. This will be the case when AODV is used as the base routing protocol, for example. The method may therefore also advantageously include deleting the next cluster leader node address from each cluster leader node upstream from where the cluster-level failure occurred. That is, the location of each “hop” along the cluster-level route is deleted from each cluster leader node since the cluster-level route is no longer valid.
Determining the cluster-level route may include determining designated communication links between the cluster leader nodes, and sending a cluster leader node route request from the cluster leader node of the source cluster to the remaining cluster leaders via the designated communication links. Further, a cluster leader node route reply may be returned from the cluster leader node of the destination cluster to the cluster leader node of the source cluster along a delivery route of the cluster leader node route request.
More specifically, at least one of the designated communications links may include a node that is not a cluster leader node. Further, each cluster leader node may store addresses of adjacent cluster leader nodes, and sending the cluster leader node route request may include sending the cluster leader node route request from each cluster leader node to its adjacent cluster leader nodes. The adjacent cluster leader nodes may also be periodically polled to maintain current addresses therefor. Also, the delivery route may have a least number of cluster leader nodes between the cluster leader nodes of t
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Harris Corporation
Marcelo Melvin
LandOfFree
Hierarchical modile ad-hoc network and methods for route... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical modile ad-hoc network and methods for route..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical modile ad-hoc network and methods for route... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3047068