Route optimization using star-mesh hybrid topology in localized dense ad-hoc networks

• US 10,230,634 B2
• Filed: 03/02/2016
• Issued: 03/12/2019
• Est. Priority Date: 09/25/2015
• Status: Active Grant

• Current Assignee: Digital Lumens, Inc. (Ams-Osram AG)
• Original Assignee: OSRAM Sylvania Inc. (Ams-Osram AG)
• Inventors: Ko, David, O'Hagan, Liam, Warner, Stefan, Tolisano, Leo
• Primary Examiner(s): Pasia, Redentor
• Application Number:
  US15/058,192
• Publication Number:
  US 20170093716A1
• Time in Patent Office: 1,105 Days
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04W 4/80 Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Optimized routing in localized dense networks is provided. A packet is received at a first network device in a network. An optimal route for the packet to a neighbor network device in the network is determined using a Source Routing Table (SRT), wherein the SRT includes an optimized routing table and a standard routing table, and wherein the optimized routing table comprises a list of neighbor network devices that the first network device can route to directly and wherein the standard routing table comprises a ZigBee source routing table. The packet is routed using the optimal route.

Claims

1. A method, comprising:

receiving a packet at a first network device in a network;

determining an optimal route for the packet to a neighbor network device in the network using a Source Routing Table (SRT), wherein the SRT includes an optimized routing table and a standard routing table;

routing the packet to the neighbor network device using the optimal route; and

maintaining the SRT, wherein maintaining the SRT comprises;

determining whether a route in the SRT is one-hop optimized;

when the route is determined not to be one-hop optimized, sending a test packet directly to the neighbor network device with no intermediary hops using a one-hop optimized route;

when sending a test packet fails, canceling a maintaining process for the route; and

when sending a test packet succeeds, resending the test packet directly to the neighbor network device with no intermediary hops a predetermined number of times at predetermined intervals, such that if the resending is successful each time, routing all future non-test packets to the neighbor network device using the one-hop optimized route.

2. The method of claim 1, wherein

the optimized routing table comprises a list of neighbor network devices that the first network device can route to directly, and wherein the standard routing table comprises a ZigBee source routing table.

3. The method of claim 1, wherein maintaining the SRT comprises:

determining whether a route in the SRT is one-hop optimized;

when the route is determined to be one-hop optimized, sending a test packet directly to the neighbor network device with no intermediary hops;

when sending a test packet succeeds, canceling a maintaining process for the route; and

when sending a test packet is not successful, setting the route as not one-hop optimized and routing all future non-test packets to the neighbor network device using the standard routing table of the SRT.

4. The method of claim 1, wherein maintaining the SRT comprises:

determining whether a route to or from a concentrator in the SRT is one-hop optimized;

when the route is determined not to be one-hop optimized, determining whether the concentrator is in a neighbor table and whether a link quality of a link to the concentrator is good;

when the concentrator is either not in a neighbor table or a link quality is not good, repeating determining whether a route to or from a concentrator in the SRT is one-hop optimized after a predetermined time interval;

when the concentrator is either in a neighbor table or a link quality is good, sending a test packet directly to the concentrator with no intermediary hops;

when sending a test packet is not successful, canceling a maintaining process for the route; and

when sending a test packet is successful, sending again a predetermined number of times, and if all are successful, setting the route as one-hop optimized and routing all future non-test packets to the concentrator using the one-hop optimized routing table of the SRT.

5. The method of claim 4, wherein when the route is determined to be one-hop optimized, and wherein a link quality is good, sending a predetermined number of test packets to or from the concentrator;

when sending a test packet succeeds, canceling a maintaining process for the route;

when sending a test packet is not successful, then setting the route as not one-hop optimized and routing all future non-test packets to or from the concentrator using the standard routing table of the SRT; and

when the route is determined to be one-hop optimized and a link quality is not good, then repeating determining whether a route to or from a concentrator in the SRT is one-hop optimized after a predetermined time interval.

6. A computer program product, stored on a non-transitory computer readable medium, including instructions of optimized routing in localized dense networks that, when executed on a processor in communication with the non-transitory computer readable medium, cause the processor to perform operations of:

receiving a packet at a first network device in a network;

determining an optimal route for the packet to a neighbor network device in the network using a Source Routing Table (SRT) wherein the SRT includes an optimized routing table and a standard routing table;

routing the packet using the optimal route; and

maintaining the SRT, by;

determining whether a route in the SRT is one-hop optimized;

when the route is determined not to be one-hop optimized, sending a test packet directly to the neighbor network device with no intermediary hops using a one-hop optimized route;

when sending a test packet fails, canceling a maintaining process for the route; and

when sending a test packet is successful, resending the test packet directly to the neighbor network device with no intermediary hops a predetermined number of times at predetermined intervals, such that if the resending is successful each time, routing all future non-test packets to the neighbor network device using the one-hop optimized route.

7. The computer program product of claim 6, wherein

the optimized routing table comprises a list of neighbor network devices that the first network device can route to directly, and wherein the standard routing table comprises a ZigBee source routing table.

8. The computer program product of claim 6, wherein the instructions for maintaining the SRT cause the processor to perform further operations of:

determining whether a route in the SRT is one-hop optimized;

when the route is determined to be one-hop optimized, sending a test packet directly to the neighbor network device with no intermediary hops;

when sending a test packet succeeds, canceling a maintaining process for the route; and

when sending a test packet is not successful, setting the route as not one-hop optimized and routing all future non-test packets to the neighbor network device using the standard routing table of the SRT.

9. The computer program product of claim 6, wherein the instructions for maintaining the SRT cause the processor to perform further operations of:

determining whether a route to or from a concentrator in the SRT is one-hop optimized;

when the route is determined not to be one-hop optimized, determining whether the concentrator is in a neighbor table and whether a link quality of a link to the concentrator is good;

when the concentrator is either not in a neighbor table or a link quality is not good, repeating determining whether a route to or from a concentrator in the SRT is one-hop optimized after a predetermined time interval;

when the concentrator is either in a neighbor table or a link quality is good, sending a test packet directly to the concentrator with no intermediary hops;

when sending a test packet is not successful, canceling a maintaining process for the route; and

when sending a test packet is successful, sending again a predetermined number of times, and if all are successful, setting the route as one-hop optimized and routing all future non-test packets to the concentrator using the one-hop optimized routing table of the SRT.

10. The computer program product of claim 9, wherein the instructions cause the processor to perform further operations of:

when the route is determined to be one-hop optimized, and wherein a link quality is good, sending a predetermined number of test packets to or from the concentrator;

when sending a test packet succeeds, canceling a maintaining process for the route;

when sending a test packet is not successful, then setting the route as not one-hop optimized and routing all future non-test packets to or from the concentrator using the standard routing table of the SRT; and

when the route is determined to be one-hop optimized and a link quality is not good, then repeating determining whether a route to or from a concentrator in the SRT is one-hop optimized after a predetermined time interval.

11. A network device comprising:

a memory;

a processor;

a communications interface; and

an interconnection mechanism coupling the memory, the processor, and the communications interface;

wherein the memory is encoded with an application to optimize routing in localized dense networks, that when performed on the processor, provides a process to optimize routing in localized dense networks, the process causing the network device to perform operations of;

receiving a packet at a first network device in a network;

determining an optimal route for the packet to a neighbor network device in the network using a Source Routing Table (SRT) wherein the SRT includes an optimized routing table and a standard routing table;

routing the packet to the neighbor network device using the optimal route; and

maintaining the SRT, wherein maintaining the SRT comprises;

determining whether a route in the SRT is one-hop optimized;

when the route is determined not to be one-hop optimized, sending a test packet directly to the neighbor network device with no intermediary hops using a one-hop optimized route;

when sending a test packet fails, canceling a maintaining process for the route; and

when sending a test packet is successful, resending the test packet directly to the neighbor network device with no intermediary hops a predetermined number of times at predetermined intervals, such that if the resending is successful each time, routing all future non-test packets to the neighbor network device using the one-hop optimized route.

12. The network device of claim 11, wherein the optimized routing table comprises a list of neighbor network devices that the first network device can route to directly, and wherein the standard routing table comprises a ZigBee source routing table.

13. The network device of claim 11, wherein maintaining the SRT comprises:

determining whether a route in the SRT is one-hop optimized;

when the route is determined to be one-hop optimized, sending a test packet directly to the neighbor network device with no intermediary hops;

when sending a test packet succeeds, canceling a maintaining process for the route; and

when sending a test packet is not successful, setting the route as not one-hop optimized and routing all future non-test packets to the neighbor network device using the standard routing table of the SRT.

14. The network device of claim 11, wherein maintaining the SRT comprises:

determining whether a route to or from a concentrator in the SRT is one-hop optimized;

when the route is determined not to be one-hop optimized, determining whether the concentrator is in a neighbor table and whether a link quality of a link to the concentrator is good;

when the concentrator is either not in a neighbor table or a link quality is not good, repeating determining whether a route to or from a concentrator in the SRT is one-hop optimized after a predetermined time interval;

when the concentrator is either in a neighbor table or a link quality is good, sending a test packet directly to the concentrator with no intermediary hops;

when sending a test packet is not successful, canceling a maintaining process for the route; and

when sending a test packet is successful, sending again a predetermined number of times, and if all are successful, setting the route as one-hop optimized and routing all future non-test packets to the concentrator using the one-hop optimized routing table of the SRT.

15. The network device of claim 14, further comprising operations of:

when the route is determined to be one-hop optimized, and wherein a link quality is good, sending a predetermined number of test packets to or from the concentrator;

when sending a test packet succeeds, canceling a maintaining process for the route;

when sending a test packet is not successful, then setting the route as not one-hop optimized and routing all future non-test packets to or from the concentrator using the standard routing table of the SRT; and

when the route is determined to be one-hop optimized and a link quality is not good, then repeating determining whether a route to or from a concentrator in the SRT is one-hop optimized after a predetermined time interval.