Self-construction system of wireless sensor network and method for self-construction of wireless sensor network using the same

• US 9,240,973 B2
• Filed: 01/19/2012
• Issued: 01/19/2016
• Est. Priority Date: 02/22/2011
• Status: Active Grant

• Current Assignee: Hybee, Inc.
• Original Assignee: SNU R&DB Foundation (Seoul National University)
• Inventors: Lee, Yong-Hwan, Kim, Hyung Sin, Lee, Seung Hwan
• Primary Examiner(s): Wong, Warner
• Application Number:
  US14/001,033
• Publication Number:
  US 20150036545A1
• Time in Patent Office: 1,461 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 61/5038 for local use, e.g. in LAN or USB networks, or in a controller area network [CAN]
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

Disclosed is a self-construction system of a wireless sensor network, and a method for self-construction of a wireless sensor network using the same. Also disclosed is a method for self-construction of a cluster tree structure-based wireless sensor network (WSN). The present invention can connect devices distributed densely in a wide area to a network while maintaining the advantages of a conventional tree-structured network, such as the reduction of time required for network construction, traffic by the exchange of control command messages, and a load for a routing path search, and thus can provide a WSN having an improved self-construction performance.

Claims

1. A method for self-construction of a cluster tree structure based wireless sensor network (WSN), comprising:

(A) a network structure determination step of calculating, by a coordinator, which is one of parent devices, a minimum network depth for covering up the entire area of the WSN and the number of devices located within a communication range, and calculating a maximum number of child router devices and a maximum number of child end devices according to a network depth at each tree step to determine a network structure;

(B) a network construction step of selecting, by the parent device at each tree step, the device as a child device with address allocation in response to a subscription request of a device as a child device, and allocating a superframe duration to a child router device among the child devices; and

(C) a data transmission step of searching for, by a router device having data packets, a routing path by means of address comparison between its own address and a final destination address of the packet, and transmitting the packet according to the routing path,

wherein step (A) includes;

(A-1) calculating an average communication range and calculating the minimum network depth based on the average communication range;

(A-2) calculating the number of devices located within the average communication range based on the average communication range and the minimum network depth;

(A-3) determining a maximum network depth and the number of tree steps; and

(A-4) calculating the maximum number of child router devices and the maximum number of child end devices according to the network depth at each tree step.

2. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 1, wherein

in step (A-3), the maximum network depth is set as the minimum network depth and the number of tree steps is input from a user or set to a previously determined value, and

in step (A-4), a tree threshold depth is determined for each tree step, and a structure for each tree step is determined by calculating the maximum number of child router devices and the maximum number of child end devices at each tree step in consideration of the maximum network depth and the tree threshold depth.

3. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 1, wherein step (B) includes:

(B-1) selecting, by a child device, a parent candidate group, selecting a parent device in consideration of a network depth and a transmission link quality (LQ) of parent devices in the parent device candidate group, and requesting subscription to the selected parent device as a child device;

(B-2) selecting, by the selected parent device, a child device that requests subscription in consideration of the number of its child devices and allowing the selected child device to subscribe as its child device;

(B-3) allocating, by the selected parent device, an address to the selected child device; and

(B-4) allocating, by the selected parent device, a superframe duration to its child router devices with address allocation.

4. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 3, wherein when the child device is selected as a child router device, step (B-1) includes:

estimating, by the child device, the transmission link quality (LQ) from reception characteristics of a received beacon signal and initializing a parent device candidate group comprising routers whose transmission link quality (LQ) is larger than a threshold value;

determining a parent device candidate group in consideration of the network depth of parent devices in the parent device candidate group;

selecting a parent device which has the lowest transmission link quality (LQ) in the parent device candidate group; and

transmitting to the selected parent device a subscription request message including the number of parent devices in the parent device candidate group.

5. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 4, wherein step (B-2) includes:

initializing, by the selected parent device, its child router candidate group comprising devices that request subscription as one of its child routers;

selecting a child router device which has the highest transmission link quality (LQ) among child router devices in the child router candidate group when the selected parent device is the coordinator, and selecting a child router device which has the smallest number of the parent devices in the parent device candidate group among child router devices in the child router candidate group when the selected parent device is the router;

adding the selected child router device to its child router group; and

confirming the subscription of the selected child router device in consideration of the number of child routers in its child router group and the maximum allowable number of child routers.

6. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 3, wherein when the child device is selected as a child end device, step (B-1) includes:

estimating, by the child device, the transmission link quality (LQ) based on reception characteristics of a received beacon signal and initializing a parent device candidate group comprising routers whose estimated transmission link quality (LQ) is larger than a threshold value;

determining parent devices belonging to the parent device candidate group in consideration of their network depth;

selecting a parent device which has the largest transmission link quality (LQ) in the parent device candidate group; and

transmitting a subscription request message to the selected parent device.

7. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 6, wherein in step (B-2),

the selected parent device confirms the subscription of devices as its child end devices in a first-come-first-service manner in consideration of the maximum allowable number of child end devices which is equal to the difference between the maximum allowable number of its child devices and the maximum allowable number of its child router devices.

8. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 5, wherein, when a device requesting subscription as a child router device is rejected by all of the parent devices in the parent device candidate group as a result of performing step (B-2), it performs step (B-1) as a child end device again.

9. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 3, wherein step (B-3) includes:

Calculating, by the selected parent device, the maximum number of its child devices allowable at its lower hierarchical tree steps;

allocating its child router devices their address each of which is separated by a space of the maximum allowable number of their descendent child devices; and

allocating the address to its child end devices by increasing one by one from the largest address that its child routers use.

10. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 3, wherein step (B-4) includes:

(B-4-a1) estimating, by the selected parent device and its child router device, the availability of a channel selected by the selected parent device by means of channel sensing;

(B-4-a2) generating, by the selected parent device, information on candidate superframe duration available in the estimated channel;

(B-4-a3) transmitting, by the selected parent device, the information on candidate superframe duration to its child router device;

(B-4-a4) determining, by the child router device, a superframe duration among candidate superframe durations in consideration of the received information on candidate superframe duration and available superframe duration estimated by itself;

(B-4-a5) transmitting, by the child router device, information on the determined superframe duration to the selected parent device; and

(B-4-a6) settling the superframe duration to be used by the selected parent device and its child router device.

11. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 10, wherein step (B-4-a4) includes:

comparing, by the child router device, the received information on candidate superframe duration and its estimated available superframe duration, and transmitting to the selected parent device a failure message on the selection of superframe duration when no superframe duration is available; and

repeating, by the selected parent device, step (B-4-a1) by means of channel sensing on a different channel when the failure message is received.

12. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 3, wherein step (B-4) includes:

(B-4-b1) estimating, by the selected parent device and its child router device, the availability of a channel selected by the selected parent device by means of channel sensing;

(B-4-b2) generating, by the child router device, information on candidate superframe duration available in the estimated channel;

(B-4-b3) transmitting, by the child router device, the information on candidate superframe duration to the selected parent device;

(B-4-b4) determining, by the selected parent device, a superframe duration among candidate superframe durations in consideration of the received information on candidate superframe duration and available superframe duration estimated by itself;

(B-4-b5) transmitting, by the selected parent device, the determined superframe duration information to the child router device; and

(B-4-b6) settling the superframe duration to be used by the selected parent device and the child router device.

13. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 12, wherein step (B-4-b4) includes:

comparing, by the selected parent device, the received information on candidate superframe duration and available superframe duration estimated by itself, and transmitting to the child router device a failure message on the selection of superframe duration when no superframe duration is available; and

repeating, by the selected parent device, step (B-4-a1) by means of channel sensing on a different channel when the failure message is received.

14. The method for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 1, wherein step (C) includes:

receiving, by the router device having a packet, the packet when its address is the same as the final destination address of the packet;

transmitting the packet to its child devices when the final destination address of the packet is larger than its address and smaller than its address plus its maximum allowable number of its child devices; and

returning the packet to its parent device when the final destination address of the packet is smaller than its address or larger than its address plus its maximum allowable number of its child devices.

15. A system for self-construction of a cluster tree structure based wireless sensor network (WSN), comprising:

a coordinator calculating an average communication range of the WSN and the number of devices located within the average communication range and calculating the maximum allowable number of child routers and child devices at each tree step based on the average communication range and the number of devices within the average communication range to determine a multi-step tree network structure;

parent devices selecting their child devices through a subscription request from devices belonging to a lower hierarchical tree step, and allocating their selected child devices to their own child devices addresses; and

child devices having their own addresses allocated by a parent device belonging to an higher hierarchical tree step through a subscription request process,

wherein the child devices include child router devices and child end devices,

the child router device includes a router parent selecting unit that selects a parent device candidate group, selects a parent device in the parent device candidate group, and requests subscription to the selected parent device, and

the child end device includes an end device parent selecting unit that selects a parent device candidate group, selects the parent device from the parent device candidate group, and requests subscription to the selected parent device.

16. The system for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 15, wherein the coordinator includes:

an operating environment estimating unit calculating an average communication range and the number of devices located within the average communication range; and

a multi-step balanced-tree structure optimizing unit calculating a maximum network depth, and the maximum allowable number of child routers and the maximum allowable number of child devices at each tree step.

17. The system for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 15, wherein the parent device includes:

a child router selecting unit determining its child router devices among devices that request subscription as a child router and managing its child router devices;

a child end device selecting unit determining its child end devices among devices that request subscription as a child end device and managing its child router devices; and

a multi-step tree based address allocating unit allocating an address to each of its selected child devices, transmitting the allocated address to its selected child devices, and allocating a superframe duration to each of its child router devices.

18. The system for self-construction of a cluster tree structure based wireless sensor network (WSN) of claim 15, wherein the coordinator, the parent device, and the child router device include a multi-step tree based hierarchical routing unit that searches for a routing path for transmitting packets as a router device.