Sage Journals: Discover world-class research

Abstract

Cognitive radio–based vehicular ad hoc networks can solve the problem of limited spectrum resource and growing vehicular communication service demands in intelligent transportation systems, and thus, it receives much concern recently. In cognitive radio–based vehicular ad hoc networks, the high mobility of vehicles and the dynamic spectrum activity of cognitive radio make routing in such networks a great challenge. Some routing researches have been proposed in cognitive radio–based vehicular ad hoc networks with single-objective optimization and neglecting the nodes’ social behaviors which can improve the network performance. From this perspective, we propose a social-aware routing scheme for cognitive radio–based vehicular ad hoc networks, with the purpose of increasing the packet delivery ratio and decreasing the overhead ratio. First, we analyze the social centrality of primary users to offer an accuracy spectrum hole measurement. Moreover, we develop a social community partition algorithm to divide secondary users into intra-community and inter-community groups. Furthermore, considering the tradeoff between the packet delivery ratio and the overhead ratio, we adopt different replication policies and forwarding ranks in different community communication processes. In the intra-community communication process, we employ the single-copy policy and the contact duration rank. In the inter-community communication process, we utilize the optimized-binary-tree replication policy and the bridge coefficient rank. Simulation results show that our social-aware routing scheme achieves the higher package delivery ratio and the lower overhead ratio when compared with the existing cognitive radio–based vehicular ad hoc networks routing schemes and other standard routing schemes.

Keywords

Cognitive radio vehicular ad hoc networks social awareness routing scheme

Introduction

In intelligent transportation system (ITS), the US Federal Communications Commission (FCC) has allocated 75 MHz of spectrum in 5.9 GHz band for the deployment of ITS services.¹ Nevertheless, a significant rise in vehicular applications, especially in urban environments, leads to an overcrowding of the band and spectrum scarcity for vehicular communications in vehicular ad hoc networks (VANETs).² In order to increase the utilization of unused or underused licensed bands, such as spectrum bands for TV broadcasting, the FCC has opened the licensed bands to secondary users (SUs) through the cognitive radio (CR) technology. In cognitive radio–based vehicular ad hoc networks (CR-VANETs), vehicles (also be referred as SUs) can opportunistically access the licensed spectrum band and avoid interfering with primary users (PUs).³ The CR-VANETs offer an efficient utilization of the radio spectrum and a highly reliable vehicular communication network.⁴

In CR-VANETs, some researches on the physical or media access control (MAC) layer have been proposed.^5–7 They have demonstrated that their methods can guarantee the correctness and timeliness of CR channel detection in CR-VANETs and improve the spectrum efficiency. However, routing is a crucial issue that bottlenecks the performance of the entire network and has not been widely studied in CR-VANETs. Different from traditional CR scenarios, existing routing solutions for cognitive radio ad hoc networks (CRAHNs) and VANETs^8,9 cannot apply to CR-VANETs, due to the mobility characteristic of vehicles and the dynamic spectrum nature of the CR environment.

Currently, some preliminary routing researches on CR-VANETs have been proposed in previous works,^10–12 which were designed for a fully interconnected environment, aiming to improve the end-to-end delay or the path duration. We have also proposed a delay tolerant routing scheme to improve the packet delivery ratio of CR-VANETs.¹³ Different from these researches, in this article, we utilize the social characteristics which are relatively stable and less volatile than the spectrum changing and node mobility features in CR-VANETs. We design an efficient social-aware routing scheme which can improve the packet delivery ratio as well as reduce the overhead ratio. Moreover, recent social-aware solutions designed for CRAHNs or VANETs^14,15 cannot be directly applied to CR-VANETs for two reasons. On one hand, considering vehicle’s mobility and wireless communication features but neglecting the vehicles’ social behaviors cannot achieve the satisfactory performance, due to the continuously changing topologies, fluctuation of node densities, and the short connection lifetime. On the other hand, without considering the social pattern of PUs, the inaccurate estimation of ON/OFF channel-usage patterns based on local spectrum knowledge may lead to sub-optimal routing decisions.

In this article, we propose a social-aware routing scheme considering the social characteristics of both PUs and SUs in CR-VANETs. In order to improve the accuracy of spectrum holes measurement, we utilize the social centrality to evaluate the PUs’ active probability instead of the traditional ON/OFF channel-usage patterns. Furthermore, since the social features of community can contribute to the routing decision, we separate the SUs into intra-community groups and inter-community groups. According to these social characteristics, we execute different replication policies and forwarding ranks in the routing scheme. For the purpose of increasing packet delivery ratio and decreasing overhead ratio, we adopt the single-copy policy and the contact duration rank in the intra-community communication process. We employ the optimized-binary-tree replication policy and the bridge coefficient rank in the inter-community communication process. The contributions of our work can be summarized as follows:

We utilize the social centrality to evaluate the active probability of PUs and then obtain the accurate CR channel availability probability of SUs.

We propose a social community partition algorithm that takes account of the correlation between encountering and geographic location. It dynamically separates SUs into intra-community groups and inter-community groups.

We apply different strategies to different community communication processes for the tradeoff between the packet delivery ratio and the overhead ratio. For the intra-community communication process, we utilize the single-copy policy and implement the contact duration as a forwarding rank.

For the inter-community communication process, we develop an optimized-binary-tree replication algorithm which can replicate packets and terminate the replication quickly, and we implement the bridge coefficient to evaluate candidates of bridge nodes.

The rest of the paper is organized as follows. Section “Related work” presents a concise review of existing related work. Section “System model and problem statement” describes the system model. Section “Social characteristics of CR-VANETs” analytically evaluates the social characteristics of CR-VANETs. Section “The social-aware routing scheme” proposes the social-aware routing scheme in details. Simulation results are presented in section “Performance evaluation.” The final section is “Conclusion.”

Related work

Routing research for CR networks

J Wang et al.¹⁶ propose a spectrum-aware anypath routing scheme with consideration of both the salient spectrum uncertainty feature of CR networks and the unreliable transmission characteristics of the wireless medium. They design the anypath routing metric based on channel and link statistics to accurately estimate and evaluate the quality under the uncertain spectrum availability. X Tang et al.¹⁷ propose a network-coding-based geographic segmented opportunistic routing scheme for CRAHNs. In their scheme, the whole path from the source to the destination is cut down into several smaller opportunistic route segments, where the packets are transmitted through multiple segments based on a step-by-step forwarding procedure until all the packets are delivered to the destination. A Liu et al.¹⁸ propose an opportunistic pipeline routing scheme that nodes employ high duty cycle in the area far from the sink and low duty cycle in the area near to the sink. It can achieve the balance of energy consumption and reduce the data transmission delay while not affecting network lifetime. A Guirguis et al.¹⁹ propose a PU-aware k-hop routing scheme where $k$ is the discovery radius. It is based on balancing the routing overhead and the route optimality, in terms of PUs avoidance, according to a user-defined utility function.

These routing schemes provide some approaches to choose paths in CR networks. However, they cannot be applied to CR-VANETs. On one hand, it needs to consider how to select available CR channels for the vehicle-to-vehicle communication, which is a dynamic object and different from the traditional static CR networks. On the other hand, the high mobility of vehicles results in highly dynamic network topology, which may lead to the available CR spectrum out of date.

Routing research for VANETs

In VANETs, D Lin et al.²⁰ design a moving-zone-based architecture in which vehicles collaborate with one another to form dynamic moving zones so as to facilitate information dissemination. Their approach introduces moving object modeling and indexing techniques from the theory of large moving object databases into the design of VANETs routing protocols. G Sun et al.²¹ build a routing graph based on the trajectories of bus lines by analyzing the probability of bus appearing on every street. It aims to choose the best path with the higher density of busses and lower probability of transmission direction deviating from the routing path. YRB Al-Mayouf et al.²² provide a geographic routing in VANETs by considering the traffic segment status when choosing the next intersection. A verity period mechanism which is used to minimize the communication overhead also be proposed to denote the projected period when a network failure is likely to occur in a particular segment. Y Tang et al.²³ propose a mobility prediction–based routing scheme to ensure reliable and timely transmissions in VANETs. They employ the software defined network (SDN) controller to predict the vehicle arrivals and vehicle connections, and the artificial neural network to learn and predict the vehicle arrival rate.

These routing schemes are designed for VANETs. Nevertheless, they are not appropriate for CR-VANETs. For the reason that they do not consider not only the temporal variations of PUs but also the spatiotemporal changes of CR channels, which need to be taken into account during the vehicle-to-vehicle communication.

Social-aware forwarding research for CR networks and vehicle networks

J Lu et al.²⁴ propose a spectrum-aware routing, including accessible whitespace and routing convergence. They consider the available whitespace determined by primary activities and the competitions based on secondary activities. X Zhong et al.²⁵ propose an energy and trust-aware opportunistic routing in CR social Internet of things, which jointly considers energy efferent, trust, and social feature. They exploit a new routing metric for selecting forwarding candidates and use network coding for the data transmission between trust nodes. L Zhu et al.²⁶ propose a privacy-preserving interest-based forwarding scheme for social Internet of vehicles. A privacy-preserving authentication protocol is used to recognize communities among mobile nodes, and new metric community energy is also introduced to indicate vehicular social proximity. W Qu et al.²⁷ exploit a social pattern prediction model in order to enhance the stability of clusters. The predicted social patterns are subsequently used to create clusters so that vehicles in the same cluster tend to share the same routes.

These social-aware forwarding schemes all focus on the social characteristics of SUs or vehicles. Different from these schemes, we analyze the social characteristics of both PUs and SUs in our scheme. Moreover, the evaluation of SUs’ social characteristics in our method is distinct from theirs.

Routing research for CR-VANETs

W Kim et al.¹⁰ propose an anypath routing protocol for CR-VANETs. They utilize both sensed channel information and geographical location to establish minimum delay routes to the destination. An expect path duration maximized routing algorithm for CR-VANETs is proposed by J Liu et al.,¹¹ where each vehicle selects the route with the maximum expected path duration among all attainable paths. Abedi and Bemaninejad¹² allow nodes to collect spectrum information during a spectrum management interval followed by a transmission period. They propose a forwarding strategy to avoid performance degradation due to the overhead by considering mobility parameters of cognitive users. We proposed a delay tolerant routing scheme for CR-VANETs,¹³ with the objective of packet delivery ratio improvement but without considering the overhead ratio optimization.

Different from these routing schemes in CR-VANETs, in this article, we bring a social-aware perspective into the routing scheme. According to the social centrality of PUs as well as the social community partition of SUs, we improve not only the accuracy of the CR availability probability but also the efficiency of the relay path in CR-VANETs. In addition, our objective is to maximize the packet delivery ratio and minimize the overhead ratio, which is different from these routing schemes.

System model and problem statement

Urban street model

A grid-like street layout, like Houston or Manhattan area, is shown in Figure 1. The network geometry comprises a set of $J$ horizontal roads which are intersected with $J$ vertical roads. Each road segment is associated with vehicle traffic. The border effects can be eliminated by the wrap-around conditions of the grid. The overall area can be normalized as a square area with a size of $Z$ . We denote $\bar{A_{d}}$ as the average vehicle density in the grid and assume the spatial distribution of vehicles is inhomogeneous in each road segment.

Figure 1.

A grid-like street layout.

Remark

$J$ and $\bar{A_{d}}$ characterize the scale of the grid. Thus, the grid-like street model with different values of $J$ and $\bar{A_{d}}$ can indicate different scales of urban scenarios from the small town to metropolitan areas.

CR spectrum model

In an overlay CR system, the spectrum bands not occupied by PUs are identified in temporal and spatial domains such that each SU can utilize the spectrum holes. We assume that there are $M$ PUs with the $λ$ Poisson distribution in the network. The transmission and interference ranges of PUs are denoted as $R$ and $R_{I}$ , respectively. Considering the high mobility of vehicles, we regard PUs as in a relatively fixed location. Accordingly, the PUs can be modeled as a graph

\begin{matrix} G_{P} = (V_{P}, E_{P}), V_{P} = {{P U_{i}} | 1 \leq i \leq M} \end{matrix}

(1)

where $V_{P}$ is the node set and $E_{P}$ indicates all the possible links between the nodes in $V_{P}$ . We assume the PU network is dense scaling as

\begin{matrix} \sqrt{Z} \times \sqrt{\frac{\log M}{M}} = O (1) \end{matrix}

(2)

where $Z$ is the square size. We assume that $N$ SUs (vehicles) are randomly deployed in the grid. The transmission and interference ranges of SUs are denoted as $r$ and $r_{I}$ , respectively. We denote $D (S U_{i}, S U_{j})$ as the Euclidean distance between $S U_{i}$ and $S U_{j}$ .

Remark

For the $S U_{i}$ and $S U_{j}$ that satisfy the $D (S U_{i}, S U_{j}) \leq r$ , if no PU is receiving in the coverage of $S U_{i}$ with radius $r_{I}$ , denoted as $Ω$ $(S U_{i}, r_{I})$ , and no PU is transmitting in the coverage of $S U_{j}$ with radius $R_{I}$ , denoted as $Ω$ $(S U_{j}, R_{I})$ , there is a spectrum opportunity exists from $S U_{i}$ to $S U_{j}$ . Such spectrum opportunity existing from $S U_{i}$ to $S U_{j}$ does not imply a spectrum opportunity from $S U_{j}$ to $S U_{i}$ . Hence, it is asymmetric.

Vehicle contact model

We assume that each vehicle (SU) is equipped with spectrum sensing terminals and GPS devices. We can obtain the moving direction, velocity, and geographical location of vehicles from the GPS and digital map. We denote vehicles $S U_{i}$ and $S U_{j}$ , $i, j \in [1, N]$ , are moving at velocities $v_{i} (t)$ and $v_{j} (t)$ , respectively. The relative velocity of these two vehicles is denoted as $v_{ij} (t)$ . When $S U_{j}$ comes within the communication coverage of $S U_{i}$ at time $t_{c}$ , that is

\begin{matrix} {∥ t_{c}^{-} \times v_{j} (t_{c}^{-}) - t_{c}^{-} v_{i} (t_{c}^{-}) ∥ > r} \cap \\ {∥ t_{c} \times v_{j} (t_{c}) - t_{c} \times v_{i} (t_{c}) ∥ = r} \end{matrix}

(3)

where $t_{c}^{-}$ denotes the time before $t_{c}$ , and $r$ is the transmission range of SUs.

The contact duration of two vehicles can be defined as the time during that $S U_{j}$ is in contact with $S U_{i}$ before $S U_{j}$ moving out of the communication coverage, that is

\begin{matrix} T_{S U_{i}, S U_{j}} = t_{c}^{+} - t_{c}, mi n_{t_{c}^{+} - t_{c}} {t : ∥ t \times v_{ij} (t_{c}) ∥ > r} \end{matrix}

(4)

where $t_{c}^{+}$ denotes the time after $t_{c}$ . The $S U_{i}$ is regarded as a stationary node, and $S U_{j}$ is moving with velocity $v_{ij} (t_{c})$ . The contact duration $T_{S U_{i}, S U_{j}}$ indicates the communication quality of different vehicle pairs.

Problem statement

The social-aware routing scheme is a social-aware data transmit and relay (SADTR) process. We denote $D_{pkt}$ as the packet delivery ratio. Considering the objective of maximizing the packet delivery ratio, we need to find an optimal routing scheme to achieve the target. We denote this routing scheme as $R^{*}$ . According to the $R^{*}$ , the proper relay operation will be executed, based on the social characteristics of PUs and SUs. The relay nodes try their best to forward packets to the destination to improve the packet delivery ratio.

In our routing scheme, we implement a strategic replication policy to increase the packet delivery ratio. Nevertheless, the contact duration between the vehicle to vehicle and the buffer capacity of each vehicle is limited. The numerous replications will cause high storage, high consumption of bandwidth, and high delivery overhead. Thus, we need to decrease the packet replication as far as possible and reduce the overhead ratio.

We formulate this target as follows and list the notations in Table 1

\begin{matrix} \max D_{pkt} \Leftrightarrow \exists R^{*} = \sum_{i = 1}^{N} (μ_{i} \times S U_{i}) \end{matrix}

(5)

Table 1.

Notations.

Notation	Description
$Z$	The size of the square area
$M$	The number of PUs
$N$	The number of SUs
$r$	The transmission range of SUs
$T_{S U_{i}, S U_{j}}$	Contact duration between $S U_{i}$ and $S U_{j}$
$R^{*}$	The optimal SADTR scheme
$D_{pkt}$	The packet delivery ratio
$P_{t} (k)$	The replicas of packet $k$
$K$	The number of packets
$μ_{i}$	A binary variable, $μ_{i} \in {0, 1}$
$ζ_{i}$	The available buffer capacity of $S U_{i}$
$B_{TH}$	The buffer size for all packets

PU: primary user; SU: secondary user; SADTR: social-aware data transmit and relay.

$s . t .$

\begin{matrix} \min \sum_{k \in K} P_{t} (k) \end{matrix}

(6)

\begin{matrix} \sum_{i = 1}^{N} (μ_{i} \times ζ_{i}) \leq B_{TH} \end{matrix}

(7)

where $N$ is the number of SUs and $μ_{i}$ is a binary variable that indicates whether $S U_{i}$ is a relay node including in $R^{*}$ or not.

$K$ is the number of packets. We consider $P_{t} (k)$ as the replicas of packet $k$ . $\min \sum_{k \in K} P_{t} (k)$ indicates the minimum overhead caused by the number of forwarding packets before they reach the destination. We denote $ζ_{i}$ as the available buffer capacity of $S U_{i}$ . The constraint $\sum_{i = 1}^{N} (μ_{i} \times ζ_{i}) \leq B_{TH}$ represents the upper bound of buffer size $B_{TH}$ for all packets, which also restricts the overhead ratio.

This routing problem can be considered as a transformative 0-1 knapsack problem, which is known to be NP-complete. In the following sections, we will use the two words “SU” and “vehicle” interchangeably, and the same for “packet” and “message.”

Social characteristics of CR-VANETs

In this section, we analyze the social characteristics of both PUs and SUs in CR-VANETs. Due to the prerequisite of CR spectrum holes for SUs in CR-VANETs, we use the social centrality to evaluate the PUs’ active probability. This measurement can improve the accuracy of the spectrum holes measurement by comparing with the ON/OFF channel-usage patterns based on local spectrum knowledge. Moreover, we also propose a social community partition algorithm that neither reply on empirical threshold values nor ignore community evolutions. It dynamically separates relay candidates into intra-community groups and inter-community groups. It can benefit to the routing decision for the reason that the same community is more likely to have the same route features.

Social centrality of PUs

In CR-VANETs, the network topology of PUs is relatively static. In PUs’ graph $G_{P} = (V_{P}, E_{P})$ , the PU in the center PUs network is more likely to relay data for other communication flows. It is busier and more crucial than other PUs. Accordingly, the spectrum hole of this central PU is less than other PUs,’ even though they have the same interference range and data generation rate. Consequently, instead of considering the activity distributions of PUs as homogeneous over time, we analyze the spectrum hole by exploiting the social pattern of PUs’ activities, which can improve the accuracy of the spectrum hole estimation.

In a graph, the centrality of a node is defined as the number of the shortest paths passing this node.²⁸ Similarly, for a PU, we measure the social centrality by the number of shortest data transmission paths passing the PU.

We denote the social centrality of $P U_{i}$ as $σ_{i}$ . We denote a centrality weight as $φ_{i}$ , which indicates how active $P U_{i}$ is in the whole PUs network. We calculate $φ_{i}$ as follows

\begin{matrix} φ_{i} = \frac{ε}{\bar{P_{s}}} \times \frac{σ_{i}}{S_{pth}} \end{matrix}

(8)

where $ε$ is the expected number of active PUs, $\bar{P_{s}}$ is the average number of PUs on all the shortest paths, and $S_{pth}$ is the number of all the shortest paths in the PUs network. $(ε / \bar{P_{s}}) \times (1 / S_{pth})$ indicates the weight of the PU’s activity on each of the shortest paths. The PU with a higher social centrality $σ_{i}$ has a higher active weight $φ_{i}$ . This PU is more likely to relay data for other traffic flows besides its own traffic.

Remark

We define the “shortest path” based on the number of hops from a source to a destination. Generally, the “shortest path” can also be defined based on some other metrics by assigning different weights on primary links. The social centrality definition of PUs is universal.

We assume that PUs’ social activity pattern follows the independent and identical distribution of $T (p)$ , where $p$ is the probability of a PU to be active in the time slot $τ$ . The expected number of active PUs during each time slot is

\begin{matrix} ε = M \times p \end{matrix}

(9)

where $M$ is the number of PUs and we assume $M \geq 2$ . Accordingly, we formulate the weight of $P U_{i}$ activity as follows

\begin{matrix} φ_{i}^{T} = \frac{M \times p}{\bar{P_{s}}} \times \frac{σ_{i}}{S_{pth}} \end{matrix}

(10)

In the PUs network, the active probability of $P U_{i}$ under the activity pattern $T (p)$ can be approximated as follows

\begin{matrix} p_{i}^{T} = \max {p, \min {1, φ_{i}^{T}}} \end{matrix}

(11)

The $p_{i}^{T}$ indicates whether $P U_{i}$ takes many forwarding tasks or just takes its own traffic. Consequently, we employ $p_{i}^{T}$ to represent the active probability of $P U_{i}$ and deduce the spectrum hole for SUs. It is more accurate than the ON/OFF channel-usage patterns.

We assume that an available CR spectrum hole exists from $S U_{i}$ to $S U_{j}$ . The network area, in which $P U_{i}$ is inactive, covered by $S U_{i}$ and $S U_{j}$ is that

\begin{matrix} Z_{ij} = Ω (S U_{i}, r_{I}) \cup Ω (S U_{j}, R_{I}) \end{matrix}

(12)

The CR channel from $S U_{i}$ to $S U_{j}$ is with the availability probability

\begin{matrix} P = \underset{P U_{i} \in Z_{ij}}{Π} (1 - p_{i}^{T}) \end{matrix}

(13)

Accordingly, in time slot $τ$ , the available CR spectrum hole for the communication from $S U_{i}$ to $S U_{j}$ is

\begin{matrix} H_{ij}^{τ} (T (p)) = W \times \underset{P U_{i} \in Z_{ij}}{Π} (1 - p_{i}^{T}) \end{matrix}

(14)

where $W$ is the bandwidth of PU. $W$ is an abstract CR spectrum bandwidth. It can be extended to the multiple spectrum bands scenario by applying it to each spectrum band individually.

We denote $S_{pth} (i, j)$ as the shortest path between $P U_{i}$ and $P U_{j}$ and denote $L_{i, j}$ as the number of PUs on $S_{pth} (i, j)$ . The maximum number of PUs on a shortest path is

\begin{matrix} L = \max {L_{i, j} | P U_{i}, P U_{j} \in V_{P}} \end{matrix}

(15)

We can deduce the upper bound and lower bound of $p_{i}^{T}$ and have Theorem 1.

Theorem 1

We assume there are $M$ PUs acting in the social pattern of independent and identical distribution of $T (p)$ , where $p$ is the probability of a PU to be active in the time slot $τ$ . The upper bound of $p_{i}^{T}$ is $p_{\max}^{T} = \max {p, min {1, Mp / 2}}$ , and the lower bound of $p_{i}^{T}$ is $p_{\min}^{T} = \max {p, min {1, \max {2 p / L, p \log M / M}}}$

Proof

For the dense scaling of the PU network, we can obtain that $Z = cM / \log M$ , where $Z$ is the square size and $c$ is an user-defined constant. Considering the extreme case of the star topology of PUs, if $P U_{i}$ is the star center, the expected number of active PUs is $ε = \log M$ , where $M$ is the number of PUs. Substituting equation (15) into equation (10), we can obtain $φ_{\max}^{T} = Mp / 2$ and $φ_{\min}^{T} = \max {2 p / L, p \log M / M}$ . Substituting these $φ_{\max}^{T}$ and $φ_{\min}^{T}$ into equation (11), we can obtain the upper bound of $p_{i}^{T}$ , that is $p_{\max}^{T} = \max {p, min {1, Mp / 2}}$ , and the lower bound of $p_{i}^{T}$ , that is $p_{\min}^{T} = \max {p, min {1, \max {2 p / L, p \log M / M}}}$ .

Social community partition of SUs

A community is usually regarded as a group of nodes with more internal connections than external connections in social relationships. SUs in the same community are more likely to have the same destination or longer contact duration, which will contribute to the relay selection. However, the community structure will be updated when there is a new community or a merger of two existing communities. To deal with this situation, for high mobility SUs, we propose a social community partition algorithm. It dynamically distributes SUs into intra-community groups and inter-community groups. For relay candidates in different communities, we employ different routing strategies.

The social community partition algorithm takes account of the correlation between encountering and geographic location. It dynamically runs while each encounter is occurring in the network. Therefore, the community structure will change from time to time and will be maintained dynamically.

In the initialization, we assume that $n$ SUs are assigned with a unique community ID randomly. Other SUs without community ties will choose one community through encounters until all the SUs are assigned with a community ID.

After this process, there are $n$ communities in the network. Each SU counts their tie parameters and then adjusts their community ties according to the latest tie parameters. The tie parameter indicates the encounter number of SUs in different communities; it is

\begin{matrix} Q = {Q_{i α} | (1 \leq i \leq N, 1 \leq α \leq η)} \end{matrix}

(16)

where $N$ is the number of SUs, and $η$ is the number of communities. When $S U_{i}$ encounters another SU node in the community $α$ , it updates $Q_{i α}$ and changes its community tie to the value of $\max {Q}$ adaptively. The overhead of one community conversion is stated in Theorem 2.

Theorem 2

There are $m$ SUs in community $X$ and $n$ SUs in community $Y$ , respectively. If $S U_{i}$ in community $X$ needs to convert its community to $Y$ , the communication overhead for one community conversion is $O (m + 2 n)$ .

Proof

We assume the transmission overhead of one community ID as 1. If there are $k$ encounters between community $X$ and $Y$ , the overhead for transmitting the community ID of $S U_{i}$ is $k$ . The overhead for flooding and remaining the community ID of $S U_{i}$ in $X$ is $m - k$ . The overhead for obtaining community members is $n$ . The overhead for flooding community ID and making others in the community $Y$ to be aware of $S U_{i}$ is $n$ . Therefore, the communication overhead for one community conversion is $O (m + 2 n)$ .

Algorithm 1 gives the details of social community partition algorithm. Steps 1–6 give the initialization process. The SUs without community ties will choose one community through encounters until all the SUs are assigned with a community ID. From steps 7 to 15, each SU counts their tie parameters and updates $Q_{i α}$ , then changes its community tie to the $\max {Q}$ .

Algorithm 1. Social community partition.
Input: the tie parameter of $S U_{i}$ Output: the community ID of $S U_{i}$ 1: for $S U_{i}$ encounters $S U_{j}$ do 2: if community ID of $S U_{i}$ is NULL then 3: $S U_{i} . ID$ = $S U_{j} . ID$ ; 4: else 5: $x = S U_{i} . ID$ ; 6: $y = S U_{j} . ID$ ; 7: if $x$ = $y$ then 8: $Q_{ix} = Q_{ix} + 1$ ; 9: else 10: $Q_{iy} = Q_{iy} + 1$ ; 11: end if 12: if $Q_{ix} > Q_{iy}$ then 13: $S U_{i} . ID = x$ ; 14: else 15: $S U_{i} . ID = y$ ; 16: end if 17: end if 18: end for

Algorithm 1. Social community partition.

Input: the tie parameter of

S U_{i}

Output: the community ID of

S U_{i}

1: for

S U_{i}

encounters

S U_{j}

do
2: if community ID of

S U_{i}

is NULL then
3:

S U_{i} . ID

S U_{j} . ID

;
4: else
5:

x = S U_{i} . ID

;
6:

y = S U_{j} . ID

;
7: if

x

y

then
8:

Q_{ix} = Q_{ix} + 1

;
9: else
10:

Q_{iy} = Q_{iy} + 1

;
11: end if
12: if

Q_{ix} > Q_{iy}

then
13:

S U_{i} . ID = x

;
14: else
15:

S U_{i} . ID = y

;
16: end if
17: end if
18: end for

Each SU is assigned to a community ID to indicate the same social community members. In the one-hop relay process, if the transmission node and reception node have the same community ID, they are in the intra-community group. If they have different community IDs, they are in the inter-community group. In order to achieve high packet delivery ratio and low overhead ratio, we execute different routing strategies to different kinds of community group.

The social-aware routing scheme

In this section, we introduce (1) the SADTR architecture that explains the relationship between the components; the SADTR scheme includes (2) replicating phase and (3) forwarding phase. Different replication policies and relay ranks will be executed in different social community communication processes. In the SADTR scheme, packets transmit based on the CR spectrum hole, packet replications are responsible for delivery improvement, and social characteristics contribute to the relay candidates selection.

The SADTR architecture

Figure 2 shows the architecture of the SADTR scheme that consists of two phases: replicating phase and forwarding phase. Social characteristics of both PUs and SUs are functional prerequisites of the SADTR scheme.

Figure 2.

Architecture of the SADTR scheme.

We exploit the social centrality to evaluate the PUs’ active probability and to improve the accuracy of the spectrum holes measurement. We also employ the social community to divide SUs into the intra-community groups and inter-community groups, in order to improve routing performance. The forwarding phase is built with the consideration of spectrum holes and social communities of SUs. The replicating phase is established with two distinctive replication policies to deal with different SUs social community communication processes.

Replicating phase

Considering the tradeoff between the packet delivery ratio and the overhead ratio, we adopt a single-copy policy for intra-community transmissions and an optimized-binary-tree replication algorithm for inter-community communications. A hybrid drop mechanism which combines with the drop-oldest and drop-most strategies is also applied to reduce the overhead ratio.

Forwarding phase

It contains a contact duration unit and a bridge coefficient unit. Both of these are relay ranks for different social community communication processes, and for proper routing path selection. We utilize the contact duration in the intra-community communication process and the weighted bridge coefficient in the inter-community communication process.

Replicating phase

In the transmission process, we can increase the packet replicas to improve the packet delivery ratio. Usually, the more replicas of a packet indicate not only the higher packet delivery ratio but also the higher overhead ratio. Considering the tradeoff between the packet delivery ratio and the overhead ratio, and the social community similarity, we employ a single-copy policy in intra-community transmission to reduce the packet replicas. In inter-community communication process, we apply a multi-copy method, which is specifically described as the optimized-binary-tree replication algorithm, to improve the packet delivery ratio. A hybrid package drop mechanism is also implemented to further reduce the overhead ratio.

The optimized-binary-tree replication algorithm can replicate packets and terminate the replication quickly. In this algorithm, if $S U_{i}$ is responsible for creating $n$ replicas, $S U_{i}$ will send a copy when it meets the relay node $S U_{j}$ . It also entitles $S U_{j}$ to be responsible for half of its remaining replicas, that is, $⌈ n - 1 / 2 ⌉$ replicas, and itself is responsible for the other $⌊ n - 1 / 2 ⌋$ replicas. Each replication node conducts the same operation according to the binary-tree branch until the leaf node has no more replicas.

Figure 3 shows an example of the optimized-binary-tree replication algorithm. The number in a solid line circle represents the number of replicas that a node should create. The number in a dotted line circle represents the number of remaining replicas in a node. We use $T S_{i}$ to denote the time step in which a replication node replicates a packet to a non-replication node. Assume that node $V_{1}$ is responsible for creating $n = 12$ replicas. It entitles the first meeting node $V_{2}$ to create $⌈ n - 1 / 2 ⌉ = 6$ replicas at $T S_{1}$ and keeps the responsibility to create the remaining $⌊ n - 1 / 2 ⌋ = 5$ replicas to itself. At $T S_{2}$ , node $V_{1}$ entitles the second meeting node $V_{4}$ to create $⌈ (⌊ n - 1 / 2 ⌋ - 1) / 2 ⌉ = 2$ replicas. At the same $T S_{2}$ , node $V_{2}$ entitles its meeting node $V_{3}$ to create $⌈ (⌈ n - 1 / 2 ⌉ - 1) / 2 ⌉ = 3$ replicas, and itself is responsible for the remaining $⌊ (⌈ n - 1 / 2 ⌉ - 1) / 2 ⌋ = 2$ replicas. Then in $T S_{3}$ , nodes $V_{2}$ , $V_{3}$ , and $V_{4}$ entitle their next meeting nodes with half of their remaining replication. The node $V_{1}$ no longer makes replicas after it has owned two replication leaf nodes. This process repeats binary branching until every node completes its replicating task.

Figure 3.

Optimized-binary-tree for $n = 12$ .

The optimized-binary-tree replication algorithm costs $O (\underset{2}{\log} n)$ time steps to replicate $n$ copies and terminates the replication process quickly. It performs better than the source-tree replication algorithm and the binary-tree replication algorithm. In the source-tree replication algorithm, only a source node can create a replica to others when it meets a new node.²⁹ It costs $O (n)$ time steps to create $n$ replicas. In the binary-tree replication algorithm, each node can only create a replica to two other nodes.²⁹ It costs $O (\underset{2}{\log} n)$ time steps for replicating $n$ copies. Although the binary-tree replication algorithm has the same replication time steps as the optimized-binary-tree replication algorithm, the former’s $T S_{i}$ step is more than the latter one. Furthermore, the binary-tree replication algorithm cannot terminate the replication process even $n$ replicas have been generated.

Considering the overhead ratio reduction, we apply a hybrid drop mechanism to deal with the redundant packages. This mechanism is combined with the drop-oldest and drop-most strategies. The drop-oldest strategy is commonly used in delay tolerant networks, which prefers to discard the packet with the least remaining lifetime. Another one is the drop-most strategy, which prefers to discard the packet with the maximum replicas.

Proposition 1

In a time slot $τ$ , dropping the packet with maximum replicas will lead to the minimum impact of delivering it to the destination.

Proof

Assume that in a time slot $τ$ , the replication numbers of packet $ξ_{i}$ and packet $ξ_{j}$ are $β_{i}$ and $β_{j}$ , respectively. If $β_{i} > β_{j}$ , the number of SUs who carry packet $ξ_{i}$ is more than the number of SUs who carry packet $ξ_{j}$ . It means that the distribution of packet $ξ_{i}$ is more widely than packet $ξ_{j}$ . Thus, the packet $ξ_{i}$ is more likely to arrive at destination for next hop than packet $ξ_{j}$ . Hence, dropping packet $ξ_{i}$ will cause the less impact than dropping packet $ξ_{j}$ .

For the limitation of buffer size of SUs, we implement the hybrid drop mechanism if the available buffer capability of the receiver is not enough. Otherwise, the packet will be received except its replica has already reached the maximum number. The replicas of the delivered packets will be deleted in order to free the buffer space for undelivered packets.

Forwarding phase

In a routing scheme, forwarding candidate set and their forwarding order should be carefully selected such that the packet delivery ratio is maximized. In particular, exploring bridge nodes locating between different communities as relay nodes not only helps quick dissemination of packets far away from the original community, but also shortens the transmission hops between source and destination. According to the social community groups, within the available CR spectrum hole, we execute two different ranks in the forwarding phase. In the intra-community communication process, we utilize the contact duration to rank the relay nodes. In the inter-community communication process, we apply a bridge coefficient to rank the relay candidates.

Contact duration

We have formulated the contact duration in equation (4). In the intra-community communication process, it is clear that the candidate with longer contact duration is more likely to accomplish the transmission process.

Bridge coefficient

We provide the bridge coefficient to evaluate the bridge node in the inter-community communication process. Usually, communities are interconnected by edges or common nodes that are served as bridges for the community-to-community communications.

It is well accepted that bridging centrality is an efficient metric to measure how well a node is located between connected communities. Hwang et al.³⁰ propose a bridging centrality with the assumption that all links are of the same strength. Their computation of bridging centrality takes time of $O (n^{3})$ , where $n$ is the node number of the network.

However, in CR-VANETs, the links between SUs are different strength. We still utilize the contact duration to measure the link strength between the SUs. Since the longer contact duration implies the node could transmit more packets. Consequently, we formulate the bridge coefficient that combines the bridging centrality with the contact duration of SUs.

We assume node $S U_{i}$ can serve as the bridge node. We denote the intra-community node set of $S U_{i}$ as $X_{i}$ , and its direct neighbor node set as $Y_{i}$ . The bridge coefficient $B_{co} (i)$ of node $S U_{i}$ is

\begin{matrix} B_{co} (i) = \frac{ϑ {(i)}^{- 1}}{\sum_{j \in Y_{i}} ϑ {(j)}^{- 1}} \end{matrix}

(17)

where $ϑ (i)$ is the weighted degree of $S U_{i}$ calculated as

\begin{matrix} ϑ (i) = \sum_{i \neq j \in X_{i}} δ_{ij} \times T_{S U_{i}, S U_{j}} \end{matrix}

(18)

$δ_{ij}$ in equation (18) is a binary variable that indicates whether $S U_{i}$ and $S U_{j}$ can connect in the social communities or not.

The bridge coefficient $B_{co} (i)$ is determined by the contact duration of $S U_{i}$ and its neighbors in the social communities. By comparing our bridge coefficient with the bridging centrality in Hwang et al.,³⁰ we achieve a lower time complexity of $O (n^{2})$ , where $n$ is the node number of the social community.

Theorem 3

The SADTR scheme has a loop-free route from a source node to a destination node.

Proof

Considering the movement patterns of the SUs in CR-VANETs, the contact duration between each pair of nodes will converge to a stable value, which can statistically reflect the communication capacity between two SUs. Since the SADTR scheme adopts a unidirectional packet routing strategy, that is, a packet is always forwarded to the SU with higher contact duration rank. Thus, the routing loop will not occur in the SADTR scheme.

A packet from a source node is initially replicated to a number of different relay nodes. In the intra-community communication process, we employ the single replication policy and apply the contact duration to rank the relay candidates. In the inter-community communication process, we exploit the optimized-binary-tree replication policy and apply the bridge coefficient to rank the relay candidates. A hybrid mechanism combined with the drop-oldest and drop-most strategies is also implemented to reduce the overhead ratio. This overall process will repeat until one replica arrives at the destination node, and all replicas of this delivered packet will be deleted in order to free the buffer space.

The detailed steps of this routing scheme are shown in Algorithm 2. Steps 1 and 2 are the redundant packet deletion process. All replicas of the delivered packet will be deleted. From steps 4 and 5, a hybrid package drop mechanism is applied to reduce the overhead ratio. From steps 7 to 9, the single replication policy and contact duration measurement are adopted to the intra-community relay candidates. From steps 11 to 13, the optimized-binary-tree replication policy and bridge coefficient are employed to the inter-community relay candidates.

Algorithm 2. SADTR scheme.
Input: concurrent forwarding set $ω_{τ}$ ; contact duration $T_{S U_{i}, S U_{j}}$ ; bridge coefficient $B_{co} (i)$ Output: optimal routing paths $R^{*}$ 1: if packet $ξ_{i}$ has been sent to destination then 2: delete all the replicas of $ξ_{i}$ . 3: else 4: if cache data ≥ buffer constraint $B_{TH}$ then 5: hybrid package drop mechanism; 6: else 7: for all intra-community relay candidates do 8: $relay = \max {T_{S U_{i}, S U_{j}}}$ ; 9: single replication; 10: end for 11: for all inter-community relay candidates do 12: $relay = \max {B_{co} (i)}$ ; 13: optimized-binary-tree replication; 14: end for 15: end if 16: end if

Algorithm 2. SADTR scheme.

Input: concurrent forwarding set

ω_{τ}

; contact duration

T_{S U_{i}, S U_{j}}

; bridge coefficient

B_{co} (i)

Output: optimal routing paths

R^{*}

1: if packet

ξ_{i}

has been sent to destination then
2: delete all the replicas of

ξ_{i}

.
3: else
4: if cache data ≥ buffer constraint

B_{TH}

then
5: hybrid package drop mechanism;
6: else
7: for all intra-community relay candidates do
8:

relay = \max {T_{S U_{i}, S U_{j}}}

;
9: single replication;
10: end for
11: for all inter-community relay candidates do
12:

relay = \max {B_{co} (i)}

;
13: optimized-binary-tree replication;
14: end for
15: end if
16: end if

Performance evaluation

Simulation setup

We evaluate the SADTR scheme with an omni-directional antenna model and an overlay CR spectrum scenario. We consider the PU numbers of 30, 40, and 50. They are Poisson distributed in a square area of size $Z = 5 km \times 5 km$ . The PU bandwidth is normalized to $W = 2 MHz$ . Each PU accesses its channel with the hidden Markov model (HMM) rule,³¹ that is, $p (0 / 0) = 0.95$ , $p (1 / 0) = 0.05$ ; $p (0 / 1) = 0.10$ , $p (1 / 1) = 0.90$ , where $p (1 / 0)$ is the probability that PU changes its state from idle $(0)$ to busy $(1)$ .

In the simulation, the vehicles are considered as the SUs. Each vehicle is equipped with CR-based wireless communication devices within the communication range of 300 m. The vehicles are randomly distributed on the road with different densities from 0.05 to 0.3 veh/m which represent the relatively sparse and dense networks. The velocity of vehicles ranges randomly from 10 to 60 km/h. Vehicles travel at their constant speeds and do not interact with one another. Each simulation iteration process uses the same movement pattern.

The NS-2 simulator runs with IEEE 802.11p in the MAC layer. The transmission pattern consists of 512-byte packets and adopts constant bit rate (CBR) data bursts with a max of 40 Kbps. Simulations were repeated 20 times for each metric and each routing scheme at each vehicle density. We adopted the 95% confidence interval for the mean of our simulation results. The simulation parameters are given in Table 2.

Table 2.

Simulation parameters.

Parameter	Value
Grid size	$5 km \times 5 km$
Number of PUs	$30, 40, 50$
Bandwidth of PU	$2 MHz$
PU active probability	HMM rule
Vehicle density	$0.05 - 0.3 veh / m$
Vehicle velocity	$10 - 60 km / h$
Transmission range	$300 m$
MAC protocol	IEEE 802.11p
Packet size	$512 bytes$
Traffic CBR	$4 - 40 Kbps$
Simulation runs	$20 times per metric$
Confidence interval	$95 %$

PU: primary user; IEEE: Institute of Electrical and Electronics Engineers; CBR: constant bit rate; HMM: hidden Markov model; MAC: media access control.

We employ the metrics including the packet delivery ratio (delivery ratio for short), the overhead ratio, and the average delay to evaluate the efficiency of routing schemes:

Delivery ratio: the ratio of the number of delivered packets to the number of generated packets.

Overhead ratio: the ratio of the number of forwarded packets except delivered packets to the number of delivered packets.

Average delay: the average time for delivering a packet to its destination over the network.

Simulation results

In this section, we (1) evaluate the performance of the SADTR; (2) make comparisons with four CR-VANETs routing schemes: CoRoute,¹⁰ EPDMR,¹¹ SSR,¹² and DTR;¹³ (3) make comparisons with three routing schemes: a social-aware routing of Bubble Rap,³² a copy-forward routing of Spray and Wait,³³ and a benchmark routing of Epidemic.³⁴

We have introduced these CR-VANETs routing schemes^10–13 in related works. The Bubble Rap³² is a community-based social routing strategy. It depends on a community structure and routes data based on the social centrality. Spray and Wait³³ is a copy-forward-based routing scheme in delay tolerant networks. Epidemic³⁴ is a flooding strategy routing scheme. It considers all participants in the same way, without including any information to guide routing decisions.

Figure 4 shows the delivery ratio of the SADTR with different CR channel bandwidth requirements, different packet time to live (TTL) thresholds, different buffer sizes, and different PU numbers under different vehicle densities. In Figure 4(a), with the extra bandwidth of the CR spectrum, the delivery ratio increases significantly due to the release of congestions over the dedicated short-range communication channel. Furthermore, the more idle channels are obtained from CR, the higher reliability is achieved.

Figure 4.

Delivery ratio of the SADTR: (a) different CR channel bandwidths, (b) different TTL thresholds, (c) different buffer sizes, and (d) different PU numbers.

The delivery ratio in various TTL thresholds is shown in Figure 4(b). When the TTL is 5 min, the delivery ratio decreased evidently. It means that if the TTL is less than a transmission threshold, the packet will be dropped when it is timeout or dropped by the drop-oldest strategy. Accompanied with a decreasing TTL value, the packet remaining lifetime is also decreased. It is a critical factor for the drop-oldest strategy to decide whether to discard a packet. If the TTL is above the transmission threshold, 10 min, the delivery ratio will not be affected by the TTL and the drop-oldest strategy severely.

The delivery ratio with different buffer sizes is shown in Figure 4(c). The buffer size indicates the upper bound for all packets. As shown in the figure, the delivery ratio is not obviously changed until the buffer size is upper 256 MB. It is shown that the replicas of the packet are not limited directly with the increasing value of buffer size. Furthermore, we can conclude that the strategy of drop-most is effective for the delivery ratio.

Figure 4(d) depicts the delivery ratio following the PU numbers of 30, 40, and 50. In this figure, the packet delivery ratio increased while the vehicle density increased. Moreover, the packet delivery ratio decreased while the PU number increased at each vehicle density. The increase of PU number means the higher utility of license channels which leads to the lower availability of idle channels. It results in the lower probability of CR channels access. Thus, the more PU number causes the lower packet delivery ratio.

Considering the parameters in Figure 4, not only CR bandwidth but also TTL and buffer size of a node will affect the delivery ratio. According to the simulation results, we choose the setting value of CR 2 MHz bandwidth, 10 min TTL, 256 MB buffer size, and 30 PUs as the baseline test scenario to compare different routing schemes in the next section. Note that we do not mean that these values are exact threshold values, but just a upper approximation.

Figure 5 shows the comparisons of routing schemes in CR-VANETs in terms of delivery ratio, overhead ratio, and average delay. Figure 5(a) depicts the delivery ratio of five routing schemes. In the sparse network, all the schemes have a low delivery ratio because of the absence of relay nodes. The SADTR performs the best in each density. It is profited by the replication policy. The DTR also performs well. Although the DTR has a replication policy as well, the indiscrimination replicas make the resources allocation unreasonable and massive overhead. CoRoute performs the worse one because of its objective of minimum delivery delay. The EPDMR scheme performs better in dense networks than sparse networks.

Figure 5.

Comparisons with CR-VANETs routing schemes: (a) delivery ratio, (b) overhead ratio, and (c) average delay.

Figure 5(b) displays the overhead ratio of five routing schemes. Because the more vehicles cause more forwarding candidates and replicas, all the routing schemes have upward curves with the increase of node density. The SADTR achieves the lowest overhead ratio in all traces. It is profited by the optimized-binary-tree replication policy, combined with the hybrid packet drop mechanism. Both DTR and CoRoute have a high overhead ratio. The SSR has a great performance for the reason that it adopts an overhead constraint for its route planning.

Figure 5(c) shows the average delay of five routing schemes. All the routing schemes have downward curves with the increase of node density. More vehicles cause more forwarding candidates and chances. The CoRoute performs the best due to its minimum routing delay strategy. The SADTR shows a relative higher latency than the CoRoute. In our scheme, packets are propagated following the optimal paths. Hence, it may miss some shortcuts, with either a shorter geometry distance or fewer vehicle hops to the destination. However, the SADTR still scales better than other routing schemes in high node density.

Figure 6 shows the comparisons of four routing schemes in terms of delivery ratio, overhead ratio, and average delay. Figure 6(a) depicts the delivery ratio of comparing the SADTR to other routing schemes. The SADTR performs a higher delivery ratio than other schemes. All schemes are more sensitive to the increase number of vehicles. Although the Epidemic greedily forwards packets to each encountered node, the miscalculation of the spectrum hole may cause the communication disconnection, interference, and conflicts, following the packet loss. This miscalculation is the same reason for the low delivery ratio of the Bubble Rap and the Spray and Wait.

Figure 6.

Comparisons with three routing schemes: (a) delivery ratio, (b) overhead ratio, and (c) average delay.

Figure 6(b) gives the evaluation results on the overhead ratio of the four routing schemes. The overhead ratio of all routing schemes increases with the increase number of vehicles. It is because that the more vehicles swarm in, the more transmission chance for each packet during a contact, leading to the increase of forwarding number per packet. The SADTR achieves the lowest overhead ratio in all traces. It is profited by the optimized-binary-tree replication policy, combined with the hybrid package drop mechanism. There is no doubt that the Epidemic has the highest overhead ratio due to its flooding nature.

Figure 6(c) shows the average delay of the four routing schemes. The Epidemic performs the better in sparse networks due to its flooding nature. The SADTR scheme performs better than both the Bubble Rap and the Spray and Wait. In the SADTR strategy, packets are propagated following the delivery ratio optimization paths. Thus, it misses some relay nodes with shorter geometry distance.

The results of Figure 6 show that by comparing with the social community-based routing strategy Bubble Rap, the SADTR scheme achieves the higher delivery ratio which benefits from the social-aware CR spectrum channel. Moreover, by comparing with the replication-based routing strategies Epidemic and Spray and Wait, the SADTR scheme achieves the lower overhead ratio which results from the social-aware replicating and forwarding as well as the hybrid package drop mechanism.

In these figures, the standard deviation values are used to indicate the statistical treatment of our simulation results. The standard deviation values in sparse networks are higher than that in dense networks. The main reason is that sparse networks have fewer relay nodes, which result in the more possibilities of unsuccessful relay links and cause the test result variations.

Conclusion

In this article, we proposed a social-aware routing solution for CR-VANETs, to increase the packet delivery ratio and decrease the overhead ratio. Considering the social characteristics of both PUs and SUs, we analyzed the social centrality of PUs to improve the accuracy of spectrum holes measurement for SUs. Moreover, we proposed the social community partition algorithm to separate SUs into intra-community and inter-community groups. For our optimization objective and routing decision improvement, we employed the single-copy policy and contact duration rank in the intra-community communication process, and we implemented the optimized-binary-tree replication algorithm and the bridge coefficient rank in the inter-community communication process. To further reduce the overhead ratio, we adopted a hybrid package drop mechanism which combined with the drop-oldest and the drop-most strategies. Simulation results demonstrated the advantage of the SADTR in the performance of delivery ratio and overhead ratio and indicated the effectiveness of our proposed scheme.

Footnotes

Handling Editor: Rodolfo Meneguette

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This article is supported by the National Natural Science Foundation of China (no. 61772386), the National Key Research and Development Program of China (no. 2018YFB130500), the China Scholarship Council (no. 201806270154), the Fundamental Research Funds for the Central Universities (WUT: 2019III060), and Hubei Key Laboratory of Transportation Internet of Things (Wuhan University of Technology) (no. 2018IOT002).

ORCID iD

Jing Wang

References

Cheng

Henty

Stancil

et al . Mobile vehicle-to-vehicle narrow-band channel measurement and characterization of the 5.9 GHz dedicated short range communication (DSRC) frequency band. IEEE J Select Areas Comm 2007; 25(8): 1501–1516.

Pan

Fang

. Cooperative communication aware link scheduling for cognitive vehicular networks. IEEE J Select Areas Comm 2012; 30(4): 760–768.

Duan

Tang

Zhou

et al . Load balancing opportunistic routing for cognitive radio ad hoc networks. Wireless Comm Mobile Comput 2018; 2018: 9412782.

Singh

Rawat

Bonnin

. Cognitive radio for vehicular ad hoc networks (CR-VANETs): approaches and challenges. EURASIP J Wireless Comm Netw 2014; 2014(1): 49.

Cheng

Zhang

et al . Opportunistic spectrum access for CR-VANETs: a game-theoretic approach. IEEE Trans Vehic Tech 2014; 63(1): 237–251.

Huang

et al . Historical spectrum sensing data mining for cognitive radio enabled vehicular ad-hoc networks. IEEE Trans Depend Secure Comput 2016; 13(1): 59–70.

Han

Ekici

Kremo

et al . Throughput-efficient channel allocation algorithms in multi-channel cognitive vehicular networks. IEEE Trans Wireless Comm 2017; 16(2): 757–770.

Tang

. Joint rate adaptation, channel assignment and routing to maximize social welfare in multi-hop cognitive radio networks. IEEE Trans Wireless Comm 2017; 16(4): 2097–2110.

Qureshi

Abdullah

Lloret

. Road perception based geographical routing protocol for vehicular ad hoc networks. Int J Distribut Sens Netw 2016; 12(2): 2617480.

10.

Kim

Gerla

et al . CoRoute: a new cognitive anypath vehicular routing protocol. Wireless Comm Mobile Comput 2011; 11(12): 1588–1602.

11.

Liu

Ren

Xue

et al . Expected path duration maximized routing algorithm in CR-VANETs. In: 2012 1st IEEE international conference on communications in China (ICCC), Beijing, China, 15–17 August 2012, pp.659–663. New York: IEEE.

12.

Abedi

Bemaninejad

. Soft and stable routing protocol for cognitive radio VANETs considering cognitive users mobility. In: 2015 11th International Conference on Innovations in Information Technology (IIT), Dubai, United Arab Emirates, 1–3 November 2015, pp.116–121. New York: IEEE.

13.

Wang

Zhang

Tang

. Delay tolerant routing for cognitive radio vehicular ad hoc networks. In: 2016 IEEE 22nd international conference on parallel and distributed systems (ICPADS), Wuhan, China, 13–16 December 2016, pp.24–31. New York: IEEE.

14.

Eryigit

Bayhan

Kangasharju

et al . Optimal cooperator set selection in social cognitive radio networks. IEEE Trans Vehic Tech 2016; 65(8): 6432–6443.

15.

Huang

Zhang

. RSUs placement based on vehicular social mobility in VANETs. In: Proceedings of the 13th IEEE conference on industrial electronics and applications (ICIEA), Wuhan, China, 31 May–2 June 2018, pp.1255–1260. New York: IEEE.

16.

Wang

Yue

Hai

et al . Spectrum-aware anypath routing in multi-hop cognitive radio networks. IEEE Trans Mobile Comp 2017; 16(4): 1176–1187.

17.

Tang

Zhou

Xiong

et al . Geographic segmented opportunistic routing in cognitive radio ad hoc networks using network coding. IEEE Access 2018; 6: 62766–62783.

18.

Liu

Chen

Liu

. Delay optimal opportunistic pipeline routing scheme for cognitive radio sensor networks. Int J Distribut Sensor Netw 2018; 14(4): 1550147 718772532.

19.

Guirguis

Digham

Seddik

et al . Primary user-aware optimal discovery routing for cognitive radio networks. IEEE Trans Mobile Comp 2019; 18(1): 193–206.

20.

Lin

Kang

Squicciarini

et al . Mozo: a moving zone based routing protocol using pure V2V communication in VANETs. IEEE Trans Mobile Comp 2017; 16(5): 1357–1370.

21.

Sun

Zhang

Liao

et al . Bus-trajectory-based street-centric routing for message delivery in urban vehicular ad hoc networks. IEEE Trans Vehic Tech 2018; 67(8): 7550–7563.

22.

Al-Mayouf

YRB

Abdullah

Mahdi

et al . Real-time intersection-based segment aware routing algorithm for urban vehicular networks. IEEE Trans Intell Transport Syst 2018; 19(7): 2125–2141.

23.

Tang

Cheng

et al . Delay-minimization routing for heterogeneous VANETs with machine learning based mobility prediction. IEEE Trans Vehic Tech 2019; 68(4): 3967–3979.

24.

Cai

Wang

et al . Primary and secondary social activity aware routing for cognitive radio networks. In: 2016 international conference on identification, information and knowledge in the Internet of Things (IIKI), Beijing, China, 20–21 October 2016, pp.311–316. New York: IEEE.

25.

Zhong

et al . ETOR: energy and trust aware opportunistic routing in cognitive radio social internet of things. In: GLOBECOM 2017 IEEE global communications conference, Singapore, 4–8 December 2017, pp.1–6. New York: IEEE.

26.

Zhu

Zhang

et al . PRIF: a privacy-preserving interest-based forwarding scheme for social internet of vehicles. IEEE Internet of Things J 2018; 5(4): 2457–2466.

27.

Song

Wang

et al . SDN-enabled social-aware clustering in 5G-VANET systems. IEEE Access 2018; 6: 28213–28224.

28.

Cai

Han

et al . Whitespace measurement and virtual backbone construction for cognitive radio networks: from the social perspective. In: 2015 12th annual IEEE international conference on sensing, communication, and networking (SECON), Seattle, WA, 22–25 June 2015, pp.435–443. New York: IEEE.

29.

Small

Haas

. Resource and performance tradeoffs in delay-tolerant wireless networks. In: Proceedings of the 2005 ACM SIGCOMM workshop on delay-tolerant networking (WDTN ’05), pp.260–267. New York: ACM, http://chants.cs.ucsb.edu/2005/papers/paper-SmaHaa.pdf

30.

Hwang

Kim

Ramanathan

et al . Bridging centrality: graph mining from element level to group level. In: Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining (KDD ’08), Las Vegas, NV, 24–27 August 2008, pp.366–344. New York: ACM.

31.

Huang

Wang

. Multitask spectrum sensing in cognitive radio networks via spatiotemporal data mining. IEEE Trans Vehic Tech 2013; 62(2): 809–823.

32.

Hui

Crowcroft

Yoneki

. BUBBLE Rap: social-based forwarding in delay-tolerant networks. IEEE Trans Mobile Comp 2011; 10(11): 1576–1589.

33.

Spyropoulos

Psounis

Raghavendra

. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In: Proceedings of the 2005 ACM SIGCOMM workshop on delay-tolerant networking (WDTN ’05), Philadelphia, PA, 26 August 2005, pp.252–259. New York: ACM.

34.

Vadhat

Becker

. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, Durham, NC, 2000.

Social-aware routing for cognitive radio–based vehicular ad hoc networks

Abstract

Keywords

Introduction

Related work

Routing research for CR networks

Routing research for VANETs

Social-aware forwarding research for CR networks and vehicle networks

Routing research for CR-VANETs

System model and problem statement

Urban street model

Remark

CR spectrum model

Remark

Vehicle contact model

Problem statement

Social characteristics of CR-VANETs

Social centrality of PUs

Remark

Theorem 1

Proof

Social community partition of SUs

Theorem 2

Proof

The social-aware routing scheme

The SADTR architecture

Replicating phase

Forwarding phase

Replicating phase

Proposition 1

Proof

Forwarding phase

Contact duration

Bridge coefficient

Theorem 3

Proof

Performance evaluation

Simulation setup

Simulation results

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References