An improved asynchronous energy-saving mechanism for IEEE 802.15.5-based networks

Abstract

IEEE 802.15.5 standard introduces the mesh routing which improves reliability and robustness of routing in wireless sensor network since there are multiple routes from source node to destination node. To achieve energy efficiency for a long network lifetime, the asynchronous energy saving is proposed in IEEE 802.15.5, which includes the receiver-initiated unicast mechanism and the sender-initiated broadcast mechanism. In this article, an improved asynchronous energy saving named semi-synchronous energy saving is proposed to deal with the energy inefficiency from idle listening existing in asynchronous energy saving. In semi-synchronous energy saving, every node maintains the wake/sleep schedule information of nodes in its two-hop neighborhood and uses this information to calculate the wake-up time of an interested neighbor that the data will be sent to, which reduces idle listening time in both unicast and broadcast mechanisms. A low delay routing mechanism is also proposed based on the wake/sleep schedule information of neighbors. Furthermore, the optimal guard time to guarantee receiving the wake-up notification from neighbor in the presence of clock drift is investigated for saving energy. The performance analysis and simulation evaluation show that semi-synchronous energy saving saves more than 80% of energy with less than 30% memory cost compared to asynchronous energy saving, and it also improves the time of completing broadcast and the end-to-end delay.

Keywords

Wireless sensor network mesh routing idle listening energy saving low delay

Introduction

Wireless sensor network (WSN), which consists of nodes with low power, short radio range, weak process capacity, and limited memory size, has been widely used in military, industrial, habitat monitoring, environmental protection, and other areas.¹ Contemporary WSNs adopt IEEE 802.15.4 standard,² which targets low-rate wireless personal area network (WPAN), in their medium access control (MAC) layer and physical (PHY) layer. Usually, tree-based routing protocols, for example, Collection Tree Protocol (CTP), are applied in gathering the data sensed by sensor nodes to the sink. There exists a shortcoming in tree-based routing that failure in a branch node prevents its descendant nodes from delivering their data to the sink. This problem is resolved by mesh-based routing that improves routing reliability.³ IEEE 802.15.5 standard⁴ defines the architectural framework that enables WPAN nodes to promote interoperable, stable, and scalable wireless mesh topologies; the framework constitutes two parts: low-rate mesh and high-rate mesh networks. Considering the former is based on IEEE 802.15.4 standard which is widely adopted in WSNs, we focus on the low-rate mesh network in this article.

An IEEE 802.15.5 low-rate mesh network starts by the sink turning on its power to allow other nodes to join the network. Then, a tree rooted at the sink is gradually formed when the nodes join one after another. After all nodes have joined the tree, they report the number of their descendants to their parent in a bottom-up manner. The top-down address allocation starts after the sink has received the number of descendants from all of its children, in which the sink allocates consecutive 16-bit logical address (i.e. an address block) to each of its children according to the number of their descendants. When a branch node obtains an address block, it assigns each of its children an address block. This process repeats till a leaf node is encountered. Figure 1 depicts a possible tree generated in address assignment,³ where node A is the sink and the number in a square bracket besides a node indicates the number of children contained in a branch of the node. For example, node C in Figure 1 has three branches that contain 1, 2, and 1 node(s), respectively.

Figure 1.

A tree generated by address assignment in IEEE 802.15.5.³

When a node receives an address block from its parent, it broadcasts Hello message to its meshTTLOfHello-hop neighbors to exchange the link state information.³ Here, meshTTLOfHello is a MeshIB attribute defined in IEEE 802.15.5. The Hello message contains the information of the sender and its one-hop neighbors. Every node uses neighbor list and connectivity matrix to store the information of (meshTTLOfHello + 1)-hop neighbors. Thus, after several rounds of exchanges of Hello messages, the mesh is formed.

In many applications of wireless sensor mesh network (WSMN), the nodes operate on battery and transmit with low data rates. Saving energy is a critical issue for WSMNs in order to prolong network lifetime. The mesh sublayer of IEEE 802.15.5 is designed with non-beacon mode for flexible mesh communication, which prevents the synchronized superframe structure of IEEE 802.15.4 from being used. To bypass the superframe structure, the asynchronous energy saving (ASES) and the synchronous energy saving (SES) are proposed in IEEE 802.15.5 to achieve energy efficiency. Both approaches operate under the non-beacon mode of IEEE 802.15.4. Since the SES requires the network-wide synchronization that is a big challenge in wide-scale WSMNs,⁴ it is unsuitable for large-scale networks. Thus, we investigate the ASES in this article.

The ASES improves energy efficiency by applying duty cycle, which significantly reduces nodes’ idle listening time.⁵ However, it exhibits several drawbacks. First, in the receiver-initiated unicast mechanism, when a node has data to send, it turns on radio immediately and listens silently to a wake-up notification (WN) message from the intended receiver. The period of the idle listening from the instant it wakes up to the instant it receives the WN message leads to energy wastage. Second, in the sender-initiated broadcast mechanism, when a node has data to broadcast, it enters the active state at once and transmits extension request (EREQ) frames for longer than one duty cycle to call all neighbors awake, which makes the receivers keeping idle listening for long time and leads to considerable energy wastage. The above shortcomings result in considerable energy waste. Regrettably, there is no literature to address these shortcomings existing in ASES so far. To reduce the idle listening for energy saving in duty-cycled WSNs, a lot of MAC protocols have been proposed. However, unlike IEEE 802.15.5, which works on top of MAC layer, they work at the MAC layer and are not compatible with IEEE 802.15.5. To remedy these drawbacks, we propose an improved ASES mechanism, named Semi-SES, which achieves large performance gains with a small extension to the standard. The main contributions of this article are as follows:

An improved local link exchange mechanism is proposed, through which each node can obtain and maintain the wake/sleep schedules of two-hop neighbors, enabling the nodes to calculate the wake-up time of neighbors.

We improve the unicast and broadcast mechanisms of the ASES, which reduce the participating nodes’ idle listening by exploiting the neighbors’ wake/sleep schedule information.

We investigate the optimal guard time for energy saving. The guard time is the time period that the sender should wake up earlier than the calculated wake-up time of a receiver to guarantee receiving the WN from the receiver in the presence of clock drift.

We propose a low delay mesh routing based on the neighbors’ wake/sleep schedule information.

The remainder of this article is organized as follows. In section “Related works,” we survey the related works. The details of Semi-SES are described in section “Semi-SES.” Section “Performance analysis and simulation evaluation” presents the performance analysis and simulation evaluation. The article is concluded in section “Conclusion.”

Related works

The ASES introduced in IEEE 802.15.5 LR-WPAN mesh standard is built on top of duty cycling. That is, a node stays in OFF state most of the time, in which the node turns off its transceiver to run with low power consumption, and the node periodically switches to ON state, in which the node is fully active, to transmit/receive data. This ON/OFF schedule, that is, duty cycle, reduces the energy waste from idle listening (EWIL), thus extending the network lifetime.

In ASES, a time structure called cycle period, similar to the superframe structure in IEEE 802.15.4, is defined, which comprises an active duration (AD) and an inactive duration (ID).⁴ The length of cycle period is called wake-up interval (WI). A WN, a command frame, is transmitted at the beginning of the AD in each cycle period, as depicted in Figure 2. WI and AD are calculated by

\begin{matrix} W I = m e s h c B a s e A c t i v e D u r a t i o n \times 2^{W O} \\ A D = m e s h c B a s e A c t i v e D u r a t i o n \times 2^{A O} \end{matrix}

(1)

where meshcBaseActiveDuration is a constant defined in IEEE 802.15.5, which equals to 5 ms, and WO and AO mean the wake-up order and the active order, respectively, which satisfy $0 \leq AO \leq WO \leq 14$ . In particular, the IEEE 802.15.5 recommends that all nodes should be configured with the same WO value, though their AO values may differ.

Figure 2.

Structure of WI.⁴

To cope with the asynchronization in the ADs of nodes, the ASES uses two different approaches to transmit data.⁴ For unicast, a receiver-initiated mechanism is used, which is illustrated in Figure 3, where the sender is node v and node u is the receiver. When node v has data to transmit, it waits for the AD of node u that is announced by a WN frame, and it transmits the data within the AD of node u. For broadcast, a sender-initiated mechanism is used. As depicted in Figure 4, node u and v are neighbors of node w, and node w has data to broadcast. Node w first wakes up all neighbors by continuously transmitting EREQ frames for longer than one WI, and then it broadcasts the data frame.

Figure 3.

Receiver-oriented unicast mechanism.⁴

Figure 4.

Sender-initiated broadcast mechanism.⁴

Benefiting from duty cycle, the ASES significantly reduces nodes’ idle listening time, thus improving energy efficiency.⁴ However, energy inefficiency resulting from idle listening still exists in ASES. First, in the receiver-initiated unicast mechanism, when a node has data to transmit, it turns on its radio immediately and listens silently to a WN message from the intended receiver. The idle listening from the instant it wakes up to the instant it receives the WN message wastes energy. Second, in the sender-initiated broadcast mechanism, the node with data ready to broadcast turns on its radio at once and transmits EREQs for longer than one WI to wake up all neighbors. When the receivers are waken up, they keep in idle listening before the broadcast time, which results in substantial energy wastage. In a word, there exists the EWIL in ASES. Unfortunately, to the best of our knowledge, the EWIL in ASES has not been remedied.

Since idle listening constitutes the most prevalent source of energy consumption of MAC schemes, a lot of MAC protocols have been proposed for duty-cycled WSNs, which can be divided into synchronous protocols and asynchronous protocols. In synchronous protocols, such as S-MAC,⁶ U-MAC,⁷ and TARS,⁸ wake/sleep scheduling and clock of nodes need to be synchronized. Because of high overhead introduced by synchronization, asynchronous protocols where sensor nodes sleep and wake up asynchronously are widely used. Asynchronous protocols can be further divided into sender-initiated protocols and receiver-initiated protocols.

Typical sender-initiated protocols include B-MAC⁹ and X-MAC.¹⁰ B-MAC employs an adaptive preamble sampling scheme to reduce duty cycle and minimize idle listening. X-MAC uses multiple copies of short preamble packet, which significantly reduces energy usage at both the transmitter and the receiver. Literature¹¹ proposes a low-cost local synchronization scheme and develops a window-based transmission to cope with synchronization variance and link burstiness. Recently, there have been sender-initiated MAC protocols based on wake-up radio technology to diminish overhearing and idle listening,¹² where nodes are equipped with a low-power radio for wake-up. Different from the above protocols, the unicast protocol adopted by IEEE 802.15.5 belongs to receiver-initiated protocols.

Lin et al.¹³ first propose a receiver-initiated paradigm named Receiver-Initiated CyclEd Receiver (RICER), and further put forward semi-synchronous RICER to reduce idle listening by exploiting received beacons to predict the wake-up periods of neighbors. RI-MAC is proposed in Sun et al.¹⁴ which attempts to minimize the time a sender and its intended receiver occupy the wireless medium to find a rendezvous time, while still decoupling the sender’s and receiver’s duty cycle schedules. D Yang et al.¹⁵ propose RW-MAC, which utilizes the remaining sleep time interval of a receiver, which is piggybacked on the beacon, to estimate its wake-up time, therefore reducing energy wastage. RP-MAC¹⁶ extends RW-MAC with a feature called frame reordering which reduces the delivery latency using the next wake-up information of several receivers to reorder the transmission buffer of the sender. A receiver-initiated X-MAC with tree topology is proposed in Park et al.¹⁷ S Basagni et al.¹⁸ redefine the CTP for duty-cycled WSNs, which uses the auxiliary radio of node called wake-up radio to eliminate idle listening and decrease the delivery delay. Wang et al.¹⁹ analyze the energy consumption for duty-cycled sensor networks with different data rates, and design a light-weight adaptive duty-cycling protocol, which reduces the energy consumption under different data rates and protocol dynamics. An improvement of RI-MAC titled as DURI-MAC is proposed in Khalil et al.,²⁰ which uses dual channel in order to minimize the number of hidden and exposed terminals. Since aforementioned schemes are designed for WSNs and are not compatible with IEEE 802.15.5, they cannot be directly applied to IEEE 802.15.5-based WSMNs. To remedy the aforementioned EWIL problems in ASES, we put forward Semi-SES.

Semi-SES

The Semi-SES improves the ASES. In Semi-SES, every node maintains the wake/sleep schedules of its two-hop neighbors, which enables the nodes to calculate the upcoming wake-up time of an interested node. Knowing the upcoming wake-up time of the receiver, the sender only turns on the radio at the time a little earlier than the receiver’s wake-up time, which significantly reduces the EWIL.

Initialization of the Semi-SES

As described in IEEE 802.15.5, the initialization and frame transmission of ASES are controlled by a mesh sublayer parameters meshASESOn, which decides whether a node is under the ASES or not. In the initial stage, each node sets meshASESOn to false, which means nodes join the network without considering the ASES mode. In other words, the association request, the association response, the address requirement report, and the address allocation frame are transmitted in normal manner. After receiving a mesh sublayer address, a node selects a wake-up time randomly and sends several eHello messages to inform its neighbors of its wake/sleep schedule in addition to other necessary information. The eHello message extends the Hello message defined in IEEE 802.15.5, which has the format illustrated in Figure 5.

Figure 5.

Format of the eHello frame.

The main difference between the eHello frame and the Hello frame is that the eHello frame includes the wake/sleep schedules of the sending node and its one-hop neighbors, which are emphasized with gray in Figure 5. In each neighbor of the node, its wake/sleep schedule comprises its AO and a WN offset of the neighbor relative to the current node. The WN offset denotes the difference between the waking times of the two nodes. In addition, the WN offset is measured by meshcTimeUnit (mTU), which is a constant defined in IEEE 802.15.5 low-rate mesh standard as the basic time unit of mesh layer and equals 1 ms. Due to the maximum of WI being 5×2¹⁴ mTUs, more than 16 bits are needed to hold the WN offset. In our scheme, 3 bytes are used to accommodate a node’s wake/sleep schedule. As shown in the bottom of Figure 5, the first 4 bits are for the AO and the remaining bits are for the corresponding WN offset.

In the sequel, we regard mTU as a time slot. A WI can be divided into L time slots, where $L = 5 \times 2^{WO}$ . Supposing there are two neighbors u and v, and node v can calculate the WN offset of node u relative to itself using

O_{v u} = (i - O_{u} ​ L) \mod L

(2)

where i represents the number of the slot in which node v received the eHello message sent by node u. O_u indicates the number of the slot in which node u sent the eHello message, which is encapsulated in the received eHello message. Figure 6 depicts the calculation of WN offset between neighbors.

Figure 6.

Calculation of WN offset between neighbors.

If a node finds that its WN slot is same with those of its neighbors, the node selects a new WN slot as far as possible from those of its neighbors. After exchanging eHello messages with neighbors, every node obtains the information of its two-hop neighborhood, and it enters ASES mode by setting meshASESOn to true, and starts operating in duty cycle.

In order to store the information of nodes in two-hop neighborhood, every node maintains a two-dimension table, called extended neighbor list (EN-List). The attributes of the EN-List include begAddr, endAddr, treeLevel, linkQuality, relation, status, numOfHops, and wake/sleep schedule. Here, begAddr and endAddr are the beginning and ending addresses of the address block assigned to the neighbor, respectively; treeLevel means the tree level of the neighbor, where the tree level of a node in routing tree is equal to the tree level of its parent plus 1, and the tree level of the sink is 0; linkQuality indicates the link quality between the neighbor and the current node; status represents the status of the neighbor, which takes one of the enumeration values of UNKNOWN, DOWN, and LEFT and is used to support the leaving and rejoining of nodes; the relation between the neighbor and the node is represented by relation field that takes one of the enumeration values of PARENT, CHILD, and COMMON NEIGHBOR; numOfHops is the number of hops between the node and the neighbor; and wake/sleep schedule indicates the AO of the neighbor and the WN offset of the neighbor relative to the current node. Each row of EN-List keeps the information of one of nodes in the current node’s two-hop neighborhood.

Moreover, a node constructs a connectivity matrix for all nodes in EN-List. An example of the connectivity matrix is shown in Table 1, in which the “1” or “0” at the cross cell of two nodes indicates whether the corresponding nodes are directly connected or not. The connectivity matrix is symmetric, which indicates that all links in the network are bidirectional and the diagonal of the table is useless. The connectivity matrix of Semi-SES is the same as ASES.

Table 1.

Example of connectivity matrix.

	me	nb₁	nb₂	nb₃	…	nb_n−2	nb_n−1	nb_n
me		1	1	0	…	0	1	0
nb₁	1		1	0	…	0	1	0
nb₂	1	1		1	…	0	0	0
nb₃	0	0	1		…	0	0	1
…	…	…	…	…	…	…	…	…
nb_n−2	0	0	0	0	…		1	0
nb_n−1	1	1	0	0	…	1		0
nb_n	0	0	0	1	…	0	0

Unicast and broadcast mechanisms in Semi-SES

Since nodes maintain the wake/sleep schedules of all neighboring nodes in EN-List, nodes are able to calculate the upcoming WN time of an interested node. When a node denoted by u has data intended to a neighbor denoted by v, it calculates the WN slot of node v by inverting the WN offset calculation $B_{v} = B_{u} + O_{uv}$ , where B_u is the WN slot of node u. If the intended receiver is active at that moment and the remaining active time is enough to transmit the packet, the node contends for sending immediately; otherwise, the node wakes up slightly earlier than the WN slot of the receiver. Once the node received a WN from the intended receiver, it starts to contend channel for sending. The procedure of the improved unicast mechanism is illustrated in Figure 7. Compared to the original unicast mechanism of the ASES, the improved unicast mechanism drastically reduces the idle listening time of the sender, which improves energy efficiency.

Figure 7.

Unicast mechanism of the Semi-SES.

The broadcast mechanism of the Semi-SES is depicted in Figure 8. Supposing node u has data intended to all of its neighbors, it first calculates the broadcast time, which is the time the last neighbor will wake up, for example, the wake-up time of node z in Figure 8. Then, node u utilizes the unicast mechanism to send eEREQ messages to inform its neighbors of the waiting time after which it will embark on broadcasting. The eEREQ extends the EREQ, and 2 bytes are added to accommodate the waiting time. When a neighbor received an eEREQ, it replies an EREP message to the sender, and it turns off its radio and keeps sleeping until the notified broadcast time. When node u received the WN message from the last neighbor, it broadcasts the data immediately. When a node has data to broadcast, it unicasts the data to neighbors one by one.

Figure 8.

Broadcast mechanism of the Semi-SES.

Compared to the original broadcast mechanism of the ASES, the improved broadcast mechanism has the following advantages: (1) the broadcasting node only keeps awake for a short period for each neighbor and only needs to perform several eEREQ/EREP message exchange with its neighbors, and in the rest time, the sender can turn off the radio to save energy, which reduces the sender’s energy consumption; (2) after finishing eEREQ/EREP message exchange, a receiver can turn off the radio and only needs to wake up slightly earlier than the notified broadcast time, which decreases the idle listening time of the receiver; and (3) the sending node does not need to wait for a period longer than one WI before broadcasting data frame, which improves the broadcast efficiency.

Guard time optimization

Since the system clock drift exists, as mentioned in subsection “Initialization of the Semi-SES” of section “Semi-SES,” the sender should wake up a short time earlier, called guard time, than the calculated WN time of the receiver to guarantee receiving the WN. To remedy the accumulated influence of the clock drift, every node needs to transmit eHello messages to update its wake/sleep schedule information in its neighbors periodically with a slightly longer interval denoted by I_update, called update interval. There is a tradeoff on how long the guard time should be. If the guard time is longer, more energy is wasted due to the longer idle listening time of the sender, but the interval of node’s updating the wake/sleep schedule information of its neighbors can be longer, which reduces the energy consumption of updating the wake/sleep schedule information, vice versa.

Since each node operates in duty cycle in operation stage in Semi-SES, node unicasts eHello messages to its neighbors one by one. In order to save energy, the sender only encapsulates the information of its one-hop neighbors subtracting the receiver’s one-hop neighbors into the Information of One-hop Neighbors field of eHello frame. For example, in the case illustrated in Figure 9, since nodes C, D, and E are also one-hop neighbors of node A, node A can obtain their information through the eHello frames from them. Therefore, node B only needs to encapsulate the information of nodes F, G, H, and I into the eHello frame intended to node A, thus reducing the overhead of exchanging eHello messages.

Figure 9.

Example of nodes encapsulated in eHello message.

The average number of neighbors of a node is denoted by N, and the number of bits of an eHello message can be expressed by

S_{eHello} = 8 \times (18 + 5 \times β N)

(3)

where β is the ratio of the average number of nodes capsulated in an eHello message to the average number of neighbors.

Since the WN time of the receiver may be at any time evenly in the specified slot. The expected idle listening time of the sender can be formulated as

t_{idle} = t_{g} + 0.5 mTU

(4)

In low-rate WSMNs, receiving almost happens in the AD of the receiver in which the radio of the receiver is always on, and the power of listening is almost equal to that of receiving in most radio transceivers compatible with IEEE802.15.4, such as CC2420, AT86RF212, and MRF24J40MA. So, we only analyze the energy consumption of the senders. The energy consumption of a node transmitting eHello messages in an update interval can be formulated as

E_{update} = N \times (t_{idle} \times p_{idle} + \frac{S_{eHello}}{e_{t}} \times p_{tx})

(5)

where p_idle and p_tx are the power of the radio in listening and transmitting modes, respectively, and e_t indicates the data transmission rate.

The system clock drift may be positive or negative. Given t_g, the maximum interval of updating wake/sleep schedule information can be calculated by

I_{update} = \frac{t_{g}}{2 \times θ}

(6)

where θ means the maximum drift rate of the system clock.

The power consumption per second for a node transmitting eHello messages can be expressed by

p_{update} = \frac{E_{update}}{I_{update}} = \frac{2 \times θ \times E_{update}}{t_{g}}

(7)

Assume that the average number of data packages a node transmits per second is r_data, then the power consumption per second from idle listening for a node waiting for the WN messages can be expressed as

p_{data} = t_{idle} \times p_{idle} \times r_{data}

(8)

The sum of p_data and p_update can be expressed as a function of t_g, which is formulated as

f (t_{g}) = p_{data} + p_{update}

(9)

To minimize f(t_g), we can derive the optimal value of t_g by solving

\frac{df}{d t_{g}} = 0

(10)

Substituting equations (3)–(9) into equation (10), we have the optimal value of t_g as

t_{g}^{*} = \sqrt{\frac{2 \times θ \times (N \times (0.5 mTU \times p_{idle} + \frac{8 \times (18 + 5 \times β N)}{e_{t}} \times p_{tx}))}{p_{idle} \times r_{data}}}

(11)

Figure 10 depicts the optimal guard time for different data rate r_data and number of neighbors.

Figure 10.

Optimal guard time for different data rate and number of neighbors.

The values of the parameters in equation (11) used in numeral calculation are listed in Table 2.

Table 2.

Values of the parameters.

Symbol	Meaning	Values²¹
$θ$	Clock drift rate	50 ppm
$p_{idle}$	Power in listening	56.4 mW
$p_{tx}$	Power in transmitting	52.2 mW
$p_{r x}$	Power in receiving	56.4 mW

The value of β under the different values of N is obtained from extensive simulations. The results shown in Table 3 are from the average of 5000 randomly generated topologies.

Table 3.

Values of the parameter β.

Number of neighbors (N)	Value of β
6	0.593
8	0.559
10	0.531
12	0.510
14	0.495
16	0.486

As demonstrated in Figure 10, the optimal guard time is positively correlated to the number of neighbors but negatively correlated to the data rate. The reasons are as follows. The more neighbors a node has, the more number of eHello messages with bigger size the sender needs to send. To reduce energy consumption in periodically broadcasting eHello messages, the interval of updating wake/sleep schedule should be longer, which results in longer guard time. However, the bigger the data rate, the more energy is consumed in idle listening for sending data. To reduce EWIL, the guard time should be shorter.

Routing mechanism in Semi-SES

In Semi-SES, when a node is about to forward a data frame, it consults with the EN-List and the connectivity matrix to determine the next hop considering end-to-end delay, as well as the number of hops. To find the optimal next hop, every node constructs a directed graph G(V, E), where V are the nodes in EN-List and E are the adjacent relations between nodes. For example, an edge denoted by e(u, v) denotes the adjacent relation from node u to node v. The weight of e(u, w), denoted by w(u, v), is expressed as

w (u, v) = L \times α + O_{uv}, 0 \leq α \leq 1

(12)

The coefficient α is a constant which is used to balance WN offset and number of time slots, and L is the number of time slots in a WI, which equals 5 × 2^WO. Since the EN-List of a node only maintains the WN offsets of neighbors relative to itself, the WN offset of a neighbor v relative to another neighbor u needs be calculated using

O_{uv} = {\begin{matrix} 0 & v = u \\ (O_{cv} - O_{cu} + L) mod L & v \neq u, c is the current node \end{matrix}

(13)

The Dijkstra algorithm is used to calculate the shortest weighted distance from the current node to every other node in G(V, E). We use distance(.) to denote the shortest weighted distance, for example, distance(u) represents the shortest weighted distance from the current node to node u.

The routing procedure in Semi-SES is as follows. When a node receives a packet, it checks whether it is the destination of the packet. If yes, it consumes the packet; otherwise, it forwards the packet according to the following three rules:

Rule 1. If the destination is one of its one-hop neighbors, the data packet will be sent directly to the destination.

Rule 2. If the destination’s address falls in the address block of one of neighbors in its EN-List, the node with the smallest address block including the destination is selected as an anchor, the algorithm findNextHop described as follows is used to find the next hop, and then the data packet will be sent to the found next hop.

Algorithm: findNextHop
Input:the address of the destination, the address of the anchor Output:next hop The algorithmic process: u* = arg _u min {distance(u)}, u∈{the one-hop neighbors of the anchor}; while (u∉* {the one-hop neighbors of the current node}){v* = one of { v \| distance(u^) −distance(v) = O _vu};u* = v} return* u*;

Rule 3. If the current node has no information about the destination, it selects one of the neighbors with the smallest “tree level + numofHops” in EN-List as an anchor, and the next hop is found by the findNextHop algorithm.

To deal with unreliable wireless links in real WSMNs, the sender uses the routing mechanism of the ASES to find a valid next hop when it detects that the next hop found by the routing mechanism of the Semi-SES is failed. If a node found some nodes in EN-List had been invalid for certain time, it updates the EN-List and the connectivity matrix, and then reconstructs the G(V, E), and re-calculates the shortest weighted distance of nodes in EN-List.

The coefficient $α$ has a significant impact on selecting next hop. When $α$ is set to 0, the power of an edge is equal to the WN offset between the two nodes associated with the edge, and a forwarding path found by the routing procedure of the Semi-SES has the smallest delay. When $α$ is set to 1, the found forwarding path has the minimal number of hops. That is because the anchor is two hops far away from the current node, and there must exist one of the anchor’s one-hop neighbors who is one hop far away from the current node, whose distance(.) is $L + WN offset$ , which is less than $L \times 2$ . Supposing there is another path from the current node to one of the anchor’s one-hop neighbors, and the length of which is not less than two hops, the weighted length of the path is more than $L \times 2$ . So, when $α$ is set to 1, the Semi-SES must be able to find a path with the minimal number of hops.

Performance analysis and simulation evaluation

Performance analysis and numerical simulation

Since the energy consumption of many sensor nodes from idle listening is almost the same as the energy consumption for receiving, the energy consumption during the active period in Semi-SES is almost the same in ASES given the same AO. Therefore, the energy consumption difference between Semi-SES and ASES is mainly due to the energy consumption caused by the idle listening during the inactive period. First, we analyze the idle listening time of the unicast mechanisms of ASES and Semi-SES. In ASES, since a sender has no information about when the receiver will wake up, the sender has to keep listening in order to receive the WN message from the receiver. Because the WN time of the receiver may be at any time in a WI, the expected idle listening time (EILT) of the sender can be represented by

EIL T_{ASES} = 0.5 \times 5 \times 2^{WO} mTU

(14)

In Semi-SES, because a sender can calculate the WN time of the receiver and the WN could appear at any time evenly in the calculated WN slot, the sender only wakes up the guard time earlier than the calculated WN slot of the receiver. The expected idle listening time of the sender can be expressed by

EIL T_{Semi - SES} = 0.5 mTU + t_{g}^{*}

(15)

The EILT saved by SEMI-SES over ASES can be expressed as

\begin{matrix} EIL T_{saved} = EIL T_{ASES} - EIL T_{Semi - SES} \\ = 2.5 \times 2^{WO} mTU - 0.5 mTU - t_{g}^{*} \end{matrix}

(16)

As shown in Figure 10, the maximum value of $t_{g}^{*}$ is less than 7 mTU, so

EIL T_{saved} \geq 2.5 \times 2^{WO} mTU - 0.5 mTU - 7 mTU

(17)

Therefore, when $WO > \log_{2}^{3}, EIL T_{saved} > 0$ .

Figure 11 shows the numerical simulation result with $t_{g}^{*} = 7 ms$ , which reflects our analytical conclusions.

Figure 11.

EILT of the sender.

In ASES, to broadcast a data frame to its neighbors, the sender needs to continuously transmit EREQ messages for longer than one WI. When a neighbor receives an EREQ message, it replays an EREP message to the sender and keeps listening until it receives the broadcast data frame. Since the WN of a node will appear at any time in a WI with the same probability, the excepted total radio on time (ETROT) of all neighbors for waiting the broadcast frame can be represented by

ETRO T_{ASES} = N \times 0.5 \times 2^{WO} mTU

(18)

As described in subsection “Unicast and broadcast mechanisms in Semi-SES” of section “Semi-SES,” when a node has data to broadcast, it first determines the broadcast time which is the time the last neighbor will wake up. Then, the sender uses unicast mechanism to inform its neighbors of the determined broadcast time one by one. Every neighbor except the last one takes a short time, for example, 3 ms referred to in IEEE 802.15.5 standard, to complete the eEREQ and EREP exchange with the sender. When the last neighbor wakes up, the other neighbors wake up almost simultaneously to receive broadcast data. So, the ETROT of all neighbors for waiting the broadcast frame can be expressed by

ETRO T_{Semi - SES} = 3 \times (N - 1) mTU

(19)

The ETROT saved by Semi-SES over ASES can be expressed as

\begin{matrix} ETRO T_{saved} = ETRO T_{ASES} - ETRO T_{Semi - SES} \\ = N \times 0.5 \times 2^{WO} mTU - 3 \times (N - 1) mTU \\ > N \times (0.5 \times 2^{WO} - 3) mTU \end{matrix}

(20)

Therefore, when $WO \geq \log_{2}^{6}, ETRO T_{saved} > 0$ .

The numerical simulation result with N = 6 is shown in Figure 12.

Figure 12.

Expected total radio on time (ETROT) of the neighbors in broadcast.

In addition, the time for a node completing convening all neighbors is longer than a WI in ASES. In Semi-SES, the time for completing convening all neighbors depends on the last slot (LS) in which at least one node wakes up. For simplicity and without loss of generality, we assume the number of the slot in which a node has data ready to broadcast is 1. The probability that the ith slot is the LS can be expressed by

p (LS = i) = {(\frac{i}{L})}^{N} - {(\frac{i - 1}{L})}^{N}

(21)

where N indicates the number of neighbors and L is the number of time slots in a WI. The expected number of slots for completing convening all neighbors can be expressed as

E (LS) = \sum_{i = 1}^{L} [{(\frac{i}{L})}^{N} - {(\frac{i - 1}{L})}^{N}] \times i = L - \frac{1}{L^{N}} \sum_{i = 1}^{L - 1} i^{N}

(22)

Obviously, equation (22) is smaller than L, which means the time for completing broadcast in Semi-SES is shorter than that in ASES.

Experimental simulations

We compare the performance of Semi-SES with ASES in terms of energy consumption, memory used to store the EN-List, and so on. We use Visual Basic programming language to make the simulation programs. The values of all parameters used in the simulations are listed in Table 4.

Table 4.

Values of the parameters used in the simulations.

Symbol	Meaning	Values
$p_{idle}$	Power in listening	56.4 mW²¹
$p_{tx}$	Power in transmitting	52.2 mW²¹
$p_{r x}$	Power in receiving	56.4 mW²¹
NN	Number of nodes	Varying
	Time to Tx/Rx a byte	32 μs
	Radio radius	150 m
	Data packet size	100 bytes
	meshTTLOfHello³	2
WO	Wake-up order	Varying

In simulations, we deploy nodes in a square of 1000 × 1000 m². For a randomly generated network topology, a node is randomly selected as the sink and the routing tree rooted at the sink is formed per IEEE 802.15.5 standard. In each WI, each node generates a packet and sends it to the sink. Therefore, the data rate is related to WO. The AO is set to 1. The senders send EREQ frames to extend the active period of the receiver when the active period of the receiver is not long enough. The results shown below are from the average of 500 randomly generated topologies. The 95% confidence intervals of the corresponding statistics are calculated and shown in figures.

First, the energy consumption of Semi-SES and ASES are compared, where the energy consumption of nodes in inactive period are neglected. Figure 13 shows the results of simulations with 100 nodes under different WO. As shown in Figure 13, the energy consumption of nodes with tree level greater than 1 in Semi-SES is considerably less than that in ASES, which thanks to the nodes knowing the scheduling information of their neighbors. The energy consumption of nodes with tree level equal to 1 in ASES is similar to that in Semi-SES; it is because the neighbor nodes of the sink do not need to wait for the WN messages from the sink since the sink is always in active state. From Figure 13, we can also see that the energy consumption of ASES increases with the increase in WO. This is because with the increase in WO, the WI increases which results in the increase in the idle listening time of nodes when waiting for WN frames. As shown in Figure 13, the energy consumption of nodes except the neighbors of the sink decrease with the increase in the tree level of nodes since the nodes with smaller tree level have more data-forwarding responsibilities than the nodes with bigger tree level.

Figure 13.

Average energy consumption of nodes in each WI.

We also compare Semi-SES with ASES in terms of the size of the EN-List under different node density (ND). As shown in Figure 14, Semi-SES has slightly bigger sizes of the EN-List than ASES, since the EN-List of Semi-SES requires additional 3 bytes to hold the wake/sleep schedule information for each neighbor. For sensors that typically have hundreds of kilobytes of memory, these additional memory requirements are still affordable. It is cost-effective that Semi-SES trades less than 30% memory for more than 80% energy saving.

Figure 14.

Size of EN-List.

The performance of broadcast mechanisms in ASES and Semi-SES are compared. Figure 15 shows the time of completing broadcast (TCB). As shown in Figure 15, the TCB of Semi-SES is less than that of ASES and it increases with the increase in WO and the ND. This is because the ADs of nodes are randomly distributed in a WI, the growth of the WO, and the ND leads to the increase in time to wake up the last node.

Figure 15.

Time of completing broadcast.

Figure 16 shows the energy consumption of the sender in a broadcast. As shown in Figure 16, the energy consumption of the broadcasting node increases with the increase in the ND, because more eEREQ and EREP exchange between the sender and it neighbors are needed for waking up all neighbors as the ND increases.

Figure 16.

Energy consumption of the broadcasting node.

We compare the end-to-end delay in Semi-SES with ASES under different ND and the values of α from 0 to 1 with step 0.1. Figure 17 depicts the ratio of the end-to-end delay in Semi-SES to that in ASES. From Figure 17, it can be observed that the delay in Semi-SES is shorter than that in ASES, and the ratio increases with the increase in the coefficient α and decreases with the increase in the ND which imply that nodes have more neighbors. The reason behind this phenomenon is that the opportunity to find a low delay forwarding path increases when nodes have more neighbors.

Figure 17.

Delay ratio vs α.

We also compare Semi-SES with ASES in terms of average number of transmissions which implies the energy cost. The ratio of the average number of transmissions in Semi-SES to that in ASES is shown in Figure 18, which shows that the average number of transmissions in Semi-SES is larger than that in ASES. This is because a low delay forwarding path generally has more hops. It can also be observed that the ratio decreases with the increase in the coefficient α, and the reason for which is that the opportunity to find a low delay forwarding path is smaller with bigger α. It can also be observed that the ratio increases with the increase in the ND, and the reason behind this is the probability of finding a low delay forwarding path which increases with the increase in the number of neighbors. The number of transmissions is traded for lower delay in Semi-SES. Exactly speaking, we trade less than 20% number of transmissions for more than 25% and up to 50% delay.

Figure 18.

Ratio of the number of transmissions vs α.

In addition, we compare the end-to-end delay and the average number of transmissions in Semi-SES with ASES under different number of nodes with fixed ND and α set to 0. Figures 19 and 20 depict the ratio of the end-to-end delay and the average number of transmissions in Semi-SES to that in ASES, respectively. Figures 19 and 20 show that the ratio varies little with the number of nodes.

Figure 19.

Delay ratio in scenarios with fixed node density.

Figure 20.

Ratio of the number of transmissions in scenarios with fixed node density.

Finally, we evaluate the routing performance of the Semi-SES in comparison with the ASES in scenarios with unreliable wireless links, where some nodes fail temporarily. We conducted the simulations for the cases where the number of nodes is 100 and the failure probability of nodes is 1%, 5%, and 10%, respectively. The ratio of the end-to-end delay is shown in Figure 21, and the ratio of the average number of transmissions is shown in Figure 22.

Figure 21.

Ratio of the end-to-end delay vs α in scenarios with unreliable wireless links.

Figure 22.

Ratio of the number of transmissions vs α in scenarios with unreliable wireless links.

As depicted in Figures 21 and 22, the ratio of the end-to-end delay increases with the increase in the failure probability of nodes, and the ratio of the average number of transmissions decreases with the increase in the failure probability of nodes. The reason is that in Semi-SES, the sender will use the routing mechanism of ASES to select next hop when the next hop found by Semi-SES is failed.

Conclusion

We can conclude that in Semi-SES, nodes exchange the wake/sleep schedule information of their neighbors with each other by periodically broadcasting eHello messages. Consulting the wake/sleep schedule of neighbors, a node has data to send can calculate the WN time of the intended neighbor, and only needs to turn on its radio slightly earlier than the calculated WN time of the receiver, which greatly reduces the idle listening of the sender in unicast. The broadcast mechanism is also improved. Exploiting the wake/sleep schedule information, the broadcasting node can determine the optimal broadcast time, which shortens the procedure of completing broadcast. Obtaining the notified broadcast time from the eEREQ, the receiver can turn off the radio and keep sleeping until the broadcast time for saving energy, which also reduces idle listening. The routing mechanism proposed in Semi-SES could find a path with shorter delay than that in ASES.

Footnotes

Handling Editor: Eleonora Borgia

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 partially supported by Zhejiang provincial Top Key Discipline of Computer Science and Technology at Zhejiang Normal University (ZSDZZZZXK24), Zhejiang provincial Top Discipline of Cyber Security at Zhejiang Normal University, and Zhejiang provincial Natural Science Fund Project (Y18F030043).

ORCID iD

Li-yong Yuan

References

Estrin

Culler

Pister

et al . Connecting the physical world with pervasive networks. IEEE Pervas Comput 2002; 1(1): 59–69.

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

IEEE 802.15.5:2009. Mesh topology capability in wireless personal area networks (WPANs).

Lee

Zhang

Zheng

et al . IEEE 802.15.5 WPAN mesh standard-low rate part: meshing the wireless sensor networks. IEEE J Sel Area Comm 2010; 28(7): 973–983.

Lee

Zhang

Zhu

et al . Meshing wireless personal area networks: introducing IEEE 802.15.5. IEEE Commun Mag 2010; 48(1): 54–61.

Heidemann

Estrin

. An energy-efficient MAC protocol for wireless sensor networks. In: Proceedings of the 21st annual joint conference on computer and communications societies, New York, 23–27 June 2002, pp.1567–1576. New York: IEEE.

Yang

Tseng

EH-K

et al . Utilization based duty cycle tuning MAC protocol for wireless sensor networks. In: Proceedings of the global telecommunications conference, St. Louis, MO, 28 November–2 December 2005, pp.3258–3262. New York: IEEE.

Han

Fei

TARS: a traffic-adaptive receiver-synchronized MAC protocol for underwater sensor networks. ACM T Sensor Network 2017; 13(4): 1–25.

Polastre

Hill

Culler

. Versatile low power media access for wireless sensor networks. In: Proceedings of the international conference on embedded networked sensor systems, Maryland, 3–5 November 2004, pp.95–107. New York: ACM.

10.

Buettner

Yee

Anderson

et al . X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks. In: Proceedings of the 4th international conference on embedded networked sensor systems, Boulder, CO, 31 October–3 November 2006, pp.307–320. New York: ACM.

11.

Cao

et al . L²: lazy forwarding in low-duty-cycle wireless sensor network. IEEE/ACM Trans Netw 2015; 23(3): 922–930.

12.

Ghose

Pla

MAC protocols for wake-up radio: principles, modeling and performance analysis. IEEE T Ind Inform 2018; 14(5): 2294–2306.

13.

Lin

E-YA

Rabaey

Wolisz

. Power-efficient rendezvous schemes for dense wireless sensor networks. In: Proceedings of the international conference on communications, Paris, 20–24 June 2004, pp.3769–3776. New York: IEEE.

14.

Sun

Gurewitz

Johnson

. RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks. In: Proceedings of the 6th ACM conference on embedded network sensor systems, Raleigh, NC, 5–7 November 2008, pp.1–14. New York: ACM.

15.

Yang

Qiu

et al . RW-MAC: an asynchronous receiver-initiated ultra low power MAC protocol for wireless sensor networks. In: Proceedings of the IET international conference on wireless sensor network, Beijing, China, 15–17 November 2010, pp.393–398. New York: IEEE.

16.

Tian

Tang

RP-MAC: a passive MAC protocol with frame reordering for wireless sensor networks. Int J Wirel Inform Netw 2013; 20(1): 74–80.

17.

Park

Lee

Receiver-initiated MAC protocol for wireless sensor networks based on tree topology. Int J Distrib Sens N 2015; 2015(11): 210.

18.

Basagni

Petrioli

Spenza

. CTP-WUR: the collection tree protocol in wake-up radio WSNs for critical applications. In: Proceedings of the international conference on computing, networking and communications, Kauai, HI, 15–18 February 2016, pp.1–6. New York: IEEE.

19.

Wang

Cao

Mao

et al . Towards energy efficient duty-cycled networks: analysis, implications and improvement. IEEE T Comput 2016; 65(1): 270–280.

20.

Khalil

Hossain

Ahmed

DURI-MAC: a dual channel receiver initiated MAC protocol for wireless sensor network (WSN). In: Proceedings of the international conference on electrical, computer and communication engineering, Cox’s Bazar, Bangladesh, 16–18 February 2017. New York: IEEE.

21.

Xing

Chen

et al . Optimal beacon interval for TDMA-based MAC in wireless sensor networks. In: Proceedings of the 11th international conference on innovations in information technology, Dubai, United Arab Emirates, 1–3 November 2015, pp.156–161. New York: IEEE.