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.