1 Introduction

A wireless sensor network is a special network with large numbers of nodes equipped with embedded microprocessors, sensors and radio modules. These nodes cooperate with each other to perform a common task, such as environment monitoring, target tracking and healthcare [1–3]. Recently, their applications is widely extended towards the new technology named Internet of Things (IoT) [4]. Sensor nodes are usually distributed within a geographical area either uniformly or with a special distribution [5]. They are very tiny and battery-powered and hence, operate with an extremely low energy resource. However due to the employment of these networks in dangerous or inaccessible environments, the replacement of node batteries is seldom possible. Therefore, based on this limitation, the sensor nodes must have a lifetime of several months or even years. Thus, one of the major challenges of these networks is that their sensor nodes survive for long periods of time on such limited energy resources. This need has motivated the current research to create innovative techniques for prolonging or maximizing the network lifetime of wireless sensor networks [6–12]. Given that the definition of a network lifetime thoroughly depends on the network application, it follows that often there is no unified definition. In most studies, the lifetime of a sensor network is considered as the duration of time in which the first node of the network runs out of energy [9, 11, 12]. In some studies, the network lifetime is assumed to be the time period in which a certain percentage of network nodes die [13]. In other works, the network lifetime is defined the time span in which the area covered by a sensor network for the collection and forwarding of data decreases to the determined threshold level [14]. In each sensor node, battery energy is consumed by different components of the sensor node. However the highest energy expenditure is due to the radio module of each sensor node [15]. In general, radio modules can operate in four distinct modes of operation, including data sending, data receiving, idle listening (IL) and sleeping. The way these operations are performed affect other important energy consumption factors such as collision and overhearing. An important observation regarding most radio modules is that operating in the IL mode results in significantly high power consumption, almost equal to that in the data receiving mode [15]. In the IL mode, a sensor node waiting to receive data, keeps its receiver on and just listens to the radio channel. Since operating the radio in the IL mode does not provide any advantage in terms of power, it is important to reduce the duration of the IL mode as much as possible. This fact has led to the design of new specific wireless sensor networks known as duty-cycled wireless sensor networks (DC-WSNs). In DC-WSNs, a suitable duty cycling mechanism for the operation of IL and sleeping modes is considered in order to attain optimum energy efficiency. This scheme which also called as sleep scheduling, can be performed either as an independent technique running on top of a MAC protocol or be strictly jointed with the MAC protocol itself [15]. Extensive researches have been performed in the field of special MAC protocols design and their challenges in wireless sensor networks [16–20]. In addition, duty cycling techniques can be divided into two main categories: synchronous and asynchronous schemes [21]. In the synchronous method, it is supposed that each sensor node wakes up at the same time as its neighbors. Therefore, sensor nodes wake up according to a given activity timing pattern and remain active for a short duration of time in order to communicate with their neighbors. Then they fall asleep until the next communication session. Synchronizing network nodes, especially on a large scale, may lead to a heavy signaling load on the network. In contrast, in the asynchronous technique, each sensor node is allowed to adjust its duty cycling pattern independently of others, thus eliminating the exchange of extra information among nodes. Hence, even though asynchronous methods may rank lower in terms of energy efficiency and lifetime, but they are easier to implement in real applications than synchronous ones. Li et al. [22] presented extensive research on the different kinds of MAC protocols and their features in DC-WSNs. In order to extend the lifetime of a data gathering tree-based DC-WSN, Anastasi et al. [23] suggested a new DC-WSNs by employing a synchronous protocol named the adaptive staggered sleep protocol (ASLEEP). ASLEEP dynamically adjusts the sleep time interval of nodes based on some specific network demands. In [20], a synchronous MAC protocol, named S-MAC, designed specifically for a sensor network, was proposed to improve the efficiency of the traditional carrier sense multiple access with collision avoidance (CSMA/CA) MAC protocol. S-MAC is the first duty cycling MAC protocol by which all nodes in a neighborhood simultaneously wake up and listen to the channel. In the S-MAC protocol, in order to synchronize nodes, a certain packet named SYNC is exchanged. B-MAC [19] and X-MAC [16] are two well-known asynchronous MAC protocols based on preamble sampling which utilize Low Power Listening (LPL) for sampling the preambles of the packets. In [18], an asynchronous MAC protocol, called AS-MAC was designed for multi-hop wireless sensor networks. AS-MAC asynchronously coordinates the waking time of neighboring nodes so as to decrease overhearing, contention and delay.

Another approach to energy conservation in wireless sensor networks is utilizing energy efficient routing protocols. These protocols have been well-studied in recent literature [24–27]. Employing such protocols in DC-WSNs can be numbered as a promising approach to prolong the network lifetime. Obviously, the procedure of such routing algorithms would definitely change in DC-WSNs. In [21], a comprehensive survey of the various aspects and current challenges of designing energy efficient routing protocols was thoroughly investigated in DC-WSNs. One of the fundamental issues in designing efficient routing protocols is energy balancing. In fact the energy balance issue is a necessary condition for maximizing the network lifetime [12]. Numerous research studies have considered this issue in their routing algorithm design [12, 13, 26, 28]. However, unfortunately this issue is not well-studied in DC-WSNs. This paper investigates a novel energy balance based maximum lifetime routing problem in asynchronous DC-WSNs. To achieve an energy balancing approach, sensor nodes are allowed to send their data into the sink nodes either in single hop or multi-hop manner. To model the issue, a new asynchronous MAC protocol is first proposed which utilizes K-Persistent Flooding of RTS and Random sending of CTS named as K-Persistent FRTS–RCTS. In this protocol, each transmitter for increasing its success probability of encountering a neighboring node in the IL mode, first repeats its request by flooding the RTS packets. After flooding a number of RTS packets, if the transmitter does not receive any CTS packets, it transmits the RTS packet directly to the sink. Under this protocol, it is shown that the maximum lifetime routing problem is formulated as a mixed integer nonlinear programming (MINLP) problem. To the best of our knowledge, this is the first mathematical programming model which addresses the maximum lifetime routing problem in asynchronous DC-WSNs which takes into account energy balancing factor. In the formulated problem, the optimization variables include the maximum number of RTS flooding requests (K) as the integer values and the flow rate of information on any route and the duty cycle of nodes both as the real values.

The reminder of this paper is organized as follows. Related work is summarized in Sect. 2. In Sect. 3 the network model and assumptions is introduced. In Sect. 4, the K-Persistent FRTS–RCTS MAC protocol is illustrated in detail. Based on the proposed MAC protocol, in Sect. 5 the energy constraints of the problem is computed according to the precise computations of energy consumption in each node in different activity modes. In Sect. 6, the method of formulating the final problem is presented based on all of the obtained constraints in the previous sections. In Sect. 7 the same maximization problem is formulated under the well-known X-MAC protocol. Section 8 presents evaluation results under various scenarios. Eventually Sect. 9 concludes the paper.

2 Related work

Many methods have been suggested for the lifetime maximization of wireless sensor networks based on energy efficient routing called the maximum lifetime routing problem. One of the first issues was presented by Chang and Tassiulas [29] who formulated the problem as a linear programming problem. In their modeling, the flow rates allocated to each link were considered as optimization parameters. Also the network lifetime was assumed to be the time duration for the first node of the network to de-energize. Madan and Lall [30] were the first researchers to present a pure distributed classic solution to this problem. Park and Sahni [31] proposed an online heuristic for the maximum lifetime routing problem in wireless sensor networks. In [32], a robust maximum lifetime routing was presented that considered the amount of energy allocated to each node as the optimization parameter. An energy-aware routing algorithm was proposed by Amgoth and Jana [25] for cluster-based wireless sensor networks. This algorithm was based on an intelligent strategy of cluster head (CH) selection, CHs residual energy, and the intra-cluster distance for cluster formation. All of the mentioned maximum lifetime routing policies suffer from two following major defects:

Firstly, it was assumed that all of the data communication among nodes is performed in a multi-hop manner and that there is no direct link between sensor nodes and sink nodes. However, this assumption results in a lack of energy balance in the network nodes and usually the nodes closer to the sink deactivate sooner than the others. Thus the network lifetime is often limited to the lifetime of the nodes closer to the sink. To eliminate this deficiency, Ok et al. [13] utilized both single and multi-hop transmission policies to address the issue of lifetime maximization, based on energy balancing. This issue was formulated by an integer linear programming problem and also a distributed protocol named distributed energy balance routing (DEBR) was presented for the practical implementation. In DEBR protocol, each node was allowed to choose its route toward the sink either directly or via a neighboring node as a data relay node. This choice was based on a given criterion of the energy cost.

Secondly, none of the mentioned routing mechanisms consider the operation of the other layers, whereas recently, the focus has changed towards joint optimization by considering different layers interaction called as cross-layer optimization [33–37]. One of the most important cross-layer approaches is considering joint routing and duty cycle scheduling or in other words, implementing the routing algorithms in DC-WSNs. In fact, although the individual aspects of the energy efficient routing, i.e. optimal routing and resource allocation, have been extensively studied, their interaction with a suitable duty cycling was disregarded. To meet this approach, Kartal et al. [38] presented a maximum lifetime routing problem in DC-WSNs and modeled it as a linear programming problem that considered all of the node operation modes. Assumed was the existence of an underlying synchronized duty cycle scheduling mechanism. It was also supposed that all of the sensor nodes operated with the same duty cycle. However, as the authors mentioned, it is obvious that this assumption cannot guarantee the maximum lifetime in the network. In [9] the issue of energy balance based lifetime maximization was proposed in wireless sensor networks which employed joint routing and asynchronous duty cycle scheduling named as EB-JRADCS. This issue was modeled by a standard signomial geometric programming (SGP) problem and also a particular solution was introduced for solving the problem. This paper shows that the EB-JRADCS is the special case of K-Persistent FRTS–RCTS MAC protocol, when the maximum number of RTS flooding requests (K) is equal to one.

3 Network model

Consider a wireless sensor network where V is the set of all sensor nodes. N sensor nodes are uniformly distributed and fixed in a specific region. Also, M sink nodes are placed in different locations of this area. Each sensor node contains primary battery energy E i and generates a fixed data rate of g i . Also it is assumed that sensor nodes have the ability of adjusting their transmission power level based on their own distance to the target node. Each sensor node forwards its generated information, either directly to the sink node or to one of its neighbors acting as a data relaying node. In the network consisting of multiple sinks, when information is sent directly to a sink, the data is sent to the nearest sink. To avoid data collision when data is being sent directly, it is assumed that a separate channel is used. It is clear that the number of neighbors that each node has, will completely depend on the node’s transmitting power level, because by an increase in the power transmission level of each node, more nodes as adjacent nodes, or in other words, relaying nodes will be covered. Now consider that each node covers a communicational radius R by sending a specific power level within its neighborhood. Later the effect of changing radius R or equivalently changing power transmission level is investigated on the network lifetime. The set of neighbors of sensor node i in coverage radius R is shown by \( N_{i}^{R} \). If \( r_{ij} \) denotes the rate of transmitting data from node i to j and \( S_{i} \) represents the nearest sink to node i, then flow conservation constraints will be shown as follows:

$$ \mathop \sum \limits_{{ j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} = \mathop \sum \limits_{{k:i \in N_{k}^{R} }} r_{ki} + g_{i} ,\quad \forall \,i \in V $$
(1)

Equation 1 shows that the sum of the outgoing data rate from any node involving the outgoing data rate toward neighbors and the outgoing data rate directly to the sink node is equal to the incoming data rate from nodes in which node i is their neighbor plus the data generated by node i itself. In fact, since all generated data should be sent to the sink nodes, the incoming and outgoing data rate at a sensor node is equal.

4 K-Persistent FRTS–RCTS MAC protocol

For the purpose of designing an asynchronous DC-WSN, this section proposes a new energy balance based asynchronous MAC protocol named K-Persistent FRTS–RCTS MAC. In the two well-known asynchronous preamble sampling based MAC protocols include B-MAC and X-MAC, load balancing factor is not considered. Hence, each sensor node in order to send a data packet to a sink node, just forwards the packet to one of its neighbors as the data relay node. This procedure is repeated until the data packet is forwarded to the sink node. In X-MAC protocol, which was proposed to overcome the drawback of the B-MAC that is having long time waiting at the intended receiver side and overhearing, the transmitter sends a series of short preambles as shown in Fig. 1. Each preamble contains an ID of the intended receiver. In order to energy conservation, the transmitter goes into sleep mode between two consecutive preambles. When the target receiver wakes up and receives the preamble, it sends the early ACK packet. Once receiving the ACK packet by the transmitter, it immediately sends the data packet. The major defect of this protocol is a lack of routing mechanism. To consider the routing in our proposed MAC protocol, the procedure of X-MAC protocol is altered and modified in both steps of RTS and CTS transmissions. It should be noted that the fundamental idea behind designing all of the asynchronous MAC protocols is the independence of the duty cycle of nodes from each other. The duty cycle of a node can be defined as the fraction of time in which a sensor node is active during a given fixed time called the duty cycle period (DCP). In each DCP, a sensor node performs some operations, including data sending, data receiving and idle listening during its waking time and during the remaining time it goes into sleep mode for conserving its battery energy. In sleep mode, the sensor node deactivates all of its communication components, so that energy expenditure in this condition is negligible. Due to the low traffic rate in wireless sensor networks, since the time related to sending and receiving data is so short in comparison to that of IL, the duty cycle of a node is usually considered as the ratio of IL time to DCP. The present paper uses this principle for calculating of the node duty cycle. According to this assumption, the following illustrates the procedure of the proposed MAC protocol in detail.

Fig. 1
figure 1

X-MAC protocol timing

Full size image

If sensor node j, the neighbor of node i, works with a given duty cycle denoted by \( dc_{j} \) and node i, in an arbitrary moment, sends a RTS packet to this node, the probability that node j is in the IL mode is \( dc_{j} \). When node i, needs to send a data packet to the sink node, due to its waking neighbors’ lack of awareness, node i first sends the RTS packet toward its neighbors by flooding, in a given radius R. The set of neighbors of sensor node i in coverage radius R is expressed as \( N_{i}^{R} \) and the number of them is denoted by \( \left| {N_{i}^{R} } \right| \). Also, the set of the waking and sleeping neighbors of node i is represented by \( WN_{i}^{R} \) and \( SN_{i}^{R} \) respectively. In terms of the waking or sleeping modes of node i’s neighbors, K-Persistent FRTS–RCTS MAC protocol works immediately after flooding RTS, according to one of the three following cases:

4.1 K-Persistent FRTS–RCTS MAC protocol: Case 1

Among all node i’s neighbors, k neighbors are in the IL mode. In this case, all of these neighbors receive the RTS packet sent by node i. In this condition, any of these neighbors can send a CTS packet in response to the received RTS packet. However, if at least two neighbors send the CTS packet immediately after receiving RTS, a collision will occur. To overcome this obstacle, K-Persistent FRTS–RCTS MAC protocol acts in two main phases: the CTS Random Scheduling (CRS) phase and the Data Scheduling (DS) phase. In the CRS phase, the transmitter node i, forms a time slotted window consisting of \( \left| {N_{i}^{R} } \right| \) slots. In fact, each of the slots is considered for receiving one of the CTS packets. The transmitter node, along with the RTS packet, sends a random and uniform sequence of numbers between 1 to \( \left| {N_{i}^{R} } \right| \), such that each of the numbers corresponds to one of the neighbors. In other words, one random number is assigned to each of the neighbors whether awake or asleep. The time duration of each slot in this window is equal to the time duration needed to receive one CTS packet. Each waking neighbor that has received the RTS packet, must send the CTS packet in its given slot number. To prevent wasting energy, each waking neighbor goes into sleep mode upon receiving the RTS packet and its own assigned slot number. It then wakes up in the assigned time slot and sends the CTS packet. The RTS transmitter listens to the radio channel until it receives the first CTS packet from its neighbors.

When the first CTS packet is received from a neighbor in nth slot of CRS phase, to avoid occurring collision between data packet and the remained CTS packets from other waking neighbors and also minimizing the energy consumption related to node i, this node goes into sleep mode and postpones sending its data packet at least \( |N_{i}^{R} | - n \) time slots. Finally after \( |N_{i}^{R} | \) time slots, the CRS phase is finished and the DS phase begins. In this phase a time slotted window consisting of \( \left| {N_{i}^{R} } \right| \) slots is used similarly. Because if sending data is performed immediately after the CRS phase, then the overhearing of data will occur by other senders of the CTS. This operation causes extra energy expenditure in the CTS senders, because other senders of the CTS packet are waiting to receive the data packet too. The DS phase consists of two parts. The first part is for sending the data packet from the transmitter to the receiver and conversely the second part is for sending the ACK packet from the receiver to the transmitter. In DS phase, if the data transmitter node receives the first CTS packet by a node in nth slot of the CRS phase, so it will send the data packet in nth slot of DS phase. To minimize energy wastage in this phase, the transmitter node just wakes up in the slot of sending data. Also in this phase, overhearing never occurs by any other CTS senders, because all of the CTS senders wake up only in the same time slot of the DS phase that is corresponding to their own specified CTS slot. In fact, the node which has sent its CTS packet later, just checks available carrier on the channel in its own data time slot. In this situation, if the carrier is not heard, the node goes back into sleep mode again. In Fig. 2, the timing related to the K-Persistent FRTS–RCTS MAC protocol in Case 1 is shown. In this figure, the color white indicates the node sleeping mode. According to Fig. 2, it is assumed that the transmitter node has ten neighbors and, at the moment of RTS flooding, only two neighbors, meaning that neighbors 1 and 2 are active or in the IL mode. Also, it is supposed that the assigned CTS random slots are the 7th and 4th slots for node 1 and 2 respectively, as determined by the transmitter. Therefore, node 2 is chosen as a data receiver node. Hence, after the end of the CRS phase, the data packet will be sent to this node, that is node 2, in the DS phase. Also, node 1 goes into sleep mode upon checking the channel and hearing no carrier.

Fig. 2
figure 2

K-Persistent FRTS–RCTS protocol timing (Case 1)

Full size image

Based on the illustrated protocol procedure in Case 1, it is possible to calculate the probability of receiving a data packet by one of the neighbors of node i such as j. If the set of node i’s waking neighbors, including j, in radius R is denoted by \( WN_{i}^{j} \) and the number of them is represented by \( \left| {WN_{i}^{j} } \right| \), then the probability of receiving a data packet by node j packet is:

$$ p\left( {r = j \left| { WN_{i}^{j} } \right.} \right) = \frac{1}{{\left| {WN_{i}^{j} } \right|}} ,\quad WN_{i}^{j} \subseteq N_{i}^{R} $$
(2)

In fact, due to the random and uniform assignment of slot numbers to all neighbors, the probability of sending the first CTS packet and, consequently, receiving of data by any of the neighbors will be the same. However, due to the independence of the duty cycle of nodes, the probability that the set of waking nodes, including node j is \( WN_{i}^{j} \), is calculated as follows:

$$ p\left( {WN_{i}^{j} } \right) = \mathop \prod \limits_{{k \in WN_{i}^{j} }} dc_{k} \mathop \prod \limits_{{k \in SN_{i}^{j} }} (1 - dc_{k} ),\quad WN_{i}^{j} \mathop \cup \nolimits SN_{i}^{j} = N_{i}^{R} $$
(3)

Finally, by using the total probability and conditional probability law, the probability of receiving a data packet by one of the neighbors of node i such as j denoted by \( p(r = j) \), is:

$$ p\left( {r = j} \right) = \mathop \sum \limits_{{ WN_{i}^{j} \subseteq N_{i}^{R} }} p\left( {r = j \left| { WN_{i}^{j} } \right.} \right) p\left( {WN_{i}^{j} } \right) = \mathop \sum \limits_{{ WN_{i}^{j} \subseteq N_{i}^{R} }} \frac{1}{{\left| {WN_{i}^{j} } \right|}}\mathop \prod \limits_{{k \in WN_{i}^{j} }} dc_{k} \mathop \prod \limits_{{k \in SN_{i}^{j} }} (1 - dc_{k} ) $$
(4)

In fact, in (4), the summation operator is performed on the all of the possible subsets of \( N_{i}^{R} \) including j.

4.2 K-Persistent FRTS–RCTS MAC protocol: Case 2

Here, all of the neighbors of node i are in the sleep mode. In this situation, node i can repeat its RTS flooding requests at equal time intervals of DCP. With this procedure, it can be expected that in its next attempts, node i increases its opportunity of encountering a neighbor in the IL mode. Actually, the aim of the protocol in this case is to increase the probability of being a neighbor in the IL mode without having to extend its duty cycle. If it is assumed that node j, which works with a duty cycle of \( dc_{j} \), is the only neighbor of node i and node i attempts K times to flood the RTS packet, then the probability that node j is in the IL mode versus the number of attempts is \( 1 - (1 - dc_{j} )^{K} \). By using this approach, it can be said from the node i’s point of view, node j works with the mentioned duty cycle. Now, this issue shall be investigated in a general manner. To this end, consider that the transmitter node i, before having flooded any RTS packets, specifies \( K_{i} \) random times \( t_{1} , t_{2} , \ldots , t_{{K_{i} }} \) with a uniform distribution in the DCP interval. If node i does not receive any CTS packets after flooding the first RTS packet at time \( t_{1} \) and waiting for a duration of time equal to the \( \left| {N_{i}^{R} } \right| \) time slots, it goes into sleep mode and examines its chance for a second time at \( t_{2} \). Similarly, if node i has not yet received any CTS packets after flooding the RTS packet at time \( t_{2} \) and waiting for a duration of time equal to the \( \left| {N_{i}^{R} } \right| \) time slots, it then repeats its request. In general, the probability that node j in the nth attempt corresponding to time \( t_{n} \) is the receiver of the data sent from node i, is computed as follows:

$$ p\left( {r = j \left| { K_{i } = n} \right. } \right) = \left[ {\mathop \sum \limits_{{ WN_{i}^{j} \subseteq N_{i}^{R} }} \frac{1}{{\left| {WN_{i}^{j} } \right|}}\mathop \prod \limits_{{k \in WN_{i}^{j} }} dc_{k} \mathop \prod \limits_{{k \in SN_{i}^{j} }} (1 - dc_{k} )} \right].\left( {\mathop \prod \limits_{{{\text{k}} \in N_{i}^{R} }} (1 - dc_{k} )} \right)^{n - 1} $$
(5)

If node i, repeats its requests at most K i times, the probability of success will be in one of the attempts between 1 to K i . Therefore, the probability of receiving data by node j is calculated as follows:

$$ \begin{aligned} p\left( {r = j } \right) = p\left( {r = j \left| { n \in [1,} \right.K_{i } ] } \right) = & \mathop \sum \limits_{n = 1}^{{K_{i } }} \left[ {\mathop \sum \limits_{{ WN_{i}^{j} \subseteq N_{i}^{R} }} \frac{1}{{\left| {WN_{i}^{j} } \right|}}\mathop \prod \limits_{{k \in WN_{i}^{j} }} dc_{k} \mathop \prod \limits_{{k \in SN_{i}^{j} }} \left( {1 - dc_{k} } \right)} \right].\left( {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{n - 1} \\ = & \left[ {\mathop \sum \limits_{{ WN_{i}^{j} \subseteq N_{i}^{R} }} \frac{1}{{\left| {WN_{i}^{j} } \right|}}\mathop \prod \limits_{{k \in WN_{i}^{j} }} dc_{k} \mathop \prod \limits_{{k \in SN_{i}^{j} }} \left( {1 - dc_{k} } \right)} \right].\mathop \sum \limits_{n = 1}^{{K_{i } }} \left( {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{n - 1} \\ = & \left[ {\mathop \sum \limits_{{ WN_{i}^{j} \subseteq N_{i}^{R} }} \frac{1}{{\left| {WN_{i}^{j} } \right|}}\mathop \prod \limits_{{k \in WN_{i}^{j} }} dc_{k} \mathop \prod \limits_{{k \in SN_{i}^{j} }} \left( {1 - dc_{k} } \right)} \right].\frac{{1 - \left( {\mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{{K_{i} }} }}{{1 - \mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)}} \\ \end{aligned} $$
(6)

In Fig. 3, the protocol timing related to this case is shown. Again, it is supposed that the transmitter node has ten neighbors. As seen, after flooding the first RTS packet and waiting for a duration of time equal to ten time slots, the transmitter has not received any CTS from the neighbors; thus, it repeats its request for a second time, but again encounters all its neighbors in sleep mode. Thus the flooding of RTS packet is repeated for a third time. At this moment, two neighbors are in the IL mode. Consequently they receive the RTS packet and send CTS packets to the transmitter with a mechanism similar to that mentioned in Case 1. According to Fig. 3, node 1, which sends the CTS packet sooner than node 2, will be chosen as the data receiver node and so will receive the data packet in DS phase.

Fig. 3
figure 3

K-Persistent FRTS–RCTS protocol timing (Case 2)

Full size image

4.3 K-Persistent FRTS–RCTS MAC protocol: Case 3

Even after \( K_{i} \) attempts of flooding the RTS packet and waiting for a duration of time equal to the \( \left| {N_{i}^{R} } \right| \) time slots, still all of the node i’s neighbors are in sleep mode. In fact, in this case, \( WN_{i}^{R} \) is an empty set or, in other words, \( SN_{i}^{j} \) is equal to \( N_{i}^{R} \). In this situation, node i increases its transmitter power level according to its distance to the nearest sink and after sending the RTS packet to the sink node and receiving the corresponding CTS packet, sends the data packet directly to the sink node. In Fig. 4, the protocol timing related to this case is presented. In this case, the probability of receiving a data packet by the sink node sent by node i, as denoted by \( p\left( {r = S_{i} } \right) \) is computed as follows:

$$ p\left( {r = S_{i} } \right) = p\left( {WN_{i}^{j} = \emptyset } \right) = p\left( {SN_{i}^{j} = N_{i}^{R} } \right) = \left[ {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right]^{{K_{i} }} $$
(7)

In (7), \( S_{i} \) represents the nearest sink to node i. According to the three possible cases of the proposed protocol, after sending each data packet by transmitter node i, either one of the members of set \( N_{i}^{R} \), such as j, with a probability of \( p(r = j) \), is a data relay node or the nearest sink with a probability of \( p\left( {r = S_{i} } \right) \) is the receiver. If the network, works for a long duration of time T, and during this time, node i sends \( R_{i} \) data packets, then the number of sent packets for all of the neighbors and also the sink node is written as follows:

$$ R_{i} = \mathop \sum \limits_{{j \in N_{i}^{R} }} R_{ij} + R_{{iS_{i} }} $$
(8)

In (8) \( R_{ij} \), represents all of the outgoing packets from node i to j and \( R_{{iS_{i} }} \) is all of the outgoing packets from node i to sink \( S_{i} \). Therefore, it can be said that the ratio of all the outgoing packets from sensor node i to j to the total number of outgoing packets from node i is equal to the probability of receiving data by node j. Similarly, the ratio of all the outgoing packets from node i to sink \( S_{i} \), to the total number of outgoing packets from node i, is equal to the probability of receiving data by the sink \( S_{i} \), Thus the following can be written:

$$ \frac{{R_{ij} }}{{R_{i} }} = p(r = j) $$
(9)
$$ \frac{{R_{{iS_{i} }} }}{{R_{i} }} = p(r = S_{i} ) $$
(10)

If the sending of all data packets by node i, happens within the time duration of T, by dividing the numerator and denominator of the fractions on the left side hand of (9) and (10) by T and by using (6) and (7), we have:

$$ r_{ij} = \left[ {\mathop \sum \limits_{{ WN_{i}^{j} \subseteq N_{i}^{R} }} \frac{1}{{\left| {WN_{i}^{j} } \right|}}\mathop \prod \limits_{{k \in WN_{i}^{j} }} dc_{k} \mathop \prod \limits_{{k \in SN_{i}^{j} }} \left( {1 - dc_{k} } \right)} \right].\frac{{1 - \left( {\mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{{K_{i} }} }}{{1 - \mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)}}.\mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} $$
(11)
$$ r_{{iS_{i} }} = \left[ {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right]^{{K_{i} }} . \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} $$
(12)

In the above equations or in other words, constraints, the share of the outgoing data flow rate to any of neighbors or to the sink node in proportion to the total amount of the outgoing data flow rate by node i is calculated. Therefore these equations are called as Flow Sharing (FS) constraints.

Fig. 4
figure 4

K-Persistent FRTS–RCTS protocol timing (Case 3)

Full size image

4.4 Special Case: 1-Persistent FRTS–RCTS MAC protocol

In the proposed MAC protocol, there is one special case that we name it as the 1-Persistent FRTS–RCTS MAC protocol. This special case is equivalent to the MAC protocol introduced in [9] named as FRTS–RCTS protocol. In FRTS–RCTS MAC, or in other words, 1-Persistent FRTS–RCTS MAC, it was considered that each transmitter just floods the RTS packet to its neighbors once and if the transmitter does not receive any CTS packets during the CRS phase, it sends the data packet directly to the sink. In fact, the procedure described for the main MAC protocol in Case 2 was not considered. In Sect. 8 we will compare the performance of the special case against that of the general form.

5 Energy consumption model

In each sensor node, data sending, data receiving and idle listening operations are the major factors in energy expenditure. In comparison, other operations, such as sensing or information processing, can be considered as negligible factors. The present study employs the basic model presented in [39] for the energy consumption modeling of sending and receiving data statuses. According to this model, the energy required to send one unit of data from node i to j can be determined as follows:

$$ E_{t}^{ij} = e_{elec} + e_{amp} (d_{ij} )^{\beta } $$
(13)

where \( e_{elec} \) and \( e_{amp} \) are fixed coefficients related to the energy consumption of electronic equipment and the transmitter amplifier module of a sensor node respectively. Also, \( d_{ij} \) is the Euclidean distance between node i and j and β is the path loss exponent which is typically in the range of 2 to 6, depending on the environment. In the case of receiving data, the energy consumption of each node is a fixed value as \( E_{r} = e_{elec} \). Finally, in the IL mode, the amount of energy consumption is dependent on the radio module of the sensor node. Due to negligible energy consumption in the sleep mode, this paper does not address this mode of operation. According to the mentioned model, in the next part, the amount of energy expenditure is computed based on the proposed MAC protocol.

5.1 Energy consumption computation in the K-Persistent FRTS–RCTS MAC protocol

Based on Fig. 2, the energy consumed by node \( i \in V \), for sending one data packet to neighbor node j, consists of the energy consumption of flooding the RTS packet in radius \( R\left( {E_{f\_RTS}^{R} } \right) \), energy consumption of time waiting to receive the first CTS packet from a neighbor (\( E_{w\_CTS}^{i} \)), the energy consumption of receiving one CTS packet (\( E_{r\_CTS} \)), the energy consumption of sending one data packet to node j, \( \left( {E_{t\_DATA}^{ij} } \right) \) and finally the energy consumption of receiving the ACK packet (\( E_{r\_ACK} \)). Therefore, the energy consumption of node i for sending a data packet to neighbor j, without considering the energy consumed for flooding at most \( K_{i } \) RTS packets nor the energy consumed in the IL mode while waiting to receive the first CTS packet, as denoted by \( E_{t}^{ij} \) is calculated as follows:

$$ E_{t}^{ij} = E_{r\_CTS} + E_{t\_DATA}^{ij} + E_{r\_ACK} $$
(14)

For simplicity, the energy consumed for flooding at most K i RTS packets and the energy consumed in the IL mode while waiting to receive the first CTS packet will be computed separately. According to the proposed MAC protocol in Case 3, if any CTS packets is not received after the end of the K i th CRS phase, the transmitter node, by adjusting its transmitting power level, sends the RTS packet to the nearest sink. In this situation, the energy consumption of node i for sending a data packet to the sink, without counting the energy consumed for flooding at most K i RTS packets nor the energy consumed while it is waiting to receive the first CTS packet, as denoted by \( E_{t}^{{iS_{i} }} \), is calculated as follows:

$$ E_{t}^{{iS_{i} }} = E_{t\_RTS}^{{iS_{i} }} + E_{r\_CTS} + E_{t\_DATA}^{{iS_{i} }} + E_{r\_ACK} $$
(15)

In (15), the energy consumption of sending the RTS packet and of sending a data packet from node i to sink \( S_{i} \) is denoted by \( E_{t\_RTS}^{{iS_{i} }} \) and \( E_{t\_DATA}^{{iS_{i} }} \) respectively. If the rate of outgoing data from node i to j either to a neighbor or to the sink \( S_{i} \) is represented by \( r_{ij} \), therefore, the average consumed power of node i for sending data denoted by \( P_{t}^{i} \) is computed as follows:

$$ P_{t}^{i} = \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} E_{t}^{ij} \cdot r_{ij} $$
(16)

Next step is the calculation for the energy consumption for flooding at most \( K_{i} \) RTS packets from a transmitter to its neighbors. To this end, the number of attempts is modeled by a random variable X. Since the number of attempts can be a number between 1 to \( K_{i} \), if the network works for a long time, it can be said that the expected value of X expresses the average number of attempts. To calculate the expected value of X versus the number of attempts \( n \), we have:

  • The success probability at the first attempt:

    $$ p\left( {X = 1 } \right) = p (success | n = 1) = 1 - \mathop \prod \limits_{{k \in N_{i}^{R} }} (1 - dc_{k} ) $$
    (17)

  • And generally the success probability at the mth attempt:

    $$ p\left( {X = m } \right) = p (success | n = m) = \left( {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{m - 1} \cdot p\left( {X = 1 } \right) $$
    (18)

Finally, the probability that the transmitter floods the RTS packet for the \( K_{i} \)th time is equal to the probability of failure in all of the previous attempts. Therefore:

$$ p\left( {X = K_{i} } \right) = p(failure\quad \forall \; all\;n < K_{i} ) = \left( {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{{K_{i} - 1}} $$
(19)

Hence, the expected value of X is computed as follows:

$$ \begin{aligned} E\left[ X \right] = & \mathop \sum \limits_{n = 1}^{{K_{i} }} n \cdot p\left( {X = n } \right) = p\left( {X = 1} \right) \cdot \mathop \sum \limits_{n = 1}^{{K_{i} - 1}} n \cdot \left( {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{n - 1} + K_{i} \cdot \left( {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{{K_{i} - 1}} \\ = & 1 + \left( {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right) + \left( {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{2} + \cdots + \left( {\mathop \prod \limits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{{K_{i} - 1}} = \frac{{1 - \left( {\mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{{K_{i} }} }}{{1 - \mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)}} \\ \end{aligned} $$
(20)

Since for sending each data packet, \( E\left[ X \right] \) RTS packets are flooded on the average; therefore if the data outgoing rate of node i is \( \mathop \sum \limits_{{ j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} \), the rate of flooding RTS packets would be \( E\left[ X \right] \times \mathop \sum \limits_{{ j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} \). Hence, by using (20), the average consumed power of flooding RTS packets, denoted by \( P_{t\_RTS}^{R} \), is calculated as follows:

$$ P_{f\_RTS}^{R} = E_{f\_RTS}^{R} .\left( {\frac{{1 - \left( {\mathop \prod \nolimits_{{k \in N_{i}^{R} }} (1 - dc_{k} )} \right)^{{K_{i} }} }}{{1 - \mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)}}} \right). \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} $$
(21)

Now, we can calculate the energy consumption related to the transmitter waiting time to receive the first CTS packet during the IL mode. According to the proposed MAC protocol, when node i wants to send a data packet, first it sends at most K i RTS packets to its neighbors in radius R by flooding. In this case it waits \( \left| {N_{i}^{R} } \right| \) time slots between every two sequential RTS attempts. If, after sending a number of RTS packets, the first CTS packet is received in the \( k_{slot} \) th slot of the CRS phase, the waiting time of node i is finished. However, the average number of sent RTS packets is \( E\left[ X \right] \). Hence, if the time duration of each slot in the CRS phase is \( t_{s} \), the amount of time waiting to receive the first CTS packet, denoted by \( CWT_{i} \), can be calculated as follows:

$$ CWT_{i} = (E\left[ X \right] - 1) \cdot \left| {N_{i}^{R} } \right| \cdot t_{s} + (k_{slot} - 1) \cdot t_{s} $$
(22)

Now we compute \( k_{slot} \). After flooding \( E\left[ X \right] \) RTS packets by the transmitter, the number of waking neighbors can be a number between 0 to \( \left| {N_{i}^{R} } \right| \). Consider that at the moment of flooding the RTS packet, the number of waking neighbors is k. In this situation, according to the MAC protocol in Case 1, transmitter node i sends a random sequence of numbers 1 to \( \left| {N_{i}^{R} } \right| \) to all of its neighbors such that each of the random numbers is assigned to one of the neighbors. Since the transmitter node chooses the first CTS transmitter as the receiver of the data packet, we can consider the average of the received slot numbers as the received slot number of the CTS packet on the whole working time of the network. Assume that Y is a random variable used for showing the slot number in which the first CTS packet is received by node i. If \( E_{k} \left[ Y \right] \) is used to represent the expected value of the random variable Y, when there are k waking neighbors, the number of waiting slots is \( E_{k} \left[ Y \right] - 1 \). In [9] it has been shown that based on the different values of k, \( E_{k} \left[ Y \right] \) can be computed as the following equation. The interested readers are referred to [9] for further details on proving the equation.

$$ E_{k} \left[ Y \right] = \left\{ {\begin{array}{*{20}c} {\frac{{\left| {N_{i}^{R} } \right| + 1}}{k + 1},} & {k < 2} \\ {\frac{{\prod\limits_{m = 0}^{k - 2} {\left( {\left| {N_{i}^{R} } \right| - n - m} \right)} }}{{ \left( {\begin{array}{*{20}c} {\left| {N_{i}^{R} } \right|} \\ k \\ \end{array} } \right) \cdot \left( {k - 1} \right)!}},} & {k \ge 2} \\ \end{array} } \right. $$
(23)

Now, let \( \Omega_{i}^{k} \) be a k-member subset of \( N_{i}^{R} \). The probability that among \( \left| {N_{i}^{R} } \right| \) neighbors, only the neighbors belonging to \( \Omega_{i}^{k} \) are awake at the flooding moment of RTS denoted by \( p(\Omega_{i}^{k} ) \) is as follows:

$$ p\left( {\Omega_{i}^{k} } \right) = \mathop \prod \limits_{{k \in \Omega_{i}^{k} }} dc_{k} \mathop \prod \limits_{{k \in N_{i}^{R} - \Omega_{i}^{k} }} (1 - dc_{k} ) $$
(24)

By using (23) and (24), \( k_{slot} \) is computed as follows and hence by using (22), \( CWT_{i} \) is determined.

$$ k_{slot} = \mathop \sum \limits_{k = 0}^{{\left| {N_{i}^{R} } \right|}} E_{k} \left[ Y \right] \cdot \mathop \sum \limits_{{\Omega_{i}^{k} \subseteq N_{i}^{R} }} p\left( {\Omega_{i}^{k} } \right) $$
(25)

Finally if the average consumed power of each node in IL mode is \( P_{IL} \), the average consumed power of node i in the waiting time for receiving the first CTS packet from its neighbors versus outgoing data rate, denoted by \( P_{w - CTS}^{i} \), is calculated as follows:

$$ P_{w\_CTS}^{i} = E_{w\_CTS}^{i} \cdot \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} = P_{IL} \cdot CWT_{i} \cdot \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} $$
(26)

In the data receiving mode, if the receiver node is not the first transmitter of CTS packet, thus it will not receive any data packet in the DS Phase. However, if receiver node k is the first transmitter of the CTS packet, the energy consumption of node i includes the energy consumed by receiving a data packet from node k and energy consumed by sending an ACK packet. Therefore:

$$ E_{r\_DATA}^{ki} = E_{r\_DATA} + E_{t\_ACK}^{ik} $$
(27)

If node i’s data receiving rate from each node such as k is \( r_{ki} \), then node i’s average consumed power in the receiving data mode denoted by \( P_{r\_DATA}^{i} \) will be:

$$ P_{r\_DATA}^{i} = \mathop \sum \limits_{{k:i \in N_{i}^{R} }} E_{r\_DATA}^{ki} .r_{ki} $$
(28)

If the node i receives a RTS packet, two possible cases occur. Either node i is the first transmitter of CTS packet or not. It is obvious that in both cases, it will send CTS packet to the transmitter. So, either in the first or second case, the energy consumption denoted by \( E_{r\_RTS,t\_CTS}^{ik} \) is:

$$ E_{r\_RTS,t\_CTS}^{ik} = E_{r\_RTS} + E_{t\_CTS}^{ik} $$
(29)

If data sending rate of every node such as k, which node i is one of its neighbors, to all of its neighbors is denoted by \( \mathop \sum \limits_{{j \in N_{k}^{R} }} r_{kj } \) and node i works with a duty cycle of \( dc_{i} \), therefore the share of receiving rate of RTS packets from node k to i denoted by \( S_{r\_CTS}^{ki} \) is as follows:

$$ S_{r\_CTS}^{ki} = dc_{i} \cdot \mathop \sum \limits_{{j \in N_{k}^{R} }} r_{kj} $$
(30)

So the average consumed power of node i for receiving RTS packets from node k and sending CTS packets to it which is denoted by \( P_{r\_RTS,t\_CTS}^{ik} \) is as follows:

$$ P_{r\_RTS,t\_CTS}^{ik} = E_{r\_RTS,t\_CTS}^{ik} \cdot S_{r\_CTS}^{ki} $$
(31)

Thus using (30) and (31), the average consumed power of node i in receiving all RTS packets from all of the neighbors that node i is their neighbor and sending all CTS packets to them denoted by \( P_{r\_RTS,t\_CTS}^{i} \) is calculated as follows:

$$ P_{r\_RTS,t\_CTS}^{i} = \mathop \sum \limits_{{k:i \in N_{k}^{R} }} P_{r\_RTS,t\_CTS}^{ik} = \mathop \sum \limits_{{k:i \in N_{k}^{R} }} E_{r\_RTS,t\_CTS}^{ik} \cdot dc_{i} \cdot \mathop \sum \limits_{{j \in N_{k}^{R} }} r_{kj} = dc_{i} \cdot \mathop \sum \limits_{{k:i \in N_{k}^{R} }} E_{r\_RTS,t\_CTS}^{ik} .\mathop \sum \limits_{{j \in N_{k}^{R} }} r_{kj} $$
(32)

In the IL mode, sensor node i listens to the radio channel to receive any RTS packets, therefore, if it works with a duty cycle of \( dc_{i} \), then its average consumed power will be:

$$ P_{IL}^{i} = P_{IL} \cdot dc_{i} $$
(33)

Finally, using (16), (21), (22), (26), (28), (32), and (33), the average consumed power of node i denoted by \( \bar{P}_{i}^{cons} \) is calculated as follows:

$$ \begin{aligned} \bar{P}_{i}^{cons} = & E_{f\_RTS}^{R} \cdot \frac{{1 - \left( {\mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{{K_{i} }} }}{{1 - \mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)}} \cdot \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} + \left( {\left[ {\frac{{1 - \left( {\mathop \prod \nolimits_{{k \in N_{i}^{R} }} (1 - dc_{k} )} \right)^{{K_{i} }} }}{{1 - \mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)}} - 1} \right] \cdot \left| {N_{i}^{R} } \right| \cdot t_{s} } \right. \\ & + \left. {\left[ {\mathop \sum \limits_{k = 0}^{{\left| {N_{i}^{R} } \right|}} E_{k} \left[ Y \right] \cdot \mathop \sum \limits_{{\Omega_{i}^{k} \subseteq N_{i}^{R} }} \left[ { \mathop \prod \limits_{{k \in \Omega_{i}^{k} }} dc_{k} \mathop \prod \limits_{{k \in N_{i}^{R} - \Omega_{i}^{k} }} (1 - dc_{k} )} \right] - 1} \right] \cdot t_{s} } \right) \cdot P_{IL} \cdot \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} \\ & + \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} E_{t}^{ij} \cdot r_{ij} + dc_{i} \cdot \mathop \sum \limits_{{k:i \in N_{k}^{R} }} E_{r\_RTS,t\_CTS}^{ik} \cdot \mathop \sum \limits_{{j \in N_{k}^{R} }} r_{kj} + \mathop \sum \limits_{{k:i \in N_{i}^{R} }} E_{r\_DATA}^{ki} \cdot r_{ki} + P_{IL} \cdot dc_{i} \\ \end{aligned} $$
(34)

Or equivalently:

$$ \begin{aligned} \bar{P}_{i}^{cons} = & \left( {\left[ {\frac{{1 - \left( {\mathop \prod \nolimits_{{k \in N_{i}^{R} }} (1 - dc_{k} )} \right)^{{K_{i} }} }}{{1 - \mathop \prod \nolimits_{{k \in N_{i}^{R} }} (1 - dc_{k} )}}} \right] \cdot \left[ {E_{f\_RTS}^{R} + \left| {N_{i}^{R} } \right| \cdot t_{s} \cdot P_{IL} } \right] - \left| {N_{i}^{R} } \right| \cdot t_{s} \cdot P_{IL} } \right. \\ \left. {\quad + \left[ {\mathop \sum \limits_{k = 0}^{{\left| {N_{i}^{R} } \right|}} E_{k} \left[ Y \right] \cdot \mathop \sum \limits_{{\Omega_{i}^{k} \subseteq N_{i}^{R} }} \left[ { \mathop \prod \limits_{{k \in \Omega_{i}^{k} }} dc_{k} \mathop \prod \limits_{{k \in N_{i}^{R} - \Omega_{i}^{k} }} (1 - dc_{k} )} \right] - 1} \right] \cdot t_{s} \cdot P_{IL} } \right) \cdot \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} \\ \quad + \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} E_{t}^{ij} \cdot r_{ij} + dc_{i} \cdot \mathop \sum \limits_{{k:i \in N_{k}^{R} }} E_{r\_RTS,t\_CTS}^{ik} \cdot \mathop \sum \limits_{{j \in N_{k}^{R} }} r_{kj} + \mathop \sum \limits_{{k:i \in N_{i}^{R} }} E_{r\_DATA}^{ki} \cdot r_{ki} + P_{IL} \cdot dc_{i} \\ \end{aligned} $$
(35)

6 Problem formulation

In this section, the problem is constructed based on all of the obtained constraints. If node i works in time duration \( T_{i} \) and its initial battery energy is \( E_{i} \), then its energy constraint under, the given flow rate \( \varvec{R}^{\varvec{i}} = \left\{ {r_{ij} } \right\} \), duty cycle \( dc_{i} \) and maximum number of RTS flooding requests \( K_{i} \) will be written as:

$$ \bar{P}_{i}^{cons} \cdot T_{i} (\varvec{R}^{\varvec{i}} ,dc_{i} ,K_{i} ) \le E_{i} $$
(36)

Now, the network lifetime is defined as the minimum lifetime over all nodes, i.e.,

$$ T_{net} = \mathop {min}\limits_{i \in V} T_{i} (\varvec{R}^{\varvec{i}} ,dc_{i} ,K_{i} ) $$
(37)

Our goal is to compute flow data rates, the duty cycle of all nodes and, the maximum number of RTS flooding requests so that the network lifetime is maximized. This maximization is carried out by considering the three mentioned constraints including the flow conservation constraints, FS constrains and energy constrains calculated in (1), (11), (12) and (35). Thus the maximization problem can be written as follows:

$$ \begin{aligned} maximize\left( {\mathop {min}\limits_{i \in V} T_{i} (\varvec{R}^{\varvec{i}} ,dc_{i} ,K_{i} )} \right) \hfill \\ \mathop \sum \limits_{{ j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} - \mathop \sum \limits_{{k:i \in N_{k}^{R} }} r_{ki} = g_{i} ,\quad \forall i \in V \hfill \\ \bar{P}_{i}^{cons} \cdot T_{i} \left( {R^{i} ,dc_{i} ,K_{i} } \right) \le E_{i} ,\quad \forall i \in V \hfill \\ r_{ij} = \left[ {\mathop \sum \limits_{{ WN_{i}^{j} \subseteq N_{i}^{R} }} \frac{1}{{\left| {WN_{i}^{j} } \right|}}\mathop \prod \limits_{{k \in WN_{i}^{j} }} dc_{k} \mathop \prod \limits_{{k \in SN_{i}^{j} }} (1 - dc_{k} )} \right] \cdot \frac{{1 - \left( {\mathop \prod \nolimits_{{k \in N_{i}^{R} }} (1 - dc_{k} )} \right)^{{K_{i} }} }}{{1 - \mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)}} \cdot \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} ,\quad \forall i \in V \hfill \\ r_{{iS_{i} }} = \left( {\mathop \prod \limits_{{{\text{k}} \in N_{i}^{R} }} (1 - dc_{k} )} \right)^{{K_{i} }} \cdot \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} ,\quad \forall i \in V \hfill \\ \end{aligned} $$
(38)

Obviously, (38) is a max–min problem which can be rewritten as a maximization problem as follows:

$$ \begin{aligned} maximize\left( T \right) \hfill \\ \mathop \sum \limits_{{ j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} - \mathop \sum \limits_{{k:i \in N_{k}^{R} }} r_{ki} = g_{i} ,\quad \forall i \in V \hfill \\ \left( {\left[ {\frac{{1 - \left( {\mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{{K_{i} }} }}{{1 - \mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)}} - 1} \right] \cdot \left[ {E_{f\_RTS}^{R} + \left| {N_{i}^{R} } \right| \cdot t_{s} \cdot P_{IL} } \right] + E_{f\_RTS}^{R} + \left[ {\mathop \sum \limits_{k = 0}^{{\left| {N_{i}^{R} } \right|}} E_{k} \left[ Y \right] \cdot \mathop \sum \limits_{{\Omega_{i}^{k} \subseteq N_{i}^{R} }} \left[ { \mathop \prod \limits_{{k \in \Omega_{i}^{k} }} dc_{k} \mathop \prod \limits_{{k \in N_{i}^{R} - \Omega_{i}^{k} }} \left( {1 - dc_{k} } \right)} \right] - 1} \right] \cdot t_{s} \cdot P_{IL} } \right) \cdot \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} + \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} E_{t}^{ij} \cdot r_{ij} \hfill \\ \quad +\quad dc_{i} \cdot \mathop \sum \limits_{{k:i \in N_{k}^{R} }} E_{r\_RTS,t\_CTS}^{ik} \cdot \mathop \sum \limits_{{j \in N_{k}^{R} }} r_{kj} + \mathop \sum \limits_{{k:i \in N_{i}^{R} }} E_{r\_DATA}^{ki} \cdot r_{ki} +\quad P_{IL} .dc_{i} \le E_{i} \cdot T^{ - 1} , \forall \;i \in V \hfill \\ r_{ij} = \left[ {\mathop \sum \limits_{{ WN_{i}^{j} \subseteq N_{i}^{R} }} \frac{1}{{\left| {WN_{i}^{j} } \right|}}\mathop \prod \limits_{{k \in WN_{i}^{j} }} dc_{k} \mathop \prod \limits_{{k \in SN_{i}^{j} }} \left( {1 - dc_{k} } \right)} \right] \cdot \frac{{1 - \left( {\mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{{K_{i} }} }}{{1 - \mathop \prod \nolimits_{{k \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)}} \cdot \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} ,\quad \forall \;i \in V \hfill \\ r_{{iS_{i} }} = \left( {\mathop \prod \limits_{{{\text{k}} \in N_{i}^{R} }} \left( {1 - dc_{k} } \right)} \right)^{{K_{i} }} \cdot \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} r_{ij} ,\quad \forall \;i \in V \hfill \\ \end{aligned} $$
(39)

As seen, (39) is a mixed integer nonlinear programming (MINLP) problem. In this problem, the optimization variables consist of the maximum number of RTS flooding requests (K) as the integer values, and the flow rate of information on any route and the duty cycle of nodes both as the real values. In the next section the same maximization problem is investigated under the X-MAC protocol.

7 Maximum lifetime routing problem under the X-MAC protocol

In this section the problem of maximum lifetime routing is investigated under the well-known X-MAC protocol. According to the procedure of X-MAC as shown in Fig. 1, the energy consumption of each transmitter node such as node i for sending one data packet, consists of the energy consumption of sending a number of preambles to each individual receiver such as node j, the energy consumption of receiving one early ACK packet (\( E_{r\_eACK} \)), the energy consumption of sending one data packet to node j, \( (E_{t\_DATA}^{ij} ) \) and finally, the energy consumption of receiving the ACK packet (\( E_{r\_ACK} \)). Consider \( t_{IL}^{j} \) and \( t_{sleep}^{j} \) denote IL and sleep periods of the receiver node j. Also, the duration of preamble and the early ACK packet is represented by \( t_{preamble} \) and \( t_{eACK} \). According to [16], in each transmitter, the duration of the IL between two consecutive preambles is equal to the time needed for receiving one early ACK packet, that is \( t_{eACK} \). Since, each transmitter has to send preambles until its intended receiver such as node j wakes up, the average time for this action, when node i begins a transmission is \( t_{sleep}^{j} /2 \). Therefore the number of the sent preambles by the transmitter in each data sending session can be calculated as follows:

$$ N^{j} = \frac{{\frac{{t_{sleep}^{j} }}{2}}}{{(t_{preamble} + t_{eACK} )}} $$
(40)

If the energy consumption for sending one preamble packet form node i to j is denoted by \( E_{t\_preamble}^{ij} \), hence by using (40) the energy consumption for sending the preambles in one data sending session is \( N^{j} \times (E_{t\_preamble}^{ij} + E_{r\_eACK}^{ij} ) \). Therefore the total of energy consumed for sending one data packet to node j is:

$$ E_{t}^{ij} = N^{j} \times (E_{t\_preamble}^{ij} + E_{{r_{eACK} }}^{ij} ) + E_{t\_DATA}^{ij} + E_{r\_ACK} $$
(41)

For simplicity, we can consider \( t_{IL}^{j} \) as a constant period for all of the nodes. In fact \( t_{IL}^{j} \) should be long enough such that the receiver node captures at least one preamble between two consecutive preambles, i.e., \( t_{IL} \ge t_{preample} + t_{ACK} \). However it is clear that for the most energy efficiency, \( t_{IL} \) must be considered as the minimum value, that is \( t_{IL} = t_{preample} + t_{ACK} \).

In the case of sending data to the sink node, Eq. (15) can be exactly used. For the fair comparison between X-MAC and the proposed method, we consider that the RTS packet length is equal to the preamble length and likewise, the CTS packet length is equal to the early ACK packet length. In the case of receiving one data packet from transmitter node such as node k, the consumed energy is:

$$ E_{r\_DATA}^{ki} = E_{r\_preamble} + E_{t\_eACK}^{ik} + E_{r\_DATA} + E_{t\_ACK}^{ik} $$
(42)

Finally by considering \( P_{IL} \) as the average power consumption when the node is in the IL mode, initial node battery energy (\( E_{i} \)), outgoing and incoming data flow rates and using (41) and (42) the energy constraint in each node can be computed as follows:

$$ \mathop \sum \limits_{{j \in N_{i}^{R} + \left\{ {S_{i} } \right\}}} E_{t}^{ij} .r_{ij} + \mathop \sum \limits_{{k:i \in N_{i}^{R} }} E_{r\_DATA}^{ki} .r_{ki} + P_{IL} .dc_{i} \le E_{i} .T^{ - 1} , \forall i \in V $$
(43)

In (43), \( dc_{i} \) is equal to \( t_{IL} /(t_{IL} + t_{sleep}^{j} ) \) and T is the total network lifetime. Finally, the above energy constrains along with the flow sharing constrains represented in (1), form a non linear programming problem in which T is the objective function that should be maximized.

8 Performance evaluation

In this section, we illustrate the performance of the maximum lifetime routing problem under the three MAC protocols, including K-Persistent FRTS–RCTS, 1-Persistent FRTS–RCTS and X-MAC. To simulate the problems, a sensor network is considered which includes 10 sensor nodes distributed in a square area of 200 m by 200 m. It is also assumed that two sink nodes are located at two separate positions in the area, such that each sensor node is able to communicate with at least one of the sink nodes directly. Each sensor node has 3 V AA batteries with 2000 mAh capacity. All sensor nodes generate the same and fixed data rate. The parameter settings for the simulation are listed in Table 1. The selection of parameters related to energy consumption is similar to [28] based on Motes. To solve the problems, Lingo is employed, which is a very powerful optimization software for solving highly nonlinear mathematical programming problems. It is obvious that the network topology and so the problem structure strictly depend on the RTS flooding radius. Figure 5 presents the topology of the assumed network with RTS flooding radius of 80 m. In this figure, each solid line indicates either a route between two sensor nodes or a route between one sensor node and the sink node in the RTS flooding radius of the sensor node. Also, each dash line represents a direct route between a sensor node and its corresponding nearest sink node, which is not in its RTS flooding radius. In the first experiment, the maximum lifetime of the network is calculated by considering three mentioned MAC protocols under the different sensor node’s data generation rates. It is noted that, by replacing all \( K_{i} \) with one in (39), the problem is transformed into the maximum lifetime routing problem under 1-Persistent FRTS–RCTS MAC which is a nonlinear programming problem. Also in X-MAC protocol the RTS flooding radius is equal to the maximum radius in which a transmitter can communicate with its neighbors. Figure 6 shows the network lifetime versus data generation rate from 0.001 to 0.1 packets/s for fixed RTS flooding radius of 80 m. As expected, by increasing the data generation rate, the network lifetime will decrease in three MAC schemes. However, both K-Persistent FRTS–RCTS and X-MAC protocols, which act very close to each other, outperform 1-Persistent FRTS–RCTS by approximately as much as 19 and 17 % at the lowest traffic rate and 12 and 8 % at the highest traffic rate, respectively. The second experiment, investigates the effect of changing the RTS flooding radius or in other words changing the network topology on the maximum network lifetime under the three MAC techniques. Figure 7 presents the network lifetime when the RTS flooding radius (or in other words, the maximum communicational radius in X-MAC) is changed in the range of 60 to 120 m. As observed, the three protocols have the same behavior such that, first, the network lifetime lengthens by increasing the RTS flooding radius until it reaches its maximum level. This level is at the radius of 89 m for both 1-Persistent and K-Persistent FRTS–RCTS MAC protocols and is at the radius of 80 m for X-MAC. Then by further increasing the flooding radius, the network lifetime is reduced. The reason for this result can be explained by the fact that, by increasing the RTS flooding radius, the consumed energy for sending RTS packets will start to increase. On the other hand, less sensor nodes should to be awake to receive RTS packets and consequently their duty cycle will be reduced. Hence, this reduction overcomes the energy consumption due to increasing RTS flooding radius until it reaches a threshold level. After the threshold level, this procedure will take place conversely, because, when flooding radius surpasses the threshold level, the energy consumed from this increase will overcome the energy consumed due to nodes’ duty cycle. It is also observed that the performance of the K-Persistent FRTS–RCTS outperforms both 1-Persistent FRTS–RCTS and X-MAC in the wide range such that at the maximum level that is at the radius of 89 m, there is about 9 % improvement in proportion to 1-Persistent FRTS–RCTS MAC and 34 % improvement in proportion to X-MAC. In some other cases near the optimum state, for instance RTS flooding radius of 77 m, there is about 21 and 8 % enhancement in proportion to 1-Persistent FRTS–RCTS and X-MAC respectively. Also as seen, there are some non-optimum cases in which the network lifetime under the X-MAC approaches to the network lifetime under the K-Persistent FRTS–RCTS. On the other hand, K-Persistent FRTS–RCTS offers a great advantage. As shown, there is a wide range of about 20 m, from the 75 to 95 m in which changes in the network lifetime are very small in proportion to the maximum level, such that there is only up to 2.5 % decrease in comparison with the maximum level. This robustness is a significant benefit in some conditions when power fluctuations occur due to environmental changes or some other reasons. In contrast, specially in X-MAC, the network lifetime is very sensitive to network topology changes. In Fig. 8, the network topology for RTS flooding radius of 89 m is shown in which the best performance, in terms of maximum lifetime, is obtained. In Tables 2 and 3, the achieved duty cycle of sensor nodes and the resulting maximum number of attempts for flooding the RTS packet versus six various RTS flooding radii and data generation rate of 0.001 packets/s are presented respectively. Table 4 provides the achieved flow rate of data packets, for the RTS flooding radius of 89 m and data generation rate of 0.001 packets/s. Finally, according to the computation through the simulation, in the three MAC protocols, we realized that the remaining energy is zero in all of the network nodes and in all of the mentioned scenarios. However, as seen, this factor is just a necessary condition for maximizing the network lifetime. In other words, in addition to energy balancing, the network lifetime strictly depends on the utilized MAC protocol.

Table 1 Parameters used in simulation [18]
Full size table
Fig. 5
figure 5

Sensor network topology with RTS flooding radius of 80 m

Full size image
Fig. 6
figure 6

Network lifetime versus data generation rate

Full size image
Fig. 7
figure 7

Network lifetime versus RTS flooding radius

Full size image
Fig. 8
figure 8

Sensor network topology with RTS flooding radius of 89 m

Full size image
Table 2 Duty cycle of sensor nodes in K-Persistent FRTS–RCTS protocol
Full size table
Table 3 Maximum number of attempts for RTS packet flooding in K-Persistent FRTS–RCTS protocol
Full size table
Table 4 Data flow rates on all links with RTS flooding radius of 89 m \( (packet/{\text{s}}) \times 10^{ - 3} \) in K-Persistent FRTS–RCTS protocol
Full size table

9 Conclusion

In this paper, the issue of lifetime maximization is investigated in asynchronous duty-cycled wireless sensor networks (DC-WSNs). This problem is formulated based on a new energy balance base asynchronous MAC protocol named as K-Persistent FRTS–RCTS. It is shown that the problem is formulated as a mixed integer nonlinear programming (MINLP) problem under the proposed MAC protocol. To evaluate the performance of the proposed method, the same maximum lifetime routing problem was investigated under the well-known asynchronous X-MAC protocol. The results verify that the proposed MAC protocol outperforms its special case that is 1-Persistent FRTS–RCTS and X-MAC in terms of both network lifetime and topology changes; such that at the best network topology, there is about 9 % lifetime improvement in proportion to 1-Persistent FRTS–RCTS MAC and 34 % improvement in proportion to X-MAC. Also under the proposed MAC protocol, when the network topology is changed in the wide range, in proportion to the best network topology, the network lifetime is reduced very small in proportion to its maximum value, such that there is only up to 2.5 % decrease in comparison with the maximum level.