Journal of Interconnection Networks

Waldvogel et al.⁹ have proposed a collection of hash tables (CHT) organization for an IP router table. Each hash table in the CHT contains prefixes of the same length together with markers for longer-length prefixes. IP lookup can be done with O(log l_dist) hash-table searches, where l_dist is the number of distinct prefix-lengths (also equal to the number of hash tables in the CHT). Srinivasan and Varghese⁸ have proposed the use of controlled prefix-expansion to reduce the value of l_dist. The details of their algorithm to reduce the number of lengths are given in [7]. The complexity of this algorithm is O(nW²), where n is the number of prefixes, and W is the length of the longest prefix. The algorithm of [7] does not minimize the storage required by the prefixes and markers for the resulting set of prefixes. We develop an algorithm that minimizes storage requirement but takes O(nW³ + kW⁴) time, where k is the desired number of distinct lengths. Also, we propose improvements to the heuristic of [7].

Efficient routing among a set of mobile hosts is one of the most important functions in ad hoc wireless networks. Routing based on a connected dominating set is a promising approach, where the search space for a route is reduced to the hosts in the set. A set is dominating if all the hosts in the system are either in the system are either in the set or neighbors of hosts in the set. In this paper, we first review a distributed formation of a connected dominating set called marking process and dominating-set-based routing. Then we propose several ways to reduce the size of the dominating set and study the locality of dominating set and study the locality of dominating set in ad hoc wireless networks with switch-on/off operations. Results show that the dominating set derived from the marking process exhibits good locality properties; i.e., the change of a host status, gateway (dominating) or non-gateway (dominated), affects only the status of hosts in a restricted vicinity. In addition, locality of host status updated is also verified through simulation.

Energy-efficient communication is critical for increasing life of power limited wireless ad hoc networks. There has been considerable interest in minimum energy broadcast operations. In this paper, we develop bounds and an algorithm for minimizing energy cost for broadcasting from any source to all other nodes in the network. Most prior work have used simpler model for energy cost for wireless communications by accounting only the analog radiation cost for transmission and ignored the fixed cost for electronics in transmission and reception circuitry in nodes. Furthermore, in a network it is possible for some node pairs not be able to communicate directly even though they are in their radio ranges due to obstacles present in the terrain of the network.

We propose a novel medium access control protocol for ad hoc wireless networks data to send can contend simultaneously for the channel. Nodes contend for access using a synchronous signaling mechanism that achieves two objectives: it arbitrates contentions locally and it selects a subset of nodes across the network that attempt to transmit simultaneously. The subset of nodes that survive the signaling mechanism can be viewed as an orchestrated set of transmissions that are spatially reusing the channel shared by the nodes. Thus the 'quality' of the subset of nodes selected by the signaling mechanism is a key factor in determining the spatial capacity of the system. In this paper, we propose a general model for such synchronous signaling mechanisms and recommend a preferred design. We then focus via both analysis and simulation on the spatial and capacity characteristics of these access control mechanisms. Our work is unique in that it specifically focuses on the spatial capacity aspects of a MAC protocol, as would be critical for ad hoc networking, and shows SCR is a promising solution. Specifically, it does not suffer from congestion collapse as the density of contending nodes grows, it does not suffer from hidden or exposed node effects, it achieves high capacities with a spatial usage exceeding 1 (i.e. more than one packet exchange in the area covered by a transmission), and it facilitates the integration of new physical layer capacity increasing technologies.

A Wireless Sensor Network (WSN) is a distributed system populated by a base station and a number of wireless sensor nodes. The main task of the sensor nodes in a WSN is to monitor the environment, collect data, and eventually transfer the sensed data to the base station. For reliable monitoring, the sensor nodes must be in close proximity to the physical events. The sensor nodes are tiny devices that operate on a frugal energy budget and may fail dua to, among other causes, power depletion, catastrophic events, and external damages. When the location and the state (faulty or fault-free) of each sensors in the network is known, the faulty sensors can be repaired/recharged or new sensors could be added to the affected areas so as to maintain accurate monitoring. The main contribution of this work is to provide energy-efficient means to identify the location of the faulty sensor nodes in the WSN. Consider a WSN populated by n wireless sensor nodes which are arranged in a two-dimensional grid of size . Let q and k denote the number of fault-free and faulty nodes in the WSN, respectively. The task of identifying the faulty nodes and reporting the location of these faulty sensors to the base station can be completed in O(α + r²) time slots and none of the sensors need to awake for more than O(log log α) time slots, where α = min(q,k) and r is the transmission range of the sensor nodes.

A critical aspect of applications with wireless sensor networks is network lifetime. Battery-powered sensors are usable as long as they can communicate captured data to a processing node. Sensing and communications consume energy, therefore judicious power management and scheduling can effectively extend the operational time. One important class of wireless sensor applications of deployment of large number of sensors in an area for environmental monitoring. The data collected by the sensors is sent to a central node for processing. In this paper we propose an efficient method to achieve energy savings by organizing the sensor nodes into a maximum number of disjoint dominating sets (DDS) which are activated successively. Only the sensors from the active set are responsible for monitoring the target area and for disseminating the collected data. All other nodes are into a sleep mode, characterized by a low energy consumption. We define the maximum disjoint dominating sets problem and we design a heuristic that computes the sets. Theoretical analysis and performance evaluation results are presented to verify our approach.

The hyperstar network has been recently proposed as an attractive product network that outperforms many popular topologies in various respects. In this paper we explore additional capabilities for the hyperstar network through an efficient parallel algorithm for solving the LU factorization problem on this network. The proposed parallel algorithm uses O(n) communication time on a hyperstar formed by the cross-product of two n-star graphs. This communication time improves the best known result for the hypercube-based LU factorization by a factor of log(n), and improves the best known result for the mesh-based LU factorization by a factor of (n - 1)!.

The triple-loop network associated with the hyper-L shape has been shown to have the best diameter among all triple-loop networks so far. In this paper we study the k- diameters of this network. In particular, we construct three node-disjoint shortest paths no longer than the diameter plus 2 for any pair of nodes.

As pervasive and high-density wireless networks become increasingly common, it is critical to address the problems of intermittent disconnection, high error rate and collision that cause degradation in the performance of wireless media access control protocols, such as slotted ALOHA Time Division Multiple Access (slotted ALOHA/TDMA) and Direct Sequence Code Division Multiple Access (DS/CDMA). We propose adaptive techniques for improving performance of media access protocols through awareness of the mobile communication environment. These techniques involve detection of intermittent disconnection, high error rates, and collisions. Upon detection and notification of these conditions by snooping devices, the media access control layer adapts its operation and synchronization accordingly to reduce delay and loss of bandwidth. Results from our simulation studies show that adaptive TDMA improves performance by as much as 12 times over basic TDMA and adaptive CDMA improves by as much as 4 times over basic CDMA in wireless network with high density cells. Overall, adaptive CDMA still performs better than adaptive TDMA by about 4 times.

We present some results concerning hamiltonian properties of recursive circulant graphs in the presence of faulty vertices and/or edges. The recursive circulant graph G(N, d) with d ≥ 2 has vertex set V(G) = {0, 1, …, N - 1} and the edge set E(G) = {(v, w)| ∃ i, 0 ≤ i ≤ ⌈ log_d N⌉ - 1, such that v = w + dⁱ (mod N)}. When N = cd^k where d ≥ 2 and 2 ≤ c ≤ d, G(cd^k, d) is regular, node symmetric and can be recursively constructed. G(cd^k, d) is a bipartite graph if and only if c is even and d is odd. Let F, the faulty set, be a subset of V(G(cd^k, d)) ∪ E(G(cd^k, d)). In this paper, we prove that G(cd^k, d) - F remains hamiltonian if |F| ≤ deg(G(cd^k, d)) - 2 and G(cd^k, d) is not bipartite. Moreover, if |F| ≤ deg(G(cd^k, d)) - 3 and G(cd^k, d) is not a bipartite graph, we prove a more stronger result that for any two vertices u and v in V(G(cd^k, d)) - F, there exists a hamiltonian path of G(cd^k, d) - F joining u and v.