SPRINGER BRIEFS IN ELECTRICAL AND COMPUTER ENGINEERING Lei Lei Chuang Lin Zhangdui Zhong Stochastic Petri Nets for Wireless Networks 123 SpringerBriefs in Electrical and Computer Engineering Moreinformationaboutthisseriesathttp://www.springer.com/series/10059 Lei Lei • Chuang Lin (cid:129) Zhangdui Zhong Stochastic Petri Nets for Wireless Networks 123 LeiLei ChuangLin StateKeyLaboratoryofRail DepartmentofComputerScience TrafficControlandSafety andTechnology BeijingJiaotongUniversity TsinghuaUniversity Beijing,China Beijing,China ZhangduiZhong SchoolofComputer andInformationTechnology BeijingJiaotongUniversity Beijing,China ISSN2191-8112 ISSN2191-8120 (electronic) SpringerBriefsinElectricalandComputerEngineering ISBN978-3-319-16882-1 ISBN978-3-319-16883-8 (eBook) DOI10.1007/978-3-319-16883-8 LibraryofCongressControlNumber:2015937432 SpringerChamHeidelbergNewYorkDordrechtLondon ©TheAuthor(s)2015 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade. Printedonacid-freepaper SpringerInternationalPublishingAGSwitzerlandispartofSpringerScience+BusinessMedia(www. springer.com) RecommendedbyXuemin(Sherman)Shen Preface Stochastic Petri Nets (SPNs), introduced in 1980, are a modeling formalism that canbeconvenientlyusedfortheperformanceandreliabilityevaluationofdiscrete eventsystems.Theyadmitagraphicalrepresentationthatiswellsuitedtotop-down and bottom-up modeling of complex systems, and present a very straightforward mapping between events in the SPN model and events in the underlying Markov process. Although SPNs have become a useful tool for researchers in computer science, they are unknown to most wireless researchers and are not widely used tomodelwirelesscommunicationsystems.Ontheotherhand,thenext-generation wireless networks such as the 5th Generation (5G) cellular systems will become increasinglycomplexinordertosupportforanincreasinglydiversesetofservices, applications, and users—all with extremely diverging performance requirements. SinceSPNsarefoundtobepowerfulinmodelingperformanceofcomputersystems withawealthofnumericalsolutiontechniques,itisveryinterestingtoexploretheir applicability in wireless systems. This book was motivated by a desire to bridge thegapbetweentheresearchonSPNmodelingformalismandontheperformance modelingofwirelessnetworks. In this book, we present our research results on applying SPNs to the perfor- mance evaluation of wireless networks under bursty traffic, in terms of typical Quality-of-Service (QoS) performance metrics such as mean throughput, average delay, packet dropping probability, etc. In the first chapter, we introduce the key motivations,challenges,andstate-of-the-artresearchonusingSPNsforcross-layer performance analysis in wireless networks. In Chap.2, we first introduce the SPN basics, and then focus on two powerful techniques in SPNs to deal with the well- known state space explosion problem: (1) model decomposition and iteration; (2) model aggregation using Stochastic High-Level Petri Nets (SHLPNs). We apply the first technique to the performance analysis of opportunistic scheduling and Device-to-Device (D2D) communications with full frequency reuse between D2D links in Chaps.3 and 4, respectively. The above two scenarios show two typical radio resource sharing paradigms in wireless networks: orthogonal sharing by schedulingandnon-orthogonalsharingbyfrequencyreuse.WeshowthatSPNscan provide an intuitive and efficient way in modeling the multiuser wireless system, vii viii Preface especiallyfacilitatingtheinclusionofdifferentresourcesharingparadigmsbetween wireless links. Moreover, the original complex model whose state space grows exponentially with the number of users can be decomposed into multiple single usersubsystems,anditerationmethodscanbeusedforperformanceapproximation. In Chap.5, we apply the second technique to formulate a wireless channel model for Orthogonal Frequency Division Multiplexing (OFDM) multi-carrier systems with SHLPN formalism in order to simplify the cross-layer performance analysis ofmodernwirelesssystems.ComparedwithexistingFiniteStateMarkovChannel (FSMC)modelwhosestatespacegrowsexponentiallywiththenumberofOFDM subchannels,ourproposedSHLPNmodelusesstateaggregationtechniquetodeal withthisproblem.Closed-formexpressionstocalculatethetransitionprobabilities among the compound markings of the SHLPN model are provided. When applied to derive the performance measures for OFDM system, the SHLPN model can accurately capture the correlated time-varying nature of wireless channels. We believetheexampleapplicationsofSPNstowirelessnetworksandrelatedfindings willrevealusefulinsightsforthedesignofradioresourcemanagementalgorithms and spur a new line of thinking for the performance evaluation of future wireless networks. Beijing,China LeiLei ChuangLin ZhangduiZhong Acknowledgements The authors would like to acknowledge the support of the NSFC (Projects No. 61272168, No. U1334202, and No. 61472199), the State Key Laboratory of Rail TrafficControlandSafetyinBeijingJiaotongUniversity(No.RCS2014ZT10),and theKeyGrantProjectofChineseMinistryofEducation(No.313006).Thanksalso areduetotheMastercandidates:MissQingyunHaoandMr.HuijianWangfortheir contributionofeditingwork. AveryspecialthankstoProf.Xuemin(Sherman)Shen,theSpringerBriefsSeries EditoronWirelessCommunications.Thisbookwouldnotbepossiblewithouthis kind support during the process. Thanks also to the Springer Editors and Staff, all ofwhomhavebeenexceedinglyhelpfulthroughouttheproductionofthisbook. ix