COLLABORATIONBASEDSPECTRUMSHARINGALGORITHMSINCOGNITIVERADIONETWORKSByChowdhurySayeedHyderADISSERTATIONSubmittedtoMichiganStateUniversityinpartialfulllmentoftherequirementsforthedegreeofComputerScience-DoctorofPhilosophy2017ABSTRACTCOLLABORATIONBASEDSPECTRUMSHARINGALGORITHMSINCOGNITIVERADIONETWORKSByChowdhurySayeedHyderRadiospectrumassignmenttowirelessprovidersusingtraditionalxedallocationpolicywillnolongerbeaviabletechniquetomeetthegrowingspectrumdemandofemergingwirelessapplica-tions.Thisisbecausewhiletheavailablepoolofunassignedradiospectrumislow,thespectrumalreadyassignedtoexistingapplicationsisalsooftenunderutilizedintime,frequency,andloca-tion.Withfeaturesliketransmissionexibilityandadaptabilitycognitiveradio(CR)providesausefulmeansofspectrumsharingamonggrowingusersasanalternativetothecurrentxedpol-icy.Thecognitiveradionetwork(CRN),basedonthefunctionalityofCR,consistsoftwotypesofusersŠprimaryusers(PU)andsecondaryusers(SU).Primaryusersarelicenseduserswhohaveexclusiveaccessrightsofaxedspectrumrange.Secondaryusersareunlicenseduserswhoopportunisticallyexploitthespectrumholesornegotiatewithprimaryuserstoearntransmissionaccessrights.TheCRNbasedefcientspectrumsharingalgorithmsworkondifferentformsofcollaborationbetweenthePUsandtheSUs(inter-usercollaboration)andamongtheSUsthemselves(intra-usercollaboration).Inthesensingbasedcollaborationmodel,theSUssenselicensedspectrumandcollaborativelydecideaboutitsavailabilitybasedonthesensingresultswithoutanyinvolvementsfromthePUs.Intherelaybasedcollaborationmodel,theSUscoordinatewiththePUsdirectly,relayprimarypacketsinexchangefortransmissionopportunities,andthusbuildawin-wincooper-ativeframeworktoattainmutualbenets.Intheauctionbasedcollaborationmodel,theSUsbidfortemporaryorpermanentusagerightsofunusedlicensedspectrumbandsthatareputintoauctionforsalebythePUs.Eachofthesecollaborationmodelsfacesdifferentsetsofchallengestowardsachievinghighspectrumutilization.Inthisdissertation,weaddresssomeofthesechallengesandpresentasetofefcientspectrumsharingalgorithmsbasedonthesecollaborationmodels.Therstworkinthisdissertationaddressesthespectrumsensingdatafalsication(SSDF)attackinIEEE802.22wirelessregionalareanetwork(WRAN)underthesensingbasedcollab-orationmodel.Wediscussdifferentstrategiesofmanipulatingsensingreportsbyoneormoremalicioususersandhowthesemanipulationstrategiesmayaffectthespectrumutilization.Tode-fendagainstsuchmaliciousattacks,wepresentanadaptivereputationbasedclusteringalgorithm.ThealgorithmcombinestheclusteringtechniquewithfeedbackbasedreputationadjustmenttopreventindependentandcollaborativeSSDFattacksandquarantinestheattackersfromthedeci-sionmakingprocess.Ournextsetofworkinthisdissertationfallsundertherelaybasedcollaborationmodel.Weinvestigatethefeasibilityofthiscollaborationmodelinthecaseofreal-timeapplications.Wequantifytheimpactofpacketdeadlinesandcooperationoverheadonthesystemperformance.Wediscusstheimpactofinterferencethatmaycausefromsecondarytransmissions.Basedontheanalysis,wedevelopaninterferenceawarereliablecooperativeframeworkwhichimprovesthepacketreceptionrateofbothuserswithlowoverhead.Weextendourinvestigationofthisrelaybasedcollaborationmodelfromsinglehoptomultiplehopsintheformofcooperativerouting.WeformulatetheroutingproblemasanoverlappingcoalitionformationgamewhereeachcoalitionrepresentsaroutingpathbetweenprimarysourceanddestinationconsistingofmultipleSUsasintermediaterelays.TheproposedmodelallowsSUstoparticipateinmorethanonecoalitionsandcreatesmoretransmissionopportunitiesforthemwhileachievingstableroutingpathsforPUs.Ournalsetofworkinthisdissertationdealswiththechallengesintheauctionbasedcollabo-rationmodel.Weconsideranonlinesettingofspectrumauctionswhereparticipationandvaluationofbothbiddersandsellersarestochastic.Weanalyzethebehaviorofbiddersandsellersinsuchsettingsanddeveloptruthfulauctionmechanismswithrespecttobidandtime,improvingspectrumreuse,auctionefciency,andrevenue.Thendingsfromourresearchwillhelptounderstandtheunderlyingchallengesinfuturenetworks,buildabetterspectrumecosystem,andencouragenewspectrumsharingmodelsinwirelessbroadbandcommunications.Tomyparents.vACKNOWLEDGMENTSAllpraisesareduetoAllah,themostbenevolentandmerciful.IwouldliketothankDr.XiaoforgivingmeanopportunitytoworkasoneofherPhDstudents.Fromthebeginning,sheinstructedmetoinvestigateresearchproblemsonmyownwhichhelpedmetounderstandthechallengesintheeldofmyresearch.Shetaughtmehowtopresentideasintowriting,howtoreviewapaper,howtoaddressthecommentsofthereviewer,andsoon.Thisknowledgedenitelyhelpedmetondmylimitations,realizemyweaknesses,andIamgratefultoherforthatvaluableinsight.IwouldalsoliketothankmyotherPhDcommitteemembers-Dr.Mutka,Dr.Esfahanian,Dr.Jeitschko,andDr.Mandrekarfortheirexibilitywiththeschedule,patiencetositthroughhoursofmypresentation,andtheirinputtomakeitbetter.IhavebeenworkingwithDr.Jeitschkoforthelastcoupleofyears.Hisprofoundknowledgeinauctiontheorymadetheinterdisciplinaryresearchsomucheasy,fun,andinteresting.Hebecamemymentor,guide,andafriend.Iwillremainevergratefultohimforhissupportandencour-agementduringthedarkesttimesofmylife.Inthisregard,Ialsowanttoshowmygratitudetothosepeoplewhohavenotdismissedmyconditionslikeothersandgenerouslyextendedtheirhelpthroughcounselingandguidance.HadInotreceivedthatsupport,itcouldhavebeenentirelyadifferentstory.Ialsowanttothankallofmycoauthorswhohavecollaboratedwithmeindifferentprojectsandcontributedwiththeirvaluableinputsandcorrections.IwanttospeciallythankDr.AlimalIslam(Razi)whosementalsupport,domainknowledge,andunyieldingattitudeledtosomegoodnishedprojects.IwanttothankDr.Torngforhisvaluablesuggestionandimportantcontributiontothejointresearchwork.Apartfromthat,Iwanttospeciallythankhimforhissupportasthegraduatedirectorofthedepartment.HealongwithDr.Mckinleywerethetwoteacherswhovishowedhowtomakeagraduateclassfunandinteresting.Despitetheirdifferentteachingstyles,Ienjoyedbothoftheirclassesandwillnothesitatetofollowtheirstyles(ifIeverpursueanacademiccareer).IamalsogratefultothelocalBangladeshiCommunity(Jewelvai&vabi,Kabirvai&vabi,Touqvai&vabi,Jamalvai&vabi,Aftabvai&vabi,Linconvai&vabi,SomaapaandZibi)whoembracedusasoneoftheirownandEastLansingbecamemyhomeawayfromhome.IalsowanttothanktheMSUBangladeshiStudentsAssociation(ABSS)anditsmembersfororganizingcolorfuleventstoremindusourbeautifulcultureeveryyear.Iwasfortunateenoughtogettheopportunitytostudyinthetopmostengineeringuniversity,BangladeshUniversityofEngineeringandTechnology(BUET)inBangladeshatalmostnocost.IamgratefultothehardworkingtaxpayingcommonpeopleofBangladeshwhosecontributiontothenationaleconomymadethispossibleforthousandslikeme.Inthisoccasion,Ialsoremembermyteachersandcolleaguesfrommyundergraduateinstitu-tion-Dr.MasroorAli,Dr.SohelRahman,Dr.AshikurRahman,Dr.MasudHasan,Dr.HumayunKabir,Dr.YusufSarwar,Dr.Atif,Dr.Rifat,Dr.Enamul,andArup.Allofthemhasmadeapositivechangeinmylife.PerhapsIwouldnotbehereifIhadnottheopportunitytomeetmytwounclesataveryearlystageofmylife.My`Boromama'wasahighschoolmathteacherwhotaughtmemathinmyhighschools.My`chotomama',anelectricalengineerbyprofession,wasmysourceofinspirationtoproblemsolvingandthatearlychildhoodexperienceledmetopursuemystudiesincomputerscience.Iremembertheircontributioninmyacademiclifewithrespectandhumility.Iamalsogratefultomytwofriends-SaidulandMasudwhoalwayskeptmefocusedinthebigpicturethroughdifculttimes.Finally,itisbecauseofmyparents,mybrother,andmyfamilyIkeepgoingagainstallodds.Myparent'supbringingtaughtmetoenjoysuccesswithhumility,andembracefailurewithviistrongerdetermination.Mymedicaldoctorbrotherdemonstratedinhisdailylifehowtobecomeacompassionatehumanbeing.IamwhoIambecauseoftheirlove,sacrice,guidance,andprac-tice.MywifeTamannahasbeenatruefriendthroughoutmyPhDyearsandalwaysbelievedinmewhenImyselfwasdoubtful.MylittleangelPriyotaalwaysbroughtsmiletomyfaceevenatthelowestpointofmylife.IthanktheAlmightyforthiswholerollercoasterexperienceandforstrengtheningmybeliefonthissayingfiallthehardshipsandnegativityinlifeisshort-livedandthebeautyandblessingsinlifeiseternal.flviiiTABLEOFCONTENTSLISTOFTABLES.......................................xiiiLISTOFFIGURES......................................xivKEYTOSYMBOLS......................................xviiCHAPTER1.........................................1INTRODUCTION.......................................11.1PresentStatusandCoreproblem...........................11.2SolutionwithCognitiveRadioNetwork.......................21.3CollaborationbasedSpectrumSharing........................31.3.1SensingbasedCollaborationModel.....................41.3.2RelaybasedCollaborationModel......................51.3.3AuctionbasedCollaborationModel.....................61.4Contribution......................................81.5Organization......................................8CHAPTER2.........................................10BACKGROUNDANDRELATEDWORK.........................102.1Background......................................102.1.1SpectrumLicensing..............................102.1.2FCCReformationInitiatives.........................112.1.3SpectrumSensing...............................122.1.4IEEE802.22WRANStandard........................122.1.5RelayingStrategies..............................132.1.6VCGAuctions................................14 2.1.7McAfeeAuction...............................152.2RelatedWork.....................................152.2.1RelatedWorkonSensingbasedCollaborationModel............152.2.2RelatedWorkonRelaybasedCollaborationModel.............172.2.3RelatedWorkonAuctionbasedCollaborationModel............20CHAPTER3.........................................23ARC:ANADAPTIVEREPUTATIONBASEDCLUSTERINGALGORITHMAGAINSTSSDFATTACKINIEEE802.22NETWORKS..............233.1SystemModel.....................................253.1.1NetworkModel................................26 3.1.2TheDecisionRules..............................273.1.3HonestUserModel..............................283.1.4AttackModel.................................293.1.4.1IndependentAttack.........................29ix3.1.4.2CollaborativeAttack........................293.2AlgorithmDesign-AttackersvsBS.........................313.2.1Attackers'Impact...............................313.2.2DesignoftheAlgorithm...........................333.3AdaptiveReputationbasedClustering(ARC)Algorithm..............353.3.1ClusterFormation(ClusteringPhase)....................363.3.2DecisionMaking(VotingPhase).......................373.3.2.1Intra-ClusterVoting........................383.3.2.2Inter-ClusterVoting(FinalDecision)...............383.3.3ReputationAdjustment(UpdatePhase)...................393.4AnalysisofAttackModels..............................393.5PerformanceEvaluation................................463.5.1PerformanceMetrics.............................463.5.2SimulationParameters............................473.5.3IndependentAttack..............................473.5.4CollaborativeAttack.............................493.5.5AdaptiveAttack................................543.6Summary.......................................55CHAPTER4.........................................56INTERFERENCEAWARERELIABLECCRNSFORREAL-TIMEAPPLICATIONS564.1RelaybasedCollaborationModel...........................574.1.1LimitationsofPriorWork...........................584.1.2ProposedApproach..............................584.1.3KeyDesignChallenges............................594.1.4OurContributions...............................614.2SystemModelandProblemFormulation.......................624.2.1Preliminaries.................................624.2.2PUTrafcModel...............................63 4.2.3ChannelModel................................64 4.2.4CooperativeTransmission..........................644.2.5PacketLoss..................................65 4.2.6MDPFormulation...............................664.3AnalysisofaCooperativeTransmissionModel...................684.3.1ActionSet...................................69 4.3.2TransitionProbabilityMatrix.........................714.3.3RewardFunction...............................724.3.3.1CalculationofDa(t)(˙;˙0).....................744.3.3.2CalculationofVa(t)(˙).......................754.3.3.3CalculationofWa(t)(˙)......................774.3.4Comparison..................................804.4Multi-userCooperativeTransmissionModel.....................834.4.1Step1:Pre-screening.............................844.4.2Step2:Negotiation..............................85x4.4.3Step3:DataTransmission..........................874.4.4Step4:CooperationRenewal.........................884.5PerformanceEvaluation................................894.5.1PerformanceMetrics.............................894.5.2SimulationSetup...............................904.5.3SingleUserSetting..............................904.5.4Multi-usersetting...............................914.6Summary.......................................94CHAPTER5.........................................96COOPERATIVEROUTINGINCOGNITIVERADIONETWORKS..........965.1SystemModelandProblemFormalization......................995.1.1SystemModel.................................99 5.1.2Preliminaries.................................1015.1.3Formulation..................................1025.1.3.1RoutingpathConstructionasCoalitionFormation........1025.1.3.2SchedulingasResourceSharing..................1035.1.4PayoffofaPrimaryUser...........................1055.1.5PayoffofaSecondaryPlayer.........................1085.1.6ProblemStatement..............................1095.2CooperativeRoutingProtocol.............................1095.2.1MessageFormat................................1115.2.2CoalitionOfferandPayoffCalculation....................1125.2.3StabilityofCoalitions.............................1145.3PerformanceEvaluation................................1155.3.1Topology...................................116 5.3.2PerformanceComparisonwithPriorWork..................1165.3.3ResultswithVaryingNumberofPUs....................1185.3.4ResultswithVaryingNumberofSUs....................1195.3.5ResultswithAlgorithmParameters......................1195.4Summary.......................................121CHAPTER6.........................................122TRUTHFULONLINESPECTRUMAUCTIONS.....................1226.1OnlineDynamicAuctions...............................1266.1.1TheAuctionEntities.............................1266.1.2AuctionProperties..............................1286.1.3DesignChallenges..............................1286.1.4Illustration...................................1296.2AuctionDesign....................................1326.2.1Prank-I(SameValuationCase).......................1336.2.2Prank-II(SingleAuctionCase).......................1366.2.3Prank-III(DoubleAuctionCase)......................1396.3DistributionAwareAuctionAlgorithms.......................1416.3.1SOADE:OnlineSingleAuctionAlgorithm.................141xi6.3.2AnalysisofSOADE..............................1446.3.3distAware:OnlineDoubleAuctionAlgorithm................1506.3.4AnalysisofdistAware.............................1506.4DistributionFreeOnlineDoubleAuctionAlgorithm.................1536.4.1CandidateScreening(Phase1)........................1546.4.2DebtCalculation(Phase2)..........................1566.4.3CriticalPriceandWinnerSelection(Phase3)................1576.4.4AnalysisofdistFree..............................1596.5PerformanceEvaluation................................1616.5.1PriorityAnalysis...............................1626.5.1.1Prank-II..............................162 6.5.1.2Prank-III.............................1646.5.2AlgorithmPerformance............................1656.5.3SingleAuctionAlgorithm..........................1656.5.3.1ResultsonSettingwithNoSpectrumReusability.........1666.5.3.2ResultsonSettingwithSpectrumReusability...........1686.5.4DoubleAuctionAlgorithms.........................1686.5.4.1ResultsonSettingwithNoSpectrumReusabililty........1706.5.4.2ResultsonSettingwithSpectrumReusability...........1716.6Summary.......................................173CHAPTER7.........................................175CONCLUSION........................................1757.1SummaryofContributions..............................1757.1.1ContributiononSensingbasedCollaborationModel............1757.1.1.1TheSSDFAttackandProposedSolution.............1767.1.1.2PerformanceEvaluation......................1777.1.2ContributiononRelaybasedCollaborationModel..............1787.1.2.1CooperationAlgorithminReal-timeApplications........1787.1.2.2CooperationAlgorithminMulti-hopRouting...........1807.1.3ContributiononAuctionbasedCollaborationModel............1827.1.3.1OnlineSpectrumAuctions.....................1827.1.3.2PerformanceEvaluation......................1847.2FutureWork......................................1857.2.1UniedSolutionsagainstCombinedSSDFandPUEAttacks........1857.2.2PervasiveCommunicationsinCooperativeCognitiveRadioNetworks...1867.2.3TrustandSecurityissuesinCooperativeCognitiveRadioNetworks....1867.2.4Multi-unitOnlineSpectrumAuctions....................1877.2.5CombinatorialSpectrumAuctions......................1887.2.6PreventingBidderCollusioninSpectrumAuctions.............1897.2.7SpectrumAuctionInfrastructure.......................189BIBLIOGRAPHY.......................................191xiiLISTOFTABLESTable4.1:Statetransitionprobabilities.........................71Table5.1:AlgorithmmcRoute:foraPUuseri....................111Table5.2:AlgorithmmcRoute:forSUuserj.....................112Table5.3:Simulationparameters............................116Table6.1:AlgorithmSOADE:SecondaryOnlineAuctioninDynamicEnvironments142Table6.2:AlgorithmdistAware:DistributionAwareOnlineDoubleAuction.....151Table6.3:Symbolsusedinthealgorithm.......................155Table6.4:Functionsusedinthealgorithm.......................155Table6.5:AlgorithmdistFree:CandidateScreening(Phase1)............156Table6.6:AlgorithmdistFree:DebtCalculation(Phase2)..............157Table6.7:AlgorithmdistFree:CriticalPriceDetermination(Phase3)........158xiiiLISTOFFIGURESFigure1.1:Sensingbasedcollaborationmodel.....................4Figure1.2:Relaybasedcollaborationmodel......................5Figure1.3:Auctionbasedcollaborationmodel.....................7Figure3.1:Systemdetectionaccuracywithvaryingattackers.............32Figure3.2:Reputationdistribution...........................34Figure3.3:Blockdiagramofdifferentphasesofthealgorithm.............35Figure3.4:Informationpropagation..........................37Figure3.5:Relationshipsamongattackersandhonestusers..............43Figure3.6:Independentattackwithvaryingnumberofattackers...........48Figure3.7:Independentattackwithvaryingattackingprobability...........48Figure3.8:Independentattackwithvaryingdetectionprobability...........49Figure3.9:Collaborativeattackwithvaryingnumberofattackers...........50Figure3.10:Collaborativeattackwithvaryingattackingprobability..........50Figure3.11:Collaborativeattackwithvaryingdetectionprobability..........51Figure3.12:CollaborativeSubGroupattackwithvaryingnumberofattackers.....52Figure3.13:CollaborativeSubGroupattackwithvaryingattackingprobability.....52Figure3.14:CollaborativeSubGroupattackwithvaryingdetectionprobability.....53Figure3.15:CollaborativeGAMAattackwithvaryingnumberofattackers......53Figure3.16:AdaptivecollaborativeSubgroupattack..................54Figure4.1:Impactofsecondaryinterferenceincooperativecommunication.....60Figure4.2:Matchingpairandactionselection.....................67xivFigure4.3:Cooperationbetweenaprimaryandasecondaryuser...........69Figure4.4:Rewardcomponent.............................76Figure4.5:Comparisonbetweencooperationmodels(packetreceptionrate).....81Figure4.6:Comparisonbetweencooperationmodels(averagepuwaitingtime)...82Figure4.7:Cooperationlifecycleofauser.......................86Figure4.8:Handshakingprotocol............................86Figure4.9:Comparisonbetweenmodelsofasinglepairofprimaryandsecondaryusers.....................................91Figure4.10:Markovthreestatetrafcmodelwithvaryingtransmissiondeadline...92Figure4.11:Markovthreestatetrafcmodelwithvaryingqueuelength........92Figure4.12:Poissontrafcmodelwithvaryingdeadline................93Figure4.13:Poissontrafcmodelwithvaryingqueuelength..............93Figure4.14:Poissontrafcmodelwithvaryingpurate.................94Figure5.1:Networkmodel...............................99Figure5.2:Overlappingcoalitionexample.......................101Figure5.3:Messageformat...............................112Figure5.4:ComparisonbetweenmcRouteandnpRoute[79].............115Figure5.5:ResultswithvaryingPUs..........................118Figure5.6:ResultswithvaryingSUs..........................118Figure5.7:Resultswithvaryingalgorithmparameters.................120Figure6.1:Auctionwithdynamicbidderandsupply..................126Figure6.2:Applyingstaticauctionrules[142]indynamicenvironments.......130Figure6.3:Latearrivalmanipulationbyabidderwhileapplyingstaticauctionrules[142].....................................131xvFigure6.4:LatedeparturemanipulationbyabidderwhileapplyingTopaz[30]....131Figure6.5:Priorityvaluewithvaryingparameters(Prank-II)............163Figure6.6:Priorityvalueswithvaryingparameter(Prank-III)............164Figure6.7:Topazvs.SOADEonsettingwithnoreusability..............167Figure6.8:Topazvs.SOADEonsettingwithspectrumreusability..........169Figure6.9:Performancecomparisononsettingwithnoreusability..........171Figure6.10:Performancecomparisononsettingwithspectrumreusability.......172xviKEYTOSYMBOLSnnumberofsecondaryusersnanumberofmalicioussecondaryusersnhnumberofhonestsecondaryusersmnumberofprimaryusersPsetofprimaryusersSsetofsecondaryuserspprimaryuserssecondaryuserPfaprobabilityoffalsealarminindividualchannelsensingPmdprobabilityofmisdetectionintermsofchannelsenPIprobabilitythatachannelisidlePBprobabilitythatachannelisbusyPhdetectPUdetectionprobabilityofanhonestsecondaryuserPadetectPUdetectionprobabilityofanattackerPdiffHHprobabilitythattwohonestusersdifferPdiffAHprobabilitythatanhonestuserandanattackerdifferPmaattackingprobabilityKL(xjjy)KLDmeasuresbetweendistributionxandydxydistancebetweenxandyQEerrorrateQDfalsedetectionrateQFfalsepositiverateˆireputationofuseriweightfactor01VidecisionofavirtualclusteraboutchannelstatusVdecisionoftheBSaboutchannelstatusnumberofdimensionofsensingreportsperusermaintainedbyBSQgoaltargetsetbyanattackerEpprimarytransmissionpowerEssecondarytransmissionpowerHihypothesisiLqueuelengthPxprobabilityofeventxhichannelgainsetofstatesAsetofactions˚transmissionpolicy˙systemstatediscountfactora(t)actionattimetUa(x;y)utilityofauserafteractionaandmovingfromstatextoyttimeperiodDa(x;y)packetdropprobabilityduetoqueueoverowVa(x;y)successfuldeliveryprobabilityofapacketWa(x;y)successfuldeliveryprobabilityofqueuedpacketsxviiiP(x;y)transitionprobabilityfromstatextoyRdatarateCicoalitioniCScoalitionstructureriresourceofuseriTtotaltimetrafcrateBbandwidthdconvergenceparameterGttransmittergainGrreceivergainRi(Ci)datarateprotofcoalitioniDi(Ci)delayprotofcoalitioni jsellerj'spaymentvivaluationofbidderibibidofasecondaryuserib(h)h-thhighestbidinthesetaiaskofaprimaryuseria(h)h-thlowestaskinthesetoiarrivaltimeofuseridideadlineofuserigilocationofuseriE[ˇ˝(vi)]expectedpayoffofabidderofvalueviwith˝moreperiodstolivexix˝(vi)priorityofabidderiwithvaluationviand˝periodstoliveL˝(vi)losingprobabilityofabidderiwithvaluationviand˝periodstolive˚p jsales/bidrequestCi(i)coalitionjoinrequestofuseriVjsetofuserintheneighborhoodofuserjFkcumulativedistributionfunctionofusers'lifetimeFncumulativedistributionfunctionofarrivingbiddersFmcumulativedistributionfunctionofsuppliesxxChapter1 Introduction 1.1PresentStatusandCoreproblem Thecommunicationworldhaswitnessedatremendousadvancementinwirelesstechnologyoverthelastfewdecades.Adiverserangeofwirelessserviceshasbeenofferedstartingfromhealth-careapplicationstovehicularnetworks,fromreal-timesystemmonitoringtoInternetofThings(IoT)applications.Anewsetofwirelesscommunicationdeviceslikesmartphones,tablets,wearabledeviceshavebeenintroducedwithusefulandinterestingfeatures.Asaresult,theusageofwirelessdeviceshasskyrocketed,wirelesscommunicationhasbecomeanintegralpartofourdailylives,andwirelesstrafchasgrownatanexponentialrate.AccordingtoCiscostudy[25],mobiledatatrafchasgrown4000-foldoverthelast10yearswith74%growthinthelastyearonly,andthistrendwillcontinuetoincreaseinfuture.Inthesamestudy,itisexpectedthatmonthlymobiledatatrafcwillbe30.6exabytes(EB)by2020.ThishugetrafchastobecarriedoveraxedrangeofradiospectrumwhoseusageandaccessareregulatedbyFederalCommunicationsCommission(FCC)intheUS.TraditionallytheFCCapprovesdifferentserviceprovidersanexclusivelicenseofaxedspec-trumband.Inthefaceofgrowingtrafcdemand,suchxedallocationcannotmeetfuturedemandwiththeunassignedspectrumbandsonly.Theserviceproviderswithalreadylicensedspectrumarenotutilizingtheirshareveryefcientlyaswell.Forexample,SharedSpectrumCompany(SSC)conductedacitywideexperimentinVienna,VAontheusageofspectrumbetween30MHz1and3GHz[108].Thestudyshowedthatasignicantnumberofspectrumbandswerefihighlyunderutilizedflorfialmostneverused.flSimilarspectrumoccupancystudieshavebeenperformedindifferentcities,andtheresultsareconsistentthroughoutallthesestudies[116][89][11][17].Therefore,thecurrentallocationsystemisprovedtobeinadequate,anditsreformationisaneces-sitytodevelopanefcientspectrumsharingplatform. 1.2SolutionwithCognitiveRadioNetwork FederalCommunicationsCommission(FCC),thespectrumregulationcommitteeintheUShastakensignicantsteps(seeSec.2.1.2)toaccommodatenewusersandsatisfytheirrequirements.SimilarstepshavebeentakenbyotherspectrumregulationcommitteesinEuropeandAsia[91].Theconceptofcognitiveradio(CR)isintroducedasaviablesolutiontoboththespectrumscarcityproblemandunderutilizationproblembydynamicallysharingspectrumtoendusersaccordingtotheirqualityofservicerequirements.Bydenition,cognitiveradiocanchangeitstransmissionparametersbasedoninteractionwiththeenvironment.Therearetwofeaturesthatmakecognitiveradiouniqueinthenetworkingworld[3]:(1)itscognitivecapabilitytocapturetheinformationfromtheradioenvironmentand(2)itsrecongurabilitytoworkondiversefrequenciesindifferenttransmissionaccesstechnologies.Basedontheusagerights,cognitiveradionetwork(CRN)consistsoftwotypesofusersŠprimaryusers(PU)andsecondaryusers(SU).Primaryusersarebasicallythelicenseholders,andtheyhaveexclusiveaccessrightstouseaxedspectrumband.Ontheotherhand,secondaryuserseitheropportunisticallyexploitfreespectrumornegotiatewithprimaryuserstotransmittheirowndata.Cognitiveradionetworkhasthusbecomeaprominentresearcheldtoaddressthespectrumallocationandsharingproblem.Variousspectrumsharingalgorithmshavebeenproposed2anddevelopedbasedonthecollaborationbetweenPUsandSUsinCRN.Inthisdissertation,wehaveexploredseveralofthesecollaborationmodels.Wehavediscussedtheuniquechallengesassociatedwitheachmodel,anddevelopedefcientspectrumsharingalgorithmsaddressingsomeofthesechallenges. 1.3CollaborationbasedSpectrumSharing InitialfocusoftheCRNresearchwastondunusedspectrumwithoutinterferingprimaryusers'transmission.Spectrumsensingtechniquesbecamethecenterofresearchtoidentifyprimaryusers'activity,detectunusedspectrum,andopportunisticallyutilizethatspectrumfortransmissionofsecondarypackets.Overtheyearsdifferentsensingtechniquesweredevelopedbytheresearchers(foracomprehensivesummaryofsensingtechniques,readersarereferredtoSec.2.1.3).Whilethesensingtechniquesofferanimmediateopportunitytoutilizeunusedspectrumwithoutanymajorchangeintheexistingprimaryuserarchitectureitalsofacesseveralchallenges.Forexample,determiningsensingdurationandsensingfrequencywhilemaintainingahighsensingaccuracywereamajorconcern.Furtherresearchshowsthatcooperativesensingcanreducethesensingerrorandprovidebetterdetectionandspectrumutilizationthanindependentsensing.Consequently,anIEEEstandard[110]isdevelopedaroundcollaborativesensingtodesignaregionalareanetwork.Thestrictrequirementofspectrumsharingislaterrelaxed,andsecondaryusersareallowedtotransmitaslongastheinterferencecausedfromtheirtransmissiondonotexceedapredenedthreshold.Inthismodel,collaborationbetweenprimary-secondarypairsisestablishedonthebasisofcooperativediversityandmutualneeds.Thesecollaborationmodelsofspectrumsharing,theirimplementationchallenges,andfutureprospectswerediscussedinthe2009NSFworkshop[109].Inparalleltothesetechniques,thereisacontinuousefforttoensureefcientspectrumsharing3Figure1.1:Sensingbasedcollaborationmodelbyimprovingtheexistingspectrumregulationsystem.Awellregulationsystemshouldmotivatetheprimaryuserstosharetheirunusedspectrumtosecondaryusersinexchangeforadditionalrevenue.Thiseffortfromtheresearchersandpolicymakersleadstodesignofvariousinnovativeauctionmechanismswithdynamicnetworksettings.Theseongoingeffortshavebeenrecognizedinthe2013NSFworkshoponwirelessnetworking[13]andwelladaptedbyFCCindesigningfuturespectrumtrading.Wesummarizethesespectrumsharingtechniquesintothefollowingthreecategoriesbasedonthecollaborationbetweentheprimaryandsecondaryusersasfollows[6].1.3.1SensingbasedCollaborationModel Therstspectrumsharingmodelinvolvescollaborationamongthesecondaryusersonly.Theprimaryusersareunawareoftheexistenceofthesecondaryusers,andthereforesecondarytrans-missionmustnotinterferetheirtransmission.Toavoidinterferencewithprimarytransmissions,thesecondaryusersapplyspectrumsensingtechniques,andtogether,theydecidethepresenceorabsenceofPUactivity.WhentheircollaborativedecisionimpliestheabsenceofPUs,thesec-ondaryuserscansharetheunusedspectrumfortheirowntransmission.Anindustrystandard[110]IEEE802.22isbeingdevelopedforWirelessRegionalAreaNet-work(WRAN)basedonthissensingbasedcollaborationmodel.Fig.1.1showsaWRANconsist-4Figure1.2:Relaybasedcollaborationmodel1ingofonebasestation(BS)andmultiplesecondaryusersasconsumerpremiseequipments(CPE).Inthisstandard,abasestationinstructstheCPEstosensespectrum,andthesecondaryuserssendbacktheirreportstothebasestation.Thebasestationthenmakesadecisionbasedonthesensingreports.However,thiscollaborationamongsecondaryusersalsogivesamalicioususeranoppor-tunitytomanipulatethesystem[15].Anindividualsecondaryusermaysendanincorrectsensingresult,leadthebasestationtoawrongdecision,andusethespectrumforitsownbenets.Thisformofmanipulationisreferredtoas`spectrumsensingdatafalsication'orSSDFattackinIEEE802.22networks.Inourresearchwork,weaddressthisproblemanddevelopadecisionmakingalgorithmthatpreventsSSDFattackandisolatesthemanipulatorsfromthedecisionmaking.1.3.2RelaybasedCollaborationModel Thisspectrumsharingmodelinvolvesmutualneedbasedcollaborationbetweenprimaryandsec-ondaryusers(seeFig.1.2).Secondaryusersintendtoaccessprimaryspectrumfortheirowntransmissioninexchangeforrelayservicestoprimaryusers.Thisrelaybasedcommunicationreducestheimpactofpathattenuation,multi-pathpropagation,shadowingbyobstaclesandthushelpstostrengthentheprimarysignalatthedestination.PUsandSUsexchangetheircoopera-tioninformationandbuildacollaborativespectrumsharingmodel.Thismodelisalsoknownas1thepictureispartiallytakenfromhttp://famousbloggers.net/quickhaggle.html5cooperativecognitiveradionetwork(CCRN).InthisCCRNmodel,thePUssharetheirlicensedspectrumintemporal,spectral,andspatialdomainiftheSUsofferrelayingservicestoPUtrafc.ThePUsandSUscoordinateandscheduletheircooperativetransmissionsforachievingmutualbenetsbyapplyingdifferentrelayingstrate-gies(seeSec.2.1.5).Sincevideowillbethedominantpartofthefuturetrafc,weinvestigatewhethermutualcooperationhelpstosupportreal-timetrafc.WepresentadetailedanalysisofthecollaborationmodelbetweenPUsandSUsaddressingtheimpactofcooperationoverheadandin-terferenceconstraints.Wedevelopadistributedinterferenceawarereliablecooperationalgorithmthathelpsausertomakecooperationdecisionandtransmitsitsdata.Nextwetakeourinvestigationfromsinglehoptomulti-hopcooperativecommunicationinre-laybasedcollaborationmodel.Weconsidermulti-hopcooperativerelayingtoestablisharoutingpaththroughtheSUsinexchangeoftheirtransmissionopportunities.Weapplytheconceptofanoverlappingcoalitiongametodenetherewardofanindividualuserforparticipatinginacoop-eration.Thesimulationresultsshowthatitincreasestransmissionopportunitiesofthesecondaryuserswhileimprovingtherewardoftheprimaryusersintermsofdatarateandtransmissiondelay.1.3.3AuctionbasedCollaborationModel Intheauctionbasedcollaborationmodel,theprimaryandsecondaryuserscollaborateviaathirdpartye.g.,FCC[39].ThePUsauctiontheirunusedspectrumforextrarevenuewhereastheSUsbidintheauctiontoacquirenecessaryusagerights.Usuallyatrustedauthority(e.g.,FCC)holdstheauction,administersspectrumallocation,andmanagesthepaymenttransaction.Fig.1.3illustratesdifferentcomponentsofaspectrumauction.RecentinitiativesfromtheFCCstronglyindicatethatspectrumauctionswillplayasignicantroleinrevolutionizingfuturespectrumdistributioningeneralaswellasinmilitaryuse.6Figure1.3:AuctionbasedcollaborationmodelThemajorchallengeinthismodelistoaccommodatediversityinbiddersandsellerswhileensuringintegrityandreliabilityoftheauction.Thelicensedusersmayauctiontheirspectrumintemporalandspatialdomainwithdifferentvalues.Similarly,thesecondaryusersplacetheirbidsaccordingtotheirtransmissionrequirementswhichalsovaryfromuserstousers.Inpresenceofsuchdiversity,anauctionmechanismmustensuretruthfulnessthatcannotbeachievedwithwell-knownVCGmechanism(seeSec.2.1.6).Additionally,spectrumauctionsmustensurereusabilitywhichisdifferentfromtraditionalauctions.Intraditionalauctions,asingleunitofproductissoldtoasinglebidderwhereasinspectrumauctions,thesamespectrumcanbeallocatedtomorethanoneusersaslongastheyarenotinterferingwitheachother.Theseuniquedifferencesmakethetraditionalauctionalgorithmsinapplicabletospectrumauctions.Inthiscontext,wefocusononlineauctionsinparticularwherethenumberofbiddersandspectrumunitsarenotknownaprioriandtheauctioneerneedstomakedecisiononline.ThissettingisinlinewiththePUactivityandspectrumdemandfromtheopportunisticusers.Wealsoconsiderthediversityinbidders'transmissionrequirements.Forexample,adelaytolerantusercanofoaddataatlatertimewhereasaninteractiveuserwantsimmediatespectrumaccess.Weconsiderdiversefeaturesofbiddersandsellersanddesignstrategyproofauctionalgorithmswhicharethenevaluatedintermsofefciencyandrevenue.71.4Contribution Withthearrivalofnewapplicationsofferingdifferentservices,thefuturenetworkrequirestoaccommodatethespectrumdemandoftheirusers.Inthisdissertation,weaddresssomeofthechallengestowardsaccomplishingthatrequirement.Thehighlightsofourcontributionareasfollows:(i)IEEE802.22[110]isthewirelessstandardforruralbroadbandaccess.SSDFattackisamajorprobleminIEEE802.22networks.OursolutionofthisproblempresentedinChapter3willbehelpfultodevelopasecurecollaborativesensingplatforminIEEE802.22.(ii)Sincethevideotrafcwilldominateinnearfuture,thenetworkshouldbeabletosupportreliablevideotransmissionwithlowinfrastructurecost.OurresultsfromtherelaybasedcollaborationmodelwillbeusefultodevelopareliablenetworkbasedonmutualcooperationbenetsbetweenthePUsandSUs.Theresultsarefurtherextendedfromasinglehopmodeltomulti-hopcollaborationmodel.(iii)Theubiquitousnessofwirelessserviceswillincreasethenumberofconsumerswhowillwanttoaccessnetworksanytimeanywhere.Thediversityintherequirementsoftheseusersandsuppliesneedtobeaddressedonlinetobuildbetterspectrumsharingmodelsaroundit.Ourproposedauctionmechanismspresentedinthisdissertationensureonlinespectrumallocationanddeterminepriceconsideringdiversitiesofboththebuyersandsellers.1.5Organization Thisdissertationisorganizedintoseveralchapters.InChapter2,werstprovidesomebackgroundinformationrelatedtoourresearch,thenpresentanextensivesummaryofrelatedworkondifferent8collaborationmodels.Eachofthefollowingchaptersaddressesaspecicproblembasedonuserrequirementsandcollaborationmodels.Chapter3addressestheSSDFattackinIEEE802.22networksundersensingbasedcollaborationmodelandpresentsanadaptiveclusteringalgorithmtopreventsuchattacks.Chapter4focusesonthechallengeswithreal-timetrafcandpresentsaninterferenceawarereliablecooperationalgorithminrelaybasedcollaborationmodel.Chapter5exploresthemulti-hoprelaybasedcollaborationmodeltoestablishstableroutingpathsforthePUswhileensuringSUtransmissionopportunities.InChapter6,weanalyzethediversityofbiddersandsellersunderauctionbasedcollaborationmodel.Wedeveloponlinesingleanddoubleauctionalgorithmsthatensuretruthfulness,individualrationality,budgetbalance,andimproveefciencyandrevenue.Finally,Chapter7concludesourworkanddiscussesourfutureresearchdirections.9Chapter2 BackgroundandRelatedWork Tobetterunderstandtheresearchproblemsandtheproposedsolution,weprovidesomeback-groundinformationaboutsomerelevanttopics.Wealsopresentacomprehensivesummaryofexistingresearchworkonthreecollaborationmodels. 2.1Background 2.1.1SpectrumLicensing Ineachcountry,spectrumlicensingishandledbyagovernmentauthorizedentitythatregulatesspectrumallocation,usageanddistributionamongtheinterestedproviders.IntheUS,FederalCommunicationCommission(FCC)isresponsibleformanagingandlicensingradiospectrumthroughoutthecountrytoadiverserangeofcommercialandnon-commercialusersincludingpub-licsafetyandemergencyresponseservices[36].Sinceitsformationin1934,theFCCworkswithspecicgoalsofadvocatinginnovationandinvestmentinbroadbandservices,offeringhigh-estandbestspectrumallocationtechniques,andensuringefcientandreliableaccesstoallocatedspectrum.Currently,theFCCcontrolstheallocationofspectrumbetween9KHzand275GHz.BasicallytherearetwowaystheFCCmakesspectrumavailabletowirelessservices-licensedandunlicensed.Thelicensedspectrumassignmentisusuallydonethroughspectrumauctions.Notethatdifferentradiofrequenciesholddifferentpropagationcharacteristicsandaresuitablefordif-10ferentservices.TheFCCholdsauctionforaspecicfrequencybandandselectsthehighestbidderaswinneramongtheinterestedserviceproviders.TheFCCthengrantsthewinnerpermissiontousethatspectrumbandforaspecicorentiregeographicallocation.Forexample,cellularserviceisintherangeof824-849MHzand869-894MHz[107].Intheunlicensedspectrum,usersoperatewithoutanylicense,however,mustcomplywiththetechnicalrequirementsguidedbytheFCC.TheFCCalsograntsexclusiveaccesstospecicspectrumrangetopublicsafetyagenciesandrstresponders. 2.1.2FCCReformationInitiatives ItisevidentfromthepresentstatisticsandtheCiscotrafcforecast[25]thatitisnotpossibletosatisfythegrowingdemandusingtraditionalspectrumlicensingtechniques.TheFCCadvocatesaninnovativeapproachofspectrumsharingbetweenlegacynetworksandnewusersviadynamicspectrumaccess(DSA).Basedonearlystatistics,theFCCopenstheTVbroadcastchannelsforunlicensedaccesswithanimposedinterferenceconstraint[38][37].Ithasbeenproposedtocreateadatabasewithspectruminformation.In2010,theFCCpresentedtheNationalBroadbandPlan(NBP)whichrecommendsseveralstepstoreformthespectrumpolicytoaddressthespectrumsit-uation[90].Therecommendationsincludetakinginitiativetomake500MHzofspectrumavailableforbroadbandaccess,offeringincentivesandmechanismstorepurposespectrum,andexpandingopportunitiesforinnovativespectrumaccessmodels.Subsequently,theFCChasstartedanincen-tiveauction,rstofitskind,inthemonthofMarchof2016[58].Recently,theFCCisplanningtosharethe3:5GHzspectrumwhichiscurrentlyusedbythegovernmentradarsandxedsatel-lites[26].Athreelayeraccesspolicyhasbeenproposed.Inthisproposal,thelegacynetworkhasthehighestpriorityandoperatesontherstlayer,thesecondlayerprovidesaccessbasedonanincentiveauction,andthethirdlayerisopentousersforunlicensedaccess.112.1.3SpectrumSensing Anumberofdifferentsensingalgorithmsarepresentedinliterature[101][42][9].Themostcommonsensingtechniqueisenergybaseddetectionduetoitslowcomputationalcostandimple-mentationalcomplexities.ThereceivedsignaliscomparedwithapresetthresholdvaluetodetectthepresenceofPU.ThechallengeofthistechniqueincludestheappropriatethresholdselectionanditsdifferentiationbetweenPUsignalandnoiseunderlowsignal-to-noise(SNR)values.Inthewavelet-basedsensing,knownpatternisusedtodetectPUsignalthatensureshigherreliabilityandfasterconvergencethantheenergydetectionmethod.Anothersensingmethodistoexploitcyclostationaryfeaturesofthereceivedsignals.Cyclostationaryfeaturescanevenbeusedtodis-tinguishamongdifferenttypesoftransmissionsandprimaryusers.WiththeknowledgeofthetechnologyusedinPUtransmission,severalfeaturescanbeextractedfromthereceivedsignalandvariousclassicationmodelcanbeappliedtodetectthePUsignal.Besidesthesesensingmethods,fewothermethodsarepresentedinliterature[133].However,detectionperformanceofanindividualsecondaryuseroftensufferfrommultipathfading,shadowing,receiveruncertaintyissues[4].Collaborativespectrumsensingisfoundtobeaneffectivesolutiontoovercometheselimitations[133]. 2.1.4IEEE802.22WRANStandard TheIEEE802.22standardhasbeenstartedbeingdevelopedin2004[1][29].Itistargetedtoprovidelowpopulationdensityruralareaswithbroadbandaccess.IEEE802.22denesacentral-ized,singlehop,pointtomulti-pointcommunicationstandardforwirelessregionalareanetwork(WRAN).ThebasestationisconnectedtotheInternetthroughabackhaulwhilethecustomerpremiseequipments(CPE)areconnectedtothebasestationthroughvacantTVchannels.The12usersapplycognitiveradiotechniquestoavoidinterferencetobroadcastusers.Thespectrumsensingiscontrolledandcoordinatedbythebasestation.Thebasestationalsohasaninterfacetoaccessthespectrumdatabase.Thenetworkoperatesover54-862MHzandusesOFDMAtechnol-ogy[1].Acompleteproposaldraftanditsamendmentscanbefoundhere[122].2.1.5RelayingStrategies Inrelaybasedcollaborationmodel,theprimarysourcenodesendspackettoanintermediatesec-ondarynode,andthenintermediatesecondarynodeforwardsittothedestination.Therearegen-erallytwostrategiesusedinrelayingpacketsfromsourcetodestination.Theyareasfollows:(a)AmplifyandForward(AF)[28]:Therelaynodereceivesthesignalatrst,thenampliesit,andnallyrelaysittothedestination.(b)DecodeandForward(DF)[28]:Therelaynodetriestodecodethesignalafteritreceiveditfromthesourceandextracttheintendedmessage.Itthenre-encodesthemessageandtransmitsittothedestination.TheAFstrategyispreferredwhentherelaynodeisclosertothedestination,andtherelaydoesnotneedtousemuchpower.Sincetherelayampliesthenoisyreceivedsignal,thenoiseisalsoampliedanditseffectbecomesmoreseverewhentherelayisfarfromawayfromthedestination.Ontheotherhand,theDFstrategyworksbetteriftherelaynodeisclosertothesource.Itisthenmoreprobablethattherelaynodedecodesthemessagewithoutanyerror.Boththeserelayingstrategiesarestudiedinrelaybasedcollaborationmodel[86][50][23]toexplorethecooperationbenetsoftransmittingprimarypacketsthroughsecondaryusersincognitiveradionetworksunderinter-usercollaborationmodel.Thereisanotherlessknownrelayingstrategycalledcompressand13forward(CF)[28].Inthisstrategy,therelaynodequantizesthereceivedsignal,encodesthesamplesintoanewmessage,andthenforwardsthemessagetothedestination.2.1.6VCGAuctions Ingeneral,anauctionmechanismshouldhavethefollowingpropertiessuchastruthfulness,in-dividualrationality,andbudgetbalance.Thetruthfulnesspropertyensuresthatabiddercannotincreaseitsprotbymanipulatinganyofitsinformation.Individualrationalitymeansthatanyparticipantintheauctionmustachievenonnegativeprot.Anauctionisbudgetbalancedifthetotalamountpaidtothesellersisnogreaterthanthetotalamountpaidbythebidders.ThedesignofsecondpriceauctionbyVickreyensurestruthfulbiddingofbidders.Accordingtothisauction[72],biddersplacetheirsealedbids.Thehighestbidderwinsbutpaysequaltothesecondhighestbid.ThisconceptisfurthergeneralizedbyVickrey,Clarke,andGroves[138].Intheirproposedsealedbidmulti-unitauction(referredtoas`VCGauction'),biddersbidtheirvaluationsforthedesireditemwithoutknowingthebidinformationofcompetingbidders.Theauctioneerassignsitemsinasociallyoptimalmanner.Eachwinnerischargedtheamountequaltothebidofthelosingbidderwhocouldwinifthewinnerwerenotpresent.Thismechanismisageneralizationofthesecondpriceauctionandisprovedtobeincentivecompatibleandindividualrational.Themechanismisattractivesinceitguaranteestruthfulreportingasthebeststrategyofabidderandabiddercannotincreaseitsprotbymanipulatingitsbid.However,thismecha-nismdoesnotguaranteetruthfulnesswhenthebiddershaveexibledeadlinesandtheirarrivalisdynamic.142.1.7McAfeeAuction McAfeeinhisseminalpaper[88]designedadominantstrategyforbothbuyersandsellersinastaticdoubleauction.Thisstrategyisusedtodesignatruthfulmechanismforspectrumdoubleauctions[20,143].Accordingtothisstrategy,biddersinthesetTaresortedintonon-increasingorderofbidb1b2:::bn0wheren0denotesthenumberofbiddersintheauction,i.e.,jTj=n0.ThesellersinsetS0aresortedintonon-decreasingorderofaska1a2:::am0wherem0denotesthenumberofsellersintheauction,i.e.,jS0j=m0.Theminimumbidofthebiddersb(n0+1)andthemaximumaskofthesellersa(m0+1)aresetto1and1respectively.Then,hpairsareselectedsuchthat8ih;biaiandb(h+1) > > < > > > :H1ifPn i=1Din0H0otherwiseThespecialcase(whenn0=1)isreferredtoasORrule(ifanyofthenodessensethechannelbusy,BSdecidesabusychannel).Thisapproachisveryconservativeinthesensethatonesingleattackerorevenamalfunctioninghonestnodecanreducethespectrumutilization.Thealternativeapproachistodecidedependingonmajorityvoting(e.g.n0=n2).Thisresolvesthespectrum27underutilizationproblembutsignicantlyincreasesthemisdetectionrate.Asaresult,itbecomesvulnerablewhenattackerscollaborativelydecidetheirattackingstrategyaswell.3.1.3HonestUserModel WeassumethatevenanhonestusercannotdetectPUpresencewith100%accuracy.WedenefalsealarmrateastheprobabilityofsensingthepresenceofaPUwhenitisactuallynottrans-mitting,andwedenemisdetectionrateastheprobabilityofnotsensingaPUwhenitisactuallyoperating.LetusassumethattheprobabilityoffalsealarmandmisdetectionrateofauserarePfaandPmdrespectively.Pfa=Pr(yi=1jH0);Pmd=Pr(yi=0jH1)whereyirepresentsthesensedresultbyuseri.Asexplained,honestusersdonotchangetheirsensingresults.LetusassumethatxirepresentsthereportsenttotheBSbyuseri.Pr(xi=1jyi=1)=1;Pr(xi=0jyi=1)=0;Pr(xi=0jyi=0)=1;Pr(xi=1jyi=0)=0Accordingly,wecancalculatethedetectionprobabilityofanhonestuser,PhdetectusingEqn.3.1.Phdetect=Pr(xi=0jH0)Pr(H0)+Pr(xi=1jH1)Pr(H1)=(1Pfa)PI+(1Pmd)PB(3.1)Here,PIandPBdenotetheactualidleandbusyrateofthechannelrespectively.283.1.4AttackModel Weconsiderthatattackersdevisetheirplanindependentlyorcollaboratively.Basedontheirat-tackingstrategy,eachattackernodemayalteritssensingresultfrombusytoidleandfromidletobusywithdifferentprobability.Wealsoassumethatbothoftheprobabilitiesarethesame.How-ever,ourresultscanbeeasilyextendedfordifferentprobability.Accordingly,weconsideroneindependentandthreecollaborativeattackingtechniques.Weselectedtheattackingtechniquesconsideringtheeaseofimplementation,impactoftheattack,frequencyofattackandsoon.Therstcollaborativetechniquefinloutofnaflwasalreadyshowntobeeffectivein[7].Thesecondtechniqueisconsideredhereduetoeaseofimplementationanditfollowsanintuitiveattackingmodel.Thethirdtechniqueisconsideredtoexploittheproposeddecisionmechanismused.3.1.4.1IndependentAttack EachindependentattackerchangesitssensingresultwithprobabilityPmal.Thedetectionproba-bilityofanindividualattacker,PadetectwhileworkingindependentlycanbeexpressedusingEqn.3.2.Padetect=Pr(xa i=0jH0)Pr(H0)+Pr(xa i=1jH1)Pr(H1)=[(1Pmal)(1Pfa)+PmalPfa]PI+[(1Pmal)(1Pmd)+PmalPmd]PB(3.2)Similarly,wecanndthefalsealarmprobabilityofanattacker(Pafa).3.1.4.2CollaborativeAttack InthecaseofacollaborativeSSDFattack,attackersexchangetheirsensinginformationanddecidetheirresponsecollaboratively.First,weconsiderthecollaborationstrategy`nloutofna'attack.29Itisshownin[7]thatonly35%ofattackersusingthisapproachcanblindthedecisionmechanismoftheBS.LetusassumethatPa1detectandPa1fadenotethecommondetectionprobabilityandfalsealarmprobabilityofattackers.Inthiscase,Pa1detectandPa1fawillbe,Pa1detect=naXi=nl(na;i;Padetect);Pa1fa=naXi=nl(na;i;Pafa)(3.3)where,(na;i;k)=nai(k)i(1k)nai:Here,nlisdenedin[7]nl=minna;˘na1+ˇwhere,=lnPfaPhdetectln1Phdetect1PfaThesecondcollaborationtechniqueisinspiredfromthefactthatifamajorityofthenodesaltertheirsensingreports,theBSwilltakeawrongdecision.Accordingly,weconsidertheGoingAgainstMAjority(GAMA)attacktoanalyzetheimpactofcollaborationinwhichallattackerssharetheirtruesensingresultsandthendecidetosendtotheBStheoppositetothemajoritysensingresultwithacertainprobability.Forexample,iftwoattackerssensethechannelidleandoneattackersensesthechannelbusy,allthreeattackersreporttotheBSthatthechannelisbusy.Inthiscase,thecommondetectionprobabilityofattackerswillbePa2detect=naXi=l(na;i;1Phdetect);Pa2fa=naXi=l(na;i;1Pfa)(3.4)wherel=na=2+1.ThethirdcollaborationtechniqueweconsideristheSubGroup(SG)attack.Thereasonwe30selectthisapproachistoinvestigatewhetheritispossibleforattackerstosuccessfullyattackandavoidbeingdetectedsimultaneouslyiftheyattackinsubgroups.Consequently,attackersformsmallgroups,andeachgroupchangestheirsensingresultaccordingtotherstapproach.Finally,onegroupischosenrandomly,andalltheattackersinthatgroupreportthesamesensingresult.Wedidnotconsiderthatattackerscanoverhearthehonestusersanddevisetheirplanaccord-inglysinceitisnoteasytooverhearthesensingreportsfromallusers.Evenifanattackercanreportitssensingreportbasedonthat,itsresponsewillincurasignicantlatencytoreachtotheBSwhichcanbeexploitedtodiscarditfromthedecisionmechanism.Also,thistypeofattackwillbemoreeffectiveiftheBSfollowsanORruleinsteadofmajorityrule[32].3.2AlgorithmDesign-AttackersvsBS Inthissection,weshowtheimpactofattackersinthedecisionmechanismandexplainthedefensemechanismthattheBSusestodefendagainstdifferentattackingstrategiesindetail.3.2.1Attackers'Impact Inthissection,weanalyzetheimpactofattackers,bothindependentandcollaborative,inthedecisionmechanismoftheBS.Letusassumethatthebasestationdecidesbasedonamajorityvoting.LetXandYdenotethenumberofhonestusersandmalicioususersthatdetectthechannelstatuscorrectly.Sinceallthehonestusersareindependent,XfollowsabinomialdistributionwithparameternhandPhdetect.Similarly,inthecaseofindependentmaliciousattack,YalsofollowsabinomialdistributionwithparameternaandPadetect.So,PS,theoveralldetectionprobabilityofthesystem,canbecalculatedusingthejointdistributionofdetectionprobabilityofindependenthonestusersandindependent31Figure3.1:Systemdetectionaccuracywithvaryingattackersattackers.Let,k=(na+nh)=2.PS=Pr(X+Y>k)=nhXi=1(nh;i;Phdetect)naXj=ki(na;j;1Padetect)Inthecaseofcollaborativeattack,thedetectionprobabilitydegradesaccordingtotheircollab-orationstrategy.Here,weonlydemonstratetheimpactofaGAMAattackasarepresentativeofcollaborativeattack.Similarly,othervariationsofcollaborativeattackscanbeexplored.LetusconsidertheGAMAattackwhenalltheattackerschangetheirdecisionagainstthemajoritysensingresultwithprobabilityi.e.Pmal=.So,eitherallattackerssendcorrectchannelstatusornoneofthemsendscorrectreport.Forsimplicity,letusassumethatprobabilityofattackis1.So,attackersalwayssendtheoppositeofthemajoritysensingresults.LetPYdenotetheprobabilitythatalltheattackerswillsendcorrectsensingreportinGAMAattack.Thisisequivalenttothecasewhenmajorityattackersfailtosensethecorrectchannelcondition.PY=Pr(YdA1A2anddA1H>dHH(b)case2:dA1A2>dA1HanddHH>dA1HFigure3.5:Relationshipsamongattackersandhonestusersbeequaltozero.(PdiffHHjjPdiffAH)=PdiffHHlog2PdiffHHPdiffAH=0(3.15)Ontheotherhand,wecanestimatethedistancebetweenanhonestuserandanattackerandbetweentwohonestusersaccordingtothestronglawoflargenumbersfromtheclusteringpointofview.Accordingly,thenormalizeddistancebetweenanytwohonestusersdHHconvergestoPdiffHHwithtime.Similarly,thenormalizeddistancebetweenanhonestuserandanattackerdAHconvergestoPdiffAHwithtime.Itfollowsthatifthesetwoprobabilitiesareequal,thendistancebetweenanhonestuserandanattackerandbetweentwohonestusersareapproximatelyequal.Hence,attackersandhonestuserswillendupinthesameordifferentclusterswithequalprobabilityandcannotbeseparatedbyARC.Withsimilaranalysisin[78],itcanbeshownthatmalicioususerscanavoidthedetectionbysettingproperPmalifthefalsealarmandmisdetectionprobabilitiesaregreaterthanorequalto0:4.However,asthestandardfalsealarmandmisdetectionprobabilityare0:1,wecanconcludethatindependentattackerscannotdefeattheARCinnormalconditions.ThealternativeapproachtodeceiveARCistotakecontrolofthemajorityoftheclusterswhichweexploredinSubGroupattack.Itiseasilyobtainableifattackersoutnumberthehonestusers.43Otherwise,thepossiblewaytomanipulatethedecisionmechanismistospreadoutintodifferentclustersanddominateindecisionmakingofeverycluster(or,majorityoftheclusters)consistently.Accordingly,eachattackergroupworkswithadifferentattackingprobability,andallmembersinagroupreportthesamesensingresulttoinuencetheclusterdecisionintheirfavor.LetusassumethattheattackingprobabilityoftheattackergroupAiisi,andtheprobabilitythattheattackergroupAiandthehonestuserdifferintheirsensingreportsatanytimeisPdiffAiH.Similarly,PdiffAiAjdenotestheprobabilitythatanyattackergroupAiandattackergroupAjdifferintheirsensingreportsatanytime.PdiffAi;Aj=[iPfa+(1i)(1Pfa)][j(1Pfa)+(1j)Pfa]+[i(1Pfa)+(1i)Pfa][jPfa+(1j)(1Pfa)](3.16)Hereforsimplicity,weassumePfa=Pmd.Accordingtothestronglawoflargenumbers,thenormalizeddistancedAiAjbetweenanytwoindependentattackergroupsAiandAjconvergestoPdiffAiAjwithtime.Similarly,thenormalizeddistancebetweenhonestusersandbetweenanyattackergroupandhonestusercanbeestimatedandarerepresentedasdHHanddAiHrespectivelywhichareequivalenttoPdiffHHandPdiffAH.So,theclustersareformedbasedontherelativedistancebetweenhonestusersanddifferentattackergroups.Now,weneedtoanswerthefollowingquestionfromattackers'perspective:WhatshouldbetherelationshipamongdHH,dAiH,anddAiAjtomanipulatetheclusterformationanddeceiveARCcompletely?Inordertoachievethat,differentgroupsofattackersshouldnotbeinthesameclusterandalsoattackersmustpreventclusterformationwithhonestusersonly.Fig.3.5illustratestheclustercharacteristicsfordifferentcases.Case1showstheexpectedclusterformationforanydetectionalgorithmwhereattackersandhonestusersareindifferentclusters.Case2showsthe44expectedformationforattackerswhereeachclusterisformedwithcombinationofattackersandhonestusers.Theattackerswilltrytomaximizetheerrorindecisionmakingwhilesatisfyingtheconditionsofcase2inFig.3.5.Forexample,considerthecaseof3clusters.Theattackerswillbesuccessfulifatleasttwoofthegroupsattackandiftheprobabilityofdifferenceinsensingresultbetweenanygroupofattackerandhonestusersmustbelessthanminimumofthedifferencebetweentwogroupsofattackersandbetweenanytwohonestusers.Furthermore,attackersmustbedominatinginthemajorityofclusterstotakecontrolofthedecisionmechanismthatdependsoninitialseedselectionandnumberofiterationsusedforclusterformation.Hence,themaximizationfunctionforattackerscanbestatedasfollows.max1232 4Xi;j;kij(1k)+Yii3 5suchthat8i;jPdiffAiH0Sincethenodesdonotknowtheactualchannelstatus,itisunlikelythattheattackerscancalculatetheexactvalueofPdiffHH.EveniftheycanestimatePdiffHH(itwillbesignicantlysmall),ndingtheattackingprobabilityfordifferentgroupsofattackerswhilesatisfyingthenecessaryconditioncannotbepossibleinanormalcondition.Fromtheaboveprobabilisticanalysis,wecanconcludethatARCcanwithstandallkindsofnonadaptiveindependentandcollaborativeattackundernormalconditions.453.5PerformanceEvaluation Inthissection,wediscusstheperformanceresultsofourproposedmethodbyspecicallycom-paringitseffectivenessagainstapreviouslyproposedmethodin[7].Fromthispoint,wewillrefertothisalgorithmasfiRawatmethodflor`R',bythenameoftherstauthorofthework[7].Wecomparethesetwoalgorithmsacrossbothindependentandcollaborativeattacksaswellasvariousprobabilitiesofattackunderarangeofsensingconditions.3.5.1PerformanceMetrics Inordertoevaluatetheperformanceofouralgorithm,weusethreeperformancemetrics.Firstoneistheprobabilityoferrororerrorrate,denotedasQE.Itdenoteshowmanytimesthebasestationmakesanincorrectdecision.Theloweristheerrorrate,thebetteristhealgorithm.ThesecondmetriciscalledtruedetectionrateorrecallandisdenotedasQD.Itiswidelyusedindataminingapplicationstoevaluatethesuccessfuldetectionofmembersofaclassthatareconsideredmoresignicantthanthedetectionofmembersofotherclasses.Algorithmswithhighervalueofrecallaredesirable.Inourwork,identifyingattackersismoresignicantthanidentifyinghonestusers.ThethirdmetricisfalsepositiverateandisdenotedasQF.Thismetricrepresentshowmanynodesaremisidentiedasattackers.Inthiscase,thelowerthefalsepositiverate,thebetterthealgorithmis.QE=#ofincorrectdecisionT(3.17)QD=#ofattackerstrulyidentied#ofactualattackers(3.18)QF=#ofhonestusersmisidentied#ofnodesidentiedasattackers(3.19)463.5.2SimulationParameters Weconsiderthatachannel'sidletimefollowsaBernoullidistributionwithparameter0:6.Inotherwords,primaryuserstransmitoverthechannelwithprobability0:4.Ateachtimestep,thechannelstatusisrandomlydrawnfromtheprobabilitydistributionfunction.Foreachtest,themethodsarerunfor80timesteps.Foreachtimestep,themethodsmustproduceanalhypothesis,whichiscomparedagainstactualtransmissionstateoftheprimaryusertodeterminethemethod'serrorrate(QE).Ratesforthecorrectdetectionofattackingnodes(QD)andtheincorrectdetectionofhonestusersasattackers(QF)arealsoreportedattheendofthetest.Eachtestisthenrepeated30timeswithanaverageofthevaluesdisplayedinthegraphs.Atestconsistsofrandomlygeneratedreportsforeachsecondaryuser,adheringtolabeledprobabilitydistributions.Foravalidationtest,weconsider=0:5.Foreachtypeofattack,wetesttheperformanceofthealgorithmwiththreevariations.Theyareasfollows.varyingnumberofattackersvaryingattackingprobabilityvaryingdetectionprobability3.5.3IndependentAttack Inthenextstep,wecomparetheperformanceofouralgorithmwithreputationbasedmethodin[7]forindependentSSDFattacks.Inthisattack,attackersdonotcollaboratetoexchangetheirreports.Eachattackerworksindependentlytomaximizeitsgoal.Fig.3.6showstheerrorrateoftwoalgorithmswithvaryingnumberofattackers.WekeeptheattackingprobabilityPmal=1.4710152025303540455000.10.20.30.40.50.60.7# of Attackers (out of 100 nodes)QE Error Rate(R)Error Rate(ARC)(a)ErrorrateQE1015202530354045500.40.50.60.70.80.91# of Attackers (out of 100 nodes)QD Recall(R)Recall(ARC)(b)RecallQD10152025303540455000.10.20.30.40.50.60.70.8# of Attackers (out of 100 nodes)QF False Detect(R)False Detect(ARC)(c)FalsePositiverateQFFigure3.6:Independentattackwithvaryingnumberofattackers0.50.60.70.80.9100.050.10.150.20.250.30.350.40.450.5Pmal (35 attackers, 100 total nodes)QE Error Rate(R)Error Rate(ARC)(a)ErrorrateQE0.50.60.70.80.910.40.50.60.70.80.91Pmal (35 attackers, 100 total nodes)QD Recall(R)Recall(ARC)(b)RecallQD0.50.60.70.80.9100.10.20.30.40.50.60.70.8Pmal (35 attackers, 100 total nodes)QF False Detect(R)False Detect(ARC)(c)FalsePositiverateQFFigure3.7:IndependentattackwithvaryingattackingprobabilityAlso,probabilitiesfortrueandfalsedetectionofasignalaresettoPhdetect=0:9andPfa=0:1.AlthoughouralgorithmperformsbetterthanRawatalgorithm,theerrorrateincreaseswiththenumberofattackers.Ontheotherhand,ouralgorithmperformsmoderatelytodetectmaliciousattackerswhiletheiralgorithmconsistentlyidentiesattackerswithhighprecision.However,theiralgorithmeliminatesalargenumberofhonestusersincorrectly.Fig.3.6showsthatabout40%honestusersaremisidentiedasattacker.Ontheotherhand,falsedetectionrateofouralgorithmisalmostnegligible.Althoughthereputationbasedalgorithmperformsbetterindetectingattackersthanouralgorithm,theymisidentiedalargenumberofhonestusersasattackers,whichmakestheiralgorithmlesseffective.Similarly,werunthesimulationforindependentSSDFattackswithvaryingattackingprob-ability.Wevarytheattackingprobabilityfrom0:5to1andplotQE,QD,andQFinFig.3.7480.50.60.70.80.9100.10.20.30.40.50.60.7Pdet (35 attackers, 100 total nodes)QE Error Rate(R)Error Rate(ARC)(a)ErrorrateQE0.50.60.70.80.910.20.30.40.50.60.70.80.91Pdet (35 attackers, 100 total nodes)QD Recall(R)Recall(ARC)(b)RecallQD0.50.60.70.80.9100.10.20.30.40.50.60.70.80.91Pdet (35 attackers, 100 total nodes)QF False Detect(R)False Detect(ARC)(c)FalsePositiverateQFFigure3.8:Independentattackwithvaryingdetectionprobabilityforouralgorithmandreputationbasedalgorithmproposedin[7].Again,ouralgorithmperformsbetterindecisionmaking(Fig.3.7).Errorrateofouralgorithmisalmostnegligiblewhiletheirerrorrateoftheiralgorithmincreasesalmostlinearlywithattackingprobability.Thetrueattackerdetectionrateisalmostthesameforbothalgorithmswhentheattackingprobabilityexceeds0:65.However,theiralgorithmconstantlyeliminates60%ofhonestnodesasattackersforanyattackingprobabilityrangingbetween0:5and1:0.Ontheotherhand,ouralgorithmperformssignicantlybetterandkeepsafalsedetectionrateclosetozero.Next,wevarythedetectionprobabilityofnodesfrom0:5to1:0andplotQE,QDandQFinFig.3.8forouralgorithmandreputationbasedalgorithmproposedin[7].Asusual,theerrorrateofouralgorithmoutperformstheiralgorithm.Also,ouralgorithmperformsbetterintermsofmisidenticationofattackers.However,theiralgorithmidentiesalmostallattackersirrespectiveofthedetectionprobability.Ontheotherhand,ouralgorithmgraduallyincreasesthetruedetectionratewiththeincreaseofdetectionprobability. 3.5.4CollaborativeAttack Wetestedbothmethods(Rawatmethod[7]andARC)againsteachofthecollaborativebyzantineattacksdiscussedinSection3.1.4.2.Therstsetofsimulation(Fig.3.9)presentstheresultfor4910152025303540455000.10.20.30.40.50.60.7# of Attackers (out of 100 nodes)QE Error Rate(R)Error Rate(ARC)(a)ErrorrateQE10152025303540455000.10.20.30.40.50.60.70.80.91# of Attackers (out of 100 nodes)QD Recall(R)Recall(ARC)(b)RecallQD10152025303540455000.10.20.30.40.50.60.70.80.91# of Attackers (out of 100 nodes)QF False Detect(R)False Detect(ARC)(c)FalsePositiverateQFFigure3.9:Collaborativeattackwithvaryingnumberofattackers0.50.60.70.80.9100.10.20.30.40.50.60.7Pmal (35 attackers, 100 total nodes)QE Error Rate(R)Error Rate(ARC)(a)ErrorrateQE0.50.60.70.80.9100.10.20.30.40.50.60.7Pmal (35 attackers, 100 total nodes)QD Recall(R)Recall(ARC)(b)RecallQD0.50.60.70.80.9100.10.20.30.40.50.60.70.80.91Pmal (35 attackers, 100 total nodes)QF False Detect(R)False Detect(ARC)(c)FalsePositiverateQFFigure3.10:Collaborativeattackwithvaryingattackingprobabilitythecollaborativeattackdenedin[7].Thenumberofmalicioususersrangefrom10to50outof100totalsecondaryusers.Theattackingprobability(Pmal)issetto1.Sensingprobabilitiesforcorrectlydetectingasignalandfalselydetectingasignalweresetto(Phdetect)=0:9and(Pfa)=0:1respectively.ARCoutperformsconsistentlywithrespectto(QE)showingamarkedlydecreasederrorrateuntilroughly50%ofthepopulationbecomesattackers.Oncethepopulationcontainsamajorityofmalicioususers,itisimpossibleforanysensingstrategytosustainanerrorrateunder50%.TheRawatmethodshowsahighQDinitiallybutquicklydiminishesafter20%ofnodesareattackersandbecomescompletelyineffectivewhen1=3ofthepopulationareattackers.Atapproximatelythesameattackerconcentration,ourmethodexceedsandmaintainsamarkedincreaseinidenti-fyingattackers.Conversely,theRawatmethodbeginswithasignicantfalsedetectionrate(QF)500.750.80.850.90.95100.10.20.30.40.50.60.7Pdet (35 attackers, 100 total nodes)QE Error Rate(R)Error Rate(ARC)(a)ErrorrateQE0.750.80.850.90.95100.10.20.30.40.50.60.70.80.91Pdet (35 attackers, 100 total nodes)QD Recall(R)Recall(ARC)(b)RecallQD0.750.80.850.90.95100.10.20.30.40.50.60.70.80.91Pdet (35 attackers, 100 total nodes)QF False Detect(R)False Detect(ARC)(c)FalsePositiverateQFFigure3.11:Collaborativeattackwithvaryingdetectionprobabilitywhileourmethodminimizesthisrateacrosstheentirerangeofattackers.Maintainingalowmisde-tectionrateallowsourmethodtomaximizehonestuserreportsandmitigatetheimpactofattackersevenunderheavyattacks.Asecondsetofmeasurementsobservedtheimpactofcollaboratingmalicioususerswhenvaryingtheirprobabilityofattack.Malicioususerscanutilizethistechniquetoescapedetectionfromhighdimensionalclusteringmethods.InFig.3.10,attackersproduceonaveragelessthan20%errorrateswhiletheRawatmethodsustainssignicanterrors.Regardlessofattackingrate,ourmethodconsistentlyidenties50%oftheattackers.TheRawatmethodexhibitsanunusuallyhighattackermisdetectionrate,whichislikelytoleadtothehigherrorrate.Thenexttestlooksatconsequencesofvariablesensoraccuracy(Fig.3.11).Here,35collab-oratingmalicioususersattackduringeachsensingstep.Bothmethodsbeginwithrelativelyhigherrorrates,asthesensingreportsofhonestusersresemblethatofattackersduetotheinaccuratesensorreadings.Oncesensingerrorsfallbelow65%,ourproposedmethodshowsalinearde-creaseintheHypothesiserrorrate.TheRawatmethodtakessignicantlyhigherdetectionrates(approximately80%)beforeerrorratesbegintodecline.Wealsotestouralgorithminthecaseofsubgroupcollaborativeattacks(Fig.3.12).Weassumethatattackersknowthenumberofclustersandcreateequalnumberofgroupsofattackers.At-5110152025303540455000.10.20.30.40.50.60.70.80.9# of Attackers (out of 100 nodes)QE Error Rate(R)Error Rate(ARC)(a)ErrorrateQE1015202530354045500.50.550.60.650.70.750.80.850.90.951# of Attackers (out of 100 nodes)QD Recall(R)Recall(ARC)(b)RecallQD10152025303540455000.10.20.30.40.50.60.70.80.91# of Attackers (out of 100 nodes)QF False Detect(R)False Detect(ARC)(c)FalsePositiverateQFFigure3.12:CollaborativeSubGroupattackwithvaryingnumberofattackers0.50.60.70.80.9100.050.10.150.20.250.30.350.40.45Pmal (35 attackers, 100 total nodes)QE Error Rate(R)Error Rate(ARC)(a)ErrorrateQE0.50.60.70.80.910.50.550.60.650.70.750.80.850.90.951Pmal (35 attackers, 100 total nodes)QD Recall(R)Recall(ARC)(b)RecallQD0.50.60.70.80.9100.10.20.30.40.50.60.70.8Pmal (35 attackers, 100 total nodes)QF False Detect(R)False Detect(ARC)(c)FalsePositiverateQFFigure3.13:CollaborativeSubGroupattackwithvaryingattackingprobabilitytackersareequallydistributedinallsubgroups.Asthenumberofattackerincreases,QEincreasesslightlyinouralgorithmwhileQEreachesalmost40%inthereputationmethod.Asexpected,boththeirtruedetectionandfalsedetectionrateishigh.Ontheotherhand,QDisabout65%andQFisalmostnegligibleinouralgorithm.Similarly,ouralgorithmoutperformsRawatalgorithmintermsoferrorrate,recallandfalsedetectwithvaryingattackingprobability(Fig.3.13)andwithvaryingdetectionprobability(Fig.3.14).WendinterestingresultsforattackerswithGAMAstrategy.Inthecaseofouralgorithm,QEis0andonlyincreaseswhenthenumberofattackersexceeds37.Ontheotherhand,QEincreasesalmostlinearlywiththenumberofattackersinthereputationbasedmethod.Wegetsimilarresultsintrueandfalsedetectionrate.TheresultsareplottedinFig.3.15.Similarly,ouralgorithmoutperformsRawatalgorithmwithvaryingattackingprobabilityandwithvarying520.50.60.70.80.9100.10.20.30.40.50.60.7Pdet (35 attackers, 100 total nodes)QE Error Rate(R)Error Rate(ARC)(a)ErrorrateQE0.50.60.70.80.910.40.50.60.70.80.91Pdet (35 attackers, 100 total nodes)QD Recall(R)Recall(ARC)(b)RecallQD0.50.60.70.80.9100.10.20.30.40.50.60.70.80.91Pdet (35 attackers, 100 total nodes)QF False Detect(R)False Detect(ARC)(c)FalsePositiverateQFFigure3.14:CollaborativeSubGroupattackwithvaryingdetectionprobability10152025303540455000.10.20.30.40.50.60.70.8# of Attackers (out of 100 nodes)QE Error Rate(R)Error Rate(ARC)(a)ErrorrateQE1015202530354045500.40.50.60.70.80.91# of Attackers (out of 100 nodes)QD Recall(R)Recall(ARC)(b)RecallQD10152025303540455000.10.20.30.40.50.60.70.80.9# of Attackers (out of 100 nodes)QF False Detect(R)False Detect(ARC)(c)FalsePositiverateQFFigure3.15:CollaborativeGAMAattackwithvaryingnumberofattackersdetectionprobability.Theresultsarenotshownduetopagelimitation.Interestingly,Rawatalgorithmshowshighererrorratewithhigherdetectionprobabilityinallcases(seeFig.3.8a,3.14a).Thisisbecausetheattackerscontributetothecorrectdecisionmakingbyalteringthesensingresultsinthecaseoflowdetectionprobability.Asdetectionprobabilityincreases,alteringthesensingresulthelpsattackersincreasingerrorrate.Thetruedetectionratealsodecreaseswithhigherdetectionprobabilityforthesamereason.Wealsoexaminedtheclusters'convergencetime.Theclustersbecomestableafter8to10timestepsonaverage.However,ifthestartingdimensionofeachnodegoesbelow20,theclusterperformancedegradessignicantly.Therefore,tostartwith,wemaintainthelatest20sensingreportsofallnodesinoursimulation.Wealsosimulatedanalternativeapproachwhereinsteadofremovingattackernodesfromthedecisionmechanismcompletely,weresettheiridentityandstart53(a)withvaryingnumberofattackers0.50.60.70.80.9100.10.20.30.40.50.60.7Qgoal (35 attackers, 100 total nodes)QE Error Rate(R)Error Rate(ARC)(b)withvaryingattackinggoalFigure3.16:AdaptivecollaborativeSubgroupattackthealgorithmagain.Theresettimerissetaftertheconvergenceoftheclusters(e.g.after10timesteps).Asaresult,theperformanceresultsdonotchangesignicantly.3.5.5AdaptiveAttack Sofar,wehaveonlyconsiderednon-adaptiveattack.Inthissection,weconsideranadaptivevariationofbothindependentandcollaborativeattackswhereattackersadaptivelychangestheirstrategiestoreachcertaingoalintermsofattack.Intheindependentadaptiveattackingapproach,eachattackerstartswitharandomattackrate,periodicallycomparesitssuccessratewithitssetgoal,andadjustsitsattackrateaccordingly.WendthatindependentattackerscannotsignicantlyimpactthedecisionmechanismoftheBSinbothapproaches(theerrorratenevergoesabove10%).Inthecaseofadaptivecollaborativeattack,weonlyconsiderthevariationofSubGroupattack.Similartoindependentadaptiveattack,attackerssetacommongoal(Qgoal)ofachievingsuccessintermsofattack.EachsubgroupofattackersstartswithrandomattackingprobabilityPmal,periodicallycheckstheirpresentsuccessrate(QE)withthesetgoalandlinearlyincreases(or,decreases)theirattackingrates(Pmal)toreachtheirtargetsuccessrate.Intherstsimulation54set,wesetQgoal=0:8andvarythenumberofattackers.ThesimulationresultinFig.3.16ashowsthatouralgorithmperformssignicantlybetterthanRawatalgorithmintermsoferrorrate.Thenumberofattackersarevariedupto45sinceboththealgorithmshowsrandombehaviorinthepresenceof50%attackers.Inthesecondsimulation,thenumberofattackersaresetto35andnumberofsubgroupscreatedare5.ThesimulationresultsarepresentedinFig.3.16bwithvaryingattackinggoalforboththealgorithms,anditshowsthatouralgorithmoutperformsRawatalgorithmwithsignicantmargin. 3.6Summary Inthischapter,wediscussoneofthemajorsecurityproblemsafictingCRNsandproposeareputationbasedclusteringalgorithmtodefendagainsttheseattacks.Weusereputationofnodesinadditiontotheirsensinghistorytoformclustersandthenadjustreputationbasedontheclusteroutput.Thisrecursiveapproachistestedinthepresenceofindependentandcollaborativespectrumsensingdatafalsicationattacks.Withrespecttocurrentapproaches,ouralgorithmsignicantlyreducestheerrorrateinthenaldecisionmakingprocess,thusincreasingspectrumutilization.Thefalsedetectionratebyouralgorithmisalmostnegligiblewhiletrueattackerdetectionrateperformsreasonablywell.However,theinitialnumberofclustersplaysanimportantroleinoverallperformanceofthealgorithm.55Chapter4 InterferenceAwareReliableCCRNsfor Real-timeApplications Withgrowingreal-timetrafcandlimitedspectrumresources,thecommunicationsystemmustadoptreliableandefcientspectrumsharingtechniquesforprovidingimprovedservicestoendusers.Relaybasedcollaborationmodelbetweentheprimaryandsecondaryuserswillplayanimportantroleinreshapingandrestructuringthespectrumallocationmechanism.Intheworkpresentedinthischapter1,weproposeanewmethodforconstructingreliablereal-timenetworksystemssuchasreal-timeindustrialautomationmeshnetworks[46]andtime-criticalsensornet-works[24].Suchareal-timenetworkrequirespacketstobedeliveredwithinadeadline.Accord-ingly,wemeasurethereliabilityofthesereal-timenetworksusingpacketreceptionrate.Whenauserinsuchnetworkstransmitsapacket,areceivermayfailtodecodethepacketintimebecauseofatemporarilyunstablelinkduetorandomnoise,fading,andshadowingorcollisionwithotherongoingtransmissions.Waitinguntilsuchalinkisusableagainisnotacceptableinreal-timesys-1Theworkpresentedinthischapterhasbeenpublishedinthreeresearcharticles:(i)ChowdhurySayeedHyder,ABMAlimalIslam,LiXiao,andEricTorng.flInterferenceawareReliableCoop-erativeCognitiveNetworkswithforReal-timeApplicationsfl,inIEEETransactionsonCognitiveCommuni-cationsandNetworks(TCCN),2(1),pp53-67,May2016.(ii)ChowdhurySayeedHyder,ABMAlimAlIslam,LiXiao,flEnhancingReliabilityofReal-timeTrafcviaCooperativeSchedulinginCognitiveRadioNetworksfl,at23rdInternationalSymposiumonQualityofService(IWQoS),pp249-254,Portland,Oregon,USA,June15-16,2015.(iii)ChowdhurySayeedHyder,LiXiao,andMaxEllison,flExploitingCooperationforDelayOptimizationinCognitiveNetworksfl,at9thInternationalConferenceonMobileAdhocandSensorSystems(MASS),pp362-370,LasVegas,Nevada,USA,October8-11,2012.56temsiflinkdowntimecanexceedpacketdeadlines.Evenifthelinkbecomesstable,traditionalretransmissionofdroppedpacketsmaynotdeliverthepacketintimeatthereceiver.Weproposetouserelaybasedcollaborationmodelaspartofthesolutionfordevelopingreli-ablereal-timenetworksystemsleveragingtheexibilityanddiversityofCRNtoovercometran-sientpackettransmissionissues.Forexample,cooperativecommunicationcanmitigatechannelfadingbyexploitingspatialdiversitywhichleadstonewtransmissionpaths[52,57,136].BasedonthetransmissionmodelinCRN,secondaryusersaregrantedchannelaccessbyprimaryusersinreturnfortheirserviceinrelayingprimarypackets. 4.1RelaybasedCollaborationModel Relaybasedcollaborationmodelisalsoreferredtoascooperativecognitiveradionetwork.TodesignatransmissionmodelinCCRN,weneedtodenethreecomponents.Therstcomponentofthemodelistoselectthecooperativetransmissionstrategy(i.e.howtocooperate).WeusethetwophasepowerdivisionapproachproposedinHanetal.[47]toschedulecooperativetransmissions(explainedinSection4.2.4).Thesecondcomponentofthedesignistodeterminetheconditionforcooperation(i.e.whentocooperate).Thenalcomponentofthedesignistoselectmatchingcooperationpairsandscheduletheirtransmissionsconsideringmutualinterferencebetweenusers.Throughoutthischapter,wediscussthechallengeswefaceindevelopingeachcomponentofthecooperativetransmissionmodel,andhowweaddresstheseissuesintoourproposedmodelfocusingonuniquefeaturesofreal-timetrafc.574.1.1LimitationsofPriorWork WhiletherehasbeenextensiveresearchinCCRNwherethegoalistooptimizespecicnetworktraitssuchasmaximizingthroughput[70]orminimizingdelay[53]orexploringthetradeoffbe-tweenthem[10],thisresearchisnotapplicabletoreal-timesystemsbecauseofthefollowingreasons.First,existingresearchdoesnotincludepacketdeadlinesintothecooperationmodelandthusignorestheeffectofeachtransmissiondecisiononthesuccessprobabilityofremainingpacketsinthequeue,andfuturepacketsthathavenotyetarrived.Second,thisresearchdoesnotdiscusstheoverheadassociatedwithcooperativetransmission.Forexample,beforeacooperativetransmissiontakesplace,usersneedtoexchangecooperationinformation(e.g.transmissiontime)andselectcooperationpairswhichintroducessignicantoverhead[124].Ignoringthisoverheadmayincreasepacketlossrate.Finally,mostoftheexistingresearchfocusesonasinglecooperat-ingpairofprimaryandsecondaryuserswhichmaynotextendtoamulti-userenvironment.Forexample,allowingasecondaryusertotransmitaspartofcooperationagreementmaychangetheinterferencerelationshipbetweenexistingusers,andifnotproperlyadministered,itmayinterferewithotherongoingtransmissionscausingpacketloss.Furthermore,mostexistingworkassumesinnitequeueswhereasrealsystemshaveonlynitequeues. 4.1.2ProposedApproach Inthischapter,weproposeanewmethodforconstructingreliablereal-timenetworksystemsbaseduponCCRNthatovercomesthelimitationsofpriorwork.Ourapproachistoformulatethemulti-userreal-timecommunicationsystemwithnitequeuesasaMarkovdecisionprocess(MDP)wherewemodeltheimpactoftransmissiondeadlinesandcooperationoverheadintherewardfunctionsoftheMDPandcontrolmutualinterferencebyregulatingtransmissionpower58ofsecondaryusers.Themodeldecidesbetweendirectandrelaybasedcooperativetransmissionandchoosesthetransmissionpowerofsecondaryusersconsideringthetradeoffbetweenthesuc-cessfulreceptionprobabilityofthecurrentpacketandtheimpactofcooperationoverheadonlaterpackets.Forexample,whilecooperativetransmissionmayincreasethesuccessprobabilityofthecurrentpacket,theassociatedoverheadmayreducethesuccessofremainingpacketsinthequeue.Thus,theMDPrewardfunctionsrepresentthedeadlineconstraintsandhelpausermakeeffectivetransmissiondecisions.WefurtherstudyandanalyzetheMDPofasinglepairofprimaryandsecondaryuserstounderstandthedynamicsofcooperation.Basedonthisanalysis,wedevelopadistributedcooper-ationalgorithmforuseinpracticalsettingstohelpusersmakecooperationdecisionsandscheduletheirtransmissions.Weevaluatetheperformanceoftheproposedalgorithmincomparisonwithanexistingcooperationalgorithm[117]. 4.1.3KeyDesignChallenges Tobuildasuccessfulsystem,wemustaddressthreedesignchallenges.(i)cooperationoverheadvs.transmissiondeadlines:Theprocessofrelayselectionandchannelestimationrequiresexchangeofcontrolinformationamonguserswhichcausessignicantoverheadandimpactstheperformanceofcooperativerelaying[124].Thisoverheadissuebecomesevenmorecriticalinthecaseofreal-timesystemsbecauseoftransmissiondead-lines.Therefore,weneedtoquantifytheoverheadofrelayselectionandincorporateitintotransmissiondecisions.Forexample,acooperativetransmissionmayincreasetheproba-bilityofsuccessfuldeliveryofthecurrentpacketatthecostofdecreasingprobabilityofsuccessfuldeliveryofpacketsinthequeue.So,insteadofdecidingtotransmitsolelybased59(a)nointerference(b)interferenceFigure4.1:Impactofsecondaryinterferenceincooperativecommunicationonthecurrentpacket,wemustalsoconsiderqueuedpackets.WedenetherewardfunctionsoftheMDPwhereeachtransmissiondecisionisevaluatedconsideringitsimpactonboththecurrentpacketandqueuedpackets.(ii)cooperationduration:Anotherdesignissueistodeterminetheoptimumcooperationdura-tionforapairofusers.Cooperationdurationreferstotheamountoftimetwousersengageincooperativetransmissionaccordingtotheiragreement.Whereasfrequentcooperationnegotiationmaygivebetterestimatesofchannelsandmoreup-to-datecooperationoppor-tunities,italsoincreasesoverhead.Ontheotherhand,alongercooperationperiodreducestheoverheadbutmayextendcooperativetransmissionlongerthanneeded.Weaddressthisissuebyintroducingalowoverheadprotocolwherethecooperatingusersassesstheirstatusandextendthecooperationperiodifappropriate.(iii)secondaryinterference:Thethirddesignissueistocontroltheinterferencecausedbysec-ondaryusers'transmissions.Forexample,considerthesimplescenariodepictedinFig.4.1wheretwopairsofprimarytransmitterandreceiver(A,A0)and(B,B0)arecommunicat-ingoverchannel1outoftheinterferencerangeofeachother.IftheprimarytransmitterAcooperateswithasecondaryuser(SU)andrelaysitspacketthroughSU,SU'stransmis-60sionoverchannel1mayinterferewithB0.Asuccessfulmodelmustconsidertheimpactofsecondaryinterferencewhileschedulingcooperativetransmission.Weregulatethetrans-missionpowerofsecondaryusersbasedontheinterferencerelationshipbetweenusersandpresentahandshakingprotocoltoensureinterferencefreedatatransmission.4.1.4OurContributions Tosummarize,wemakethefollowingkeycontributionsintheworkinthischapter.WeidentifythechallengesassociatedwithdesigningarelaybasedcollaborationmodelinCCRNforreal-timesystems.WeformulatethetransmissionmodelasanMDP.Weconverttheessenceoftransmissiondeadlinesandcooperationoverheadintorewardfunctions.WedenetheactionsetsofMDPbyimposingpowerconstraintsonsecondarytransmissiontocontrolmutualinterferencebetweenusersinthenetwork.Wepresentanextensiveanalysisofthecollaborationmodelofasinglepairofprimaryandsecondaryusersandcompareitsperformancewithanexistingmodel[117].Theanalysisshowsthatthelattermodelleadstopoorreceptionrateduetoignoringcooperationoverheadandtransmissiondeadlinesintheirformulationwhileourproposedmodelprovideshigherpacketreceptionrateandlowwaitingtime.Theanalysisalsorevealstheimpactofvariousnetworkparametersonsystemperformance.Weproposeadistributedcooperationalgorithmwhereprimaryusersnegotiatewithsec-ondaryusersaboutcooperationdurationandtransmissionpower.Ausermakestransmissiondecisionbasedoncooperationgainthatiscalculatedintermsoftransmissionopportunity,transmissionpower,andqueuesize.Wealsopresentahandshakingprotocolforcooperatinguserstoscheduledatatransmissionavoidingmutualinterference.61Finally,weconsiderdifferentprimaryreal-timetrafcmodelstoevaluatetheperformanceoftheproposedcooperationmodelincomparisontoanexistingcooperativetransmissionmodel[117].Thesimulationresultsshowthattheproposedrelaybasedcollaborationmodelachieveshigherpacketreceptionratethanthepriormodelunderdifferentnetworksettings.Wealsoprovideanoverheadanalysisintermsoffrequencyofcooperationnegotiationandcostbenetanalysisintermsofenergyconsumptioninrelaying.4.2SystemModelandProblemFormulation Inthissection,wedescribenetworksetup,explainthepowerdivisioncooperativetransmissionapproach,andformulatetherelaybasedcollaborationmodel.4.2.1Preliminaries WeconsideraCRNconsistingofasetofmprimarytransmittersP=fp1;:::;pmg,theircorrespondingmprimaryreceiversP0=fp0 1:::p0 mg,andasetofnsecondarytransmittersS=fs1;:::;sng,andtheircorrespondingnsecondaryreceiversS0=fs0 1:::s0 ng.Each(primaryorsecondary)userhasasingletransceiverradioandcannottransmitandreceivesimultaneously.Sincethecooperationdecisionistakenamongthetransmittersonly,weuseprimarytransmitterandprimaryuser,andsecondarytransmitterandsecondaryuserinterchangeably.Weassumethattheprimarynetworkhasanexclusivelicenseofaxedbandwidthspectrum.Eachprimaryuserisassignedafractionofthisbandwidthwhichisreferredtoasa`channel'.Channelsmaybeoverlapping(similarto802.11)orcompletelydisjointbasedontheallocationalgorithm.Sinceourfocusistoanalyzethecooperationmodel,wewillnotdiscussthechannelallocationalgorithm(pleasesee[95]foralistofchannelselectionalgorithms).Secondarytrans-62mitters,ontheotherhand,dependontheprimaryusersfortheirtransmissionopportunitytotheirrespectivesecondarydestinations.Weassumethataprimaryusercontendsforchannelswithotherprimaryusersinthesamenet-work.Letusdenotethataprimaryuserisassignedachannelbythecontrollerwithprobabilityq.Inotherwords,aprimaryusercannottransmitorengageinanytransmissionactivities(cooperativeornon-cooperative)withprobability1qindependentofitsqueuestatus.Finally,weassumeaprimaryusermayeitherchoosetotransmitdirectlyoragreetocooperativetransmission.EachprimaryandsecondarytransmitterhasanitepriorityqueueQ()oflengthLtostorepackets.Eachpackethasadeadlinet;thepacketmustbedeliveredwithinttimeunitsfromthetimeofitsgeneration.Ifthequeueisfull,thenextpacketgeneratedisdropped.Otherwise,thepacketisaddedattheendofthequeue.Usersinthesystemdonotretransmitpackets.Onceapacketistransmitted,itisremovedfromthequeueevenifisnotsuccessfullyreceivedatthedestination. 4.2.2PUTrafcModel VarioustrafcmodelsarestudiedtoaccuratelyrepresentPUactivityincognitiveradionetworks[19][94].Markovmodulatedprocessisthemostcommonmodelamongthem.InSec.4.3,weassumethattheprimarytrafcfollowsaBernoullidistributiontokeepouranalysissimple.How-ever,thisanalysiscanbeextendedtoaMarkovmodulatedprocessasmentionedin[117].LaterinSec.4.5,weuseathreestateMarkovchaintorepresentthePUtrafcmodel[49]andevaluatetheproposedcooperationmodelwithsimulation.WealsoconsiderPoissondistributiontorepresentthePUtrafcmodel[134][80]todemonstratetheperformanceoftheproposedcooperationmodelwithadifferenttrafcmodel.634.2.3ChannelModel WeconsiderthatchannelsexperienceRayleighatfadingwhichimpliesthatthechannelgainre-mainsconstantwithinatimeslotwhereitchangesfromoneslottoanother[104],[33].ChannelgainhiisexpressedasaGaussianrandomvariablewithmean0andvariancediwherediisthenormalizeddistancebetweensenderandreceiverandisthepathlossexponent.Channelexpe-riencesadditivewhiteGaussiannoiseatthereceiverwithmean0andvariance2.SincechannelgainhifollowsaRayleighdistribution,itcanbeshownthati=jhij2followsanexponentialdistributionwithmeand ii.e.i˘exp(d i)[47].4.2.4CooperativeTransmission Forcooperativetransmission,wepreferthepowerdivisionapproachtothetimedivisionap-proach[34,98]becausetheformerapproachprovidesexibilitytocontrolthesecondarytrans-missionpowerandtheprimaryuserdoesnotincuradditionaloverheadforsecondarytransmis-sion.Inthismodel,aprimaryusermayestablisharelaytransmissionpathviaasecondaryuserbyadoptingthepowerdivisiontransmissionapproachproposedin[47]wherecooperativetrans-missionisscheduledintwophases.Intherstphase,aprimaryusertransmitsitspackettoitsdestinationwhichisalsoreceivedbytheparticipatingsecondarytransmitter.Inthesecondphase,thecooperatingsecondarytransmitterregeneratestheprimarysignalandsuperimposesitwithitsowntransmission.Thetransmissionpowerofthesecondarytransmitterisproportionallyallocatedtotheprimarysignalandsecondarysignal,andthecombinedsignalisthentransmittedbythesecondarytransmitter.Theprimaryreceiverdecodesthepacketfromthesetwosignalsreceivedfromdirectandrelayedtransmission.Thejointtransmissiondecisionbetweenaprimarytransmitterpi2Pandasecondarytrans-64mittersj2Scanthusbecharacterizedwith(01),thetransmissionpowerdistributionratio.Primaryuserpirsttransmitsthepackettoitsdestination,anditisalsoreceivedbythesecondaryusersj.ThesecondaryusersjassignstransmissionpowerEtotheprimarysignaland(1)Etothesecondarysignalandtransmitsthecombinedsignal.Additionally,theuserpimayoptfordirecttransmissionwithoutanycooperation,andtheusersjmaytransmitonlywhenthequeueofthepiisempty.Thistransmissiondecisionisrepresentedwith=;.Wemakethefollowingassumptionsregardingthecooperationmodel.First,usersexchangecooperationinformationoveracommoncontrolchannelandcannottransmitwhilenegotiatingcooperationterms.Second,aprimaryusermayparticipateinacooperativetransmissionwithatmostonesecondaryuseratanytime.Theremaybemultiplecooperatingpairsbasedonthenumberofusersandavailabilityofresources(channels).Third,aprimary(orsecondary)useralreadyinvolvedinacooperativetransmissiondoesnotinitiateoracceptanothercooperationrequestuntilthepresentcooperationagreementends(i.e.ongoingtransmissionphasenishes).Forth,allpacketshavethesamelength,anddecodingandregeneratingaprimarypacketatthesecondaryusertakesconstanttime.Finally,theprimarypacketreceivedbyasecondaryuserisimmediatelyrelayedtoitsdestination;therelayedpacketdoesnotexperiencesignicantwaitingtimeinthequeueofthesecondaryuser. 4.2.5PacketLoss Packetlossmayoccurforthefollowingreasons.First,ifaqueueisfull,anincomingpackettothatqueueisdropped.Second,ifthewaitingtimeofapacketexceedsitsdeadline,thepacketisremovedfromthequeue.Finally,ifareceiverfailstodecodeapacketbyitsdeadlineduetointerference,thepacketislostandiscountedasanunsuccessfultransmission.Ourgoalistodevelopacooperativetransmissionmodelthatreducespacketlosses.654.2.6MDPFormulation WemodelthejointtransmissiondecisionoftheprimaryandsecondaryusersasaMarkovDecisionProcess(MDP).InanMDP,eachstateisassociatedwithasetofactionsandcorrespondingrewards.Thus,thecooperationmodelisrepresentedwithanMDP(,A,P:(;),U:(;),)whereisanitesetofstates.Eachstatedenotesthepresentnumberofpacketswaitinginthequeueofalltheusersinthenetwork.Thusastate˙2canberepresentedas˙=(ip 1;:::ip m;js1;:::jsn).Hereip mandjsndenotethenumberofpacketswaitinginthequeueofaprimaryuserpmandasecondaryusersn.Thenumberofdifferentstatesofthesystemisjj=(L+1)m+nwhereLdenotesthequeuesize.Aisasetofallpossibleactionswhereeachactionrepresentsajointtransmissiondecisionofaprimaryandasecondaryuser.Weexpressanactionas(pi;sj)whichdenotesthedis-tributionofpowerallocationbetweenthesignalsoftheprimaryuser(pi)andthesecondaryuser(sj).Sincecanbeanyvaluebetween0and1,thenumberofpossibleactionsisthe-oreticallyinnite.Weuse=;toexpressthedirecttransmissionapproach.TheactionsetcanthusberepresentedasA=f(pi;sj)=;_(pi;sj)2[0;1];pi2P;sj2Sg.Wedroptheindexin(pi;sj)whenwediscussontransmissionpoweringeneral.Attimet,asubsetofactionsa(t)ˆAischosenasthetransmissiondecisionsofprimaryandsecondaryusersinthenetworksuchthatnotwoactionsofthesetinvolvethesameprimaryuserorthesamesecondaryuserorboth.Pa(t)(˙;˙0)=Pr(˙t+1=˙0j˙t=˙;a(t)=f(;)gˆA)denotesthetransitionprobabil-ityfromstate˙tostate˙0iftheactionseta(t)ˆAistakenattimet.66Figure4.2:MatchingpairandactionselectionUa(t)(˙;˙0)denotestherewardoftransferringfromstate˙to˙0duetotheactionseta(t)attimet.Therewardfunctioniscalculatedintermsofimmediaterewarddiscountedbythefutureopportunitycost.Therewardfunctionalsoincludestheimpactofthechangeinthestatusofthequeue.2[0;1]isadiscountfactorthatbalancestheimportanceofimmediaterewardsversuslongtermrewards.Ourgoalistodeterminetheoptimumpolicy'thatmaximizestheexpectedrewardofthecoop-eratingusersoveralongperiodT.Assumingemptyqueuesofallusersastheinitialsystemstate˙0,weexpresstheobjectivefunctionasfollowsmax'limT!11TE'0 @TXt=0tUa(t)(˙;˙0)j˙0=(0;:::;0)1 A:(4.1)wherea(t)representstheactionstakeninstate˙attimetaccordingtothepolicy'andE'()istheexpectationtakenunderpolicy'.Theobjectivefunctioninvestigatestheimpactofdifferentactionsa2Aonallpairsofprimaryandsecondaryusers(PS)todeterminetheoptimalpolicythatrecommendsoptimumactionatdifferentsystemstate(seeFig.4.2).Ifthepairsaremutuallyindependentintermsofthecho-senactionandtheirimpacts,wecanseparatelycalculatetherewardcomponentforallsuchpair67(pi;sj)PS.WeusetheBellmanequationordynamicprogrammingtosolvetheproblemforapairofprimaryandsecondaryuseranddetermineoptimumactionintheirdifferentstates.Werepeatthesameproceduretocalculatetherewardcomponentforallpossiblepairsintheirdifferentstatesfordifferentactions.Finally,wecanuseweightedbipartitematchingtodeterminetheopti-mumactionandoptimummatchingpairsfromthesetatanygiventimetthatmaximizesreward.Tobetterunderstandtheprocedure,weanalyzetheMDPcooperationmodelofasinglepairofprimaryandsecondaryusersinSec.4.3.However,inpractice,anactionofapairofusersaffectstherewardofanotherpairduetomutualinterferenceandtherewarddependencybetweenpairsmakeitintractabletondadeterministicsolutionattimet.Wethereforedevelopadistributedmulti-usercooperationalgorithm(Sec.4.4)addressingthemutualinterferencebetweenuserswithsimultaneoustransmission. 4.3AnalysisofaCooperativeTransmissionModel Tounderstandthedynamicsofsystemparametersonourmultiusercooperationmodel,wersttakeacloserlookatthecooperationmodelforthecaseofasinglepairofprimaryandsecondaryusers.Thesinglepairanalysiswillhelpusidentifytheimpactofdifferentsystemparameters;theseresultswillbeusedtodevelopthedistributedalgorithminSec.4.4.Wedepictthenetworkconsistingofaprimarytransmitterp,aprimarydestinationp0,asec-ondarytransmitters,andasecondarydestinations0inFig.4.3.Wedenotethechannelgainbetweenpandp0,pands,pands0,sandp0,andsands0ash1,h2,h3,h4,andh5respectively.BothusershaveanitequeueoflengthL.WedenotethetransmissionpowerofthecooperatingprimaryuserpandsecondaryusersasEpandEs,respectively.Primaryandsecondarypackets'arrivalfollowaBernoullidistributionwithmeanpandsrespectively.Thesamedistribution68Figure4.3:Cooperationbetweenaprimaryandasecondaryuserisusedtomodelprimaryuseractivityin[12][94].WecanextendthisanalysisfromaBernoullidistributiontoaMarkovmodulatedprocess[117].ThistwouserMDPmodelhasatotal(L+1)2states.Eachstate˙2isrepresentedwith˙=(˙p;˙s)where˙pand˙sdenotethenumberofpacketsinprimaryandsecondaryqueuerespectively,and0˙p;˙sL.Weassumethatsystemparametersremainunchangedwhileausercompletesanaction;changesoccuronlyatstatetransitions.Atthebeginningofeachstate,ausertakesatransmissiondecisionfortherstpacketofthequeue.Auser'sdefaulttransmissiondecisioninthemodelistotakethesingleactionavailableinanon-cooperativesystemi.e.directtransmissionwhereptransmitsdirectlytop0andstransmitstos0onlywhentheprimaryqueueisempty(˙p=0).Thesuccessfuldeliveryoftherstpacketandwaitingtimeofthequeuedpacketsdependsonthedirectdatarate,trafcrate,andchannelavail-ability.Whentheusersinthenetworkintendtoexplorecooperativetransmissionopportunities,theyneedtogothroughanegotiationperiod.Whilethiscooperativetransmissionmayimprovethesuccessfuldeliveryoftherstpacket,thenegotiationperiodcontributestoadditionalwaitingtimetoqueuedpacketsthatmayaffecttheirsuccessfuldeliveryatlatertime.4.3.1ActionSet Thetransmissiondecisionsarerepresentedasactions(p;s)2AinMDP.Sinceweareconsid-eringasinglepairofprimaryandsecondaryusers,tosimplifynotation,wereferto(p;s)as.69Insummary,theactionsareasfollows=;:Thisrepresentsthedefaultnon-cooperativetransmissionapproachwhereptransmitsdirectlytop0andstransmitsonlywhenthequeueofpisempty.Usersexecutethisactionwithnoadditionalcostofcooperationnegotiation.=0:Thisrepresentsthecooperativetransmissiondecisionwherepdefersitstransmissionandletsstransmitwithfulltransmissionpower.Thisactionisprecededbycooperationnegotiation.=1:Thisrepresentsthecooperativetransmissiondecisionwheresrelaystheprimarypacketwithitsfulltransmissionpoweranddoesnotcombines'sowntransmission.Thisactionisalsoprecededbycooperationnegotiation.0<<1:ThisrepresentsthecasewheresallocatesEspowertotheprimarysignaland(1)Espowertoitsownsignal,combinesbothsignals,andthentransmits.Thisactionisalsoprecededbycooperationnegotiation.Atanytimet,pandstakeajointtransmissiondecisiona(t)=,whichmovesthesystemfromastate˙toastate˙0withaprobabilityofPa(t)(˙;˙0)andachievesrewardUa(t)(˙;˙0).Notethat,theoreticallythecooperatinguserscanselectanyvaluebetween0and1fortransmissionpower.However,basedontherelativedistancebetweentransmittersandreceivers,smallchangesintransmissionpowermaynotaffectthesignalstrengthsignicantlyandthusitcanbenarroweddowntoanitenumberofvalues.Foranalysis,weuse=0:65torepresenttheaveragepowerdivisionwithextremevaluesof=0and1.70No.nextstatetransitionprobabilityconditions(1)(i-1,j-1)q(1p)(1s)1i;jL(2)(i-1,j)q(1p)s1i;jL(3)(i,j-1)qp(1s)1i;jL(4)(i+1,j+1)(1q)ps0i;jL1(5)(L,1)(1q)s+qpsi=L;j=0(6)(0,j+1)(1p)si=0Table4.1:Statetransitionprobabilities4.3.2TransitionProbabilityMatrix Thetransitionprobabilitymatrixrepresentsthetransitionprobabilitiesfromonestatetoanotherstatedependingontheactiontakenbytheusers.Duetopagerestrictionsandtoimprovereadabil-ity,weavoidlistingtheentirematrix.Instead,wepresentalistoftransitionprobabilitiesatstate˙(˙p;˙s)whenanaction(0<<1)istakenfollowedbyashortdescription(seeTable4.1)whereqrepresentsthechannelaccessprobabilityofuserp.Thefollowingstatetransitionoccurs(i)whenbothpandsdecidetotransmitcooperativelyandnonewpacketsarriveatthequeueatthattime.(ii)whenbothpandscooperativelytransmitandonlyanewsecondarypacketarrives.(iii)whenbothpandscooperativelytransmitandonlyanewprimarypacketarrives.(iv)whenpdoesnotgetchannelaccessandbothprimaryandsecondarypacketsarrive.(v)whentheprimaryqueueisfullandthesecondaryqueueisemptyandonlyanewsecondarypacketarrives.(vi)whentheprimaryqueueisemptyandonlyanewsecondarypacketarrives.Similarly,wecanliststatetransitionprobabilitiesforallothercases.714.3.3RewardFunction TherewardfunctionUa(t)(˙;˙0)denotesthetotalrewardachievedbythecooperatingprimaryandsecondaryuserforactiona(t)whereweweighttherelativeimportanceofthetwouserswithparameter.Ifsuccessfuldeliveryofprimarypacketsismore(less)preferredtothatofsecondarypacketsinthesystem,thevalueofissethigher(smaller)than0:5.Laterinsimulation,weset=0:5consideringbothrewardcomponentswithequalimportance.Weomittheindex(`p'or`s')fromtherewardcomponentwhenitappliesforbothusers.Ua(t)(˙;˙0)=Upa(t)(˙;˙0)+(1)Usa(t)(˙;˙0)(4.2)ThekeychallengeinmodelingtheMDPistoselectanappropriaterewardfunctionthatac-curatelymeasurestheimpactofthechosenactiononthesystemperformanceintermsofpacketloss.Asmentionedearlier,whileacooperativetransmissiondecisionatastatemayincreasetheprobabilityofsuccessfuldeliveryoftherstpacketofthequeueitalsoaddswaitingtimetolaterpackets.Thismaydecreasethesuccessfuldeliveryoflaterpackets.Likewise,adecisiontode-ferpackettransmissionmayincreasethedroppingprobabilityofanincomingpacket.Therefore,givenapairofprimaryandsecondaryuserandthesystemstate˙,therewardfunctionUa(t)(˙;˙0)shouldanswerthefollowingtwoquestionsHowdoestheactiona(t)atstate˙change(increase/decrease)thedropprobabilityofincomingpacketsduetoqueueoverow?Howdoestheactiona(t)atstate˙change(increase/decrease)thesuccessprobabilityofthepacketswaitinginthequeue?Toanswerthesequestions,weconsideranexampleofapairofaprimaryandasecondaryuser72withqueuelength10.Weconsiderthatthesuccessprobabilityofaprimarypacketwith=;,and=1is0:65,and0:9respectively.Assumethatifthetransmissiondecisionreducesthenumberofwaitingpacketsinthequeueby1,thedropprobabilityofanincomingpacketisreducedby0:2.Anycooperativeactionaddswaitingtimeandreducesthesuccessprobabilityofaprimarypacketwithdirecttransmissionby0:05.Weevaluatetheimpactofdirectandcooperativeactionfromtheperspectiveofaprimaryuserwhenthesystemmovesfromastatewith3waitingpacketstoastatewith2waitingpackets.Thetotalimpactofdirecttransmissioncanthusbequantiedassummationof0:2(changeindroppingprobability)and0:65(successprobabilityoftherstpacket).Letusconsideracooperativeactionwith=1.Inthiscase,theimpactofthecooperativeactionis0:2fromthechangeindroppingprobabilityand0:9fromthesuccessprobabilityoftherstpacket.Furthermore,theremaining2packetsinthequeueexperienceadditionalwaitingtimewhichreducestheprobabilityofsuccessfuldeliveryby0:052=0:1.So,thetotalimpactis0:2+0:90:1=1:0.Thenetrewardofusingaction=1over=;is1:00:85=0:15.Basedontheaboveexample,wedenetherewardfunctionUa(t)(˙;˙0)foreachactionthatincludesitsimpacton1)thepacketattheheadofthequeue,2)theremainingpacketsinthequeue,and3)incomingpacketsnotyetinthequeue.BoththerewardfunctionsUpa(t)(˙;˙0)andUsa(t)(˙;˙0)havethreecomponents(seeEqn.4.3)thataremeasuredincomparisonwithdirecttransmission.Therstcomponentmeasuresthechangeinthedropprobabilityofanincomingpacketbecauseofqueueoverowifactiona(t)isappliedinsteadofdirecttransmission.Thiscomponentdependsonboththechosenactiona(t),currentstate˙,andthenextstate˙0.WedenotethisrewardcomponentasDa(t)(˙;˙0)D;(˙;˙0).Thesecondcomponentmeasurestheprobabilityofsuccessfuldeliveryofthepacketatthe73headofthequeueifactiona(t)isappliedinsteadofdirecttransmission.Thesecondcompo-nentdependsonlyontheactiona(t),andcurrentstate˙.WedenotethesecondcomponentasVa(t)(˙)V;(˙).Thethirdcomponentmeasuresthenetchangeinprobabilityofsuccessfuldeliveryofthequeuedpacketsifactiona(t)isappliedatpresentstate˙insteadofdirecttransmission.WedenotethethirdcomponentasWa(t)(˙)W;(˙).Theusersinthecurrentstatedonotknowwhichactions(exceptthedefaultaction)willbeavailableatfuturestates.Therefore,theimpactofcurrentactiononlaterpacketsisevaluatedonthebasisofdirect(default)transmissiondecision.Forasecondaryuser,thesuccessprobabilityofdefaulttransmissiondecisiondoesnotchangeaslongastheprimaryqueueisnotempty.Therefore,thethirdcomponentdoesnotcontributetotherewardfunctionofasecondaryusers.Insummary,weexpresstherewardofanactionatanygivenstateasthedifferencebetweentheimpactofthatactionanddefaultaction.Upa(t)(˙;˙0)=Dpa(t)(˙;˙0)Dp;(˙;˙0)+Vpa(t)(˙)Vp;(˙)+Wpa(t)(˙)Wp;(˙)(4.3)Usa(t)(˙;˙0)=Dsa(t)(˙;˙0)Ds;(˙;˙0)+Vsa(t)(˙)Vs;(˙)(4.4)4.3.3.1CalculationofDa(t)(˙;˙0)TherstcomponentDa(t)(˙;˙0)denotesthechangeinpacketlossprobabilityduetoqueueover-owbecauseoftheactiona(t)andtransitionfromstate˙tostate˙0.Atransmissiondecisionopensupaslotinthequeueforanewpacket.Therefore,eachtransmissiondecisionreducesthefuturepacket'sdroppingprobabilitybeforeitentersthequeue.However,thisreductioninpacketlossprobabilityisnotsameatallstates.74Thepacketlossprobabilityatstate˙isexpressedasPr(Q(t0)=Lj˙)whichdenotestheprobabilityofaqueuebecomingfullattimet0givenitscurrentstate˙attimet.Assumingservicerateremainssame,thisprobabilityisapproximatedbasedonthepacketarrivalrateasfollowsDpa(t)(˙;˙0)=(p)L˙p(p)L˙0p(4.5)Dsa(t)(˙;˙0)=(s)L˙s(s)L˙0s:(4.6)Here,˙pand˙sdenotethenumberofpacketswaitinginthequeueoftheprimaryandsecondaryuseratstate˙.Asthenumberofpacketsincreasesinthequeue,theprobabilitythatthenextpacketwillbedroppedalsoincreases.Accordingtothisfunction,ifanactionandchangeofstateleadtofewerwaitingpackets,theeventisrewarded.Ontheotherhand,asthequeuebecomesfull,thepenaltyincreases.Forexample,consideraprimaryqueueoflength10andmeantrafcarrivalrateof0:7.Wecalculatetherewardcomponentfortwocases-(1)whentheactionleadstoastatewithonelesspacketswaitinginthequeue,(2)whentheactionleadstoastatewithonemorepacketswaitinginthequeue.Fig.4.4showsthetwocomponentsforprimaryuseronly.Theresultshowsthatreducingthenumberofwaitingpacketsismorehighlyrewardedasthequeuegetsfuller.Similarly,increasingthenumberofwaitingpacketsismorehighlypenalizedwhenthequeueisfuller. 4.3.3.2CalculationofVa(t)(˙)Va(t)(˙)denotestheprobabilityofsuccessfuldeliveryofthepacketattheheadofthequeueusingtheselectedtransmissiondecisiona(t)atstate˙.Consideringtransmissiondeadlineandpacketlengthastandlen,wecalculatetheprobabilityofsuccessfuldeliveryofanyarbitrarypacketintermsofthetransmissionrateRofferedbya(t)andwaitingtime!.So,Pr(!+lenRtj!)7524681000.10.20.30.4number of current packetsDa(t)p(sp,sp - 1) reward component(a)changetoastatewithonelesswaitingpacket02468-0.4-0.3-0.2-0.10number of current packetsDa(t)p(sp,sp + 1) reward component(b)changetoastatewithonemorewaiting packetFigure4.4:Rewardcomponent=Pr(Rlent!j!)=Pr(Rg(!)j!)=(R;g(w)).Here,g(!)=lent!isafunctionofwaitingtimethatalsodenotestheminimumdataraterequiredtodeliverapacketsuccessfully;g(!)dependsonthepresentstateoftheuserandandtheselectedtransmissionapproach.NotethatthetransmissionrateRfollowsadistributioninducedbytherandomchannelgainandthetransmissionapproach.Basedontheaboveequation,weexpresswaitingtime,transmissionrate,andpacketreceptionprobabilityintermsofactiona(t)andthepresentsystemstate˙.Wedenotetheaveragewaitingtimeoftherstpacketofprimaryuserpandsecondaryusersatstate˙as!(˙p)and!(˙s)re-spectively.WealsodenotetransmissionrateofprimaryuserpandsecondaryuserswithRpa(t)andRsa(t)andpacketreceptionprobabilitywith(Rpa(t);g(!(˙p))and(Rsa(t);g(!(˙s))respectively.Vpa(t)(˙)=(Rpa(t);g(!(˙p))=PrRpa(t)g(!(˙p)jw=!(˙p))(4.7)Vsa(t)(˙)=(Rsa(t);g(!(˙s))=PrRsa(t)g(!(˙s)jw=!(˙s))(4.8)764.3.3.3CalculationofWa(t)(˙)Thethirdrewardcomponentisapplicabletoonlytheprimaryuser.Weobservethatacooperativetransmissiondecisionofaprimaryusermayincreasethesuccessfulreceptionprobabilityoftherstpacketatthecostofincreasingwaitingtimeoflaterpackets.Thelongerthecooperationnegotiationperiod,thehighertheimpactonremainingpacketswillbe.Therefore,eachcooperationdecisionmustconsiderhowitaffectsthechanceofsuccessfuldeliveryoflaterpacketsincasethereisnocooperationinthenextstateandpacketsaretransmitteddirectlytothedestination.So,thisthirdcomponentincludesthesuccessprobabilityofremainingpacketswithcooperationoverhead.WecanexpressthenetrewardasfollowsWpa(t)(˙)=˙pXi=1hRp;;g(!(i)+s)i:(4.9)Here,sdenotestheadditionalwaitingtimeimposedonlaterpacketsbecauseoftheactiontakenatpresentstate.Next,wecalculateRpand(Rp;g(!(˙p))fordifferentvaluesofa(t)=.Specically,therearefourcasesweneedtoconsider.=;:TheprimaryusersendsthepacketattherateR1andthesecondaryuseropportunis-ticallysendspacketatrateR5thatarecalculatedasfollows:Rp;=R1=log1+Ep12;Rs;=R5=log1+Es52Forthedirecttransmission,thesuccessfulpacketreceptionprobabilityatrespectivedestina-77tionscanbeexpressedas(Rp;;g(!(˙p)))=expd 12Ep2g(!(˙p))1(4.10)(Rs;;g(!(˙s)))=expd 52Es2g(!(˙s))1:(4.11)=0:Inthiscase,pletsstransmits'spacketwhichimpliesthatRp0=0.ThensappliesitsfulltransmissionpowertosenditspacketatrateR5i.e.Rs0=R5.However,allowingstheexclusivetransmissionopportunityincreaseswaitingtimeofp'spacketsinadditiontothenegotiationtimes.Rp0=0;Rs0=R5=log1+Es52Thesuccessfulpacketreceptionprobabilityofaprimaryandasecondaryuseratstate˙canbeexpressedas(Rp0;g(!(˙p)))=0(4.12)(Rs0;g(!(˙s)))=expd 52Es2g(!(˙s))1:(4.13)=1:Theprimaryuserrelaysthroughsecondaryuserandthesecondaryuserappliesitsfulltransmissionpowertorelaytheprimarysignaltoitsdestination.So,theeffectiveprimarytransmissionrateisminimumofthetransmissionratefromprimarysourcetosecondarysource(p!s)andfromsecondarysourcetoprimarydestination(s!p0).Rp1=12minlog1+Ep22;log1+Ep1+Es4278Wecalculate(Rp1;g(!(˙p)))asfollowsRp1;g(!(˙p))=8 > > > < > > > :expd 22Ep22g(!(˙p)1;if24+1d 1d 1d 4exp(yd 4)d 4d 1d 4exp(yd 1);otherwise:(4.14)Here,y=2Ep(22g(!(˙p)1).0<<1:TheprimaryuserrelaysthroughsecondaryuserandthesecondaryuserappliesEstorelaytheprimarysignaltoitsdestinationandapplies(1)Estotransmititsownsignal.So,theeffectiveprimarytransmissionrateisminimumofthetransmissionratefromprimarysourcetosecondarysource(p!s)andfromsecondarysourcetoprimarydestination(s!p0).Rp=12minlog1+Ep22;log1+Ep12+Es4(1)Es4+2Wecalculate0=(21)(1+Es42)4+(21)Es42whichdecidestheeffectivetransmissionrateoftheprimaryuser.Rp;g(!(˙p))=8 > > > < > > > :expd 22Ep22g(!(˙p))1if0expd 12Ep22g(!(˙p))1otherwise(4.15)Thesuccessfulpacketreceptionprobabilityofasecondaryuserwillbecalculatedasfollows:(Rs;g(!(˙s)))=exp2(1)Esd 522g(!(˙s))1(4.16)794.3.4Comparison Inthissection,weevaluatehoweffectivelytheproposedmodel(referredtoas`rtCoop')representsthereal-timesystemrequirements.Ifamodelcapturesthetruecharacteristicsoftheunderlyingsystem,itsselectedactionshouldleadtotheoptimumsystemperformance,inthiscase,higherpacketreceptionrate.Inthisregard,wealsoconsideranexistingmodelpresentedin[117](referredtoas`prCoop')forcomparison.Inthismodel,rewardfunctionsaredenedbasedonthecostofstoringandrelayingaprimarypacket.Weassumethattherearefourdifferentvaluesof(;,0,1,0:65)tochoosefrom.Accordingly,wesolvetheMDPofeachmodelusinglinearprogramming,runthesimulation,andrecorddifferentstatisticse.g.theaveragewaitingtime,packetreceptionrate.Additionally,weincludethedirecttransmissionapproachintheanalysiswhereptransmitsdirectlytop0andstransmitsonlywhentheprimaryqueueisempty.Werefertothedirecttransmissionas`noCoop'.Toanalyzethesimulationresults,wevarydifferentsystemparameterse.g.distancebetweenusers,queuelength,trafcrate.Foreachdifferentconguration,wecollectseveralstatisticse.g.numberoftimesacooperativeactionispreferredoverdirecttransmission,averagewaitingtime!pexperiencedbyp,andcumulativepacketreceptionrateandcomparetheresults.First,wextheprimaryandsecondarytrafcratefollowingaBernoullidistribution,channelaccessprobability(q=0:8),queuesize(L=5).Wevarythedistancebetweenpandsandp0ands0whicharedenotedasd2andd4respectively.Allthedistancesarenormalizedto1.Wemovethesecondaryuseralongthelinebetweentheprimarytransmitterandthedestinationi.e.wesetd2=1d4whilekeepingthedistancebetweenthesecondarytransmitterandthesecondarydestinationxedto0:3.Fig.4.5aand4.6ashowthatrtCoopachieveshighercumulativepacketreceptionrateandloweraverageprimarywaitingtimecomparedtoprCoop.800.30.40.50.60.7lineardistance(d)60708090100PRR (%)noCooprtCoopprCoop(a)Varyingd2=1d40.511.5distance60708090100PRR (%)noCooprtCoopprCoop(b)Varyingd2=d444.555.56qLen60708090100PRR (%)noCooprtCoopprCoop(c)Varyingqueueinglength0.20.40.60.8purate6p5060708090100PRR (%)noCooprtCoopprCoop(d)VaryingpFigure4.5:Comparisonbetweencooperationmodels(packetreceptionrate)810.30.40.50.60.7lineardistance(d)00.20.40.60.8wpunoCooprtCoopprCoop(a)Varyingd2=1d40.511.5distance00.20.40.60.8wpunoCooprtCoopprCoop(b)Varyingd2=d444.555.56qLen00.20.40.60.8wpunoCooprtCoopprCoop(c)Varyingqueueinglength0.20.40.60.8purate6p00.20.40.60.8wpunoCooprtCoopprCoop(d)VaryingpFigure4.6:Comparisonbetweencooperationmodels(averagepuwaitingtime)82Next,weputthesecondaryuserawayfromthelinebetweentheprimarytransmitterandthedestinationandwesetd2=d4andd5=d22.Wealsovarythequeuelength,primarytrafcrate,andsecondarytrafcratewhilekeepingallotherparametersxed.Foreachofthesedifferentcongurations,weplotthepacketreceptionrateandaveragewaitingtimeofaprimarypacketinFig.4.5.TheresultsshowthattheproposedcooperationmodelrtCoopimprovesthepacketrecep-tionratecomparedtoprCoopandnoCoop.WealsorecordtheaveragewaitingtimeencounteredbyprimaryusersandshowtheresultsinFig.4.6.Ingeneral,itshowsthatprCoopincurshigherwaitingtimecomparedtoourproposedmodel.Thisisbecausetheformerapproachdoesnottakeintoconsiderationthecommunicationoverheadassociatedwithcooperationthatleadstowrongtransmissiondecisionandlowpacketreceptionrate. 4.4Multi-userCooperativeTransmissionModel Thecooperationmodelinmulti-usersettingaddssomeuniquechallengestothesingleusermodel.First,inthesingleuseranalysis,weassumethatchangesoccuratdiscretetimeintervalsandsystemparametersdonotchangeinastate.However,inreality,theinteractionbetweenprimaryandsecondaryusersisasynchronous.Packetsarriveasynchronouslyattheuserandtransmissiontimesmaydifferfromusertouser.Therefore,statetransitionmayoccuratdifferentintervals.Second,weneedtoconsidertheinterferencebetweenprimaryandsecondarytransmissionswhichwasabsentinthesingleuseranalysis.Furthermore,auserhasnoknowledgeofotherusers'trafcandqueuestatus,andhastodecidesolelybasedonitsstateparametersandcooperationoffersreceivedfromitsneighbors.Addressingtheseaboveissues,wepresentadistributedcooperativetransmissionmodelformakingcooperationoffers,negotiatingtermsofcooperation,selectingatransmissionapproach,andnallyschedulingpackettransmission.Weexplainthesestepsofthe83algorithmnext. 4.4.1Step1:Pre-screening Inthisstep,asecondaryuserconstructsaninterferencemapwhichhelpsittoidentifypotentialprimaryusersthatitcanengageincooperativetransmissions.Weassumethateachsecondaryuserisawareoftheinterferenceconstraintoftheprimarynetworkandknowsthechannelgainbetweenitselfandeveryprimaryreceiverinthenetwork.Asecondaryusermayestimatethechannelqualityandlinkratefromoverhearingthemessageexchangebetweenprimarytransmittersandreceiversandbyapplyingstandardtrainingsequencemethods[43]orbyanalyzingthereceivedpatterns[82].Thus,asecondaryuserdeterminesthemaximumtransmissionpoweritcanuseforeachprimaryuserandbuildstheinterferencemap.LetV(sj)denotethesetofprimaryuserswithintransmissionrangeofsj.TheinterferencemaphasjV(sjjentriesandeachentryrepresentsthemaximumtransmissionpowermax(pi;sj),sjcanuseinrelayingwhilecooperatingwithpi2V(sj).sjcalculatesitsinterferencecontributiontootherongoingtransmissionwhilecooperatingwithpiandndsthemaximumvalueitcanusewithoutinterferinganyofthesetransmissions.Forexample,tocalculatemax(pi;sj)wecalculatemax(pi;sjjpk),themaximumtransmissionpowersjcanuserelayingpi'strafcwithoutinter-feringwithpk'stransmission.Finally,themaximumpowermax(pi;sj)issettotheminimumofthesemaximumvalues.max(pi;sj)=min8k2Pmax(pi;sjjpk)(4.17)Ontheotherhand,aprimaryuserbydefaultoperatesindirecttransmissionmode.Aprimaryusercontinuouslymonitorsitsqueuesizeandpacketlossrate,andifthechangeinpacketloss84exceedsbeyondathresholdp,ittunestocontrolchannel,looksforcooperationopportunity,andentersintothenegotiationstep. 4.4.2Step2:Negotiation Atthisstep,theinteresteduserstunetothecommoncontrolchannelforsubmittingoracceptingitscooperationoffer.Aprimaryuser'sgoalistondasecondaryuserwhoserelayingwillreducepacketloss.Asecondaryuser'sgoalistoensuretransmissionopportunitywhilespendinglesspowerinrelayingandavoidinginterferencetoothers'transmission.Accordingly,asecondaryuserconsultsitsinterferencemap,initiatesthecooperationprocess,andsendsanoffertooneormoreprimaryusersfromthelist.Acooperationofferfromasecondaryuserincludesthevalueof,anditstransmissionduration.Tostartwith,sjstartswithanofferofthehighesttransmissionpowermax(pi;sj)itcanprovidetopi.Thisinitialofferhelpssjinassessingitsfuturecooperativetransmissionopportunities.ThesubsequentoffersaremodiedusingEqn.4.18.Ifitsofferisaccepted,thevalueoft(pi;sj)ischangedattherateofthechangeinqueue.Ontheotherhand,thevalueoft1(pi;sj)isdoubledinthenextoffer.Here,dQdtdenotesthechangeinthenumberofwaitingpacketswithtime.t(pi;sj)=8 > > > < > > > :mint1(pi;sj)1+dQdt;max(pi;sj)ifsuccessfult1(pi;sj)2otherwise:(4.18)Aprimaryuserwillingtocooperatelooksintothecooperationoffersithasreceived.Foreachsuchpotentialoffer,aprimaryusercalculatesitscooperationgainconsideringitsimpactoncurrentandlaterperiodsincomparisonwithdirecttransmission.So,aprimaryuserpireceivesofferfromitsneighboringsecondaryusersjintheformoftransmissionpowert(pi;sj)andtransmission85Figure4.7:CooperationlifecycleofauserFigure4.8:Handshakingprotocoltimeytj.Foreachofferfromsj,piestimatescooperativechannelgain,calculatestheexpectedrelaytransmissiontimeandcooperationgainGj(i),andcomparesitwithdirecttransmissionap-proach.Bothimmediategainandfutureopportunitiesareconsideredingaincalculationandareweighedbythestateofthequeue.Giventheremainingtimetotransmitapacket(rti),estimateddirecttransmissiontime(dti),andestimatedofferedtransmissiontime(xtj)andtherequestedtransmissiontime(ytj),picalculatesthecooperationgainGj(i)ofacooperationofferfromsjasfollows: Gj(i)=c1(dtirti)max(rti;dti)+c2(rtixtj)max(rti;xtj)+c3(dtixtj)max(dti;xtj)1QiL+1ytjxtjQiL(4.19)Here,c1,c2,andc3areconstantsthatdenotetherelativeweightfactorofthesesubcomponentswherec1+c2+c3=1.Qidenotesthenumberofpacketswaitinginthequeueofpi.piselectsthesecondaryuserwiththehighestgainforcooperation.Otherwise,itdecidestotransmitdirectly.Inthenalstep,asecondaryusersjreceivesconrmationfromoneormoreprimaryusers.Ifthereismorethanonereply,sjpickstheonethatincreasesitscooperationgaini.e.achieveshigherenergyefciencyandlesspowerconsumptioninrelaying.sjsendsaconrmationmessage86totheselectedprimaryuser,andbothusersstartagreetocooperativetransmission.Sinceprimaryusersoperateasynchronously,ausermayreceivecooperationoffersfromotheruserswhileitisindatatransmissionmode.However,alltheseoffersduringtransmissionmodeareignored.Fig.4.7showsthedifferentphasesofthecooperationlifecycleofatypicaluser.Eachusergoesthroughthisabovenegotiationproceduretomaketransmissiondecisions.4.4.3Step3:DataTransmission AprimaryuserincooperationagreementwithasecondaryuserfollowsamodiedRTS/CTShandshakingprotocolbeforedatatransmission.InthetraditionalRTS/CTShandshakingprotocol,thesourceandthedestinationsendssmallcontrolpackettoannouncetheirnextdatatransmission.Anyuseroverhearingeitherofthesepacketsbacksoffthetransmissionperiodandtriesagain.Incooperativerelayedtransmission,anadditionaluserinvolvesindatatransmission.Specif-ically,thesecondaryuserreceivesapacketfromtheprimaryuserandthenrelaysthepackettothedestination.Withthetraditionalhandshakingprotocol,asuccessfulpacketdeliveryinvolvesatleasttwohandshakingperiods-therstonefromprimarytransmittertosecondaryuser,andthesecondonefromsecondaryusertoprimaryreceiver.Theprimarypacketneedstobestoredinthesecondaryqueue.Intheproposedhandshakingprotocol,weintroduceanadditionalcontrolpacketRTR(readytorelay)whichwillbesentbythecooperatingsecondaryuser.Thisensuresaprimarypacketspentminimumtimeinasecondaryqueue,andreducestheoverheadofhandshaking.Ac-cordingly,whentwocooperatingusersarereadytotransmit,aprimaryusersendsaRTSpacketincludingthenameofthesecondaryuseritiscooperatingwith.ThecooperatingsecondaryuserthensendsaRTRpacketdenotingtheaddressofboththesenderandreceiver.Finally,theprimaryreceiversendsaCTSpacketwithcooperationduration.Ifeachcooperatinguserinvolvedintheco-operationagreementreceivestheothertwocontrolpackets,itassumesthatthechannelissecured87anddatatransmissionstarts.Anyotheruseroutsidethiscooperationagreementbacksofftheentiredurationwhenitreceivesanyofthosecontrolpackets.Fig.4.8demonstratesahandshakingeventbetweenacooperatingprimaryandsecondaryuser. 4.4.4Step4:CooperationRenewal Thenalstepofthecycleistodeterminethecooperationduration.Ifthedurationissmall,usershavetofrequentlygothroughnegotiationperiods;theoverheadassociatedwithitmayoutweighthecooperationbenets.Ontheotherhand,whilelongerintervalsreducethecommunicationoverhead,usersmaymisscooperationopportunitieswhichhurtthesystemreliability.So,itisimportantforausertobeabletoadaptthecooperationdurationwithchanginguserandnetworkconditions.Withthisinmind,theproposedmodelallowsacooperatingusertocontinuecooperativetrans-missionwithoutgoingthroughnegotiationperiod.Aprimaryuserkeepsrecordoftherateofchangeinqueuestatusandthechangeinpacketreceptionrate.Ifthisratiodropsbelowathreshold(p),itterminatesthecurrentcooperationperiodandswitchestodirecttransmission.Otherwise,itcontinuestosenditspackettothecooperatingsecondaryuserwithoutadditionalmessageex-change.Similarly,asecondaryuseralsokeepsrecordoftherateofchangeinitsqueuestatusandcooperationgainintermsofenergyconsumption.Iftheratiodropsbelowathreshold(s),thesecondaryuserdoesnotparticipateinhandshaking.Thiswaycommunicationoverheadisreducedwithoutsacricingsignicantcooperationbenets.Thetradeoffiscontrolledbyadjustingtheparameterspands.884.5PerformanceEvaluation Inthissection,weevaluatetheperformanceoftheproposedcooperationmodelinacognitiveradionetworktosupportreal-timetrafc. 4.5.1PerformanceMetrics Weusethreemetricstoanalyzetheperformanceofthemodel.Theyareasfollows:packetreceptionrate:Ourprimaryevaluationmetricispacketreceptionrateofthenetwork.Wedene`weightedpacketreceptionrate'or`weightedPRR',PRRasweightedsumofprimaryandsecondarypacketreceptionrate.So,PRR=Pm i=1PRRi+(1)Pn j=1PRRj.Here,PRRiandPRRjdenotethepacketreceptionrateofprimaryuserpiandsecondaryusersj.Throughoutoursimulation,weuse=0:5i.e.weconsiderequalprioritytoprimaryandsecondarypackets.cooperationoverheadanalysis:Weintroduceanothermetricthatdeterminestheoverheadcausedfromexchangingmessageduringnegotiationprocedure.Wedene`puoverhead'asthenumberoftimesaprimaryuserengagesincooperationnegotiation(whetheritissuccessfulornot)duringitslifetime.costbenetanalysis:Weperformacostbenetanalysisforsecondaryusersintermsofpowerconsumptioninrelayingprimarytrafc.Wedene`sucostperpacket'asaratioofthetotalpowerspentinrelayedtransmissionandnumberofitspacketsithastransmitted.894.5.2SimulationSetup Weconsidera150m150msimulationareawheresecondaryusersarerandomlyplacedintheareabetweenprimarysourcesanddestinations.Numberof(primaryandsecondary)usersarevariedbetween1and5.Foreachsetofprimaryandsecondaryusers,wecreate20randomtopologiesandforeachtopology,werunthesimulationoneachtopology20times;eachcaseissimulatedfor1000ms.Ineachtopology,itwasmadesurethateachprimary(secondary)userhasatleastonesecondary(primary)userwithinitstransmissionrange.Allresultsaresummarizedoverthesetopologiesandpresentedwith95%condenceinterval.Eachprimaryuserisassignedachannelofbandwidth20KHz.The(maximum)primaryandsecondarytransmissionpower,Ep=Es=E=100mWandthenoise,N0issetto10e10mW/Hz.Pathlossissetto4andthesizeofthepacket,lenissetto1Kb.Weuseadditiveinterferencemodel[59]tocalculatemutualinterferencebetweenongoingtransmissions.Wecomparetheperformanceoftheproposedmodelintwodifferentusersettingswithtwodifferentprimarytrafcmodel.Intherstsetting,weconsiderasinglepairofprimaryandsec-ondaryuserswhereprimarytrafcfollowsaPoissondistribution.Inthesecondsetting,wecon-sideramulti-usersettingwherenumberofchannelsarelessthantheactiveprimaryusersandtwoprimaryusersmayusethesamechannel. 4.5.3SingleUserSetting Weselectthepowerdivisionapproachproposedin[47]tocomparetheperformanceofourpro-posedcooperationmodel.Werefertotheproposedcooperationmodelas`rtCoop'andthebasicpowerdivisionapproachin[47]as`prCoop0'.Inthisapproach[47],thepowerdistributionisoptimizedtoreducetheoutageprobabilityoftheprimarysystems.Thisapproachdoesnottake900.811.21.4pu rate00.20.40.60.8weighted PRRrtCoop (lbound)rtCoop (ubound)prCoop0 (lbound)prCoop0 (ubound)(a)weightedPRR0.811.21.4pu rate0.30.40.50.60.70.80.9pu PRRrtCoop (lbound)rtCoop (ubound)prCoop0 (lbound)prCoop0 (ubound)(b)pupacketreceptionrate0.811.21.4pu rate00.20.40.60.8su PRRrtCoop (lbound)rtCoop (ubound)prCoop0 (lbound)prCoop0 (ubound)(c)supacketreceptionrateFigure4.9:Comparisonbetweenmodelsofasinglepairofprimaryandsecondaryusersintoconsiderationtheuser'squeuestatusandfutureopportunities.Thenetworktopologyandsimulationprocedureremainssame.WeconsiderthattheprimarytrafcfollowsaPoissondistribution.Wevarythemeanprimarytrafcratefrom0:75and1:5,andrecordthepacketreceptionrateforeachcases.TheresultisshowninFig.4.9wheretheproposedmodeloutperformsthebasicmodel[47].Thisisbecauseinourproposedapproach,asecondaryuserhasequalrightstoselectcooperationparametersandtakesitsdecisionfromtheperspectiveofreal-timetrafc.4.5.4Multi-usersetting Tocomparetheperformanceoftheproposedmodelinamulti-usersetting,weconsiderthecoop-erationmodelproposedin[117].Inthismodel,asecondaryuserconsidersthecostofstoringapacketinqueueandspendingpowerinrelayingandsendscooperationofferaccordingly.Apri-maryuserselectsthesecondaryuserthatoffersthehighesttransmissionpower.Uponnegotiation,RTS/CTShandshakingprotocolisusedfordatatransmission.Weconsidertwotrafcmodelstoevaluatetheperformanceoftheproposedmodel.TherstoneisaMarkovmodulatedprocesspresentedin[49]whichhasthreeinternalstatesandtrafcgenerationratevariesbetweenstates.ThesecondtrafcmodelweconsiderhereisaPoissondistribution.Inbothcases,secondary915060708090100Deadline00.20.40.60.8weighted PRRrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(a)weightedPRR5060708090100Deadline1520253035pu overheadrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(b)puoverhead5060708090100Deadline050010001500200025003000su costrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(c)sucostFigure4.10:Markovthreestatetrafcmodelwithvaryingtransmissiondeadline1015202530Queue length00.20.40.60.8weighted PRRrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(a)weightedPRR1015202530Queue length20253035pu overheadrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(b)puoverhead1015202530Queue length05001000150020002500su costrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(c)sucostFigure4.11:Markovthreestatetrafcmodelwithvaryingqueuelengthuser'strafcfollowsaPoissondistribution.Foreachtrafcmodel,werunsimulationwithvaryingtransmissiondeadlineandqueuelengthandanalyzetheperformanceoftheproposedmodel.First,wevarythetransmissiondeadlinewithMarkovthreestatetrafcmodelandplottheresultsinFig.4.10.ThesimulationresultshowsthatrtCoopachieveshigherpacketreceptionratethanprCoop.However,bothapproachesexhibithighpuoverheadbecauseoftherateofchangeinqueuesizeisnotconsistentwhichmakesthecooperationdurationsmallandtriggersfrequentcooperationnegotiation.However,secondaryusersspendlesspowerinrtCoopcomparedtoprCoop.Next,wevarythequeuelengthandplottheperformancemetricsinFig.4.11whichshowssimilartrendaswithvaryingtransmissiondeadline.Next,weconsiderthatprimarytrafcfollowsaPoissondistribution.Themeanvalueoftrafc9220406080100Deadline0.30.40.50.60.7weighted PRRrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(a)weightedPRR20406080100Deadline050100150pu overheadrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(b)puoverhead20406080100Deadline5001000150020002500su costrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(c)sucostFigure4.12:Poissontrafcmodelwithvaryingdeadline1015202530Queue length0.50.520.540.560.580.6weighted PRRrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(a)weightedPRR1015202530Queue length05101520pu overheadrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(b)puoverhead1015202530Queue length5001000150020002500su costrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(c)sucostFigure4.13:Poissontrafcmodelwithvaryingqueuelengthisvariedissetto0:05.AgainwevarythetransmissiondeadlineandplotthreemetricsinFig.4.12.Asdeadlineincreases,thepacketreceptionrateincreases,however,rtCoopensureshigherpacketreceptionrateinallcases.TheproposedmodelalsoachieveslowprimaryoverheadandlesssecondarycostperpacketcomparedtoprCoop.WealsovarythequeuelengthandtheresultsareshowninFig.4.13.Again,theproposedmodeloutperformsprCoop.Next,wevarythemeanvalueofPoissondistributionwhilekeepingeveryotherparameterxed.TheresultsareshowninFig.4.14.Theresultsshowthattheproposedmodelachieveshigherpacketreceptionratewhileensuringlowprimaryoverheadandlowenergyperbitforasecondaryuser.Finally,wevarythenumberofsecondaryusersfrom5to15whilekeepingthenumberofprimaryusersxedto5toanalyzetheimpactofcooperationoverheadonthesystemperformance.930.020.040.060.080.1pu rate (Poisson)0.20.40.6weighted PRRrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(a)weightedPRR0.020.040.060.080.1pu rate (Poisson)0102030405060pu overheadrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(b)puoverhead0.020.040.060.080.1pu rate (Poisson)05001000150020002500su costrtCoop (lbound)rtCoop (ubound)prCoop (lbound)prCoop (ubound)(c)sucostFigure4.14:PoissontrafcmodelwithvaryingpurateThesimulationresultshowsthatthecooperationoverheadintheproposedalgorithmincreasesveryslowlycomparedtotheexistingmodels.Thisisbecauseasecondaryuserintheproposedalgorithmgoesthrougharenewalstepwithalmostnooverheadinsteadoffrequentnegotiationintheexistingalgorithms. 4.6Summary Inthischapter,wedevelopaninterferenceawarecooperativecognitiveradionetworkforreal-timeapplications.WeformulatethecooperationoptimizationproblemintoanMDPanddeneitsstates,actionsets,transitionmatrix,andrewardfunctionsreectingthetradeoffbetweencoop-erationoverheadandcooperationbenets.Wedenetherewardofaprimaryuserintermsofsuccessfulpacketreceptionprobabilitysubtractedbythecostofcooperationoverhead.Likewise,wedenetherewardofasecondaryuserintermsofsuccessfulpacketreceptionprobabilitywithrespecttotransmissionpowerappliedtorelayedtransmission.Ouranalysisofasinglepairofpri-maryandsecondaryuserspointsoutthefactthatthereisaneffectivecooperationregionintermsofthedistanceamongusers.Inamulti-usercooperationmodel,wedene`cooperationgain'thatrepresentsbenetsofcooperationandselectspairsfortransmissionfollowinganegotiationproce-94dure.ThecooperatingpairsuseamodiedRTS/CTShandshakingprotocolfordatatransmission.Weperformextensivesimulationsunderdifferentnetworksettingswithvaryingdifferentnetworkparametersandcomparetheresultswithanexistingmodel.Theresultshowsthatcooperativetransmissionensureshigherpacketreceptionratethanthepriorcooperationmodel.Weperformacostbenetanalysisthatrepresentsthesecondaryuser'scostintermsofenergyconsumptioninrelayingprimarypacket.Wealsoperformanoverheadanalysiswhichdemonstratestheeffectofcooperationnegotiationonprimaryusers.Theproposedmodelensureslowcontroloverheadandlowenergycostforcooperatingprimaryandsecondaryusersrespectively.95Chapter5 CooperativeRoutinginCognitiveRadio Networks AsdiscussedinChapter4,relaybasedcollaborationmodelbringsapowerfulmeanstocombatchannelfading,toachieveimprovednetworkcapacity,andtoprovideefcientspectrumsharingamongprimaryandsecondaryusers.Byexploitingcooperativediversity,aprimaryuser(PU)appointsasecondaryusertorelayitspackets,andimprovesitsthroughput,andasecondaryuser(SU)increaseschannelaccessopportunitiesinreturnforitsservices.Thesuccessinsinglehoprelaymodelmotivatestheresearcherstostudyandexplorethecollaborationmodelinmulti-hopcooperativecommunication.Inthischapter1,westudyandanalyzethemulti-hopcooperativerelayselectionandschedulingproblem.Inamulti-hopcooperationmodel,aprimaryuserintendstoestablishastableroutingpathtoitsdestinationbyselectingmultiplesecondaryusersasintermediaterelays.Asecondaryuser,ontheotherhand,participatesinoneormoreroutingpathstoensureitstransmissionopportunitieswhilelimitingpowerconsumptioninrelaying.Exploitingtimeandspacediversityovermultiplehops,thismodelcanofferaninnovativesolutionforrelayingthegrowing3G=4Gcellulartrafc[128].Theemergingtechnologyofcognitivesensornetworkswithlimitedtransmissionrangeand1Theworkpresentedinthischapterhasbeenpublishedinthefollowingresearcharticle:(i)ChowdhurySayeedHyder,andLiXiao.flCooperativeRoutingviaOverlappingCoalitionFormationGameinCognitiveRadioNetworksfl,inthe10thWorkshoponWirelessMeshandAd-hocNetworking(WiMAN),Waikoloa,Hawaii,USA,Aug4,2016.96longerlifetimeexpectationalsoadvocatesanefcientmechanismforrelayingtrafc[79].Finally,networkmodelrelyingonspectrumsensingtechniquesmaynotprovidesatisfactoryresultsduetoimperfectsensing.Ontheotherhand,cooperationamongprimaryandsecondaryuserseliminatestheunintentionalcollisionwithPUtransmission[127].Althoughmulti-hopcooperativerelayingbringssignicantpromises,weneedtoaddresssev-eraluniquechallengestodesignthecooperationmodelandexploititsfullbenets.Themainchallengeistoquantifythemutualinterestofprimaryandsecondaryusersintopayoffandincor-porateitincooperationdecisionmaking.Forexample,whileasecondaryuserasanintermediaterelaymayofferhigherdatarate,italsointroducesdelayinthesameroutingpath.Therefore,aprimaryuser'spayoffmustreectthetradeoffbetweenachievablethroughputandpathdelay.Ontheotherhand,unlikesinglehoprelaymodel,asecondaryuser'scooperationbenetisdenednotonlybyitsownactionbutalsobytheactionofotherusersintheroutingpath.Therefore,wemusttakeintoconsiderationthecompetitionamongthesecondaryuserstomeettheirrequirements.Asaresult,singlehoprelaybasedresearch([64,67,76,131,136])arenotextensibletomulti-hopscenarios.Inthisregard,fewwork[79,127]addressthemulti-hopcooperativerelayselectionproblemanddesignacooperationmodelfocusingonprimaryusers'interestonly.Forexample,Xueetal.[127]presentaschedulingalgorithmforasingleprimarytransceiverpairwhoseroutingpathconsistsofxedandpredeterminedsecondaryrelaynodes.However,thecompetitionamongmul-tipleprimarysource-destinationpairsisnotaddressedandtheconsiderationofxedroutingpathmakethecooperationmodelimpractical.AlthoughLietal.[79]haveconsideredmultipleprimaryusersintheirwork,themodelbecomesunstablewhenusershavetodealsimultaneousrequests.Furthermore,asecondaryuseractsonlyinresponsetoprimaryusers'specicrequests,andeachonemaycooperatewithatmostoneprimaryuser.Thislimitationpreventsasecondaryuserfrom97exploringitscooperativetransmissionopportunity.Finally,weneedtoensurethestabilityoftheroutingpathandthescalabilityandcomplexityofthecooperationalgorithm.Anunscalablealgo-rithmcausesunstableroutingpaththatleadstocollisionandpacketloss,andthenetworkoutputdegradessignicantly.Therefore,theseproposedframeworkdonotrepresentthetruepotentialofamulti-hopcooperationframework.Inthischapter,weanalyzethemulti-hopcooperationframeworkandpresentmcRoute,amulti-hopcooperation-basedrelayselectionandtransmissionschedulingalgorithmaddressingtheissuesdiscussedabove.Weconsidercoexistingprimaryandsecondaryusersandanalyzeamulti-hopcooperationframeworkbasedonusers'mutualinterests.Inthisframework,weconsiderbothprimaryandsecondaryusersas`active'participantswhichactivelyadoptstrategiestodecidewhenandhowtoacceptcooperationfromotherusersforimprovedsystemperformance.Thiscomplexinteractionandnegotiationprocessisanalyzedusinganoverlappingcoalitionformationgame.Theresultfromthisanalysisisthenusedtodeviseacooperationbasedroutingalgorithmthathandlessi-multaneousroutediscoveryrequestsandensuresstableroutingpathsthroughcoalitionformation.Therefore,ournetworkmodelismoregeneralthanothersandexploitsthefullbenetsofmutualcooperation.Thesalientcontributionsofourworkaresummarizedasfollows.Weformulatethemulti-hoprelayselectionandschedulingproblemasanoverlappingcoali-tionformation(OCF)game.Unlikeexistingapproaches,thismodelinvolvesactivepar-ticipationfrombothprimaryandsecondaryuserswhereonesecondaryusercanjoinmorethanonecoalition.Theuserpayofffunctionsinthegamearedenedreectingtheirmutualinterestoncooperation.WeproposemcRoute,acooperationbasedroutingalgorithmbasedonthepropertiesofthe98Figure5.1:NetworkmodelOCFgame.Eachprimarytransmitterinitiatesaroutediscoveryrequest.Whenasecondaryuserreceivessuchrequests,itcoordinatesbetweenmultiplerequestsandcarefullysetsitscooperationparameterstoshowitsinteresttojoinincoalitions.Afterexchangingmessagesbetweenusers,theroutingpathsareguaranteedtoconvergeandpacketsarescheduledfortransmissionintimedomain.Finally,wedeveloptheproposedjointroutingandschedulingalgorithmandcompareoural-gorithmwithanexistingwork[79]andshowthatouralgorithmperformsbetterthanexistingone.Wealsoanalyzeourproposedalgorithmintermsofvariousperformancemetrics.5.1SystemModelandProblemFormalization 5.1.1SystemModel WeconsideranOFDMA-basednetworkconsistingofmindependentsource-destinationpairsofprimaryusers(Fig.5.1).ThesetofprimarytransmittersisrepresentedasP=fp1;:::pmgwhilethesetofcorrespondingreceiversisrepresentedasP0=fp0 1;:::p0 mg.WeassumethecoexistenceofanadhocsecondarynetworkwithnsecondarytransmittersinsetS=fs1;:::;sngandtheircorrespondingreceiversinsetS0=fs0 1;:::;s0 ng.Eachuser(primaryandsecondary)isequipped99withtworadiosŒoneisdedicatedfordatatransmissionandtheotheroneisforexchangeofcontrolmessage.Tomakethebestuseofthebandwidthsavailabletotheprimarynetwork,theorthogonalsub-carrierscanbedividedintodatachannelsandcontrolchannels[73][140].Sinceourgoalistoaddressthemulti-hoprelayselectionandroutingpathformationviacooperation,thischannelallocationtechniqueamongtheprimaryuserswillnotbediscussed.Forsimplicity,weassumethateachprimarytransmitterpi2Pisallocatedasubsetofsub-carriers,andtogethertheyarereferredtoas`sub-channel'fordatatransmission[79].Weconsiderthateachsub-channelconsistsofanequalnumberofsub-carriers,therebyachievingequalbandwidth2,B.Eachsecondaryusersi2Scanoperateoveranyofthesub-channelsoftheseprimaryusersbasedontheircooperationagreement.Acommoncontrolchannelisalsoestablishedforexchangingcontrolmessageintimedomainamongtheusers.Weassumethatusersengageincooperativetransmissionandsharetheirresourcesintimedomain[64,67,79]ifitincreasestheirprot.Aprimaryuserisinterestedinexploitingthecoop-erationdiversitytobuildaroutingpaththatprovidesimprovednetworkperformance.Similarly,asecondaryuser'sinterestistoensureenoughtransmissiontimetomeetitsraterequirementwhilespendingaslesspowerinrelayingprimarypacketsaspossible.Thismutualinterestinachievinghigherpayoffdrivestheuserstonegotiatecooperationterms,shareresourcesintimedomain,andbuildsamulti-hopcooperationmodel.Ourgoalhereistodeterminethetermsofcooperationanddesignamulti-hoptransmissionmodelthatmaximizesusers'payoff.Toachievethisgoal,werstformulatetherelayselectionproblemasanoverlappingcoalitionformationgame.Westartwithabriefdescriptiononoverlap-pingcoalitionformationgamefollowedbystepbystepproblemformalization.2Themodelcanbeextendedtouserswithvariablebandwidth.1005.1.2Preliminaries Overlappingcoalitionformationgameisaspecialtypeofcooperativegamewhereplayerscanparticipateinseveralcoalitions.Thistheoryhasbeenusedtomodelcollaborativespectrumsensingincognitiveradionetworks[119],interferencemanagementinsmallcellnetworks[139],andsoon.InthecontextofrelayselectioninCCRN,weadopttheoverlappingcoalitionformationgametomodelandanalyzethebehavioroftheframework.Wepresentthepropertiesoftheoverlappingcoalitionformationgameinthefollowingdenitions.Figure5.2:OverlappingcoalitionexampleOCFGame:AnOCFgameGwithplayersetN=P[SisgivenbyacharacteristicfunctionU[0;1]m+n7!R,whereU(0m+n)=0.Theroleofthecharacteristicfunctionofacoalitiongamespeciesthevaluationofacoalition[139].CoalitionStructure:AnoverlappingcoalitionstructureoverN,denotedasCS,isdenedasasetCS=fC1;:::;Cmgwheremisthenumberofcoalitions,CjˆNand[m j=1Cj=N.Thecoalitionscanbeoverlapping,andthus,thesetsmaynotbedisjoint.ResourceVector:AcoalitionCj2CScanalsoberepresentedasaresourcevectorrj.rjisthecumulativeresourcecontributionofeachplayerinthatcoalition.So,rj=[rj1:::rj(m+n)]whererjidenotesthefractionofresourcethatplayeriallocatestocoalitionCj.Ifrji=0,itmeansthatuseridoesnotbelongtocoalitionCj.101AcoalitionstructureCSisalsorepresentedwithanitelistofvectorsCS=(r1;:::;rm)thatsatises(i)rj2[0;1]m+n;and(ii)Pm j=1rji1foralli2N.PaymentVector:ThecharacteristicfunctionUdenesamappingfromtheresourcevectorrtopaymentvectorUforallcoalitionCj2CS.ThisisrepresentedasU(r;CS)=U=[U1U2:::Um].ThepaymentvectorofanindividualcoalitionCjcanberepresentedasU(Cj;CS)=U(rj;CS)=Uj=[Uj1Uj2:::Ujm+n].Thepaymentofanindividualplayercanberepresentedasasummationofpaymentfromallthecoalitionsithasparticipatedin.Ui(CS)=Pm j=1Ui(Cj;CS)=Pm j=1uj i.5.1.3Formulation WeformulatethecooperativerelayselectionandschedulingproblemasanOCFgame,G=(N;U)whereN=P[S,andjNj=m+n,andUdenotesthepayofffunctionthatconvertsauser'scontributioninacoalitionintoitsprot.Wepresenttheformulationintotwosteps-routingpathconstructionascoalitionformationandtransmissionschedulingasresourcesharinginanOCFgame. 5.1.3.1RoutingpathConstructionasCoalitionFormation Inthecontextofcooperativerelaycommunication,aprimaryuserinitiatesasearchfordiscover-ingaroutingpathtoitsdestination.Nodesareaddedtothepathbasedontheirmutualinterest(expressedaspayofffunction).Finally,aroutingpathbetweenaprimarytransmitter(source)andaprimaryreceiver(destination)isestablishedthatincludesoneormoresecondaryusersasinter-mediaterelaynodes(toreceivepacketsfromthepreviousoneandforwardpacketstothenextone102inthepath.)TheconstructionofroutingpathcanbemappedtothecoalitionformationinanOCFgame.Eachprimarytransmitteri2Pstartstheprocess,secondaryusersjointhecoalitionifitincreasestheirpayoff,andacoalitionCi(i.e.apathbetweentheprimarytransmitterandreceiver)isformed.Thus,Cirepresentstheroutingpathstartingwithprimarytransmitteri,followedbyoneormoresecondarytransmittersfromthesetNbasedontheirmutualneeds-constructingamulti-hoproutingpathandcreatingtransmissionopportunitiesrespectively.Thepayoffofacoalitionisdenedasthesummationofthepayoffofallitsmembersearnedfromjoiningthecoalition.AcoalitionstructureCSrepresentsthesetofmsuchcoalitions(i.e.routingpathofmprimaryusers)whereanyofthesecondarytransmittersmayparticipateinmorethanonecoalition.So,CS=fC1;:::;Cmg.Forexample,therearetwocoalitionsformedinFig.5.2.Therstprimarytransmitter-receiverpair(p1;p0 1)formsacoalitionC1withfoursecondaryuserss1,s3,s4,ands5.Thisimpliesthepacketsfromprimaryuserp1followsthispathp1!s1!s3!s4!s5!p0 1.Thesecondprimarytransmitter-receiverpair(p2;p0 2)formsanothercoalitionC2withthreesecondaryuserss2,s3,ands4.Therearetwosecondaryusers(s3,s4)overlappinginboththecoalitions. 5.1.3.2SchedulingasResourceSharing Thepackettransmissionschedulingcanbemappedtoresourcesharinginthecoalitiongame.Theresourcecontributionofindividualuseri2NisdenotedasriandtheresourcecontributiontoacoalitionCjisdenotedasrjiandri=Pm j=1rji.TheresourcevectorofacoalitionCjisdenotedasrj=[rj1:::rj(m+n)]wheretherstmentriesrepresentresourcecontributionfromprimaryusersandthenextnentriesrepresentcontributionfromsecondaryusers.ConsideringTtimeslots,eachuserhasmaximumTtimeslotstoshareitwithotherusersinitscoalitionorscheduleitsown103transmission.Aprimaryuseronlycontributestoitsowncoalitionandtheresourcecontributionbyaprimaryuseri2Pisthetotalamountoftimesecondaryusersinitscoalitiontransmittheirownpacketsinitssub-channels.ri=rii=1TTXt=1Xj2Ciij!j0(t)1;8i2P(5.1)Here,jx!y(t)isanindicatorfunctionwhosevaluecanbef0;1g.jx!y(t)=1impliesthatuserxsendspackettouseryattimetincoalitionCjwherex;y2N,0meansnotransmission.Ify=x0,userxsendspacketdirectlytoitscorrespondingdestination.Asecondaryusercontributesitsresourcetomorethanonecoalitions.Theresourcecontribu-tionbyasecondaryuseri2StoacoalitionCjistheamountoftimeitengagesinreceivingandrelayingpacketsoftheprimaryuserj2Pofthatcoalition.rji=1TTXt=12 6 4Xk2Cjji!k(t)+Xq2Cjjq!i(t)3 7 5;8i2S(5.2)Foranyuseri2Nbydenition,ri1.Inordertoscheduleusers'transmissionwithoutinterference,additionalconstraintsmustbesatised.Ingeneral,anyuserx2Ncannotsendtomorethanoneusery2N.Also,itcannotreceivefrommorethanoneusery2N.mXj=1Xy2Cjjx!y(t)1;(x2N)(5.3)mXj=1Xy2Cjjy!x(t)1;(x2N)(5.4)104Also,auserx2Ncannotsendandreceivepacketsimultaneouslyatthesametimeslott.mXj=12 6 4Xy2Cjjx!y(t)+Xy2Cjjy!x(t)3 7 51(5.5)Furthermore,allthescheduledtransmissionsmustbeinterferencefree.So,whileauserinacoalitionisreceivingpacketfromanotheruserinthesamecoalition,allotherinterferinguserstothatreceiverinthesamecoalitioncannotsendanypacket.Otherwise,thereceiverwillexperienceinterference.jx!y(t)+Xz2IyXq2Vzjz!q(t)1(5.6)Here,Iyrepresentsthesetofnodesinterferingtousersy'stransmissionwhileVzrepresentsthesetofnodeswithintransmissionrangeofuserz.Notethat,auser'sinterferencerangeisusuallylongerthanitstransmissionrange. 5.1.4PayoffofaPrimaryUser Thepayoffofaprimaryuseri2PfromacoalitionCi,Upi(Ci;CS)isdenedintermsofdatarateprot > > < > > > :jUdj=difd>11otherwise(5.18)whereUddenotesthedifferencebetweenuseri'spayoffatrounddandatroundd1.Asthenumberofroundincreases,ddecreasestoavaluebelowthethresholdandprimaryuserbecomesstablewithitscoalition.Also,eachsecondaryusercannotrequesttransmissiontimelowerthans.Whenasecondaryuser'srequestwithminimumtransmissiontimetoaprimaryuserfails,itstopsparticipatinginthatcoalition.Thus,theusageofdandscontrolstheconvergencespeed,andtheroutingpathsbecomestable.Whenusersareonastableroutingpath,thechannelstatesmaychangethatmayreducethepayoffvaluationofoneormoreusersonthepath.Toavoidcontinuingonalessprotablepath,allparticipantscontinuouslymonitorthepayoffvalue.Ifthepayoffdropssignicantlyfromtheagreedone,theprimaryusermayswitchtodirecttransmissionandinitiatethesearchfortherout-ingpathwhileasecondaryusermayremoveitselffromthepathandsearchforanewopportunity.1145678910# of PUS, # of SUs 30, Tx power 0.100000W02468PU profitmcRoute upper limitmcRoute lower limitnpRoute upper limitnpRoute upper limit(a)averagePUprot5678910# of PUS, # of SUs 30, Tx power 0.100000W0.60.70.80.911.11.21.31.4SU profitmcRoute upper limitmcRoute lower limitnpRoute upper limitnpRoute upper limit(b)averageSUprot5678910# of PUS, # of SUs 30, Tx power 0.100000W051015202530data ratemcRoute upper limitmcRoute lower limitnpRoute upper limitnpRoute upper limit(c)averagedatarate5678910# of PUS, # of SUs 30, Tx power 0.100000W-101234number of roundsmcRoute upper limitmcRoute lower limitnpRoute upper limitnpRoute upper limit(d)numberofroundsFigure5.4:ComparisonbetweenmcRouteandnpRoute[79]5.3PerformanceEvaluation Inthissection,weanalyzetheperformanceofcoalitionbasedmulti-hopcooperativeroutingalgo-rithm.Wesimulateacognitiveradionetworklocatedinanareaof5000m5000m.Wedeploydifferentnumberofprimarysource-destinationpairs(5to10).Eachprimarysourcenodeisas-signedachannelwith20KHzbandwidth.Thetransmissioncycletimeisnormalizedtooneunitandasecondaryuserrequires1=10thofitscycletimeisforsupportingitsminimumraterequire-ment.Inordertoevaluatetheimpactofcooperationintheroutingpathselection,wevarythe115Table5.3:SimulationparametersParametersValueBandwidth(B)20KHzTransmitterandReceiverGain(Gt;Gr)1PowerspectraldensityofNoise(N0)1010W/HzTransmissionPower(Etx)100mWPathlossexponent()2Basedistance(d0)10m[44]Threshold()0:001Packetlength(len)1024bitsnumberofprimaryusers,secondaryusers,andtransmissionpower.ThesimulationparametersarelistedinTable5.3. 5.3.1Topology Theprimarysourceanddestinationnodesarerandomlyanduniformlydeployedinthenetworkarea.Secondaryusersarealsorandomlyanduniformlydeployedintheareasothateachuserhasatleastoneneighbor.Wealsomadesurethateachpairofprimarysourceanddestinationnodeisconnected,andthereexistsatleastonepathbetweenprimarysource-destinationpairsthroughsecondaryusers.Foreachsetofinputconguration,wehavegeneratedasmanyas50samplescenariosandthestatisticsarerecordedforeachset.Finally,forstatisticalcondence,wetakeanaverageofresultsofallsetstorepresenttheoutcomeofeachscenario.5.3.2PerformanceComparisonwithPriorWork Tocomparewithanexistingalgorithm,weimplementamodiedversionofthealgorithmproposedin[79].Wehavechosen[79]over[127]sincethelatteroneassumesxedroutingpath.Unlike[79],inthemodiedversion,asecondaryusermayreceivesimultaneouscoalitionrequestsfrommorethanoneprimaryuser.Asecondaryuserprocessesmultipleconcurrentcooperationrequests,116selectsoneofthemrandomly,andparticipatesinroutingpathofonlyoneprimaryuseratatime.Werefertothisalgorithmas`non-overlappingrouting'inshort`npRoute'.WecalculatePUandSUprot(with95%condenceinterval)withthevaryingnumberofprimaryuserswhilethetransmissionpowerissetto0:1Wandnumberofsecondaryusersissetto30.Fig.5.4aand5.4bshowthattheproposedcooperationalgorithmachieveshigherPUandSUpayoffthanthoseofnpRoute.InmcRoute,PUprotstaysalmostconstantwiththeincreaseinthenumberofPUs.ThisisbecauseeachprimaryuseronaveragecooperateswithsamenumberofsecondaryusersandincreasingnumberofprimaryusersdoesnotincreasetheaveragePUprot.Ontheotherhand,SUprotdecreasesduetoincreasingcompetitionamongthem.WealsoshowinFig.5.4cthatthecooperativedatarateachievedthroughmcRouteishigherthannpRoute.Also,weinvestigateaveragenumberofrounds[119]thatreectsthestabilityandconvergencespeed.Fig.5.4dshowsthatnpRouteconvergestoalocalmaximawhenithandlesmultiplecooperationofferssimultaneously.Ontheotherhand,mcRoutegoesthroughfewmoreroundstoachievehigherdatarateandhigherPUandSUpayoff.Similarly,wealsovarythenumberofsecondaryusersandcalculatePUandSUprot(with95%condenceinterval).mcRoutecreatesmorecooperationopportunityforsecondaryusersthannpRouteandincreasesthenumberofsecondaryusersinvolvedincooperationandtheirprotsaswell.Tobetterunderstandthemulti-hopcooperationbehaviorincognitivenetworks,wefurtherinvestigatethefollowingpropertiesoftheproposedmechanisminadditiontoaveragetoPUandSUprot.First,averagelengthoftheroutingpath(i.e.numberofrelaysoneachpathofPU);italsoindicatestheaverageparticipationofsecondaryusersineachroutingpath.Second,numberofoverlappingsecondaryusers(i.e.numberofSUsinvolvedinmorethanoneroutingpathsofPUsincomparisontototalparticipatingSUs).117# of PUS, # of SUs: 20, Tx power 0.100000 W5678910path length23456max path lengthmin path lengthavg path length(a)pathlengthvs.numberofPUs# of PUS, # of SUs: 20, Tx power 0.100000 W5678910# of SUs24681012overlapping SUsparticipating SUs(b)numberofoverlappingSUsvs.numberofPUsFigure5.5:ResultswithvaryingPUs# of PUS 5, # of SUs, Tx power 0.100000 W1015202530path length23456max lengthmin lengthavg length(a)pathlengthvs.numberofSUs# of PUS 5, # of SUs, Tx power 0.100000 W1015202530# of SUs0246810overlapping SUsparticipating SUs(b)numberofoverlappingSUsvs.numberofSUsFigure5.6:ResultswithvaryingSUs5.3.3ResultswithVaryingNumberofPUs Werstvarythenumberofprimaryusersfrom5to10pairswhilethenumberofsecondaryusersisxedto20.Figure5.5showstheroutingpathlength,andthenumberoftheoverlappingnodesparticipatinginthecooperation.Althoughthelengthoftheroutingpathdoesnotvarywiththenumberofprimaryusers(Fig.5.5a),thenumberoftheparticipatingandoverlappingsecondaryusersincreasesalmostlinearly(Fig.5.5b).1185.3.4ResultswithVaryingNumberofSUs Next,weperformthesamesetofexperimentsbutwithvaryingnumberofSUsfrom10to30.Thenumberofprimaryusersisxedto5pairs.Allotherparametersarekeptthesame.TheresultsaredepictedinFig.5.6.Thepathlengthincreaseswithanincreaseinthenumberofsecondaryusers(Fig.5.6a).Asexpected,thenumberofcooperatingSUsincreaseswithvaryingnumberofSUs(Fig.5.6b).Wealsoevaluatetheimpactoftransmissionpoweroncooperationbyvaryingthetransmissionpowerfrom0:1Wto0:5W.5.3.5ResultswithAlgorithmParameters Weinvestigatetheimpactofchangingtwokeyparametersinrelayselectionandcoalitionforma-tion.TherstparameterdenotesthetradeoffbetweenthroughputanddelayinthepayoffofaprimaryuserinEqn.5.7.Wevarythevalueofbetween0and1andrecordthechangeinuserpayoff,pathlength,andnumberofcooperatingsecondaryusers.TheresultisshowninFig.5.7.Asthevalueofreachesto1,theprimaryuserismoreinterestedinincreasingdatarateandachievablethroughputandignoringthedelaycostintroducedbyrelayingsecondaryusers.There-fore,numberofparticipatingsecondarynodes(Fig.5.7a)andpathlength(Fig.5.7b)increaseswiththeincreaseinvalueof.ThisalsoincreasesPUprotalmostlinearlyandopensmoreop-portunityforsecondaryuserstoincreasetheirpayoff(Fig.5.7c).Next,weselecttoinvestigatethestabilityofthealgorithm.Fig.5.7dshowsthatmoreroundsareneededtoreachstablecoali-tionswithsmallervaluesof.Thus,thesetwoparameterscontrolthecooperationopportunityandconvergencespeedoftheroutingpaths.119# of PUS: 10, # of SUs: 30, Tx power 0.100000 W00.20.40.60.81# of SUs0510152025overlapping SUsparticipating SUs(a)numberofoverlappingSUsvs.# of PUS: 10, # of SUs: 30, Tx power 0.100000 W00.20.40.60.81path length24681012max path lengthmin path lengthavg path length(b)pathlengthvs.00.20.40.60.81# of PUS: 10, # of SUs: 30, Tx power 0.100000 W051015average PU profit1.11.21.31.4average SU profitavg. PU profitavg SU profit(c)protvs.00.0010.01 0.1 1 convergence time33.544.55number of rounds(d)ConvergenceandstabilityFigure5.7:Resultswithvaryingalgorithmparameters1205.4Summary Inthischapter,weformulatethecooperativeroutingpathformationproblemasanoverlappingcoalitiongamewheresecondaryusersactivelyparticipateinmultipleroutingpaths.APU'spayoffisdenedasacombinationofdatarateprotandpathdelay.AnSU'spayoffisdenedasbitperenergyspentinrelaying.BasedonthepayofffunctionsdenedinanOCFgame,wedeviseadis-tributedmulti-hoproutingandschedulingprotocol.Bothprimaryandsecondaryusersgothroughroundsofexchangingmessagesandnegotiatingoncooperationtermstobuildstableroutingpaths.WecompareouralgorithmwithanexistingworkandthesimulationresultsshowthatourapproachoutperformstheexistingworkintermsofPUandSUprot.Ouralgorithmprovidesstableroutingpathsthatisalsoveriedthroughsimulation.Wehaveconsideredsinglepathroutingbetweeneachprimarysourcedestinationpair.Wewillinvestigatetheimpactofcooperativebehaviorinthecaseofmulti-pathroutingandpossiblecooperationstrategywithsecondaryusersinfuturework.121Chapter6 TruthfulOnlineSpectrumAuctions Inpreviouschapters,wehavediscussedspectrumsharingtechniquesundersensingandrelaybasedcollaborationmodels.Inthesensingbasedcollaborationmodel,secondaryuserssharetheirsens-ingreportstotakeajointdecisionwithoutprimaryusers'participation.ThesuccessinspectrumutilizationdependsontheaccuracyofPUdetectiontechniquesandtheircollaborativedecision.Intherelaybasedcollaborationmodel,PUsactivelycoordinatewithSUstoimprovetheirsignalper-formancewithcooperativediversity.WhenthePUsareidlewithnopendingtransmissionrequeststheyhavenoincentiveinsharingtheirunusedspectrumwithspectrumhungrysecondaryusers.Inthischapter,weexploreauctionbasedcollaborationmodels1thathaverecentlybeeninvestigatedasameanstoencouragetheseusersintosharingtheirunusedspectrumandearningrevenueinre-turn.RecentinitiativesfromFCCalsoindicatetheprospectofauctionbasedcollaborationmodel.Accordingtothismodel,PUscanselltheirunusedlicensedspectrumunitsintemporal,spectral,and/orspatialdomainsfordifferentdurationswhilethebuyerslikesmallwirelessnetworks,indi-vidualinfrastructurenetworks,orhomenetworkscanbidfortheshareofthespectrum[22].These1Theworkpresentedinthischapterhasbeenpublishedinthreeresearcharticles:(i)ChowdhurySayeedHyder,ThomasD.Jeitschko,andLiXiao.BidandTimeTruthfulOnlineSpectrumAuc-tionswithDynamicUserArrivalandDynamicSpectrumSupply,inthe25thInternationalConferenceonComputerCommunicationandNetworks,Waikoloa,Hawaii,USA,Aug1-3,2016.(ii)ChowdhurySayeedHyder,ThomasD.Jeitschko,andLiXiao.TruthfulOnlineDoubleAuctionswithReal-timeStochasticArrivalofDemandandSupply,inthe25thInternationalConferenceonComputerComminca-tionandNetworks,Waikoloa,Hawaii,USA,Aug1-3,2016.(iii)ChowdhurySayeedHyder,ThomasD.Jeitschko,andLiXiao.Towardsatruthfulonlinespectrumauctionwithdynamicdemandandsupply.inMilitaryCommunicationsConference(MILCOM),pp413Œ418,Tampa,Florida,USA,October26-28,2015.122users'spectrumdemandmayvarydependingontheapplicationtype,usertrafc,andusermobil-ity.Forexample,auserwithdelay-tolerantapplicationscandeferitstransmissionwhereasauserwithdelay-sensitiveapplicationsmayrequireimmediatetransmission.Auctionbasedcollaborationmodelshavebeenstudiedinthecontextofspectrum(re-)allocation,withparticularattentionbeingpaidtotheresultingefciencyofspectrumuse(bothwithinandacrosslocations,becauseforagivengeographicallocation,non-interferinguserscanbeallocatedthesamespectrumtoincreasebothcoverageandcapacity[114]),therevenueorprotgeneratedintheprocessof(re-)allocation[31,129],demandsatisfaction[135,143],andotherperformancemetrics.Similartothesesingleauctionmechanisms,doubleauctionmechanismshavebeende-signedwithauxiliarymotivationsofimprovingefciency,increasingrevenue,etc.[22,31,40,143].Thereareadditionalpracticalconcerns:forinstance,byexploitingtheinherentcharacteristicsofwirelessnetworks,abiddermayoverhearorinterceptthebiddinginformationofcompetitorsandgainanadvantage[138];and,thus,considerableattentionhasbeengiventoassuringthattheauc-tionmechanisminducesparticipantstotruthfullyreporttheirneedsandrequirements,ratherthanhavethemmisrepresenttheirunderlyingsupplyordemandconsiderationsinordertofigameflthesystemandtherebyincreasetheirownbenetsattheexpenseofothers[142].Thisauctionbasedresearchconstitutesasignicantadvancementinthepotentialforeffectivespectrummanagement.However,mostworkfocusesonstatic(oroff-line)settingswithknownnumberofbiddersandsupplies,therebysuppressingtheinherentdynamicaspectsofspectrumavailabilityandspectrumneedsdiscussedattheoutset.Also,existingworkconsidersuserswithnotransmissiondeadlinesandtherefore,theproposedauctionmechanismsareonlybidtruthful.Unfortunately,giventhetransmissionexibilitytheusersmaymanipulatetheoutcomeoftheseauctionsbytweakingtheirdeadlineseveninthecaseofasingleunitdemandperuser(explainedwithexamplesinSec.6.1.4).Anexceptiontothisissomerecentwork(e.g.,TRADE[141],123Topaz[30],andTofu[125])thatconsidersdynamicarrivalofbiddersandaddressesonlinesingleauctionmechanismsbasedontheideaspresentedin[45].Thebiddersintheseauctionsplacetheirbidstocompeteforaxednumberofspectrumunits.However,thesupplyuncertaintyi.e.,thedynamicsinspectrumavailabilityhasnotbeenanalyzedinthesestudies.Ontheotherhand,thestudyin[114]andTORA[63]analyzethesingleauctionmechanismconsideringthedynamicsinspectrumavailabilitywhilethenumberofbiddersisxedthroughouttheauction.TODA[118]presentsadoubleauctionmechanismconsideringstochasticarrivalofuserswithoutconsideringspectrumreusabilitywhichisoneofthedistinctfeaturesofspectrumauction.Amorerecentpaper,LOTUS[20]considersadoubleauctionmodelconsistingofaxednumberofuserswithdynamicdemandandxednumberofspectrum.Althoughthisworkconsidersadoubleauctionwithdynamicuserdemand,thebiddershavenotransmissiondeadlinesandthenumberofsellersisxed.Asaresult,LOTUSfailstosatisfythetruthfulnesspropertywhenitisappliedinanonlinesettingsinceusersmaygainbenetsbylyingabouttheirdeadlines.Incontrast,weinvestigateauctionbasedcollaborationmodelsinwhichbothspectrumavail-abilityanddemandarestochasticthroughouttheauctions,andusers'urgencyfortransmissionisalsorandom.Werstanalyzethisdynamicsettingfromthesingleauctionperspective,discussitschallenges,anddevelopthetruthfulmechanism.Wefurtherextendouranalysistoanonlinedoubleauctionsettingwherebothbiddersandsellersstochasticallyjointheauctionwithdifferentdeadlinesandvaluations.Anonlinedoubleauctionbetterrepresentsthesecondaryspectrummar-ketthanthesingleauctionsincedoubleauctionsaccommodatediversityinsellers'reservepricesandofferexibilitytotheauctiondesign.Inpresenceofsuchdiversity,anauctioneerhastomakeonlinedecisionsonspectrumallocationandpricingwithouttheknowledgeoffutureparticipantsandtheirdemandandsupply.Thisonlinefeaturemakesthespectrumauctioneasilyvulnerabletobidanddeadlinemanipulation.Abidderorsellermaygainbenetoverothersbymisreportingits124arrival,deadline,oritsvaluation.Therefore,themechanismmustbeholdthetruthfulnessproperty.Additionally,themechanismmustsupporttheallocationofsamespectrumunittonon-interferingbidderstoimprovethespectrumutilizationrate.Ourgoalhereisthustoexploresuchdynamicsettingsanddesignonlinemechanismsforbothsingleanddoubleauctionsthatconformtotheserequirements.Summaryofourcontributionsinonlineauctionsettingsis:Westudythespectrumallocationproblemtosecondaryusersinanauctionsettingwhereidlechannelsarrivestochasticallyandthetotalchannelsupplyisunknown;andbidderswithrandomlifetimes(transmissiondeadline)arriveattheauctionstochasticallywiththetotalnumberofbiddersbeingunknown.Weidentifythechallengesassociatedwiththedynamicauctionmodelandshowthevulnerabilitiesofexistingresearchinsuchsettings.Wepresentouranalysisofthisdynamicsettinginthreesteps.Intherststep,allbidders(andsellers)havethesamevaluations.Inthesecondstep,werelaxthisrestrictionandconsiderdiversityinbidders'valuations.Inthethirdstep,wealsoconsiderthesellerswithdifferentvaluations.Ouranalysisoftheseauctionsettingsisbasedonanendogenouspriorityvaluefunctionthatdeterminesthepriorityofabidderateachperiodgivenitsvalueandurgencyfortransmissioniftheauctioneerhasdistributionknowledge.Weprovethatourproposedmechanismadherestotruthfulnessandindividualrationality.Consequently,wepresentthreeauctionalgorithms.Therstalgorithmisderivedbasedonthepriorityfunctiontodevelopadistributionawaretruthfulsingleauctionmechanism.Thesecondalgorithmisalsoderivedbasedonthepriorityfunctionanddevelopadistributionawaretruthfuldoubleauctionmechanism.Finally,wepresentadistributionunawaremech-anismforatruthfuldoubleauction.Weintroduceabid-independent`debtfactor'thatadjuststhepaymentamountofawinnerdependingonthenumberofusersinterferingwithitover125Figure6.1:Auctionwithdynamicbidderandsupplyitslifetime.Theusersgothroughacandidatescreeningphasefollowedbyadebtcalculationphase,andnallywinnersareselectedadheringtopricingrulesinthealgorithm.Finally,wepresentsimulationresultstoanalyzetheperformanceofthesealgorithmsunderdifferentauctionsettings.Weevaluatetheefciencyoftheproposedmechanisms.Wecom-paretheperformanceoftheauctionmechanismswithanoff-linemechanismandexistingworke.g.Topaz[30]intermsofrevenue,demandsatisfaction,andspectrumutilization.6.1OnlineDynamicAuctions Inthissection,weexplainthedifferentcomponentsoftheauctionmodelandhighlightthedesignchallengestoachieveatruthfulonlineauctionmechanism. 6.1.1TheAuctionEntities Weconsiderperiodicspectrumauctionswhereusers'arrivalsandspectrumavailabilityoccuronlyatthebeginningofaperiod(seeFig.6.1).Theperiodlengthisxedacrosstime.Thethreeentitiesinvolvedinaspectrumauctionareprimaryusersassellers,secondaryusersasbidders,andanauctioneer.Sellers:Primaryusersputtheirunusedspectrumresourcesforsaleattheauctioninunitsofxedspectrumbandwidth.Thesalesunitsareidentical;however,eachsellerhasitsownvaluation126ofitsspectrumunits.Aspectrumunitremainsattheauctionforsaleforoneperiodonly.Asalesrequestofatypicalsellerjcontainsitsreserveprice,commonlyreferredtoasthe`ask'thatdenotestheminimumpriceasellerwillacceptperspectrumunit.Werepresentasalesrequestwith˚p j=(aj)whereajdenotesthesellerj'saskforitsspectrumunit.Aseller'sutilityiscalculatedbysubtractingitsvaluefromthepaymentitreceivedattheauc-tion.So,sellerj'sutilityUj=xj( pj-vj)wherexj2f0;1gdenoteswhethersellerjhaswon(xj=1)ornot(xj=0),vjdenotesseller'svaluation,and pjdenotessellerj'spaymentwhenitwinsintheauction.Bidders:Secondaryuserssubmittheirspectrumrequirementsintheformofbidrequests.Abidrequestofabidderiisrepresentedas˚i=(gi;oi;di;bi)wheregidenotesitslocationinfor-mation,oidenotesthetimeofarrivalattheauction,di(oi)denotesthetransmissiondeadline,i.e.,themaximumtimeabidderstaysintheauction,andbidenotesthemaximumvalueabidderiswillingtopayforonespectrumunit.Eachbidderhasunitdemandandhasnoparticularpreferenceoveranyspectrumunitsinceallunitsareidentical.Abidder'slifetimedenotesitstransmissiondeadline,anditisexpressedintermsofnumberofperiodsabiddercanstayintheauctiontowinaspectrumunit.Ifthebiddercannotwinbyitsdeadline,itexitstheauction.Thelifetimeliofabidderiwitharrivaltimeoianddeparturetimediisexpressedasli=dioi+1.Bidderi'sutilityisUi=xi(vi si)wherexi2f0;1gdenoteswhetherbidderihaswon(xi=1)ornot(xi=0),videnotesthebidder'svaluation,and sidenotesbidderi'spaymentwhenitwinstheauction.Auctioneer:Theauctioneerisresponsibleforconductingper-periodauctions.Ateachperiod,theauctioneerappliesanalgorithmtoselectwinnersanddeterminetheirprices.Theauctioneer'sutilityisreferredtoastherevenueitmakesfromtheauctionthatiscalculatedbysubtractingthetotalamountofsellers'paymentfromthetotalamountofbidders'payment.Theauctioneer's127utility,UAisthusdenedas,UA=Pi si-Pj pjwhere sirepresentsthepaymentreceivedfrombidderiand pjdenotesthepaymentmadetosellerj.6.1.2AuctionProperties Denition1AnonlineauctionmechanismistruthfulifandonlyifnobiddericanimproveitsutilityUibyreportingb0 i6=vi,orfalselyreportingitslocationg0i6=gi,orarrivaltimeo0 i6=oi,ordeadlined0 i6=di,oranycombinationofthemandnosellerjcanimproveitsutilityUjbyreportingitsaska0 j6=vj[30].Denition2Anauctionmechanismisfiexanteweaklyindividualrationalflifallagents'expectedutilityfromthemechanismwhenenteringintotheauctionarenon-negative.Anonlineauctionmechanismisfiexantestronglyindividualrationalfliftheexpectedutilityofallagentswhenen-teringintotheauctionarepositive.Anonlineauctionmechanismisfiexpostweaklyindividualrationalflifallagents'realizedutilityfromthemechanismisnon-negative.Anonlineauctionmechanismisfiexpoststronglyindividualrationalflifallagents'realizedutilityfromthemecha-nismispositive.Thisimpliesthatforanybidderi,Ui0andforanysellerj,Uj0.Denition3Thebudgetbalancereferstonon-negativeutilityoftheauctioneer.Anauctionmech-anismisbudgetbalancedifineachperiodthetotalpaymentsreceivedfromallbuyersisnolessthanthetotalamountspaidtoallsellers.ThisimpliesthattheutilityoftheauctioneerUA0.6.1.3DesignChallenges Anonlineauctionindynamicenvironmentsposesseveralchallengesindesigningthemechanism.Wepresentthreekeydesignchallengesasfollows:128(a)Onlinedecisionwithdemandandsupplyuncertainty:Theprimarychallengeistotakeanonlinedecisionwithoutknowingtheexactnumberofsupplyandbidderinfutureperiods.Themechanismmusttakeintoconsiderationthetradeoffbetweenpresentopportunityandfutureuncertaintyforefcientspectrumallocation.(b)Spectrumreusability:Unliketraditionalauctions,samesupply(i.e.,spectrum)canbesoldtomultiplenon-interferingbiddersinspectrumauctions.Thisuniquepropertymakesitmorechallengingtoachieveatruthfulmechanism.(c)Timeandbidbasedcheating:Duetotheonlinedemandandsupplynatureofthespec-trumauction,biddersmayreporttheirbids,arrivaltime,anddeadlineuntruthfully,andgainadvantageintheformofincreasedutilities[30].Theauctionmechanismmustprovidesafe-guardagainstanysuchattemptofcheatingfrombidders.6.1.4Illustration Beforeexplainingourauctiondesign,wedemonstratehowbidderscangainadvantagebymisre-portingtheirinformatione.g.theirarrivaltimesordeadlinesinanonlinedynamicauctionsetting.Usingillustrativeexamples,weshowthatexistingstaticorpartiallydynamicmodelscannotensuretruthfulnessinsuchcases.Forthesakeofsimplicity,wehaveonlyshownbidderswithdifferentvaluationsinthefollowingexamples.Westartwithasimpleexamplewhereeachparticipantreportstruthfully.BiddersA,B,andCarriveattimet1andbid$100,$80,and$50respectively.Oneunitofspectrumalsobecomesavailableatthesametime.Weassumethatallthreebiddersareinterferingtoeachother.Thelifetimeofbiddersis[t1;t4),[t1;t2),[t1;t5)respectively.Weapplystaticauctionrulespresentedin[142]wherethehighestbidderswinandthepriceisdeterminedbythenexthighestlosing129Figure6.2:Applyingstaticauctionrules[142]indynamicenvironmentsbidderinitsneighborhood.Accordingly,bidderAwins,andpays$80.Attimet2,Bleavestheauction,andattimet3,anotherspectrumunitbecomesavailable.So,Cwinsnextandpays$0.Finally,anotherspectrumunitarrivesatt6butremainsunsold.So,theauctionefciencybecomes$150($100+$50),revenuebecomes$80($80+$0),bidders'satisfactionratiobecomes2=3,andspectrumutilizationratebecomes2=3.Fig.6.2demonstratesthearrivalanddepartureofbiddersintheauctionandalsonotesdownthedecisionmadebytheauctioneerateachperiodfollowingrulesin[142].Next,weshowthatabiddercanlieaboutitsarrivaltimeandincreaseitsutilitywhilestaticrules[142]areappliedinanonlinedynamicenvironment.Inthesamepreviousexample,considerbidderAreportsitsarrivaltimeatt3insteadoft1(t3>t1)andthusavoidscompetitionwithhighervaluedbidders.Asaresult,bidderBwinsatt1,pays$50,andleavestheauction.Attimet3,bidderAwinsandpays$50,andthusincreasesitsutilityby$30.Again,thereisnotradeattimet6.So,thebiddersatisfactionratioandspectrumutilizationrateremainunchanged,butefciencyandrevenuebecome$180($100+$80)and$100($50+$50).Fig.6.3demonstratesthisauctionscenario.Fromthisinstance,itisclearthatstaticauctionrulescannotbeappliedtoonlineauctionsindynamicenvironments.Finally,weselectapartiallydynamicmodelTopaz[30]andshowhowabiddermisreportsitsinformationandincreasesitsutilityindynamicenvironments.Inthesameexample,consider130Figure6.3:Latearrivalmanipulationbyabidderwhileapplyingstaticauctionrules[142]Figure6.4:LatedeparturemanipulationbyabidderwhileapplyingTopaz[30]thatbidderAreportsitsdeadlinet7insteadoft4(t4kXx=1nx1 A=1Fm0 @kXx=1nx1 A+fm0 @kXx=1nx1 A=1Nk(6.5)whereNy=FmPy x=1nxfmPy x=1nx.Second,ifthetotalnumberofoldestbidders(bidderswithonlyoneperiodtolive)aremorethanthenumberofsupplyitems,thebidderpaysthehighestvalueandearnszeroutility.So,thepaymentissetbythepriorityrankofabidderj2A(t)with1periodtolive:Pr( si=1(v))=Pr m<1Xx=1nx!=Fm 1Xx=1nx!fm 1Xx=1nx!=N1:(6.6)Apartfromthersttwocases,thewinningpriceissetbyabidderj2A(t)andisgivenby:Pr si=y(v)=Pr0 @y1Xx=1nxm