SCHEDULING METHOD AND SCHEDULING INFORMATION SYNCHRONIZING METHOD IN WIRELESS AD HOC NETWORK

• US 20100268825A1
• Filed: 11/27/2009
• Published: 10/21/2010
• Est. Priority Date: 04/16/2009
• Status: Active Grant

• Current Assignee: Electronics and Telecommunications Research Institute, Industry-Academic Cooperation Foundation Yonsei University
• Original Assignee: Electronics and Telecommunications Research Institute, Industry Academic Cooperation Foundation
• Inventors: Kim, Min-seok, Chung, Jong-moon, JEONG, Wun-cheol, Jin, Ki-yong, Choi, Won-ju, Chae, Jong-suk, Joo, Seong-soon
• Granted Patent: US 8,458,266 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365
• CPC Class Codes: H04W 52/0216 using a pre-established activity schedule, e.g. traffic indication frame
• CPC Class Codes: H04W 52/0219 where the power saving management affects multiple terminals
• CPC Class Codes: H04W 72/04 Wireless resource allocation
• CPC Class Codes: H04W 72/12 Wireless traffic scheduling
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A decentralized scheduling method in a wireless ad hoc network is provided which includes grouping nodes in the network cluster by cluster, determining a cluster head of each cluster, and sequentially performing scheduling cluster by cluster. Accordingly, it is possible to provide an efficient cluster-based scheduling method which is quickly adapt to changes and reduces power consumption.

Claims

1. A scheduling method of nodes in a wireless ad hoc network, comprising:

forming a plurality of clusters including at least one node within the network;

selecting a cluster head among nodes included in each of the clusters; and

allocating, by the selected cluster head, resources to nodes cluster by cluster.

2. The scheduling method of claim 1, further comprising, after completing the resource allocation, transmitting, by the cluster head, a cluster head message including scheduling information to other nodes within a cluster which the cluster head belongs to.

3. The scheduling method of claim 2, further comprising:

transmitting, by at least one edge node of the cluster in which the resource allocation has been completed, the scheduling information to an edge node of a cluster which is subject to a next scheduling; and

transmitting, by the edge node of the cluster which is subject to the next scheduling, the scheduling information to a cluster head of the cluster,

wherein the cluster head of the cluster which is subject to the next scheduling reflects the scheduling information to resource allocation to other nodes within the cluster.

4. The scheduling method of claim 3, wherein transmitting, by the edge node of the cluster which is subject to the next scheduling, the scheduling information to a cluster head of the cluster comprises transmitting an edge node message including a hop count to count a number of intermediate nodes between the edge node and the cluster head of the cluster which the edge node belongs to.

5. The scheduling method of claim 4, wherein the cluster head message comprises a broadcast hop count which is a largest hop count received from the edge node.

6. The scheduling method of claim 5, wherein the cluster head message further comprises a remaining hop count to count a number of transmission hops of the header message from the cluster head.

7. The scheduling method of claim 5, wherein the cluster head message comprises a flag to indicate if the cluster head message is sent to nodes within a corresponding cluster or to nodes within the network.

8. The scheduling method of claim 2, wherein after completing the resource allocation, if the scheduling information is changed, the cluster head transmits a header message including the changed scheduling information to other nodes within a corresponding cluster.

9. The scheduling method of claim 1, wherein selecting the cluster head comprises selecting a node having a most number of links within a cluster.

10. The scheduling method of claim 1, further comprising, after selecting the cluster head, sequentially assigning IDs to the clusters in order of a cluster having more to less nodes,

wherein allocating the resources to nodes cluster by cluster comprises sequentially allocating the resources on an ID basis.

11. The scheduling method of claim 1, further comprising, after sequentially assigning the IDs to the clusters, matching frame lengths of scheduling information of the clusters whose scheduling has been completed.

12. The scheduling method of claim 11, further comprising, if a frame length has been increased in matching the frame lengths of scheduling information, further performing, by the cluster head, scheduling on the increased frame area.

13. The scheduling method of claim 1, wherein allocating the resources to nodes cluster by cluster comprises performing scheduling by broadcast scheduling algorithm (BSA).

14. A synchronizing method of changed schedule information within a network with a plurality of distributed clusters, comprising:

receiving, by a cluster head, hop counts for nodes within a corresponding cluster;

setting a largest of the hop counts as a broadcast hop count;

determining a synchronized change frame number larger than a largest number of hops within the network to simultaneously apply a frame length of the changed schedule information within the network; and

transmitting, by the cluster head, a cluster head message including the synchronized change frame number and the frame length of the changed scheduling information to nodes within a cluster.

15. The synchronizing method of claim 14, wherein the synchronized change frame number is a value which counts down a frame length change time while decreasing one by one every frame cycle.

16. The synchronizing method of claim 15, wherein a node receiving the header message applies the frame length of the changed schedule information at the same time when the synchronized change frame number becomes zero (0).

17. The synchronizing method of claim 14, wherein the largest number of hops within the network is equal to twice a sum of broadcast hop counts of clusters within the network.