A self-organizing wireless network protocol

We have designed a self-organizing wireless network protocol and associated routing protocols for low-power fixed nodes with potentially varying transmitted powers. The heart of the protocol is a logical backbone architecture through which data communications between all the network nodes are supported by hierarchical routing. The self-organizing and hierarchical routing features are achieved by three core algorithms designed and analyzed in this thesis. The first algorithm constructs the optimal backbone sequentially as new nodes are introduced. The second algorithm dictates how the nodes exchange essential information for maintaining the optimal backbone as the network evolves. The optimality in terms of minimizing the maximum number of hops between any pair of nodes is mathematically proved. The third algorithm enables the network to recover automatically from node/link failures.; To illustrate the performance, we evaluate the communication complexity, in number of transmissions involved in delivering a message, the control complexity, concerning control message overhead used to maintain and operate the network, the time complexity involved in a node for reaching a routing decision, and the space complexity, regarding the quantity of necessary topological information for a node to perform the routing and self-organizing functions. For comparison, we evaluate several other well-known self-organizing networks using the same metrics. We show that our network is superior to each in at least two categories while tying it in all the others. In particular, our network has a node complexity independent of the size of the network.; We then present a group polling MAC protocol for the self-organizing network, where nodes within a polling group are non-interfering. This protocol minimizes the MAC logic within every node except the high-capability root of the backbone while exploiting frequency reuse throughout the network. Optimizing the protocol entails minimizing the number of groups thereby maximizing concurrency and network capacity. We show that the optimal grouping problem is comparable to an NP-hard graph coloring problem and therefore present an O(n 2) heuristic algorithm for grouping and use simulations to demonstrate its performance. We conclude that the number of groups depends on node density and degree of the graph of the logical backbone.