Shared MPR Sets for Moderately Dense Wireless Multihop Networks

Multipoint relays (MPRs) are used for flooding topology control messages and finding the shortest paths for unicast communications in the optimized link state routing protocol (OLSR). In this paper, we propose a method for achieving more efficient MPR selection in moderately dense wireless multihop networks (including sensor networks) than the conventional MPR selection. First, we analyze moderately dense networks to show that a node close to the two-hop border has little probability of being a two-hop neighbor. Second, we explain that there is a chance of the node's MPRs being shared with its neighbors. To maximize this chance, we propose using shared MPR sets. These sets minimize the MPR ratio, which is defined as the number of nodes selected as MPRs by at least one neighbor divided by the total number of nodes in the network. Simulations are used to confirm the efficiency of using shared MPR sets. A centralized heuristic algorithm shows an MPR ratio redundancy in moderately dense networks that is about 10% of that obtained through conventional MPR selection.