Scalable unidirectional routing with zone routing protocol extensions for mobile AD-HOC networks

An apparatus for routing data in wireless ad-hoc networks comprising:

• a proactive element, configured to route messages utilizing an intra zone routing protocol;
• and
• a reactive element, configured to route messages utilizing a inter zone routing protocol;
• and
• a bordercast tree element, configured to bordercast to a plurality of border nodes;
• and
• at least one query packet memory element comprising data, wherein nodes receiving one or more query packets are configured to provide at least one query response or discard the query packet;
• wherein the apparatus includes:
• i. a first means for initiating a route query from a first node or a source node and wherein the route query concerns a route to a destination node;
• ii. a central means determines if there is a path to a destination node in an outbound tree, as computed by the proactive element, and, if such a path is found, that path is the desired path;
• and the apparatus transmits its message;
• otherwise;
• iii. the source node checks if its bordercast tree is empty:
• a. if the bordercast tree is empty go to step viii;
• b. if the bordercast tree is not empty go to step iv;
• iv. the bordercast tree is stored in the query packet, and is forwarded along the bordercast tree, one or more intermediate nodes of the bordercast tree (non-border nodes), forward the query packet until it reaches a border node, wherein a plurality of processing steps occur culminating in the sending of a bordercast:
• a. after sending the bordercast, there is a pause for a predetermined period of time equal to ENHANCEMENT_NTERVAL, during which the source node awaits either a query response or one or more enhancement messages;
• v. if a query response to the route query is received, then the route query step is termed complete and the computed route is returned to the first node;
• vi. if a query response is not received, then the source node checks if an enhancement message has been received, the ENHANCEMENT_INTERVAL having passed since the initiation of the bordercast;
• if one or more query enhancement messages were received during the ENHANCEMENT_INTERVAL, then one or more alternate destination nodes suggested in the query enhancement message, or messages, are utilized to create an enhanced route query with an alternative set of destinations, wherein other nodes have reported that the alternative destination nodes have routes to the destination node;
• the new enhanced route query is processed like the original route query;
• by returning to step ii;
• vii. if the bordercasting did not result in any enhancement of the route query or in a route, the bordercast tree is incapable of reaching nodes that can enhance the query (assuming no message losses);
• this state is also reached from step ii, when the bordercast tree is empty;
• in this situation a two-way tree is used to send a request to enhance the query and the source node and the border nodes forward this Query Enhancement Request using the two-way tree just as they would forward a regular query, except that the two-way tree is used for bordercasting, instead of the bordercast tree;
• the objective here is to try to discover nodes, which know of paths to the destination node;
• viii. after waiting for ENHANCEMENT_INTERVAL, the source node checks to see if any responses to the query enhancement request using the two way tree exist;
• if one or more query enhancement responses are received during the ENHANCEMENT_INTERVAL, the resulting one or more destinations suggested in the query enhancement response can be queried for routes to the desired destination, if there is a path to a desired destination node in an outbound tree as computed by the proactive component then that path is the desired path and the protocol terminates;
• ix. if there are any responses to the query enhancement request but there is not a path to the desired destination in an outbound tree as computed by the proactive component then go to step iii;
• x. if no enhancement message was received then the destination is assumed to be unreachable and the protocol terminates.