Group testing is traditionally considered effective only in settings with low infection rates. However, recent models that capture correlation among individuals, especially through hypergraphs, raise the question of whether group testing can remain efficient even when the infection rate is high. In this work, we study adaptive group testing under correlated settings modeled by hypergraphs and show that group testing can remain effective by leveraging these correlations to infer node states. We first state our results for k-partite hypergraphs and graphs with pairwise bounded edge intersections, and provide testing strategies that remain efficient even when the average number of infections is high. We then focus on a special class of hypergraphs called hypertrees, where infections originate from a single seed, and show that the number of tests depends on the Hamiltonian number of the underlying tree and the entropy of the edges. We then generalize the results to two seeds infection and more general contact graphs.

Group testing, a problem with applications in various fields, traditionally assumes independent node states. Recent research, however, focuses on real-world scenarios that often involve correlations among nodes, challenging the simplifying assumptions made in existing models. In this work, we consider a comprehensive model for arbitrary statistical correlation among node states. To capture and leverage these correlations effectively, we model the problem by hypergraphs inspired by [1]. We establish that arbitrary correlations among nodes can be represented as a hypergraph with a probability distribution over its edges, and design a novel greedy adaptive algorithm capable of conducting informative tests and dynamically updating the distribution. We analyze its performance and give theoretical guarantees on the number of tests that depend solely on the entropy of the underlying probability distribution and the average number of infections.

In applications of group testing in networks, e.g. identifying individuals who are infected by a disease spread over a network, exploiting correlation among network nodes provides fundamental opportunities in reducing the number of tests needed. We model and analyze group testing on n correlated nodes whose interactions are specified by a graph G. We model correlation through an edge-faulty random graph formed from G in which each edge is dropped with probability$1-r$, and in the newly formed graph, all nodes in the same component have the same state. We consider three classes of graphs: cycles and trees, d-regular graphs and stochastic block models or SBM, and obtain lower and upper bounds on the number of tests needed to identify the defective nodes. Roughly speaking, we use correlation among the states of the nodes to transform the problem into that of a smaller graph with independent node states. This enhancement is quantified through the ratio of the diminished node count to the overall count of nodes, n; thus, a lower ratio signifies superior performance. The lower bounds are derived by illustrating a strong dependence of the number of tests needed on the expected number of components. In this regard, we establish a new approximation for the distribution of component sizes in “d-regular trees” which may be of independent interest and leads to a lower bound on the expected number of components in d-regular graphs. The upper bounds are found by forming dense subgraphs in which nodes are more likely to be in the same state. When G is a cycle or tree, we show an improvement by a factor of$\log (1/r)$. For grid, a graph with almost$2n$edges, the improvement is by a factor of$(1-r) \log (1/r)$, indicating drastic improvement compared to trees. When G has a larger number of edges, as in SBM, the improvement can scale in n.

Emerging V2X technology enables vehicles to exchange messages with each other (V2V) and with signaling infrastructure (I2V) on the roadways. Information propagation in transportation networks is highly influenced by both vehicle mobility and wireless communication. As for vehicle mobility, realistic traffic flow changes with time, exhibiting sharp time-triggered transitions, due to external factors such as traffic lights. Thus, mobility process is temporally heterogeneous and not smooth, which fundamentally alters the dynamics of V2X (V2V and I2V together) message propagation in a complex manner. As for wireless communication, communication heterogeneity is an integral component of V2X systems - different types of vehicles may have different communication capabilities, and V2V and I2V communications coexist. We propose a mathematical framework, based on a continuous-time Markov chain (CTMC), for characterizing the spatio-temporal spread of V2X information (1) when the traffic flow exhibits sharp time-triggered transitions and (2) when there exists communication heterogeneity comprising of different V2V commutation capabilities, different wireless communication conditions, and both V2V and I2V. We prove that the state evolutions under the CTMC model converge to a set of differential equations in the asymptotic limit of a large number of vehicles, enabling computations that gracefully scale with increase in network size and the number of vehicles. Our framework can accommodate arbitrary traffic synchronization patterns corresponding for example to incorporate the presence of an arbitrary number of traffic signals. Furthermore, numerical computations using this mathematical framework answer several questions that influence the practice of V2X network design and security.

With the growth of big data in the past few decades, compression has become inseparable from data generation. The data generated daily across different platforms are correlated: friend networks on Facebook and Instagram, contact networks in subsequent days, and many more. This raises the question of compressing a dataset using another correlated dataset. For instance, can we compress the Facebook graph of friends when we know Instagram’s graph? This can be cast as the classical problem of source coding with side information, and the answer is known to be positive when the graphs are "labeled" and/or aligned, meaning we need to know the node corresponding to Jon Doe in both Facebook and Instagram graphs. The classical idea is to utilize joint typicality to decide whether two graphs are correlated or not. In practice, graphs are often not aligned and/or the labels are concealed to keep the identity of the users private. In these scenarios, classical ideas are no longer applicable as joint typicality highly depends on the ordering of sequences. In this work, we prove for the first time the existence of lossless graph compression schemes that utilize unlabeled side information and improve the compression rate. In order to do that, we design binning along with a novel testing criterion that relies on graph matching, the closely related quadratic assignment problem and its asymptotic properties.

In applications of group testing in networks, e.g. identifying individuals who are infected by a disease spread over a network, exploiting correlation among network nodes provides fundamental opportunities in reducing the number of tests needed. We model and analyze group testing on n correlated nodes whose interactions are specified by a graph G. We model correlation through an edge-faulty random graph formed from G in which each edge is dropped with probability 1−r, and all nodes in the same component have the same state.We consider three classes of graphs: cycles and trees, d-regular graphs, and stochastic block models or SBM, and obtain lower and upper bounds on the number of tests needed to identify the defective nodes. Our results are expressed in terms of the number of tests needed when the nodes are independent and they are in terms of n, r, and the target error. In particular, we quantify the fundamental improvements that exploiting correlation offers by the ratio between the total number of nodes n and the equivalent number of independent nodes in a classic group testing algorithm.The lower bounds are derived by illustrating a strong dependence of the number of tests needed on the expected number of components. In this regard, we establish a new approximation for the distribution of component sizes in "d-regular trees" which may be of independent interest and leads to a lower bound on the expected number of components in d-regular graphs.The upper bounds are found by forming dense subgraphs in which nodes are more likely to be in the same state. When G is a cycle or tree, we show an improvement by a factor of log(1/r). For grid, a graph with almost 2n edges, the improvement is by a factor of (1 − r)log(1/r), indicating drastic improvement compared to trees. When G has a larger number of edges, as in SBM, the improvement can scale in n.

Information propagation in V2V-enabled transportation networks is highly influenced by both vehicle mobility and wireless communication. The mobility patterns and communication conditions are not only heterogeneous, but also vary both temporally and spatially. In particular, realistic traffic flow changes with time, exhibiting sharp time-triggered transitions, due to external factors such as traffic lights, unpredictable disruptions (e.g., accidents), and planned disruptions (e.g., road-block). More specifically, traffic signals cause traffic synchronization, due to vehicles stopping during the red phase, and starting almost simultaneously during the green phase, which fundamentally alters the dynamics of V2V message propagation in a complex manner. In this paper, we propose a mathematical framework, starting from a continuous-time Markov chain, that characterizes the fraction of vehicles that have received a message over time and space in an arbitrary road network even when the traffic flow exhibits sharp time-triggered transitions. Our framework can accommodate arbitrary traffic synchronization patterns corresponding for example to the presence of an arbitrary number of traffic signals. The stochastic model for V2V message flow converges to a set of differential equations as the number of vehicles increases. The analytical characterization lends itself to a fast computation regardless of the number of vehicles and traffic synchronization patterns, while vehicular network simulators can only realistically simulate small-scale transportation networks. We find that V2V simulations of a statistical model with traffic synchronization and simulation of communications applied on a synthetic traffic trace well match our model solution.

We consider a system in which there exists two ISPs, one “big” Content Provider (CP), and a continuum of End-Users (EUs). One of the ISPs is neutral and the other is non-neutral. We consider that the CP can differentiate between ISPs by controlling the quality of the content she is offering on each one. We also consider that EUs have different levels of innate preferences for ISPs. We formulate a sequential game, and explicitly characterize all the possible Sub-game Perfect Nash Equilibria (SPNE) of the game. We prove that if an SPNE exists, it would be one of the five possible strategies each of which we explicitly characterize. We prove that when EUs have sufficiently low innate preferences for ISPs, a unique SPNE exists in which the neutral ISP would be driven out of the market. We also prove that when these preferences are sufficiently high, there exists a unique SPNE with a non-neutral outcome in which both ISPs are active. Numerical results reveal that the neutral ISP receives a lower payoff and the non-neutral ISP receives a higher payoff (most of the time) in a non-neutral scenario. However, we identify scenarios in which the non-neutral ISP loses payoff by adopting non-neutrality. We also show that a non-neutral regime yields a higher welfare for EUs in comparison to a neutral one if the market power of the non-neutral ISP is small, the sensitivity of EUs (respectively, the CP) to the quality is low (respectively, high), or a combinations of these factors.

We consider a secondary spectrum market where primaries set prices for their unused channels. The payoff of a primary then depends on the availability of channels for its competitors, which a primary might not have information about. We study a model where a primary can acquire this competitor's channel state information (C-CSI) at a cost. We formulate a game between two primaries, where each primary decides whether to acquire the C-CSI or not and then selects its price based on that. We first characterize the Nash equilibrium of this game for a symmetric model where the C-CSI is perfect. We show that the payoff of a primary is independent of the C-CSI acquisition cost. We then generalize our analysis to allow for imperfect estimation and cases, where the two primaries have different C-CSI costs or different channel availabilities. Our results show interestingly that the payoff of a primary increases when there is estimation error. We also show that surprisingly the expected payoff of a primary may decrease when the C-CSI acquisition cost decreases or primaries have different availabilities.

The growing demand for data has driven the service providers (SPs) to provide differential treatment of traffic to generate additional revenue streams from content providers (CPs). While SPs currently only provide best-effort services to their CPs, it is plausible to envision a model in near future, where CPs are willing to sponsor quality of service for their content in exchange of sharing a portion of their profit with SPs. This quality sponsoring becomes invaluable especially when the available resources are scarce, such as in wireless networks, and can be accommodated in a non-neutral network. In this paper, we consider the problem of quality-sponsored data (QSD) in a non-neutral network. In our model, SPs allow CPs to sponsor a portion of their resources, and price it appropriately to maximize their payoff. The payoff of the SP depends on the monetary revenue and the satisfaction of end-users both for the non-sponsored and sponsored content, while CPs generate revenue through advertisement. Note that in this setting, end-users still pay for the data they use. We analyze the market dynamics and equilibria in two different frameworks, i.e., sequential and bargaining game frameworks, and provide strategies for: 1) SPs-to determine if and how to price resources and 2) CPs-to determine if and what quality to sponsor. The frameworks characterize different sets of equilibrium strategies and market outcomes depending on the parameters of the market.

In a secondary spectrum market primaries set prices for their unused channels to the secondaries. The payoff of a primary depends on the channel state information (CSI) of its competitors. We consider a model where a primary can acquire its competitors CSI at a cost. We formulate a game between two primaries where each primary decides whether to acquire its competitor's CSI or not and then selects its price based on that. Our result shows that no primary decide to acquire its competitor's CSI with an absolute certainty. When the cost of acquiring the CSI is above a threshold, there is a unique Nash Equilibrium (NE) where both the primaries remain uninformed of their respective competitor's CSI. When the cost is below the threshold, in the unique NE each primary randomizes between its decision to acquire the CSI or not. Our result reveals that irrespective of the cost of acquiring the CSI, the expected payoff of a primary remains the same.

Studies on the propagation of malware in mobile networks have revealed that the spread of malware can be highly inhomogeneous. Platform diversity, contact list utilization by the malware, clustering in the network structure, etc., can also lead to differing spreading rates. In this paper, a general formal framework is proposed for leveraging such heterogeneity to derive optimal patching policies that attain the minimum aggregate cost due to the spread of malware and the surcharge of patching. Using Pontryagin's Maximum Principle for a stratified epidemic model, it is analytically proven that in the mean-field deterministic regime, optimal patch disseminations are simple single-threshold policies. These policies are amenable to implementation and can serve as benchmarks for policies that have less knowledge of the network. Through numerical simulations, the behavior of optimal patching policies is investigated in sample topologies, and their advantages are demonstrated.

We investigate a spectrum oligopoly market where each primary seeks to sell its channel to a secondary. Transmission rate of a channel evolves randomly. Each primary needs to select a price depending on the transmission rate of its channel. Each secondary selects a channel depending on the price and the transmission rate of the channel. We formulate the above problem as a noncooperative game. We show that there exists a unique Nash equilibrium (NE) and explicitly compute it. Under the NE strategy profile, a primary prices its channel to render the channel that provides high transmission rate more preferable; this negates the perception that prices ought to be selected to render channels equally preferable to the secondary regardless of their transmission rates. We show the loss of revenue in the asymptotic limit due to the noncooperation of primaries. In the repeated version of the game, we characterize a subgame perfect NE where a primary can attain a payoff arbitrarily close to the payoff it would obtain when primaries cooperate.

We investigate the economics of internet of things (IoT). An economic model of IoT consists of end users, advertisers and three different kinds of providers. We model different kinds of interaction among the providers as a combination of sequential and parallel non-cooperative games. We characterize the equilibrium pricing strategy and payoff of providers and corresponding demands of end users in each such setting. We quantify the impact of advertising revenue on the equilibrium pricing and demands, and compare the payoffs and demands for different interaction models.

In this paper, we study the problem of differential pricing and QoS assignment by a broadband data provider. In our model, the broadband data provider decides on the power allocated to an end-user not only based on parameters of the transmission medium, but also based on the price the user is willing to pay. In addition, end-users bid the price that they are willing to pay to the Base Station (BS) based on their channel condition, the throughput they require, and their belief about other users' parameters. We will characterize the optimum power allocation by the BS which turns out to be a modification of the solution to the well-known water-filling problem. We also characterize the optimum bidding strategy of end-users using the belief of each user about the cell condition.

We investigate a spectrum oligopoly where primary users allow secondary access in lieu of financial remuneration. Transmission qualities of the licensed bands fluctuate randomly. Each primary needs to select the price of its channel with the knowledge of its own channel state but not that of its competitors. Secondaries choose among the channels available on sale based on their states and prices. We formulate the price selection as a non-cooperative game and prove that a symmetric Nash equilibrium (NE) strategy profile exists uniquely. We explicitly compute this strategy profile and analytically and numerically evaluate its efficiency. Our structural results provide certain key insights about the unique symmetric NE.

The openness of the Android operating system increased the number of applications developed, but it also introduced a new propagation vector for mobile malware. We model the propagation of mobile malware using epidemiology theory and study the problem as a function of the underlying mobility models. We define the optimal approach to heal an infected system with the help of a set of static healers that distribute patches, as the T-COVER problem and show that it is NP-HARD. We then propose two families of healer protocols that trade-off time recovery and energy consumed by sending patches. The first one uses randomization to ensure a small recovery time but may result in healers sending more patches than needed. The second one uses system feedback to optimize energy consumed by sending patches, but it may result in a larger recovery time. We show through simulations using the NS-3 simulator that despite lacking knowledge of the future, our protocols obtain a recovery time within a 10x bound of the oracle solution that knows the arrival time of the infected nodes.

In this work, we investigate the use of epidemic routing in energy constrained Delay Tolerant Networks (DTNs). In DTNs, connected paths between source and destination rarely materialize due to the mobility and sparse density of nodes. Epidemic routing is well-suited for these environments due to its simplicity and fully distributed implementation. In epidemic routing, messages are relayed by intermediate nodes at contact opportunities, i.e., when pairs of nodes come within transmission range. Each node needs to decide whether to forward its message upon contact with a new node based on its residual energy level and the age of that message.

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.

Given the flexibility that software-based operation provides, it is unreasonable to expect that new malware will demonstrate a fixed behavior over time. Instead, malware can dynamically change the parameters of their infective hosts in response to the dynamics of the network, in order to maximize their overall damage. However, in return, the network can also dynamically change its counter-measure parameters in order to attain a robust defense against the spread of malware while minimally affecting the normal performance of the network. The infinite dimension of freedom introduced by variation over time and antagonistic and strategic optimization of malware and network against each other demand new attempts for modeling and analysis. We develop a zero-sum dynamic game model and investigate the structural properties of the saddle-point strategies. We specifically show that saddle-point strategies are simple threshold-based policies and hence, a robust dynamic defense is practicable.

The security threat posed by malware in mobile wireless networks can be countered through immunization using security patches. The distribution of patches, however, consumes bandwidth that is scarce in wireless networks, and must, there fore, be judiciously controlled in order to attain desired tradeoffs between security risks and bandwidth consumption. We consider both nonreplicative and replicative dissemination of patches: a predetermined set of dispatcher nodes distribute the patches in the former, whereas the dispatcher set continually grows in the latter as the nodes that receive the patch become dispatchers themselves. In each case, the desired tradeoffs can be attained by activating at any given time only fractions of dispatchers and selecting their packet transmission rates. We formulate the afore said tradeoffs as optimal control problems that seek to minimize the aggregate network costs that depend on security risks and the overall extra bandwidth used in the network for dissemination of the security patches. We prove that the dynamic control strategies have simple structures: when the cost function associated with the bandwidth consumed in patching is concave, the control strategies are bang-bang with at most one jump from the maximum to the minimum value. When the cost function is strictly convex, the aforesaid transition is strict but continuous. We compare the efficacy of different dispatch models and also those of the optimum dynamic and static controls using numerical computations.

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.

Malware attacks constitute a serious security risk that threatens to slow down the large-scale proliferation of wireless applications. As a first step toward thwarting this security threat, we seek to quantify the maximum damage inflicted on the system due to such outbreaks and identify the most vicious attacks. We represent the propagation of malware in a battery-constrained mobile wireless network by an epidemic model in which the worm can dynamically control the rate at which it kills the infected node and also the transmission ranges and/or the media scanning rates. At each moment of time, the worm at each node faces the following tradeoffs: 1) using larger transmission ranges and media scanning rates to accelerate its spread at the cost of exhausting the battery and thereby reducing the overall infection propagation rate in the long run; or 2) killing the node to inflict a large cost on the network, however at the expense of losing the chance of infecting more susceptible nodes at later times. We mathematically formulate the decision problems and utilize Pontryagin Maximum Principle from optimal control theory to quantify the damage that the malware can inflict on the network by deploying optimum decision rules. Next, we establish structural properties of the optimal strategy of the attacker over time. Specifically, we prove that it is optimal for the attacker to defer killing of the infective nodes in the propagation phase until reaching a certain time and then start the slaughter with maximum effort. We also show that in the optimal attack policy, the battery resources are used according to a decreasing function of time, i.e., most aggressively during the initial phase of the outbreak. Finally, our numerical investigations reveal a framework for identifying intelligent defense strategies that can limit the damage by appropriately selecting network parameters.

We consider a network in which several service providers offer wireless access to their respective subscribed customers through potentially multihop routes. If providers cooperate by jointly deploying and pooling their resources, such as spectrum and infrastructure (e.g., base stations) and agree to serve each others' customers, their aggregate payoffs, and individual shares, may substantially increase through opportunistic utilization of resources. The potential of such cooperation can, however, be realized only if each provider intelligently determines with whom it would cooperate, when it would cooperate, and how it would deploy and share its resources during such cooperation. Also, developing a rational basis for sharing the aggregate payoffs is imperative for the stability of the coalitions. We model such cooperation using the theory of transferable payoff coalitional games. We show that the optimum cooperation strategy, which involves the acquisition, deployment, and allocation of the channels and base stations (to customers), can be computed as the solution of a concave or an integer optimization. We next show that the grand coalition is stable in many different settings, i.e., if all providers cooperate, there is always an operating point that maximizes the providers' aggregate payoff, while offering each a share that removes any incentive to split from the coalition. The optimal cooperation strategy and the stabilizing payoff shares can be obtained in polynomial time by respectively solving the primals and the duals of the above optimizations, using distributed computations and limited exchange of confidential information among the providers. Numerical evaluations reveal that cooperation substantially enhances individual providers' payoffs under the optimal cooperation strategy and several different payoff sharing rules.

Epidemic models based on nonlinear differential equations have been extensively applied in a variety of systems as diverse as infectious outbreaks, marketing, diffusion of beliefs, etc., to the dissemination of messages in MANET or p2p networks. Control of such systems is achieved at the cost of consuming the resources. We construct a unifying framework that models the interactions of the control and the elements in systems with epidemic behavior. Specifically, we consider non-replicative and replicative dissemination of messages in a network: a pre-determined set of disseminators distribute the messages in the former, whereas the disseminator set continually grows in the latter as the nodes that receive the patch become disseminators themselves. In both cases, the desired trade-offs can be attained by activating at any given time only fractions of disseminators and selecting their dissemination rates. We formulate the above trade-offs as optimal control problems that seek to minimize a general aggregate cost function which cogently depends on both the states and the overall resource consumption. We prove that the dynamic control strategies have simple structures: (1) it is never optimal to activate a partial fraction of the disseminators (all or none) (2) when the resource consumption cost is concave, the distribution rate of the activated nodes are bang-bang with at most one jump from the maximum to the minimum value. When the resource consumption cost is convex, the above transition is strict but continuous. We compare the efficacy and robustness of different dispatch models and also those of the optimum dynamic and static controls using numerical computations.

Given the flexibility that software-based operation provides, it is unreasonable to expect that new malware will demonstrate a fixed behavior over time. Instead, malware can dynamically change the parameters of their infective hosts in response to the dynamics of the network, in order to maximize their overall damage. However, in return, the network can also dynamically change its counter-measure parameters in order to attain a robust defense against the spread of malware while minimally affecting the normal performance of the network. The infinite dimension of freedom introduced by variation over time and antagonistic and strategic optimization of malware and network against each other demand new attempts for modeling and analysis. We develop a zero-sum dynamic game model and investigate the structural properties of the saddle-point strategies. We specifically show that saddle-point strategies are simple threshold-based policies and hence, a robust dynamic defense is practicable.

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.

Efficacy of commercial wireless networks can be substantially enhanced through large-scale cooperation among involved entities such as providers and customers. The success of such cooperation is contingent upon the design of judicious resource allocation strategies that ensure that the individuals' payoffs are commensurate to the resources they offer to the coalition. The resource allocation strategies depend on which entities are decision-makers and whether and how they share their aggregate payoffs. Initially, we consider the scenario where the providers are the only decision-makers and they do not share their payoffs. We formulate the resource allocation problem as a nontransferable payoff coalitional game and show that there exists a cooperation strategy that leaves no incentive for any subset of providers to split from the grand coalition, i.e., the core of the game is nonempty. To compute this cooperation strategy and the corresponding payoffs, we subsequently relate this game and its core to an exchange market setting and its equilibrium, which can be computed by several efficient algorithms. Next, we investigate cooperation when customers are also decision-makers and decide which provider to subscribe to based on whether there is cooperation. We formulate a coalitional game in this setting and show that it has a nonempty core. Finally, we extend the formulations and results to the cases where the payoffs are vectors and can be shared selectively.

Malware attacks constitute a serious security risk that threatens to slow down the large scale proliferation of wireless applications. As a first step towards thwarting this security threat, we seek to quantify the maximum damage inflicted on the system owing to such outbreaks and identify the most vicious attacks. We represent the propagation of malware in a battery-constrained mobile wireless network by an epidemic model in which the worm can dynamically control the rate at which it kills the infected node and also the transmission range and/or the media scanning rate. At each moment of time, the worm at each node faces the following trade-offs: (i) using larger transmission range and media scanning rate to accelerate its spread at the cost of exhausting the battery and thereby reducing the overall infection propagation rate in the long run or (ii) killing the node to inflict a large cost on the network, however at the expense of loosing the chance of infecting more susceptible nodes at later times. We mathematically formulate the decision problems and utilize Pontryagin Maximum Principle from optimal control theory to quantify the damage that the malware can inflict on the network by deploying optimum decision rules. Next, we establish structural properties of the optimal strategy of the attacker over time. Specifically, we prove that it is optimal for the attacker to defer killing of the infective nodes in the propagation phase until reaching a certain time and then start the slaughter with maximum effort. We also show that in the optimal attack policy, the battery resources are used according to a decreasing function of time, i.e., mostly during the initial phase of the outbreak. Finally, our numerical investigations reveal a framework for identifying intelligent defense strategies that can limit the damage by appropriately selecting network parameters.

We provide a formal model for the Change Management process for Enterprise IT systems, and develop change scheduling algorithms that seek to attain the "change capacity" of the system. The change management process handles critical updates in the system that often use overlapping sets of servers, resulting in scheduling conflicts between the corresponding change classes. Furthermore, applications are typically associated with certain permissible downtime windows, which impose constraints on the timing of the change executions. Scheduling of changes for such systems represent a complex dynamic optimization question. In a limiting fluid regime, where changes are assumed nonatomic, we develop a scheduling policy that provably attains the change capacity of the system. We then propose and evaluate an atomic approximation of the optimal fluid scheduling policy, which is well suited for application to a real change management system. Simulation results demonstrate that the expected change execution delay and the capacity attained by the approximate policy is close to the best attainable values, when unavoidable capacity losses due to fragmentation effects are taken into account and is significantly better than a randomized scheduling policy.

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.

Reliable security measures against outbreaks of malware is imperative to enable large scale proliferation of wireless technologies. Immunization and healing of the nodes through dissemination of security patches can counter the spread of a malware upon an epidemic outbreak. The distribution of patches however burdens the bandwidth which is scarce in wireless networks. The trade-offs between security risks and resource consumption can be attained by activating at any given time only fractions of dispatchers and dynamically selecting their packet transmission rates. We formulate the above trade-offs as an optimal control problem that seek to minimize the aggregate network costs that depend on security risks and resource consumed by the countermeasures. Using Pontryagin's maximum principle, we prove that the dynamic control strategies have simple structures. When the resource consumption cost is concave, optimal strategy is to use maximum resources for distribution of patches until a threshold time, upon which, the patching should halt. When the resource consumption cost is convex, the above transition is strict but continuous.

A system with ann-dimensional state vector and acontrollerand anactoris considered. The controller has complete information about the system state, and reveals a certain “minimum” amount of information to the actor. The actor takes certain actions based on the information the controller reveals, and the actions fetch certain utilities for each entity. Both the controller and actor seek to maximize their individual utilities by respectively selecting the information to reveal and the actions to adopt. This decision problem forms the basis of several technical and social systems, and can be formulated as a signaling game. It is shown that the Perfect Bayesian Equilibrium of this game has several counterintuitive properties and can be obtained as a saddle point of a different two person zero sum game. The computation time for saddle points using standard linear programs however turns out to be superexponential inn, which leads to computational intractability even for moderaten. Algorithms for computing saddle point policies using a computation time that is exponential innare presented. Finally, simple linear time computable policies that approximate the saddle-point policies within guaranteeable approximation ratios are obtained.

We consider a wireless network consisting of two classes of potentially mobile users: primary users and secondary users. Primary users license frequency channels and transmit in their respective bands as required. Secondary users resort to unlicensed access of channels that are not used by their primary users. Primaries impose access fees on the secondaries which depend on access durations and may be different for different primary channels and different available communication rates in the channels. The available rates to the secondaries change with time depending on the usage status of the primaries and the random access quality of channels. Secondary users seek to minimize their total access cost subject to stabilizing their queues whenever possible. Our first contribution is to present a dynamic link scheduling policy that attains this objective. The computation time of this policy, however, increases exponentially with the size of the network. We next present an approximate scheduling scheme based on graph partitioning that is distributed and attains arbitrary trade-offs between aggregate access cost and computation times of the schedules, irrespective of the size of the network. Our performance guarantees hold for general arrival and primary usage statistics and multihop networks. Each secondary user is, however, primarily interested in minimizing the cost it incurs, rather than in minimizing the aggregate cost. Thus, it will schedule its transmissions so as to minimize the aggregate cost only if it perceives that the aggregate cost is shared among the users as per a fair cost sharing scheme. Using concepts from cooperative game theory, we develop a rational basis for sharing the aggregate cost among secondary sessions and present a cost sharing mechanism that conforms to the above basis.

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.

We consider a network in which several service providers offer wireless access service to their respective subscribed customers through potentially multi-hop routes. If providers cooperate, i.e., pool their resources, such as spectrum and base stations, and agree to serve each others' customers, their aggregate payoffs, and individual shares, can potentially substantially increase through efficient utilization of resources and statistical multiplexing. The potential of such cooperation can however be realized only if each provider intelligently determines who it would cooperate with, when it would cooperate, and how it would share its resources during such cooperation. Also, when the providers share their aggregate revenues, developing a rational basis for such sharing is imperative for the stability of the coalitions. We model such cooperation using transferable payoff coalitional game theory. We first consider the scenario that locations of the base stations and the channels that each provider can use have already been decided apriori. We show that the optimum cooperation strategy, which involves the allocations of the channels and the base stations to mobile customers, can be obtained as solutions of convex optimizations. We next show that the grand coalition is stable in this case, i.e. if all providers cooperate, there is always an operating point that maximizes the providers' aggregate payoff, while offering each such a share that removes any incentive to split from the coalition. Next, we show that when the providers can choose the locations of their base stations and decide which channels to acquire, the above results hold in important special cases. Finally, we examine cooperation when providers do not share their payoffs, but still share their resources so as to enhance individual payoffs. We show that the grand coalition continues to be stable.

We consider the question of obtaining tight delay guarantees for throughout-optimal link scheduling in arbitrary topology wireless ad-hoc networks. We consider two classes of scheduling policies: 1) a maximum queue-length weighted independent set scheduling policy, and 2) a randomized independent set scheduling policy where the independent set scheduling probabilities are selected optimally. Both policies stabilize all queues for any set of feasible packet arrival rates, and are therefore throughput-optimal. For these policies and i.i.d. packet arrivals, we show that the average packet delay is bounded by a constant that depends on the chromatic number of the interference graph, and the overall load on the network. We also prove that this upper bound is asymptotically tight in the sense that there exist classes of topologies where the expected delay attained by any scheduling policy is lower bounded by the same constant. Through simulations we examine the scaling of the average packet delay with respect to the overall load on the network, and the chromatic number of the link interference graph.

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.

A decision maker (Actor) has to decide which of several available resources to use in the presence of an adversary (Controller) that can prevent the Actor of receiving information on the state of some of the resources. The Controller has a limitation on the amount of information it can conceal. We formulate this problem as a game and compute the most harmful behavior of the Controller and the best choice of a resource for the Actor. We identify cases in which the exact solution is computationally intractable, and provide approximate solutions with polynomial complexity.

The question of providing throughput guarantees through distributed scheduling, which has remained an open problem for some time, is addressed in this paper. It is shown that a simple distributed scheduling strategy, maximal scheduling, attains a guaranteed fraction of the maximum throughput region in arbitrary wireless networks. The guaranteed fraction depends on the ldquointerference degreerdquo of the network, which is the maximum number of transmitter-receiver pairs that interfere with any given transmitter-receiver pair in the network and do not interfere with each other. Depending on the nature of communication, the transmission powers and the propagation models, the guaranteed fraction can be lower-bounded by the maximum link degrees in the underlying topology, or even by constants that are independent of the topology. The guarantees are tight in that they cannot be improved any further with maximal scheduling. The results can be generalized to end-to-end multihop sessions. Finally, enhancements to maximal scheduling that can guarantee fairness of rate allocation among different sessions, are discussed.

We consider the problem of uplink/downlink scheduling in a multichannel wireless access point network where channel states differ across channels as well as users, vary with time, and can be measured only infrequently. We demonstrate that, unlike infrequent measurement of queue lengths, infrequent measurement of channel states reduce the maximum attainable throughput. We then prove that in frequency division multiplexed systems, a dynamic scheduling policy that depends on both the channel rates (averaged over the measurement interval) and the queue lengths, is throughput optimal. We also generalize the scheduling policy to solve the joint power allocation and scheduling problem. In addition, we provide simulation studies that demonstrate the impact of the frequency of channel and queue state measurements on the average delay and attained throughput.

We consider the problem of uplink/downlink scheduling in a multichannel wireless access point network where channel states differ across channels as well as users, vary with time, and can be measured only infrequently. We demonstrate that, unlike the infrequent measurement of queue lengths, infrequent measurement of channel states reduce the maximum attainable throughput. We then prove in frequency division multiplexing systems, a dynamic scheduling policy that depends on both the channel rates (averaged over the measurement interval) and the queue lengths, attains the maximum possible throughput. We also generalize the scheduling policy to solve the joint power allocation and scheduling problem in orthogonal frequency division multiplexing systems. In addition, we provide simulation studies that demonstrate the impact of the frequency of channel and queue state measurements on the average delay and attained throughput.

Several power-aware routing schemes have been developed for wireless networks under the assumption that nodes are willing to sacrifice their power reserves in the interest of the network as a whole. But, in several applications of practical utility, nodes are organized in groups, and as a result, a node is willing to sacrifice in the interest of other nodes in its group but not necessarily for nodes outside its group. Such groups arise naturally as sets of nodes associated with a single owner or task. We consider the premise that groups will share resources with other groups only if each group experiences a reduction in power consumption. Then, the groups may form a coalition in which they route each other's packets. We demonstrate that sharing between groups has different properties from sharing between individuals and investigate fair, mutually beneficial sharing between groups. In particular, we propose a Pareto-efficient condition for group sharing based on max-min fairness called fair coalition routing. We propose distributed algorithms for computing the fair coalition routing. Using these algorithms, we demonstrate that fair coalition routing allows different groups to mutually beneficially share their resources

We consider a class of queueing referred to as generalized constrained queueing networks which form the basis of several different communication and informa- tion systems. These consist of a collection of queues such that only certain sets of queues can be concurrently served. When- ever a queue is served, the system receives a certain reward. Dif- ferent rewards are obtained for serving different queues, and fur- thermore, the reward obtained for serving a queue depends on the set of concurrently served queues. We demonstrate that the depen- dence of the rewards on the schedules alter fundamental relations between performance metrics like throughput and stability. Specif- ically, maximizing the throughput is no longer equivalent to max- imizing the stability region; we therefore need to maximize one subject to certain constraints on the other. Since stability is crit- ical for bounding packet delays and buffer overflow, we focus on maximizing the throughput subject to stabilizing the system. We design provably optimal scheduling strategies that attain this goal by scheduling the queues for service based on the queue lengths and the rewards provided by different selections. The proposed scheduling strategies are however computationally complex. We subsequently develop techniques to reduce the complexity and yet attain the same throughput and stability region. We demonstrate that our framework is general enough to accommodate random re- wards and random scheduling constraints.

We focus on detecting intrusions in ad hoc networks using the misuse detection technique. We allow for detection modules that periodically fail to detect attacks and also generate false positives. Combining theories of hypothesis testing and approximation algorithms, we develop a framework to counter different threats while minimizing the resource consumption. We obtain computationally simple optimal rules for aggregating and thereby minimizing the errors in the decisions of the nodes executing the intrusion detection software (IDS) modules. But, we show that the selection of the optimal set of nodes for executing the IDS is an NP-hard problem. We describe a polynomial complexity, distributed selection algorithm, "Maximum Unsatisfied Neighbors in Extended Neighborhood" (MUNEN) that attains the best possible approximation ratio. The aggregation rules and MUNEN can be executed by mobile nodes with limited processing power. The overall framework provides a good balance between complexity and performance for attaining robust intrusion detection in ad hoc networks.

The analysis and design of wireless MAC protocols, coding schemes and transmission algorithms can significantly benefit from an understanding of the channel quality variation. We attempt to represent channel quality variation using a finite state birth-death Markov model. We outline a method to compute the parameters of the model based on measured traces obtained using common wireless chipsets. Using this Markov chain, we evaluate the performance statistically based on the channel quality, long term correlations and burst length distributions. Such a model performs significantly better than a traditional two-state Markov chain in characterizing 802.11 networks while maintaining the simplicity of a birth-death model. We interpret the variation of the model parameters across different locations and different times. A finite state stationary model is amenable to analysis and can substantially benefit the design of efficient algorithms and make simulations for wireless network protocols faster

We investigate the fairness and throughput properties of a simple distributed scheduling policy, maximal scheduling, in the context of a general ad-hoc wireless network. We design a fully distributed algorithm that combines a token generation scheme with maximal scheduling policy so as to attain max-min fair rates within the feasible region of maximal scheduling. We next present throughput guarantees of maximal scheduling that quantify the performance loss of each session due to the use of local information based scheduling. We show that the performance loss for each session depends on the maximum “interference degree” in its neighborhood. We also demonstrate that the performance penalties can not be localized any further.

We consider ad hoc networks with multiple, mobile intruders. We investigate the placement of the intrusion detection modules for misuse-based detection strategy. Our goal is to maximize the detection rate subject to limited availability of communication and computational resources. We mathematically formulate this problem, and show that computing the optimal solution is NP-hard. Thereafter, we propose two approximation algorithms that approximate the optimal solution within a constant factor, and prove that they attain the best possible approximation ratios. The approximation algorithms though require recomputation every time the topology changes. Thereafter, we modify these algorithms to adapt seamlessly to topological changes. We obtain analytical expressions to quantify the resource consumption versus detection rate tradeoffs for different algorithms. Using analysis and simulation, we evaluate these algorithms, and identify the appropriate algorithms for different detection rate and resource consumption tradeoffs.

We focus on detecting intrusions in ad hoc networks using the misuse detection technique. We allow for detection modules that periodically stop functioning due to operational failure or compromise by intruders. Combining theories of stochastic coverage processes and approximation algorithms, we develop a framework to counter failure of detection modules, while minimizing the resource consumption. We show that the selection of the optimal set of nodes for executing the detection modules is an NP-hard problem. We present a distributed polynomial complexity selection algorithm that attains the best possible approximation ratio. We next consider a simple heuristic selection strategy that allows for seamless operation in time varying topologies. We obtain analytical expressions to quantify the tradeoffs between the resource consumption and detection rates attained by these algorithms. Using analysis and simulation, we identify the appropriate algorithms for different failure rates, resource limitation, and required detection rates.

The goal of this correspondence is to minimize delay in real-time multiple-access channel (MAC) layer multicast by exploiting the broadcast nature of wireless medium and limited loss tolerance of the applications. Multiple transmissions of a packet at the MAC layer significantly reduces the delay than that when only one transmission is allowed. But each additional transmission consumes additional power and increases network load. Therefore, the goal is to design a policy that judiciously uses the limited transmission opportunities so as to deliver each packet in the minimum possible time to the required number of group members. The problem is an instance of the stochastic shortest path problem, and using this formulation computationally simple, closed-form transmission strategies have been obtained in important special cases

Many real-time applications require one to many (multicast) communication. Real time applications can gracefully accommodate some loss but require low delay. We minimize the delay in real-time MAC layer multicast by exploiting the broadcast nature of wireless medium and limited loss tolerance of the applications. We show that multiple transmissions of a packet at the MAC layer significantly reduces the delay than that when only one transmission is allowed. But each additional transmission consumes additional power and increases network load. Therefore, our goal is to design a policy that judiciously uses the limited transmission opportunities so as to deliver each packet in minimum possible time to the required number of group members. We show that the problem is an instance of the stochastic shortest path problem, and using this formulation obtain a computationally simple, closed form transmission strategy in important special cases. Numerical computations show that only a small number of transmissions, if used judiciously, are sufficient to minimize the delay subject to loss constraint.

We investigate from an algorithmic perspective the maxmin fair allocation of bandwidth in wireless ad hoc networks. We formalize the maxmin fair objective under wireless scheduling constraints, and present a necessary and sufficient condition for maxmin fairness of a bandwidth allocation. We propose an algorithm that assigns weights to the sessions dynamically such that the weights depend on the congestion in the neighborhood, and schedules the sessions that constitute a maximum weighted matching. We prove that this algorithm attains the maxmin fair rates, even though it does not use any information about the statistics of the packet arrival process.

We investigate issues that Bluetooth may face in evolving from a simple wire replacement to a large-scale ad hoc networking technology. We do so by examining the efficacy of Bluetooth in establishing a connected topology, which is a basic requirement of any networking technology. We demonstrate that Bluetooth experiences some fundamental algorithmic challenges in accomplishing this seemingly simple task. Specifically, deciding whether there exists at least one connected topology that satisfies the Bluetooth constraints is NP-hard. Several implementation problems also arise due to the internal structure of the Bluetooth protocol stack. All these together degrade the performance of the network, or increase the complexity of operation. Given the availability of efficient substitute technologies, Bluetooth's use may end up being limited to small ad hoc networks.

We design transmission strategies for medium access control (MAC) layer multicast that maximize the utilization of available bandwidth. Bandwidth efficiency of wireless multicast can be improved substantially by exploiting the feature that a single transmission can be intercepted by several receivers at the MAC layer. The multicast nature of transmissions, however, changes the fundamental relations between the quality of service (QoS) parameters, throughput, stability, and loss, e.g., a strategy that maximizes the throughput does not necessarily maximize the stability region or minimize the packet loss. We explore the tradeoffs among the QoS parameters, and provide optimal transmission strategies that maximize the throughput subject to stability and loss constraints. The numerical performance evaluations demonstrate that the optimal strategies significantly outperform the existing approaches.

We study the fair allocation of bandwidth in multicast networks with multirate capabilities. In multirate transmission, each source encodes its signal in layers. The lowest layer contains the most important information and all receivers of a session should receive it. If a receiver's data path has additional bandwidth, it receives higher layers which leads to a better quality of reception. The bandwidth allocation objective is to distribute the layers fairly. We present a computationally simple, decentralized scheduling policy that attains the maxmin fair rates without using any knowledge of traffic statistics and layer bandwidths. This policy learns the congestion level from the queue lengths at the nodes, and adapts the packet transmissions accordingly. When the network is congested, packets are dropped from the higher layers; therefore, the more important lower layers suffer negligible packet loss. We present analytical and simulation results that guarantee the maxmin fairness of the resulting rate allocation, and upper bound the packet loss rates for different layers.

We study fairness of resource allocation in multirate, multicast networks. In multirate networks, different receivers of the same multicast session can receive service at different rates. We develop a mathematical framework to model the maxmin fair allocation of bandwidth with minimum and maximum rate constraints. We present a necessary and sufficient condition for a rate allocation to be maxmin fair in a multirate, multicast network. We propose a distributed algorithm for computing the maxmin fair rates allocated to various source-destination pairs. This algorithm has a low message exchange overhead, and is guaranteed to converge to the maxmin fair rates in finite time.

Sensor networks have increasingly become the subject of intense scientific interest over the past few years. In this work, we focus on intrusion detection in sensor networks. The intrusion detection community has been focusing mainly on wired networks. But techniques geared towards wire line networks would not suffice for a sensor environment because of the constraints associated with such networks. In this paper, we consider the arbitrary sized sensor networks and propose algorithms to improve the detection rates by intelligently enabling the intrusion detection functionality on particular sensor nodes. The proposed algorithms, based on the concepts of minimum cut-set and minimum dominating set, allow for a distributed implementation. The performance of the algorithms in identifying intrusions using signature based detection techniques is studied via simulations.

Bandwidth efficiency of wireless multicast can be improved substantially by exploiting the fact that several receivers can be reached at the MAC layer by a single transmission. The multicast nature of the transmissions, however, introduces several design.

We consider ad hoc networks with multiple, mobile colluding intruders. We investigate the placement of the intrusion detection modules for misuse intrusion detection. Our goal is to maximize the detection performance subject to limitation in the computational resources. We mathematically formulate different detection objectives, and show that computing the optimal solution is NP-hard in each case. Thereafter, we propose a family of algorithms that approximate the optimal solution, and prove that some of these algorithms have guaranteeable approximation ratios. The algorithms that have analytically guaranteeable performance require re-computation every time the topology changes due to mobility. We next modify the computation strategy so as to seamlessly adapt to topological changes due to mobility. Using simulation we evaluate these algorithms, and identify the appropriate algorithms for different detection performance and resource consumption tradeoffs.

We study fairness in allocating bandwidth for loss-tolerant real-time multicast applications. We assume that the traffic is encoded in several layers so that the network can adapt to the available bandwidth and receiver processing capabilities by varying the number of layers delivered. We consider the case where receivers cannot subscribe to fractional layers. Therefore, the network can allocate only a discrete set of bandwidth to a receiver, whereas a continuous set of rates can be allocated when receivers can subscribe to fractional layers. Fairness issues differ vastly in these two different cases. Computation of lexicographic optimal rate allocation becomes NP-hard in this case, while lexicographic optimal rate allocation is polynomial complexity computable when fractional layers can be allocated. Furthermore, maxmin fair rate vector may not exist in this case. We introduce a new notion of fairness, maximal fairness. Even though maximal fairness is a weaker notion of fairness, it has many intuitively appealing fairness properties. For example, it coincides with lexicographic optimally and maxmin fairness, when maxmin fair rate allocation exists. We propose a polynomial complexity algorithm for computation of maximally fair rates allocated to various source-destination pairs, which incidentally computes the maxmin fair rate allocation, when the latter exists.

The goal of this paper is to design optimal scheduling and memory management so as to minimize packet loss in input queued switches with finite input buffers. The contribution is to obtain closed-form optimal strategies that minimize packet loss in 2/spl times/2 switches with equal arrival rates for all streams. For arbitrary arrival rates, the contribution is to identify certain characteristics of the optimal strategy, and use these characteristics to design a near-optimal heuristic. A lower bound for the cost associated with packet loss for N/spl times/N switches is obtained. This lower bound is used to design a heuristic which attains near-minimum packet loss in N/spl times/N switches with arbitrary N. These policies reduce packet loss by about 25% as compared to the optimal strategy for the infinite buffer case. The framework and the policies proposed here apply to buffer-constrained wireless networks as well.

This paper addresses scheduling and memory management in input queued switches with finite input buffers, with the objective of minimizing packet loss. The framework and algorithms proposed here apply to buffer constrained wireless networks as well. The scheduling problem has been extensively addressed under the assumption of infinite input buffers. We study the finite buffer case here which arises in practice. The introduction of memory constraint significantly complicates the problem. The optimal strategies for infinite buffer case no longer apply and become strictly suboptimal in presence of memory limitations. We present closed form optimal strategies which minimize packet loss in 2 × 2 switches with equal arrival rates for all streams. We identify certain characteristics of the optimal strategy for arbitrary arrival rates, and use these properties to design a near optimal heuristic. We use the insight obtained from the investigation for 2 × 2 switches to propose a heuristic for N × N switches, arbitrary N and show numerically that this strategy performs close to optimal. The policies presented here reduce packet loss by about 25% as compared to the optimal strategy for the infinite buffer case.

The focus of this paper is to extend the lifetime of a battery powered node in wireless context. The lifetime of a battery depends on both the manner of discharge and the transmission power requirements. We present a framework for computing the optimal discharge strategy which maximizes the lifetime of a node by exploiting the battery characteristics and adapting to the varying power requirements for wireless operations. The complexity of the optimal computation is linear in the number of system states. However, since the number of states can be large, the optimal strategy can only be computed offline and executed via a table lookup. We present a simple discharge strategy which can be executed online without any table lookup and attains near maximum lifetime.

The focus of this paper is to extend the lifetime of a battery powered node in wireless context. The lifetime of a battery depends on both the manner of discharge and the transmission power requirements. We present a framework for computing the optimal discharge strategy which maximizes the lifetime of a node by exploiting the battery characteristics and adapting to the varying power requirements for wireless operations. The complexity of the optimal computation is linear in the number of system states. However, since the number of states can be large, the optimal strategy can only be computed offline and executed via a table-lookup. We also present a simple discharge strategy which can be executed online without any table lookup, and attains near maximum battery lifetime. Finally, we use state space reduction techniques to approximate the optimal computation in significantly lower complexity.

We consider scheduling policies for maxmin fair allocation of bandwidth in wireless ad hoc networks. We formalize the maxmin fair objective under wireless scheduling constraints. We propose a fair scheduling which assigns dynamic weights to the flows such that the weights depend on the congestion in the neighborhood and schedule the flows which constitute a maximum weighted matching. It is possible to prove analytically that this policy attains both short term and long term fairness. We consider more generalized fairness notions, and suggest mechanisms to attain these objectives.

In multirate multicasting, different users (receivers) within the same multicast group can receive service at different rates, depending on the user requirements and the network congestion level. Compared with unirate multicasting, this provides more flexibility to the user and allows more efficient usage of the network resources. We address the rate control problem for multirate multicast sessions, with the objective of maximizing the total receiver utility. This aggregate utility maximization problem not only takes into account the heterogeneity in user requirements, but also provides a unified framework for diverse fairness objectives. We propose an algorithm for this problem and show, through analysis and simulation, that it converges to the optimal rates. In spite of the nonseparability of the problem, the solution that we develop is completely decentralized, scalable and does not require the network to know the receiver utilities. The algorithm requires very simple computations both for the user and the network, and also has a very low overhead of network congestion feedback.

Channel allocation algorithms for channelized cellular systems are discussed from a new perspective, viz., fairness of allocation. The concepts of relative and absolute fairness are introduced and discussed. It is shown that under certain reasonable assumptions, there exists an absolute (max-min) fair carried traffic intensity vector (a vector describing the traffic carried in the cells of the system). We also show that this vector is unique. We describe some properties of the max-min fair carried traffic intensity vector in an asymptotic limit where the traffic and the number of channels are scaled together. For each traffic pattern, we determine a fixed channel allocation which attains this max-min fair carried traffic intensity vector independent of the value of the offered traffic, in the same asymptotic limit. Finally, we discuss a tradeoff between being max-min fair and trying to maximize revenue. We conclude by discussing some possible extensions of our work.

We propose a new multicast routing and scheduling algorithm called multipurpose multicast routing and scheduling algorithm (MMRS). The routing policy load balances among various possible routes between the source and the destinations, basing its decisions on the message queue lengths at the source node. The scheduling is such that the flow of a session depends on the congestion of the next hop links. MMRS is throughput optimal. In addition, it has several other attractive features. It is computationally simple and can be implemented in a distributed, asynchronous manner. It has several parameters which can be suitably modified to control the end-to-end delay and packet loss in a topology-specific manner. These parameters can be adjusted to offer limited priorities to some desired sessions. MMRS is expected to play a significant role in end-to-end congestion control in the multicast scenario.

Multirate multicasting, where the receivers of a multicast group can receive service at different rates, is an efficient mode of data delivery for many real-time applications. We address the problem of achieving rates that maximize the total receiver utility for multirate multicast sessions. This problem not only takes into account the heterogeneity in user requirements, but also provides a unified framework for diverse fairness objectives. We propose two algorithms and prove that they converge to the optimal rates for this problem. The algorithms are distributed and scalable, and do not require the network to know the receiver utilities. We discuss how these algorithms can be implemented in a real network, and also demonstrate their convergence through simulation experiments.

We consider the rate control problem with the objective of maximizing the total user utility. It takes into account the possible differences in user requirements, and also provides a framework for achieving a wide range of fairness objectives. We propose a simple algorithm for achieving the optimal rates for this problem. The algorithm can be implemented in a distributed way and does not require the network to know the user utility functions. In our algorithm, the network communicates to the user the number of congested links on the user's path, and the user (end-host) adjusts its rate accordingly, taking into account its utility function and the network congestion feedback. We show through analysis and experimentation that our algorithm converges to the optimum rates.

We study fair allocation of resources in multicast networks with multirate capabilities. In multirate transmission, the session source hierarchically encodes its signal and the receivers subscribe to the appropriate number of layers. The objective of the network is to distribute the layers fairly. This can be attained either by computing the fair rates first, and then using a scheduling policy to attain the fair rates, or by using a scheduling policy which allocates the fair rates without computing them explicitly. The first requires knowledge of system parameters like link bandwidth, which are not generally known to the link schedulers. The second approach is more realistic. We present a scheduling policy which allocates the fair rates without computing them beforehand. We have presented analytical and experimental results demonstrating the fairness of the resulting rate allocation. In addition to guaranteeing the fair rates, this policy confines the packet losses to enhancement layers, and protects the more important base layers, when there is shortage of bandwidth. Furthermore, this policy does not require any knowledge of traffic statistics, is computationally simple, and is essentially local information based.

We study fairness in arbitrary networks with multicast capabilities. Multicast traffic in Internet and ATM provides a motivation for studying these networks. A study of fairness in multicast networks poses several interesting problems, e.g., the issue of inter-session fairness in addition to that of inter-session fairness in unicast networks. We develop a mathematical framework to model the fair allocation of bandwidth in multirate multicast networks with minimum and maximum rate constraints. We present distributed algorithms for computation of maxmin fair rates allocated to various source-destination pairs.

We study fairness when receivers in a multicast network can not subscribe to fractional layers. This case arises when the source hierarchically encodes its signal and the hierarchical structure is predetermined. Unlike the case of the fractional layer allocation, which has been studied extensively in (Sarkar and Tassiulas, 1999), bandwidth can be allocated in discrete chunks only. Fairness issues become vastly different. Computation of lexicographic optimal rate allocation becomes NP-hard in this case, while lexicographic optimal rate allocation is polynomial complexity computable when fractional layers can be allocated. Furthermore, the maxmin fair rate vector may not exist in this case. We introduce a new notion of fairness, maximal fairness. We propose a polynomial complexity algorithm for computation of maximally fair rates allocated to various source-destination pairs. Even though maximal fairness is a weaker notion of fairness, it coincides with lexicographic optimality and maxmin fairness, when maxmin fair rate allocation exists. So the algorithm for computing maximally fair rate allocation computes maxmin fair rate allocation, when the latter exists.

We propose a new multicast routing and scheduling algorithm called multipurpose multicast routing and scheduling algorithm (MMRS). The routing policy load balances amongst various possible routes between the source and the destinations, basing its decisions on the message queue lengths at the source node. The scheduling amongst various sessions sharing links is devised such that the flow of a session depends on the congestion of the next hop links. MMRS is throughput optimal and computationally simple. It can be implemented in a distributed, asynchronous manner. It has several parameters which can be suitably modified to control the end to end delay, packet loss in a topology specific manner. These parameters can be adjusted to offer limited priorities to some desired sessions. MMRS is expected to play a significant role in end to end congestion control in the multicast scenario.

Improved channel assignment algorithms for cellular networks were designed by modelling the interference constraints in terms of a hypergraph (Sarkar and Sivarajan). However these algorithms only considered cochannel reuse constraints. Receiver filter responses impose restrictions on simultaneous adjacent channel usage in the same cell or in neighbouring cells. An asymptotically tight upper bound for the traffic carried by the system in the presence of arbitrary cochannel and adjacent channel reuse constraints was developed in Deora (1995). However this bound is computationally intractable even for small systems like a regular hexagonal cellular system of 19 cells. We have obtained approximations to this bound using the optimal solutions for cochannel reuse constraints only, and a further graph theoretic approach. Our approximations are computationally much more efficient and have turned out to track very closely the exact performance bounds in most cases of interest. We also present some heuristics for designing fixed channel assignment algorithms with a minimum number of channels satisfying both cochannel and adjacent channel reuse constraints.