In federated learning (FL), clients update their local machine learning models using private data that is not to be shared with others. In each update period, the local models are then shared with a central server that maintains a global model that is used by all the clients. In this paper we consider the problem of scheduling and bandwidth assignment for vehicles that share a wireless communication channel during the FL. The objective is to minimize the update period duration so that global model updates can occur as quickly as possible. This is done by creating a transmission schedule and a fractional bandwidth assignment for each FL update period. The problem is modeled as a mixed-integer nonlinear program (MINLP) and since the problem is NP-complete, approximation algorithms are introduced that yield near-optimal solutions. This is done by doing a binary search on the update duration using a fractional relaxation and then by applying different dependent rounding procedures to obtain valid solutions. A variety of simulation results are presented that demonstrate the excellent performance of the proposed solutions when compared to the results obtained by an optimum direct solver on the same inputs.

A digital twin (DT) is a software version of a physical system (PS) that interacts with other objects on its behalf. In order to do so, changes in the PS must be communicated to the DT in a timely fashion, and this updating is referred to as DT synchronization. This paper addresses the Minimum Synchronization Period (MSP) problem in vehicular networks, which seeks to place DTs on execution servers (ESs) so as to minimize the maximum synchronization period for all physical systems and their DTs (PS-DT pairs), while satisfying communication and computation requirements. A novel solution is proposed by modelling the MSP problem as a multi-commodity quickest flow evacuation problem, which treats the synchronization data and processing as flow network inputs to be evacuated in the shortest possible time. Transmission and computation components are represented as network flows with linear edge delays, which enables the use of well-known techniques to find the quickest flow solution. To ensure that each DT is placed at a single execution server, an unsplittable flow rounding procedure is used that assigns DTs to servers without significantly increasing the synchronization objective. Simulation results demonstrate the quality of the MSP solutions produced by our algorithm using the optimal fractional solution as a lower bound for the optimal integral solution.

This paper introduces algorithms for static task class partitioning in mobile computation offloading (MCO). The objective is to partition a given set of task classes into two sets that are either executed locally by the mobile device (MD) or those classes that are permitted to contend for remote edge server (ES) execution. The goal is to find the task class partition that gives the minimum mean MD power consumption subject to task completion deadlines. The paper generates these partitions for both soft and hard task completion deadlines. Two variations of the problem are considered. The first assumes that the wireless and computational capacities are given and the second generates both capacity assignments subject to an additional resource cost budget constraint. The proposed partitioning algorithms are based on heuristic class ordering methods. The paper introduces two class ordering methods, a simpler one based on a task latency criterion, and an hierarchical version that first sorts and groups classes based on a mean power consumption criterion and then orders the task classes within each group based on a task completion time criterion. A variety of simulation results are presented that demonstrate the excellent performance of the proposed solutions for both given and optimized network resource assignments.

Digital twins (DTs) can be used to represent the behavior of real physical systems (PSs) in their interaction with other objects. Each DT periodically communicates with its PS and uses these updates to implement features that reflect the real behavior of the PS. A given feature can be implemented using different models that create the feature with differing levels of system accuracy. In this article, we study the DT model selection problem, where the DTs of multiple PSs are hosted at an execution server (ES). The objective is to maximize the minimum feature accuracy for the requested features by making appropriate model selections subject to the synchronization and ES execution constraints. The model selection problem is first formulated as an NP-complete integer program. It is then decomposed into multiple subproblems, each consisting of a modified Knapsack problem. A polynomial-time approximation algorithm is proposed using dynamic programming to solve it efficiently, by violating its constraints by at most a given factor. A generalization of the model selection problem is then given and an approximation algorithm using relaxation and dependent rounding is proposed to solve the problem efficiently with guaranteed constraint violations. A variety of simulation results are presented that demonstrate the excellent performance of the proposed solutions.

In mobile computation offloading (MCO), mobile devices (MDs) can choose to either execute tasks locally or have them executed on a remote edge server (ES). This paper addresses the problem of assigning the wireless communication bandwidth and the ES capacity used for the task execution, so that task completion time constraints are satisfied. The objective is to minimize the average power consumption of the mobile devices, subject to a cost budget constraint for obtaining the communication and computation resources. The paper includes contributions for both soft and hard task completion deadline constraints. The problems are first formulated as mixed integer nonlinear programs (MINLPs). Approximate solutions are then obtained by decomposing the problems into a collection of convex subproblems that can be efficiently solved. Results are presented that demonstrate the quality of the proposed solutions, which can achieve near optimum performance over a wide range of system parameters.

Digital twins (DTs) are virtual implementations of real physical systems (PSs) that interact with other objects on their behalf. Each PS periodically communicates with its digital twin so that the state of the DT is always sufficiently current. Using these updates, a DT can provide features that represent the real behavior of its PS using models that yield differing levels of system accuracy. In this paper, we study the DT model selection problem in wireless networks where the DTs of multiple PSs are hosted at an edge server (ES). The accuracy obtained from a given model is a function of its required amount of PS input data, the updating frequency, and the amount of computational capacity needed at the ES. The objective is to maximize the minimum achieved accuracy among the requested features by making appropriate model selections subject to wireless channel and ES resource availability. The problem is first formulated as an NP-complete integer program. The paper then uses relaxation and dependent rounding, and introduces a polynomial time approximation algorithm to obtain good solutions. A variety of simulation results are presented that demonstrate the excellent performance of the proposed solution.

Digital twins (DTs) are virtual implementations of physical systems (PSs) and can represent the states of the PSs in realtime. In order to update the DTs with changes in their corresponding PSs, the PSs should regularly send their state information data to the DTs. Each DT must be assigned to an execution server (ES) that processes the forwarded data from its corresponding PS. The output is then made available to applications that are operating at an Internet cloud server. In this article, we consider the problem of DT placement such that the maximum data request–response delay experienced by the application over all PSs is minimized, subject to maximum data age target constraints at the DTs and the application server. The problem is first formulated as an integer quadratic program (IQP) and then transformed into a semidefinite program (SDP). The problem is NP-complete. Since exact polynomial solutions are unavailable, several practical polynomial-time approximation algorithms are introduced. The algorithms are designed to give solutions with different tradeoffs between the accommodation of the application input timing latency and the achievement of data age targets.

This paper proposes a method of joint wireless network and job service allocation for use with mobile computation offloading where task completion times have deadline constraints. In this design, mobile devices (MDs) may execute a computational task locally or offload the task through a wireless network for execution on an edge server (ES). The network owner offers to lease wireless communication channels at a given set of base stations along with edge server capacity that is used for job execution. The objective is to obtain a wireless and service capacity allocation that minimizes the total energy consumption of the mobile devices, subject to a cost budget constraint and constraints on the delay incurred by offloaded task execution. The design is first formulated as a mixed integer nonlinear programming problem. An approximate solution is then obtained by decomposing it into a collection of convex subproblems that can be efficiently solved. Results are presented that demonstrate that the proposed solution achieves near optimum performance over a wide range of system parameters.

Digital twin (DT) has attracted a lot of attention from both industry and academia since it was proposed over a decade ago. A DT can be viewed as a virtual implementation of a real physical system (PS) and used as a representation of the PS for various applications. Despite the great potential of DTs in various fields, implementing DTs to obtain the desired functionality is not always straightforward. Specifically, accurate real-time synchronization between the features at a PS and its DT is essential for the DT to represent the PS. In this case, appropriate networking support is a key component to enable future DT development and applications. Currently, the research on DTs from a networking standpoint is still at an early stage, and only limited work has been done on DT implementation in practical systems. To fill this gap, this article investigates networking-related issues for DTs. Based on the existing literature, a feature-based method is provided for describing the desired properties and quality of DTs from the networking perspective. A stage-based implementation framework is presented for creating large-scale DTs for complex PSs by considering various networking constraints. Networking-related challenging issues and open research topics are discussed at the end.

This paper considers the problem of algorithmic efficiency in mobile computation offloading with Concurrent Local Execution (CLE). Online energy optimal algorithms can be developed when CLE is used to guarantee hard task deadlines while offloading over Markovian wireless channels. Unfortunately, these algorithms often have a high computational complexity, which prohibits their use in online mobile implementations. Three algorithms are introduced to reduce this complexity: Markovian Compression (MC), Time Compression (TC) and Preemption Using Continuous Offloading (Preemption-CO). MC and TC reduce the state space of the offloading Markovian process, by using a novel notion of geometric similarity, or by running an optimal online offloading algorithm in periodic time steps. In Preemption-CO, while a task is offloaded preemptively, the offloading decision at every time-slot is based on non-preemptive calculations. Our simulations show that, by applying these methods, the running times of the algorithms can be significantly reduced without suffering unreasonable performance degradation compared with the optimal energy performance.

This paper considers mobile computation offloading where task completion times are subject to hard deadline constraints. Hard deadlines are difficult to meet in conventional computation offloading due to the stochastic nature of the wireless channels involved. Rather than using binary offload decisions, we permit concurrent remote and local job execution when it is needed to ensure task completion deadlines. The paper addresses this problem for homogeneous Markovian wireless channel models. An online energy-optimal computation offloading algorithm, OnOpt, is proposed. Its energy optimality is shown by constructing a time-dilated absorbing Markov process and applying dynamic programming. Closed form results are derived for general Markovian processes, and the Gilbert-Elliott channel model is used to show how the particular structure of the Markov chain can be exploited in computing optimal offload initiation times more efficiently. It is shown that job completion time probabilities can be computed recursively, which leads to a significant reduction in the computational complexity of OnOpt. The performance of the proposed algorithm is compared to three others, namely, Immediate Offloading, Channel Threshold, and Local Execution. Performance results show that the proposed algorithm can significantly improve mobile device energy consumption compared to the other approaches while guaranteeing hard task execution deadlines.

Multi-decision mobile computation offloading occurs when a task to be remotely executed is uploaded in separate parts. Since the upload is partitioned, separate decisions are needed to determine the best time to initiate each upload. The multi-decision problem is considered for the case where execution completion times are subject to hard deadline constraints and where task offloads occur over a Markovian wireless channel. An online energy-optimal computation offloading algorithm, Multiopt (Multi-decision online Optimum), is introduced, whose optimality is proven using Markovian stopping theory. The paper presents results using the Gilbert-Elliott channel model, where task completion time probabilities can be efficiently computed using Dynamic Programming. Although the proposed algorithm is proven to be energy optimal, its performance is also compared to four others, namely, Immediate Offloading, Channel Threshold, Local Execution, as well as optimal single-part offloading. Results show that the proposed algorithm can significantly improve mobile device energy consumption compared to the other approaches while guaranteeing hard task execution deadlines.

This paper addresses the problem of scheduling transmission requests in vehicular networks so that long-term road side unit (RSU) energy costs are minimized. We demonstrate that knowledge of vehicular routes greatly improves the energy service costs and request drop ratio of RSU transmission. At the same time, simple and fast prediction algorithms can recover a significant portion of the loss incurred by a lack of vehicle route knowledge. The proposed algorithms use recent historical traffic data and simple calculations, such as Bayesian estimates, to predict the next few routing decisions by a vehicle, in order to load balance the scheduling of its requests over the RSU network. Our simulation results show that, while the common assumption in the literature of knowing the vehicle routes is indeed crucial for achieving good performance, simple algorithms can be used in cases where vehicle routes are not known ahead of time, in order to achieve comparable costs and loss ratios.

This paper considers a set of mobile users that employ cloud-based computation offloading. In order to execute jobs in the cloud, the user uploads must occur over a base station channel that is shared by all of the uploading users. Since the job completion times are subject to hard deadline constraints, this restricts the feasible set of jobs that can be processed. The system is modelled as a competitive game in which each user is interested in minimizing its own energy consumption. The game is subject to the real-time constraints imposed by the job execution deadlines, user specific channel bit rates, and the competition over the shared communication channel. The paper shows that for a wide range of parameters, a game where each user independently sets its offloading decisions always has a pure Nash equilibrium, and a Gauss-Seidel-like method for determining this equilibrium is introduced. Results are presented that illustrate that the system always converges to a Nash equilibrium using the Gauss-Seidel method. Data is also presented that show the number of iterations required, and the quality of the solutions. We find that the solutions perform well compared to a lower bound on total energy performance.

In conventional cognitive radio, the primary network usually remains unchanged. In some cases, however, the primary network operator may wish to accommodate secondary user access. In this paper, we assess the secondary user VoIP capacity when primary basestation scheduling is designed to be secondary network friendly. Friendliness is measured by the number of connections that can be supported subject to typical quality of service constraints in the presence of delay tolerant primary traffic. An offline scheduler is first derived that maximizes friendliness using an integer linear program formulation. We show that this schedule can be found using a minimum cost flow graph construction in time complexity that is polynomial in the number of time slots. Two online scheduling algorithms are then compared that achieve various levels of friendliness. The first algorithm operates by having the primary network temporally shape its residual capacity subject to satisfying its own packet deadline constraints. The second algorithm assumes virtual secondary calls and applies scheduling to both primary traffic and virtual secondary traffic. Results are presented for a variety of parameters that show the degree to which friendly scheduling can improve secondary user VoIP capacity compared to non-friendly primary scheduling.

In this paper we consider mobile users that employ computation offloading. In computational offloading, users can reduce energy consumption by executing jobs on a remote cloud server, rather than locally. In order to execute a job in the cloud, a mobile user must upload the job over a base station channel which is shared by all of the uploading users. The jobs are subject to hard deadline constraints, and since the channel quality may be different for each user, this may restrict the users ability to reduce energy usage. The system is modelled as a competitive game where each user is interested in minimizing its own energy use. The game is subject to the real-time constraints imposed by job execution deadlines, user specific channel bit rates, and the competition over the shared communication channel. The paper shows that for known classes of parameters, a game where each user independently adjusts its offload decisions always has a pure Nash equilibrium, and a Gauss-Seidel-like method for determining this equilibrium is presented. Results are then presented which illustrate that the system always converges to a Nash equilibrium using Gauss-Seidel. Data is presented which show the number of Nash equilibria that are found, the number of iterations required, and the quality of the solutions obtained. In particular, we find that the solutions perform well compared to a lower bound on total energy performance.

In this paper we consider a system that uses computation offloading, where an infrastructure-based cloud server executes jobs on behalf of a set of mobile devices. In this type of system, mobile job completion times include the latency needed for uploading to the cloud server. Since the processed jobs are subject to hard deadline constraints, this can introduce energy unfairness where mobile devices with poor channel conditions do not fully benefit from computation offloading. This unfairness however, can be compensated for, by dynamic scheduling at the cloud server. We first derive an offline scheduler using an integer linear program which uses a min-max energy objective and non-preemptive cloud server scheduling. We then introduce three online scheduling algorithms. The first is referred to as First-Generated-First-Served (FGFS) where jobs that are generated earlier are given priority at the cloud server. A modified version, referred to as γ-Ratio Accepted FGFS (γ-FGFS) is proposed where acceptance of a job execution partition is subject to an energy threshold test. We also introduce a version of this algorithm, γ-Ratio Accepted Earliest Deadline First (γ-EDF) which uses earliest deadline first scheduling to test for job partition feasibility. Various performance results are presented which show the improvements in energy fairness possible with the proposed schedulers.

Smart scheduling can be used to reduce infrastructure energy costs in vehicular roadside networks [1]. In this paper we consider the scheduling problem when there are multiple roadside units (RSUs) in tandem. In this case it is often desirable to load balance the energy consumption across the roadside units so that energy provisioning costs can be reduced as much as possible. We first derive an integer linear programming bound on the min-max energy usage of the roadside units for a given input sample function. This bound is used for comparisons with two proposed on-line scheduling algorithms. The first is a low complexity First-Come-First-Assigned (FCFA) scheduler that makes greedy RSU selections followed by a minimum energy time slot assignment. The second algorithm, the Greedy Flow Graph Algorithm (GFGA), makes the same RSU selection but reassigns time slots whenever a new vehicle is assigned to the same RSU. This is done using a locally optimum integer linear program that can be efficiently solved using a minimum cost flow graph. Results from a variety of experiments show that the proposed scheduling algorithms perform well when compared to the energy lower bounds. Our results also show that near-optimal results are possible but come with increased computation times compared to our heuristic algorithms.

Smart downlink scheduling can be used to reduce infrastructure-to-vehicle energy costs in delay tolerant roadside networks. In this paper we incorporate this type of scheduling into ON/OFF roadside unit sleep activity, to further reduce infrastructure power consumption. To achieve significant power savings however, the OFF-to-ON sleep transitions may be very lengthy, and this overhead must be taken into account when performing the ON state scheduling. We first incorporate the OFF/ON sleep transitions into a lower bound on energy usage that can be computed for given input sample functions. An online scheduling algorithm referred to as the Flow Graph Sleep Scheduler (FGS) is then introduced, which makes locally optimum decisions about when to initiate new ON/OFF cycles. This is done by computing an estimate of the energy needed to fulfill known vehicle communication requirements with and without the OFF period. This calculation is efficiently done using a novel minimum flow graph formulation. Results from a variety of experiments show that the proposed scheduling algorithm performs well when compared to the energy lower bound. It is especially attractive in situations where vehicle demands and arrival rates are such that the energy costs permit frequent ON/OFF cycling.

It is our sincere pleasure to welcome you to the IEEE Workshop on Video Everywhere, which will take place on June 4 in Madrid, Spain, as part of the 14th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM 2013). VidEv focusses on the significant challenges that must be addressed in order to enable the full potential of mobile video networking. After a very thorough and selective process, our workshop includes 6 papers which address various key issues relating to mobile video. The workshop will bring together researchers from industry and academia in order to discuss their views on the future of mobile video.

In conventional cognitive radio networks it is usually assumed that the primary network remains unchanged. The onus is then placed on the secondary network users to make the best use of any residual radio capacity. In some situations however, the primary network operator may wish to accommodate secondary user access. This objective has motivated recent work which considers simple modifications at the primary user stations that would lead to better secondary spectrum availability. In this paper primary base station scheduling mechanisms are proposed which are designed to be friendly from a secondary network user perspective. We focus on packet scheduling algorithms which maximize friendliness when the secondary users are transmitting real-time VoIP traffic. An optimization problem is first formulated which can maximize friendliness over finite time intervals. An on-line scheduling algorithm is then proposed which attempts to achieve this goal. This is done by having the primary network temporally shape its residual capacity subject to satisfying its own packet deadline constraints. Simulation results are presented which show that our proposed scheme results in better secondary user real-time traffic support compared with conventional scheduling.

It is our sincere pleasure to welcome you to the IEEE Workshop on Video Everywhere, taking place on June 25 in San Francisco, as part of the 13th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM 2012).

Vehicular ad-hoc networks will soon support a wide variety of inter-vehicle and vehicle-to-roadside applications. In many cases these networks will also co-exist with battery operated networks such as those deployed for sensor and mesh networked applications. In these latter types of networks, mesh node energy efficiency is often of paramount importance. This paper proposes improvements in mesh network energy efficiency by opportunistically ferrying delay tolerant traffic through co-existent vehicular networks. This is accomplished by dynamically routing traffic through vehicular paths when this forwarding is compatible with traffic flow quality-of-service constraints. The proposed mechanism is referred to as opportunistic vehicle assisted forwarding (OVAF). A model is formulated which provides an optimum routing bound under different objectives using hybrid multi-hop mesh routing and vehicular packet forwarding. A heuristic is then presented which can be used in practical networks which use OVAF. Simulation results show large improvements in network performance when this is used compared to conventional single-network multi-hop forwarding.

Roadside infrastructure can be used provide a wide variety of commercial services in vehicular ad hoc networks. One particular challenge is that of providing roadside radio coverage in highway locations where wired electricity is not available. In this case, roadside access points (APs) powered by renewable energy such as solar power, is a viable alternative. The cost of provisioning this type of roadside infrastructure is dependent on the average power consumption of the AP, and can be reduced by energy efficient scheduling. In this paper, we consider the problem of satisfying vehicle communication requirements while minimizing the energy needed by the roadside access point. The problem is formulated as a Mixed Integer Linear Program (MILP) which provides an upper bound for the performance of any realizable scheduling algorithm. We then propose a Nearest Fastest Set (NFS) scheduler that uses vehicle location and velocity inputs to address the problem. Results from a variety of experiments show that the proposed scheduling algorithm performs well when compared to the performance bound.

Solar powered wireless mesh nodes must be provisioned with a solar panel and battery combination that is sufficient to prevent node outage. When such a network is deployed, there are usually restrictions in the way the nodes can be positioned, and this results in a time-varying and node-dependent attenuation of the available solar energy. Unfortunately, conventional resource provisioning methodologies do not take into account these positional variations, and therefore the deployed system may be over-provisioned. In this paper the resource provisioning problem is considered from this point of view. A linear programming formulation is first developed which gives lower bounds on the node resource provisioning cost assignments. A provisioning algorithm is then introduced that takes positional solar energy variations into consideration. Our results show that a significant reduction in provisioning cost can be obtained using the proposed methodology when compared to the conventional case.

Dual-Mode handsets containing both WLAN and cellular interfaces are becoming increasingly common. When moving between WLAN and cellular radio coverage,the switching of an active session from one interface to another is referred to as Vertical Handover (VHO). To provide successful VHO the WLAN link has to be maintained until the cellular connection is established. Our previous measurements of the WLAN coverage inside a building shows that this is very difficult given the time constraints in a loosely coupled cellular/WLAN architecture. In this paper we extend our previous work and propose an explicit trigger node to assist early detection of a VHO when transitioning out of a building, which will give the handset enough time to connect to the cellular network before loosing its WLAN link. A trigger node is a very simple IEEE 802.11 device that merely transmits beacons and is placed at the building exits. It provides no coverage extension or relaying and does not communicate with any other entity. We also provide some guidelines for the deployment of an indoor WLAN so that conventional signal threshold based HO triggering can be used with acceptable success probability.

This paper considers the design of secondary wireless mesh networks which use leased frequency channels. In a given geographic region, the available channels are individually priced and leased exclusively through a primary spectrum owner. The usage of each channel is also subject to published interference constraints so that the primary user is not adversely affected. When the network is designed and deployed, the secondary user would like to minimize the costs of using the required resources while satisfying its own traffic and interference requirements. This problem is formulated as a mixed integer optimization which gives the optimum deployment cost as a function of the secondary node positioning, routing, and frequency allocations. Because of the problem's complexity, the optimum result can only be found for small problem sizes. To accommodate more practical deployments, two algorithms are proposed and their performance is compared to solutions obtained from the optimization. The first algorithm is a greedy flow-based scheme (GFB) which iterates over the individual node flows based on solving a much simpler optimization at each step. The second algorithm (ILS) uses an iterated local search whose initial solution is based on constrained shortest path routing. Our results show that the proposed algorithms perform well for a variety of network scenarios.

Sensor nodes are often used in outdoor locations where they can be operated using solar power. When such a network is deployed, there are usually restrictions in the way that the nodes can be positioned, and this results in a node-dependent attenuation of the usable solar energy. This effect must be taken into account when placing the basestations used to communicate with the sensor nodes. In this paper we consider the minimum-cost placement of data collecting basestation nodes so that outage-free operation of the sensor nodes is obtained. This is done by minimizing the number of basestations required when taking into account the energy costs of sensor node traffic relaying. An optimization is first formulated which gives a lower bound on the number of basestations that are required. Because of the complexity of the problem, an algorithm is proposed which can be used to do placements for practical problem sizes. The algorithm uses the result from an iterated local search as a starting point, and then uses an energy aware local optimization to obtain feasible basestation placements. Results are presented which show that the algorithm performs well for a variety of network scenarios.

Vehicular ad-hoc networks (VANETs) will enable a wide variety of future inter-vehicle and vehicle-to-roadside applications. These services will span a large range of functionality, such as those supporting vehicular safety, to those used for best-effort roadside advertising. To support this wide range, the IEEE 802.11p standard defines seven communication channels, consisting of a single control channel for safety applications, and six service channels which can be used for other purposes. To allow a single radio interface to support both types of applications, the standard defines a channel coordination mechanism that allows the vehicular radio to alternately access the control and service channels. When this happens it is very important that safety messages are transmitted with high reliability and low latency. Using analytical models, this paper provides a performance evaluation of vehicular safety message delivery. Our results show that the mechanism defined in the standard can satisfy the needed latency requirements, but cannot satisfy the required reliability for safety message delivery.

Wireless local area networks (WLANs) are now being used in places where access point (AP) power saving would be very desirable. Although this is not currently possible, modifications to the IEEE 802.11 protocol have recently been proposed which would permit this functionality. A difficult problem that arises is to maintain good client power saving when AP power saving is introduced. This is especially true when carrying multiple real-time traffic flows such as H.263 video, where the payload size varies randomly over short time periods. In this paper, we first present protocol modifications for power saving quality-of-service (QoS) enabled access points (PSQAP). We then focus on the transmission of bursty real-time H.263 video over a PSQAP. A variety of mechanisms are proposed for this purpose, which result in various tradeoffs between station and PSQAP power saving performance. Analytical models and simulation experiments are used to assess the performance of the video scheduling algorithms. The best overall performance is obtained using a mechanism that combines a novel variant of the power save multi-poll (PSMP) protocol with a scheduling mechanism based on a discrete autoregressive video prediction model.

Wireless mesh nodes must often be upgraded so that the network can accommodate evolving user demands. When some of the nodes are operated using a sustainable solar energy source, these upgrades must take into account the cost of updating the node energy resource configurations. This is required so that the new network configuration can properly accommodate the updated energy workloads of the re-provisioned network. In this paper we study this problem in the context of sustainable energy mesh node provisioning costs. We derive a mixed integer linear programming (MILP) formulation which is used to optimize the costs of node resource upgrades. Using this result, a lower bound on the network upgrade cost is obtained. The paper then proposes the use of a genetic algorithm based methodology for determining practical cost-effective mesh node resource upgrading. Various examples are given using networks with random, mesh and tree topologies which show the value of the proposed mechanism. In particular we find that the genetic algorithm approach achieves results which are much better than those from an algorithm which uses local optimization. It also performs well compared to our derived lower bound.

Wireless LAN mesh networks are used to provide Wi-Fi access for temporary events. In this type of application it is sometimes necessary to operate some of the mesh nodes using an energy sustainable source, such as solar power. When the network is deployed, each mesh node is equipped with a solar panel and battery combination which is sufficient to prevent network outage using an assumed traffic design profile. During post-deployment network operation however, the actual traffic flows may be different from that for which the nodes were originally provisioned. To prevent node outage, the network must flow control the inputs, and this should be done in as fair a manner as possible. In this paper we propose a mechanism for achieving fair flow control on a per-flow basis. We first formulate a bound which achieves the best max-min fair flow control subject to eliminating network outage. This bound is non-causal in that it uses knowledge of future solar insolation and traffic flows to determine the optimum flow control. The bound motivates a proposed causal flow control algorithm whose operation uses prediction based on access to on-line historical weather data. Our results show that the proposed algorithm eliminates node outage and performs very well compared to the optimum flow control bound for a variety of network scenarios.

WLAN mesh networks are often installed to provide wireless coverage for temporary events. In these types of networks, the WLAN mesh nodes can sometimes be operated using an energy sustainable source such as solar power. Resource provisioning consists of pre-assigning each node with a solar panel and battery combination that is sufficient to prevent node outage for the duration of the deployment. This is done by assuming a temporal load profile for each node, which is then used to perform the assignment using historical solar insolation data for the desired deployment location. Unfortunately, this methodology cannot take into account the state dependencies which occur when the network uses energy aware routing, and therefore the system may be over-provisioned. In this paper we propose a methodology for WLAN mesh node resource assignment that incorporates energy aware routing into the assignment algorithm. The problem consists of determining a network-wide minimum cost resource assignment subject to satisfying the input load profile. A genetic algorithm (GA) has been developed for this purpose. Our results show the large resource savings that energy aware resource assignment can achieve when compared to that done using the conventional methodology. We also study the competitive ratio of both resource assignment schemes and show that for small traffic overloading, energy aware routing performs better than shortest path routing in networks which are provisioned using the proposed methodology.

Wireless mesh networks (WMN) must often be upgraded as usage demands evolve. This is usually done by adding gateways which serve to increase the backhaul capacity of the network. In this paper we study the problem of this type of capacity augmentation using free-space optical (FSO) backhaul links. A joint clustering and gateway placement problem is formulated which includes the strong rate-distance dependence of practical FSO links. The formulation incorporates the positions of existing wireline gateways and minimizes the number of additional hybrid-FSO/RF gateways which are needed to satisfy the new target capacity requirements. A genetic algorithm solution is proposed, and the performance of our algorithm is compared to an optimal solution generated using an integer linear programming (ILP) formulation. Various scenarios are considered which demonstrate the value of using FSO backhaul links to obtain post-deployment capacity upgrades in response to evolving user traffic.

WLAN mesh networks are often installed to provide wireless coverage for temporary events. In many of these cases, the WLAN mesh nodes can be operated using an energy sustainable source such as solar power. Node resource assignment consists of provisioning each node with a solar panel and battery combination that is sufficient to prevent node outage for the duration of the deployment. In this paper we consider this resource assignment problem with the objective of minimizing the total battery cost for a given energy source assignment. A methodology and algorithms for determining this resource assignment are first given. We then study the problem in the presence of shortest path and energy aware routing. To evaluate the quality of the resource assignments, we develop a linear programming formulation which gives lower bounds on the network resource assignment. Competitive ratios for different routing algorithms are then used, which demonstrates their effectiveness. We also include the case where some of the deployed nodes are designated in advance as having a continuous power source. Our results show the resource savings which are possible using the design algorithms and the potential resource assignment benefits of energy aware routing.

IEEE 802.11 is now being used in many situations where access point (AP) power saving would be highly desirable. Unfortunately, this is not possible since the existing standard requires that APs remain active at all times. In this paper, we present a framework for a power saving quality-of-service (QoS) enabled access point (PSQAP), intended for use in low power infrastructure applications. The proposed scheme introduces infrastructure based power saving while preserving the QoS requirements for delay and loss intolerant real-time applications. Using an extensive simulation study we have evaluated the integrated framework, which consists of a proposed energy efficient media access control (MAC) protocol and an adaptive connection admission control (CAC) scheme. Our results show that the power consumption at PSQAPs can be significantly reduced without violating any of the QoS requirements for real-time traffic streams. The effect on power saving at the stations is also reasonable and can be controlled via protocol specific parameters.

Hybrid WLAN mesh networks use a combination of nodes that are continuously powered and those that are powered using an energy sustainable source such as solar power. In this paper we consider the problem of cost-optimal placement of the energy sustainable nodes in these types of hybrid networks. We first introduce a cost model that takes into account the provisioning required to operate the solar/wind powered nodes subject to a desired node outage criterion. We then formulate the design problem as a Mixed Integer Quadratic Problem (MIQP). A branch and bound approach is used to obtain node positioning solutions and is compared with a proposed algorithm that uses optimum shortest path routes. Our results show that there is a significant improvement in cost that can be obtained using the proposed methodology and that the branch and bound approach achieves the optimum assignment for a variety of network examples.

WLAN VoIP capacity is known to be very low due to the effects of overheads at various protocol layers. An IEEE 802.11b access point (AP) operating at 11 Mbps for example, can support only about 12 G.711 voice connections with a 20 ms packetization interval. These effects can be mitigated by taking into account the available latency margin of the call and using it in the VoIP parameter selection. In this paper we propose the use of an adaptive voice packetization server (AVP-RTS) which splits the RTP VoIP connection into two legs. In this way each end of the call is negotiated separately and the server can allocate the available latency margin (and the ensuing capacity gain) asymmetrically across the call. We propose new algorithms for performing this capacity assignment and compare them to the conventional voice packetization scheme. Results from extensive simulations show that by using the AVP-RTS server we can significantly improve the multi-AP VoIP capacity for certain typical IEEE 802.11 situations.

Solar powered WLAN mesh nodes are assigned a solar panel and battery size based on power consumption profiles. If future loading exceeds the design target, then a node may not be able to achieve the outage performance for which it was configured. To prevent this from happening, forced power saving can be used to reduce node power consumption to acceptable levels. However, forced power saving generates a deficit in offered capacity which should be minimized as much as possible. In this paper we first formulate this as a non-linear control problem. An efficient linear programming approximation is then defined and solved based on an offline optimization where future solar insolation is known in advance. This provides a bound on the performance of any real control algorithm. We show that the LP solution is accurate in that it comes very close to achieving a no-control capacity deficit lower bound. A control algorithm is then proposed whose operation uses dynamic access to publicly available on-line meteorological data. The proposed approach uses this on-line data but could also benefit from on-line weather forecasting. Our results show that the proposed algorithm minimizes node outage and performs favorably compared to the offline and no-control lower bounds.

Solar powered WLAN infrastructure is a cost effective option in outdoor deployments where continuous power sources are not practical. In these nodes the cost of the solar panel and battery can be a significant fraction of the total, and therefore reducing access point power consumption is very important. In this type of network, peak bandwidth requirements may not be satisfied by a single access point radio, even though long term average bandwidth requirements may be very low. In this case multiple radio APs or overlapped AP coverage deployment is required to meet this peak demand. When this happens the long term power consumption of the nodes can be reduced by implementing shared dynamic power saving between the WLAN mesh nodes. In this paper we propose and evaluate two algorithms for efficiently activating the solar powered infrastructure when additional bandwidth is needed. The algorithms are designed to be compatible with the existing IEEE 802.11 standard and include conventional load balancing when more than one AP is active in a given coverage area. We demonstrate that the proposed algorithms can significantly reduce the power consumption of the shared solar powered infrastructure.

Seamless WLAN-to-cellular handover is often difficult to achieve, since WLAN coverage can often be lost very quickly. Recent results have shown that successful handover may require that the WLAN link be allowed to rate-adjust itself to very low values (e.g., 1-2 Mbps) before the vertical handover is completed. When this occurs the call temporarily occupies a WLAN bandwidth far higher than the value for which it was originally provisioned. This effect is referred to as the vertical handover bandwidth deficit problem. In this paper we consider the effects of the bandwidth deficit problem on system performance, and how the problem can be mitigated. It is shown that this bandwidth demand can result in significant vertical handover dropping due to a lack of bandwidth on the WLAN access point. A static bandwidth reservation scheme motivated by the classical cellular guard channel approach is first considered and is found to result in an unacceptable increase in the WLAN new call blocking rate. A novel transient bandwidth reservation scheme accompanied by a momentary forced handover mechanism is proposed to overcome the shortcomings of the static approach in multiple AP WLANs. Our presented results show that almost two orders of magnitude reduction in the vertical handover dropping rate can be achieved while maintaining an acceptable new call blocking rate at the WLAN AP.

In this paper, resource allocation and outage control are considered for solar-powered WLAN mesh networks. Solar-powered nodes are a very cost effective option in WLAN mesh deployments where continuous power sources are not practical. In such nodes, the cost of the solar panel and battery can be a significant fraction of the total and, therefore, reducing AP power consumption is very important. A solar panel/battery configuration methodology is introduced based on a proposed AP power-aware version of IEEE 802.11. Public meteorological data is used to provision each node based on an averaged offered capacity profile. Since a node is configured statistically, it is possible that future loading may result in nonzero outage even when negligible outage is the design target. Control algorithms are introduced which can improve node outage performance by sometimes introducing an access point capacity deficit. Results are presented which show the value of the proposed configuration methodology and show that the control algorithms can prevent outage even at high levels of excess loading.

Future mobile handsets will often be multi-mode and may include both wireless LAN (WLAN) and cellular air interfaces. When this type of handset roams in and out of WLAN coverage, connections must be transferred to the new network point of attachment. In order to support real-time wireless services, seamless vertical handoff is an essential requirement. In this paper we propose the use of ad hoc relaying during vertical handoff in hybrid WLAN/Cellular systems. The proposed method improves handoff algorithm behavior in terms of handoff dropping probability and other mobility performance measures. Both analytic models and simulation results support the effectiveness of the proposed method.

In this paper we consider vertical handoff for dualmode (DM) cellular/WLAN handsets. When the handset roams out of WLAN coverage, the DM's cellular interface is used to maintain the call by anchoring it through a PSTN gateway/PBX. Soft handoff can be achieved in this case if the gateway supports basic conference bridging, since a new leg of the call can be established to the conference bridge while the existing media stream path is active. Unfortunately this requires that all intraenterprise calls be routed through the gateway when the call is established. In this paper we consider conferenced dual-mode handoff and propose a much more scalable mechanism whereby active calls are handed off into the conference bridge just prior to the initiation of the vertical handoff. Results are presented which are taken from dual-mode handset simulations which characterize the scalability of the proposed mechanism.

Real-time vertical handover is an important capability for multimode WLAN/cellular handsets. In many cases however, seamless handover can be very difficult to achieve, since WLAN coverage may be lost long before a cellular call leg can be triggered and established. Worse-case handovers of this kind occur when mobile users walk from indoor building WLAN coverage to outdoors during voice connections. In this paper we report on a measurement-based study of WLAN-to-cellular handover. Our results are based on extensive IEEE 802.11 measurements that were made on the McMaster University campus during the summer of 2005. Our methodology involved traversing many indoor-to-outdoor paths for a large number of campus buildings and exits while monitoring multi-AP Wi-Fi coverage. The collected data was then processed to determine the probability of seamless handover using classical vertical handover algorithms. The results presented give important insights into the difficulty of this problem, and relate to issues such as Wi-Fi deployment type, handover triggering, and Wi-Fi link loss threshold. The results provided enable handset designers and WLAN administrators to better understand the sensitivity of vertical handover performance to these parameters and how they can be optimized

In the past decade, there has been a huge proliferation of wireless local area networks (WLANs) based on the IEEE 802.11 WLAN standard. As 802.11 connectivity becomes more ubiquitous, multihop communications will be increasingly used for access point range extension and coverage enhancement. In this paper, we present a design for an IEEE 802. 11 -based power saving access point (PSAP), intended for use in multihop battery and solar/battery powered applications. These types of APs have many practical applications and can be deployed very quickly and inexpensively to provide coverage enhancement in situations such as campuses, building complexes, and fast deployment scenarios. Unlike conventional wired access points, in this type of system, power saving on the AP itself is an important objective. A key design constraint is that the proposed PSAP be backward compatible to a wide range of IEEE 802.11 functionality and existing wired access points. In this paper, we introduce the protocols required to achieve this compatibility, show the constraints imposed by this restriction, and present performance results for the proposed system.

In this paper, we consider the capacity of cellular code division multiple access (CDMA) when there is out-of-band ad hoc traffic relaying. The mobile stations (MSs) are dual-mode, having both ad hoc and cellular CDMA radios. An active MS is free to choose any available relay station (RS) within its ad hoc radio coverage area for dual-hop communication with the CDMA base station (BS). Communications between the RSs and the MSs use bandwidth which is available to the ad hoc radio and does not consume the CDMA capacity. Using this mechanism, CDIVIA interference can be reduced by dynamically selecting RSs which have more favorable CDMA link characteristics. Several relay station selection criteria are considered, namely, ad hoc relaying with low relative interference (ARRI), with best link gain (ARLG), and with shortest distance (ARSD). The relay station selection protocols are compatible with existing wireless local area network (WLAN) standards such as IEEE 802.11. An analytic model is used to compute the effects on uplink and downlink CDMA capacities when out-of-band relaying is added. The results show that very significant capacity improvements are possible by using these criteria compared with conventional CDMA with hard or soft handoff. Ad hoc relaying which dynamically tracks CDMA link quality can achieve greater capacity improvements than that using a distance-based relay station selection. Relaying, which considers both signal and interference conditions, achieves better capacity than that based on signal link quality alone.

Wireless LAN-to-cellular vertical handoff involves time consuming procedures that may significantly disrupt real-time communication. This situation is compounded by the fact that WLAN coverage may sometimes be lost very abruptly and without warning. In this paper we propose and investigate the use of a vertical handoff support node (VHSN), which is attached locally to the wired LAN hotspot infrastructure. Unlike proxy forwarding and wireless multi-hop schemes, the VHSN does not extend wireless coverage or perform infrastructure-based packet forwarding. The VHSN also does not communicate directly with any mobile station. Instead the VHSN functions as both an (Ethernet) LAN and cellular end station. When abrupt loss of WLAN coverage occurs, the VHSN quickly intercepts and redirects the media flow through the local cellular basestation using its cellular end station attachment. This action can quickly recover the connection before the remaining vertical handoff is executed. There are a number of key advantages that this mechanism has over existing forwarding/relaying techniques. Results will be presented which show the performance improvements, which are possible using this approach

No abstract available.

ESS mesh networks will soon provide extensive coverage deployment for outdoor WLAN hotzones. In these types of networks, solar powered mesh access points (MAPs) and mesh points (MPs) can be used to provide tether-less infrastructure extension in an inexpensive and flexible manner. Unlike conventional WLAN networks, power saving on the access points (APs) is an important feature which can result in significantly reduced solar-powered AP node costs. Unfortunately, when infrastructure nodes conserve power, they become less responsive and this can significantly lengthen the hand off process. In this paper we propose and analyze different algorithms for mitigating these effects, so that real-time handoff can occur as fast as possible. Three different algorithms are proposed for dynamically activating the power saving infrastructure. The proposed algorithms are tested and compared to conventional handoff algorithms via simulation and analysis

This paper proposes a practical joint power allocation and scheduling scheme for medium access control (MAC) layer design in ultra-wideband (UWB) networks. The scheme increases system spectral efficiency and reduces power consumption by fully considering the properties of the UWB, such as its capacity in supporting parallel transmission and providing accurate positioning, and its stringent constraint on computational complexity. Practical implementations of the proposed scheme are achieved by introducing a margin based power allocation scheme and an exclusive region based scheduling scheme. The margin based power allocation scheme is carried out based on each link's own information, and is simple to implement, while the exclusive region based scheduling scheme takes into account the interaction among different links. Simulation results show that the proposed power allocation and scheduling schemes exhibit good performance in terms of the average number of slots per frame and the power consumption reduction.

IEEE 802.11 access point (AP) power saving is an important feature for solar/battery powered ESS mesh networks. In this paper we propose a media access control (MAC) protocol for power-aware multihop infrastructure, based on extensions to IEEE 802.11(e). A power saving mesh AP includes a network allocation map (NAM) in its beacon broadcasts which specifies its temporal operation, and thus coordinates traffic delivery and power saving at both end stations and at the AP. A simple algorithm is proposed for dynamically updating channel activities so that best-effort traffic load changes can be quickly accommodated. Simulation and analytic results are presented for the proposed system which show that the proposed protocol and algorithm can achieve good AP power consumption without any significant end station performance degradation

In this paper we study admission control in IEEE 802.11-based ESS mesh networks. An analytical model is developed for studying the mesh network capacity. Based on this, a distributed connection admission control (CAC) scheme is proposed, which incorporates load balancing in selecting a mesh path for a new connection. Our results show that connection level performance, including both average number of connections in the network and connection blocking probability, can be greatly improved using the proposed admission control compared to other admission control schemes.

Multi-constraint quality-of-service routing becomes increasingly important as the Internet evolves to support real-time services. It is well known however, that optimum multi-constraint QoS routing is computationally complex, and for this reason various heuristics have been proposed for routing in practical situations. Among these methods, those that use a single mixed metric are the most popular. Although mixed metric routing discards potentially useful information, this is compensated for by the significantly reduced complexity. Exploiting this tradeoff is becoming increasingly important where low complexity designs are desired, such as in battery operated wireless applications. In this paper, a novel single mixed metric multi-constraint routing algorithm is introduced. The proposed technique has similar complexity compared with existing low complexity methods. Simulation results are presented which show that it can obtain better performance than comparable techniques in terms of generating feasible multi-constraint QoS routes.

In the past decade there has been a huge proliferation of wireless local area networks (WLANs) based on the IEEE 802.11 WLAN standard. Unfortunately, there is currently a large variety of commercial installations already deployed using APs with poor capabilities for supporting real-time QoS and power saving. This presents a problem for voice handset manufacturers and network operators. In this paper we consider the use of a power saving real-time gateway (i.e., POWSAR gateway). The gateway is installed on the wired infrastructure and filters all traffic towards a set of existing APs. A single gateway can support a large number of APs since infrastructure data rates are typically much higher than those of the air interface. We first consider the worse-case situation where the APs involved support neither station power saving nor packet QoS. Following this, performance comparisons are presented for a WiFi-compatible power saving solution and the POWSAR gateway approach. Results are presented which suggest that a POWSAR gateway has the potential for greatly improving power saving and real-time performance in certain legacy WLAN situations.

In this paper we consider the capacity of a cellular CDMA system when there is out-of-band ad hoc traffic relaying. In the system studied, the mobile stations (MS) are dual-mode, having both ad hoc and cellular CDMA radios. An active MS is free to choose any available relay station (RS) within its ad hoc radio coverage area for communication with the CDMA base station (BS). A relay station selection protocol, referred to as ad hoc relaying with best link gain (ARLG), is proposed which dynamically tracks the CDMA link quality when making this determination. An analytic model is used to compute the effects on uplink and downlink CDMA capacities when using the proposed protocol. The results show that very significant capacity improvements are possible by using this algorithm. Multihop relaying of this kind can be used to improve the performance of a cellular system., or to improve the performance in CDMA hotspot cells.

Future mobile handsets will often be multi-mode, containing both wireless LAN (WLAN) and cellular air interfaces. Vertical handoffs will commonly be used to pass voice calls to a cellular network when the user roams outside of WLAN radio coverage. Unfortunately, the transition from WLAN hotspot to cellular coverage is often very abrupt and leads to unacceptable call dropping rates. In this paper we propose and investigate the use of explicit WLAN/cellular handoff triggering. A simple Wi-Fi handoff trigger node (HTN) can be installed in the WLAN/cellular transition region, and generates link layer triggers which cause the initiation of the vertical handoff process. A key function provided by the HTN is to significantly reduce the call dropping rate even when there is very little collaboration between the cellular and WLAN hotspot providers. Results are presented which show that the call dropping probability can be dramatically reduced by the use of a handoff trigger node.

In this paper a media access control protocol is proposed for ad hoc network stations with adaptive antenna arrays. The protocol is based on the IEEE 802.11 distributed coordination function (UCF) and uses omnidirectional RTS/CTS exchanges to initiate data packet transmissions. Unlike previous directional antenna MAC protocols, the proposed protocol accommodates the active nulling of co-channel interferers that may arise during the course of ongoing transmissions. This is done using a three-way handshake where neighboring stations cooperate during link activations thus allowing the active receiver to dynamically null potential future interfering packet transmissions. The protocol uses omnidirectional transmission combined with beamformed reception, and is referred to as selective CSMA with cooperative nulling (SCSMA/CN). Packet type identification is used to enable/disable carrier sensing based upon whether or not existing transmissions are protected by antenna beamforming. Simulation results are presented which show that the proposed protocol can achieve higher capacity than previous comparable MAC protocols. The results also include the effects of transmit power control on system performance.

IEEE 802.11 WLANs are increasingly used to support real-time services such as voice and video. Reliable portable operation, however, is often difficult due to factors such as imperfect customer access point (AP) installation, unpredictable WLAN coverage, and unexpected co-channel interferers. In this paper we propose and investigate the use of IEEE 802.11 ad hoc-assisted handoff (AAHO). In AAHO, a single additional ad hoc hop may he used by a mobile station (MS) to obtain the range extension or channel quality needed to maintain its real-time voice connection. There are three versions of IEEE 802.11 AAHO. In backward ad hoc assisted handoff (BAAHO), the additional hop uses a relay station which already has an IEEE 802.11 association with the AP that the MS is using. In forward ad hoc assisted handoff (FAAHO) the additional hop uses a relay station whose AP is different from the one that the MS is currently using. Hybrid ad hoc assisted handoff (HAAHO) is a combination of the two and allows an MS to perform either BAAHO or FAAHO. The proposed AAHO designs are backward compatible, and thus can be implemented as a transparent overlay across existing IEEE 802.11 infrastructure deployments. Performance results show that AAHO can greatly improve performance in many practical situations.

Bluetooth is currently being integrated into many different types of cellphones and other portable devices. Future access networks can use this connectivity to provide real-time voice services in public places such as airports, convention centers and shopping malls. To obtain good statistical performance a large number of potential Bluetooth voice links would he provided throughout the desired coverage area. In the results presented we show that Bluetooth SCO voice links are inadequate for this purpose. Unfortunately, when coverage is such that significant Bluetooth base station and link sharing is possible. SCO packet loss rates are unacceptable. The alternative is to operate such a network using voice over Bluetooth ACL links (VoACL). and a simple VoACL scheme is proposed and investigated. A finite windowed loss rate model is also proposed and is used to characterize these designs. Analytic and simulation models show that VoACL can result in acceptable voice packet loss performance compared with SCO voice designs and that the call blocking rate is about the same between the ACL and SCU systems.

In the past decade there has been a huge proliferation of wireless local area networks (WLANs) based on the IEEE 802.11 WLAN standard. As 802.11 connectivity becomes more ubiquitous, multi-hop communications is increasingly used for range extension and coverage enhancement purposes. In this paper we present a design for an IEEE 802.11-based power saving access point (PSAP), intended for use in multi-hop battery and solar/battery powered applications. These types of APs have many practical applications and can be deployed very quickly and inexpensively to provide coverage enhancement in situations such as campuses, building complexes and fast deployment scenarios. Unlike conventional wired access points, in this type of system power saving on the AP itself is an important objective. A key design constraint is that the proposed PSAP be backward compatible to a wide range of legacy IEEE 802.11 end stations and existing wired access points. In this paper we describe the protocols required to achieve this compatibility, show the constraints imposed by this restriction, and present performance results for the proposed system.

In this paper we consider the capacity improvements in a cellular CDMA hotspot with out-of-band ad hoc traffic relaying. Two different multihop relaying options are compared, and an analytic model is used to compute the effects on CDMA uplink and downlink capacities. The results show that significant capacity improvements are possible using ad hoc relaying, but these are dependent upon the ad hoc to cellular coverage ratio and other parameters. It is also shown that in some situations ad hoc relaying should be used to shrink the cells in question, but in other cases it should be used to shed traffic from the hotspot cell. The results give a useful indication of the potential role of ad hoc relaying in CDMA hotspot traffic situations.

Smart antennas have been studied extensively for use in cellular radio base station applications. Recently however, low cost array technologies have suggested that adaptive antennas may soon be cost effective for mobile ad hoc networks. In this paper we consider the potential use of adaptive antenna arrays in networks using protocols based on the IEEE 802.11 distributed coordination function (DCF). In the system under study, omnidirectional RTS/CTS exchanges are used to initiate array-mode data packet transmissions. Several variations on the basic protocol are considered. When two stations communicate using their antenna arrays, the ensuing gain across the link can be very large. In many cases the transmit power can be significantly reduced while still maintaining a sufficient link margin. We show that this reduction in power is a key factor in improving the capacity of an ad hoc network. Results are presented for various parameters which show how the capacity of the system scales with the size of the system. Significant capacity improvements are possible compared with a network using conventional IEEE 802.11 protocols. In our simulations a relatively inexpensive circular antenna array configuration is used with a fairly modest number of elements.

Scheduled rendezvous is a common technique for reducing power consumption in embedded wireless networks. In scheduled rendezvous, nodes remain in a low power sleep mode whenever possible and periodically awaken to rendezvous with other nodes. Unfortunately, in many embedded wireless systems node power consumption may be unnecessarily dominated by this rendezvous activity. We study the use of radio frequency identification (RFED) technology, as a low power wakeup mechanism for embedded radio networks. RFED radios are very low cost and can currently be operated at power consumptions of over three orders of magnitude lower than that of typical commercial radios operating in the Mbps range. We first compare the regions of operation where RFED wakeup and scheduled rendezvous are preferred. A protocol is proposed which allows the basestation to block transmissions that may interfere with the wakeup process. In addition, a hybrid low power rendezvous wakeup protocol is proposed which attains very low power consumption. We find that in low utilization situations where a high level of responsiveness is needed, low power wakeup can achieve much lower levels of power consumption than scheduled rendezvous. The results also suggest that adaptive schemes are possible where the mode used is selected dynamically by the basestation.

In the near future Bluetooth will be embedded into many different types of mobile and portable devices. Initially this will provide simple wire replacement functions for applications such as hands-free headsets for cellular radio. However, this will also enable future picocellular services such as real-time voice and data. There are many possible applications for this such as telephone lounges in airports, shopping malls and other public places. We consider several Bluetooth-based telephony basestation (BS) designs. Since the number of SCO links per Bluetooth node is very limited, the designs consider the use of multiple overlapping Bluetooth basestations/chips. The first scheme is a direct implementation of the telephony profile where the Bluetooth basestations operate independently, without any coordination. When a mobile comes within range of the system, it associates with a basestation using the normal inquiry/page process. The second scheme, BBSM (Bluetooth basestation with migration), reduces the probability of blocking by having mobile nodes re-associate with available basestations when their current basestation is about to become blocked by SCO links. This improves the performance of the system from a blocking standpoint, but can be very spectrally wasteful. The third design, BBSS (Bluetooth basestation with standby), further improves blocking performance and decreases the wasteful effects of "node migration storms" which can occur in BBSM. We also include results for a design which uses ACL-based voice links. This scheme gives the best performance but has the disadvantage that more complex vocoding is required.

We introduce and study the use of dynamic slot allocation (DSA) in packet-switched space-division-multiple-access (SDMA) systems. In conventional SDMA, a smart antenna is used at the basestation to simultaneously communicate with multiple stations on the same frequency channel. When dynamic slot allocation is added, the basestation uses uplink channel measurements to intelligently construct future SDMA/TDMA frames. It is shown that under a simple minimum signal-to-interference-plus-noise ratio (SINR) constraint, the problem of performing optimal dynamic slot allocation is NP-complete. Heuristic slot allocation algorithms are introduced which are capable of greatly increasing SDMA/TDMA frame capacity compared with a random allocation of stations. The paper uses both theoretical results and measured data from an experimental testbed to characterize the performance of dynamic slot allocation. The experimental system operates at a carrier frequency of 1.86 GHz and uses an eight-element circular antenna array. It is demonstrated that significant increases in system capacity are possible using DSA in the indoor situations that were tested. Dynamic slot allocation requires the channel to be essentially constant from the time that channel measurements are made until the SDMA/TDMA frame is transmitted. We also present channel measurements which show the effects of channel time coherence in the presence of indoor pedestrian movement. This and other results we have taken suggest that dynamic slot allocation is possible at the frequency considered, provided turnaround times are in the low-to-mid tens of milliseconds.

In the future, wireless networking will be embedded into a wide variety of common, everyday objects. In many embedded networking situations, the communicating nodes will be very small and battery powered. For this reason, it is crucial that power consumption is as low as possible. A technique for reducing power consumption is to place nodes into a sleep mode whenever possible, and have them occasionally awaken to interact with other nodes. This type of action is referred to as a node rendezvous, and can be used in a variety of different ways. We consider power-efficient service rendezvous in embedded wireless networks with external triggering. We first define two basic rendezvous mechanisms, namely, server beaconing and client beaconing. We show that server beaconing is preferred when the client arrival rate is below a parameter dependent threshold. Above this level, the use of client beaconing results in lower power consumption. We also consider a hybrid technique whereby server nodes independently select the beaconing mode so that the total power consumption is reduced over a wide range of system parameter values. The operation of the client nodes is transparent to this selection. We also introduce the use of adaptive server beaconing. In a static server beaconing system, the optimum beaconing rate is an increasing function of the client loading level. It is shown that by adapting the server beacon rate in an intelligent way, the total power consumption can be greatly reduced over a large range of traffic loading conditions. A very simple method is introduced for performing this adaptation. Several other innovations are discussed which can be used to reduce power consumption in embedded networks. We investigate the use of an AC mains-powered rendezvous server for power reduction, and we discuss a distributed power reduction technique referred to as client beacon proxying. It is shown that by performing rendezvous in an intelligent manner, the total power consumption may be greatly reduced in many situations.

Parasitic antennas are much lower in cost and complexity than conventional smart antennas. For this reason, they may be considered for use at the portable station. In this paper we study the capacity of a space-division-multiple-access (SDMA) system when n-element switched parasitic antenna arrays (SPAA) are used for this purpose. Dynamic slot allocation (DSA) is used with a conventional smart antenna at the basestation. We first present analytic and simulation results which suggest the improvements in static capacity performance possible using this approach. Results show that the system capacity can be significantly improved with a small number of parasitic elements. We then then present results using measurements taken at McMaster University using an 8-element circular basestation antenna array and a 4-element switched-parasitic antenna array. The basestation array was used to collect spatial channel soundings in various indoor locations. We also propose several dynamic TDMA/SDMA slot allocation algorithms, which vary in their complexity and achieved performance. It is shown that significant improvements in capacity are possible using the proposed technique.

Many LAN designs have been considered using passive star and passively tapped ring and bus architectures. Similar networks can also be designed using active wavelength-selective coupling devices such as those based on acoustooptics. A major advantage of actively coupled designs is that functions such as station slot synchronization are greatly simplified. In this paper, we consider the use of active couplers as station taps in networks that support packet-switched modes of operation. When used for this purpose, a major source of complexity results from the fact that at a given time, an unknown number of stations may be inserted into a particular wavelength-division multiplexing bus. For this reason, global slot-timing information cannot be derived from any one particular channel. As a result, when conventional protocols are used, the system may suffer from "retuning collision", where a station destroys transit packets on other channels when the coupler is inadvertently retuned. We investigate protocols that can avoid this problem. In the simplest protocol, the overhead drastically restrict the range of physical parameters over which efficient operation can be achieved. The more sophisticated ones significantly extend this range so that metropolitan coverage is possible at reasonable data rates. In addition, we consider the use of active station taps in multichannel dual-bus networks. Capacity, delay, and power models are also derived, and comparisons are made with previous systems including passively tapped networks.

We consider the capacity performance of several slotted ALOHA protocols adapted for smart antenna SDMA operation. We assume that a set of portable stations share a single radio link with a basestation which is equipped with a smart antenna operating in a multi-beam SDMA mode. The system uses time division duplexing so that the uplink and downlink spatial channels are highly correlated. Versions of the protocols are considered where initial station access occurs in the data slots directly, and when a minislotted reservation channel is used. Both multi-beam and single-beam operation is considered in the reservation minislots. In all cases, we assume that optimal SINR beamforming is used when assigning stations to transmission slots. In the results shown, we optimize the design of each system to maximize the capacity achieved. The comparisons thus show the relative tradeoffs between capacity and complexity possible in these systems. In all cases considered, multibeam operation in both reservation minislots and data slots can achieve the highest capacity. However, we find that when operating under low SNR, and especially for long packet lengths, only very marginal improvements in capacity are achieved. The same observation is true under higher SNRs, but the advantage of multibeam reservation is improved somewhat. This is important since operating the system with multibeam minislot contention is expected to be highly complex, due to the dynamic acquisition which must take place. We also find that when packet lengths are in the ATM cell size range, there is little or no capacity advantage in using a single-beam reservation protocol over multibeam S-ALOHA. However, in the latter case, dynamic acquisition of multiple transmissions is needed.

In this paper we consider a set of portable stations which communicate with a base station equipped with a smart antenna operating in multibeam packet-switched SDMA mode. We assume that the system operates using time division duplexing (TDD) and focus on the problem of access to the stations by the base station in the forward link direction. A polling protocol is used which permits efficient access in this type of system. The operation of the protocol is unique in that it permits dynamic slot allocation and accommodates variations in channel time coherence. In the protocol, dynamic slot assignment is integrated into the forward link beam scheduling. The results show the improvements in capacity which are possible in such systems and give insight into the degradation in protocol performance which occurs when channel coherence times decrease. We find that very large improvements in capacity are possible, especially under harsh channel conditions. We also investigate various base station queueing issues in this type of system. It is shown that care must be taken in how buffering is performed so that blocking effects do not unnecessarily degrade the forward link capacity.

Researchers have recently considered the use of smart antennas in various packet-switched data networks. Previously, a single-beam system was described which employs a smart antenna basestation, operating in carrier-sense (CSMA) mode. Performance improvements are obtained by having the antenna dynamically point pattern nulls in the direction of interfering stations, thus reducing the frequency of channel collisions. In this paper, we consider the reverse-link performance of stations accessing a smart antenna basestation using multibeam SDMA. A basic CSMA/SDMA protocol is first proposed for this type of system. Following this, we also present a CSMA/SDMA protocol which incorporates basestation/portable signalling which mitigates the effects of hidden stations. The performance of these systems is characterized and compared using analytical throughput and capacity models. It is shown that when hidden stations are present, the capacity performance of the more sophisticated protocol may be much higher than that of the basic version.

This paper introduces the multiaccess mesh (or multimesh) network. Stations are arranged in a two-dimensional (2-D) mesh in which each row and column functions as a conventional linear local-area network (LAN) or metropolitan-area network (MAN) subnetwork. Full connectivity is achieved by enabling stations to merge their row and column subnetworks, under the coordination of a merge control protocol. A two-dimensional token-passing protocol is considered, and a more complex protocol motivated by max-min fairness is also presented. Like conventional LANs and MANs, the multimesh requires no transit routing or store-and-forward buffering. The multimesh is a generalization of the token grid network. Using analysis and simulation, we study the capacity of multimeshes constructed of token rings and slotted rings, under uniform and nonuniform loads. A multimesh can support much higher throughput than conventional linear LAN and MAN networks with the same transmission hardware. Moreover, the multimesh capacity grows with the number of stations, We also present a healing mechanism that ensures full network connectivity regardless of the number of failed stations.

Future photonic LANs and MANs may be based upon single-hop architectures using wavelength division multiplexing and passive coupling. In such systems, stations access shared sets of channels using some combination of receiver or transmitter tunability. Due to the optical device limitations however, the number of available channels may not be as large as previously envisioned. As a result, spatial wavelength reuse may be required to achieve networks with an acceptable number of stations and performance. We present a single hop wavelength routed optical network architecture, referred to as the flat channel controller network (FCCN). The network is divided into a set of local optical clusters interconnected via a static wavelength router. Two architectural variations are examined. The first uses a distributed control scheme for signaling within each cluster and requires each station to have only a single fixed receiver and a single fast agile transmitter. The second uses a dedicated control channel within each cluster and requires each station to have an additional fixed receiver. Three packet switched media access protocols are examined, static TDMA, and two reservation protocols.

In future WDM local area networks, the number of available wavelengths may initially be fairly modest. As a result, spatial reuse is required in order to obtain designs which will support a reasonable number of stations. A dual-hop architecture is considered. The network is partitioned into two stages. In the first, the wavelength agility of the user stations is used to route packets from a given local optical network (LON) to a destination LON. When packets arrive at their destination LON, they are buffered and transmitted onto the required wavelength. There are a number of significant advantages to this arrangement. In addition, the proposed design takes advantage of increasingly available commercial ATM buffer/switch components. Several hybrid electro-optic designs are discussed. We propose electronic implementations for the buffering stage and also consider the "almost" all-optical approaches first introduced by Haas (1993). The performance of the proposed systems is considered using various traffic models. Simplified control strategies are also proposed and multiple wavelength sharing is used to decrease the number of required buffers.

Research in photonics is currently aimed at ways to exploit the enormous information-carrying capacity of optical fiber. Many networks based upon wavelength division multiplexing (WDM) have recently been proposed using passive star couplers. However, new advances in travelling-wave and doped-fiber amplifiers have sparked interest in multichannel ring and bus networks. A new network architecture is proposed which is applicable to both multichannel folded busses and rings. The motivation behind the designs is to simplify the user stations as much as possible, thus giving an economical implementation. As proposed by Janoska and Todd (see GLOBECOM'93, vol.1, p.481-487, 1993) this is accomplished through the use of a headend channel controller which assists in the operation of the networks.>

In the near future, networks based upon the IEEE 802.6 metropolitan area network standard will become widespread. Eventually, networks of this type will be possible using both conventional point-to-point fiber and new photonic implementations. In both cases, it is possible to decouple the physical and logical topologies of the network yielding a rearrangeable bus. This capability magnifies the benefits of a media access protocol with destination slot release. In this paper, a media access protocol is introduced which provides destination slot release at each station. The REQPASS Protocol is a way of achieving fair bandwidth allocation in the presence of network overload conditions. REQPASS combines the request protocol with a slot release mechanism which permits request erasures on the reverse bus. A novel analytic model is introduced which accurately computes the mean queueing delay for individual stations. The success of the model is attributed to the fact that in a network with slot reuse, traffic independence approximations are more reasonable.>

An overwhelming majority of local and metropolitan area network products (LANs and MANs) are based upon linear topologies such as buses and rings. Such networks are economical for high speed operation since the station interfaces are simple and require very little transit buffering. However because of their linear structure, the total throughput is restricted by the transmission rate of the media access channels. In the paper, a token grid network is introduced where media access is performed over a two-dimensional mesh. In the resulting system, each station is two-connected and has the same transmission hardware and small station latency as in a dual token ring. In the token grid however, the total system throughput may be many factors larger than that which is possible in a dual token ring. In a large /spl radic/N/spl timesspl radic/N network, the uniform load capacity is approximately /spl radic/N/2 times that of an N station dual token ring. In addition, the token grid can take advantage of communities-of-interest amongst the stations. It is possible to implement the system in such a way as to achieve robust operation in the presence of station and link failures.>

Local area networks (LANs) with a branching rooted-tree topology are considered. In these systems, the metropolitan area gateway (MAG) is responsible for coordinating the flow of traffic into and out of the local subnetworks. A traffic scheduling technique is proposed for this topology. The algorithm is motivated by a finite-horizon maximization of conditional channel cycle utilization, resulting in a zero/infinite scheduling window scheme. Improved mean delay performance is achieved over a much wider range of traffic conditions than for other known algorithms. In order to obtain this robust behaviour, the local media access algorithms are modified to interact with the dynamic scheduling scheme in the MAG.>

A token grid network in which media access is performed over a two-dimensional mesh is introduced. In the resulting system, each station is two-connected and has the same transmission hardware and small station latency as in a dual token ring. In the token grid, however, the total system throughput may be many factors larger than that which is possible in a dual token ring. This advantage increases with the normalized end-to-end propagation delay. In the results presented, the uniform load capacity of the token grid grows with the size of the network. In addition, the token grid can take advantage of communities-of-interest amongst the stations. It is possible to implement the system in such a way as to achieve robust operation in the presence of station and link failures.>

Traffic processing algorithms are introduced for SIGnet (slotted interconnected-grid network), which is intended for local and metropolitan area backbone communication networks using multichannel optical transmission media. The design is motivated by the development of inexpensive multichannel capabilities based on dense wavelength division multiplexing (WDM) and future coherent optical systems. In SIGnet, the virtual topology is piecewise regular and permits bandwidth allocation and network evolution which is much more easily accomplished than in previous designs. SIGnet employs deflection routing to accommodate nonisochronous traffic. However, a multilink grid topology provides a closer match to the actual physical topology in many networks. This work includes an introduction to the network design and presents results obtained concerning the traffic processing algorithms which have been investigated.>

The photonic bus network (PBNet) approach to the design of small backbone networks is considered. The basic building block of PBNets consist of a linear multihop network interconnected in a bidirectional bus virtual topology using point-to-point optical channels. The system is designed to exploit transmissive optical star technology employing multichannel coherent lightwave modulation, but a wavelength-division implementation is also possible. The NCounter Protocol is introduced as a way of achieving fair bandwidth allocation in the presence of network overload conditions. Due to the optical implementation, there is considerable flexibility in PBNet topological design and bandwidth deployment. New design algorithms are introduced for this purpose. Performance results show that substantial improvements in system operation are possible using the proposed design techniques. In addition, the concept of receiver allocation is introduced which permits simple performance evolution of fixed-channel PBNets.>

Traffic processing algorithms are discussed for the slotted interconnected-grid network (SIGnet). SIGnet is intended for use as a high-performance backbone in metropolitan and extended-metropolitan areas. The system is designed to exploit the use of existing wavelength division multiplexing and coherent lightwave technologies. When accommodating nonisochronous traffic classes, the virtual topology in SIGnet is piecewise regular. As a result, bandwidth allocation and network evolution are easily accomplished. The philosophy of the design is to drastically minimize the buffering and protocol requirements at the transmit nodes, thus giving a highly cost-effective implementation. The SIGnet architecture is introduced, and results are given for certain traffic processing algorithms which have been investigated. A two-stage analytic model is presented which allows for the calculation of both detailed link traffic flow rates and the mean queueing delay at individual nodes. The results indicate that in typical subnetworks, reasonable accuracy may be obtained over a wide range of parameter values using link independence assumptions.>

A novel gateway design (referred to as T-SWIFT) is presented for integrating the flow of voice streams into existing broadband cable systems. The interface between the integrated voice subnetwork and the cable system is realized by a metropolitan area gateway (MAG) which is implemented at the broadband cable head-end. In T-SWIFT, an intelligent scheduling algorithm in the MAG dynamically allocates channel bandwidth using a variation of the data switch-filtering and fixed-frame synchronous voice/data integration techniques introduced by the author (see IEEE J. Selected Areas in Commun. vol., SAC-5, no.9, p.1391-1402 (1987)). The MAG accomplishes this by coordinating the transmission of inbound and outbound voice talkspurts in an upwardly compatible fashion with respect to the existing CSMA/CD data stations. Thus previously installed stations require no modification. Results are presented which indicate that the T-SWIFT design performs significantly better than previous compatible voice/data integration methods.>

A method (referred to as I-SWIFT) is presented for integrating the flow of synchronous voice streams into existing broadband cable systems. The interface between the integrated voice subnetwork and the cable system is realized by a metropolitan area gateway (MAG) implemented at the broadband cable headend. In I-SWIFT, an intelligent scheduling algorithm in the MAG dynamically allocates channel bandwidth using modified data switch-filtering techniques. The MAG accomplishes this by establishing a fixed voice frame (with realignment) which is implemented in an upwardly compatible fashion with respect to the existing carrier-sense multiaccess communication with collision detection (CSMA/CD) data stations. Thus, previously installed stations require no modification. It is shown that for typical system design parameters, the I-SWIFT gateway approach can achieve much improved performance over previous compatible voice/data integration methods.>

A media access technique called MICON (Migratory Connection-Based Media Access) is presented for broadband local and metropolitan area networks. In the technique proposed, CSMA/CD (carrier-sense multiple access with collision detection) is combined with a dynamic channel assignment scheme applied to multichannel network architectures. By virtue of a controlled migration of users the channel selection scheme achieves dynamic load balancing in connection environments. The 1-persistent mode of MICON is presented. An analytic model is developed by incorporating an extension of S.S. Lam's (1980) assumption for single-channel CSMA/CD to the multichannel case. The throughput-delay performance predicted by the model is found to be in close agreement with the results obtained by simulating MICON for single-connection environments.>

In the future, metropolitan area networks (MAN's) will provide high bandwidth interconnection between local access networks in high density office, industrial, and residential settings. In these systems, the metropolitan area gateway (MAG) is responsible for coordinating the flow of traffic in and out of the metropolitan subnetwork. In certain environments, it is expected that the traffic will possess distinct characteristics. In this paper, a technique called SWIFT is proposed which efficiently schedules these traffic flows when the local access network is based upon broadband CATV-type cable technology. SWIFT satisfies the important constraint that it is compatible with existing CSMA/CD packet data network adapters which means that it may be implemented in previously installed systems. In this paper, a throughput model is given for the proposed technique. Also, an analytic model is given which approximates the mean remote delay when the traffic is moderately to heavily remote-bound. The performance results presented indicate that a system operating the SWIFT algorithm can achieve much reduced delays at higher throughput than would otherwise be possible.

The theoretical issues of scheduling for capacity allocation in multiple access networks using in-band and out-of-band signaling are addressed. The analysis is carried out under the hypothesis that the "scheduling epochs" consist of bandwidth-dependent and bandwidthindependent components. The ultimate limitation on channel capacity rests with the bandwidth-independent component. It is shown that over the range of practical interest, scheduling using a separate side channel is superior to in-band scheduling in that, under similar conditions, the former attains a higher usable channel capacity.