PDF Links
PubReader
ePub Link1. Introduction
Most wireless sensor networks have been developed based on the IEEE802.15.4 [1] standard, which supports various topologies, such as star, peer-to-peer, and a clustered tree, and different modes of operation, such as the beacon-enabled mode and the non-beacon mode. In particular, since a superframe structure in a beacon-enabled mode enables an energy efficient network to be constructed, most wireless sensor applications have made an attempt to use IEEE802.15.4 as their PHY and MAC layer. However, in multi-hop networks, beacon packets from different nodes have a high collision probability, and a beacon collision problem is therefore considered to be one of the most significant challenges in designing a multi-hop network that is based on IEEE802.15.4.
Over the past few years, several studies [2–13] have been conducted on improving the energy efficiency and reliability in multi-hop networks that are based on IEEE802.15.4. Most of them have mainly focused on solving beacon collision problems. More specifically, the authors of [2–9] proposed the use of beacon scheduling algorithms and protocols for multi-hop tree networks that are based on ZigBee [14]. While these studies addressed the beacon-collision problem in a multi-hop network, most of them have only focused on the tree architecture in which some failures can make a partial or entire network lose connectivity to its root. Instead, a mesh architecture, which is able to provide high reliability and a fast error recoverability by maintaining multiple paths, is more suitable for various applications with different network topologies. Other bodies of research [10–12] have dealt with beacon scheduling methodologies for mesh-based multi-hop networks. However, these proposals, which are based on IEEE802.15.4, do not overcome the inherent limitations of PHY and MAC. In parallel, TG4e [15] has rolled out the IEEE802.15.4e draft for an enhancement of the MAC layer of IEEE802.15.4-2006. In particular, the emerging new standard, IEEE802.15.4e, or more specifically, the deterministic and synchronous multichannel extension (DSME) capability, contains a mesh-enabled, beacon-scheduling functionality that utilizes a specific bitmap and a multi-superframe structure. However, the standard does not yet provide a critical recipe for a superframe duration (SD) allocation method or for concrete implementation details on the proposed beacon scheduling. Therefore, critical system performance, in terms of resource use, such as processing, memory, and energy, might depend significantly on which SD index allocation algorithm is applied. In this paper, we provide concrete implementation guidelines for IEEE802.15.4e beacon scheduling, and then carry out various experiments on different SD allocation algorithms, which include the least significant bit (LSB) first, most significant bit (MSB) first, and random. Based on the results of our experiments, we also propose an adaptive SD allocation algorithm that utilizes a distributed neighboring slot incrementer (DNSI), instead of using a SD bitmap, to manage neighboring scheduled beacon slots.
The remainder of this paper is organized as follows: in Section 2, various beacon scheduling algorithms and protocols for multi-hop communications based on IEEE802.15.4 are investigated. Section 3 provides an overview of the new standard, IEEE802.15.4e DSME, particularly for beacon scheduling functionality. In Section 4, we carry out various experiments on different SD allocation methods, and thoroughly analyze the experimental results from the viewpoint of resource efficiency. Based on the results of our experiments, Section 5 describes the development of an adaptive SD allocation algorithm for resource-efficient beacon scheduling. Next, a performance comparison is evaluated in Section 6. Finally, Section 7 provides some concluding remarks regarding this proposal.
2. Related Work
Over the last few years, a lot of research has focused on beacon scheduling to efficiently manage beacon collisions in multi-hop communication that is based on IEEE802.15.4. Some researchers [2–9] have focused on preventing beacon collisions among coordinators or routers in a tree network. Two different proposals by TG4b [2] have dealt with beacon collision and interference problems among different coordinators. The first approach is to use a contention-free time slot in its active period by utilizing a specific indicator called a beacon_tx_offset between the parent beacon and child beacon. Moreover, this approach was reflected in the ZigBee specifications [14]. The second approach uses a dedicated beacon-only period in which only scheduled beacon frames are allowed to transmit. However, this research did not address the issue of time offset selection by neighboring coordinators. A time-division beacon scheduling method for clusters has been proposed by Koubaa et al. [3]. Based on the assumption that PAN coordinators are aware of their neighbors’ location and connection information, each PAN coordinator schedules all coordinators and routers. A method proposed by Cho and An [4] first constructs clusters using different transmission power, and then makes the PAN coordinator allocate a beacon slot and a group ID to the group headers. However, this approach might give the PAN coordinator increased overhead due to a centralized beacon slot allocation. A slotted beacon scheduling method proposed by Ahn et al. [5] uses a slot allocation method coupled with the Cskip address allocation scheme used for ZigBee. In addition, a method to use separate slots for an uplink and a downlink in a superframe was proposed by Yeh et al. [6]. To efficiently reuse slots in a tree network, a stochastic beacon scheduling method has been introduced in [7]. For a specific sensor application, such as target monitoring, an adaptive beacon interval method, with respect to varying the detection level of the target, has been proposed by Chen et al. [8]. In addition, Kim and Yoon [9] proposed a tree-routing protocol based on a hybrid scheme combining distributed and stochastic addressing methods. Although these studies address a beacon-collision problem in a multi-hop network, most of them have focused only on a tree architecture in which failures of some point can make a partial or entire network lose connectivity to its root.
A mesh architecture, which is able to provide high reliability and a fast error recoverability by maintaining multiple paths, is more suitable for various applications with different network topologies. Burda and Wietfeld [10] made an attempt to construct autonomous and distributed mesh networks in the beacon-enabled mode, in which the PAN coordinator selects and allocates a random beacon slot for slot request nodes. However, this algorithm requires a long integrity checking time and still has a high collision probability of the request packets. The WPAN mesh network proposed by TG5 [11] characterizes block address assignments and a connection matrix. Even though this standard is to construct a mesh network based on WPAN, asynchronous energy saving in non-beacon mode might increase unnecessary delays and the wasting of energy. Moreover, the initial setup phase is still based on a tree topology. In addition, MeshMAC [12] proposed a distributed beacon scheduling for a mesh network, but it did not address a neighboring beacon slot collection method, which is the key point of distributed beacon scheduling. The IEEE802.15.4e standard [15], more specifically, DSME capability, provides the specifications regarding the concept level of bitmap-based distributed beacon scheduling. However, the standard does not yet provide a critical recipe for an SD allocation method or concrete implementation details regarding the proposed beacon scheduling.
Our former work [13] dealt with a distributed, fast beacon scheduling method for mesh networks. However, while we previously presented only a conceptual model for bitmap-free beacon scheduling, this paper provides a more concrete, explicit SD allocation algorithm and beacon scheduling methodology by introducing three possible SD allocation algorithms and analyzing the IEEE802.15.4e DSME beacon scheduling through various experiments.
3. Overview of IEEE802.15.4E Beacon Scheduling
IEEE802.15.4e DSME is one of the different operation modes of eMAC (TSCH, LLDN, RFID Blink, DSME, and AMCA), and characterizes mesh-based beacon collision free networks. In particular, the distributed beacon scheduling functionality is one of the outstanding new features in the DSME standard. DSME beacon scheduling is based on the multi-superframe structure in a beacon interval of a PAN coordinator node. This feature allows neighboring nodes to allocate different beacon slots in a distributed way. To allocate its own beacon slot, each node manages the SD indexes of its neighboring nodes. More specifically, the SD index information of all neighboring nodes is represented as a bitmap structure and issued through an enhanced beacon frame. A coordinator who wants to join the PAN can collect its neighboring SD index information from received beacon frames, allocate a vacant SD index slot for itself, and broadcast an allocation notification command frame containing its allocated SD index value to its neighbors. All nodes receiving the frame check whether the allocated SD index value exists or not in their man-aging neighbor SD index bitmap. If it does, the nodes reply with a collision notification command frame to the sender. Otherwise, the new SD index value is marked as ‘Active.’ As a result, each node can realize the SD index allocation information through their two-hop neighbors. This distributed beacon scheduling can construct a beacon-enabled mesh network. However, the standard does not provide the following critical ingredients for a slot allocation or implementation details about beacon scheduling functionality. It is important to note that these matters, which are not specified in the DSME standard, might generate a significant performance variation in the resource usage for items, such as processing, memory, and energy, depending on the implementation methodologies that are applied.
4. Experimental Study on Three Possible SD Allocation Approaches
In this section, we first provide concrete implementation guidelines for IEEE802.15.4e DSME beacon scheduling, and then introduce three possible SD allocation algorithms. Based on the design and implementation guidelines, we carried out various experiments on different SD allocation methods, and thoroughly analyzed the experimental results based on their resource efficiency.
4.1 Implementation Considerations
The DSME standard only considers a single SD bitmap and macSDBitmap in macPIB for beacon scheduling, but two independent bitmap spaces (a beacon bitmap and a neighbor [NBR] bitmap) are needed for real implementation. A beacon bitmap is needed, so that it can seek its own SD index location. The bitmap field included in an extended beacon is copied to the beacon bitmap. A node can select a slot out of the vacant SD slots in the bitmap for its candidate SD index, and the corresponding bit in the bitmap is then set. The node then broadcasts an allocation notification message with its new candidate SD index. The neighbor nodes that received the allocation notification message check whether the received SD index value already exists in the neighbor bitmap. If so, the neighbor node notifies the originator that the SD index is already occupied by sending a collision notification message. The originator that received the collision notification message reselects its candidate SD index and then broadcasts an allocation notification with this new SD index. This SD allocation procedure is repeated until collision notification messages are no longer received. While a beacon bitmap is used to seek its own candidate SD index from the received beacon, the neighbor bitmap is used to notify neighbors of the latest neighbor SD index information and is contained in its cyclic extended beacon. Even though the usage of two independent bitmaps is not specified in the DSME standard, utilizing these two independent bitmaps is indispensable for DSME beacon scheduling operations. SD allocation starts by receiving an extended beacon containing the SD bitmap field. As mentioned previously, every node should select a vacant slot (superframe) to be used for its SD index, based on the SD bitmap. However, the standard does not provide the criteria for selecting an SD index from the received beacon bitmap.
Therefore, we are introducing three different selection algorithms: LSB first, MSB first, and random.
Fig. 1 describes the criteria for LSB first and MSB first from the received SD bitmap. The LSB first scheme seeks the least slot value out of all of the vacant slots (0). Conversely, the MSB first scheme selects a vacant slot immediately following the allocated slot with the largest value. Lastly, the random scheme selects a vacant slot randomly within the SD bitmap length. Fig. 2(b) lists the results of the DSME beacon scheduling on individual SD allocation mechanisms (LSB first, MSB first, and random), on the same network topology, which is shown in Fig. 2(a). The results demonstrate that the SD index allocation of each node differs according to the underlying SD allocation method. Therefore, we presume that the DSME beacon scheduling might show a different performance according to the SD allocation scheme that is applied.
4.2 Experimental Analysis
In this subsection, an experimental study of DSME beacon scheduling on different SD allocation schemes is described. To perform more extensive evaluations, we developed a WPAN beacon scheduling simulator framework in which each algorithm is implemented independently using C and C++. The developed simulator constructs entities of each node based on various input parameters, as shown in Table 1, and an even-driven scheduler processes various events that occur during the run time. The simulator also supports various topologies, and in particular, we used the following three different types of topologies for our experiments: tree, mesh, and cluster. On each topology, we observed the association completion time, the required bitmap size, and the amount of traffic by varying the network size from 3×3 to 10×10 in the tree and mesh topologies, and from 10 to 100 cluster members in the cluster topology, as shown in Fig. 3.
4.2.1 Association completion time
Fig. 4(a) shows the experimental results of the association completion time under various conditions. The association completion time is defined as the time until the superframe allocation of all nodes is completed. Therefore, we measured the time spent until the end of the superframe allocation of the last node was completed, starting from the first beacon reception of the PAN coordinator. The results demonstrate that the MSB first scheme outperforms the LSB first and random schemes under all circumstances. In particular, LSB first shows a large variation in the association completion time with respect to a varying network size. In the LSB first scheme, if a node selects a vacant slot preceding the current ongoing superframe number, the node should wait until its SD index turns in the next beacon interval, and it can then continue to carry out the beacon scheduling with its children. These situations frequently occur in the random scheme, as well as in LSB first. In particular, the larger the network size and the smaller the connected links, the more the delay is increased. On the other hand, since MSB first always seeks a vacant slot immediately following the allocated slot with the largest value, the new SD index does not precede the current ongoing superframe number. Therefore, any unnecessary delay until the next beacon interval is removed. The results also show that the MSB first scheme allows all nodes to be associated within 700 ms in each topology with 100 nodes at a maximum BO size of 512. On the other hand, it shows that LSB first spends more than 10 beacon intervals for the association completion.
4.2.2 Required bitmap size
The bitmap that reflects the neighboring SD index information is included in its extended beacon and is transmitted periodically together with the latest neighbor information. The bitmap length is specified in the SD bitmap length field of the extended beacon. The SD bitmap length is generally defined as 2 (BO-SO) bits, and the BO value should be no more than 10, including the mandatory header fields, since the maximum frame size of IEEE802.15.4 is limited to 128 bytes. That is, the maximum available length is 512 bits (64 bytes). Furthermore, if the length is too small, the number of available superframes for the new nodes is insufficient, and the PAN coordinator should start with a length that is great enough to accommodate the nodes which will be associated. For example, if it is expected that at least 100 nodes will be associated with the network, the PAN coordinator should secure a bitmap space of at least 128 bits, the BO value of which is 8. Under these conditions, Fig. 3(b) shows the required bitmap size for all of the nodes that will be associated with the network. The required bitmap size represents the maximum occupied bitmap size during the association procedure. It is notable that LSB first shows a considerable reduction of bitmap size over LSB first and the random scheme, even if the network size is increased. This is because LSB first selects the front-most vacant slot, and thus, the superframe reuse ratio is increased. Accordingly, the required bitmap size can be reduced. Since the random scheme selects a vacant slot randomly within the maximum SD index length, the slot reuse ratio is very low, and thus, an increased bitmap size is required. Since a bitmap represents the allocation information of all neighbors within two hops, the bitmap size might vary according to the number of connected links. More specifically, the required bitmap size is increased proportionally to the number of connected links. Therefore, the required bitmap size, L(i), of an arbitrary node is determined as follows:
where, M is a set of nodes in the network, and N(Ai) represents the total number of neighboring nodes of node i.
In particular, in a cluster topology, the required bitmap size is the sum of the number of cluster headers and the total number of cluster members of a cluster, which has the largest number of cluster members among the clusters. In this case, the bitmap size of both the MSB first and LSB first reach the maximum value. The results show that in the case of a cluster topology, in which there are three clusters and each cluster has 100 members, the required bitmap size is 103. The results prove (1). Therefore, as the number of connected links is increased, the required bitmap size in all of the allocation schemes is also increased.
4.2.3 The traffic amount
Fig. 4(c) shows the amount of traffic, which includes all beacon, allocation notification, and collision notification messages generated during beacon scheduling. The results show that LSB first generates the most amount of traffic. This increased traffic amount is caused by additional allocation messages due to collisions that occur during beacon allocation and because of beacon messages that are generated during a long association time. It is important to note that, in a mesh topology, the random scheme generates less traffic than the other two schemes. Since the random method randomly selects a vacant slot when a beacon bitmap is received, the collision ratio in the network is decreased. However, the performance is degraded in the case of a tree topology, which has few link connections, or a cluster topology, which has numerous link connections.
4.3 Summary
We verified that IEEE802.15.4e DSME beacon scheduling performs differently based on the SD allocation schemes applied. LSB first shows a superior performance for the required bitmap size. In fact, LSB first makes it possible to allocate all nodes with only 11 bits, even in a 10×10 mesh network. However, the experimental results revealed that LSB first generates too much traffic, and in particular, has a long association time. Therefore, this might lead to a large amount of energy being wasted during network construction time. The MSB shows the fastest association, but the required bitmap size is significantly increased along with the network size. The increased bitmap size expands the beacon frame size, thus lengthening the channel occupancy time. Eventually, it might bring an increase in the collision probability and error rates. Furthermore, the increased bitmap size brings about wasted memory resources, and it may eventually become impossible for some nodes to be allocated if the bitmap size exceeds 64 bytes. These limitations are not suitable for a large-scale network covering a wide area. The random scheme shows a slightly better performance in terms of the traffic amount, but it also demonstrates the worst performance in the association completion time and required bitmap size. Therefore, this scheme is not desirable as an SD allocation mechanism for DSME beacon scheduling. As a result, all SD allocation schemes have both strengths and weaknesses. Therefore, it is necessary to develop a new SD allocation mechanism that can accommodate all of these strengths.
5. Adaptive Superframe Duration Allocation
In this section, we describe an adaptive SD allocation (ASDA) algorithm for resource-efficient beacon scheduling that is based on the experimental results performed in the previous section. Since all of the methods (LSB first, MSB first, and random) perform bitmap-based SD allocation, they cannot overcome the limitations of the bitmap itself. Therefore, instead of using a bitmap, we attempted using a different approach for SD allocation utilizing a DNSI to manage neighboring scheduled beacon slots. In addition, the allocation notification message and collision notification message used in IEEE802.15.4e DSME are replaced with an allocated superframe notification message and superframe realignment message, respectively. First, each node initializes the DNSI value by ‘0,’ and the PAN coordinator sends its periodic extended beacon containing its current DNSI value. If node i receives an extended beacon from node j, it compares its current DNSI value with the DNSI value in the received beacon. If DNSI(i) <= DNSI(j), node i applies DNSI(i) = DNSI(j) + 1, and then broadcasts an allocated a superframe notification message containing the updated DNSI value and starts an allocation timer. The neighboring nodes that receive the allocated superframe notification message compare the DNSI value with its own DNSI. If node k receives an allocated superframe notification from node i, and DNSI(k) >= DNSI(i), node k sends a superframe realignment message with its current DNSI value to the originator. However, if DNSI(k) < DNSI(i), node k applies DNSI(k) = DNSI(i). Upon receipt of a superframe realignment message, node i restarts the allocation timer and compares its current DNSI value with the DNSI value received from node k. If DNSI(i) <= DNSI(k), node i applies DNSI(i) = DNSI(k) + 1, and then rebroadcasts the allocated superframe notification message containing the updated DNSI value. This process lasts until the allocation timer expires. As soon as the timer expires, the SD index value of node i is determined to be the current DNSI value. Through this iterative DNSI increment process, each node can allocate a unique SD index within two neighbors. This is because the DNSI value of the node, which has already completed allocation, represents the maximum DNSI value of their neighboring nodes, and the SD index value of a new node becomes a value greater than the maximum DNSI value out of all active neighboring nodes. Fig. 5(a)–(k) illustrate the process of beacon scheduling used in the proposed SD allocation algorithm; the final result of which is shown in (1). In this way, the proposed SD allocation scheme is simple, but it enables fully distributed beacon scheduling among the neighbor nodes. Furthermore, compared to the other SD index allocation algorithms based on a bitmap, the ASDA, which utilizes only a single variable, DNSI, can reduce the wasting of memory resources, as it requires only 1 or 2 bytes of memory space.
6. Performance Evaluations
In this section, a performance evaluation of the proposed ASDA is described, as compared to the LSB first, MSB first, and random methods. The ASDA experiments were conducted under the same experimental environment described in Section 3.
Fig. 6 shows variations in the association completion time of each algorithm with respect to a varying BO size of 64 to 512 bits. Note that the ASDA outperforms the LSB first and random schemes and shows a similar association completion time as the MSB first scheme, which has a superior performance. In addition, the results also demonstrate that the proposed scheme is rarely affected by a variation in the BO size, and the association of all of the nodes is complete within 670 ms for every BO size. Since the ASDA does not utilize a bitmap, and all of the nodes always select a vacant slot after the current ongoing superframe value for their SD index, an unnecessary delay until the next beacon interval might be removed.
Fig. 7 shows the comparative results of the ASDA, LSB first, and MSB first methods with respect to the required bitmap size. Since the random method leads to too much bitmap waste, as discussed in Section 3, it is excluded in this experiment. The results show that the ASDA outperforms even MSB first, which has a superior performance in terms of the required bitmap size. In fact, the ASDA allows 100 nodes to be allocated in just 4 bits at a BO size of 64 bits, and 7 bits at BO sizes of 128, 256, and 512 bits. On the other hand, the bitmap of LSB first is increased by 52 bits. This reduction in the required bitmap size is enabled by SD allocation utilizing a single variable of a fixed length (DNSI), rather than using a bitmap. For algorithms that use a bitmap, as the number of connected links is increased, the number of bitmaps is also increased as in (1), and the maximum bitmap size cannot exceed 512 bits (64 bytes). On the other hand, the ASDA can accommodate a maximum of 65,535 neighbors with only a single variable (DNSI) of 16 bits in length. Fig. 8 shows the comparative results with respect to the amount of traffic. The random method has the smallest amount of traffic, but is not desirable when considering other performance aspects, as discussed in the previous section. The results demonstrate that the ASDA generates a reasonable amount of traffic. As a result, the experimental results demonstrate that the ASDA, which overcomes the limitations of algorithms that depend on a bitmap, has a superior performance over the other methods in various aspects. In other words, the ASDA enables resource-efficient beacon scheduling.
7. Conclusion
In this paper, we emphasized the design and implementation of the SD allocation algorithm for resource-efficient beacon scheduling. In particular, it was demonstrated experimentally that the ASDA enables an energy-efficient association by reducing an unnecessary active waiting period for completing the association procedure of all of the nodes in the network; it minimizes memory utilization, which is necessary for beacon scheduling, by utilizing only a fixed-length single variable for representing neighboring SD indexes; and it saves more energy by generating a small amount of traffic during the beacon scheduling procedure. Therefore, it is expected that the several features of ASDA will provide a major contribution to the design of resource-efficient beacon scheduling for various applications that require an adaptive Low-Rate Wireless Personal Area Network (LR-WPAN).
