We consider opportunistic spectrum access (OSA) strategies for a transmitter in a multichannel wireless system, where a channel may or may not be available and the transmitter must sense/probe the channel to find out before transmission. Applications for this work include joint probing and transmission for a secondary user in a cognitive radio network. Limited by resources, e.g., energy and time, the transmitter must decide on a subset of a potentially very large number of channels to probe and can only use for transmission those that have been found to be available. In contrast to previous works, we do not assume the user has a priori knowledge regarding the statistics of channel states. The main goal of this work is to design strategies that decide, based only on knowledge of the channel bandwidths/data rates, which channels to probe. We derive optimal strategies that maximize the total expected bandwidth/data rate in the worst-case, via a performance measure in the form of a competitive regret (ratio) between the average performance of a strategy and a genie (or omniscient observer). We examine the performance of these optimal strategies under a wide range of system parameters and practical channel models via numerical studies.

We consider opportunistic spectrum access (OSA) strategies for a transmitter in a multichannel wireless system, where a channel may or may not be available and the transmitter must sense/probe the channel to find out before transmission. Applications for this work include joint probing and transmission for a secondary user in a cognitive radio network. Limited by resources, e.g., energy and time, the transmitter must decide on a subset of a potentially very large number of channels to probe and can only use for transmission those that have been found to be available. In contrast to previous works, we do not assume the user has a priori knowledge regarding the statistics of channel states. The main goal of this work is to design robust strategies that decide, based only on knowledge of the channel bandwidths/data rates, which channels to probe. We derive optimal strategies that maximize the total expected bandwidth/data rate in the worst-case, via a performance measure in the form of a competitive regret (ratio) between the average performance of a strategy and a genie (or omniscient observer). This formulation can also be viewed as a two-player zero-sum game between the user and an adversary which chooses the channel state that minimizes the useriquests gain. We show that our results correspond to a Nash equilibrium (in the form of a mixed strategy) in this game. We examine the performance of the optimal strategies under a wide range of system parameters and practical channel models via numerical studies.

In this paper, we consider a constrained sequential resource allocation problem where an individual needs to accomplish a task by repeatedly guessing/investing a sufficient level of effort/input. If the investment falls short of a minimum required level that is unknown to the individual, she fails; with each unsuccessful attempt, the individual then increases the input and tries again until she succeeds. The objective is to complete the task with as little resources/cost as possible subject to a delay constraint. The optimal strategy lies in the proper balance between 1) selecting a level (far) below the minimum required and therefore having to try again, thus wasting resources, and 2) selecting a level (far) above the minimum required, and therefore, overshooting and wasting resources. A number of motivating applications arising from communication networks are provided. Assuming that the individual has no knowledge on the distribution of the minimum effort required to complete the task, we adopt a worst-case cost measure and a worst-case delay measure to formulate the above constrained optimization problem. We derive a class of optimal strategies, shown to be randomized, and obtain their performance as a function of the constraint.

In this study we consider optimal opportunistic spectrum access (OSA) policies for a transmitter in a multichannel wireless system, where a channel can be in one of multiple states. Each channel state is associated with either a probability of transmission success or a transmission rate. In such systems, the transmitter typically has partial information concerning the channel states, but can deduce more by probing individual channels, e.g. by sending control packets in the channels, at the expense of certain resources, e.g., energy and time. The main goal of this work is to derive optimal strategies for determining which channels to probe (in what sequence) and which channel to use for transmission. We consider two problems within this context,allthe constant data time (CDT) and the constant access time (CAT) problems. For both problems, we derive key structural properties of the corresponding optimal strategy. In particular, we show that it has a threshold structure and can be described by an index policy. We further show that the optimal CDT strategy can only take on one of three structural forms. Using these results we present a two-step lookahead CDT (CAT) strategy. This strategy is shown to be optimal for a number of cases of practical interest. We examine its performance under a class of practical channel models via numerical studies.

Abstract — In this paper we consider the problem of query and search in a network, e.g., searching for a specific node or a piece of data. We limit our attention to the class of TTL (time-to-live) based controlled flooding search strategies where query/search packets are broadcast and relayed in the network until a preset TTL value carried in the packet expires. Every unsuccessful search attempt results in an increased TTL value (i.e., larger search area) and the same process is repeated. Every search attempt also incurs a cost (in terms of packet transmissions and receptions) and a delay (time till timeout or till the target is found). The primary goal is to derive search strategies (i.e., sequences of TTL values) that minimize a worst-case cost measure subject to a worst-case delay constraint. We present a constrained optimization framework and derive a class of optimal strategies, shown to be randomized strategies, and obtain their performance as a function of the delay constraint. We also use these results to discuss the trade-off between search cost and delay within the context of flooding search. Index Terms — data query and search, TTL, controlled flood-ing search, wireless sensor and ad hoc networks, constrained optimization, randomized strategy, competitive analysis I.

In this paper we consider the problem of searching for a node or an object (i.e., piece of data, file, etc.) in a large wireless network. We consider the class of controlled flooding search strategies where query/search packets are broadcast and propagated in the network until a preset TTL (time-to-live) value carried in the packet expires. Every unsuccessful search attempt results in an increased TTL value (i.e., larger search area) and the same process is repeated. We derive search strategies that minimize the search cost in the worst-case, via a performance measure in the form of the competitive ratio between the average search cost of a strategy and that of an omniscient observer. This ratio is shown in prior work to be lower bounded by 4 among all deterministic search strategies. In this paper we show that by using randomized strategies this ratio is lower bounded by e. We derive an optimal strategy that achieves this lower bound, and discuss its performance under other performance criteria.

In this paper we consider the problem of searching for a node or an object (i.e., piece of data, file, etc.) in a large network. Applications of this problem include searching for a destination node in a mobile ad hoc network, querying for a piece of desired data in a wireless sensor network, and searching for a shared file in an unstructured peer-to-peer network. We limit our attention in this study to the class of controlled flooding search strategies where query/search packets are broadcast and propagated in the network until a preset TTL (time-to-live) value carried in the packet expires. Every unsuccessful search attempt results in an increased TTL value (i.e., larger search area) and the same process is repeated. The primary goal of this study is to derive search strategies (i.e., sequences of TTL values) that will minimize the cost of such searches associated with packet transmissions. The main results of this paper are as follows. When the probability distribution of the location of the object is known a priori, we present a dynamic programming formulation with which optimal search strategies can be derived that minimize the expected search cost. We also derive the necessary and sufficient conditions %on the location distribution for two very commonly used search strategies to be optimal. When the probability distribution of the location of the object is not known a priori and the object is to minimize the worst-case search cost, we show that the best strategies are randomized strategies, i.e., successive TTL values are chosen from certain probability distributions rather than deterministic values. We show that given any deterministic TTL sequence, there exists a randomized version that has a lower worst-case expected search cost. We also derive an asymptotically (as the network size increases) optimal strategy within a class of randomized strategies.