Maintenance of time slot usage indicators and self-organizing wireless networking

• US 20150049644A1
• Filed: 08/15/2013
• Published: 02/19/2015
• Est. Priority Date: 08/16/2012
• Status: Active Grant

• Current Assignee: Daniel Chonghwan Lee
• Original Assignee: Daniel Chonghwan Lee
• Inventors: Lee, Daniel Chonghwan
• Granted Patent: US 9,351,301 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• 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 wireless 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. The presented methods also provide a procedure by which an individual node maintains its knowledge of the scheduled signal transmission and/or reception activities, or an estimate or prediction of the scheduled transmission and/or reception activities, of other nodes that are not within the individual node'"'"'s signal-reachable range.

Claims

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

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

each device scheduling its transmission and reception in the time slots of the superframe;

each device maintaining 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;

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

each device recurrently updating its neighborhood map on the basis of said each device'"'"'s new 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

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

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 on the basis of its neighborhood map or a list of neighboring nodes and another device'"'"'s neighborhood map received a conflict and 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:

devices forming a tree topology including one root node;

each non-root node sending 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;

each non-root node forwarding 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 wireless 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:

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

said non-root node sending 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;

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

said parent node sending 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 wireless network including a plurality of devices, wherein communication takes place according to the method according to claim 1.

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

15. A wireless network including a plurality of devices as in claim 13, 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.

16. A wireless network including a plurality of devices as in claim 13, wherein 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 wireless network including a plurality of devices as in claim 13, wherein said communication method further includes:

devices forming a tree topology including one root node;

each non-root node sending 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;

each non-root node forwarding 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.