This thesis contributes toward the design of a quality-of-service (QoS) aware network layer for wireless ad hoc networks. With the lack of an infrastructure in ad hoc networks, the role of the network layer is not only to perform multihop routing between a source node and a destination node, but also to establish an end-to-end connection between communicating peers that satisfies the service level requirements of multimedia applications running on those peers. Wireless ad hoc networks represent autonomous distributed systems that are infrastructure-less, fully distributed, and multi-hop in nature. Over the last few years, wireless ad hoc networks have attracted significant attention from researchers. This has been fueled by recent technological advances in the development of multifunction and low-cost wireless communication gadgets. Wireless ad hoc networks have diverse applications spanning several domains, including military, commercial, medical, and home networks. Projections indicate that these self-organizing wireless ad hoc networks will eventually become the dominant form of the architecture of telecommunications networks in the near future. Recently, due to increasing popularity of multimedia applications, QoS support in wireless ad hoc networks has become an important yet challenging objective. The challenge lies in the need to support the heterogeneous QoS requirements (e.g., data rate, packet loss probability, and delay constraints) for multimedia applications and, at the same time, to achieve efficient radio resource utilization, taking into account user mobility and dynamics of multimedia traffic. In terms of research contributions, we first present a position-based QoS routing framework for wireless ad-hoc networks. The scheme provides QoS guarantee in terms of packet loss ratio and average end-to-end delay (or throughput) to ad hoc networks loaded with constant rate traffic. Via cross-layer design, we apply call admission control and temporary bandwidth reservation on discovered routes, taking into consideration the physical layer multi-rate capability and the medium access control (MAC) interactions such as simultaneous transmission and self interference from route members. Next, we address the network-layer resource allocation where a single-hop ad hoc network is loaded with random traffic. As a starting point, we study the behavior of the service process of the widely deployed IEEE 802.11 DCF MAC when the network is under different traffic load conditions. Our study investigates the near-memoryless behavior of the service time for IEEE 802.11 saturated single-hop ad hoc networks. We show that the number of packets successfully transmitted by any node over a time interval follows a general distribution, which is close to a Poisson distribution with an upper bounded distribution distance. We also show that the service time distribution can be approximated by the geometric distribution and illustrate that a simplified queuing system can be used efficiently as a resource allocation tool for single hop IEEE 802.11 ad hoc networks near saturation. After that, we shift our focus to providing probabilistic packet delay guarantee to multimedia users in non-saturated IEEE 802.11 single hop ad hoc networks. We propose a novel stochastic link-layer channel model to characterize the variations of the IEEE 802.11 channel service process. We use the model to calculate the effective capacity of the IEEE 802.11 channel. The channel effective capacity concept is the dual of the effective bandwidth theory. Our approach offers a tool for distributed statistical resource allocation in single hop ad hoc networks, which combines both efficient resource utilization and QoS provisioning to a certain probabilistic limit. Finally, we propose a statistical QoS routing scheme for multihop IEEE 802.11 ad hoc networks. Unlike most of QoS routing schemes in literature, the proposed scheme provides stochastic end-to-end delay guarantee, instead of average delay guarantee, to delay-sensitive bursty traffic sources. Via a cross-layer design approach, the scheme selects the routes based on a geographical on-demand ad hoc routing protocol and checks the availability of network resources by using traffic source and link-layer channel models, incorporating the IEEE 802.11 characteristics and interaction. Our scheme extends the well developed effective bandwidth theory and its dual effective capacity concept to multihop IEEE 802.11 ad hoc networks in order to achieve an efficient utilization of the shared radio channel while satisfying the end-to-end delay bound.

Modern routers use specialized hardware, such as Ternary Content Addressable Memory (TCAM), to solve the Longest Prefix Matching Problem (LPMP) quickly. Due to the fact that TCAM is a non-standard type of memory and inherently parallel, there are concerns about its cost and power consumption. This problem is exacerbated by the growth in routing tables, which demands ever larger TCAMs. To reduce the size of the TCAMs in a distributed forwarding environment, a batch caching model is proposed and analyzed. The problem of determining which routing prefixes to store in the TCAMs reduces to the In-tree Knapsack Problem (ITKP) for unit weight vertices in this model. Several algorithms are analysed for solving the ITKP, both in the general case and when the problem is restricted to unit weight vertices. Additionally, a variant problem is proposed and analyzed, which exploits the caching model to provide better solutions. This thesis concludes with discussion of open problems and future experimental work.

This research investigates cross-layer design in multi-hop wireless networks with random access. Due to the complexity of the problem, we study cross-layer design with a simple slotted ALOHA medium access control (MAC) protocol without considering any network dynamics. Firstly, we study the optimal joint configuration of routing and MAC parameters in slotted ALOHA based wireless networks under a signal to interference plus noise ratio based physical interference model. We formulate a joint routing and MAC (JRM) optimization problem under a saturation assumption to determine the optimal max-min throughput of the flows and the optimal configuration of routing and MAC parameters. The JRM optimization problem is a complex non-convex problem. We solve it by an iterated optimal search (IOS) technique and validate our model via simulation. Via numerical and simulation results, we show that JRM design provides a significant throughput gain over a default configuration in a slotted ALOHA based wireless network. Next, we study the optimal joint configuration of routing, MAC, and network coding in wireless mesh networks using an XOR-like network coding without opportunistic listening. We reformulate the JRM optimization problem to include the simple network coding and obtain a more complex non-convex problem. Similar to the JRM problem, we solve it by the IOS technique and validate our model via simulation. Numerical and simulation results for different networks illustrate that (i) the jointly optimized configuration provides a remarkable throughput gain with respect to a default configuration in a slotted ALOHA system with network coding and (ii) the throughput gain obtained by the simple network coding is significant, especially at low transmission power, i.e., the gain obtained by jointly optimizing routing, MAC, and network coding is significant even when compared to an optimized network without network coding. We then show that, in a mesh network, a significant fraction of the throughput gain for network coding can be obtained by limiting network coding to nodes directly adjacent to the gateway. Next, we propose simple heuristics to configure slotted ALOHA based wireless networks without and with network coding. These heuristics are extensively evaluated via simulation and found to be very efficient. We also formulate problems to jointly configure not only the routing and MAC parameters but also the transmission rate parameters in multi-rate slotted ALOHA systems without and with network coding. We compare the performance of multi-rate and single rate systems via numerical results. We model the energy consumption in terms of slotted ALOHA system parameters. We found out that the energy consumption for various cross-layer systems, i.e., single rate and multi-rate slotted ALOHA systems without and with network coding, are very close.

Several decades of physiology, imaging and psychophysics research on attention has generated an enormous amount of data describing myriad forms of attentional effects. A similar breadth of theoretical models have been proposed that attempt to explain these effects in varying amounts of detail. However, there remains a need for neurally detailed mechanistic models of attention that connect more directly with various kinds of experimental data -- behavioural, psychophysical, neurophysiological, and neuroanatomical -- and that provide experimentally testable predictions. Research has been conducted that aims to identify neurally consistent principles that underlie selective attentional processing in cortex. The research specifically focuses on describing the functional mechanisms of attentional routing in a large-scale hierarchical model, and demonstrating the biological plausibility of the model by presenting a spiking neuron implementation that can account for a variety of attentional effects. The thesis begins by discussing several significant physiological effects of attention, and prominent brain areas involved in selective attention, which provide strong constraints for developing a model of attentional processing in cortex. Several prominent models of attention are then discussed, from which a set of common limitations in existing models is assembled that need to be addressed by the proposed model. One central limitation is that, for many existing models, it remains to be demonstrated that their computations can be plausibly performed in spiking neurons. Further, few models address attentional effects for more than a single neuron or single cortical area. And finally, few are able to account for different forms of attentional modulation in a single detailed model. These and other limitations are addressed by the Attentional Routing Circuit (ARC) proposed in this thesis. The presentation of the ARC begins with the proposal of a high-level mathematical model for selective routing in the visual hierarchy. The mathematical model is used to demonstrate that the suggested mechanisms allow for scale- and position-invariant representations of attended stimuli to be formed, and provides a functional context for interpreting detailed physiological effects. To evaluate the model's biological plausibility, the Neural Engineering Framework (NEF) is used to implement the ARC as a detailed spiking neuron model. Simulation results are then presented which demonstrate that selective routing can be performed efficiently in spiking neurons in a way that is consistent with the mathematical model. The neural circuitry for computing and applying attentional control signals in the ARC is then mapped on to neural populations in specific cortical laminae using known anatomical interlaminar and interareal connections to support the plausibility of its cortical implementation. The model is then tested for its ability to account for several forms of attentional modulation that have been reported in neurophysiological experiments. Three experiments of attention in macaque are simulated using the ARC, and for each of these experiments, the model is shown to be quantitatively consistent with measured data. Specifically, a study by Womelsdorf et al. (2008) demonstrates that spatial shifts of attention result in a shifting and shrinking of receptive fields depending on the target's position. An experiment by Treue and Martinez-Trujllo (1999) reports that attentional shifts between receptive field stimuli produce a multiplicative scaling of responses, but do not affect the neural tuning sensitivity. Finally, a study by Lee and Maunsell (2010) demonstrates that attentional shifts result in a multiplicative scaling of neural contrast-response functions that is consistent with a response-gain effect. The model accounts for each of these experimentally observed attentional effects using a single mechanism for selectively processing attended stimuli. In conclusion, it is suggested that the ARC is distinguished from previous models by providing a unifying interpretation of attentional effects at the level of single cells, neural populations, cortical areas, and over the bulk of the visual hierarchy. As well, there are several advantages of the ARC over previous models, including: (1) scalability to larger implementations without affecting the model's principles; (2) a significant increase in biological plausibility; (3) the ability to account for experimental results at multiple levels of analysis; (4) a detailed description of the model's anatomical substrate; (5) the ability to perform selective routing while preserving biological detail; and (6) generating a variety of experimentally testable predictions.

Resource management is important for network design and deployment. Resource management and allocation have been studied under a wide variety of scenarios --- routing in wired networks, scheduling in cellular networks, multiplexing, switching, and channel access in opportunistic networks are but a few examples. In this dissertation, we revisit resource management in the context of routing and scheduling in multihop wireless networks and pricing in single resource systems. The first issue addressed is of delays in multihop wireless networks. The resource under contention is capacity which is allocated by a joint routing and scheduling algorithm. Delay in wireless networks is a key issue gaining interest with the growth of interactive applications and proliferation of wireless networks. We start with an investigation of the back-pressure algorithm (BPA), an algorithm that activates the schedule with the largest sum of link weights in a timeslot. Though the BPA is throughput-optimal, it has poor end-to-end delays. Our investigation identifies poor routing decisions at low loads as one cause for it. We improve the delay performance of max-weight algorithms by proposing a general framework for routing and scheduling algorithms that allow directing packets towards the sink node dynamically. For a stationary environment, we explicitly formulate delay minimization as a static problem while maintaining stability. We see similar improved delay performance with the advantage of reduced per time-slot complexity. Next, the issue of pricing for flow based models is studied. The increasing popularity of cloud computing and the ease of commerce over the Internet is making pricing a key issue requiring greater attention. Although pricing has been extensively studied in the context of maximizing revenue and fairness, we take a different perspective and investigate pricing with predictability. Prior work has studied resource allocations that link insensitivity and predictability. In this dissertation, we present a detailed analysis of pricing under insensitive allocations. We study three common pricing models --- fixed rate pricing, Vickrey-Clarke-Groves (VCG) auctions, and congestion-based pricing, and provide the expected operator revenue and user payments under them. A pre-payment scheme is also proposed where users pay on arrival a fee for their estimated service costs. Such a mechanism is shown to have lower variability in payments under fixed rate pricing and VCG auctions while generating the same long-term revenue as in a post-payment scheme, where users pay the exact charge accrued during their sojourn. Our formulation and techniques further the understanding of pricing mechanisms and decision-making for the operator.

In order to meet the increasing demand for higher data rates, next generation wireless networks must incorporate additional functionalities to enhance network throughput. Multihop networks are considered as a promising alternative due to their ability to exploit spatial reuse and to extend coverage. Recently, industry has shown increased interest in multihop networks as they do not require additional infrastructure and have relatively low deployment costs. Many advances in physical and network layer techniques have been proposed in the recent past and they have been studied mostly in single-hop networks. Very few studies, if any, have tried to quantify the gains that these techniques could provide in multihop networks. We investigate the impact of simple network coding, advanced physical layer and cooperative techniques on the maximum achievable throughput of wireless multihop networks of practical size. We consider the following advanced physical layer techniques: successive interference cancellation, superposition coding, dirty-paper coding, and some of their combinations. We achieve this by formulating several cross-layer frameworks when these techniques are jointly optimized with routing and scheduling. We also formulate power allocation subproblems for the cases of continuous power control and superposition coding. We also provide numerous engineering insights by solving these problems to optimality.

Ad-Hoc Wireless routing has become an important area of research in the last few years due to the massive increase in wireless devices. Computational Geometry is relevant in attempts to build stable, low power routing schemes. It is only recently, however, that models have been expanded to consider devices with a non-uniform broadcast range, and few properties are known. In particular, we find, via both theoretical and experimental methods, extremal properties for the Localized Delaunay Triangulation over the Mutual Inclusion Graph. We also provide a distributed, sub-quadratic algorithm for the generation of the structure.

Wireless sensor networks offer the advantages of low cost, flexible measurement of phenomenon in a wide variety of applications, and easy deployment. Since sensor nodes are typically battery powered, energy efficiency is an important objective in designing sensor network algorithms. These algorithms are often application-specific, owing to the need to carefully optimize energy usage, and since deployments usually support a single or very few applications.<p> This thesis concerns applications in which the sensors monitor a continuous scalar field, such as temperature, and addresses the problem of determining the location of a contour line in this scalar field, in response to a query, and communicating this information to a designated sink node. An energy-efficient solution to this problem is proposed and evaluated. This solution includes new contour detection and query propagation algorithms, in-network-processing algorithms, and routing algorithms. Only a small fraction of network nodes may be adjacent to the desired contour line, and the contour detection and query propagation algorithms attempt to minimize processing and communication by the other network nodes. The in-network processing algorithms reduce communication volume through suppression, compression and aggregation techniques. Finally, the routing algorithms attempt to route the contour information to the sink as efficiently as possible, while meshing with the other algorithms. Simulation results show that the proposed algorithms yield significant improvements in data and message volumes compared to baseline models, while maintaining the integrity of the contour representation.

Expanderande städer resulterar i ökande behov av godstransporter och för att behålla en fungerande godsdistribution kan åtgärder behöva vidtas. Trafikstockning och försämrad stadsmiljö är negativa effekter som kan förknippas med en dåligt fungerande godsdistribution. Citylogistik handlar om att kontrollera och optimera godstransporter i urbana områden (city) så att negativa effekter minimeras. Olika typer av citylogistiska åtgärder och koncept har identifierats. Till dem hör till exempel samdistribution, reglering av godstransporter och avancerade IT-system. Inom ramen för projektet SAMLIC, som startades i Linköping 2004, genomfördes pilotförsöket PILOT med det övergripande syftet att utvärdera ekonomisk potential med samdistribution i Linköpings city. Under PILOT omsattes ett samdistributionskoncept i praktiken. En databas med information om godsdistributionen under försöket upprättades för senare analys. Syftet med detta examensarbete har varit att formulera matematiska modeller över godsdistributionen i ett medelstort city, som kan ge underlag för utvärdering av citylogistiska koncept och i synnerhet samdistributionskoncept. De matematiska modeller som tagits fram är optimeringsmodeller för ruttplanering och metoder för att lösa optimeringsmodellerna har implementerats. För att utvärdera modellerna och metoderna har en fallstudie av Linköpings city gjorts, med datamaterial från PILOT. Modellerna ger möjlighet till effektiva analyser och jämförelser av citylogistiska koncept. Fallstudien visar dessutom att optimering av godsdistributionen i city innebär god förbättringspotential vilket ger ytterligare motiv till att använda modeller som verktyg. / Urbanization and city expansion result in an increasing need of transportation of goods, and in order to maintain efficiency, measures are needed. The aim of city logistics is to minimize negative impacts associated with city center goods distribution, such as traffic congestion and negative impacts on the living environment. Several city logistic measures have previously been suggested, such as freight consolidation, governance and advanced IT systems. Within the SAMLIC project started in 2004, a demonstration project known as PILOT was carried out in central Linköping, wherein the concept of freight consolidation was applied in reality. The objective was to evaluate the economic potential of freight consolidation. The aim of this thesis was to formulate mathematical models of the distribution of goods in a medium sized Swedish city. The models are to be used in the evaluation of city logistic measures, focusing on freight consolidation. The distribution problem is modelled as a vehicle routing problem, and methods for solving the resulting optimization problems have been implemented. Using data from PILOT, the models have been applied on Linköping with the purpose of evaluating the methods, as well as investigating the potential of using models for planning the distribution of goods. Conclusions involve that analyses of, and comparisons between, city lo-gistic measures can be efficiently made using mathematical models. The case study also indicates that goods distribution can be improved through the use of optimization methods, which further motivates mathematical modelling.

This dissertation focuses on improvements in vehicle routing that can be gained by allowing multiple vehicles to service a common load. We explore how costs can be reduced through the elimination of the constraint that a load must be serviced by only one vehicle. Specifically, we look at the problem of routing vehicles to service loads that have distinct origins and destinations, with no constraint on the amount of a load that a vehicle may service. We call this the Pickup and Delivery Problem with Split Loads (PDPSL). We model this problem as a dynamic program and introduce structural results that can help practitioners implement the use of split loads, including the definition of an upper bound on the benefit of split loads. This bound indicates that the routing cost can be reduced by at most one half when split loads are allowed. Furthermore, the most benefit occurs when load sizes are just above one half of vehicle capacity. We develop a heuristic for the solution of large scale problems, and apply this heuristic to randomly generated data sets. Various load sizes are tested, with the experimental results supporting the finding that most benefit with split loads occurs for load sizes just above one half vehicle capacity. Also, the average benefit of split loads is found to range from 6 to 7% for most data sets. The heuristic was also tested on a real world example from the trucking industry. These tests reveal the benefit of both using split loads and allowing fleet sharing. The benefit for split loads is not as significant as with the random data, and the various business rules added for this case are tested to find those that have the most impact. It is found that an additional cost for every stop the vehicle makes strictly limits the potential for benefit from split loads. Finally, we present a simplified version of the PDPSL in which all origins are visited prior to any destination on a route, generalizing structural results from the Split Delivery Vehicle Routing Problem for this problem.