Approximation Schemes for Information Acquisition and Exploitation in Multichannel Wireless Networks
Nodes in future wireless networks are likely to have access to multiple channels. A node can learn the instantaneous state of a channel only by probing it which in turn consumes both additional energy and time. A node therefore needs to not only optimally select the channel based on available information but also optimally determine the amount of information it should acquire about the instantaneous states of its available channels. The successful exploitation of the available channels is therefore contingent upon designing simple mechanisms for jointly optimizing both information acquisition and exploitation. We provide a joint channel probing and selection scheme that can approximate a utility function that captures both the cost and value of information. The approximation can be made arbitrarily close to the optimal while increasing the computation time of the solution. Specifically, given any positive , the proposed scheme can be tuned to attain a utility which is at most times the maximum reward less than that of the optimal, and requires a computation time which is polynomial in the number of channels and the degree of this polynomial increases with decrease in .
