Technical Reports of the Computer Science Department
Permanent URI for this collectionhttp://hdl.handle.net/1903/6
Browse
Item Accurate Anchor-Free Node Localization in Wireless Sensor Networks(2006-02-10T16:51:23Z) Youssef, Adel; Younis, Mohamed; Agrawala, AshokThere has been a growing interest in the applications of wireless sensor networks in unattended environments. In such applications, sensor nodes are usually deployed randomly in an area of interest. Knowledge of accurate node location is essential in such network setups in order to correlate the reported data to the origin of the sensed phenomena. In addition, awareness of the nodes’ positions can enable employing efficient management strategies such as geographic routing and conducting important analysis such as node coverage properties. In this paper, we present an efficient anchor-free protocol for localization in wireless sensor networks. Each node discovers its neighbors that are within its transmission range and estimates their ranges. Our algorithm fuses local range measurements in order to form a network wide unified coordinate systems while minimizing the overhead incurred at the deployed sensors. Scalability is achieved through grouping sensors into clusters. Simulation results show that the proposed protocol achieves precise localization of sensors and maintains consistent error margins. In addition, we capture the effect of error accumulation of the node’s range estimates and network’s size and connectivity on the overall accuracy of the unified coordinate system.Item Capacity and Variability Analysis of the IEEE 802.11 MAC Protocol(2004-04-19) Yeo, Jihwang; Agrawala, Ashok{\em Packet error} in the IEEE 802.11 network %which is due to non-ideal channel condition and wireless device variability, is one source of performance degradation and its variability. %Therefore the effect of packet errors, along with {\em collision %avoidance} and {\em hidden terminals}, is among the most important %considerations in performance anaylsis of the 802.11 MAC protocol. Most of the previous works study how {\em collision avoidance} and {\em hidden terminals} affect 802.11 performance metrics, such as probability of a collision and saturation throughput. In this paper we focus on the effect of packet errors on capacity and variability of the 802.11 MAC protocol. We develope a new analytical model, called $p_e$-Model, by extending the existing model (Tay and Chua's model) to incorporate {\em packet error probability} $p_e$. With $p_e$-Model, we successfully analyze capacity and variability of the 802.11 MAC protocol. The variability analysis shows that increasing packet error probability by $\Delta p_e$ has more effect on saturation throughput, than adding $0.5 W \Delta p_e$ stations, where $W$ is the minimum contention window size, We also show the numerical validation of $p_e$-Model with 802.11 MAC-level simulator. (UMIACS-TR-2003-45)Item CARS: A New Code Generation Framework for Clustered ILP Processors(2000-08-08) Kailas, Krishnan; Ebcioglu, Kemal; Agrawala, AshokClustered ILP processors are characterized by a large number of non-centralized on-chip resources grouped into clusters. Traditional code generation schemes for these processors consist of multiple phases for cluster assignment, register allocation and instruction scheduling. Most of these approaches need additional re-scheduling phases because they often do not impose finite resource constraints in all phases of code generation. These phase-ordered solutions have several drawbacks, resulting in the generation of poor performance code. Moreover, the iterative/back-tracking algorithms used in some of these schemes have large running times. In this report we present CARS, a code generation framework for Clustered ILP processors, which combines the cluster assignment, register allocation, and instruction scheduling phases into a single code generation phase, thereby eliminating the problems associated with phase-ordered solutions. The CARS algorithm explicitly takes into account all the resource constraints at each cluster scheduling step to reduce spilling and to avoid iterative re-scheduling steps. We also present a new on-the-fly register allocation scheme developed for CARS. We describe an implementation of the proposed code generation framework and the results of a performance evaluation study using the SPEC95/2000 and MediaBench benchmarks. (Also cross-referenced as UMIACS-TR-2000-55)Item Characterizing the IEEE 802.11 Traffic: The Wireless Side(2004-04-19) Yeo, Jihwang; Youssef, Moustafa; Agrawala, AshokMany studies on measurement and characterization of wireless LANs have been performed recently. Most of these measurements have been conducted from the wired portion of the network based on wired monitoring or SNMP statistics. In this paper we argue that traffic measurements from a wireless vantage point in the network are more appropriate than wired measurements or SNMP statistics, to expose the wireless medium characteristics and their impact on the traffic patterns. While it is easier to make consistent measurements in the wired part of a network, such measurements can not observe the significant vagaries present in the wireless medium itself. As a consequence constructing an accurate measurement system from a wireless vantage point is important but usually quite difficult due to the noisy wireless channel. In our work we have explored the various issues in implementing such a system to monitor traffic in an IEEE 802.11 based wireless network. We show the effectiveness of the wireless monitoring by quantitatively comparing it with SNMP and measurements at wired vantage points. We also show the analysis of a typical computer science department network traffic using the wireless monitoring technique. Our analysis reveals rich information about the PHY/MAC layers of the IEEE 802.11 protocol such as the typical traffic mix of different frame types, their temporal characteristics, correlation with the user activities and the error characteristics of the wireless medium. Moreover, we identify anomalies in the operation of the IEEE 802.11 MAC protocol. Our results show excessive retransmissions of some management frame types reducing the useful throughput of the wireless network. We also find that some features of the protocol, which were designed to reduce the retransmission errors, are not used. In addition, most of the clients fail to adapt the data rate according to the signal condition between them and the access point, which further reduce the useful throughput. (UMIACS-TR-2004-15)Item Cycle Synchronization in Cyclone Networks(2001-05-10) Szajda, Doug; Hawkin, Simon; Agrawala, AshokNetworks with time-cyclic allocation of node resources (e.g. SONET or a wireless network using TDMA media access scheduling) require a degree of synchronization in order to guarantee that cycle lengths and drifts remain within acceptable tolerances. Cyclone is a class of such networks. By requiring applications to reserve resources in both time and space, a balance is achieved between arriving and departing flows, ensuring a lack of congestion and eliminating the need for flow control. This paper presents a lightweight cycle synchronization algorithm for Cyclone networks, and shows through both theoretical analysis and simulation that even in the presence of timing errors, both cycle length jitter and cycle phase differences fall well within tolerable levels. (Cross-referenced as UMIACS-TR-2001-17)Item Dynamic Real-Time Scheduling in Distributed Environments(2001-10-10) Elsharkawy, Sameh M.; Agrawala, AshokReal-time applications are becoming increasingly popular in distributed environments. These real-time applications range from hard real-time applications with periodic or aperiodic tasks and intertask relative timing constraints to soft real-time applications with best effort timing requirements. This paper introduces a complete system model for scheduling and dispatching hard as well as soft real-time tasks with intertask temporal dependencies in distributed environments. The model uses a dynamic time based off-line scheduler to verify the feasibility of a distributed hard real-time task set, and a parametric run-time kernel that guarantees the temporally determinate dispatching of hard real-time task instances and best effort performance for soft real-time task instances. The use of the dynamic time based scheduling, provides off-line guarantees for all the timing requirements of the hard real-time tasks while the parametric dispatching mechanism maintains a flexible run-time environment that makes use of the slack time with a limited overhead. (Also cross-referenced as UMIACS-TR-2001-65)Item Efficient Data Processing using Cross Layer Hints(2002-12-19) Banerjee, Suman; Agrawala, Ashok; Kramer, Michael J.Conventional network stacks define a layered architecture, where each layer implements a set of services and exports a well-defined interface to be used by its immediate upper layer. A key design choice of the layered architecture has been to provide isolation between the functional modules of distinct layers. While such an architecture provides an useful abstraction for system development, the strict isolation of this layered architecture limits the flexibility of tailoring the behavior of the lower layers of the stack to the needs of the application. In this paper we define a new architecture, called X-Tags, which allows flexible interaction between layers for cooperative data processing without impacting the isolation property. In this architecture, applications use special tags to provide semantic hints for data processing to lower layers. We motivate the usefulness of this architecture by describing ts applicability to some emerging applications. UMIACS-TR-2002-59Item Efficient Time-Based Topology-Dependent Scheduling for Radio Packet Networks(2002-08-01) Nadeem, Tamer; Agrawala, AshokIn Radio Packet Network (RPN), unconstrained transmission may lead to collision of two or more packets. Time Division Multiple Access (TDMA) protocol is a common used protocol to schedule collision-free transmission for such networks. TDMA transmission allows a number of users to access a single radio channel without interference by allocating unique time slots to each user. In TDMA network, time is divided into frames and a frame consists of time slots. For networks where each node is a neighbor for all the other nodes, each node should assign a different time slot in TDMA frame to transmit in it to have collision-free transmission. Typically, those time slots are ended by \emph{guard times} for propagation delays. Those guard times are fixed for all time slots regardless the actual needed propagation delays. In this paper, we propose a topology-dependent algorithm that automatically schedules collision-free channel access and specify the time instant when a node is to send a packet. We use variable guard times, instead of the fixed ones, calculated using the actual needed propagation delays between sources and destinations. We show that with such scheduling algorithm, a 90% saving in the original guard times could be achieved that increases the network utilization by about 10%. Also UMIACS-TR-2002-57Item Handling Samples Correlation in the Horus System(2003-08-01) Youssef, Moustafa; Agrawala, AshokWe present an autoregressive model for modeling samples autocorrelation from the same access point in WLAN location determination systems. Our work is in the context of the Horus system, which is a probabilistic WLAN location determination system. We show that the autocorrelation between consecutive samples from the same access point can be as high as 0.9. Using our model, we describe a technique to use multiple signal strength samples from each access point, taking the high autocorrelation into account, to achieve better accuracy. Implementation of the technique in the Horus system shows that the average system accuracy is increased by more than 50%. Our results show that assuming independence of samples from the same access point can lead to degraded performance as the number of samples used in the estimation algorithm is increased, due to the wrong independence assumption. We also discuss how to incorporate the new technique with other algorithms for enhancing the performance of WLAN location determination systems. (UMIACS-TR-2003-75)Item Measuring Traffic on the Wireless Medium: Experience and Pitfalls(2003-01-21) Yeo, Jihwang; Banerjee, Suman; Agrawala, AshokA number of measurement studies have examined traffic characteristics in wireless networks. Most of these measurements have been conducted from the wired portion of the network. In this paper we argue that such measurements are not sufficient to expose either the characteristics of the wireless medium or how such characteristics impact traffic patterns. While it is easier to make consistent measurements in the wired part of a network, such measurements can not observe the significant vagaries present in the wireless medium itself. As a consequence constructing an efficient and accurate measurement system from a wireless vantage point is important but usually quite difficult. In our work we have explored the various issues in implementing such a system to monitor traffic in an 802.11 based wireless network. We identify different challenges in making such measurements and provide detailed experimental evidence in their supports. Our work shows that the wireless measurement allows us to infer much richer information about the medium characteristics than is possible with a measurements made on the wired part of the network. We apply our measurement technique to study the end-to-end wireless network delay. We show that wireless monitoring can effectively identify the causes of end-to-end delays. (UMIACS-TR-2002-101)Item Multiscale Analysis for Wireless LAN Traffic Characterization(2004-04-19) Yeo, Jihwang; Agrawala, AshokIn this survey paper, we overview the various network traffic models, especially focusing on the multiscale analysis. By multiscale analysis we mean wavelet-based self-similar and multifractal analysis. Multiscale analysis is advantageous in that it can reveal the scaling behavior of the traffic on large time scale, at the same time characterize small-scale irregularity. We also discuss how we can apply this analysis technique to wireless LAN traffic characterization. (UMIACS-TR-2004-16)Item On the Optimality of WLAN Location Determination Systems(2003-04-04) Youssef, Moustafa A.; Agrawala, AshokThis paper presents a general analysis for the performance of WLAN location determination systems. In particular, we present an analytical method for calculating the average distance error and probability of error of WLAN location determination systems. These expressions are obtained with no assumptions regarding the distribution of signal strength or the probability of the user being at a specific location, which is usually taken to be a uniform distribution over all the possible locations in current WLAN location determination systems. We use these expressions to find the optimal strategy to estimate the user location and to prove formally that probabilistic techniques give more accuracy than deterministic techniques, which has been taken for granted without proof for a long time. The analytical results are validated through simulation experiments. We also study the effect of the assumption that the user position follows a uniform distribution over the set of possible locations on the accuracy of WLAN location determination systems. The results show that knowing the probability distribution of the user position can reduce the number of access points required to obtain a given accuracy. However, with a high density of access points, the performance of a WLAN location determination system is consistent under different probability distributions for the user position. UMIACS-TR-2003-29Item A Probabilistic Clustering-Based Indoor Location Determination System(2002-04-04) Youssef, Moustafa A.; Agrawala, Ashok; Shankar, A. Udaya; Noh, Sam H.We present an indoor location determination system based on signal strength probability distributions for tackling the noisy wireless channel and clustering to reduce computation requirements. We provide two implementation techniques, namely, Joint Clustering and Incremental Triangulation and describe their tradeoffs in terms of location determination accuracy and computation requirement. Both techniques have been incorporated in two implemented context-aware systems: User Positioning System and the Rover System, both running on Compaq iPAQ Pocket PC's with Familiar distribution of Linux for PDA's. The results obtained show that both techniques give the user location with over 90% accuracy to within 7 feet with very low computation requirements, hence enabling a set of context-aware applications. Also UMIACS-TR-2002-30Item Rover Technology: Enabling Scalable Location-Aware Computing(2002-01-31) Banerjee, Suman; Agarwal, Sulabh; Kamel, Kevin; Kochut, Andrzej; Kommareddy, Christopher; Nadeem, Tamer; Thakkar, Pankaj; Trinh, Bao; Youssef, Adel; Youssef, Moustafa; Larsen, Ron; Shankar, A. Udaya; Agrawala, AshokLocation-aware computing involves the automatic tailoring of information and services based on the current location of the user. We have designed and implemented Rover, a system that enables location-based services, as well as the traditional time-aware, user-aware and device-aware services. To achieve system scalability to very large client sets, Rover servers are implemented in an "action-based" concurrent software architecture that enables fine-grained application-specific scheduling of tasks. We have demonstrated feasability through implementations for both outdoor and indoor environments on multiple platforms. (Also UMIACS-TR 2001-89)Item A SECURE SERVICE DISCOVERY PROTOCOL FOR MANET(2003-08-01) Yuan, Yuan; Agrawala, AshokService discovery technologies are exploited to enable services to advertise their existence in a dynamic way, and can be discovered, configured and used by other devices with a minimum of manual efforts. Automatic service discovery will play essential role in future network scenarios. Especially, the development Mobile Ad Hoc Networks (MANETs) to support the proliferation of mobile devices and emergence of pervasive computing gives rise to the challenges of the service discovery techniques, because MANET allows these devices to communicate dynamically without fixed infrastructure and centralized administration. In this paper, we present a dynamic service discovery infrastructure that uses XML to describe services and match using the semantic content of service descriptions for MANET. We believe that the architecture we have designed is a necessary component of any discovery of non-infrastructure services effectively and correctly. We further exploit the secure and performance issues of this infrastructure. This work funded by MIND Laboratory. UMIACS-TR-2003-67Item A Study of Permutations Permissible by LIFO Service Disciplines(1998-11-12) Hawkin, Simon; Agrawala, AshokWe study permutations of the job order performed by various LIFO service disciplines. The sets of such permutations are shown to be equivalent to sets of string permutations with simple characteristics. In particular, it is easy to test whether a given permutation belongs to these sets. Several algorithms that efficiently perform such tests are presented. (Also cross-referenced as UMIACS-TR-98-65)