This paper discusses the problem of deploying a minimum number of directional sensors equipped with directional sensing units and directional communication antennas with beam-width ${\theta _c} \geq \frac{\pi }{2}$ such that the set of sensors covers a set of targets P in the 2D plane and the set of sensors forms a symmetric connected communication graph. As this problem is NP-hard, we propose an approximation algorithm that uses up to 3.5 times the number of omni-directional sensors required by the currently best approximation algorithm proposed by Han et al. [1]. This is a significant result since we have broken the barrier of $2\pi /\frac{\pi }{2} = 4$ when switching from omni-directional sensors to directional ones. Moreover, we improve the approximation ratio of the Strip-based algorithm for the Geometric Sector Cover problem proposed by Han et al. [1] from 9 to 7, and we believe that this result is of interest in the area of Computation Geometry. Simulation results show that our algorithms only require around 3 times the number of sensors used by Han et al.’s algorithm and significantly outperform other heuristics in practice.

Recent advances in wireless sensor networks (WSNs) allow directional antennas to be used instead of omni-directional antennas. However, the problem of maintaining (symmetric) connectivity in directional wireless sensor networks (DWSNs) is significantly harder. Contributing to this field of research, in this paper, we study the Antenna Orientation problem in WSNs equipped with k directional antennas (3 ≤ k ≤ 4). Antenna Orientation (AO) is the problem that given a set S of nodes equipped with omni-directional antennas of unit range, the goal is to replace omni-directional antennas by directional antennas with beam-width θ ≥ 0 and to find a way to orient them such that the required range r to yield a symmetric connected communication graph (SCCG) is minimized. For this problem, we propose an O(n log n) time algorithm yielding $r = 2\sin \left( {\frac{{{{180}^\circ }}}{k}} \right)$. Our results show that the proposed algorithms achieve good performance in both theory and practice.

In this paper, we investigate the Antenna Orientation (AO) and Antenna Orientation and Power Assignment (AOPA) problems concerning symmetric connectivity in Directional Wireless Sensor Networks (DWSNs) where each sensor node is equipped with 2 ≤ k ≤ 5 directional antennas having beamwidth θ ≥ 0. The AO problem for DWSNs is closely related with the well-known Euclidean Degree-Bounded Minimum Bottleneck Spanning Tree (EBMBST) problem where different cases for the degree bound have been studied. While current works on DWSNs focus on solving each case of k(=2, 3, 4) separately, we propose a uniform approach for the AO problem that yields constant-factor approximation algorithms for the AO as well as the EBMBST problem where the degree bound is between 2 and 4. Our method achieves the same constant factors. For the AOPA problem, to the best of our knowledge, our paper provides the first results concerning this problem. We show that the problem is NP-hard when 2 ≤ k ≤ 4. We also establish the first constant-factor approximation algorithms for the problem. Finally, we perform some simulations to understand the practical performance of our algorithms.

Consider a set S of nodes in the plane such that the unit-disk graph G(S) spanning all nodes is connected. Each node in S is equipped with a directional antenna with beam-width θ = π/2. The objective of the directional antenna orientation (AO) problem concerning symmetric connectivity is to determine an orientation of the antennas with a minimum transmission power range r = O(1) such that the induced symmetric communication graph is connected. Another related problem is the AO and power assignment (AOPA) problem whose objective is to assign each node u ∈ S an orientation of its antenna as well as a range r(u) such that the induced symmetric communication graph is connected and the total power assigned Σu∈Sr(u)βis minimized, where β ≥ 1 is the distance-power gradient (typically 2 ≤ β ≤ 5). In this paper, we study both problems by first proving that they are NP-hard. We then propose two algorithms for the AO problem that orient the antennas to yield a symmetric connected communication graph where the transmission power ranges are bounded by 9 and 7, respectively, which are currently the best results for this problem. We also propose constant-factor approximation algorithms for the AOPA problem where our constants are smaller than Aschner et al's. Finally, we study the performance of our algorithms through simulations.

Consider a set S of nodes in the plane such that the unit-disk graph G(S) spanning all nodes is connected. Each node in S is equipped with a directional antenna with beam-width θ = π/2. The objective of the Directional Antenna Orientation (AO) problem concerning symmetric connectivity is to determine an orientation of the antennas with a minimum transmission power range r = O(1) such that the induced symmetric communication graph is connected. Another related problem is the Antenna Orientation and Power Assignment (AOPA) problem whose objective is to assign each node u ϵ S an orientation of its antenna as well as a range r(u) such that the induced symmetric communication graph is connected and the total power assigned ΣuϵSr(u)β is minimized, where β ≥ 1 is the distance-power gradient (typically 2 ≤ β ≤ 5). In this paper, we study both problems by first proving that they are NP-hard. To the best of our knowledge, these NP-hardness results have not been obtained before in the literature. We then propose an algorithm for the AO problem that orients the antennas to yield a symmetric connected graph where the transmission power range is bounded by 9 which is currently the best result for this problem. (Previous bound for this problem is 14√2 by Aschner et al). We also propose a constant-approximation algorithm for the AOPA problem where our constant is smaller than the one in Aschner et al's algorithm.

In this paper, we study the Antenna Orientation (AO) problem concerning symmetric connectivity in Directional Wireless Sensor Networks. We are given a set of nodes each of which is equipped with one directional antenna with beam-width θ = 2π/3 and is initially assigned a transmission range 1 that yields a connected unit disk graph spanning all nodes. The objective of the problem is to compute an orientation of the antennas and to find a minimum transmission power range r = O(1) such that the induced symmetric communication graph is connected. We propose an algorithm that orients the antennas to yield a symmetric connected graph where the transmission power range is bounded by 6 which is currently the best result for this problem. We also study the performance of our algorithm through simulation.

In this paper, we study the Minimum Channel Assignment (MCA) problem for strong connectivity in wireless sensor networks in the physical model known as Signal-to-Interference-Noise-Ratio (SINR). The main issue is to compute a minimum channel assignment that yields a strongly-connected communication graph spanning all nodes such that the nodes assigned to the same channel can communicate without interference in the SINR model. The complexity measure is the number of channels, and our objective is to minimize it. We show the NP-hardness of the MCA problem, and propose an algorithm that compute a channel assignment for 2-dimensional grid networks. The algorithm produces an assignment with a constant number of channels for the network. We also propose two constant-factor approximation algorithms that yield channel assignments in which the number of channels is bounded by O(Δ), where Δ is the maximum node degree of a network. We also study the performance of the algorithms through simulation.

Topology control has been used to minimize interference or to reduce power consumption while maintaining connectivity in wireless ad hoc and sensor networks (WSNs)(which are represented as undirected graphs). In the graph model, the interference experienced by an edge in a WSN has been defined in at least two different ways: the sender-based and receiver-based interference models. These models have been extensively studied in the literature although the receiver-based model has received more attention. Recently, several researchers have started investigating interference in the more realistic physical model which is known as the Signal-to-Interference-Noise-Ratio (SINR) model. The SINR model better reflects the real environment than the receiver-based or sender-based graph models. In this paper, we study the problem of assigning power to nodes in the plane to yield a connected network of minimum edge interference in the receiver-based (RB-MEI) as well as the SINR models (SINR-MEI). We show that RB-MEI is NP- complete for geometric graphs. For SINR-MEI, NP- completeness holds for planar geometric graphs. We also propose some simple greedy heuristics based on the minimum spanning tree approach, and study their performance through simulation.

Data aggregation has been the focus of many researchers as one of the most important applications in Wireless Sensor Networks. A main issue of data aggregation is how to construct efficient schedules by which data can be aggregated without any interference. The problem of constructing minimum latency data aggregation schedules (MLAS) has been extensively studied in the literature although most of existing works use the graph-based interference model. In this paper, we study the MLAS problem in the more realistic physical model known as Signal-to-Interference-Noise-Ratio (SINR) where few works exist and algorithms that guarantee theoretical performances are scarce [17, 16]. We first derive an © (log n) approximation lower bound for the MLAS problem in the metric SINR model. We also prove the NP-completeness of the decision version of MLAS in the geometric SINR model. This is a significant contribution as these results have not been obtained before for the SINR model. In addition, we propose a constant factor approximation algorithm whose latency is bounded by O(Δ+R) for the dual power model, where Δ is the maximum node degree of a network and R is the network radius. Finally we study the performance of the algorithms through simulation.

Power consumption is one of the crucial issues in Wireless Sensor Networks (WSNs). It therefore has been the focus of many researchers. An important problem concerning power consumption is how to minimize the number of maximum power nodes while maintaining a desired network topology. As fault tolerance is vitally important in practice, it is desirable that the constructed network topology is k-edge-connected (or k-connected). In this paper, we study the dual power assignment problem for k-edge connectivity (kEDP) in WSNs. While other studies consider only the special case k=2, our goal is to address the general problem. We prove the NP-completeness of kEDP problem in the geometric case and provide a 2-approximation algorithm using linear programming techniques. To our knowledge, this approximation ratio is currently the best one. We also introduce a heuristic whose performance is better compared with an approximation algorithm in [1].

In wireless ad hoc networks, a clustering structure can be a backbone for efficient communications. Simplicity in communications can be achieved when the clusters can more simply communicate with each other. One way to achieve this is to require that the clusterheads be connected. We would also like to be able to adapt quickly to small changes in the network. In graph-theoretic terminology, a minimum set of such clusterheads is a minimum connected d-hop dominating set. In this paper, we show that the problem of adapting minimum connected d-hop dominating sets to local topology changes in wireless ad hoc networks is NP-complete. We then propose a heuristic to adapt a given minimal connected d-hop dominating set to a topology change in the networks. A distributed implementation of the heuristic is also presented.

A mobile ad hoc network may be logically represented as a set of clusters, and the clusterheads form what is known as a dominating set in graph theory. The clusterheads can be used to perform a variety of functions for nodes in their cluster such as channel access, routing, data collection, broadcasting, etc. There have been several heuristics proposed for forming 1-hop as well as d-hop clusters. In d-hop clustering, the value of d, a constant representing the number of wireless hops in ad hoc networks, is a parameter of the heuristic and controls the size of the clusters. The problem of finding a minimum d-hop connected dominating set was shown to be NP-complete in [9], where the authors raised the question of whether the problem is still NP-complete for the restricted model of unit disk graphs. In this paper, we provide an affirmative answer to this open question. In fact, we show that the minimum d-hop connected dominating set problem is NP-complete for planar unit disk graphs with maximum degree 4. We also review some known 1-hop heuristics that we generalize to the d-hop case and compare their performance. The experimental results show that the algorithm proposed in [9] is the most efficient one.

By grouping neighboring stations into clusters, a clustering architecture could provide a good infrastructure for efficient channel access and packet routing. Unfortunately, existing cluster formation algorithms to construct minimal sets of clusters have to be rerun on the entire network even if there is a small change in the topology. This wastes communication bandwidth and delays user data transmission. In graph-theory terminology, a minimum set of clusterheads in an ad hoc network is precisely a minimum dominating set. In this paper, we show that the problem of adapting a minimum d-hop dominating set to a simple topology change in ad hoc networks is NP-complete. We then propose a heuristic to adapt a given dominating set in an ad hoc network to a simple topology change by looking only at a small local area around the change. We perform some experiments to show that the proposed heuristic performs consistently almost as well as the rerun approach. We also discuss an efficient distributed implementation of our heuristic.

Software architectural design is becoming increasingly important in software engineering, as being manifested through various recent developments in the field such as the component-based software engineering paradigm and the distributed and collaborative computing paradigm. Abstraction is such a mechanism as the key concept underpinning software architecture, namely hiding the immense amount of details. Despite its long-recognized benefits, however abstraction can also pose difficulties with the understanding and analysis of software architecture since one architecture can result in potentially an infinite number of different system behaviors. In order to alleviate such difficulties, we introduce the notion of dynamic software architecture slicing (DSAS), a methodology for using the notion, and an algorithm to generate dynamic software architecture slice. We demonstrate the feasibility and the expected benefits of the approach by using an illustrative example.

Most existing algorithms that maximize throughput in packet radio networks by selecting a maximal broadcasting set in each time slot of a TDMA frame cannot accommodate changes in the topology of the network. In fact, when there is a change in the network topology, these algorithms have to be rerun for the entire network to compute a new broadcasting set. This is certainly time and bandwidth consuming. In this paper, we show that the problem of adapting a maximum broadcasting set to a simple topology change in packet radio networks is NP-complete. We then propose a new heuristic that adapts a given broadcasting set to topological changes caused by the addition of new radio stations to the network. We do some experiments to show that the performance of our heuristic is almost as good as rerunning the original heuristic for the entire network. We also discuss a distributed implementation of our heuristic.

This paper shows that the membership problems for two subclasses of polynomial ideals are NP-hard. The first subclass is defined by bounding the number of variables ($ \leqq 4$), whereas the second is defined by considering polynomials of the form $Y - M$, where Y is a variable and M is a monomial.

In this note we investigate some connections between hard languages and random languages. We show that there exist languages that are both hard and random. We also show that every EXPTIME-hard language is polynomial-time weakly random.

This paper shows that the equivalence problems for commutative semigroups and symmetric vector addition systems are decidable in space cNlogN for some fixed constant c, solving an open question by Cardoza, Lipton, Mayr, and Meyer. From the exponential-space completeness of the word problems, it follows that our upper bound is nearly optimal.