Distributed Ad Hoc Network Protocol Using Synchronous Shared Beacon Signaling

• US 20100226342A1
• Filed: 07/28/2008
• Published: 09/09/2010
• Est. Priority Date: 07/30/2007
• Status: Active Grant

• Current Assignee: Innovative Wireless Technologies Inc.
• Original Assignee: Innovative Wireless Technologies Inc.
• Inventors: Colling, Kent D., Schmidt, Paul E., Carpenter, Paul R., Koleszar, Luke
• Granted Patent: US 8,385,322 B2
• Time in Patent Office: Days
• US Class Current: 370/336
• CPC Class Codes: H04W 56/002 Mutual synchronization
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 92/18 between terminal devices

Abstract

A method for forming a protocol structure for use in an ad hoc, distributed, scaleable wireless sensor node network which enables nodes to join the network autonomously without there being a designated, permanent central time reference and for enabling such nodes to synchronize timing with each other and with other nodes in the network. The method involves discovering the active channel changing sequence used by the network, synchronizing communications of a new node with the remainder of the nodes in the network and scanning communications channels to detect merging clusters of nodes.

Claims

1. A method for providing an ad hoc, distributed, scaleable wireless sensor node network with a protocol structure enabling the nodes in the network and new nodes joining the network to synchronize with each other autonomously comprising:

providing at least one superframe time interval within the protocol structure, each of which is of equal duration;

further providing at least one time slot cycle in each superframe interval;

assigning to each time slot cycle at least one activity selected from the group consisting of periodic active data exchange, extended data exchange, guaranteed time slots for dedicated bandwidth and quality of service, pilot beacon and scan intervals;

dividing each time slot cycle into at least one of five types of time slot intervals selected from the group consisting of guard, carrier sense minislot, packet transfer, sync packet appending and packet acknowledgement window; and

adding inter-frame spacing between each type of time slot interval;

wherein a pilot beacon activity is randomly assigned to at least one time slot cycle for providing a known network synchronizing reference and a continuous update mechanism for channel control.

2. The method of claim 1 wherein sync packet appending intervals are inserted opportunistically between said packet transfer intervals and said packet acknowledgement window intervals.

3. The method of claim 1 wherein said superframe time interval defines sleep time and controls latency throughout the network.

4. The method of claim 1 wherein said superframe time interval is responsive to packet forwarding.

5. The method of claim 1 wherein said superframe time interval controls power consumption.

6. A method for enabling new nodes, neighbor nodes and clusters of nodes, some of which may be mobile, to join an ad hoc, distributed, scaleable wireless sensor node network without a central time reference, wherein each node has its own time metric and slot alignment, using spread spectrum communications on a plurality of channels and a protocol structure comprised of at least one configurable superframe time interval, each of which intervals is of equal duration and each of which has at least one active time slot cycle to which at least one pilot beacon interval is randomly assigned for providing pilot beacons having a known network synchronizing reference and a continuous update mechanism for channel control comprising:

discovering the active channel changing sequence used by the spread spectrum communications system;

synchronizing the communications of the new node with the remainder of the nodes in the network; and

randomly scanning communications channels to detect merging clusters of nodes.

7. The method of claim 6 wherein the active channel changing sequence type used is frequency hopping and discovering further comprises:

determining first a scan mode;

setting first a configured scan duration period, configured dwell time parameter, a noise floor average, a scan priority, a blackball count, a blackball count limit, a reinstatement count and a reinstatement count level;

determining second if the scan duration period is complete;

if so, storing the identity of the last channel scanned and exiting the method;

if not, selecting a next channel to be scanned;

testing first whether the blackball count for the selected channel exceeds the blackball count limit;

if so, further comparing the blackball count is further compared to the reinstatement count and, if less than the reinstatement count, incrementing the blackball count by one and returning to selecting;

otherwise, reinstating the present channel if it has been designated as a potential interfering channel and decrementing the blackball count by one;

setting second a received signal strength indicator threshold indicating a strength difference between a received signal and the noise floor average, a minimum threshold level and a threshold level increment amount;

initiating a scan;

waiting for expiration of the dwell time;

reading a received channel energy level;

determining third if the received channel energy level exceeds the indicator threshold;

if not, testing second whether the threshold is at the minimum threshold level;

if so, returning to determining second;

otherwise, reducing the threshold by one level and returning to determining second;

further incrementing the blackball count by one for the present channel;

listening in receiver mode to acquire network synchronization;

determining fourth if good synchronization has been achieved;

if not, testing third the blackball count to determine if it exceeds the blackball count limit;

if not, yet further incrementing the minimum threshold level by the threshold level increment amount and returning to determining second;

if so, designating the present channel as a potential interfering channel and returning to determining second; and

otherwise, decrementing the blackball count for the present channel by one, storing the identity of the last channel with good synchronization and returning to determining second.

8. The method of claim 7 wherein the scan mode is one selected from the group consisting of initial long scan, fixed channel long scan or randomized merge scan.

9. The method of claim 6 wherein the active channel changing sequence type used is direct sequence.

10. The method of claim 6 wherein for each node synchronizing further comprises:

performing a continuous long scan over a minimum of two pilot beacon intervals to search for active neighbor nodes;

if neighbor nodes are found,

responding to discovered pilot beacons during the cluster active time slot cycle;

scheduling a contention access period to inform neighbor nodes of the existence of new nodes; and

synchronizing the slot alignment of the new node to the highest seniority time metric of existing nodes and assuming operation within a piconet;

if no neighbor nodes are not found,

broadcasting its own pilot beacon during a pilot beacon interval; and

adopting its own search schedule;

returning to performing

11. The method of claim 6 wherein randomly scanning further comprises:

if a mobile cluster is found and the clock metric of that mobile cluster is junior to that of the cluster of the scanning node, propagating the clock metric from the more senior cluster through the junior cluster; and

if a mobile cluster is found and the clock metric of that mobile cluster is senior to that of the cluster of the scanning node, assuming an updated slightly degraded time metric relative to the newly discovered senior time metric.

12. The method of claim 10 wherein the frequency of pilot beacon intervals is configurable.

13. The method of claim 10 wherein nodes participate in every active time slot interval in order to maintain slot synchronization.

14. A method for autonomous wireless sensor nodes in an ad hoc, distributed scaleable wireless sensor node network with nodes having neighbor nodes, some of which may be gateway nodes, orphan nodes and clusters of nodes, to synchronize timing with each other within time slots under the control of a network Time Master node using synchronization packets identifying the cluster Time Master node, node Time Rank, node Time Sequence Number, sending node source identification, packet transmission time, slot alignment offset, slot number, operating channel number and time synchronization data wherein each node is identified by an ID number comprising:

initially designating all nodes as Time Master nodes;

placing all nodes in a wait state to listen for synchronization packets;

transmitting synchronization packets from one sender node to its neighbor nodes;

parsing data in each synchronization packet received at a neighbor node;

determining first for each receiving node whether the receiver'"'"'s configured operating channel matches that of the sender;

if not, jumping to processing;

otherwise, determining second whether the receiving node is configured to synchronize to a known gateway time master;

if so, and the time master ID of the sending node is not the ID of the receiving node, jumping to processing;

otherwise, determining third if the receiving node is an orphan node;

if so, synchronizing the sending and the receiving node and returning to placing;

otherwise, determining fourth if the time master ID and the receiving node ID are equal;

if so, jumping to processing;

otherwise, determining fifth if the sending time master ID number is equal to the known cluster time master ID number of the receiving node;

if so, determining sixth if the packet time sequence differs from the cluster time sequence;

if so, synchronizing the receiving node;

if not, determining seventh if the packet sending source is the same as the time parent;

if so, jumping to processing;

if not, determining eighth whether the packet time rank is greater than the cluster time rank plus one;

 

if so, synchronizing the receiving node with the source node closer to the time master node;

 

otherwise, jumping to processing;

otherwise, determining if the new time master ID from the sending node is less than the current cluster time master ID;

if so, synchronizing to the new time master ID and returning to placing; and

processing the remainder of the received packet normally.

15. The method of claim 14 wherein a dedicated network gateway is part of the distributed network and the gateway node having the highest seniority metric is designated as Time Master of the network.

16. The method of claim 14 wherein transmitting occurs either during designated periodic pilot beacon time slots or following receipt of a data packet in a time slot.

17. The method of claim 14 wherein synchronizing further comprises:

determining first whether the receiving node is an orphan;

if not, transmitting a cluster departure packet prior to adjusting synchronization to the new cluster;

otherwise, adjusting the time slot offset and the channel hopping pattern to match that of the sender node;

determining second whether the receiving node ID is the same as the configuration gateway ID;

if so, designating the receiving node as the gateway node, assigning the time master ID to that receiving node, updating the media access control command frame time master data and jumping to processing;

otherwise, determining third whether the sending node time master ID is the same as the configuration gateway ID;

if so, designating the sending node as the gateway and updating the time metrics of the receiver node;

otherwise, determining fourth whether the receiving node ID is less than the sending node ID;

if so, designating the receiving node as the time master;

otherwise, designating the sending node as the time master; and

returning to placing.