Collision-Free Beacon Scheduling Method based on Distributed Address Assignment Scheme

• US 20100157914A1
• Filed: 02/27/2009
• Published: 06/24/2010
• Est. Priority Date: 12/24/2008
• Status: Active Grant

• Current Assignee: Korea Electronics Technology Institute (Government of South Korea)
• Original Assignee: Korea Electronics Technology Institute (Government of South Korea)
• Inventors: KIM, Jae-Ho, Ahn, II-Yeup, Lee, Sang-Shin, Kim, Tae-Hyun, Won, Kwang-Ho, Song, Min-Hwan
• Granted Patent: US 8,213,400 B2
• Time in Patent Office: Days
• US Class Current: 370/329
• CPC Class Codes: H04W 74/006 in the downlink, i.e. towards the terminal

Abstract

Provided is a beacon scheduling method based on a distributed address assignment scheme that schedules a beacon and minimizes data delay using non-collision of addresses in a network, such as a ZigBee network, that provides a distributed address system. In the method, a time offset T_n between beacon reception from a parent device and beacon transmission of a device in a wireless network system having a tree structure may be obtained from T_n=SD×(1+O_n×B_d) according to an address of the device determined by a distributed address assignment mechanism to create a beacon transmission schedule, where SD denotes a super-frame duration, O_n denotes a value for determining which child among sibling devices in the network the device corresponds to, and B_d denotes a maximum number of router devices that a sub-network having a depth d in a tree can have.

Claims

1. A beacon scheduling method based on a distributed address assignment scheme, wherein a time offset T_n between beacon reception from a parent device and beacon transmission of a device in a wireless network system having a tree structure is obtained from T_n=SD×

(1+O_n×

B_d) according to an address of the device determined by a distributed address assignment mechanism to create a beacon transmission schedule,

where SD denotes a super-frame duration, O_n denotes a value for determining which child among sibling devices in the network the device corresponds to, and B_d denotes a maximum number of router devices that a sub-network having a depth d in a tree is capable of having.

2. The method of claim 1, wherein a network is configured from:

$2^{\mathrm{BO}-\mathrm{SO}}\ge <br><br>\{\begin{array}{cc}{L}_m,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array}$

so that all routers, including coordinators, that are capable of transmitting a beacon are capable of transmitting the beacon within one beacon interval, where BO denotes an order of the beacon and SO denotes an order of the super-frame.

3. The method of claim 1, wherein B_d is obtained from:

$B_d=\{\begin{array}{cc}{L}_m-d,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m-d}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array},$

O_n is obtained from;

O_n=(A_n−

A_parent−

1)/C<sub>skip(d−

1)</sub>, and

C_skip(d) is obtained from;

$C_{{\mathrm{skip}}_{\left(d\right)}}=\{\begin{array}{cc}1+C_m·<br><br>\left(L_m-d-1\right),& \mathrm{if}<br><br><br><br>R_m=1\\ \frac{1+C_m-R_m-C_m·<br><br>R_m^{L_m-d-1}}{1-R_m},& \mathrm{otherwise}\end{array}$

where A_n denotes an address value of the device, A_parent denotes an address value of the parent device, C_skip denotes a range of addresses capable of being assigned to child nodes belonging to the device, and C_m denotes a maximum number of all child nodes including routers and end devices, and

L_m denotes a maximum depth in the network, R_m denotes a maximum number of routers capable of transmitting beacons among child nodes, and d denotes a current depth.

4. The method of claim 3, wherein a network is configured from:

$2^{\mathrm{BO}-\mathrm{SO}}\ge <br><br>\{\begin{array}{cc}{L}_m,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array}$

so that all routers, including coordinators, that are capable of transmitting a beacon are capable of transmitting the beacon within one beacon interval, where BO denotes an order of the beacon and SO denotes an order of the super-frame.

9. A computer-readable recording medium having a program recorded thereon for performing the method according to claim 1.

10. The computer-readable recording medium of claim 9, wherein a network is configured from:

$2^{\mathrm{BO}-\mathrm{SO}}\ge <br><br>\{\begin{array}{cc}{L}_m,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array}$

so that all routers, including coordinators, that are capable of transmitting a beacon are capable of transmitting the beacon within one beacon interval, where BO denotes an order of the beacon and SO denotes an order of the super-frame.

11. The computer-readable recording medium of claim 9, wherein B_d is obtained from:

$B_d=\{\begin{array}{cc}{L}_m-d,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m-d}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array},$

O_n is obtained from;

O_n=(A_n−

A_parent−

1)/C<sub>skip(d−

1)</sub>, and

C_skip(d) is obtained from;

$C_{{\mathrm{skip}}_{\left(d\right)}}=\{\begin{array}{cc}1+C_m·<br><br>\left(L_m-d-1\right),& \mathrm{if}<br><br><br><br>R_m=1\\ \frac{1+C_m-R_m-C_m·<br><br>R_m^{L_m-d-1}}{1-R_m},& \mathrm{otherwise}\end{array}$

where A_n denotes an address value of the device, A_parent denotes an address value of the parent device, C_skip denotes a range of addresses capable of being assigned to child nodes belonging to the device, and C_m denotes a maximum number of all child nodes including routers and end devices, and

L_m denotes a maximum depth in the network, R_m denotes a maximum number of routers capable of transmitting beacons among child nodes, and d denotes a current depth.

12. The computer-readable recording medium of claim 11, wherein a network is configured from:

$2^{\mathrm{BO}-\mathrm{SO}}\ge <br><br>\{\begin{array}{cc}{L}_m,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array}$

so that all routers, including coordinators, that are capable of transmitting a beacon are capable of transmitting the beacon within one beacon interval, where BO denotes an order of the beacon and SO denotes an order of the super-frame.

5. A beacon scheduling method based on a distributed address assignment scheme, wherein a time offset T_n between beacon reception from a parent device and beacon transmission of a device in a wireless network system having a tree structure is obtained from T_n=BI−

SD*(1+O_n*B_d) according to an address of the device determined by a distributed address assignment mechanism to create a beacon transmission schedule,

where BI denotes a beacon interval, SD denotes a super-frame duration, O_n denotes a value for determining which child among sibling devices in the network the device corresponds to, and B_d denotes a maximum number of router devices that a sub-network having a depth d in a tree is capable of having.

6. The method of claim 5, wherein a network is configured from:

$2^{\mathrm{BO}-\mathrm{SO}}\ge <br><br>\{\begin{array}{cc}{L}_m,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array}$

so that all routers, including coordinators, that are capable of transmitting a beacon are capable of transmitting the beacon within one beacon interval, where BO denotes an order of the beacon and SO denotes an order of the super-frame.

7. The method of claim 5, wherein B_d is obtained from:

$B_d=\{\begin{array}{cc}{L}_m-d,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m-d}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array},$

O_n is obtained from;

O_n=(A_n−

A_parent−

1)/C<sub>skip(d−

1)</sub>, and

C_skip(d) is obtained from;

$C_{{\mathrm{skip}}_{\left(d\right)}}=\{\begin{array}{cc}1+C_m·<br><br>\left(L_m-d-1\right),& \mathrm{if}<br><br><br><br>R_m=1\\ \frac{1+C_m-R_m-C_m·<br><br>R_m^{L_m-d-1}}{1-R_m},& \mathrm{otherwise}\end{array}$

where A_n denotes an address value of the device, A_parent denotes an address value of the parent device, C_skip denotes a range of addresses capable of being assigned to child nodes belonging to the device, and C_m denotes a maximum number of all child nodes including routers and end devices, and

L_m denotes a maximum depth in the network, R_m denotes a maximum number of routers capable of transmitting beacons among child nodes, and d denotes a current depth.

8. The method of claim 7, wherein a network is configured from:

$2^{\mathrm{BO}-\mathrm{SO}}\ge <br><br>\{\begin{array}{cc}{L}_m,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array}$

so that all routers, including coordinators, that are capable of transmitting a beacon are capable of transmitting the beacon within one beacon interval, where BO denotes an order of the beacon and SO denotes an order of the super-frame.

13. A computer-readable recording medium having a program recorded thereon for performing the method according to claim 5.

14. The computer-readable recording medium of claim 13, wherein a network is configured from:

$2^{\mathrm{BO}-\mathrm{SO}}\ge <br><br>\{\begin{array}{cc}{L}_m,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array}$

so that all routers, including coordinators, that are capable of transmitting a beacon are capable of transmitting the beacon within one beacon interval, where BO denotes an order of the beacon and SO denotes an order of the super-frame.

15. The computer-readable recording medium of claim 13, wherein B_d is obtained from:

$B_d=\{\begin{array}{cc}{L}_m-d,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m-d}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array},$

O_n is obtained from;

O_n=(A_n−

A_parent−

1)/C<sub>skip(d−

1)</sub>, and

C_skip(d) is obtained from;

$C_{{\mathrm{skip}}_{\left(d\right)}}=\{\begin{array}{cc}1+C_m·<br><br>\left(L_m-d-1\right),& \mathrm{if}<br><br><br><br>R_m=1\\ \frac{1+C_m-R_m-C_m·<br><br>R_m^{L_m-d-1}}{1-R_m},& \mathrm{otherwise}\end{array}$

where A_n denotes an address value of the device, A_parent denotes an address value of the parent device, C_skip denotes a range of addresses capable of being assigned to child nodes belonging to the device, and C_m denotes a maximum number of all child nodes including routers and end devices, and

L_m denotes a maximum depth in the network, R_m denotes a maximum number of routers capable of transmitting beacons among child nodes, and d denotes a current depth.

16. The computer-readable recording medium of claim 15, wherein a network is configured from:

$2^{\mathrm{BO}-\mathrm{SO}}\ge <br><br>\{\begin{array}{cc}{L}_m,& \mathrm{if}<br><br><br><br>R_m=1\\ \left(R_m^{L_m}-1\right)/\left(R_m-1\right),& \mathrm{otherwise}\end{array}$

so that all routers, including coordinators, that are capable of transmitting a beacon are capable of transmitting the beacon within one beacon interval, where BO denotes an order of the beacon and SO denotes an order of the super-frame.