Distributed ad hoc network protocol using synchronous shared beacon signaling

• US 8,385,322 B2
• Filed: 07/28/2008
• Issued: 02/26/2013
• 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., Carpenter, Paul R., Koleszar, Luke, Schmidt, Paul E.
• Primary Examiner(s): Chriss, Andrew
• Assistant Examiner(s): Cehic, Kenan
• Application Number:
  US12/670,280
• Publication Number:
  US 20100226342A1
• Time in Patent Office: 1,674 Days
• Field of Search: 370310-350, 370503-520, 455500-503, 455/507
• US Class Current: 370/350
• 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 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 an autonomously determined network Time Master node using synchronization packets identifying for each such packet the sending node'"'"'s cluster Time Master node ID number, sending node Time Rank, sending 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 in the network is identified by a node ID number and each node in a cluster has associated therewith a cluster Time Master node ID number, a cluster node Time Rank and a cluster node Time Sequence Number and wherein further for each cluster in the network a node ID number of a Time Master, a Time Rank, a Time Sequence, a timestamp and a node ID number of a Time Parent is stored in memory, 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 sending node to its neighbor nodes, wherein for each received synchronization packet at a neighbor node;

parsing data in each synchronization packet received;

determining based on the parsed data in each synchronization packet received whether the receiver'"'"'s configured operating channel matches that of the sender;

if not, processing the remainder of the received synchronization packet;

otherwise, determining second whether the receiving node is configured to synchronize to a known network gateway Time Master node;

if so, and the Time Master node ID number associated with the sending node is not the same as the known preconfigured network gateway Time Master node ID number, processing the remainder of the received synchronization packet;

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

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

otherwise, determining fourth if the cluster Time Master node ID number contained in the synchronization packet associated with the sending node is the same as the receiving node ID number;

if so, processing the remainder of the received synchronization packet;

otherwise, determining fifth if the Time Master node ID number contained in the synchronization packet associated with the sending node is equal to the known cluster Time Master node ID number associated with the receiving node;

if so, determining sixth if a sending node Time Sequence Number differs from the cluster Time Sequence Number associated with the receiving node;

 

if so, synchronizing the receiving node;

 

if not, determining seventh if a synchronization packet sending node ID number is the same as the node ID number of the Time Parent;

 

if so, processing the remainder of the received synchronization packet;

 

if not, determining eighth whether the sending node'"'"'s Time Rank is greater than the cluster node'"'"'s Time Rank plus one;

 

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

 

otherwise, processing the remainder of the received synchronization packet;

otherwise, if the Time Master node ID number contained in the synchronization packet associated with the sending node is not equal to the known cluster Time Master node ID number,

determining ninth if the sending node'"'"'s Time Master node ID number is less than a current cluster Time Master node ID number;

 

if so, synchronizing the receiving node with the sending node'"'"'s Time Master node;

 

otherwise, processing the remainder of the received synchronization packet.

2. The method of claim 1 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.

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

4. The method of claim 1 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 a new cluster;

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

determining second whether the receiving node ID number is the same as the receiving node'"'"'s preconfigured gateway ID number;

if so, designating the receiving node as a gateway node, assigning the time master ID number to that receiving node, updating media access control command frame Time Master data and processing the remainder of the received synchronization packet;

otherwise, determining third whether the Time Master node ID number of the sending node is the same as the receiving node'"'"'s preconfigured gateway ID number;

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

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

if so, designating the receiving node as the Time Master;

otherwise, designating the sending node as the Time Master; and

returning to the placing.