Abstract
The IEEE 802.15.4 standard provides Guaranteed Time Slot (GTS) mechanism for reliable transmission. GTS mechanism is suitable for transmitting time-sensitive data because it allocates time slots to a specific node. However, the GTS mechanism in the standard can be used only for one-hop communication. This paper proposes and implements a multihop GTS mechanism for reliable transmission in multihop networks. Simulation results using NS-2 show that low delay and high delivery ratio can be achieved using the proposed mechanism.
1. Introduction
Reliable communication in data networking is normally defined to ensure that there is no loss of data, that the packets are in the right order, that the delay is to an acceptable level, and that there is no duplication of packets. All this is to ensure that the data received is consistent, in order.
Many protocols used in wireless communication have mechanism in themselves for reliable communication. Retransmission and sequence number are generally used to guarantee the features of the reliable transmission of no loss of packets and of the packets in the right order, respectively. One example of providing acceptable delay is to allow a certain node to use media exclusively during a certain amount of time. In fact, the IEEE 802.15.4 guarantees acceptable delay using the Guaranteed Time Slot (GTS) mechanism.
The IEEE 802.15.4 standard, widely used in sensor networks, is a standard for low-speed, low-power, low-cost Wireless Personal Area Networks (WPANs). The IEEE 802.15.4 defines the physical layer (PHY) and medium access control (MAC) sublayer specifications for low-rate wireless personal area networks (LR-WPANs), which support simple devices that consume minimal power and typically operate in the personal operating space (POS) of 10 m or less. The nodes of the IEEE 802.15.4 standards basically contend with each other to gain a channel by using the carrier sense multiple access with collision avoidance (CSMA/CA) mechanism. The GTS mechanism is also supported in the beacon-enabled mode in order for a specific node to be able to use a channel exclusively during a certain time interval. Since a node can use a channel without contention by using the GTS, it can be applied to reliable transmission of data with a high priority in a stable way [1]. However, the GTS mechanism guarantees only one-hop communication with a PAN coordinator. Based on an application, a certain technology is required that should be able to transmit important and time-sensitive data reliably in the multihop network environment.
Transmitting a fire alarm signal can be a good example for that. The fire alarm signal can be delivered to a rescuer via a prereserved sensor network or via an alternative IEEE 802.15.4 network. If the paths from the node of sending the fire alarm signal to the sink node are composed of multiple hops, then the transmission of the fire alarm signal cannot be guaranteed using the currently defined GTS mechanism.
This paper proposes and evaluates a novel GTS allocation mechanism for the multihop path from a node to a sink node in the beacon-enabled network of the IEEE 802.15.4 standards.
The rest of the paper is structured as follows. In Section 2, the IEEE 802.15.4 GTS Mechanism standard is studied. Next, in Section 3, the related works and multihop communication using GTS are studied. Then, in Section 4, the proposed multihop GTS mechanism is provided. In Section 5, the simulations are performed using the NS-2 for evaluation. Finally, Section 6 concludes the paper with the closing remarks.
2. Overview of the IEEE 802.15.4
In this section, the necessary parts of the IEEE standards required for our work are overviewed.
2.1. Superframe Structure
The IEEE 802.15.4 standard specifies the physical layer and the MAC sublayer for low-rate wireless personal area network (LR-WPANs) [1]. The MAC protocol in IEEE 802.15.4 can operate both in a beacon-enabled and in a non-beacon-enabled mode. The operation mode is determined by a single central controller termed the PAN coordinator. Basically, media access is contention based (slotted or unslotted CSMA/CA); however, in the beacon-enabled mode, Guaranteed Time Slots can be allocated by the PAN coordinator exclusively to devices willing to transmit time-sensitive data or data requiring specific bandwidth reservation. The allocated device transmits a data frame without checking the channel if it is idle or not; that is, fast transmission is possible because there is no processing delay for the CSMA/CA mechanism. In beacon-enabled mode, beacon frames are periodically sent by the PAN coordinator every Beacon Interval (BI) to identify its PAN, to synchronize associated devices, and to describe the superframe structure (Figure 1), comprising an active period and, optionally, an inactive period. The active period, corresponding to the Superframe Duration (SD), is divided into 16 equally sized time slots, during which data transmission is allowed. SD cannot exceed the BI. Each active period can be further divided into a Contention Access Period (CAP) and an optional Contention Free Period (CFP), composed of GTSs. Slotted CSMA/CA mechanism is used within the CAP. The slotted CSMA/CA mechanism is implemented using unit of time, called backoff period, whose unit length is defined as the aUnitBackoffPeriod.
An example of the superframe structure.
The structure of the superframe is described by the values of the macBeaconOrder (BO) and the macSuperframeOrder (SO). The value of BO describes the BI at which the coordinator shall transmit its beacon frames. The value of SO describes the length of the active period of the superframe which is referred to as SD. Two values are in 0 ≤ SO ≤ BO ≤ 14. If it is operated as non-beacon-enabled mode and it has not superframe structure. BI and SD can be expressed as follows:
The aBaseSuperframeDuration constant denotes the minimum length of the superframe when BO equals 0. The standard fixes this duration to 960 symbols (one symbol corresponds to 4 bits, assuming the 2.4 GHz frequency band and 250 kbps of bit rate).
2.2. GTS Mechanism
A GTS allows a device to operate on the channel within a portion of the superframe that is dedicated (on the PAN) exclusively to that device. The concept of a GTS allocation is similar to a Time Division Multiple Access (TDMA). A GTS is allocated only by the PAN coordinator, and it is used only for communications between the PAN coordinator and a device. A single GTS may extend over one or more superframe slots. The PAN coordinator may allocate up to seven GTSs simultaneously, provided there is sufficient capacity in the superframe.
GTS management is undertaken by the PAN coordinator. The PAN coordinator needs to be able to store all the information necessary to manage seven GTSs to facilitate GTS management. For each GTS, the PAN coordinator stores its starting slot, length, direction, and associated device address. For each allocated GTS, the device stores its starting slot, length, and direction. Like the transmission during a CAP, an acknowledgement is occasionally required optionally for a data frame transmission during a GTS.
The device that wants a GTS allocation sends a GTS allocation request command frame to the PAN coordinator in a CAP. Upon receiving a GTS allocation request, the PAN coordinator checks whether there are sufficient resources and, if possible, allocates the requested GTS. When the PAN coordinator determines whether capacity is available for the requested GTS, it generates a GTS descriptor with the requested specifications and the short address of the requesting device. The allocation of the GTS cannot reduce the length of the CAP to less than aMinCAPLength (440 symbols). If the GTS was allocated successfully, the PAN coordinator sets the start slot in the GTS descriptor to the superframe slot at which the GTS begins and the length in the GTS descriptor to the length of the GTS [1].
If there was not sufficient capacity to allocate the requested GTS, the start slot is set to 0 and the length to the largest GTS length that can currently be supported. The PAN coordinator then includes this GTS descriptor in its beacon and updates the GTS specification field of the beacon frame accordingly. When a device receives a beacon frame including the GTS descriptor which corresponds to the macShortAddress of the device, it judges the success or failure of the GTS allocation by checking whether the GTS starting slot is 0. Note that a device to which a GTS has been allocated can also transmit during the CAP. Figure 2 shows a simple example of the GTS mechanism in the IEEE 802.15.4.
GTS mechanism in the IEEE 802.15.4.
3. Related Works
3.1. GTS Mechanism Improvements
Even though the GTS mechanism of the IEEE 802.15.4 standards provides reliable communication, it hardly meets the requirements of various real-time applications. There have been several research works on its improvement.
Reference [2] proposes a D-GTS (Dynamic GTS) allocation algorithm for both the efficient use of the GTS and the periodic message transmission. D-GTSs are allocated at regular intervals in the CAP. Its length is determined not by an alternative superframe slot unit but by its backoff period unit. References [3, 4] reduce the waste of the channel bandwidth by dividing the length of a GTS further to smaller than a superframe slot. With smaller slots, GTS utilization in the new scheme is better than that in the standard scheme. Reference [5] proposes a method that allocates the GTS with higher priority first after classifying the priorities of the requests of GTSs. This allows GTSs to be allocated first for real-time applications by letting them to have higher priorities. Reference [6] proposes an implicit GTS allocation mechanism where a GTS is shared by several nodes in round-robin way. It overcomes the number of the concurrently allocatable GTSs and the underutilization of GTS bandwidth.
Most of the previous works focus on the reduction of the waste and the efficient use of the GTSs. Those works guarantee the reliability only for one-hop communication as in the GTS mechanism of the IEEE 802.15.4 standard. On the contrary, our work is on guaranteeing the reliability of not only single-hop but also multihop communication.
3.2. Multihop Communication
On a beacon-enabled PAN, a coordinator that is not the PAN coordinator maintains the timing of both the superframe in which its coordinator transmits a beacon (the incoming superframe) and the superframe in which it transmits its own beacon (the outgoing superframe). The relative timing of these superframes is defined by the StartTime parameter. The relationship between incoming and outgoing superframes is illustrated in Figure 3. The BO and SO is equal for all superframes on a PAN. All devices interact with the PAN only during the active period of a superframe [1].
The relationship between incoming and outgoing beacons [1].
Communication among several PAN coordinators should be possible in the multihop beacon-enabled network. However, there is no specific procedure on how to communicate among coordinators in the IEEE 802.15.4 standard. Reference [7] presents and analyzes nonacknowledged GTS option for interconnection of IEEE 802.15.4 beacon-enabled network cluster using ordinary network nodes as bridge nodes. A bridge node periodically visits source and sink cluster and exchanges data using GTS access as shown in Figure 4. While the communication among the coordinators using different channels is studied in [7], the direct communication using the same channel without the help of a bridge node is studied in our work. The communication among the coordinators using a same channel is shown in Figure 5.
Intercluster communication using a bridge [7].
Communication between two coordinators using a same channel.
In Figure 5(a), arrow represents association direction. The coordinator at the beginning part of the arrow is child while the coordinator at the ending part is parent. In Figure 5(b), dotted rectangles represent the incoming superframes and other rectangles are the outgoing superframes. The child coordinator transmits data frame in the active period of the parent coordinator. If the parent coordinator has data to transmit to the child coordinator, it indicates in the network beacon that the data are pending. When the child coordinator receives beacon and confirms that there exist data that are pending, it transmits a MAC command, requesting data in the CAP. After the parent coordinator transmits the ACK, it transmits the pending data. This procedure is the same as the one for communication between coordinator and device in the IEEE 802.15.4 standards. In this study, the PAN coordinator is regarded as parent coordinator while device is considered to be child coordinator. Then, as the case in the standards, it is assumed that allocation is made for transmitting the GTS and receiving the GTS, and the CFP performs communication.
Reference [8] analyzed feasibility of IEEE 802.15.4 multihop beacon-enabled network and demonstrated that the 802.15.4 multihop beacon-enabled network was feasible when the BO was larger than 1 and when distribution of coordinators was not too dense under low traffic load. In particular, if the BO was 4 or higher, occurrence of beacon collision did not increase even though the number of coordinators increased, which resulted in low lost synchronization probability. (In the experiment, a coordinator starts the beacon transmission at random time.) Since all coordinators in the same network have the same value of the BO as that of the SO, the beacon interval is equal. However, the active period should not be overlapped in order to avoid beacon collision between coordinators. In the IEEE 802.15.4 standards, there is no clear description on how to avoid collision of beacon frames with each other and data frames with each other. Reference [9] introduced several methods to solve the problems on beacon collision, and compared the two most popular ones. This paper does not cover resolving problems on beacon collision.
4. Multihop GTS Mechanism
4.1. BO, SO for Multihop Communication Using the GTS
For prevention of coordinators, which can receive beacons of others, from having their active periods overlapped with one another, it is required to ensure that the value of the BO that determines beacon interval should be larger enough than that of the SO. The values of the BO and the SO determine the number of coordinators that enables intercommunication in a dense state. As shown in the Section 2.1, SD is the same with the active period and both of the BI and the SD are the multiples of aBaseSuperframeDuration. If the BO is larger than the SO by as much as 1, the active period is half of the beacon interval. In this case, two active periods in maximum can exist during one BI.
The number N of coordinators available for communication, as coordinators can receive beacons of others and the active period is not overlapped with those of others, can be calculated in the equation following.
Since the BO is larger than or equal to the SO, N has the value of exponential multiplication of 2 such as 1, 2, 4, 8, and 16. For example, when the BO is 3 and the SO is 1, N is 4. Therefore, four coordinators can communicate with each other without their active periods overlapped. In our work, the number of the coordinators that can receive the beacons of the others is assumed to be no more than N.
4.2. Propagation of the Sink Node Information
In the IEEE 802.15.4 standards, it is explained that only PAN coordinator allocates and manages the GTS. And the GTS is used only for communication between the PAN coordinator and a device. However, it is assumed in this study that the coordinator that is not the PAN coordinator allocates the GTS for multihop GTS allocation and that the GTS is used for communication.
A node is required to find out sink node address first if it intends to be allocated with multihop GTS for communication. The sink node address starts to be propagated as the sink node sends sink notification command frame to its parent coordinator. Figure 6 shows the sink notification command frame format. Addressing field contains destination PAN ID and source address. The 16-bit short address is used for address. In order to indicate sink notification command frame, the value of command frame ID field is set at 0x0a that is not used as the standards. When the coordinator receives such frame, it transmits ACK frame.
Sink notification command frame format.
Afterward, the coordinator maintains the sink node information for allocation of multihop GTS. This information includes sink address, next hop address, hop count, and valid time. Next hop address means the address of the next hop for delivering data to the sink node. The coordinator that received the sink notification command frame saves the source address of the sink notification command frame to the sink address and the next hop address. Hop count means the hop count up to the sink address. In this case, 1 is saved. Valid time means the valid time of the sink node information. The value of the valid time is set at the constant value of aMaxSinkInfoValidTime when the sink node information is received for the first time. The default value for aMaxSinkInfoValidTime is set to 4, and the value will become a larger one in the environment where there is much noise or there is possibility for collision.
The coordinator that has the sink node information transmits the beacon frame that includes the sink address and the hop count. And the coordinator decreases the value of the valid time by 1 for every transmission. If the value of the valid time is 0, the coordinator deletes the sink node information and stops transmitting it. The sink node transmits a sink notification command frame at every superframe in order for the sink node information of its parent coordinator not to be deleted. The valid time has two purposes. First, the coordinator stops to transmit the gradually sink node information when the sink node disappears in order to deallocate the allocated GTSs. Second, it prevents the immediate deallocation of the allocated GTSs when a child coordinator cannot temporarily receive the beacon from the parent coordinator.
Figure 7 shows the modified beacon frame format. The sink info field is located next to the GTS fields. The sink info format shown in Figure 8 consists of the sink address of 2-octets and the hop count of 1-octets. The GTS specification field in the beacon frame was changed as shown in Figure 9. The sink info available field is used to indicate that the sink info field is included in the beacon frame. And it uses 1-bit among 4-bit reserved.
Modified beacon frame format.
Sink info field format.
Modified GTS specification field format.
The coordinator that received the beacon frame that included the sink node information of other coordinator sets the next hop address of the sink node information at the address of the coordinator that transmitted the beacon frame before saving the setting. The hop count adds 1 to the received value before saving it. The value of valid time is reset at the constant value of aMaxSinkInfoValidTime when the sink node information is received from the same source.
In this process, every coordinator sends the beacon with sink node information and every node knows the address of the sink node in the network. Figure 10 shows a simple example of the process.
An example of propagation of the sink node information.
4.3. Multihop GTS Allocation and Deallocation
After the sink node information is propagated through coordinators in the network, the node that intends to transmit data to the sink node can be allocated with multihop GTS. In order to be allocated with the multihop GTS, the node transmits multihop GTS request command frame to parent coordinator. Figure 11 shows the multihop GTS request command frame format. Addressing field contains destination PAN ID and source address. In order to indicate multihop GTS request command frame, the value of command frame ID field is set at 0x0b that is not used as the standards. GTS characteristics field is identical to the standards, and the sink address field was added. When coordinator receives such frame, it transmits ACK frame.
Multihop GTS request command frame format.
The coordinator that received the multihop GTS request frame checks if the sink address received from the node is identical to the saved address. And it determines whether or not it allocates the multihop GTS on the same basis as when it determines allocation of the GTS following the standards. If the coordinator can allocate multihop GTS, it informs the node of allocation by using GTS descriptor in a beacon frame. There is no beacon indication that the allocated GTS is for multihop or not. However, the coordinator distinguishes the allocation information of the GTS from that of the multihop GTS before saving it. This is for delivering a data frame from a child node during a multihop GTS to the next hop using the multihop GTS. And then, the coordinator transmits the multihop GTS request command frame to the coordinator that indicates the next hop of the saved sink node information before getting allocated with the multihop GTS. When this procedure is repeated, the parent coordinator of the sink node receives the multihop GTS request command frame in the end. This coordinator, having the sink node information that the next hop is identical to the sink address, allocates the GTS for reception to the sink node. When all of the coordinators on the path from the source node to the sink node can allocate the GTS, allocation of the multihop GTS comes to an end successfully.
When a source node wants the deallocation of the multihop GTS, it transmits the multihop GTS request command frame to the parent coordinator. In that case, the value of the character type of the GTS characteristics field is set to 0 for the deallocation. This complies with the standard. However, the operation after the parent receives this command frame differs. The coordinator deallocates the multihop GTS that has been allocated to the source node and then transmits a multihop GTS request command frame to its parent node as well. Like the allocation, the deallocation of a multihop GTS is sequentially executed from a source node to the parent coordinator of a sink node.
4.4. Communication Using a Multihop GTS
The source node allocated with the multihop GTS transmits data to a parent coordinator in the CFP. When the coordinator receives data during the multihop GTS that has been allocated to a child node, it checks the next hop of the sink node information. Then the coordinator relays the data using the multihop GTS allocated from the parent node.
In this case, the data frame does not go up to the upper layer but directly replaces source address with its own address and destination address with the next hop. If the destination of the received data frame is not the sink node, the data frame is sent to the upper layer for routing. The parent coordinator of the sink node uses the allocated GTS for reception to transmit data to the sink node. Figure 12 shows an example of the GTS mechanism when the sink is 3 hops away from the source node.
An example of the multihop GTS mechanism.
5. Evaluation
In this section, the reliability of the multihop GTS is evaluated using NS-2.
5.1. Simulation Environment
The parameters used in the simulation are shown in Table 1. The routing protocol is not used in the simulation to prevent any effect of multihop routing paths on performance. Similarly, the ARP is not enabled. The beacon order is set to 5, and the superframe order is set to 3. When this value is substituted in the expression (2), four coordinators in maximum can communicate with each other without overlapping their active periods when receiving the beacons of each other. Every coordinator including the PAN coordinator sets to the same BO and SO value. It is also assumed that a beacon is transmitted after the active period of their parent coordinator in order for the active period not to be overlapped.
Simulation parameters.
The simulation considers a situation where the time-sensitive data such as fire alarms are recurrently transmitted. Figure 13 shows the topology for the simulation. Node A in Figure 13 is the node that transmits time-sensitive data. The RFDs except Node A periodically transmit normal data frames to sink nodes. All the nodes are separated 5 meters away from each other and can sense the carrier signals of the nodes in diagonals. Every coordinator has four child nodes.
Experiment scenario.
The simulation compares the cases where node A uses the slotted CSMA/CA and the multihop GTS. In the first simulation, the performance of various hop counts by changing the numbers of the intermediary coordinators is evaluated. In the second simulation, the performance of various number of the contending nodes by changing the number of the child nodes of a coordinator is evaluated. The hop count is fixed as 4.
The simulation runs for 300 simulation seconds. The results after 100 seconds are used for the evaluation, considering the association time and the multihop GTS allocation.
5.2. Simulation Result
Figure 14 shows the end-to-end delay for various hop counts. The result shows that the delay of using a multihop GTS is smaller by about a half for 3-hop case and by about 1/15 for 8-hop case than that of using the slotted CSMA/CA.
End-to-end delay of hop count.
The amount of the delay increment corresponds to the length of the beacon interval. This is because the coordinator should wait for the active period of the parent in order to transmit the received data from a child node to the parent node. This applies to the case of using the slotted CSMA/CA in the same way. However, the delay increases much due to the fact that the use of a channel is possible only by contention among the contending nodes.
While the variance of the end-to-end delay is big when using the slotted CSMA/CA, there is not much change when using the multihop GTS. In order to guarantee the acceptable delay, the delay not only should be small, but also should be its variance. Figure 14 shows that the slotted CSMA/CA in multihop networks does not meet such requirement.
Figure 15 shows the packet delivery ratio of various hop counts. While the delivery ratio decreases as the number of the hop counts increases when using the slotted CSMA/CA, all the transmissions are successful when using the multihop GTS. This result shows that the stable transmissions of data are possible if there is no bit error. Contending situations often occur when the slotted CSMA/CA is used in multihop networks. Contentions can cause collisions, which makes reliable data transmissions difficult.
Packet delivery ratio.
Figure 16 shows the end-to-end delay of various numbers of the child nodes of an intermediary node. When the number of the child nodes of a coordinator increases, so does the number of the contending nodes trying to use a sharing channel. However, this applies only to the slotted CSMA/CA. In case of the multihop GTS, the increment of the number of the nearby nodes does not affect the delay, because a channel can be exclusively allocated to a node for a time interval.
End-to-end delay of the number of child nodes.
6. Closing Remarks
Previous research on the GTS of the IEEE 802.15.4 has been focusing on increasing utilization and reducing the waste of bandwidth. However, the GTS of the current IEEE standard has a drawback that does not guarantee the reliable transmission in multihop networks. The multihop GTS mechanism introduced in this paper provides the guarantee on the reliable transmission for multihop networks. According to the results using NS-2, low end-to-end delay and high delivery ratio can be checked. The proposed mechanism is especially suitable for delivering time-sensitive data thanks to its feature that the end-to-end delay is low and its variance is small regardless of various numbers of the hop counts.
Footnotes
Acknowledgment
The present research has been conducted by the Research Grant of Kwangwoon University in 2010.