Mesh topologies are important for large-scale peer-to-peer systems that use low-power transceivers. The quality of service (QoS) in such systems is known to decrease as the scale increases. We present a scalable approach for dissemination that exploits all the shortest paths between a pair of nodes and improves the QoS. Despite the presence of multiple shortest paths in a system, we show that these paths cannot be exploited by spreading the messages over the paths in a simple round-robin manner; nodes along one of these paths will always handle more messages than the nodes along the other paths. We characterize the set of shortest paths between a pair of nodes in regular mesh topologies and derive rules, using this characterization, to effectively spread the messages over all the available paths. These rules ensure that all the nodes that are at the same distance from the source handle roughly the same number of messages. By modeling the multihop propagation in the mesh topology as a multistage queuing network, we present simulation results from a variety of scenarios that include link failures and propagation irregularities to reflect real-world characteristics. Our method achieves improved QoS in all these scenarios.

We present a systematic approach to selecting cluster heads in regular mesh topologies based on the idea of k- Domination in graphs. Given a graph, G=(V,E), a subset D of V is said to be a 1-dominating set if every node v in V is either in D or is adjacent to a node in D. A subset D is said to be a k- dominating set if every node v, not in D, is connected to a node in D via a path of length less than or equal to k. Using regular mesh topologies that are obtained by embedding a collection of nodes in a two dimensional grid, where each node has q neighbors, we show how k-dominating sets impact the energy consumed and the quality of service of the data aggregation. We present simulation results that validate the results.