Abstract IEEE 802.11 distributed coordination function (DCF) is a popular protocol used for the physical and medium access control layers in most ad hoc networks. DCF employs carrier sense multiple access with collision avoidance and a binary slotted exponential back off. It has been observed that the hidden and exposed terminal problems among stations degrade DCF's performance in terms of throughput and fairness. Hence, the effectiveness of the IEEE 802.11 DCF mechanism in ad hoc networks has attracted many research studies. Many collision avoidance schemes were proposed to address the IEEE 802.11 DCF weaknesses as the performance of the medium access control layer directly impacts the performance of higher‐layer protocols and hence the entire network. An evaluation of representative schemes under the same conditions will be helpful in understanding the limitations and strengths of these schemes. This paper surveys various collision avoidance schemes, classify them on the basis of their mechanism, and then provide a comparative study of representative schemes based on their performance. They are evaluated on a chain topology, a pair topology, and a random topology with static environment to measure their throughput, fairness, collision probabilities, and delay. On the basis of the evaluation, we conclude that gentle DCF is the best scheme that has lesser collisions with improved throughput and fairness. A comparison with the legacy carrier sense multiple access with collision avoidance suggests that these proposed schemes do tend to be promising and would inspire future researchers who are interested to find solutions to the age‐old collision and fairness issues in ad hoc networks. Copyright © 2014 John Wiley & Sons, Ltd.

With the proliferation of mobile devices such as smartphones, an interesting problem is how to make use them to improve the accuracy of localization in indoor environments. In this paper, we develop a novel cooperative localization scheme exploiting mobility in the indoor environment. The problem is formulated as a semidefinite program (SDP) using Linear Matrix Inequality (LMI). With the proposed approach, mobile users utilize their top RSS measurements for distance estimation and to mitigate the the shadowing effect found in indoor environments. In addition, we utilize the estimated position for a user from the last time slot as a virtual access point (AP) to obtain the next position estimation, by utilizing the inertial measurement unit (IMU) data from smartphones. To better take advantage of the moving direction and velocity information provided by the smartphones, we next apply Kalman filter to further mitigate the errors in estimated positions. Simulation results confirm that both the mean error and variance can be effectively reduced by exploiting IMU data and Kalman filter.

Attracting increasing attention in recent years, the Free Space Optics (FSO) technology has been recognized as a cost-effective wireless access technology for multi-Gigabit rate wireless networks. Radio over Free Space Optics (RoFSO) provides a promising enhancement to optical fiber systems. In an RoFSO system using wavelength-division multiplexing (WDM), it is possible to concurrently transmit multiple data streams consisting of various wireless services at very high rate. In this paper, we develop power allocation schemes for adaptive WDM transmissions to combat the effect of weather turbulence in FSO networks. The problem of optical power allocation under power budget and eye safety constraints is investigated for adaptive WDM transmission in RoFSO networks. Simulation results show that WDM RoFSO can support high data rates even over long distance or under bad weather conditions with an adequate system design.

Cooperative diversity is considered as an effective means for combating weather turbulence in FSO networks. We investigate the problem of maximizing the FSO network-wide throughput under constraint of a given power budget and a number of FSO transceivers. The problem is formulated as a Mixed Integer Nonlinear Programming (MINLP) problem. We propose both centralized and distributed algorithms using bipartite matching and convex optimization to obtain highly competitive solutions. The proposed algorithms are shown to outperform the non-cooperative scheme and an existing relay selection protocol with considerable gains through simulations.

Free space optical (FSO) networking is an attractive technology with applications ranging from high capacity military communications to “Last-mile” broadband access solutions. Topology control is an important problem in FSO networks. The problem of building a spanning tree when number of transceivers on each base station is limited, in FSO networks, is NP-hard. What makes the problem even more challenging is to maximize the algebraic connectivity of the spanning tree. In this paper, we develop an initially configuring, or bootstrapping, algorithm which produces a degree constrained spanning tree with high algebraic connectivity and also high average edge weight, where the edge weight in the graph represents the FSO link reliability. We also develop a fast reconfiguration algorithm when one or more links fail in the FSO network. Our algorithms outperform alternative schemes in improving both algebraic connectivity and average edge weight. The robustness of the resulting topology of FSO networks is significantly improved.

Reducing test cost by minimizing the overall test time remains one of the main goals of System-on-Chip (SoC) testing. Power-aware strategies optimize the overall test time of a SoC for a global peak power budget. Test time and test power can be regulated by VDDand test clock frequency to optimize SoC test schedules for a given power budget. Dynamic voltage and frequency scaling (DVFS) techniques have been used in the past to optimize energy efficiency in SoCs. In this paper, we extend the concept of DVFS to optimize the test scheduling of SoC. We adopt a sessionless test scheduling strategy and provide a simple heuristic approach for its optimization. The proposed idea is implemented on several ITC02 benchmarks. Results show significant test time reduction over sessionless reference test schedules for which VDDand clock frequency are fixed at nominal values.

Although the technology of femtocells is highly promising, many challenging problems should be addressed before fully harvesting its potential. In this paper, we investigate the problem of cell association and handover management in femtocell networks. Two extreme cases for cell association are first discussed and analyzed. Then we propose our algorithm to maximize network capacity while achieving fairness among users. Based on this algorithm, we further develop a handover algorithm to reduce the number of unnecessary handovers using Bayesian estimation. The proposed handover algorithm is demonstrated to outperform a heuristic scheme with considerable gains in our simulation study.

No abstract available.

Spectrum sensing and sharing the sensing results is one of the most important tasks for the operation of a cognitive radio network. It is even more crucial in a multi-hop cognitive radio network, where there is no omni-present central authority. But since communicating the sensing results periodically to other users consumes significant amount of energy, users tend to conserve energy by not sharing their results. This non-cooperation will lead to lesser clarity in spectrum occupancy map. Therefore, appropriate strategies are required to enforce cooperative sharing of the sensing results. The classic Tit-For-Tat strategy cannot be used because punishing a node by not broadcasting the sensing results also affects other nodes. In this paper, we address this problem by exploiting the unique characteristics of cross-layer interaction in cognitive radios to sustain cooperative spectrum sensing. In this direction, we design a Cross-Layer game which is a combination of the spectrum sensing game in the physical layer and packet forwarding game in the network layer. In this strategy, users punish those who do not share their sensing results by denying to cooperate in the network layer. The Cross-Layer game is modeled as a noncooperative non- zero-sum repeated game and a Generous Tit-For-Tat strategy is proposed to ensure cooperation even in the presence of collisions and spectrum mobility. We prove that the Nash Equilibrium of this strategy is mutual cooperation and that it is robust against attacks on spectrum sensing and sharing session.

The threat landscape continues to evolve, with increasingly complex attacks directed at the corporate network to achieve malicious goals. Enterprise networks build their first line of defense with firewalls and virtual private network (VPN) gateways. However, this kind of defense can be easily circumvented. It is possible that an attacker may have compromised a client process and gain privilege of the client computer. Even though we have corporate-wide access control, the access control approach is currently insufficient to stop these malicious processes. To better defend enterprise network, this paper proposed a novel system that empowers the corporate networks to verify client integrity properties based on our trusted measurement architecture. When the critical system configuration is changed, the trusted platform module (TPM) attestation mechanism is called to inform security agent about the trusted measurement values. Once the verification process fails, the client will be excluded from the network and notification to a super security agent will be sent. The system performance is also illustrated in this paper.

In this paper, we propose a cooperative framework for spectrum sharing between a secondary random ad hoc network and a primary network with capacity constraint. While the interference from secondary network must satisfy a power constraint, there is no stipulation on its higher order statistics. Considering a generalized Gaussian model for interference, we show that the capacity of a primary link can be improved by increasing the kurtosis of interference. We show that by using power control, the secondary network can increase the kurtosis of its interference and thereby can help the primary links to maintain their minimum capacity constraint. Secondary network is allowed to share the spectrum for a fraction of time proportional to the capacity gain obtained by the primary link. Simulation results show that by cooperation from the secondary network, both secondary and primary networks can achieve their goals in accessing the spectrum and satisfying the capacity constraint.

Wireless user-mobility prediction has been investigated from various angles to improve network performance. Student populations in campuses, pedestrian and vehicular movement in urban areas, etc have been studied by cell phone and mobility management researchers to address issues in quality of service (QoS), seamless session handoffs, etc. Access to information such as user movement times, direction, speed, etc provides an opportunity for networks to efficiently manage resources to satisfy user needs. Towards this goal, we propose a generic framework to approach the problem of mobility prediction using hidden Markov models (HMM). This method can be used to model hidden parameters in the models. We propose a way to extract user movement information from a real dataset, train a HMM using this data and make predictions using the HMM. This model can successfully predict long sequences of a mobile user's path from observed sequences and also uses successive sequences of observed data to train its learning parameters to enhance prediction accuracy. Furthermore, we show that this model is very generic and can be suited to make predictions using the same information from the perspective of the access point or the mobile node.

PKI-based security in Vehicular Networks has to heavily rely on revoking the malicious user by adding his certificates to a Certificate Revocation List and broadcasting it to all the nodes. In a vehicular network with minimal infrastructure there is a need for a quick and reliable delivery or this CRL to all the nodes. While vehicle-to-vehicle or infrastructure-to-vehicle flooding could seem a natural way to deliver the CRL to all the nodes, existing flooding techniques either are unreliable, generate overwhelming unnecessary retransmission or incur excessive network control overhead. In this paper we study the problem of efficient distribution of CRLs in a vehicular network with minimal infrastructure by analyzing the performance of several broadcast protocols for CRL distribution. Our overall result is the definition and analysis of efficient CRL geo-cast protocols over vehicular networks with realistic scenarios of maps with varying density regions. Previous results did not consider the case of varying density regions or required a significant number of infrastructure servers. In the process, we reduce the problem of efficient geo-cast over a practical geographic map to the much more tractable problem of efficient broadcast over a region with an arbitrary vehicle density, which is solved via natural variants of known broadcasting protocols.

In order to ensure fair access and efficiency of bandwidth usage in wireless integrated networks, resource allocation algorithms should be well designed. In this paper, we briefly discuss the complete sharing, complete partitioning and Hybrid resource sharing approaches and their shortcomings in WiMax-WiFi integrated networks. To overcome these shortcomings we propose the Prioritized Resource Sharing algorithm for WiMax-WiFi integrated networks. In this algorithm, the channels are prioritized for different traffic classes rather than strict reservation or open access. The prioritized resource sharing algorithm is then extended to multiple integrated networks. Finally, we analyze the proposed algorithm by modeling it using two dimensional continuous time Markov chains. The simulation results indicate that the Prioritized Sharing model achieves the best system utilization compared to other algorithms. It is also observed that due to heavy traffic of one class of users, other class of users are not starved unlike in complete sharing.

Mobile wireless network performance, measured using throughput, call blocking and dropping probabilities and resource utilization, is related to the mobility behavior of users. Statistical information pertaining to user mobility can be exploited to design mobility aware networks. This paper proposes a mobile network design method using prior mobility data. The mobility prediction scheme proposed is based on the well known Hidden Markov Model (HMM). This model is incorporated into a control theoretic framework that uses mobility history in the feedback loop to optimally allocate network resources to user sessions. The model and framework are validated via extensive Simulink Control System toolbox and MATLAB simulations. Simulation results show the effectiveness of the approach in improving network resource utilization and significantly reducing call dropping probability. It is also observed that the approach is scalable in the number of network users.

In this paper, we study the effects of mobility on network parameters in hierarchical ad hoc networks. Several mobility models have been designed and studied to mimic the behavior of real world mobility in networks. They have been successful in modeling the movement of mobile nodes in simulations. However, in this work, we show that several mobility models fall short of extending the same result to hierarchical networks. Most mobility models can only predict the movement of nodes in a single cell or cluster. When mobile nodes start moving into adjacent clusters, the time required for handoff and other protocol overhead issues alter the throughput. This leads to drastic drop in throughput and increased latency in packet delivery. Also, commonly used routing protocols do not adequately support handling high mobility and frequent route discovery issues. We evaluate the performances of various routing protocols and mobility models in a highly mobile hierarchical ad hoc network using NS2 simulation.

Transmission Control Protocol (TCP) is the most commonly used transport protocol on the Internet. All indications assure that it will be an integral part of the future internetworks. In this paper, we present how regular TCP which was designed for wired networks is not suitable for dynamic spectrum access networks. We develop an analytical model to estimate the TCP throughput of Dynamic spectrum access networks. Dynamic spectrum access networks deal with opportunistic spectrum access leading to greater utilization of the spectrum. The extent of utilization depends on the primary user's traffic and also on the way the spectrum is accessed by the primary and secondary users. The proposed model considers primary and secondary user traffic in estimating the TCP throughput by modeling the spectrum access using continuous-time Markov chains, thus providing more insight on effect of dynamic spectrum access on TCP performance than the existing models.

To support fast and efficient handovers in mobile WiMAX, we propose fast intra-network and cross-layer handover (FINCH) for intradomain (intra-CSN) mobility management. FINCH is a complementary protocol to mobile IP (MIP), which deals with interdomain (inter-CSN) mobility management in mobile WiMAX. FINCH can reduce not only the handover latency but also the end-to-end latency for MIP. Paging extension for FINCH is also proposed to enhance the energy efficiency. The proposed FINCH is especially suitable for real-time services in frequent handover environment, which is important for future mobile WiMAX networks. In addition, FINCH is a generic protocol for other IEEE 802-series standards. This is especially beneficial for the integration of heterogeneous networks, for instance, the integration of WiMAX and WiFi networks. Both mathematical analysis and simulation are developed to analyze and compare the performance of FINCH with other protocols. The results show that FINCH can support fast and efficient link layer and intradomain handovers. The numerical results can also be used to select proper network configurations.

This paper proposes a hierarchical two-step localization method for heterogeneous sensor networks. The network consists of three types of nodes: anchor nodes with known locations, a few nodes equipped with both Ultra-Wide Band (UWB) and RF radios, and a large number of sensor nodes called Lite Nodes. By using a hierarchical network architecture and UWB technology, only a small number of anchor nodes are needed. The localization method works in two steps. First, UWB nodes estimate their locations by using the built-in high-precision distance measurement and locations of anchor nodes. Next, Lite Nodes use UWB nodes as references to estimate their locations. The performance of iterative and non-iterative localization methods are compared. It is observed through simulations that iterative method produces much smaller localization error. The effects of UWB node placement and other parameters such as measurement noise, number of anchor nodes, and communication ranges on the resulting localization error are also presented.

Cognitive networks enable efficient sharing of the radio spectrum. Multi-hop cognitive network is a cooperative network in which cognitive users take help of their neighbors to forward data to the destination. Control signals used to enable cooperation communicate through a common control channel (CCC). Such usage introduces conditions like channel saturation which degrades the overall performance of the network. Thus, exchanging control information is a major challenge in cognitive radio networks. This paper proposes an alternative MAC protocol for multi-hop cognitive radio networks in which the use of a CCC is avoided. The scheme is applicable in heterogeneous environments where channels have different bandwidths and frequencies of operation. It inherently provides a solution to issues like CCC saturation problem, Denial of Service attacks (DoS) and multi-channel hidden problem. The proposed protocol is shown to provide better connectivity and higher throughput than a CCC based protocol, especially when the network is congested.

Developing routing protocol for vehicular ad hoc networks (VANET) is a challenging task due to potentially large network sizes, rapidly changing topology and frequent network disconnections, which can cause failure or inefficiency in traditional ad hoc routing protocols. We propose an adaptive connectivity aware routing (ACAR) protocol that addresses these problems by adaptively selecting an optimal route with the best network transmission quality based on the statistical and realtime density data that are gathered through an on-the-fly density collection process. The protocol consists of two parts: (1) select an optimal route, consisting of road segments, with the best estimated transmission quality (2) in each road segment in the selected route, select the most efficient multi-hop path that will improve delivery ratio and throughput. The optimal route can be selected using our new connectivity model that takes into account vehicles densities and traffic light periods to estimate transmission quality at road segments, which considers the probability of connectivity and data delivery ratio for transmitting packets. In each road segment along the optimal path, each hop is selected to minimize the packet error rate of the entire path. Our simulation results show that the proposed ACAR protocol outperforms existing VANET routing protocols in terms of data delivery ratio, throughput and data packet delay. In addition, ACAR works very well even if accurate statistical data is not available.

Multi-hop car to car communications are useful for supporting many vehicular applications that provide drivers with safety and convenience ranging from office on the wheel to real traffic query, vehicle safety, parking space searching and on-road advertisement. Developing multi-hop communication in vehicular ad hoc networks (VANET) is a challenging problem due to the rapidly changing topology and frequent network disconnections, which cause failure or inefficiency in traditional ad hoc routing protocols. The problem of frequent network disconnections can be partially addressed using a carry-and- forward mechanism which may incur higher delay. However, our connectivity aware routing (CAR) protocol addresses this problem by selecting an optimal route with the least probability of network disconnection and avoids carry-and-forward delay. This can be achieved using our new probabilistic model of network connectivity which takes into account a more realistic clustering phenomenon of vehicle traffic in city scenarios that is caused by traffic lights. Our simulation results show that the proposed CAR protocol outperforms existing VANET routing protocols in terms of data delivery ratio, data packet delay and network throughput. In addition, CAR improves performance for both sparse and dense networks.

Ultra-wideband (UWB) communications is receiving significant attention recently due to its high data rates and low power, low interference transmission. This paper considers the issue of utilizing these advantages of UWB to design improved Wireless Sensor Networks (WSNs). In particular, we consider data gathering in wireless sensor networks using a mobile node for data collection. We first propose a network architecture where a mobile node equipped with both a UWB transceiver and a narrowband RF transceiver is used to collect data from sensor nodes. The sensor nodes are equipped with a narrowband RF transceiver and only a UWB transmitter (not receiver). This approach is chosen to strike a balance between cost of each sensor node and speed of data transfer, since a UWB transmitter is much less complex and expensive than a UWB receiver. We then propose a mobile Data Gathering (DGR) algorithm to find a minimal set of points in the sensor network, which will serve as data gathering points for the mobile node. We use a Voronoi diagram of the network as a starting point, considering each sensor node in the network as a site in the Voronoi diagram and finnding points in the network where data from multiple sites (sensor nodes) can be collected. We then use a weight function designed to reduce the number of these data collection points, and generate a new smaller set of points, such that the mobile node can collect data from multiple sites from each such point. With the aid of a discrete-event simulation model, we show significant savings in the total time for data collection while providing a high level of network coverage.

In this paper, we consider the problem of employing UltraWideBand (UWB) radio technology in Wireless Sensor Networks. UWB promises very high data rates (of the order of few hundred Mbps), in-built localization features and low power consumption. However, UWB radios have a high acquisition time (in the order of milliseconds). As a result, distributed Medium Access Control (MAC) solutions based on a Request/Response mechanisms suffer from increased overhead when employed in UWB based networks. To mitigate the effect of UWB acquisition time, we propose a node architecture that uses dual radios on the sensor nodes: a primary UWB-based radio for data transmission and an auxiliary narrowband RF-based radio for control information and signaling. We introduce two techniques for Medium Access based on this architecture. In the first technique, we employ the narrowband channel for the exchange of RTS/CTS (as defined in IEEE 802.11 standard) information and thus enable collision-free data transmission in the UWB space. In the second technique, we employ the concept of wake-up radios to provide signaling for data transmission. We employ a distributed channel assignment technique by which neighbors agree on a wake-up channel for each node. This channel is then used to signal the receiver of an impending transmission. Through extensive simulation studies, we demonstrate that both the techniques deliver considerable improvements in delay performance and increase the network throughput over the traditional single radio UWB solution.

Hybrid networks can be conceived by combining suitably interfaced 802.11 access points (APs) and WiMAX (802.16) backhaul. One of the major problems associated with such networks is the increased communication delay experienced by 802.16 users. For instance, containing such delay is important in maintaining quality of service for VoIP applications. This delay can be substantially decreased by a strategic reduction in the number of active 802.16 subscribers in the network. This paper deals with realizing such reduction by rerouting traffic through lightly loaded 802.11 APs. For doing so, a schedule has to be generated. A scheduling algorithm was designed and its effect on the overall network performance, using end to end packet delay as a metric, was analyzed. For this purpose CBR traffic was used over UDP connections. NS-2 simulations using CBR traffic show significant improvement in end-to-end packet delay.

Utra-Wide Band (UWB) technology can provide high data rate and accurate localization at low energy cost. It is considered to be very useful for wireless sensor networks. We propose a reinforcement learning based geographic routing algorithm for UWB sensor networks. A comprehensive reward function is proposed in the learning algorithm to consider node energy, delay, routing failure, and network lifetime. The algorithm performance is evaluated in NS2 and compared with GPSR. Simulation results demonstrate that the proposed algorithm can improve network robustness and network lifetime to be 75% to 213% better than GPSR

In this paper, we address the problem of node placement in a hierarchical heterogeneous wireless sensor network. We consider a two-tiered wireless sensor network where the resource constrained lite nodes (LNs) are used for sensing the environment and high-end sophisticated nodes (SNs) are added to aggregate and forward data. We intend to place minimum number of SNs to handle the traffic generated by LNs and ensure that the SNs form a connected network. We formulate the node placement problem as an optimization problem and use three different algorithms to solve it; namely, binary integer linear programming (BILP), greedy algorithm (GREEDY) and genetic algorithm (GA). We also propose a hybrid approach (HYBRID) combining BILP, GREEDY and GA to improve results. It was found through simulations that GA performed better for random LN deployment. However, using HYBRID, results comparable to original GA could be obtained in only 11.46 % of the time required for the original GA. We support the results with statistical tests.

Devices using disparate wireless technologies often cannot communicate directly with each other. However, in many practical scenarios such as disaster management and public safety crises, communication amongst dissimilar wireless networks may become a necessity. We investigate the problem of communication in an ad hoc heterogeneous network comprising of several underlying homogeneous networks. Our proposed solution introduces special multi-interface devices, called drones, that enable communication between dissimilar networks. The optimal placement of drones with accompanying network interfaces is determined by a new placement and interface selection algorithm (PISA). The algorithm is validated, considering example scenarios, using MATLAB simulations. Solutions achievable using PISA result in high connectivity in the heterogeneous network with minimal number of drones and network interfaces.

Location determination of mobile users within a building has attracted much attention lately due to its many applications in mobile networking including network intrusion detection problems. However, it is challenging due to the complexities of the indoor radio propagation characteristics exacerbated by the mobility of the user. A common practice is to mechanically generate a table showing the radio signal strength at different known locations in the building. A mobile user's location at an arbitrary point in the building is determined by measuring the signal strength at the location in question and determining the location by referring to the above table using a LMSE (least mean square error) criterion. Obviously, this is a very tedious and time consuming task. This paper proposes a novel and automated location determination method called ARIADNE. Using a two dimensional construction floor plan and only a single actual signal strength measurement, ARIADNE generates an estimated signal strength map comparable to those generated manually by actual measurements. Given the signal measurements for a mobile, a proposed clustering algorithm searches that signal strength map to determine the current mobile's location. The results from ARIADNE are comparable and may even be superior to those from existing localization schemes.

Performance analysis is one of the important ingredients of network management. Wireless networks, apart from experiencing problems like congestion, will also suffer from fading, multi path effects and interference from other devices. Many devices operate in the same frequency band as 802.11b networks such as Bluetooth, 802.11g networks, microwave ovens and cordless phones to name a few. In such cases, guaranteeing predefined performance is difficult. In the present work we study the performance degradation of 802.11b networks, in terms of throughput, in the presence of interference. Experiments are carried out in an anechoic chamber to reduce the effects of multi path, fading and other radio related interferences and understand the true effect of the interference introduced. Analyzing the performance of the wireless 802.11b networks under interference helps in drawing a base line for acceptable performance. This helps in proactive performance management which enables us to take necessary corrective measures for the imminent problem before hand.

The demand for location based applications including network intrusion detection has grown tremendously lately. However, location determination of indoor mobile users is challenging because of the complexities of the indoor radio propagation characteristics. A radio-frequency (RF) based indoor localization system, like ARIADNE, typically operates by first constructing a lookup table mapping the radio signal strength at different known locations in the building, and then a mobile user's location at an arbitrary point in the building is determined by measuring the signal strength at the location in question and searching the corresponding location from the above lookup table. Usually, the mobile user's signal strength is measured by three or more sniffers mechanically deployed inside the building. Obviously, the sniffers position configuration and the number of available sniffers greatly affect the localization performance. This paper presents experimental results that explore the impact of the sniffers deployment on the localization based on the ARIADNE system. The results demonstrate that the triangular deployment and extra available sniffers generally generate better localization performance.

In a wireless sensor network, sensors can be randomly distributed in order to collect data from a site. In many cases the location of the wireless sensor nodes is required in order to map the collected data to a particular location. Various schemes have been proposed earlier to estimate the location of sensor nodes in a sensor network. However most of these schemes assume the absence of a malicious user in the system which might not always be true. This paper presents a secure localization algorithm (SLA) that can be implemented with the capabilities of current sensor nodes without the need for any additional specialized hardware. The scheme is based on the transmission of nonces at different power levels from the anchor nodes. A sensor node receives a certain set of nonces which it will have to transmit back to the sink via the anchor nodes. The location of the sensor node can be estimated securely based on this set of nonces. We have investigated the properties of SLA using simulations

The performance of IEEE 802.11 in multi-hop wireless networks depends on the characteristics of the protocol itself, and on those of the upper layer routing protocol. Extensive work has been done to analyze and evaluate the performance of single hop networks under saturated traffic conditions, either through simulations or mathematical modeling. Little work has been done on the analysis of the performance of IEEE 802.11 protocol under the unsaturated traffic conditions that arise in multi-hop networks. The paper proposes analytical models and scenarios for such an analysis. ns-2 simulations with different network configurations validate the proposed models for performance metrics such as throughput, message delay, average queue length, and energy consumption. Simulation results show that the proposed models work well. Key to the modeling of the multi-hop networks is a treatment of the upper layer routing protocols that can affect the network performance through the way they forward packets and the impact of that on the traffic load. The model proposed takes into account the impact of the upper layer routing protocol by introducing a packet acceptance factor with which each relay station accepts packets from the wireless medium before forwarding the same.

Current wireless networks that are widely deployed for various commercial applications, do not keep track of a mobile user's location. However, location information can enhance security by facilitating tracking of misbehaving users, or though implementation of location based network access. Previous work done on location estimation typically involves methods that use a lookup table comprising the client or access point signal strengths, which are collected manually at short distances throughout the site. This paper proposes a new data collection scheme for building a lookup table using client assistance in an enterprise wireless environment. In this work, a network-bused location estimation scheme is implemented using sniffers, which monitor client signal strength. It is observed that the accuracy of location estimation is improved by averaging the lookup table data collected over time. The client assisted data collection scheme can be used to frequently build lookup tables in an efficient manner and hence improve accuracy in location estimation. Thus, this scheme could be used to implement a location based security policy throughout the enterprise wireless network.

To support real-time multimedia services in UMTS all-IP network, 3GPP TR 25.936 proposed two approaches to support real-time serving radio network controller (SRNC) switching, which require packet duplication during SRNC relocation. These approaches significantly consume extra system resources. This paper proposes the fast SRNC relocation (FSR) approach that does not duplicate packets. In FSR, a packet buffering mechanism is implemented to avoid packet loss at the target RNC. We propose an analytic model to investigate the performance of FSR. The numerical results show that packet loss at the source RNC can be ignored. Furthermore, the expected number of packets buffered at the target RNC is small, which does not prolong packet delay.

We are currently witnessing a boom in the deployment and usage of wireless local area networks (WLANs). Once only seen within the enterprise, WLANs are increasingly making their way into residential, commercial, industrial, and public areas. The recent efforts of carriers to integrate WLANs into their wide-area service offerings are testimony to their growing role in the future of wireless networking. Voice continues to be the most predominant wireless application, and, in order to integrate fully with existing and future cellular systems, WLANs must deliver a high quality voice service. We present an experimental evaluation of VoIP capacity in an IEEE 802.11b network. Moreover, we identify and quantify the contributing factors that limit the capacity to less than 10 voice calls per access point.

To support real-time multimedia services in UMTS all-IP network, Third-Generation Partnership Project TR 25.936 proposed two approaches to support real-time serving radio network controller (SRNC) switching, which require packet duplication during SRNC relocation. These approaches significantly consume extra system resources. This paper proposes the fast SRNC relocation (FSR) approach that does not duplicate packets. In FSR, a packet buffering mechanism is implemented to avoid packet loss at the target RNC. We propose an analytic model to investigate the performance of FSR. The numerical results show that packet loss at the source RNC can be ignored. Furthermore, the expected number of packets buffered at the target RNC is small, which does not prolong packet delay.

In this work, we measure wireless local area network (WLAN) voice performance and capacity. While most WLAN applications today are data centric, the growing popularity of Voice over IP (VoIP) applications and the escalating trend towards convergence with cellular networks will catalyze an increased mix of voice traffic. Since voice applications must compete with each other and with simultaneous data applications for WLAN bandwidth, quantifying voice performance and capacity in the presence of background data traffic is an important issue. We offer a practical investigation into the ability of 802.11b MAC layer to support simultaneous voice and data. We quantify VoIP capacity for standard WLAN networks, indicative of those already in the field, as well as evaluate the practical benefits of implementing backoff control and priority queuing at the access point. Conclusions are drawn based on an extensive set of real-world measurements conducted using off-the-shelf equipment in a commercial testbed.

We propose a wireless access mechanism for web traffic packets in an integrated wireless code-division multiple-access system that has both voice and Web traffic. The proposed scheme is a medium-access control layer/link layer (MAC/LL) scheduling algorithm that consists of a two level control: admission control and packet scheduling. The admission control restricts the number of users in the system such that quality-of-service requirements [target signal-to-interference ratio (SIR) and delay] for both voice and Web traffic can be met. The packet scheduling balances the system interference on a slot-by-slot basis such that the target SIRs can be achieved for all users (voice and Web browsing sessions) with a higher scheduling priority for voice. Designing admission control for Web users based on the average offered rate per session is difficult due to the high variations in the offered load generated by heavy tailed distributions for Web traffic. To overcome this problem, we propose an admission control algorithm that adaptively estimates the aggregate average load based on load measurements using a sliding observation window.

Personal Number (PN) service or Follow-me service allows a user to access telecommunication services with any terminal (e.g., fixed telephones or mobile phones) in any location within the service area. To provide this feature, the PN user needs to manually register with a phone number every time he/she enters a new location. If the user forgets to register the new phone number, the incoming calls will be misrouted. To provide user-friendly follow-me service, this paper proposes an automatic follow-me service (AFS) approach that automatically updates the PN records in the Follow-me database. The significance of our approach is that AFS can be integrated with existing Follow-me databases to automate PIN services offered by different PSTN service providers. We show how AFS can be implemented by using the Voice over IP and Bluetooth technologies. Then, we propose an analytic model to investigate the performance of AFS. The analytic results are validated by simulation experiments. Our study suggests how to select polling frequency to optimize the AFS performance.

This paper presents a new method for predicting resource requirements of future handoff calls in multimedia wireless IP networks. It allows call arrivals to be non-Poisson and non-stationary and calls to have arbitrary bandwidth needs. Statistical models, based on time series forecasting theory, that utilize only local information are developed. Our simulations show that the proposed method achieves close correlation between predicted and actual handoff resource demands even when demands fluctuate rapidly over a wide range. Furthermore, it can generate accurate dynamic reservation levels to provide quality/grade of service guarantees for handoff calls. The approach is simple and can be implemented easily.

This paper presents a new method for predicting resource requirements of and resenting resources for future handoff calls in multimedia wireless networks. It allows handoff calls to (1) follow non-Poisson and/or non-stationary arrival processes, (2) have arbitrary resource demands, and (3) have arbitrarily distributed call and channel holding times in any cell. A statistical model, based on Wiener prediction theory, that uses only local information is developed. Our simulations show that it performs well under the above conditions as designed. Furthermore, for Poisson handoff call arrivals, identical per-call bandwidth demands and exponential call and channel holding times, it generates comparable performance with an existing method optimized only for these conditions.

This paper presents two new methods that use local information alone to predict the resource demands of and determine resource reservation levels for future handoff calls in multimedia wireless IP networks. The proposed methods model the instantaneous resource demand directly. This differs from most existing methods that derive the demands from modeling the factors that impact the demands. As a result, the proposed methods allow new and handoff calls to: (1) follow non-Poisson and/or nonstationary arrival processes; (2) have arbitrary per-call resource demands; and (3) have arbitrarily distributed call and channel holding times. The first method is based on the Wiener prediction theory and the second method is based on time series analysis. Our simulations show that they perform well even for non-Poisson and nonstationary handoff call arrivals, arbitrary per-call bandwidth demands, and nonexponentially distributed call and channel holding times. They generate closely comparable performance with an existing local method and an existing collaborative method that uses information about mobiles in neighboring cells, under assumptions for which these other methods are optimized. The proposed methods are much simpler to implement than most other existing methods with fewer capabilities.

Abstract This paper considers three applications—VoIP, mobile Web access and mobile server‐based data transfers—and evaluates the applicability of various IP‐based mobility management mechanisms. We first survey the features and characteristics of various IP mobility protocols, such as MIPv4, MIPv6, MIP‐RO, SIP, CIP, HAWAII, MIP‐RR and IDMP, and then evaluate their utility on an application‐specific basis. The diversity in the mobility‐related requirements ensures that no single mobility solution is universally applicable. We recommend a hierarchical mobility architecture. The framework uses our Dynamic Mobility Agent (DMA) architecture for managing intra‐domain mobility and multiple application‐based binding protocols for supporting inter‐domain mobility. Thus, we recommend SIP as the global binding protocol for VoIP applications and MIPv4/MIPv6 as the global binding mechanism for the mobile server scenario. Copyright © 2001 John Wiley & Sons, Ltd.

To support fast and efficient handoffs, we propose a single protocol for both link-layer (within an IP subnet) and IP-layer (across the IP subnet) handoffs within a local domain. It is a complementary protocol to Mobile IP, in which Mobile IP deals with inter-domain mobility in the wide area. By combining a routing table in the IP layer and a bridging table in the link layer to form a single forwarding table, packets destined for a mobile terminal can be forwarded by simple table look-ups. When a mobile terminal moves, the new route can be established by table updates initiated by the mobile terminal. Compared with Mobile IP, the proposed scheme does not need IP encapsulation and does not have the triangular routing problem. In addition, the overhead and latency caused by interfacing the mobility management in the link layer and the IP layer are eliminated. Although link-layer mobility management depends on the underlying wireless technologies to a certain extent, the proposed scheme is general enough for most wireless multiple-access protocols.

There are many different types of video coding standards which can only be played with specific decoders. The lack of a decoder requires a user to download and install the proper decoder in order to decode a particular video stream. This however may not be preferable for real-time applications due to real-time constraint. We propose active techniques to dynamically inject video coding software into the transmitted video packets so that users are capable of playing video encoded in any format without having the decoding software pre-installed. The proposed techniques encapsulate the encoded video stream along with the appropriate video decoding software into active packets, and transmit the active packets to the receiving terminal. The receiver then only needs to extract the code from the active packets to get the software to decode the encoded video. The process of creating and extracting active packets is referred as active activation. Depending upon the nature of the video stream, there are different active techniques to encapsulate and restore the video stream. This paper details these active techniques.

Receiver synchronization of continuous media streams is required to deal with delay differences and variations resulting from delivery over packet networks such as the Internet. This function is commonly provided using per-stream playout buffers which introduce additional delay in order to produce a playout schedule which meets the synchronization requirements. Packets which arrive after their scheduled playout time are considered late and are discarded. In this paper, we present the Concord algorithm, which provides a delay-sensitive solution for playout buffering. It records historical information and uses it to make short-term predictions about network delay with the aim of not reacting too quickly to short-lived delay variations. This allows an application-controlled tradeoff of packet lateness against buffering delay, suitable for applications which demand low delay but can tolerate or conceal a small amount of late packets. We present a selection of results from an extensive evaluation of Concord using Internet traffic traces. We explore the use of aging techniques to improve the effectiveness of the historical information and hence, the delay predictions. The results show that Concord can produce significant reductions in buffering delay and delay variations at the expense of packet lateness values of less than 1%.

User mobility management is one of the important components of mobile multimedia systems. In a cell-based network, a mobile should be able to seamlessly obtain transmission resources after handoff to a new basestation. This is essential for both service continuity and quality of service assurance. We present strategies for accommodating continuous service to mobile users through estimating resource requirements of potential handoff connections. A diverse mix of heterogeneous traffic with diverse resource requirements is considered. We investigate static and dynamic resource allocation schemes. The dynamic scheme probabilistically estimates the potential number of connections that will be handed off from neighboring cells, for each class of traffic. The performance of these strategies in terms of connection blocking probabilities for handoff and local new connection requests are evaluated. The performance is also compared to a scheme previously proposed by Yu and Leung (see IEEE Journal on Selected Areas in Communications, vol.15, p.1208-25, 1997). The results indicate that using dynamic estimation and allocation, we can significantly reduce the dropping probability for handoff connections.

User mobility management is one of the important components of mobile multimedia systems. In a cell-based network, a mobile should be able to seamlessly obtain transmission resources after handoff to a new base station. This is essential for both service continuity and quality of service assurance. In this paper, we present strategies for accommodating continuous service to mobile users through estimating resource requirements of potential handoff connections. A diverse mix of heterogeneous traffic with diverse resource requirements is considered. The investigate static and dynamic resource allocation schemes. The dynamic scheme probabilistically estimates the potential number of connections that will be handed off from neighboring cells, for each class of traffic. The performance of these strategies in terms of connection blocking probabilities for handoff and local new connection requests are evaluated. The performance is also compared to a scheme previously proposed by Yu and Leung (see IEEE J. Select. Areas Commun., vol.15, p.1208-25, 1997). The results indicate that using dynamic estimation and allocation, we can significantly reduce the dropping probability for handoff connections.

This paper describes the design and analysis of the scheduling algorithm for energy conserving medium access control (EC-MAC), which is a low-power medium access control (MAC) protocol for wireless and mobile ATM networks. We evaluate the scheduling algorithms that have been proposed for traditional ATM networks. Based on the structure of EC-MAC and the characteristics of wireless channel, we propose a new algorithm that can deal with the burst errors and the location-dependent errors. Most scheduling algorithms proposed for either wired or wireless networks were analyzed with homogeneous traffic or multimedia services with simplified traffic models. We analyze our scheduling algorithm with more realistic multimedia traffic models based on H.263 video traces and self-similar data traffic. One of the key goals of the scheduling algorithms is simplicity and fast implementation. Unlike the time-stamped based algorithms, our algorithm does not need to sort the virtual time, and thus, the complexity of the algorithm is reduced significantly.

Energy efficiency is an important issue in mobile wireless networks since the battery life of mobile terminals is limited. Conservation of battery power has been addressed using many techniques. This paper addresses energy efficiency in medium access control (MAC) protocols for wireless networks. The paper develops a framework to study the energy consumption of a MAC protocol from the transceiver usage perspective. This framework is then applied to compare the performance of a set of protocols that includes IEEE 802.11, energy-conserving MAC (EC-MAC), PRMA, multiservices dynamic reservation-TDMA (MDR-TDMA), and distributed-queueing request update multiple access (DQRUMA). The performance metrics considered are transmitter and receiver usage times for packet transmission and reception. The analysis here shows that protocols that aim to reduce the number of contentions perform better from a energy consumption perspective. The receiver usage time, however; tends to be higher for protocols that require the mobile to sense the medium before attempting transmission.

One critical issue in wireless systems is the efficient encoding of data in the presence of noise and Rayleigh fading. We analyze automatic repeat request (ARQ)-selective repeat and forward error correction control (FEC) algorithms using Markov chain model for mobile systems that can optimize the amount of battery energy consumed by transmitters. In this paper, we introduce an enhanced distributed algorithm which dynamically balances the combination of FEC and ARQ. The algorithm is shown to be suitable for both real time and non-real time multimedia environments. Extensive simulation indicates that our proposed algorithm outperforms existing schemes solely based on either FEC or ARQ and demonstrates the usefulness of our novel scheme.

Bit errors are fairly common during transmission in a wireless network.As a result, a straight-forwarcl application of existing packet fair queueing (PFQ) algorithms from wire-Iine to wireless networks results in an ine~cient use of ~he Kmited wireless bandwidth.In this paper, we propose a simple approach for adapting the existing PFQ algorithms for the wire]ine networks to provide the same kind of long-term fairness guarantees while making efficient use of the wireless bandwidth.In the proposed approach, long-term fairness guarantees are provided by supplementing the bandwidth given to sessions which have not received satisfactory service in the short -t erm due to poor quahty of their wireless channel.To efficiently keep track of the amount of supplemental bandwidth for each session, the paper introduces the concept of a long-term fairness server.This concept.also allows one to easily integrate the proposed approach with any of the existing PFQ algorithms.

Energy efficiency is crucial for wireless networks due to the limited battery life of mobile terminals. Power conservation techniques are commonly used in the hardware design of such systems. In addition, a low-pouter design of the entire protocol stack of wireless systems can significantly enhance energy efficiency and network utilization. This paper discusses recent advances and contributes novel ideas on power adaptive design of networking protocols.

Mobile computers typically have limited energy for computing and communications due to short battery lifetimes. Encoding, decoding, and transmission of video information require significant computing and communication resources. Low power encoding and decoding schemes have been researched extensively. In this paper, we focus on processing encoded video for transmission under low battery power conditions. Such processing, while conserving battery power, attempts to reduce deterioration of video quality.

This paper describes the design and analysis of the scheduling algorithm for EC-MAC (energy conserving medium access control) (Sivalingam et al.), a low-power medium access control (MAC) protocol for wireless and mobile ATM networks. Based on the structure of EC-MAC and the characteristics of the wireless channel, we propose a new algorithm which can deal with the bursty errors and the location-dependent errors. Most scheduling algorithms proposed for either wired or wireless networks were analyzed with homogeneous traffic or multimedia services with simplified traffic models. We analyze our scheduling algorithm with more realistic multimedia traffic models. One of the key goals of the scheduling algorithm is simplicity and fast implementation. Unlike the time-stamp based algorithm, our algorithm does not need to sort the virtual time, thus reducing the complexity of the algorithm significantly.

We present an algorithm to derive logic systems for various classes of path delay test problems. In these logic systems, the value of a signal represents the relevant conditions that occur during a set of consecutively applied vectors. Starting from a set of basic values for valid signals at primary inputs, a state transition graph is constructed to enumerate all possible signal states relevant to path activation that are reachable by Boolean operations. These states include all incompletely specified states, composed as combinations of basic values. A distinguishability analysis then finds all state-pairs that need to be distinguished during test generation. The final step minimizes the number of states. For forward and backward implications of test generation in combinational or sequential circuits, the procedure provides optimal logic systems. We define optimality as the smallest set of logic states that provides the least possible ambiguity in implications. Thus, an optimal set of logic states will minimize the number of backtracks in test generation. A 10-valued logic described in the literature is found to be optimal for generating tests for single path delay faults. Other problems addressed in this paper include compact test generation through activation of many single path delay faults, test generation for rated-clock test application, and test generation for multiple path delay faults. The limitations and capabilities of various logic systems are illustrated by examples.

Even though hardware accelerators are common in very large scale integration (VLSI) computer-aided design (CAD), fault simulation is a notable exception because of limited availability of memory, the need for dynamic memory management and the complexity of the algorithms themselves. Although simplified fault simulation algorithms that assume a zero delay circuit model can be accelerated, their applicability is limited. Most application specific integrated circuits (ASIC's) designed in industry today have on-chip memory blocks of different dimensions and characteristics, enhancing the complexity of a fault simulator. In this paper, we present a multiple delay algorithm for concurrent fault simulation of logic gates and functional memory blocks. This algorithm has been implemented on the microprogrammable accelerator for rapid simulation (MARS) hardware accelerator system with a 22 MHz clock and a capacity to simulate circuits with millions of devices. Speedup factors of 20 to 30 are easily achieved when compared to software simulators running on comparable hardware platforms and using identical circuit models.

Current test generation algorithms for path delay faults assume a variable-clock methodology for test application. Two-vector test sequences assume that the combinational logic reaches a steady state following the first vector before the second vector is applied. While such tests may be acceptable for combinational circuits, their use for nonscan sequential circuit testing is impractical. A rated-clock path delay simulator shows a large drop in coverage for vectors obtained from existing test generators that assume a variable clock. A new test generation algorithm provides valid tests for uniform rated-clock test application. In this algorithm, signals are represented for three-vector sequences. The test generation procedure activates a target path from input to output using the three-vector algebra. For an effective backward justification, we derive an optimal 41-valued algebra. This is the first time, rated-clock tests for large circuits are obtained. Results for ISCAS-89 benchmarks show that rated-clock tests cover some longest, or close to longest, paths.

We propose a novel channel management algorithm, called distributed load balancing with selective borrowing (D-LBSB), for cellular mobile networks. As an underlying approach, we start with a fixed channel assignment scheme where each cell is initially allocated a set of local channels, each to be assigned on demand to a user in that cell. The novelty of our D-LBSB scheme lies in handling the hot cell problem because it proposes to migrate unused channels from suitable cold cells to the hot ones through a distributed channel borrowing algorithm. With the help of a Markov model, the probability of a cell being hot and the call blocking probability in a cell are derived. Detailed simulation experiments are carried out in order to evaluate our proposed methodology. Performance comparison reveals that the D-LBSB scheme performs better than a centralized version in an overloaded system, and significantly better than several other existing schemes in terms of call blocking probability, under moderate and heavy loads.

In this paper, we advocate the use, propose the design, and describe the implementation of an asymmetric transport-layer protocol for mobile systems. In an asymmetrically designed protocol, peer functions are implemented through algorithms and procedures that are of substantially different complexity, with the lower complexity procedures used on the mobile device. We have devised and implemented an example of such a communication protocol, termed by us Mobile-TCP that provides the TCP functionality. Although Mobile-TCP is based on the indirect interaction model, the semantics of the TCP protocol are preserved.

We study the performance of a unified power control and forward error correction control algorithm for mobile radio systems that attempts to maximize system capacity and minimize transmitter power utilization while satisfying user defined quality of service constraints. The algorithm is distributed, with each individual transmitter-receiver pair determining its own operating point with respect to power and error control parameters. Simulation results from a cellular system with mobile users show that this unified algorithm outperforms the schemes that use power control alone.

There is an emergent interest in providing mobile users with ubiquitous wireless access to multimedia information. In this paper we present a network architecture and protocols to achieve this goal and describe their implementation in a prototype network called SWAN. Our network model assumes end to end ATM connectivity. Thus, the key question we address is how best to enhance ATM to support host mobility and wireless access.

We present a new acknowledgment strategy to improve the performance of TCP sessions that originate or terminate in noisy wireless networks for mobile computers. This acknowledgment strategy allows the TCP source to distinguish between losses due to congestion and losses due to corruption. With this distinction, the source can reduce its sending rate when congestion occurs, and quickly retransmit when corruption occurs. Without this distinction, TCP throughput is shown to suffer significantly over a path with a large bandwidth-delay product. The strategy is also appropriate for dealing with losses due to hand-offs of a mobile computer from one wireless cell to another.

In the last decade the growth of wireless communication has been rapid. One critical issue in wireless systems is the efficient encoding of data to ensure correctness in the presence of noise and multipath fading. We propose some encoding schemes which span the FEC/ARQ spectrum and analyze them with respect to throughput and delay. We conclude with an adaptive algorithm for choosing the optimal encoding scheme based on observed error rates.

Abstract Programming applications in computer‐aided design of VLSI are difficult on parallel architectures, especially pipelined implementations derived from their sequential counterparts by algorithmic partitioning. The difficulty is primarily due to lack of good program development environments and tools. Our solution, applicable to message‐passing architectures, is based upon a definition of a broad class of non‐linear pipeline configurations and an asynchronous data‐driven model for pipeline stage interactions. It provides object‐oriented definitions of stages and interconnecting channels. These objects are embedded in C++ so that the correctness of application programs can be tested on a workstation in a simulated environment. The simulation is instrumented to provide data useful in assessing relative computational loading and balancing of stages. Thus a large part of program development can take place in the environment of a workstation familiar to the programmer. A non‐trivial application is developed to illustrate these ideas.

A new test generation technique for path delay faults in circuits employing scan/hold type flip-flops is presented. Reduced ordered binary decision diagrams (ROBDDs) are used to represent Boolean functions realized by all signals in the circuit, as well as to represent the constraints to be satisfied by the delay fault test. Two faults are considered for each path in the circuit. For each fault, a pair of constraint functions, corresponding to the two time frames that constitute a transition, is evaluated. If the constraint function in the second time frame is non-null, robust-hazard-free-test generation for the delay fault is attempted. A robust test thus generated belongs either to the class of fully transitional path (FTP) tests or to the class of single input transition (SIT) tests. If a robust test cannot be found, the existence of a non-robust test is checked. Boolean algebraic manipulation of the constraint functions guarantees that if neither robust nor non-robust tests exist, the fault is undetectable. In its present form the method is applicable to all circuits that are amenable to analysis using ROBDDs. An implementation of this technique is used to analyze delay fault testability of ISCAS '89 benchmark circuits. These results show that the algebraic technique is one to two orders of magnitude faster than previously reported methods based on branch-and-bound algorithms.>

The need for tight coupling between methodologies for design-and-test, VLSI technology, architecture and CAD has never been as strong as it is today. The design and test challenges of today are due to the sudden demand for systems that deal with multimedia, high speed networking and computing, and wireless communications, to name a few. The competitive nature of these businesses puts enormous pressure on electronic system and integrated circuit designers and test engineers to deliver reliable and complex systems with very short design intervals. Extremely large scales of integration, very high operating speeds and the proliferation of analog or mixed analog-digital designs have given rise to new problems of design verification, testing and packaging technologies.>

Investigates channel allocation policies that choose among incoming handover requests to a particular cell. Within a class of non-reserving policies that efficiently utilize the scarce channel resources, the authors identify a most critical first policy that is optimal with respect to handover failure probability. The proof of optimality is accompanied by the description of two techniques to realize the policy in practice. Simulation results that demonstrate its improvement over previous policies are presented as well.

We demonstrate the feasibility of a distributed implementation of the Goldberg-Tarjan algorithm for finding the maximum flow in a network. Unlike other parallel implementations of this algorithm, where the network graph is partitioned among many processors, we partition the algorithm among processors arranged in a pipeline. The network graph data are distributed among the processors according to local requirements. The partitioned algorithm is implemented on six processors within a 15-processor pipelined message-passing multicomputer operating at 5 MHz. We used randomly generated networks with integer capacities as examples. Performance estimates based upon a six-processor pipelined implementation indicated a speedup between 3.8 and 5.9 over a single processor.>

A sequential circuit teat generation program ts paratleltzed to run on a network of Spare 2 workstations con.

For a given set of vectors, the guaranteed failure frequency of a synchronous sequential circuit is defined. This frequency is obtained from multiple delay logic simulation by selectively suppressing timing hazards. Any path delay fault testable by the vectors, if present, is guaranteed to be detected if the tests were run at this frequency.>

A sequential circuit test generation program is parallelized to run on a network of Sparc 2 workstations connected through ethernet. The program attempts to compute tests to detect all faults in a given list. The fault list is equally divided among the processors. The entire process consists of a series of parallel computing passes with synchronization occurring between passes. During a pass, each processor independently generates test sequencies for the assigned faults through vector generation and fault simulation. A fixed per-fault CPU time limit is used within a pass. Faults requiring more time are abandoned for later passes. Each processor simulates the entire fault list with its vectors and communicates the list of undetected faults to all other processors. Processors then combine these fault lists to create a list of faults that were not detected by all processors. This list is again equally divided and the next pass begins with a larger per-fault time limit for test generation. The process stops after either the required fault coverage is achieved or the pass with given maximum per-fault time limit is completed. Some benchmark results are given to show the advantage of distributed system for large circuits. Finally, the authors study a speedup model that considers duplicated computation and interprocessor communication.>

This paper describes an ROBDD-based distributed test generation algorithm for combinational circuits. This technique lends itself to a natural partitioning of both the fault list and the circuit across processors. A preliminary implementation on an Ethernet-connected SPARC2 workstation cluster shows the feasibility of the method.

We use a 23-value logic system to generate robust path delay tests. Each test is successively augmented to detect as many path faults as possible. Other features of the test generator are a podem-like branch and bound search for test, an efficient path designation based on ordering of paths, and an algorithmic selection of secondary target faults for augmenting the tests to cover multiple faults. Results for ISCAS '89 benchmarks are given.>

The authors consider the problem of selecting an implementation of each circuit module from a cell library so as to satisfy overall delay and area (or delay and power) requirements. Two versions of the circuit implementation problem, the basic circuit implementation problem and the general circuit implementation problem, are shown to be NP-hard. A pseudo-polynomial-time algorithm for the basic circuits is developed, and heuristics for the basic circuit implementation problem on general circuits are formulated and experimented with.>

To analyze path delay faults in synchronous sequential circuits, stimuli are simulated in a dual-vector mode. The signal states represent the logic and transition conditions for two consecutive vectors. After the simulation of each vector, only the activated paths are traced and the corresponding fault effect, if propagated to a flip-flop, is added to its fault list. A path numbering scheme avoids storage of path data which can be generated, if needed, from the path number. The simulation is independent of the specific delays of the combinational elements, and either robust or nonrobust detection can be simulated as options to the user. For robust simulation, an update rule for state variables is proposed whereby a flip-flop is updated with its correct value, provided it is a destination of at least one robustly activated path. This rule gives a higher and more realistic coverage of robustly detected faults. Experimental results verify the effectiveness of the simulator.>

The factorization of sparse matrices is used in the inner loop of many engineering algorithms. including circuit simulation. This time consuming operation can be speeded up by utilizing multiprocessor architectures. Distributed memory architectures can overcome the memory bottleneck normally associated with shared memory machines but require a careful distribution of matrix data to the processors. The authors present partitioning schemes that distribute the rows of the matrix to processors to allow a better utilization of the processing resources. They also present bounds on the speedup achieveable with partitioned matrices. They demonstrate that a good partitioning strategy coupled with more sophisticated scheduling algorithms improves the overall processor utilization.>

The problem of sparse matrix decomposition using distributed memory multiprocessors is addressed. The data partitioning scheme is simple and is based on equalizing the load among the processors. A new O(n log n) task scheduling heuristic with provably deadlock-free properties is presented. The key idea is the ordering of nodes in a task graph that represents the matrix decomposition steps in a levelized manner, based on a new measure, delta the remaining completion time. The method tends to minimize the idle time of processors by revising the overall decomposition schedule by permitting the execution of tasks within these idle periods. For large sparse matrices, the analysis and simulation results show that a multiprocessor with even a small number of processors will exceed the performance of a supercomputer like the Cray X-MP.>

Circuit simulation uses a substantial amount of computation time to simulate a large circuit. A multiprocessor architecture can provide a cost effective way of speeding up the inner loop of the algorithm. A parallel processing architecture for circuit simulation algorithms that is designed as an accelerator system for workstations is presented. The architecture allows the inner loop of the circuit simulation algorithm, assembling the equations that describe the circuit and solving them, to be executed at high speed. It solves the large sets of equations using LU decomposition, which is both accurate and robust. The way in which the algorithms are supported by the distributed memory architecture and how this is reflected in the architecture's implementation are discussed.>

Novel models and algorithms for MOS transmission gates, buses and functional memories for use in statistical fault analysis (Stafan) are described. A bus is modeled as a multiple input multiplexer with feedback to account for its memory state. A CMOS transmission gate, modeled as a unidirectional device, always feeds into a bus that processes the high impedance state. Novel algorithms are devised to compute input observabilities of functional memory blocks. A novel implementation of Stafan algorithms is described for the MARS hardware accelerator environment. MARs is run in the true-value simulation mode and sends signal changes for all lines through a Unix pipe to the Stafan process running on a SUN workstation. The Stafan process computes controllabilities, observabilities, detection probabilities, and fault coverage. MARS and Stafan thus run as a pipeline. Results on several CMOS circuits are obtained and compared with those obtained from a concurrent fault simulator.>

Shared memory multiprocessors have failed to achieve large speedups because of the processor to memory bottleneck, which gets worse as more processors are used. The authors match a distributed memory architecture to the problem to overcome the processor to memory bottleneck. A study is made of parallel source row and target row directed matrix factorization algorithms where the operations are precompiled at the row level. The authors' contribution is in the formulation and analysis of these factorization algorithms for a distributed memory architecture. The authors evaluate the effectiveness of their approach for processor utilization, memory accesses and communication costs for large matrices corresponding to real VLSI circuits. It is shown quantitatively, using the above metrics, that the source row factorization scheme is the most effective.>

Several heuristic schemes for storing large sparse matrices in memory are presented. These heuristics exploit the distribution of the zero and non-zero elements of the matrix rather than just the number of non-zeros. Their performance ranges from very high packing density and acceptable processing time to extremely fast but acceptable packing density. The best packing density is comparable to the Ziegler scheme but at only 20% of the CPU time. The fastest scheme is about two orders of magnitude faster than the Ziegler method but achieves only about 60% of its packing density. Example matrices from circuit simulation data illustrate the superiority of the authors' schemes.>

Multiple-delay logic simulation algorithms developed for the microprogrammable accelerator for rapid simulations (MARS) hardware simulator are discussed. In particular, timing-analysis algorithms for event cancellations, spike and race analyses, and oscillation detection are described. It is shown how a reconfigurable set of processors, called processing elements (PEs), can be arranged in a pipelined configuration to implement these algorithms. The algorithms operate within the partitioned-memory, message-passing architecture of MARS. Three logic simulators-two multiple delay and one unit delay-have been implemented using slightly different configuration of the available PEs. In these simulators, VLSI chips are modeled at the gate level with accurate rise/fall delays assigned to each logic primitive. On-chip memory blocks are modeled functionally and are integrated into the simulation framework. The MARS hardware simulator has been tested on many VLSI chip designs and has demonstrated a speed improvement of about 50 times that of an Amdahl 5870 system running a production-quality software simulator while retaining the accuracy of simulations.>

It is shown how the substitution of a partial order facilitates automatic modeling in switch-level simulators that use the traditional total ordering of strengths for resolving conflicts between opposing signals while increasing the accuracy of that model. Minimization techniques are described that reduce the number of required modeling strengths to acceptable levels. As a result, the use of partially ordered strengths does not significantly degrade simulation performance. It is also shown how to rearrange the computations performed during switch-level simulation to yield a nearly twofold increase in speed for good circuit simulation. A switch-level simulator using this algorithm with partially ordered strengths has been successfully used to verify several full-custom industrial designs.>

In this paper, we describe a hardware multiple delay logic simulator that incorporates efficient timing analyses algorithms for event cancellations, spike and race analyses and oscillation detection. The algorithms are implemented on a set of reconfigurable processors, arranged in a pipelined configuration. Spike analysis is accomplished by dynamic pulse width measurement. Both zero and non-zero delay oscillations are detected. Results of simulating industrial VLSI chips are presented to illustrate the effectiveness of the algorithms with minimal performance penalty.

The authors report on efforts to put a connected speech recognition application on the MARS hardware accelerator. The beam-search algorithm chosen for this purpose was decomposed on a functional basis, not on a data-partitioning basis as in other attempts. This allows for easy synchronization and static load balancing. Further flexibility is provided by retaining the hierarchical structure of the speech graph. The implementation is being tested on a 1000-word vocabulary and preprocessed input data.>

The authors describe fault simulation algorithms for the MARS hardware accelerator. Two algorithms are considered. The first, serial fault simulation, has a performance that is linear in the number of faults. Its performance is easily predictable and it takes full advantage of the true-value simulation speed of the accelerator; it is also easy to implement. The second algorithm, concurrent fault simulation, is found to have a performance that is nonlinear in the number of faults. It also requires either a large amount of memory or a dynamic memory management, both of which are difficult to implement in an accelerator. Yet the concurrent method has the advantage of more efficient event processing and less duplicated effort. Combining the features of both algorithms, a fixed-memory, multipass, concurrent algorithm is developed for MARS.>

A description is given of the application of a concurrent fault simulator to automatic test vector generation. As faults are simulated in the fault simulator a cost function is simultaneously computed. A simple cost function is the distance (in terms of the number of gates and flip-flops) of a fault effect from a primary output. The input vector is then modified to reduce the cost function until a test is found. Experimental results are presented showing the effectiveness of this method in generating tests for combinational and sequential circuits. By defining suitable cost functions, it has been possible to generate: (1) initialization sequences; (2) tests for a group of faults; and (3) a test for a given fault. Even asynchronous sequential circuits can be handled by this approach.>

A key idea in switch-level simulation is the use of a total ordering of signal strengths to resolve conflicts between opposing signals. For many circuits, however, it is not possible to assign such strengths to circuit elements in a logically consistent fashion without user intervention. It is shown that the use of a partial ordering of strengths avoids these difficulties and allows modeling to be done automatically. The authors also discuss the need to minimize the number of distinct strengths needed to model a circuit, because simulation times are affected by the number of strengths being used. This is especially important for compiled switch-level simulators that generate representations whose size is proportional to the number of strengths. Statistics on the application of these ideas to industrial chips are presented.>

An algorithm called RAFT (recursive algorithm for fault tolerance) for achieving fault tolerance in multiprocessor systems is described. Through the use of a combination of dynamic space- and time- redundancy techniques, RAFT achieves fault tolerance in the presence of permanent as well as intermittent faults. Performance and reliability of multiprocessor systems using RAFT are determined as a function of individual processor reliability and the total number of fault modes in a processor. RAFT-based systems are superior to triple modular redundancy (TMR) systems in hardware economy and provide comparable reliability. A multiprocessor architecture adopting RAFT is given.>

MARS (Microprogrammable Accelerator for Rapid Simulations) is a multiprocessor based hardware accelerator capable of efficiently implementing a wide range of computationally complex algorithms. Its architecture is ideally suited for performing event driven simulations of VLSI circuits. The highly pipelined and parallel architecture of MARS provides a performance comparable to existing hardware simulation engines while its highly flexible architecture supports a wide range of applications. Flexibility is achieved through custom designed microprogrammable and reconfigurable VLSI processors. Logic simulation performance of about one million events per second is easily achievable.

RAFT is a recursive algorithm for fault tolerance that uses a combination of dynamic space and time redundancy techniques for detecting faulty processors and recovering from errors. U * is a multicomputer testbed consisting of a network of AT&T 3B2 computers running a network operating system based on the UNIX system. This paper describes a software implementation of RAFT on U * , and demonstrates the effectiveness of a RAFT-like scheme for designing fault-tolerant multicomputer systems. Results of Monte Carlo experiments, conducted on this system that validated the theoretical basis of RAFT, are presented. Experimentally observed performance penalty, incurred due to fault tolerance, is also presented.

This paper describes models for concurrency and interpartition communication in a hardware logic simulator implemented using multiprocessors. Software simulation data from production VLSI chips were analyzed in the context of a multiprocessor environment to obtain experimental values for concurrency and communication. The VLSI chips were randomly partitioned in the above experiments. The concurrency observed is significantly lower than the maximum achievable theoretically. This effect was more pronounced for circuits with lower activity. The effect of different simulators (unit and multiple delay), on concurrency and communication, is explained. Finally, a partitioning heuristic whose objective is to enhance concurrency and minimize communication is proposed. It makes use of the circuit topology and the delay information in a simulation database.

This paper describes two logic minimization algorithms. CAMP (Computer Aided Minimization Procedure) minimizes single functions. The minterms are covered either by essential prime implicants or by selective prime implicants. The two types of prime implicants are determined one at a time thus completely avoiding the computationally expensive covering problem. The adjacency of a minterm, that depends upon the proximity of this minterm with respect to other minterms on the Karnaugh map, guides the determination of prime implicants. This procedure is nonheuristic and has proved to be very efficient for large number of input variables. The multiple output minimization (MOM) algorithm generates the product terms with maximum sharing between the output functions. In addition to using adjacency, this procedure is also guided by the frequency with which a minterm is used by the functions. Examples show the performance of this algorithm to be equal or better than many other minimization procedures.

The dynamics of today's electronics industry introduces enormous pressure on chip designers to come up with chip designs in a very limited time. This is due partly to the short life cycle of application specific products in the marketplace. The availability of powerful graphics processors and microprocessors with processing powers comparable to minicomputers has introduced several stand alone workstations into the design arena. Designer productivity is improved to a great extent by the provision of computer-aided design tools that take a product from concept all the way through test at a single design station. This improvement in productivity is very much felt while designing less complex chips. However, corporations that turn out highly complex chips like 32-bit microprocessors and their peripheral chips still rely heavily on the processing powers of powerful mainframes or supercomputers. It is design cases such as these that will question the adequacy and practicability of introducing workstations into the culture of the compcenter-based design methodologies. To them, workstations represent yet another level of computing power which has to be integrated into the design environment.

Due to inaccuracies in gate level models of VLSI digital circuits, current practice is to use transistor level simulators to analyze VLSI digital circuits. The inaccuracies of gate level models are even more severe when faults in digital circuits are considered. For this reason, recently several researchers have proposed the use of test pattern generation from digital circuits described at the transistor level. In this paper an efficient test pattern generation procedure for digital circuits described at the transistor level is given.

Abstract A probabilistic model is developed for studying the problem of routing printed circuits. The model, which uses the density of blockages on the carrier as a parameter, is based on the path‐searching mechanism of Lee's algorithm. Lee's algorithm is used in our analysis because it belongs to a class of pathfinding procedures which guarantee finding a path between two given points if one exists. It is shown that the routing probability, RM(d), is bounded above by PM(d), where PM(d) is the probability of existence of an arbitrary path of ideal Manhattan distance d from a given source point. Analytical computation shows that PM(d) is practically one until a density of about 35%. After this it sharply reduces, reaching a negligible value at a density of 43% for all but very small values of d. Some experiments related to the verification of the model are described. These experimental results show good agreement with the theoretically derived probabilities.

In this correspondence a new routing cost function is defined which is a function of local blockage density in addition to path length. A parameter α specifies the degree to which density is to influence the cost. The use of such a cost function results in what we refer to as a density router. The classical Lee router is a special case of the density router with α equal to 0. We present four performance measures (two of which are based on the density of blockages) for comparing the performance of the classical Lee router with that of the density router. It is experimentally determined that a value of a of about 1.25 optimizes our cost function for the density router when evaluated according to each of the four performance measures and for the board model assumed.

It is shown that by a proper selection of the probabilities of 0 and 1 at the inputs, the efficiency of random test generation can be improved. This correspondence includes some results describing the testing of actual logic networks used in a computer.

In this paper the random test generation method for large logic circuits is analyzed. Formulas for the detection probability and the number of random input patterns required to complete the test generation with a high probability are obtained for an irredundant fan-out-free combinational network tree consisting of identical n-input NAND gates. The quantitative estimates for the number of random input patterns required for test generation appear to depend upon the number of levels in the circuit and the fan-ins of the gates. Experimental results for actual computer logic circuits are given and show the validity of the approach.

A test generation system, developed for the logic boards of the Illiac IV computer, is described. The system combines the test generation by random patterns and the D-algorithm. Some results are given to illustrate the effectiveness of this approach.