In recent years, the availability of open-source 5G stacks that support the use of Software-Defined Radios (SDRs) as Radio Frequency (RF)-frontends has significantly accelerated experimental 5G research. This has enabled researchers to deploy customized 5G networks and utilize them with both SDR-based and Commercial Off-The-Shelf (COTS) User Equipments (UEs) for various applications. However, SDRs, unlike commercial 5G Radio Units (RUs), are designed to support a wide range of frequencies and protocols, leading to limitations when used specifically for 5G deployments. These limitations include supported Sampling Rates (srates), inherent Local Oscillator (LO) leakages, and limited Transmit (Tx) and Receive (Rx) gains. In this work, we benchmark the throughput performance of 5G standalone networks using the srsRAN 5G stack, Open5GS core, and three SDRs from National Instruments (NI) (X310, N310, and B210) in an indoor Over-the-Air (OTA) environment at varying distances. Measured throughput is compared to the estimated theoretical maximum under identical configurations. Also, we demonstrate how srates and LO leakage affect OTA throughput, comparing results across the three SDR platforms. Additionally, we show that similar Received Signal Strength (RSS) can result in significantly different throughput due to LO leakage, correlating these effects with overall performance. We also provide the dataset of the measured OTA throughput and RSS values.

Software-defined cellular networks (SDCN) have been recently introduced to enable flexible cellular network design that facilitates fulfilling 5G design requirements. Placement of controllers within the SDCN plays a crucial role in optimizing its performance. In this paper, we study the controller placement problem in SDCN, considering the uncertainty in cellular user locations. Specifically, our contributions are as follows. First, we develop C3P2, a static joint stochastic controller placement and evolved node B (eNB)-controller assignment problem. The objective of C3P2is to minimize the number of controllers needed to control all eNBs, while ensuring that the response time to each eNB will exceed seconds with probability less than 1-β. Second, we develop CPPA, a joint stochastic controller placement and adaptive eNB-controller assignment problem. In contrast to C3P2, in CPPA the eNB-controller assignment adapts to variations in the eNB request rates, resulting from the variations in the cellular user locations. Finally, we use sample average approximation combined with various linearization techniques to solve and evaluate C3P2and CPPA under various system parameters. Our results demonstrate the advantages of (i) joint compared to sequential optimization, (ii) stochastic compared to deterministic optimization, and (iii) adaptive compared to static optimization.

Software-defined networking (SDN) abstracts and centralizes the network control functions in a software entity that runs on a server, known as SDN controller. The controller needs to respond to its controlled elements in a strictly timely manner, and the controller placement has a prominent effect on its response time. Originally, all SDN architectures assumed a physical wired connection between the SDN controller and its controlled elements, and the controller placement problem (CPP) has been only studied under such wired settings. Recently, novel SDN architectures have been proposed in which a direct wireless connection is assumed between the controller and its controlled elements. In this paper, we consider the 'wireless CPP,' when the link between the controller and the controlled element is wireless. Specifically, our contributions are as follows. First, we propose two joint controller placement and assignment formulations, assuming wired links between the controllers and their controlled elements; the first formulation considers an average response time constraint, whereas the second one considers a per-link response time constraint. Then, using chance- constrained stochastic programming (CCSP), we extend our formulation to the case when the links between the controllers and their controlled elements are wireless. Finally, we evaluate our joint placement and assignment schemes under various system parameters. Our results demonstrate the advantage of our joint scheme, in terms of reducing the required number of controllers, compared to a recent sequential assignment and placement scheme in the literature. They also show the ability of our CCSP-based scheme in probabilistically satisfying the controllers response time constraints.

In recent years, there has been great interest from the cellular service providers to use the unlicensed spectrum for their service offerings. On the other hand, existing unlicensed users in these bands (e.g., Wi-Fi in the 5-GHz band) have serious concern that such coexistence will jeopardize their service quality. Although there are some proposals on how to achieve coexistence, they are driven by the service providers and as such there remain many issues and skepticism. In this paper, we take a novel human-centric approach to understand coexistence between Wi-Fi and LTE by focusing on human satisfaction. Through mathematical modeling, problem formulation, and extensive simulations studies, we show that in terms of maximizing total human satisfaction function, there does not appear to be any advantage with the coexistence of unlicensed spectrum for Wi-Fi and LTE under static partitioning of unlicensed spectrum. This finding serves as a powerful counter argument to some LTE service providers' proposal to share the unlicensed spectrum with Wi-Fi through static partitioning. On the other hand, we find that there is a significant improvement in human satisfaction in coexistence between Wi-Fi and LTE under adaptive spectrum partitioning. Since adaptive spectrum partitioning may require a user to change its service provider whenever there is a change among the users, we propose a practical (semi-adaptive) algorithm for implementation without affecting existing users' service providers. Through performance evaluation, we show that the proposed semi-adaptive algorithm is highly competitive.

Underwater acoustic (UWA) networks are a key form of communications for human exploration and activities in the oceanographic space of the earth. A fundamental issue of UWA communications is large propagation delays due to water medium, which has posed a grand challenge in UWA network protocol design. Conventional wisdom of addressing this issue is to live with this disadvantage by inserting a guard interval to introduce immunity to propagation delays. Recent advances in interference alignment (IA) open up a new direction to address this issue and promise a great potential to improve network throughput by exploiting large propagation delays. In this paper, we investigate propagation delay-based IA (PD-IA) in multi-hop UWA networks. We first develop a set of simple constraints to characterize PD-IA feasible region at the physical layer. Based on the set of PD-IA constraints, we develop a distributed PD-IA scheduling algorithm to greedily maximize interference overlapping possibilities in a multi-hop UWA network. Simulation results show that the proposed PD-IA algorithm yields higher throughput than an idealized benchmark algorithm without propagation delays, indicating that large propagation delays are not adversarial but beneficial for network throughput performance.

There have been some rapid advances on the design of full duplex (FD) transceivers in recent years. Although the benefits of FD have been studied for single-hop wireless communications, its potential on throughput performance in a multi-hop wireless network remains unclear. As for multi-hop networks, a fundamental problem is to compute the achievable end-to-end throughput for one or multiple communication sessions. The goal of this paper is to offer some fundamental understanding on end-to-end throughput performance limits of FD in a multi-hop wireless network. We show that through a rigorous mathematical formulation, we can cast the multi-hop throughput performance problem into a formal optimization problem. Through numerical results, we show that in many cases, the end-to-end session throughput in a FD network can exceed 2x of that in a half duplex (HD) network. Our finding can be explained by the much larger design space for scheduling that is offered by removing HD constraints in throughput maximization problem. The results in this paper offer some new understandings on the potential benefits of FD for end-to-end session throughput in a multi-hop wireless network.

Existing spectrum sharing paradigms have set clear boundaries between the primary and secondary networks. There is either no or very limited node-level cooperation between the primary and secondary networks. In this paper, we develop a new and bold spectrum-sharing paradigm beyond the state of the art for future wireless networks. We explore network cooperation as a new dimension for spectrum sharing between the primary and secondary users. Such network cooperation can be defined as a set of policies under which different degrees of cooperation are to be achieved. The benefits of this paradigm are numerous, as they allow integrating resources from two networks. There are many possible node-level cooperation policies that one can employ under this paradigm. For the purpose of performance study, we consider a specific policy called United cooperation of Primary and Secondary (UPS) networks. UPS allows a complete cooperation between the primary and secondary networks at the node level to relay each other's traffic. As a case study, we consider a problem with the goal of supporting the rate requirement of the primary network traffic while maximizing the throughput of the secondary sessions. For this problem, we develop an optimization model and formulate a combinatorial optimization problem. We also develop an approximation solution based on a piece-wise linearization technique. Simulation results show that UPS offers significantly better throughput performance than that under the interweave paradigm.

Network-coded cooperative communications (NC-CC) refers to the use of network coding (NC) in cooperative communications (CC). Prior studies have shown that NC has the potential to improve the performance of CC when there are multiple sessions in the wireless network. These studies were done for the case when multiple sessions are sharing a single relay node. However, how NC-CC behaves when multiple relay nodes are employed remains an open problem. In this paper, we explore this problem by analyzing the achievable rate of each session in this setting. We develop closed form formulas for the mutual information and the achievable data rate for each session. We show that prior results for a single relay is a special case of our result. Based on these findings, we then study a network optimization problem that requires joint optimization of session grouping, relay node grouping, and matching of session/relay groups. We show that this problem is NP-hard, and present a polynomial time heuristic algorithm to solve this problem. Using simulation results, we show this algorithm is highly competitive and can produce results that are near to optimality.

Interference alignment (IA) is a powerful technique to handle interference in wireless networks. Since its inception, IA has become a central research theme in the wireless communications community. Due to its intrinsic nature of being a physical layer technique, IA has been mainly studied for point-to-point or single-hop scenario. There is a lack of research of IA from a networking perspective in the context of multi-hop wireless networks. The goal of this paper is to make such an advance by bringing IA technique to multi-hop MIMO networks. We develop an IA model consisting of a set of constraints at a transmitter and a receiver that can be used to determine IA for a subset of interfering streams. We further prove the feasibility of this IA model by showing that a DoF vector can be supported free of interference at the physical layer as long as it satisfies the constraints in our IA model. Based on the proposed IA model, we develop an IA design space for a multi-hop MIMO network. To study how IA performs in a multi-hop MIMO network, we compare the performance of a network throughput optimization problem based on our developed IA design space against the same problem when IA is not employed. Simulation results show that the use of IA can significantly decrease the DoF consumption for IC, thereby improving network throughput.

Recently, a new MIMO degree-of-freedom (DoF) model was proposed to allocate DoF resources for spatial multiplexing (SM) and interference cancellation (IC) in a multi-hop network. Although this DoF model promises many benefits, it hinges upon a global node ordering to keep track of IC responsibilities among all the nodes. An open question about this model is whether its global ordering property can be achieved among the nodes in the network through distributed operations. In this paper, we explore this question by studying DoF scheduling in a multi-hop MIMO network, with the objective of maximizing the minimum throughput among a set of sessions. We propose an efficient DoF scheduling algorithm to solve it and show that our algorithm only requires local operations. We prove that the resulting DoF scheduling solution is globally feasible and show that there exists a corresponding feasible global node ordering for IC, albeit such global ordering is implicit. Simulation results show that the solution values obtained by our algorithm are relatively close to the upper bound values computed by CPLEX solver, thereby indicating that our algorithm is highly competitive.

The classical approach to interference management in wireless medium access is based on avoidance. Recently, there is a growing interest in exploiting interference (rather than avoiding it) to increase network throughput. This was made possible by a number of advances at the physical layer. In particular, the so-called successive interference cancellation (SIC) scheme appears very promising, due to its ability to enable concurrent receptions from multiple transmitters as well as interference rejection. Although SIC has been extensively studied as a physical layer technology, its research and advances in the context of multi-hop wireless network remain limited. In this paper, we aim to close this gap by offering a systematic study of SIC in a multi-hop wireless network. After gaining a fundamental understanding of SIC's capability and limitation, we propose a cross-layer optimization framework for SIC that incorporates variables at physical, link, and network layers. We use numerical results to affirm the validity of our optimization framework and give insights on how SIC behaves in a multi-hop wireless network.

Recently, degree-of-freedom (DoF)-based models have been widely used to study MIMO network performance. Existing DoF-based models differ in their interference cancellation (IC) behavior and many of them suffer from either loss of solution space or possible infeasible solutions. To overcome these limitations, a new DoF-based model, which employs an IC scheme based on node-ordering was proposed. In this paper, we apply this new DoF IC model to study a throughput maximization problem in a multihop MIMO network. The problem formulation involves joint consideration of flow routing and DoF allocation and falls in the form of a mixed-integer linear program (MILP). Our main contribution is an efficient polynomial time algorithm that offers a competitive solution to the MILP through a series of linear programs (LPs). The algorithm employs a sequential fixing framework to obtain an initial feasible solution and then improves the solution by exploiting: 1) the impact of node ordering on DoF consumption for IC at a node and 2) route diversity in the network. Simulation results show that the solutions obtained by our proposed algorithm are competitive and feasible.

The transparent coexistence (TC) paradigm allows simultaneous activation of the secondary users with the primary users as long as their interference to the primary users can be properly canceled. This paradigm has the potential to offer much more efficient spectrum sharing than the traditional interweave paradigm. In this paper, we design a distributed algorithm to achieve this paradigm for a secondary multi-hop network. For interference cancelation (IC), we employ MIMO at secondary nodes. We present a distributed iterative algorithm to maximize each secondary session's throughput while meeting all IC requirements under TC. By maintaining two local sets for each node, we can keep track of the node's IC responsibility. Although no explicit node ordering is maintained in our distributed algorithm, we prove that our distributed data structure at each node (with the use of two local sets) can be mapped to an explicit global node ordering for IC among all nodes in the network. This guarantees that each active node's degree-of-freedoms allocated for IC is feasible at the physical layer. Our algorithm is iterative in nature and all steps can be accomplished based on local information exchange among the neighboring nodes. We present the simulation results to show that the performance of our distributed algorithm is highly competitive when compared with an upper bound solution from the corresponding centralized problem.

Recent advances in MIMO degree-of-freedom (DoF)models allow us to study MIMO in a multi-hop network environment. On the other hand, successive interference cancellation (SIC) is a powerful physical layer technique used in multi-user detection. Based on the strengths and weaknesses of MIMO DoF and SIC, we propose a marriage between these two techniques so that DoF-based interference cancellation (IC) and SIC can help each other as follows: (i) SIC is exploited to decode multiple received signals to conserve DoF resources in IC, and (ii) DoFIC resolves the potential SINR barrier that SIC may encounter. In this paper, we develop the necessary mathematical models to realize the two ideas in a multi-hop wireless network. Together with scheduling and routing constraints, we develop a cross-layer optimization framework with joint DoF IC and SIC. By applying the framework on a throughput maximization problem, we find that SIC and DoF IC can indeed offer significant performance improvement by addressing each other's limitation.

This paper presents an analytical and simulation study of the efficiency of using cooperative communication for Dynamic Spectrum Access (DSA) in secondary infrastructure networks. The licensed and unlicensed network transmissions are modeled using a Discrete Time Markov Chain (DTMC). The secondary network spectrum occupancy and throughput are evaluated analytically and by simulation. A COoperative and COgnitive MAC protocol (CO2MAC) is developed to facilitate cooperative transmissions in secondary infrastructure networks. The results show significant performance enhancement for cooperative transmission over direct transmission, especially in crowded spectrum, where it achieves up to 80% enhancement in throughput compared to direct transmission.

Wireless energy transfer (WET) is a new technology that can be used to charge the batteries of sensor nodes without wires. Although wireless, WET does require a charging station to be brought to within reasonable range of a sensor node so that a good energy transfer efficiency can be achieved. On the other hand, it has been well recognized that data collection with a mobile base station has significant advantages over a static one. Given that a mobile platform is required for WET, a natural approach is to employ the same mobile platform to carry the base station for data collection. In this paper, we study the interesting problem of co-locating a wireless charger (for WET) and a mobile base station on the same mobile platform-the wireless charging vehicle (WCV). The WCV travels along a pre-planned path inside the sensor network. Our goal is to minimize energy consumption of the entire system while ensuring that 1) each sensor node is charged in time so that it will never run out of energy, and 2) all data collected from the sensor nodes are relayed to the mobile base station. We develop a mathematical model for this problem (OPT-t), which is time-dependent. Instead of solving OPT-t directly, we show that it is sufficient to study a special subproblem (OPT-s) which only involves space-dependent variables. Subsequently, we develop a provably near-optimal solution to OPT-s. Our results offer a solution on how to use a single mobile platform to address both WET and data collection in sensor networks.

The dominate spectrum sharing paradigm of today is interference avoidance, where a secondary network can use the spectrum only when such a use is not interfering with the primary network. However, with the advances of physical-layer technologies, the mindset of this paradigm is being challenged. This paper explores a new paradigm called “transparent coexistence” for spectrum sharing between primary and secondary nodes in a multihop network environment. Under this paradigm, the secondary network is allowed to use the same spectrum simultaneously with the primary network as long as their activities are “transparent” (or “invisible”) to the primary network. Such transparency is accomplished through a systematic interference cancelation (IC) by the secondary nodes without any impact on the primary network. Although such a paradigm has been studied in the information theory (IT) and communications (COMM) communities, it is not well understood in the wireless networking community, particularly for multihop networks. This paper offers an in-depth study of this paradigm in a multihop network environment and addresses issues such as scheduling (both in frequency channels and time slots) and IC (to/from primary network and within the secondary network). Through a rigorous modeling and formulation, problem formulation, solution development, and simulation results, we show that transparent coexistence paradigm offers significant improvement in terms of spectrum access and throughput performance as compared to the current prevailing interference avoidance paradigm.

Wireless energy transfer based on magnetic resonant coupling is a promising technology to replenish energy to a wireless sensor network (WSN). However, charging sensor nodes one at a time poses a serious scalability problem. Recent advances in magnetic resonant coupling show that multiple nodes can be charged at the same time. In this paper, we exploit this multi-node wireless energy transfer technology and investigate whether it is a scalable technology to address energy issues in a WSN. We consider a wireless charging vehicle (WCV) periodically traveling inside a WSN and charging sensor nodes wirelessly. Based on charging range of the WCV, we propose a cellular structure that partitions the two-dimensional plane into adjacent hexagonal cells. We pursue a formal optimization framework by jointly optimizing traveling path, flow routing, and charging time. By employing discretization and a novel Reformulation-Linearization Technique (RLT), we develop a provably near-optimal solution for any desired level of accuracy. Through numerical results, we demonstrate that our solution can indeed address the charging scalability problem in a WSN.

Transparent coexistence, also known as underlay, offers much more efficient spectrum sharing than traditional interweave coexistence paradigm. In a previous work, the transparent coexistence for a multi-hop secondary networks is studied. In this paper, we design a distributed solution to achieve this paradigm. In our design, we show how to increase the number of data streams iteratively while meeting constraints in the MIMO interference cancelation (IC) model and achieving transparent coexistence. All steps in our distributed algorithm can be accomplished based on local information exchange among the neighboring nodes. Our simulation results show that the performance of our distributed algorithm is highly competitive when compared to an upper bound solution for the centralized problem.

Wireless energy transfer is a promising technology to fundamentally address energy and lifetime problems in a wireless sensor network (WSN). On the other hand, it has been well recognized that a mobile base station has significant advantages over a static one. In this paper, we study the interesting problem of co-locating the mobile base station on the wireless charging vehicle (WCV). The goal is to minimize energy consumption of the entire system while ensuring none of the sensor nodes runs out of energy. We develop a mathematical model for this complex problem. Instead of studying the general problem formulation (OPT-t), which is time-dependent, we show that it is sufficient to study a special subproblem (OPT-s) which only involves space-dependent variables. Subsequently, we develop a provably near-optimal solution to OPT-s. The novelty of this research mainly resides in the development of several solution techniques to tackle a complex problem that is seemingly intractable at first glance. In addition to addressing a challenging and interesting problem in a WSN, we expect the techniques developed in this research can be applied to address other related networking problems involving time-dependent movement, flow routing, and energy consumption.

Interference alignment (IA) is a major advance in information theory. Despite its rapid advance in the information theory community, most results on IA remain point-to-point or single-hop and there is a lack of advance of IA in the context of multi-hop wireless networks. The goal of this paper is to make a concrete step toward advancing IA technique in multi-hop MIMO networks. We present an IA model consisting of a set of constraints at a transmitter and a receiver that can be used to determine a subset of interfering streams for IA. Based on this IA model, we develop an IA optimization framework for a multihop MIMO network. For performance evaluation, we compare the performance of a network throughput optimization problem under our proposed IA framework and the same problem when IA is not employed. Simulation results show that the use of IA can significantly decrease the DoF consumption for IC, thereby improving network throughput.

There has been a growing interest to employ the so-called degree-of-freedom (DoF) based models to study multihop MIMO networks. Existing DoF-based models differ in their interference cancelation (IC) behavior and suffer from either loss of solution space or possible infeasible solutions. Recently, a DoF model based on a novel node-ordering concept was proposed to overcome the limitations of the exiting DoF models. In this paper, we apply this new DoF model to study a throughput maximization problem in a multi-hop network. The problem formulation jointly considers half duplex, node ordering, DoF consumption constraints and flow routing and is in the form of a mixed integer linear program (MILP). Our main contribution is the development of an efficient polynomial time algorithm that offers a competitive solution to the MILP through a series of linear programs (LPs). The key idea in the algorithm is to explore (i) the impact of node ordering on DoF consumption for IC at a node, and (ii) route diversity in the network while ensuring DoF constraints are satisfied at each node throughout the iterations. Simulation results show that our solutions by the proposed algorithm are competitive and feasible.

Network throughput and energy consumption are two important performance metrics for a multihop wireless network. Current state-of-the-art research is limited to either maximizing throughput under some energy constraint or minimizing energy consumption while satisfying some throughput requirement. Although many of these prior efforts were able to offer some optimal solutions, there is still a critical need to have a systematic study on how to optimize both objectives simultaneously. In this paper, we take a multicriteria optimization approach to offer a systematic study on the relationship between the two performance objectives. To focus on throughput and energy performance, we simplify link layer scheduling by employing orthogonal channels among the links. We show that the solution to the multicriteria optimization problem characterizes the envelope of the entire throughput-energy region, i.e., the so-called optimal throughput-energy curve. We prove some important properties of the optimal throughput-energy curve. For case study, we consider both linear and nonlinear throughput functions. For the linear case, we characterize the optimal throughput-energy curve precisely through parametric analysis, while for the nonlinear case, we use a piecewise linear approximation to approximate the optimal throughput-energy curve with arbitrary accuracy. Our results offer important insights on exploiting the tradeoff between the two performance metrics.

There is a growing interest in exploiting interference (rather than avoiding it) to increase network throughput. In particular, the so-called successive interference cancellation (SIC) scheme appears very promising, due to its ability to enable concurrent receptions from multiple transmitters as well as interference rejection. Although SIC has been extensively studied as a physical layer technology, its research and advances in the context of multi-hop wireless network remain limited. In this paper, we try to answer the following fundamental questions. What are the limitations of SIC? How to overcome such limitations? How to optimize the interaction between SIC and interference avoidance? How to incorporate multiple layers (physical, link, and network) in an optimization framework? We find that SIC alone is not adequate to handle interference in a multi-hop wireless network, and advocate the use of joint SIC and interference avoidance. To optimize a joint scheme, we propose a cross-layer optimization framework that incorporates variables at physical, link, and network layers. This is the first work that combines successive interference cancellation and interference avoidance in multi-hop wireless network. We use numerical results to affirm the validity of our optimization framework and give insights on how SIC and interference avoidance can complement each other in an optimal manner.

Capacity scaling laws offer fundamental understanding on the trend of user throughput behavior when the network size increases. Since the seminal work of Gupta and Kumar, there have been active research efforts in developing capacity scaling laws for ad hoc networks under various advanced physical layer technologies. These efforts led to many custom-designed solutions, most of which were intellectually challenging and lacked universal properties that can be extended to address scaling laws of ad hoc networks with other physical layer technologies. In this paper, we present a set of simple yet powerful tool that can be applied to quickly determine the capacity scaling laws for various physical layer technologies under the protocol model. We prove the correctness of our proposed criteria and demonstrate their usage through a number of case studies, such as ad hoc networks with directional antenna, MIMO, multi-channel multi-radio, cognitive radio, and multiple packet reception. These simple criteria will serve as powerful tools to networking researchers to obtain throughput scaling laws of ad hoc networks under different physical layer technologies, particularly those to be developed in the future.

Wireless energy transfer based on magnetic resonant coupling is a promising technology to replenish energy to sensor nodes in a wireless sensor network (WSN). However, charging sensor node one at a time poses a serious scalability problem. Recent advances in magnetic resonant coupling shows that multiple nodes can be charged at the same time. In this paper, we exploit this multi-node wireless energy transfer technology to address energy issue in a WSN. We consider a wireless charging vehicle (WCV) periodically traveling inside a WSN and charging sensor nodes wirelessly. We propose a cellular structure that partitions the two-dimensional plane into adjacent hexagonal cells. The WCV visits these cells and charge sensor nodes from the center of a cell. We pursue a formal optimization framework by jointly optimizing traveling path, flow routing and charging time. By employing discretization and a novel Reformulation-Linearization Technique (RLT), we develop a provably near-optimal solution for any desired level of accuracy.

It has been shown that cooperative communications (CC) has the potential to significantly increase the capacity of wireless networks. However, most of the existing results are limited to single-hop wireless networks. To explore the behavior of CC in multi-hop wireless networks, we study a joint optimization problem of relay node assignment and flow routing for a group of sessions. We develop a mathematical model and propose a solution procedure based on the branch-and-bound framework augmented with cutting planes (BB-CP). We design several novel components to speed-up the computational time of BB-CP. Via numerical results, we show the potential rate gain that can be achieved by incorporating CC in multi-hop networks.

A major benefit of employing network coding (NC) in cooperative communications (CCs) is its ability to reduce time-slot overhead. Such approach is called network-coded CC (or NC-CC). Most of the existing works have mainly focused on exploiting this benefit without considering its potential adverse effect. In this paper, we show that NC may not always benefit CC. We substantiate this important finding with two important scenarios: employing analog network coding (ANC) in amplify-and-forward (AF) CC, and digital network coding (DNC) in decode-and-forward (DF) CC. For both scenarios, we introduce the important concept of network coding noise (NC noise). We analyze the origin of this noise via a careful study of signal aggregation at a relay node and signal extraction at a destination node. We derive a closed-form expression for NC noise at each destination node and show that the existence of NC noise could diminish the advantage of NC in CC. Our results shed new light on how to use NC in CC most effectively.

As streaming videos are becoming increasingly popular, it is important to understand the end-to-end streaming system and to develop effective algorithms for quality control. In this paper, we address the problem of rate control for streaming videos with a control-theoretic approach. Among the various control knobs, video bit rate is one of the most effective in the sense that it has a direct impact on the interaction between the video coder and network system. While increasing rate reduces the coder-induced distortion, it may also cause congestion at a bottleneck link. The packet loss due to congestion will, then, increase the distortion of the decoded video. We model end-to-end video steaming as a feedback control system, taking into account video codec and sequence characteristics, rate control, active queue management, and receiver feedback. We then develop effective proportional (P) controllers to stabilize the received video quality as well as the bottleneck link queue, for both homogeneous and heterogeneous video systems. Simulation results are presented to demonstrate the efficacy of thePcontrollers and the viability of the proposed control-theoretic approach.

The combination of multi-radio nodes in conjunction with a suitably structured mesh architecture has the potential to solve some of the key limitations of present day mesh networks. We propose and evaluate two practical and self-stabilizing channel assignment algorithms for multi-channel dual-radio mesh backhauls. The objective is to find a channel assignment that maximizes network capacity through balancing traffic load and/or co-channel interference on available channels. Through simulations, we show that the proposed scheme can effectively improve the capacity of wireless mesh networks.

It has been shown in the literature that many MAC protocols for wireless networks have a considerable control overhead, which limits their achievable throughput and delay performance. In this paper, we study the problem of improving the efficiency of MAC protocols. We first analyze the popular p- Persistent CSMA scheme and show that it does not achieve 100% throughput.Motivated by insights from polling system theory, we then present three polling service-based MAC schemes, termed PSMACs, for improved performance. The main idea is to serve multiple data frames after a successful contention resolution, thus amortizing the high control overhead and making the protocols more efficient. We present analysis and simulation studies of the proposed schemes. Our results show that PSMAC can effectively improve the throughput and delay performance of p-Persistent CSMA, as well as providing energy savings. We also observe that PSMAC is more efficient for handling the more general and challenging bursty traffic and outperforms p-Persistent CSMA with respect to fairness.

The session initiation protocol (SIP) enables multipoint communications through the use of conferencing and IP multicast, but the usefulness of SIP's multiparty communications is limited. This paper introduces an extension to SIP that provides membership awareness, fault tolerance, and partition recovery for conferencing. The extension also supports application layer multicast for session negotiation and transfer of necessary session information for protocol initialization. We report performance results that characterize message size, message processing time, and partition reformation delays. Using a ring protocol implementation, we demonstrate the ability of the extension to operate with an application layer multipoint protocol and evaluate performance with respect to message size and reformation delay.

We present an innovative routing protocol that utilizes multiple channels to improve performance in a mobile ad hoc network. The basic idea of the design is to provide nodes with the ability to use multiple channels effectively so that multiple useful transmissions can occur simultaneously, thus improving network capacity. The proposed scheme requires minor changes to existing proactive or table-driven routing protocols and no modifications to current the IEEE 802.11 medium access control protocol. To avoid inefficiencies due to transmission of periodic updates in proactive routing protocols, the proposed scheme divides the network layer into control and data planes. To demonstrate the multi-channel routing scheme, we extend the OSPF-MCDS routing protocol to a multi-channel version, OSPF- MCDS-MC. Simulation results indicate that OSPF-MCDS-MC successfully exploits multiple channels to improve network capacity. The routing protocol allows the network goodput to increase in proportion to the number of available channels, even as the number of nodes and network load increase, in both single- hop and multiple-hop networks.

Utilization of multiple channels in ad-hoc networks provides the benefits of increasing network capacity and increasing efficiency by reducing the probability of collisions. Multi-channel schemes are becoming more attractive as the cost of transceivers decreases and the capacity requirements for potential ad-hoc network applications increase. However, channel assignment mechanisms may distribute channels unfairly to different nodes, thus leading to inefficient use of available capacity and creating system bottlenecks. In this paper, we present a new metric to explore channel distribution in multi-channel wireless ad-hoc networks. The approach lets each node measure the fairness of channel distribution among neighboring nodes. Most prior work on multi-channel schemes focuses on the channel assignment (CA) problem and multi-channel multiple access control (MAC) protocols. Our proposed channel distribution index (CDI) measures the fairness of channel distribution and indicates the dynamic channel distribution among neighboring nodes. Our proposed metric for multi-channel wireless ad-hoc networks can be used to evaluate the fairness of CA and MAC schemes and, in the future, to improve their efficiency

Despite the fact that it is not optimal, the availability of low-cost, commodity network interface cards (NICs) has made the IEEE 802.11 medium access control (MAC) protocol the de facto MAC standard for wireless mobile ad-hoc networks. The IEEE 802.11 MAC protocol is designed to have stations share a single channel in a given network. However, many of the IEEE 802.11 physical (PHY) layer specifications define multiple channels and allow the simultaneous, non-interfering use of some of these channels. Therefore, simultaneous communications can use different channels, offering the opportunity to increase the effective network capacity. We have designed and implemented an innovative proactive routing protocol that utilizes multiple channels to improve performance in a mobile ad hoc network. The key feature of the protocol is that nodes can effectively use multiple channels for simultaneous useful transmissions, thus improving network capacity. The proposed scheme requires minor changes to existing proactive or table-driven routing protocols and no modifications to the current IEEE 802.11 MAC protocol. To demonstrate the multi-channel routing scheme, we extend the optimized link state routing (OLSR) protocol to create a multi-channel version, OLSR-MC. Experimental results indicate that OLSR-MC successfully exploits multiple channels to improve network capacity and increases the network throughput

This paper considers ultra-wideband (UWB)-based sensor networks and studies the following problem: given a set of source sensor nodes in the network each generating a certain data rate, is it possible to relay all these rates successfully to the base station? We will show that such problem is intrinsic cross-layer, and subsequently we formulate an optimization problem, with joint consideration of link-layer scheduling, power control, and network-layer routing. For large-sized networks, we propose an efficient heuristic algorithm by partitioning the given network into a core centered around the base station and a boundary edge. For the network core, we formulate a nonlinear programming problem, which can be solved by branch-and-bound approach. For data generated at network edge, we propose an algorithm to connect it to the network core. We use simulation results to demonstrate the efficacy of the proposed solution procedure, as well as the importance of cross-layer considerations.

Wireless sensor networks are becoming increasingly important in recent years due to their ability to detect and convey real-time, in-situ information for many civilian and military applications. A fundamental challenge for such networks lies in energy constraint, which poses a performance limit on the achievable network lifetime. We consider a two-tier wireless sensor network and address the network lifetime problem for upper-tier aggregation and forwarding nodes (AFNs). Existing flow routing solutions proposed for maximizing network lifetime require AFNs to split flows to different paths during transmission, which we call multisession flow routing solutions. If an AFN is equipped with a single transmitter/receiver pair, a multisession flow routing solution requires a packet-level power control at the AFN so as to conserve energy, which calls for considerable overhead in synchronization among the AFNs. In this paper, we show that it is possible to achieve the same optimal network lifetime by power control on a much larger timescale with the so-called single-session flow routing solutions, under which the packet-level power control and, thus, strict requirement on synchronization are not necessary. We also show how to perform optimal single-session flow routing when the bit-rate of composite flows generated by AFNs is time-varying, as long as the average bit-rate can be estimated

We study the problem of multipath routing for double description (DD) video in wireless ad hoc networks. We follow an application-centric cross-layer approach and formulate an optimal routing problem that minimizes the application layer video distortion. We show that the optimization problem has a highly complex objective function and an exact analytic solution is not obtainable. However, we find that a meta-heuristic approach such as genetic algorithms (GAs) is eminently effective in addressing this type of complex cross-layer optimization problems. We provide a detailed solution procedure for the GA-based approach. Simulation results demonstrate the superior performance of the GA-based approach versus several other approaches. Our efforts in this work provide an important methodology for addressing complex cross-layer optimization problems, particularly those involved in the application and network layers

To improve the capacity of wireless ad hoc networks by exploiting multiple available channels, we propose a combined proactive routing and multi-channel medium access control (MAC) protocol. The multi-channel MAC protocol is compatible with IEEE 802.11 MAC and imposes the minimum system requirement among existing multi-channel MAC protocols. Because a proactive routing protocol allows each node to have complete topology information of the network, channel assignment can be closely coupled with a proactive routing protocol. The proposed channel assignment protocol is shown to require fewer channels and exhibit significantly lower communication, computation, and storage complexity than existing channel assignment schemes. We prove the correctness of the proposed channel assignment protocol. In addition, through a performance study, we show that the proposed protocol, by effectively increasing capacity, substantially increases throughput and decreases delay compared to the IEEE 802.11 MAC protocol.

Directional antenna has great potential to reduce power consumption in energy constrained wireless sensor networks. We consider a two-tier wireless sensor network where directional antenna is employed for upper-tier aggregation and forwarding nodes (AFNs). Existing flow routing solutions for maximizing network lifetime require each AFN to transmit multiple flows to different nodes at the same time, which we call multi-beam flow routing solution. In this paper, we show that it is possible to develop single-beam flow routing solution for nodes with directional antenna. More important, we show that the single-beam flow routing solution developed here is provably optimal in terms of network lifetime performance. This result is based on a novel technique to transform the optimal multi-beam flow routing into an equivalent single-beam flow routing solution. Numerical example illustrating how to obtain an optimal single-beam flow routing solution is also given.

Although it has been an active research area for a number of years, distributed channel assignment remains a challenging problem and existing protocols tend to be complex and usually not suitable for practical implementation. In this paper, we propose three principles that facilitate the design of efficient distributed channel assignment protocols in wireless ad hoc networks. Protocols that implement these design principles are shown to require fewer channels and exhibit significantly lower communication, computation, and storage complexity, compared with existing approaches. As examples, we present two such protocols built on the ad-hoc on-demand distance vector (AODV) routing protocol. In addition, we prove the correctness of the algorithms and derive an upper bound on the number of channels required to both resolve collisions and mitigate interference. Simulation results show that, in many cases, the performance of the proposed protocols can approach that of centralized near-optimal algorithms while maintaining low control overhead.

Real-time multimedia communication is an important service that should be supported in wireless ad hoc networks, In this paper we consider the problem of how to optimally support multiple concurrent video communication sessions in an ad hoc network. Our problem formulation follows an application-centric cross-layer approach with the objective of minimizing the average distortion for all video sessions via finding optimal paths for each session. Since this network-wide optimization problem is shown to be NP-complete, we pursue to develop competitive heuristic algorithms to address this problem. We find that genetic algorithms (GA) are eminently efficient in solving such cross-layer problems with complex objective functions and constraints. We describe a detailed solution procedure based on the GA approach and use numerical results to demonstrate its superior performance over other conventional approaches. Our efforts in this work provide an important methodology for addressing cross-layer network-wide optimal routing problems for video applications.

As developments in wireless ad hoc networks continue, there is an increasing expectation with regard to supporting content-rich multimedia communications (e.g., video) in such networks, in addition to simple data communications. The recent advances in multiple description (MD) video coding have made it highly suitable for multimedia applications in such networks. In this paper, we study the important problem of multipath routing for MD video in wireless ad hoc networks. We follow an application-centric cross-layer approach and formulate an optimal routing problem that minimizes the application layer video distortion. We show that the optimization problem has a highly complex objective function and an exact analytic solution is not obtainable. However, we find that a meta-heuristic approach such as genetic algorithms (GAs) is eminently effective in addressing this type of complex cross-layer optimization problems. We provide a detailed solution procedure for the GA-based approach, as well as a tight lower bound for video distortion. We use numerical results to demonstrate the superior performance of the GA-based approach and compare it to several other approaches. Our efforts in this work provide an important methodology for addressing complex cross-layer optimization problems, particularly those involving application and network layers.

Ultra-wideband (UWB) has great potential for wireless communications in emerging applications such as sensor networks. This paper considers UWB-based sensor networks and studies the following problem: given a set of source sensor nodes in the network each generating a certain data rate, is it possible to relay all these rates successfully to the base-station? We follow a cross-layer optimization approach, with joint consideration of link layer scheduling, power control, and network layer routing. The optimization problem is formulated as a non-linear programming problem. For small-sized networks, we develop a powerful approximation solution procedure to this problem based on the branch-and-bound approach and the novel Reformulation-Linearization Technique (RLT). For large-sized networks, we propose an efficient heuristic algorithm by partitioning the sensor network into a core centered around the base-station and an edge that is outside the core. We also provide a closed-form analysis for the maximum rate that a base-station can receive. Simulation results exhibit the efficacy of our proposed optimization solution procedure and demonstrate the importance of the cross-layer approach to UWB-based sensor networks.

Encryption algorithms can be used to help secure wireless communications, but securing data also consumes resources. The goal of this research is to provide users or system developers of personal digital assistants and applications with the associated time and energy costs of using specific encryption algorithms. Fouriblock ciphers (RC2, Blowfish, XTEA, and AES) were considered. The experiments included encryption and decryption tasks with different cipher and file size combinations. The resource impact of the block ciphers were evaluated using the latency, throughput, energy-latency product, and throughput/energy ratio metrics. We found that RC2 encrypts faster and uses less energyithan XTEA, followed by AES. The Blowfish cipher is a fast encryption algorithm, but the size of the plaintext affects its encryption speed and energy consumption. Faster algorithms seem to be more energy efficient because of differences in speed rather than differences in power consumption levels while encrypting.

Abstract — Wireless sensor networks that operate on batteries have limited network lifetime. There have been extensive recent research efforts on how to design protocols and algorithms to prolong network lifetime. However, due to energy constraint, even under the most efficient protocols and algorithms, the network lifetime may still be unable to meet the mission’s requirements. In this paper, we consider the energy provisioning problem for a two-tier wireless sensor network. In addition to provisioning additional energy on the existing nodes, we also consider deploying relay nodes (RNs) into the network to mitigate network geometric deficiency and prolong network lifetime. We formulate the joint problem of energy provisioning and relay node placement (EP-RNP) into a mixed-integer nonlinear programming (MINLP) problem. Since an MINLP problem is NP-hard in general, and even the state-of-the-art software and techniques are unable to offer satisfactory solutions, we develop a heuristic algorithm, called SPINDS, to address this problem. We show a number of novel algorithmic design techniques in the design of SPINDS that effectively transforms a complex MINLP problem into linear programming (LP) problems without losing critical points in its search space. Through numerical results, we show that SPINDS offers very attractive solution and some important insights to the EP-RNP problem. Index Terms — Energy provisioning, relay node placement, power control, network lifetime, flow routing, wireless sensor networks. I.

Despite being the subject of many years of research, distributed channel assignment remains a challenging problem. In this paper, we use a cross-layer approach and present a family of efficient distributed channel assignment protocols for wireless ad hoc networks. These protocols seek to assign distinct channels to each node within all sets of interfering nodes on the same route, subject to a channel availability constraint. Because the proposed protocols combine channel assignment with routing, they exhibit significantly lower communication, computation, and storage complexity than existing channel assignment schemes. We present an example protocol that utilizes the AODV routing protocol. In addition, we prove the correctness of the algorithms and derive an upper bound on the number of channels required to both resolve collisions and mitigate interference. Simulation results show that the performance of the proposed protocols can approach that of centralized near-optimal algorithms when the number of active routes is small.

In this paper, we demonstrate the unfair utilization of resources by transmission control protocol (TCP) traffic flows traversing satellite links when they compete with terrestrial flows in a congested router. To mitigate this problem and provide quality of service (QoS), we propose a preferential suppression (PS) scheme to suppress flows that consume too many resources. By selectively suppressing terrestrial TCP flows with PS, we show that resources can be allocated fairly to the TCP flows using satellite links. However, these TCP flows cannot fully utilize available bandwidth due to the long delay in receiving feedback over high latency satellite links. To improve response time, a TCP spoofing scheme is integrated with PS to reduce the effective round-trip time. Simulation results show that target TCP flows are able to utilize a designated amount of bandwidth and, thus, can achieve QoS objectives. This enables QoS support in an edge router for TCP flows over satellite links that must compete with other flows in the terrestrial network.

This paper describes a novel multipath routing algorithm, Fresnel zone routing (FZR), for wireless ad hoc networks. First, the concept of Fresnel zones in an ad hoc network is introduced to classify intermediate nodes according to their capacity and efficiency for forwarding traffic. Second, multiple paths via different Fresnel zones are constructed efficiently using a hybrid of proactive and on-demand approaches. By dispersing traffic into multiple zones according to network load and congestion conditions, FZR can alleviate congestion at intermediate nodes and achieve better transport layer throughput. The operations of FZR are implemented and verified with discrete-event simulation models. Simulation experiments show that FZR can provide significant performance improvement over existing unipath and multipath routing protocols for both TCP and UDP traffic.

Broadband wireless access (BWA) is a promising emerging technology. The IEEE 802.16 task group recently standardized the physical (PHY) and medium access control (MAC) layers for BWA systems. To operate in a wide range of physical channel conditions, the standard defines a robust and flexible PHY. A wide range of modulation and coding schemes are defined. While the standard provides a framework for implementing link adaptation, it does not define how exactly adaptation algorithms should be developed. The paper evaluates the performance of IEEE 802.16 using a few typical PHY burst profiles defined in the standard. Based on these performance results, TCP delay is identified as a suitable metric to serve as the link quality indicator. A simple link adaptation algorithm is developed to minimize the end-to-end (ETE) TCP delay based on the measured signal-to-noise ratio (SNR). The effects of TCP performance enhancements, namely dynamic window scaling and selective acknowledgements, on the adaptation algorithm are also studied.

This paper describes a one-hop self-organized clustering (SOC) algorithm developed specifically for ultra-wideband (UWB) networks. Our research is motivated by the strict regulation of the transmit power of UWB devices, as imposed by U.S. Federal Communications Commission (FCC). To comply with FCC power regulations and to maximize network capacity, we propose a heuristic clustering algorithm to form clusters that have the minimum total power emission subject to constraints on radio range and multiple access capacity. Simulation results show that the proposed algorithm performs better than a random selection algorithm in terms of power emission under all circumstances. Furthermore, the performance of the SOC algorithm can approach that of the k-means algorithm when an appropriate upper limit on the number of nodes in a cluster is imposed.

Ing-Ray Chen, Luiz DaSilva, Scott Midkiff; Editorial: Mobile and Pervasive Computing, The Computer Journal, Volume 47, Issue 4, 1 January 2004, Pages 404, https

The Bluetooth radio system has been developed to provide mobile ad-hoc connectivity between a wide range of portable and fixed devices. This paper describes the security features of the Bluetooth system and presents an experimental analysis of security vulnerabilities. Vulnerabilities were found as a result of improper validation, exposure, and randomness using a scheme called VERDICT. These vulnerabilities include device address validation, invalid states, and exposed keys.

This paper focuses on characterizing the overhead of IP security (IPSec) for email and Web applications using a set of test bed configurations. The different configurations are implemented using both wireline and wireless network links. The testing considers different combinations of authentication algorithms and authentication protocols. Authentication algorithms include Hashed Message Authentication Code-Message Digest 5 (HMAC-MD5) and Hashed Message Authentication Code-Secure Hash Algorithm 1 (HMAC-SHA1). Authentication protocols include Encapsulating Security Payload (ESP) and Authentication Header (AH) protocols. Triple Digital Encryption Standard (3DES) is used for encryption. Overhead is examined for scenarios using no encryption and no authentication, authentication and no encryption, and authentication and encryption. A variety of different file sizes are considered when measuring the overhead The results present a thorough analysis of the overhead of different IPSec configurations and provide practical guidance for choosing the IPSec configuration needed in a network environment.

Blind broadcast in a wireless ad hoc network means any mobile node will rebroadcast all received broadcast messages. One node may receive the same copy of a message from more than one neighbor, so unnecessary overhead is introduced. A connected dominating set (CDS) can be used to reduce broadcast overhead. We propose a proactive link state routing protocol, integrated with CDS discovery algorithms, as a promising approach for routing in wireless ad hoc networks. This paper presents approximation algorithms to find a minimal CDS for a given network. A prototype of a proactive link state routing protocol integrated with CDS algorithms is introduced. Both simulation and analytical results indicate better performance than other algorithms.

Bluetooth has been developed to provide mobile ad hoc connectivity between a wide range of portable and fixed devices. In this paper, the Bluetooth system is described with an emphasis on its security features and known vulnerabilities. Additional security vulnerabilities were discovered using a scheme called VERDICT. These vulnerabilities are compared to vulnerabilities found in the IEEE 802.11 wireless local area network standard with VERDICT. Vulnerabilities were found as a result of poor improper validation, exposure, and randomness. These vulnerabilities include device address validation, invalid states, and exposed keys.

Many wireless ad hoc routing protocols have been proposed in the literature. Researchers are comparing and improving these protocols before standard routing protocols are defined. In this paper, we present a framework for wireless ad hoc routing protocols based on the concept of a relay node set (RNS). This framework facilitates the comparison, design, and improvement of wireless ad hoc routing protocols. We briefly present an analytical model for comparing protocols using this framework with packet overhead as the metric. We also apply the framework to show how to improve a routing protocol. Future work using the framework is also discussed.

Wireless mobile ad hoc networks differ from wired networks in that their topologies are highly dynamic and their links can have a relatively high bit error rate. These properties make it difficult to conduct controlled, repeatable experiments with routing and other protocols in a wireless ad hoc network environment. To address this problem, we have developed a switch that connects multiple unaltered hosts according to a controllable dynamic topology with a controllable bit error rate on the links. The dynamic topology switch emulates a wireless mobile ad hoc network using standard Ethernet physical connections. This allows researchers to experiment with routing and other protocols in a mobile ad hoc network (MANET) environment. In this paper, we describe our dynamic topology switch and describe the validation of the switch. We validate the switch by comparing control packet overhead for the optimized link state routing (OLSR) protocol measured using the switch and using the ns-2 simulator.

This paper addresses the problem of providing secure network management using the Simple Network Management Protocol (SNMP) across a backbone network. We compare using the built-in authentication and privacy features of SNMP version 3 (SNMPv3) and using SNMP version 2 (SNMPv2c) over IP Security (IPSec). Our results indicate that a framework based on IPSec offers functional and performance advantages. With respect to capacity utilization, our experimental results show that SNMPv3 consumes as much as 24 percent more network capacity than SNMPv2c over IPSec.

Flexible and fast routers are generally considered a contradiction in terms since maintaining high-throughput requires fast but fixed-configuration application specific integrated circuits (ASICs) while flexibility requires slower but flexible configuration of general-purpose processors. A configurable stream-based reconfigurable router is a fast, flexible solution that includes the best features of both hardware and software processing through the efficient use of field-programmable gate array (FPGA) technology, active VHDL, and hardware/software partitioning and scheduling algorithms. This paper discusses the architecture of the stream-based reconfigurable router and presents the design, implementation, and evaluation of a prototype reconfigurable router.

This paper examines the use of the available bit rate (ABR) service in asynchronous transfer mode (ATM) networks for video traffic. The ABR service can utilize network capacity more efficiently than constant bit rate (CBR) or variable bit rate (VBR) services, but it makes no guarantees concerning cell delay or cell delay variation. Unlike the unspecified bit rate (UBR) service, the ABR service does provide congestion feedback. The effects of three specific MPEG-1 video source adaptation schemes, arbitrary loss or no control method, selective discard of MPEG B pictures, and selective discard of MPEG B and P pictures, on network performance are compared. Performance is evaluated based on end-to-end (ETE) delay, queue occupancy, link utilization, jitter, and distribution of delay.

We develop and analyze an elegant, opportunistic medium access control (MAC) protocol based on the proposed MAC standard for wireless local area networks (WLAN)-IEEE 802.11. Our adaptation of 802.11 is called CATER (code adapts to enhance reliability) and allows communicating stations to reconfigure their transceivers to use a longer pseudonoise (PN) code when retransmissions are unsuccessful over a degraded channel. Results show that our protocol continues to function, permitting up to 14 percent normalized aggregate throughput, at times when IEEE 802.11 fails. In addition, throughput experiences only a small decrease due to protocol overhead during periods when stations experience a good channel and few bit errors.

This paper describes a test generation methodology that supports test generation for bridging faults in CMOS circuits using I/sub DDQ/ testing or quiescent supply current observation. A modular, hierarchical approach is used to handle large circuit sizes while maintaining an accurate representation of the structure of CMOS designs and fault mechanisms. The emphasis of this work is on the efficient generation of I/sub DDQ/ test sets that achieve very high fault coverage of unrestricted bridging faults, including both gate- and switch-level bridging faults, with reasonable computational requirements. An implementation of the approach supports all operations required for automatic test pattern generation, including fault sensitization, fault simulation, and test set compaction. Results are presented for tests of realistic bridging faults derived directly from the CMOS layouts of a set of benchmark circuits.>

Investigates linkages between physically realistic faults in CMOS integrated circuits and test generation and test quality. The procedure and results for an inductive fault analysis experiment that determined likely bridging faults in a set of CMOS circuits are presented. The implications of the results on test generation for physically realistic faults and on fault coverage are discussed.>

Explores the feasibility of using circuit partitioning approach to reduce the run-time complexity of test generation via parallel processing. Characterization of the major phases of test generation is used to show how the inherent parallelism existing in test generation can be exploited during forward implication and backward justification. Upper bounds on the concurrency available in specific are empirically determined by simulating the behavior of a 'perfect' conflict-free test generation algorithm that operates without backtracking. Results presented for a number of benchmark circuits indicate that the average available parallelism is fairly low, limiting the potential speedup of a circuit partitioning approach to test generation.>

The authors examine tests for short and open faults in CMOS circuits considering both IDDQ and logic observation test methods. Short and open faults are classified according to a topological classification that considers the type of fault, fault location, and affected transistor structure. The testability of each fault classification is considered for both optimistic and pessimistic assumptions. Circuit-level simulation is used to illustrate the classification.>

A graph-based solution to the mapping problem using the simulated annealing optimization heuristic is developed. An automated two-phase mapping strategy is formulated: process annealing assigns parallel processes to processing nodes, and connection annealing schedules traffic connections on network data links so that interprocess communication conflicts are minimized. To evaluate the quality of generated mappings. cost functions suitable for simulated annealing that accurately quantify communications overhead are derived. Communication efficiency is formulated to measure the quality of assignments when the optimal mapping is unknown. The mapping scheme is implemented using the hypercube as a host architecture, and results for several image graphs are presented.>

The authors present two novel metrics (range effectiveness and differentiation effectiveness) for evaluating the effectiveness of continuous-domain test techniques, such as supply current and propagation delay testing, for CMOS faults of general severity. The metrics consider both the severity of the fault and the differentiation of test measurements. Range effectiveness is used to determine the range of fault severities that are reliably detected as being present in a circuit, and differentiation effectiveness is used to determine the differentiation between good and faulty circuits for a specified maximum acceptable fault severity. An application comparing supply current and propagation delay testing of a bridging fault is presented to illustrate the metrics.>