System and method for efficient network-wide broadcast in a multi-hop wireless network using packet echos
A mesh network protocol, comprising: receiving a packet from a sender, identifying the sender, a prior sender, a flood mode, a time-to-live, and a sequence identifier; marking the recipient as critical if during a full flood period, the recipient is the same as the prior sender, and marking the recipient as non-critical if no packet is received with the recipient the same as the prior sender; rebroadcasting the packet, modified by updating sender with the recipient, and sender as prior sender, decrementing the time to live until expiration, and, the identity of the recipient is different from the identity of the prior sender in full flood mode; or the identity of the recipient is different from the prior sender, and the recipient is critical, in partial flood mode.
1. A mesh network communication method for operating a mesh network node, having a first state in which it is marked as not critical, and a second state in which it is marked as critical, comprising:
marking the mesh network node as critical, in response to a broadcasting of a flood packet, of a packet with an identifier of itself as a prior sender;
marking the mesh network node as non-critical upon failure to receive a packet with an identifier of itself as a prior sender during a period; and
employing the critical marking to selectively determine forwarding behavior for received non-flood packets,
wherein at least one of:
(1) the flood packet defines: an identity of a current sender mesh network node, an identity of a prior sender from which the flood packet was received, a flood mode indicator, a time-to-live, a sequence identifier, and an optional payload, the method further comprising selectively rebroadcasting a single instance of a received flood packet based on a comparison of the sequence identifier with prior sequence identifiers, modified by a replacement of the identity of the current sender with an identity of the mesh network node, and the prior sender with the current sender, and a decrement of the time to live, wherein the flood packet is rebroadcast by the mesh network node selectively dependent on whether the time to live is not expired, and the flood mode alternately indicates (a) a full flood mode and the sequence identifier is not present in a list of prior sequence identifiers, and (b) a partial flood mode, the sequence identifier is not present in the list of prior sequence identifiers, and the mesh network node is marked as critical; and
(2) each packet comprises an identity of the current sender, a criticality of the current sender, an identity of a prior sender, a time-to-live, and an optional payload, the method further comprising:
sending a packet from a current sender mesh network node;
determining whether retransmission of the packet is expected, based on at least a criticality of a neighboring mesh network node, and the time-to-live of the packet;
monitoring for re-transmission of the packet by the neighboring mesh network node within a time window;
determining whether re-transmission of the packet is expected before expiration of the time window;
determining whether retransmission of the packet is detected within the time window; and
resending the packet selectively dependent on whether re-transmission of the packet is expected before expiration of the time window, and whether retransmission of the packet is not detected within the time window.
2. The mesh network communication method according to claim 1 , further comprising broadcasting the flood packet from the mesh network node, comprising the identity of the mesh network node.
3. The mesh network communication method according to claim 1 , wherein the flood packet defines: the identity of a current sender mesh network node, the identity of the prior sender from which the flood packet was received, the flood mode indicator, the time-to-live, the sequence identifier, and the optional payload.
4. The mesh network communication method according to claim 3 , further comprising selectively rebroadcasting the single instance of the received flood packet based on the comparison of the sequence identifier with prior sequence identifiers, modified by the replacement of the identity of the current sender with the identity of the mesh network node, and the prior sender with the current sender, and the decrement of the time to live, wherein the flood packet is rebroadcast by the mesh network node selectively dependent on whether the time to live is not expired, and one of:
(a) the flood mode indicator indicates the full flood mode and the sequence identifier is not present in a list of prior sequence identifiers; and
(b) the flood mode indicator indicates the partial flood mode, the sequence identifier is not present in the list of prior sequence identifiers, and the mesh network node is marked as critical.
5. The mesh network communication method according to claim 1 , wherein each packet comprises an identity of the current sender, a criticality of the current sender, an identity of a prior sender, a time-to-live, and an optional payload,
further comprising:
sending a packet from a current sender mesh network node;
determining whether retransmission of the packet is expected, based on at least a criticality of a neighboring mesh network node, and the time-to-live of the packet;
monitoring for re-transmission of the packet by the neighboring mesh network node within a time window;
determining whether re-transmission of the packet is expected before expiration of the time window;
determining whether retransmission of the packet is detected within the time window; and
resending the packet selectively dependent on whether re-transmission of the packet is expected before expiration of the time window, and whether retransmission of the packet is not detected within the time window.
6. The mesh network communication method according to claim 5 , wherein said determining whether retransmission of the packet is expected, is based on whether the time-to-live of the sent packet is at least one, and whether the current sender mesh network node has at least one neighbor other than the prior sender that is critical.
7. A mesh network communication method, comprising:
transmitting by a sender mesh network node, a packet defining an identity of a current sender, an identity of a prior sender, a flood mode indicator, time-to-live data, a packet identifier, and an optional payload;
receiving the packet by other mesh network nodes by a receiving node;
marking the receiving node as critical selectively dependent on whether the flood mode indicator indicates a full flood mode corresponding to the first mode, and the receiving node is identified as the prior sender;
retransmitting a modified representation of the received packet unless:
the packet has already been transmitted by the receiving node based on analysis of the packet identifier;
the receiving node is marked as non-critical and the flood mode indicator indicates a non-full flood mode corresponding to the second mode; or
the time to live has decremented beyond a predetermined threshold;
the modified representation having updated time to live data, the identity of the sender becoming the identity of the prior sender, and an identity of the receiving node becoming the identity of the sender;
in a first mode, selectively the retransmission of each packet received by a respective node as a first modified packet, being further selectively dependent on whether the received packet has not been transmitted before by the respective node; and
in a second mode, determining whether the respective node is a critical link within the mesh network based on echoed packets received during the first mode, and the retransmission of each packet received by a node as a second modified packet, being further selectively dependent on whether the received packet does not originate from the respective node and the respective node is critical.
8. The method according to claim 7 , wherein the flood mode indicator is time-sensitive.
9. The method according to claim 7 , wherein marking the receiving node as critical selectively dependent on whether the flood mode indicator indicates the full flood mode and the receiving node is identified as the prior sender in a packet received within a time period.
10. The method according to claim 7 , wherein the full flood mode has a limited time.
11. The method according to claim 7 , wherein the modified representation comprises a decremented time to live counter, and the expiration of the time to live is dependent on a predetermined state of the counter.
12. The method according to claim 7 , wherein, in the full flood mode, the packet transmission is triggered by a timer.
13. The method according to claim 7 , wherein the flood is triggered by a received packet.
14. A mesh network node, comprising:
a radio frequency transceiver, configured to receive a flood packet from a current sender mesh network node, the flood packet comprising information defining an identity of the current sender, an identity of a prior sender from which the flood packet was received, a flood mode indicator, a time-to-live, and a sequence identifier, and an optional payload;
a memory configured to store a critical node indicator and a set of prior sequence identifiers of packets previously received;
an automated processor, configured to:
mark the critical node indicator as critical in the memory selectively dependent on whether during a period, the flood mode indicator is full flood mode, and the identity of the mesh network node is the same as the identity of the prior sender, and mark the critical node indicator as non-critical selectively dependent on whether during a period, the flood mode indicator is full flood mode, and no packet is received with the identity of the mesh network node the same as the identity of the prior sender;
selectively rebroadcast through the radio frequency transceiver, a single instance of the flood packet based on a comparison of the sequence identifier with the set of prior sequence identifiers, modified by a replacement of the identity of the current sender with an identity of the mesh network node, a replacement of the identity of the prior sender with an identity of the current sender, and a decrement of the time to live, wherein the flood packet is rebroadcast selectively dependent on whether the time to live is not expired, and:
(a) the flood mode indicator indicates a full flood mode and the sequence identifier is not present in a list of prior sequence identifiers; or
(b) the flood mode indicator indicates a partial flood mode, the sequence identifier is not present in the list of prior sequence identifiers, and the recipient is marked as critical.
15. The mesh network node according to claim 14 , wherein the flood mode indicator is time-sensitive.
16. The mesh network node according to claim 14 , wherein the full flood mode has a limited time.
17. The mesh network node according to claim 14 , wherein the automated processor is further configured to generate a transmission of a full flood packet through the radio frequency transceiver.
18. The mesh network node according to claim 17 , wherein the automated processor is further configured to generate the transmission triggered by a timer.
19. The mesh network node according to claim 17 , wherein the automated processor is further configured to generate the transmission triggered by a received packet.
20. The mesh network node according to claim 14 , wherein the flood packet having the flood mode indicator which indicates the full flood mode is rebroadcast periodically.