Distributed algorithm and pricing strategy for resource allocation and revenue maximization in communication networks
by Yuan Wu
Ph.D. Electronic and Computer Engineering
xxi, 164 p. : ill. ; 30 cm
With the rapid growth of communication networks and services, design of distributed algorithm for resource allocation in wired and wireless networks has attracted more and more research interests in recent years. Different from many technique-based centralized algorithms, pricing-based distributed algorithm exploits economic-driven behaviors of network users and thus is more transparent and incentive-compatible. A typical example is that pricing takes the form of “shadow price” to indicate the scarcity of limited resource and thus generates an efficient allocation distributedly. In this thesis, we study two applications of pricing scheme (and the corresponding distributed algorithm design) in communication networks, namely, (i) distributed resource allocation in Dynamic Spectrum Access...[ Read more ]
With the rapid growth of communication networks and services, design of distributed algorithm for resource allocation in wired and wireless networks has attracted more and more research interests in recent years. Different from many technique-based centralized algorithms, pricing-based distributed algorithm exploits economic-driven behaviors of network users and thus is more transparent and incentive-compatible. A typical example is that pricing takes the form of “shadow price” to indicate the scarcity of limited resource and thus generates an efficient allocation distributedly. In this thesis, we study two applications of pricing scheme (and the corresponding distributed algorithm design) in communication networks, namely, (i) distributed resource allocation in Dynamic Spectrum Access (DSA) networks, and (ii) revenue maximization for Internet Service Providers (ISPs) with limited capability of utility-extraction.
Facing with the severe problem of spectrum scarcity, the concept of dynamic spectrum access has been proposed to tackle inefficiency of the static spectrum management policy by leveraging a secondary spectrum utilization. In spite of its simple objective, implementation of DSA networks is much more challenging. The past decade has witnessed a joint effort from engineering, economics, and regulation communities on DSA networks research. By envisioning different capabilities of DSA networks, different models, namely, the Open Sharing model, the Hierarchical Access model, and the Dynamic Exclusive Usage model, have been proposed. In the first part of this thesis, we first study resource allocations (mainly the rate and power allocations) for DSA networks based on these different models.
First, based on the Dynamic Exclusive Usage model, we study the joint pricing and power allocation for DSA networks with the Stackelberg game model. Specifically, Primary User (PU) has the power control flexibility and is willing to share its channel with Secondary User (SU) to obtain extra revenue by charging the cochannel interference. In response, SU pays the interference cost to obtain transmission opportunity. Pricing has two purposes in our model, namely, (i) to motivate PU’s channel sharing and (ii) to motivate SU’s efficient utilization of PU’s channel. Because of its Quality of Service (QoS) requirement, PU faces a tradeoff between charging SU and consuming its own power cost. We quantify the benefits that PU and SU can obtain from the sharing model and derive the stability condition for the sharing model. We further analyze two extensions. The first extension is the single PU multiple SUs scenario, where PU allows multiple SUs to share its channel simultaneously with the objective of revenue maximization. The second extension is the multiple PUs multiple SUs scenario, where each PU can only share its channel with one SU (and vice versa). Our objective is to maximize the entire network welfare by matching PUs and SUs distributedly.
Second, based on the spectrum underlay approach of the Hierarchical Access model, we study the distributed multi-channel power allocation for DSA networks with QoS guarantee. By exploiting the Interference Temperature (IT) metric, we model this problem as a noncooperative power demand game with a coupled strategy space to address both PUs’ interference constraints and SUs’ QoS requirements. We analyze the properties of Nash Equilibrium (N.E.) of our proposed game and propose a distributed algorithm to find the N.E.. Our distributed algorithm is based on a layered structure, where PUs and SUs first separately update their dual prices, and then all SUs form a power demand subgame. By incorporating the dual prices, each SU’s power demand is both interference-aware and QoS-aware.
In the first part of this thesis, we mainly use pricing to motivate certain “desired” network performance in DSA networks, i.e, the efficient channel sharing between PUs and SUs, and the QoS-aware and interference-aware power demand of SUs. In the second part of this thesis, we focus on ISPs’ revenue maximization. Specifically, pricing serves as a bridge transferring customer’s utility into ISP’s revenue. Practical conditions, however, limit ISP’s capability of utility-extraction and thus result in ISP’s revenue loss. We study two of these factors, namely, (i) single ISP with“time-constrained” pricing strategy, and (ii) multiple ISPs inter-charging in a two-sided market.
First, we study ISP’s revenue maximization trading off with End-User’s (EU’s) QoS under the condition that ISP has a limited capability of adjusting its price within a time duration. Specifically, EU’s QoS is measured by the number of packets dropped in two time scales, namely, each individual time slot and the entire time duration. We quantify this revenue-QoS tradeoff based on these two measures of packets dropped. Our results show the impact of customer’s price elasticity on ISP’s revenue and suggest that in order to mitigate the revenue loss, ISP should carry out a differentiated QoS protection strategy based on customer’s price elasticity. Meanwhile, the structure of ISP’s optimal revenue indicates the importance of flat-price in reaping revenue as the packet dropping constraint becomes loose.
Second, we study multiple ISPs inter-charging in a two-sided market. Acting selfishly, each ISP may aggressively set a high transit-price to cover its cost and maximize its own revenue, which inevitably results in a social revenue loss. By modeling ISPs as a supply chain to deliver traffic in a two-sided market, we propose a revenue sharing contract to coordinate these ISPs’ objectives so that the optimal social revenue is achieved. Next, to evaluate the revenue loss due to noncooperation, a Stackelberg game model where each ISP selfishly maximizes its own revenue is analyzed. Analytical results quantify the social revenue loss at the noncooperative equilibrium and show that the revenue loss decreases (increases) with the utility level of the customer whose access service is provided by the leader-ISP (follower-ISP). Finally, a revenue division scheme is proposed for ISPs’ revenue sharing contract by using the asymmetric Nash Bargaining Solution (NBS).