Multi-packet reception (MPR) has been recognized as a powerful capacity-enhancement technique for randomaccess wireless local area networks (WLANs). As is common with all random access protocols, the wireless channel is often under-utilized in MPR WLANs. In this paper, we propose a novel multi-round contention random-access protocol to address this problem. This work complements the existing randomaccess methods that are based on single-round contention. In the proposed scheme, stations are given multiple chances to contend for the channel until there are a sufficient number of ?winning? stations that can share the MPR channel for data packet transmission. The key issue here is the identification of the optimal time to stop the contention process and start data transmission. The solution corresponds to finding a desired tradeoff between channel utilization and contention overhead. In this paper, we conduct a rigorous analysis to characterize the optimal strategy using the theory of optimal stopping. An interesting result is that the optimal stopping strategy is a simple threshold-based rule, which stops the contention process as soon as the total number of winning stations exceeds a certain threshold. Compared with the conventional single-round contention protocol, the multi-round contention scheme significantly enhances channel utilization when the MPR capability of the channel is small to medium. Meanwhile, the scheme automatically falls back to single-round contention when the MPR capability is very large, in which case the throughput penalty due to random access is already small even with single-round contention.
The theory of optimal stopping has been widely studied in the fields of statistics, economics, and mathematical finance since 1960's @cite_5 . It was not until very recently that optimal stopping theory started to find application in wireless networks. In @cite_9 , the tradeoff between the spectrum access opportunity and spectrum sensing overhead in cognitive radio systems is formulated as a finite-horizon optimal stopping problem, which is solved using backward induction. Likewise, a finite-horizon optimal stopping problem is formulated in @cite_4 to derive an optimal next-hop selection strategy in multi-hop ad hoc networks. The problem of maximizing the rate of return (MR) was applied to opportunistic scheduling in ad-hoc networks in @cite_11 and opportunistic spectrum access of cognitive radio networks in @cite_3 . Notably, the application of optimal stopping theory in wireless systems is still at its infancy stage. Our work in this paper is an attempt to introduce it to wireless random-access networks.
@cite_4 @cite_9 @cite_3 @cite_5 @cite_11
2159238092 2157313704 2147910082 70227856 2082330137
Radio spectrum resource is of fundamental importance for wireless communication. Recent reports show that most available spectrum has been allocated. While some of the spectrum bands (e.g., unlicensed band, GSM band) have seen increasingly crowded usage, most of the other spectrum resources are underutilized. This drives the emergence of open spectrum and dynamic spectrum access concepts, which allow unlicensed users equipped with cognitive radios to opportunistically access the spectrum not used by primary users. Cognitive radio has many advanced features, such as agilely sensing the existence of primary users and utilizing multiple spectrum bands simultaneously. However, in practice such capabilities are constrained by hardware cost. In this paper, we discuss how to conduct efficient spectrum management in ad hoc cognitive radio networks while taking the hardware constraints (e.g., single radio, partial spectrum sensing and spectrum aggregation limit) into consideration. A hardware-constrained cognitive MAC, HC-MAC, is proposed to conduct efficient spectrum sensing and spectrum access decision. We identify the issue of optimal spectrum sensing decision for a single secondary transmission pair, and formulate it as an optimal stopping problem. A decentralized MAC protocol is then proposed for the ad hoc cognitive radio networks. Simulation results are presented to demonstrate the effectiveness of our proposed protocol. In a cognitive radio scenario, we consider a single secondary user (SU) accessing a multichannel system. The SU senses the channels sequentially to detect if a primary user (PU) is occupying the channels and stops its search to access a channel if it offers a significantly high throughput. The optimal stopping rule and power control problem is considered. The problem is formulated as an SU's throughput-maximization problem under power, interference, and packet delay constraints. We first show the effect of the optimal stopping rule on packet delay and then solve this optimization problem for both the overlay system, where the SU transmits only at the spectrum holes, and the underlay system, where tolerable interference (or tolerable collision probability) is allowed. We provide closed-form expressions for the optimal stopping rule and show that the optimal power control strategy for this multichannel problem is a modified waterfilling approach. We extend the work to a multi-SU scenario and show that when the number of SUs is large, the complexity of the solution becomes smaller than that of the single-SU case. We discuss the application of this problem in typical networks where packets simultaneously arrive and have the same departure deadline. We further propose an online adaptation policy to the optimal stopping rule that meets the packets' hard-deadline constraint and, at the same time, gives higher throughput than the offline policy. We consider distributed opportunistic scheduling (DOS) in wireless ad-hoc networks, where many links contend for the same channel using random access. In such networks, distributed opportunistic scheduling involves a process of joint channel probing and distributed scheduling. Due to channel fading, the link condition corresponding to a successful channel probing could be either good or poor. In the latter case, further channel probing, although at the cost of additional delay, may lead to better channel conditions and hence higher transmission rates. The desired tradeoff boils down to judiciously choosing the optimal stopping strategy for channel probing and the rate threshold. In this paper, we pursue a rigorous characterization of the optimal strategies from two perspectives, namely, a network-centric perspective and a user-centric perspective. We first consider DOS from a network-centric point of view, where links cooperate to maximize the overall network throughput. Using optimal stopping theory, we show that the optimal strategy turns out to be a pure threshold policy, where the rate threshold can be obtained by solving a fixed point equation. We further devise an iterative algorithm for computing the threshold. Next, we explore DOS from a user-centric perspective, where each links seeks to maximize its own throughput. We treat the problem of rate threshold selections for different links as a non-cooperative game. We explore the existence and uniqueness of the Nash equilibrium, and show that the Nash equilibrium can be approached by the best response strategy. We then develop an online stochastic iterative algorithm using local observations only, and establish its convergence. Finally, we observe that there is an efficiency loss in terms of the throughput at the Nash equilibrium, and introduce apricing-based mechanism to mitigate the loss. In order to adapt to time-varying wireless channels, various channel-adaptive schemes have been proposed to exploit inherent spatial diversity in mobile wireless ad hoc networks where there are usually alternate next-hop relays available at a given forwarding node. However, current schemes along this line are designed based on heuristics, implying room for performance enhancement. To seek a theoretical foundation for improving spatial diversity gain, we formulate the selection of the next-hop as a sequential decision problem and propose a general "optimal stopping relaying (OSR)" framework for designing such next-hop diversity schemes. As a particular example, assuming Rayleigh fading channels, we implement an OSR strategy to optimize information efficiency (IE) in a protocol stack consisting of greedy perimeter stateless routing (GPSR) and IEEE 802.11 MAC protocols. We present mathematical analysis of the proposed OSR together with other strategies in literature for a single forwarding node. In addition, we perform extensive simulations (using QualNet) to evaluate the end-to-end performance of these relaying strategies in a multi-hop network. Both the mathematical and simulation results demonstrate the superiority of OSR over other existing schemes.