Scheduling method and scheduling information synchronizing method in wireless ad hoc network

• US 8,458,266 B2
• Filed: 11/27/2009
• Issued: 06/04/2013
• Est. Priority Date: 04/16/2009
• Status: Expired due to Fees

• 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: Chung, Jong-moon, Choi, Won-ju, Jin, Ki-yong, Kim, Min-seok, Joo, Seong-soon, Chae, Jong-suk, Jeong, Wun-cheol
• Primary Examiner(s): TAYLOR, NICHOLAS R
• Application Number:
  US12/626,803
• Publication Number:
  US 20100268825A1
• Time in Patent Office: 1,285 Days
• Field of Search: 709/206, 709/204, 709/226
• US Class Current: 709/206
• 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 quickly adapts 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;

allocating resources for a first cluster to set a transmission schedule for the first cluster;

transmitting the transmission schedule for the first cluster from the cluster head of the first cluster to an edge node of the first cluster;

transmitting the transmission schedule for the first cluster from the edge node of the first cluster to an edge node of the second cluster;

transmitting the transmission schedule for the first cluster from the edge node of the second cluster to the cluster head of the second cluster;

allocating resources for the second cluster to set a transmission schedule for the second cluster based on the transmission schedule of the first cluster; and

after selecting the cluster head, assigning cluster IDs to the clusters in an ascending sequence from the cluster with the most nodes to the cluster with the least nodes,

wherein resources are allocated to each of the clusters sequentially in order of cluster ID.

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

3. The scheduling method of claim 1, wherein transmitting the transmission schedule for the first cluster from the edge node of the first cluster to an edge node of the second cluster includes transmitting a hop count corresponding to a number of intermediate nodes between the edge node of the first cluster and the cluster head of the first cluster.

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

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

6. The scheduling method of claim 4, 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.

7. The scheduling method of claim 2, wherein, after transmitting the transmission schedule for the first cluster, if the transmission schedule for the first cluster is changed, the cluster head of the first cluster transmits a header message including changed schedule information to other nodes within the first cluster.

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

9. The method of claim 1, further comprising, after allocating resources for the second cluster, creating an integrated transmission schedule by integrating the transmission schedule of the first cluster and the transmission schedule of the second cluster.

10. The scheduling method of claim 9, wherein creating the integrated transmission schedule further comprises:

determining a longest frame length from among schedules to be integrated; and

setting the frame length of the integrated schedule to the longest frame length,

wherein the schedules to be integrated include at least the transmission schedule for the first cluster and the transmission schedule for the second cluster.

11. The scheduling method of claim 10, further comprising, for a cluster whose frame length has been increased by the setting the frame length of the integrated schedule to the longest frame length, performing additional scheduling for each of the clusters.

12. The scheduling method of claim 1, wherein allocating resources for the first and second clusters comprises performing scheduling by broadcast scheduling algorithm (BSA).

13. 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;

allocating resources for a first cluster to set a transmission schedule for the first cluster;

transmitting the transmission schedule for the first cluster from the cluster head of the first cluster to an edge node of the first cluster;

transmitting the transmission schedule for the first cluster from the edge node of the first cluster to an edge node of the second cluster;

transmitting the transmission schedule for the first cluster from the edge node of the second cluster to the cluster head of the second cluster;

allocating resources for the second cluster to set a transmission schedule for the second cluster based on the transmission schedule of the first cluster; and

after allocating resources for the second cluster, creating an integrated transmission schedule by integrating the transmission schedule of the first cluster and the transmission schedule of the second cluster, determining a longest frame length from among schedules to be integrated, and setting the frame length of the integrated schedule to the longest frame length,

wherein the schedules to be integrated include at least the transmission schedule for the first cluster and the transmission schedule for the second cluster.