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, 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.