Ahmed Bader

Senior Member, IEEE Karim Abed-Meraim

Fellow, IEEE Mohamed-Slim Alouini

-Beaconless Geo-Routing Under The Spotlight: Practical Link Models and Application Scenarios

Keywords: beaconless geo-routing, packet detection criteria, average packet error rate, energy, latency, end-to-end performance

Analysis and simulation of beaconless geo-routing protocols have been traditionally conducted assuming equal communication ranges for the data and control packets. In reality, this is not true since the communication range is actually function of the packet length. Control packets are typically much shorter than data packets. As a consequence, a substantial discrepancy exists in practice between their respective communication ranges. In this paper, we devise a practical link model for computing the effective communication range. We further introduce two simple strategies for bridging the gap between the control and data packet communication ranges. Our primary objective in this paper is to construct a realistic analytical framework describing the end-to-end performance of beaconless geo-routing protocols. Two flagship protocols are selected in this paper for further investigation under the developed framework. For a better perspective, the two protocols are actually compared to a hypothetical limit case; one which offers optimal energy and latency performance. Finally, we present four different application scenarios. For each scenario, we highlight the geo-routing protocol which performs the best and discuss the reasons behind it.

I. INTRODUCTION

Beaconless geo-routing protocols have emerged as some of the most efficient packet delivery solutions for Wireless Sensor Networks (WSNs) [START_REF] Yicka | Wireless sensor network survey[END_REF], [START_REF] Sanchez | Beacon-less geographic routing made practical: Challenges, design guidelines, and protocols[END_REF] as well as Mobile Ad Hoc Networks (MANETs) [START_REF] Xiang | Self-Adaptive On-Demand Geographic Routing for Mobile Ad Hoc Networks[END_REF]. This is mainly due to the fact that nodes can locally make their forwarding decisions using very limited knowledge of the overall network topology. This comes very handy for mobile applications as well as for scenarios where random sleeping schedules are applied. Consequently, beaconless geo-routing offered substantial enhancement in terms of bandwidth efficiency in comparison to their beaconbased predecessors [START_REF] Sanchez | Beacon-less geographic routing made practical: Challenges, design guidelines, and protocols[END_REF].

In beaconless geo-routing, potential relays must undergo first a selection process whereby the node with the most favorable attributes (e.g. closeness to destination) shall eventually forward the packet [START_REF] Sanchez | Beacon-less geographic routing made practical: Challenges, design guidelines, and protocols[END_REF]. The selection process is triggered by the sender using a Request-To-Send (RTS) message. The key concept here is to weigh the response time of potential relays according to their forwarding attributes. Two of the earliest such protocols reported in literature are Geographic Random Forwarding (GeRaF) [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Energy and latency performance[END_REF], [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Multihop performance[END_REF] and Beaconless Routing (BLR) [START_REF] Heissenbüttel | BLR: beacon-less routing algorithm for mobile ad hoc networks[END_REF]. In GeRaF, the relay selection process is controlled by the packet sender at any given hop. The aim is to select the node lying within the communication range and which is closest to the destination. In BLR, the relay selection criteria is very similar but the process itself is rather distributed. The ideas presented in [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Energy and latency performance[END_REF], [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Multihop performance[END_REF] and [START_REF] Heissenbüttel | BLR: beacon-less routing algorithm for mobile ad hoc networks[END_REF] are believed to have fueled the research in this area over the decade to follow. Many of the geo-routing protocols have embraced on the key concepts presented in those early works. For instance, in Contention-Based Forwarding (CBF) [START_REF] Füssler | Contention-based forwarding for mobile ad-hoc networks[END_REF], response time to the RTS message is rather calculated as function of the advancement offered by a candidate relay towards the destination. On the other hand, the response time of potential relays in MACRO [START_REF] Ferrara | MACRO: an integrated mac/routing protocol for geographic forwarding in wireless sensor networks[END_REF] is weighed by the progress that can be made per unit power. In Cost and Collision Minimizing Routing (CCMR) [START_REF] Rossi | Cost-and collision-minimizing forwarding schemes for wireless sensor networks: Design, analysis and experimental validation[END_REF], the authors propose a technique whereby contending relays dynamically adjust their cost metrics during the selection process. GeRaF itself is modified in M-GeRaF [START_REF] Odorizzi | M-GeRaF analysis: Performance improvement of a multisink ad hoc and sensor network geographical random routing protocol[END_REF], such that it serves wireless sensor networks with multiple sinks. Implicit Geographic Forwarding (IGF) [START_REF] He | Robust and timely communication over highly dynamic sensor networks[END_REF] proposes two optimizations to reduce the number of responses and collisions during the relay selection process. Yet, one of the most noteworthy twists in beaconless geo-routing was offered in Beaconless On Demand Strategy for Geographic Routing (BOSS) [START_REF] Sanchez | BOSS: Beacon-less On Demand Strategy for Geographic Routing in Wireless Sensor Networks[END_REF]. In this protocol, the sender piggybacks the data payload in the RTS control packet. This was mainly motivated by the discrepancy in the communication ranges between the data packet (containing the payload) and the control packet. Another recent and interesting addition to the geo-routing protocol family is CoopGeo [START_REF] Aguilar | Coop-Geo: A Beaconless Geographic Cross-Layer Protocol for Cooperative Wireless Ad Hoc Networks[END_REF] which combines cooperative relaying and beaconless geo-routing with the objective of enlarging the progress made every hop. Finally, a hybrid mechanism has been recently devised in [START_REF] Xiang | Self-Adaptive On-Demand Geographic Routing for Mobile Ad Hoc Networks[END_REF] to switch between beacon-based and beaconless states based on the underlying application scenario.

Despite the breadth of development in the beaconless georouting protocol family, analysis and simulation of these protocols have been carried out often using simplistic link models. To be more specific, the effect of the packet length on the probability of successful packet detection has not been considered at all except in BOSS [START_REF] Sanchez | BOSS: Beacon-less On Demand Strategy for Geographic Routing in Wireless Sensor Networks[END_REF]. Empirical test results obtained by the authors in [START_REF] Sanchez | BOSS: Beacon-less On Demand Strategy for Geographic Routing in Wireless Sensor Networks[END_REF] indicated that the average packet error rate (PER) for the data message is notably higher than that of the control message. This is true simply due to the fact that the data packet is typically much larger in size. In fact, this is expected and is inline with literature [START_REF] Awoniyi | Packet Error Rate in OFDM-Based Wireless LANs Operating in Frequency Selective Channels[END_REF]. When convolutional coding is utilized (which is often the case), the average PER grows with the packet length. The growth in PER is associated with larger signal to noise and interference ratio (SINR) targets and therefore shorted communication ranges.

Another major area where improvement is deemed essential relates to the assessment of end-to-end performance. The vast majority of beaconless geo-routing protocols have been investigated only from the perspective of a single node or a single hop. End-to-end performance has been seldom considered, and whenever considered, it has been studied using empirical test or simulations. Results obtained from such approaches are valuable indeed. However, they are limited to a finite set of scenarios and parameter values. Consequently, we believe that it is quite instrumental to develop an analytical framework for the evaluation of the end-to-end performance. Such a framework should offer the research community a readily available tool to study as well as optimize the performance of beaconless geo-routing protocols under any arbitrary choice of scenarios and parameters.

Based on the above, it is our primary objective in this paper to develop an end-to-end analytical framework for beaconless geo-routing protocols while taking into consideration a more practical link model. In doing so, we do not analyze all georouting protocols as this would require a substantial amount of work. Instead, we have reverted to studying two representative protocols: GeRaF and BOSS. A detailed rationale behind this selection is provided in Section II-A. Subsequently, our main contribution in this paper is twofold:

1) Providing an end-to-end analytical framework for two prominent beaconless geo-routing protocols. This framework can be conveniently adapted to other protocols within the same family. 2) Incorporating practical link models in the analysis which take into consideration fading as well as the effect of packet length on the average PER. The paper is organized as follows. Section II provides an overview of beaconless geo-routing protocols. In specific, Section II-A rationalizes the selection of BOSS and GeRaF as the focus of our study. Section III presents the wireless channel as well as the wireless link models. The end-to-end performance of BOSS and GeRaF is analyzed in depth in Section IV. Four distinct application scenarios are investigated in the context of beaconless geo-routing in Section V. Finally, key examples on how to optimize end-to-end performance of beaconless geo-routing are illustrated in Section VI. A summary of notations used in this paper is provided in Table I.

II. BEACONLESS GEO-ROUTING OVERVIEW

In broad terms, beaconless geo-routing protocols operate as per the following guidelines. The sender's communication range is divided into two areas. The first area is the one offering positive progress towards the destination and is denoted as PPA. In other word, relays lying in the PPA are closer to the destination than the sender. The complementary of this area is the negative progress area (NPA). Each area is further sliced into N forwarding subareas. Two interesting alternative for slicing PPA and NPA are illustrated in [START_REF] Aguilar | Coop-Geo: A Beaconless Geographic Cross-Layer Protocol for Cooperative Wireless Ad Hoc Networks[END_REF](Fig. 2) and [START_REF] Sanchez | BOSS: Beacon-less On Demand Strategy for Geographic Routing in Wireless Sensor Networks[END_REF](Fig. 3). The sender of a packet first issues a requestto-send (RTS) message. Upon the reception of this message,

A. Assessment of Various Protocols

As mentioned in Section I, we have selected GeRaF and BOSS as a baseline for our study. The selection of GeRaF stems from the fact that its performance on per-node basis is well understood and elaborately analyzed in [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Energy and latency performance[END_REF] and [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Multihop performance[END_REF]. On the other hand, BOSS has been shown in practice to excel in certain aspects of performance [START_REF] Sanchez | Beacon-less geographic routing made practical: Challenges, design guidelines, and protocols[END_REF]. Justifications for not including other protocols in this study are summarized in the following.

1) BLR was not studied further for the simple reason that it has been observed to suffer from frequent packet duplications and collisions [START_REF] Sanchez | Beacon-less geographic routing made practical: Challenges, design guidelines, and protocols[END_REF], [START_REF] Heissenbüttel | Evaluating the limitations of and alternatives in beaconing[END_REF]. 2) CBF is also expected to suffer to some extent from the same problem as BLR since the relay selection is carried out in a distributed fashion. CBF proposes to reduce the impact of packet duplication by means of devising a suppression phase. However, this is expected to drive the protocol to consume more energy and produce larger forwarding delays. 3) MACRO is based on utilizing the residual energy as a relay selection metric. It is shown in [START_REF] Ferrara | MACRO: an integrated mac/routing protocol for geographic forwarding in wireless sensor networks[END_REF] that MACRO outperforms GeRaF only slightly in certain aspects of single-hop performance. Furthermore, our preliminary investigations revealed that the end-to-end delay performance of both protocols tends to be quite comparable. 4) M-GeRaF is a mult-sink extension of GeRaF. It may be useful in infrastructure-based applications with multiple sinks or for multicast applications. The scope of this paper is restricted however to unicast scenarios. 5) On the other hand, a deeper look at IGF exposes two aspects which may jeopardize its ability to perform well. The forwarding region which contains candidate relays is restricted in IGF to a small sector [START_REF] He | Robust and timely communication over highly dynamic sensor networks[END_REF](Fig. 2). The rationale behind this is to increase the probability that all candidate relays lie within the communication range of each other. As such, it is assumed that collisions are very unlikely to occur. In practice, restricting the size of the forwarding region limits the average number of candidate relays to a small subset. This may result in empty cycles wherein there will no candidate relays. This needs to be taken into consideration for the sake of an objective analysis. Furthermore, IGF assumes that in the case of collisions, the sender has the ability to resolve duplicate CTS responses by choosing only one. However, authors do not indicate how this is achieved. The lack of an explicit mechanism for resolving colliding packets only leaves room for speculations about how IGF would perform. Based on the above reasoning we have selected not to pursue IGF any further. 6) CoopGeo on the other hand focuses on creating diversity during the transmission process by selecting two relays instead of one. The primary relay is the one that maximizes progress towards the destination. The secondary one offers diversity. In that sense, CoopGeo has been designed in a way to reduce PER without really considering its impact on energy performance. The study has been also limited to a single-hop case. Although we do acknowledge the value of contributions of CoopGeo, we rather believe it should be deferred as a subject of future research. 7) At the other end of the spectrum, CCMR indeed promises performance levels which are superior to GeRaF. However, the dynamic nature of the relay selection process makes it nothing but straightforward to derive meaningful expressions for the end-to-end performance.

It is essential to note here that we are not overlooking the performance bounds that CCMR is poised to achieve. In order to put things into the right perspective, we have introduced a hypothetical beaconless geo-routing protocol which is able to achieve the optimum end-to-end performance. Although we do not know for a fact where CCMR stands with respect to this optimum performance level, we will have the chance now to compare GeRaF and BOSS against the performance limits of beaconless geo-routing. In the context of beaconless geo-routing, the optimum protocol is evidently the one which involves the minimum number of transactions during the relay selection phase. This simply translates to one RTS message from the sender, one CTS response from the best candidate relay, followed by packet transfer. The optimum forwarding process here is denoted as RTS/CTS/DATA-opt.

B. Bridging The Gap

As mentioned in Section I, BOSS has been originally designed such that the data payload is incorporated inside the first RTS message. By doing that, only those nodes who are able to successfully receive the data packet will contend for becoming the next forwarder [START_REF] Sanchez | BOSS: Beacon-less On Demand Strategy for Geographic Routing in Wireless Sensor Networks[END_REF]. However, transmitting the data and control packets at the same maximum available power obviously results in a range gap. In other words, there will be some nodes who were not able to receive the RTS message successfully but rather will be able to receive the subsequent control packets. This is clearly a waste of node energy. Control packets can have the same range as the data packet while using lower transmit power. To alleviate this shortcoming, we assume that nodes transmit at a lower power level when sending a control message. To offer a fair comparison, GeRaF is equipped with the same capability. In other words, nodes are able to reduce the transmit power on the control packet to the level that the resulting range matches that of the data packet. GeRaF in this case is labeled as GeRaF-PC. In the specific case of GeRaF however, there is more than one way to bridge the gap between the data and control packets. One method that we have studied here is to utilize time diversity with maximal ratio combining (MRC) at the receiver. Under this scheme, the sender transmits control and data packets at the maximum power. The data packet is retransmitted as many times as needed to make the two communication ranges equivalent. This version of GeRaF is thus tagged as GeRaF-MRC. The average number of transmissions needed is denoted as n T .

III. WIRELESS LINK MODEL

In this section, we first highlight some key elements to be considered with respect to the underlying wireless channel model. We then shed some light on how to derive a numerical relationship between packet length and average PER. This is instrumental to lay down a practical model for establishing a successful link between two nodes.

A. Key Considerations

1) Unpunctured convolution coding is utilized with code rate 1 2 . Hard-decision decoding is assumed. Unless explicitly mentioned, QPSK modulation is used.

2) The physical layer (PHY) is loosely based on the widely adopted IEEE 802.15.4-2006 standard [START_REF] Baronti | Wireless sensor networks: A survey on the state of the art and the 802.15.4 and ZigBee standards[END_REF]. 3) Nodes are generally mobile thus the channel is timeselective with respect to the packet but is assumed to be constant within the symbol duration. For application scenarios where nodes are stationary, we assume a quasistatic fading channel. 4) For WSN applications, we may conveniently assume that the channel is frequency non-selective. However, for some MANET applications such as Vehicular Ad Hoc Networks (VANETs), the channel is indeed frequency selective. The time and frequency selectivity of the channel requires further elaboration. For WSN application scenarios, the communication ranges are typically short; in the range of a couple of hundred meters. Consequently, the delay spread of the wireless channel is also small. As such, the fading channel can be assumed to be frequency non-selective. The occupied bandwidth in IEEE 802.15.4-2006 is 2 MHz [START_REF] Francisco | Coexistence of ZigBee Wireless Sensor Networks and Bluetooth inside a Vehicle[END_REF]. For the channel to be otherwise frequency-selective, the delay spread should be greater than 0.5µs. This corresponds to an excess path length of 150 meters. Communication ranges in WSN applications are relatively short such that an excess path length great than 150 meters is quite unlikely. Furthermore, nodes are typically stationary in WSNs thus the channel can be assumed to be quasi-static as mentioned above.

On the other hand, nodes in VANET applications enjoy better access to energy resources, and thus are able to transmit at higher power levels. As such, communication ranges are relatively larger and so are the excess path lengths. This drives the channel towards becoming frequency selective. As a consequence, this mandates nodes to utilize some sort of channel equalization, e.g. a zero-forcing equalizer which in essence performs as a RAKE receiver. From a time-domain perspective, the channel varies over the duration of a single packet. This definitely needs to be taken into consideration when developing the packet detection model.

B. Dependency of Range on Packet Length

This subsection outlines the method for deriving a relationship between the length of the packet and the detection threshold. In [START_REF] Awoniyi | Packet Error Rate in OFDM-Based Wireless LANs Operating in Frequency Selective Channels[END_REF], the authors derive an expression for the PER of an Orthogonal Frequency Division Multiplexing (OFDM) system utilizing convolutional coding. The channel in [START_REF] Awoniyi | Packet Error Rate in OFDM-Based Wireless LANs Operating in Frequency Selective Channels[END_REF] is assumed to be quasi-static and frequency selective. Thus, the channel vector H represents a set of uncorrelated fading coefficients corresponding to the OFDM subcarriers. In our case, the channel is assumed to be frequency non-selective or is forced to become so by means of a RAKE equalizer. In the case of stationary nodes, the channel simply becomes a scalar. However, for mobile nodes, the channel is actually time-varying. Nevertheless, we can still utilize the same analytical framework in [START_REF] Awoniyi | Packet Error Rate in OFDM-Based Wireless LANs Operating in Frequency Selective Channels[END_REF] here. However, H would be now representing the channel fading coefficients over time instead of frequency.

In our case, time is divided into equal blocks whereby the duration of one block equals the channel coherence time. Obviously, the channel coherence time depends on the level of node mobility and may be computed using [START_REF] Rappaport | Wireless Communications: Priciples and Practice[END_REF] (Eq. 4.40.c). To proceed, we assume that the channel fading coefficient within each coherence block is constant and is uncorrelated with respect to the other blocks. For the sake of simplification, we assume that the coherence time is an integer multiple of the symbol duration. The SINR in a given coherence block is denoted by γ. As will be discussed in the next subsection, γ is exponentially distributed with mean γ. Based on the above, we can now utilize the analysis offered in [START_REF] Awoniyi | Packet Error Rate in OFDM-Based Wireless LANs Operating in Frequency Selective Channels[END_REF] to derive a numerical relationship between the length of the packet and γ. This is plotted in Figure 1 for various PER targets. It is worthwhile to note that for loose PER targets (e.g. 20%), a 20 fold increase in packet length resulted in an 8-dB growth in the required SINR. This growth is less drastic in case of lower PER targets.

C. Packet Detection Criteria

The SINR threshold required to successfully receive a control packet and a data packet are denoted by γ tC and γ tD respectively. As the length of the control message is shorter in length than the data message, then γ tC < γ tD . The fading coefficients are assumed to be complex Gaussian. As a generic case, the channel is considered to be frequency selective. It is modeled by a tap-delay line with coefficients {h n } m n=1 , where m is the number of multipaths [START_REF] Rappaport | Wireless Communications: Priciples and Practice[END_REF]. In case of a frequency non-selective channel m = 1. The SINR over an arbitrary communication link is given by γ = Pt Pn m n=1 |h n | 2 , where P t is the transmit power and P n is the noise floor. The SINR γ is exponentially distributed with mean

γ = 2Pt Pn m n=1 E[|h n | 2 ], where m n=1 E[|h n | 2 ]
is function of the distance between the transmitter and the receiver. A control packet is successfully detected if γ ≥ γ tC . Similarly, γ ≥ γ tD is the condition for successful detection of the data message. Denoting the communication range by R, we have

m n=1 E[|h n | 2 ] = λ 4πR 2 α
at the edge of the range, where α is the path loss exponent and λ is the wavelength. Consequently, the communication range for the data message is expressed as

R = λ 4π 2P tD γ tD P n 1/α , (1)
where P tD is the transmit power of the data packet. The range for the control packet is obviously obtained by substituting γ tD and P tD in (1) with γ tC and P tC respectively.

For GeRaF-MRC, we assume i.i.d. channel fading coefficients every time the packet is transmitted. The desired MRC gain here is γ tD /γ tC . As such, the number of packet transmissions required is n T = ⌈γ tD /γ tC ⌉.

IV. END-TO-END PERFORMANCE ANALYSIS

Nodes are assumed to be distributed according to a Poisson Point Process (PPP) with an average density of ρ. Nodes are assumed to employ asynchronous sleeping schedules with a duty cycle of ǫ. Furthermore, nodes are assumed to activate a busy tone (BT) during listening and receiving to help mitigate the hidden node effect [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Energy and latency performance[END_REF], [START_REF] Haas | Dual busy tone multiple access (DBTMA) -a multiple access control scheme for ad hoc networks[END_REF]. Originally, BOSS neither incorporates sleeping schedules nor a busy tone. Nevertheless, BOSS is equipped here with these tools for the sake of a fair and objective study. The duration of the data and control messages are denoted by T p and T c respectively. It is assumed in this paper that both versions of GeRaF as well as BOSS are utilizing the smallest possible packet size for the control message. Control packets are transmitted at a power level of P tC while data packets are transmitted at P tD . The power consumed while in receive state is P Rx while the transmit power for the BT is P tBT . In the next two subsections, we offer a detailed analysis of the end-to-end performance of GeRaF-PC, GeRaF-MRC, and BOSS.

A. GeRaF

The forwarding process occurs in time over successive cycles. One cycle consists of N time slots corresponding to the number of forwarding subareas in PPA. The duration of one slot is T s . GeRaF is designed such that each slot consists of two parts. The first is always reserved to the sender while the second contains responses from candidate relays. As such, T s = 2T c . There are three main types of messages that the sender may send over the first half of the control slot: RTS, CONTINUE, and OK. The CONTINUE message indicates the occurrence of a collision and triggers a new round of contention between the relays. Collisions typically occurs between those relays offering the best progress towards the destination, i.e. those lying in the foremost forwarding subarea. The OK message simply informs the successful relay of being selected as the next-hop forwarder.

At any given hop, there would be η empty cycles followed by one non-empty cycle. Empty cycles occur when there are no awaken nodes in the PPA. In the non-empty cycle, there would be m e empty slots followed by m n collision-resolution slots. The m e empty slots reflect the fact that there are no awaken nodes in the first m e forwarding subareas of the PPA. The expectations E[η], E[m e ], and E[m n ] are found in explicit forms in [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Energy and latency performance[END_REF] ((3) and ( 4)). Table II provides a description of the relay selection and packet forwarding process during a given hop of GeRaF-MRC. For each activity, Table II indicates: 1) The duration of the activity, t y .

2) The nature of the nodes involved in the activity.

3) The average count of nodes involved, n y .

4) The task associated with this activity.

5) The power factor at which the associated task is conducted, pf y .

It is important to note that activities may overlap in time. For instance activities 3 and 4 in Table II take place at exactly the same time: the sender issues a RTS message while awaken nodes react to it. The energy consumed to accomplish a given activity is t y n y pf y . The overall energy consumed per hop, E hop is the sum of all individual transmission and reception activities undertaken to select the successful relay and then send the packet to it. As per Table II, groups of activities are repeated multiple times. For example, activities 1 and 2 in Table II are repeated on average E[η] times. For GeRaF-MRC, P tD = P tC = P tmax which is the maximum transmit power available to a node. We also note that for GeRaF-PC, P tC = P tD γt C γt D , while P tD = P tmax . On the other hand, it can be shown in light of Table II that the average delay per hop is expressed as

l hop = (E[η]N + E[m e + m n ])T s + n T T p. (2)
The expected number of hops traversed before reaching the destination as function of R and ρ is denoted by q. It may be derived using [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Multihop performance[END_REF] (( 8) and ( 19)). As such, the end-to-end energy and delay are qE hop and ql hop respectively.

The forwarding process of GeRaF-PC is quite similar, except for the fact that the data payload is only transmitted once.

B. BOSS

BOSS was designed such that packet forwarding may well be picked up by a node in the NPA. Under such circumstances, authors of BOSS suggest to use a greedy-facegreedy algorithm [START_REF] Sanchez | BOSS: Beacon-less On Demand Strategy for Geographic Routing in Wireless Sensor Networks[END_REF]. In such a case, we assume that the remaining distance to the destination stays unchanged. This is indeed a sub-accurate assumption. However, it constrains the complexity of the subsequent analysis.

Nodes in BOSS compute the value of the response time based on the subarea they lie within. Nodes offering the best progress will have the shortest response time. To reduce the probability of collisions, a random variable is added to the response time. The variable is uniformly-distributed over the interval [0, x]. As a result, this enhances the granularity at which time is slotted: the duration of one control slot for BOSS is T c /x while for GeRaF is as large as 2T c .

The forwarding process in BOSS can be conceived to consist of 4 distinct stages:

1) Empty cycles 2) Cycles where forwarding is picked up from NPA 3) Cycles with collisions 4) Successful round The relay selection and packet forwarding process in BOSS is captured in detail in Table III. The probability that forwarding is picked up by a node in NPA is equivalent to the probability that there exists no awaken nodes in PPA and at least one awaken node in NPA. As such

p N P A = e -ζǫρπR 2 (e -(1-ζ)ǫρπR 2 ), (3)
where ζ is the ratio of the PPA to the entire coverage area. The probability that forwarding takes place from PPA is therefore

p P P A = 1 -p N P A . Expressions for E[m e
] and E[m n ] are again found in [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Energy and latency performance[END_REF]((3) and ( 4)). We also need to derive an expression for the probability of collision denoted here as p c . This probability can be derived in light of [START_REF] Bader | An Efficient Multi-Carrier Position-Based Packet Forwarding Protocol for Wireless Sensor Networks[END_REF] [START_REF] Füssler | Contention-based forwarding for mobile ad-hoc networks[END_REF]. Given the number of contending nodes is n, then [START_REF] Bader | An Efficient Multi-Carrier Position-Based Packet Forwarding Protocol for Wireless Sensor Networks[END_REF] (7) provides an expression for the probability that the first j slots are not resolvable, i.e. they carry colliding messages. In our case, we are rather interested in the event of having a collision after a series of "empty" slots. The probability of having j -1 empty slots from a pool of x slots is hence x-j+1

x n . When we are left with only x -j + 1 slots, then using [START_REF] Bader | An Efficient Multi-Carrier Position-Based Packet Forwarding Protocol for Wireless Sensor Networks[END_REF] (6) and ( 7), the probability that the first slot will be non-resolvable is 1 -x-j

x-j+1 n-1

, n ≥ 1. Consequently, the probability of collision given n is

p c|n = 1 - x-1 j=1 x -j x -j + 1 n-1 , n ≥ 1. (4)
The probability mass function (pmf) for the number of nodes existing in a given forwarding subarea is given by

p n (n|m e ) = (ǫρa me ) n n! e -ǫρam e . (5)
With p me (m e ) readily available from [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Energy and latency performance[END_REF](3), we are able now to compute p n (n) by averaging over m e . We can then compute p c = n p c|n p n (n). The number of cycles with collisions before a successful round is denoted by η and follows a geometric distribution such that p ή (ή) = p c ή (1-p c ). Consequently,

E[ή] = 1 -p c p c . (6)
In light of Table III, the energy consumed in forwarding a packet per hop can be expressed by summing up all energy terms (as we have done in the case of GeRaF-MRC). On the other hand, the delay per hop is given by

l hop = E[η](T p + 2xN T s ) + p N P A (T p + (2xN + 1)T s ) + p P P A (E[ή](T p + xN T s ) + T p + (E[m e ] + 2)T s ). (7)
For a communication range equal to R, the average number of hops is again derived using [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Multihop performance[END_REF](( 8) and ( 19)), such that E e2e = qE hop and l e2e = ql hop .

C. RTS/CTS/DATA-opt

Whereas GeRaF-PC and GeRaF-MRC mandate the use of a CONTINUE message, it is assumed that RTS/CTS/DATAopt does not. As mentioned before, RTS/CTS/DATA-opt is a hypothetical geo-routing protocol which is able to successfully forward a packet using the minimum number of message transactions. This is illustrated in Table IV. Energy consumed per hop is derived in light of Table IV by summing up all energy terms as done before for BOSS, GeRaF-MRC, and GeRaF-PC. The delay per hop however is given by

l hop = (2N E[η] + 2E[m e ] + 3)T c + T p . ( 8
)
Bringing RTS/CTS/DATA-opt into the picture greatly aids in understanding the performance limits of GeRaF-PC, GeRaF-MRC, and BOSS. Consequently, we introduce here a composite metric of performance relative to RTS/CTS/DATA-opt. The metric incorporates both energy and delay and is defined as

C e2e = ϕ E e2e,P E e2e,opt + (1 -ϕ) l e2e,P l e2e,opt , (9)
where the subscript P corresponds to any of the protocols GeRaF-MRC, GeRaF-PC, or BOSS, and ϕ is a weighting parameter.

V. APPLICATION SCENARIOS

With the ability to compute end-to-end energy and delay, we are able now to study the performance of geo-routing protocols over a wide range of parameters and application scenarios. Before doing so, we look more closely at how these protocols perform as function of node density which is indeed an intrinsic characteristic of any wireless network. Figure 2 shows the end-to-end performance as function of the underlying node density.

There are a few noteworthy observations here. First, we note how well GeRaF-MRC performs in terms of delay at low node densities (Figure 2(a)). In fact, at very low densities GeRaF-MRC clearly outperforms BOSS and GeRaF-PC and approaches optimality (represented by RTS/CTS/DATA-opt). The reason behind this is the fact that GeRaF-MRC transmits both data and control packets at the maximum available power, thus achieving larger hop distances. As a consequence, the number of hops required is less. Furthermore, sparse node densities accompanied with shorter hop distances in case of GeRaF-PC induce many more empty cycles. However, at higher node densities, BOSS starts to demonstrate better delay performance. The strategy of introducing more granularity to the time domain in case of BOSS indeed pays off at higher node densities. On the flip side of the coin, excellent delay performance for BOSS comes at the expense of more energy consumption as per Figure 2(b). As shown in the figure, it is GeRaF-PC which offers unparalleled performance in terms of energy. GeRaF-PC reaches nearly optimal energy performance starting from medium node densities. With such an excellent energy performance, GeRaF-PC is able to offer the lowest composite cost metric as shown in Figure 2(c).

In this section, we further evaluate the performance of beaconless geo-routing protocols from the perspectives of four specific application scenarios: 1) VANET scenarios in which traffic and road safety information are exchanged between vehicles. 2) Rescue field operations in which members of a rescue team communicate voice and video data with each other.

3) Transmission of meter readings and usage patterns in

Smart Utility Networks (SUNs). 4) Environmental or process monitoring applications such as monitoring air quality in urban areas or temperature variations in an industrial process.

The analytical framework developed in this paper comes handy in identifying the application areas or scenarios where each protocol is better positioned. These four application scenarios are discussed in greater detail next.

A. Vehicular Ad Hoc Networks

The wireless channel in a VANET is going to be frequency selective as explained in Section III. A node in a VANET is privileged with access to relatively abundant energy. Therefore, nodes can transmit at a higher radio power level. Furthermore, energy consumption is not a primary concern. As such, we can grant end-to-end delay performance more attention by setting the weighting factor ϕ = 0.2 in (9). Moreover, the availability of energy eliminates the need for sleeping in VANETs, i.e. ǫ = 1. In urban and dense urban scenarios, node density is high. With ǫ = 1, the node density is virtually even higher.

Figure 3 captures performance results in terms of the composite performance metric for a VANET scenario. It is quite evident that BOSS is the protocol of choice in this case, particularly at medium node densities. In highly dense networks, GeRaF-PC might be able to keep up with BOSS (Figure 3(a)). However, increasing the transmit power gives grounds back to BOSS as shown in Figure 3(b). For instance, when the transmit power is set at greater than 22 dBm, performance of BOSS comes very close to the limit.

B. Rescue Field Networks

Fire fighters and rescue teams would highly benefit from the availability of voice and video communications during their operations. Higher data rates would be required under such circumstances. We assume that the PHY layer is capable of meeting this requirement in the sense that is able to support higher oreders of modulation and coding schemes (MCS) 1 . On the other hand, shorter packet lengths would be typically the case here since voice and video are the primary type of data. The duration of the packet size is set here at T p = 10 ms.

Delay performance is of large importance for this application scenario. Energy comes at second priority since users may have the chance to recharge the batteries of their devices upon the completion of each mission. Nevertheless, energy consumption is still a concern especially for operations of long durations. Consequently, we set ϕ = 0.6. Needless to mention here that ǫ = 1, i.e. nodes do not sleep due to the risk and human safety factors associated with such applications.

Figure 4 shows end-to-end performance of GeRaF-MRC, GeRaF-PC, and BOSS for 5 different modulation and coding schemes: QPSK 1 2 , QPSK 3 4 , 16 QAM 1 2 , 16 QAM 3 4 , and 64 QAM 1 2 . We first note that all protocols suffer from growth in the end-to-end delay as the MCS rank is upgraded, as shown in Figure 4(a). This is intuitive since communication ranges are reduced due to the increase in the SINR requirement. At the same time however, the number of bits transported endto-end also increases. As such, we normalize the end-to-end delay by the number of bits as shown in Figure 4(b) which conveys a less steep growth in the performance metric as MCS is upgraded. It is also worthwhile to note from Figure 4 that GeRaF-MRC performs quite poorly at higher MCS ranks. This is due to the fact that the SINR gap between the control and data packets grows significantly and thus the number of data packet transmissions n T faces a sheer increase. In terms of energy per bit, it is clear also that BOSS does not perform very well. For rescue field networks, GeRaF-PC is clearly the best choice since it consistently offers the lowest relative cost metric as Figure 4(d) reveals.

C. Smart Utility Networks

Remote home metering and transfer of usage patterns is one important aspect of smart utility networks [START_REF] Hatler | Wireless Sensor Networks for Smart Cities: A Market Study[END_REF]. For such an application, energy performance is very important since users will not be willing to recharge the batteries very often. On the other hand, delay is substantially insignificant since meter readings collection may take place only every few weeks. As such, the focus in a SUN application is to study the energy performance.

Sleeping is an essential practice in this application scenario as it helps save energy. So it is favorable to apply immense sleeping patterns. The virtual effect of immense sleeping is a steep decline in node density. An additional property of a SUN is the requirement for only modest data rates. The performance of beaconless geo-routing for SUN applications is thus best viewed by varying the node density as a study parameter. Looking again at Figure 2(b), it is clear that GeRaF-PC is best fit to serve remote utility metering applications.

D. Environmental Monitoring Networks

Environmental and process monitoring applications are very similar in terms of their requirements to smart utility networks, except for the fact that delay may hold larger significance. This is mainly because some level-crossing events may mandate a rapid response, e.g. process temperature crossing a hazard limit, or liquid level in tank near to cause spills. Looking back again on Figure 2(a), GeRaF-MRC is shown to provide the best end-to-end delay performance. Nevertheless, if energy and delay have equal importance, GeRaF-MRC has an edge only for very low node densities as illustrated in Figure 2(c). As node density increases, GeRaF-PC becomes a better choice.

VI. PARAMETER OPTIMIZATION

We can also utilize the analytical framework developed in this paper to optimize protocol performance. For instance, we can optimize the performance of GeRaF-PC over the number of forwarding subareas, N . Figure 5 shows the behavior of end-to-end performance metrics in response to variations in the N . It is clear that the optimum value of N increases with node density. For considerable ranges of node densities, the end-to-end performance function (whether latency, energy, or composite cost) is convex. In other words, an absolute optimum value for N exists. We further note that it is preferable at low densities to keep N small. We recall that increasing the value of N may be needed to reduce the probability of collisions. Nevertheless, doing that is not necessary for low densities since the probability of collision is anyway small. Otherwise, increasing N would only lead to increasing the delay since it entails a proportional increase in the number of time slots per cycle.

It is also interesting to study performance as function of data packet durations. It is important to study performance from this perspective since some applications place some constraints on packet lengths. For instance, vector-based data applications (i.e. voice and video) typically require short packets [START_REF] Akyildiz | A survey on wireless multimedia sensor networks[END_REF]. So the question here is: how well do GeRaF-PC, GeRaF-MRC, and BOSS perform for short packet lengths? Figure 6 provides the answer. It is quite intuitive to expect the end-to-end delay to increase as the packet duration T p increases. For the sake of a more meaningful insight, we have instead normalized the delay by the number of bits when constructing the plots of Figure 6. In other words, we seek the amount of end-to-end delay incurred in transporting a single information bit from source to destination. The same normalization philosophy is applied when considering end-to-end energy. From Figure 6(a), we note that the normalized end-to-end delay for all three protocols drops as the packet length increases. However, it is worthwhile also to note that they all diverge away from optimality. From the perspective of normalized energy performance -Figure 6(b) -we see see clearly that GeRaF-PC slightly improves as T p increases, GeRaF-MRC features an almost steady performance, while BOSS inclines more energy per bit. Taking energy and delay jointly into consideration -Figure 6(c) -shows that only GeRaF-PC enjoys better performance at larger values of T p . So if the designer has some flexibility in choosing the packet duration, then there is no doubt that short packet lengths are generally favorable for GeRaF-PC but not for GeRaF-MRC and BOSS.

VII. CONCLUSIONS

In this paper, we have developed an analytical framework for the end-to-end performance of two prominent beaconless geo-routing protocols: GeRaF and BOSS. In doing so, we have utilized a practical packet detection model in order to account for the discrepancy between the communication ranges of the data and control packets. In line with this practical model, two new versions of GeRaF have been devised. The first one applies a power headroom on data packets and is labeled as GeRaF-PC. The second utilizes MRC techniques to bridge the gap between control and data packets and is tagged as GeRaF-MRC. Using the analytical framework developed herewith, four different application scenarios have been studied: VANETs, rescue field networks, smart utility networks, and environmental monitoring. It is shown in this paper that BOSS is optimal for VANETs since it offers the best delay performance. On the other hand, GeRaF-PC is the best choice for rescue field networks, as it is able to cope well with video communication requirements. GeRaF-PC is also very wellpositioned for smart utility applications. For environmental monitoring applications, GeRaF-MRC is often the protocol with best performance. Finally, we have exemplified how the analytical framework can be used to optimize some of the protocol parameters. For instance, we have shown that the optimum number of forwarding subareas increases with node density in the case of GeRaF-PC.

Fig. 1 .

 1 Fig. 1. Relationship between the required average SINR and the packet length for a range of PER targets.

  Energy consumed to transport one bit from source to destination.

5 Fig. 2 .Fig. 3 .

 523 Fig.2. End-to-end performance of GeRaF-PC, GeRaF-MRC, and BOSS as function of the network node density.

  /DATA-opt (a) Absolute end-to-end delay.

  -end delay per bit (sec/bit) GeRaF-MRC GeRaF-PC BOSS RTS/CTS/DATA-opt (b) End-to-end delay normalized by the number of bits transported per packet. bit (mJ/bit) GeRaF-MRC GeRaF-PC BOSS RTS/CTS/DATA-opt (c) End-to-end energy consumed in transferring one bit from the source to the destination.

  End-to-end composite cost metric with ϕ = 0.6.

Fig. 4 .

 4 Fig.4. End-to-end performance results for rescue field networking applications.

  ms) e2e delay per bit (sec/bit) GeRaF-MRC GeRaF-PC RTS/CTS/DATA-opt BOSS (a) End-to-end delay elapsed to transport one bit of information.

  ms) e2e energy per bit (mJ/bit) GeRaF-MRC GeRaF-PC RTS/CTS/DATA-opt BOSS (b) Energy to transport one bit end-to-end.

  End-to-end composite cost metric.

Fig. 6 .

 6 Fig.6. Performance of beaconless geo-routing protocols over a range of packet durations.

Fig. 5 .

 5 Fig.5. Optimizing over the number of forwarding subareas, N . GeRaF-PC is studied in this specific example. In each subfigure, the optimum value of N is shown as function of the node density.

TABLE I TABLE OF NOTATIONS

 IOF

	D	Distance between source and destination
	L	Packet length in bits
	Pt max	Maximum transmit power available for a node
		(limited by hardware and energy constraints)
	Pt D	Transmit power for data messages (GeRaF)
		and RTS messages (BOSS)
	Pt C	Transmit power for control packets
	Pt BT	Transmit power on the busy tone
	P Rx	Power consumed when in receive state
	Pn	Noise power
	a i	Area of the ith forwarding slice, i = 1, . . . , 2N
	Tp	Data packet duration
	Tc	Minimum control packet duration
	Ts	Duration of a forwarding slot
	N	Number of forwarding subareas
	n T	Number of data packet transmissions (GeRaF-MRC)
	γ	Instantaneous SINR
	γt C	Detection threshold, control packet
	γt D	Detection threshold, data packet
	hn	Fading coefficient of the nth multipath
	R	Communication range
	λ	Wavelength
	α	Path loss coefficient
	ρ	Network node density
	ǫ	Sleeping duty cycle
	η	Number of cycles elapsing without a CTS response
	me	Number of slots elapsing without a CTS response
	mn	Number of slots required to resolve a collision
	x	Random offset from the beginning of the control slot
		(applicable to BOSS)
	PPA	Positive progress area
	NPA	Negative progress area
	potential relays lying within the sender's coverage zone enter
	into a time-based contention phase. Some protocols such as
	GeRaF, BLR, IGF, CBF, MACRO, and CCMR exclude nodes
	in the NPA right away. Others such as BOSS and CoopGeo
	may revert to those nodes at a later stage in the relay selection
	process. Each potential relay triggers a timer whose expiry
	depends on a certain cost function. The first node to have its
	timer expire will transmit a clear-to-send (CTS) message on
	the next available time slot. However, since time is slotted it
	is probable that collisions may occur. A secondary collision
	resolution phase may be devised in this case.

TABLE II RELAY

 II SELECTION AND PACKET FORWARDING PROCESS IN GERAF-MRC

				η empty cycles
	Activity, y	Duration, ty	Node(s)	Avg. count, ny	Task	Power Factor, pfy
	1	Tc	sender	1	transmit RTS	Pt C
	2	Tc + (N -1)Ts	sender	1	listen and activate	P Rx + Pt BT
					BT while listening
				non-empty cycle
	Activity, y	Duration, ty	Node(s)	Avg. count, ny	Task	Power Factor, pfy
	3 4	Tc Tc	sender awaken nodes in PPA (ζπR 2 -me 1 i=1 a i )ǫρ	transmit RTS receive RTS, activate BT while receiving	Pt C P Rx + Pt BT
	5	meTs	awaken nodes in PPA (ζπR 2 -me i=1 a i )ǫρ	listen in anticipation of a CTS, P Rx + Pt BT activate BT while listening
	6	meTs	sender	1	transmit CONTINUE message in the 1st half of the slot	1 2 Pt C
	7	meTs	sender	1	wait for a CTS response in the 2nd half of the slot,	1 2 Pt C
					activate BT while listening
	8	mnTs	relays in the (N -me -1)th	at least 2	transmit CTS response in the 1st half of the slot,	1 2 Pt C
			forwarding subarea		activate BT while listening
	9	mnTs	sender	1	detect colliding responses	1 2 (Pt C + P Rx + Pt BT )
					in the 1st half of the slot,
					activate BT while listening,
					transmit CONTINUE message
					in the 2nd half of the slot
	10	Tc	successful relay	1	transmit CTS	Pt C
	11	Tc	sender	1	receive CTS, activate BT	P Rx + Pt BT
	12	Tc	sender	1	inform successful relay	Pt C
	13	Tc	successful relay	1	receive selection message,	P Rx + Pt BT
					activate BT meanwhile
				n T data packet transmissions
	Activity, y	Duration, ty	Node(s)	Avg. count, ny	Task	Power Factor, pfy
	14	Tp	sender	1	transmit data payload	Pt D
	15	Tp	selected relay	1	receive packet	P Rx + Pt BT
	16	Tc	selected relay	1	transmit ACK/NACK message	Pt C
	17	Tc	sender	1	receive ACK/NACK message,	P Rx + Pt BT
					activate BT while receiving

TABLE III RELAY

 III SELECTION AND PACKET FORWARDING PROCESS IN BOSS Cycles with Collisions (in case forwarding takes place from the Positive Progress Area) Successful Round (in case forwarding takes place from the Positive Progress Area)

				η Empty Cycles
	Activity, y	Duration, ty	Node(s)	Avg. count, ny	Task	Power Factor, pfy
	1	Tp	sender	1	transmit RTS, payload included	Pt D
	2	2xN Ts	sender	1	listen and activate BT	P Rx + Pt BT
				j NPA Cycles
			(in case forwarding takes place from the Negative Progress Area)
	Activity, y	Duration, ty	Node(s)	Avg. count, ny	Task	Power Factor, pfy
	3	Tp	sender	1	transmit RTS	Pt D
	4	Tp	awaken nodes	ǫρ 2N i=N+1 a i	receive RTS,	P Rx + Pt BT
			in NPA		activate BT while receiving
	5	2xN Ts	awaken nodes	ǫρ 2N i=N+1 a i	transmit CTS messages,	Pt C 2xN
			in NPA		each in its corresponding slot
	6	2xN Ts	sender	1	receive CTS messages,	P Rx + Pt BT
					activate BT meanwhile
	7	Ts	sender	1	select relay	Pt C
	8	Ts	successful relay	1	receive selection message,	P Rx + Pt BT
					activate BT meanwhile
	ή Activity, y Duration, ty Node(s)	Avg. count, ny	Task	Power Factor, pfy
	9 10	Tp Tp	sender awaken nodes in NPA ∪ PPA	1 (πR 2 -me i=1 a i )ǫρ	transmit RTS receive RTS, activate BT while receiving	Pt D P Rx + Pt BT
	11	meTs	awaken nodes in NPA ∪ PPA plus sender	(πR 2 -me i=1 a i )ǫρ + 1	listen in anticipation of a CTS, activate BT while listening	P Rx + Pt BT
	12	Ts	colliding relays	at least 2	send CTS on the same slot	Pt C
	13	Ts	sender	1	attempt to receive the CTS,	P Rx + Pt BT
					activate BT meanwhile
	14	(xN -me -1)Ts	colliding relays	at least 2	listen hoping for ACK from sender,	P Rx + Pt BT
			(assuming other		activate BT meanwhile
			nodes have already
			dropped off)
	Activity, y	Duration, ty	Node(s)	Avg. count, ny	Task	Power Factor, pfy
	15	Tp	sender	1	transmit RTS	Pt D
	16 17 18	Tp meTs Ts	awaken nodes in NPA ∪ PPA awaken nodes in NPA ∪ PPA plus sender successful relay	(πR 2 -me i=1 a i )ǫρ (πR 2 --me i=1 a i )ǫρ + 1 1	receive RTS, activate BT while receiving listen in anticipation of a CTS, activate BT while listening transmit CTS	P Rx + Pt BT P Rx + Pt BT Pt C
	19	Ts	sender	1	receive CTS, activate BT	P Rx + Pt BT
	20	Ts	sender	1	inform successful relay	Pt C
	21	T s	successful relay	1	receive selection message,	P Rx + Pt BT
					activate BT meanwhile

The IEEE 802.15.4-2006 standard actually only supports

kbps. Nevertheless, for the sake of this study we assume higher rates are achievable by means of adapting the MCS.


Ahmed Bader

Senior Member, IEEE Karim Abed-Meraim

Fellow, IEEE Mohamed-Slim Alouini

Optimized Beaconless Geo-Routing for Smart Utility Networks

Keywords: Optimized Beaconless Geo-Routing for Smart Utility Networks Geographical routing, smart utility networks, OFDM

I. INTRODUCTION

T HE IEEE 802.15.4g-2012 standard was ratified in 2012.

It comes as an amendment to the IEEE 802.15.4-2011 standard to address the needs for outdoor low-data-rate Smart Utility Network (SUN) [START_REF]Low-Rate Wireless Personal Area Networks (LR-WPANs) Amendment 3, Physical Layer ([END_REF]. Two alternate physical layer (PHY) options were defined, one of which utilizes a multi-rate orthogonal frequency division multiplexing and is dubbed MR-OFDM. Although the work at the PHY level has been already completed, there is still a need however to complement the 802.15.4g standard with a multihop routing mechanism. To that end, several efforts are taking place including the Routing Protocol for Low Power and Lossy Networks (RPL) [START_REF] Winter | RPL: IPv6 Routing Protocol for Low power and Lossy Networks[END_REF] which was published by the Internet Engineering Task Force (IETF) in 2012. Several academic and industrial entities have participated in authoring this protocol specification.

In this letter, we advocate the use of beaconless multihop geo-routing in conjunction with the 802.15.4g standard. Beaconless geo-routing protocols have indeed emerged as some of the most efficient routing techniques for wireless sensor networks (WSN) [START_REF] Sanchez | Beacon-less geographic routing made practical: Challenges, design guidelines, and protocols[END_REF]. In beaconless geo-routing, candidate relaying nodes contend for forwarding the packet. The sender first issues a Request-To-Send (RTS) message. Candidate relaying nodes get ready to respond with a Clear-To-Send (CTS) message. However, each node weighs its response time according to a desired mix of forwarding attributes (e.g. closeness to destination, residual battery energy, ...). The node with the most favorable attributes should typically In this letter, we actually introduce a simple yet optimized mechanism for relay selection in beaconless geo-routing protocols. As a result we gain significant performance enhancements particularly in terms of energy efficiency over the IETF-RPL protocol.

II. OPTIMIZED BEACONLESS GEO-ROUTING

The optimized geo-routing scheme proposed in this letter makes use of the underlying OFDM PHY of the 802.15.4g specification to achieve the minimum forwarding delay. Our proposed scheme. The main contribution is in the design of the CTS message. The idea here is to shift the contention process from the time domain to the frequency domain. One whole OFDM symbol composed of an ensemble of v subcarriers is allocated specifically for this purpose. The IEEE 802.15.4g standard specifies 4 values for v (equivalent to the sixe of the FFT block): 16, 32, 64, and 128. The optimized relay selection process operates as follows (and is further illustrated in Figure 1):

1) The sender issues a RTS message, which -at minimumincludes the position information of the sender and the destination. As illustrated in Figure 1, nodes may fall in the positive progress area (PPA) or the negative progress area (NPA). Those in the PPA will become candidate relaying nodes. 2) Each candidate relaying node compares its position to those of the sender and the destination. Accordingly, it determines in which forwarding zone it falls. 3) Each candidate relaying node is required to modulate one of the v subcarriers allocated in the CTS message.

The larger the progress a node offers towards the destination, the higher the subcarrier index it will select to modulate. Each node makes its subcarrier selection decision locally, i.e. without reverting to any sort of coordination with other candidate relaying nodes. 4) Candidate relaying nodes concurrently transmit the CTS composite frame as illustrated in Figure 1. 5) The sender performs non-coherent energy detection on the output of the FFT block of that allocated OFDM symbol to detect which subcarriers have been energized.

A decision threshold is used on each subcarrier output to judge whether this subcarrier contains only noise or has been actually illuminated by one of the candidate relaying nodes. 6) The sender then transmits the data packet and uses a specific field to indicate the highest subcarrier index noted in the previous step.

1530-437X © 2013 IEEE Fig. 1. The sender transmits a RTS message. The positive progress area (PPA) is sliced into four forwarding zones in this simple example. The CTS message contains a special OFDM response symbol. Each forwarding zone maps into a specific subcarrier. Candidate relaying node C will illuminate the 4th subcarrier since it offers the best positive progress towards the destination.

7) The candidate relaying node which has illuminated that subcarrier will receive the packet. All other nodes will go back to idle state. There is an important consideration here. This is related to the case of two candidate relaying nodes having the more or less the same forwarding attributes, and thus selecting the same subcarrier index. In classical beaconless geo-routing, this would have mandated the design of a collision-resolution mechanism. The probability of such a situation was derived neatly in [START_REF] Zorzi | Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Energy and latency performance[END_REF]. It can be straightforwardly shown that this probability is negligibly small for FFT sizes greater than 32. As a matter of fact, we argue that there is no need for a collision-resolution mechanism in our case here. If two or more nodes happen to forward the packet concurrently, their transmissions can be simply regarded as artificial multipath. As such, the packet can still be received intact by the nodes of the next hop. The cyclic prefix in the 802.15.4g standard is 24 µs. This is in fact the amount of delay spread a receiver can handle. The excess path length corresponding to 24 µs of delay spread is as high as 7.2 km. By all means, this is much larger than the separation between two candidate relaying nodes.

III. PERFORMANCE EVALUATION

We have simulated the end-to-end energy performance of the optimized geo-routing protocol against RPL. A total of 6000, 8000, and 10 000 smart meters respectively were distributed according to a Poisson Point Process (PPP) over an area of 1 × 1 km. This corresponds to a typical dense residential area. Performance was studied in terms of the distance from the smart meter to the sink. We have embarked on an application with a moderate traffic intensity such as Automated Demand Response (ADR) [START_REF] Patel | Assessing communications technology options for smart grid applications[END_REF]. We have followed the strategy of rebuilding the neighbor list every time a message is exchanged between two neighbors as described in [START_REF] Watteyne | Implementation of gradient routing in wireless sensor networks[END_REF]. In this example, we have assumed that forwarding in the geo-routing protocol is done solely on position-based criteria. The average reference communication range is 100 meters.

Results are depicted in Figure 2. In the case of RPL, it is worthwhile noting that the overhead induced by neighbor discovery messages and link metric updates accumulates as the packet traverses the network towards the sink. This drives RPL to consume more energy compared to the optimized I).

IV. CONCLUSION

In this letter, we have introduced a simple PHY-based method aimed at minimizing the forwarding delay in beaconless geo-routing protocols. The method can be applied in conjunction with the MR-OFDM specification of the IEEE 802.15.4g standard for Smart Utility Networks. The performance enhancement obtained through this PHY-based method makes the optimized geo-routing protocol a strong candidate for a layer-2 routing solution in SUNs.

Fig. 2 .

 2 Fig. 2. of energy consumed in IETF-ROLL with respect to optimized beaconless geo-routing as function of distance from sink.