{'fraction_non_alphanumeric': 0.028527518970319854, 'fraction_numerical': 0.005811161271731822, 'mean_word_length': 4.865633802816902, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
QoS-aware Opportunistic Routing with Directional Antennas in Cognitive Radio Sensor Networks

In this paper, a directional antenna based opportunistic routing (DAOR) scheme is proposed for cognitive radio sensor networks (CRSNs) with QoS assurances and energy efficient design. Specifically, based on the investigation and understanding about how directional antenna operation affects spectrum access and route selection, a joint optimization problem is formulated. After dividing angular domain into multiple antenna sectors with fixed beamwidth and direction, an approximate strategy is presented to determine the antenna sector and transmission channel. With obtained antenna and channel parameters, a heuristic algorithm is further designed to construct prioritized permutation of forwarding candidates, aimed at reducing computational complexity while approaching the optimal solution. Simulation results demonstrate that DAOR outperforms existing QoS routing schemes in terms of QoS provisioning and energy efficiency.


Introduction
Most existing wireless sensor networks (WSNs) operate in the 2.4 GHz industrial, scientific and medical (ISM) bands. However, with the growing proliferation of wireless devices, these unlicensed bands are increasingly getting congested, making WSNs suffer from heavy interference, poor QoS performance and energy inefficiency. Moreover, the licensed spectrum usage, such as in the 400-700 MHz band, is temporally and geographically under-utilized for transmission. Cognitive radio sensor networks (CRSNs) [1,2] has emerged as a promising solution to alleviate the spectrum congestion and improve the spectrum utilization, where sensor nodes equipped with cognitive radio can change their transmission frequency and make use of vacant licensed spectrum for communication in an opportunistic manner [3,4].
The critical issue in CRSNs is the exploration of spectrum access opportunities and preventing harmful interference to primary users (PUs) transmissions as PUs have the priority to access the licensed spectrum. Some preliminary works on cognitive routing have been proposed in CRSNs for joint channel assignment and route establishment [5,6]. But these research efforts are mostly based on omnidirectional antennas and target temporal spectrum reuse. One possibility to increase the gain of CRSNs is to leverage spatial reuse. Directional antenna is a way to achieve spatial reuse, which can further reduce the interference to PUs as well as improving the spectrum utilization and QoS performance [7][8][9].
By leveraging multiple potential forwarders, opportunistic routing (OR) significantly improves the performance of wireless networks. Nevertheless, such a way of using directional antennas to increase the spectrum utilization comes with its own challenges of opportunistic routing design in that different choices of antenna parameters may result in different paths and available channels [9,10]. To improve the network performance, many factors, including the channel availability, link quality and antenna parameters, must be taken into consideration for energy-efficient QoS routing design in CRSNs with directional antennas.
In this paper, we propose a directional antenna based opportunistic routing for CRSNs in consideration of QoS assurances and energy efficiency. The main contributions can be concluded as follows: (i) a joint optimization problem regarding the selection of antenna parameters, data channels and forwarding candidates is formulated. (ii) to reduce computational complexity, a problem approximation framework is presented for the antenna sector and channel selection. With the chosen antenna sector and data channel, a heuristic algorithm is designed to construct a prioritized forwarder list of candidate nodes. (iii) simulation results demonstrate the effectiveness and superiority of the proposed DAOR compared with conventional routing schemes.
The remainder of this paper is organized as follows. The system model is introduced in Section II. Section III describes and formulates the joint optimization problem regarding opportunistic routing and directional antenna operation. A complexity-adjustable algorithm design is proposed to determine the antenna sector, data channel and forwarder list in Section IV, followed by performance evaluation in Section V. Concluding remarks are given in Section VI.

Antenna Model
Consider a multi-hop CRSN, where sensor nodes are equipped with smart antenna systems that provide two modes of operation: Directional and Omni. The Omni mode is mainly used for reception and in the Directional mode, sensor nodes can only select one beam for data transmission. The main lobe of a directional antenna beam is modeled as a sector with radius r, beamwidth θ and direction φ. The antenna gain is G=2π/θ, where 0≤θ≤2π. Assume that a node transmits with power P t . Then, the receiving power at the receiver denoted by P r can be calculated by 10 10 t t r r where l is the distance between two nodes, G t and G r are antenna gains of a transmitter and a receiver, respectively. α∈ [2,6] is the path loss exponent. The shadow fading effect is modeled as log-normal random variable ω with zero mean and standard deviation σ. In practice, the quality of signal transmission is usually measured by power attenuation ∆= P t / P r , which is fixed at a given threshold Δ t in this work. According to (1), we have the directional transmission distance r as shown in (2), where G t =G and G r =1.
Especially, when G t =G r =1, we have the omnidirectional transmission distance = ( ∆ 10 /10 ) 1/ . It can be seen that directional antenna can extend the transmission range by ( 2 ) 1/ compared with omnidirectional antenna.

Network Model
Assume that there is a set of data channels M in the network that are licensed to PUs, whose activities are unknown. Sensor nodes can opportunistically access idle channels without interfering with PUs' communications. A fixed common control channel (CCC) is considered to be available to exchange the control information. When a source node communicates with a destination node, it first senses for a spectrum access opportunity and then selects a forwarding node in the detected idle channel. In this work, a set of neighbor nodes could be selected as forwarding candidates with a certain priority.
According to the practical transmission situation, each node opportunistically selects its relay node from multiple candidates. With GPS or other available localization services, cognitive sensor nodes can acquire their own location information.
Due to the randomness of PU activities, the channel availability may differ between the spectrum sensing phase and data transmission phase. To characterize dynamics of channel availability, we model the occupation time of PUs in each channel as an independent and exponentially distributed alternating ON/OFF random process [6,11]. The ON state indicates that the channel is occupied by PUs, whereas the OFF state implies that the channel is idle. Let exponential random variables Z m and . A larger m off q indicates that m is better and more suitable for data transmission. Considering that the channel availability on each antenna sector for each node is dynamic, we extend the PU activity model to each sector and use , , i m q ϕ θ to indicate the probability that node v i detects channel m available on the antenna sector with direction φ and beamwidth θ.

Joint Optimization Problem
In this section, we explain the proposed DAOR in detail. We first give the problem description of route selection. Then, we show the link criterion and energy model. Finally, we give the local reliability and delay requirements.

Problem Formulation
Before sending data, the antenna sector, transmission channel and forwarding candidates must be determined, which is different from traditional OR. Each node distributedly selects these items with the objective of minimizing energy consumption and satisfying QoS requirements. Without loss of generality, we consider both delay and reliability requirements in this strategy. It is impossible to obtain the exact state of an end-to-end route in real-time due to dynamics of wireless links. Thus, we partition end-to-end QoS requirements into one-hop QoS requirements.
Denoted T i and R i as the local delay and reliability requirements of v i for single-hop forwarding. The directional neighbors of v i on the antenna sector with φ and θ is defined as Ω i (φ,θ). Let F i m (φ,θ)={v 1 , v 2 ,…v n } as an ordered forwarder list of v i on the corresponding sector and channel m, where |F i m (φ,θ)|=n and m∈M∧F i m (φ,θ)⊆Ω i (φ,θ). Then, the optimal solution is formulated as follows.
Node v i selects the local optimal channel m * , antenna direction φ * , beamwidth θ * and the corresponding forwarder list F i m* (φ * ,θ * ), where the objective corresponding to (3) is to minimize energy consumption under delay and reliability requirements. Constraints (4) and (5) represent the local reliability and delay requirements for opportunistic forwarding using F i m (φ,θ).

Link Criterion
Denote (x i ,y i ) and (x j ,y j ) as the geographical coordinates of v i and v j whose Euclidian distance and angel [12] are is not greater than r and the included angle does not exceed the beam boundary, i.e. |φ-β|≤θ/2, then v j falls within the signal coverage area of v i , denoted as v j ∈Ω i (φ,θ).
In CRSNs, link criterion depends not only on the transmission region but also on the channel availability. Nodes v i and v j are connected if and only if the following two conditions are satisfied. First, v i and v j fall into the transmission area of each other, i.e. v i and v j are mutual neighbors. Second, both v i and v j have the available channel, which means that there are no active PUs in their transmission region.

Energy Consumption
Suppose that v i transmits L bits of data over a distance l to v j . According to the energy consumption model in [13], the energy consumption for data transmission can be expressed as where E elec is the energy needed by the transceiver circuitry to transmit or receive one bit, ε amp is power consumption of the amplifier, and α is the path loss exponent. Considering the packet loss during data transmission, v j may just receive To be energy efficient, we assume that nodes only listen to the transmission intended to themselves. To examine the impact of PU activities on nodes' communications, the expected cognitive energy consumption is defined in (9), where the energy consumption for channel sensing and accessing [11], i.e., e s and e a , is taken into consideration.

Local Reliability Guarantee
In this work, packet delivery ratio, the percentage of packets successfully delivered to the destination, is used to evaluate reliability. If each hop on a route provides the same level of reliability, the local required packet delivery ratio for v i to select forwarding candidates can be estimated as where R i,s is the reliability requirement from v i to the destination s and H i is the estimated hop count, given by Equation (11) consists of i d , which represents the mean single-hop advancement from the source to v i . The expected delivery ratio R(F i m (φ,θ)) is defined as the probability that a packet transmitted by v i on channel m is successfully received by at least one node in F i m (φ,θ). Since the loss of a packet at different receivers occurs independently in practice, it can be calculated as

Local Delay Guarantee
In our model, at each hop, the sending node first senses for a spectrum access opportunity and transmits data in the detected idle channel. After receiving data packets, candidate nodes, sorted in a given prioritized order, reply an ACK message in a sequence. If the sender receives ACK at the first time, it broadcasts a Complete To Receive (CTR) message on CCC to notice other candidates with lower priority that the sender has received ACK. If v j ∈F i m (φ,θ) is the j-th forwarding candidate, the delay of v j , denoted as t i,j , is defined as where t S is sensing delay and t DATA is data transmission delay. Equation (13) consists of t W , which represents the duration of waiting for sending ACK message after receiving the packet, t W =j·(2μ+t ACK +t CTR ), where μ is the short frame interval, t ACK is the delay for transmitting an ACK and t CTR is that for transmitting a CTR message. The delay requirement is essentially the spatiotemporal constraint for packet migrating. A geographic based mechanism is used to estimate the local delay requirement in (4) by limiting the packet advance speed, as shown in (14) and (15), where T i,s is the delay requirement from v i to s.
Given F i m (φ,θ), the expected single-hop advancement, denoted by A(F i m (φ,θ)), and the expected relay delay, denoted by T(F i m (φ,θ)), are defined as where a i,j represents the advancement from v i to v j (given by a i,j = d(v i ,s)-d(v j ,s)) and ,0 m i p is equal to 0.

Complexity-Adjustable Algorithm Design
Theoretically, the space of both antenna direction and beamwidth is continuous, so there will be an infinite number of antenna sectors. But it is impractical to design such a complicated antenna system in reality and to perform an exhaustive search under each sector to find the optimal solution. To simplify the issue, we divide the angular domain into N antenna sectors with fixed beamwidth and direction. Each sector spans an angle of θ=2π/N. The direction set is denoted by Φ={φ 1 , φ 2 , …φ N }, where φ k =φ 1 +(k-1)·2π/N. Because the beamwidth is fixed for each node, only the sector direction has yet to be determined. Given N optional sectors, a straightforward way to get the optimal forwarder list is to search all possible combinations of data channels, antenna sectors and the ordered subset of neighbor nodes. For |M|=C and |Ω i (φ,θ)|=n, there are choices. It is, however, not feasible for energy and processing capability constrained CRSNs especially when N, C or n becomes very large. Thus, it is essential to design an effective approximation scheme to get suboptimal solution while significantly reducing computational burden. The optimization problem is decomposed into two phases. One is to determine the forwarding sector and transmission channel. The other is to construct a forwarder list with the least energy consumption while satisfying QoS requirements under the selected antenna sector and data channel.

Selection of Antenna Sector and Data Channel
It is possible to accelerate packet advance speed and reduce transmission delay if the antenna sector that points to the destination is chosen. However, selecting an antenna sector only based on the direction could not provide a guarantee of higher channel availability, which may result in link failure and increase the number of retransmission. Moreover, if we simply follow the principle of maximizing channel quality, longer paths and delays are very likely to occur.
To sum up, the selection of a better antenna sector depends not only on its direction but also on the channel availability detected on that sector. So we design a joint sector-channel selection scheme, with the objective of reducing transmission cost as much as possible while providing channel availability guarantee. The optimization problem of selecting both forwarding sector and data channel is formulated as follows.
Given a random variable X with mean μ and variance σ 2 , according to one-sided Chebyshev's inequality, it satisfies Applying the Chebyshev's inequality on (22), we get With such a probabilistic guarantee policy, many unnecessary searches can be filtered out by reasonably adjusting λ.

Heuristic Algorithm for Forwarder List Construction
With selected antenna sector and data channel, the next step is to choose forwarding candidates and assign priority. According to [14], the expected advancement will be maximized if the priority is assigned based on the single-hop advancement. The expected transmission delay will be reduced if the priority is assigned according to the packet delivery ratio. Considering that under the dynamic wireless link, further transmission distance would lead to lower packet reception rate. A tradeoff strategy is to use , , as a metric for priority assignment. To obtain the optimal forwarder list, the most direct way is to perform an exhaustive search. But it is not suitable for sensor nodes to run such an algorithm with high computational complexity. Moreover, it is unrealistic for a forwarder list to contain too many nodes as energy consumption and coordination delay may increase with the growing number of candidate nodes. Thus, a heuristic algorithm is designed to construct a forwarder list, where neighbors with higher priority are preferentially chosen and no more candidates need to be chosen if QoS requirements are met.  15) and repeat above traversal process from the remaining neighbor nodes until there are no nodes to be selected or a forwarder list that satisfies QoS requirements is constructed.

Performance Evaluation
We set up a CRSN with multiple sensor nodes randomly distributed in a 500m×500m area, whose omnidirectional transmission distance is set to be 80m. Assume that there are six data channels and PU activity in each channel is modeled as an exponentially distributed ON/OFF process. The data channel rate is 1 Mbps and packet size is 256 bytes. The maximum number of candidates h is 4, probabilistic guarantee λ is 0.5 and delay threshold is 1s. For performance comparison, we choose DTQOR [15], which is based on omnidirectional antenna, as a baseline and extend its capabilities in terms of spectrum sensing and dynamic channel access. The performance evaluation of DAOR is conducted in terms of reception ratio within deadline and energy consumption under the given QoS constraints. To improve the accuracy of results, each experiment is run for 300 times to calculate the average. Fig.1 depicts the effect of node density, where reception ratio of DAOR is much higher than that of DTQOR. Especially when node number is less than 380, DTQOR cannot meet reliability requirement, i.e., 0.9. With the equivalent transmission power, transmission distance of omnidirectional antennas is much smaller than that of directional antennas, resulting in a larger hop count and higher single-hop reliability requirement. It is difficult to provide QoS guarantee especially under the situation of fewer available candidates. From Fig.2, we can see that the energy consumption of DAOR maintains at a lower level compared with DTQOR. Moreover, the more the antenna sectors are, the smaller the energy consumption is. The utilization of directional antennas helps to expand the transmission distance, and the narrower the antenna beam is, the further signals can reach. This reduces the number of packet forwarding and total energy consumption.

Impact of Reliability Requirement
The effect of reliability requirement on packet reception ratio is investigated in Fig.3. Despite the increasing demand for reliability, packet reception ratios of both two cases of DAOR can still meet the reliability requirement and always keep a higher value. On the contrary, DTQOR can only meet a lower reliability requirement rather than a higher requirement over a threshold of 0.8. This lies in that the utilization of omnidirectional antennas for data transmission increases hop count and degrades route stability.  Figure 3 Impact of reliability requirement on reception ratio Figure 4 Impact of reliability requirement on energy consumption Fig.4 illustrates the relation between energy consumption and reliability requirement. As is shown from the diagram that, average energy consumption shows a slight increase when the reliability requirement changes from 0.75 to 0.95. In order to ensure a higher reliability requirement, more candidates may be selected to construct a forwarder list, which takes additional energy consumption for data reception. However, the energy consumption in two cases of DAOR is still far less than that of DTQOR, which results from the benefit of hop count decreasing.

Conclusion
A directional antenna based opportunistic routing (DAOR) strategy is designed for energy-efficient CRSNs with QoS assurances. Depending on the impact of directional antenna operation on spectrum access and route selection, a joint selection problem in terms of antenna sectors, transmission channels and forwarder list is presented. And then, an efficient approximation framework and heuristic algorithm are designed to reduce computational complexity while approaching the optimal solution. Simulation results demonstrate that compared with omnidirectional QoS routing, DAOR achieves significant performance improvement in terms of QoS provisioning and energy efficiency.