Multi-channel wireless broadcast protocol for a self-organizing network

• US 20050180356A1
• Filed: 12/10/2002
• Published: 08/18/2005
• Est. Priority Date: 10/01/2002
• Status: Abandoned Application

• Current Assignee: SYS Technologies (San Diego) (Kratos Defense & Security Solutions Incorporated)
• Original Assignee: Graviton, Inc. (Kratos Defense & Security Solutions Incorporated)
• Inventors: Wang, Weilin, Gillies, Donald W.
• Application Number:
  US10/316,621
• Publication Number:
  US 20050180356A1
• Time in Patent Office: Days
• US Class Current: 370/329
• CPC Class Codes: H04W 16/14 Spectrum sharing arrangements between different networks
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 74/00 Wireless channel access
• 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

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.

Claims

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.

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.

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.