Maintenance of time slot usage indicators and self-organizing networking

• US 9,351,301 B2
• Filed: 08/15/2013
• Issued: 05/24/2016
• Est. Priority Date: 08/16/2012
• Status: Active Grant

• Current Assignee: Daniel Chonghwan Lee, Ehsan Seyedin, Eric James Yun Loong Lee
• Original Assignee: Daniel Chonghwan Lee
• Inventors: Lee, Eric James Yun Loong, Seyedin, Ehsan, Lee, Daniel Chonghwan
• Primary Examiner(s): FOUD, HICHAM B
• Application Number:
  US13/968,425
• Publication Number:
  US 20150049644A1
• Time in Patent Office: 1,013 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04B 7/26 at least one of which is mobile
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

Provided are methods by which multiple devices self-form a communication network and self-coordinate their access to communication media. In these methods, an individual node maintains its knowledge of other nodes in its vicinity and knowledge of those nodes'"'"' scheduled activities to an adequate degree of details. Such knowledge can be obtained by receiving control signals from nodes that are within the range of wireless communication. Examples of such knowledge include the identities of the nodes in the vicinity, the nodes'"'"' scheduled times of control message transmission and/or reception, the nodes'"'"' scheduled times of application data transmission and/or reception, etc. Such knowledge can be embodied in the form of a memory module of a computing device.

Claims

1. A method for communicating using a network including a plurality of devices, comprising:

partitioning medium access time into a series of superframes and partitioning each superframe into time slots;

scheduling by each of said devices its transmission and reception in the time slots of the superframe;

maintaining by each of said devices its neighborhood map, a neighborhood map being an ordered set of indicators corresponding to the time slots of the superframe, wherein the indicator distinguishes among the device'"'"'s scheduled use of the corresponding time slot for a control packet transmission or reception, the device'"'"'s scheduled use of the corresponding time slot for a data packet transmission or reception, and no scheduled use of the corresponding time slot by the device, and the indicator indicates whether the device is allowed to transmit in the corresponding time slot;

transmitting by each of said devices a packet containing said each device'"'"'s neighborhood map recurrently;

updating recurrently by each of said devices its neighborhood map on the basis of information available to the device, wherein information available to the device includes the device'"'"'s schedule of time slot uses, one or a plurality of neighborhood maps received from one or a plurality of other devices, and one or a plurality of control packets received from one or a plurality of other devices; and

updating by each of said devices its schedule of packet transmission and reception on the basis of information available to the device, wherein information available to the device includes the device'"'"'s transmission need, the device'"'"'s neighborhood map, and one or a plurality of control packets received from one or plurality of other devices.

2. The method according to claim 1, wherein said each device designates one or a plurality of time slots in the superframe for transmitting a packet containing its neighborhood map.

3. The method according to claim 1, wherein each indicator in the neighborhood map of said each device takes one of five values corresponding to 0, 1, 2, 3, 4, and said maintaining of the neighborhood map includes:

setting the indicator to the value corresponding to 4 if said indicator'"'"'s corresponding time slot is scheduled for said each device'"'"'s transmitting or receiving a control packet;

setting the indicator to the value corresponding to 2 if said indicator'"'"'s corresponding time slot is scheduled for said each device'"'"'s transmitting or receiving a data packet; and

setting the indicator to the value corresponding to 0 at the beginning of the medium access time.

4. The method according to claim 3, wherein said each device'"'"'s updating its neighborhood map includes:

updating said each device'"'"'s ith indicator to the value corresponding to 3 if said each device'"'"'s ith indicator has a current value corresponding to a number less than 3 and said each device receives from another device a neighborhood map in which the ith indicator has the value corresponding to 4;

updating said each device'"'"'s ith indicator to the value corresponding to 1 if said each device'"'"'s ith indicator has a current value corresponding to 0 and said each device receives from another device a neighborhood map in which the ith indicator has the value corresponding to 3; and

updating said each device'"'"'s ith indicator to the value corresponding to 1 if said each device'"'"'s ith indicator has a current value corresponding to 0 and said each device receives from another device a neighborhood map in which the ith indicator has the value corresponding to 2.

5. The method according to claim 1, wherein said each device detects a conflict on the basis of information available to the device, wherein the information available to the device includes its neighborhood map or a list of neighboring nodes and another device'"'"'s neighborhood map received, wherein said each device resolves the detected conflict by modifying its transmission schedule and neighborhood map.

6. The method according to claim 1, wherein the devices form a tree topology and each data packet is routed from its source to destination through the path in the tree topology.

7. The method according to claim 1, further comprising

forming by said devices a tree topology including one root node;

sending by each non-root node data packets originated from said each non-root node to said each non-root node'"'"'s parent node, wherein said each non-root node'"'"'s parent node is defined as the node that is one hop closer to the root node than said each node in said tree topology; and

forwarding by each non-root node data packets received from one or a plurality of said each non-root node'"'"'s child nodes to said each non-root node'"'"'s parent node, wherein a child node of said each non-root node is defined as a node that is one hop farther from the root node than said non-root node in said tree topology.

8. The method according to claim 7, wherein said each device designates one or a plurality of time slots in the superframe for transmitting a packet containing its neighborhood map.

9. The method according to claim 8, wherein said each node designates one or a plurality of time slots for receiving a control packet from its child nodes or from nodes that are to be joined to said network, and each non-root node designates one or a plurality of time slots for receiving a control packet from its parent node.

10. The method according to claim 9, wherein scheduling of data packet transmission from a non-root node to its parent comprises:

selecting by said non-root node one or a plurality of proposed time slots for transmission to its parent;

sending by said non-root node to its parent a control packet containing the list of said proposed time slots during said parent'"'"'s designated time slot for receiving a control packet from said parent'"'"'s child nodes;

selecting by said parent node from said list of proposed time slots a set of permitted time slots; and

sending by said parent node to said non-root node a control packet containing the list of said permitted time slots during said non-root node'"'"'s designated time slot for receiving a control packet from said non-root node'"'"'s parent.

11. The method according to claim 10, wherein each indicator in the neighborhood map of said each device takes one of five values corresponding to 0, 1, 2, 3, 4, and said maintaining of the neighborhood map includes:

setting the indicator to the value corresponding to 4 if said indicator'"'"'s corresponding time slot is scheduled for said each device'"'"'s transmitting or receiving a control packet;

setting the indicator to the value corresponding to 2 if said indicator'"'"'s corresponding time slot is scheduled for said each device'"'"'s transmitting or receiving a data packet; and

setting the indicator to the value corresponding to 0 at the beginning of the medium access time.

12. The method according to claim 11, wherein said each device'"'"'s updating its neighborhood map includes:

updating said each device'"'"'s ith indicator to the value corresponding to 3 if said each device'"'"'s ith indicator has a current value corresponding to a number less than 3 and said each device receives from another device a neighborhood map in which the ith indicator has the value corresponding to 4;

updating said each device'"'"'s ith indicator to the value corresponding to 1 if said each device'"'"'s ith indicator has a current value corresponding to 0 and said each device receives from another device a neighborhood map in which the ith indicator has the value corresponding to 3; and

updating said each device'"'"'s ith indicator to the value corresponding to 1 if said each device'"'"'s ith indicator has a current value corresponding to 0 and said each device receives from another device a neighborhood map in which the ith indicator has the value corresponding to 2.

13. A network including a plurality of devices configured to

partition medium access time into a series of superframes and partition each superframe into time slots

schedule the devices'"'"' transmission and reception in the time slots of the superframe;

maintain neighborhood maps associated with individual devices, a neighborhood map being an ordered set of indicators corresponding to the time slots of the superframe, wherein the indicator of the neighborhood map distinguishes among the associated device'"'"'s scheduled use of the corresponding time slot for a control packet transmission or reception, the associated device'"'"'s scheduled use of the corresponding time slot for a data packet transmission or reception, and no scheduled use of the corresponding time slot by the associated device, and the indicator indicates whether the associated device is allowed to transmit in the corresponding time slot;

transmit packets containing individual devices'"'"' neighborhood maps recurrently;

update recurrently the neighborhood maps associated with individual devices on the basis of information available to the individual devices, wherein information available to an individual device includes the device'"'"'s schedule of time slot uses, one or a plurality of neighborhood maps received from one or a plurality of other devices, and one or a plurality of control packets received from one or a plurality of other devices; and

update individual devices'"'"' schedule of packet transmission and reception on the basis of information available to the individual devices, wherein information available to an individual node includes the device'"'"'s transmission need, the device'"'"'s neighborhood map, and one or a plurality of control packets received from one or plurality of other devices.

14. A network including a plurality of devices as in claim 13, wherein each of said devices designates one or a plurality of time slots in the superframe for transmitting a packet containing said each device'"'"'s neighborhood map.

15. A network including a plurality of devices as in claim 13, wherein each indicator in each neighborhood map takes one of five values corresponding to 0, 1, 2, 3, 4, and maintaining of a neighborhood map includes:

setting the indicator to the value corresponding to 4 if said indicator'"'"'s corresponding time slot is scheduled for the associated device'"'"'s transmitting or receiving a control packet;

setting the indicator to the value corresponding to 2 if said indicator'"'"'s corresponding time slot is scheduled for the associated device'"'"'s transmitting or receiving a data packet; and

setting the indicator to the value corresponding to 0 at the beginning of the medium access time.

16. A network including a plurality of devices as in claim 13, wherein said devices form a tree topology and each data packet is routed from its source to destination through the path in the tree topology.

17. A network including a plurality of devices as in claim 13, wherein

devices form a tree topology including one root node;

wherein each non-root node sends data packets originated from said each non-root node to said each non-root node'"'"'s parent node, wherein said each non-root node'"'"'s parent node is defined as the node that is one hop closer to the root node than said each node in said tree topology;

wherein each non-root node forwards data packets received from one or a plurality of said each non-root node'"'"'s child nodes to said each non-root node'"'"'s parent node, wherein a child node of said each non-root node is defined as a node that is one hop farther from the root node than said non-root node in said tree topology.