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

• US 20040233855A1
• Filed: 05/19/2003
• Published: 11/25/2004
• Est. Priority Date: 05/19/2003
• Status: Active Grant

• Current Assignee: Eaton Intelligent Power Limited (Eaton Corporation PLC.)
• Original Assignee: Eaton Corp. (Wisconsin) (Eaton Corporation PLC.)
• Inventors: Pereira, Luis R., Gutierrez, Jose A.
• Granted Patent: US 7,349,360 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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, and

a first communication interface; and

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

a second processor,

a second memory, and

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, and

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.

2. The ad-hoc network of claim 1 wherein said first and second communication interfaces include at least one wireless communication link therebetween.

3. The ad-hoc network of claim 1 wherein said messages from said ad-hoc network coordinator and said message from the second communication interface of a corresponding one of said ad-hoc network devices include data therein.

4. The ad-hoc network of claim 1 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.

5. The ad-hoc network of claim 4 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.

6. The ad-hoc network of claim 4 wherein said ad-hoc network devices include a first ad-hoc network device, a second ad-hoc network device and a third ad-hoc network device;

wherein said message from the second communication interface of a corresponding one of said ad-hoc network devices is forwarded in a first message from said first ad-hoc network device to said second ad-hoc network device, and in a second message from said second ad-hoc network device to said third ad-hoc network device, and in a third message from said third ad-hoc network device to said ad-hoc network coordinator;

wherein said means for providing of said second processor of said first ad-hoc network device provides said identification of said second ad-hoc network device;

wherein said means for providing of said second processor of said second ad-hoc network device provides said identification of said third ad-hoc network device; and

wherein said means for providing of said second processor of said third ad-hoc network device provides said identification of said ad-hoc network coordinator.

7. The ad-hoc network of claim 6 wherein a first partial communication route to said ad-hoc network coordinator is defined by said first ad-hoc network device and said second ad-hoc network device and is stored in said first message;

wherein a second partial communication route to said ad-hoc network coordinator is defined by said first ad-hoc network device, said second ad-hoc network device and said third ad-hoc network device, and is stored in said second message; and

wherein a complete communication route between said first ad-hoc network device and said ad-hoc network coordinator is defined by said first ad-hoc network device, said second ad-hoc network device, said third ad-hoc network device and said ad-hoc network coordinator, and is stored in said third message.

8. The ad-hoc network of claim 1 wherein said first processor employs a full source routing protocol for communication of a plurality of messages from the first communication interface of said ad-hoc network coordinator to the second communication interface of said ad-hoc network devices.

9. The ad-hoc network of claim 8 wherein said ad-hoc network devices include a first ad-hoc network device, a second ad-hoc network device and a third ad-hoc network device;

wherein one of said messages is forwarded in a first message from said ad-hoc network coordinator to said first ad-hoc network device, and in a second message from said first ad-hoc network device to said second ad-hoc network device, and in a third message from said second ad-hoc network device to said third ad-hoc network device; and

wherein said complete communication route is defined by said ad-hoc network coordinator, said first ad-hoc network device, said second ad-hoc network device and said third ad-hoc network device, and is stored in each of said first, second and third messages.

10. The ad-hoc network of claim 1 wherein said ad-hoc network devices include a first ad-hoc network device, a second ad-hoc network device and a third ad-hoc network device;

wherein one of said messages is forwarded in a first message from said ad-hoc network coordinator to said first ad-hoc network device, and in a second message from said first ad-hoc network device to said second ad-hoc network device, and in a third message from said second ad-hoc network device to said third ad-hoc network device; and

wherein said complete communication route is defined by said ad-hoc network coordinator, said first ad-hoc network device, said second ad-hoc network device and said third ad-hoc network device, and is stored in said first message.

11. The ad-hoc network of claim 10 wherein a first partial communication route is defined by said second ad-hoc network device and said third ad-hoc network device, and is stored in said second message;

and wherein a second partial communication route is defined by said third ad-hoc network device, and is stored in said third message.

12. The ad-hoc network of claim 1 wherein said second processor of said corresponding one of said ad-hoc network devices includes means for updating said stored identification in response to at least one of:

(a) a message from said ad-hoc network coordinator, and (b) loss of communication with the second communication interface of said another one of said ad-hoc network devices.

13. The ad-hoc network of claim 1 wherein said second processor of said corresponding one of said ad-hoc network devices includes means for forwarding said message from said corresponding one of said ad-hoc network devices through the second communication interface of said another one of said ad-hoc network devices to said ad-hoc network coordinator based upon routing information, and means for updating said routing information based upon changes in said ad-hoc network.

14. The ad-hoc network of claim 1 wherein said identification includes an indication whether said another one of said ad-hoc network devices has a communication route to said ad-hoc network coordinator and is mains-powered.

15. The ad-hoc network of claim 1 wherein said second processor of said corresponding one of said ad-hoc network devices includes means for forwarding said message from said corresponding one of said ad-hoc network devices through the second communication interface of said another one of said ad-hoc network devices to said ad-hoc network coordinator based upon routing information, and means for updating said routing information based upon whether said forwarded message was acknowledged by said another one of said ad-hoc network devices.

16. 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; and

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.

17. The method of claim 16 further comprising

associating with said identification of another one of said ad-hoc network devices a first value indicating that the second communication interface of said another one of said ad-hoc network devices is able to directly or indirectly communicate with the first communication interface of said ad-hoc network coordinator, and a second value indicating that said another one of said ad-hoc network devices is mains-powered.

18. The method of claim 16 further comprising

forwarding said message as a first message from a first one of said ad-hoc network devices to a second one of said ad-hoc network devices;

forwarding said first message as a second message from the second one of said ad-hoc network devices to a third one of said ad-hoc network devices;

forwarding said second message as a third message from the third one of said ad-hoc network devices to said ad-hoc network coordinator;

providing as said identification an identification of said second one of said ad-hoc network devices at said first one of said ad-hoc network devices;

providing as said identification an identification of said third one of said ad-hoc network devices at said second one of said ad-hoc network devices; and

providing as said identification an identification of said ad-hoc network coordinator at said third one of said ad-hoc network devices.

19. The method of claim 18 further comprising

including with said first message an address of said first one of said ad-hoc network devices;

including with said second message said address of said first one of said ad-hoc network devices and an address of said second one of said ad-hoc network devices; and

including with said third message said address of said first one of said ad-hoc network devices, said address of said second one of said ad-hoc network devices, and an address of said third one of said ad-hoc network devices.

20. The method of claim 16 further comprising

employing a plurality of wireless communication links between said first communication interface and at least some of said second communication interfaces.

21. The method of claim 16 further comprising

sending information data between said first and second communication interfaces.

22. The method of claim 16 further comprising

employing a plurality of mobile ad-hoc network devices as said ad-hoc network devices.

23. The method of claim 16 further comprising

employing a wireless personal area network (LR-WPAN) as said ad-hoc network.

24. The method of claim 16 further comprising

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.

25. The method of claim 24 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.

26. The method of claim 24 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.

27. The method of claim 16 further comprising

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;

and

receiving at least one response message from said at least some of other ones of said ad-hoc network devices, each of said at least one response message including an identification that a corresponding one of said at least some of other ones of said ad-hoc network devices has a communication route to said ad-hoc network coordinator.

28. The method of claim 27 further comprising

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;

associating 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, and an indication whether said another one of said ad-hoc network devices has a communication route to said ad-hoc network coordinator; and

determining from said routing information that for said corresponding one of said ad-hoc network devices there are none of said another one of said ad-hoc network devices having a communication route to said ad-hoc network coordinator, and responsively starting said broadcasting a plurality of request messages.

29. The method of claim 16 further comprising

employing as said message a first message;

sending a second message from said ad-hoc network coordinator toward said corresponding one of said ad-hoc network devices to redefine said stored identification to a different one of said ad-hoc network devices; and

sending a third message from the second communication interface of said 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 different one of said ad-hoc network devices based upon said redefined stored identification.

30. The method of claim 29 further comprising

sending said second message from said ad-hoc network coordinator through some of said ad-hoc network devices to said different one of said ad-hoc network devices;

and

employing said different one of said ad-hoc network devices to forward said second message directly to said corresponding one of said ad-hoc network devices.

31. The method of claim 24 further comprising

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

32. The method of claim 24 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.

33. The method of claim 32 further comprising

employing said quality value having a predetermined maximum value.

34. The method of claim 24 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.

35. The method of claim 28 further comprising

receiving a response message from one of said at least some of other ones of said ad-hoc network devices;

and

entering an entry for said one of said at least some of other ones of said ad-hoc network devices in said routing information.

36. The method of claim 28 further comprising

including with said routing information at least one entry comprising a quality value corresponding to a communication link between said corresponding one of said ad-hoc network devices and a different one of said ad-hoc network devices,

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

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

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

37. The method of claim 27 further comprising

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 routing 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.

38. The method of claim 16 further comprising

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 entry for said second ad-hoc network device in said routing information.

39. The method of claim 38 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.

40. The method of claim 16 further comprising

employing a first memory at said ad-hoc network coordinator to store said complete communication routes;

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;

associating 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;

determining said stored identification of said another one of said ad-hoc network devices from said routing information; and

employing a second memory, which is substantially smaller than said first memory, at said corresponding one of said ad-hoc network devices to store said routing information and said stored identification.

41. A method of routing communications in a communication network, said method comprising:

employing a network coordinator including a first communication interface;

employing a plurality of network devices;

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

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

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