System and method for communication in a wireless mobile ad-hoc network

• US 8,341,289 B2
• Filed: 05/17/2006
• Issued: 12/25/2012
• Est. Priority Date: 05/17/2005
• Status: Active Grant

• Current Assignee: Rajant Corporation
• Original Assignee: Rajant Corporation
• Inventors: Hellhake, Paul R., Lamb, Martin A., Parks, Joseph E., Mansanpally, Rajashekhar
• Primary Examiner(s): HIGA, BRENDAN Y
• Application Number:
  US11/435,287
• Publication Number:
  US 20070038743A1
• Time in Patent Office: 2,414 Days
• Field of Search: 709230-237, 709238-244, 709223-224, 709/227, 370235-2381, 3703952-39543, 370/401, 370464-480
• US Class Current: 709/238
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 61/25 of the same type
• CPC Class Codes: H04L 61/5014 using dynamic host configuration protocol [DHCP] or bootstrap protocol [BOOTP]
• CPC Class Codes: H04L 61/5061 Pools of addresses
• CPC Class Codes: H04W 28/18 Negotiating wireless communication parameters
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes
• CPC Class Codes: H04W 72/00 Local resource management
• CPC Class Codes: H04W 76/20 Manipulation of established connections
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

A system and method for improving digital communication in a wireless mobile ad-hoc network. More specifically, the system includes one or more portable network devices operable to support the seamless operation of a self-initializing, self-healing, adaptive portable network. The portable network devices implement protocols that provide bandwidth management capabilities for use with radios, routers and other wireless network devices. Each portable network device includes at least one wireless transceiver, a processor and control software. The processor and control software are logically coupled to the wireless transceiver to facilitate digital communication via a plurality of communication channels with other network devices.

Claims

1. A method of communicating in an ad-hoc network, comprising:

providing at least one portable network device including a transceiver and a processor that implements a data communication protocol to communicate communications data to other network devices through one or more network ports connected to the other network devices in the ad-hoc network, the communications data being divided into data packets, and each data packet being encoded with a protocol header that includes the packet'"'"'s source address and cost information;

detecting an incoming data packet received by the portable network device;

identifying an ingress port on which the data packet was received;

reading the packet'"'"'s source address and cost information;

comparing the packet'"'"'s source address, cost information, and ingress port with source address, cost information, and ingress port stored in a bridge table in the portable network device to determine retransmission parameters for each data packet;

determining based on the retransmission parameters whether the data packet should be dropped or retransmitted through one or more of the network ports of the portable network device and processing the data packet accordingly; and

determining whether lower cost routing is available for packets to the source based on the results of said comparing step and, if so, storing new cost and routing information associated with the lower cost routing in the bridge table.

2. The method of claim 1, further comprising a step of determining whether the bridge table has an entry corresponding to the packet'"'"'s source address and, if not, creating a bridge table entry using the cost information provided in the data packet.

3. The method of claim 1, further comprising a step of determining whether the bridge table has an entry corresponding to a packet destination and, if not, creating a bridge table entry for the packet destination.

4. The method of claim 1, further comprising the steps of detecting an incoming data packet that has not been encoded with the packet'"'"'s source address and cost information and encoding the data packet with the packet'"'"'s source address and cost information before retransmitting the data packet to a wireless device on the network.

5. The method of claim 1, wherein the data packet includes a protocol identifier indicating that the data packet includes a header to facilitate transmission in the ad-hoc network.

6. The method of claim 5, further comprising the steps of changing the protocol identifier, removing the source address and cost information from the data packet and retransmitting the data packet via a non-ad-hoc network connection.

7. The method of claim 5, wherein the step of reading the packet'"'"'s source address and cost information includes reading at least one of a destination address, source address, source sequence number (SSN), mesh protocol identifier, cost, and one or more mesh protocol flags.

8. The method of claim 7, wherein the mesh protocol flags comprise lower-order bits including at least one of an introductory flag, a discovery flag and, an undeliverable flag.

9. The method of claim 8, wherein the mesh protocol flags include the undeliverable flag when the destination address is not at least one of broadcast, multicast, or local, and the data packet is sent back to the source via the reception port when the destination address is not at least one of broadcast, multicast, or local.

10. The method of claim 1, wherein comparing header information with the bridge table includes comparing source information in the header with source information in the bridge table.

11. The method of claim 1, wherein comparing header information with the bridge table includes comparing destination information in the header with destination information in the bridge table.

12. The method of claim 1, wherein comparing header information with the bridge table includes comparing a timestamp associated with the data packet with a current timestamp.

13. An ad-hoc mesh network, comprising:

a portable network device that includes;

at least one wireless transceiver and a processor that performs stored program steps to operate the portable mesh network device as a node in the ad-hoc mesh network by implementing a data communication protocol that communicates communications data to other mesh network devices in the ad-hoc mesh network through one or more mesh network ports, the communications data being divided into data packets, and each data packet being encoded with a protocol header that includes the packet'"'"'s source address and cost information; and

a bridge table that identifies known mesh network devices and cost information for data transmissions to the known mesh network devices,

the processor being configured to detect an incoming data packet received by the portable network device,

identify an ingress port on which the data packet was received,

read the packet'"'"'s source address and cost information,

compare the packet'"'"'s source address, cost information, and ingress port with source address, cost information, and ingress port stored in the bridge table to determine retransmission parameters for each data packet,

determine based on the retransmission parameters whether the data packet should be dropped or retransmitted through one or more of the network ports of the portable network device and process the data packet accordingly; and

determine whether lower cost routing is available for packets to the source based on the results of said comparison and, if so, storing new cost and routing information associated with the lower cost routing in the bridge table.

14. The ad-hoc mesh network of claim 13, wherein the processor is further configured to determine whether the bridge table has an entry corresponding to the packet'"'"'s source address and, if not, to create a bridge table entry using the cost information provided in the data packet.

15. The ad-hoc mesh network of claim 13, wherein the processor is further configured to determine whether the bridge table has an entry corresponding to a packet destination and, if not, to create a bridge table entry for the packet destination.

16. The ad-hoc mesh network of claim 13, wherein the processor is further configured to determine whether the data packet has been encoded with the packet'"'"'s source address and cost information and, if not, to encode the data packet with the packet'"'"'s source address and cost information before retransmitting the data packet to a wireless device on the ad-hoc mesh network.

17. The ad-hoc mesh network of claim 16, wherein the processor is further configured to change the protocol identifier, to remove the source address and cost information from the data packet, and to retransmit the data packet via a non-ad-hoc network connection.

18. The ad-hoc mesh network of claim 16, wherein reading the packet'"'"'s source address and cost information includes reading at least a destination address, source address, source sequence number (SSN), mesh protocol identifier, cost, and one or more mesh protocol flags.

19. The ad-hoc mesh network of claim 18, wherein the mesh protocol flags comprise lower-order bits including at least one of an introductory flag, a discovery flag and, an undeliverable flag.

20. The ad-hoc mesh network of claim 19, wherein the mesh protocol flags include the undeliverable flag when the destination address is not at least one of broadcast, multicast, or local, and the data packet is sent back to the source via a reception port on which the data packet was received when the destination address is not at least one of broadcast, multicast, or local.

21. The ad-hoc mesh network of claim 13, wherein the protocol implements a distinctive ethertype identifier indicating that the data packet includes data to facilitate transmission in the ad-hoc mesh network.

22. An ad-hoc mesh network, comprising:

a portable network device that includes;

at least one wireless transceiver and a processor that performs stored program steps to operate the portable mesh network device as a node in the ad-hoc mesh network by implementing a data communication protocol that communicates communications data to other mesh network devices in the ad-hoc mesh network through one or more mesh network ports, the communications data being divided into data packets, and each data packet being encoded with a protocol header that includes packet source and cost information; and

a bridge table that identifies known mesh network devices and cost information for data transmissions to the known mesh network devices;

wherein the processor is configured to compare the packet source and cost information in the data packet with corresponding information in the bridge table to determine whether lower cost routing is available for transmitting data packets to the source and, if so, to store new cost and routing information associated with the lower cost routing in the bridge table;

wherein implementation of the data communication protocol causes each mesh network device in the ad-hoc mesh network to determine retransmission parameters for each data packet, the retransmission parameters establishing whether the data packet should be dropped or retransmitted to other mesh network devices in the ad-hoc mesh network and through which mesh network port the data packet should be retransmitted;

wherein the protocol header further includes destination information;

wherein the bridge table further identifies at least one mesh network device with a source address that corresponds to the packet source information and at least one mesh network device with a destination address that corresponds to the packet destination information;

wherein each mesh network device in the ad-hoc mesh network is configured to compare the packet destination information with corresponding information in the bridge table in that mesh network device to determine if the destination address is at least one of broadcast, multicast, or local and to update the retransmission parameters so that the destination information identifies a data packet as undeliverable when the destination address is not at least one of broadcast, multicast, or local;

wherein the processor of the portable network device sends the data packet back to the at least one mesh network device with the source address that corresponds to the packet source information via a mesh network port through which the data packet was received when the destination information identifies that data packet as undeliverable; and

wherein a processor at the at least one mesh network device with the source address that corresponds to the packet source information that updates its bridge table to remove the destination address when the destination information identifies that data packet as undeliverable.

23. The ad-hoc mesh network of claim 22, wherein the processor is further configured to determine whether the bridge table has an entry corresponding to the packet'"'"'s source address and, if not, to create a bridge table entry using the cost information provided in the data packet.

24. The ad-hoc mesh network of claim 22, wherein the processor is further configured to determine whether the bridge table has an entry corresponding to a packet destination and, if not, to create a bridge table entry for the packet destination.

25. The ad-hoc mesh network of claim 22, wherein the processor is further configured to determine whether the data packet has been encoded with the packet'"'"'s source address and cost information and, if not, to encode the data packet with the packet'"'"'s source address and cost information before retransmitting the data packet to a wireless device on the ad-hoc mesh network.

26. The ad-hoc mesh network of claim 25, wherein the processor is further configured to change the protocol identifier, to remove the source address and cost information from the data packet, and to retransmit the data packet via a non-ad-hoc network connection.

27. The ad-hoc mesh network of claim 25, wherein reading the packet'"'"'s source address and cost information includes reading at least a destination address, source address, source sequence number (SSN), mesh protocol identifier, cost, and one or more mesh protocol flags.

28. The ad-hoc mesh network of claim 27, wherein the mesh protocol flags comprise lower-order bits including at least one of an introductory flag, a discovery flag and, an undeliverable flag.

29. The ad-hoc mesh network of claim 28, wherein the mesh protocol flags include the undeliverable flag when the destination address is not at least one of broadcast, multicast, or local, and the data packet is sent back to the source via a reception port on which the data packet was received when the destination address is not at least one of broadcast, multicast, or local.

30. The ad-hoc mesh network of claim 22, wherein the protocol implements a distinctive ethertype identifier indicating that the data packet includes data to facilitate transmission in the ad-hoc mesh network.

31. The ad-hoc mesh network of claim 22, wherein the processor of the portable network device is configured such that potential flood packets are carried as unicast packets towards a densest part of the mesh network.

32. The ad-hoc mesh network of claim 22, wherein the processor of the portable network device is configured to use source sequence numbers in the packets for loop prevention.