Sage Journals: Discover world-class research

Abstract

In this article, we propose a time division multiple access scheduling algorithm for end-to-end on-time packet delivery in multi-hop wireless sensor networks. Our proposed algorithm establishes a new communication path to substitute the old path including the link failed and schedules communication links on the new path by allocating timeslots satisfying end-to-end delay bound. Max–min optimization is employed to maximize the number of dedicated timeslots to establish the substitute path in the event of the next link failure. We evaluate the performance of the proposed algorithm using QualNet network simulator and compare it with the performance of the algorithm that minimizes the end-to-end delay. Our numerical results show that the path survival ratio of the proposed algorithm is approximately two times higher when large number of communication links fails. In addition, we apply the global recovery and local recovery schemes to observe the increase in the overhead message exchanges. Compared to the global recovery scheme, local recovery scheme requires six times less control messages to establish the substitute path when a small number of link failures occur, whereas more than 90% communication paths survive.

Keywords

Wireless sensor networks time division multiple access timeslot scheduling link failure recovery multi-hop networks IEEE 802.15.4e

Introduction

Advances in information and communication technology (ICT) have led to widespread changes in human and economic activity over the past decade. Wireless sensor network (WSN) has emerged as one of the most popular technologies in the ICT industry. A WSN consists of a number of low-cost wireless devices deployed over a geographical area to exchange information without direct human interventions. Typically, wireless devices in WSNs are inexpensive, battery-powered, and operated for years. While WSN applications need to cover large geographical area, the communication range of a device is short mainly due to battery-powered limited transmission. To overcome the limitation on the short communication range, sensor information originating from a source device is relayed to a destination device on end-to-end basis at the cost of transmission delay. The end-to-end transmission delay is a critical issue in industrial applications where sensor information with long delay may be outdated and lead to wrong decisions.¹ Thus, end-to-end transmission delay should be carefully considered for delay-sensitive services such as industrial applications.

Standardization activities for WSNs have been conducted by many standard development organizations including IEEE, IETF, ITU-T, and ISA.² IEEE standards association published IEEE 802.15.4:2006³ PHY/MAC specification for low-rate wireless personal area networks (WPANs) in 2006. IEEE 802.15.4 standard has been widely adopted as the specification for PHY/MAC communication layers for many WSN standard specifications including 6LoWPAN,⁴ WirelessHART,⁵ ISA-100.11a:2009,⁶ and ZigBee.⁷ IEEE 802.15.4 standard is a lightweight, power-efficient PHY/MAC protocol for exchanging packets with small payload sizes. However, the standard is not suitable for the services demanding on-time packet delivery in multi-hop environments such as industrial applications, since the carrier sense multiple access with collision avoidance (CSMA/CA) scheme introduces random delay in channel access and the delay accumulates in an unpredicted manner as the number of hop increases. In addition, single channel operation further aggravates channel interferences among the devices in the network. Recently, IEEE 802.15.4e:2012⁸ has amended IEEE 802.15.4 MAC to improve radio frequency (RF) link reliability and ensure determinism for channel access. IEEE 802.15.4e employs time division multiple access (TDMA) as a reservation channel access with multiple frequency channels to support on-time packet delivery in multi-hop environments.

Scheduling packet transmission plays crucial role in TDMA-based wireless networks to meet the service requirements. There have been significant research efforts on transmission scheduling for wireless multi-hop networks. IETF WG IPv6 over the time slotted channel hopping (TSCH) mode of IEEE 802.15.4e (6TiSCH) has developed the 6TiSCH operation sublayer (6top) located between IEEE 802.15.4e TSCH MAC sublayer and 6LoWPAN sublayer.⁹ The 6top sublayer employs a distributed timeslot allocation method based on information of bandwidth required by neighbor devices to use communication resources effectively. Also, a randomized timeslot allocation method is introduced to minimize end-to-end transmission delay in a distributed manner.¹⁰ These distributed algorithms do not need knowledge of global network topology to schedule timeslots, which results in low complexity. However, scheduling with local information may cause conflicts in transmissions; thus, distributed algorithms may not be suitable for industrial applications requiring reliable communications. On the other hand, the centralized scheduling algorithm globally optimizes the transmission schedule for all links in the network.^11–14 In the previous works, communication graph model is employed to schedule timeslots for link transmission in multi-hop environments.^11–13 The max–min optimization is used in the scheduling to minimize the maximum end-to-end transmission delay among all communication paths by employing conflict graph model,¹¹ while a scheduling algorithm to minimize time span from the earliest link transmission to the last link transmission for all communication paths is proposed.¹² Signal to interference and noise ratio (SINR) graph model is proposed to maximize throughput of wireless mesh networks.¹³ Also, meta-heuristic algorithms such as simulated annealing (SA) and particle swarm optimization (PSO) are considered to satisfy end-to-end transmission delay bound for all multi-hop paths.¹⁴ Performance of wireless networks is strongly influenced by signal interference between devices sharing the same frequency band and network topology changes due to mobility. According to previous studies,^15–17 it is observed that signal interference, which seriously degrades network performance, is caused not only by devices using the same communication protocol but also between devices using different communication protocols sharing the frequency band. Moreover, movement of the device or adjacent object causes abrupt changes in the received signal strength, which makes some devices unreachable to the network. Signal interference and mobility may make a communication link unusable, which is referred as link failure.

Link failure results in packet loss and may require packet retransmission over the communication path. Therefore, the link recovery mechanism should be used to recover from a failed communication path in wireless networks prone to link failures. Routing protocols with recovery process have been studied for wireless ad-hoc networks.^18–21 Recovery process establishes new path to substitute the old path including the link failed. As a method to establish the substitute path, the destination device initiates new path establishment procedure when quality of service (QoS) violations are detected, and the source device switches to the new parent chosen by the destination device.¹⁸ On the contrary, the transmitting device of failed links chooses new parent device and initiates new route path establishment procedure in some routing protocols.^19–21 Routing protocol for low-power and lossy networks (RPL) developed by IETF WG Roll provides two recovery mechanisms, global and local recovery mechanisms.²² In the global recovery mechanism, the network coordinator reschedules communication links over the entire network if the link failure is detected, while new end-to-end path is established in a distributed manner if the local recovery mechanism is applied. A transmission scheduling algorithm is proposed to recover the link failure in TDMA networks.²³ The algorithm uses a fixed number of dedicated timeslots to establish a substitute path and to schedule transmission order to reduce the end-to-end packet delivery delay. Since the number of dedicated timeslots cannot be changed during network operation, large amount of delay can be introduced as the number of link failures increases.

In this article, we propose a transmission scheduling algorithm for on-time packet delivery in multi-hop wireless networks prone to link failures. In industrial applications, sensor information should be reliably delivered to the target devices to ensure the proper functioning of each facility. To this end, we employ a centralized scheduling algorithm to optimize the end-to-end transmission order of the entire communication path in the network. In the proposed algorithm, a network coordinator schedules timeslots and frequency channels for all communication links in the network. The algorithm recovers from link failures by allocating timeslots and frequency channels to achieve conflict-free transmissions without wireless interferences originating from other devices. Theoretically, all timeslots not occupied by links can be used to recover from link failures. However, some unoccupied timeslots are not available to establish the substitute path, since allocating those timeslots could result in delay larger than the end-to-end delay bound. In our study, unoccupied timeslots, which satisfy the end-to-end delay bound condition and conflict-free transmission condition, are referred as dedicated timeslots. The proposed algorithm maximizes the number of dedicated timeslots to recover from link failures. To this end, the algorithm schedules the current transmission order to maximize the number of dedicated timeslots when the next link recovery occurs. We employ multi-superframe structure of IEEE 802.15.4e deterministic and synchronous multi-channel extension (DSME) MAC to schedule timeslots. The multi-superframe structure supports TDMA-based channel access with multiple frequency channels for packet transmissions; therefore, the frame structure is suitable for the delay-sensitive services such as industrial applications requiring on-time packet delivery. We define control layer on top of IEEE 802.15.4e MAC layer to schedule end-to-end transmissions satisfying end-to-end delay bound.

The rest of the article is organized as follows. In section “Overview of IEEE 802.15.4e DSME MAC and DSME control layer protocol,” we briefly introduce the IEEE 802.15.4e DSME MAC specification and the DSME control layer protocol and explain how transmission schedules are shared among devices in the network. In section “System model,” a transmission schedule model in a multi-channel TDMA network is introduced to provide on-time packet transmissions. A TDMA scheduling algorithm is proposed to achieve on-time packet delivery in multi-hop environments prone to link failures in section “Transmission scheduling algorithm for link recovery.” In section “Performance evaluation,” we evaluate the network performance of the proposed algorithm under various simulation scenarios. Finally, we conclude our study in section “Conclusion.”

Overview of IEEE 802.15.4e DSME MAC and DSME control layer protocol

IEEE 802.15.4e MAC specification was released in 2012 that enhanced and added functionality to the existing IEEE 802.15.4 MAC specification. IEEE 802.15.4e defines several MAC operation modes, such as DSME, TSCH, low latency deterministic network (LLDN), and radio frequency identification blink (BLINK). The first three MAC operation modes are mainly intended to support industrial monitoring and process automation, while the BLINK MAC mode is designed to support item/people identification, location, and tracking. Among these MAC operation modes defined by IEEE 802.15.4e standard, the DSME MAC mode runs on a beacon-enabled network so that all devices are time synchronized using timing information from periodic beacons. The DSME MAC mode guarantees determinism for channel access based on a time synchronized frame structure and supports multiple frequency channel operation by employing channel diversity schemes such as channel hopping and channel adaptation. In this section, we first introduce timing synchronized structure of DSME MAC described by IEEE 802.15.4e standard. Then, we describe DSME control layer protocol exchanging transmission schedule between the devices in the communication paths.

Multi-superframe structure of DSME MAC

Devices in a DSME-enabled network exchange frames based on time synchronization structure known as multi-superframe. The multi-superframe structure consists of multiple superframes defined by IEEE 802.15.4 standard. In a superframe, 16 timeslots of equal time duration are dedicated for exchanging frames. The first timeslot of the superframe called beacon period is dedicated for beacon transmission, and the rest of timeslots following the beacon period are used to exchange MAC frames by either random channel access or reservation-based channel access. The portion of the superframe for random channel access following the beacon period is called contention access period (CAP), and the portion of the superframe following the CAP is called contention free period (CFP). The CFP consists of seven timeslots and a frequency channel is selected among the available frequency channels to exchange MAC frames in each timeslot. MAC command frames are exchanged using a predetermined frequency channel in the CAP, while MAC data frames requiring on-time packet delivery are sent in the CFP by allocating timeslots and frequency channels.

The multi-superframe structure is fully described by beacon order (BO), multi-superframe order (MO), and superframe order (SO) parameters defined by IEEE 802.15.4e standard. There are $2^{BO - MO}$ multi-superframes in the structure and $2^{MO - SO}$ superframes are in a multi-superframe. Figure 1 illustrates an example of the multi-superframe structure of IEEE 802.15.4e DSME MAC. We assume that the values of BO and MO are equal to 6, the value of SO is 4, and the multi-superframe structure consists of four superframes illustrated in the example.

Figure 1.

Multi-superframe structure in IEEE 802.15.4e.

DSME control layer

IEEE 802.15.4e DSME MAC defines the multi-superframe structure for transmission of MAC frames. MAC data frames containing the sensor information are sent in the CFP of the multi-superframe structure. Since the length of the timeslot is fixed, the position of the timeslot relaying the frame from the source device to the destination device determines the transmission delay of the end-to-end packet transmission. Therefore, transmission scheduling of timeslots for the links in the communication path is necessary to guarantee on-time packet delivery. In this section, we define DSME control layer as the next upper layer of the DSME MAC and describe the control message exchange procedure for transmission scheduling of the links in multi-hop environments. Figure 2 shows DSME communication protocol stack including the DSME control layer based on the IEEE 802.15.4e DSME MAC. The DSME control layer manages transmission schedules by scheduling transmissions of links and exchanging control messages to support on-time packet transmissions.

Figure 2.

Structure of DSME communication protocol stack.

DSME control layer is designed for a centralized scheduling procedure that a network coordinator schedules communication resources for entire network configurations. A device requiring a transmission schedule sends a message indicating a transmission schedule request to the network coordinator, and the network coordinator generates a transmission schedule for all the links in the path upon the receipt of request message. We define three control messages, CLME-ALLOC.request, CLME-ALLOC.response, and CLME-ALLOC.notify, to describe the message exchange procedures. First, all source devices in the network send the CLME-ALLOC.request message to the network coordinator in the CAP of multi-superframe structure for network initialization. The request message includes MacAddr, NumSlot, and MaxDelay fields. The MacAddr field is the list of the MAC addresses of the devices, NumSlot field represents the required number of timeslots to schedule, and MaxDelay field indicates the end-to-end delay bound. If the source device is deployed nearby the network coordinator, the message is directly delivered to the network coordinator. However, relay devices are typically deployed between the source device and the network coordinator in multi-hop environments. In this case, the source device selects the relay device to forward the message. The relay device broadcasts the beacon frame including hop-counts from the network coordinator. If the source device receives the beacon frame from relay devices, the source device creates a list of relay devices transmitting beacons. Then, the source device selects the relay device with the smallest hop-count in the list to establish the shortest path and sends the request message to the selected relay device. Each relay device adds its MAC address to the MacAddr field of the received CLME-ALLOC.request message and forward it to the next device in the communication path. The request message is forwarded until the network coordinator receives the message successfully. Upon the receipt of CLME-ALLOC.request messages from all source devices, the network coordinator recognizes entire network topology from the MAC address list in the MacAddr field. Also, the request message is transmitted to the network coordinator when the link failure occurs. We assume that a communication link fails if the transmitting device does not receive an acknowledgement (ACK) frame from the receiving device after sending a data frame. If the communication link fails, the transmitting device of the failed link selects another device as a parent device and sends CLME-ALLOC.request message to the new parent device. Upon the receipt of the request message, the relay device forward the message to the network coordinator. Therefore, the network coordinator recognizes that the link failure has occurred in the network by receiving the request message.

The network coordinator schedules timeslots and frequency channels for the communication links of the devices listed in the MacAddr fields of the received CLME-ALLOC.request message. The transmission schedule is generated to satisfy the end-to-end delay bound specified in the MaxDelay field of the message. If the transmission schedule of the all the communication links is successfully generated, the network coordinator sends the CLME-ALLOC.response message including the transmission schedule in the CAP to the source device. The CLME-ALLOC.response message includes an AllocInfo field that describes the transmission schedules of the communication link. If a relay device receives the CLME-ALLOC.response message successfully, the device retrieves its transmission schedule from the AllocInfo field and forward the message to the next device in the communication path. This message is forwarded until the source device retrieves its transmission schedule from the CLME-ALLOC.response message.

Upon the receipt of CLME-ALLOC.response message from the network coordinator, the source device sends a CLME-ALLOC.notify message to the network coordinator to confirm that the transmission schedule is successfully assigned for all links in the communication path. This message is forwarded to the next device in the path until the network coordinator receives the CLME-ALLOC.notify message successfully. Unlike the other messages, the CLME-ALLOC.notify message is forwarded via timeslots and frequency channels assigned in the CFP. Upon the receipt of CLME-ALLOC.notify message, the network coordinator confirms that the timeslot and frequency channel corresponding to the transmission schedule has been successfully allocated to all devices on the communication path.

Figure 3 illustrates how the source device and the network coordinator on the communication path exchange the control messages. We assume that a relay device is deployed between the source device and the network coordinator, and MAC addresses of the source device and the relay device are 1 and 2, respectively. In this example, the network coordinator schedules four communication links (i.e. an incoming link and an outgoing link of the relay device and those of the source device). If four links are scheduled successfully, the network coordinator sends the CLME-ALLOC.response message including the transmission schedule to the source device. There are two AllocInfo fields in the CLME-ALLOC.response message. The first AllocInfo field (i.e. AllocInfo[0]) represents the transmission schedule for the incoming and outgoing links of the relay device, and the second AllocInfo field (i.e. AllocInfo[1]) describes the transmission schedule for the incoming and outgoing links of the source device. Upon the receipt of the response message, the relay device retrieves its transmission schedule from the AllocInfo[0] field and forward the message to the source device. Similarly, when the source device receives the message from the relay device, it retrieves its transmission schedule from the AllocInfo[1] field.

Figure 3.

Transmission schedule control message exchange procedure: (a) CLME-ALLOC.request message exchange procedure, (b) CLME-ALLOC.response message exchange procedure, and (c) CLME-ALLOC.notify message exchange procedure.

System model

In this section, we present the transmission schedule model in a multi-channel TDMA network to provide end-to-end on-time packet transmissions. In the multi-channel TDMA network, all timeslots are time synchronized and orthogonally divided in the time and frequency domains. The source device transmits a packet to the destination device by relaying the packet over the assigned timeslot and frequency channel, and the incoming and outgoing links of the device are distinguished by assigning them to different timeslots. In our analysis, we assume that communication links within a two-hop distance are in conflict. We describe conflict-free transmission schedule conditions that avoid conflicts in packet transmissions among links, while satisfying end-to-end delay bound in multi-hop environments. In a single channel network, transmission from a device may interfere with the reception of packets from its neighbor devices, which causes packet reception failure. Thus, a communication link interfering with transmissions of neighbor devices should be assigned to different timeslots to avoid packet reception failure from neighbor devices. Meanwhile, simultaneous transmissions are available in a multi-channel network without interfering with each other by allocating different frequency channels. However, simultaneous transmissions of adjacent links are not allowed, even if they allocate different channels, since the device does not transmit and receive the packet simultaneously.

Figure 4 illustrates the conflict-free transmissions in single channel operation and multi-channel operation. We assume that the ith link $e_{i}$ and jth link $e_{j}$ are in conflict. Let us denote that $π_{i}$ , $f_{i}$ , and $Δ_{i}$ are the timeslot index, the frequency channel index, and the number of timeslots allocated to $e_{i}$ , respectively. Figure 4(a) shows the conflict-free transmissions in a single channel operation. To avoid conflict of the link transmissions, transmission of $e_{j}$ is not allowed before completion of transmission of $e_{i}$ , and transmission of $e_{j}$ should be terminated before transmission of $e_{i}$ in the next frame structure starts. On the other hand, the transmission of $e_{j}$ is available regardless of the transmission of $e_{i}$ in multi-channel operation as illustrated in Figure 4(b). However, simultaneous transmissions of $e_{i}$ and $e_{j}$ are not allowed due to the nature of half-duplex RF transceiver if the conflicting links are adjacent. Thus, transmissions of $e_{i}$ and $e_{j}$ should be allocated in different timeslots to avoid conflicts as shown in Figure 4(c).

Figure 4.

Conflict-free transmissions: (a) transmission in single channel operation, (b) transmissions of non-adjacent links in multi-channel operation, and (c) transmissions of adjacent links in multi-channel operation.

From the example, we realize that the conflict-free transmission depends on whether the two links are adjacent to each other. Considering it, we derive the conditions of conflict-free transmissions. First, the condition for conflict-free transmissions of arbitrary two adjacent links over the frame structure with $N$ timeslots is represented as follows

$Δ_{i} \leq π_{j} - π_{i} + o_{ij} N \leq N - Δ_{j}$ (1)

$o_{ij} = {\begin{matrix} 1, & π_{j} < π_{i} \\ 0, & π_{j} > π_{i} \end{matrix}$ (2)

$π_{j} \in A_{i}$ (3)

where $A_{i}$ is the set of adjacent links to $e_{i}$ . Second, the condition for conflict-free transmissions of arbitrary two non-adjacent links is represented as follows

$f_{i} \neq f_{j}, π_{j} \in T_{i}$ (4)

where $T_{i}$ is the set of links located in two-hop distance from $e_{i}$ . The schedule model provides conflict-free transmissions to enable multiple access in multi-channel environments such as orthogonal frequency division multiple access (OFDMA).

In multi-hop environments, the amount of delay introduced in relaying the data packet from the source device to the destination device is an important measure used to determine whether the transmission schedule meets the end-to-end delay bound. We define the end-to-end scheduling delay of the kth path as follows

$d_{k} = \sum_{h_{j} = h_{i} + 1} π_{j} - π_{i} + o_{ij} N, e_{i}, e_{j} \in I_{k}$ (5)

where $I_{k}$ is the set of all links in the kth path and $h_{i}$ is the number of links from the source device to $e_{i}$ in the path.

Transmission scheduling algorithm for link recovery

In this section, we propose a scheduling algorithm for establishing a new communication when the link failure occurs. The substitute path is established by allocating empty timeslots and available frequency channels to the links on the path to satisfy the end-to-end delay bound. These timeslots are called dedicated timeslots. It should be noted that not all empty timeslots are the dedicated timeslots, since some of the empty timeslots may result in a large delay. Allocating timeslots affects the transmission scheduling in the next link recovery procedure, since the number of dedicated timeslots is changed by timeslot allocation in the previous link recovery procedure. Therefore, securing the maximum number of dedicated timeslots in the current scheduling process provides an opportunity to successfully generate a transmission schedule that meets the delay condition during the link failure recovery procedure that may occur later.

The main concern of the proposed algorithm is to schedule transmissions to maximize the number of dedicated timeslots in the next link recovery procedure. To this end, the algorithm allocates timeslots such that the transmission links on the communication path are located as far as possible while satisfying the end-to-end delay bound condition and conflict-free condition. This scheduling policy eventually maximizes the number of dedicated timeslots. Figure 5 is a flow chart of the proposed scheduling algorithm. Upon the receipt of link failure recovery request, the network coordinator generates a transmission schedule $T'$ of the links to establish the substitute path. If the transmission schedule violates the end-to-end delay bound condition or conflict-free transmission condition, the network coordinator discards it and regenerates a new transmission schedule until both conditions are satisfied. The network coordinator searches for the minimum transmission delay $δ'$ between adjacent links from the transmission schedule. If the minimum transmission delay $δ'$ obtained at the current stage is larger than the minimum transmission delay $δ$ obtained at the previous stage, then $δ$ and $T$ are updated to $δ'$ and $T'$ , respectively. Otherwise, they remain the same. The network coordinator repeats this procedure for all combinations of transmission schedules. Finally, the network coordinator sends the final transmission schedule $T$ to the device that requested the link failure recovery.

Figure 5.

Flow chart of the proposed algorithm.

We employ max–min optimization in the proposed algorithm to maximize the minimum transmission delay $δ$ between the adjacent links as follows

$max_{Π} δ$ (6)

subject to

$π_{j} - π_{i} + o_{ij} N \geq δ, h_{j} = h_{i} + 1, e_{i}, e_{j} \in I_{k}$ (7)

$d_{k} \leq D_{k}, \forall k$ (8)

$Π \in ⋃_{e_{i} \in β} Ω_{i}, Ω_{i} \in {1, \dots, N}, \forall i$ (9)

$I_{k} \in L, δ > 0$ (10)

where $Π$ is the set of timeslots assigned to new links on the substitute path, $β$ is the set of new links, $Ω_{i}$ is the set of dedicated timeslots that can be assigned to $e_{i}$ , $D_{k}$ is the end-to-end delay bound for the kth path, and $L$ is the set of all links in the network. The first constraint equation (7) indicates that all transmission delays between adjacent links on the path are larger than or equal to $δ$ . In equation (7), $π_{i}$ and $π_{j}$ should be chosen to satisfy equations (1)–(4) to achieve conflict-free transmission. The second constraint equation (8) implies that end-to-end transmission delay for all communication paths in the network satisfies the delay bound. Finally, the proposed algorithm maximizes the number of dedicated timeslots by maximizing the minimum transmission delay value on the communication path.

Figure 6 illustrates a comparison of the transmission schedules between the proposed algorithm and other scheduling algorithm that maximizes link efficiency. The network consists of 3 source devices, 12 relay devices, and a network coordinator as shown in Figure 6(a). We consider the uplink traffic from the source device to the network coordinator; thus, there are three communication paths in the network (shown as solid arrow in the figure). The end-to-end delay bound for each path is assumed to be nine timeslots long. Figure 6(b) shows the transmission schedule for the three end-to-end paths obtained using the proposed algorithm before the link failure occurs. As shown in the transmission schedule, adjacent links of a communication path are assigned to timeslots as far as possible. The timeslot assignment maximizes the number of timeslots available for future link failure recovery while ensuring that the end-to-end transmission delay value of the communication path does not exceed the target delay value. Meanwhile, the transmission schedule generated by the algorithm maximizing link efficiency shows that communication links are allocated to a small number of timeslots to maximize link efficiency as shown in Figure 6(c).

Figure 6.

An example of transmission schedule for link failure recovery: (a) network topology, (b) transmission schedule generated by the proposed algorithm, (c) transmission schedule generated by the scheduling algorithm maximizing link efficiency, (d) network topology including new communication path, (e) new transmission schedule generated by the proposed algorithm, and (f) new transmission schedule generated by the scheduling algorithm maximizing link efficiency.

Let us consider the circumstance where a link failure occurs. Device $v_{3}$ does not receive ACK frame from Device $v_{4}$ due to changes in the wireless environment. To recover from the link failure, Device $v_{3}$ selects Device $v_{9}$ as the new parent device and sends the request message via the substitute communication path including the new links (i.e. $e_{16}$ , $e_{17}$ , $e_{18}$ , and $e_{19}$ ) as shown in Figure 6(d). The proposed algorithm arbitrarily selects timeslots among the empty timeslots to generate the transmission schedule of the new links and checks whether the conflict-free condition and the end-to-end delay condition are satisfied. In the next step, the algorithm checks whether the minimum transmission delay value can be increased. If there is no transmission schedule with a larger minimum transmission delay value, the algorithm terminates. The new transmission schedule for link failure recovery using the proposed algorithm is illustrated in Figure 6(e). The transmission schedule generated by the proposed algorithm shows that the scheduling delay for three communication paths is lesser than or equal to the end-to-end delay bound as shown in Figure 6(e). However, the end-to-end scheduling delay for the newly established substitute path generated by the algorithm maximizing link efficiency is 10 timeslots, which results in the violation of the end-to-end delay bound condition as shown in Figure 6(f). This is because that the number of empty timeslots satisfying the end-to-end delay bound is not enough to allocate for new communication links on the substitute path. From the transmission schedules in the example, maximizing the number of timeslots available for future link failure recovery improves the robustness of wireless network prone to link failure rather than the timeslot assignment that maximizes link efficiency.

Performance evaluation

In this section, we evaluate the performance of the proposed algorithm in multi-hop environments prone to link failure using QualNet network simulator. We implement the DSME MAC specification defined in IEEE 802.15.4e standard and control layer protocol on top of the MAC layer in the simulator. We consider an uplink network configuration with 100 devices randomly deployed in 700[m] by 700[m] geographical area and consider that some randomly selected source devices on the network request transmission schedules. We employ shortest routing path from the source device to the network coordinator to establish an end-to-end communication path. Each device creates a list of neighbor devices transmitting beacons and selects the parent device in the list closest from the network coordinator to establish the shortest path. If a communication link fails, the transmitting device of the failed link selects another device closest to the network coordinator as the new parent except for the previous parent device and requests the destination device for the transmission schedule of the new communication link. We assume that randomly selected communication links fail at different times after all communication links are scheduled successfully. Table 1 lists the simulation parameters.

Table 1.

Simulation parameters.

Parameters	Values
Number of devices	100
Terrain dimensions	700[m] × 700[m]
Device placement	Random
MAC model	IEEE 802.15.4e DSME
Channel diversity	Channel adaptation
Beacon order	8
Multi-superframe order	8
Superframe order	4
PHY model	IEEE 802.15.4
Frequency channel	CH1: 2.405 GHz
	CH2: 2.410 GHz
	CH3: 2.415 GHz
Tx power	3.0 dBm
Pathloss model	Two-ray
Modulation	O-QPSK
Symbol rate	62.5 ksymbol/s

We employ the path survival ratio as a performance metric to evaluate how the robust the proposed algorithm is for the link failure. The path survival ratio represents the ratio of the number of survived communication paths to the total number of communication paths in the network when link failures occur. We assume that a communication path is survived if all communication links on the path are scheduled successfully, while the path is not survived if one or more communication links on the path are not scheduled due to lack of dedicated timeslots. Therefore, the path survival ratio shows how many paths support the end-to-end transmission satisfying the delay bound when link failures occur in multi-hop environments. In addition, we investigate how many control messages are exchanged to recover link failures to measure the amount of overhead to establish substitute paths. We adopt the centralized algorithm¹¹ that employs max–min optimization to minimize end-to-end scheduling delay as a comparison algorithm for the performance evaluation of our proposed algorithm. The comparison algorithm minimizes end-to-end scheduling delay by allocating timeslots for transmission links on the communication path as close as possible. If the communication link fails, the comparison algorithm generates transmission schedules for new communication links so as to minimize transmission delay on the substitute path. Since the comparison algorithm considers single channel operation, we extend the algorithm to use multiple frequency channels in the multi-channel environment to evaluate the performance of both algorithms. In our analysis, we apply global recovery and local recovery schemes to both algorithms to observe performance depending on which links need to be rescheduled. When the global recovery scheme is applied, all communication links on the network are rescheduled when the link failure occurs, regardless of the number of failed links. The global recovery scheme generates a relatively large number of control messages, but it provides more survival paths since it optimizes the transmission schedule for all links in the network. On the other hand, when the local recovery scheme is applied, a transmission schedule is generated for a new substituting path including the failed links. The local recovery scheme generates a small amount of control messages, but the number of paths that can be recovered is generally less than the global recovery scheme, since the timeslots and frequency channels available for the new transmission schedule are limited in the local recovery scheme. It should be noted that the amount of control messages is an important metric for evaluating the performance of algorithms in wireless networks where energy consumption is an important concern, such as WSNs.

Figure 7 shows the path survival ratio of both algorithms as the number of failed links increases. We define the link failure ratio as the ratio of the number of link failures to the total number of communications to describe how many link failures occur in the network. We also evaluate the performance against different end-to-end delay bound (D) values of D = 500 ms, D = 1 s, and D = 5 s. In the simulation, 20 source devices among 100 devices deployed in the network are randomly selected, and two non-overlapping frequency channels are considered. It is observed that the path survival ratio of both algorithms decreases as the number of link failures increases. In the global recovery scheme, the performance of both algorithms shows that approximately 70% communication paths of the network survive when 90% communication links fail. However, the performance degradation due to increase in link failure ratio is not noticeable, since both algorithms recreate transmission schedule for all communication links regardless of how many link failure occurs. On the other hand, the performance difference between two algorithms is noticeable when local recovery scheme is applied. Especially, Figure 7(a) shows that the proposed algorithm establishes two times more substitute paths compared to the comparison algorithm, when 90% communication links fail. The large number of link failures increases the number of substitute paths to be established, which requires more dedicated timeslots to schedule substitute paths. However, the comparison algorithm makes difficult to assign timeslots satisfying end-to-end delay bound when the link failure occurs, since transmission links on the communication path are assigned as close as possible to minimize the end-to-end transmission delay. Meanwhile, the performance of the proposed algorithm employing the local recovery scheme is similar to that of the global recovery scheme. This implies that the proposed algorithm consumes less energy to meet the target path survival ratio than the comparison algorithm, since it exchanges a small number of control messages. Simulation results show that the performance difference between the global recovery scheme and the local recovery scheme is reduced as the target end-to-end delay bound D increases. Especially, the performance of both recovery schemes is similar when the end-to-end delay bound is 5 s, as shown in Figure 7(c). This is because that the number of dedicated timeslots satisfying the end-to-end delay bound is sufficient to recover from link failures, even though the local recovery scheme is applied to both algorithms.

Figure 7.

Path survival ratio ( $ρ$ ) versus link failure ratio ( $σ$ ) for end-to-end delay bounds (D): (a) path survival ratio when D is 500 ms, (b) path survival ratio when D is 1 s, and (c) path survival ratio when D is 5 s.

Figure 8 shows the path survival ratio of both algorithms for different available frequency channel conditions. Figure 8(a) shows the performance of the algorithms in a single channel network, while Figure 8(b) shows the performance in the multi-channel network with three non-overlapping frequency channels. We limit the end-to-end delay bound D to 1 s for all communication paths and randomly select 20 source devices from all devices in the network. In the single channel network, the proposed algorithm improves the path survival ratio compared with the comparison algorithm. As shown in Figure 8(a), the performance of the proposed algorithm shows that approximately 40% more communication paths survive than the number of surviving communication paths provided by the comparison algorithm, when half of all communication links fail. Meanwhile, the performance of both algorithms in the multi-channel network is improved over the single channel network. When the local recovery scheme is employed in the multi-channel network, Figure 8(b) shows that 67% of communication paths survive in all paths by applying the proposed algorithm and 60% of the communication paths survive by applying the comparison algorithm. As shown in the simulation results, the performance of both algorithms is improved in the multi-channel network as compared to the single channel network, since there is a possibility of generating more dedicated timeslots due to a large number of available frequency channel resources.

Figure 8.

Path survival ratio ( $ρ$ ) versus link failure ratio ( $σ$ ) for the number of available frequency channels: (a) path survival ratio in single channel network and (b) path survival ratio in multi-channel network.

Figure 9 shows the path survival ratio of both algorithms by varying the number of source devices in the network. Figure 9(a) shows the performance of the algorithms when 12 source devices are randomly selected among all devices in the network, while Figure 9(b) shows the performance when 18 source devices are selected. We consider two non-overlapping frequency channels and limit the end-to-end delay bound D to 1 s for all communication paths. If 12 source devices are deployed in the network, the performance behavior of both algorithms is similar when a small number of communication links fail, and the performance difference gradually increases as the link failure ratio increases, as shown in Figure 9(a). Meanwhile, Figure 9(b) shows the performance when the number of source devices is increased to 18. The performance of the comparison algorithm employing local recovery scheme rapidly degrades as the number of failed links increases; approximately 15% performance degradation is observed when 90% of all communication links fail compared to Figure 9(a). This is because that it is difficult for the comparison algorithm using local recovery scheme to obtain a sufficient number of dedicated timeslots to establish new communication paths due to the increased number of source devices compared to Figure 9(a).

Figure 9.

Path survival ratio ( $ρ$ ) versus link failure ratio ( $σ$ ) for the number of source devices: (a) path survival ratio when 12 source devices are deployed and (b) path survival ratio when 18 source devices are deployed.

Figure 10 shows the number of control messages exchanged to recover the link failure in both algorithms. In order to observe the number of control messages for the different the number of source devices, 12 and 20 source devices were selected respectively in Figure 10(a) and (b). The end-to-end delay bound D is set to 1 s for all communication paths, and two non-overlapping frequency channels are employed in the network. The simulation results show that the global recovery scheme requires more control messages than the local recovery scheme to recover from the link failure. As shown in Figure 10(b), approximately two times less control messages are exchanged in the local recovery scheme when 30% communication links fail, while the proposed algorithm employing local recovery scheme achieves 85% communication paths survive as shown in Figure 7(b). In the meantime, the performance of comparison algorithm employing the global recovery scheme shows a similar path survival ratio as the proposed algorithm. This implies that the proposed algorithm consumes only half the energy consumed by the comparison algorithm to achieve 85% path survival ratio. The energy efficiency of the local recovery scheme is maximized as the number of failed communication links decreases. When 10% communication links fail in the network, approximately six times less control messages are exchanged to recover the link failure compared to the global recovery scheme, whereas more than 90% communication paths survive. In the global recovery scheme, all communication links are rescheduled even if a single link fails. This implies that the network coordinator sends control messages including new transmission schedules to all devices in the network, regardless of the number of link failures. On the other hand, the network coordinator sends the transmission schedules to the devices of failed links in the network with local recovery scheme. Therefore, the amount of overhead can be reduced by employing the local recovery scheme. Simulation results show that the number of control messages increases as the number of source devices in the network increases. Comparing the simulation results when half of all communication links fail, Figure 10(b) shows that approximately 50% more control messages are exchanged than in Figure 10(a) where 12 source devices are selected.

Figure 10.

Number of control messages versus link failure ratio ( $σ$ ) for the number of source devices: (a) number of control messages when 12 source devices are deployed and (b) number of control messages when 20 source devices are deployed.

Conclusion

In this article, we propose a TDMA scheduling algorithm with link recovery in multi-hop environments. The proposed algorithm schedules the transmission to maximize the number of dedicated timeslots when the next link recovery occurs, while providing the end-to-end transmission within delay bound. We evaluate the performance of the proposed algorithm and compare it with the work where max–min optimization is employed to minimize end-to-end scheduling delay. The main difference between the two algorithms is that our proposed algorithm schedules to meet the end-to-end delay bounds to generate more substitute paths in the event of link failure, while the other algorithm minimizes end-to-end delay in substitute paths. The performance is evaluated by varying the end-to-end delay bound, channel bandwidth, and the number of source devices in the network. Simulation results show that the proposed algorithm achieves higher path survival ratio while satisfying end-to-end delay bound than the comparison algorithm. Especially, the difference in the performance between the two algorithms is noticeable when a large number of link failures occur: the performance of the proposed algorithm is approximately twice as high as that of the comparison algorithm.

In addition, we apply global recovery and local recovery schemes to observe performance depending on which communication links need to be rescheduled. The control message generated by each scheme represents the amount of energy consumed in the network for link recovery. The global recovery scheme that reschedules links across the network requires a lot of control messages to be exchanged, but provides lower end-to-end latency on the new communication path than the local recovery scheme. On the other hand, the local recovery scheme reduces energy consumed in the network by generating a small amount of control messages to recover the link failure. Simulation results show that the local recovery scheme requires six times less control messages to establish the substitute path when a small number of link failures occur, while more than 90% communication paths survive.

Footnotes

Academic Editor: Myungsik Yoo

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: This work was supported by the IT R&D program of MSIP/IITP [2015-0-00517,Development of remote ship identification technology and radar associated maritime monitoring system].

References

Guner

Hancke

. Industrial wireless sensor networks: challenges, design principles, and technical approaches. IEEE T Ind Electron 2009; 56(10): 4258–4265.

Aref

. Internet of things standards: who stands out from the crowd?IEEE Commun Mag 2016; 54: 40–47.

IEEE 802.15.4:2006. Part 15.4: wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs).

IETF RFC 4922:2007. Transmission of IPv6 packets over IEEE 802.15.4 networks.

HART Communication Foundation. HART field communication protocol specification, 2013, https://fieldcommgroup.org/sites/default/files/technologies/hart/toc_spec013.pdf

ISA-100.11a:2009. Wireless systems for industrial automation: process control and related applications.

ZigBee Alliance. ZigBee specification, 2007, https://people.ece.cornell.edu/land/courses/ece4760/FinalProjects/s2011/kjb79_ajm232/pmeter/ZigBee%20Specification.pdf

IEEE 802.15.4e:2012. Part 15.4: low-rate wireless personal area networks (LR-WPANs) amendment 1: MAC sublayer.

Wang

Vilajosana

. 6top protocol: draft-ietf-6tish-protocol-03, 2016, https://tools.ietf.org/html/draft-ietf-6tisch-6top-protocol-03

10.

Rhee

Warrier

Min

et al . DRAND: distributed randomized TDMA scheduling for wireless ad hoc networks. IEEE T Mobile Comput 2009; 8(10): 1384–1396.

11.

Djukic

Valaee

. Delay aware link scheduling for multi-hop TDMA wireless networks. IEEE ACM T Network 2009; 17(3): 870–883.

12.

Lee

Jeong

. Multi-channel TDMA link scheduling for wireless multi-hop sensor networks. In: Proceedings of the IEEE international conference on information and communication technology convergence (ICTC), Jeju, South Korea, 28–30 October 2015, pp.630–635. New York: IEEE.

13.

Gore

Karandikar

. Link scheduling algorithms for wireless mesh networks. IEEE Commun Surv Tut 2011; 13(2): 258–273.

14.

Kim

Lee

. Scheduling multi-channel and multi-timeslot in time constrained wireless sensor networks via simulated annealing and particle swarm optimization. IEEE Commun Mag 2014; 52(1): 122–129.

15.

Lee

Jeong

. Performance analysis of IEEE 802.15.4e DSME MAC protocol under WLAN interference. In: Proceedings of the IEEE international conference on information and communication technology convergence (ICTC), Jeju, South Korea, 15–17 October 2012, pp.741–746. New York: IEEE.

16.

Shin

Park

Choi

et al . Packet error rate analysis of ZigBee under WLAN and Bluetooth interferences. IEEE T Wirel Commun 2007; 6(8): 2825–2830.

17.

Angrisani

Bertocco

Fortin

et al . Experimental study of coexistence issues between IEEE 802.11b and IEEE 802.15.4 wireless networks. IEEE T Instrum Meas 2008; 57(8): 1514–1523.

18.

Xue

Ganz

. Ad hoc QoS on-demand routing (AQOR) in mobile ad hoc networks. J Parallel Distr Com 2003; 63(2): 154–165.

19.

Goff

Abu-Ghazaleh

Phatak

et al . Preemptive routing in ad hoc networks. J Parallel Distr Com 2003; 63(2): 123–140.

20.

Lai

Hsiao

Lin

. Adaptive backup routing for ad-hoc networks. Comput Commun 2007; 30(2): 453–464.

21.

Cheng

. A low overhead dynamic route repairing mechanism for mobile ad hoc networks. Comput Commun 2007; 30(5): 1152–1163.

22.

IETF RFC6550:2012. RPL: IPv6 routing protocol for low-power and lossy networks.

23.

Lee

. Robust QoS scheduling using alternate path for recovery from link failures in IEEE 802.15.4e. In: Proceedings of the IEEE international conference on mobile computing and ubiquitous networking (ICMU), Singapore, 6–8 January 2014, pp.630–635. New York: IEEE.

Multi-channel time division multiple access timeslot scheduling with link recovery for multi-hop wireless sensor networks