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

Patent metadata

Field	Value
Publication number	US-9240973-B2
Application number	US-201214001033-A
Country	US
Kind code	B2
Filing date	Jan 19, 2012
Priority date	Feb 22, 2011
Publication date	Jan 19, 2016
Grant date	Jan 19, 2016

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.

First claim

The invention claimed is:

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

Assignees

• Lee Yong-Hwan
• Kim Hyung Sin
• Lee Seung Hwan
• Snu R&Db Foundation

Inventors

• Lee Yong-Hwan
• Kim Hyung Sin
• Lee Seung Hwan

Classifications

• H04L45/48 Primary

  Routing tree calculation · CPC title

• H04L61/5038

  for local use, e.g. in LAN or USB networks, or in a controller area network [CAN] · CPC title

• H04W40/246 Primary

  Connectivity information discovery · CPC title

• H04W84/20

  Leader-follower arrangements · CPC title

• H04L45/02

  Topology update or discovery · CPC title