Multi-channel wireless broadcast protocol for a self-organizing network
The disclosed embodiments of a media access control (MAC) scheme are devised to solve the hidden node problem for channel-hopping broadcast operations in wireless communication networks. The multi-channel broadcast MAC may be adapted to sense and hop around channel interference, and to perform concurrent sensing and load balancing across a set of channels. A multi-hop routing engine using this packet broadcast operator may allow a plurality of network nodes to organize themselves reliably into a communications network. By routing packets around the troubled areas, the routing engine may heal nodal and link failures. When a node changes location, the routing engine may reorganize the network topology automatically and restore the connectivity between communicating peers.
1 . A method of selecting an idle communication channel for broadcast by a first node in a network, the network including a plurality of nodes having a transmitter and a receiver, the method comprising:
a) selecting one of a plurality of predetermined channels;
b) detecting, by the receiver of the first node, the presence or absence of a carrier signal on the selected channel;
c) determining whether the selected channel is available for communication between the first node and a second node; and
d) repeating steps a) through c) when the determining step indicates unavailability of the selected channel.
2 . The method according to claim 1 , wherein the determining includes sensing RF power by the receiver of the first node.
3 . A method of selecting an idle communication channel for unicast by a first node for communication with a second node in a network, each node having a transmitter and a receiver, the method comprising:
a) selecting an integer value between one and n, n being a positive integer less than or equal to a number of available unicast channels;
b) selecting one of the available channels based on the selected integer value and a hash value corresponding to the second node;
c) determining whether the selected channel is open for communication between the first node and the second node; and
e) repeating steps a) through c) when the determining step indicates the selected channel is not open.
4 . The method according to claim 3 , wherein the selecting of the integer value is random to facilitate load balancing.
5 . The method according to claim 3 , wherein the determining includes sensing RF power by the receiver of the first node.
6 . The method according to claim 3 , wherein the determining whether the selected channel is open includes performing a reception scan.
7 . The method according to claim 6 , wherein the reception scan determines whether the selected channel is being used for communication by at least one other node in the network.
8 . A method of transmitting data by a first node to a second node in a network, comprising:
a) selecting, according to a prioritization, an available broadcast or unicast channel from a plurality of predetermined channels;
b) performing a broadcast handshake between the first node and the second node;
c) transmitting a “broadcast extension” message for a predetermined length of time if the selected channel is a broadcast channel, the “broadcast extension” message being adapted to alert other nodes in the network of an upcoming transmission;
d) transmitting data packets on the selected channel for receipt by the second node; and
e) receiving an acknowledgement signal from the second node, the acknowledgement signal being either a positive acknowledgement or a negative acknowledgement, the positive acknowledgement being indicative of a successful receipt of data packets by the second node.
9 . The method according to claim 8 , further comprising:
repeating steps d) and e) if the acknowledgement signal is a negative acknowledgement until the acknowledgement signal is a positive acknowledgement.
10 . The method according to claim 8 , wherein the broadcast handshake includes:
broadcasting a signal indicative of readiness to transmit data packets from the first node; and
receiving a signal indicative of readiness to receive for the second node.
11 . The method according to claim 8 , further comprising:
transmitting a carrier signal during at least one of the performing a broadcast handshake, transmitting a “broadcast extension” message, and the transmitting of the data packets.
12 . The method according to claim 8 , further comprising:
generating a carrier signal by the second node and by other nodes in the network receiving the “broadcast extension” message until a start of the transmitting of data packets, the carrier signal being detectable by all nodes in the network.
13 . The method according to claim 8 , wherein the transmitting data packets includes:
forming message frames, each frame including at least the identities of an original source node, an original destination node, a local source node, and a local destination node.
14 . A method of organizing a network having a plurality of nodes, comprising:
a) broadcasting a synchronization packet from a root node, the packet indicating the root node as the originating node and having a source node field for an address of a source node;
b) receiving the synchronization packet by a non-root node;
c) determining whether the received synchronization packet is a duplicate of a previously received packet;
d) discarding the synchronization packet if step c) determines it is a duplicate;
e) updating, if step c) determines the synchronization packet is not a duplicate, an entry in a routing table at the non-root node to indicate the address in the source node field as the path to the root node;
f) updating the source node field in the synchronization packet to indicate the non-root node as the source node; and
g) re-broadcasting of the synchronization packet by the non-root node.
15 . The method according to claim 14 , wherein each entry in the routing table includes identities of an original destination node and a corresponding next-hop node.
16 . A method of organizing a network having a plurality of nodes, comprising:
a) receiving a packet from a source node at an intermediate node, the packet including an address for the source node, an originating node and a destination node;
b) updating an entry for the originating node in a routing table at the intermediate node to indicate the address of the source node as the path to the originating node;
f) updating the address for source node in the packet to indicate the intermediate node as the source node; and
g) transmitting the packet to another node, the another node being determined according to an entry in the routing table for the destination node.
17 . The method according to claim 14 , wherein each entry in the routing table includes identities of an original source node and a corresponding next-hop node.