# Shared MPR Sets for Moderately Dense Wireless Multihop Networks

Authors: Teruaki Kitasuka; Shigeaki Tagashira
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

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.


---

## Body

## 1. Introduction

Multipoint relays (MPRs) [1, 2] support the efficient flooding of topology control (TC) messages in the optimized link state routing protocol (OLSR) [3] and are used to find the shortest path to any pair of nodes for unicast communications in OLSR. Although OLSR is designed as a routing protocol for mobile ad hoc networks (MANETs), it can also be used for sensor networks. OLSR is a proactive routing protocol on which each node regularly exchanges topology information with other nodes.MPR is the key concept used in OLSR. Each node selects a subset of its neighbors as its MPR set. According to the RFC 7181 [4], the MPR set is selected to satisfy two properties: (1)if a nodevsends a message and that message is successfully forwarded by all MPRs ofv, then all 2-hop neighbors ofvwill receive that message and (2)keeping the MPR set small ensures that the overhead of the protocol is kept at a minimum.The nodes that have been selected as MPRs have two roles: generating and forwarding TC messages into the entire network and acting as routers. Each TC message generated by a nodew advertises the link state information between itself and a node v during v’s selection of w as one of its MPRs. In contrast, non-MPR nodes (none of which is selected as an MPR by a neighbor) do not generate or forward TC messages except to enable an OLSR redundancy option calledTC_REDUNDANCY. Thus, it is implied that non-MPR nodes act as edge nodes; that is, they do not act as routers. The path constructed with a sequence of links between an MPR and its selector is the shortest path.We analyze the density of MPRs in moderately dense wireless multihop networks including sensor networks and present two issues that arise with conventional MPR selection: high MPR density and redundancy. First, the high MPR density issue implies that many TC messages are generated and flooded. Wu et al. [5] have already proven the asymptotic property that the average number of MPRs in a finite region is infinite when the network is extremely dense. However, we analyze moderately dense networks for additional insight into their nonasymptotic properties. Our concern is the distance from a node to its two-hop neighbor.The second issue—redundancy of the conventional MPR selection—causes redundancy in dense networks because it minimizes the number of MPRs selected by each node using a fully distributed manner. Therefore, we propose a concept called “shared MPR sets” to reduce routing overhead. Through a simulation with a heuristic shared MPR selection algorithm, which is not distributed, we confirm the redundancy of conventional MPR selection in moderately dense networks.For sensor networks, it is important to conserve the spectrum and energy. A way to achieve this is to improve the efficiency of OLSR by reducing TC messages. Our goal is to explain the following properties of moderately dense wireless multihop networks.(i)
Each node has a chance to share its MPRs with its neighbors (Section3).(ii)
If MPR sharing is achieved well, OLSR’s routing overhead is reduced (Section4).In this paper, we only discuss the existence of shared MPR sets with a centralized algorithm (the effectiveness of this method is shown through simulations); we do not discuss a feasible algorithm for finding shared MPR sets in a distributed manner. A preliminary version of this study appeared in [6]. Developing an efficient distributed algorithm is our main goal for future work. Several distributed heuristic algorithms have been proposed by Yamada et al. [7], Maccari and Lo Cigno [8], and ourselves [9]. However, the efficiency of those proposed algorithms has not yet been fully analyzed.The rest of the paper is organized as follows. Related work is described in Section2; this includes studies regarding OLSR, MPRs, and connected dominating sets (CDSs). In Section 3, we analyze the distance from a node to its two-hop neighbor, which is associated with conventional MPR selection, and introduce the concepts of MPR sharing and shared MPR sets. In Section 4, we provide a heuristic algorithm for shared MPR selection and provide the simulation results for dense wireless multihop networks. Based on those results, we confirm that routing overhead is reduced when shared MPR sets are used. Finally, we conclude this paper in Section 6.


## 2. Related Work

### 2.1. OLSR

OLSR [3] is a proactive routing protocol for MANETs. OLSR maintains neighborhood information and topology information in each node and can find the shortest path between any pair of nodes with relatively less control traffic.We briefly review these two types of information and two types of messages. We denote a node byv, w, or u. Regarding neighborhood information, node v stores the partial two-hop information GP2(v)=(N(v)∪N2(v),EP2(v)), MPRs M(v), and MPR selectors M-1(v). The node sets N(v) and N2(v) are sets of one-hop neighbors and strict two-hop neighbors, respectively. The edge set EP2(v) is a set of symmetric links between one-hop neighbors and two-hop neighbors. Note that EP2(v) does not contain links between strict two-hop neighbors.Neighborhood information is updated when nodev receives a HELLO message. HELLO messages are broadcasted by all nodes periodically but are never forwarded. When node v receives a HELLO message from node w, v recognizes that w is a one-hop neighbor of v and adds w to N(v).The HELLO message ofw includes one-hop neighbors N(w) and MPRs M(w). When v receives a HELLO message of w, for each node u∈N(w), v adds u and (w,u) in N2(v) and EP2(v), respectively. Node v also adds w in M-1(v) if v∈M(w). Afterward, node v computes its MPRs M(v) by using the MPR selection algorithm [3] with updated N(v), N2(v), and EP2(v) (The MPR selection algorithm is described in Section 2.2). Note that if node u∈N2(v) is also in N(v), then node u is removed from N2(v). After several HELLO messages are exchanged, the neighborhood information satisfies (1)Nv=w∣dv,w<rN2v=u∣u∈Nw,w∈Nv,u∉Nv,u≠vEP2v=w,u∣w∈Nv,u∈NwMv⊆Nvsuch  thatu∀∈N2v,w∃∈Mv,w,u∈EP2vM-1v=w∣v∈Mw.Note that d(v,w) is the distance between v and w and r is the radio range.The topology information for each node, denoted byu, is a directed subgraph of the network G. The directed subgraph, denoted by G′(u)=(V′(u),E′(u)), includes all reachable nodes and partial directed links. G′(u) is generated on the basis of the received TC messages. A TC message is periodically generated by every MPR, denoted by w, and includes M-1(w). M-1(w) is called an MPR selector set. TC messages are flooded into the entire network, and each of it informs the links between w and each of M-1(w). When node u receives a TC message generated by w, for each v∈M-1(w), node u adds v and (w,v) in V′(u) and E′(u), respectively. Node u also adds w in V′(u).The routing table of nodeu is constructed using GP2(u) of the neighborhood information and G′(u) of the topology information. By using these two types of information, node u can find the shortest path to any other node in the network for unicast communications.OLSRv2 [4] has already released in April 2014. Therefore, the discussion here is applicable to OLSRv2. In OLSRv2, nodes can freely interoperate regardless of whether they use the same MPR selection algorithm; an example algorithm for calculating MPRs is available in appendix B of OLSRv2 [4]. OLSRv2 defines two MPR sets (flooding MPR and routing MPR) and adopts neighborhood discovery protocol (NHDP) [10] to acquire neighborhood information.


### 2.2. Multipoint Relays

Multipoint relaying has been proposed by Qayyum et al. [1, 2] for efficiently flooding broadcast messages in mobile wireless networks. The concept of multipoint relaying is to reduce the number of duplicate retransmissions while forwarding a broadcast message.Each nodev selects a small subset of its neighbors N(v) as MPRs M(v). When node v transmits a broadcast message generated either by itself or another node, each node w∈M(v) retransmits the message only once; other neighbors do not retransmit it.In MANETs, for proactive and reactive protocols, flooding is used to find a path to the destination. OLSR [3] also adopts the use of MPRs to disseminate TC messages.Qayyum et al. [2] analyze MPRs and propose a heuristic MPR set selection algorithm. They prove that the following MPR problem is NP-complete:given a network (i.e., the set of one-hop neighbors for each node), a nodevof the network, and an integerk, is there a multipoint relay set forvof size less thank?The heuristic algorithm proposed by Qayyum et al. provides a near-optimal MPR set. They prove that the MPR set computed by that heuristic contains at mostlog⁡n times more nodes than the optimal MPR set [2], where n is the number of nodes in the network. The input of the heuristic is the partial two-hop information GP2(v), and the output of the heuristic is the MPR set M(v). The heuristic algorithm is stated as follows:(1)
Start with an empty MPR setM(v).(2)
First, select as MPRs those one-hop neighbors inN(v) that are only neighbors of some node in N2(v); add these one-hop neighbors to M(v).(3)
While there still exists some node inN2(v) that is not covered by M(v), one has the following:
(a)
For each node inN(v) that is not in M(v), compute the number of nodes that it covers among the uncovered nodes in N2(v).(b)
Add the node ofN(v) in M(v) for which this number is maximum.Jacquet et al. [11] have analyzed OLSR MPR flooding in two network models: the random graph model and the random unit disk graph model. These two models are used for indoor and outdoor networks, respectively. In the two-dimensional random unit disk graph model, Jacquet et al. prove that the average size of the MPR sets tends to be smaller than 3π(n′/3π)1/3, where n′ is defined by (3) in Section 3.1 below.Busson et al. [12] have analyzed the conventional MPR selection in random unit disk graphs. They did not analyze sharing MPRs with neighbors; however, they do show that approximately 75% of MPR sets are selected in step 2 of the heuristic algorithm above, which implies that only the remaining 25% have a chance of sharing MPRs with their neighbors. The starting point of their analysis also uses (4), shown in Section 3.2 below. Our analysis in Section 3.2 is similar to theirs; however, unlike their research, we go on to analyze MPR sharing (Sections 3.3 and 3.4).The motivation behind Maccari and Lo Cigno’s research [8] is the same as ours. They describe the size of the global MPR set MG=⋃v∈V‍M(v) as the objective function that needs to be minimized; this objective function also appears in [6]. They have carefully revised the MPR selection algorithm and addressed implementation issues associated with that algorithm. Furthermore, they propose using the selector set tie breaker (SSTB) distributed strategy to minimize MG. Unlike us, their strategy for finding shared MPR sets is to use distributed algorithms; we use the centralized algorithm instead. However, we believe that the size of the global MPR set, which is calculated by the centralized algorithm, can be referred to as a type of numerical lower bound.


### 2.3.  Connected Dominating Set

A connected dominating set (CDS) is a subset of nodes. Each node in a CDS has a path only through other nodes in the CDS, and every node in the network has at least one node in the CDS as a neighbor.A small CDS is another candidate to reduce the number of forwarding nodes during the flooding process [13]. Instead of MPRs, a CDS can be used to flood messages to the entire network, and the nodes that are not there in CDS do not need to relay messages to flood. A small CDS will have less control traffic than MPRs. Furthermore, if the shortest path for every node is not a mandatory routing requirement, a small CDS can also be used for routing instead of MPRs.A CDS does not have the (1) property of MPR sets that is described in Section1. In other words, the use of MPRs guarantees the shortest path between any pair of nodes; CDS does not guarantee it. Furthermore, the time and message complexities of CDS schemes are slightly higher than those of MPR schemes. Perhaps for these reasons, unfortunately, CDSs are not currently employed in major MANET routing protocols.Wu et al. [5] have explained several extensions designed to generate smaller CDSs using complete two-hop information. The complete two-hop information of node v is denoted by GC2(v)=(N(v)∪N2(v),EC2(v)). The difference between GC2(v) and GP2(v) is the sets of links. EC2(v) includes all links in EP2(v) as well as links between any pair of two-hop neighbors N2(v). Consider(2)EC2=EP2∪w1,w2∣w1,w2∈N2v,w1,w2∈V.To construct GC2(v) in v, node v has to receive one-hop neighbor information N(u) from each of its two-hop neighbor u∈N2(v). Because node u’s HELLO messages have to reach all of u’s two-hop neighbors, it implies that constructing GC2 requires higher communication overhead than constructing GP2.Wu et al. have proved that the extended MPR has a constant local approximation ratio rather than the logarithmic local ratio associated with the original MPR [5].


## 2.1. OLSR

OLSR [3] is a proactive routing protocol for MANETs. OLSR maintains neighborhood information and topology information in each node and can find the shortest path between any pair of nodes with relatively less control traffic.We briefly review these two types of information and two types of messages. We denote a node byv, w, or u. Regarding neighborhood information, node v stores the partial two-hop information GP2(v)=(N(v)∪N2(v),EP2(v)), MPRs M(v), and MPR selectors M-1(v). The node sets N(v) and N2(v) are sets of one-hop neighbors and strict two-hop neighbors, respectively. The edge set EP2(v) is a set of symmetric links between one-hop neighbors and two-hop neighbors. Note that EP2(v) does not contain links between strict two-hop neighbors.Neighborhood information is updated when nodev receives a HELLO message. HELLO messages are broadcasted by all nodes periodically but are never forwarded. When node v receives a HELLO message from node w, v recognizes that w is a one-hop neighbor of v and adds w to N(v).The HELLO message ofw includes one-hop neighbors N(w) and MPRs M(w). When v receives a HELLO message of w, for each node u∈N(w), v adds u and (w,u) in N2(v) and EP2(v), respectively. Node v also adds w in M-1(v) if v∈M(w). Afterward, node v computes its MPRs M(v) by using the MPR selection algorithm [3] with updated N(v), N2(v), and EP2(v) (The MPR selection algorithm is described in Section 2.2). Note that if node u∈N2(v) is also in N(v), then node u is removed from N2(v). After several HELLO messages are exchanged, the neighborhood information satisfies (1)Nv=w∣dv,w<rN2v=u∣u∈Nw,w∈Nv,u∉Nv,u≠vEP2v=w,u∣w∈Nv,u∈NwMv⊆Nvsuch  thatu∀∈N2v,w∃∈Mv,w,u∈EP2vM-1v=w∣v∈Mw.Note that d(v,w) is the distance between v and w and r is the radio range.The topology information for each node, denoted byu, is a directed subgraph of the network G. The directed subgraph, denoted by G′(u)=(V′(u),E′(u)), includes all reachable nodes and partial directed links. G′(u) is generated on the basis of the received TC messages. A TC message is periodically generated by every MPR, denoted by w, and includes M-1(w). M-1(w) is called an MPR selector set. TC messages are flooded into the entire network, and each of it informs the links between w and each of M-1(w). When node u receives a TC message generated by w, for each v∈M-1(w), node u adds v and (w,v) in V′(u) and E′(u), respectively. Node u also adds w in V′(u).The routing table of nodeu is constructed using GP2(u) of the neighborhood information and G′(u) of the topology information. By using these two types of information, node u can find the shortest path to any other node in the network for unicast communications.OLSRv2 [4] has already released in April 2014. Therefore, the discussion here is applicable to OLSRv2. In OLSRv2, nodes can freely interoperate regardless of whether they use the same MPR selection algorithm; an example algorithm for calculating MPRs is available in appendix B of OLSRv2 [4]. OLSRv2 defines two MPR sets (flooding MPR and routing MPR) and adopts neighborhood discovery protocol (NHDP) [10] to acquire neighborhood information.


## 2.2. Multipoint Relays

Multipoint relaying has been proposed by Qayyum et al. [1, 2] for efficiently flooding broadcast messages in mobile wireless networks. The concept of multipoint relaying is to reduce the number of duplicate retransmissions while forwarding a broadcast message.Each nodev selects a small subset of its neighbors N(v) as MPRs M(v). When node v transmits a broadcast message generated either by itself or another node, each node w∈M(v) retransmits the message only once; other neighbors do not retransmit it.In MANETs, for proactive and reactive protocols, flooding is used to find a path to the destination. OLSR [3] also adopts the use of MPRs to disseminate TC messages.Qayyum et al. [2] analyze MPRs and propose a heuristic MPR set selection algorithm. They prove that the following MPR problem is NP-complete:given a network (i.e., the set of one-hop neighbors for each node), a nodevof the network, and an integerk, is there a multipoint relay set forvof size less thank?The heuristic algorithm proposed by Qayyum et al. provides a near-optimal MPR set. They prove that the MPR set computed by that heuristic contains at mostlog⁡n times more nodes than the optimal MPR set [2], where n is the number of nodes in the network. The input of the heuristic is the partial two-hop information GP2(v), and the output of the heuristic is the MPR set M(v). The heuristic algorithm is stated as follows:(1)
Start with an empty MPR setM(v).(2)
First, select as MPRs those one-hop neighbors inN(v) that are only neighbors of some node in N2(v); add these one-hop neighbors to M(v).(3)
While there still exists some node inN2(v) that is not covered by M(v), one has the following:
(a)
For each node inN(v) that is not in M(v), compute the number of nodes that it covers among the uncovered nodes in N2(v).(b)
Add the node ofN(v) in M(v) for which this number is maximum.Jacquet et al. [11] have analyzed OLSR MPR flooding in two network models: the random graph model and the random unit disk graph model. These two models are used for indoor and outdoor networks, respectively. In the two-dimensional random unit disk graph model, Jacquet et al. prove that the average size of the MPR sets tends to be smaller than 3π(n′/3π)1/3, where n′ is defined by (3) in Section 3.1 below.Busson et al. [12] have analyzed the conventional MPR selection in random unit disk graphs. They did not analyze sharing MPRs with neighbors; however, they do show that approximately 75% of MPR sets are selected in step 2 of the heuristic algorithm above, which implies that only the remaining 25% have a chance of sharing MPRs with their neighbors. The starting point of their analysis also uses (4), shown in Section 3.2 below. Our analysis in Section 3.2 is similar to theirs; however, unlike their research, we go on to analyze MPR sharing (Sections 3.3 and 3.4).The motivation behind Maccari and Lo Cigno’s research [8] is the same as ours. They describe the size of the global MPR set MG=⋃v∈V‍M(v) as the objective function that needs to be minimized; this objective function also appears in [6]. They have carefully revised the MPR selection algorithm and addressed implementation issues associated with that algorithm. Furthermore, they propose using the selector set tie breaker (SSTB) distributed strategy to minimize MG. Unlike us, their strategy for finding shared MPR sets is to use distributed algorithms; we use the centralized algorithm instead. However, we believe that the size of the global MPR set, which is calculated by the centralized algorithm, can be referred to as a type of numerical lower bound.


## 2.3.  Connected Dominating Set

A connected dominating set (CDS) is a subset of nodes. Each node in a CDS has a path only through other nodes in the CDS, and every node in the network has at least one node in the CDS as a neighbor.A small CDS is another candidate to reduce the number of forwarding nodes during the flooding process [13]. Instead of MPRs, a CDS can be used to flood messages to the entire network, and the nodes that are not there in CDS do not need to relay messages to flood. A small CDS will have less control traffic than MPRs. Furthermore, if the shortest path for every node is not a mandatory routing requirement, a small CDS can also be used for routing instead of MPRs.A CDS does not have the (1) property of MPR sets that is described in Section1. In other words, the use of MPRs guarantees the shortest path between any pair of nodes; CDS does not guarantee it. Furthermore, the time and message complexities of CDS schemes are slightly higher than those of MPR schemes. Perhaps for these reasons, unfortunately, CDSs are not currently employed in major MANET routing protocols.Wu et al. [5] have explained several extensions designed to generate smaller CDSs using complete two-hop information. The complete two-hop information of node v is denoted by GC2(v)=(N(v)∪N2(v),EC2(v)). The difference between GC2(v) and GP2(v) is the sets of links. EC2(v) includes all links in EP2(v) as well as links between any pair of two-hop neighbors N2(v). Consider(2)EC2=EP2∪w1,w2∣w1,w2∈N2v,w1,w2∈V.To construct GC2(v) in v, node v has to receive one-hop neighbor information N(u) from each of its two-hop neighbor u∈N2(v). Because node u’s HELLO messages have to reach all of u’s two-hop neighbors, it implies that constructing GC2 requires higher communication overhead than constructing GP2.Wu et al. have proved that the extended MPR has a constant local approximation ratio rather than the logarithmic local ratio associated with the original MPR [5].


## 3. Analysis of MPRs in Dense Networks

### 3.1. Notation

We model a network as a unit disk graphG=(V,E), where V is a set of nodes in the network and E is a set of available links between nodes. Each node knows partial information of G by receiving HELLO and TC messages. The total number of nodes in the network is denoted by n(=|V|). For simplicity, we assume that the transmission range r of each node is uniform. There is an edge (v,w)∈E if and only if d(v,w)<r, where the function d() is a distance between two nodes. A region D(v,x) is defined as a disk with radius x that centers v. D(v,r) is called a unit disk of v. A node in the unit disk D(v,r) is called a one-hop neighbor of v.Our analysis assumes that nodes are placed uniformly in a two-dimensional region. The expected number of nodes in a one-hop region is denoted byn′. For example, if the region is a square of side R and the number of nodes in the region is n, then(3)n′=πr2nR×R.We use the term “density” (defined as n′) instead of the number of nodes in a unit square, that is, n/R2, for convenience.


### 3.2. Distance to Two-Hop Neighbors

Suppose that there are two nodesv and u such that d(v,u)=2r-δ≤2r, as shown in Figure 1(a). We discuss the condition where u is a two-hop neighbor of v. Obviously, node u is a two-hop neighbor of v if and only if there is at least one node w that satisfies d(v,w)≤r and d(w,u)≤r. In other words, d(v,u)≤2r is a necessary but insufficient condition for u being a two-hop neighbor of v.Figure 1
Determining whetheru is a two-hop neighbor of v.
(a)
Nodeu is a two-hop neighbor of v, if w covers u
(b)
Nodeu is not a two-hop neighbor of v if there is no node ∈WThe regionW is defined as W=D(v,r)∩D(u,r), as shown in Figure 1(b). Node u is a two-hop neighbor of v if and only if there is at least one node w∈W. The size of region W is denoted by S(W) and expressed as follows:(4)SW=2πr2·2θ2π-r2sin⁡θcos⁡⁡θ=r22θ-sin⁡2θ,where θ=θ(δ)=arccos⁡(2r-δ/2r). We define a probability function p(δ,n′) that expresses the probability that u is a two-hop neighbor of v when u is 2r-δ away from v. Suppose that node w is a two-hop neighbor of v. The probability that w is not in the region W is (πr2-SW)/πr2. Node u is a two-hop neighbor of v if there is at least one one-hop neighbor of v in W. Therefore, in uniformly distributed networks, we approximate(5)pδ,n′=1-πr2-SWπr2n′,where n′ is the average number of a node’s one-hop neighbors.We try to expect the number of two-hop neighbors ofv in various densities. First, we denote the expected number of nodes in D(v,2r) by f(2r)=π(2r)2·n′/πr2=4n′. Note that f(2r) includes the number of one-hop neighbors in D(v,r). We suppose that f′(x)=2n′x/r2 is the derivative of f(x). We denote the expected number of two-hop neighbors of v by E[|N2(v)|]. We derive E[|N2(v)|] using a function g(x,n′), which is the expected number of two-hop neighbors of v in a disk D(v,x) with the radius x(r≤x≤2r) and the density n′. The function g(x,n′) is derived using f′(x) and p(δ,n′). Consider(6)EN2v=g2r,n′(7)gx,n′=∫rxf′y·p2r-y,n′dy.Figure2 shows the numerical results of g(x,n′) with various radii x and densities n′=∞, 80, 40, 20, 10, and 5. From these results, we confirm that nodes close to the border of D(v,2r) are rarely a two-hop neighbor of v under moderately high-density conditions.Figure 2
The expected number of two-hop neighbors in a disk of radiusx.To ensure the rareness of two-hop neighbors close to the border ofD(v,2r) in moderately dense networks, Table 1 shows the radius x of a disk covering q=70%–95% of two-hop neighbors. The radius x satisfies (q/100)g(2r,n′)=g(x,n′) for each q and n′. We conclude that, even when density n′=80 (a very high density where the expected number of two-hop neighbors is 214), 95% of the two-hop neighbors (nearly 203 nodes) have δ>0.10r=(2-1.90)r, θ>0.32=18°. In a moderately dense network, such as n′=20 (where the expected number of two-hop neighbors is 44), 90% of two-hop neighbors (40 nodes) have δ>0.22, θ>0.47=27°, and 70% of two-hop neighbors (31 nodes) have δ>0.39, θ>0.64=36°. From this observation, we expect that some small number of MPRs can cover all of a node’s two-hop neighbors in moderately dense wireless multihop networks. This expectation is confirmed by the simulation illustrated in Figure 7 of Section 4.Table 1
The radiusx of a disk that covers q% of two-hop neighbors on various density n′.
q
n
′
=
∞
80
40
20
10
5
70%
1.76
r
1.69
r
1.66
r
1.61
r
1.55
r
1.51
r
80%
1.84
r
1.77
r
1.74
r
1.69
r
1.64
r
1.59
r
90%
1.92
r
1.85
r
1.82
r
1.78
r
1.74
r
1.70
r
95%
1.96
r
1.90
r
1.87
r
1.84
r
1.81
r
1.78
r


### 3.3. Conventional MPR Selection of a Node

Here, we review OLSR’s conventional MPR selection in which any node selects its MPR set independently of its neighbors’ MPR sets. Understanding the symmetric property of this conventional selection will be helpful in understanding how MPRs can be shared as described in Section3.4.Suppose that there are two nodesu1 and u2 that satisfy d(v,u1)=2r-δ1 and d(v,u2)=2r-δ2 and that they are node v’s two-hop neighbors, as shown in Figure 3. We assume that u1 and u2 are closer to each other than to other v’s two-hop neighbors.Figure 3
Covering two two-hop neighbors.The regionsW1 and W2 are defined similar to W in Section 3.2. Consider(8)W1=Dv,r∩Du1,rW2=Dv,r∩Du2,r,where u1 (or u2) is a two-hop neighbor of v if and only if there is at least one node w1∈W1 (or w2∈W2). The angles θ1 and θ2 are defined as θ1=θ(δ1) and θ2=θ(δ2), respectively.The following discussion assumes that there are multiple nodes inW1 and W2; this avoids the case of having only one node in W1 and W2, in which case, the nodes must be added to MPR set M(v) in step 2 of the heuristic described in Section 2.2.If there is at least one nodew in W1∩W2, which is the hatched region in Figure 3, then u1 and u2 can be covered by single node w(=w1=w2). If there is no node in W1∩W2, there must be at least one node w1∈W1∩W2¯ and the other node must be w2∈W1¯∩W2 to cover u1 and u2, respectively.We denote∠u1vu2 by ϕ and suppose that δ1≥δ2; that is, θ1≥θ2. The inclusion relation between W1 and W2 is divided into the following three cases, where S() is the size of the region:(1)
ϕ>θ1+θ2; that is, S(W1∩W2)=0.(2)
θ1+θ2≥ϕ and ϕ>θ1-θ2, as shown in Figure 3; that is, S(W1∩W2)>0.(3)
θ1+θ2≥ϕ and θ1-θ2≥ϕ; that is, W2⊆W1.In the first case, two nodesw1∈W1 and w2∈W2 are selected as MPRs of v to cover u1 and u2, respectively. Two nodes w1 and w2 are selected independent of each other.In the second case, if there is at least one nodew∈W1∩W2, the optimal or heuristic MPR selection algorithm selects w as an MPR of v. However, this selection depends on the existence of other two-hop neighbors. The nodes in v’s MPR set are either a single node w or two nodes w1∈W1∩W2¯ and w2∈W2∩W1¯.In the third case, if the optimal or heuristic MPR selection algorithm selects a nodew2∈W2 as an MPR to cover u2, then node w2 also covers u1.The number of MPRs of nodev changes by selecting the second case. Each iteration of step 3 in the heuristic greedily adds a node in M(v); thus, the algorithm covers the maximum number of uncovered nodes in N2(v).


### 3.4.  Sharing an MPR with a Neighbor

Considering the symmetric property of conventional MPR selection (see Section3.3), we explain how sharing MPRs with a neighbor is possible. Suppose that there are two nodes v1 and v2, each of which is a one-hop neighbor of the other. Sharing MPRs means that v1 and v2 select the same node as their MPR.First, we discuss the condition in which sharing MPRs is not allowed. As shown in Figure4(a), if v1 has a two-hop neighbor u such that u is not a two-hop neighbor of v2, then v2 has no one-hop neighbor in W1. In this condition, v1 and v2 cannot share an MPR to cover u.Figure 4
Covering two two-hop neighbors.
(a)
u is a two-hop neighbor of v1 but not a two-hop neighbor of v2
(b)
u is a two-hop neighbor of both v1 and v2However, if there is a nodeu such that u is a two-hop neighbor of both v1 and v2, as shown in Figure 4(b), and there is at least one node w∈W1∩W2, then v1 and v2 can select a node w as an MPR to cover u, thus sharing an MPR.The sharable condition discussed above is symmetrical to the second case of conventional MPR selection, which is described in Section3.3. However, the optimal and heuristic MPR selection described in Section 2.2 does not consider such sharing.Note that the two-hop coverage ofv1 and v2’s MPR set is maintained regardless of whether the MPR is shared between them. The MPR is still guaranteed to construct the shortest path between any pair of nodes in the network, in contrast to CDSs, which do not guarantee the shortest path.


### 3.5.  The Proposed Shared MPR Sets

The concept of shared MPR sets was first introduced by Yamada et al. [7]. They call the concept an MPR selection “redundancy,” which is defined as follows:for a combination of MPR sets of all nodes, if the number of MPRs in the network is greater than that of other combinations of MPR sets, the combination of MPR sets is redundant.We define the MPR ratio to measure the degree of sharing. The ratio for shared MPR selection will be less than that for conventional MPR selection. We also define the number of MPRs per node to compare the average size of each node’s MPR sets; this number will be constant for shared and conventional MPR selections. The MPR ratio and number of MPRs per node are defined as follows:(9)the  MPR  ratio=⋃v∈VMvn,the  number  of  MPRs  per  node=∑v∈VMvn,where V is the set of nodes in the network, M(v) is an MPR set of node v, and n is the number of nodes in the network (i.e., n=|V|). The MPR ratio shows the number of nodes selected as MPRs by at least one neighbor in the network. If the ratio is 1, then all nodes are selected as MPRs. The number of MPRs per node shows the average number of MPRs selected by a node.To computeM(v) for all nodes, we define a bipartite graph G=(N∪N2,E), where N is the union of one-hop neighbor sets N(v) of all v∈V and N2 is the target pairs set derived by N2(v) of all v∈V. Consider(10)N=⋃v∈VNv(11)N2=v,u∣v∈V,u∈N2v(12)E=w,p∣w∈N,p=v,u∈N2,w∈Nv,u∈Nw,where (w,p)=(w,(v,u))∈E means that there are two links (v,w) and (w,u); N and N2 satisfy the conditions of |N|≤n and |N2|=Σv∈V|N2(v)|.To achieve the smallest MPR ratio, we need to find the smallest subset ofN that covers all of N2. We define the coverage that w∈N covers as (v,u)∈N2 if and only if w∈N(v) and u∈N(w); that is, (w,p)∈E. In conventional MPR selection, the coverage is defined for each node v as w∈N(v) covers u∈N2(v) if and only if u∈N(w); that is, (w,u)∈EP2.LetM be a subset of N. The set M is called a global MPR set if a subset M covers all pairs of N2. For every node v∈V, each node u∈N2(v) has one or more one-hop neighbors in a global MPR set. Then, N(v)∩M can be a candidate MPR set of v. Each node can select N(v)∩M or its subset as the shared MPR set. The MPR ratio is given by |M|/n.The computational complexity of finding the shared MPR sets that minimize the MPR ratio is expected to be NP-complete, because the basic structure of the problem is the same as the MPR problem [1] described in Section 2.2. Then, we use a heuristic shared MPR selection algorithm, which is discussed in the next section.


## 3.1. Notation

We model a network as a unit disk graphG=(V,E), where V is a set of nodes in the network and E is a set of available links between nodes. Each node knows partial information of G by receiving HELLO and TC messages. The total number of nodes in the network is denoted by n(=|V|). For simplicity, we assume that the transmission range r of each node is uniform. There is an edge (v,w)∈E if and only if d(v,w)<r, where the function d() is a distance between two nodes. A region D(v,x) is defined as a disk with radius x that centers v. D(v,r) is called a unit disk of v. A node in the unit disk D(v,r) is called a one-hop neighbor of v.Our analysis assumes that nodes are placed uniformly in a two-dimensional region. The expected number of nodes in a one-hop region is denoted byn′. For example, if the region is a square of side R and the number of nodes in the region is n, then(3)n′=πr2nR×R.We use the term “density” (defined as n′) instead of the number of nodes in a unit square, that is, n/R2, for convenience.


## 3.2. Distance to Two-Hop Neighbors

Suppose that there are two nodesv and u such that d(v,u)=2r-δ≤2r, as shown in Figure 1(a). We discuss the condition where u is a two-hop neighbor of v. Obviously, node u is a two-hop neighbor of v if and only if there is at least one node w that satisfies d(v,w)≤r and d(w,u)≤r. In other words, d(v,u)≤2r is a necessary but insufficient condition for u being a two-hop neighbor of v.Figure 1
Determining whetheru is a two-hop neighbor of v.
(a)
Nodeu is a two-hop neighbor of v, if w covers u
(b)
Nodeu is not a two-hop neighbor of v if there is no node ∈WThe regionW is defined as W=D(v,r)∩D(u,r), as shown in Figure 1(b). Node u is a two-hop neighbor of v if and only if there is at least one node w∈W. The size of region W is denoted by S(W) and expressed as follows:(4)SW=2πr2·2θ2π-r2sin⁡θcos⁡⁡θ=r22θ-sin⁡2θ,where θ=θ(δ)=arccos⁡(2r-δ/2r). We define a probability function p(δ,n′) that expresses the probability that u is a two-hop neighbor of v when u is 2r-δ away from v. Suppose that node w is a two-hop neighbor of v. The probability that w is not in the region W is (πr2-SW)/πr2. Node u is a two-hop neighbor of v if there is at least one one-hop neighbor of v in W. Therefore, in uniformly distributed networks, we approximate(5)pδ,n′=1-πr2-SWπr2n′,where n′ is the average number of a node’s one-hop neighbors.We try to expect the number of two-hop neighbors ofv in various densities. First, we denote the expected number of nodes in D(v,2r) by f(2r)=π(2r)2·n′/πr2=4n′. Note that f(2r) includes the number of one-hop neighbors in D(v,r). We suppose that f′(x)=2n′x/r2 is the derivative of f(x). We denote the expected number of two-hop neighbors of v by E[|N2(v)|]. We derive E[|N2(v)|] using a function g(x,n′), which is the expected number of two-hop neighbors of v in a disk D(v,x) with the radius x(r≤x≤2r) and the density n′. The function g(x,n′) is derived using f′(x) and p(δ,n′). Consider(6)EN2v=g2r,n′(7)gx,n′=∫rxf′y·p2r-y,n′dy.Figure2 shows the numerical results of g(x,n′) with various radii x and densities n′=∞, 80, 40, 20, 10, and 5. From these results, we confirm that nodes close to the border of D(v,2r) are rarely a two-hop neighbor of v under moderately high-density conditions.Figure 2
The expected number of two-hop neighbors in a disk of radiusx.To ensure the rareness of two-hop neighbors close to the border ofD(v,2r) in moderately dense networks, Table 1 shows the radius x of a disk covering q=70%–95% of two-hop neighbors. The radius x satisfies (q/100)g(2r,n′)=g(x,n′) for each q and n′. We conclude that, even when density n′=80 (a very high density where the expected number of two-hop neighbors is 214), 95% of the two-hop neighbors (nearly 203 nodes) have δ>0.10r=(2-1.90)r, θ>0.32=18°. In a moderately dense network, such as n′=20 (where the expected number of two-hop neighbors is 44), 90% of two-hop neighbors (40 nodes) have δ>0.22, θ>0.47=27°, and 70% of two-hop neighbors (31 nodes) have δ>0.39, θ>0.64=36°. From this observation, we expect that some small number of MPRs can cover all of a node’s two-hop neighbors in moderately dense wireless multihop networks. This expectation is confirmed by the simulation illustrated in Figure 7 of Section 4.Table 1
The radiusx of a disk that covers q% of two-hop neighbors on various density n′.
q
n
′
=
∞
80
40
20
10
5
70%
1.76
r
1.69
r
1.66
r
1.61
r
1.55
r
1.51
r
80%
1.84
r
1.77
r
1.74
r
1.69
r
1.64
r
1.59
r
90%
1.92
r
1.85
r
1.82
r
1.78
r
1.74
r
1.70
r
95%
1.96
r
1.90
r
1.87
r
1.84
r
1.81
r
1.78
r


## 3.3. Conventional MPR Selection of a Node

Here, we review OLSR’s conventional MPR selection in which any node selects its MPR set independently of its neighbors’ MPR sets. Understanding the symmetric property of this conventional selection will be helpful in understanding how MPRs can be shared as described in Section3.4.Suppose that there are two nodesu1 and u2 that satisfy d(v,u1)=2r-δ1 and d(v,u2)=2r-δ2 and that they are node v’s two-hop neighbors, as shown in Figure 3. We assume that u1 and u2 are closer to each other than to other v’s two-hop neighbors.Figure 3
Covering two two-hop neighbors.The regionsW1 and W2 are defined similar to W in Section 3.2. Consider(8)W1=Dv,r∩Du1,rW2=Dv,r∩Du2,r,where u1 (or u2) is a two-hop neighbor of v if and only if there is at least one node w1∈W1 (or w2∈W2). The angles θ1 and θ2 are defined as θ1=θ(δ1) and θ2=θ(δ2), respectively.The following discussion assumes that there are multiple nodes inW1 and W2; this avoids the case of having only one node in W1 and W2, in which case, the nodes must be added to MPR set M(v) in step 2 of the heuristic described in Section 2.2.If there is at least one nodew in W1∩W2, which is the hatched region in Figure 3, then u1 and u2 can be covered by single node w(=w1=w2). If there is no node in W1∩W2, there must be at least one node w1∈W1∩W2¯ and the other node must be w2∈W1¯∩W2 to cover u1 and u2, respectively.We denote∠u1vu2 by ϕ and suppose that δ1≥δ2; that is, θ1≥θ2. The inclusion relation between W1 and W2 is divided into the following three cases, where S() is the size of the region:(1)
ϕ>θ1+θ2; that is, S(W1∩W2)=0.(2)
θ1+θ2≥ϕ and ϕ>θ1-θ2, as shown in Figure 3; that is, S(W1∩W2)>0.(3)
θ1+θ2≥ϕ and θ1-θ2≥ϕ; that is, W2⊆W1.In the first case, two nodesw1∈W1 and w2∈W2 are selected as MPRs of v to cover u1 and u2, respectively. Two nodes w1 and w2 are selected independent of each other.In the second case, if there is at least one nodew∈W1∩W2, the optimal or heuristic MPR selection algorithm selects w as an MPR of v. However, this selection depends on the existence of other two-hop neighbors. The nodes in v’s MPR set are either a single node w or two nodes w1∈W1∩W2¯ and w2∈W2∩W1¯.In the third case, if the optimal or heuristic MPR selection algorithm selects a nodew2∈W2 as an MPR to cover u2, then node w2 also covers u1.The number of MPRs of nodev changes by selecting the second case. Each iteration of step 3 in the heuristic greedily adds a node in M(v); thus, the algorithm covers the maximum number of uncovered nodes in N2(v).


## 3.4.  Sharing an MPR with a Neighbor

Considering the symmetric property of conventional MPR selection (see Section3.3), we explain how sharing MPRs with a neighbor is possible. Suppose that there are two nodes v1 and v2, each of which is a one-hop neighbor of the other. Sharing MPRs means that v1 and v2 select the same node as their MPR.First, we discuss the condition in which sharing MPRs is not allowed. As shown in Figure4(a), if v1 has a two-hop neighbor u such that u is not a two-hop neighbor of v2, then v2 has no one-hop neighbor in W1. In this condition, v1 and v2 cannot share an MPR to cover u.Figure 4
Covering two two-hop neighbors.
(a)
u is a two-hop neighbor of v1 but not a two-hop neighbor of v2
(b)
u is a two-hop neighbor of both v1 and v2However, if there is a nodeu such that u is a two-hop neighbor of both v1 and v2, as shown in Figure 4(b), and there is at least one node w∈W1∩W2, then v1 and v2 can select a node w as an MPR to cover u, thus sharing an MPR.The sharable condition discussed above is symmetrical to the second case of conventional MPR selection, which is described in Section3.3. However, the optimal and heuristic MPR selection described in Section 2.2 does not consider such sharing.Note that the two-hop coverage ofv1 and v2’s MPR set is maintained regardless of whether the MPR is shared between them. The MPR is still guaranteed to construct the shortest path between any pair of nodes in the network, in contrast to CDSs, which do not guarantee the shortest path.


## 3.5.  The Proposed Shared MPR Sets

The concept of shared MPR sets was first introduced by Yamada et al. [7]. They call the concept an MPR selection “redundancy,” which is defined as follows:for a combination of MPR sets of all nodes, if the number of MPRs in the network is greater than that of other combinations of MPR sets, the combination of MPR sets is redundant.We define the MPR ratio to measure the degree of sharing. The ratio for shared MPR selection will be less than that for conventional MPR selection. We also define the number of MPRs per node to compare the average size of each node’s MPR sets; this number will be constant for shared and conventional MPR selections. The MPR ratio and number of MPRs per node are defined as follows:(9)the  MPR  ratio=⋃v∈VMvn,the  number  of  MPRs  per  node=∑v∈VMvn,where V is the set of nodes in the network, M(v) is an MPR set of node v, and n is the number of nodes in the network (i.e., n=|V|). The MPR ratio shows the number of nodes selected as MPRs by at least one neighbor in the network. If the ratio is 1, then all nodes are selected as MPRs. The number of MPRs per node shows the average number of MPRs selected by a node.To computeM(v) for all nodes, we define a bipartite graph G=(N∪N2,E), where N is the union of one-hop neighbor sets N(v) of all v∈V and N2 is the target pairs set derived by N2(v) of all v∈V. Consider(10)N=⋃v∈VNv(11)N2=v,u∣v∈V,u∈N2v(12)E=w,p∣w∈N,p=v,u∈N2,w∈Nv,u∈Nw,where (w,p)=(w,(v,u))∈E means that there are two links (v,w) and (w,u); N and N2 satisfy the conditions of |N|≤n and |N2|=Σv∈V|N2(v)|.To achieve the smallest MPR ratio, we need to find the smallest subset ofN that covers all of N2. We define the coverage that w∈N covers as (v,u)∈N2 if and only if w∈N(v) and u∈N(w); that is, (w,p)∈E. In conventional MPR selection, the coverage is defined for each node v as w∈N(v) covers u∈N2(v) if and only if u∈N(w); that is, (w,u)∈EP2.LetM be a subset of N. The set M is called a global MPR set if a subset M covers all pairs of N2. For every node v∈V, each node u∈N2(v) has one or more one-hop neighbors in a global MPR set. Then, N(v)∩M can be a candidate MPR set of v. Each node can select N(v)∩M or its subset as the shared MPR set. The MPR ratio is given by |M|/n.The computational complexity of finding the shared MPR sets that minimize the MPR ratio is expected to be NP-complete, because the basic structure of the problem is the same as the MPR problem [1] described in Section 2.2. Then, we use a heuristic shared MPR selection algorithm, which is discussed in the next section.


## 4. Experiments of Sharing MPRs with Neighbors

### 4.1. A Heuristic Shared MPR Selection Algorithm

We use the following algorithm in our experiment to show that shared MPR sets can reduce the routing overhead, especially the number of TC messages; however, note that because it is a centralized algorithm, it is not directly applicable to OLSR or other MANET routing protocols.The algorithm adopts the greedy heuristic proposed by Qayyum et al. [1]. The primary difference between it and the conventional OLSR algorithm is that this algorithm runs on a whole network (i.e., is nondistributed) rather than on each node. Only the final step (4) runs on each node.The input of this algorithm isG as defined in Section 3.5, and the output is the MPR sets M(v) for all nodes. The heuristic algorithm is as follows:(1)
Start with an empty global MPR setM.(2)
First, select, as global MPRs, those nodes inN that are the only neighbors of pairs in N2, and add these nodes to M.(3)
While there exists at least one pair inN2 that is not covered by M, one has the following:
(a)
For each node inN that is not in M, compute the number of pairs that it covers among the uncovered pairs in N2.(b)
Add the node ofN in M for which this number is maximum.(4)
For each nodev, run the heuristic described in Section 2.2 to compute M(v). However, N(v)∩M is used instead of N(v) as the heuristic’s input. The heuristic outputs the MPR set M(v) for each v.


### 4.2. Metrics and Method

We use five metrics to explain our simulation results. The first two metrics concern the number of MPRs: the MPR ratio and the number of MPRs per node (described in (9)).The remaining three metrics concern the routing protocol’s communication overhead: the number of TC messages, the number of OLSR packets, and the total size of OLSR packets (in bytes). These three metrics are measured at the data link layer using a simulator log and are normalized by dividing the number of nodes and the simulation duration. Note that we count TC messages that are generated by a node and are forwarded by other nodes.Moreover, to clearly show the redundancy of conventional MPR selection, the MPR ratio and number of TC messages in conventional MPR and shared MPR selections are compared. We define the MPR redundancy of conventional MPR selection as(13)⋃v∈VMvof  conventional  MPR  selection⋃v∈VMvof  shared  MPR  selection-1.We define the TC message redundancy of conventional MPR selection as(14)#of  TC  messages  of  conventional  MPR  selection#of  TC  messages  of  shared  MPR  selection-1.We use the ns-2 simulator (ver. 2.29) with UM-OLSR v0.8.8 [14]. The simulation is set so that each node has an IEEE 802.11 interface, the transmission range is r=250 meters, and all nodes are distributed randomly in a region of 2000×2000 meters2 (i.e., an 8r×8r region); the HELLO and TC message intervals are set to 2 and 5 s, respectively, and all nodes are set towill_default willingness. The simulation for each scenario runs for 100 s, and the number of messages is counted during the last 80 s of each simulation.For the simulation, we assume that nodes do not move. We show the results of conventional MPR selection adopted in OLSR as well as shared MPR selection (which are described in Section4.1). The number of nodes n in the network varies from 20 to 300. For each number of nodes, fifty different node topologies are simulated; the average results are shown in Section 4.3. Note that some topologies with small numbers of nodes are not fully connected graphs.Regarding communication overhead, we describe how OLSR is modified to evaluate the heuristic shared MPR selection algorithm. Communication overhead caused by aggregatingG to a virtual server and informing the global MPR set M from the virtual server is ignored. If it is included, the last two metrics (the number of OLSR packets and the total size of OLSR packets (in bytes)) increase, but the other three do not change. To suppress the increase in the first two metrics, we need to consider using a distributed algorithm; this is the most important goal of our future study. In our simulation, there is no difference in the number of HELLO messages when conventional MPR selection in OLSR is used and when shared MPR selection is used; in other words, HELLO messages are used to create partial two-hop neighbor information GP2(v) for each node v, and MPR set M(v) is broadcasted to the neighbors of v using HELLO messages.We assume that the wireless multihop network is moderately dense (meaning that each node has about 5 to 10 one-hop neighbors). Statistically, the number of one-hop neighbors for each node, except for those close to the border of the8r×8r region, is n′=π×2502×n/(2000×2000) as defined in (3). The number of strict two-hop neighbors is expected to be E[|N2(v)|] based on (6). In networks of 300 nodes, there are statistically 14.7 one-hop neighbors and 34.2 strict two-hop neighbors for each node.


### 4.3. Simulation Results

Figures5–10 show the simulation results for each metric. In each figure (except Figure 6), the results of conventional MPR selection and shared MPR selection are shown with the labels “Conventional” and “Shared,” respectively.Figure 5
MPR ratio.Figure 6
MPR and TC message redundancy.Figure 7
Number of MPRs per node.Figure 8
Number of TC messages per node per second.Figure 9
Number of OLSR packets per node per second.Figure 10
Size of OLSR packets (in bytes) per node per second.The plot in Figure5 shows that the MPR ratio for conventional MPR selection increases as the number of nodes increases (which is also discussed in Section 3.2). Wu et al. [5] have proved that this ratio will eventually increase to 1; however, the speed of increase shown in Figure 5 is rather slow.By comparing the MPR ratios of conventional MPR selection with those of shared MPR selection (in Figure5), we see that conventional MPR selection has over 10% redundancy in networks containing 100 or more nodes. Figure 6 charts MPR redundancy, which is defined in (13), thereby showing the redundancy more clearly. Based on the results shown in Figure 6, we determine that there is little redundancy in the low density networks of less than 50 nodes and large redundancy in moderately dense networks of over 100 nodes. In other words, when the average number of one-hop neighbors is greater than 5 (n′=4.9 when n=100), there is 10% redundancy in conventional MPR selection.Figure7 shows the average number of MPRs per node. Conventional MPR and shared MPR selection have almost the same results. The number of MPRs increases slowly when the number of nodes in the network increases. Even when n=300 (n′=14.7), no more than an average of 4.5 nodes are selected as MPRs by a node.Figures8 to 10 show the routing overhead results. These results are averaged per node and per second. Comparing conventional MPR selection to shared MPR selection, we find that, in all three metrics, shared MPR selection is able to reduce routing overhead in networks with 100 or more nodes.When the number of nodes is greater than or equal to 80, the reduction ratio of shared MPR selection relative to conventional MPR selection is around 9%–12% in the number of TC messages (see Figure8). More importantly, when the number of nodes is between 140 and 260, the reduction ratio is around 11%-12%. These results are also shown as TC message redundancy (defined in (14)) in Figure 6. From Figure 6, we observe that TC message redundancy is nearly proportional to MPR redundancy in networks of less than 200 nodes; however, we observe a different trend in networks of over 200 nodes. The reason for this different trend in high-density networks cannot be clearly explained, but it is possible that TC message redundancy decreases as networks increase in density. Future studies will examine this trend in greater detail to determine its cause.Shared MPR selection also reduces the number of OLSR packets, depicted in Figure9, and the reduction ratio here is even lower than that of the number of TC messages. Most likely, the ability to piggyback several messages into one packet causes the number of packets to decrease. The reduction ratio is around 9%-10% when the number of nodes is between 140 and 260 and around 5%–9% when the number of nodes is between 80 and 120.Shared MPR selection also decreases the total size of OLSR packets (in bytes), as depicted in Figure10, and the reduction ratio here is even lower than that of the number of TC messages and the number of OLSR packets. Although the headers of UDP, IP, and MAC will affect these results, the reduction ratio is around 7% when the number of nodes is between 140 and 260 and 4%–6% when the number of nodes is between 80 and 120.To summarize the simulation results, we see that the MPR ratio increases slowly as the number of nodes in the network also increases, shared MPR selection maintains smaller MPR ratios and less routing overhead than does conventional MPR selection, and conventional MPR selection has room for improvement.


### 4.4.  Comparison with CDS

To compare the MPR ratio with the CDS ratio, we refer to some results reported by Wu et al. [5]. Their evaluation simulates CDS within a 4r×4r region. We increase the size of the CDS as the number of nodes in the network also increases. For networks of 30, 50, and 80 nodes, the CDS sizes are around 15 (50%), 20 (40%), and 25 (30%), respectively. The CDS ratio shown in parentheses is obtained by dividing the CDS size by the number of nodes in a network. Comparing the density of nodes in their 4r×4r region with that in our 8r×8r region, 30, 50, and 80 nodes in the former region have similar densities to 120, 200, and 300 nodes in the latter region.In high-density networks (e.g., in our simulation, networks of 300 nodes), the MPR ratios of conventional MPR and shared MPR selection are 72% and 64%, respectively, and the CDS ratio of the corresponding network is only 30%. Thus, both MPR ratios in Figure5 are higher than the CDS ratio.In moderately dense networks of 200 nodes (see Figure5), the MPR ratio of conventional MPR selection is 65% (that of shared MPR selection is 57%), and the CDS ratio is 40% in a network of similar density.When the network is not so dense, the difference between the MPR and CDS ratios is small. In low-density networks (e.g., in our simulation, the network of 120 nodes (n′=5.9)), the MPR ratio of conventional MPR selection is 57% (that of shared MPR selection is 52%), and the CDS ratio is 50% in a network of similar density.Consequently, if there is a feasible solution for calculating a CDS in a distributed manner and the network is dense, then the CDS will perform better than MPRs; however, the CDS does not guarantee the shortest path between any pair of nodes. Therefore, the next best choice is to find a feasible method for calculating shared MPRs in a distributed manner.Comparing the MPR ratio with the CDS ratio, we see that the CDS achieves the smallest ratio and that shared MPR selection achieves the next smallest ratio.


## 4.1. A Heuristic Shared MPR Selection Algorithm

We use the following algorithm in our experiment to show that shared MPR sets can reduce the routing overhead, especially the number of TC messages; however, note that because it is a centralized algorithm, it is not directly applicable to OLSR or other MANET routing protocols.The algorithm adopts the greedy heuristic proposed by Qayyum et al. [1]. The primary difference between it and the conventional OLSR algorithm is that this algorithm runs on a whole network (i.e., is nondistributed) rather than on each node. Only the final step (4) runs on each node.The input of this algorithm isG as defined in Section 3.5, and the output is the MPR sets M(v) for all nodes. The heuristic algorithm is as follows:(1)
Start with an empty global MPR setM.(2)
First, select, as global MPRs, those nodes inN that are the only neighbors of pairs in N2, and add these nodes to M.(3)
While there exists at least one pair inN2 that is not covered by M, one has the following:
(a)
For each node inN that is not in M, compute the number of pairs that it covers among the uncovered pairs in N2.(b)
Add the node ofN in M for which this number is maximum.(4)
For each nodev, run the heuristic described in Section 2.2 to compute M(v). However, N(v)∩M is used instead of N(v) as the heuristic’s input. The heuristic outputs the MPR set M(v) for each v.


## 4.2. Metrics and Method

We use five metrics to explain our simulation results. The first two metrics concern the number of MPRs: the MPR ratio and the number of MPRs per node (described in (9)).The remaining three metrics concern the routing protocol’s communication overhead: the number of TC messages, the number of OLSR packets, and the total size of OLSR packets (in bytes). These three metrics are measured at the data link layer using a simulator log and are normalized by dividing the number of nodes and the simulation duration. Note that we count TC messages that are generated by a node and are forwarded by other nodes.Moreover, to clearly show the redundancy of conventional MPR selection, the MPR ratio and number of TC messages in conventional MPR and shared MPR selections are compared. We define the MPR redundancy of conventional MPR selection as(13)⋃v∈VMvof  conventional  MPR  selection⋃v∈VMvof  shared  MPR  selection-1.We define the TC message redundancy of conventional MPR selection as(14)#of  TC  messages  of  conventional  MPR  selection#of  TC  messages  of  shared  MPR  selection-1.We use the ns-2 simulator (ver. 2.29) with UM-OLSR v0.8.8 [14]. The simulation is set so that each node has an IEEE 802.11 interface, the transmission range is r=250 meters, and all nodes are distributed randomly in a region of 2000×2000 meters2 (i.e., an 8r×8r region); the HELLO and TC message intervals are set to 2 and 5 s, respectively, and all nodes are set towill_default willingness. The simulation for each scenario runs for 100 s, and the number of messages is counted during the last 80 s of each simulation.For the simulation, we assume that nodes do not move. We show the results of conventional MPR selection adopted in OLSR as well as shared MPR selection (which are described in Section4.1). The number of nodes n in the network varies from 20 to 300. For each number of nodes, fifty different node topologies are simulated; the average results are shown in Section 4.3. Note that some topologies with small numbers of nodes are not fully connected graphs.Regarding communication overhead, we describe how OLSR is modified to evaluate the heuristic shared MPR selection algorithm. Communication overhead caused by aggregatingG to a virtual server and informing the global MPR set M from the virtual server is ignored. If it is included, the last two metrics (the number of OLSR packets and the total size of OLSR packets (in bytes)) increase, but the other three do not change. To suppress the increase in the first two metrics, we need to consider using a distributed algorithm; this is the most important goal of our future study. In our simulation, there is no difference in the number of HELLO messages when conventional MPR selection in OLSR is used and when shared MPR selection is used; in other words, HELLO messages are used to create partial two-hop neighbor information GP2(v) for each node v, and MPR set M(v) is broadcasted to the neighbors of v using HELLO messages.We assume that the wireless multihop network is moderately dense (meaning that each node has about 5 to 10 one-hop neighbors). Statistically, the number of one-hop neighbors for each node, except for those close to the border of the8r×8r region, is n′=π×2502×n/(2000×2000) as defined in (3). The number of strict two-hop neighbors is expected to be E[|N2(v)|] based on (6). In networks of 300 nodes, there are statistically 14.7 one-hop neighbors and 34.2 strict two-hop neighbors for each node.


## 4.3. Simulation Results

Figures5–10 show the simulation results for each metric. In each figure (except Figure 6), the results of conventional MPR selection and shared MPR selection are shown with the labels “Conventional” and “Shared,” respectively.Figure 5
MPR ratio.Figure 6
MPR and TC message redundancy.Figure 7
Number of MPRs per node.Figure 8
Number of TC messages per node per second.Figure 9
Number of OLSR packets per node per second.Figure 10
Size of OLSR packets (in bytes) per node per second.The plot in Figure5 shows that the MPR ratio for conventional MPR selection increases as the number of nodes increases (which is also discussed in Section 3.2). Wu et al. [5] have proved that this ratio will eventually increase to 1; however, the speed of increase shown in Figure 5 is rather slow.By comparing the MPR ratios of conventional MPR selection with those of shared MPR selection (in Figure5), we see that conventional MPR selection has over 10% redundancy in networks containing 100 or more nodes. Figure 6 charts MPR redundancy, which is defined in (13), thereby showing the redundancy more clearly. Based on the results shown in Figure 6, we determine that there is little redundancy in the low density networks of less than 50 nodes and large redundancy in moderately dense networks of over 100 nodes. In other words, when the average number of one-hop neighbors is greater than 5 (n′=4.9 when n=100), there is 10% redundancy in conventional MPR selection.Figure7 shows the average number of MPRs per node. Conventional MPR and shared MPR selection have almost the same results. The number of MPRs increases slowly when the number of nodes in the network increases. Even when n=300 (n′=14.7), no more than an average of 4.5 nodes are selected as MPRs by a node.Figures8 to 10 show the routing overhead results. These results are averaged per node and per second. Comparing conventional MPR selection to shared MPR selection, we find that, in all three metrics, shared MPR selection is able to reduce routing overhead in networks with 100 or more nodes.When the number of nodes is greater than or equal to 80, the reduction ratio of shared MPR selection relative to conventional MPR selection is around 9%–12% in the number of TC messages (see Figure8). More importantly, when the number of nodes is between 140 and 260, the reduction ratio is around 11%-12%. These results are also shown as TC message redundancy (defined in (14)) in Figure 6. From Figure 6, we observe that TC message redundancy is nearly proportional to MPR redundancy in networks of less than 200 nodes; however, we observe a different trend in networks of over 200 nodes. The reason for this different trend in high-density networks cannot be clearly explained, but it is possible that TC message redundancy decreases as networks increase in density. Future studies will examine this trend in greater detail to determine its cause.Shared MPR selection also reduces the number of OLSR packets, depicted in Figure9, and the reduction ratio here is even lower than that of the number of TC messages. Most likely, the ability to piggyback several messages into one packet causes the number of packets to decrease. The reduction ratio is around 9%-10% when the number of nodes is between 140 and 260 and around 5%–9% when the number of nodes is between 80 and 120.Shared MPR selection also decreases the total size of OLSR packets (in bytes), as depicted in Figure10, and the reduction ratio here is even lower than that of the number of TC messages and the number of OLSR packets. Although the headers of UDP, IP, and MAC will affect these results, the reduction ratio is around 7% when the number of nodes is between 140 and 260 and 4%–6% when the number of nodes is between 80 and 120.To summarize the simulation results, we see that the MPR ratio increases slowly as the number of nodes in the network also increases, shared MPR selection maintains smaller MPR ratios and less routing overhead than does conventional MPR selection, and conventional MPR selection has room for improvement.


## 4.4.  Comparison with CDS

To compare the MPR ratio with the CDS ratio, we refer to some results reported by Wu et al. [5]. Their evaluation simulates CDS within a 4r×4r region. We increase the size of the CDS as the number of nodes in the network also increases. For networks of 30, 50, and 80 nodes, the CDS sizes are around 15 (50%), 20 (40%), and 25 (30%), respectively. The CDS ratio shown in parentheses is obtained by dividing the CDS size by the number of nodes in a network. Comparing the density of nodes in their 4r×4r region with that in our 8r×8r region, 30, 50, and 80 nodes in the former region have similar densities to 120, 200, and 300 nodes in the latter region.In high-density networks (e.g., in our simulation, networks of 300 nodes), the MPR ratios of conventional MPR and shared MPR selection are 72% and 64%, respectively, and the CDS ratio of the corresponding network is only 30%. Thus, both MPR ratios in Figure5 are higher than the CDS ratio.In moderately dense networks of 200 nodes (see Figure5), the MPR ratio of conventional MPR selection is 65% (that of shared MPR selection is 57%), and the CDS ratio is 40% in a network of similar density.When the network is not so dense, the difference between the MPR and CDS ratios is small. In low-density networks (e.g., in our simulation, the network of 120 nodes (n′=5.9)), the MPR ratio of conventional MPR selection is 57% (that of shared MPR selection is 52%), and the CDS ratio is 50% in a network of similar density.Consequently, if there is a feasible solution for calculating a CDS in a distributed manner and the network is dense, then the CDS will perform better than MPRs; however, the CDS does not guarantee the shortest path between any pair of nodes. Therefore, the next best choice is to find a feasible method for calculating shared MPRs in a distributed manner.Comparing the MPR ratio with the CDS ratio, we see that the CDS achieves the smallest ratio and that shared MPR selection achieves the next smallest ratio.


## 5. Discussion

There are several distributed heuristic algorithms for calculating shared MPR sets, such as those put forth by Yamada et al. [7], Maccari and Lo Cigno [8], and ourselves [9]. However, in those studies, the sharing mechanism of MPR is not well analyzed and no bound is shown.In Section4, we simulate only a static environment; that is, nodes do not move in the simulation area. This limitation is the result of the high computational complexity associated with the centralized algorithm described in Section 4.1, which exists because the structure of the problem solved by the centralized algorithm is the same as the local MPR computation, which is an NP-complete problem [1]. Furthermore, the problem size increases; for example, |N| of (10) is larger than |N(v)| if the graph G=(V,E) is not a complete graph, and |N2| of (11) is about |V| times larger than |N2(v)|.We employ the unit disk graph model for analysis and simulation. This model is valuable for theoretical discussions but does not represent the real environments of wireless communication. For an explanation of the differences between the model and real environments, we refer to the communication gray zones introduced by Lundgren et al. [15]. These zones are defined as areas where data messages cannot be exchanged—although HELLO messages indicate neighbor reachability—for various reasons including bit error rate, variable transmission rate, packet size, and different MAC layer handling between broadcast and unicast packets. To create simulations close to real environment, Chen et al. [16] and Pei and Henderson [17] have redesigned or tuned the IEEE 802.11 WLAN simulation model. More realistic evaluations can be performed with these models than with previous models. Furthermore, when we evaluate urban environments in our future study, obstacles should be modeled; for example, Sommer et al. [18] have proposed an empirical model of IEEE 802.11p path loss, including the attenuation of obstacles. For more realistic simulations, especially with mobile scenarios, these models will be valuable.If nodes are allowed to move, then node mobility will be another important aspect to be considered in wireless multihop networks. Maccari and Lo Cigno [8] have proposed a stability-driven MPR choice strategy to minimize changes in the MPR selector sets in mobile scenarios. Minimizing these changes implies reducing the routing table calculation in each node. Musolesi and Mascolo [19] have also proposed a mobility model; theirs is based on community such as family members sharing a home or colleagues sharing an office. When mobile nodes are carried by humans, the community structures of humans strongly affect the dynamics of the mobile nodes. Therefore, the model put forth by Musolesi and Mascolo assigns each square area to a community. They have compared their mobility model with the Intel trace [20] and random waypoint mobility model in terms of intercontact times and contact durations. Our future work will include finding a suitable mobility model for evaluation.


## 6. Conclusion

In this paper, we explored MPR selection in moderately dense wireless multihop networks.We have analyzed the distance to a two-hop neighbor in moderately dense networks and explained that nodes close to the border of a two-hop diskD(v,2r), where r is a transmission range, have little probability of being a two-hop neighbor of v. From this observation, we expected that some small number of MPRs could cover all two-hop neighbors of a node, even in moderately dense wireless multihop networks. This expectation was confirmed by the simulation of up to 300 nodes in an 8r×8r region.We have also demonstrated the redundancy of conventional MPR sets and described a definition of shared MPR sets that minimizes the MPR ratio. We then provided a heuristic algorithm to select shared MPR sets. This heuristic is not applicable to the OLSR protocol, because it is not a distributed algorithm; however, the heuristic is valuable for showing the redundancy of conventional MPR selection. With this heuristic, we simulated some network topologies and measured the MPR ratio and routing overhead. Simulation results show that the redundancy in the number of TC messages, the number of OLSR packets, and the total size of OLSR packets is up to 12%, 10%, and 7%, respectively. We will continue to explore the feasibility of shared MPR selection as well as CDS schemes.



---

*Source: 486023-2015-06-01.xml*