Ad-hoc network and method of routing communications in a communication network

• US 7,349,360 B2
• Filed: 05/19/2003
• Issued: 03/25/2008
• Est. Priority Date: 05/19/2003
• Status: Active Grant

• Current Assignee: Eaton Intelligent Power Limited (Eaton Corporation PLC.)
• Original Assignee: Eaton Corporation (Eaton Corporation PLC.)
• Inventors: Gutierrez, José A., Pereira, Luis R.
• Primary Examiner(s): Ngo; Ricky Q.
• Assistant Examiner(s): Mui; Gary
• Application Number:
  US10/441,315
• Publication Number:
  US 20040233855A1
• Time in Patent Office: 1,772 Days
• Field of Search: 370/395.31, 370/401, 370/396, 370/408, 370/395.32, 370/255, 370/229, 370/230, 370/230.1, 370/231, 370/235, 370/252, 370/253
• US Class Current: 370/315
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• 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

An ad-hoc low rate-wireless personal area network (LR-WPAN) includes an ad-hoc network coordinator having a first processor, a first memory, and a first communication interface; and a plurality of ad-hoc network devices. Each of the devices includes a second processor, a second memory, and a second communication interface for communication with the first communication interface of the coordinator or with the second communication interface of another one of the devices. A simple, low-cost, incremental source routing is employed. The first memory stores complete communication routes for messages from the coordinator through at least one of the devices to other devices. The second memory of each of the devices stores an identification of another device to forward a message from the second communication interface of a corresponding one of the devices toward the coordinator'"'"'s first communication interface and through the second communication interface of that other device.

Claims

1. An ad-hoc network comprising:

an ad-hoc network coordinator comprising;

a first processor,

a first memory,

a first communication interface;

a plurality of ad-hoc network devices, each of said ad-hoc network devices comprising;

a second processor,

a second memory,

a second communication interface for communication with the first communication interface of said ad-hoc network coordinator or with the second communication interface of another one of said ad-hoc network devices,

wherein said first memory stores for at least some of said ad-hoc network devices a complete communication route for messages from said ad-hoc network coordinator through at least one of said ad-hoc network devices to a corresponding one of said at least some of said ad-hoc network devices,

wherein said second memory of each of said ad-hoc network devices stores an identification of another one of said ad-hoc network devices to forward a message from the second communication interface of a corresponding one of said ad-hoc network devices toward the first communication interface of said ad-hoc network coordinator and through the second communication interface of said another one of said ad-hoc network devices;

wherein said second processor includes means for providing said identification of another one of said ad-hoc network devices to forward a message based upon quality information associated with communications between said second communication interface of said corresponding one of said ad-hoc network devices and said second communication interface of said another one of said ad-hoc network devices; and

wherein said quality information is positively correlated with a quality value associated with a communication link between said second communication interface of said corresponding one of said ad-hoc network devices and said second communication interface of said another one of said ad-hoc network devices, and is negatively correlated with a count of hops from said second communication interface of said another one of said ad-hoc network devices to said ad-hoc network coordinator.

2. A method of routing communications in an ad-hoc network, said method comprising:

employing an ad-hoc network coordinator including a first communication interface;

employing a plurality of ad-hoc network devices;

employing with each of said ad-hoc network devices a second communication interface for communication with the first communication interface of said ad-hoc network coordinator or with the second communication interface of another one of said ad-hoc network devices;

storing a plurality of complete communication routes for at least some of said ad-hoc network devices for messages from said ad-hoc network coordinator through at least one of said ad-hoc network devices to a corresponding one of said at least some of said ad-hoc network devices;

for each of said ad-hoc network devices, storing an identification of another one of said ad-hoc network devices to forward a message from the second communication interface of a corresponding one of said ad-hoc network devices toward the first communication interface of said ad-hoc network coordinator and through the second communication interface of said another one of said ad-hoc network devices;

employing routing information with each of said ad-hoc network devices to forward said message from said corresponding one of said ad-hoc network devices to said ad-hoc network coordinator; and

including with said routing information at least one entry comprising a network address of another one of said ad-hoc network devices other than said corresponding one of said ad-hoc network devices, a quality value corresponding to a communication link between said corresponding one of said ad-hoc network devices and said another one of said ad-hoc network devices, a count of hops from said corresponding one of said ad-hoc network devices through said another one of said ad-hoc network devices toward said ad-hoc network coordinator, and an indication whether said another one of said ad-hoc network devices is mains-powered.

3. The method of claim 2 further comprising

employing as said another one of said ad-hoc network devices a mains-powered ad-hoc network device having a rechargeable power capability.

4. The method of claim 2 further comprising

for each of at least some of said another one of said ad-hoc network devices, determining a quality function based upon said routing information;

and

determining a maximum value of said quality function and responsively starting a communication route for said message from said corresponding one of said ad-hoc network devices toward said ad-hoc network coordinator and through the corresponding one of said at least some of said another one of said ad-hoc network devices having said maximum value.

5. The method of claim 2 further comprising

updating said routing information based upon changes in said ad-hoc network.

6. The method of claim 2 further comprising

employing as said message a first message;

receiving a second message from one of said ad-hoc network devices at said corresponding one of said ad-hoc network devices;

determining that said second message was acknowledged; and

increasing the quality value for said one of said ad-hoc network devices.

7. The method of claim 6 further comprising

employing said quality value having a predetermined maximum value.

8. The method of claim 2 further comprising

employing as said message a first message;

receiving a second message from one of said ad-hoc network devices at said corresponding one of said ad-hoc network devices;

determining that said second message was not acknowledged; and

decreasing the quality value for said one of said ad-hoc network devices.

9. A method of routing communications in an ad-hoc network, said method comprising:

employing an ad-hoc network coordinator including a first communication interface;

employing a plurality of ad-hoc network devices;

employing with each of said ad-hoc network devices a second communication interface for communication with the first communication interface of said ad-hoc network coordinator or with the second communication interface of another one of said ad-hoc network devices;

storing a plurality of complete communication routes for at least some of said ad-hoc network devices for messages from said ad-hoc network coordinator through at least one of said ad-hoc network devices to a corresponding one of said at least some of said ad-hoc network devices;

for each of said ad-hoc network devices, storing an identification of another one of said ad-hoc network devices to forward a message from the second communication interface of a corresponding one of said ad-hoc network devices toward the first communication interface of said ad-hoc network coordinator and through the second communication interface of said another one of said ad-hoc network devices;

broadcasting a plurality of request messages from said corresponding one of said ad-hoc network devices to at least some of other ones of said ad-hoc network devices;

employing routing information with each of said ad-hoc network devices to forward said message from said corresponding one of said ad-hoc network devices toward said ad-hoc network coordinator;

including with said muting information at least one entry comprising a count of hops from said corresponding one of said ad-hoc network devices through at least one of said ad-hoc network devices toward said ad-hoc network coordinator, and an indication whether said at least one of said ad-hoc network devices has a communication route to said ad-hoc network coordinator and is mains-powered;

receiving a response message from one of said ad-hoc network devices;

entering an entry for said one of said ad-hoc network devices in said routing information;

obtaining said indication and said count of hops from said response message; and

entering said indication and said count of hops in said routing information for said entry for said one of said ad-hoc network devices.

10. A method of routing communications in an ad-hoc network, said method comprising:

employing an ad-hoc network coordinator including a first communication interface;

employing a plurality of ad-hoc network devices;

employing with each of said ad-hoc network devices a second communication interface for communication with the first communication interface of said ad-hoc network coordinator or with the second communication interface of another one of said ad-hoc network devices;

storing a plurality of complete communication routes for at least some of said ad-hoc network devices for messages from said ad-hoc network coordinator through at least one of said ad-hoc network devices to a corresponding one of said at least some of said ad-hoc network devices;

for each of said ad-hoc network devices, storing an identification of another one of said ad-hoc network devices to forward a message from the second communication interface of a corresponding one of said ad-hoc network devices toward the first communication interface of said ad-hoc network coordinator and through the second communication interface of said another one of said ad-hoc network devices;

employing as said message a first message;

employing a first ad-hoc network device as said corresponding one of said ad-hoc network devices;

employing a second ad-hoc network device as another one of said ad-hoc network devices;

employing routing information with said first ad-hoc network device to forward said first message from said first ad-hoc network device toward said ad-hoc network coordinator,

including with said routing information at least one entry comprising a count of hops from said first ad-hoc network device through at least one different one of said ad-hoc network devices toward said ad-hoc network coordinator, and an indication whether said different one of said ad-hoc network devices is mains-powered;

receiving a second message from said second ad-hoc network device; and

entering an winy for said second ad-hoc network device in said routing information.

11. The method of claim 10 further comprising

obtaining said indication from said second message;

entering said indication in said entry for said second ad-hoc network device in said routing information; and

setting said count of hops in said entry for said second ad-hoc network device in said routing information to a predetermined count.