We propose a geographic content placement policy for wireless caching networks. This policy, named Joint Caching Policy (JCP), jointly determines the caching strategy across the set of base stations (BSs) to improve the hit probability of an arbitrarily located user in the network versus caching policies where placement is independent and identically distributed across the BSs. To that end, JCP divides the BSs into groups, and executes a joint caching policy for each group, while content placement is independent across the groups. Existing joint caching policies require knowledge of user location to optimize content placement. On the other hand, JCP does not require any information on user location, and it provides a content placement policy that outperforms the one given by Independent Caching Policy (ICP), proposed by Błaszczyszyn and Giovanidis in 2015, under any user location distribution. We prove that the hit probability under JCP is lower bounded by that of ICP. We further propose an extension of JCP, named JCP-OPT, which improves the hit probability over JCP by solving a concave maximization problem, provided that there is side information about the user locations. We validate the performance of JCP and JCP-OPT via numerical evaluations and demonstrate that they can provide up to a 30% gain in hit probability over ICP.

This paper presents the design and performance evaluation of a new machine learning-based transport protocol called Reinforcement learning-based retransmission Control Protocol (RCP). Unlike prior transport protocols that aim at either providing guaranteed end-to-end delivery, e.g., TCP, or minimizing the end-to-end delay, e.g., UDP, RCP aims to optimize any achievable combination of these objectives, as specified by an application layer utility function. The utility function in this paper can be quite general, and can capture a combination of delay and packet delivery metrics. RCP can be thought of as an intelligent middle-ground between UDP and TCP, that maps application layer objectives subject to what is learned about the network state. It is window-based like TCP, but retransmissions are decided based on a reinforcement learning algorithm to maximize the application layer utility function. RCP employs a reinforcement learning method, double Q-Learning network, to learn the best strategy in real-time from a history of packet transmission/re-transmission experiences. No assumption on the shape of the utility function is needed. RCP is evaluated under a wide range of network settings, and is found to outperform UDP, TCP, and ARQ for almost all settings. The performance is also evaluated with respect to TCP-friendliness and network stability.

We consider the problem of partitioning a spectrum band into$M$channels of equal bandwidth, and then further assigning these$M$channels into$P$licensed channels and$M-P$unlicensed channels. Licensed channels can be accessed both for licensed and opportunistic use following a tiered structure that has a higher priority for licensed use. Unlicensed channels can be accessed only for opportunistic use. We address the following question in this paper. Given a market setup, what values of$M$and$P$maximize the net spectrum utilization of the spectrum band? While this problem is fundamental, it is highly relevant practically, e.g., in the context of partitioning the recently proposed Citizens Broadband Radio Service band. If$M$is too high or too low, it may decrease spectrum utilization due to limited channel capacity or due to wastage of channel capacity, respectively. If$P$is too high (low), it will not incentivize the wireless operators who are primarily interested in unlicensed channels (licensed channels) to join the market. These tradeoffs are captured in our optimization problem which manifests itself as a two-stage Stackelberg game. We design an algorithm to solve the Stackelberg game and hence find the optimal$M$and$P$. The algorithm design also involves an efficient Monte Carlo integrator to evaluate the expected value of the involved random variables like spectrum utilization and operators’ revenue. We also benchmark our algorithms using numerical simulations.

This paper addresses the following question which is of interest in designing efficient exclusive-use spectrum licenses sold through spectrum auctions. Given a system model in which customer demand, revenue, and bids of wireless operators are characterized by stochastic processes and an operator is interested in joining the market only if its expected revenue is above a threshold and the lease duration is below a threshold, what is the optimal lease duration which maximizes the net customer demand served by the wireless operators? Increasing or decreasing lease duration has many competing effects; while shorter lease duration may increase the efficiency of spectrum allocation, longer lease duration may increase market competition by incentivizing more operators to enter the market. We formulate this problem as a two-stage Stackelberg game consisting of the regulator and the wireless operators and design efficient algorithms to find the Stackelberg equilibrium of the entire game. These algorithms can also be used to find the Stackelberg equilibrium under some generalizations of our model. Using these algorithms, we obtain important numerical results and insights that characterize how the optimal lease duration varies with respect to market parameters in order to maximize the spectrum utilization. A few of our numerical results are non-intuitive as they suggest that increasing market competition may not necessarily improve spectrum utilization. To the best of our knowledge, this paper presents the first mathematical approach to optimize the lease duration of spectrum licenses.

Coded caching, introduced by Maddah-Ali and Niesen, jointly designs content placement and delivery policies that achieve order-optimal transmission rate. We first prove that the coded caching scheme cannot protect the anonymity of network users when an eavesdropper in the network has access to the broadcast channel. Then, a three-stage attack is proposed to estimate users file requests by building an X-D table mapping between server transmissions X and users requests D. For a coded caching network having N files and K users, there are NKdifferent demand vectors. We show that the approximate average time complexity of the proposed attack is only a factor of two from the total number of possible demand vectors, while the best case (for the eavesdropper) time complexity is in the order of only NK. Once the X-D table is completely deduced by the eavesdropper, the users seize from having any privacy. Numerical simulations demonstrate that the analytical results for the time complexity of the attack match well with the simulation results.

Control of conventional transportation networks aims at bringing the state of the network (e.g., the traffic flows in the network) to the system optimal (SO) state. This optimum is characterized by the minimality of the social cost function, i.e., the total cost of travel (e.g., travel time) of all drivers. On the other hand, drivers are assumed to be rational and selfish, and make their travel decisions (e.g., route choices) to optimize their own travel costs, bringing the state of the network to a user equilibrium (UE). A classic approach to influence users' route choice is using congestion tolls. In this paper, we study the SO and UE of future connected vehicular transportation networks, where users consider both the travel cost and the utility from data communication, when making their travel decisions. We leverage the data communication aspect of the decision making to influence the user route choices, driving the UE state to the SO state. We assume the cache-enabled vehicles can communicate with other vehicles via vehicle-to-vehicle (V2V) connections. We propose an algorithm for calculating the values of the data communication utility that drive the UE to the SO. This result provides a guideline on how the system operator can adjust the parameters of the communication network (e.g., data pricing and bandwidth) to achieve the optimal social cost. We discuss the insights that the results shed on a secondary optimization that the operator can conduct to maximize its own utility without deviating the transportation network state from the SO. We validate the proposed communication model via Veins simulation. The simulation results also show that the system cost can be lowered even if the bandwidth allocation does not exactly match the optimal allocation policy under 802.11p protocol.

This work studies the user equilibrium (UE) state and the system optimal (SO) state in vehicular communication networks that support both V2V and V2I communication. Each user in this network is assumed to make route choice that optimizes a utility function that involves the traditional travel cost and the data communication utility. The overall social cost is minimized when the network is in the SO state. However, the rational and selfish user behavior brings the network to the UE state. It is well known that, in general, the UE state does not necessarily coincide with the SO state. In this paper, we leverage the data communication aspect of the decision making to influence the users' route choices, driving the UE state to the SO state. We provide a guideline for the system operator on how to drive the network towards the SO state using the V2I bandwidth allocation scheme developed in the paper. The model and the proposed algorithm are validated using Veins simulation under IEEE 802.11p protocol. In the simulation, we also show that the system cost can be lowered compared with the UE state if the bandwidth allocation is close to the optimal solution under the proposed algorithm.

We consider the problem of proactive retention aware caching in a heterogeneous wireless edge network consisting of mobile users accessing content from a server and associated to one or more edge caches. Our goal is to design a caching policy that minimizes the sum of content storage costs and server access costs over two design variables: the retention time of each cached content and the probability that a user routes content requests to each of its associated caches. We develop a model that captures multiple aspects such as cache storage costs and several capabilities of modern wireless technologies, such as server multicast/unicast transmissions, device multi-path routing, and cache access constraints. We formulate the problem of Proactive Retention Routing Optimization as a non-convex, non-linear mixed-integer program. We prove that it is NP-hard under both multicast/unicast modes-even when the caches have a large capacity and storage costs are linear-and develop greedy algorithms that have provable performance bounds for the case of uncapacitated caches. Finally, we propose heuristics with low computational complexity for the capacitated cache case as well as for the case of convex storage costs. Systematic evaluations based on real-world data demonstrate the effectiveness of our approach, compared to the existing caching schemes.

The three-tier spectrum sharing framework (3-TSF) is a spectrum sharing model adopted by the Federal Communications Commission. According to this model, under-utilized federal spectrum like the Citizens Broadband Radio Service band is released for shared use where the highest preference is given to Tier-1 followed by Tier-2 (T2) and then Tier-3 (T3). In this paper, we study how a wireless operator, who is interested in maximizing its profit, can strategically operate as a T2 and/or a T3 user. T2 is characterized by paid but ”almost” guaranteed and interference-free channel access while T3 access is free but has the lesser guarantee and also faces channel interference. So the operator has to optimally decide between paid but better channel quality and free but uncertain channel quality. Also, the operator has to make these decisions without knowing future market variables like customer demand or channel availability. The main contribution of this paper is a deterministic online algorithm for leasing channels that has finite competitive ratio, low time complexity, and that does not rely on the knowledge of market statistics. Such algorithms are desirable in the early stages of the deployment of 3-TSF because the knowledge of market statistics may be rather inaccurate. We use tools from the ski-rental literature to design the online algorithm. The online optimization problem for leasing channels is a novel generalization of the ski-rental problem. We, therefore, make fundamental contributions to the ski-rental literature, the applications of which extend beyond this paper. We also conduct simulations using synthetic traces to compare our online algorithm with the benchmark and state-of-the-art algorithms.

Cooperative content delivery using multiple air interfaces (CCDMI) is a powerful solution to mitigate congestion in cellular networks. In CCDMI, the operator distributes content to selected users that further distribute it locally among its nearby users. However, a user that is capable of contributing to CCDMI might act selfishly and refuse to participate. Although the operator can encourage user participation by offering incentives, it has incomplete information about the users' willingness to participate. In order to overcome this problem of adverse selection in CCDMI, we propose two contract-based methods under information asymmetry. In both methods, the operator designs a performance-based contract set for the users that are capable of local content distribution. Using a mathematical analysis, we show that the optimal contract under information asymmetry achieves close to optimal utility for the users and the operator, compared with the information symmetry case. Moreover, the users with high willingness to participate get positive utility and the users with low willingness get zero utility. Hence, by assigning contracts, the operator can motivate user participation, despite the information asymmetry between them. Our results verify that the proposed methods improve the system performance in terms of the utility of the operator and the users.

We consider the problem of proactive (i.e. predictive) content caching that is aware of the costs of retention of the content in the cache. Prior work on caching (whether proactive or reactive) does not explicitly take into account the storage cost due to the duration of time for which a content is cached. This new problem, which we call retention aware caching, is motivated by two recent technological developments that are described in the paper: cloud storage rental costs and flash memory damage. We consider a hierarchical network consisting of a server connected to a number of cache-enabled nodes, located either at the edge of a network (e.g. base stations) or in the core of a data center. There are two types of network costs: storage cost at the caches and download cost from the server. We formulate the problem of proactive retention aware data caching (PRAC), which minimizes the total cost subject to the node capacity constraints. We first prove that PRAC is NP-Hard in general and then analyze PRAC for two cases: (1) linear storage cost, (2) convex storage cost. We show that PRAC admits efficient polynomial time algorithms when the storage cost is linear in retention times and caches have a large capacity. Furthermore, we derive bounds on the performance of PRAC for the case when the storage cost is a practically motivated convex function. Numerical evaluations demonstrate that PRAC outperforms other state-of-the-art caching policies for a wide range of parameters of interest.

We consider the problem of proactive retention aware caching in a heterogeneous wireless edge network consisting of mobile users connected to a server and associated to one or more edge caches. Our goal is to design a caching policy that minimizes the sum of content storage costs and server access transmissions costs over two design variables: the retention time of each cached content and the probability that a user routes content requests to its associated caches. We develop a model that captures multiple aspects such as cache storage costs and several capabilities of modern wireless technologies, such as server multicast/unicast transmissions, device multipath routing, and cache access constraints. We formulate the problem of Proactive Retention Routing Optimization (PRRO) as a non-convex, non-linear mixed-integer program. We prove that it is NP-Hard under both multicast/unicast modes, even when the caches have a large capacity, and develop a greedy algorithm that has provable performance bounds. Finally, we propose a heuristic for the capacitated cache case that has low computational complexity. Systematic evaluations including real data sets demonstrate the effectiveness of our approach, compared to the existing caching schemes.

Caches in Content-Centric Networks (CCN) are increasingly adopting flash memory based storage. The current flash cache technology stores all files with the largest possible “expiry date,” i.e., the files are written in the memory so that they are retained for as long as possible. This, however, does not leverage the CCN data characteristics where content is typically short-lived and has a distinct popularity profile. Writing files in a cache using the longest retention time damages the memory device thus reducing its lifetime. However, writing using a small retention time can increase the content retrieval delay, since, at the time a file is requested, the file may already have been expired from the memory. This motivates us to consider a joint optimization wherein we obtain optimal policies for jointly minimizing the content retrieval delay (which is a network-centric objective) and the flash damage (which is a device-centric objective). Caching decisions now not only involve what to cache but also for how long to cache each file. We design provably optimal policies and numerically compare them against prior policies.

Small operators who take part in secondary wireless spectrum markets typically have strict budget limits. In this paper, we study the bidding problem of a budget constrained operator in repeated secondary spectrum auctions. In existing truthful auctions, truthful bidding is the optimal strategy of a bidder. However, budget limits impact bidding behaviors and make bidding decisions complicated, since bidders may behave differently to avoid running out of money. We formulate the problem as a dynamic auction game between operators, where knowledge of other operators is limited due to the distributed nature of wireless networks/markets. We first present a Markov Decision Process (MDP) formulation of the problem and characterize the optimal bidding strategy of an operator, provided that opponents' bids are i.i.d. Next, we generalize the formulation to a Markov game that, in conjunction with model-free reinforcement learning approaches, enables an operator to make inferences about its opponents based on local observations. Finally, we present a fully distributed learning-based bidding algorithm which relies only on local information. Our numerical results show that our proposed learning-based bidding results in a better utility than truthful bidding.

This work considers the joint problem of content placement and service scheduling in femtocell caching networks, to maximize the traffic volume served from the cache. The problem is modeled as a Markov decision process. We combine the Edmonds-Karp algorithm and the marginal allocation algorithm to develop an efficient centralized policy called Infinite CAche-filling (ICA), which can get arbitrarily close to optimal asymptotically as the estimation time window increases. We also design a randomized algorithm called Infinite CAche-filling with Probabilistic scheduling (ICAP) that takes into consideration the femtocells service capability due to interference or multiplexing techniques. We derive a lower bound on the expected discounted hit count of ICAP. We also derive an upper bound on the probability that the performance of ICAP degrades from this expected value. Numerical results show that ICAP scales well and converges relatively fast in response to request pattern changes.

In this work, we study the problem of allocating two types of memory, which have different access speeds, to a set of routers in a single content-centric network. Total network delay is adopted as the performance metric. We first formulate the allocation problem and show that it is NP-hard. Then we prove that this problem is monotone submodular with a matroid constraint. Hence, we are able to derive a guaranteed (1-1/e)-approximation solution when the network is originally stable. We consider tree-structured networks with variable hierarchies under the widely used En-route caching assumption. Simulation results show that the developed algorithm performs well compared to the optimal solution, and only a limited fraction of nodes becomes hybrid regardless of the network size. To the best of our knowledge, this is the first theoretical work on quantitative analysis and algorithm development for hybrid memory allocation for content- centric networking (CCN).

Caches in Content-Centric Networks (CCN) are increasingly adopting flash memory based storage owing to its efficiency. The current flash cache technology stores all files with the largest possible "expiry date," i.e., the files are written in the memory so that they are retained for as long as possible. This, however, does not suit the CCN data characteristics where contents are typically short-lived and have a distinct popularity profile. Writing files in cache using the longest retention time damages the flash memory thus reducing the flash lifetime. However, writing using a small retention time can increase the content retrieval delay, since, at the time a file is requested, the file may already have been expired from the memory. This motivates us to propose a joint optimization wherein we obtain optimal policies for jointly minimizing the content retrieval delay (which is a network-centric objective) and the flash damage (which is a device centric objective). Caching decisions now not only involve what to cache and where to cache but also for how long is each file cached. The optimality of our policies are shown analytically, and are compared against prior policies using simulations.

In a cooperative content distribution (CCD) using multiple interfaces, a smart wireless device receives content from a base station (BS) on its cellular interface, and it broadcasts the same content through another wireless interface, such as WiFi. However, different users can experience different link qualities, and users with slow wireless links can be a bottleneck in terms of CCD performance. To address this problem, we propose a device selection method, which leverages multiple interfaces of the selected devices to perform CCD. Our proposed method takes into account the link quality of both primary (cellular) and secondary (WiFi/short-range) interfaces of the devices, and selects the devices with the best link quality for CCD. To analyze the stability of the proposed CCD method against selfish deviators, we model the problem as a repeated CCD game. We show that although the proposed method yields significant gains in terms of energy and frequency carrier savings, it is vulnerable to selfish deviating users. To address this challenge, we propose a carrier aggregation-based incentive mechanism. The analytical and simulation results show that the proposed mechanism maximizes individual and network payoffs, and is an equilibrium against unilateral selfish deviations.

This paper considers co-operation between primary and secondary users in shared spectrum radio networks via caching. We first consider a network with one channel shared between a single macro (primary) base station and multiple micro (secondary) base stations. Secondary base stations can cache some primary files and thereby satisfy content requests generated from nearby primary users. For this co-operative scenario, we develop two caching and scheduling policies under which the set of primary and secondary request generation rates that can be supported increases from the case without cooperation. The first of these algorithms, fixed primary caching policy (FPCP), provides more gain in the set of supportable request generation rates. However under this algorithm primary packet transmissions from secondary base stations have the same priority of access as secondary packets and thus might suffer in terms of delay. In the second algorithm, variable primary caching policy (VPCP), primary packet transmissions from the secondary base stations have higher priority of access than that of secondary packets. We find that the set of request generation rate vectors for which all queues in the network are stable under each of these algorithms is greater than that under any non-cooperative algorithm. We conduct extensive simulations to compare the performance of both algorithms against that of an optimal noncooperative algorithm. Finally, we extend the analysis to a network with multiple channels.

This paper considers cooperation between primary and secondary users in shared spectrum radio networks via caching. A network consisting of a single macro (primary) base-station and multiple small (secondary) base-stations is considered. Secondary base-stations can cache some primary files and thereby satisfy content requests generated from nearby primary users. For this cooperative scenario, we develop two caching and scheduling policies under which the set of primary and secondary user request generation rates that can be supported increases from the case without cooperation. The first of these algorithms provides maximum gain in the set of supportable primary and secondary request generation rates. However under this algorithm primary packet transmissions from secondary base-stations do not have higher priority than that of secondary packets. As a result, we propose another sub-optimal (with respect to set of supportable request generation rate vectors) algorithm wherein primary packet transmissions from secondary base-stations have higher priority than that of secondary packets. Extensive simulations are conducted to compare the performance of both algorithms with that of a non-cooperative algorithm that is optimal, with respect to set of supportable request generation rates, among all noncooperative policies.

In this paper, we characterize the average end-to-end delay in an opportunistic multihop secondary cognitive radio network overlaid with a primary multihop network. The nodes in both networks use a random medium access control scheme with exponentially distributed backoff. We first model the network as a two-class priority queuing network and use queuing theoretic approximation techniques to obtain a set of relations involving the mean and second moments of the interarrival and service times of packets at a secondary node. Then, applying these parameters to an equivalent open single-class G/G/1-queuing network, we obtain expressions for the average end-to-end delay of a packet in the secondary network using a diffusion approximation. Next, we extend the analysis to a case where secondary nodes cooperatively relay primary packets to improve their own transmission opportunities. The mathematical results are validated against extensive simulations.

We consider network layer cooperation in spectrum sharing networks whereby some secondary users relay primary users' packets, in return for more favorable spectrum access rules. Under this cooperative scheme, we investigate how primary and secondary networks can be stabilized without explicit knowledge of the packet arrival rates. We consider a primary packet generation process wherein a packet is formed by aggregating constant amount of bits that arrive in every time slot from upper-layers of the primary transmitter. For this primary packet generation model we develop a relaying and scheduling algorithm using Lyapunov drift techniques that does not require knowledge of packet arrival rates. We also construct a guaranteed stability region representing packet generation rates for which the algorithm can stabilize the network. The set of secondary packet generation rate vectors for which the network can be stabilized do not decrease under cooperation when the primary packet generation rate is lower than what can be maximally supported without cooperation. For higher primary packet generation rates the algorithm stabilizes the network for a non-empty set of secondary packet generation rate vectors.

Spectrum auction is considered a suitable approach to efficiently allocate spectrum among unlicensed users. In a typical spectrum auction, secondary users (SUs) bid to buy spectrum bands from a primary owner (PO) who acts as the auctioneer. Existing spectrum auctions assume that SUs have static and known values for the channels. However, in many real world settings, the SUs do not know the exact value of channel access at first, but they learn it and adapt it over time. In this paper, we study spectrum auctions in a dynamic setting where SUs can change their valuations based on their experiences with the channel quality. We propose ADAPTIVE, a dynAmic inDex Auction for sPectrum sharing with TIme-evolving ValuEs that maximizes the social welfare of the SUs. ADAPTIVE is based on multi-armed bandit models where for each user an allocation index is independently calculated in polynomial time. Then we generalize ADAPTIVE to Multi-ADAPTIVE that auctions multiple channels at each time. We provide a sufficient condition under which Multi-ADAPTIVE achieves the maximum social welfare. Both ADAPTIVE and Multi-ADAPTIVE have some desired economic properties that are formally proven in the analysis. Also, we provide a numerical performance comparison between our proposed mechanisms and the well known static auctions, namely the Vickrey second price auction and the VCG mechanism.

In this paper, we characterize the average end-to-end delay and maximum achievable per-node throughput in an opportunistic secondary cognitive radio network coexisting with a primary network where both networks consist of static nodes that use random medium access schemes. Assuming an ideal sensing mechanism, we first model the secondary network as a two-class priority queuing network and use queuing approximation techniques to obtain a set of relations involving the mean and second moments of the inter-arrival time and service-time of packets at a secondary node. Then, utilizing these parameters in an equivalent open G/G/1 queuing network, we obtain closed form expressions for average end-to-end delay of a packet in the secondary network and the maximum achievable throughput of a secondary node. The results are validated against extensive simulations.

This paper considers network-layer cooperation in cognitive radio networks whereby secondary users can relay primary user's packets, in return for a more favorable spectrum access rules. Under this cooperative scheme, the paper investigates whether, and under what conditions, the primary and secondary networks can be stabilized without explicit knowledge of the packet arrival-rates. We consider a deterministic and periodic primary packet arrival process and develop a relaying and scheduling algorithm using Lyapunov drift techniques that does not require knowledge of primary and secondary packet arrival rates. The algorithm is then shown to stabilize the transmission queues in the network for all secondary packet arrival rates that lie in the interior of a certain region. The region includes all secondary arrival-rate vectors that can be supported when the secondary nodes do not cooperate. Furthermore, when the primary data arrival-rate is greater than what could have been supported without relays but less than what can be maximally supported with relays, the algorithm stabilizes the network for a non-empty set of secondary arrival-rate vectors. The significance of these results is that they show that properly designed cooperation may result in a win-win scenario for both primary and secondary users (and not just for one type of users). Finally we extend our analysis to the case of a deterministic but aperiodic primary packet arrival process.

Spectrum auction is considered a suitable approach to efficiently allocate spectrum among unlicensed users. In a typical spectrum auction, Secondary Users (SUs) bid to buy spectrum bands from a Primary Owner (PO) who acts as the auctioneer. Existing spectrum auctions assume that SUs have static and known values for the channels. However, in many real world settings, SUs do not know the exact value of channel access at first, but they learn it over time. In this paper, we study spectrum auctions in a dynamic setting where SUs can change their valuations based on their experiences with the channel. We propose ADAPTIVE, a dynAmic inDex Auction for sPectrum sharing with TIme-evolving ValuEs that maximizes the social welfare of the SUs. ADAPTIVE is based on multi-armed bandit models where for each user an allocation index is independently calculated in polynomial time. ADAPTIVE has some desired economic properties that are formally proven in the analysis. Also, we provide a numerical performance comparison between ADAPTIVE and the well known Vickrey second price auction as a representative of static auctions.

Cognitive radio is a novel communication paradigm that can significantly improve spectrum utilization by allowing the cognitive radio users to dynamically utilize the licensed spectrum. To achieve this, studying efficient spectrum allocation mechanisms is imperative. In this paper, we consider a cognitive radio network consisting of a primary spectrum owner (PO), multiple primary users (PU) and multiple secondary users (SU). We propose a reserve price auction mechanism for spectrum sharing in cognitive radio networks where the SUs bid to buy spectrum bands from the PO who acts as the auctioneer, selling idle spectrum bands to make a profit. Unlike most existing auction mechanisms that assume identical channels, we consider a more general and more realistic case where channels have different qualities. Also, SUs are allowed to express their preferences for each channel separately. That is, each SU submits a vector of bids, one for each channel. In addition, reservation prices that are proportional to channel qualities are imposed by the PO. The proposed auction mechanism results in efficient allocation that maximizes SUs' valuations subject to reserve price constraints, and it has desired economic properties that we formally prove in the analysis. Numerical results show performance improvements compared to the case of reserve price auction with identical channels and the case of having no reservation prices.

In this paper, we extend an information-theoretic approach for characterizing the minimum cost of tracking the motion state information, such as locations and velocities, of nodes in dynamic networks. A rate-distortion formulation is proposed to solve this minimum-cost motion-tracking problem, where the minimum cost is the minimum information rate required to identify the network state at a sequence of tracking time instants within a certain distortion bound. The formulation is applicable to various mobility models, distortion criteria, and stochastic sequences of tracking time instants and hence is general. Under Brownian motion and Gauss-Markov mobility models, we evaluate lower bounds on the information rate of tracking the motion state information of nodes, where the motion state of a node is 1) the node's locations only, or 2) both its locations and velocities. We apply the obtained results to analyze the geographic routing overhead in mobile ad hoc networks. We present the minimum overhead incurred by maintaining the geographic information of nodes in terms of node mobility, packet arrival process, and distortion bounds. This leads to precise characterizations of the observation that given certain state-distortion allowance, protocols aimed at tracking motion state information may not scale beyond a certain level of node mobility.

Efficient transmission control (e.g., power/rate control) in the physical layer, link scheduling in the link layer and routing in the network layer are critical design issues of wireless ad hoc networks. By considering both the quality-of-service and the utilization of resources under the temporally correlated uncertainties of the network conditions, a sequential decision framework is proposed for protocol design and layering. By observing that there are usually different performance concerns in the network layer versus lower layers, two correlated sequential decision models for the operations at different layers are proposed. With the decision model in the link and physical layers, scheduling and transmission control are jointly optimized. By adding a decision model in the network layer, the benefit of cross-layer information is quantified and the optimal routing/forwarding strategy is characterized. Practical algorithms based on the proposed decision models are also developed to achieve optimal/near-optimal performance.

Overheads incurred by network protocols diminish the capacity available for relaying useful data in a dynamic communications network. Discovering lower bounds on the amount of protocol overhead incurred is important for the development of efficient network protocols and for characterizing the effective capacity available for network users. This paper presents an information-theoretic framework for characterizing the minimum protocol overheads incurred for maintaining location information in a network with mobile nodes. Specifically, the minimum overhead problem is formulated as a rate-distortion problem. The formulation may be applied to networks with arbitrary traffic arrival and location service schemes. Lower bounds are derived for the minimum overheads incurred for maintaining the location of the nodes and consistent neighborhood information in terms of node mobility and packet arrival processes. This leads to a characterization of the deficit caused by the protocol overheads on the overall transport capacity.

We consider the location service in a mobile ad-hoc network (MANET), where each node needs to maintain its location information by 1) frequently updating its location information within its neighboring region, which is called neighborhood update (NU), and 2) occasionally updating its location information to certain distributed location server in the network, which is called location server update (LSU). The trade off between the operation costs in location updates and the performance losses of the target application due to location inaccuracies (i.e., application costs) imposes a crucial question for nodes to decide the optimal strategy to update their location information, where the optimality is in the sense of minimizing the overall costs. In this paper, we develop a stochastic sequential decision framework to analyze this problem. Under a Markovian mobility model, the location update decision problem is modeled as a Markov Decision Process (MDP). We first investigate the monotonicity properties of optimal NU and LSU operations with respect to location inaccuracies under a general cost setting. Then, given a separable cost structure, we show that the location update decisions of NU and LSU can be independently carried out without loss of optimality, i.e., a separation property. From the discovered separation property of the problem structure and the monotonicity properties of optimal actions, we find that 1) there always exists a simple optimal threshold-based update rule for LSU operations; 2) for NU operations, an optimal threshold-based update rule exists in a low-mobility scenario. In the case that no a priori knowledge of the MDP model is available, we also introduce a practical model-free learning approach to find a near-optimal solution for the problem.

In this paper, an information-theoretic framework is developed for characterizing the minimum cost, in bits per second, of tracking the motion state information, such as locations and velocities, of nodes in dynamic networks. The minimum-cost motion-tracking problem is formulated as a rate-distortion problem, where the minimum cost is the minimum rate of information required to identify the network state at a sequence of tracking time instants within a certain distortion bound. The formulation is general in that it can be applied to a variety of mobility models, distortion criteria, and stochastic sequences of tracking time instants. Under the Gauss-Markov mobility model, lower bounds on the information rate of tracking the motion state information of nodes in dynamic networks are derived, where the motion state of a node is 1) the node's locations only, or 2) both its locations and velocities. The results are then used to analyze the protocol overhead of geographic routing protocols in mobile ad hoc networks. The minimum overhead incurred by maintaining the geographic information of the nodes is characterized in terms of node mobility, packet arrival process and distortion bounds. This leads to precise mathematical description of the observation that, given certain state-distortion allowance, protocols aimed at tracking motion state information (such as geographic routing protocols) may not scale beyond a certain level of node mobility.

Forwarding decisions in routing protocols rely on information about the destination nodes provided by routing table states. When paths to a destination change, corresponding states become invalid and need to be refreshed with control messages for resilient routing. In large and highly dynamic networks, this overhead can crowd out the capacity for data traffic. For such networks, we propose the concept of weak state, which is interpreted as a probabilistic hint, not as absolute truth. Weak state can remain valid without explicit messages by systematically reducing the confidence in its accuracy. Weak State Routing (WSR) is a novel routing protocol that uses weak state along with random directional walks for forwarding packets. When a packet reaches a node that contains a weak state about the destination with higher confidence than that held by the packet, the walk direction is biased. The packet reaches the destination via a sequence of directional walks, punctuated by biasing decisions. WSR also uses random directional walks for disseminating routing state and provides mechanisms for aggregating weak state. Our simulation results show that WSR offers a very high packet delivery ratio ( ≥ 98%). Control traffic overhead scales asO(N), and the state complexity is Θ(N3/2), whereNis the number of nodes. Packets follow longer paths compared to prior protocols (OLSR , GLS-GPSR , ), but the average path length is asymptotically efficient and scales asO(√N). Despite longer paths, WSR's end-to-end packet delivery delay is much smaller due to the dramatic reduction in protocol overhead.

State signaling and maintenance mechanisms play crucial roles in communication network protocols. State is used to facilitate indirections in protocols such as routing. Design approaches for traditional state signaling mechanisms have been categorized into soft and hard state. In both approaches, the state is deterministic. Hence, we call both as having strong state semantics, or more crisply, refer to them as strong state. If the state tracks entities with dynamic nature, strong state rapidly becomes invalidated and needs to be refreshed explicitly through control packets. In this paper, we evaluate the recently proposed weak state. Weak state is a generalization of soft state that is characterized by probabilistic semantics and local updates. It is interpreted as a probabilistic hint and not absolute truth. Weak state also contains the confidence in the state value, which is a measure of the probability that the state remains valid. The confidence or the state semantics is decayed locally without the need for explicit state update traffic traversing the network. The local updates also help the protocol use better estimates for the state value. We define two metrics, pure distortion and informed distortion, to evaluate the consistency of the weak state paradigm and compare it against strong state. Pure distortion measures the average gap between the actual value of the state and the value maintained at a remote node. On the other hand, the use of confidence increases the protocol's ability to cope with even large pure distortion. The resulting effective distortion is captured by the informed distortion metric. Using mathematical analysis, we compare weak with strong state. Local updates reduce the pure distortion because the protocol uses the best estimate of state value. The informed distortion is also significantly less because the probabilistic confidence value hints the protocol if the state is invalid. The weak state mechanism can be used to build protocols (eg: WSR [1]), which systematically interpret the state information. The state itself can be mostly updated locally, with less frequent explicit update messages over the network (i.e. leading to dramatic reductions in control traffic).

This paper considers basic bounds on the overhead of link-state protocols in mobile ad hoc networks. Hierarchical protocols are known for their good scalability properties, and hence this paper considers a two-level hierarchical protocol. In such protocols, nodes need to keep track of shortest path information, link states and cluster membership. Two types of overheads are considered; the memory needed to store routing-related information, including link-states and cluster membership, and the control messages that need to be exchanged to keep track of the changes in the network. Memory overhead is important practically for dimensioning network nodes, while message routing overhead is important since it reduces the effective capacity of the network to carry user data (vis-a-vis control data). The scalability properties of the message routing overhead are analyzed for different modes of network scaling. Practical implications, such as optimal cluster size, average/fixed memory requirement and routing protocol parameter selections are discussed.

We consider the location service in a mobile ad-hoc network (MANET), where each node needs to maintain its location information in the network by (i) frequently updating its location information within its neighboring region, which is called neighborhood update (NU), and (ii) occasionally updating its location information to a certain (fixed) distributed location server in the network, which is called location server update (LU). A trade-off exists between the costs in location update operations, on one hand, and the additional incurred costs in (position-based) routing due to location errors, on the other hand. In this paper, we develop a stochastic sequential decision framework to analyze this trade-off and provide design guidelines on selecting good location update strategies in practice. Under a Markovian mobility model, the location update decision problem is modeled as a Markovian decision process (MDP). Based on the separable cost structure of the proposed MDP model, we first show that the location update decisions on NU and LU can be independently carried out without loss of optimality. Then we investigate the optimality of simple threshold-based updating rules in NU and LU operations. We finally introduce a model-free learning approach which is practically useful to find a near-optimal solution for the problem.

In this paper an information-theoretic formulation is used for characterizing the minimum overhead of maintaining link state information across a mobile ad hoc network. The minimum overhead problem is formulated a rate-distortion problem. Lower bounds are derived for the minimum overhead incurred by maintaining link state information when link state routing protocols are designed with guaranteed delivery ratio for data packets. The deficit caused by the this overhead on the overall transport capacity of a mobile network is characterized. Further a threshold value is derived for the delivery error ratio, and it is shown that no link state routing protocol can achieve a delivery error ratio smaller than this threshold.

We develop an analytical framework to study the throughput and routing overhead for proactive and reactive routing strategies in random access mobile ad hoc networks. To characterize the coexistence of the routing control traffic and data traffic, we model the interaction as a multi-class queue model at each node, where the aggregate control traffic and data traffic are two different classes of customers of the queue. We investigate the scaling property of the throughput, maximum mobility degree supported by the network and mobility-induced throughput deficiencies, under both classes of routing strategies. The proposed analytical model can be extended to incorporate various optimization techniques in routing. We present one exemplary technique and discuss its impacts on the scaling properties of throughput and routing overhead. The connection between the derived throughput result and some well-known network throughput capacity results in the literature is also addressed.

In order to adapt to time-varying wireless channels, various channel-adaptive schemes have been proposed to exploit inherent spatial diversity in mobile/wireless ad hoc networks where there are usually alternate next-hop relays available at a given forwarding node. However, current schemes along this line are designed based on heuristics, implying room for performance enhancement. To seek a theoretical foundation for improving spatial diversity gain, we formulate the selection of the next-hop as a sequential decision problem and propose a general "optimal stopping relaying (OSR)" framework for designing such next-hop diversity schemes. As a particular example, assuming Rayleigh fading channels, we implement an OSR strategy to optimize information efficiency (IE) in a protocol stack consisting of greedy perimeter stateless routing (GPSR) and IEEE 802.11 MAC protocols. We present mathematical analysis of the proposed OSR together with other strategies in literature for a single forwarding node. In addition, we perform extensive simulations (using QualNet) to evaluate the end-to-end performance of these relaying strategies in a multi-hop network. Both the mathematical and simulation results demonstrate the superiority of OSR over other existing schemes.

Overheads incurred by routing protocols diminish the capacity available for relaying useful data over a mobile wireless ad hoc network. Discovering and understanding the lower bounds on the amount of protocol overhead incurred for routing data packets is important for development of efficient routing protocols, and for understanding the actual (effective) capacity available for network users. In this paper we use an information-theoretic approach for characterizing the minimum routing overheads of geographic routing in a mobile network. We formulate the minimum overhead problem as a rate-distortion problem. The formulation may be applied to networks with arbitrary traffic arrival and location service schemes. We evaluate lower bounds on the minimum overheads incurred for maintaining the location of destination nodes and consistent neighborhood information in terms of node mobility and packet arrival process. We also characterize the deficit caused by the routing overheads in the overall transport capacity of a mobile network.

We consider the scenario of distributed data aggregation in wireless sensor networks, where each sensor can obtain and estimate the information of the whole sensing field through local data exchange and aggregation. The intrinsic trade-off between energy and delay in aggregation operations imposes a crucial question on nodes to decide optimal instants for forwarding their samples. The samples could be composed of the information from their own sensor readings or an aggregation of information with other samples forwarded from neighboring nodes. By considering the randomness of the sample arrival instants and the uncertainty of the availability of the multiaccess communication channel due to the asynchronous nature of information exchange among neighboring nodes, we propose a decision process model to analyze this problem and determine the optimal decision policies at nodes with local information. We show that, once the statistics of the sample arrival and the availability of the channel satisfy certain conditions, there exist optimal control-limit type policies which are easy to implement in practice. In the case that the required conditions are not satisfied, we provide two learning algorithms to solve a finite-state approximation model of the decision problem. Simulations on a practical distributed data aggregation scenario demonstrate the effectiveness of the developed policies, which can also achieve a desired energy-delay tradeoff.

Routing in communication networks involves the indirection from a persistent name (or ID) to a locator and delivering packets based upon the locator. In a large-scale, highly dynamic network, the ID-to-locator mappings are both large in number, and change often. Traditional routing protocols require high overhead to keep these in directions up-to-date. In this paper, we propose Weak State Routing (WSR), a routing mechanism for large-scale highly dynamic networks. WSR's novelty is that it uses random directional walks biased occasionally by weak indirection state information in intermediate nodes. The indirection state information is weak, i.e. interpreted not as absolute truth, but as probabilistic hints. Nodes only have partial information about the region a destination node is likely to be. This method allows us to aggregate information about a number of remote locations in a geographic region. In other words, the state information maps a set-of-IDs to a it geographical region. The intermediate nodes receiving the random walk use a method similar to longest-prefix-match in order to prioritize their mappings to decide how to bias and forward the random walk. WSR can also be viewed as an unstructured distributed hashing technique. WSR displays good rare-object recall with scalability properties similar to structured DHTs, albeit with more tolerance to dynamism and without constraining the degree distribution of the underlying network.Through simulations, we show that WSR offers a high packet delivery ratio, more than 98%. The control packet overhead incurred in the network scales as O(N) for N-node networks. The number of mappings stored in the network appears to scale as Θ(N(3/2)). We compare WSR with Dynamic Source Routing (DSR) and geographic forwarding (GPSR) combined with Grid Location Service (GLS). Our results indicate that WSR delivers more packets with less overhead at the cost of increased path length.

Mobile sensors cover more area over a fixed period of time than do the same number of stationary sensors. However, the quality of coverage (QoC) achieved by mobile sensors depends on the velocity, mobility pattern, number of mobile sensors deployed, and the dynamics of the phenomenon being sensed. The gains attained by mobile sensors over static sensors and the optimal motion strategies for mobile sensors are not well understood. In this paper, we consider the following event capture problem: the events of interest arrive at certain points in the sensor field and disappear according to known arrival and departure time distributions. An event is said to be captured if it is sensed by one of the mobile sensors before it fades away. We analyze how the QoC scales with velocity, path, and number of mobile sensors. We characterize cases where the deployment of mobile sensors has no advantage over static sensors, and find the optimal velocity pattern that a mobile sensor should adopt. We also present algorithms for two motion planning problems: 1) for a single sensor, what is the sensor trajectory and theminimum speedrequired to satisfy a bound on the event loss probability and 2) for sensors with fixed speed, what is theminimum number of sensorsrequired to satisfy a bound on the event loss probability. When the robots are restricted to move along a line or a closed curve, our algorithms return the optimal velocity for the minimum velocity problem. For the minimum sensor problem, the number of sensors used is within a factor of 2 of the optimal solution. For the case where the events occur at arbitrary points on a plane, we present heuristic algorithms for the aforementioned motion planning problems and bound their performance with respect to the optimal.

The wireless mesh networks (WMNs) are emerging as a popular means of providing connectivity to communities in both affluent and poor parts of the world. The presence of backbone mesh routers and the use of multiple channels and interfaces allow mesh networks to have better capacity than infrastructure-less multihop ad hoc networks. In this paper we characterize the average delay and capacity in random access MAC based WMNs. We model residential area WMNs as open G/G/1 queuing networks. The analytical model takes into account the mesh client and router density, the random packet arrival process, the degree of locality of traffic and the collision avoidance mechanism of random access MAC. The diffusion approximation method is used to obtain closed form expressions for end-to-end packet delay and maximum achievable per-node throughput. The analytical results indicate that how the performance of WMNs scales with the number of mesh routers and clients. We also discuss that how the results obtained for WMNs compare with well known results on asymptotic capacity of infrastructure-less ad hoc networks. The results obtained from simulations agree closely with the analytical results.

In this paper we focus on characterizing the average end-to-end delay and maximum achievable per-node throughput in random access multihop wireless ad hoc networks with stationary nodes. We present an analytical model that takes into account the number of nodes, the random packet arrival process, the extent of locality of traffic, and the back off and collision avoidance mechanisms of random access MAC. We model random access multihop wireless networks as open G/G/1 queuing networks and use the diffusion approximation to evaluate closed form expressions for the average end-to-end delay. The mean service time of nodes is derived and used to obtain the maximum achievable per-node throughput. The analytical results obtained here from the queuing network analysis are discussed with regard to similarities and differences from the well established information-theoretic results on throughput and delay scaling laws in ad hoc networks. We perform extensive simulations and verify that the analytical results closely match the results obtained from simulations.

In order to adapt to the time-varying nature of wireless channels, various channel-adaptive schemes have been proposed to exploit inherent spatial diversity in wireless ad hoc networks where there are usually alternate forwarding nodes available at a given forwarding node. However, existing schemes along this line are designed based on heuristics, implying room for performance enhancement. Thereby, to seek a theoretical foundation for improving spatial diversity gain, we formulate the selection of the next-hop relay as a sequential decision problem and derive a general "optimal stopping relaying (OSR)" framework for designing such spatial-diversity schemes. As a particular example, assuming Rayleigh fading channels, we implement an OSR strategy to optimize information efficiency (IE) in a protocol stack consisting of greedy perimeter stateless routing (GPSR) and IEEE 802.11 MAC protocols. We present an analysis of the algorithm for a single node. In addition, we perform extensive simulations (using QualNet) to evaluate the end-to-end performance of the proposed forwarding strategy. The results demonstrate the superiority of OSR over other existing schemes

Mobile sensors cover more area over a period of time than the same number of stationary sensors. However, the quality of coverage achieved by mobile sensors depends on the velocity, mobility pattern, number of mobile sensors deployed and the dynamics of the phenomenon being sensed. The gains attained by mobile sensors over static sensors and the optimal motion strategies for mobile sensors are not well understood. In this paper we consider the problem of event capture using mobile sensors. The events of interest arrive at certain points in the sensor field and fade away according to arrival and departure time distributions. An event is said to be captured if it is sensed by one of the mobile sensors before it fades away. For this scenario we analyze how the quality of coverage scales with the velocity, path and number of mobile sensors. We characterize the cases where the deployment of mobile sensors has no advantage over static sensors and find the optimal velocity pattern that a mobile sensor should adopt.We also present algorithms for two motion planning problems: (i) for a single sensor, what is the minimum speed and sensor trajectory required to satisfy a bound on event loss probability and (ii) for sensors with fixed speed, what is the minimum number of sensors required to satisfy a bound on event loss probability. When events occur only along a line or a closed curve our algorithms return optimal velocity for the minimum velocity problem. For the minimum sensor problem, the number of sensors used is within a factor two of the optimal solution. For the case where the events occur at arbitrary points on a plane we present heuristic algorithms for the above motion planning problems and bound their performance with respect to the optimal. The results of this paper have wide range of applications in areas like surveillance, wildlife monitoring, hybrid sensor networks and under-water sensor networks.

In this paper we focus on characterizing the average end-to-end delay and maximum achievable per-node throughput in random access multihop wireless ad hoc networks with stationary nodes. We present an analytical model that takes into account the number of nodes, the random packet arrival process, the extent of locality of traffic, and the back off and collision avoidance mechanisms of random access MAC. We model random access multihop wireless networks as open G/G/1 queuing networks and use diffusion approximation to evaluate closed form expressions for the average end-to-end delay. The mean service time of nodes is derived and used to obtain the maximum achievable per-node throughput. The analytical results obtained here from the queuing network analysis are discussed with regard to similarities and differences from the well established information-theoretic results on throughput and delay scaling laws in ad hoc networks. We also investigate the extent of deviation of delay and achievable throughput in a real world network from the analytical results presented in this paper. We perform extensive simulations and verify that the analytical results closely match the results obtained from simulations

We study a novel “coverage by directional sensors” problem with tunable orientations on a set of discrete targets. We propose a Maximum Coverage with Minimum Sensors (MCMS) problem in which coverage in terms of the number of targets to be covered is maximized whereas the number of sensors to be activated is minimized. We present its exact Integer Linear Programming (ILP) formulation and it is used as a baseline for comparison. Then we provide a distributed greedy algorithm (DGA) solution. By incorporating a measure of the sensors’ residual energy into DGA, we further develop a Sensing Neighborhood Cooperative Sleeping (SNCS) protocol which performs adaptive scheduling on a larger time scale. Finally, we evaluate the properties of the proposed solutions and protocol in terms of providing coverage and maximizing network lifetime through extensive simulations.

In this paper, information theoretic techniques are used to derive analytic expressions for the minimum expected length of control messages exchanged by proactive routing in a two-level hierarchical ad hoc network. Several entropy measures are introduced and used to bound the memory size necessary for the storage of the routing tables. The entropy rates of the topology sequences are used to bound the communication routing overhead-both the interior routing overhead within a cluster and the exterior routing overhead across clusters. A scalability analysis of the routing overheads with regard to the number of nodes and the cluster size is provided under three different network scaling modes. Finally, practical design issues are studied by providing the optimal cluster sizes that asymptotically minimize (i) the memory requirement for each cluster head; (ii) the total control message routing overhead.

This paper presents a mathematical and simulative framework for quantifying the overhead of reactive routing protocols, such as dynamic source routing and ad hoc on-demand distance vector, in wireless variable topology (ad hoc) networks. A model of the routing-layer traffic, in terms of the statistical description of the distance between a source and a destination, is presented. The model is used to study the effect of the traffic on the routing overhead. Two network models are analyzed; a Manhattan grid model for the case of regular node placement, and a Poisson model for the case of random node placement. We focus on situations where the nodes are stationary but unreliable. For each network model, expressions of various components of the routing overhead are derived as a function of the traffic pattern. Results are compared against ns-2 simulations, which corroborate the essential characteristics of the analytical results. One of the key insights that can be drawn from the mathematical results of this paper is that it is possible to design infinitely scalable reactive routing protocols for variable topology networks by judicious engineering of the traffic patterns to satisfy the conditions presented in this paper.

We consider transmitting images in a multihop wireless network with the minimal total power consumption while satisfying an end-to-end image quality constraint. Contrary to popular belief, we show that maximum compression before transmission does not always provide minimal energy consumption, especially in the case of dense sensor networks with complex signal processing algorithms. We formulate the minimal energy transmission problem as an optimization problem and present a heuristic algorithm for it. The proposed algorithm selects the optimal image compression parameters to minimize total energy dissipation given the network conditions and image quality constraints. Simulation results show up to 80% reduction in the total power consumption achieved by using the proposed adaptive algorithm compared to nonadaptive algorithms.

While several cluster based routing algorithms have been proposed for ad hoc networks, there is a lack of formal mathematical analysis of these algorithms. Specifically, there is no published investigation of the relation between routing overhead on one hand and route request pattern (traffic) on the other. This paper provides a mathematical framework for quantifying the overhead of a cluster-based routing protocol. We explicitly model the application-level traffic in terms of the statistical description of the number of hops between a source and a destination. The network topology is modelled by a regular two-dimensional grid of unreliable nodes, and expressions for various components of the routing overhead are derived. The results show that clustering does not change the traffic requirement for infinite scalability compared to flat protocols, but reduces the overhead by a factor of O(1/M) where M is the cluster size. The analytic results are validated against simulations of random network topologies running a well known (D-hop max-min) clustering algorithm.

This paper presents a new mathematical and simulative framework for quantifying the overhead of a broad class of reactive routing protocols, such as DSR and AODV, in wireless variable topology (ad-hoc) networks. We focus on situations where the nodes are stationary but unreliable, as is common in the case of sensor networks. We explicitly model the application-level traffic in terms of the statistical description of the number of hops between a source and a destination. The sensor network is modelled by an unreliable regular Manhattan (i.e. degree four) grid, and expressions for various components of the routing overhead are derived. Results are compared against ns-2 simulations for regular and random topologies, which corroborate the essential characteristics of the analytical results. One of the key insights that can be drawn from the mathematical results of this paper is that it is possible to design infinitely scalable reactive routing protocols for variable topology networks by judicious engineering of the traffic patterns to satisfy the conditions presented in this paper.

A link model-driven approach toward transmission control protocol (TCP) performance over a wireless link is presented. TCP packet loss behavior is derived from an underlying two-state continuous time Markov model. The approach presented here is (to our knowledge) the first that simultaneously considers (1) variability of the round-trip delay due to buffer queueing; (2) independent and nonindependent (bursty) link errors; (3) TCP packet loss due to both buffer overflow and channel errors; and (4) the two modes of TCP packet loss detection (duplicate acknowledgments and timeouts). The analytical results are validated against simulations using the ns-2 simulator for a wide range of parameters; slow and fast fading links; small and large link bandwidth-delay products. For channels with memory, an empirical rule is presented for categorizing the impact of channel dynamics (fading rate) on TCP performance.

An analytical framework for multiple TCP flows sharing a bottleneck link under the random early detection (RED) regime is developed. Closed form expressions for the steady state throughput and average queueing delay are derived and verified by simulations; these show that RED significantly improves the inherent TCP bias against links with higher round-trip delays as compared to tail drop, contrary to prevailing belief. Further, we derive closed form bounds on the minimum average queuing delay achievable through a RED gateway with no deterministic packet drop.

An analytical framework for modeling the performance of a single TCP session in the presence of random packet loss is presented. A Markovian approach is developed that allows us to study both memoryless channels (IID packet loss) and channels with memory (correlated packet loss) modeled by a two-state continuous-time Gilbert model. The analytical results are validated against results using the ns simulator. It is shown that the model predicts throughput for LAN/WAN (low and high bandwidth-delay products) with good accuracy. Further, throughput for the IID loss model is found to be relatively insensitive to the probability density function (PDF) of the loss inter-arrival process. For channels with memory, we present an empirically validated rule of thumb to categorize the channel transition frequency.