We develop a new tractable model for K-tier heterogeneous cellular networks (HetNets), where each base station (BS) is powered solely by a self-contained energy harvesting module. The BSs across tiers differ in terms of the energy harvesting rate, energy storage capacity, transmit power and deployment density. Since a BS may not always have enough energy, it may need to be kept OFF and allowed to recharge while nearby users are served by neighboring BSs that are ON. We show that the fraction of time a kthtier BS can be kept ON, termed availability ρk, is a fundamental metric of interest. Using tools from random walk theory, fixed point analysis and stochastic geometry, we characterize the set of K-tuples (ρ1, ρ2, ... ρK), termed the availability region, that is achievable by general uncoordinated operational strategies, where the decision to toggle the current ON/OFF state of a BS is taken independently of the other BSs. If the availability vector corresponding to the optimal system performance, e.g., in terms of rate, lies in this availability region, there is no performance loss due to the presence of unreliable energy sources. As a part of our analysis, we model the temporal dynamics of the energy level at each BS as a birth-death process, derive the energy utilization rate, and use hitting/stopping time analysis to prove that there exists a fundamental limit on ρkthat cannot be surpassed by any uncoordinated strategy.

We develop a new tractable model for K-tier cellular networks, where each base station (BS) is solely powered by a self-contained energy harvesting module instead of a conventional power-line source. The BSs across tiers differ in terms of the energy harvesting rate, energy storage capacity, transmit power and deployment density. Since a BS may not always have enough energy, it may need to be kept OFF and allowed to recharge while its load is served by the neighboring BSs that are ON. Using tools from random walk theory and stochastic geometry, we characterize the fraction of time each type of BS can be kept ON, termed availability, for general uncoordinated strategies, where each BS toggles its ON/OFF state independently of the others. As a part of our analysis, we model the temporal dynamics of the energy level at each BS as a birth-death process, derive energy utilization rate for each BS class, and use hitting/stopping time analysis to study availabilities. We prove that there is a fundamental limit on the availabilities, which cannot be surpassed by any uncoordinated strategy. As a part of the proof, we construct the strategy that achieves this limit.

In this paper, we argue that network performance can be improved when nodes explicitly exchange protocol information with each other. We present a vision of network society for next generation wireless networks that entails such social networking. We begin by describing our cognitive social network (CosNet) system architecture that enables network nodes to effectively gather, analyze, compact, repositorize, and exchange network experience information. We also describe a host of technical issues that need to be addressed for successful realization of a network society, including the management of control overhead, protecting user privacy, vulnerability to selfish and malicious attacks, and scalability concerns. We demonstrate the utility of our approach by studying CosNet inspired modifications of the IEEE 802.11 MAC algorithm that we call CosMAC, respectively. Simulation results show that CosMAC outperforms the throughput of 802.11 MAC in single-hop wireless LAN scenarios. CosMAC also appears to result in a fairer allocation, recorded by 10-15% improvement in Jain's fairness index.

The implementation of QoS provisioning at the MAC layer requires users to classify their traffic into QoS categories. In realistic scenarios where users are selfish and interested in maximizing their own utility, users may have an interest in misrepresenting the QoS category of their traffic. We examine a simplified model for IEEE 802.11e networks in which channel access can be obtained via random access or polling. Using concepts from game theory, we show that a polling based incentive mechanism can stimulate users to truthfully report the QoS category of their traffic. Furthermore, we show that our incentive mechanism improves the system capacity, in terms of the number of QoS constrained users that can be admitted, when users are strategic.

We provide a new unified framework, called "multiple correlated informants - single recipient" communication, to address the variations of the traditional Distributed Source Coding (DSC) problem. Different combinations of the assumptions about the communication scenarios and the objectives of communication result in different variations of the DSC problem. For each of these variations, the complexities of communication and computation of the optimal solution is determined by the combination of the underlying assumptions. In the proposed framework, we address the asymmetric, interactive, and lossless variant of the DSC problem, with various objectives of communication and provide optimal solutions for those. Also, we consider both, the worst-case and average-case scenarios.

In this paper, we examine the use of pricing for distributed, incentive-compatible and socially optimal resource allocation in a QoS-differentiated random-access wireless network. We argue that QoS mechanisms in wireless networks are susceptible to misuse by self-interested users. We first present a simple pricing scheme that leads to social optimality (i.e., achieves QoS-differentiated proportional fairness) when users' utility functions are known to the AP. We then characterize the price of anarchy when users are strategic. Finally, the centerpiece of this paper is a pricing scheme that ensures socially optimal operation as a Nash equilibrium strategy among users whose utility functions are not known and who attempt to access the channel in a decentralized manner.

Many wireless network standards include quality-of-service (QoS) features at the MAC layer. These features provide nodes transmitting high priority delay sensitive traffic such as voice and video preferential access to the channel over nodes carrying low priority delay tolerant traffic such as file transfer and email. However, such schemes are unfair to low priority users, depriving them of equitable transmission opportunities, and causing throughput starvation for their applications. Such unfairness can provoke rational nodes carrying low priority traffic to falsely declare their traffic as high priority in order to maximize their throughput, thereby defeating the very purpose of QoS differentiation. In this paper, we provide game-theoretic analysis of a slotted Aloha like MAC that resembles the IEEE 802.11e MAC in many essential respects. Our MAC model allows traffic to be classified as either high-priority (HP) or low-priority (LP), and allows for both random access (contention) and polled (contention-free) channel access. We advocate an incentive mechanism to stimulate LP users to be truthful. This incentive mechanism makes use of the contention-free channel access feature of our MAC as an efficient and protocol-compliant mechanism to encourage low priority users to be truthful. We discuss appropriate utility functions for HP and LP traffic and use a fixed point analysis to derive the performance of the system in terms of the fraction of time the system is operated in contention-free mode. We find the condition for which our incentive mechanism results in a truthful Nash equilibrium, i.e., no user has an incentive to unilaterally lie about her traffic type. We then use the Nash bargaining solution (NBS) concept to suggest how an AP can pick an operating point using our incentive mechanism to ensure fairness and Pareto- optimality.

Many wireless network standards include quality-of-service (QoS) features at the MAC layer. These features provide nodes transmitting real-time traffic such as voice and video preferential access to the channel over nodes carrying best-effort traffic. The success of these QoS mechanisms requires that nodes be honest and truthfully report their application's QoS category. However rational nodes will, if they can, deviate from a standard's specification to maximize their utility. Network interfaces are becoming increasingly programmable and it is possible for nodes to falsely classify their best-effort traffic as real-time traffic to obtain increased throughput. In this paper, we provide a game-theoretic analysis for a slotted Aloha like MAC that resembles the IEEE 802.11e MAC in many essential respects. Our MAC model allows traffic to be classified as either high-priority (HP) or low-priority (LP), and allows for both random access (contention) and polled (contention-free) channel access. We advocate the use of the contention-free access feature as an efficient and protocol-compliant mechanism to incentivize LP users to be truthful. We discuss appropriate utility functions for HP and LP traffic and analyze the performance of the system using the Nash bargaining solution (NBS) concept from cooperative game theory. The NBS concept is used to find a fair and Pareto-optimal operating point for our system. Since users are strategic, we then use the framework of non-cooperative game theory to find the set of Nash equilibria. Somewhat remarkably, we find that the NBS operating point is a Nash equilibrium, implying that our strategy is both efficient and strategy-proof.

We are concerned with maximizing the lifetime of a data-gathering wireless sensor network consisting of set of nodes directly communicating with a base-station. We model this scenario as the m-message interactive communication between multiple correlated informants (sensor nodes) and a recipient (base-station). With this framework, we show that m-message interactive communication can indeed enhance network lifetime. Both worst-case and average-case performances are considered.

In this paper, we study the performance of client-Access Point (AP) association policies in IEEE 802.11 based WLANs. In many scenarios, clients have a choice of APs with whom they can associate. We are interested in finding association policies which lead to optimal system performance. More specifically, we study the stability of different association policies as a function of the spatial distribution of arriving clients. We find for each policy the range of client arrival rates for which the system is stable. For small networks, we use Lyapunov function methods to formally establish the stability or instability of certain policies in specific scenarios. The RAT heuristic policy introduced in our prior work is shown to have very good stability properties when compared to several other natural policies. We also validate our analytical results by detailed simulation employing the IEEE 802.11 MAC.

In this paper, we address the problem of energy efficient packet scheduling in a wireless environment. We consider a wireless transmitter which is limited by its finite battery resource. Our objective is to design a transmission schedule that maximizes battery lifetime subject to some delay constraints. To achieve this, we exploit two previously unconnected ideas: (i) channel coding can be used to conserve energy by transmitting at reduced power levels over longer durations; (ii) electro-chemical mechanisms in batteries allow them to recover energy during idle periods. While the first idea favors extending transmission durations, the second idea requires the transmitter to be idle to allow for recovery. In other words, bursty packet transmissions interspersed with idle periods extend battery life. Therefore, a strategy which is based entirely on either one or the other idea is not optimal. We provide a framework to merge the two ideas. We consider two kinds of delay constraints, one a deadline constraint and the other an average delay constraint and show that energy aware scheduling strategies for both these scenarios can result in significant energy savings.

People often seek information by asking other people even when they have access to vast reservoirs of information such as the Internet and libraries. This is because people are great sources of unique information, especially that which is location-specific, community-specific and time-specific. Social networking is effective because this type of information is often not easily available anywhere else. In this paper, we conceive a wireless virtual social network which mimics the way people seek information via social networking. PeopleNet is a simple, scalable and low-cost architecture for efficient information search in a distributed manner. It uses the infrastructure to propagate queries of a given type to users in specific geographic locations, called bazaars. Within each bazaar, the query is further propagated between neighboring nodes via peer-to-peer connectivity until it finds a matching query. The PeopleNet architecture can overlay easily on existing cellular infrastructure and entails minimal software installation. We identify three metrics for system performance: (i) probability of a match, (ii) time to find a match and (iii) number of matches found by a query. We describe two simple models, called the swap and spread models, for query propagation within a bazaar. We qualitatively argue that the swap model is better with respect to the performance metrics identified and demonstrate this via simulations. Next, we compute analytically the probability of match for the swap model. We show that the probability of match can be significantly improved if, prior to swapping queries, the nodes exchange some limited information about their buffer contents. We propose a simple greedy algorithm which uses this limited information to decide which queries to swap. We show via simulation that this algorithm achieves significantly better performance. Overall our results demonstrate that PeopleNet, with its bazaar concept and peer-to-peer query propagation, can provide a simple and efficient mechanism for seeking information.

We consider the energy consumed in radio transmission by a set of sensors forming a data gathering wireless network. Our objective is to enhance the lifetime of such networks by exploiting three system-level opportunities. First, the number of bits to be transmitted can be reduced by taking advantage of the redundancy induced by spatio-temporal correlation in sensor data. Second, channel coding allows us to reduce transmission energy at the cost of increased transmission time. Third, sensor nodes can be expected to operate collaboratively, allowing optimal management of distributed energy resources. Our main contribution lies in providing a framework to merge these ideas for energy conscious networking. We pose the problem of maximizing network lifetime as an optimal scheduling problem. We consider a special case where the data rate is linearly proportional to received signal power, investigating both static and dynamic scheduling strategies. The optimal static schedule turns out to have a very simple form. For the dynamic case, we obtain an integer linear program formulation to find the optimal strategy. We then propose an efficient algorithm that exploits the special nature of the problem setting to find the optimal solution quickly. Finally, we consider the general case where data rates and signal power need not be linearly related and propose an algorithm to find the optimal transmission times subject to the deadline constraint imposed by the system.

In wireless ad hoc networks, nodes communicate with far off destinations using intermediate nodes as relays. Since wireless nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. On the other hand, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios (complete cooperation and complete noncooperation) are inimical to the interests of a user. In this paper, we address the issue of user cooperation in ad hoc networks. We assume that nodes are rational, i.e., their actions are strictly determined by self interest, and that each node is associated with a minimum lifetime constraint. Given these lifetime constraints and the assumption of rational behavior, we are able to determine the optimal share of service that each node should receive. We define this to be the rational Pareto optimal operating point. We then propose a distributed and scalable acceptance algorithm called Generous TIT-FOR-TAT (GTFT). The acceptance algorithm is used by the nodes to decide whether to accept or reject a relay request. We show that GTFT results in a Nash equilibrium and prove that the system converges to the rational and optimal operating point.

In this paper, we address the problem of energy efficiency in wireless ad hoc networks. We consider an ad hoc network comprising a set of sources, communicating with their destinations using multiple routes. Each source is associated with a utility function which increases with the total traffic flowing over the available source-destination routes. The network lifetime is defined as the time until the first node in the network runs out of energy. We formulate the problem as one of maximizing the sum of the source utilities subject to a required constraint on the network lifetime. We present a primal formulation of the problem, which uses penalty functions to take into account the system constraints, and we introduce a new methodology for solving the problem. The proposed approach leads to a flow control algorithm, which provides the optimal source rates and can be easily implemented in a distributed manner. When compared with the minimum transmission energy routing scheme, the proposed algorithm gives significantly higher source rates for the same network lifetime guarantee.

In wireless ad hoc networks, nodes communicate with far off destinations using intermediate nodes as relays. Since wireless nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. On the other hand, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios (complete cooperation and complete noncooperation) are inimical to the interests of a user. In this paper we address the issue of user cooperation in ad hoc networks. We assume that nodes are rational, i.e., their actions are strictly determined by self interest, and that each node is associated with a minimum lifetime constraint. Given these lifetime constraints and the assumption of rational behavior, we are able to determine the optimal throughput that each node should receive. We define this to be the rational Pareto optimal operating point. We then propose a distributed and scalable acceptance algorithm called generous tit-for-tat (GTFT). The acceptance algorithm is used by the nodes to decide whether to accept or reject a relay request. We show that GTFT results in a Nash equilibrium and prove that the system converges to the rational and optimal operating point.

In this paper, we address the problem of energy-conscious cache placement in wireless ad hoc networks. We consider a network comprising a server with an interface to the wired network, and some nodes requiring access to the information stored at the server. In order to reduce access latency in such a communication environment, an effective strategy is caching the server information at some nodes distributed across the network. Caching, however, can considerably impact the system energy expenditure; for instance, disseminating information incurs additional energy burden. Since wireless devices have limited amounts of available energy, we need to design caching strategies that optimally trade-off between energy consumption and access latency. We pose our problem as an integer linear program. We show that this problem is the same as a special case of the connected facility location problem, which is known to be NP-hard. We devise a polynomial time algorithm which provides a sub-optimal solution. The proposed algorithm applies to any arbitrary network topology and can be implemented in a distributed and asynchronous manner. In the case of a tree topology, our algorithm gives the optimal solution. In the case of an arbitrary topology, it finds a feasible solution with an objective function value within a factor of 6 of the optimal value. This performance is very close to the best approximate solution known today, which is obtained in a centralized manner. We compare the performance of our algorithm against three candidate caching schemes, and show via extensive simulation that our algorithm consistently outperforms these alternative schemes.

Wireless networking has experienced a great deal of popularity, and significant advances have been made in wireless technology. However, energy efficiency of radio communication systems is still a critical issue due to the limited battery capacity of portable devices. In this paper, we deal with the charge recovery effect that takes place in electrochemical cells and show how we can take advantage of this mechanism to increase the energy delivered by a battery. Then, we present energy-aware traffic shaping techniques, as well as scheduling and routing algorithms, which exploit the battery recovery effect.

In this paper, we address the problem of energy efficient packet scheduling in a wireless environment. We consider a wireless transmitter which is limited by its finite battery resource. Our objective is to design a transmission schedule that maximizes battery lifetime subject to some delay constraints. To achieve this, we exploit two previously unconnected ideas: (i) channel coding can be used to conserve energy by transmitting at reduced power levels over longer durations; (ii) electro-chemical mechanisms in batteries allow them to recover energy during idle periods. While the first idea favors extending transmission durations, the second idea requires the transmitter to be idle to allow for recovery. Therefore, a strategy which is based entirely on either one or the other idea is not optimal. We provide a framework to merge these two ideas. We consider two kinds of delay constraints, one a deadline constraint and the other an average delay constraint and show that energy aware scheduling strategies for both these scenarios can result in significant energy savings.

In this paper, we address the problem of energy efficiency in ad hoc wireless networks. We consider a network that is shared by a set of sources, each one communicating with its corresponding destination using multiple routes. Each source is associated with a utility function which increases with the total traffic flowing over the available source-destination routes. The network lifetime is defined as the time until the first node in the network runs out of energy. We formulate the problem as one of maximizing the sum of the sources' utilities subject to the required constraint on network lifetime. We present a primal formulation of the problem, which uses penalty functions to take into account the system constraints, and we introduce a new methodology for solving the problem. The proposed approach leads to a flow control algorithm, which provides the optimal sources' rate and can be easily implemented in a distributed manner. When compared with the minimum transmission energy routing scheme, the proposed algorithm gives significantly higher sources' rates for same network lifetime guarantee.

In wireless ad hoc networks, nodes communicate with far off destinations using intermediate nodes as relays. Since nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. However, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios (complete cooperation and complete non-cooperation) are inimical to the interests of a user. In this paper, we address the issue of user cooperation in ad hoc networks. We assume that nodes are rational, i.e. their actions are strictly determined by self-interest, and that each node is associated with a minimum lifetime constraint. Then, we are able to determine the optimal throughput that each node should receive, and we define this to be the rational Pareto optimal operating point. We propose a distributed and scalable acceptance algorithm, which is used by the nodes to decide whether to accept or reject a relay request. The algorithm results in a Nash equilibrium, and we prove that the system converges to the rational and optimal operating point.

In an effort to conserve energy, mobile hosts wake up periodically to serve incoming traffic. This gives rise to a trade-off between energy consumption and delay. However, the deterministic strategy of current systems might not yield the desired performance. We show that knowledge of the statistical characteristics of incoming traffic can be used to better meet the energy and delay requirements of the mobile node. We consider zero-buffer and buffered models. We propose some strategies to improve the energy efficiency and study the related trade-offs. We also introduce a new metric for energy efficiency and derive explicit expressions for the same. Our results prove that significant gains accrue by employing intelligent wake-up schemes.