We consider a set of cellular users associated with a base station (BS) in a cellular network that employs Device-to-device (D2D) communication. A subset of the users request for some files from the BS. Now, some of the users can potentially act as relays and forward the requested files, or partitions of files, from the BS to the requesting users (destination nodes) over D2D links. However, this requires cooperation among the cellular users. Also, when cellular users cooperate with each other, the total amount of energy consumed in transferring the requested files from the BS to the destination nodes can usually be considerably reduced compared to the case when each user separately downloads the file it needs from the BS. In this paper, we seek conditions under which users have an incentive to cooperate with each other. To this end, we model the above scenario using the framework of cooperative game theory. We are particularly interested in conditions under which it is beneficial for all the cellular users to cooperate, i.e., the grand coalition is stable. For this we use the solution concept of core from cooperative game theory. We consider two different models: (i) Model A, in which the BS can split a file into multiple partitions and send these partitions to different relays, which multicast the partitions to the destination nodes, and (ii) Model B, in which for each file, the BS sends the entire file to a single relay, which multicasts it to the destination nodes. First, we show that, in general, the above coalitional game under Model A may have an empty core, i.e., it may not be possible to stabilize the grand coalition. However, we show that in an important special case of this game, wherein all D2D and BS-cellular user communication links are symmetric across cellular users and the D2D data rates are much higher than the BS-cellular user data rates, the core is always non-empty. Next, we show that under Model B, the problem of assigning relays to destination nodes so as to maximize the sum of utilities of all the users is NP-Complete. Finally, we design heuristics to solve this problem and evaluate their performance via numerical computations.

Machine-to-Machine (M2M) networks are an emerging technology with applications in various fields including smart grids, healthcare, vehicular telematics, smart cities etc. Heterogeneous M2M networks contain different types of nodes, e.g., nodes that send emergency, periodic and normal type data. An important problem is to rapidly estimate the number of active nodes of each node type in every time frame in such a network. In this paper, we design an estimation scheme for estimating the active node cardinalities of each node type in a heterogeneous M2M network with three types of nodes. Our scheme consists of two phases- in phase 1, coarse estimates are computed and these estimates are used to compute the final estimates to the required accuracy level in phase 2. We analytically derive a condition that can be used to decide as to which of two possible approaches is to be used in phase 2. Using simulations, we show that our proposed scheme requires significantly fewer time slots to execute compared to separately executing a well-known estimation protocol designed for a homogeneous network in prior work thrice to estimate the cardinalities of the three node types, even though both these schemes obtain estimates with the same accuracy.

Machine-to-Machine (M2M) networks are an emerging technology with applications in numerous areas including smart grids, smart cities, vehicular telematics, healthcare, security and public safety. In this paper, we design a medium access control (MAC) protocol that supports multi-channel operation for a heterogeneous M2M network, with three types of M2M devices (e.g., those that send emergency, periodic and normal type data), operating as a secondary network using Cognitive Radio technology. Also, we design an estimation protocol for rapidly obtaining separate estimates of the number of active nodes of each traffic type, and use these estimates to find the optimal contention probabilities to be used in the Cognitive MAC protocol. We compute a closed form expression for the expected number of time slots required by our estimation protocol to execute as well as a simple upper bound on it, which shows that the expected number of time slots required by our protocol to obtain the above estimates is small. Also, we mathematically analyze the performance of the Cognitive MAC protocol and obtain expressions for the expected number of successful contentions and the expected amount of energy consumed per frame. Finally we evaluate the performance, in terms of average throughput and average delay, of our MAC protocol using simulations.

Vehicular traffic congestion is a major problem all over the world with significant economic and environmental impact. Adapting traffic signal durations is one method to alleviate this problem and has the advantage that it does not require any significant changes to existing infrastructure such as traffic poles and roads. Reinforcement learning is suitable for adapting the traffic signal durations since it does not require any prior knowledge of traffic patterns, which are time-varying and a priori unknown. In reinforcement learning based schemes proposed in previous studies, the algorithm for adapting the durations of a traffic signal takes into account only the vehicle queue lengths at that signal. In this paper, we propose a novel Q-Learning based algorithm, which adapts the durations of a signal by taking into account the vehicle queue lengths at all the signals that are n or fewer hops away from the signal, where n is a parameter that enables us to trade performance with computational complexity. In particular, our simulations show that as n increases, the performance of the algorithm improves in terms of travelling time, number of moving vehicles as well as Carbon dioxide emissions, albeit at the expense of an increase in computation time. Further, we consider the case in which n is increased gradually as time progresses, and show that the performance achieved is significantly better than in the case where n is a constant.

Dynamic Spectrum Access technology enables two types of users to operate on a channel- primary users, which have prioritized access to the channel and secondary users, which can use the channel when it is not in use by the primaries. We consider a scenario in which multiple primaries own bandwidth in a large region (e.g., a state), which is divided into smaller locations (e.g., towns). A primary that has unused bandwidth in a time slot would like to lease it out to secondaries at a set of mutually non-interfering locations in return for a fee. This results in price competition among the primaries. In prior work, this price competition has only been studied under the approximation, made for analytical tractability, that the price of each primary takes values from a continuous set. However, in practice, the set of available prices is discrete. In this paper, we investigate the fundamental question of how the behaviour of the players involved in the price competition changes when this continuity assumption is removed. Our analysis reveals several important differences between the games with continuous and discrete price sets. For example, in the game at a single location, no pure strategy Nash equilibrium (NE) exists in the game with continuous price sets, whereas a pure strategy NE may exist in the game with discrete price sets. Also, multiple symmetric NE exist in the game with discrete price sets in contrast to the game with continuous price sets, where a unique NE exists. However, we show that as the number of available prices becomes large in the discrete prices game, the strategies of the primaries under every symmetric NE converge to the unique NE strategy of the game with continuous price sets.

The design of an efficient Medium Access Control (MAC) protocol for multichannel ad hoc Cognitive Radio Networks is an important problem and has been the topic of extensive recent research. In this paper, we present the design and performance evaluation of a protocol, Group MAC (GMAC), which is customized for a situation that commonly arises in ad hoc networks: the network consists of multiple groups of nodes such that a large fraction of the traffic of each node needs to be sent to other nodes of its own group. Some examples are: (a) units (e.g., platoons) in a military ad hoc network, (b) divisions in an emergency or disaster relief network, (c) departments in a corporate or university network. Our protocol requires each secondary node to have only one narrowband transceiver, does not rely on a control channel and incorporates a novel technique for dynamically balancing the traffic load of secondary nodes across the set of free channels. We analyze the stability region of the protocol using a queuing theoretic framework. Our extensive simulations show that a large fraction of the bandwidth unoccupied by primary users is utilized by the GMAC protocol for data transmissions.

In Cognitive Radio Networks (CRN), there are multiple primary and secondary users in a region, and primaries can lease out their unused bandwidth to secondaries in exchange for a fee. This gives rise to price competition among the primaries, wherein each primary tries to attract secondaries by setting a lower price for its bandwidth than the other primaries. Radio spectrum has the distinctive feature that transmissions at neighboring locations on the same channel interfere with each other, whereas the same channel can be used at far-off locations without mutual interference. So in the above price competition scenario in a CRN, each primary must jointly select a set of mutually non-interfering locations within the region (which corresponds to an independent set in the conflict graph representing the region) at which to offer bandwidth and the price at each location. In this paper, we analyze this price competition scenario as a game and seek a Nash Equilibrium (NE). We identify a class of conflict graphs, which we refer to as mean valid graphs, such that the conflict graphs of a large number of topologies that commonly arise in practice are mean valid. We explicitly compute a symmetric NE in mean valid graphs and show that it is unique.

We analyze price competition among primary users in a Cognitive Radio Network (CRN), in which there are a random and unknown number of secondary users. In every slot, each primary has unused bandwidth with some probability, which it would like to lease to a secondary user, and must set a price for this bandwidth. The valuations of the secondary users for unit bandwidth are independent and identically distributed random variables. We analyze this price competition as a game and explicitly compute a Nash Equilibrium (NE), which we show to be unique in the class of symmetric NE. We show that randomness in the valuations of the secondary users results in significant structural differences in the strategies of the primaries in the NE compared to the case in which the valuations of the secondaries are constants.

Wireless sensor networks (WSNs) have recently emerged as a key sensing technology with diverse civilian and military applications. In these networks, a large number of small sensors or nodes perform distributed sensing of a target field. Each node is capable of sensing events of interest within its sensing range and communicating with neighboring nodes. The target field is said to be$k$-covered if every point in it is within the sensing range of at least$k$sensors, where$k$is any positive integer. We present a comprehensive framework for verifying$k$-coverage of a$d$-dimensional target field for an arbitrary positive integer$k$and$d \in \{1, 2, 3\}$. Our framework uses a divide-and-conquer approach based on the technique of dimension reduction, in which the$k$-coverage verification problem in$d$dimensions is reduced to a number of coverage verification problems in$(d-1)$dimensions, which are then recursively solved. Our framework leads to a distributed polynomial-time coverage verification algorithm that does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in WSNs. Each node can execute the algorithm using only the distances between adjacent nodes within its transmission range and their sensing radii. We analytically prove that the scheme detects a coverage hole if and only if the target field has a coverage hole.

We consider price competition among multiple primary users in a cognitive radio network with multiple secondary users. Each primary has unused bandwidth with some probability, possibly different for different primaries, which he would like to lease to a secondary. For the case in which all the primaries and secondaries are in a single location, we explicitly compute a Nash equilibrium (NE) and show its uniqueness. Then we consider the game with spatial reuse of spectrum, and for linear conflict graphs, explicitly compute a NE and show its uniqueness in a natural sub-class of NE.

In this paper, we address the spectrum portfolio optimization (SPO) question in the context of secondary spectrum markets, where bandwidth (spectrum access rights) can be bought in the form of primary and secondary contracts. While a primary contract on a channel provides guaranteed access to the channel bandwidth (possibly at a higher per-unit price), the bandwidth available to use from a secondary contract (possibly at a discounted price) is typically uncertain/stochastic. The key problem for the buyer (service provider) in this market is to determine the amount of primary and secondary contract units needed to satisfy uncertain user demand. We initially consider a single-region problem in which the spectrum contracts are valid only in the single-region in which the buyer wishes to provide service. We formulate the problem as one of minimizing the cost of the spectrum portfolio subject to constraints on bandwidth shortage. Two different forms of bandwidth shortage constraints are considered, namely, the demand satisfaction rate constraint, and the demand satisfaction probability constraint. While the SPO problem under demand satisfaction rate constraint is shown to be convex for all density functions, the SPO problem under demand satisfaction probability constraint is not convex in general. We derive some sufficient conditions for convexity for this case. The SPO problems can therefore be solved efficiently using standard convex optimization techniques. Later, we extend the problem formulation and the convexity results to the multiple-region setting, where the buyer's portfolio is intended to serve a set of disjoint geographical locations, each having its own customer demand. Finally, we perform a thorough simulation-based study of the single-region and the multiple-region problems for different choices of the problem parameters, and provide key insights regarding the portfolio composition and demonstrate the convexity of the efficient frontier. We provide several insights about the scaling behavior of the unit prices of the secondary contracts, as the stochastic characterization of the bandwidth available from secondary contracts change.

In wireless sensor networks (WSNs), a large number of sensors perform distributed sensing of a target field. A sensor cover is a subset of the set of all sensors that covers the target field. The lifetime of the network is the time from the point the network starts operation until the set of all sensors with nonzero remaining energy does not constitute a sensor cover any more. An important goal in sensor networks is to design a schedule-that is, a sequence of sensor covers to activate in every time slot-so as to maximize the lifetime of the network. In this paper, we design a polynomial-time distributed algorithm for maximizing the lifetime of the network and prove that its lifetime is at most a factorO(logn* lognB) lower than the maximum possible lifetime, wherenis the number of sensors andBis an upper bound on the initial energy of each sensor. Our algorithm does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in sensor networks. Each sensor only needs to know the distances between adjacent nodes in its transmission range and their sensing radii. In every slot, the algorithm first assigns a weight to each node that is exponential in the fraction of its initial energy that has been used up so far. Then, in a distributed manner, it finds anO(logn) approximate minimum weight sensor cover, which it activates in the slot.

In cognitive radio networks (CRN), primary users can lease out their unused bandwidth to secondary users in return for a fee. We study price competition in a CRN with multiple primaries and multiple secondaries in a region, where each primary tries to attract secondaries by setting a lower price for his bandwidth than other primaries. A CRN has two distinctive features, which makes the price competition very different from that in traditional commodity markets. First, in every slot, each primary may or may not have unused bandwidth available. So primaries are uncertain about the number of other primaries from whom they face competition. Second, spectrum is a commodity that allows spatial reuse: the same band can be simultaneously used at far-off locations without interference; on the other hand, simultaneous transmissions at neighboring locations on the same band interfere with each other. As a result, a primary cannot offer bandwidth at all locations, but must select an independent set of locations at which to offer it. Also, the choice of the independent set and the prices at those locations must be made jointly. We formulate price competition in a CRN as a game, taking into account both bandwidth uncertainty and spatial reuse. We analyze the game in a single slot, as well as its repeated version. In each case, we not only prove the existence of a Nash equilibrium, but also explicitly compute it. The expressions we obtain provide interesting insights into how the price competition evolves for different values of the system parameters. Moreover, for the game in a single slot, we prove the uniqueness of the Nash equilibrium in the class of symmetric equilibria.

In cognitive radio networks, there are two categories of networks on different channels: primary networks, which have high-priority access, and secondary networks, which have low-priority access. We develop an auction-based framework that allows networks to bid for primary and secondary access based on their utilities and traffic demands. The bids are used to solve the access allocation problem, which is that of selecting the primary and secondary networks on each channel either to maximize the auctioneer's revenue or to maximize the social welfare of the bidding networks, while enforcing incentive compatibility. We first consider the case when the bids of a network depend on which other networks it will share channels with. When there is only one secondary network on each channel, we design an optimal polynomial-time algorithm for the access allocation problem based on reduction to a maximum matching problem in weighted graphs. When there can be two or more secondary networks on a channel, we show that the optimal access allocation problem is NP-complete. Next, we consider the case when the bids of a network are independent of which other networks it will share channels with. We design a polynomial-time dynamic programming algorithm to optimally solve the access allocation problem when the number of possible cardinalities of the set of secondary networks on a channel is upper-bounded. Finally, we design a polynomial-time algorithm that approximates the access allocation problem within a factor of 2 when the above upper bound does not exist.

Wireless Sensor Networks are emerging as a key sensing technology, with diverse military and civilian applications. In these networks, a large number of sensors perform distributed sensing of a target field. Each sensor is a small battery-operated device that can sense events of interest in its sensing range and can communicate with neighboring sensors. A sensor cover is a subset of the set of all sensors such that every point in the target field is in the interior of the sensing ranges of at least $k$ different sensors in the subset, where k is a given positive integer. The lifetime of the network is the time from the point the network starts operation until the set of all sensors with non-zero remaining energy does not constitute a sensor cover. An important goal in sensor networks is to design a schedule, that is, a sequence of sensor covers to activate in every time slot, so as to maximize the lifetime of the network. In this paper, we design a polynomial-time, distributed algorithm for maximizing the lifetime of the network and prove that its lifetime is at most a factor O(log n * log nB) lower than the maximum possible lifetime, where n is the number of sensors and B is an upper bound on the initial energy of each sensor. Our algorithm does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in sensor networks. Each sensor only needs to know the distances between adjacent nodes in its transmission range and their sensing radii. In every slot, the algorithm first assigns a weight to each node that is exponential in the fraction of its initial energy that has been used up so far. Then, in a distributed manner, it finds a O(log n) approximate minimum weight sensor cover which it activates in the slot. Our simulations reveal that our algorithm substantially outperforms several existing lifetime maximization algorithms.

In cognitive radio networks, there are two categories of networks on different channels: primary networks, which have highpriority access, and secondary networks, which have low-priority access. We develop an auction-based framework that allows networks to bid for primary and secondary access based on their utilities and traffic demands. The bids are used to solve the access allocation problem, which is that of selecting the primary and secondary networks on each channel either to maximize the auctioneer’s revenue or to maximize the social welfare of the bidding networks, while enforcing incentive compatibility. We first consider the case when the bids of a network depend on which other networks it will share channels with. When there is only one secondary network on each channel, we design an optimal polynomial-time algorithm for the access allocation problem based on reduction to a maximum matching problem in weighted graphs. When there can be two or more secondary networks on a channel, we show that the optimal access allocation problem is NP-Complete. Next, we consider the case when the bids of a network are independent of which other networks it will share channels with. We design a polynomial-time dynamic programming algorithm to optimally solve the access allocation problem when the number of possible cardinalities of the set of secondary networks on a channel is upper-bounded. Finally, we design a polynomial-time algorithm which approximates the access allocation problem within a factor of 2 when the above upper bound does not exist.

Wireless sensor networks (WSNs) have recently emerged as a key sensing technology with diverse civilian and military applications. In these networks, a large number of small sensors or nodes perform distributed sensing of a target field. Each node is capable of sensing events of interest within its sensing range and communicating with neighboring nodes. The target field is said to be k-covered if every point in it is within the sensing range of at least k sensors, where k is any positive integer. We present a comprehensive framework for verifying k-coverage of a d-dimensional target field for arbitrary positive integers k, d. Our framework uses a divide and conquer approach based on the technique of dimension reduction, in which the k-coverage verification problem in d-dimensions is reduced to a number of coverage verification problems in (d-1) dimensions, which are then recursively solved. Our framework leads to a distributed polynomial-time coverage verification algorithm that does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in WSNs. Each node can execute the algorithm using only the distances between adjacent nodes within its transmission range and their sensing radii. We analytically prove that the scheme detects a coverage hole if and only if the target field has a coverage hole.

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.