Veleco

SECURITY OPTIMIZATION OF DYNAMIC NETWORKS WITH PROBABILISTIC GRAPH MODELING AND LINEAR PROGRAMMINGByAPROJECT REPORTSubmitted to the Department of Computer Science & Engineering in the                                                  FACULTY OF ENGINEERING & TECHNOLOGYIn partial fulfillment of the requirements for the award of the degreeOfMASTER OF TECHNOLOGYINCOMPUTER SCIENCE & ENGINEERINGAPRIL 2016
CERTIFICATECertified that this project report titled “SECURITY OPTIMIZATION OF DYNAMIC NETWORKS WITH PROBABILISTIC GRAPH MODELING AND LINEAR PROGRAMMING” is the bonafide work of Mr. _____________Who carried out the research under my supervision Certified further, that to the best of my knowledge the work reported herein does not form part of any other project report or dissertation on the basis of which a degree or award was conferred on an earlier occasion on this or any other candidate.Signature of the Guide                                                                         Signature of the H.O.DName                                                                                                                      Name
DECLARATIONI hereby declare that the project work entitled “SECURITY OPTIMIZATION OF DYNAMIC NETWORKS WITH PROBABILISTIC GRAPH MODELING AND LINEAR PROGRAMMING” Submitted to BHARATHIDASAN UNIVERSITY in partial fulfillment of the requirement for the award of the Degree of MASTER OF SCIENCE IN COMPUTER SCIENCE is a record of original work done by me the guidance of  Prof.A.Vinayagam M.Sc., M.Phil., M.E., to the best of my knowledge, the work reported here is not a part of any other thesis or work on the basis of which a degree or award was conferred on an earlier occasion to me or any other candidate.                                                                                                        (Student Name)                                                                                                           (Reg.No)Place:Date:
ACKNOWLEDGEMENTI am extremely glad to present my project “SECURITY OPTIMIZATION OF DYNAMIC NETWORKS WITH PROBABILISTIC GRAPH MODELING AND LINEAR PROGRAMMING” which is a part of my curriculum of third semester Master of Science in Computer science. I take this opportunity to express my sincere gratitude to those who helped me in bringing out this project work.I would like to express my Director, Dr. K. ANANDAN, M.A.(Eco.), M.Ed.,  M.Phil.,(Edn.), PGDCA., CGT., M.A.(Psy.) of who had given me an opportunity to undertake this project.I am highly indebted to Co-Ordinator Prof. Muniappan Department of Physics and thank from my deep heart for her valuable comments I received through my project.I wish to express my deep sense of gratitude to my guide                                                  
Prof. A.Vinayagam M.Sc., M.Phil., M.E., for her immense help and encouragement for successful completion of this project.I also express my sincere thanks to the all the staff members of Computer science for their kind advice.And last, but not the least, I express my deep gratitude to my parents and friends for their encouragement and support throughout the project.CHAPTER 11.1 ABSTRACT:Securing the networks of large organizations is technically challenging due to the complex configurations and constraints. Managing these networks requires rigorous and comprehensive analysis tools. A network administrator needs to identify vulnerable configurations, as well as tools for hardening the networks. Such networks usually have dynamic and fluidic structures, thus one may have incomplete information about the connectivity and availability of hosts. In this paper, we address the problem of statically performing a rigorous assessment of a set of network security defense strategies with the goal of reducing the probability of a successful large-scale attack in dynamically changing and complex network architecture. We describe a probabilistic graph model and algorithms for analyzing the security of complex networks with the ultimate goal of reducing the probability of successful attacks. Our model naturally utilizes a scalable state-of-the-art optimization technique called sequential linear programming that is extensively applied and studied in various engineering problems. In comparison to related solutions on attack graphs, our probabilistic model provides mechanisms for expressing uncertainties in network configurations, which is not reported elsewhere. We have performed comprehensive experimental validation with real-world network configuration data of a sizable organization.
1.2 INTRODUCTIONBRACER: A Distributed Broadcast Protocolin Multi-Hop Cognitive Radio Ad HocNetworks with Collision AvoidanceYi Song and Jiang Xie, Senior Member, IEEEAbstract—Broadcast is an important operation in wireless ad hoc networks where control information is usually propagated asbroadcasts 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 hocnetworks, different unlicensed users may acquire different available channel sets. This non-uniform spectrum availability imposesspecial design challenges for broadcasting in CR ad hoc networks. In this paper, a fully-distributed Broadcast protocol in multi-hopCognitive Radio ad hoc networks with collision avoidance, BRACER, is proposed. In our design, we consider practical scenarios thateach 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 broadcastingsequences and scheduling schemes, our proposed broadcast protocol can provide very high successful broadcast ratio while achievingvery short average broadcast delay. It can also avoid broadcast collisions. To the best of our knowledge, this is the first work thataddresses the unique broadcasting challenges in multi-hop CR ad hoc networks with collision avoidance.Index Terms—Cognitive radio ad hoc networks, distributed broadcast, channel hopping, broadcast collision avoidanceÇ1 INTRODUCTIONCOGNITIVE radio (CR) technology has been proposed asan enabling solution to alleviate the spectrum underutilizationproblem [1]. With the capability of sensing the frequencybands in a time and location-varying spectrumenvironment and adjusting the operating parameters basedon the sensing outcome, CR technology allows an unlicenseduser (or, secondary user (SU)) to exploit those frequencybands unused by licensed users (or, primary users)in an opportunistic manner [2]. Secondary users can form aCR infrastructure-based network or a CR ad hoc network.Recently, CR ad hoc networks have attracted plentifulresearch attention due to their various applications [3], [4].Broadcast is an important operation in ad hoc networks,especially in distributed multi-hop multi-channel networks.Control information exchange among nodes, such as channelavailability and routing information, is crucial for therealization of most networking protocols in an ad hoc network.This control information is often sent out as networkwidebroadcasts, messages that are sent to all other nodes ina network. In addition, some exigent data packets such asemergency messages and alarm signals are also deliveredas network-wide broadcasts [5]. Due to the importance ofthe broadcast operation, in this paper, we address thebroadcasting issue in multi-hop CR ad hoc networks. Sincebroadcast messages often need to be disseminated to all destinationsas quickly as possible, we aim to achieve very highsuccessful broadcast ratio and very short broadcast delay.The broadcasting issue has been studied extensively intraditional ad hoc networks [6], [7], [8], [9]. However, unliketraditional single-channel or multi-channel ad hoc networkswhere the channel availability is uniform, in CR ad hoc networks,different SUs may acquire different sets of availablechannels. This non-uniform channel availability imposesspecial design challenges for broadcasting in CR ad hoc networks.First of all, for traditional single-channel and multichannelad hoc networks, due to the uniformity of channelavailability, all nodes can tune to the same channel. Thus,broadcast messages can be conveyed through a single commonchannel which can be heard by all nodes in a network.However, in CR ad hoc networks, the availability of a commonchannel for all nodes may not exist. More importantly,before any control information is exchanged, a SU isunaware of the available channels of its neighboring nodes.Therefore, broadcasting messages on a global commonchannel is not feasible in CR ad hoc networks.To further illustrate the challenges of broadcasting in CRad hoc networks, we consider a single-hop scenario shownin Fig. 1, where node A is the source node. For traditionalsingle-channel and multi-channel ad hoc networks, asshown in Fig. 1a, nodes can tune to the same channel (e.g.,channel 1) for broadcasting. Thus, node A only needs onetime slot to let all its neighboring nodes receive the broadcastmessage in an error-free environment. However, in CRad hoc networks where the channel availability is heterogeneousand SUs are unaware of the available channels of_ Y. Song is with the Department of Electrical Engineering and ComputerScience, Wichita State University, Wichita, KS 67260.E-mail: yi.song@wichita.edu._ J. Xie is with the Department of Electrical and Computer Engineering,University of North Carolina at Charlotte, 9201 University City Blvd.,Charlotte, NC 28223-0001. E-mail: linda.xie@uncc.edu.Manuscript received 22 Feb. 2012; revised 22 Apr. 2014; accepted 20 May2014. Date of publication 4 June 2014; date of current version 29 Jan. 2015.For information on obtaining reprints of this article, please send e-mail to:reprints@ieee.org, and reference the Digital Object Identifier below.Digital Object Identifier no. 10.1109/TMC.2014.2328998IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 3, MARCH 2015 5091536-1233 _ 2014 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.each other, as shown in Fig. 1b, node A may have to usemultiple channels for broadcasting and may not be able tofinish the broadcast within one time slot. In fact, the exactbroadcast delay for all single-hop neighboring nodes to successfullyreceive the broadcast message in CR ad hoc networksrelies on various factors (e.g., channel availabilityand the number of neighboring nodes) and it is random.Furthermore, since multiple channels may be used forbroadcasting and the exact time for all single-hop neighboringnodes to successfully receive the broadcast message israndom, to avoid broadcast collisions (i.e., a node receivesmultiple copies of the broadcast message simultaneously) ismuch more complicated in CR ad hoc networks, as comparedto traditional ad hoc networks. In traditional ad hocnetworks, numerous broadcast scheduling schemes are proposedto reduce the probability of broadcast collisions whileoptimizing the network performance [10], [11], [12], [13],[14], [15]. All these proposals are on the basis that all nodesuse a single channel for broadcasting and the exact delayfor a single-hop broadcast is one time slot. However, in CRad hoc networks, without the information about the channelused for broadcasting and the exact delay for a single-hopbroadcast, to predict when and on which channel a broadcastcollision occurs is extremely difficult. Hence, to designa broadcast protocol which can avoid broadcast collisions,as well as provide high successful broadcast ratio and shortbroadcast delay is a very challenging issue for multi-hopCR ad hoc networks under practical scenarios. Simplyextending existing broadcast protocols to CR ad hoc networkscannot yield the optimal performance.Currently, research on broadcasting in multi-hop CRad hoc networks is still in its infant stage. There are onlylimited papers addressing the broadcasting issue in CRad hoc networks [16], [17], [18], [19]. However, in [16]and [17], the global network topology and the availablechannel information of all SUs are assumed to be known.Additionally, in [17], a common signaling channel for thewhole network is employed which is also not practical.These two papers adopt impractical assumptions whichmake them inadequate to be used in practical scenarios.In [18], a Quality-of-Service (QoS)-based broadcast protocolunder blind information is proposed. However, thisscheme does not consider optimizing the network performance.Moreover, it ignores the broadcast collision issue.Other proposals aiming to locally establish a commoncontrol channel may also be considered for broadcasting[20], [21], [22], [23]. However, these proposals need a-priorichannel availability information of all SUs which isusually obtained via broadcasts. In addition, althoughsome schemes on channel hopping in CR networks can beused for finding a common channel between two nodes[24], [25], [26], they still suffer various limitations andcannot be used in broadcast scenarios. In [24] and [25],the proposed channel hopping schemes cannot guaranteerendezvous under some special circumstances. In addition,one of the proposed schemes in [24] only workswhen two SUs have exactly the same available channelsets. Furthermore, in [26], a jump-stay based channel hoppingalgorithm is proposed for guaranteed rendezvous.However, the expected rendezvous time for the asymmetricmodel (i.e., different users have different availablechannels) is of polynomial complexity with respect to thetotal number of channels. Thus, it is unsuitable for broadcastscenarios in CR ad hoc networks where channelavailability is usually non-uniform and short broadcastdelay is often required. Other channel hopping algorithmsexplained in [27] require tight time synchronizationwhich is also not feasible before any controlinformation is exchanged.In this paper, a fully-distributed broadcast protocol in amulti-hop CR ad hoc network, BRACER, is proposed. Weconsider practical scenarios in our design: 1) no global andlocal common control channel is assumed to exist; 2) theglobal network topology is not known; 3) the channel informationof any other SUs is not known; 4) the available channelsets of different SUs are not assumed to be the same;and 5) tight time synchronization is not required. Our proposedBRACER protocol can provide very high successfuldelivery ratio while achieving very short broadcast delay. Itcan also avoid broadcast collisions. To the best of ourknowledge, this is the first work that addresses the broadcastingchallenges specifically in multi-hop CR ad hoc networkswith a solution for broadcast collision avoidance.The remainder of this paper is organized as follows.In Section 2, the proposed broadcast protocol for multihopCR ad hoc networks, BRACER, is presented. Thederivation of an important system parameter is given inSection 3. Two implementation issues of the proposedprotocol are further discussed in Section 4. Simulationresults are shown in Section 5, followed by the conclusionsin Section 6.2 THE PROPOSED BRACER PROTOCOLIn this section, we introduce the proposed broadcast protocolfor multi-hop CR ad hoc networks, BRACER. There arethree components of the proposed BRACER protocol: 1) theconstruction of the broadcasting sequences; 2) the distributedbroadcast scheduling scheme; and 3) the broadcast collisionavoidance scheme. We assume that a time-slottedsystem is adopted for SUs, where the length of a time slot islong enough to transmit a broadcast packet [28]. In addition,we assume that the locations of SUs are static. We alsoassume that each SU knows the locations of its all two-hopneighbors. We claim that this is a more valid assumptionthan the knowledge of global network topology. We providea detailed discussion on this issue in Section 4. In therest of the paper, we use the term “sender” to indicate a SUwho has just received a message and will rebroadcast themessage. In addition, we use the term “receiver” to indicatea SU who has not received the message. The notations usedin our protocol design are listed in Table 1.Fig. 1. The single-hop broadcast scenario.510 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 3, MARCH 20152.1 Construction of the Broadcasting SequencesThe broadcasting sequences are the sequences of channelsby which a sender and its receivers hop for successfulbroadcasts. First of all, we consider the single-hop broadcastscenario. As explained in Section 1, due to the nonuniformchannel availability in CR ad hoc networks, a SUsender may have to use multiple channels for broadcastingin order to let all its neighboring nodes receive thebroadcast message. Accordingly, the neighboring nodesmay also have to listen to multiple channels in order toreceive the broadcast message. Hence, the first issue todesign a broadcast protocol is which channels should beused for broadcasting. One possible method is to broadcaston all the available channels of the SU sender. However,this method is quite costly in terms of the broadcastdelay when the number of available channels is large.Therefore, we propose to select a subset of available channelsfrom the original available channel set of each SU.First, the available channels of each SU are ranked basedon the channel indexes. Then, each SU selects the first wchannels from the ranked channel list and forms a downsizedavailable channel set. The value of w needs to becarefully designed to ensure that at least one commonchannel exists between the downsized available channelsets of the SU sender and each of its neighboring nodes.The detailed derivation process to obtain a proper w isgiven in Section 3. Based on the derivation process, eachSU can calculate the value of w of its own and its one-hopneighbors before a broadcast starts.On the other hand, the second issue is the sequences ofthe channels by which a sender and its receivers hop forsuccessful broadcasts. In this paper, we design differentbroadcasting sequences for a SU sender and its receivers toguarantee a successful broadcast in the single-hop scenarioas long as they have at least one common channel. Thesender hops and broadcasts a message on each channel in atime slot following its own sequence. On the other hand, thereceiver hops and listens on each channel following its ownsequence. The pseudo-codes for constructing the broadcastingsequences are shown in Algorithms 1 and 2. wðvÞ is theinitial w of node v.Algorithm 1: Construction of the Broadcasting SequenceBSv for a SU Sender v.Input: wðvÞ; Lv.Output: BSv.1 randomize the order of elements in Lv;2 BSv ?; = _ initialization _ =3 i 1;4 while i _ wðvÞ2 do5 BSvðiÞ Lvðði mod wðvÞÞ þ 1Þ;6 i i þ 1; = _ repeat Lv for wðvÞ times _ =7 return BSv;Algorithm 2: Construction of the Broadcasting SequenceRSv for a SU Receiver v.Input: wðvÞ; Lv.Output: RSv.1 randomize the order of elements in Lv;2 RSv ?; = _ initialization _ =3 j 1;4 while i _ wðvÞ do5 i 16 while j _ wðvÞ2 do7 RSvðði _ 1ÞwðvÞ þ jÞ LvðiÞ;8 j j þ 1; = _ repeat an element forwðvÞ times _ =9 i i þ 1; = _ repeat for every element inLðvÞ _=10 return RSv;From Algorithms 1 and 2, for a SU sender, it hops periodicallyon the w available channels for w periods (i.e., w2time slots). For each receiver, it stays on one of the w availablechannels for w time slots. Then, it repeats for everychannel in the w available channels. Fig. 2 gives an exampleto illustrate the construction of the broadcastingsequences for SU senders and receivers. In Fig. 2, thedownsized available channel set of a sender and a receiveris f1; 2g and f2; 3; 4g, respectively. Based on Algorithm 1,the broadcasting sequence of the sender is f2; 1; 2; 1g. Similarly,based on Algorithm 2, the broadcasting sequence ofthe receiver is f4; 4; 4; 3; 3; 3; 2; 2; 2g. Since a sender usuallydoes not know the length of the broadcasting sequence ofthe receiver, it broadcasts the message following its broadcastingsequence for bM2w2 cþ1 cycles, where M is the totalnumber of channels. In this way, the total length of timeslots that the sender broadcasts is bound to be longer thanTABLE 1Notations Used in the ProtocolNðvÞ The set of the neighboring nodesof node vNðNðvÞÞ The set of the neighbors of the neighboringnodes of node vdðv; uÞ The Euclidean distance betweennode v and urc The radius of the transmission rangeof each nodej _ j The number of elements in a setLv The downsized available channelset of node vwðvÞ The size of the downsized available channelset of node vC The set of the initial w of intermediate nodesBSv The broadcasting sequence for a sender vRSv The broadcasting sequence for a receiver vDSv The default sequence of a sender vstv The starting time slot of a sender vrtv The time slot that a receiver vreceives the messageRv The random number assigned to areceiver v by its senderFig. 2. An example of the broadcasting sequences.SONG AND XIE: BRACER: A DISTRIBUTED BROADCAST PROTOCOL IN MULTI-HOP COGNITIVE RADIO AD HOC NETWORKS… 511one cycle of the receiver’s broadcasting sequence. Asshown in Fig. 2, the shaded part represents a successfulbroadcast.Since every SU calculates the initial value of w based onits local information and the derivation process in Section 3,different SUs may obtain different values of w. We furtherdenote ws and wr as the w used by the sender and thereceiver to construct their broadcasting sequences, respectively.Note that ws and wr may not necessarily be the sameas the initial w calculated by each SU. They also depend onthe initial w of its neighboring nodes. The following theoremgives an upper-bound on the single-hop broadcast delay.Theorem 1. If ws _ wr, the single-hop broadcast is a guaranteedsuccess within w2rtime slots as long as the sender and thereceiver have at least one common channel between their downsizedavailable channel sets.Proof. Based on Algorithm 1, a SU sender broadcasts onall the channels in its downsized available channel setin ws consecutive time slots. Based on Algorithm 2, aSU receiver listens to every channel in its downsizedavailable channel set for wr consecutive time slots. Ifws_wr, during the wr consecutive time slots for whichthe SU receiver stays on the same channel, every channelof the SU sender must appear at least once. Thus, aslong as the SU sender and the receiver have at least onecommon channel, there must exists a time slot that thesender and the receiver hop on the same channel duringone cycle of the broadcasting sequence of thereceiver (i.e., w2r). Since we let the total length of timeslots that the sender broadcasts be longer than one cycleof the receiver’s broadcasting sequence, the broadcast isguaranteed to be successful. tuThen, how to determine ws and wr? From Theorem 1,ws _ wr is a sufficient condition of a single-hop successfulbroadcast. Therefore, in order to satisfy this condition, aproper wr needs to be selected by any SU who has notreceived the broadcast message to ensure the reception ofthe broadcast message sent from any potential neighbor.Since wr depends on ws and a SU receiver usually does notknow which neighboring node is sending until it receivesthe broadcast message, it selects the largest initial w of all itsone-hop neighbors as its wr. That is, for a SU receiver v,wrðvÞ ¼ maxfwðuÞju 2 NðvÞg. On the other hand, the senderuses its calculated initial w as ws to broadcast. Therefore, thews selected by the actual sender is bound to be smaller thanor equal to this wr. Thus, according to Theorem 1, the single-hop broadcast is a guaranteed success as long as thesender and its receiver have at least one common channelbetween their downsized available channel sets.To illustrate the above discussed operation, we considera multi-hop scenario shown in Fig. 3. The initial w calculatedby each SU before the broadcast starts based on itslocal information are shown. Every node also calculatesthe initial w of its one-hop neighbors. Without loss of generality,node A is assumed to be the source node. Based onTheorem 1, the values of wr employed by each receiver canbe obtained. For instance, since node B knows the initial wof its neighbors (i.e., wðAÞ ¼ 3, wðDÞ ¼ 4, and wðFÞ ¼ 4), itselects 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, andwrðFÞ ¼ 5. Then, all nodes except node A use their wr toconstruct the broadcasting sequences based on Algorithm2. On the other hand, since each sender uses its calculatedinitial w as ws, we have wsðAÞ ¼ 3, wsðBÞ ¼ 3;wsðCÞ ¼ 5;wsðDÞ ¼ 4; wsðEÞ ¼ 2, and wsðFÞ ¼ 4. Then, if a node needsto broadcast a message, it uses its ws to construct thebroadcasting sequence based on Algorithm 1.2.2 The Distributed Broadcast Scheduling SchemeNext, we consider the broadcast scheduling issue in themulti-hop broadcast scenario. The goal of the proposed distributedbroadcast scheduling scheme is to intelligentlyselect SU nodes for rebroadcasting in order to achieve theshortest broadcast delay.First, Fig. 4 shows the simulation results using theparameters given in Section 5. From Fig. 4, we observe thatthe single-hop broadcast delay increases when w increases.Therefore, in a multi-hop broadcast scenario, if there aremultiple intermediate nodes with the same child node, theintermediate node with the smallest w is selected torebroadcast. If there are more than one intermediate nodewith the smallest w, all these nodes should rebroadcastand a broadcast collision avoidance scheme (which isexplained in detail in Section 2.3) is executed before theyrebroadcast the message. The pseudo-code of the proposedscheduling scheme is shown in Algorithm 3, where node vhas just received the broadcast message from node q andneeds to decide whether to rebroadcast. Node q includesthe calculated initial w of its one-hop neighbors in thebroadcast message. Algorithm 3 indicates that each SUshould know the locations of its one-hop neighbors (inorder to obtain NðvÞ) and its two-hop neighbors (in orderto obtain NðqÞ and dðu; kÞ). Once a node receives the message,it executes Algorithm 3 to decide whether it shouldrebroadcast or not. If it needs to rebroadcast, it uses its calculatedinitial w as ws to construct the broadcastingFig. 3. A multi-hop broadcast scenario.Fig. 4. The single-hop broadcast delay when ws ¼ wr ¼ w.512 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 3, MARCH 2015sequence based on Algorithm1. Thus, as illustrated inFig. 3, the message deliveries are shown by the arrows.Algorithm 3: The Pseudo-Code of the BroadcastScheduling Scheme for a SU Sender v.Input: q;NðvÞ;NðNðvÞÞ; fwðuÞju 2 NðqÞg.Output: Decision of rebroadcasting.1 C fwðvÞg;2 If fkjk 2 ðNðvÞ _ NðvÞ \ NðqÞÞg 6¼ ? then = _ v has atleast one receiver _ =3 foreach k do4 if fuju 2 NðqÞ; dðu; kÞ _ rc; u 6¼ vg 6¼ ? then= _ there are multiple paths fromq ! k _ =5 foreach u do6 C {C;wðuÞg;7 if wðvÞ ¼ minC and jfeje ¼ minCgj ¼ 1then = _ v is the only node with thesmallest w _ =8 return TRUE;9 else if wðvÞ ¼ minC and jfeje ¼ minCgj > 1then = _ v is one of the multiple nodeswith the same smallest w _ =10 run Algorithm 4;11 return TRUE;12 else13 return FALSE; = _ v does notrebroadcast _ =14 else15 return TRUE; = _ v rebroadcaststhe message _ =16 else17 return FALSE;From the above design, it is noted that each SU (eithersending or receiving) follows the same rules and no centralizedentity or prior information about the sender isrequired. Thus, the proposed broadcast scheduling schemeis fully distributed. In addition, since the node with thesmallest w is selected for rebroadcasting, the broadcastdelay is the shortest. Moreover, because only a subset ofintermediate nodes are selected to rebroadcast, the numberof intermediate nodes that need to forward the message isreduced. Thus, the probability that multiple senders broadcastingto the same receiver simultaneously can be reduced.Hence, the proposed broadcast scheduling scheme alsocontributes to the broadcast collision avoidance.2.3 The Broadcast Collision Avoidance SchemeFrom Algorithm 3, if there are multiple intermediate nodeswith the same child node, only the intermediate node withthe smallest w should rebroadcast. However, if more thanone intermediate node with the same smallest w, all theseintermediate nodes should rebroadcast and a broadcast collisionmay occur if these nodes deliver the messages on thesame channel at the same time. For instance, in the exampleshown in Fig. 5 where node A is the source node, node Band C have the same w, which may lead to a broadcast collisionwhen they rebroadcast simultaneously.Most broadcast collision avoidance methods in traditionalad hoc networks assign different time slots to differentintermediate nodes to avoid simultaneous transmissions.However, as explained in Section 1, these methods cannotbe applied to CR ad hoc networks because the exact time forthe intermediate nodes to receive the broadcast message israndom. As a result, to assign different time slots for differentintermediate nodes is very challenging. In addition,since the intermediate nodes use multiple channels forbroadcasting, the channel on which the broadcast collisionoccurs is also unknown. To the best of our knowledge, noexisting collision avoidance scheme can address these challengesin CR ad hoc networks.In this paper, we propose a broadcast collision avoidancescheme for CR ad hoc networks. The main idea is to prohibitintermediate nodes from rebroadcasting on the same channelat the same time. Our proposed broadcast collisionavoidance scheme works in a scenario where the intermediatenodes have the same parent node, as shown in Fig. 5.The procedure of the proposed broadcast collision avoidancescheme 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 includesits own original available channel set in the message.Hence, if an intermediate node receives the message, itobtains the original available channel information of itsparent node. Then, the intermediate node uses the first wavailable channels of its parent node to generate a defaultsequence, where w is its own calculated initial w (whichmay not be the same as the initial w of its parent node). Ifa channel in the default sequence is not available for thisintermediate node, a void channel is assigned to replacethe corresponding channel. For instance, if node B and Cboth obtain w¼3 and the original available channels ofnode A, B, and C are f1; 2; 3; 4; 5g, f2; 3; 4; 5g, and f1; 3;4; 6g, respectively, node B and C only use the first threeavailable channels of node A to generate their defaultsequences. Therefore, the default sequence of node B isf0; 2; 3g and the default sequence of node C is f1; 0; 3g,where 0 means a void channel. A node does not send anythingon a void channel.Step 2 circular shifting the default sequence with a randomnumber. Apart from the available channel set, the sourcenode also includes a distinctive integer for each intermediatenode v randomly selected from ½1; wðvÞ_. If there aremore than wðvÞ intermediate nodes, the parent node randomlyselects wðvÞ of them and assigns a random integer.Only those intermediate nodes that acquire the random integerwill rebroadcast the packet. Then, each intermediatenode generates a new sequence from its default sequenceFig. 5. The broadcast scenario where a broadcast collision may occur.SONG AND XIE: BRACER: A DISTRIBUTED BROADCAST PROTOCOL IN MULTI-HOP COGNITIVE RADIO AD HOC NETWORKS… 513using circular shift and the random integer. If we denote thedefault sequence as DS and the random integer as R, theintermediate node performs circular shift on the DS for Rtimes (there is no difference of right-shift or left-shift). Forinstance, if node B and C get 3 and 1 as their random integers,respectively, the new sequences they generate fromleft-handed circular shift are f0; 2; 3g and f0; 3; 1g,respectively.Step 3 forming the broadcasting sequence. Denote the startingtime slot of the source node’s broadcasting sequence as st andthe time slot when an intermediate node receives the broadcastmessage as rt. The source node includes its st in thebroadcast message. Then, the intermediate node performs circularshift on the new sequence generated from Step 2 foranother (rt _ st þ 1) times. It repeats that sequence for wðvÞtimes to forma cycle of its broadcasting sequence.The pseudo-code of the broadcast collision avoidancescheme is shown in Algorithm 4, where q is the source nodeand Circshift() is the function of circular shift. To further elaboratethe scheme, Fig. 6 shows an example of the proposedbroadcast collision avoidance scheme. Without loss of generality,the starting time slot of the source node is 1. When nodeB and C do not receive the broadcast message, they hopthrough the channels based on the broadcasting sequencesgenerated from Algorithm 2. Then, node B and C receive thebroadcast message at time slot 4 and 1, respectively. Based onAlgorithm 4 and if the random integers for node B and C are3 and 1, respectively, node B forms the broadcastingsequence as f2; 3; 0; 2; 3; 0; 2; 3; 0g and node C forms thebroadcasting sequence as f3; 1; 0; 3; 1; 0; 3; 1; 0g. Then, theystart rebroadcasting from time slots 5 and 2 using the broadcastingsequences, respectively. The underlined channels arethose a node hops on if it starts from time slot 1.Algorithm 4: The Pseudo-Code of the BroadcastCollision Avoidance Scheme for SU v.Input: q;Lq; Lv; stq; rtv;Rv; wðvÞ.Output: BS0v.1 BS0v?; = _ initialization _ =2 i 1;3 l 1;4 While i _ wðvÞ do = _ generating adefault sequence _ =5 j 16 While j _ wðvÞ do7 If LvðiÞ ¼ LqðjÞ then8 DSvðjÞ LqðjÞ;9 Tv Circshift(DSv;Rv ); = _ circular shifting _ =10 While l _ wðvÞ2 do = _ forming a broadcastsequence _ =11 BS0vðlÞ Tvðl þ ðrtv _ stqÞ þ 1 mod wðvÞÞ;12 l l þ 1;13 return BS0v;Therefore, by constructing the broadcasting sequencesfrom the same channel set (the channel set of the commonparent node, node A) but circular shifting different times fordifferent nodes, the intermediate nodes are guaranteed notto send on the same channel at the same time. Thus, broadcastcollisions can be avoided. In addition, the proposedbroadcast collision avoidance scheme still works when intermediatenodes are not synchronized. They can be synchronizedbased on the time stamp received from the commonparent node. In this way, time slots of the intermediate nodesare perfectly aligned. Then, broadcast collisions are resolved.A tradeoff of the proposed broadcast collision avoidancescheme is that less available channels are used for broadcastingbecause some void channels may be assigned. However,the benefit (e.g., the increase of the successful broadcastratio) gained from eliminating broadcast collisions is greaterthan the loss of a very few number of channels. Hence, theonly issue left is the derivation of the initial w, which is introducedin Section 3.2.4 Protocol Flow ChartIn this section, we summarize the procedure of the proposedBRACER protocol. Fig. 7 shows the flow chart of theBRACER protocol. As shown in Fig. 7, before a broadcaststarts, every SU node first calculates its own initial w andthe initial w of its one-hop neighboring nodes using thetwo-hop location information. If this node is the sourcenode, it uses its own initial w as its ws and constructs thebroadcasting sequence based on Algorithm 1. Then, it hopsand broadcasts a message on each channel during one timeslot following its sequence. On the other hand, if this nodeis not the source node, it is by default a receiver. Then, ituses the maximum w of its one-hop neighboring nodes asits wr and constructs the broadcasting sequence based onAlgorithm 2. It hops and listens on each channel during oneFig. 6. An example of the proposed broadcast collision avoidancescheme.Fig. 7. The flow chart of the proposed BRACER protocol.514 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 3, MARCH 2015time slot following its sequence. If the node receives thebroadcast message from a sender, it runs the broadcastscheduling scheme based on Algorithm 3 to determinewhether it needs to rebroadcast this message. If it needs torebroadcast and there is only one smallest w, it uses its ownw as ws and runs Algorithm 1 to rebroadcast. If it needs torebroadcast and there are more than one smallest w, itruns the broadcast collision avoidance scheme based onAlgorithm 4 to rebroadcast the message.3 THE DERIVATION OF THE VALUE OF wIn this section, we first introduce a network model weconsider. Then, based on this model, we present the derivationprocess of the size of the downsized availablechannel set w.3.1 The Network ModelIn this paper, we consider a CR ad hoc network where NSUs and K primary users (PUs) co-exist in an a _ a area.PUs are evenly distributed within the area. The SUs opportunisticallyaccess M licensed channels. Each SU has a circulartransmission range with a radius of rc. The SUswithin the transmission range are considered as the neighboringnodes of the corresponding SU. That is, only whena SU receiver is within the transmission range of a SUtransmitter, the signal-to-noise ratio (SNR) at the SUreceiver 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 broadcast collisionsas the reason for the packet error. We claim that thisis a valid assumption in most broadcast scenarios [6], [7],[8], [9], [10], [11], [12], [14], [15], [16], [17], [29], [30].Each SU also has a circular sensing range with a radiusof rs. That is, if a PU is currently active within the sensingrange of a SU, the corresponding SU is able to detect itsappearance. Since different SUs have different local sensingranges which include different PUs, their acquiredavailable channels may be different [31], [32]. In addition,because the available channels of a SU are obtained basedon the sensing outcome within the sensing range, a SU isnot allowed to communicate with other SUs outside itssensing range since it may mistakenly use an occupiedchannel 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 activity as an ON/OFFprocess, where the length of the ON period is the length ofa PU packet. The length of the ON period and the OFFperiod can follow arbitrary distributions. We assume thateach PU randomly selects a channel from the spectrumband to transmit one packet which consists of multipletime slots. Moreover, because PUs at different locationscan claim any channels for communications, the packetson the same channel do not necessarily belong to the samePU. This is a more practical scenario, as compared to somepapers which assume that each channel is associated witha different PU. Under such a practical scenario, only thosePUs that are within the sensing range of a SU and areactive during the broadcast process contribute to theunavailable channels of the SU [18].3.2 The Derivation of the Value of wAs explained in Section 2, the value of w is essential to ensurea successful single-hop broadcast. Denote the probability ofa successful single-hop broadcast as PsuccðwÞ, where PsuccðwÞis a function of w. Our goal is to obtain an appropriate w thatsatisfies the condition: PsuccðwÞ        1 _ _, where _ is a smallpre-defined value. From Theorem 1, the condition that atleast one common channel exists between the downsizedavailable channel sets of a SU pair is a necessary conditionfor a successful single-hop broadcast. Therefore, if we denotethe source SU of a single-hop broadcast as S0 and the neighborsof S0 as fS1; S2; . . . ; SHg, where H is the number ofneighbors, PsuccðwÞ is equal to the probability that there is atleast one common channel between S0 and each of its neighborsin their downsized available channel sets.3.2.1 The Single-Pair ScenarioWe first calculate the probability that there is at least onecommon channel between the downsized available channelsets of S0 and one of its neighbors Si. The relative locationsof the two SUs and their sensing ranges are shown inFig. 8a. As illustrated in Fig. 8a, sensing ranges are dividedinto three areas: A1, A2, and A3. Note that PUs in differentareas have different impact on the channel availability ofthe two SUs. For instance, if a PU is active within A3, thechannel used by this PU is unavailable for both SUs. However,if a PU is active within A1, the channel used by this PUis only unavailable for S0. Thus, we first calculate the probabilitythat a channel is available within each area,Pk; k 2 ½1; 2; 3_. The size of the total network area is denotedas AL (i.e., AL ¼ a2). Since the locations of PUs are evenlydistributed, the probability that p PUs are within Ak isPrðpÞ ¼Kp_ _AkAL_ _p AL_AkAL_ _K_p; (1)where ðKp Þ represents the total combinations of K choosingp. In addition, we define the probability that a PU isactive, r, asr ¼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, theFig. 8. The single-hop broadcast scenario.SONG AND XIE: BRACER: A DISTRIBUTED BROADCAST PROTOCOL IN MULTI-HOP COGNITIVE RADIO AD HOC NETWORKS… 515probability that there are b PUs active isPrðb j pÞ ¼pb_ _rbð1 _ rÞp_b: (3)Furthermore, given that there are p PUs and b active PUswithin Ak, the probability that there are c available channelsis denoted as Prðc j p; bÞ. Since the number of availablechannels is only related to the number of active PUs, c isindependent of p. In addition, since an active PU randomlyselects a channel from M channels in the band, Prðc j p; bÞis equivalent to the probability that there are exactly cempty boxes given that b balls are randomly put into atotal 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 j p; bÞ can be expressed asPrðc j p; bÞ ¼Mc_ _ðM _ cÞSðb;M _ cÞMb ; c 2 ½maxð0;M _ bÞ;M_;(4)where Sðb;M_cÞ is the Stirling number of the second kind.In addition, Sðb;M_cÞ is defined asSðb;M_cÞ ¼1ðM_cÞ!XM_ci¼0 ð_1Þi M_ci_ _ðM_c_iÞb: (5)Hence, the probability that there are c available channelsand there are p PUs and b active PUs within Ak is the productof (1), (3), and (4). Then, the probability that a channel isavailable within Ak is obtained from (6).Pk ¼1MXKp¼0Xpb¼0XMc¼maxð0;M_bÞc Mc_ _ðM _ cÞ!Sðb;M _ cÞMbpb_ _rbð1 _ rÞp_b Kp_ _AkAL_ _p AL _ AkAL_ _K_p:(6)Next, we consider the relationship between the downsizedavailable channel sets of the two SUs. In our derivation,we only consider the scenario where the senderand its receiver have the same w (i.e., ws ¼ wr). Ifwr > ws, the channels after the first ws channels do notaffect the number of common channels. Thus, the derivationprocess is the same. Fig. 9 shows an example of thechannel availability status of two SUs when wðS0Þ ¼ 3,where a shaded square indicates an idle channel and awhite square indicates a busy channel. A square with across means that a channel can be either idle or busy.Since each SU only selects the first w available channelsto form a downsized available channel set, theavailability status of the channels after the first w availablechannels is not specified. Then, without loss of generality,we denote t and h as the index of the lastavailable channel in the downsized available channelsets of S0 and Si, respectively. We first assume thatt _ h. Hence, from channel 1 to t, there are four possiblescenarios of every channel in terms of its availability forthe two SUs. They are: 1) the channel is available forboth SUs (denoted as C1); 2) the channel is unavailablefor both SUs (denoted as C2); 3) the channel is onlyavailable for S0 (denoted as C3); and 4) the channel isonly available for Si (denoted as C4). In addition, fromchannel t þ 1 to h (if t < h), there are two possible scenarios:1) the channel is available for Si but it can be anystatus for S0 (denoted as C5) and 2) the channel isunavailable for Si but it can be any status for S0(denoted as C6). Based on Fig. 8a, the probabilities ofthe 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.Denote Zð0; iÞ as the number of common channelsbetween S0 and Si in their downsized available channelsets. In order to obtain PrðZð0; iÞ¼zÞ, we need to considerall the combinations of the channel status for every channelfrom channel 1 to h. There are two possible cases: 1) t¼hand 2) t<h. For the first case, channel h is a common channelbetween the two SUs. In addition, from channel 1 tochannel 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 channelsin the first case isP0ðhÞ ¼h _ 1z _ 1_ _h _ zw _ z_ _h _ ww _ z_ _PzC1Ph_2wþzC2 Pw_zC3 Pw_zC4 :(7)For the second case, since t<h, the common availablechannels can only be between channel 1 to t. We denotethe number of available channels for Si from channel 1to t as x. Thus, from channel 1 to t, similar to the firstcase, there are z channels in C1; t _ w _ x þ z channels inC2; w _ z channels in C3; and x _ z channels in C4. Inaddition, from channel t þ 1 to h, there are w _ x channelsin C5 and h _ t _ w þ x channels in C6. Therefore,the probability that there are totally z common channelsis obtained from (7).P00 1 ðhÞ ¼ PzC1Pw_zC3Xh_1t¼wXt_wx¼maxð0;wþt_hÞt _ 1w _ 1_ _wz_ _t _ wx _ z_ __h _ t _ 1w _ x _ 1_ _Px_zC4 Pðt_w_xþzÞ C2 ðPC1 þ PC4Þðw_xÞ_ðPC2 þ PC3Þðh_t_wþxÞ:(8)If we switch S0 and Si in Fig. 9, we can obtain the probabilityfor the dual case. Hence, the probability that there are zFig. 9. An example of the channel availability status when w(S0) ¼ 3.516 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 3, MARCH 2015common channels in the second case is expressed in (9).P00ðhÞ ¼ PzC1Pw_zC3Xh_1t¼wXt_wx¼max ð0;wþt _hÞt _ 1w _ 1_ _wz_ _t _ wx _ z_ __h _ t _ 1w _ x _ 1_ _Px_zC4 Pðt_ w_xþzÞ C2 ðPC1 þ PC4Þðw_xÞ_ðPC2 þ PC3Þðh_t_wþxÞþ PzC1Pw_zC4Xh_1t¼wXt_wx¼max ð0;wþt_hÞt _ 1w _ 1_ _wz_ _t _ wx _ z_ __h _ t _ 1w _ x _ 1_ _Px _zC3 Pðt_w_xþzÞ C2 ðPC1 þ PC3Þðw_xÞ_ðPC2 þ PC4Þðh_t_wþxÞ:(9)Therefore, the probability that there are z common channelsfor the first w available channels for each SU isPrðZð0; iÞ ¼ zÞ ¼XMh¼2w_zP0ðhÞ þ P00ðhÞ: (10)Thus, the probability of a successful single-hop broadcastfrom S0 to Si isPsuccðwÞ ¼ 1 _ PrðZð0; iÞ ¼ 0Þ: (11)Fig. 10a shows the analytical and simulation results ofPsuccðwÞ in the single-pair scenario under various w and differentM. To obtain these results, the number of PUs K ¼ 40and the probability that a PU is active r¼0:9. In addition,the side length of the network area a¼10 (unit length) andtwo neighboring SUs are at the border of each other’s sensingrange where rs¼2 (unit length). As shown in Fig. 10a,the simulation results match extremely well with the analyticalresults.3.2.2 The Multi-Pair ScenarioWe extend the above results to a multi-pair scenario, asshown in Fig. 8b where Si and Sj are two neighbors of S0.Based on the knowledge of combination mathematics, theprobability of a successful broadcast in the multi-pair scenarioshown in Fig. 8b isPsuccðwÞ ¼ 1 _ PrðZð0; iÞ ¼ 0Þ _ PrðZð0; jÞ ¼ 0Þþ PrðZð0; i; jÞ ¼ 0Þ;(12)where Prðzð0; i; jÞ ¼ 0Þ is the probability that both Si and Sjdo not have any common channel in the downsized availablechannel sets with S0. Since the other two terms in (12)(i.e., PrðZð0; iÞ ¼ 0Þ and PrðZð0; jÞ ¼ 0Þ) can be obtainedfrom (10), we only need to calculate PrðZð0; i; jÞ ¼ 0Þ.To calculate PrðZð0; i; jÞ¼0Þ, we use the same idea fromthe single-pair scenario. That is, we consider Si and Sjtogether as one new neighboring node. The sensing rangeof the new neighboring node is the union of the sensingranges of the two original nodes (i.e., the shaded area inFig. 8b). Therefore, we can obtain new P1, P2, and P3 for themulti-pair scenario based on the new size of the sensingrange. Moreover, the probabilities of every scenario of thechannel status can also be obtained accordingly. Therefore,by using (7)-(10), we can calculate PrðZð0; i; jÞ ¼ 0Þ. Then,given the locations of the H neighbors, each SU can get theprobability of a successful single-hop broadcast by performingthe same procedure iteratively for H times. Finally, byletting PsuccðwÞ            1 _ _, a proper w can be acquired for S0.Fig. 10a shows the analytical and simulation results ofPsuccðwÞ in the two-pair scenario under various w and differentM.From Fig. 10b, the simulation results match very wellwith the analytical results.4 DISCUSSION ON THE PROPOSED BRACERPROTOCOLIt is noted that our proposed BRACER protocol is particularlydesigned for broadcast scenarios in multi-hop CRad hoc networks without a common control channel. Asdescribed in Sections 1 and 2, there are two implementationissues that are essential to the performance of ourproposed distributed broadcast protocol: 1) the two-hoplocation information; and 2) the time synchronization. Inthis section, we provide a further discussion on thesetwo issues.4.1 Two-Hop Location InformationFrom Section 2, in our proposed BRACER protocol, every SUnode needs the location information of its two-hop neighboringnodes in order to calculate the size of the downsizedavailable channel sets of its one-hop neighboring nodes.Even though the localization issue for CR ad hoc networks isout of the scope of this paper, we hereby introduce severalsolutions to obtain the two-hop location information indetail. Generally speaking, the location information for a traditionalad hoc network can be obtained either from externalpositioning techniques (e.g., Global Positioning System(GPS) [33]) or from some localization algorithms withoutexternal positioning techniques [34], [35]. Hence, GPS is anoption to obtain the location information of the two-hopneighboring nodes in CR ad hoc networks. However, GPSrequires additional hardware and consumes extra energy,which may not be efficient in CR ad hoc networks wherecost and power constraints are often needed.On the other hand, a number of localization algorithmsthat do not rely on GPS for CR ad hoc networks have beenproposed [36], [37]. In these works, the legacy localizationalgorithms proposed for traditional ad hoc networks, suchas time-of-arrival (TOA)-based, angle-of-arrival (AOA)-based, and received-signal-strength (RSS)-based methodsFig. 10. Analytical and simulation results of PsuccðwÞ under various w anddifferentM.SONG AND XIE: BRACER: A DISTRIBUTED BROADCAST PROTOCOL IN MULTI-HOP COGNITIVE RADIO AD HOC NETWORKS… 517are improved and adopted in CR ad hoc networks. Theselocalization algorithms often require the assistance fromcertain special nodes with known location information(named reference nodes). However, all these algorithmsignore the control message exchange issue between the referencenodes and the regular nodes in CR ad hoc networks.The control message exchange issue is either not consideredor simplified by using a common control channel. Based onSection 1, transmitting messages on a global common channelwithout any additional control information is not feasiblein CR ad hoc networks. Therefore, in order to receivethe control message containing the location informationfrom the reference nodes, a communication mechanism thatdoes not rely on any other control information (i.e., underblind information) between the reference nodes and the regularnodes is needed. As mentioned before, in [18], a QoSbasedbroadcast protocol under blind information is proposed.We can use this scheme as the communicationscheme between the reference nodes and the regular nodesto obtain the two-hop location information. Since the broadcastprotocol proposed in [18] can only support QoS provisioning,the successful broadcast ratio and averagebroadcast delay of this scheme for the whole network arenot optimized. Therefore, this scheme is suitable to be usedin the early stage of a broadcast procedure. After everynode in the network acquires the two-hop location information,the proposed BRACER protocol can be executed.4.2 Time SynchronizationFrom Section 1, an advantage of our proposed BRACERprotocol is that it does not require tight time synchronization.This special advantage is essential since tight time synchronizationis extremely difficult to achieve in a realad hoc network system. In this paper, we define tight timesynchronization as the scenario where time slots of differentnodes are precisely aligned. This means that the proposedBRACER protocol can guarantee the successfulreception of a whole broadcast message even if the timeslots of the sender and the receiver have an offset. Denotethe length of the offset as d. Without the loss of generality, dis less than a time slot. Based on Theorem 1, in order toguarantee a successful single-hop broadcast, ws must besmaller than or equal to wr. Thus, we consider the time synchronizationissue under the following two scenarios.4.2.1 Scenario Iws is strictly smaller than wr. If ws < wr and the sender andthe receiver have at least one common channel betweentheir downsized available channel sets, we have the followingtheorem:Theorem 2. If ws < wr, the single-hop broadcast is a guaranteedsuccess within w2rtime slots even if the time slots of the senderand the receiver have an offset.Proof. Similar to the proof of Theorem 1, if ws < wr, duringthe wr consecutive time slots for which the receiver stayson the same channel, every channel of the sender mustappear at least once. More importantly, since d is lessthan a time slot, at least a whole time slot of the commonchannel between the sender and the receiver must becompletely covered by the wr consecutive time slots ofthe common channel. That is, the receiver can hear awhole time slot of the common channel when the senderbroadcasts the message. Thus, a successful single-hopbroadcast is guaranteed. tuFig. 11 shows an example of Scenario 1 where ws < wr.We assume that the time slots of the sender are ahead of thereceiver with an offset of d. As illustrated in Fig. 11, on the9th slot of the sender’s broadcasting sequence, the senderand the receiver are on the same channel (i.e., channel 2). Inaddition, this time slot is completely covered by the threeconsecutive time slots when the receiver is on channel 2.Hence, the broadcast message can be successfully receivedby the receiver.4.2.2 Scenario IIws is equal to wr. If ws ¼ wr, there are two sub-cases: 1)Case 1: a time slot of the common channel is completelycovered by the wr consecutive time slots of the receiver onthe same channel; and 2) Case 2: a time slot of the commonchannel is partially covered by the wr consecutive timeslots of the receiver on the same channel. Fig. 12 shows anexample of Case 1 in Scenario II. Similar to Scenario I, thebroadcast message can still be successfully received even ifan offset exists.On the other hand, Fig. 13 shows an example of Case 2 inScenario II. This case occurs when the time slot of the commonchannel of the sender is partially covered by the firstand the last time slot of the wr consecutive time slots of thereceiver. From the communication theory, if a node onlyreceives a part of a packet, it cannot decode this packet correctlyand will drop it at the physical (PHY) layer. Thus,even if the sender and the receiver have a common channel,the receiver cannot successfully receive the broadcast messagewithin w2rtime slots in Case 2.We provide two simple modifications of our proposedBRACER protocol for this case. The first way is that thereceiver always shift the whole cycle of the broadcastingsequence one slot forward or one slot backward after ithops for one cycle (i.e., w2rtime slots) and has not receivedFig. 12. An example of Case 1 in Scenario II when time slots areunsynchronized.Fig. 11. An example of Scenario I when time slots are unsynchonized.Fig. 13. An example of Case 2 in Scenario II when time slots areunsynchronized.518 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 3, MARCH 2015the broadcast message. At the same time, the total length oftime slots that the sender broadcasts needs to be longer thanthree cycles of the receiver’s broadcasting sequence. That is,the sender broadcasts the message following its broadcastingsequence for b3_M2w2scþ1 cycles. In this way, Case 2becomes Case 1. Then, even if the receiver may not receivethe message within one cycle, it can still successfully receivethe message in the following cycle, as shown in Fig. 14.On the other hand, the second way is that the receiver vselects wrðvÞ to be maxfwðuÞju 2 NðvÞg þ 1, where NðvÞ isthe set of the neighboring nodes of the receiver v. Therefore,the wr of the receiver is always larger than the wsused by the sender. In this way, Case 2 becomesScenario I. Based on Theorem 2, the successful broadcast isguaranteed within w2rtime slots, as shown in Fig. 15. Tosum up, from the above analysis, our proposed BRACERprotocol can be used in an environment where tight timesynchronization is not required.5 PERFORMANCE EVALUATIONIn this section, we evaluate the performance of the proposedbroadcast protocol. We consider two types of PU trafficmodels in the simulation [38]. The first PU traffic model isdiscrete-time, where the PU packet inter-arrival time followsthe biased-geometric distribution [39]. The second PUtraffic model is continuous-time, where the PU packet interarrivaltime follows the Pareto distribution [39]. We assumethat the probability that a PU is active is fixed (i.e., r ¼ 0:9).In addition, the side length of the network area a ¼ 10 (unitlength). We assume that the radius of the sensing range andthe transmission range are the same (i.e., rs ¼ rc ¼ 2 (unitlength)). In this paper, we mainly investigate the followingtwo performance metrics: 1) successful broadcast ratio: theprobability that all nodes in a network successfully receivethe broadcast message and 2) average broadcast delay: theaverage duration from the moment a broadcast starts tothe moment the last node receives the broadcast message.In addition, we compare our proposed broadcast protocolwith five other schemes: 1) RandomþFlooding: each SU randomlyselects a channel to hop and uses flooding (i.e., a SUis obligated to rebroadcast once receiving the message); 2)SequenceþFlooding (1=3 of our design): each SU downsizesits available channel set and constructs broadcastingsequences based on our scheme and uses flooding; 3)SequenceþSchedule (2=3 of our design): each SU constructsbroadcasting sequences based on our scheme and uses ourbroadcast scheduling scheme; 4) Basic QoS Scheme: each SUuses the basic scheme of the QoS-based broadcast protocolto broadcast [18]; and 5) JSþFlooding: each SU uses thejump-stay scheme [26] to construct the broadcastingsequences and uses flooding.5.1 Successful Broadcast RatioSince the single-hop successful broadcast ratio depends onw which is related to a pre-defined value _, we define_ ¼ 0:001. In fact, _ can be an arbitrary small value. Thus,based on Section 3, each SU calculates a proper w before thebroadcast starts in our scheme, the Sequence+Floodingscheme, and the SequenceþSchedule scheme. Tables 2 and 3show the simulation results of the successful broadcast ratiounder different number of SUs and PUs, where the value inthe upper cell is for the discrete-time PU traffic and thelower cell is for the continous-time PU traffic. In Table 2,M ¼ 20 and K ¼ 40. In Table 3, M ¼ 20 and N ¼ 20. Asshown in Tables 2 and 3, the successful broadcast ratio ishigher than 99 percent under our proposed broadcast protocolin all scenarios. In addition, the proposed broadcast protocoloutperforms other schemes in terms of highersuccessful broadcast ratio. Since the jump-stay schemerequires that the ith available channel in the available channelset is also channel i, it cannot utilize the technique in ourscheme to downsize the original available channel set. Inaddition, the jump-stay scheme can guarantee rendezvouswithin 6MPðP_GÞ, where P is the smallest prime numberlarger than M and G is the number of common channelsbetween two SUs. Thus, in order to ensure a successfulbroadcast, each SU broadcasts the message for 6MPðP_GÞFig. 14. An example of the first way of modification for Case 2 inScenario II when time slots unsynchronized.Fig. 15. An example of the second way of modification for Case 2 in ScenarioII when time slots are unsynchronized.TABLE 2Successful Broadcast Ratio under Different Number of SUsN N¼ 10 N ¼ 15 N ¼ 20 N ¼ 25RandomþFlooding 0.8801 0.8180 0.8100 0.8726 0.88210.8630 0.9148 0.9075 0.8698 0.8708SequenceþFlooding 0.9849 0.9839 0.9828 0.9823 0.98630.9762 0.9769 0.9777 0.9773 0.9719SequenceþSchedule 0.9859 0.9864 0.9823 0.9857 0.98550.9812 0.9845 0.9849 0.9876 0.9861Basic QoS Scheme 0.8915 0.9022 0.8543 0.9314 0.93170.8739 0.8386 0.8952 0.8498 0.8624Proposed Scheme 0.9991 0.9973 0.9969 0.9982 0.99090.9994 0.9959 0.9954 0.9967 0.9951TABLE 3Successful Broadcast Ratio under Different Number of PUsK ¼ 20 K ¼ 30 K ¼ 40 K ¼ 50 K ¼ 60RandomþFlooding 0.8189 0.8326 0.8842 0.9208 0.89070.7980 0.8738 0.9191 0.9139 0.8849SequenceþFlooding 0.9866 0.9863 0.9823 0.9819 0.98710.9742 0.9765 0.9773 0.9711 0.9797SequenceþSchedule 0.9868 0.9872 0.9857 0.9881 0.98720.9874 0.9885 0.9876 0.9833 0.9850Basic QoS Scheme 0.9502 0.9167 0.9314 0.8222 0.78840.8950 0.8921 0.8498 0.8792 0.8463Proposed Scheme 0.9978 0.9976 0.9982 0.9951 0.99210.9946 0.9941 0.9967 0.9977 0.9969SONG AND XIE: BRACER: A DISTRIBUTED BROADCAST PROTOCOL IN MULTI-HOP COGNITIVE RADIO AD HOC NETWORKS… 519slots. However, 6MPðP_GÞ is usually a very large numberwhen M is large. Hence, to better illustrate the trade-offbetween the successful broadcast ratio and broadcast delay,we compare our scheme with JSþFlooding in Section 5.2.5.2 Average Broadcast DelayTables 4 and 5 show the simulation results of the averagebroadcast delay under different number of SUs and PUs.Similarly to the successful broadcast ratio, in Table 4,M ¼ 20 and K ¼ 40. In Table 5, M ¼ 20 and N ¼ 20. Asshown in Tables 4 and 5, the proposed broadcast protocoloutperforms other schemes in terms of shorter averagebroadcast delay. Furthermore, Figs. 16 and 17 show the averagebroadcast delay under different number of channelswhen N ¼ 10 and K ¼ 40. As explained in Section 1, besidesour proposed scheme, we also compare with JSþFloodingand our scheme without downsizing the available channelset (i.e., w ¼ M). It is shown that even though the successfulbroadcast ratio is similar, the broadcast delay underJSþFlooding is much longer than our proposed scheme.To sum up, our proposed broadcast protocol outperformsRandomþFlooding in terms of higher successful broadcastratio and shorter broadcast delay. It also outperformsJSþFlooding in terms of shorter broadcast delay. In addition,even with the tradeoff in our proposed broadcast collisionavoidance scheme as explained in Section 2.3 and limitedoverhead, our proposed scheme and the schemes that use apart of our design (e.g., SequenceþFlooding) can still achievebetter performance results than RandomþFlooding for bothmetrics and JSþFlooding for the broadcast delay.5.3 The Impact of Unsynchronized Time SlotsFrom the discussion in Section 4.2, our proposed BRACERprotocol has an advantage that tight time synchronizationis not required. Accordingly, we provide two modificationsof our proposed protocol when time slots are unsynchronized.In this section, we evaluate the impact of the unsynchronizedtime slots on the performance of the proposedBRACER protocol.Figs. 18 and 19 show the single-hop successful broadcastratio and the average broadcast delay under different scenarios.In the first modification, we let ws ¼ wr ¼ w,whereas in the second modification, we let ws ¼ w andwr ¼ w þ 1. It is shown that unsynchronized scenarios usuallylead to lower successful broadcast ratio and longeraverage broadcast delay than the synchronized scenario.However, with the modifications of our proposed protocol,the low successful broadcast ratio can be significantlyimproved. From the figures, we may see that the secondmodification outperforms the first modification in terms ofhigher successful broadcast ratio. However, it also results inlonger average broadcast delay than the first modification.Fig. 16. Successful broadcast ratio under different number of channels.TABLE 4Average Broadcast Delay under Different Number of SUsDelay (unit: slots) N ¼ 5 N ¼ 10 N ¼ 15 N ¼ 20 N ¼ 25RandomþFlooding 19.781 26.483 28.003 29.252 31.20320.981 23.765 27.686 33.153 32.883SequenceþFlooding 8.458 11.168 12.744 14.243 15.9097.712 11.799 12.903 14.534 17.257SequenceþSchedule 7.811 10.995 13.324 13.896 15.8237.155 11.457 13.553 14.551 15.078Basic QoS Scheme 15.576 19.642 26.447 22.745 24.59916.093 23.164 21.698 26.834 32.078Proposed Scheme 7.066 10.532 12.259 13.353 15.1986.545 11.097 12.786 13.639 14.801TABLE 5Average Broadcast Delay under Different Number of PUsDelay (unit: slots) K ¼ 20 K ¼ 30 K ¼ 40 K ¼ 50 K ¼ 60RandomþFlooding 29.189 31.459 25.737 25.361 24.24334.547 30.629 27.617 28.424 26.399SequenceþFlooding 13.918 14.886 14.243 14.649 14.25914.413 13.958 14.534 14.867 14.389SequenceþSchedule 12.747 14.206 13.896 14.361 14.01413.652 14.086 14.551 14.521 14.237Basic QoS Scheme 25.148 25.187 22.745 27.182 28.53329.111 24.931 26.834 24.639 24.907Proposed Scheme 12.322 13.555 13.352 14.279 13.59713.249 13.401 13.639 13.335 13.471Fig. 17. Average broadcast delay under different unmber of channels.Fig. 18. The impact of unsynchronized time slots on the single-hop successfulbroadcast ratio.520 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 3, MARCH 2015Furthermore, when w>5, the performance of the two modificationsis very close to the unsynchronized scenario withoutmodification. This is because that when w is largeenough, more than one common channels exist between thesender and the receiver. Thus, there is at least one time sloton the common channel that is completely covered by thewr consecutive time slots. Hence, the receiver can successfullyreceive the message without any modification.Figs. 20 and 21 show the multi-hop successful broadcastratio and average broadcast delay under differentscenarios. It is illustrated in Fig. 20 that when the numberof SUs is small (e.g., N < 20), the synchronized scenariooutperforms all the unsynchronized scenarios in terms ofhigher successful broadcast ratio. This is because when Nis small, each SU usually selects small w for broadcasting.Thus, from Fig. 18, the successful broadcast ratio of theunsynchronized scenarios is lower than the synchronizedscenario. However, when N is large (e.g., N > 20), theunsynchronized scenarios with both modifications outperformthe synchronized scenario in terms of higher successfulbroadcast ratio. This is because when N is large, areceiver often has more than one senders. These sendersbroadcast the message on different channels to thereceiver. Thus, the impact of unsynchronized time slots isdiminished.5.4 Broadcast Collision AnalysisIn this section, we evaluate the performance of broadcastcollisions for our proposed BRACER protocol. Sincebroadcast collisions usually lead to the waste of networkresources, they should be efficiently avoided to save networkresources. In this paper, we use the average numberof broadcast collisions in a broadcast procedure per SUnode as the performance metric.Fig. 22 shows the average number of broadcast collisionsunder different numbers of channels. It is illustratedthat the Proposed Scheme outperforms the SequenceþFloodingand SequenceþSchedule schemes in terms of fewer broadcastcollisions on average. This means that the broadcast collisionavoidance scheme in the Proposed Scheme can effectivelyavoid broadcast collisions. In addition, the ProposedScheme also incurs fewer broadcast collisions than the RandomþFloodingscheme when M _ 20. That is, the RandomþFloodingscheme performs better than the Proposed Schemeonly when M is very large. This is because that in the RandomþFloodingscheme, each sender randomly selects anavailable channel in the band to broadcast. If the numberof channels is large, the probability that two senders selectthe same channel is fairly low. However, when M is small,the RandomþFlooding scheme leads to the highest numberof broadcast collisions among the four schemes (e.g.,M ¼ 5). Even though the RandomþFlooding scheme causesthe fewest broadcast collisions when M is large, the successfulbroadcast ratio and average broadcast delay of theRandomþFlooding scheme are not acceptable, as shown inTables 2, 3, 4, and 5. Additionally, the SequenceþSchedulescheme performs better than the SequenceþFlooding scheme,as shown in Fig. 22. This means that our proposedFig. 19. The impact of unsynchronized time slots on the single-hop averagebroadcast delay.Fig. 20. The impact of unsynchronized time slots on the multi-hop successfulbroadcast ratio.Fig. 21. The impact of unsynchronized time slots on the multi-hop averagebroadcast delay.Fig. 22. Average number of broadcast collisions under different numbersof chennels when N ¼ 10.SONG AND XIE: BRACER: A DISTRIBUTED BROADCAST PROTOCOL IN MULTI-HOP COGNITIVE RADIO AD HOC NETWORKS… 521distributed broadcast scheduling scheme also contributesto the collision avoidance.5.5 Overhead AnalysisOverhead is an important metric to evaluate the efficiencyof a broadcast protocol. To evaluate the impact of overhead,we use normalized overhead as the performancemetric [40], [41]. Normalized overhead is defined as theratio of the total broadcast packets (in bits) propagated byevery node in the network to the total broadcast packets(in bits) received by the receivers [40], [41].We denote the length of the original broadcast packet asLb. Based on Section 2.2, extra information needs to beadded in the original broadcast packet in order to realizethe proposed BRACER protocol. The extra information in abroadcast packet mainly consists of three parts. First of all,as mentioned in Section 2.2, the sender should include thecalculated initial w of its one-hop neighbors in the broadcastmessage. Second, as described in Section 2.3, thesender should include its own channel availability informationand the starting time slot of its broadcastingsequence in the message. Thirdly, the sender shouldinclude random integers for the intermediate nodes whoneed to rebroadcast to the same node. Thus, if we definethe length of the initial w, the starting time slot, and therandom integer as 8 bits, the length of the total extra informationin a broadcast packet in bits for a node isQ ¼ 8Na þM þ 8 þ 8Nb; (13)where Na is the number of the one-hop neighbors of thenode and Nb is the number of the intermediate nodes whoneed to rebroadcast to the same node. Therefore, the totallength of a broadcast packet of the proposed BRACER protocolis Lb þ Q.Fig. 23 shows the normalized overhead under differentlengths of the original broadcast packet. We set the range ofthe original broadcast packet length as ½50; 500_ bits. Sincebroadcast packets are control packets which are often veryshort, they mainly fall in this range. In addition, we compareour proposed scheme with the SequenceþFlooding andSequenceþSchedule schemes. The RandomþFlooding schemedoes not require the two-hop location information, so weexclude it for fair comparison. From Section 2, the length ofthe extra information in a broadcast packet for the SequenceþFloodingand SequenceþSchedule schemes are Q ¼ 0 andQ ¼ 8Na, respectively. Thus, the Proposed Scheme has thelongest broadcast packets among the three schemes. Eventhough the Proposed Scheme has the longest extra informationin a packet, it outperforms the other two schemes interms of lower normalized overhead, as shown in Fig. 23.The Proposed Scheme can achieve up to 106 and 12:5 percentless normalized overhead than the SequenceþFlooding andSequenceþSchedule schemes, respectively.Fig. 24 shows the normalized overhead under differentnumbers of SUs. We use the AODV route request (RREQ)packet as a typical original broadcast packet (i.e., Lb ¼ 192bits) [42]. From Fig. 24, it is shown that the proposed BRACERbroadcast protocol outperforms the other twoschemes in terms of lower normalized overhead undervarious numbers of SUs. More importantly, when thenumber of SUs increases by 400 percent, the normalizedoverhead of the Proposed Scheme only increases by 115 percent.Thus, the scalability of the proposed BRACER protocolis satisfactory.6 CONCLUSIONIn this paper, the broadcasting challenges specifically inmulti-hop CR ad hoc networks under practical scenarioswith collision avoidance have been addressed for thefirst time. A fully-distributed broadcast protocol namedBRACER is proposed without the existence of a global orlocal common control channel. By intelligently downsizingthe original available channel set and designing the broadcastingsequences and broadcast scheduling schemes, ourproposed broadcast protocol can provide very high successfulbroadcast ratio while achieving very short broadcastdelay. In addition, it can also avoid broadcast collisions.Simulation results show that our proposed BRACER protocoloutperforms other possible broadcast schemes in termsof higher successful broadcast ratio and shorter averagebroadcast delay.ACKNOWLEDGMENTSThis work was supported in part by the US NationalScience Foundation (NSF) under Grant No. CNS-0953644, CNS-1218751, and CNS-1343355. The authorswould like to thank the anonymous reviewers for theirconstructive comments which greatly improved the qualityof this work.Fig. 23. Normalized overhead under lengths of the original broadcastpacket.Fig. 24. Normalized overhead under different numbers of SUs whenLb ¼ 192 bits.522 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 3, MARCH 2015networks,” IEEE Pers. Commun., vol. 8, no. 1, pp. 16–28, Feb. 2001.[42] C. E. Perkins, E. M. Belding-Royer, and S. Das, “Ad hoc ondemanddistance vector (AODV) routing,” Request for Comments(RFC) 3561, Internet Eng. Task Force (IETF), Jul. 2003.SONG AND XIE: BRACER: A DISTRIBUTED BROADCAST PROTOCOL IN MULTI-HOP COGNITIVE RADIO AD HOC NETWORKS… 523Yi Song received the BS degree in electricalengineering from Wuhan University, Wuhan,China, in 2006, the ME degree in electrical engineeringfrom Tongji University, Shanghai, China,in 2008, and the PhD degree in electrical engineeringfrom the University of North Carolina atCharlotte, Charlotte, in 2013. He joined theDepartment of Electrical Engineering and ComputerScience, Wichita State University, as anassistant professor in August 2013. He receivedthe Kansas National Science Foundation EPSCoRFirst Award in 2014. His research interests include protocol design,modeling, and analysis of spectrum management and spectrum mobilityin cognitive radio networks.Jiang Xie received the BE degree from TsinghuaUniversity, Beijing, China, in 1997, the MPhildegree from the Hong Kong University of Scienceand Technology in 1999, and the MS and PhDdegrees from the Georgia Institute of Technology,in 2002 and 2004, respectively, all in electrical andcomputer engineering. She joined the Departmentof Electrical and Computer Engineering at the Universityof North Carolina at Charlotte (UNC-Charlotte)as an assistant professor in August 2004,where she is currently an associate professor. Hercurrent research interests include resource and mobility management inwireless networks, QoS provisioning, and the next-generation Internet.She is on the Editorial Boards of the IEEE Transactions on Mobile Computing,IEEE Communications Surveys and Tutorial, Computer Networks(Elsevier), Journal of Network and Computer Applications(Elsevier), and the Journal of Communications (ETPub). She receivedthe US National Science Foundation (NSF) Faculty Early Career Development(CAREER) Award in 2010, a Best Paper Award from IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT2010), and a Graduate Teaching Excellence Award from the College ofEngineering at UNC-Charlotte in 2007. She is a senior member of theIEEE and the ACM.” For more information on this or any other computing topic,please visit our Digital Library at www.computer.org/publications/dlib.524 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 3, MARCH 2015
CHAPTER 99.1 REFERENCES[1] S. Fenz, “An ontology- and Bayesian-based approach for determining threat probabilities,” in Proceedings of the 6 th ACM Symposium on Information, Computer and Communications Security, ser. ASIACCS ’11. New York, NY, USA: ACM, 2011, pp. 344–354. [2] M. Frigault, L. Wang, A. Singhal, and S. Jajodia, “Measuring network security using dynamic Bayesian network,” in Proceedings of the 4 th ACM Workshop on Quality of Protection, ser. QoP ’08. New York, NY, USA: ACM, 2008, pp. 23–30. [Online]. Available: http://doi.acm.org/10.1145/1456362.1456368 [3] N. Poolsappasit, R. Dewri, and I. Ray, “Dynamic security risk management using Bayesian attack graphs,” IEEE Transactions on Dependable and Secure Computing, vol. 9, no. 1, pp. 61–74, Jan 2012. [4] P. Xie, J. H. Li, X. Ou, P. Liu, and R. Levy, “Using Bayesian networks for cyber security analysis,” in The 40th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), 2010. [5] S. Noel, S. Jajodia, L. Wang, and A. Singhal, “Measuring security risk of networks using attack graphs,” International Journal of Next-Generation Computing, vol. 1, no. 1, July 2010. [6] L. Wang, T. Islam, T. Long, A. Singhal, and S. Jajodia, “An attack graph-based probabilistic security metric,” in Proceedings of the 22nd annual IFIP WG 11.3 Working Conference on Data and Applications Security. Berlin, Heidelberg: Springer-Verlag, 2008, pp. 283–296. [7] R. E. Sawilla and X. Ou, “Identifying Critical Attack Assets in Dependency Attack Graphs,” in Proceedings of the 13th European Symposium on Research in Computer Security: Computer Security, ser. ESORICS ’08. Berlin, Heidelberg: SpringerVerlag, 2008, pp. 18–34.