In this paper, we propose the Expanded Borel Cayley Graphs Topology Construction (EBTC) algorithm to formulate an efficient communication topology for WSNs. The EBTC is an integrated method of Neighbor Discovery and Topology Control to produce a communication topology with collision avoidance and energy saving. The EBTC consists of two phases: Phase I) where nodes collect node IDs of their logical neighbor candidates (Neighbor Discovery) and Phase II) where nodes establish bidirectional links with the most qualified logical neighbor candidate(s) (Topology Control). Nodes under EBTC algorithm save energy and avoid collision during topology construction by following a selective and deterministic node wake-up schedule which is designed based on Ex-BCG connection characteristics. From simulation, the EBTC generates an efficient communication topology with more than 98% reachability while consuming less energy than other topology control algorithms. We also found that it has short average path length and small, constrained logical node degree when compared to other topology control algorithms.

In this paper, we propose the Aggressive Multi-path Aware (AMA) routing protocol. The AMA routing protocol is designed to demonstrate routing feasibility in the resized Borel Cayley Graphs (BCGs) and Expanded Borel Cayley Graphs (Ex-BCGs) formulated by the Cut-Through Rewiring (CTR) algorithm. The AMA routing protocol focuses on resolving the single shortest path and multi-paths depletion problems of the Vertex-Transitive (VT) and Class-level Vertex-Transitive (CVT) routing protocols when BCGs and Ex-BCGs are resized. The AMA routing protocol updates the routing table to reflect topology changes with a small network overhead. Based on the updated routing table, the AMA routing protocol delivers data with the Multi-path Aware routing and the Random Direction routing schemes. The multi-path aware routing exploits all available multi-paths with prioritized selection from the updated routing table. The random direction routing supplements the multi-path aware routing failure by relaying the packet to randomly selected neighbor. From simulation, we observe that the AMA routing protocol has reliable reachability and efficient average routing path length along the removed node ratios. Furthermore, we identify that the AMA routing protocol achieves almost identical reachabilities independent of the networks generated by different parameters. For extensive evaluation with traffic patterns, we show the potential of the AMA routing protocol for network applications with reasonable reachability, End-to-End delay and dropped packets analysis.

In this paper, we explore the use of a pseudo-random graph family, Borel Cayley graph family, as the network topology in an NGN (Next Generation Network) with thousands of nodes operated in a packet switching environment asynchronously. BCGs are known to be an efficient topology in interconnection networks because of its small diameters, short average path lengths, and low-degree connections. However, the application of BCGs in NGN are hindered by a lack of size flexibility and fault tolerant routing. We propose a fault-tolerant routing algorithm for BCGs. Our algorithm exploits the vertex-transitivity property of Borel Cayley graphs and relies on extra information to reflect topology change. Our results show that the proposed method supports good reachability and short average hop count.

In our previous work, we reported Borei Cayley Graphs (BCGs) have prominent properties such as outstanding topologlcal properties, ultrafast consensus speed and optimal routing algorithm. However, the network performance of BCGs Intensively relies on generating parameters p and k, where p Is a prime number and k Is a factor of p — 1. In this paper, we propose the Expanded BCGs (Er-BCGs) to theoretically expand BCGs to eliminate the dependence on the parameters with node ID space expansion and extended connection rule. The E∗-BCGs preserve outstanding topological properties of BCGs and enable nodes to be represented as Generalized Chordal Ring (GCR). Furthermore, the E∗-BCGs have class-level vertex transitivity which allows the networks viewed by vertices in the same class have an identical structure. Based on these properties, we present the class-level vertex transitive (CVT) routing algorithm for Er-BCGs. The CVT routing algorithm is an optimal, distributed algorithm and incorporates with the routing table which is generated by the GCR constant based routing table generation requiring a low size complexity of O{dk), where d is a node degree. To further improve the CVT routing efficiency, we provide the routing table folding scheme to reduce the number of routing table entries from Nd to Nd/n, where N is a network size and n is an expansion factor. In the routing simulation with All-to-All and All-to-M traffic patterns, Er-BCGs outperform the benchmark networks in reachability, end-to-end delay and the mean number of packets at node with a variety of packet generation ratios.

We present a novel topology control algorithm for very dense wireless sensor networks that is constrained by a small maximum nodal degree k. Particularly, we limit k = 4 which makes it challenging to formulate a connected network that possesses favorable properties such as a small diameter, short average path length and low energy consumption. Towards this goal, we introduce a graph theoretic approach that utilizes a Borel Cayley Graph as an underlying network topology. We call this approach Borel Cayley Graph Topology Control (BCG-TC). Simulation results for a network with 1081 nodes distributed over a 100 m × 100 m area showed that BCG-TC can formulate connected networks for the radio range exceeding certain threshold. Furthermore, these connected networks generated by BCG-TC exhibit (i) a small nodal degree k ≤ 4, (ii) a small diameter and short average path length, and (iii) fast information dissemination that leads to the least energy consumption among considered topology control protocols.

With the rapid growth of wireless sensor technology, there is a need for MAC protocols that support efficient simultaneous peer-to-peer communications in large and dense wireless sensor networks. To meet such a need, we propose a MAC protocol that uses a novel channel assignment scheme based on the pseudo-random connection of a dense Cayley graph as an underlying graph. By utilizing all or most of the available frequency channels, the proposed protocol can support many, simultaneous peer-to-peer communications. Other features of the protocol include minimal collisions due to fixed channel assignments and a decentralized routing algorithm that avoids global time synchronization. The effectiveness of using Cayley graphs as the underlying topology for such frequency assignment is evaluated and compared with that of the Manhattan Street Network via a simulator with power model parameterized to CrossBow MICA 2 sensors.

Recently, it was correctly pointed out by Jha that there is an error in our earlier paper on diagonal mesh networks. In response to Jha's critique, we now provide an upper bound on the bisection width of a diagonal mesh. The proof is a constructive one and an algorithm is provided to divide the network into two equal halves (plus/minus one node)

With the rapid growth of wireless sensor technology, we foresee a need for MAC protocols to allow efficient simultaneous peer-to-peer communications in large and dense wireless sensor networks. To meet such a need, we propose a novel MAC protocol that exploits network graphs property to assign frequencies such that the number of intermediate hops to reach destinations is minimized. Via a simulation model parameterized to CrossBow MICA2, we evaluate the performance of our MAC protocol with Cayley and Manhattan Street networks

Performance modeling under nonuniform traffic is a useful tool to validate simulation accuracy and lend insights to realistic implementation of multihop networks. We present memoryless and independence assumptions based performance models capable of tracking nonuniform traffic for an arbitrary multihop network with the deflection and store-and-forward routing strategies. We also include a description of the efficient numerical algorithms, and provide comparisons to simulation. Our models are a generalization of Greenberg-Goodman (1986, 1992), Greenberg-Hajek (1992), Hajek-Krishna (1990), and Brassil-Cruz (1991, 1993) models.

Dense, symmetric graphs are useful interconnection models for multicomputer systems. Borel Cayley graphs, the densest degree-4 graphs for a range of diameters, are attractive candidates. However, the group-theoretic representation of these graphs makes the development of efficient routing algorithms difficult. In earlier reports, we showed that all degree-4 Borel Cayley graphs have generalized chordal ring (GCR) and chordal ring (CR) representations. We present the class-congruence property and use this property to develop the two-phase routing algorithm for Borel Cayley graphs in a special GCR representation. The algorithm requires a small space complexity of O(p+k) for n=p/spl times/k nodes. Although suboptimal, the algorithm finds paths with length bounded by 2D, where D is the diameter. Furthermore, our computer implementation of the algorithm on networks with 1,081 and 15,657 nodes shows that the average path length is on the order of the diameter. The performance of the algorithm is compared with that of existing optimal and suboptimal algorithms.

A multihop, wavelength division multiplex (WDM)-based network, CayleyNet, is proposed for the realization of terabit lightwave networks. CayleyNets are attractive virtual topologies because they support the largest number of nodes for four-neighbor connection in a range of diameters. In general, CayleyNets are bi-directional and there are N=p/spl times/k nodes, where p is a prime and k is a factor of p-1. The analysis shows that CayleyNet has a similar performance in channel efficiency, total and user throughput as the ShuffleNet with N=4/sup kspl times/k. However, CayleyNet has the advantages of a more flexible network size and symmetric transmission distance. Compared with the N=2/sup kspl times/k ShuffleNet and toroidal mesh, the CayleyNet has a superior performance.>

Diagonal and toroidal mesh are degree-4 point to point interconnection models suitable for connecting communication elements in parallel computers, particularly multicomputers. The two networks have a similar structure. The toroidal mesh is popular and well-studied whereas the diagonal mesh is relatively new. In this paper, we show that the diagonal mesh has a smaller diameter and a larger bisection width. It also retains advantages such as a simple rectangular structure, wirability and scalability of the toroidal mesh network. An optimal self-routing algorithm is developed for these networks. Using this algorithm and the existing routing algorithm for the toroidal mesh, we simulated and compare the performance of these two networks with N=35/spl times/71=2485, N=49/spl times/99=4851, and N=69/spl times/139=9591 nodes under a constant system with a fixed number of messages. Deflection routing is used to resolve conflicts. The effects of various deflection criteria are also investigated. We show that the diagonal mesh outperforms the toroidal mesh in all cases, and thus provides an attractive alternative to the toroidal mesh network.>

There is a continuing search for dense $( \delta ,D )$ interconnection graphs, that is, regular, undirected, degree $\delta $ graphs with diameter D and having a large number of nodes. Cayley graphs formed by Borel subgroups currently contribute to some of the densest known $( \delta = 4,D )$ graphs for a range of D [1]. However, the group theoretic representation of these graphs makes the development of efficient routing algorithms difficult. In an earlier report, it was shown that all Cayley graphs have generalized chordal ring (GCR) representations [2]. In this paper, it is shown that all degree-4 Borel Cayley graphs can also be represented by the more restrictive chordal rings (CR) through a constructive proof. A step-by-step algorithm to transform any degree-4 Borel Cayley graph into a CR graph is provided. Examples are used to illustrate this concept.

It is shown that all finite Cayley graphs can be represented by generalized chordal rings (GCR). An example Borel Cayley graph is used to illustrate the generation of GCR representations. A sufficient condition is given for the representation of a Cayley graph as a chordal ring (CR). With the integer labeling of GCR representations, a straightforward, progressive routing algorithm based on table look-up is summarized.>