Method and system for improving a wireless communication route

A system and method for improving a current wireless communication route, between a source node and a destination node in an on-demand wireless communication network, enables the current communication route to be improved even when the current route has not failed. The method includes analyzing at a local node a packet transmission from the source node, the packet transmission comprising a current route metric (step 705). The local node then determines that it can provide an improved wireless communication route, between the source node and the destination node, having a better route metric than the current route metric (step 710). A route improvement message is then transmitted from the local node to the source node (step 740).

FIELD OF THE INVENTION

The present invention relates generally to wireless networks, and in particular to improving routes between mobile nodes in an on-demand wireless network.

BACKGROUND

On-demand routing algorithms enable dynamic, self-starting, multihop routing between participating mobile nodes in ad hoc wireless communication networks. Various methods exist for determining a preferred on-demand route through a network. For example an ad hoc, on-demand distance vector (AODV) routing protocol allows mobile nodes to obtain routes quickly for new destinations, and does not require nodes to maintain routes to inactive destinations. Thus AODV protocols allow mobile nodes to respond to route failures and changes in network topology in a timely manner.

However, after a route is established in an on-demand routing protocol, mobile nodes generally continue using the established route until there is a need, based for example on a failure of the established route, to discover an alternative route. Therefore, even if an improved route becomes available, due for example to a change in network topology, change in link condition, or movement of one or more mobile nodes, the mobile nodes along the established route will nonetheless continue using the established route. Hence, improved routes that may become available are not utilized.

One known method for addressing the above problem is to periodically transmit route request (RREQ) packets, which explores all possible routing options in a wireless neighborhood. However, because the RREQ packets are transmitted as a broadcast, such RREQ packets can place a large overhead on wireless bandwidth. Broadcasting of RREQ packets also works against a basic principle of on-demand routing protocols, which is to conserve bandwidth by avoiding unnecessary packet transmissions.

Other known methods of route improvement in on-demand routing protocols are based on “nexthops,” which endeavor to optimize a route by minimizing a number of “hops” between nodes. These methods however risk the formation of loops. Additionally, in varying link conditions, such methods can be prone to generating RREQ packets excessively and when RREQ packets are not needed, thus unnecessarily increasing overhead on a wireless bandwidth. Furthermore, such methods risk adopting a route that is improved based on one criteria, such as node minimization, but which is inferior based on another criteria, such as route stability.

DETAILED DESCRIPTION

Referring toFIG. 1, a schematic diagram illustrates an ad hoc, on-demand wireless communication network100comprising a plurality of mobile nodes110-naccording to an embodiment of the present invention. The network100can be, for example, a wireless Mobile Ad Hoc Network (MANET), and the nodes110-ncan be associated with devices such as mobile phones or handheld radios. Also, fixed nodes110-ncan be associated with devices such as routers, as for example a router installed in a wireless local area network (WLAN) access point (AP) on a light pole in a city. As described in more detail below, data are routed through the network100using various routes that are determined dynamically.

Each route line120extending from a node110-nto one or more other nodes110-nrepresents a functioning wireless communication interface operatively connecting two nodes110-ntogether. The interfaces may conform, for example, to a wireless standard such as IEEE 802.11.

Consider, according to the present embodiment, that the “A” node110-1is a source node, which is an originator of a communication, and the “C” node110-3is a destination node, which is the destination of the communication. The lines120extending between the “A” node110-1and the “B” node110-2, and between the “B” node110-2and the “C” node110-3, together indicate a current wireless communication route between mobile nodes “A” and “C” via “B”. The “B” node110-2thus acts as an intermediate node110-nin a “two-hop” communication route.

Further consider that the “C” node110-3is within radio communication range of both the “A” node110-1and the “B” node110-2. That means that each time the “A” node110-1transmits a packet destined for the “C” node110-3, the “C” node110-3will receive the packet twice (i.e., once when the packet is transmitted from “A” to “B”, and a second time when the packet is transmitted from “B” to “C”). Thus the “C” node110-3is in a position to monitor two independent routes between the “A” node110-1and the “C” node110-3.

According to an embodiment of the present invention, any nodes110-nthat are within radio range of both a source node110-1and a destination node110-3are referred to as local nodes, and can assist in determining an improved route between the source node110-1and the destination node110-3. Note that inFIG. 1, the “C” node110-3acts as both a local node110-nand as a destination node110-3. Such a situation occurs whenever a destination node110-3is within radio range of a source node110-1, but is not currently receiving communications directly from the source node110-1.

For example, the dashed line130extending between the “A” node110-1and the “C” node110-3indicates an alternative, direct wireless communication route between the “A” node110-1and the “C” node110-3. If the “C” node110-3determines that the direct route line130represents an improved route over the indirect route lines120, the “C” node110-3transmits a route improvement message to the “A” node110-1. After receiving the route improvement message, the “A” node110-1can decide to abandon the current indirect route along lines120, and use the direct route line130when it sends additional packets to the “C” node110-3.

In a real-world ad hoc, on-demand wireless network environment, possibly involving many more mobile nodes110-nthan the three nodes110-nshown inFIG. 1, after a route is established the mobile nodes110-ncontinue using the established route until there is a need to discover an alternative route—even if an improved route is immediately available. The present invention provides a system and method for improving a current wireless communication route between mobile nodes110-nby efficiently comparing route metrics of at least one alternative route with a route metric of the current route. According to different embodiments of the present invention, various parameters can be used to define a route metric including but not limited to throughput, delay, jitter, signal strength, packet completion rate, or combinations thereof.

For example, one parameter that can be used to define a route metric is a Packet Completion Rate (PCR). InFIG. 1the numbers next to each indirect route line120and next to the direct route line130represent a respective PCR for each route. For example, the number 1.0 next to the lines120indicates that 100% of packets are successfully transmitted from the “A” node110-1to the “B” node110-2and then to the “C” node110-3. The PCR for the route represented by line130is shown as 0.8, indicating that 80% of packets are successfully transmitted between the “A” node110-1and the “C” node110-3. Thus if a route metric is based solely on PCR, the indirect route lines120will comprise a better route metric than the direct route line130.

Another parameter that can be used to define a route metric is an Expected Transmission Time (ETT), which is an estimate of the time required to transmit a packet between two nodes110-n. ETT is a function of PCR, delay, and other system parameters, and can be considered in some embodiments of the present invention as a highly accurate way of estimating the quality of a communication link.

Referring toFIG. 2, a schematic diagram illustrates components of a typical wireless mobile node110-noperating within a network100, according to an embodiment of the present invention. The node110-ncan be any type of electronic communication apparatus having wireless communication capability, such as a mobile telephone, personal digital assistant, or wireless router. The node110-ncan include various elements such as the following: a user interface200such as a keypad, display or touch sensor; a processor210to control operating features of the node110-n; a memory220to store, for example, data and computer program code components; and an ad hoc wireless networking communication interface230, which conforms to a wireless standard such as IEEE 802.11 and enables the node110-nto communicate wirelessly with other nodes110-n.

The user interface200, memory220and communication interface230are each operatively connected to the processor210. Those skilled in the art will appreciate that the memory220may comprise various types of memory such as a random access memory (e.g., static random access memory (SRAM)), read only memory (e.g., programmable read only memory (PROM)), electrically erasable programmable read only memory (EPROM), or hybrid memory (e.g., FLASH) as is well known in the art. The processor210then accesses a computer useable medium in the memory220, which medium includes computer readable program code components configured to cause the node110-nto execute the functions of the present invention.

Referring toFIG. 3, a schematic diagram illustrates a modified data packet300, according to an embodiment of the present invention. The data packet300comprises, in a header, a source field310, a destination field320, a time-to-live (TTL) field330and a route metric field340. Following the header is a payload field350. The route metric field340comprises data concerning the quality of a route through which a packet300travels. The route metric field340thus can comprise PCR data, ETT data or other data related to a route. Further, according to an embodiment of the present invention, the route metric field340is updated at each intermediate hop along a route to indicate a cumulative route metric.

Referring again toFIG. 1, consider a modified data packet300according to the present invention that is destined for the “C” node110-3and routed from the “A” node110-1through the intermediate “B” node110-2. Consider further that the route metric field340in the packet300comprises PCR data. As described above, the route metric field340that is defined for the route between the “A” node110-1and “B” node110-2thus will be updated during the hop from the “B” node110-2to the “C” node110-3. So, for example, here a PCR data component in the route metric field340in a packet300received at the “C” node110-3, equals 1.0 because the PCR for both hops along the route equals 100%.

As another example, consider that the route metric field340in the packet300comprises ETT data. Again, as described above, the route metric field340that is defined for the route between the “A” node110-1and “B” node110-2will be updated during the hop from the “B” node110-2to the “C” node110-3. An ETT data component in the route metric field340in a packet300received at the “C” node110-3, thus comprises the total estimated transmission time between the “A” node110-1and the “C” node110-3.

If a local node110-ndetermines that it can provide an improved route between a source node110-1and destination node110-3, the local node110-ntransmits a route improvement message to the source node110-1. The route improvement message indicates that the local node110-ncan provide a wireless communication route having a higher route metric than the route metric of the current route.

For example, a route improvement message can comprise a request for a source node110-1to transmit a route request (RREQ) packet. Based on received responses to an RREQ, the source node110-1will then re-determine an optimized route to a destination node110-3. According to an embodiment of the present invention, route improvement messages are not transmitted every time a local node110-ndetermines that it can provide an improved route to a destination node110-3. Rather, a route improvement message is transmitted only when a local node110-ndetermines that it can provide an improved route having a route metric that exceeds a route metric of a current route.

According to another embodiment of the present invention, a route improvement message is transmitted only when a local node110-ndetermines that it can provide an improved route having a route metric that exceeds a route metric of a current route by a predetermined threshold. For example, a predetermined threshold can be set at 10%, so that a route metric of an improved route must exceed a route metric of a current route by 10% or more before a route improvement message is transmitted. It will be appreciated by those skilled in the art that such a threshold can be set at various levels depending on the needs of a particular network to minimize bandwidth use.

According to a further embodiment of the present invention, transmission of a route improvement message from a local node110-nto a source node110-1is delayed for a predetermined time interval. Such a predetermined time interval is used to monitor the stability of an improved route. That ensures that route improvement messages are not sent concerning improved but unstable routes, which may temporarily comprise a high route metric but which rapidly degrade to a low route metric. For example, during a predetermined time interval a route metric should not vary significantly due to node mobility or changing link conditions. If a stability of an improved wireless communication route falls below a predetermined threshold during a predetermined time interval, a route improvement message is not sent from a local node110-nto a source node110-1.

Further, transmission of a route improvement message from a local node110-nto a source node110-1can be delayed for a random time interval, such as 0 or twice the Round Trip Time (RTT) between the source node110-1and the destination node110-3. That enables other local nodes110-n, which also may identify an improved route over a current route, to send alternative route improvement messages. For example, if a route improvement message from a second local node110-nis received by a first local node110-nduring a random time interval generated at the first local node110-n, where both the first and second local nodes110-nhave identified an improved route concerning an identical current route, then a route improvement message from the first local node110-nis suppressed or cancelled and is not sent to the source node110-1.

Referring toFIG. 4, a schematic diagram illustrates a wireless network400comprising a “multi-hop” communication route between a source node110-1and a destination node110-3, according to an embodiment of the present invention. In this example, a current wireless communication route between the source “A” node110-1and the destination “C” node110-3is via local “B” node110-2and via local “D” node110-4. Thus, in this embodiment there are three “hops” in the current wireless communication route. The dashed lines405-1,405-2,405-4indicate an outer limit of the direct radio range of the respective nodes110-1,110-2,110-4. A local “E” node110-5is further shown located inside the radio range of all of the nodes110-1,110-2,110-4. Further, consider that the “E” node110-5is also in direct radio range of the “C” node110-3. Here, when a modified packet300is sent from the “A” node110-1to the “C” node110-3using the current route, the “E” node110-5receives the same packet three times in its routing layer (i.e., once from the “A” node110-1, once from the “B” node110-2and once from the “D” node110-4).

In the example shown inFIG. 4, the local “E” node110-5determines according to the teachings of the present invention whether it can provide an improved route between the “A” node110-1and the “C” node110-3. For example, consider that the numbers shown between each of the nodes110-nrepresent an ETT for each “hop”, respectively, between the nodes110-n. Because route metrics are cumulative across hops, an ETT data component of a route metric for the total route from the “A” node110-1to the “B” node110-2to the “D” node110-4and to the “C” node110-3equals 4+4+5=13. However, an ETT data component of a route metric for a potential improved route from the “A” node110-1to the “E” node110-5to the “C” node110-3equals 5+5=10. Because lower transmission times are generally desirable, the ETT data components indicate that the route through the “E” node110-5may present an improved route over the current route.

Referring toFIG. 5, a schematic diagram illustrates another wireless network500comprising a “multi-hop” communication route between a source node110-1and a destination node110-3, according to an embodiment of the present invention. The embodiment here is similar to that described in reference toFIG. 4, except that the local node110-5is not within the transmission range of local nodes110-2,110-4. Therefore, during transmission of a modified packet300from “A” node110-1to “B” node110-2to “D” node110-4to “C” node110-3, the local “E” node110-5receives the packet transmission only once—i.e., when the packet300is sent from the source “A” node110-1. In this example, the “E” node110-5cannot determine whether it can provide an improved route based on data from the “B” node110-2or “D” node110-4. However, when a packet300is transmitted back to the “A” node110-1from the “C” node110-3, the “E” node110-5will be able to determine whether it can provide an improved route.

Referring toFIG. 6, a time line600illustrates a further method for minimizing bandwidth, processor resources, and network traffic congestion, according to an embodiment of the present invention. The analysis at a local node110-nconcerning whether an improved route exists in a wireless network, according to the teachings of the present invention, not need to occur continuously. Such analysis, which generally can be referred to as “snooping”, can proceed efficiently when it is programmed to occur only during specific periods. For example, a route optimization interval605is an interval during which a node110-ngenerally snoops a MAC layer packet to see if the node110-ncan provide a more optimized route. A route optimization period610then can be defined as a component of a route optimization interval605. Local nodes110-nthen are programmed to perform snooping only during route optimization periods610, thus minimizing bandwidth, processor resources, and network congestion during the remaining part of a route optimization interval605.

Referring toFIG. 7, a general flow diagram illustrates a method700for improving a current wireless communication route between a source node110-1and a destination node110-3in an on-demand wireless communication network, according to an embodiment of the present invention. First, at step705, a packet transmission from a source node110-1is analyzed at a local node110-n. At step710, the local node110-ndetermines whether it can provide an improved wireless communication route between the source node110-1and the destination node110-3, where the improved route has a better route metric than the current route metric. If at step710it is determined that an improved route can be provided, at step715transmission of a route improvement message from the local node110-nto the source node110-1is delayed for a predetermined time interval, in order to monitor the stability of the improved route. At step720, it is determined whether the stability of the improved route falls, during the predetermined time interval described at step715, below a predetermined threshold. If so, at step725the route improvement message is cancelled. The method700then loops back to step705where another packet transmission is analyzed.

However, if at step720the stability of the improved route does not fall below the predetermined threshold during the predetermined time interval, the method700continues at step730where transmission of the route improvement message is delayed by a random time interval. At step735it is determined whether an alternative route improvement message, concerning the same current route, is received from another local node110-n. If so, at step725the route improvement message is cancelled. If no alternative route improvement messages are received at step735, then at step740the route improvement message is transmitted to the source node110-1.

Advantages of the present invention thus include the ability to switch a current communication route in an on-demand wireless communication network to an improved route, even when the current route has not failed. An improved route can be determined by local nodes110-nin a network irrespective of whether the local nodes110-nare in a current communication route. Comparisons of improved routes and current routes can be made based on various factors such as Packet Completion Rates (PCRs) or Expected Transmission Times (ETTs), and whether an improved route is stable. Further, the present invention enables route improvement messages to be generated only when needed, thus reducing bandwidth overhead and conserving network resources.