Abstract:
Provided is a network self-healing method in which, when a link between a parent device and a child device breaks down in a wireless communication network of a cluster-tree structure in which a main communication device (referred to an access point (AP)) manages network operation, routers that are devices capable of having their child devices, and end devices that are devices incapable of having their child devices are associated with each other in a parent-child device relationship, the link is restored. When a router becomes an orphan device, the router makes network re-association in a cluster unit while maintaining synchronized operation with its child devices, and thus time, energy and signaling burden for network self-healing is largely reduced.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application claims priority to Korean Patent Application No. 10-2015-0185989, filed Dec. 24, 2015, the disclosure of which is hereby incorporated in its entirety by reference. 
       BACKGROUND OF THE INVENTION 
       [0002]    Rapid development of wireless communications has constantly affected habits and behavior patterns of people, and recently, Internet of Things (IoT) service technologies connecting persons and wireless devices anywhere and anytime have been under development. A wireless sensor network (WSN) provides and maintains connectivity among devices and persons, as a core technology for deploying IoT services. However, since devices in a WSN operate in limited computing capability and battery condition, the WSN is frequently damaged due to the change of channel condition, interference, malfunction, and power depletion. In order to deploy a WSN system, devices in the WSN need to be recovered from networking damage through efficient network self-healing. 
         [0003]    A cluster-tree structure provides ease of network controllability since a network may be divided in terms of network layer and cluster unit, where a main communication device, referred to an access point (AP), makes network association with a plurality of devices in a parent-child device (node) relationship. A device, referred to a router, may have its child devices, and transmit and receive data to and from its child devices. A device, referred to an end device, cannot have its child devices. 
         [0004]    ZigBee widely applied to construction of WSNs may perform network operation while reducing power consumption of devices by means of duty cycling with a super-frame structure in which a parent device synchronously operates with its child devices by periodically transmitting a beacon signal in a beacon-enabled mode, and a signal is transmitted and received during an active period and is not transmitted and received during an inactive period. When a child device does not consecutively receive a beacon signal from its parent device a certain number of times due to link damage between the child device and its parent device, the child device determines itself as an orphan device and performs following network re-association process. 
         [0005]    A child device becoming an orphan device sequentially scans available channels to find parent candidate devices (i.e., an AP or routers) nearby, determines information on a set of parent candidate devices using a beacon signal received during the channel scanning, selects a parent candidate device as a device having the lowest network depth in the set of parent candidate devices, and requests the parent candidate device to allocate a new address, thereby re-associating the WSN. 
         [0006]    However, since a network self-healing technique of ZigBee does not allow an orphan device having its child devices to make normal packet transmission with its child devices during the network re-association process, an orphan propagation phenomenon, in which the child devices of an orphan device are unable to receive a beacon signal and thus all the child devices may become orphan devices, may occur. Due to the orphan propagation phenomenon, despite link damage at one device of a network, a plurality of devices becoming orphan devices may need to perform network re-association process, which may take long time and large power consumption for the network re-association. Thus, ZigBee may not be able to efficiently handle networking damage frequently occurred in a practical environment. 
       BRIEF DESCRIPTION OF THE INVENTION 
       [0007]    According to an embodiment, when a device having its child devices becomes an orphan device, the device keeps transmission and reception of packets to and from its child devices to prevent the orphan propagation during the network re-association process, and re-associates to the network in a cluster-wise mode in consideration of network depth by getting a new address allocated by a new parent candidate device through exchange of association control messages. The child devices update their address by themselves after receiving a beacon signal including the new address of their parent device, thereby reducing power consumption and signaling burden for exchange of re-association control messages in the network re-association process. 
         [0008]    Additional aspects will be set forth in part in the description which follows and, in part, will be apparent from the description, or may be learned by practice of the presented embodiments. 
         [0009]    According to an embodiment of the present invention, there is provided a network self-healing method in which an orphan device dis-associated from a network due to networking damage makes network re-association in a cluster-tree structured multi-hop wireless communication network, wherein a main communication device (referred to an access point (AP)) that manages network operation, routers that can have their child devices, and end devices that cannot have their child devices are associated with each other in a parent-child device relationship, and a child device keeps network synchronization with its parent device by receiving a beacon signal periodically transmitted from its parent device, the network self-healing method including: when the orphan device is a router, keeping, by the orphan device, network synchronization with its child devices by periodically transmitting a beacon signal during a network re-association procedure as before being an orphan device; determining, by the orphan device, a set of parent candidate devices and a parent candidate device in the set of parent candidate devices in consideration of network depth and received signal power; and determining, by the orphan device, child devices to make the network re-association together in consideration of a network depth of the determined parent candidate device, and making the network re-association to the determined parent candidate device with the determined child devices, and when the orphan device is an end device, determining, by the orphan device, a set of parent candidate devices and a parent candidate device in the set of parent candidate devices in consideration of received power of signal transmitted from the set of parent candidate devices, and making, by the orphan device, the network re-association to the determined parent candidate device. 
         [0010]    The determining of a set of parent candidate devices and a parent candidate device in the set of parent candidate devices when the orphan device is a router may include: estimating, by the orphan device, network depth and received signal power of adjacent devices (i.e., an AP or routers) after receiving a beacon signal transmitted from the adjacent devices by using a conventional channel scanning method; determining, by the orphan device, a set of parent candidate devices for network re-association in consideration of network depth in an ascending order; and determining, by the orphan device, a parent candidate device as a device providing a maximum received signal power among devices having the lowest network depth in the set of parent candidate devices. 
         [0011]    The determining of the child devices and making network re-association when the orphan device is a router may include: when L max  denotes a maximum network depth, L past  denotes a network depth of its previous parent device before being an orphan device, wherein 0≦L past &lt;L max , and L new  denotes a network depth of the determined parent candidate device, wherein 0≦L new &lt;L max ; when L new =L max −1, transmitting, by the orphan device, a re-association control message to all its child devices, and making, by the orphan device, the network re-association as an end device; when 0≦L new &lt;L max −1 and L new ≦L past , making, by the orphan device, the network re-association with its child devices while keeping network synchronization with its child devices; and when 0≦L new &lt;L max −1 and L new &gt;L past , transmitting, by the orphan device, a re-association control message to its child routers, and making, by the orphan device, the network re-association only with its child end devices. 
         [0012]    The making, by the orphan device, network re-association with its child devices may include: requesting, by the orphan device, the determined parent candidate device to accept its network re-association as a child router; when the determined parent candidate device has an address space available for accepting the orphan device as its child router, allocating, by the determined parent candidate device, the available address space to the orphan device and accepting a request of network re-association of the orphan device as its child router, and when the determined parent candidate device has no address space available, refusing a request of network re-association of the orphan device; after the orphan device re-associates to the determined parent candidate device, allocating, by the orphan device, addresses to its child devices by using the address space allocated by the determined parent candidate device, and when a request of network re-association of the orphan device is refused by the determined parent candidate device, removing, by the orphan device, the determined parent candidate device in the set of parent candidate devices, determining a new parent candidate device in the set of parent candidate devices, and making the network re-association with its child devices determined in consideration of network depth of the new parent candidate device when the orphan device is a router; and when a request of network re-association of the orphan device is refused by all parent candidate devices in the set of parent candidate devices, transmitting, by the orphan device, a re-association control message including a ‘re-association command’ to all its child devices and making network re-association alone as an end device after determining a new set of parent candidate devices and a parent candidate device in the new set of parent candidate devices. 
         [0013]    The determining of a set of parent candidate devices and a parent candidate device in the set of parent candidate devices, and the making of network re-association when the orphan device is an end device may include: estimating, by the orphan device, received power of beacon signal transmitted from adjacent parent candidate devices (e.g., an AP or routers) by using a conventional channel scanning method; determining, by the orphan device, a set of parent candidate devices for network re-association in consideration of received signal power in a descending order; determining, by the orphan device, a parent candidate device as a device providing the highest received signal power in the set of parent candidate devices; requesting, by the orphan device, a network re-association to the determined parent candidate device as a child end device; when the determined parent candidate device has an address space available for accepting the orphan device as its child end device, allocating, by the determined parent candidate device, the orphan device an address in the address space available for its child end devices and accepting a request of network re-association of the orphan device as its child end device, and when the determined parent candidate device has no address space available for its child end devices, refusing a request of network re-association of the orphan device; when a request of network re-association of the orphan device is refused by the determined parent candidate device, removing, by the orphan device, the determined parent candidate device in the set of parent candidate devices, determining a new parent candidate device as a device providing the highest received signal power in the set of parent candidate devices, and requesting a network re-association to the determined parent candidate device as a child end device; and when a request of network re-association of the orphan device is refused by all parent candidate devices in the set of parent candidate devices, requesting, by the orphan device, the network re-association after determining a new set of parent candidate devices and a parent candidate device in the new set of parent candidate devices. 
         [0014]    The network self-healing method may further include, after the orphan device transmits a re-association control message to its child devices: when a child device that receives the re-association control message is a router, requesting, by the child device, a network re-association as a router while keeping network synchronization with its child devices, the determining of a set of parent candidate devices and a parent candidate device in the set of parent candidate devices, and the determining of the child devices that make the network re-association together; and when a child device that receives the re-association control message is an end device, requesting, by the child device, a network re-association as an end device after determining a set of parent candidate devices and a parent candidate device in the set of parent candidate devices, and making the network re-association. 
         [0015]    The network self-healing method according to an embodiment may improve, compared to an existing technique, network self-healing performance in a cluster-tree structured wireless communication network, in which a plurality of devices are associated to an AP in a parent-child device relationship with a multi-hop structure, while reducing signaling burden and power consumption by means of network re-association in a cluster-wise manner. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0016]    The above and other objects, features and other advantages of the present invention will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings, in which: 
           [0017]      FIG. 1  illustrates an operational environment of a wireless communication network according to an embodiment of the present invention; 
           [0018]      FIG. 2  illustrates network self-healing processes according to an embodiment of the present invention; 
           [0019]      FIG. 3  illustrates a principle of cluster-wise network re-association processes according to an embodiment of the present invention; 
           [0020]      FIG. 4  illustrates a principle of single-node network re-association processes according to an embodiment of the present invention; 
           [0021]      FIG. 5  illustrates a principle of address requesting and address allocation processes according to an embodiment of the present invention; 
           [0022]      FIG. 6  illustrates a principle of address updating processes according to an embodiment of the present invention; and 
           [0023]      FIG. 7  illustrates a principle of address calculating processes according to an embodiment of the present invention. 
       
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0024]    Hereinbelow, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. In the description of the present invention, certain detailed explanations are omitted when it is deemed that they may unnecessarily obscure the essence of the invention. All terms which are used herein should be construed as having meanings that are obvious to one of ordinary skill in the art. However, the terms may have different meanings according to an intention of one of ordinary skill in the art, precedent cases, or the appearance of new technologies. Thus, the terms used herein have to be defined based on the meaning of the terms together with the description throughout the specification. 
         [0025]      FIG. 1  illustrates a concept of a cluster-tree structured wireless sensor network (WSN) to which an embodiment of the present invention is applicable. In  FIG. 1 , an access point (AP) manages a network, routers can have their own child devices, and end devices may be associated to the AP or a router and are unable to have their own child devices. In an arbitrary pair of devices associated in one hop, a device associated to the AP in less hops than the other device is defined by a parent device and the other device is defined by a child device, wherein a network depth of the child device is larger than that of the parent device by one. Referring to a configuration of the cluster-tree structured WSN in detail with reference to  FIG. 1 , for example, based on a device  102  in the WSN, the device  102  is a child device with respect to a device  101  associated to the AP in less hops among devices associated to the device  102 , and the device  102  is a parent device with respect to devices  103  and  104  associated to the AP in more hops. 
         [0026]    In order to reduce power consumption of a WSN, parent-child devices use a super-frame structure wherein parent-child devices make communications only during an active period and stop transceiver operation during an inactive period as shown in  FIG. 1 . Such a super-frame structure is periodically repeated, wherein a parent device periodically transmits a beacon signal including network information at the beginning of each super-frame at a period of a super-frame length (equal to a beacon interval (BI)), and child devices receive a beacon signal transmitted from their parent device to keep network synchronization, and transmit and receive data to and from their parent device (for example, a beacon-enabled mode of ZigBee). 
         [0027]    In the WSN, when N denotes the number of channels available for communications, a device making network association determines information on a set of parent candidate devices using a beacon signal received through N channels, selects a parent candidate device, and attempts to make network association to the parent candidate device which will allocate an L-bit network address for network communications. Devices may generally have their unique identifier, but they may reduce signaling burden for communications by using an address allocated in the network association. In a case of ZigBee, a router has a its own address space of C skip  allocated by its parent device, which can be used for address allocation to its child devices as in Equation 1 below, and has Cm addresses available for network association of its child devices in a tree structure, wherein R m  addresses may be available for network association of its child routers and the remaining, i.e., (C m −R m ), addresses may be available for network association of its child end devices. 
         [0000]    
       
         
           
             
                 
             
              
             
               [ 
               
                 Equation 
                  
                 
                     
                 
                  
                 1 
               
               ] 
             
           
         
       
       
         
           
             
               Cskip 
                
               
                 ( 
                 D 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           max 
                            
                           
                             { 
                             
                               0 
                               , 
                               
                                 1 
                                 + 
                                 
                                   Cm 
                                   × 
                                   
                                     ( 
                                     
                                       Lm 
                                       - 
                                       D 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                               
                             
                             } 
                           
                         
                         , 
                       
                     
                     
                       
                         
                           for 
                            
                           
                               
                           
                            
                           Rm 
                         
                         = 
                         1 
                       
                     
                   
                   
                     
                       
                         
                           max 
                            
                           
                             { 
                             
                               0 
                               , 
                               
                                 
                                   
                                     Cm 
                                     × 
                                     
                                       Rm 
                                       
                                         Lm 
                                         - 
                                         D 
                                         - 
                                         1 
                                       
                                     
                                   
                                   + 
                                   Rm 
                                   - 
                                   Cm 
                                   - 
                                   1 
                                 
                                 
                                   Rm 
                                   - 
                                   1 
                                 
                               
                             
                             } 
                           
                         
                         , 
                       
                     
                     
                       otherwise 
                     
                   
                 
                 . 
               
             
           
         
       
     
         [0028]    Here, D denotes a network depth and L m  denotes a maximum network depth. 
         [0029]    A network self-healing message protocol in an example of an orphan device having its child devices, according to an embodiment of the present invention, is shown in  FIG. 2 . When an orphan device has no child device, the network self-healing message protocol of  FIG. 2  is performed without operation  203 ,  204 ,  2 ) of  205 ,  206 , and  207 . The orphan device determines information on a set of parent candidate devices in operation  201  after receiving a beacon signal transmitted from adjacent devices in operation  202 , by using a conventional channel scanning method, and transmits a beacon signal at the beginning of its beacon interval to perform a super-frame based operation as a parent device, in operation  204 . While the orphan device makes a network re-association, its child devices may regularly receive a beacon signal and perform packet transmission, in operation  203 . After the channel scanning, the orphan device determines a parent candidate device in the set of parent candidate devices in an ascending order of network depth and a descending order of received signal power, in operation  205 . When the network depth of the determined parent candidate device is not larger than that of the previous parent device of the orphan device (a condition in which all child devices can be re-associated to the network together) or when the network depth of the determined parent candidate device is enough to only keep its child end devices (a condition in which only child end devices can be re-associated to the network together), the orphan device may make network re-association in a cluster-wise manner and thus keeps network synchronization with its child devices by transmitting a beacon signal at the beginning of its own beacon interval and performs a super-frame based operation as a parent device in operation  207  as in operation  204 . The orphan device that makes network re-association in a one-hop cluster mode transmits a re-association control message including a ‘re-association command’ to its child routers in the super-frame based operation in operation  207 . The orphan device exchanges association request/response messages with a parent candidate device for network re-association, in operation  208  and  209 . After the orphan device receives an association response message including an ‘association permission’ information, the orphan device finishes the network self-healing process, and after the orphan device receives an association response message including an ‘association denial’ information, the orphan device repeats the network re-association operation from operation  205  until the set of parent candidate devices becomes empty. When the set of parent candidate devices is empty, the network self-healing message protocol of  FIG. 2  is performed again from operation  201  without performing operation  203 ,  204 ,  2 ) of  205 ,  206 , and  207 . 
         [0030]    A cluster-wise network re-association procedure performed when a device having child devices becomes an orphan device, according to an embodiment of the present invention, is shown in  FIG. 3 . The orphan device transmits a beacon signal and performs a super-frame based operation in operation  302  at the beginning of its own beacon interval in operation  301  even while scanning a channel, selecting a parent candidate device, or exchanging network association-related messages. When a parent candidate device is not determined in operation  303 , the orphan device determines whether to continue the channel scanning in operation  306  and  307 . After the orphan device performs the channel scanning in operation  306  and determines a set of parent candidate devices in operation  309 , the orphan device selects a parent candidate device as a device having the lowest network depth and providing the highest received signal power in the set of parent candidate devices for network re-association, and compares the network depth of the selected parent candidate device with that of its previous parent device before being an orphan device in operation  310  to determine whether to make network re-association with its child devices together. In detail, when the network depth of the selected parent candidate device is not larger than that of its previous parent device, the orphan device keeps a current network structure with its child devices, and when the network depth of the selected parent candidate device is enough to only keep its child end devices, the orphan device transmits a re-association control message including a ‘re-association command’ to its child routers so that its child routers is disconnected from the orphan device and only its child end devices are kept with the orphan device in operation  312 . As described above, after the orphan device selects a parent candidate device in operation  303 , the orphan device transmits an association request message to the selected parent candidate device to request for an address space and receives an association response message from the selected parent candidate device in operations  304  and  305 . When the orphan device receives an association response message including an ‘association permission’ information, the orphan device gets a new address included in the association response message in operation  308 , and finishes its cluster-wise network re-association process in operation  313 . When the orphan device receives an association response message including an ‘association denial’ information, the orphan device repeats the above operations until the set of parent candidate devices becomes empty, and when the set of parent candidate devices is empty in operation  309 , the orphan device re-associates to the network alone by itself in operation  311 . 
         [0031]    A single-node network re-association process performed when a device having no child device becomes an orphan device in operation  311  of  FIG. 3 , according to an embodiment of the present invention, is shown in  FIG. 4 . When a parent candidate device is not determined in operation  401 , the orphan device determines whether to continue a channel scanning in operations  404  and  405 . After the orphan device performs the channel scanning and determines a set of parent candidate devices in operation  407 , the orphan device selects a parent candidate device as a device having the lowest network depth and providing the highest received signal power in the set of parent candidate devices for network re-association in operation  408 . When the orphan device selects a parent candidate device in operation  401 , the orphan device transmits an association request message to the selected parent candidate device to request for an address, and receives an association response message from the selected parent candidate device in operations  402  and  403 . When the orphan device receives an association response message including an ‘association permission’ information, the orphan device gets a new address included in the association response message in operation  406  and finishes its single-node network re-association process in operation  409 . When the orphan device receives an association response message including an ‘association denial’ information, the orphan device repeats the above operations until the set of parent candidate devices becomes empty, and when the set of parent candidate devices is empty in operation  407 , the orphan device performs the channel scanning to determine a new set of parent candidate devices in operation  405 . 
         [0032]    Procedures for address request of the orphan device and address allocation of the parent candidate device, which correspond to operations  304 ,  305 , and  308  of  FIG. 3  and operations  402 ,  403 , and  406  of  FIG. 4 , according to an embodiment of the present invention, are shown in  FIG. 5 . The orphan device transmits an association request message to the selected parent candidate device to request for an address of itself or as a representative of its cluster, in operation  501 . Upon receiving the association request message in operation  506 , the selected parent candidate device determines whether it can allocate the orphan device an address space in its available address space in consideration of a type of the orphan device in operation  507 . When it can allocate the orphan device an address space, it generates an association response message including an ‘association permission’ information in operation  508 , and when it cannot allocate the orphan device an address space, it generates an association response message including an ‘association denial’ information in operation  509 , and transmits the association response message to the orphan device. The orphan device checks whether an address space is allocated in operation  503  from a flag of the association response message received in operation  502 . When a new address space is not allocated in operation  505 , the orphan device removes the selected parent candidate device from the set of parent candidate devices, and performs operation  301  of  FIG. 3  or operation  401  of  FIG. 4 . When a new address space is allocated in operation  504  after transmitting the association request message as a representative of its cluster, the orphan device transmits its beacon signal including its new address and network depth. 
         [0033]    An address update procedure of a child device, according to an embodiment of the present invention, is shown in  FIG. 6 . A parent device re-associated to the network with a new address space transmits a beacon signal including its new address and network depth, and upon receiving the beacon signal in operation  601 , a child device checks whether the address of its parent device in the received beacon signal has been changed in operation  602 . Examples of a method of checking, by the child device, whether the beacon signal has been transmitted from its parent device, include a method of examining a unique identifier of its parent device included in the beacon signal and a method of examining the previous address of its parent device included in the beacon signal, which can be transmitted by the parent device. After the child device confirms that the address of its parent device has been changed in operation  602 , the child device recognizes that its parent device has re-associated to the network, and tests whether the new network depth of its parent device is equal to or less than the previous network depth of its parent device in operation  603 . After the child device confirms that the network depth is equal to or less than the previous network depth in operation  603 , the child device updates its address in operation  605  regardless of its type (i.e., a router or an end device). Upon confirming that the new network depth of the parent device is larger than the previous network depth in operation  603 , the child device updates its address in operation  605  only when the child device is an end device in operation  604 . When the child device is a router, regardless of receiving a network re-association control message from its parent device in operation  312  of  FIG. 3 , the child device determines that the child device becomes an orphan device in operation  604 , and may perform a cluster-wise network re-association procedure ( FIG. 3 ) or a single-node network re-association procedure ( FIG. 4 ) depending on whether the child device has its child devices or not. 
         [0034]    A procedure for updating an address in operation  605  is shown in  FIG. 7 . As in operation  701 , upon confirming that a network depth D parent  of its parent device re-associating to the network is the same as the previous network depth D parent   past  of its parent device and is less than a maximum network depth minus one (i.e., L m −1), the child device may update its network address A by adding a difference |Δ addr   parent | between the new and the previous address of its parent device to the network address A (i.e., A=A+|Δ addr   parent |). Also, upon confirming that the network depth D parent  is larger than the previous network depth D parent   past  in operation  701 , when the child device is a router in operation  703 , the child device updates its address by calculating a number n according to Equation 2 below in operation  704 , where n denotes the n-th child device of its parent device. 
         [0000]        n =( A−A   parent )/ C   skip ( D   parent   past )+1 
         [0000]        A=A   parent +1+( n− 1)× C   skip ( D   parent )   [Equation 2]
 
         [0035]    On the other hand, when the child device is an end device in operation  703 , the child device updates its address by calculating the number n according to Equation 3 below in operation  705 . 
         [0000]        n =( A−A   parent )− R   m   ×C   skip ( D   parent   past )
 
         [0000]        A=A   parent   +n+R   m   ×C   skip ( D   parent )   [Equation 3]
 
         [0036]    Although preferred embodiments of the present invention have been described for illustrative purposes, those skilled in the art will appreciate that various modifications, additions and substitutions are possible, without departing from the scope and spirit of the invention as disclosed in the accompanying claims. Therefore, the embodiments of the present invention are disclosed only for illustrative purposes and should not be construed as limiting the present invention.