Usable wireless network bandwidth can be increased by adding spectrum, reducing cell site spacing (frequency reuse), use of higher-order modulation (this is less robust, but suitable for short paths) and, as outlined in a recent MIT news release, some new approaches to network design.
The concept of connectivity in graph theory should apply to wireless as well as wired networks. Most research in graph theory focuses on solving problems with edge connectivity. Mohsen Ghaffari, a graduate student in the Computer Science and Artificial Intelligence Laboratory at MIT will present a new technique for addressing vertex-connectivity problems at the upcoming Jan. 5-7 ACM-SIAM Symposium on Discrete Algorithms being held in Portland, Ore.
Ghaffari, who developed the new approach alongside Keren Censor-Hillel at the Technion and Fabian Kuhn at the University of Freiburg said, “This could ultimately help us understand how to build more robust and faster networks.”
The MIT release explains the technology in this way: “One of the fundamental concepts within graph theory is connectivity, which has two variants: edge connectivity and vertex connectivity. These are numbers that determine how many lines or nodes would have to be removed from a given graph to disconnect it. The lower the edge-connectivity or vertex-connectivity number of a graph, therefore, the easier it is to disconnect, or break apart.”
Spanning trees are one of the key technical tools used in many of the problems about edge connectivity. The MIT release explains: “A spanning tree is a subgraph--or a graph-within-a-graph--in which all of the nodes are connected by the smallest number of edges. A set of spanning trees within a graph are called “edge-disjoint” if they do not share any of these connecting lines. If a network contains three edge-disjoint spanning trees, for example, information can flow in parallel along each of these trees at the same time, meaning three times more bandwidth than would be possible in a graph containing just one tree. The higher the number of edge-disjoint spanning trees, the larger the information flow.”
The research team created an analogous theory about vertex connectivity by breaking down the graph into separated groups of nodes, known as connected dominating sets. In graph theory, a group of nodes is called a “connected dominating set” if all the vertices within it are connected to one another and any other node within the graph is adjacent to at least one of those inside the group. Information can be disseminated among the modes of the set and then passed to any other node in the network.
Regarding this theory about vertex connectivity, Ghaffari said: “Each graph contains almost as many vertex-disjoint connected dominating sets as its vertex connectivity. So if you think of an application like broadcasting information through a network, we can now decompose the network into many groups, each being one connected dominating set. Each of these groups is then going to be responsible for broadcasting some set of the messages, and all groups work in parallel to broadcast all the messages fast--almost as fast as possible. These new techniques also allow us to analyze whether a network is likely to remain connected when its nodes fail randomly with some given probability.”
Noga Alon, professor of mathematics and computer science at Tel Aviv University, said Ghaffari and his fellow authors have identified the notion that determines the largest achievable flow when broadcasting messages using routing in communications networks.
As wireless systems incorporate an increasing number of wireless nodes and opportunities for “mesh” networking arise, this work by Ghaffari and his team could provide a way to maximize performance of these systems, both in terms of bandwidth and robustness.
