Untitled record

p00001System and method to achieve continuous connectivity with an access point or entry in a wireless network following a demand routing protocol

p00002Background of the invention

p00003Field of the invention:

p00004[0001] The present invention relates to a system and method for allowing an ad-hoc communication network to maintain connectivity within mobile nodes and fixed nodes in the network effectively and efficiently with minimal overload.

p00005More particularly, the present invention relates to a system and method for allowing an ad-hoc communication network to maintain connectivity between intelligent network access points and other nodes (for example, wireless routers and subscriber devices that may be landline or mobile) on the network while using a routing on demand protocol. The present invention also relates to a system and method for achieving smooth deliveries of mobile nodes between fixed nodes in an ad-hoc communication network using a distance vector routing algorithm and enhanced unicast messages. In addition, the present invention relates to a system and method for modifying the ad hoc demand remote vector routing (AODV) protocol to facilitate smooth delivery of subscriber devices in a communication network ad-hoc while eliminating unidirectional links between nodes in the network. The present invention claims the benefit according to USC. 119 (e) of the serial no. of Provisional US Patent Application 60 / 439,448, 60 / 439,449 and 60 / 439,455 of Avinash Joshi, each filed on January 13, 2003, and U. no. Series of Provisional US Patent Application 60 / 476,237 of Avinash Joshi, filed June 6, 2003.

p00006Description of related techniques:

p00007[0002] Wireless communication networks, such as mobile wireless telephone networks, have gained increasing dominance over the past decade. These wireless communications networks are commonly referred to as "cellular networks" because the network infrastructure is arranged to divide the service area into a plurality of regions called "cells". A cellular terrestrial network includes a plurality of interconnected base stations, or base nodes, which are geographically distributed at designated locations throughout the service area. Each base node includes one or more transmitters that can transmit and receive electromagnetic signals, such as radio frequency (RF) communications signals, to and from mobile user nodes, such as cordless telephones, located in the coverage area. Communication signals include, for example, voice data that has been modulated according to a desired modulation technique and transmitted as data packets. As one skilled in the art can appreciate, network nodes transmit and receive data packet communications in a multiplexed format, such as time division multiple access format (TDMA), multiple access format. by code division (CDMA), or frequency division multiple access format (FDMA), which allows a single transceiver in the base node to communicate simultaneously with several mobile nodes in its coverage area.

p00008[0003] In recent years, a type of mobile communications network known as an "ad-hoc" network has been developed. In this type of network, each mobile node is able to function as a base station or router for the other mobile nodes, thus eliminating the need for a fixed base station infrastructure. Details of an ad-hoc network are set forth in US Patent No. 5,943,322 to Major.

p00009[0004] More sophisticated ad-hoc networks are also being developed which, in addition to allowing mobile nodes to communicate with each other as in a conventional ad-hoc network, also allow mobile nodes to access a fixed network and thus communicate with others mobile nodes, such as those in the public switched telephone network (PSTN), and in other networks such as the Internet. Details of these advanced types of ad-hoc networks are described in U.S. Patent No. 7,072,650 (Application Serial No. 09 / 897,790) entitled "Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks & quot ;, granted on July 4, 2006, in U.S. Patent No. 6,807,165 (Application Serial No. 09 / 815,157) entitled & quot; Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel & quot ;, issued October 19, 2004 and in U.S. Patent No. 6,873,839 (Application Serial No. 09 / 815,164) entitled "Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System", issued on March 29, 2005. A mobile workgroup system based on which allows a selected set of users of two or more private virtual mobile networks to form an extra network workgroup in a secure manner is described in US2002 / 0133534. A new protocol that is optimized to support local mobility but that effectively interferes with existing mobile guest protocols to provide wide-area mobility support is described on pages 50-65 of XP00082387 titled & quot; Cellular IP: A new approach to internet host mobility & quot ;. A new approach to internet host mobility & quot ;.

p00010[0005] As one skilled in the art can appreciate, since certain nodes of the ad-hoc network are mobile, it is necessary for the network to maintain connectivity with those nodes. Therefore, it needs to exist for improved techniques to allow an ad-hoc network to maintain connectivity with the mobile nodes in the network in an efficient and effective manner with minimal overhead. Similarly, most traffic flows through the access point (AP) in such a network and, therefore, there is a need for all nodes to maintain routes with the access point (AP) all the time in An efficient and effective way with minimal overload.

p00011Summary of the Invention

p00012[0006] An object of the present invention is to provide a system and method to allow an ad-hoc communication network to maintain connectivity in the mobile nodes and fixed nodes in the network in an efficient and effective manner with minimal overload.

p00013[0007] These and other objects are substantially achieved by a system according to claim 12 and method according to claim 1 to allow an ad-hoc communication network to maintain connectivity between intelligent network access points and other nodes (mobile nodes and fixed nodes) in the network using a demand routing protocol.

p00014Brief description of the drawings

p00015[0008] These and other objects, the advantages and new features of the invention will be more readily appreciated from the following detailed description when read in conjunction with the accompanying drawings, in which:

p00016[0009] Figure 1 is a block diagram of an example switched packet wireless communications ad-hoc network that includes a plurality of nodes according to an embodiment of the present invention;

p00017[0010] Figure 2 is a block diagram illustrating an example of a mobile node employed in the network shown in Figure 1;

p00018[0011] Figure 3 is a conceptual block diagram of an example of the relationship between wireless routers and network access points shown in Figure 1;

p00019[0012] Figure 4 is a conceptual block diagram of an example of the relationship between a device of the subscriber in motion with respect to the fixed wireless routers of the network shown in Figure 1;

p00020[0013] Figure 5 is a conceptual block diagram of an example of the relationship between a moving subscriber's device with respect to the fixed wireless routers and network access points shown in Figure 1 and

p00021[0014] Figure 6 is another conceptual block diagram of an example of the relationship between a subscriber's device, wireless routers and a network access point shown in Figure 1.

p00022Detailed description of the preferred embodiments

p00023[0015] Figure 1 is a block diagram illustrating an example of an ad-hoc wireless packet-switched communication network 100 using an embodiment of the present invention. Specifically, the network 100 includes a plurality of wireless mobile user terminals 102-1 to 102-n (generally referred to as nodes 102, mobile nodes 102 or subscriber (SD) devices, and may include, but is not required to, a fixed network 104 with a plurality of intelligent access points 106-1,106-2, ... 106-n (generally referred to as nodes 106, access points 106 or IAP), to supply nodes 102 with access to the fixed network 104. The fixed network 104 may include, for example, a central local access network (LAN), and a plurality of servers and incoming routers to provide network nodes with access to other networks, such as other ad-hoc networks, the network Public Switched Telephone (PSTN) and Internet. The network 100 may also include a plurality of fixed routers 107-1 to 107-n (generally referred to as nodes 107, fixed routers 107 or wireless routers (WR)) for routing data packets between other nodes 102,106 or 107. It is noted that , for the purposes of this discussion, the nodes mentioned above may be collectively referred to as "nodes 102,106 and 107", or simply "nodes".

p00024[0016] As one skilled in the art can appreciate, nodes 102, 106 and 107 are able to communicate with each other directly, or through one or more different nodes 102,106 or 107 operating as a router or routers for packets that are sent between nodes, as described in U.S. Patent No.

p000255,943,322 to Major, and in U.S. Patent Nos. 7,072,650, 6,807,165 and 6,873,839 (serial number of application 09 / 897,790, 09 / 815,157 and 09 / 815,164), mentioned above.

p00026[0017] As shown in Figure 2, each node 102, 106 and 107 includes a transceiver 108 that is coupled to an antenna 110 and can receive and transmit signals, such as packet signals, to and from node 102,106 or 107, under the control of a controller 112. The packet data signals may include, for example, voice, multimedia data or information, and packet control signals, including node update information.

p00027[0018] Each node 102,106 and 107 also includes a memory 114, such as a random access memory (RAM), which can store, among other things, routing information belonging to itself and other nodes in the network 100. Nodes 102,106 and 107 participate in the routing protocol that can be on demand or proactive and, therefore, can send routing messages that can be Route request, Route response, Route error or Routing announcement whenever there is a change in the network topology or periodically.

p00028[0019] As also shown in Figure 2, certain nodes, especially mobile nodes 102, may include a guest 116 that may consist of any number of devices, such as a laptop terminal, a mobile phone unit, a unit of mobile data or any other suitable device. Each node 102,106 and 107 also includes the appropriate hardware and software to execute the Internet Protocol (IP) and the Address Resolution Protocol (ARP), whose objectives can be easily appreciated by one skilled in the art. The appropriate hardware and software to execute the transmission control protocol (TCP) and user datagram protocol (UDP) may also be included.

p00029[0020] As can be seen from the foregoing, in the network 100, an IAP 106 is the connection point of the wireless part and the wired Internet. If a Subscriber Device (SD) 102 is not in the range of direct communication with an IAP 106, the DS 102 depends on other devices to reach the IAP 106. These devices may be other SD 102 or Wireless Routers (WR) 107 that are specifically deployed to provide coverage to these SDs.

p00030[0021] In an ad-hoc network such as network 100, all nodes need to maintain continuous connectivity with the access point (or IAP) since most of the traffic is to and from an IAP. This applies to field deployment and deployment in an office environment. Continuous connectivity is also necessary to create a tunnel between the Dynamic Host Configuration Protocol (DHCP) and the IP address of the address resolution protocol (ARP) to the IAP. If an on-demand protocol, such as the ad hoc routing protocol of the distance vector (AODV), is used in an ad-hoc network, none of the routes is proactively maintained. Accordingly, the embodiments of the present invention described herein provide routes to IAPs that can be maintained at all times with minimal sovereignty. This technique can also be used as an IAP association protocol. The technique has been called the proactive IAP locator protocol (PIL).

p00031[0022] As one skilled in the art can appreciate, a routing on demand protocol (eg, AODV) creates routes only when the source node wishes. AODV is described in a publication by Charles E. Perkins, Elizabeth M. Belding-Royer and Samir Das entitled "Ad Hoc On Demand Distance Vector (AODV) Routing" RFC 3561, July 2003 ..

p00032[0023] Therefore, when a node requires a route to a destination, the node starts a route discovery process within network 100. The commonly used method, called an Expansive Ring Search, can increase the average latency of route discovery, since multiple discovery attempts and interruptions may be necessary before a path to the target node is found, high latency will require that the source node stores the packets in buffer memory, which can be difficult for limited nodes of memory in such a kind of network resulting in packet loss. In addition, this elongated route discovery process also increases the overhead since each discovery can lead to flooding in the network. Since most of the traffic in this kind of network flows between IAP and other nodes, such as WR and SD, these floods can be avoided if the nodes proactively maintain routes to the IAP. This will also prevent latency and intermediate storage of packets that participate in the detection of routes to an IAP. AODV also assumes two-way links between nodes, which can lead to incorrect routes. The technique according to the embodiments of the invention described herein avoids unidirectional links while detecting node routes to the IAP and vice versa.

p00033[0024] An example of the process will now be described with reference to Figure 3. In this example, it is assumed that all nodes follow the AODV routing protocol with modifications in accordance with the embodiments of the present invention described herein. .

p00034All nodes periodically transmit a packet called IAP Ads (IA). Instead of an AI package, nodes can also use a "Greeting Message" which is generally sent by all nodes in such a network to maintain connectivity as described, for example, in a la. Patent Application Publication No. US20040258040A1 entitled "System and Method to Maximize Channel Utilization in a Multi-Channel Wireless Communication Network", published December 23, 2004.

p00035[0025] The contents of the IA package may be any combination of the following fields:

<dl><dt>• </dt><dd>Type of node: this will let other nodes know the type of device that can help them decide if this node should be used to route packets or not. </dd></dl>

This field can also help decide routing metrics as described in U.S. Provisional Patent No. 7,280,483 (application serial number 60 / 476,237 entitled "System And Method To Improve The Network Performance Of A Wireless" Communications Network By Finding An Optimal Route Between A Source And A Destination &amp; quot; granted on October 9, 2007.

<dl><dt>• </dt><dd>Number of jumps of the associated IAP. </dd></dl>

<dl><dt>• </dt><dd>Node address (IP or MAC address or both): This decision is based on whether the network uses Layer 2 routing or Layer 3 routing or a combination of both. </dd></dl>

<dl><dt>• </dt><dd>Associated IAP address (IP or MAC address or both): This decision is based on whether the network uses Layer 2 routing or Layer 3 routing or a combination of both. </dd></dl>

<dl><dt>• </dt><dd>Routing metric to the associated IAP: This field helps to decide one route against another as described, for example, in U.S. Patent No. 7,280,483 mentioned above, and in a U.S. Patent Application Publication US20020191573A1 by Eric A. Whitehill et al. titled &amp; quot; EMBEDDED ROUTING ALGORITHMS UNDER THE INTERNET PROTOCOL ROUTING LAYER OF A SOFTWARE ARCHITECTURE PROTOCOL STACK &amp; quot ;, published on December 19, 2002.</dd></dl>

<dl><dt>• </dt><dd>Another metric (for example some metric that represents the load on the IAP as the number of active users associated with the IAP or total bandwidth used by the users): this field can be used to balance load across multiple IAPs and achieve goals Quality of service (QoS) through multiple IAPs. </dd></dl>

<dl><dt>• </dt><dd>QoS metric: used for QoS routing. </dd></dl>

<dl><dt>• </dt><dd>Address of the node that is being used as the next leap towards the IAP: this field can be used to perform a technique of &amp; quot; Split Horizon &amp; quot; as performed by traditional distance vector protocols on the Internet as described below.</dd></dl>

<dl><dt>• </dt><dd>Transmission identity: a transmission identity similar to that used in the AODV route request (RREQ) process, which is useful in the detection of duplicate packets and the reduction of those duplicates. </dd></dl>

<dl><dt>• </dt><dd>It is possible that this transmission identity is not required if any sequence number is already part of the MAC header to discard duplicate packets. </dd></dl>

<dl><dt>• </dt><dd>Power level: this message can be sent to some fixed power that is known throughout the network, or the power used should be indicated in this field of the package. This will help the node receiving the packet to know the path loss between the transmitter and itself.</dd></dl>

<dl><dt>• </dt><dd>TTL: The packet can also have a TTL (lifetime) value set in network diameter, which depends on the size of the network 100 and the maximum possible number of hops between an IAP and a node associated with that IAP. The TTL value can then be deducted for each protocol interface layer (PIL) daemon when the packet propagates throughout the entire network 100, which can control the maximum number of possible hops between an IAP and any other node in the network.</dd></dl>

<dl><dt>• </dt><dd>A node can also send similar information about some other IAP / IAPs with which it is not associated. </dd></dl>

p00036The information can include all the metrics mentioned above.

p00037[0026] Referring to Figure 3, the process begins when an IAP transmits one of these packets (step 1) and the nodes in the network 100 that are one hop from the LAP receive it. Upon receiving such a message, the node stores the relevant information of the message in a table and compares that information with other entries if it has received the same message from other adjacent nodes. You can also simply discard the message if the next hop field in such a package has its own address. This is done to avoid loops and is similar to the well-known method "Divided Horizon" used in conjunction with the distance vector routing protocol. As one skilled in the art can appreciate, Split Horizon is a well known method in wired networks to solve the problem "count to infinity" in the distance vector protocol. Although the algorithm is not perfect and the problem of "counts to infinity" It can still exist if the number of nodes involved is greater than 3, it is still useful. The algorithm selectively excludes a destination from an ad to a neighbor, if the next jump to that destination is that neighbor. Since the AI ​​packet is a transmission packet and is sent instead of a unicast packet to an individual neighbor, the split horizon method cannot be used in its original form. Instead, the next hop used to reach the destination (an IAP in this example) can be announced in the package. Therefore, when a neighbor who receives the package sees his address in the next jump field, he ignores the announcement to avoid the problem "count to infinity". Thus, the split horizon method is used on the receiving side in a wireless network as opposed to being used on the transmission side as in a wired network.

p00038[0027] These nodes will now make a routing decision based on the number of factors, including, among others, the number of hops, the routing metric, the load balancing metric, the QoS metric, and so on. If a node decides to use the sender of this message as a next hop towards the IAP (the IAP itself in the present example), then it sends a Unicast Route Request (RREQ) for the IAP address to the node (the IAP in this case) that sent the AI ​​Package (step 2). Uniforming the RREQ will confirm that the link is not a unidirectional link, but a bidirectional link. If this type of Route Request fails, the node may blacklist the sender for some time and await AI messages from other nodes so that the node can jump through those other nodes to reach IAP. Nodes that are successful in the route discovery process receive a Response (RREP) from the IAP (step 3), and the IAP also creates a reverse route to the node that follows the normal AODV routing protocol.

p00039This reverse route can be used to send an IAP association / update message.

p00040[0028] After obtaining the route, the nodes retransmit the AI ​​message (step 4) after updating the relevant fields such as increasing the hop count, deducting the TTL, updating the different metrics, etc. The nodes that receive this AI will repeat the procedure by unicasting a RREQ (step 5) to the forwarding node and will receive a Unicast Response (RREP) from the forwarding node (step 6). It is noted that the G bit will be set in this unicast RREQ so that a free RREP (step 7) is also sent to the destination node (in this case, the IAP), so that the IAP also discovers a route to the nodes In this way, knowledge of the IAP (which is the default route in network 100) is proactively flooded over network 100. As indicated in step 8, the nodes that receive the relay AI then retransmit the AI ​​themselves ( step 8).

p00041[0029] According to the AODV protocol, after a node receives an RREQ and responds with a RREP routing response, the node discards the RREQ. If intermediate nodes, such as another SD or WR, answer each transmission of a given RREQ, the destination (for example; IAP) does not receive any copy of the RREQ. In this situation, the destination does not discover a route to the origin node. In an ad-hoc network, if WR always answers the RREQs, the amateur IAP will never discover any route to the SD. Currently, the AODV draft has a provision to let the destination know about this route. Specifically, the AODV draft states that, for the destination to know the routes to the origin node, the origin node SHOULD set the indicator "Free RREP". (`G ') in the RREQ. If, in response to a RREQ with an established 'G' indicator, an intermediate node returns an RREP, a free RREP must also be unicast to the destination node. Charles E. Perking, Elizabeth M. Belding-Royer and Samir Das. "Ad Hoc On Demand Distance Vector (AODV) Routing" mentioned above. This is the reason to support the G bit in the RREQ packet. However, instead of the G bit, a D bit (destination only indicator) can also be set so that no other than the destination (IAP in this case) responds to the message.

p00042[0030] A summary of the proactive IAP locator algorithms are as follows.

p00043[0031] A proactive IAP locator Daemon of an IAP obtains the IP or MAC address of the IAP and builds an IAP announcement packet that contains data relating to an IP / MAC address of the IAP. The associated IAP is set to 0 which is itself an IAP, the next jump to the IAP is also initialized to 0, the number of hops is set to 0, and appropriate metrics are set. If the network emission identifier that is initialized to 0 is used, and if the power used for the message is not set, the quantized power value is placed in the power level fields, and the TTL is set to the NETWORK_DIAMETER value. The proactive IAP locator Daemon then issues the IAP announcement packet on all interfaces. The proactive IAP locator Daemon then repeats the IAP announcement every second IAP_ADVERTISEMENT_INTERVAL, which is a configurable parameter, while increasing the network transmission identification.

p00044[0032] A proactive IAP locator Daemon of the WR and SD listens to an IAP announcement packet that contains data relating to an IP / MAC address of an IAP, a number of hops from the forwarding node, different metrics and so on , as mentioned earlier. If the node decides to use the sender as the next hop towards the IAP, the proactive IAP locator Daemon issues an RREQ for IAP with a G bit or D bit set to the forwarding node. If an RREP is received, the proactive IAP locator Daemon sends an IAP sociation / update message, increases the hop field, reduces the TTL, updates other fields and forwards to the broadcast address on all interfaces. However, if no RREP is received, the proactive IAP locator Daemon waits for another AI packet and may choose to blacklist the sender for some time. It should also be noted here that all nodes send the AI ​​or the greeting message periodically, which can be configured based on the type of device or other factors.

p00045[0033] As one skilled in the art can appreciate, the technique according to the embodiments of the present invention described above avoids the process of discovering high-latency-prone routes for a common destination, such as an IAP, at the same time. which minimizes the load on the network of 100. The technique can be used as an IAP association protocol, and load balancing can be achieved between different IAPs in the service of the network of 100.

p00046[0034] It should also be noted that unicast techniques similar to those mentioned above can be used to provide smooth delivery between mobile SD, such as those used in a moving vehicle. Figure 4 shows a typical scenario where WR1 and WR2 wireless routers are implemented to provide coverage on a highway. Circles represent the scope of these WRs, which means that any device, such as an SD, IAP or other WR can communicate with this WR if it is within this circle. As can be seen in the figure, there is a small area where these two circles overlap. In this area, the SD is in position to communicate with both wireless routers. It is advantageous for service providers to keep this area as small as possible since it reduces the number of WRs that must be implemented in a given area.

p00047[0035] When a mobile SD travels at road speed, it quickly crosses the coverage area of ​​the wireless routers WR1 and, therefore, passes through the overlapping area in a very short time. During this short period of time, the SD needs to change its routing table to reflect the fact that its best next leap to infrastructure has changed from WR1 to WR2. A similar process is known as &amp; quot; delivery &amp; quot; in cellular networks.

p00048[0036] In an ad hoc such as network 100 described above, most of the traffic flows between an IAP and the SD, so that in this small period of time, the IAP should also be informed about this change of connection point of SD to the network of 100. The embodiments of the invention described herein provide a system and method for achieving this and other objectives quickly and efficiently. Specifically, the embodiments provide a method that allows an SD to update its routing table to reflect the change in its connection point to the network 100 (i.e., its affiliation with a specific IAP) quickly and efficiently with the minimal loss of packages (called "soft delivery"). An example of a smooth delivery technique is described in U.S. Patent No. 7,072,323 to Robin U. Roberts and Charles R. Barker, Jr. titled &amp; quot; A System and Method for Performing Soft Handoff in a Wireless Data Network &amp; quot ;, granted on July 4, 2006. The embodiments also provide a method for other devices (in particular, IAP 106) to know this change in a Effective and fast way.

p00049[0037] In a distance vector approach, devices such as SD, IAP and WR learn route changes through periodic routing announcements. Therefore, it takes substantial time (depending on the periodic interval between these announcements) before an SD can know that it has moved away from one WR and is close to another WR. This time is even longer for an IAP that is usually several jumps away from where the routes have changed. This is illustrated in the following example, which will be examined in particular with reference to Figure 5.

p00050[0038] As shown in Figure 5, a mobile SD advances at high speed on a road where it has received coverage by wireless routers WR-3 to WR-6. In this example, the SD moves from left to right in Figure 5 as shown, which means that it is moving from the coverage area of ​​WR-3 to WR-4. It is assumed that the moment when the mobile (SD) enters the communication range of WR-4 is t, and that the periodic interval between two consecutive routing announcements is T (which is the same for SD and WR). It is also assumed that there is a three-way link mechanism that confirms that SD has in fact moved to the coverage range of WR-4 and there is a two-way link between them. This change may take up to 3T periods. After this link, WR will begin announcing the SD. The information is propagated as follows (in the worst case)

p00051Time (t + 3T): performs WR-4 confirming the presence of SD in its wireless range

p00052Time (t + 4T): WR-4 sends this information in its RA, WR-1 receives this information.

p00053Time (t + 5T): WR-1 sends this information in your RA, IAP now knows about this

p00054[0039] Thus it takes (jumps +2) times of periodic time of RA to inform IAP of the change of route of SD, where jumps = number of jumps between SD and IAP.

p00055[0040] If T is large, the IAP will take a long time to know the route change. Also, the time required to perform the three-way link can also be so great that the SD actually moves out of reach of the WRs participating in the link before it is completed. One way to address this issue is to have a lower T. However, having a lower T greatly increases network overload. The embodiments of the invention described herein thus provide a technique in which this linking operation can be performed more efficiently so that the information can be propagated to the IAP without significant overhead.

p00056[0041] To perform this technique, all infrastructure devices, that is, all IAPs and WRs, must periodically issue a neighbor announcement or greeting message. This message may have similar fields as in the AI ​​package mentioned above. A three-way link protocol can be used in this case to confirm the two-way link.

p00057[0042] All SDs actively monitor this neighbor announcement or greeting message and measure the signal strength of the signal. An SD can also make the three-way link to determine the strength of the received signal (RSSI) and the quality values ​​(PDSQ) of the signal at both ends after detection. As soon as the SD determines from the strength of the signal and / or these values ​​that it will lose connectivity with the old WR and should deliver, the SD unites an empty routing announcement to the WR to which it is intended to be delivered. You can also decide to deliver based on the routing metrics in the routing announcement or calculated by the node. In the example shown in Figure 5, if the SD advances from the coverage area of ​​WR-3 to WR-4, the SD will send this WR-4 unicast (RA) routing announcement. This RA will be empty, that is, there will be no other entries for other nodes but it will have the header that will inform the receiving node about this SD. The WR (that is, WR-4) that receives this unicast RA will update its routing table in a normal way, but since it is a unicast RA, it will also unify a RA to the next hop towards the IAP with which it is affiliate In this example, upon receiving the SD RA, WR-4 will query your routing table to find the best next hop towards IAP and send a unicast RA to that node. This RA will only have one entry on the SD. In this example, the next best jump to IAP is WR-1, which will follow the same procedure to direct the unicast RA towards the IAP. Other types of messages may also be used instead of explicit RA, for example, some geographic packets can also be used to carry information carried by routing announcement. Information can sometimes also be uploaded to data packets.

p00058[0043] As can be seen from the above, the SD can thus deliver in a very short time that does not depend on the periodic RA. In addition, the IAP will be aware of the SD movement in real time, instead of waiting to receive a periodic RA. Since this critical path update is no longer dependent on the broadcast RA, the periodic interval can be increased which will result in substantially less overhead. Therefore, the embodiment achieves rapid route convergence and low overhead because it can reduce the frequency of transmission of routing advertisements.

p00059[0044] Another smooth delivery technique, which is an ad hoc demand routing modification of the distance vector (AODV), will now be described with respect to Figure 6.

p00060[0045] As one skilled in the art can appreciate, AODV is a well-known routing protocol on demand.

p00061Specifically, this type of routing protocol creates routes only when the source node wishes.

p00062When a node, such as SD, WR or IAP, requires a route to a destination, such as another SD, WR or IAP, the node starts a route discovery process within the 100 network. This process has been completed once that a route is found or after all possible route permutations have been examined. Once a route has been established, the established route is maintained by some type of route maintenance procedure until the destination of both is inaccessible along each route of the source or until the route is no longer desired. .

p00063[0046] Although the demand approach reduces route overload, it adds latency in obtaining a route since routes are not calculated before they are really necessary. Due to the latency involved in the search for routes, packages are necessary to buffer packages at the source. If the node is limited memory, packet losses may occur due to latency. Therefore, this approach generally does not facilitate smooth delivery.

p00064[0047] The modifications to the standard AODV technique according to embodiments of the present invention, which facilitate smooth delivery in an ad hoc network, are described below. These modifications also help to eliminate unidirectional links in the network 100, because AODV assumes bidirectional links.

p00065[0048] Figure 6 illustrates a part of the network 100 in which the WR-1 and WR-2 wireless routers are connected to IAP through wireless links. The IAP is connected to the central LAN as shown in Figure 1. An SD that moves at a road speed is also shown.

p00066[0049] It can be assumed that most of the time, the SD will need a route to IAP since the most important applications made by the SD will be to surf the Internet, voice phone calls over Internet Protocol (VOIP) and so on . Using the AODV Standard Routing Protocol, it takes a long time before the route discovery process ends. In addition, by the time the SD receives a route response, it is likely that the SD has moved to another position that may be outside the scope of a particular WR included in the route response. The following technique according to an embodiment of the present invention avoids this inconvenience and helps to achieve smooth deliveries of SD from one WR or IAP to another.

p00067[0050] In this example, it is assumed that all WR and SD are always associated with an IAP. The IAP and WR periodically transmit a "greeting message" (or neighbor ad) that may have fields similar to AI packages described above. Fixed nodes can maintain routes to the IAP by sending a periodic RREQ, as mentioned above. These nodes can also maintain the route by only sending the RREQ the first time and then not finishing the route to the IAP after receiving the Route Response.

p00068[0051] To provide smooth delivery, the SDs will send a RREQ for their associated IAP at a periodic interval. This periodic interval is variable depending on various factors, such as the speed of the vehicle in which the SD is available (if the speed can be determined, for example, by indicating the average change of geographical location, the activity of SD, the rate of change in signal quality with the neighboring WR and an average of new neighbors added in the neighbor table). Route request packets are generated with the G or D bit set. Consequently, the destination (IAP) learns about the route without making any route requests. If a packet arrives at an IAP intended for some SDs, the packet can be delivered because the IAP knows the routes to all SDs that are associated with that IAP.

p00069[0052] It is also noted that WRs must periodically issue neighbor announcements, in which they must include their IP address, as well as that of the IAP with which they are associated. The SD must cache these ads and errically must unicast the RREQs to these WRs. If the link quality measurements are continuously performed through passive request / send to listen (RTS / CTS) or these announcements, the SD can

p00070intelligently choose, for example, one to three 1-3 of the WRs you are currently listening to (depending on desired backup paths) and unicast a RREQ to these WRs. As stated, the WR number does not have to be within the range of one to three, but rather, it can be any suitable number based on the number of backup routes desired.

p00071[0053] Instead of sending the periodic route request (RREQ) to several wireless routers, all nodes in the network can simply use the Proactive IAP Locator Protocol and achieve smooth delivery of mobile nodes. For it to work, the nodes must actively receive the neighbor announcement / AI message / greeting and must use such a combination of metrics that mean good route in terms of performance, as well as the signal strength between the node and the next hop. For example, if the metrics involve the combination of hops, node types, speed, signal strength, battery power, packet delivery rate, etc., then a mobile node moves away from a WR (i.e. , WR2) and approaching another WR (i.e., WR1) as shown in Figure 6, the cumulative routing metric between the mobile node and the IAP through WR2 will increase while one through WR1 will decrease. As indicated, it is assumed in this example that the mobile node moves away from the coverage area of ​​WR2 and is directed towards the coverage area of ​​WR1. Also, in this example it is assumed that less routing metrics represents a better way than greater routing metrics. Consequently, the mobile node automatically changes the routes and sends a RREQ to WR1 by determining that the routing metric through WR1 is better than through WR2, in order to achieve smooth deliveries.

p00072[0054] As one skilled in the art can appreciate, this plan has the advantage of eliminating unidirectional links. As noted above, the AODV protocol assumes two-way links and, therefore, a network 100 operating in accordance with AODV creates a reverse route from a node that receives an RREQ to the node that made the RREQ as soon as the receiving node Receive the RREQ. It should be noted that if this link is not bidirectional, but rather unidirectional, the AODV Protocol may erroneously create incorrect routes. However, the unicast of the RREQ message confirms that the link is bidirectional since the RTS-CTS link is completed between the node that sends the RREQ and the node that will receive the RREQ before the sending node sends the RREQ . In addition, the bidirectional link is verified because the node that sends the RREQ receives an acknowledgment (ACK) for the unicast RREQ from the node that receives the RREQ.

p00073[0055] Accordingly, the technique described above supports smooth deliveries of SD and low latency in the network of

p00074100 In addition, each IAP in network 100 knows about the routes to all the SDs associated with itself all the time, and these routes between the IAP and its associated SD are updated in real time, which can help reduce the time of route preparation for calls from an external network, for example. In addition, the overhead in network 100 is minimized because the periodic RREQ can be loaded with the data packets that are already being sent from SDs, WR and so on.

p00075[0056] Furthermore, although all the techniques described above are used with AODV in the given examples, these techniques can be used with other routing protocols and, in particular, the on-demand type routing protocol such as dynamic source routing (DSR). or any other suitable protocol.

p00076[0057] Although only some illustrative embodiments of the present invention have been described in detail above, those skilled in the art readily note that many modifications are possible in exemplary embodiments without departing considerably from the instructions and the new advantages of this invention. Therefore, all such modifications must be included within the scope of this invention.