Embedded routing algorithms under the internet protocol routing layer of a software architecture protocol stack in a mobile Ad-Hoc network

• US 7,756,041 B2
• Filed: 05/31/2002
• Issued: 07/13/2010
• Est. Priority Date: 06/14/2001
• Status: Active Grant

• Current Assignee: Strong Force IoT Portfolio 2016, LLC (Strong Force Intellectual Capital, LLC)
• Original Assignee: MeshNetworks, Inc. (Motorola Solutions, Inc.)
• Inventors: White, Eric, Whitehill, Eric
• Primary Examiner(s): Moe, Aung S
• Assistant Examiner(s): Rose, Kerri M
• Application Number:
  US10/157,979
• Publication Number:
  US 20020191573A1
• Time in Patent Office: 2,965 Days
• Field of Search: 370/310, 370/328, 370/338, 370/351, 370/389, 370/400, 370/401, 370/406, 370/216, 370/217, 370/221, 370/225, 370229-232, 370/235, 370/237, 370/236, 370/252, 370/238, 370/253, 370/329, 370/332, 370464-469, 455/445, 455/422.1, 455/452.21, 455/452
• US Class Current: 370/238
• CPC Class Codes: H04L 1/0002 by adapting the transmission rate
• CPC Class Codes: H04L 1/0026 Transmission of channel quality indication
• CPC Class Codes: H04L 1/0034 where the transmitter decides based on inferences, e.g. use of implicit signalling
• CPC Class Codes: H04L 1/1671 the supervisory signal being transmitted together with control information
• CPC Class Codes: H04L 1/1887 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 1/203 Details of error rate determination, e.g. BER, FER or WER
• CPC Class Codes: H04L 1/208 involving signal re-encoding
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 52/04 TPC
• CPC Class Codes: H04W 80/04 Network layer protocols, e.g. mobile IP [Internet Protocol]
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 : in wireless communication networks

Abstract

A novel software architecture protocol stack with embedded routing algorithms under the Internet Protocol (IP) routing layer in order to provide high quality distribution of multimedia (voice, video, and data) services. These routing algorithms may include Logical Link Control, Adaptive Transmission Protocol, Neighbor Discovery, Traffic Control, Ad-Hoc Routing, Flow Processing, Intelligent Access and Admission Control. These routing algorithms when implemented further provide for advantages in speed of service, reliability of service, self-healing in case of catastrophic failure of an infrastructure component, load-balancing and geographic reuse.

Claims

1. An ad-hoc wireless communications network employing a protocol stack, the protocol stack comprising:

an Internet Protocol Routing Layer; and

one or more protocol algorithms embedded between the Internet Protocol Routing Layer and a media access control layer, for routing of data packets between a plurality of nodes in the ad-hoc wireless communications network, the one or more protocol algorithms comprising;

an Ad-Hoc Routing algorithm, wherein the Ad-Hoc Routing algorithm is a least cost type routing algorithm for determining an optimal route based on a quality of service requirements of a traffic type in a real time traffic transiting the ad-hoc wireless communications network, where the cost is an algebraic expression comprising one or more routing metrics, and

a Flow Processing algorithm, wherein the Flow Processing algorithm negotiates a source routed path from a source node to a destination node in the real time traffic, wherein one or more intermediate relay nodes agree to allocate at least a portion of their bandwidth for a Flow Processing request from the Flow Processing algorithm.

2. The ad-hoc wireless communications network employing a protocol stack of claim 1, wherein the one or more routing metrics are selected from a group comprising an energy, a number of hops, a congestion, and a battery life.

3. The ad-hoc wireless communications network employing a protocol stack of claim 1, wherein the Flow Processing algorithm negotiates to provide an agreement by one or more relay nodes and the destination node to communicate one or more messages within the quality of service requirements of the traffic type.

4. The ad-hoc wireless communications network employing a protocol stack of claim 1, wherein the one or more protocol algorithms of the protocol stack further comprise:

an Adaptive Transmission Protocol algorithm, wherein the Adaptive Transmission Protocol algorithm adjusts an information rate and a transmitter power level to provide for a successful transmission of data packets.

5. The ad-hoc wireless communications network employing a protocol stack of claim 4, wherein the Adaptive Transmission Protocol algorithm utilizes one or more channel quality measurements made in a destination node'"'"'s receiver to optimize the information rate and the transmitter power level for one or more subsequent packet transmissions to the destination node.

6. The ad-hoc wireless communications network employing a protocol stack of claim 5, wherein the channel quality measurements comprise one or more of a bit-error rate estimate, a number of multipath signals present during demodulation, a post-detection signal quality, and an analog gain control output.

7. The ad-hoc wireless communications network employing a protocol stack of claim 4, wherein the one or more protocol algorithms of the protocol stack further comprise:

a Neighbor Discovery algorithm, wherein the Neighbor Discovery algorithm provides for a discovery of one or more infrastructure elements, and further provides for a neighborhood size maintenance,

an Intelligent Access module, wherein the Intelligent Access module creates an association between a node and one or more Intelligent Access Points within the ad-hoc wireless communications network,

a Logical Link Control layer, wherein the Logical Link Control layer comprises one or more of a link layer queuing algorithm, a random backoff algorithm, a relevancy timer, and a retransmission policy,

a Traffic Control algorithm, wherein the Traffic Control algorithm stores a data packet until a routing decision provides for the data packet to be serviced by the Logical Link Control layer, and

an Admission Control module, wherein the Admission Control module;

traps a broadcast and tunnels requests to an Intelligent Access Point, and

determines a quality of service required and responds appropriately based on one or more current network conditions as determined by the Ad-Hoc routing protocol.

8. The ad-hoc wireless communications network employing a protocol stack of claim 7, wherein the link layer queuing algorithm comprises a prioritized First-In-First-Out algorithm, wherein a priority scheme for the link layer queuing algorithm is dependent on a Quality-of-Service(QoS) requested and a number of previous transmission attempts.

9. The ad-hoc wireless communications network employing a protocol stack of claim 7, wherein the random backoff algorithm is dependent on a quality of service requested.

10. The ad-hoc wireless communications network employing a protocol stack of claim 1, wherein the one or more protocol algorithms of the protocol stack further comprise:

a Neighbor Discovery algorithm, wherein the Neighbor Discovery algorithm provides for a discovery of one or more infrastructure elements, and further provides for a neighborhood size maintenance, and

an Intelligent Access module, wherein the Intelligent Access module creates an association between a node and one or more Intelligent Access Points within the ad-hoc wireless communications network.

11. The ad-hoc wireless communications network employing a protocol stack of claim 10, wherein the Neighbor Discovery algorithm uses a solicitation message for a discovery of one or more infrastructure elements.

12. The ad-hoc wireless communications network employing a protocol stack of claim 10, wherein the Neighbor Discovery algorithm sends out beacons at a slow rate to probe the neighborhood.

13. The ad-hoc wireless communications network employing a protocol stack of claim 10, wherein the Neighbor Discovery algorithm on passive listening for receiving information.

14. The ad-hoc wireless communications network employing a protocol stack of claim 10, wherein the Neighbor Discovery algorithm maintains node information including one or more of a neighbor identity, a received power, a data rate to a destination, a connectivity information, a node'"'"'s position, and a suitability to act as a position reference.