A Vehicular Sensor Network (VSN) is a sensing platform composed of smart onboard sensor nodes (vehicles) and roadside units, in which vehicles continuously collect sensor data from the road network to enable a range of real-time data-intensive applications, such as traffic pattern/congestion analysis, road surface diagnosis, and urban pollution monitoring. However, due to lossy links, limited bandwidth and highly dynamic network topology, it is very challenging to efficiently collect the data generated by vehicles on the road, especially under dense traffic situations. In this paper, we propose to deploy mobile agents for collecting sensor readings from a given road segment of interest. The mobile agent migrates among vehicles within the segment via wireless broadcast and uses local on-board computational resources to process and collect data as required. Since the wireless links are generally lossy, a broadcast may not reach all the vehicles within the segment; thus, to improve the reliability of the scheme, we further propose a termination decision algorithm based on recursive Bayesian estimation by which the agent decides whether all vehicles within the segment have been visited. Extensive simulation results show that the proposed agent-based data collection scheme achieves close to 100% data collection coverage under a wide range of vehicular traffic densities, while retaining a small communication overhead.

We consider a system where packets (jobs) arrive for processing using one of the policies in a given class. We study the connection between the minimal evacuation time and the stability region of the system and show that evacuation time optimal policies can be used for stabilizing the system (and for characterizing its stability region) under broad assumptions. Conversely, we show that while a stabilizing policy can be suboptimal in terms of evacuation time, one can always design a randomized version of any stabilizing policy that achieves an optimal evacuation time in the asymptotic regime when the number of evacuated packets scales to infinity.

With the emergence of high speed mobile Internet access in smart devices, providing a specific quality of service (QoS) for video delivery is a challenging task due to the dynamic nature of the wireless channels. In this paper, we propose an auction based mechanism that facilitates cooperation among mobile nodes, in order to increase the level of QoS satisfaction in the network. In the proposed mechanism, users with excess resources that are surplus to their QoS requirement (sellers) are motivated to provide a relaying service to users with low QoS (buyers), in exchange for monetary compensation. Our mechanism is entirely distributed and does not require a coordination by a centralized auctioneer, which helps to minimize the implementation overhead and allows it to be applied regularly with short period times. The efficiency of the auction mechanism is verified using simulation over a range of typical practical scenarios.

The high popularity of Wi-Fi technology for wireless access has led to a common problem of densely deployed access points (APs) in residential or commercial buildings, competing to use the same or overlapping frequency channels and causing a degradation to the user experience due to excessive interference. This degradation is partly caused by the restriction where each client device is allowed to be served only by one of a very limited set of APs (e.g. belonging to the same residential unit), even if it is within range of (or even has a better signal quality to) many other APs. In this paper, we propose a cooperative strategy to mitigate the interference and enhance the quality of service in dense wireless deployments, by having neighboring APs agree to take turns (e.g. in round-robin fashion) to serve each other's clients. We present and analyze a cooperative game-theoretic model of the incentives involved in such cooperation and identify the conditions under which cooperation would be beneficial for the participating APs.

Intelligent transport information systems (TIS) are one of the most rapidly emerging applications of wireless vehicular communications using DSRC/WAVE technology. A core function in a TIS is the estimation of traffic density using beacons transmitted by individual vehicles, subsequently used for purposes such as traffic light control or incident detection. In this paper, we conduct an in-depth study on how the accuracy of traffic density estimation depends on various parameters of the wireless beacons transmission policy, such as beaconing rate and timing. Unlike many other studies, our focus is entirely on the application-layer metric of density estimation accuracy, rather than low-layer metrics such as packet loss rate and throughput. Our results are evaluated over a wide range of traffic traces generated by a commercial microscopic traffic simulator (Paramics), corresponding to a typical urban scenario consisting of a signalized intersection of multiple-lane roads.

The IEEE 802.11 MAC protocol performance degrades severely as the number of stations in the collision domain increases in a saturated network. Employing cooperative retransmission at the MAC layer provides a way to work around the performance limitations by exploiting the broadcast nature of wireless communication. This paper presents a new routing metric, termed Expected Cooperative Forwarding Delay (ECFD), with the aim of selecting a minimum end-to-end delay path for multi-hop multi-rate wireless mesh networks. Different from previously proposed cooperative-aware routing metrics such as ORETT, the ECFD metric is based not only on expected cooperative transmission time but accounts for queueing and backoff delays in the path selection process. We describe the design and implementation of ECFD, and conduct extensive simulation experiments in random topologies showing that, under various realistic network traffic patterns, the use of ECFD instead of ORETT and ETT significantly improves both end-to-end delay and throughput.

We consider a system where jobs (packets) arrive for processing using one of the policies in a given class. We study the connection between the minimal evacuation times and the stability region of the system under the given class of policies. The result is used to establish the equality of information theoretic capacity region and system stability region for the multiuser broadcast erasure channel with feedback.

This paper proposes an opportunistic rate-adaptive expected transmission time (ORETT) metric, which exploits cooperative (relay-aided) retransmissions to achieve high-throughput routing in multi-rate wireless mesh networks. This metric captures the combined effects of MAC-layer cooperative retransmission by neighbor nodes with transmission rate diversity (and rate-dependent link quality). In our approach, a relay node is selected among one-hop neighbors to assist with packet retransmissions and minimize the expected retransmission time. The paper describes the design and implementation of the ORETT routing metric using the DSR routing protocol. Our extensive simulation on the Qualnet platform confirms that multi-rate routing using ORETT significantly reduces the overall transmission time while yielding higher packet delivery ratio compared to single rate unicast or non-cooperative ETT based routing.

Cooperative communication techniques offer significant performance benefits over traditional methods that do not exploit the broadcast nature of wireless transmissions. Such techniques generally require advance coordination among the participating nodes to discover available neighbors and negotiate the cooperation strategy. However, the associated discovery and negotiation overheads may negate much of the cooperation benefit in mobile networks with highly dynamic or unstable topologies (e.g. vehicular networks). This paper discusses uncoordinated cooperation strategies, where each node overhearing a packet decides independently whether to retransmit it, without any coordination with the transmitter, intended receiver, or other neighbors in the vicinity. We formulate and solve the problem of finding the optimal uncoordinated retransmission probability at every location as a function of only a priori statistical information about the local environment, namely the node density and radio propagation model. We show that the solution consists of an optimal cooperation region which we provide a constructive method to compute explicitly. Our numerical evaluation demonstrates that uncoordinated cooperation offers a low-overhead viable alternative, especially in high-noise (or low-power) and high node density scenarios.

We investigate the impact of wireless channel temporal variations on the design of medium access control (MAC) protocols for body area networks (BANs). Our measurements-based channel model captures large and small time-scale signal correlations, giving an accurate picture of the signal variation, specifically, the deep fades which are the features that mostly affect the behavior of the MAC. We test the effect of the channel model on the performance of the 802.15.4 MAC both in contention access mode and TDMA access mode. We show that there are considerable differences in the performance of the MAC compared to simulations that do not model channel temporal variation. Furthermore, explaining the behavior of the MAC under a temporal varying channel, we can suggest specific design choices for the emerging BAN MAC standard.

The design of an end-to-end Internet congestion control protocol that could achieve high utilization, fair sharing of bottleneck bandwidth, and fast convergence while remaining TCP-friendly is an ongoing challenge that continues to attract considerable research attention. This paper presents ACP, an Adaptive end-to-end Congestion control Protocol that achieves the above goals in high bandwidth-delay product networks where TCP becomes inefficient. The main contribution of ACP is a new form of congestion window control, combining the estimation of the bottleneck queue size and a measure of fair sharing. Specifically, upon detecting congestion, ACP decreases the congestion window size by the exact amount required to empty the bottleneck queue while maintaining high utilization, while the increases of the congestion window are based on a “fairness ratio” metric of each flow, which ensures fast convergence to a fair equilibrium. We demonstrate the benefits of ACP using both ns-2 simulation and experimental measurements of a Linux prototype implementation. In particular, we show that the new protocol is TCP-friendly and allows TCP and ACP flows to coexist in various circumstances, and that ACP indeed behaves more fairly than other TCP variants under heterogeneous round-trip times (RTT).

Urban residential areas are becoming increasingly dense with more and more home networks being deployed in close proximity. The paper considers a dense urban residential area where each house/unit has its own wireless access point (AP), deployed without any coordination with other such units. In this situation, it would be much better if neighbouring APs - i.e., APs that are physically close to each other - would form groups, where one member of the group would serve the terminals of all group members in addition to its own terminals, while the other access points of the group can be silent or even turned off, thus reducing interference and increasing overall Quality of Experience (QoE). The fact that participating units are deployed without any coordination makes the overall QoE vulnerable to the selfish behaviour of each unit. We propose a protocol where each unit operates in an equilibrium of a cooperative-neighbourhood game. We show using a game theoretic model that there exists a motivation for APs to enter and remain in cooperative neighbourhoods, in which interference is decreased due to the voluntary cooperation of the neighbours.

Vehicular traffic density is a key factor in determining the behaviour of radio overlapping and thus impacts performance of data and safety message communication in Vehicular Ad hoc Networks (VANETs). In this paper, we propose a novel density model for urban traffic systems and employ this model for the purpose of spatial-temporal analysis of radio overlapping. To model traffic density, we consider a signalized junction and road segments linked to that junction as basic building blocks of urban traffic systems. The density model enables us to derive a framework to explain trends and critical regions of radio overlapping corresponding to VANET scenarios targeted for urban transportation systems, which cannot be derived from uniform density models widely used in existing literature. We apply the derived radio overlapping model to study channel load associated with periodic beaconing, a fundamental mechanism for safety message communication in VANETs. This study also provides a generic analytical framework to investigate other performance aspects of data and safety message communication in VANETs. Our experimental results using the proposed realistic density model demonstrate the need for an adaptive mechanism to adjust transmission power and data rate to reduce channel loads associated with dense traffic conditions.

We consider a body area network (BAN) setting in which sensor nodes send data to a common hub regularly on a TDMA basis, as defined by the emerging IEEE 802.15.6 BAN standard. Our previous work has established the benefits of variable TDMA scheduling in this setting, where the order of communication with nodes in each TDMA round is determined on the fly by the hub, based on the actual outcomes (success or failure) of their recent transmissions. This technique takes into account the very slow fading nature of wireless channels in BANs, and can minimize the expected rate of transmission losses merely by ordering nodes according to their most recent channel state information, without any additional energy overhead. In this paper, we focus on an extended TDMA setting where the length of each TDMA round is greater than the number of nodes, i.e. a number of 'spare' slots are reserved for retransmissions of lost packets. We consider delay-constrained data transmissions based on a Markov model of the wireless channels. We evaluate several variable scheduling strategies in terms of the trade-off between the energy consumption due to the additional retransmissions and the reduction of the loss rate. We show how the best strategy depends on the energy budget of the sensor nodes, and demonstrate the considerable reduction in the loss rate (up to 18%) that can be achieved over a naive approach where static TDMA scheduling is combined with retransmission slots at the end of the round.

Road safety is one of the most important emerging applications envisioned for Vehicular Ad hoc Networks (VANETs). Generally, such applications involve the broadcast of safety messages, consisting of beacons transmitting vehicles' state (e.g. position and velocity) with a regular period, as well as emergency messages warning about unexpected critical events. From the perspective of safety, the application performance depends foremost on two metrics: for the event-driven warning messages, the probability of message reception; and for periodic messages, the variability of the inter-reception time (IRT), which ultimately determines the freshness of the information received by the driver. In this paper, we develop an analytical model to compute the above metrics in an urban traffic scenario. Focusing on a road segment linked to a signalized junction as a basic building block of urban traffic systems, we apply a novel road traffic density model to investigate the dynamics of the reliability metrics and characterize the region(s) on the road segment according to the achieved safety level. Our numerical study shows that in broadcast mode, the hidden terminal effect is the driving factor determining the reliability of transmissions. Furthermore, the impact of hidden terminals has the greatest effect in road sections where vehicles have high velocity, leading to the poorest performance in regions where reliable reception is needed the most in order to minimize the risk of accidents.

This paper presents a portable and hardware-independent data-link layer design that adds cooperative retransmission support to the Linux kernel wireless SoftMAC implementation (mac80211). With cooperative retransmission, a unicast packet that is not acknowledged by its intended destination node can be retransmitted by a third node in the vicinity of the source and destination, rather than by the original source itself, if the cooperating node overhears the packet successfully and has a better link to the destination. Unlike prior realizations of MAC-layer cooperation schemes, our implementation is entirely hardware-independent and transparent, requiring no modification of existing wireless drivers or upper-layer software. We evaluate the cooperative kernel module on the ORBIT wireless testbed platform and present a range of experimental results that demonstrate the significant improvements in the throughput and reliability that can be achieved by its usage.

We consider a typical body area network (BAN) setting in which sensor nodes send data to a common hub regularly on a TDMA basis, as defined by the emerging IEEE 802.15.6 BAN standard. We explore variable TDMA scheduling techniques that allow the order of transmissions within each TDMA round to be decided on the fly, rather than be fixed in advance. Our approach is related to opportunistic scheduling used in other multiuser wireless systems, which aims to maximize the system throughput by allocating transmission opportunities to users with the `best' instantaneous channel. However, the energy overheads of opportunistic scheduling, which requires the continuous reporting of channel states to the scheduler, make it incompatible with body area networks where nodes turn their radio off (`sleep') until it is their turn to transmit, as an energy-saving measure. Accordingly, we consider variable TDMA scheduling strategies that decide on the transmission order at the start of each TDMA round based on the last known channel state of each sensor. We formulate the optimization problem of maximizing the expected throughput (or, equivalently, minimizing the expected loss rate) based on a Markov model of the wireless channel, and present some simple approximate heuristics that can be computed quickly yet perform well in practice. We evaluate the performance of these strategies and heuristics numerically in a wide range of scenarios, and demonstrate the marked improvement they achieve over a fixed TDMA allocation.

Extensive research in recent years has shown the benefits of cooperative relaying in wireless networks, where nodes overhear and cooperatively forward packets transmitted between their neighbors. Most existing studies focus on physical-layer optimization of the effective channel capacity for a given transmitter-receiver link; however, the interaction among simultaneous flows between different endpoint pairs, and the conflicts arising from their competition for a shared pool of relay nodes, are not yet well understood. In this paper, we study a distributed pricing framework, where sources pay relay nodes to forward their packets, and the payment is shared equally whenever a packet is successfully relayed by several nodes at once. We formulate this scenario as a Stackelberg (leader-follower) game, in which sources set the payment rates they offer, and relay nodes respond by choosing the flows to cooperate with. We provide a systematic analysis of the fundamental structural properties of this generic model. We show that multiple follower equilibria exist in general due to the nonconcave nature of their game, yet only one equilibrium possesses certain continuity properties that further lead to a unique system equilibrium among the leaders. We further demonstrate that the resulting equilibria are reasonably efficient in several typical scenarios.

We consider the problem of gathering data from a sensor network using mobile elements. In particular, we consider the case where the data are produced by measurements and need to be delivered to a predefined sink within a given time interval from the time the measurement takes place. Mobile elements travel the network in predefined paths, collect the data from the nodes, and deliver them to the sink. Each node must be visited by a mobile element that must then reach the sink within the given time constraint. The goal is to plan the paths for the mobile elements that minimize the total length travelled. Several variations of this problem have been considered in existing literature. We propose an algorithmic solution that builds node-disjoint tours that always include the sink, cover the network, and optimize the total length travelled. We provide an integer linear programming formulation for the problem, and propose two novel heuristics for building the tours. We evaluate the performance of our algorithm by comparing it to the optimal solution as well as to an alternative heuristic, commonly used in related time-window vehicle routing problems, and demonstrate the superior performance of our approach.

Several studies in recent years have considered the use of mobile elements for data gathering in wireless sensor networks, so as to reduce the need for multi-hop forwarding among the sensor nodes and thereby prolong the network lifetime. Since, typically, practical constraints preclude a mobile element from visiting all nodes in the sensor network, the solution must involve a combination of a mobile element visiting a subset of the nodes (cache points), while other nodes communicate their data to the cache points wirelessly. This leads to the optimization problem of minimizing the communication distance of the sensor nodes, while keeping the tour length of the mobile element below a given constraint. Several algorithms in existing literature have tackled this problem by separating the construction of the mobile element tour from the computation of the forwarding trees to the cache points. In this paper, we propose a new algorithm that alternates between these phases and iteratively improves the outcome of each phase, based on the result of the other. We compare the resulting performance of our algorithm with that of previous work, and show that it closes a considerable portion of the gap from the theoretical optimal solution.

We describe our experience from the implementation of the T-MAC protocol for wireless sensor networks in the open-source Castalia simulator. Notwithstanding the popularity of the protocol in the research literature in recent years, we find several practical issues that are not addressed in the original protocol description, which lead to a degree of freedom in the protocol design and implementation and have an impact on its resulting performance. These issues include the ability of the underlying physical layer and hardware to efficiently detect the activation events in the protocol, and necessary changes to the collision resolution and clock synchronization procedures in the presence of varying sleep patterns. Our results highlight the need for rigorous detail in protocol descriptions in the research literature and provide important insights into some of the common pitfalls.

In wireless networks, transmissions can generally be overheard by unintended nodes in the vicinity of the sender and receiver, potentially causing interference to their own communications. Much of the related research has considered this as a nuisance and resulted in various proposals for overcoming the interference using scheduling, channel assignment, and many other mechanisms. In recent years, there has been growing attention to methods that aim to take advantage of the broadcast nature of the wireless medium and the ability of nodes to overhear their neighbors' transmissions. Two of the most important such methods are opportunistic routing (OR) and wireless network coding (NC), exemplified by the ExOR and COPE protocols, respectively. In this paper, we study the potential benefits (in terms of reducing transmissions) of forwarding schemes that combine elements from both the OR and NC approaches, when traffic on a bidirectional unicast connection between two nodes is relayed by multiple common neighbors. We present a dynamic programming algorithm to find the optimal scheme as a function of link error probabilities, and demonstrate that it can achieve up to 20% reduction in the number of transmissions compared to either OR or NC employed alone, even in a simple scenario of two common neighbors between the connection endpoints.

We consider cooperative retransmission strategies in wireless networks, where the retransmission of a failed frame is handled not by the original source but rather by common neighbors overhearing the transmission. The majority of existing literature in this space focuses on opportunistic mechanisms for choosing a single ¿best¿ neighbor, with a goal of minimizing the number of required (re-)transmissions. However, the coordination overhead of such mechanisms renders them unsuitable in general for scenarios involving delay-critical control or sensing applications, where the delivery latency, rather than number of retransmissions, is the dominant performance criterion. Accordingly, we study a distributed uncoordinated setting, where each neighbor that successfully overhears a frame decides independently whether to retransmit it in subsequent time slots, considering that multiple simultaneous such retransmissions will cause a collision. We employ a Bayesian approach to analyze the evolution of the system state view from the perspective of each cooperative neighbor, and derive a strategy of finding a sequence of retransmission probabilities for every neighbor in each time slot to minimize the expected delivery latency. We demonstrate for a wide variety of scenarios that this strategy achieves a significantly lower expected latency than either traditional retransmission or two-hop routing to the destination.

Cooperative communication methods in wireless networks, ranging from relaying by a common neighbor over a single wireless hop to opportunistic routing at the network layer, have been shown in recent years to offer significant performance gains over traditional approaches that ignore the broadcast nature of the wireless medium, and are particularly valuable in environments prone to channel shadowing and fading, such as mobile ad-hoc networks. A common feature of various cooperative methods proposed in the literature is the coordination required to discover the available neighbors and determine the optimal one(s) to be involved in the cooperation. However, the overhead cost of such coordination may be prohibitive in networks with highly dynamic topology (e.g. due to high mobility), as the discovery and negotiation overheads may negate much of the cooperation gains. Accordingly, we present the case for uncoordinated cooperative retransmission, where a node overhearing a frame may retransmit it ¿blindly¿ without any prior coordination with the transmitter, intended receiver, or any other neighbors in the vicinity. We pose and solve the problem of finding the optimal retransmission probability as a function of location, and characterize the optimal uncoordinated cooperation region through the solution of an integral equation that depends only on the a priori node density and wireless propagation model. Through numerical evaluation, we demonstrate that uncoordinated cooperation provides a low-overhead viable alternative, with a frame delivery probability that can even exceed that of coordinated cooperation methods in situations with high noise (or low transmission power) and high node density.

The concept of cooperative retransmission in wireless networks has attracted considerable research attention. The basic idea is that when a receiver cannot decode a frame, the retransmission is handled not by its original source but rather by a neighbour that overheard the transmission successfully, and may have a better channel to the destination. However, the majority of existing literature tackles the issue from the physical layer perspective, with either a single cooperating neighbour, or a multiple-neighbour setting where the receiver is capable of combining and decoding the signal from several simultaneous retransmissions. In this paper, we consider the case of multiple cooperating neighbours from a MAC-layer perspective. Thus, we assume a receiver that can only decode one transmission at a time, while multiple simultaneous retransmissions (by several neighbours that had overheard the frame successfully) will cause a collision. As a result, each neighbour with a successfully overheard copy of the frame faces a tradeoff between helping with a cooperative retransmission and possibly causing a collision. Accordingly, we pose the optimization problem of finding a distributed randomized strategy for the cooperating neighbours, which assigns a certain retransmission probability to every neighbour in each time slot, so as to minimize the expected latency until successful reception. We analyse the performance achieved by two approaches: one where the original source is silent while the neighbours conduct their cooperative retransmissions, and another where both the source and the neighbours may have a nonzero retransmission probability simultaneously. We show that the latter approach offers a significant performance improvement over the former one, as well as either traditional retransmission or two-hop routing to the destination.

Wireless mesh networks (WMN) have attracted considerable interest in years as a convenient, flexible and low-cost alternative to wired communication infrastructures in many contexts. However, the great majority of research on metropolitan-scale WMN has been centered around maximization of available bandwidth, suitable for non-real-time applications such as Internet access for the general public. On the other hand, the suitability of WMN for mission-critical infrastructure applications remains by and large unknown, as protocols typically employed in WMN are, for the most part, not designed for real-time communications. In this paper, we describe the smart transport and roads communications (STaRComm) project at National ICT Australia (NICTA), which sets a goal of designing a wireless mesh network architecture to solve the communication needs of the traffic control system in Sydney, Australia. This system, known as SCATS (Sydney coordinated adaptive traffic system) and used in over 100 cities around the world, connects a hierarchy of several thousand devices - from individual traffic light controllers to regional computers and the central traffic management centre (TMC) - and places stringent requirements on the reliability and latency of the data exchanges. We discuss our experience in the deployment of an initial testbed consisting of 7 mesh nodes placed at intersections with traffic lights, and share the results and insights learned from our measurements and initial trials in the process.

Communication solutions for passengers on public transport vehicles, in the form of on-board networks connected to the Internet via a mobile router (MR) and a wireless link, are increasingly offered by public transport providers in many countries. An important challenge in such networks is to guarantee a fair access to the scarce wireless bandwidth by all on-board users, particularly in networks with multiple wireless interfaces. Accordingly, we consider an active fairness control scheme, where the MR transparently overrides the TCP advertised receiver window size to limit the transmission rates of on-board TCP connections to their fair share. We focus on the overhead that this scheme places on the mobile router and the wireless interface, due to the need for the MR to estimate the round-trip time (RTT) of each on-board connection. We investigate the performance of three strategies that differ in the timing of RTT estimations, and show that a fairness target-based strategy, which continuously monitors the ongoing fairness index and invokes an RTT reestimation whenever it drops below a predetermined value, consistently achieves a significant improvement in fairness for only a mild overhead cost.

The concept of providing mobile Internet connectivity for passengers in public transport vehicles, where users connect to a local network that attaches to the Internet via a mobile router and a wireless link, has become increasingly popular in recent years, as evidenced by the growing amount of commercially available systems and associated research and standardization activities. The challenge of providing wireless connectivity to networks in motion is compounded by the highly dynamic nature of the user population and the strict quality-of-service (QoS) requirements of many applications typical of such environments. As a result, several protocols extending Internet QoS support approaches to on-board mobile networks have been proposed in the past. In this paper, we focus on modeling and performance evaluation of periodical aggregation of resource reservation messages, which forms the basis of the on-board RSVP protocol. We present a model consisting of a discrete-time, multiple-server and finite-capacity queueing system with bulk arrivals and departures, conduct a detailed analysis of the model, and use it to evaluate the performance of the resource reservation aggregation scheme in a practical scenario. The validity of our model is also backed by extensive simulation results.

We investigate the effects of using dual transmission power to achieve quality-of-service (QoS) differentiation in IEEE 802.11 wireless LANs. Specifically, we assume all stations employ the standard IEEE 802.11 distributed coordination function (DCF), with the exception that some stations transmit at a higher power than others. Consequently, in the event of a collision involving frames from both power levels, a high-power frame is more likely to be received correctly as a result of the so-called capture effect (i.e. received at a power sufficiently higher than that of the interference, allowing it to be decoded correctly). This effectively leads to QoS differentiation between two classes, corresponding to the high-power and low-power stations. We develop a Markov model for the IEEE 802.11 DCF in a network with dual transmission power over a Rayleigh-fading channel, and use it to evaluate the resulting performance, in terms of the key metrics of throughput and delay. We explore how the performance of the service classes depends on the proportion of stations in each class and the transmission power ratio, focusing in particular on the bounds achieved in the limit case of 'ideal differentiation', characterised by a perfect capture probability of high-power frames. We find that significant performance differentiation between high-power and low-power stations is achieved even with transmission power ratios that are not very high, leading us to conclude that employing multiple transmission power levels is a viable and efficient approach for service quality differentiation in wireless LANs.

A research area that has become increasingly important in recent years is that of on-board mobile communication, where users on a vehicle are connected to a local network that attaches to the Internet via a mobile router and a wireless link. In this architecture, link disruptions (e.g., due to signal degradation) may have an immediate impact on a potentially large number of connections. We argue that the advance knowledge of public transport routes, and their repetitive nature, allows a certain degree of prediction of impending link disruptions, which can be used to offset their catastrophic impact. Focusing on the transmission control protocol (TCP) and its extension known as Freeze-TCP, we present a detailed analysis of the performance improvement of TCP connections in the presence of disruption prediction. In particular, we propose a Markov model of Freeze-TCP that captures both the TCP behavior and the prediction+"freezing" feature and, using simulations, show that it accurately predicts the performance of the protocol. Our results demonstrate the significant throughput improvement that can be gained by disruption prediction, even with random packet losses or imperfect timing of the predicted disruptions

We study the problem of optimal packet coding for connections with large delay-bandwidth products. Generally, for a given loss rate, using a higher coding redundancy achieves a higher average throughput, but incurs higher transmission costs (e.g. in terms of energy of a wireless device) and creates a higher load on the network. We define an optimal coding strategy as one that minimizes the expected cost/throughput ratio, for a connection that has a cost per unit time and a cost per transmitted packet. We present an algorithm for computing the optimal strategy and study its properties. We demonstrate that the cost/throughput ratio can be significantly better than with simple retransmission schemes, show that it strongly depends on the decoding buffer size, and obtain several asymptotic bounds on the optimal strategy performance for both unlimited and fixed-size decoding buffers

We investigate the effects of using a dual transmission power scheme for quality-of-service (QoS) differentiation in IEEE 802.11 wireless LANs. By setting hosts to transmit at different power levels, we enhance the likelihood that a high-power frame gets received correctly when a collision involving frames from both power levels occurs due to the capture effect. We develop a Markov model for the IEEE 802.11 DCF in a dual transmission power system over a Rayleigh-fading channel, and use it to evaluate the resulting performance, in terms of the key metrics of throughput and delay. Specifically, we study how the performance of the service classes depends on the proportion of hosts from each service class and the transmission power ratio, and demonstrate that, counter-intuitively, this dependence may be non-monotonic

The inherent difficulty in faithfully modeling wireless channel characteristics in simulators has prompted researchers to build wireless network testbeds for realistic testing of protocols. While previous testbeds are mostly designed to provide a research environment of static wireless networks, our work is aimed to assess protocols used for mobile wireless networks (such as an on-board network on public transport vehicles). In this work, we describe our on-going efforts in designing and implementing a network mobility testbed for network mobility (NEMO) protocol. This paper attempts to provide an initial reference to identify the feature set necessary for a network mobility testbed. We first describe the architecture of our testbed. Next, we present some preliminary results to demonstrate the use of our testbed in evaluating the performance of NEMO protocol under different scenarios.

Protocols designed to provide error-free communications over lossy links commonly employ the idea of sliding windows, which is based on the go-back-n automatic repeat request (ARQ) scheme. Unless the packet error rate is extremely small, this scheme is known to perform poorly in connections with high bandwidth and round-trip delay. The methods typically used to address this drawback, such as selective repeat (SR) feedback and forward error correction (FEC), carry a cost in terms of memory requirements (e.g. buffers for out-of-order packets), implementation complexity, and extra computation time, and therefore energy consumption. While this is not a major consideration in traditional wired networks, it implies that such methods are unsuitable for certain applications involving wireless devices with severe resource limitations, e.g. in sensor networks. In this work, we focus on low-key bufferless receivers, incapable of accepting out-of-order packets or decoding FEC codes; consequently, the only possible way to increase the throughput efficiency above that of the go-back-n scheme is by advance packet retransmission. We carry out a detailed study of the fundamental performance bounds achievable by advance retransmission strategies, show that schemes based on a fixed number of packet repetitions are suboptimal, and describe a novel heuristic approach, called maximum expected advance first, which is shown to be asymptotically optimal and attain a significant throughput gain over go-back-n, without requiring any enhancements or additional resources at the receiver

In on-board mobile networks, such as those proposed for (and employed in) public transport vehicles, users are connected to a local network that attaches to the Internet via a mobile router and a wireless link. Central and coordinated management of mobility in a single router, rather than by each user device individually, has numerous advantages; however, it also means that link outages, e.g. due to signal degradation or handoff failure, may have an immediate impact on a potentially large number of connections. We argue that the advance knowledge of public transport routes, and their repetitive nature, allows a certain degree of prediction of impending link outages, which can be used to offset their catastrophic impact. Focusing on the TCP protocol and its extension known as Freeze-TCP, we study how the performance of the protocol depends on the outage prediction probability. In particular, we propose a Markov model of Freeze-TCP and, using simulations, show that it accurately predicts the performance improvement gained by outage prediction.

We study the problem of optimal packet coding for connections with large delay-bandwidth products. Generally, for a given loss rate, using a higher coding redundancy achieves a higher average throughput, but also incurs higher transmission costs (e.g. in terms of energy of a wireless device) and creates a higher load on the network. We define an optimal coding strategy as one that minimizes the expected cost/throughput ratio, for a connection that has a cost per unit time and a cost per transmitted packet. We present an algorithm for computing the optimal strategy and study its properties. We demonstrate that the cost/throughput ratio can be significantly better than with the simple retransmission schemes, showing, in particular, that it strongly depends on the decoding buffer size, and obtain several asymptotic bounds on the optimal strategy performance for both unlimited and fixed-size decoding buffers.

We study the problem of shared path protection in optical networks from the viewpoint of blocking probability minimization. Unlike the worst-case approach common in other studies, which typically deals with one failure at a time and requires recomputation of the protection paths after every failure, our framework assumes a fixed path protection strategy for every connection that does not change in response to failures in other connections, which is more realistic for networks with high failure rates. We study backup-path strategy configurations that minimize the blocking probability and derive various properties. We show that configurations which do not have partial overlaps among connections backup paths are optimal in a rather general sense. We discuss the minmax optimal configuration properties and present an efficient algorithm for finding it in a case of special interest, while showing it to be NP-hard in general. In addition, we discuss the properties of the game resulting if each connection chooses its backup path selfishly; we show it to belong to the class of potential games, well-studied in the game theory literature, and derive several further properties resulting from its specific structure.

A method commonly used for packet flow control over connections with long round-trip delays is "sliding windows". In general, for a given loss rate, a larger window size achieves a higher average throughput, but also a higher rate of spurious packet transmissions, rejected by the receiver merely for arriving out-of-order. We analyze the problem of optimal flow control quantitatively, for a connection that has a cost per unit time and a cost for every transmitted packet (these costs can have generic interpretations, not necessarily in terms of money). The optimal strategy is defined as one that minimizes the expected cost/throughput ratio, and is allowed to transmit several copies of a packet within a window. We derive bounds on the performance of the optimal strategy; in particular, we show that the optimal cost/throughput ratio increases merely logarithmically with the time price. We present a method for computing the optimal strategy, and demonstrate that a simple and efficient 'greedy' algorithm is sufficient to find a near-optimal solution.

The notion of timeout (i.e., the maximal time to wait before retrying an action) occurs in many networking contexts. Use of timeouts is encountered especially in large-scale networks, where negative acknowledgments (NACKs) on failures have significantly higher delays than positive acknowledgments (ACKs) and frequently are not employed at all. Selection of a proper timeout involves a tradeoff between waiting too long and loading the network needlessly by waiting too little. The common approach is to set the timeout to a large value, such that, unless the action fails, it is acknowledged within the timeout duration with a high probability. This approach leads to overly long, far from optimal, timeouts. Our quantitative approach has the purpose of computing and studying the optimal timeout strategy. The tradeoff is modeled by introducing a "cost" per unit time (until success) and a "cost" per repeated attempt. The optimal strategy is then defined as one that a selfish user would follow to minimize its expected cost. We discuss various practical interpretations of these costs. We then derive formulas for the optimal timeout values and study some of their fundamental properties. We identify the worthwhile conditions for making parallel attempts from the outset. We also demonstrate a striking property of positive feedback and study the interaction resulting when many users selfishly apply the optimal timeout strategy; we use a noncooperative game model and show that it suffers from an inherent instability problem. Some implications of these results on network design are discussed.

In noncooperative networks, resources are shared among selfish users, which optimize their individual performance measure. Traditional design methods tend to perform poorly in such networks, as they do not take into account the inherent noncooperative nature of the network users. Such networks require specialized design techniques in order to achieve efficient utilization of resources. We consider the generic and practically important class of atomic resource sharing networks, in which traffic bifurcation is not implemented, hence each user allocates its whole traffic to one of the network resources. We investigate topologies of parallel resources within a game-theoretic framework and establish the foundations of a design and management methodology that enables operation of such networks efficiently, despite both the lack of cooperation among users and the restrictions imposed by atomic resource sharing. We study various problems pertaining to capacity allocation, pricing, and admission control, and show that their solutions are substantially different from those corresponding to traditional networks.

In noncooperative networks, resources are shared among selfish users, which optimize their individual performance measure. We consider the generic and practically important case of atomic resource sharing, in which traffic bifurcation is not implemented, hence each user allocates its whole traffic to one of the network resources. We analyze topologies of parallel resources within a game-theoretic framework and establish several fundamental properties. We prove the existence of and convergence to a Nash equilibrium. For a broad class of residual capacity performance functions, an upper bound on the number of iterations till convergence is derived. An algorithm is presented for testing the uniqueness of the equilibrium. Sufficient conditions for achieving a feasible equilibrium are obtained. We consider extensions to general network topologies. In particular, we show that, for a class of throughput-oriented cost functions, existence of and convergence to a Nash equilibrium is guaranteed in all topologies. With these structural results at hand, we establish the foundations of a design and management methodology, that enables one to operate such networks efficiently, in spite of the lack of cooperation among users and the restrictions imposed by atomic resource sharing.