Optimal Random Access Protocols for Wireless Networks by Man Hon Cheung B.Eng., The Chinese University of Hong Kong, Hong Kong, China, 2005 M.Phil., The Chinese University of Hong Kong, Hong Kong, China, 2007 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in The Faculty of Graduate Studies (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) March 2012 c Man Hon Cheung, 2012 Abstract In this thesis, we present several random access algorithms for medium access control in wireless networks. Optimization theory, game theory, and dynamic programming are applied in the analysis and the design of these algorithms. First, we study the problem of multi-channel random access using the signal-to-interferenceplus-noise-ratio (SINR) model in cognitive radio networks. We formulate it as a network utility maximization (NUM) problem, and propose a distributed algorithm that converges to a near-optimal solution. Moreover, we apply coalitional game theory to study the incentive issues of rational user cooperation in a given channel under the SINR model. Next, we consider a wireless local area network (WLAN) with rational users, who may strategically declare their access categories (ACs) not intended for their applications in order to gain some unfair shares of the network resources. We propose to use the VickreyClarke-Groves (VCG) mechanism to motivate each user to declare truthfully its actual AC to the access point (AP). In order to implement the VCG mechanism with concave, step, and quasi-concave utility functions, we propose an enumeration algorithm to obtain the global optimal solution of the formulated non-convex NUM problem. To extend the aforementioned work on single-channel random access in WLANs, we focus on sigmoidal utility functions. We propose a subgradient algorithm to solve the formulated NUM problem using the dual decomposition method. If the sufficient conditions on link capacities are satisfied, the algorithm obtains the optimal solution. Finally, we consider the vehicular ad hoc networks. We study the problem of random ii Abstract access in a drive-thru scenario, where roadside APs are installed on a highway to provide temporary Internet access for vehicles. We first consider the single-AP scenario with random vehicular traffic, and propose a dynamic optimal random access (DORA) algorithm that aims to minimize the total transmission cost of a vehicle. We determine the conditions under which the optimal transmission policy has a threshold structure, and propose an algorithm with a lower computational complexity. Then, we consider the multiple-AP scenario with deterministic vehicular traffic arrival due to traffic estimation. A joint DORA is proposed to obtain the optimal transmission policy. iii Preface I am the first author and principal contributor of all chapters. All chapters are co-authored with Dr. Vincent W.S. Wong, who supervised the research. Chapters 2, 3, and 4 are co-authored with Dr. Robert Schober, who provided valuable comments for the works. Chapters 3 and 4 are co-authored with Dr. Amir-Hamed Mohsenian-Rad, who contributed in the formulation of the network utility maximization problems. In particular, in Chapter 3, Dr. Amir-Hamed Mohsenian-Rad contributed in proving a necessary condition related to the feasibility of the optimization problem. Chapter 5 are co-authored with Dr. Fen Hou and Dr. Jianwei Huang, who provided valuable comments for the work. The following publications describe the work completed in this thesis. In some cases, the conference papers contain materials overlapping with the journal papers. Journal Papers Accepted/Published • Man Hon Cheung, Amir-Hamed Mohsenian-Rad, Vincent W.S. Wong, and Robert Schober, “Random Access for Elastic and Inelastic Traffic in WLANs,” IEEE Trans. on Wireless Communications, vol. 9, no. 6, pp. 1861–1866, June 2010. • Man Hon Cheung, Vincent W.S. Wong, and Robert Schober, “SINR-based Random Access for Cognitive Radio: Distributed Algorithm and Coalitional Game,” IEEE Trans. on Wireless Communications, vol. 10, no. 11, pp. 3887–3897, Nov. 2011. iv Preface • Man Hon Cheung, Fen Hou, Vincent W.S. Wong, and Jianwei Huang, “DORA: Dynamic Optimal Random Access for Vehicle-to-Roadside Communications,” accepted for publication in IEEE Journal on Selected Areas in Communications, 2012. Journal Paper Submitted • Man Hon Cheung, Amir-Hamed Mohsenian-Rad, Vincent W.S. Wong, and Robert Schober, “Utility-Optimal Random Access for Wireless Multimedia Networks,” submitted, 2012. Conference Papers Published • Man Hon Cheung, Amir-Hamed Mohsenian-Rad, Vincent W.S. Wong, and Robert Schober, “Random Access Protocols for WLANs based on Mechanism Design,” in Proc. of IEEE International Conference on Communications (ICC), Dresden, Germany, June 2009. • Man Hon Cheung, Fen Hou, Vincent W.S. Wong, and Jianwei Huang, “Dynamic Optimal Random Access for Vehicle-to-Roadside Communications,” in Proc. of IEEE International Conference on Communications (ICC), Kyoto, Japan, June 2011. v Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii 1 Introduction 1.1 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Random Access in Wireless Networks 1 . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Cognitive Radio Networks . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Wireless Local Area Networks . . . . . . . . . . . . . . . . . . . . 2 1.1.3 Vehicular Ad Hoc Networks . . . . . . . . . . . . . . . . . . . . . . 3 Mathematical Foundation . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.1 Optimization Theory . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.2 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.3 Dynamic Programming 13 . . . . . . . . . . . . . . . . . . . . . . . . vi Table of Contents 1.3 Summary of Results and Contributions . . . . . . . . . . . . . . . . . . . 17 1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 Multi-channel SINR-based Random Access and Coalitional Game . . 22 2.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Network Utility Maximization . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4 Three-Phase Distributed Algorithm using Sequential Convex Optimization 33 2.4.1 Transmission Probability Optimization . . . . . . . . . . . . . . . . 33 2.4.2 Listening Probability Optimization . . . . . . . . . . . . . . . . . . 34 2.4.3 Three-Phase Distributed Algorithm . . . . . . . . . . . . . . . . . 35 Coalitional Game Theory for SINR Model . . . . . . . . . . . . . . . . . . 39 2.5.1 Coalitional Game . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.5.2 The Core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.5.3 Shapley Value 43 2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Performance Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3 VCG-based Truthful Random Access Protocols for WLANs . . . . . . 52 3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2.1 Utility Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.2 Network Utility Maximization Problem . . . . . . . . . . . . . . . 58 3.2.3 Non-cooperative Random Access Game . . . . . . . . . . . . . . . 59 3.3 Truthful Mechanism Design for WLANs . . . . . . . . . . . . . . . . . . . 61 3.4 Implementation of the VCG Mechanism . . . . . . . . . . . . . . . . . . . 64 3.5 Performance Evaluations 71 . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Table of Contents 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Random Access with Sigmoidal and Concave Utility Functions . . . . 79 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.1 System Model 4.2 Random Access with Sigmoidal and Concave Utilities 4.3 77 . . . . . . . . . . . 83 4.2.1 NUM for Random Access . . . . . . . . . . . . . . . . . . . . . . . 83 4.2.2 Dual Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.2.3 First Dual Subproblem . . . . . . . . . . . . . . . . . . . . . . . . 85 4.2.4 Second Dual Subproblem . . . . . . . . . . . . . . . . . . . . . . . 87 4.2.5 Centralized Algorithm for Random Access . . . . . . . . . . . . . . 87 4.2.6 General Optimality Conditions . . . . . . . . . . . . . . . . . . . . 89 Optimality and Sub-optimality . . . . . . . . . . . . . . . . . . . . . . . . 91 4.3.1 Optimal Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 4.3.2 Sub-optimal Solution: Upper and Lower Bounds . . . . . . . . . . 92 4.4 Performance Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5 Dynamic Optimal Random Access for Vehicle-to-Roadside Communications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.2.1 Traffic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.2.2 Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.2.3 Distributed Medium Access Control . . . . . . . . . . . . . . . . . 104 5.3 Problem Formulation 5.4 Finite-Horizon Dynamic Programming . . . . . . . . . . . . . . . . . . . . 109 5.4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Single AP Optimization with Random Vehicular Traffic . . . . . . 109 viii Table of Contents 5.4.2 Joint AP Optimization with Deterministic Vehicular Traffic . . . . 120 5.5 Performance Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6 Conclusions and Future Work 6.1 Research Contributions 6.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 131 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 . . . . . . . . . . . . . . . . . . . . . . . . . 133 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 ix List of Tables 5.1 List of Key Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.2 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 x List of Figures 1.1 V2V and V2R communications in a VANET. . . . . . . . . . . . . . . . . . 2.1 A CRN with set of users N = {1, 2, 3}, where the triangles and circles 5 represent the transmitters and receivers, respectively. The set of available (c) orthogonal data channels C = {1, 2} is provided by the primary BS. pi and (c) qi denote the transmission and listening probabilities for user i in channel c, respectively. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 25 Aggregate utility obtained using an exhaustive search and the three-phase distributed algorithm (i.e., Algorithm 2.1) based on the multi-channel SINR model. We can see that Algorithm 2.1 achieves a near-optimal solution. . . 2.3 45 Convergence of the aggregate utility u∗ (t) using the three-phase distributed algorithm (i.e., Algorithm 2.1). Notice that the aggregate utility obtained in each iteration is non-decreasing. The users probe the channels in phase I and select the best channel in phase II. In phase III, the transmission probabilities are adjusted based on the channels selected in phase II. . . . . 47 xi List of Figures 2.4 The change in aggregate utility u∗ (t) when the set of data channels C changes due to dynamic spectrum leasing. Initially, we assume that there are four data channels available. We assume that two data channels are removed from C and then one data channel is added back to C. We run the three-phase distributed algorithm (i.e., Algorithm 2.1) based on the previous solution after set C has changed. We can see that u∗ (t) converges again quickly to a fixed point when the set C changes. . . . . . . . . . . . . . . . . . . . . . . 2.5 48 Average aggregate throughput versus the number of orthogonal channels available for Algorithm 2.1 using the SINR model, the protocol model, and the MMAC [1]. Notice that the design based on the SINR model achieves the highest aggregate throughput. . . . . . . . . . . . . . . . . . . . . . . . 2.6 A CRN with eight users. User 5 generates and receives the least amount of interference due to its isolated position. . . . . . . . . . . . . . . . . . . . . 2.7 49 Aggregate utility of the grand coalition v(N ) = i∈N 50 φi(v) and the Shapley value φ(v) for the secondary users in Fig. 2.6. When θth is increased, v(N ) is decreased because the interference range is increased. When θth is increased to 15 dB, v(N ) is equally shared among these one-hop neighbours as stated in Theorem 2.7. Notice that user 5 has the largest share of payoff for θth < 15 dB due to its large marginal contribution to different coalitions. . . . . . . 3.1 51 Three different types of utility functions considered in this work: (1) Concave function: α-fair function (Ki = 0.1, αi = 1, and Li = 4), (2) Step function (Ki = 1.5 and pcritical = 0.25) , and (3) Quasi-concave function: i α-critical function (Ki = 0.015, αi = 3, and pcritical = 0.1). . . . . . . . . . . i 56 xii List of Figures 3.2 A WLAN with a set of users N = {1, 2, 3}. In our system model, user i first declares to the AP the utility parameter (or type) θˆi , which characterizes the AC of the application of user i. After receiving θˆi , ∀ i ∈ N , the AP assigns the transmission probabilities pˆ = (ˆ p1 , pˆ2 , pˆ3 ) for random access and charges the users t = (t1 , t2 , t3 ) according to the allocation and payment rules of the VCG mechanism described in (3.8) and (3.10), respectively. By using the VCG mechanism, it is shown in Theorem 3.2 that a rational player i should declare its true utility parameter θi in order to maximize its own utility. . . 3.3 64 Results in a sample network with six stations: (a) Utility, (b) Payment, and (c) Surplus (i.e., utility minus payment) of each station using the proposed VCG-based scheme. With the use of VCG mechanism, station 1 ends up having a lower surplus when it is selfish and is thus motivated to be honest. 3.4 73 (a) Throughput of users with step utility functions and other utility functions and (b) aggregate utility. We assume that the stations with α-fair and α-critical utilities are honest and we vary the number of selfish stations with step utilities. We can see that differentiated QoS and maximum aggregate utility can be maintained by using the VCG-based mechanism design (MD). 74 3.5 Number of iterations required to obtain the optimal solution by Algorithm 3.1 and an exhaustive search. We can see that Algorithm 3.1 has a much lower computational complexity than an exhaustive search. . . . . . . . . . 3.6 75 Average utility in the system achieved by our NUM-based random access scheme and a CSMA scheme versus the total number of stations N in the system. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 xiii List of Figures 4.1 Utility functions Ui versus data rate x for utility functions U1 (x) = 1 − (x + 1)−1 , U2 (x) = x2 , x2 +20 U3 (x) = 12 [1 − (x + 1)−2 ], and U4 (x) = x4 . x4 +300 Notice that U1 and U3 are concave functions, and U2 and U4 are sigmoidal functions. We address both concave and sigmoidal utility functions in this chapter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The solution of the first dual subproblem x¯∗i (λi ) versus λi for sigmoidal utility function Ui (x) = x2 . x2 +20 We can see that x¯∗i (λi ) is discontinuous at λi = λci = 0.0780. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 83 88 The minimal capacities cc1 and cc2 for types of utility functions versus the total number of stations N. Type 1 utility functions are concave, while Type 2 utility functions are sigmoidal. . . . . . . . . . . . . . . . . . . . . 4.4 Aggregate utility versus the total number of stations N when c ≻ cc using exhaustive search and Algorithm 4.1. . . . . . . . . . . . . . . . . . . . . . 4.5 93 94 Aggregate utility versus the total number of stations N when c ≺ cc using exhaustive search and Algorithm 4.1. The lower and upper bounds are obtained by replacing p∗ (λ∗ ) and x ¯∗ (λ∗ ) (i.e., the results from Algorithm 4.1) into the expressions in (4.33) and (4.32), respectively. We can see that the lower bound is very tight in this case. In fact, except for the case with 14 stations, the lower bound exactly matches the global optimal solution in all other considered cases. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 95 Convergence of the allocation of the persistent probabilities with insufficient capacity c ≺ cc using diminishing step size α(t) = 0.01/t, even though the allocation may not be globally optimal as discussed in Section 4.3. . . . . . 5.1 96 Drive-thru V2R communications with multiple APs. . . . . . . . . . . . . . 102 xiv List of Figures 5.2 An example of the time line representation for the events happened with three APs (i.e., J = {1, 2, 3}). Here, we assume that T1 = 10, T2 = 15, and T3 = 12. With respect to the time line, we have T1 = {1, . . . , 10}, T2 = {11, . . . , 25}, and T3 = {26, . . . , 37}. It is clear from the figure that ζ(j, τ ) = j−1 i=0 Ti + τ, ∀ τ ∈ {1, . . . , Tj }, where T0 = 0. . . . . . . . . . . . . 104 5.3 The structure of a time slot of the j th AP. . . . . . . . . . . . . . . . . . . 106 5.4 Total uploaded file size against the penalty parameter b for S = 100 Mbits and ρ = 20 veh/km with a single AP. As b increases, a larger file size is uploaded for the DORA scheme. . . . . . . . . . . . . . . . . . . . . . . . . 124 5.5 Total cost versus traffic density ρ for file size S = 200 Mbits with a single AP. The DORA scheme has the minimal total cost. . . . . . . . . . . . . . 125 5.6 Upload ratio (i.e., total uploaded file size / total payment to the APs) versus traffic density ρ for file size S = 200 Mbits with a single AP. The DORA scheme achieves the highest upload ratio. . . . . . . . . . . . . . . . . . . . 126 5.7 Total cost versus traffic density ρ for file size S = 500 Mbits with five APs. The JDORA scheme with perfect estimation of psucc has the minimal total t cost. Moreover, a higher total cost is required when the precision of the estimation reduces (i.e., when the variance of the estimation θ increases). . 127 5.8 Upload ratio versus traffic density ρ for file size S = 500 Mbits with five APs. achieves the highest The JDORA scheme with perfect estimation of psucc t upload ratio as compared with three other heuristic schemes. Moreover, a lower upload ratio is achieved when the precision of the estimation reduces (i.e., when the variance of the estimation θ increases). . . . . . . . . . . . . 128 5.9 The thresholds s∗t (psucc) of the optimal policy against the decision epoch t for different penalty parameters b. . . . . . . . . . . . . . . . . . . . . . . 129 xv List of Abbreviations AC Access category ACK Acknowledgement AP Access point BS Base station CR Cognitive radio CRN Cognitive radio network CSMA/CA Carrier sense multiple access with collision avoidance DCF Distributed coordination function DORA Dynamic optimal random access DP Dynamic programming DSRC Dedicated short range communications IEEE Institute of Electrical and Electronics Engineers ITS Intelligent transportation system JDORA Joint dynamic optimal random access KKT Karush-Kuhn-Tucker (optimality conditions) MAC Medium access control MS Mobile station NE Nash equilibrium NUM Network utility maximization xvi List of Abbreviations OBU Onboard unit QoS Quality of service RSU Roadside unit SINR Signal-to-interference-plus-noise ratio SNR Signal-to-noise ratio VANET Vehicular ad hoc network VCG Vickrey-Clarke-Groves (mechanism) V2R Vehicle-to-roadside V2V Vehicle-to-vehicle WAVE Wireless access in vehicular environments WLAN Wireless local area network xvii Acknowledgments First and foremost, I wish to express my deep gratitude to my supervisor, Dr. Vincent Wong, for his supervision. His advice and comments have greatly improved the quality of my research. He has provided me with a lot of opportunities to experience different research areas in wireless networking. He has also taught me about technical writing and has helped me improve the presentation of my works. I am particularly grateful to Dr. Robert Schober, Dr. Victor Leung, Dr. Jianwei Huang, Dr. Amir-Hamed Mohsenian-Rad, and Dr. Fen Hou for their collaborations and useful comments that help improve the quality of my research work. I would also like to thank the members of my doctoral committee for their time and effort. I am grateful to the colleagues in my lab: Dr. Joo-Han Song, Dr. Hongbo Guo, Dr. Enrique Stevens-Navarro, Dr. Yuxia Lin, Dr. Vahid Shah-Mansouri, Derrick Wing Kwan Ng, Keivan Ronasi, Pedram Samadi, Binglai Niu, Mani Malekesmaeili, Ehsan Vahedi, Enxin Yao, Bojiang Ma, Chi Sun, Jiaqi Gui, Wei Bao, Xiaolei Hao, Wenbo Shi, Jinbiao Xu, Shaobo Mao, and Suyang Duan. I wish to record my gratitude to my dad, mom, and sister for their love and support when I am studying in Canada. The life as a Ph.D student would be tough and lonely without their care. I hope to thank my friends in my church in Vancouver. They have helped me adapt to a new environment in Vancouver. Their prayers are important to me, especially when the deadlines are approaching. I am also grateful to my friends in my church in Hong Kong xviii Acknowledgments for their prayers and support. Last by not the least, I would like to thank my Lord for accompanying me in my life in Vancouver and every stages of my research. He is “a lamp to my feet and a light for my path” (Psalm 119:105). This work was supported by the AUTO21, a member of the Network of Centres of Excellence of Canada program. xix Chapter 1 Introduction In a wireless network, a medium access control (MAC) protocol is used to coordinate the access of the users to the shared wireless medium. In general, there are two main classes of MAC protocols: scheduling and random access [2]. In a scheduling-based MAC, the transmissions of the users are scheduled orderly in an attempt to prevent packet collisions among the users. On the other hand, in a random access MAC, the users need to contend for the channel for transmission, so packet collisions are likely to occur. However, contentionbased random access protocols are scalable and flexible, and are widely used in wireless networks. In this thesis, we design random access protocols for different types of wireless networks, which includes cognitive radio networks (CRNs), wireless local area networks (WLANs), and vehicular ad hoc networks (VANETs). Mathematical tools, such as optimization theory, game theory, and dynamic programming, are applied in the design and analysis of these protocols. The rest of this chapter is organized as follows. In Section 1.1, we first provide an overview of the wireless network settings that we consider in this thesis. We then introduce the mathematical tools that we use in the thesis in Section 1.2. In Section 1.3, we summarize the main contributions and results in this thesis. Finally, the organization of the thesis is described in Section 1.4. 1 Chapter 1. Introduction 1.1 1.1.1 Random Access in Wireless Networks Cognitive Radio Networks With the licensed radio spectrum being under-utilized [3], cognitive radio (CR) [4, 5] has emerged as the solution to the spectrum scarcity problem. To address the problem of spectrum sharing between the primary (licensed) users and secondary (unlicensed) users, the commons model and the property model [6] have been proposed. In the commons model, the primary users act as if the secondary users are not present. The secondary users access the spectrum holes opportunistically so that they do not cause interference to the primary users. In the property model, the primary users are allowed to trade some of their temporarily unused spectrum to the secondary users in exchange for monetary return. In Chapter 2, we consider the setting where a set of channels from the primary network is available to the secondary CRN, e.g., in the form of dynamic spectrum leasing [7–9] in the property model or by spectrum sensing [10, 11] in the commons model. In order to implement a scalable system that is adaptive to the dynamic network changes in a CRN, a distributed MAC protocol is proposed for the secondary users. The multi-channel signal-to-interference-plus-noise-ratio (SINR) model is consider in the chapter. 1.1.2 Wireless Local Area Networks In a WLAN, an access point (AP) is usually set up to offer connectivity to the users in the network. Due to the network topology and limited transmission range in a WLAN, it is usually reasonable to assume that all the users are one-hop neighbours to each other. We consider a single channel model, where each user randomly attempts to access the shared channel with a certain transmission probability. We consider that the users support applications with both elastic and inelastic traffic [12]. The elastic traffic is generated by 2 Chapter 1. Introduction non-real-time applications such as traditional file transfer and electronic mail. The inelastic traffic is generated by real-time applications including real-time voice and video streaming, which usually have tight quality of service (QoS) requirements. The random access problem is formulated mathematically using the framework of network utility maximization (NUM). In Chapter 3, we model the utilities of the users with elastic traffic using concave functions, and the utilities of the users with inelastic traffic using quasi-concave and step functions. Global optimal solution is obtained for the NUM problem. In Chapter 4, we extend the work in Chapter 3 by considering concave utility functions for elastic traffic sources, and sigmoidal utility functions for inelastic traffic sources. Optimal solution is obtained if a sufficient condition on link capacities is satisfied. Otherwise, an approximate solution with the lower and upper bounds of the objective value are obtained. 1.1.3 Vehicular Ad Hoc Networks The development of intelligent transportation system (ITS) has gained significant momentum in recent years, especially after the Federal Communications Commission (FCC) in the United States allocated 75 MHz licensed spectrum in the 5.9 GHz band in 1999 for this purpose. There are two types of application in an ITS. Safety applications, such as cooperative forward collision warning, lane change warning, and left turn assistant (e.g.,[13, 14]), have been proposed to improve the safety of the passengers by informing the vehicles of potential dangers ahead of time. Non-safety applications, such as traffic management, instant messaging, and media content delivery, have been designed to avoid traffic congestion and improve the experience of driving. Vehicular ad hoc networks, which are designed to provide reliable communications among vehicles and roadside APs, are playing an important role in the development of ITS. VANETs support the ITS applications through different types of communication pat- 3 Chapter 1. Introduction terns, including vehicle-to-roadside (V2R) and vehicle-to-vehicle (V2V) communications [15]. V2R communications involve data transmissions between vehicular nodes and roadside APs, and V2V communications involve data exchange among vehicular nodes only. For both types, we can further classify the communications as either single-hop or multi-hop. Some of the characteristics of VANETs are briefly described as follows: • Rechargeability: Because the power of the vehicles can be recharged easily and readily, power constraint is usually not a prime design issue in VANETs. • Frequent change in network topology: In urban areas, the average speed of the vehicles is around 50 to 60km/h. While in highways, the vehicles move with high average speed of around 80 to 110 km/h. As a result, the network topology changes rapidly. • Variable network density: In urban areas with traffic jams during rush hours, the network density is very high. On the other hand, it can be very low in rural areas. • Non-random trajectory: Because of the fixed road topology, vehicles move in an organized instead of a completely random manner. The position of a vehicle is confined to the road network. Also, the mobility of the vehicles is influenced by human behaviours and some pre-defined traffic rules. • Frequent fragmentation of network: Due to the mobility of the vehicles and the limited transmission ranges of the antenna, a network is frequently segmented in regions where the network density is not too high. As a result, some of the nodes are isolated and are not connected to the network. • Large scale: During the rush hours in urban areas, the number of vehicles involved in a VANET can be very large. 4 Chapter 1. Introduction RSU RSU Figure 1.1: V2V and V2R communications in a VANET. In recent years, the dedicated short range communications (DSRC) was proposed to provide a short to medium range communication service that supports both the safety and non-safety applications in V2R and V2V communication environments. DSRC is meant to be a complement to the cellular communications by providing high data rate in some circumstances while minimizing the latency of the communication links. The wireless access in vehicular environments (WAVE) standard is a core part of DSRC, and it includes the IEEE 802.11p and IEEE 1609.x standards. The IEEE 802.11p standard specifies the physical and MAC layer of the wireless communications, and the IEEE 1609.1, 1609.2, 1609.3, and 1609.4 standards are related to the resource manager, security, networking, and multichannel operations, respectively [16–18]. Since the IEEE 802.11p MAC protocol is a heuristic, we aim to design distributed and optimal uplink random access schemes for VANETs analytically. In Chapter 5, we study random access for V2R single-hop uplink transmissions from the vehicles to the APs in a drive-thru scenario. We propose algorithms for single AP optimization with random vehicular traffic and for joint AP optimization with traffic pattern estimation. 5 Chapter 1. Introduction 1.2 Mathematical Foundation In this thesis, we extensively employed several useful mathematical tools for the design and analysis of the random access protocols, which include the optimization theory, game theory, and dynamic programming. Optimization theory [19–23] is related to the problem of maximization or minimization of a real-valued function by systematically choosing the variables from a feasible set and computing the values of the objective and constraint functions. Game theory [24–27] is a useful technique for studying the interactions among the users with strategic interdependence and characterizing the outcome of the game based on some well-defined solution concepts. Dynamic programming [28, 29] is a set of mathematical and computational tools that is usually applied for the study of sequential decision problems by taking into account both the short-term and long-term consequences of a chosen action. In this section, we provide an overview of each of these three techniques. 1.2.1 Optimization Theory In some problems, we are given a well-defined objective function, some constraints, and some optimization variables. We may want to obtain an optimal or a near-optimal solution of the problem systematically based on some results in optimization theory. Specifically, we consider the following optimization problem minimize f0 (x) x subject to fi (x) ≤ 0, i = 1, . . . , m, (1.1) x ∈ X, where f0 (x) is the objective function, and fi (x) ≤ 0 is the ith constraint. The vector x contains all the optimization variables, and X is its feasible set. 6 Chapter 1. Introduction The Lagrangian function is given by m λi fi (x), L(x, λ) = f0 (x) + (1.2) i=1 where λi is the Lagrange multiplier associated with the ith constraint fi (x) ≤ 0. The Lagrangian dual function is given by g(λ) = inf L(x, λ). (1.3) x∈X The dual problem is maximize g(λ) λ subject to λ (1.4) 0. It should be noted that the dual problem (1.4) is a convex optimization problem. This is the case whether or not the primal problem (1.1) is convex [21, pp. 223]. We assume that g(λ) has a finite value for all λ 0. By applying the Danskin’s Theorem [19, pp. 737], the subdifferential ∂g(λ) (i.e., the set of all subgradients of g(λ)) is given by ∂g(λ) = conv ∇λL(x, λ) : x ∈ x∗ (λ) , (1.5) where ∇λL(x, λ) = ∂L(x, λ) ∂L(x, λ) ,..., ∂λ1 ∂λm T , (1.6) and x∗ (λ) = arg min L(x, λ). (1.7) x∈X conv{H} is the convex hull of set H and the notation (·)T denotes vector transpose operator. 7 Chapter 1. Introduction Since g(λ) is concave, it can be shown that ∂g(λ) is a nonempty, convex, and compact set [19, pp. 732]. Let s(λ) ∈ ∂g(λ) be the subgradient of g at λ. g(λ) is differentiable at λ with gradient s(λ) = ∇g(λ) = ∇λL(x∗ (λ), λ), if and only if there is only one element ∇g(λ) in ∂g(λ) (i.e., ∂g(λ) = {∇g(λ)} is a singleton) [19, pp. 732]. Otherwise, g(λ) is non-differentiable at λ. Using the subgradient projection method (or more specifically, the gradient projection method if g(λ) is a differentiable function), we update λ according to the following equation: λ(t + 1) = λ(t) + α(t)s λ(t) + , (1.8) where t is the index of the iteration, α(t) is the step size, and [z]+ = max{z, 0}. Note that for gradient projection method, s(λ) is an improving feasible direction [23, pp. 590]. However, this may not be true for the subgradient projection method [22, pp. 461]. The convergence of the subgradient projection method is due to the fact that the distance of the current solution λ(t) to the optimal solution λ∗ decreases for sufficiently small step size [22, pp. 462]. To study the convergence of the subgradient projection method, we need to assume that the subgradients are bounded [22, pp. 471]. With the use of diminishing step size α(t) ≥ 0 such that limt→∞ α(t) = 0 and ∞ t=0 α(t) = ∞ (e.g., we can choose α(t) = 1+k , k+t where k is a positive constant [19, pp. 624]), it can be shown that the subgradient projection method can obtain the optimal solution λ∗ of problem (1.4) [22, pp. 478]. However, with the use of fixed step size α(t) = α, it is only guaranteed to converge to within some bounds of the optimal value [22, pp. 473]. For differentiable function g(λ), with the use of fixed step size, it is guaranteed to converge to the optimal solution λ∗ , provided that α is sufficiently small and the gradient satisfies a Lipschitz continuity condition [19, pp. 240]. Let p⋆ and d⋆ be the optimal values of the primal problem (1.1) and the dual problem 8 Chapter 1. Introduction (1.4), respectively. We can establish the lower bound on the optimal value of the primal problem by the weak duality theorem [19, pp. 495]). Theorem 1.1 (Weak Duality Theorem) d⋆ ≤ p⋆ . After we have obtained the optimal solution λ∗ of the dual problem (1.4), we may want to check if we can use λ∗ to obtain the optimal solution of the primal problem (1.1). This is done possible by the following theorem. Theorem 1.2 If g(λ) is differentiable at λ∗ and x∗ is the unique minimum in x of L(x, λ), then (x∗ , λ∗ ) is a saddle point of the primal problem (1.1). Thus, x∗ is the global optimal solution of the primal problem (1.1). The results follow from [20, Property 6.5(c), Theorem 5.3]. Even if we cannot obtain the primal optimal solution from the dual optimal solution, we can still find a good approximate solution to the primal problem based on the dual solution. Consider the following perturbed problem minimize f0 (x) x subject to fi (x) ≤ fi (x∗ λ) , i = 1, . . . , m, (1.9) x ∈ X, where x∗ (λ) is defined in (1.7). Theorem 1.3 For any λ 0, x∗ (λ) is a global optimal solution of the perturbed problem (1.9). The results follow from [20, Property 6.6]. As a result, if the term fi (x∗ λ) is not much larger than zero for all i (i.e., there is only a small violation of the inequality constraints), we may obtain an acceptable practical solution using the dual algorithm [19, pp. 602]. 9 Chapter 1. Introduction 1.2.2 Game Theory In some problems, we need to model the interaction among multiple rational users with strategic interdependence [27] in a wireless network. Game theory is a useful mathematical tool for analyzing the strategic interactions of the players and predicting the final outcome. Here, we introduce two main branches in game theory, namely the non-cooperative game theory and coalitional game theory (also known as cooperative game theory). However, their names may be misleading in that the former does not apply exclusively to situations where the interests of different players conflict (e.g., the result of using cooperative strategies in the prisoner’s dilemma in a repeated game), and the latter does not consider only situations where the interests of players align with each other (e.g., the grand coalition may not be stable in some cases that the players choose not to cooperate as one coalition). In other words, it is possible that the players cooperate in non-cooperative game theory and does not cooperate in coalitional game theory. The essential differences between these two branches lies in the modeling unit, where the modeling unit for the former is an individual player, while that for the latter is a group of players [24]. In addition, we discuss the theory of mechanism design, which the players have private preferences on the available options, and the preferences are not publicly observable. Non-cooperative Game Theory In a non-cooperative game, there are four ingredients that characterize the game [27]: the players, the rules (e.g., the order of the players in making a move), the outcome (i.e., the result after the players have chosen their actions), and the payoff (i.e., the utility function that ranks the preference of a player towards different outcomes). One way of classifications in non-cooperative game theory is to classify the games into two categories: strategic game (also known as static game) or extensive game (also known 10 Chapter 1. Introduction as dynamic game). In a static game, each player chooses his action once and for all, and all the players make their moves simultaneously. Given the assumptions about the preference, rationality, and information available of each player, solution concepts are defined that characterize the possible outcomes of a game. Examples of solution concepts include Nash equilibrium, Pareto optimality, dominant strategy, Bayesian-Nash equilibrium, maxmin strategy, minmax strategy, minimax regret, correlated equilibrium [24–27]. In contrast, in a dynamic game, the events are ordered sequentially that the players may choose their actions at different time instants. The players are interacted sequentially, which the strategy of one player is conditioned on the strategies of the other players. Solution concepts, such as subgame perfect Nash equilibrium and perfect Bayesian-Nash equilibrium, are commonly used in a dynamic game. Coalitional Game Theory Different from noncooperative game theory, coalitional game theory focuses on on what a group or some groups of players can achieve rather than on what individual players can achieve. Formally, a coalitional game G is defined as a pair (N , v), where • N is the set of players or the grand coalition. • v is the value of a coalition S ⊆ N . For a transferable utility (TU) game [24], we have v(S) ∈ R, which is a scalar. Otherwise, for a nontransferable utility (NTU) game, v(S) ∈ R|S| , which is a vector that represents the payoff of each player in coalition S. In fact, there are different categories of coalitional game, which includes the canonical coalitional game and coalition formation game [30]. For the canonical coalitional game, a superadditive game is considered. For a TU game, it is defined as follows: 11 Chapter 1. Introduction Definition 1.1 A coalitional game G is superadditive if v(S1 ∪S2 ) ≥ v(S1 )+v(S2 ), ∀ S1 , S2 ⊂ N with S1 ∩ S2 = φ. It means that the formation of a large coalition by cooperation out of disjoint coalitions achieves at least the sum of the value achieved by the disjoint coalitions individually. Solution concepts, such as the core and the Shapley value, are usually used to analyze the coalitional game. The core is used to analyze the stability of the grand coalition. Because of the superadditivity of the game, the players have an incentive to form the grand coalition N that consists of all the players. The core characterizes if it is possible that a subset of players may opt out of the grand coalition to form a smaller coalition, where the players in the smaller coalition receive higher utilities than when they participate in the grand coalition. The Shapley value is related to fairly dividing the payoff, achieved by the grand coalition, among the players. It is fair in the sense that the division of the payoff among the players is related to the contribution of each player to a coalition. Other useful solution concepts for superadditive game include the nucleolus, the kernel, the bargaining set, and the Nash bargaining solution [24]. For games that are not superadditive, we may consider the problem of coalition formation [30]. We define a coalition structure as a partition of the set of players N into a number of disjoint coalitions. Let the value of a coalition structure be the sum of the values of all the coalitions in the coalition structure. If the game is superadditive, coalition structure generation is trivial because the coalition structure with the largest value is the grand coalition. For the formation of coalitions based on maximizing the value of the coalition structure, the merge-and-split algorithm can be used to find a stable coalition structure [30, 31]. Stability concepts such as Dhp -stability and Dc -stability can be applied to study the stability of the coalition structure after the merge-and-split operations. For the formation of coalitions based on the individual preferences of the players, hedonic coali12 Chapter 1. Introduction tion formation game can be used [30, 32, 33]. We can characterize the stability of the final coalition structure by testing if it is Nash-stable or individually stable. Mechanism Design Theory Mechanism design is a sub-field in microeconomics and game theory that considers how to implement a desirable solutions with self-interested players, each with private information about their preferences [25, 27, 34]. Since the players’ actual preferences are not publicly known, it is important to elicit this information from the rational players so that a socially favourable outcome can be implemented. Famous examples of mechanism design includes the Vickrey-Clarke-Groves (VCG) mechanism and the dAGVA mechanism due to d’Aspremont, Gerard-Varet, and Arrow. There are a number of properties that can be used to characterize the operation of a mechanism. They include incentive compatibility (i.e., whether the players will reveal their true preferences), efficiency (i.e., whether the allocation results in the maximum aggregate utility in the system), budget balance (i.e., whether there is a net transfer of payment from or to the mechanism), and individual rationality (i.e., whether a player has the intention to participate in the system). 1.2.3 Dynamic Programming In some problems, we need to make decisions sequentially, which have both short-term and long-term consequences. In order to achieve the optimal performance, we need to take into account the relationship between the current and future decisions, and that between the current and future outcomes. Dynamic programming is a collection of mathematical and computational tools for analyzing this type of sequential decision problems. Specifically, there are five key ingredients in a sequential decision problem [28]: 1. Decision epoch: t ∈ T , where T represents the set of time points at which decisions 13 Chapter 1. Introduction can be made. Notice that T can be either finite or infinite, and either discrete or continuous. In this chapter, we focus on a discrete-time finite-horizon problem with T = {1, . . . , T }, where T is the total number of decision time points. 2. State: s ∈ S, where S represents the set of states. It summarizes the past information that is relevant for future optimization. 3. Action: a ∈ A, where A represents the set of actions that the decision maker can take. 4. State transition probability: pt (s′ |s, a) represents that the probability that the system will be in state s′ at time t + 1 if action a is taken in state s at time t. 5. Cost: ct (s, a) represents the immediate cost incurred by choosing action a in state s at time t ∈ T . For a discrete-time finite-horizon problem with T = {1, . . . , T }, we define cˆT +1 (s) as the terminal cost when the system is in state s at time t = T + 1 (i.e., after all the decision epochs). Let δt : S → A be the decision rule that specifies the decision at state s at time t ∈ T . We define a policy π = (δt (s), ∀ s ∈ S, t ∈ T ) as a set of decision rules covering all the states at all the time. We denote sπ t as the state at time t if policy π is used, and we let Π be the feasible set of π. The decision maker aims to find an optimal policy that minimizes the total expected cost, which can be formulated as the following optimization problem T min Eπ,S π∈Π π ct sπ ˆT +1 (sπ t , δt (st ) + c T +1 ), (1.10) τ =1 where Eπ,S denotes the expectation with respect to the probability distribution by policy π with an initial state S at time t = 1. Besides the finite-horizon decision problem described 14 Chapter 1. Introduction in this chapter, it is also possible to consider a infinite-horizon problem with discounted cost or average cost [28]. Finite-Horizon Dynamic Programming Let vt (s) be the minimal expected total cost that the decision maker has to pay from time t to time T + 1, given that the system is in state s immediately before the decision at time slot t ∈ T . The optimality equation [28, pp. 83] relating the minimal expected total cost at different states for t ∈ T is vt (s) = min{ψt (s, a)}, a∈A (1.11) where ψt (s, a) = ct (s, a) + s′ ∈S pt s′ | s, a vt+1 (s′ ) (1.12) The first and second terms on the right hand side of the equation above are the immediate cost and the expected future cost in the remaining decision epochs for choosing action a, respectively. For time t = T + 1, we have the boundary condition that vT +1 (s) = cˆT +1 (s). (1.13) By evaluating the optimality equation (1.11) recursively from t = T to t = 1 starting from the boundary condition in (1.13) (i.e., using backward induction [28, pp. 92]), we can obtain the optimal policy π ∗ = (δt∗ (s), ∀ s ∈ S, t ∈ T ), where δt∗ (s) = arg min{ψt (s, a)}. (1.14) a∈A 15 Chapter 1. Introduction The policy π ∗ obtained is the optimal solution of problem (1.10) [29, pp. 18]. In fact, π ∗ is a contingency plan that contains information about the optimal decisions in all possible states s at all time t ∈ T . Threshold Optimal Policy In some special cases, the optimal policy π ∗ may have a threshold structure. Consider an example with an action set A = {a1 , a2 }, where a1 and a2 are distinct actions. The optimal policy is said to have a threshold structure, if for all t ∈ T , we have δt∗ (s) = a1 , if s ≤ s∗ , t (1.15) a2 , otherwise. where s∗t is a control limit. Establishing a threshold policy is appealing, because the decision rule is easier to implement and the computational complexity in obtaining the optimal policy can be reduced significantly [28, pp. 103]. Moreover, memory can be saved, because we do not need to store the decision rules in all states at all time (i.e., δt∗ (s), ∀ s ∈ S, t ∈ T ), but just the set of thresholds (s∗t , ∀ t ∈ T ) in order to characterize the optimal policy π ∗ . In addition, it may provide useful insight into the structure of the problem. To establish a threshold policy, one useful step is to check if the expected total cost ψt (s, a) is supermodular or submodular. Definition 1.2 A function ψt (s, a) is supermodular in S × A if for sˆ, sˇ ∈ S and a ˆ, a ˇ ∈ A, where sˆ ≥ sˇ and a ˆ≥a ˇ, we have ψt (ˆ s, a ˆ) + ψt (ˇ s, a ˇ) ≥ ψt (ˆ s, a ˇ) + ψt (ˇ s, a ˆ). (1.16) If the reverse inequality holds, then ψt (s, a) is submodular. 16 Chapter 1. Introduction If we can establish the supermodularity or submodularity of the function ψt (s, a), we can show directly that the optimal policy π ∗ has a threshold structure by the following theorem: Theorem 1.4 a) If ψt (s, a) is a supermodular function in S × A, then δt∗ (s) is a nonincreasing function in S. b) If ψt (s, a) is a submodular function in S × A, then δt∗ (s) is a nondecreasing function in S. The result follows from [28, pp. 104, 115]. With a threshold structure, we can apply the monotone backward induction [28, pp. 111] with a lower computational complexity to obtain the optimal policy π ∗ . 1.3 Summary of Results and Contributions The thesis covers several analytical MAC design problems in different types of wireless networks, which includes CRNs, WLANs, and VANETs. The results are divided into four chapters. The contributions in each chapter are as follows: • Chapter 2 considers the problem of multi-channel random access in CRNs. While most of the previously proposed MAC protocols for CRNs are heuristic and are based on the simplistic protocol model, we design a distributed MAC protocol using the more accurate SINR model. First, we assume that the secondary users are cooperative and formulate the problem of assigning transmission and listening probabilities for random access as a non-convex NUM problem. We propose a three-phase algorithm that converges to a near-optimal solution after solving a number of convex optimization problems distributively. Simulation results show that our proposed algorithm based on the SINR model achieves a higher aggregate throughput than other schemes which are based on the protocol model. Then, we consider the case that the 17 Chapter 1. Introduction secondary users are rational. We use coalitional game theory to study the incentive issues of user cooperation in a given channel for the SINR model. In particular, we use the solution concept of the core to analyze the stability of the grand coalition, and the solution concept of the Shapley value to fairly divide the payoff among the users. We show that the Shapley value lies in the core when all the users are onehop neighbours of each other. We illustrate the Shapley value and the core with a numerical example. The work in Chapter 2 is published in [35]. • Chapter 3 considers the incentive issues of access category (AC) declaration in a WLAN, where any rational station can strategically declare an AC which is not intended for its application in order to gain an unfair share of the network resources. We first apply game theory to analyze the behaviour of the rational stations. We then propose to use the VCG mechanism to motivate each station to declare truthfully the required AC of its application to the AP. The AP will then inform each station about its transmission probability and the price that the station needs to pay for the offered service. Furthermore, we consider the implementation of the VCG mechanism in a WLAN with both elastic (e.g., file transfer) and inelastic (e.g., real-time video) traffic. By modeling the utilities of mobile stations with concave, step, and quasiconcave utility functions, we show that implementing the VCG mechanism involves solving a non-convex network utility maximization problem optimally. We propose an enumeration algorithm to obtain the global optimal solution by solving a number of convex optimization problems. Simulation results show that a truthful mechanism prevents selfish users from gaining an unfair share of the network bandwidth and supports adequate service differentiation among different ACs. The work in Chapter 3 is published in [36]. • Chapter 4 extends the work of random access in a WLAN with both elastic and 18 Chapter 1. Introduction inelastic traffic in Chapter 3. The utilities of the applications generating elastic and inelastic traffic are modeled by concave and sigmoidal functions, respectively. We formulate a NUM problem, where the optimization variables are the transmission probabilities of the stations. By applying the dual decomposition method, we propose a subgradient algorithm to solve the formulated NUM problem. We also develop closed-form solutions for the dual subproblems involving sigmoidal functions that have to be solved in each iteration of the proposed algorithm. Furthermore, we obtain a sufficient condition on the link capacities which guarantees achieving the global optimal solution when our proposed algorithm is being used. If this condition is not satisfied, then we can still guarantee that the optimal value of the objective function is within some lower and upper bounds. We perform various simulations to validate our analytical models when the available link capacities meet or do not meet the sufficient optimality condition. The work in Chapter 4 is published in [37]. • Chapter 5 considers the problem of random access in a drive-thru scenario, where roadside APs are installed on a highway to provide temporary Internet access for vehicles. We consider V2R communications for a vehicle that aims to upload a file when it is within the APs’ coverage ranges, where both the channel contention level and transmission data rate vary over time. The vehicle will pay a fixed amount each time it tries to access the APs, and will incur a penalty if it cannot finish the file uploading when leaving the APs. First, we consider the problem of finding the optimal transmission policy in an AP with random vehicular traffic arrival. We formulate it as a finite-horizon sequential decision problem, solve it using dynamic programming (DP), and design a general dynamic optimal random access (DORA) algorithm. We determine the conditions under which the optimal transmission policy has a threshold structure. A monotone DORA algorithm with a lower computational 19 Chapter 1. Introduction complexity is proposed for this special case. Next, we consider the problem of finding the optimal transmission policy in multiple APs with deterministic vehicular traffic arrival due to traffic estimation. The optimal transmission policy is obtained using DP and a joint DORA algorithm is proposed. Simulation results based on realistic vehicular traffic model show that our algorithms achieve the minimal total cost and the highest upload ratio as compared with some other heuristic schemes. The work in Chapter 5 is published in [38, 39]. 1.4 Thesis Organization The rest of the thesis is organized as follows. In Chapter 2, we study the multi-channel random access problem using the SINR model, and propose a distributed algorithm to obtain a near-optimal solution. We also study the interactions of the rational users in single channel under the SINR model using coalitional game theory. In Chapter 3, we study the incentive issues of AC declaration of the rational users. We apply the VCG mechanism to motivate the users to declare their ACs truthfully. To implement the VCG-based random access with concave, quasi-concave, and step utility functions, an enumeration algorithm is proposed to obtain the optimal solution of the NUM problem. In Chapter 4, we focus on users with sigmoidal and concave utility functions. A subgradient algorithm based on the dual method is proposed that can obtain the optimal solution if a sufficient condition on link capacities is satisfied. Otherwise, it can be used to obtain a near-optimal solution with the lower and upper bounds of the optimal value of the objective function. Finally, in Chapter 5, we study uplink random access in VANETs. Both the single-AP and multipleAP scenarios are studied, and DORA algorithms that minimizes the total transmission cost in a finite horizon are proposed. Each of the main chapters in this thesis is self-contained and included in separate journal articles or conference papers. A review of the related 20 Chapter 1. Introduction work is given for each chapter accordingly. The notations are defined separately for each chapter. 21 Chapter 2 Multi-channel SINR-based Random Access and Coalitional Game In the throughput analysis of multi-channel MAC protocols in CRNs, such as [40, 41], the protocol model or unit disk model [42] is widely used to account for the effect of multi-user interference due to its simplicity in characterizing the physical layer. Under the protocol model, a transmission is successful if the receiver is within the transmission range of its intended transmitter and outside the interference range of other transmitters. However, in reality, the interference at the receiver is the cumulative power received from other nodes that are concurrently transmitting. As a result, the signal-to-interference-plus-noise-ratio (SINR) model or physical model [42] characterizes the effect of interference more accurately. Under the SINR model, a transmission is successful if and only if the SINR at the intended receiver is above a predefined threshold that depends on the adopted modulation and coding schemes. Despite its higher complexity, the SINR model is getting more attention in recent years due to its higher practicality and accuracy in modeling. Some recent works have investigated contention-based random access protocols [43, 44] and collisionfree scheduling protocols [45, 46] using the SINR model. Since most of the proposed multi-channel MAC protocols for CRNs are heuristic in nature and apply the simplistic protocol model, in this chapter, we propose a distributed random access protocol for CRNs, which is based on the multi-channel SINR model and the mathematical framework of network utility maximization (NUM). In particular, we 22 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game extend the mathematical models in [44] and [47], where the former focused on the singlechannel SINR model, while the latter focused on the multi-channel protocol model. The resulting non-convex optimization problem is more difficult to solve than the problems in [44] and [47]. In particular, our problem involves the dimension of channel selection which was absent in [44], and entails a more accurate and complex interaction among the users due to the SINR model which was absent in [47]. We propose a distributed threephase algorithm using convex optimization and the coordinate ascent method to obtain a near-optimal solution for the non-convex NUM problem. Simulation results show that the proposed scheme based on the SINR model achieves a higher aggregate throughput than other schemes which are based on the protocol model. In the formulation of the NUM problem, we assume that all the secondary users are cooperative. Thus, an interesting question is what happens if the users are rational and they aim to maximize their own utilities? Previous works, such as [48, 49] use non-cooperative game theory to analyze the behaviour of rational users in CRNs. However, this approach is more appropriate for analyzing the behaviour of individual rational users. To analyze what a group of rational users can achieve under the SINR model, where the effect of interference is cumulative, coalitional game theory [24] is a more suitable tool. Coalitional game theory has found many applications in communication networks [10, 30, 50]. In [50], it was applied to study the behaviour of users under the SINR model. However, [50] investigated cooperative communications, whereas we consider random access in CRNs. In summary, the contributions of this chapter are as follows: • We first assume that the secondary users are cooperative. We formulate the problem of random access with multiple channels as a NUM problem using the SINR model, where the optimization variables are the transmission and listening probabilities of the users. 23 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game • We propose a distributed three-phase algorithm using convex optimization and the coordinate ascent method to obtain a near-optimal solution for the non-convex NUM problem. • We then study the case where the secondary users are rational. We formulate the problem as a coalitional game to analyze the interactions among the users under the SINR model. We apply the solution concepts of the core and the Shapley value [24] to characterize the stability and fair allocation of the aggregate utility among the rational users, respectively. We show that the Shapley value lies in the core when all users are one-hop neighbours. • Simulation results show that the proposed scheme based on the SINR model achieves a higher aggregate throughput than other schemes which are based on the protocol model. A numerical example is given to illustrate both the Shapley value and the core. The rest of this chapter is organized as follows. We present the related work in Section 2.1. The system model is described in Section 2.2. We formulate the random access problem in Section 2.3 and present our distributed algorithm in Section 2.4. The coalitional game is discussed in Section 2.5 and simulation results are presented in Section 2.6. A summary is given in Section 2.7. 2.1 Related Work Several multi-channel MAC protocols have been proposed for CRNs. In [51], Cordeiro et al. proposed a distributed cognitive MAC protocol that includes a slotted beaconing period for nodes to negotiate on the channel usage. A rendezvous channel is used to coordinate nodes tuned to different channels. Su et al. proposed in [40] two sensing policies for 24 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game q1(1) Data Channel 1 q1(2) Data Channel 2 User 1 Primary BS User 2 q2(1) q2(2) p2(1) p1(1) p1(2) q3(1) q3(2) User 3 p3(1) p2(2) p3(2) Figure 2.1: A CRN with set of users N = {1, 2, 3}, where the triangles and circles represent the transmitters and receivers, respectively. The set of available orthogonal data channels (c) (c) C = {1, 2} is provided by the primary BS. pi and qi denote the transmission and listening probabilities for user i in channel c, respectively. the physical layer and a packet scheduling algorithm for the MAC layer of a distributed CRN. Queueing theory was used to evaluate the throughput and delay in saturated and non-saturated networks under the proposed sensing policies. Jia et al. proposed in [52] a hardware-constrained cognitive MAC protocol that coordinates the contention and spectrum usage among the secondary users. Practical constraints related to hardware, sensing, and transmission were considered. Timmers et al. proposed in [41] an energy-efficient distributed multi-channel MAC protocol for a multi-hop CRN, which is based on the timing structure of the power-saving mode used in the IEEE 802.11 standard. 2.2 System Model As shown in Fig. 2.1, we consider a CRN with several secondary nodes located in a neighbourhood, where a set of orthogonal data channels C and one control channel are obtained from the primary base station (BS), e.g, in the form of spectrum leasing. The data channels are used for data transmissions, and the control channel is used for the exchange of control messages. The total number of data channels is C = |C|. We consider only 25 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game single-hop transmissions between the secondary nodes. We define N as the set of one-hop transmitter/receiver pairs or links in the CRN, and we refer to each transmitter/receiver pair as a user. The total number of users is N = |N |. We adopt a slotted MAC protocol, where time is divided into equal time slots. The users attempt to access the shared channel at the beginning of each time slot according to their transmission probabilities in each channel. That is, each user i ∈ N can access a channel c with a certain transmission (c) (c) probability pi , and we define a vector p = (pi , ∀ i ∈ N , c ∈ C). Also, we introduce (c) (c) a vector q = (qi , ∀ i ∈ N , c ∈ C), where qi is the listening probability of receiver i in channel c. We have the following constraints: (c) c∈C pi ≤ 1 and (c) c∈C qi ≤ 1, ∀ i ∈ N . (2.1) For the SINR model, if user i ∈ N chooses to transmit in channel c ∈ C, then the SINR at receiver i is given by (c) (c) θi = Pi Gii (c) (c) ιi + ni , (2.2) (c) where Pi is the transmit power of user i. Gij is the channel gain from the transmitter of (c) user i to the receiver of user j in channel c. ιi (c) and ni are the interference and noise powers received by user i in channel c, respectively. Given that receiver i has tuned to channel c for reception, the communication of user i is successful if (c) (c) (c) θi ≥ θith ⇔ ιi ≤ Pi Gii (c) − ni , θith (2.3) where θith is the SINR threshold. Let Ni be the power set (i.e., the set of all subsets) of N \{i}. As an example, for N = {1, 2, 3}, N2 = {{}, {1}, {3}, {1, 3}}. Assuming that the (c) transmit powers (Pi , ∀ i ∈ N ) are fixed, we define Mi as a set where each element is a set of users that can transmit simultaneously with user i without affecting the reception 26 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game (c) of receiver i in channel c (i.e., θith can be achieved). The set Mi obtained with the SINR model is given by (c) (c) Mi,SIN R (c) Pm Gmi = M ∈ Ni : m∈M Pi Gii (c) − ni . ≤ th θi (2.4) If the protocol model is used, only pairwise interference is considered. User m is an interferer or one-hop neighbour to user i if the SINR due to the interference from user m only is below the SINR threshold. That is, (c) Pi Gii (c) Pm Gmi + (c) ni < θith . (2.5) (c) The set Mi obtained with the protocol model is given by (c) (c) Mi,P T C = M ∈ Ni : (c) Pm Gmi Pi Gii (c) ≤ − ni , ∀ m ∈ M . th θi (2.6) Intuitively, more users are allowed to transmit simultaneously in the protocol model than in the SINR model. This is confirmed by the following lemma. (c) (c) Lemma 2.1 Mi,SIN R ⊆ Mi,P T C . Proof : Observing the fact that (c) Pi Gii θith (c) (c) m∈M Pm Gmi ≤ (c) Pi Gii θith (c) − ni (c) (c) in (2.4) implies Pm Gmi ≤ (c) − ni , ∀ m ∈ M in (2.6), it follows directly that Mi,SIN R ⊆ Mi,P T C . Example 2.1 We consider Fig. 2.1 where the transmit powers of all users are the same. Assuming that all users have selected channel 1, at a certain transmit power level P , we can observe the following: Since transmitter 1 is close to receivers 2 and 3, user 1 interferes with users 2 and 3. However, since transmitters 2 and 3 are far away from receiver 1, users 2 and 3 do not interfere with user 1 as long as they do not transmit 27 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game simultaneously. Users 2 and 3 are far from each other and do not interfere with each other. (1) (1) For the protocol model, we have M1,P T C = {{}, {2}, {3}, {2, 3}}, M2,P T C = {{}, {3}}, and (1) M3,P T C = {{}, {2}}. However, the protocol model does not take into account that user 1 may be interfered when both users 2 and 3 transmit simultaneously. In this case, we have (1) (1) (1) (1) (1) (1) M1,SIN R = {{}, {2}, {3}} ⊂ M1,P T C , M2,SIN R = M2,P T C , and M3,SIN R = M3,P T C . The probability of successful transmission of user i in channel c is given by succ,(c) pi (c) (c) (c) M∈Mi (c) (c) pm = pi qi (1 − pk ) . m∈M (2.7) k∈N \M,k=i (c) We define Mi = Mi , ∀ c ∈ C . The average data rate of user i is given by (c) succ,(c) ri (p, qi , Mi) = µ i pi , (2.8) c∈C (c) where µi (c) is the peak data rate for user i in channel c, and vector qi = qi , ∀ c ∈ C contains the listening probabilities of receiver i in all the channels. Given p and qi , we have the following lemma, which states that the average data rate ri is over-estimated when the protocol model is used. Lemma 2.2 ri (p, qi , Mi,P T C ) ≥ ri (p, qi , Mi,SIN R). Proof : From (2.8) and Lemma 2.1, we have (c) (c) (c) ri (p, qi , Mi,P T C ) = ri (p, qi , Mi,SIN R) + µi pi qi c∈C × (c) pm (c) (c) M∈Mi,P T C \Mi,SINR ≥ ri (p, qi , Mi,SIN R), m∈M (c) (1 − pk ) (2.9) k∈N \M,k=i (2.10) 28 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game which completes the proof. (c) For the rest of this chapter, we assume that sets Mi in (2.4) and (2.6) are given, so we write ri (p, qi , Mi) as ri (p, qi) for simplicity. 2.3 Network Utility Maximization We now formulate the multi-channel random access problem as a NUM problem with vectors p and q as the optimization variables. The NUM problem is given by maximize p, q Ui ri (p, qi) i∈N (c) subject to c∈C (c) (2.11) (c) pi ≤ 1, c∈C qi ≤ 1, ∀ i ∈ N , (c) 0 ≤ pi , qi ≤ 1, ∀ i ∈ N , c ∈ C, where Ui ri (p, qi) is a concave and non-decreasing function in ri (p, qi ). However, due to the product form of the variables in (2.7), problem (2.11) is non-convex, even if the utility functions are concave. As a result, the problem is difficult to solve in general. An example of a concave utility function useful for resource allocation is the α-fair function [53] defined as Ui (ri ) = (1 − αi )−1 ri1−αi , if αi ∈ [0, 1) ∪ (1, ∞), ln ri , if αi = 1, (c) Intuitively, ri increases when pi (c) increases or when pj ∀i ∈ N. (2.12) decreases, j = i. This is confirmed by the following lemma: (c) Lemma 2.3 For i ∈ N , we have: (a) ri (p, qi) is a non-decreasing function of pi , ∀ c ∈ C. (c) (b) ri (p, qi ) is a non-increasing function of pj , ∀ j ∈ N \{i}, c ∈ C. 29 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game Proof : (a) From (2.8), ri can be written in the form ri (p, qi ) = (c) (c) (c) xi = µi qi (c) M∈Mi (c) m∈M (c) (c) c∈C (c) (c) pm xi pi , where (1 − pk ) . k∈N \M,k=i (2.13) (c) (c) Since xi ≥ 0 and it is independent of pi , ri (p, qi) is a non-decreasing function of pi , ∀ c ∈ C. (b) Let j ∈ N \{i} be given. We first define two sets of users that exclude users i and j: and (c) S˜i,j = S : S ∈ N \{i, j}, S ∈ Mi , S ∪ {j} ∈ Mi (c) (c) (c) Sˆi,j = / Mi S : S ∈ N \{i, j}, S ∈ Mi , S ∪ {j} ∈ (c) (c) (2.14) . (2.15) From (2.8), we can write ri as (c) (c) (c) ri (p, qi ) = c∈C (c) ps(c) µi pi qi (c) S∈S˜i,j s∈S k∈N \S,k=i,j (c) ps(c) (c) S∈Sˆi,j s∈S (1 − pk ) + k∈N \S,k=i,j (c) (1 − pk ) (1 − pj ) , (2.16) (c) which is a non-increasing function of pj , ∀ c ∈ C. Although it is possible that the users may occupy more than one channel at an optimal solution, we can show based on Lemma 2.3 that we can always find another optimal solution where each user occupies only one channel. 30 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game Theorem 2.1 A global optimal solution of problem (2.11), (p∗ , q ∗ ), is in the form: ∈ [0, 1], if c = ci , (c)∗ pi = 0, (c)∗ and qi = 1, if c = ci , (2.17) 0, otherwise, otherwise, where ci is the channel chosen by user i. Proof : Assume that (p, q) is feasible in problem (2.11), but p and q are not in the form of (2.17). From (2.8), we have (c) ri (p, qi ) = (c) si (p)qi , (2.18) c∈C where (c) (c) (c) (c) (c) pm si (p) = µi pi m∈M (c) M∈Mi (1 − pk ) . (2.19) k∈N \M,k=i We define (c) ci = arg max si (p), ∀ i ∈ N , c∈C (c)∗ and qi∗ = (qi (2.20) , ∀ i ∈ N , c ∈ C), where (c)∗ qi We have (c) ri (p, qi ) = c∈C = 1, if c = ci , (2.21) 0, otherwise. (c) (c ) si (p)qi ≤ si i (p) = ri (p, qi∗ ), ∀ i ∈ N , (2.22) where the inequality in the middle is due to the definition of ci in (2.20) and the fact that 31 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game (c)∗ c∈C qi ≤ 1. Since Ui (ri ) is a non-decreasing function in ri , ∀ i ∈ N , we have i∈N Ui ri (p, qi ) ≤ Ui ri (p, qi∗ ) . (2.23) i∈N Given q ∗ , we have (c ) (ci ) ri (p, qi∗) = µi i pi m∈M (c ) M∈Mi i (c ) (1 − pk i ) . (ci ) pm k∈N \M,k=i (2.24) Since p is not in the form as shown on the left hand side of (2.17), there exists c = ci (c) (c)∗ such that pi > 0. We define p∗ = (pi (c)∗ pi = , ∀ i ∈ N , c ∈ C), where pi(c) , if c = ci , 0, (2.25) otherwise. (c) Notice that ri in (2.24) is independent of pi for c = ci , and it is a non-increasing function (c) of pj , ∀ j ∈ N \{i}, c ∈ C as shown in Lemma 2.3(b). Thus, we have ri (p, qi∗ ) ≤ ri (p∗ , qi∗ ), ∀ i ∈ N . (2.26) Since Ui (ri ) is a non-decreasing function in ri , ∀ i ∈ N , we have i∈N Ui ri (p, qi∗ ) ≤ Ui ri (p∗ , qi∗ ) . (2.27) i∈N Combining (2.23) and (2.27), we have i∈N Ui ri (p, qi) ≤ i∈N Ui ri (p, qi∗) ≤ Ui ri (p∗ , qi∗ ) . (2.28) i∈N 32 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game To sum up, given any feasible point (p, q), we can always find another feasible point (p∗ , q ∗) in the form of (2.25) and (2.21), which yields an objective value that is not smaller than that for (p, q) and each user occupies only one channel. The result thus follows. 2.4 Three-Phase Distributed Algorithm using Sequential Convex Optimization In this section, our goal is to solve non-convex NUM problem (2.11). We propose a lowcomplexity three-phase algorithm where the transmitters and receivers have to solve a number of convex optimization problems distributively. Convergence of the solution is guaranteed. 2.4.1 Transmission Probability Optimization (c) We define the vector pi = (pi , ∀ c ∈ C). Transmitter i ∈ N needs to solve the following local optimization problem, which has the same objective function as problem (2.11): (c) (c) maximize Ui pi oi pi c∈C subject to pi ≤ 1, c∈C (c) (2.29) (c) (c) (c) oi = µi qi (c) M∈Mi (c) (c) 0 ≤ pi ≤ 1, ∀ c ∈ C, where (c) (c) (c) vji pi + wji 1 − pi Uj j∈N \{i} (c) c∈C + m∈M (c) pm (c) (c) (c) (c) k∈N \M,k=i 1 − pk (c) M∈Mj : i∈M m∈M\{i} , (c) (c) pm vji = µj pj qj k∈N \M,k=j 1 − pk (2.30) , (2.31) 33 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game and (c) (c) (c) (c) wji = µj pj qj (c) M∈Mj : i∈M / (c) (c) m∈M (c) (c) pm k∈N \M,k=j,i 1 − pk . (2.32) (c) The coefficients oi , vji , and wji should be computed by transmitter i based on the broadcast messages from other transmitters and receivers. Theorem 2.2 Problem (2.29) is a convex optimization problem in pi . (c) (c) (c) Proof : First, the constraints in problem (2.29) are linear. Also, as oi , vji , and wji (c) are independent of pi , and since the arguments within the utility functions are linear in pi , the objective function is concave in pi [21, pp. 79]. Thus, problem (2.29) is a convex optimization problem. Hence, we can solve problem (2.29) by using the interior point method [21]. 2.4.2 Listening Probability Optimization Receiver i ∈ N needs to solve the following local optimization problem with the same objective function as problem (2.11). (c) (c) maximize Ui qi ai qi c∈C c∈C qi ≤ 1, where (c) (c) (c) ai = µi pi (c) M∈Mi Uj (rj (p, qj )) (2.33) j∈N \{i} (c) subject to + m∈M (c) 0 ≤ qi ≤ 1, ∀ c ∈ C, (c) pm (c) (1 − pk ) . k∈N \M,k=i (2.34) 34 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game (c) Theorem 2.3 Let ci = arg maxc∈C ai . A closed-form solution of problem (2.33) is (c)∗ qi = (2.35) 0, otherwise. (c) Proof : First, notice that ai and 1, if c = ci , j∈N \{i} (c) Uj (rj (p, qj )) are independent of qi . Since Ui is a non-decreasing function, problem (2.33) is equivalent to the following linear programming problem (c) (c) ai qi maximize qi c∈C (2.36) (c) subject to c∈C qi ≤ 1, (c) 0 ≤ qi ≤ 1, ∀ c ∈ C, the solution of which is given by (2.35). 2.4.3 Three-Phase Distributed Algorithm Having introduced the local optimization problems for the transmitter and receiver of user i ∈ N , we are now ready to present Algorithm 2.1 for obtaining a near-optimal solution of problem (2.11) based on the coordinate ascent method [54, pp. 207]. Let p−i = (p1 , . . . , pi−1 , pi+1 , . . . , pN ) and q−i = (q1 , . . . , qi−1 , qi+1 , . . . , qN ). Considering transmitter i, the basic idea of this method is that we fix p−i and q, and maximize the aggregate utility i∈N Ui ri (p, qi ) with respect to pi (i.e., problem (2.29)). Similarly, for receiver i, we fix p and q−i , and maximize the aggregate utility i∈N Ui ri (p, qi ) with respect to qi (i.e., problem (2.33)). The updates of the solutions are carried out successively. Notice that the solution of problem (2.33) as stated in Theorem 2.3 represents a channel selection. Once the channel is selected by the receiver, the transmitter will not attempt to transmit in other channels, to which the receiver is not listening. As a result, the receivers should 35 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game defer their decisions of selecting a channel until after the transmitters have coordinated their transmission probabilities. With this idea, we propose our Algorithm 2.1 with three phases. In phase I, the receivers are initialized to listen to each channel with a certain probability. The transmitters then probe the channels by adjusting their transmission probabilities until the aggregate utility converges. In phase II, each transmitter/receiver pair selects the channel that results in the highest average data rate. The reason for choosing only one channel is given by Theorem 2.1. In phase III, based on this channel selection, the transmitters adjust their transmission probabilities again until the aggregate utility converges. After the execution of Algorithm 2.1, the transmitters and receivers can proceed to transmit in and listen to the data channels according to p∗ and q ∗ , respectively. In other words, in the control stage, Algorithm 2.1 is executed to determine p∗ and q ∗ . In the transmission stage, data transmissions take place based on p∗ and q ∗ . In Algorithm 2.1, Ti is the set of time slots in which user i ∈ N solves the local optimization problem in the control stage. Also, we use variable u to keep track of the aggregate utility achieved in the previous iteration, and we let u∗ (t) be the aggregate utility achieved in iteration t. The algorithm transitions from phase I to phase II and from phase III to the exit if the difference ∆ = u∗ (t) − u is less than the predefined convergence threshold ǫ. The complexity of Algorithm 2.1 is relatively low because it involves solving only convex problem (2.29) and evaluating closed-form equation (2.35). Thus, it is reasonable to assume that users in CRNs have the computational capabilities to perform these mathematical operations. 36 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game Algorithm 2.1 Three-Phase Distributed Algorithm to Obtain a Near-optimal Solution for Problem (2.11). 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: (c)∗ (c)∗ Initialize p∗ such that c∈C pi ≤ 1, ∀ i ∈ N , and 0 ≤ pi ≤ 1, ∀ i ∈ N , c ∈ C (c)∗ (c)∗ Initialize q ∗ such that c∈C qi ≤ 1, ∀ i ∈ N , and 0 ≤ qi ≤ 1, ∀ i ∈ N , c ∈ C Set the convergence threshold ǫ > 0 Set the iteration counter t := 1 Set u := −∞ and ∆ := ∞ Phase I: Channel Probing while ∆ > ǫ for each transmitter i ∈ N If t ∈ Ti then (c) Calculate oi , ∀ c ∈ C using (2.30) (c) Calculate vji , ∀ j ∈ N \{i}, c ∈ C using (2.31) (c) Calculate wji , ∀ j ∈ N \{i}, c ∈ C using (2.32) Solve problem (2.29) to obtain the solution p∗i Broadcast p∗i to other users using the control channel Set u∗ (t) := i∈N Ui ri (p∗ , qi∗ ) Set t := t + 1 end if end for Set ∆ := u∗ (t) − u and u := u∗ (t) end while Phase II: Channel Selection for each receiver i ∈ N If t ∈ Ti then (c) Calculate ai , ∀ c ∈ C using (2.34) (c) Set ci := arg maxc∈C ai (c)∗ Set qi , ∀ c ∈ C using (2.35) Broadcast qi∗ to other users using the control channel (c)∗ Set pi := 0, if c = ci , ∀ c ∈ C Set u∗ (t) := i∈N Ui ri (p∗ , qi∗ ) Set t := t + 1 end if end for Phase III: Transmission Probability Allocation Set ∆ := ∞ Repeat Lines 7 to 20 once For the message exchanges, after solving for the corresponding local optimization prob- 37 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game lems, transmitter i and receiver i need to broadcast the solutions p∗i and qi∗ in (2.29) and (2.35) using the control channel, respectively. Thus, the signalling overhead grows linearly with the number of users N in the system. The exchange of p∗i and qi∗ can be achieved by using broadcast protocols, such as limited-scope message flooding [55]. However, it should be noted that interference also affects these message exchanges. For the case with a high level of interference in the CRN, broadcast protocols with high reliability can be considered, such as [56]. Alternatively, the transmitters or receivers that cannot receive the control messages correctly are not required to solve their corresponding local optimization problems. In our system model, since the secondary nodes are located in a neighbourhood, the broadcast of each control message to the whole CRN can be completed in a few hops. In this way, the duration of a time slot in the control stage should take into account both the amount of time required for solving a local optimization problem and for broadcasting a control message to all the secondary nodes in the CRN. We have the following theorem that shows the convergence of Algorithm 2.1. Notice that even in a centralized setting, there is no guarantee that we can obtain the globally optimal solution of problem (2.11) due to its non-convexity. Theorem 2.4 The aggregate utility u∗ (t) converges to a fixed point u∗ . That is, limt→∞ u∗ (t) = u∗ . Moreover, u∗ (t) is a non-decreasing sequence in t. That is, u∗ (t) ≤ u∗ (t + 1) for all t ≥ 0. Proof : In both phases I and III, because we fix p∗−i and q ∗ to solve problem (2.29) for p∗i , and update the solution of transmission probabilities p∗ in the Gauss-Seidel manner [54, pp. 185], we can show by [54, Proposition 3.9, pp. 219] that u∗ (t) converges to a fixed point. In each iteration t, since we are maximizing the objective function i∈N Ui ri (p∗ , qi∗) over some variables, while the other variables are fixed, we must have u∗ (t) ≤ u∗ (t + 1) for all t ≥ 0. 38 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game 2.5 Coalitional Game Theory for SINR Model In the previous section, we have assumed that all the secondary nodes cooperate to maximize the aggregate utility. This gives rise to the question of what happens if the users are rational and aim to maximize their own utilities. In fact, if user i is rational and there is no coordination among the users, user i may choose to transmit in a particular channel ci by (ci ) setting pi (ci ) = qi (c) (c) = 1 and pi = qi = 0 for c = ci in order to maximize Ui as suggested by the proof of Theorem 2.1. Hence, a significant amount of interference will be generated. In the worst case (e.g., when the number of channels C is small), it is possible that the utilities of all the users will be zero. To prevent this problem, the users may coordinate among themselves in the form of a coalition. The users belonging to the same coalition coordinate their transmission and listening probabilities to maximize the aggregate utility, which is then divided among themselves. Example 2.2 We continue with Example 2.1, and assume that the three users have selected channel 1 and transmit with power P . We assume that their peak data rates are µ1 = 5, µ2 = 2, and µ3 = 1. If all the users are willing to coordinate their transmission probabilities p, the optimal transmission probabilities based on throughput maximization (i.e., α = 0 in problem (2.11)) for both the SINR and protocol models are given by p∗1 = 1, p∗2 = 0, and p∗3 = 0. From (2.12), the corresponding utilities are U1 = 5 and U2 = U3 = 0. However, if users 2 and 3 are rational, they may not be satisfied with zero utility. For the protocol model, users 2 and 3 have no bargaining power with user 1 to increase their utilities. On the other hand, the SINR model reveals that users 2 and 3 can threaten user 1 to transmit simultaneously and jam user 1’s transmission. This effect is not captured by the protocol model. In the following, we apply coalitional game theory to study the incentives of rational user cooperation and the payoff distribution among the users. We note that coalitions can also be formed in the protocol model. However, in this case, the significance 39 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game of the formation of coalitions may be undermined by the fact that the protocol model does not capture the cumulative effect of interference. 2.5.1 Coalitional Game Since the channels are orthogonal, we focus on one particular channel, and refer to the set of users that have selected that channel by N for notational simplicity. In this case, the average data rate of user i in (2.8) can be simplified to ri (p) = µipi pm M∈Mi m∈M (1 − pk ) , (2.37) k∈N \M,k=i where we drop the superscript for channel c and the term for the listening probability. We further restrict our attention to non-decreasing concave utility functions Ui (ri ), where Ui (0) = 0. We define the coalitional game G with transferable utility [24] as a pair (N , v), where N is the set of players or the grand coalition, and v : 2N → R is the value of a coalition S ⊆ N that the members of the coalition can distribute among themselves. In our problem, this value is defined as v(S) = maximize p Ui ri (p) i∈S subject to 0 ≤ pi ≤ 1, pj = 1, That is, v(S) = i∈S ∀ i ∈ S, (2.38) ∀ j ∈ N \S. Ui ri (p∗ (S)) , where p∗ (S) is the optimal solution of problem (2.38). The users within coalition S coordinate among themselves to maximize the aggregate utility, subject to the worst-case interference from users j ∈ N \S when they choose transmission probabilities pj = 1. All users in set N \S are not coordinating with the users 40 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game within coalition S. Instead, each user j ∈ N \S transmits with pj = 1 in order to maximize its own utility, because Uj (rj (p)) is a non-decreasing function in pj from Lemma 2.3(a). v(S) can be obtained from Algorithm 2.1 with a few minor changes: Choose C = 1. Run line 13 if i ∈ S, but replace it with “Set p∗i := 1” if i ∈ N \S. It should be noted that game G is a one-shot game. Also, we assume that the communication overhead is negligible when a coalition is formed. The property of superadditivity [24] is often observed in coalitional games, including game G. It is defined as follows: Definition 2.1 A game is superadditive if v(S1 ∪ S2 ) ≥ v(S1 ) + v(S2 ), ∀ S1 , S2 ⊂ N with S1 ∩ S2 = φ. Theorem 2.5 Game G is superadditive. Proof : Let p∗ (S1 ), p∗ (S2 ), and p∗ (S1 ∪ S2 ) be the optimal probabilities maximizing v(S1 ), v(S2 ), and v(S1 ∪ S2 ), respectively, as defined in (2.38). For S1 ∩ S2 = φ, we construct a vector p(S1 ∪ S2 ), where the ith element is pi (S1 ∪ S2 ) p∗ (S1 ), if i ∈ S1 , i p∗i (S2 ), if i ∈ S2 , 1, otherwise. (2.39) So p(S1 ∪ S2 ) is feasible in problem (2.38) with S = S1 ∪ S2 . From (2.38), we have p∗i (S1 ) = 1 if i ∈ N \S1 . Thus, we have = pi (S1 ∪ S2 ), if i ∈ S1 , ∗ pi (S1 ) ≥ pi (S1 ∪ S2 ), if i ∈ N \S1 . (2.40) 41 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game From Lemma 2.3(b), we have ri (p∗ (S1 )) ≤ ri (p(S1 ∪ S2 )), ∀ i ∈ S1 . (2.41) Since Ui is a non-decreasing function of ri , we have Ui ri (p∗ (S1 )) ≤ Ui ri (p(S1 ∪ S2 )) , ∀ i ∈ S1 , (2.42) which implies that i∈S1 Ui ri (p∗ (S1 )) ≤ i∈S1 Ui ri (p(S1 ∪ S2 )) . (2.43) Ui ri (p(S1 ∪ S2 )) . (2.44) Similarly, we have i∈S2 Ui ri (p∗ (S2 )) ≤ i∈S2 Overall, we have Ui ri (p∗ (S1 )) + i∈S1 ≤ i∈S1 ∪S2 Ui ri (p∗ (S2 )) i∈S2 Ui ri (p(S1 ∪ S2 )) ≤ i∈S1 ∪S2 Ui ri (p∗ (S1 ∪ S2 )) , (2.45) which concludes the proof. 2.5.2 The Core To determine the stability of the grand coalition, we use the solution concept of the core [24]. It is possible that a subset of users may opt out of the grand coalition to form a smaller coalition, if the users in the smaller coalition receive higher utilities than when 42 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game they participate in the grand coalition. In that case, the core is empty. The core is formally defined as follows: Definition 2.2 The core is the set of feasible utility allocation vectors U = (Ui , ∀ i ∈ N ) where Ucore = U : Ui ≥ v(S), ∀ S ⊂ N . Ui = v(N ), i∈N i∈S (2.46) In some special cases, it can be shown that the core is non-empty. One such special case is when all the users are one-hop neighbours to each other (i.e., user i is a one-hop neighbour to user j, ∀ i, j ∈ N , i = j, where one-hop neighbour is defined in (2.5)). In this case, since Mi,SIN R and Mi,P T C are null sets ∀ i ∈ N from (2.4) and (2.6), the SINR model is identical to the protocol model. So, the average data rate of user i in (2.37) can further be simplified as ri (p) = µi pi (1 − pj ). (2.47) j∈N \{i} Theorem 2.6 If all the users are one-hop neighbours to each other, then the core is nonempty. Proof : Since pj = 1, ∀ j ∈ N \S from (2.38), we have ri = 0, ∀ i ∈ S ⊂ N from (2.47) if all the users are one-hop neighbours to each other, which implies that v(S) = 0, ∀ S ⊂ N . Notice that any vector U = (Ui , ∀ i ∈ N : i∈S i∈N Ui = v(N ), Ui ≥ 0, ∀ i ∈ N ) satisfies Ui ≥ v(S) = 0, ∀ S ⊂ N . So U ∈ Ucore , and the core is thus non-empty. 2.5.3 Shapley Value As a solution concept, the core has a few drawbacks. It can be empty and the allocation of payoff according to the core may be unfair. In Example 2.2, with the use of the SINR model, we can show that v({1, 2}) = v({1, 3}) = v({1, 2, 3}) = 5 using (2.38). The only 43 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game allocation of utilities that lies in the core is U1 = 5, U2 = U3 = 0. This allocation is stable since no smaller coalitions can be formed where the members can receiver a higher payoff than when they are in the grand coalition. However, it is unfair in the division of the payoff among the users as it does not take into account the contribution of each user to a coalition. In the following, we propose to use the Shapley value [24] to fairly divide the payoff among the players. Let the total number of users in coalition S be S = |S|. Definition 2.3 The Shapley value is the payoff allocation vector φ(v) = φ1 (v), . . . , φN (v) , where φi (v) = S⊆N \{i} S!(N − S − 1)! v(S ∪ {i}) − v(S) . N! (2.48) In fact, φi (v) represents the expected marginal contribution of user i to different coalitions S without user i. we have i∈N The Shapley value has a number of nice properties. First, φi (v) = v(N ). Moreover, it is fair in the sense that users who make the same contribution to different coalitions receive the same payoff. Mathematically, if v(S ∪{i}) = v(S ∪{j}), ∀ S ∈ N \{i, j}, then φi (v) = φj (v). As we have discussed in Example 2.2, with the use of the SINR model, users 2 and 3 can threaten to leave the coalition to jointly jam user 1’s transmission. The Shapley value in this case is φ(v) = (3.33, 0.83, 0.83) and both users 2 and 3 receive positive utilities. It is worth mentioning that since users 2 and 3 have no bargaining power in the protocol model, we can show that the Shapley value in this case is φ(v) = (5, 0, 0) and both users 2 and 3 receive zero utility. In general, the Shapley value is not directly related to the core. However, the Shapley value lies in the core in some special cases, including the case where all the users are one-hop neighbours to each other for our problem. Theorem 2.7 If all the users are one-hop neighbours to each other, then (a) φi (v) = v(N ) ,∀i N ∈ N , and (b) φ(v) ∈ Ucore . 44 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game 0 −0.2 Aggregate Utility −0.4 −0.6 −0.8 −1 −1.2 −1.4 −1.6 Exhaustive Search Three−Phase Distributed Algorithm −1.8 −2 0 5 10 15 20 25 30 Scenario Index Figure 2.2: Aggregate utility obtained using an exhaustive search and the three-phase distributed algorithm (i.e., Algorithm 2.1) based on the multi-channel SINR model. We can see that Algorithm 2.1 achieves a near-optimal solution. Proof : (a) If all the users are one-hop neighbours to each other, we have v(S) = 0, ∀ S ⊂ N , from the proof of Theorem 2.6. From (2.48), notice that the only non-zero term in the summation is given by S = N \{i}. Therefore, we have φi (v) = v(N \{i})] = (N −1)!(N −(N −1)−1)! [v(N ) N! − v(N ) . N (b) From part (a), we have i∈N φi (v) = v(N ). Also, i∈S φi (v) = Sv(N )/N > 0 = v(S), ∀ S ⊂ N . From (2.46), we know that φ(v) ∈ Ucore . Thus, in this case, the payoff allocation vector φ(v), which distributes the total payoff equally among the users, is in the core. Empirical investigations regarding the core and the Shapley value in the general setting, where not all the users are one-hop neighbours, are provided in the next section. 45 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game 2.6 Performance Evaluations In this section, we evaluate the performances of Algorithm 2.1 for the SINR and protocol models, and compare with that of a heuristic scheme. We also illustrate the significance of the core and the Shapley value. Unless specified otherwise, we assume that the secondary nodes are randomly placed in a 50 m × 50 m area. The peak data rate of a user is randomly selected to be between 1 Mbps and 10 Mbps. For simplicity, we do not take into account (c) the effect of fading and model the channel gain as Gi,j = 1/dγi,j , where di,j is the distance between the transmitter of user i and the receiver of user j, and γ is the path loss exponent. We adopt γ = 2. When the effect of channel fading is considered, Algorithm 2.1 is still (c) applicable. In this case, after estimating the channel gain Gi,j in every coherence interval, we rerun Algorithm 2.1 to obtain an updated solution. The transmit powers of all the users are equal and set to a value which yields a minimum signal-to-noise-ratio (SNR) of 10 dB at the receivers. The SINR threshold is θith = θth , ∀ i ∈ N , and is set to 0 dB. The convergence threshold ǫ is set to 10−4 . All the users have the same α-fair utility functions (c)∗ with αi = α, ∀ i ∈ N . For initialization, we use pi (c)∗ = qi = 1/C, ∀ i ∈ N , c ∈ C in lines 1 and 2 in Algorithm 2.1. We first evaluate the optimality of the solution obtained with Algorithm 2.1. We consider the case of five users, two orthogonal channels with identical channel conditions, and α = 5. The optimal solution under the SINR model is obtained with an exhaustive search. As shown in Fig. 2.2, the solution obtained with Algorithm 2.1 is near-optimal. In Fig. 2.3, we evaluate the convergence of Algorithm 2.1 for N = 10, C = 3, and α = 0. From Theorem 2.4, the algorithm converges to a fixed point limt→∞ u∗ (t) = u∗ . Also, the aggregate utility u∗ (t) obtained in iteration t is a non-decreasing sequence, i.e., u∗ (t) ≤ u∗ (t + 1). The improvement in u∗ (t) in phase III is more significant than that in phase I. In phase I, the transmitters may transmit in all channels, i.e., a significant amount of 46 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game 40 * Aggregate Utility u (t) 35 30 25 20 Phase I Phase II Phase III 15 10 5 0 10 20 30 40 50 60 Iteration t Figure 2.3: Convergence of the aggregate utility u∗ (t) using the three-phase distributed algorithm (i.e., Algorithm 2.1). Notice that the aggregate utility obtained in each iteration is non-decreasing. The users probe the channels in phase I and select the best channel in phase II. In phase III, the transmission probabilities are adjusted based on the channels selected in phase II. interference is generated. However, in phase III, since the users have selected to transmit and listen to only one channel, the number of potential interferers in each channel is reduced. As a result, the improvement in u∗ (t) is more significant. In Fig. 2.4, we consider the case N = 10, C = 4, and α = 0 when the set of data channels C changes due to dynamic spectrum leasing. Specifically, we assume that two channels are removed from C when the lease expires, and one new channel is leased and added back to C later. As we can see, by running Algorithm 2.1 based on p∗ from the previous solution after each change in set C, the solution converges quickly to a fixed point again and adapts to these dynamic network changes. Next, we compare the aggregate throughput achieved with Algorithm 2.1 for the SINR model (using Mi = Mi,SIN R, ∀ i ∈ N ) and protocol model (using Mi = Mi,P T C , ∀ i ∈ N ), and the multi-channel MAC (MMAC) protocol [1] for N = 10 and α = 0 averaged over 100 47 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game 50 Two channels removed 45 * Aggregate Utility u (t) 40 One channel added 35 30 25 20 15 10 5 Phase I 0 20 II 40 I III 60 80 II 100 III I 120 140 II 160 III 180 Iteration t Figure 2.4: The change in aggregate utility u∗ (t) when the set of data channels C changes due to dynamic spectrum leasing. Initially, we assume that there are four data channels available. We assume that two data channels are removed from C and then one data channel is added back to C. We run the three-phase distributed algorithm (i.e., Algorithm 2.1) based on the previous solution after set C has changed. We can see that u∗(t) converges again quickly to a fixed point when the set C changes. different random topologies when the number of orthogonal channels C varies. The MMAC protocol is a multi-channel extension of the IEEE 802.11 distributed coordination function and is suitable for the spectrum leasing model in CRNs. In MMAC, the users first select the channel with the least scheduled traffic, and then contend for it by using the carrier sense multiple access with collision avoidance (CSMA/CA) protocol. We assume that the channel is sensed busy if any one-hop neighbour transmits. In other words, the sensing is based on the protocol model. Since Algorithm 2.1 obtains a locally optimal solution from a given starting point, we execute Algorithm 2.1 from thirteen randomly generated feasible starting points (p∗ , q ∗ ), and record the solution that yields the maximum aggregate utility to obtain a solution that is close to the globally optimal one. As shown in Fig. 2.5, when C increases, less interference is experienced by each user, so the overall system throughput is increased. Also, we notice that the design based on the SINR model always achieves a 48 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game Average Aggregate Throughput 60 50 40 30 20 SINR Model Protocol Model MMAC 10 0 1 2 3 4 5 6 Number of Available Orthogonal Channels C Figure 2.5: Average aggregate throughput versus the number of orthogonal channels available for Algorithm 2.1 using the SINR model, the protocol model, and the MMAC [1]. Notice that the design based on the SINR model achieves the highest aggregate throughput. higher throughput than that using the protocol model and the MMAC protocol. Finally, we investigate the payoff distribution for the Shapley value and the existence of the core for the network scenario shown in Fig. 2.6. Eight secondary users are randomly placed in a 75 m × 75 m open area, α = 0, and the peak data rate of each user is fixed to 10 Mbps. The minimum SNR is guaranteed to be at least 20 dB and we consider different SINR thresholds θth , e.g., for different bit error rate requirements. The aggregate utility of the grand coalition v(N ) = i∈N φi (v) and the Shapley value φ(v) are shown in Fig. 2.7. By increasing θth , the receivers become less tolerant to interference from other users, so the interference range is increased and the spatial reuse factor is reduced. As a result, v(N ) is reduced as shown in Fig. 2.7. From (2.5), when θth is increased up to a certain value, all users are one-hop neighbours to each other. This holds true in this setting when θth ≥ 15 dB. As expected from Theorem 2.7, all the users equally share the aggregate utility in this case. Also, notice that user 5 generates and receives the least amount of interference due to 49 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game 6 70 8 3 2 50 y 5 3 6 60 40 5 8 4 30 7 42 20 1 10 0 7 1 0 10 20 30 40 50 60 70 x Figure 2.6: A CRN with eight users. User 5 generates and receives the least amount of interference due to its isolated position. its isolated position. Thus, it has a large marginal contribution to different coalitions, and receives the largest proportion of the payoff for θth < 15 dB. Moreover, it can be shown that the constraints in (2.46) can be satisfied and the core exists in this example for all the values of θth that we have studied. However, the Shapley value lies only in the core for θth ≥ 10 dB, which includes the cases θth ≥ 15 dB where all the users are one-hop neighbours to each other as stated in Theorem 2.7. 2.7 Summary In this chapter, we have studied random access in CRNs using the SINR model. For cooperative users in a multi-channel model, a three-phase distributed algorithm has been proposed to obtain a near-optimal solution for the formulated non-convex NUM problem. It converges readily to a close-to-optimal value even when the set of data channels changes due to dynamic spectrum leasing. For rational users in a single-channel model, we have used the core and the Shapley value to characterize the stability and fair allocation of the 50 Chapter 2. Multi-channel SINR-based Random Access and Coalitional Game 40 35 φ (v) 8 φ7(v) 30 φ6(v) v(N) 25 φ (v) 5 φ4(v) 20 φ3(v) 15 φ2(v) φ1(v) 10 5 0 0 5 10 15 20 θth (dB) Figure 2.7: Aggregate utility of the grand coalition v(N ) = i∈N φi (v) and the Shapley value φ(v) for the secondary users in Fig. 2.6. When θth is increased, v(N ) is decreased because the interference range is increased. When θth is increased to 15 dB, v(N ) is equally shared among these one-hop neighbours as stated in Theorem 2.7. Notice that user 5 has the largest share of payoff for θth < 15 dB due to its large marginal contribution to different coalitions. payoff among the users, respectively. In our system model, we have assumed that (a) the set of users N is fixed and (b) the transmission between the transmitter and receiver of each user is only single-hop. For (a), it can be shown that by running Algorithm 2.1 starting from the previous solution after N has changed, the solution converges readily again to a fixed point. For (b), we may consider the multi-hop setting by introducing binary routing variables and flow conservation constraints as in [57]. 51 Chapter 3 VCG-based Truthful Random Access Protocols for WLANs In this chapter, we consider a WLAN with several users associated with an AP. The users support applications with both elastic and inelastic traffic [12]. The elastic traffic is generated by applications such as traditional file transfer and electronic mail. The inelastic traffic is generated by applications including real-time voice and video streaming, which usually have tight QoS requirements. We consider the setting where the users first declare their ACs (or utility functions) to the AP. In return, the AP assigns transmission probabilities to the users for random access such that the aggregate utility of all the users is maximized. If all the users accurately declare their AC information, the aforementioned setting can lead to adequate QoS and service differentiation based on application needs. However, some users may cheat on their declared ACs to obtain some larger shares of bandwidth. We first use non-cooperative game theory to analyze the behaviour of users in the described wireless system. Then, we apply the Vickrey-Clarke-Groves (VCG) mechanism [25, 26, 34] to motivate the users to be truthful through pricing. In fact, pricing is important for the efficient allocation of network resources among users [58]. The VCG mechanism has been successfully applied in various other areas, e.g., resource allocation for wireless multimedia applications [59] and multipath traffic assignment [60]. To implement the VCG mechanism in the described wireless system, we need to obtain the exact optimal solution of a formulated NUM problem, where the optimization variables 52 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs are the transmission probabilities of all the users in the system. Note that replacing the optimal solution with even a near-optimal solution will make the mechanism useless and untruthful [61]. Previous works, such as [62, 63], have focused on solving the NUM problem to achieve efficiency and fairness for wireless random access for elastic traffic only, where the utility functions of the applications are concave [64]. However, here we include the more challenging case of inelastic traffic. The application requirements of users with inelastic traffic are modeled using step or quasi-concave utility functions. As a result, the formulated NUM problem in this chapter is non-convex and is difficult to solve in general. We propose an algorithm to obtain the optimal solution for the formulated non-convex problem, which is based on solving a number of convex optimization problems. In summary, the main contributions of this chapter are listed as follows. • We formulate a wireless random access game using non-cooperative game theory and analyze the behaviour of rational users, where service differentiation for QoS support is implemented. • We apply the VCG mechanism to encourage the users to truthfully reveal their ACs. • We address several challenging computational issues in implementing the VCG mechanism which requires solving a complicated non-convex optimization problem. We propose a low-complexity enumeration algorithm to obtain the global optimal solution by iteratively solving a chain of convex optimization problems. • Simulation results show that our scheme ensures that both service differentiation and maximum network utility can be achieved. Moreover, we demonstrate the low computational complexity of our scheme and its performance gain over a CSMA scheme in terms of the system utility. The rest of this chapter is organized as follows. We present the related work in Section 53 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs 3.1. The system model and the non-cooperative random access game are described in Section 3.2. The proposed VCG-based scheme is presented in Section 3.3. The algorithm required for implementing the VCG mechanism for random access is discussed in Section 3.4. Simulation results are presented in Section 3.5. A summary is given in Section 3.6. 3.1 Related Work A number of previous works addressed non-cooperative random access from the players’ viewpoint using game theory. Network equilibrium points were characterized and strategies were proposed to counteract the selfish behaviours of players. In [65], Cagalj et al. modeled carrier sense multiple access with collision avoidance (CSMA/CA) using game theory. Both normal-form and repeated-form CSMA/CA games were formulated and the existence of a Nash equilibrium (NE) was shown for each game. In [66], game theory was applied to analyze the behaviour of selfish nodes in a one-shot random access game. Necessary and sufficient conditions for the NE were proposed, and the asymptotic properties of the system were studied. Chen et al. proposed in [67] an analytical framework for random access using game theory. Distributed algorithms were proposed to achieve the NE. In [68], a cartel maintenance repeated game framework was proposed. A trigger-punishment rule was designed so that it is always in each user’s best interest to cooperate. On the other hand, it is possible to take a proactive approach from the system designer ’s point of view and introduce some mechanisms to prevent players from misbehaving. Wang et al. proposed in [69] a strategyproof mechanism for wireless multicast routing. An agent’s profit is maximized when it truthfully reports its cost. Nuggehalli et al. proposed in [70] an incentive mechanism to avoid selfishness. They showed that the users are encouraged to always be truthful on declaring their ACs in an attempt to increase throughput under some conditions. Bae et al. studied in [71] the design of a dynamic auction for wireless 54 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs spectrum sharing between the high and low transmit power users. A mechanism was proposed that maximizes the incentives for truthful bidding. Huang et al. proposed in [72] two auction mechanisms, namely signal-to-noise ratio (SNR) auction and power auction, for distributed relay selection and relay power allocation in cooperative communications. The best response bid updates globally converge to the unique NE asynchronously. Ko et al. proposed in [73] a mechanism to gather the private traffic information of selfish users in two-tier Orthogonal Frequency Division Multiple Access (OFDMA) femtocell networks. It was shown that the resource allocation achieves weighted max-min fairness, weighted proportional fairness, and Pareto efficiency. 3.2 System Model Consider a WLAN with one AP and N mobile stations (MSs)1 . The set of MSs is denoted by N = {1, 2, . . . , N}. All MSs are one-hop neighbors to the AP. Time is divided into equal-length slots. We only consider the uplink scenario2 , where each MS i ∈ N attempts to access the shared wireless channel at the beginning of each time slot with transmission probability pi . Note that the choice of transmission probabilities can be transformed into equivalent contention window sizes that can be implemented in IEEE 802.11 WLANs [74]. Let psucc denote the probability that a transmission from station i ∈ N is successful, i.e., i does not experience collision, in a time slot. We have psucc (p) = pi i (1 − pj ), j∈N \{i} ∀i ∈ N, (3.1) 1 In this chapter, we use the terms mobile stations, users, and players interchangeably. We notice that selfish users may only affect the performance of the uplink transmissions. In fact, for downlink transmissions, the AP can simply perform scheduling with adequate QoS provisioning and there is no need for random access. 2 55 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs 2 1.5 Utility 1 0.5 α−fair Step α−critical 0 −0.5 0 0.2 0.4 0.6 0.8 Probability of successful transmission 1 (psucc) i Figure 3.1: Three different types of utility functions considered in this work: (1) Concave function: α-fair function (Ki = 0.1, αi = 1, and Li = 4), (2) Step function (Ki = 1.5 and pcritical = 0.25) , and (3) Quasi-concave function: α-critical function (Ki = 0.015, αi = 3, i and pcritical = 0.1). i where vector p = (pi , i ∈ N ). Given the nominal data rate ϕ (e.g., 54 Mbps in IEEE 802.11g), the average data rate for user i is obtained as ϕ psucc (p). The MSs are assumed i to run different types of applications, where each application may have different QoS requirements. 3.2.1 Utility Functions For each MS i ∈ N , we use a utility function ui (psucc (p)) to model the level of satisfaction i that station i experiences from its application when it attains success probability psucc (p). i The utility functions are assumed to be nondecreasing. We consider a system with MSs having both elastic and inelastic traffic. Let NE and NI denote the sets of users with elastic and inelastic traffic, respectively. We refer to these users as elastic and inelastic users in the following. Note that NE ∩ NI = ∅ and NE ∪ NI = N , where ∅ is the null set. For each user j ∈ NE with an elastic application 56 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs (e.g., file transfer and electronic mail), we can use a concave function to model the utility [64]. A common class of concave utility functions is α-fair utility function, which is defined as [53] ui (psucc (p), αi , Ki , Li ) = i Ki ln psucc (p) + Li , i Ki psucc (p)(1−αi ) i 1−αi + Li , if αi = 1, (3.2) if αi > 1, where ui is the utility that user i receives, αi ≥ 1 is a fixed utility parameter, and Ki ≥ 0 is an amplitude parameter. Li is a parameter that adjusts the vertical position of the utility curve. On the other hand, the applications supported by each user i ∈ NI , such as voice and video streaming, may have tight QoS requirements and require some minimum level of available bandwidth. If the available bandwidth drops below the required threshold, then the connection will become useless, leading to zero utility for the corresponding user. In this chapter, we use two types of utility functions to model inelastic traffic: step functions and quasi-concave functions. A step utility function is characterized by parameters Ki and pcritical . Parameter pcritical ≥ 0 refers to the minimum required psucc (p) for the application i i i to run properly in station i ∈ NI . Parameter Ki determines the amplitude of the utility function as long as the required pcritical is achieved. Step utility functions are used to mathi ematically model various hard real-time applications, such as audio and voice applications, which cannot operate if the minimum required data rate is not provided [12]. That is, ui psucc (p), Ki , pcritical = i i Ki , if psucc (p) ≥ pcritical , i i 0, if (3.3) psucc (p) < pcritical . i i Furthermore, for rate-adaptive video, audio, and other applications with minimum bandwidth requirements, we can model the utility functions to be quasi-concave. We introduce a new quasi-concave utility function [21, pp. 95], which we refer to as the α-critical utility 57 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs function, by modifying the α-fair utility function in (3.2). If αi = 1, we have ui psucc (p), αi, Ki , pcritical i i = Ki ln psucc (p) i pcritical i , if psucc (p) ≥ pcritical , i i 0, (3.4) . (p) < pcritical if psucc i i If αi > 1, then the α-critical utility function is modeled as ui (psucc (p), αi, Ki , pcritical ) i i = Ki (psucc (p))(1−αi ) − pcritical i i 1−αi (1−αi ) 0, , if psucc (p) ≥ pcritical , i i if psucc (p) < pcritical . i i (3.5) Clearly, α-critical and step utility functions are non-concave and non-differentiable. Some examples of the utility functions that we consider in this chapter are shown in Fig. 3.1. For simplicity of presentation, we denote the set of utility parameters for each user i ∈ N by θi . Using the terminology of game theory, we refer to θi as a type for user i. Notice that there is a one-to-one correspondence between a type and an AC. If utility function ui is a concave α-fair function as in (3.2), we have θi = {Ki , αi , Li }. If utility function ui is a step function as in (3.3), then θi = {Ki , pcritical }. Finally, if it is an α-critical i function as in (3.4) and (3.5), then θi = {Ki , αi , pcritical }. i 3.2.2 Network Utility Maximization Problem Given complete knowledge of all system parameters (i.e., θi , ∀ i ∈ N ) and centralized control of the WLAN, an efficient choice of all transmission probabilities p is characterized as an optimal solution of the following NUM problem across all users [12, 62, 75]: ui (psucc (p), θi ) , i maximize p ∈P (3.6) i∈N where P = {p : 0 ≤ pi ≤ 1, ∀ i ∈ N } represents the set of all feasible transmission proba58 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs bilities. The objective function in optimization problem (3.6) is also called network social welfare [27]. As the ACs of the applications running on the MSs are private information, they are not known to the AP. That is, the AP is not aware of the MSs’ utility functions. Thus, the AP may not be able to solve NUM problem (3.6) unless each MS i ∈ N declares its true type θi to the AP. Clearly, if all the stations are truthful, then the obtained vector of optimal transmission probabilities leads to the optimal network performance. However, if a user i ∈ N is selfish, then it may declare its type to be θˆi = θi to obtain a higher utility. In that case, the obtained transmission probabilities are not optimal. In fact, the network performance can be very poor in the latter case, as shown in Section 3.5. 3.2.3 Non-cooperative Random Access Game Using game theory, we next formulate the described N-user random access system as a finite N-person non-cooperative normal-form game (N , Ω, u), where N is the set of players, Ω = Θ1 × Θ2 × · · · × ΘN is the Cartesian product of the action sets of all players, Θi is the action set of player i, and u = (u1 , u2, . . . , uN ) is the vector of utility functions for all the stations. In this chapter, we assume for simplicity that all players have the same action set Θ. That is, Θi = Θ, ∀ i ∈ N . The action of each station i ∈ N is to strategically select its declared type θˆi (which is not necessarily the same as its true type θi ) to maximize its own utility. That is, given θˆ−i = (θˆ1 , . . . , θˆi−1 , θˆi+1 , . . . , θˆN ) as the vector of declared types for all stations other than station i, where θˆ−i ∈ Ω−i = Θ1 × · · · × Θi−1 × Θi+1 × · · · × ΘN , station i selects θˆi to solve the following local problem related to its actual utility function ui (psucc , θi ): i ˆ θˆi , θˆ−i )), θi , (p( maximize ui psucc i θˆi ∈Θi (3.7) which is based on the prior knowledge that the AP will determine the vector of the players’ transmission probabilities pˆ by solving the following global optimization problem, according 59 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs to the application type declarations θˆ of all the players: ˆ = arg max ˆ θˆi , θˆ−i ) = p( ˆ θ) p( p ∈P ui psucc (p), θˆi . i (3.8) i∈N Notice that the difference between problems (3.6) and (3.8) is that in (3.8) we have replaced the true type θi with the declared type θˆi for each i ∈ N . That is, the solution of problem (3.6) is what the system aims to achieve, while that of problem (3.8) is what the system actually achieves. The complete analysis of game (N , Ω, u) is very difficult in general. Nevertheless, we can show the following interesting theorem, which states that player i is interested in ˆ i to be as large as possible in order to have a higher success probability psucc (p), declaring K i and thus a higher utility ui . Theorem 3.1 For any α-fair, step, or α-critical utility functions in game (N , Ω, u), if ˆ i > Ki ≥ 0 and the declarations of other players θˆ−i a player i ∈ N declares θˆi such that K remain the same, we have ˆ θˆi , θˆ−i )) ≥ psucc ˆ i , θˆ−i )), ∀ θˆi = θi , θˆ−i ∈ Ω−i , psucc (p( (p(θ i i (3.9) ˆ θˆi , θˆ−i )) and psucc ˆ i , θˆ−i )) are the probabilities of successful transmission where psucc (p( (p(θ i i ˆ i and Ki , respectively. obtained when player i declares K ˆ i , i ∈ N , act as weighting parameters in problem Proof : We notice that parameters K (3.8). Together with the fact that α-fair, step, and α-critical utility functions are all ˆ i , the higher nondecreasing functions in psucc (p), it follows that the higher the value of K i ˆ i > Ki , we have psucc (p( ˆ θˆi , θˆ−i)) ≥ (p) would be at optimality. Thus, for K the value of psucc i i ˆ i , θˆ−i)). psucc (p(θ i ˆ i can be chosen from, then From Theorem 3.1, if there is a range of values that K 60 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs ˆ i to its maximum possible value is a dominant strategy [25, 34] of player i. A declaring K dominant strategy is a strategy that is chosen regardless of the strategies of other players. Clearly, playing such an untruthful dominant strategy results in a significant degradation of the network performance and prevents adequate service distinction among different ACs. In our system model, we assume that the players can possibly declare all the utility parameters (i.e., their types) in such a way that increases their own utilities. The analysis related to the strategic declarations of α ˆi and pˆcritical are not as straightforward as that of i ˆ i stated in Theorem 3.1 and we leave it for future work. Next, we show that by using K a VCG mechanism, the players are encouraged to declare their types truthfully for their own good. 3.3 Truthful Mechanism Design for WLANs The results in Theorem 3.1 reveal that it is crucial to develop efficient schemes to motivate the stations to be truthful, i.e., to declare their true types. In this section, we use mechanism design [25, 26, 34] for this purpose. Mechanism design is a sub-field in microeconomics and game theory that studies the problem of optimal resource allocation in the presence of selfish players, who aim to maximize only their own payoffs. Mechanisms are responsible for the allocation of resources and incur payment to the players, so as to provide them with incentives to declare their private information (i.e., their types) truthfully. Groves mechanism and its subfamily, named Vickrey-Clarke-Groves (VCG) mechanism, are among the most efficient mechanisms that not only prevent the dishonesty of players, but also guarantee achieving the maximum network social welfare. The latter implies achieving the optimal performance in terms of solving the NUM problem in (3.6). The VCG mechanism consists of two main components [34]: an allocation rule and a payment rule. For the allocation rule, given the declared types of all players θˆ= (θˆ1 , . . . , θˆN ), 61 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs the AP selects the transmission probabilities according to the optimal solution of problem ˆ on each (3.8). Moreover, according to the payment rule, it also imposes a payment ti (θ) MS i ∈ N such that ˆ = ti (θ) j∈N \{i} ˆ θˆj − uj psucc (p˜i (θ)), j p∈P, pi =0 (3.10) j∈N \{i} uj psucc (p), θˆj , j ˆ = arg max p˜i (θ) where ˆ θˆj , ˆ θ)), uj psucc (p( j (3.11) j∈N \{i} ˆ is as in (3.8). The above payment values are calculated based on the declared ˆ θ) and p( ˆ not the true types θ, as the AP is not aware of the true types of the MSs. Also types θ, notice that in (3.10), the first term, i.e., j∈N \{i} ˆ θˆj ), charges player i with uj (psucc (p˜i (θ)), j the aggregate utility achieved when player i is removed from the network, and the second term, i.e., j∈N \{i} ˆ θˆj ), pays player i with the aggregate utility achieved ˆ θ)), uj (psucc (p( j excluding that of player i when player i is added to the network. Thus, player i is made to pay its social cost, which is the aggregate impact that its participation has on other players’ utilities [25]. Note that there are various ways to implement such payments in practice. For example, one can assume that there is a trusted charging entity which maintains a billing account for every player in the system (e.g., as in [76]). ˆ = (t1 (θ), ˆ . . . , tN (θ)), ˆ each station needs to pay Given the vector of payment rules t(θ) ˆ to the AP for relaying its transmitted packets. Intuitively, VCG selects the payment ti (θ) values such that it is the best choice for the players to be honest and declare their true types. In fact, since each player needs to pay the AP for the packets it transmits, player i ∈ N needs to declare its type θˆi such that its surplus (i.e., its utility minus payment) is maximized. In other words, when VCG mechanism is used, instead of solving problem 62 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs (3.7), player i has to solve the following problem to maximize its own payoff: ˆ θˆi , θˆ−i)), θi − ti (θˆi , θˆ−i). maximize ui psucc (p( i θˆi ∈Θi (3.12) In fact, VCG mechanism forces all players to be honest as shown by the following theorem. Theorem 3.2 Assume that the allocation and payment rules are implemented as in (3.8) and (3.10), respectively, then declaring θˆi = θi is a dominant strategy for player i ∈ N . Proof : Please refer to [34, pp. 42]. From Theorem 3.2, if VCG mechanism is used, the most beneficial action for all players is to declare their true types such that θˆi = θi for all i ∈ N , irrespective of the declarations by other players. Thus, solving problem (3.8) based on the declared types suffices to achieve optimal performance, i.e., the maximum network utility as described in (3.6). This is the key property of the VCG mechanism. We are now ready to propose our VCG-based mechanism for QoS provisioning in WLANs with random access. It includes the following key steps: 1. Type declaration: Before starting transmission, all stations declare their types to the AP. ˆ the AP calculates the transmission 2. VCG mechanism: Given the declared types θ, ˆ as in (3.8). It also calculates the payments t(θ) ˆ using (3.10) and ˆ θ) probability p( (3.11). 3. Resource allocation and payment: The obtained vectors of transmission probabilities and payments are broadcast by the AP to all stations. Stations may only transmit based on the transmission probabilities assigned by the AP; otherwise, they will be 63 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs Figure 3.2: A WLAN with a set of users N = {1, 2, 3}. In our system model, user i first declares to the AP the utility parameter (or type) θˆi , which characterizes the AC of the application of user i. After receiving θˆi , ∀ i ∈ N , the AP assigns the transmission probabilities pˆ = (ˆ p1 , pˆ2 , pˆ3 ) for random access and charges the users t = (t1 , t2 , t3 ) according to the allocation and payment rules of the VCG mechanism described in (3.8) and (3.10), respectively. By using the VCG mechanism, it is shown in Theorem 3.2 that a rational player i should declare its true utility parameter θi in order to maximize its own utility. refused service3 . The system model of the VCG-based random access scheme is shown in Fig. 3.2. Next, we try to answer the following key question: How can we solve the computationally challenging optimization problems (3.8) and (3.11)? 3.4 Implementation of the VCG Mechanism ˆ in (3.8) and p( ˆ in ˆ θ) ˜ θ) In order to implement the VCG mechanism, we need to compute p( (3.11). However, in general, solving the optimization problems in (3.8) and (3.11) is not an easy task due to the non-convexity of the product forms in (3.1) and the non-differentiability 3 It is easy for the AP to check whether the stations are indeed transmitting according to the assigned transmission probabilities by listening to the shared communication medium as explained in [75]. 64 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs of step and α-critical utility functions. In this section, we propose an algorithm to obtain the globally optimal solutions of problems (3.8) and (3.11) by iteratively solving a number of convex optimization problems. Here, we will focus on problem (3.8) because similar techniques can be applied to solve problem (3.11). In this chapter, we assume that the declared utility function for each elastic user j ∈ NE is an α-fair utility function as in (3.2). We also assume that the declared utility function for each inelastic user i ∈ NI is either a step function as described in (3.3) or an α-critical function as defined in (3.4) and (3.5). Although we only consider α-fair functions for concave functions and α-critical functions for quasi-concave functions, our approach can be applied to any similar continuous nondecreasing function as long as its concave part satisfies the following condition on the curvature of the utility function [62]: ˆ ˆ du(psucc , θ) d2 u(psucc , θ) succ p ≤ − . d(psucc )2 dpsucc (3.13) With both elastic and inelastic users in the system, problem (3.8) can be written as uj (psucc (p), θˆj ) + j maximize p ∈P j∈NE ui (psucc (p), θˆi ), i (3.14) i∈NI where psucc (p) is defined as in (3.1) for all users i ∈ N . Notice that problem (3.14) is i a non-convex and non-differentiable optimization problem due to the non-convexity and non-differentiability of α-critical or step utility functions as we discussed in Section 3.2.1. Let p∗ denote the optimal solution of problem (3.14). Also let psucc (p∗ ) = p∗i i j∈N \{i} (1− p∗j ) denote the corresponding optimal success probability for station i ∈ N . We can show the following lemma which helps us compute the optimal allocation of transmission probabilities. Lemma 3.1 At any optimal solution of problem (3.14), for all inelastic users i ∈ NI , we 65 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs have either psucc (p∗ ) ≥ pˆcritical or psucc (p∗ ) = 0. i i i Proof : We prove by contradiction. Assume that at optimality, we have 0 < psucc (p∗ ) < i pˆcritical for some user i ∈ NI . Since the minimum required success probability is not i satisfied for user i ∈ NI , we have ui = 0. Thus, the objective function of problem (3.14) at optimality becomes uj (psucc (p∗ ), θˆj ) + j j∈NE ∗ ˆ uk (psucc k (p ), θk ). (3.15) k∈NI \{i} On the other hand, from (3.1), the success probability psucc (p) is a decreasing function of j pi for any j = i. Therefore, the summation in (3.15) is decreasing in p∗i and at optimality we have p∗i = 0. This implies that psucc (p∗ ) = 0 which contradicts our assumption that i 0 < psucc (p∗ ) < pˆcritical . i i From Lemma 3.1, when VCG mechanism is being used, the AP either does not admit an inelastic user i, or if it does admit user i, then it guarantees to provide it with its minimum required success probability pˆcritical . Thus, we can obtain the optimal value of i problem (3.14) by considering all subsets of users M ⊆ NI admitted: v(M), maximize M⊆NI (3.16) where v(M) uj (xj , θˆj ) + maximize x, p ∈ P j∈NE ui(xi , θˆi ) i∈NI subject to 0 ≤ xi ≤ psucc (p), i ∀ i ∈ NE ∪ M, pˆcritical ≤ psucc (p), i i ∀ i ∈ M, pi = 0, ∀ i ∈ NI \M. (3.17) 66 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs In problem (3.17), the first constraint is introduced for the auxiliary variable xi [62]. We divide the set of inelastic users NI into two subsets: subset M and subset NI \M. Here, set M denotes the set of those users which are admitted to the system, and acts as an auxiliary set to model admission control. For each inelastic user i ∈ M, problem (3.17) includes the extra constraint psucc (p) ≥ pˆcritical such that all admitted inelastic users achieve i i their minimum required success probabilities pˆcritical . On the other hand, for each inelastic i user i ∈ NI \M, which is not admitted, we include the constraint pi = 0 to make sure that no transmission probability is allocated to it. By taking the logarithm of both sides of the first and second constraints in (3.17) and ′ a logarithm change of variables u′i (x′i , θˆi ) = ui(exi , θˆi ) and x′i = ln xi , we can reformulate problem (3.17) as v(M) = maximize ′ x , p ∈P j∈NE u′j (x′j , θˆj ) + subject to x′i ≤ ln pi + ln pˆcritical i i∈NI u′i (x′i , θˆi ) ln(1−pj ), j∈N \{i} ≤ ln pi + pi = 0, j∈N \{i} ∀ i ∈ NE ∪ M, (3.18) ln(1−pj ), ∀ i ∈ M, ∀ i ∈ NI \M. From [62], problem (3.18) is convex, so it can be solved using the interior point method [21]. Let NI = |NI |. Notice that we need to evaluate 2NI possible subsets M of NI in problem (3.16). However, there are many redundant computations that can be eliminated. Let M(θ) = i ∈ M : θˆi = θ be the subset of users in set M ⊆ NI with declared type θ. We define the equivalent AC sets as follows: 67 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs Definition 3.1 A pair of sets M1 , M2 ⊆ NI are equivalent AC sets if |M1 (θ)| = |M2 (θ)|, ∀ θ ∈ Θ. (3.19) In other words, sets M1 and M2 have the same number of users in every ACs. Given the above definition, we can show the following lemma for equivalent AC sets: Lemma 3.2 If M1 , M2 ⊆ NI are equivalent AC sets, then we necessarily have v(M1 ) = v(M2 ). Proof : By definition, M1 and M2 have the same number of users in every AC. Thus, the optimization problems resulting for v(M1 ) and v(M2 ) as defined in (3.17) have the same objective functions and constraints. Thus, we have v(M1 ) = v(M2 ). Let ΘI be the set of types that are present in set NI . That is, θi ∈ ΘI ⇔ i ∈ NI . Let NIθ be the number of users in set NI with type θ ∈ ΘI . We have θ∈ΘI NIθ = NI . The total number of subsets of set NI which are not equivalent AC sets is given by θ θ∈ΘI (NI + 1) [77, pp. 197]. From Lemma 3.2, after solving problem (3.18) for v(M1) in problem (3.16), we do not have to solve it again for v(M2) if M1 and M2 are equivalent AC sets. Thus, in problem (3.16), we actually need to solve problem (3.18) for only θ θ∈ΘI (NI + 1) different v(M) if we explore the equivalent AC sets. Moreover, in some cases when too many users are admitted, problem (3.17) may become infeasible. Let M = |M|. The following lemma helps us in identifying some of the infeasible cases. Lemma 3.3 Given set M ⊆ NI and pˆcritical for all i ∈ M, problem (3.17) is feasible only i if M −1 i∈M pˆcritical ≤ 1− i i∈M pˆcritical . i (3.20) 68 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs Proof : Problem (3.17) is feasible if and only if we have pi j∈M\{i} (1 − pj ) ≥ pˆcritical , i ∀ i ∈ M. (3.21) From (3.21) and by reordering of the terms we have pi ≥ 1 − pi pˆcritical i j∈M (1 − pj ) ⇒ pi ≥ 1 j∈M (1−pj ) pˆcritical i 1+ ∀ i ∈ M. , (3.22) From the last line, for each user i ∈ M, we have 1 − pi ≤ j∈M (1−pj ) pˆcritical i 1+ j∈M (1−pj ) = pˆcritical i j∈M (1 pˆcritical i + − pj ) j∈M (1 − pj ) . (3.23) Multiplying the terms for each user i ∈ M, we can come up with the following condition i∈M We define A(p) = (1 − pi ) ≤ j∈M (1 j∈M (1 i∈M pˆcritical i + − pj ) j∈M (1 − pj ) . (3.24) − pj ). Clearly, 0 ≤ A(p) ≤ 1 is the probability of experiencing an idle time slot. That is, the probability that no user transmits any packet. Replacing A(p) in (3.24), problem (3.17) is feasible if there exists a value A between zero and one such that we have A≤ AM pcritical + A) i i∈M (ˆ ⇒ i∈M (ˆ pcritical + A) ≤ AM −1 . i (3.25) For the rest of the proof, we show that condition (3.20) is a necessary condition for the existence of any A such that (3.25) holds. We first notice that from (3.25), we need to 69 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs have M −1 i∈M pˆcritical ≤ A. i (3.26) Condition (3.25) can be written in the following extended form AM + i∈M pˆcritical − 1 AM −1 + Γ(A) ≤ 0, i (3.27) where Γ(A) is a polynomial in A with degree M − 2 and only non-negative multipliers. Clearly, Γ(A) ≥ 0. Thus, from (3.27) we also need to have A≤1− i∈M pˆcritical . i (3.28) Combining the lower-bound in (3.26) and the upper-bound in (3.28), optimization problem (3.17) is feasible only if there exists an A such that the following holds: M −1 i∈M pˆcritical ≤ A ≤1− i i∈M pˆcritical . i (3.29) Clearly, the above condition holds as long as the upper bound is greater than or equal to the lower bound. This directly results in condition (3.20). Notice that the condition in (3.20) is a necessary condition for the feasibility of the constraints in problem (3.17). We are now ready to propose Algorithm 3.1 to find the exact global optimal solution of problem (3.8) when elastic users have α-fair utility functions and inelastic users have α-critical or step utility functions. A similar algorithm can be used to solve problem (3.11). In Algorithm 3.1, from lines 3 to 7, we iterate through all possible subsets of NI and record the non-equivalent AC sets in Ψ. We only need to consider the non-equivalent AC sets, ˜ if M and M ˜ are equivalent AC because we know from Lemma 3.2 that v(M) = v(M) 70 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs Algorithm 3.1 Algorithm to solve (3.8) for the mix of α-fair, step, and α-critical utility functions defined in (3.2) to (3.5). 1: Input: θˆi , ∀ i ∈ N 2: (Initialization) Set s := −∞, p∗ := 0, M∗ := ∅, and Ψ := ∅ 3: for all subset M of NI do ˜ are not equivalent AC sets, ∀ M ˜ ∈ Ψ, as defined in (3.19), then 4: if M and M 5: Set Ψ := Ψ ∪ M 6: end if 7: end for 8: for all M ∈ Ψ do 9: Set M := |M| 10: 11: 12: 13: 14: 15: 16: 17: ≤ 1− ˆcritical then if M −1 i∈M pˆcritical i i i∈M p Solve problem (3.18) for v(M) and the optimal solution p using the interior point method if v(M) > s, then Set s := v(M), p∗ := p, and M∗ := M end if end if end for Output: p∗ and M∗ sets. From lines 8 to 16, we iterate through all the sets in Ψ. In line 10, we use Lemma 3.3 to rule out infeasible cases, which reduces the computational complexity of the algorithm. In line 11, the allocated transmission probability p for the given set M is calculated. Set M and the corresponding p that result in the largest aggregate utility so far are recorded in lines 12 to 14. In line 17, p∗ is the resulting optimal solution of optimization problem (3.8) and M∗ is the resulting set of inelastic users admitted to the system for the optimal admission control solution. 3.5 Performance Evaluations In this section, we assess the performance of our proposed VCG-based scheme in random access systems using MATLAB. We first illustrate with an example about how our proposed 71 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs VCG-based scheme enforces truthfulness of the stations. Then, we show the support of service differentiation of different ACs and maximum aggregate utility in various scenarios with selfish stations, and the low computational complexity of our scheme. We also compare our random access scheme with a CSMA scheme. Unless specified otherwise, we assume a nominal data rate ϕ = 54 Mbps. First, we provide an example to illustrate the operation of our proposed VCG-based pricing and resource allocation scheme by considering a network with one AP and six MSs. The AP supports four different ACs: AC 1 has a step utility function with parameters K = 0.1 and pcritical = 0.1. AC 2 also has a step utility function but with parameters K = 1 and pcritical = 0.1. AC 3 has an α-critical utility function with parameters K = 0.3, α = 1, and pcritical = 0.001. AC 4 has an α-fair utility function with parameters K = 5, α = 1, and L = 4. We assume that MS 1 belongs to AC 1, MS 2 belongs to AC 2, both MSs 3 and 4 belong to AC 3, and both MSs 5 and 6 belong to AC 3. We consider two cases: In Case I, MS 1 honestly declares that it supports applications in AC 1 and all other MSs are honest. In Case II, MS 1 selfishly declares that it supports applications in AC 2 (i.e., declares a larger K) while other MSs are still honest. Notice that MS 1 has the motivation to do so as stated in Theorem 3.1. With the use of the VCG mechanism and Algorithm 3.1, we plot the utilities, payments, and surpluses of the six MSs in Fig. 3.3, where Cases I and II are represented by the two bars at the index of each MS. As shown in Fig. 3.3(a), when MS 1 is honest, it is not admitted into the system and it receives zero utility. However, it is not charged with any payment by the VCG mechanism as shown in Fig. 3.3(b). On the other hand, when MS 1 is selfish, it is admitted into the system and receives a positive utility. However, with the use of the VCG mechanism, MS 1 is punished with a large payment when it lies. As shown in Fig. 3.3(c), the surplus (i.e., utility minus payment) of player 1 indeed decreases if it lies due to the use of the proposed 72 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs (a) Utility 2 Station 1 is honest Station 1 is selfish 1 0 1 2 3 4 5 6 4 5 6 4 5 6 Payment (b) 1 0.5 0 1 2 3 (c) Surplus 1 0 −1 1 2 3 Index of Stations Figure 3.3: Results in a sample network with six stations: (a) Utility, (b) Payment, and (c) Surplus (i.e., utility minus payment) of each station using the proposed VCG-based scheme. With the use of VCG mechanism, station 1 ends up having a lower surplus when it is selfish and is thus motivated to be honest. VCG mechanism. Clearly, this forces user 1 to be truthful about its type. Notice that in Case II, although MS 1 declares its application to be in AC 2 and thus receives the same transmission probability as MS 2 which has an AC 2 type of application, it receives a lower utility than MS 2 because its application is indeed in AC 1. Next, we evaluate the performance of our proposed scheme in a larger network with twelve MSs. We assume that four MSs have step utility functions with parameters K = 0.1 and pcritical = 0.1, four MSs have α-critical utility function with parameters K = 0.1, α = 1, and pcritical = 0.001, and the remaining four MSs have α-fair utility functions with parameters K = 0.01, α = 1 and L = 4. We assume that all the MSs are honest, except some of the MSs with step utility functions which are selfish and may declare a ˆ = 1 > 0.1 = K (see Theorem 3.1). The throughput and higher amplitude parameter K the network aggregate utility (i.e., the objective function in problem (3.6)) achieved for 73 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs (a) Throughput (Mbps) 25 20 15 Others (With MD) Step (Without MD) Others (Without MD) Step (With MD) 10 5 0 0 1 2 3 4 Number of selfish players with step utilities (b) 2 Aggregate Utility 1.8 1.6 56.4% 1.4 1.2 1 With Mechanism Design Without Mechanism Design 0.8 0 1 2 3 4 Number of selfish players with step utilities Figure 3.4: (a) Throughput of users with step utility functions and other utility functions and (b) aggregate utility. We assume that the stations with α-fair and α-critical utilities are honest and we vary the number of selfish stations with step utilities. We can see that differentiated QoS and maximum aggregate utility can be maintained by using the VCG-based mechanism design (MD). different numbers of selfish MSs with step utility functions are shown in Figs. 3.4(a) and (b), respectively. As shown in Fig. 3.4(a), without the use of mechanism design, selfish MSs ˆ > K in order to gain admission to the system. In with step utilities may indeed declare K this case, since many users are not truthful, the AP’s information is inaccurate. Therefore, the AP is not able to provide differentiated QoS. On the other hand, when our proposed VCG-based scheme is used, the throughput of MSs with other types of utility functions is guaranteed that the differentiated QoS is supported. In Fig. 3.4(b), we can see that the dishonest declaration of the MSs with step utilities causes a deviation from the optimal 74 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs 1200 Exhaustive Search Algorithm 1 Number of Iterations 1000 800 600 400 200 0 4 6 8 10 12 14 16 18 20 Total Number of Stations N Figure 3.5: Number of iterations required to obtain the optimal solution by Algorithm 3.1 and an exhaustive search. We can see that Algorithm 3.1 has a much lower computational complexity than an exhaustive search. network aggregate utility. The performance reduction becomes more severe as the number of selfish MSs increases, e.g., resulting in more than 56.4% efficiency loss in the presence of four selfish MSs. Thus, using the VCG-based mechanism results in a significantly better network performance. In Fig. 3.5, we compare the computational complexity of Algorithm 3.1 with an exhaustive search. Specifically, to solve problem (3.8), we compare the number of iterations that v(M) in problem (3.16) is evaluated by the two schemes. In other words, we compare the total number of times that problem (3.18) is solved for different M. For the exhaustive search, we modify Algorithm 3.1 by removing lines 3 to 7 and initializing Ψ to be the power set (i.e., the set of all subsets) of NI in line 2 instead. That is, we do not include the result of Lemma 3.2 in the exhaustive search algorithm. In our evaluation, we assume that there are four ACs, where two ACs are for inelastic traffic and the other two ACs are for elastic traffic. We assume that the number of MSs in each AC is the same and we vary 75 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs 6.2 NUM CSMA 6 5.8 15.0% Average Utility 5.6 5.4 5.2 5 4.8 10.1% 4.6 4.4 4.2 3 6 9 12 15 Total Number of Stations N Figure 3.6: Average utility in the system achieved by our NUM-based random access scheme and a CSMA scheme versus the total number of stations N in the system. the number of MSs N in the system. As we can see, by eliminating a significant number of redundant computations due to the equivalent AC sets from Lemma 3.2, Algorithm 3.1 results in a much lower computational complexity than that of the exhaustive search. In Fig. 3.6, we compare our random access scheme with a CSMA scheme similar to the one used in the IEEE 802.11e with different contention window sizes for different ACs. Let aCWmin and aCWmax be two parameters related to the contention window sizes. For the CSMA scheme, we assume that three ACs are available with different minimum and maximum contention window sizes [78, pp. 131]: aCWmin and aCWmax for AC 1 (best effort), (aCWmin + 1)/2 − 1 and aCWmin for AC 2 (video), and (aCWmin + 1)/4 − 1 and (aCWmin + 1)/2 − 1 for AC 3 (voice). We assume that when a user initiates a transmission, it keeps the channel for µ time slots. For simplicity, we do not implement the interframe space in the IEEE 802.11e standard. We assume that the number of MSs in each ACs is the same. We consider a system with real-time voice, rate-adaptive video, and file transfer applications, which their utility functions are as follows: a step function with 76 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs parameters K = 10 and pcritical = 0.001 for the real-time voice application, an α-critical utility function with parameters K = 1.2, α = 1, and pcritical = 0.001 for the rate-adaptive video application, and an α-fair utility function with parameters K = 0.5, α = 1, and L = 4 for the file transfer application. Note that the utility of the step utility function is the highest and that of the α-fair utility function is the lowest. From the nature and utilities of the applications, we map the real-time voice application to AC 3 (voice), the rate-adaptive video application to AC 2 (video), and the file transfer application to AC 1 (best effort). We choose aCWmin = 63, aCWmax = 1023 [78, pp. 589], and µ = 3. As shown in Fig. 3.6, the performance improvement of the average utility in the system of our scheme over the CSMA scheme is 15.0% for N = 3 and 10.1% for N = 15, although the CSMA scheme achieves a higher throughput as suggested in the literature. 3.6 Summary In this chapter, we studied the problem of assigning transmission probabilities to MSs for random access in a WLAN. Each MS is running an elastic or an inelastic application with different QoS requirements, which are characterized by different ACs and modeled by different utility functions. Specifically, we considered that the utility functions for elastic users are concave, while those for inelastic users are step or quasi-concave. Potentially, a selfish MS may strategically declare its AC to unfairly achieve a larger share of bandwidth, which can drastically degrade the network performance and inhibit adequate service distinction among different ACs. We used game theory to analyze the strategic declarations of the ACs of the rational users, and applied the VCG mechanism in our random access protocol to motivate the MSs to declare the ACs of their applications truthfully. In our proposed scheme, the AP performs admission control, and informs the MSs about their assigned transmission probabilities as well as the required payments. In order to implement the 77 Chapter 3. VCG-based Truthful Random Access Protocols for WLANs VCG mechanism, we need to solve a non-convex NUM problem optimally. We proposed a novel enumeration algorithm, which involves solving only a convex optimization problem in each iteration. Analytical results related to the equivalent AC sets were presented that significantly reduce the computational complexity of the proposed algorithm. Simulation results show that a truthful mechanism can prevent selfish users from gaining an unfair share of the network bandwidth, such that both the overall network performance in terms of aggregate utility and service differentiation in terms of necessary throughput in each AC can be supported. 78 Chapter 4 Random Access with Sigmoidal and Concave Utility Functions In this chapter, we extend the work in Chapter 3 for single-channel wireless random access with both elastic and inelastic traffic in a WLAN. We still model the utilities of the applications generating elastic traffic with concave utility functions. However, we extend the work in [62] and Chapter 3 by not restricting the utility functions to remain concave after a logarithmic change of variables, but allowing the possibilities of concave, convex, or sigmoidal utility functions. For applications generating inelastic traffic, we model their utilities with sigmoidal utility functions, leading to NUM problems which are usually difficult to solve. NUM problems with sigmoidal utility functions have previously been considered in various networking design problems such as Internet congestion control [79, 80], downlink power allocation [81], power control [82], and radio resource allocation [83]. But no prior work has addressed NUM problems with sigmoidal utility functions in random access systems. In this chapter, since we are not considering a VCG-based random access that requires the computation of a global optimal solution, it suffices to obtain obtain a near-optimal solution. We formulate the problem of random access as a NUM problem, which is nonconvex. We use the dual approach and the subgradient projection method to tackle the non-convexity of the NUM problem. For sigmoidal utility functions, each iteration in our algorithm involves only updating the dual variables with some closed-form expressions. In summary, the contributions of this chapter are as follows: 79 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions • We consider solving the primal problem using the dual method and derive the KarushKuhn-Tucker (KKT) optimality conditions of the dual problem. • We propose a centralized algorithm based on the subgradient projection method to solve the formulated non-convex NUM problem. • We provide a sufficient condition on the wireless link capacities which guarantee our algorithm to find the exact global optimal solution of the NUM problem. If this condition is not satisfied, we can still obtain upper and lower bounds for the optimal objective value. The bounds approach each other when the duality gap is zero. • Simulations are performed to verify our analytical results. The rest of this chapter is organized as follows. The system model is described in Section 4.1. We present our centralized algorithm and the optimality conditions for the dual problem in Section 4.2. We study the condition on capacity that results in optimal or sub-optimal solutions in Section 4.3. Simulation results are given in Section 4.4. A summary is given in Section 4.5. 4.1 System Model Consider a WLAN with a single AP and a set of N mobile stations, denoted by N = {1, 2, . . . , N}. All stations are one-hop neighbors to the AP. We only consider the uplink scenario, where each station i ∈ N can access the shared medium with a persistent probability (or transmission probability) pi . We consider using a slotted Aloha MAC protocol, where time is divided into equal time slots. The stations attempt to access the shared channel at the beginning of each time slot according to their persistent probabilities. Notice that the choice of persistent probabilities can be transformed into equivalent 80 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions contention window sizes that can be implemented directly in IEEE 802.11 WLANs [74]. Let psucc denote the probability that a transmission from station i ∈ N is successful, i.e., i the transmission does not experience any collision. We have psucc (p) = pi i (1 − pj ), j∈N \{i} ∀i ∈ N, (4.1) where p = (pi , i ∈ N ). For the rest of this chapter, we will use bold symbols to denote vectors with components ∀ i ∈ N . Given the capacity ci for user i, the average data rate for station i is xi = ci psucc (p), which is a function of both ci and p. We denote the utility i function of each station i ∈ N by Ui (xi ), which is a non-decreasing function in xi . The utility function is used to model the level of satisfaction that station i experiences from its application when it attains average data rate xi . In particular, we have Ui (xi ) ≥ 0 if xi ≥ 0. Also, we have Ui (0) = 0. Each station may have either elastic or inelastic traffic. Let NE and NI denote the sets of stations with elastic and inelastic traffic, respectively. We notice that NE ∩ NI = φ and NE ∪ NI = N . For each user v ∈ NE , we can use a concave function to model the utility. A common example is the α-fair utility function (see Fig. 4.1) [53] normalized such that Ui (0) = 0: Uv (xv ) = ln (xv + 1) , (1−αv )−1 (xv + 1)(1−αv ) − 1 , if αv = 1, (4.2) if αv ∈ (0, 1) ∪ (1, ∞), where αv is a fixed utility parameter. On the other hand, for each user w ∈ NI , the utility function depends on the quality of service (QoS) requirements of the running voice and video applications. We can use a sigmoidal utility function Uw (xw ) to model these ′′ in in applications such that Uw′′ (xw ) > 0 for xw < xin w and Uw (xw ) < 0 for xw > xw , where xw 81 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions is the point of inflection. In particular, we can use the sigmoidal function (see Fig. 4.1) defined as [84]: Uw (xw ) = xaww , kw + xaww where xw ≥ 0, aw > 1, kw > 0, and xin w = of variables x¯i ln xi and U¯i (¯ xi ) aw (4.3) kw (aw −1) . aw +1 With the logarithmic change Ui (ex¯i ), the utility functions become more convex. That is, the concave part may remain concave or turn convex [62], while the convex part always remains convex. For the concave function Uv (xv ) in (4.2), we can see that U¯v (¯ xv ) 1 is a sigmoidal function with point of inflection x¯in v = ln( αv −1 ) for αv > 1, and a convex function for 0 < αv ≤ 1. Moreover, we have U¯w (¯ xw ) = 1 1+ e−(aw x¯w +bw ) , (4.4) which represents a sigmoidal function in standard form with the point of inflection x¯in w = in −bw /aw , where kw = e−bw . Note that x¯in w = ln xw in general. In the sequel, we will assume that U¯i (¯ xi ) is sigmoidal for x¯min ≤ x¯i ≤ x¯max , ∀ i ∈ N . We will omit the cases where i i U¯i (¯ xi ) is either a convex or a concave function for brevity, because the dual problem is straightforward in these cases. It should be noted that the solution approach discussed in the following sections can be applied to concave, convex, and sigmoidal utility functions in general. 82 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions 1 0.9 0.8 0.7 Utility 0.6 0.5 0.4 0.3 U 0.2 U 1 2 U 3 0.1 U 4 0 0 2 4 6 8 10 Data Rate x Figure 4.1: Utility functions Ui versus data rate x for utility functions U1 (x) = 1−(x+1)−1 , 2 x4 U2 (x) = x2x+20 , U3 (x) = 12 [1 − (x + 1)−2 ], and U4 (x) = x4 +300 . Notice that U1 and U3 are concave functions, and U2 and U4 are sigmoidal functions. We address both concave and sigmoidal utility functions in this chapter. 4.2 Random Access with Sigmoidal and Concave Utilities 4.2.1 NUM for Random Access In this chapter, we consider the following NUM problem: maximize p,x i∈N Ui (xi ) = v∈NE subject to xi ≤ ci psucc = ci p i i xmin i ≤ xi ≤ 0 ≤ pi ≤ 1, xmax , i Uv (xv ) + j∈N \{i} (1 w∈NI − pj ), Uw (xw ) ∀i ∈ N, (4.5) ∀i ∈ N, ∀i ∈ N, where xmin and xmax are the constraints on the minimum and maximum data rates for the i i transmission of user i, respectively. Notice that problem (4.5) is a non-convex optimization 83 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions problem, because the objective function is non-concave in general, and the first constraint is non-convex. 4.2.2 Dual Method Using the logarithmic change of variables x¯i U¯i (¯ xi ) Ui (ex¯i ), and c¯i maximize p,¯ x ln xmin , x¯max i i ln xmax , i ln ci , we can reformulate optimization problem (4.5) as i∈N U¯i (¯ xi ) = subject to c¯i + ln pi + x¯min i ln xi , x¯min i ≤ x¯i ≤ v∈NE j∈N \{i} U¯v (¯ xv ) + w∈NI U¯w (¯ xw ) ln(1−pj ) − x¯i ≥ 0, ∀i ∈ N, x¯max , i (4.6) ∀i ∈ N, 0 ≤ pi ≤ 1, ∀i ∈ N. Here, the Lagrangian function is derived as L(p, x ¯, λ) = i∈N U¯i (¯ xi ) − λi x¯i + λi c¯i + ln pi + i∈N ln(1−pj ) , (4.7) j∈N \{i} and the Lagrangian dual function becomes g(λ) = sup ¯i ∈X¯i i∈N x ¯i (¯ U xi ) − λi x¯i + sup p∈P λi ln pi + i∈N ln(1−pj ) j∈N \{i} + λi c¯i , (4.8) i∈N where P = {p : 0 ≤ pi ≤ 1, ∀ i ∈ N } and X¯i = {¯ xi : x¯min ≤ x¯i ≤ x¯max }. The dual problem i i is minimize g(λ) λ subject to λ (4.9) 0. In order to solve optimization problem (4.9), we need to solve two subproblems for each 84 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions i ∈ N: ¯i (¯ max U xi ) − λi x¯i , x ¯i ∈X¯i 4.2.3 and max p∈P λi ln pi + i∈N ln(1−pj ) . (4.10) j∈N \{i} First Dual Subproblem ¯i (¯ To solve the first dual subproblem, we define si (¯ xi , λi ) = U xi ) − λi x¯i and x¯∗i (λi ) = arg max si (¯ xi , λi ). (4.11) x ¯i ∈X¯i Notice that si is also a sigmoidal function in x¯i with point of inflection x¯in i . Lemma 4.1 If x¯min ≤ x¯in ¯max , we have i i ≤ x i x¯∗i (λi ) = arg max x ¯i ∈{¯ xmin ,x ¯vi (λi )} i si (¯ xi , λi ), (4.12) where x¯vi (λi ) xi , λi ). arg max si (¯ (4.13) x ¯in xi ≤¯ xmax i ≤¯ i Proof : It is always true that max si (¯ xi , λi) = max x ¯i ∈X¯i max x ¯min ≤¯ xi ≤¯ xin i i si (¯ xi , λi ), max x ¯in xi ≤¯ xmax i ≤¯ i si (¯ xi , λi) . (4.14) Also notice that si (¯ xi , λi ) is a convex function in x¯i for x¯min ≤ x¯i ≤ x¯in i i . Thus, we have arg maxx¯min si (¯ xi , λi ) = {¯ xmin , x¯in ≤¯ xi ≤¯ xin i i }. This concludes the proof. i i Notice that problem (4.13) is convex. In fact, we can obtain a closed-form solution for (4.13) when U¯w (¯ xw ) is as in (4.4): 85 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions Lemma 4.2 For U¯w (¯ xw ) in (4.4), we have x¯vw (λw ) = − ln aw −2λw − √ a2w −4aw λw /2λw −bw aw x ¯max w x ¯in w x¯in , , if aw ≥ 4λw , (4.15) otherwise, w where [z]yw = min{max{z, w}, y}. Proof : Since sw (¯ xw , λw ) is concave for x¯in ¯w ≤ x¯max w ≤ x w , by taking the derivative, we have v U¯w′ (¯ xvw ) − λw = aw e−(aw x¯w +bw ) − λw = 0. [1 + e−(aw x¯vw +bw ) ]2 (4.16) v Let yw = e−(aw x¯w +bw ) , we obtain λw yw2 + (2λw − aw )yw + λw = 0. We can consider two cases: √ aw −2λw − a2w −4aw λw , Case I: If aw ≥ 4λw , since 0 ≤ yw ≤ 1, we can take the root yw = 2λw so x¯vw (λw ) = − ln aw −2λw − √ a2w −4aλw /2λw −bw aw x ¯max w . (4.17) x ¯in w Case II: If aw < 4λw , we have s′w (¯ xw , λw ) < 0 and sw (¯ xw , λw ) is decreasing in x¯w . Thus, x¯vw (λw ) = arg max sw (¯ xw , λw ) = x¯in w. (4.18) x ¯in xw ≤¯ xmax w ≤¯ w Considering the two cases above, we can fully characterize x¯vw (λw ) as in (4.17) and (4.18). 86 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions 4.2.4 Second Dual Subproblem For the second dual subproblem, given λ, we have max p∈P i∈N λi ln pi + = i∈N j∈N \{i} ln(1−pj ) max λi ln pi + 0≤pi ≤1 j∈N \{i} (4.19) λj ln(1 − pi ) . Since the problem at the right hand side in (4.19) is convex, we can apply the first order necessary and sufficient optimization condition to obtain the given optimal solution [62] as follows p∗i (λ) = λi j∈N 4.2.5 λj , if λj = 0. (4.20) j∈N Centralized Algorithm for Random Access We define λci = min{λ ≥ 0 : si (¯ xmin , λ) = i max x ¯in xi ≤¯ xmax i ≤¯ i si (¯ xi , λ)}. (4.21) Thus, x¯∗i (λci ) has two solutions: x¯∗i (λci ) = x¯min and x¯in ¯∗i (λci ) ≤ x¯max . As shown in Fig. i i ≤ x i 4.2, x¯∗i (λi ) is discontinuous at λci . Consider g(λ) = supp∈P,¯x∈X¯ L(p, x ¯, λ), we apply Danskin’s Theorem [19] to find the subdifferential ∂g(λ) (i.e., the set of all subgradients of g(λ)) ∂g(λ) = conv{∇λL(p, x ¯, λ) : p ∈ p∗ (λ), x ¯∈x ¯∗ (λ)}, where conv{H} is the convex hull of set H and ∇λL(p, x ¯, λ) = (4.22) x,λ) ∂L(p,¯ x,λ) , . . . , ∂L(p,¯ ∂λ1 ∂λN T denotes the gradient of L with respect to λ, and the notation (·)T denotes vector transpose operator. Moreover, p∗ (λ) and x ¯∗ (λ) are the solutions of (4.20) and (4.11) at λ for all 87 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions 5 i i x*(λ ) 0 −5 −10 0 0.02 0.04 0.06 λ 0.08 0.1 0.12 0.14 i Figure 4.2: The solution of the first dual subproblem x¯∗i (λi ) versus λi for sigmoidal utility 2 function Ui (x) = x2x+20 . We can see that x¯∗i (λi ) is discontinuous at λi = λci = 0.0780. i ∈ N , respectively. We note that g(λ) is differentiable at λ, because there is only one element in both sets p∗ (λ) and x ¯∗ (λ). This is always true unless ∃ i ∈ N such that λi = λci , because in that case there are two possible solutions for x¯∗i (λci ) as discussed above. Using the subgradient projection method, we update (λi , ∀i ∈ N ) according to the following equation: λi (t + 1) = λi (t) − α(t) c¯i + ln p∗i (λ(t)) + j∈N \{i} + ln(1 − p∗j (λ(t))) − x¯∗i (λi (t)) , (4.23) where [z]+ = max{z, 0} and t is the index of the iteration. With a diminishing step size α(t) ≥ 0 such that limt→∞ α(t) = 0 and ∞ t=1 α(t) = ∞ (e.g., we can choose α(t) = m/t, where m is a positive constant), it can be shown that λi (t) converges to the dual optimal solution λ∗i as t → ∞ [19]. The algorithm to solve problem (4.6) is shown in Algorithm 4.1. In the algorithm, we initialize the variables in lines 1 to 3, and update the variables p∗ , x ¯∗ and λ in lines 4 to 10. Notice that the subgradient method is usually used without any 88 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions Algorithm 4.1 Centralized Algorithm to Solve Problem (4.6). 1: Input: ci , xmin , xmax , ∀i ∈ N i i in 2: Calculate x ¯i , ∀ i ∈ N 3: Set t := 1 and initialize λi (t) > 0, ∀ i ∈ N 4: while t < MAXIT ER 5: Set p∗i (λ(t)) := λi (t)λj (t) , ∀i ∈ N j∈N xi , λi (t)) 6: Set x¯vi (λi (t)) := arg max si (¯ Set 7: 8: 9: 10: 11: x¯∗i (λi (t)) x ¯in xi ≤¯ xmax i ≤¯ i := arg max si (¯ xi , λi (t)) x ¯i ∈{¯ xmin ,¯ xvi (λi (t))} i Set λi (t + 1) as in (4.23) with α(t) := m/t, where m > 0 Set t := t + 1 end while Output: p∗ and x ¯∗ . formal stopping criterion, so we run our algorithm for a pre-specified number of iterations MAXIT ER. We will discuss the optimality of its solution in the next section. 4.2.6 General Optimality Conditions We have the following general optimality condition for the dual problem in (4.9): Theorem 4.1 Vector λ∗ is the solution of problem (4.9) if and only if λ∗ 0 and 1. If λ∗i = 0, we have c¯i + ln p∗i (λ∗ ) + j∈N \{i} ln(1 − p∗j (λ∗ )) − x¯vi (λ∗i ) ≥ 0. (4.24) ln(1 − p∗j (λ∗ )) − x¯vi (λ∗i ) = 0. (4.25) 2. If λ∗i > 0 and λ∗i = λci , we have c¯i + ln p∗i (λ∗ ) + j∈N \{i} 89 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions 3. If λ∗i > 0 and λ∗i = λci , we have c¯i + ln p∗i (λ∗ ) + j∈N \{i} ln(1 − p∗j (λ∗ )) − x¯vi (λ∗i ) ≤ 0, (4.26) ln(1 − p∗j (λ∗ )) − x¯min ≥ 0. i (4.27) and c¯i + ln p∗i (λ∗ ) + j∈N \{i} Proof : First, for dual feasibility, we have λ∗ 0. For cases 1 and 2, g(λ)i is differentiable at λi = λ∗i , where g(λ)i is the ith element in g(λ). The ith entry of the derivative becomes ∇g(λ∗)i = c¯i + ln p∗i (λ∗ ) + j∈N \{i} ln(1 − p∗j (λ∗ )) − x¯vi (λ∗i ). (4.28) Since problem (4.9) is convex, the result directly follows from [21, pp. 142]. For case 3, g(λ)i is non-differentiable at λi = λ∗i ; therefore, the KKT condition is 0 ∈ ∂g(λ∗ )i . From (4.22), we have ∂g(λ∗ )i = conv{¯ ci + ln p∗i (λ∗ ) + = c¯i + ln p∗i (λ∗ ) + c¯i + ln p∗i (λ∗ ) + j∈N \{i} ln(1 j∈N \{i} − p∗j (λ∗ )) − x¯∗i : x¯∗i ∈ x¯∗i (λ∗i )} ln(1 − p∗j (λ∗ )) − x¯vi (λ∗i ), j∈N \{i} ln(1 (4.29) , − p∗j (λ∗ )) − x¯min i which is simply an interval. Considering the lower and upper bounds in the interval, we can directly derive (4.26) and (4.27), respectively. Since the dual problem is convex, the KKT conditions (4.24)-(4.27) are necessary and sufficient [21, p. 139]. By using the following theorem, we can determine whether Algorithm 4.1 can solve the NUM problem. Theorem 4.2 If λ∗i = λci , ∀i ∈ N , then Algorithm 4.1 finds the optimal solution of problem (4.6). 90 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions Proof : If λ∗i = λci , ∀ i ∈ N , from the discussion in Section 4.2.5, p∗ = p∗ (λ∗ ) and x ¯∗ = x ¯∗ (λ∗ ) form the unique minimizer of Lagrangian L(p, x ¯, λ∗ ). Thus g(λ) is differentiable at λ∗ by (4.22). Finally, from [20, Property 6.5(c)], the primal problem (4.6) has a saddle point (p∗ , x ¯∗ , λ∗ ). By [20, Theorem 5.3], p∗ and x ¯∗ are the global optimum of the primal problem (4.6). 4.3 Optimality and Sub-optimality In this section, we assume that xmax = ci , ∀ i ∈ N such that the optimal value of the i objective function is restricted by capacity c = (ci , i ∈ N ) only, but not the data rate , i ∈ N ). Next, we discuss certain conditions on vector c which affect bound xmax = (xmax i optimality and sub-optimality of Algorithm 4.1. 4.3.1 Optimal Solution We first provide a sufficient condition on the link capacities for optimality of Algorithm 4.1: Theorem 4.3 With xmax = ∞, suppose λci and x¯vi (λci ) are obtained by (4.21) and (4.13) i for any i ∈ N , respectively. We define v cci = p∗i (λc ) c ex¯i (λi ) , ∗ c j∈N \{i} (1 − pj (λ )) ∀i ∈ N, (4.30) where p∗i (λc ) is as in (4.20). Here, cc denotes the vector of critical link capacities. If c ≻ cc , then Algorithm 4.1 can obtain the optimal solution in problem (4.6), and thus that of problem (4.5). 91 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions Proof : Let λ∗ be the dual optimal solution and assume that c ≻ cc . From (4.30), we have c¯i + ln p∗i (λc ) + j∈N \{i} ln(1 − p∗j (λc )) − x¯vi (λci ) > 0, for any i ∈ N . We can further show that 0∈ / ∂g(λc )i = [¯ ci + ln p∗i (λc ) + c¯i + ln p∗i (λc ) + j∈N \{i} ln(1 − p∗j (λc )) − x¯vi (λci ), (4.31) ∗ c ¯min ]. i j∈N \{i} ln(1 − pj (λ )) − x Thus, λ∗i = λci , ∀ i ∈ N . By Theorem 4.2, Algorithm 4.1 finds the optimum of problem (4.5). The key idea in the proof is that if c ≻ cc , λ∗i < λci , ∀ i ∈ N , then the optimality of the solution directly results from Theorem 4.2. 4.3.2 Sub-optimal Solution: Upper and Lower Bounds Next, assume that c cc . In this case, Algorithm 4.1 may only obtain a sub-optimal solution. For cases other than c ≻ cc and c cc , Algorithm 4.1 may obtain an optimal or sub-optimal solution depending on the exact scenario. Notice that x ¯∗ (λ) and p∗ (λ) obtained from lines 5 to 7 of Algorithm 4.1 always satisfy the second and third constraints in problem (4.6), respectively. By Theorem 4.1, the first constraint can be satisfied in all the three cases in (4.24), (4.25), and (4.27). That is, for the case λ∗i > 0 and λ∗i = λci , we . By weak duality [21, pp. 225], we can obtain an upper bound for will choose x¯∗i (λi ) = x¯min i the objective value of problems (4.5) and (4.6) as Ui (x∗i ) = i∈N i∈N U¯i (¯ x∗i ) ≤ g(λ∗ ) = L(p∗ (λ∗ ), x ¯∗(λ∗ ), λ∗). (4.32) The first equality is due to the fact that problems (4.5) and (4.6) have the same objective function. The inequality is due to weak duality, and the last equality is by def- 92 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions 1.4 1.2 1 i Minimal Capacity cc (Mbps) Utility Type 1 Utility Type 2 0.8 0.6 0.4 0.2 0 2 4 6 8 10 12 14 16 18 Total Number of Stations N Figure 4.3: The minimal capacities cc1 and cc2 for types of utility functions versus the total number of stations N. Type 1 utility functions are concave, while Type 2 utility functions are sigmoidal. inition. In some cases, we can also obtain a lower bound for problem (4.5). If xi = ci p∗i (λ∗ ) j∈N \{i} (1 − p∗j (λ∗ )) satisfies constraint xmin ≤ xi ≤ xmax , ∀i ∈ N , by the optii i mality of x∗ , we can obtain a lower bound as ¯i (¯ U x∗i ) = i∈N i∈N Ui (x∗i ) ≥ i∈N Ui ci p∗i (λ∗ ) (1 − p∗j (λ∗ )) . j∈N \{i} (4.33) It should be noted that both the upper and lower bounds are constructed from the same p∗ (λ∗ ) and x ¯∗ (λ∗ ) obtained from Algorithm 4.1. When the duality gap is zero, the upper and lower bounds are both equal to the optimal value of the objective function 4.4 i∈N Ui (x∗i ). Performance Evaluations In this section, we consider both cases where c ≻ cc and c cc for Algorithm 4.1. We choose xmin = 0.0001 and xmax = ci , for ∀ i ∈ N . Here, we assume that there are two types i i 93 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions 18 Exhaustive Search Algorithm 1 16 Aggregate Utility 14 12 10 8 6 4 2 0 2 4 6 8 10 12 14 16 18 Total Number of Stations N Figure 4.4: Aggregate utility versus the total number of stations N when c ≻ cc using exhaustive search and Algorithm 4.1. of utility functions used in the network: a concave (Type 1) function U1 (x1 ) = 1−(x1 +1)−1 , and a sigmoidal (Type 2) function U2 (x2 ) = x22 2 x2 +20 , as shown in Fig. 4.1. We can then obtain λc1 = 0.0789 and λc2 = 0.0780 numerically (e.g., using MATLAB as in Fig. 4.2). We assume that there are N stations in the network, where half of them are Type 1, and the other half are Type 2. We plot cc1 and cc2 versus the total number of stations N in Fig. 4.3. We can see that only a linear increase in cc1 and cc2 is required for Algorithm 4.1 to find the optimal solution when N increases. Next, we plot the aggregate utility versus the number of stations in Fig. 4.4 to verify the optimality of Algorithm 4.1 when c ≻ cc . We can see that the result of the exhaustive search is identical to that of Algorithm 4.1, meaning that Algorithm 4.1 obtains the optimal solution. Then, we consider the case where c ≺ cc by using the capacities c = 0.5cc . Fig. 4.5 shows the upper and lower bounds obtained from Algorithm 4.1. Next, we focus on the case when N = 2, c1 = 21 kbps and c2 = 44 kbps to study the resource allocation when c ≺ cc . With the use of diminishing step size α(t) = 0.01/t, the 94 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions 35 Upper Bound Exhaustive Search Lower Bound Aggregate Utility 30 25 20 15 10 5 0 2 4 6 8 10 12 14 16 18 Total Number of Stations N Figure 4.5: Aggregate utility versus the total number of stations N when c ≺ cc using exhaustive search and Algorithm 4.1. The lower and upper bounds are obtained by replacing p∗ (λ∗ ) and x ¯∗ (λ∗ ) (i.e., the results from Algorithm 4.1) into the expressions in (4.33) and (4.32), respectively. We can see that the lower bound is very tight in this case. In fact, except for the case with 14 stations, the lower bound exactly matches the global optimal solution in all other considered cases. allocations of persistent probabilities converge, as shown in Fig. 4.6. Moreover, we have noticed in the simulation that λ1 (t) → λ∗1 = λc1 and λ2 (t) → λ∗2 = λc2 as t → ∞. It can be verified, by simulation, that the use of a constant step size leads to oscillatory behaviour in the dual variables and the allocation of persistent probabilities. 95 Chapter 4. Random Access with Sigmoidal and Concave Utility Functions 0.525 Utility Type 1 Utility Type 2 Allocated Persistent Probability 0.52 0.515 0.51 0.505 0.5 0.495 0.49 0.485 0.48 0.475 0 500 1000 1500 2000 Iteration Figure 4.6: Convergence of the allocation of the persistent probabilities with insufficient capacity c ≺ cc using diminishing step size α(t) = 0.01/t, even though the allocation may not be globally optimal as discussed in Section 4.3. 4.5 Summary In this chapter, we proposed a random access algorithm based on the NUM framework for stations with either concave or sigmoidal utilities. We applied the dual method to solve our problem. A sufficient condition on link capacities that guarantee the optimality of the solution is proposed. Simulations have been performed to verify our analytical results. 96 Chapter 5 Dynamic Optimal Random Access for Vehicle-to-Roadside Communications In this chapter, we aim to design a uplink random access algorithm that is distributed in nature, so that it is compatible with the IEEE 802.11p standard that is developed to facilitate the provision of wireless access in vehicular environment [16, 17]. Different from most previous works on heuristic distributed uplink V2R communication algorithm design, we aim at designing an optimal uplink resource allocation scheme in VANETs analytically. Specifically, we consider the drive-thru scenario [85], where vehicles pass by several APs located along a highway and obtain Internet access for only a limited amount of time. We assume that a vehicle wants to upload a file when it is within the coverage ranges of the APs, and needs to pay for the attempts to access the channel. As both the channel contention level and achievable data rate vary over time, the vehicle needs to decide when to transmit by taking into account the required payment, the application’s QoS requirement, and the level of contention in current and future time slots. Because of the dynamic nature of the problem, we formulate it as a finite-horizon sequential decision problem and solve it using the dynamic programming (DP). The main contributions of this chapter are as follows: • In the case of a single AP with random vehicular traffic, we propose a general dynamic optimal random access (DORA) algorithm to compute the optimal access policy. We 97 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications further extend the results to the case of multiple consecutive APs and propose a joint DORA (JDORA) algorithm to compute the optimal policy. • We consider a special yet practically important case of a single AP with constant data rate. We show that the optimal policy in this case has a threshold structure, which motivates us to propose a low complexity and efficient monotone DORA algorithm. • Extensive simulation results show that our proposed algorithms achieve the minimal total cost and the highest upload ratio as compared with three other heuristic schemes. In the multi-AP scenario, the performance improvements in upload ratio of the JDORA scheme are 130% and 207% at low and high traffic density, respectively. The rest of this chapter is organized as follows. We present the related work in Section 5.1. We describe our system model in Section 5.2 and formulate the DP problem in Section 5.3. The general and monotone DORA algorithms for single AP are proposed in Section 5.4.1, and the JDORA algorithm for multiple APs is discussed in Section 5.4.2. Simulation results are given in Section 5.5, and a summary is given in Section 5.6. A list of the key notations used in this chapter is given in Table 5.1. 98 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications Table 5.1: List of Key Notations Notation λ ρ, ρmax ν, νf j, J Rj P γ W N0 /2 dt ∆t ∆tdata t, Tj , T Tj a, A S, s, S psucc , psucc ,P t qj wt lt δt (·) π, Π h(·) σ n, nt , Nj Nmax,j gj (·) ζ(j, τ ) ct cˆ vt (s, psucc ) ψt (s, psucc , a) K, pr , F Meaning Arrival rate of the vehicles Density of the vehicles and density of the vehicles during traffic jam Speed and free-flow speed of the vehicles Index of an AP and its feasible set Transmission radius of the j th AP Transmit power of the vehicle Path loss exponent Channel bandwidth Power spectral density of the Gaussian noise Distance between the vehicle and the closest AP at time slot t Length of a time slot Length of time in a time slot for data transmission Time slot, its feasible set in the j th coverage range, and its overall feasible set Total number of time slots that the vehicle stays within the j th coverage range Action and its feasible set Total file size, remaining file size to be uploaded, and its feasible set Probability of successfully gaining access to the time slot, its value at time slot t, and its feasible set Payment per time slot in the j th coverage range Data rate at time slot t Number of vehicles leaving the j th coverage range at time slot t ∈ Tj Decision rule at time slot t Transmission policy and its feasible set Self-incurred penalty Granularity of discrete state element s in the algorithms Number of vehicles in the coverage range, its value at time slot t, and its feasible set in the j th coverage range Maximum number of vehicles that can be accommodated in the j th coverage range A function used by the j th AP that maps n to psucc A function that maps the τ th time slot in the j th coverage range to the time line as shown in Fig. 5.2 Cost at time slot t Terminal cost Minimal expected total cost in state (s, psucc ) from time t over the planning horizon Expected total cost in state (s, psucc ) from time t over the planning horizon if action a is chosen MAC parameters in the MCBC scheme [86] 99 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications 5.1 Related Work Several centralized and distributed resource allocation schemes have been proposed for VANETs. In the centralized setting, the AP schedules the transmissions from different vehicles based on some predefined criteria. Hadaller et al. in [87] proposed a scheduling protocol that grants channel access to a vehicle that achieves the maximum transmission rate. Analytical and simulation results showed significant overall system throughput improvement over a benchmark scheme. Chang et al. in [88] proposed a heuristic downlink scheduling algorithm for dedicated short range communication (DSRC) networks. It aims to reduce the handoff rate under some delay constraints of the vehicles. Based on a metric which measures the chance that a vehicle can be served completely within the coverage range of an AP, the algorithm divides the vehicles into two priority classes for scheduling. Zhang et al. in [89] considered the case where roadside APs only store the data uploaded by the vehicles. Scheduling priority is determined by two factors: data size and deadline. A request with either a smaller data size or an earlier deadline will be served first. Alcaraz et al. in [90] considered both uplink and downlink scheduling of non-real-time traffic for non-safety applications. The scheduling problem was formulated as a constrained linear quadratic regulator design problem that aims to reduce the residual queue backlog for each user. However, because centralized resource allocation is not scalable due to its computational complexity, we focus on distributed resource allocation scheme in this chapter. In the distributed setting, the vehicles contend for the channel for transmission based on the applications’ QoS requirements. Yang et al. in [91] proposed a cross-layer protocol called coordinated external peer communication for multi-hop V2R communications. The roads are divided into segments such that the vehicles are divided into clusters. Information is aggregated and passed between cluster heads. Shrestha et al. in [92] considered the scenario where the data packets are first distributed from the roadside units (RSUs) 100 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications to the onboard units (OBUs). The OBUs then bargain with each other for the missing data packets, and exchange them using BitTorrent protocol. Jarupan et al. in [93] proposed a cross-layer protocol for V2R multi-hop communication. The MAC module collects information of local data traffic, and the routing module finds a path with the minimum delay. Niyato et al. in [94] proposed a hierarchical optimization framework for downlink data streaming in V2R communications. The optimal pricing and bandwidth reservation of a service provider is obtained using game theory, and the optimal download policy of an OBU is obtained using constrained Markov decision processes. Sikdar in [95] proposed a V2R protocol, where the AP first obtains an estimate of the number of active nodes in the network, and then uses it to determine the optimal number of data contention slots. An information-theoretic lower bound on the MAC layer overhead was derived related to node reassociations induced by the mobility of the nodes. Tan et al. in [96] analyzed the performance of a downlink resource allocation scheme in a V2R communication system with one AP on a road. The resources are equally shared among all the vehicles that are within the coverage range of the AP. The distribution of the number of bytes downloaded per drive-thru was derived using Markov reward processes. Roman et al. in [86] proposed a cross-layer protocol in the physical and MAC layers that addresses the issues of channel fading, synchronization, and channel contention. Performance analysis was presented for the channel contention scheme, and a testbed was used to evaluate the proposed protocol. 5.2 System Model We consider a drive-thru scenario on a highway as shown in Fig. 5.1, where multiple APs are installed and connected to a backbone network to provide Internet services to vehicles within their coverage ranges. We focus on a vehicle that wants to upload a single file of size S when it moves through a segment of this highway with a set of APs J = {1, . . . , J}, 101 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications Figure 5.1: Drive-thru V2R communications with multiple APs. where the vehicles pass through the ith AP before the j th AP for i < j with i, j ∈ J . We assume that the j th AP has a transmission radius Rj . We also assume that the vehicle is connected to at most one AP at a time. If the coverage areas of the APs are overlapping, then proper handover between the APs will be performed [97]. For the ease of exposition, we assume that the APs are set up in a way that any position in this segment of highway is covered by an AP. Our work can easily be extended to consider the settings where the coverage areas of adjacent APs are isolated from each other. 5.2.1 Traffic Model Let λ denote the average number of vehicles passing by a fixed AP per unit time. We assume that the number of vehicles moving into this segment of the highway follows a Poisson process [98] with a mean arrival rate λ. Let ρ denote the vehicle density representing the number of vehicles per unit distance along the road segment, and ν be the speed of the vehicles. From [99], we have λ = ρν. (5.1) 102 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications The relation between the vehicle density ρ and speed ν is given by the following equation [99]: ν = νf (1 − ρ/ρmax ), (5.2) where νf is the free-flow speed when the vehicle is moving on the road without any other vehicles, and ρmax is the vehicle density during traffic jam. As we are studying the traffic flow in steady state, all the vehicles within the coverage range are assumed to move with the same speed ν in (5.2). Let ⌊·⌋ denote the floor function. The maximum number of vehicles that can be accommodated within the coverage range of the j th AP is given by Nmax,j = ⌊2Rj ρmax ⌋ , 5.2.2 ∀j ∈ J. (5.3) Channel Model Wireless signal propagations suffer from path loss, shadowing, and fading. Since the distance between the vehicle and the AP varies in the drive-thru scenario, we focus on the dominant effect of channel attenuation due to path loss. The data rate at time slot t is given by wt = W log2 1 + P N0 W dγt , (5.4) where W is the channel bandwidth, P is the transmit power of the vehicle, dt is the distance between the vehicle and the closest AP at time slot t, and γ is the path loss exponent. We assume that the additive white Gaussian noise has a zero mean and a power spectral density N0 /2. In addition, we also consider a special case with fixed data rate in Section 5.4.1. 103 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications ζ(1,1) ζ(1,2) Ϯ ϭ ζ(1,10) ζ(2,1) ϭϬ ϭϮ ƚŝŵĞ ƐůŽƚƐ ŝŶ W ϯ ϭϱ ƚŝŵĞ ƐůŽƚƐ ŝŶ W Ϯ ϭϬ ƚŝŵĞ ƐůŽƚƐ ŝŶ W ϭ ζ(2,15) ζ(3,1) ϭϭ Ϯϱ Ϯϲ ζ(3,12) dŝŵĞ ϯϳ ȴƚ Figure 5.2: An example of the time line representation for the events happened with three APs (i.e., J = {1, 2, 3}). Here, we assume that T1 = 10, T2 = 15, and T3 = 12. With respect to the time line, we have T1 = {1, . . . , 10}, T2 = {11, . . . , 25}, and T3 = {26, . . . , 37}. j−1 It is clear from the figure that ζ(j, τ ) = i=0 Ti + τ, ∀ τ ∈ {1, . . . , Tj }, where T0 = 0. 5.2.3 Distributed Medium Access Control We consider a slotted MAC protocol, where time is divided into equal time slots of length ∆t. We assume that there is perfect synchronization between the APs and the vehicles with the use of global positioning system (GPS) [18]. The total number of time slots that the vehicle stays within the coverage range of the j th AP is Tj = 2Rj ν∆t . We use the notation ζ(j, τ ) to denote the τ th time slot when the vehicle is in the coverage area of the j th AP, i.e., j−1 Ti + τ, ζ(j, τ ) = i=0 ∀ τ ∈ {1, . . . , Tj }, (5.5) where T0 = 0. The set of time slots in the j th AP with respect to this time line representation is Tj = {ζ(j, 1), . . . , ζ(j, Tj )}. An example of the time line representation is given in Fig. 5.2. When the vehicle first enters the coverage range of the j th AP, it declares the type of its application to the AP. In return, the j th AP informs the vehicle the channel contention in the coverage range (λ and psucc , ∀ t ∈ Tj ), data rate in all the time slots in the j th coverage t range (i.e., wt , ∀ t ∈ Tj ), the price qj , and the estimated number of vehicle departures from 104 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications the coverage range in all the time slots in the j th coverage range (i.e., lt , ∀ t ∈ Tj ). We further elaborate these system parameters as follows: • psucc represents the probability that the vehicle can successfully obtain access in time t slot t ∈ Tj after contending with all the vehicles in the j th coverage range. psucc is t estimated by the AP based on the level of system contention and it varies over time. Since psucc is related to the number of vehicles nt currently in the j th coverage range t at time slot t, we define psucc = gj (nt ), where gj is a strictly decreasing function. t An AP knows the value of nt , since vehicles need to establish and terminate their connections when they enter and leave the coverage range, respectively. • qj ≥ 0 denotes the amount (e.g., in virtual currency) that a vehicle needs to pay the AP for each time slot that it sends a transmission request in the j th coverage range, even it fails to access the channel. The value of qj does not change over time. Moreover, in order to provide QoS support, an AP may charge differently for vehicles running different types of applications. • lt represents the number of vehicle departing at time slot t ∈ Tj from the j th coverage range. Since all the vehicles move with constant speed ν in the traffic model, we assume that (lt , ∀ t ∈ Tj ) are accurately known by the j th AP, and are sent to the vehicle when it enters the coverage range. In each time slot t ∈ Tj in the j th coverage range, the j th AP first broadcasts the value of psucc to all the vehicles in its coverage range. If a vehicle decides to transmit t within this time slot, it sends a request to the j th AP at its scheduled mini-slot, where Nmax,j mini-slots are reserved for transmission requests. The transmissions of requests are thus collision-free. After collecting the requests from all vehicles in its coverage range, the j th AP assigns the time slot to one of these vehicles. The vehicle, which receives the 105 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications W ďƌŽĂĚĐĂƐƚƐ ƚŚĞ ǀĂůƵĞ ŽĨ ƉƚƐƵĐĐ W ƐĞŶĚƐ < ĂƚĂ ȴƚĚĂƚĂ EŵĂǆ͕ũ ŵŝŶŝͲƐůŽƚƐ ĨŽƌ ƚƌĂŶƐŵŝƐƐŝŽŶ ƌĞƋƵĞƐƚƐ ȴƚ Figure 5.3: The structure of a time slot of the j th AP. acknowledgement (ACK), can transmit the data packets in the remaining time ∆tdata of this time slot, where ∆tdata < ∆t. The structure of a time slot is shown in Fig. 5.3. Meanwhile, regardless of which vehicle is granted the time slot, each vehicle which requested to transmit in the time slot needs to pay qj to the j th AP. Without such pricing, each vehicle would send a request in every time slot, which unnecessarily increases the contention level and prevents efficient allocation of time slots to the most needed application. The vehicle aims to achieve a good tradeoff between the total uploaded file size and the total payment to the APs according to the QoS requirement of the application. For example, a higher priority may be placed on the total uploaded file size for safety applications, but on the total payment for non-safety applications. The problem is further complicated by the time-varying data rate wt and channel contention level. Therefore, it is a challenge for the vehicle to decide when to request for data transmission. 5.3 Problem Formulation In this section, we formulate the optimal transmission problem of a single vehicle as a finite-horizon sequential decision problem [28]. The decision epochs of the vehicle are t∈T = j∈J Tj = ζ(j, 1), . . . , ζ(j, Tj ) , (5.6) j∈J 106 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications where T is the set of all the time slots in the total of J coverage ranges. The system state of a vehicle is defined as (s, psucc), where the state element s ∈ S = [0, S] represents the remaining size (in bits) of the single file to be uploaded. If we denote the number of vehicles in the coverage range of the j th AP as n ∈ Nj = {1, . . . , Nmax,j }, then psucc ∈ Pj = {gj (n) : n ∈ Nj }. At any state (s, psucc ), the vehicle has two possible actions: a ∈ A = {0, 1}, (5.7) where action a = 1 implies that the vehicle decides to request to transmit, and action a = 0 otherwise. The cost at state (s, psucc) with action a ∈ A at time slot t ∈ Tj in the j th coverage range is ct (s, psucc, a) = aqj , ∀ t ∈ Tj . (5.8) After the vehicle has left the J th coverage range at time ζ(J, TJ + 1), we define a self-incurred penalty of the vehicle for not being able to complete the file uploading as cˆζ(J,TJ +1) (s, psucc) = h(s), (5.9) where h(s) ≥ 0 is a nondecreasing function of s with h(0) = 0. The function depends on the QoS requirement of the application. To sum up, each vehicle is incurred with two costs: the transmission cost in each time slot in (5.8) and the penalty after leaving the J th coverage range in (5.9). ′ The state transition probability pt (s′ , psucc ) | (s, psucc), a is the probability that the ′ system will go into state (s′ , psucc ) if action a is taken at state (s, psucc ) at time slot t ∈ T. ′ Since the transition from psucc to psucc is independent of the value of s but depends on 107 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications time t, we have ′ ′ pt (s′ , psucc ) | (s, psucc), a = pt s′ | (s, psucc), a pt psucc | psucc . (5.10) With action a = 1, we have psucc , if s′ = [s − wt ∆tdata ]+, pt s′ | (s, psucc), 1 = 1 − psucc , if s′ = s, 0, otherwise, (5.11) where [x]+ = max{0, x}. The first and second cases correspond to the scenarios of successful and unsuccessful packet transmissions, respectively. With action a = 0, we have pt s′ | (s, psucc), 0 = 1, if s′ = s, (5.12) 0, otherwise, where the remaining size of the file to upload does not change. The derivation of ′ pt psucc | psucc will be discussed in detail in Section 5.4. Let δt : S × Pj → A be the decision rule that specifies the transmission decision of the vehicle at state (s, psucc ) at time slot t ∈ Tj in the j th coverage range. We define a policy as a set of decision rules covering all the states as π = (δt (s, psucc ), ∀ s ∈ S, psucc ∈ Pj , t ∈ succ,π Tj , ∀ j ∈ J ). We denote (sπ ) as the state at time slot t if policy π is used, and we t , pt let Π be the feasible set of π. The vehicle aims to find an optimal policy that minimizes 108 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications the total expected cost, which can be formulated as the following optimization problem J Tj succ,π succ,π π cζ(j,τ ) sπ ζ(j,τ ) , pζ(j,τ ) , δζ(j,τ ) (sζ(j,τ ) , pζ(j,τ ) ) min Eπ,(S,psucc ) 1 π∈Π j=1 τ =1 (5.13) succ,π + cˆζ(J,TJ +1) (sπ ζ(J,TJ +1) , pζ(J,TJ +1) ) , where Eπ,(S,psucc ) denotes the expectation with respect to the probability distribution by 1 policy π with an initial state (S, psucc ) at time slot t = ζ(1, 1) = 1. In the following section, 1 we will study two scenarios: single AP with random vehicular traffic and multiple APs with traffic pattern estimation. 5.4 Finite-Horizon Dynamic Programming In this section, we describe how to obtain the optimal transmission policies in both the single-AP and multiple-AP scenarios using finite-horizon dynamic programming. We first study the single-AP scenario with random vehicular traffic arrival in Section 5.4.1. In particular, we consider a special case that the optimal policy has a threshold structure in Section 5.4.1. When the traffic pattern can be estimated accurately, we consider a joint AP optimization in Section 5.4.2. 5.4.1 Single AP Optimization with Random Vehicular Traffic Since we are considering one AP (i.e., J = {1}) in this subsection, we drop the subscript j for simplicity. Although the exact traffic pattern (i.e., the exact number of vehicles in the coverage range of the AP in each time slot) is not known, the vehicles arrive according to a Poisson process with parameter λ. Meanwhile, the parameters lt (∀ t ∈ T ), ρmax , ∆t, 109 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications R, and the function g(·) are available. The transition probability of psucc is given by pt p succ′ |p succ where φt (n) = ′ ′ = pt g(n ) | g(n) = pt n | n = Nmax −n+lt+1 (λ∆t)y y=0 y! ′ (λ∆t)n −n+lt+1 , (n′ −n+lt+1 )! φt (n) 0, if n − lt+1 ≤ n′ ≤ Nmax , otherwise, (5.14) is a normalization factor. Because psucc = g(n) is a strictly decreasing function of n, there is a one-to-one mapping between psucc and n as shown in the first two equalities in (5.14). The expression after the third equalities describes the probability with n′ − n + lt+1 arrivals due to the Poisson process and lt+1 deterministic departures at time t + 1. n′ is lower-bounded by n − lt+1 ≥ 0 when there is no vehicle arrival, and is upper-bounded by Nmax . In this subsection, since we consider J = {1}, we can simplify problem (5.13) as T succ,π succ,π succ,π ct sπ , δt (sπ ) + cˆT +1 (sπ t , pt t , pt T +1 , pT +1 ) . min Eπ,(S,psucc ) 1 π∈Π (5.15) t=1 Let vt (s, psucc) be the minimal expected total cost that the vehicle has to pay from time t to time T + 1 when it is in the coverage range, given that the system is in state (s, psucc) immediately before the decision at time slot t ∈ T . The optimality equation [28, pp. 83] relating the minimal expected total cost at different states for t ∈ T is vt (s, psucc) = min{ψt (s, psucc, a)}, a∈A (5.16) 110 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications where ′ ′ pt (s′ , psucc ) | (s, psucc), a vt+1 (s′ , psucc ) (5.17) ψt (s, psucc, a) = ct (s, psucc, a) + s′ ∈S psucc′ ∈P ′ = aq + psucc′ ∈P pt psucc | psucc apsuccvt+1 [s − wt ∆tdata ]+ , psucc ′ ′ + 1 − apsucc vt+1 (s, psucc ) . (5.18) The first and second terms on the right hand side of (5.17) are the immediate cost and the expected future cost in the remaining time slots in the coverage range for choosing action a, respectively. Equation (5.18) follows directly by evaluating (5.17) using (5.10) - (5.12). For time t = T + 1, we have the boundary condition that vT +1 (s, psucc) = cˆT +1 (s, psucc ) = h(s). (5.19) Lemma 5.1 The value of ψt (s, psucc , a), ∀ t ∈ T , can be obtained as Nmax −n+lt+1 ψt (s, p succ , a) = aq + m=0 (λ∆t)m apsucc vt+1 [s − wt ∆tdata ]+ , g(n + m − lt+1 ) m!φt (n) + 1 − apsucc vt+1 s, g(n + m − lt+1 ) , (5.20) where n = g −1(psucc ) is the number of vehicles in the coverage range of the AP. Proof : The result follows directly by evaluating (5.18) using (5.14). Intuitively, the minimal expected cost vt (s, psucc) should be smaller when the remaining file size s to be uploaded is smaller. It is confirmed by the following lemma: Lemma 5.2 vt (s, psucc) is a nondecreasing function in s, ∀ psucc ∈ P, t ∈ T . 111 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications Proof : We prove it by induction. From (5.19), since vT +1 (s, psucc) = h(s), vT +1 (s, psucc ) is a nondecreasing function in s, ∀ psucc ∈ P. Assume that vt+1 (s, psucc) is a nondecreasing ′ function in s, ∀ psucc ∈ P. Since pt psucc | psucc ≥ 0 and 0 ≤ apsucc ≤ 1, it can be inferred from (5.18) that ψt (s, psucc, a) is a nondecreasing function in s, ∀ psucc ∈ P. Thus, vt (s, psucc) in (5.16) is a nondecreasing function in s, ∀ psucc ∈ P. Using the optimality equation and backward induction [28, pp. 92], we propose the general dynamic optimal random access (DORA) algorithm in Algorithm 5.1 to obtain the optimal policy π ∗ = (δt∗ (s, psucc), ∀ s ∈ S, psucc ∈ P, t ∈ T ), where δt∗ (s, psucc) = arg min{ψt (s, psucc , a)}. (5.21) a∈A Theorem 5.1 The policy π ∗ obtained from Algorithm 5.1 is the optimal solution of problem (5.15). Proof : Using the principle of optimality [29, pp. 18], we can show that π ∗ is the optimal solution of problem (5.15). The proposed DORA algorithm consists of two phases: Planning phase and transmission phase. The planning phase starts when the vehicle enters the coverage range. The vehicle then obtains information from the AP and computes the optimal policy π ∗ offline using dynamic programming. In fact, π ∗ is a contingency plan that contains information about the optimal decisions at all possible states (s, psucc) in the coverage range. In the transmission phase, the transmission decision in each time slot is made according to the optimal policy π ∗ , and s is updated depending on whether the time slot is granted to the vehicle for transmission or not. Note that the computational complexity of the algorithm is directly proportional to the dimension of the optimal policy, which is given by |S|×|P|×T . 112 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications Algorithm 5.1 General DORA Algorithm for single AP optimization (i.e., problem (5.15)). 1: Planning Phase: 2: Input the traffic parameters: ν, λ, ρmax , lt (∀ t ∈ T ); 3: Input the system parameters: h(·), S, R, wt (∀ t ∈ T ), q, ∆t, ∆tdata , σ, g(·); 4: Set the boundary condition vT +1 (s, psucc ), ∀ s ∈ S, ∀ psucc ∈ P using (5.19); 5: t := T ; 6: while t ≥ 1 7: for psucc ∈ P 8: s := 0; 9: while s ≤ S 10: Calculate ψt (s, psucc, a), ∀ a ∈ A = {0, 1} using (5.20); 11: δt∗ (s, psucc ) := arg min{ψt (s, psucc, a)}; a∈A 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: vt (s, psucc) := ψt s, psucc, δt∗ (s, psucc ) ; s := s + σ; end while end for t := t − 1; end while Output the optimal policy π ∗ for use in the transmission phase; Transmission Phase: t := 1 and s := S; while t ≤ T Receive the information of psucc from the AP; Set action a := δt∗ (s, psucc ) based on the policy π ∗ ; If action a = 1 Send a request to the AP; If ACK is received from the AP Transmit packets with total size wt ∆tdata ; s := [s − wt ∆tdata ]+ ; end if end if t := t + 1; end while Special Case: Convex Penalty Function and Fixed Data Rate In this subsection, we further investigate a special yet practically important case with convex penalty function and non-adaptive data rate [96]. The key idea is that if the self113 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications incurred penalty function h(s) is convex and the data rate wt is fixed within the coverage range (i.e., wt = w, ∀ t ∈ T ), we can show that ψt (s, psucc , a) is submodular [28, pp. 103] on S × A, ∀ t ∈ T , which is defined as follows. Definition 5.1 Given psucc , the function ψt (s, psucc , a) is submodular on S × A if for sˆ, sˇ ∈ S and a ˆ, a ˇ ∈ A, where sˆ ≥ sˇ and a ˆ≥a ˇ, we have ψt (ˆ s, psucc, a ˆ) + ψt (ˇ s, psucc, a ˇ) ≤ ψt (ˆ s, psucc, a ˇ) + ψt (ˇ s, psucc , a ˆ). (5.22) Furthermore, with δt∗ (s, psucc ) as defined in (5.21), we can establish the threshold structure of the optimal policy [28, 100, 101]. The details of the derivation of the threshold policy are as follows. Because wt = w, ∀ t ∈ T , we let ω = w∆tdata . Since δt∗ (s, psucc ) is defined as in (5.21), we can establish the threshold policy if we can prove that ψt (s, psucc, a) is submodular on S ×A, ∀ t ∈ T [28, pp. 104, 115]. The following results from Lemma 5.3 and 5.4 establish the submodularity of ψt (s, psucc, a). First, Lemma 5.3 shows that vt (s, psucc) has a nondecreasing difference in s if h(s) is a convex and nondecreasing function. Lemma 5.3 If h(s) is a convex and nondecreasing function in s, then vt (s, psucc) − vt [s − ω]+ , psucc ≥ vt [s − σ]+ , psucc − vt [s − σ − ω]+ , psucc , ∀ s ∈ S, p succ (5.23) ∈ P, t ∈ T ∪ {T + 1}. Proof : We prove it by induction. Since h(s) is a nondecreasing convex function, we have h(s) − h([s − ω]+ ) ≥ h([s − σ]+ ) − h([s − σ − ω]+ ), ∀ s ∈ S. (5.24) 114 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications Let s ∈ S, psucc ∈ P be given. For t = T + 1, we have vT +1 (s, psucc ) − vT +1 [s − ω]+ , psucc = h(s) − h [s − ω]+ ≥ h([s − σ]+ ) − h([s − σ − ω]+ ) = vT +1 ([s − σ]+ , psucc) − vT +1 [s − σ − ω]+ , psucc , (5.25) where the equalities are due to (5.19) and the inequality is due to (5.24). Assume that for a given t ∈ T , we have vt+1 (s, psucc) − vt+1 [s − ω]+ , psucc ≥ vt+1 [s − σ]+ , psucc − vt+1 [s − σ − ω]+ , psucc , ∀ s ∈ S, psucc ∈ P. (5.26) From (5.16), let actions a1 , a2 , a3 , and a4 be defined such that vt (s, psucc ) = min{ψt (s, psucc , a)} = ψt (s, psucc , a1 ), a∈A (5.27) vt [s − ω]+ , psucc = min{ψt [s − ω]+ , psucc , a } = ψt [s − ω]+ , psucc , a2 , (5.28) a∈A + succ + succ vt [s − σ] , p vt [s − σ − ω] , p = min{ψt [s − σ]+ , psucc, a } = ψt [s − σ]+ , psucc, a3 , (5.29) a∈A = min{ψt [s − σ − ω]+ , psucc, a } a∈A = ψt [s − σ − ω]+ , psucc, a4 . (5.30) 115 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications We thus have vt (s, psucc) − vt [s − ω]+ , psucc − vt [s − σ]+ , psucc + vt [s − σ − ω]+ , psucc = ψt (s, psucc, a1 ) − ψt [s − ω]+ , psucc, a2 − ψt [s − σ]+ , psucc, a3 + ψt [s − σ − ω]+ , psucc , a4 A B = ψt (s, psucc, a1 ) − ψt [s − σ]+ , psucc , a1 + ψt [s − σ]+ , psucc , a1 − ψt [s − σ]+ , psucc , a3 C + − ψt [s − ω] , p succ , a2 + ψt [s − ω]+ , psucc, a4 D − ψt [s − ω]+ , psucc, a4 − ψt [s − σ − ω]+ , psucc, a4 = A + B + C − D. (5.31) We have ′ ′ A= psucc′ ∈P ′ pt psucc | psucc a1 psucc vt+1 ([s − ω]+ , psucc ) − vt+1 ([s − σ − ω]+ , psucc ) ′ ′ + 1 − a1 psucc vt+1 (s, psucc ) − vt+1 ([s − σ]+ , psucc ) ≥ ≥ ′ psucc′ ∈P ′ ′ ′ psucc′ ∈P ′ pt psucc | psucc vt+1 ([s − ω]+ , psucc ) − vt+1 ([s − σ − ω]+ , psucc ) ′ pt psucc | psucc a4 psucc vt+1 ([s − 2ω]+ , psucc ) − vt+1 ([s − σ − 2ω]+ , psucc ) ′ ′ + 1 − a4 psucc vt+1 ([s − ω]+ , psucc ) − vt+1 ([s − σ − ω]+ , psucc ) = D, (5.32) where the two equalities are obtained by using (5.18) and the two inequalities are due to the induction hypothesis in (5.26). From (5.29) and (5.28), we have B ≥ 0 and C ≥ 0, respectively. Overall, from (5.31), we obtain vt (s, psucc) − vt [s − ω]+ , psucc − vt [s − σ]+ , psucc + vt [s − σ − ω]+ , psucc ≥ 0, (5.33) 116 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications which completes the proof. Lemma 5.4 shows that ψt (s, psucc, a) is submodular if vt (s, psucc ) has a nondecreasing difference in s. Lemma 5.4 If ∀ sˆ, sˇ ∈ S, psucc ∈ P, t ∈ T with sˆ ≥ sˇ, where vt+1 (ˆ s, psucc ) − vt+1 [ˆ s − ω]+ , psucc ≥ vt+1 (ˇ s, psucc ) − vt+1 [ˇ s − ω]+ , psucc , (5.34) then ψt (s, psucc, a) is submodular on S × A, ∀ t ∈ T . Proof : Let sˆ, sˇ ∈ S, a ˆ, a ˇ ∈ A, psucc ∈ P, and t ∈ T be given, where sˆ ≥ sˇ and a ˆ≥a ˇ. Then ψt (ˆ s, psucc, a ˆ) + ψt (ˇ s, psucc , a ˇ) − ψt (ˆ s, psucc , a ˇ) − ψt (ˇ s, psucc , a ˆ) =− ′ psucc′ ∈P ′ pt psucc | psucc psucc(ˆ a−a ˇ) vt+1 (ˆ s, psucc ) − vt+1 [ˆ s − ω]+ , psucc ′ ′ − vt+1 (ˇ s, psucc ) + vt+1 [ˇ s − ω]+ , psucc ′ ≤ 0, (5.35) where the equality is obtained by using (5.18). The inequality at the end is due to the fact ′ that pt psucc | psucc ≥ 0, psucc ≥ 0, aˆ ≥ aˇ, and the given condition in Lemma 5.4. From Definition 5.1 and (5.22), the result follows. Theorem 5.2 If h(s) is a convex and nondecreasing function in s, and the data rate wt is fixed such that wt = w, ∀ t ∈ T , then we have a threshold optimal policy π ∗ = (δt∗ (s, psucc ), ∀ s ∈ S, psucc ∈ P, t ∈ T ) in s as follows: δt∗ (s, psucc) = 1, if s > s∗ (psucc), t (5.36) 0, otherwise, where s∗t (psucc) is the threshold that depends on both psucc and t. 117 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications Proof : Let sˆ, sˇ ∈ S, ω ≥ 0, psucc ∈ P, and t ∈ T be given. Moreover, let sˇ = [ˆ s − kσ]+ , where k > 0. If the condition of the theorem is satisfied, by repetitively applying Lemma 5.3, we have s − σ]+ , psucc − vt [ˆ s − σ − ω]+ , psucc ≥ · · · vt (ˆ s, psucc) − vt [ˆ s − ω]+ , psucc ≥ vt [ˆ + ≥ vt [ˆ s − kσ] , p succ + − vt [ˆ s − kσ − ω] , p succ = vt sˇ, p succ + − vt [ˇ s − ω] , p succ (5.37) . From Lemma 5.4, ψt (s, psucc , a) is submodular on S × A, ∀ t ∈ T . From [28, pp. 104, 115], δt∗ (s, psucc ) is a monotone nondecreasing function in s. Since δt∗ (s, psucc) ∈ A = {0, 1}, δt∗ (s, psucc ) is in the form of (5.36). By modifying Algorithm 5.1, we are ready to propose the monotone DORA algorithm with a lower computational complexity in Algorithm 5.2 using monotone backward induction [28, pp. 111]. Let A˜ ⊆ A be the set of actions that we need to consider in the minimization in line 11 in Algorithm 5.2. When δt∗ (s, psucc ) = 1 and f lag = 0 are satisfied (line 13), which means that the threshold s∗t (psucc ) is reached, set A˜ is reduced from {0, 1} to {1} and the threshold s∗t (psucc ) is recorded (line 14). Then the minimization in line 11 is readily known, since set A˜ = {1} is a singleton. The computational complexity is thus reduced. Moreover, memory can be saved, because we do not need to store the complete optimal policy π ∗ = (δt∗ (s, psucc), ∀ s ∈ S, psucc ∈ P, t ∈ T ). We just need to store the thresholds (s∗t (psucc ), ∀ psucc ∈ P, t ∈ T ), which completely characterize the optimal policy π ∗ as shown in (5.36). 118 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications Algorithm 5.2 Monotone DORA Algorithm for single AP optimization (i.e., problem (5.15)) for the special case with convex penalty function h(s) and fixed data rate wt . 1: Planning Phase: 2: Input the traffic parameters: ν, λ, ρmax , lt (∀ t ∈ T ); 3: Input the system parameters: h(·), S, R, wt (∀ t ∈ T ), q, ∆t, ∆tdata , σ, g(·); 4: Set the boundary condition vT +1 (s, psucc ), ∀ s ∈ S, ∀ psucc ∈ P using (5.19); 5: t := T ; 6: while t ≥ 1 7: for psucc ∈ P 8: Set s := 0, f lag := 0, and A˜ := {0, 1}; 9: while s ≤ S 10: Calculate ψt (s, psucc, a), ∀ a ∈ A˜ using (5.20); 11: δt∗ (s, psucc ) := arg min{ψt (s, psucc, a)}; a∈A˜ 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: vt (s, p ) := ψt s, psucc, δt∗ (s, psucc ) ; if δt∗ (s, psucc ) = 1 and f lag = 0 Set A˜ := {1}, s∗t (psucc) = s, and f lag = 1; end if s := s + σ; end while end for t := t − 1; end while Output the thresholds (s∗t (psucc ), ∀ psucc ∈ P, t ∈ T ) for use in the transmission phase; Transmission Phase: t := 1 and s := S; while t ≤ T Receive the information of psucc from the AP; If s > s∗t (psucc ) Send a request to the AP; If ACK is received from the AP Transmit packets with total size wt ∆tdata ; s := [s − wt ∆tdata ]+ ; end if end if t := t + 1; end while succ 119 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications 5.4.2 Joint AP Optimization with Deterministic Vehicular Traffic In the previous subsection, we consider the optimization problem in a single AP. In this subsection, we extend the result to the case of multiple APs, where we assume that the traffic pattern (i.e., the exact number of vehicles in the coverage ranges of the APs in each time slot) can be estimated accurately. The traffic pattern can be estimated in various ways, such as by installing a traffic monitor at a place before the first AP to observe the actual traffic pattern when the vehicles pass by (e.g., using computer vision [102] and pattern recognition [103]). If the traffic flow reaches the steady state (as discussed in Section 5.2.1), the estimation of the number of vehicles nt at time t ∈ T can be reasonably accurate. As a result, the values of psucc = gj (nt ), ∀ t ∈ T can be obtained accurately. As t an example, we consider that the traffic model is as described in Section 5.2.1, and all the APs have the same transmission radii. After the traffic monitor has estimated the values succ for the remaining of psucc , ∀ τ ∈ T1 for the first coverage range, it can set psucc τ ζ(j,τ ) := pτ coverage ranges j ∈ J \{1}. The optimality equations relating the minimal expected total cost at different time t ∈ T for problem (5.13) are similar to that described in Section 5.4.1, but are simplified because we assume that psucc , ∀ t ∈ T are known. At time t ∈ Tj , we have t vt (s, psucc ) = min{ψt (s, psucc , a)}, t t a∈A (5.38) 120 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications where ψt (s, psucc , a) = ct (s, psucc , a) + t t = aqj + succ pt (s′ , psucc ), a vt+1 (s′ , psucc t+1 ) | (s, pt t+1 ) s′ ∈S succ apt vt+1 [s − wt ∆tdata ]+ , psucc t+1 + 1 − apsucc vt+1 (s, psucc t t+1 ). (5.39) The second line in (5.39) is obtained by using (5.11) and (5.12). After the vehicle has left the Jth coverage range at t = ζ(J, TJ + 1), the boundary condition is vζ(J,TJ +1) (s, psucc ˆζ(J,TJ +1) (s, psucc ζ(J,TJ +1) ) = c ζ(J,TJ +1) ) = h(s). (5.40) The JDORA algorithm for joint AP optimization is given in Algorithm 5.3.In Algorithm 5.3, the vehicle first needs to obtain the values of psucc , ∀ t ∈ T, from the traffic monitor. t In the planning phase, for each s ∈ S and t ∈ T, the optimal decision rule δt∗ (s, psucc ) is t the action that minimizes the expected total cost (line 10), where the expected total cost , a) for all possible actions is calculated (line 9) based on vt+1 obtained (line 11) ψt (s, psucc t in the previous iteration t + 1. After the process is repeated for all t ∈ T (line 6) and s ∈ S (line 8), we obtain the optimal policy π ∗ . In the transmission phase, the transmission decision in each time slot is made according to the optimal policy π ∗ , and it follows the MAC protocol described in Section 5.2.3. ), ∀ s ∈ S, t ∈ T) obtained from Algorithm 5.3 Theorem 5.3 The policy π ∗ = (δt∗ (s, psucc t is the optimal solution of problem (5.13) when psucc , ∀ t ∈ T are accurately known. t Proof : The result follows directly from the principle of optimality [29, pp. 18]. 121 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications Algorithm 5.3 JDORA Algorithm for joint AP optimization (i.e., problem (5.13)). 1: Planning Phase: 2: Input the traffic parameters: ν, psucc (∀ t ∈ T); t 3: Input the system parameters: h(·), S, Rj (∀ j ∈ J ), wt (∀ t ∈ T), qj (∀ j ∈ J ), ∆t, ∆tdata , σ; 4: Set the boundary condition vζ(J,TJ +1) (s, psucc ζ(J,TJ +1) ), ∀ s ∈ S using (5.40); 5: t := ζ(J, TJ ); 6: while t ≥ 1 7: s := 0; 8: while s ≤ S 9: Calculate ψt (s, psucc , a), ∀ a ∈ A = {0, 1} using (5.39); t 10: δt∗ (s, psucc ) := arg min {ψt (s, psucc , a)}; t t a∈A 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: vt (s, psucc ) := ψt s, psucc , δt∗ (s, psucc ) ; t t t s := s + σ; end while t := t − 1; end while Output the optimal policy π ∗ for use in the transmission phase; Transmission Phase: t := 1 and s := S; while t ≤ ζ(J, TJ ) Set action a := δt∗ (s, psucc ) based on the policy π ∗ ; t If action a = 1 Send a request to the AP; If ACK is received from the AP Transmit packets with total size wt ∆tdata ; s := [s − wt ∆tdata ]+ ; end if end if t := t + 1; end while 5.5 Performance Evaluations In this section, we first compare Algorithms 5.1 and 5.3 with three heuristic schemes using the traffic model described in Section 5.2.1 in both the single-AP and multipleAP scenarios. In particular, we study the performance of Algorithm 5.3 under imperfect 122 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications Table 5.2: Simulation Parameters Parameters Number of APs J AP’s transmission radius R Free-flow speed νf Vehicle jam density ρmax Duration of a time slot ∆t Duration for data transmission in a time slot ∆tdata Channel bandwidth W Transmit signal-to-noise ratio N0PW Path loss exponent γ Payment per time slot q Contention window cw ∈ [cwmin , cwmax ] MCBC parameter K (used in [86]) MCBC parameter [p1 p2 , p3 ] (used in [86]) MCBC parameter F (used in [86]) Values 1, 5 100 m 110 km/hr 100 veh/km 0.02 sec 0.018 sec 20 MHz 60 dB 3 1 [1, 8] 3 [0.12, 0.77, 0.86] 15 estimations of the psucc in the multiple-AP scenario. We then study the threshold policies t obtained by Algorithm 5.2. The three heuristic schemes that we consider are as follows. The first heuristic scheme is a greedy algorithm, in which each vehicle sends transmission requests at all the time slots if its file upload is not complete. That is, the greedy algorithm aims to maximize the total uploaded file size. The second heuristic scheme is the exponential backoff algorithm that is similar to the one used in the IEEE 802.11. We have slightly modified it for the system that we consider as follows. Each vehicle has a counter, which randomly and uniformly chooses an initial integer value cnt from the interval [0, cw), where cw is the contention window size. The value of cnt is decreased by one after each time slot. When cnt = 0, the vehicle will send a request. If the vehicle has sent a request in a time slot, the size of cw ∈ [cwmin , cwmax ] will change according to the response from the AP: If an ACK is received from the AP, cw is set to cwmin . Otherwise, cw is doubled until it reaches cwmax . For the DORA, JDORA, greedy, and exponential schemes, we assume that the APs allow the vehicles to share the channel with an equal probability. Therefore, psucc = 1/nt . The t 123 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications Total Uploaded File Size (Mbits) 100 90 80 70 60 50 40 30 Greedy MCBC DORA Exponential Backoff 20 10 0 0 0.5 1 1.5 2 Penalty b Figure 5.4: Total uploaded file size against the penalty parameter b for S = 100 Mbits and ρ = 20 veh/km with a single AP. As b increases, a larger file size is uploaded for the DORA scheme. third heuristic scheme is the MAC protocol in the multi-carrier burst contention (MCBC) scheme [86]. Similar to the greedy scheme, a vehicle will send a request if it has data to send in each time slot. However, the vehicles need to undergo K rounds of contention in each time slot. First, in round r, a vehicle survives the contention with probability pr . Each of these vehicles will choose a random integer in {1, . . . , F }. Vehicles that have chosen the largest number can proceed to round r + 1. The transmission is successful if there is only one vehicle left in round K. Otherwise, packet collision will occur. For the evaluations of all the schemes, we use the convex self-incurred penalty function h(s) = bs2 , ∀ s ∈ S, (5.41) where b ≥ 0 is a constant. The three heuristic schemes are evaluated using a similar transmission phase as in Algorithms 5.1 and 5.3, but with π ∗ in Algorithms 5.1 and 5.3 replaced by the corresponding policies. The simulation parameters are listed in Table 5.2. 124 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications 2000 Total Cost 1500 24% 1000 48% Exponential Backoff MCBC Greedy DORA 500 20 30 40 50 60 Density ρ (veh/km) 70 80 Figure 5.5: Total cost versus traffic density ρ for file size S = 200 Mbits with a single AP. The DORA scheme has the minimal total cost. We first study the impact of penalty parameter b on the total uploaded file size for S = 100 Mbits and ρ = 20 veh/km in one AP. As shown in Fig. 5.4, by increasing b, a larger penalty is incurred on the size of the file not yet uploaded by using Algorithm 5.1. As a result, a larger file size is uploaded to reduce the penalty. Depending on the QoS requirements of different applications, different values of b should be chosen that tradeoff the total uploaded file size and total payment to the AP by a different degree. Taking safety application as an example, it may be more important to maximize the uploaded file size than to reduce the total payment to the APs, so a large value of b should be be chosen. Also, since the transmission policies of the greedy, MCBC, and exponential backoff schemes do not consider the self-incurred penalty in (5.41), their total uploaded file size are independent of b. Next, we plot the total cost against the traffic density ρ for S = 200 Mbits with b = 0.1 for the case of one AP in Fig. 5.5. It is clear that the DORA scheme in Algorithm 5.1 achieves the minimal total cost as stated in Theorem 5.1, with 48% and 24% cost reduction as compared with the exponential backoff scheme at low and high ρ, respectively. To measure the cost effectiveness of the file uploading for the four schemes, we propose a 125 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications 0.6 DORA Exponential Backoff Greedy MCBC 17% 0.55 0.5 Upload Ratio 0.45 0.4 0.35 0.3 0.25 0.2 77% 0.15 0.1 20 30 40 50 60 Density ρ (veh/km) 70 80 Figure 5.6: Upload ratio (i.e., total uploaded file size / total payment to the APs) versus traffic density ρ for file size S = 200 Mbits with a single AP. The DORA scheme achieves the highest upload ratio. metric called the upload ratio, which is defined as the total uploaded file size divided by the total payment to the APs. In other words, it represents the size of the file uploaded per unit payment. As shown in Fig. 5.6, since the DORA algorithm takes into account the varying channel contention level and data rate in determining the transmission policy, it is cost effective and achieves the highest upload ratio. In particular, the performance gains in upload ratio over the exponential backoff scheme are 17% and 77% at low and high ρ, respectively. Furthermore, we consider the case with five APs, where we assume that all of them have the same transmission radii R and price q. For the JDORA scheme in Algorithm 5.3, we consider that the estimated number of vehicles n ˜ t at time t ∈ T is obtained by rounding off a normally distributed random variable with a mean nt and a variance θ to the nearest non-negative integer. Thus, the lower the variance θ, the higher is the precision of the estimation. The value of psucc is obtained by setting psucc = gj (˜ nt ), ∀ t ∈ Tj , j ∈ J . We t t plot the total cost and upload ratio in Figs. 5.7 and 5.8 for S = 500 Mbits with b = 0.01, respectively. In Fig. 5.7, we can see that the JDORA scheme with perfect estimation (i.e., 126 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications 5000 MCBC Greedy Exponential Backoff JDORA (θ = 2) JDORA (θ = 1) JDORA (Perfect Estimation) 4500 4000 Total Cost 3500 3000 71% 2500 2000 1500 1000 53% 500 20 30 40 50 60 Density ρ (veh/km) 70 80 Figure 5.7: Total cost versus traffic density ρ for file size S = 500 Mbits with five APs. The JDORA scheme with perfect estimation of psucc has the minimal total cost. Moreover, t a higher total cost is required when the precision of the estimation reduces (i.e., when the variance of the estimation θ increases). θ = 0) of psucc , ∀ t ∈ T achieves the minimal total cost as stated in Theorem 5.3, where t it achieves 53% and 71% cost reduction as compared with the exponential backoff scheme at low and high traffic density ρ, respectively. In Fig. 5.8, we can see that the JDORA scheme with perfect estimation achieves the highest upload ratio. In particular, it achieves an upload ratio 130% and 207% better than the exponential backoff scheme at low and high traffic density ρ, respectively. As shown in Figs. 5.7 and 5.8, the total cost is increased and the upload ratio is reduced, respectively, when the estimation precision decreases. However, this result based on equal share of bandwidth that psucc = 1/˜ nt , ∀ t ∈ T is less t sensitive to the estimation error when the traffic density ρ is high. It suggests that the JDORA algorithm is suitable especially for VANETs with high traffic densities. Finally, we study the threshold policy in a single AP obtained by Algorithm 5.2 when the penalty function h(s) is convex and data rate wt is fixed. We consider that S = 100 Mbits, ν = 100 km/hr, wt = 54 Mbps, ∀ t ∈ T , and h(s) is defined as in (5.41). From Theorem 5.2, we know that the optimal policy has a threshold structure. In Fig. 5.9, we 127 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications 1.1 JDORA (Perfect Estimation) JDORA (θ = 1) JDORA (θ = 2) Exponential Backoff Greedy MCBC 1 0.9 Upload Ratio 0.8 0.7 130% 0.6 0.5 0.4 0.3 207% 0.2 0.1 20 30 40 50 60 Density ρ (veh/km) 70 80 Figure 5.8: Upload ratio versus traffic density ρ for file size S = 500 Mbits with five APs. The JDORA scheme with perfect estimation of psucc achieves the highest upload ratio as t compared with three other heuristic schemes. Moreover, a lower upload ratio is achieved when the precision of the estimation reduces (i.e., when the variance of the estimation θ increases). plot the thresholds s∗t (psucc) of the optimal policy against the decision epoch t for different values of psucc. With the use of the convex penalty function, we can see that the threshold increases with t. In Fig. 5.9(a), for b = 0.1, we can observe that the threshold increases when psucc decreases. It is because a small penalty parameter is chosen, which places a higher priority on the total payment than on the uploaded file size. When psucc is small, the chance of successful transmission is low, so the vehicle chooses a higher threshold and transmits less aggressively to reduce the amount of payment. In Fig. 5.9(b), we choose a larger penalty parameter b = 10 such that a higher priority is placed on the uploaded file size than on the total payment. We can observe that the threshold decreases when psucc decreases. It is because when psucc is small, the vehicle needs to transmit more aggressively (i.e., with a lower threshold) to prevent a large penalty. Moreover, we can see that the thresholds presented in Fig. 5.9(b) is lower than that in Fig. 5.9(a) due to the higher incentive to transmit when the penalty is large. 128 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications 88 86 t Threshold s*(psucc) succ = 0.071 succ = 0.083 p p 84 psucc = 0.100 82 80 78 76 74 72 70 0 20 40 60 80 100 Decision Epoch t (a) b = 0.1 18 17 succ = 0.100 succ = 0.083 p t Threshold s*(psucc) 16 p psucc = 0.071 15 14 13 12 11 10 9 0 20 40 60 80 100 Decision Epoch t (b) b = 10 Figure 5.9: The thresholds s∗t (psucc ) of the optimal policy against the decision epoch t for different penalty parameters b. 5.6 Summary In this chapter, we studied the V2R uplink transmission from a vehicle to the APs in a dynamic drive-thru scenario, where both the channel contention level and data rate vary over time. Depending on the applications’ QoS requirements, the vehicle can achieve different levels of tradeoff between the total uploaded file size and the total payment to the APs by tuning the self-incurred penalty. For a single AP with random vehicular traffic, we proposed a DORA algorithm based on DP to obtain the optimal transmission 129 Chapter 5. Dynamic Optimal Random Access for Vehicle-to-Roadside Communications policy for the vehicle in a coverage range. We prove that if the self-incurred penalty function h(s) is convex and the data rate wt is non-adaptive and fixed, then the optimal transmission policy has a threshold structure. A monotone DORA algorithm with a lower computational complexity was proposed for this special case. Next, for multiple APs with known vehicular patterns, we considered the transmission policy in multiple coverage ranges jointly and proposed an optimal JDORA algorithm. Simulation results showed that our schemes achieve the minimal total cost and the highest upload ratio as compared with three other heuristic schemes. 130 Chapter 6 Conclusions and Future Work In this chapter, we summarize the results and highlight the contributions of this thesis. We also suggest several topics for future work. 6.1 Research Contributions In this thesis, we have proposed several optimal or near-optimal random access algorithms for wireless networks in Chapters 2, 3, and 4 using the NUM framework. We have also considered a uplink transmission problem in VANETs with time-varying channel contention level and data rate in Chapter 5. • In Chapter 2, we considered the random access problem in CR networks using the SINR model. For cooperative users in a multi-channel model, a three-phase distributed algorithm was proposed to obtain a near-optimal solution for the formulated non-convex NUM problem. It converges readily to a close-to-optimal value even when the set of data channels changes due to dynamic spectrum leasing. For rational users in a single-channel model, we used the solution concepts of core and the Shapley value in coalitional game theory to characterize the stability and fair allocation of the payoff among the users, respectively. The performance gain in aggregate throughput of the proposed algorithm based on the SINR model over other schemes based on the protocol model are validated by simulations. The Shapley value and the core were illustrated with a numerical example. 131 Chapter 6. Conclusions and Future Work • In Chapter 3, we studied the single-channel random access problem in WLANs, where the users have concave, step, and quasi-concave utility functions. Potentially, a selfish user may strategically declare its utility function or AC to unfairly achieve a larger share of bandwidth, which can drastically degrade the network performance and inhibit adequate service distinction among different ACs. We applied the VCG mechanism in our random access protocol to motivate the users to declare the ACs of their applications truthfully. In order to implement the VCG mechanism, we proposed a low-complexity enumeration algorithm that can obtain the global optimal solution for the formulated non-convex problem. Simulation results show that a truthful mechanism can prevent selfish users from gaining an unfair share of the network bandwidth, such that both the overall network performance in terms of aggregate utility and service differentiation in terms of necessary throughput in each AC can be supported. • In Chapter 4, we extended the work of random access in WLANs, where we considered that the users have concave or sigmoidal utility functions. Different from Chapter 3, we did not restrict a concave utility function to remain concave after a logarithmic change of variables. By applying the dual decomposition method, we proposed a subgradient algorithm to solve the formulated non-convex NUM problem. Closed-form solutions for the dual subproblems involving sigmoidal functions were obtained. If a sufficient condition on link capacities is satisfied, it is guaranteed that the proposed algorithm can obtain the global optimal solution. Otherwise, lower and upper bounds of the optimal value of the objective function were obtained. Simulations were performed to verify our analytical results. • In Chapter 5, we studied V2R uplink transmission from a vehicle to the APs in a dynamic drive-thru scenario with time-varying channel contention level and trans132 Chapter 6. Conclusions and Future Work mission data rate. First, for a single AP with random vehicular traffic, we proposed a DORA algorithm based on DP to obtain the optimal transmission policy. We proved that if the self-incurred penalty function is convex and the data rate is fixed, then we obtain an optimal transmission policy with threshold structure. We proposed a low complexity monotone DORA algorithm for this special case. Then, for multiple APs with known vehicular patterns, we considered joint AP optimization and proposed a JDORA algorithm to obtain the optimal transmission policy. Simulation results showed that our proposed schemes achieve the minimal total cost and the highest upload ratio as compared with three other heuristic schemes. 6.2 Suggestions for Future Work In the following, we consider several interesting possibilities for extension of the current work. 1. CSMA-based MAC Protocol. In Chapters 2, 3, and 4, we have used a slotted Aloha type of MAC protocol, which each user accesses the channel with a certain transmission probability. It is interesting to consider the CSMA-based MAC protocol, where a user attempts to transmit only when the channel is sensed idle [104–106]. 2. Rational User Cooperation in Multiple Channels. In Chapter 2, we have analyzed the rational user cooperation in a single channel under the SINR model. It is interesting to extend the model to a multi-channel setting and analyze the interactions of the rational users. The idea of coalition formation game in coalitional game theory is an interesting direction for future work. 3. Multi-hop Communication. In Chapters 2, 3, and 4, we have assumed that the transmission between the transmitter and receiver of each user is only single-hop. It 133 Chapter 6. Conclusions and Future Work is possible to consider the multi-hop setting by introducing binary routing variables and flow conservation constraints as in [57]. 4. Analysis of the Random Access Game. In Chapter 3, we have analyzed the ˆ by the rational players in the strategic declarations of the amplitude parameters K non-cooperative random access game. It is possible to extend the analysis to consider the strategic declarations of the other utility parameters, i.e., α ˆ and pˆcritical . 5. Joint AP Optimization Without Traffic Pattern Estimation. In Chapter 5, we have considered the single-AP scenario with random vehicular traffic, and the multiple-AP scenario with deterministic vehicular traffic due to traffic pattern estimation. One possible direction for extension is to characterize the probability related to the number of vehicles in each AP in the multiple-AP scenario, and consider joint AP optimization with random vehicular traffic (i.e., without the need of traffic pattern estimation). 134 Bibliography [1] J. So and N. Vaidya, “Multi-channel MAC for ad hoc networks: Handling multichannel hidden terminals using a single transceiver,” in Proc. of ACM MobiHoc, Roppongi, Japan, May 2004. [2] A. Leon-Garcia and I. Widjaja, Communication Networks: Fundamental Concepts and Key Architectures, 2nd ed. New York, NY: McGraw-Hill, 2004. [3] FCC Spectrum Policy Task Force. (2002, Nov.) Report of the spectrum efficiency working group. [4] S. Haykin, “Cognitive radio: Brain-empowered wireless communications,” IEEE J. Select. Areas Commun., vol. 23, no. 2, pp. 201–220, Feb. 2005. [5] Q. Zhao and B. M. Sadler, “A survey of dynamic spectrum access,” IEEE Signal Processing Magazine, vol. 24, no. 3, pp. 79–89, May 2007. [6] J. M. Peha, “Approaches to spectrum sharing,” IEEE Communications Magazine, vol. 43, no. 2, pp. 10–12, Feb. 2005. [7] D. Niyato and E. Hossain, “Competitive pricing for spectrum sharing in cognitive radio networks: Dynamic game, inefficiency of Nash equilibrium, and collusion,” IEEE J. Select. Areas Commun., vol. 26, no. 1, pp. 192–202, Jan. 2008. [8] L. Duan, J. Huang, and B. Shou, “Cognitive mobile virtual network operator: Investment and pricing with supply uncertainty,” in Proc. of IEEE INFOCOM, San Diego, CA, Mar. 2010. [9] G. Vazquez-Vilar, C. Mosquera, and S. K. Jayaweera, “Primary user enters the game: Performance of dynamic spectrum leasing in cognitive radio networks,” IEEE Trans. on Wireless Communications, vol. 9, no. 12, pp. 3625–3629, Dec. 2010. [10] W. Wang, B. Kasiri, J. Cai, and A. S. Alfa, “Distributed cooperative multi-channel spectrum sensing based on dynamic coalitional game,” in Proc. of IEEE Globecom, Miami, FL, Dec. 2010. [11] T. Y¨ ucek and H. Arslan, “A survey of spectrum sensing algorithms for cognitive radio applications,” IEEE Communications Surveys & Tutorials, vol. 11, no. 1, pp. 116–130, first quarter 2009. 135 Bibliography [12] S. Shenker, “Fundamental design issues for the future Internet,” IEEE J. Select. Areas Commun., vol. 13, no. 7, pp. 1176–1188, Sept. 1995. [13] H. Hartenstein and K. P. Laberteaux, “A tutorial survey on vehicular ad hoc networks,” IEEE Communications Magazine, vol. 46, no. 6, pp. 164–171, June 2008. [14] Y. Toor, P. M¨ uhlethaler, A. Laouiti, and A. de La Fortelle, “Vehicle ad hoc networks: Applications and related technical issues,” IEEE Communications Surveys & Tutorials, vol. 10, no. 3, pp. 74–88, third quarter 2008. [15] E. Hossain, G. Chow, V. C. M. Leung, R. D. McLeod, J. Misic, V. W. S. Wong, and O. Yang, “Vehicular telematics over heterogeneous wireless networks: A survey,” Elsevier Computer Communications, vol. 33, no. 7, pp. 775–793, May 2010. [16] Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification, IEEE Std. 802.11p, 2010. [17] R. A. Uzcategui and G. Acosta-Marum, “WAVE: A tutorial,” IEEE Communications Magazine, vol. 47, no. 5, pp. 126–133, May 2009. [18] Y. L. Morgan, “Notes on DSRC & WAVE standards suite: Its architecture, design, and characteristics,” IEEE Communications Surveys & Tutorials, vol. 12, no. 4, pp. 504–518, fourth quarter 2010. [19] D. P. Bertsekas, Nonlinear Programming, 2nd ed. Athena Scientific, 1999. [20] M. Minoux, Mathematical Programming: Theory and Algorithms. Wiley, 1986. [21] S. Boyd and L. Vandenberghe, Convex Optimization. University Press, 2004. New York, NY: Cambridge, UK: Cambridge [22] D. P. Bertsekas, A. Nedic, and A. E. Ozdaglar, Convex Analysis and Optimization. Belmont, MA: Athena Scientific, 2003. [23] M. S. Bazarra, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, 3rd ed. Hoboken, NJ: Wiley, 2006. [24] M. J. Osborne and A. Rubinstein, A Course in Game Theory. MIT Press, 1994. [25] Y. Shoham and K. Leyton-Brown, Multi Agent Systems: Algorithmic, GameTheoretic, and Logical Foundations. Cambridge University Press, 2008. [26] D. Fudenberg and J. Tirole, Game Theory. Cambridge, Massachusetts: MIT Press, 1991. 136 Bibliography [27] A. Mas-Colell, M. D. Whinston, and J. R. Green, Microeconomic Theory. University Press, 1995. Oxford [28] M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. New York, NY: John Wiley and Sons, 2005. [29] D. P. Bertsekas, Dynamic Programming and Optimal Control: Volume 1, 3rd ed. Athena Scientific, 2005. [30] W. Saad, Z. Han, M. Debbah, A. Hjorungnes, and T. Basar, “Coalitional game theory for communication networks,” IEEE Signal Processing Magazine, vol. 26, no. 5, pp. 77–97, Sept. 2009. [31] K. R. Apt and A. Witzel, “A generic approach to coalition formation,” International Game Theory Review, vol. 11, no. 3, pp. 347–367, 2009. [32] W. Saad, Z. Han, T. Basar, M. Debbah, and A. Hjorungnes, “Hedonic coalition formation for distributed task allocation among wireless agents,” IEEE Trans. on Mobile Computing, vol. 10, no. 9, pp. 1327–1344, Sept. 2011. [33] A. Bogomolnaia and M. O. Jackson, “The stability of hedonic coalition structures,” Games and Economic Behavior, vol. 38, pp. 201–230, Feb. 2002. [34] D. C. Parkes, “Iterative combinatorial auctions: Achieving economic and computational efficiency,” Ph.D. dissertation, University of Pennsylvania, May 2001. [35] M. H. Cheung, V. W. S. Wong, and R. Schober, “SINR-based random access for cognitive radio: Distributed algorithm and coalitional game,” IEEE Trans. on Wireless Communications, vol. 10, no. 11, pp. 3887–3897, Nov. 2011. [36] M. H. Cheung, A. H. Mohsenian-Rad, V. W. S. Wong, and R. Schober, “Random access protocols for WLANs based on mechanism design,” in Proc. of IEEE ICC, Dresden, Germany, June 2009. [37] ——, “Random access for elastic and inelastic traffic in WLANs,” IEEE Trans. on Wireless Communications, vol. 9, no. 6, pp. 1861–1866, June 2010. [38] M. H. Cheung, F. Hou, V. W. S. Wong, and J. Huang, “Dynamic optimal random access for vehicle-to-roadside communications,” in Proc. of IEEE ICC, Kyoto, Japan, June 2011. [39] ——, “DORA: Dynamic optimal random access for vehicle-to-roadside communications,” accepted for publication in IEEE J. on Selected Areas in Commun., 2012. [40] H. Su and X. Zhang, “Cross-layer based opportunisitc MAC protocols for QoS provisionings over cognitive radio wireless networks,” IEEE J. Select. Areas Commun., vol. 26, no. 1, pp. 118–129, Jan. 2008. 137 Bibliography [41] M. Timmers, S. Pollin, A. Dejonghe, L. Van der Perre, and F. Catthoor, “A distributed multichannel MAC protocol for multihop cognitive radio networks,” IEEE Trans. on Vehicular Technology, vol. 59, no. 1, pp. 446–459, Jan. 2010. [42] P. Gupta and P. Kumar, “The capacity of wireless networks,” IEEE Trans. Inform. Theory, vol. 46, no. 2, pp. 388–404, Mar. 2000. [43] L. Fu, S. C. Liew, and J. Huang, “Effective carrier sensing in CSMA networks under cumulative interference,” in Proc. of IEEE INFOCOM, San Diego, CA, Mar. 2010. [44] A. H. Mohsenian-Rad, V. W. S. Wong, and R. Schober, “Optimal SINR-based random access,” in Proc. of IEEE INFOCOM, San Diego, CA, Mar. 2010. [45] O. Goussevskaia, Y. A. Oswald, and R. Wattenhofer, “Complexity in geometric SINR,” in Proc. of ACM MobiHoc, Montreal, Quebec, Canada, Sept. 2007. [46] D. Qian, D. Zheng, J. Zhang, and N. Shroff, “CSMA-based distributed scheduling in multi-hop MIMO networks under SINR model,” in Proc. of IEEE INFOCOM, San Diego, CA, Mar. 2010. [47] A. H. Mohsenian-Rad and V. W. S. Wong, “Distributed multi-interface multi-channel random access using convex optimization,” IEEE Trans. on Mobile Computing, vol. 10, no. 1, pp. 67–80, Jan. 2011. [48] M. Felegyhazi, M. Cagalj, and J.-P. Hubaux, “Efficient MAC in cognitive radio systems: A game-theoretic approach,” IEEE Trans. on Wireless Communications, vol. 8, no. 4, pp. 1984–1995, Apr. 2009. [49] C. Zou and C. Chigan, “A game theoretic DSA-driven MAC framework for cognitive radio networks,” in Proc. of IEEE ICC, Beijing, China, May 2008. [50] S. Mathur, L. Sankar, and N. B. Mandayam, “Coalitions in cooperative wireless networks,” IEEE J. on Selected Areas in Commun., vol. 26, no. 7, pp. 1104–1115, Sept. 2008. [51] C. Cordeiro and K. Challapali, “C-MAC: A cognitive MAC protocol for multi-channel wireless networks,” in Proc. of IEEE DySPAN, Dublin, Ireland, Oct. 2007. [52] J. Jia, Q. Zhang, and X. Shen, “HC-MAC: A hardware-constrained cognitive MAC for efficient spectrum management,” IEEE J. Select. Areas Commun., vol. 26, no. 1, pp. 106–117, Jan. 2008. [53] J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Trans. on Networking, vol. 8, no. 5, pp. 556–567, Oct. 2000. [54] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Athena Scientific, 1997. 138 Bibliography [55] S. Pleisch, M. Balakrishnan, K. Birman, and R. van Renesse, “MISTRAL: Efficient flooding in mobile ad-hoc networks,” in Proc. of ACM MobiHoc, Florence, Italy, May 2006. [56] W. Lou and J. Wu, “Toward broadcast reliability in mobile ad hoc networks with double coverage,” IEEE Trans. on Mobile Computing, vol. 6, no. 2, pp. 148–163, Feb. 2007. [57] A. H. Mohsenian-Rad and V. W. S. Wong, “Joint logical topology design, interface assignment, channel allocation, and routing for multi-channel wireless mesh networks,” IEEE Trans. on Wireless Communications, vol. 6, no. 12, pp. 4432–4440, Dec. 2007. [58] D. Niyato and E. Hossain, “Competitive pricing in heterogeneous wireless access networks: Issues and approaches,” IEEE Network, vol. 22, no. 6, pp. 4–11, Nov.-Dec. 2008. [59] F. Fu and M. van der Schaar, “Noncollaborative resource management for wireless multimedia applications using mechanism design,” IEEE Trans. on Multimedia, vol. 9, no. 4, pp. 851–868, June 2007. [60] F. Wu, S. Zhong, and J. Liu, “An optimal, strategy-proof scheme for multi-path traffic assignment in non-cooperative networks,” IEEE Trans. on Wireless Commun., vol. 9, no. 3, pp. 1012–1021, Mar. 2010. [61] N. Nisan and A. Ronen, “Algorithmic mechanism design,” Games and Economic Behavior, vol. 35, pp. 166–196, 2001. [62] J. Lee, M. Chiang, and A. R. Calderbank, “Utility-optimal random-access control,” IEEE Trans. on Wireless Communications, vol. 6, no. 7, pp. 2741–2751, Jul. 2007. [63] A. H. Mohsenian-Rad, J. Huang, M. Chiang, and V. W. S. Wong, “Utility-optimal random access: Reduced complexity, fast convergence, and robust performance,” IEEE Trans. on Wireless Communications, vol. 8, no. 2, pp. 898–911, Feb. 2009. [64] F. Kelly, “Charging and rate control for elastic traffic,” European Trans. on Telecommunication, vol. 8, pp. 33–37, 1997. [65] M. Cagalj, S. Ganeriwal, I. Aad, and J. P. Hubaux, “On selfish behavior in CSMA/CA networks,” in Proc. of IEEE INFOCOM, Miami, FL, Mar. 2005. [66] H. Inaltekin and S. B. Wicker, “The analysis of Nash equilibria of the one-shot random-access game for wireless networks and the behavior of selfish nodes,” IEEE/ACM Trans. on Networking, vol. 16, no. 5, pp. 1094–1107, Oct. 2008. 139 Bibliography [67] L. Chen, S. H. Low, and J. C. Doyle, “Random access game and medium access control design,” IEEE/ACM Trans. on Networking, vol. 18, no. 4, pp. 1303–1316, Aug. 2010. [68] Z. Han, Z. Ji, and K. J. R. Liu, “A cartel maintenance framework to enforce cooperation in wireless networks with selfish users,” IEEE Trans. on Wireless Communications, vol. 7, no. 5, pp. 1889–1899, May 2008. [69] W. Wang, X.-Y. Li, and Y. Wang, “Truthful multicast routing in selfish wireless networks,” in Proc. of ACM MobiCom, Philadelphia, PA, Sept. 2004. [70] P. Nuggehalli, M. Sarkar, and R. Rao, “QoS and selfish users: A MAC layer perspective,” in Proc. IEEE GLOBECOM, Washington, DC, Nov. 2007. [71] J. Bae, E. Beigman, R. Berry, M. L. Honig, and R. Vohra, “A dynamic auction for spectrum sharing,” in Proc. of Allerton Conference, Monticello, IL, Sept. 2007. [72] J. Huang, Z. Han, M. Chiang, and H. Poor, “Auction-based resource allocation for cooperative communications,” IEEE J. Select. Areas Commun., vol. 26, no. 7, pp. 1226–1237, Sept. 2008. [73] C. Ko and H. Wei, “On-demand resource sharing mechanism design in two-tier OFDMA femtocell networks,” IEEE Trans. Veh. Technol., vol. 60, no. 3, pp. 1059– 1071, Mar. 2011. [74] J. Lee, A. Tang, J. Huang, M. Chiang, and A. R. Calderbank, “Reverse-engineering MAC: A non-cooperative game model,” IEEE J. Select. Areas Commun., vol. 25, no. 6, pp. 1135–1147, Aug. 2007. [75] A. H. Mohsenian-Rad, J. Huang, M. Chiang, and V. W. S. Wong, “Utility-optimal random access without message passing,” IEEE Trans. on Wireless Communications, vol. 8, no. 3, pp. 1073–1079, Mar. 2009. [76] N. Ben Salem, L. Buttyan, J.-P. Hubaux, and M. Jakobsson, “Node cooperation in hybrid ad hoc networks,” IEEE Trans. on Mobile Computing, vol. 5, no. 4, pp. 365–376, Apr. 2006. [77] S. G. Rao, Discrete Mathematical Structures, 2nd ed. New Age International, 2009. [78] “IEEE 802.11,” 2007. http://standards.ieee.org/getieee802/download/802.11-2007.pdf, [79] J. Lee, R. R. Mazumdar, and N. B. Shroff, “Nonconvexity issues for Internet rate control with multiclass services: Stability and optimality,” in Proc. of IEEE INFOCOM, Hong Kong, China, Mar. 2004. 140 Bibliography [80] P. Hande, S. Zhang, and M. Chiang, “Distributed rate allocation for inelastic flows,” IEEE/ACM Trans. on Networking, vol. 15, no. 6, pp. 1240–1253, Dec. 2007. [81] J. Lee, R. R. Mazumdar, and N. B. Shroff, “Downlink power allocation for multi-class wireless systems,” IEEE/ACM Trans. on Networking, vol. 13, no. 4, pp. 854–867, 2005. [82] M. Xiao, N. B. Shroff, and E. K. P. Chong, “A utility-based power-control scheme in wireless cellular systems,” IEEE/ACM Trans. on Networking, vol. 11, no. 2, pp. 210–221, Apr. 2003. [83] W.-H. Kuo and W. Liao, “Utility-based radio resource allocation for QoS traffic in wireless networks,” IEEE Trans. on Wireless Commun., vol. 7, no. 7, pp. 2714–2722, July 2008. [84] W. G. Bardsley and R. M. W. Wood, “Critical points and sigmoidicity of positive rational functions,” The American Mathematical Monthly, vol. 92, no. 1, pp. 37–48, 1985. [85] J. Ott and D. Kutscher, “Drive-thru Internet: IEEE 802.11b for automobile users,” in Proc. of IEEE INFOCOM, Hong Kong, China, Mar. 2004. [86] B. Roman, I. Wassell, and I. Chatzigeorgiou, “Scalable cross-layer wireless access control using multi-carrier burst contention,” IEEE J. Select. Areas Commun., vol. 29, no. 1, pp. 113–128, Jan. 2011. [87] D. Hadaller, S. Keshav, and T. Brecht, “MV-MAX: Improving wireless infrastructure access for multi-vehicular communication,” in Proc. of ACM SIGCOMM Workshop, Pisa, Italy, Sept. 2006. [88] C. Chang, R. Cheng, H. Shih, and Y. Chen, “Maximum freedom last scheduling algorithm for downlinks of DSRC networks,” IEEE Trans. on Intelligent Transportation Systems, vol. 8, no. 2, pp. 223–232, June 2007. [89] Y. Zhang, J. Zhao, and G. Cao, “On scheduling vehicle-roadside data access,” in Proc. of ACM International Workshop on VANETs, Montreal, QC, Canada, Sept. 2007. [90] J. J. Alcaraz, J. Vales-Alonso, and J. Garcia-Haro, “Link-layer scheduling in vehicle to infrastructure networks: An optimal control approach,” IEEE J. Select. Areas Commun., vol. 29, no. 1, pp. 103–112, Jan. 2011. [91] K. Yang, S. Ou, H.-H. Chen, and J. He, “A multihop peer-communication protocol with fairness guarantee for IEEE 802.16-based vehicular networks,” IEEE Trans. on Vehicular Technology, vol. 56, no. 6, pp. 3358–3370, Nov. 2007. 141 Bibliography [92] B. Shrestha, D. Niyato, Z. Han, and E. Hossain, “Wireless access in vehicular environments using BitTorrent and bargaining,” in Proc. of IEEE GLOBECOM, New Orleans, LA, Nov. 2008. [93] B. Jarupan and E. Ekici, “Location- and delay-aware cross-layer communication in V2I multihop vehicular networks,” IEEE Communications Magazine, vol. 47, no. 11, pp. 112–118, Nov. 2009. [94] D. Niyato and E. Hossain, “A unified framework for optimal wireless access for data streaming over vehicle-to-roadside communications,” IEEE Trans. Veh. Technol., vol. 59, no. 6, pp. 3025–3035, Jul. 2010. [95] B. Sikdar, “Characterization and abatement of the reassociation overhead in vehicle to roadside networks,” IEEE Trans. on Communications, vol. 58, no. 11, pp. 3296– 3304, Nov. 2010. [96] W. L. Tan, W. C. Lau, O. Yue, and T. H. Hui, “Analytical models and performance evaluation of drive-thru Internet systems,” IEEE J. Select. Areas Commun., vol. 29, no. 1, pp. 207–222, Jan. 2011. [97] J. Choi and H. Lee, “Supporting handover in an IEEE 802.11p-based wireless access system,” in Proc. of ACM International Workshop on VANETs, Chicago, IL, Sept. 2010. [98] R. J. Cowan, “Useful headway models,” Transportation Research, vol. 9, no. 6, pp. 371–375, Dec. 1975. [99] J. D. Fricker and R. K. Whitford, Fundamentals of Transportation Engineering: A Multimodal Systems Approach. Prentice Hall, 2004. [100] M. H. Ngo and V. Krishnamurthy, “Optimality of threshold policies for transmission scheduling in correlated fading channels,” IEEE Trans. on Communications, vol. 57, no. 8, pp. 2474–2483, Aug. 2009. [101] S. Ross, Introduction to Stochastic Dynamic Programming. demic Press, 1983. San Diego, CA: Aca- [102] T. N. Schoepflin and D. J. Dailey, “Dynamic camera calibration of roadside traffic management cameras for vehicle speed estimation,” IEEE Trans. on Intelligent Transportation Systems, vol. 4, no. 2, pp. 90–98, June 2003. [103] S. A. Vaqar and O. Basir, “Traffic pattern detection in a partially deployed vehicular ad hoc network of vehicles,” IEEE Wireless Commun., vol. 16, no. 6, pp. 40–46, Dec. 2009. 142 Bibliography [104] M. Lotfinezhad and P. Marbach, “Throughput-optimal random access with orderoptimal delay,” in Proc. of IEEE INFOCOM, Shanghai, China, April 2011. [105] L. Jiang and J. Walrand, “A distributed CSMA algorithm for throughput and utility maximization in wireless networks,” in Proc. of Allerton Conference, Monticello, IL, Sept. 2008. [106] B. Nardelli, J. Lee, K. Lee, Y. Yi, S. Chong, E. Knightly, and M. Chiang, “Experimental evaluation of optimal CSMA,” in Proc. of IEEE INFOCOM, Shanghai, China, April 2011. 143
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Optimal random access protocols for wireless networks
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Optimal random access protocols for wireless networks Cheung, Man Hon 2012
pdf
Page Metadata
Item Metadata
Title | Optimal random access protocols for wireless networks |
Creator |
Cheung, Man Hon |
Publisher | University of British Columbia |
Date Issued | 2012 |
Description | In this thesis, we present several random access algorithms for medium access control in wireless networks. Optimization theory, game theory, and dynamic programming are applied in the analysis and the design of these algorithms. First, we study the problem of multi-channel random access using the signal-to-interference-plus-noise-ratio (SINR) model in cognitive radio networks. We formulate it as a network utility maximization (NUM) problem, and propose a distributed algorithm that converges to a near-optimal solution. Moreover, we apply coalitional game theory to study the incentive issues of rational user cooperation in a given channel under the SINR model. Next, we consider a wireless local area network (WLAN) with rational users, who may strategically declare their access categories (ACs) not intended for their applications in order to gain some unfair shares of the network resources. We propose to use the Vickrey-Clarke-Groves (VCG) mechanism to motivate each user to declare truthfully its actual AC to the access point (AP). In order to implement the VCG mechanism with concave, step, and quasi-concave utility functions, we propose an enumeration algorithm to obtain the global optimal solution of the formulated non-convex NUM problem. To extend the aforementioned work on single-channel random access in WLANs, we focus on sigmoidal utility functions. We propose a subgradient algorithm to solve the formulated NUM problem using the dual decomposition method. If the sufficient conditions on link capacities are satisfied, the algorithm obtains the optimal solution. Finally, we consider the vehicular ad hoc networks. We study the problem of random access in a drive-thru scenario, where roadside APs are installed on a highway to provide temporary Internet access for vehicles. We first consider the single-AP scenario with random vehicular traffic, and propose a dynamic optimal random access (DORA) algorithm that aims to minimize the total transmission cost of a vehicle. We determine the conditions under which the optimal transmission policy has a threshold structure, and propose an algorithm with a lower computational complexity. Then, we consider the multiple-AP scenario with deterministic vehicular traffic arrival due to traffic estimation. A joint DORA is proposed to obtain the optimal transmission policy. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2012-03-28 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0072643 |
URI | http://hdl.handle.net/2429/41856 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2012-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2012_spring_cheung_manhon.pdf [ 1.16MB ]
- Metadata
- JSON: 24-1.0072643.json
- JSON-LD: 24-1.0072643-ld.json
- RDF/XML (Pretty): 24-1.0072643-rdf.xml
- RDF/JSON: 24-1.0072643-rdf.json
- Turtle: 24-1.0072643-turtle.txt
- N-Triples: 24-1.0072643-rdf-ntriples.txt
- Original Record: 24-1.0072643-source.json
- Full Text
- 24-1.0072643-fulltext.txt
- Citation
- 24-1.0072643.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0072643/manifest