Critique paper on wireless network research paper

DBP-CR.pdf

Home >Computer Science homework help >Critique paper on wireless network research paper

A Distributed Broadcast Protocol in Multi-hop Cognitive Radio Ad Hoc Networks without a Common Control Channel

Yi Song and Jiang Xie Department of Electrical and Computer Engineering

The University of North Carolina at Charlotte Email: {ysong13, Linda.Xie}@uncc.edu

Abstract—Broadcast is an important operation in wireless ad hoc networks where control information is usually propagated as broadcasts for the realization of most networking protocols. In traditional ad hoc networks, since the spectrum availability is uniform, broadcasts are delivered via a common channel which can be heard by all users in a network. However, in cognitive radio (CR) ad hoc networks, different unlicensed users may acquire different available channel sets. This non-uniform spectrum availability imposes special design challenges for broad- casting in CR ad hoc networks. In this paper, a fully-distributed broadcast protocol in multi-hop CR ad hoc networks without a common control channel is proposed. In our design, we consider practical scenarios that each unlicensed user is not assumed to be aware of the global network topology, the spectrum availability information of other users, and time synchronization information. By intelligently downsizing the original available channel set and designing the broadcasting sequences and scheduling schemes, our proposed broadcast protocol can provide very high successful broadcast ratio while achieving the shortest average broadcast delay. It can also eliminate broadcast collisions. To the best of our knowledge, this is the first work that addresses the broadcasting challenges specifically in multi-hop CR ad hoc networks under practical scenarios.

I. INTRODUCTION

Cognitive radio (CR) technology has been proposed as an enabling solution to alleviate the spectrum underutilization problem [1]. With the capability of sensing the frequency bands in a time and location-varying spectrum environment and adjusting the operating parameters based on the sens- ing outcome, CR technology allows an unlicensed user (or, secondary user) to exploit those frequency bands unused by licensed users (or, primary users) in an opportunistic manner [2]. Secondary users (SUs) can form an infrastructure-based network or an ad hoc network. Recently, CR ad hoc networks have attracted plentiful research attention due to their various applications [3].

Broadcast is an important operation in ad hoc networks, especially in distributed multi-hop multi-channel networks. Control information exchange among neighboring nodes, such as channel availability and routing information, is crucial for the realization of most networking protocols in an ad hoc network. This control information is often sent out as network- wide broadcasts, messages that are sent to all other nodes in a network. In addition, some exigent data packets such as emergency messages and alarm signals are also delivered as network-wide broadcasts [4]. Due to the importance of the broadcast operation, in this paper, we address the broadcasting

This work was supported in part by the US National Science Foundation (NSF) under Grant No. CNS-0855200, CNS-0915599, and CNS-0953644.

issue in multi-hop CR ad hoc networks. Since broadcast messages often need to be disseminated to all destinations as quickly as possible, we aim to achieve very high successful broadcast ratio and the shortest broadcast delay.

The broadcasting issue has been studied extensively in traditional ad hoc networks [5]–[8]. However, unlike tradi- tional single-channel or multi-channel ad hoc networks where the channel availability is uniform, in CR ad hoc networks, different SUs may acquire different sets of available channels. This non-uniform channel availability imposes special design challenges for broadcasting in CR ad hoc networks. First of all, for traditional single-channel and multi-channel ad hoc networks, due to the uniformity of channel availability, all nodes can tune to the same channel. Thus, broadcast messages can be conveyed through a single common channel which can be heard by all nodes in a network. However, in CR ad hoc networks, the availability of a common channel for all nodes may not exist. More importantly, before any control information is exchanged, a SU is unaware of the available channels of its neighboring nodes. Therefore, broadcasting messages on a global common channel is not feasible in CR ad hoc networks.

To further illustrate the challenges of broadcasting in CR ad hoc networks, we consider a single-hop scenario shown in Fig. 1, where node A is the source node. For traditional single-channel and multi-channel ad hoc networks, as shown in Fig. 1(a), nodes can tune to the same channel (e.g., channel 1) for broadcasting. Thus, node A only needs one time slot to let all its neighboring nodes receive the broadcast message in an error-free environment. However, in CR ad hoc networks where the channel availability is heterogeneous and SUs are unaware of the available channels of each other, as shown in Fig. 1(b), node A may have to use multiple channels for broadcasting and may not be able to finish the broadcast within one time slot. In fact, the exact broadcast delay for all single- hop neighboring nodes to successfully receive the broadcast message in CR ad hoc networks relies on various factors (e.g., channel availability and the number of neighboring nodes) and it is random.

A (ch1)

B (ch1)

C (ch1)

(a)Traditional ad hoc networks.

A (ch1,ch3)

B (ch1,ch2)

C (ch2,ch3)

(b) CR ad hoc networks.

Fig. 1. The single-hop broadcast scenario.

Furthermore, since multiple channels may be used for

2012 Proceedings IEEE INFOCOM

broadcasting and the exact time for all single-hop neighboring nodes to successfully receive the broadcast message is random, to avoid broadcast collisions (i.e., a node receives multiple copies of the broadcast message simultaneously) is much more complicated in CR ad hoc networks, as compared to traditional ad hoc networks. In traditional ad hoc networks, numerous broadcast scheduling schemes are proposed to reduce the probability of broadcast collision while optimizing the network performance [9]–[14]. All these proposals are on the basis that all nodes use a single channel for broadcasting and the exact delay for a single-hop broadcast is one time slot. However, in CR ad hoc networks, without the information about the channel used for broadcasting and the exact delay for a single-hop broadcast, to predict when and on which channel a broadcast collision occurs is extremely difficult. Hence, to design a broadcast protocol which can eliminate broadcast collisions, as well as provide high successful broadcast ratio and short broadcast delay is a very challenging issue for multi- hop CR ad hoc networks under practical scenarios. Simply extending existing broadcast protocols to CR ad hoc networks cannot yield the optimal performance.

Currently, research on broadcasting in multi-hop CR ad hoc networks is still in its infant stage. There are only limited papers addressing the broadcasting issue in CR ad hoc networks [15] [16]. However, both papers adopt imprac- tical assumptions which make them inadequate to be used in practical scenarios. In [15] and [16], the global network topology and the available channel information of all SUs are assumed to be known. Additionally, in [16], a common signaling channel for the whole network is employed which is also not practical. Other proposals aiming to locally es- tablish a common control channel may also be considered for broadcasting [17]–[19]. However, these proposals need a-priori channel availability information of all SUs which is usually obtained via broadcasts. In addition, although some schemes on channel hopping in CR networks can be used for finding a common channel between two nodes [20]–[22], they still suffer various limitations and cannot be used in broadcast scenarios. In [20] and [21], the proposed channel hopping schemes cannot guarantee rendezvous under some special circumstances. In addition, one of the proposed schemes in [20] only works when two SUs have exactly the same available channel sets. Moreover, in [22], a jump-stay based channel hopping algorithm is proposed for guaranteed rendezvous. However, the expected rendezvous time for the asymmetric model (i.e., different users have different available channels) increases exponentially when the total number of channels increases. Thus, it is unsuitable for broadcast scenarios which usually require short broadcast delay. Other channel hopping algorithms explained in [23] require tight time synchronization which is also not feasible before any control information is exchanged.

In this paper, a fully-distributed broadcast protocol in a multi-hop CR ad hoc network is proposed. We consider practical scenarios in our design: 1) no global and local common control channel is assumed to exist; 2) the global

network topology is not known; 3) the channel information of any other SUs is not known; 4) the available channel sets of different SUs are not assumed to be the same; and 5) tight time synchronization is not required. Our proposed broadcast protocol can provide very high successful delivery ratio while achieving the shortest broadcast delay. It can also eliminate broadcast collisions. To the best of our knowledge, this is the first work that addresses the broadcasting challenges specifically in multi-hop CR ad hoc networks under practical scenarios.

The rest of this paper is organized as follows. In Section II, the proposed broadcast protocol for multi-hop CR ad hoc networks is presented. The derivation of an important system parameter is given in Section III. Simulation results are shown in Section IV, followed by the conclusions in Section V.

II. THE PROPOSED BROADCAST PROTOCOL

In this section, we introduce the proposed broadcast protocol for multi-hop CR ad hoc networks. There are three compo- nents of the protocol: 1) the construction of the broadcasting sequences; 2) the distributed broadcast scheduling scheme; and 3) the broadcast collision avoidance scheme. We assume that a time-slotted system is adopted for SUs, where the length of a time slot is long enough to transmit a broadcast packet. We also assume that each SU knows the locations of its all 2-hop neighbors. We claim that this is a more valid assumption than the knowledge of global network topology. In the rest of the paper, we use the term “sender” to indicate a SU who has just received a message and will rebroadcast the message. In addition, we use the term “receiver” to indicate a SU who has not received the message. The notations used in our protocol design are listed in Table I.

TABLE I NOTATIONS USED IN THE PROTOCOL

N (v) The set of the neighboring nodes of node v N (N (v)) The set of the neighbors of the neighboring nodes of node v d(v, u) The Euclidean distance between node v and u

rc The radius of the transmission range of each node | · | The number of elements in a set Lv The downsized available channel set of node v

w(v) The size of the downsized available channel set of node v C The set of the initial w of intermediate nodes

BSv The broadcasting sequence for a sender v RSv The broadcasting sequence for a receiver v DSv The default sequence of a sender v stv The starting time slot of a sender v rtv The time slot that a receiver v receives the message Rv The random number assigned to a receiver v by its sender

A. Construction of the Broadcasting Sequences

The broadcasting sequences are the sequences of chan- nels by which a sender and its receivers hop for successful broadcasts. First of all, we consider the single-hop broadcast scenario. As explained in Section I, due to the non-uniform channel availability in CR ad hoc networks, a SU sender may have to use multiple channels for broadcasting in order to let all its neighboring nodes receive the broadcast message. Accordingly, the neighboring nodes may also have to listen

2274

to multiple channels in order to receive the broadcast mes- sage. Hence, the first issue to design a broadcast protocol is which channels should be used for broadcasting. One possible method is to broadcast on all the available channels of the SU sender. However, this method is quite costly in terms of broadcast delay when the number of available channels is large. Therefore, we propose to select a subset of channels from the original available channel set of each SU. The available channels of each SU are first ranked based on the channel indexes. Then, each SU selects the first w channels from the ranked channel list and forms a downsized available channel set. The value of w needs to be carefully designed to ensure that at least one common channel exists between the downsized available channel sets of the SU sender and each of its neighboring nodes. The detailed derivation process to obtain a proper w is given in Section III. Based on the derivation process, each SU can calculate the value of w of its own and its 1-hop neighbors before a broadcast starts.

On the other hand, another important issue is the sequences of the channels by which a sender and its receivers hop for successful broadcasts. In this paper, we design two broadcast- ing sequences for a SU sender and its receivers to guarantee a successful broadcast in the single-hop scenario as long as they have at least one common channel. The sender hops and broadcasts a message on each channel in a time slot following its sequence. On the other hand, the receiver hops and listens on each channel following its sequence. The pseudo-codes for constructing the broadcasting sequences are shown in Algorithm 1 and 2.

Algorithm 1: Construction of the broadcasting sequence BSv for a SU sender v.

Input: w(v), Lv . Output: BSv . randomize the order of elements in Lv ; BSv ← ∅; /* initialization */ i ← 1; while i ≤ w(v)2 do

BSv(i) ← Lv((i mod w(v)) + 1); i ← i + 1; /* repeat Lv for w(v) times */

return BSv ;

Algorithm 2: Construction of the broadcasting sequence RSv for a SU receiver v.

Input: w(v), Lv . Output: RSv . randomize the order of elements in Lv ; RSv ← ∅; /* initialization */ i ← 1; while i ≤ w(v) do

j ← 1; while j ≤ w(v) do

RSv((i − 1)w(v) + j) ← Lv(i); j ← j + 1; /*repeat an element for w(v) times*/

i ← i + 1; /*repeat for every element in Lv */ return RSv ;

Fig. 2 gives an example to illustrate the construction of the broadcasting sequences for SU senders and receivers. In Fig. 2, the downsized available channel set of the sender and the receiver is {1, 2} and {2, 3, 4}, respectively. Based on Algorithm 1, the broadcasting sequence of the sender is

{2, 1, 2, 1}. Similarly, based on Algorithm 2, the broadcasting sequence of the receiver is {4, 4, 4, 3, 3, 3, 2, 2, 2}. Since a sender usually does not know the length of the broadcasting sequence of the receiver, it broadcasts the message based on its broadcasting sequence for b M

w2 c+1 cycles, where M is the total number of channels. Therefore, as shown in Fig. 2, the shaded part represents a successful broadcast.

2 1 2 1 2 1Tx

2 1

4 4 4 3 3 3 2 2 2

...

1 cycle

Fig. 2. An example of the broadcasting sequences.

Since every SU calculates the initial value of w based on its local information and the derivation process in Section III, different SUs may obtain different values of w. We further denote ws and wr as the w used by the sender and the receiver to construct their broadcasting sequences, respectively. Note that ws and wr may not necessarily be the same as the initial w calculated by each SU. They also depend on the initial w of its neighboring nodes. The following theorem gives an upper- bound on the single-hop broadcast delay.

Theorem 1. If ws ≤ wr, the single-hop broadcast is a guaranteed success within w2r time slots as long as the sender and the receiver have at least one common channel between their downsized available channel sets.

Proof: Based on Algorithm 1, a SU sender broadcasts on all the channels in its downsized available channel set in ws consecutive time slots. Based on Algorithm 2, a SU receiver listens to every channel in its downsized available channel set for wr consecutive time slots. If ws ≤ wr, during the wr consecutive time slots for which the SU receiver stays on the same channel, every channel of the SU sender must appear at least once. Thus, as long as the SU sender and the receiver have at least one common channel, there must exists a time slot that the sender and the receiver hop on the same channel during one cycle of the broadcasting sequence of the receiver (i.e., w2r ). Therefore, the broadcast is guaranteed to be successful.

Then, how to determine ws and wr ? From Theorem 1, ws ≤ wr is a sufficient condition of a single-hop successful broadcast. Therefore, in order to satisfy this condition, a proper wr needs to be selected by any SU who has not received the broadcast message to ensure the reception of the broadcast message sent from any potential neighbor. Since wr depends on ws and a SU receiver usually does not know which neighboring node is sending until it receives the broadcast message, it selects the largest initial w of all its 1-hop neighbors as its wr . That is, for a SU receiver v, wr(v) = max{w(u)|u ∈ N (v)}. On the other hand, the sender uses its calculated initial w as ws to broadcast. Therefore, the ws selected by the actual sender is bound to be smaller than or equal to this wr . Thus, according to Theorem 1, the single- hop broadcast is a guaranteed success as long as the sender and its receiver have at least one common channel between their downsized available channel sets.

2275

To illustrate the above discussed operation, we consider a multi-hop scenario shown in Fig. 3. The initial w calculated by each SU before the broadcast starts based on its local informa- tion is shown in the brackets. Every node also calculates the initial w of its 1-hop neighbors. Without loss of generality, node A is assumed to be the source node. Thus, based on Theorem 1, the values of wr employed by each receiver can be obtained. For instance, since node B knows the initial w of its neighbors (i.e., w(A)=3, w(D)=4, and w(F )=4), it selects the largest initial w as its own wr (i.e., wr(B) = 4). Similarly, we have wr(C) = 4, wr(D) = 3, wr(E) = 4, and wr(F ) = 5. Then, all nodes except node A use their wr to construct the broadcasting sequences based on Algorithm 2.

A [3] B [3]

C [5]

D [4]

F [4]

E [2]

Fig. 3. A multi-hop broadcast sce- nario.

B [3]

C [3]

Fig. 5. The broadcast scenario where a broadcast collision may occur.

B. The Distributed Broadcast Scheduling Scheme

Algorithm 3: The pseudo-code of the broadcast scheduling scheme for a SU sender v.

Input: q, N (v), N (N (v)),{w(u)|u ∈ N (q)}. Output: Decision of rebroadcasting. C ←{w(v)}; if {k|k ∈ (N (v) − N (v) ∩ N (q))} 6= ∅ then /* v has at least one receiver */

foreach k do if {u|u ∈ N (q), d(u, k) ≤ rc, u 6= v} 6= ∅ then /* there are multiple paths from q → k */

foreach u do C ← {C, w(u)};

if w(v) = minC and |{e|e = minC}| = 1 then /*v is the only node with the smallest w*/

return TRUE; else if w(v) = minC and |{e|e = minC}|> 1 then /* v is one of the multiple nodes with the same smallest w */

run Algorithm 4; return TRUE;

else return FALSE; /* v does not rebroadcast */

else return TRUE; /*vrebroadcasts the message*/

else return FALSE;

Next, we consider the multi-hop broadcast scenario. The goal of the proposed broadcast scheduling scheme is to intel- ligently select SU nodes for rebroadcasting in order to achieve the shortest broadcast delay.

First, from the simulation results shown in Fig. 4, we can observe that the single-hop broadcast delay increases when w increases. Therefore, in a multi-hop broadcast scenario, if there are multiple intermediate nodes with the same neighboring node, the node with the smallest w is selected to rebroadcast. If there are more than one intermediate node with the smallest w, a broadcast collision avoidance scheme (which is explained in detail in Section II-C) is executed before they rebroadcast the

message. The pseudo-code of the proposed scheduling scheme is shown in Algorithm 3, where node v has just received the broadcast message from node q and needs to decide whether to rebroadcast. Node q includes the calculated initial w of its 1-hop neighbors in the broadcast message. Algorithm 3 indicates that each SU should know the locations of its 1-hop neighbors (in order to obtain N (v)) and its 2-hop neighbors (in order to obtain N (q) and d(u, k)). Once a node receives the message, it executes Algorithm 3 to decide whether it should rebroadcast or not. If it needs to rebroadcast, it uses its calculated initial w as ws to construct the broadcasting sequence based on Algorithm 1. Thus, as shown in Fig. 3, the message deliveries are shown by the arrows.

From the above design, it is noted that each SU (either sending or receiving) follows the same rules and no prior information about the sender is required. Thus, the proposed broadcast scheduling scheme is fully distributed. In addition, since the node with the smallest w is selected for rebroadcast- ing, the broadcast delay is the shortest.

3 4 5 6 7 2.5

3.5

4.5

5.5

S in

g le

− h

o p

B ro

a d

ca st

D e

la y

(t im

e s

lo ts

)

Fig. 4. The single-hop broadcast delay when ws=wr=w.

C. The Broadcast Collision Avoidance Scheme From Algorithm 3, if there are multiple intermediate nodes

between two SUs, only the intermediate node with the smallest w should rebroadcast. However, if more than one intermediate node with the same smallest w, a broadcast collision may occur if these nodes deliver the messages on the same channel at the same time. For instance, in the example shown in Fig. 5 where node A is the source node, node B and C have the same w, which may lead to a broadcast collision.

Most broadcast collision avoidance methods in traditional ad hoc networks assign different time slots to different interme- diate nodes to avoid simultaneous transmissions. However, as explained in Section I, these methods cannot be applied to CR ad hoc networks because the exact time for the intermediate nodes to receive the broadcast message is random. As a result, to assign different time slots for different intermediate nodes is very challenging. In addition, since the intermediate nodes use multiple channels for broadcasting, the channel on which the broadcast collision occurs is also unknown. To the best of our knowledge, no existing collision avoidance scheme can address these challenges in CR ad hoc networks.

In this paper, we propose a broadcast collision avoidance scheme for CR ad hoc networks. The main idea is to prohibit intermediate nodes from rebroadcasting on the same channel at the same time. The procedure of the proposed broadcast collision avoidance scheme is summarized as follows:

Step 1 Generating a Default Sequence: When a source node (e.g., node A in Fig. 5) broadcasts the message, it includes

2276

its own original available channel set in the message. Hence, if an intermediate node receives the message, it obtains the original available channel information of its parent node. Then, the intermediate node uses the first w available channels of its parent node to generate a default sequence, where w is its own calculated initial w (which may not be the same as the initial w of its parent node). If a channel in the default sequence is not available for this intermediate node, a void channel is assigned to replace the corresponding channel. For instance, if node B and C both obtain w = 3 and the original available channels of node A, B, and C are {1, 2, 3, 4, 5}, {2, 3, 4, 5}, and {1, 3, 4, 6}, respectively, node B and C only use the first three available channels of node A to generate their default sequences. Therefore, the default sequence of node B is {0, 2, 3} and the default sequence of node C is {1, 0, 3}, where 0 means a void channel. A node does not send anything on a void channel.

Step 2 Circular Shifting the Default Sequence with a Ran- dom Number: Apart from the available channel set, the source node also includes a distinctive integer for each intermediate node v randomly selected from [1, w(v)]. Then, each interme- diate node generates a new sequence from its default sequence using circular shift and the random integer. If we denote the default sequence as DS and the random integer as R, the intermediate node performs circular shift on the DS for R times (there is no difference of right-shift or left-shift). For instance, if node B and C get 3 and 1 as their random integers, respectively, the new sequences they generate from left-handed circular shift are {0, 2, 3} and {0, 3, 1}, respectively.

Step 3 Forming the Broadcasting Sequence: Denote the starting time slot of the source node’s broadcasting sequence as st and the time slot when an intermediate node receives the broadcast message as rt. The source node includes its st in the broadcast message. Then, the intermediate node performs circular shift on the new sequence generated from Step 2 for another (rt − st + 1) times. It repeats that sequence for w(v) times to form a cycle of its broadcasting sequence.

The pseudo-code of the broadcast collision avoidance scheme is shown in Algorithm 4, where q is the source node and Circshift() is the function of circular shift. To further elaborate the scheme, Fig. 6 shows an example of the proposed broadcast collision avoidance scheme. Without loss of generality, the starting time slot of the source node is 1. When node B and C do not receive the broadcast message, they hop through the channels based on the broadcasting sequences generated from Algorithm 2. Then, node B and C receive the broadcast message at time slot 4 and 1, re- spectively. Based on Algorithm 4 and if the random integers for node B and C are 3 and 1, respectively, node B forms the broadcasting sequence as {2, 3, 0, 2, 3, 0, 2, 3, 0} and node C forms the broadcasting sequence as {3, 1, 0, 3, 1, 0, 3, 1, 0}. Then, they start rebroadcasting from time slot 5 and 2 using the broadcasting sequences, respectively. The underlined channels are those a node hops on if it starts from time slot 1.

Therefore, by constructing the broadcasting sequences from the same channel set (the channel set of the common parent

node, node A) but circular shifting different times for different nodes, the intermediate nodes are guaranteed not to send on the same channel at the same time. Thus, broadcast collisions can be totally eliminated. A trade-off of the proposed broadcast collision avoidance scheme is that less available channels are used for broadcasting because some void channels may be assigned. However, the benefit (e.g., the increase of the successful broadcast ratio) gained from eliminating broadcast collisions is greater than the loss of a very few number of channels. Hence, the only issue left is the derivation of the initial w, which is introduced in Section III.

Algorithm 4: The pseudo-code of the broadcast collision avoidance scheme for SU v.

Input: q, Lq , Lv , stq , rtv , Rv , w(v). Output: BS′v . BS′v ← ∅; /* initialization */ i ← 1; l ← 1; while i ≤ w(v) do /* generating a default sequence */

j ← 1; while j ≤ w(v) do

if Lv(i) = Lq(j) then DSv(j) ← Lq(j);

Tv ← Circshift(DSv , Rv ); /* circular shifting */ while l ≤ w(v)2 do /* forming a broadcast sequence */

BS′v(l) ← Tv(l+(rtv−stq)+1 mod w(v)); l ← l + 1;

return BS′v ;

1 2 1 2 1 2Tx

1 2Node A

Node B 4 4 4 2 2 2 3 3 3

0 2 3 0 2 3 0 2 3Tx 0 2 3 0

RxNode C 1 1 1 3 3 3 4 4 4

0 3 1 0 3Tx 1 0 3 1 0

time slot 1 2 3 4 5 6 7 8 9 10 11 12 13

...

Fig. 6. An example of the proposed broadcast collision avoidance scheme.

III. THE DERIVATION OF THE VALUE OF w

In this section, we first introduce a network model we consider. Then, based on this model, we present the derivation of the size of the downsized available channel set w.

A. The Network Model

In this paper, we consider a CR ad hoc network where N SUs and K primary users (PUs) co-exist in an α×α area. PUs are evenly distributed within the area. The SUs opportunistically access M licensed channels. Each SU has a circular transmission range with a radius of rc. The SUs within the transmission range are considered as the neighboring nodes of the corresponding SU. That is, only when a SU receiver is within the transmission range of a SU transmitter, the signal- to-noise ratio (SNR) at the SU receiver is considered to be acceptable for reliable communications. In addition, apart from the broadcast collision, other factors may also contribute to the packet error (e.g., channel quality, modulation schemes, and coding rate). However, in this paper, we only consider the

2277

broadcast collision as the reason for the packet error. We claim that this is a valid assumption in most broadcast scenarios [5]– [11] [13]–[16].

Each SU also has a circular sensing range with a radius of rs. That is, if a PU is currently active within the sensing range of a SU, the corresponding SU is able to detect its appearance. Since different SUs have different local sensing ranges which include different PUs, their acquired available channels may be different. In addition, because the available channels of a SU are obtained based on the sensing outcome within the sensing range, a SU is not allowed to communicate with other SUs outside its sensing range since it may mistakenly use an occupied channel by a PU, which results in interference to the PU. Therefore, in this paper, we assume that rc ≤ rs.

In this paper, we model the PU channel activity as an ON/OFF process, where the length of the ON period is the length of a PU packet. The length of the ON period and the OFF period can follow arbitrary distributions. We assume that each PU randomly selects a channel from the spectrum band to transmit one packet which consists of multiple time slots. Moreover, because PUs at different locations can claim any channels for communications, the packets on the same channel do not necessarily belong to the same PU. This is a more practical scenario, as compared to some papers which assume that each channel is associated with a different PU. Under such a practical scenario, only those PUs that are within the sensing range of a SU and are active during the broadcast process contribute to the unavailable channels of the SU [24].

B. The Derivation of the Value of w

As explained in Section II, the value of w is essential to ensure a successful single-hop broadcast. Denote the prob- ability of a successful single-hop broadcast as Psucc(w), where Psucc(w) is a function of w. Our goal is to obtain an appropriate w that satisfies the condition: Psucc(w) ≥ 1 − δ, where δ is a small pre-defined value. From Theorem 1, the condition that at least one common channel exists between the downsized available channel sets of a SU pair is a necessary condition for a successful single-hop broadcast. Therefore, if we denote the source SU of a single-hop broadcast as S0 and the neighbors of S0 as {S1, S2, · · · , SH}, where H is the number of neighbors, Psucc(w) is equal to the probability that there is at least one common channel between S0 and each of its neighbors in their downsized available channel sets.

S0 Si

A1 A2

(a) The single-pair scenario.

S0 Si

(b)The multi-pair scenario.

Fig. 7. The single-hop broadcast scenario.

1) The single-pair scenario: we first calculate the prob- ability that there is at least one common channel between the downsized available channel sets of S0 and one of its

neighbors Si. The relative locations of the two SUs and their sensing ranges are shown in Fig. 7(a). As shown in Fig. 7(a), sensing ranges are divided into three areas: A1, A2, and A3. Note that PUs in different areas have different impact on the channel availability of the two SUs. For instance, if a PU is active within A3, the channel used by this PU is unavailable for both SUs. However, if a PU is active within A1, the channel used by this PU is only unavailable for S0. Thus, we first calculate the probability that a channel is available within each area, Pk, k ∈ [1, 2, 3]. The size of the total network area is denoted as AL (i.e., AL = α2). Since the locations of PUs are evenly distributed, the probability that p PUs are within Ak is

Pr(p) = (

K p

) (

Ak AL

)p( AL−Ak AL

)K−p

, (1)

where (K

)

represents the total combinations of K choosing p. In addition, we define the probability that a PU is active, ρ, as:

ρ = E[ON duration]

E[ON duration] + E[OFF duration] , (2)

where E[·] represents the expectation of the random variable. Therefore, given that there are p PUs within Ak, the proba- bility that there are b PUs active is

Pr(b|p) = (

p b

)

ρb(1 − ρ)p−b. (3)

Furthermore, given that there are p PUs and b active PUs within Ak, the probability that there are c available channels is denoted as Pr(c|p, b). Since the number of available channels is only related to the number of active PUs, c is independent of p. In addition, since an active PU randomly selects a channel from M channels in the band, Pr(c|p, b) is equivalent to the probability that there are exactly c empty boxes given that b balls are randomly put into a total of M boxes and a box can have more than one ball (because we do not limit a channel to only one PU). Thus, Pr(c|p, b) can be expressed as:

Pr(c|p, b) =

(M c

)( b−1 b−M+c

)

(b+M−1 b

) , c ∈ [max(0, M −b), M ]. (4)

Hence, the probability that there are c available channels and there are p PUs and b active PUs within Ak is the product of (1), (3), and (4). Then, the probability that a channel is available within Ak is obtained from (5).

Next, we consider the relationship between the downsized available channel sets of the two SUs. In our derivation, we only consider the scenario where the sender and its receiver have the same w (i.e., ws=wr ). If wr > ws, the channels after the first ws channels do not affect the number of common channels. Thus, the derivation process is the same. Fig. 8 shows an example of the channel availability status of two SUs when w(S0) = 3, where a shaded square indicates an idle channel and a white square indicates a busy channel. A square with a cross means that a channel can be either idle or busy. Since each SU only selects the first w available channels to form a downsized available channel set, the availability status of the channels after the first w available channels is not specified. Then, without loss of generality, we denote t and h as the index of the last available channel in the downsized

2278

Pk = 1 M

K ∑

p=0

p ∑

b=0

M ∑

c=max(0,M−b)

c (M

)( b−1 b−M+c

)

(b+M−1 b

)

(

p b

)

ρb(1 − ρ)p−b (

K p

) (

Ak AL

)p ( AL − Ak AL

)K−p

. (5)

P ′′1 (h) = P z C1P

w−z C3

h−1 ∑

t=w

t−w ∑

x=max(0,w+t−h)

(

t−1 w−1

)(

w z

)(

t−w x−z

)(

h−t−1 w−x−1

)

P x−zC4 P (t−w−x+z) C2 (PC1+PC4)

(w−x)(PC2+PC3) (h−t−w+x). (7)

P ′′(h) = P zC1P w−z C3

∑h−1 t=w

∑t−w x=max(0,w+t−h)

( t−1 w−1

)(w z

)(t−w x−z

)( h−t−1 w−x−1

)

P x−zC4 P (t−w−x+z) C2 (PC1 +PC4)

(w−x)(PC2 +PC3)(h−t−w+x)

+P zC1P w−z C4

∑h−1 t=w

∑t−w x=max(0,w+t−h)

( t−1 w−1

)(w z

)(t−w x−z

)( h−t−1 w−x−1

)

P x−zC3 P (t−w−x+z) C2 (PC1 +PC3)

(w−x)(PC2 +PC4)(h−t−w+x). (8)

available channel sets of S0 and Si, respectively. We first assume that t ≤ h. Hence, from channel 1 to t, there are four possible scenarios of every channel in terms of its availability for the two SUs. They are: 1) the channel is available for both SUs (denoted as C1); 2) the channel is unavailable for both SUs (denoted as C2); 3) the channel is only available for S0 (denoted as C3); and 4) the channel is only available for Si (denoted as C4). In addition, from channel t+1 to h (if t < h), there are two possible scenarios: 1) the channel is available for Si but it can be any status for S0 (denoted as C5) and 2) the channel is unavailable for Si but it can be any status for S0 (denoted as C6). Based on Fig. 7(a), the probabilities of the above six scenarios can be obtained: 1) PC1 = P1P2P3; 2) PC2 = (1−P3)+(1−P1)(1−P2)P3; 3) PC3 = P1P3(1−P2); 4) PC4 = (1 − P1)P2P3; 5) PC5 = PC1 + PC4; and 6) PC6 = PC2 + PC3.

Fig. 8. An example of the channel availability status when w(S0) = 3.

Denote Z(0, i) as the number of common channels between S0 and Si in their downsized available channel sets. In order to obtain Pr(Z(0, i) = z), we need to consider all the combinations of the channel status for every channel from channel 1 to h. There are two possible cases: 1) t = h and 2) t < h. For the first case, channel h is a common channel between the two SUs. In addition, from channel 1 to channel h−1, there must be z−1 channels in scenario C1; h−2w+z channels in C2, and w−z channels in C3 and C4, respectively. Since t = h, no channel is in scenario C5 or C6. Thus, the probability that there are z(z > 0) common channels in the first case is

P ′(h)= (

h−1 z−1

)(

h−z w−z

)(

h−w w−z

)

P zC1P h−2w+z C2 P

w−z C3 P

w−z C4 . (6)

For the second case, since t < h, the common available channels can only be between channel 1 to t. We denote the number of available channels for Si from channel 1 to t as x. Thus, from channel 1 to t, similar to the first case, there are z channels in C1; t−w−x+z channels in C2; w−z channels in C3; and x−z channels in C4. In addition, from channel t+1 to h, there are w−x channels in C5 and h−t−w+x channels in C6. Therefore, the probability that there are totally z common

channels is obtained from (7). If we switch S0 and Si in Fig. 8, we can obtain the probability for the dual case. Hence, the probability that there are z common channels in the second case is expressed in (8).

Therefore, the probability that there are z common channels for the first w available channels for each SU is

Pr(Z(0, i) = z) = M ∑

h=2w−z

P ′(h) + P ′′(h). (9)

Thus, the probability of a successful single-hop broadcast from S0 to Si is

Psucc(w) = 1 − Pr(Z(0, i) = 0). (10) Fig. 9 shows the analytical and simulation results of

Psucc(w) in the single-pair scenario under various w and different M . To obtain these results, the number of PUs K = 40 and the probability that a PU is active ρ = 0.9. In addition, the side length of the network area α = 10 (unit length) and two neighboring SUs are at the border of each other’s sensing range where rs = 2 (unit length). As shown in Fig. 9, the simulation results match extremely well with the analytical results.

1 2 3 4 5 6 7 0.7

0.75

0.8

0.85

0.9

0.95

P su

cc (w

)

M=15 analytical M=15 simulation M=20 analytical M=20 simulation

Fig. 9. Analytical and simulation results of Psucc(w) in the single-pair scenario under various w and different M .

2) The multi-pair scenario: we extend the above results to a multi-pair scenario, as shown in Fig. 7(b) where Si and Sj are two neighbors of S0. Based on the knowledge of combination mathematics, the probability of a successful broadcast in the multi-pair scenario shown in Fig. 7(b) is

Psucc(w) =1−Pr(Z(0, i) = 0)−Pr(Z(0, j) = 0) +Pr(Z(0, i, j) = 0),

(11)

where Pr(z(0, i, j) = 0) is the probability that both Si and Sj do not have any common channel in the downsized available channel sets with S0. Since the other two terms in (11) (i.e., Pr(Z(0, i) = 0) and Pr(Z(0, j) = 0)) can be obtained from (9), we only need to calculate Pr(Z(0, i, j) = 0).

2279

To calculate Pr(Z(0, i, j) = 0), we use the same idea from the single-pair scenario. That is, we consider Si and Sj together as one new neighboring node. The sensing range of the new neighboring node is the union of the sensing ranges of the two original nodes (i.e., the shaded area in Fig. 7(b)). Therefore, we can obtain new P1, P2, and P3 for the multi-pair scenario based on the new size of the sensing range. Moreover, the probabilities of every scenario of the channel status can also be obtained accordingly. Therefore, by using (6)-(9), we can calculate Pr(Z(0, i, j) = 0). Then, given the locations of the H neighbors, each SU can get the probability of a successful single-hop broadcast by performing the same procedure iteratively for H times. Finally, by letting Psucc(w) ≥ 1 − δ, a proper w can be acquired for S0.

IV. PERFORMANCE EVALUATION

In this section, we evaluate the performance of the proposed broadcast protocol. We consider two types of PU traffic models in the simulation. The first PU traffic model is discrete-time, where the PU packet inter-arrival time follows the biased- geometric distribution [25]. The second PU traffic model is continuous-time, where the PU packet inter-arrival time follows the Pareto distribution [25]. We assume that the proba- bility that a PU is active is fixed (i.e., ρ = 0.9). In addition, the side length of the network area α=10 (unit length). We assume that the radius of the sensing range and the transmission range are the same (i.e., rs = rc = 2 (unit length)). In this paper, we mainly investigate the following two performance metrics: 1) successful broadcast ratio: the probability that all nodes in a network successfully receive the broadcast message and 2) average broadcast delay: the average duration from the moment a broadcast starts to the moment the last node receives the broadcast message. In addition, we compare our proposed broadcast protocol with four other schemes: 1) Random+Flooding: each SU randomly selects a channel to hop and uses flooding (i.e., a SU is obligated to rebroadcast once receiving the message); 2) Sequence+Flooding (1/3 of our design): each SU downsizes its available channel set and constructs broadcasting sequences based on our scheme and uses flooding; 3) Sequence+Schedule (2/3 of our design): each SU constructs broadcasting sequences based on our scheme and uses our broadcast scheduling scheme; and 4) JS+Flooding: each SU uses the jump-stay scheme [22] to construct the broadcasting sequences and uses flooding.

A. Successful Broadcast Ratio

Since the single-hop successful broadcast ratio depends on w which is related to a pre-defined value δ, we define δ = 0.001. In fact, δ can be an arbitrary small value. Thus, based on Section III, each SU calculates a proper w before the broadcast starts in our scheme, the Sequence+Flooding scheme, and the Sequence+Schedule scheme. Table II and III show the simulation results of the successful broadcast ratio under different number of SUs and PUs, where the value in the upper cell is for the discrete-time PU traffic and the lower cell is for the continous-time PU traffic. In Table II, M = 20 and

K = 40. In Table III, M = 20 and N = 20. As shown in Table II and III, the successful broadcast ratio is higher than 99% under our proposed broadcast protocol in all scenarios. In addition, the proposed broadcast protocol outperforms other schemes in terms of higher successful broadcast ratio. Since the jump-stay scheme requires that the i-th available channel in the available channel set is also channel i, it cannot utilize the technique in our scheme to downsize the original available channel set. In addition, the jump-stay scheme can guarantee rendezvous within 6M P (P −G), where P is the smallest prime number larger than M and G is the number of common channels between two SUs. Thus, in order to ensure a successful broadcast, each SU broadcasts the message for 6M P (P −G) slots. However, 6M P (P −G) is usually a very large number when M is large. Hence, to better illustrate the trade-off between the successful broadcast ratio and broadcast delay, we compare our scheme with JS+Flooding in Section IV-B.

TABLE II SUCCESSFUL BROADCAST RATIO UNDER DIFFERENT NUMBER OF SUS

N =5 N =10 N =15 N =20 N =25

Random+Flooding 0.8801 0.8180 0.8100 0.8726 0.8821 0.8630 0.9148 0.9075 0.8698 0.8708

Sequence+Flooding 0.9849 0.9839 0.9828 0.9823 0.9863 0.9762 0.9769 0.9777 0.9773 0.9719

Sequence+Schedule 0.9859 0.9864 0.9823 0.9857 0.9855 0.9812 0.9845 0.9849 0.9876 0.9861

Proposed Scheme 0.9991 0.9973 0.9969 0.9982 0.9909 0.9994 0.9959 0.9954 0.9967 0.9951

TABLE III SUCCESSFUL BROADCAST RATIO UNDER DIFFERENT NUMBER OF PUS

K=20 K=30 K=40 K=50 K=60

Random+Flooding 0.8189 0.8326 0.8842 0.9208 0.8907 0.7980 0.8738 0.9191 0.9139 0.8849

Sequence+Flooding 0.9866 0.9863 0.9823 0.9819 0.9871 0.9742 0.9765 0.9773 0.9711 0.9797

Sequence+Schedule 0.9868 0.9872 0.9857 0.9881 0.9872 0.9874 0.9885 0.9876 0.9833 0.9850

Proposed Scheme 0.9978 0.9976 0.9982 0.9951 0.9921 0.9946 0.9941 0.9967 0.9977 0.9969

B. Average Broadcast Delay

Table IV and V show the simulation results of the average broadcast delay under different number of SUs and PUs. Similarly to the successful broadcast ratio, in Table IV, M = 20 and K = 40. In Table V, M = 20 and N = 20. As shown in Table IV and V, the proposed broadcast protocol outperforms other schemes in terms of shorter average broadcast delay. Furthermore, Fig. 10 and 11 show the average broadcast delay under different number of channels when N = 10 and K = 40. As explained in Section IV-A, besides our proposed scheme, we also compare JS+Flooding and our scheme without downsizing the available channel set (i.e., w=M ). It is shown that even though the successful broadcast ratio is similar, the broadcast delay under JS+Flooding is much longer than our proposed scheme.

To sum up, our proposed broadcast protocol outperforms Random+Flooding in terms of higher successful broad- cast ratio and shorter broadcast delay. It also outperforms JS+Flooding in terms of shorter broadcast delay. In addition,

2280

even with the trade-off in our broadcast collision avoidance scheme explained in Section II-C and limited overhead, our proposed scheme and the schemes that use a part of our design (e.g., Sequence+Flooding) can still achieve better per- formance results than Random+Flooding for both metrics and JS+Flooding for broadcast delay.

TABLE IV AVERAGE BROADCAST DELAY UNDER DIFFERENT NUMBER OF SUS

Delay (unit: slots) N =5 N =10 N =15 N =20 N =25

Random+Flooding 19.781 26.483 28.003 29.252 31.203 20.981 23.765 27.686 33.153 32.883

Sequence+Flooding 8.458 11.168 12.744 14.243 15.909 7.712 11.799 12.903 14.534 17.257

Sequence+Schedule 7.811 10.995 13.324 13.896 15.823 7.155 11.457 13.553 14.551 15.078

Proposed Scheme 7.066 10.532 12.259 13.353 15.198 6.545 11.097 12.786 13.639 14.801

TABLE V AVERAGE BROADCAST DELAY UNDER DIFFERENT NUMBER OF PUS

Delay (unit: slots) K=20 K=30 K=40 K=50 K=60

Random+Flooding 29.189 31.459 25.737 25.361 24.243 34.547 30.629 27.617 28.424 26.399

Sequence+Flooding 13.918 14.886 14.243 14.649 14.259 14.413 13.958 14.534 14.867 14.389

Sequence+Schedule 12.747 14.206 13.896 14.361 14.014 13.652 14.086 14.551 14.521 14.237

Proposed Scheme 12.322 13.555 13.352 14.279 13.597 13.249 13.401 13.639 13.335 13.471

5 10 15 20 0

0.5

1.5

Total Number of Channels

S u

cc e

ss fu

l B ro

a ca

st R

a tio JS+Flooding

Proposed Proposed (w=M)

Fig. 10. Successful broadcast ratio under different number of channels.

5 10 15 20 0

100

120

Total Number of Channels

A ve

ra g

e B

ro a

d ca

st D

e la

y (t

im e

s lo

ts )

JS+Flooding Proposed Proposed (w=M)

Fig. 11. Average broadcast delay under different number of channels.

V. CONCLUSION

In this paper, the broadcasting challenges specifically in multi-hop CR ad hoc networks under practical scenarios have been addressed for the first time. A fully-distributed broadcast protocol is proposed without the existence of a global or local common control channel. By intelligently downsizing the original available channel set and designing the broadcasting sequences and broadcast scheduling schemes, our proposed broadcast protocol can provide very high successful broadcast ratio while achieving the shortest broadcast delay. In addition,

it can also eliminate broadcast collisions. Simulation results show that our proposed broadcast protocol outperforms other possible broadcast schemes in terms of higher successful broadcast ratio and shorter average broadcast delay.

REFERENCES [1] J. Mitola, “Cognitive radio: an integrated agent architecture for software

defined radio,” Ph.D. dissertation, KTH Royal Institute of Technology, 2000.

[2] I. F. Akyildiz, W.-Y. Lee, M. C. Vuran, and S. Mohanty, “NeXt generation/dynamic spectrum access/cognitive radio wireless networks: A survey,” Computer Networks (Elsevier), vol. 50, 2006.

[3] I. F. Akyildiz, W.-Y. Lee, and K. R. Chowdhury, “CRAHNs: cognitive radio ad hoc networks,” Ad Hoc Networks, vol. 7, no. 5, 2009.

[4] G. Resta, P. Santi, and J. Simon, “Analysis of multi-hop emergency message propagation in vehicular ad hoc networks,” in Proc. ACM MobiHoc, 2007, pp. 140–149.

[5] I. Chlamtac and S. Kutten, “On broadcasting in radio networks-problem analysis and protocol design,” IEEE Transactions on Communications, vol. 33, no. 12, pp. 1240–1246, Dec. 1985.

[6] S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu, “The broadcast storm problem in a mobile ad hoc network,” in Proc. ACM MobiCom, 1999, pp. 151–162.

[7] J. Wu and F. Dai, “Broadcasting in ad hoc networks based on self- pruning,” in Proc. IEEE INFOCOM, 2003, pp. 2240–2250.

[8] J. Qadir, A. Misra, and C. T. Chou, “Minimum latency broadcasting in multi-radio multi-channel multi-rate wireless meshes,” in Proc. IEEE SECON, vol. 1, 2006, pp. 80–89.

[9] A. Qayyum, L. Viennot, and A. Laouiti, “Multipoint relaying for flooding broadcast messages in mobile wireless networks,” in Proc. HICSS, 2002, pp. 3866–3875.

[10] Z. Haas, J. Halpern, and L. Li, “Gossip-based ad hoc routing,” IEEE/ACM Trans. Networking, vol. 14, no. 3, pp. 479–491, June 2006.

[11] Z. Chen, C. Qiao, J. Xu, and T. Lee, “A constant approximation algorithm for interference aware broadcast in wireless networks,” in Proc. IEEE INFOCOM, 2007, pp. 740–748.

[12] S. Huang, P.-J. Wan, X. Jia, H. Du, and W. Shang, “Broadcast scheduling in interference environment,” IEEE Transactions on Mobile Computing, vol. 7, no. 11, pp. 1338–1348, 2008.

[13] R. Mahjourian, F. Chen, R. Tiwari, M. Thai, H. Zhai, and Y. Fang, “An approximation algorithm for conflict-aware broadcast scheduling in wireless ad hoc networks,” in Proc. ACM MobiHoc, 2008, pp. 331–340.

[14] R. Gandhi, A. Mishra, and S. Parthasarathy, “Minimizing broadcast latency and redundancy in ad hoc networks,” IEEE/ACM Transactions on Networking, vol. 16, no. 4, pp. 840–851, 2008.

[15] Y. Kondareddy and P. Agrawal, “Selective broadcasting in multi-hop cognitive radio networks,” in Proc. IEEE Sarnoff Symposium, 2008.

[16] C. J. L. Arachchige, S. Venkatesan, R. Chandrasekaran, and N. Mittal, “Minimal time broadcasting in cognitive radio networks,” in Proc. ICDCN, 2011, pp. 364–375.

[17] L. Lazos, S. Liu, and M. Krunz, “Spectrum opportunity-based control channel assignment in cognitive radio networks,” in Proc. IEEE SECON, 2009, pp. 1–9.

[18] J. Zhao, H. Zheng, and G. Yang, “Spectrum sharing through distributed coordination in dynamic spectrum access networks,” Wireless Communi- cations and Mobile Computing, vol. 7, pp. 1061–1075, November 2007.

[19] K. Bian, J.-M. Park, and R. Chen, “Control channel establishment in cognitive radio networks using channel hopping,” IEEE JSAC, vol. 29, no. 4, pp. 689–703, April 2011.

[20] N. Theis, R. Thomas, and L. DaSilva, “Rendezvous for cognitive radios,” IEEE Trans. Mobile Computing, vol. 10, no. 2, pp. 216–227, 2010.

[21] C. Cormio and K. R. Chowdhury, “Common control channel design for cognitive radio wireless ad hoc networks using adaptive frequency hopping,” Ad Hoc Networks, vol. 8, no. 4, pp. 430–438, 2010.

[22] Z. Lin, H. Liu, X. Chu, and Y.-W. Leung, “Jump-stay based channel hopping algorithm with guaranteed rendezvous for cognitive radio networks,” in Proc. IEEE INFOCOM, 2011.

[23] J. Mo, H.-S. W. So, and J. Walrand, “Comparison of multichannel MAC protocols,” IEEE Trans. on Mobile Computing, vol. 7, no. 1, 2008.

[24] Y. Song and J. Xie, “A QoS-based broadcast protocol for multi-hop cognitive radio ad hoc networks under blind information,” in Proc. IEEE GLOBECOM, 2011.

[25] ——, “ProSpect: A proactive spectrum handoff framework for cognitive radio ad hoc networks without common control channel,” to appear in IEEE Trans. Mobile Computing, 2012.

2281