Method and apparatus for reducing the length of a packet storm in a wireless mesh network

• US 10,321,379 B2
• Filed: 04/02/2015
• Issued: 06/11/2019
• Est. Priority Date: 04/16/2014
• Status: Active Grant

• Current Assignee: Signify Holding B.V. (Signify N.V.)
• Original Assignee: Signify Holding B.V. (Signify N.V.)
• Inventors: Ge, Xiaodong
• Primary Examiner(s): Levitan, Dmitry
• Application Number:
  US15/304,031
• Publication Number:
  US 20170034760A1
• Time in Patent Office: 1,531 Days
• Field of Search: 370310, 370312, 370389, 370390, 370400
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/023 Limited or focused flooding to selected areas of a network
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A broadcast transmission will generate a packet storm in a mesh network, which will last for a very long time and block the network for other traffic. There is a parameter in a broadcast control mechanism named radius which controls the duration of the packet storm. The invention proposes to dynamically select the smallest radius to reduce the packet storm to a minimum, by reporting the smallest possible radius parameter for the broadcast control mechanism. Each device or node of the network comprises a neighbor table for tracking which of its neighboring devices or nodes has successfully relayed the broadcast transmission. Additionally, each device or node comprises a broadcast transaction table to keep a record of any new broadcast transmission or transaction that is either initiated locally or received from a neighboring device or node. Each broadcast transmission comprises a so called radius parameter R which indicates an allowed number of hops through the mesh network before the broadcast transmission is discarded. The mechanism to report broadcast status may be realized in an exemplary embodiment of the invention by adding two new tables to track broadcasting status from neighboring devices: the child table, to which the concerned network node or network device has transmitted or relayed a broadcast transmission, and the broadcast listening table; and by adding three fields into the broadcast transaction table: the radius, report interval and report timeout; and also by adding two new parameters into broadcast message itself: report interval and report timeout.

Claims

1. A system for controlling information broadcast in a wireless mesh network, the network comprising a plurality of wirelessly interconnected devices, the system comprising:

a device table comprised in each of the devices, for tracking which device has successfully relayed a broadcast transmission;

a broadcast table comprised in each of the devices, for keeping a record of any new broadcast transmission that has been initiated by a device of the plurality of wirelessly interconnected devices or received from a neighboring device of the plurality of wirelessly interconnected devices;

wherein each broadcast transmission includes a radius parameter R, which indicates an allowed number of hops through said mesh network before the broadcast transmission is discarded;

wherein the system is adapted to add to a new broadcast transmission a radius parameter R, or to reduce the radius parameter R, by one when a received broadcast transmission is forwarded;

wherein the system is adapted to check information provided in the device table and the broadcast table so as to report to a device of the plurality of wirelessly interconnected devices initiating a message, a maximum repetition number, Rmax, representative of the number of hops which was necessary to transmit the message to each device of the plurality of wirelessly interconnected devices, wherein the maximum repetition number Rmax is determined by the system using a broadcast storm as a number of repetitions necessary to reach every device in the network;

wherein the device table includes a neighbor table for tracking which neighboring device, which is a device within a transmission or reception range of the device, has successfully relayed a broadcast transmission;

and wherein the at least one broadcast table includes a broadcast transaction table for keeping a record of any new broadcast transmission that has been initiated by the associated device or received from a neighboring device;

wherein the at least one device table includes,

a child table for tracking which child device, which is a device to which said device has transmitted a broadcast transmission, has successfully relayed the broadcast transmission;

and wherein the at least one broadcast table includes a broadcast listening table for keeping a record of any new broadcast transmission that has been received by a child device.

2. The system of claim 1, wherein the system is adapted to compare the radius parameter R, of a new broadcast transmission with a previous one when updating an existing entry in the broadcast transaction table and to record the smaller one in the broadcast transaction table.

3. The system of claim 1, wherein the system is adapted to check a report interval RPT-int, provided for each recorded broadcast message of the broadcast transaction table, to search for the same broadcast message in the broadcast listening table when the report interval has been reached, and to flag all child devices having received the same broadcast message so as to form a status report message, which status report message comprising a maximum repetition number value for said broadcast message received by each of said flagged child devices.

4. The system of claim 3, wherein the system is adapted to compare all values of the radius parameter R, in the broadcast table for all devices having received the same broadcast message and to insert the largest repetition number in a status report message.

5. The system of claim 1, wherein the system is adapted to check a report timeout RPT-to, provided for each recorded broadcast message of the broadcast transaction table, to search for the same broadcast message in the broadcast listening table when the report timeout has expired, and to flag all child devices having received the same broadcast message so as to form a status report message, which status report message comprising a maximum repetition number value for said broadcast message received by each of said flagged child devices.

6. The system of claim 1, wherein the device initiating a new message is adapted to retransmit a new broadcast transmission if after a timeout any of the devices listed in the device table has not relayed the new broadcast transmission.

7. The system of claim 1, wherein, if a status report message has been received by said system, the system is adapted to:

search for the same message with the shortest radius parameter R, in the broadcast transaction table if there is a child device having the same message and

extract a device address of the message with the shortest radius parameter, or to discard the status report message if there is no such message in the broadcast transaction table.

8. The system of claim 1 said system being adapted to:

extract from at least one received status report message a maximum repetition number which indicates the number of hops necessary to reach a device, and

select the largest value of extracted maximum repetition numbers as a calibration value to generate a radius parameter to be inserted into a broadcast transmission, said radius parameter being indicative of an allowed number of hops through said mesh network before the broadcast transmission is discarded.

9. The system of claim 8, wherein the system is adapted to initiate a re-calibration if it determines that a device of the wireless mesh network is not able to receive a broadcast transmission or that the number of devices not able to receive the broadcast transmission decreases, and wherein the system is adapted to start re-calibration by selecting an initial value for the radius parameter that is larger than a current value and smaller than a default value.

10. A system for controlling information broadcast in a wireless mesh network, the network comprising a plurality of wirelessly interconnected devices, the system comprising:

a device table comprised in each of the devices, for tracking which device has successfully relayed a broadcast transmission;

a broadcast table comprised in each of the devices, for keeping a record of any new broadcast transmission that has been initiated by a device of the plurality of wirelessly interconnected devices or received from a neighboring device of the plurality of wirelessly interconnected devices;

wherein each broadcast transmission includes a radius parameter R, which indicates an allowed number of hops through said mesh network before the broadcast transmission is discarded;

wherein the system is adapted to add to a new broadcast transmission a radius parameter R, or to reduce the radius parameter R, by one when a received broadcast transmission is forwarded; and

wherein the system is adapted to check information provided in the device table and the broadcast table so as to report to a device of the plurality of wirelessly interconnected devices initiating a new message, a maximum repetition number, Rmax, representative of the number of hops which was necessary to transmit the message to each device of the plurality of wirelessly interconnected devices, wherein the maximum repetition number Rmax is determined by the system using a broadcast storm as a number of repetitions necessary to reach every device in the network; and

wherein the system is adapted to;

search for a message with the shortest radius parameter R, in the broadcast table if a status report message is generated,

extract a sending address of the message with the shortest radius parameter, and

send the status report message to the extracted sending address using a unicast transmission.

11. A method of controlling information broadcast in a wireless mesh network, the method comprising:

tracking which device has successfully relayed a broadcast transmission with at least one device table;

recording any new broadcast transmission that has been initiated by a device initiating a message or received from a neighboring device with at least one broadcast table; and

adding to a new broadcast transmission a radius parameter R, which indicates an allowed number of hops through said mesh network before the broadcast transmission is discarded, or reducing the radius parameter R, by one when a received broadcast transmission is forwarded, wherein each broadcast transmission includes the radius parameter R;

checking the recorded broadcast transmissions;

determining a maximum repetition number, Rmax, using a broadcast storm, wherein Rmax is representative of the number of hops which is necessary to transmit the messages in the broadcast storm to each device of a plurality of wirelessly interconnected devices,

determining and reporting to a device initiating a message, the maximum repetition number Rmax, and

wherein the device table includes a neighbor table for tracking which neighboring device, which is a device within a transmission or reception range of the device, has successfully relayed a broadcast transmission;

and wherein the at least one broadcast table includes a broadcast transaction table for keeping a record of any new broadcast transmission that has been initiated by the associated device or received from a neighboring device;

wherein the at least one device table includes,

a child table for tracking which child device, which is a device to which said device has transmitted a broadcast transmission, has successfully relayed the broadcast transmission;

and wherein the at least one broadcast table includes a broadcast listening table for keeping a record of any new broadcast transmission that has been received by a child device.

12. The method of claim 11 further comprising:

at a device initiating a new message;

receiving said reporting of maximum repetition number Rmax,

extracting from said reporting the maximum repetition number Rmax, and

selecting the largest value of extracted maximum repetition numbers as a calibration value to generate a radius parameter to be inserted into a broadcast transmission, said radius parameter being indicative of an allowed number of hops through said mesh network before the broadcast transmission is discarded.