Method for nodes in a multi-hop wireless network to acquire and maintain synchronization with a master node

• US 6,751,248 B1
• Filed: 12/07/1999
• Issued: 06/15/2004
• Est. Priority Date: 12/07/1999
• Status: Expired due to Fees

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Tan, Narciso Lau
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): WILLIAMS, LAWRENCE B
• Application Number:
  US09/455,666
• Time in Patent Office: 1,652 Days
• Field of Search: 370/338, 370/401, 375/132, 375/256, 375/131
• US Class Current: 375/132
• CPC Class Codes: H04B 7/269 Master/slave synchronisation
• CPC Class Codes: H04W 56/0015 one node acting as a reference for the others
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

The present invention is directed to a method of selecting nodes in a multi-hop network having a combined coverage that reaches all the nodes in the network. These nodes called parent nodes, together with the root broadcast synchronization information regularly to the rest of the network. As part of the selection process, the parent nodes that would not interfere with each other are identified and then scheduled to broadcast synchronization information at the same time. Further, a time division structure can be used to control the access of these parent nodes to a common communication channel, resulting in the efficient use of the bandwidth available. The time division structure also ensures that each node receives regular synchronization information so that it can acquire and maintain synchronization with the root. However, other structures are also contemplated such as frequency division, code division and hybrids. Further, minimal coordination between the nodes is required to implement this method and timing structure.

Claims

1. A method for transmitting synchronization information in a multi-hop wireless network, the method comprising the steps of:

selecting parent nodes in the network to transmit synchronization information to children nodes; and

transmitting the synchronization information from the parent nodes in a number of channels, wherein the parent nodes being a predetermined number of hops from each other transmit in one channel;

wherein the selecting of parent nodes includes;

(i) receiving by a particular child node a first clock packet from a particular node identifying the particular child node as its own child node;

(ii) entering an initialization phase wherein the particular child node sets a timer for a predetermined period of time T and listens for clock packets from other nodes that seek to be selected as a parent node for the particular child node;

(iii) upon expiration of the predetermined period of time T the particular child node determining which of the parent nodes has a smallest hop number in its clock packet, and selecting as a parent node the node having the smallest hop number; and

(iv) the particular child node transmitting a packet to the node selected in step (iii) to inform the node that it has been selected by the particular child node to be the parent node of the particular child node.

2. The method of claim 1, wherein the parent nodes include at least one node from each hop in the network to transmit the synchronization information to at least one of-the children nodes in an adjacent hop.

3. The method of claim 1, wherein one of the parent nodes is a root node providing the synchronization information and having a smallest possible hop number in its clock packet.

4. The method of claim 1, wherein further comprising the steps of:

monitoring a hop number from subsequent clock packets received by the particular child node; and

performing sub-steps (ii), (iii) and (iv) by the particular child node to reschedule a transmission of clock packets if the particular child node receives a clock packet with a smaller hop number than the parent node of the particular child node.

5. The method of claim 1, wherein a minimum number of parent nodes are selected having a combined coverage to reach all nodes of the network.

6. The method of claim 1, wherein the channels are selected from a group consisting of time division channels, frequency division channels, code division channels and hybrids thereof;

and

wherein parent nodes having a difference in respective hop numbers of at least three hops are permitted to transmit at a same time on a same channel.

7. The method of claim 1, wherein the parent nodes include multiple nodes from one hop and the multiple nodes from one hop transmit in a different sub-division of one of the channels.

8. A method for transmitting synchronization information in a multi-hop wireless network, the method comprising the steps of:

selecting parent nodes in the network to transmit synchronization information to children nodes;

dividing the parent nodes into a number of groups, wherein each of the groups include parent nodes being a predetermined number of hops from each other; and

transmitting the synchronization information from the parent nodes in a number of channels, wherein each of the groups corresponds to one of the channels_wherein

wherein the selecting of parent nodes includes;

(i) receiving by a particular child node a first clock packet from a particular node identifying the particular child node as its own child node;

(ii) entering an initialization phase wherein the particular child node sets a timer for a predetermined period of time T and listens for clock packets from other nodes that seek to be selected as a parent node for the particular child node;

(iii) upon expiration of the predetermined period of time T the particular child node determining which of the parent nodes has a smallest hop number in its clock packet, and selecting as a parent node the node having the smallest hop number; and

(iv) the particular child node transmitting a packet to the node selected in step (iii) to inform the node that it has been selected by the particular child node to be the parent node of the particular child node.

9. The method of claim 8, wherein the parent nodes include at least one node from each hop in the network to transmit the synchronization information to at least one of the children nodes in an adjacent hop.

10. The method of claim 8, wherein one of the parent nodes is a root node providing the synchronization information and having a smallest possible hop number in its clock packet.

11. The method of claim 8, wherein the predetermined number of hops is at least three hops, and said method further comprising the steps of:

monitoring a hop number from subsequent clock packets received by the particular child node; and

performing sub-steps (ii), (iii) and (iv) by the particular child node to reschedule a transmission of clock packets if the particular child node receives a clock packet with a smaller hop number than the parent node of the particular child node.

12. The method of claim 8, wherein the synchronization information is transmitted in a packet including a hop number of the parent nodes and a list of the children nodes of the parent nodes transmitting the packet.