In recent years, online marketplaces have seen a large increase in business. Managing and making sellers' reputations available to buyers is vital for the success of these markets since buyers may be dealing with unknown online sellers. Typically, prospective buyers assess sellers' performance by looking at past buyers' reviews, prior to making a purchase. In current online marketplaces, buyers' reviews are associated with their identities, raising privacy issues. Several decentralized solutions have been proposed using blockchain technologies to solve this problem. However, some of these systems are not entirely decentralized or have some weaknesses such as requiring a trusted third party. In this paper, we propose a system for decentralized reviewing that trades off cost for unlinkability. Using blockchain-based smart contracts, we propose a fully decentralized marketplace to provide reviewers with a secure and trusted platform. Here, buyers can use one-time identities to provide feedback on their transactions. The system also ensures that a review can only be submitted after a transaction is completed, and that at most one review may be submitted per transaction. The system enforces these properties through blockchain technologies and smart contracts. In addition, we propose an innovative approach to encourage buyers to submit reviews. The system has been prototyped using Remix IDE.

Very recently, in an attempt to reduce the uncertainty associated with notoriously unreliable buyer feedback, researchers proposed a blockchain-based trust and reputation management system, where a Smart Contract manages all aspects of a transaction: setting up a contract, interacting with the two parties, and finally evaluating and providing feedback on the buyer/seller performance at the end of each transaction. They have also proposed a data structure that manages seller reputation scores inside the blockchain. In this paper, we provide two novel reputation management schemes that significantly improve on these methods. Our first such scheme is adaptive; the second one is randomized, wherein decisions about managing the underlying data structure are made based on coin flips. We provide analytical performance predictions and verify, empirically, by extensive simulation, the accuracy of our predictions. Our schemes are shown to result in more efficient query execution with enhanced block structure schemes.

Estimating highway traffic density in real-time is an important goal of Intelligent Transportation Systems. The main contribution of this work is to propose a simple and entirely V2V-based methodology to estimate, in real-time, traffic density based on data collected by moving observers in co-directional and on- coming traffic. To estimate traffic density in a privacy-preserving manner, our methodology uses tallies consisting of the number of times a vehicle is passed by other vehicles, minus the number of times it passes other vehicles. As it turns out, keeping tallies is a non-trivial task since vehicles are allowed to vary their speed in arbitrary ways and, as a result, the same two vehicles may pass each other any number of times. We provide a detailed proof of correctness of our methodology; to assess its accuracy, we have performed extensive simulations and sensitivity analyses using SUMO-generated synthetic traffic traces over a wide range of penetration rates and traffic flows.

Roughly a decade ago, inspired by the phenomenal success of cloud computing, a group of researchers have defined Vehicular Clouds as a group of vehicles whose sensing, communication, and computing resources can be coordinated and allocated to authorized users. While both conventional and Vehicular Clouds are instances of utility computing, a number of important characteristics set vehicular clouds apart from their conventional counterparts. These characteristics include the mobility of vehicles and the volatility of resources that fluctuate with the arrival and departure of vehicles. As in the conventional version of cloud computing, approximating job completion time is one of the key performance metrics of interest. Unfortunately, estimating job completion time with any degree of accuracy and confidence requires complete knowledge of the distributions of several relevant random variables. Typically, however, these probability distributions are not known. Luckily, in many cases of practical relevance, accumulated empirical evidence allows to estimate the first few moments of these random variables. The main contribution of this paper is to offer an accurate approximation of the expected job completion time in Dynamic Vehicular Clouds built on top of vehicles on a highway. For this purpose, we rely on empirical estimates of the first moment of the user job execution time in the absence of any overhead attributable to the Dynamic Vehicular Cloud itself. Our extensive simulations have confirmed that our approximations of the expected job execution time are very accurate.

The moving observer method, proposed almost 70 years ago, was found to yield traffic parameter estimates that are, in terms of accuracy, very similar to the estimates obtained by using the classical stationary observer method. Over the years, the moving observer method was validated either experimentally or else statistically by showing that the traffic estimates it produces are statistically indistinguishable from those produced by the stationary observer method. However, to the best of our knowledge, the moving observer method was not justified theoretically. The main contribution of this work is to offer the first theoretical justification of the moving observer method.

The term traffic state estimation refers to measuring or inferring values of the key traffic state variables, such as density, flow, speed, and delay, by using a combination of observed and derived traffic-related data. Due to recent advances in vehicular networking and sensor technology and by exploiting existing and emerging computer and communications paradigms, the task of estimating traffic state parameters in real-time has become technically feasible but remains a very challenging task.

Existing surveys look at parking solutions from the perspective of sensors, communication protocols, and the hardware-software interface. While this is a worthwhile approach, it suffers from three obvious shortcomings, namely that present-day sensors are likely to become obsolete in a few years, communication protocols get discontinued, and present-day software will almost certainly not run on tomorrow’s platforms. Consequently, these approaches are not promising for the Smart Cities of the near future. Unlike previous surveys, we look at parking in Smart Cities through the lens of market-based allocation of goods and services. In competitive markets prices act as signals used to allocate goods to those who value them most. In the case of parking spots, some drivers are willing to pay higher prices for the use of those parking spots that offer them the highest utility. What makes our survey unique is that we are looking at the recent literature with an eye for market-oriented solutions including pricing as an instrument for shaping traffic and for incentivizing socially-desirable driver behavior. We believe that one of the important contributions of any survey paper, over and above being a compendium of known art, is to suggest new lines of research. With this in mind, we have peppered the manuscript with slightly unorthodox perspectives. These perspectives are intended to be thought-provoking and to open new avenues for possible investigations.

Rrecently, communication technologies have been advanced rapidly to guarantee large bandwidth with low latency and reduced overhead. In addition, many new technologies are in pursuit to ensure guaranteed communication and services such as 5th and 6th generation (5G/6G) services and technologies, future Internet architectures, edge computing techniques, edge cloud-based architectures, services virtualization, and so forth. The prime objective of these new technologies is to make user-produced information easily accessible to the users on the go. Hence, these technologies play a vital role in forms of wireless networks. However, in this Special Issue, we solely focus on the new solutions, services, communication techniques, and architectures to provide efficient information communication to the vehicular networks.

The past eight years have seen the emergence ofvehicular cloudsas a topic of research in its own right. Vehicular clouds were inspired by the insight that present-day vehicles feature an impressive array of on-board compute, storage and sensing capabilities. These on-board capabilities are a vast untapped resource that, at the moment, is wasted. One of the defining ways in which vehicular clouds differ from conventional clouds is resource volatility. As vehicles enter and leave the cloud, new compute resources become available while others depart, creating a volatile environment where the tasks of enhancing reliability and availability become very challenging. It is intuitively clear that the longer and more predictable the vehicle residency times in the cloud are, the easier it is to ensure reliability and system availability. In this work we look at vehicular clouds withshort and unpredictablevehicular residency times. We propose to enhance the reliability and availability of these types of vehicular clouds through a family of redundancy-based job assignment strategies that attempt to mitigate the effect of resource volatility. We offer a theoretical prediction of the Mean Time To Failure (MTTF) of these strategies. We also show how to fine-tune the granularity of the redundancy in order to meet QoS requirements specified in terms of a minimum MTTF for a given user job. Extensive simulations, using vehicle residency data derived from shopping mall statistics, have confirmed the accuracy of our analytical predictions.

Inspired by the success of conventional cloud services and by the reality of present-day vehicles endowed with powerful on-board computers that can act as servers in a datacenter, researchers have recently introduced the concept of a vehicular cloud. Our main contribution is to offer a tight theoretical analysis of the expected job completion time in vehicular clouds characterized by short vehicular residency times, under a redundancy-based job assignment strategy. We also discuss various approximations of the expected completion time. A comprehensive set of simulations have confirmed the accuracy of our theoretical predictions.

Cloud Computing, a catchy metaphor for utility computing, implemented through the provisioning of various types of hosted services over the Internet, has seen phenomenal growth and quasi-universal adoption in the past two decades. The underlying business model of cloud computing is the familiar “pay-as-you-go” model of metered services, where a user pays for whatever he/she uses and no more, and where additional demand for service can be met in real time. This powerful idea was suggested, at least in part, by the pervasive low-cost high-speed Internet, a good handle on virtualization, and advances in parallel and distributed computing. Three aspects are novel in conventional cloud computing: First, it gives users the illusion of infinite computing resources available to them on demand. Second, it eliminates the up-front financial commitment by cloud users, allowing them to increase hardware/software resources as needed. Third, it gives users the ability to pay for resources on a short-term basis and release them when they are no longer needed.

The past decade has seen the emergence of Vehicular Clouds as a topic of research in its own right. Vehicular clouds were inspired by the reality of present-day vehicles featuring an impressive array of on-board compute, storage and sensing capabilities and by the insight that these on-board capabilities are a vast untapped resource that, at the moment, is wasted. Harvesting these vehicular resources and putting them to work in a meaningful and productive way promises to have a significant and lasting societal impact. One of the defining ways in which vehicular clouds differ from conventional clouds is resource volatility. As vehicles enter and leave the cloud, new compute resources become available while others depart, creating a volatile environment where reasoning about fundamental performance metrics becomes very challenging. Given that vehicular clouds and their numerous variants have becomes a very active field of research, this seems to be a good moment to survey the state of the art of vehicular cloud research. In this survey, we adopt an inclusive rather than an exclusive definition of various flavors of vehicular clouds. Vehicular clouds, in their many incarnations, have a huge array of potential applications. In order to bring this potential to fruition, significant research challenges have to be overcome. With this in mind, this survey identifies promising applications and draws attention to a number of research challenges facing the vehicular clouds community at large.

Motivated by the success of cloud computing, vehicular clouds were introduced as a group of vehicles whose corporate computing, sensing, communication, and physical resources can be coordinated and dynamically allocated to authorized users. Our main contribution is to offer an easy-to-compute approximation of job completion time in a dynamic vehicular cloud model involving vehicles on a highway. We assume estimates of the first moment of the time it takes the job to execute without any overhead attributable to the working of the vehicular cloud. Our simulations have shown that our approximation is very accurate. To the best of our knowledge, this is the first paper dealing with estimating job completion time in dynamic vehicular clouds.

Motivated by the phenomenal success of conventional cloud computing, vehicular clouds (VCs) were introduced as a group of vehicles whose corporate computing, sensing, communication, and physical resources can be coordinated and dynamically allocated to authorized users. Just as in conventional clouds, job completion time ranks high among the fundamental quantitative performance figures of merit. Recently, the authors have analytically investigated the effect of a redundancy-based job assignment on job completion time in VCs. However, these analytical expressions require full knowledge of the distribution functions of various random variables contributing to job completion time. In a practical context, the data center manager does not know these distribution functions. Instead, using accumulated empirical data, they may be able to estimate the first and, perhaps, the second moments of these random variables. Yet, getting a handle on the expected job completion time is a very important problem that must be addressed. Consequently, it is of great theoretical interest and practical relevance to be able to approximate the expression of job completion time. With this in mind, the main contribution of this paper is to offer easy-to-compute approximations of job completion time when estimates of the first or the first two moments of the intervening random variables are available. A comprehensive set of simulations have shown that our approximations are very close to the analytical predictions.

In a recent paper, Ghazizadeh et al. have studied vehicular clouds running on top of the vehicles in the parking lot of a major airport. The defining difference between vehicular clouds and their conventional counterparts is the unpredictable availability of computational resources. Indeed, as vehicles enter the parking lot, fresh compute resources become available; when vehicles depart, their compute resources leave with them. In such a volatile environment, the task of promoting reliability becomes quite challenging. To solve the reliability problem, Ghazizadeh et al. suggested employing redundancy-based job assignment strategies. They derived analytical expressions for the mean time to failure of these strategies. Their expressions require full knowledge of the distribution of vehicle residency times and of the time it takes to recruit a vehicle into the vehicular cloud. In a practical context, the datacenter manager does not know these distribution functions. Instead, using accumulated empirical evidence, she may know the first and perhaps the second moment of these random variables. With this in mind, this paper derives easy-to-compute approximations of the mean time to failure of the job assignment strategies proposed by Ghazizadeh et al.. A comprehensive set of simulations have shown that our approximations are very close to the analytical predictions by Ghazizadeh et al. even if the exact distribution functions are not known.

In order to enhance dependability and availability, it is common practice in conventional clouds to assign two servers to each job. In this paper, we investigate the effect of such a redundancy-based job assignment strategy on job completion time in vehicular clouds. We offer a heuristic analysis of the expected job completion time under this strategy. A comprehensive set of simulations confirmed the accuracy of our analytical predictions.

The mobile observer method has been used by traffic engineers since the middle of the last century to estimate traffic velocity, flow and density. Although simple and intuitive, the method suffers from two major issues. First, the vehicle must traverse a given road segment both in the direction of the traffic whose parameters are of interest and also in the opposite direction, essentially driving in a loop. Second, to get accurate results, several runs must be taken and the results aggregated. Our variant utilizes the communication capabilities in present-day vehicles to mitigate both these issues, thus enabling faster and more accurate traffic maps and traffic routing applications. Extensive simulation results have confirmed that our variant of the mobile observer method is comparable in accuracy with the stationary observer method even at lower flow rates.

The Twelfth Annual International Conference on Distributed Computing in Sensor Systems (DCOSS) will be held in Washington DC, USA on May 26-28, 2016. This conference broadly focuses on the design, development, and optimization of large scale networked sensor systems. In addition to the established tracks in the previous editions of DCOSS, such as Algorithms and Performance Analysis, Applications, Systems, Real Deployments and Tools, Signal Processing and Information Theory, this twelfth edition includes a new Track of the Year, called "Cloud Computing and Applications to Sensing Systems." DCOSS 2016 includes a high-quality technical program consisting of keynotes, research papers, Poster and Demo session, and Ph.D. Forum. This year we received 65 submissions in response to the call for papers. Each paper was reviewed by at least three experts in the field. After detailed on-line discussions with the Track Chairs, 24 papers were finally accepted, leading to an acceptance ratio of 37%. Specifically, the program covers important aspects of distributed computing in sensor systems, such as mobile crowdsourcing, energy efficiency and communication, routing, tracking and localization, security, and applications and outdoor testbed, to name a few. Additionally, there is one workshop that addresses challenging research topics in sensor networking. We believe the technical program will provide an exciting forum for researchers and practitioners to exchange cutting-edge ideas in distributed sensor systems.

MOTIVATION: As the mean age of parenthood grows, the effect of parental age on genetic disease and child health becomes ever more important. A number of autosomal dominant disorders show a dramatic paternal age effect due to selfish mutations: substitutions that grant spermatogonial stem cells (SSCs) a selective advantage in the testes of the father, but have a deleterious effect in offspring. In this paper we present a computational technique to model the SSC niche in order to examine the phenomenon and draw conclusions across different genes and disorders. RESULTS: We used a Markov chain to model the probabilities of mutation and positive selection with cell divisions. The model was fitted to available data on disease incidence and also mutation assays of sperm donors. Strength of selective advantage is presented for a range of disorders including Apert's syndrome and achondroplasia. Incidence of the diseases was predicted closely for most disorders and was heavily influenced by the site-specific mutation rate and the number of mutable alleles. The model also successfully predicted a stronger selective advantage for more strongly activating gain-of-function mutations within the same gene. Both positive selection and the rate of copy-error mutations are important in adequately explaining the paternal age effect. AVAILABILITY AND IMPLEMENTATION: C ++/R source codes and documentation including compilation instructions are available under GNU license at https://github.com/anwala/NicheSimulation CONTACT: [email protected] information: Supplementary data are available at Bioinformatics online.

In this work, we envision a vehicular cloud involving cars in the parking lot of a major airport. The owners of these cars are typically on travel for several days, providing a pool of cars that can serve as the basis for a data center at the airport. We assume that the cars that participate in the vehicular cloud are plugged into a standard power outlet and are provided wireless connection to a central server at the airport. The defining difference between vehicular and conventional clouds lies in the distributed ownership and, consequently, the unpredictable availability of computational resources. As cars enter and leave the parking lot, new computational resources become available while others depart, creating a dynamic environment where the task of efficiently assigning cars to jobs becomes very challenging. Our main contribution is a family of redundancy-based job assignment strategies that mitigate the effect of resource volatility in vehicular clouds. We offer a theoretical analysis of the mean time to failure of these strategies. A comprehensive set of simulations has confirmed the accuracy of our theoretical predictions.

NOTICE is a secure privacy-aware architecture for the automatic detection of traffic events and for the dissemination of related traffic advisories. NOTICE uses belts of piezoelectric elements embedded in the roadways to detect passing vehicles and to initiate meaningful interaction with them. NOTICE learns about traffic conditions by collecting data from passing vehicles and as a rule, these data are highly correlated. Thus, to detect a traffic-related event, there is no need to aggregate data from all passing vehicles, particularly in dense traffic. The main contribution of this paper is to investigate probabilistic data collection from a passing car with some application-dependent handshake probability p. We analyze various parameters of such data collection and reveal their impact on the time it takes NOTICE to detect a traffic-related event. Indeed, observe that p and the flow intensity directly impact the expected time between consecutive cars that interact with a given belt and, consequently, the time it takes to collect sufficient data to ensure a meaningful data aggregation. In turn, this gives us a handle on the expected time it takes NOTICE to detect traffic-related events. There is an obvious tradeoff here: To save energy, a belt may decide to collect and aggregate data from fewer cars. In turn, this increases the time it takes to detect a traffic-related event. Extensive simulations using traces of real traffic and simulated data have confirmed the accuracy of our analytical predictions.

Vehicle-to-Vehicle (V2V) communication in Vehicular Ad hoc Networks (VANETs) is one of the key ingredients in the Intelligent Transportation System (ITS) where vehicles receive relevant traffic information using wireless communications from their peers. Forwarding traffic information to drivers can assist with the tasks of avoiding traffic accidents and related congestion. In this paper, we investigate the effect of association time (a.k.a. connection setup time), relative speed of vehicles, transmission range and message/data size in short range based V2V communications. The analysis is illustrated with the numerical results obtained from simulations.

NOTICE is a secure, privacy-preserving architecture for the automatic detection of traffic incidents and the dissemination of related traffic advisories. NOTICE uses belts of piezo-electric elements embedded in the highways to detect variations in the attributes of traffic flow. By using their piezo-electric elements the belts detect passing vehicles and initiate meaningful interaction with them. NOTICE learns about traffic conditions by collecting data from passing vehicles and, as a rule, this data is highly correlated. Thus, there is no need to collect data from all vehicles, especially in dense traffic, and one of the important issues we investigate in this work is probabilistic data collection where instead of collecting traffic-related data from all vehicle, the belt flips a coin and only collects data from a vehicle with some application-dependent probability p. Vehicular Networks and Traffic-related systems are just like mission-oriented sensor networks, both are time-varying systems consist of both humans and sensors that collect, communicate and coordinate to accomplish a near real-time solution or mission. The main contribution of this work is to analyze various parameters of probabilistic data collection in the NOTICE architecture and to reveal how they impact data aggregation and the time to detect traffic-related events. Extensive simulations of various traffic regimens have confirmed the accuracy of our analytical predictions.

This work proposes an algorithm for asset registry in emergency situations. Specifically, we take the view that first responders need to harvest the unknown capabilities of sensors in an area affected by an emergency. We show how a first responder can estimate the number of sensors with a desired sensing capability in an efficient fashion. At the heart of our algorithm is a simple probabilistic counting strategy. Our theoretical predictions were confirmed both by simulation and by implementation on IRIS sensor motes. Our theoretical and experimental results show that the error percentage of the capability collection is very low.

In vehicular networks, there is a strong correlation between a vehicle's identity and that of the driver. It follows that any effort to protect driver privacy must attempt to make the link between the two harder to detect. One of the most appealing solutions to hiding the identity of a vehicle is the use of pseudonyms, whereby each vehicle is issued one or several temporary identities (i.e., pseudonyms) that it uses to communicate with other vehicles and/or the roadside infrastructure. Due to the large number of vehicles on our roadways and city streets and of the sophistication of possible attacks, privacy protection must be both scalable and robust. The first main contribution of this work is to take a nontrivial step towards providing a scalable and robust solution to privacy protection in vehicular networks. To promote scalability and robustness we employ two strategies. First, we view vehicular networks as consisting of nonoverlapping subnetworks, each local to a geographic area referred to as a cell. Depending on the topology and the nature of the area, these cells may be as large as few city blocks or, indeed, may comprise the entire downtown area of a small town. Each cell has a server that maintains a list of pseudonyms valid for use in the cell. Instead of issuing pseudonyms to vehicles proactively, as virtually all existing schemes do, we issue pseudonyms only to those vehicles that request them. Our second main contribution is to model analytically the time-varying request for pseudonyms in a given cell. This is important for capacity planning purposes since it allows system managers to predict, by taking into account the time-varying attributes of the traffic, the probability that a given number of pseudonyms will be required at a certain time as well as the expected number of pseudonyms in use in a cell at a certain time. Empirical results obtained by detailed simulation confirmed the accuracy of our analytical predictions.

Data integrity is a major concern in outsourced IT services like cloud computing. Cloud computing has become popular because of cost reductions, time saving and mobility in service. However data integrity is still an unresolved issue in cloud services. We present an efficient mechanism for evaluating data integrity in cloud database-as-a-service. Our approach is based on inserting fake tuples into the database. In our model the owner of the data is the only trusted party and the server as a service provider or any other users are not trusted. We refer to distrusted party as a potentially malicious attacker. In our approach we define generating functions to create fake tuples with uniform distribution. Malicious attackers are not able to distinguish between fake tuples and real tuples. Our approach does not use encryption which makes it more efficient. We explore the strengths and limitations of these generating functions by describing our approach.

In a series of recent papers, Prof. Olariu and his co-workers have promoted the vision of vehicular clouds (VCs), a nontrivial extension, along several dimensions, of conventional cloud computing. In a VC, underutilized vehicular resources including computing power, storage, and Internet connectivity can be shared between drivers or rented out over the Internet to various customers. Clearly, if the VC concept is to see a wide adoption and to have significant societal impact, security and privacy issues need to be addressed. The main contribution of this work is to identify and analyze a number of security challenges and potential privacy threats in VCs. Although security issues have received attention in cloud computing and vehicular networks, we identify security challenges that are specific to VCs, e.g., challenges of authentication of high-mobility vehicles, scalability and single interface, tangled identities and locations, and the complexity of establishing trust relationships among multiple players caused by intermittent short-range communications. Additionally, we provide a security scheme that addresses several of the challenges discussed.

In this paper we study the use of a beaconing mechanism for vehicle-to-infrastructure communication and information exchange in intelligent transportation systems. We provide analytical expressions for the probability of successful connection between roadside infrastructure and passing vehicles showing the dependence on the beacon frequency and distribution of the vehicle speed, as well as on the amount of information to be exchanged between vehicle and roadside infrastructure and the data rate of the wireless link established between the vehicle and roadside infrastructure. The performance of the beaconing mechanism is illustrated for specific scenarios which show that it can be used successfully used in conjunction with wireless systems using the Dedicated Short Range Communications (DSRC) standard as well as other types of systems.

One of the challenges for Vehicular Ad-hoc Networks (VANETs) is the design of the Medium Access Control (MAC) protocol. When exchanging messages between vehicles, there are network issues that must be addressed, including the hidden terminal problem, high density, high node mobility, and data rate limitations. A cluster-based MAC scheme is needed in VANETs to overcome the lack of specialized hardware for infrastructure and the mobility to support network stability and channel utilization. This paper presents a MAC algorithm for vehicular ad-hoc networks using a new method for TDMA slot reservation based on clustering of vehicles. Our algorithm aims to decrease collisions and packet drops in the channel, as well as provide fairness in sharing the wireless medium and minimizing the effect of hidden terminals.

In this paper, we introduce the theoretical foundations of FRIEND: A cyber-physical system for traffic Flow-Related Information aggrEgatioN and Dissemination. By integrating resources and capabilities at the nexus between the cyber and physical worlds, FRIEND will contribute to aggregating traffic flow data collected by the huge fleet of vehicles on our roads into a comprehensive, near real-time synopsis of traffic flow conditions. We anticipate providing the drivers with a meaningful, color-coded, at-a-glance view of flow conditions ahead, alerting them to congested traffic. FRIEND can be used to provide accurate information about traffic flow and can be used to propagate this information. The workhorses of FRIEND are the ubiquitous lane delimiters (a.k.a. cat-eyes) on our roadways that, at the moment, are used simply as dumb reflectors. Our main vision is that by endowing cat's eyes with a modest power source, detection and communication capabilities they will play an important role in collecting, aggregating and disseminating traffic flow conditions to the driving public. We envision the cat-eye system to be supplemented by road-side units (RSU) deployed at regular intervals (e.g. every km or so). The RSUs placed on opposite sides of the roadway constitute a logical unit and are connected. The physical components of FRIEND collect traffic flow-related data from passing vehicles. The collected data is used by an inference engine in the RSU's cyber component to build beliefs about the state of the traffic, to detect traffic trends, and to disseminate relevant traffic flow-related information along the roadway.

In this work, we assume a geographic area populated by tiny sensors, each perhaps no larger than a dime. In order to save their energy, the sensors spend most of their lifetime in sleep mode and wake up for short periods of time to participate in various tasks supportive of the overall mission of the network. We assume that the tasks to be performed stipulate QoS parameters expressed in terms of the minimum number of sensors that need to monitor their sensing area. Since only awake sensors participate in tasks, the Effective Sensor Density (ESD), defined as the density of awake sensors, is an important network parameter that obviously depends on the sleep schedules adopted in the network. The first main contribution of this work is to provide a mathematical analysis of ESD from the perspective of the monitored events. We also provide design guidelines to determine deployment-time sensor density and an associated sleep schedule that probabilistically keeps the ESD at a level needed by QoS requirements. We also propose a fully distributed sleep schedule which adaptively adjusts the duty cycles of sensors within the same sensing area based on the relative difference in their remaining energy budget. The main advantage of the proposed adaptive scheme is to balance energy consumption among sensors, thus promoting the functional longevity of the sensor network without adversely affecting the ESD.

Sensor networks have their own distinguishing characteristics that set them apart from other types of networks. Several techniques have been proposed in the literature to address some of the fundamental problems faced by a sensor network design. Most of the proposed techniques attempt to solve one problem in isolation from the others; hence, protocol designers have to face the same common challenges again and again. This, in turn, has a direct impact on the complexity of the protocols and on energy consumption. Instead of using this approach, we propose BEES, a lightweight bioinspired backbone construction protocol, that can help mitigate many of the typical challenges in sensor networks by allowing the development of simpler network protocols. We show how BEES can help mitigate many of the typical challenges inherent to sensor networks including sensor localization, clustering, and data aggregation among others.

Recently, Olariu et al. [3], [7], [18], [19], [20] proposed to refer to a dynamic group of vehicles whose excess computing, sensing, communication, and storage resources can be coordinated and dynamically allocated to authorized users, as a vehicular cloud. One of the characteristics that distinguishes vehicular clouds from conventional clouds is the dynamically changing amount of available resources that, in some cases, may fluctuate rather abruptly. In this work, we envision a vehicular cloud involving cars in the long-term parking lot of a typical international airport. The patrons of such a parking lot are typically on travel for several days, providing a pool of cars that can serve as the basis for a datacenter at the airport. We anticipate a park and plug scenario where the cars that participate in the vehicular cloud are plugged into a standard power outlet and are provided Ethernet connection to a central server at the airport. In order to be able to schedule resources and to assign computational tasks to the various cars in the vehicular cloud, a fundamental prerequisite is to have an accurate picture of the number of vehicles that are expected to be present in the parking lot as a function of time. What makes the problem difficult is the time-varying nature of the arrival and departure rates. In this work, we concern ourselves with predicting the parking occupancy given time-varying arrival and departure rates. Our main contribution is to provide closed forms for the probability distribution of the parking lot occupancy as a function of time, for the expected number of cars in the parking lot and its variance, and for the limiting behavior of these parameters as time increases. In addition to analytical results, we have obtained a series of empirical results that confirm the accuracy of our analytical predictions.

Ambient data generated by sensor nodes must be forwarded to sink node and made available to central system for further processing. Additionally, in a densely deployed sensor network, data are correlated and redundancy may occur. To minimize energy consumption, data may be aggregated during forwarding process. Although clustering helps in eliminating redundancy and prolonging network lifetime, but the formation and maintaining of cluster heads is energy consuming. Utilizing fine-grain location-based cluster (enhanced Virtual Infrastructure - eVI) [2] we demonstrate that clustering without cluster heads can provide energy efficient in-network aggregation and offers inherent default aggregators for fault-tolerance. Centralized routing for eVI cannot be done implicitly as in Virtual Infrastructure (VI) [1]. Each fine grain clusters must be scheduled properly during data forwarding in reducing energy usage due to data collision. Exploitation of mobile sink requires non-centralized routing in minimizing delay and data loss. Hybrid routing is proposed in which dynamic destination cluster is determined as a data collection point. Simulation results demonstrate that the in-network processing of clustering without cluster head performs better than cluster with a head.

Neighborhood discovery (ND) in a wireless sensor network is a process of identifying the sensors that a given node can communicate directly. In this paper, our main contribution is to model the ND protocol in a wireless sensor network. In ND task, each node is assigned its own N timeslots, with equal slot intervals. In each slot, each node chooses either to transmit or listen, with probabilities p and 1 -- p. Our objectives are to analyze the optimal value of p, and model the formulation of N by mapping the problem into the coupon's collector problem. The simulation results show close match to the theoretical results.

In numerous applications of wireless sensor networks (WSN), the reliability of the data collected by sensors is cast as specific QoS requirements expressed in terms of the minimum number of sensors needed to perform various tasks. Designing a long-lived sensor network with reliable performance has always been challenging due to the modest nonrenewable energy budget of individual sensors. In such a context, energy-unaware task management protocols may result in uneven expenditure of sensor energy by assigning uneven workloads to sensors. This, in turn, often translates into reduced sensor density around those heavily loaded sensors and may, eventually, lead to the creation of energy holes that partition the network into disconnected islands. To avoid these problems and to promote network longevity, we propose two energy-aware task management protocols: our first protocol is centralized, while the second one is fully distributed. The proposed protocols assign tasks to sensors based on their remaining energy so that energy expenditure among neighboring sensors is almost even. We compare the reliable lifetime of the network achieved by assigning tasks to sensors using the proposed protocols against optimal task assignment and also against energy-unaware protocols. Extensive simulation results have revealed that the performance of the proposed protocols is very close to that of the optimal task assignment. Furthermore, our simulation has shown that the proposed protocols can increase the functional longevity of the network by about 16 percent.

The past decade has witnessed a phenomenal market penetration of wireless communications and a steady increase in the number of mobile users. Unlike wired networks, where communication links are inherently stable, in wireless networks, the lifetime of a link is a random variable whose probability distribution depends on mobility, transmission range, and various impairments of radio communications. Because of the very dynamic nature of Vehicular Ad hoc NETworks (VANETs) and the short transmission range mandated by the Federal Communications Commission (FCC), individual communication links come into existence and vanish unpredictably, making the task of establishing and maintaining routing paths between fast-moving vehicles very challenging. The main contribution of this work is to investigate the probability distribution of the lifetime of individual links in a VANET under the combined assumptions of a realistic radio transmission model and a realistic probability distribution model of intervehicle headway distance. Our analytical results were validated and confirmed by extensive simulation.

In this work, we consider a large-scale geographic area populated by tiny sensors and some more powerful devices called actors, authorized to organize the sensors in their vicinity into short-lived, actor-centric sensor networks. The tiny sensors run on miniature nonrechargeable batteries, are anonymous, and are unaware of their location. The sensors differ in their ability to dynamically alter their sleep times. Indeed, the periodic sensors have sleep periods of predefined lengths, established at fabrication time; by contrast, the free sensors can dynamically alter their sleep periods, under program control. The main contribution of this work is to propose an energy-efficient location training protocol for heterogeneous actor-centric sensor networks where the sensors acquire coarse-grain location awareness with respect to the actor in their vicinity. Our theoretical analysis, confirmed by experimental evaluation, shows that the proposed protocol outperforms the best previously known location training protocols in terms of the number of sleep/awake transitions, overall sensor awake time, and energy consumption.

In this paper, we present a new scheme for dynamic adaptation of transmission power and contention window (CW) size to enhance performance of information dissemination in Vehicular Ad-hoc Networks (VANETs). The proposed scheme incorporates the Enhanced Distributed Channel Access (EDCA) mechanism of 802.11e and uses a joint approach to adapt transmission power at the physical (PHY) layer and quality-of-service (QoS) parameters at the medium access control (MAC) layer. In our scheme, transmission power is adapted based on the estimated local vehicle density to change the transmission range dynamically, while the CW size is adapted according to the instantaneous collision rate to enable service differentiation. In the interest of promoting timely propagation of information, VANET advisories are prioritized according to their urgency and the EDCA mechanism is employed for their dissemination. The performance of the proposed joint adaptation scheme was evaluated using the ns-2 simulator with added EDCA support. Extensive simulations have demonstrated that our scheme features significantly better throughput and lower average end-to-end delay compared with a similar scheme with static parameters.

Current driver assistance systems merely use a minimum amount of information. By using additional information of the environment hazardous situations can be detected earlier, more reliably and with a higher accuracy. This situational information has a significant impact not only on hazard detection, but also on other modules such as the human-machine-interface or knowledge distribution between vehicles over vehicular ad-hoc networks. In this paper, we design TOCADAS (TOlerant Context-Aware Driver Assistance System) in order to help prevent accidents and reduce the number of traffic fatalities. The proposed TOCADAS is aware of uncertain situational information, recognizes current context situation and provides drivers with the most effective driver assistance services for the current context situation using pattern similarity degrees.

Location is important information in Vehicular Adhoc Network because most, if not all, applications will depend on accurate location information. In reality, the dynamics of vehicles makes the location information consistently changing. The existence of malicious attackers even makes the task of estimating accurate location more difficult. In this paper, we describe an efficient statistic method for estimating accurate location of vehicles in a noisy environment including malicious attackers and measurement errors. Given such noisy input, the algorithm estimates the high resolution location of a vehicle by filtering the malicious location input and by refining low resolution location input. We show results of simulations and evaluate the quality of location estimation as well.

Location, fundamental information, plays a critical role in many applications and network routings in Vehicular Adhoc NETworks (VANETs). Therefore, it is of importance to validate the location information. We propose a cross-layer design to achieve location validation. We assume vehicles are installed with radar, GPS and transceiver. On physical layer, radar detection can validate GPS coordinates. On network layer, an agreement of a location can be achieved. On application layer, location information as a set of measurements can be filtered and refined by using a proposed data fusion method. We also present results of simulations and evaluate the location validation methods.

The past decade has witnessed the confluence of Intelligent Transportation Systems (ITS) and Vehicular Ad hoc Networks (VANET) that promises to revolutionize incident detection and the timely dissemination of traffic-related information to the various interested parties. One of the key components is expected to be a Cooperative Collision Warning System (CCWS). Our main contribution is to derive analytical expressions for key CCWS metrics that rely on mobility information exchanged by various players. The feasibility of CCWS has been demonstrated in previous work; this paper analyzes the mobility parameters and derives the conditional probability of a collision. We begin by proposing a set of fundamental parameters for CCWS: conditional probability of collision, headway distance, driver reaction time, relative velocity and acceleration. Preliminary simulation results have demonstrated the effectiveness of our analytical derivations.

Positioning or tracking in VANET is currently based on GPS. However, GPS is known to be prone to failure in case of emergencies. In addition, the current market penetration rate of GPS devices is low. Vehicles with built-in cellular communication capability are expected to be a part of the near future. Therefore, it is reasonable to assume that any vehicle possesses the functionality of a mobile unit (MU). The principal contribution of this paper is the proposed novel concept that employs the existing cellular RSS measurements as the basis for position estimation in VANET in situations where GPS services are unavailable. The proposed localization technique involves sampling the signal beacons received from three base stations surrounding the mobile unit for a very small time duration. Each of the RSS samples are then mapped to a sample of distance estimates based on shadowing radio propagation model. The medians of the generated distance sets are then used by a state of the art technique to produce a final location estimate. One of the important contributions of this work is justifying the selection of median over mean. An extremely small sampling duration negates the impact of mobile unit movement while the median selection neutralizes the deviation caused by time varying radio channel characteristics. All computation is restricted to mobile unit, thereby ensuring privacy. Simulation results demonstrate the efficiency of the proposed algorithm.

The past decade has witnessed a growing interest in vehicular networking and its myriad potential applications. The initial view of practitioners and researchers was that radio-equipped vehicles could keep the drivers informed about potential safety risks and increase their awareness of road conditions. The view then expanded to include access to the Internet and associated services. More recently, the availability of bandwidth has seen vehicular peer-to-peer networking and multimedia content delivery.

The capability of sensor nodes to collect and aggregate ambient data enables a mobile user to receive assistance from the network in charting a safe path through a potentially dangerous area. However, the information would be meaningless without localization. Applying an existing coarse-grain location-aware cluster (virtual infrastructure i.e. VI) for object detection provides only approximate location of dangerous objects as the objects are further away from the center. This distance-dependent location-based cluster creates various sizes of localized clusters, which cause inconsistency in size and thus may lead to inefficient path planning.

We model an important aspect of the problem of sensor information integration that arises in wireless communications, where N sensors try to communicate with a receiver using a single un-shareable radio channel. If several sensors transmit at the same time their transmissions collide at the receiver resulting in garbled messages and the need for re-transmission. This is highly undesirable since the sensor nodes are energy-constrained and the radio interface is known to be the most significant source of energy expenditure. Consequently, it is of paramount importance to design arbitration protocols that are highly efficient in stamping out collisions and are, at the same time, as lightweight as possible. The main contribution of this paper is to present a distributed probabilistic mechanism that aims to arbitrate between several competing requests by sensor nodes for the radio channel. Our mechanism is simple, energy-efficient and does not rely on the existence of unique sensor identifiers (IDs).

The diffusion of time-critical information, like traffic alert messages, is critical and challenging in Vehicle Ad hoc Networks (VANETs). It is critical because lives of people on the road are at stake and is challenging due to a combination of highly dynamic mobility patterns, which result in rapidly changing network topologies, combined with the fast movement of vehicles and highly dynamic traffic patterns. Flooding-based alert diffusion among vehicles has a strong similarity with diffusion of a new product among people. Applying a diffusion model to alert messages enables the dissemination modeling of the alert messages among vehicles, and thus opening an opportunity to adopt appropriate strategies to recovery from the traffic accidents. In this paper, a diffusion model is developed for a flooding-based alert message diffusion algorithm and the diffusion speed is explored. The fact that information value (or importance) is decreasing with time and distance, is also considered in the proposed model. We analytically investigate the impact parameters on time-critical information diffusion by mapping to the classic BASS diffusion model [1, 2]. The analytical model allows the evaluation at runtime and enables vehicles to dynamically adapt their diffusion strategies depending on the local node density.

In a typical sensor network environment, sensor energy is considered a precious resource that must be used wisely and only if necessary. Energy-unaware task assignment protocols can deplete the energy of some sensors much more than they do for others. This results in reducing network density around those heavily loaded sensors and eventually creates energy holes that isolate the network into separated islands. These problems have negative impacts on network durability and reliability. To avoid these problems, we propose and evaluate a lightweight management protocol that assigns tasks to sensors based on their energy so that energy consumption is almost even among network sensors. In addition, we propose another mechanism to aggregate data collected by sensors before sending them back to the base station. Our aggregation mechanism supports different aggregation functions including exact evaluation of the minimum, the maximum, and the logical OR and an approximation of the average of the collected sensory data. Using simulation, we compare the lifetime achieved by assigning tasks to network sensors using the proposed protocol against another energy- neutral protocol. Simulation results verified that the proposed approach increases network durability by balancing task load among sensors. Also simulation shows that, under reasonable parameters, the error in the approximated value of the average is less than 3%.

Although, current technology enables an inexpensive massive production of sensors, it raises numerous challenges on the protocols needed to interact with these sensors efficiently. Several techniques have been proposed to address each of these challenges individually (i.e. localization, clustering, routing, aggregation ... etc). Instead of solving each of these problems individually facing the same common challenges with each problem, we propose to construct what we call a network skeleton that is constructed immediately after network deployment and provides a topology that makes the network more tractable. The skeleton provides sensors with coarse localization information that enables them to associate their sensory data with the geographic location in which the data was measured. Moreover, it promotes a geographic routing scheme that simplifies data communication across the network through skeleton sensors. By hypothetically tiling the deployment area using identical hexagons, the construction algorithm clusters sensors based on their locations into hexagons. Skeleton sensors are chosen to be the closest sensors to the centers of these hexagons. Simulation results show that the accuracy of the proposed protocol to establish the skeleton is sufficient to make the approach applicable for most WSN applications.

In vehicular adhoc network (VANET), applications are involved with sensitive and secret information. We address a location-based encryption method that not only ensures messages confidentiality but also authenticates identity and location of communication peers. The authentication of location means that a message can only decrypted by the receiver which is ldquophysicallyrdquo present inside a decryption region that is specified by location, time and speed. A practical mapping function which converts location, time and speed into a unique lock key is proposed. The determination of the decryption region is addressed in two steps: predicting and updating. The proposed method evaluated by simulations is efficient and secure.

Road and traffic safety can be improved if the drivers have the ability to see further down the road and can be informed of relevant traffic events, including collisions and slow-downs. The recently proposed VANETs (Vehicular Ad hoc Networks) are expected to enable both vehicle-to-vehicle (V2V) and vehicle-to-roadside (V2R) communications. Virtually all the papers published in the literature assume that V2V communications will rely on a strong roadside infrastructure. Unfortunately, the roadside infrastructure, is very likely to be the target of theft, vandalism and other similar activities that will jeopardize their intended functionality. Worse yet, one can easily contemplate a scenario where the roadside infrastructure may be hacked and injected with malicious code, rendering it not only useless but, downright dangerous.

The key attribute that distinguishes Vehicular Ad hoc Networks (VANET) from Mobile Ad hoc Networks (MANET) is scale. To wit, while MANET involve up to one hundred nodes and are short lived, being deployed in support of special-purpose operations, VANET networks involve millions of vehicles on thousands of kilometers of highways and city streets. Also, being mission-driven, MANET mobility is inherently limited by the application at hand. Indeed, in a search-and-rescue mission a search party is deployed to look, say, for children lost in the woods. It stands to reason that in such a context the mobility of individual nodes is not arbitrary, but rather restricted by the search strategy implemented. In most MANET applications, such as the one just mentioned, mobility occurs at low speed. By contrast, VANET networks involve vehicles that move at high speed, often well beyond what is reasonable or legally stipulated.

Road and traffic safety can be improved if the drivers have the ability to see further down the road and can be informed of relevant traffic events, including collisions and slow-downs. The recently proposed VANETs (Vehicular Ad hoc Networks) are expected to enable both vehicle-to-vehicle (V2V) and vehicle-to-roadside (V2R) communications. Virtually all the papers published in the literature assume that V2V communications will rely on a strong roadside infrastructure. Unfortunately, the roadside infrastructure, is very likely to be the target of theft, vandalism and other similar activities that will jeopardize their intended functionality. Worse yet, one can easily contemplate a scenario where the roadside infrastructure may be hacked and injected with malicious code, rendering it not only useless but, downright dangerous.

Although vehicular ad hoc networks (VANETs) started mainly for safety applications, surprisingly very few work have been done in VANETs for automatic incident detection (AID) while most of the research went for developing routing protocols and privacy techniques. On the other hand, it is fundamentally difficult for most of the existing AID techniques to detect incidents in non dense traffic especially for those incidents that do not block all lanes. In this paper, we introduce a novel probabilistic automatic incident detection technique for non dense traffic flow based on Bayesian theory.

One of the fundamental requirements of a traffic management system is the ability to determine when an incident has occurred so that proper responses can be initiated. Most of the existing automatic incident detection techniques suffer from many limitations including their inability to detect incidents under non dense traffic conditions and generation of many false positive alarms. In this paper, we introduce a novel Bayesian-based approach to enhance the performance of existing techniques specially under non-dense traffic flow through vehicle to readside communications. The proposed technique also offers zero false positive alarms under most situations and can be integrated with any of the current techniques.

Recently, Vehicular Ad-hoc Networks (VANETs) employing a combination of Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I) wireless communication have been proposed to alert drivers about different traffic events. NOTICE, a secure and privacy-aware architecture for the Notification Of Traffic InCidEnts that provides drivers with up-to-the-minute notification about highway conditions, is introduced in. NOTICE moves the responsibility for making decisions about traffic-related incidents to the infrastructure rather than leaving those decisions with the vehicles, which may have incomplete or incorrect knowledge. This paper introduces a secure data dissemination technique that could be used in NOTICE or can be easily adapted to enhance other existing data routing or dissemination techniques.

In this paper, we propose an algorithm for joint adaptation of transmission power and contention window to improve the performance of vehicular network in a cross layer approach. The high mobility of vehicles in vehicular communication results in the change in topology of the Vehicular Ad-hoc Network (VANET) dynamically, and the communication link between two vehicles might remain active only for short duration of time. In order for VANET to make a connection for long time and to mitigate adverse effects due to high and fixed transmission power, the proposed algorithm adapts transmission power dynamically based on estimated local traffic density. In addition to that, the prioritization of messages according to their urgency is performed for timely propagation of high priority messages to the destination region. In this paper, we incorporate the contention based MAC protocol 802.11e enhanced distributed channel access (EDCA) mechanism to implement a priority-based vehicle-to-vehicle (V2V) communication. Simulation results show that the proposed algorithm is successful in getting better throughput with lower average end-to-end delay than the algorithm with static/default parameters.

Abstract Given two nonnegative integers h and k, an L(h, k)‐labeling of a graph G = (V, E) is a map from V to a set of integer labels such that adjacent vertices receive labels at least h apart, while vertices at distance at most 2 receive labels at least k apart. The goal of the L(h, k)‐labeling problem is to produce a legal labeling that minimizes the largest label used. Since the decision version of the L(h, k)‐labeling problem is NP‐complete, it is important to investigate classes of graphs for which the problem can be solved efficiently. Along this line of thought, in this article we deal with co‐comparability graphs, its subclass of interval graphs, and circular‐arc graphs. To the best of our knowledge, ours is the first reported result concerning the L(h, k)‐labeling of co‐comparability and circular‐arc graphs. In particular, we provide the first algorithm to L(h, k)‐label co‐comparability, interval, and circular‐arc graphs with a bounded number of colors. Finally, in the special case where k = 1 and G is an interval graph, our algorithm improves on the best previously‐known ones using a number of colors that is at most twice the optimum. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

A graph is an interval graph if it is the intersection graph of intervals on a line. Interval graphs are known to be the intersection of chordal graphs and asteroidal triple–free graphs, two families where the well-known lexicographic breadth first search (LBFS) plays an important algorithmic and structural role. In this paper we show that interval graphs have a very rich LBFS structure and that by exploiting this structure one can design a linear time, easily implementable, interval graph recognition algorithm.

Scalable energy-efficient training protocols are proposed for wireless networks consisting of sensors and a single actor, where the sensors are initially anonymous and unaware of their location. The protocols are based on an intuitive coordinate system imposed onto the deployment area, which partitions the sensors into clusters. The protocols are asynchronous, in the sense that the sensors wake up for the first time at random, then alternate between sleep and awake periods both of fixed length, and no explicit synchronization is performed between them and the actor. Theoretical properties are stated under which the training of all the sensors is possible. Moreover, both worst-case and average case analyses of the performance, as well as an experimental evaluation, are presented showing that the protocols are lightweight and flexible.

We propose and evaluate a new localization protocol for sensor networks. Contrary to most current localization schemes, this protocol relies on the existence of only a single beacon node. The main idea is to hypothetically tile the deployment area with identical equilateral geometric shapes (e.g. hexagons, triangles... etc). Tiling should be such that the positions of the centers of these shapes can be easily computed relative to the position of the beacon node. After that, the set of nodes that are as close as possible to the centers of these shapes is determined. We refer to these nodes as central nodes. Basically, the positions of these central nodes can be approximated by the positions of the centers of the geometric shapes which can be calculated mathematically. These central nodes can be treated as beacons and the positions of all non-central nodes can be estimated using any range-free protocol (e.g. the centroid). Simulation results show that the accuracy of the proposed protocol is comparable to the accuracy of current localization protocols especially near the beacon node. In addition to this, the achieved localization accuracy increases significantly as the network density increases.

We investigate how to maximize network lifetime by devising a task assignment protocol that balances task load on sensors based on their remaining energy. First, we show that energy-unaware protocols can excessively assign tasks to a set of sensors more than others. Consequently, the energy of those heavily loaded sensors will be depleted much faster than lightly loaded ones. This results in reducing network density around heavily loaded sensors and eventually creates energy holes that isolate the network into separated islands. This kind of behavior has its negative impacts on network durability and reliability. To avoid these problems, we propose a management protocol that assigns tasks to sensors based on their remaining energy so that energy consumption is almost even among network sensors.

Vehicular ad hoc networks (VANET) have recently received increasing attention in the media. And with good reason: VANET promises to integrate driving into a ubiquitous and pervasive network that will redefine the way we live and work.

The NOTICE architecture is a new concept in vehicular ad-hoc networking (VANET) that aims at providing automated notification of traffic incidents on highways in order to reduce congestion and improve overall traffic safety. The basic component of NOTICE is a system of sensor belts that collect information from passing cars through a wireless radio link. An indicator of performance for the NOTICE system is the incident detection time which depends on various parameters among which we note the vehicle speed, the time required by communicating radios for connection setup and information exchange, the amount of information to be transmitted, or the radio technology employed. In this paper we present a numerical performance study of the NOTICE system with realistic values of these parameters in an attempt to provide some basic specifications for the physical layer of the system.

We introduce NOTICE, a secure, privacy-aware architecture for the notification of traffic incidents. Using sensor belts embedded in the roadway, traffic-related messages and advisories are carried between belts by passing cars. NOTICE moves the responsibility for making decisions about traffic- related information dissemination to the infrastructure rather than leaving those decisions with the vehicles, which may have incomplete or incorrect knowledge. Extensive simulation showed that NOTICE can provide "up-to-the-minute" notification of road incidents.

Abstract Networked multimedia applications involve a set of cooperating streams that together form amultimedia session. Existing QoS provisioning schemes for multimedia applications in cellular networks either allow composite streams to compete with one another for resources or else provide QoS to a session as an atomic entity, leaving to the application the task of managing QoS for the individual streams. The main contribution of this work is to propose a novel local QoS provisioning scheme for cellular networks that is aware of the relationships between the streams that compose a session. Our new Multimedia Session‐Aware QoS (MUSAQ) provisioning scheme manages the QoS of the individual streams in a session, and, with the knowledge of their relationships, it prevents destructive competition between the streams. Further, by allowing application‐specified prioritization between streams in a session, MUSAQ features a significant improvement in performance over session‐unaware schemes. Copyright © 2007 John Wiley & Sons, Ltd.

This paper proposes an efficient chaos-reducing information dissemination approach for spatiotemporal traffic information related to first responders and planned evacuation scenarios using vehicular ad hoc networks (VANETs). VANETs have recently been proposed as one of the promising ad-hoc networking techniques that can be used to provide a safe and enjoyable driving experience. In our approach, we provide an emergency vehicle path clearing technique, and real-time resource (e.g. shelter) availability information. Therefore, traffic confusion and chaos is lowered on evacuation and emergency vehicle routes. Simulation results show that our approach works efficiently without fully relying on any message relaying infrastructure.

Disasters, natural and man-made alike, pose a serious threat to the nation by taking a heavy toll in human lives, destroying the public infrastructure and production capacity, interrupting supply lines, and stalling economic activity. One of the time-honored strategies for dealing with predictable natural disasters is a planned evacuation of the population from the afflicted area. Thus, evacuation strategies and supporting infrastructure are of the highest importance for mitigating the effects of such events. The main contribution of this work is to propose an intelligent highway infrastructure in support of planned evacuations. Specifically, we show that the recently-proposed architecture for the notification of traffic incidents and congestion (NOTICE) can be enhanced to support the needs of large-scale evacuations.

This paper proposes a novel chaos reducing information dissemination approach for spatio-temporal traffic information related to first responders and evacuation scenarios using Vehicular Ad Hoc Networks (VANETs). In our approach, we provide an emergency vehicle path clearing technique. Therefore, traffic confusion and chaos is lowered on evacuation and emergency vehicle routes. Simulation results show that our approach works efficiently without fully relying on any message relaying infrastructure.

Situation management is a rapidly evolving science where managed sources are processed as realtime streams of events and fused in a way that maximizes comprehension, thus enabling better decisions for action. Sensor networks provide a new technology that promises ubiquitous input and action throughout an environment, which can substantially improve information available to the process. Here we describe a program of NASA that requires improvements in sensor networks and situation management. We present an approach for massively deployed sensor networks that does not rely on centralized control but is founded in lessons learned from the way biological ecosystems are organized. In this approach, fully distributed data aggregation and integration can be performed in a scalable fashion where individual motes operate based on local information, making local decisions that achieve globally-meaningful effects. This exemplifies the robust, fault-tolerant infrastructure required for successful situation management systems

Abstract — This paper investigates theoretical aspects of the uneven energy depletion phenomenon recently noticed in sink-based wireless sensor networks. We consider uniformly distributed sensors, each sending roughly the same number of reports toward the closest sink. We assume an energy consumption model governed by the relation E = dα +c where d, (d ≤ tx), is the transmission distance, α ≥ 2 is the power attenuation, c is a technology-dependent positive constant, and tx is the maximum transmission range of sensors. Our results are multifold. First, we show that for α> 2, all sensors whose distance to the sink is min{tx, ( 2c 1 α−2) α} should transmit directly to the sink. Interestingly, this limit does not depend on the size of the network, expressed as the largest distance R from a sensor to the closest sink. Next, we prove that in order to minimize the total amount of energy spent on routing along a path originating at a sensor in a corona and ending at the sink, all the coronas must have the same width, equal to the above expression. This choice, however, leads to uneven energy depletion and to the creation of energy holes. We show that for α>2 the uneven energy depletion can be prevented by judicious system design, resulting in balanced energy expenditure across the network. We describe an iterative process for determining the sizes of coronas. Their optimal sizes (and corresponding transmission radii) and the number of coronas depend on R. As expected, the width of coronas in energy-balanced sensor network increases. Finally, we show that for α =2, the uneven energy depletion phenomenon is intrinsic to the system and no routing strategy can avoid the creation of an energy hole around the sink. I.

One of the notoriously difficult problems in quality of service (QoS) routing in mobile ad-hoc networks (MANET) is to ensure that the established path for a connection does not break before the end of the data transmission. This paper addresses the issue of reducing path breakage during data transmission, even if geographic location information is not available. Using delay-constrained QoS routing as an example, we propose a novel algorithm that we call ticket-based probing with stability estimation (TBP-SE) as an enhancement for the multi-path distributed QoS routing scheme proposed in Chen, S et al. (1999). Models are created to estimate relative link and path stability. During path discovery, the estimated relative stability is used to direct tickets along paths featuring high stability. Among multiple detected paths, the one with the highest relative stability is selected. Through extensive simulations, we show that our algorithm significantly improves the stability of established paths in terms of average relative path stability, path breakage speed, and percentage of data transmissions completed before path breakage

Asteroidal triple free (AT‐free) graphs have been introduced as a generalization of interval graphs, since interval graphs are exactly the chordal AT‐free graphs. While for interval graphs it is obvious that there is always a linear ordering of the vertices, such that for each triple of independent vertices the middle one intercepts any path between the remaining vertices of the triple, it is not clear that such an ordering exists for AT‐free graphs in general. In this paper we study graphs that are defined by enforcing such an ordering. In particular, we introduce two subfamilies of AT‐free graphs, namely, path orderable graphs and strong asteroid free graphs. Path orderable graphs are defined by a linear ordering of the vertices that is a natural generalization of the ordering that characterizes cocomparability graphs. On the other hand, motivation for the definition of strong asteroid free graphs comes from the fundamental work of Gallai on comparability graphs. We show that cocomparability graphs $\subset$ path orderable graphs $\subset$ strong asteroid free graphs $\subset$ AT‐free graphs. In addition, we settle the recognition question for the two new classes by proving that recognizing path orderable graphs is NP‐complete, whereas the recognition problem for strong asteroid free graphs can be solved in polynomial time.

1 THE SCOPE WE are very proud and honored to have been entrusted to guest edit this special section. The main goal was to put together a strong issue emphasizing quality and relevance to current interests in this important field. Papers were sought to cover comprehensively the algorithmic issues in the “hot” area of ad hoc and sensor networking. The concentration was on the network layer problems which can be divided into two groups: data communication and topology control problems. In data communication problems, such as routing, quality-of-service routing, geocasting, multicasting, and broadcasting, the primary goal is to fulfill a given communication task successfully between nodes in an ad hoc network. The secondary task is to minimize the communication overhead and power consumption given that in the vast majority of applications nodes run on batteries. Topology control problems are further subdivided into neighbor discovery and network organization problems. In the neighbor discovery problem, the problem is to detect neighboring nodes located within transmission range. In the network organization problem, each node should decide what communication links to establish with neighboring nodes (an example is the Bluetooth scatternet formation problem), and what power management schemes to adopt (examples are “sleep” period operations and adjusting transmission ranges). Due to their theoretical challenges and myriads of practical applications, wireless sensor networks are emerging as one of the priority research and development areas. The applications of sensor networks are envisioned primarily for monitoring the environment (e.g., motion detection, chemicals, temperature) or as key components in embedded systems (e.g., biomedical sensor engineering). This special section also sought submissions on this “hot” topic, including problems such as: physical properties, sensor training, security through intelligent node cooperation, medium access, sensor area coverage with random and deterministic placement, object location, sensor position determination, energy efficient broadcasting and activity scheduling, routing, connectivity, data dissemination and gathering, sensor centric quality of routing, path exposure, tree reconfiguration, topology construction, and transport layer. The main paradigm shift is to apply localized schemes as opposed to existing protocols requiring global information. Localized algorithms are distributed algorithms where simple local node behavior achieves a desired global objective. Localized protocols provide scalable solutions, that is, solutions for wireless networks with an arbitrary number of nodes, which is the main goal of this plan. Sensor and rooftop/mesh networks, for instance, have hundreds or thousands of nodes.

The main contribution of this work is to propose OSCAR - an opportunistic call admission protocol that provides a simple and robust solution to call admission and handoff management in LEO satellite networks. One of the features that sets OSCAR apart from existing protocols is that it avoids the overhead of reserving resources for users in a series of spotbeams along predicted user trajectories. Instead, OSCAR relies on a novel opportunistic bandwidth allocation mechanism that is very simple and efficient and does not involve maintaining complicated data structures or making expensive reservations. Extensive simulation results have shown that OSCAR achieves results comparable to those of Q-Win: it features very low call dropping probability, thus providing for reliable handoff of on-going calls, low call blocking probability for new call requests, and high bandwidth utilization.

Summary form only given. Most of the current research in wireless sensor networks (WSN, for short) is constraint driven and focuses on optimizing the use of limited resources (for example, power) at each sensor. While such constraints are important, there is a need for more general performance metrics describing the effectiveness of WSNs. There is also a need for a unified model that would enable comparison of different types of WSNs. We propose a new service-centric model that focuses on services provided by a WSN and their corresponding performance metrics. A WSN is modeled at different levels of abstraction. For each level, a set of services and a set of metrics are defined. A mapping between metrics at different levels relates high-level, mission-oriented metrics to low-level capability-oriented metrics. The proposed model consists of mission, network, region, sensor, and capability layers. Within each layer, four planes are identified, namely, communications, management, application, and generation learning. The proposed model provides a flexible, open framework for expressing and evaluating capabilities, functionalities, management, behavior, and evolution of a WSN. In addition, the proposed model provides a holistic approach to comparing WSNs and to measuring their effectiveness. The generation learning plane is unique in that it serves to extend the longevity of the network and to enhance the network effectiveness over time.

The classification problem transforms a set of N numbers in such a way that none of the first N/2 numbers exceeds any of the last N/2 numbers. A comparator network that solves the classification problem on a set of r numbers is commonly called an r-classifier. We show how the well-known Leighton's Columnsort algorithm can be modified to solve the classification problem of N=rs numbers, with 1 /spl les/ s /spl les/ r, using an r-classifier instead of an r-sorting network. Overall, the r-classifier is used O(s) times, namely, the same number of times that Columnsort applies an r-sorter. A hardware implementation is proposed that runs in optimal O(s+logr) time and uses an O(rlogr(s + logr)) work. The implementation shows that, when N= rlogr, there is a classifier network solving the classification problem on N numbers in the same O(logr) time and using the same O(rlogr) comparators as an r-classifier, thus saying a logr factor in the number of comparators over an (rlogr)-classifier.

Recently, an elegant routing protocol, the zone routing protocol (ZRP), was proposed to provide a hybrid routing framework that is locally proactive and globally reactive, with the goal of minimizing the sum of the proactive and reactive control overhead. The key idea of ZRP is that each node proactively advertises its link state over a fixed number of hops, called the zone radius. These local advertisements provide each node with an updated view of its routing zone - the collection of all nodes and links that are reachable within the zone radius. The nodes on the boundary of the routing zone are called peripheral nodes and play an important role in the reactive zone-based route discovery. The main contribution of this work is to propose a novel hybrid routing protocol - the two-zone routing protocol (TZRP) - as a nontrivial extension of ZRP. In contrast with the original ZRP where a single zone serves a dual purpose, TZRP aims to decouple the protocol's ability to adapt to traffic characteristics from its ability to adapt to mobility. In support of this goal, in TZRP each node maintains two zones: a crisp zone and a fuzzy zone. By adjusting the sizes of these two zones independently, a lower total routing control overhead can be achieved. Extensive simulation results show that TZRP is a general MANET routing framework that can balance the trade offs between various routing control overheads more effectively than ZRP in a wide range of network conditions.

Abstract In recent years, a significant number of clustering schemes have been proposed in the literature. Most of them treat cluster initialization and cluster maintenance differently as if they were two entirely different undertakings. The main contribution of this work is a unifying way of looking at clustering in MANET. We make an important point: there is no difference between cluster initialization and cluster maintenance, and one algorithm should gracefully blend into the other. To illustrate the feasibility of this concept, we propose a novel tree‐based clustering algorithm for MANET based on a number of properties of diameter‐2 graphs. The algorithm is cluster‐centric and, unlike the vast majority of algorithms in the literature, works in the presence of node mobility. Extensive simulation results show the effectiveness of our algorithm when compared to other clustering schemes proposed in the recent literature. Copyright © 2004 John Wiley & Sons, Ltd.

The network model assumed in this paper consists of tiny, energy-constrained, commodity sensors massively deployed alongside with one or more sink nodes that provide the interface to the outside world. The sensors in the network are initially anonymous and unaware of their location. Our main contribution is to propose a new robust and energy-efficient solution for secure operation of wireless sensor networks. The paper motivates a new paradigm where security is based upon using parameterized frequency hopping and cryptographic keys in a unified framework to provide differential security services for wireless sensor networks.

The main contribution of this work is to propose an efficient parallel prefix sums architecture based on the recently-developed technique of shift switching with domino logic, where the charge/discharge signals propagate along the switch chain producing semaphores in a network that is fast and highly hardware-compact. The proposed architecture for computing the prefix sums of N-1 bits features a total delay of (4 log N + /spl radic/N-2)/sub */T/sub d/, where T/sub d/ is the delay for charging or discharging a row of two prefix sum units of eight shift switches. Our simulation results show that, under 0.8-micron CMOS technology, the delay T/sub d/ does not exceed 1 ns. As it turns out, our design is faster than any design known to us for values on N in the range 1 /spl les/ N /spl les/ 2/sup 10/. Yet, another important and novel feature of the proposed architecture is that it requires very simple controls, partially driven by the semaphores. This significantly reduces the hardware complexity of the design and fully utilizes the inherent speed of the process.

Wireless networks are expected to support real-time interactive multimedia traffic and must be able, therefore, to provide their users with quality-of-service (QoS) guarantees. Although the QoS provisioning problem arises in wireline networks as well, mobility of hosts and scarcity of bandwidth makes QoS provisioning a challenging task in wireless networks. It has been noticed that multimedia applications can tolerate and gracefully adapt to transient fluctuations in the QoS that they receive from the network. The additional flexibility afforded by the ability of multimedia applications to tolerate and adapt to transient changes in QoS can be exploited by protocol designers to significantly improve the overall performance of wireless systems. This paper presents a fair resource allocation protocol for multimedia wireless networks that uses a combination of bandwidth reservation and bandwidth borrowing to provide network users with QoS in terms of guaranteed bandwidth, call blocking, and call dropping probabilities. Our view of fairness was inspired by the well-known max-min fairness allocation protocol for wireline networks. Simulation results are presented that compare our protocol to similar schemes.

Abstract The paper describes a media access system for satellite network uplinks. The media access protocol is designed to support a range of low‐level protocols using a dual‐framing system, that is, there is a synchronous traffic subframe in which registered station requests are assigned fixed blocks or slots and an asynchronous traffic subframe for unregistered station random access on a contention basis. Slots for the registered stations are assigned through request to the satellite; the remaining frame time is assigned to unregistered stations. Capacity waste through contention resulting in collisions is minimized. The system uses dynamic bandwidth (bit rate) allocation for each channel, that is, the base frequency and bandwidth are changed for each channel at frame boundaries. The total bandwidth for the sum of all uplink channels is fixed. Channels that have low load based upon their request in a prior uplink frame are assigned lower bandwidth, while those with higher loading are provided larger bandwidth. By sharing bandwidth over channels at frame boundaries, overall network efficiency and fairness are significantly enhanced. Bandwidth allocation is decided in the satellite. It allocates sufficient bandwidth for all synchronous traffic and then commits the remaining bandwidth to asynchronous traffic. Here, the allocation for asynchronous traffic provides each channel with sufficient slots so that equal probability of success for stations sharing the channel can be expected. The combination of traffic assignment and bandwidth allocation provides significant improvement in overall network efficiency and fairness for all traffic types. The hardware implementation of media access for variable bandwidth sharing between channels use the concepts of Digital Software Radio. Copyright © 2003 John Wiley & Sons, Ltd.

Multimedia LEO satellite networks will play an important role in providing truly global coverage required by mobile personal communication services. Due to the high mobility inherent to LEO systems, a number of challenging technical problems arise. The first contribution of this work is to propose a realistic mobility model, taking into account the rotation of the Earth, which was systematically ignored in the literature. Our second contribution is a novel resource reservation strategy, termed sequential probabilistic resource reservation (SPR), specifically designed to minimize connection interruption due to handoffs. Finally, we propose a novel connection admission control (CAC) algorithm, differentiating real-time and non-real-time services. Performance results obtained by simulation show that the novel mobility model is essential for a realistic network performance evaluation and that the novel SPR strategy offers low handoff blocking probability for both service classes and low new call blocking probability for non-real-time connections.

Now that cellular networks are being called upon to support real-time interactive multimedia traffic such as video teleconferencing, these networks must be able to provide their users with quality-of-service (QoS) guarantees. Although the QoS provisioning problem arises in wireline networks as well, mobility of hosts, scarcity of bandwidth, and channel fading make QoS provisioning a challenging task in wireless networks. It has been noticed that multimedia applications can tolerate and gracefully adapt to transient fluctuations in the QoS that they receive from the network. The management of such adaptive multimedia applications is becoming a new research area in wireless networks. As it turns out, the additional flexibility afforded by the ability of multimedia applications to tolerate and adapt to transient changes in the QoS parameters can be exploited by protocol designers to significantly improve the overall performance of wireless systems. The main contribution of this paper is to propose a novel, rate-based, borrowing scheme for QoS provisioning in high-speed cellular networks carrying multimedia traffic. Our scheme attempts to allocate the desired bandwidth to every multimedia connection originating in a cell or being handed off to the cell. The novelty of our scheme is that, in case of insufficient bandwidth, in order not to deny service to requesting connections (new or hand-off), bandwidth will be borrowed, on a temporary basis, from existing connections. Our borrowing scheme guarantees that no connection gives up more than its fair share of bandwidth, in the sense that the amount of bandwidth borrowed from a connection is proportional to its tolerance to bandwidth loss. Importantly, our scheme ensures that the borrowed bandwidth is promptly returned to the degraded connections. Extensive simulation results show that our rate-based QoS provisioning scheme outperforms the best previously known schemes in terms of call dropping probability, call blocking probability, and bandwidth utilization.

A radio network is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations are identical and cannot be distinguished by serial or manufacturing number. The leader election problem asks to designate one of the stations as leader. In this work, we focus on single-channel, single-hop radio networks. We assume that time is slotted and all transmissions occur at slot boundaries. In each time slot, the stations transmit on the channel with some probability until, eventually, one of the stations is declared leader. A leader election protocol is said to be uniform if, in each time slot, every station transmits with the same probability. In a seminal paper, Willard (1986) presented a uniform leader election protocol for single-channel single-hop radio stations terminating in log log n+o(log log n) expected time slots. It was open for more than 15 years whether Willard's protocol featured the same time performance with "high probability." One of our main contributions is to show that, unfortunately, this is not the case. Specifically, we prove that for every parameter f/spl isin/e/sup O(n)/, in order to ensure termination with probability exceeding 1-1/f, Willard's protocol must take log log n+/spl Omega/(/spl radic/f) time slots. The highlight of this work is a novel uniform leader election protocol that terminates, with probability exceeding 1-1/f, in log log n+o(log log n)+O(log f) time slots. Finally, we provide simulation results that show that our leader election protocol outperforms Willard's protocol in practice.

The broadcast communication model (BCM, for short) is a distributed system with no central arbiter populated by p stations denoted by S(1),S(2),...,S(p) that communicate by transmitting messages on a communication channel. The stations are assumed to have the computing power of a laptop computer and to be synchronous, in particular, they all run the same program, albeit on different data. We assume that a station is expending power while transmitting or receiving messages. As it turns out, one of the most effective energy-saving strategies is to mandate individual stations to power their transceiver off (i.e., go to sleep) whenever they are not transmitting or receiving messages. Suppose that the p stations of the BCM store collectively n items such that station S(i), (1 /spl les/ i /spl les/ p), stores s/sub i/ items. Each of the items has a unique destination which is the identity of the station to which the item must be routed. The goal is to route all the items to their destinations, while expending as little energy as possible. Since, in the worst case, each item must be transmitted at least once, every routing protocol must take at least n time slots to terminate. Furthermore, station S(i), (1 /spl les/ i /spl les/ p), must be awake for at least s/sub i/ + d/sub i/ time slots, where d/sub i/ denotes the number of items destined for S(i). Since, in the BCM, every station is within transmission range from every other station, the design of energy-efficient protocols is highly nontrivial. An additional complication stems from the inherent asymmetry of the routing problem: no destination knows the identity of the sender, precluding a priori arrangements between senders and receivers. The main contribution of this work is to present an energy-efficient routing protocol for the single-channel, p-station BCM. We show that for every f /spl ges/ 1, the task of routing n items in this model can be completed with probability exceeding 1 - 1/f, in n + O(q + ln f) time slots and that no station S(i), (1 /spl les/ i /spl les/ p), has to be awake for more than s/sub i/ + d/sub i/ + O(q/sub i/ + r/sub i/ log p + log f) time slots, where q/sub i/ is the number of stations that have items destined for S(i), q = q/sub 1/ + q/sub 2/ +/spl middot//spl middot//spl middot/+ q/sub p/, and r/sub i/ is the number of stations for which S(i) has items. Since q/sub i/ /spl les/ d/sub i/, r/sub i/ /spl les/ s/sub i/ and q /spl les/ n, our protocol is close to optimal both in terms of overall completion time and energy efficiency.

In recent years, the areas of mobile computing and wireless networks have seen explosive growth both in terms of the number of services provided and the types of technologies that have become available. Indeed, cellular telephony, radio paging, cellular data, and even rudimentary cellular multimedia services have become commonplace and the demand for enhanced capabilities will continue to grow into the foreseeable future. It is anticipated that, in the not-so-distant future, mobile users will be able to access their data and other services, such as electronic mail, video telephony, stock market news, map services, electronic banking, while on the move. Already today, there are more portable phones than computers connected to the Internet. However, the trend toward the Internet with its protocols around IP as the common basis for all communication applications seems to be quite clear.

Unlike terrestrial networks, LEO satellite networks are expected to provide a truly global coverage and to support sophisticated PCS services including multimedia communications. However, LEO satellite networks are known to have a serious mobility management problem. The main contribution of this work Is to propose a predictive handoff management and admission control strategy for multimedia LEO satellite networks. Simulation results have shown that our scheme offers very low call dropping probability for multimedia connections while, at the same time, keeping resource utilization high.

A radio network is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations are identical and cannot be distinguished by serial or manufacturing number. The leader election problem asks to designate one of the stations as leader. A leader election protocol is said to be uniform if in each time slot every station transmits with the same probability. In a seminal paper Willard (1986) presented a uniform leader election protocol for single-channel single-hop radio stations terminating in log log n+o(log log n) expected time slots. It was open whether Willard's protocol featured the same time performance with "high probability". We propose a uniform leader election protocol that terminates, with probability exceeding 1-1/f for every f/spl ges/1, in log log n+o(log log n)+O(log f) time slots. We also prove that for every f/spl isin/e/sup O(n)/, in order to ensure termination with probability exceeding 1-1/f, Willard's protocol must take log log n+/spl Omega/(/spl radic/f) time slots. Finally, we provide simulation results that show that our leader election outperforms Willard's leader election protocol in practice.

The main contribution of this work is to show that a number of fundamental and seemingly unrelated problems in database design, pattern recognition, robotics, computational geometry, and image processing can be solved simply and elegantly by stating them as instances of a unifying algorithmic framework that we call the multiple query problem. The multiple query problem (MQ, for short) is a 5-tuple (Q, A, D, /spl phi/, /spl oplus/), where Q is a set of queries, A is a set of items, D is a set of solutions, /spl phi/: Q/spl times/A/spl rarr/D is a function, and /spl oplus/ is a commutative and associative binary operator over D. The input to the MQ problem consists of a sequence Q=of m queries from Q and of a sequence A=of n items from A. The goal is to compute, for every query q/sub i/ (1/spl les/i/spl les/m) its solution defined as /spl phi/(q/sub i/,A)=/spl phi/(q/sub i/,a/sub 1/)/spl oplus//spl phi/(q/sub i/,a/sub 2/)/spl oplus//spl middot//spl middot//spl middot//spl oplus//spl phi/(q/sub i/,a/sub n/). We begin by discussing a generic algorithm that solves a large class of MQ problems in O(/spl radic/m+f(n)) time on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n, where f(n) is the time necessary to compute the expression d/sub 1/ /spl oplus/ d/sub 2/ /spl oplus//spl middot//spl middot//spl middot//spl oplus/ d/sub n/ with d/sub i/ /spl isin/ D on such a platform. We then go on to show that the MQ framework affords us an optimal algorithm for the multiple point location problem on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n. Given a set A of n points and a set Q of m (m/spl les/n) points in the plane, our algorithm reports, in O(/spl radic/m+log log n) time, all points of Q that lie inside the convex hull of A. Quite surprisingly, our algorithm solves the multiple point location problem without computing the convex hull of A which, in itself, takes /spl Omega/(/spl radic/n) time on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n. Finally, we prove an /spl Omega/(/spl radic/m+g(n)) time lower bound for nontrivial MQ problems, where g(n) is the lower bound for evaluating the expression d/sub 1/ /spl oplus/ d/sub 2/ /spl oplus//spl middot//spl middot//spl middot//spl oplus/ d/sub n/ with d/sub i/ /spl isin/ D, on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n.

A radio network (RN, for short) is a distributed system populated by small, hand-held commodity devices running on batteries. Since recharging batteries may not be possible while on mission, we are interested in designing protocols that are highly energy efficient. One of the most effective energy-saving strategies is to mandate that the stations go to sleep whenever they do not transmit or receive messages. It is well known that a station is expending power while its transceiver is active, that is, while transmitting or receiving a packet. It is perhaps surprising at first that a station is expending power even if it receives a packet that is not destined for it. Since, in single-hop radio networks, every station is within transmission range from every other station, the design of energy-efficient protocols is highly nontrivial. An instance of the permutation routing problem involves p stations of an RN, each storing n/p items. Each item has a unique destination which is the identity of the station to which the item must be routed. The goal is to route all the items to their destinations while expending as little energy as possible. Since, in the worst case, each item must be transmitted at least once, every permutation routing protocol must take n/k time slots. Similarly, each station must be awake for at least n/p time slots to transmit and/or receive packets. Our main contribution is to present an almost optimal energy-efficient permutation routing protocol for a k-channel, a p-station RN that routes n packets in at most (2d+2b+1)n/k+k time slots with no station being awake for more than (4d+7b-1)n/p time slots, where d=[(logp/k)/(logn/p)], b=[(log k)/(logn/p)] and k/spl les//spl radic/(p/2). Since, in most real-life situations, the number n of packets to route, the number p of stations in the RN, and the number k of channels available satisfy the relation k/spl Lt/p/spl Lt/n, it follows that d and b are very small.

A radio network (RN, for short) is a distributed system consisting of n radio stations. The initialization problem is to assign each of the n stations of the RN a unique ID. The initialization problem is non-trivial since the stations are assumed to be indistinguishable. The main contribution of this work is to propose energy-efficient randomized initialization protocols for RNs lacking collision detection capabilities. We show that if the number n of stations is known beforehand, the single-channel RN can be initialized by a protocol that terminates, with probability exceeding 1-1/n, in O(n) time slots, with no station being awake for more than O(log log n) time slots.

A radio network (RN, for short) is a distributed system populated by small, bulk-produced, handheld radio transceivers, running on batteries. Since recharging batteries may not be possible while on mission, it is important to design protocols that are highly energy-efficient. In this work we address the problem of energy-efficient routing in k-channel RNs. An important subproblem is that of permutation routing an instance of which involves p stations each storing n/p items. Since in the worst case each item must be transmitted at least once, every permutation routing protocol must take n/k time slots. Similarly, each station must be awake for at least n/p time slots. Our main contribution is to present an almost optimal energy-efficient permutation routing protocol on the k-channel, p-station RN that routes n items in at most (2d+2b+1)n/k+k time slots, with no station being awake for more than (4d+7b-1)n/p time slots, where d=[log p/k/log n/p], b=[log k/log n/p], and k/spl les//spl radic/(p/2).

We present a hardware-algorithm for sorting N elements using either a p-sorter or a sorting network of fixed I/O size p while strictly enforcing conflict-free memory accesses. To the best of our knowledge, this is the first realistic design that achieves optimal time performance, running in /spl Theta/(NlogN/plogp) time for all ranges of N. Our result completely resolves the problem of designing an implementable, time-optimal algorithm for sorting N elements using a p-sorter. More importantly, however, our result shows that, in order to achieve optimal time performance, all that is needed is a sorting network of depth O(log/sup 2/p) such as, for example, Batcher's classic bitonic sorting network.

The main contribution of this work is to offer a simple and cost-efficient parallel algorithm that, given an arbitrary n-vertex cubic graph G as input, produces an orthogonal grid drawing of G in O(log n) time, using n processors on an EREW PRAM. Our algorithm matches the time and cost performance of the best previously-known algorithm while at the same time improving the constant factors involved in two important metrics: layout area and number of bends. More importantly, however, our algorithm stands out by its conceptual simplicity and ease of implementation.

We address the problem of designing efficient and scalable hardware-algorithms for computing the sum and prefix sums of a w/sup k/-bit, (k/spl ges/2), sequence using as basic building blocks linear arrays of at most w/sup 2/ shift switches, where w is a small power of 2. An immediate consequence of this feature is that in our designs broadcasts are limited to buses of length at most w/sup 2/. We adopt a VLSI delay model where the "length" of a bus is proportional with the number of devices on the bus. We begin by discussing a hardware-algorithm that computes the sum of a w/sup k/-bit binary sequence in the time of 2k-2 broadcasts, while the corresponding prefix sums can be computed in the time of 3k-4 broadcasts. Quite remarkably, in spite of the fact that our hardware-algorithm uses only linear arrays of size at most w/sup 2/, the total number of broadcasts involved is less than three times the number required by an "ideal" design. We then go on to propose a second hardware-algorithm, operating in pipelined fashion, that computes the sum of a kw/sup 2/-bit binary sequence in the time of 3k+[log/sub w/ k]=3 broadcasts. Using this design, the corresponding prefix sums can be computed in the time of 4k+[log/sub w/ k]-5 broadcasts.

AbstractÐAd hoc networks are self-organizing entities that are deployed on demand in support of various events including collaborative computing, multimedia classroom, disaster-relief, search-and-rescue, interactive mission planning, and law enforcement operations. One of the fundamental tasks that have to be addressed when setting up an ad hoc network (AHN, for short) is initialization. This involves assigning each of the n stations in the AHN a distinct ID number (e.g., a local IP address) in the range from 1 to n. Our main contribution is to propose efficient randomized initialization protocols for AHNs. We begin by showing that if the number 1 n of stations is known beforehand, an n-station, single-channel AHN can be initialized with probability exceeding 1 n,inen‡ p O … n log n† time slots, regardless of whether the AHN has collision detection capability. We then go on to show that even if n is not 1 known in advance, an n-station, single-channel AHN with collision detection can be initialized with probability exceeding 1 n,in

A radio network (RN, for short) is a distributed system consisting of n radio stations. We assume that the stations are small, bulk-produced, hand-held devices running on batteries and cannot be distinguished by serial or manufacturing number. Since recharging batteries may not be possible while on mission, we are interested in designing protocols that are highly energy-efficient. The initialization problem is to assign each of the n stations in the RN a unique ID. The initialization problem is nontrivial since the stations are assumed to be indistinguishable. The problem is fundamental, since practically all communication protocols for RNs proceed under the assumption that the RN has been initialized in advance. The main contribution of this work is to propose energy-efficient randomized initialization protocols for single-hop RNs lacking collision detection capabilities. First, we show that if the number n of stations is known beforehand, the single-channel RN can be initialized by a protocol that terminates, with probability exceeding 1-/sup 1///sub n/ in O(n) time slots, with no station being awake for more than O(log log n) time slots. We then go on to address the multichannel case and show that if k, (k/spl ges/1), channels are available, an n-station RN can be initialized, with probability exceeding 1-/sup 1///sub n/, in O(/sup n///sub k/+log n) time slots, with no station being awake for more than O(log log n) time slots.

An independent set of three vertices is called an asteroidal triple if between each pair in the triple there exists a path that avoids the neighborhood of the third. A graph is asteroidal triple-free (AT-free) if it contains no asteroidal triple. The motivation for this investigation is provided, in part, by the fact that AT-free graphs offer a common generalization of interval, permutation, trapezoid, and cocomparability graphs. Previously, the authors have given an existential proof of the fact that every connected AT-free graph contains a dominating pair, that is, a pair of vertices such that every path joining them is a dominating set in the graph. The main contribution of this paper is a constructive proof of the existence of dominating pairs in connected AT-free graphs. The resulting simple algorithm, based on the well-known lexicographic breadth-first search, can be implemented to run in time linear in the size of the input, whereas the best algorithm previously known for this problem has complexity O(|V| 3 ) for input graph G=(V,E). In addition, we indicate how our algorithm can be extended to find, in time linear in the size of the input, all dominating pairs in a connected AT-free graph with diameter greater than 3. A remarkable feature of the extended algorithm is that, even though there may be O(|V| 2 ) dominating pairs, the algorithm can compute and represent them in linear time.

The first main contribution of this work is to propose an efficient VLSI architecture obtained by augmenting the Mesh with Multiple Broadcasting (MMB) with precharged 1-bit row and column buses. The new architecture, which we call Mesh with Hybrid Buses (MHB for short), is realizable in VLSI with no increase in the area or the wiring complexity of the MMB chip. Our second main contribution is to show that the MHB is extremely well-suited for solving an entire slew of digital geometry tasks. The MHB is not a reconfigurable architecture. Yet, quite remarkably, for a large number of fundamental digital geometry tasks, the MHB offers a level of performance previously attained only by reconfigurable architectures. Specifically, with a digital image pretiled onto a MHB of size /spl radic/n/spl times//spl radic/n one pixel per processor, we show that the problems of computing the convex hull of the image, computing the diameter and the width of the image, deciding whether a set of digital points is a digital line, computing the maximum distance between two images, deciding whether two images are linearly separable, computing several moments and low-level descriptors of the image, including the perimeter, area, center, and median row of its convex hull, can be solved in O(log n) time. By contrast, the fastest possible algorithms for the problems above on the MMB run in /spl Theta/(n/sup 1/6/) time. Finally, we go on to show that, with minor changes, our algorithms can be implemented to run within cost-optimality on a MHB of size /spl radic/n/log n/spl times//spl radic/n/log n.

The main contribution of this work is to present elegant broadcast-efficient protocols for permutation routing, ranking, and sorting on single-hop Mobile Radio Networks with p stations and k radio channels, denoted by MRN(p,k). Clearly, any protocol performing these tasks on n items must perform /sup n///sub k/ broadcast rounds because each item must be broadcast at least once. We begin by presenting an optimal off-line permutation routing protocol using /sup n///sub k/ broadcast rounds for arbitrary k, p, and n. Further, we show that optimal on-line routing can be performed in /sup n///sub k/ broadcast rounds, provided that either k=1 or p=n. We then go on to develop an online routing protocol that takes 2/sup n///sub k/+k-1 broadcast rounds on the MRN(p,k), whenever k/spl les//spl radic//sup p///sub 2/. Using these routing protocols as basic building blocks, we develop a ranking protocol that takes 2/sup n///sub k/+o(/sup n///sub k/) broadcast rounds as well as a sorting protocol that takes 3/sup n///sub k/+o(/sup n///sub k/) broadcast rounds, provided that k /spl epsiv/ o(/spl radic/n) and p=n. Finally, we develop a ranking protocol that takes 3/sup n///sub k/+o(/sup n///sub k/) broadcast rounds, as well as a sorting protocol that takes 4/sup n///sub k/+o(/sup n///sub k/) broadcast rounds on the MRN(p,k), provided that k/spl les//spl radic//sup p///sub 2/ and p /spl epsiv/ o(n). Featuring very low proportionality constants, our protocols offer a vast improvement over the state of the art.

Sorting networks of fixed I/O size p have been used, thus far, for sorting a set of p elements. Somewhat surprisingly, the important problem of using such a sorting network for sorting arbitrarily large datasets has not been addressed in the literature. Our main contribution is to propose a simple sorting architecture whose main feature is the pipelined use of a sorting network of fixed I/O size p to sort an arbitrarily large data set of N elements. A noteworthy feature of our design is that no extra data memory space is required, other than what is used for storing the input. As it turns out, our architecture is feasible for VLSI implementation and its time performance is virtually independent of the cost and depth of the underlying sorting network. Specifically, we show that by using our design N elements can be sorted in /spl Theta/(N/p log N/p) time without memory access conflicts. Finally, we show how to use an AT/sup 2/-optimal sorting network of fixed I/O size p to construct a similar architecture that sorts N elements in /spl Theta/(N/p log N/p log p) time.

This paper presents novel very large scale integration (VLSI) architectures in support of an efficient implementation of Leighton's well-known Columnsort. The designs take advantage of reconfigurable bus architectures enhanced with simple shift switches. Our first main contribution is to show that Columnsort can be partitioned into two components: a hardware scheme involving the task of sorting arrays of small size and a hardware or software scheme that involves simple data movement tasks. Our second main contribution is to demonstrate that the dynamically reconfigurable mesh architecture can be exploited to obtain a small and efficient hardware sorter. The resulting architectures feature high regularity of circuitry, simplicity of control structure, and adaptability. Both theoretical analyses and simulation tests have shown that the proposed VLSI architectures for sorting are superior to existing designs in the context of sorting small and moderate size arrays.

Sorting is a fundamental problem with applications in all areas of computer science and engineering. In this work, we address the problem of sorting on mesh connected computers enhanced by endowing each row and each column with its own dedicated high-speed bus. This architecture, commonly referred to as a mesh with multiple broadcasting, is commercially available and has been adopted by the DAP family of multiprocessors. Somewhat surprisingly, the problem of sorting m, (m/spl les/n), elements on a mesh with multiple broadcasting of size /spl radic/n/spl times//spl radic/n has been studied, thus far, only in the sparse case, where m/spl isin//spl Theta/(/spl radic/n) and in the dense case, where m/spl isin//spl Theta/O(/spl radic/n). Yet, many applications require using an existing platform of size /spl radic/n/spl times//spl radic/n for sorting m elements, with /spl radic/n<m/spl les/n. Our main contribution is to present the first known adaptive time- and VLSI-optimal sorting algorithm for meshes with multiple broadcasting. Specifically we show that, for every choice of a constant 0

A number of applications in computer-aided manufacturing, CAD, and computer-aided geometric design ask for triangulating pieces of material with defects. These tasks are known collectively as constrained triangulations. Recently, a powerful architecture called the reconfigurable mesh has been proposed: In essence, a reconfigurable mesh consists of a mesh-connected architecture augmented by a dynamically reconfigurable bus system. The main contribution of this paper is to show that the flexibility of the reconfigurable mesh can be exploited for the purpose of obtaining constant-time algorithms for a number of constrained triangulation problems. These include triangulating a convex planar region containing any constant number of convex holes, triangulating a convex planar region in the presence of a collection of rectangular holes, and triangulating a set of ordered line segments. Specifically with a collection of O(n) such objects as input, our algorithms run in O(1) time on a reconfigurable mesh of size n/spl times/n. To the best of our knowledge, this is the first time constant time solutions to constrained triangulations are reported on this architecture.

Consider a set P of points in the plane sorted by the x-coordinate. A point p in P is said to be a proximate point if there exists a point q on the x-axis such that p is the closest point to q over all points in P. The proximate point problem is to determine all the proximate points in P. Our main contribution is to propose optimal parallel algorithms for solving instances of size n of the proximate points problem. We begin by developing a work-time optimal algorithm running in O(log log n) time and using n/loglogn Common-CRCW processors. We then go on to show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. In addition to being work-time optimal, our EREW algorithm turns out to also be time-optimal. Our second main contribution is to show that the proximate points problem finds interesting, and quite unexpected, applications to digital geometry and image processing. As a first application, we present a work-time optimal parallel algorithm for finding the convex hull of a set of n points in the plane sorted by x-coordinate; this algorithm runs in O(log log n) time using n/logn Common-CRCW processors. We then show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. Next, we show that the proximate points algorithms afford us work-time optimal (resp, time-optimal) parallel algorithms for various fundamental digital geometry and image processing problems.

The problem of computing the convex hull of a set of n sorted points in the plane is one of the fundamental tasks in image processing, pattern recognition, cellular network design, and robotics, among many others. Somewhat surprisingly, in spite of a great deal of effort, the best previously known algorithm to solve this problem on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n was running in O(log2 n) time. It was open for more than ten years to obtain an algorithm for this important problem running in sublogarithmic time. Our main contribution is to provide the first breakthrough: we propose an almost optimal convex hull algorithm running in O((log log n)/sup 2/) time on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n. With slight modifications, this algorithm can be implemented to run in O((log log n)/sup 2/) time on a reconfigurable mesh of size /spl radic/n/loglogn/spl times//spl radic/n/loglogn. Clearly, the latter algorithm is work-optimal. We also show that any algorithm that computes the convex hull of a set of n sorted points on an n-processor reconfigurable mesh must take /spl Omega/(log log n) time. Our result opens the door to an entire slew of efficient convex-hull-based algorithms on reconfigurable meshes.

For 2/spl les/k/spl les/n, the k-merge problem is to merge a collection of ksorted sequences of total length n into a new sorted sequence. The k-merge problem is fundamental as it provides a common generalization of both merging and sorting. The main contribution of this work is to give simple and intuitive work-time optimal algorithms for the k-merge problem on three PRAM models, thus settling the status of the k-merge problem. We first prove that /spl Omega/(n log k) work is required to solve the k-merge problem on the PRAM models. We then show that the EREW-PRAM and both the CREW-PRAM and the CRCW require /spl Omega/(log n) time and /spl Omega/(log log n+log k) time, respectively, provided that the amount of work is bounded by O(n log k). Our first k-merge algorithm runs in /spl Theta/(log n) time and performs /spl Theta/(n log k) work on the EREW-PRAM. Finally, we design a work-time optimal CREW-PRAM k-merge algorithm that runs in /spl Theta/(log log n+log k) time and performs /spl Theta/(n log k) work. This latter algorithm is also work-time optimal on the CREW-PRAM model. Our algorithms completely settle the status of the k-merge problem on the three main PRAM models.

A matrix A of size m/spl times/n containing items from a totally ordered universe is termed monotone if, for every i, j, 1/spl les/i2. In case m=n/sup /spl epsiv// for some constant /spl epsiv/, (0

Task scheduling is important for the proper functioning of parallel processor systems. The static scheduling of tasks onto networks of parallel processors is well-defined and documented in the literature. However, in many practical situations a priori information about the tasks that need to be scheduled is not available. In such situations, tasks usually arrive dynamically and the scheduling should be performed on-line or "on the fly". In this paper, we present a framework based on stochastic reinforcement learning, which is usually used to solve optimization problems in a simple and efficient way. The use of reinforcement learning reduces the dynamic scheduling problem to that of learning a stochastic approximation of an unknown average error surface. The main advantage of the proposed approach is that no prior information is required about the parallel processor system under consideration. The learning system develops an association between the best action (schedule) and the current state of the environment (parallel system). The performance of reinforcement learning is demonstrated by solving several dynamic scheduling problems. The conditions under which reinforcement learning can used to efficiently solve the dynamic scheduling problem are highlighted.

We present simple and broadcast-efficient ranking and sorting algorithms on the broadcast communication model (BCM, for short) with few communication channels. At the heart of our algorithms is a new and elegant sampling and bucketing scheme whose main feature is that the resulting buckets are well balanced, making costly rebalancing unnecessary. The resulting ranking algorithm uses only 2 n/k+o(n/k) broadcast rounds, while 3 n/k+o(n/k) broadcast rounds are needed for sorting on a L-channel, n-processor BCM whenever k/spl les//spl radic/(n/log n). These bounds are fairly tight, when compared with the trivial lower bound of n/k broadcast rounds necessary to permute n items using k communication channels.

An independent set of three vertices such that each pair is joined by a path that avoids the neighborhood of the third is called an asteroidal triple. A graph is asteroidal triple-free (AT-free) if it contains no asteroidal triples. The motivation for this investigation was provided, in part, by the fact that the AT-free graphs provide a common generalization of interval, permutation, trapezoid, and cocomparability graphs. The main contribution of this work is to investigate and reveal fundamental structural properties of AT-free graphs. Specifically, we show that every connected AT-free graph contains a dominating pair, that is, a pair of vertices such that every path joining them is a dominating set in the graph. We then provide characterizations of AT-free graphs in terms of dominating pairs and minimal triangulations. Subsequently, we state and prove a decomposition theorem for AT-free graphs. An assortment of other properties of AT-free graphs is also provided. These properties generalize known structural properties of interval, permutation, trapezoid, and cocomparability graphs.

The main contribution of this paper is to present simple and elegant podality-based algorithms for a variety of computational tasks motivated by, and finding applications to, pattern recognition, computer graphics, computational morphology, image processing, robotics, computer vision, and VLSI design. The problems that we address involve computing the convex hull, the diameter, the width, and the smallest area enclosing rectangle of a set of points in the plane, as well as the problems of finding the maximum Euclidian distance between two planar sets of points, and of constructing the Minkowski sum of two convex polygons. Specifically, we show that once we fix a positive constant /spl epsiv/, all instances of size m, (n/sup 1/2 +/spl epsiv///spl les/m/spl les/n) of the problems above, stored in the first [m//spl radic/n] columns of a mesh with multiple broadcasting of size /spl radic/n/spl times//spl radic/n can be solved time-optimally in /spl Theta/(m//spl radic/n) time.

Query processing is a crucial component of various application domains including information retrieval, database design and management, pattern recognition, robotics, and VLSI. Many of these applications involve data stored in a matrix satisfying a number of properties. One property that occurs time and again specifies that the rows and the columns of the matrix are independently sorted. It is customary to refer to such a matrix as sorted. An instance of the batched searching and ranking problem (BSR) involves a sorted matrix A of items from a totally ordered universe, along with a collection Q of queries. Q is an arbitrary mix of the following query types: for a search query q/sub j/, one is interested in an item of A that is closest to q/sub j/; for a rank query q/sub j/ one is interested in the number of items of A that are strictly smaller than q/sub j/. The BSR problem asks for solving all queries in Q. The authors consider the BSR problem in the following context: the matrix A is pretiled, one item per processor, onto an enhanced mesh of size /spl radic/n/spl times//spl radic/n; the m queries are stored, one per processor, in the first m//spl radic/n~ columns of the platform. Their main contribution is twofold. First, they show that any algorithm that solves the BSR problem must take at least /spl Omega/(max{logn, /spl radic/m}) time in the worst case. Second, they show that this time lower bound is tight on meshes of size /spl radic/n/spl times//spl radic/n enhanced with multiple broadcasting, by exhibiting an algorithm solving the BSR problem in /spl Theta/(max{logn, /spl radic/m}) time on such a platform.

Given a set S of n points in the plane and two directions r/sub 1/ and r/sub 2/, the Angle-Restricted All Nearest Neighbor problem (ARANN, for short) asks to compute, for every point p in S, the nearest point in S lying in the planar region bounded by two rays in the directions r/sub 1/ and r/sub 2/ emanating from p. The ARANN problem generalizes the well-known ANN problem and finds applications to pattern recognition, image processing, and computational morphology. Our main contribution is to present an algorithm that solves an instance of size n of the ARANN problem in O(1) time on a reconfigurable mesh of size n/spl times/n. Our algorithm is optimal in the sense that /spl Omega/(n/sup 2/) processors are necessary to solve the ARANN problem in O(1) time. By using our ARANN algorithm, we can provide O(1) time solutions to the tasks of constructing the Geographic Neighborhood Graph and the Relative Neighborhood Graph of n points in the plane on a reconfigurable mesh of size n/spl times/n. We also show that, on a somewhat stronger reconfigurable mesh of size n/spl times/n/sup 2/, the Euclidean Minimum Spanning Tree of n points can be computed in O(1) time.

Recently it has been noticed that for semigroup computations and for selection, rectangular meshes with multiple broadcasting yield faster algorithms than their square counterparts. The contribution of the paper is to provide yet another example of a fundamental problem for which this phenomenon occurs. Specifically, we show that the problem of computing the convex hull of a set of n sorted points in the plane can be solved in O(n/sup 1/8/ log /sup 3/4/) time on a rectangular mesh with multiple broadcasting of size n/sup 3/8/ log/sup 1/4/ n/spl times/n/sup 5/8//log/sup 1/4/n. The fastest previously known algorithms on a square mesh of size /spl radic/n/spl times//spl radic/n run in O(n/sup 1/6/) time in case the n points are pixels in a binary image, and in O(n/sup 1/6/log/sup 3/2/ n) time for sorted points in the plane.

Given a family I of intervals, two intervals in I interlock if they overlap but neither of them strictly contains the other. A set of intervals in which every two are related in the reflexive transitive closure of the interlock relation is referred to as an interlocking set. The task is determining the maximal interlocking sets of I arises in numerous applications, including traffic control, robot arm manipulation, segmentation of range images, routing, automated surveillance systems, recognizing polygonal configurations, and code generation for parallel machines. Our first contribution is to show that any sequential algorithm that computes the maximal interlocking sets of a family of n intervals must take /spl Omega/(n log n) time in the algebraic tree model. Next, we show that any parallel algorithm for this problem must take /spl Omega/(log n) time in the CREW model even if an infinite number of processors and memory cells are available. We then go on to show that both the sequential and the parallel lower bounds are tight by providing matching algorithms running, respectively, in /spl Theta/(n log n) sequential time and in /spl Theta/(log n) time using n processors in the CREW model. At the same time, if the endpoints of the intervals are specified in sorted order, our sequential algorithm runs in O(n) time, improving the best previously known result. It is interesting to note that even if the endpoints are sorted, /spl Omega/(log n) is a time lower bound for solving the problem in the CREW model, regardless of the amount of resources available. As an application of our algorithm for interlocking sets, we obtain a time- and cost-optimal solution to a restricted version of the single row routing problem. The best previously known result for routing a set of n nets without street crossovers runs in O(log n loglog n) time using n processors in the CRCW model. By contrast, our algorithm runs in /spl Theta/(log n) time using n/log n processors in the CREW model, being both time- and cost-optimal.

Answering rank queries is a recurring operation in various application domains including geographic data processing, information retrieval, database design, information management, and medical image processing. Many of these applications involve data stored in a matrix satisfying a number of properties. One property that occurs time and again in applications specifies that the rows and the columns of the matrix are independently sorted. It is customary to refer to such a matrix as sorted. An instance of the Batched Ranking problem, (BR, for short) involves a sorted matrix A of items from a totally ordered universe, along with a collection Q of queries of the following type: for a query q/sub j/ one is interested in the number of items in A that are smaller than q/sub j/. The BR problem asks for solving all queries in Q. In this work, we consider the BR problem in the following context: the matrix A is pretiled, one item per processor, onto an enhanced mesh of size /spl radic/n/spl times//spl radic/n; the m queries are stored, one per processor, in the first m//spl radic/n columns of the platform. Our main contribution is twofold. First, we show that any algorithm that solves the BR problem must take at least /spl Omega/(log n+/spl radic/m) time in the worst case. Second, we show that this time lower bound is tight on meshes of size /spl radic/n/spl times//spl radic/n enhanced with multiple broadcasting, by exhibiting an algorithm solving the BR problem in O(log n+/spl radic/m) time on such a platform.

The task of computing the prefix sums of a binary sequence (BPS, for short) arises frequently in expression evaluation, data and storage compaction, routing, processor assignment, and operating system design. The main goal of this work is to propose an efficient special-purpose architecture for the BPS problem. Our design exploits a novel and elegant idea that allows us to considerably reduce the number of processors of the best-known design. The resulting design is simple and intuitive and scales easily to handle input sequences of various sizes.

The main contribution of this work is to show that a number of digital geometry problems can be solved elegantly on meshes with multiple broadcasting by using a time-optimal solution to the leftmost one problem as a basic subroutine. Consider a binary image pretiled onto a mesh with multiple broadcasting of size [Formula: see text] one pixel per processor. Our first contribution is to prove an Ω(n1/6) time lower bound for the problem of deciding whether the image contains at least one black pixel. We then obtain time lower bounds for many other digital geometry problems by reducing this fundamental problem to all the other problems of interest. Specifically, the problems that we address are: detecting whether an image contains at least one black pixel, computing the convex hull of the image, computing the diameter of an image, deciding whether a set of digital points is a digital line, computing the minimum distance between two images, deciding whether two images are linearly separable, computing the perimeter, area and width of a given image. Our second contribution is to show that the time lower bounds obtained are tight by exhibiting simple O(n1/6) time algorithms for these problems. As previously mentioned, an interesting feature of these algorithms is that they use, directly or indirectly, an algorithm for the leftmost one problem recently developed by one of the authors.

A graph G is an interval graph if there is a one-one correspondence between its vertices and a family I of intervals, such that two vertices in G are adjacent if and only if their corresponding intervals overlap. In this context, the family I of intervals is referred to as an interval model of G. Recently, a powerful architecture called the reconfigurable mesh has been proposed: in essence, a reconfigurable mesh consists of a mesh-connected architecture augmented by a dynamically reconfigurable bus system. In this paper, we exploit the reconfigurable mesh architecture for the purpose of obtaining constant-time algorithms for a number of computational problems on interval graphs. These problems include finding a maximum size independent set, a minimum clique cover, a minimum size dominating set, a shortest path between any two vertices in G, the diameter and the center of G, as well as Breadth-First Search and Depth-First Search trees for G. Specifically, with an n-vertex interval graph specified by its interval model as input, all our algorithms run in constant time on a reconfigurable mesh of size n × n. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

In this paper we introduce and investigate the notion of p-connectedness. As it turns out, this concepts leads naturally to a unique tree representation for arbitrary graphs; the leaves of this tree are the p-connected components along with weak vertices, that is, vertices of the graph that belong to no p-connected component. We then show how to refine this decomposition to obtain a new decomposition that extends the well-known modular decomposition.

Given a collection of objects in the plane along with a viewpoint /spl omega/, the visibility problem involves determining the portion of each object that is visible to an observer positioned at /spl omega/. The visibility problem is central to various application areas including computer graphics, image processing, VLSI design, and robot navigation, among many others. The main contribution of this work is to provide time-optimal solutions to this problem for several classes of objects, namely ordered line segments, disks, and iso-oriented rectangles in the plane. In addition, our visibility algorithm for line segments is at the heart of time-optimal solutions for determining, for each element in a given sequence of real numbers, the position of the nearest larger element within that sequence, triangulating a set of points in the plane, determining the visibility pairs among a set of vertical line segments, and constructing the dominance and visibility graphs of a set of iso-oriented rectangles in the plane. All the algorithms in this paper involve an input of size n and run in O(log n) time on a mesh with multiple broadcasting of size n/spl times/n. This is the first instance of time-optimal solutions for these problems on this architecture.>

We propose to enhance traditional broadcast buses by the addition of a new feature that we call shift switching. We show that on a linear array of processors enhanced with shift switching, the prefix sums of n bits can be computed in [log(n+1)/log w] broadcasts, each over n switches, assuming a global bus of width w. Next our prefix sums algorithm is used in conjunction with broadcasting on short buses to obtain several efficient architectural designs for the following fundamental problems: 1) ranking linked lists, 2) counting the number of 1's in a sequence of n bits, and 3) sorting small sets. We see our main contribution in showing that the new bus feature leads to designs that are both theoretically interesting and practically relevant.>

The Distributed Queue Dual Bus (DQDB) system consists of a linear arrangement of N nodes that communicate with each other using two contra-flowing buses. The nodes use an extremely simple protocol to send messages on these buses. This simple, but elegant, system has been found to be very challenging to analyze. We consider a simple and uniform abstraction of this model to highlight the fairness issues in terms of average waiting time. We introduce a new approximation method to analyze the performance of DQDB system in terms of the average waiting time of a node expressed as a function of its position. Our approach abstracts the intimate relationship between the load of the system and its fairness characteristics, and explains all basic behavior profiles of DQDB observed in previous simulation. For the uniform DQDB with equal distance between adjacent nodes, we show that the system operates under three basic behavior profiles and a finite number of their combinations that depend on the load of the network. Consequently, the system is not fair at any load in terms of the average waiting times. We also show that the main theme of the analysis carries over to the general (nonuniform) DQDB. By suitably choosing the inter-node distances, the DQDB can be made fair around some loads, but such system will become unfair as the load changes. In the vicinity of a critical load, the uniform network runs into a state of instability, where its behavior fluctuates from one extreme to the other with small load variations. Our analysis is supported by simulation results.>

Triangulating a set of points in the plane is a central theme in computer-aided manufacturing, robotics, CAD, VLSI design, geographic data processing, and computer graphics. Even more challenging are constrained triangulations, where a triangulation is sought in the presence of a number of constraints such as prescribed edges and/or forbidden areas. In this paper, we show that the flexibility of the reconfigurable mesh architecture can be exploited to obtain constant-time algorithms for a number of triangulation problems. These include triangulating an arbitrary set of points in the plane, a convex planar region with a convex hole, and a convex planar region in the presence of rectangular holes. Specifically, with a collection of O(n) such constraints as input, our algorithms run in O(1) time on a reconfigurable mesh of size n/spl times/n. To the best of our knowledge, these are the first constant time solutions to constrained triangulations reported on this architecture.>

The main contribution of this work is to show that a number of fundamental digital geometry tasks can be solved fast on a novel VLSI architecture obtained by augmenting the mesh with multiple broadcast architecture (MMB) with precharged 1-bit row and column buses. The new architecture that we call mesh with hybrid buses (MHB) is readily implementable in VLSI with no increase in the area or the wiring complexity of the MMB chip. More importantly, the new architecture affords us an exponential gain in the running time when compared with the MMB. Specifically, with a digital image pretiled onto an MHB of size /spl radic/n/spl times//spl radic/n one pixel per processor we show that the problems of computing the convex hull of the image, computing the diameter and the width of the image, deciding whether two images are linearly separable, computing several moments and low-level descriptors of the image including the perimeter, area, center, and median row of its convex hull can be solved in O(log n) time. The fastest possible algorithms for the problems above on the MMB run in /spl Theta/(n/sup 1/6/).>

Consider arbitrary collections A = a_1,a_2,.. .,a_n of items and Q = q_1,q_2,...,q_m (1 leqslant mn leqslant n) of queries from a totally ordered universe. The multiple rank problem involves computing for every query qi the number of items in A that have a lesser value. Our contribution is to show that the problem at hand can be solved time-optimally on meshes with multiple broadcasting. More specifically, if the collection A is siored in some order one item per processor and if Q is stored one query per processor in the leftmost frac{m} {{sqrt n }} columns of a mesh with multiple broadcasting of size sqrt n x /sqrt n, the corresponding instance of the multiple rank problem can be solved in Theta left( {m^{frac{1} {3}} n^{frac{1} {6}} } right) time. As an application we present a time-optimal algorithm to compute the histogram of a m-level gray image of size sqrt n x sqrt n in Theta left( {m^{frac{1} {3}} n^{frac{1} {6}} } right) time.

Recently the authors have shown that the versatility of the reconfigurable mesh can be exploited to devise 0(1) time algorithms for a number of important computational tasks relevant to image processing, computer graphics, and computer vision. Specifically, we have shown that if one or two n-vertex (convex) polygons are pretiled, one vertex per processor, onto a reconfigurable mesh of size sqrt n X sqrt n, then a number of geometric problems can be solved in 0(1) time. These include testing an arbitrary polygon for convexity, the point location problem, the supporting lines problem, the stabbing problem, constructing the common tangents of two separable convex polygons, deciding whether two convex polygons intersect, and computing the smallest distance between the boundaries of two convex polygons. The novelty of these algorithms is that the problems are solved in the dense case. The purpose of this paper is to add to the list of problems that can be solved in 0(1) time in the dense case. The problems that we address are: determining the minimum area corner triangle for a convex polygon, determining the k-maximal vertices of a restricted class of convex polygons, updating the convex hull of a convex polygon in the presence of a set of query points, and determining a point that belongs to exactly one of two given convex polygons.

Considers a simple and uniform abstraction of the distributed queue dual bus (DQDB) system of N nodes to highlight the fairness issues in terms of average waiting time. For the uniform DQDB with equal distance between adjacent nodes, the authors show that the system operates under three basic behavior profiles and a finite number of their combinations that depend on the load of the network. Consequently, the system is not fair at any load in terms of the average waiting times. In the vicinity of a critical load of 1-4/N the uniform network runs into a state akin to chaos, where its behavior fluctuates from one extreme to the other with a load variation of 2/N. The analysis is supported by simulation results. The authors also show that the main theme of the analysis carries over to the general (non-uniform) DQDB.>

Due to its attractive topological properties, the hypercube multiprocessor has emerged as one of the architectures of choice when it comes to implementing a large number of computational problems. In many such applications, Gray-code labelings of the hypercube are a crucial prerequisite for obtaining efficient algorithms. We propose a greedy algorithm that, given an n-dimensional hypercube H with N=22 nodes, returns a Gray-code labeling of H, that is, a labeling of the nodes with binary strings of length n such that two nodes are neighbors in the hypercube if, and only if, their labels differ in exactly one bit. Our algorithm is conceptually very simple and runs in O(N log N) time being, therefore, optimal. As it turns out, with a few modifications our labeling algorithm can be used to recognize hypercubes as well.

One of the fundamental algorithmic problems in computer science involves selecting the kth smallest element in a collection A of n elements. We propose an algorithm design methodology to solve the selection problem on meshes with multiple broadcasting. Our methodology leads to a selection algorithm that runs in O(n/sup 1/8/(log n)/sup 3/4/)) time on a mesh with multiple broadcasting of size n/sup 3/8/(log n)/sup 1/4//spl times/n/sup 5/8//(log n)/sup 1/4/. This result is optimal over a large class of selection algorithms. Our result shows that just as for semigroup computations, selection can be done faster on suitably chosen rectangular meshes than on square meshes.>

The compaction step of integrated circuit design motivates the study of various visibility problems among vertical segments in the plane. One popular variant is referred to as the Vertical Segment Visibility problem (VSV, for short) and is stated as follows. Given a collection S of n disjoint vertical line segments in the plane, for every endpoint of a segment in S determine the first line segment, if any, interacted by a horizontal ray to the right (resp. left) originating from that endpoint. The contribution of this paper is to propose a time-optimal algorithm for the VSP problem on meshes with multiple broadcasting. The authors then use this algorithm to derive time-optimal solutions for two related problems. All the algorithms run in O(log n) time on a mesh with multiple broadcasting of size n /spl times/ n. This is the first instance of time-optimal solutions for these problems known to us.>

The authors propose a novel VLSI sorting network implementing Leighton's column sort. The network is mech-based and modular; it consists of comparison-exchange processing elements (PEs), routing paths, and short broadcast buses. Each bus contains a small number of simple switches that the authors call shift switches. They enhance and simplify the previously proposed shift switching mechanism to obtain an efficient O(1) VLSI-optimal sorting algorithm. From a theoretical perspective, the new approach reduces significantly both the number of PEs (from N/sup 2/ to N/sup 13/9/) and the number of broadcasts from more than 58 bus broadcasts, each over N switches, to at most 16 bus broadcasts, each over N/sup 4/9/ switches. From a practical standpoint, the network features a significant time-performance gain in comparison with the bitonic sorting circuit, especially when multiple smaller size arrays are sorted in parallel.>

Recently it has been noticed that for semigroup computations and for selection, rectangular meshes with multiple broadcasting yield faster algorithms than their square counterparts. The contribution of this paper is to provide yet another example of a fundamental problem for which this phenomenon occurs.

In this work, we present a time-and VLSI-optimal sorting algorithm for meshes with multiple broadcasting. Specifically, we show that for every choice of a positive integer constant c, m items \left( {n^{\frac{1} {2} + \frac{1} {{2c}}} \leqslant m \leqslant n} \right) stored in the first \left\lceil {\frac{m} {{\sqrt n }}} \right\rceil columns of a mesh with multiple broadcasting of size \sqrt {n} x \sqrt {n} can be sorted in O({\frac{m} {{\sqrt n }}}) time.

Interval graphs provide a natural model for a vast number of scheduling and VLSI problems. A variety of interval graph problems have been solved on the PRAM family. Recently, a powerful architecture called the reconfigurable mesh has been proposed: in essence, a reconfigurable mesh consists of a mesh-connected architecture augmented by a dynamically reconfigurable bus system. It has been argued that the regular structure of the reconfigurable mesh is suitable for VLSI implementation. The authors develop a set of tools and show how they can be used to devise constant time algorithms to solve a number of interval-related problem on reconfigurable meshes. These problems include finding a maximum independent set, a minimum clique cover, a minimum dominating set, a minimum coloring, along with algorithms to compute the shortest path between a pair of intervals and, based on the shortest path, an algorithm to find the center of an interval graph. More precisely, with an arbitrary family of n intervals as input, all their algorithms run in constant time on a reconfigurable mesh of size n*n.>

0(r) is the state occupied at time '/*, and m and , are any two states with transition probabilities Prob [ m ) and P*U> n ), the equilibrium probabilities of being in m and n respectively, obey: P*(*J/P*(*J = <7» m/ for all m, n. (Now the transition from (R ( ,R, ,...,R,,R t , ...,^v)to(/?(i ,7? v . . ., * w A (j , '..,R,Joccurs whenever # , is accessed from the left or R ( is accessed from the right.Similarly, the transition from (R( ,R( ,...,Rj ,Rt,...,Rt) to (R,,R.,...,Rt,R\ ,'..,R.)'occurs whenever /?, is accessed from the right

A graph G is $P_4 $-sparse if no set of five vertices in G induces more than one chordless path of length three. $P_4 $-sparse graphs generalize both the class of cographs and the class of $P_4 $-reducible graphs. One remarkable feature of $P_4 $-sparse graphs is that they admit a tree representation unique up to isomorphism. It has been shown that this tree representation can be obtained in polynomial time. This paper gives a linear time algorithm to recognize $P_4 $-sparse graphs and shows how the data structures returned by the recognition algorithm can be used to construct the corresponding tree representation in linear time.

A family of intervals on the real line provides a natural model for a vast number of scheduling and VLSI problems. Recently, a number of parallel algorithms to solve a variety of practical problems on such a family of intervals have been proposed in the literature. The authors develop computational tools and show how they can be used for the purpose of devising cost-optimal parallel algorithms for a number of interval-related problems, including finding a largest subset of pairwise nonoverlapping intervals, a minimum dominating subset of intervals, along with algorithms to compute the shortest path between a pair of intervals and, based on the shortest path, a parallel algorithm to find the center of the family of intervals. More precisely, with an arbitrary family of n intervals as input, all the algorithms run in O(log n) time using O(n) processors in the EREW-PRAM model of computation.>

An implementation of a double-ended priority queue is discussed. This data structure referred to as min–max–pair heap can be built in linear time; the operations Delete-min, Delete-max and Insert take O(log n) time, while Find-min and Find-max run in O(1) time. In contrast to the min-max heaps, it is shown that two min–max–pair heaps can be merged in sublinear time. More precisely, two min–max–pair heaps of sizes n and k can be merged in time O(log (n/k) * log k).

An adaptive parallel algorithm for inducing a priority queue structure on an n-element array is presented. The algorithm is extended to provide optimal parallel construction algorithms for three other heap-like structures useful in implementing double-ended priority queues, namely min-max heaps, deeps, and min-max-pair heaps. It is shown that an n-element array can be made into a heap, a deap, a min-max heap, or a min-max-pair heap in O(log n+(n/p)) time using no more than n/log n processors, in the exclusive-read-exclusive-write parallel random-access machine model.>