Review paper on Connectivity Schemes for Zigbee Networks

Review paper on Connectivity Schemes for Zigbee Networks

Baneet Kaur (M.Tech), Ms. Ruchi Singla (Associate Professor)

Department of Electronics and Communication Chandigarh Group of Colleges, Landran CGC College of Engineering, Landran

Abstract

Zigbee is basically a self organizing digital radio network. It is based on IEEE 802.15.4 standard used for Wireless Sensor Network. In Zigbee Network, every device/node has assigned a permanent address i.e. 64-Bit MAC address. But for join a zigbee network, A network address is necessary i.e. 16-Bit network Address. In Zigbee network, a Zigbee Coordinator (ZC) initiates the network or Zigbee Router (ZR) can extend the network. So,this network address is assigned from ZC or ZR. In Zigbee network, ZC follows some address assignment policies and decides three paremeters, Cm (Maximum number of children of a router), Lm (Depth of the network) and Rm (Maximum number of child router of a router). Due to the limitation of these parameters, some devices cannot receive the network address from ZC. And these devices become isolated nodes. These devices degrade the performance of the network. Many schemes has been proposed to decrease the isolated nodes. This review paper illustrates, these proposed schemes and suggests what changes can be applied for further improvement.

Keywords- Orphan Problem, Network Formation, Connectivity, Connectivity Schemes

1. Introduction

   Zigbee [1] is a standard which is designed for low data rate, low cost and low power WSN. Zigbee is based on IEEE standard 802.15.4 [2] as its physical and MAC (Media Access Control) layers and can be applied to various fields like Home Automation, Industrial Control, Environmental Sensing, Target Tracking, Battle Field monitoring, etc. More and more papers on various issues in Zigbee network, were published recently, but the connectivity problem in zigbee network, was not really much concerned in these studies such as Routing Algorithms[3, 4, 5] or data broadcast schemes[6, 7]. Many papers were also published, which focused on the Zigbee network coverage issues, assuming that there is not any connectivity problem in the network. But the performance of the network gets affected by network connectivity, so it should be concerened indeed.

   Zigbee supports three kinds of topologies:- Star, Mesh and Tree.The two types of generic 802.15.4 LR-WPAN(Low-Rate Wireless Personal Area Network) nodes upon which Zigbee devices are based, consists of the following:-

   • Reduced Function Devices (RFD):- These are reduced complexity nodes with relatively limited memory, processing, and power capabilities. They can only serve As End Devices in a network and cannot perform the more complex roles of Router or Coordinator.

   • Full Function Devices (FFD):- These devices have the resources to perform more Complex task such as Coordinator or Router but can also be an End Device in a network. The primary components that comprise a Zigbee LR-WPAN network are

   • Zigbee Coordinator (ZC): Also referred to more generically as the PAN Coordinator, this device is responsible for performing critical functions such as starting a PAN network, assigning device addresses, and controlling the PAN formation and operation. There can be only one Coordinator per Zigbee network, and the Coordinator must be an FFD.

   • Zigbee Router (ZR): A Router has the resources to execute routing algorithms and forward message to and from Zigbee devices. It is capable of establishing and maintaining multiple connections to children and parent nodes. A Router must be an FFD.

     • Zigbee End Device (ZED): An End Device can be an RFD or an FFD but is a leaf node in the network and does not perform any of the other Zigbee device functions of Router, Coordinator, Trust Center, or Gateway.

     1.1 Network formation in Zigbee

     According to Zigbee Standard [7], a Zigbee network is formed by particular procedures. Devices that can perform the function of ZC, but currently do not associated with any network, can be a candidate of a ZC. A device that wants to be a ZC will scan all the channels to find a suitable one.

     After selecting a channel, the device broadcasts a beacon, containing a PAN identifier to initialize a PAN. A device that hears a beacon of an existing network can join this network by performing the required association procedures and specifying its role, as ZR or ZED.

     If the device hears multiple beacons, it chooses the beacon sender with smallest hop count to the coordinator. Then the beacon sender will determine whether to accept this device or not, by considering its current capacity and its permitted association duration. If the device is successfully associated, the association response will contain a 16-bit address, which is the network address for the request sender.

     1.2 Orphan problem (Isolated nodes) in Zigbee

     In Zigbee, each node has a permanent 64-bit MAC address. A device is said to successfully join a network if it can obtain a 16-bit network address from the coordinator or router. Before forming a network, the coordinator needs to decide three important system parameters:-Cm, Rm and Lm. Zigbee has suggested a distributed address assignment scheme.

     This scheme may prohibit a node from accepting a child router/device as constrained by these parameters. We say that node becomes an orphan node when it cannot associate with any parent router but there are still unused address spaces remaining. We call this the orphan problem or isolated nodes. For example[8], in figure1, the router capable device A has two potential parents B and C. Router B cannot accept parent A as its child because it has reached its maximum capacity of Cm=5 children. Router C cannot accept A either because it has reached its maximum depth of Lm=2. So, a will become an orphan node. The orphan problem will worsen as the network

     scares up. The orphan problem can be relieved if proper actions are taken.

2. Different schemes Proposed to decrease the Isolated nodes

There are different mechanisms which have been already proposed to deal with connectivity problem in zigbee networks. These proposed schemes are:-

1. Connectivity Improving Mechanism for Zigbee Networks [9]:-

   In this paper, a connection shifting and extended joining procedures were proposed to decrease the isolated nodes. This scheme basically goes through four processes, before an isolated node can extendedly join to a potential parent node. These Processes are:-

   1. How a node can determine that it is a shift able node:-

      First, in the proposed mechanism, they make use of the MAC beacon payload of ZigBee for an already joined node checking whether it has a neighbor as another choice to join. The following Fig. 2 shows the format of MAC beacon payload defined in ZigBee. Router Capacity field has a TRUE/FALSE value that indicates whether the beacon broadcasting node has capability to accept a ZR device as its child. End Device Capacity field similarly indicates that whether the node can accept a ZED device as it child. Therefore, when an already joined node receives a beacon frame from its neighbor, it can check the Router Capacity or End Device Capacity field for determining that whether it has another choice to change the parent and become a shift able node.

      Fig. 2 Payload format of Zigbee MAC Beacon

   2. How the potential parent can determine that it has a shift able child:-

      in the proposed mechanism, when a child which is a ZED device wants to notify its parent the Shiftable information, it needs to send a short message. We design that a ZED child sends a notification to its parent only when the change of its Shiftable status

      occurs, that is, when the status of Shiftable changes from SHIFTABLE to NOTSHIFTABLE or the contrary. This scheme is used instead of periodically sending notification message and it will reduce the communication overhead as far as possible for notifying the ZED Shiftable status. For the scheme, a new message command (Fig. 3) is added to the existed ZigBee command list.

      Fig.3 Add shift notification Command

   3. How the potential parent can announce the status that it is joinable since it has a shift able child:-

      For this a new attribute item named nwkUseShifting was added indicates whether to the existed ZigBee NIB (Network Information Base). This attribute the ZigBee network will use the proposed shifting mechanism to improve the network connectivity. if nwkUseShifting is TRUE and a potential parent node has no router (or end device) capacity for accepting a join request of ZR (or ZED) device, the potential parent will check whether it has a shift able ZR (or ZED) child and set Router (End Device) Capacity field of MAC beacon payload to TRUE (or FALSE) if it has a (or has no) shift able ZR (or ZED) child. Since the Router Capacity and End Device Capacity fields in MAC beacon payload can imply the information of both normal joining and extended joining provided by a potential parent node, the join process is transparent to the joining nodes. A ZR (or ZED) node which has not joined to the network can send a join request to the potential parent after receiving a beacon with Router Capacity (or End Device Capacity) = TRUE from that potential parent.

   4. How the potential parent to process a join request:-

   In this process a procedure in zigbee device for the propagation of joining information which contains shifting and extended joining.

   Note:-But by using this mechanism, the joined nodes selection cannot gain the best connectivity.

2. Algorithms for BDTF (Bounded-degree- and-depth tree formation) and EDMM ( End Device maximum matching) [8]:-

In this paper, the orphan problem was divided into two sub-problems. Various schemes are designed by trying to maintain sufficient children for nodes nearby the coordinator. While both routers and end devices may become orphans, there capabilities are different. A

router may accept more routers/devices, while an end device cannot. Further, their address calculation rules are also different. For these reasons, they divide the problem into two sub problems: BDDTF and EDMM problems.

The orphan problem can be divided into two sub problems:

1. Connecting as many routers as possible to form a tree .This sub problem involves the router-capable devices only and can be modelled as a bounded-degree-and- depth tree formation (BDDTF) problem.

2. The second sub problem needs to connect as many end devices to the above tree as possible constrained by router's capacities and can be modelled as an end-device maximum matching (EDMM) problem.

   The approach proposed in this paper has two stages. The first stage will try to relieve the BDDTF problem by connecting more routers. Based on the result, the second stage will be able to connect the largest number of end devices to the tree.

   ALGORITHMS FOR THE BDTF PROBLEM:-

   The goal of this algorithm is to assign parent-child relationships to all the nodes, so that many nodes can join the network. Then the tree topology is formed and that tree contains at least N no. of nodes. Several BFS priority trees algorithms are repeatedly generated. For each tree being generated, some nodes are truncated. The truncation done is based on node association properties in the tree. In BFS tree some properties are defined. These properties are:-

   (a)A node x has a higher priority than another node y if the sub tree rooted at x in T has more nodes than the sub tree rooted at y.

   (b)If the sub trees rooted at nodes x and y have the same number of nodes, the one with less potential parents has a higher priority. A node regards a neighbor as a potential parent if this neighbor has a smaller hop count distance to the root in T than itself.

   CENTRALIZED SPAN-AND-PRUNE ALGORITHM FOR BDTF PROBLEM:-

   In this algorithm, a graph Gr = (Vr, Er) is used. The ultimate goal is to find a tree T =(vT, Et) from Gr conforming to the ZigBee tree definition. The algorithm consists of a sequence of iterations.

   Initially, T contains only the coordinator t. Then,

   in each iteration, there are two phases: Span and Prune. In the Span phase, we will pick a node in T , say x, and span from x a subtree T 0 to include as many nodes not

   yet in T as possible. Then, we attach tree to T to form a larger tree. However, the new tree may not satisfy the ZigBee definition. So, in the Prune phase, some of the

   newly added nodes in T 0 may be trimmed. The

   resulting tree is then passed to the next iteration for another Span-and-Prune phases. This is repeated until no more nodes can be added. Each node in the network will be spanned at most once. To keep track of the nodes yet to be spanned, a queue Q will be maintained.

   DISTRIBUTED DEPTH THEN BREADTH SEARCH ALGORITHM FOR BDTF PROBLEM:-

   The above Span-and-Prune algorithm is a centralized one. In this section, we present a distributed algorithm, which does a depth-first search followed by a breadth-first-like search. The depth-first search tries to form some long, thin back- bones, which are likely to pass through high- node-density areas. Then, from these backbones, the tree is spaned in a breadth-first-like manner.

   ALGORITHM FOR THE EDMM PROBLEM:-

   In this algorithm the EDMM problem is formulated as a maximum matching problem. This algorithm consists of two phases. These are:-

   Greedy phase: Each router will periodically broadcast

   beacon packets with a reserve bit to indicate whether it still has capacity to accept more end devices. Each end device e will overhear beacons from routers and, based on these beacons, compute the number Ne of its neighbor routers reserve bits on. In the case of Ne = 0, e is a potential orphan. If Ne> 0, e will try to perform the association procedure by providing its Ne value to routers. Routers simply accept as many end devices as possible with smaller Ne first (intuitively, a smaller Ne means less potential parents).

   Probing phase: After the greedy phase, each associated end device will broadcast its new Ne value.

   NOTE: – The BDDTF problem is NP- complete and proposes a two-stage network formation policy, which can effectively relieve the orphan problem. EDMM problem is solvable in an optimal way in polynomial time by a centralized algorithm and propose a distributed matching algorithm.

   The authors presented a method to reconnect the joined node while the link between this joined node and its neighbor node is breakage. This method cannot let more

   isolated devices join to the network.

3. An innovation scheme for increasing connectivity of Zigbee network[10]:-

In this scheme an extended joining procedure was proposed. The extended joining procedure is given below:-

Step 1.If nwkUseShifting = TRUE, the potential parent periodically announces that it has capacity to accept more children. Otherwise, it announces that it cannot accept more children.

Step 2.While the potential parent receives joining requests from isolated nodes, the potential parent runs Enhanced Connectivity Scheme (ECS) to select the most protable isolated node.

Step 3. While the potential parent successfully disjoins a shift able child, it accepts the isolated node selected by Step 2.

Step 4. Updates the neighbour table.

Step 5. If the potential parent still has shift able.

Children and there is any isolated node

within its communication rnge, go to Step 1.

Step 6. Runs the swapping procedure.

The most important part of the algorithm of our extended joining procedure is to select the most protable isolated node. The algorithm for selecting the most profitable isolated node is called Enhanced Connectivity Scheme (ECS). An isolated node is a either ZR or ZED in ZigBee. How this method selects the isolated node in the three cases as Following:-

Case 1: All isolated nodes are ZED devices. Since ZED cannot accept the other isolated nodes as its children within its communication range, it cannot improve the connectivity of the network. If all isolated nodes are ZED devices, we choose the one with the smallest depth due to the lower power consumption of transferring data to ZC. Case 2: All isolated nodes are ZR devices. If all isolated nodes are ZR, we have to check how many isolated nodes within its communication range for each isolated ZR. If a ZR wants to join the network, it has to scan how many isolated nodes are within its communication range. Then it noties the potential parent this message within a join request. When the potential parent receives

the join requests, it chooses the ZR device that has the most nodes within its communication range.

Case 3: Isolated nodes consist of both ZR and ZED. In this case, the ZR device is selected since it has capacity to accept other isolated devices and potentially improve connectivity of the network. If the isolated nodes contain multiple ZRs and the potential parent has capacity to accept ZR as its children, the method in Case 2 is used to choose the best ZR. If the potential parent only has capacity to accept ZED as its children, the method in Case 1 is used to choose the best ZED. NOTE: – Scheme describes various scenarios and provides the best profitable joining structure. In scenario based on energy depletion of Zigbee router, it chooses the leaf part Zigbee router as a replacement for extending the life time of network. In joining process isolated node is selected on the bases of maximum nodes it carrying.

The limitation is found in Zigbee router swapping in case of energy depletion. When energy depleted, inter-node Zigbee router send request to its child nodes and find

replacement bases of residual energy which should be more than threshold. If energy level is less then swapping is terminated and Zigbee router goes to sleep.

1. Conclusion

   This condition is avoided by introducing refined joining procedure of nodes to the network. In process of joining in to network, isolated node is selected on the bases of number of nodes it carrying. Nodes with most nodes will become part of network. In case of two nodes which are not joined network yet, which have same number of nodes, isolated node selected randomly.

   No energy level threshold was checked. And this randomly selected router becomes the part of the network. Router has to perform all the routing procedures. So the energy consumption is more in the router. If there is no energy level checking, the router with less energy might be selected and will cause failure so early. So to avoid this situation, there is need to modify this existing technique. In my thesis work I will modify this scheme.

2. References

1. ZigBee Alliance, ZigBee Specification, V1.0, Dec. 2004.

2. ZigBee Alliance, ZigBee-2007 Specification, Oct. 2007.

3. T. Kim, D. Kim, N. Park, S. Yoo, and T.S.Lopez, Shortcut Tree Routing in ZigBee Networks, 2ndInternational Symposium on Wireless Pervasive Computing (ISWPC'07), San Juan, Puerto Rico, Feb. 5-7, 2007, pp. 42-47.

4. P. Ran, M.H. Sun, and Y.M. Zou, ZigBee Routing Selection Strategy Based on Data Services and Energy- balanced ZigBee Routing, IEEE Asia-

   Pacific Conference on Services Computing (APSCC'06), Guangzhou, China, Dec. 12-15, 2006, pp, 400-404.

5. K.K. Lee, S.H. Kim, and H.S. Park, Cluster Label- based ZigBee Routing Protocol with High Scalability, 2nd International Conference on Systems and Networks Communications (ICSNC'07), Cap Esterel, France, Aug. 25-31, 2007, pp.12.

6. M. Abolhasan, T. Wysocki, and E. Dutkiewicz, A review of routing protocols for mobile ad hoc networks, Ad Hoc Networks, 2 (1), 2003, pp. 1-22.

7. Zigbee Specification Version 2006, Zigbee document 064112, 2006.

1. T.W. Song, C.S. Yang, A connectivity improving mechanism for ZigBee wireless sensor networks, In Proceedingas of IEEE/IFIP international conference on embedded and ubiquitous computing, pp 495500, 2008.

2. C.M. Wu, R.S. Chang, P.I. Lee, J.H. Yen, An innovative scheme for increasing connectivity and life of ZigBee networks, Springer Science and Business Media, LLC 2011