Intelligence and sustainability are two essential drivers for the development of current and future Intelligent Transportation Systems. On one hand, the complexity of vehicular ecosystems and the inherently risk-prone circumstances under which pedestrian and vehicles coexist call for the endowment of intelligent functionalities in almost all systems and processes participating in such ecosystems. On the other hand, risk may be the most important objective to be guaranteed by the provision of intelligence in ITS, but it is not certainly the only one: when safety is assured, sustainability comes into play, seeking to convey intelligence to the distinct parts composing the ITS landscape with efficiency, minimum carbon footprint, wastage of resources or any other factor affected by the technological empowerment itself.

Mobile Edge Computing (MEC) has been in the forefront recently for its ability to supplement cloud computing. MEC servers are deployed closer to the users at the network edge in order to reduce the latency and computation load on the cloud. Edge caching plays a dominant role in the MEC paradigm. Popular content is cached in the MEC nodes thereby reducing user access latencies. However, the cache capacity of MEC nodes are limited and therefore efficient caching mechanisms are required to make optimum utilization of MEC node caches. In this work we propose a novel, scalable, hierarchical size and access frequency aware caching policy for mobile edge computing. Our experiments show that the policy outperforms traditional caching policies at the cloud and is scalable with the next generation of workloads in MEC environments.

The papers in this special issue mainly focus on deep learning models for industry informatics, addressing both original algorithmic development and new applications of deep learning.

In vehicular networks, Roadside Units (RSUs) handle Vehicle-to-Infrastructure communications and are essential to overall network functionality. A successful deployment strategy for RSUs must consider both the network coverage and the cost of deployment. In this work, we propose a technique for selecting contextually significant locations for RSU deployment. In our scheme, we consider the underlying context of candidate locations in determining their possible candidacy for RSU deployment. To understand the context of a given area, we analyze passively collected GPS data from smart phones to determine what type activity is most common in a given area. With this technique, we can identify areas that are regularly visited by commuters. We then examine the intersection usage statistics in the area and select only the most frequently used intersections locations for RSU deployment. By targeting specific locations based on their context and reducing the set of candidate intersections, we can reduce the number of RSUs required to cover an area, thus reducing the overall cost of the RSU network.

Existence of several application specific network technologies like Sensor Networks, Cloud, Personal Area Networks (WPANs), Vehicular Networks (VANETs), Content Delivery Networks and Wifi operating oblivious to each other in the same ISM band creates numerous problems like contention for the same bandwidth leading to excessive collisions and hence lower throughput. This calls for a hybrid mesh framework that is capable of supporting heterogeneous devices in an IoT paradigm. This work proposes exactly that kind of environment.There are several benefits of deploying a hybrid mesh to bridge numerous types of networks and devices, like availability of more data and in some cases, redundant data leads to high reliability. Further, Co-operative interoperability assures higher throughput and efficiency. In case of universal rich data availability, accurate and situation aware decision modeling is achieved. For example, In case of a vehicular network, accurate driving decisions can be made. Additionally, Higher and reliable data availability leads to detailed knowledge and perception which can be further exploited to ensure high level of Security in the network.

Connectivity in vehicular networks is continuously changing due to high mobility of vehicles, causing rapid changes in the network topology. This has a direct negative impact on the throughput and packet transmission delay. Many algorithms and approaches have been proposed to address this problem. However, most of them are not practical due to their dependence on a centralized infrastructure, which are attributed with high cost for installation and maintenance. Vehicular networks are composed of all types of vehicles including autonomous and nonautonomous vehicles. In this paper, we propose addressing the problem of VANET connectivity through controlling the routes and speed of autonomous vehicles according to the density and speed of non-autonomous vehicles. This is achieved through a decentralized cooperative game theory approach that provides a balance between autonomous vehicles' trip duration, and enhancements to the VANET connectivity. We evaluate our proposed approach through extensive simulations using real traffic data, and observe substantial enhancements of up to 46% in the network connectivity using our approach.

Recent research in the performance of public key algorithms, such as Elliptic Curve Cryptography (ECC), have illustrated upon their practical applicability in sensor networks. With this research, we are proposing an optimization to one of the most critical operations in Public Key Cryptography (PKC)-authentication of the public key. Here, we provide a framework that proposes a resource-efficient, lightweight and scalable key management scheme for the network under consideration. The proposed scheme uses a one-way hash function to construct a hash tree (Merkle Tree) as an alternative to traditional public key authentication techniques. Security and privacy are two foundational pillars in the design of electronic health systems, with users demanding high confidentiality of their personal data. Without the right infrastructure it is difficult to secure the ecosystem of wearable devices. We envision that by harnessing the performance capabilities of traditional symmetric-key algorithms coupled with the inherent benefits of the PKC architecture, the proposed scheme will provide a more robust and efficient security solution for e-Health driven applications.

In this paper, we exploit the capture-effect for channel allocation. We experimentally show the characteristics of capture-effect across different channels, over time, and in different network densities. Then, we introduce CACA, an effective channel assignment protocol for wireless sensor networks. Traditional channel assignment protocols utilize all available channels to minimize interferences between any adjacent links. However, their performances are often not much better than the case of using single channel only. This is mainly due to an assumption that all channels are independent and quality of all channels are similar. However, this is a false assumption. In fact, there are only a few channels that show very good quality at any given time. The CACA avoids this problem by utilizing a few good channels and reuse these channels. When the channels are reused it relies on the capture-effect to ensure at least one of the contending nodes to transmit successfully. Maximizing this capture probability is a main objective of the CACA whenever the channels need to be reused. We evaluate the CACA on a 140-node wireless sensor network testbed and compare its performance with another benchmark protocol. Our results indicate that the CACA can improve the packet reception ratio of every link. As a result of this improvement, end-to-end throughput increases upto 100% in the case of a wireless sensor network with bursty traffic.

Fog computing is a recently proposed computing paradigm that extends Cloud computing and services to the edge of the network. The new features offered by fog computing (e.g., distributed analytics and edge intelligence), if successfully applied for time-sensitive healthcare applications, has great potential to accelerate the discovery of early notification of emergency situations to support smart decision making. While promising, how to design and develop real-world fog computing-based data monitoring system is still an open question. As a first step to answer this question, in this research, we employ a fog-based cloud paradigm for time-sensitive medical applications and also propose to show the practical applicability and significance of such a novel system. The ubiquitous deployment of mobile and sensor devices is creating a new environment, namely the Internet of Things (IoT) that enables a wide range of future Internet applications. In this work, we present dynamic Fog, a high level programming model for time-sensitive applications that are geospatially distributed, large–scale, and latency–sensitive. We also analyze our fog model with healthcare data, more specifically with Heartrate data that is one of the most time-sensitive medical data which deals with life and death situations. Our experiments show that our proposed system achieves minimum delay while it also achieves the data accuracy and data consistency which are very important in many applications like medical data.

In previous decades, there has been a significant paradigm shift in the domain of computer architecture and processing mechanisms of large-scale data due to the increase of computational power caused by an overwhelming flow of massive amount of data. Hadoop and MapReduce are very powerful concepts which enable the efficient development of scalable and parallel applications required for processing vast amounts of data. In this paper, we investigate the concept of Hadoop and MapReduce and eventually use the programming tool of MapReduce and Apache Pig to solve existing computation problems of very complex and complicated Google Ngrams datasets.

Wireless Body Area Networks (WBANs) have the potential for extensive use in health care monitoring. To provide optimum network utilization, it is important to efficiently schedule multiple co-existing WBANs which could possibly suffer from high degree of interference. A graceful coexistence can be feasible by appropriately scheduling transmissions from different WBANs. In this paper, we use a recent standard of IEEE 802.15.6 (TG6), which has been finalized in May 2012, to address the problems of intra and inter-WBAN interference. This standard offers several advantages for medical applications as compared to IEEE 802.15.4 which has been previously adopted for numerous healthcare applications. In this paper, we propose a QoS based MAC scheduling approach to avoid inter-WBAN interference and introduce a fuzzy inference engine for intra-WBAN scheduling so as to avoid interference within WBANs.

Wireless Body area networks comprise of sensor nodes attached on or implanted inside the human body and promise large improvements in patients health monitoring. However, the heat generated by the sensor nodes circuitry can cause damage to the tissues in the human body. Therefore, in an attempt to reduce the heat generated, efficient sleep cycles and temperature-aware routing for the sensor nodes should be established. In this paper, we present a probabilistic sleep cycle management and a temperature aware data-packet routing algorithm.

Wireless Sensor Networks (WSNs) have been primarily introduced for defense application, with an objective of monitoring enemy's activities without any human intervention, using a large number of wireless sensor nodes (SNs) and a Base Station (BS) or a sink to collect information from all SNs. In recent years, advances in miniaturization, low-power circuit design, improved low cost, and small-size batteries have made it possible for monitoring physical parameters such as temperature, pressure, velocity, acceleration, stress and strain, fatigue, tilt, light intensity, sound, humidity, gas-sensors, biological, pollution, impurity level detection, nuclear radiation, civil structural sensors, blood pressure, sugar level, white cell count, and many others. The magic of WSNs is also expanded to Wireless Body Area Sensor Network (WBASN) as applied to human health. We introduce an interesting application of WBASN in the field of Sports Medicine by monitoring postural balance and stability of athletes in real time and providing valuable feedback to the coaches so as to minimize athletes' injury and maximize their playing potential. We also consider a fascinating application of continuous, non-invasive wireless home monitoring of patients with movement disorders and Parkinson's disease. We discuss an effective home based monitoring system that could monitor patients in their homes. Final comments are added to provide glimpse of what WSNs can do in numerous areas

The number of hops from Mesh Routers (MRs) to an Internet gateway (IGW) plays an important role in determining the performance of a wireless mesh network (WMN). A recent patent has introduced a mechanism of using an existing femtocell (FC) as an additional potential IGW so that the performance of a WMN could be enhanced. Such an integration of WMN with FCs enables an increase in WMN's overall capacity. But, due to FCs' unpredictable operating times and uninformed disconnections, MRs require reliable and efficient schedule for switching between available FCs which has not been analyzed in the patent. The switching can be done in a push based preemptive or a pull based non-preemptive manner. In this paper, we formulate both these switching schemes for a WMN-FC integrated network as approximate statistical models based on a Markovian process. We also determine a switching schedule of FCs for each of MR based on reliable uncapacitated facility location (RUFL) problem. We extend an existing RUFL problem to incorporate dynamic operating nature of multiple FCs which display dynamic available/unavailable patterns for additional potential IGWs. Extensive simulations are carried out to validate our proposed statistical models and establish the performance of these switching schemes.

The locality of reference is a well studied phenomenon in computer systems. As one special case, the network locality has been demonstrated to exist in the wired local area networks. Previous research suggests that the network traffic does not follow uniform distribution. In this paper, we explore the network locality in the wireless networks. We take a close look at wireless traces from wireless local area networks (WLANs) and wireless mesh network simulations with different routing protocols to analyze various network locality characteristics. We also measure a new network locality characteristic to explore the possible use of such property in the network coding. Our experiment validates the prevailing existence of network locality in wireless networks and shows how these network locality characteristics are different from those in the wired networks.

Remote monitoring of patients with movement disorders is currently being researched extensively with the help of Wireless Body Area Sensor Network (WBASN). e-Healthcare is one such popular WBASN application. We focus our research addressing an important issue of wireless monitoring of patients suffering from Parkinson's Disease (PD) for fall detection in order to avoid potential injuries. We also propose a non-invasive, wireless technique that could detect multiple occurrences of Freezing of Gait (FoG) over single or multiple days of observation. For wireless monitoring of patients, we would embed wireless sensors in patient's vicinity, such as his room and determine the values of Received Signal Strength Indicator (RSSI) from these sensors. RSSI can thus be used as one of the measures to detect falls of PD patients. Our initial results of embedding force sensors in person's shoe, suggest that it can be used to detect and record the number of occurrences of FoG, which is hard to reproduce at doctor's clinic, due to its relation with patient's consciousness at the hospital. We also propose to derive different mobility patterns for a PD patient based on the RSSI values during a day's activity and then train the system for intelligent analysis in future.

Femtocell (FC) is a low-power, low cost indoor cellular base station (BS) installed by an end user at home or in an office environment. A typical indoor coverage of an FC is tens of meters and could cover several rooms. When Femto base stations (F-BS) are densely deployed, interference between them becomes an unavoidable issue. Hence, there is an immediate need for a robust interference management technique before femtocells can be extensively adopted for commercial purpose. In this paper, we propose a distributed algorithm that takes into account dynamic topology of FCs and carefully allocates communication channels to each F-BS. This also addresses the co-domain interference problem in FCs. We perform extensive simulations to demonstrate the novelty of our proposed scheme, called as distributed topology-based spectrum allocation. This avoids spectrum overlap that facilitates efficient resource allocation for each cell, thereby enabling low interference under high resource utilization and increased reuse efficiency.

Recently, Wireless Sensor Networks (WSNs) are spread all over the world, and are commonly used to collect physical information from the surrounding world. WSNs play a central role in the Internet of Things (IoT) vision. IoT is a new paradigm that aims to integrate and connect anything at anytime, anyplace, with anything and by anyone. However, addressing objects is the main challenge for IoT. IPv6 over Low power Wireless Personal Area Networks (6LoWPAN) has been introduced to cope with this issue. The emerging paradigm Social web of thing (SWoT) enables users to manage, access, share, and integrate smart objects with Social Network Site (SNS). This paper investigates different SWoT platforms and architectures, provides an overview of the current state-of-the-art on WSN communication standards.

Wireless technologies employing small sensors are particularly useful since they allow monitoring of kinetic and physiological data without affecting any individual in motion. The primary objective of this collaborative research between the Department of Electrical Engineering and Computing Sciences and the Department of Athletes at the University of Cincinnati is to build a wireless system using a wireless body area sensor network (WBASN) for the overhead squat in assessing one element of human movement and its relationship to the kinematic lower extremity movement and injuries. This research can provide an objective analysis of the pilot data for movement of the human body during regular athletic exercises.

Network coding has been shown to improve the performance of the multi-hop wireless networks, by taking advantage of the "mix and broadcast" style communication. In this work, we explore coding-aware routing to further improve end-to-end throughput in the multi-hop wireless networks. A heuristic routing metric ETOX and a novel routing framework HyCare are proposed to route the packets when inter-session network coding protocol is incorporated. Using Network Locality as a heuristic, ETOX homogenizes coding opportunities with other measurements into routes selection. Different from previous attempts on such kind of design, e.g., ERC, ETOX is an unconditional link metric that can be used in many existing routing protocols. It is included in our proposed hybrid routing framework HyCare, which possesses both link-state routing and reverse forwarding functionality. While HyCare can work as an independent routing protocol, it can also collaborate with underlying network coding protocol so as to acquire more accurate ETOX values. Extensive performance evaluation shows significant enhancement for different settings, thereby validating our design methodology.

A novel channel detection timing scheme for periodic sensing is proposed to minimize the sensing cost of the secondary users while protecting the transmission of the primary users. The framework consists of a Cognitive Radio Network where secondary users operate in a periodic fashion while the primary users operate in continuous-time. The scheme has been presented for both non-erroneous and erroneous channel sensing conditions. Numerical results show the effectiveness of our scheme for erroneous sensing conditions when compared to non-erroneous sensing conditions.

Due to the requirement for extensive coverage, Long Term Evolution (LTE) has developed small cellular base stations called femtocells that can dramatically improve voice and data coverage for the indoor subscribers. However, limited spectrum availability in the cellular networks causes severe interference issues in the neighboring femtocell users transmitting in the same radio band. In densely deployed environments, interference problems in co-channel femtocell networks causes significant degradation in performance. In this paper, we propose a Cluster-Aware Soft Frequency Reuse (CASFR) scheme, that assigns distinct set of Physical Resource Blocks (PRB)s to each interfering femtocells. The scheme first uses periodic messages from the femto-user (FUE) to identify the interfering femtocells. It then divides each femtocell area into cell-center and cell-edge. Finally, it uses the CASFR algorithm to assign un-interfering sets of PRBs to the cell-center and cell-edge users of all the interfering femtocells. We also proposed a PRB Swapping and Exchange (PSE) algorithm for the uplink to further reduce any interference that may remain after performing CASFR. The simulation results show 14% decrease in the Inter Cell Interference (ICI) levels in the femto users, thereby increasing their average throughput by 25%.

Numerous solutions have been proposed to improve the efficiency of wireless sensor networks (WSNs). Data aggregation, which reduces the data redundancy so as to mitigate energy consumption, is one of desirable solutions. One common feature of geographically close-by data known as spatial correlation, has been utilized for eliminating redundant information. To reduce redundancy and enhance eventual performance, we explore the possibility of combining sensing data with similar characteristics without considering spatial information.We define this relationship of data as characteristic correlation and propose an automatic procedure to discover characteristic correlation between sensor nodes (SNs) with limited overheads. Furthermore, we introduce a novel characteristic correlation based data aggregation approach that allows any SN to compress unlimited number of packets into virtual packets up to a constant number. With experimental and simulation results, our proposed approach is illustrated as an effective data aggregation method in term of data accuracy.

In conventional Wireless Mesh Networks (WMNs), multihop relays are performed in the backbone comprising of interconnected Mesh Routers (MRs) and this causes capacity degradation. This paper proposes a hybrid WMN architecture that the backbone is able to utilize random connections to Access Points (APs) of Wireless Local Area Network (WLAN). In such a proposed hierarchal architecture, capacity enhancement can be achieved by letting the traffic take advantage of the wired connections through APs. Theoretical analysis has been conducted for the asymptotic capacity of three-tier hybrid WMN, where per-MR capacity in the backbone is first derived and per-MC capacity is then obtained. Besides related to the number of MR cells as a conventional WMN, the analytical results reveal that the asymptotic capacity of a hybrid WMN is also strongly affected by the number of cells having AP connections, the ratio of access link bandwidth to backbone link bandwidth, etc. Appropriate configuration of the network can drastically improve the network capacity in our proposed network architecture. It also shows that the traffic balance among the MRs with AP access is very important to have a tighter asymptotic capacity bound. The results and conclusions justify the perspective of having such a hybrid WMN utilizing widely deployed WLANs.

In a Wireless Sensor Network (WSN), intrusion detection is of significant importance in many applications in detecting malicious or unexpected intruder(s). The intruder can be an enemy in a battlefield, or a malicious moving object in the area of interest. With uniform sensor deployment, the detection probability is the same for any point in a WSN. However, some applications may require different degrees of detection probability at different locations. For example, an intrusion detection application may need improved detection probability around important entities. Gaussian-distributed WSNs can provide differentiated detection capabilities at different locations but related work is limited. This paper analyzes the problem of intrusion detection in a Gaussian-distributed WSN by characterizing the detection probability with respect to the application requirements and the network parameters under both single-sensing detection and multiple-sensing detection scenarios. Effects of different network parameters on the detection probability are examined in detail. Furthermore, performance of Gaussian-distributed WSNs is compared with uniformly distributed WSNs. This work allows us to analytically formulate detection probability in a random WSN and provides guidelines in selecting an appropriate deployment strategy and determining critical network parameters.

Wireless Mesh Networks (WMNs) have generated a lot of enthusiasm over the last decade or so, both in research and implementations. However, they are yet to reach their full potential and deliver on the promise of ubiquitous high-speed Internet access, due to a number of real world limitations. As such, the current research focus is shifting towards understanding the ground realities of building a high-performing WMN and finding solutions to any shortcomings. The success of these attempts has the potential to propel the popularity of WMNs to a whole new level. However, with increasing popularity, energy efficiency also becomes a major consideration for WMN design, not only to facilitate power-constrained usages, but also to be proactive in energy conservation as a whole. The existing research in WMNs considers energy-efficiency as an after-thought at best, especially since existing criteria and metrics are not being designed with energy-efficiency in mind. In this paper, we present a new energy-aware link quality metric that could be used at the initial configuration of a WMN to increase the average throughput, while reducing the power consumption. We validate our design strategy with a detailed measurement study performed on a mesh network testbed. We show that in addition to increasing the throughput and reducing the power consumption, we can increase the connectivity of the network by using this link quality metric.

The visual sensing capability of a Visual Sensor Network (VSN) makes it a very effective tool for applications such as large scale surveillance, environmental monitoring and object tracking. The image sensing, processing and storing functions of the VSN, combined with its function of transmitting and forwarding data towards the sink, consumes more energy and increases the well known energy-hole problem in the network. In this paper, we propose to deploy a Gaussian distributed relay network over pre existing uniform random VSN so as to avoid the energy-hole problem. By forming a heterogeneous wireless sensor network with low-cost relay nodes (RNs), lifetime of the VSN is prolonged with minimal additional cost. We use the energy model of image compression enabled VSNs and determine optimal parameters for the Gaussian deployment of the relay network.

In this paper, we introduce a new framework for network coding in a multi-radio multi-channel wireless mesh network. Our proposed protocol called Murco, is the first practical work in this area that embraces a distributed solution of network coding in a multi-radio multi-channel network. Murco has been fully implemented and evaluated as a high performance mesh backbone. Experiments indicate very promising results not just on throughput, but also on end-to-end delay. Murco does not depend on any special channel assignment algorithm or routing protocol. Therefore, it offers a total compatibility with existing technologies.

Vehicular Ad hoc Networks (VANETs) are emerging as the first commercial implementation of mobile ad hoc networks. There has been a significant rise in the use of secure group communication as a result of the growth in the applications that require confidentiality and authorized access to multicast data. Numerous Group Key Management (GKM) schemes have been proposed to meet the security and QoS requirements. The highly dynamic nature of VANETs can cause significant overhead in the form of re-keying communication, if these existing GKMs are to be used. Hence, we identify the need for new solutions specific to VANETs and introduce a multivariable symmetric polynomial based GKM which eliminates the need for the re-distribution of keys upto a configurable number of membership changes, without compromising the forward or the backward secrecy. Furthermore, our scheme reduces the effect of mobility on the re-keying overhead by allowing vehicles to handoff between road side units (RSUs) within the group without re-keying.

To ensure the uninterrupted usage in a Wireless Sensor Network (WSN), it is important to preserve the location privacy of sensor nodes. In this paper, we propose a novel technique of protecting the location privacy of the base station in a WSN. Many techniques have been proposed to protect the source in WSNs and relatively fewer techniques exist to protect the base station. Our technique, which we call BLAST is aimed at protecting the base station from both Packet Tracing and Traffic Analysis attacks with equal importance to the delay and energy consumption. It also provides reasonable privacy against a Global attacker. The core idea is to vary the transmission range of a set of selected sensors around the base to confuse the attacker. Through this technique, we are able to create a set of fake base stations which cannot be identified even by a strong Global attacker who can hear all the transmissions.

In this paper, we consider scenarios where traditional methods of sensor deployment do not perform well with regard to intrusion detection at the boundary of an area under protection. We propose a Hybrid Gaussian-Ring Deployment that provides a higher intrusion detection probability with fewer nodes for attacks at the edge of the network. This reduces the distance, that an external intruder can traverse before being detected. We provide the network deployment parameters to suit the desired level of security for a given Wireless Sensor Network application.

In this paper, we explore two specific Wireless Sensor Network applications of environmental monitoring and motion capturing, where the traditional methods of energy-balanced data propagation are not ideally suited. These solutions are either too generic to exploit the specific characteristic of our application or are too complex to be implemented for simplistic requirements of our application. We propose and analyse a simple, energy efficient and energy balanced algorithm for the propagation of data in our specific application which can be used in other Wireless Sensor Networks with similar characteristics and requirements. We first model our problem using Integer Programming to find an optimal solution which is NP hard to solve. Subsequently, we also provide a heuristic solution that prolongs the lifetime of our network to near the optimal value.

Intrusion detection is one of many typical applications for wireless sensor networks (WSNs). A WSN for intrusion detection application is capable of detecting any physical existence of external intruder invading an area under protection and alert the system for appropriate actions. Traditional deployment schemes for intrusion detection usually consider detection probability of having separate facilities within the monitored area. In this work, we assume that the scenario includes multiple facilities. A Reverse Gaussian distribution is derived from two dimensional Gaussian distribution and sensors are deployed following a Reverse Gaussian distribution. By placing a larger number of sensor nodes at the border, the detection probability is enhanced. As intrusion attacks start from border area, Reverse Gaussian deployment scheme can provide a better security performance with the same amount of investment as compared to traditional deployment schemes, and is validated by extensive simulation results.

Integration of various wireless access technologies have pushed the evolution of mobile clients (MC) to be equipped with multiple interfaces for simultaneously accessing different network technologies. In these heterogeneous wireless networks (HWNs), MCs (and the underlying network) must be able to quickly and dynamically adapt to varying network conditions so as to satisfy required communication constraints. However, unlike their machine counterparts, MCs tend to have very vague and uncertain demands. This paper focuses on imprecise and dynamic nature of the MC's demands, while fulfilling multiple - often contradicting - constraints. The problem of uncertain decision making is considered by utilizing techniques from the multiple criteria decision making area. At each MC, an enhanced minimization of maximal regret (MMR) ranks available network interfaces and this maps imprecise user constraints to ranked interfaces.

The received signal strength indicator (RSSI) and the link quality indicator (LQI) are metrics that are commonly available in commercial off-the-shelf (COTS) sensor hardware. The former has been widely regarded as a cheap alternative for distance estimation and node localization. However, experimentally RSSI has been shown to behave in an inconsistent manner, even in ideal scenarios, and serve at best as bounds for distances. The latter is effectively a measure of chip error rate, and can be used to identify higher quality transmissions, and the combination RSSI/LQI can be expected to make more precise estimates with the tradeoff of increased delay and estimation cost. In this paper, we describe our distance estimation system that uses these two metrics and test our hypothesis purely through experimental measurements using sensor nodes. Results indicate that such a combination of metrics can be used to provide a tighter bound on the range of estimated distances.

This demo will demonstrate implementation of a secured EMR (Electronic Medical Record) system that can be used by Physicians, Nurses, Patient Care Technician and Dietician in a Dialysis Center setting. Although substantial work has been done for applications using a desktop browser, only few operations have been implemented on mobile devices. The line between the native and web application development does not have to be crystal clear and there could be a third model which is gradually evolving in creating a hybrid application that could combine strengths of both the native and web technology. The EMR set up consisting of an iPod, an iPhone and a desktop browser and shown in Figure 1, provides a workflow for a patient coming for a dialysis treatment, accounts for Patient Demographics, track orders written by Physicians, keep current intake of medications and sends notifications to Physicians and Nurses on record updates. All modules have numerous functions such as add, edit and view. We show the user's login following patient's demographics screen in Figure 2 and Figure 3 respectively. The top-level menu items consist of Patient, Search and E-sign modules. Figure 3 shows the “Add Patient” option from the menu. Once the patient is served, the user can search for a specific patient and get an extended menu items as shown in Figure 4. These menu items include editing a patient, add/edit physician's and standing orders, add/edit home and in-center medications. Once the patient extended information has been saved, the patient is ready for a dialysis treatment. A complete workflow for the treatment is captured with the workflow module as illustrated in Figure 5.

There are many ways to determine the boundary of an event based on Satellite imaging which does not provide accurate information. In many situations, there may not be enough time to monitor the effect of emergency and the affected area. Moreover, the event region could continuously change in the geographical region and a robust deployment of sensors is desirable that could capture maximum information about the entire event as soon as possible and continue capturing information without a break. These events are not physically accessible and most of the sensor deployments are static to check if they can fully cover an event. We explore these issues in this work and look at dynamic sensor network deployment strategies.

Femtocells are capable of providing services in shadowed areas of the WiMAX macrocell (cell coverage enhancement) and can relieve traffic from the macrocell networks, reduce infrastructure costs for the network operators, allow for network capacity increase, and provide needed service quality in an indoor environment. However, conventional handover methods cannot support a good enough performance under different mobility patterns and dynamic network conditions. This work introduces an appropriate call admission control and proposes a resource management scheme that significantly reduces unnecessary handovers. Simulation results are shown to validate our performance predictions.

With the constant evolution of wireless communication access technologies, there is a clear trend for mobile clients (MC) to be equipped with multiple interfaces for simultaneous access to different types of networks. This has been denominated a heterogeneous wireless networks. However, in order to achieve a desired quality of service while satisfying the user's requirements, MCs must take advantage of the inherent characteristics of these access technologies, and rely on adaptable decision making mechanism for data forwarding. Unfortunately, route selection satisfying multiple constraints has proven to be NP-Complete, and although various heuristic algorithms have been proposed, they assume that the network state information is static and both the user's and networks constraints are clearly specified. This paper focuses on the imprecise and dynamic nature of the network conditions while satisfying multiple - often contradicting - constraints. A fuzzy logic model is proposed which aims at translating the uncertainty factor of the network conditions to accurate values using the fuzzy logic tools and techniques. We then perform a thorough analysis of the metric values offered by various wireless technologies, and derive crisp values for the imprecise network parameters. A sensitivity analysis reflecting the performance of, and relative importance of metrics on each network is carried out. These results are shown to impact user's decision in handing over data to the appropriate interface.

Development of femtocells is the most recent step towards increasing the network capacity of a wireless network and improving the quality of service for cellular users. However, as all the femtocells use the same radio band, it poses a serious interference issue amongst neighboring femtocells, especially when femtocells are densely deployed. In this paper, we study the problem of DL (downlink) and UL (uplink) interference amongst closed-access neighboring femtocells used in conjunction with the Long Term Evolution (LTE) technology and propose a solution to mitigate this interference using Fractional Frequency Reuse (FFR) technique. User equipments (UEs) report to their serving femto base stations (F-BSs) periodically. If the report reveals high interference level, neighboring F-BSs locally adopt FFR in a coordinated but decentralized way. FFR divides the femtocell in cell-center and cell-edge areas where the cell-edge of interfering F-BSs use distinct set of sub-carriers (SCs). The division takes place in a way such that the affected UE falls in the cell-edge area. The simulation results indicate that the proposed scheme decreases interference in the neighboring F-BSs, femto UEs (F-UEs) and macro UEs (M-UEs) and improves the overall throughput.

Modern multi-hop wireless networks employ a number of sophisticated schemes to secure the network against hostile attacks. However, constant improvements in any security mechanism is matched by ever increasing sophisticated attacks. Therefore, there is a constant need to develop innovative schemes, especially for applications where the integrity of the message is vital. Attacks from trusted byzantine nodes that belong to the network itself are particularly challenging, as these nodes have a hidden malicious component and have complete access to the network resources. Previous works have studied these attacks and countermeasures for multi-hop networks and on networks capable of performing Network Coding. In this paper, we identify an inherent security benefit of Analog Network Coding and show how it can be used to design a novel Dual Non-adjacent Watchdog scheme that can detect a set of malicious byzantine attacks.

Wireless Mesh Network (WMN) is a promising technology in providing high-bandwidth Internet access over a specific coverage area, with relative lower investment cost as compared with traditional wireless access networks. Authenticated key establishment (AKE) schemes enable two entities (e.g., a client and a server) to share common communication keys in an authentic way. Due to mobility of Mesh Clients (MCs), a WMN needs to have fast and efficient AKE scheme to provide adequate security during clients handoff while meeting the Quality of Service (QoS) requirements. In this paper, we propose a lightweight distributed AKE scheme based on hierarchical multi-variable symmetric functions (HMSF). In this AKE scheme, network entities in a WMN such as MCs and mesh routers can authenticate each other and establish pairwise communication keys without any interaction from the centralized authentication center, which substantially reduces the communication overhead and authentication delay.

As mobile stations (MSs) in the next generation cellular wireless systems will more frequently operate on multiple applications, such as web browsing, VoIP, online video etc., energy saving becomes more critical and face new challenges from the quality of service (QoS) requirements. A special operation state, called sleep mode, is designed for energy saving of MS, in which MS operates on continuous sleep cycles, where every sleep cycle is the sum of a listening window and a sleep window. This paper proposes an energy saving method that adaptively determines sleep cycles and shifts listening window. When MS is in sleep mode, the sleep cycles are extended by probabilistic decisions related to the traffic statistic attributes. Different from conventional methods, our method is also able to deal with mixed traffic pattern by shifting listening window. Extensive simulation results validate the advantages of our method both in terms of energy saving and shorter response time.

Fractional frequency reuse (FFR), using different frequency reuse factors for cell center and edge regions, is able to effectively improve spectrum efficiency in multi-cell OFDMA networks. However, optimal performance is hard to achieve in practice as the efficiency of resource allocation could drop drastically due to the constraint from the frequency partitions formed by FFR. Since the radio resource is pre-partitioned for cell edge and center, fair resource allocation in a cell is also difficult to implement. Conventional frequency partition adjustment either has high complexity due to global optimization or suffers from heavy performance degradation due to absence of effective control on inter-cell interference (ICI). To solve this issue, we create models for analyzing geographical distribution of interference in multi-cell networks. Based on the observed non-uniform distributed ICI, we redefine the zones for fractional reuse and propose clustering based FFR, which offers resource allocation higher flexibility and better fairness with additional spatial dimension. Extensive simulation has been performed to validate practicality and effectiveness of our proposed scheme.

Heterogeneous wireless network (HWN) technology enables a mobile client (MC) to access multiple heterogeneous subnets for better quality of service (QoS) at a lower cost. In the context of conventional network protocol, we cannot fully utilize the potential of a HWN by having separate and independently operating subnet interfaces. In this paper, we propose a multi-MAC management scheme, performing multi-subnets selection and rate allocation over multiple heterogenous wireless interfaces for uplink traffic. Our scheme considers uplink traffic mixed by multiple applications with different QoS requirements and allocates appropriate data rates to multiple connections between MC and subnets. Extensive simulation results compare the performance and validate our scheme.

Wireless sensors are low power devices with small transmission range, restricted computation power, limited amount of memory and with portable power supply. Wireless Sensor Network (WSN) is a collection of such sensors where the number of sensors can vary from few hundreds to thousands. Performing secure pair-wise communication between sensors is a really difficult task due to inherent characteristics. As memory and power consumption are most stringent requirements for these devices, use of conventional techniques for secured communication are totally out of question. This paper introduces a scheme that enables a complete pair-wise secure connectivity between any two adjacent sensor nodes, in spite of using small key ring (KR) for sensors. The Proposed Scheme (ELKPD) doesn't require any additional hardware while providing keys to the sensors irrespective of their location. Also, proposed scheme is easily scalable which enables addition of sensor nodes without any computational or hardware overheads.

Wireless Mesh Networks (WMNs) offer broadband wireless Internet access with flexible and cost-effective deployment. Security is one of the key issues should be considered before WMNs get widespread use. Authentication and key establishment (AKE) schemes enable two entities to share common communication keys in an authentic way. In a WMN, a Mesh Client (MC) and the accessing Mesh Router (MR) need to need to authenticate each other before the secure connection could be set up between them. Due to mobility of MCs, a WMN needs to have efficient authentication and key establishment scheme to provide adequate security while meeting the Quality of Service (QoS) requirements, especially during clients handoff. Mesh routers (MRs) also need to authenticate each other before set up the wireless connection. In this paper, we propose a authentication and key establishment scheme for WMN based on the identity-based cryptography (IBC), which enables efficient key agreement and mutual authentication between network entities in a WMN. Through this distributed authentication key establishment scheme, network entities can authenticate each other and establish pairwise communication keys with substantially reduced communication overhead and authentication delay.

To mitigate inter-cell interference (ICI) and achieve higher spectrum efficiency, fractional frequency reuse (FFR) has been widely adopted by the next generation wireless systems, wherein different frequency reuse factors are applied to cell center and cell edge zones. In such conventional FFR, a contiguous radio spectrum is partitioned in a fixed fashion across all cells for edge and cell center zones. This approach evidently lacks the flexibility of inter-cell and/or intra-cell resource allocation adjustment and the capability of dealing with traffic load fluctuation and quality of service (QoS) requirements variations. This paper models the implementation of FFR in a multi-cell network environment and proposes a scheme called D-FFR that can adaptively partition radio spectrum in a distributed manner to achieve different FFR configuration among different cells. Resource demands and various inter-cell/intracell allocation constraints are accounted in D-FFR to enable differentiable inter-cell and/or intra-cell throughput and deliver higher spectrum efficiency. Analytical and extensive simulation results are provided in the paper to validate the effectiveness of our proposed scheme.

Due to a continued increase in the speed and capacities of computing devices, combined with our society's growing need for mobile communication capabilities, multihop wireless networks (MWNs), such as wireless mesh networks (WMNs), have gained a lot of interest from the research community. Quality of service (QoS) provisioning in these networks is an essential component that is needed to support multimedia and real-time applications. On the other hand, directional antenna technology provides the capability for considerable increases in spatial reuse, which is essential in the wireless medium. In this paper, a bandwidth reservation protocol for QoS routing in TDMA-based MWNs using directional antennas is presented. The routing algorithm allows a source node to reserve a path to a particular destination with the needed bandwidth, which is represented by the number of slots in the data phase of the TDMA frame. Further optimizations to improve the efficiency and resource utilization of the network are also provided.

In this paper, we propose a novel spectrum occupancy model designed to generate accurate temporal and frequency behavior of various wireless transmissions. Our proposed work builds upon existing concepts in open literature in order to develop a more accurate time-varying spectrum occupancy model. This model can be employed by wireless researchers for evaluating new wireless communication and networking algorithms and techniques designed to perform dynamic spectrum access (DSA). Using statistical characteristics extracted from actual radio frequency measurements, first- and second-order parameters are employed in a statistical spectrum occupancy model based on a combination of several different probability density functions (PDFs) defining various features of a specific spectrum band with several concurrent transmissions. To assess the accuracy of the model, the output characteristics of the proposed spectrum occupancy model are compared with realtime radio frequency measurements in the television and paging bands.

Abstract In a static wireless sensor network (WSN), sensors close to the base station (BS) run out of energy at a much faster rate than sensors in other parts of the network. This is because the sensor close to the BS always relays the data for other sensors, resulting in an unequal distribution of network residual energy. In this paper, we propose a scheme for enhancing the network lifetime using multiple mobile cluster heads (CHs) that can move in the WSN in a controllable manner. The CH controllably moves toward the energy‐rich sensors or the event area, offering the benefits of maintaining the remaining energy more evenly, or eliminating multihop transmission. Therefore, the proposed scheme increases the network lifetime. We theoretically analyze the energy consumption in our scheme and propose three heuristical mobility strategies. We further study the collaboration among CHs in order to maintain their connectivity to the BS to ensure the delay requirement for real‐time applications. Simulation shows that network lifetime is increased by upto 75% over existing approach by making CHs always move toward a stable equilibrium point. Our connectivity algorithm provides a best case improvement of 40% in transmission delays over existing schemes. Copyright © 2009 John Wiley & Sons, Ltd.

Next generation wireless system such as advanced WiMAX (i.e., IEEE802.16m) and LTE advanced will fully embrace multi-hop relay architecture. The conventional Automatic Repeat reQuest (ARQ) and the more recent Hybrid ARQ (HARQ) are two simple yet highly effective error control techniques designed for single hop system. Nevertheless, extending them in a synergistic manner to support multi-hop relay networks is by no means a trivial undertaking. This paper explores a variety of multi-hop error control techniques such as hop-by-hop ARQ, 2-link ARQ and end-to-end ARQ, and various possible combinations with HARQ. We further establish an analytical framework for each of these key techniques and evaluate the performance. Based on the analysis and comparison, we propose a low complexity error control mechanism tailored for the multihop transmission features. Extensive simulation results compare the performance and validate our analytical framework.

In a wireless mesh network (WMN), mesh clients (MCs) access the Internet through the wireless backbone formed by the Internet Gateways (IGWs) and Mesh Routers (MRs). An IGW as the traffic center may easily become the congestion center in a WMN. The load balancing between IGWs will reduce the traffic congestion thereby improving the network performance and providing a better quality of service (QoS). In this paper, potential load balancing between different IGW service domains is examined and fairness metrics are defined for both homogenous and heterogeneous WMNs. A distributed load balancing scheme based on diffusion methods is proposed to achieve a global load fairness. The effectiveness and efficiency of proposed load balancing scheme are verified by extensive simulations.

A Wireless Mesh Network (WMN) is connected by multiple wireless mesh routers that are able to operate multiple channels for increased network capacity. As other wireless networks, the network capacity is a fundamental issue in the WMN. The analytical results in this paper show that the upper bound of network capacity lambda scales Theta(Wf/cradicn) if the number of infrastructure nodes m is significantly less than the number of MRs (n). Only when m asymptotically grows with n, the network capacity achieves Theta(Wfm/(n(2-P)c)), resulting in significant capacity gain. We shows the WMN upper bounds of the infrastructure network capacity eta and its ad hoc capacity zeta as well.

Widely deployed mesh routers (MRs) interconnect to each other and form a multi-hop backbone of a wireless mesh network (WMN), which provides a ubiquitous high-speed network access service for mesh clients (MCs) with a multi-cell architecture. Besides using air-interfaces, a more flexible and low cost MR deployment assumes lack of power cable at the locations of MRs, which enables MRs to be deployed anywhere needed. In deploying such a WMN, the power issue of MRs can be addressed by carry-on batteries that could be recharged by solar panels. The deployment of MRs, on the other hand, should ensure the connectivity of multi-hop backbone network, and an overlapped multi-cell coverage is also necessary to provide seamless connections for MCs. This paper provides analytical models to simultaneously consider connectivity, coverage and energy constraints in MR deployment and derives the necessary MR distribution function. Following the obtained results, we also propose a non-uniform WMN deployment scheme that substantially enhances the network throughput. Simulation results validate the effectiveness and advantages of our deployment strategy.

Wireless mesh networking (WMN), the static mesh routers (MRs) cooperatively relay each other packets to the Internet Gateway (IGW). The routing protocols assume all the nodes in the network to be non-malicious. However, the open architecture of WMNs paves way to malicious attackers who can exploit hidden loopholes in the routing protocol. In this paper, we mainly focus on the vulnerability of the network to a suction attack called blackhole attack. In detecting such attacks, we explore the use of intelligent agents called honeypots which are roaming virtual software agents that generate a dummy route request (RREQ) packets to lure and trap blackhole attackers. We illustrate the performance of our proposed detection approach by extensive simulation results using the ns-2 simulator.

Mesh router (MR) placement is one of the fundamental issues that need to be addressed carefully to achieve a desired performance of a wireless mesh network (WMN). The objective of the MR placement schemes is to systematically determine the minimal number of MRs and their positions while satisfying various constraints, such as coverage, connectivity, traffic demand, etc. This paper explores the solution for placing the MRs with multiple transmission rates, which influence both transmission range and wireless link capacity. In the paper, we first formulate the problem with a mixed integer programming model. We then present a heuristic placement algorithm called ILSearch which takes into account both multiple transmission rates and co-channel interference. The ILSearch consists of two components: (1) Coverage MR determination which greedily exploits the capability of each selected MR to cover mesh clients (MCs); and (2) Relay MR determination that incrementally chooses the additional MRs for traffic relaying through the local search. Our simulation has not only shown that ILSearch can effectively obtain the MR placement that meets all the constraints, but also demonstrated that a MR placement which considers the variable transmission rates outperforms those don't.

Intrusion detection in a Wireless Sensor Network (WSN) is of significant importance in many applications to detect malicious or unexpected intruder(s). The intruder can be an enemy in a battlefield, or a unusual environmental change in a chemical industry etc. With uniform distribution, the detection probability is the same for any point in a WSN. However, some applications may require different degrees of detection probability at different locations in the deployment area. Gaussian distributed WSNs (i.e., normal distribution) can provide differentiated detection capabilities at different locations and are widely deployed in practice. In view of this, this paper analyzes the problem of intrusion detection in a Gaussian distributed WSN, by characterizing intrusion detection probability with respect to intrusion distance and network deployment parameters. Two detection models are considered: single-sensing detection and multiple-sensing detection. Effects of different network parameters on the intrusion detection probability are examined in details. This work allows us to analytically formulate the intrusion detection probability within a certain intrusion distance under various application scenarios, therefore provides insight for directing the application-specific WSN deployment such as intrusion detection.

In this paper, we provide a new perspective for analyzing spectrum occupancy by introduced an M/M/l queueing model to generate accurate temporal and frequency behavior of various wireless transmissions. Our proposed research builds upon existing concepts in the open literature in order to develop a more accurate time-varying spectrum occupancy model. This model can be employed by wireless researchers for evaluating new wireless communication and networking algorithms and techniques designed to perform dynamic spectrum access (DSA). Using statistical characteristics extracted from actual radio frequency measurements, first- and second-order parameters are employed in a statistical spectrum occupancy model based on a combination of several different probability density functions (PDFs) defining various features of a specific spectrum band with several concurrent transmissions. To assess the accuracy of the model, the output characteristics of the proposed spectrum occupancy model are compared with real-time radio frequency measurements in the paging and ISM bands.

This paper proposes a Real-Time Duplication-Based Algorithm (RT-DBA) for scheduling precedence-related periodic tasks with hard deadlines on networks of workstations (NOWs). We have utilized selective subtask duplication that enables some tasks to have earlier start times, which enables additional tasks (and, hence, task sets) to finish before their deadlines, thereby increasing the schedulability of a real-time application. We strongly believe that duplication can be used as a tool for obtaining a better quality of service (QoS) from the real-time heterogeneous system, and this is our major contribution. We have taken both the computation and the communication heterogeneities into account while modeling such a system. Both data and control dependencies between the tasks have also been considered. Our algorithm exhibits scalability, fully exploits the underlying parallelism, and is capable of scheduling an application, even if the available number of processors is less than the required number of processors. Based on extensive simulation studies, we observe that RT-DBA offers an enhanced success ratio as compared to other scheduling schemes when communication is a dominant factor.

Localization algorithm continues to be an important and challenging topic in today's wireless sensor networks (WSNs). In this paper, a novel range-free localization algorithm using expected hop progress (LAEP) to predict the location of any sensor in a WSN is proposed. This algorithm is based on an accurate analysis of hop progress in a WSN with randomly deployed sensors and arbitrary node density. By deriving the expected hop progress from a network model for WSNs in terms of network parameters, the distance between any pair of sensors can be accurately computed. Since the distance estimation is a key issue in localization systems for WSNs, the proposed range-free LAEP achieves better performance and less communication overhead as compared to some existent schemes like DV-Hop and RAW. In addition, we study the effect of anchor placement on the algorithm performance by deriving the corresponding mean position error range. Extensive simulations are performed and the results are observed to be in good agreement with the theoretical analysis.

Interconnected Mesh Routers (MRs) constitute the backbone network of a Wireless Mesh Network (WMN) that provides access service to the Mesh Clients (MCs) spread over a wider region. In such an environment, multi-radio and multichannel are utilized to improve the network performance. This paper introduces an effective radio partitioning scheme and a queue management strategy that provide a novel hybrid operating mode. Few radios are dynamically switched among the channels in forwarding the packets while the rests remain at the assigned channels. The radios are allowed to adaptively change so as to meet the traffic load at a MR. Queue management changes the sequence of forwarding packet by grouping the packets over the same channel so that the channel switching overhead and the packet delay are minimized. Extensive simulations are performed to illustrate the effectiveness of our proposed scheme.

Wireless mesh network (WMN) technology extends the service coverage by supporting multi-hop communication and enhances the network capacity by utilizing multi-radio and multichannel. The number of multiple channels is essential for the implementation and the efficiency of channel assignment. While the number of channels is not sufficient, channel assignment needs to consider the channel sharing at certain mesh routers (MRs). The distribution of traffic flows in the network greatly affects the channel assignment. Different to a mobile ad hoc network (MANET), the traffic in a WMN is predominated by the Internet traffic. In this paper, we analyze the number of channels for a feasible conflict free channel assignment in such a network. We also propose a flow-based channel assignment in the channel constrained situation by implementing channel mergence algorithm so that MRs can appropriately share the channel resource. Extensive simulations are performed to illustrate the effectiveness of our proposed scheme.

This paper proposes a scheme for improvement of network lifetime and delay by employing a connected group of mobile cluster heads in a wireless sensor network (WSN). As data sensing is triggered by an event, the sensors relaying the aggregated data to the base station run out of energy at a much faster rate than sensors in other parts of the network. This gives rise to an unequal distribution of residual energy in the network, making the nodes with lower remaining energy level to die much faster than others. To distribute the remaining energy more evenly in the network, some energy-rich nodes are designated as cluster heads which move in a controlled manner toward locations rich in energy and data. This reduces the transmission energy required by the static sensors to send data and thus increases the overall lifetime of the network. Along with transmission energy, time taken for transmitting data to the BS is also reduced as the CHs follow a connectivity strategy to always maintain a connected path to the BS. Simulation shows that lifetime of the network can be increased by 42% over existing scheme by making the CHs always move towards a stable equilibrium point, i.e., a point where the total residual energy of the network and data are concentrated. Our connectivity algorithm also provides 40% improvement in the transmission delay as compared to existing schemes.

The technology of wireless mesh network (WMN) provides a flexible Internet access service in a wide region by employing multi-hop wireless routing and enhances the network performance by utilizing multi-radio and multi-channel. Delay analysis is a fundamental issue for delay-sensitive application such as VoIP and video conference, and delay constrained capacity is essential for a network to provide satisfied service. This paper models such a network and obtains the packet delay and network capacity by considering a queueing network formed by multi-radio mesh routers (MRs) and carrier sense multiple access (CSMA) mechanism is assumed for packet transmissions over links between MRs. We investigate the problems of intercluster dominated traffic, study the impact of the number of radios and channels to the delay and the capacity, and optimize the network performance by adjusting the MR deployment and the transmission power.

We present a mechanism for optimum distribution of internet traffic over heterogeneous network environment. A heterogeneous network can be considered as a combination of multiple homogenous networks available simultaneously to the end users. For simplicity, each network has been modeled as a M/M/1 queue. We aim to minimize the number of jobs in each queue subject to constraints. The optimization problem has been achieved through the use of Lagrange multiplier. Depending on their service rate the formulation done in this work is shown to optimally divide the rate of incoming traffic into different networks.

We propose a novel graph theoretic matching algorithm to model the dynamic channel allocation problem in cognitive radio networks. In the past, no research work has considered both the channels and the user request priorities in the context of spectrum allocation. In our work, we define a unique model to assign priorities among the channels in a spectrum based on the transmission power allowed in each channel to mitigate interference on the licensed primary users. Crisp logic lines categorize requests into distinct priorities based on the user requirements. These prioritized channels and user requests then constitute the set of vertices V of a bi-partite graph G = (V,E), whose set of edges E represent the communication links between the channels and the users. We propose a novel O(|E|) priority-satisfying matching algorithm to design an allocation scheme to satisfy the quality of service guarantees of the unlicensed secondary users. We evaluate the performance of our proposed algorithm based on critical parameters such as latency and packet dropping probability.

In the recent years, wireless mesh network (WMN) has evolved as a new paradigm for broadband wireless Internet access. The self-configurability, open wireless infrastructure, and different management styles of WMN make them vulnerable to malicious attackers. As a first step to secure WMNs, it is critical to incorporate an authentication mechanism for mesh clients. The existing proposals are primarily based on public key certificates, which incur considerable overhead in signature verification. We propose a network layer authentication mechanism called Merkle Tree based Mesh Authentication Protocol (MT-MAP) for WMNs. It incorporates inexpensive hash operations using Merkle tree to authenticate single/multihop mesh clients. We also show how the use of hash tree facilitates fast and periodic refresh of authentication certificates. Finally, we present a security analysis of MT-MAP against impersonation and replay attacks.

In this demo, a new application for the Wireless Sensor Networks (WSN) is presented. This is the first time WSN is used to in the music field, where the music is being manipulated and changed according to the movement of the dancer. Twenty-three tmote sensors have been deployed on a dancing stage, and two sensors were attached to the arms of each dancer. Information collected from sensors deployed on the stage are being sent and processed at a central location where the music being played is manipulated. This project is the first phase of collaboration in a multi-disciplinary research between the Computer Science department and the College-Conservatory of Music at the University of Cincinnati.

The wireless sensor network (WSN) has recently attracted considerable attention due to the low price and ease to deploy it. In particular, in a hostile or harsh regions where sensors cannot be deployed manually, WSNs can be established just by dropping sensors from the air. In this case, however, most likely sensors are not placed at optimal positions, although the location of sensors does have a drastic impact on the WSN performance. Moreover, randomized deployment algorithm can leave holes in terms of coverage in the sensing area. This paper proposes a sensor relocation scheme where mobile sensors move to patch up the holes by appropriate coverage. Simulation results show that the proposed algorithm outperforms prior existing schemes in terms of coverage and lifespan of WSNs.

In a wireless mesh network (WMN), mesh routers (MRs) are interconnected by wireless links and form a wireless backbone to provide ubiquitous high-speed Internet connectivity for mobile clients (MCs). The wireless backbone is tightly integrated with the Internet by a special kind of nodes called as Internet gateways (IGWs). Even though the capacity of WMN can be improved by equipping the MRs with multiple radios working at non-overlapping channels, the deployment of IGW is critical to the network performance of WMN. In this paper, we address the IGW placement problem based on a hierarchical cluster based architecture. The problem is first formulated as a linear program (LP) issue, then some heuristic algorithms are developed. Our simulation results show the effectiveness of the proposed algorithms.

The network performance such as node capacity in a wireless mesh network (WMN) could be limited due to inappropriate interface configuration. Mesh routers (MRs) with heavy load may suffer from interface shortage. On the other hand, a MR with less load experiences a low utilization of interfaces. In this paper, we advocate heterogeneous interface configuration to appropriately configure the MRs' interfaces. It achieves the purpose of minimizing the total number of interfaces in a WMN while guaranteeing the various constraints such as traffic demand. We first formulate the problem when the traffic demand is non-uniformly distributed. On the basis of theoretical analysis, we propose a heuristic algorithm to find a ";close-to- optimal"; solution for interface configuration. Our simulation shows the effectiveness of our proposed heuristic algorithm.

Under a multirate network scenario, the IEEE 802.11 DCF MAC fails to provide airtime fairness for all competing stations since the protocol is designed for ensuring max-min throughput fairness. As such, the maximum achievable throughput by any station gets bounded by the slowest transmitting peer. In this paper, we present an analytical model to study the delay and throughput characteristics of such networks so that the rate anomaly problem of IEEE DCF multirate networks could be mitigated. We call our proposal time fair CSMA (TFCSMA) which utilizes an interesting baseline property for estimating a target throughput for each competing station so that its minimum contention window could be adjusted in a distributed manner. As opposed to the previous work in this area, TFCSMA is ideally suited for practical scenarios where stations frequently adapt their data rates to changing channel conditions. In addition, TFCSMA also accounts for packet errors due to the time varying properties of the wireless channel. We thoroughly compare the performance of our proposed protocol with IEEE 802.11 and other existing protocols under different network scenarios and traffic conditions. Our comprehensive simulations validate the efficacy of our method toward providing high throughput and time fair channel allocation.

Intrusion detection in Wireless Sensor Network (WSN) is of practical interest in many applications such as detecting an intruder in a battlefield. The intrusion detection is defined as a mechanism for a WSN to detect the existence of inappropriate, incorrect, or anomalous moving attackers. For this purpose, it is a fundamental issue to characterize the WSN parameters such as node density and sensing range in terms of a desirable detection probability. In this paper, we consider this issue according to two WSN models: homogeneous and heterogeneous WSN. Furthermore, we derive the detection probability by considering two sensing models: single-singing detection and multiple-sensing detection. In addition, we discuss the network connectivity and broadcast reachability, which are necessary conditions to ensure the corresponding detection probability in a WSN. Our simulation results validate the analytical values for both homogeneous and heterogeneous WSNs.

A wireless sensor network (WSN) has to maintain a desirable sensing coverage and periodically report sensed data to the administrative center (i.e., base station) and the reporting period may range from months to years. Coverage and lifetime are two paramount problems in a WSN due to constraint of associated battery power. All previous theoretical analysis on the coverage and lifetime is primarily focused on the random uniform distribution of sensors or some specific network scenarios (e.g., a controllable WSN). In this paper, we provide an analytical framework for the coverage and lifetime of a WSN that follows a two-dimensional Gaussian distribution. We also study the coverage and lifetime when the dimensions of Gaussian dispersion (i.e., x, y) admit different Gaussian parameters (i.e., standard deviation, $\sigma_x \neq\sigma_y$). We identify intrinsic properties of coverage/lifetime in terms of Gaussian distribution parameters, which is a fundamental issue in designing a WSN. Following the results obtained, we further determine the sensor deployment strategies for a WSN that could satisfy a predefined coverage and lifetime. Two deployment algorithms are developed based on using our analytical models and are shown to effectively increase the WSN lifetime.

The paper presents a detailed discussion of various issues involved in designing a medium access control (MAC) protocol for multihop wireless networks with nodes employing multiple beam smart antennas. Multiple beam smart antennas can form several beams simultaneously and can initiate concurrent transmissions or receptions .in them, thereby increasing the throughput of the bottleneck nodes. Traditional on-demand MAC protocols for omnidirectional and single beam directional antennas based on the IEEE 802.11 distributed coordination function (DCF) mechanism cannot take advantage of this unique capability of multiple beam antennas as they do not facilitate concurrent transmissions or receptions by a node. This paper introduces a novel protocol, hybrid MAC (HMAC), which enables concurrent packet reception (CPR) and concurrent packet transmission (CPT) at a node equipped with multiple beam antennas and is backward compatible with IEEE 802.11 DCF. Simulation results show the superior performance of HMAC in most ad hoc scenarios. Moreover, in some sample topologies, the throughput of HMAC is close to the theoretical maximum. The paper also presents a wireless mesh network architecture with heterogeneous antenna technologies and illustrates the advantages of employing multiple beam smart antennas and HMAC in such networks.

Existing rate adaptation algorithms can broadly be classified under two categories: (a) signal to noise ratio measurement based and (b) statistical count based. While the former suffers from inaccurate estimations, the latter utilizes pre-defined thresholds for dynamically varying the rate. In this paper, we first analyze the impact of transmission rate on the performance of a wireless link as the performance may either improve or deteriorate with increasing transmission rates. Based on this observation, we then propose stochastic automata rate adaptation algorithm (SARA). SARA is inspired by stochastic learning automata (SLA), a machine learning technique for adaptation in random environments. SARA assigns a selection probability to each of the transmission rates. It then randomly selects a rate for a transmission attempt and dynamically updates the probabilities based on the obtained feedback from the receiver (ACK/NACK), thereby obviating the need for explicit channel estimation or predefined thresholds. As opposed to the previous work, SARA is ideally suited for both stationary and non-stationary channel environments and is fully compatible with the existing IEEE 802.11 MAC standard. We compare the performance of our proposed protocol with automatic rate fallback (ARF) thoroughly and adaptive ARF (AARF) and other existing protocols, under different channel scenarios.

Abstract In ad hoc networks, CSMA/CA is a widely used MAC layer protocol. There has been considerable work on the performance evaluation of this protocol. But most work is confined to saturation performance of single‐hop ad hoc networks. In this paper, we employ a linear feedback model to evaluate the performance for CSMA/CA according to the Poisson distributed traffic in both single‐hop and multi‐hop ad hoc networks. To the best of our knowledge, this is the first attempt to analytically evaluate the performance for CSMA/CA protocol under a general assumption about the traffic. This paper also gives analytical results, showing the impact of RTS/CTS. Although RTS/CTS do add the overhead to the system, they become essential when either the hidden terminal problem is dominant, or the traffic is heavy, or the packet length is very large. This paper also shows that the performance degrades dramatically in multi‐hop ad hoc networks when the number of competing nodes increases, which implies that the scalability is still a major problem in ad hoc networks. To validate our analytical results, we have done extensive simulations, and it is observed that the simulation results match the analytical results very well. Copyright © 2006 John Wiley & Sons, Ltd.

Abstract Integration of ad hoc networks with the Internet provides global Internet connectivity for ad hoc hosts through the coordination of mobile IP and ad hoc protocols. In a pure ad hoc network, it is difficult to establish trust relationship between two ad hoc hosts due to lack of infrastructure or centralized administration. In this paper, an infrastructure‐supported and distributed authentication protocol is proposed to enhance trust relationships amongst ad hoc hosts. In addition, an effective secure routing protocol (SRP) is discussed to protect the multi‐hop route for Internet and ad hoc communication. In the integrated ad hoc networks with Internet accessibility, the ad hoc routing security deployed with the help of infrastructure has a fundamental impact on ad hoc hosts in term of Internet access, integrity, and authentication. Both analysis and simulation results demonstrate the effectiveness of the proposed security protocol. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract — We present two on-demand MAC protocols to provide differentiated service classes over multiple beam antennas. We use embedded feedback from neighboring nodes to synchronize data communication at multiple beams. The protocols use multilevel queues to organize data, and employ a quality of service (QoS) aware packet scheduler to facilitate disparate traffic flows. We further present a novel paradigm in wireless channel access – receiver initiated choice of sender (RICS). RICS organizes the senders into multilevel queues providing an elegant method to bias the probability of channel award to these nodes. Simulation results demonstrate successful provision for multiple service classes. Keywords- Differentiated service classes, multiple beam antennas, medium access control, Quality of Service, wireless ad hoc networks. I.

This paper identifies faulty sensor(s) in a polynomial-based data aggregation scenario, TREG proposed in our earlier work. In TREG, function approximation is performed over the entire range of data and only coefficients of a polynomial (P) are passed instead of aggregated data. Performing further mathematical operations on the calculated P can identify the maximum (max) and minimum (min) values of the sensed attribute and their locations. Therefore, if any sensor reports a data value outside the [min, max] range, it can be identified as a faulty sensor. We achieve the following goals: (1) uncorrelated readings from a specific sensor helps in detecting a faulty sensor, (2) faulty sensors are detected near the source and isolated preventing them from affecting the accuracy of the overall aggregated data and reducing the overall delay. Results show that a faulty sensor can be detected with an average accuracy of 94 %. With increase in node density, accuracy in faulty sensor detection improves as more nodes are able to report the information to their nearest tree node.

We propose a polynomial-based scheme that addresses the problem of event region detection (PERD) for wireless sensor networks (WSNs). Nodes of an aggregation tree perform function approximation of the event using multivariate polynomial regression. Only the coefficients of this polynomial are then transmitted up the tree instead of aggregated data. PERD includes two components: event recognition and event report with boundary detection. In addition, PERD is capable of detecting single event or multiple events simultaneously occurring in the WSN. Since PERD is implemented over a polynomial tree on a WSN in a distributed manner, it is easily scalable and computation overhead is very light. Results reveal that event(s) can be detected by PERD with error in detection remaining almost constant achieving a percentage error within a threshold of 10% with increase in communication range.

In this paper we present a design of a medium access control protocol that allows the utilization of unused licensed spectrum of deployed wireless cellular systems (Primary System) by an overlaid multi-hop ad hoc network (Secondary System). The basic design principle is that the secondary operates in a non-intrusive manner and does not interact with the primary. We address a number of architectural challenges pertinent to this networking environment, and evaluate the performance of the MAC. Our performance evaluation results show that, in a single-hop ad hoc network, the proposed MAC transparently utilizes 75% of the bandwidth left unused by the primary, while, in the multi-hop cases, due to spatial reuse, the bandwidth utilization can be significantly higher.

The problems of energy efficient sensor network configuration and local fusion of sensed data have been addressed separately in the previous works. In this paper, we propose to analyze the sensing accuracy with the consideration of the node distribution and fusion overhead in terms of the energy consumption. By extending existing sensing model in the literature, we quantify how the sensing ranges and node densities of sensor nodes impact the sensing accuracy, and how it affects the fusion overhead and the sensing lifetime of the network. We identify the tradeoff between sensing accuracy and energy consumption in an analytical framework. It can be used to choose optimal parameters of sensor networks to meet the specified sensing or lifetime requirements.

The wide area wireless network (IEEE 802.16 WMAN) supports integrated services such as constant bit rate voice, variable bit rate video, high speed FTP and low speed www data. Efficient resource management in such network is a real challenge because of QoS requirements of integrated services and the error prone nature of the radio channel. In this paper, we mainly focus on the efficient packet transmission mechanism in such network. We propose an efficient channel prediction scheme which combines the handshake probing and prediction together to probe the channel state before transmission. Based on the maximum tolerant BER of different services, channel state is classified into three different states and an adaptive packet transmission scheme for all services under different channel states is introduced. The performance of the proposed schemes are evaluated and the results verified by using extensive simulations.

Unlike ad hoc networks where traffic is randomly distributed among every pair of nodes, the traffic in wireless mesh networks (WMNs) is predominantly toward or from the Internet Gateways (IGWs)for Internet services. Due to this, interference and collision are more serious in the Mesh Router (MRs) closer to the IGWs and the Internet throughput of the network is limited by the number of orthogonal channels and radios of the IGW. In this paper, we propose a channel assignment scheme which exploits a tree-based topology in WMNs and implements a heuristic channel assignment algorithm, aiming to achieve the maximal Internet throughput. The channels are sequentially assigned level by level in the tree, starting from the IGW. The simulation results show that the network using this scheme achieve the Internet throughput close to the maximal capacity of IGW.

The allocation of channel bandwidth without significantly increasing the interference among existing users is a challenge for the future UWB networks. Our research work presents a novel rake optimization and power aware scheduling (ROPAS) architecture for UWB networks. We propose to use cognitive radio (CR) for dynamic channel allocation among the requesting users while limiting the average power transmitted in each sub-band. In our proposed ROPAS architecture, dynamic channel allocation is achieved by a CR-based cross-layer design between the PHY and medium access control (MAC) layers. The joint power control and link scheduling in the MAC layer reduces adjacent channel and multi-access interference introduced by multiple access of the links. Furthermore, the Rake optimization with its strategic selection of propagation paths achieves the minimal bit-error rate (BER) at the rake receiver by mixed integer programming. Our simulated-based performance evaluation confirms the effectiveness and novelty of our proposed ROPAS architecture.

In a wireless mesh network (WMN), mesh routers (MRs) are interconnected by wireless links and form a wireless backbone to provide ubiquitous high-speed Internet connectivity for mobile clients. The wireless backbone is tightly integrated with the Internet by nodes called as Internet gateways (IGWs). In this paper, we address the IGW deployment problem which is shown to be NP-hard. We first formulate it as a linear program (LP) issue, then develop two heuristic algorithms for the purpose of cost-efficient IGW deployment. We further compare our algorithms with a leading approach by extensive simulations. Our analysis shows the effectiveness of the proposed algorithms.

Physical attributes such as temperature exhibit gradual change in value with space. Observations from the sensor nodes are thus highly correlated. In this paper, we propose a scheme to exploit the spatial correlation of data in a three dimensional wireless sensor network (WSN), in a way so as to reduce the number of transmissions in the network, thereby saving energy. The presented work is an extension of the earlier proposed TREG scheme which is only applicable to two dimensional WSN. Our scheme involves formation of binary tree and transmission of data along the tree nodes. Simulation has been carried out for different tree heights. Simulation results show that a tree height of four provides results with optimal values.

The placement of mesh routers (MRs) in building a wireless mesh network (WMN) is the first step to ensure the desired network performance. Given a network domain, the fundamental issue in placing MRs is to find the minimal configuration of MRs so as to satisfy the network coverage, connectivity, and Internet traffic demand. In this paper, the problem is addressed under a constraint network model in which the traffic demand is non-uniformly distributed and the candidate positions for MRs are pre-decided. After formulating the MR placement problem, we first provide the theoretical analysis to validate the traffic demand and determine the optimal position of Internet gateway (IGW). To reduce complexity of determining the locations of MRs while satisfying the traffic constraint, we propose an effective heuristic algorithm to obtain an close-to-optimal solution. Finally, our simulation results verify our analytical model and show the effectiveness of our proposed algorithm.

This paper proposes a scheme for enhancement of network Lifetime using MObile Clusterheads (LIMOC) in a wireless sensor network (WSN). The low energy, static sensor nodes sense physical parameters and route the data to the highly energy-rich nodes called ClusterHeads (CHs) which are mobile and can transmit data directly to the base station (BS). A collaborative strategy among the CHs increases the lifetime (hence residual energy) of the network further. Simulation has shown that residual energy of the network can be improved by 45% by making the CHs always move towards the event in an event-driven network. For general cases, increased energy savings is obtained by making the CH move towards the center of equilibrium w.r.t. to both the total residual energy and data flow of the network.

As wireless channel is bursty in nature, a two-state Markov channel model that considers the impact of bursty characteristics of channel errors is introduced into the analysis of operation and performance of saturated IEEE 802.11 DCF in this paper. A new scheme IDCF to exploit the information on the channel burstiness is further proposed to enhance the performance of DCF. The main idea of IDCF is to differentiate the handling of collision and data packet corruption at the sender. By adopting a persistent re-transmission approach according to the instantaneousness of the channel error, the performance of IEEE 802.11 DCF can be improved. Simulations are conducted and simulation results show that our analysis is accurate, and our proposed IDCF scheme does improve the performance in terms of throughput soundly.

Energy efficiency and reliable data delivery are the two most important parameters for designing wireless sensor network protocols. Wireless communication is inherently unpredictable and error-prone. Hence, reliability is required to ensure that a packet reaches its desired destination; otherwise the energy expended in forwarding the packet is wasted On the other hand, energy-saving mechanisms are required for battery-constrained sensor networks. In this paper, we have designed an on-demand energy-efficient and reliable medium access control (E2RM: AC) protocol that enables reliable data delivery and energy conservation without affecting packet latency. We have demonstrated the superior performance of E2RMAC over existing energy-efficient and reliability-enforcing approaches in terms of reliability, latency, scalability and energy-efficiency.

In a wireless ad hoc networks where all mobile nodes (MNs) have the same transmission range and the MN density is sufficiently high, the actual hop count between any two MNs is proportional to the distance between them. This paper shows the relation between distance and hop count first. Then, based on the relation, the required hop count between two given MNs is estimated. With the distribution of distance between pairs of MNs, this paper also suggests the optimal transmission power of MNs, which can guarantee delay constraints of a requested ratio of connections in an entire network. All problems are investigated in both a two-dimensional and a three-dimensional area. Simulation results substantiate the accuracy of the proposed approximation methods. The errors of the hop count estimation method are just 0.88% and 2.33% in a 2D and 3D area.

Abstract A growing need to have ubiquitous connectivity has motivated our research to provide continuous connection between various wireless platforms such as cellular networks, wireless local area networks (WLANs), and mobile ad hoc networks (MANETs). In this paper, we consider integration at the routing layer and propose two adaptable routing protocols (IRP‐RD and IRP‐PD) that exploit topology information stored at the fixed network components (cellular base stations and WLAN access points) for the route discovery and maintenance processes. Our proposed protocols can provide connectivity to the cellular network and/or WLAN hotspots through multihop routing, while differ in the gateway discovery approach used. In IRP‐RD, multihop routes to gateways to the cellular network or WLAN hot spots are discovered on demand, while in IRP‐PD out of coverage users proactively maintain routes to the gateways. Furthermore, proposed protocols can be used in any heterogeneous scenario, combining a cellular network and WLANs operating in infrastructure or ad hoc (MANET) mode. We provide simulation results that demonstrate the effectiveness of the proposed integrated routing protocols and show the advantages and drawbacks of each gateway discovery approach in different heterogeneous scenarios. Copyright © 2006 John Wiley & Sons, Ltd.

This paper proposes a scheme for domain partition to achieve the tradeoff between load-balancing and inter-domain mobility to reduce the negative impact of the host mobility. The load-balancing scheme for domains includes: an initialization procedure to divide a mesh network into domains, and a load adjustment procedure to rebalance the traffic load of neighboring domains when required. Moreover, the proposed scheme provides inter-domain mobility in support of multi-hop communication with the multi-hop cellular IP (MCIP) mobility protocol. Our experimental results show that the proposed protocol effectively controls the migration of mesh routers as well as mobile stations.

Assuming that all mobile nodes (MNs) have the same transmission range, the actual hop count between any two MNs is proportional to the distance between them. Based on the found relation between distance and hop count, the required hop count between two MNs can be accurately estimated, given the distance between them. Using the distribution of distance between MNs, this paper also suggests the optimal transmission range of MNs, which can guarantee delay constraints of a requested ratio of connections in an entire network.

While most existing research efforts in the area of wireless sensor networks have focused on networks with identical nodes, deploying sensors with different capabilities has become a feasible choice. In this paper, we focus on sensor networks with two types of nodes that differ in their capabilities, and discuss the effects of heterogeneity of sensing and transmission ranges on the network coverage and broadcast reachability. Our work characterizes how the introduction of a few sensor nodes with better capabilities can reduce the number of total required sensors without sacrificing the coverage and the broadcast reachability. Analytical results are validated via simulations. This work can serve as a guideline for designing large-scale sensor networks cost-effectively. It can also be extended to more complicated heterogeneous wireless sensor networks with more than two types of sensors.

Wireless sensor networks present a feasible and economic solution to some of the most challenging problems such as intrusion detection. In this paper, we establish relationship between node density, sensing range, and the possible intrusion distance before the intruder is detected by any of the sensors. We also extend our model to the multi-sensor joint detection case where an event can only be detected by k (k > 1) sensors simultaneously. Furthermore, we consider the effect of node heterogeneity on the intrusion detection in wireless sensor network, where two types of sensors with different sensing ranges are deployed. All the analytical results are validated via simulations. Our analysis can provide very useful insights in choosing network design parameters of sensor networks so that specified performance requirements can be met, thereby enhancing the acceptance of sensor networks.

Wireless mesh networks exploit multi-hop wireless communications between access points to replace wired infrastructure. However, in multi-hop networks, effective bandwidth decreases with increasing number of hops, mainly due to increased spatial contention. Longer hop length flows suffer from extremely low throughputs which is highly undesirable in the envisioned scenarios for mesh networks. In this paper, we show that queue/buffer management, at intermediate relay mesh nodes, plays an important role in limiting the performance of longer hop length flows. We propose a novel queue management algorithm for IEEE 802.11s based mesh networks that improves the performance of multihop flows by fairly sharing the available buffer at each mesh point among all the active source nodes whose flows are being forwarded. Extensive simulations reveal that our proposed scheme substantially improves the performance of multihop flows. We also identify some important design issues that should be considered for the practical deployment of such mesh networks.

Wireless mesh networks are envisioned to support the wired backbone with a wireless backbone for providing Internet connectivity to residential areas and offices. Routing protocols designed for mobile ad hoc networks (MANETs) primarily concentrate on finding a single best possible route to any destination out of the various paths available. However in wireless mesh networks, traffic is primarily routed either towards the Internet gateways (IGWs) or from the IGWs to the access points (APs). Thus, if multiple APs choose the best throughput path towards a gateway, the traffic loads on certain paths and mesh routers increases tremendously thereby deteriorating the overall performance of the network. To this end, we propose a novel multi-path hybrid routing protocol, multipath mesh (MMESH), that effectively discovers multiple paths. We also propose elegant traffic splitting algorithms for balancing traffic over these multiple paths to synergistically improve the overall performance. Through extensive simulations, we observe that our protocol works very well to cope with the variations in the network. Our protocol also improves the performance of flows traversing multiple hops

Wireless mesh networks (WMNs) are evolving to be the key technology of the future. As the WMNs are envisioned to provide high bandwidth broadband service to a large community of users, the Internet gateway (IGW) which acts as a central point of Internet attachment for the mesh routers, it is likely to be a potential bottleneck because of its limited wireless link capacity. We propose a novel technique that elegantly balances the load among the different IGWs in a WMN. We switch the point of attachment of an active source serviced gateway depending on the average queue length at the IGW. The proposed load balancing scheme includes: an initial gateway discovery module, which determines a primary gateway for a mesh router and a load balancing module that rebalances the load among the gateways. We use ns-2 for evaluating our proposed scheme and we observe that the proposed scheme is able to balance the traffic efficiently

A wireless sensor network (WSN) is composed of wireless sensors using batteries with energy constraints, which limits the network lifetime. How to maximize the network lifetime is an important issue in the design of WSNs. We establish a relationship between node density and network lifetime in a periodically data delivery scenario of WSNs with sensors transmitting data to the sink node periodically. Based on our analysis, we propose a sensor node density deployment method that could implement a differential node density in WSNs so that the lifetime of the network could be maximized. Both theoretic analysis and simulation results show that our method outperforms the uniform node distribution method in terms of the network lifetime

In this paper, we study the node sleep scheduling scheme in the commonly used static disk model for sensor networks, where homogenous sensors are uniformly distributed in a circular area with a stationary sink located at the center. Then, we introduce and analyze a hops-based sleeping scheduling algorithm (HSS) for enhancing the lifetime and energy efficiency of the sensor networks. The HSS divides the circular sensor network into several levels according to the average hop distance based on certain network parameters. By assigning hops-based sleeping probabilities to each sensor, and the network lifetime as well as energy efficiency can be greatly improved. Simulations are performed to compare our proposed HSS scheme with the traditional randomized sleeping scheduling (RSS) scheme, where all the nodes have the uniform sleeping probability. The results demonstrate that our HSS scheme can enhance network lifetime greatly, provide desired QoS requirement effectively, and drastically outperform the RSS scheme

In this paper, we propose a novel localization algorithm using expected hop progress (LAEP) to predict the positions of sensor nodes in WSNs. Our algorithm is based on a hop progress analytical model for a given network topology. By deriving relationship between node connectivity and expected-hop progress from the model, the distance between any two nodes can be accurately computed. As the distance estimation is a key issue in positioning system of WSNs, our expected-hop progress based localization algorithm also achieves reasonable performance in anchor-based WSNs with very few anchors. In addition, we considered the impact of deterministic anchor placement on the algorithm performance when the sensors are random deployed. Both grid and triangular placement of anchor nodes have been examined in this paper. Simulation results are seen to be in good agreement with the theoretical analysis and substantiate the validity of our proposed scheme LAEP

Multiple beam antennas can initiate several data communications concurrently by forming spatially separable beams. However, their concurrent packet reception (CPR) capability is largely governed by the underlying medium access control (MAC) protocol. In this paper, we present an analytical framework to calculate CPR upper bounds of multiple beam antennas using on-demand MAC protocols. The model can be used for adaptively changing transmission probability of the nodes so as to achieve optimal performance. We consider both transmitter-initiated and receiver initiated medium access protocols with uniform and random distribution of nodes. Using the developed model, we compute CPR capability of IEEE 802.11 DCF and ESIF based mechanisms for multiple beam antennas. We verify our model using simulations

Tins paper presents CMAC, a fully desynchronized MAC protocol that is designed to exploit the existing multi-channel support in sensor nodes. The hardware requirements of our protocol are minimal, requiring a single half-duplex transceiver and a low-power wake-up radio. CMAC takes into account the fundamental energy constraint in sensor nodes by placing them in a default sleep mode and waking them up only when necessary. As a contrast to other dual radio wake-up schemes, our protocol focuses on how communication and its preceding control message exchange mechanism can be undertaken in a multi-channel scenario without assuming a separate control channel. CMAC enables spatial channel re-use, nearly collision free communication, and addresses the deafness problem without incurring a tradeoff in fairness or latency. When compared with a recent MAC protocol SMAC, results show that CMAC obtains nearly 200% reduction in energy consumption, significantly improved throughput, and end-to-end delay values that are 50-150% better than SMAC for our simulated topologies

Multi-hop cellular networks offer attractive benefits for the next generation of wireless communication by integrating ad hoc relaying to cellular networks. However, most of the existing architectures and protocols for multi-hop cellular networks suffer from a variety of security threats in an adversarial environment. The existing architectures and protocols are not capable of providing end-to-end security protection for mobile users. A generalized multi-hop security protocol (GMSP) is proposed in this paper to achieve an effective route discovery protection from a range of potential security threats. The proposed multi-hop security protocol integrates mobile IP security and ad hoc security schemes. Moreover, the proposed protocol is flexible enough for fulfilling security protection for most existing heterogeneous multi-hop cellular architectures

Due to the resource constraints, pre-distributing secret keys into sensor nodes before they are deployed is an applicable approach to achieve information security in wireless sensor networks. Several key pre-distribution schemes have been proposed in literature to establish pairwise keys between sensor nodes; they are either too complicated, or insecure for some common attacks. To address these weaknesses, we propose an improved pairwise key establishment mechanism for wireless sensor networks in this paper. Compared with existing approaches, our scheme has better network resilience against node capture attack. Analysis and simulation results show that our scheme performs better than earlier proposed schemes in terms of network connectivity, key storage overhead, maximum supported network size, computational and communication overheads

Over the past few years, wireless local area networks (WLANs) have gained an increased attention and a large number of WLANs are being deployed in universities, companies, airports etc. Majority of the IEEE 802.11 based WLANs employ distributed coordination function (DCF) in wireless access points (AP) to arbitrate the wireless channel among Wireless Stations (STAs). However, DCF poses serious unfairness problem between uplink and downlink flows. To overcome this unfairness problem, we propose a simple enhancement to the IEEE 802.11 DCF which provides priority to the AP and thus enables it to acquire a larger share of the channel when required. We have demonstrated the unfairness problem through systematic measurements in an experimental test bed of WLAN using the legacy 802.11 DCF. We also developed analytical models to calculate the throughput of AP and the STAs and verify these results through thorough simulations in ns-2. We observe that our simulation results find in good agreement with our analytical models. Results show that our proposed enhancement achieves a fair distribution of bandwidth and improves the throughput (by nearly 300%) for the downlink flows as compared to the DCF, without severely affecting the performance of uplink flows

A wireless sensor network typically consists of a dense deployment of sensor nodes to achieve higher resolution and better network coverage. Having a dense network increases the fault-tolerance and robustness of the system. However, if not properly handled, it can lead to more collisions during transmission and also network congestion. Furthermore, wireless communication is inherently unpredictable and error-prone. Hence, it is imperative to design an efficient medium access control (MAC) protocol that facilitates guaranteed delivery of data over unreliable wireless links. In this paper, we have designed an on-demand reliable MAC (RMAC) protocol that enables timely delivery of data. We have demonstrated its superior performance over existing reliability-enforcing approaches in terms of reliability, latency, scalability and energy-efficiency

Bluetooth is a radio technology for wireless personal area networks in the 2.4 GHz ISM frequency band and allows short-range devices to be connected in the form of ad hoc networks. The Bluetooth medium access control protocol is based on a strict master/slave concept wherein any communication between slave devices has to go through the master. While this model is simple, the use of such a nonoptimal packet forwarding scheme incurs much longer delays between any two slave-devices as double the bandwidth is used by the master. In addition, if two or more devices want to communicate as a group, this can only be achieved by either multiple unicast transmissions or a piconet-wide broadcast from the master. To handle these issues efficiently, we propose a novel combination of dynamic slot assignment (DSA) and piconet partitioning. With DSA, the piconet master dynamically assigns slots to slaves so as to allow them to communicate directly with each other without any intervention from the master. Our proposed communication architecture provides for enhanced quality of service (QoS), better admission control, and multidevice conversation, which make a multicast-like communication feasible within the piconet. To widen the scope of DSA, we propose a QoS-aware enhanced DSA (EDSA) version where dynamic piconet partitioning and scatternet support are exploited by grouping devices into piconets as per their connection endpoints, enabling it to be employed over a scatternet. We have performed extensive simulations and observe that these schemes drastically enhance Bluetooth performance in terms of the delay and the throughput, while significantly reducing the network power consumption

This paper addresses the issue of routing in mobile ad hoc networks (MANETs) using directional antennas. Existing directional routing schemes either assume a complete network topology beforehand or simply use omni-directional routing schemes to forward packets in underlying directional environment. In this paper, we propose a Directional Routing Protocol (DRP) for MANETs. DRP is an on-demand directional routing protocol which assumes a cross layer interaction between routing and MAC layer and is inspired by Dynamic Source Routing (DSR) protocol. The main features of DRP include an efficient route discovery mechanism, establishment and maintenance of directional routing and directional neighbor tables (DRT and DNT, respectively), and novel directional route recovery mechanisms. We have implemented DRP on top of MDA; a MAC protocol for directional antennas and have compared its performance with the DSR protocol over both omni-directional and directional antenna models. Our results show that DRP considerably improves the packet delivery ratio, decreases the end to end packet latency, has lesser routing overhead, and is robust to link failures.

Abstract In this work we address the issue of deafness and hidden terminal problem in mobile ad hoc networks (MANETs) using directional antennas. To minimize these effects, we propose a MAC protocol for directional Antennas (MDA) which employs a novel enhanced directional network allocation vector (EDNAV) scheme and an efficient technique of diametrically opposite directions (DOD) transmission of RTS and CTS packets. We compare MDA with IEEE 802.11 and two recently proposed directional MAC (DMAC) schemes and results show that MDA outperforms these protocols in the majority of scenarios investigated. We also point out that the performance does depend on the network topology and the traffic pattern. A shorter version of this has appeared in Globecom 2005. Copyright © 2006 John Wiley & Sons, Ltd.

Abstract In this paper, we propose a directional antenna medium access (DAMA) protocol and its enhanced version called enhanced DAMA (EDAMA), which takes advantage of the benefits offered by directional antennas. Both of these schemes have been inspired by the IEEE 802.11 MAC, with major enhancements including a new neighbor discovery scheme, an optimized circular directional transmission of RTS and CTS to prevent the hidden node problem, reduce collisions and decrease node deafness, and also a multi‐buffer management scheme. A pair of communicating nodes using these schemes simultaneously transmits the circular directional RTS and CTS only to those sectors with neighbors, hence reducing overall communication delay and enhancing throughput. The main difference between DAMA and EDAMA lies in the way buffering is provided in the MAC layer. Unlike DAMA, which uses a single MAC buffer for all antenna beams as in IEEE 802.11, EDAMA employs separate buffers for each of the antenna sectors and introduces an integrated network and MAC cross‐layer design. This helps in eliminating the ‘self‐induced blocking’ problem prominent in existing directional MAC protocols. We have compared DAMA, EDAMA, IEEE 802.11, and two recently proposed directional MAC protocols, and results show that DAMA and EDAMA perform better than existing MAC protocols in the majority of the scenarios investigated, while EDAMA is observed to perform best. We also point out that the performance usually depends on the network topology and traffic pattern. Copyright © 2006 John Wiley & Sons, Ltd.

This paper addresses the issue of deafness and hidden terminal problem in a Mobile Ad Hoc Networks (MANETs) using directional antennas. To minimize these effects, we propose a MAC protocol for directional Antennas (MDA) which employs an enhanced directional network allocation vector (NAV) scheme and, a novel technique of Diametrically Opposite Directions (DOD) transmission of RTS and CTS. We compare MDA with IEEE 802.11 and two recently proposed directional MAC protocols and results show that MDA outperforms these protocols in the majority of scenarios investigated. We also point out that the performance does depend on the network topology and the traffic pattern.

This paper introduces a novel cross layer medium access control protocol for multiple beam antennas to fully utilize their multiple-beam-forming capability. Our protocol, explicit synchronization via intelligent feedback (ESIF), uses feedback from neighboring nodes to synchronize data communication at multiple beams. ESIF exploits routing information to guarantee long-term fairness and minimize the energy and latency overheads. Unlike previous works on directional antennas that discuss range extension, we focus on optimal spatial reuse. Simulation results demonstrate that ESIF outperforms other on-demand access schemes based on IEEE 802.11 DCF for multiple beam antennas

Recent interest in multi-hop infrastructure networks (MINs) has resulted in a need for an accurate model to predict the behavior of such systems. We consider a traffic-based network model to characterize these networks. We first analyze the link delay characteristics of MINs. This is followed by a method to obtain the cdf of multi-hop traffic inter-arrival time. Finally, the IEEE 802.11 distributed coordination function (DCF) is modeled for MINs and expressions for the throughput and delay are obtained. The proposed model is generic and can be used to characterize any MIN for known topology and traffic patterns. We confirm our results through simulations carried out using ns-2

This paper evaluates the energy efficiency of the IEEE 802.11 distributed coordinated function (DCF) over bursty error channel. Most existing works in the literature assume ideal channel or a simple uniform error model. These existing analysis can hardly capture the impact of fading on the energy efficiency accurately. In this paper, a Markov channel model is adopted, and the impact of bursty channel errors is characterized to obtain the energy efficiency of DCF. In our analysis, many factors that affect the energy efficiency of 802.11 DCF have been considered. Simulations in ns-2 are also performed to validate the analysis

Routing protocols for mobile ad hoc networks (MANETs) have assumed that all nodes voluntarily participate in forwarding others' packets. This was a reasonable assumption because all nodes in previous MANETs belonged to a single authority. In the near future, however, a MANET may consist of nodes that belong to multiple organizations since various civilian applications are expected to appear. In this situation, mobile nodes may deliberately avoid packet forwarding to save their own energy, resulting in network partition. To make nodes volunteer in packet forwarding we suggest a payment scheme called protocol-independent fairness algorithm (PIFA). In this type of schemes, nodes need credits to transmit their own packets, and this credit can be earned by forwarding others' packets. PIFA can be utilized irrespective of the type of basic routing protocols, while previous methods are compatible only with source routing like DSR. Simulation results show that PIFA can prevent network partition and network performance degradation due to selfish nodes by inducing them to participate in forwarding packets.

Most existing solutions to group security in mobile ad hoc networks (MANETs) rely on a multicast core based tree (CBT) for key distribution. Such solutions, although suitable for systems with low mobility and static characteristics, are highly unsuitable for dynamic and sparse groups with changing neighborhoods. Also, tree based solutions are prone to a man-in-the-middle attack which might lead to network partitioning. Moreover, a group controller is required to control the key generation process. In this paper, we propose an entirely decentralized key generation mechanism. Using our approach, keys can be established between group members with absolutely no prior communication, as long as the group members are known. The solution relies on threshold cryptography and introduces a novel concept of node-group-key (NGK) mapping. Analytical and simulation results show appreciable performance enhancements.

In this paper we propose a method for data compression and its subsequent regeneration using a polynomial regression technique. We approximate data received over the considered area by fitting it to a function and communicate this by passing only the coefficients that describe the function. In this paper, we extend our previous algorithm TREG to consider non-complete aggregation trees. The proposed algorithm DUMMYREG is run at each parent node and uses information present in the existing child to construct a complete binary tree. In addition to obtaining values in regions devoid of sensor nodes and reducing communication overhead, this new approach further reduces the error when the readings are regenerated at the sink. Results reveal that for a network density of 0.0025 and a complete binary tree of depth 4, the absolute error is 6%. For a non-complete binary tree, TREG returns an error of 18% while this is reduced to 12% when DUMMYREG is used

Wireless sensor networks have enabled information gathering from a large geographical region and present unprecedented opportunities for a broad spectrum of monitoring applications. In this paper, we propose a data-centric storage scheme to determine a distribution of attributes over a large-scale sensor network such that the cost of retrieving data is minimized. We analytically determine the conditions under which the proposed architecture is beneficial and present simulation results to demonstrate the same. To the best of our knowledge, this is the first attempt to determine an allocation of attributes over a sensor network based on the correlations between attributes

Key establishment and management is the core of security protocols for wireless sensor networks deployed in the hostile environment. Due to the strict resource constraints, traditional asymmetric key cryptosystems, such as public/private key based schemes, are infeasible for large-scale wireless sensor networks. Research shows that pre-distributing pairwise keys into wireless sensor nodes before deployment is a practical way to deal with the key establishment problem. Existing random key based key pre-distribution schemes only provide probabilistic connectivity of the network and some level of network resilience. In this paper, we propose an efficient pairwise key establishment and management scheme to achieve both network connectivity and resilience for static wireless sensor networks. Compared with current key pre-distribution schemes, our scheme supports large network size, and has lower communication and computational overhead

Multiple beam antennas can receive (or transmit) data on multiple beams simultaneously. The aim of this paper is to show the limitations of using IEEE 802.11 distributed coordination function (DCF) based schemes for medium access control (MAC) in such antennas. We provide four different variants of IEEE 802.11 DCF based on-demand protocols to study this phenomenon. Our simulation results and analyses emphasize the need to develop a novel MAC protocol to fully exploit the capabilities of multiple beam antennas. We further provide some embryonic guidelines for the development of such a protocol

This paper proposes a new heterogeneous multi-hop cellular IP (MCIP) network that integrates multi-hop communication with cellular IP. MCIP increases the coverage of the wireless network and improves the network robustness against adverse propagation phenomena by supporting communication in dead zones and areas with poor radio coverage. MCIP includes three components: location management, connection management and route reconfiguration. Location management is responsible for maintaining the location information for mobile stations (MSs) in a local domain. Connection management establishes an initial path for data transmission and a route reconfiguration mechanism is proposed to take advantage of various multi-hop connection alternatives available based on terminal interfaces, network accessibility and topology. Our simulation results show that MCIP performs well in networks of various sizes.

A growing need for ubiquitous connectivity has motivated the integration of various wireless technologies such as cellular systems, WLANs and MANETs. In this paper we introduce the integrated routing protocol (IRP) that exploits topology information obtained by cellular base stations and WLAN access points in the route discovery and maintenance in a heterogeneous wireless access network. IRP also provides connectivity to the cellular network and/or WLAN hotspots through the multi-hop routing by allowing out of coverage users to maintain routes to Gateway Nodes (GN). We provide a simulation study of IRP with two different link quality metrics, number of hops and a new integrated metric based on the expected transmission time (ETT). Our results show that IRP improves the network coverage and capacity and allows connectivity alternatives that are not supported by other integrated solutions.

Future wireless networks are expected to integrate heterogeneous devices equipped with multiple radios and different characteristics. Therefore, it is important to understand how these heterogeneous radios can affect connectivity and overall multi-hop network performance. In this paper, we study the connectivity of a heterogeneous ad hoc network. We consider two types of nodes: nodes equipped with a single communication interface with communication range r, and dual-mode (DM) nodes, equipped with two communication interfaces with two different communication ranges r and r/sub f/, respectively, where r/sub f/>r. We assume the radios in the DM nodes operate in two different channels. We provide a theoretical analysis of connectivity in a linear network and we present simulation results for the two-dimensional case that show the impact of DM nodes on connectivity, broadcast latency and robustness in static scenarios.

This paper introduces a distributed channel assignment scheme (DCA) for wireless sensor networks. Recent developments in sensor technology, as seen in Berkeley's Mica2 Mote, Rockwell's WINS nodes and the IEEE 802.15.4 Zigbee, have enabled support for single-transceiver, multi-channel communication. DCA exploits this capability by assigning optimally minimum channels in a distributed manner in order to make subsequent communication free from both primary and secondary interference. The main contribution of this paper is solving the channel assignment problem, also named as the 2-hop coloring problem, in which repetition of colors occurs only if the nodes are separated by more than 2 hops. Our work achieves legal coloring under energy constrained conditions for sensor networks and significant performance improvements are shown when compared with similar existing schemes. Finally, we validate our approach through extensive analysis and simulation results.

Historically, a large number of small and cheaper sensors are deployed to form a sensor network. This paper provides rationale behind using an aggregate logical sensor unit (ALSU) as a building block in a Wireless Sensory Information network (WSIN). In this architecture, a single ALSU is composed of many off-the-shelf sensor nodes in the manner similar to the Beowulf cluster concept. The highly capable, cost effective and flexible ALSUs built in this manner from several smaller physical sensor nodes, would enable high computation power and built-in reliability for sensor applications. The objective of this paper is to provide an alternative where energy and computation is not a limiting factor in order to achieve the operational objectives of WSIN applications. This paper highlights critical issues that need to be addressed in developing a framework where each ALSU could have the capability to perform required operations as dictated by an underlying application

Abstract: In this paper we propose a Directional Routing Protocol (DRP) for MANETs. DRP is an on-demand directional routing protocol which assumes a cross layer interaction between routing and MAC layer. The main features of DRP include an efficient route discovery mechanism, establishment and maintenance of directional routing and directional neighbor tables (DRT and DNT respectively), and novel directional route recovery mechanisms. We have implemented DRP on top of an existing MAC protocol for directional antennas and have compared its performance with the popular dynamic source routing (DSR) protocol over both omni-directional and directional antenna models. Preliminary simulation results are found to be very promising.

Wireless sensor networks form an emerging technology that can significantly improve the quality of spatio-temporal data monitoring because of their untethered operation and potential for large scale deployment. We define a communication architecture that supports distributed query processing to evaluate spatio-temporal queries within the network. We represent these queries by query trees and distribute query operators to appropriate sensor nodes. As operator execution demands high computation capability, we propose the use of a heterogenous sensor network where query operators are assigned to sparsely deployed resource-rich nodes within a dense network of low power sensor nodes. We design an adaptive, decentralized, low communication overhead algorithm to determine an operator placement on the resource-rich nodes in the network to minimize cost of transmitting data along a routing tree constructed to retrieve data continuously at the sink from a set of spatially distributed geographical regions. To the best of our knowledge, this is the first attempt to build an energy aware routing infrastructure to enable in-network processing of spatio-temporal queries.

Authentication delays of the order of 1 s are a severe bottleneck in maintaining QoS guarantees over WLANs. Pre-authentication schemes have been proposed to reduce these delays. However, most of these schemes suffer from an increased message overhead on the network. The primary reason for this is that mobility modeling is not on a per-user basis. We exploit the notion of predictability in user mobility patterns and propose a set of novel proactive key distribution algorithms to achieve low latencies while minimising the message overhead in the network. We further provide a model to measure the responsiveness of our schemes to randomness in user motion. Simulation results indicate up to 60% message reduction in comparison to existing schemes, while maintaining similar latency values.

The paper introduces an analytical model to investigate the energy efficiency of the IEEE 802.11 distributed coordinated function (DCF). Many factors, such as the number of contending nodes, packet size, contention window, packet transmission collision probability and channel condition, that affect the energy efficiency of 802.11 DCF have been considered. We determine the packet transmission probability by a method simpler than the existing Markov chain model. The paper identifies the tradeoff in choosing packet size to optimize the energy efficiency of DCF in error-prone environments. The effects of contention window and packet size on the energy efficiency are obtained for both DCF basic mode and DCF with four-way handshaking. It is shown that under error-prone environments, optimal packet size can improve more on the energy efficiency than optimal contention window. Combining both optimal contention window and optimal packet size can achieve the maximum optimization. To validate our analytical results, we have done extensive simulations, and they seem to match very well with the presented analytical results.

Due to the high node density and stringent constraints on the energy consumption in wireless sensor networks, designing an energy efficient flooding scheme with high reachability is critical for the operation and the lifetime of sensor networks. Many existing flooding approaches address the needs of general ad hoc networks. In contrast, this paper presents a cross-layer approach tailored specifically to the needs of sensor networks. Without assuming location awareness, a novel MAC layer access-deferring scheme, based on the received signal power, is proposed to reduce the collision possibility and broadcast redundancy. Local neighborhood information is piggybacked onto the broadcast packet, and exploited to enhance the reachability. Simulation results show that compared with probabilistic flooding, this scheme has good performance in terms of reachability, average delay and energy efficiency. Moreover, we examine how the range estimation error and neighborhood information inaccuracy introduced by the fading environment affects the performance of our flooding scheme.

In this paper, we propose and analyze two different handoff schemes in integrated wireless mobile networks. The channels in each cell are divided into two parts and pre-allocated for real-time and nonreal-time services. To increase the channel utilization while keeping the quality of service (QoS) of each type for traffic, one type of service is allowed to borrow channels from the other under certain constraints. Depending on whether or not nonreal-time service calls can be interrupted, we have two channel borrowing schemes: nonpreemptive and preemptive. We use a system model defined by a multidimensional Markov chain and compute the performance in terms of blocking probability of originating calls, forced termination probability of real-time service calls, and average transmission delay of nonreal-time service calls. The simulation results are observed to match closely with the analytical model. The preemptive borrowing scheme is observed to perform better than the nonpreemptive scheme at the cost of increased handoff for nonreal-time service calls. The impact of the long-term dependence of data traffic on system performance is also discussed.

Abstract In this paper, we evaluate the impact of transmission error rate on the contention and the system throughput in IEEE 802.11 DCF. We identify the trade‐off between the desire to reduce the ratio of overhead in the data packet by adopting larger packet size and the need to reduce the packet error rate by using smaller packet length. Meanwhile, we provide a novel approach to model the different channel conditions incurred by different nodes. This work has applications in performance optimization by establishing trade‐offs between transmission error rate and transmission power, modulation, coding scheme, packet size. Our results substantiate the intuition that in a contention‐based system like 802.11 DCF, the channel variation of any single node in the system not only impacts the throughput of itself, but also affects the throughput of other nodes and the system throughput. Our work shows that to achieve maximum optimization of the throughput, the channel conditions of all the nodes in the system have to be taken into account. Otherwise the optimization is suboptimal. Copyright © 2005 John Wiley & Sons, Ltd.

In code-division multiple-access (CDMA) systems, the number of users that each cell can support is limited by the total received power or interference received at each base station and can vary with time. The total received power can be used as an indicator of traffic load in call admission control. In this paper, we develop an algorithm to estimate the updated total received power due to a new call based on the current measure of the received power. Using this algorithm, we propose a call admission control (CAC) scheme with the purpose of maximizing the resource utilization and guaranteeing a minimum amount of resources for each type of traffic when congestion occurs. We model the system by a multi-dimensional Markov chain to evaluate the system performance.

It is against our intuition that being selfish sometimes can be beneficial to both oneself and others. In a mobile ad hoc network (MANET), we show potential use of this concept by categorizing mobile hosts into normal nodes and selfish nodes. Normal nodes forward packets for other nodes while selfish nodes do not. The advantage of using selfish nodes is that the total rebroadcast traffic during flooding based route discovery can be reduced. The disadvantage, in theory, is that we may miss the optimal route and suffer from a low delivery rate. In this paper, we propose a probabilistic approach to set up a proper number of selfish nodes. Using a combination of gossiping and dominating set, we can reduce the route discovery cost by minimizing the number of rebroadcasts, while achieving higher delivery rate due to the reduction of rebroadcast traffic, thereby reducing the number of collisions. We compare our approach with AODV in terms of several metrics, including average number of rebroadcasts, average number of packet collisions, end-to-end delay, and throughput. Simulation results show that our approach outperforms the AODV protocol in most cases.

In this paper, we propose a new scheme for small group multicast in mobile ad hoc networks (MANETs) named extended explicit multicast (E/sup 2/M), which is built on top of Xcast and introduces mechanisms to make it scalable with number of group members for a given multicast session. E/sup 2/M is based on the novel concept of dynamic selection of Xcast forwarder (XF) between a source and its potential destinations. The XF selection is carried out based on group membership and the processing overhead involved in supporting the Xcast procedure at a given node. If the number of members in a given session is small, E/sup 2/M works just like the basic Xcast scheme with no intermediate XFs. As group membership increases, the overhead involved in supporting an Xcast session also increases. Therefore, to reduce the overhead and provide scalability, in E/sup 2/M nodes may dynamically decide to become a XF. This scheme, which can work with few E/sup 2/M aware nodes in the network, provides the transparency of stateless multicast, reduces header processing overhead and makes Xcast scalable with the number of group members.

In mobile ad hoc networks (MANET), some mobile hosts may be outside the range of the source node. In order to deliver the message to those hosts, intermediate nodes should relay the packets for them. Due to the node mobility, we cannot have a fixed group of mobile nodes perform the task of packet relaying. In this paper we propose a routing protocol based on the preassigned probability model. In this protocol, a mobile host probabilistically sends the relay packets (rebroadcasts) according to its neighborhood information. We exploit the "HELLO" message exchanges between immediate neighbors to obtain the neighborhood information. Using this method, we can reduce routing cost by minimizing the number of rebroadcasts in route discovery period without a significant impact on the network connectivity. Moreover, the chance of contention and collision among neighboring nodes is also reduced. As a result, the overall network performance is improved, while higher goodput and lower energy consumption is achieved. Our approach categorizes mobile hosts into four groups according to their neighborhood information. For each group of nodes, we assign a specified value of rebroadcasting probability. The mobile hosts with more neighbors are given higher rebroadcasting probability, while the mobile hosts with fewer neighbors have a lower rebroadcasting probability. Analytical results show that our approach outperforms the AODV protocol.

Bluetooth is a promising wireless technology aiming at supporting electronic devices to be instantly interconnected into short-range ad hoc networks. The Bluetooth medium access control protocol is based on the master/slave concept wherein any communication between slave devices has to go through the master. While this model is simple, it incurs longer delay between any two slave devices due to the use of non-optimal packet forwarding scheme and the use of double the bandwidth at the master. Moreover, if more than two devices want to communicate as a group, this can only be achieved by either multiple unicast transmissions or a piconet-wide broadcast from the master. To handle these issues efficiently, we propose a novel combination of dynamic slot assignment (DSA) and piconet partitioning. With DSA, the piconet master dynamically assigns slots to slaves so as to allow them to communicate directly with each other without any intervention from the master. Such proposed communication architecture provides for quality of service (QoS) requests, admission control, and multi-device conversation by which a multicast-like communication is feasible within a piconet. To widen the scope of DSA, we propose QoS-driven enhanced DSA (EDSA) where dynamic piconet partitioning and scatternet support comes into picture. Devices are grouped in piconets according to their connection endpoints in EDSA, enabling it to be employed over a scatternet. We have performed extensive simulations and observe that these schemes drastically enhance Bluetooth performance in terms of delay and throughput, while significantly reducing network power consumption.

In wireless ad hoc networks, frequent topology changes and the absence of any centralized control make the networks vulnerable to many security attacks not present in a traditional wired network. Existing routing protocols offer little or no security to address these vulnerabilities. In this paper, we describe a security scheme based on the working of cluster based routing protocol (CBRP). Using threshold cryptography we eliminate the use of a centralized certification authority to distribute the process of certification among the nodes of the network. We make use of a combination of public key and symmetric key cryptography for authentication and exchange of data. This approach can as well be easily extended to other hierarchical routing protocols.

Energy efficiency has been a bottleneck in the wireless local area network (LAN) based communication of portable wireless devices. This paper introduces an analytical model to investigate the energy efficiency of 802.11 distributed coordinated function (DCF) under both ideal channel and error prone environment. The two major factors contributing to the extra energy consumption in 802.11 DCF: contention and transmission errors, are analyzed thoroughly. Based on the analysis, a scheme of choosing optimal minimum contention window size to optimize the energy consumption under both ideal and error prone environment is proposed. Our extensive simulation results are observed to match very well with the analytical results, which indicate that the analytical model is accurate.

In our paper, we investigate some MAC layer issues associated with the use of multiple-beam smart antennas at nodes in a distributed wireless ad-hoc network. We propose a transmitter-initiated on-demand MAC protocol that exploits the spatial parallelism in the transmission of packets at a node. We devise two MAC scheduling strategies in the one-hop neighborhood of a node, largest edge first (LEF) and largest degree node first (LDNF), that allow spatial parallelism to be exploited in the transmission as well as reception of packets. Our simulation results indicate that significant gain may be achieved through our scheduling strategies in a one-hop traffic bottleneck.

In IEEE 802.11 based mobile ad hoc networks (MANET) multicast packets are generally forwarded as one hop broadcast; mainly to reach all the multicast members in the neighborhood in a single transmission. Because of the broadcast property of the forwarding, packets suffer from increased instances of the hidden terminal problem. Mobility of nodes makes things more difficult, and unlike unicast transmissions where MAC can detect the movement of a nexthop by making several retries, it is not possible in case of multicast forwarding. To address these issues, we propose a multicast aware MAC protocol (MMP) for MANET. The basic objective of MMP is to provide a MAC layer support for multicast traffic. This is done by attaching an extended multicast header (EMH) by the multicast agent, which provides the address of the nexthop nodes that are supposed to receive the multicast packet. The MAC layer in MMP uses the EMH field to support an ACK based data delivery. After sending the data packet, the transmitter waits for the ACK from each of its destinations in a strictly sequential order. A retransmission of the multicast packet is performed only if the ACK from any of the nodes in EMH is missing. We compare MMP with IEEE 802.11 and results show that MMP substantially improves the performance of multicast packet delivery in MANET without creating much MAC overhead. In addition, MMP provides a better mechanism to detect the movement of its nexthop members.

Many emerging mobile wireless applications use symmetric keys for secure multicast communication. This key has to be changed every time a user decides to leave or join the network. We introduce a novel hierarchical security framework for mobile ad hoc multicast networks in which data encryption is done using a symmetric key and key establishment using symmetric 'level' keys and asymmetric node keys. Our primary contention is that the tree formation process should be integrated with the key exchange process and should not be treated as an add-on. Our scheme effectively handles the impact of mobility on key establishment while minimizing the number of messages to be exchanged.

With the popularity of the IEEE 802.11 based wireless network, it has become increasingly important to analyze the performance of the IEEE 802.11 protocol accurately. Throughput and delay are key measures, reflecting the performance of a wireless network. In this paper, we analyze the performance of the IEEE 802.11 distributed coordination function (DCF) in the saturated traffic condition, and consider the effects of packet size, the number of contention nodes, transmission collision probability and channel conditions. Under this analytical framework, we evaluate the impact of error-prone channel on unsuccessful transmission probability and its impact on the performance. A trade-off exists between the desire to reduce the ratio of overhead in the data packet by adopting larger packet size, and the need to reduce the packet error rate in the error-prone environment by using smaller packet length. An optimal packet size can be derived to maximize the throughput of the IEEE 802.11 DCF under various channel conditions and network configurations. To validate our analytical results, we have done extensive simulations, and the simulation results are observed to match very well with the analytical results.

Optimal scheduling of parallel tasks with some precedence relationship, onto a parallel machine is known to be NP-complete. The complexity of the problem increases when task scheduling is to be done in a heterogeneous environment, where the processors in the network may not be identical and take different amounts of time to execute the same task. We introduce a task duplication-based scheduling algorithm for network of heterogeneous systems (TANH), with complexity O(V/sup 2/), which provides optimal results for applications represented by directed acyclic graphs (DAGs), provided a simple set of conditions on task computation and network communication time could be satisfied. The performance of the algorithm is illustrated by comparing the scheduling time with an existing "best imaginary level scheduling (BIL)" scheme for heterogeneous systems. The scalability for a higher or lower number of processors, as per their availability is also discussed. We have shown to provide substantial improvement over existing work on the task duplication-based scheduling algorithm (TDS).

We consider the medium access control (MAC) protocol design for nodes in a wireless LAN that use a wide-azimuth switched beam smart antenna system comprised of a multiple beam antenna array. The one-hop performance of carrier sense multiple access (CSMA) as well as slotted aloha for such a system is presented analytically and through simulation. The problem of synchronization of multiple beams in CSMA is investigated in our analysis. Our results show that, under heavy offered load conditions, CSMA is a good choice with nodes that have multiple-beam smart antennas, despite the performance loss due to the beam synchronization, providing a stable throughput that approaches unity and is invariant to fluctuations in the offered load. Slotted Aloha, on the other hand, is capable of higher peak throughput in a narrow range of offered loads as more switched beams are employed, but performance drastically reduces beyond optimum offered loads. We also introduce a method, expanded receive rule (ERR), whereby the tight synchronization among different beams of a receiver node in CSMA is relaxed, which is observed to provide better throughput. Finally, we also present performance results for a 4-way-handshake-type carrier sense mechanism using multiple beam antennas.

Abstract The IEEE 802.11e working group aims to enhance the current 802.11 medium access control (MAC) to support integrated data and voice (or video) communications. Till now, a draft of the IEEE 802.11e enhanced distributed coordination function (EDCF) has been proposed. In the literature, there is very limited analysis about EDCF since it is a new protocol, and most related work are only confined to simulation or saturation state. In this paper, we evaluate the performance of EDCF by dividing the traffic into two groups, namely real‐time packets and non‐real‐time packets, and use an analytical model to quantify the performance of both IFS priority and contention window (CW) priority in the EDCF. In our analysis, we assume that the traffic arrival is a Poisson process. We provide a queue model for EDCF. Since there are multiple stations contending for one channel in the system, the queue model for EDCF cannot be a regular M/G/1 model. We redefine the service time and the waiting time so that we can still use M/G/1 model in the analysis. To validate the accuracy of our analytical results, we have done extensive simulations and we observed that EDCF does provide service differentiation between different traffic categories. But due to the inherent contention characteristic of carrier sense multiple access with collision avoidance (CSMA/CA) MAC protocol, the delay cannot be guaranteed, even for the highest priority traffic. A lot more work needs to be done for the MAC protocol to effectively support service differentiation in the future. Copyright © 2004 John Wiley & Sons, Ltd.

Bluetooth is a radio technology for wireless personal area networking (WPAN) operating in the 2.4 GHz ISM frequency band. The Bluetooth MAC protocol is based on the master/slave concept wherein any communication between slave devices has to go through the master. While this model provides for simplicity, it incurs longer delay between any two slave devices due to far from optimal packet forwarding, the use of double the bandwidth, and also it wastes additional energy at the master. Moreover, if more than two devices want to communicate as a group, this can only be achieved by either multiple unicast transmissions or a piconet-wide broadcast, clearly resulting in inefficiency. We propose a novel dynamic slot assignment (DSA) scheme whereby the master device dynamically assigns slots to slaves so as to allow them to communicate directly with each other without master intervention. This proposed mechanism also provides for quality of service (QoS) requests, and multi-device conversation by which a multicast-like communication is implemented within a piconet. Through extensive simulation, we observe that this mechanism greatly enhances Bluetooth performance in terms of delay and throughput while incurring extremely low overhead.

Security in multicast is a necessity for applications that require a group of members to transmit data among themselves. Non-members should be precluded from receiving and sending message to the group. The issue of efficient and scalable key management in such a multicast environment is difficult, since multicast usually involves a large number of hosts. A single change in the group membership often affects many hosts. IOLUS is one existing framework having a central group security controller (GSC) with trusted group security intermediaries (GSI) connected to it. GSIs handle the multicast members. But, IOLUS involves a large overhead whenever a member connected to the GSI leaves the group, since the GSI has to update the sub-group key for all the remaining members. Mobility increases the overhead. In this paper, we introduce micro-grouped IOLUS (M-IOLUS), a novel concept of dynamic micro-groups maintained by the GSI. A 'micro-key' is used for the transmission of control information. This drastically reduces the control overhead incurred. We have performed extensive simulations varying the different parameters involved and observed a considerable reduction in overhead.

Bluetooth is a short-range wireless technology designed to connect various low power, resource constrained devices such as cameras, cell-phones, laptops, handhelds, etc. Devices form autonomous ad hoc networks of up to 8 active devices, referred to as piconets. Piconets may be inter-connected by one or more bridge devices to form a scatternet. The Bluetooth specification is very clear about piconet formation, maintenance, operation and termination, but only mentions the concept of a scatternet. The bridges are the most important part of the scatternet as they bear the responsibility of a switch -relaying traffic from one piconet to another. Generally, the implicit assumption made is that the bridge already exists or that the bridge can be formed in some manner. However, the issues surrounding the bridge are complex and involve the masters of more than one piconet. In this paper we propose a framework - the bridge establishment, adaptation and maintenance (BEAM) - for bridge formation, maintenance, negotiation and termination. We have enunciated the mechanisms by which a node may be made a bridge and how it may be used to add or replace subsequent bridges. The framework has been designed to be flexible so that, it may be used by any of the scatternet formation or performance improvement algorithms. It is a logical step absolutely necessary for real world Bluetooth scatternet working and is simply an enabling mechanism to be used in conjunction with other protocols. It is presented in the form of a design specification or a protocol that may be customized by different implementers, and yet maintain a very high degree of interoperability.

Bluetooth is a radio technology for wireless personal area networking (WPAN) operating in the 2.4 GHz ISM frequency band. We introduce a novel Bluetooth architecture (BlueStar) whereby selected Bluetooth devices, called Bluetooth wireless gateways (BWGs), are also IEEE 802.11 enabled so that these BWGs could serve as ingress/egress points to/from the IEEE 802.11 wireless network and thus provide access to WANs such as the Internet. We propose mitigating interference between Bluetooth and IEEE 802.11 by employing a hybrid approach of adaptive frequency hopping (AFH) and Bluetooth carrier sense (BCS) of the channels. AFH labels channels as "bad" or "good", and Bluetooth devices only access those channels in the "good" state, whereas BCS is used to avoid collision by sensing the channel prior to any transmission. By combining AFH and BCS, we minimize the effect of the worst-case interference scenario wherein both a Bluetooth and an IEEE 802.11 interface are colocated in a single device. BlueStar enables Bluetooth devices, in either a piconet or a scatternet, to access the WAN through the BWG without the need for any fixed Bluetooth access points, while utilizing the widely deployed base of IEEE 802.11 networks. We define the protocol stack employed by BlueStar as well as indicate how BWGs efficiently manage their capacity allocation through different systems. We also mathematically derive an upper bound on the number of BWGs needed in a scatternet so that uninterrupted access to all Bluetooth devices could be provided.

Wireless sensor networks consist of large number of low power devices equipped with RF links for communication that have several military, civil and environmental monitoring applications. The energy constraints due to limited battery power present numerous design challenges. In this paper we propose an energy efficient, cluster based framework for collaboration among nodes in a region for reducing the redundancy in reporting events. Collaboration is done among the exposed nodes using a localized and deterministic schedule based on TDMA/FDMA MAC. A novel, three phase collaboration scheme is presented to exchange messages for determining the local maximum of the confidence measure in the two hop cluster neighborhood of the event. This local maximum generates the response for the event, thereby reducing the redundant reporting of the event. Through extensive simulations we have shown that there is a significant reduction in the overall network traffic thereby, saving energy at the nodes responsible for originating response traffic and also at nodes, which handle the route-through traffic.

The seamless communication of data and voice over short-range, point-to-multipoint wireless links between mobile and/or stationary devices is becoming a reality by newly introduced Bluetooth radio technology for Wireless Personal Area Networking, which can support only up to 1 Mbps of nominal bandwidth. It is based on a master-slave model where double the resources are allocated for any slave-to-slave communication via the master. In addition, it does not have any mechanism to serve demands exceeding this capacity. In this paper, we employ the concepts of Internet Traffic Engineering to maximize the channel utilization and optimize the performance of QoS-sensitive applications, with minimum possible interference. We introduce two novel techniques of Pseudo Role Switching (PRS) and Pseudo PaRtitioning (PPR) to alleviate bottlenecks in the existing schemes in a proactive manner. We propose a two-layered approach wherein we first achieve the maximum possible throughput in existing network using PRS technique, and then dynamically partition piconets using the PPR to satisfy the increased demands. It has been observed that combining both PRS and PPR drastically enhances the aggregate network throughput while minimizing the interference. Through extensive performance evaluations, we show that our proposed schemes reduce up to 50 % of the network overhead and increase the overall throughput by 200%.

Today's wireless sensors act as information agents, our eyes and ears, for all types of applications, especially in inaccessible regions. But these sensors are resource-constrained devices; the key challenges remain in exploiting their limited time-life. A crucial factor to achieve this is to develop appropriate mobility models that would assure high information coverage of the desired deployed region within the area. We propose a biologically inspired mobility model to direct sensors' movement towards the target area. We show the benefits acquired in terms of data coverage and efficient resource-utilization.

We propose an analytical model for integrated real-time and non-real-time services in a wireless mobile network with priority reservation and preemptive priority handoff schemes. We categorize the service calls into four different types, namely, real-time and non-real-time service originating calls, and real-time and non real-time handoff service request calls. Accordingly, the channels in each cell are divided into three parts: one is for real-time service calls only, the second is for non-real-time service calls only, and the last one is for overflow of handoff requests that cannot be served in the first two parts. In the third group, several channels are reserved exclusively for real-time service handoffs so that higher priority can be given to them. In addition, a realtime service handoff request has the right to preempt non-real-time service in the preemptive priority handoff scheme if no free channels are available, while the interrupted non-real-time service call returns to its handoff request queue. The system is modeled using a multidimensional Markov chain and a numerical analysis is presented to estimate blocking probabilities of originating calls, forced termination probability, and average transmission delay. This scheme is also simulated under different call holding time and cell dwell time distributions. It is observed that the simulation results closely match the analytical model. Our scheme significantly reduces the forced termination probability of real-time service calls. The probability of packet loss of non-real-time transmission is shown to be negligibly small, as a non-real-time service handoff request in waiting can be transferred from the queue of the current base station to another one.

The emergence of Bluetooth as a default radio interface has allowed handheld electronic devices to be instantly interconnected as ad hoc networks. These short-range ad hoc wireless networks, called piconets, operate in the unlicensed 2.4-GHz ISM (Industrial-Scientific-Medical) band where devices may be used to configure single or overlapping piconets, known as scatternet. As all piconets operate in the same frequency band, the presence of multiple piconets in the vicinity may create interference on signal reception. This paper employs a signal capture model to study the piconet MAC performance, taking inter-piconet interference into consideration. This model leads to several important mathematical relationships for Bluetooth networks, including successful packet transmission probability. Furthermore, our model and anticipated throughput are validated using extensive simulation. These results indicate that Bluetooth throughput is affected by multiple piconet interference. Definitely, our model can be considered to provide a solid foundation for future interference aware Bluetooth protocols.

The emergence of Bluetooth as a defacto radio interface has allowed handheld electronic devices to be instantly interconnected as ad hoc networks. Recent studies show that since Bluetooth operates in the unlicensed 2.45 GHz frequency band, the presence of multiple piconets in the vicinity creates intermittent interference on signal reception which, in turn, degrades the overall throughput of the network. Another kind of interference, called as persistent interference, is the one generated by IEEE 802.11 enabled devices as they use the same frequency band as Bluetooth, and thus may lead to significant performance degradation. In order to cope up with both of these interference sources, this paper proposes an interference aware Bluetooth segmentation algorithm (IBLUES), where Bluetooth packet types are selected depending on the packet success probability, which is calculated based on the interference generated both by multiple piconets, as well as by IEEE 802.11 devices. Among other things, we show that when the number of bridge nodes are larger than five the propagation delay between piconets increases rapidly. We have also observed a drastic overhead in the current Bluetooth piconet switching procedure and conclude that future enhancements to this procedure are crucial to efficiency of Bluetooth-based ad hoc networking.

Previous proposals to provide multicasting over mobile IP focus mainly on recipient mobility and little attention has been given to the case when the mobile host (MH) is also the source. In this paper, we have attempted to address the case when the MH is a source as well as a recipient of a given multicast session and more than one source is participating in the session. The basic essence of the problem is that the effect of receiver movement on the multicast tree is local while it may be global for source movement and it may affect the complete multicast delivery tree. We have used a MH initiated approach for multicast handoff and introduced a unified solution and made the effect of the MH movement local, irrespective of whether it is working as a source or a recipient of a multicast group. We examine and compare our proposed approach to existing approaches by simulating under various traffic environments and we observe an improved performance.

Most studies on TCP over multi-hop wireless ad hoc networks have only addressed the issue of performance degradation due to temporarily broken routes, which results in TCP inability to distinguish between losses due to link failures or congestion. This problem tends to become more serious as network mobility increases. We tackle the equally important capture problem to which there has been little or no solution, and is present mostly in static and low mobility multihop wireless networks. This is a result of the interplay between the MAC layer and TCP backoff policies, which causes nodes to unfairly capture the wireless shared medium, hence preventing neighboring nodes to access the channel. This has been shown to have major negative effects on TCP performance comparable to the impact of mobility. We propose a novel algorithm, called COPAS (COntention-based PAth Selection), which incorporates two mechanisms to enhance TCP performance by avoiding capture conditions. First, it uses disjoint forward (sender to receiver for TCP data) and reverse (receiver to sender for TCP ACKs) paths in order to minimize the conflicts of TCP data and ACK packets. Second, COPAS employs a dynamic contention-balancing scheme where it continuously monitors and changes forward and reverse paths according to the level of MAC layer contention, hence minimizing the likelihood of capture. Through extensive simulation, COPAS is shown to improve TCP throughput by up to 90% while keeping routing overhead low.

Recently, MAC protocols using directional antennas for wireless ad hoc networks that are based on and similar to IEEE 802.11 type WLAN have been proposed. These protocols, however, are unable to attain substantial performance improvements because they do not enable the nodes to perform multiple simultaneous transmissions/receptions. In this paper, we propose a MAC layer protocol that exploits space division multiple access, thus using the property of directional reception to receive more than one packet from spatially separated transmitter nodes (equipped with smart antenna systems). Our simulation results show that drastic throughput improvements may be achieved through this scheme.

The use of directional antennas in cellular wireless networks offers many advantages such as range extension, reduced interference for signal detection and improved throughput. MAC protocols using directional antennas for wireless ad hoc networks that are based on and similar to IEEE 802.11 type WLANs have been proposed. We explore 'multiplexing in space' with directional antennas to enhance the total throughput at a bottleneck node in the network. We develop an access protocol for antenna systems that can transmit to multiple destinations simultaneously (and possibly receive from multiple sources as well). Some issues enabling multiple access in space for ad hoc network nodes are discussed. Our simulation results show that the current 802.11 MAC scheme using omnidirectional antennas for channel access fairs very poorly as the bandwidth demand increases. In contrast, we see substantial improvement when spatial multiplexing is employed.

This paper presents an efficient algorithm for near optimal channel assignment when different types of services are to be provided in the next generation integrated wireless and mobile networks. We specifically propose a preemptive priority scheme for an integrated wireless and mobile network by first dividing channels into three independent groups and classifying traffic into four different types. The proposed system is modeled by Markov chain model, and then such a model is used to obtain a set of relations that correlate performances with various system parameters. We have analytically determined the minimal number of channels required for each type of traffic that can satisfy a desired level of QoS (Quality of Service) requirements. We also investigate the impact of load ratio for different types of traffic on channel assignment. Finally, we discuss some limitations of our approach and indicate possible future work. We believe that the partitioning scheme proposed in this paper can become a starting point for analysis of future integrated wireless and mobile networks.

Bluetooth is a promising wireless technology aiming at supporting electronic devices to be instantly interconnected into short-range ad hoc networks. Previous studies show that since Bluetooth operates in the unlicensed 2.45 GHz frequency band, the presence of multiple piconets in the vicinity creates intermittent interference on signal reception which, in turn, degrades the overall throughput of the network. In order to cope up with this interference source, this paper proposes a sophisticated interference aware Bluetooth segmentation algorithm (IBLUES), where Bluetooth packet types are selected depending on the packet success probability, which is calculated based on the interference generated by multiple piconets. Among other things, we show that when the number of bridge nodes are larger than five the propagation delay between piconets increases rapidly. We have also observed a drastic overhead in the current Bluetooth piconet switching procedure and conclude that future enhancements to this procedure are crucial to efficiency of Bluetooth-based ad hoc networking.

In this paper we present a novel multilevel graph partitioning algorithm, KACE, which uses knowledge about the domain and employs several graph transformation techniques. Both functional and structural parallelism in the sequential code are explored to improve the quality of parallel tasks. Statistical information about communication times between nodes as a function of message size and/or other factors are used to have a better estimate of balancing factors, code replication, and synchronization penalties. This enables us to use a task cohesion algorithm to obtain a coarse version of the partitioned graph. Many of KACE's parameters are shown to have definite impact on the parallelized program code.

Wireless sensor networks are a new class of ad hoc networks that will find increasing deployment in coming years, as they enable reliable monitoring and analysis of unfamiliar and untested environments. The advances in technology have made it possible to have extremely small, low powered sensor devices equipped with programmable computing, multiple parameter sensing, and wireless communication capability. Because of their inherent limitations, the protocols designed for such sensor networks must efficiently use both limited bandwidth and battery energy. We develop an M/G/1 model to analytically determine the delay incurred in handling various types of queries using our enhanced APTEEN (Adaptive Periodic Threshold-sensitive Energy Efficient sensor Network protocol) protocol. Our protocol uses an enhanced TDMA schedule to efficiently incorporate query handling, with a queuing mechanism for heavy loads. It also provides the additional flexibility of querying the network through any node in the network. To verify our analytical results, we have simulated a temperature sensing application with a Poisson arrival rate for queries on the network simulator ns-2. As the simulation and analytical results match perfectly well, this can be said to be the first step towards analytically determining the delay characteristics of a wireless sensor network.

The emergence of Bluetooth as a default radio interface has allowed handheld electronic devices to be instantly interconnected as ad-hoc networks. These short range ad-hoc wireless networks, called piconets, operate in the unlicensed 2.45 GHz ISM (industrial-scientific-medical) band where up to eight devices may be used to configure single or overlapping piconets. As all piconets operating in the same frequency band, the presence of multiple piconets creates interference on signal reception. This paper employs a signal capture model to study the piconet MAC performance, taking inter-piconet interference into consideration. Furthermore, extensive simulation is performed to validate the throughput obtained from our model. These results indicate that Bluetooth throughput is sensibly affected by multiple piconet interference.

The emergence of Bluetooth as a default radio interface allows handheld electronic devices to be instantly interconnected into ad hoc networks. These short range ad-hoc wireless networks, called piconets, operate in the unlicensed 2.45 GHz ISM (Industrial-Scientific-Medical) band where up to eight devices may be used to configure single or overlapping piconets. This creates interference on the device from other devices operating in the same frequency band including microwaves and devices enabling various wireless LAN standards. This paper uses a signal capture model to study piconet MAC performance. Furthermore, simulations are used to validate the throughput obtained from this model. These results reveal important performance implications of the effect of inter-piconet interference on throughput.

Allocation of tasks of a periodic, time critical application, onto a set of processors, with task duplication is examined here. Pipelined execution, where computations and communications take place simultaneously, is employed to meet the required flow rate of the application. The prime objective of the algorithm is to reduce the number of pipeline stages and/or the pipeline period and thereby reducing pipeline latency. The algorithm is well suited for both homogeneous and heterogeneous systems and it is scalable. The order of complexity of the algorithm is O(/spl nu//sup 2/), where /spl nu/ is the number of nodes in directed acyclic task graph (DAG) representing the application. Simulations have indicated that the proposed algorithm generates 9%-52% shorter pipelines.

Wireless sensor networks are expected to find wide applicability and increasing deployment in the near future. In this paper, we propose a formal classification of sensor networks, based on their mode of functioning, as proactive and reactive networks. Reactive networks, as opposed to passive data collecting proactive networks, respond immediately to changes in the relevant parameters of interest. We also introduce a new energy efficient protocol, TEEN (Threshold sensitive Energy Efficient sensor Network protocol) for reactive networks. We evaluate the performance of our protocol for a simple temperature sensing application. In terms of energy efficiency, our protocol has been observed to outperform existing conventional sensor network protocols. 1.

Ad hoc networks are a new generation of networks offering unrestricted mobility without any underlying infrastructure. Primary applications of ad hoc networks are in military, tactical and other security-sensitive operations, where the environment is hostile. Hence, security is a critical issue. Due to the nature of ad hoc networks, conventional security measures cannot be used. New security techniques are essential for a high-survivability network. The performance of the protocol may be severely affected in the presence of compromised nodes that inflict unpredictable and undetectable Byzantine failure. We have identified certain misbehaviors caused by a malicious node to a reactive routing protocol, specifically the ad hoc on-demand distance vector (AODV) protocol. We also discuss the intrusion detection and intrusion prevention model to prevent several identified attacks in the network.

In this paper, we propose an analytical modeling for integrated wireless networks with priority reservation and preemptive priority procedures. In our scheme, calls are separated into four different classes: originating voice calls, originating data calls, voice and data handoff request calls. In the proposed scheme, there are queues for handoff request calls. Some number of channels in each cell are reserved exclusively for handoff request calls. Out of this number of channels, some are reserved exclusively for voice handoff requests. The remaining channels are shared by both originating and handoff request calls. Higher priority is given to voice handoff requests over data handoff requests and can preempt the service of ongoing data calls if on arrival it finds no free channels. A three-dimensional Markov chain model is used to determine system performance in terms of blocking probabilities of originating calls, forced termination probability of voice handoff requests calls, and average transmission delay of data calls.

Optimal scheduling of tasks represented by a directed acyclic graph (DAG) onto a set of homogeneous processors, is a strong NP-hard problem. In this paper we introduce a scalable scheduling scheme called STDS for heterogeneous systems. This implies that tasks could potentially have different run times on different processors. The complexity of STDS is O(v/sup 2/) where v is the number of nodes in the task graph. Schedule length is primarily reduced by selected task duplication. Current task duplication based scheduling schemes are mostly done for homogeneous systems. Comparing the performance of STDS with BIL, another scheduling scheme for heterogeneous systems, it is observed that STDS obtained speed-ups of 6 to 40 generating shorter schedules when sufficient duplication can be carried out.

We present a task duplication based scalable scheduling algorithm for Symmetric Multiprocessors (SMP), called S3MP (Scalable Scheduling for SMP), to address the problem of task scheduling. The algorithm pre-allocates network communication resources so as to avoid potential communication conflicts, and generates a schedule for the number of processors available in an SMP. This algorithm employs heuristics to select duplication of tasks so that schedule length is reduced/minimized. The performance of the S3MP algorithm has been observed by comparing the schedule length under various number of processors and the ratio of communication to computation cost. This algorithm also has been applied to some practical directed acyclic graphs (DAGs).

Optimal scheduling of tasks of a directed acyclic graph (DAG) onto a set of processors is a strong NP-hard problem. In this paper we present a scheduling scheme called TDS to schedule tasks of a DAG onto a heterogeneous system. This models a network of workstations, with processors of varying computing power. The primary objective of this scheme is to minimize schedule length and scheduling time itself. The existing task duplication based scheduling scheme is primarily done for totally homogeneous systems. We compare the performance of this algorithm with an existing scheduling scheme for heterogeneous processors called BIL. In initial simulations TDS has been observed to generate scheduling lengths shorter than that of BIL, for communication-to-computation cost ratios (CCR) of 0.2 to 1. Moreover TDS is far more superior than BIL as far as scheduling time is concerned.

With the advent of high-speed networks for data and multimedia communications, traffic is becoming more and more bursty. Self-similarity, which is introduced by new data networks, is a manifestation of heavy correlation between cell/packet inter-arrival times. We examine the effectiveness of a congestion control framework in reducing the inherent variability of fractal traffic, with the objective of increasing utilization of the links and reducing the cell loss ratio in ATM networks. We propose to do so at the source by controlling the injection of the burst of cells at the user-network interface (UNI) source nodes. We show that the proposed algorithm also reduces the cell delay at individual nodes of the ATM backbone. End-to-end delay (a QoS parameter) is also shown to be reduced by the proposed algorithm. We further show that including the burst control approach reduces the buffer requirement in a congested environment to maintain the negotiated QoS.

The field of ad hoc networks is currently receiving a lot of attention due to its immense potential in diverse applications. Most of the research in this area is focused on designing efficient routing protocols. As per our knowledge, the issue of QoS improvement in ad hoc networks is yet to be addressed. We examine the use of packet scheduling at the network level so as to improve the network QoS. We present two scheduling strategies that schedule packets based on the length of the message to which they belong. Simulations conducted on ns, the network simulator from the University of California at Berkeley, indicate that substantial improvement in terms of end-to-end message delay can be obtained without adversely affecting the network message throughput.

Ad hoc networks are a new generation of networks offering unrestricted mobility without any underlying infrastructure. In these kinds of networks, all the nodes share the responsibility of network formation and management. As their principle application is in catastrophic environments, security is critical. Authentication, integrity and encryption are key issues pertaining to network security. Traditional authentication schemes cannot be effectively used in such decentralized networks. We present an end-to-end data authentication scheme that relies on mutual trust between nodes. The basic strategy is to take advantage of the hierarchical architecture that is implemented for routing purposes. We have proposed an authentication scheme that uses TCP at the transport layer and a hierarchical architecture at the IP layer so that the number of encryptions needed is minimized, thereby reducing the computational overheads. This also results in substantial savings as each node has to maintain keys for fewer nodes.

+I INRE arc several means nf intercomiecting the compoT nents of a computer system. Components can be connccted through direct or indirect connections. In a direct network, channels directly connect each processor. Neighboring nodes communicate with each other by scnding messages across the channcls. In an indirect network, processors are cnnnccted through switches and/or buses. Depending on how components are connected, we have bus-based networks, router-based networks, switcli-bascd networks, and cluster-based (hybrid of the other thrce networks) nctworks. Nctworks can also be classified bascd on topologies, which cau be either replnr or irregulnr. Anothcr classification is based on applications-there are local arca networks (LANs), networks of workstations (NOWs), multiprocessors, and mobilc networks. In a computer network, the efficiency of a routing process is critical to the system performance. A routing process deals with moving data between processors in a given network. When a routing process involves oiic source and onc destination, it is called unicnst or poirit-lopoint communication. When such a proccss involves more than one source and/or one destination, it is called a collective comrnlrnicntion process. Examples of collective communication include iirulticnst (one-to-many, one source and many destinations), brundcnst (one-to-all), and gossip (all-to-all).

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

Task Scheduling is one of the key elements in any distributed-memory machine (DMM), and an efficient algorithm can help reduce the interprocessor communication time. As optimal scheduling of tasks to DMMs is a strong NP-hard problem, many heuristic algorithms have been introduced in the literature. This paper presents a Task Duplication based Scheduling (TDS) algorithm which can schedule directed acyclic graphs (DAGs) with a complexity of O(|V|/sup 2/), where |V| is the number of tasks in the DAG. This algorithm generates an optimal schedule for a class of DAGs which satisfy a simple cost relationship. The performance of the algorithm has been observed by its application to some practical DAGs, and by comparing it with other existing scheduling schemes in terms of the schedule length and algorithm complexity.

Several intra- and inter-procedural program analysis techniques form the backbone of an optimizing and parallelizing compiler. The efficacy of these analyses depends upon how precise the call graph is. However, due to lack of exact type information for objects in an object-oriented (OO) program the existing call graph construction algorithms are rendered imprecise. In this paper, we present an algorithm for constructing a more precise call graph by exploiting the static class hierarchy of an OO program. The information collected during the class hierarchy analysis helps in avoiding unnecessary addition of many spurious call graph edges for virtual-function calls. We have implemented our algorithm for handling C++ programs within a restructuring tool, Sage++. With our precise algorithm for call graph construction, the percentage reduction in the number of nodes and edges in the call graphs for the benchmark programs we had selected ranged between 4% to 56% and between 22% to 58%, respectively.

This paper introduces a generic methodology for developing deadlock-free routing in an arbitrary network by partitioning a graph into subdigraphs without cyclic dependencies and by strategically assigning virtual channels. We illustrate our scheme by identifying subdigraph characteristics that guarantee acyclic routing for n-dimensional hypercube, n-dimensional mesh and k-ary n-cube torus. Further generalization allows partial cyclic dependencies and forms a larger class of deadlock-free routing algorithms. We apply our technique to k-ary n-cube torus network and develop several novel deadlock-free, adaptive algorithms. Because our technique decomposes networks into several subdigraphs, it simplifies and generalizes the development of both static and adaptive deadlock-free routing algorithms for arbitrary networks.

This article provides an overview of doubly linked networks. We first classify the doubly linked network on the basis of the number of tuples used to represent each node address in the network. Then, each subclass of network is further partitioned into loop or nonloop categories. Various routing algorithms are studied and grouped into static or adaptive routing type, based on the number of paths between nodes used in the point-to-point message transmission. The useful protocols of the token ring and the register insertion ring and their relative advantages are also described. Some issues, such as multiple destinations routing, graceful degradation on cluster faults, and network behavior under unbalanced traffic conditions, in a doubly linked network are still open. There seems to be a need for new protocols when optical fiber is used as the medium for message transmission, which necessitates high-quality and large bandwidth data transmission. © 1996 John Wiley & Sons, Inc.

In a Distributed Computing System (DCS), the failure of one or more system components causes the degradation in its effectiveness to complete a given task as opposed to a complete network breakdown. This paper addresses the issue of degraded system effectiveness evaluation by introducing two static measures, namely, Distributed Program Performance Index (DPPI) and Distributed System Performance Index (DSPI). These metrics can be used to compare networks with different features for application execution. It can be used to determine if the network with high reliability and low capacity, or low reliability and high capacity is better for a given program execution. An algorithm is also developed for computing these indices, and it is shown to be not only efficient, but general enough to compute many other existing measures such as computer networks, distributed systems, transaction based systems, etc.

Many recent supercomputers employ either a cluster-based design or a highly scalable network. Clustering is built-in in a hierarchical system, while highly scalable networks like mesh or torus could be easily partitioned into modules to form several clusters. This paper first specifies a self-routing connection method in a recently introduced class of hierarchical topology called de Bruijn-Cube (dBCube) network, and presents a deadlock-free routing scheme using virtual channels. A new switching method called Wormhole Intracluster Cut-through Intercluster (WICI) routing is also introduced to improve the network performance fairly close to the virtual cut-through and to maintain the buffer cost as compared to prevalent routing schemes of wormhole. Usefulness of WICI routing has been demonstrated for the hierarchical network of dBCube and large networks like mesh and torus, and simulation results for WICI routing are compared with wormhole and virtual cut-through routings.

Abstract Our earlier work reported a Threshold Scheduling Method for compile‐time mapping of functional parallism on distributed‐memory systems. The work reported in this paper discusses run‐time issues in efficiently supporting the functional parallism with minimal overheads, through a combination of compile‐time and run‐time ownership analysis. At compile time, the code generation phase determines whether a local copy of a live definition of a variable needed by a task is available on a given processor, through an ownership analysis. In case ownership cannot be resolved at compile time, an appropriate code is generated to perform analysis at run time. The code generation is carried out so that all the processors carry the same copy of the compiled program with the individual processor's code being isolated and the universally owned code being replicated on all processors to minimize run‐time overheads. The run‐time system maintains the static and dynamic ownerships at every processor to avoid communication overhead on ownership information. We demonstrate the approach by incorporating it in the compiler for targeting a parallel functional language, Sisal (streams and iterations in single assignment language), to Intel Touchstone i860 systems. Several benchmarks demonstrate the viability of the approach.

We attempt a new variant of the scheduling problem by investigating the scalability of the schedule length with the required number of processors, by performing scheduling partially at compile time and partially at run time. Assuming infinite number of processors, the compile time schedule is found using a new concept of the threshold of a task that quantifies a trade-off between the schedule-length and the degree of parallelism. The schedule is found to minimize either the schedule length or the number of required processors and it satisfies: A feasibility condition which guarantees that the schedule delay of a task from its earliest start time is below the threshold, and an optimality condition which uses a merit function to decide the best task-processor match for a set of tasks competing for a given processor. At run time, the tasks are merged producing a schedule for a smaller number of available processors. This allows the program to be scaled down to the processors actually available at run time. Usefulness of this scheduling heuristic has been demonstrated by incorporating the scheduler in the compiler backend for targeting Sisal (Streams and Iterations in a Single Assignment Language) on iPSC/860.>

Efficient scheduling algorithm is one of the key factors in determining the performance of distributed memory machines. This paper presents an enhanced Search and Du plication Based Scheduling (SDBS) algorithm which car schedule Directed Acyclic Graphs (DA Gs) with variable execution time tasks. Since the DAGs are based on data dependencies of the tasks, the control dependencies are clustered within each node. If the node encapsulates a loop or an if-then-else kind of statement, then assuming the execution times to be fixed would not be appropriate. It is assumed in this paper that the execution time varies between two time estimates. The complexity of this scheduling algorithm is in 0(V 4- E), where V is the number of node,- and E is the number of edges in the task graph. This algo rithm is based on some realistic assumptions and generates an optimal time schedule. If the assumptions cannot be completely satisfied then the algorithm provides a schedule which is close to optimal. The performance in these cases has been obtained using extensive simulation work which indicate the closeness of the results.

Two recent topologies-Manhattan Street Network (MSN) and HR/sup 4/-Net (or 2-D Torus)-proposed for metropolitan areas are primarily mesh connected networks. The authors compare the average distance, the diameter, the terminal reliability, and the cost. Simulation results indicate that they are fairly close in performance, while the MSN is observed to be more cost-effective than the HR/sup 4/-Net.>

This short paper presents a framework for periodic execution of task-flow graphs that enables schedulability analysis of the communication requirements. The analysis performs the steps of segmenting messages, assigning the segments to specific links and time intervals, and ordering them within the intervals to generate node switching schedules that provide contention-free message routing at run-time. The analysis is also used to integrate task allocation with message routing using a contention-based objective function. Usefulness of the proposed scheme in ensuring guaranteed communication performance is demonstrated by an appropriate example.>

Design of a large distributed system (DS) is becoming increasing important and with its added popularity, it is crucial to define its topology based on some objective function. This paper introduces a reliability-based systematic approach for defining the topology of a DS network in a hierarchical form, given the traffic requirements, a set of cluster topologies and the cost constraints. The authors scheme first identifies a group of permissible inter-cluster links which yields the maximum network reliability to cost ratio and then selects the gateways within each cluster for balancing the traffic through the inter-cluster links and the node degrees within each cluster. The usefulness of their method lies in a simultaneous consideration of the cost and the network reliability. Some examples are included to illustrate their design procedure.>

An efficient algorithm to compute Task Based Reliability of large multiprocessor systems or Distributed Computer Systems, using hierarchical modeling approach, is introduced. Heterogenous clusters with irregular topologies are handled.

Hierarchical interconnection schemes have been proposed in the literature to take advantage of locality of refernce. This paper presents a dynamic scheme for hierarchical intercon nection called Hierarchical Multistage Interconnection Net work (HMIN). We discuss the various design alternatives and evaluate each of them with respect to average delay and cost. HMINs are compared only with MINs because of a lack of a method of comparing the cost of a static HIN with a dynamic HMIN.

A class of doubly connected two-dimensional Manhattan street networks (MSN) is extended to a multidimensional MSN (MMSN) by a simple edge division operation. The topology is defined by three simple link equations. An approximate expression for the diameter is obtained and a simple routing scheme for three-dimensional MMSN is introduced. The proposed MMSN is shown to possess better performance parameters than the MSN topology.>

Introduces a class of hierarchical networks that is suitable for implementation of large multi-computers in VLSI with wafer scale integration (VLSI/WSI) technology. These networks, which are termed dBCube, employ the hypercube topology as a basic cluster, connect many of these clusters using a de Bruijn graph, and maintain the node connectivity to be the same for all nodes product graph. The size of this class of regular networks can be easily extended by increments of a cluster size. Local communication, to be satisfied by the hypercube topology, allows easy embedding of existing parallel algorithms, while the de Bruijn graph, which was chosen for JPL's 8096-node multiprocessor, provides the shortest distance between clusters running different parts of an application. A scheme for obtaining WSI layout is introduced and used to estimate the number of tracks needed and the required area of the wafer. The exact number of tracks in the hypercube and an approximation for the de Bruijn graph are also obtained. Tradeoffs of area versus static parameters and the size of the hypercube versus that of the de Bruijn graph are also discussed.>

Several arc consistency algorithms for sequential and parallel processing computers are reviewed. Three distributed parallel arc consistency algorithms-DSPAC-1, DSPAC-2, and DSPAC-3-are introduced and compared with existing algorithms. Through actual machine experimentation the time required for the DSPAC algorithms was measured and compared with that for existing sequential algorithms. Results indicate that the parallel arc consistency algorithms are very effective and that scalability can be efficiently maintained.>

Article Scheduling pipelined communication in distributed memory multiprocessors for real-time applications Share on Authors: Shridhar B. Shukla Code EC/Sh, Dept. of Elect. & Computer Engineering, Naval Postgraduate School, Monterey, CA Code EC/Sh, Dept. of Elect. & Computer Engineering, Naval Postgraduate School, Monterey, CAView Profile , Dharma P. Agrawal Computer Systems Laboratory, Dept. of Elect. & Computer Engineering, North Carolina State University, Raleigh, NC Computer Systems Laboratory, Dept. of Elect. & Computer Engineering, North Carolina State University, Raleigh, NCView Profile Authors Info & Claims ISCA '91: Proceedings of the 18th annual international symposium on Computer architectureApril 1991 Pages 222–231https://doi.org/10.1145/115952.115975Online:01 April 1991Publication History 19citation274DownloadsMetricsTotal Citations19Total Downloads274Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A single-stage interconnection network (SSIN) consisting of only one stage of switches and recirculation through processors is studied. An analytical probability model for SSINs using 2*2 switches is introduced, and results obtained with the model are compared with simulation results. Four SSINs with different network sizes, loading, and routing strategies are discussed. Processors with and without buffers are considered, and three different routing strategies are applied to resolve conflicts. The analytical model is seen to be in close agreement with the simulation results while providing at least an order of magnitude reduction in CPU time.>

The authors introduce the tilted-tree concept to obtain a closed-form solution for the average distance and diameter. A simple distributed algorithm for optimal broadcasting in Manhattan Street Networks (MSNs) is also presented. Simulation results are compared with the analytical results to substantiate the optimality of the proposed algorithm.>

Three pipelined multiprocessor implementations of adaptive lattice filters are examined. A performance analysis is done for each multiprocessor system, and expressions for approximate computation time and speedup are derived. Each system is shown to be flexible with respect to the different algorithms and the different filter sizes it can implement.>

Three pipelined multiprocessor implementations of adaptive lattice filters are examined. The three multiprocessor architectures, which can be characterized as a serial pipeline, a ladder-connected dual pipeline, and a ring pipeline, are derived directly from the computational and data-transfer requirements of adaptive lattice algorithms. The order-recursive nature of the adaptive lattice structure results in architectures which use pipelining extensively. A performance analysis is done for each multiprocessor system, with respect to two different adaptive lattice algorithms. Expressions for approximate computation time and speedup are derived for each combination of architecture and algorithm.>

The authors present a group of multidimensional regular topologies with two incoming and two outgoing link per node. The use of a mixed-radix numbering system in defining the network topology leads to many choices for the jump distance, which provides better performance when the total number of nodes is large. They introduce a performance parameter named spanning radius (SPR) which determines the addition traversal required to use all different choices when the number of choices exceeds two. The impact of the number of choices and its SPR on the network performance is also studied. The results show that a multidimensional network performs better in terms of diameter and reliability when the penalty of the extra link traversal is offset by the saving due to the additional jump distance choices used.>

The authors introduce two techniques for computing the reliability of a distributed computing system (DCS). The first scheme uses two steps and requires enumeration of multiterminal connections which, in turn, leads to the reliability expression. The second technique, called FARE (Fast Algorithm for Reliability Evaluation), does not require an a priori knowledge of multiterminal connections for computing the reliability expression. A performance parameter called the communication cost index (CCI) is defined. The authors compare algorithms with an existing method in terms of computer time and memory requirement. The results show that FARE outperforms two-step methods.>

A flexible, fault-tolerant architecture to perform 2-D convolution of images for kernels of arbitrary shapes and sizes is proposed. The convolved image is output online as the input image is generated and received, providing optimal turnaround time. The regularity of the computation and the raster-scan input of pixels are used to pipeline computations as well as memory operations. Throughput of (kl/u) is achieved for a variety of kernel sizes with a k*l array of multiply-accumulate cells, where u is the time for a single fixed-point multiply-accumulate operation. It is shown that by queuing accesses at memory modules the limitation placed by access time on the throughput can be removed. Larger, as well as smaller kernels can be accommodated on a fixed-size array with a single pass of the image and a minor change in the computation flow. The host enjoys absence of any control overhead and only has to supply the pixels and collect the output pixels in simple raster-scan fashion for any kernel size.>

The authors propose a technique to compute software system reliability (SSR). The method, called FARE (fast algorithm for reliability evaluation), does not require a priori knowledge of multiterminal connections (MCs) for computing the reliability expression. An effort is made to sole the problem of N-version programming by using the FARE approach. Owing to its short execution time and low memory requirement, FARE can be used to calculate the SSR of fairly large distributed systems.>

Nonequivalence of multistage interconnection networks is established by obtaining a reduced graph model and then partitioning it into several bipartite subgraphs. This is shown to transform nonequivalence to nonisomorphism, which can be easily determined by examining the intrinsic characteristics of undirected loops. A reverse process allows the design of nonequivalent networks.>

A technique for parallel backtracking using randomization is proposed. Its main advantage is that good speedups are possible with little or no interprocessor communication. The speedup obtainable is problem-dependent. In those cases where the problem size becomes very large, randomization is extremely successful achieving good speedups. The technique also ensures high reliability, flexibility, and fault tolerance.>

A general class of hypercube structures is presented in this paper for interconnecting a network of microcomputers in parallel and distributed environments. The interconnection is based on a mixed radix number system and the technique results in a variety of hypercube structures for a given number of processors N, depending on the desired diameter of the network. A cost optimal realization is obtained through a process of discrete optimization. The performance of such a structure is compared to that of other existing hypercube structures such as Boolean n-cube and nearest neighbor mesh computers.

This paper introduces the VLSI design and layout of a (log2n) time n-bit binary parallel multiplier for two unsigned operands. Proposed design consists of partitioning the multiplier and multiplicand bits Into four groups of n/4 bits each and then reducing the matrix of sixteen product terms using three to two parallel counters and Brent-Kung (log n) time parallel adder. Area-time performance of the present scheme has been compared with the existing schemes for parallel multipliers. Regular and recursive design of the multiplier is shown to be suitable for VLSI implementation and an improved table look up multiplier has been used to form the basis of the recursive design scheme.

This paper introduces two graph theoretic models that provide a uniform procedure for analyzing 2n-input/2n-output Multistage Interconnection Networks (MIN's), implemented with 2-input/2-output Switching Elements (SE's) and satisfying a characteristics called the "buddy property." These models show that all such n-stage MIN's are topologically equivalent and hence prove that one MIN can be implemented from integrated circuits designed for another MIN. The proposed techniques also allow identical modeling and comparison of permutation capabilities of n-stage MIN's and other link-controlled networks like augmented data manipulator and SW Banyan Network and hence, allows comparison of their permutation. In the case of any conflict in the MIN, an upper bound for the required number of passes has been obtained.

This paper introduces a general class of self-routing interconnection networks for tightly coupled multiprocessor systems. The proposed network, named a "generalized shuffle network (GSN)," is based on a new interconnection pattern called a generalized shuffle and is capable of connecting any number of processors M to any number of memory modules N. The technique results in a variety of interconnection networks depending on how M nd N are factored. The network covers a broad spectrum of interconnections, starting from shared bus to crossbar switches and also includes various multistage interconnection networks (MIN's).

A decimation-in-time radix-2 fast Fourier transform (FFT) algorithm is considered here for implementation in multiprocessors with shared bus, multistage interconnection network (MIN), and in mesh connected computers. Results are derived for data allocation, interprocessor communication, approximate computation time, and speedup of an N point FFT on any P available processing elements (PE's). Further generalization is obtained for a radix-r FFT algorithm. An N X N point two-dimensional discrete Fourier transform (DFT) implementation is also considered when one or more rows of the input data matrix are allocated to each PE.

A new class of general topologies is proposed in this paper for interconnecting a large network of computers in parallel and distributed environment. These structures have been shown to possess small internode distances, fairly low number of links per node, easy message routing and large number of alternate paths that can be used in case of faults in the system. The interconnection is based on a mixed radix number system, presented in this paper. The technique results in a variety of structures for a given number of processors N, depending on the required diameter in the network. A bus oriented structure is also introduced here, based on the same mathematical framework. These structures possess only two I/O ports per processor and are also shown to have small internode distances.

In this paper we introduce the concept of pseudoparallelism, in which the serial algorithm is partitioned into several noninteractive independent subtasks so that parallelism can be used within each subtask level. This approach is illustrated by applying it to a real-time dynamic scene analysis. Complete details of such a pseudoparallel architecture with an emphasis to avoid interprocessor communications have been worked out. Problems encountered in the course of designing such a system with a distributed operating system (no master control) have been outlined and necessary justifications have been provided. A scheme indicating various memory modules, processing elements, and their data-path requirements is included and ways to provide continuous flow of partitioned information in the form of a synchronized pipeline are described.

In this correspondence we derive algorithms for multioperand addition of Koren's generalized number system. A carry-lookahead adder for fast addition of two operands in generalized binary numbers is developed. Truncation errors for this type of representation are examined and rounding algorithms are presented to reduce these errors.

The use of sorting in various computer-related applications such as database management, is well established. Normally, sorting is implemented by employing a combination of hardware and software techniques. In this correspondence the authors examine the utility of serial-shifting nature of the charge coupled device (CCD) and the magnetic bubble memories for achieving low-cost sorting within the secondary storage. The radix-sort method has been found to be very suitable for this purpose. Five different memory organizations implementing radix sort have been described in detail and their relative merits are also outlined.

This correspondence emphasizes the close relationship between binary addition and negative negabinary addition (n.n.b.a.). This is established by describing two possible ways of utilizing binary adders for performing n.n.b.a. Similar techniques of using n.n.b.a. adders for binary addition are also outlined and thus, negative addition is seen to be a primitive operation. These algorithms lead to four simple conversion processes of numbers from binary to negabinary system and vice versa.

This paper describes an asynchronous circuit switching network for multiple-processor systems. Several circuit switching networks for various applications have been proposed and constructed. However, there are problems associated with these networks. The asynchronous circuit switching network possesses several features that can solve these problems. A three-stage fully connected topology is utilized to construct the network. Each switching element is functionally and physically identical and this facilitates a cost-effective LSI implementation and software development. The control structure of the switching element and the routing algorithm are re-organized to fit the asynchronous operation. The network takes advantage of low-cost microcomputers to do the distributed routing control and to implement the communication protocols. The graceful degradation characteristic in the network is provided by independent multiple paths existing between any pair of the source and the destination. A network monitor is incorporated to facilitate an adaptive routing strategy and to have the fault diagnostic capability. Three alternatives for the switching element implementation are described to demonstrate the hardware and software tradeoffs.

High-speed multifunction arithmetic arrays for multiplication, division, square and square-root operations are presented in this paper. These arrays seem attractive due to their versatility and speed. A recently described quotient-bit evaluation technique that uses the carry-save method in a nonuniform division array is extended here for the restoring-division process. This array includes the multiplication process as well, and the division time approaches that of multiplication. The design objective of multifunctional arithmetic arrays precludes consideration of other high-speed division techniques. A further extension of the restoring division process is shown to make the design of an array for square/square-root operation straightforward. The two underlying arrays can be coalesced to perform any one of the four operations. Possible methods of merging the arrays, with their relative merits, are also discussed. For illustration purposes, complete internal details of such a generalized pipelined array for 4-bit operation is included in this paper. Due consideration is also given to the possibility of large-scale integration of the different arrays illustrated in this paper.

Recent use of the negabinary system in the application oriented digital hardware, has encouraged the search for suitable arithmetic algorithms in -2 base. These algorithms have been directly utilized in designing logic circuits and several logic implementations have been reported in the literature. The main objective of this paper is to show the close relationship between +2 base addition and -2 base negative addition. Two possible ways of utilizing binary adders for performing negabinary addition and their underlying theories are presented. Two similar techniques of using negabinary adders for binary addition are also considered in detail. An interesting aspect of this investigation about negabinary base is that negative addition (rather than just addition) seems to be the primitive operation from logic complexity and interchangeability of +2 and -2 adders point of view. The technique of adding two numbers in one system by the adders of the other system is extended here for multiple operand addition. This requires inclusion of an additional correction factor. Further, the additive algorithms of this work lead to four simple conversion processes of number from one system to another. This paper seems to be a realistic step towards the use of similar hardware for +2 and -2 bases and hence this allows an instantaneous flexibility on the selection of number system. It is believed that this paper will attract more attention on the use of -2 base system for the design of special purpose digital machines and process controllers.

A novel format for representing modulo (2n+1) numbers, is shown to be helpful in achieving modular addition and complementation. Logic for fast addition using carry-look-ahead and modular complementation is also presented.

In this paper, various Communication Processor Systems (CPS) architectures are reviewed and classified according to their interconnection organizations. The evolution and future development of the CPS architectures are discussed and the intercommunication subsystem requirement, interconnection networks structure, network hardware and software design aspects are carefully examined. The functional baseline for the processing unit of the CPS is identified and a comparative study of various existing and proposed processing units is included. The critical review is based on the important features such as the reliability improvement, the interrupt handling, the priority encoding, and the optimized repertoire, etc. Finally, general software considerations are also outlined.

A novel technique for computing squares of negabinary numbers is described in this correspondence. The basic principle is to use an arithmetic algorithm normally utilized for the square-root operation. Asuitable recursive combinations are shown to reduce the problem of obtaining the square of "n" bit number to the addition of [n/3] operands and the change of sign in the last step is shown to be helpful in reducing the hardware. One way for further improvement is also suggested.

Recent application of negabinary number systems in signal processing has evoked the question of the suitability of binary base. Many proposals for multioperand addition of unsigned binary numbers are available in the literature. Here, the addition of two numbers in 2's complement notation-has been extended to n signed summands. The time delay remains the same as that of processing n unsigned numbers. This method shows new promises for its application to signal processing.

Recently, Yuen1 has given simple methods for positive-negative base conversion. This correspondence presents a straightforward and complete proof for his algorithmetic steps. A few comments on the choice of negabinary adders with positive twin carries and with positive and negative carries have also been added.

A signed modified reflected binary (SMRB) code with unique representability of both positive and negative numbers has been proposed in this correspondence. The bit pattern in this code can be defined in a systematic way leading to a simple synchronous up/down counter. Some arithmetic operations for this code have also been considered.

Array-like structures for high-speed multiplication, division, square and square-root operations have been described in this paper. In these designs the division and square-rooting time have been made to approach to that of multiplication operation. These structures are optimum from speed and versatility point of view. Most of the cellular arrays described in the literature are adequately slow. The time delay is particularly significant in the division and square-rooting operations due to the ripple effect of the carries. Though the carry-save technique has been widely utilized for multiplication operation, it has been only recently employed by Cappa et. al. in the design of a non-restoring divider array. This requires sign-bit detection that makes the array non-uniform. Such an array has been named as an array-like structure. The carry-save method has been extended here for restoring division operation. Due to sign-detection and overflow correction requirements, the restoring method is slightly complex. But the main advantage of such restoring array is in its simple extension for multiplication operation. The array for the two operations, when pipelined, will have more computing power than all other multiplier-divider arrays. Suggestions have also been included for further speed improvement. The technique applied for division operation is as well applicable for the square-rooting and an array-like structure for square-square-rooting operations has also been given. For performing any one of the four operations, the only manipulation to be done is to combine the two arrays; one for multiplication-division and another for square-square-rooting. Possible methods of combining the two arrays have been indicated and their relative advantages and disadvantages have been mentioned. Finally, a generalized pipeline array-like structure with complete internal details and for 4-bit operation, has been shown. Due consideration has also been given to the possibility of large-scale-integration of different arrays presented in this paper.

Algorithms are described for the basic arithmetic operations in a negative base. These algorithms are simpler, faster, and more general than those proposed by Sankar et al.