Optimal random access protocols for wireless networks

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.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat