In this paper, we propose a novel deferred acceptance based resource allocation algorithm (DARA) for allocating LTE cellular user resource to D2D devices. The quality of service (QoS) constrained downlink resource block (RB) allocation problem is first formulated as a computationally expensive mixed integer nonlinear programming (MINLP) problem. We also propose a polynomial-time matching algorithm based on deferred acceptance method to find an allocation of cellular resources to D2D devices. Outcome of this algorithm is a stable matching of cellular users to the D2D devices. We compare the system sum rate obtained from DARA to that from a simple local search based algorithm (SLOC), a greedy heuristic based resource allocation algorithm (GHRA) and a random resource allocation algorithm. The simulation results show that, DARA achieves significantly better system sum rate than the rest of the algorithms while it runs in O(n2) in the worst case and O(n log n) on average.

Interference coordination while sharing cellular radio resources with Device-to-Device (D2D) pairs needs to be done in the short LTE scheduling period of 1 ms. In this paper, we propose a fast, two-phase auction based, fair and interference aware resource allocation algorithm (TAFIRA) for underlaying D2D communication. TAFIRA can be used to minimize the interference both at the evolved Node B (eNB) and the receiver of the D2D pairs while simultaneously maintaining a target system sum rate and ensuring fair allocation of cellular resources among D2D pairs. We compare TAFIRA with a MInimum Knapsack based Interference Resource Allocation algorithm (MIKIRA) and a random allocation technique. The time complexity of TAFIRA on average is O(m2n), where m and n are the number of D2D pairs and number of cellular users respectively. Our simulation results how that, TAFIRA obtains a much better system sum rate while incurring very little increased interference at the eNB and the D2D receivers when compared with MIKIRA and the random approach. TAFIRA also shows much more fairness in allocating cellular resources among the D2D pairs when compared with MIKIRA.

Resource allocation for Device-to-Device (D2D) communication underlaying cellular network poses new challenges in terms of interference while at the same time provides increased system sum rate. In this paper, we propose a local search based resource allocation algorithm (LORA) for allocating resource blocks to D2D devices that are shared with Long Term Evolution (LTE) cellular users. We first formulate the problem of downlink resource block (RB) allocation to D2D users from cellular users as a computationally expensive mixed integer nonlinear programming (MINLP) problem. However, as the optimal solution of an MINLP can take exponential time to compute, we propose a local search based algorithm to compute a locally optimal solution based on an initial feasible solution. We compare the obtained system sum rate from this local search algorithm with a well-known greedy heuristic based resource allocation algorithm and a random resource allocation algorithm. The simulation results show that LORA achieves an overall better system sum rate compared to the other algorithms for RB allocation while maintaining the signal quality at the cellular users and the D2D receivers.

Sharing resources between Long Term Evolution (LTE) cellular users and Device-to-Device (D2D) pairs comes at the cost of increased interference. In this paper, we propose a Minimum Knapsack-based Interference-aware Resource Allocation (MIKIRA) approach to show that a channel sharing approach can be used to increase system sum rate, minimize the interference both at the evolved Node B (eNB) and the receiver of the D2D pairs, and most importantly achieve a good signal quality at the eNB in lower time complexity in an LTE cellular network. We compare the system sum rate, interference and Signal-to-Interference and Noise Ratio (SINR) obtained by MIKIRA with a bipartite graph-based approach (GRA) for resource allocation and a random allocation approach. ¿From the results we find that MIKIRA shows improved performance when compared to other approaches in all of the metrics we used in the simulation. MIKIRA is more efficient in terms of time complexity (O(n2log(n))) when compared with the GRA (O(n3)); and also results in higher quality signals as the SINR achieved at the eNB is much better than the other two approaches.

Object monitoring is an important application of mobile wireless sensor networks. Several algorithms appear in the literature for different variants of the object monitoring problem. Most of them are either centralized or distributed. Algorithms for mobile wireless sensor networks involve many aspects not dealt with in traditional networks and hence mobile wireless networks can be viewed as an unconventional computation model. We design algorithms for mobile wireless sensor networks based on another unconventional model of computation namely, the biologically inspired cellular automata. We design a cellular automaton based algorithm for an object monitoring problem where initially a number of mobile sensors and mobile objects are deployed randomly in a dense area of the network and they are allowed to move within the network. Our main goal is to monitor the mobile objects by the mobile sensors as long as possible. To the best of our knowledge, we propose the first cellular automaton based algorithm for this problem. We find that our algorithm can monitor a good number of objects constantly over time.

We consider the problem of allocating clients to base stations in wireless networks. Two design decisions are the location of the base stations, and the power levels of the base stations. We model the interference, due to the increased power usage resulting in greater serving radius, as capacities that are non-increasing with respect to the covering radius. Clients have demands that are not necessarily uniform and the capacity of a facility limits the total demand that can be served by the facility. We consider three models. In the first model, the location of the base stations and the clients are fixed, and the problem is to determine the serving radius for each base station so as to serve a set of clients with maximum total profit subject to the capacity constraints of the base stations. In the second model, each client has an associated demand in addition to its profit. A fixed number of facilities have to be opened from a candidate set of locations. The goal is to serve clients so as to maximize the profit subject to the capacity constraints. In the third model, the location and the serving radius of the base stations are to be determined. There are costs associated with opening the base stations, and the goal is to open a set of base stations of minimum total cost so as to serve the entire demand subject to the capacity constraints at the base stations. We show that for the first model the problem is NP-complete even when there are only two choices for the serving radius, and the capacities are 1,2. For the second model, we give a 1/2 approximation algorithm. For the third model, we give a column generation procedure for solving the standard linear programming model, and a randomized rounding procedure. We establish the efficacy of the column generation based rounding scheme on randomly generated instances.

We propose a cellular automaton based local algorithm to reposition mobile sensors of a wireless sensors network. Our main goal is to maximize the total coverage of the network while maintaining the connectivity among the sensors. In most of the applications, it is not feasible to deploy mobile sensors using a global algorithm. Typically, the sensors are initially densely deployed and use their mobility to increase the coverage of the network. Our algorithm uses very limited local information to compute the final positions of the sensors. In many applications, maximizing the coverage is not the only objective; the sensors also need to communicate with each other. Therefore, maintaining connectivity when the sensors disperse is an important goal, and our algorithm achieves this as well. We perform different simulations on different starting configurations. For some configurations, the optimal solution is arrived at, while for others a near optimal solution is obtained.

We design new cellular automaton based algorithms to improve coverage in a network with mobile sensors. The algorithms can be useful in applications where sensors are initially deployed in one place and need to disperse to the environment autonomously, or in situations where in certain areas sensors may be destroyed (e.g. due to a natural disaster), and the sensors need to use their mobility in order to restore coverage. We propose a cellular automaton model that divides the neighborhood of a cell into four (North West, North East, South West and South East) quadrants and the sensors try to find out the directions where they can move to increase the coverage. We compared our model with a previous model for different initial configurations and have found that our model reaches a comparable coverage more quickly. Our algorithms use two parameter values to guide the movements of the sensors. Especially with the best choices of the parameter values, our algorithms require the sensors to make considerably fewer atomic movements than the earlier algorithm. For mobile sensor networks, energy consumption is largely determined by the amount of movement, and minimizing movement will increase the life time of the network.

ABSTRACT The number of cellular communication subscribers continues to grow, attesting to the great success of this technology. However, cellular networks have inherent limitations on cell capacity and coverage and shortcomings such as the dead spot and the hot spot problems. Multi‐hop cellular networks (MCNs) help enhance the cell capacity and coverage, while, at the same time, alleviating the dead spot and hot spot problems, increasing the utilization of radio resource, and reducing the power consumption of mobile terminals. In the past decade, more than a dozen of MCN architectures were proposed. In this paper, we study various types of MCN proposals. We identify and discuss the design decision factors and use these factors to classify most existing MCN proposals. Future research directions, including studies of capacity and energy consumption, and approaches addressing design issues such as cell size, routing, channel assignment, load balancing for MCNs are discussed. Copyright © 2010 John Wiley & Sons, Ltd.

Abstract Cryptographic key management (CKM) schemes can be used to support identity management (IM) systems where linking users securely to data objects is important. CKM schemes enforce data security by encrypting data granting access only to authorized users and security compromises are prevented by updating any keys that are held by users from whom access rights have been revoked. Handling key updates efficiently and providing security against collusion attacks is challenging in dynamic environments like the Internet where manual Security management increases the likelihood of delayed responses. Delay increases the system's vulnerability to security attacks and the potential of the system's violating its service level agreements. Adaptive CKM has emerged as a possibility of addressing this problem but needs to be designed in a way that justifies the cost/benefit tradeoff. In this paper, we show that the key update and collusion avoidance problems are NP‐complete and need heuristic algorithms to prevent performance degradations in comparison to standard CKM schemes. As an example of the benefits of a good heuristic, we present a collusion detection and resolution algorithm whose running time is polynomial in the number of keys. The algorithm operates by mapping the generated key set onto a key graph whose independent set is computed. In the key graph, the vertices represent the keys and the edges the probability that their endpoints can be combined to provoke a collusion attack. Collusion possibilities are resolved by applying a heuristic that resets the probability to zero. The performance of our algorithm is analyzed in comparison to the Akl and Taylor scheme that is secure against collusion attack, and the experimental results indicate that collusion prevention can be done dynamically without affecting performance. Copyright © 2010 John Wiley & Sons, Ltd.

We study the problem of computing an energy-efficient data delivery scheme in wireless sensor networks that leverages the knowledge of a set of trajectories of mobile sinks in the network to route data from the sensors to the mobile sinks. Sensors collect data from the environment and instead of directly sending them to the mobile sinks (henceforth simply “sinks”), they route data to a number of selected nodes (we call them relay or stashing nodes) in the network. These stashing nodes lie on the trajectories of the sinks, and relay the received data directly to the sinks on behalf of the sensors. Assuming a set of p different applications being executed on each sensor node, we consider the following problem: Given a set of p trajectories T1, T2, ..., TPcorresponding to p sinks, where sink Ti is dedicated to collect i-th application data, node u selects at least k stashing nodes from Tisuch that it can forward at least k copies of its i-application data to them. The goal of u is to minimize the total routing cost to send all its p application data to the corresponding stashing nodes of p trajectories. We use the expected number of transmissions on a link as the routing cost of the link and the routing cost for a path is the sum of all the link costs of that path. We wish to minimize the sum of the total routing costs of all the nodes. We call this the Minimum Cost Stashing problem and formulate this as a primal-dual problem. We present a 1/2(2f -k + 1)-approximation algorithm using the primal-dual method for approximation algorithms, where f is the maximum size of a trajectory.

Multihop cellular networks (MCNs) enhance the capacity and coverage and alleviate the dead-spot and hot-spot problems of cellular networks. They also allow faster and cheaper deployment of cellular networks. A fundamental issue of these networks is packet delay because multihop relaying for signals is involved. An effective channel assignment is the key to reducing delay. In this paper, we propose an optimal and a heuristic channel assignment scheme, called OCA and minimum slot waiting first (MSWF), respectively, for a time division duplex (TDD) wideband code division multiple access (W-CDMA) MCN. OCA provides an optimal solution in minimizing packet delay and can be used as an unbiased or benchmark tool for comparison among different network conditions or networking schemes. However, OCA is computationally expensive and, thus, inefficient for large real-time channel assignment problem. In this case, MSWF is more appropriate. Simulation results show that MSWF achieves on average 95 percent of the delay performance of OCA and is effective in achieving high throughput and low packet delay in conditions of different cell sizes.

In 3G-based multihop cellular networks (MCNs), the cell size affects the cell capacity and the network reachability, which in turn affect the total demand of source nodes that can be served or the system throughput. Improper cell size assignment greatly affects the performance of the networks. To address the cell size issue, we recently proposed the optimal cell size (OCS) scheme to find optimal cell sizes to maximize the system throughput for a 3G TDD W-CDMA MCN. Although OCS provides an optimal cell size solution, it is computationally expensive. In this paper, we propose a heuristic cell size scheme, called Small Cell Size First (SCSF), which is more efficient and provides good results in terms of throughput compared to the optimal solutions provided by OCS. SCSF outperforms the fixed small cell size (SCS) multi-hop case when the network is sparse and the large cell size single-hop case regardless of the network density.

In this paper, we propose a distributed scheme for data gathering using a mobile data collector in wireless sensor networks (WSNs). In our scheme, a mobile data collector moves along a predefined track over the sensing field and data are forwarded to nodes whose transmission disks overlap with the trajectory of the data collector; these nodes are called relaying nodes. Data are classified into two categories: delay-sensitive data and delay-tolerant data. While delay-sensitive data are sent to the data collector directly, delay-tolerant data may be sent to a nearby relaying node, where they wait for the data collector to come and pick them up. We give a theoretical analysis to quantify the impact of data collector mobility on the lifetime of the network as compared to a WSN with a stationary data collector. Moreover, we use simulations to evaluate our scheme in practice. Simulation results show that our scheme has the potential to prolong the lifetime of the network significantly.

Distributing sensing and data gathering tasks to a dominating set is an attractive choice in wireless sensors networks since it helps prolong network lifetime by engaging such a subset of nodes for these tasks and letting other nodes go into energy-efficient sleep mode. Because they are busy all the time for sensing, processsing, and transmitting data, nodes in the dominating set quickly run out of energy. One possible way to overcome this situation is to find a number of dominating sets among the nodes of the network and use them one by one iteratively. In this paper, we investigate the problem of finding the maximum number of disjoint dominating sets called the domatic partition problem in unit disk graphs. Although the domatic partition problem is NP-hard in general graphs, it is unknown whether the same is true for unit disk graphs. However, we present an algorithm towards solving this problem (approximately) together with experimental results and give a conjecture based on our results about the maximum number of disjoint dominating sets in unit disk graphs.

3G-based Multi-hop cellular networks (MCNs) inherit a special characteristic of 3G systems, namely the relationship between a cell's coverage and its capacity. At the planning stage, a cell may be statically set to have small coverage with high capacity, a large coverage with small capacity, or some other fixed settings in between. Such static settings, however, do not adapt to the projected dynamic nature of users in 3G-especially in an MCN environment. In this paper, we propose the Optimal Cell Size (OCS) scheme for a 3G TDD W-CDMA MCN multi-cell environment. Given the cell capacity function, users' distribution and demands, OCS yields optimal cell sizes that maximize the system throughput through balancing coverage and capacity. Not only can OCS cope with dynamic network conditions, but it can also be considered as an aid to the network planning process. To the best of our knowledge, this is the first multi-cell optimal cell size scheme in the context of MCNs.

For the sake of maximizing the network lifetime, we propose a novel placement scheme for mobile data collectors in underwater acoustic sensor networks (UASNs). Our scheme is based on a 3D architecture, in which on-the-surface data collectors gather data from underwater sensors and relay them to an on-shore sink. We divide the lifetime of the network into fixed length rounds and move the data collectors to new locations at the beginning of each round. We formulate the problem as an integer linear program (ILP) and use an ILP solver to find the optimal placement of data collectors together with the multi-hop routing paths to deliver data from underwater sensors to data collectors. Our work is a pioneering effort in the placement of mobile data collectors in three-dimensional UASNs. Comprehensive experiments show that our scheme prolongs the lifetime of the network significantly as compared to other data collector placement schemes.

Connected dominating sets (CDSs) are probably the most common way of constructing virtual backbones for broadcasting operation in wireless sensor networks. This is because such backbones guarantee to reduce unnecessary message transmissions or flooding in the network. In this paper we propose a simple localized algorithm to construct a small-sized CDS. Considering the sensors deployed in the plane, our main idea is based on the computation of convex hulls of sensor nodes (nodes are considered points in the plane) in a localized manner and a simple coloring scheme, which produces a CDS in unit disk graphs whose size is at most 38*|MCDS| where |MCDS| is the size of a minimum CDS. To the best of our knowledge, this is a significant improvement over the best published results in the same context [5]. We also analyze grids and trees to compute the exact approximation ratios for the problem. We show that our algorithm produces an optimal CDS if the graph is a tree and in the case of grids the approximation factor is 2.

We propose a scheme for routing and placement of mobile data collectors in Underwater Acoustic Sensor Networks (UASNs). The proposed scheme maximizes the lifetime of the network with an upper bound on the maximum delay. We assume a 3D architecture, in which on-the-surface data collectors gather data from underwater sensors and relay them to an on-shore sink. We divide the lifetime of the network into fixed length rounds and move the data collectors to new locations at the beginning of each round. This problem is formulated as an Integer Linear Program (ILP), and we use an ILP solver to find the optimal placement of data collectors together with the multi-hop routing paths to deliver data from underwater sensors to data collectors. To the best of our knowledge, this is the first attempt towards the placement of data collectors in a 3D environment with delay constraints. When compared with other schemes, our scheme has shown the capability to achieve longer lifetime and shorter delay.

We present, for the first time, a formal model for the general problem of uplink scheduling of a set of packets with various QoS classes and soft or hard deadlines. Our goal is to maximize the value of packets to be sent in uplink such that the expectations from the system are guaranteed. We use our general model and the properties of the application to derive an algorithm which has two highly favorable features: it finds the globally optimal solution in logarithmic time. We also present a method to fine-tune our general model. This approach guarantees that the optimal algorithm for the model is indeed the optimal scheduler for the system. Simulation results demonstrate the effectiveness of our algorithms.

We present, for the first time, a formal model for the general problem of uplink scheduling of a set of packets with various QoS classes and soft or hard deadlines. Our goal is to maximize the number of packets to be sent in uplink such that the expectations from the system are guaranteed. We use our general model and the properties of the application to derive an algorithm which has two highly favorable features: it finds the optimal solution in linear time. Finally, we present a method to fine-tune our general model in order to make sure that the model represents the actual system. This approach guarantees that the optimal algorithm for the model is indeed the optimal scheduler for the system.

Shared data access maximizes resource utilization on the Internet but raises the issue of data security. We consider a method of shared data access control whereby the data is sub-divided into categories and each encrypted with a unique cryptographic key that is distributed to the user group requir ing access. Key management can be simplified by classifying every user into exactly one of a number of disjoint groups that are partially ordered such that lower level keys are mathematically derivable from higher level keys, but not the reverse. The drawback in this approach is that changes in group membership imply updating both the affected group key and those that are derivable from it. Moreover, the data encrypted with the affected keys must be re-encrypted with the new keys to preserve data security. In the worst case, when the affected group is at the highest level of the hierarchy, the entire hierarchy is affected. This paper presents an algorithm that minimizes the cost of key replacement (rekeying) by associating a timestamp to each key. The timestamp and key are used to compute a verification signature that is used to authenticate users before data access is granted. Thus, whenever group membership changes, instead of rekeying and re-encrypting the affected data, only the timestamp is updated and a new verification signature computed. The new scheme is analyzed using both a time complexity and experimental analysis.

Abstract We propose two schemes for routing and placement of mobile data collectors in underwater acoustic sensor networks (UASNs): the delay tolerant placement and routing (DTPR) and the delay constrained placement and routing (DCPR). As their names reveal, while the DTPR maximizes the lifetime of the network without any delay considerations, the DCPR maximizes the lifetime of the network with an upper bound on the maximum delay. Both schemes are based on a 3D architecture, in which on‐the‐surface data collectors gather data from underwater sensors and relay them to an on‐shore sink. We divide the lifetime of the network into fixed length rounds and move the data collectors to new locations at the beginning of each round. These problems are formulated as integer linear programs (ILPs), and we use an ILP solver to find the optimal placement of data collectors together with the multi‐hop routing paths to deliver data from underwater sensors to data collectors. Our work is a pioneering effort in the placement of mobile data collectors in three‐dimensional UASNs. Comprehensive experiments show that our schemes prolong the lifetime of the network significantly as compared to other data collector placement schemes. Copyright © 2008 John Wiley & Sons, Ltd.

A typical task in many applications for vehicular networks is to disseminate information to a subset of vehicles on a highway. In this work we describe a theoretical estimation for the average number of such independent tasks that can be sustained concomitantly in ad-hoc vehicular networks using contention free medium access and a fixed number of wireless channels. We call this measure the vehicle to vehicle (V2V) capacity of the network. Using our estimation, we perform an analysis of the V2V network capacity under different highway traffic conditions and scenarios. A surprising conclusion drawn is that congestion actually determines an increase in capacity. Based on these observations, we propose a simple strategy that can increase the capacity by filtering communication tasks with length greater than a certain threshold which can be determined numerically.

Wireless networks have made great gains in usability and popularity. However, inherent limitations on cell capacity and coverage still exist. There are also dead-spots and hotspots problems in these networks. Ad hoc multi-hop relaying enhances cell capacity and coverage, alleviates the dead-spots problem, and helps to ease congestion in hotspots. However, multi-hopping also increases packet delay. Effective channel assignment is key to reducing delay. Existing channel assignment schemes are heuristics and may not guarantee optimal solutions in terms of minimum delay. In this paper, we provide an optimal channel assignment (OCA) scheme for ad hoc TDD W-CDMA multi-hop cellular networks (MCN) to minimize packet delay. OCA can also be used as an un-biased tool for the comparison among different network topologies, network densities, and protocols. To the best of our knowledge, this is the first time that a minimum delay optimal channel assignment is proposed in a multi-hop cellular environment.

In this paper, a workflow scheduling approach, which consists of two algorithms, is proposed. A submitted workflow is first partitioned into subgraphs on the global Grid level by the graph partitioning algorithm according to features of the workflow itself and the status of selected available resource clusters. Then, at the resource cluster level, metatasks in each subgraph are allocated to computational resources by the metatask mapping algorithm. To reduce the total makespan of a workflow, the schedule of raw input data preloading are considered by the two algorithms. This two-phase approach does not require detailed resource information or control privilege on every Grid resource for Grid schedulers at the global Grid level, so that the dependence on Grid information services is reduced and the higher priority of local resource management policies is respected.

Resource performance in the computational grid is not only heterogeneous, but also changing dynamically. However scheduling algorithms designed for traditional parallel and distributed systems, such as clusters, only consider the heterogeneity of the resources. In this paper, a workflow scheduling algorithm, called PFAS, is proposed and tested in the grid environment. PFAS considers dynamic resource performance fluctuation in the grid, and conducts the scheduling according to its knowledge of the fluctuation. This new algorithm works in an offline way which allows it to be easily set up and run with less cost. Simulations show that our approach can achieve better schedules than the HEFT algorithm.

Many mission-critical applications of wireless sensor networks generate traffic that have a stringent delay requirement. In this paper, we study the effects of relaying delay- constrained traffic in a wireless sensor network according to two different strategies. The first strategy allows traffic splitting, in which data flow can be split and sent on multiple paths from the source to the destination. The second strategy disallows traffic splitting, in which data flow cannot be split and must be sent on a single path from the source to the destination. We present a model based on linear and integer linear programming for finding an optimal allocation of splittable and unsplittable traffic in a wireless sensor network, in which traffic is subject to soft delay constraints. The objective is to minimize the total energy consumption spent on communication and the penalty incurred from the violation of delay constraints. Based on this model, we perform an empirical analysis to quantify the performance gains and losses of a splittable and unsplittable traffic allocation strategy for wireless sensor networks with delay-constrained traffic. The experiment results show that splitting traffic does not provide a significant advantage in energy consumption, but can afford strategies for relaying data with a lower delay penalty.

Energy is often considered the primary resource constraint in a wireless sensor network. Compared to sensing and data processing, the cost of communication is among the highest in energy consumption. In this paper, we study the effects of relaying data in a wireless sensor network according to two different strategies. The first strategy allows traffic splitting, in which data can be sent on multiple paths from the source to the destination. The second strategy disallows traffic splitting, in which data must be sent on a single path from the source to the destination. We present algorithms based on linear and integer programming for finding an optimal allocation of splittable and unsplittable traffic in a wireless sensor network that minimizes total energy consumption. The technique provides optimal solutions, and can be used by designers of communication protocols to assess the energy efficiency of a data relaying scheme for a given network configuration. We also perform an empirical analysis to quantify the comparative performance gains and losses of a splittable and unsplittable traffic allocation strategy for wireless sensor networks. Results show that although the energy savings of a splittable traffic allocation strategy is relatively small when compared to the unsplittable case (on average, ranging from 0% to 1.82%), an allocation of splittable traffic can tolerate up to an additional 14.1% increase in network traffic load until any further load increase returns no feasible solutions.

Multi-hop relaying is an important concept in tackling the inherent problems of limited capacity and coverage in cellular networks. It helps to solve the dead-spots problem and to ease congestion in hotspots. However, to obtain good performance of multi-hop relaying, an effective channel assignment scheme is needed. In this paper, we study the design goals of a good channel assignment scheme. We then propose a channel assignment scheme, called Extended Delay-Sensitive Slot Assignment (E-DSSA), which achieves all these goals. The distinctive feature of E-DSSA is the use of a novel transmission zone testing technique which allows high flexibility and precision in channel assignment in TDD W-CDMA multi-hop cellular environment. Performance evaluation shows that E-DSSA outperforms its existing counterparts in terms of data throughput with low delay for both sparse and dense networks. E-DSSA is also shown to adapt to different cell sizes achieving high throughput and call acceptance ratios.

Multi-hop relaying is an important concept in future generation wireless networks. It can address the inherent problems of limited capacity and coverage in cellular networks. However, most multi-hop relaying architectures are designed based on a small fixed-cell-size and a dense network. In a sparse network, the throughput and call acceptance ratio degrades because distant mobile nodes cannot reach the base station to use the available capacity. In addition, a fixed-cell-size cannot adapt to the dynamic changes of traffic pattern and network topology. In this paper, we propose a novel multi-hop relaying architecture called the adaptive multi-hop cellular architecture (AMC). AMC adapts the cell size to an optimal value that maximizes throughput by taking into account the dynamic changes of network density, traffic patterns, and network topology. To the best of our knowledge, this is the first time that adaptive (or optimal) cell size is accounted for in a multi-hop cellular environment. AMC also achieves the design goals of a good multi-hop relaying architecture. Simulation results show that AMC outperforms a fixed-cell-size multi-hop cellular architecture and a single-hop case in terms of data throughput, and call acceptance ratio

In this paper, the concern is with the management of data traffic after node deployment. To address some of the shortcomings of both single and multihop communication, this paper work with a hybrid model. The WSNet architecture is comprised of three classes of sensor nodes, sensors, relay nodes, and relay gateways. Sensors - gather and send data values to one relay nodes. Relay nodes - receive data values from sensors and/or other relay nodes and forward them to relay nodes or relay gateways. Relay gateways - receive data values from RN and send them directly (in one hop) to the base station, possibly using a dedicated channel. Our goal is to select paths along which data packets can be relayed until they reach one or more relay gateways while satisfying several constraints. These decisions take place at the application level, are computed by a central algorithm running at the base station, and rely on routing protocols to deliver the messages. A fixed topology of directly communicating nodes were assumed and a long term data communication plan based on knowing the amount of data generated by sensor nodes. The optimality of the solution obtained was guaranteed

Since the emergence of mobile computing, reducing energy consumption of battery-operated computing devices has become a very active research area. The widespread popularity of mobile computing devices, such as laptops, handheld devices and cell phones, motivates this research area. Several hardware based techniques have been proposed; this has led to more energy-efficient systems. Nevertheless, it is presumed in the literature of energy-aware design that software based techniques have the potential to reduce energy demand and contribute to solve the problem. In this paper, we look into the problem of distributing computational tasks amongst a set of mobile computing devices in a mobile wireless ad hoc network (MANET) in such a way that reduces the total consumed energy. In such a distributed environment, the assignment of computational tasks to different devices plays a vital role in energy conservation. The main contributions of this paper are formulating a novel energy-aware allocation problem and proposing a heuristic-based greedy algorithm to solve it approximately. Our allocation algorithm assigns a set of computational tasks, which may communicate with each other, into a set of heterogeneous processors in such a way that minimizes the total consumed energy. Experiments show that our algorithm is near-optimal in most of the tested benchmarks.

The k-ary n-cube has been used as the underlying topology for most practical multicomputers, and has been extensively studied in the past. We investigate some properties of this network. In particular, we study the problem of finding the number of nodes located i hops away from a given node (surface area) and the number of nodes located within i hops away from a given node (volume) in both the unidirectional and bidirectional k-ary n-cube, and have derived exact expressions calculating these numbers. These results are very useful when studying, for example, the spanning tree structure of the k-ary n-cube and the problem of resource placement in this network.

The concept of "real-time" has different meanings in the systems and theory communities. As a consequence, the currently available formal real-time models do not capture all the practically relevant aspects of such computations. We propose a new definition, and we believe that it allows a unfied treatment of all practically meaningful variants of real-time computations. Then, we use the developed formalism to model two important features of real-time algorithms, namely the presence of deadlines and the real-time arrival of input data. We also emphasize the expressive power of our model by using it to formalize aspects from the areas of real-time database systems and ad hoc networks. We offer formulations of the recognition problem for real-time database systems and the routing problem in ad hoc networks. Finally, we suggest a variant of our formalism that is suited for modeling parallel distributed real-time algorithms. We believe that the proposed formalism is a first step towards a unified and realistic complexity theory for real-time parallel computations.

No abstract available.

This paper introduces a parallel algorithm for computing an N=n!-point Lagrange interpolation on an n-star (n>2). It exploits several communication techniques on stars in a novel way which can be adapted for computing similar functions. The algorithm is optimal and consists of three phases: initialization, main and final. While there is no computation in the initialization phase, the main phase is composed of n!/2 steps, each consisting of four multiplications, four subtractions and one communication operation, and an additional step including one division and one multiplication. The final phase is carried out in (n-1) sub-phases each with O(log n) steps where each step takes three communications and one addition.

A recursive algorithm GenWordsR and a non-recursive algorithm GenWordsNR are presented in this paper to generate sequences for regular k-ary trees efficiently. They are compared with some of the previous recursive and non-recursive algorithms for this problem that were found in the literature. When the average number of recursive calls is used as a measure of the time complexity of recursive algorithms for generating k-ary trees, O(k) calls for a k-ary tree is the bestresult in the previous recursive algorithms, while O(1/k) calls for a k-ary tree is needed by GenWordsR. When the average number of comparisons is used as a measure of the time complexity of non-recursive algorithms for generating k-ary trees, GenWordsNR outperforms the previous non-recursive algorithms. As k increases, the number (and the average number) of comparisons performed by GenWordsNR tends to 66% that of the best previous non-recursive algorithms.

BSR (Broadcasting with Selective Reduction) is a PRAM more powerful than any CRCW PRAM. In order to extend the Broadcast Instruction of BSR and make it more useful for a large class of applications, this article permits it to use a general form of selection, specifically, an arbitrary relational expression. BSR with general selection is denoted by BSR/sup +/. Thus, BSR or BSR with k criteria (k>1) is BSR/sup +/ in a special case. An efficient implementation for the Broadcast Instruction of BSR/sup +/ is proposed, requiring (1/k)th of the circuits used by the best previous implementation of BSR with k criteria. Of all PRAMs, BSR/sup +/ is the most powerful in computation.

Data communication and fault tolerance are important issues in parallel computers in which the processors are interconnected according to a specific topology. One way to achieve fault tolerant interprocessor communication is by exploiting the disjoint paths that exist between pairs of source and destination nodes. We construct n-1 directed edge disjoint spanning trees on the star network. These spanning trees are used to derive a near optimal single node broadcasting algorithm, and fault tolerant algorithms for the single node and multinode broadcasting, and for the single node and multinode scattering problems. Broadcasting is the distribution of the same group of messages from one processor to all the other processors. Scattering is the distribution of distinct groups of messages from one processor to all the other processors. We consider broadcasting and scattering from a single processor of the network and simultaneously from all processors of the network. The single node broadcasting algorithm offers a speed up of n-1 for a large number of messages, over the straightforward algorithm that uses a single shortest path spanning tree. Fault tolerance is achieved by transmitting the same messages through a number of edge disjoint spanning trees. The fault tolerant algorithms operate successfully in the presence of up to n-2 faulty nodes or edges in the network. No prior knowledge of the faulty nodes or edges is required. All of the algorithms operate under the store and forward, all port communication model.

Given a graph induced by an even number of points on the plane, the minimum weight matching problem calls for finding a pairing of all the points such that the sum of the distances between the paired points is the smallest possible. In this paper, we propose a parallel algorithm for this problem. The algorithm is designed for the EREW PRAM model of parallel computation with p processors. For points on the Euclidean and manhattan planes, the algorithm executes in O((n2.5log4n)/p) time, where p ≤ n0.5. The algorithm provides an optimal speedup with respect to the fastest existing sequential algorithm. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The n-star graph, denoted by S/sub n/, is one of the graph networks that have been recently proposed as attractive alternatives to the n-cube topology for interconnecting processors in parallel computers. We present a parallel algorithm for the computation of the Fourier transform on the star graph. The algorithm requires O(n/sup 2/) multiply-add steps for an input sequence of n! elements, and is hence cost-optimal with respect to the sequential algorithm on which it is based. This is believed to be the first algorithm, and the only one to date, for the computation of the Fourier transform on the star graph.>

Abstract The star and pancake networks were recently proposed as attractive alternatives to the hypercube topology for interconnecting processors in a parallel computer. However, few parallel algorithms are known for these networks. In this paper, we present several data communication schemes and basic algorithms for these two networks. These algorithms are then used to develop parallel solutions to various computational geometric problems on both networks. Computational geometry is just one area where the algorithms proposed here can be applied. Indeed, we believe that these algorithms are interesting and important in their own right and are fundamental to the design of solutions on the star and pancake networks to a host of other problems. © 1993 by John Wiley & Sons, Inc.

A model of parallel computation called broadcasting with selective reduction (BSR) can be viewed as a concurrent-read concurrent-write (CRCW) parallel random access machine (PRAM) with one extension. An additional type of concurrent memory access is permitted in BSR, namely the BROADCAST instruction by means of which all N processors may gain access to all M memory locations simultaneously for the purpose of writing. At each memory location, a subset of the incoming broadcast data is selected and reduced to one value finally stored in that location. For several problems, BSR algorithms are known which require fewer steps than the corresponding best-known PRAM algorithms, using the same number of processors. A circuit is introduced to implement the BSR model, and it is shown that, in size and depth, the circuit presented is of the same order as an optimal circuit implementing the PRAM. Thus, if it is reasonable to assume that CRCW PRAM instructions execute in constant time, the assumption of a constant time BROADCAST instruction is no less reasonable.>

Two arrays of numbers sorted in nondecreasing order are given: an array A of size n and an array B of size m, where n>

Classification constraints are rules for assigning access classes to data when they are entered into a database. In order that a given set of constraints specify meaningful classes, they should be consistent, that is, not define conflicting classes for the same data; and complete, that is, assign a class to all data. This paper gives algorithms for checking the consistency and completeness of a set of classification constraints defined on a database schema. The techniques use computational geometry to compute intersecting regions in a multidimensional space, where each region is defined by a classification constraint or integrity constraint.

Three new adaptive and cost-optimal parallel algorithms are described for the problems of enumerating permutations and combinations of m out of n objects. The algorithms are designed to be executed on a very simple model of parallel computation which consists of k autonomous processors running synchronously without needing to communicate among themselves. For the first two algorithms, I ≤ k ≤ N, where N is the number of permutations or combinations to be enumerated. When I ≤ k ≤ N/n, both algorithms require 0([N/k]· m) time for an optimal cost of 0(N.m). The third algorithm is designed for the case where m = n and I ≤ k ≤ n. It runs in 0([n!/k] · m) time for an optimal cost of 0(n!.n).

A parallel algorithm is described for merging two sorted vectors of total length N. The algorithm runs on a shared-memory model of parallel computation that disallows more than one processor to simultaneously read from or write into the same memory location. It uses k processors where l ≤ k ≤ N and requires O(N/k + log k × log N) time. The proposed approach for merging leads to a parallel sorting algorithm that sorts a vector of length N in O(log2k + N/k) log N) time. Because they modify their behavior and hence their running time according to the number of available processors, the two new algorithms are said to be self-reconfiguring. In addition, both algorithms are optimal, for k ≤ N/log2N, in view of the Ω(N) and Ω(N log N) lower bounds on merging and sorting, respectively.

Because views on relational database systems mathematically define arbitrary sets of stored and derived data, they have been proposed as a way of handling context-and content-dependent classification, dynamic classification, inference, aggregation, and sanitization in multilevel database systems. This paper describes basic view concepts for a multilevel-secure relational database model that addresses the above issues. All data entering the database are labeled according to views called classification constraints, which specify access classes for related data. In addition, views called aggregation constraints restrict access to aggregates of information. All data accesses are confined to a third set of views called access views.

Because views on relational database systems mathematically define arbitrary sets of stored and derived data, they have been proposed as a way of handling context- and contenbdependent classification, dynamic classification, inference, aggregation, and sanitization in multilevel database systems. This paper describes basic view concepts for a multilevelsecure relational database model that addresses the above issues. The model treats stored and derived data uniformly within the database schema. All data in the database is classified according to views called classification constraints, which specify security levels for related data. In addition, views called aggregation constraints specifies classifications for aggregates that are classified higher than the constituent elements. All data accesses are confined to a third set of views called access views, which higher than their declared filter out all data classified view level.

A cryptographic scheme for controlling access to information within a group of users organized in a hierarchy was proposed in [1]. The scheme enables a user at some level to compute from his own cryptographic key the keys of the users below him in the organization.

This paper addresses one aspect of the problem of access control in a hierarchy. A general scheme is described which allows a user to generate from his own key the keys of users below him in the hierarchy. Two implementations of this scheme are then proposed and compared in terms of security and efficiency to an existing one.

A scheme based on cryptography is proposed for access control in a system where hierarchy is represented by a partially ordered set (or poset).Straightforward implementation of the scheme requires users highly placed in the hierarchy to store a large number of cryptographic keys.A timeversus-storage trade-off is then described for addressing this key management problem.

A brief comparative analysis of existing true and arbitrated digital signatures is presented. A new scheme for obtaining signatures which is a hybrid of conventional and public-key cryptosystems - is then proposed and its properties discussed.

The alpha-beta algorithm for searching decision trees is adapted to allow parallel activity in different parts of a tree during the search. The algorithm has been implemented in a procedural simulation language (GASP IV). The simulation environment provides the illusion of multiple software processes and multiple hardware processors. A number of preliminary experiments have been done to gather statistics on run time, nodes scored, and nodes visited. Results indicate that a substantial reduction in time of search occurs because of the use of parallelism. An analytic expression for the storage requirements of the algorithm is derived. The analysis provides an example of the classical tradeoff between time and storage.

This paper introduces four new digital signature schemes for computer communication networks. These involve one or more arbitrators who validate and authenticate messages and signatures without having access to the actual contents of the messages.

GenerationIt is emptncally shown that the algorithm of Mffsud is the fastest exlstmg combination generator This contradicts recent efficmncy claims concerning other algorithms.