Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Routing data updating
Reexamination Certificate
2002-04-29
2004-04-06
Luu, Le Hien (Department: 2141)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Routing data updating
C709S239000, C709S238000, C370S351000
Reexamination Certificate
active
06718394
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.
This and other objects, features, and advantages in accordance with the present invention are provided by a method for sending data in a wireless 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 between 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. Further, a node-level route may be determined from the source node to the destination node along the cluster-level route, and each node along the node-level route may store an address of a next node along the node-level route. Additionally, the data may be transferred from the source node to the destination node via the node-level route based upon the addresses of each next node along the node-level route.
More particularly, the method may further include generating a mission data packet comprising an address of the destination node, and transferring may further include transferring the data also based upon the mission data packet. Also, a respective cluster target node may be determined for each cluster along the cluster-level route. Thus, determining the node-level route may include determining a node-level route from the source node to a cluster target node for a next adjacent cluster along the cluster-level route, and determining a node-level route from each cluster target node to a next cluster target node along the cluster-level route.
In addition, each cluster leader node along the cluster-level route may store an address of a next cluster along the cluster-level route. Each cluster target node may also poll its respective cluster leader node for the next cluster address, and each cluster target node may determine the next cluster target node based upon the next cluster address.
The address of the destination node may be stored along with an address of its respective cluster at the cluster leader node for the source cluster. The method may also include indexing the address of the next node along the node-level route stored at the source node by an address of the destination node.
In addition, a plurality of the cluster leader nodes comprising at least the source cluster leader node and the destination cluster leader node may be grouped into a leader node cluster, and a high-level route from the cluster leader node of the source cluster to the cluster leader node of the destination cluster may be determined within the leader node cluster. Further, the cluster-level route may include at least the clusters having respective cluster leader nodes along the high-level route.
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 particularly, 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 identities of adjacent cluster leader nodes, and sending the cluster leader node route request may include sending the cluster leader node route request fro
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Harris Corporation
Luu Le Hien
LandOfFree
Hierarchical mobile ad-hoc network and methods for... 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 mobile ad-hoc network and methods for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical mobile ad-hoc network and methods for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3245888