Affoua Thérèse

Alexandre Guitton
email: guitton@sancy.univ-bpclermont.fr

Michel Misson
email: misson@sancy.univ-bpclermont.fr

Asynchronous blind MAC protocol for wireless sensor networks

Keywords: MAC protocol, asynchronous duty-cycle, blind protocol, IEEE 802.15.4

In the past few years, energy conservation has been the main focus of researchers working on wireless sensor networks. One of the main technique to save energy is to deactivate periodically the radio module of sensor nodes: nodes alternate periods of activity and periods of inactivity, which is referred to as their duty-cycle. In this paper, we focus on asynchronous dutycycle mechanisms, as these mechanisms are usually simple, do not require time synchronization and support network changes. We propose an asynchronous MAC protocol based on blind rendez-vous and random wake-up. Our protocol is based on a modification of the IEEE 802.15.4 standard, where activities start at a random time within each activity cycle. Our simulations show that our protocol can achieve a good performance under various scenarios, for small duty cycles (ranging from 0.1% to 5%).

I. INTRODUCTION

Energy conservation is an important factor in wireless sensor networks (WSNs) dedicated to environmental monitoring such as volcanoes [START_REF] Geoffrey | Monitoring volcanic eruptions with a wireless sensor network[END_REF], fields [START_REF] Hart | Environmental sensor networks: A revolution in the Earth system science?[END_REF], and bridges [START_REF] Nagayamaa | Suspension bridge vibration measurement using multihop wireless sensor networks[END_REF]. Because the environment of deployment for these types of applications has no fixed infrastructure and is not always be accessible to recharge the sensors. As the radio module is the component of a sensor node that consumes the most energy, energy-efficient MAC protocols aim at deactivating the radio module as often as possible (thus, the node can neither send nor receive during these periods). Many MAC protocols of the literature use a sequence of periodic activity and inactivity periods, called duty cycle. These protocols can be classified into two main categories: synchronous and asynchronous MAC protocols.

In the synchronous MAC protocols (such as D-MAC [START_REF] Lu | An adaptive energyefficient and low-latency MAC for data gathering in sensor networks[END_REF], SEA-MAC [START_REF] Zhao | An energy-efficient self-adaptive duty cycle MAC protocol for traffic-dynamic wireless sensor networks[END_REF], and others [START_REF] Gallego | Energy efficient neighborhood maintenance and medium access with wake on idle[END_REF], [START_REF] Nordin | Effects and implications of beacon collisions in co-located IEEE 802.15.4 networks[END_REF]), the nodes share a common vision of time, obtained through synchronization. The IEEE 802.15.4 standard [START_REF]Part 15.4: Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (WPANs)[END_REF] in beacon-enabled mode is one of the main synchronous MAC protocol for WSNs. However, synchronous MAC protocols suffer from several drawbacks: the synchronization requires to exchange a large number of messages, is hard to achieve when the topology is large or dynamic, and is not suitable to low duty cycles.

In the asynchronous MAC protocols [START_REF] Carrano | Survey and taxonomy of duty cycling mechanisms in wireless sensor networks[END_REF], a mechanism is required to ensure that nodes can communicate. This mechanism can be initiated by the sender (using a preamble, such as in B-MAC [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF] or in [START_REF] Kenneth | O-MAC: a receiver centric power management protocol[END_REF], [START_REF] Tom | The MAC framework: redefining MAC protocols for wireless sensor networks[END_REF]) or by the receiver (such as in RI-MAC [START_REF] Sun | RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks[END_REF], PW-MAC [START_REF] Sun | PW-MAC: An energy-efficient predictive-wakeup MAC protocol for wireless sensor networks[END_REF], HKMAC [START_REF] Tang | Low-latency asynchronous dutycycle MAC protocol for burst traffic in wireless sensor networks[END_REF]). The nodes can also start their activities using an on-demand wake-up (such as in DW-MAC [START_REF] Sun | DW-MAC: a low latency, energy efficient demand-wakeup MAC protocol for wireless sensor networks[END_REF] or in [START_REF] Huy | Low-power wake-up radio for wireless sensor networks[END_REF]), a scheduled wake-up (as in [START_REF] Zheng | Asynchronous wakeup for ad hoc networks[END_REF], [START_REF] Carrano | Nested block designs: Flexible and efficient schedule-based asynchronous duty cycling[END_REF]) or a random wake-up (as in RAW [START_REF] Paruchuri | Random asynchronous wakeup protocol for sensor networks[END_REF] and [START_REF] Chau | Opportunistic forwarding in wireless networks with duty cycling[END_REF]).

In this paper, we propose an asynchronous MAC protocol, based on random wake-up for nodes. Nodes have a fixed duty cycle, but start their activities at random intervals (for a constant duration). Our protocol is blind in the sense that a node does not know the activity periods of its neighbors. When a node wakes up, it sends a beacon frame to notify its active neighbors that it can be used to forward data to the sink. Our protocol has the main following advantages: it is based on low control overhead, it is suitable to various scenarios (involving mobility or a large number of nodes) such as environmental monitoring, as nodes do not need to maintain any information about the topology (such as routing tables or neighborhood information), and does not require any synchronization between nodes. The delay required for a source to send data to the sink might be large, however, our protocol is able to operate on very low duty cycles (typically, around 1%).

The remainder of this work is organized as follows. Section II describes some MAC protocols of the literature. Section III presents our asynchronous, blind MAC protocol. Section IV gives our simulations results, performed in a large variety of scenarios. Finally, Section V summarizes and concludes our work.

II. RELATED WORKS ON ASYNCHRONOUS MAC

PROTOCOLS

In asynchronous MAC protocols, nodes are not synchronized. When a source node has to send a frame to a destination node, the source and the destination have to be both awake. To do this, an explicit mechanism is required, and various mechanisms are described in the following. Notice that generally, asynchronous MAC protocols yield large delays, but have a low energy consumption.

In sender-initiated MAC protocols, the source sends a long preamble before each frame, and receivers wake up periodically to sense the preamble. The B-MAC protocol [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF] is the main protocol of this category, and it has been improved in [START_REF] Kenneth | O-MAC: a receiver centric power management protocol[END_REF] and [START_REF] Tom | The MAC framework: redefining MAC protocols for wireless sensor networks[END_REF] by using short preambles. The drawbacks of these protocols are that energy consumption depends heavily on traffic production, and that the medium is often busy because of the preamble, rather than because of actual frame transmissions, which reduces the overall performance.

In receiver-initiated MAC protocols, a node that wakes up sends a beacon frame to inform its neighbors that it is now able to receive frames. A node has to receive a beacon frame before being allowed to send its data frame. This mechanism is used by RI-MAC [START_REF] Sun | RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks[END_REF], for instance, but it introduces a wasted period as the sender has to wait for the reception of the beacon. This overhead is reduced by PW-MAC [START_REF] Sun | PW-MAC: An energy-efficient predictive-wakeup MAC protocol for wireless sensor networks[END_REF], by having each node use a scheduled duty cycle (based on a pseudorandom generator), and by ensuring that each node knows the schedule of its neighbors, which introduces additional overhead. HKMAC [START_REF] Tang | Low-latency asynchronous dutycycle MAC protocol for burst traffic in wireless sensor networks[END_REF] uses an hybrid approach, where time is divided into random activation periods (similar as in RI-MAC) and scheduled activation periods (where activation periods are scheduled, which requires synchronization).

On-demand wake-up protocols assume that each sensor node possesses two radio modules: one is used for frame transmission, and the other is used to notify destination nodes of an incoming frame and consumes low energy. A node waits with the first radio module inactive but the second radio module active. When it receives the notification on a frame incoming on the second radio module, it activates the first radio module and is able to receive the frame. Examples of on-demand wake-up protocols are DW-MAC [START_REF] Sun | DW-MAC: a low latency, energy efficient demand-wakeup MAC protocol for wireless sensor networks[END_REF] and [START_REF] Huy | Low-power wake-up radio for wireless sensor networks[END_REF]. The main drawbacks of these protocols are the use of two radio modules (which increases the cost of the sensor nodes), as well as the energy consumption of the second radio module.

Scheduled wake-up protocols divide activity periods of neighboring nodes using repetitive patterns, such that the activity of neighboring nodes overlap eventually. The existing protocols [START_REF] Zheng | Asynchronous wakeup for ad hoc networks[END_REF], [START_REF] Carrano | Nested block designs: Flexible and efficient schedule-based asynchronous duty cycling[END_REF] differ on the way the patterns are built. These protocols have the advantage to be simple to implement, but the produced patterns might depend on the number of neighbors of each node.

Random wake-up protocols are protocols where the activation periods are chosen randomly. These protocols are suited for dense deployments, as they assume that when a node wakes up, it has another active neighbor to communicate with. Such protocols include RAW [START_REF] Paruchuri | Random asynchronous wakeup protocol for sensor networks[END_REF] and [START_REF] Chau | Opportunistic forwarding in wireless networks with duty cycling[END_REF].

III. PROPOSITION

In this section, we describe our proposition of an asynchronous, blind MAC protocol for WSNs. The protocol is receiver-initiated, and is based on a random wake-up mechanism (although it does not assume a dense deployment of nodes). It also operates according to a fixed duty cycle, that is, node activity does not depend on traffic.

A. Principle of operation

Each node knows the duration c of a cycle (although this duration might vary slightly from nodes to nodes, due to clock skews), and its activity duration a per cycle. During each cycle, the node decides randomly when the activity starts by waiting for a random delay in [0; c -a[ at the beginning of each cycle. With this mechanism, two nodes that are in range will eventually share a common activity period (even if their cycles do not start at the same time, or if the duration of the cycle is slightly different for each node).

Figure 1 shows this mechanism for three nodes n 1 , n 2 and n 3 , that are supposed to be in range, and with a duty cycle of 10% (that is, a = 0.1 × c). Note that to simplify the presentation, the cycles of each node are shown as if they were starting at the same time, which is not the case in practice. It can be seen that, on this example, any pair of node can eventually share a common activity period, even though this does not happen at each cycle. On this example, there is even a period where all three nodes share a common activity period. The delay in our mechanism can be high, because a source has to wait for a common period with the destination before sending a frame. This delay depends on parameters a and c. However, it is possible to reduce this delay by fragmenting the activity into f parts: instead of being active once for a duration of a per cycle, a node can become active f times per cycle, for a duration of a/f . In this way, the duty cycle remains a/c, but nodes share common activities more often (but for less time). Finding the optimal number of fragmentations f such that the delay is low but the duration of common activities is long enough to communicate is an issue of this mechanism, which will be discussed in Section IV.

Figure 2 shows this mechanism with a fragmentation of f = 2, again with a duty cycle of 10%. It can be noticed that each node has now two short activities per cycle, which results into more, but shorter, common activities. The energy savings of our protocol come from several features. First, as it is completely asynchronous, it is robust against clock drifts, which become relevant when nodes are inactive for large durations. For instance, if a clock drift of 30 ppm is assumed, the clock drift between two nodes can exceed 320 µs after only 4 s (which is the duration of a backoff slot in the slotted CSMA/CA mechanism of IEEE 802.15.4 in beacon-enabled mode). This means that a global synchronization has to be performed every 4 s, which generates a large overhead if nodes are active only 1% of these 4 s. Second, nodes are able to communicate with any neighbor, which improves the energy efficiency of the approach. For instance, if nodes have a duty cycle of 1%, the expected number of cycles for two nodes to share an activity is 100. However, if a node has more neighbors, the expected number of cycles for a node to communicate with a neighbor greatly decreases: it is 50 for two neighbors and 33 for three neighbors. This overhead becomes small as the number of neighbors increase, as shown in results given later in Section IV (see for instance the delivery rate as a function of the duty cycle for a varying number of next hops, as it is related to the number of common active periods).

B. Description of the MAC protocol

Our MAC protocol uses the unslotted CSMA/CA mechanism of the non beacon-enabled mode of the IEEE 802.15.4 standard, but uses a different activation mechanism (based on random wake-up). When a node wakes up, it transmits a beacon frame. To reduce the probability of a collision with this beacon frame, the beacon is sent using unslotted CSMA/CA, as shown on Figure 3. Because of the random backoffs of unslotted CSMA/CA, the beacon frame might be delayed, which reduces the duration of the active period that can be used to transmit frames. All data frames (which are sent in unicast) are required to be acknowledged. A data frame which is not acknowledged is retransmitted at most four times. Our protocol also differs from IEEE 802.15.4 by the fact that our protocol uses a receiver-initiated, gradient-based approach in order to identify active next-hops towards the sink. Algorithm 1 presents this approach. Each node stores a hop count (used as a gradient), which is the distance to the sink. When a node n wakes up, it sends a beacon frame to inform the neighbors that are further away from the sink of its potential availability as a next hop. A neighbor r that is further away from n can use n as a next hop if their common active duration is greater than a threshold (defined as twice the expected time to transmit a frame using unslotted CSMA/CA). Then, n waits to receive beacon frames from neighbors that are closer to the sink. When it receives such a beacon, it considers the neighbor as a potential next hop (for this active period only). Nodes having queues which are nearly filled are not available (but the node can still store frames produced locally).

The main advantages of our proposition can be summarized as: it does not require synchronization (and is robust to clock skews and drifts), nodes do not need to maintain information about the topology (which makes the protocol suitable in Algorithm 1 Our receiver-initiated, gradient-based approach to identify the next-hops of a node n.

if there is enough room in the queue size of n for five frames then n is available else n is not available end if n sends a beacon frame (with its current hop count, availability, and activity duration a) while node n is active do if a beacon frame is received from neighbor r then if hop count of r < current hop count of n then if node r is available then neighbor r becomes a potential next hop (for this active period) end if else if n is available and the remaining common active duration is greater than a threshold then node n sends a beacon message to inform r of its availability (with its current hop count, availability, and remaining active time) end if end if end if if there is another frame to send and there is enough remaining time to send the frame and receive the acknowledgment then n sends the frame to any potential next hop end if end while the case of mobility or varying propagation conditions), the protocol has a low control overhead, and the protocol can operate with low duty cycles (typically, around 1%).

IV. SIMULATION RESULTS

In order to evaluate the performance of our protocol, we performed simulations using the network simulator NS-2 [START_REF]Network simulator 2[END_REF], in three different scenarios (each scenario corresponding to a subsection). The transmit power is set to 0 dBm, and the propagation model is the shadowing model with a path loss of 3.0 and a standard deviation of 2 dBm. In the following, results are averaged over 100 repetitions, and each repetition lasts for 5000 seconds.

Unless specified otherwise, the activity cycle is 5 s, the duty cycle is 5%, the number of fragmentations f is 1, and one packet is generated at the source every 8 s.

A. Scenario 1: Evaluation of a single link

In this first scenario, we evaluate the performance of the MAC protocol between a source and a destination in range. We use this scenario to compute the delivery rate and the delay between the generation of packets at the source and their reception at the destination. Our objective is also to find the optimal value for the number of fragmentations f , which is an important parameter of our protocol.

The delivery rate is equal to 100% when f ∈ [2; 20], and is about 99.9% when f = 1 or when f ∈ [21; 25]. This can be explained as follows. When the number of fragmentation is high (f ≥ 21), the delivery rate decreases slightly. Indeed, in this case, a node is active during very short periods (of 12, 5 ms for f = 20 fragmentations), which yields common activities that, sometimes, do not last long enough for the source to detect the destination, perform the required backoffs, and actually send the frames to the neighbor. This shows that the value of f has to be limited. When the number of fragmentation is low (f = 1), the time required for the source to have a common activity with the destination is very large (it is larger than 25 s, that is 5 cycles). Frames accumulate in the queues of nodes, and some are eventually dropped.

Figure 4 shows the delay as a function of the number of fragmentations f . When the number of fragmentations is high (f ≥ 20), the delay is high due to the fact that nodes often meet for a duration which is too short to send frames. When the number of fragmentations is low (f ≤ 5), the delay is high due to the time required for the source to meet the destination. With these settings, the number of fragmentations f can be set 15, which correspond to both a large delivery rate and a small delay. Each node has an activity of about 17 ms, and 15 activities every 5 s.

B. Scenario 2: Evaluation of several possible next hops

In this second scenario, we evaluate the performance of our receiver-initiated, gradient-based approach. To do so, we consider a source in range of k intermediate nodes. Each of these intermediate nodes is in range of the destination. Thus, the source has k potential next hops in order to send the frame to the destination. The topology is shown on Figure 5, where s is the source and d is the destination. We refer to this topology as the diamond topology (with k intermediate nodes). Both delivery rates and delay are computed from source to destination (that is, they take into account the two links each frame has to follow). The delivery rate is equal to 100% when the number of next hops k varies between 2 and 6. When k = 1, the delivery rate is equal to about 99.8%. Indeed, when the number of next hops in the topology is low (k = 1), the delivery rate decreases. This is due to the fact that the source has few opportunities to send frames: frames fill node queues quickly, and get eventually dropped. Note that smaller delivery rates are achieved with periods smaller than 8 s. The small difference between the delivery rate for k = 1 and in the first scenario is due to the fact that in the second scenario with k = 1, there are two links, while there is only one link in the first scenario.

Figure 6 shows the delay as a function of the number of next hops k. As the number of possible next hops increases, the source has a larger probability to have a common activity with one of these next hops, which decreases the delay to send frames. This illustrates that when k is large, delivery rate is high and delay is low. In the following, we focus on small numbers of next hops. More specifically, we study the cases where k varies between 1 and 4, as we believe that these numbers of next hops are realistic for many WSNs. Figure 7 shows the delivery rate as a function of the duty cycle, for several number of possible next hops. When the duty cycle increases, the delivery rate increases. This is because the nodes are active more often and for longer durations. When the duty cycle is low (below 4%), nodes do not share common activities that are sufficiently long to exchange frames, which reduces dramatically the delivery rate. Figure 8 shows the delay as a function of the duty cycle, for several number of possible next hops. When the duty cycle is high (above 5%), the delay is low as nodes are active often and for long durations. When the duty cycle is low (below 4%), the delay is high. The sudden drop of delay for a duty cycle of 1% with k = 1 is due to the fact that many frames are dropped with these parameters, and frames experiencing long delays are more likely to be dropped.

C. Scenario 3: Evaluation of several possible next hops with very low duty cycles

In this third scenario, we evaluate the performance of our protocol when it is applied on very low duty cycles (between 0.1% and 1%). We consider larger periods, as WSNs with very low duty cycles are adapted to low traffic production.

Figure 9 shows the delivery rate as a function of the sending period, on a diamond topology with k = 3 possible next hops, and with a duty cycle of 1%. We varied the sending period from 8 s to 300 s. The results show that when the sending period is about 50s, the delivery rate reaches 100% for all number of fragmentations. Thus, it seems that the delivery rate is more impacted by the sending period than by the number of fragmentations. Figure 10 shows the delay as a function of the sending period, on a diamond topology with three next hops, and with a duty cycle of 1%. The delay is high for small sending periods (below 50 s), as the network becomes congested quickly with such small periods and duty cycles. The sudden drop in delay for a sending period of 8 s is due to the low delivery rate. Figure 11 shows the delivery rate as a function of the duty cycle, for very low duty cycles (between 0.1% and 1%). The results are obtained for a sending period of 300 s (that is, one packet is sent every 5 minutes), and for f = 1 and f = 2. This large period of traffic generation is intended to model a realistic application running over a WSN that has a very low duty cycle. It can be noticed that when the duty cycle exceeds 0.2%, the delivery ratio is high. Increasing the number of fragmentations for this small duty cycle has a detrimental impact on the delivery ratio, as the nodes share common activities that are too short to be further reduced by increasing f . From this figure, it can be seen that our protocol achieves a throughput of about 0.8 bps (with a payload of 30 bytes every 300 s, and with a duty cycle of 0.2%), for a two-hop network. To the best of our knowledge, there is no study on the performance of unsynchronized MAC protocols for very low duty cycles. Figure 12 shows the delay as a function of the duty cycle, for very low duty cycles (between 0.1% and 1%). The results are obtained for f = 1 and f = 2, and a sending period of 300 s. The delay is small for duty cycles above 0.3%, and the delay is high when the duration of the node activities is too small, as it forbids communications. The sudden drop of the delay for f = 2 and a duty cycle of 0.1% can be explained by the very important loss rate (as shown on Figure 11). V. CONCLUSION Asynchronous MAC protocols are suitable for WSN applications which require low duty cycles. In this paper, we propose an asynchronous, blind MAC protocol based on random wake-up, and using a gradient-based approach to identify possible next-hops. Our protocol randomizes the activities of each node within each global cycle. It can achieve reasonable delay by further fragmenting the activities, without impacting too much the delivery ratio. Our protocol has many advantages, as it supports very low duty cycles (of less than 1%) and is adapted to dynamic network (as it does not need to maintain information about the topology). Extensive simulations carried on NS-2 under various scenarios show that our protocol can achieve good performance in terms of delivery ratio and delay.

Figure 1 .

 1 Figure 1. An example of the activity of three nodes, with a duty cycle of 10%, and with nodes starting their activities randomly in each cycle.

n 1 n 2 n 3 Figure 2 .

 232 Figure 2. An example of the activity of three nodes, when the activity is fragmented into f = 2, and with a duty cycle of 10%.

Figure 3 .

 3 Figure 3. Zoom on the activity of a node during a cycle.

Figure 4 .

 4 Figure 4. Delay of data frames as a function of the number of fragmentations, on a link and with a duty cycle of 5%.

Figure 5 .

 5 Figure 5. Network topology (called the diamond topology) for the second and third scenarios, with k possible next hops for the source s.

Figure 6 .

 6 Figure 6. Delay of data frames as a function of the number of next hops, on a diamond topology.

3 Figure 7 .

 37 Figure 7. Delivery rate as a function of the duty cycle, for a varying number of possible next hops on a diamond topology.

3 Figure 8 .

 38 Figure 8. Delay of data frames as a function of the duty cycle, for a varying number of possible next hops on a diamond topology.

4 Figure 9 .

 49 Figure 9. Delivery rate as a function of the sending period, for three possible next hops on a diamond topology, with a duty cycle of 1%, and for a varying number of fragmentations.

4 Figure 10 .

 410 Figure 10. Delay of data frames as a function of the sending period, for three possible next hops on a diamond topology, with a duty cycle of 1%, and for a varying number of fragmentations.

2 Figure 11 .

 211 Figure 11. Delivery rate as a function of the duty cycle, for three next hops on a diamond topology, for a sending period of 300 s, and for a varying number of fragmentations.

Figure 12 .

 12 Figure 12. Delay of data frames as a function of the duty cycle, for three possible next hops on a diamond topology, for a sending period of 300 s, and for a varying number of fragmentations.


Affoua Thérèse

Alexandre Guitton
email: guitton@sancy.univ-bpclermont.fr

Michel Misson
email: misson@sancy.univ-bpclermont.fr

Study of Blind Rendez-vous in Low Power Wireless Sensor Networks

In wireless sensor networks (WSNs) applications such as environmental monitoring, it is essential to design protocols that are energy efficient and that are scalable. The main technique to reduce energy consumption is to use a duty-cycle, where nodes periodically go to sleep. However, the implementation of such a duty-cycle often requires nodes to be synchronized, which is difficult to achieve in a scalable manner. In this paper, we study the delay of blind rendez-vous for unsynchronized nodes, that is the delay required for two unsynchronized nodes to be active at the same time. There are several major advantages of blind rendez-vous: nodes do not need to share a prior knowledge, nodes do not need to be synchronized, and the support for network dynamicity (due to node mobility or failure) is simplified. We show through simulations that the delay to achieve a blind rendez-vous is reasonable in many scenarios.

I. INTRODUCTION

Wireless sensor networks (WSNs) are a promising solution for environmental monitoring due to their easy deployment, energy autonomy and low cost. Examples of such applications include the monitoring of volcanoes [START_REF] Geoffrey | Monitoring volcanic eruptions with a wireless sensor network[END_REF], of bird nests [START_REF] Robert | An analysis of a large scale habitat monitoring application[END_REF], of fields [START_REF] Hart | Environmental sensor networks: A revolution in the Earth system science?[END_REF], and of bridges [START_REF] Nagayamaa | Suspension bridge vibration measurement using multihop wireless sensor networks[END_REF]. These types of applications require the deployment of a large number of energy-efficient sensor nodes, and the auto-configuration of these nodes. Several MAC protocols have been proposed in this area to achieve a trade-off between energy consumption and delay.

The IEEE 802.15.4 [START_REF]Part 15.4: Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (WPANs)[END_REF] standard has been proposed for low-power, low-rate wireless personal area networks, which includes WSNs. The standard operates in two modes: the beacon-enabled mode and the non beacon-enabled mode. In the beacon-enabled mode, all nodes are synchronized: they wake up to communicate, and go back to sleep simultaneously to save energy. The main drawback of this mode is that the synchronization mechanism is costly in terms of energy and is not scalable. In the non beacon-enabled mode, nodes wake up when they have a packet of data to transmit and go into sleep mode after transmission. The main drawback of this mode is that it requires a large number of nodes to remain active to receive packets, which causes a significant energy consumption. Thus, IEEE 802.15.4 is not able to achieve a good trade-off between energy consumption and scalability, due to the overhead and complexity of the synchronization.

In this paper, we study the behaviour of IEEE 802.15.4 in beacon-enabled mode, when the requirement of synchronized beacons is removed. Each node is active according to its own random schedule. Blind rendez-vous occur when two nodes in the same vicinity are active at the same time, which occurs randomly. There are several major advantages to blind rendezvous: nodes do not need to share a prior knowledge of their schedule, they do not need to be synchronized, and the support for network dynamicity (due to node mobility or node failure) is simplified. During these rendez-vous, it can also be noted that contention for the medium is reduced, as some nodes are still sleeping. These advantages come at the cost of long delays before blind rendez-vous, which is the focus of this study.

The remainder of this paper is organized as follows. Section II describes the state of the art of related MAC protocols. Section III describes how to remove the requirement of synchronized beacons from IEEE 802.15.4 in beacon-enabled mode. Section IV presents our simulations results. Finally, Section V summarizes our work.

II. STATE OF THE ART

Most energy-efficient MAC protocols are based on a sequence of active and inactive periods, called duty-cycle. Nodes remain active for a given duration and go back to sleep for the rest of the time, which saves energy. These MAC protocols can be divided into synchronized and unsynchronized.

A. Synchronized MAC protocols

The IEEE 802.15.4 protocol [START_REF]Part 15.4: Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (WPANs)[END_REF] in beacon-enabled mode is one of the most common low-power MAC protocols for WSNs. Each full-function device (FFD) sends a beacon with a period called BI (for beacon interval). When a reducedfunction device (RFD) receives a beacon, it starts its activity period for a duration called SD (for superframe duration). The ratio SD/BI defines the duty-cycle of the protocol. Note that all RFDs are in range of a FFD, and are synchronized by the beacon. All nodes share the same activity period. The medium is accessed using slotted CSMA/CA (carrier-sense multiple access with collision avoidance).

In D-MAC [START_REF] Lu | An adaptive energyefficient and low-latency MAC for data gathering in sensor networks[END_REF], nodes are synchronized according to their depth on a collection tree. When nodes of depth d are in a transmission slot, nodes of depth d -1 are in a reception slot. The synchronization is also performed using the tree topology. In S-MAC [START_REF] Ye | An energy-efficient MAC protocol for wireless sensor networks[END_REF] and [START_REF] Ganeriwal | Estimating clock uncertainty for efficient duty-cycling in sensor networks[END_REF], each node propagates periodically its time schedule to its neighbors. Thus, nodes can determine when to be active or inactive, depending on whether they have to communicate with a given neighbor or not.

In Z-MAC [START_REF] Rhee | A hybrid MAC for wireless sensor networks[END_REF], a TDMA (time-division multiple access) approach is used. A slot is assigned to all nodes in the configuration phase, and is used in case of high contention. In G-MAC [START_REF] Brownfield | Wireless sensor network denial of sleep attack[END_REF], time is divided into three periods: a collection period (where the medium is accessed by CSMA/CA), a period of traffic indication (whose role is to maintain synchronization between nodes) and a distribution period (where the medium is accessed by TDMA). All nodes have simultaneous activities during the first and the second periods, and non-simultaneous activities during the third period. In SEA-MAC [START_REF] Zhao | An energy-efficient self-adaptive duty cycle MAC protocol for traffic-dynamic wireless sensor networks[END_REF], the authors propose a synchronous duty-cycle MAC protocol which allows nodes to adjust their duty-cycle according to the dynamic traffic load.

B. Unsynchronized MAC protocols

The IEEE 802.15.4 protocol in non beacon-enabled mode allows nodes to communicate without requiring a synchronization mechanism. When an RFD has to send data to an FFD, it simply wakes up and transmits the data. This requires, however, the FFDs to be active all the time, which consumes energy. The medium is accessed using the nonslotted CSMA/CA algorithm, a slightly modified version of slotted CSMA/CA. Although the non beacon-enabled mode allows nodes to have non-simultaneous activities, it cannot be used in practice due to its large energy requirements.

In B-MAC [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF], nodes are not synchronized but wake up periodically for a short duration. When a sender node has to communicate to a receiver node, the sender node sends a long preamble before its frame (which makes B-MAC a senderinitiated protocol). When the receiver wakes up, it detects the preamble and stays active until the end of the preamble and the reception of the frame. While this approach yields good performance, nodes have to stay awake frequently in order to receive frames, and therefore the energy consumption of B-MAC relies heavily on the traffic.

In X-MAC [START_REF] Buettner | X-MAC: A short preamble MAC protocol for duty-cycled wireless sensor networks[END_REF] and [START_REF] Tom | The MAC framework: redefining mac protocols for wireless sensor networks[END_REF], the same approach as B-MAC is used. Instead of using a long preamble, each sender sends several small frames, which allows the receiver to go back to sleep as soon as it has received the frame, rather than having to wait for the preamble. RI-MAC [START_REF] Sun | RI-MAC: a receiver-initiated asynchronous duty cycle MAC protocol for dynamic traffic loads in wireless sensor networks[END_REF], ABD [START_REF] Yanjun | ADB: an efficient multihop broadcast protocol based on asynchronous dutycycling in wireless sensor networks[END_REF], PW-MAC [START_REF] Sun | PW-MAC: An energy-efficient predictive-wakeup MAC protocol for wireless sensor networks[END_REF], EM-MAC [START_REF] Lei | EM-MAC: A dynamic multichannel energy-efficient MAC protocol for wireless sensor networks[END_REF] and WiseMAC [START_REF] El-Hoiydil | WiseMAC: An ultra low power MAC protocol for multi-hop wireless sensor networks[END_REF] focus on a receiver-initiated approach. In RI-MAC, the receiver initiates the communication by using a low power probing, where the receiver sends a beacon to express its ability to receive data packets. RI-MAC reduces channel occupation (as it does not require nodes to send preambles), but generates high energy consumption. The ABD protocol provides a broadcast service in RI-MAC protocol. PW-MAC reduces the listening time of the sender in RI-MAC, by having each node compute its awakening times according to a pseudo-random number generator rather than according to a fixed schedule. The drawback of PW-MAC is that sending the beacons before packet transmission generates overhead, and introduces a delay when listening the channel. In EM-MAC [START_REF] Lei | EM-MAC: A dynamic multichannel energy-efficient MAC protocol for wireless sensor networks[END_REF], a node computes its awakening schedule using a pseudo-random generator. A node independently decides its wake-up time and exchange channel. The wake-up channel is not necessarily the same as the channel for exchanging data. In EM-MAC, the sender also knows the parameters of the pseudo-random generator and receiver wake-up channel. EM-MAC inherits the shortcomings of PW-MAC, and more, in EM-MAC, each node invokes twice a pseudo-random generator, hence, generating an additional overhead. In WiseMAC, preambles are used, but their lengths is reduced by allowing the sender to wake up before the beginning of the activity period of the receiver.

C. Blind rendez-vous

Blind rendez-vous refer to the ability of a node to be active at the same time as another node, and to detect it without prior knowledge. In [START_REF] Misic | Properties of blind rendezvous in channel hopping cognitive piconets[END_REF], the authors show that only few MAC protocols operate using blind rendez-vous. The authors study an algorithm where rendez-vous is detected by having a node scan the channel to detect the activity of the other node. Once a rendez-vous occurs, the node that has detected it stays on the same channel. In this paper, we have different assumptions: the rendez-vous has to be detected each time it occurs, and we generate explicit messages instead of detecting the activity of nodes (which is supposed to be limited).

III. IMPLEMENTATION OF BLIND RENDEZ-VOUS

In this section, we describe how IEEE 802.15.4 in beaconenabled mode can be changed to work without requiring a beacon synchronization. In this new version, each node decides of its own schedule randomly and independently, at each cycle.

A. Description of the modification of IEEE 802.15.4

In the MAC layer of the beacon-enabled mode of IEEE 802.15.4 (in its original version), nodes are synchronized by the beacons. The activities of nodes are simultaneous, as shown on Fig. 1 for a duty-cycle of 25%. We denote this approach A sp , where the nodes are synchronized and their activities are periodically repeated at the same time. In this approach, nodes meet systematically in each cycle. However, this approach causes high contention because multiple nodes attempt to access the channel at the same time, and requires synchronization. If the synchronization procedure of the beacon-enabled mode of IEEE 802.15.4 is removed, it is possible to consider an approach where activities are periodic, but unsynchronized. We denote this approach A up . The start time of the activity of each node is independent, as shown in Fig. 2. This approach has the advantage to reduce the contention for the channel, because few nodes are active at the same time, and also does not require synchronization. However, the major drawback of A up is the high probability that some pairs of nodes never communicate directly (see pairs (n 1 , n 3 ) and (n 2 , n 3 ) on Fig. 2).

n 1 n 2 n 3
Note that in Fig. 2, the time slots for each node are still synchronized. In practice, this is not required. Each time two nodes share an activity period, one time slot is generally lost at the beginning of the common activity period, and another at the end of the common activity period, due to synchronization issues. However, as these time slots are expected to be very short (they can have the same length as a backoff period, which is 320 µs, time base of the IEEE 802.15.4 standard) with respect to the much longer common activity duration, this phenomenon can be neglected. The mechanism we study shifts randomly the starting time of the activity of each node, at each cycle. We denote this approach A ua , as activities are unsynchronized and also aperiodic. A ua is shown on Fig. 3. This approach has many advantages: any pair of nodes will eventually be able to have a rendez-vous, contention is low (as the average number of nodes active at the same time is low), and no synchronization is required. Note that broadcasting is also possible, as the probability that all nodes are active simultaneously is not null (even if it is low). However, the fact that few nodes are generally active simultaneously reduces the contention for the medium and the probability of collisions, which in turn reduces the probability to miss a detection. The main drawback of our approach is that it can yield long delays before a given pair of nodes share a common activity period.

n 1 n 2 n 3

B. Technical details on the implementation

The mechanism can be implemented easily from IEEE 802.15.4 as follows. Each node knows its duty-cycle e and the cycle duration b. Each node schedules its activities according to its own schedule, and each activity period lasts for a duration s = e.b. The start of the activity duration is randomly chosen in the interval [0; bs[. When the activity duration starts, the node wakes up, sends a beacon message, and waits to detect neighbors before sending data messages, as shown on Fig. 4. Neighbors are detected (and thus, rendezvous are generated) when the node receives a beacon message from another node. Beacon and data messages are sent using unslotted CSMA/CA.

To detect a rendez-vous, a minimum duration (called t in the following) is required. Let us consider two nodes, n 1 and n 2 , and let us assume that n 1 is active before n 2 (for a given cycle). For n 1 to detect the rendez-vous with n 2 , n 1 has to wait for the beginning of the activity of n 2 , and then for the reception of the beacon of n 2 (which is delayed as beacons are sent using unslotted CSMA/CA). Thus, time t includes the average time required to send one packet (i.e., the beacon) in unslotted CSMA/CA (assuming that the contention is relatively low). A study conducted by Niek et al. [START_REF] Niek | Throughput and delay analysis of unslotted IEEE 802.15.4[END_REF] showed that this time varies between 2 ms and 6 ms, in the case of a perfect channel. To take into consideration lossy channels and beacon retransmissions, we set the value of t to 15.36 ms. This value corresponds to the minimum duration of a superframe in IEEE 802.15.4, and is expected to be sufficient to exchange a few frames among nodes, even if several nodes are contending for the medium. The impact of t on the network performance is left for future work. We assume that as soon as two nodes can share a common activity period of length at least t, one of them can detect the rendez-vous. An analytical evaluation of the delay has been proposed in [START_REF] Aby | MAC mechanism for a scalable wireless sensor network using independent duty cycles[END_REF], in a slightly different case where each node initially chooses a random value for its cycle duration, computes its duty-cycle accordingly, and activates its radiomodule periodically afterwards. The main differences with this paper are the following: in this paper, we assume that all nodes have the same cycle duration b and activate their radio-module randomly within each cycle duration, and our delay evaluation is more accurate as it takes into account the contention delay (and not only the delay before a common activity).

C. Reduction of the delay to detect a rendez-vous

The delay required to detect a rendez-vous is the main focus of this study, as it is the main issue of the mechanism. To reduce this delay, the activity can be fragmented: instead of having one activity of duration s = e.b randomly located every b time units (where e is the duty-cycle), nodes can have several activities, each of duration e.b/f , randomly located every b/f time units. Note that the duty-cycle in the second case is (e.b/f )/(b/f ) = e, as it is in the first case. Figure 5 shows an example with three nodes, with b = 8, e = 25% and f = 2. Note that each activity lasts for e.b/f = 1 time unit, and is randomly located once every b/f = 4 time units.

IV. PERFORMANCE EVALUATION

We conducted simulations in order to evaluate the delay before blind rendez-vous, for several scenarios. The simulation settings are the following. Backoff slots of 320 µs are used, as in the IEEE 802.15.4 standard. For the sake of simplicity, backoff slots are synchronized: to deal with unsynchronized backoffs, an additional delay of 320 µs should be added to all results (but this value is negligeable with respects to the total delay we obtain). Time for each node is expressed using a large array a: a n [i] is equal to 1 if node n is active at time-slot i, and a n [i] is equal to 0 otherwise. Nodes n 1 and n 2 share a common activity at time-slot i if a n1 [i] = a n2 [i] = 1. To account for lossy channel, we assume that the rendez-vous can be detected if the nodes share an activity of t =15.36 ms, that is 48 backoff slots. Results are averaged over 300 repetitions, and each repetition is a sequence of cycles that lasts for 1 hour. We vary the duration of the cycle b, as well as e.

In all the simulations, the evaluated delay is the time before a common activity of two nodes. This delay does not take into account the medium access delay required for a node to transmit a beacon, nor the probability that the beacon can be missed by an active receiver due to the channel. We expect the medium access delay to be lower than t = 15.36 ms, as our mechanism yields a low contention, and thus we consider that the medium access delay can be neglected. We also consider that the two nodes are in range of each other, and that channel losses due to the propagation conditions are low. Losses due to collisions should also be limited, as the probability that many nodes are active at the same time is low.

Figure 6 shows the average delay for two nodes to detect a rendez-vous for at least t = 15.36 ms, as a function of the duration of the activity cycle b, for our protocol. Three dutycycles are shown: 5%, 15% and 25%. As expected, the delay increases when b increases: when the cycles are long, it takes more time for nodes to share a common activity. Also, the delay increases when s decreases: when the duty-cycle is low, common activity occurs less often, which in turn increases the delay. For a cycle of 60 s and a duty-cycle of 25%, nodes wait on average less than 60 s. For a cycle of 10 s and a duty-cycle of 5%, nodes wait on average about 80 s. When the duty-cycle is 15% or more, our approach achieves small delays: it takes less than two global cycles for two nodes to achieve a rendez-vous. Figure 7 shows the impact of the fragmentation of the activity on the average delay, as a function of the duration of the cycle b, for a duty-cycle of 5%. For a cycle of b = 60 s, the average delay is more than 350 s when there is no fragmentation (f = 1), and is only 120 s when the activity is fragmented four times (f = 4). With the fragmentation of the activity, the delay has been significantly reduced. This result shows that without changing the duty cycle of nodes, it is possible to reduce the delay for blind rendez-vous. Figure 8 shows the impact of the fragmentation of the activity on the average delay, as a function of the duration of the cycle b, for a duty-cycle of 25% (rather than 5% for Figure 7). Again, the reduction of the delay is very important as f increases. For a cycle of b = 60 s, the delay can be reduced from about 57 s to 14 s, which is about a quarter of the whole activity cycle. Even if a delay of 14 s seems to be large, it is important to remember that nodes are active only 25% of the time, and that nodes experience this delay only when they have packets to send, which is expected to be rare.

It is not possible to fragment the activity too many times. Indeed, the more the activity is fragmented, the shortest duration nodes have in common. When f becomes too large, the common duration becomes too small, and nodes cannot detect rendez-vous anymore. We choose f so that it achieves a good tradeoff between the delay (which reduces when f increases) and the common activity duration (which decreases when f increases, as shown on Figure 9). We propose to

V. CONCLUSION

The IEEE 802.15.4 protocol in beacon-enabled mode is a good candidate for WSNs, as it aims at reducing the energy consumption of nodes. However, the synchronization required for IEEE 802.15.4 is costly and difficult, and raises energy consumption and scalability issues. Thus, we propose to remove this requirement by allowing nodes to have their activities start at a random time within each global cycle. We explain how nodes can achieve blind rendez-vous, and we compute how long nodes have to wait (on average) before these rendez-vous. Even when the duty-cycle is low (such as 5%), the duration before rendez-vous can be kept small (in this case, the average is always at most twice the duration of a cycle). The advantages of blind rendez-vous are that contention is reduced (as in general, only few nodes are active simultaneously), and network dynamicity can be supported easily. Our future work consists in determining the optimal cycle duration (i.e., the optimal value of the fragmentation of the cycle) that ensures that rendez-vous can be detected, in realistic conditions (such as with lossy links and congestion).

Figure 1 .

 1 Figure 1. Activity of three nodes (in time) when the duty-cycle is 25%, and all activities are synchronized and periodic.

Figure 2 .

 2 Figure 2. Activity of three nodes (in time) when the duty-cycle is 25%, when nodes start their activities independently but in a periodic manner.

n 1 n 2 n 3 Figure 3 .

 233 Figure 3. Activity of three nodes (in time) when the duty-cycle is 25%, when nodes start their activities independently and randomly in each cycle.

Figure 4 .

 4 Figure 4. Zoom on the activity of a node.

n 1 n 2 n 3 Figure 5 .

 235 Figure 5. Activity fragmentation into f = 2, with a duty-cycle of 25%.

Figure 6 .

 6 Figure 6. Average delay for two nodes to detect a rendez-vous.

  b (in seconds) Average delay (in seconds) Without fragmentation of s s fragmented twice per b s fragmented 4 times per b

Figure 7 .

 7 Figure 7. Impact of activity fragmentation when the duty-cycle is 5%.

Figure 8 .

 8 Figure 8. Impact of activity fragmentation when the duty-cycle is 25%.

Figure 9 .

 9 Figure 9. Node activity when s is fragmented four times per b (e = 25%).

ACKNOWLEDGMENT

This is Laboratory of Excellence ClerVolc contribution number 89.


Alessio Zappone

Emil Björnson

Luca Sanguinetti

Eduard Jorswieck

A FRAMEWORK FOR GLOBALLY OPTIMAL ENERGY-EFFICIENT RESOURCE ALLOCATION IN WIRELESS NETWORKS

Keywords: Energy Efficiency, Fractional programming, Monotonic optimization, Resource allocation, Power control

State-of-the-art algorithms for energy-efficient resource allocation in wireless networks are based on fractional programming theory, and are able to find the global maximum of the system energy efficiency only in noise-limited scenarios. In interference-limited scenarios, several sub-optimal solutions have been proposed, but an efficient framework to globally maximize energy-efficient metrics is still lacking. The goal of this work is to fill this gap, which will be achieved by merging fractional programming theory with monotonic optimization theory. The resulting optimization framework is useful for at least two main reasons. First, it sheds light on the ultimate energy-efficient performance of wireless networks. Second, it provides the means to benchmark the energy efficiency of practical, but sub-optimal, solutions.

INTRODUCTION AND RELATION TO PRIOR WORK

The percentage of the total CO2-equivalent emissions due to information and communications technologies (ICT) is estimated to be 5% [START_REF] Fehske | The Global Footprint of Mobile Communications-The Ecological and Economic Perspective[END_REF]. While this may seem a small percentage, it will rapidly increase, due to the advent of 5G networks and the associated exponential growth of connected devices. Credited sources foresee the number of connected devices to reach 50 billions by 2020, with a data traffic increase of a factor 1000 [START_REF] White | More than 50 billion connected devices[END_REF]. If no countermeasures are taken, the energy demand to operate and provide such massive data rates to this massive number of devices will become unmanageable, and the resulting greenhouse gas emissions and electromagnetic pollution will exceed safety thresholds. While restricting the global ICT usage is unrealistic, a promising answer to this issue lies in optimizing the energy efficiency (EE) of ICT systems, defined as the ratio between the data rate and associated energy consumption. Given the fractional nature of the EE, the main mathematical framework adopted for EE optimization is fractional programming theory [START_REF] Zappone | Energy efficiency in wireless networks via fractional programming theory[END_REF]. However, while fractional programming algorithms exhibit polynomial complexity in noise-limited systems [START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF], their complexity becomes prohibitive in interference-limited systems [START_REF] Zappone | Energy efficiency in wireless networks via fractional programming theory[END_REF]. A common way to circumvent this problem is to only consider suboptimal orthogonal or semi-orthogonal transmission schemes as well as interference cancellation techniques, to fall back into the noiselimited case. In [START_REF] Ng | Energy-efficient resource allocation in multi-cell OFDMA systems with limited backhaul capacity[END_REF][START_REF] Xu | Energy-efficient resource allocation for heterogeneous services in OFDMA downlink networks: Systematic perspective[END_REF] multi-carrier networks are considered, and the global energy efficiency (GEE) of the system (defined as the ratio between the sum achievable rate and the total consumed power) is optimized using orthogonal or semi-orthogonal subcarrier allocation schemes. In [START_REF] Xu | Energy efficiency optimization for MIMO broadcast channels[END_REF], the authors consider a multiple-antenna system and aim at maximizing the GEE when non-linear interference cancellation techniques are used. However, orthogonal interference suppression schemes inevitably result in a poor resource reutilization in multi-link networks and are thus not reasonable in large networks. Moreover, practical impairments like channel estimation errors can also break the orthogonality in many cases. Alternative approaches employ suboptimal procedures, typically based on the use of alternating optimization techniques, as in [START_REF] Du | Distributed energyefficient power optimization for CoMP systems with max-min fairness[END_REF], where the minimum of the individual EEs is maximized and in [START_REF] He | Coordinated beamforming for energy efficient transmission in multicell multiuser systems[END_REF][START_REF] He | Coordinated multicell multiuser precoding for maximizing weighted sum energy efficiency[END_REF] where both the maximization of GEE and of the sum of the individual EEs are considered. In [START_REF] Venturino | Energyefficient scheduling and power allocation in downlink OFDMA networks with base station coordination[END_REF][START_REF] Zappone | Energy efficiency and interference neutralization in two-hop MIMO interference channels[END_REF] fractional programming is used in conjunction with sequential convex optimization to develop an optimization framework able to determine local optima of the system EE with polynomial complexity.

The main issue with all the cited works is that, although all proposed solutions exhibit an affordable complexity, they are not guaranteed to achieve global optimality. Indeed, a framework to obtain the global solution of EE maximization problems is currently lacking. This prevents one from gaining insight on the ultimate energyefficient performance of wireless networks and from benchmarking the performance of suboptimal methods against the optimal solution. This work aims at filling these gaps by developing an optimization framework to globally maximize the EE in wireless networks. This will be done by merging fractional programming theory with monotonic optimization, which is a theory that provides algorithms to globally solve certain classes of non-convex problems [START_REF] Tuy | Monotonic optimization[END_REF][START_REF] Tuy | Monotonic optimization: Branch and cut methods[END_REF]. Monotonic optimization has been previously used to globally solve power control and scheduling problems [START_REF] Qian | S-MAPEL: Monotonic optimization for non-convex joint power control and scheduling problems[END_REF], rate maximization problems [START_REF] Björnson | Robust monotonic optimization framework for multicell MISO systems[END_REF], and beamforming problems [START_REF] Utschick | Monotonic optimization framework for coordinated beamforming in multicell networks[END_REF]. Recent surveys of monotonic optimization applied to wireless communications are [START_REF] Björnson | Optimal resource allocation in coordinated multi-cell systems[END_REF][START_REF] Zhang | Monotonic optimization in communication and networking systems[END_REF].

SYSTEM MODEL AND PROBLEM STATEMENT

Consider a wireless network wherein K mutually interfering links are active over a communication bandwidth of B Hz. Each link includes a single-antenna transmitter node and a receiver node (possibly equipped with multiple antennas). Denoting by p the K × 1 vector collecting all users' transmit powers, we assume the k-th link's signal to interference plus noise ratio (SINR) γ k (p) takes on the following general form:

γ k (p) = α k p k σ 2 + φ k p k + K i=1,i =k piβ i,k . (1)
The coefficient σ 2 is the thermal noise power at the receiver (over the bandwidth B), α k is the k-th user's channel power gain, while {β i,k } are multi-user interference coefficients, depending on the other users' channel coefficients and on global system parameters. The coefficient φ k models a self-interference term, proportional to the useful power, which arises in several relevant instances of communication systems [START_REF] Zappone | Energy-efficient power control: A look at 5G wireless technologies[END_REF], such as hardware-impaired networks, receivers with imperfect CSI estimation, and relay-assisted communications. By setting φ k = 0, (1) reduces to the usual SINR expression in interference networks. Given (1), the k-th user's achievable rate is expressed as

B log 2 (1 + γ k (p)) = q + k (p) -q - k (p), with q + k (p) = B log 2 (σ 2 + (α k + φ k )p k + K i=1,i =k piβ i,k ) and q - k (p) = B log 2 (σ 2 + φ k p k + K i=1,i =k piβ i,k
). The EE (measured in bit/Joule) of link k is defined as the ratio of the achievable rate and the total consumed power (neglecting the functional dependence of γ k from p for notational simplicity):

EE k (p) = B log 2 (1 + γ k ) µ k p k + Ψ k (2)
wherein µ k ≥ 1 is the inverse of the power amplifier efficiency of node k and Ψ k is the circuit power required to operate link k accounting for the dissipation in analog hardware, digital signal processing, backhaul signaling, and other overhead costs (such as cooling and power supply losses) [START_REF] Björnson | Optimal design of energy-efficient multi-user MIMO systems: Is massive MIMO the answer?[END_REF]. Clearly, ( 2) is a link-centric (or user-centric) performance metric. A network-centric definition of EE requires to combine the individual energy efficiencies of the different links. Although different approaches have been proposed, a single definition that unarguably best represents the EE of the whole network is not available, since the different EEs are typically conflicting objectives [START_REF] Zappone | Energy efficiency in wireless networks via fractional programming theory[END_REF][START_REF] Björnson | Multi-objective signal processing optimization: The way to balance conflicting metrics in 5G systems[END_REF]. Two well-established metrics to measure the network EE are the GEE and the weighted minimum energy efficiency (WMEE), defined as [START_REF] Zappone | Energy efficiency in wireless networks via fractional programming theory[END_REF][START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF].

GEE(p) = K k=1 B log 2 (1 + γ k ) K k=1 µ k p k + Ψ k (3) WMEE(p) = min k=1,...,K w k B log 2 (1 + γ k ) µ k p k + Ψ k . (4)
The GEE has the strong physical meaning of network benefit-cost ratio, in terms of global amount of reliably transmitted data and global amount of consumed energy. However, it does not depend on the individual EEs, and so does not allow to tune the EE of the individual links according to specific needs. Instead, the WMEE is more connected to a multi-objective optimization perspective [START_REF] Björnson | Multi-objective signal processing optimization: The way to balance conflicting metrics in 5G systems[END_REF], in which the individual EEs are the objectives to maximize. By varying the weights in (4) it is possible to prioritize the links that require a higher EE and to describe the complete energy-efficient Pareto boundary of the system. 1 The goal of this work is to find the global solution of the following optimization program:

max p u(p) (5a) s.t. p k ∈ [0, P max,k ] , B log 2 (1 + γ k ) ≥ R min,k , (5b)
wherein the objective u(p) can be either the GEE or the WMEE, P max,k and R min,k are the maximum feasible transmit power and minimum acceptable rate for link k, for all k = 1, . . . , K.

1 For the considered system, the Pareto-boundary is the outer boundary of the K-dimensional region containing all feasible energy-efficient operating points, i.e. all feasible K × 1 vectors [EE 1 (p), . . . , EE k (p)].

PROBLEM SOLUTION

As far as both GEE and WMEE maximization are concerned, the optimization problem in ( 5) is a fractional program. However, fractional programming algorithms exhibit a guaranteed polynomial complexity only if the numerator and denominator of the fraction to maximize are respectively concave and convex in the optimization variables, and if the constraints are also convex [START_REF] Zappone | Energy efficiency in wireless networks via fractional programming theory[END_REF]. Unfortunately, this requirement is not fulfilled in interference-limited networks, because the presence of the functions q - k (p) (which are non-zero whenever multi-user interference is present) makes the numerators of the individual EEs non-concave in p. For these scenarios, fractional programs are in general NP-hard, and the conventional approach is to resort to global optimization algorithms. However, these methods operate by performing an exhaustive search of the whole feasible set, with a prohibitive computational complexity, even for small problem instances, and a convergence that is only guaranteed if the functions have a limited variability (e.g. Lipschitz continuity). Instead, a more recent optimization framework with the potential to reduce such computational burden and to ensure a guaranteed convergence is monotonic optimization [START_REF] Tuy | Monotonic optimization[END_REF]. Roughly speaking, the basic idea is that if the objective to maximize is increasing in all optimization variables, then it is not necessary to explore the complete feasible set, but only its outer boundary.

The main difficulty in applying this framework for EE maximization is that, unlike what happens for achievable rates, both the GEE and the WMEE are not monotonic in the transmit powers. However, this difficulty can be overcome by an interplay of fractional programming and monotonic optimization. We start by providing some necessary preliminaries on fractional programming and monotonic optimization in Sections 3.1 and 3.2, respectively. Next, we develop the proposed optimization framework in Sections 3.3 and 3.4, where the global maximizations of the GEE and WMEE are carried out, respectively.

Fractional programming

For a more comprehensive overview of fractional programming applied to EE maximization in wireless networks, the interested reader is referred to [START_REF] Zappone | Energy efficiency in wireless networks via fractional programming theory[END_REF]. Definition 1 (Generalized fractional program) Let D ⊆ R N and consider the functions f k : D → R and g k : D → R++, with k = 1, . . . , K. A generalized fractional program is the optimization problem defined as

max x min k=1,...,K f k (x) g k (x) s.t. x ∈ D. (6)
If K = 1, then the above problem reduces to the so-called singleratio fractional program:

max x f1(x) g1(x) s.t. x ∈ D. (7)
Since the objective function in ( 6) is in general not concave, standard convex optimization algorithms are not guaranteed to solve [START_REF] Xu | Energy-efficient resource allocation for heterogeneous services in OFDMA downlink networks: Systematic perspective[END_REF] and specific algorithms are required. Towards this end, we have the following key result. Proposition 1 [START_REF] Jagannathan | On some pproperties of programming problems in parametric form pertaining to fractional programming[END_REF][START_REF] Dinkelbach | On nonlinear fractional programming[END_REF]. A vector x ∈ D solves (6) if and only if

x = arg max x∈D min k=1,...,K f k (x) -λ g k (x) (8)
with λ being the unique zero of the auxiliary function F (λ):

F (λ) = max x∈D min k=1,...,K {f k (x) -λg k (x)} . (9)
This result allows solving (6) by finding the unique zero of F (λ).

To this end, the most widely used algorithm is the (Generalized, if K > 1) Dinkelbach's algorithm [START_REF] Dinkelbach | On nonlinear fractional programming[END_REF][START_REF] Crouzeix | Algorithms for generalized fractional programming[END_REF], reported in Algorithm 1.

Algorithm 1 Generalized Dinkelbach's algorithm Initialize λ0 with F (λ0) ≥ 0, j = 0; repeat Solve the problem:

x j = arg max x∈D min k=1,...,K f k (x) -λjg k (x) ; λj+1 = min k=1,...,K f k (x j ) g k (x j ) ; j = j + 1; until F (λj) > ε
It can be shown that the update rule for λ follows Newton's method applied to the function F (λ). Hence, Algorithm 1 exhibits a superlinear convergence rate, but converges to the global optimum of the corresponding instance of fractional problem only provided that (8) can be globally solved at each iteration. In general, if ( 8) is not a convex problem, this calls for global optimization algorithms that perform an exhaustive search over the whole feasible set, with unmanageable computational complexity and with a convergence that is only guaranteed if the functions have a limited variability (e.g. Lipschitz continuity).

Monotonic optimization

Monotonic optimization provides a framework to globally solve problems that exhibit monotonicity or hidden monotonicity structures [START_REF] Tuy | Monotonic optimization[END_REF][START_REF] Tuy | Monotonic optimization: Branch and cut methods[END_REF]. Some fundamental definitions and results from monotonic optimization theory are briefly recalled henceforth. Definition 2 (Monotonicity in R N ) A function f : R N → R is monotonically increasing if f (y) ≥ f (x) when y x, with denoting component-wise ordering. The main result of monotonic optimization theory states that the solution to [START_REF] He | Coordinated multicell multiuser precoding for maximizing weighted sum energy efficiency[END_REF] lies on the upper boundary of S ∩ Sc [13, Proposition 7]. In these cases, methods like the polyblock algorithm [START_REF] Tuy | Monotonic optimization[END_REF] and the branch-reduce-and-bound (BRB) algorithm [START_REF] Tuy | Monotonic optimization: Branch and cut methods[END_REF] can be used to globally solve [START_REF] He | Coordinated multicell multiuser precoding for maximizing weighted sum energy efficiency[END_REF] by searching only on the upper boundary of the feasible set, thus drastically simplifying the problem. Nevertheless, we remark that the complexity of monotonic optimization methods is still exponential in the problem size. However, as already observed, it is much lower than general global optimization methods which do not exploit any monotonicity structure. This makes monotonic optimization attractive for the development of a framework to benchmark any suboptimal method for solving [START_REF] He | Coordinated multicell multiuser precoding for maximizing weighted sum energy efficiency[END_REF].

GEE maximization

The GEE maximization belongs to the class of single-ratio fractional problems. So, finding its solution by the Dinkelbach's algorithm requires to solve the following auxiliary problem at iteration j:

max p K k=1 B log 2 (1 + γ k ) -λj (µ k p k + Ψ k ) s.t. p ∈ P (11)
for any given positive λj, and with P denoting the feasible set of Problem [START_REF] Ng | Energy-efficient resource allocation in multi-cell OFDMA systems with limited backhaul capacity[END_REF]. Note that the above problem is not in convex form due to the achievable rates, {B log 2 (1 + γ k )}, which also appear in the rate constraints. It is also not a monotonic optimization problem in canonical form, since the objective function is not increasing in p. Proposition 3 Problem (11) can be reformulated as a monotonic problem in canonical form.

Proofsketch: Problem ( 11) can be equivalently written as

max p q + (p) -q -(p, λj) s.t. p ∈ P (12)
wherein q + (p) and q -(p, λj) are increasing in p and given by

q + (p) = K k=1 q + k (p), q -(p, λj) = K k=1 q - k (p) + λj µ k p k + Ψ k .
The above reformulation is not yet a monotonic optimization problem in canonical form since the difference q + (p) -q -(p) of two increasing functions is not monotonic in the sense of Definition 2.

To proceed further, define p max = [Pmax,1, . . . , Pmax,K ] and introduce the auxiliary variable t = q -(p max , λj)-q -(p, λj). Then, for any given λj, rewrite the auxiliary problem in [START_REF] Zappone | Energy efficiency and interference neutralization in two-hop MIMO interference channels[END_REF] as max (t, p)

q + (p) + t s.t. (t, p) ∈ P ∩ Q (13)
with Q = (t, p) :

0 ≤ t ≤ q -(p max , λj) -q -(p, λj) 0 ≤ t ≤ q -(p max , λj) -q -(0K , λj) .
As for the constraints, the minimum rate constraint functions are also not monotonic in the sense of Definition 2. However, the set of constraints B log 2 (1 + γ k ) -R min,k ≥ 0 with k = 1, . . . , K, can be equivalently rewritten as the following single constraint:

min k=1,...,K q + k (p) -q - k (p) -R min,k ≥ 0 ⇐⇒ (14) min k=1,...,K   q + k (p)-   K i=1 q - i (p) - K i=1,i =k q - i (p)   -R min.k   = (15) min k=1,...,K   q + k (p) + K i=1,i =k q - i (p) -R min,k   q + (p) - K i=1 q - i (p) q -(p) ≥ 0 (16)
which is the difference of the two increasing functions q + (p) and q -(p). Similarly as above, we can thus introduce the auxiliary variable s and reformulate the problem in (13) as max (s,t, p)

q + (p) + t (17) s.t. (t, p) ∈ Q , 0 ≤ s ≤ q -(p max ) -q -(0K ) q -(p) + s ≤ q -(p max ) , q + (p) + s ≥ q -(p max )
Finally, it can be verified that Problem [START_REF] Utschick | Monotonic optimization framework for coordinated beamforming in multicell networks[END_REF] fulfills Definition 5, thus being a monotonic problem in canonical form. The exact details are omitted due to space constraints.

WMEE maximization

The maximization of WMEE belongs to the class of generalized fractional programs and requires to solve the following auxiliary problem at iteration j: max p min k=1,...,K

q + k (p)-q - k (p)-λj(µ k p k +Ψ k ) s.t. p ∈ P. ( 18
)
As before, the objective function is not monotonic. Proposition 4 Problem (18) can be reformulated as a monotonic problem in canonical form.

Proofsketch: Letting ν k (p, λj) = q - k (p) + λj (µ k p k + Ψ k )
, we can proceed as follows:

q + k (p) -ν k (p, λj) = q + k (p) -   K i=1 νi(p, λj) - K i=1,i =k νi(p, λj)   =   q + k (p) + K i=1,i =k νi(p, λj)   - K i=1 νi(p, λj). ( 19
)
By similar steps as in Section 3.3, we define t = K i=1 νi(p max , λj)-K i=1 νi(p, λj), and reformulate [START_REF] Björnson | Optimal resource allocation in coordinated multi-cell systems[END_REF] as

max (t,p) min k=1,...,K q + k (p) + K i=1,i =k νi(p, λj) + t s.t. (t, p) ∈ P ∩ Q with Q = (t, p) : 0 ≤ t ≤ K i=1 νi(p max , λj) -νi(p, λj) 0 ≤ t ≤ K i=1 νi(p max , λj) -νi(0K , λj)
, which, reformulating the rate constraints as in Section 3.3, can be checked to fulfill Definition 5.

NUMERICAL RESULTS

To exemplify the benefits of our framework, we consider the uplink massive MIMO scenario from [START_REF] Zappone | Energy-efficient power control: A look at 5G wireless technologies[END_REF], with B = 180 kHz. A base station equipped with 50 antennas and subject to hardware impairments serves a square area with edge of 1 km, where K = 5 mobiles are randomly placed. It is shown in [START_REF] Zappone | Energy-efficient power control: A look at 5G wireless technologies[END_REF] that, assuming MRC reception, the SINR enjoyed by the generic mobile k is expressed as in (1), wherein the coefficients α k , φ k , and β i,k depend only the propagation channels (here modeled as realizations of Rayleigh fading with path-loss model as in [START_REF] Calcev | A wideband spatial channel model for system-wide simulations[END_REF]) and on a parameter ∈ [0, 1] related to the hardware quality ( = 0 means ideal hardware). Here we set = 10 -2 . All mobiles have the same maximum feasible power Pmax and hardware-dissipated power Ψ k = -20 dBW. The noise power is generated as σ 2 = F BN0, wherein F = 3 dB and N0 = -174 dBm/Hz are the receiver noise figure, and noise power spectral density, respectively. No rate constraints have been enforced (i.e. R min,k = 0 for all k). In Fig. 1 we use our GEE maximization framework to benchmark the (theoretically suboptimal) procedure from [START_REF] Zappone | Energy-efficient power control: A look at 5G wireless technologies[END_REF], versus Pmax. As a baseline scheme, we also report the GEE obtained by full power allocation (i.e. p k = Pmax for all k). The results have been obtained by averaging over 10 3 independent channel scenarios. Our benchmark allows showing that the polynomial-time algorithm in [START_REF] Zappone | Energy-efficient power control: A look at 5G wireless technologies[END_REF] enjoys virtually optimal performance. Also, the achieved GEE eventually saturates, because for large Pmax only the transmit power required to achieve the global maximizer of the GEE is used.

In Fig. 2 we plot the energy-efficient Pareto region of the system for K = 2. All other system parameters are as in Fig. 1. The Pareto region is obtained by solving the WMEE maximization problem for different choices of the weights. As a comparison, we report the energy-efficient region obtained by a grid search over the transmit powers. We can see that our approach is able to characterize the complete region, while the gird search easily fails to find all parts. Also, it is interesting to observe that the point corresponding to GEE maximization lies on the Pareto frontier. In general, this is not guaranteed, because the GEE is not increasing in all individual EEs.

CONCLUSIONS

This work has developed an optimization framework to globally maximize the EE in wireless networks by jointly exploiting monotonic optimization theory and fractional programming theory. The framework is general enough to be applied to several instances of communication systems, such as general interference networks, massive MIMO systems, relay-assisted communications. While still exhibiting an exponential complexity, the developed framework enjoys a guaranteed convergence and a much lower complexity than standard global optimization algorithms. Also, it enables to benchmark practical algorithms, which are not theoretically guaranteed to achieve global optimality, as illustrated in the numerical results.

Definition 3 (

 3 Hyper-rectangle in R N ) Let a, b ∈ R N with a b. Then, the set of all x ∈ R N such that a x b is a hyperrectangle in R N and is denoted by [a, b].Definition 4 (Normal and Co-normal sets)A set S ⊂ R N is normal if ∀x ∈ S, the hyper-rectangle [0, x] belongs to S. A set Sc ⊂ R N is co-normal in [0, b] if ∀x ∈ Sc, then [x, b] ⊂ Sc.A given function h : R N → R defines a normal or a co-normal set if the following results hold true:Proposition 2 ([13]) The set S = {x ∈ R N : h(x) ≤ 0} is normal and closed if h is lower semi-continuous and increasing. The set Sc = {x ∈ R N : h(x) ≥ 0} is co-normaland closed if h is upper semi-continuous and increasing. Definition 5 (Monotonic optimization) A monotonic optimization problem in canonical form is defined as max x f (x) s.t. x ∈ S ∩ Sc (10) wherein f : R N → R is an increasing function, S ⊂ [0, b] is a compact, normal set with nonempty interior, and Sc is a closed conormal set in [0, b].

Fig. 1 .

 1 Fig. 1. GEE versus Pmax by: (a) global optimum by monotonic optimization plus fractional programming; (b) GEE maximizationproposed in[START_REF] Zappone | Energy-efficient power control: A look at 5G wireless technologies[END_REF]; (c) Full power allocation.

Fig. 2 .

 2 Fig. 2. Energy-efficient Pareto region for K = 2, by: (a) WMEE maximization by monotonic optimization plus fractional programming; (b) grid search over power; (c) GEE maximization point.